CRANIOFACIAL RECONSTRUCTION USING HIERARCHICAL B-SPLINE INTERPOLATION By KATRINA MARIE ARCHER B.Eng., McGill University, 1992 A THESIS SUBMITTED IN PARTIAL FULFILMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF APPLIED SCIENCE in THE FACULTY OF GRADUATE STUDIES (Department of Electrical and Computer Engineering) We accept this thesis as conforming to the required standard THE UNIVERSITY OF BRITISH COLUMBIA August 25, 1997 © Katrina Marie Archer, 1997 In presenting this degree at the thesis in University of partial fulfilment of of department this thesis for or by his or requirements British Columbia, I agree that the freely available for reference and study. I further copying the representatives. an advanced Library shall make it agree that permission for extensive scholarly purposes may be her for It publication of this thesis for financial gain shall not is granted by the understood that head of copying of gLeCJTPAPAl, 9- rQrnVuTfcjg. The University of British Columbia Vancouver, Canada Date • AoCo". DE-6 (2/88) 7?r- / or be allowed without my written permission. Department my t^VJQ) \r^=£S:'fe_lrO<b Abstract Craniofacial forensic reconstruction is often the only means of determining a deceased individual's appearance. Current manual methods of estimating the appearance of the individual from his or her skull are extremely expensive and time-consuming. Normally a single facial estimate is produced and publicized. As a result, the success rate for identification resulting from facial reconstruction is on the order of only 50%. A software tool that produces multiple threedimensional likenesses that more completely cover the range of likely appearances due to factors such as body fat content, and nose and lip appearance would improve this success rate. The application should closely simulate the artist's technique of generating a base facial shape with rough details that are later refined. The prototype generates a generic hierarchical B-spline surface around a 3D scan of the skull. Sparse data points representing tissue thickness are first placed at landmarks about the scan. The generic surface is subsequently automatically placed in order to smoothly and evenly interpolate the data points. This thesis presents a new interpolation method that is well adapted to fitting a hierarchical surface to sparse data points. A reasonable facial approximation is produced from a minimal amount of data using this technique. Multiple facial base shapes are easily created by using the appropriate tissue depths for race, age, sex and body fat content. Facial details such as the eyes, nose and lips can be edited after interpolation. These basic techniques are appropriate for use in an eventual commercial 3D forensic reconstruction tool. ii Table of Contents Abstract ii Table of Contents iii List of Tables v List of Figures vi Acknowledgements ix Dedication x Chapter 1 Introduction 1 Chapter 2 5 Forensic Reconstruction 2.1 Overview 5 2.2 Identification of the Individual 8 2.2.1 Superimposition 9 2.2.2 Craniofacial Reconstruction 12 2.3 The Way Ahead Chapter 3 17 Parametric Curves and Surfaces 20 3.1 Overview 20 3.2 Parametric Representation 20 3.3 B-Spline Curves and Surfaces 24 3.3.1 Uniform Non-rational 25 3.3.2 B-spline Surfaces 30 3.4 Hierarchical Representations 31 3.4.1 Wavelets 31 3.4.2 Overlays 34 3.5 Surface Representation Implemented Chapter 4 40 Curve and Surface Fitting 42 iii 4.1 Overview 42 4.2 Related Work 43 4.2.1 Constraint-Based Fitting 43 4.2.2 Finite Element Analysis 46 4.2.3 Direct Manipulation of a Single Data Point 52 4.3 Fitting Method Chosen 54 4.3.1 Interpolation of Multiple Data Points 55 4.3.2 Multi-resolution Interpolation 57 4.3.3 Extension to Surfaces 61 4.3.4 Extension to Tangent Fitting 65 4.4 Summary Chapter 5 67 Results 69 5.1 Test Overview 69 5.2 Results Using Standard Landmarks 74 5.3 Results Using Standard and Extrapolated Landmarks 76 5.4 Tangential Fit 83 5.5 Modification of Facial Features After Interpolation 85 5.6 Artists'Feedback 87 5.7 Summary 88 Chapter 6 Summary and Conclusions 90 Bibliography 94 Appendix 1: Standard Tissue Thickness Measures iv 100 List of Tables Table 1 Tissue thickness measures, American Caucasoids (mm) 101 Table 2 Tissue thickness measures, American Blacks (mm) 102 Table 3 Tissue thickness measures, Southwestern Indians (mm) 103 v List of Figures Figure 1: Amerindian skull [Source: 24, p. 147] 7 Figure 2: Black American skull [Source: 24, p. 148] 7 Figure 3: Caucasian skull [Source: 24, p. 146] 8 Figure 4: Ruxton case line drawings [Source: 34, pp. 426-427] 10 Figure 5: Three-dimensional Reconstruction [Source: 34, p. 444] 14 Figure 6: Two-dimensional Reconstruction [Source: Cam Pye, Royal Canadian Mounted Police] 15 Figure 7: Lateral craniograph reconstruction [Source: 22] Figure 8: Example of a parametric curve, (x(t), y(t)) [Source: 13, p. 330] 16 22 Figure 9 B-spline curve with one segment 26 Figure 10 B-spline curve with 6 segments 26 Figure 11: B-spline blending functions 27 Figure 12: B-spline basis function with basis segments shown 28 Figure 13 Effect of replicating control points 29 Figure 14 A 16-patch surface described by 49 control vertices [Source: 14] 36 Figure 15 A 16-patch surface with refinement and overlay control vertices [Source: 14] 36 Figure 16 Local refinement of adjacent regions [Source: 14] 37 Figure 17 Offset orientation [Source: 14] 38 Figure 18 Control graphs of a surface patch at various refinement levels, with all offsets zero... 39 Figure 19 Refinement level 3 after editing 40 Figure 20 Offset preservation after underlying surface modification 40 Figure 21 Restricting control vertex movement 54 Figure 22 Interpolation of multiple data points 57 Figure 23 Displacement fraction (DF) =1.0 59 vi Figure 24 Effects of subdivision before performing interpolation. DF = 1.0 60 Figure 25 Effect of initial displacement fraction. Interpolation at given DF, refinement and reinterpolation of remaining distance 61 Figure 26 B-Spline patch interpolating 5 data points 63 Figure 27 Hierarchical surface interpolation. DF =1.0 64 Figure 28 Hierarchical surface interpolation. DF = 0.4 65 Figure 29 Polygonal model of skull 69 Figure 30 B-spline surface model of head 70 Figure 31 Cylindrical surface with 3 refinement levels, all offsets zero, and polygon model with vertical dowel 71 Figure 32 Cylindrical surface fit to dowel 71 Figure 33 Cylindrical surface model with 1 non-zero offset at level 2 Figure 34 Cylindrical surface fit to dowel, with bulging produced by non-zero offset Figure 35 Surface model of head with zero offsets at levels 1 and 2 72 72 73 Figure 36 Skull model with standard dowel set 74 Figure 37 Interpolation of standard dowel set 75 Figure 38 Skull with standard plus extrapolated dowels 77 Figure 39 Interpolation of standard plus extrapolated dowel set 77 Figure 40 Overconstrained surface. Note undesirable bulging at lips 79 Figure 41 Improved zero offset model with extrapolated dowels 79 Figure 42 Zero offset model superimposed on skull 81 Figure 43 Improved model at levels 0 and 1 82 Figure 44 Improved model with zero offsets at level 2 83 Figure 45 Optimal fit using improved head model 83 Figure 46 View of bulging at forehead seen from below 84 Figure 47 Tangential fit 85 Figure 48 Modification of surface details through editing 86 vii Figure 49 Location of standard landmarks 100 viii Acknowledgements This work was generously funded by the Natural Science and Engineering Research Council of Canada, by MacDonald Dettwiler and Associates of Richmond, BC, and by the British Columbia Advanced Systems Institute. I am very grateful to Cam Pye and Peter Petersen, Forensic Artists with the Royal Canadian Mounted Police, for their invaluable assistance in testing the software and for their helpful comments and suggestions. I would also like to thank Dr. David Forsey and Dr. Rabab Ward for taking me on at the eleventh hour. My association with this project would not have been possible without their support and commitment. Finally, thanks go to Mom and Dad for letting me go my own way without ever batting an eyelash, even when they had doubts, to Guylain for moral support and reality checks, to everyone at the Imager Lab for welcoming the engineer into their midst, and to all my friends (you know who you are) for all the good times, over the past two years, that helped preserve my sanity. Katrina Archer S A Ganache Vancouver, BC August 25 , 1997 th ix Dedication To Guylain, for your constant support and belief in me. I couldn't have done it without you! x Chapter 1 Introduction One aspect of forensic pathology and archeology is the determination of an individual's appearance prior to death for the purposes of identification, through reconstruction of facial features based on known relations to skull features. Facial reconstruction in itself is not a means of positive identification: the likenesses created are publicized in the hope of generating leads that would ultimately confirm the identity of the individual in question. Current methods of estimating the appearance of the individual from his or her skull are extremely time-consuming and expensive. Normally a single facial estimate is produced, and as a direct result, success rates for identification resulting from facial reconstruction are on the order of only 50%. This single likeness is not necessarily the best estimate of a person's appearance, due to the difficulty in determining, solely from cranial information, both body fat content prior to death and the appearance of features such as the nose, lips and eyes. Another factor that affects the success rate is the variability introduced by artistic interpretation: different artists will produce quite differing facial estimates from the same skull; conversely, the same artist may create several similar faces from a set of completely different skulls. Low success rates are also caused by the lack of statistically significant tissue depth data, since facial reconstruction relies on knowing the tissue depths at specific landmarks on the skull. Most studies have very small population samples. As well, they were done on cadavers lying in a prone position, so the tissues sagged, and the resulting measurements do not necessarily reflect the true tissue thickness found in living individuals. The goal is to improve the success rates for victim or suspect identification by finding a way to quickly and cost-effectively generate a variety of facial representations. This is based on the assumption that one of the multiple likenesses will most closely approximate the individual's 1 actual appearance, thus facilitating recognition by family, friends or acquaintances. A software application that can produce a variety of plausible three-dimensional facial reconstructions for a given skull would be of benefit to law enforcement agencies. The software would allow faster, easier and more efficient generation of multiple representations of an individual that would take into account differences in facial appearance not apparent from cranial analysis. In order to be useful to the artist, a software application that performs facial reconstruction needs to be easy to use, and must closely simulate the process already familiar to the artist. The idea is not to replace the artist, but to improve the process by which he or she creates a facial reconstruction, allowing quicker generation of multiple likenesses, with the ability to easily specify various facial features that cannot be determined from cranial parameters. The basic facial shape is determined from the skull and tissue depth information, while details such as the eyes, nose and lips are first roughed in. Different facial base shapes are built using tissue depth data that take into account race, sex, age and body fat content. The facial details are then refined and changed by the artist to produce differing facial estimates from the same basic facial shape. The prototype application described in this thesis makes use of recent advances in threedimensional digital technology. A three-dimensional digitized polygonal model of the skull is first obtained by laser scanning or medical imaging techniques such as CAT scans or MRI. A generic surface model of a head is then generated about the scan. This surface model is then automatically placed in order to smoothly and evenly interpolate tissue thickness values at specific landmarks on the skull. The primary contribution of this thesis to the creation of a fullfledged facial reconstruction package is the development and evaluation of an interpolation algorithm for sparse data points that in this case represent the tissue depth information. The premise is that once the initial manual work of finding the landmark locations is done, considerable timesavings can be obtained through the ability to interactively update the tissue 2 depth information, based on such parameters as gender, race, age and body fat content. The software can quickly generate each new facial estimate once the tissue depths have been changed. It should be noted that the surface model representing the face must still be editable after performing each estimate, so that the artist can alter features such as the nose, eyes and lips. Chapter 2 will discuss how estimation of an individual's appearance from the skull is currently accomplished. This usually involves placing dowels representing known average tissue thickness at predetermined landmarks on the skull, and employing a trained forensic artist to use clay or other media to build up the facial features around these landmarks. To simulate current reconstruction methods, it is necessary to choose a surface representation that lends itself to fitting and interpolation, and which is also well suited to interactive editing. To approximate the technique by which an artist first roughs in the general shape of the face then layers on the facial details, the representation chosen must be able to describe surfaces with varying levels of detail. Since the desired application must also run quickly, the chosen surface representation must be fairly compact. B-spline curves and surfaces, and in particular hierarchical or multi-resolution B-splines, meet all these requirements. Chapter 3 will give a brief overview of parametric curves and surfaces, in order to introduce B-spline curves and surfaces and their hierarchical or multi-resolution representations. Since a generic facial model is to be fitted to tissue depth data, Chapter 4 will introduce curve and surface interpolation. The fitting technique chosen should produce a good likeness of a face, but optimally be simple and fast. Various methods of interpolation will be discussed, together with the interpolation algorithm developed for this project. Techniques for controlling the fit of the interpolation will also be presented. Ideally, the interpolation technique will produce a good 3 facial fit from a small amount of sparse tissue depth data. Chapter 5 will present results. The object of the tests is to evaluate whether the interpolation algorithm developed is capable of producing a reasonable facial approximation from sparse data, and to determine the optimal procedure and amount of data needed to obtain a good fit. Discussion, conclusions and possible future work will be discussed in Chapter 6. 4 Chapter 2 Forensic Reconstruction 2.1 Overview Archeologists, forensic anthropologists and pathologists have long studied human skeletal remains for a variety of purposes, including applications in medical-legal problems, understanding extinct populations and personal identification in police investigations. The goal of a forensic investigation is to answer a standard set of questions [29]: • Did the remains belong to a person? • How many individuals were in the sample? • What was the sex of the individual? • What was the age of the individual? • How tall were they? • What was their weight/body shape? • What was their race? • Can they be positively identified? • What was their nutritional and health history? • Did they experience trauma or occupational stress? Often, the skeletal remains are incomplete, making it difficult to determine exact answers to all 5 of the above questions. The skull, however, is useful in determining many of the above factors. For example, the condition of skull sutures and dentition [30] [31] is useful in determining the age of an individual. Dentition is most useful for determining the age of young children. Skull sutures, while not providing an exact estimate of age, are used to corroborate other age indicators, and their shape also helps to determine race [24]. Other features of the skull are used to determine sex and race [46] [24]. Large brow ridges and squarer, heavier chins are found in many males, whereas females tend to have more rounded chins and less pronounced brow ridges. Various facial shapes are more common to different races: Inuit tend to have long, high and narrow crania, with long faces, and long noses. Asians have less developed brow ridges. An important feature of the face in determining race is the nose area, as the shape of the nose opening and the bones around it are quite racially specific, as are shape of the jawbone, or mandible. Mongoloids and Amerindians (Figure 1) tend to exhibit a more robust, square mandible, whereas Negroids (Figure 2) show a more oblique mandibular angle, and Caucasoids (Figure 3) a medium mandibular angle. The primary focus of many criminal investigations is often the identification of the individual, and here the skull can be most useful. Once race and sex have been determined from an examination of the complete skeleton, the skull can be used to reconstruct the facial appearance of the individual. 6 Figure 1: Amerindian skull [source: 24, p. 147] F i g u r e 3: C a u c a s i a n s k u l l [source: 24, p. 146] 2.2 Identification of the Individual The main goal of biological anthropology is the study of human skeletal remains, for the purpose of identifying individuals belonging to extinct populations. Forensic anthropology is primarily concerned with the identification of individuals, for the purpose of identifying suspect or victim in a criminal investigation. Clues in a criminal investigation generally fall into one of two categories: biological or peripheral. Biological evidence usually consists of the physical remains of the body itself, whereas peripheral evidence consists of clothing, photographs or personal belongings. Possession of a relatively complete skeleton is helpful in determining the basic characteristics of a person, such as race and sex. Often, to aid in the identification of the individual, or when there is a complete lack of peripheral evidence, some form of reproduction of the face from the skull is 8 used in an attempt to identify the remains. Several different facial reproduction techniques exist [5]. The first, facial restoration, consists of rebuilding facial tissues that have been severed, crushed or otherwise mutilated, but which are still present on or around the body. The goal is to reestablish the presumed appearance of the individual to establish or verify identity. This technique will not be discussed further. The second technique is superimposition, where an image of the skull is superimposed on a portrait or photograph of an individual. This technique requires the availability of photographs of potential candidates for identification, in order for an exact match to be achieved. Generally, it is used to eliminate possible matches. The third method is craniofacial reconstruction, in either 2 or 3 dimensions. A representation of the face is built up from knowledge of tissue thickness at known landmarks on the skull. A two dimensional facial reconstruction is generally an artist's drawing of the face based upon photographs and tracings of the skull. A three dimensional reconstruction uses a cast of the skull, or the actual skull, over which a sculptor builds up the facial features with clay. Facial reconstruction is generally used when the identity of the deceased is not known, in the hope of generating leads in the form of recognition by friends or family of the deceased, after the likeness has been widely publicized. 2.2.1 Superimposition Superimposition consists of matching a photograph of an individual with the skull. Early attempts tried to match historical figures with a skull. In 1883, Welcker identified Immanuel Kant's skull [26][34] by matching orthogonal perspective drawings of outlines of the skull with the death mask of Kant. In 1926, Pearson matched the skull of George Buchanan with his portrait 9 [28][34]. Subsequent attempts were used in criminal investigations. Glaister, Brash and Smith, in 1937, helped solve the Buck Ruxton murder case [28][26][34]. Two skulls, allegedly from the victims, Isabella Ruxton and Mary Rogerson, were photographed in positions matching photographs of the victims. The photographs of the skulls were then enlarged to life size and outline drawings of the pictures were successfully compared. Figure 4 shows the results. Figure 4-a shows one of the victim's skulls superimposed on an outline drawing of a photograph of Isabella Ruxton. The skull is not a good match. Figure 4-b shows the other victim's skull superimposed on the same outline drawing. The skull is a good match, and was in fact proven by other means to be that of Isabella Ruxton. a) Figure 4: Ruxton case line drawings Some problems with superimposition are 10 b) [source: 34, pp. 426-427] • determining the enlargement of the photographs of individual and skull (reference objects are needed) • positioning the skull to match the orientation of the photograph The availability of large data banks of mugshots, or orthodontic photographs, showing individuals in standardized positions, will speed up the identification process. Regular portrait or studio photographs are often taken from the most flattering angle, which is often not the optimal angle for superimposition. The advent of video cameras and mixing and editing apparatus also helped alleviate these problems. A video-animation compositor [26] is used to simultaneously project images of the skull and photograph onto a screen. The compositor adjusts the intensities of both images so that the photograph and the skull over which it is to be superimposed are both visible. Sizing is accomplished through zooming instead of multiple photographic enlargements or reductions. Orientation correction is much simpler. One person repositions the skull on its mounting apparatus based on feedback received from a second person observing the combined images on the monitor. As well, the results can be more easily recorded, for replay in courtrooms. Any point on the bony surface can be projected to the soft tissue surface using a model for soft tissue thickness. Errors may still be introduced if • important morphological points are not precisely associated with the corresponding areas of the head in the photograph • rotation and tilting of the head is not properly accounted for Iscan [34] has used video superimposition in several court cases since 1980. Webster and Murray [51], et al, have successfully identified several crime victims. They compared and superimposed 11 images of the skull with pictures of the victims showing dentition. Care was taken to match the dentition of the skull to that in the photographs. Computers also aid in the process by allowing digitization of images and better quantification of differences between images. However, superimposition is only useful if photographs of the deceased are readily obtainable. The technique is most useful if the identity of the victim is suspected to be that of a particular person. It can also be used to quickly eliminate possible identity matches. 2.2.2 Craniofacial Reconstruction The first facial reconstruction was attempted by His in 1895. It was performed in order to represent the appearance of early human beings and historical figures. His correctly identified the skull of Johann Sebastian Bach [26][34]. He carefully examined the skeleton belonging to the skull to establish age, sex, and stature, then modeled a bust on a plaster cast of the skull. The bust was then compared with known portraits and busts of Bach. His's tissue measurements were obtained by pushing a thin, sharp needle, equipped with a small piece of rubber, into the flesh of cadavers at right angles to the bone, until the needle struck bone. The piece of rubber moved upwards along the needle as penetration became deeper. The tissue thickness was recorded in millimetres as the distance from the point of the needle to the rubber piece. Gerasimov was one of the first to use reconstruction to scientifically ascertain the appearance individuals in extinct populations. The application to forensics is due to Krogman, who set down a step-by-step method for facial reconstruction in 1962. This method, expanded upon by Krogman and Iscan in 1986, is now standard in the field [28][34]. To begin reconstructing the face, the forensic artist must first determine the race and sex of the 12 subject. Then, the overall shape of the face is ascertained from skull measurements and proportions between facial features. Next, the position of facial features such as the eyes, nose, ears, and lips are located [11]. The structure of the face is then determined by matching craniofacial landmarks (on the skull) with their corresponding cephalometric landmarks (on the surface of the soft tissue). This task is the most difficult, because cephalometric points are occasionally not normal to their craniofacial points [23], which means that care must be taken when placing markers on the skull during clay reconstruction, to ensure they are properly angled. Blocks of clay or dowels made of pieces of cut eraser are used as the markers. The markers are then connected with strips of clay, the surface built up, and subsequently the features modeled in. Hair can be added based upon samples from the corpse or a best guess given the race of the deceased. Other distinguishing articles, such as jewelry, can be added if they exist in the peripheral evidence. Some forensic anthropologists create two-dimensional drawings from the skull, as opposed to complete sculptural reconstructions. This method is simple and inexpensive. Life sized pictures of the skull are taken from lateral and frontal views, and tracings are done over the photographs. However, full use of the tissue thickness data is often difficult, especially for the frontal view, due to foreshortening. Various methods have been developed to counteract this problem. Taylor [49] places dowels on the skull before the photographs are taken, thus using the camera to appropriately foreshorten the tissue thickness data. The frontal and lateral drawings are worked on simultaneously, to help merge new information obtained from one drawing into the other. Having the actual skull on the drawing table for reference is also helpful. 13 Figure 5: Three-dimensional Reconstruction 14 [source: 34, p. 444] Figure 6: Two-dimensional Reconstruction [Source: Cam Pye, Royal Canadian Mounted Police] George [22] used craniographs (high contrast X-ray skull films) to generate lateral profiles of individuals, artistically enhanced to produce more life-like drawings of individuals. The technique was validated by a study of 54 lateral craniographs of orthodontic patients. Tissue depth measurements were obtained from the craniographs by tracing the skull and soft tissue outlines on ruled graph paper, and locating the appropriate cranial and cephalometric landmarks. Average measurements were then computed, for males and females. The X-ray tracing of the skull outline was then redrawn on a separate sheet of paper, minus the soft tissue outline. The average tissue measurements were then used to draw an average soft tissue profile over the skull profile. This reconstructed profile was then compared to the actual profile in each case. The method was developed in an effort to standardize the way reconstruction is done, since different forensic artists often produce different individual likenesses. Figure 7 shows a lateral craniograph reconstruction. The skull profile obtained from the craniograph is shown as the 15 interior solid line. The dotted line is the actual X-ray tracing of the individual. The superimposed solid line is the outline reconstruction created from the average profile measurements. Figure 7: Lateral craniograph reconstruction [lource: s< 22] Problems in facial reconstruction arise because of inconsistencies in tissue thickness data due to the lack of extensive studies and the techniques used to conduct them. Early studies of tissue thickness were done on cadavers, which produce different results from measurements taken from living subjects, since tissues sag due to both the prone position of the cadaver and its decay. X ray analysis was then done on the skulls of living subjects, but due to health concerns, this is not a very good method for studying large populations. Recently, ultrasound has been used to determine tissue depths, and this method shows promise due to its non-invasiveness and the portability of the equipment [35]. Facial reconstruction offers at best only an approximation of the individual's appearance. Often 16 this is enough to generate leads that eventually result in positive identification of the subject. Due to its very nature, facial reconstruction should not be considered as a means of positive identification, but only as an aid in identification. While sometimes criticized as too timeconsuming and unstandardized, facial reconstruction has led to positive identification of deceased individuals in 50% of the cases in which it has been used. 2.3 The Way Ahead While technology has allowed great advances in the ability to identify humans from their skeletal remains, most techniques currently in use provide only two-dimensional analysis facilities, or are extremely time-consuming. Computers have to date been used effectively in superimposition methods, but as yet, there is no three-dimensional method in place for reconstruction, aside from the manual approach developed by Krogman. It would be beneficial to have a reconstruction technique that would increase the identification success rate, while simultaneously producing timesaving benefits over current two- and threedimensional methods. One way to raise the success rate would be to produce several different possible representations of an individual, allowing for the fact that he or she might have been slim or obese, or might have had a slightly different nose or lip shape than the artist's best single guess. Due to the time-consuming nature of Krogman's three-dimensional sculpting technique, it is difficult to generate different likenesses of an individual. For each new facial estimate, the artist must obtain a new cast of the skull, cut dowels of the appropriate length and place them on the cast, then recreate the facial features. The technology is now available to perform three-dimensional analysis quickly and costeffectively. This thesis presents the foundation behind a software package that performs facial 17 reconstruction. The premise is to closely simulate the process already known to the artist, to minimize the amount of training needed. The prototype application developed is described as follows. A three-dimensional digitized polygonal model of the skull is first obtained by laser scanning or medical imaging techniques such as CAT scans or MRI. Virtual dowels are then placed and oriented by the artist on this skull model. A generic surface model of a head is subsequently generated about the scan. This surface model is then fit to the virtual dowels laid out by the artist so that it smoothly and evenly interpolates them. The primary work accomplished in this thesis is the development and evaluation of a fast and efficient algorithm for the interpolation of sparse data. Considerable timesavings over conventional reconstruction methods are obtained through the ability to interactively update the lengths of all the dowels, based on such parameters as gender, race and body fat content, once the initial manual work of placing the dowels is done. Variations in tissue depth due to these parameters are stored in data files. To create a new facial estimate from different parameters, the correct data file is read by the software, which automatically updates the dowel lengths. The software then quickly generates each new facial base shape by interpolating the new dowel information. Detailed facial features such as the nose, lips and eyes are initially just rough estimates. The artist then has the ability to modify these features by directly editing the resulting surface model. In the prototype application, this editing is a completely manual interactive process. The artist must directly manipulate the surface model. An improved application would make use of sliders to control the basic facial shape parameters, race, age, sex and body-fat content. The application would supply a variety of stock shapes for facial details to be placed at the correct facial locations. For example, nose shape types could be provided for straight noses or roman noses, and sliders could be used to control nose length and width. Fine-tuning would then be done through interactive editing. With the ability to generate 18 varying individual likenesses easily and efficiently, it is hoped that the success rate in engendering leads to positively identify individuals can be increased to above 50%. r 19 Chapter 3 Parametric Curves and Surfaces 3.1 Overview An effective facial reconstruction tool requires a surface representation which lends itself to fitting and interpolation, and which is also well suited to interactive editing. The objective is to closely follow the artist's approach of roughing in a basic facial shape, then adding in the details of facial features later. Hierarchical or multi-resolution B-spline surfaces meet all these requirements. The following sections will give a brief overview of parametric curves and surfaces, in order to introduce B-spline curves and surfaces and their hierarchical representations. 3.2 Parametric Representation Curves and surfaces can be modeled in several different manners. The explicit form expresses y and z as an explicit function of x, for example y = f(x) and z = g(x) . Limitations of this approach include not being able to obtain multiple values of y for a single x, which may be desirable in some cases, the lack of rotational invariance, and the inability to properly represent vertical tangents, due to infinite slopes. Figure 8 shows a parametric curve in x and y as a function of an arbitrary parameter t. Since surfaces are generally expressed as functions of the parameters u and v, the notation u will be used in the following sections to denote the parameter values for curves. The parametric form of a curve expresses each coordinate as a function of another parameter, say u , such that x = x(u), y = y{u) and z = z{u) . Curves can then be approximated by piecewise polynomials. Cubic polynomials are the most common representations, as they offer a good tradeoff between 20 flexibility and control. Each curve segment Q(u) = [x(u) y(u) z(u)J is written as x(u) = a u +b u + c u + d , 3 x 2 x x x y(u) = a u + b u +c u + d , 3 2 y y y y z(u) = a ii +b u +c u + d , z z z 0<M<1 z Equation 1 which may be rewritten as Q(u) = C-U Equation 2 where C= a b y c y y y d_ d z Equation 3 and r 3 = \u 2 It U ir Equation 4 Cubic curve segments can be joined together to form more complex curves. The join points between curve segments, and the initial and final points on the curve are called knots. The parameter value at each knot is known as a knot value. Continuity of the overall curve at the join point can be defined in terms of geometric (G ) or parametric ( C ) continuity. C (nth parametric continuity) implies that the direction and magnitude of the nth derivative of the curve are equal at join points. Geometric continuity implies that the directions of the curve derivatives at the knots are equal, but that their magnitudes are not necessarily equal. 21 Figure 8: Example of a parametric curve, (x(t), y(t)) [Source: 13, p. 330] In general, the definition of a curve segment Q as stated in Equation 2 can be rewritten as Q(u) = G-M-U Equation 5 where G is the 3 x 4 geometry matrix and M is, for cubics, a 4 X 4 basis matrix. The geometry matrix describes the constraints that define the curve segment. These constraints are usually endpoints, control points, or tangent vectors, depending on the type of curve, and are constants. When the basis matrix is multiplied by the polynomial terms, the blending functions are obtained, such that B=MU Equation 6 This implies that each point on a curve segment is a weighted sum of the constant elements of the geometry matrix, and that those weights are the blending functions. Specific basis matrices 22 depend on the type of curve defined. Most curves will be defined by some set of control points and other constraints, the control points delimiting a control graph, or polyline, about the curve. Good properties of basis functions for curve and surface representation include [19] • Convex hull - the curve is contained entirely within the set of control points which define it • Variation diminution - the curve is smoother than the polyline defined by its control vertices • Local control - moving a control vertex affects the curve only locally • Specified continuity between segments • Independence from coordinate systems, or invariance under affine transformations Curves can be generalized to surfaces quite easily, by adding a second parameter, v, such that Q(u,v) = [x(u,v) y(u,v) z(u,v)J = U -M -G-M-V T 0<w,v<l T Equation 7 where G= <?00 #01 £02 803 <?10 8n 8n 8n £20 821 822 823 <?30 #31 8i2 833 Equation 8 is the geometry matrix for a parametric bicubic surface. Equation 7 and Equation 8 are usually written separately for each of the JC, y and z components. For a fixed value of u , a curve is generated in v. By varying u , a family of curves is generated, creating a surface. The elements 23 of the geometry matrix in Equation 8 are the corresponding coordinate components of the surface's control points. The tensor product notation for a surface is derived as follows. Let 2( ) = ]T/>fl>) M 1=0 Equation 9 be a curve expressed as a function of basis functions B and control points P . This curve can i t sweep out a surface by moving it through space and possibly deforming it. The sweep of the curve is described by allowing each P to follow a curve P (v), which in turn is defined by basis ; t functions as m ;=0 Equation 10 The resulting tensor product surface is given by n n m Q{u,v) = J P (v)B. (u) = ^J P B (u)B j i j i j (v) i=0 j=0 /=0 3.3 ij Equation 11 B-Spline Curves and Surfaces The term spline comes from drafting, where splines are long metal strips that are pulled in any direction, using weighted control handles called ducks. They were used to design curved surfaces, such as those found in boats and planes. Unless severely stressed, they had C 2 continuity. Natural cubic splines pass through their control points, and have C continuity, but 2 require extensive computation to calculate their coefficients, and do not allow local control over 24 the curve, in that moving one control point affects the whole curve. B-splines are splines built up from several curve segments. The 'B' stands for basis, because the splines are weighted sums of polynomial basis functions. They do not necessarily interpolate their control points. The polynomial coefficients are defined by only a few control points, and moving a single point affects a limited portion of the curve, thus giving local control over the curve. 3.3.1 Uniform Non-rational A B-spline [2] [9] [13] is defined by a set of control vertices, V ,..., V . For a cubic B-spline, m 0 m must be greater than 3. The resulting curve has m — 2 segments, Q ,..., Q . Each segment Q is 3 m t defined over the parameter values M, < u < u , 3 < i < m . If i is greater than 4, more than one M segment is defined, and the parameter value at each join point, as well as at the start and end points of the curve, is known as a knot, for a total of m — 1 knots. A uniform B-spline has its knots spaced evenly in parameter space. The term non-rational means that the spline is not defined as a ratio of polynomials [9] [13]. Figure 9 shows a B-spline curve with one curve segment, whereas Figure 10 shows a B-spline curve with 6 segments. The control graph is shown as the straight line segments between control points. Knots are shown as points on the curve. 25 Figure 9 B-spline curve with one segment Figure 10 B-spline curve with 6 segments For a cubic B-spline, each segment of the curve is defined by 4 control vertices, such that the geometry matrix for segment i is G,=\V M V,_ V,_, V , l 2 3</<m Equation 12 This property offers local control, since only a part of the overall curve moves when one control vertex is displaced. A single control vertex can affect up to 4 curve segments in a uniform cubic B-spline. 26 The B-spline basis matrix is -1 3 -3 1 3 -6 0 4 -3 3 3 1 1 0 0 0 Equation 13 0.9 0.8 - u Figure 11: B-spline blending functions This basis matrix is defined such that each basis function is defined over four successive knot intervals. The portion of the basis function defined over each interval is known as a basis segment, for a total of four basis segments, b_ , b_ , b_ , and b_ , per basis function 0 x 2 3 Each basis segment in turn is defined by a cubic polynomial given by 4 polynomial coefficients. This results in a total of 16 polynomial coefficients to be determined in order to define a basis function. As well, C°, C , and C continuity between adjacent basis functions is required at each 1 2 knot. The final assumption is the existence of a normalizing condition such that at their initial points, the basis segments sum to 1. This results in the set of equations 27 MO) MO) MO) MO) =0 ^(0) = 0 tf?(0) = 0 = b_ o(l) Mo) = MD Mo) =MD Mo) = M D Mo) = tf?(D = tf?(D = MD ,(D (D = b_ = b_ 2 0 = b_ (1) 0= M D 3 0 = &*>(!) b_ (0) + b_ (0) + b_ (0) + b_ (0) = 1 0 t 2 3 Equation 14 Solving for the segment polynomial coefficients results in b (w) = —u ~° 6 3 n fc_,( ) =-(1 + 3M + 3M -3M ) 6 2 3 M fc_ ( )=i(4-6w +3w ) 6 1 , , b_ (u) — — (1-3M + 3M —U) 6 2 2 3 M 3 Equation 15 The B-spline blending functions are each shifted copies of the B-spline basis function, are obtained from M • U , are positive and sum to 1. The blending functions are shown in Figure 11, whereas the basis function is shown in Figure 12. Figure 12: B-spline basis function with basis segments shown 28 If control points are replicated, the curve can be forced to interpolate specific points. This is intuitively evident, since if a control point is duplicated, the curve more closely approximates its convex hull, due to the double weighting. Tripling a control point forces the curve to pass through that point, and creates a straight line for that segment. Figure 13 demonstrates this effect. In Figure 13-a, all control points have multiplicity 1. In Figure 13-b, the central control point has multiplicity 2, and in Figure 13-c the central control point has multiplicity 3. a) b) c) Figure 13 Effect of replicating control points 29 3.3.2 B-spline Surfaces A B-spline surface patch is given by a grid of control vertices defining a control graph about the surface patch. Each point on the surface is a weighted average of the control vertices given by i=0 _/=0 Equation 16 or alternatively, for the /,/ patch Q (u,v) = [u u 3 u 2 iJ l]-M-V.j-M'' v V 1 Equation 17 The Bjj are the blending functions. In the uniform case, matrix M is as in Equation 13. The order of the splines is given by k and /. V is the matrix of control points for a surface with mXn control points v 00 V= y ... v 0n v V ... V mO mn Equation 18 The control vertices for the /,/ patch are V r ... V i-k+l, y ... v V V i-k+\,l i . j - M V 30 i.j Equation 19 3.4 Hierarchical Representations When modeling objects using parametric surfaces, it is often necessary to increase the number of patches to obtain a given shape. The number of patches on a parametric surface is increased by the insertion of additional knots. This process is known as refinement or subdivision. Refinement allows manipulation of smaller details of the surface. This is of particular interest when modeling objects such as faces, where greater levels of detail are desired in areas such as the eyes, nose, mouth and ears. One drawback to the parametric surfaces described above is that refinement often introduces or changes control points in areas far outside the region of interest: refinement is not as local as could be desired. Entire rows or columns must be refined to obtain the required detail in only a small area. This creates a large overhead in memory due to the need to store unnecessary control points. As well, editing the surface becomes more difficult as the complexity is increased. : This problem can be solved through the use of hierarchical surface representations, as discussed below. 3.4.1 Wavelets A hierarchical curve representation has been proposed by Finkelstein and Salesin [12], using wavelets. A set of m control points V" can be viewed as a discrete signal expressed as a column vector with m samples. It is desired to obtain a lower resolution version of V, V"~ , which has fewer l samples, m . This can be done by filtering and downsampling, and in matrix form becomes yn-\ Qr>y>> = Equation 20 31 G" is an m'xm matrix. The detail lost by going from level n to level n — 1 can be recaptured in a separate signal D ~ , such that n l n-l nyn D =H Equation 21 H" is an ( m - m ' ) X m matrix. The matrices G" and H" are known as analysis filters. Going from a higher resolution signal to one of less detail is known as decomposition. If the analysis filters are chosen correctly, it is possible to perform reconstruction on the less detailed signal, using a corresponding pair of synthesis filters, R" and S", such that V" =R V' n +S D"- i n 1 Equation 22 Each lower resolution signal can in turn be decomposed yet again into yet another less detailed signal, creating a hierarchy of signals. This hierarchy of lower level signals and their corresponding details, V°, D° ... ,V", D", is known as a filter bank. Because the original signal V can be recovered from the sequence of lower level signals and details, the sequence can be viewed as a wavelet transform of the original. The analysis and synthesis filters are found in the following way. Given that V" represents the control points for a B-spline curve segment, the function representing that segment is Q (u) = n B (u)V n Equation 23 B" (u) is the row matrix of basis functions for the curve. These basis functions are refinable for all j in [l,n] such that each coarser level basis can be expressed as a linear combination of more detailed bases. This implies that there exists a matrix that satisfies the relationship 32 Equation 24 This refinement matrix is also the synthesis matrix of Equation 22. Each basis B spans some linear space L . Each of these linear spaces is a subset of the linear 1 J space at the next finer resolution level. To go from linear space V to Z / , an orthogonal +1 complement space M', with its own basis functions * F , can be defined if an appropriate inner ; product is chosen for the basis vectors B . The *¥ are known as wavelets, are themselves 1 J orthogonal to the B under the chosen inner product, and together with the B form a basis for 1 1 L\ j+ The synthesis filter S is found from J Equation 25 The analysis filters are found by concatenating the above matrix equations, to obtain square matrices, and inverting -i|»j/7-ij 7[ ;| 7j fiJ =B /? 5 B 1 H' Equation 26 Resulting in =[ \ Y Ri si Equation 27 33 This hierarchical curve representation allows several functions to be easily performed. In general, the wavelet transform filters can be built such that they are sparse, allowing fast calculation of the transforms. Similarly to hierarchical B-splines, introduced in the next section, it is quite common for a large number of the entries in the wavelet transform to be negligible, allowing significant compression of the signal to be obtained by storing only the larger valued wavelet coefficients. As well, when used for the specific application of hierarchical surface representation, wavelets allow curves to be easily smoothed by using decomposed versions. The overall shape of a curve or surface can be modified without affecting its details by changing control points at lower resolution levels. The details can also be modified without affecting the overall sweep. The disadvantage of using wavelets to represent hierarchical surfaces stems from the fact that unlike the B-spline basis, the wavelet coefficients can be negative. This can result in a ringing effect when modeling and editing surfaces, where instead of a smooth surface, a wavy or oscillating surface is produced. The ringing effect can occur if the appropriate coefficients are not modified upon zeroing out of coefficients that had been previously changed. 3.4.2 Overlays Given the surface defined by Equation 17, it is possible to refine the basis functions, and thus the surface, such that they are linear combinations of smaller basis functions r « (v) = Xa (jR (v) s w JJ J Equation 28 where k and / represent the polynomial order of the basis functions. A larger number of control points is also generated, and the new refined surface definition is 34 fi(".v) = X2W iV (u)iV (v) ril r>t lii r s Equation 29 W r>i is related to V,- by ; Equation 30 Since the conversion from one matrix of control points to the other is done via the conversion of the basis functions, refinement is non-local, because of the large-scale replacement of V s by W's over an entire row or column. More W's are generated than are generally needed. Forsey and Bartels [16] use overlays to minimize the number of W vertices that must be stored, and offset referencing to simplify the editing process. Figure 14 shows a typical control graph for a B-spline surface. When a surface defined by V control vertices is refined such that its new representation is given by W, an exact copy of the surface is produced. If one of the W control vertices is moved, then the parts of the surface lying outside the [l + 2(k — l)]x [l + 2(1 — 1)] grid of control vertices surrounding the displaced vertex remain unchanged. This would imply that to faithfully reproduce the modified surface, only this restricted grid amid all the W vertices needs to be retained. This [l + 2(k — l)]x [l + 2(1 — 1)] grid of control vertices can be viewed as a separate surface. Only the central vertex in this grid can move if continuity with the surrounding surface is to be maintained, however, locally refined portions of the surface can now be edited. These grids are called overlays. Each overlay, in turn, can be refined into sub-overlays, producing areas of greater and greater refinement. The overlays are stored in a tree-stmcture, where each level of 35 refinement is another depth level in the tree. Figure 15 shows a surface that has been refined using overlays. It is possible to locally refine adjacent regions to produce refined areas of different shape and size. This is shown in Figure 16. Figure 14 A 16-patch surface described by 49 control vertices o o o o o o ©—e—9—e—o o o o o • »-»-•»•+-» • o <\> • f -f • o o o o o • (I • (> o—e—e- [Source: 14] © o vj o o o k +1] s o o o o Figure 15 A 16-patch surface with refinement and overlay control vertices 36 [Source: 14] Given that the coarser levels of the surface might require editing, it becomes necessary to relate the coordinates of overlay vertices to their parent levels somehow, so that any change at a lower level gets reflected in the overlay. This becomes easier if the overlay control vertices are defined in terms of a relative reference frame, instead of a fixed external coordinate system. Forsey and Bartels [16] introduce offset referencing to solve this problem. Each control vertex W,, at any ; level of refinement is written as W,,=R, +0,, y Equation 31 ::fi: -r -f- -JC- -j-T- 4-f-f-r-f 1 Figure 16 Local refinement of adjacent regions [Source: 14] The reference, R,-, is derived from the parent surface. Any changes at the current level of 7 refinement are stored in the offset, O . Each surface at a higher level of refinement becomes an i; offset from a reference surface. Changes at lower levels of refinement affect the reference portion of the overlays, whereas changes at the current level affect the offset. The orientation of the overlays follows any changes in orientation of the underlying surface, shown in Figure 17. 37 [u 3 u 2 u l]-M -W-M u • r v U-M„ -{R + 0 } - M - V = r T v {U-M u -R-Ml -V } + {U-M -0-M T T u -V } T v Equation 32 Original Orientation o o i o a) Offsets as vector addition o b) Desired offset behaviour Figure 17 Offset orientation [Source: 14] Figure 18 shows the control graph of a surface patch at various levels of refinement. The offsets at each level are zero, since the patch has not been edited. Figure 19 shows the control graph of the same patch after control points at level 3 have been displaced. Control points at lower levels remain unaffected by this displacement. However, if any points at lower levels were to be modified, the offsets at level 3 would be preserved. This is shown in Figure 20. Figure 20-a shows a rendered version of the surface in Figure 19. Figure 20-b shows the preservation of the surface details after the central control point at level 1 of the hierarchy is displaced. Judicious 38 use of the hierarchy allows details to be preserved even after modification of the coarser levels in the hierarchy. c) Refinement level 2 d) Refinement level 3 Figure 18 Control graphs of a surface patch at various refinement levels, with all offsets zero 39 Figure 19 Refinement level 3 after editing a) b) Figure 20 Offset preservation after underlying surface modification The hierarchical representation offers an efficient means of compressing a more detailed surface. Only areas of detail whose offsets differ from the original lower resolution surface are stored. Banded matrices are also inherent to the B-spline and H-spline formulation, due to their local control property. This allows more efficient computation of surface modifications. 3.5 Surface Representation Implemented The surface representation chosen for the craniofacial reconstruction software is based on the 40 hierarchical B-spline surface overlay method described in Section 3.4.1. B-splines were chosen due to their greater generality and simplicity of representation. The positive basis functions result in numerically stable, convex combinations. They are invariant under affine transformations, and are well suited to interactive editing. A software application, Dragon [14], already exists which makes use of the hierarchical overlay representation for B-spline surfaces. This package was designed for facial modeling and animation, and is easily adaptable to the craniofacial application. The package also has the ability to read in polygonal definition files, a standard format for data from scanned objects, in this case, scans of skulls. In order to upgrade this existing software to perform craniofacial reconstruction, it is necessary to develop an appropriate interpolation method for fitting surfaces to data points, and to subsequently integrate this technique into the application. Various surface fitting techniques, together with a new method developed for craniofacial reconstruction, will be discussed in the next chapter. 41 Chapter 4 Curve and Surface Fitting 4.1 Overview In order for the computer to generate a three-dimensional representation of the appearance of an individual's face based upon a scan of the skull, a generic B-spline surface will be placed about the scan, together with data points representing craniofacial landmarks. The generic surface will subsequently be placed automatically to interpolate the data points smoothly and evenly. Initially, it may be desirable to leave intact areas of detail such as the eyes, nose, and lips, while modifying their general position by fitting to lower surface resolution levels. The fitting method should have the following characteristics. It should be adaptable to any tensor-product, parametric spline surface defined in terms of control vertices and basis functions. This is useful in the event future implementations of the craniofacial reconstruction application use a parametric surface other than B-splines, since the current version is a prototype only. The method should provide local or global control over the locality and smoothness of the fit; local to leave regions far from certain data points unaffected by the interpolation, and global to change the overall shape of the surface with only a few points. It should handle data sets with finer levels of detail at different resolution levels, to simulate the artist's process of creating a base face shape with rough details which can be refined later. The technique should also provide a reasonable facial approximation with the fewest data points possible. While, as mentioned above, it is desirable to develop a method adaptable to any tensor product parametric spline surface, discussions and derivations below will mostly be specific to uniform cubic B-spline curves and uniform bicubic B-spline surfaces. While not completely general, the method presented is well suited to the intended application, due to its overall simplicity and 42 flexibility. 4.2 4.2.1 Related Work Constraint-Based Fitting Given a curve segment Q(u) defined in terms of basis functions and control points, if that curve is to be fitted to a data point d at a given parameter value u , then k k Q(u ) = ^V B (u ) k i i =d k k alii Equation 33 provides a single linear equation involving the control vertices V for the segment, since for the t given u , the basis functions become constants. If p data points are to be interpolated, a system k of linear equations is produced, such that Q(u ) = J^V B (u ) = d k i i k k k = l,...p alii Equation 34 In matrix notation, this becomes B(u )\ T k =D Equation 35 where B i s p X i, V is i X1 and D is p X1. Since the data points and control vertices are usually two- or three-dimensional points, Equation 34 is shorthand for three simultaneous systems with the same matrix of basis coefficients. If an existing curve is used, any interpolation of a data point can be viewed as a change to that curve, such that 43 B(u )A\ =AQ(u ) T T k k Equation 36 A Q is simply the vector of changes of position of the curve require to interpolate the data points For a given curve segment the problem of interpolating data points is often underdetermined. If the system is overdetermined, the problem is made underdetermined by refining the curve. An overdetermined system can produce contradictory constraints on the curve. Refinement therefore reduces each point's influence on any other constraint point. In general [18][48][17], the optimal solution obtained for these underdetermined systems is that which minimizes the combined movement of the control vertices involved, otherwise known as the minimum length solution. AV = B r R ( B B R ) AQ r Equation 37 Differential constraints are also defined and solved for similarly, since G ( / ) K ) = S ;- .-' K) V B ) alii Equation 38 The solution to Equation 37 is efficiently solved by precomputing the right inverse ( B B R ) _ 1 . It is also often unnecessary to include all of the segments' control vertices in the system of constraints. The vertex with maximum positional influence on the desired point of the curve should always be included, as well as one additional degree of freedom to reduce undesirable assymmetry in the case of unique solutions. For instance, if 2 constraints are specified, 3 control vertices should be included in the system. Given a tensor product surface patch, a point on that patch is defined by its control points and basis functions such that 44 G(M,V) = £ £ V , , B . ( M ) ^ ( V ) J 1 i=0 7=0 Equation 39 For specific values of u and v, the basis functions are constant, and the position of a point on the surface becomes a linear combination of the control vertices defining the given patch on the surface, such that m n 2K-v ) = £ £ v , , B , K ) B . ( v j s i=0 ; j=0 Equation 40 If the univariate basis functions are recombined into bivariate basis functions, the posititional change in the surface are re-expressed in matrix notation as B(u ,v )A\ =AQ(u ,v ) T k T k k k Equation 41 In this case A V is indexed as a vector, and not a matrix, and the system is solved similarly to Equation 37. Reformatting the equation in this manner allows partial derivatives to be constrained, by applying the appropriate values on the right-hand side. This allows specification of the tangent plane at the point to be interpolated. The method provides local control over the surface, as each calculation is done on a patch by patch basis [17] [18]. One of the difficulties encountered when satisfying positional constraints d is the choice of the k associated parameter value u . Altering the parameter value can radically change the shape of k the resulting curve, as different curve segments are then affected by the constraint. One common solution to choosing parameter values is uniform parametrization, in which the parameter values assigned to the d are evenly spaced. Uniform parametrization however, does not usually k produce the best results, since the data points themselves may not be evenly spaced, resulting in 45 stretching, shrinking or overcompensation effects. Arc-length parametrization sets the parametric distance between the data points as being proportional to the distance between the data points themselves. In this case it is assumed that the data points originate from some relatively smooth surface that is to be approximated. Since this surface is unknown, the actual arc-length cannot be precisely determined, and most often the Euclidean distance between the data points is used as the approximation of the arc-length. However, if an iterative approach is used [40], the parameter values can be re-chosen based upon the arc-length distance between points on previous approximations to the surface. 4.2.2 Finite Element Analysis Finite element analysis is a technique used to approximate some function (p in some region Q. bounded by a closed curve T ..It is often used to solve complex boundary value problems and systems of differential equations. If a function \f/ can be found which takes on the same values as (jJ on T , and if a set of independent trial functions {N ; m = 1 , 2 , 3 , M } is introduced m such that N | = 0 for all m , then function (p can be approximated by m r M (p = 0 = y/ + ^a N m m m=l Equation 42 The coefficients a are computed to obtain a good fit. The trial functions are often referred to as m shape or basis functions. In weighted residual methods of fitting, the trial functions are defined by a single expression valid throughout the whole domain Q.. The error or residual R is n defined by R =<p-Q Q Equation 43 46 This error is reduced by requiring that a certain number of integrals of the error equal zero over the region Q , or jW (<p-<p)dn = jW (R )dei = 0; a. l l n l = \,...,M a. Equation 44 Each W is an independent weighting function. If <p is replaced in Equation 44 by Equation 42, l then a set of simultaneous linear equations for the unknowns a m is produced, such that Ka = f Equation 45 where a = [a, ••• a] M K =\w,N da lm \<l,m<M m fx = [ Wicp-^dQ. \<1<M Equation 46 If a suitable function I// is chosen, together with appropriate weighting and trial functions, Equation 45 can then be solved for the unknown coefficients. Different choices of weighting functions lead to different weighted residual approximation methods. In the point collocation method, the weights are chosen to be W, =8(x- ) Xl Equation 47 where S(x — x,) is the Dirac delta function. This form of weighting results in the residual being zero at the chosen points x,. In the Galerkin method, the weights take on the value of the trial functions 47 W,=N, Equation 48 In this case, typically K Equation 49 This results in matrix K being symmetric, thus facilitating computation. If the region Q. is divided into subdomains or elements Q. , then the approximation <p is e constructed in a piecewise manner over each subdomain. The trial functions used are then also defined in a piecewise manner by using different expressions in each subdomain Q. . The e residual over the whole region is obtained by summing the contributions from each element Q. e as Equation 50 E is the total number of subdivisions and T is the portion of the boundary of Q which lies on e e r. If the elements are chosen with simple shapes and the trial function definitions are repeatable, then assembled regions of complex shapes are dealt with fairly easily. With the trial functions defined in a piecewise manner, their value is zero everywhere outside the element over which they are defined. This results in banded matrices in the final approximation equations. 48 The finite element method is simply illustrated by attempting to approximate a one-dimensional function. Let each shape function be obtained from a piecewise constant global shape function N , which has value unity on element m and is zero everywhere else. The one-dimensional m region Q. = [0, L ] is divided into elements by choosing a set of points {x ; / = 1,..., M }, with x t n x = 0 and x ^ = L . Each element is defined from x < x < x . The midpoints of each x M x e e+l element are known as nodes. Each node and element is numbered such that node m belongs to element m . If the Galerkin method of weighted residuals is chosen, then the weighted residual equations become 1 J N ,((p - q))dx = 0 0 Equation 51 If (p is given by <P = <P = Y,<P N m m m=l Equation 52 where (p is the value of cp at node m , then the elements of Equation 45 become m K =JN N dx lm l m 0 1 /, =j(pN,dx Equation 53 The global integrals in Equation 53 are evaluated by summing over the elements, such that 49 e=\ f,=if; Equation 54 This results in a diagonal system in Equation 45, since N,N m =0 I#m Equation 55 Weighted residuals and finite elements are also used to approximate systems of differential equations. The finite element method has been used to model skin surface for simulation of facial surgery [33]. The skin is modeled as a deformable surface mesh. Each vertex of the mesh belongs to a corresponding vertex on the skull surface. The stiffness of the skin is modeled using a spring mesh topology, with main springs connecting each skin vertex with its corresponding skull vertex, and strut springs connecting each skin vertex to the neighbours of its skull vertex. This deformable surface has some internal deformation energy E , such that def E def = j^a stretching + /J bending dQ. 'Pu a = Ct \ 2 ,p = (%22 1 P 22 P 33 Equation 56 The energy depends on the shape's natural resistance against bending and stretching, a and /? are the tensors defining the material properties. If f (u,v) are the external forces applied to a surface Q(u, v) whose first and second derivatives in the parametric directions are Q , Q , u Q , and Q , then the energy is redefined as uu m 50 v E = \a Ql n -wc Q Q n u + a Q? + (3 Q 2 v 22 U + 2(3, Q + P Q 2 UU 2 -HQdQ. 2 UV 22 n Equation 57 The surface Q is unknown and is approximated by finite element patches Q composed of p weighted sums of bases (p,, such that Q (u,v)^Y i Pi i a ( P 4 Equation 58 The bases are defined over a limited domain Q . The problem remains of solving for the p coefficients a,. These coefficients are viewed as the coordinates of the trial function in a functional space spanned by the bases (jO,. Equation 57 is collapsed and rewritten in matrix form as Ka = F Equation 59 where K is the system global stiffness matrix and F is the external load vector. Equation 59 is the standard finite element system of equations seen in Equation 45. The global stiffness matrix is constructed by assembling all the local stiffness matrices of each finite element. K is usually large but sparse. The facial surgery simulator was designed to obtain the shape of the face from an initial preprocessing step, which involves initializing the shape of the face from CT scans in which the soft tissue surfaces have been extracted via a segmentation step. The spring constants and optimized surface mesh are calculated from these scans during this preprocessing phase. The total calculation time for the global stiffness matrix was 17 minutes, and to solve the equation system of Equation 59, 11 minutes, on a SGI Indigo R4400, 200MHz processor, with 192 MB of 51 RAM. While producing a very good postoperative model of the head surface, the method requires prior knowledge of the original skin surface. As well, it is very computationally intensive, and overcomplex for the forensic application in question. 4.2.3 Direct Manipulation of a Single Data Point Consider a uniform cubic B-spline curve, Q(u) = (X(u),Y(u)) vertices Vo = (;c ,y ) through V =(x ,y ) 0 0 m m of m-2 segments, control and non-decreasing knot sequence m u ,...,u _ . 0 m 2 The B-spline blending functions for segment i where 3<i<m are B-[fi 0 B i B B] T 2 3 "-1 3 -3 f 3 -6 3 0 6 -3 0 3 0 {U — Uj ) 1 4 1 0 1 1 («-«,-) (u-Uj) 3 2 Equation 60 and each curve segment is given by Xj(u) = x _ B + *,_ Bi + x _ B Yi («) = yi_3B0 +_B t 3 0 2 yi 2 x i l 2 + XjB 3 + y,_,B + y B 2 t 3 Equation 61 Bartels and Beatty [1] propose a method for manipulating spline curves as follows. It is desired to move a given point on the curve, (x,y), with fixed value of u, to a new position (x',y'). Then x' = x + Ax y' = y + Ay Equation 62 In terms of the B-spline formulation, this can be written as 52 x + Ax = (x(_3 + Ax,_ )Z? + (x,_ + Ax,_ )B + (x,_! + Ax,-_] )B + (x,- + Ax,- )B3 0 2 L 2 2 I (y _ +Ay _ )B +(y _ +Ay _ )B +(y _ +Ay _ )B +(y +Ay )B y + Ay = i I 3 3 0 i I 2 2 l i l I L 2 i I 3 Equation 63 therefore Ax - AX^BQ + AXJ_ BI + Ax,_]fi + Ax,fi 2 Ay = A y , _ B + 3 0 2 \ + yi-\B2 B 3 + J,fi3 A A Equation 64 Equation 64 gives two equations in eight unknowns, Ax, and Ay,, which implies that multiple solutions exist. A simple solution would be to set Ax, = Ax and Ay, = Ay . This would satisfy Equation 64 since the basis function sum to 1. However, since all control points are moved by the same amount, a simple translation of the curve results. A solution which provides a change in shape to the curve can be found by noting that the total displacement of the point on the curve is a weighted sum of the displacements Ax, and Ay, of each of the control vertices. In turn, the displacement of each control vertex can be weighted and is chosen by Battels and Beatty [1] to be B: AX; - AX • W: -BQ Ax+ B^ + B + Bj B, 2 Ay i = Ay • w,- = Ay BQ + B\ + B 2 + B 3 Equation 65 This implies that the amount by which each control vertex is displaced is proportional to its parametric distance from, or influence on, the point to be moved. While this method could be considered constraint-based, it does not involve solving systems of linear equations. As well, it has the advantage of allowing control over the smoothness of the interpolation. A smoother interpolation is produced by allowing all vertices affecting a given segment to move, or a more localized interpolation by restricting the movement of a subset of the 53 control vertices. The effects of limiting the number of vertices that can move are shown in Figure 21. The points to be interpolated are shown as crosses, while control points are shown as dots. In Figure 21-a, 4 vertices are allowed to move. In Figure 21-b, only one vertex is displaced. The shape of the curve is narrower, the fit more localized, in Figure 21-b. a) b) Figure 21 Restricting control vertex movement 4.3 Fitting Method Chosen Optimally, the fitting method chosen for the forensic reconstruction technique should be fast, simple, and offer good control over the smoothness of the fit. It should be well adapted for use with data sets of varying levels of detail, to approximate the artist's technique of creating a base facial shape with rough details which are later refined. For this reason, the finite-element method was discarded, as it is too computationally intensive. A constraint-based approach could be used, as it does offer some local control over the smoothness and locality of the fit. It is also adaptable to data sets with varying levels of detail. 54 However, it may not necessarily be the optimal solution for use with hierarchical surface representations, as it adaptively subdivides a given surface in order to produce underdetermined systems of equations. Thus the possibility exists that areas of detail that might be desirable to preserve could be modified during the fit. Extra areas of detail are automatically added where they are not necessarily needed. Control over the resolution level at which the fit is performed is not available. Due to its flexibility and simplicity, Barrel and Beatty's method of direct manipulation could offer a good solution to all these problems. However, it needs to be extended to handle multiple data points, as well as surface representations instead of curves. These new augmentations are derived and explored in the following sections. 4.3.1 Interpolation of Multiple Data Points If the approach in Section 4.2.3 is to be used to perform forensic reconstruction, it must now be extended to interpolate multiple points. If points on the curve, (XJ , y ) , each with fixed value of 7 Uj, are to be moved to new positions in order to interpolate data points j = 0,...,n, for (x'j,y'j), each point on the curve to be displaced AXJ - A x , _ j 5 j +Ax _ jB j 3 Ayj=*yi-3,jB j 0 0 i 2 +Ay,_ +Ax _ jB j l 2 J i B 1 J l 2 +Ay,_ fi 1 J 2 J + Ax,-jB 3 j + Ay, B 3 J J Equation 66 and for a given point data point j the displacement of each control vertex is Ax,- • = AXJ 0J + l,j + 2,j + l B B B B B; Ay,- 0J + IJ + 2J + i B B B B Equation 67 55 The overall Ax, and Ay, of each control vertex for all j can be derived as a weighted sum of all its displacements ;'=o n 7=0 Equation 68 Let the actual displacement of the curve for each data point be Mj = Axi_ B 3 +Ax _ B 0j Ajy = A y , _ B 3 i 0 J 2 +Ax _ B j lj i +Ay _ B i 2 l + Ax,<B 2 3J .+ A y f l j + A y , B lj M 2 3 J Equation 69 To find the , •, the squared error between the desired displacement of point j and its actual displacement is minimized MIN(S = ]T (xj - xj) ) 2 wit Wjj 7=0 ds =0 y' = 0,. ..n Equation 70 and similarly for y . This gives the result 4=0 Equation 71 These weights are proportional to the control vertex's parametric distance from each point to be moved, which is intuitively satisfying. Thus, to interpolate multiple data points, the individual displacement of each control vertex is 56 calculated and stored for each separate data point. Once all points have been processed, the total displacement of each control vertex is calculated by a weighted sum of all its individual movements. The curve may be re-interpolated to reduce the error further still. Results of using this method are shown in Figure 22. The curve has 9 control vertices, and 4 data points are to be interpolated. Control vertices are not shown. Figure 22-a is the result after one iteration, Figure 22-b after several (n<10) iterations. a) b) Figure 22 Interpolation of multiple data points 4.3.2 Multi-resolution Interpolation Aside from limiting the number of control vertices that are allowed to move, the smoothness of interpolation can also be controlled by using a multi-resolution representation of the curve. Multi-resolution interpolation has been used by Harrison [20] to simulate the response of a piecewise linear multi-resolution surface to a deformation by using a multigrid solution to control the 57 smoothness versus the locality of the fit. The response of the surface to the deformation is computed at all levels of the hierarchy, and the total resulting deformation is computed by blending percentages of the deformations at user-specified resolution levels. A similar process is used here, but on piecewise cubic B-spline curves. If the curve is subdivided or refined before interpolation, a narrow fit results, as less curve segments are affected. The more refinements done before attempting a fit, the narrower the resulting fit. As well, given that point (Xj,y -) ; on the curve will interpolate point (x'j,y'j), the full interpolation need not be performed immediately. In other words, the displacement of the control vertices can be calculated based upon a fraction of the desired total displacement of the curve. Subsequent to the initial interpolation, the curve may then be subdivided using the Oslo algorithm [7]. After several successive fractional interpolations followed by refinements, the curve passes through the desired point. This iterative procedure allows better control over the locality of the interpolation. Choosing a larger fraction of the displacement at the initial stage produces a smoother fit. When a smaller fraction is used at each successive iteration, a more localized fit results. The curve has not been initially displaced as far, and so, after refinement of the spline, fewer segments of the curve are affected by the remaining displacement. Results are shown in Figure 23, Figure 24 and Figure 25. 58 Figure 23 Displacement fraction (DF) = 1.0. The ability to choose at which level of refinement the fit will be performed also allows areas of finer details to be preserved. This may be done by stopping the interpolation process beyond a given resolution level. This is of use for forensic reconstruction because details such as eyes, lips and nose can be created beforehand on the generic surface to be fit. When the fit is performed, these details will be properly positioned on the face, but their overall shape will not have been destroyed during the interpolation. 59 a) 1 Subdivision b) 2 Subdivisions c) 3 Subdivisions d) 4 Subdivisions Figure 24 Effects of subdivision before performing interpolation. D F = 1.0 60 a) DF = 0.2 b) DF = 0.4 c) DF = 0.6 d) DF = 0.8 Figure 25 Effect of initial displacement fraction. Interpolation at given DF, refinement and re-interpolation of remaining distance 4.3.3 Extension to Surfaces The techniques described in Sections 4.3.1 and 4.3.2 can be extended to bicubic B-spline surfaces quite easily. A bicubic B-spline surface Q(u,v) = (X(u,v),Y(u,v),Z(w,v)) 61 with control vertices Von - V = v • m0 mn ' Equation 72 is defined by X (u,v) iJ B V(x) Bl = u iJ B \(y) Bl Y (u,v) = iJ iJ u Equation 73 where B u and B v are the blending functions for u and v as defined in Section 3.3.2, and V , j is the sub-matrix of control vertices for the given parametric intervals. For each data point k the resulting displacement of each C V becomes B . .B u = A** A*/,;,* = A** • ij,k w 3 v 3 1=0 m=0 B Ay,-,;,* = Ay* • w ijk " , = Ay ——j-= k * *j B k — /=0 m=0 tei,j,k = Az* • w,j,* = Az k 3 3 /=0 m=0 Equation 74 As well, when accumulating the results of interpolation over all points k for control vertex (/, j ) , the weights given to each displacement are 62 allk Equation 75 Results of multiple data point interpolation of a bicubic B-spline patch are shown in Figure 26. The patch has 15 control vertices in the u direction and 7 in the v direction. No refinements were performed, and control vertices in a 4x4 area about each data point were allowed to move. Figure 26 B-Spline patch interpolating 5 data points 63 The locality of the interpolation for surfaces can still be controlled by the four methods described above: limiting the number of control vertices allowed to move, refining the surface, controlling the displacement fraction at each level of refinement, and beginning or halting interpolation at a given refinement level. Hierarchical refinement [16] allows better control over the fit because the refinements themselves are more localized. Interpolation can be done over refined patches of irregular shape. Care must be taken however, to avoid moving control vertices which could cause cracks in the surface. Results of refining and using different displacement factors are shown in Figure 27 and Figure 28. The refined areas are visible in the wireframe view as areas with a finer grid spacing. The data points to be interpolated are lozenges. a) Wireframe view b) Rendered view Figure 27 Hierarchical surface interpolation. DF = 1.0 64 a) Wireframe view b) Rendered view Figure 28 Hierarchical surface interpolation. DF = 0.4 4.3.4 Extension to Tangent Fitting The modified direct manipulation algorithm may also be extended to fit points on the surface to specific tangent planes. This is desirable since in forensic reconstruction, the orientation of the dowels provides some additional information about the curvature of the skull. The bicubic Bspline surface defined by Equation 72 and Equation 73 has partial derivatives with respect to u and v defined by dBU du dB u du dB u du V(y)„ B: 7 V(Z)„.B: Equation 76 and 65 dX., dB T —ii. = B,,V(x) —^ dv av / J 3^, dB T 8v H dv v Equation 77 where B„ and B are the blending functions for u and v as defined in Section 3.3.2, and V, v y is the sub-matrix of control vertices for the given parametric intervals. From these equations it is evident that to fit a B-spline surface to a tangent plane, it is only necessary to displace the control vertices appropriately. The partial derivatives of the surface are projected onto the desired tangent plane at data point k and normalized. The projected and normalized partials represent the required values of the partial derivatives needed for the surface to conform to the tangent plane at data point k. For each data point k , to fit to the partial derivative with respect to u, the resulting displacement of each CV becomes dB u k i.j.k 1,7,* k 3 du £Q 3 Vjt 1=0 m=0 a u dB u ;=0 m=0 a u dB u Az, =Az -w, =Az M t M t 3 3 ;=0 m=0 a u Equation 78 66 As well, when accumulating the results of interpolation to the partial with respect to u, over all points k for control vertex (i, j), the weights given to each displacement are dB {—^±-B u ) v W.' . = ^ dB, d u iJ k du ^ all k a " Vi u Equation 79 To complete the fit to a given tangent plane, the surface must be fit to the partial derivative with dB dB u respect to v, which is done by substituting B„ for v , and du for B v in Equation 78 and dv Equation 79. 4.4 Summary To generate a three-dimensional representation of the appearance of an individual's face based upon a scan of the skull, a generic B-spline surface may be placed about the scan. The generic surface will subsequently automatically be placed in order to smoothly and evenly interpolate data points representing tissue thickness. It may be desirable to leave intact areas of detail such as the eyes, nose, and lips, while modifying their general position by fitting to lower surface resolution levels. The fitting method chosen to do forensic reconstruction should be fast, simple, offer good control over the smoothness and locality of the fit, and be well adapted for use with data sets of varying levels of detail. The finite-element method, while producing a very good fit for complex shapes such as faces, is too computationally intensive. A constraint-based approach could be used, as it does offer some local control over the smoothness and locality of the fit. It is also well suited to data sets with 67 varying levels of detail. As it adaptively subdivides a given surface in order to produce underdetermined systems of equations, it may not necessarily be the optimal solution for use with hierarchical surface representations. Control over the resolution level at which the fit is performed is not available. Thus surface details that might be desirable to preserve could be modified during the fit. Bartel and Beatty's method of direct manipulation is simple and flexible, offering suitable control of fit locality. New additions to the technique were derived in Section 4.3, that allow fitting to multiple data points and surfaces, as well as fit control through restriction of control vertex movement, interpolation at multiple resolution levels and choice of displacement fraction. Fitting to tangent planes is also possible. The technique now offers a good solution to the problems of handling multi-resolution data sets, as well as better control over fit smoothness. It now remains to be seen if the technique is capable of producing a reasonable facial estimate. Chapter 5 will present results. 68 Chapter 5 Results 5.1 Test Overview The surface fitting method described in Section 4.3 was integrated into a hierarchical surface editing tool, Dragon, created by Forsey [14]. Preliminary tests were done in order to determine if the method was capable of generating a reasonable likeness of a face. At this stage, no attempt was made to identify a specific individual. A polygonal model of a skull, shown in Figure 29, was obtained from Viewpoint Data Labs, a provider of graphical models. The skull is that of a male, most likely Caucasoid. The original facial appearance of the individual from whom the model was obtained is unknown. A B-spline surface model of a head, created by an artist, was used as the generic surface to wrap about the skull (Figure 30). Figure 29 Polygonal model of skull 69 Figure 30 B-spline surface model of head The original surface model of the head was then modified prior to interpolation. Error could occur in the fit if areas of non-zero offset are not near any interpolation data points, implying that the patch control points are outside the region of interest and therefore not displaced. Non-zero offsets would therefore create inappropriate bulging or pinching in the surface. This effect is 70 illustrated on a simple cylindrical model with one dowel to be interpolated, in Figure 31, Figure 32, Figure 33, and Figure 34. On the head model, the offsets (Section 3.4.1) at refinement levels 1 and 2 of the generic head model were zeroed in order to minimize any interpolation error. Offsets at levels 3 and up were left intact, in an attempt to preserve the appearance of the nostrils and the eyes. The location of the eyes and nose can be determined from landmarks on the skull, but not their specific appearance, so the eyes and nose created by the artist were preserved. The resulting surface is shown in Figure 35. a) Wireframe view b) Rendered view Figure 31 Cylindrical surface with 3 refinement levels, all offsets zero, and polygon model with vertical dowel a) Wireframe view b) Rendered view Figure 32 Cylindrical surface fit to dowel 71 a) Wireframe view b) Rendered view Figure 33 Cylindrical surface model with 1 non-zero offset at level 2 72 Figure 35 Surface model of head with zero offsets at levels 1 and 2 In all test cases, the displacement fraction was 100% for each resolution level. Initial trials showed poor results at lower displacement fractions. Three control vertices were allowed to move to interpolate the data point, in an attempt to reduce asymetry effects. 73 5.2 Results Using Standard Landmarks The Dragon editor was modified to allow the user to place virtual dowels at any vertex on a polygonal model. A dowel can be interactively named and rotated, and its length updated either interactively or from a data file. Cam Pye, a professional forensic artist with the Royal Canadian Mounted Police was brought in to place dowels at the correct landmarks on the skull model. The 32 dowels used are those for which standard tissue thickness data are available [43](see Appendix 1). The resulting skull model is shown in Figure 36. Figure 36 Skull model with standard dowel set Each dowel was then associated with a u,v coordinate on the generic surface model of Figure 30. Tissue thickness values for a normal American Caucasoid male were used. The zero-offset surface was then required to interpolate the data points. The results appear in Figure 37. 74 Figure 37 Interpolation of standard dowel set It would appear, from examining Figure 37, that the standard 32 dowel set is insufficient to produce a good fit. Areas of the skull protrude through the B-spline surface, which is clearly not acceptable. The top and back of the skull are visible because no standard dowels exist in those areas. Other skull areas protrude because the software has no information on the curvature of the surface at each dowel. Thus, if the dowels are spaced too far apart, the surface will attempt to produce the smoothest interpolation between the two points, which will not necessarily follow the skull. When a facial reconstruction is done manually, by sculpting, the artist lays down strips of clay between each dowel, following the curvature of the skull. There are several solutions to this problem. The first is to place more dowels on the skull, thus providing the software with more information on the location and curvature of the skull surface. Tissue thickness measures at these new dowels are extrapolated from measures from nearby standard dowels. The second solution is to incorporate tangent information at each dowel into the 75 interpolation process itself. This would likely produce a better fit around areas of high curvature. The third solution is to simulate the artist's strips of clay by interpolating dowel thickness measures along isoparametric curves. Thus, following a curve of constant u or v, a sequence of parametric sample points could be generated. At each point, the tissue thickness measure could be estimated by interpolation of the measures of nearby dowels. The position of the skull surface is known from the skull model, therefore, the interpolation coordinates can be determined at each parametric sample point. 5.3 Results Using Standard and Extrapolated Landmarks Following the procedures discussed in Sections 5.1 and 5.2, extra dowels were added by the author at various locations on the skull (Figure 38). The dowel lengths at these locations were estimated from measures at nearby standard landmarks. The zero-offset surface was then fitted to the standard points as well as all the extrapolated points. Results are shown in Figure 39. Adding extra dowels results in a marked improvement in the appearance of the interpolated surface. The skull no longer intersects the surface. However, a pinching effect is noticeable below the cheek, around the eyebrows and around the upper lip/nose area. Some of this is likely due to the interpolator's attempt to pass through the many dowels of differing orientation in each area such as the Inferior Malar and Supra M , and Sub M and Mid Philtrum (see Appendix 1). 2 2 As well, a vertical ridge is faintly apparent on the forehead. This is caused by the lack of tangential information around the apex of the cranial curve. The interpolator overcompensates to either side of the midline on the forehead, producing a slight bulge on both sides of the midline that is manifested as the visible groove. 76 Figure 38 Skull with standard plus extrapolated dowels Adding dowels manually is rather time-consuming. Eighty-nine extra dowels were added, for a total of 121 dowels needed to produce a good fit. The locations of the extra dowels must be carefully chosen, as well as their corresponding u,v coordinates on the surface to be interpolated. If extrapolated dowels are to be used efficiently, some method of automatic placement on the skull needs to be implemented, as well as a method to automatically link each dowel with appropriate u,v coordinates on the surface. This last should be a fairly simple improvement, because cephalometric landmarks exist on the skin surface that correspond to the craniofacial landmarks. Incorrect placement of dowels or choice of associated parameter values can produce undesirable effects such as pinching or bulging. As well, the injudicious use of extra dowels can overconstrain the surface. This is especially true in areas such as the lips, at the finer resolution levels, as seen in Figure 40. It may be necessary either to stop interpolation at a lower surface resolution to avoid this problem, to be especially careful when selecting the parameter values associated with such dowels, or to avoid the use of too many dowels in certain areas. It should also be noted that the head model used might not be entirely suitable for the interpolation application, given that it was adapted from an artist's model used as the head of an animated television character. In fact, using a slightly different model, in which offsets at levels 3 and 4 near the brow ridge were zeroed, and offsets at level 2 around the lips were left intact, produces the results shown in Figure 41. These results also include slight modifications in the location of extra dowels and their associated parametric positions on the zero offset surface. 78 Figure 40 Overconstrained surface. Note undesirable bulging at lips Figure 41 Improved zero offset model with extrapolated dowels The zero offset model of Figure 35 would also not appear to be optimal for other reasons. When superimposed on the skull (Figure 42), it can be seen that refinement levels zero and one do not 79 initially conform well to the skull. This can be remedied by fixing the position of control vertices at level 2 and above, then performing a fit at levels 0 and 1, before zeroing any offsets at level 2. Figure 43 shows the effects of performing the fit at levels 0 and 1. The underlying shape of the model conforms much better to the skull. Figure 44 shows the improved level 2 zero offset model. Even before performing any fitting at level 2, the model appears much more face-like than that of Figure 35. Figure 45 shows the results of fitting using the improved model of Figure 44. As well, certain extrapolated dowels were adjusted, together with parameter values. Pinching in the cheek and lip area has been virtually eliminated. The fit conforms well to the jaw shape, and the lips are properly placed. This demonstrates that a reasonable facial approximation can be produced, from a relatively small amount of data (121 dowels). 80 81 b) Level 1 Figure 43 Improved model at levels 0 and 1 82 Figure 44 Improved model with zero offsets at level 2 Figure 45 Optimal fit using improved head model 5.4 Tangential Fit While Figure 45 is a good fit, there are still some improvements that can be made. The vertical indentation can be seen on the forehead in Figure 46 due to the fitting method improperly taking 83 into account the skull's curvature on the forehead. Overcompensation at certain control points produces a bulge to either side of the forehead dowels, which is manifested as the indentation between the bulging. If tangential information could be included in the fitting process, it might be possible to reduce this effect. Figure 46 View of bulging at forehead seen from below The method of performing a tangential fit described in Section 4.3.4 was used. The derivative at each point on the spline surface is calculated in the exact same way as the position of a point on the spline, but substituting the B-spline basis function derivatives for the basis functions themselves [2]. The dowel orientation was used as a normal to determine the desired tangent plane at each dowel. Figure 47 shows the results. There is reduced bulging in the forehead area, as can be seen in Figure 47-a. Although not very noticeable in these views, the frontal and lateral views also show slightly better conformity to tangent planes as compared to Figure 45. 84 a) View from below a) Frontal view b) Lateral view Figure 47 Tangential fit 5.5 Modification of Facial Features After Interpolation One of the goals in constructing a facial reconstruction software tool is to improve the 85 identification success rate through the easy generation of multiple plausible likenesses. A forensic artist will generally want to generate one or more facial base shapes, and then layer on more detailed facial features which can also be edited to produce different feature sets over a given base face. In the prototype application, modification of facial features is done through interactive editing of the facial surface. Control points at any level of the hierarchy are selected and moved using the mouse. Figure 48 shows how the nose shape can be significantly changed without affecting large portions of the underlying facial shape. Only four control vertices at level 1 of the hierarchy were moved to produce the new exaggerated nose shape. Figure 48 Modification of surface details through editing Since the areas of facial detail are layered on top of the lower resolution levels, it is possible to easily change the shapes of the facial features without affecting the underlying fit. 86 5.6 Artists' Feedback The prototype system was demonstrated to and used by two forensic artists from the Royal Canadian Mounted Police, Cam Pye and Peter Petersen. Their preliminary feedback indicates that for the system to be useful as a commercial craniofacial application, significant user interface changes are needed. However, their initial response to the facial shape obtained from the interpolation algorithm is very positive. Their opinion is that the overall facial base shape obtained is a reasonable approximation based on the skull shape. Certain facial features are anatomically incorrect, though. Specifically, the mouth covers too much area on the skull. Eye location and size must be improved, and ears, neck and shoulders added. These problems can be fixed by creating a more anatomically correct head model. The nose shape must be more closely based on skull characteristics such as the shape of the nasal bone, and size of the nasal spine and nasal opening. This is unrelated to the fitting algorithm. The artists would also like to be able to use stock shapes for various facial features, for example aquiline versus straight noses, and to place these stock shapes on the base facial shape. Sliders would ideally control the sizing parameters for these shapes, such as width, height and length. This functionality is easily added to the prototype by storing offset data for each given stock shape, since the areas of facial detail can be represented as areas of local refinement using the hierarchical B-spline overlays. The dowels should automatically be inserted normal to the skull surface. Currently, they must be manually oriented. Automatic dowel orientation would save considerable time even when placing extra dowels. As well, selection of the u, v attachment points of the dowels to the skin surface must also be automated. 87 The interpolation process itself must be less visible to the user. Currently, levels 0 and 1 of the hierarchy must be pre-fit to the skull, before performing any fitting at level 2. This pre-fitting needs to be automated, so that the artist need not bother adjusting low-level fitting parameters. Overall, the artists' comments indicate that although more automation is needed before a commercial forensic reconstruction software tool becomes useful to them, the current prototype generates a reasonable facial approximation and the interpolation algorithm can become a core component of the final version of the tool. 5.7 Summary Testing of the interpolation algorithm demonstrates that it holds significant promise for use in forensic reconstruction. Various different fits were performed, including fits to the standard forensic dowels and extrapolated dowels, and tangential fits. I- It was shown that the standard dowel set is insufficient to produce a good facial approximation. Extrapolated dowels yield better fits, yet are time-consuming to place. Automatic orientation of the dowels normal to the skull surface would immediately yield significant timesavings over the current manual orientation method. Some form of automatic placement of dowels, that is to say selection of the location of the interpolated dowels on the skull, needs to be developed in order for the system to be of benefit to a forensic artist. If automatic placement is not possible, some form of simulation of the artist's clay strips could be investigated, perhaps by interpolating tissue depths along isoparametric lines. Judicious choice of model, and parameter values significantly affect the resulting facial approximation. With an anatomically correct head model, it should be possible to automatically link dowels with u,v coordinates on the skin surface by using the appropriate cephalometric 88 landmarks corresponding to craniofacial landmarks. Immediately initializing all the generic model's offsets to zero yields poor results compared with first fitting lower refinement levels. A tangential fit is fairly simple to perform using essentially the same fitting algorithm as for position, and reduces bulging effects causes by lack of knowledge of the skull's curvature. Comments from actual forensic artists indicate that while more automation of the process is needed before a useful commercial system is produced, the current interpolation algorithm does result in a reasonable facial estimate, from a relatively small amount of tissue depth information. Overall, tests of the prototype system, while pointing out possible areas of improvement as mentioned above, indicate that the underlying fitting algorithm is appropriate for use in forensic reconstruction. 89 Chapter 6 Summary and Conclusions For the purposes of identification, it is sometimes necessary to try to determine a deceased individual's appearance. Analysis of the skull is the primary means of accomplishing this task, through reconstruction of facial features based on their known relation to skull features. While not a means of positive identification, the likenesses created are publicized in the hope of generating leads that would ultimately confirm the identity of the individual in question. Current methods of estimating the appearance of the individual from his or her skull are extremely time-consuming and costly. Because of this, often only a single facial estimate is produced. Because of the difficulty involved in determining body fat content prior to death, and of ascertaining the appearance of features such as the nose, lips and eyes, this single likeness is not necessarily the best estimate of a person's appearance. Current success rates for " identification resulting from facial reconstruction are on the order of 50%. Law enforcement agencies would benefit from a software application that can produce multiple three-dimensional facial reconstructions of an individual that more completely cover the range of likely appearances. In order to be useful to the artist, a software application that performs facial reconstruction would need to be easy to use, and must closely simulate the process already known to the artist. The idea is not to replace the artist, but to improve the process by which he or she creates a facial reconstruction, allowing quicker generation of multiple likenesses, with the ability to easily modify various facial features that cannot be determined from cranial parameters. The goal is to facilitate recognition by family, friends and acquaintances, based on the assumption that one of the multiple likenesses will most closely approximate the individual's actual appearance, thus improving the identification success rate. Chapter 2 discussed how estimation of an individual's appearance from the skull is currently 90 accomplished. Methods of superposition, as well as two- and three-dimensional facial reconstruction were introduced. The prototype application developed during this project uses a three-dimensional digitized polygonal model of the skull obtained by laser scanning or medical imaging techniques such as CAT scans or MRI. Virtual dowels are correctly placed and oriented by the artist on this skull model. A generic surface model of a head, created by an artist, is then positioned about the scan. This surface model is then automatically placed in order to smoothly and evenly interpolate the virtual dowels laid out by the artist. The premise is that once the initial manual work of placing the dowels is done, considerable timesavings may be obtained through the ability to interactively update the lengths of all the dowels, based on such parameters as gender, race and body fat content. The software quickly generates each new facial estimate once the dowel lengths have been changed. The surface model representing the face is editable after performing each estimate, so that the artist can alter features such as the nose, eyes and lips. Chapter 3 gave a brief overview of parametric curves and surfaces, with particular emphasis on hierarchical B-spline curves and surfaces. These lend themselves well to fitting and interpolation, and are also well suited to interactive editing. Hierarchical B-splines are also ideal for simulating the artist's process of creating a base facial shape with rough details that are subsequently given more accurate shape. Through the use of locally refined overlays, the facial details are layered on top of the coarser refinement levels, allowing the facial features to be easily changed without modifying the underlying facial shape. Since the generic facial model is fitted to virtual dowels, Chapter 4 introduced curve and surface interpolation methods. The fitting technique chosen must produce a good likeness of a face, but be simple and fast. Various methods of interpolation were discussed, among them finite-element 91 analysis, constraint-based approaches, and direct manipulation of points. With some new adaptations for multiple points and surface use, direct manipulation offers a good compromise between simplicity, speed and control of the fit. The extended direct manipulation technique has been integrated into a hierarchical B-spline editor. This software package is a prototype that eventually might be used to estimate the appearance of an individual from a 3D scan of the skull. The use of a hierarchical B-spline surface to represent the facial surface around the skull allows the user to easily modify finer details around areas of the face such as the eyes, nose and mouth, since they are layered on top of the underlying facial base shape. Although the work done was very exploratory, preliminary tests of the system are promising, since according to two professional forensic artists, a reasonable facial likeness was produced. The amount of data required to produce this likeness was minimal: 121 dowels representing tissue depth information. Future work will involve improving the technique by automating placement of extra dowels, or by interpolation of tissue thickness along isoparametric lines. These modifications should reduce the need for manual placement of extrapolated data points, as well as improve the appearance of the facial model, by reducing pinching and bulging effects. Once an anatomically correct head model is used, it should be possible to automatically link dowels to parametric coordinates on the skin surface through the use of the cephalometric landmarks that correspond to the craniofacial landmarks. How to further reduce the amount of data required should also be investigated. To become a better forensic tool, stock shapes for facial details must also be provided. More automation to the process in general and a better user interface are also needed. The system must be put through a series of double-blind tests, in which the skulls of known individuals will be scanned. A forensic artist would then use the system to generate a likeness of 92 each individual, without having seen an actual photograph of the individual. The results would then be compared against photographs of the deceased, and other likenesses generated by forensic artists. This would allow evaluation of the effectiveness of the technique in facial reconstruction. Subsequent testing would involve field trials of the software during actual criminal investigations. While the software is still in the prototype phase, initial results are encouraging and indicate the technique should be a useful tool in forensic investigation. As well, the medical community has shown interest in adapting the system for use in planning oral and plastic surgery procedures. In both the fields of forensics and medicine, the most widely used techniques for facial modeling are still two-dimensional, and thus limited in their presentation of visual information to the user, or, if three-dimensional, are very computationally intensive, such as finite element analysis. The interpolation technique developed in the preceding sections, while highly flexible, is simple and not as computationally intensive as finite-element analysis, and thus could easily be adapted for use on a high performance PC platform. It makes full use of all the three-dimensional information available from the skull, and eventually could be more efficient than sculpture in generating varying likenesses of individuals that take into account body type and facial details such as eyes, nose and lips. , 93 Bibliography 1. Barrels, Richard H. and Beatty, John C , "A Technique for the Direct Manipulation of Spline Curves", Graphics Interface, 1989 2. Battels, Richard H., Beatty, John C. and Barsky, Brian A., An Introduction to Splines for use in Computer Graphics and Geometric Modeling, Morgan Kaufmann Publishers, Inc., Los Altos, California, 1987 3. Birkhoff, G.D., Aesthetic Measure, Harvard University, Cambridge, Mass., 1933 4. Bbhm, W., Farin, G., and Kahmann, J., "A Survey of Curve and Surface Methods in CAGD", Computer Aided Geometric Design, Vol. 1 No. 1, July, 1984 5. Caldwell, P.C., "New Questions (And Some Answers) on the Facial Reproduction '•' Techniques", Forensic Osteology: Advances in the Identification of Human Remains, Reichs, K.J., Editor, Charles C. Thomas, Publisher, 1986 Chapter 13, pp. 229-255 6. Celniker, G. and Gossard, D., "Deformable Curve and Surface Finite-Elements for FreeForm Shape Design", Computer Graphics, Vol. 25, No. 4, July 1991 7. Cohen, E., Lyche, T., & Riesenfeld, R., "Discrete B-Splines and Subdivision Techniques in Computer-Aided Geometric Design and Computer Graphics", Computer Graphics and Image Processing, Vol. 14, 1980 8. Fagin, Gary, The Artist's Complete Guide to Facial Expressions, Watson-Guptill Publications, 1990 9. Farin, G., Curves and Surfaces for Computer Aided Geometric Design: A Practical 94 Guide, Academic Press, Inc., San Diego, 1988 10. Farkas, Leslie G., Anthropometry of the Head and Face, 2 Edition, Raven Press, New York, nd 1994 11. Fedosyutkin, Boris A. and Nainys, Jonas V., "The Relationship of Skull Morphology to Facial Features", Forensic Analysis of the Skull, Iscan, Mehmet Yasar and Helmer, Richard P., Editors, Wiley-Liss, Inc., 1993, Chapter 15, pp. 199-213 12. Finkelstein, Adam and Salesin, David H., "Multiresolution Curves", Computer Graphics Proceedings, A C M Annual Conference Series, SIGGRAPH 1994, Orlando, Florida, July 24- 29,1994 13. Foley, James D., van Dam, Andries, Feiner, Steven K., Hughes, John F., and Phillips, Richard L.,Introduction to Computer Graphics, Addison-Wesley Publishing, 1994 14. Forsey, David Robert, Motion Control and Surface Modeling of Articulated Figures in Computer Animation, Ph.D Thesis, Department of Computer Science, University of Waterloo, October, 1990 15. Forsey, David Robert, The Dragon Wing, http://www.cs.ubc.ca/nest/imager/contributions/forsey/dragon/top.html 16. Forsey, David Robert and Battels, Richard H. "Hierarchical B-Spline Refinement", Computer Graphics, Vol. 22, No. 4, August, 1988 17. Fowler, Barry, "Geometric Manipulation of Tensor Product Surfaces", Proceedings of the 1992 Symposium on Interactive 3D Graphics, March 1992 18. Fowler, Barry, and Battels, Richard, "Constraint-Based Curve Manipulation", IEEE 95 Computer Graphics & Applications, September, 1993 19. Fournier, Alain, "Parametric Curves and Surfaces", CPSC 535 Computer Graphics, Supplementary Notes, University of British Columbia, 1995 20. Harrison, Jason, A Kinematic Model for Collision Response, Masters Thesis, Department of Computer Science, University of British Columbia, April, 1994 21. Helman, Paul, Veroff, Robert, and Carrano, Frank M., Intermediate Problem Solving and Data Structures: Walls and Mirrors, Benjamin/Cummings Publishing Co., Redwood City, CA, 1991 22. George, Robert M., "The Lateral Craniographic Method of Facial Reconstruction", Journal of Forensic Sciences, Vol. 32, No.5, September 1987, pp.1305-1330 23. George, Robert M., "Facial Reconstruction Guidelines", Forensic Analysis of the Skull, Iscan, Mehmet Yasar and Helmer, Richard P., Editors, Wiley-Liss, Inc., 1993, Chapter 16, pp. 215-227 24. Gill, G.W., "Craniofacial Criteria in Forensic Race Identification", Forensic Osteology: Advances in the Identification of Human Remains, Reichs, K.J., Editor, Charles C. Thomas, Publisher, 1986, Chapter 8, pp. 143-159 25. Gilly, Daniel and Staff of O'Reilly and Associates, Inc., UNIX in a Nutshell, O'Reilly and Associates, Inc., Sebastopol, CA, 1992 26. Griiner, Oskar, "Identification of Skulls: A Historical Review and Practical Applications", Forensic Analysis of the Skull, Iscan, Mehmet Yasar and Helmer, Richard P., Editors, WileyLiss, Inc., New York, 1993, Chapter 3, pp. 29-45 96 27. Horn, B. K. P., Robot Vision, The MIT Press, Cambridge, Mass., 1986 28. Iscan, Mehmet Yasar, "Craniofacial Image Analysis and Reconstruction", Forensic Analysis of the Skull, Iscan, Mehmet Yasar and Helmer, Richard P., Editors, Wiley-Liss, Inc., 1993, Chapter 1, pp. 1-10 29. Iscan, Mehmet Yasar and Kennedy, Kenneth A.R., "Reconstruction of Life From the Skeleton: An Introduction", Reconstruction of Life From the Skeleton, Iscan, Mehmet Yasar and Kennedy, Kenneth A.R., Editors, Alan R. Liss, Inc. 1989, Chapter 1, pp. 1-10 30. Iscan, Mehmet Yasar and Loth, Susan R., "Osteological Manifestations of Age in the Adult", Reconstruction of Life From the Skeleton, Iscan, Mehmet Yasar and Kennedy, Kenneth A.R., Editors, Alan R. Liss, Inc., 1989, Chapter 3, pp. 23-40 31. Johnston, Francis E. and Zimmer, Louise O., "Assessment of Growth and Age in the Immature Skeleton", Reconstruction of Life From the Skeleton, Iscan, Mehmet Yasar and Kennedy, Kenneth A.R., Editors, Alan R. Liss, Inc., 1989, Chapter 2, pp. 11-21 32. Kernighan, Brian W. and Ritchie, Dennis M., The C Programming Language, Prentice Hall, 1988 33. Koch, R.M, Gross, M.H., Carls, F.R., von Buren, D.F., Fankhauser, G. and Parish, Y.I.H., "Simulating Facial Surgery Using Finite Element Models", Computer Graphics Proceedings, Annual Conference Series, 1996 34. Krogman, W.M., and Iscan, M.Y., The Human Skeleton in Forensic Medicine, Charles C. Thomas, Publisher, Springfield, Illinois, 1986 35. Lebedinskaya, G.V., Balueva, T.S., and Veselovskaya, E.V., "Principles of Facial 97 Reconstruction", Forensic Analysis of the Skull, Iscan, Mehmet Yasar and Helmer, Richard P., Editors, Wiley-Liss, Inc., 1993, Chapter 14, pp. 183-198 36. Leon, Louis and Millet, Francois, C Si Facile, Editions Eyrolles, Paris, France, 1987 37. Lott, N.J., and Pullin, D.I., "Method for fairing B-spline surfaces", Computer-Aided Design, Vol. 20, No. 10, December, 1988 38. Moreton, Henry P., and Sequin, Carlo H., "Functional Optimization for Fair Surface Design", Computer Graphics, Vol. 26, No. 2, July 1992 39. Nicholson, W. Keith, Elementary Linear Algebra with Applications, Prindle, Weber and Schmidt, Boston, Massachusetts, 1986 40. Plass, Michael, and Stone, Maureen, "Curve-Fitting with Piecewise Parametric Cubics", Computer Graphics, Vol. 17, No. 3, July 1983 41. Press, William H., Teukolsky, Saul A., Vetterling, William T., and Flannery, Brian P., Numerical Recipes in C, 2 Edition, Cambridge University Press, New York, 1992 nd 42. Rando, T., and Roulier, J.A., "Designing faired parametric surfaces", Computer-Aided Design, Vol. 23, No. 7, September 1991 43. Rhine, Stanley, Tissue Thickness Measures: American Caucasoids, American Blacks, Southwestern Indians, Physical Anthropology Laboratories, Maxwell Museum of Anthropology, University of New Mexico, 1982, 1983, 1984 44. Schildt, Herbert, C++: The Complete Reference, Osborne McGraw-Hill, Berkeley, CA, 1991 45. Snow, C.C., Gatliff, B.P., McWilliams, K.R., "Reconstruction of Facial Features from the 98 Skull: An Evaluation of its Usefulness in Forensic Anthropology", American Journal of Physical Anthropology, Vol. 33, 1970, pp.221-227 46. St. Hoyme, Lucile E. and Iscan, Mehmet Yasar, "Determination of Sex and Race: Accuracy and Assumptions", Reconstruction of Life From the Skeleton, Iscan, Mehmet Yasar and Kennedy, Kenneth A.R., Editors, Alan R. Liss, Inc., 1989, Chapter 5, pp. 53-93 47. Stewart, T.D., "The Points of Attachment of the Palpebral Ligaments: Their Use in Facial Reconstructions on the Skull", Journal of Forensic Sciences, Vol. 28, No. 4, 1983, pp. 858863 48. Strang, Gilbert, Linear Algebra and Its Applications, Second Edition, Academic Press, New York, 1980 49. Taylor, K.T., "Technique of Facial Reconstruction Drawing", Proceedings of International Symposium on the Forensic Aspects of Mass Disasters and Crime Scene Reconstruction, FBI Academy, Quantico, Virginia, June 23-29, 1990 50. Thomas, George B., and Finney, Ross L., Calculus and Analytic Geometry, Part II, 7 th Edition, Addison-Wesley Publishing Co., Reading, Mass., 1988 51. Webster, W.P., Murray, W.K., Brinkhous, W.B., and Hudson, P., "Identification of Human Remains Using Photographic Reconstruction", Forensic Osteology: Advances in the Identification of Human Remains, Reichs, K.J., Editor, Charles C. Thomas, Publisher, 1986, Chapter 14, pp. 256-289 52. Zienkiewicz, O.C., and Morgan, K., Finite Elements and Approximation, John Wiley & Sons, New York, 1983 99 Appendix 1: Standard Tissue Thickness Measures Source: Rhine, Stanley, Tissue Thickness Measures: American Caucasoids, American Blacks, Southwestern Indians, Physical Anthropology Laboratories, Maxwell Museum of Anthropology, University of New Mexico, 1982, 1983, 1984 Figure 49 Location of standard landmarks 100 Measurement No. Midline 1 Emaciated Normal Obese Supraglabella Male (3) 2.25 Female (3) 2.50 Male (37) 4.25 Female (19) 3.50 Male (8) 5.50 Female (3) 4.25 2 Glabella 2.50 4.00 5.25 4.75 7.50 7.50 3 Nasion 4.25 5.25 6.50 5.50 7.50 7.00 4 End of Nasals 2.50 2.25 3.00 2.75 3.50 4.25 5 Mid Philtrum 6.25 5.00 10.00 8.50 11.00 9.00 6 Upper Lip Margin 9.75 6.25 9.75 9.00 11.00 11.00 7 Lower Lip Margin 9.50 8.50 11.00 10.00 12.75 12.25 8 Chin-Lip Fold 8.75 9.25 10.75 9.50 12.25 13.75 9 Mental Eminence 7.00 8.50 11.25 10.00 14.00 14.25 10 Beneath Chin 4.50 3.75 7.25 5.75 10.75 9.00 Bilateral 11 Frontal Eminence 3.00 2.75 4.25 3.50 5.50 5.00 12 Supraorbital 6.25 5.25 8.25 7.00 10.25 10.00 13 Suborbital 2.75 4.00 5.75 6.00 8.25 8.50 14 Inferior Malar 8.50 7.00 13.25 12.75 15.25 14.00 15 Lateral Orbit 5.00 6.00 10.00 10.75 13.75 14.75 16 Zygomatic Arch, 3.00 3.50 7.25 7.50 11.75 13.00 midway 17 Supraglenoid 4.25 4.25 8.50 8.00 11.25 10.50 18 Gonion 4.50 5.00 11.50 12.00 17.50 17.50 19 Supra M 12.00 12.00 19.50 19.25 25.00 23.75 20 Occlusal Line 12.00 11.00 18.25 17.00 23.50 20.25 21 Sub M 10.00 9.50 16.00 15.50 19.75 18.75 2 2 Table 1 Tissue thickness measures, American Caucasoids (mm) 101 Measurement No. Midline 1 Emaciated Normal Obese Supraglabella Male (4) 4.00 Female (5) 5.00 Male (27) 5.00 Female (10) 4.50 Male (1) 5.00 Female (2) 3.50 2 Glabella 5.25 6.00 6.25 6.00 7.50 6.00 3 Nasion 5.25 5.25 6.00 5.25 5.25 4.75 4 End of Nasals 3.00 3.25 3.75 3.75 3.25 3.00 5 Mid Philtrum 11.75 10.00 12.25 11.25 11.75 12.00 6 Upper Lip Margin 12.50 12.00 14.25 12.50 12.50 15.25 7 Lower Lip Margin 13.75 12.25 15.50 15.00 15.50 12.00 8 Chin-Lip Fold 11.75 9.50 11.75 12.25 13.00 12.25 9 Mental Eminence 11.25 11.00 11.50 12.50 15.25 13.00 10 Beneath Chin 8.00 6.50 8.25 8.00 9.50 8.50 Bilateral - 11 Frontal Eminence 3.75 3.25 5.00 4.00 5.50 5.00 12 Supraorbital 7.75 7.25 8.50 8.00 11.75 8.50 13 Suborbital 5.75 6.50 7.75 8.25 9.25 9.00 14 Inferior Malar 14.00 14.50 16.50 16.75 17.50 18.75 15 Lateral Orbit 10.50 12.00 13.25 13.00 20.00 12.75 16 Zygomatic Arch, 6.75 8.00 8.25 9.50 13.75 9.25 midway 17 Supraglenoid 9.50 9.75 11.00 11.50 17.50 17.25 18 Gonion 11.50 11.00 13.00 13.50 24.00 17.50 19 Supra M 19.00 20.50 22.00 20.25 24.00 23.50 20 Occlusal Line 16.75 17.75 19.00 19.25 30.00 20.00 21 Sub M 13.50 14.25 16.50 17.00 23.50 20.00 2 2 Table 2 Tissue thickness measures, American Blacks (mm) 102 Measurement No. Midline 1 Emaciated Normal Obese Supraglabella Male (4) 5.75 Female (1) 4.00 Male (9) 5.00 Female (2) 4.50 Male (5) 4.50 Female (3) 4.25 2 Glabella 5.75 4.75 5.75 4.50 6.00 4.50 3 Nasion 5.75 6.50 6.86 7.00 6.50 5.00 4 End of Nasals 2.75 2.50 3.50 2.50 3.25 3.25 5 Mid Philtrum 7.50 10.00 9.75 10.00 9.25 8.51 6 Upper Lip Margin 8.25 9.50 9.75 11.00 9.25 10.00 7 Lower Lip Margin 9.25 12.00 11.00 12.25 8.75 11.25 8 Chin-Lip Fold 8.50 9.00 11.50 10.00 9.75 11.00 9 Mental Eminence 8.00 11.00 12.00 13.00 12.50 13.25 10 Beneath Chin 5.25 8.00 8.00 8.00 8.00 7.75 Bilateral • 11 Frontal Eminence 4.75 4.75 i 4.25 4.00 4.50 4.20 12 Supraorbital 6.75 5.00 9.00 8.50 8.50 8.25 13 Suborbital 3.75 3.25 7.50 6.25 7.75 6.75 14 Inferior Malar 10.00 9.00 14.00 12.00 15.75 15.00 15 Lateral Orbit 8.00 8.25 12.50 11.50 11.75 13.75 16 Zygomatic Arch, 6.00 5.75 7.50 7.00 8.75 9.00 midway 17 Supraglenoid 5.75 4.50 8.50 6.25 9.75 7.75 18 Gonion 7.75 6.25 13.25 10.50 15.40 12.75 19 Supra M 14.25 11.75 21.50 18.00 23.50 19.00 20 Occlusal Line 15.50 12.25 20.75 17.50 22.75 19.25 21 Sub M 12.50 10.50 19.25 17.00 18.50 15.75 2 2 Table 3 Tissue thickness measures, Southwestern Indians (mm) 103
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Craniofacial reconstruction using hierarchical B-Spline...
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Craniofacial reconstruction using hierarchical B-Spline interpolation Archer, Katrina Marie 1997
pdf
Page Metadata
Item Metadata
Title | Craniofacial reconstruction using hierarchical B-Spline interpolation |
Creator |
Archer, Katrina Marie |
Date Issued | 1997 |
Description | Craniofacial forensic reconstruction is often the only means of determining a deceased individual's appearance. Current manual methods of estimating the appearance of the individual from his or her skull are extremely expensive and time-consuming. Normally a single facial estimate is produced and publicized. As a result, the success rate for identification resulting from facial reconstruction is on the order of only 50%. A software tool that produces multiple three-dimensional likenesses that more completely cover the range of likely appearances due to factors such as body fat content, and nose and lip appearance would improve this success rate. The application should closely simulate the artist's technique of generating a base facial shape with rough details that are later refined. The prototype generates a generic hierarchical B-spline surface around a 3D scan of the skull. Sparse data points representing tissue thickness are first placed at landmarks about the scan. The generic surface is subsequently automatically placed in order to smoothly and evenly interpolate the data points. This thesis presents a new interpolation method that is well adapted to fitting a hierarchical surface to sparse data points. A reasonable facial approximation is produced from a minimal amount of data using this technique. Multiple facial base shapes are easily created by using the appropriate tissue depths for race, age, sex and body fat content. Facial details such as the eyes, nose and lips can be edited after interpolation. These basic techniques are appropriate for use in an eventual commercial 3D forensic reconstruction tool. |
Extent | 13010785 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
File Format | application/pdf |
Language | eng |
Date Available | 2009-03-24 |
Provider | Vancouver : University of British Columbia Library |
Rights | For non-commercial purposes only, such as research, private study and education. Additional conditions apply, see Terms of Use https://open.library.ubc.ca/terms_of_use. |
DOI | 10.14288/1.0065288 |
URI | http://hdl.handle.net/2429/6373 |
Degree |
Master of Applied Science - MASc |
Program |
Electrical and Computer Engineering |
Affiliation |
Applied Science, Faculty of Electrical and Computer Engineering, Department of |
Degree Grantor | University of British Columbia |
Graduation Date | 1997-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Aggregated Source Repository | DSpace |
Download
- Media
- 831-ubc_1997-0377.pdf [ 12.41MB ]
- Metadata
- JSON: 831-1.0065288.json
- JSON-LD: 831-1.0065288-ld.json
- RDF/XML (Pretty): 831-1.0065288-rdf.xml
- RDF/JSON: 831-1.0065288-rdf.json
- Turtle: 831-1.0065288-turtle.txt
- N-Triples: 831-1.0065288-rdf-ntriples.txt
- Original Record: 831-1.0065288-source.json
- Full Text
- 831-1.0065288-fulltext.txt
- Citation
- 831-1.0065288.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065288/manifest