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.00826^e123) - (2.48541^e124) - (2.52098^e125) - (2.0268^e134) - (2.05569^e135) - (0.03698^e145) + (4.62049^e234) + (4.68572^e235) + (0.26972^e245) + (0.15121^e345),rgb(255,0,0));
DrawCircle((0.07488^e123) - (3.01421^e124) - (3.06244^e125) - (2.16798^e134) - (2.19853^e135) - (0.16644^e145) + (3.98087^e234) + (4.03651^e235) + (0.3243^e245) + (0.01344^e345),rgb(255,0,0));
DrawCircle((0.1219^e123) - (2.58716^e124) - (2.6323^e125) - (1.64078^e134) - (1.66865^e135) - (0.01615^e145) + (4.36508^e234) + (4.42458^e235) + (0.35349^e245) + (0.19693^e345),rgb(255,0,0));
DrawCircle(-(0.14252^e123) - (3.76352^e124) - (3.81027^e125) - (2.01953^e134) - (2.04417^e135) + (0.01162^e145) + (4.09111^e234) + (4.1508^e235) + (0.23431^e245) + (0.13837^e345),rgb(255,0,0));
DrawCircle(-(0.13029^e123) - (3.85108^e124) - (3.89871^e125) - (2.34931^e134) - (2.37978^e135) - (0.0417^e145) + (3.95159^e234) + (4.00779^e235) + (0.21627^e245) + (0.08915^e345),rgb(255,0,0));
DrawCircle((0.07663^e123) - (2.90283^e124) - (2.94739^e125) - (1.33139^e134) - (1.35299^e135) + (0.04387^e145) + (4.54373^e234) + (4.60621^e235) + (0.27509^e245) + (0.19484^e345),rgb(255,0,0));
DrawCircle(-(0.01301^e123) - (3.13086^e124) - (3.1727^e125) - (2.6444^e134) - (2.68^e135) - (0.06395^e145) + (4.26159^e234) + (4.31936^e235) + (0.2007^e245) + (0.08247^e345),rgb(255,0,0));
DrawCircle((0.13407^e123) - (3.61744^e124) - (3.665^e125) - (2.45617^e134) - (2.48743^e135) - (0.02785^e145) + (4.51047^e234) + (4.56629^e235) + (0.09378^e245) + (0.02895^e345),rgb(255,0,0));
DrawCircle((0.02739^e123) - (3.27806^e124) - (3.32379^e125) - (2.03957^e134) - (2.06726^e135) - (0.09085^e145) + (4.37911^e234) + (4.43824^e235) + (0.23421^e245) + (0.02436^e345),rgb(255,0,0));
DrawCircle(-(0.11795^e123) - (4.15433^e124) - (4.20682^e125) - (0.5669^e134) - (0.57315^e135) + (0.03228^e145) + (4.163^e234) + (4.22267^e235) + (0.24913^e245) + (0.06635^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.51353^e123) - (6.72986^e124) - (6.76283^e125) + (5.11748^e134) + (5.16498^e135) - (0.29397^e145) + (4.3813^e234) + (4.38121^e235) + (0.28254^e245) - (0.40623^e345),rgb(255,0,0));
DrawCircle((0.49979^e123) - (6.96549^e124) - (7.00054^e125) + (5.64761^e134) + (5.69359^e135) - (0.24469^e145) + (3.59155^e234) + (3.59072^e235) + (0.26348^e245) - (0.3398^e345),rgb(255,0,0));
DrawCircle((0.53697^e123) - (6.38468^e124) - (6.4187^e125) + (5.73354^e134) + (5.78029^e135) - (0.19273^e145) + (4.93342^e234) + (4.93415^e235) + (0.30379^e245) - (0.42173^e345),rgb(255,0,0));
DrawCircle((0.46164^e123) - (5.20983^e124) - (5.23673^e125) + (6.85299^e134) + (6.90417^e135) - (0.17824^e145) + (3.58056^e234) + (3.58109^e235) + (0.20262^e245) - (0.38902^e345),rgb(255,0,0));
DrawCircle((0.50938^e123) - (6.26235^e124) - (6.29261^e125) + (5.78113^e134) + (5.82986^e135) - (0.25568^e145) + (4.78623^e234) + (4.79353^e235) + (0.19452^e245) - (0.37499^e345),rgb(255,0,0));
DrawCircle((0.24683^e123) + (5.41801^e124) + (5.48095^e125) + (1.32656^e134) + (1.36475^e135) + (0.50013^e145) - (0.0722^e234) - (0.06643^e235) + (0.14505^e245) + (0.04218^e345),rgb(255,0,0));
DrawCircle((0.35825^e123) + (5.93296^e124) + (5.98802^e125) + (2.18149^e134) + (2.23048^e135) + (0.47606^e145) - (0.51514^e234) - (0.51054^e235) + (0.15537^e245) + (0.09846^e345),rgb(255,0,0));
DrawCircle((0.2677^e123) + (5.36402^e124) + (5.42206^e125) + (1.71805^e134) + (1.7624^e135) + (0.51632^e145) + (0.43773^e234) + (0.4486^e235) + (0.12279^e245) - (0.00281^e345),rgb(255,0,0));
DrawCircle((0.29341^e123) + (5.38223^e124) + (5.4355^e125) + (2.27008^e134) + (2.31941^e135) + (0.49276^e145) + (1.14897^e234) + (1.16244^e235) + (0.03851^e245) - (0.08895^e345),rgb(255,0,0));
DrawCircle((0.28202^e123) + (5.30389^e124) + (5.35861^e125) + (2.09314^e134) + (2.14271^e135) + (0.52598^e145) - (0.46213^e234) - (0.46388^e235) + (0.05679^e245) + (0.06824^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.13267^e123) + (2.43898^e124) + (2.50294^e125) - (0.65492^e134) - (0.66372^e135) + (0.15402^e145) + (3.36028^e234) + (3.4215^e235) - (0.49469^e245) - (0.07936^e345),rgb(127, 127, 0));
DrawCircle((0.17848^e123) + (3.1776^e124) + (3.2509^e125) - (0.56043^e134) - (0.56707^e135) + (0.11196^e145) + (3.28017^e234) + (3.33017^e235) - (0.4571^e245) - (0.03495^e345),rgb(127, 127, 0));
DrawCircle((0.22321^e123) + (2.96823^e124) + (3.04116^e125) - (1.11135^e134) - (1.12637^e135) + (0.16338^e145) + (3.40699^e234) + (3.45568^e235) - (0.46571^e245) - (0.01316^e345),rgb(127, 127, 0));
DrawCircle((0.17724^e123) + (2.71129^e124) + (2.77911^e125) - (0.47182^e134) - (0.47818^e135) + (0.08324^e145) + (3.55554^e234) + (3.61278^e235) - (0.48495^e245) - (0.02476^e345),rgb(127, 127, 0));
DrawCircle((0.18972^e123) + (2.57504^e124) + (2.6444^e125) - (0.74993^e134) - (0.75668^e135) + (0.18258^e145) + (3.39847^e234) + (3.45377^e235) - (0.49184^e245) - (0.09772^e345),rgb(127, 127, 0));
DrawCircle((0.21063^e123) + (2.34566^e124) + (2.40892^e125) - (0.7579^e134) - (0.76271^e135) + (0.17399^e145) + (3.82473^e234) + (3.8871^e235) - (0.45407^e245) - (0.13699^e345),rgb(127, 127, 0));
DrawCircle((0.16494^e123) + (2.64946^e124) + (2.71803^e125) - (0.63863^e134) - (0.64591^e135) + (0.14855^e145) + (3.35631^e234) + (3.41253^e235) - (0.49228^e245) - (0.06952^e345),rgb(127, 127, 0));
DrawCircle((0.18593^e123) + (1.79453^e124) + (1.85344^e125) - (0.52273^e134) - (0.52568^e135) + (0.13709^e145) + (3.70818^e234) + (3.7748^e235) - (0.53182^e245) - (0.12836^e345),rgb(127, 127, 0));
DrawCircle((0.28299^e123) + (2.29781^e124) + (2.36429^e125) - (1.72286^e134) - (1.74673^e135) + (0.21091^e145) + (3.8711^e234) + (3.92519^e235) - (0.47018^e245) - (0.00279^e345),rgb(127, 127, 0));
DrawCircle((0.16133^e123) + (2.43846^e124) + (2.50388^e125) - (1.18882^e134) - (1.208^e135) + (0.1922^e145) + (3.32748^e234) + (3.38465^e235) - (0.48517^e245) - (0.02573^e345),rgb(127, 127, 0));
DrawCircle((0.09559^e123) + (4.52843^e124) + (4.54099^e125) - (10.11985^e134) - (10.14254^e135) + (0.25512^e145) + (7.5933^e234) + (7.6128^e235) - (0.07443^e245) - (0.26145^e345),rgb(0, 255, 0));
DrawCircle((0.09225^e123) + (3.51136^e124) + (3.52182^e125) - (9.17817^e134) - (9.199^e135) + (0.24763^e145) + (8.66303^e234) + (8.6856^e235) - (0.12273^e245) - (0.29014^e345),rgb(0, 255, 0));
DrawCircle((0.09114^e123) + (4.66591^e124) + (4.67862^e125) - (9.51099^e134) - (9.53232^e135) + (0.23431^e145) + (8.03428^e234) + (8.05517^e235) - (0.05092^e245) - (0.29965^e345),rgb(0, 255, 0));
DrawCircle((0.14279^e123) + (4.67711^e124) + (4.69063^e125) - (10.59518^e134) - (10.61794^e135) + (0.25748^e145) + (6.93398^e234) + (6.95275^e235) - (0.04183^e245) - (0.28697^e345),rgb(0, 255, 0));
DrawCircle((0.12581^e123) + (4.70738^e124) + (4.72177^e125) - (10.31438^e134) - (10.33748^e135) + (0.31581^e145) + (6.45766^e234) + (6.47532^e235) - (0.07802^e245) - (0.26228^e345),rgb(0, 255, 0));
DrawCircle((0.13027^e123) + (4.00367^e124) + (4.01589^e125) - (10.99875^e134) - (11.02299^e135) + (0.28709^e145) + (6.90978^e234) + (6.92756^e235) - (0.10191^e245) - (0.21551^e345),rgb(0, 255, 0));
DrawCircle((0.13961^e123) + (5.0532^e124) + (5.06805^e125) - (10.78401^e134) - (10.80745^e135) + (0.29852^e145) + (6.32268^e234) + (6.33951^e235) - (0.06307^e245) - (0.23891^e345),rgb(0, 255, 0));
DrawCircle((0.1442^e123) + (4.36345^e124) + (4.37658^e125) - (10.7645^e134) - (10.78775^e135) + (0.27672^e145) + (6.92067^e234) + (6.9391^e235) - (0.0725^e245) - (0.26005^e345),rgb(0, 255, 0));
DrawCircle((0.15243^e123) + (3.69069^e124) + (3.7024^e125) - (11.21763^e134) - (11.24202^e135) + (0.27099^e145) + (6.47916^e234) + (6.49707^e235) - (0.06411^e245) - (0.28088^e345),rgb(0, 255, 0));
DrawCircle((0.13903^e123) + (5.04845^e124) + (5.06285^e125) - (9.96363^e134) - (9.98475^e135) + (0.26548^e145) + (7.71378^e234) + (7.73377^e235) - (0.07356^e245) - (0.26045^e345),rgb(0, 255, 0));
DrawCircle(-(0.56052^e123) + (7.7917^e124) + (7.81128^e125) + (4.74456^e134) + (4.79684^e135) - (0.56102^e145) - (3.586^e234) - (3.60607^e235) + (0.15371^e245) - (0.1646^e345),rgb(255, 0, 0));
DrawCircle(-(0.56592^e123) + (8.09547^e124) + (8.11726^e125) + (5.15007^e134) + (5.2036^e135) - (0.56746^e145) - (2.53353^e234) - (2.54691^e235) + (0.09383^e245) - (0.1179^e345),rgb(255, 0, 0));
DrawCircle(-(0.58711^e123) + (8.48541^e124) + (8.50781^e125) + (5.39343^e134) + (5.44696^e135) - (0.56801^e145) - (1.87676^e234) - (1.88909^e235) + (0.10659^e245) - (0.05788^e345),rgb(255, 0, 0));
DrawCircle(-(0.58701^e123) + (8.46608^e124) + (8.49076^e125) + (4.86475^e134) + (4.91688^e135) - (0.54737^e145) - (3.09424^e234) - (3.10811^e235) + (0.06983^e245) - (0.15993^e345),rgb(255, 0, 0));
DrawCircle(-(0.61061^e123) + (8.89207^e124) + (8.91897^e125) + (5.02691^e134) + (5.0778^e135) - (0.51952^e145) - (2.99674^e234) - (3.01111^e235) + (0.07732^e245) - (0.13137^e345),rgb(255, 0, 0));
DrawCircle(-(0.55592^e123) + (8.24014^e124) + (8.26437^e125) + (5.20446^e134) + (5.25729^e135) - (0.55623^e145) - (1.38876^e234) - (1.40069^e235) + (0.11625^e245) - (0.02032^e345),rgb(255, 0, 0));
DrawCircle(-(0.59029^e123) + (8.97254^e124) + (9.00029^e125) + (4.22612^e134) + (4.27564^e135) - (0.55408^e145) - (2.68509^e234) - (2.70233^e235) + (0.13572^e245) - (0.10189^e345),rgb(255, 0, 0));
DrawCircle(-(0.50202^e123) + (7.48505^e124) + (7.50567^e125) + (4.78071^e134) + (4.83574^e135) - (0.62408^e145) - (1.02353^e234) - (1.03167^e235) + (0.0793^e245) - (0.03469^e345),rgb(255, 0, 0));
DrawCircle(-(0.54484^e123) + (8.42352^e124) + (8.45073^e125) + (3.97494^e134) + (4.02413^e135) - (0.56193^e145) - (2.42454^e234) - (2.44351^e235) + (0.17213^e245) - (0.08051^e345),rgb(255, 0, 0));
DrawCircle(-(0.58664^e123) + (8.57359^e124) + (8.59632^e125) + (5.08386^e134) + (5.13731^e135) - (0.58416^e145) - (2.06272^e234) - (2.07481^e235) + (0.09669^e245) - (0.08321^e345),rgb(255, 0, 0));
DrawCircle((0.12569^e123) + (4.44073^e124) + (4.45377^e125) - (10.37705^e134) - (10.39984^e135) + (0.27149^e145) + (7.22233^e234) + (7.24142^e235) - (0.07486^e245) - (0.26661^e345),rgb(0,0,0));
DrawCircle((0.19115^e123) + (2.54792^e124) + (2.61536^e125) - (0.83309^e134) - (0.8433^e135) + (0.15787^e145) + (3.53431^e234) + (3.59144^e235) - (0.48542^e245) - (0.06027^e345),rgb(0,0,0));
DrawCircle(-(0.57164^e123) + (8.38953^e124) + (8.41341^e125) + (4.86625^e134) + (4.91876^e135) - (0.56748^e145) - (2.37037^e234) - (2.3847^e235) + (0.11133^e245) - (0.09576^e345),rgb(0,0,0));