Applied Science, Faculty of
Electrical and Computer Engineering, Department of
DSpace
UBCV
Yang, Rui
Master of Applied Science - MASc
University of British Columbia
Mandibular meshes segmented from computerized tomography (CT) images contain rich information of the dentition. Inconsistent dentition conditions in healthy mandible data sets can impair data-driven premorbid shape prediction for diseased mandibles. We developed a mesh segmentation method that includes a preprocessing algorithm using an off-the-shelf non-rigid registration, a surface mesh feature function, and an active contour model using geodesic distance. Constructive Solid Geometry (CSG) operations are employed to separate the dentition area from the mandibular mesh. An easy-to-use interactive tool was implemented, allowing users to adjust the contour position. We evaluated our method (preprocessing algorithm and user intervention) by comparing it with the traditional method of manual removal using 3D Slicer. The results indicated that our method helped save the manual processing time by 40%, which largely improves the efficiency. From a statistical-shape-modeling-based shape completion test, we drew the conclusion that edentulous mandibular data set could help make significantly better premorbid shape predictions (Z=-2.484,p=0.013) than data set with mixed dentition conditions. Besides tooth segmentation from 3D meshes, our research can assist virtual planning for bone graft placement in the defective mandible and implant placement in the bone graft. This work forms the underlying basis of a useful tool for coupling jaw reconstruction and restorative dentition for patient treatment planning.
Snake-Based Tool for SupportingInteractive Tooth Segmentation from3D Mandibular MeshesbyRui YangB.Sc., Tianjin University, 2017A THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinThe Faculty of Graduate and Postdoctoral Studies(Electrical and Computer Engineering)THE UNIVERSITY OF BRITISH COLUMBIA(Vancouver)August 2021c© Rui Yang 2021The following individuals certify that they have read, and recommend to the Faculty of Graduate and Postdoctoral Studies for acceptance, the thesis entitled: Snake-Based Tool for Supporting Interactive Tooth Segmentation from 3D Mandibular Meshes submitted by Rui Yang in partial fulfillment of the requirements for the degree of Master of Applied Science in Electrical and Computer Engineering Examining Committee: Sid Fels, Professor, Electrical and Computer Engineering, UBC Supervisor Purang Abolmaesumi, Professor, Electrical and Computer Engineering, UBC Supervisory Committee Member Antony Hodgson, Professor, Mechanical Engineering, UBC Supervisory Committee Member iiAbstractMandibular meshes segmented from computerized tomography (CT) imagescontain rich information of the dentition. Inconsistent dentition conditionsin healthy mandible data sets can impair data-driven premorbid shape pre-diction for diseased mandibles. We developed a mesh segmentation methodthat includes a preprocessing algorithm using an off-the-shelf non-rigid reg-istration, a surface mesh feature function, and an active contour model us-ing geodesic distance. Constructive Solid Geometry (CSG) operations areemployed to separate the dentition area from the mandibular mesh. Aneasy-to-use interactive tool was implemented, allowing users to adjust thecontour position.We evaluated our method (preprocessing algorithm and user interven-tion) by comparing it with the traditional method of manual removal using3D Slicer. The results indicated that our method helped save the man-ual processing time by 40%, which largely improves the efficiency. From astatistical-shape-modeling-based shape completion test, we drew the con-clusion that edentulous mandibular data set could help make significantlybetter premorbid shape predictions (Z=-2.484,p=0.013) than data set withmixed dentition conditions.Besides tooth segmentation from 3D meshes, our research can assistvirtual planning for bone graft placement in the defective mandible andimplant placement in the bone graft. This work forms the underlying basisof a useful tool for coupling jaw reconstruction and restorative dentition forpatient treatment planning.iiLay SummaryAs part of mandible model data processing, tooth segmentation from mandibu-lar CT scans or 3D meshes is common practice for clinical research. It is tra-ditionally done manually and can become time-consuming and error-prone.To facilitate this process, we implemented a tooth segmentation methodincluding a preprocessing step that computes the tooth crown contour forthe target model, and a user interface customized for contour editing onmandibular meshes. 40% of manual processing time was saved using ourmethod, which is promising to warrant further efforts towards clinical us-age.iiiPrefaceThis thesis was approved by UBC Clinical Research Ethics Board, certificatenumbers: H15-01663, H18-02268 and H21-01492. All chapters in this workhave been written by me and guided with input from my supervisor Dr.Sidney Fels. Dr. Antony Hodgson, Dr. Eitan Prisman and fellow colleagueAmir H. Abdi have also contributed with ideas during brainstorming meet-ings. I was the primary author and main contributor to the overall solutiondesign, and method evaluation. Dr. Eitan Prisman at the Vancouver Gen-eral Hospital provided patient data of mandibular Computed Tomography(CT) scans and meshes following the approval of the ethics committee.A version of Chapter 3 to Chapter 5 was submitted at SPIE MedicalImaging 2021.[1] Yang, Rui, Amir H. Abdi, Atabak Eghbal, Edward Wang, KhanhLinh Tran, David Yang, Antony Hodgson, Eitan Prisman, and Sidney Fels.”Snake-based interactive tooth segmentation for 3D mandibular meshes.”In Medical Imaging 2021: Image-Guided Procedures, Robotic Interventions,and Modeling, vol. 11598, p. 115981O. International Society for Optics andPhotonics, 2021.ivTable of ContentsAbstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiLay Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iiiPreface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ivTable of Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . vList of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . viiiList of Figures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xList of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . xviiiList of Abbreviations . . . . . . . . . . . . . . . . . . . . . . . . . xixAcknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . xxiDedication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xxii1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.2 Research Questions . . . . . . . . . . . . . . . . . . . . . . . 91.3 Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . 101.4 Structure of the Thesis . . . . . . . . . . . . . . . . . . . . . 112 Related work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.1 Mesh Segmentation . . . . . . . . . . . . . . . . . . . . . . . 132.2 Tooth-Oriented Mesh Segmentation . . . . . . . . . . . . . . 18v2.3 Image registration methods . . . . . . . . . . . . . . . . . . . 212.4 Snake: Active Contour Model . . . . . . . . . . . . . . . . . 232.5 Constructive Solid Geometry . . . . . . . . . . . . . . . . . . 262.6 Chapter Summary . . . . . . . . . . . . . . . . . . . . . . . . 273 Snake-Based Preprocessing Algorithm and User Interaction 283.1 Introduction of Tooth Crown Contour . . . . . . . . . . . . . 303.2 Preprocessing Algorithm . . . . . . . . . . . . . . . . . . . . 303.2.1 Data Acquisition and Template Creation . . . . . . . 313.2.2 Rigid and Non-Rigid Registration . . . . . . . . . . . 343.2.3 Contour Refinement Algorithm . . . . . . . . . . . . . 363.2.4 Computational Complexity . . . . . . . . . . . . . . . 523.2.5 Discussion . . . . . . . . . . . . . . . . . . . . . . . . 523.3 Interactive Tooth Removal . . . . . . . . . . . . . . . . . . . 543.3.1 User Interface for Contour Editing . . . . . . . . . . . 553.3.2 Dentition Area Removal . . . . . . . . . . . . . . . . 583.3.3 Discussion . . . . . . . . . . . . . . . . . . . . . . . . 594 Comparing Our Mesh-Based Method with A Voxel-BasedMethod using 3D Slicer . . . . . . . . . . . . . . . . . . . . . . 614.1 Hypothesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614.2 Input Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624.3 Experiment Setup . . . . . . . . . . . . . . . . . . . . . . . . 634.4 Pilot Studies and the Main Study . . . . . . . . . . . . . . . 654.5 Results and Data Analysis . . . . . . . . . . . . . . . . . . . 654.6 An Additional Study . . . . . . . . . . . . . . . . . . . . . . 704.7 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715 Edentulous Models for VSP . . . . . . . . . . . . . . . . . . . 745.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . 745.2 Hypothesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 755.3 Input Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . 755.4 Experimental Design and Measurement . . . . . . . . . . . . 765.5 Results and Data Analysis . . . . . . . . . . . . . . . . . . . 77vi5.6 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 846.1 Summary of Contributions . . . . . . . . . . . . . . . . . . . 846.2 Limitation and Future Work . . . . . . . . . . . . . . . . . . 856.3 Future Application . . . . . . . . . . . . . . . . . . . . . . . 896.3.1 Donor Site Placement Planning . . . . . . . . . . . . 896.3.2 Individual Tooth Identification . . . . . . . . . . . . . 916.4 Concluding Remarks . . . . . . . . . . . . . . . . . . . . . . 92Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93AppendicesA The Pseudo-Code of Jung and Kim’s Greedy Algorithm forEvolving Snakes . . . . . . . . . . . . . . . . . . . . . . . . . . . 109B User Interface Quick Reference Manual . . . . . . . . . . . . 110C The Results of the Study Comparing Our Method with AVoxel-Based Method . . . . . . . . . . . . . . . . . . . . . . . . 112D The Results of the Study Evaluating Using Edentulous Mod-els for VSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127viiList of Tables2.1 Frequently used mesh attributes for segmentation[44, 46–51] . 142.2 Mesh segmentation methodologies[47, 54–63] . . . . . . . . . 164.1 Distance comparison between the cut surfaces from 4 groups:P-M: the proposed mesh-based method and the voxel-basedmanual removal using 3D Slicer. P-A: the proposed mesh-based method and automatic segmentation (based on the con-tours generated by the preprocessing algorithm). M-A: thevoxel-based manual removal using 3D Slicer and automaticsegmentation. M-M: between two rounds of voxel-based man-ual removal in 3D Slicer for 10 models. . . . . . . . . . . . . . 695.1 Symmetric HD95 and DSC for all 7 classes of defects in theoriginal study (WT) . . . . . . . . . . . . . . . . . . . . . . . 775.2 Symmetric HD95 and DSC for all 7 classes of defects testedon 84 mandibles without teeth (NT) . . . . . . . . . . . . . . 785.3 Symmetric HD95 and DSC averaged across all 7 defects, testedon 84 mandibles without teeth (NT) and on the original 84mandibles in the study of Wang et al. (WT) . . . . . . . . . 81C.1 Manual processing time comparison (unit: s) . . . . . . . . . 112C.2 Compare the processing time running on a laptop with 4 coresto running on a desktop computer with 8 cores(unit: s) . . . 114viiiC.3 Distance comparison between the cut surfaces from three groups:P-M: the proposed mesh-based segmentation and a voxel-based manual removal using 3D Slicer. P-A: the proposedmesh-based segmentation and automatic segmentation. M-M: between two rounds of voxel-based manual removal for 10models. (Unit: mm) . . . . . . . . . . . . . . . . . . . . . . . 116C.4 Screenshots of the 48 mandible models before and after toothremoval using the proposed method (preprocessing algorithmand user intervention) and using 3D Slicer. . . . . . . . . . . 118D.1 The results of the statistical-shape-modeling-based shape com-pletion algorithm introduced in [2] (Symmetric 95th PercentileHausdorff Distance (HD95) and Volumetric Dice Score (DSC)).The algorithm is tested on all 7 classes of mandibular defects(I, Ic, II, IIc, III, IV, IVc) using the edentulous models ofthe mandible data set used in [2]. The results from the orig-inal study are shown in the last tow columns. The imagesof the original models are displayed in the first column. Thetypes of the original model (E: edentulous model. D: dentu-lous model or model with partial dentition) are shown in thesecond column. . . . . . . . . . . . . . . . . . . . . . . . . . . 127ixList of Figures1.1 Oral reconstruction[5]. The surgical plate is used to fixate thefibula bone grafts with screws. Dental implants are inserted inthe native bone and the bone grafts to allow dental restorations. 11.2 Examples of 3D mandibular meshes segmented from clinicalCT scans. (a) and (f): models from patients lacking certainteeth. (b): a model with obscure dentition area. (c): a modelwith the whole dentition area removed. (d): a model with thewhole dentition area retained. (e): a model with the dentitionpartially removed. . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Mandible models with shapes completed by a VSP algorithm[7].(The diseased mandible parts are removed from the 3D mod-els.) Mandibular shape completion algorithms aim to gen-erate bone geometries (green) that resemble the premorbidshape of the dissected segments as much as possible. Theyusually utilize data sets of healthy mandible models. Thepresence of teeth in the data sets often negatively affects themissing geometry computation. . . . . . . . . . . . . . . . . . 31.4 Mandible anatomy. The alveolar process is the thick ridge ofbone in the jaw that holds the dental alveoli, or tooth sockets[20] 4x1.5 Data-driven VSP algorithms workflow for mandible recon-struction using 3D meshes. For a defective mandible with itsdiseased part osteotomized, shape completion algorithms areemployed to model and generate the missing geometry vir-tually based on a data set of healthy mandible models. Thepresence of teeth in both the data set and the osteotomizedtarget mandibles often interferes with the bone geometry com-putation in terms of volume. Our research focuses on toothremoval for healthy models. . . . . . . . . . . . . . . . . . . . 71.6 Dental impression meshes derived from intra-oral scans. (a)A model with negative curvature vertices colored in green[37].(b) Individual tooth identification[38]. . . . . . . . . . . . . . 81.7 Meshes of different slice thicknesses derived from the CT scan.(a) is of a finer slice thickness than (b). . . . . . . . . . . . . 92.1 Snake-based tooth segmentation for dental casts. (a) Thered contours: the snake contours (an active contour aroundeach tooth crown) after optimization. (b) Based on the snakecontours, each tooth is separated individually.[67] . . . . . . . 192.2 A Gaussian mixture of the sum of three normal distributions[89] 222.3 Mesh segmentation using snake contours formed by the ver-tices and edges of the triangular mesh[100] . . . . . . . . . . . 262.4 Constructive Solid Geometry operations. (a) Two geometriesin Maya. (b)Union. (c) Difference. (d) Intersection.[103] . . . 263.1 Snake-based tooth segmentation from mandibular meshes.White model: target mesh. Pink model: mandible template.Cyan wireframe: manually marked tooth crown contour tem-plate. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 293.2 Tooth crown contour marked by a contour template mesh andthe occlusal plane. The contour template is slightly enlargedto illustrate the contour position in here. . . . . . . . . . . . . 30xi3.3 The most back tooth can help determine the tooth crowncontour position (red). The red contours are drawn by adentist from our team. . . . . . . . . . . . . . . . . . . . . . . 313.4 (a) The 16-teeth mandible template[108] and the marked toothcrown contour template. (b) The 16-teeth mandible template[108]and the widened contour template. Following the arrows’ di-rections, we widen the contour template and extend and liftthe two ends in the back behind the molars. . . . . . . . . . . 323.5 Contour line artifacts. Red contours: the tooth crown con-tours on the target model generated by registration. Cyanwireframe: marked tooth crown contour template. (a) A 14-teeth target model with a 16-teeth template registered to it.There are extra contour lines behind the most back teeth. (b)A 16-teeth target model with a 14-teeth template registeredto it. The most back teeth are omitted by the tooth crowncontours. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 333.6 GMM-FEM registration. White model: target mesh. Pinkmodel: mandible template. (a) Before GMM-FEM registra-tion (After aligning the template with the target mesh). Boththe mandible template and the contour template are not de-formed yet. (b) After GMM-FEM registration. The FEMelements deform the mandible template and the contour tem-plate during the registration. Note that the intersection con-tours are drawn closer to the tooth-bone boundary. This isparticularly evident around the area pointed by the arrows. . 353.7 Initial contours that show potential for improvement. Thearrows point to the areas that need modification after regis-tration. Green dash lines: corrections of the initial contours. . 363.8 Key points (red points) insertion based on the initial contoursafter GMM-FEM registration converges. Approximately 50points are evenly selected from the initial contours. We usetheir nearest vertices on the target mesh as key points. . . . . 37xii3.9 Impact of key point number. The snake algorithm balancesbetween finding the shortest path between two key pointsand finding the path passing the desired features. Shown onthe left side of the figure, there are two ways to connect thetwo key points around the most back tooth (the last molar).When the lengths of these two paths are similar, the snakealgorithm may choose the contour that bypasses the tooth. . 383.10 A mandible model colored by SDF value in MeshLab. (a) Theplot range is narrowed to [5,15]. (b) Detail of (a). The toothcrown contour area has higher SDF values than it surroundings. 393.11 For a point on a surface mesh, SDF value is computed bysending rays to the other side of the mesh in the shape of acone that centers around the point’s inward-normal direction(the opposite direction of its normal)[52]. . . . . . . . . . . . 403.12 Checking shape diameter function value can help move keypoints to better positions around the tooth interstices. Bluepoints: updated key points after checking SDF. Red trian-gles: tooth interstices. The updated points are closer to theground-truth tooth crown contour position (right below thetooth interstices) than the initial key points. (a) CheckingSDF values can move the key points below tooth interstices.(b) Checking SDF values can move the key points lying atlower positions up. . . . . . . . . . . . . . . . . . . . . . . . . 413.13 Dealing with key points falling near to the bump at the upperborder of the mandibular bone. (a) The region below thebump (blue point) has a larger SDF value than the initialkey point (red point) position. (b) The updated key pointsare even farther from the ground-truth tooth crown contourthan the initial key points. (c) Adding a constraint on vertexnormal change can prevent the key points from moving belowthe bump. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43xiii3.14 SDF value check results of the two models in Figure 3.7. Theblack arrows point at the areas that need modification afterregistration (same as the ones shown in Figure 3.7). Overallspeaking, SDF value check helps improve the key point posi-tioning for both models. The blue arrow at the bottom of theleft figure points at an artifact introduced by SDF value check. 443.15 Random noise inside of a mandibular mesh derived from CTdata. (a)A mandibular mesh rendered with transparency. (b)Cross section of a mandibular mesh. . . . . . . . . . . . . . . 443.16 SDF value check artifacts caused by the internal geometry.For the three key points counting from the left in (a) and theone in the center of (b), SDF value check did not improvetheir positioning possibly due to the existence of the internalgeometry. The key point to the very right in (a) is updatedto a better position. (c) SDF value check result for the keypoints on the internal geometry beneath the surface shown in(a). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453.17 Geodesic distance and Euclidean distance for contour refine-ment. Green points: updated key points (snaxels) after run-ning the snake algorithm. Red triangles: tooth interstices.(a) Geodesic distance and Euclidean distance between snaxelvertices v1 and v2. (b) Snake algorithm using Euclidean dis-tance. The snaxels are moved above the tooth interstices.(c) Snake algorithm using geodesic distance. The snaxels aremoved below the tooth interstices. . . . . . . . . . . . . . . . 48xiv3.18 The snake algorithm refines the key point position by movingthem to more concave areas in their vicinity. Green points:updated key points (snaxels) after running the snake algo-rithm. (d)-(f) show the snake contours on our models. Bluecontours: the initial snake contours, geodesic paths betweenkey points derived from SDF check. Green contours: snakecontours after energy minimization. (b)(c) The smoothing ef-fect of the snake algorithm fixes the artifacts shown in Figure3.16 (a) and (b). . . . . . . . . . . . . . . . . . . . . . . . . . 493.19 The snake algorithm results. The black arrows point at theareas that need modification after registration (same as theones shown in Figure 3.7). The snake algorithm further im-proves the key point positioning for both models. The bluearrow at the bottom of the left figure points at a previousartifact introduced by SDF value check, which is fixed by thesmoothing effect of the snake algorithm. . . . . . . . . . . . . 503.20 Fitting the contour template to the key points (snaxels) us-ing local deformation. Red contours: final results of the pre-processing algorithm, formed by the locally deformed contourtemplate. Cyan wireframe: the locally deformed contour tem-plate. The black arrows point to the areas that need modi-fication after registration. The contour refinement algorithmimproved the key point positioning for a model with well-defined dentition area (left) and a model with limited surfacefeatures (right). . . . . . . . . . . . . . . . . . . . . . . . . . . 523.21 The preprocessing algorithm result visualization. Cyan wire-frame: the contour template deformed by registration. Redcontours: the results of the whole contour refinement process. 533.22 Contour artifacts. (a)Extra contours (b)Contours on the in-ternal geometry. (b) is the difference mesh between the targetmodel and the contour template in (a). . . . . . . . . . . . . . 54xv3.23 The user interface embedded in ArtiSynth. One control pointin selected (highlighted in yellow) in the main viewer. Atransparent sphere with a radius of 17.0243 mm is renderedaround the control point to show its control range. . . . . . . 553.24 Tooth removal using CSG operator and cut area smoothing . 583.25 An open intersection contour between the contour templateand the target. (a)(b) show the open contour from differ-ent angle. (c) shows the artifact fixed by dragging a nearbycontrol point in the negative y-direction. . . . . . . . . . . . 594.1 Tooth segmentation workflows . . . . . . . . . . . . . . . . . 624.2 Voxel-based manual tooth segmentation using 3D Slicer. (a)3D Slicer interface. Researchers use fiducial points to markthe tooth-bone boundaries. Teeth are removed using toolssuch as ”Erase” and ”Scissors”. (b) The dentulous mandibu-lar mesh. (c) The manual tooth removal result processed byour expert. (d) The edentulous model in (c) is highlighted inred. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 644.3 The manual processing time in the voxel-based method us-ing 3D Slicer (M) and in the proposed mesh-based method(excluding the preprocessing time)(P). . . . . . . . . . . . . . 664.4 Manual processing time for each mandible model. . . . . . . 674.5 Distance comparison between the cut surfaces from 4 groups. 694.6 The manual editing time spent by the two experts in the ad-ditional study and in the main study for 5 randomly selectedmodels. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 704.7 Tooth segmentation strategy. . . . . . . . . . . . . . . . . . . 724.8 Jagged cut surface caused by small fluctuations of the contouris largely resolved after surface smoothing. (a) A small curvyarea between two control points on the contour. (b) The cutsurface appears jagged after CSG tooth removal. (c) Aftersurface smoothing, the effect of the small contour fluctuationis largely removed. . . . . . . . . . . . . . . . . . . . . . . . . 73xvi5.1 The workflow of a Statistical Shape Models (SSM)-based shapecompletion algorithm [2] . . . . . . . . . . . . . . . . . . . . . 765.2 7 classes of mandibular defects. . . . . . . . . . . . . . . . . . 775.3 Symmetric HD95 comparison between Group NT and GroupWT for 7 classes of mandibular defects. . . . . . . . . . . . . 795.4 DSC comparison between Group NT and Group WT for 7classes of mandibular defects. . . . . . . . . . . . . . . . . . . 805.5 Boxplots of symmetric 95th Percentile Hausdorff Distance(HD95) and Volumetric Dice Score (DSC) results averagedacross all 7 defects. . . . . . . . . . . . . . . . . . . . . . . . . 815.6 An unsuccessful shape completion result for a mandible withclass IVc defect (symmetric HD95: 105.99 mm, DSC 0.00).(a) The original mandible and the plane to create the defect.(b) The SSM registration malfunctions possibly due to toomuch missing data in the defect. (c) There is zero overlapbetween the defect replacement and the original cut-out partof the mandible. . . . . . . . . . . . . . . . . . . . . . . . . . 826.1 Tooth segmentation for a mandible with a defect in the frontusing our method with no user input. . . . . . . . . . . . . . 866.2 Donor site placement planning for jaw reconstructive surg-eries. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 916.3 Expected outcome of fitting cylinders to the teeth. . . . . . . 92xviiList of Algorithms1 Local deformation based on Gaussian interpolation. . . . . . 512 One iteration of snake evolvement in the proposed tooth seg-mentation method[96] . . . . . . . . . . . . . . . . . . . . . . 109xviiiList of Abbreviations3D 3-DimensionalAGD Average Geodesic DistanceCAD-CAM Computer-Aided Design and ManufacturingCBCT Cone-Beam Computed TomographyCNNs Convolutional Neural NetworksCSG Constructive Solid GeometryCT Computerized TomographyDSC Volumetric Dice ScoreFEM Finite Element ModelGMM Gaussian Mixture ModelingHD95 95th Percentile Hausdorff DistanceI2C2 Intra-Class Correlation CoefficientICP Iterative Closest PointIOS Intra-Oral ScansSD Standard DeviationSDF Shape Diameter FunctionSSM Statistical Shape ModelsxixUBC University of British ColumbiaVGH Vancouver General HospitalVSP Virtual Surgical PlanningxxAcknowledgementsI would like to first thank my supervisor Dr. Sidney Fels for his continuoussupport and guidance throughout my program. Thank him for allowing meto explore research directions that match my interests and always havinggreat patience and suggestions for me. I learned so much from him on bothresearch thinking and work ethic.Also, many thanks to Dr. Eitan Prisman, Dr. David Yang, EdwardWang, Khanh Linh Tran, Matthew Mong and Jennifer Ham for provid-ing clinical background information, feedback to the proposed interface andhelping me understand the clinical need. Thank Dr. John Lloyd for pro-viding suggestions on programming using ArtiSynth and brainstorming so-lutions with me.Thanks to the members of my research team that assisted me in my thesisproject. A special thanks to two of them for their time as users testing thetool in a pilot study and in the main study.To all my colleagues in the Human Communications Technologies (HCT)Laboratory, I really appreciate their help and support. I feel really luckyworking alongside with them in the past four years. They made so manychallenges I met in research much easier and way more fun. The lab has anamazing research atmosphere, welcoming and motivating.In the end, I am deeply grateful for my loving parents and friends whostood by my side throughout the course of my Master study. I owe every-thing to them.xxiDedicationTo my family and friendsxxiiChapter 1IntroductionGeometric modeling is an invaluable tool for biomechanical research andclinical applications such as therapy modeling, treatment planning, andsurgical simulation. With technological methods improving and interdis-ciplinary collaborations increasing, many advancements have been madein Virtual Surgical Planning (VSP) utilizing Computer-Aided Design andManufacturing (CAD-CAM) tools. VSP has been applied to enhance thetraditional freehand osteotomy and bone reconstruction techniques, boost-ing surgery effectiveness and reducing operative time[2–4]. Mandibular anddental reconstructive surgeries (see Figure 1.1) are among the most complexyet common surgical procedures that have reaped substantial benefits fromVSP.Figure 1.1: Oral reconstruction[5]. The surgical plate is used to fixate thefibula bone grafts with screws. Dental implants are inserted in the nativebone and the bone grafts to allow dental restorations.1To attain optimal functional and aesthetic results, mandibular recon-structive surgeries ideally replace the diseased skeletal buttresses, restorethe external and internal soft tissue envelope, eliminate fistulas, and pro-vide a foundation for dental rehabilitation[6]. As for many other surgeries,it is common to use 3-Dimensional (3D) models segmented from patients’Computerized Tomography (CT) scans to plan for jaw surgeries virtually.Mandibular meshes acquired this way have diversified dentition conditions(see Figure 1.2). The presence of teeth is one major cause of error for bonyshape completion algorithms(see Figure 1.3)[7, 8]. Traditionally, the tootharea on mandibular meshes is either overlooked[9–12] or removed manuallyby research assistants. Manual removal can be time-consuming and error-prone.Figure 1.2: Examples of 3D mandibular meshes segmented from clinical CTscans. (a) and (f): models from patients lacking certain teeth. (b): a modelwith obscure dentition area. (c): a model with the whole dentition arearemoved. (d): a model with the whole dentition area retained. (e): a modelwith the dentition partially removed.From the perspective of dental-implant-based oral rehabilitation (see2Figure 1.3: Mandible models with shapes completed by a VSP algorithm[7].(The diseased mandible parts are removed from the 3D models.) Mandibu-lar shape completion algorithms aim to generate bone geometries (green)that resemble the premorbid shape of the dissected segments as much aspossible. They usually utilize data sets of healthy mandible models. Thepresence of teeth in the data sets often negatively affects the missing geom-etry computation.Figure 1.1), the success rate of implants on the donor bone increases whenthe oral surgeons achieve good positioning of the reconstructed alveolarprocess[13]. The dentists would be able to conduct better virtual planningfor implant placement with the native tooth crown contour and individualtooth identified. Therefore, improved tooth segmentation on mandibularmeshes is needed to support advances in tools for VSP.This thesis develops a fast and easy tooth segmentation method to locatethe alveolar process and remove the dentition area for mandibular meshes.The method includes a preprocessing algorithm and an interactive tool. Thepreprocessing algorithm uses a well-studied and validated non-rigid regis-tration method[14, 15], Shape Diameter Function (SDF) value check, andan active contour model to identify the tooth crown contours, which arethe boundaries of the dentition area. Unlike most active contour modelsthat estimate the contour length using Euclidean distance, we use geodesicdistance on 3D meshes to navigate the contours better around the toothinterstices. The preprocessing algorithm can run offline automatically.We choose to have users in the loop to have a tooth segmentation per-formance as refined as the users prefer. The results of the preprocessingalgorithm will be presented to the users for inspection. Our interactive tool3allows contour position adjustment, which is realized by translating controlpoints that induce local deformation based on Gaussian interpolation. Inthe end, CSG operations are used to remove the teeth. The whole methodwill be introduced in detail in Chapter 3.For method evaluation, our mesh-based tool is compared to the voxel-based manual removal from CT data using 3D Slicer in terms of time costand surface distances. We also would like to better understand the advan-tage of using edentulous mandible models (models without teeth) in VSP.Therefore, we test it using a statistical-shape-modeling-based algorithm formandible reconstruction. Our input data are 3D mandibular meshes ac-quired from Vancouver General Hospital (VGH) and public data sets[16–19].The experimental results indicate great potential in using our tool to im-prove the VSP for oral rehabilitation. We believe our method can assist theresearchers in boosting their tooth removal efficiency and provide guidancefor future studies on implant placement planning.1.1 MotivationFigure 1.4: Mandible anatomy. The alveolar process is the thick ridge ofbone in the jaw that holds the dental alveoli, or tooth sockets[20]The mandible, lower jaw, or jawbone, is the largest bone in the human4facial skeleton[21], as is shown in Figure 1.4. Loss of a segment on themandible may result from trauma, inflammatory disease, and benign ormalignant tumors of head and neck (H&N) cancer, which are diagnosed innearly 1.5 million people worldwide each year[22]. Mandibular defects canlead to functional impairment of chewing and swallowing, causing speechdifficulties as well as cosmetic problems, diminishing the feeling of “well-being” and oral health-related quality of life[23–25]. The goals of mandibularreconstruction are to repair the bone continuity and muscle attachments,establish sufficient height and arch form, maintain an unencumbered airway,and restore the patient’s ability to eat and speak in public[6, 13, 26]. Thetreatments are oftentimes very complicated, requiring expertise from bothoral surgery and restorative dentistry.For structural and functional mandibular reconstruction, free tissue trans-fer has long been a routine method: the shape of the donor bone is dissectedand modeled according to the extent and location of the defect. Ideally, thebone graft can restore the original contour of the mandible and the intermax-illary relationship of the alveolar crest to allow dental implant placement[5].A vascularized rib is one of the earliest donor sites reported[27]. The vas-cularized free fibula flap has been the technique of choice since its intro-duction in 1989[28]. Fibula flap can provide a good length of bone withpossibilities for osteotomies and is easily contoured to fit orofacial bonedefects[29]. A drawback is its limited height, not allowing contouring ofthe inferior mandibular margin and restoring sufficient alveolar height atthe same time[30]. Other autogenous sources for the grafts include the iliaccrest, osseocutaneous radial forearm, and scapula[29, 31].In the past, the shaping and positioning of the free flap are based onthe surgeon’s experience, which is difficult to control during conventionalsurgeries. With the development of VSP tools using preoperative data, thesurgeons are provided with the opportunity to transfer the surgery planto intraoperative templates and predict, anticipate, and prevent surgicalcomplications[10, 32]. Many efforts have been made in evolving VSP usingknowledge in biomechanical modeling, computer graphics, medical imaging,machine learning, etc.5SSM and machine learning algorithms have gained traction in the con-text of data-driven VSP algorithms for modeling the missing geometry ofosteotomized mandibles (see Figure 1.5). Raith et al. introduced a shapereconstruction method for statistical shape representations with anatomy-related topology. They excluded the dental region from the analysis and leftthe alveolar ridge open[33]. The reconstruction shape is computed basedon the residual mandibular structure. Abdi et al. empirically proved thefeasibility of generating missing shapes for diseased mandible models from apredefined set of landmarks. Later, they extended a conditional variationalautoencoder to train deep models using a data set of healthy mandibles.They were able to generate realistic variations for the missing segment withimproved accuracy(see Figure 1.3)[7, 8]. However, they analyzed that theinconsistency in the presence of teeth across the mandible samples causedtraining errors associated with bone loss. Recently Wang et al. createdSSM from a set of 84 healthy mandibles to determine the premorbid shapesfor diseased mandibles[2]. The various dentition conditions in their samplesalso adversely affected their results.These algorithms ”learn” the shapes of mandibular meshes using datasets of healthy models and predict the premorbid shape for diseased mandibles.For the SSM-based method, the suggested range for the number of samplesin such data sets is 60-100[33–35]. (We also see works using up to 200samples to generate SSM in the literature[36].) The data set often con-tains models from various sources, derived from different imaging systems,and segmented by multiple researchers. The dentition area may have beentreated with different segmentation standards, ranging from preserving thewhole tooth crowns to removing the whole alveolar process including thetooth roots embedded in the jawbone. Such inconsistency is a cause ofinconvenience or error to VSP algorithms. Therefore, tooth removal frommandible models is crucial for the performance enhancement of shape com-pletion algorithms.Another motivation of ours is to prepare the diseased mandible for fu-ture dental reconstruction surgery, which requires the reconstructed alveolararch to be similar to the native one so that the dental implants can mimic6Figure 1.5: Data-driven VSP algorithms workflow for mandible reconstruc-tion using 3D meshes. For a defective mandible with its diseased part os-teotomized, shape completion algorithms are employed to model and gener-ate the missing geometry virtually based on a data set of healthy mandiblemodels. The presence of teeth in both the data set and the osteotomizedtarget mandibles often interferes with the bone geometry computation interms of volume. Our research focuses on tooth removal for healthy models.the original native teeth to a large extent. The final goal of mandibularreconstruction is often considered to be dental-implant-supported oral re-habilitation, for which the donor site ideally provides enough bone volumeand is placed at a suitable position taking subsequent dental restorationinto account[5]. Although the timing of implantation remains controversialin the literature, it is widely recommended to have a close collaboration be-tween the oral surgeon and the dental team throughout the treatment. Oralsurgeons may refer to the natural alveolar ridge position when deciding thegraft placement in the virtual plan, enabling the dentist to achieve moreaccurate alignment of implants with the opposing maxillary dentition[30].In the clinic, mandible models are routinely segmented from head andneck CT scans. They are usually saved as 3D mesh files for oral surgeryplanning and simulation. Manual tooth segmentation from mandibular CTscans or 3D meshes is common practice for clinical research. When the CT7data of a mandible (separated from the head and neck area) is available, itgenerally takes trained researchers 3-4 minutes to remove the teeth from itin medical imaging software like 3D Slicer. When the CT data for a singlemandible is difficult to retrieve, tooth removal is conducted on 3D meshesin computer graphics software, such as Blender. Researchers usually cutwith a plane parallel to the occlusal plane or fit a few Boolean boxes to thedentition area on the mesh. Manual editing is needed to clean the cut andfix topology issues, which can also become time-consuming and error-prone.It takes about 10-15 minutes to process one model. We aim to provide asolution to facilitate the tooth segmentation process.Figure 1.6: Dental impression meshes derived from intra-oral scans. (a) Amodel with negative curvature vertices colored in green[37]. (b) Individualtooth identification[38].In the field of tooth segmentation on 2-manifold meshes, most researchprocess meshes derived from Intra-Oral Scans (IOS), which is commonlyused in modern dentistry. IOS imaging captures tooth crowns and gingiva(gum) in a high-spatial resolution, depicting clean tooth border lines. Thisgives sufficient clues for individual tooth identification (see Figure 1.6). Un-der many circumstances, satisfactory contour lines can be found using cur-vature alone[37, 39–42]. However, there is no such privilege for mandibularmeshes segmented from CT scans(see Figure 1.2). With different slice thick-nesses of the CT scan (see Figure 1.7), the teeth on the models are not always8well-defined, making the separation of the dentition area from the mandiblebody difficult. Individual tooth identification is even more challenging. Con-ventional geometry-based methods tend to receive undesirable results[37].Therefore, we explore a solution that combines the prior knowledge of thedentition area position on a jawbone, geometric features in surface meshes,and user intervention. The implementation of the proposed method is withinthe environment of ArtiSynth, a biomechanical toolkit that has been usedin a wide range of applications for modeling and simulation[43].Figure 1.7: Meshes of different slice thicknesses derived from the CT scan.(a) is of a finer slice thickness than (b).1.2 Research QuestionsFrom a holistic perspective, tooth segmentation itself is a preprocessingstep that prepares the mandibular meshes for better reconstruction plan-ning. The major limitation is that it currently remains an unguided manualprocess. Our main research question is:• How can we improve the manual tooth segmentation method usedin the current clinical research workflow for 3D mandibular meshesderived from CT scans?9In this thesis, we develop a tooth segmentation method with a prepro-cessing step supporting interactive tooth removal. We would like to evaluateits effectiveness:• How helpful is the tooth segmentation method we presented in termsof saving time?We also try to answer the following question with proof regarding theimpact of using edentulous models in VSP:• Can data-driven shape completion algorithms perform better usingedentulous mandible data sets than data sets with mixed dentitionconditions?1.3 ContributionsThis proposed tooth removal method serves as a preprocessing step for 3Dmandibular meshes segmented from CT scans of the head and neck area.Figure 1.5 illustrates where tooth removal fits into the VSP workflow formandible reconstruction. Our research mostly focuses on developing andtesting a tooth removal method for data sets of healthy models. In the-ory, the method can also be applied to patient models with defects up to acertain size. We may investigate this in our future work. Tooth crown con-tour identification may also assist donor bone and dental implant placementplanning. The main contributions in this thesis are:• A boundary-based tooth segmentation method that improvesmanual editing efficiency: We propose a mesh segmentation method,including a preprocessing algorithm to compute the tooth crown con-tour on the target mandible model and an interactive contour editingtool. Our study shows that, on average, the proposed method canimprove the traditional manual removal efficiency by 40%. With thepreprocessing-algorithm-generated contour guiding the tooth segmen-tation, 31% of the data need minor user adjustments, 87.5% of userintervention is finished in less than 3 minutes.10• An easy-to-use, interactive mesh editing tool targeted at toothremoval from mandibular meshes: We develop an interactive toolto support user intervention, allowing artifact fixing and fine-to-coarsescale adjustment on the algorithm-generated contours. The functionsin the interface are designed based on both the mandible geometryand the contour editing task. We provide detailed descriptions of theuser interaction design. Given that VSP for mandible reconstructivesurgeries often uses 3D meshes, the proposed mesh editing tool canseamlessly fit into the current clinical research workflow.• Proof of the advantage of using edentulous mandible modelsfor data-driven VSP algorithms: So far, we understand how teethhave an impact on modeling mandible reconstruction in theory. To testthe impact of teeth on modeling mandible reconstruction, we run theSSM-based shape completion test in [2] using their 84 mandible mod-els with teeth removed (we conduct tooth removal for the dentulousmodels based on the results of the preprocessing algorithm). Com-pared to using the original data set with mixed dentition conditions,using edentulous models generates significantly better shapes for theosteotomized mandibles regarding 95th percentile Hausdorff distance(Z=-2.484,p=0.01). The shape completion algorithm performs morerobustly. The study also reflects the effectiveness of the preprocessingalgorithm.1.4 Structure of the ThesisThe remainder of this thesis is structured as follows:• Chapter 2 provides background information on the related work andprevious methods for mesh segmentation, tooth crown contour identifi-cation in 3D meshes, non-rigid registration, and active contour model.We also briefly introduce the constructive solid geometry operations.• Chapter 3 describes the methodology of the preprocessing step andthe user interaction design in detail. We explain the off-the-shelf non-11rigid registration method, the theory of using SDF value to refinethe identified contours, and the snake algorithm using curvature andgeodesic distance on 3D surfaces. We introduce the user interfacedesign and tooth removal using CSG operations.• Chapter 4 describes our study that evaluates how helpful our toothsegmentation method is comparing to the traditional manual removalusing 3D Slicer (a voxel-based method).• Chapter 5 describes our experimental design to test the impact of usingedentulous models on a SSM-based VSP algorithm. The results areshown and discussed.• Chapter 6 summarizes our contribution, discusses the limitations andchallenges expected as well as future research recommendations.In the appendices, we attach the pseudo-code of a published snake evolve-ment algorithm we used (Appendix A), a user interface manual that explainsthe functions in our interactive tool (Appendix B), and the results of ourtwo studies (Appendix C and Appendix D).12Chapter 2Related workIn this chapter, we first review the mesh segmentation techniques in theliterature, covering the commonly used mesh attributes and methods. Wethen provide an overview of teeth-oriented mesh segmentation. The regis-tration method and the active contour model we used in this thesis will beintroduced. The chapter will end with a brief discussion on the constructivesolid geometry (CSG) operator.2.1 Mesh SegmentationThe input data in this thesis are mandible models derived from CT scans,which are essentially 3D meshes. We first consider the tooth segmentationproblem from the perspective of computer graphics. Mesh segmentationalgorithms apply criteria and constraints to mesh attributes to decide whichelements belong to the same segment. Summarized by Shamir, there aremainly ten frequently used mesh attributes[44]. Table 2.1 shows examplesof using mesh attributes to segment objects.For mandibular mesh segmentation, about half of the attributes listedhere are applicable. Curvature and geodesic distance are two of the mostuseful surface properties of the mesh. They are easy to compute or ap-proximate but susceptible to local noise. Curvature is frequently utilizedto segment an object into meaningful volumetric parts (part-type semanticsegmentation) following the minima rule, which states that an object tendsto be segmented by human perception at areas of concavity[45]. Geodesicdistance is the shortest path length between two vertices in a graph. AverageGeodesic Distance (AGD), also known as centricity, is the average geodesicdistance from each vertex to all other vertices on the mesh. AGD can reflect13the global geometry and topology of an object.Table 2.1: Frequently used mesh attributes for segmentation[44, 46–51]14In addition, a mandible can be regarded as a symmetric structure to alarge extent. Mirroring the healthy side of the mandible is one of the prepro-cessing techniques for reconstruction planning in the clinic[2]. Nonetheless,the dentition conditions are not necessarily symmetrical. The shape diame-ter function (SDF) is also worth considering. As a scalar function defined ona closed manifold surface[52], SDF can distinguish the thick and thin partsby measuring the neighborhood diameter of the object at each vertex[53].For the methodologies of mesh segmentation, Theologou et al. classifiedthe previous efforts into ten types[54].15Table 2.2: Mesh segmentation methodologies[47, 54–63]16Clustering and region growing are two of the earliest proposed and mostfundamental approaches, usually used as subroutines in the geometric mod-eling algorithms nowadays. Surface fitting is based on the observation thatmany object parts can be approximated by a primitive shape or a high-ordersurface, primarily applicable to mechanical CAD objects. Topological meth-ods are further categorized into methods using Reeb graphs and methods us-ing core identification, both suited for partitioning articulated objects. AGDis widely used in topological methods due to its pose-invariance. For spatialsubdivision methods, the objects are hierarchically subdivided using multi-scale volumetric attributes. In our case, the mandible model, especially thedentition area, is not composed of varying scales of the structuring elements.Spectral methods can reveal meaningful global shape properties using local17relations. They employ the eigenvalues, eigenvectors, or eigenspace projec-tions derived from appropriately constructed mesh operators[59]. Boundary-based methods aim at locating the boundaries of the segments instead ofthe segments themselves, which follow the minima rule introduced by Hoff-man and Richards[45]. In this thesis, we developed a boundary-based toothsegmentation method.In the rest of the methodologies, the probabilistic methods make use ofmachine learning, which can achieve high segmentation accuracy trainingon ground-truth datasets. These methods are more complex than mostdeterministic methods. When applying to our case, the sample size is amajor concern. The research pertains to patient health records, which areusually not accessible to the public. Open datasets with segment labels arealso difficult to acquire. Motion-based methods separate parts of movingobjects by locating the joints of the segments (our target meshes are staticobjects). Co-segmentation methods take unsegmented, unlabelled meshes asinput and seek correspondences between similar shapes. They are possiblesolutions, given the fact that, naturally, there is a low variance betweenindividual mandibular models. However, these methods are also data-drivenand the segmentation results relies heavily on the data quality[64, 65].2.2 Tooth-Oriented Mesh SegmentationWith oral surgery and computer-aided orthodontics techniques developing,research in tooth-oriented segmentation has advanced fast, mainly targetingdental cast meshes. To this end, the goal is to achieve accurate segmenta-tion of each tooth, whereas our objective is to locate the dentition area onmandibular meshes. Nonetheless, these works are valuable references.Many techniques[66–68] have reported good segmentation performanceson models with normal dentition conditions but encounter problems whenthe teeth arrangements are complex. In 2004, Kondo, Ong, and Foongproposed a highly automatic method that segments teeth by extracting in-terstice points on planar and panoramic range images. They employed edgedetection and curve fitting algorithms to detect the dental arch and tooth18interstices and used surface normal difference to separate the teeth fromthe gum. Their result was not satisfactory when processing models with se-vere malocclusions[69]. Kronfeld et al. estimated the boundary between theteeth and the gum using an active contour, calculated the dental arch andthe interstices between the teeth, and evolved a snake around each toothcusp (see Figure 2.1). Their approach is highly automatic but may notperform well on models with boundary noises[67]. Kumar et al. identifiedinterstices between teeth by connecting the points that link the lingual andthe labial sides of the gumline. The adjacent teeth were separated usingthe interstices. On teeth with complex contours (e.g., crowded teeth), theperformance of this method may be impaired[68].Figure 2.1: Snake-based tooth segmentation for dental casts. (a) The redcontours: the snake contours (an active contour around each tooth crown)after optimization. (b) Based on the snake contours, each tooth is separatedindividually.[67]In later works, Wu et al. obtained single-vertex width tooth boundariesbased on a morphologic skeleton technique. The method is robust to tooth-crowding problems but can require more user interactions when the input istoo noisy [70]. Liao et al. developed an automatic framework that extractseach tooth boundary as an isoloop by a dental-targeted harmonic field fromdental mesh. Relying on prior knowledge of the feature points on the teeth,their method is robust to various tooth shapes and crowding problems[71].19In 2016, Li and Wang employed automatic feature point detection, mouseclicks from the user to specify which teeth to segment, and a harmonic fieldwith a concavity-aware weighting scheme. The candidate cutting lines canbe detected from concave regions with large variations of field data[72]. Kimand Choi used a transverse plane to partition the model into the tooth andunknown parts. They projected the vertices from the tooth part onto thetransverse plane and clustered vertices into individual teeth. The methodis robust to noise but may not function well when there are snaggleteethand misalignment[73]. In 2020, Woodsend et al. proposed an automaticmethod to identify landmarks on each tooth[42]. They extracted the shapeand boundaries of the individual tooth using surface gradient and curvature.To label the teeth and their landmarks, they used a combination of machinelearning and linear programming. The algorithm has a relatively good toler-ance for tooth crowding but has trouble separating the molar teeth. Yang etal. developed a boundary-based method and an intelligent scissors tool[74].They mainly used curvature and anisotropic geodesic distance to extractthe contour curves and a 3D midpoint smoothing algorithm to smooth thecontour. The algorithm works well on meshes with visible valleys or ridges.More and more recent works[37, 38, 40, 41, 75–79] use deep learningapproaches for accurate and robust segmentation. In 2018, Xu et al. pro-posed a 2-level hierarchical deep Convolutional Neural Networks (CNNs)structure for tooth segmentation: one level for teeth-gingiva labeling andthe other level for inter-teeth labeling[37]. The approach proposed by Tianet al. used the sparse voxel octree and 3D CNNs for segmenting and classi-fying tooth types on the dental models. Compared with four state-of-the-artmethods, Tian’s method achieved higher accuracy and universality, but thegeneralization ability of their network is yet to be proved with more trainingsamples[77]. Very recently, Sun et al. enabled simultaneous teeth-gingivaand inter-tooth segmentation on digital dental casts via feature steered graphCNNs, which dynamically updates the mapping between convolutional fil-ters and local patches from the input[78].We also see a trend of using multi-modal data for tooth segmentation.Unlike other works we reviewed, the goal here is to acquire a 3D complete20tooth mesh model (including both the dental crown and the root) for or-thodontic treatment. In 2015, Wei et al. fused the tooth root extractedfrom the Cone-Beam Computed Tomography (CBCT) data with the lasercrown model[80]. The two parts are connected by the Bezier surface. In2018, Zhou et al. reconstructed the teeth by fusing the crown mesh fromlaser scanning and the root mesh from CT images using the Delaunay-basedregion-growing (DBRG) algorithm[81]. Their method requires manual se-lection of one seed point for each crown. Qian et al. offered an automaticlevel-set-based solution. The initial contour of the level set is formed byregistering the laser-scanned crown mesh to the CBCT data and computingthe convex hull[82].From these works, we see again that surface features (concavity in par-ticular) are heavily used for partitioning. There are several boundary-basedsolutions, given that the boundary between teeth and gum is usually rich infeatures. Because of the complex appearance of human teeth, a high-levelinterpretation of the mesh geometry may be needed to ensure segmentationaccuracy. Therefore, user intervention may be necessary, either to initial-ize the algorithm or to fix the segmentation artifacts. In addition, machinelearning algorithms are gaining traction. With more clinical data, a machinelearning approach could be more feasible in the future.2.3 Image registration methodsTo initialize the boundary between the dentition area and the jawbone,we consider using the image registration technique, which is an importanttechnique in computer vision and pattern recognition. Image registrationcomputes a spatial transformation that aligns the two images. It is usu-ally formulated as an energy minimization problem of finding the best set oftransform inputs that maximize the similarity between two images[83]. Non-rigid registration is preferred for clinical applications of simulation, identify-ing landmarks, and medical image segmentation[84, 85]. It utilizes non-rigidtransformation, which includes affine transformations such as scaling andshearing mapping.21The Iterative Closest Point (ICP) algorithm introduced by Besl andMcKay is a crucial approach for registering 3D shapes[86]. It is an iterativedescent procedure that minimizes the sum of the squared distances betweenall points in the source shape and their closest points in the target shape.With known correspondences between the source and target point sets, therigid transformation that best aligns the scene can be computed in closedform using least-squares fitting [83, 87]. ICP-based algorithms are simple,intuitive, and fast to converge but very sensitive to initialization, noise, andoutliers[14, 88]. The drawbacks are due to the fact that the closest pointpairs do not necessarily correspond to each other.Figure 2.2: A Gaussian mixture of the sum of three normal distributions[89]Gaussian Mixture Modeling (GMM) based registration has been shownto be more robust than ICP. A Gaussian mixture model is a parametricprobability density function represented as a weighted sum of Gaussiancomponent densities (see Figure 2.2), commonly used as a model of theprobability distribution of continuous measurements or features in biomet-ric systems[90]. Using GMM, the problem of image registration is refor-mulated as the problem of aligning two Gaussian mixtures and minimizingthe discrepancy between them[91]. In 2015, Khallaghi et al. implemented anon-rigid registration method, GMM-FEM, a probabilistic framework usingGMM along with a Finite Element Model (FEM) that treated the sourcesurface as the centroids of Gaussian distributions[14, 15]. Given a sourcesurface formed by a collection of points X = {xm}Mm=1, and a collection of22target points forming a target surface Y = {yn}Nn=1 , the correspondencebetween source and target points is defined as the log-likelihood that thetarget points are drawn from the surface distribution:S(X,Y ) =1N∑nlog(1M∑mp(yn|xm))p(·|xm) is a Gaussian distribution centered at the current xm with varianceσ2:p(y|xm) = 1√(2piσ2)3exp(−‖y − xm‖2)/2σ2).Khallaghi et al. also incorporated biomechanical prior knowledge in aFEM regularizer to extrapolate and constrain the deformation field. Therobustness and efficiency of GMM-FEM were validated using clinical datain previous studies. We tested several non-rigid registration methods (in-cluding ICP based registration methods) and found that the GMM-FEMregistration works best for our purpose of initializing the tooth crown con-tour on mandibular meshes.2.4 Snake: Active Contour ModelAfter running GMM-FEM registration, the approximate location of thetooth crown on a target mandible model is known. We consider using anactive contour model to refine the contour lines. Active contour model, orsnakes, was first proposed by Kass et al. to enable feature detection in 2Dimages. It was very influential and sparked many research works. One ofthe essential enhancements made to the original model was an extension togeometric snakes to extract features from 3D surfaces[92]. The snake modelis currently used in a wide range of applications in object tracking, shaperecognition, segmentation, edge detection, and stereo matching.A snake is an energy minimizing, deformable spline shaped by internalforces that resist deformation and external forces that pull it towards objectcontours. The internal forces impose a piecewise smoothness constraint.The external forces, coming from a user interface, automatic algorithms, or23high-level interpretations, put the snake near the desired local minimum[93].The snake evolves around the model and forms a closed loop for cutting theindividual part[94]. For a snake v on a 3D mesh formed by a set of snakevertices: v = {v0, v1, v2, . . . , vn−1}, the energy is defined as:Esnake(v) =n−1∑i=0(Eint(vi) + Eext(vi))Eint(vi) is the internal energy of vi, which controls the length and thesmoothness of the snake. The external energy Eext(vi) is used for attract-ing the snake to desired features on the mesh, defined depending on therequirements on the boundary. At mesh features, the energy has its localminimums among the neighbor vertices[92, 95, 96].Comparing to other feature extraction methods, the key advantages ofsnakes are:• Autonomous and self-adapting during energy minimization.• Easy to manipulate. External image forces affect the snake in anintuitive manner.• Applicable for tracking dynamic objects.The drawbacks of the traditional snakes mainly are:• Sensitive to initial contour position and local minima states. Simulatedannealing techniques are able to counteract this drawback, but theytake a longer time to compute.• Relatively insensitive to minute features during energy minimization.• Compromising between accuracy and computation time. Higher ac-curacy requires tighter convergence criteria, which results in longercomputation time[97].The sensitivity to local minima may mislead active contours, especiallywhen the model contains noisy textures. Adding user interaction is a com-mon strategy to help improve the contour accuracy or to enable faster con-vergence. Many researchers have endeavored to combine snakes with user24interference of various forms with the least user input. Bischoff et al. han-dled snakes on 3D surfaces using an interactive method. A sequence ofvertices was first selected by the user on an input mesh and then connectedusing a discrete shortest path algorithm (Dijkstra) along the edges of themesh[98]. Torkaman et al. also used user input to initialize the active con-tour. The level set technique was employed for contour evolution. The restof their algorithm is automatic procedures[99].When an image snake is extended to a geometric snake, there are two ma-jor problems: how to constrain the snake movements onto the mesh surfaceand how to define the desired features. Lee, Y. and Lee, S. used parameter-ization that embedded the neighboring region of a geometric snake to a 2Dplane. The geometric snake evolves on the plane and is mapped back to thesurface of the mesh during energy minimization. The method makes use ofthe normal changes of faces to determine the feature energy functional[92].Based on this method, Lee et al. refined geometric active contour loops us-ing mean curvature[95]. They reported a fully automatic scissoring schemeand a semi-automatic user interface, but they encountered topological issues(e.g.broken regions representing the same boundary). Jung and Kim formedtheir snake using the vertices of the triangular mesh in question. The snakenever leaves the 3D surface in this way. During each iteration, they movedeach snake vertex to one of its neighbor vertices on the mesh and calculatedfeatures related to Gaussian curvature. The energy of the snake is dimin-ished using a greedy optimization[96]. For simplicity and faster computationtime, we based our algorithm on Jung and Kim’s method.Later works [94, 100, 101] have developed various methods to compen-sate for the drawbacks of the snake algorithm. Benhabiles et al. mainlyused a learning approach to identify contours and then used the snake tooptimize them (see Figure 2.3). They improved the snake movement algo-rithm proposed by Jung and Kim by using the learned edge function insteadof curvature for external energy[100]. Their method is automatic, but it en-countered difficulties capturing semantic contours because of using simplelocal geometric criteria. Xie et al. employed an active contour model simi-lar to the works of Benhabiles et al. to smooth the contour[102]. Ng et al.25Figure 2.3: Mesh segmentation using snake contours formed by the verticesand edges of the triangular mesh[100]generated a skeleton model to guide the snake-based approach to find theboundary between two features. Comparing to the Shape Diameter methodand the Core Extraction method, the contours generated by this methodturn out to be more accurate[94]. The method is designed for segmentingobjects of hierarchical structures, which is not exactly suitable for our taskof tooth segmentation.2.5 Constructive Solid GeometryFigure 2.4: Constructive Solid Geometry operations. (a) Two geometries inMaya. (b)Union. (c) Difference. (d) Intersection.[103]26For our project, we used CSG operations to compute the intersectioncontours between the mandible model in question and a template clip meshand remove the dentition area.Constructive Solid Geometry (CSG) is a solid modeling technique incomputer graphics. It allows the creation of a complex surface or objectusing Boolean operators to compute the union, intersection, or difference ofsimpler objects(see Figure 2.4)[104, 105]. ArtiSynth supports CSG opera-tions on volumes bounded by triangular meshes, which works by determiningthe intersection contours between a pair of meshes and computing the tri-angles that need to be added or removed to produce the CSG surface[106].The operations achieve the best results when the two intersecting meshesform closed contours.2.6 Chapter SummaryIn this chapter, we reviewed the related work on mesh segmentation, teeth-oriented mesh segmentation, GMM-FEM registration, and the active con-tour model. We briefly introduced the concept of CSG operator. In thefollowing chapter, we will develop our methods for segmenting the dentitionarea for mandibular meshes.27Chapter 3Snake-Based PreprocessingAlgorithm and UserInteractionIn this thesis, we develop a snake-based tool for supporting interactive toothsegmentation from mandibular meshes (see the workflow in Figure 3.1). Wesegment the teeth by identifying the boundary between the teeth and thebone. The core of our work is the contour refinement algorithm that in-cludes shape diameter function (SDF) value check and a snake algorithm(active contour model) using surface features. As mentioned in Section 2.4,the convergence of the snake algorithm relies heavily on its initial place-ment. If a snake starts the evolution somewhere far from the ground-truthcontour location, the result usually ends up not being ideal (being locallyoptimal but globally suboptimal). To initialize the snakes on the targetmesh, we first run rigid and non-rigid registration[14, 15] using a mandibletemplate with marked tooth crown contours. The tooth crown contours onthe target mesh are estimated using the intersection contours formed by thecontour template. For contour refinement, we extract key points near theinitial contours, check their SDF values, and run a snake algorithm thatuses geodesic distance to refine the contour position. The contour templateis further deformed. A simple interface embedded in ArtiSynth is presentedto allow manual contour editing using control points and local deformation.In the end, a CSG operator is employed to remove the dentition area fromthe position of the tooth crown contours and the cut surface is smoothed.The result edentulous model can be saved in any 3D mesh format.28Figure 3.1: Snake-based tooth segmentation from mandibular meshes. White model: target mesh. Pink model:mandible template. Cyan wireframe: manually marked tooth crown contour template.293.1 Introduction of Tooth Crown ContourFigure 3.2: Tooth crown contour marked by a contour template mesh andthe occlusal plane. The contour template is slightly enlarged to illustratethe contour position in here.On dental impression meshes (see Figure 1.6), tooth crown contour is theboundary between the dentition and the gingiva (gum)[37, 40, 73, 77, 78,107]. Similarly, it is the boundary between the dentition and the bone onthe mandibular meshes. Tooth crown contour separates the dentition areaand the mandibular bone body, marking the position of the alveolar process.As shown in Figure 3.2, the contour is roughly parallel to the occlusal planeand below the tooth interstices. The area is concave on a mandible but mayappear to be flat on a low-resolution mesh. Some mandible models derivedfrom CT scans lack definitive surface features around the front teeth (seeFigure 3.3). Nonetheless, the most back tooth can give researchers a goodsense of the height of the tooth crown, thereby determining the tooth crowncontour for the entire mandible.3.2 Preprocessing AlgorithmThe preprocessing algorithm identifies the tooth crown contours/the alveolarprocess position on target mandible models based on surface mesh features.The calculated contours can serve as a guidance or a baseline for the user,thus helping reduce human efforts in conducting tooth removal. The wholealgorithm includes an off-the-shelf non-rigid registration method, SDF valuecheck, and a snake algorithm using geodesic distance.30Figure 3.3: The most back tooth can help determine the tooth crown contourposition (red). The red contours are drawn by a dentist from our team.3.2.1 Data Acquisition and Template CreationOur input data are dentulous mandibular meshes either converted from CTscans of nononcologic patients from Vancouver General Hospital, or acquiredfrom publicly available data sets (see the screenshots in Appendix C andD). The mandibles are healthy models that do not display pathology orsegmentation artifacts. They are utilized for VSP in clinical research. TheCT data are of different scanning resolutions. The mesh resolutions arewithin the range of 10-20k vertices. In our two studies for method evaluation,the first study uses 48 dentulous models, while the second one uses another28 dentulous models and 56 edentulous models.Besides models of patients, we also prepare a mandible template. Forbiomechanical models, it is difficult to achieve adequate segmentation resultsrelying on the surface features only. So we first match a mandible templatewith marked tooth crown contours to the target model using GMM-FEMregistration. Our template model was created by the University of Dundee,School of Dentistry[108] (see Figure 3.4). It is a triangular mesh with 82,668vertices, which is of a high resolution. According to literature[14], GMM-FEM registration is not sensitive to the number of surface points as long asthe surface adequately represents the anatomy. So we simplify the templatemodel to approximately 3000 vertices to speed up the registration.To match the tooth crown contours, we create a contour template that is31Figure 3.4: (a) The 16-teeth mandible template[108] and the marked toothcrown contour template. (b) The 16-teeth mandible template[108] and thewidened contour template. Following the arrows’ directions, we widen thecontour template and extend and lift the two ends in the back behind themolars.deformed along with the mandible template in the registration. We manuallymark the ring of vertices that separates the teeth from the bone on themandible template. They are triangulated into a horseshoe-shaped contourtemplate (an open mesh) (see Figure 3.4(a)). At a later step, we will use thecontour template in a CSG operation for tooth removal, which requires thecontour template to form closed intersection contours with different targetmodels. So we widen the contour template and extend and lift the two endsin the back behind the molars (see Figure 3.4(b)). We also subdivide the32contour template. After applying the CSG operator, the subdivided meshresults in a better triangulated flat cut surface, also leading to a bettersurface smoothing outcome.It is worth noting that our mandible template has 16 teeth (see Figure3.4). An adult usually has 14 to 16 teeth (with the third molars) on themandible. In our experiments with 14-teeth and 16-teeth templates, bothtemplates can cause contour artifacts when registering to target models withdifferent numbers of teeth. A 16-teeth template can morph to 14-teethtarget meshes well, except for around the third molars. The third molarsare usually matched to the bone area behind the second molars on a 14-teethtarget, forming extra contour lines (see Figure 3.5(a)). On the other hand,the third molars of 16-teeth targets are usually matched to the bone areabehind the second molars on a 14-teeth template. The 3rd molars are left outfrom the dentition (see Figure 3.5(b)), which is a problem more challengingto fix. It is easier to shrink or remove contours than to expand or createnew ones. Therefore, 16-teeth templates are preferred over 14-teeth ones.Figure 3.5: Contour line artifacts. Red contours: the tooth crown contourson the target model generated by registration. Cyan wireframe: markedtooth crown contour template. (a) A 14-teeth target model with a 16-teethtemplate registered to it. There are extra contour lines behind the mostback teeth. (b) A 16-teeth target model with a 14-teeth template registeredto it. The most back teeth are omitted by the tooth crown contours.In the figures of this chapter, unless otherwise specified, the red contours33are the initial tooth crown contours on the target model generated by reg-istration (the intersection contours between the contour template and thetarget mesh). And the cyan wireframe is the contour template deformed byregistration.3.2.2 Rigid and Non-Rigid RegistrationModel registration is a crucial medical imaging technique that can be easilyand quickly applied to different surgical cases. As discussed previously, weuse the registration to help initialize the tooth crown contour on the targetmodel. Our goal is to match the tooth crown contour area on the two meshesas closely as possible. We start by aligning the mandible template (andthe contour template) with the target mesh using a rigid ICP registration.Preliminary registrations, usually with lower degrees of freedom, can helpimprove the final result. Subsequently, we use the non-rigid GMM-FEMregistration (see Figure 3.6) by adapting an existing registration frameworkimplemented in ArtiSynth[14]. In the framework, all points on the surfacecorrespond to nodes, and internal nodes are appended to the end of the nodelist. A deformable FEM grid is created for the mandible template (with thecontour template) through spatial discretization. The contour template goesthrough the same deformation as the corresponding area on the mandibletemplate because they are controlled by the same group of FEM nodes andelements.By the end of the registration, the intersection contours between thecontour template and the target mesh are our initial tooth crown contourestimation for the target model (see the red contours in Figure 3.6 (b)).The accuracy of the initial contours varies from model to model. For themodels in Figure 3.6 and Figure 3.8, the initial contours are mostly correct.For the models in Figure 3.7, which are also typical in our input data set,there are large potentials for improvement. The model on the left lacks afew teeth but has an adequately defined dentition area. The model on theright has limited surface features around the teeth-bone boundary, whichis a challenging case for our algorithm. We will use these two models as34Figure 3.6: GMM-FEM registration. White model: target mesh. Pinkmodel: mandible template. (a) Before GMM-FEM registration (After align-ing the template with the target mesh). Both the mandible template and thecontour template are not deformed yet. (b) After GMM-FEM registration.The FEM elements deform the mandible template and the contour templateduring the registration. Note that the intersection contours are drawn closerto the tooth-bone boundary. This is particularly evident around the areapointed by the arrows.examples illustrating the effect of each step of the preprocessing algorithmin Section 3.2.For the goal of matching the alveolar process on two models, the GMM-FEM registration is not very sensitive to its parameters. In our experiments,a FEM density of less than 0.1 and a force scaling parameter in the range of35Figure 3.7: Initial contours that show potential for improvement. The ar-rows point to the areas that need modification after registration. Greendash lines: corrections of the initial contours.[104, 107] are adequate. We set the default values as 10−4 for FEM densityand 106 for the force scaling parameter. Our input meshes are the same typeof biomechanical models with similar resolutions. So they can share the sameset of registration parameters. The parameters are chosen according to thevalues mentioned in the literature [15] and adjusted according to the meshproperties. On a regular laptop, the registration usually converges within100 iterations, which takes about 10 seconds. For meshes with much largeror smaller resolutions than our input meshes, the registration can convergewithin 10 seconds with the parameters properly tuned.3.2.3 Contour Refinement AlgorithmInitial Key Point SelectionThe initial contours derived from registration fluctuate in the vicinity of theground-truth alveolar process position due to registration error and variationin mandible shapes. So we would like to search the neighborhood of theinitial contours to refine the contour position and further deform the contourtemplate. Technically speaking, the intersection contours are lists of pointslying on the 3D mesh surface. However, using the original mesh verticesfor iteration is more convenient than using points in the mesh faces. Sowe evenly select approximately 50 points from the contours and find thenearest vertices for them on the target mesh (see Figure 3.8). The nearest36Figure 3.8: Key points (red points) insertion based on the initial contours af-ter GMM-FEM registration converges. Approximately 50 points are evenlyselected from the initial contours. We use their nearest vertices on the targetmesh as key points.vertices serve as the initial key points that anchor the contours in our contourrefinement algorithm. (In the rest of this chapter, we use red-colored pointsto represent the initial key points in the figures.)The number of key points is decided because of the reasons below. Byselecting about 50, there are 3-4 key points on average encircling each tooth,pinning down the contour line. With less than 3 points around each tooth,the contours may shrink and bypass teeth during the iteration of the con-tour refinement algorithm (see Figure 3.9). (Part of our contour refinementalgorithm aims at minimizing the distance between key points. When thereare only 2 key points around the most back tooth, the algorithm may chooseto exclude the tooth from the dentition area while looking for the shortestpath between the key points.) On the other hand, increasing the key pointnumber may stretch the computation time. So we come to settle on about50 points for each model.37Figure 3.9: Impact of key point number. The snake algorithm balancesbetween finding the shortest path between two key points and finding thepath passing the desired features. Shown on the left side of the figure, thereare two ways to connect the two key points around the most back tooth(the last molar). When the lengths of these two paths are similar, the snakealgorithm may choose the contour that bypasses the tooth.Shape Diameter Function CheckTo refine the contours, we experiment with a number of surface features andfind that shape diameter function (SDF) can distinguish the tooth crowncontours from their surroundings. This can be proved in the MeshLab qual-ity maps. Figure 3.10 (a) illustrates that our area of interest contains localmaximum values. The contrast is particularly salient around the molars (seeFigure 3.10 (b) for more detail). Hence, contour corrections can be madebased on this observation.The SDF is defined for solving mesh partitioning and skeletonization [52].It is a scalar function that measures the local diameter of the object’s volumeon the surface, distinguishing the thick and thin parts of the object. For apoint on a surface mesh, a group of rays is sent to the opposite side of themesh (see Figure 3.11). For each ray, the normal at the point of intersectionis checked to remove false intersections. The SDF value is computed as theweighted average of all rays’ lengths that are within one standard deviation38Figure 3.10: A mandible model colored by SDF value in MeshLab. (a) Theplot range is narrowed to [5,15]. (b) Detail of (a). The tooth crown contourarea has higher SDF values than it surroundings.from the median of all lengths.We illustrate how the SDF value can refine the initial contours in Figure3.12. In this chapter, we use blue-colored points to represent the updatedkey points after checking SDF value in the figures. The blue points are39Figure 3.11: For a point on a surface mesh, SDF value is computed bysending rays to the other side of the mesh in the shape of a cone thatcenters around the point’s inward-normal direction (the opposite directionof its normal)[52].rather close to our target position in Figure 3.12 (a) and (b). Their normaldirections are almost parallel to the occlusal plane. So the median rays sentfrom them are almost horizontal.Consider the situation when an initial key point is at a higher positionthan desired (see the red points in Figure 3.12 (a)). It lies on the convexcurved surface near the bottom of the tooth crown. And its inward-normalfaces upward (positive z-direction). When sending rays in a cone centeredaround the inward normal, most of them intersect with the crown’s topsurface. In comparison, for a point closer to the tooth crown contour (seethe blue points in Figure 3.12 (a)), its inward-normal faces more horizontallyto the other side of the tooth. Some of the rays can reach the inferior borderof the bone, contributing to a higher SDF value of this point than the keypoint above it. In another situation, when an initial key point is at a lowerposition than desired (see the red points in Figure 3.12 (b)), its inward-normal faces downward. Some of the projected rays intersect with the topof the mandibular bone, yielding very short ray lengths and a small SDFvalue. Whereas for a point right above the key point (see the blue points inFigure 3.12 (b)), the inward-normal faces more upward. The rays evade thetop part of the bone that is near to them. Some extend in the bone body40Figure 3.12: Checking shape diameter function value can help move keypoints to better positions around the tooth interstices. Blue points: updatedkey points after checking SDF. Red triangles: tooth interstices. The updatedpoints are closer to the ground-truth tooth crown contour position (rightbelow the tooth interstices) than the initial key points. (a) Checking SDFvalues can move the key points below tooth interstices. (b) Checking SDFvalues can move the key points lying at lower positions up.and some can hit the crown’s top surface. So the SDF value of this point,which is closer to the tooth crown contour, is larger than the key point belowit. In summary, the tooth crown contour area tends to contain locally largeSDF values. So we can adjust the initial key point positions by relocatingthem to places nearby with large SDF values.41For our purpose, we compute the SDF value in a way slightly differentfrom its original definition. In practice, the points we are discussing hereare very close to each other. The differences in SDF values are subtle. Theway SDF is originally defined reduces this difference: ray lengths fallingout of a designated range are eliminated, and smaller weights are assignedfor rays with larger angles. The cone angle is set to 120◦and 30 rays aresent per point in [52]. To amplify the value difference, we include all raysand consider them equally in the computation. We compute SDF as thearithmetic mean of all rays’ lengths within the cone. The cone angle isenlarged to 150◦. 50 rays are sent at each point.3 iterations of SDF value check are applied to each contour in our ex-periments. With mandible models of higher resolution, more iterations areneeded. For each key point vertex, we check its one-ring neighbors on thetarget model. If a neighbor has a higher SDF value, it will substitute thecurrent key point vertex.Through experimenting with different models, we realize that constraintson vertex normal need to be added to boost the effectiveness of SDF valuecheck. We observe that it is tricky when the initial key points are on thebump region at the superior border of the mandibular bone. The bumps arepossibly exostoses, which are often observed below the tooth crown contourof the anterior teeth. The areas both below and above the bump havelarger SDF values than the vertices right on top of it (see Figure 3.13(a)).Key points on the bump may end up moving to an even lower position(see Figure 3.13(b)). To eliminate this artifact, we add a constraint onthe vertex normal during the iterations: SDF values are only computed forthe neighbor vertices whose vertex normals face more upward (positive z-direction) than the key point normal. The vertices lying below the bumpresult in negative vertex normal changes, so they are excluded from being akey point candidate. Moreover, all positions above the bump are unaffectedand protected by this constraint. Both of the situations we discussed inFigure 3.12 are still valid. To prevent the key points from moving to the topsurface of the teeth, the key point normal should also form an angle largerthan 60 degrees with the positive z-direction.42Figure 3.13: Dealing with key points falling near to the bump at the upperborder of the mandibular bone. (a) The region below the bump (blue point)has a larger SDF value than the initial key point (red point) position. (b)The updated key points are even farther from the ground-truth tooth crowncontour than the initial key points. (c) Adding a constraint on vertex normalchange can prevent the key points from moving below the bump.Judging from the updated key point positions visually, SDF is generallya reliable feature for adjusting the tooth crown contour positions (see Fig-ure 3.14). The only drawback is caused by the fact that the mesh samplessegmented from CT scans often contain internal geometry (see Figure 3.15and Figure 3.16 (c)). On the one hand, false ray-mesh intersections underthis circumstance would be difficult to rule out. The ray lengths wouldbe shortened, and contours misled, which introduces artifacts as shown in43Figure 3.14: SDF value check results of the two models in Figure 3.7. Theblack arrows point at the areas that need modification after registration(same as the ones shown in Figure 3.7). Overall speaking, SDF value checkhelps improve the key point positioning for both models. The blue arrow atthe bottom of the left figure points at an artifact introduced by SDF valuecheck.Figure 3.15: Random noise inside of a mandibular mesh derived from CTdata. (a)A mandibular mesh rendered with transparency. (b) Cross sectionof a mandibular mesh.Figure 3.14 and Figure 3.16 (a) and (b). On the other hand, the intersec-tion contours between the contour template and the internal geometry, asshown in Figure 3.16 (c), are also difficult to rule out. They are treated thesame way as the intersection contours on the bone surface: key points areinserted and SDF values are checked. The positioning of these key points44will affect the smoothness of the tooth removal surface, which, however, canbe ameliorated by surface smoothing.Figure 3.16: SDF value check artifacts caused by the internal geometry. Forthe three key points counting from the left in (a) and the one in the centerof (b), SDF value check did not improve their positioning possibly due tothe existence of the internal geometry. The key point to the very right in(a) is updated to a better position. (c) SDF value check result for the keypoints on the internal geometry beneath the surface shown in (a).Snake Algorithm Using Geodesic DistanceWith SDF, we attempt to accent the tooth crown contour area using themandible’s local thickness. Still, there are potentials for improvement. Theproblem of object segmentation can also be approached from the perspec-45tive of human vision. The minima rule from perception states that distinctmeaningful part boundaries recognized by humans tend to be lines of min-imum negative curvature[45]. Our observation of the tooth crown contoursconforms with this rule. So we consider using curvature in the snake algo-rithm (active contour model) to refine the contours further and correct theartifacts shown in Figure 3.16. The snake algorithm autonomously evolvescontour from a sequence of key points (also called snxels) once they are des-ignated. The snake energy formulation automatically maintains the contoursmoothness. The algorithm is designed to be initialized by user input orautomatic algorithms[93, 96, 109–111]. We employ automatic algorithms(the aforementioned registration and the SDF check) for initialization. Thekey points derived from the SDF check are directly used as snaxels, whichrelieves the user from the tedious and repetitive work of selecting snaxelsaround the dentition area for each mandible.We propose a slightly modified version of the snake movement algorithmfrom Jung and Kim [96] by using geodesic distance. They adopt a greedyoptimization method using dynamic programming (see Algorithm 2 in Ap-pendix A), which is known for its simplicity and fast computation time. Asnaxel is moved to one of its neighbor vertices at a time. The contours arenaturally guaranteed to remain on the 3D surface. The assumption holds ingeneral: the snake energy can be written as the sum of each snaxel’s energy.The energy minimization is realized by a multi-stage decision process thatrepositions each snaxel to the best position within a neighborhood.We make a small change on the internal energy, Eint, in Algorithm 2and use a different external energy, Eext, from Jung and Kim’s work. Eintis defined as:Eint(vi) =12(α‖vi − vi−1‖2) + 12(β‖vi+1 − 2vi + vi−1‖2)The first term controls the distances between snaxels. Our snakes progresson surfaces rich in features in between snaxels, so it is appropriate to usethe geodesic distance, the sum of the shortest path edge length. Euclideandistance is usually used in snake algorithms to estimate the length of a46contour segment for efficiency[100, 112], but it ignores the shape of theobject and does not function well for our purpose. Figure 3.17 comparesusing geodesic distance to using Euclidean distance. Green-colored pointsare used in our figures to represent the updated key points (snaxels) afterrunning the snake algorithm. Given two snaxel vertices vi and vi+1, weiterate over vi+1’s one-ring neighbors, which include vi+1,1 and vi+1,2, to seeif there is a vertex closer to vi than vi+1. Visually observing the situation, wecan tell that vi+1 should move to vi+1,2. However, in terms of the Euclideandistance to vi, vi+1,1 and vi+1,2 are similar candidates, both being closerto vi than vi+1. It is easy to see that vi+1,2 is a better choice when thetwo vertices are considered in terms of geodesic distance. In Figure 3.17(b)and (c), some of the key points derived from the SDF check (blue points)are around the tooth interstices. For the reasons stated above, Euclideandistance can raise the key point positions, whereas geodesic distance canguide them below the tooth interstices.To speed up the computation, we implement a parallelized Dijkstra’salgorithm and use a min-heap to calculate the geodesic distance[113]. InTable C.2 in Appendix C, we compare the algorithm running time on alaptop with four cores to a desktop computer with eight cores. It showsan amount of reduction in the total contour refinement time due to parallelprogramming.The second term of the internal energy function controls the contourcurvature at each snaxel[96]. The parameters α and β affect the smoothnessof the snake in terms of distance and curvature. We set them as α = 0.1,β = 0.2.Mesh curvature is a commonly used feature in snake’s external energyEext. The purpose of the external energy is to guide the snake to desiredfeatures on the mesh. We use mesh curvature to attract contours to theconcave area, conforming to the minima rule. The tooth crown contour areais often obscure on mandibular meshes derived from CT scans. Withoutmore high-level interpretations of the geometry, we let mesh concavity playa dominant role in deciding the contour position. A simple normal curvature-based estimation is employed: given the normal ni at a snake vertex vi with47Figure 3.17: Geodesic distance and Euclidean distance for contour refine-ment. Green points: updated key points (snaxels) after running the snakealgorithm. Red triangles: tooth interstices. (a) Geodesic distance and Eu-clidean distance between snaxel vertices v1 and v2. (b) Snake algorithmusing Euclidean distance. The snaxels are moved above the tooth inter-stices. (c) Snake algorithm using geodesic distance. The snaxels are movedbelow the tooth interstices.position pi, for each neighbor vertex vneighbor with the normal nneighbor andthe position pneighbor, the curvature in the direction of the edge between viand vneighbor is estimated as[114]:Curvature =(nneighbor − ni) · (pneighbor − pi)|pneighbor − pi|2Then we find the minimum value among all neighbors of vi.The parameters we used can be applied to target surface meshes that areof similar mesh quality as our data set. If the surface mesh is much noisier,using concavity as the desired feature would be less reliable. Smoothing thesurface before applying the preprocessing algorithm or increasing the weightson the internal energy can help boost our algorithm performance. The snakealgorithm iterates 5 times for each contour. The number of iterations is48related to the size of the search window centered on each snaxel (the ringsof snaxel neighbors the iteration can reach). We choose the number takingthe mesh resolution into consideration.Figure 3.18: The snake algorithm refines the key point position by movingthem to more concave areas in their vicinity. Green points: updated keypoints (snaxels) after running the snake algorithm. (d)-(f) show the snakecontours on our models. Blue contours: the initial snake contours, geodesicpaths between key points derived from SDF check. Green contours: snakecontours after energy minimization. (b)(c) The smoothing effect of the snakealgorithm fixes the artifacts shown in Figure 3.16 (a) and (b).In summary, our snake algorithm refines the contours by smoothing themand attracting them to concave areas in the vicinity (see Figure 3.18 and3.19). Due to the smoothing effect of snake, some of the artifacts introducedby the suboptimal performance of SDF value check (shown in Figure 3.16)are also ameliorated. The greedy optimization method is fast in updatingthe snaxel positions but, in principle, is likely to produce contours whoseenergy is not a local minimum. In practice, the problem is not critical. Forthis matter, and in case the user disagrees with the algorithm on the best49Figure 3.19: The snake algorithm results. The black arrows point at theareas that need modification after registration (same as the ones shown inFigure 3.7). The snake algorithm further improves the key point positioningfor both models. The blue arrow at the bottom of the left figure points ata previous artifact introduced by SDF value check, which is fixed by thesmoothing effect of the snake algorithm.place to segment teeth from, we provide functionalities in the ArtiSynthinterface to allow user intervention on the contour positioning, which willbe introduced in Section 3.3.1.Gaussian Local DeformationWe explored several ways of introducing user intervention and conductingtooth removal utilizing the snake algorithm’s outcome. Because our snakecontours are made of mesh vertices, the contours may appear jagged depend-ing on the mesh resolution. Directly segmenting the mesh from the snakecontours often results in jagged cut surfaces. Most importantly, watertightoutputs cannot be guaranteed when the contours cross a hole on the mesh.Topology issues like this are difficult to resolve. To overcome these limita-tions, we employ the CSG operation using the contour template. The toothcrown contours themselves are non-intersecting closed simple curves withoutsharp corners, which can be estimated using the smoothly deformed contourtemplate that fits the updated key points/snaxels. So we approximate thesnake contours using the intersection contours between the deformed contourtemplate and the target model.A local deformation based on Gaussian interpolation (see Algorithm 1)50Algorithm 1 Local deformation based on Gaussian interpolation.vi: i-th key point.n: the number of key points.r: the preset radius of the control range.D(vi): the domain of the contour template vertices whose distances to viare smaller than the radius r.δ: the position difference in z-direction between vi and its the nearestvertex in D(vi).pari: the Gaussian parameter for the nearest vertex to vi in D(vi), calcu-lated using the distance between them.for each key point i = 0 to n doFind all the vertices that form the domain D(vi);Calculate δ;Calculate parifor each vertex vij ∈ D(vi) doCalculate parij , the Gaussian parameter for the distance between vijand vivij .z +=parijpari· δ;end forend foris adopted to allow the contour template to pass through all key point po-sitions. The main idea is that each key point is in charge of the positioningof a group of contour template vertices in its neighborhood. The standarddeviation of the Gaussian function is set to be 10 mm based on the averagedistance between adjacent key points. The closer a vertex is to a key pointby Euclidean distance, the more it is affected by the key point’s positionchange in the z-direction. In this way, the contour template is deformed andfitted to the key points. And the contours are repositioned.Local deformation is the final step of the preprocessing algorithm, which,combining with CSG operations and smoothing, can form an automatictooth removal method. Comparing to the initial contours in Figure 3.7,Figure 3.20 shows that the preprocessing algorithm improved the contourpositioning for both models.51Figure 3.20: Fitting the contour template to the key points (snaxels) usinglocal deformation. Red contours: final results of the preprocessing algo-rithm, formed by the locally deformed contour template. Cyan wireframe:the locally deformed contour template. The black arrows point to the areasthat need modification after registration. The contour refinement algorithmimproved the key point positioning for a model with well-defined dentitionarea (left) and a model with limited surface features (right).3.2.4 Computational ComplexityWe used a 2.7 GHz Dual-Core Intel Core i5, 8 GB 1867 MHz DDR3 laptopto run the preprocessing algorithm. The laptop functions as four processorswith hyperthreading. The GMM-FEM registration converges on averagewithin 10 seconds (see Table 5.2). The snake algorithm using Dijkstra’salgorithm dominates the running time of the contour refinement algorithmwith the complexity of O(E log V ), V is the number of vertices in the mesh,E is the number of edges.3.2.5 DiscussionIn Figure 3.21, we visualize the results of each step of the preprocessingalgorithm using two models with well-defined tooth crown contour areas.The figure illustrates the key point positions after registration (red points),after checking SDF (blue points), and after running the snake algorithm(green points). Based on our observations of the tooth crown contours inSection 3.1, the key points approach the ground-truth position more andmore in each step in these two examples. The algorithm-generated contoursare consistent with the natural alveolar process position.52Figure 3.21: The preprocessing algorithm result visualization. Cyan wire-frame: the contour template deformed by registration. Red contours: theresults of the whole contour refinement process.However, when handling mandible models in various shapes, we haveseen occasional artifacts occur. There are undesired curves that neither theSDF value check nor the snake algorithm can effectively remove (such as theextra contours for absent teeth and the contours on the internal geometry,see Figure 3.22). At times, the artifacts are introduced by the preprocessingalgorithm itself. Every so often, high-level interpretations of the bone ge-ometry are needed to draw a conclusion. Therefore, we recommend havingusers in the loop for a refined segmentation.In summary, the proposed preprocessing algorithm is simple, fast, androbust. We use an off-the-shelf non-rigid registration method to find theinitial tooth crown contours and refine them by checking the SDF value andevolving the active contours on the 3D surface using geodesic distance. Our53Figure 3.22: Contour artifacts. (a)Extra contours (b)Contours on the inter-nal geometry. (b) is the difference mesh between the target model and thecontour template in (a).target mandibular meshes are within the resolution of 10-20k vertices. Formodels out of this range, the proposed algorithm could use some parametertuning to ensure its optimal functioning. The algorithm (and our contourediting tool) can be used for individual model processing. The preprocessingalgorithm can also handle a set of models in one batch, running offline andsparing the users from waiting.3.3 Interactive Tooth RemovalWe would like to present the algorithm-generated tooth crown contours toresearchers for inspection. Our target users are researchers at the hospitaland from medical imaging labs who have sufficient knowledge of mandibleanatomy and are experienced with manipulating objects in 3D software.In this section, we introduce the functions we developed and added tothe ArtiSynth interface to support fine-to-coarse scale user interaction withthe contours using control points. In addition, we describe tooth removalusing a CSG operation and postprocessing.543.3.1 User Interface for Contour EditingFigure 3.23: The user interface embedded in ArtiSynth. One control pointin selected (highlighted in yellow) in the main viewer. A transparent spherewith a radius of 17.0243 mm is rendered around the control point to showits control range.We design our user interaction taking advantage of the local functional-ities in the ArtiSynth interface. The ArtiSynth interface provides multipletools, e.g., toolbars and keyboard shortcuts, for object selection and transfor-mation, which will be utilized by our users to achieve contour modification.Our design is mainly based on Blender, a 3D computer graphics software.We adapt some of Blender’s interface and function design to our task athand.To adjust the position for tooth removal, our users interact with the55contours using control points. About 50 points are evenly placed on theintersection contours. They are displayed to the user and utilized as controlpoints for locally deforming the contour template. The users are free todeform the contour template in their preferred scale and extent, thus chang-ing the intersection contours. The interface contains a main viewer and acontrol panel (see Figure 3.23). The main viewer visualizes the whole toothsegmentation process. The control panel includes the following items:• Messages text area: Information regarding the proprocessing al-gorithm and contour editing are displayed here to offer guidance tousers.• Progress bar: It shows the iteration progress of the snake algorithm.• “Remove teeth” and ”Smooth the cut area” checkboxes: When”Remove teeth” is checked, the CSG operation is applied. The mainviewer will show the model without the dentition. The users cansmooth the cutting area and save the edentulous model from the drop-down menu in ”Application” in the main viewer. When the users workin the ArtiSynth interface, they may check the edentulous model usingthese functions multiple times to decide whether to export the modelor go back for more contour editing.• ”Select all” and ”Reassign points” buttons: ”Select all” high-lights all the control points and enables translation of the whole con-tour template along the z-axis. ”Reassign points” deletes the existingcontrol points and assigns new ones evenly along all contours. This isuseful when the control points are moved out of the place (e.g., insidethe mandible body or far from the contour) and become difficult toselect.• ”controlRadius”: Control points are the tools for locally modify-ing vertex positions in the contour template. Figure 3.23 shows thetype of user interaction when one control point is selected. Gaussian-interpolation-based local deformation is also employed here. A trans-56parent sphere is rendered around the selected point to show the con-trol range. We set that the sphere radius can only be tuned by wheelscrolling, similar to the proportional editing function in Blender. Thegranularity of radius adjustment by wheel scrolling should be able tomeet the users’ need for fine-tuning the contours. The exact figureof the radius is displayed in the uneditable ”controlRadius” textboxin the control panel. The control point can affect the vertices of thecontour template lying within the sphere. Using the ”select and trans-late components” tool in the ArtiSynth interface, the user can changethe control point positions and thereby deform the contour template.To control a more extensive range on the contour template, users caneither set a larger control radius for one selected control point or si-multaneously select and translate multiple control points.• “One-sided control” and “Clip on to the surface”: These func-tions are customized for our task of contour template modification.When one control point is selected, and the control range is large,the sphere can cover both the anterior and the posterior sides of themandible. The contours on both sides will be deformed at the sametime, which may not always be what the user wants. We offer theoption of editing one side of the contour without changing the otherside. This is realized based on the mandible geometry. We observethat, given two vertices that are close to each other around the toothcrown contour, the angle between their normals tends to be small whenthey are on the same side of a mandible. When they are on differentsides, their normal directions are opposite to each other. So when the”One-sided control” checkbox is ticked, we let the algorithm decidewhether a vertex should be translated by checking the angle betweenthe vertex normal and the normal of the nearest vertex to the controlpoint.The “Clip on to the surface” checkbox can restrain the selected controlpoints to move along the surface of the target mesh. This is achievedby constantly projecting the control points back to the mandibular57mesh surface while it is being translated.We demonstrate the major user interaction options in a video made forour SPIE conference submission [1] and summarized detailed operations inArtiSynth in Appendix B.3.3.2 Dentition Area RemovalFigure 3.24: Tooth removal using CSG operator and cut area smoothingSegmenting the teeth directly using active contours often raises criticaltopology issues. So we employ the CSG operator in ArtiSynth to conducttooth removal, which can guarantee that the mesh output is a closed mani-fold. We compute the difference mesh between the contour template and thetarget mesh (The face normals of the contour template are set towards theinferior mandible, the negative z-direction). The difference mesh is the eden-tulous model of the target mandible (see Figure 3.24(b)). The triangulationof the cut surface is the same as the respective area on the contour template.The CSG operator also triangulates the faces along the intersection contourswith more than 3 vertices.For tooth removal, the only criterion of the CSG operator is that thecontour template and the target model should form closed intersection con-tours. Using our manually modified contour template, this criterion is easilysatisfied. In the very rare cases where the contours are open, the users canfix it with a few clicks using the control points in the ArtiSynth interface(see an example in Figure 3.25).58Figure 3.25: An open intersection contour between the contour template andthe target. (a)(b) show the open contour from different angle. (c) shows theartifact fixed by dragging a nearby control point in the negative y-direction.We apply smoothing to the tooth removal surface as a postprocessingstep. Because of the cut, the difference mesh contains sharp edges along thecontour lines. The sudden cut-off is untrue to natural mandible anatomy.The discontinuous change of the normal direction may cause issues whenfeeding the model to other VSP algorithms. So a smooth tooth removalsurface is preferred over an abrupt flat cut. In the last step of the workflowshown in Figure 3.1, we apply two iterations of Laplacian smoothing to thetooth removal surface (see Figure 3.24(c)). Laplacian smoothing relocateseach vertex on the surface to its one-ring neighbors’ average position.3.3.3 DiscussionOur proposed contour editing tool for tooth segmentation from mandibularmeshes is simple and suitable for real-time user interaction. We strive tomake the user interaction design intuitive and consistent with the functionsin 3D computer graphics software like Blender, 3ds Max, Maya, etc. Thecontrol-point-based deformation is very similar to the proportional editingfunction in Blender or the soft selection function in 3ds Max and Maya.Wheel scrolling is also used to tune the control radius in Blender. “One-sidedcontrol” and “Clip on to the surface” are functions we designed specificallybased on the mandible and contour template geometry. These functionscan also be achieved with more operation steps in general 3D modeling59software. By combining several operations into a panel item and adaptingthem for our task, we form the interface design for the convenience of ourusers. For users having experience modeling 3D objects, there should be nodifficulty manipulating the control points and the intersection contours inthe proposed interface.Although our preprocessing algorithm and contour editing tool are de-signed for tooth segmentation, it can be investigated in the future that theentire method can be more general. The method can be applied to differentanatomical structures and even other types of objects, such as tooth removalfor maxilla and general 3D object segmentation. The users would need toprepare a set of object templates and contour templates suitable for theirsegmentation purposes. According to the local geometry around the con-tour on the object, the iteration conditions for SDF value check may needto change. Our snake algorithm can direct the contours to concave areas.Alternatively, the user may want to modify the external energy of the snaketo attract the contours to other features. In the end, artifacts can be fixedusing our contour editing tool. As a 3D mesh segmentation tool, our methodcould be added to mesh editing software such as MeshLab, Meshmixer, andthe ones we mentioned previously.In the context of clinical research for mandible reconstruction, our seg-mentation method aims at boosting the efficiency of conducting tooth re-moval. In the next chapter, we will evaluate the effectiveness of our method.60Chapter 4Comparing Our Mesh-BasedMethod with A Voxel-BasedMethod using 3D SlicerOur mesh-based tooth segmentation method uses a preprocessing algorithmto locate the tooth crown contours on mandibular meshes and user inter-vention to refine the contours before removing the teeth. For method evalu-ation, we would like to compare our tool with a voxel-based manual removalmethod using 3D Slicer. The performances are compared in terms of man-ual editing time, symmetric 95th percentile Hausdorff distance (HD95), andsymmetric root mean square deviation (RMSD).4.1 HypothesisFor the researchers, tooth removal can be conducted from the 3D meshes orthe CT scan data (which will also be exported as 3D meshes for later usage inVSP). Manual removal from 3D meshes can become very tedious and time-consuming because of the topology issues on the surface mesh. It usuallytakes less time to work on CT scans using voxel-based methods, but it is alsolaborious and repetitive. Figure 4.1 shows the tooth segmentation workflowsusing 3D Slicer and using our tool. They both first locate the tooth-boneboundaries and then remove the teeth. In 3D Slicer, these processes aremostly manual, whereas our tool offers guidance to facilitate them. Wewould like to test our tooth segmentation method and make a comparisonbetween the two workflows in Figure 4.1. Therefore, we hypothesize:61• Our mesh-based tooth segmentation method can help save time com-paring to the voxel-based tooth segmentation using 3D Slicer.Figure 4.1: Tooth segmentation workflows4.2 Input DataThe mandible models we use are from two sources:1. Training set: 5 healthy mandibular meshes with teeth, segmentedfrom Head-Neck-PET-CT data set[19]. The set is used for partici-pant training, which involves familiarization with the proposed userinterface and practice exercises.2. Test set: 48 healthy mandible models with teeth from VGH. Themodels are from emergency room patients with conditions unrelated62to the mandible. The set includes mandibular CT data (that areseparated from head and neck scans) and the 3D meshes exportedfrom the CT data. It is used in our tool testing study.4.3 Experiment SetupFollowing the workflow in Figure 4.1 (a), we invite a voxel-based toothsegmentation expert from our team to conduct tooth removal for the testset using 3D Slicer. The expert is a biomedical engineering student withthe necessary training from a dentist and sufficient practice time. The ex-pert identifies the tooth-bone boundaries and removes the dentition areafor all 48 mandibular CT scans. The edentulous results are exported as 3Dmeshes, which form our manual removal reference data set (Group M). Thetime spent on each model (examining the model and removing the teeth)is recorded. Our dentist evaluates all the tooth removal results and offerscorrection opinions. Adjustments are made for 5 models accordingly. Fig-ure 4.2 shows the 3D Slicer interface for conducting tooth removal and anexample in our manual reference data set.To estimate the variability in the reference data set, we test the repeata-bility of the voxel-based segmentation expert’s segmentation. The expertconducts an additional round of manual segmentation (Group M) for 10randomly selected models out of the 48 without referring to the previouswork. Between the tooth removal surfaces of these two rounds (M-M),an image Intra-Class Correlation Coefficient (I2C2) [115] of nearly 1.0 isachieved, showing a very reliable performance. By comparing surface dis-tance between the two rounds (symmetric HD95 and symmetric RMSD), wealso gain a sense of how much good tooth segmentation results can differfor the same mandible model. The difference can serve as a reference forcomparison between different segmentation results for one model.Our main study follows the workflow in Figure 4.1 (b). The 3D meshes inthe two data sets are used. The setup involves running the preprocessing al-gorithm and generating the tooth crown contours for all models offline (priorto running the interface testing sessions with participants). We also save the63Figure 4.2: Voxel-based manual tooth segmentation using 3D Slicer. (a)3D Slicer interface. Researchers use fiducial points to mark the tooth-boneboundaries. Teeth are removed using tools such as ”Erase” and ”Scissors”.(b) The dentulous mandibular mesh. (c) The manual tooth removal resultprocessed by our expert. (d) The edentulous model in (c) is highlighted inred.edentulous models directly resulted from the automatically generated con-tours (Group A). After running the main study, we would like to comparethe edentulous models before and after the participant’s modifications.644.4 Pilot Studies and the Main StudyThe proposed tooth segmentation tool is debugged by running informal pilotstudies in the early stage. (These studies do not require ethical approval.) Intotal, we conduct seven virtual and in-person tests with electrical engineer-ing and computer science students at University of British Columbia (UBC).They have different levels of experience with 3D modeling software, rangingfrom having never used one before (two participants) to mastering several ofthem (three participants). Two participants have backgrounds in anatomy(one of them is both a UBC student and a research assistant at VGH work-ing on a mandible-related project). The virtual test participants becomefamiliarized with the functionalities of our interface. The in-person testparticipants all become proficient in using our contour editing tool within ashort training period.For the main study using the workflow in Figure 4.1 (b), our participantis a research assistant (mesh-based segmentation expert) from our team atVGH, who is well-experienced in tooth removal using different modalitiesof data. Our two experts have similar backgrounds in terms of their un-derstanding of the mandible anatomy and their familiarity with using 3Dsoftware. The participant first receives a training session through Zoomusing the training set, then inspects the 48 tooth crown contour resultsof the preprocessing algorithm, makes modifications, and saves the eden-tulous models (Group P). The time spent on each model (examining thealgorithm-generated contours, editing them, and applying smoothing) isrecorded. (Both of the two experts process the models following the modelsequence number.) The participant (mesh-based segmentation expert) isfree to take breaks after finishing segmentation for each mesh (each meshtook about 1-2 minutes). The whole test approximately takes 3.5 - 4 hours.4.5 Results and Data AnalysisThe results of the study are described in detail in Appendix C. We show thevoxel-based manual processing time using 3D Slicer (M)(M = 177, SD =6551.72) and using the proposed mesh-based tool (excluding the preprocess-ing time) (P)(M = 106, SD = 84.56) to process the test set in Figure4.3. The time for each of the 48 models is illustrated in Figure 4.4. Thedata is not normally distributed (from the results of the normality tests(theKolmogorov-Smirnov and Shapiro-Wilk tests)). In total, our voxel-basedsegmentation expert uses 141.52 minutes to process the test set. The mesh-based segmentation expert uses 85.12 minutes. Our segmentation methodreduces the manual processing time by 40%. It is evident both in Figure 4.3and in our non-parametric Mann–Whitney U test result (U = 400, p < .001)that tooth segmentation using our tool is significantly faster than the voxel-based method. With 31% of the test set data, less than 1 minute is spentin the proposed interface, including 10-15 seconds to examine the modelaround. With 87.5% of the data, the mesh-based segmentation expertspends less time in our interface than the voxel-based segmentation expertin 3D Slicer. Also, with 87.5% of the data, less than 3 minutes is spent inour interface. (The mean manual processing time using 3D Slicer is approx-imately 3 minutes.) The amount of user input involved in our method issmall, which indicates that the preprocessing algorithm is effective in guidingand assisting tooth segmentation.Figure 4.3: The manual processing time in the voxel-based method using3D Slicer (M) and in the proposed mesh-based method (excluding the pre-processing time)(P).We also notice that the manual processing time costs using both methodshave large standard deviation values. The proposed method has a standarddeviation of 85 seconds (51 seconds for the voxel-based method in 3D Slicer).66Figure 4.4: Manual processing time for each mandible model.In addition, Figure 4.4 shows interesting results. Most of the time, the ex-pert of the proposed mesh-based method spends much less time than theother expert using the voxel-based method. We can infer that the algorithm-generated contours from the preprocessing step help reduce the human effortin tooth segmentation. For three or four models, the time costs are similarin both methods. Then, there are four cases (No.1, 8, 26, 30) when themesh-based segmentation expert is more than 25% slower than the expertusing 3D Slicer. To better understand these cases, we check their cut areasurface distances (symmetric HD95 and symmetric RMSD) before and afterthe expert’s modification on the contours. Only one model out of the fourof them (in terms of both distances) is beyond one standard deviation fromthe mean distance (between the cut surfaces formed before and after theexpert’s input), meaning that the mesh-based segmentation expert did notuse the extra time on these models to make larger changes. For this mat-ter, the expert explains that adjusting the control points sometimes affectsother points around it unexpectedly. More efforts are needed to readjustother control points. Therefore, the processing time is prolonged. This fac-tor reveals a shortcoming of the designed tool. It also implied that the timecost could be further decreased by improving the usability of the interface.In addition, the way our user interaction is designed may also contributeto longer manual editing time. Thu users are able to conduct contour ad-justments at different scales. So they may tend to spend more time makingchanges.67Besides efficiency, we compare the surface distances using symmetric95th percentile Hausdorff distance (HD95) and symmetric root mean squaredeviation (RMSD)[116, 117]. We extract the cut surfaces for the surfacedistance computation and make three groups of comparison. Table 4.1 andFigure 4.5 display the computation results comparing the proposed segmen-tation method (with user input from a mesh-based segmentation expert) tomanual removal using 3D Slicer (P-M) for the 48 models, the manual re-moval using 3D Slicer to automatic segmentation for the 48 models(M-A),the proposed method to automatic segmentation (segmentation based onthe contours generated by the preprocessing algorithm) for the 48 models(P-A), and between the two rounds of manual segmentation of 10 models(M-M). The P-M surface distances reveal the difference between our twoexperts’ tooth removal. The M-A distances show how much the voxel-basedsegmentation expert disagrees with the tooth removal position computed bythe preprocessing algorithm. The P-A distances show the amount of changethe mesh-based segmentation expert makes to the computed contours. TheM-M distances serve as a comparison reference in this table. The 10 segmen-tation results from both rounds are qualified tooth removal conducted by thesame expert. On average, the cut surfaces differ by 0.80 mm (SD = 0.92)in symmetric HD95 and 0.51 mm (SD = 0.40) in symmetric RMSD.In contrast, the cut surfaces from the proposed segmentation method(conducted by the mesh-based segmentation expert) and the manual seg-mentation (conducted by the voxel-based segmentation expert) (P-M) haverelatively large symmetric HD95 and symmetric RMSD. The M-A group hassimilar distance values to the P-M group. The two outlier values in sym-metric HD95 from both groups are from the same two mandible models. Onthe one hand, the automatically identified contours sometimes deviate fromthe ones identified by the experts. The algorithm is limited in its contouridentification ability to some extent. On the other hand, the outliers shownin Figure 4.5 are most likely due to disagreement between our two expertson the bone level location. Such ambiguity exists in both manual removaland the proposed segmentation method, especially when the geometric fea-tures around the tooth crown are obscure or when the mandibular bone68Table 4.1: Distance comparison between the cut surfaces from 4 groups:P-M: the proposed mesh-based method and the voxel-based manual removalusing 3D Slicer. P-A: the proposed mesh-based method and automatic seg-mentation (based on the contours generated by the preprocessing algorithm).M-A: the voxel-based manual removal using 3D Slicer and automatic seg-mentation. M-M: between two rounds of voxel-based manual removal in 3DSlicer for 10 models.Symmetric HD95 Symmetric RMSDMean (mm) SD (mm) Mean (mm) SD (mm)P-M 2.41 1.07 1.18 0.57M-A 2.71 1.27 1.32 0.67P-A 1.33 0.84 0.61 0.35M-M 0.80 0.92 0.51 0.40Figure 4.5: Distance comparison between the cut surfaces from 4 groups.surrounding the tooth roots is thin. On such occasions, the tooth removalperformance may depend on the person conducting the segmentation. Thebest segmentation position and the accuracy required also depend on howthe mandible model in question will be later utilized in clinical research.69As for comparing the proposed segmentation before and after user inter-vention (P-A), the cut surfaces differ slightly. Specifically, they have a veryclose mean and SD symmetric RMSD value (0.61 mm and 0.35 mm) to thebaseline group (0.52 mm and 0.40 mm), which once again confirms that themesh-based segmentation expert is mostly satisfied with the automaticallygenerated contour, only making minor alterations.4.6 An Additional StudyAlthough the two experts in our experiment have similar backgrounds in us-ing 3D tools, personal difference may still exist and affect the tooth removalperformance. So we conduct an additional study to test their speeds in usingthe other segmentation tool, the tool that they are less familiar with thanthe one they used in the main study. 7 models are randomly selected outof the 48 in the test set for this study. We use 2 of them for training and 5of them for testing. (The mesh-based segmentation expert is familiar with3D Slicer. So the 2 training models are used as warm-up exercises. Thevoxel-based segmentation expert learns and practices functions in our toolusing the 2 training models.) There is a time interval of 8 months betweenthis study and the main study, so the learning effect of the 5 models is neg-ligible. The results of manual editing time comparing to the time used forthe 5 models in the main study are shown in Figure 4.6.Figure 4.6: The manual editing time spent by the two experts in the addi-tional study and in the main study for 5 randomly selected models.70The mesh-based segmentation expert spends 66 seconds on average foreach of the 5 models using our tool in the main study (the average speed inthe main study is 106 s/model), 241 s/model using 3D Slicer in this study.The voxel-based segmentation expert spends 145 s/model using our tool inthis study, 174 s/model using 3D Slicer in the main study (the average speedin the main study is 177 s/model). These speeds can serve as a referencefor the comparison in the main study. The mesh-based segmentation expertis slower than the voxel-based segmentation expert in terms of using 3DSlicer, and vice versa. There is a speed difference between the two experts.The mesh-based segmentation expert benefits more from using our tool thanthe other expert. However, both experts spent less time using our tool thanusing 3D Slicer, proving that our method is effective in facilitating the toothremoval process.4.7 DiscussionOur work aims to facilitate the tooth removal process in the current clinicalresearch, thus assisting VSP for oral reconstructive surgeries. The studyshows achievements made towards this goal and reveals future work poten-tials. The tooth crown contours computed by the preprocessing algorithmserve as a good starting point for the user to find the best tooth segmen-tation positions. Our study shows that our snake-based method can helpexpedite the tooth removal process. Using the proposed tool is faster than3D Slicer for 87.5% of the data. For the rest 12.5% of the data, the usabilityissue is more prominent, making the segmentation performance suffer. Sowe suggest a tooth segmentation strategy for proficient users to take advan-tage of both tools (see Figure 4.7). The majority of the data are suitablefor processing by our tool, while the user may want to switch back to 3DSlicer for a few models when the automatically generated contours appeartoo curvy or the deformed contour template has a complex topology. In thisway, the tooth removal efficiency can be maximized.As aforementioned, the required tooth segmentation accuracy dependsupon the usage of the mandible model. For example, the requirement would71Figure 4.7: Tooth segmentation strategy.be high when planning the surgery for an individual patient. The researchassistants may need the flexibility to control the boundary around each toothof interest, considering its intermaxillary relationship in the jaw reconstruc-tion. However, the standard can be more lenient if tooth removal is neededfor a mandibular data set, e.g., data sets for training VSP algorithms suchas the one shown in Chapter 5.Given that VSP for oral reconstruction mainly uses 3D meshes, the pro-posed mesh editing tool can conveniently integrate into the workflow of thecurrent clinical research. Our interface offers a combination of functionalitiessimilar to the current state-of-art computer graphic software and customizedto the mandible geometry, which is easy to grasp and maneuver in general.The benefit would be more prominent with better usability of the tool.Moreover, we have some interesting findings on user experience from run-ning the pilot studies and the main study, which are valuable for improvingthe interface. We notice that the participants share a few preferences withthe functions provided in ArtiSynth. The majority of them seldom changethe control radius when having one control point selected. More attention ispaid to which point to select and how to translate it than its control range.72Our reasoning for this is two-fold. First, although wheel scrolling for radiuschange is widely used in 3D graphics software and easy to remember, it isstill a slight stretch from the most common mouse operations. Users mayhave to go through a learning curve getting used to it. Second, other moreintuitive methods are adopted to achieve similar control in our interface.To modify a large range of contour, the users usually chose to select mul-tiple points instead of dialing up the control radius for one point. Wheelscrolling is mostly used for editing a small range of the contour, which is arare situation in our experiments.Additionally, a few participants mentioned the inconvenience that theysometimes could not find a control point near enough to the small curvesthey wanted to fix. This is because the control points are placed evenly onthe contours, regardless of the contour features. Usually, the small fluctua-tions between two adjacent control points can be removed in later cut areasmoothing (see Figure 4.8). It may not require any action from the usersto resolve them. Nonetheless, this issue can be alleviated by us adopting acontrol point insertion strategy that is based on the contour features.Figure 4.8: Jagged cut surface caused by small fluctuations of the contouris largely resolved after surface smoothing. (a) A small curvy area betweentwo control points on the contour. (b) The cut surface appears jagged afterCSG tooth removal. (c) After surface smoothing, the effect of the smallcontour fluctuation is largely removed.To address the insights from our participants, more efforts are needed toenhance and polish the usability design of the proposed tool.73Chapter 5Edentulous Models for VSPWe want to evaluate the impact of edentulous models on a statistical-shape-modeling-based VSP algorithm for mandible reconstruction. We utilizeedentulous meshes processed by our automatic segmentation (tooth removalbased on the automatically generated contours) as part of the experiment’sinput.5.1 IntroductionFor VSP in mandibular reconstruction, a prior premorbid CT scan is themost reliable reference, but it is often not available. Researchers have toseek other modeling techniques in its absence. Wang et al. use statisticalshape models (SSMs) to predict the original mandibular shape[2]. Theycreate defects for healthy mandible models and train SSMs to generate defectreplacement geometries. Their results show encouraging accuracy. However,the performance of SSM approaches depends on the size and quality of thedata set and the quality of the mapping to the target diseased models. Ourtooth segmentation method is able to help improve the data quality.In theory, an edentulous data set is of better quality than a set ofmandibles with mixed dentition conditions. Previous works suggest thatthe presence of teeth causes errors for bony shape completion algorithmstraining on healthy mandible models[7, 8]. The mixed dentition conditionin the training samples increases the variance of the data set. Algorithmsusually do not differentiate the teeth from the mandibular bone. So theyrecognize larger vertical mandibular bone heights on dentulous models thanon edentulous models. The dentition also interferes with result evaluation,affecting the calculation of the volume overlap between the original segment74and the segment generated by the algorithm (defect replacement). In thisstudy, we would like to gain more understanding and more concrete proofof this issue.5.2 HypothesisTo quantify the impact of teeth, we run the shape completion study de-scribed in [2] using edentulous models and compare our accuracy resultswith their original results. We hypothesize that• The shape completion algorithm conducted in [2] will perform bet-ter using edentulous mandible data sets than data sets with mixeddentition conditions.5.3 Input DataThe original data set used by Wang et al. comprises 84 mandibular meshes(no overlap with the 48 models in the first study). 31 of them are manuallysegmented from CT scans of nononcologic patients in the otolaryngologyoutpatient clinic from VGH. The rest of the 53 models are segmented fromopen data sets[16–18]. They have all been manually edited to remove theinternal geometry, ensured to be watertight, decimated to 10-20k vertices,and saved in STL format. Out of all the meshes:1. 28 models have all or part of their dentitions. To create the edentu-lous data set, we conduct tooth removal for them using our automaticsegmentation method (preprocessing algorithms, CSG operation fortooth removal, and Laplacian smoothing).2. 56 models are edentulous. They are used in our study without anyprocessing.75Figure 5.1: The workflow of a SSM-based shape completion algorithm [2]5.4 Experimental Design and MeasurementFigure 5.1 shows the workflow of the shape completion study conducted byWang et al.. We use edentulous models as the input in our study. The GIAS2Shape Modeling package[36] is adopted to generate SSMs and conduct reg-istration. Wang et al. specify 7 sets of virtual cutting planes to create the7 classes of mandibular defects in the Brown classification[118](see Figure5.2). To be specific, an individual set of planes are manually defined foreach defect class to remove a certain part of the mandible. The leave-one-out approach is adopted to create one SSM for each model (the SSM iscomputed from all mandibles in the data set except the one being tested).To predict the premorbid bone shape virtually, the SSM deforms to fit the 7target models with defects through registration. Finally, the defect replace-ment models are extracted by applying the respective cutting planes to thedeformed SSMs. The mandibular defects are corrected with the generateddefect replacements.To assess the quality of the generated geometries, Wang et al. com-pare them with the cut-out segments from the original mandibles using twomeasurements, symmetric 95th percentile Hausdorff distance (HD95) andvolumetric dice coefficient (DSC). So we also use these two measurements.76Figure 5.2: 7 classes of mandibular defects.5.5 Results and Data AnalysisFor all 7 classes of defects, the results of the original study (WT) are sum-marized in Table 5.1. The results tested on the edentulous models (NT) aredisplayed in Table 5.2. We compare between Group NT and Group WT for7 classes of mandibular defects in Figure 5.3 and Figure 5.4.Table 5.1: Symmetric HD95 and DSC for all 7 classes of defects in theoriginal study (WT)Symmetric HD95 DSCDefect Mean (mm) SD (mm) Mean (%) SD (%)I 2.66 1.28 84.80 5.59Ic 4.91 2.80 65.96 13.78II 3.21 1.82 82.68 7.07IIc 5.70 3.23 64.36 16.05III 3.88 2.46 80.03 10.19IV 6.43 3.16 71.14 14.92IVc 12.93 21.40 54.22 22.86Ave 5.67 8.98 71.88 17.40Both the HD95 and the DSC values are not normally distributed. The77Table 5.2: Symmetric HD95 and DSC for all 7 classes of defects tested on84 mandibles without teeth (NT)Symmetric HD95 DSCDefect Mean (mm) SD (mm) Mean (%) SD (%)I 2.45 1.00 84.85 5.40Ic 5.20 2.28 62.42 14.43II 2.80 1.35 82.86 6.52IIc 5.98 2.83 61.23 15.04III 3.34 1.66 80.81 9.47IV 4.90 2.23 74.48 11.52IVc 6.14 2.62 58.05 16.67Ave 4.40 2.51 72.10 15.89class I, II, III, and IV defects are of smaller volume than class Ic, IIc, and IVc.With less information missing, the shape completion algorithm naturallyperforms better. Statistical test results also prove this. Wilcoxon SignedRank Test shows significant differences (p < 0.001) for symmetric HD95and DSC between class I and Ic defects and class II and IIc defects for bothGroup NT and Group WT. Between class IV and IVc defects, except forHD95 for Group WT, the rest of the comparison results show significantdifferences.Comparing Table 5.1 with Table 5.2 (Figure 5.3 with Figure 5.4), us-ing edentulous models for SSM creation produces better defect replacementshapes for class I, III, IV, and especially IVc. The teeth had less impacton class Ic, II, and IIc. Overall, training using edentulous models achievessmaller Standard Deviation (SD) values in terms of both HD95 and DSC.This is possibly due to the fact that the edentulous models have more consis-tent and similar appearances, which helps generate SSMs with better qualityand facilitates surface registration.The average results of all 7 defects are shown in Table 5.3 and Figure5.5. We attach the detailed experimental outcome regarding each of the 7defects for each model in Appendix D.78Figure 5.3: Symmetric HD95 comparison between Group NT and GroupWT for 7 classes of mandibular defects.Considering the overall averaged results, both the mean distance andthe standard deviation of group NT are better than group WT regardingthe two measurements. The two groups use the same set of 84 mandibles.Neither of their results follows the normal distribution. Hence, we useWilcoxon Signed Ranks Test, a non-parametric test, to assess the statis-tical hypothesis. In terms of HD95, the defect replacements generated us-ing edentulous models (NT) are found to be significantly better than thosegenerated using the unprocessed meshes with mixed dentition conditions79Figure 5.4: DSC comparison between Group NT and Group WT for 7 classesof mandibular defects.(WT) (Z = −2.484, p = 0.013). DSC results show no significant difference(Z = −0.563, p = 0.573).We observe that the outlier values are mainly from class IVc defect forboth groups, which is also shown in Figure 5.3 and Figure 5.4. For 38 casesfrom group WT with HD95 larger than the statistical higher range limit(10.33 mm), 17 of them are from class IVc defect. The boxplots in Figure5.5 reveal more insights into the data pattern. Group NT has much feweroutlier data with values much closer to the interquartile range than group80Table 5.3: Symmetric HD95 and DSC averaged across all 7 defects, testedon 84 mandibles without teeth (NT) and on the original 84 mandibles in thestudy of Wang et al. (WT)Symmetric HD95 DSCMean (mm) SD (mm) Mean (%) SD (%)NT 4.40 2.51 72.10 15.89WT 5.67 8.98 71.88 17.40Figure 5.5: Boxplots of symmetric HD95 and DSC results averaged acrossall 7 defects.WT. The large outlier values of HD95 (or the small DSC outlier valuesthat are close to zero) from group WT mean that the corresponding defectreplacement shapes are very different from the ground-truth missing shapes81of the mandibles (see an example in Figure 5.6). The shape completionalgorithm in the study tends to show more aberrant performances usingmodels with different dentition conditions. In comparison, the plots showincreased robustness of the algorithm training with the edentulous data sets.Figure 5.6: An unsuccessful shape completion result for a mandible withclass IVc defect (symmetric HD95: 105.99 mm, DSC 0.00). (a) The originalmandible and the plane to create the defect. (b) The SSM registrationmalfunctions possibly due to too much missing data in the defect. (c) Thereis zero overlap between the defect replacement and the original cut-out partof the mandible.5.6 DiscussionIn the current clinical research, the teeth are usually preserved for mandibu-lar meshes, which means that meshes with various dentition conditions areutilized in modeling and simulation. Our study confirms the positive im-pact of edentulous models on planning mandible reconstruction. Some defectclasses benefit more than others. The overall shape completion outcome isimproved, and the robustness of the algorithm increased.In addition, the study reflects the effectiveness of our preprocessing al-gorithm. We conduct tooth removal for the dentulous models based on the82algorithm-generated contours. Then Laplacian smoothing is applied. Thereis no user input, so the segmentation is relatively rough. The shape com-pletion results may be even better if a more refined segmentation with userintervention is adopted.In summary, tooth removal can enhance the quality of 3D mandibulardata sets. Tooth removal helps the SSM-based algorithm in our study per-form more robustly and generate shapes that better resemble the premorbidmandibular shapes. We believe these benefits can be shared by most VSPalgorithms that rely on data sets of healthy mandibles. It would be in-teresting to test the impact of dentition on other VSP algorithms and usea larger sample size in the future to draw further conclusions. Our studyprovides evidence that supports using edentulous mandibular models in theVSP workflow and helps pave the way for further studies.83Chapter 6ConclusionsTo facilitate VSP for oral rehabilitation, we tackle the efficiency issue oftooth segmentation from mandible models. Our solution includes a snake-based preprocessing algorithm that identifies tooth crown contours on targetmandibular meshes and a user interface that supports contour editing. Byidentifying the alveolar process position and segmenting the teeth, our workcan also assist bone graft placement planning to prepare for dental implants.6.1 Summary of Contributions• A boundary-based tooth segmentation method that improvesmanual editing efficiency: We propose a mesh segmentation method,including a preprocessing algorithm to compute the tooth crown con-tour on the target mandible model and user intervention. Our studyshows that, on average, the proposed method can improve the tradi-tional manual tooth removal efficiency by 40%. With the algorithm-generated contour guiding the tooth segmentation, 31% of the dataonly needs minor user adjustment, 87.5% of user intervention is fin-ished in less than 3 minutes.• An easy-to-use, interactive mesh editing tool targeted at toothremoval from mandibular meshes: We develop an interactive toolto support user intervention, allowing artifact fixing and fine-to-coarsescale adjustment on the algorithm-generated contours. The functionsin the interface are designed based on both the mandible geometryand the contour editing task. We provide detailed descriptions of theuser interaction design. Given that VSP for mandible reconstructive84surgeries often uses 3D meshes, the proposed mesh editing tool canseamlessly fit into the current clinical research workflow.• Proof of the advantage of using edentulous mandible modelsfor data-driven VSP algorithms: To test the impact of teeth onmodeling mandible reconstruction, we run the SSM-based shape com-pletion test in [2] using their 84 mandible models with teeth removed(we conduct tooth removal for the dentulous models based on theresults of the preprocessing algorithm). Compared to using the origi-nal data set with mixed dentition conditions, using edentulous modelsgenerates significantly better shapes for the osteotomized mandiblesregarding 95th percentile Hausdorff distance (Z=-2.484,p=0.01). Theshape completion algorithm performs more robustly. The study alsoreflects the effectiveness of the preprocessing algorithm.6.2 Limitation and Future WorkThere are several limitations in this thesis in terms of the input data, themethodology, and the evaluation study design. Our tooth segmentationsolution mainly targets healthy mandible models. It can be adapted to toothremoval from mandibular segments (by registering our mandible templateto the original mandible the segment comes from and having the algorithmcompute the intersection contours between the segment and the contourtemplate). It can also tolerate diseased mandibles with small defects (see thetooth removal result for a diseased model in Figure 6.1). With large defects,the registration process may become unstable due to too much missing data.To better assist clinical patients and boost the robustness of the algorithm,we would like to address challenges experimenting on models with differentsizes of defects and with a larger sample size in the future. As discussed inChapter 3, future research can also include using the method as a generalobject segmentation method for 3D meshes.The major challenge we encounter in methodology is optimizing the pre-processing algorithm to produce the best result close to the ground-truth85Figure 6.1: Tooth segmentation for a mandible with a defect in the frontusing our method with no user input.tooth crown contour position. Mandible models derived from clinical CTscans are of various dentition conditions and mesh qualities. We notice thatour contour identification accuracy increases when the tooth crown is morewell-defined on the mesh surface.The need for parameter tuning is a drawback of the preprocessing algo-rithm. Given a set of healthy mandible models, mesh resolution is the firstfactor that needs to be considered in the context of parameter tuning. Vari-ables such as the registration parameters and numbers of iterations for theSDF check and snake algorithm need to be optimized for different mesh res-olutions. We have tuned the parameters for meshes with 10-20k vertices andoffered detailed descriptions in Chapter 3. For meshes with higher (lower)resolutions, the user may experiment with the registration parameters andincrease (decrease) the number of iterations for contour refinement to obtainthe best tooth segmentation outcome. Some of the algorithm parameterscan remain unchanged for meshes of different resolutions. For example, thenumber of key points/control points is decided by the number of teeth ona mandible with full dentition (14-16). They are not dependent on the res-olution. The user may increase the number of control points for finer userinteraction with the contours. In addition, the weights of the internal andthe external energy of the snake algorithm are manually tuned by us. Theycan be applied to target surface meshes that are of similar mesh quality as86our data set.Most of the artifacts in the algorithm-identified tooth crown contour canbe resolved by user intervention in the ArtiSynth interface. Nonetheless, wewould like to eliminate their occurrence as much as possible. The first partof the method, the non-rigid registration, is proved in the literature to havevery reliable performances[15]. For our task at hand, the registration processcould be improved by using multiple category-specific mandible templates(and contour templates) instead of relying only on one template. For exam-ple, the mandibles can be categorized based on age, gender, and dentitioncondition, such as whether the patient has the third molars. The templateused in the non-rigid registration can be chosen from the category our targetmodel belongs to. Alternatively, we may run a pretest to find the templatethat best fits the target model. This would allow subject-specific deformableregistration and produce better initial contours[85].Another related issue is that using a template with full dentition (16teeth) for registration occasionally creates extra contour rings. By usingsuch a template, we are expecting to segment the full dentition from thetarget mesh. When the target lacks certain teeth, empty contours may beformed on the bone surface (as shown in the model on the left in Figure 3.18).Besides, there may be extra contours on the inner geometries, affecting thesmoothness of the tooth removal surface. Unfortunately, neither the SDFvalue check nor our snake algorithm can effectively remove these contours.Although there are control points assigned to the internal contours, it isinconvenient to manipulate them because they are hidden. Although theseissues are largely mitigated by our cut surface smoothing, it would be usefulto add extra contour detection/internal contour detection or missing teethdetection to the algorithm.As for contour refinement, the SDF value can effectively reflect the ob-ject thickness surrounding a surface point. Experimenting with more meshfeatures may be helpful. Nonetheless, mesh features are limited in theirability to detect semantic parts and contours for complex biological objects.As mentioned in Section 2.4, the snake algorithm is sensitive to local min-ima states, which can introduce artifacts to the contour line, specifically87when the target area is noisy. Previous works combine the model withgraph cut[119–121] or simulated annealing[122] to increase stability duringenergy minimization. We could also dedicate further studies to better theconstruction of the internal and external energies.For the contour editing interface, we informally collect some user feed-back in our pilot studies and main study. A few participants mentioned thatthey would like to have more control points at curved parts on the contourline. There are several directions we could pursue to accomplish this. On abasic level, the users could be provided with a tool to add and remove controlpoints. An automatic solution could be to assign control points based onthe contour curvature instead of doing an even insertion. Additionally, wediscuss with our participants whether they need to see the contour templatewhile editing the contour and receive diverse opinions. Using a 3D displayinstead of a 2D interface may also help the users in their task of inspectingand editing the contours. It would be interesting to run more studies tostreamline the user interface design.Both of our two evaluation studies are limited by the sample size. Thedesign of the 1st study is also constrained by the user size. There is onetooth removal expert creating the manual removal reference data set using3D Slicer and one research assistant using the proposed tool to test ourmethod. We choose to have two researchers in the study instead of one toavoid one user becoming familiarized with the data set (learning and transferacross conditions). Although there is individual variation, we attempt tominimize it by having two researchers with similar backgrounds in theirknowledge of the mandible anatomy and their familiarity with using 3Dsoftware. Nonetheless, we would have more flexibility in the study designwith a larger user size and be able to draw firmer conclusions.To further assess the proposed method, future studies can include ex-ploration and comparison to other methodologies. As discussed in Chapter2, there is rarely any similar work on tooth segmentation for mandibularmeshes derived from CT scans in the literature. However, mesh segmen-tation is a venerable well-studied field. Methods such as spectral analysis,topological methods using level set, harmonic-field-based methods, and co-88segmentation are also potential solutions, although they are of higher com-putational costs than the proposed method. Given sufficient labeled data,probabilistic algorithms are well-known for being able to conduct highlyaccurate segmentation. The algorithm may again utilize mesh surface fea-tures, such as curvature and the SDF value used in our method. We wouldconsider a machine learning method, e.g., a generative adversarial network(GAN) using training sets of dentulous and edentulous models, with morepatient data accumulated from the clinic.We recommend adding our method as a function in the current softwareused for tooth segmentation, such as 3D Slicer and Blender. For 3D Slicer,more functions may be developed for smoothly toggling between a mesh-based segmentation mode and a voxel-based segmentation mode. In thisway, the users can easily benefit from the advantages of both of the toothsegmentation methods tested in Chapter 4.6.3 Future ApplicationThis work serves as a preprocessing step of mandibular meshes used in clin-ical research. Besides tooth removal, our research can be utilized by boththe oral surgeons when planning for donor site placement and the dentistswhen arranging implants.6.3.1 Donor Site Placement PlanningThere has been a long-standing debate on the best bone graft placement inthe mandible. When a fibula graft is used as the donor site, it is usuallyplaced at the thickest part of the native bone, near the inferior border ofthe mandible, to maximize bone contact and stability. And this offers goodaesthetic results for facial form. However, the fibula has a shorter verticalheight than the native mandible. A major shortcoming of this arrangementis that it introduces a height discrepancy between the graft and the naturalalveolus, adding difficulty to dental reconstruction[123]. When the graft isplaced close to the superior border, a few millimeters below the alveolus, the89facial contour may not be fully restored, but soft tissue draping can greatlycamouflage. The plastic filler may also be applied to hide the bony irregular-ities. In this case, the dental reconstruction options and implant longevityare considerably better. Compromising between aesthetic and functionaloutcomes, it is also common in the clinic to place the graft somewhere inbetween the inferior and superior borders. Sometimes oral surgeons choosescapular flap for elderly patients or when fibula is not usable[124, 125]. Thescapula is a more versatile and malleable reconstructive option in terms ofshaping the missing geometry.For better oral rehabilitation outcomes, it is recommended that the oralsurgeon and the prosthodontist collaborate on the treatment when possible.There is an unsettled discussion on whether to conduct implantation andreconstruction at the same operative time. The implant type (implant bridgeand implant denture) could be a factor at play for donor site placement. Forimplant bridge, the top surface of the donor site is ideally placed at 8-10 mmbelow the occlusal plane, while for implant denture, it is 13-15 mm belowthe occlusal plane[126]. When the bone grafts are placed at these locationsor within such a range, the prosthodontists have a better implant insertioncondition.Our work can be extended as a tool to help decide bone graft placementand facilitate cooperation between oral physicians and prosthodontists. Ahigh-fidelity prototype is shown in Figure 6.2. The occlusal plane is calcu-lated from a group of selected tooth top vertices on the template mesh afterthe non-rigid registration. By translating the contour template in the direc-tion perpendicular to the occlusal plane, we acquire the range between 10mm to 15 mm below the occlusal plane. The contour template position canbe utilized as the position of the superior bone graft surface in the planning.A slider controlling the height of the contour template is added to supportmanual adjustment by the oral physicians and the prosthodontists or by theresearch assistants. With further development, the interface could serve asa platform allowing a deeper conversation on oral surgery planning.90Figure 6.2: Donor site placement planning for jaw reconstructive surgeries.6.3.2 Individual Tooth IdentificationOur research identifies the position of the alveolar process on the mandible,which paves the way for individual tooth identification for dental implantplanning. Prosthodontists insert implants in the mandibular bone to restoreoral functions for the patients. To establish a good occlusal relationship, theimplants mimic the positioning of the natural teeth on the missing part of themandible. Since cylinders are commonly used representations of implantsin virtual planning, a future research direction could be shaped as fittingcylinders to the teeth of interest on the native mandible. The expected out-come is illustrated in Figure 6.3 for reference. With object translation tools,the cylinder placement can be manually adjusted by the prosthodontists91according to the specific oral condition.Figure 6.3: Expected outcome of fitting cylinders to the teeth.We hope that our work can assist oral surgeons and prosthodontistsand motivate more efforts on algorithm and application development for theadvancement of oral rehabilitation research.6.4 Concluding RemarksUsing non-rigid registration, shape diameter function, snake algorithm us-ing geodesic distance, and CSG operations, we develop a mesh segmentationtool for supporting interactive tooth removal from 3D mandibular meshes.Our method can considerably alleviate the traditional manual removal work-load. On average, it is 40% faster than the voxel-based manual removalmethod using 3D Slicer. 31% of the data only need minor adjustmentson the algorithm-generated segmentation. In addition, we provide evidencethat data-driven shape completion algorithms perform significantly bettertraining on edentulous mandible models than models with mixed dentitionconditions (HD95: Z=-2.484, p=0.013).This work forms the basis of a useful tool for coupling jaw reconstructionand restorative dentition for patient treatment planning.92Bibliography[1] Rui Yang, Amir H Abdi, Atabak Eghbal, Edward Wang, Khanh LinhTran, David Yang, Antony Hodgson, Eitan Prisman, and Sidney Fels.Snake-based interactive tooth segmentation for 3d mandibular meshes.In Medical Imaging 2021: Image-Guided Procedures, Robotic Inter-ventions, and Modeling, volume 11598, page 115981O. InternationalSociety for Optics and Photonics, 2021.[2] E. Wang, K.L. Tran, E. D’heygere, and E. Prisman. Predicting thepremorbid shape of a diseased mandible. The Laryngoscope, 2020.[3] Hirsch DL, Garfein ES, Christensen AM, Weimer KA, Saddeh PB,and Levine JP. Use of computer-aided design and computer-aidedmanufacturing to produce orthognathically ideal surgical outcomes: aparadigm shift in head and neck reconstruction. Journal of Oral andMaxillofacial Surgery, 67(10):2115–2122, 2009.[4] J. Sink, D. Hamlar, D. Kademani, and S. S. Khariwala. Computer-aided stereolithography for presurgical planning in fibula free tissue re-construction of the mandible. Journal of reconstructive microsurgery,28(06):395–404, 2012.[5] Koord Smolka, Michel Kraehenbuehl, Nicole Eggensperger, WockHallermann, Hanna Thoren, Tateyuki Iizuka, and Wenko Smolka.Fibula free flap reconstruction of the mandible in cancer patients: eval-uation of a combined surgical and prosthodontic treatment concept.Oral oncology, 44(6):571–581, 2008.[6] B. P. Kumar, V. Venkatesh, K. J. Kumar, B. Y. Yadav, and S. R.93Mohan. Mandibular reconstruction: overview. Journal of maxillofacialand oral surgery, 15(4):425–441, 2016.[7] Amir H Abdi, Mehran Pesteie, Eitan Prisman, Purang Abolmaesumi,and Sidney Fels. Variational shape completion for virtual planningof jaw reconstructive surgery. In International Conference on Medi-cal Image Computing and Computer-Assisted Intervention, pages 227–235. Springer, 2019.[8] Amir H Abdi, Heather Borgard, Purang Abolmaesumi, and SidneyFels. Anatomygen: deep anatomy generation from dense representa-tion with applications in mandible synthesis. In International Confer-ence on Medical Imaging with Deep Learning, pages 4–14, 2019.[9] Steven M Roser, Srinivasa Ramachandra, Henry Blair, William Grist,Grant W Carlson, Andrew M Christensen, Katherine A Weimer, andMartin B Steed. The accuracy of virtual surgical planning in free fibulamandibular reconstruction: comparison of planned and final results.Journal of oral and maxillofacial surgery, 68(11):2824–2832, 2010.[10] Benjamin D Foley, Wesly P Thayer, Adam Honeybrook, SamuelMcKenna, and Steven Press. Mandibular reconstruction usingcomputer-aided design and computer-aided manufacturing: an anal-ysis of surgical results. Journal of Oral and Maxillofacial Surgery,71(2):e111–e119, 2013.[11] Giovanni Succo, Mattia Berrone, B Battiston, Pierluigi Tos, F Goia,P Appendino, and Erika Crosetti. Step-by-step surgical technique formandibular reconstruction with fibular free flap: application of digitaltechnology in virtual surgical planning. European Archives of Oto-Rhino-Laryngology, 272(6):1491–1501, 2015.[12] Philipp Metzler, Erik J Geiger, Andre Alcon, Xioayang Ma, andDerek M Steinbacher. Three-dimensional virtual surgery accuracy forfree fibula mandibular reconstruction: planned versus actual results.Journal of Oral and Maxillofacial Surgery, 72(12):2601–2612, 2014.94[13] B. T. Goh, S. Lee, H. Tideman, and P. J. Stoelinga. Mandibularreconstruction in adults: a review. International journal of oral andmaxillofacial surgery, 37(7):597–605, 2008.[14] Siavash Khallaghi, C Antonio Sa´nchez, Abtin Rasoulian, Yue Sun,Farhad Imani, Amir Khojaste, Orcun Goksel, Cesare Romagnoli,Hamidreza Abdi, Silvia Chang, et al. Biomechanically constrainedsurface registration: Application to mr-trus fusion for prostate inter-ventions. IEEE transactions on medical imaging, 34(11):2404–2414,2015.[15] C Antonio Sa´nchez. Overcoming obstacles in biomechanical modelling:methods for dealing with discretization, data fusion, and detail. PhDthesis, University of British Columbia, 2018.[16] Ju¨rgen Wallner, Irene Mischak, and Jan Egger. Computed tomographydata collection of the complete human mandible and valid clinicalground truth models. Scientific data, 6(1):1–14, 2019.[17] Patrik F Raudaschl, Paolo Zaffino, Gregory C Sharp, Maria FrancescaSpadea, Antong Chen, Benoit M Dawant, Thomas Albrecht, TobiasGass, Christoph Langguth, Marcel Lu¨thi, et al. Evaluation of seg-mentation methods on head and neck ct: auto-segmentation challenge2015. Medical physics, 44(5):2020–2036, 2017.[18] Stanislav Nikolov, Sam Blackwell, Ruheena Mendes, Jeffrey De Fauw,Clemens Meyer, C´ıan Hughes, Harry Askham, Bernardino Romera-Paredes, Alan Karthikesalingam, Carlton Chu, et al. Deep learning toachieve clinically applicable segmentation of head and neck anatomyfor radiotherapy. arXiv preprint arXiv:1809.04430, 2018.[19] Martin Vallie`res, Emily Kay-Rivest, Le´o Jean Per-rin, Xavier Liem, Christophe Furstoss, Nader Khaouam,Phuc Fe´lix Nguyen-Tan, Chang-Shu Wang, and KhalilSultanem. Data from head-neck-pet-ct. https://wiki.cancerimagingarchive.net/display/Public/Head-Neck-PET-CT#952428386718407d3b90dd4fbc8cf71d58e68781b7, 2017. Data fromHead-Neck-PET-CT.[20] Alveolar process. https://www.icoi.org/glossary/alveolar-process/, Mar 2019.[21] Susan Standring and Henry Gray. Grays anatomy: the anatomicalbasis of clinical practice. Churchill Livingstone/Elsevier, 40 edition,2008.[22] Freddie Bray, Jacques Ferlay, Isabelle Soerjomataram, Rebecca LSiegel, Lindsey A Torre, and Ahmedin Jemal. Global cancer statis-tics 2018: Globocan estimates of incidence and mortality worldwidefor 36 cancers in 185 countries. CA: a cancer journal for clinicians,68(6):394–424, 2018.[23] P-I Br˚anemark, J Lindstro¨m, O Hallen, U Breine, P-H Jeppson, andA O¨hman. Reconstruction of the defective mandible. Scandinavianjournal of plastic and reconstructive surgery, 9(2):116–128, 1975.[24] Anne-Gae¨lle Bodard, Samuel Salino, Aline Desoutter, and SophieDeneuve. Assessment of functional improvement with implant-supported prosthetic rehabilitation after mandibular reconstructionwith a microvascular free fibula flap: a study of 25 patients. TheJournal of prosthetic dentistry, 113(2):140–145, 2015.[25] Judith A Lam Tang, Jana M Rieger, and Johan F Wolfaardt. A reviewof functional outcomes related to prosthetic treatment after maxillaryand mandibular reconstruction in patients with head and neck cancer.International Journal of Prosthodontics, 21(4), 2008.[26] Pao-Yuan Lin, Kevin C Lin, and Seng-Feng Jeng. Oromandibularreconstruction: the history, operative options and strategies, and ourexperience. ISRN surgery, 2011, 2011.[27] Takao Harashina, Hideo Nakajima, and Tatsuro Imai. Reconstruction96of mandibular defects with revascularized free rib grafts. Plastic andReconstructive Surgery, 62(4):514–522, 1978.[28] David A Hidalgo. Fibula free flap: a new method of mandible recon-struction. Plastic and reconstructive surgery, 84(1):71–79, 1989.[29] T Wilkman, A Husso, and P Lassus. Clinical comparison of scapular,fibular, and iliac crest osseal free flaps in maxillofacial reconstructions.Scandinavian Journal of Surgery, 108(1):76–82, 2019.[30] Harvey Chim, Christopher J Salgado, Samir Mardini, and Hung-ChiChen. Reconstruction of mandibular defects. In Seminars in plasticsurgery, volume 24, page 188. Thieme Medical Publishers, 2010.[31] Jeffrey M Blumberg, Paul Walker, Stephanie Johnson, Bradley John-son, Eugene Yu, Marie-Constance Lacasse, David K Lam, Brian Rit-tenberg, Christopher MKL Yao, Douglas Chepeha, et al. Mandibularreconstruction with the scapula tip free flap. Head & neck, 41(7):2353–2358, 2019.[32] W. Ren, L. Gao, S. Li, C. Chen, F. Li, Q. Wang, ..., and K. Zhi. Vir-tual planning and 3d printing modeling for mandibular reconstructionwith fibula free flap. Medicina Oral, Patolog´ıa Oral y Cirug´ıa Bucal,23(3):e359, 2018.[33] Stefan Raith, Sebastian Wolff, Timm Steiner, Ali Modabber, MichaelWeber, Frank Ho¨lzle, and Horst Fischer. Planning of mandibular re-constructions based on statistical shape models. International journalof computer assisted radiology and surgery, 12(1):99–112, 2017.[34] Katrien Plessers, Filip Verhaegen, Christophe Van Dijck, Roel Wirix-Speetjens, Philippe Debeer, Ilse Jonkers, and Jos Vander Sloten. Auto-mated quantification of glenoid bone defects using 3-dimensional mea-surements. Journal of shoulder and elbow surgery, 29(5):1050–1058,2020.97[35] Peter Vanden Berghe, Jan Demol, Frederik Gelaude, and Jos Van-der Sloten. Virtual anatomical reconstruction of large acetabular bonedefects using a statistical shape model. Computer methods in biome-chanics and biomedical engineering, 20(6):577–586, 2017.[36] Ju Zhang, Jacqui Hislop-Jambrich, and Thor F Besier. Predictive sta-tistical models of baseline variations in 3-d femoral cortex morphology.Medical engineering & physics, 38(5):450–457, 2016.[37] Xiaojie Xu, Chang Liu, and Youyi Zheng. 3d tooth segmentation andlabeling using deep convolutional neural networks. IEEE transactionson visualization and computer graphics, 25(7):2336–2348, 2018.[38] Zhiming Cui, Changjian Li, Nenglun Chen, Guodong Wei, RunnanChen, Yuanfeng Zhou, and Wenping Wang. Tsegnet: An efficient andaccurate tooth segmentation network on 3d dental model. MedicalImage Analysis, 69:101949, 2021.[39] Tianran Yuan, Wenhe Liao, Ning Dai, Xiaosheng Cheng, and QingYu. Single-tooth modeling for 3d dental model. International Journalof Biomedical Imaging, 2010, 2010.[40] Farhad Ghazvinian Zanjani, David Anssari Moin, Bas Verheij, FrankClaessen, Teo Cherici, Tao Tan, et al. Deep learning approach to se-mantic segmentation in 3d point cloud intra-oral scans of teeth. In In-ternational Conference on Medical Imaging with Deep Learning, pages557–571, 2019.[41] Farhad Ghazvinian Zanjani, Arash Pourtaherian, Svitlana Zinger,David Anssari Moin, Frank Claessen, Teo Cherici, Sarah Parinussa,and Peter HN de With. Mask-mcnet: Tooth instance segmentation in3d point clouds of intra-oral scans. Neurocomputing, 2021.[42] Bre´nainn Woodsend, Eirini Koufoudaki, Peter A Mossey, and PingLin. Automatic recognition of landmarks on digital dental models.arXiv preprint arXiv:2012.12946, 2020.98[43] John E Lloyd, Ian Stavness, and Sidney Fels. Artisynth: A fast inter-active biomechanical modeling toolkit combining multibody and finiteelement simulation. In Soft tissue biomechanical modeling for com-puter assisted surgery, pages 355–394. Springer, 2012.[44] Ariel Shamir. A survey on mesh segmentation techniques. In Computergraphics forum, volume 27, pages 1539–1556. Wiley Online Library,2008.[45] Donald D Hoffman and Whitman A Richards. Parts of recognition.Cognition, 18(1-3):65–96, 1984.[46] Michael Garland, Andrew Willmott, and Paul S Heckbert. Hierarchi-cal face clustering on polygonal surfaces. In Proceedings of the 2001symposium on Interactive 3D graphics, pages 49–58, 2001.[47] Marco Attene, Bianca Falcidieno, and Michela Spagnuolo. Hierarchicalmesh segmentation based on fitting primitives. The Visual Computer,22(3):181–193, 2006.[48] Emanoil Zuckerberger, Ayellet Tal, and Shymon Shlafman. Polyhe-dral surface decomposition with applications. Computers & Graphics,26(5):733–743, 2002.[49] Natasha Gelfand and Leonidas J Guibas. Shape segmentation usinglocal slippage analysis. In Proceedings of the 2004 Eurographics/ACMSIGGRAPH symposium on Geometry processing, pages 214–223, 2004.[50] Joshua Podolak, Philip Shilane, Aleksey Golovinskiy, SzymonRusinkiewicz, and Thomas Funkhouser. A planar-reflective symme-try transform for 3d shapes. In ACM SIGGRAPH 2006 Papers, pages549–559. 2006.[51] Jyh-Ming Lien and Nancy M Amato. Approximate convex decompo-sition of polyhedra. In Proceedings of the 2007 ACM symposium onSolid and physical modeling, pages 121–131, 2007.99[52] Lior Shapira, Ariel Shamir, and Daniel Cohen-Or. Consistent meshpartitioning and skeletonisation using the shape diameter function.The Visual Computer, 24(4):249, 2008.[53] Shuangmin Chen, Taijun Liu, Zhenyu Shu, Shiqing Xin, Ying He, andChanghe Tu. Fast and robust shape diameter function. Plos one,13(1):e0190666, 2018.[54] Panagiotis Theologou, Ioannis Pratikakis, and Theoharis Theoharis. Acomprehensive overview of methodologies and performance evaluationframeworks in 3d mesh segmentation. Computer Vision and ImageUnderstanding, 135:49–82, 2015.[55] Guillaume Lavoue´, Florent Dupont, and Atilla Baskurt. A newcad mesh segmentation method, based on curvature tensor analysis.Computer-Aided Design, 37(10):975–987, 2005.[56] Hitoshi Yamauchi, Seungyong Lee, Yunjin Lee, Yutaka Ohtake,Alexander Belyaev, and H-P Seidel. Feature sensitive mesh segmenta-tion with mean shift. In International Conference on Shape Modelingand Applications 2005 (SMI’05), pages 236–243. IEEE, 2005.[57] Julien Tierny, Jean-Philippe Vandeborre, and Mohamed Daoudi.Topology driven 3d mesh hierarchical segmentation. In IEEE Interna-tional Conference on Shape Modeling and Applications 2007 (SMI’07),pages 215–220. IEEE, 2007.[58] Kai Huebner, Steffen Ruthotto, and Danica Kragic. Minimum vol-ume bounding box decomposition for shape approximation in robotgrasping. In 2008 IEEE International Conference on Robotics andAutomation, pages 1628–1633. IEEE, 2008.[59] Hao Zhang, Oliver Van Kaick, and Ramsay Dyer. Spectral mesh pro-cessing. In Computer graphics forum, volume 29, pages 1865–1894.Wiley Online Library, 2010.100[60] Aleksey Golovinskiy and Thomas Funkhouser. Randomized cuts for3d mesh analysis. In ACM SIGGRAPH Asia 2008 papers, pages 1–12.2008.[61] Evangelos Kalogerakis, Aaron Hertzmann, and Karan Singh. Learning3d mesh segmentation and labeling. In ACM SIGGRAPH 2010 papers,pages 1–12. 2010.[62] Stefanie Wuhrer and Alan Brunton. Segmenting animated objects intonear-rigid components. The Visual Computer, 26(2):147–155, 2010.[63] Aleksey Golovinskiy and Thomas Funkhouser. Consistent segmenta-tion of 3d models. Computers & Graphics, 33(3):262–269, 2009.[64] Oana Sidi, Oliver van Kaick, Yanir Kleiman, Hao Zhang, and DanielCohen-Or. Unsupervised co-segmentation of a set of shapes viadescriptor-space spectral clustering. ACM Trans. on Graphics (Proc.SIGGRAPH Asia), 30(6):126:1–126:10, 2011.[65] Zhiqin Chen, Kangxue Yin, Matthew Fisher, Siddhartha Chaud-huri, and Hao Zhang. Bae-net: Branched autoencoder for shape co-segmentation. In Proceedings of the IEEE International Conferenceon Computer Vision, pages 8490–8499, 2019.[66] Nonlapas Wongwaen and Chanjira Sinthanayothin. Computerized al-gorithm for 3d teeth segmentation. In 2010 International Conferenceon Electronics and Information Engineering, volume 1, pages V1–277.IEEE, 2010.[67] Thomas Kronfeld, David Brunner, and Guido Brunnett. Snake-basedsegmentation of teeth from virtual dental casts. Computer-Aided De-sign and Applications, 7(2):221–233, 2010.[68] Yokesh Kumar, Ravi Janardan, Brent Larson, and Joe Moon. Im-proved segmentation of teeth in dental models. Computer-Aided De-sign and Applications, 8(2):211–224, 2011.101[69] Toshiaki Kondo, Sim Heng Ong, and Kelvin WC Foong. Tooth seg-mentation of dental study models using range images. IEEE Transac-tions on medical imaging, 23(3):350–362, 2004.[70] Kan Wu, Li Chen, Jing Li, and Yanheng Zhou. Tooth segmentationon dental meshes using morphologic skeleton. Computers & Graphics,38:199–211, 2014.[71] Sheng-hui Liao, Shi-jian Liu, Bei-ji Zou, Xi Ding, Ye Liang, and Jun-hui Huang. Automatic tooth segmentation of dental mesh based onharmonic fields. BioMed research international, 2015, 2015.[72] Zhongyi Li and Hao Wang. Interactive tooth separation from dentalmodel using segmentation field. PloS one, 11(8):e0161159, 2016.[73] Suzi Kim and Sunghee Choi. Automatic tooth segmentation of dentalmesh using a transverse plane. In 2018 40th Annual InternationalConference of the IEEE Engineering in Medicine and Biology Society(EMBC), pages 4122–4125. IEEE, 2018.[74] Shuai Yang, Ruikun Wang, Wenjie Zhao, and Yongzhen Ke. 3d in-telligent scissors for dental mesh segmentation. Computational andmathematical methods in medicine, 2020, 2020.[75] Chunfeng Lian, Li Wang, Tai-Hsien Wu, Mingxia Liu, FranciscaDura´n, Ching-Chang Ko, and Dinggang Shen. Meshsnet: Deep multi-scale mesh feature learning for end-to-end tooth labeling on 3d dentalsurfaces. In International Conference on Medical Image Computingand Computer-Assisted Intervention, pages 837–845. Springer, 2019.[76] Chunfeng Lian, Li Wang, Tai-Hsien Wu, Fan Wang, Pew-Thian Yap,Ching-Chang Ko, and Dinggang Shen. Deep multi-scale mesh featurelearning for automated labeling of raw dental surfaces from 3d intrao-ral scanners. IEEE transactions on medical imaging, 39(7):2440–2450,2020.102[77] Sukun Tian, Ning Dai, Bei Zhang, Fulai Yuan, Qing Yu, and Xi-aosheng Cheng. Automatic classification and segmentation of teethon 3d dental model using hierarchical deep learning networks. IEEEAccess, 7:84817–84828, 2019.[78] Diya Sun, Yuru Pei, Guangying Song, Yuke Guo, Gengyu Ma, Tian-min Xu, and Hongbin Zha. Tooth segmentation and labeling fromdigital dental casts. In 2020 IEEE 17th International Symposium onBiomedical Imaging (ISBI), pages 669–673. IEEE, 2020.[79] Jianda Zhang, Chunpeng Li, Qiang Song, Lin Gao, and Yu-Kun Lai.Automatic 3d tooth segmentation using convolutional neural networksin harmonic parameter space. Graphical Models, 109:101071, 2020.[80] Xiaomeng Wei, Li Chen, and Chaowei Gao. Automatic mesh fusionfor dental crowns and roots in a computer-aided orthodontics system.In 2015 8th international conference on biomedical engineering andinformatics (BMEI), pages 280–290. IEEE, 2015.[81] Xinwen Zhou, Yangzhou Gan, Jing Xiong, Dongxia Zhang, QunfeiZhao, and Zeyang Xia. A method for tooth model reconstructionbased on integration of multimodal images. Journal of healthcare en-gineering, 2018, 2018.[82] Jiahong Qian, Shijuan Lu, Yuan Gao, Yubo Tao, Jun Lin, and HaiLin. An automatic tooth reconstruction method based on multimodaldata. Journal of Visualization, 24(1):205–221, 2021.[83] Barbara Zitova and Jan Flusser. Image registration methods: a survey.Image and vision computing, 21(11):977–1000, 2003.[84] Gary KL Tam, Zhi-Quan Cheng, Yu-Kun Lai, Frank C Langbein,Yonghuai Liu, David Marshall, Ralph R Martin, Xian-Fang Sun, andPaul L Rosin. Registration of 3d point clouds and meshes: A sur-vey from rigid to nonrigid. IEEE transactions on visualization andcomputer graphics, 19(7):1199–1217, 2012.103[85] Heather Borgard, Amir H Abdi, Eitan Prisman, and Sidney Fels. Cre-ation of categorical mandible atlas to benefit non-rigid registration. InInternational Symposium on Computer Methods in Biomechanics andBiomedical Engineering, pages 597–607. Springer, 2019.[86] Paul J Besl and Neil D McKay. Method for registration of 3-d shapes.In Sensor fusion IV: control paradigms and data structures, volume1611, pages 586–606. International Society for Optics and Photonics,1992.[87] Gregory C Sharp, Sang W Lee, and David K Wehe. Icp registrationusing invariant features. IEEE Transactions on Pattern Analysis andMachine Intelligence, 24(1):90–102, 2002.[88] Andriy Myronenko and Xubo Song. Point set registration: Coher-ent point drift. IEEE transactions on pattern analysis and machineintelligence, 32(12):2262–2275, 2010.[89] John McGonagle, Geoff Pilling, Andrei Dobre, Vincent Tembo, AnvarKurmukov, Alex Chumbley, Eli Ross, and Jimin Khim. Gaussianmixture model.[90] Douglas A Reynolds. Gaussian mixture models. Encyclopedia of bio-metrics, 741, 2009.[91] Bing Jian and Baba C Vemuri. Robust point set registration usinggaussian mixture models. IEEE transactions on pattern analysis andmachine intelligence, 33(8):1633–1645, 2010.[92] Yunjin Lee and Seungyong Lee. Geometric snakes for triangularmeshes. In Computer Graphics Forum, volume 21, pages 229–238.Wiley Online Library, 2002.[93] Michael Kass, Andrew Witkin, and Demetri Terzopoulos. Snakes:Active contour models. International journal of computer vision,1(4):321–331, 1988.104[94] Kok-Why Ng, Junaidi Abdullah, Sew-Lai Ng, and Hau-Lee Tong.Snake-based boundary search for segmentation of 3d polygonal model.In Intelligent and Interactive Computing, pages 537–546. Springer,2019.[95] Yunjin Lee, Seungyong Lee, Ariel Shamir, Daniel Cohen-Or, and Hans-Peter Seidel. Mesh scissoring with minima rule and part salience.Computer Aided Geometric Design, 22(5):444–465, 2005.[96] Moonryul Jung and Haengkang Kim. Snaking across 3d meshes.In 12th Pacific Conference on Computer Graphics and Applications,2004. PG 2004. Proceedings., pages 87–93. IEEE, 2004.[97] Ramani Pichumani. Snakes: an active model. http://homepages.inf.ed.ac.uk/rbf/CVonline/LOCAL_COPIES/RAMANI1/node31.html, July 1997. Accessed: 2020-09-27.[98] Stephan Bischoff, Tobias Weyand, and Leif Kobbelt. Snakes on trian-gle meshes. In Bildverarbeitung fu¨r die Medizin 2005, pages 208–212.Springer, 2005.[99] Mahsa Torkaman, Liangjia Zhu, Peter Karasev, and Allen Tannen-baum. Sulci segmentation using geometric active contours. In MedicalImaging 2017: Image Processing, volume 10133, page 101330I. Inter-national Society for Optics and Photonics, 2017.[100] Halim Benhabiles, Guillaume Lavoue´, Jean-Philippe Vandeborre, andMohamed Daoudi. Learning boundary edges for 3d-mesh segmen-tation. In Computer Graphics Forum, volume 30, pages 2170–2182.Wiley Online Library, 2011.[101] Matthias Krueger, Patrice Delmas, and Georgy Gimel’farb. Activecontour based segmentation of 3d surfaces. In European Conferenceon Computer Vision, pages 350–363. Springer, 2008.105[102] Zhige Xie, Kai Xu, Ligang Liu, and Yueshan Xiong. 3d shape seg-mentation and labeling via extreme learning machine. In Computergraphics forum, volume 33, pages 85–95. Wiley Online Library, 2014.[103] Constructive solid geometry (csg). https://renderman.pixar.com/resources/RenderMan_20/constructiveSolidGeometry.html.Renderman Documentation.[104] David H Laidlaw, W Benjamin Trumbore, and John F Hughes. Con-structive solid geometry for polyhedral objects. In Proceedings of the13th annual conference on Computer graphics and interactive tech-niques, pages 161–170, 1986.[105] James D Foley, Foley Dan Van, Andries Van Dam, Steven K Feiner,John F Hughes, Edward Angel, and J Hughes. Computer graphics:principles and practice, volume 12110. Addison-Wesley Professional,1996.[106] John Lloyd and Antonio Sa´nchez. Artisynth modeling guide. https://www.artisynth.org/doc/html/modelguide/modelguide.html, Jul2019.[107] AA Pupykina, AV Ochepovsky, OM Gushchina, and DA Nasonov.Algorithm for the boundary detection of dental crowns for 3d dentalmodel segmentation. In Journal of Physics: Conference Series, volume1278, page 012033. IOP Publishing, 2019.[108] University of Dundee. Mandible. https://sketchfab.com/3d-models/mandible-7a3c3b99916e481197e6f18fda107c15, 2015.Sketchfab.[109] UAA Niroshika, RGN Meegama, and TGI Fernando. Active contourmodel to extract boundaries of teeth in dental x-ray images. In 20138th International Conference on Computer Science & Education, pages396–401. IEEE, 2013.106[110] Na Dong, Li Zhao, and Aiguo Wu. Cervical cell recognition basedon agvf-snake algorithm. International journal of computer assistedradiology and surgery, 14(11):2031–2041, 2019.[111] Sida Peng, Wen Jiang, Huaijin Pi, Xiuli Li, Hujun Bao, and XiaoweiZhou. Deep snake for real-time instance segmentation. In Proceed-ings of the IEEE/CVF Conference on Computer Vision and PatternRecognition, pages 8533–8542, 2020.[112] Youyi Zheng, Chiew-Lan Tai, and Oscar Kin-Chung Au. Dot scissor:a single-click interface for mesh segmentation. IEEE transactions onvisualization and computer graphics, 18(8):1304–1312, 2011.[113] Edsger W Dijkstra et al. A note on two problems in connexion withgraphs. Numerische mathematik, 1(1):269–271, 1959.[114] Szymon Rusinkiewicz. Estimating curvatures and their derivativeson triangle meshes. In Proceedings. 2nd International Symposium on3D Data Processing, Visualization and Transmission, 2004. 3DPVT2004., pages 486–493. IEEE, 2004.[115] H Shou, A Eloyan, S Lee, Vadim Zipunnikov, AN Crainiceanu,MB Nebel, B Caffo, MA Lindquist, and Ciprian M Crainiceanu. Quan-tifying the reliability of image replication studies: the image intraclasscorrelation coefficient (i2c2). Cognitive, Affective, & Behavioral Neu-roscience, 13(4):714–724, 2013.[116] Nicolas Aspert, Diego Santa-Cruz, and Touradj Ebrahimi. Mesh:Measuring errors between surfaces using the hausdorff distance. InProceedings. IEEE international conference on multimedia and expo,volume 1, pages 705–708. IEEE, 2002.[117] Tobias Heimann, Bram Van Ginneken, Martin A Styner, YuliaArzhaeva, Volker Aurich, Christian Bauer, Andreas Beck, ChristophBecker, Reinhard Beichel, Gyo¨rgy Bekes, et al. Comparison and evalu-ation of methods for liver segmentation from ct datasets. IEEE trans-actions on medical imaging, 28(8):1251–1265, 2009.107[118] James S Brown, Conor Barry, Michael Ho, and Richard Shaw. A newclassification for mandibular defects after oncological resection. TheLancet Oncology, 17(1):e23–e30, 2016.[119] Ning Xu, Narendra Ahuja, and Ravi Bansal. Object segmentationusing graph cuts based active contours. Computer Vision and ImageUnderstanding, 107(3):210–224, 2007.[120] Hailing Zhou, Jianmin Zheng, and Lei Wei. Texture aware image seg-mentation using graph cuts and active contours. Pattern Recognition,46(6):1719–1733, 2013.[121] Shaofeng Jiang, Yu Wang, Xuxin Zhou, Zhen Chen, and Suhua Yang.Brain extraction using active contour neighborhood-based graph cutsmodel. Symmetry, 12(4):559, 2020.[122] Liqun Tang, Kejun Wang, Guangsheng Feng, and Yonghua Li. Animage segmentation algorithm based on the simulated annealing andimproved snake model. In 2007 International Conference on Mecha-tronics and Automation, pages 3876–3881. IEEE, 2007.[123] Ryan S Jackson, Daniel L Price, Kevin Arce, and Eric J Moore. Eval-uation of clinical outcomes of osseointegrated dental implantation offibula free flaps for mandibular reconstruction. JAMA facial plasticsurgery, 18(3):201–206, 2016.[124] Jason I Kass, Eitan Prisman, and Brett A Miles. Guide design invirtual planning for scapular tip free flap reconstruction. LaryngoscopeInvestigative Otolaryngology, 3(3):162–168, 2018.[125] Mathew Bak, Adam S Jacobson, Daniel Buchbinder, and Mark LUrken. Contemporary reconstruction of the mandible. Oral oncol-ogy, 46(2):71–76, 2010.[126] Steven Kendrick and David Wong. Vertical and horizontal dimensionsof implant dentistry: numbers every dentist should know. Inside Dent,4287:2–5, 2009.108Appendix AThe Pseudo-Code of Jungand Kim’s Greedy Algorithmfor Evolving SnakesAlgorithm 2 One iteration of snake evolvement in the proposed toothsegmentation method[96]vi: i-th snaxel.n: the number of snaxels.D(vi): the domain of the 1-ring neighbor vertices to vi; the feature valueof vi will be compared to those of the vertices in D(vi).vi.neighbor[j]: the j-th neighbor vertex of vertex vi.for each snaxel i = 0 to n doEi,min = Esnake(vi);for each neighbor vertex j ∈ D(vi) dovij := vi.neighbor[j];Esnake(vij) = Eint(vi−1, vij , vi+1) + Eext(vij);if Esnake(vij) < Ei,min thenEi,min := Esnake(vij);vi,min := vij ;end ifend forSubstitute snaxel point vi with vi,min, whose energy is the smallestamong vi and its neighbor verticesend for109Appendix BUser Interface QuickReference Manual1. ProcedureAutomatic part ⇒ (Optional) Contour editing ⇒ Save the toothlessmesh2. Contour editing controls• Reassign control points.• Remove teeth.• Smoothing.• Point selection.Refer to the message panel to see the number of points selected.– 1 point (x,y,z direction translation).∗ Radius adjustment.Make sure a sphere appears around the selected pointbefore moving.The sphere radius: adjusted by wheel scrolling.∗ One-sided control.· Unticked (default): modify both the front side and theback side of the contour at the same time.· Ticked: only modify the contour on one side.∗ Clip on to the surface.· Unticked (default): the control point can move freely.110· Ticked: the control points can stick to the surface whenmoved.– Multiple points (x, y, z direction translation).∗ LMB+CTRL / Elliptical component selection / Dragto select, pay attention to not select more points thanwanted.∗ Clip on to the surface.– All points (only z-direction translation).∗ “Select all” button.∗ Click and drag.The whole contour can be translated when all the points areselected.Points clip on to the mesh by default.• Z/Edit: undo translation.• C: clear selection.3. Trouble shooting• Red errors in the console: reload the model.• Particular function does not work well: reload the model.• Lots of outputs in the console: it’s fine.• Screen is stuck:– One point is selected.– The code crashes: restart the computer.• Topology issue:Error file written to /var/folders/94/...txt.Maspack.util.InternalErrorException: No new vertex found for72 face=33 mesh0=false.Can keep editing contour, sometimes lead to crashes.111Appendix CThe Results of the StudyComparing Our Methodwith A Voxel-Based MethodTable C.1: Manual processing time comparison (unit: s)No.Manual editing using theproposed methodManual removal using 3DSlicer001 410 252003 168 270004 157 362005 86 202007 57 186008 180 328009 91 153012 321 110013 45 162014 160 108015 79 172016 209 172018 166 215019 45 191020 66 120021 212 226022 104 141024 76 148112025 25 137026 69 208027 119 159028 83 127029 97 201030 32 162031 42 139033 310 147034 49 140035 91 123036 37 263037 281 183038 133 197039 54 156040 61 190041 26 219042 46 175043 60 158045 118 173049 93 168050 76 190052 107 150053 117 159054 27 164055 61 118056 46 118057 71 160058 36 135060 21 165061 85 189Ave 106 177SD 84.56 51.72113Table C.2: Compare the processing time running on a laptop with 4 coresto running on a desktop computer with 8 cores(unit: s)No. 4 cores 8 coresRegistration SDF+snake Registration SDF+snake001 9.51 12.44 9.08 11.51003 9.31 15.08 8.85 13.45004 9.58 12.65 8.75 10.11005 9.62 10.80 8.26 10.51007 10.03 11.06 8.43 11.65008 9.32 10.94 9.47 9.90009 8.79 14.76 8.64 16.33012 9.00 14.66 8.97 12.67013 10.00 11.61 9.06 10.49014 9.31 13.76 10.22 10.20015 9.87 13.06 8.92 11.67016 10.30 7.77 9.40 7.14018 9.35 12.64 9.10 12.72019 9.47 9.98 8.72 8.71020 9.79 8.54 8.77 6.68021 9.10 9.40 8.71 10.54022 8.98 13.83 9.63 10.29024 10.46 12.84 9.28 10.19025 9.32 39.60 8.82 24.62026 9.93 13.93 9.30 10.50027 9.07 14.63 9.68 12.77028 9.16 20.84 9.50 15.42029 9.41 13.31 8.52 12.41030 8.75 10.71 9.42 10.50031 9.21 14.37 8.62 11.30033 9.40 12.12 9.09 8.49034 9.27 10.62 8.91 8.90035 9.81 14.05 8.30 13.54036 12.85 14.25 8.36 12.72114037 9.31 27.05 8.43 19.66038 8.91 13.46 8.44 10.15039 9.77 17.43 9.16 13.80040 8.88 14.25 8.22 9.55041 9.13 12.95 9.13 11.10042 11.82 15.06 8.92 12.66043 8.82 7.59 9.11 6.33045 11.38 13.50 9.07 9.04049 9.49 12.29 9.46 11.15050 9.86 25.22 9.18 18.54052 9.23 15.86 8.63 11.19053 10.51 17.63 8.67 14.61054 9.12 10.96 8.68 10.89055 10.09 14.39 8.20 13.06056 9.44 11.65 8.41 11.26057 9.43 14.65 8.76 10.99058 9.68 10.25 8.78 8.75060 8.58 19.68 8.91 17.54061 9.04 12.74 9.29 9.13Ave 9.59 14.18 8.92 11.78SD 0.78 5.28 0.43 3.35115Table C.3: Distance comparison between the cut surfaces from three groups:P-M: the proposed mesh-based segmentation and a voxel-based manual re-moval using 3D Slicer. P-A: the proposed mesh-based segmentation andautomatic segmentation. M-M: between two rounds of voxel-based manualremoval for 10 models. (Unit: mm)No. P-M P-A M-MRMSD HD95 RMSD HD95 RMSD HD95001 1.17 2.99 0.60 1.27 0.30 0.31003 1.54 2.98 0.56 1.26004 0.87 1.73 0.69 1.39005 0.76 1.58 0.49 1.01007 1.17 2.28 0.76 1.48008 1.50 3.14 0.70 1.41009 1.13 2.55 0.49 1.07012 1.15 2.82 1.92 4.08013 0.89 1.90 0.37 0.83014 0.90 1.73 0.67 1.84015 0.81 1.69 0.73 1.47 0.51 0.81016 1.18 2.23 0.55 1.20018 0.73 1.48 1.32 2.89 0.18 0.09019 0.74 1.37 0.44 1.03 0.76 0.84020 1.22 2.58 0.53 1.12021 1.26 2.71 0.77 1.55022 3.03 5.33 0.90 2.57024 1.13 2.68 0.46 1.01025 0.67 1.60 0.00 0.00 0.16 0.02026 1.42 3.06 0.62 1.25 1.19 2.66027 0.71 1.59 0.84 2.25028 0.66 1.34 0.64 1.31029 0.95 2.13 0.53 1.10030 1.13 2.23 0.66 1.38031 1.10 1.98 0.52 0.97 1.09 1.88033 0.76 1.40 0.98 1.98116034 0.66 1.29 0.17 0.34035 1.10 2.41 0.89 1.87036 1.17 3.15 0.59 0.98 0.62 1.39037 0.54 1.09 0.40 0.88038 2.34 3.99 0.65 1.29039 1.46 2.78 0.27 0.65040 0.78 1.70 0.49 0.96041 0.82 1.64 0.17 0.44042 1.20 2.62 0.29 0.65043 0.73 1.41 0.60 1.22045 1.10 2.66 0.66 1.39049 1.71 3.57 0.79 1.56050 1.73 4.37 0.62 1.25052 1.43 2.52 0.57 1.22 0.14 0.00053 1.23 2.53 0.45 0.96054 0.64 1.20 0.55 0.69055 0.88 1.79 0.54 1.00056 3.45 6.62 0.24 0.60057 0.58 1.13 1.73 4.64058 1.91 3.14 0.33 0.68060 1.22 2.43 0.50 1.32061 1.37 2.47 0.16 0.39 0.15 0.02Ave 1.18 2.41 0.61 1.33 0.51 0.80SD 0.57 1.07 0.35 0.84 0.40 0.92117Table C.4: Screenshots of the 48 mandible models before and after toothremoval using the proposed method (preprocessing algorithm and user in-tervention) and using 3D Slicer.118119120121122123124125126Appendix DThe Results of the StudyEvaluating Using EdentulousModels for VSPTable D.1: The results of the statistical-shape-modeling-based shape com-pletion algorithm introduced in [2] (Symmetric 95th Percentile HausdorffDistance (HD95) and Volumetric Dice Score (DSC)). The algorithm is testedon all 7 classes of mandibular defects (I, Ic, II, IIc, III, IV, IVc) using theedentulous models of the mandible data set used in [2]. The results from theoriginal study are shown in the last tow columns. The images of the originalmodels are displayed in the first column. The types of the original model(E: edentulous model. D: dentulous model or model with partial dentition)are shown in the second column.127 Model Type Defect Edentulous models Original models HD95 (mm) DSC (%) HD95 (mm) DSC (%) 001 E I 3.00 85.80 2.83 86.61 Ic 7.87 69.28 7.21 69.37 II 3.16 81.77 3.16 83.61 IIc 6.00 52.79 6.32 50.75 III 5.10 69.56 4.12 70.70 IV 4.47 68.38 5.83 63.74 IVc 5.10 74.09 5.10 63.82 004 D I 1.41 90.36 3.00 83.26 Ic 3.00 75.10 4.58 64.11 II 2.00 88.94 3.00 84.43 IIc 4.12 64.16 7.62 57.28 III 2.24 83.90 3.61 83.89 IV 2.24 83.74 15.65 72.12 IVc 4.58 60.26 11.18 32.87 006 D I 2.45 82.57 2.24 88.63 Ic 8.06 55.89 7.68 40.12 II 3.32 75.83 2.45 88.67 IIc 10.49 54.68 9.22 43.45 III 3.61 74.02 4.12 73.51 IV 2.83 82.44 5.20 71.71 IVc 9.49 40.15 7.21 57.60 007 D I 3.16 86.59 4.58 83.77 Ic 9.06 38.65 9.64 61.11 II 2.83 86.70 4.24 79.11 IIc 10.77 47.94 10.72 64.37 III 4.00 83.25 6.00 78.96 IV 5.10 78.83 4.24 82.07 IVc 9.43 56.58 4.58 76.23 128 008 E I 3.16 84.88 3.00 84.95 Ic 7.28 41.22 6.08 43.38 II 3.00 81.73 3.74 80.37 IIc 9.06 34.76 8.06 37.05 III 5.92 61.28 7.00 63.28 IV 7.35 65.20 8.54 64.10 IVc 9.43 42.47 7.00 53.23 009 D I 2.24 84.20 3.16 83.96 Ic 5.00 73.04 8.31 65.58 II 3.00 80.03 3.61 81.30 IIc 7.21 62.50 7.07 63.42 III 4.24 76.20 6.08 72.95 IV 5.10 78.52 6.71 75.43 IVc 6.48 61.68 5.20 66.56 010 D I 2.00 88.96 2.24 87.10 Ic 4.12 78.09 5.74 51.67 II 2.45 85.61 2.83 85.65 IIc 7.00 65.10 5.83 58.70 III 3.16 83.10 3.00 82.74 IV 3.32 82.57 8.06 72.33 IVc 6.40 60.23 7.07 51.22 011 D I 2.45 79.99 2.83 83.00 Ic 7.00 42.91 3.61 76.45 II 2.45 81.11 2.24 86.97 IIc 5.92 56.09 2.83 82.77 III 3.32 74.42 2.00 88.52 IV 5.74 71.30 6.16 82.95 IVc 5.10 62.06 3.46 73.64 012 E I 2.83 83.86 3.61 80.91 Ic 5.83 60.80 5.92 58.39 II 5.92 79.21 5.00 79.87 IIc 4.58 72.61 6.71 61.38 III 4.12 82.98 3.00 85.05 IV 8.60 69.13 9.27 69.31 IVc 6.00 58.19 9.38 44.07 129 013 D I 2.45 87.35 2.00 89.33 Ic 5.92 58.68 3.00 73.65 II 2.24 83.59 2.24 87.35 IIc 6.08 56.15 3.00 77.79 III 3.00 87.59 2.24 88.83 IV 2.83 86.33 2.00 88.51 IVc 7.07 41.38 3.00 81.86 014 D I 2.00 88.97 2.83 85.85 Ic 4.00 78.17 4.00 66.00 II 2.45 85.66 3.00 85.28 IIc 7.00 65.09 3.00 77.76 III 3.16 83.11 3.00 81.97 IV 3.32 82.57 8.00 77.21 IVc 6.40 60.24 3.61 68.27 015 D I 2.24 86.15 3.32 83.77 Ic 5.39 68.17 4.24 74.54 II 2.24 85.15 3.16 84.82 IIc 5.10 75.28 5.10 75.95 III 3.00 82.36 3.61 79.00 IV 5.00 76.67 8.31 66.04 IVc 4.12 75.02 5.10 66.49 016 D I 2.00 83.83 2.24 85.14 Ic 7.35 35.74 4.47 76.43 II 2.00 85.51 2.83 85.18 IIc 7.00 46.52 4.90 78.04 III 2.00 89.45 2.24 88.01 IV 2.45 85.17 6.00 79.69 IVc 8.00 41.15 4.90 68.25 017 D I 3.32 79.25 4.24 88.32 Ic 4.12 65.31 5.00 77.11 II 4.12 78.10 5.10 85.82 IIc 5.39 60.31 4.47 74.88 III 3.61 85.80 2.24 89.45 IV 3.61 82.96 6.08 81.63 IVc 10.49 25.38 5.00 74.17 130 018 D I 3.61 79.67 5.00 83.60 Ic 10.10 28.13 6.00 59.60 II 3.32 79.84 3.46 84.41 IIc 10.49 31.56 8.60 58.54 III 4.12 66.18 3.61 79.22 IV 5.83 65.19 6.00 74.75 IVc 10.20 43.26 8.49 65.66 019 D I 3.74 85.92 3.00 87.40 Ic 6.40 66.33 10.00 69.53 II 3.16 82.80 3.00 84.08 IIc 9.70 53.79 16.25 56.66 III 2.24 83.77 3.16 81.20 IV 4.24 70.10 10.00 62.88 IVc 8.37 42.62 17.00 52.53 020 D I 2.24 86.33 2.00 88.62 Ic 7.28 53.17 2.24 80.75 II 2.24 85.85 2.24 89.01 IIc 10.25 47.85 2.24 85.78 III 2.24 84.56 4.12 81.63 IV 2.83 85.10 5.39 80.48 IVc 9.85 53.55 3.74 74.64 021 D I 1.41 90.63 3.74 81.01 Ic 5.20 59.09 6.16 62.20 II 2.45 85.79 3.32 78.61 IIc 5.20 60.56 5.00 71.81 III 4.00 79.10 4.12 81.56 IV 6.00 77.94 6.08 63.74 IVc 5.10 59.28 4.69 68.50 022 D I 1.73 90.67 3.00 85.83 Ic 5.39 48.15 8.00 68.96 II 1.73 90.14 3.16 83.69 IIc 6.40 50.92 6.08 76.61 III 2.83 76.48 3.16 80.46 IV 5.10 68.49 5.83 77.34 IVc 5.00 60.51 5.66 51.57 131 023 D I 2.00 87.44 4.12 83.07 Ic 5.48 70.29 4.00 72.49 II 2.00 85.79 5.00 78.37 IIc 8.25 59.79 4.12 75.00 III 3.16 82.42 7.00 77.32 IV 3.16 86.10 8.77 80.78 IVc 7.07 59.18 4.24 76.31 024 D I 1.41 92.67 2.24 90.83 Ic 2.24 78.85 3.16 72.93 II 1.41 92.52 2.24 90.52 IIc 2.83 76.00 3.16 79.20 III 1.73 89.98 2.24 90.84 IV 2.00 89.47 7.28 80.93 IVc 2.45 79.52 4.12 64.96 031 E I 1.41 84.09 1.41 86.37 Ic 4.36 60.30 3.16 67.86 II 4.00 80.84 11.45 56.29 IIc 7.35 42.43 5.83 52.41 III 4.90 79.25 4.36 75.92 IV 8.31 70.28 5.10 75.93 IVc 8.54 41.78 46.88 5.49 032 E I 2.00 89.16 2.00 87.25 Ic 6.78 52.55 5.10 58.88 II 3.16 77.35 3.00 79.33 IIc 5.74 66.18 4.24 71.61 III 3.16 82.99 3.00 83.59 IV 4.00 78.09 5.48 74.96 IVc 5.10 67.17 4.24 67.56 036 E I 2.00 89.13 1.73 89.15 Ic 4.24 56.18 3.61 65.54 II 2.00 87.96 2.00 88.15 IIc 5.00 60.63 4.24 64.41 III 2.24 86.43 2.24 85.04 IV 4.47 75.02 5.74 72.71 IVc 5.00 65.67 4.69 66.71 132 041 E I 2.24 82.08 2.24 82.59 Ic 3.16 66.88 3.74 80.82 II 2.24 81.86 2.45 81.64 IIc 2.83 73.75 4.00 82.78 III 2.24 84.65 2.24 85.57 IV 5.39 63.41 7.81 59.00 IVc 3.74 72.03 4.47 61.43 042 E I 3.16 80.04 3.32 79.35 Ic 5.20 54.74 5.20 61.23 II 2.83 78.52 2.83 80.57 IIc 6.40 58.47 5.83 62.52 III 3.00 81.95 2.45 80.57 IV 5.92 62.29 6.32 64.87 IVc 4.00 70.33 64.29 14.14 043 E I 3.00 71.23 2.45 75.11 Ic 6.71 38.79 6.00 52.84 II 3.61 65.64 3.61 66.30 IIc 6.32 52.78 4.12 61.95 III 3.16 73.36 3.16 73.00 IV 7.48 60.38 7.00 63.25 IVc 6.40 58.46 4.69 60.47 044 E I 1.73 86.82 1.73 88.63 Ic 2.83 82.86 3.00 77.49 II 2.00 87.32 2.00 87.38 IIc 3.00 80.76 3.32 75.45 III 3.00 87.76 2.83 88.54 IV 4.12 79.88 4.00 76.89 IVc 3.32 81.61 14.14 37.42 045 E I 4.24 80.17 5.10 80.06 Ic 3.61 74.50 3.74 72.55 II 4.12 81.80 5.39 81.09 IIc 3.16 78.68 4.00 78.90 III 3.00 79.06 3.00 79.94 IV 8.66 58.34 7.55 58.85 IVc 3.00 80.83 4.12 74.61 133 047 E I 2.45 80.90 2.45 78.91 Ic 4.58 60.17 5.39 45.09 II 6.16 67.65 8.25 64.73 IIc 4.24 67.18 5.74 48.70 III 6.32 68.68 7.62 62.70 IV 9.22 63.67 13.45 57.88 IVc 5.66 47.11 47.04 15.02 048 E I 2.83 71.28 2.45 77.30 Ic 3.74 52.63 3.00 69.56 II 2.24 77.09 2.24 83.20 IIc 5.92 39.63 13.04 25.63 III 4.47 62.84 4.47 63.81 IV 5.74 56.86 17.00 7.67 IVc 5.00 57.49 19.34 11.77 049 E I 2.83 71.55 3.32 68.27 Ic 2.45 56.63 22.83 6.15 II 2.24 78.62 3.00 74.27 IIc 3.16 58.72 17.72 17.34 III 3.61 59.57 4.12 45.99 IV 9.27 49.13 15.03 17.92 IVc 5.83 22.52 105.99 0.13 050 E I 2.83 74.20 2.83 75.23 Ic 8.06 48.13 6.00 56.67 II 3.00 75.02 3.00 76.29 IIc 10.05 38.65 8.00 38.72 III 1.73 82.80 1.73 83.47 IV 3.00 72.86 4.69 70.28 IVc 11.36 34.33 54.31 0.00 051 E I 1.41 87.96 1.41 89.04 Ic 3.16 63.53 3.00 72.92 II 1.41 88.84 1.41 89.05 IIc 5.00 56.33 3.61 65.92 III 3.00 80.74 3.00 80.36 IV 6.08 69.59 6.00 72.74 IVc 4.47 57.16 3.61 60.29 134 052 E I 3.61 83.16 3.61 82.68 Ic 4.12 65.22 2.83 76.50 II 3.16 83.05 3.32 82.19 IIc 5.00 66.20 4.24 71.96 III 2.24 82.19 2.45 80.36 IV 5.00 70.55 4.47 70.10 IVc 4.90 63.11 6.40 46.42 053 E I 1.41 87.89 1.41 86.86 Ic 4.24 46.77 5.00 49.98 II 2.45 82.83 5.20 76.88 IIc 8.06 33.35 6.00 40.82 III 4.12 76.86 3.16 76.67 IV 5.74 74.12 8.12 69.02 IVc 8.12 31.00 50.16 0.71 054 E I 2.24 77.73 2.00 84.79 Ic 7.07 52.12 4.24 64.86 II 3.00 71.01 2.45 76.46 IIc 9.17 45.02 6.48 48.43 III 4.47 65.40 4.12 68.67 IV 7.28 62.31 7.00 64.26 IVc 6.48 62.97 5.10 63.24 055 E I 2.00 86.29 1.41 85.67 Ic 10.49 26.40 10.20 29.02 II 2.24 83.56 2.00 82.88 IIc 10.20 35.02 10.05 37.73 III 5.10 81.93 5.10 81.78 IV 4.90 80.31 8.06 67.05 IVc 9.27 42.56 45.78 1.21 056 E I 2.00 81.10 1.41 87.25 Ic 3.74 50.79 3.16 54.83 II 2.00 81.46 1.41 85.91 IIc 5.74 38.98 5.39 40.65 III 2.83 71.38 1.41 83.94 IV 6.32 56.65 4.47 67.62 IVc 6.78 39.04 5.39 44.71 135 057 E I 2.24 82.26 1.73 86.63 Ic 7.68 30.12 4.58 52.00 II 2.83 84.09 2.24 86.15 IIc 9.38 35.40 8.06 42.75 III 5.10 72.74 5.10 79.35 IV 6.32 67.83 5.20 76.62 IVc 9.43 47.62 8.00 53.98 058 E I 9.00 59.98 8.12 59.41 Ic 6.71 29.78 4.69 65.47 II 11.79 44.03 11.58 43.30 IIc 12.04 21.38 7.00 42.92 III 14.04 27.19 15.13 23.28 IV 9.00 36.27 17.32 6.10 IVc 10.49 9.41 76.68 0.00 059 D I 1.73 85.26 1.73 89.73 Ic 7.81 53.18 4.47 63.85 II 2.83 74.58 2.24 85.86 IIc 10.68 36.71 6.08 66.82 III 2.45 81.15 2.24 87.97 IV 3.74 78.07 3.00 83.89 IVc 12.57 15.75 6.63 67.94 060 E I 1.41 91.09 2.00 90.43 Ic 3.00 71.67 2.00 87.96 II 1.41 91.22 2.00 88.55 IIc 3.46 74.13 3.61 82.97 III 3.32 89.00 3.00 88.27 IV 2.83 87.34 2.24 87.30 IVc 2.83 78.87 2.83 76.50 061 E I 2.00 85.73 2.00 86.87 Ic 6.00 73.18 5.48 74.43 II 2.24 83.32 2.00 84.31 IIc 5.10 74.07 5.00 70.98 III 2.24 85.36 2.83 84.32 IV 2.24 87.25 4.24 76.28 IVc 5.39 76.70 5.10 74.13 136 062 E I 2.00 83.10 1.41 86.69 Ic 2.83 72.91 2.24 73.96 II 2.24 84.22 1.73 87.15 IIc 4.24 68.59 2.24 75.73 III 2.24 85.42 2.45 83.31 IV 2.45 84.16 3.00 81.32 IVc 6.00 47.73 6.93 36.75 063 E I 2.00 89.62 2.00 90.28 Ic 4.12 62.16 3.16 73.87 II 2.24 88.59 2.24 89.11 IIc 5.00 58.38 3.61 70.88 III 3.00 86.57 2.24 87.96 IV 7.00 75.27 5.48 73.69 IVc 6.48 44.41 4.90 56.65 064 D I 2.00 89.44 1.73 88.95 Ic 2.83 77.75 6.48 66.52 II 2.00 89.93 2.83 77.46 IIc 2.45 82.47 8.83 52.21 III 2.83 85.62 4.47 76.59 IV 5.00 82.24 4.47 75.36 IVc 3.61 72.16 8.12 53.28 065 E I 2.00 87.81 2.00 87.29 Ic 5.83 74.62 3.61 79.62 II 2.00 87.86 2.24 86.55 IIc 5.39 71.62 2.24 84.86 III 3.16 79.95 3.00 79.77 IV 4.24 78.34 4.12 78.77 IVc 4.12 75.75 3.61 72.17 066 D I 2.00 84.79 3.16 78.04 Ic 4.12 74.99 5.39 45.63 II 1.73 86.42 3.00 81.80 IIc 4.90 57.40 5.92 53.19 III 1.73 88.13 3.00 80.00 IV 1.73 87.40 5.39 63.82 IVc 7.00 34.10 6.08 56.32 137 067 D I 2.24 88.21 2.24 87.51 Ic 4.69 65.41 4.12 76.09 II 2.45 87.48 2.45 87.04 IIc 4.36 65.24 3.61 82.63 III 3.00 86.55 3.61 78.71 IV 3.16 87.50 4.00 78.37 IVc 5.20 54.20 3.61 67.79 068 D I 3.00 82.90 2.24 83.82 Ic 3.61 78.06 6.71 48.27 II 3.00 79.76 2.83 77.90 IIc 3.16 75.13 10.86 34.52 III 3.61 83.25 3.61 78.58 IV 3.61 75.78 4.12 77.13 IVc 4.12 69.41 10.44 46.39 069 E I 3.74 85.05 3.00 86.29 Ic 5.00 55.88 5.10 52.93 II 3.32 81.39 4.12 79.26 IIc 5.74 59.13 5.92 58.01 III 4.36 81.15 5.83 76.28 IV 8.94 73.71 9.43 67.33 IVc 4.58 64.58 6.08 57.01 070 E I 2.24 84.31 1.41 88.26 Ic 5.39 60.92 4.24 63.16 II 5.00 79.03 2.00 86.22 IIc 5.10 59.27 3.00 76.99 III 4.90 68.57 3.61 77.59 IV 9.00 59.16 5.92 71.97 IVc 5.48 51.38 4.58 54.80 071 E I 3.16 80.60 3.61 81.83 Ic 4.24 61.16 4.12 68.02 II 3.16 81.45 3.61 81.05 IIc 3.46 71.81 3.46 77.21 III 3.00 81.86 3.46 80.11 IV 4.12 79.58 4.24 79.85 IVc 4.24 61.33 3.16 76.36 138 072 E I 3.00 85.14 3.46 84.90 Ic 4.90 69.04 4.12 69.70 II 2.24 86.26 3.00 86.38 IIc 6.40 61.73 5.39 62.88 III 3.00 82.84 3.16 81.04 IV 3.74 82.46 5.39 74.30 IVc 5.48 62.16 6.16 63.82 073 D I 2.00 86.90 2.83 77.44 Ic 7.00 61.39 3.32 73.33 II 2.24 84.62 2.83 79.27 IIc 7.00 65.66 2.24 78.77 III 1.73 89.27 4.24 72.38 IV 2.00 87.93 8.00 70.08 IVc 6.71 68.82 16.61 17.73 074 E I 2.24 80.47 2.24 79.71 Ic 4.12 49.94 4.00 54.10 II 2.00 84.93 2.24 84.22 IIc 5.10 51.37 5.10 53.15 III 3.61 81.87 4.00 82.16 IV 3.00 77.29 4.24 73.48 IVc 5.39 55.59 5.39 53.07 075 D I 1.41 88.84 4.12 82.17 Ic 3.00 65.44 3.16 81.78 II 2.24 85.09 9.17 76.55 IIc 4.90 56.67 8.06 60.84 III 2.24 82.08 10.77 79.69 IV 4.24 69.34 13.04 78.79 IVc 5.48 54.03 9.70 55.02 076 E I 3.16 81.88 3.00 82.22 Ic 15.43 35.56 13.00 43.67 II 3.46 79.04 3.32 79.38 IIc 18.41 37.48 18.03 37.06 III 5.39 72.28 5.39 72.72 IV 7.68 60.04 6.71 64.56 IVc 16.82 43.17 121.34 0.54 139 077 D I 2.24 87.82 2.00 88.25 Ic 5.74 62.38 2.24 84.47 II 2.24 84.56 2.24 88.44 IIc 7.21 60.50 4.12 73.08 III 2.45 85.50 3.74 83.45 IV 3.61 77.28 6.00 79.53 IVc 7.68 46.00 4.69 68.17 078 E I 1.73 91.31 1.41 91.30 Ic 4.12 70.01 5.66 70.69 II 2.45 84.42 4.12 84.49 IIc 3.74 76.49 6.40 68.19 III 4.00 84.56 6.08 81.80 IV 4.24 85.62 8.25 83.03 IVc 4.47 71.79 6.00 63.75 079 E I 4.00 78.51 4.24 80.15 Ic 5.92 63.11 5.00 66.50 II 3.16 83.76 3.61 85.02 IIc 9.90 53.52 6.63 61.44 III 4.24 83.04 4.47 80.63 IV 4.69 79.71 5.20 76.54 IVc 8.06 42.80 6.56 52.73 080 D I 2.24 88.34 2.00 86.20 Ic 3.00 80.16 4.47 54.85 II 2.24 84.60 2.83 84.64 IIc 2.83 82.03 4.47 62.47 III 2.00 86.44 4.00 85.36 IV 2.00 86.39 3.46 80.21 IVc 2.24 80.93 4.12 68.31 081 E I 2.00 87.85 1.73 90.37 Ic 5.74 75.15 4.12 81.18 II 2.24 86.69 1.73 89.97 IIc 7.28 70.43 4.69 79.83 III 2.24 87.36 1.41 90.10 IV 2.24 86.14 2.24 87.53 IVc 5.48 67.76 4.24 66.71 140 082 E I 1.41 90.62 1.41 89.64 Ic 2.00 83.68 4.00 58.43 II 1.73 88.57 1.73 87.72 IIc 2.00 85.56 5.00 56.27 III 2.00 86.67 2.83 85.37 IV 2.24 84.66 4.24 71.43 IVc 2.24 84.13 3.74 71.03 083 D I 4.00 79.99 2.24 85.62 Ic 10.30 45.80 3.16 77.70 II 3.74 79.46 3.00 81.09 IIc 9.70 49.86 5.39 68.46 III 6.40 61.52 3.74 80.27 IV 7.35 68.52 5.10 74.77 IVc 9.22 55.06 6.71 54.99 084 E I 2.24 84.26 2.24 83.78 Ic 4.12 64.67 3.16 72.24 II 2.83 80.45 2.83 80.46 IIc 3.16 74.01 3.00 74.41 III 2.24 85.75 2.24 84.38 IV 4.00 73.15 6.08 64.12 IVc 4.24 67.30 4.58 64.48 085 E I 2.83 88.39 3.00 87.40 Ic 2.45 77.25 2.45 78.80 II 2.24 87.71 2.83 85.42 IIc 2.24 84.25 2.24 84.25 III 1.41 92.00 1.41 91.62 IV 2.83 80.96 4.12 72.53 IVc 2.24 84.75 2.24 86.01 086 E I 2.24 86.57 2.24 86.69 Ic 3.74 80.03 2.83 83.34 II 2.45 84.40 2.24 87.09 IIc 2.83 84.52 2.83 82.06 III 3.00 88.70 4.24 85.14 IV 3.61 82.68 4.69 81.40 IVc 4.12 79.19 4.24 76.72 141 087 E I 2.24 89.86 2.24 90.12 Ic 4.24 73.12 5.00 67.15 II 3.61 84.79 4.00 85.57 IIc 6.00 59.58 6.08 59.13 III 3.16 85.72 4.69 81.98 IV 3.74 76.28 5.00 73.33 IVc 7.00 40.06 6.40 44.71 088 E I 2.00 86.78 2.83 84.66 Ic 6.08 65.18 4.47 70.86 II 2.24 86.54 2.83 85.49 IIc 5.00 75.62 4.24 73.35 III 1.41 91.22 2.83 89.46 IV 4.36 74.25 7.68 68.29 IVc 7.00 54.43 7.28 51.47 089 E I 3.00 88.24 2.45 89.97 Ic 2.83 82.69 2.45 80.08 II 3.16 88.45 4.47 88.02 IIc 4.69 77.08 5.00 69.06 III 5.39 86.34 7.68 83.90 IV 3.74 87.01 7.28 85.00 IVc 5.83 69.55 7.35 51.17 090 E I 2.45 85.65 2.45 85.99 Ic 5.83 78.99 5.83 67.52 II 2.24 82.27 2.45 81.54 IIc 2.83 76.18 4.12 73.59 III 2.24 82.05 3.00 81.13 IV 5.48 73.11 5.00 73.99 IVc 2.45 84.74 3.74 75.68 091 E I 2.00 89.92 1.41 91.14 Ic 2.24 83.21 3.00 77.50 II 2.00 85.70 1.73 87.16 IIc 3.00 75.55 2.24 83.68 III 2.00 90.73 2.00 91.02 IV 1.73 89.27 2.00 89.55 IVc 4.00 68.99 3.32 74.30 142 092 E I 1.41 91.04 1.73 88.70 Ic 6.71 72.04 5.39 67.19 II 1.41 89.69 2.00 84.84 IIc 6.00 72.91 8.06 61.59 III 2.24 84.38 1.73 85.75 IV 10.49 43.56 9.43 45.18 IVc 6.48 64.80 20.83 36.22 093 E I 2.45 87.71 2.24 88.97 Ic 2.45 79.41 2.45 79.94 II 2.24 87.72 3.00 87.57 IIc 3.00 79.35 2.83 81.53 III 1.41 91.38 3.00 87.39 IV 5.39 79.71 5.39 81.24 IVc 5.74 43.92 4.00 57.85 095 E I 1.41 90.27 1.41 90.41 Ic 4.90 54.37 2.83 75.02 II 1.41 90.39 1.41 91.53 IIc 4.90 63.01 2.83 78.67 III 3.00 79.53 2.24 84.98 IV 9.49 50.63 8.31 56.18 IVc 5.10 59.53 4.69 61.18 096 E I 2.83 78.25 2.24 81.11 Ic 3.61 78.60 3.00 80.56 II 3.16 78.04 2.45 83.50 IIc 3.00 76.04 2.83 76.53 III 2.24 85.11 2.24 84.93 IV 4.47 75.42 5.00 73.35 IVc 2.24 83.11 2.83 77.39 097 E I 2.24 87.68 2.00 88.02 Ic 3.61 82.47 4.12 72.79 II 3.16 85.30 3.00 84.57 IIc 2.45 84.08 3.61 69.05 III 2.00 88.66 3.00 85.63 IV 2.45 86.24 2.24 86.04 IVc 2.45 81.64 5.00 56.75 143 098 E I 3.00 85.57 3.00 84.29 Ic 8.72 45.88 6.00 55.23 II 5.20 81.43 2.83 85.96 IIc 8.31 60.12 6.00 59.04 III 4.90 84.46 3.16 82.83 IV 7.81 76.34 4.12 79.63 IVc 8.77 61.99 6.16 62.07 099 E I 2.24 91.94 2.24 90.66 Ic 3.74 62.90 4.12 67.37 II 2.24 88.15 2.45 85.13 IIc 3.61 74.01 3.16 77.65 III 2.00 90.20 2.24 87.63 IV 2.45 83.91 3.00 81.98 IVc 5.00 67.60 3.61 76.98 101 E I 3.00 82.05 9.22 64.19 Ic 4.24 57.84 7.28 34.84 II 4.00 78.88 4.24 78.30 IIc 8.31 30.70 11.09 18.58 III 4.58 77.27 16.67 46.97 IV 9.11 40.71 11.36 34.13 IVc 8.19 31.44 18.17 2.65 102 E I 1.73 85.59 2.00 88.15 Ic 2.24 75.19 2.00 82.20 II 2.00 85.62 2.00 86.55 IIc 3.16 74.58 2.00 82.57 III 3.00 85.55 3.00 85.40 IV 5.10 73.85 5.00 76.30 IVc 3.00 77.45 2.24 82.29 103 E I 2.00 88.60 2.00 89.18 Ic 5.20 71.42 4.90 72.32 II 2.00 87.04 2.00 87.88 IIc 5.92 72.09 5.48 72.90 III 2.45 85.95 3.16 85.94 IV 3.00 83.87 3.74 82.61 IVc 7.81 67.94 7.35 67.04 144
Thesis/Dissertation
eng
Electrical and Computer Engineering
Vancouver : University of British Columbia Library
Attribution-NonCommercial-NoDerivatives 4.0 International
Graduate
Fels, Sidney
Snake-based tool for supporting interactive tooth segmentation from 3D mandibular meshes
Text