|Home | About | Journals | Submit | Contact Us | Français|
Active contours are very popular tools for video tracking and image segmentation. Parameterized contours are used due to their fast evolution and have become the method of choice in the Sobolev context. Unfortunately, these contours are not easily adaptable to topological changes, and they may sometimes develop undesirable loops, resulting in erroneous results. To solve such topological problems, one needs an algorithm for contour self-crossing detection. We propose a simple methodology via simple techniques from differential topology. The detection is accomplished by inspecting the total net change of a given contour’s angle, without point sorting and plane sweeping. We discuss the efficient implementation of the algorithm. We also provide algorithms for locating crossings by angle considerations and by plotting the four-connected lines between the discrete contour points. The proposed algorithms can be added to any parametric active-contour model. We show examples of successful tracking in real-world video sequences by Sobolev active contours and the proposed algorithms and provide ideas for further research.
Active contours (snakes) are widely used in segmentation and tracking. The development of this field began with the seminal paper by Kass et al. . Snakes have applications in various fields, from medical imaging to surveillance. The purpose of snakes is to define an object’s outline in the tested image, i.e., by minimizing an energy associated with different object properties (e.g., average intensity value), and intrinsic curve properties (e.g., smoothness).
Parametric snakes are given as curves that explicitly provide the (x,y) coordinates of the given points on the given contour (these are called snaxels). The advantage of such a parametrization is in the fast evolution of the snake and, in fact, has dominated the tracking literature . The problem that occurs with parametric snakes, particularly when used to segment noisy images, is the development of false loops [see Fig. 1(c)–(e)]. If the snakes are region based (e.g., in  and ), then these loops can cause a divergence of the snake since they change the normal direction and thus the inside and outside of the closed contour. In other cases, the false loops may catch irrelevant features for tracking. This brings us to the importance of the contour self-crossing detection and of the consequent topological changes (loop elimination or snake splitting).
Currently, there are five main approaches to tackle the problem of self-crossing. First, level sets are perhaps the most popular approach. The curve is defined by zero level set of the graph of surface, usually starting with the distance function (see  and  the references therein). With level sets, the topological changes are automatically managed, and the problem of self-crossing does not occur. In general, the snake evolution in the level-set framework is slower than the evolution of parametric snake models. Moreover, automatic topological changes may be less appropriate for tracking, where a single target may be unintentionally split or two distinct targets may have merged.
A second popular class of approaches for detection and location of the crossing points is based on the classical Bentley–Ottmann line segment intersection algorithm in computational geometry. These approaches are reviewed in [6, Ch. 2] and . The general idea of this type of techniques is to sort the snake’s points by the x-coordinate in ascending order and to employ the plane sweep algorithm to detect the overlapping x and y projections of the segment pairs. The actual crossing is tested only if both x and y projections overlap. These algorithms are fast and efficient but are not simple to implement, partly due to the need of checking various special cases.
The third approach is grid based –. For easy collision and crossing detection, the motion of snake points can be restricted to the edges of the grid, as in , or one can inspect the crossings with a constant rectangular grid  or simplicial cell decomposition , . Unfortunately, these algorithms are not always able to detect all the crossings because of the discretization of the snaxel locations or the restrictions.
The next approach is perhaps the simplest. The idea is to complete the lines with additional points computed from linear interpolation between the snaxels, i.e., to complete the segments between the endpoints and to make the snake segments connected (continuous) on the given discrete grid . Then, all the points are plotted on a 2-D counter raster (matrix), where the crossing is detected and located if the points are plotted more than once to the same raster location. The obvious problems with this method are explained in . The method cannot provide sub-pixel accuracy in crossing location because of the discretization of snaxel locations. In addition, by the nature of the interpolation algorithm, false positive and false negative detections may frequently occur (see Fig. 4). The proposal to use double-width lines makes the problem of false positives much worse, and the additional computational time for the direct checking of these pseudocrossings virtually eliminates all the advantages of the algorithm.
The last approach is based on an idea of Kass et al. . Here, one employs a “repulsion force, ” which forces the snaxels not to be too close to one another. This force can be incorporated into the energy minimization framework. Ivins and Porrill  propose to compute the repulsion force from the tension, stiffness, and reversed pressure. Unfortunately, introducing the new repulsion force will not always prevent crossings; therefore, an additional self-crossing check may be needed. In addition, introducing the repulsive force affects the snake dynamics and convergence properties, which may not be desirable.
It is important to note that while self-crossing does not occur very frequently, nevertheless, its appearance may ruin the tracking of a target in a given scenario. Consequently, our goal is to effectively detect the existence of self-crossing as quickly as possible, and when it exists, to locate the crossing points, and to apply the appropriate topological change to the snake (loop removing or snake splitting). Since the problem of detection is simpler than the simultaneous detection and location of the crossing (as in the approaches described earlier), this problem can be solved more efficiently with regard to space usage and run time. We propose two algorithms: The first is for an efficient self-crossing detection, and the second is for the computation of crossing locations.
The first algorithm should be run for each snake iteration, without computing the crossing segments and the crossing point. We base our idea on the Hopf turning-number topological theorem [13, p.162], which states that the total net angle change of a simple continuous closed curve (without self-crossings) can be 360° for a clockwise (CW) curve and −360° for a counterclockwise (CCW) curve, as explained in Section II. The same is true for simple polygons.
In Section II-B, we show that an explicit angle computation is unnecessary and may be replaced by a more efficient algorithm that counts the number of quadrants that the curve has passed in turn. In Section II-C, we investigate the rare cases when our detection algorithm may fail, and propose a possible solution.
The second algorithm solves the problem of crossing localization. We propose a particular line completion algorithm for that purpose. In Section II-D, we describe our novel interpolation scheme. The proposed algorithm provides four-connected segments (each snake point has two neighbors, from the left, right, top, or down), which totally eliminates the false negatives without a significant increase in false positives. The crossing points are computed only if a self-crossing is detected (Sections II-C and II-D). The self-crossing can be found by checking the appropriate segments for crossing, which can be accomplished by solving certain simultaneous parametric equations  or by testing on which side of the given segment lies the endpoints of the second segment, as explained in the Section II-D. In case of self-crossing, the snake can be split by a simple method described in  or  (see Section II-E).
We have successfully tested our approach on numerous real-world videos. We have used region-based Sobolev snakes  with the Chan–Vese energy . Representative results and the discussion are provided in Section III. Section IV summarizes this and proposes possible further research.
In this section, we propose an easily implementable algorithm for detecting active-contour self-crossing, which is based on the concept of turning number.
Let α : → 2 be a regular closed curve. The turning number of α, i.e., Turn(α), is the total signed curvature of α divided by 360° [13, p.156]. It can be shown that, for closed curves, the number Turn(α) is an integer, and it is equivalent to the topological rotation index [13, p.160]. Intuitively, Turn(α) is the number of full CCW turns until the curve returns to the (arbitrarily) chosen initial point. If the turns are CW, then Turn(α) is negative. Similarly, the total curvature is the net change of unwrapped angle Δϕ (see Fig. 1).
For convenience, we define the turning direction by
We now state the key result due to Hopf [13, p.162].
The turning number of a simple closed curve α (without self-crossings) equals to dir(α).
As we have mentioned earlier, this theorem can be restated in terms of the total net angle change of 360°·dir(α). In particular, this theorem is true for any simple closed polygon, as is typically given with the snake representation. In the following subsection, we use this observation to formulate a straightforward algorithm for the detection of crossings.
Suppose the parametric snake is defined by its point coordinates: pi = (xi, yi) i = 1,…, n, where pn+1 = p1. The corresponding segment between pi and pi+1 is denoted by si (see Fig. 2).
The unwrapped angle of segment si is denoted by ϕi as follows:
The angle is defined up to 360°; therefore, one should note the meaning of the unwrapped angle: If the angle difference between the consecutive segments is larger than 180°, then multiples of +360° or −360° should be added to ϕ. As a result, the angle ϕ can get any real value and is not bounded by ±180°.
The following algorithm allows one to check if self-crossings exist, without actual computing the crossing points. The algorithm is based on Theorem 1 for polygons, and it should be run for each snake iteration.
|Input : snaxels pi|
|Compute the angle ϕ by (2)|
|if |ϕ(n) − ϕ(1) −360° · dir| > 180° then|
|report that crossing is detected|
In most practical situations, the proposed algorithm robustly and efficiently detects the existence of self-crossings. The special cases when this algorithm fails [an even number of crossings with double twist, as in Fig. 3, and an equal number of inward and outward loops, as in Fig. 1(e)] are explored in Section II-C, and a solution for these cases is proposed.
The next subsection describes a more efficient version of the self-crossing detection algorithm.
The next algorithm is based on the observation that any simple closed curve is topologically equivalent to a square. Accordingly, the turning number may be computed by considering how many quadrants the curve has passed in turn, or how many 90° turns the curve performed along the way. If this number is not 4, then the curve is not simple. The increments in the number of quadrants may be computed by inspecting the signs of Δyi = yi+1 − yi and Δxi = xi+1 − xi as described in the following.
Let (+,+)(i) denote sign(Δxi) = +1 and sign(Δyi) = +1, (+,−)(i) denote sign(Δxi) = +1 and sign(Δyi) = −1, (−,+)(i) denote sign(Δxi) = −1 and sign(Δyi) = +1, and (−, −)(i) denote sign(Δxi) = −1 and sign(Δyi) = −1.
The increment in the number of quadrants is summarized in the Table I.
The sign of 2 on the second diagonal (for a very sharp angle change) is computed by inspecting the slopes of the consecutive segments si and si+1 as follows:
where ε is a small number that is added to prevent the division by zero.
All the values in Table I (except the second diagonal) may be computed by the following formula:
Note that sign(ΔyiΔxi+1) is mathematically equivalent to a binary XOR operation and can be efficiently implemented.
We can now describe our algorithm as follows.
|Input : snaxels pi|
|q0 ← 0|
|For i = 1 to n|
|Compute Δq by (4)|
|If |Δq| = 2 then|
|qi ← qi−1 + sign(Slopei − Slopei+1)Δq|
|qi ← qi−1 + Δq|
|If qn ≠ 4 · dir then|
|report that crossing is detected|
As we stated earlier, for an even number of self-crossings, if double twisting occurs (see Figs. 1(e) and and3),3), our algorithm will not find the crossing. The algorithm for detecting self-crossings in these cases is more computationally demanding but can be still accomplished by exploring the snake segment angles.
The test for self-crossing is based on the following important observations.
All five tests (or relevant portions of them) can be used in the proposed order to rule out the segments that cannot cross. All the proposed conditions are necessary but not sufficient; thus, the segment pairs that passed all the proposed tests should be directly checked for crossing by solving simultaneous equations , or explicitly, for the segments si and sj, if
then the segments are crossed.
It is important to note that if one does not halt the algorithm after the first crossing, then all the crossings may be found in this manner. Another possibility for self-crossing localization is to use the algorithm proposed in the following subsection. This algorithm is simple and fast but cannot achieve subpixel accuracy.
In addition to the known methods for detection and computation of crossing points outlined in Section I and the method described in the previous subsection, we propose another approximate method that allows finding the location of all the crossing points by four-connected linear interpolation of the snake segments. The idea is to connect the sequential but distant points of the given snake with additional points in between, and if the added points will fall on the same grid cell, then a crossing is located. All the points are registered in a 2-D raster accumulator. Algorithms of simple linear interpolation (single- and double-width lines plotted on a raster) are prone to false positives and false negatives, as shown in Fig. 4.
It is clear in Fig. 4 that the reason for the false negative is the two crossing lines that are not four connected (vertically or horizontally connected). Thus, we propose a simple algorithm for four-connected line interpolation between the two given snake points as follows:
|Input : rounded to the closest integer segment|
|endpoint (x1,y1) and (x2,y2)|
|if x1 = x2 then draw a vertical line|
|Slope = |(y2 − y1)/(x2 − x1)||
|r ← Slope|
|Repeat until the (x2, y2) points is reached|
|make [r] steps in sign(y2 − y1) y direction|
|(i.e., move 1 point in signed y direction)|
|make 1 step in sign(x2 − x1) x direction|
|r ← − [r] + Slope|
When a self-crossing is detected and located, the snake will generally go through a topological change (splitting into two snakes or removing the loop). Different methods for topological changes have been proposed earlier –, . In this paper, we use the simplest splitting proposed in . If the segments si : pi → pi+1 and sj : pj → pj+1 are crossed, then we remove these segments and add the segments between pi → pj+1 and pj → pi+1 (see Fig. 3). If some loops are removed, e.g., for single-target tracking, the shortest loops are eliminated, and the removed points are distributed in the most sparse regions of the remaining loop.
Additional cues about the loops that should be removed can also be extracted from the angle information. If we suppose that the direction dir(α) does not change through tracking or segmentation, we can remove the loops with the wrong direction.
In this section, we show how the proposed algorithms improved the tracking with parametric Sobolev snakes  with the Chan–Vese energy functional . The snake was used to track a single target in video sequences with a constant-velocity dynamic model (current frame initialization contour is a translated version of the previous frame result). The algorithms have been implemented in Matlab.
We have chosen two representative videos. The first is the well-known “Walking in Finland” sequence from the University of Oulu. This sequence consists of 22 frames and is frequently used to test visual trackers. We run the algorithm of the Sobolev snake with the same parameters (λ = 1, step size dt = 1, six iterations per frame), with and without the loop detection and elimination algorithms. The target is manually selected in the first frame. For the following frames, the predicted in the previous frame result is used to initialize the snake. The results are shown in Fig. 5.
Without the proposed algorithm, in frame 3, the snake develops a loop, which prevents further convergence of the snake around the target. When the developing loop was detected via our self-crossing detection algorithm, it was removed, and the tracking was successful.
The second sequence, i.e., “The Hand, ” is filmed by infrared (IR) camera, and has 1050 frames. Again, only with the self-crossing detection algorithm, the Sobolev snake managed to track the hand in the entire sequence. The results of tracking are shown in Fig. 6.
The additional time to detect and remove the loops for all the tested sequences was less than 2%, compared with the running time of the Sobolev snake algorithm.
Some more experiments illustrating our methodology may be found on the website: http://www.youtube.com/playlist?list=PL0E921BB9455C23B3. The failure scenarios for these videos (without our algorithm) are shown in the top row in Fig. 7, and the success scenarios (with the self-crossing detection and elimination) are show at the bottom row of this figure.
We have proposed a fast and simple approach to snake self-crossing detection and localization. The algorithms can be adapted to any type of parametric snakes, which is defined by snaxel coordinates, and do not restrict the snake’s motion and evolution in any manner.
The proposed crossing-point computation algorithm uses rounded integer values for snaxels and is appropriate in cases where no subpixel accuracy is needed. Its implementation is fast and efficient, with a low number of false positives (that can be easily rejected).
We have shown that the proposed algorithm can be used for tracking real-world scenarios and helps to prevent the divergence of the active contour from the target of interest. We believe that future research of angle dependencies for an even number of self-crossings will simplify the algorithm for the special cases discussed in this paper. The idea of Perrin et al.  of using the assumption that, initially, the contour is simple and that each moved snaxel should be tested only if the simplicity condition is violated should be applicable to our framework by testing the changes in the angles of each moved point. Additional improvements may be done by considering the work of Whitney and Graustein [13, p.164] and the connection of the right-hand and left-hand crossings with the total angular change.
This work was supported in part by grants from AFOSR and ARO. This project was also supported by the National Center for Research Resources under Grant P41-RR-013218 and the National Institute of Biomedical Imaging and Bioengineering under Grant P41-EB-015902 of the National Institutes of Health. This work is part of the National Alliance for Medical Image Computing (NAMIC), funded by the National Institutes of Health through the NIH Roadmap for Medical Research under Grant U54 EB005149. Information on the National Centers for Biomedical Computing can be obtained from http://nihroadmap.nih.gov/bioinformatics. The associate editor coordinating the review of this manuscript and approving it for publication was Prof. Gang Hua.
Arie Nakhmani received the Ph.D. degree in electrical engineering from Technion–Israel Institute of Technology, Haifa, Israel, in 2011.
He is currently a Postdoctoral Researcher and a Lecturer with the Department of Electrical and Computer Engineering, Boston University, Boston, MA. His research interests include visual tracking, image segmentation, estimation, and robust control.
Allen Tannenbaum He is currently a faculty member with the Department of Electrical and Computer Engineering and Department of Biomedical Engineering, Boston University, Boston, MA, and the Department of Radiology/Wallace Cancer Center, University of Alabama at Birmingham, Birmingham. His research interests include medical imaging, control, image processing, and computer vision.
Color versions of one or more of the figures in this paper are available online at http://ieeexplore.ieee.org.
Arie Nakhmani, Department of Electrical Engineering, Technion, Haifa 32000, Israel. He is now with the Department of Electrical and Computer Engineering, Boston University, Boston, MA 02115 USA.
Allen Tannenbaum, Department of Electrical and Computer Engineering and Department of Biomedical Engineering, Boston University, Boston, MA 02115 USA, and is also with the Department of Radiology/Wallace Cancer Center, University of Alabama at Birmingham, Birmingham, AL 35294-1150.