IntroductionRelated WorkConstructing a Fragment Set (Fragment Extraction)Learning the Fragments Figure-Ground SegmentationDegree of CoverBorder ConsistencyDetermining the Figure-Ground SegmentationImage Segmentation by Covering FragmentsImproving the Figure-Ground Labeling of FragmentsResultsDiscussion and ConclusionsLearning to SegmentEran Borenstein and Shimon UllmanFaculty of Mathematics and Computer ScienceWeizmann Institute of ScienceRehovot, Israel 76100{eran.borenstein,shimon.ullman}@weizmann.ac.ilAbstract. We describe a new approach for learning to perform class-based segmentation using only unsegmented training examples. As inprevious methods, we first use training images to extract fragments thatcontain common object parts. We then show how these parts can besegmented into their figure and ground regions in an automatic learningprocess. This is in contrast with previous approaches, which requiredcomplete manual segmentation of the objects in the training examples.The figure-ground learning combines top-down and bottom-up processesand proceeds in two stages, an initial approximation followed by iterativerefinement. The initial approximation produces figure-ground labeling ofindividual image fragments using the unsegmented training images. Itis based on the fact that on average, points inside the object are cov-ered by more fragments than points outside it. The initial labeling isthen improved by an iterative refinement process, which converges inup to three steps. At each step, the figure-ground labeling of individualfragments produces a segmentation of complete objects in the trainingimages, which in turn induce a refined figure-ground labeling of the in-dividual fragments. In this manner, we obtain a scheme that starts fromunsegmented training images, learns the figure-ground labeling of imagefragments, and then uses this labeling to segment novel images. Our ex-periments demonstrate that the learned segmentation achieves the samelevel of accuracy as methods using manual segmentation of training im-ages, producing an automatic and robust top-down segmentation.1 IntroductionThe goal of figure-ground segmentation is to identify an object in the image andseparate it from the background. One approach to segmentation – the bottom-upapproach – is to first segment the image into regions and then identify the imageregions that correspond to a single object. The initial segmentation mainly relieson image-based criteria, such as the grey level or texture uniformity of imageregions, as well as the smoothness and continuity of bounding contours. Oneof the major shortcomings of the bottom-up approach is that an object may besegmented into multiple regions, some of which may incorrectly merge the objectThis research was supported in part by the Moross Laboratory at the WeizmannInstitute of Science.T. Pajdla and J. Matas (Eds.): ECCV 2004, LNCS 3023, pp. 315–328, 2004.c Springer-Verlag Berlin Heidelberg 2004316 E. Borenstein and S. Ullmanwith its background. These shortcomings as well as evidence from human vision[1,2] suggest that different classes of objects require different rules and criteriato achieve meaningful image segmentation. A complementary approach, calledtop-down segmentation, is therefore to use prior knowledge about the object athand such as its possible shape, color, texture and so on. The relative merits ofbottom-up and top-down approaches are illustrated in Fig. 1.A number of recent approaches have used fragments (or patches) to performobject detection and recognition [3,4,5,6]. Another recent work [7] has extendedthis fragment approach to segment and delineate the boundaries of objects fromcluttered backgrounds. The overall scheme of this segmentation approach, in-cluding the novel learning component developed in this paper, is illustratedschematically in Fig. 2. The first stage in this scheme is fragment extraction(F.E.), which uses unsegmented class and non-class training images to extractand store image fragments. These fragments represent local structure of commonobject parts (such as a nose, leg, neck region etc. for the class of horses) and areused as shape primitives. This stage applies previously developed methods forextracting such fragments, including [8,4,5]. In the detection and segmentationstage a novel class image is covered by a subset of the stored fragments. A criticalassumption is that the figure-ground segmentation of these covering fragmentsis already known, and consequently they induce figure-ground segmentation ofthe object. In the past, this figure-ground segmentation of the basic fragments,termed the fragment labeling stage (F.L.), was obtained manually. The focusof this paper is to extend this top-down approach by providing the capacity tolearn the segmentation scheme from unsegmented training images, and avoidingthe requirement for manual segmentation of the fragments.The underlying principle of our learning process is that class images areclassified according to their figure rather than background parts. While figureregions in a collection of class-image samples share common sub-parts, the back-ground regions are generally arbitrary and highly variable. Fragments are there-fore more likely to be detected on the figure region of a class image rather thanin the background. We use these fragments to estimate the variability of regionswithin sampled class images. This estimation is in turn applied to segment thefragments themselves into their figure and background parts.1.1 Related WorkAs mentioned, segmentation methods can be divided into bottom-up and top-down schemes. Bottom-up segmentation approaches use different image-baseduniformity criteria and search algorithms to find homogenous segments withinthe image. The approaches vary in the selected image-based similarity criteria,such as color uniformity, smoothness of bounding contours, texture etc. as wellas in their implementation.Top-down approaches that use class-based (or object-specific) criteria toachieve figure-ground segmentation include deformable templates [10], activeshape models (ASM) [11] and active contours (snakes) [12]. In the work on de-formable templates, the template is designed manually for each class of objects.Learning to Segment 317Fig. 1. Bottom-up and Top-down segmentation (two examples): Left – input images.Middle – state-of-the-art bottom-up segmentation ([9]). Each colored region (middle-left) represents a segment