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.12507^e123) + (1.0602^e124) + (1.068^e125) + (5.67628^e134) + (5.73106^e135) + (0.1106^e145) + (1.13568^e234) + (1.13344^e235) - (0.08978^e245) - (0.59917^e345),rgb(255,0,0));
DrawCircle((0.11167^e123) + (0.9957^e124) + (1.00278^e125) + (6.98932^e134) + (7.0437^e135) + (0.04163^e145) - (0.00972^e234) - (0.01744^e235) - (0.06819^e245) - (0.47823^e345),rgb(255,0,0));
DrawCircle((0.13611^e123) + (0.99176^e124) + (0.99592^e125) + (7.18716^e134) + (7.24107^e135) + (0.17307^e145) - (0.51028^e234) - (0.52225^e235) - (0.07165^e245) - (0.43023^e345),rgb(255,0,0));
DrawCircle((0.00082^e123) + (0.03665^e124) + (0.03693^e125) + (6.3932^e134) + (6.44714^e135) + (0.28381^e145) - (1.47416^e234) - (1.48666^e235) - (0.06791^e245) - (0.43031^e345),rgb(255,0,0));
DrawCircle((0.11915^e123) + (2.7929^e124) + (2.81279^e125) + (5.41471^e134) + (5.46638^e135) + (0.30737^e145) + (0.92842^e234) + (0.9271^e235) - (0.18591^e245) - (0.46261^e345),rgb(255,0,0));
DrawCircle((0.07787^e123) + (0.76198^e124) + (0.76751^e125) + (7.07151^e134) + (7.12627^e135) + (0.03416^e145) - (0.12837^e234) - (0.13447^e235) - (0.05057^e245) - (0.46352^e345),rgb(255,0,0));
DrawCircle((0.07137^e123) + (1.28443^e124) + (1.29256^e125) + (7.7654^e134) + (7.81972^e135) + (0.0933^e145) - (0.55485^e234) - (0.56188^e235) - (0.06325^e245) - (0.34206^e345),rgb(255,0,0));
DrawCircle((0.108^e123) + (1.37527^e124) + (1.38351^e125) + (6.75934^e134) + (6.81409^e135) + (0.18143^e145) + (0.80912^e234) + (0.80836^e235) - (0.07129^e245) - (0.45715^e345),rgb(255,0,0));
DrawCircle((0.06086^e123) + (0.19544^e124) + (0.19564^e125) + (6.64531^e134) + (6.6998^e135) + (0.15286^e145) - (0.65376^e234) - (0.6636^e235) - (0.02942^e245) - (0.48913^e345),rgb(255,0,0));
DrawCircle((0.13918^e123) + (0.75169^e124) + (0.75325^e125) + (6.70743^e134) + (6.76224^e135) + (0.22109^e145) + (0.27638^e234) + (0.26864^e235) - (0.04488^e245) - (0.48179^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.22344^e123) + (3.25256^e124) + (3.24744^e125) - (5.12962^e134) - (5.16327^e135) - (0.60733^e145) + (4.63761^e234) + (4.6512^e235) + (0.30404^e245) + (0.38645^e345),rgb(255,0,0));
DrawCircle((0.19984^e123) + (3.90954^e124) + (3.91065^e125) - (3.57722^e134) - (3.61045^e135) - (0.63015^e145) + (4.25747^e234) + (4.27289^e235) + (0.27804^e245) + (0.43183^e345),rgb(255,0,0));
DrawCircle((0.22073^e123) + (3.65026^e124) + (3.64639^e125) - (4.4511^e134) - (4.48573^e135) - (0.65081^e145) + (4.17028^e234) + (4.18161^e235) + (0.26054^e245) + (0.42582^e345),rgb(255,0,0));
DrawCircle((0.24729^e123) + (4.96469^e124) + (4.96429^e125) - (4.1327^e134) - (4.16809^e135) - (0.71717^e145) + (3.78233^e234) + (3.79185^e235) + (0.19733^e245) + (0.38211^e345),rgb(255,0,0));
DrawCircle((0.23091^e123) + (3.54623^e124) + (3.54184^e125) - (4.28914^e134) - (4.32387^e135) - (0.61497^e145) + (4.612^e234) + (4.62284^e235) + (0.25423^e245) + (0.4923^e345),rgb(255,0,0));
DrawCircle((0.48288^e123) - (1.27863^e124) - (1.26913^e125) - (6.67672^e134) - (6.74518^e135) + (0.31263^e145) - (0.93619^e234) - (0.97417^e235) + (0.119^e245) + (0.39248^e345),rgb(255,0,0));
DrawCircle((0.40134^e123) - (1.85107^e124) - (1.8399^e125) - (5.20495^e134) - (5.26667^e135) + (0.42963^e145) - (1.18636^e234) - (1.23417^e235) + (0.25351^e245) + (0.43749^e345),rgb(255,0,0));
DrawCircle((0.42165^e123) - (0.80145^e124) - (0.78728^e125) - (6.2071^e134) - (6.27596^e135) + (0.33944^e145) - (0.76981^e234) - (0.80555^e235) + (0.09381^e245) + (0.40049^e345),rgb(255,0,0));
DrawCircle((0.39529^e123) - (1.71066^e124) - (1.69797^e125) - (5.50664^e134) - (5.57708^e135) + (0.48159^e145) - (0.7367^e234) - (0.76983^e235) + (0.16702^e245) + (0.33024^e345),rgb(255,0,0));
DrawCircle((0.39139^e123) - (1.30102^e124) - (1.28645^e125) - (5.76676^e134) - (5.83834^e135) + (0.45268^e145) - (0.67414^e234) - (0.70386^e235) + (0.12387^e245) + (0.3145^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.88493^e123) + (10.30949^e124) + (10.32827^e125) + (10.94068^e134) + (10.99576^e135) + (0.40954^e145) + (0.33587^e234) + (0.32776^e235) - (0.10157^e245) - (0.12113^e345),rgb(255, 0, 0));
DrawCircle((0.87426^e123) + (10.14283^e124) + (10.15994^e125) + (10.85403^e134) + (10.90984^e135) + (0.4351^e145) - (0.18897^e234) - (0.19569^e235) - (0.07425^e245) - (0.07135^e345),rgb(255, 0, 0));
DrawCircle((0.82853^e123) + (10.00928^e124) + (10.03129^e125) + (9.93766^e134) + (9.99211^e135) + (0.39371^e145) + (0.89255^e234) + (0.89097^e235) - (0.04284^e245) - (0.07764^e345),rgb(255, 0, 0));
DrawCircle((0.83843^e123) + (9.51775^e124) + (9.53455^e125) + (10.62696^e134) + (10.6831^e135) + (0.42429^e145) - (0.56486^e234) - (0.56922^e235) - (0.03814^e245) - (0.01741^e345),rgb(255, 0, 0));
DrawCircle((0.87858^e123) + (9.54047^e124) + (9.5543^e125) + (11.40645^e134) + (11.46262^e135) + (0.43031^e145) - (1.32975^e234) - (1.34004^e235) - (0.09078^e245) - (0.04855^e345),rgb(255, 0, 0));
DrawCircle((0.89483^e123) + (7.85031^e124) + (7.8585^e125) + (12.9735^e134) + (13.03166^e135) + (0.39136^e145) + (1.13714^e234) + (1.13562^e235) - (0.02376^e245) - (0.09595^e345),rgb(255, 0, 0));
DrawCircle((0.85771^e123) + (10.44457^e124) + (10.46664^e125) + (10.10162^e134) + (10.15439^e135) + (0.38271^e145) - (1.36389^e234) - (1.37728^e235) - (0.12799^e245) - (0.07381^e345),rgb(255, 0, 0));
DrawCircle((0.84967^e123) + (9.51783^e124) + (9.53284^e125) + (10.82869^e134) + (10.88359^e135) + (0.42357^e145) - (0.89364^e234) - (0.90821^e235) - (0.14745^e245) - (0.12799^e345),rgb(255, 0, 0));
DrawCircle((0.8979^e123) + (10.4378^e124) + (10.45674^e125) + (10.71825^e134) + (10.77387^e135) + (0.4204^e145) + (2.99304^e234) + (2.9929^e235) - (0.06471^e245) - (0.187^e345),rgb(255, 0, 0));
DrawCircle((0.86731^e123) + (9.28927^e124) + (9.30456^e125) + (11.45539^e134) + (11.51178^e135) + (0.40203^e145) - (0.16467^e234) - (0.1709^e235) - (0.06387^e245) - (0.07164^e345),rgb(255, 0, 0));
DrawCircle(-(0.3663^e123) + (9.85688^e124) + (9.86981^e125) + (2.07338^e134) + (2.08487^e135) - (0.23613^e145) - (1.59782^e234) - (1.5662^e235) - (0.90722^e245) - (0.22911^e345),rgb(0, 255, 0));
DrawCircle(-(0.37368^e123) + (10.29711^e124) + (10.31104^e125) + (0.2588^e134) + (0.26141^e135) - (0.06221^e145) - (2.22584^e234) - (2.1927^e235) - (0.99617^e245) - (0.03848^e345),rgb(0, 255, 0));
DrawCircle(-(0.34765^e123) + (9.56679^e124) + (9.57946^e125) + (0.49107^e134) + (0.50077^e135) - (0.2489^e145) - (1.87023^e234) - (1.83792^e235) - (0.9575^e245) - (0.09781^e345),rgb(0, 255, 0));
DrawCircle(-(0.33719^e123) + (9.22936^e124) + (9.24273^e125) + (0.3227^e134) + (0.32734^e135) - (0.11417^e145) - (2.36938^e234) - (2.33624^e235) - (1.00128^e245) - (0.06432^e345),rgb(0, 255, 0));
DrawCircle(-(0.34944^e123) + (9.58429^e124) + (9.59658^e125) + (1.0817^e134) + (1.09208^e135) - (0.2466^e145) - (1.40767^e234) - (1.37541^e235) - (0.93414^e245) - (0.14165^e345),rgb(0, 255, 0));
DrawCircle(-(0.37079^e123) + (10.14427^e124) + (10.1598^e125) - (0.84369^e134) - (0.84281^e135) - (0.05945^e145) - (1.81293^e234) - (1.78042^e235) - (0.96541^e245) + (0.06967^e345),rgb(0, 255, 0));
DrawCircle(-(0.36436^e123) + (9.78176^e124) + (9.79806^e125) + (1.1846^e134) + (1.19032^e135) - (0.10042^e145) - (2.6167^e234) - (2.58507^e235) - (0.96633^e245) - (0.14389^e345),rgb(0, 255, 0));
DrawCircle(-(0.34569^e123) + (8.9929^e124) + (9.00984^e125) + (1.22976^e134) + (1.23594^e135) - (0.10053^e145) - (3.73398^e234) - (3.70278^e235) - (0.9948^e245) - (0.17778^e345),rgb(0, 255, 0));
DrawCircle(-(0.33632^e123) + (9.17513^e124) + (9.19013^e125) + (0.49782^e134) + (0.5003^e135) - (0.04551^e145) - (1.86868^e234) - (1.83599^e235) - (0.9749^e245) - (0.06216^e345),rgb(0, 255, 0));
DrawCircle(-(0.3523^e123) + (9.78055^e124) + (9.79255^e125) - (0.5099^e134) - (0.50448^e135) - (0.16774^e145) - (1.425^e234) - (1.39145^e235) - (0.97999^e245) + (0.02665^e345),rgb(0, 255, 0));
DrawCircle(-(0.53407^e123) + (8.36079^e124) + (8.37517^e125) + (2.04252^e134) + (1.99558^e135) + (0.7898^e145) - (4.38255^e234) - (4.41139^e235) + (0.33357^e245) + (0.49549^e345),rgb(127, 127, 0));
DrawCircle(-(0.47425^e123) + (7.16758^e124) + (7.18443^e125) + (2.02517^e134) + (1.97966^e135) + (0.75973^e145) - (3.948^e234) - (3.97778^e235) + (0.3098^e245) + (0.506^e345),rgb(127, 127, 0));
DrawCircle(-(0.49462^e123) + (6.61615^e124) + (6.6341^e125) + (1.9092^e134) + (1.86349^e135) + (0.68075^e145) - (5.37178^e234) - (5.40059^e235) + (0.19032^e245) + (0.60763^e345),rgb(127, 127, 0));
DrawCircle(-(0.48855^e123) + (7.15429^e124) + (7.17235^e125) + (0.90381^e134) + (0.85523^e135) + (0.74476^e145) - (4.68529^e234) - (4.70887^e235) + (0.17208^e245) + (0.50948^e345),rgb(127, 127, 0));
DrawCircle(-(0.48842^e123) + (7.6006^e124) + (7.61162^e125) + (0.99069^e134) + (0.94224^e135) + (0.77626^e145) - (4.12236^e234) - (4.15017^e235) + (0.33978^e245) + (0.46531^e345),rgb(127, 127, 0));
DrawCircle(-(0.51811^e123) + (8.21754^e124) + (8.24225^e125) + (2.92627^e134) + (2.88192^e135) + (0.84303^e145) - (3.21511^e234) - (3.24088^e235) + (0.2554^e245) + (0.42078^e345),rgb(127, 127, 0));
DrawCircle(-(0.47837^e123) + (6.98614^e124) + (6.9955^e125) + (1.9682^e134) + (1.92172^e135) + (0.71723^e145) - (4.62157^e234) - (4.6531^e235) + (0.37009^e245) + (0.57874^e345),rgb(127, 127, 0));
DrawCircle(-(0.42584^e123) + (6.83195^e124) + (6.85349^e125) + (1.00719^e134) + (0.9579^e135) + (0.84181^e145) - (2.88851^e234) - (2.90715^e235) + (0.15296^e245) + (0.37846^e345),rgb(127, 127, 0));
DrawCircle(-(0.51446^e123) + (8.51413^e124) + (8.5322^e125) + (1.32878^e134) + (1.28046^e135) + (0.84634^e145) - (3.17981^e234) - (3.2039^e235) + (0.28705^e245) + (0.36089^e345),rgb(127, 127, 0));
DrawCircle(-(0.51524^e123) + (7.91571^e124) + (7.93639^e125) + (2.25063^e134) + (2.20577^e135) + (0.77964^e145) - (4.03869^e234) - (4.06699^e235) + (0.27263^e245) + (0.47529^e345),rgb(127, 127, 0));
DrawCircle(-(0.35672^e123) + (9.72935^e124) + (9.74355^e125) + (0.56693^e134) + (0.57288^e135) - (0.13991^e145) - (2.11884^e234) - (2.08612^e235) - (0.9769^e245) - (0.08739^e345),rgb(0,0,0));
DrawCircle(-(0.49678^e123) + (7.60925^e124) + (7.62659^e125) + (1.7609^e134) + (1.71359^e135) + (0.78608^e145) - (4.07877^e234) - (4.10578^e235) + (0.27133^e245) + (0.48415^e345),rgb(0,0,0));
DrawCircle((0.87516^e123) + (9.83113^e124) + (9.84799^e125) + (11.07339^e134) + (11.12954^e135) + (0.41755^e145) + (0.07662^e234) + (0.06987^e235) - (0.0773^e245) - (0.09032^e345),rgb(0,0,0));