Tooth Segmentation Algorithms

Growth Model-Based Clustering

I am still implementing this idea, but roughly speaking it is a top-down method for growing a flat surface under the tooth crown upward with signaling centers similar to how real teeth grow, segmenting the surface each time a new stage of growth is entered. This segmentation method is in the same spirit as medial axis-based segmentation, except this method may be less prone to problems with noisy data. This method is also much more appropriate for segmentation of biological shapes than standard clustering methods since it attempts to segment by modeling the actual history of the formation of the shape.

Standard k-means Clustering

Below are pictures of segmentations performed on teeth using Lloyd's algorithm for k-means clustering. The algorithm works roughly as follows.

LLOYD (k, N)
1. Randomly pick k initial centers
2. Cluster all faces into the corresponding k clusters
3. Repeat N times:
3.1 Compute centroid of each of the k clusters
3.2 Compute corresponding clusters using new centers

Figure 1. Segmentation of a tooth into k = 10 segments using Lloyd's algorithm for k-means clustering with N = 1 extra iteration.

Figure 2. Segmentation of a tooth into k = 10 segments using Lloyd's algorithm for k-means clustering with N = 4 extra iterations.

Top-Down Fuzzy Clustering

The paper Hierarchical Mesh Decomposition using Fuzzy Clustering and Cuts by Katz and Tal describes a top-down segmentation algorithm for triangle meshes. The algorithm takes as input a triangle mesh and a positive integer k which is the number of segments into which the mesh will be decomposed. Essentially the algorithm works by choosing a set of k faces, each serving as a "representative" face for a segment. Then for each non-representative face of the mesh, we compute its probabilities of belonging to each of the k segments based on its distance to each of the k representative faces. The first representative is the face with the minimum sum of distances to all other faces of the mesh. The remaining k - 1 representatives are chosen by repeatedly choosing the face with the maximum distances from all previously assigned representatives. Katz and Tal also include a fuzzy boundary computation step: for any face that does not have a high enough probability of belonging to any one segment, they label the face as a boundary face and will assign all boundary faces to segments so that boundaries are smooth. In my implementation, I ignored this fuzzy boundary step and simply assigned each face to a segment in which it has the highest probability of belonging. As a result the boundaries in my implementation are less smooth than in the actual algorithm. Figure 3 below shows the result of running my implementation of this algorithm on a tooh with k = 20. Figure 4 shows the result of running the same algorithm on the same tooth with k = 10.

Distances are measured in two different ways which I compare below: (1) by running Dijkstra's algorithm over the dual graph of the mesh and (2) by simply computing the Euclidean distance between the centroids of triangles. Unfortunately, since the set of pairwise distances between faces is too large to store in memory for large meshes such as the tooth below, the algorithm typically takes a few days to complete if I am using distance measurement (1) and several minutes if for (2), since the pairwise distances must be recomputed each time we pick the next representative, and Dijkstra's algorithm is considerably slow for large sets.

Figure 3. Top-down decomposition of a tooth into k = 20 segments using the probability-based mesh segmentation algorithm of Katz and Tal. I did not implement the fuzzy boundary computation step, so the segment boundaries are not very smooth. Distances are computed using the Euclidean distance between triangle centroids.

Figure 4. Top-down decomposition of a tooth into k = 20 segments using the probability-based mesh segmentation algorithm of Katz and Tal. I did not implement the fuzzy boundary computation step, so the segment boundaries are not very smooth. Distances are computed using the Euclidean distance between triangle centroids.

Figure 5. Top-down decomposition of a tooth into k = 20 segments using the probability-based mesh segmentation algorithm of Katz and Tal. I did not implement the fuzzy boundary computation step, so the segment boundaries are not very smooth. Distances are computed using the dual graph of the mesh.

Figure 6. Top-down decomposition of a tooth into k = 10 segments using the probability-based mesh segmentation algorithm of Katz and Tal. I did not implement the fuzzy boundary computation step, so the segment boundaries are not very smooth. Distances are computed using the Euclidean distance between triangle centroids.

Figure 7. Top-down decomposition of a tooth into k = 10 segments using the probability-based mesh segmentation algorithm of Katz and Tal. I did not implement the fuzzy boundary computation step, so the segment boundaries are not very smooth. Distances are computed using the Euclidean distance between triangle centroids.

Figure 8. Top-down decomposition of a tooth into k = 10 segments using the probability-based mesh segmentation algorithm of Katz and Tal. I did not implement the fuzzy boundary computation step, so the segment boundaries are not very smooth. Distances are computed using the dual graph of the mesh.

Fast Marching Watersheds

Figure 9 below shows the result of my partial implementation of the fast marching watersheds algorithm of Page, Koschan and Abidi. The algorithm is described in the paper Perception-based 3D Triangle Mesh Segmentaton Using Fast Marching Watersheds. The algorithm consists of four steps:

  1. Compute principal curvatures and directions at each vertex of the mesh.
  2. Threshold the regions of positive curvature to get an initial marker set of vertices.
  3. Apply mathematical morphology to clean up the marker set.
  4. Grow each "catchment basin" in the marker set so that every vertex is assigned to some segment. This yields the final segmentation.

Figure 9. Initial catchment basins on a tooth using curvature information as in the fast marching watersheds algorithm of Page, Koschan and Abidi.

Bottom-Up Hierarchical Face Clustering

The paper Hierarchical Face Clustering on Polygonal Surfaces by Garland, Willmott and Heckbert describes a bottom-up algorithm for triangle mesh segmentation. The algorithm works by assigning a "score" to each pair of adjacent triangles in the mesh. The list of scores is sorted. Initially each triangle is in its own cluster. Then in order of the list of sorted scores, we merge the clusters of the two triangles with the highest (or lowest) score, assuming they are not already in the same segment. We can stop the algorithm somewhere in between to get a segmentation of desired coarseness or fineness. If the algorithm merges every pair of triangles, then of course the entire mesh will be in one cluster. In the paper, the authors use a quadric metric to compute the score of each pair of triangles. However I used a simpler measure based on the dot product of the oriented vectors of each pair of triangles. Figure 10 shows the result of my implementation. It appears that the small fluctuations on the tooth surface prevented sufficiently large segments from growing, since my score measures "flatness" of each pair of triangles and merges the triangle clusters starting with the flattest pair.

Figure 10. Decomposition of a tooth by pairwise merging similar to the hierarchical face clustering algorithm of Garland, Willmott and Heckbert. Each pair of triangles is assigned a score based on the dot product of their oriented normal vectors, unlike the quadric metric-based score in the original algorithm.