Automatic Image Segmentation method based on ALG

Abstract

An automatic anatomy segmentation method is proposed which effectively combines the Active Appearance Model, Live Wire and Graph Cut (ALG) ideas to exploit their complementary strengths. It consists of three main parts: model building, initialization, and delineation. For the initialization (recognition) part, a pseudo strategy is employed and the organs are segmented slice by slice via the OAAM (Oriented Active Appearance method). The purpose of initialization is to provide rough object localization and shape constraints for a latter GC method, which will produce refined delineation. It is better to have a fast and robust method than a slow and more accurate technique for initialization. One of the strengths of the proposed method is to segment the organ during the process of manually delineating the boundaries. For single-object segmentation, global optimality is guaranteed.

Keywords

Active Appearance model, Oriented Active Appearance Model, Live Wire method, Graph cut method

INTRODUCTION

Image segmentation is a classic problem in computer vision. It is a process that partitions the image pixels into meaningful groups so that we can achieve a compact representation of the image. Segmentation is usually performed based on many factors, such as intensity, color, or texture similarities, pixel continuity, and higher level knowledge about the objects model. Image segmentation has many applications in the biomedical field. In medical image analysis, image segmentation is a fundamental and challenging problem. In spite of several decades of research and many key advances, several challenges still remain in this area. An Efficient, robust, and automatic segmentation of anatomy on radiological images is one such challenge. Medical imaging has become an important part in health care nowadays. Xrays, ultrasound, computer tomography (CT) and magnetic resonance (MR) images have been routine diagnostic methods that are performed in hospitals and clinics. In many cases, the tissues or organ of interest is difficult to be separated from its surroundings, when they share similar intensity levels. With the other tissues, and their boundaries lack strong edge information. For example, CT technique is weak at imaging soft tissues. It cannot differentiate grey and White matters well in neural tissues.

In [9], the main goals of segmentation are to be (i) to provide effective control to the user, and (ii) to minimize the total user's time required in the process. In this paper, authors have proposed two paradigms, referred to as live wire and live lane. In live wire, the user first selects an initial point on the boundary. An optimal path from the initial point to the current point is found and displayed in real time. The user thus has a live wire on hand which is moved by moving the cursor. If the cursor goes close to the boundary, the live wire snaps onto the boundary. In live lane, the user selects only the initial point. Subsequent points are selected automatically as the cursor is moved within a lane surrounding the boundary whose width changes as a function of the speed and acceleration of cursor motion. Live-wire segments are generated and displayed in real time between successive points. This method is1.5–2.5 times faster than manual tracing. In [3], to encode the image support, a Voronoi decomposition of the domain is considered and regional based statistics are used. The resulting model is computationally efficient, can encode complex statistical models of shape variations. The main challenges of knowledge-based segmentation are: (i) appropriate modelling of shape variations, (ii) successful inference between the image and the manifold. In this knowledge based approach, defined the shape model as an incomplete graph. The proposed approach aims to optimize the connectivity of the graph nodes, and learns the structure and the local deformation statistics of an object from a set of training examples. However, this method did not perform segmentation at the pixel level.

II. MATERIALS AND METHODS

A. Live wire Method

The boundary-based segmentation strategies have two specific aims:

1) To provide as complete a control as possible to the user on the segmentation process while it is being executed and

2) To minimize the user involvement.

The total user’s time required for segmentation, without compromising the precision and accuracy of segmentation. This strategy in these boundary-based segmentation methods has been to actively exploit the superior abilities of human operators (compared to computer algorithms) in object recognition and the superior abilities of computer algorithms (compared to human operators) in object delineation. Falcao and Udupa [9] developed a method that determines object boundary information from orthogonal slices of a volume segmented by a user. This technique allows the user to segment a minimal number of slices, reducing the total segmentation time. The user-steered 2-D segmentation method [9] allows the user to select three seed points. After selection, Live Wire is used to generate an initial frame and then “spokes.” After the spokes are found, a gap filling algorithm is used to close the space between spokes. The Live Wire method stands out among the class of user-interactive image segmentation tools. The user clicks on an edge of the object with the mouse, defining a “seed point”. The user then moves the cursor to some other portion of the object’s edge. The pixel that lies under the cursor is called the “free point”. As the free point moves, a wire connecting the seed point and the free point automatically snaps to the edge.

The Live Wire has proven to be very powerful and is widely used because of its high degree of userinteractivity. This is because automatic segmentation is still an unsolved problem and many datasets still require expert knowledge from users. A drawback of this method is that the speed of optimal path computation depends on image size. On modestly powered computers, for images of even modest size, some sluggishness appears in user interaction, which reduces the overall segmentation efficiency. In this work, this problem is solved by exploiting some known properties of graphs to avoid unnecessary minimum-cost path computation during segmentation. In this project, user steered segmentation paradigms, [9] referred to as live wire and live lane has used to segment three-dimensional (3-D) object boundaries in a slice-by-slice fashion.

B. Active Appearance Model

PCA is used to find the mean shape and main variations of the training data to the mean shape[6]. After finding the Shape Model, all training data objects are deformed to the main shape, and the pixels converted to vectors.

C. Graph Cut Method

By applying the graph cut technique, a wide variety of low-level computer vision problems, such as image smoothing and many other computer vision problems and the stereo correspondence problem, can be solved in terms of energy minimization. This approach can solve binary problems exactly: But, problems where pixels can be labeled with more than two different labels cannot be solved exactly, but there is the optimum solution to the problem. In the graph cut technique we represent the image in the form of graphs. So here we represent the each pixel as a node and the distance between those nodes as the edges. In graph theory, a cut is a partition of the nodes that divides the graph into two disjoint subsets. The set of cuts of the cut is the set of edges whose ending points are in different subsets of the divided region. And in the case of a weighted graph, it is defined as the sum of the weights of all the edges crossing the cut. The basic cuts in the graph theory are minimum cut and maximum cut.

III. PROPOSED METHODOLOGY

The proposed GC – OAAM method consists of two phases:

1) Training Phase and

2) Segmentation Phase.

Fig.1 presents the Flowchart of the proposed GC–OAMM system. In the training phase, an AAM is constructed, and the LW boundary cost function and GC parameters are estimated. The segmentation phase consists of two main steps: recognition or initialization and delineation. In the recognition step, a pseudo-3-D initialization strategy is employed in which the pose of the organs is estimated slice by slice via a object OAAM method. A further refinement may be needed to adjust the initialization of improperly initialized slices.

First, 3-D initialization is difficult and has computational drawbacks; the proposed method is much faster. Second, combining the AAM and LW in a 3-D manner is challenging. Indeed, the pseudo-3-D method offers fast initialization, and its performance is comparable to the fully 3-D AAM initialization method. Finally, for the delineation part, the object shape information generated from the initialization step is integrated into the GC cost computation. Before building the model, the top and bottom slices of each organ are first manually identified. Then, linear interpolation is applied to generate the same number of slices for the organ in every training image. Since we treat shape as an infinite point set in principle, it can be assumed that the shape of an object is captured by a finite subset of a sufficient number of its points. Therefore, different numbers of landmarks are used for different objects based on their size. Since there is a vast amount of literature on the analysis of effects of distribution of landmarks on model building and segmentation results, we avoid repeating these experiments, but we validate manual land marking by the equal-space labelling method. Once the landmarks are specified, the standard AAM method [6], [7] is used for constructing the model.

GC segmentation can be formulated as an energy minimization problem such that, for a set of pixels p and a set of labels, the goal is to find a labelling f : p → Lthat minimizes the energy function En (f)as follows:

IV. RESULTS AND DISCUSSION

Fig. 2 shows the input test image. This test image is matching with the trained image. The contour line selection is based on the knowledge of OAAM training output. Because it can select the best edge contour line is selected by initialization step of the algorithm.

Here we have the best contour line fixed to the best place of the test image by manually. So this method is called semi-automatic method.

The best contour line is fixed manually to the best place of test image as shown in the figure 4.10. The next following outputs and finally concluded boundary selection are shown (Fig.4.) for detecting suitable boundary line for the corresponding object.

The finalized segmented output, which is the representation of the proposed algorithm for the 2D test image is as shown in figure 4.17. From this output, the proposed method is eligible for 3D image segmentation by mentioning of top and bottom slice for the test 3D image.

V. CONCLUSION

An automatic anatomy segmentation method is proposed which effectively combines the Active Appearance Model, Live Wire and Graph Cut (ALG) ideas to exploit their complementary strengths. It consists of three main parts: model building, initialization, and delineation. For the initialization (recognition) part, employ a pseudo strategy and segment the organs slice by slice via the OAAM (Oriented Active Appearance method). The purpose of initialization is to provide rough object localization and shape constraints for a latter GC method, which will produce refined delineation. It is better to have a fast and robust method than a slow and more accurate technique for initialization. One of the strengths of the proposed method is to segment the organ during the process of manually delineating the boundaries. For single-object segmentation, global optimality is guaranteed.

References

1. A. Ayvaci and D. Freedman, “Joint segmentation-registration of organs using geometric models,” in Proc. IEEE Eng.Med. Biol. Soc.,pp. 5251–5254,2012
3. R. Anderson and J. Setubal, “A parallel implementation of the push relabel algorithm for the maximum flow problem,” J. Parallel Distrib. Comput., vol. 29, no. 1, pp. 17–26, Aug. 2011.
5. A. Besbes, N. Komodakis, G. Langs, and N. Paragios, “Shape priors and discrete MRFs for knowledge-based segmentation,” in Proc.IEEE Comput. Soc. Conf. Comput. Vis. Pattern Recogn., pp. 1295–1302,2011
7. Y. Boykov and V. Kolmogorov, “An experimental comparison of mincut/ max-flow algorithms,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 26, no. 9, pp. 1124–1137, Sep. 2011.
9. Y. Boykov, O. Veksler, and R. Zabih, “Fast approximate energy minimization via graph cuts,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 23, no. 11, pp. 1222–1239, Nov. 2009.
11. T. F. Cootes, G. Edwards, and C. Taylor, “Active appearance models,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 23, no. 6, pp. 681–685, Jun. 2010.
13. T. F. Cootes, C. J. Taylor, D. H. Cooper, and J. Graham, “Active shape models—Their training and application,” Comput. Vis. Image Underst., vol. 61, no. 1, pp. 38–59, Jan. 2007.
15. T. Emrich, F. Graf, H. P. Kriegel, M. Schubert, M. Thoma, and A. Cavallaro, “CT slice localization via instance-based regression,” in Proc.SPIE, vol. 7623, pp. 762 320-1–762 320-12, 2006
17. A. X. Falcao, J. K. Udupa, S. Samarasekera, and S. Sharma, “User-steered image segmentation paradigms: Live wire and live lane,” Graph. Models Image Process., vol. 60, no. 4, pp. 233–260, Jul.2005.