Multi-Scale Contour Segmentation
Effective local segmentation of contours is an important problem which arises in occluded object recognition as well as other areas. For any recognition system to perform well, the segmentation procedure used must be robust in presence of noise and local distortions of shape. Previous approaches to this problem have attempted to discover a natural scale to be used for feature extraction. However, this approach is misguided since on a free-form contour, features usually exist at different scales. If the scale chosen is too small, the segmentation will be affected by noise and local distortions of shape, and if it is too large, important/useful structure on the contour may be lost. The segmentation technique described here is a multi-scale one and is based on the Curvature Scale Space image. Consider the following contour:
The CSS image of a 2-D contour such as this one is a multi-scale organization of the inflection points (or curvature zero-crossing points) of the contour as it evolves. Intuitively, curvature is a local measure of how fast a planar contour is turning. Contour evolution is achieved by first parametrizing using arclength. This involves sampling the contour at equal intervals and recording the 2-D coordinates of each sampled point. The result is a set of 2 coordinate functions (of arclength) which are then convolved with a Gaussian filter of increasing width or standard deviation. Next step is to compute curvature on each smoothed contour. As a result, curvature zero-crossing points can be recovered and mapped to the CSS image in which the horizontal axis represents the arclength parameter on the original contour, and the vertical axis represents the standard deviation of the Gaussian filter. The CSS image of the Panda looks like the following:
The basic idea behind multi-scale contour segmentation is to recover curvature zero-crossing segments from the input contour at multiple scales as long as the segments are not repeated. A curvature zero-crossing segment is defined as a segment of the input contour between two consecutive curvature zero-crossing points (referred to as endpoints). The first step is to recover all curvature zero-crossing segments on the input contour at a small scale, and to place them in a segment-list. The following figure shows all such segments for the Panda:
The next step is to recover all curvature zero-crossing segments at the next higher scale, and to compare them to the ones that exist in the segment-list. If a new segment is discovered (its endpoints must be different from those of existing segments), it is added to the segment-list. In doing so, movement of curvature zero-crossings across scales must be accomodated. This step is repeated until the contour becomes simple and convex. The following figure shows the curvature zero-crossing segments recovered from the Panda at higher scales:
This multi-scale segmentation technique proves to be very robust when used in conjunction with a silhouette-based occluded object recognition system described in the next section. Further details can be found in published papers (such as Vision Interface'97, Scale-Space'97 and ACCV'98).
Silhouette-Based Object Recognition with Occlusion
This section describes a robust system for object recognition with occlusion based on the multi-scale segmentation technique described in the previous section. About 15 free-form 3-D objects were used in the experiments. No constraints were imposed on object shapes. It was assumed that objects rested on a flat surface, and that the camera was looking straight down at them. As a result, each object can be modelled using a limited number of classes of 2-D contours such that all the contours in each class are related by a similarity transform. The recognition system was implemented in C and consisted of the following stages:
- 1. Processing of the Input Image
- Each input image was processed to recover the outer boundary of the cluster of objects present in the image.
- 2. Multi-Scale Segmentation of image and model contours
- The multi-scale segmentation technique described in the previous section was applied to all model contours as well as the image contours. About 10-20 segments were extracted from each model contour, and about 20-40 segments were extracted from each image contour.
- 3. Candidate Generation and Filtering
- All possible pairs of model and image contour segments must be considered. Object indexing is employed to render the initial search more efficient. Segment pairs are registered to find the best matching ones which are selected for the next stage.
- 4. Candidate Merging
- It is possible for the visible boundary of an object to be divided into several segments. As a result, neighboring segments that are compatible are merged to create longer segments.
- 5. Candidate Extention
- In general, the intersection point of two object boundaries gives rise to a corner on the corresponding image contour. Surviving candidates are extended to nearby corners as long as an acceptable fit can be observed.
- 6. Candidate Grouping
- Due to occlusion, an object may appear as two or more disjoint components in the input image. As a result, compatible but disjoint candidates are grouped in this stage.
- 7. Candidate Selection
- In the final stage, the candidates with the best support are selected. A candidate's support depends on its quality of fit as well as the length of its corresponding segments. Candidate selection continues until all data is accounted for.
The segmentation of that image yielded the following contour:
which was correctly recognized by the system. The result is shown in the following figure. Relevant model contours have been registered to the image contour.
Further details can be found in published papers (such as ECCV'96 and MV&A 1997).
F.Mokhtarian@ee.surrey.ac.uk Dec 2003