Segmentation and interpretation using multiple physical hypotheses of image formation
Steven A. Shafer, Bruce Maxwell · 1996
One of the first, and most important tasks in single image analysis is segmentation: finding groups of pixels in an image that belong together. Physics-based segmentation algorithms are based upon identifying coherent regions of an image according to a model of object appearance. This work challenges considers multiple physical hypotheses for simple image regions. For each initial region, the framework proposes a set of hypotheses, each of which specifically models the illumination, reflectance, and shape of the 3-D patch which caused that region. Each hypothesis represents a distinct, plausible explanation for the color and intensity variation of that patch. The framework proposes comparing hypotheses of adjacent patches for similarity and merging them when appropriate, resulting in more global hypotheses which group elementary regions that are part of the same surface. A physical analysis of the hypotheses reveals strong constraints on hypothesis compatibility which significantly reduces the space of possible image interpretations and specifies which hypothesis pairs should be tested for compatibility. A consequence of this framework is a new approach to segmenting complex scenes into regions corresponding to coherent surfaces rather than merely regions of similar color. The second part of this work presents an implementation of this new approach and example segmentations of scenes containing multi-colored piece-wise uniform objects. The algorithm contains four phases. The first phase segments an image based upon normalized color. The algorithm then attaches a list of potential explanations, or hypotheses to each initial region. The second phase examines adjacent hypotheses for compatibility. This work explores two methods of compatibility testing. The first is direct comparison, which estimates the shape, illumination, and material properties of each region and directly compares their compatibility. The second method uses weak tests of compatibility, which compare physical characteristics that must be compatible if two hypotheses are part of the same surface, but which are not necessarily incompatible between different objects. By using a number of these necessary, but not sufficient tests the algorithm rules out most incompatible hypothesis pairs. The third phase builds a hypothesis graph from the results of the analysis. Each hypothesis is a node in the graph, and edges contain information about the cost of merging adjacent hypotheses. The fourth phase then extracts segmentations from the hypothesis graph and rank-orders them. Each segmentation contains exactly one hypothesis from each region and provides a potential physical interpretation of the scene. This work explores the issue of preferring certain hypotheses over others depending on their compatibility with the image data. It also shows how the algorithm can expand to handle scenes of greater complexity by expanding the initial list of hypotheses and developing new tests of hypothesis compatibility. (Abstract shortened by UMI.)