# 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:

In [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:

In [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.

In [3]:

from clifford.tools.g3c.GAOnline import *
clustered_circles = generate_random_object_cluster(10, random_circle)
sc = GAScene()
for c in clustered_circles:
print(sc)

DrawCircle(-(0.31484^e123) + (0.73299^e124) + (0.70766^e125) + (1.40116^e134) + (1.37456^e135) - (0.0508^e145) + (4.3493^e234) + (4.41163^e235) - (0.495^e245) - (0.64479^e345),rgb(255,0,0));
DrawCircle(-(0.18917^e123) - (0.11849^e124) - (0.14981^e125) + (1.29312^e134) + (1.2875^e135) - (0.21765^e145) + (3.33532^e234) + (3.40029^e235) - (0.51159^e245) - (0.54333^e345),rgb(255,0,0));
DrawCircle(-(0.38601^e123) + (0.89999^e124) + (0.87499^e125) + (4.68352^e134) + (4.69113^e135) - (0.32106^e145) + (2.3867^e234) + (2.45416^e235) - (0.31185^e245) - (0.7714^e345),rgb(255,0,0));
DrawCircle(-(0.20954^e123) - (0.72565^e124) - (0.7668^e125) + (1.57239^e134) + (1.5547^e135) - (0.37004^e145) + (2.84263^e234) + (2.89944^e235) - (0.36145^e245) - (0.66635^e345),rgb(255,0,0));
DrawCircle(-(0.22265^e123) - (0.13684^e124) - (0.15628^e125) + (1.50958^e134) + (1.49274^e135) - (0.14215^e145) + (3.5128^e234) + (3.58042^e235) - (0.26515^e245) - (0.72405^e345),rgb(255,0,0));
DrawCircle(-(0.15041^e123) + (0.67695^e124) + (0.66795^e125) + (1.82987^e134) + (1.81099^e135) - (0.0245^e145) + (0.72496^e234) + (0.79421^e235) - (0.35508^e245) - (0.93359^e345),rgb(255,0,0));
DrawCircle(-(0.33918^e123) - (0.6596^e124) - (0.68847^e125) + (3.91527^e134) + (3.90977^e135) - (0.34391^e145) + (2.57539^e234) + (2.6415^e235) - (0.09063^e245) - (0.80486^e345),rgb(255,0,0));
DrawCircle(-(0.18345^e123) - (0.94996^e124) - (0.9666^e125) + (0.90313^e134) + (0.88694^e135) - (0.16574^e145) + (3.89852^e234) + (3.96704^e235) + (0.00134^e245) - (0.68143^e345),rgb(255,0,0));
DrawCircle(-(0.21895^e123) + (0.06233^e124) + (0.02898^e125) + (2.00305^e134) + (1.99275^e135) - (0.30222^e145) + (2.6092^e234) + (2.67256^e235) - (0.41554^e245) - (0.70248^e345),rgb(255,0,0));
DrawCircle(-(0.19565^e123) + (0.46712^e124) + (0.45524^e125) + (1.14881^e134) + (1.13218^e135) - (0.03008^e145) + (3.35327^e234) + (3.42266^e235) - (0.36939^e245) - (0.69253^e345),rgb(255,0,0));


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

In [4]:

from clifford.tools.g3c import generate_random_object_cluster


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

In [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:

In [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:
print(sc)

DrawCircle(-(0.16217^e123) + (2.97917^e124) + (2.99841^e125) + (3.92365^e134) + (3.96365^e135) - (0.26927^e145) - (3.85229^e234) - (3.86623^e235) - (0.20085^e245) - (0.61271^e345),rgb(255,0,0));
DrawCircle(-(0.12858^e123) + (1.80767^e124) + (1.81929^e125) + (4.19108^e134) + (4.2324^e135) - (0.20242^e145) - (3.87486^e234) - (3.89279^e235) - (0.09782^e245) - (0.66069^e345),rgb(255,0,0));
DrawCircle(-(0.16348^e123) + (2.41733^e124) + (2.43252^e125) + (3.27076^e134) + (3.31082^e135) - (0.28844^e145) - (4.18507^e234) - (4.20319^e235) - (0.12093^e245) - (0.66301^e345),rgb(255,0,0));
DrawCircle(-(0.19671^e123) + (2.41959^e124) + (2.43575^e125) + (3.6042^e134) + (3.64491^e135) - (0.20462^e145) - (4.60746^e234) - (4.62313^e235) - (0.18581^e245) - (0.66642^e345),rgb(255,0,0));
DrawCircle(-(0.16531^e123) + (2.45387^e124) + (2.471^e125) + (3.63752^e134) + (3.67802^e135) - (0.22437^e145) - (4.05318^e234) - (4.06833^e235) - (0.19502^e245) - (0.65969^e345),rgb(255,0,0));
DrawCircle(-(0.09656^e123) + (3.46561^e124) + (3.49869^e125) - (5.95308^e134) - (6.00375^e135) - (0.22032^e145) - (0.63419^e234) - (0.64443^e235) + (0.15017^e245) - (0.29828^e345),rgb(255,0,0));
DrawCircle(-(0.12821^e123) + (3.01476^e124) + (3.0429^e125) - (6.40023^e134) - (6.45147^e135) - (0.20012^e145) - (1.62349^e234) - (1.64214^e235) + (0.08219^e245) - (0.28225^e345),rgb(255,0,0));
DrawCircle(-(0.13799^e123) + (2.49932^e124) + (2.52336^e125) - (6.25229^e134) - (6.30269^e135) - (0.17664^e145) - (2.22927^e234) - (2.25472^e235) + (0.07254^e245) - (0.33902^e345),rgb(255,0,0));
DrawCircle(-(0.05212^e123) + (2.47084^e124) + (2.4958^e125) - (5.4372^e134) - (5.48701^e135) - (0.24211^e145) - (2.40896^e234) - (2.4347^e235) + (0.06691^e245) - (0.38329^e345),rgb(255,0,0));
DrawCircle(-(0.12872^e123) + (3.15656^e124) + (3.18617^e125) - (6.24359^e134) - (6.29433^e135) - (0.19187^e145) - (1.4091^e234) - (1.42684^e235) + (0.111^e245) - (0.30521^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.

In [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!

In [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.20227^e123) + (3.68853^e124) + (3.70859^e125) + (6.69222^e134) + (6.7093^e135) + (0.35214^e145) + (8.27769^e234) + (8.29876^e235) + (0.43647^e245) + (0.00165^e345),rgb(127, 127, 0));
DrawCircle(-(0.19449^e123) + (4.15521^e124) + (4.17646^e125) + (6.68607^e134) + (6.70345^e135) + (0.35945^e145) + (7.82879^e234) + (7.84838^e235) + (0.4371^e245) + (0.02608^e345),rgb(127, 127, 0));
DrawCircle(-(0.19413^e123) + (2.54994^e124) + (2.56785^e125) + (6.93778^e134) + (6.95572^e135) + (0.40432^e145) + (7.77893^e234) + (7.80118^e235) + (0.42521^e245) - (0.07654^e345),rgb(127, 127, 0));
DrawCircle(-(0.19235^e123) + (3.00812^e124) + (3.02654^e125) + (7.23375^e134) + (7.25405^e135) + (0.37514^e145) + (7.68266^e234) + (7.70231^e235) + (0.42835^e245) + (0.07196^e345),rgb(127, 127, 0));
DrawCircle(-(0.2128^e123) + (1.78351^e124) + (1.80029^e125) + (6.80302^e134) + (6.82182^e135) + (0.37889^e145) + (8.25675^e234) + (8.27917^e235) + (0.46324^e245) + (0.0129^e345),rgb(127, 127, 0));
DrawCircle(-(0.2006^e123) + (3.36847^e124) + (3.38856^e125) + (6.30349^e134) + (6.31959^e135) + (0.36114^e145) + (8.23686^e234) + (8.25865^e235) + (0.45924^e245) - (0.0237^e345),rgb(127, 127, 0));
DrawCircle(-(0.20668^e123) + (3.24948^e124) + (3.26872^e125) + (6.58968^e134) + (6.60622^e135) + (0.35326^e145) + (8.50069^e234) + (8.52292^e235) + (0.44172^e245) - (0.02837^e345),rgb(127, 127, 0));
DrawCircle(-(0.21942^e123) + (4.12826^e124) + (4.14913^e125) + (6.70461^e134) + (6.72112^e135) + (0.32691^e145) + (8.65345^e234) + (8.67418^e235) + (0.43294^e245) + (0.01786^e345),rgb(127, 127, 0));
DrawCircle(-(0.20306^e123) + (4.92419^e124) + (4.94727^e125) + (6.71642^e134) + (6.73236^e135) + (0.37698^e145) + (7.62534^e234) + (7.64406^e235) + (0.413^e245) - (0.02046^e345),rgb(127, 127, 0));
DrawCircle(-(0.21409^e123) + (2.68117^e124) + (2.69961^e125) + (7.44289^e134) + (7.4617^e135) + (0.40544^e145) + (7.83951^e234) + (7.86057^e235) + (0.41144^e245) - (0.04333^e345),rgb(127, 127, 0));
DrawCircle(-(0.40782^e123) + (4.68067^e124) + (4.74328^e125) + (1.52966^e134) + (1.59583^e135) - (0.52462^e145) - (1.57719^e234) - (1.58818^e235) - (0.11596^e245) - (0.21467^e345),rgb(255, 0, 0));
DrawCircle(-(0.4501^e123) + (4.81796^e124) + (4.88992^e125) + (0.9099^e134) + (0.96301^e135) - (0.42304^e145) - (2.6565^e234) - (2.67694^e235) - (0.20595^e245) - (0.27215^e345),rgb(255, 0, 0));
DrawCircle(-(0.43826^e123) + (4.3681^e124) + (4.42768^e125) + (1.01033^e134) + (1.07424^e135) - (0.4997^e145) - (2.79475^e234) - (2.82275^e235) - (0.10087^e245) - (0.34304^e345),rgb(255, 0, 0));
DrawCircle(-(0.43664^e123) + (4.98568^e124) + (5.05192^e125) + (1.9227^e134) + (1.98464^e135) - (0.41552^e145) - (1.8838^e234) - (1.89774^e235) - (0.12659^e245) - (0.20582^e345),rgb(255, 0, 0));
DrawCircle(-(0.44016^e123) + (5.41776^e124) + (5.49366^e125) + (1.26678^e134) + (1.31616^e135) - (0.38931^e145) - (1.71676^e234) - (1.73159^e235) - (0.11357^e245) - (0.14992^e345),rgb(255, 0, 0));
DrawCircle(-(0.44156^e123) + (4.65655^e124) + (4.71908^e125) + (1.67201^e134) + (1.73641^e135) - (0.44229^e145) - (2.43223^e234) - (2.4512^e235) - (0.14438^e245) - (0.28286^e345),rgb(255, 0, 0));
DrawCircle(-(0.43675^e123) + (5.2683^e124) + (5.34061^e125) + (1.11551^e134) + (1.17177^e135) - (0.494^e145) - (1.19315^e234) - (1.19801^e235) - (0.1389^e245) - (0.14129^e345),rgb(255, 0, 0));
DrawCircle(-(0.36432^e123) + (4.80764^e124) + (4.87962^e125) + (1.29285^e134) + (1.34826^e135) - (0.47571^e145) - (1.28559^e234) - (1.2985^e235) - (0.08369^e245) - (0.14971^e345),rgb(255, 0, 0));
DrawCircle(-(0.46643^e123) + (5.13838^e124) + (5.20312^e125) + (0.91744^e134) + (0.97989^e135) - (0.56066^e145) - (1.84738^e234) - (1.86547^e235) - (0.05707^e245) - (0.21176^e345),rgb(255, 0, 0));
DrawCircle(-(0.42497^e123) + (4.54793^e124) + (4.61273^e125) + (1.62902^e134) + (1.68535^e135) - (0.35444^e145) - (2.95433^e234) - (2.98667^e235) - (0.1044^e245) - (0.26764^e345),rgb(255, 0, 0));
DrawCircle(-(0.42013^e123) - (5.05754^e124) - (5.09999^e125) - (3.9058^e134) - (3.94999^e135) - (0.13733^e145) + (5.00335^e234) + (5.03059^e235) - (0.17751^e245) - (0.27294^e345),rgb(0, 255, 0));
DrawCircle(-(0.4204^e123) - (4.8129^e124) - (4.85442^e125) - (4.43112^e134) - (4.47783^e135) - (0.09711^e145) + (4.80465^e234) + (4.82895^e235) - (0.19633^e245) - (0.2777^e345),rgb(0, 255, 0));
DrawCircle(-(0.40422^e123) - (4.77909^e124) - (4.81538^e125) - (4.58668^e134) - (4.63852^e135) - (0.20112^e145) + (4.30056^e234) + (4.32274^e235) - (0.12383^e245) - (0.29984^e345),rgb(0, 255, 0));
DrawCircle(-(0.48689^e123) - (5.04796^e124) - (5.09024^e125) - (3.35541^e134) - (3.39607^e135) - (0.13017^e145) + (6.10546^e234) + (6.13795^e235) - (0.1934^e245) - (0.28599^e345),rgb(0, 255, 0));
DrawCircle(-(0.50508^e123) - (5.66186^e124) - (5.70421^e125) - (4.57387^e134) - (4.61911^e135) - (0.12367^e145) + (5.18866^e234) + (5.21427^e235) - (0.14792^e245) - (0.23283^e345),rgb(0, 255, 0));
DrawCircle(-(0.46268^e123) - (5.13517^e124) - (5.17588^e125) - (4.06211^e134) - (4.10634^e135) - (0.13352^e145) + (5.45141^e234) + (5.4811^e235) - (0.15021^e245) - (0.26057^e345),rgb(0, 255, 0));
DrawCircle(-(0.46002^e123) - (4.91265^e124) - (4.95376^e125) - (3.52648^e134) - (3.57091^e135) - (0.15932^e145) + (5.61338^e234) + (5.64222^e235) - (0.19368^e245) - (0.32107^e345),rgb(0, 255, 0));
DrawCircle(-(0.41436^e123) - (4.60951^e124) - (4.65127^e125) - (3.87479^e134) - (3.9189^e135) - (0.10007^e145) + (5.25483^e234) + (5.28324^e235) - (0.21354^e245) - (0.29358^e345),rgb(0, 255, 0));
DrawCircle(-(0.40702^e123) - (5.07483^e124) - (5.11662^e125) - (3.32447^e134) - (3.36912^e135) - (0.21542^e145) + (4.9051^e234) + (4.93262^e235) - (0.16037^e245) - (0.31327^e345),rgb(0, 255, 0));
DrawCircle(-(0.48744^e123) - (6.49706^e124) - (6.54444^e125) - (3.88503^e134) - (3.92847^e135) - (0.20143^e145) + (4.2541^e234) + (4.27317^e235) - (0.1593^e245) - (0.22715^e345),rgb(0, 255, 0));
DrawCircle(-(0.44855^e123) - (5.1796^e124) - (5.2216^e125) - (3.96644^e134) - (4.01162^e135) - (0.15027^e145) + (5.1197^e234) + (5.14628^e235) - (0.17246^e245) - (0.2806^e345),rgb(0,0,0));
DrawCircle(-(0.20411^e123) + (3.35448^e124) + (3.37418^e125) + (6.83434^e134) + (6.85191^e135) + (0.37081^e145) + (8.09671^e234) + (8.11772^e235) + (0.43629^e245) - (0.00614^e345),rgb(0,0,0));
DrawCircle(-(0.43546^e123) + (4.91891^e124) + (4.9869^e125) + (1.34334^e134) + (1.40285^e135) - (0.46249^e145) - (2.0546^e234) - (2.07234^e235) - (0.12036^e245) - (0.22605^e345),rgb(0,0,0));