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:
    sc.add_circle(c,'rgb(255,0,0)')
print(sc)
DrawCircle(-(0.41118^e123) - (1.91292^e124) - (1.8667^e125) - (2.33801^e134) - (2.32664^e135) - (0.20991^e145) - (2.20627^e234) - (2.30607^e235) - (0.71231^e245) - (0.6285^e345),rgb(255,0,0));
DrawCircle(-(0.34792^e123) - (1.2574^e124) - (1.21299^e125) - (2.10183^e134) - (2.09139^e135) - (0.23051^e145) - (1.94467^e234) - (2.04539^e235) - (0.6122^e245) - (0.66684^e345),rgb(255,0,0));
DrawCircle(-(0.40317^e123) - (1.73566^e124) - (1.71474^e125) - (2.75313^e134) - (2.7707^e135) - (0.2185^e145) - (1.6057^e234) - (1.71284^e235) - (0.54458^e245) - (0.66167^e345),rgb(255,0,0));
DrawCircle(-(0.4085^e123) - (0.66661^e124) - (0.62089^e125) - (2.67678^e134) - (2.66064^e135) - (0.2733^e145) - (2.42326^e234) - (2.52264^e235) - (0.43342^e245) - (0.74689^e345),rgb(255,0,0));
DrawCircle(-(0.58233^e123) - (0.71035^e124) - (0.63268^e125) - (3.78289^e134) - (3.77409^e135) - (0.49379^e145) - (3.74938^e234) - (3.82759^e235) - (0.59546^e245) - (0.56471^e345),rgb(255,0,0));
DrawCircle(-(0.58938^e123) - (1.55346^e124) - (1.50891^e125) - (3.52022^e134) - (3.51662^e135) - (0.25658^e145) - (3.67793^e234) - (3.77907^e235) - (0.54457^e245) - (0.62655^e345),rgb(255,0,0));
DrawCircle(-(0.56977^e123) - (1.89339^e124) - (1.8406^e125) - (3.39013^e134) - (3.38471^e135) - (0.29604^e145) - (3.47401^e234) - (3.57101^e235) - (0.64422^e245) - (0.61029^e345),rgb(255,0,0));
DrawCircle(-(0.48071^e123) - (2.36558^e124) - (2.30024^e125) - (3.21931^e134) - (3.22595^e135) - (0.47028^e145) - (2.22814^e234) - (2.31709^e235) - (0.7406^e245) - (0.56492^e345),rgb(255,0,0));
DrawCircle(-(0.50455^e123) - (1.20574^e124) - (1.16179^e125) - (3.78336^e134) - (3.77297^e135) - (0.30471^e145) - (2.39006^e234) - (2.49099^e235) - (0.44938^e245) - (0.80606^e345),rgb(255,0,0));
DrawCircle(-(0.37849^e123) - (0.77877^e124) - (0.76376^e125) - (2.45795^e134) - (2.46136^e135) - (0.10454^e145) - (2.49926^e234) - (2.60876^e235) - (0.32447^e245) - (0.68859^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:
    sc.add_circle(c,'rgb(255,0,0)')
print(sc)
DrawCircle(-(0.3714^e123) - (2.72555^e124) - (2.74793^e125) + (8.66057^e134) + (8.71685^e135) - (0.10879^e145) - (1.01367^e234) - (1.02345^e235) - (0.01064^e245) + (0.07426^e345),rgb(255,0,0));
DrawCircle(-(0.32021^e123) - (1.74502^e124) - (1.7642^e125) + (8.45434^e134) + (8.51197^e135) - (0.19249^e145) - (0.8727^e234) - (0.88138^e235) + (0.005^e245) + (0.07206^e345),rgb(255,0,0));
DrawCircle(-(0.35302^e123) - (3.26065^e124) - (3.28756^e125) + (8.38322^e134) + (8.4381^e135) - (0.13219^e145) - (0.70077^e234) - (0.70607^e235) + (0.00452^e245) + (0.01679^e345),rgb(255,0,0));
DrawCircle(-(0.32491^e123) - (2.62664^e124) - (2.65081^e125) + (8.25308^e134) + (8.30855^e135) - (0.16568^e145) - (0.78879^e234) - (0.79895^e235) - (0.02344^e245) + (0.12342^e345),rgb(255,0,0));
DrawCircle(-(0.29156^e123) - (3.18899^e124) - (3.21595^e125) + (8.02152^e134) + (8.07627^e135) - (0.14308^e145) - (0.7611^e234) - (0.76735^e235) + (0.00202^e245) + (0.02905^e345),rgb(255,0,0));
DrawCircle((0.05708^e123) - (2.2634^e124) - (2.31254^e125) - (2.19754^e134) - (2.24969^e135) + (0.1758^e145) + (1.50236^e234) + (1.52443^e235) + (0.41853^e245) + (0.52304^e345),rgb(255,0,0));
DrawCircle((0.14807^e123) - (1.86048^e124) - (1.90893^e125) - (1.39176^e134) - (1.44351^e135) + (0.19489^e145) + (2.31829^e234) + (2.34273^e235) + (0.45136^e245) + (0.58049^e345),rgb(255,0,0));
DrawCircle((0.07677^e123) - (2.33879^e124) - (2.38905^e125) - (2.16902^e134) - (2.2216^e135) + (0.18201^e145) + (1.50311^e234) + (1.52133^e235) + (0.42907^e245) + (0.51489^e345),rgb(255,0,0));
DrawCircle((0.13472^e123) - (1.85608^e124) - (1.89987^e125) - (1.79805^e134) - (1.85598^e135) + (0.21364^e145) + (1.99298^e234) + (2.01166^e235) + (0.39039^e245) + (0.60758^e345),rgb(255,0,0));
DrawCircle((0.0887^e123) - (1.87061^e124) - (1.91902^e125) - (1.78365^e134) - (1.83525^e135) + (0.11474^e145) + (1.81983^e234) + (1.84465^e235) + (0.46965^e245) + (0.55944^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.22666^e123) - (6.80156^e124) - (6.82843^e125) - (9.53174^e134) - (9.56327^e135) - (0.18402^e145) - (0.5039^e234) - (0.5097^e235) + (0.11456^e245) + (0.17418^e345),rgb(255, 0, 0));
DrawCircle((0.26435^e123) - (7.34844^e124) - (7.37689^e125) - (9.50354^e134) - (9.53414^e135) - (0.17217^e145) + (0.71104^e234) + (0.70901^e235) + (0.13292^e245) + (0.15524^e345),rgb(255, 0, 0));
DrawCircle((0.21071^e123) - (8.72727^e124) - (8.75925^e125) - (8.10302^e134) - (8.1298^e135) - (0.1207^e145) + (0.07671^e234) + (0.0736^e235) + (0.14035^e245) + (0.12925^e345),rgb(255, 0, 0));
DrawCircle((0.24528^e123) - (6.70169^e124) - (6.72872^e125) - (9.61596^e134) - (9.64786^e135) - (0.18831^e145) + (1.56143^e234) + (1.56264^e235) + (0.13892^e245) + (0.15546^e345),rgb(255, 0, 0));
DrawCircle((0.21975^e123) - (6.98235^e124) - (7.00983^e125) - (9.34916^e134) - (9.38056^e135) - (0.17117^e145) + (0.35261^e234) + (0.34972^e235) + (0.13575^e245) + (0.17312^e345),rgb(255, 0, 0));
DrawCircle((0.26916^e123) - (6.85711^e124) - (6.88401^e125) - (9.85007^e134) - (9.88208^e135) - (0.16891^e145) + (1.58941^e234) + (1.59052^e235) + (0.13069^e245) + (0.14858^e345),rgb(255, 0, 0));
DrawCircle((0.26661^e123) - (6.10919^e124) - (6.13425^e125) - (10.03557^e134) - (10.06886^e135) - (0.18052^e145) + (0.63193^e234) + (0.6283^e235) + (0.1428^e245) + (0.2159^e345),rgb(255, 0, 0));
DrawCircle((0.23732^e123) - (6.04841^e124) - (6.0727^e125) - (10.29089^e134) - (10.32478^e135) - (0.18976^e145) + (0.00527^e234) + (0.00201^e235) + (0.08362^e245) + (0.14211^e345),rgb(255, 0, 0));
DrawCircle((0.2466^e123) - (7.70161^e124) - (7.73162^e125) - (8.88805^e134) - (8.91718^e135) - (0.17165^e145) + (1.30487^e234) + (1.30484^e235) + (0.15958^e245) + (0.15508^e345),rgb(255, 0, 0));
DrawCircle((0.2735^e123) - (6.36684^e124) - (6.39194^e125) - (10.2299^e134) - (10.26193^e135) - (0.19342^e145) - (1.81621^e234) - (1.82588^e235) + (0.05837^e245) + (0.14895^e345),rgb(255, 0, 0));
DrawCircle((0.08857^e123) - (2.57309^e124) - (2.58021^e125) + (6.64566^e134) + (6.68042^e135) - (0.47544^e145) - (0.67109^e234) - (0.66776^e235) - (0.15075^e245) + (0.51335^e345),rgb(127, 127, 0));
DrawCircle((0.06505^e123) - (0.97138^e124) - (0.97173^e125) + (6.5939^e134) + (6.62885^e135) - (0.48575^e145) + (0.32202^e234) + (0.32904^e235) - (0.1031^e245) + (0.53883^e345),rgb(127, 127, 0));
DrawCircle((0.09234^e123) - (1.8497^e124) - (1.85373^e125) + (7.16993^e134) + (7.20395^e135) - (0.36906^e145) + (0.52279^e234) + (0.53264^e235) - (0.17456^e245) + (0.57235^e345),rgb(127, 127, 0));
DrawCircle((0.08361^e123) - (2.28027^e124) - (2.28656^e125) + (6.82087^e134) + (6.85403^e135) - (0.39157^e145) + (0.99272^e234) + (1.00417^e235) - (0.23767^e245) + (0.54045^e345),rgb(127, 127, 0));
DrawCircle((0.09807^e123) - (2.16911^e124) - (2.17455^e125) + (6.85708^e134) + (6.89194^e135) - (0.39071^e145) - (0.64694^e234) - (0.64191^e235) - (0.14726^e245) + (0.58206^e345),rgb(127, 127, 0));
DrawCircle((0.08806^e123) - (1.16405^e124) - (1.16541^e125) + (6.76274^e134) + (6.79621^e135) - (0.33802^e145) + (0.80869^e234) + (0.82088^e235) - (0.14855^e245) + (0.62817^e345),rgb(127, 127, 0));
DrawCircle((0.09582^e123) - (2.04637^e124) - (2.05112^e125) + (7.0365^e134) + (7.07052^e135) - (0.3774^e145) + (0.36382^e234) + (0.37336^e235) - (0.18556^e245) + (0.57094^e345),rgb(127, 127, 0));
DrawCircle((0.07139^e123) - (1.90666^e124) - (1.91209^e125) + (6.89404^e134) + (6.92839^e135) - (0.39282^e145) + (0.3984^e234) + (0.40621^e235) - (0.17845^e245) + (0.56314^e345),rgb(127, 127, 0));
DrawCircle((0.11792^e123) - (2.22334^e124) - (2.22931^e125) + (7.19659^e134) + (7.23161^e135) - (0.29563^e145) - (1.50726^e234) - (1.50441^e235) - (0.13008^e245) + (0.62147^e345),rgb(127, 127, 0));
DrawCircle((0.0369^e123) - (0.40141^e124) - (0.40129^e125) + (7.34636^e134) + (7.38151^e135) - (0.40662^e145) + (0.66323^e234) + (0.66919^e235) - (0.06694^e245) + (0.55329^e345),rgb(127, 127, 0));
DrawCircle(-(0.61355^e123) - (7.6561^e124) - (7.66479^e125) - (9.24655^e134) - (9.29482^e135) - (0.4714^e145) + (4.56661^e234) + (4.5708^e235) - (0.01234^e245) - (0.29607^e345),rgb(0, 255, 0));
DrawCircle(-(0.59227^e123) - (5.89291^e124) - (5.89533^e125) - (10.23632^e134) - (10.28536^e135) - (0.4461^e145) + (4.28089^e234) + (4.28434^e235) + (0.01689^e245) - (0.29473^e345),rgb(0, 255, 0));
DrawCircle(-(0.60133^e123) - (6.31149^e124) - (6.31505^e125) - (10.31563^e134) - (10.36467^e135) - (0.45352^e145) + (3.92967^e234) + (3.93209^e235) + (0.00213^e245) - (0.27889^e345),rgb(0, 255, 0));
DrawCircle(-(0.60995^e123) - (5.59389^e124) - (5.5949^e125) - (10.48242^e134) - (10.53147^e135) - (0.43246^e145) + (4.85264^e234) + (4.85667^e235) + (0.02888^e245) - (0.32104^e345),rgb(0, 255, 0));
DrawCircle(-(0.56149^e123) - (6.48422^e124) - (6.49028^e125) - (9.43585^e134) - (9.48461^e135) - (0.46133^e145) + (3.80358^e234) + (3.80654^e235) - (0.00684^e245) - (0.28056^e345),rgb(0, 255, 0));
DrawCircle(-(0.56045^e123) - (7.33386^e124) - (7.34331^e125) - (9.13115^e134) - (9.17925^e135) - (0.47542^e145) + (2.46618^e234) + (2.46179^e235) - (0.09904^e245) - (0.28319^e345),rgb(0, 255, 0));
DrawCircle(-(0.56724^e123) - (5.51313^e124) - (5.51738^e125) - (10.2111^e134) - (10.2601^e135) - (0.39961^e145) + (3.99981^e234) + (4.00178^e235) - (0.01085^e245) - (0.31001^e345),rgb(0, 255, 0));
DrawCircle(-(0.60223^e123) - (5.26778^e124) - (5.26839^e125) - (10.8602^e134) - (10.90939^e135) - (0.41937^e145) + (3.90688^e234) + (3.90514^e235) - (0.01908^e245) - (0.35036^e345),rgb(0, 255, 0));
DrawCircle(-(0.59668^e123) - (3.95263^e124) - (3.94696^e125) - (10.66202^e134) - (10.71057^e135) - (0.42286^e145) + (5.41204^e234) + (5.41784^e235) + (0.08978^e245) - (0.33681^e345),rgb(0, 255, 0));
DrawCircle(-(0.57085^e123) - (5.98918^e124) - (5.99243^e125) - (9.82156^e134) - (9.87063^e135) - (0.45892^e145) + (3.97075^e234) + (3.97281^e235) - (0.00096^e245) - (0.30583^e345),rgb(0, 255, 0));
DrawCircle(-(0.59123^e123) - (6.06845^e124) - (6.07173^e125) - (10.10468^e134) - (10.15385^e135) - (0.44872^e145) + (4.13652^e234) + (4.13867^e235) - (0.00092^e245) - (0.3074^e345),rgb(0,0,0));
DrawCircle((0.08414^e123) - (1.77826^e124) - (1.78232^e125) + (6.97504^e134) + (7.00964^e135) - (0.39494^e145) + (0.12899^e234) + (0.13653^e235) - (0.15315^e245) + (0.57207^e345),rgb(0,0,0));
DrawCircle((0.24756^e123) - (7.01118^e124) - (7.03867^e125) - (9.60165^e134) - (9.63311^e135) - (0.17518^e145) + (0.39771^e234) + (0.39486^e235) + (0.1247^e245) + (0.16084^e345),rgb(0,0,0));