Авторы: Wai-Pak Choi, Kin-Man Lam, Wan-Chi Siu
Snake is an active contour model for representing image contours. In this paper, we propose an efficient active contour model which can represent highly irregular boundaries. The algorithm includes an adaptive force along the contour, and adjusts the number of points for the snake according to the desired boundary. A better stopping criterion based on the area of a closed contour is devised. Furthermore, in this method, a contour can break automatically to represent the contours of multiple objects. Experiments show that this method can extract object’s boundaries accurately and efficiently. © 2000 Pattern Recognition Society. Published by Elsevier Science Ltd. All rights reserved.
Keywords: Retrieval system; Active contour model; Irregular boundary; Multiple object
Locating an object’s boundary is an important step for content-based retrieval systems [1]. Most of the systems use shape information for image query. An active contour model (snake) [2] has been successfully used in contour detection for object recognition, computer vision, computer graphics, and biomedical image processing. Based on the object’s boundary, its contents can then be extracted. Nevertheless, this active contour model has many limitations. Firstly, the initial contour should be close to the object, provided that the contour is in the effect of the image force. Secondly, the performance of the snake depends on the number of contour points, which is usually fixed. According to these reasons, the model is unable to represent irregular objects accurately. Besides, this method fails to extract the contours of multiple
objects. In real situations, an image may contain a number of objects which are relevant objects for retrieval.
In this paper, the original snake model is reviewed in Section 2. Our proposed adaptive snake model is presented in Section 3. Section 4 describes the contours representation for multiple objects by using the adaptive snake model. Experimental results are demonstrated in Section 5. Finally, conclusions are given in Section 6.
An active contour model (snake) [2] is an energy-minimizing spline, which can be operated under the influence of internal contour forces, image forces, and external constraint forces. A snake is represented as a parametric curve v(s) = [x(s), y(s)], where the arc length s is a parameter. An energy functional of the snake is defined as
Eint = Eimage + Econstraint
where Eint represents the internal energy of the contour due to bending or discontinuities, Eimage refers to the image forces, and Econstraint is the external constraint forces. The location of the snake corresponds to the local minima of the energy functional.
We have proposed the fast greedy algorithm [3], which is an iterative method for minimizing the energy functional. In order to locate the boundary of an object in an image, an accurate estimation of the initial position and the number of points of the snake is necessary. The initial snake is then drawn by image forces to the object’s boundary. However, the image force is effective only when the snake is placed near the edge. To attract the snake from a fairly large distance away from the edges, the image force is blurred by a 2-D Gaussian smoothing operator with a large window size. The window size is chosen to be 23 x 23. This allows the snake to move to the blurry energy functional and the blurring is then slowly reduced when the snake is close to the image. Nevertheless, for a highly irregular boundary, part of the snake may still be too far away from the desired boundary.
Cohen [4] proposed a balloons model for snake, but it only partially resolved the problems. It is difficult to locate concave parts of an object from outside. In view of such a limitation, Wong et al. [5] proposed a segmented snake which converts the global optimization of a closed snake curve into local optimization based on a number of open snake curves. A recursive split-and-merge procedure is then used to determine the final object contour. However, the method is computationally expensive.
In our proposed model, an adaptive force is introduced at a point of the snake whenever the image forces in its neighborhood are smaller than a threshold. In order to achieve an accurate representation of a boundary, the distances between adjacent points of the snake are kept close to a constant. Two processes, namely deletion and insertion, are introduced to change the number of points for the snake during the energy minimization process.
In our method, an adaptive force will be introduced at a point if its surrounding image forces are smaller than a threshold. If the noise in the surroundings of a point is less than the threshold, an adaptive force is created and the effect of the noise can be overcome. The direction of the force is defined to be perpendicular to the line joining its two adjacent points.
Considering a point Vt, the direction n of the force is defined as follows:
Vi+1-Vi-n
where n is the unit adaptive force. As the point is far away from the desired boundary, it is allowed to move with a larger step size in the direction as follows:
Vi =Vi + 3n
n • v = 0
where Vi is the new position of the point. In other words, the snake can move 3 steps in the direction of the normal force whenever the image forces are small. This can reduce the number of iterations required and speed up the whole process.
After determining the direction of the adaptive force, it can be observed that the points may move too close or too far away from each other. It has been shown that overshoot and undershoot problems in the concave region may occur. Wong et al. [5] proposed a segmented snake approach to determine the object contour, but the method is computationally expensive. Although this method can overcome the problem of overshoot and undershoot by using different normal forces in between the non-contour segments, it involves a number of calculations for each segment. Furthermore, a fixed number of snake points cannot represent the object accurately if the boundary of the object is highly irregular.
The above problems are solved in this paper by the deletion and insertion of snake points. The main idea of this method is to keep the distance between each point more constant. If the distances between adjacent points are small, a deletion process will be applied to avoid overshoot. If the distances between adjacent points are large, an insertion process will be applied such that the continuity of the snake can be maintained. The snake is constructed by using a doubly linked list structure so that
the deletion and insertion processes can be performed efficiently.
To achieve an accurate representation of a boundary and overcome the overshoot and undershoot problem, the number of points for the snake must be determined appropriately. As this number depends on the size and shape of the boundary, in the iterative process, two operations — deletion and insertion — are introduced to keep the distance between two points of the snake more constant.
In our method, if the distance of two adjacent points of a point, Vi, is less than a threshold or if the distance between the points, vt and vi+1, is less than another threshold, point vt is deleted, and vi-1 and vi+1 will then become adjacent points. When the distance between two adjacent points is larger than a threshold, an additional point will be inserted between them.
Suppose the distances d1 and d2 are defined as follows:
d1 = |vi + 1-vt | and d2 =|vi + 1-vi-1|,
then the criteria for these two operations are described as follows:
If d1 <t1 or d2 <t2, then delete vt
else if d1 > t3, then a new point u is inserted between vt and vi +1
where the new point, u = (vt + vi+1 )/2 and t1, t2, t3 are threshold values.
In the fast greedy algorithm, the iteration will be stopped if the number of points moved is less than a threshold
or if the number of iterations has reached a certain quantity. It is observed that, sometimes, the points of the snake shift along the boundary, and the contour only moves very slightly. However, as most of the points are moved, the iteration process will be continued. Other terminating criteria include the measurement of the difference between the lengths of the contour in the current and previous iterations and the measurement of the change of the energy per unit length of the contour in successive iterations. The limitations of the criterion are the incorrect detection of image with no object, inability to locate small objects, and poor stability. Wong et al. [6] have proposed a contour length criterion (CL-criterion) which can overcome the above limitations. The CL-criterion measures the rate of change of the normalized total length of a curve and possesses two properties: a two-phase convergence property and an averaging property. The two-phase convergence property can solve the problem of detecting a small object or no object. The averaging property can solve the stability problem by smoothing the contour lengths computed in successive iterations. In the method, however, it requires the contour lengths to be stored over the past 10 iterations for smoothing. Otherwise, the sudden increase and decrease of the rate of change of normalized total length may cause the spikes and valleys during the iterations. The instability problem is due to the space discretization of the evolution problem which is introduced by the oscillation of the snake points between the quantized steps. The plots of CL-criterion against the iteration without averaging and with averaging.
In our method, a new terminating criterion called contour area criterion (CA-criterion) is proposed, which makes use of the normalized total area to determine the convergence of the process.
Suppose that Ak is the area of the snake at the kth iteration. Then, the CA-criterion, yk, is defined as follows:
nk = Ak -Ak
The area of the snake Ak can be calculated by using the equation.
The adaptive snake model can be used to represent the contour of a single object. However, if there are more than one object in the image, the snake model must be modified such that it can determine the corresponding contour of each object. In Section 4.1, we will describe the determination of critical points where the snake is split and connected for multiple object representation. In Section 4.2, we will demonstrate the splitting and connecting process. Finally, the validation of each contour will be verified so that invalid contours are removed.
In order to determine which parts of a contour should be split to form two contours, the segments of the snake are classified into two types, contour segment and noncontour segment, which are determined by calculating the surrounding image forces along a segment. If the surrounding image forces of a point are smaller than a threshold, we define it as a non-contour point. Otherwise, it is defined as a contour point. A sequence of contour points or non-contour points forms a contour or non-contour segment. A critical point is defined as the end points of a contour segment which are adjacent to non-contour segments.
The CA-criterion exhibits a smoother and faster convergence than that of the CL-criterion. The CA-criterion also has better stability in convergence, as its fluctuation between successive iterations is much smaller than the CL-criterion without using any averaging. In addition, the calculation of area is simple and fast, while the CL-criterion requires computing square roots to obtain the length of each segment.
We can observe that the area of the object is bounded provided that its perimeter is convergent. If the perimeter is converged, then the area of the object will converge faster. Therefore, the use of area as a stopping criterion can give a better convergence.
If (E(vi)>Enoise,E(vi-1)
{C(x, y) | i = 0, 1, 2,... n-1},
where Ci is a critical point and n is the number of critical points. The number, n, is equal to zero or an even number for a closed-loop contour.
During the iteration process, each of the critical points will be checked in sequence. Pairs of the critical points will be marked as connected points where the splitting and connecting operations will be performed to form two contours.
With reference, the procedure to identify connected points is as follows:
Step 1: Set i = 0 as the starting critical point c.
Step 2: Set j = i + 1 for the other critical point ci.
Step 3: Compute the distance, dj, between the two critical points c and cj.
Step 4: If dt,j is less than a threshold, ci and Cj are marked as a pair of connected points.
Step 5: If j < n, then j = j + 2 and go to Step 3. Otherwise, go to Step 6.
Step 6: If i < n, then i = i + 1 and go to Step 2. Otherwise, go to Step 7.
Step 7: End.
Having searched the pairs of connected points, which are close to each other, the splitting and connecting operations are then performed. Suppose that a pair of the connected points is dened as follows:
S = {sk = (v;, Vj) | i < j < n, k < m},
With the above processes, new snakes may be generated. However, some of the snakes may be invalid, as illustrated in Fig. 4. The invalid contour will grow until it touches the edges in the image. This kind of contour can be identi"ed by calculating its enclosed area.
If the points of a snake collapse and meet each other, the area enclosed by the snake will be zero. If the snake grows in a reverse direction, its computed area will be negative. This signi"es that an invalid snake has been formed. In addition, a snake is also considered to be invalid if its number of points is less than a certain value (e.g. 5). The computed area for a contour is also used in the terminating criterion in the iteration process. As described in Section 3.4, this is a better terminating criterion than that based on length measurement.
where sk is the kth pair of connected points, n is the number of snake points, and m is the number of connected pairs. The transition from contour segment to noncontour segment occurs at the point vt, while an opposite transition happens at the point vj. Then, the procedure for the splitting and connecting operations is shown as follows:
Step 1: Set k= 0.
Step 2: Splitting process: the contour is broken between the points V; and vi+ 1 and between the points Vj and Vj-1.
Step 3: Connecting process: the contours between the points Vi and Vj and the points vi+1 and Vj+1 are connected. Two contours are, therefore, formed after this connection process.
Step 4: If k < m, then k = k + 1 and go to Step 2. Otherwise, go to Step 5.
Step 5: End.
In our algorithm, the snakes are initialized as a circle or a rectangle with an arbitrary number of points surrounding the desired objects. The inter-distances between two adjacent points are set to a constant. In the experiments, we compare the performance in contour representation of our new algorithm with that of the fast greedy algorithm. The performances based on the CL- and CA-criterion are also compared. Finally, the extractions of the boundaries of multiple objects are illustrated. The experiments were conducted on a Pentium II 400MHz PC.
There are shown the initial contours depict the signal contours using both the fast greedy algorithm and our new algorithm, respectively. It is obvious that the new algorithm can achieve an
accurate representation of the concave region of representation based on the CL- and CA-criterion are
a boundary, and keep the distances between adjacent very similar. However, the required number of iterations
points close to a constant. The performances in contour and runtimes are different, as shown in Table 1. The
Table 1
Comparison with CL- and CA-criterion
|
Penguins |
B-2 |
Pochacco | ||||
|
CL |
CA |
CL |
CA |
CL |
CA | |
|
Number of iterations |
75 |
72 |
47 |
43 |
41 |
39 |
|
Runtime (ms) |
118.5 |
111.6 |
56.4 |
50.8 |
68.5 |
63.6 |
|
Number of snake |
142 |
142 |
109 |
110 |
146 |
144 |
|
points |
142 |
142 |
109 |
110 |
146 |
144 |
CA-criterion results in a smoother convergence and can therefore make decision on stopping iteration more accurately.
In this paper, we have presented an active contour model which can locate highly irregular boundaries in an image. An adaptive force is applied when the image forces around a point are small and points on the snake can be deleted or inserted such that the distance between adjacent points can be kept more constant. An additional terminating criterion based on area is also proposed such that unnecessary iterations can be prevented. By identifying contour and non-contour segments in a snake, the algorithm can extract multiple objects in an image by the splitting and connecting processes. Experimental results show that the new algorithm can achieve a better contour representation with a required runtime similar to that of the fast greedy algorithm.
[1] C.L. Huang, D.H. Huang, A content-based image retrieval system, Image Vision Comput. 16 (1998) 149-163.
[2] M. Kass, A. Witkin, D. Terzopoulos, Snakes: active contour models, Int. J. Comput. Vision 9 (1988) 321-331.
[3] K.M. Lam, H. Yan, Fast greedy algorithm for active contours, Electron Lett. 30 (1) (1994) 21-22.
[4] L.D. Cohen, On active contour models and balloons, CVGIP, Image Understanding 53 (2) (1991) 211-218.
[5] Y.Y. Wong, P.C. Yuen, C.S. Tong, Segmented snake for contour detection, Pattern Recognition 31 (11) (1998) 1669-1679.
[6] Y.Y. Wong, P.C. Yuen, C.S. Tong, Contour length terminating criterion for snake model, Pattern Recognition 31 (5) (1998) 597-606.
About the Author—WAI-PAK CHOI received his B.Eng. Degree in Electronic Engineering from the City University of Hong Kong in 1992. He is now an MPhil student in the Department of Electronic and Information Engineering, The Hong Kong Polytechnic University. His research interests are in the areas of Image Processing and Pattern Recognition.
About the Author—KIN-MAN LAM received his Associateship of the Hong Kong Polytechnic University in electronic engineering in 1986 and the MSc degree in communication engineering from the Department of Electrical Engineering, Imperial College of Science, Technology and Medicine, England, in 1987. Then, he joined TechTrend E. & C. Ltd. as an Application Engineer working on micro-supercomputers and CAD/CAM. From 1990 to 1993, he was with the Department of Electronic Engineering at the Hong Kong Polytechnic University as a lecturer. In 1993, he undertook a Ph.D. degree in the Department of Electrical Engineering at the University of Sydney, Australia. He completed his Ph.D. studies in August 1996. He joined the Department of Electronic and Information Engineering, The Hong Kong Polytechnic University again as an Assistant Professor in October 1996, and was conferred the title of Associate Professor in February 1999. His current research interests include image processing, pattern recognition, video technology, and digital TV.
About the Author—WAN-CHISIU received the Associateship from The Hong Kong Polytechnic University (formerly called the Hong Kong Polytechnic), the MPhil degree from The Chinese University of Hong Kong and the PhD degree from Imperial College of Science, Technology and Medicine, London, in 1975, 1977 and 1984, respectively. He was with The Chinese University of Hong Kong between 1975 and 1980. He then joined The Hong Kong Polytechnic University as a Lecturer in 1980 and was Chair Professor and Associate Dean of Engineering Faculty between 1992 and 1994. Prof. Siu has been Chair Professor and Head of Department of Electronic and Information Engineering of the same university since 1994. Professor Siu has published over 180 research papers. His research interests include digital signal processing, fast computational algorithms, transforms, video coding, computational aspects of image processing and pattern recognition, and neural networks.
Professor Siu is a Member of the Editorial Board of the Journal of VLSI Signal Processing Systems for Signal, Image and Video Technology, and an overseas member of the Editorial Board of the IEE Review. He was a Guest Editor of the Special Issue on ISCAS’97 of the IEEE Transactions on Circuits and Systems, Pt.II, published in May 1998. He was also an Associate Editor of the IEEE Transactions on Circuits and Systems, Pt.II between 1995 and 1997. Professor Siu was the General Chairman of the International Symposium on Neural Networks, Image and Speech Processing (ISSIPNN’94), and a Co-Chair of the Technical Program Committee of the IEEE International Symposium on Circuits and Systems (ISCAS’97) which were held in Hong Kong in April 1994 and June 1997, respectively. Prof. Siu is the General Chair of the 2003 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP) which is to be held in Hong Kong. Between 1991 and 1995, Prof. Siu was a member of the Physical Sciences and Engineering Panel of the Research Grants Council (RGC), Hong Kong Government, and in 1994 he chaired the first Engineering and Information Technology Panel to assess the research quality of 19 Cost Centers (departments) from all universities in Hong Kong.