William Klippgen
"Region Competition: Unifying Snakes, Region Growing, Energy/Bayes/MDL for Multiband Image Segmentation" by Zhu, Lee and Yuille. ---------------------------------------------------------------------- By using a method called "region competition", this paper suggests that existing techniques such as snake/ballon models, region growing and Bayes/MDl can be unified within a statistical framework that makes use of each method's advantages. Simply explained, the method lets pixels in a number of regions compete for ownership of pixels along their boundaries. By using statistical properties ranging from mean pixel values up to complex probability distributions of pixels, the likelihood for membership in regions can be decided. In case more complicated statistical analysis has to be performed, the paper suggest to use a window of m pixels around each boundary point. The window size must be kept small, however, to avoid loosing to much precision. Initially, the "seeds" that are points in the image that should lie within a certain probability distribution family, will sometime be hypothezised as being on the border of two distributions. The proposed method works well, even if such "bad" seeds are given at the start. As long as all the probability models assumed to exist for all region of the image is known to the region competition algorithm, the homogenous regions within a given picture will be found. I am fascinated by the generalization proposed in this article, especially as the probablility models are being used for color and texture. The authors are currently working on combining cues from the different models to gain better detection. "Markov Random Field Models for Unsupervised Segmentation of Textured Colour Images" by Panjwani and Healey. --------------------------------------------------------------------- By using Markov random field models for color textures, this approach looks at the spatial interaction within the color planes and interaction between them. The stepwise final merging is based on optimizing a conditional pseudolikelihood of the image. The conditional pseudolikelihood is a sum of all conditional probability densities for each pixel in the current image. This probability density is measured by how a given pixel's value is likely, given its neighbours, based on the various probability functions for the various regions. By optimizing the sum of all likelihoods, a steady progress towards a correct segmentations is assumed.
Lars Liden
"Markov Random Field Models for Unsupervised Segmentation of Textured Color Images" Panjwani & Healey Goal: Look at developing an unsupervised segmentation process for textured color images with no a priori knowledge of the textures. The Model: Gaussian Markov Random Field Model Model color textures by looking at spatial interaction: Within Plane. each of three color planes (RGB) Between color planes. Each component of the RGB vector at a location is represented as a linear combination of the color components of the neighbors and additive noise. Parameter Estimation: Use maximum likelihood method The Segmentation algorithm (3 parts): Region Splitting Phase - ensures initial images is small enough to fall within a single textured region in the image Conservative Merging Process - Locally merges similar adjacent regions Stepwise Optimal Merging - Iteratively processes optimal merges until a stopping criteria is met Region Splitting: Input image is first divided into a number of square blocks Each block is tested for uniformity of non-uniformity - First broken into four sub-blocks - The block is assumed to be uniform if the estimated color mean and estimated covariance matrix differs from each of the sub-blocks by some threshold Uniform block are left as-is, non-uniform block are broken up The process is repeated until a minimum block size is reached Result is the image is divided into uniform segments Agglomerative Hierarchical Clustering The ratio of the log of the pseudolikelihood of an block before and after a merge is used to decide whether to perform a merge Note that the merging of regions corresponding to different textures results in a large decrease in the likelyhood of an image and a corresponding large value for the pseudolikelyhood ratio (see P. 942 for equation for pseudolikelihood) Conservative Merging To criteria are used: - The color mean vector and covariance matrix for adjacent region must be below a threshold vector - The pseudolikelihood ratio for the merge must be less than a threshold The process is repeated until every possible new merge does not satisfy the merging criteria. Stepwise Optimal Merging At each step, find the pair of adjacent cluster whose merger would decrease the conditional pseudolikelihood as little as possible Assures that at each iteration the algorithm selects the best possible merge Stopping Criterion: Stop merging if the pseudolikelyhood ratio corresponding to a new merge is large compared to the pseudolikelihood ratio for the last merge. This is likely to happen when dissimilar textures start to be merged Comments: (+) Particularly well suited for natural scenes (a particularly hard problem) (-) Seems to be very computationally expensive involving estimation of a large number of parameters (12 within-plane parameters and 24 across-plane parameters for EACH textured region) Although segmentation is "unsupervised" it doesn't seem like there is an automatic way to choose good thresholds. It seems like the optimal threshold will vary depending on the texture density within an image. Authors point out that if an image consists of many small regions with different textures the algorithm is more sensitive to the choice of threshold Seems to require a priori knowledge of image contents, and possibility even several tries as segmentation to find the best thresholds "Region Competition: Unifying Snakes, Region Growing, Energy/Bayes/MDL for Multi-ban Image Segmentation." Zhu, Lee & Yuille This paper was a bit frustrating in that it assumed prior knowledge of the various image segmentation methods captured by this common statistical framework. It wouldn't have been so bad if the authors had bothered to define all their variables, but in many cases, they left the reader hanging, making it difficult to work through the computations. I have two main comments. First, in the examples, the authors mentioned that after initial convergence the regions created by bad seeds are removed by merging them with adjacent regions after which computation proceeds until it once again converges. What they don't explain is how this procedure is determined. They vaguely state that pairs which cause the energy function to decrease the most are merged, but what determines how many regions will be merged? This would seem to require some knowledge of the "right segmentation" so to speak. Are they using and energy threshold to determine when to stop merging? Note in the example of the human figure (6f), the author's also vaguely mention showing results after "spreading additional seeds". I was a little bothered by the fact that they didn't explain this in more detail. Did they selectively decide where to add more seeds in the image to improve segmentation? If so this seems rather a bogus final result. Secondly, I wanted to comment that this method seems vulnerable to different scales within the image. As pointed out by the authors, the eyes and mouth in the image are merged into the face region. This would seem to be true of any smaller scale feature in an image - that it will be treated as noise. As long as regions share similar scale of features, this method seems to work fairly well. However, unlike GMRF, it doesn't seem to be able adjust for the level of detail within an area.
Gregory Ganarz
In "Region Competition", S.C. Zhu et al. present an algorithm for image segmentation which combines the snake/balloon and region growing approaches to segmentation. This approach suffers from a dependence on initial seed choice. Also, by only partitioning the image into subregions with homogeneous properties, the algorithm is unable to link similar regions which have dissimilar regions interposed between them, or regions which are dissimilar, but are part of the same object. As an example, consider: OO **********OO****** *********OO******* ********OO******** OO The above image would be segmented into three regions by the "region competition" algorithm, yet humans generally perceive only two objects (a rectangle composed of *'s, with an occluding bar composed of O's on top of it. Though the algorithm might "know" that the left and right regions of *'s are the same based on their similar texture (*'s), it would introduce two new borders, which should be assigned to the O bar, and not the * regions. ----------------------------------------------------------------------------- In "Markov Random Field Models for Unsupervised Segmentation of Textured Color Images", Panjwani and Healey present an unsupervised segmentation algorithm for color textures. Based on Markov models, the algorithm describes "color texture in terms of the statistical dependence of the RGB vector measured at a pixel on the RGB values measured at neighboring pixels." p. 939. This algorithm suffers from the assumption that pixels are the relevant units to base a segmentation on. In some situtations, high level groupings may provide the basis for segmentation. By choosing the smallest scale availible for units, the Panjwani algorithms is computationally very expensive.
Shrenik Daftary
Throughout this course, many of the papers that we have covered have assumed some type of segmentation algorithm or have given an inadequate method to segment images. The two papers this week provide methods to actually segment images with seemingly adequate results. Synopsis of "Markov Random Field Models for Unsupervised Segmentation of Textured Color Images" by Panjwani and Healey In this paper an automated segmentation technique is presented that relies on numerous properties of the image, but concentrates on the red, green, and blue vectors of each pixel. Part of the problem for the technique presented in this paper are its reliance on color for appropriate segmentation, because many of the objects that may need to be found could be multicolored, and these variations in color may arbitrarily be segmented apart from each other. This issue could be addressed by an additional level of processing that rejoins parts of an image that are from the same object. The method presented also relied on models that are based on spatial interaction between the three color panes. A method to represent the spatial interaction of pixel is presented based on the mean values for the R,G,B panes, and the actual value at the current pixel point. Next parameter estimation techniques is presented in terms of maximum likelihood methods. The segmentation algorithm involves the simple process of creating a conservative merge. Next regions that are similar to each other are joined. Next a process is applied to the image to form uniform image segments, which can be divided into 4x4 pixels. This allows differently textured portions of the image to be separated from each other in most cases. The actual clustering begins by using a distance function based on the pseudolikelihood of the image with the merging of the segments and before the merging. Other merging techniques are presented which rely on the distance between the two segments, in which if the distance is below a threshold the images are joined. Finally stepwise optimal merging completes the segmentation process. The pseudolikelihood ratio is calculated for each region and if the difference is greater than a threshold the clustering is stopped otherwise the regions are joined. Although the images were difficult to see, since they were apparently in color, the technique seemed to function well in the cases that were presented. However the color was fairly constant for each of the segmented regions, and the technique would probably fail in cases where wide stripes run across the object. Another problem is that the system is not scale invariant, since the initial segmentation relies on the division of the object into minimally 4x4 segments. Synopsis of "Region Competition: Unifying Snakes, Region Growing, Energy/Bayes/MDL for Multi-band Image Segmentation" by Zhu, Lee and Yuille This paper attempts to present the best of different image segmenting techniques to obtain better segmentation. The first technique that they present is the snake technique, which attempts to form a closed boundary of a region. This is improved by the forming of a balloon contour, which pushes the initial contour out and smooths the contour. Techniques to region merge, and grow are presented based on the Fisher distance being less than a threshold. The other technique that this paper relies on is the use of Bayes, and minimum description length (MDL). The technique is first described for grey scale images divided into homogenous regions. Homogenous means that the distribution created by the image is consistent with a prespecified pdf (Gaussian is considered) that is different for each region in the image. Region segmentation occurs by the competition among separate regions for pixels adjacent to them. Several examples are presented with different seeds and the growth of the seeds to either bigger regions or to nothing after several iterations. This method worked well in the cases presented, but in many of the cases relied on several iterations. It functioned well with a textured object. Problems with this technique may include functioning in situations where the object is partially occluded completely in one direction for perhaps two pixels. This paper may also have difficulty dealing with multicolored objects; and objects that have very similar colors. Its functioning may be modified though by using a different function with skewed probabilities though.
John Petry
REGION COMPETITION: UNIFYING SNAKES, REGION GROWING, ENERGY/BAYES/MDL FOR _________________________________________________________________________ MULTI-BAND IMAGE SEGMENTATION, by Zhu, Lee and Yuille _____________________________ Zhu et al present a good method for combining two types of segmentation measures -- local connectivity measures for use near boundary points, and general measures within regions. Theirs is an iterative approach, in which regions compete for pixels and can lose them to neighboring regions if the pixel better fits the profile of the neighboring region. The test can be done with a single equation which considers both the probability measure for boundary pixels and grey-level tests for interior pixels. The boundary tests include use of a small window around the pixel to average out noise effects. The authors show some very good demonstrations, particularly the fact that the initial region seeds need not be well positioned in order for the code to converge on a good solution. I had several problems with the approach, though, and I'm not sure if they're minor details which are easily handled, or more major problems which the authors' glanced over: (1) They do not discuss region splitting, only merging. If a region contains no seeds to begin with, it's not clear to me that it will be located as a separate entity. (I assume this is easy to handle, but I may be wrong). This is related to the problem that they seem to require at least as many seeds to begin as there are final regions. This is a poor assumption in an unsupervised system. The alternative is to plant many seeds, but that may cause the code to slow down (consider the limit of one seed per pixel, or more likely one centered in every 3x3 block, for instance). (2) The number of iterations required is large -- about 100 in some of their examples. How is this number chosen? Is there any guarantee that the system will converge on a good solution, and that each pass of the algorithm produces a result that is closer to the optimum than the previous result was (ie., is it monotonically increasing in "accuracy"). And are there cases where regions will chase each other around the image, for instance, or live in some form of alternating size like some stable blinking structures in Conway's "Life"? I don't expect this to happen, but I don't know that the monotonic part is guaranteed to occur. MARKOV RANDOM FIELD MODELS FOR UNSUPERVISED SEGMENTATION OF TEXTURED ____________________________________________________________________ COLOR IMAGES, by Panjwani and Healy ____________ This approach is an iterative method of clustering and splitting textured color regions for segmentation. The basic merge and split approach is reasonable, though it results in blocky objects and is thus best for large objects rather than detecting fine borders. The measure on which the clustering is done tests textures both within each RGB (or equivalent) plane, and between planes. I don't have a lot of comments on this paper, though I'm curious how well it handles changes in resolution; i.e., at what point texture features become regions of their own. There also seems to be an issue of how finely to threshold the different regions. It's chief advantages appear to be the fact that it is almost totally independent of operator interaction, and that it works well on natural scenes, which may the the hardest to handle (though I'm curious how it handles really high-frequency natural features).
Stan Sclaroff
Created: Oct 23, 1995
Last Modified: