“Mix 3351’"

3

 

1 . OH,
2. 5.4»!
.4 .

. nu... ihv
’
‘3: :v.
~ V x 3.1

Jali
. 3. ‘19 ‘

 

200?

This is to certify that the
dissertation entitled

AUTOMATIC FORENSIC IDENTIFICATION BASED ON
DENTAL RADIOGRAPHS

presented by

HONG CHEN

has been accepted towards fulfillment
of the requirements for the

Doctoral degree in Computer Science and
Engineering

 

 

Au;9usaa«$v/’

 

Major Professor’s Signature
MYIQ IZ l 00 7

Date

 

MSU is an afiinnative-action, equal-opportunity employer

PLACE IN RETURN BOX to remove this checkout from your record.
TO AVOID FINES return on or before date due.
MAY BE RECALLED with earlier due date if requested.

 

DATE DUE DATE DUE DATE DUE

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

6/07 p:/CIRC/DateDue.indd-p.1

AUTOMATIC FORENSIC IDENTIFICATION BASED ON
DENTAL RADIOGRAPHS

By

Hang Chen

A DISSERTATION

Submitted to
Michigan State University
in partial fulfillment of the requirements
for the degree of

DOCTOR OF PHILOSOPHY

Department of Computer Science and Engineering

2007

ABSTRACT

AUTOMATIC FORENSIC IDENTIFICATION BASED ON DENTAL
RADIOGRAPHS

By

Hong Chen

The purpose of forensic identification is to determine the identity of unidentified vic-
tims. Dental radiographs are often the only means of identifying victims, but manually
comparing dental radiographs is inefficient and subject to errors due to fatigue in human
experts. This thesis has designed and developed an automatic system for identifying hu-
man victims based on dental radiographs. There are three stages in the proposed automatic
dental identification system:

1. Feature extraction. Salient features in the dental radiograph are identified, such as
the contours of the tooth and the contours of crowns or fillings.

2. Registration. Each tooth is labeled according to its location within the mouth, and
missing teeth are detected.

3. Matching. Each unidentified radiograph (post-mortem or PM) is compared to a
database of known individuals (ante-mortem or AM).

In the first stage, namely feature extraction, contours of teeth and dental work are ex-
tracted from dental radiographs. The radiographs are first segmented into regions such that
each region contains only a single tooth. Contours of individual teeth are then extracted
from each region of the radiograph using active shape models (ASMs). Dental work such
as crowns, fillings, and root canal treatment is composed of radio-opaque material that ap-
pears as bright regions in the radiographs. An anisotropic diffusion-based technique is used
to enhance the images, and regions of dental work are segmented using image thresholding.

The second step in dental radiograph-based identification is to determine which teeth

are (or are not) present in the radiograph. This step is important because the matching

algorithm cannot properly align AM and PM radiographs if they do not contain the same
number of teeth. Thus, the second step is to label each tooth in the radiograph based on
the human dental atlas, which is a descriptive model of the shapes and relative positions of
teeth. A hybrid model involving Support Vector Machines (SVMs) and a Hidden Markov
Model (HMM) is developed for representing the dental atlas and classifying individual
teeth in dental radiograph images.

The final stage of the proposed automatic identification system is to match dental radi-
ographs of unidentified subjects against dental radiographs of known subjects in the data-
base. The extracted tooth contours are matched for every pair of teeth with the same index
in the two radiographs. When both teeth in the pair to be matched contain dental work, then
the shapes of dental work are also matched. An overall matching distance for each pair of
teeth is computed by combining the matching distances for the tooth contours and for the
dental work. Finally, the distances between the unidentified subject and all the subjects in
the database are computed based on the distances between all pairs of teeth. The database
subjects are then sorted in ascending order of the matching distances and the results are
provided to forensic experts.

Due to poor quality of dental radiographs and complexity of the matching problem,
fully automatic methods may sometimes produce errors. Monitoring schemes are designed
to evaluate the image quality and correctness of the automatic results at each processing
stage. User interaction is requested when errors in intermediate processing steps are en-
countered.

Experiments on retrieving PM radiographs of 29 subjects from a database of radi-
ographs of 33 subjects show an accuracy of 72% for top-1 retrieval and 93% for top-2
retrievals. Experiments on retrieving PM radiographs of 29 subjects from a larger database
of relatively poor quality radiographs of 133 subjects show a lower accuracy of 66% for

top-l retrieval and 90% for top-13 retrievals.

To my grandparents and parents

iv

ACKNOWLEDGMENTS

I am grateful to all the people who have helped me during the past 4 years at Michigan
State University. First of all, I would like to express my gratitude to my advisor, Dr. Anil
K. Jain, for his guidance and support. His devotion to his career, preference for perfection,
and relentless chase of novelty have inspired a great deal of my thinking on how to be a
professional researcher. I am grateful to my Ph.D. committee, Dr. Joyce Chai, Dr. Sarat
C. Dass, and Dr. John J. Weng for their suggestions, comments, and encouragement. I am
also grateful to Dr. George C. Stockrnan for his support and guidance.

1 would especially like to thank Dr. Rong Jin for his guidance, which led me into the
fantastic world of machine learning and numerical optimization techniques.

I would like to thank all the members in the PRIP lab in the Department of Computer
Science and Engineering at MSU for their generous help and inquisitive discussions (in
alphabetical order): Yi Chen, Dirk Colbry, Meltem Demirkus, Michael Farmer, Miguel
F igueroa-Villanue, Steve Krawczyk, Martin Law, Xiaoguang Lu, Pavan K. Mallapragada,
Anoop Namboodiri, Karthik Nandakumar, Unsang Park, Arun A. Ross, Umut Uludag, and
YongFang Zhu.

I would like to thank all visiting scholars to the PRIP lab for their guidance, discussion,
and friendship, especially Dr. Yunhong Wang, Dr. Francesc J. Ferri, Dr. Aparecido N.
Marana, and Dr. Choonwoo Ryu.

Thanks are also due to Adam Pitcher, Starr Portice, Norma Teague, Linda L. Moore,
Cathy M. Davison, and Debbie Kruch for their assistance and help. I would also like to

thank Kim G. Thompson and Dr. Katy L. Colbry for their help in proofreading my thesis.

I want to express my gratitude to the National Science Foundation (NSF) for supporting
this research. I would like to thank Dr. Hany H. Amrnar, Dr. Gama] Fahmy, Dr. Mohamed
Abdel-Mottaleb and Dr. Robert Howell for providing image data so that the experiments
for my research could be conducted.

Finally, and most importantly, I would like to thank my family for their unconditional

love and support.

vi

TABLE OF CONTENTS

LIST OF TABLES ix
LIST OF FIGURES x
1 Automatic Forensic Identification l
1.1 Automatic Identification of Humans ....................................................................... 1

1.2 Forensic Identification ............................................................................................. 3

1.3 Procedure of Comparative Dental Identification ..................................................... 4

1.4 Identification of Humans Using Dental Radiographs ............................................. 7
1.4.1 Introduction to Dental Radiographs ................................................................ 7

1.4.2 Dental Radiographs for Identification ............................................................ 9

1.5 Automatic Dental Identification ............................................................................ 13
1.5.1 Available Software for Matching Dental Records to Forensic Evidence ..... 13

1.5.2 Dental Radiograph-based Automatic Identification System ......................... 15

1.5.3 Challenges ..................................................................................................... 17

1.6 Summary ................................................................................................................ 22

2 Segmentation and Contour Extraction 24
2.1 Automatic Image Quality Evaluation .................................................................... 25
2.1.1 Detection of Panoramic Images .................................................................... 25

2.1.2 Detection of Intensity Imbalance .................................................................. 26

2.1.3 Blur Detection ............................................................................................... 27

2.2 Radiograph Segmentation .......................................................... . ........................... 27
2.2.1 Automatic Segmentation ............................................................................... 28

2.2.2 User Interaction ............................................................................................. 33

2.3 Extracting Tooth Contours ..................................................................................... 37
2.3.1 Introduction to Active Shape Models ........................................................... 37

2.3.2 ASM-Based Tooth Contour Extraction ........................................................ 39

2.3.3 Experiments .................................................................................................. 50

2.4 Segmenting Regions of Dental Work .................................................................... 51
2.4.1 Image Thresholding ...................................................................................... 53

2.5 Summary ................................................................................................................ 54

3 Registration of Radiographs to Dental Atlas 57
3.1 Introduction ............................................................................................................ 58
3.2 SVM / HMM Hybrid Model .................................................................................. 59

3.3 Registering a Tooth Sequence to Dental Atlas ...................................................... 62
3.3.1 Representation of Dental Atlas ..................................................................... 63

3.3.2 Extraction of Observation Sequences ........................................................... 64

3.4 User Interaction ...................................................................................................... 65

3.5 Experimental Results ............................................................................................. 65
3.6 Summary ................................................................................................................ 67

vii

4 Matching and Retrieval 72

4.1 Radiograph Matching ............................................................................................. 72
4.1.1 Introduction to Shape Matching .................................................................... 73

4.1.2 Matching Tooth Contours ............................................................................. 75

4.1.3 Matching Dental Work Contours .................................................................. 80

4.1.4 Fusing the Matching Distances ..................................................................... 82

4.2 Matching Subjects ..................................................... ‘ ............................................. 8 5

4.3 Experimental Results ............................................................................................. 87
4.4 Summary ................................................................................................................ 93

5 Conclusions and Future Directions 108
5.1 Feature Extraction ................................................................................................ 108

5.2 Atlas Registration ................................................................................................. 110

5.3 Matching .............................................................................................................. 110

5.4 Future Directions ................................................................................................. 111
APPENDICES 113
A Database Description 113
B Anisotropic Diffusion 115
BIBLIOGRAPHY 117

viii

LIST OF TABLES

1.1 A Comparison of Evidence Types Used in Victim Identification ................................. 4
1.2 A Comparison of WinID and Odonto Search ................. I ............................................. 1 5
2.1 Results of Automatic Radiograph Segmentation ......................................................... 33
2.2 Success Rate of Automatic Contour Extraction ........................................................... 51
2.3 Summary of CPU (2.99 GHz Pentium 4) Time for Extracting Features ..................... 56
3.1 Accuracies and Sources of Error in Estimating Tooth Indices .................................... 67

4.1 CPU (2.99 GHz Pentium 4) Time for Matching one PM Query Image Set to one
AM Database Image Set .................................................................................................. 103

A.1 List of Types, Numbers and Sources of Images In the Database ............................. 114

ix

LIST OF FIGURES

1.1 An example of postmortem dental chart [51]. .............................................................. 5

1.2 Three types of dental radiographs. (a) A bitevving radiograph; (b) a periapical
radiograph; (c) a panoramic radiograph. ............................................................................. 8

1.3 Three types of dental radiograph series. (a) Full mouth series; (b) bitewing series; (0)
panoramic series. ............................................................................................................... 10

1.4 A forensic expert examines a dental radiograph film of a tsunami victim in Phuket,
Thailand, on Jan. 11, 2005 [3]. ......................................................................................... 12

1.5 Dental radiographs and the corresponding description chart used byWinID system.
The crosses indicate the missing teeth, and the filled squares indicate locations of the
dental restorations in each tooth. ...................................................................................... 14

1.6 System diagram of automatic dental identification system. ....................................... 16

1.7 Fully automatic process of matching one pair of PM and AM images from the same
subject. .............................................................................................................................. 18

1.8 Automatic matching of one pair of PM and AM images with user interaction. .......... 19
1.9 Antemortem (a) and postmortem (b) radiographs of a difficult identification case for
an automatic matching system. The poor image quality poses difficulties for contour
extraction. The orthodontics operation in (a) and missing teeth in (b) have significantly

altered the dentition appearance over time. ..................................................................... 21

1.10 Changes in the imaging angle result in significant deformations in the appearances

of corresponding teeth in (3) AM and (b) PM periapical radiograph images. .................. 22
1.11 Some images in the dental radiograph database. ......................................... - ............. 23
2.1 Detection of intensity imbalance. (a) An over-exposed image; (b) an underexposed
image; (0) an non-homogeneously exposed image with STDMI= 30. ............................. 26
2.2 Detection of blur. (a) A sharp image with MAD = 2.35; (b) A blurred image with
MAD = 1.08. ..................................................................................................................... 27
2.3 A dental radiograph of a child showing both permanent teeth and primary teeth. ..... 28

2.4 Classification of image types based on number of rows of teeth. (a) and ((1) images
with two rows of teeth; (b) and (e) images with only lower row of teeth; (c) and (f)
images with only upper row of teeth. ................................................................................ 30

2.5 Finding knots in the segmentation line. ...................................................................... 31
2.6 Some examples of correct segmentation. .................................................................... 32

2. 7 Some results of incorrect automatic segmentation. (a) and (b) incorrect location of
segmentation line between upper and lower rows of teeth, (c) under segmentation; ((1)
over segmentation, (e) Improper segmentation. ................................................................ 34

2.8 User interaction for correcting of the first type of error: incorrect location of
segmentation line between upper and lower rows of teeth. (b) Correction of the

incorrect segmentation line between upper and lower teeth in (a) by specifying one

point (shown as cross). ...................................................................................................... 35

2.9 User interaction for correcting of the second type of error: under segmentation. (b)
Adding an isolation line in (a) by specifying one point (shown as cross). ....................... 35

2.10 User interaction for correction of the third type of error: over segmentation. (b)
Removing an extra isolation line in (a) by specifying one point (shown as cross). ......... 36

2.11 User interaction for correction of the fourth type of error: improper segmentation.
(b) Correction of an improper segmentation by removing the improper segmentation

line in (a) by specifying one point (shown as cross in (a)) and adding correct
segmentation lines by specifying two points (shown as cross in (b)). .............................. 36

2.12 Region of Interest (ROI) for a tooth. ........................................................................ 37

2.13 Shape Alignment. (a) correspondence between a prototype shape and a training
shape; (b) correspondence between the prototype shape and the rotated training shape;
(c) correspondence between the prototype shape and the scaled training shape. ............. 41

2.14 First five modes of the shape model of teeth. The middle shape in each row is the
mean shape, while the other four shapes are, from left to right, mean shape plus four
eigenvectors multiplied by -2, -1, l, and 2 times the square root of the corresponding

eigenvalues. ....................................................................................................................... 43
2.15 Shape extraction procedure. ...................................................................................... 44
2.16 Initialization of tooth shapes. .................................................................................... 46
2.17 Crown nodes and root nodes in the model. ............................................................... 49
2.18 Detection of erroneous tooth contours. ..................................................................... 50
2.19 Tooth shapes successfully extracted using ASMs. ................................................... 52

xi

2.20 Fitting a mixture of Gaussians model to the intensity histogram (b) of an image (a),
in which the dental work appears as a bright block. ......................................................... 54

2.21 Extracted dental work contours with and without image enhancement. (a), (b) and
(c) Without enhancement. (d), (e) and (f) After enhancement. ........................................ 55

2.22 Process of extracting tooth contours and dental work contours with human
interaction. Automatic method works well for the good quality image (image 1), but

needs user interaction for poor quality image (image 2). ................................................. 56
3.1 Three types of teeth. (a) Molar; (b) (bi)cuspid; (c) incisor. ........................................ 59
3.2 Dental Atlas of a complete set of adult teeth containing indices and classification

labels of the teeth. ............................................................................................................. 64
3.3 SVM/HMM model for the upper row of 16 teeth. ...................................................... 65

3.4 Extraction of tooth contours and generation of an observation sequence, E = {e1 , e2,
e3, e4, e5}; e1, e3 and e5 correspond to tooth states, and e2 and e4 correspond to
distance states. ................................................................................................................... 69

3.5 A user interface for manually specifying tooth indices by clicking the corresponding
teeth in the dental atlas, which is shown on the right side of the dental radiograph. ........ 70

3.6 Examples of successful registration of the dental atlas to (a) a bitewing image, (b) a
periapical image, and (c) an image with a missing tooth. In (c), teeth numbered as 12,
14, and 15 are correctly registered. The missing tooth (number 13) is detected. ............ 70

3.7 Examples of atlas registration errors. (a) The tooth types are correctly classified as
molars, but the teeth (with genuine indices 30 and 31) are registered to teeth 31 and 32

in the atlas since teeth 30, 31, and 32 are all molars and the length of the sequence is
insufficient for resolving the ambiguity; (b) all the three incisors are classified as
(bi)cuspids, thus these teeth (with genuine indices 8, 9, and 10) are registered to teeth 3,
4, and 5 in the atlas; (c) the distance between teeth 3 and 6 seems to support only one
missing tooth, so the input sequence is registered to the atlas teeth numbered 1, 2, 3, 5,

6, 7, 8, 9, 10, 12, 13, and 14, while the genuine indices are l, 2, 3, 6, 7, 8, 9, 10, 11, 13,
14, and 15. The lower row of teeth is, however, correctly registered to the atlas. ........... 71

4.1 Classification of shape matching methods [65]. ......................................................... 74

4.2 Polygonal approximation of a tooth contour with different interval are lengths. (a)
Original tooth contour; (b) polygonal approximation of (a) with interval arc length l = 5
pixels; (c) polygonal approximation of (a) with interval arc length 1 = 10 pixels; (d)
polygonal approximation of (a) with interval arc length l = 20 pixels; (e) polygonal
approximation of (a) with interval arc length l = 30 pixels. ............................................. 77

xii

4.3 Dental radiographs are 2D projections of 3D structures. ............................................ 78

4.4 Shape registration process. (a) Continuous tooth contours; (b) discrete tooth

contours; (c) initialization by aligning bounding boxes; ((1) initialized point
correspondence; (e) aligned contours after optimum transformation; (f) correspondence
after alignment and outlier detection. ............................................................................... 81

4.5 Dental work merging due to a change in the imaging angle. The hole in the circled
dental work seen in image (a) is occluded when viewed from the angle shown in (b)

even though both the images are of the same tooth; (c) preprocessed image for two

teeth in image (a); (d) preprocessed image for two teeth in image (b); (e) result of
‘Exclusive-Or’ operation for the two teeth. Pixels of value ‘1’ are displayed in black,

and the pixels of value ‘0’ are displayed in gray. ............................................................. 83

4.6 Distribution of matching distances based on the shape of dental work. ..................... 84

4.7 Coupling 4 pairs of neighboring teeth with 6 pairs of neighboring teeth. The

matching score between each pair of neighboring teeth is calculated and the average is
taken along the arrows. The results are listed in the bottom bar of black and white cells,
and the minimum of these values is defined as the matching distance between the two
sequences. ......................................................................................................................... 87

4.8 Two examples of tooth correspondence. Tooth contours in (a) and (b) are paired up
in (c); tooth contours in (d) and (e) are paired up in (f). ................................................... 88

4.9 Some AMimages (a) and PMimages (b) of a single individual in the database. ........ 89

4.10 Examples of matching. The gray lines represent the tooth shapes in the database

and the query images; the black lines represent the query shapes after transformation.
Note that in these examples, the matching distance for the genuine AM images is

smaller than the matching distance for the imposter AM images. .................................... 91

4.11 The top-4 retrievals for 3 different queries. The first image in each column is the
query image and the remaining four images are the top-4 retrievals. The genuine AM
images are ranked first for these three queries. ................................................................. 92

4.12 Cumulative matching characteristics (CMC) curves for subject retrieval in the
database of 33 subjects. ..................................................................................................... 94

4.13 Cumulative matching characteristics (CMC) curves for subject retrieval in the
database of 133 subjects. ................................................................................................... 95

4.14 Subject 10 was not tested for retrieval due to poor image quality. (3) AM
radiograph; (b) PM radiographs. ....................................................................................... 96

xiii

4.15 Subject 14 was not tested for retrieval due to eruption of new teeth in AM
radiographs. (a) AM radiographs; (b) PM radiographs. ................................................... 97

4.16 Subject 21 was not tested for retrieval due to eruption of new teeth in AM
radiographs. (a) AM radiographs; (b) PM radiographs. ................................................... 98

4.17 Subject 36 was not tested for retrieval due to poor image quality. (a) AM
radiograph; (b) PM radiographs. ....................................................................................... 99

4.18 Subject 1 was not correctly retrieved from the database due to changes in the
dentition caused by loss of teeth. (a) AMradiographs; (b) PMradiographs. ................... 100

4.19 Subject 2 was not correctly retrieved from the database due to incorrect AM tooth
contour extraction from the only available panoramic image. (a) AM radiograph; (b)
PM radiographs. .............................................................................................................. 101

4.20 Subject 9 was not correctly retrieved from the database due to incorrect AM tooth
contour extraction caused by overlapping upper and lower rows of teeth. (a) AM
radiographs; (b) PM radiographs. ................................................................................... 102

4.21 Subject 16 was not correctly retrieved from the database due to changes in tooth
appearances in AM and PM radiographs. (a) AM radiograph; (b) PM radiograph. ....... 103

4.22 Subject 25 was not correctly retrieved from the database due to incorrect AM tooth
contour extraction from the panoramic image and the bitewing images where upper and
lower rows of teeth overlap. (a) AM radiographs; (b) PM radiographs. ........................ 104

4.23 Subject 28 was not correctly retrieved from the database due to incorrect AM tooth
contour extraction from the only available panoramic image. (a) AM radiograph; (b)
PM radiographs. .............................................................................................................. 105

4.24 Subject 39 was not correctly retrieved from the database due to insufficient
number of teeth in the AM image. (a) AM radiograph; (b) PM radiographs. ................ 106

4.25 Subject 42 was not correctly retrieved from the database due to incorrect AM tooth
contour extraction from the only available panoramic image. (a) AM radiograph; (b)
PM radiographs. .............................................................................................................. 107

5.1 A dental X-ray shows loss of jaw bones caused by periodontal disease. ................. 111

xiv

CHAPTER 1

Automatic Forensic Identification

The purpose of forensic identification is to determine the identities of unidentified suspects
or victims. The significance of research on automatic methods for forensic identification
has been brought to public attention by recent disasters, such as the 9/11 terrorist attack
and the 2004 Asian tsunami.

This chapter begins with a brief survey of the methods for automatic human identi-
fication, and introduces the dental radiograph-based approach for forensic identification.
We also discuss some challenges to automatic identification based on dental records, and
briefly introduce the proposed automatic system for identifying humans based on dental

radiographs.

1.1 Automatic Identification of Humans

The evidence used for human identification is categorized into three classes: what you have,
what you know, and what you are [39]. The first category, what you have, includes credit
cards, identification documents, etc. What you know refers to all kinds of passwords and
confidential information, e.g., mother’s maiden name. What you are includes your anatom-
ical features, also called biometrics, such as your face, DNA, iris, fingerprints, etc. With

the growing need for reliable and robust human identification in a variety of applications

1

(e.g., international border crossing), biometric-based recognition has become an important
topic for research in computer vision and pattern recognition.

Biometric features can be categorized into two types: physical and behavioral [39].
Physical biometric features represent the anatomical makeup of the human body, such as
the fingerprint, face, iris, retina scan, ear shape, hand geometry, hand vein, etc. Behav-
ioral biometric features reflect the behavioral traits of an individual, such as voice, gait,
signature, key stroke dynamics, etc.

Biometric features are evaluated in terms of universality, uniqueness, permanence, col-
lectability, and acceptability [39]. Universality means the degree to which a biometric
feature is commonly possessed. For instance, faces have a higher universality than key
stroke dynamics, since much of the population does not use a keyboard regularly. Unique-
ness measures how a biometric feature varies across the population. For instance, the iris
has a higher uniqueness than hand geometry. While uniqueness measures the inter-user
variability, permanence measures the intra-user variability. Generally, physical biometric
features are more permanent than behavioral biometric features, since behavioral biometric
features are affected by a person’s mental status and environmental factors. Collectability
measures how easily a feature can be measured quantitatively. Physical biometric features
are usually easier to measure quantitatively than behavioral biometric features. However,
some physical biometric features, such as hand vein pattern and retina scans, generally
have lower acceptability, because they may reveal a person’s health status and this may be
regarded as an invasion of privacy.

Biometric technologies are evaluated in terms of their performance and vulnerability to
circumvention. Technologies using more unique and permanent biometric features usually
have higher performance. Some biometric technologies are more vulnerable to fiaud than
others. For example, 2D face recognition technologies are easier to spoof than 3D face
recognition technologies. Research on anti-spoofing technologies is addressing this issue

[44] [53] [24] [21].

1.2 Forensic Identification

There are two main purposes for forensic identification of humans: suspect identification
and victim identification. For suspect identification, evidence such as fingerprints, bite
marks, and blood samples are collected at crime scenes. Based on this evidence, the guilt
or innocence of the suspects can be confirmed. The goal of victim identification is to deter-
mine the identity of victims based on characteristics of the human remains. Based on the
number of victims involved, victim identification is categorized into two types: individual
victim identification and disaster victim identification. There is an urgent demand for an
automatic disaster victim identification system due to the recent occurrences of massive
disasters.

Victim identification can be achieved by matching antemortem (AM) and postmortem
(PM) circumstantial evidence and physical evidence [2]. The circumstantial evidence in-
cludes a victim’s clothing, jewelry, and pocket contents. If the antemortem description of
the same circumstantial evidence can be provided, it may assist in the victim’s correct iden-
tification. However, circumstantial evidence can easily be attributed to the wrong person,
particularly when there are many disaster victims to be identified. Physical evidence is
more reliable, and includes external evidence, internal evidence, dental evidence, and ge-
netic evidence [2]. External evidence includes gender, estimated age, height, build, color of
skin, etc. Specific features, such as scars, moles, tattoos, and abnormalities, are especially
useful if they can be matched with antemortem records, and fingerprints are valuable ex-
ternal evidences as well. Internal examination (autopsy) is often necessary for determining
the cause of death. An autopsy may also find medical evidence that can assist in iden-
tification, such as previous fractures or surgery, missing organs (e.g., appendix, kidney),
or implants. Dental evidence (such as fillings or missing teeth) is particularly important,
since it can offer sufficient information to positively identify a victim without the need for
additional information. The use of dental evidence for human identification is discussed

in the next section. Genetic identification involves comparing DNA samples from an indi-

vidual with antemortem DNA, or with DNA samples from the suspected victim’s ancestors
or descendants. Genetic identification is especially useful when the bodies of the victims
are severely mutilated. Table 1.1 compares the various methods of identifying victims in
terms of accuracy, time needed for identification, antemortem record availability (the pos-
sibility of obtaining antemortem evidence), robustness to decomposition (of the body) and
instrument requirement (number of instruments needed for matching).

Table 1.1. A Comparison of Evidence Types Used in Victim Identification

 

 

 

 

 

 

 

 

 

. . . PH sical
Evrdence type Circumstantial External Intema)l Dental Genetic
Accuracy Med. High Low High High
Time for Identification Short Short Long Short Long
Antemortem Record Availability High Med. Low Med. High
Robustness to Decomposition Med. Low Low High Med.
Instrument Requirement Low Med. High Med. High

 

 

1.3 Procedure of Comparative Dental Identification

Typically, unidentified human remains are reported to the law enforcement agencies who
then initiate a request for dental identification. Often a presumptive 'or tentative identifi-
cation is available (e.g., wallet or driving licence found on the body) and this will enable
antemortem records to be located. In other instances, using data from the missing persons’
database, the location where the body is found or other physical characteristics and circum-
stantial evidence may enable a putative identification to be made. Antemortem records are
then obtained from the dentist of the suspected missing persons.

The forensic dentist produces the postmortem record by careful charting and writing
descriptions of the dental structures and radiographs. An example of dental chart is shown
in Figure 1.1. If the antemortem records are available at this time, postmortem radiographs
should be imaged to replicate the type and angle of the antemortem records [33]. Ra-
diographs should be marked with a rubber-dam punch to indicate antemortem and post-

mortem to prevent confusion - one hole for antemortem films and two holes for postmortem

films [1].

Once the postmortem record is complete, a comparison between the two records can be
carried out. A methodical and systematic comparison is required to examine each tooth and
surrounding structures. While dental restorations play a significant role in the identification
process, many other oral features such as pathological and morphological characteristics
are assessed. Such additional features play an increasingly important role in those indi-

viduals with minimal restorations. Because of the progressive decrease in dental cavities,

 

 

8.6. CORONERS' SERVICE
Dam. locurmcntou Form

concus- casnn. lefllzm—
mrno-nue cm ML—
LOCAYION

[9m MIC W" CAI. I 1‘- l1! _
mu m m ___.11:_I.IL'L.
’OUCl m

react manure» MM.

out. MM!—
um-«vso- m MW

 

WWW

N.
"mam

it if

mi

 

“1“,” “In-“l.“
m

 

Dan-v.6-
coo-ea:
A on“ re. rumou- OI. hum I.
I Cayu- eta—c.— lh‘m n
u an moan—a— m.“ II.
n we... “Minimal—n .00“
II, 7m“ u. “out” tenant-v.1
I “it—d than II manna-urn It
1. Ina-d I Moth-Id IO lulu—Io...-
. w u l..- n moan-.- n
n I“. II who II a.“
C Civi— II “It! I. 'II‘ F
5 A...- ll mun so I-
v Ana-.- awn. II. can. It
Dun—onus». n/ a...
H“ . . .7-
........... ..... .../:

 

Figure 1.1. An example of postmortem dental chart [51].

so-called non—restorative cases are likely to become more common [46].

Similarities and discrepancies should be noted during the comparison process [55].

 

There are two types of discrepancy, those that can be explained and those that cannot.
Explainable discrepancies normally relate to the time elapsed between the antemortem and
postmortem records. Examples include teeth extracted or restorations placed or enlarged.
If a discrepancy is unexplainable, for example a tooth is not present in the antemortem
record but is present in the postmortem record then an exclusion must be made.

A range of conclusions can be reached when reporting a dental identification. The
American Board of Forensic Odontology recommends that these be limited to the following

four conclusions [1]:

0 Positive identification: The antemortem and postmortem data match in sufficient
detail, with no unexplainable discrepancies, to establish that they are from the same

individual.

0 Possible identification: the antemortem and postmortem data have consistent fea-
tures but, because of the quality of either the postmortem remains or the antemortem

evidence, it is not possible to establish identity positively.

0 Insufficient evidence: The available information is insufiicient to form the basis for

a conclusion.

0 Exclusion: the antemortem and postmortem data are clearly inconsistent.

It is important to note that there is no minimum number of concordant points or features
that are required for a positive identification. In many cases a single tooth can be used for
identification if it contains sufiiciently unique features. On the other hand, a full-mouth
series of radiographs may not reveal sufficient detail to render a positive conclusion [1].
The discretion of identification lies with the odontologist who must be prepared to justify

the conclusions in court [51].

1.4 Identification of Humans Using Dental Radiographs

Dental radiographs are one of the most valuable pieces of evidence for disaster victim
identification. This section begins with an overview of dental radiographs (also known as

dental X-rays) and then describes how dental radiographs can be used to identify victims.

1.4.1 Introduction to Dental Radiographs

There are three common types of dental radiographs (dental X-rays): bitewing, periapi-
cal, and panoramic. Bitewing X-rays (Figure 1.2(a)) are taken during most routine dental
check-ups and are useful for revealing cavities in the teeth. Periapical X-rays show the
entire tooth, including the crown, root, and the bone surrounding the root (Figure 1.2(b)).
One difference between periapical and bitewing radiographs is the imaging setup. For
bitewing radiographs, the film is parallel to the teeth and the X-ray beam is perpendicular
to both the teeth and the film. In contrast, periapical radiographs do not require that the
film be parallel to the teeth. In some cases, the film and the teeth are deliberately set not
to be parallel so that the whole tooth can be imaged on a small radiograph film. Periapical
X-rays are useful for diagnosing abscessed teeth and periodontal disease. The third type
of X-ray is the panoramic X-ray. As its name suggests, panoramic X-rays give a broad
overview of the entire dentition (the development of teeth and their arrangement in the
mouth). Panoramic X-rays provide information not only about the teeth, but also about
upper and lower jawbones, sinuses, and other hard and soft tissues in the head and neck
(Figure 1.2(c)). Panoramic films are entirely extraoral, which means that the film remains
outside of the mouth while the X-ray machine shoots the beam through other tissues from
the outside. Since it is entirely extraoral, panoramic radiographs work quite well for peo-
ple who cannot tolerate the placement of films inside their mouths. Another advantage
of panoramic film is that it takes very little radiation to expose it. The amount of radia-

tion needed to expose a panoramic X-ray film is about the same as the radiation needed to

 

(C)

Figure 1.2. Three types of dental radiographs. (a) A bitewing radiograph; (b) a periapical
radiograph; (c) a panoramic radiograph.

expose two intraoral films (periapical or bitewing). The disadvantage of panoramic radi-
ographs is that the resolution is lower than for intraoral images, which means the edges and
structures in the panoramic images are fuzzy.

For diagnosis and documentation purposes, dentists usually collect three types of den-
tal radiograph series: the initial full mouth series, the yearly bitewing series, and the
panoramic X-ray film. Figure 1.3(a) is an example of the initial full mouth series, which
combines bitewing and periapical X-rays to show a complete survey of the teeth and bones.
It consists of 2 or 4 bitewing films taken at an angle in order to look for decay, and 14 peri-

apical films taken from other angles to show the tips of the roots and the supporting bone.

In the full mouth series, each tooth is seen in multiple films. This redundancy helps dentists
create a mental image of the teeth in three dimensional (3D) space. A yearly bitewing series
(Figure 1.3(b)) consists of either 2 or 4 bitewing films. A bitewing series is the minimum
set of X-rays that most dental offices take to document the internal structure of the teeth
and gums. The third type of radiograph series consists of a single panoramic radiograph.
With the development of digital imaging technology, digital X-ray machines are becom-
ing popular in dental clinics. Digital dental radiographs have several advantages [11]: i)
compared to traditional radiographs, only half the dosage of radiation is needed for obtain-
ing a dental radiograph of comparable quality; ii) digital dental radiographs do not require
time needed for film development, so dentists need to wait for only a few seconds before the
acquired image is displayed; iii) dentists can take another image instantly if the acquired
image is not of good quality, so in general digital dental radiographs in a patient’s record
have better image quality than conventional dental radiographs; iv) digital radiographs are
easier to store and process, while conventional radiographs need to be digitized for image
processing; v) digital dental radiographs are environmentally fiiendly since they do not
generate chemical wastes used in film processing; vi) digital radiographs also have been
shown to have some diagnostic advantages for several diseases. Mainly due to their advan-
tages in speed, storage, and image quality, digital dental radiographs will be routinely used

for victim identification in the future.

1.4.2 Dental Radiographs for Identification

An individual’s dentition includes information about the number of teeth present, the ori-
entation of those teeth, and dental restorations. Each dental restoration is unique because
it is designed specifically for that particular tooth. An individual’s dentition is defined by
a combination of all these characteristics, and the dentition can be used to distinguish one
individual from another. The major challenge in the field of forensic dentistry is to deter-

mine how unique the features of an individual’s dentition are, and whether this information

 

(C)

Figure 1.3. Three types of dental radiograph series. (a) Full mouth series; (b) bitewing
series; (c) panoramic series.

is useful for identification purposes. The information about dentition is represented in the
form of dental codes and dental radiographs. The dental codes are symbol strings for de-
scribing the type of dental restorations, the presence/absence of the teeth, and the number of
cusps in the teeth, etc. Many studies have been done to define this characteristic of unique-
ness in dental codes for identification purposes. Adams concluded fiom his analysis [8]
[9] that when adequate antemortem dental codes are available for comparison, the inherent
variability of the human dentition could accurately establish identity with a high degree
of confidence. Adams further stated that the dentition is comparable in distinctiveness
to the human mitochondrial sequence because of the abundant combinations of missing,
filled, or unrestored teeth. Adams also noted that, like mitochondrial haplotypes, certain
dental restorations are more common than others. When the dental features or mitochon-
drial sequences are unique, both techniques have the potential to produce identifications
with high statistical certainty. However, both methods suffer when common characteristics
(e. g., common dental restorations) are encountered.

One challenge to future efforts in forensic identification based on dental codes is the
decline in the number of dental restorations that is attributed to increased awareness of
dental hygiene. While general descriptions of dentition can be quite useful for excluding
possible identities in cases where a limited number of identities are possible, large scale
efforts to identify victims based on dentition are hindered when only dental codes are avail-
able. The availability of antemortem dental radiographs in addition to dental codes allows
individuals with common dental characteristics to be distinguished from one another based
on visual features in the images.

Forensic identification of humans based on dental information requires the availability
of antemortem dental records, including dental radiographs, written records, tooth molds
and photographs. Antemortem radiographs should be obtained if possible. The antemortem
dental radiographs may have been acquired in several situations. Taking dental radiographs

is very routine during the dental clinical visits in United States and Britain. Also in the

11

 

Figure 1.4. A forensic expert examines a dental radiograph film of a tsunarrri victim in
Phuket, Thailand, on Jan. 11, 2005 [3].

United States and some other countries, newly recruited soldiers are required to have den-
tal examinations that include taking their dental radiographs. The discovery and collec-
tion of antemortem records is ordinarily the responsibility of investigative agencies. These
agencies might locate records fiom sources such as hospitals, dental schools, health care
providers, dental insurance carriers, public aid insurance administrators, and the FBI Na-
tional Crime Information Center (N CIC). Other resources include military service, judicial
detention, oral surgeons, orthodontists, etc.

Recent disasters have brought the significance of dental identification to the public’s
attention. For example, in the terrorist attack in the United States on Sept. 11, 2001, many
victims were identifiable only from pieces of jaw bones. Dentists were asked to help in
identifying the victims using dental records and about 20% of the 973 victims identified in
the first year after the 9/11 attack were identified using dental records [47]. A large number
of victims of the 2004 Asian tsunami were also identified based on dental information. As
reported in [59] and [6], 75% of the tsunami victims in Thailand were identified using
dental records, 10% by fingerprints, and just 0.5% using DNA profiling. The remaining
victims were identified using a combination of techniques. Figure 1.4 shows a forensic

expert identifying a 2004 Asian tsunami victim based on radiographs.

1.5 Automatic Dental Identification

Identifying the 2,749 victims of 9/11 disaster took around 40 months [7], and the number
of Asian tsunami victims identified during the first 9 months was only 2,200 (out of an esti-
mated total of 190,000) [6]. The low efficiency rate of current manual dental identification
methods makes it imperative that forensic science and computer science researchers work
together to develop algorithms to automatically identify disaster victims. There have been a
number of attempts to utilize machine intelligence techniques to facilitate the identification
of victims. However, none of the existing approaches are based on a fully automatic inter-
pretation of dental radiographs, so a human expert is needed for final victim identification.

This section begins with an overview of existing software for matching dental records
to forensic evidence. This section also introduces the proposed system for automating the
use of dental radiographs for victim identification and discusses some of the challenges for

this proposed system.

1.5.1 Available Software for Matching Dental Records to Forensic Ev-

idence

The most widely used software for matching dental remains to forensic evidence is WinID
(http://www. WmID.com). This matching system uses information entered into the system
by dental experts, including a series of dental characteristics regarding restoration and den-
tition descriptions (shown in Figure 1.5). The system then analyzes the manually input
characteristics and generates a ranked list of possible identities based on similarities be-
tween the input characteristics and existing database entries [45]. The matching accuracy
depends on the presence of dental restoration and abnormalities, which are becoming less
prevalent due to increasing awareness of dental hygiene.

Another software package, called OdontoSearch

(http://wwwjpacpacom.mil/CIL/entryhtm), can help determine the frequency of a

13

 
     

5678910111213141516
28272825+2423222120191817

Figure 1.5. Dental radiographs and the corresponding description chart used by WinID
system. The crosses indicate the missing teeth, and the filled squares indicate locations of
the dental restorations in each tooth.

certain dental pattern in the population. This system utilizes a large sample set that is
demographically and temporally distinct. The database contains the coded dental profile
information, such as presence or absence of teeth or of restoration. This package reduces
some of the subjectivity associated with determining the similarity of dental profiles, and
allows forensic odontologists to infer the likelihood of a particular identification. However,
the OdontoSearch software cannot be used to search for a victim’s identity; it can only
determine how common a particular dental profile is within the profile database.

In situations where antemortem radiographs are not available, it is difficult to determine
the strength of a match between antemortem and postmortem dental profiles because the
dental profile does not provide precise information about the dentition. The criteria for
determining the strength of a match between two profiles are vague and subject to the
opinion of the expert who analyzes the data. While fewer points of concordance are needed
to establish a match between radiographic evidence than what is needed to establish a match
between coded records, the exact number of points of concordance needed to establish a
match is not universally agreed upon by the forensic Odontology community [1]. As stated
by Gustafson [35], “it would be unlikely for any two individuals to have identical dental

characteristics, but it is quite possible for two people to have similar data on their dental

14

charts.”
The pros and cons of WinlD and OdontoSearch are compared in table 1.2.

Table 1.2. A Comparison of WinID and OdontoSearch

 

 

Pros Cons -
W'nID Retrieves subjects based on 0 Features are extracted manually
I descriptions of dentition 0 Does not work for dentition Without

dental work

 

0 Cannot be usedTor subject retrieval
OdontoSearch Measures reliability of a match 0 Features are manually extracted

0 Does not work for dentition without
dental work

 

 

 

 

 

1.5.2 Dental Radiograph-based Automatic Identification System

Existing software for matching dental records to forensic evidence is based on dental de-
scription codes entered by human experts. The reduced prevalence of dental restorations
limits the usefulness of matching methods based on dental descriptions and encourages
continued research on the use of dental radiographs for identification. The goal of the pro-
posed dental identification system is to automate the identification procedure and to explore
new features for identification other than dental restorations and abnormalities. Figure 1.6
diagrams the proposed system for automatically identifying human subjects based on den-
tal radiographs.

The first step in automatically identifying human subjects from dental radiographs is
to extract features from the radiograph. An image quality evaluation fiinction assesses the
quality of the image before it is processed. A warning message is issued to request user
interaction during the following steps if the quality of the image is assessed as poor. The
features extracted for matching purposes are the contours of teeth and the contours of dental
work. Before extracting these features, the radiographs are segmented into regions so that
each region contains only one tooth. Boundary extraction methods are then applied to each
region of the image to extract the contours of each tooth and dental restoration. An active

shape model is trained and used for tooth contour extraction. To enhance radiograph images

15

 

Feature Extraction (Chap. 2)

 

 

L Image Quality Evaluation

I

L Radiograph Segmentation I

 

 

 

[ Tooth Contour Extraction I

 

 

L Dental Work Swflentation I

I

Atlas Registration (Chap. 3)

i

Matching Radiographs (Chap. 4)

 

 

 

 

 

 

 

 

 

Matching Contours of Matching Regions of
Teeth Dental Work
f 1
I Fusion j
I

Subject Identification

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 1.6. System diagram of automatic dental identification system.

and segment regions of dental work (including crowns, fillings, and root canal treatment),
anisotropic diffusion is used. A monitoring scheme is developed to monitor the results of
radiograph segmentation and tooth contour extraction. User interaction is requested if the
results are erroneous. Chapter 2 describes the feature extraction process in more detail.
The second step, described in Chapter 3, is to register the radiographs to the human
dental atlas, which is a descriptive model of the shape and relative positions of teeth. This
registration step is important because the matching algorithm cannot properly align two
sequences of teeth if they do not contain the same number of teeth. Missing teeth can
be detected by labeling the existing teeth based on known dental anatomy. The anatomy-

based tooth labeling can also accelerate the image matching stage, since a pair of PM-AM

16

images need not be matched if they do not share the same label. To label the teeth with
anatomical indices, the dental radiographs are registered to the human dental atlas, which
is a descriptive model of the shapes and relative positions of teeth. We propose a hybrid
model involving Support Vector Machines (SVMs) and a Hidden Markov Model (HMM)
for representation of the dental atlas and estimation of the tooth indices in dental radi-
ograph images. A monitoring scheme is also developed to assess the results of automatic
registration. Questionable registration results are interactively corrected by the system user.

Corresponding teeth from a PM and an AM radiograph are matched in the third stage
of the matching system, which is described in Chapter 4. Tooth contours are matched for
every pair of corresponding teeth, and if dental work is present in both the teeth, the dental
work is also matched. A method is prOposed for computing the distances between the
given unidentified subject and all the database subjects based on the tooth indices obtained
by registering the radiographs to the dental atlas. The database subjects are then sorted in
ascending order of the matching distances and the results are presented to forensic experts
for final analysis. Just as in other human identification systems, user interaction may be
necessary in our system [58] [52].

Figures 1.7 and 1.8 show the process of matching two pairs of AM and PM images with-
out and with user interaction for correcting errors during segmentation, contour extraction,

and atlas registration.

1.5.3 Challenges

One major challenge in automatic identification of dental information is the poor image
quality of dental radiographs. Whether due to incorrect operation of the X-ray equipment
during image acquisition or digitization, to irregular arrangement of teeth, or to degradation
of the radiograph films, the contours of teeth often appear to be blurred and the different
tissues contrast poorly in many radiographs. These factors make it difficult to automatically

extract edge features and tooth boundaries from the radiographs.

l7

Post-mortem Image Ante-mortem Image

Input
Images

 

Image
Segmentation

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Contour
Extraction
Atlas 2 3 4 5
Registration 31- 30 2928
30 29 28
Upper Row I Lower Row
Matching 30 29 28

3 4

Matching Distance = 2.41 Matching Distance = 5.30

Figure 1.7. Fully automatic process of matching one pair of PM and AM images from the
same subject.

PM Image AM Image User Correction

 

   
    

Segmentation

I

I

I

Input ‘ I

Images I

I

I

I

Image I
'T’

I

 

 

 

 

 

I
Contour .' I
Extraction _:_,
/:
I
Atlas 1213 14 15 I
Registration 20 19 ‘8 -‘_) .
14 15 16 : 13 ‘4 '15

 

 

 

 

 

 

 

 

 

 

Matching 14 15 7 CP
13 C)

Tooth Contour Dental Work
Matching Distance = 20.41 Matching Distance = 0.93

Figure 1.8. Automatic matching of one pair of PM and AM images with user interaction.

A second challenge is changes in the dentition over time, such as tooth eruption and
loss, the emergence, abrasion, falling and replacement of dental restorations, the sliding
of neighboring teeth after a tooth is extracted, orthodontic operations, etc. These changes
cause inconsistent appearances of teeth in AM and PM radiographs fi'om the same indi-
vidual and are difficult to model. An example of a difficult identification case is shown in
figure 1.9. The quality of the images is poor due to inappropriate exposure, and the ortho-
dontics operation (shown in the AM images) and a number of missing teeth (shown in the
PM images) have significantly changed the dentition appearance over time.

A third challenge in automatically identifying humans based on dental information is
the changes in the imaging angle. Since dental radiographs are 2D projections of 3D struc-
tures, changes in the imaging angle result in complex deformations in the 2D projections
that are difficult to model without any information about the 3D dimensions of the teeth.
Changes in the imaging angle are smaller for bitewing and panoramic images than for pc-
riapical images, because of the fixed setup for acquiring bitewing and panoramic images.
Figure 1.10 shows an AM-PM image pair in which the changes in the imaging angle result
in significant deformations in the periapical radiograph images.

A fourth challenge is the insufiiciency of data in dental radiograph databases. We ob-
tained dental radiographs fiom three sources. The first source is the F Bl’s Criminal Justice
Information Service (CJ IS) division, which is interested in utilizing dental radiographs for
identifying Missing and Unidentified Persons (MUPs). The second source is the Wash-
ington State Police Department, and the third source is Dr. Howell, a professor in the
Department of Oral and Maxillofacial Pathology at West Virginia University. The three
data sets are combined into a database containing 33 subjects, each with a number of AM
and PM images. If we view upper and lower rows of teeth as separate sequences, there are
a total of 360 PM and 316 AM dental sequences, containing a total of 810 PM teeth and
892 AM teeth. Figure 1.11 shows some of the images in the database. A larger database

used in the experiments contains 100 unmatched AM subjects, which are composed of 748

20

 

Figure 1.9. Antemortem (a) and postmortem (b) radiographs of a difficult identification
case for an automatic matching system. The poor image quality poses difliculties for con-
tour extraction. The orthodontics operation in (a) and missing teeth in (b) have significantly
altered the dentition appearance over time.

21

 

(a) (b)

Figure 1.10. Changes in the imaging angle result in significant deformations in the appear-
ances of corresponding teeth in (a) AM and (b) PM periapical radiograph images.

AM sequences and 2,379 AM teeth. The small number of subjects in the database makes
it difficult to provide a sufficient ntunber of matched pairs for training and performance

evaluation of the system.

1.6 Summary

Human identification using dental radiographs is an important but very challenging re-
search topic. This chapter introduced the background on forensic identification of humans,
especially the dental radiograph-based approach. Challenges to automatic processing and
matching of dental information were also discussed, and each stage in the proposed auto-
matic identification system was described. The following chapters detail each stage of the

proposed automatic system for human identification based on dental information.

22

CHAPTER 2

Segmentation and Contour Extraction

This chapter introduces methods for evaluating image quality, segmenting radiographs and
extracting features from dental radiographs. Image quality affects the accuracy of auto-
matic algorithms in all the processing stages. To detect images of poor quality, an image-
quality evaluation method is designed to identify difficult images and request user interac-
tions after the automatic processing results are produced.

The features extracted from dental radiographs for matching purposes are the contours
of teeth and the contours of dental work, such as crowns and fillings. In order to automati-
cally extract these features, the radiographs are first segmented into regions such that each
region contains only one tooth. Contours of teeth and dental work are then extracted from
each region.

We propose a method for segmenting dental radiographs based on fast marching al-
gorithm [54]. To correct the segmentation errors, an interactive semiautomatic method is
also developed. We also propose a method for extracting the contours of teeth using active
shape models. Dental work, such as crowns, fillings, and evidence of root canal treatment
are composed of radio-opaque materials, like silver, gold, and CaOH. These materials ap-
pear as bright regions in radiographs. To identify the dental work contours, an anisotropic

diffusion-based technique is used to enhance the radiographs. The regions of dental work

24

 

are then segmented using image thresholding.

2.1 Automatic Image Quality Evaluation

Images of poor quality pose difficulties at every stage of feature extraction and matching.
In our database, all the radiograph images were scanned from photographic films, which
reduces the number of levels of intensity and introduces problems such as over-exposure.
Due to the fact that the AM images were usually acquired many years before they were
actually scanned and were stored in non-ideal condition, there is also loss of contrast and
resolution.

Evaluation of image quality is needed so that for poor quality images, the system user
can interactively correct the results obtained automatically. The evaluation of image quality
consists of the following steps:

1. Detection of panoramic images;
2. Detection of intensity imbalance;
3. Detection of image blurring.

The details of these steps are given below.

2.1.1 Detection of Panoramic Images

Since panoramic images have more teeth than bitewing and periapical images, when scaled
to a certain size, panoramic images have more high frequency components and fewer low
frequency components compared to bitewing and periapical images. The detection algo-
rithm is as follows:

1. Image is first scaled so that the longest side of the resulting image is 256 pixels;

2. A Fast Fourier Transform is applied to obtain a 256 x 256 image in fiequency domain,
and the magnitude of the components of fi'equency at 1 / (256pixels) is computed;

3. If the magnitude of the frequency at 1/(256pixels) is less than a threshold value

25

(3,400,000), the image is a panoramic image. Otherwise, it is a bitewing or periapical
image. The threshold value was empirically determined.

Experiments on 206 randomly selected images (51 panoramic images and 155 bitewing
and periapical images) showed that only 3 panoramic images and 4 bitewing/periapical

images were misclassified using this algorithm.

2.1.2 Detection of Intensity Imbalance

Intensity imbalance means that the images are over-exposed, under-exposed, or partially
over-exposed and/or partially under-exposed. The rules for detecting intensity imbalance
are as follows:

1. If more than half of all pixels in the image are darker than l/4th of the intensity range
(255 in our experiments), the image is under-exposed (Figure 21(3));

2. If more than half of all pixels in the image are brighter than 3/4th of the intensity range
(255 in our experiments), the image is over-exposed (Figure 2.1(b));

3. Segment the image into four equally sized blocks (upper left, upper right, lower left, and
lower right). Calculate the mean pixel intensities of the blocks, and calculate the standard
deviation of the mean intensities (STDM I). If STDM I is larger than 25, the image is not
homogeneously exposed (Figure 2.1(c)).

a:
a .
r?

   

Figure 2.1. Detection of intensity imbalance. (a) An over-exposed image; (b) an under-
exposed image; (c) an non-homogeneously exposed image with STDMI = 30.

26

2.1.3 Blur Detection

Due to out-of-focus errors during image acquisition, the image may appear to be blurred,
which poses difliculty for feature extraction. To detect the blur, a Gaussian kernel of 5 x 5
pixels with a = 0.5 is convolved with the original image. The Mean of the Absolute
Difference (MAD) between the original image and the result of convolution is used to
detect the blur. If the original image is blurred, the MAD value will be small since the
convolution does not significantly increase the degree of blur. In practice, images with
MAD < 2 are categorized as blurred images. Figure 2.2 shows two images, one detected

as a sharp image (Figure 2.2 (a)) and the other as a blurred image (Figure 2.2 (b)).

 

(*0 (b)

Figure 2.2. Detection of blur. (a) A sharp image with MAD = 2.35; (b) A blurred image
with MAD = 1.08.

2.2 Radiograph Segmentation

The goal of radiograph segmentation is to find the region of interest (ROI) associated with
every tooth in the image. For simplicity, we assume there is only one row each of maxillary
(upper jaw) and mandibular (lower jaw) teeth in the image. This assumption is usually true,
except for children who are at the stage of losing their primary teeth. For them, both the
rows of permanent teeth and the rows of primary teeth are present in dental radiographs

(Figure 2.3). Once the upper and lower rows of teeth are separated, each tooth needs to

27

 

Figure 2.3. A dental radiograph of a child showing both permanent teeth and primary teeth.

be isolated from its neighbors. A method based on fast marching algorithm is proposed to
automate the whole segmentation process. In general, radiograph segmentation has three
steps:

1. Segmentation of upper and lower rows of teeth;

2. Detection of the presence of upper (lower) rows of teeth;

3. Isolation of neighboring teeth in each row.

The details of each step are given in the remainder of this section.

2.2.1 Automatic Segmentation

Fast marching methods [54] find the shortest path between a set of start points and a set
of end points in an image by propagating a wave from the start points. When the wave
front touches one of the end points, the shortest path is established by tracking the steepest
gradient descent from the touched end point back to the start point. The wave propagation

is described by the Eikonal equation [54]:
IVTIF(z.y) = 1, (2.1)

where T is the wave front, and F(a:, y) is the propagation speed. Equation (2.1) can be

solved efficiently by using heaps, which allows the solution to be obtained in a reasonable

28

amount of time.
The speed parameter in the fast marching algorithm depends on the application. In
order to detect the paths that segment teeth in radiographs, the propagation speed is set as

a fimction of the pixel values:
F(a:, y) = ((max —I(:r, y))/(max — min»2 + 0.01, (2.2)

where I (:13, y) is the gray level value of the pixel at point (11:, y), and min and man: are the
minimum and the maximum intensity values of pixels in the image. The speed configu-
ration sets lower propagation speed for pixels of higher gray values (brighter), and higher
propagation speed for pixels of lower gray values (darker). Bright pixels correspond to
teeth and darker pixels correspond to soft tissue and air. So, the wave propagates more
slowly along the tooth pixels than along the pixels of other tissues.

The line segmenting the upper and lower rows of teeth is detected first. A wave prop-
agates from the left side of the image and ends at the right side of the image. The wave
propagates faster in the area between the upper and lower rows of teeth because it has lower
gray values than the tooth pixels. Thus, the fastest path must pass through the area that sep-
arates the two rows of teeth. The fastest path is the line (denoted as so) segmenting the
upper and lower rows of teeth.

The presence of upper and lower rows of teeth is detected by using the position of the
separating line, so. Denote the y coordinates of points in the segmentation line so as soy,
and the height of the image as H (see Figure 2.4). The following classification rules are

used to determine which rows of teeth are present in the image:

0 if min 322,, 2 %H and max 32),, g gH, then there must be two rows of teeth in the

image; otherwise,

0 if min 322,, < éH, then there should be only the lower row of teeth in the image;

otherwise,

29

o if max 312,, > %H, then there should be only the upper row of teeth in the image.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Figure 2.4. Classification of image types based on number of rows of teeth. (a) and ((1)
images with two rows of teeth; (b) and (e) images with only lower row of teeth; (0) and (f)
images with only upper row of teeth.

Once the upper and lower rows of teeth are segmented, the neighboring teeth in each
row are isolated using the fast marching method, which finds the separating lines that orig-
inate at the segmentation line so and propagate either to the top or bottom of the image
through gaps between the teeth. The gray values of the pixels in the regions between the
teeth are also lower than the gray values of the tooth pixels, so the speed parameter is set
the same way as in Equation (2.2). There are two steps for isolating teeth in the upper row:

1) Finding knots in the segmentation line so. Denote the points where the lines

30

 

CUTVC C

 

 

 

 

Figure 2.5. Finding knots in the segmentation line.

separating neighboring teeth touch the segmentation line, so, as knots. Sum up values of
the pixels above the segmentation line so (inteng projection) to form a curve, C. Knots
in the segmentation line so are points having the same sis-coordinates as the valleys in the
curve, C. Figure 2.5 illustrates the curve C and the knots.

2) Finding the isolation lines. For every knot t, find the shortest path fi'om t to the top
of the image. This fastest path always goes through the gap between neighboring teeth and
isolates the two teeth.

The algorithm for segmenting individual teeth in the lower row is the same as for seg-

menting teeth in the upper row. Figure 2.6 shows some results of successfirl automatic

31

 

Figure 2.6. Some examples of correct segmentation.

segmentation.

Table 2.1 shows the results of applying the automatic radiograph segmentation algo-
rithm to 611 dental radiograph images. On average, the entire segmentation process (im-
plemented in C) takes ~ 2.5 seconds for a 300 x 250 image containing 8 teeth on a PC
with a 2.99 GHz Pentium 4 processor. There are four types of errors that our algorithm
makes (see Figure 2.7): incorrect location of segmentation line between upper and lower
teeth, under segmentation, over segmentation, and improper segmentation. The first type
of error occurs when the dental work present in upper and lower rows of teeth appears to
be connected to form a single block in the radiographs. In this situation, the wave does not
propagate sufficiently fast through the middle of the block, so the estimated separating line
tries to avoid the dental work and therefore segments the upper and lower rows of teeth
incorrectly (Figure 2.7(a)). This type of error also occurs when the space between upper
and lower rows of teeth is not fully captured in the radiograph (Figure 2.7(b)). The under
segmentation errors occur when the dental work or teeth overlap in the radiograph, leaving
the gap between the teeth invisible (Figure 2.7(c)). Over segmentation errors occur when
the space between cusps of a tooth creates a valley in the integral projection and the pixel
intensity of the teeth is not sufficiently high to block the propagation of the wave (Figure
2.7(d)). Improper segmentation refers to the result in which the segmentation line goes

through the inside of a tooth. This is caused by the overlapping dental work, which blocks

32

the propagation of the wave at the gap between teeth (Figure 2.7(e)).
Table 2.1. Results of Automatic Radiograph Segmentation

 

 

Segmentation Results Percentage

Correct Segmentation 61 . 1° 0

Incorrect Segmentation Line Between Upper and Lower Teeth 11.1%
Under Segmentation 17.8%

Over Segmentation 3.0%

Improper Segmentation 7.0%

 

 

 

 

2.2.2 User Interaction
An algorithm is developed for detecting the following types of aberrant segmentation lines:

1. The segmentation line between upper and lower rows of teeth passes through the
middle of teeth (Figure 2.7(a)). This type of error is detected if the variation of the

pixel intensities along the segmentation line is larger than 100.

2. The segmentation line between upper and lower rows of teeth has sharp turns due to
the upper and lower teeth biting together and blocking the wave propagation during
detection of the segmentation line (see Figures 2.7(b) and 2.8(a)). This type of error
is detected if the largest gradient in y coordinates of the segmentation line is larger

than 20 pixels.

3. Under segmentation and over segmentation (Figures 2.7(c), (d) and (e)) are detected
by computing the ratio of maximum interval to minimal interval between isolation

lines. If the ratio is over 2, a warning message is issued.

Interactive methods based on fast marching algorithms have been developed to assist
the system user in correcting all the above segmentation errors. After a user specifies some
points in the image that the correct segmentation line must pass through, the fastest paths
are established between the specified points and the original starting and ending points, and
all line segments are then connected to form the final segmentation line. Figures 2.8, 2.9,

2.10, and 2.11 show user interactions for correcting the four types of segmentation errors.

33

 

Figure 2.7. Some results of incorrect automatic segmentation. (a) and (b) incorrect location
of segmentation line between upper and lower rows of teeth; (c) under segmentation; (d)
over segmentation; (e) improper segmentation.

34

 

 

 

 

 

 

(a)

Figure 2.8. User interaction for correcting of the first type of error: incorrect location of
segmentation line between upper and lower rows of teeth. (b) Correction of the incorrect
segmentation line between upper and lower teeth in (a) by specifying one point (shown as
cross).

 

 

 

 

 

 

 

(a) (b)

Figure 2.9. User interaction for correcting of the second type of error: under segmentation.
(b) Adding an isolation line in (a) by specifying one point (shown as cross).

35

 

 

 

 

 

 

 

 

(8) (b)

Figure 2.10. User interaction for correction of the third type of error: over segmentation.
(b) Removing an extra isolation line in (a) by specifying one point (shown as cross).

 

 

 

 

 

 

 

(a) (b)

Figure 2.1 1. User interaction for correction of the fourth type of error: improper segmenta-
tion. (b) Correction of an improper segmentation by removing the improper segmentation
line in (a) by specifying one point (shown as cross in (a)) and adding correct segmentation
lines by specifying two points (shown as cross in (b)).

36

2.3 Extracting Tooth Contours

A region of interest (ROI) for a tooth is defined as an enclosing rectangle that tightly fits the
segmented area (Figure 2.12). We propose an algorithm for extracting the tooth contours

using active shape models.

 

Region of Interest

Figure 2.12. Region of Interest (ROI) for a tooth.

2.3.1 Introduction to Active Shape Models

Active Shape Models (ASMs) [23] are deformable models used for shape extraction. Un-
like the active contour models (snakes), ASMs incorporate statistical global constraints on
shapes. ASMs utilize the Principal Component Analysis to discover the principal modes
of deformation among training shapes and find the most plausible shapes in the image with
respect to the detected principal deformation. The details of the algorithm are introduced
as follows [57]. Consider N planar training shapes each consisting of n boundary points.

Let each shape be represented as:

xi:[mama...,m;,y[,y§,...,yf,]T,i=1,...,N, (2.3)

37

where (11:3,, yt), k = 1, ..., n is the coordinate of point k in the ith shape. A linear orthogonal
transformation, M, of the data is designed to obtain the compact representation of xi,

denoted as z,, where

Z, = M(Xi - i),
i — 1 N x (2.4)
— N i=1 1,

so that the covariance matrix of z, is a diagonal matrix. The mean of the z-variables can

then be expressed as:

1 N 1 N
Z=N§zi=M- N;(xi—i)]=0. (2.5)
The shape covariance matrix of x, is defined as
1 N _ _ T
2.. = N g... — xxxi — ) . (2.6)

The covariance matrix of z, is defined as

1 N
Ez = — (Zi — E)(Zi — E)T
N :2; (2.7)

= szMT.
Since M is orthogonal, i.e., M’1 = MT, equation (2.7) can be changed into the following:
ZXMT = MTzz. (2.8)

So a possible solution for MT is the (column) eigenvectors of the covariance matrix 23,,
and the diagonal of the covariance matrix 2, contains the corresponding eigenvalues. Ac-

cording to equation (2.4),

x, = it + MTzi, (2.9)

38

where each eigenvector column in MT represents a typical variation among the shapes.
This gives a different perspective on shapes: a particular shape can be viewed as the mean
shape plus the sum of the weighted principal deformations. With this view point, the prob-
lem of detecting a shape is reduced to finding the correct coefficients, 2,.

There are usually three steps in applying ASMs to shape extraction problems:

1. Shape Alignment: Align training shapes to find the corresponding points;

2. Modeling Shape Variation: Find eigenvectors of the covariance matrix of the shapes,

and the appropriate number of eigenvectors for representing the shape variations;

3. Shape Extraction: Use the statistical shape model to extract shapes fiom images.

The remainder of this section provides details of the above steps for extracting tooth

contours.

2.3.2 ASM-Based Tooth Contour Extraction

In this section, we introduce the method for aligning the training tooth contours, provide a
method for modeling shape variations including scaling and rotation, and describe a proce-

dure for using the trained model to extract tooth contours in dental radiographs.

Shape Alignment

Before aligning training shapes, a prototype shape is created manually (Figure 2.13(a)). a
precise definition of prototype shape is not needed; a typical shape of teeth with approx-
imate height and width is good enough. It is used for aligning all three types of teeth:
incisors, (bi)cuspids and molars. The training shapes are aligned to the prototype shape by
first rotating them so that their tightest bounding boxes are in the upright positions. Then
training shapes are scaled so that their heights become the same as the prototype (Figure

2.13(a)). Given a point x0 in the prototype and a point set X, which contains points in

39

an aligned training shape, xo’s corresponding point x in the training shape is detected as
follows:

x=argmin||x’—xo||, (2.10)
x’EX

where H - || represents the Euclidean distance.

Modeling Shape Variation

Traditional ASMs do not model scaling and rotation. To use the traditional ASMs for shape
extraction, an additional linear transformation, including translation, scaling, and rotation,
has to be imposed on the nonlinear transformation modeled by the ASMs. Both the ASM-
based nonlinear transformation and the linear transformation take place simultaneously, but
are handled sequentially, which is not only time consuming, but also makes it difficult to
find an optimal solution.

We propose to solely use ASMs to represent the overall transformation, including scal-
ing and rotation. To incorporate the scaling and rotation into the ASM model, scaling
and rotation are applied to training shapes after point correspondence between the training
shapes and the prototype shape has been established. Figures 2.13 (b) and (c) show the ro-
tated and the scaled training shapes corresponding to the original training shape in Figure
2.13 (a).

After the shape alignment is done, the principal modes of deformation are extracted as
the eigenvectors of the covariance matrix of the shape vectors. Figure 2.14 shows the first
five modes of shape variation captured by the trained model. The first mode indicates the
scaling of shapes (Figure 2.14 (a)). Since the deformation of this mode is the shrinkage of
all nodes towards the middle point of the shape, after the scale of a shape shrinks to zero,
the orientation of the shape is inverted. The second mode indicates the rotation of shapes
(Figure 2.14 (b)). The third mode indicates the variations in widths of tooth shapes (Figure
2.14 (e)). The fourth mode indicates the variations in the two ends of the shapes (Figure
2.14 (d)). The fifth mode indicates the shape variations in the tooth crowns (Figure 2.14

40

 
     
   
    
      
   
   

A Training

Prototype Shape\

Shape

(a)

A Rotated
Training
Shape

Prototype _'
Shape .

(b)
A Scaled
Training
Prototype Shap
Shape e\

(C)

Figure 2.13. Shape Alignment. (a) correspondence between a prototype shape and a train-
ing shape; (b) correspondence between the prototype shape and the rotated training shape;
(c) correspondence between the prototype shape and the scaled training shape.

41

(6))-

Shape Extraction

An algorithm for tooth contour extraction is given in Figure 2.15.

 

Algorithm: Tooth Contour Extraction

1. Image Enhancement. The input image is enhanced using the anisotropic dif-

fusion to remove noise.

2. Gradient Computation. Salient edges in the enhanced images are detected
using the Canny edge detector and a smoothed gradient field is computed

based on the gradients of the detected edges.
3. Shape Evolution. The iterative procedure has the following steps:

(a) Initialize the current shape.
(b) Use ASMs to approximate the current shape.

(0) Search for optimal positions for all nodes in the mOdel based on the

current ASM-approximated shape.

((1) Replace the current shape with a smoothing spline, which connects de-

tected optimal positions of the nodes.

(e) Repeat steps (b) to ((1) five times to guarantee the convergence of shape

evolution.

 

(f) Output the current shape.

 

 

Details of each step are given below.
Image Enhancement
The input images are enhanced using the anisotropic diffusion algorithm, which is de-

scribed in detail in Appendix B.

42

Figure 2.14. First five modes of the shape model of teeth. The middle shape in each row
is the mean shape, while the other four shapes are, from left to right, mean shape plus
four eigenvectors multiplied by -2, -1, 1, and 2 times the square root of the corresponding

eigenvalues.
43

 

Input Image Smoothed Image

Iteration

 

      

Spline approximation Tooth Contour

Figure 2.15. Shape extraction procedure.

Gradient Computation
We use a smoothed gradient field to guide the shape evolution. The smoothed gradient field

is constructed in the following steps:

1. Edge Detection. The salient edges in the enhanced images are detected using the

Canny edge detector.

2. Gradient Smoothing. A method inspired by Gradient Vector Field (GVF) [63] is used
to construct the smoothed gradient field. Let the original gradient field be (no, v0),
where for the edges detected in the previous step, uo and v0 are the gradients in a: and
y directions, and for other pixels, no and v0 are zeros. Let u and v be the objective

smooth gradient field that minimizes the energy E defined as follows:
E = f/Mui +u§ +v: +v5) + (no2 +v02)((v — v0)2 + (u — u0)2)d:z:dy, (2.11)

where [I controls the smoothness of the field, 11,, and u,, are the gradients of u in x
and y directions, and vx and v3, are the gradients of v in :1: and y directions. The

minimization procedure is the same as the GVF [63].

Shape Initialization
Given the ROI of the tooth, the tooth shape is initialized as the shape of ‘n’ (for lower row
of teeth) or the shape of ‘U’ (for upper row of teeth) in the middle of the ROI (Figure 2.16).
For the lower row of teeth, the width of the initialized shape is 1/3rd of the width of the
ROI, and the height is the same as width of the ROI. The distance between the top of the
shape and the top of the R01 is l/8th of the width of the shape.

Approximate a Shape with ASM
Since shape rotation and scaling have been incorporated in the ASM model using the train-
ing techniques introduced in Section 2.3.2, the approximation procedure is simplified into
a linear regression problem in vector space. To be robust with respect to noise in detected

positions of boundary points, robust weighting is used [4]. The details of the approxima-

45

Initialization
ofShapes

 

Figure 2.16. Initialization of tooth shapes.

tion algorithm are as follows. Let the shapes to be approximated be represented as a vector
V = lamb, ...,xn,y1,y2, ...,yn]T. Let the mean shape of the trained ASM be denoted
as M = [$1m, $2,", ..., rum, y,,,,, 312,", ..., yum]T, and the eigenvectors of the trained ASM
denoted as e,-, i = 1, 2, ..., N — 1, where N is the number of training shapes. Denote the
number of eigenvectors used for shape extraction as lc (k = 10 for tooth shape extraction
since top-10 modes can explain 98% of variations in tooth shape [23]), the coefficient vec-
tor for those lc eigenvectors as c, and the translation as (:5, y). The objective firnction for

shape approximation is defined as

{c,:r,y} = arg min J, (2.12)
{0.1.31}

46

where
J = LTWL,
L: (M+E-p)—V,g
W = diag(w),

E = [81, 32; “-9 ek) 8X3 93’]?

ex = [1, 1,0, ...,0]T,
nl’s nO’s

e =| ,...,0,1,...,1|T,

y nO’s nl’s

p = [5.13.1117

(2.13)

The weights w are obtained using robust weighting [4], which is described as follows.

1. Calculate the residuals between the input shape and the appropriate shape obtained

by using uniform weights.

2. Compute the robust weights for each point on the boundary. The weights are given
by the bisquare firnction shown below.
1— (my, if|r,-| < 3 . MAD
11),; = , (2.14)
0, if|r,;| 2 3 . MAD

where r,- is the residual of the ith data point, and MAD is the median absolute value

of the residuals:
MAD = median(|r|). (2.15)

The median absolute value is a measure of how spread out the residuals are. If r,- is
small compared to 3 - MAD, then the robust weight is close to 1. If r,- is greater than

3 - MAD, the robust weight is 0 and the associated data point is excluded from the

47

smoothness calculation.
3. Smooth the data again using the robust weights.
4. Repeat the previous two steps for five iterations.

To solve for the unknown parameters p = [cT, :1:, y]T in equation (2.12), the derivative of

J with respect to p is set to be zero, i.e.,

a_ay
op _ op 6L
= ETWL
(2.16)
=ETW.(M+E.p—V)
= 0.
SO,
p = (ETWE)-1 . ETW . (V — M). (2.17)

Searching for Optimal Positions
To find the optimal position for each node in the model, the search range is the inside
and outside 19 / 2 (k = 20) points along the normal line at each node of the shape. The
nodes in the model are classified into two types: crown nodes and root nodes (Figure
2.17). Different search strategies are used for the two types of nodes since boundaries of
crowns and roots have different characteristics. The boundaries of crowns are located at the
outermost gradients, while the boundaries of roots are located at the strongest gradients in
the search range. Assume there are k points for the search. Denote the normal line direction
of the node as n, the gradient of the original image in the search scope as {g1, g2, ..., gk}

and the smoothed gradient as {51, $2, ..., sk}. A metric for each point It in the search space

48

 

is defined as

sign(n - gk)(n nxgki. + nygky), 1f the node is a crown node
M(k) =

sign(n - sk)(n§ski + nzsk2)

y , 1f the node is a root node

(2.18)
where n,c and 11,, are a: and y elements of the normal line direction n gkx and gky are a:

and y elements of the gradient gk, and SI”, and sky are :1: and 3; elements of the smoothed
gradient 31,.

For crown nodes the optimal position is the outermost point in the range Wthh has a

negative value of the metric M (k). For root nodes, the optimal posrtron rs the pornt that
has the most negative value of metric M ( k)

Root Nodes

Search Range

4
e
e

..‘I/ Crown Nodes\>

......

o
...‘OOOOOOOOOOOOO..........O

Figure 2 17. Crown nodes and root nodes in the model

Smoothing Spline

The detected optimal posrtrons of the nodes are connected usrng a smoothing spline s
which minimizes [5]

p}:(3r(1—p)/(g:§)2dx, (2.19)

where p IS the smoothing factor, x,- is the index for the spline s y, is the zth pornt to connect

and n rs the number of boundary points in each training shape

49

User Interaction
The automatic contour extraction algorithm may fail due to the poor image quality or im-
proper initialization. The failure can be detected and a request can be issued for user inter-
action. The detection algorithm compares the coefficients, 0, obtained in Equation (2.12)
to the eigenvalues of the covariance matrix, 2x, in Equation (2.8). In particular, denote
the eigenvalue of the i-th mode as o,, i = 1, 2, ..., k, where It is the number of eigenvec-
tors used for shape extraction. Since eigenvalues represent the variances for a mode, if
the absolute value of a coefficient, c,-, is larger than the square root of the eigenvalue, o,-,
it may imply an aberrantly extracted shape and a warning message is issued. Figure 2.18
shows two examples of erroneous tooth contours detected by the algorithm. The check is
not applied to the first two modes, since these modes represent scaling and rotation and,
therefore, large coefficient values for these two modes do not imply aberrantly extracted
shapes. The erroneous tooth contours are corrected by manually specifying points along

the tooth contours.

 

Figure 2.18. Detection of erroneous tooth contours.

2.3.3 Experiments

The tooth contour extraction routine (implemented in Matlab 7.0) takes ~ 15 seconds

for a single tooth on a PC with a 2.99 GHz Pentium 4 processor. Experiments on 198

50

images containing a total of 1,284 teeth show that 59.4% of tooth contours were correctly
extracted. For images of good quality, 76% of teeth were correctly extracted. The details of
the accuracy are shown in table 2.2. Figure 2.19 shows some successfully extracted tooth
shapes.

Table 2.2. Success Rate of Automatic Contour Extraction

 

Image Quality

, Good Medium Poor
Number of Extractions

Successful 323 241 I99
Failed 102 135 284

 

 

 

 

 

 

 

 

2.4 Segmenting Regions of Dental Work

Another useful feature for matching AM and PM radiographs is the contours of dental
work, if present, which appear as bright blocks in the radiograph (Figure 2.20 (a)). The
most common dental work includes fillings and crowns, which are made of material such
as silver amalgam, gold, stainless steel, CaOH base, and porcelain [31]. These materials
are more radiopaque than the tooth enamel. ’

There are two steps for extracting the contours of dental work:

1. Anisotropic Diffusion. Anisotropic diffusion (see Appendix B) is used to enhance
the image such that the boundaries of regions are preserved while the interiors of regions
are smoothed. The number of iterations for enhancing dental work is eight, which has been
determined empirically.

2. Image Thresholding. A mixture of Gaussians model is used to model the intensity
histogram of the enhanced image. A threshold value is chosen to segment the dental work.

The details of the second step are given in the remainder of this section.

51

 
   
 

1“,“: . ‘
I 1" II M
f 2 Emmi-41.11149 ~

(13)

 

(6) (0

Figure 2.19. Tooth shapes successfully extracted using ASMs.

52

 

2.4.1 Image Thresholding

The extraction of dental work contours is accomplished using the intensity histogram of
the radiographs. We fit a mixture of Gaussians to the intensity histograms. The Gaussian
component with the largest mean corresponds to the pixel intensities associated with the
dental work, while other components correspond to the pixel intensities belonging to the
teeth. Dental work can be segmented using a threshold that best splits the Gaussian com-
ponent with the largest mean from the other Gaussian components (See Figure 2.20) [34],
[56]. Let the intensity histogram be denoted as p(:1:). It is represented in terms of a mixture

of C + 1 Gaussians as
0
19(3) = P0 490(3) + 2 Pi 'Pi(113), (2.20)
i=1

where 190(2) is the Gaussian component for the dental work and p,(z),i = 1, ..., C, are the

C Gaussian components for the tooth pixels, Po and P,’s are the mixing coefficients, and

1 ‘(33 — #02

 

13,-(1r) = maexp T,i=0,1,...,C, (2.21)
,110 > 11,-,2' = 1, ...,C, (2.22)

a .

Zr),- = 1. (2.23)

i=0
The number of components in the mixture, (0 + 1), can be estimated using the algorithm
proposed by Figueiredo and Jain [29]. The method utilizes an expectation-maximization
(EM) algorithm to select the number of components in a mixture model based on the min-
imum message length (MML) criterion.

Intuitively, if the variances of the Gaussians in the mixture decrease without changing
the means, then misclassification error decreases as well, because there will be less over-
lap between the Gaussians. This objective is achieved by first enhancing the image with
anisotropic diffusion. Figure 2.21 shows some input images ((a), (b), and (e)) compared
with the smoothed images ((d), (e), and (f)) and the resulting contours of the tooth and the

dental work. Small or narrow areas extracted in the images are regarded as artifacts and are

53

 

   
  

Optimal Threshold

Probability

  

 

 

‘ r;
-

 

DentalWork " , _ 7. .7.
0 so 100 150 200 250
Intensity
(b)

Figure 2.20. Fitting a mixture of Gaussians model to the intensity histogram (b) of an
image (a), in which the dental work appears as a bright block.
removed. As can be seen, more accurate dental work contours are detected in smoothed
images.

The process for extracting dental work contour for a single tooth takes ~ 10 seconds
on a PC with a 2.99 GHz Pentium 4 processor. Experiments on 128 teeth images show that
90% of dental work contours are correctly extracted. The incorrectly retrieved contours are

fixed by adjusting the parameters and number of iterations in the algorithm.

2.5 Summary

This chapter proposed methods for radiograph segmentation, extraction of tooth contours,
and extraction of dental work contours. We proposed a method for segmenting dental
radiographs based on fast marching algorithm. To correct the segmentation errors, an inter-
active method was developed. We also proposed an active shape model-based algorithm for
extracting the contours of teeth. To extract dental work contours, an anisotropic diffusion-
based technique was used to enhance the radiographs, and the regions of dental work were

segmented using image thresholding. Segmenting a dental radiograph takes ~ 2.5 seconds,

54

 

(d) (e) (0

Figure 2.21. Extracted dental work contours with and without image enhancement. (a), (b)
and (0) Without enhancement. (d), (e) and (f) After enhancement.

extracting tooth contours takes ~ 15 seconds for one tooth, and extracting dental work con-
tours takes ~ 10 seconds for one tooth. These processes are evaluated on a PC with 2.99
GHz Pentium 4 processor. Table 2.3 summarizes the CPU time used in each step. Exper-
iments have shown 61.1% accuracy for radiograph segmentation, 76% accuracy for tooth
contour extraction (for images of good quality), and 90% accuracy for dental work contour
extraction. An image quality evaluation firnction and monitoring scheme were developed
to assess the image quality and correctness of results given by automatic algorithms. User
interactions are requested when the image has poor quality or the results are incorrect. Fig-
ure 2.22 shows a process of extracting tooth contours and dental work contours with human

interactions to correct detected errors.

55

 

Input

Images User Interaction

 

Image
Segmentation

 

Tooth Contour
Extraction

 

Dental Work
Contour Extraction

Figure 2.22. Process of extracting tooth contours and dental work contours with human
interaction. Automatic method works well for the good quality image (image I), but needs

user interaction for poor quality image (image 2).

Table 2.3. Summary of CPU (2.99 GHz Pentium 4) Time for Extracting Features

 

 

 

 

Procedure Time Overall Time Avg. Number of Calls
adrograph Seigmentatron 2.55 25$ 1
Tooth Contour Extraction 15s 1208 8
Dental Work Extraction 103 50s 5

 

 

 

 

56

 

CHAPTER 3

Registration of Radiographs to Dental
Atlas

One of the challenges in automatically matching dental radiographs is missing teeth in
either the AM or PM image. In the presence of missing teeth, the matching algorithm
will not be able to correctly align the tooth sequences in AM and PM images if it cannot
determine which teeth are missing. However, missing teeth can be detected if the teeth
in the images are first labeled based on dental anatomy. Anatomy-based tooth labeling
can also accelerate the image matching stage, since a pair of PM-AM images need not be
matched if no teeth share the same labels.

To label teeth with anatomical indices, dental radiographs are first registered to the hu-
man dental atlas, which is a descriptive model of the shapes and relative positions of teeth.
We propose a hybrid model involving Support Vector Machines (SVMs) and a Hidden
Markov Model (HMM) for representation of the dental atlas and classification of the teeth

in dental radiographs.

57

 

3.1 Introduction

Mahoor and Abdel-Mottaleb [43] proposed a method to obtain the indices of teeth in bitew-
ing images. After the tooth contours are extracted, Fourier descriptors, which are invariant
to scaling, rotation and translation of the contours, are extracted from the sequence of
contour coordinates. A Bayesian classifier is trained to classify the descriptor series into
two categories: molars (M) and premolars or bicuspids (P). The tooth sequences without
any missing teeth in the bitewing dental radiographs have only the following possible pat-
terns: PM, PMM, PMMM, PPM, PPMM, and PPMMM for the left side image; MP, MMP,
MMMP, MPP, MMPP, and MMMPP for the right side image, where “M” stands for mo-
lar, and “P” stands for premolar. Since the anatomical indices of teeth in each pattern are
known, the indices of teeth in the radiographs can be determined after the pattern of the
tooth sequence is identified. A major limitation of Mahoor and Abdel-Mottaleb’s method
is that bitewing images are only one of the three types of dental radiographs, and bitewing
images only include two classes of teeth: molars and premolars. Furthermore, this method
assumes that there are no missing teeth in the images. When this assumption is not satisfied
or classification errors between M and P types occur, the method results in false registra-
tions. Experiments in [43] on 50 bitewing images show that the classification accuracy for
molars in the lower row of teeth is 91.8%, the accuracy for molars in the upper row of teeth
is 93.7%, the accuracy for premolars in the lower row of teeth is 82.0%, and the accuracy
for premolars in the upper row of teeth is 91.4%.

Compared to Mahoor and Abdel-Mottaleb’s method, the method proposed here has the
following advantages: it deals with all three types of dental radiographs (bitewing, periapi-
cal, and panoramic images (Figure 1.1)), and it considers all three classes of teeth (molars,
(bi)cuspids, and incisors (Figure 3.1)) [31]. The proposed method is a hybrid system in-
volving the Support Vector Machine (SVM) and the Hidden Markov Model (HMM) for the
representation and classification of teeth. The HMM serves as an underlying representation

of the dental atlas by representing various teeth and the distances between the neighboring

58

 

teeth as HMM states. The SVM classifies the teeth into 3 classes based on their contours.
Missing teeth in a radiograph can be detected by registering the observed tooth shapes and
the distances between adjacent teeth to the dental atlas. Furthermore, instead of simply
assigning a class label to each tooth, the posterior class-probability associated with each
tooth is extracted from the SVM and passed to the HMM. This approach reduces the im-
pact of classification errors during registration. The hybrid model yields the probability of
registering the tooth sequences in a radiograph to their possible positions in the atlas. The

top-n (n=3) possible registrations are explored further in the radiograph" matching stage.

 

Figure 3.1. Three types of teeth. (a) Molar; (b) (bi)cuspid; (c) incisor.

In this chapter, the SVM/HMM model is described in section 3.2, and the representa-
tion of the dental atlas using the SVM/HMM model is discussed in section 3.3. Section
3.4 introduces a method for detecting incorrect estimations of tooth indices. Section 3.5

presents experimental results of applying the algorithm to a database of dental radiographs.

3.2 SVM / HMM Hybrid Mode]

Hybrid models of SVMs and HMMs have been utilized for sequential data analysis. Gana-
pathiraju et al. [30] used a SVM prior to a HMM for speech recognition. Castellani et al.
[17] used the same structure for analysis and segmentation of teleoperation tasks. Campbell
[16] applied a HMM before the SVM for speaker recognition. Our system utilizes SVM for

classification of teeth and HMM for registering a tooth sequence to the dental atlas using

59

the classification results. By integrating SVM and HM, the classification results passed
from the SVM to the HMM are posterior class probabilities instead of classification labels.
This reduces the impact of erroneous SVM classifications on registration.

A hybrid SVM/HMM system is used to model a sequence of events. The goal is to
estimate P(E, Q), the probability of observing a sequence of events E = {e1,e2, ..., e L}
from a sequence of states Q = {q1, Q2, ..., qL} in the model. Q is called a path in the follow-
ing text. For a given event sequence E, the top-n registrations are retrieved by comparing
P(E, Q) for all possible Q’s. The SVM/HMM system is denoted as A = {S, A, V, B, 71},

where the definitions of the elements are as follows:

0 S = {51, 82, ..., SN} denotes the set ofN states;

A 2 {an} is the N x N transition matrix, which represents the probability of tran-

siting from state S,- to state S j.
aij = P(qt+1 = Slet = 32'): (3-1)

wherel gi,jgN,1_<_tSL—1,a,-j 20andforalli,2;v:1a,j=1;

V = {o1, o2, ..., oM} is a set ofM observation classes;

B = {b,-,,} is an M x N emission matrix, indicating the probability of observing an

instance of class k at state j, i.e.,

by. = P(vklsj); (3-2)

71 = {71,-} is the set of N initial state probabilities, representing the probabilities of

starting a sequence from every state, i.e.,

71.- = P(Ql = Si)° (33)

Given an event sequence E = {e1,e2,...,eL} and a path Q = {q1,q2,...,qL}, the

60

probability P(E, Q) evaluated by the model /\ is defined as

P(E.Q) = P(EIQ)P(Q), (3.4)
P(Q) = P(Q1)HP(quQi—1)° (3-5)

L
P(EIQ) = IIP(e.~Iq.-) (3.6)

p(e.-lvk.q1)P(vk|q.-)- (3-7)

M:

=11

l

‘l

L

a-
II

1
Since the shape of a tooth depends more on its type than on its position, let us assume that
p(e,|ok, q,-) is independent of the state q,, i.e., p(e,-|ok, q,) = p(e,~|ok). Then, according to
the Bayes rule,

Met-Io.) = p(v1.1|)e(.35(e.). (3.8)

 

Now equation (3.7) can be written as

 

 

P(EIQ) = HZP(”’}Le(‘3:(ei)P(vtiq.-), (3.9)
L M 10(ka61) ~
O( H: P(Uk) P(vqui)1 (310)

where the posterior probability p(ok|e,-) is extracted from the SVM, and P(e,) is the con-
stant of proportionality, which does not impact the comparison of P(E, Q)'s. P(ok) is
derived from the training data, and P(oqu,) is given by the emission matrix B. In Equa-
tion (3.5), P(ql) is given by the initial state probabilities 7r, and P(q,|q,-_1) is given by the
transition matrix A.

Traditional SVMs solve two—class classification problems, and they do not provide pos-
terior class probabilities. To solve multi-class classification problems, a strategy of one-
versus-one or a strategy of one-versus-all is used [50]. If there are M classes, M (M — 1) / 2
SVMs are needed for the one-versus-one strategy, as compared to M SVMs for the strat-

egy of one-versus-all. Experiments on a number of standard classification tasks have shown

61

that one-versus-one classifiers are marginally more accurate than one-versus-all classifiers
[10]. Therefore, our system uses the strategy of one-versus-one.

The extraction of posterior class probabilities from a group of one-versus-one SVMs
involves two steps. We first estimate pairwise posterior probabilities from each one-versus-

one classifier. The pairwise posterior probability is defined as
rm 2 p(o = kle,o = k or I), (3.11)

where k and l are the class labels, and p(o = kle, o = k or I) is extracted using the formula

1
1 + eAf(e)+B’

 

p(o = kle,o = k or Z) = (3.12)

where e is the input to SVM, f (e) is the output score of SVM, and A and B are esti-
mated using a model-trust minimization algorithm under cross-validation [50]. The global

posterior probability for class k is denoted as pk, where
191. =p(v1.|e) =p(v=kle),k= 1,.--,M- (3-13)

The global posterior probability, p1,, is estimated from all the m’s by solving the following

optimization problem [62]:

M M
M: 2((7‘11491: —7‘1c1p1)2 1

11:1 1:1,1761:

NII—I

,,,,,

subject to (3-14)

Zpk =19pk Z OIVk

kzl

3.3 Registering a Tooth Sequence to Dental Atlas

The SVM/HMM model is used to represent the dental atlas, and the observation sequences
are extracted from the dental radiographs and registered to the dental atlas to find the

anatomical labels (molar, (bi)cuspid and incisor) of the teeth.

62

3.3.1 Representation of Dental Atlas

The dental atlas of a complete set of adult teeth is shown in Figure 3.2. The teeth are
classified into three categories according to their appearances: molars, (bi)cuspids, and
incisors.l Molars have 2 or 3 roots and 3 or 4 cusps in their crowns. Cuspids and bicuspids
have 1 or 2 cusps and 1 to 3 roots. Usually only one of the roots is visible in the radiographs.
Incisors have fiat crowns compared to other types of teeth, and each incisor has a single
root. According to the universal nomenclature system [9], tooth indexing starts from the
rightmost upper molar to the leftmost upper molar, and resumes from the leftmost lower
molar to the rightmost lower molar. Using SVM/HMM model, upper and lower teeth are
modeled separately. A SVM/HMM model representing the 16 upper teeth is illustrated in
Figure 3.3. For each tooth in the dental atlas, there is a tooth state representing the observed
tooth in that position, as well as three distance states representing the number of missing
teeth (0, 1, or 2) after this position. The tooth states are shown as circles, and the number
inside each circle is the tooth index. The squares in the model are distance states, and the
number inside the square is the number of missing teeth. Here we assume there are at most
2 consecutive missing teeth. For the 16 lower teeth, the model has the same structure as the
model shown in Figure 3.3, except that the tooth indices now go fi'om 32 down to 17. Since
an observation sequence can start from any tooth state, the initial state probabilities for the
tooth states in the model are the same, i.e., P(q) = 1/ 16 for each row of teeth, where q is
any one of the 16 tooth states in the model. The teeth are not classified with respect to their
indices by SVMs due to the fact that the small inter-category variability poses difliculty for

classification.

 

1Bicuspids and cuspids are sometimes regarded as two different classes. Here we use “(bi)cuspids” to
refer to both bicuspids and cuspids as one class due to their similar appearances in dental radiographs.

63

Classes: Molars (Bi)cuspids Incisors(Bi)cuspids Molars

r——:—3\ MH—wr—‘H r—-*—-\
Index: 4 67 8 91011121314 15 16

01112111212 ‘11; 22:
”1:31;: 01:1” ;3 {7‘ W1 1,? ”‘ ,{Jg

 

I
. I '
v

I

V

Index: 32 31 30 29 28 27 2625 2423 22 2120 19 18 17
L—w—J L_Y___l t___Y__7 t_Y_J 1 Y 1

Classes: Molars (Bi)cuspids Incisors (Bi)cuspids Molars

 

Figure 3.2. Dental Atlas of a complete set of adult teeth containing indices and classifica-
tion labels of the teeth.

3.3.2 Extraction of Observation Sequences

The model structure in Figure 3.3 shows that a feasible path is an alternating sequence of
tooth states and distance states. The observation for a path is accordingly an alternating
sequence of observations for tooth states and for distance states; Figure 3.4 shows the
procedure for generating an observation sequence. The observation for a tooth state is the
contour of the tooth (methods for extracting the tooth contours are discussed in Chapter 2
(See Figure 3.4)). Tooth contours are then normalized into equal-length vectors as the input
to the SVM. The observation for a distance state is the distance between the neighboring
teeth. To eliminate the inconsistency caused by different resolutions used in radiograph
digitization, each distance is divided by the width of its preceding tooth.

The teeth belong to one of three classes: molars, (bi)cuspids, or incisors. For a tooth-
contour vector e,, the SVM generates the posterior class probabilities p(ok|e,-), o), 6

{molar, (bi)cuspids, incisor}. For a distance state q,- and an observed distance ej, a trained

64

 

 

 

 

 

 

 

Figure 3.3. SVM/HMM model for the upper row of 16 teeth.

mixture of Gaussians model generates the probability p(ej lqj) in Equation (3.6). By com-
paring P (E , Q)’s given by Equation (3.4), we retrieve the top-n possible paths. The indices

of the teeth in the observation sequence are obtained from the tooth states in the path.

3.4 User Interaction

Detection of incorrect estimation of tooth indices makes it possible for users to interactively
correct the errors. The estimation errors result from untypical shapes of teeth. Given an
untypical shape, SVMs produce similar posterior probabilities fOr the three classes. A
probability-based error detection algorithm is proposed based on this phenomenon. The
detection rule is: if the difference between the probabilities of top-2 estimations is less than
0.2, the estimated tooth indices may be incorrect. The incorrect estimation can be corrected
by manually assigning the tooth indices to the teeth. Figure 3.5 shows the user interface for

manually specifying tooth indices.

3.5 Experimental Results

The algorithm was evaluated on the database mentioned in Chapter 1. A total of 1,702 tooth
contours associated with 33 subjects were extracted from the radiographs in the database

with the contour extraction methods, proposed in Chapter 2. Experiments were conducted

65

on the extracted tooth contours before and after user interaction.

There are 676 tooth sequences in the database, and the 33 subjects were separated into
3 folds of approximately equal-size. One fold was used for training the SVM, the second
fold was used for training the HMM, and the third fold was used for testing the registration
algorithm. We used the 3-fold cross-validation, so all the tooth sequences were registered
to the dental atlas after three executions of the routine. The implementation of the SVM
used in the experiments was LibSVM 2. The confidence measure for each estimate of the
tooth indices in a tooth sequence is evaluated in the SVM/HMM model as the probability of
registering the tooth sequence to the corresponding states in the atlas. The estimates of the
tooth indices were ranked with respect to the confidence measures. For firlly automatically
extracted tooth contours, the accuracy for top-1 estimation is 60.1%, the accuracy for top-2
estimations is 72%, and the accuracy for top-3 estimations is 75%. For extracted tooth
contours with the help of user interaction, accuracy using top-1 estimation increases to
85.1%, accuracy using top-2 estimations is 91.1%, and accuracy using top-3 estimations is
92.6%. The top—3 estimations will be used in the matching process discussed in Chapter
4 since there is no increase in the accuracy by using top-4 estimations compared to top-3
estimations. The training process takes 0.183 for each sequence (consisting of 2.5 teeth on
average), and the registration process takes 0.178 for each sequence on a PC with a 2.99
GHz Pentium 4 processor.

Figure 3.6 shows some instances of successful atlas registrations, while Figure 3.7
shows some instances of atlas registration errors. The errors in atlas registration are caused
due to three main sources: (i) Insufficient length of tooth sequences. For example, a se-
quence of 2 consecutive lower molars can be registered to positions 30 and 31, or 31 and
32, or 17 and 18, or 18 and 19 with equal probabilities, though only one of the four esti-
mates is true (Figure 3.7(a)). (ii) Tooth classification errors in short sequences, for which

the lengths of the sequence are not sufficient to compensate for the tooth misclassifications.

 

2LibSVM can be downloaded at (http://WWIucsiemtu.edu.tw/~cjlin/libsvm/)

66

In other words, a classification error in a 16-tooth sequence is easier to correct than an error
in a 4-tooth sequence (Figure 3.7(b)). (iii) Errors in detection of missing teeth, because the
remaining teeth slide together and nearly fill the gap caused by the missing teeth (Figure
3.7(c)). Table 3.1 shows the accuracies of estimating tooth indices and the percentage of
errors caused by each of the three factors in the top-3 estimations.

Table 3.1. Accuracies and Sources of Error in Estimating Tooth Indices

 

Sources ofError

 

 

 

 

 

 

 

 

 

Rank of Registration Accurate Estimation Factor (1) Factor (11) Factor (111)
Top-1 85.1% 8.1% 5.6% 1.2%
Top-2 91.1% 4.3% 3.6% 1.0%
Top-3 92.6% 3 .6% 3.1% 0.7%
3.6 Summary

This chapter discussed a scheme for registering dental radiographs to the dental atlas. The
method utilizes a SVM/HMM model to represent the dental atlas and classify teeth in the
radiographs. Tooth indices are determined by registering the tooth sequence in the radi-
ograph to the dental atlas. The system generates probabilities for each registration of the
tooth sequence. Experiments were conducted on a database of 676 tooth sequences. For
tooth contours that were not corrected by the user, the accuracy for top-1 estimation is
60.1%, the accuracy for top-2 estimations is 72%, and the accuracy for top-3 estimations
is 75%. For user corrected tooth contours, accuracy using top-1 estimation is 85.1%, accu-
racy using top—2 estimations is 91.1%, and accuracy using top-3 estimations is 92.6%. On
average, training of the proposed SVM/HMM model takes 0.185 for each sequence, and
estimation of tooth indices takes 0.175 for each sequence on a PC with a 2.99 GHz Pentium
4 processor.

The proposed method fails when tooth sequences do not have suflicient number of teeth
for correct registration, the tooth types are misclassified, or teeth slide together after tooth

extraction. We have developed an error detection algorithm and a graphical user interface

67

(GUI) to interactively correct the estimation errors.

68

 

 

 

 

 

 

 

 

 

\ L L
r r ‘ r
Widths: w: w" W3.
—> + -> <—
W1 W2

[ wl/wl' ’ w2/w2' ]

e1 e2 e3 e4 85

Figure 3.4. Extraction of tooth contours and generation of an observation sequence, E =
{e1, e2, e3, e4, e5}; e1, e3 and 65 correspond to tooth states, and oz and 6., correspond to
distance states.

69

(Bimpltln Incisors (Humid: mm

2 345678 91011121314 1515

~49 satiillllli 81111122322

2 332111221221

32 31302928272625 2423222I'20 I9 1817
L—r—J EHL-fir—‘W I_'_J

 

Figure 3.5. A user interface for manually specifying tooth indices by clicking the corre-
sponding teeth in the dental atlas, which is shown on the right side of the dental radiograph.

 

Figure 3.6. Examples of successfirl registration of the dental atlas to (a) a bitewing image,
(b) a periapical image, and (c) an image with a missing tooth. In (c), teeth numbered as 12,
14, and 15 are correctly registered. The missing tooth (number 13) is detected.

70

 

Figure 3.7. Examples of atlas registration errors. (a) The tooth types are correctly classified
as molars, but the teeth (with genuine indices 30 and 31) are registered to teeth 31 and 32
in the atlas since teeth 30, 31, and 32 are all molars and the length of the sequence is in-
suflicient for resolving the ambiguity; (b) all the three incisors are classified as (bi)cuspids,
thus these teeth (with genuine indices 8, 9, and 10) are registered to teeth 3, 4, and 5 in the
atlas; (c) the distance between teeth 3 and 6 seems to support only one missing tooth, so
the input sequence is registered to the atlas teeth numbered 1, 2, 3, 5, 6, 7, 8, 9, 10, 12, 13,
and 14, while the genuine indices are 1, 2, 3, 6, 7, 8, 9, 10, 11, 13, 14, and 15. The lower
row of teeth is, however, correctly registered to the atlas.

71

CHAPTER 4

Matching and Retrieval

The final stage of the identification system is to match dental radiographs of unidentified
subjects against dental radiographs of subjects in the database. Tooth-wise matching is
executed first to match tooth contours of every pair of teeth. When dental work is present
in both teeth, the shapes of dental work are also matched. An overall matching distance
for a pair of teeth is generated by fusing the matching distances for the tooth contours
and the dental work via posterior probabilities. A method using the results of tooth index
estimation is proposed for computing the distances between the given unidentified subject
and all database subjects. The database subjects are then sorted in ascending order of the

matching distances and presented to forensic experts for final analysis.

4.1 Radiograph Matching

This section discusses the process of matching dental radiographs using tooth contours and

regions of dental work.

72

 

4.1.1 Introduction to Shape Matching

In terms of the dimensionality of shapes, shape matching tasks can be categorized into 2D
shape matching and 3D shape matching. Tooth and dental work contours are 2D shapes,
therefore this chapter only discusses 2D shape matching. 2D shape matching can be clas-
sified according to the closeness/openness of the contours, where the difierence is the ease
or difficulty of establishing correspondences. When matching closed contours, every point
in one contour must correspond to a point in the counterpart contour. This assumption is
not satisfied when matching open contours, where some sections of one contour may not
have corresponding sections in the counterpart contour. Matching closed contours is gen-
erally easier than matching open contours, since the overlapping sections of the two open
contours need to be detected before alignment.

Matching closed shapes is a well-studied problem. Closed-shape matching algorithms
are classified into two classes: contour-based methods and region-based methods [65]. The
features used for contour-based matching are extracted from the contours, while the fea-
tures used for region-based matching are extracted from the entire shape. Each class can
be firrther divided into global methods and structural methods. For the global methods,
features are extracted fi'om the entire contour, e. g., the Fourier descriptor, while the struc—
tural methods match shapes using contour primitives (segments/sections), such as chain
codes. Based on whether the features are extracted in the spatial domain or the transformed
domain, the methods can also be categorized into space domain methods and transform
domain methods. Zhang et a]. provide a taxonomy of closed shape matching methods in
[65] (see Figure 4.1).

The main challenge for the open shape matching task is to establish the correspon-
dence. Since it is generally more diflicult to establish correspondence between regions
than between contours, open shapes are generally matched based on contours, instead of
regions. Since the shape correspondence is unknown, global representations of shapes are

not appropriate because they cannot be used to explicitly establish correspondences.

73

 

 

Shape

1
I I

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Contour-based Region-based
I ' I
Structural Global | Global Structural
3 I I

Chain Code Perimeter Area C onvex Hull
Polygon Cornpactness Euler Number Media Axis
B-spline Eccentricity Eccentricity Core
Invariants Shape Signature Geometric Moments

Hausdolf Distance Zernike Moments

Fotuier Descriptors Pseudo-Zemike Moments

Wavelet Descriptors Legendre Moments

Scale Space Generic Fotuier Descriptor“

Autoregressive Grid Method

Elastic Matching Shape Matrix

 

 

 

 

 

 

Figure 4.1. Classification of shape matching methods [65].

A solution to the open shape matching problems is to convert them into point match-
ing problems. As noted by Gold et a1. [32], to solve a point matching problem, one has
to search in two complimentary spaces: the space of correspondence fimctions (e.g., find-
ing correspondence with respect to shape context [12] and sharpness of comers [38]), and
the space of similarity transformations (e.g., thin-plate splines [15] or ICP [13]). Point
matching problems can be solved either by minimizing an energy function that incorpo-
rates transformation and matching metrics, such as Gold et al.’s sofiassign algorithm [32]
[22], or by sequentially and iteratively finding the point correspondence and optimizing the
transformation between the two shapes.

The tooth contours we extract from the dental radiographs are open contours, while the
contours of the dental work are closed contours. The methods for matching these features

are presented in the following sections.

74

4.1.2 Matching Tooth Contours

Given two tooth contours A and B, the problem of matching A and B is to find a trans-
formation T between a segment of A, denoted as A’(t) (t E [0, 1]) and a segment of B,
denoted as B’(t) (t E [0, 1]), such that

1
{7121.3} = arg {72223,} / 114(1) — 80:11:12 (4.11

where H . H is the Euclidean distance between two points. The algorithm for solving this
problem in a discrete fashion is outlined here, followed by more detailed explanations in

the remainder of this section.

 

Algorithm: Matching Tooth Contours

Input: two shape instances A and B in the form of spline curves.

1. Polygonal approximation: Approximate shape A and shape B with point sets
AP and BP. In order to find the correspondence from shape A to shape B, the
sampling rate for B should be higher than the sampling rate for A so that BP can
approximate B precisely enough for distance computation.

2. Shape registration: If the applied transformation from AP to BP is T, then find
the correspondence from T(AP) to BP that preserves the topologies of the two
curves.

3. Distance computation: Compute the distance between T(AP) and BP on the
basis of their correspondence. Denote the distance as D(T(AP), BP).

4. Optimization: Optimize D(T(AP), BP) in the space of transformations and
correspondences by repeating steps 2 and 3 until the value of D(-, ) converges or

the maximum number of iterations is reached.

 

 

 

Polygonal Approximation

The polygonal approximation of tooth contours converts the shape matching problem into a

point matching problem. There are many methods for approximating curves with polygonal

75

 

 

lines [28] [49] [60]. We use arc length parametrization to generate equally spaced points
along curves [49] [60], so that the overall distance between two curves will not be biased
by some portions of the curve that are more densely sampled than other portions.

Let Q be a spline curve with m control points. Using Lee’s centripetal scheme
[42], the m control points are represented with 4(m + 1) coefficients, denoted as cfi,
2' = 1, 2, 3,4,j = 0, ...,m and m control values, o1, ..., om. The cubic spline represen-

tation of the jth (j = 0, ..., m) piece of Q is formulated as:

4
= 202 - vj)""'cj.-. (4.2)
i=1

Define (5 as an index into Q’s knot vector, i.e., 1‘15 occurs before 1'15“, 1‘15 < 115“. Given a

control value 11, 1'10 3 u 3 Tim, the arc length of the curve from 110 to u is:

6<oz
=2 [:61 IIQ u>11du+ / no (21111121 (4.3)

for all 6
where a is the largest index satisfying the condition that 110, < 71.

Since L(u) is a monotonically non-decreasing function, the inverse function L‘1(-)
exists and we can calculate it for a given arc length a as u = '1.(a) So Q(L"1(a)) is
the point at distance a from the starting point of the curve. When a increases evenly, the
extracted points have equal distances along the curve.

The process for obtaining Q’s polygonal approximation QP is summarized as follows:

1. Curve length computation: Use Equation (4.3) to get the length of the curve, L(flm),
where rim is the largest control value of the spline.

2. Selection of control values: Given interval arc length I, generate an array 11,-, i =
0, ., [L(r‘1m)/l], such that a0 = 0 and a,+1 - a, = l. The corresponding array p,, i =
0, ., [L(r‘1m)/l] is obtained as p,- = L‘1(a,-).

3. Point generation: Use p,-, i = 0, ..., [L(r‘1m)/l] , as the parameter in Equation (4.2) to
obtain the ith point in QP.

Figure 4.2 shows polygonal approximations of a tooth contour with different interval

76

arc lengths. In our experiments, we use interval arc length l = 10 for approximating query

shapes, andl = 5 for approximating database shapes.

....................
."

 

[=5 (=10 l=20 [=30

(a) (b) (C) (d) (6)

Figure 4.2. Polygonal approximation of a tooth contour with different interval are lengths.
(a) Original tooth contour; (b) polygonal approximation of (a) with interval arc length
l = 5 pixels; (0) polygonal approximation of (a) with interval arc length l = 10 pixels;
(d) polygonal approximation of (a) with interval arc length l = 20 pixels; (e) polygonal
approximation of (a) with interval arc length l = 30 pixels.

Transformation

The dental radiographs are projections of 3D structures (teeth) onto 2D planes (X-ray fihns)
(Figure 4.1.2). Changes in imaging angle are equal to rotation and translation of the tooth
in 3D space. However, the rotations around the x-axis and y-axis are small enough to be
ignored, so rotation in 3D space can be modeled as the rotation around the z-axis in 2D
space, and the translation along z-axis can be viewed as scaling in :c-y space [31]. Let the
rotation around the z-axis be 0, the translations along zit-axis and along y-axis be t, and
ty, respectively, and the scale factor be 3. Then a point (:13, y) is mapped to T(x, y) after

transformation, where T(x, y) is defined as:

cos 6’ — sin 6 a: t
T = z . 4.4
(33,31) 3(sin6 c030 )(y)+(ty) ( )
The transformation T is optimized to find the minimtun of the matching distances (de-

77

 

Figure 4.3. Dental radiographs are 2D projections of 3D structures.

fined in section 4.1.2) between the corresponding sections of tooth contours T (AP) and
BP. Before initializing T, both shapes should be normalized so that the widths of their
bounding boxes are scaled to a constant (100 pixels in our experiments). This normal-
ization sets the matching distances to the same scale so that they can be compared. The
initialized transformation T is the transform that aligns the bounding boxes of the two

shapes (Figure 4.4(c)).

Shape Registration

Denote the approximation point set for shape A as AP, the approximation point set for
shape B as BP and the transformation from AP to BP as T. The shape registration stage
establishes the correspondence from T(AP) to BP, which preserves the topologies of the
two curves, i.e., if a,- and a, (a,, a,- E T(AP)) correspond to bk and b) (bk, b; 6 BP),
respectively, and 1' < j, then lc < l [26]. Because the two curves may not fully overlap,
outliers (the points in either curve that do not have corresponding points in the counterpart

curve) may be present. The shape registration algorithm (illustrated in Figure 4.4) is given

78

as follows:

 

Algorithm: Shape Registration

Input: Two ordered point sets, TAP and BP, where TAP is the transformed ver-
sion of AP, i.e., TAP = T(AP). The kth point in TAP is denoted as TAP(k)
and the kth point in BP is denoted as BP(k).

Goal: To find the correspondence from TAP to BP, which is denoted as Cor(i),
wherei = 1, ..., ITAPI, and 1 g Cor(i) g |BP|. The notation “| - |” denotes the
number of elements in the set.

1. Initialization: Initialize Cor(~) as Cor(i)—— - [,TP,(A1+) 1], where i =
1, .., [TAP], and [m] denotes the greatest integer below m. For descriptive conve-
nience, we add two elements to Cor(-), i.e., Cor(0) = l and Co7'(|TAP| + 1) =
|BP|.

2. Fori = 1, ..., |TAP| do

001(7) *- arg.=:....:2;?:....., ”TAM - BM)”;

Dis(i) +— ||TAP(1')—C'or(i)||.

3. Repeat step 2 until the algorithm converges or a maximum number of iterations
is reached.

4. If some adjacent points in TAP correspond to the same point in BP, i.e.,
Cor(z') = Cor(i + 1) = = Cor(z' + k), andp = arg mink=,,,,-+k Dis(k), then
Cor(z') = nil, Vi 75 p. The points for which 007(1) = nil are the outliers (Figure
4.4(f)).

Denote the subset of TAP that has corresponding points in B P as TAP’. The distance

 

 

 

between tooth contours A and B is given as D,C(A, B), where:

 

D,C(A, B): min

VT ITAP’I Z IITIQI)“COT(G')II. (4.5)

all a’ ETAP’

79

The distance Dtc(A, B) is minimized by searching for the optimal transformation T. This
optimization problem is solved iteratively using Sequential Quadratic Programming [36].
Since Cor(-) is affected by T, the correspondence is established at each optimizing itera-

tion.

4.1.3 Matching Dental Work Contours

The shape of dental work is another feature used to match dental radiographs. Since the
appearance of dental work varies widely, it is more discriminative to match dental work
than to match tooth contours. However, because the dental work does not always have a
convex shape, even a slight change in the imaging angle can cause great variation in the
shape of dental work in dental radiographs (Figs. 4.5(a), (b), (c)). To solve this problem,
we use a metric based on the area of the dental work.

The preprocessing goal is to set the pixels inside the tooth contours to be 0, and the
pixels inside the contours of the dental work to be 1 (See Figs. 4.5(d), (e)). Given two
images F and G, the ratio of Misaligned Pixels (Rm?) between them is defined as:

23,, F ’(($, 31) E A) EBG’CT, y)
Z(1:,y)EA F’($a y) + Git”: y) ,

where A is the overlapped region of tooth pixels and dental work pixels in images F and

R‘mP(F3 G) =

 

(4.6)

G, $ is the ‘Exclusive-OR’ operator, and F’ and G’ are the results of preprocessing on F
and G, i.e.,

I 0, if F(:z:, y) is a tooth pixel;
F (re, 31) = (4-7)

1, if F (x, y) is a dental work pixel.
Image 0’ is defined in a similar way. The metric Rm, is used to measure the alignment of
the dental work. If the dental works in images F and G have similar shapes and are well
aligned, then Gmp is small. So the distance between the dental works in images F and G is
defined as:

de(F, G) = min Rmp(T(F), G), (4.8)

for all T

80

Postmortem Contours,

A Antemortem Contours, B
(a)
”’M.. .o’ u ..... o
. .0 """""""" e..
. o
8 0.0 '1‘ z. E. 3..
C. .0. z. .0 D. ‘.
. : '. ' —> - '.
.. . .. C C
o ' o
o o
.0 ' .0 .
O. .. ..
. o

O
Postmortem Point Set, AP

Antemortem Point Set, BP

0’)

 

 

 

 

 

 

l.
(C)

EDBDDDDDDB

a

E

E)

El
8 s
13

E E]

D a

D a
B a
[3 k .
[3 :9, Out I I er s

E] 4”.—
(c) (0

Figure 4.4. Shape registration process. (a) Continuous tooth contours; (b) discrete tooth
contours; (c) initialization by aligning bounding boxes; (d) initialized point correspon-

dence; (e) aligned contours after optimum transformation; (1) correspondence after align-
ment and outlier detection.

81

where T is the transformation defined in Equation (4.4) and optimized using Sequential

Quadratic Programming [36].

4.1.4 Fusing the Matching Distances

In the previous section we defined the distance Dtc, which measures the difference between
tooth contours, and the distance de, which computes the difference between dental work
contours. Combining these two matching distances should improve the retrieval accuracy.
However, for teeth without dental work, de is not available. To handle this situation, we
propose to combine the distances Dtc and de via posterior probabilities.

Let tug represent the matching between radiographs of the same subject (genuine class),
and w,- represent the matching between radiographs belonging to two different subjects
(imposter class). The likelihood distributions (shown in Figure 4.6) of de for genuine
and imposter classes, 13(de Iwg) and p(de|w,-), were estimated using approximately 100
genuine and 100 imposter matchings. A Parzen window approach with a Gaussian kernel
was used to estimate the probability distributions, p(de|w,-) and p(de|wg). The two

posterior probabilities are

«P(wiIde) : p(de|wi)P(wi)

 

 

p(de) (4'9)
P(wngdw) = 29(Dd;(|lu;:)1)’(wg), (4.10)

where the priors, P(w,) and P(wg), are assumed to be 0.5. The probability p(de) is
defined as 12(de) = 0.5 - [p(de|w,-) + p(de|wg)].
The matching distance 0,6 is combined with de to generate the fused distance D f

between the two teeth, A and B, as follows

Df(AiB) : Dtc(AwB)' (1+ a ' (T(de)))v (4-11)

82

 

(e) (d)

(6)

Figure 4.5. Dental work merging due to a change in the imaging angle. The hole in the
circled dental work seen in image (a) is occluded when viewed from the angle shown in (b)
even though both the images are of the same tooth; (c) preprocessed image for two teeth in
image (a); (d) preprocessed image for two teeth in image (b); (e) result of ‘Exclusive-Or’
operation for the two teeth. Pixels of value ‘1’ are displayed in black, and the pixels of
value ‘0’ are displayed in gray.

83

 

 

 

 

 

3 1 l T i I l
Distribution of Genuine Matching Distance
2.5. / NONI 0.)
Distribution of Imposter Matching Distance
1.5.
1 _
0.5~ .
8. 2 o 0.2 0.4 05 08 1 1.2
de

Figure 4.6. Distribution of matching distances based on the shape of dental work.

and

P(w,|de) — P(wg[de), if Dd,” is available

T(D...) = (4.12)

0, otherwise,

where a weighs the importance of the dental work shape in fusion (0 S a _<_ 1). The
combination scheme described above implies that if de is more likely to be the distance
between the genuine teeth, i.e., P(wngdw) > P(wilde), Dtc is reduced by multiplying
it with (1 + a - (T(de))), which is less than 1; if de is more likely to be the distance
between imposter teeth, i.e., P(wngdw) < P(wilde), Dtc is amplified by multiplying it
with (1 + a- (T (de))), which is larger than 1; if de is not available, Dtc is not modified.

In practice, neighboring teeth are matched as a unit denoted as
D,([R,,, 12,-+1], [R;, R2+1]), where R; and 12,-+1 are neighboring teeth in image R,
and R; and R; H are neighboring teeth in image R’; the notation [12,, RH] means the
concatenation of R,- and R)“, and similarly for [R2, R2 +1]. Distances Dtc(-) and de(-)

are also computed based on pairs of neighboring teeth. This scheme has the advantage that

84

both tooth contours and their relative positions contribute to the matching score.

4.2 Matching Subjects

Given a database of AM radiographs, the identity associated with a set of PM radiograph
images is established by matching the tooth sequences in the PM images to a database of
tooth sequences in labeled AM radiographs. Note that for each subject in the database,
there may be more than one AM image. Tooth correspondence, which means that teeth
from the two sequences have the same indices, is established by comparing the indices of
teeth, which are estimated by registering the tooth sequence to the dental atlas, introduced
in chapter 3.

Given two tooth sequences R and S, suppose C is one of the top-m estimated tooth
indices for teeth in sequence R, and 17 is one of the top-m estimated tooth indices for teeth
in sequence S. In our experiments, we use m = 3. Despite the fact that the numbers of
teeth in R and S may be difi‘erent, as long as there are corresponding teeth, denote them as
(R1, SI), (R2, 32), ..., (Rn, Sn), where n 2 1. We denote the distance between sequences
R and S based on C and n as DC,,,(R, S), which is given by

12?: 124121352), lf’n _>_1,
04,,(12, S) = " 1 (4.13)

00, otherwise,

where D f (R), S,) is the distance between teeth R, and 5,, which is obtained in the previous
section. The minimum value of DC," among all the combinations of top-m estimations for

R and S is set to the value of the distance between sequences R and S, written as
D(R, S) = 152m DC,,,(R, S). (4.14)
:‘7

To estimate the similarity of subjects (I) and \II, assume that sequence R belongs to (I)

and sequence 8’ belongs to \II. Denote the distance measure between subjects (D and \II as

85

Ds(<I>, \IJ), which is given by:

_ ZREQ mingeq, K.(R,S)
DWI” ‘1’) " #{RIR 6 <1», :36, n(R, S) > 0}’ (4'15)

 

where <I> means all tooth sequences of subject (I), \II means all tooth sequences of subject
\IJ, and

D(R, S), ifn(R, S) > 0,
MR, S) = (4.16)

00, ifn(R, S) = 0,

where n(R, S) is the number of corresponding teeth used for computation of D(R, S), and
{#{RlR E <I>, 2591' n(R, S) > 0}} is the number of sequences of <1) that have corre-
sponding teeth in any sequence of \II. According to Equation (4.16), the distance between
the sequence R of subject (I) and the subject ‘11 is first calculated as the minimum distance
between sequence R and all the sequences of subject \II. Then we calculate the average
distances between the sequences of subject \II and subject (I) that have corresponding teeth.

To compare the experimental results with and without the use of tooth index informa-
tion, we developed a method for matching subjects that does not use results of atlas regis-
tration, but uses the results of the tooth-level matching to establish correspondence between
two sequences, R and S, instead. The numbers of teeth in R and S are not necessarily the
same. Suppose a possible tooth correspondence starts from the ith tooth in R and the jth
tooth in S (i = 1 orj = 1), denoted as C = {(R:,Sj), (R,+1,Sj+1),...,(R,+,,Sj+l)},
where Rm, is the corresponding tooth of Sj+k, k: = 0, ..., I. Then the correct tooth cor-
respondence should minimize the average distance between corresponding teeth, defined

as:

Df([Ri+k, Ri+k+1[, [Si+kaSi+k+1])i (4-17)

where [., .] means that the contours of neighboring teeth are concatenated and matched as a
unit, as discussed in section 4.1.4. Figure 4.7 illustrates the computation of D in matching a

5-tooth sequence to a 7-tooth sequence. Figure 4.8 shows some correctly established tooth

86

correspondences.

df

[ [.9 [5-
1&8?”qu

6’4 s),

    

Figure 4.7. Coupling 4 pairs of neighboring teeth with 6 pairs of neighboring teeth. The
matching score between each pair of neighboring teeth is calculated and the average is taken
along the arrows. The results are listed in the bottom bar of black and white cells, and the
minimum of these values is defined as the matching distance between the two sequences.

4.3 Experimental Results

We evaluated our algorithm on the two databases mentioned in Chapter 1. Figure 4.9
shows some of the AM and PM images associated with one subject in the databases. The
first database includes 33 subjects, with several AM and PM images fi'om each subject.
Each panoramic or bitewing image is divided into two sequences: an upper set of teeth and
a lower set of teeth. The teeth in the same sequence will not change their relative positions
in different radiographs, while teeth from different sequences will probably change relative
positions in different radiographs because of the opening and closing of the jaws. So we
match the two sequences of teeth separately.

The database contains a total of 360 PM and 316 AM dental sequences, containing a to-
tal of 810 PM teeth and 892 AM teeth. The experimental results reported here are based on

the experiments involving retrieving 29 subjects out of the 33 subjects, because the images

87

 

(0

Figure 4.8. Two examples of tooth correspondence. Tooth contours in (a) and (b) are paired
up in (c); tooth contours in (d) and (e) are paired up in (f).

of 4 remaining subjects cannot be used for following reasons: i) tooth contours of subjects
10 and 36 cannot be extracted due to poor image quality (Figs. 4.14 and 4.17), ii) subjects
14 and 21 have variations in dental structure due to tooth development or orthodontic treat-
ment (Figs. 4.15 and 4.16). We did not try to establish the identities of these 4 subjects, but
instead used the AM images of these 4 subjects as the imposter identities in the database.
In other words, the 29 subjects (312 PM sequences) used in our experiments were matched
to all the 33 subjects (316 AM sequences) in the database.

The dental radiographs are matched in two steps. The first step is shape registration -
the PM teeth are matched with the AM teeth individually. Matching a pair of teeth takes
~ 2 seconds on a PC with a 2.99 GHz Pentium 4 processor. It takes about 1.7 hours
to perform the matching process to retrieve a subject fiom the 33 subject database. To
estimate the probability distribution of the matching distances for contours of dental work
(p(de[w,-)) and (p(de[wg)), we use a Parzen window approach with Gaussian kernels
[25]. By comparing the accuracies of teeth matching (all with dental work) with different

values for the weight coeflicient in Equation (4.11), a = 0, 0.1,0.2, ..., 1, the optimum

88

 

Figure 4.9. Some AM images (a) and PM images (b) of a single individual in the database.

89

value of a, a = 1, is selected.

The second step is subject identification. The distances between images are generated
first. Figure 4.10 shows some examples of query images matched with a genuine and an
impostor database image. The distance score between two images with corresponding teeth
is smaller than the distance score for the imposter teeth pair. Figure 4.11 shows the top 4
retrievals for three different query images, and how the query shapes are matched to the
database shapes. In some cases, query images were not correctly matched because: (i) the
images were of poor quality, so the tooth shapes were not reliably extracted, (ii) the tooth
was only partially visible, and (iii) different individuals had similarly shaped teeth.

Figure 4.12 shows the Cumulative Match Characteristics (CMC) curve for retrieving
29 subjects from the database consisting of 33 subjects, compared with results obtained by
the method without using tooth index information. Without using tooth index information,
the accuracy for the top-1 retrieval is 20/29 (= 69%). Using top-2 retrievals, the retrieval
accuracy is 76%. The accuracy reaches 100% for the top-20 retrievals. Using the tooth
indices obtained by registering the images to the dental atlas, the accuracy for top-l retrieval
is 21/29 (= 72%). Using top-2 retrievals, the retrieval accuracy is 27/29 (=93%). The
accuracy reaches 100% when the top-7 retrievals are used. It is clear that using tooth index
information greatly improves the retrieval accuracy.

AM and PM images of the subjects that were not correctly retrieved in the top-l re-
trieval are shown in Figs. 4.18, 4.19, 4.20, 4.21, 4.22, 4.23, 4.24, 4.25. The reasons for the
incorrect retrievals are as follows: (i) subjects 2, 28, and 42 have only one panoramic ra-
diograph in AM records, and no panoramic radiographs in PM records. Matching between
different types of images (i.e., panoramic against bitewing) results in large matching dis-
tances, even for genuine subjects. (ii) The extensive overlapping of upper and lower teeth
in images of subjects 9 and 25 results in unreliably extracted tooth contours. (iii) Change
in the appearance of dentition due to loss of teeth or tooth filling for subjects 1 and 16.

(iv) The number of available teeth for matching AM and PM radiographs of subject 39 is

90

  

age

 
 

Qe lm

   
  

Query image

 

MD(T)=48.72

 

MD(T)=54.43

 

Imposter

(C)

Figure 4.10. Examples of matching. The gray lines represent the tooth shapes in the data-
base and the query images; the black lines represent the query shapes afler transformation.
Note that in these examples, the matching distance for the genuine AM images is smaller
than the matching distance for the imposter gilM images.

 

 

     

MD=21.33

MD=48.61

       

MD=17.43 TM MD=38.68 A' MD=62.18

(a) (b) (C)

Figure 4.11. The top-4 retrievals for 3 different queries. The first image in each column is
the query image and the remaining four images are the top-4 retrievals. The genuine AM
images are ranked first for these three queries.

92

insufficient for discriminating genuine and imposter subjects.

A second set of experiments involved retrieval of 29 PM subjects used in the previous
experiment from a larger AM database, consisting of 33 AM subjects in the previous exper-
iment and 100 additional subjects. The database is composed of 360 PM tooth sequences
(810 teeth) and 1,064 AM tooth sequences (3,271 teeth). It takes about 7 hours to perform
the matching processes to retrieve one subject from the 133 subject database. Figure 4.13
shows the Cumulative Match Characteristics (CMC) curve for retrieving 29 subjects from
the database consisting of 133 subjects. The accuracy for top-l retrieval is 19/29 (= 66%),
the top-4 accuracy is 23/29 (= 79%), and the top-13 accuracy is 26/29 (=90%). The reasons
for the failed retrieval of the remaining 3 cases within the t0p-13 retrievals are as follows:
(i) The appearance of dentition of subject 1 has changed due to loss of teeth (Figure 4.18)
and (ii) subjects 2 and 42 have only one panoramic radiograph in AM records, and no
panoramic radiographs in PM records (Figures 4.19 and 4.25). Matching between different
types of images (i.e., panoramic against bitewing) results in large matching distances, even

for genuine subjects.

4.4 Summary

This chapter examined methods for matching dental radiographs. The matching method
proposed here is based on the tooth contours of corresponding teeth, as well as shape of the
dental work region if dental work is present in both teeth. The matching distances obtained
based on tooth contours and dental work contours are fused to generate matching distances
between the unidentified subject and subjects in the database.

Experiments were conducted on retrieving 29 PM subjects from two databases of 33
AM subjects and 133 AM subjects, respectively. For the database of 33 AM subjects, it
takes about 1.7 hours to retrieve one subject. The top-1 retrieval accuracy is 21/29 (= 72%).

Using top-2 retrievals, the retrieval accuracy is 27/29 (=93%). The accuracy reaches 100%

93

 

 

 

 

 

 

 

 

 

I l I I I I
1- c::;;::::::::‘.:::::::::;::>
/, C J
0.95L - 1
s ' ‘ ‘ v
'4:
£09” c:::::::a ‘
"E’
a) C 3 :1
g 0.85— 1
“5 'I
g 08- l’ d
.D
(U
8 075 c J
$— '- _.
0. .
' —-0— With Tooth Index Infermatio
0-7 ” U —e—Without Tooth Index Information i
0.65 l l I l l I
0 5 10 15 20 25 30
Rank

Figure 4.12. Cumulative matching characteristics (CMC) curves for subject retrieval in the
database of 33 subjects. ‘

when the top-7 retrievals are used.

For the experiments with the database of 133 AM subjects, it takes about 7 hours to
retrieve one subject. The accuracy for top-1 retrieval is 19/29 (= 66%), the top-4 accuracy
is 23/29 (= 79%), and the top-13 accuracy is 26/29 (=90%). The reasons for failed retrieval
of the remaining 3 cases within the top-13 retrievals are (i) change in dentition appearance,
and (ii) matching between different types of dental radiographs.

Table 4.1 gives a breakdown of the computational requirements for each of the major
modules in our system. The column “Time for One Call” shows the time for one execution
of the program for the procedure. The column “Overall Time” shows the time the proce-
dure takes during the entire process of matching one PM query image set against one AM

database image set. The column “Avg. Number of Calls” means the average number of

94

 

 

 

 

0.95 r I

0.85 -

 

.0
‘0

T
J

 

.0

a
I
g

0.75 L‘

Probability of Identification

.0
‘1

 

 

 

 

0.65 I I 4 I I I
0 20 40 60 80 100 120

Rank

Figure 4.13. Cumulative matching characteristics (CMC) curves for subject retrieval in the
database of 133 subjects.

times the procedure is called during the entire process. Note that the AM database image
set has been processed beforehand. Each PM query contains several images. After image
segmentation, upper and lower rows of teeth are treated as different sequences. Each PM
query includes 6 images and 10.9 sequences on average, since some images have both up-
per and lower rows while others have only upper or lower row. The software has not been
optimized and most of the algorithms are implemented in Matlab 7.0. The speed of match-
ing process can be significantly accelerated if the algorithms are implemented in C/C++.
To get an idea of this speedup, the gradient vector flow (GVF) algorithm used for tooth
contour extraction was implemented in both Matlab and C. It takes 5.75 seconds for the
Matlab program to process a 159 x 236 image, while it takes only 0.76 seconds for the C
program to process the same image.

The retrieval accuracy could be improved by using digital radiographs since they pro-
vide more gray levels, which will lead to higher reliability of the extracted tooth contours

and dental work contours.

95

\nIr-nmrlrm -—
.‘lun‘h 5. 10'!“ - —

Might

 

Figure 4.14. Subject 10 was not tested for retrieval due to poor image quality. (a) AM
radiograph; (b) PM radiographs.

96

 

Right Left

Antemortem

Periapical
June 26, 1996

 

 

Figure 4.15. Subject 14 was not tested for retrieval due to eruption of new teeth in AM
radiographs. (a) AM radiographs; (b) PM radiographs.

97

 

 

Figure 4.16. Subject 21 was not tested for retrieval due to eruption of new teeth in AM
radiographs. (a) AM radiographs; (b) PM radiographs.

98

 

(b)

Figure 4.17. Subject 36 was not tested for retrieval due to poor image quality. (a) AM
radiograph; (b) PM radiographs.

99

 

Figure 4.18. Subject 1 was not correctly retrieved from the database due to changes in the
dentition caused by loss of teeth. (a) AM radiographs; (b) PM radiographs.

100

 

Figure 4.19. Subject 2 was not correctly retrieved fi'om the database due to incorrect AM
tooth contour extraction from the only available panoramic image. (a) AM radiograph; (b)
PM radiographs.

101

 

- Postmortem - 10418-01

 

Figure 4.20. Subject 9 was not correctly retrieved from the database due to incorrect AM
tooth contour extraction caused by overlapping upper and lower rows of teeth. (a) AM
radiographs; (b) PM radiographs.

102

Table 4.1. CPU (2.99 GHz Pentium 4) Time for Matching one PM Query Image Set to one
AM Database Image Set

 

 

Procedure Time for One can Overall Time Avg. NumBer of Calls
Feature Extraction 172.53 per Image 17.3m 6
Atlas Registration 0.165s per Sequence 1.8s 10.9
Matching 25 per Tooth Pair 3.1m 93

 

 

 

 

 

 

 

Figure 4.21. Subject 16 was not correctly retrieved fi'om the database due to changes in
tooth appearances in AM and PM radiographs. (a) AM radiograph; (b) PM radiograph.

103

[113597

Right Postmortem
5/31/0

 

(b)

Figure 4.22. Subject 25 was not correctly retrieved from the database due to incorrect AM
tooth contour extraction from the panoramic image and the bitewing images where upper
and lower rows of teeth overlap. (a) AM radiographs; (b) PM radiographs.

104

Iii-:11? Antemortem -

 

Figure 4.23. Subject 28 was not correctly retrieved from the database due to incorrect AM
tooth contour extraction from the only available panoramic image. (a) AM radiograph; (b)
PM radiographs.

105

 

Figure 4.24. Subject 39 was not correctly retrieved from the database due to insufficient
number of teeth in the AM image. (a) AM radiograph; (b) PM radiographs.

106

 

(b)

Figure 4.25. Subject 42 was not correctly retrieved from the database due to incorrect AM
tooth contour extraction from the only available panoramic image. (a) AM radiograph; (b)
PM radiographs.

107

CHAPTER 5

Conclusions and Future Directions

We have developed an automatic system for using dental radiographs to identify disaster
victims. The system has three stages: feature extraction, atlas registration, and matching
and retrieval. Related publications for Chapter 2 are [27], [27], [40], [18]. The publication
for Chapter 3 is [41]. Publications for Chapter 4 are [19], [40] and [18]. Major contributions

of the thesis are summarized in the following sections.

5.1 Feature Extraction

o Segmentation of Radiographs. We have proposed a fast marching based algorithm to
segment radiographs into homogeneous regions so that each region contains only one
tooth. This method utilizes the characteristics of dental radiographs in that soft tissue
and bone have different pixel intensity. This method can be extended to analyze other

types of radiographs [20].

o ASM-Based Tooth Contour Extraction. We have proposed an active shape model
(ASM) to extract tooth contours. The incorporated statistical shape information in
ASM deals with shape extraction difficulties caused by poor quality of dental radi-

ographs. We have made some changes to the traditional ASMs so that ASMs can be

108

used for tooth contour extraction. The proposed changes are as follows:

— Aligning Tooth Contours for Training. Tooth contours are smooth curves and
have no salient feature points. To align tooth contours, our method aligns the

given shape to an atlas and registers the points in the Shape to nodes in the atlas.

— Rotation and Scaling of Training Shapes During Training. The training method
incorporates rotation and scaling into the ASM so that rotation and scaling need

not be modeled in the transformation.

— Diflerent Searching Strategies for Crown and Root Nodes. All nodes in a tra-
ditional ASM use the same search strategy. For an ASM for tooth shape ex-
traction, crown nodes and root nodes have to use different search strategies
because the boundaries of crowns are located at the outermost gradients while

the boundaries of roots are located at the strongest gradients.

— Smoothed Gradient Field for Searching Optimal Positions of ASM nodes. Tra-
ditional ASMs use profile correlation to find the optimal positions for the nodes,
which requires the search range to be sufliciently large to include the optimal
position. If the true optimal position is not in the search range, an incorrect
position will be located for the nodes. We use the smoothed gradient field to
provide the search guidance for the root nodes in the ASM, so that even if the
optimal position is not in the search range, a position closest to the true optimal

position can be located.

— Robust Weighting During ASM-based Shape Approximation. Newly detected
node positions need to be approximated with the trained ASMs. To deal with
the noise in the detected positions, robust weighting used in linear regression is
applied. Since rotation and scaling have been modeled with ASMs, the entire
approximation procedure can be deduced into a linear regression form in vector

space, and thus the robust weighting can be used.

109

o Extraction of Contours of Dental Work. We use anisotropic diffusion to enhance the

5.2

5.3

images and extract the contours of dental work with a reasonable assumption that

pixel values of dental restoration follow a Gaussian distribution [18].

Atlas Registration

Hybrid HMM/SVM Model for Representation of Dental Atlas. Tooth states in the
HMM combined with SVMs model the shape of teeth, and distance states in the

HMM model the inter-teeth distance caused by missing teeth [41].

Construction of Observation Sequences. An observation sequence is an alternating
sequence of tooth shapes and distances between successive teeth. To compensate for
the difference between image resolutions of AM and PM images, the tooth shapes
are normalized to a fixed width, and the distances between teeth are regularized with

the width of neighboring teeth [41].

Matching

Matching of Tooth Contours. Tooth contours are open curves. To match tooth con-
tours, correspondence between the tooth contours has to be established. We have de-
veloped an iterative procedure to align tooth contours and compute distances based

on the corresponding segments of the two curves [18].

Matching of Contours of Dental Work. Topological changes may occur between the
contours of the same type of dental work in different images. We have developed an
algorithm to align dental work and compute the distance between two images using

a metric of overlapping pixels [18].

0 Fusion of Matching Scores of Tooth Contours and Contours of Dental Work via

Posterior Probability. Dental restorations are not always present in the dental radi-

110

 

Figure 5.1. A dental X-ray shows loss of jaw bones caused by periodontal disease.

ographs. To firse the matching distances between tooth contours and dental restora-

tion contours, we developed a scheme based on posterior probability [18].

0 Calculation of Distances between Subjects Based on Distances between Teeth. We
developed a scheme to compute the distance between an image and a subject and the

distance between two subjects [18].

5.4 Future Directions
The following directions should be considered for firture research.

a Abnormality-Based Identification. Dental abnormalities, such as tumors, periodontal
disease, tooth malformations and abnormal resorptions, are important features used
by human experts in matching dental radiographs [1]. Figure 5.1 shows an example
of loss of j aw bones due to periodontal disease. To detect dental abnormality, a dental
radiograph needs to be registered to a dental atlas, and a statistical approach is needed
to discover the uniqueness of the given image in terms of tooth shape, tooth position,

and intensity, etc.

111

0 Knowledge Inference. Knowledge of the victim, such as age, gender, and periodontal
disease, etc., can be inferred from dental radiographs and matched with the side
(ancillary) information of suspected victims to narrow the search scope. An expert
system incorporating rich odontological knowledge needs to be developed to fulfill

the task.

0 User Feedback-Based Improvement. A machine learning scheme can be developed
to improve the system based on user feedback, including user correction on tooth

contours, tooth indices, and final decision by human experts.

0 Matching of Non-tooth Feature. Features shown in dental radiographs, e.g., the tra-
becular pattern of mandible bones and the shape of sinus and canals in the mandible

and maxilla bones [1], can be extracted and used for identification.

112

APPENDIX A

Database Description

The number and types of images as well as the source of images for each subject are listed
in table A.l. In the table, source A is the Criminal Justice Information Service (CJIS)
division of the FBI; source B is the Washington State Police Department; source C is Dr.
Howell from West Virginia University. The subject IDs are not continuous due to removal
of some duplicate subjects from the database after the subjects were indexed. So, the total

number of subjects is only 33 though the subject IDs range from 1 to 42. '

113

Table A. 1. List of Types, Numbers, and Sources of Images in the Database.

 

Number and T e of Images

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Sufijfct Antemortem (AM) Postmortem (PM) Source
Panoramic Bitewing Periapical Panoramic Bitewing Periapical
1 2 2 2 0 7 0 8 A
2 1 0 0 0 2 12 A
3 1 0 6 0 0 6 A
4 1 4 0 O l 1 A
5 O 2 O 0 2 0 A
6 O 4 1 0 1 15 A
8 0 6 O O 2 15 A
9 0 2 10 0 2 14 A
10 1 0 O 0 0 10 A
11 0 7 4 0 1 13 A
12 0 2 l 0 1 2 A
13 O 10 0 0 2 14 A
14 0 2 1 0 2 14 A
16 0 0 1 0 0 l B
20 0 3 0 0 2 14 B
21 0 4 1 0 2 14 B
22 0 9 14 0 0 16 B
23 0 4 14 0 2 14 B
24 2 4 16 O 2 14 B
25 1 4 1 O l 17 B
26 0 4 14 0 0 16 B
27 2 4 0 0 0 16 B
28 2 0 O 0 0 18 B
29 0 2 l 0 2 14 B
31 0 4 14 O 2 4 C
32 0 4 0 0 4 0 C
33 O 4 14 0 4 0 C
35 0 2 O O 2 O C
36 l 0 0 O 4 0 C
37 0 2 l4 0 0 16 C
39 0 O 1 0 2 0 C
42 1 0 0 0 0 6 C

 

114

 

APPENDIX B

Anisotropic Diffusion

The anisotropic diffusion method was introduced by Perona and Malik [48] and modified
by others [64], [37], [14]. It is used for smoothing images while preserving boundaries in
the images, which is a desired property for image enhancement. Let the original image be
denoted as 1(113, y, 0), and the transformed image after the t“h iteration be I (at, y, t). Then

the anisotropic diffusion equation is given by

g = div(c(:c, y, t)VI), (B.1)

where div is the divergence operator, V is the gradient operator, and C(x, y, t) is the smooth-
ing criterion. When c is constant, Equation (8.1) reduces to the isotropic heat difl'usion
equation, which is a smoothing operation on the image. If we want to encourage smooth-
ing within each region in preference to smoothing across the boundaries, C(x, y, t) can be
defined as c(:c, y, t) = g([VI(:r:, y, t)[). The function g(.) should be chosen such that when
[VI(:c, y, t)[ is small, g(.) is large to encourage smoothing, and when [VI (:c, y, t)[ is large,
g(.) is small to inhibit smoothing. Since the boundaries of regions are assumed to have
a large gradient magnitude [V1(ac, y, t)[, this process smoothes the pixels inside the ho-
mogeneous regions, while suppressing smoothing across the boundaries. Thus, the means

of the intensities inside the regions do not change while their variance decreases. If we

115

assume that gray level distributions of each region can be modeled as a Gaussian, this has
the effect of reducing the overlap of the Gaussians for different regions and minimizing the
classification error. One option of specifying g(.) is Weickert’s definition [61]:
1, if a: = 0
9(33) = (32)
1— e"Cm(”/’\)—2m, ifzc > 0,
where /\ is the threshold for the flux change, Gm is selected such that g’()\) = 0, and m
controls the speed of the flux changes. For enhancing dental radiographs, the values for the

parameters were chosen as A = 5 and m = 12.

116

BIBLIOGRAPHY

[1] ABFO body identification guidelines. http://www.abfo.org/ID.htm.
[2] Disaster victim identification. http://www.interpol.int/Public/DisasterVictim/Guide.

[3] Disaster victims identification information management center starts operation in
Phuket. http://english.people.com.cn/200501/12/eng20050112-170385.html.

[4] Lowess and loess: Local regression smoothing. http://www.mathworks.com/access
Arelpdesk/help/toolbox/curvefit/ch_data7.htrnl.

[5] Smoothing spline : Fitting data (curve fitting toolbox). http://www.mathworks.com
/access/helpdesk/help/toolbox/curvefit/ch_fit1 5.html.

[6] Dental records beat DNA in tsunami IDs. New Scientists, 2516212, Sept. 2005.
http://www.newscientist.com/article.ns?id=mgl 8725 163 .900.

[7] Forensic identification of 9/11 victims ends, February 2005.
http://abcnews.go.com/WNT/story?id=525937&page=l.

[8] B. Adams. The diversity of adult dental patterns in the United States and the im-
plications for personal identification. Journal of Forensic Science, 48(3):497—503,
2003.

[9] B. Adams. Establishing personal identification based on specific patterns of missing,
filled and unrestored teeth. Journal of Forensic Science, 48(3):487—496, 2003.

[10] E. Allwein, R. E. Schapire, and Y. Singer. Reducing multiclass to binary: A unifying
approach for margin classifiers. J. Machine Learning Research, 12113—141, 2000.

[11] E. Arana and L. Marti-Bonmati. Digital dental radiology.
http://www.priory.com/den/dentrvgl .htrn.

[12] S. Belongie, J. Malik, and J. Puzicha. Feature based 2d shape transformation. IEEE
Trans. Pattern Analysis and Machine Intelligence, 24(4):509—522, 2002.

[13] Paul J. Besl and Neil D. McKay. A method for registration of 3d shapes. IEEE Trans.
Pattern Analysis and Machine Intelligence, 14(2):239—256, 1992.

117

[14] M.J. Black, G. Sapiro, D.H. Marimont, and D. Heeger. Robust anisotropic diffusion.
IEEE Trans. Image Processing, 7(3):421—432, 1998.

[15] FL. Bookstein. Principal warps: thin-plate splines and the decomposition of defor-
mations. IEEE Trans. Pattern Analysis and Machine Intelligence, 11(6):567—585,
1989. '

[16] W. M. Campbell. A SVM/HMM system for speaker recogniton. In Proc. ICASSP,
volume 11, pages 209—212, Hong Kong, April 2003.

[17] Andrea Castellani, Debora Botturi, Manuele Bicego, and Paolo Fiorini. Hybrid
HMM/SVM model for the analysis and segmentation of teleoperation tasks. In Proc.
IEEE International Conference on Robotics & Automation, pages 2918—2923, New
Orleans, LA, April 2004.

[18] Hong Chen and Anil Jain. Dental biometrics: Alignment and matching of dental
radiographs. IEEE Trans. on Pattern Analysis and Machine Intelligence, 27(8): 13 19-
1326, 2005.

[19] Hong Chen and Anil Jain. Dental biometrics: alignment and matching of dental
radiographs. In Proc. WAC V (Workshop on Applications of Computer Vision), pages
316—321, Breckenridge, Colorado, January 2005.

[20] Hong Chen and Carol Novak. Segmentation of hand radiographs using fast marching
methods. In Proc. SPIE Conference on Medical Imaging, volume 6144, pages 68—76,
San Diego, California, 2006.

[21] Yi Chen, Anil Jain, and Sarat Dass. Fingerprint deformation for spoof detection. In
Proc. Biometric Symposium, Crystal City, VA, 2005.

[22] H. Chui, J. Rambo, R. Shultz, and A. Rangarajan. Registration of cortical anatomical
structures with robust 3d point matching. In Proc. Information Processing in Medical
Imaging, pages 168—1 81, 1999.

[23] T. F. Cootes and C. J. Taylor. Active shape models - ‘smart snakes’. In Proc. British
Machine Vision Conf, pages 266—275, 1992.

[24] R. Derakhshani, Stephanie Schuckers, and Larry Homak. Determination of vitality

from a non-invasive biomedical measurements for use in fingerprint scanners. Pattern
Recognition, 36(2):383-396, 2003.

[25] Richard O. Duda, Peter E. Hart, and David G. Stork. Pattern Classification, chap-
ter 10, pages 164—174. Wiley Interscience, 2nd edition, 2001.

118

[26] Nicolae Duta, Anil K. Jain, and Marie-Pierre Dubuisson-Jolly. Automatic construc-
tion of 2D shape models. IEEE Trans. Pattern Analysis and Machine Intelligence,
23(5):433—446, May 2001.

[27] G. Fahmy, D. Nassar, E. Haj-Said, H. Chen, 0. Nomir, J. Zhou, R. Howell, H. H. Am-
mar, M. Abdel-Mottaleb, and A. K. Jain. Towards an automated dental identification
system (ADIS). In Proc. ICBA (International Conference on Biometric Authentica-
tion), volume LNCS 3072, pages 789—796, Hong Kong, July 2004.

[28] M. Figueiredo, J. Leitao, and Anil K. Jain. Unsupervised contour-representation and
estimation using B-splines and a minimum description length criterion. IEEE Trans.
Image Processing, 9(6): 1075—1087, 2000.

[29] Mario Figueiredo and Anil K. Jain. Unsupervised learning of finite rrrixture models.
IEEE Trans. Pattern Analysis and Machine Intelligence, 24(3):381—396, 2002.

[30] Aravind Ganapathiraju, Jonathan E. Hamaker, and Joseph Picone. Applications of
support vector machines to speech recognition. IEEE Trans. Signal Processing,
52(8):2348—2355, 2004.

[31] Paul W. Goaz and Studart C. White. Oral Radiology—Principles and Interpretation.
The C. V. Mosby Company, St. Louis, 1982.

[32] S. Gold, A. Rangarajan, C. Lu, S. Pappu, and E. Mjolsness. New algorithms for 2d
and 3d point matching: Pose estimation and correspondence. Pattern Recognition,
31(8):]019—1031,1998.

[33] M. Goldstein, Sweet D. J ., and Wood R. E. A specimen positioning device for dental
radiographic identification. Journal of Forensic Science, 43: 185—189, 1998.

[34] Rafael C. Gonzalez and Paul Wintz. Digital Image Processing. Addison-Wesley
Publishing Company, Inc., 1977.

[35] G. Gustafson. Forensic Odontology. Staples Press, 1966.

[36] S. P. Han. A globally convergent method for nonlinear programming. Journal of
Optimization Theory and Applications, 221297, 1977.

[37] Hao Huang and Junghua Wang. Anisotropic diffusion for object segmentation. In
Proc. IEEE International Conference on Systems, Man, and Cybernetics, volume 3,
pages 1563—1567, Nashville, TN, October 2000.

[3 8] KC. Hui and Yadong Li. Feature based 2d shape transformation. In Proc. IEEE Con-
ference on Information Visualization (IV ’97), pages 337—342, London, UK, August
1997.

119

[39] A. K. Jain, R. Bolle, and Pankanti S., editors. BIOMETRICS: Personal Identification
in Networked Society. Kluwer Academic Publishers, 1999.

[40] Anil Jain and Hong Chen. Matching of dental x—ray images for human identification.
Pattern Recognition, 37(7): 1519—1532, 2004.

[41] Anil Jain and Hong Chen. Registration of dental atlas to radiographs for human iden-
tification. In Proc. of SPIE Conference on Biometric Technology for Human Identifi-
cation 11, volume 5779, pages 292-298, Orlando, Florida, 2005.

[42] Eugene Lee. Choosing nodes in parametric curve interpolation. Computer-Aided
Design, 21 :363—370, 1989.

[43] Mohammad H. Mahoor and Mohamed Abdel-Mottaleb. Classification and numbering
of teeth in dental bitewing images. Pattern Recognition, 38(4):577—586, 2005.

[44] T. Matsumoto, H. Matsumoto, K. Yamada, and S. Hoshino. Impact of artificial
“gummy” fingers on fingerprint systems. volume 4677, pages 275—289, April 2002.

[45] J. McGarvey. WinID: Dental identification system, 2005. http://www.winid.com.
[46] J. Murray. Prevention of oral disease. Oxford: Oxford University Press, 1986.

[47] Patrice O’Shaughnessy. More than half of victims IDd. New York Daily News, 11
Sep.2002.

[48] Pietro Perona and Jitendra Malik. Scale-space and edge detection using anisotropic
diffusion. IEEE Trans. Pattern Analysis and Machine Intelligence, 12(7):629—639,
1990.

[49] John W. Peterson. Arc length parameterization of spline curves.
http://www.saccade.com/writing/graphics/.

[50] John C. Platt. Probabilistic outputs for support vector machines and comparison
to regularized likelihood methods. In Alexander J. Smola, Peter Bartlett, Bernhard
Schlkopf, and Dale Schuurrnans, editors, Advances in Large Margin Classifiers. MIT
Press, Cambridge, MA, 1999.

[51] I. A. Pretty and D. Sweet. A look at forensic dentistry - part 1: The role of teeth in
the determination of human identity. British Dental Journal, 190(7):359—366, April
2001.

[52] D. M. Russell, P. P. Maglio, R. Dordick, and C. Neti. Dealing with ghosts: managing
the user experience of autonomic computing. IBM systems Journal, 42(1):177—188,
2003.

120

[53] Marie Sandstrom. Liveness detection in fingerprint recognition systems. Master’s
thesis, Examensarbete utfort i Informationsteori, vid Linkopings tekniska hogskola,
2004.

[54] James Sethian. Level Set Methods and Fast Marching Methods. Cambridge University
Press, Cambridge, UK, 2nd edition, 1999.

[55] H. Silverstein. Comparison of antemortem and postmortem findings. In: Manual of
forensic Odontology. Ontario: Manticore, 3rd edition edition, 1995.

[56] Milan Sonka, Vaclav Hlavac, and Roger Boyle. Image Processing - Analysis, and
Machine Vision. Brooks/Cole, Thomson Learning, Florence, KY, 2nd edition, 1999.

[57] M. B. Stegmann and D. D. Gomez. A brief introduction to statistical shape analysis.
Technical report, Richard Petersens Plads, Building 321, DK-2800 Kgs. Lyngby, Mar.
2002.

[5 8] Ambika Suman. Knowledge-Based Intelligent Information and Engineering Systems,
volume 2774/2003 of Lecture Notes in Computer Science, chapter Human Factors that
Affected the Benchmarking of NAFIS: A Case Study, pages 1235—1244. Springer
Berlin / Heidelberg, 2003.

[59] Panarat Thepgumpanat. Thai tsunami forensic centre produces first IDs. Reuters,
http://www.alertnet.org/, 18 Jan. 2005.

[60] H. Wang, J. Kearney, and K. Atkinson. Arc-length parameterized spline curves for
real-time simulation. In Proc. 5th International Conference on Curves and Surfaces,
pages 387—396, San Malo, France, June 2002.

[61] J. Weickert. Anisotropic Diflusion in Image Processing. B.G. Teubner, 1998.

[62] T. F. Wu, C. J. Lin, and R. C. Weng. Probability estimates for multi-class classification
by pairwise coupling. In S. Thrun, L. Saul, and B. Scholkopf, editors, Proc. Advances
in Neural Information Processing Systems (NIPS), volume 16, Cambridge, MA, 2003.
MIT Press.

[63] Chenyang Xu and Jerry L. Prince. Snakes, shapes, and gradient vector flow. IEEE
Trans. Image Processing, 7(3):359-369, March 1998.

[64] Yongjian Yu and ST. Acton. Speckle reducing anisotropic diffusion. IEEE Trans.
Image Processing, 11(1 1): 1260—1270, 2002.

[65] Dengsheng Zhang and Guojun Lum. Review of shape representation and description
techniques. Pattern Recognition, 37(1): 1—19, 2004.

121

 

I)"[[;[[[gj[[[1]