Printer Friendly

An efficient fast marching algorithm for dental cyst segmentation in digital radiographs.


Digital radiography has several advantages over film radiography. To begin with, digital radiography has a wider dynamic range, and therefore, the radiation exposure to the patient can be reduced. The elimination of chemical processing and processing errors saves time and reduces the radiation exposure. In addition, images can be stored permanently without any degradation of image quality. One of the important advantages of digital radiography is the easy access to image processing. Image processing can reduce retakes caused by processing or exposure errors, because the contrast and density of digital images can be manipulated by image processing. Because of these benefits digital radiography has replaced film radiography in dental practice. The regions of the cysts are of low contrast and the pixel intensity distribution is not homogenous, hence the image processing techniques are used to segment the cyst.

The diagnosis of the tooth cyst is quite usual in the dentistry region, Tooth cyst is a thick capsule in the root of the tooth, which is formed as a reaction to the radicular inflammation of the tooth membranes and infections .Dental cyst are classified, depending on the several factors, location and the causes, in particular, the most common dental cyst types are: radicular and follicular cyst.

The layers in the cyst are

1. Lumen(cavity)- Cyst fluid( watery & opalescent ) but sometimes viscid and Yellowish.

2. Epithelial lining - Non keranized stratified squamous epithelium. Lacks a well-defined basal cell layer. Thick, irregular, hyperplastic or net like forming rings & arcades. Mucous cells as a result of metaplasia.

3. Wall(capsule)- Composed of collagenous fibrous connective tissue.


Radicular cysts are the most common inflammatory cyst arising from the epithelial residues in the periodontal ligament as a result of periapical periodontis following necrosis of the pulp remains asymptomatic and left unnoticed until detected during the routine periapical radiography.


2. Literature Review:

A novel RBF neural network based cyst identification procedure employing cross correlation between original and template images is presented in this paper[2]. The study of severity of dental cysts and the related pathological bony changes used by the various gray levels provide a clear idea to the dentists to arrive at accurate diagnosis and the corresponding treatment plan.

Jaw bone cysts can be classified into two groups: follicular and radicular. The classification of cysts can be performed using a combination of several parameters (circularity, radius of semi-axes of the fitted ellipse, surface of the cystic area [3]. Based on evaluation of the accuracy rates achieved by the various classifiers, they identified the simple Decision Tree method, the Naive Bayes model, and the neural network approach as the most appropriate classification tools.

A new fast algorithm for dental diseases detection has been achieved by performing cross correlation in the frequency domain between input image and the input weights of fast neural networks (FNNs)[4]. It has been proved mathematically and practically that the number of computation steps required for the presented FNNs is less than that needed by conventional neural networks (CNNs).

The oral leukoplakia has a potential to transform into oral cancer, this method can be used as a support in detection of pre-cancerous lesions. To improve classification results the color feature vector should probably be extended with features having more discriminating power e.g. some morphological, texture features or additional color related features[5]. In this particular application, the Hue-Saturation-Intensity system was the most suitable.

Differentiating odontogenic keratocysts and ameloblastomas from other cystic lesions in the maxilla mandibular region is important because of their high recurrence rates. Conventional radiography, CT, and fine-needle aspiration biopsy are limited for differential diagnosis. To assist dentist, it focuses on automatic analysis of cyst using the texture information [6].

The boundaries of oral lesions in color images were detected using a live-wire method and compared to expert delineations[7]. The live-wire algorithm was shown to be considerably more accurate and faster compared to manual segmentations by untrained users. Multiple cost terms were analyzed for their inclusion in the final total cost function including color gradient magnitude, color gradient direction, Canny edge detection, and Laplacian zero crossing.

Live-wire segmentation is an interactive tool for efficient, accurate boundary extraction which requires minimal user input with a mouse to segment the image faster and more accurate than the manual segmentation.[8]. It is very good compromise between simple manual edge tracing and automatic methods such as thresholding, watershed segmentation or other methods. Livewire increases user's capabilities to crop images to "objects", but yet, one cannot employ the algorithm to complex images with long-distance object boundaries.

In this paper, the semi-automated segmentation algorithm is proposed to segment the dental cyst from the dental X-ray images. This method is the combination of both fast multi-level Otsu algorithm and Dual Thresholding Binary Decomposition (DTBD)[9]. The Fast multi-level Otsu algorithm is used to find the threshold that minimizes the input image intra-class variance. The recursive form of Otsu algorithm is applied to each image region until the desired number of thresholds n is obtained. Then the DTBD algorithm is applied to decompose the input grayscale image into a set of binary images by selecting a pair of thresholds from set of Thresholds resulting 2n binary images. The resultant images having the partitions of different dental regions. Among the segmented regions the dental Cyst portion is exposed as prominent region.

The methods discussed above are semi-automated, where more human intervention is needed. so there is a need of an efficient automated segmentation in dental cyst diagnosis. The boundaries of the lesions were manually delineated by oral experts, and served as a ground truth in the performance measurement. 3

3. Introduction To Interface Propagation:

Interface propagation has numerous applications. Water waves, burning fires, growth of cyst and physical boundaries all have a form which is easily interpreted as the propagation of an interface. [11] This application of this project will be in the field of computer vision. The fast marching method can be used when solving the problem of image segmentation. In order to implement these methods, a numerical approximation scheme for the two principle interface propagation formulations must be constructed. These schemes must propagate the interface using a desired motion, and satisfy certain requirements such as not introducing any new information when propagating. Using a Hamilton-Jacobi formulation will allow the construction of such schemes, where numerical approximations will be provided by numerical flux functions. The function F in fig 3.1 is often referred to as the speed function.



4. Introduction To Live Wire Algorithm:

Livewire is a semi-automatic image segmentation technique that allows a user to easily and quickly select regions of interest on an image using mouse clicks to delineate the edges. When the user starts the selection of the region with a mouse click, a virtual wire is created linking the first clicked point referred as anchor to the point where the mouse is over, following a path that is as close as possible from image features detected as edges. Livewire is known as Intelligent scissors The algorithm produces reasonable cost function to construct the optimal path between the starting point and ending point provided by the user, so as to achieve the purpose of edge segmentation. The important point of the live-wire algorithm is the construction of it is cost function. The live-wire in this work has includes the gradient magnitude, gradient direction, Canny edge detection, and Laplacian zero crossing edge detection as part of the cost function. [7].The local cost function C.

4.1 Cost term Calculation:

The local cost function used in the live-wire algorithm can include different terms one of which is usually the gradient information. The live-wire in this work has included the gradient magnitude, gradient direction, Canny edge detection, and Laplacian zero crossing edge detection as part of the cost function. The local cost function C(p, q) from pixel p to a neighboring pixel q is defined as

C(p, q) = wz fz(q) + wc fC(q) + wg fG(q) + wd fD (p,q) (4.1)

where fZ(q), fC(q), fG(q), and fD(p, q) represent the Laplacian zero crossing edge detection, Canny edge detection, gradient magnitude and gradient direction cost terms, respectively. Each cost term is weighted by a corresponding weight constant wZ, wC, wG, and wD to allow cost terms to contribute to the total cost at different rates. The local cost term for the gradient magnitude of pixel q is defined as fG(q) = 1 - G(q)/max(G) (4.2)

where G(q) is the magnitude of the color gradient estimated as [square root of [lambda]]max at pixel q and max(G) is the highest gradient from the entire image. The local cost term is subtracted from 1 so that strong edges give low cost. Similarly, the eigenvector that corresponds to the maximum eigenvalue is inverted for the gradient direction local cost term. The local cost term for the gradient direction from pixel p going to pixel q is defined as fD(p,q) = [acos ([D.sub.x](p)/G(p) * [D.sub.x](q)/G(q) + [D.sub.y](p)/G(p) * [D.sub.y](q)/G(q)) / [pi] ] (4.3)

where [D.sub.x](p) and [D.sub.y](p) are the eigenvectors corresponding to the largest eigenvalue for the x and y gradient directions of pixel p, respectively, where


The gradient image was computed using a vector gradient approach. An image is here defined as a function (a vector field), which maps an n-dimensional (spatial) space to an m-dimensional (color or attribute) space. In our application, the color images map a two-dimensional (n=2) spatial space (x, y) into a threedimensional (m=3) color space (u, v, w). Here (u, v, w) represent the corresponding color space coordinates.

The output of edge detection functions is a binary image with edges represented as pixels containing ones and the rest of the background pixels containing zeros. Therefore, these binary images must also be inverted to give strong edges low costs. Furthermore, the function C(p, q) is scaled by [square root of 2], if pixel q is a diagonal neighbor to pixel p, which corresponds to the Euclidian metric.

4.2 Live wire operation on Cyst image:

Livewire typically works as two stage process.

1. The entire image must be filtered using filters such as the Median filter, and/or edge detection algorithms such as the Sobel filter and

2. A lowest cost path algorithm, such as Dijkstra's algorithm, is applied to the modified image to find the best path from one point, to another. In resulting "graph" each pixels is a node with edges going to the 4 (up, down, left, right) or 8 pixels around it and the edge costs are defined on a cost function based on the pixel value, and possibly other factors.

The user sets the starting point clicking on an image's pixel, known as an anchor. Then, as he starts to move the mouse over other points, the smallest cost path is drawn from the anchor to the pixel where the mouse is over, changing itself if the user moves the mouse. If he wants to choose the path that is being displayed, he simply clicks the image again.

One can easily see in the right image, that the places where the user clicked to outline the desired region of interest are marked with a small square. It is also easy to see that the livewire has snapped on the image's borders.[8].

5. The Fast Marching Method (Fmm):

The fast marching method is appropriate only for the boundary value problem. The basic principle underlying this method is that the boundary value problem contains a front that is always expanding or contracting.

[absolute value of [nabla]T]] F = 1 (5.1)

For the boundary value formulation, F > 0 or F < 0 for all time. This implies that an interface described by the boundary value formulation is strictly expanding or contracting. Since the interface can only move in one direction, the efficient Fast Marching Method can be used.

As such, the interface is always propagated to the next smallest T value in the grid, since the interface will always reach the unknown node nearest to the known fringe next.

There must be some iteration condition that will be specific to the problem being solved. This will most likely be when a certain time value or location is reached. Also, for efficiency sake, the min-heap should keep not only the time values, but a pointer to which cell that T value came from.

The Fast Marching method [12] is connected to Huyghen's principle, which is a construction involving expanding wave fronts, and Dijkstra's method, which is depth-first search algorithm on network paths.

The viscosity solution to the Eikonal equation.

[absolute value of [nabla]u(x) = F(x)] (5.2)

can be interpreted through Huyghen's principle in the following way; circular wave fronts are drawn at each point on the boundary, with the radius proportional to F (x). The envelope of these wave- fronts is then used to construct a new set of points, and the process is repeated in the limit the Eikonal solution is obtained. The Fast Marching Method mimics this construction a computational grid is used to carry the solution u, and an upwind, viscosity-satisfying finite difference scheme is used to approximate this wave front.

In more detail, the Fast Marching Method is as follows. Suppose at some time the Eikonal solution is known at a set of points (denoted Accepted points). For every not-yet accepted grid point such that it has an accepted neighbor, we compute a trial solution to the a quadratic equation.

For the boundary value formulation, it is to be solved

[absolute value of [nabla]u(x,y,z)] = f (x,y,z)] (5.3)

Using the multi-dimensional approximations


The forward and backwards operators [D.sup.-y], [D.sup.+y], [D.sup.-z], [D.sup.+y] in the other coordinate directions are similar to the one defined earlier for the x direction.

It can be written in convenient way as


First, tag points in the initial conditions as Accepted. Then tag as Considered all points one grid point away and compute values at those points by solving Eqn. 5.5 Finally, tag as Far all other grid points.

Fmm Algorithm:

(1) Begin Loop: Let Trial be the Considered point with smallest value of u.

(2) Tag as Considered all neighbors of Trial that are not Accepted. If the neighbor is in Far, remove it from that set and add it to the set Considered.

(3) Recompute the values of u at all Considered neighbors of Trial by solving the piecewise quadratic equation according to Eqn. 5.5

(4) Add point Trial to Accepted; remove from Considered.

(5) Return to top until the Considered set is empty.

This is the Fast Marching Method given in [13]. Malladi and Sethian apply the Fast Marching Method to image segmentation in [14].


a.Input 1                           b. Input 2
c.Geodesic distances of Input 1     d.Geodesic distances of Input 1
e.Segmented output                  f.Segmented output
e.Segmented output                  f.Segmented output

In the Fig 6.1 the first Cyst image is taken for applying the fast marching algorithm. The algorithm started with seed manual seed point selection. The geodesic distances are calculated first for that image. From that the cyst portion is segmented effectively. In the output the curve edges, ridges of cyst portion is segmented effectively. This method is semi-automatic, because it needs only the selection of seed points. But in Live wire program we have to trace the edges of cyst. So the delineation of cyst is fully manual in Live wire algorithm.

Comparison with Live Wire algorithm:

a.Input Image                       b. Livewire Boundary Output
c.Segmented Cyst using Live wire    d.FMM output


Even in the presence of physical indicators like pain, tumor, color, and function loss, determining the exact size or location of acute dental apical diseases is challenging. This paper is aimed to introduce an automated dental apical lesion detection methodology by assessing changes in hard tissue structures. Fast marching method is the interface techniques can be used to segment images. The central idea is to grow a seed inside a region with a propagation velocity which depends on the image gradient and hence stops when the boundary is reached. This stems from a Dijkstra-like technique which exploits a causality relationship inherent in the chosen upwind finite difference formulation. The fast marching method outperforms the livewire algorithms where the cyst regions are well extracted and it is very fast. It extracts uneven boundaries very effectively which helps dentists in surgically removing the cyst. Future work includes the improvement to be made in the algorithm is, the selection of seed pixel to be fully automatic instead manual seeding. This is a step forward in achieving accurate diagnosis as well as increasing the utility of digitized radiographs in providing qualitative and quantitative information concerning the investigated diseases.


[1.] Cernochova, P., 2006. "The Diagnosis of Impacted Teeth". Prague: Grada Publishing, ISBN 80-247-12695.

[2.] Banumathi, A., J. Praylin Mallika, S. Raju, V. Abhai Kumar, 2009. "Automated Diagnosis and Severity Measurement of Cyst in Dental X-ray Images using Neural Network" Int.J. of Biomedical Soft Computing and Human Sciences, 14(2): 103-108.

[3.] Jan Mikulka, Eva Gescheidtova, Miroslav Kabrda, Vojtech Perina, 2013. "Classification of Jaw Bone Cysts and Necrosis via the Processing of Orthopantomograms" Radio engineering, 22: 1.

[4.] Hazem, M., El-Bakry, Nikos Mastorakis, 2008. "An Effective Method for Detecting Dental Diseases by using Fast Neural Networks", 8th WSEAS International Conference On Signal, Speech And Image Processing (SSIP '08) Santander, Cantabria, Spain, pp: 23-25.

[5.] Chodorowski, A., U. Mattson, T. Gustavasson, "Oral lesion classification using true color images", Department of Signals and Systems, Chalmers University of Tech., Sweden.

[6.] Vijayakumari, B., G. Ulaganathan, A. Banumathi, AFS Banu, M. Kayalvizhi, 2012. "Dental cyst diagnosis using texture analysis" Machine Vision and Image Processing (MVIP), IEEE International Conference, 117-120,978-1-4673-2319-2.

[7.] Chodorowski, A., U. Mattsson, M. Langille, G. Hamarneh, 2005. "Color Lesion Boundary Detection Using Live Wire", Proceedings of SPIE Medical Imaging: Image Processing, 5747: 1589-1596.

[8.] Ulaganathan, G. Banumathi, A. Amutha, J.J. Jeevani Selvabala, 2012. "Dental Cyst Delineation Using Live Wire Algorithm" Machine Vision and Image Processing (MVIP), International Conference on pp: 129-132.

[9.] Karthika Devi, R., A. Banumathi, G. Ulaganathan, 20145. "An Automated Segmentation Algorithm for Dental Cyst using Dual Threshold Binary Decomposition" IJAER, 10(28): 22069-22074.

[10.] Costa, A.F., G.E. Humpire-Mamani, A.J.M. Traina, 2012. "An Efficient Algorithm for Fractal Analysis of Textures." In SIBGRAPI 2012 (XXV Conference on Graphics, Patterns and Images), 39-46, Ouro Preto, Brazil.

[11.] Chopp, D.L., and J.A. Sethian, 1993. "Flow Under Curvature: Singularity Formation, Minimal Surfaces, and Geodesics", Jour. Exper. Math., 2: 4.

[12.] Chopp, D.L. and J.A. Sethian, 1999. "A Level Set Approach to the Numerical Simulation of Viscous Sintering", Interfaces and Free Boundaries.

[13.] Sethian, J.A., 1996. "A Marching Level Set Method for Monotonically Advancing Fronts", Proc. Nat. Acad. Sci., 93(4): 1591-1595.

[14.] Malladi, R. and J.A. Sethian, 1996. "An O(N log N) Algorithm for Shape Modeling", Proc. Nat. Acad. Sci., 93.

(1) R. Karthika Devi and (2) A. Banumathi

(1) Associate Professor, Dept. of Electronics and Communication Engineering, Sethu Institute of Technology, Pulloor, Kariapatti, Virudhunagar 626115 India.

(2) Associate Professor, Dept. of Electronics and Communication Engineering,Thiagarajar College of Engineering, Madurai 625015 India.

Received 27 May 2016; Accepted 28 June 2016; Available 12 July 2016

Address For Correspondence:

R. Karthika Devi, Associate Professor, Dept. of Electronics and Communication Engineering, Sethu Institute of Technology, Pulloor, Kariapatti, Virudhunagar 626115 India.

COPYRIGHT 2016 American-Eurasian Network for Scientific Information
No portion of this article can be reproduced without the express written permission from the copyright holder.
Copyright 2016 Gale, Cengage Learning. All rights reserved.

Article Details
Printer friendly Cite/link Email Feedback
Author:Devi, R. Karthika; Banumathi, A.
Publication:Advances in Natural and Applied Sciences
Date:Jun 30, 2016
Previous Article:Factors influencing online shopping intention: impact of perceived risk.
Next Article:Evaluation of MRR and surface roughness of high carbon high Chromium die steel in electrical discharge machining.

Terms of use | Privacy policy | Copyright © 2020 Farlex, Inc. | Feedback | For webmasters