Unformatted text preview:

11Image Segmentation How do we know which groups of pixels in a digital image correspond to the objects to be analyzed? Objects may be uniformly darker or brighter than the background against which they appear Black characters imaged against the white background of a page Bright, dense potatoes imaged against a background that is transparent to X-rays2Image Segmentation: Definitions “Segmentation is the process of partitioning an image into semantically interpretable regions.” - H. Barrow and J. Tennenbaum, 1978 “An image segmentation is the partition of an image into a set of nonoverlapping regions whose union is the entire image. The purpose of segmentation is to decompose the image into parts that are meaningful with respect to a particular application.” - R. Haralick and L. Shapiro, 19923Image Segmentation: Definitions “The neurophysiologists’ and psychologists’ belief that figure and ground constituted one of the fundamental problems in vision was reflected in the attempts of workers in computer vision to implement a process called segmentation. The purpose of this process is very much like the idea of separating figure from ground ...” - D. Marr, 19824Image Segmentation: Definitions “The partitioning problem is to delineate regions that have, to a certain degree, coherent attributes in the image. We will refer to this problem as the image partitioning problem. It is an important problem because, on the whole, objects and coherent physical processes in the scene project into regions with coherent image attributes. Thus, the image partitioning problem can be viewed as a first approximation to the scene partitioning problem...” - Y. LeClerc, 198925Formal Definition Given region R and uniformity criterion U, define predicate P(R) = True, if ∃ a ∋ |U(i,j) - a| < ε, ∀ (i,j) ∈ R Partition image into subsets Ri, i = 1, ..., m, such that Complete: Image = ∪ Ri, i = 1, ..., m Disjoint subsets: Ri∩ Rj= ∅, ∀ i ≠ j Uniform regions: P(Ri) = True, ∀ i Maximal regions: P(Ri∪ Rj) = False, ∀ i ≠ j67 839 10Image Segmentation Ideally, object pixels would be black (0 intensity) and background pixels white (maximum intensity) But this rarely happens because Pixels overlap regions from both the object and the background, yielding intensities between pure black and white - edge blur Cameras introduce “noise” during imaging -measurement “noise” Potatoes have non-uniform “thickness”, giving variations in brightness in X-ray - model “noise”11Image Segmentation by Thresholding But if the objects and background occupy different ranges of gray levels, we can “mark” the object pixels by a process called thresholding: Let F(i,j) be the original, gray level image B(i,j) is a binary image (pixels are either 0 or 1) created by thresholding F(i,j): B(i,j) = 1 if F(i,j) <= t B(i,j) = 0 if F(i,j) > t We will assume that the 1’s are the object pixels and the 0’s are the background pixels12Thresholding How do we choose the threshold t? Histogram: Gray level frequency distribution of the gray level image F hF(k) = number of pixels in F whose gray level is k HF(k) = number of pixels in F whose gray level is <= kintensity, gh(g)peak peakvalley413Thresholding P-tile method In some applications we know approximately what percentage, p, of the pixels in the image come from objects Might have one potato in the image, or one character. HFcan be used to find the gray level, g, such that ~p% of the pixels have intensity <= g Then, we can examine hFin the neighborhood of g to find a good threshold (low valley point)  Could also examine the binary images corresponding to alternative thresholds to choose a “best” one. E.g., one with straightest edges, most easily recognized objects, etc.14Thresholding Mode (peak and valley) method Find the two most prominent peaks of h g is a peak if hF(g) > hF(g ± ∆g), ∆g = 1, ..., k Let g1and g2be the two highest peaks, with g1< g2 Find the deepest valley, g, between g1and g2 g is the valley if hF(g) < hF(g’) , ∀g, g’ ∈ [g1, g2]  Use g as the threshold When image contains 2 normally-distributed classes, can prove that the probability of misclassification is minimized when g is at the minimum point15 16517 1819 20621 2223Thresholding Hand selection Select a threshold by hand at the beginning of the day Use that threshold all day long! Many threshold selection methods in the literature Probabilistic methods Make parametric assumptions about object and background intensity distributions and then derive “optimal” thresholds Structural methods Evaluate a range of thresholds with respect to properties of resulting binary images Local thresholding Apply thresholding methods to image windows24An Advanced Threshold Selection Method: Minimizing Kullback Information Distance The observed histogram, f, is a mixture of the gray levels of the pixels from the object(s) and the pixels from the background In an ideal world the histogram would contain just two spikes But measurement noise, model noise and edge blur spread these spikes out into hills Make a parametric model of the shapes of the component histograms of the objects(s) and background725Kullback Information Distance Parametric model - the component histograms are assumed to be Gaussian poand pbare the proportions of the image that comprise the objects and background µoand µbare the mean gray levels of the objects and background σoand σbare their standard deviationsfo(g) =po2πσoe−1 / 2(g−µoσo)2ofb(g) =pb2πσbe−1 / 2(g−ubσb)226Kullback Information Distance Now, once we choose a threshold, t, then all of these unknown parameters are determined. Let f(g) be the observed and normalized histogram f(g) = percentage of pixels from image having gray level gpo(t) = f(g)g= 0t∑µo(t) = f (g)gg= 0t∑µb(t) = f (g)gg= t +1max∑pb(t)=1−p0(t)27Kullback Information Distance So, once t is chosen we can “predict” what the total normalized image histogram should be if our model (mixture of two Gaussians) is correct Pt(g) = pofo(g) + pbfb(g) The total normalized image histogram is reallyf(g) So, the question reduces to: Determine a suitable way to measure the similarity of Ptand f Find the t


View Full Document

UW-Madison CS 766 - Image Segmentation

Documents in this Course
Load more
Download Image Segmentation
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Image Segmentation and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Image Segmentation 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?