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.57004^e123) - (4.34196^e124) - (4.27753^e125) - (2.55641^e134) - (2.59331^e135) + (0.57003^e145) - (1.66057^e234) - (1.76083^e235) + (0.95143^e245) + (0.34217^e345),rgb(255,0,0));
DrawCircle((0.70078^e123) - (6.30794^e124) - (6.24542^e125) - (3.87086^e134) - (3.92031^e135) + (0.79044^e145) - (0.8129^e234) - (0.90888^e235) + (0.9365^e245) + (0.47282^e345),rgb(255,0,0));
DrawCircle((0.50483^e123) - (5.05384^e124) - (4.99381^e125) - (1.74312^e134) - (1.77813^e135) + (0.55774^e145) - (0.50423^e234) - (0.60786^e235) + (1.09734^e245) + (0.32284^e345),rgb(255,0,0));
DrawCircle((0.42812^e123) - (3.16653^e124) - (3.0968^e125) - (1.13172^e134) - (1.16828^e135) + (0.45471^e145) - (1.68584^e234) - (1.78263^e235) + (0.99045^e245) + (0.11191^e345),rgb(255,0,0));
DrawCircle((0.52552^e123) - (5.60347^e124) - (5.55525^e125) - (1.82622^e134) - (1.87484^e135) + (0.68597^e145) + (0.64336^e234) + (0.53906^e235) + (1.05307^e245) + (0.42196^e345),rgb(255,0,0));
DrawCircle((0.73537^e123) - (5.05099^e124) - (4.97079^e125) - (3.46046^e134) - (3.4552^e135) + (0.34121^e145) - (4.16418^e234) - (4.25961^e235) + (1.10963^e245) + (0.4789^e345),rgb(255,0,0));
DrawCircle((0.57765^e123) - (4.13484^e124) - (4.06699^e125) - (1.7403^e134) - (1.73459^e135) + (0.16351^e145) - (2.81923^e234) - (2.92378^e235) + (1.0795^e245) + (0.34286^e345),rgb(255,0,0));
DrawCircle((0.54556^e123) - (3.3875^e124) - (3.33096^e125) - (2.08372^e134) - (2.11593^e135) + (0.41593^e145) - (2.26197^e234) - (2.36843^e235) + (0.89542^e245) + (0.27306^e345),rgb(255,0,0));
DrawCircle((0.73271^e123) - (4.35859^e124) - (4.29698^e125) - (3.87918^e134) - (3.91956^e135) + (0.56639^e145) - (2.86809^e234) - (2.96879^e235) + (0.84017^e245) + (0.37506^e345),rgb(255,0,0));
DrawCircle((0.17341^e123) - (3.7413^e124) - (3.67932^e125) + (0.25617^e134) + (0.21763^e135) + (0.73996^e145) + (2.92854^e234) + (2.82735^e235) + (1.13656^e245) + (0.50139^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.43834^e123) + (4.91661^e124) + (4.92227^e125) - (8.54165^e134) - (8.42973^e135) - (1.36554^e145) + (6.89423^e234) + (6.86465^e235) + (0.42085^e245) + (1.18366^e345),rgb(255,0,0));
DrawCircle(-(0.45464^e123) + (4.83996^e124) + (4.83924^e125) - (6.65549^e134) - (6.54523^e135) - (1.16328^e145) + (7.55912^e234) + (7.52344^e235) + (0.3678^e245) + (1.31106^e345),rgb(255,0,0));
DrawCircle(-(0.60895^e123) + (6.20919^e124) + (6.22775^e125) - (6.79321^e134) - (6.68431^e135) - (1.31744^e145) + (7.96816^e234) + (7.93312^e235) + (0.60021^e245) + (1.03398^e345),rgb(255,0,0));
DrawCircle(-(0.63044^e123) + (7.04459^e124) + (7.04962^e125) - (6.80967^e134) - (6.69787^e135) - (1.30355^e145) + (8.73754^e234) + (8.7074^e235) + (0.40647^e245) + (1.22391^e345),rgb(255,0,0));
DrawCircle(-(0.47238^e123) + (5.73279^e124) + (5.73762^e125) - (8.71357^e134) - (8.60415^e135) - (1.41698^e145) + (8.07236^e234) + (8.03447^e235) + (0.54235^e245) + (1.1709^e345),rgb(255,0,0));
DrawCircle((0.39854^e123) + (8.12318^e124) + (8.07525^e125) - (4.32942^e134) - (4.24051^e135) + (1.29144^e145) + (9.50218^e234) + (9.44228^e235) - (0.07809^e245) - (1.46905^e345),rgb(255,0,0));
DrawCircle((0.35269^e123) + (7.61977^e124) + (7.57015^e125) - (4.87468^e134) - (4.78564^e135) + (1.23805^e145) + (9.15859^e234) + (9.10029^e235) + (0.02866^e245) - (1.50641^e345),rgb(255,0,0));
DrawCircle((0.3891^e123) + (8.88695^e124) + (8.83833^e125) - (6.8917^e134) - (6.79348^e135) + (1.38219^e145) + (8.79358^e234) + (8.7514^e235) + (0.13535^e245) - (1.47263^e345),rgb(255,0,0));
DrawCircle((0.3761^e123) + (7.34812^e124) + (7.30065^e125) - (4.14028^e134) - (4.05147^e135) + (1.2126^e145) + (9.07748^e234) + (9.01707^e235) - (0.03465^e245) - (1.47846^e345),rgb(255,0,0));
DrawCircle((0.40334^e123) + (7.55764^e124) + (7.51045^e125) - (3.89137^e134) - (3.80233^e135) + (1.21309^e145) + (9.37243^e234) + (9.31214^e235) - (0.03282^e245) - (1.48749^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
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-7-628c8ee6f811> in <module>
----> 1 from clifford.tools.g3c.object_clustering import n_clusters_objects
      2 import time
      3
      4 def run_n_clusters( object_generator, n_clusters, n_objects_per_cluster, n_shotgunning):
      5     all_objects, object_clusters = generate_n_clusters( object_generator, n_clusters, n_objects_per_cluster )

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _find_and_load(name, import_)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _find_and_load_unlocked(name, import_)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _load_unlocked(spec)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _load_backward_compatible(spec)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/site-packages/clifford-1.0.1-py3.6.egg/clifford/tools/g3c/object_clustering.py in <module>
      9 from .GAOnline import GAScene
     10
---> 11 from .cuda import object_set_cost_cuda_mvs
     12
     13

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _find_and_load(name, import_)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _find_and_load_unlocked(name, import_)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _load_unlocked(spec)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _load_backward_compatible(spec)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/site-packages/clifford-1.0.1-py3.6.egg/clifford/tools/g3c/cuda.py in <module>
      1
----> 2 from .cuda_products import gmt_func as gp_device
      3 from .cuda_products import imt_func as ip_device
      4 import numpy as np
      5 import numba.cuda

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _find_and_load(name, import_)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _find_and_load_unlocked(name, import_)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _load_unlocked(spec)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _load_backward_compatible(spec)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/site-packages/clifford-1.0.1-py3.6.egg/clifford/tools/g3c/cuda_products.py in <module>
      3
      4
----> 5 @numba.cuda.jit(device=True)
      6 def gmt_func_o0(value, other_value):
      7     return 0 + 1.0*value[0]*other_value[0] + 1.0*value[3]*other_value[3] + 1.0*value[4]*other_value[4] + -1.0*value[5]*other_value[5] + -1.0*value[6]*other_value[6] + -1.0*value[7]*other_value[7] + -1.0*value[8]*other_value[8] + 1.0*value[9]*other_value[9] + -1.0*value[10]*other_value[10] + -1.0*value[11]*other_value[11] + 1.0*value[12]*other_value[12] + -1.0*value[13]*other_value[13] + 1.0*value[14]*other_value[14] + 1.0*value[15]*other_value[15] + 1.0*value[2]*other_value[2] + -1.0*value[16]*other_value[16] + 1.0*value[18]*other_value[18] + -1.0*value[19]*other_value[19] + 1.0*value[20]*other_value[20] + 1.0*value[21]*other_value[21] + -1.0*value[22]*other_value[22] + 1.0*value[23]*other_value[23] + 1.0*value[24]*other_value[24] + 1.0*value[25]*other_value[25] + 1.0*value[26]*other_value[26] + -1.0*value[27]*other_value[27] + -1.0*value[28]*other_value[28] + -1.0*value[29]*other_value[29] + -1.0*value[30]*other_value[30] + -1.0*value[17]*other_value[17] + 1.0*value[1]*other_value[1] + -1.0*value[31]*other_value[31]

AttributeError: module 'numba' has no attribute 'cuda'

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)
---------------------------------------------------------------------------
AttributeError                            Traceback (most recent call last)
<ipython-input-8-8a46a49cfb84> in <module>
----> 1 from clifford.tools.g3c.object_clustering import visualise_n_clusters
      2
      3 object_generator = random_circle
      4
      5 n_clusters = 3

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _find_and_load(name, import_)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _find_and_load_unlocked(name, import_)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _load_unlocked(spec)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _load_backward_compatible(spec)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/site-packages/clifford-1.0.1-py3.6.egg/clifford/tools/g3c/object_clustering.py in <module>
      9 from .GAOnline import GAScene
     10
---> 11 from .cuda import object_set_cost_cuda_mvs
     12
     13

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _find_and_load(name, import_)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _find_and_load_unlocked(name, import_)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _load_unlocked(spec)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _load_backward_compatible(spec)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/site-packages/clifford-1.0.1-py3.6.egg/clifford/tools/g3c/cuda.py in <module>
      1
----> 2 from .cuda_products import gmt_func as gp_device
      3 from .cuda_products import imt_func as ip_device
      4 import numpy as np
      5 import numba.cuda

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _find_and_load(name, import_)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _find_and_load_unlocked(name, import_)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _load_unlocked(spec)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/importlib/_bootstrap.py in _load_backward_compatible(spec)

~/checkouts/readthedocs.org/user_builds/clifford/conda/latest/lib/python3.6/site-packages/clifford-1.0.1-py3.6.egg/clifford/tools/g3c/cuda_products.py in <module>
      3
      4
----> 5 @numba.cuda.jit(device=True)
      6 def gmt_func_o0(value, other_value):
      7     return 0 + 1.0*value[0]*other_value[0] + 1.0*value[3]*other_value[3] + 1.0*value[4]*other_value[4] + -1.0*value[5]*other_value[5] + -1.0*value[6]*other_value[6] + -1.0*value[7]*other_value[7] + -1.0*value[8]*other_value[8] + 1.0*value[9]*other_value[9] + -1.0*value[10]*other_value[10] + -1.0*value[11]*other_value[11] + 1.0*value[12]*other_value[12] + -1.0*value[13]*other_value[13] + 1.0*value[14]*other_value[14] + 1.0*value[15]*other_value[15] + 1.0*value[2]*other_value[2] + -1.0*value[16]*other_value[16] + 1.0*value[18]*other_value[18] + -1.0*value[19]*other_value[19] + 1.0*value[20]*other_value[20] + 1.0*value[21]*other_value[21] + -1.0*value[22]*other_value[22] + 1.0*value[23]*other_value[23] + 1.0*value[24]*other_value[24] + 1.0*value[25]*other_value[25] + 1.0*value[26]*other_value[26] + -1.0*value[27]*other_value[27] + -1.0*value[28]*other_value[28] + -1.0*value[29]*other_value[29] + -1.0*value[30]*other_value[30] + -1.0*value[17]*other_value[17] + 1.0*value[1]*other_value[1] + -1.0*value[31]*other_value[31]

AttributeError: module 'numba' has no attribute 'cuda'