Figures
Abstract
This paper proposes the reconstruction of craniofacial fracture using rational cubic Ball curve. The idea of choosing Ball curve is based on its robustness of computing efficiency over Bezier curve. The main steps are conversion of Digital Imaging and Communications in Medicine (Dicom) images to binary images, boundary extraction and corner point detection, Ball curve fitting with genetic algorithm and final solution conversion to Dicom format. The last section illustrates a real case of craniofacial reconstruction using the proposed method which clearly indicates the applicability of this method. A Graphical User Interface (GUI) has also been developed for practical application.
Citation: Majeed A, Mt Piah AR, Gobithaasan RU, Yahya ZR (2015) Craniofacial Reconstruction Using Rational Cubic Ball Curves. PLoS ONE 10(4): e0122854. https://doi.org/10.1371/journal.pone.0122854
Academic Editor: James Cray Jr., Medical University of South Carolina, UNITED STATES
Received: November 18, 2014; Accepted: February 15, 2015; Published: April 16, 2015
Copyright: © 2015 Majeed et al. This is an open access article distributed under the terms of the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original author and source are credited
Data Availability: CT scan data used for this study were obtained by the authors from the USM. Data requests may be sent to the corresponding author.
Funding: The authors would like to extend their gratitude to the Ministry of Education of Malaysia and Universiti Sains Malaysia for supporting this work under its Fundamental Research Grant Scheme (FRGS), Account No. 203/PMATHS/6711365. The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.
Competing interests: The authors have declared that no competing interests exist.
Introduction
Craniofacial refers to the study and treatment of certain congenital malformations or facial injuries. Craniofacial fractures are common with the principal causes by sports-related injuries, gunshot wounds, and motor vehicle accidents. Frequently encountered craniofacial fractures hold certain distinct patterns. Sometimes the fracture is small and at times it makes a large cavity in the skull. A direct surgical reconstruction is complex, time consuming and expensive, where the surgeon relies on personal experience to reconstruct the structure back to its normal contour.
Today, the emerging virtual craniofacial reconstruction employs computer vision technologies which opens its door for mathematicians, engineers, and doctors to visualize, identify and reconstruct the hard/soft tissues using various curves and splines see [1–10] and references therein.
Ball curve was first introduced by Alan Ball at British Aircraft Corporation (BAC) which was featured in BAC Computer Aided Design (CAD) system [11]. It has a number of similar features as the world renowned Bezier curves such as symmetry, satisfies convex hull property, variation diminishing property, coordinate system independence, invariant under affine transformation and interpolates end points.
The distinct advantages of Ball basis functions over Bezier basis functions are twofold. Firstly, a robust algorithm has been developed to evaluate the Ball curve which suits interactive design environment [12–15]. Secondly, generalized Ball basis suits much better in degree elevation and reduction which eases data portability and curve approximation in CAD systems [16, 17]. We have chosen rational Ball curve for the reconstruction of craniofacial due to these reasons. Other advantages include the flexibility, easy shape tweaks by changing control points and extra free parameters which can be used to satisfy design constraints.
This paper proposes the construction of missing portion of traumatised parts of the craniofacial region using rational cubic Ball curves and the final solution is represented in Dicom format for direct application. The next section discusses on the representation of rational cubic Ball basis functions. It is followed by an explanation on boundary extraction and corner detection, and then on genetic algorithm (GA) which is used as an optimization engine to obtain the best fit for derived corner points. An algorithm on craniofacial reconstruction using rational Ball curve is proposed after the explanation of GA configuration. A real case of craniofacial fracture has been chosen to show the applicability of proposed algorithm. These data are obtained from Universiti Sains Malaysia (USM) Health Campus. Matlab has been used to develop a Graphics User Interface (GUI) for craniofacial reconstruction using the proposed algorithm, which can be used by surgeons who may employ this tool without detailed understanding of its mathematical knowledge.
The Rational Cubic Ball Interpolant
The cubic Ball polynomial basis was first proposed by Ball [11] for CAD systems application. Fig 1 illustrates these functions against its parameter θ. The Ball basis functions can be written as
where
These functions were further generalized by Said to arbitrary degree [12]. He further proposed a recursive formula to compute Ball curve which were proven to be more efficient than Bezier curves. A rational cubic Ball curve for craniofacial reconstruction is given as follows:
(1)
where
and
Eq (1) satisfies the following conditions
(2)
ai, bi are free parameters, fi, fi+1 are the endpoints of each segment, and di, di+1 are unit tangent vectors at fi and fi+1, respectively.
Boundary Extraction and Corner Detection
The first step on craniofacial reconstruction is to identify the boundary of missing part from a scanned image which is in Dicom format. The boundary of the original image is obtained using mathematical morphology defined by β(A) = A − (AΘB) where A is the set of all black pixel, B is the 3×3 structuring element and β(A) is the boundary of set A. Θ and —represent the erosion and difference operator, respectively. The corner points are used to divide the boundaries into smaller segments. This paper employs Sarfraz et al.’s method [18] to identify the corner points.
Parameterization
Chord length parameterization is used to evaluate the values of θi related to points fi = Di, where Di represent the data points of segments,
(3)
It can be observed that θi is a normalized form and varies from 0 to 1 with hi = θi+1 − θi. Hence, .
Tangent Vectors
In general, the tangent vectors di at fi are defined as follows:
For open curve,
for i = 1, .…, n − 1.
For close curve,
for i = 1, .…, n − 1.
We use both open and closed curves. To reconstruct the complete skull we use closed curves and to reconstruct curves of the missing parts for each slice, we use open curves.
Normalized Mean Squares Error
A normalized mean squares error is used as cost function which is employed to find the errors of free parameters of rational Ball interpolant. The normalized mean squares error is computed by
(4)
where Di represents the pixel values of the segments and θ is the parameterized chord length. The goal is to find the values of unknown parameters ai and bi in Eq (1) in order to minimize the normalized mean squares error. GA is used to optimize the value of ai and bi for craniofacial reconstruction.
Genetic Algorithm
Once the boundaries and corners are identified, the next step is to fit rational cubic Ball curves to reconstruct the missing craniofacial parts. For this we have to minimize Eq (4) for best fitting rational Ball curve. Two free parameters ai and bi are involved in Eq (4). We use a continuous genetic algorithm (GA) as an engine to optimize free parameters ai and bi to obtain a suitable fit from given boundaries and corner points.
The GA employed in this study is similar to binary GA where the primary difference is variables are no longer represented by bits of zeros and ones. We start the GA process on E2 by defining a chromosome as an array of variables to be optimized. Since there are two variables for our interpolant, the chromosome is represented as an array of 1×2 elements i.e chromosome = [ai, bi], i = 1, … n.
The GA is an optimization engine which must be constrained to explore a reasonable region of variable space. Sometimes this is done by imposing a constraint on the interpolant. For example, if an initial search region is unknown, then we define a suitable search space to start the GA process. It is then followed by stating an initial population of chromosome; a normal practise is the initial population is varied from 2k to 4k, where k is the number of chromosomes. In our case, initial population size is set to be 8. The chromosomes are now ready for evaluation and selection of suitable interpolant.
In the next step, we select chromosomes in the initial population which fits enough to survive and possibly reproduce a better offspring in the next generation. For this, the cost and its associated chromosomes are ranked from lowest to highest. Only the top 50% of population with lowest cost will be selected for crossover which are represented as new set of parents. This process of natural selection occurs at each iteration of the algorithm.
The simplest method for crossover is to choose one or more points in the selected chromosomes to produce various solutions. The variables at these points are merely swapped between the two parents. Mutation is the final step where we change some chromosome values randomly within the search space; usually the mutation rate is set to 20%. This process continues iteratively for a given number of generations or until a result obtained is less than a defined value.
Curves to Dicom Format
After fitting the missing part with rational Ball curves of each Dicom image, the next step is to convert the missing part into a Dicom format. For this, we take the corner points of both curves and then join the initial and final points by using the following linear form:
where Ai and Bi are initial and final points of curves, and t varies from 0 to 1. Our next step is to define a black image (all zero values) of the same size as the original Dicom image slices. The fitted rational Ball curve is then converted into white form by equaling this data to 1. Finally, we use Matlab command imfill to fill the area bounded by the curves. To note, ezDicom is a software which is used to read the constructed Dicom image.
Graphical user interface(GUI)
A graphical user interface (GUI) is graphical display which is used to carry out interactive tasks and consists on one or more windows having controls. These are called components. This interface eases out user from creating and executing the commands in order to complete tasks. In contrast to coding programs GUI user does not have to go into details to understand the procedure of execution of commands. This interface include menu, start and stop buttons, boxes etc.
Each control, and the GUI itself, has one or more user written routines (executable MATLAB code) known as callbacks, named for the fact that they call back to MATLAB to ask it to do things. The execution of each callback is triggered by a particular user action such as pressing a screen button, clicking a mouse button, selecting a menu item, typing a string or a numeric value, or passing the cursor over a component. The GUI then responds to these events. In this article GUI is used to control the curve by using free parameters. The input is the end points of missing part depending on the users. The free parameters allow the user to control the curve.
Proposed Algorithm
This section simplifies the algorithm for craniofacial fracture reconstruction.
- Input: CT scan image in Dicom format. (case study: A patient with head injury for craniofacial fracture reconstruction as shown in Figs 2 and 3)
- Boundaries are divided into segments after obtaining corner points. The blue dots in Fig 4d represent the corner points
- Each segment is fitted using rational Ball interpolant where the unknown parameters ai and bi in Eq (1) are optimized using genetic algorithm. We used sixteen segments for the construction of outer curve of slice 176 in Fig 4d and twenty segments for inner curve shown in Fig 4d
- Errors are calculated using normalized mean squares equation for all segments of both inner and outer curves of slice 176 see in Table 1
- Steps 3 and 4 are repeated until a desired solution is obtained
- The CT scan data used in this case has 189 slices out of these 55 slices have a fracture part
- Reconstruct the missing part for each Dicom slice separately after converting the image into binary and boundary form Fig 5b and 5c
- Finally, convert the area enclosed by the curves into Dicom format using Matlab, and ezDicom software is used to visualize the constructed Dicom image
- GUI is used to construct the missing part with out understanding the mathematics behind
(a) Original image (b) Binary image (c) Boundary (d)Reconstructed boundary using rational cubic Ball
(a)Original image (b) Binary image (c) Boundary (d)Reconstructed missing part using rational cubic Ball
Results and Discussion
Case Study: A Patient With Head Injury
This section illustrates an example of application of the proposed algorithm. We have constructed the inner and outer curve for all CT scan slices using rational Ball interpolant. Fig 5a is the original CT scan of slice 160. To construct the traumatized part, we first convert the image to its binary form Fig 5b, then we extracts the boundary of skull shown in Fig 5c using mathematical morphology. Fig 5d shows the reconstructed inner and outer curves. Once a satisfactory result is obtained from GA optimization, we convert the area between two curves into Dicom format as shown in Fig 6. The first image of Fig 6 shows a given Dicom slice of 160, the second image is the missing part obtained from the proposed algorithm in Dicom and third image is the combination of first two images, which is the required Dicom solution. This process is repeated for various CT scan slices as shown in Figs 7–12. The given Dicom data for skull are in sequence and consistent for different frames or contours. The constructed curves of the missing parts using rational cubic Ball interpolant will be consistent between different frames since these curves obey convex hull property, variation diminishing property (VDP), independent of coordinate system and satisfy the end point conditions. By convex hull property all constructed curves will lie within the convex hull of control polygon. Fig 13 represents the graph of normalized mean squares error of slice 176. Fig 14 is the display of Graphical User Interface (GUI).
(a)Original image (b) Binary image (c) Boundary (d)Reconstructed missing part using rational cubic Ball
(a)Original image (b) Binary image (c) Boundary (d)Reconstructed missing part using rational cubic Ball
(a)Original image (b) Binary image (c) Boundary (d)Reconstructed missing part using rational cubic Ball
Conclusion
This paper proposes craniofacial reconstruction using cubic rational Ball interpolant. A patient with head injury as a case study is illustrated to show its applicability. The computed errors and final outputs indicate that the proposed interpolant is suitable for solving craniofacial reconstruction problem. In addition, a user friendly GUI is developed which surgeons may use for practical applications.
Acknowledgments
The authors would like to acknowledge Dr Hassan Iqbal’s (Resident Oral and Maxillofacial Surgery in Pakistan) input in reading this article and supporting us in elaborating it. The authors are also grateful to the anonymous reviewers for their helpful, valuable comments and suggestions in the improvement of this manuscript.
Author Contributions
Conceived and designed the experiments: AM ARMP. Performed the experiments: AM ARMP ZRY. Analyzed the data: RUG AM. Contributed reagents/materials/analysis tools: RUG ZRY. Wrote the paper: AM RUG ARMP. Carried out coding, verification and calculation using Matlab: AM.
References
- 1.
Vandermeulen D, Claes P, Loeckx D, De Greef S, Willems G (2006) Computerized craniofacial reconstruction using CT-derived implicit surface representations. Forensic Science International 159: S164–S174.
- 2.
Eck M, Hoppe H (1996) Automatic reconstruction of B-spline surfaces of arbitrary topological type. In: Proceedings of the 23rd Annual Conference on Computer Graphics and Interactive Techniques. ACM, 325–334.
- 3. Magnenat-Thalmann N, Cordier F (2000) Construction of a human topological model from medical data. Information Technology in Biomedicine, IEEE Transactions on 4: 137–143.
- 4. Lian Q, Li DC, Tang YP, Zhang YR (2006) Computer modeling approach for a novel internal architecture of artificial bone. Computer-Aided Design 38: 507–514.
- 5. Kou X, Tan S (2007) Heterogeneous object modeling: A review. Computer-Aided Design 39: 284–301.
- 6.
Fang Z (2005) Image-guided modeling, fabrication and micromechanical analysis of bone and heterogeneous structure. Ph.D. thesis, Drexel University.
- 7. Bhatt AD, Warkhedkar RM (2008) Reverse engineering of human body: a B-spline based heterogeneous modeling approach. Computer-Aided Design and Applications 5: 194–208.
- 8. Park H, Lee JH (2007) B-spline curve fitting based on adaptive curve refinement using dominant points. Computer-Aided Design 39: 439–451.
- 9. Yoshimoto F, Harada T, Yoshimoto Y (2003) Data fitting with a spline using a real-coded genetic algorithm. Computer-Aided Design 35: 751–760.
- 10. Li W, Xu S, Zhao G, Goh LP (2005) Adaptive knot placement in B-spline curve approximation. Computer-Aided Design 37: 791–797.
- 11. Ball AA (1974) CONSURF. Part one: introduction of the conic lofting tile. Computer-Aided Design 6: 243–249.
- 12. Said H (1989) A generalized Ball curve and its recursive algorithm. ACM Transactions on Graphics (TOG) 8: 360–371.
- 13. Majeed A, Piah ARM (2014) Image reconstruction using rational Ball interpolant and genetic algorithm. Applied Mathematical Sciences 8: 3683–3692.
- 14.
Yahya ZR, Piah ARM, Majid AA (2012) Conic curve fitting using particle swarm optimization: Parameter tuning. In: Knowledge Technology, Springer 379–382.
- 15. Piah ARM, Unsworth K (2011) Improved sufficient conditions for monotonic piecewise rational quartic interpolation. Sains Malaysiana 40: 1173–1178.
- 16. Goodman TN, Said H (1991) Properties of generalized Ball curves and surfaces. Computer-Aided Design 23: 554–560.
- 17.
Farin GE (2002) Curves and surfaces for CAGD: a practical guide. Morgan Kaufmann.
- 18.
Sarfraz M, Masood A, Asim M (2006) A new approach to corner detection. In: Computer Vision and Graphics, Springer 528–533.