Example 2 Clustering Geometric ObjectsΒΆ

In this example we will look at a few of the tools provided by the clifford package for (4,1) conformal geometric algebra (CGA) and see how we can use them in a practical setting to cluster geometric objects via the simple K-means clustering algorithm provided in clifford.tools

As before the first step in using the package for CGA is to generate and import the algebra:

[1]:
from clifford.g3c import *
print('e1*e1 ', e1*e1)
print('e2*e2 ', e2*e2)
print('e3*e3 ', e3*e3)
print('e4*e4 ', e4*e4)
print('e5*e5 ', e5*e5)
e1*e1  1.0
e2*e2  1.0
e3*e3  1.0
e4*e4  1.0
e5*e5  -1.0

The tools submodule of the clifford package contains a wide array of algorithms and tools that can be useful for manipulating objects in CGA. In this case we will be generating a large number of objects and then segmenting them into clusters.

We first need an algorithm for generating a cluster of objects in space. We will construct this cluster by generating a random object and then repeatedly disturbing this object by some small fixed amount and storing the result:

[2]:
from clifford.tools.g3c import *
import numpy as np

def generate_random_object_cluster(n_objects, object_generator, max_cluster_trans=1.0, max_cluster_rot=np.pi/8):
    """ Creates a cluster of random objects """
    ref_obj = object_generator()
    cluster_objects = []
    for i in range(n_objects):
        r = random_rotation_translation_rotor(maximum_translation=max_cluster_trans, maximum_angle=max_cluster_rot)
        new_obj = apply_rotor(ref_obj, r)
        cluster_objects.append(new_obj)
    return cluster_objects

We can use this function to create a cluster and then we can visualise this cluster with GAOnline using the built in tools in clifford.

[3]:
from clifford.tools.g3c.GAOnline import *
clustered_circles = generate_random_object_cluster(10, random_circle)
sc = GAScene()
for c in clustered_circles:
    sc.add_circle(c,'rgb(255,0,0)')
print(sc)
DrawCircle(-(0.31495^e123) + (7.17423^e124) + (7.21242^e125) - (2.67545^e134) - (2.70477^e135) + (0.34338^e145) + (3.79502^e234) + (3.82412^e235) - (0.20276^e245) - (0.10603^e345),rgb(255,0,0));
DrawCircle(-(0.34619^e123) + (7.40458^e124) + (7.4434^e125) - (4.22417^e134) - (4.26234^e135) + (0.34262^e145) + (2.86528^e234) + (2.87949^e235) + (0.01735^e245) - (0.14248^e345),rgb(255,0,0));
DrawCircle(-(0.38917^e123) + (7.59451^e124) + (7.63036^e125) - (5.36773^e134) - (5.41009^e135) + (0.33205^e145) + (1.81861^e234) + (1.82788^e235) - (0.01337^e245) - (0.07006^e345),rgb(255,0,0));
DrawCircle(-(0.33054^e123) + (7.3166^e124) + (7.35529^e125) - (3.38137^e134) - (3.41555^e135) + (0.36067^e145) + (3.44481^e234) + (3.46716^e235) - (0.09145^e245) - (0.12755^e345),rgb(255,0,0));
DrawCircle(-(0.41644^e123) + (9.10776^e124) + (9.15442^e125) - (3.02619^e134) - (3.05248^e135) + (0.23599^e145) + (2.88519^e234) + (2.90242^e235) - (0.05362^e245) - (0.05694^e345),rgb(255,0,0));
DrawCircle(-(0.28874^e123) + (6.2713^e124) + (6.30297^e125) - (3.97306^e134) - (4.01134^e135) + (0.39578^e145) + (3.201^e234) + (3.2274^e235) - (0.22244^e245) - (0.06109^e345),rgb(255,0,0));
DrawCircle(-(0.36929^e123) + (7.71774^e124) + (7.75653^e125) - (4.50176^e134) - (4.53638^e135) + (0.25063^e145) + (3.45914^e234) + (3.48065^e235) - (0.08605^e245) - (0.06214^e345),rgb(255,0,0));
DrawCircle(-(0.26559^e123) + (7.7121^e124) + (7.76256^e125) - (1.0891^e134) - (1.1119^e135) + (0.45532^e145) + (1.26673^e234) + (1.27665^e235) - (0.04754^e245) - (0.06807^e345),rgb(255,0,0));
DrawCircle(-(0.3711^e123) + (7.19187^e124) + (7.22725^e125) - (4.3511^e134) - (4.38413^e135) + (0.22539^e145) + (4.69033^e234) + (4.71902^e235) - (0.10884^e245) - (0.08114^e345),rgb(255,0,0));
DrawCircle(-(0.38218^e123) + (8.39569^e124) + (8.4395^e125) - (2.63344^e134) - (2.66526^e135) + (0.39698^e145) + (2.27035^e234) + (2.28563^e235) - (0.07541^e245) - (0.0837^e345),rgb(255,0,0));

This cluster generation function appears in clifford tools by default and it can be imported as follows:

[4]:
from clifford.tools.g3c import generate_random_object_cluster

Now that we can generate individual clusters we would like to generate many:

[5]:
def generate_n_clusters( object_generator, n_clusters, n_objects_per_cluster ):
    object_clusters = []
    for i in range(n_clusters):
        cluster_objects = generate_random_object_cluster(n_objects_per_cluster, object_generator,
                                                         max_cluster_trans=0.5, max_cluster_rot=np.pi / 16)
        object_clusters.append(cluster_objects)
    all_objects = [item for sublist in object_clusters for item in sublist]
    return all_objects, object_clusters

Again this function appears by default in clifford tools and we can easily visualise the result:

[6]:
from clifford.tools.g3c import generate_n_clusters

all_objects, object_clusters = generate_n_clusters(random_circle, 2, 5)
sc = GAScene()
for c in all_objects:
    sc.add_circle(c,'rgb(255,0,0)')
print(sc)
DrawCircle((0.18847^e123) - (0.46054^e124) - (0.42175^e125) + (2.45154^e134) + (2.46017^e135) - (0.52577^e145) + (2.6336^e234) + (2.56812^e235) - (0.38215^e245) - (0.97236^e345),rgb(255,0,0));
DrawCircle((0.19525^e123) - (1.72862^e124) - (1.68681^e125) + (1.93897^e134) + (1.96064^e135) - (0.60713^e145) + (4.05555^e234) + (3.99514^e235) - (0.33365^e245) - (1.05015^e345),rgb(255,0,0));
DrawCircle((0.13632^e123) - (0.99946^e124) - (0.96176^e125) + (1.68312^e134) + (1.6934^e135) - (0.54083^e145) + (2.77363^e234) + (2.70775^e235) - (0.28399^e245) - (1.02264^e345),rgb(255,0,0));
DrawCircle((0.17477^e123) - (0.85345^e124) - (0.8131^e125) + (2.29789^e134) + (2.30607^e135) - (0.57048^e145) + (2.97195^e234) + (2.90736^e235) - (0.37072^e245) - (0.98843^e345),rgb(255,0,0));
DrawCircle((0.16788^e123) - (1.16012^e124) - (1.11624^e125) + (2.44176^e134) + (2.44544^e135) - (0.66381^e145) + (2.30653^e234) + (2.24386^e235) - (0.16991^e245) - (0.96216^e345),rgb(255,0,0));
DrawCircle((0.1832^e123) + (4.99017^e124) + (5.04079^e125) + (1.98042^e134) + (2.01543^e135) + (0.40661^e145) + (1.57092^e234) + (1.59999^e235) + (0.35798^e245) + (0.01407^e345),rgb(255,0,0));
DrawCircle((0.2265^e123) + (5.27015^e124) + (5.31985^e125) + (1.69627^e134) + (1.72785^e135) + (0.3628^e145) + (1.7867^e234) + (1.82084^e235) + (0.40245^e245) + (0.00654^e345),rgb(255,0,0));
DrawCircle((0.22816^e123) + (5.06037^e124) + (5.1059^e125) + (2.50686^e134) + (2.54722^e135) + (0.39484^e145) + (1.59984^e234) + (1.63037^e235) + (0.35765^e245) + (0.05235^e345),rgb(255,0,0));
DrawCircle((0.17873^e123) + (5.07051^e124) + (5.12457^e125) + (2.04778^e134) + (2.08218^e135) + (0.3563^e145) + (0.82342^e234) + (0.84641^e235) + (0.40299^e245) + (0.10489^e345),rgb(255,0,0));
DrawCircle((0.21159^e123) + (5.02229^e124) + (5.0706^e125) + (2.2345^e134) + (2.27209^e135) + (0.38191^e145) + (1.37815^e234) + (1.40794^e235) + (0.39252^e245) + (0.06984^e345),rgb(255,0,0));

Given that we can now generate multiple clusters of objects we can test algorithms for segmenting them.

The function run_n_clusters below generates a lot of objects distributed into n clusters and then attempts to segment the objects to recover the clusters.

[7]:
from clifford.tools.g3c.object_clustering import n_clusters_objects
import time

def run_n_clusters( object_generator, n_clusters, n_objects_per_cluster, n_shotgunning):
    all_objects, object_clusters = generate_n_clusters( object_generator, n_clusters, n_objects_per_cluster )
    [new_labels, centroids, start_labels, start_centroids] = n_clusters_objects(n_clusters, all_objects,
                                                                                initial_centroids=None,
                                                                                n_shotgunning=n_shotgunning,
                                                                                averaging_method='unweighted')
    return all_objects, new_labels, centroids

Lets try it!

[8]:
from clifford.tools.g3c.object_clustering import visualise_n_clusters

object_generator = random_circle

n_clusters = 3
n_objects_per_cluster = 10
n_shotgunning = 60
all_objects, labels, centroids = run_n_clusters(object_generator, n_clusters,
                                                     n_objects_per_cluster, n_shotgunning)

sc = visualise_n_clusters(all_objects, centroids, labels, object_type='circle',
                     color_1=np.array([255, 0, 0]), color_2=np.array([0, 255, 0]))
print(sc)
DrawCircle((0.08354^e123) + (0.06174^e124) + (0.08735^e125) + (0.57207^e134) + (0.55492^e135) - (0.18805^e145) + (2.89764^e234) + (2.88465^e235) - (0.89789^e245) + (0.506^e345),rgb(127, 127, 0));
DrawCircle((0.09592^e123) + (1.38394^e124) + (1.40687^e125) - (0.24195^e134) - (0.25906^e135) - (0.18906^e145) + (2.55284^e234) + (2.53551^e235) - (0.86021^e245) + (0.49912^e345),rgb(127, 127, 0));
DrawCircle((0.12709^e123) + (1.72306^e124) + (1.74778^e125) - (0.33079^e134) - (0.34745^e135) - (0.16151^e145) + (3.42012^e234) + (3.40494^e235) - (0.87099^e245) + (0.4878^e345),rgb(127, 127, 0));
DrawCircle((0.07715^e123) + (0.78403^e124) + (0.8071^e125) + (0.21049^e134) + (0.19358^e135) - (0.23488^e145) + (2.36502^e234) + (2.34769^e235) - (0.88341^e245) + (0.47133^e345),rgb(127, 127, 0));
DrawCircle((0.10317^e123) + (1.20832^e124) + (1.23098^e125) + (0.08345^e134) + (0.06649^e135) - (0.21702^e145) + (3.06964^e234) + (3.05181^e235) - (0.88289^e245) + (0.49035^e345),rgb(127, 127, 0));
DrawCircle((0.0998^e123) + (1.16857^e124) + (1.18983^e125) + (0.35685^e134) + (0.33951^e135) - (0.27901^e145) + (3.11823^e234) + (3.09909^e235) - (0.88831^e245) + (0.47324^e345),rgb(127, 127, 0));
DrawCircle((0.10986^e123) + (0.95546^e124) + (0.97847^e125) + (0.34137^e134) + (0.32444^e135) - (0.21876^e145) + (3.57103^e234) + (3.55363^e235) - (0.89923^e245) + (0.49631^e345),rgb(127, 127, 0));
DrawCircle((0.12957^e123) + (0.98655^e124) + (1.01318^e125) - (0.27943^e134) - (0.29349^e135) - (0.04957^e145) + (3.96139^e234) + (3.94681^e235) - (0.92505^e245) + (0.46105^e345),rgb(127, 127, 0));
DrawCircle((0.10582^e123) + (1.04403^e124) + (1.06702^e125) + (0.12894^e134) + (0.11206^e135) - (0.19454^e145) + (3.29549^e234) + (3.27801^e235) - (0.88847^e245) + (0.50434^e345),rgb(127, 127, 0));
DrawCircle((0.07623^e123) + (0.42182^e124) + (0.44572^e125) - (0.12322^e134) - (0.14027^e135) - (0.05576^e145) + (2.43973^e234) + (2.4237^e235) - (0.85349^e245) + (0.57183^e345),rgb(127, 127, 0));
DrawCircle((0.12261^e123) - (0.53071^e124) - (0.57688^e125) - (0.67589^e134) - (0.70642^e135) - (0.12231^e145) + (2.30777^e234) + (2.32969^e235) + (0.774^e245) + (0.45386^e345),rgb(255, 0, 0));
DrawCircle((0.14501^e123) - (1.45116^e124) - (1.498^e125) - (1.2784^e134) - (1.30925^e135) - (0.10422^e145) + (2.8118^e234) + (2.83178^e235) + (0.70814^e245) + (0.42189^e345),rgb(255, 0, 0));
DrawCircle((0.12218^e123) - (0.88344^e124) - (0.93154^e125) - (0.99679^e134) - (1.025^e135) - (0.18837^e145) + (2.34766^e234) + (2.3685^e235) + (0.7735^e245) + (0.37216^e345),rgb(255, 0, 0));
DrawCircle((0.13848^e123) - (0.78549^e124) - (0.83105^e125) - (0.76996^e134) - (0.804^e135) - (0.06026^e145) + (2.51423^e234) + (2.53183^e235) + (0.72734^e245) + (0.52008^e345),rgb(255, 0, 0));
DrawCircle((0.13953^e123) - (0.33893^e124) - (0.38132^e125) - (0.65111^e134) - (0.68402^e135) - (0.11788^e145) + (2.63342^e234) + (2.65919^e235) + (0.73749^e245) + (0.50085^e345),rgb(255, 0, 0));
DrawCircle((0.158^e123) - (0.83276^e124) - (0.87834^e125) - (0.80178^e134) - (0.83236^e135) - (0.07019^e145) + (2.97662^e234) + (2.99966^e235) + (0.73732^e245) + (0.45901^e345),rgb(255, 0, 0));
DrawCircle((0.13059^e123) - (0.70773^e124) - (0.75222^e125) - (0.57436^e134) - (0.60282^e135) - (0.0414^e145) + (2.64106^e234) + (2.66851^e235) + (0.75104^e245) + (0.455^e345),rgb(255, 0, 0));
DrawCircle((0.15006^e123) - (0.77499^e124) - (0.82243^e125) - (0.74743^e134) - (0.77568^e135) - (0.09042^e145) + (2.80591^e234) + (2.82818^e235) + (0.77203^e245) + (0.4172^e345),rgb(255, 0, 0));
DrawCircle((0.16792^e123) - (1.37853^e124) - (1.42813^e125) - (0.87016^e134) - (0.89456^e135) - (0.05675^e145) + (3.19106^e234) + (3.21317^e235) + (0.76111^e245) + (0.34908^e345),rgb(255, 0, 0));
DrawCircle((0.09836^e123) - (0.83157^e124) - (0.87822^e125) - (0.59806^e134) - (0.62686^e135) - (0.04017^e145) + (2.03431^e234) + (2.0575^e235) + (0.76898^e245) + (0.45477^e345),rgb(255, 0, 0));
DrawCircle(-(0.32178^e123) + (2.25291^e124) + (2.22376^e125) - (0.98685^e134) - (1.01081^e135) + (0.2571^e145) - (5.74431^e234) - (5.7807^e235) + (0.77514^e245) + (0.31599^e345),rgb(0, 255, 0));
DrawCircle(-(0.3383^e123) + (1.12591^e124) + (1.09004^e125) + (0.45287^e134) + (0.43296^e135) + (0.01824^e145) - (6.38659^e234) - (6.41922^e235) + (0.78575^e245) + (0.41949^e345),rgb(0, 255, 0));
DrawCircle(-(0.31814^e123) + (0.92273^e124) + (0.88229^e125) - (0.13829^e134) - (0.15334^e135) + (0.06124^e145) - (6.04585^e234) - (6.0756^e235) + (0.85485^e245) + (0.27316^e345),rgb(0, 255, 0));
DrawCircle(-(0.34861^e123) + (0.76385^e124) + (0.72649^e125) - (1.14153^e134) - (1.15879^e135) + (0.16016^e145) - (6.70845^e234) - (6.74091^e235) + (0.79011^e245) + (0.2258^e345),rgb(0, 255, 0));
DrawCircle(-(0.28349^e123) + (0.48136^e124) + (0.445^e125) - (1.20321^e134) - (1.22794^e135) + (0.19631^e145) - (5.512^e234) - (5.54053^e235) + (0.75537^e245) + (0.3598^e345),rgb(0, 255, 0));
DrawCircle(-(0.30824^e123) + (2.0058^e124) + (1.97125^e125) - (0.45843^e134) - (0.47899^e135) + (0.18518^e145) - (5.53199^e234) - (5.56561^e235) + (0.83905^e245) + (0.31895^e345),rgb(0, 255, 0));
DrawCircle(-(0.32742^e123) + (2.29788^e124) + (2.2645^e125) - (0.14427^e134) - (0.16666^e135) + (0.17179^e145) - (5.80406^e234) - (5.83771^e235) + (0.82787^e245) + (0.38193^e345),rgb(0, 255, 0));
DrawCircle(-(0.30324^e123) + (1.08033^e124) + (1.04669^e125) - (1.06873^e134) - (1.08991^e135) + (0.19404^e145) - (5.85748^e234) - (5.89164^e235) + (0.77166^e245) + (0.28868^e345),rgb(0, 255, 0));
DrawCircle(-(0.35989^e123) + (1.21094^e124) + (1.17343^e125) - (1.00641^e134) - (1.02714^e135) + (0.17467^e145) - (6.73897^e234) - (6.76915^e235) + (0.80391^e245) + (0.30392^e345),rgb(0, 255, 0));
DrawCircle(-(0.33602^e123) + (0.901^e124) + (0.86406^e125) - (1.50814^e134) - (1.53244^e135) + (0.23095^e145) - (6.28915^e234) - (6.3173^e235) + (0.76686^e245) + (0.32849^e345),rgb(0, 255, 0));
DrawCircle(-(0.32497^e123) + (1.32467^e124) + (1.28886^e125) - (0.7287^e134) - (0.74977^e135) + (0.1662^e145) - (6.09423^e234) - (6.12632^e235) + (0.80237^e245) + (0.32323^e345),rgb(0,0,0));
DrawCircle((0.1007^e123) + (0.97607^e124) + (0.99985^e125) + (0.07375^e134) + (0.05707^e135) - (0.17909^e145) + (3.07757^e234) + (3.06097^e235) - (0.88743^e245) + (0.49762^e345),rgb(0,0,0));
DrawCircle((0.13697^e123) - (0.84663^e124) - (0.89304^e125) - (0.80678^e134) - (0.83659^e135) - (0.08909^e145) + (2.63332^e234) + (2.65575^e235) + (0.75361^e245) + (0.44104^e345),rgb(0,0,0));