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.03253^e123) - (2.76112^e124) - (2.76448^e125) - (9.90002^e134) - (9.91629^e135) - (0.35666^e145) + (4.74981^e234) + (4.7595^e235) + (0.33148^e245) + (0.57498^e345),rgb(255,0,0));
DrawCircle((0.01294^e123) - (5.54595^e124) - (5.55666^e125) - (7.90287^e134) - (7.91758^e135) - (0.23033^e145) + (3.83923^e234) + (3.84548^e235) + (0.49669^e245) + (0.54833^e345),rgb(255,0,0));
DrawCircle(-(0.01601^e123) - (4.15318^e124) - (4.16078^e125) - (8.37417^e134) - (8.39046^e135) - (0.24975^e145) + (2.91867^e234) + (2.92555^e235) + (0.40098^e245) + (0.633^e345),rgb(255,0,0));
DrawCircle((0.03138^e123) - (3.93565^e124) - (3.94456^e125) - (8.02748^e134) - (8.04362^e135) - (0.25571^e145) + (3.93938^e234) + (3.94489^e235) + (0.42759^e245) + (0.61619^e345),rgb(255,0,0));
DrawCircle((0.03726^e123) - (3.06312^e124) - (3.07001^e125) - (9.93457^e134) - (9.95248^e135) - (0.36583^e145) + (2.11305^e234) + (2.11451^e235) + (0.27034^e245) + (0.62441^e345),rgb(255,0,0));
DrawCircle(-(0.00851^e123) - (4.42337^e124) - (4.43221^e125) - (7.79586^e134) - (7.81193^e135) - (0.25888^e145) + (2.48892^e234) + (2.49473^e235) + (0.43502^e245) + (0.62103^e345),rgb(255,0,0));
DrawCircle((0.00688^e123) - (2.78206^e124) - (2.78813^e125) - (7.49471^e134) - (7.51041^e135) - (0.26744^e145) + (4.72949^e234) + (4.73882^e235) + (0.40542^e245) + (0.63755^e345),rgb(255,0,0));
DrawCircle((0.03195^e123) - (4.54745^e124) - (4.5563^e125) - (9.2288^e134) - (9.245^e135) - (0.25273^e145) + (4.25756^e234) + (4.263^e235) + (0.40637^e245) + (0.58809^e345),rgb(255,0,0));
DrawCircle(-(0.01461^e123) - (7.21141^e124) - (7.22136^e125) - (9.2067^e134) - (9.2199^e135) - (0.24852^e145) + (6.40694^e234) + (6.41679^e235) + (0.50045^e245) + (0.41812^e345),rgb(255,0,0));
DrawCircle((0.00123^e123) - (4.16953^e124) - (4.17711^e125) - (8.75685^e134) - (8.77267^e135) - (0.36366^e145) + (4.41902^e234) + (4.42693^e235) + (0.43142^e245) + (0.52064^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.28269^e123) - (0.0399^e124) - (0.04002^e125) + (4.03926^e134) + (4.03228^e135) - (0.0026^e145) - (0.18207^e234) - (0.10644^e235) + (0.01075^e245) - (1.07606^e345),rgb(255,0,0));
DrawCircle(-(0.23038^e123) - (0.04873^e124) - (0.05419^e125) + (3.12557^e134) + (3.11511^e135) - (0.07637^e145) + (0.28937^e234) + (0.36439^e235) + (0.009^e245) - (1.03094^e345),rgb(255,0,0));
DrawCircle(-(0.29366^e123) - (0.35926^e124) - (0.36466^e125) + (4.18271^e134) + (4.17126^e135) - (0.09104^e145) + (0.07879^e234) + (0.15367^e235) + (0.09016^e245) - (1.06963^e345),rgb(255,0,0));
DrawCircle(-(0.32525^e123) + (0.04168^e124) + (0.04431^e125) + (4.61603^e134) + (4.6055^e135) + (0.03863^e145) + (0.26196^e234) + (0.33712^e235) - (0.00752^e245) - (1.07521^e345),rgb(255,0,0));
DrawCircle(-(0.30897^e123) + (0.61533^e124) + (0.6194^e125) + (3.8609^e134) + (3.84838^e135) + (0.07573^e145) + (1.25151^e234) + (1.3263^e235) - (0.13249^e245) - (0.98534^e345),rgb(255,0,0));
DrawCircle((0.00935^e123) + (1.36192^e124) + (1.33423^e125) - (0.18228^e134) - (0.17799^e135) + (0.08559^e145) + (0.47039^e234) + (0.45372^e235) - (1.0356^e245) + (0.10904^e345),rgb(255,0,0));
DrawCircle((0.00221^e123) + (2.11413^e124) + (2.08665^e125) + (0.04289^e134) + (0.04207^e135) - (0.25434^e145) + (1.26539^e234) + (1.24785^e235) - (1.03811^e245) + (0.13117^e345),rgb(255,0,0));
DrawCircle(-(0.0383^e123) + (0.54904^e124) + (0.52111^e125) + (0.0509^e134) + (0.05448^e135) - (0.08844^e145) + (1.72522^e234) + (1.70879^e235) - (1.02277^e245) + (0.18309^e345),rgb(255,0,0));
DrawCircle((0.00568^e123) + (2.4174^e124) + (2.3897^e125) - (0.40887^e134) - (0.40436^e135) - (0.07724^e145) + (1.23141^e234) + (1.21481^e235) - (1.06004^e245) + (0.21864^e345),rgb(255,0,0));
DrawCircle((0.00404^e123) + (2.08425^e124) + (2.05636^e125) + (0.0711^e134) + (0.06993^e135) - (0.11125^e145) + (1.10422^e234) + (1.08737^e235) - (1.06757^e245) + (0.02252^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.27891^e123) + (0.75372^e124) + (0.79068^e125) + (5.0914^e134) + (5.16333^e135) + (0.48031^e145) + (0.10488^e234) + (0.09379^e235) + (0.04387^e245) + (0.2295^e345),rgb(255, 0, 0));
DrawCircle(-(0.25785^e123) + (1.42804^e124) + (1.46722^e125) + (5.27414^e134) + (5.34552^e135) + (0.40611^e145) + (0.18919^e234) + (0.18349^e235) + (0.06033^e245) + (0.16901^e345),rgb(255, 0, 0));
DrawCircle(-(0.23818^e123) + (0.88589^e124) + (0.9172^e125) + (5.29942^e134) + (5.37438^e135) + (0.41777^e145) - (0.074^e234) - (0.08202^e235) + (0.02007^e245) + (0.15496^e345),rgb(255, 0, 0));
DrawCircle(-(0.29951^e123) + (1.01373^e124) + (1.05365^e125) + (5.354^e134) + (5.42466^e135) + (0.47433^e145) - (0.0851^e234) - (0.09387^e235) + (0.01833^e245) + (0.13661^e345),rgb(255, 0, 0));
DrawCircle(-(0.26293^e123) + (0.87613^e124) + (0.90995^e125) + (5.30842^e134) + (5.38205^e135) + (0.43753^e145) - (0.12067^e234) - (0.13053^e235) + (0.01735^e245) + (0.16538^e345),rgb(255, 0, 0));
DrawCircle(-(0.22512^e123) + (0.82842^e124) + (0.85997^e125) + (5.00977^e134) + (5.08401^e135) + (0.42893^e145) - (0.09936^e234) - (0.11188^e235) + (0.03215^e245) + (0.24585^e345),rgb(255, 0, 0));
DrawCircle(-(0.20314^e123) + (1.0679^e124) + (1.09929^e125) + (5.16497^e134) + (5.24032^e135) + (0.40206^e145) + (0.34992^e234) + (0.34883^e235) + (0.05981^e245) + (0.15752^e345),rgb(255, 0, 0));
DrawCircle(-(0.26976^e123) + (0.66375^e124) + (0.69406^e125) + (5.30911^e134) + (5.38221^e135) + (0.41667^e145) - (0.62538^e234) - (0.64543^e235) - (0.02095^e245) + (0.22501^e345),rgb(255, 0, 0));
DrawCircle(-(0.25994^e123) + (1.22886^e124) + (1.26884^e125) + (5.10768^e134) + (5.17829^e135) + (0.45186^e145) + (0.04843^e234) + (0.03949^e235) + (0.04971^e245) + (0.18879^e345),rgb(255, 0, 0));
DrawCircle(-(0.30297^e123) + (0.73401^e124) + (0.77167^e125) + (5.29879^e134) + (5.37092^e135) + (0.48387^e145) + (0.28256^e234) + (0.27613^e235) + (0.05071^e245) + (0.17979^e345),rgb(255, 0, 0));
DrawCircle((0.30095^e123) + (1.95767^e124) + (1.97612^e125) - (5.48093^e134) - (5.53155^e135) + (0.00668^e145) - (4.24241^e234) - (4.29184^e235) - (0.06148^e245) + (0.1866^e345),rgb(127, 127, 0));
DrawCircle((0.31858^e123) + (1.2227^e124) + (1.23345^e125) - (6.36178^e134) - (6.42172^e135) - (0.01538^e145) - (2.9067^e234) - (2.94718^e235) - (0.0573^e245) + (0.26157^e345),rgb(127, 127, 0));
DrawCircle((0.32127^e123) + (1.4411^e124) + (1.45052^e125) - (5.99146^e134) - (6.04768^e135) - (0.07635^e145) - (3.7139^e234) - (3.75971^e235) - (0.09648^e245) + (0.20436^e345),rgb(127, 127, 0));
DrawCircle((0.34304^e123) + (1.17127^e124) + (1.1814^e125) - (6.6202^e134) - (6.68147^e135) - (0.01357^e145) - (2.98582^e234) - (3.02442^e235) - (0.04356^e245) + (0.21159^e345),rgb(127, 127, 0));
DrawCircle((0.29718^e123) + (1.0895^e124) + (1.09963^e125) - (6.21626^e134) - (6.2754^e135) - (0.00488^e145) - (3.20098^e234) - (3.24276^e235) - (0.04403^e245) + (0.23688^e345),rgb(127, 127, 0));
DrawCircle((0.34947^e123) + (2.07948^e124) + (2.098^e125) - (5.59698^e134) - (5.64668^e135) + (0.00082^e145) - (4.4804^e234) - (4.53074^e235) - (0.06209^e245) + (0.1689^e345),rgb(127, 127, 0));
DrawCircle((0.28325^e123) + (1.60313^e124) + (1.61814^e125) - (5.97311^e134) - (6.03048^e135) - (0.00805^e145) - (3.30661^e234) - (3.34938^e235) - (0.06681^e245) + (0.23232^e345),rgb(127, 127, 0));
DrawCircle((0.31271^e123) + (1.83713^e124) + (1.85368^e125) - (6.11745^e134) - (6.17506^e135) - (0.01478^e145) - (3.41983^e234) - (3.46172^e235) - (0.06517^e245) + (0.1895^e345),rgb(127, 127, 0));
DrawCircle((0.3761^e123) + (2.24003^e124) + (2.26048^e125) - (6.2103^e134) - (6.26443^e135) + (0.01529^e145) - (3.31658^e234) - (3.36128^e235) - (0.08591^e245) + (0.26083^e345),rgb(127, 127, 0));
DrawCircle((0.27733^e123) + (1.81235^e124) + (1.82989^e125) - (5.55416^e134) - (5.607^e135) + (0.00603^e145) - (3.43911^e234) - (3.48651^e235) - (0.09221^e245) + (0.29402^e345),rgb(127, 127, 0));
DrawCircle((0.09781^e123) - (6.74734^e124) - (6.70548^e125) + (4.58992^e134) + (4.54814^e135) + (0.91781^e145) - (3.5426^e234) - (3.52963^e235) + (0.62121^e245) - (0.90446^e345),rgb(0, 255, 0));
DrawCircle((0.12087^e123) - (7.42232^e124) - (7.37756^e125) + (4.1442^e134) + (4.10385^e135) + (0.94323^e145) - (2.96287^e234) - (2.95695^e235) + (0.73322^e245) - (0.78591^e345),rgb(0, 255, 0));
DrawCircle((0.14723^e123) - (6.29905^e124) - (6.25868^e125) + (3.6811^e134) + (3.63754^e135) + (0.8546^e145) - (4.08344^e234) - (4.07165^e235) + (0.61532^e245) - (0.91359^e345),rgb(0, 255, 0));
DrawCircle((0.07915^e123) - (7.27843^e124) - (7.2331^e125) + (4.63302^e134) + (4.59294^e135) + (1.0328^e145) - (1.63153^e234) - (1.62911^e235) + (0.71166^e245) - (0.68451^e345),rgb(0, 255, 0));
DrawCircle((0.13363^e123) - (5.53891^e124) - (5.49634^e125) + (2.90664^e134) + (2.86395^e135) + (0.84384^e145) - (2.82978^e234) - (2.82411^e235) + (0.66647^e245) - (0.78086^e345),rgb(0, 255, 0));
DrawCircle((0.14858^e123) - (6.00505^e124) - (5.96339^e125) + (2.68396^e134) + (2.64168^e135) + (0.95637^e145) - (3.58217^e234) - (3.57021^e235) + (0.52098^e245) - (0.80336^e345),rgb(0, 255, 0));
DrawCircle((0.10067^e123) - (7.26965^e124) - (7.22198^e125) + (2.99384^e134) + (2.96098^e135) + (0.95562^e145) - (4.13293^e234) - (4.11518^e235) + (0.67482^e245) - (0.82119^e345),rgb(0, 255, 0));
DrawCircle((0.07737^e123) - (7.4979^e124) - (7.44866^e125) + (3.46445^e134) + (3.43224^e135) + (0.9167^e145) - (3.41113^e234) - (3.39681^e235) + (0.78365^e245) - (0.77914^e345),rgb(0, 255, 0));
DrawCircle((0.14549^e123) - (6.25234^e124) - (6.2117^e125) + (3.72947^e134) + (3.68695^e135) + (0.78523^e145) - (4.56132^e234) - (4.54691^e235) + (0.65508^e245) - (0.9636^e345),rgb(0, 255, 0));
DrawCircle((0.08271^e123) - (6.46107^e124) - (6.41854^e125) + (4.58749^e134) + (4.5453^e135) + (0.93654^e145) - (2.59734^e234) - (2.58849^e235) + (0.64352^e245) - (0.8334^e345),rgb(0, 255, 0));
DrawCircle((0.11381^e123) - (6.69703^e124) - (6.6532^e125) + (3.74218^e134) + (3.70211^e135) + (0.91647^e145) - (3.33341^e234) - (3.32288^e235) + (0.66459^e245) - (0.82753^e345),rgb(0,0,0));
DrawCircle((0.31945^e123) + (1.65191^e124) + (1.6667^e125) - (6.04533^e134) - (6.10146^e135) - (0.0104^e145) - (3.51494^e234) - (3.55952^e235) - (0.0678^e245) + (0.22601^e345),rgb(0,0,0));
DrawCircle(-(0.26069^e123) + (0.95289^e124) + (0.98814^e125) + (5.23403^e134) + (5.30702^e135) + (0.44089^e145) - (0.00323^e234) - (0.01252^e235) + (0.03352^e245) + (0.18562^e345),rgb(0,0,0));