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.38678^e123) - (1.91742^e124) - (1.94133^e125) + (6.91973^e134) + (6.96132^e135) - (0.22152^e145) + (5.52512^e234) + (5.56136^e235) - (0.16186^e245) - (0.05418^e345),rgb(255,0,0));
DrawCircle(-(0.33987^e123) + (0.75777^e124) + (0.74989^e125) + (7.83819^e134) + (7.89232^e135) - (0.30234^e145) + (3.27911^e234) + (3.30407^e235) - (0.13165^e245) - (0.05347^e345),rgb(255,0,0));
DrawCircle(-(0.37382^e123) - (0.74852^e124) - (0.76404^e125) + (7.58131^e134) + (7.62883^e135) - (0.21951^e145) + (4.82303^e234) + (4.85645^e235) - (0.13327^e245) - (0.06464^e345),rgb(255,0,0));
DrawCircle(-(0.37748^e123) + (0.55994^e124) + (0.55204^e125) + (7.73076^e134) + (7.7784^e135) - (0.23249^e145) + (3.97408^e234) + (4.00989^e235) - (0.13631^e245) - (0.23196^e345),rgb(255,0,0));
DrawCircle(-(0.34061^e123) - (0.80825^e124) - (0.82776^e125) + (7.54742^e134) + (7.59627^e135) - (0.31655^e145) + (3.54831^e234) + (3.57744^e235) - (0.1342^e245) - (0.13655^e345),rgb(255,0,0));
DrawCircle(-(0.3885^e123) - (0.24343^e124) - (0.26138^e125) + (8.32769^e134) + (8.38078^e135) - (0.35155^e145) + (2.11562^e234) + (2.13739^e235) - (0.08412^e245) - (0.1776^e345),rgb(255,0,0));
DrawCircle(-(0.34542^e123) - (1.10837^e124) - (1.12526^e125) + (6.99253^e134) + (7.03374^e135) - (0.20968^e145) + (4.77368^e234) + (4.81407^e235) - (0.10381^e245) - (0.24812^e345),rgb(255,0,0));
DrawCircle(-(0.49254^e123) - (1.20995^e124) - (1.22933^e125) + (7.63914^e134) + (7.68173^e135) - (0.19593^e145) + (6.31907^e234) + (6.35682^e235) - (0.15587^e245) - (0.03919^e345),rgb(255,0,0));
DrawCircle(-(0.3568^e123) - (0.13368^e124) - (0.14936^e125) + (7.73291^e134) + (7.78269^e135) - (0.32107^e145) + (3.08204^e234) + (3.11189^e235) - (0.12422^e245) - (0.21696^e345),rgb(255,0,0));
DrawCircle(-(0.47822^e123) + (0.95099^e124) + (0.93877^e125) + (8.23947^e134) + (8.28673^e135) - (0.30452^e145) + (4.52343^e234) + (4.55852^e235) - (0.18538^e245) - (0.15765^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.05689^e123) + (1.37625^e124) + (1.35096^e125) - (0.72155^e134) - (0.67235^e135) + (0.86954^e145) + (0.99663^e234) + (0.95302^e235) - (0.61175^e245) - (0.30896^e345),rgb(255,0,0));
DrawCircle((0.12766^e123) + (2.63315^e124) + (2.60128^e125) - (0.28908^e134) - (0.24159^e135) + (0.90731^e145) + (0.85413^e234) + (0.81301^e235) - (0.635^e245) - (0.2246^e345),rgb(255,0,0));
DrawCircle((0.02852^e123) + (1.17348^e124) + (1.13794^e125) - (0.70377^e134) - (0.66196^e135) + (0.8435^e145) + (0.92971^e234) + (0.88555^e235) - (0.6589^e245) - (0.27311^e345),rgb(255,0,0));
DrawCircle((0.03978^e123) + (0.99262^e124) + (0.95596^e125) - (0.24846^e134) - (0.20586^e135) + (0.83416^e145) + (0.4909^e234) + (0.44845^e235) - (0.60707^e245) - (0.26059^e345),rgb(255,0,0));
DrawCircle((0.02886^e123) + (1.99057^e124) + (1.95768^e125) - (2.10885^e134) - (2.0592^e135) + (1.02128^e145) + (1.75676^e234) + (1.71916^e235) - (0.59158^e245) - (0.27458^e345),rgb(255,0,0));
DrawCircle((0.46247^e123) + (6.82031^e124) + (6.80696^e125) - (7.2191^e134) - (7.227^e135) - (0.32506^e145) + (1.76699^e234) + (1.712^e235) - (0.75999^e245) + (0.88865^e345),rgb(255,0,0));
DrawCircle((0.54499^e123) + (7.94068^e124) + (7.93765^e125) - (7.17776^e134) - (7.19177^e135) - (0.24408^e145) + (1.21763^e234) + (1.16231^e235) - (0.79917^e245) + (0.75981^e345),rgb(255,0,0));
DrawCircle((0.41905^e123) + (5.40705^e124) + (5.40588^e125) - (6.5543^e134) - (6.55964^e135) - (0.08733^e145) + (2.34971^e234) + (2.29283^e235) - (0.72732^e245) + (0.9196^e345),rgb(255,0,0));
DrawCircle((0.48961^e123) + (7.28099^e124) + (7.27321^e125) - (7.08481^e134) - (7.0916^e135) - (0.21351^e145) + (1.31179^e234) + (1.25559^e235) - (0.81492^e245) + (0.83143^e345),rgb(255,0,0));
DrawCircle((0.47505^e123) + (5.83257^e124) + (5.82608^e125) - (7.67906^e134) - (7.693^e135) - (0.27619^e145) + (3.29739^e234) + (3.24236^e235) - (0.6306^e245) + (0.98638^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.41084^e123) - (5.84018^e124) - (5.8676^e125) - (9.87024^e134) - (9.8526^e135) - (0.90938^e145) + (1.78951^e234) + (1.76575^e235) + (0.45719^e245) + (0.49403^e345),rgb(0, 255, 0));
DrawCircle((0.3952^e123) - (5.80091^e124) - (5.82868^e125) - (9.42414^e134) - (9.40489^e135) - (0.94465^e145) + (2.44344^e234) + (2.4214^e235) + (0.49522^e245) + (0.40663^e345),rgb(0, 255, 0));
DrawCircle((0.39539^e123) - (5.76707^e124) - (5.79434^e125) - (9.12128^e134) - (9.10085^e135) - (0.9271^e145) - (0.1185^e234) - (0.14009^e235) + (0.30675^e245) + (0.50421^e345),rgb(0, 255, 0));
DrawCircle((0.40515^e123) - (6.7082^e124) - (6.73721^e125) - (8.53818^e134) - (8.51723^e135) - (0.95824^e145) + (2.11392^e234) + (2.0953^e235) + (0.45969^e245) + (0.28313^e345),rgb(0, 255, 0));
DrawCircle((0.40373^e123) - (6.57907^e124) - (6.60631^e125) - (8.78371^e134) - (8.76362^e135) - (0.92019^e145) + (1.38788^e234) + (1.36594^e235) + (0.45113^e245) + (0.40819^e345),rgb(0, 255, 0));
DrawCircle((0.42663^e123) - (6.6722^e124) - (6.70212^e125) - (9.80927^e134) - (9.78693^e135) - (1.03727^e145) + (1.95084^e234) + (1.93558^e235) + (0.37558^e245) + (0.24889^e345),rgb(0, 255, 0));
DrawCircle((0.40904^e123) - (6.47351^e124) - (6.50072^e125) - (9.24618^e134) - (9.22735^e135) - (0.91307^e145) + (2.95255^e234) + (2.92948^e235) + (0.56156^e245) + (0.38563^e345),rgb(0, 255, 0));
DrawCircle((0.40396^e123) - (4.89684^e124) - (4.92865^e125) - (9.62289^e134) - (9.60876^e135) - (0.92911^e145) + (3.23645^e234) + (3.21606^e235) + (0.50199^e245) + (0.3724^e345),rgb(0, 255, 0));
DrawCircle((0.42396^e123) - (6.19792^e124) - (6.2258^e125) - (9.73816^e134) - (9.72277^e135) - (0.86533^e145) + (2.40034^e234) + (2.37558^e235) + (0.51986^e245) + (0.48167^e345),rgb(0, 255, 0));
DrawCircle((0.43645^e123) - (6.29616^e124) - (6.32541^e125) - (10.52974^e134) - (10.51065^e135) - (0.98095^e145) + (1.96347^e234) + (1.94328^e235) + (0.4228^e245) + (0.40119^e345),rgb(0, 255, 0));
DrawCircle((0.5069^e123) + (2.11154^e124) + (2.08572^e125) - (3.256^e134) - (3.32643^e135) - (0.45922^e145) + (4.30978^e234) + (4.35947^e235) + (0.42648^e245) + (0.27965^e345),rgb(127, 127, 0));
DrawCircle((0.49373^e123) + (2.18307^e124) + (2.16861^e125) - (2.7412^e134) - (2.81152^e135) - (0.39119^e145) + (4.5812^e234) + (4.63543^e235) + (0.37392^e245) + (0.3514^e345),rgb(127, 127, 0));
DrawCircle((0.48711^e123) + (1.7885^e124) + (1.76667^e125) - (3.67308^e134) - (3.74996^e135) - (0.44688^e145) + (4.00177^e234) + (4.0431^e235) + (0.33108^e245) + (0.31994^e345),rgb(127, 127, 0));
DrawCircle((0.46156^e123) + (1.75501^e124) + (1.73816^e125) - (4.15406^e134) - (4.23564^e135) - (0.46185^e145) + (3.35023^e234) + (3.38424^e235) + (0.2516^e245) + (0.2861^e345),rgb(127, 127, 0));
DrawCircle((0.53657^e123) + (3.4823^e124) + (3.47753^e125) - (2.69754^e134) - (2.77396^e135) - (0.51992^e145) + (4.12631^e234) + (4.17356^e235) + (0.34326^e245) + (0.35017^e345),rgb(127, 127, 0));
DrawCircle((0.43635^e123) + (1.42085^e124) + (1.40259^e125) - (3.35906^e134) - (3.43359^e135) - (0.3833^e145) + (4.02016^e234) + (4.06713^e235) + (0.3212^e245) + (0.32514^e345),rgb(127, 127, 0));
DrawCircle((0.47539^e123) + (2.89626^e124) + (2.89254^e125) - (2.95079^e134) - (3.02672^e135) - (0.48573^e145) + (3.75146^e234) + (3.79957^e235) + (0.32248^e245) + (0.30061^e345),rgb(127, 127, 0));
DrawCircle((0.4555^e123) + (1.73165^e124) + (1.71319^e125) - (3.6373^e134) - (3.71435^e135) - (0.44037^e145) + (3.76949^e234) + (3.81212^e235) + (0.31487^e245) + (0.29722^e345),rgb(127, 127, 0));
DrawCircle((0.53863^e123) + (3.25242^e124) + (3.24954^e125) - (3.04347^e134) - (3.12065^e135) - (0.48236^e145) + (4.21861^e234) + (4.26477^e235) + (0.30135^e245) + (0.34365^e345),rgb(127, 127, 0));
DrawCircle((0.54319^e123) + (2.29975^e124) + (2.28195^e125) - (3.98285^e134) - (4.06093^e135) - (0.46111^e145) + (4.20547^e234) + (4.24648^e235) + (0.31148^e245) + (0.30378^e345),rgb(127, 127, 0));
DrawCircle((2.70953^e123) - (1.5259^e124) - (1.4046^e125) + (21.11776^e134) + (21.16454^e135) - (0.97172^e145) - (14.24211^e234) - (14.39452^e235) + (0.72341^e245) - (0.94201^e345),rgb(255, 0, 0));
DrawCircle((2.61692^e123) - (1.53551^e124) - (1.39186^e125) + (20.10617^e134) + (20.16626^e135) - (1.13897^e145) - (13.61413^e234) - (13.74015^e235) + (0.82128^e245) - (0.65564^e345),rgb(255, 0, 0));
DrawCircle((2.74121^e123) - (0.20019^e124) - (0.06316^e125) + (21.08015^e134) + (21.14735^e135) - (1.05871^e145) - (14.03432^e234) - (14.16406^e235) + (0.71105^e245) - (0.65371^e345),rgb(255, 0, 0));
DrawCircle((2.7487^e123) - (3.73151^e124) - (3.58751^e125) + (19.59692^e134) + (19.66164^e135) - (1.11453^e145) - (17.80093^e234) - (17.92424^e235) + (1.09998^e245) - (0.46003^e345),rgb(255, 0, 0));
DrawCircle((2.78464^e123) - (1.711^e124) - (1.58028^e125) + (21.67211^e134) + (21.73749^e135) - (1.05756^e145) - (14.89893^e234) - (15.03592^e235) + (0.78359^e245) - (0.71632^e345),rgb(255, 0, 0));
DrawCircle((2.72945^e123) - (7.71058^e124) - (7.58301^e125) + (21.04915^e134) + (21.14323^e135) - (1.24955^e145) - (14.68271^e234) - (14.8052^e235) + (1.03226^e245) - (0.43854^e345),rgb(255, 0, 0));
DrawCircle((2.52118^e123) - (5.44878^e124) - (5.31848^e125) + (20.36066^e134) + (20.44316^e135) - (1.23051^e145) - (10.60886^e234) - (10.73672^e235) + (0.82458^e245) - (0.68542^e345),rgb(255, 0, 0));
DrawCircle((2.85382^e123) - (5.32097^e124) - (5.19396^e125) + (22.13045^e134) + (22.19841^e135) - (1.11166^e145) - (16.97438^e234) - (17.11359^e235) + (1.01502^e245) - (0.67525^e345),rgb(255, 0, 0));
DrawCircle((2.73914^e123) - (3.31821^e124) - (3.19096^e125) + (19.98116^e134) + (20.03049^e135) - (0.98801^e145) - (16.5921^e234) - (16.73874^e235) + (0.94845^e245) - (0.7709^e345),rgb(255, 0, 0));
DrawCircle((2.79354^e123) - (4.83608^e124) - (4.71675^e125) + (22.91682^e134) + (23.0015^e135) - (1.12552^e145) - (13.18445^e234) - (13.32127^e235) + (0.80005^e245) - (0.72276^e345),rgb(255, 0, 0));
DrawCircle((0.41223^e123) - (6.14652^e124) - (6.17514^e125) - (9.54321^e134) - (9.52424^e135) - (0.94545^e145) + (2.02091^e234) + (1.99957^e235) + (0.45842^e245) + (0.4009^e345),rgb(0,0,0));
DrawCircle((0.49621^e123) + (2.31848^e124) + (2.30375^e125) - (3.36862^e134) - (3.44511^e135) - (0.45742^e145) + (4.06801^e234) + (4.1134^e235) + (0.33289^e245) + (0.31892^e345),rgb(0,0,0));
DrawCircle((2.78234^e123) - (3.88711^e124) - (3.75112^e125) + (22.0066^e134) + (22.07247^e135) - (1.1676^e145) - (14.61176^e234) - (14.75164^e235) + (0.90958^e245) - (0.76049^e345),rgb(0,0,0));