Emerging Trends in Image Processing, Computer Vision, and Pattern Recognition, 1st Edition (2015)
Part II. Computer Vision and Recognition Systems
Chapter 28. Semi-automatic teeth segmentation in 3D models of dental casts using a hybrid methodology
J.D. Tamayo-Quintero1; S. Arboleda-Duque1,2; J.B. Gómez-Mendoza1 1 Department of Electric, Electronic and Computer Engineering, Universidad Nacional de Colombia, Manizales, Caldas, Colombia
2 Department of Telecommunications Engineering, Universidad Católica de Manizales, Manizales, Caldas, Colombia
Abstract
This document is an extension of the chapter “Image Segmentation Techniques Applied to Point Clouds of Dental Models with an Improvement in Semi-Automatic Teeth Segmentation,” presented in the International Conference on Image Processing and Computer Vision IPCV 2014. The work arises from an exploratory study on the application of a combination of different segmentation techniques to point clouds of dental models. Results from a previous work—where the subject of study are point clouds representing urban landscapes—suggested that hybridization of current methods for point cloud segmentation perform better if compared to the methods themselves. Base techniques used in this work comprise geometric primitive model approximation (e.g., RANSAC), Region Growing segmentation, and a graph theory-based approach (particularly the “Min-Cut” algorithm). In our application, the techniques were tested using dental 3D point clouds. Data were acquired using a Konica Minolta VIVID 9i laser range scanner.
Also, a semi-automatic segmentation methodology is presented. Results of teeth segmentation using testing data suggest that it is possible to automatically segment teeth from digital 3D models.
Keywords
Point cloud
3D dental models
Segmentation
Region Growing
Min-Cut
Acknowledgments
This work was made possible thanks to the support of the Universidad Nacional de Colombia Sede Manizales, and in particular the research groups on Perception and Intelligent Control (PCI) and Soft and Hard Applied Computing (SHAC).
1 Introduction
The advent of new technologies has driven the development of increasingly sophisticated 3D acquisition systems [1]. 3D models originated by using those systems, also referred as point clouds, provide surface information, metrics, texture, etc. This 3D information is of great interest in different fields in the industry, such as in-process inspection, accident reconstruction, crime scene analysis, machine calibration, orthodontics, etc. [2].
Digital dental models have proven to be helpful and important for experts in odontology and orthodontics. They provide information precise enough to be used in diagnosis and prognosis [3], this has caused a number of concerns to emerge using 3D dental models is becoming a more common practice in the field.
Colombian laws in consumer protection require dental cast records of patients to be preserved during a period no less than 10 years, and according to the Association of Orthodontists [4], it is recommended that study models are retained for at least 11 years or until the patient is 26 years old. This has caused a number of concerns to emerge, like limited storage capacity, model fragility, among others.
Therefore, it is important to use the 3D digital dental models in place of physical alginate casts. Aiming to further strengthen the acceptance of such practice, 3D image processing and digital measuring tools are finding their way into orthodontics.
Surface and object segmentation is an intermediate step in artificial vision that eases object recognition and classification. A good segmentation is a key to facilitate, enhance, and achieve further interpretation of the input data.
For that reason, in this work we present an exploratory analysis of current segmentation techniques for point clouds applied to dental 3D models. This is a first step toward parameter measurement [5,6], simulation of the movement of teeth to correct malocclusions [7], planning for dental and maxillofacial surgery [8], pose estimation [9], among others.
This chapter is organized as follows: Section 2 describes briefly the process of obtaining integrated 3D point clouds from plaster dental models. Section 3 introduces the segmentation techniques applied to 3D digital dental models. Section 3.4 shows the analysis and results of applying those segmentation techniques to point clouds of dental models. Finally, Section 3.5 presents the findings and discussion of the results of this work.
2 Dental Study Model
Experts in dental areas use diagnostic logs, which are kept in order to document the initial condition of the patient and complement the information gathered during clinical examination. These records are commonly divided in three categories: dental models, photographs, and radiographs [10].
Dental models in dentistry are built primarily using alginate cast. They are important for diagnosis and orthodontic treatment planning, as well as to detect anomalies of pose, size, and shape of the teeth. Also, they are indispensable to assess the outcomes of treatment process [11–13].
2.1 3D Model Acquisition
The Universidad Nacional de Colombia Sede Manizales has a 3D digitizer VIVID 9i Konica (Figure 1). This scanner produces range images which constitute a valuable source of information. Since range images cover the object’s geometry from a specific point of view, several shots are needed in order to reconstruct a whole model without occlusions.
FIGURE 1 Konica Minolta VIVID 9i 3D digitizer.
The views acquired with the range scanner must be aligned up into a single coordinate space. This procedure is called registration (e.g., in Figure 2).
FIGURE 2 Registration.
Once the views have been registered, the integration process starts. The goal of integration is to generate a well-defined mesh or data set using the information coming from all the views (partial meshes or point sets) captured during scanning (Figure 3). Furthermore, this process seeks to eliminate redundant information in regions with little variation in the surface, and to fill small holes in the surface.
FIGURE 3 Integration.
In this study five dental models were used. Eight views were captured in order to construct each model, with the scanner tilted at 45°, thus achieving good detail within the object of interest. This process was conducted by the research group in Perception and Intelligent Control (PCI). For further details please refer to the Master’s final technical report [14].
3 Point cloud segmentation
In this section, a brief introduction on three different techniques for segmenting point clouds is given: RANdom SAmpling and Consensus (RANSAC) [15], Region Growing [16], and Maximum-Flow Minimum-Cut (Min-Cut) [17].
3.1 RANSAC
The iterative method of RANSAC was proposed by Fischer and Bolles. The technique aims to estimate the parameters of a mathematical model from a set of observed data using a method of hypothesis testing. The algorithm is used as a geometric model-based segmentation algorithm, due to its ability to automatically recognize parameterized shapes through the data.
The principle of the algorithm is as follows. If ε is the probability of choosing a sample that produces a poor estimate (outlier), then 1 - ε is the probability of getting a good sample (inliers). This means that the probability of catching s good samples becomes (1 - ε)s. For k trials, the probability of failure becomes (1 - (1 - ε)s)k. If ρ is the desired probability of success, given for Equation (1):
(1)
3.2 Region Growing Segmentation
The Region Growing algorithm is based on the idea that some features in local data do not change greatly regarding those features measured for a given sample, called seed. Therefore, regions can be “grown” if neighboring data remain homogeneous given certain constraints, commonly the spatial closeness of the data, although other features can also be included. In our work, we choose to enrich the spatial closeness with features that are based in local surface orientation and curvature, both approximated at each point in the cloud. The algorithm can be summarized as follows:
• Points are sorted according to their curvature.
• The point that has the minimum value of curvature is chosen as a seed and the region growth begins from that point (flat areas have less curvature).
• For each seed point, a list containing its closest neighbors is extracted:
• The angle between the normal of each neighbor and the normal of the current point (seed) is compared: if the angle is less than a certain threshold, the point is added to the current region.
• Subsequently, every neighbor is tested for the curvature value. If the neighbor’s curvature is less than certain curvature threshold value then that point is turned into a new seed.
• Current seeds are removed from the set of seeds, but remain marked as points belonging to the region. This avoids double checking points.
Regions are found once the algorithm runs out of seeds. For further details regarding Region Growing please refer to [16].
3.3 Min-Cut
According to the results of Golovinskiy and Funkhouser [17], Min-Cut is robust to noise and is very effective for segmenting dense point clouds of outdoor urban scans. However, it requires prior knowledge of the location of the objects to be segmented, and has input parameter (namely radius and σ) that should be set in order to control the resulting segmentation, where the main cues are distances and point densities, rather than colors and textures.
The principle of the algorithm is as follows:
First of all, the structure of the point cloud as a flow graph through the K closest neighbors, which are joined together using links with different weights. Additionally, points are joined to a source and a sink, used to represent the object and the background.
The first weight is given to all edges of the point cloud and is called SmoothCost (SC), computed using Equation (2):
(2)
where dist is the distance between the points and σ is a free input parameter that allows modifying the smoothing effect.
The next step of the algorithm is to establish the cost of the data. In this case it is necessary to make use of the source (t) and sink (s), where the source is related to the central point of the object to segment (given manually) and sink with any point belonging to background, where the following penalty calculated by Equation (3).
(3)
where distocenter is the expected distance to the center of the object in a horizontal plane, and is computed as in Equation (4):
(4)
Radius is an input parameter and can be considered as the range from the center of the object where the points belong to a region of interest by assigning a higher weight. On the other hand, z axis is not considered in Equation (4). Such constraint can be interpreted geometrically as an infinite length cylinder with radius given by radius, whose length is aligned parallel to the z axis.
Once the graph is constructed, the segmentation is given by the minimum cut where the region of interest is extracted.
3.4 Feature Sampling Using NARF
Semi-automated 3D point cloud segmentation results are highly dependent upon parameter set-up. Whenever possible, it is the user’s responsibility to provide proper values for such parameter set as part of the algorithm’s prior. In some algorithms, those parameters are points which are representative for the regions contained in the point set, and selecting them can be a demanding task.
In order to overcome such limitation, an automatic or semi-automatic point selection technique can be applied.
Normal-aligned radial features (NARF), presented by Steder et al. [18], aim to cope with the necessity of generating a structured subsampling of the data, taking into account elements such as spatial density (including empty areas) and robustness to noise.
According to the authors, in order to obtain NARF descriptors one must:
• calculate a normal aligned range value patch in the point, which is a small range image with the observer looking at the point along the normal,
• overlay a star pattern onto this patch, where each beam corresponds to a value in the final descriptor, that captures how much the pixels under the beam change,
• extract a unique orientation from the descriptor,
• and shift the descriptor according to this value to make it invariant to the rotation.
Resulting points are not overcrowded in high variation areas, but retain a well-defined representation of the information contained in the original cloud. Additionally, each feature vector contains the mean orientation of the local patch that it represents.
3.5 The Hybrid Technique
This method implemented is a contribution for semi-automatic segmentation of point cloud based in Min-Cut, NARF, and Region Growing.
Min-Cut is an efficient and powerful technique for point cloud segmentation; however, this method has a number of disadvantages as it is the prior knowledge of the center of object to be segmented and the radius value. Due to these drawbacks, we propose a method to achieve a semi-automatic segmentation without prior knowledge of the location of the objects, supplying part of that information by the means of NARF.
On the other hand, Region Growing segmentation based in local surface orientation and curvature is an efficient technique for segmenting point clouds of dental models, effectively separating the gum and teeth.
In our first work, a hybrid technique was constructed using NARF and Min-Cut, aimed to segment outdoor environments [19]. Figures 4 and 5 show some of the results obtained in that work. The streamline of the technique can be summarized as shown below:
FIGURE 4 This is an example segmentation in outdoor environment using the first work with the hybrid technique (for easier visualization background is subsample).
FIGURE 5 Some important objects are obtained by the hybrid technique. Tree (a), tall post (b), road sign (c).
• Two input parameters are set up prior to execution: support size and angular resolution.
• Then, we use NARF as a descriptor to obtain the target landmarks;
• The final step is to segment the cloud using each landmark as a seed in the Min-Cut algorithm.
In this work, the hybrid technique is based in NARF, Min-Cut, and Region Growing [20]. The methodology can be summarized as shown below:
• First of all, the gum is separated from teeth using the Region Growing method.
• Once gum is set apart, a set of landmarks is extracted using the NARF technique in the segmented teeth region.
• Subsequently, each landmark is used as a source in the Min-Cut method.
The final segmentation is composed of the gum and a set of tooth regions. Notice that, unlike the case of outdoor scene segmentation, there is no need to preestablish angular resolution and support size. This is because overall teeth geometry does not vary greatly from one model to another.
4 Results of segmentation techniques applied to 3D dental models
Exploration results obtained by applying different segmentation techniques described in Section 3 are shown in this section. Five 3D dental models were used in this analysis (Figure 10). Each cloud has approximately 50,000 points.
The tests were performed on all models; some important conclusions drawn from this analysis are mentioned. Finally, a semi-automatic segmentation methodology for 3D dental models is presented.
4.1 First, a Test Using RANSAC
As mentioned in Section 3.1, RANSAC allows automatic recognition of known forms of the data (planes, cylinders, spheres, and tori). In this case a planar model was used, with a threshold of ± 5 mm, as shown in Figure 6(a). The result obtained applying this technique is shown in Figure 6(b). The points retain colors red (dark gray in the print version) and blue (light gray in the print version) according to the region they have been assigned to. Notice that the plane in Figure 6(a) serves only as a mere illustration of the principle used by the technique, and do not correspond to the one used to obtain the classification in Figure 6(b).
FIGURE 6 (a) Planar segmentation by RANSAC with a threshold of ± 5 mm and (b) dental model segmented.
This method finds the highest concentration of points in a planar model based in a planar hypothesis. In this case the highest concentration of points is found on the teeth’s surface.
4.2 Gum Extraction Using Region Growing
The results obtained by applying the algorithm of region growing are shown in Figure 7. The stop criteria are given comparing the points normal and then the curvature of the points. The input parameters are shown in Table 1.
FIGURE 7 (a) Example of curvature in point clouds of dental models, (b) 3D dental model segmented using a Region Growing segmentation.
Table 1
Input Parameters for Region Growing Segmentation
In order to improve understanding and visualization, the point cloud of dental model is drawn with colors representing their curvature Figure 7(a) and the result obtained applying the Region Growing segmentation technique in a 3D dental model is illustrated in Figure 7(b).
For further information regarding neighbor search process and Kd-trees please refer to PCL, API Documentation [21] or the Flann library documentation [22].
Figure 7(b) shows some points colored in aqua blue (light gray in the print version), which are not targeted because of their high curvature or because the region generated by the region growing process do not contain enough data points to be considered as such.
Clearly this method requires some refinement that would allow merging some regions. However, this is an acceptable approximation which can be used instead of usable as start point for further refinement.
4.3 Per-Tooth Separation Using Min-Cut
As mentioned in Section 3.3, this algorithm requires human interaction to introduce the virtual node called source (t) to segment an object of interest. We can see a clear example in Figure 8.
FIGURE 8 Segmentation applying the Min-Cut. (a) Selection of the interest point. (b) Segmentation of the selected tooth.
Min-Cut requires human interaction in order to set some important parameters such as the radius. For this reason, we designed a variant of the methodology used by Tamayo-Quintero and Gómez-Mendoza [19] to search the virtual nodes automatically—landmarks—i.e., a point in the centers of each object—in the ideal case—in this case each tooth, by means of NARF. The input parameters are shown in Table 2.
Table 2
Input Parameters for Min-Cut Segmentation
4.4 Semi-Automatic Segmentation (Hybrid Technique)
The results obtained by applying the hybrid technique are shown in Figures 9 and 10. The stop criteria are mentioned in the previous techniques and the input parameter are shown in Table 3.
FIGURE 9 Semi-automatic segmentation proposal.
Table 3
Input Parameters Used in the Proposed Methodology
In Figure 9, we designed a variant and this methodology is based in the hybridization of three algorithms: Region Growing, NARF, and Min-Cut. The first step is separated the gum from teeth using the region growing method then apply NARF and subsequently, each landmark is used as source in order to apply the Min-Cut. Finally, the segmentation is composed of the gum and a set of teeth. The methodology is illustrated in Figure 9, and the results obtained are shown in Figure 10.
FIGURE 10 Results obtained by applying different segmentation techniques to five dental models.
5 Comments and Discussions
Figure 10 shows the result of applying segmentation methods to five dental casts. The first column contains the point cloud of dental models one to five. The second column shows the segmentation using RANSAC algorithm. There is a noticeable difference in the results for model three in comparison to the other four, mainly due to teeth unevenness.
The third column presents the result of the Region Growing segmentation, where restrictions of smoothness given by the curvature and the angle between the normal are used.
The fourth column corresponds to Min-Cut-based segmentation, which separates the tooth but requiring human interaction in selecting a landmark for each tooth. As a consequence of this, the fifth column shows a methodology where landmarks are automatically selected through NARF, and then segmented using Min-Cut. Finally, the sixth column shows the Ground truth, built manually using Mesh Lab.
Results of teeth segmentation using the proposed methodology seem appropriate in appearance; however, they must be subject to analysis carried by experts in order to qualify them.
6 Conclusion
Dental casts contain rich information in terms of curvature and geometry, comprising semi-flat zones, highly curved zones, objects of interest with variable sizes, etc. As it happened with urban structures in our previous work [19], this data set posed an interesting segmentation problem that proved to be tackled in a more comprehensive manner through the means of a mixed methodology, composed by various well-known techniques that can be further tuned to recognize or separate a particular structure.
From this work, some achievements can be highlighted:
• Segmentation of the gum and teeth can be carried out adequately using the Region Growing algorithm based on the curvature and the angle between the normal vectors.
• The potential for Min-Cut algorithm for segmenting each tooth is evidenced.
• It is possible to apply the proposed methodology using NARF and Min-Cut, obtaining acceptable results for segmentation while reducing human interaction in setting internal parameters of the Min-Cut algorithm (landmark selection).
• Automatic radii selection for Min-Cut remains an open issue.
References
[1] Rusu RB, Cousins S. 3D is here: point cloud library (PCL). In: 2011 IEEE International Conference on Robotics and Automation; 2011:1–4. available at: http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5980567.
[2] FARO’s 3D metrology solutions, Measurement Industries, available at: http://www.faro.com/measurement-solutions.
[3] Motohashi N, Kuroda T. A 3D computer-aided design system applied to diagnosis and treatment planning in orthodontics and orthognathic surgery. Eur J Orthod. 1999. ;21:263–274. available at: http://ejo.oxfordjournals.org/content/21/3/263.full.pdf.
[4] Bell A, Ayoub AF, Siebert P. Assessment of the accuracy of a three-dimensional imaging system for archiving dental study models. J Orthod. 2003. ;30(3):219–223. available at: http://www.ncbi.nlm.nih.gov/pubmed/14530419.
[5] Laurendeau D, Guimond L, Poussart D. A computer-vision technique for the acquisition and processing of 3-D profiles of dental imprints: an application in orthodontics. IEEE Trans Med Imaging. 1991. ;10(3):453–461. available at:http://www.ncbi.nlm.nih.gov/pubmed/18222848.
[6] Mokhtari M, Laurendeau D. Feature detection on 3-D images. In: 1994:287–296. available at: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=315842.
[7] Chuah JH, Ong SH, Kondo T, Foong KWC, Yong TF. 3D space analysis of dental models, Visualization, Display, an Image-Guided Procedures. Proc SPIE. 2001. ;4319:564–573. 2, 26, available at: http://proceedings.spiedigitallibrary.org/proceeding.aspx?articleid=905781.
[8] Heo H, Chae O-S. Segmentation of tooth in ct images for the 3D reconstruction of teeth, Image Processing: Algorithms and Systems III. Proc SPIE-IS & T Electron Imaging. 2004. ;5298:455–466. 2, 13, available at:http://proceedings.spiedigitallibrary.org/proceeding.aspx?articleid=837263.
[9] Mok VW, Ong S, Foong KW, Kondo T. Pose estimation of teeth through crown-shape matching, Medical Imaging 2002: Image Processing. Proc SPIE. 2002. ;4684:955–964. available at: http://proceedings.spiedigitallibrary.org/proceeding.aspx?articleid=879917.
[10] Hou H-M, Wong R.W.-K., Hagg U. The uses of orthodontic study models in diagnosis and treatment planning. HKDJ. 2006;3(2):107–115 3, 14.
[11] Vellini-Ferreira F. Ortodoncia: diagnóstico y planificación clínica. 1st ed. Paulo, Brazil: Editora Artes Médicas Ltda; 2002 xvii, 3, 5, 6.
[12] Acosta W, Meneses F, Morzán A, Pastor E, Tomona N. Manual de procedimientos de laboratorio en ortodoncia. 1st ed. Lima, Perú: Universidad Peruana Cayetano Heredia; 1999.
[13] Rudge SJ. A computer program for the analysis of study models. Eur J Orthod. 1982;4:269–273.
[14] Morantes LJ. Caracterización de piezas dentales a partir de modelos 3D. Maestría tesis, Universidad Nacional de Colombia, Sede Manizales. 2008. available at: http://www.bdigital.unal.edu.co/3377/#sthash.4QRtCEp7.dpuf.
[15] Schnabel R, Wahl R, Klein R. Efficient RANSAC for point-cloud shape detection. Comput Graphics Forum. 2007;26(2):214–226 available at: http://doi.wiley.com/10.1111/j.1467–8659.2007.01016.x.
[16] Point cloud Library (PCL), documentation, tutorial, available at: http://pointclouds.org/documentation/tutorials/region_growing_segmentation.php.
[17] Golovinskiy A, Funkhouser T. Min-cut based segmentation of point clouds. In: 2009 IEEE 12th International Conference on Computer Vision Workshops ICCV Workshops, XXXIX-B3 (September); 2009:39–46. available at:http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5457721.
[18] Steder B, Rusu RB, Konolige K, Burgard W. Point feature extraction on 3D range scans taking into account object boundaries. In: 2011 IEEE International Conference on Robotics and Automation; 2011:2601–2608. available at:http://ieeexplore.ieee.org/lpdocs/epic03/wrapper.htm?arnumber=5980187.
[19] Tamayo-Quintero JD, Gómez-Mendoza JB. Semi-automatic 3D point cloud segmentation using a modified Min-Cut approach. In: 5th Latin American Conference on Networked and Electronic Media (LACNEM 2013); 2013. available at:http://revnoos.manizales.unal.edu.co/index.php/articulo/volumen-4-lacnem-2013.
[20] Tamayo-Quintero JD, Arboleda-Duque S, Gómez-Mendoza JB. Image segmentation techniques applied to point clouds of dental models with an improvement in semi-automatic teeth segmentation. In: IPCV'14—The 2014 International Conference on Image Processing, Computer Vision, and Pattern Recognition; 2014:23–25.
[21] Point Cloud Library (PCL), API documentation, available at: http://docs.pointclouds.org/trunk/.
[22] Fast Library for Approximate Nearest Neighbors (FLANN), available at: http://www.cs.ubc.ca/research/flann/.