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.52771^e123) - (6.66178^e124) - (6.65676^e125) + (0.01409^e134) + (0.0285^e135) - (0.18202^e145) + (13.73453^e234) + (13.76668^e235) - (0.53629^e245) - (0.37414^e345),rgb(255,0,0));
DrawCircle((0.49008^e123) - (9.18368^e124) - (9.18098^e125) + (4.09018^e134) + (4.11573^e135) - (0.50135^e145) + (9.64964^e234) + (9.67425^e235) - (0.5143^e245) - (0.29773^e345),rgb(255,0,0));
DrawCircle((0.47534^e123) - (8.27104^e124) - (8.27599^e125) + (0.25166^e134) + (0.27308^e135) - (0.37002^e145) + (11.10787^e234) + (11.13585^e235) - (0.37115^e245) - (0.48563^e345),rgb(255,0,0));
DrawCircle((0.53054^e123) - (6.50982^e124) - (6.50998^e125) - (0.22995^e134) - (0.20814^e135) - (0.26763^e145) + (13.69184^e234) + (13.71995^e235) - (0.34084^e245) - (0.57493^e345),rgb(255,0,0));
DrawCircle((0.45228^e123) - (8.31885^e124) - (8.32247^e125) + (1.32562^e134) + (1.34736^e135) - (0.38925^e145) + (10.31982^e234) + (10.34775^e235) - (0.43117^e245) - (0.41417^e345),rgb(255,0,0));
DrawCircle((0.5328^e123) - (7.2731^e124) - (7.27275^e125) - (2.22577^e134) - (2.21096^e135) - (0.20068^e145) + (13.24995^e234) + (13.2823^e235) - (0.4501^e245) - (0.50334^e345),rgb(255,0,0));
DrawCircle((0.54973^e123) - (4.54162^e124) - (4.53636^e125) - (2.09682^e134) - (2.08067^e135) - (0.11336^e145) + (14.91066^e234) + (14.94193^e235) - (0.40085^e245) - (0.55724^e345),rgb(255,0,0));
DrawCircle((0.44547^e123) - (6.7609^e124) - (6.76287^e125) + (1.92617^e134) + (1.94761^e135) - (0.31688^e145) + (11.5696^e234) + (11.59793^e235) - (0.37884^e245) - (0.43433^e345),rgb(255,0,0));
DrawCircle((0.42316^e123) - (4.85213^e124) - (4.84941^e125) + (3.27939^e134) + (3.30476^e135) - (0.31202^e145) + (11.45137^e234) + (11.47616^e235) - (0.35778^e245) - (0.49458^e345),rgb(255,0,0));
DrawCircle((0.48825^e123) - (7.75955^e124) - (7.76211^e125) - (0.27647^e134) - (0.25437^e135) - (0.35264^e145) + (11.6388^e234) + (11.66656^e235) - (0.38041^e245) - (0.54249^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.04441^e123) - (3.11537^e124) - (3.13596^e125) - (7.30715^e134) - (7.35465^e135) + (0.05635^e145) - (3.58125^e234) - (3.60406^e235) + (0.06082^e245) + (0.07787^e345),rgb(255,0,0));
DrawCircle(-(0.04134^e123) - (3.16322^e124) - (3.18373^e125) - (7.30098^e134) - (7.34846^e135) - (0.01235^e145) - (3.60696^e234) - (3.62989^e235) + (0.03444^e245) + (0.09358^e345),rgb(255,0,0));
DrawCircle(-(0.04576^e123) - (3.23959^e124) - (3.26129^e125) - (6.70164^e134) - (6.74566^e135) + (0.06147^e145) - (4.38615^e234) - (4.41428^e235) + (0.08827^e245) + (0.09938^e345),rgb(255,0,0));
DrawCircle(-(0.07381^e123) - (3.7509^e124) - (3.77555^e125) - (7.47827^e134) - (7.52691^e135) + (0.0255^e145) - (2.47396^e234) - (2.48902^e235) + (0.06091^e245) + (0.10461^e345),rgb(255,0,0));
DrawCircle(-(0.09645^e123) - (1.80905^e124) - (1.8212^e125) - (7.81739^e134) - (7.86801^e135) + (0.03501^e145) - (3.59608^e234) - (3.61821^e235) + (0.0378^e245) + (0.09375^e345),rgb(255,0,0));
DrawCircle((0.00946^e123) - (7.93959^e124) - (7.97137^e125) + (0.6978^e134) + (0.70135^e135) - (0.63903^e145) - (2.36137^e234) - (2.37087^e235) + (0.03704^e245) + (0.1868^e345),rgb(255,0,0));
DrawCircle((0.01761^e123) - (7.68957^e124) - (7.72219^e125) - (0.86057^e134) - (0.86271^e135) - (0.65819^e145) - (1.4846^e234) - (1.49122^e235) + (0.14324^e245) + (0.1431^e345),rgb(255,0,0));
DrawCircle((0.01606^e123) - (7.76742^e124) - (7.7994^e125) - (0.71245^e134) - (0.71405^e135) - (0.64522^e145) - (2.23276^e234) - (2.2421^e235) + (0.072^e245) + (0.19207^e345),rgb(255,0,0));
DrawCircle((0.01413^e123) - (7.46301^e124) - (7.49435^e125) - (2.10469^e134) - (2.11228^e135) - (0.6568^e145) - (2.02798^e234) - (2.03652^e235) + (0.01354^e245) + (0.1823^e345),rgb(255,0,0));
DrawCircle((0.00746^e123) - (7.66835^e124) - (7.70037^e125) - (0.53179^e134) - (0.53338^e135) - (0.64617^e145) - (2.18338^e234) - (2.1926^e235) + (0.10861^e245) + (0.19151^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.07699^e123) + (0.09125^e124) + (0.08988^e125) + (1.91178^e134) + (1.80039^e135) - (0.09792^e145) - (0.78427^e234) - (0.68858^e235) + (0.09942^e245) + (1.24143^e345),rgb(127, 127, 0));
DrawCircle((0.13501^e123) + (0.69276^e124) + (0.67753^e125) + (3.37664^e134) + (3.25702^e135) - (0.23292^e145) - (0.85093^e234) - (0.7671^e235) + (0.33413^e245) + (1.34251^e345),rgb(127, 127, 0));
DrawCircle((0.08638^e123) + (0.50933^e124) + (0.49147^e125) + (1.98374^e134) + (1.86752^e135) - (0.27494^e145) - (0.6377^e234) - (0.54971^e235) + (0.38694^e245) + (1.16279^e345),rgb(127, 127, 0));
DrawCircle((0.02901^e123) + (0.1562^e124) + (0.15309^e125) + (1.69994^e134) + (1.574^e135) - (0.49597^e145) - (0.76927^e234) - (0.69379^e235) + (0.32398^e245) + (1.08332^e345),rgb(127, 127, 0));
DrawCircle((0.15412^e123) + (0.67635^e124) + (0.65863^e125) + (2.5128^e134) + (2.39375^e135) - (0.23357^e145) - (0.19931^e234) - (0.11517^e235) + (0.34636^e245) + (1.21798^e345),rgb(127, 127, 0));
DrawCircle((0.10999^e123) + (0.73194^e124) + (0.71607^e125) + (2.40418^e134) + (2.28771^e135) - (0.42814^e145) - (0.74382^e234) - (0.65578^e235) + (0.47857^e245) + (1.13684^e345),rgb(127, 127, 0));
DrawCircle((0.05706^e123) + (0.56945^e124) + (0.54529^e125) + (2.49963^e134) + (2.37888^e135) - (0.1467^e145) - (1.05207^e234) - (0.97206^e235) + (0.35305^e245) + (1.2787^e345),rgb(127, 127, 0));
DrawCircle(-(0.00013^e123) + (0.47947^e124) + (0.45383^e125) + (2.20885^e134) + (2.09079^e135) - (0.18365^e145) - (1.56376^e234) - (1.48026^e235) + (0.40365^e245) + (1.26058^e345),rgb(127, 127, 0));
DrawCircle((0.11385^e123) + (0.36941^e124) + (0.37057^e125) + (3.07113^e134) + (2.9483^e135) - (0.42995^e145) - (0.83226^e234) - (0.75177^e235) + (0.26968^e245) + (1.27334^e345),rgb(127, 127, 0));
DrawCircle((0.09592^e123) + (0.98803^e124) + (0.95126^e125) + (2.74171^e134) + (2.62564^e135) - (0.14451^e145) - (0.90282^e234) - (0.8207^e235) + (0.49976^e245) + (1.25474^e345),rgb(127, 127, 0));
DrawCircle(-(0.15858^e123) + (4.09456^e124) + (4.10106^e125) + (1.46339^e134) + (1.42718^e135) + (0.99491^e145) + (0.65834^e234) + (0.6472^e235) + (0.31463^e245) - (0.04752^e345),rgb(0, 255, 0));
DrawCircle(-(0.15762^e123) + (3.93586^e124) + (3.94356^e125) + (2.36497^e134) + (2.33203^e135) + (0.93819^e145) + (0.53915^e234) + (0.52091^e235) + (0.48181^e245) + (0.161^e345),rgb(0, 255, 0));
DrawCircle(-(0.14849^e123) + (3.82818^e124) + (3.83437^e125) + (1.3928^e134) + (1.35693^e135) + (0.98277^e145) + (0.72596^e234) + (0.71361^e235) + (0.34874^e245) - (0.05949^e345),rgb(0, 255, 0));
DrawCircle(-(0.17955^e123) + (4.5552^e124) + (4.56369^e125) + (2.30609^e134) + (2.27002^e135) + (1.02415^e145) + (0.65343^e234) + (0.64321^e235) + (0.29019^e245) + (0.0^e345),rgb(0, 255, 0));
DrawCircle(-(0.18322^e123) + (4.77196^e124) + (4.77853^e125) + (0.97455^e134) + (0.93869^e135) + (0.96897^e145) + (0.26058^e234) + (0.2484^e235) + (0.32645^e245) + (0.01376^e345),rgb(0, 255, 0));
DrawCircle(-(0.17445^e123) + (4.5751^e124) + (4.58068^e125) + (2.48048^e134) + (2.44368^e135) + (1.04458^e145) + (0.25085^e234) + (0.24127^e235) + (0.25923^e245) + (0.08327^e345),rgb(0, 255, 0));
DrawCircle(-(0.15577^e123) + (3.83457^e124) + (3.84364^e125) + (2.38697^e134) + (2.35202^e135) + (0.99945^e145) + (0.44605^e234) + (0.43288^e235) + (0.35011^e245) + (0.10168^e345),rgb(0, 255, 0));
DrawCircle(-(0.13127^e123) + (3.36143^e124) + (3.36636^e125) + (2.48384^e134) + (2.44742^e135) + (1.02596^e145) + (1.35242^e234) + (1.34116^e235) + (0.33922^e245) - (0.16212^e345),rgb(0, 255, 0));
DrawCircle(-(0.14763^e123) + (3.73235^e124) + (3.74104^e125) + (1.3391^e134) + (1.30386^e135) + (0.96966^e145) + (0.49885^e234) + (0.48619^e235) + (0.34958^e245) - (0.00418^e345),rgb(0, 255, 0));
DrawCircle(-(0.17281^e123) + (4.27556^e124) + (4.2855^e125) + (2.38122^e134) + (2.3449^e135) + (1.03562^e145) + (0.68717^e234) + (0.67946^e235) + (0.23014^e245) - (0.03827^e345),rgb(0, 255, 0));
DrawCircle((0.12343^e123) + (2.70228^e124) + (2.70698^e125) + (0.5528^e134) + (0.57711^e135) + (0.51126^e145) - (3.94734^e234) - (3.96637^e235) - (0.2666^e245) + (0.69229^e345),rgb(255, 0, 0));
DrawCircle((0.11317^e123) + (2.27291^e124) + (2.27669^e125) + (1.72368^e134) + (1.75234^e135) + (0.51794^e145) - (3.58488^e234) - (3.59673^e235) - (0.11842^e245) + (0.7271^e345),rgb(255, 0, 0));
DrawCircle((0.10872^e123) + (2.03823^e124) + (2.04019^e125) + (2.21648^e134) + (2.2436^e135) + (0.4686^e145) - (4.06662^e234) - (4.08198^e235) - (0.21475^e245) + (0.70141^e345),rgb(255, 0, 0));
DrawCircle((0.10754^e123) + (1.9695^e124) + (1.97088^e125) + (2.13333^e134) + (2.1612^e135) + (0.48294^e145) - (3.81041^e234) - (3.82444^e235) - (0.20796^e245) + (0.70909^e345),rgb(255, 0, 0));
DrawCircle((0.08554^e123) + (1.84893^e124) + (1.85208^e125) + (1.6967^e134) + (1.72395^e135) + (0.52664^e145) - (3.1236^e234) - (3.13854^e235) - (0.20807^e245) + (0.69877^e345),rgb(255, 0, 0));
DrawCircle((0.11009^e123) + (2.17723^e124) + (2.17997^e125) + (1.02499^e134) + (1.05218^e135) + (0.51224^e145) - (3.51733^e234) - (3.53245^e235) - (0.21131^e245) + (0.72805^e345),rgb(255, 0, 0));
DrawCircle((0.11105^e123) + (2.26047^e124) + (2.26369^e125) + (1.52215^e134) + (1.54896^e135) + (0.5017^e145) - (3.81922^e234) - (3.83491^e235) - (0.20862^e245) + (0.70718^e345),rgb(255, 0, 0));
DrawCircle((0.13003^e123) + (2.3675^e124) + (2.36903^e125) + (1.73901^e134) + (1.76655^e135) + (0.48101^e145) - (4.29279^e234) - (4.30743^e235) - (0.21599^e245) + (0.71352^e345),rgb(255, 0, 0));
DrawCircle((0.1092^e123) + (1.94164^e124) + (1.94259^e125) + (1.78812^e134) + (1.81615^e135) + (0.48294^e145) - (3.70423^e234) - (3.71797^e235) - (0.21221^e245) + (0.72592^e345),rgb(255, 0, 0));
DrawCircle((0.12149^e123) + (2.54342^e124) + (2.54649^e125) + (2.25456^e134) + (2.28387^e135) + (0.55674^e145) - (3.62284^e234) - (3.63318^e235) - (0.12492^e245) + (0.68229^e345),rgb(255, 0, 0));
DrawCircle(-(0.16187^e123) + (4.12316^e124) + (4.13057^e125) + (1.96524^e134) + (1.92932^e135) + (1.00481^e145) + (0.62775^e234) + (0.61586^e235) + (0.33169^e245) + (0.00511^e345),rgb(0,0,0));
DrawCircle((0.08952^e123) + (0.5199^e124) + (0.5045^e125) + (2.48057^e134) + (2.36031^e135) - (0.2718^e145) - (0.83748^e234) - (0.75203^e235) + (0.35218^e245) + (1.24252^e345),rgb(0,0,0));
DrawCircle((0.11159^e123) + (2.21199^e124) + (2.21461^e125) + (1.66372^e134) + (1.6912^e135) + (0.50553^e145) - (3.76197^e234) - (3.77647^e235) - (0.19904^e245) + (0.71006^e345),rgb(0,0,0));