Document from Maahi

Module 3: Image Segmentation And Morphological Image Processing Image Segmentation Group similar components (such as, pixels in an image, image frames in a video) to obtain a compact representation. Applications: Finding tumors, veins, etc. in medical images, finding...

Module 3: Image Segmentation And Morphological Image Processing Image Segmentation Group similar components (such as, pixels in an image, image frames in a video) to obtain a compact representation. Applications: Finding tumors, veins, etc. in medical images, finding targets in satellite/aerial images, finding people in surveillance images, summarizing video, etc. Methods: Thresholding, K-means clustering, etc. Image Segmentation Segmentation algorithms for monochrome images generally are based on one of two basic properties of gray- scale values:  Discontinuity The approach is to partition an image based on abrupt changes in gray-scale levels. The principal areas of interest within this category are detection of isolated points, lines, and edges in an image.  Similarity The principal approaches in this category are based on thresholding, region growing, and region splitting/merging.  Point Detection Using the mask shown in Fig 10.2(a), we say that a point has been detected at the location on which the mask is centered if |R| >=T The idea is that an isolated point will be quite different from its surroundings, and thus be easily detectable by this type of mask.  Detection of Discontinuities The most common way to look for discontinuities is to run a mask through the image. © 2002 R. C. Gonzalez & R. E. Woods  Line Detection Consider the masks shown in Fig 10.3. If the first mask were moved around an image, it would respond more strongly to lines (one pixel thick) oriented horizontally.  Line Detection Fig10.4(a) shows a digitized (binary) portion of a wire-bond mask for an electronic circuit. Suppose that we are interested in finding all the lines that are one pixel thick and are oriented at -45°. For the purpose, we use last mask shown in Fig. 10.3.  Line Detection In order to determine which line best fit the mask, we simply threshold this image. The result of using a threshold equal to the maximum value in the image is shown in Fig 10.4(c).  Edge Detection Edge detection is by far the most common approach for detecting meaning discontinuities in gray level. Intuitively, an edge is a set of connected pixels that lie on the boundary between two regions. A reasonable definition of “edge” requires the ability to measure gray- level transitions in a meaningful way.  Edge Detection Intuitively, an ideal edge has the properties has the properties of the model shown in Fig 10.5(a). Edges are more closely modeled as having a “ramplike” profiles, such as the one shown in Fig 10.5(b), Blurred edges tend to be thick and sharp tend to be thin.  Edge Detection We conclude from these observations that the magnitude of the first derivative can be used to detect the presence of an edge at a point in an image. Similarly, the sign of the second derivation can be used to determine whether an edge pixel lies on the dark or light side of an edge.  Edge Detection Two additional properties of the second derivative around an edge: 1) It produces two value for every edge in an image 2) an imaging straight line joining the extreme positive and negative values of the second derivative would cross zero near the midpoint of the edge. The zero-crossing property of the second derivative is quite useful for locating the centers of thick edges.  Edge Detection  These examples are good illustrations of the sensitivity of derivatives to noise.  The fact that fairly little noise can have such a significant impact on the two key derivatives used for edge detection in images is an important issue to keep im mind.  In particular, image smoothing should be a serious consideration prior to the use of derivatives in applications where noise with levels similar to those we have just discussed is likely to be present.  We define a point in an image as being an edge point if its two-dimensional first-order derivative is greater than a specified threshold. Image gradient The gradient of an image: The gradient points in the direction of most rapid increase in intensity The gradient direction is given by: how does this relate to the direction of the edge? The edge strength is given by the gradient magnitude  Gradient operators A weight value of 2 is used to achieve some smoothing by giving more importance to the center point, called the Sobel operators. The Prewitt and Sobel operators are among the most used in practice for computing digital gradients. Prewitt masks are simpler to implement than the Sobel masks, but the later have slightly superior noise-suppression characteristics, an important issue when dealing with derivatives.  Gradient operators An approach used frequently is to approximate the gradient by absolute values: the gradient by absolute values: The two additional Prewitt and Sobel masks for detecting discontinuities in the diagonal directions are shown in Fig. 10.9.  The Laplacian The Laplacian of a 2-D function (x,y) is a second-order derivative defined as For a 3x3 region, one of the two forms encountered most frequently in practice is  The Laplacian A digital approximation including the diagonal neighbors is given by As a second-order derivative, the Laplacian typically is unacceptably sensitive to noise. The Laplacian is unable to detect edge direction.  The Laplacian Role of the Laplacian in segmentation consist of (1) using its zero-crossing property for edge location, (2) using it for the complementary purpose of establishing whether a pixel is on the dark or light side of an edge: this function is commonly referred to as the Laplacian of a Gaussian (LoG) because Eq(10.1-16) is in the form of a Gaussian function. © 2002 R. C. Gonzalez & R. E. Woods  The Laplacian The LoG result in Fig. 10.15(e) is the image from which zero crossings are computed to find edges. One straightforward approach for approximating zero crossings is to threshold the LoG image by setting all its positive values to, say, white, and all negative values to black.  The Laplacian Compare Fig. 10.15(b) and (g) reveals several interesting and important differences. First, we denote that the edges in the zero- crossing image are thinner than the gradient edges. On the other hand, we see in Fig. 10.15(g) that the edges determined by zero crossings for, numerous closed loops. This so-called spaghettieffect is one of the most seties drawbacks of this method.  Edge linking and Boundary Detection One of the simplest approaches for linking edge points is to analyze the characteristics of pixels in a small neighborhood (say, 3x3 or 5x5). All points that are similar according to a set of predefined criteria are linked. The two principal properties used for establishing similarity of edge pixels in this kind of analysis are (1) the strength of the response of the gradient operator used to produce the edge pixel; and (2) the direction of the gradient vector. Local Processing  Local Processing Fig.10.16(d) shows the result of linking all points that simultaneously had a gradient value greater than 25 and whose gradient directions did not differ by more than 15°. Global Processing via the Hough Transform In this section, points are linked by determining first if they lie on a curve of specified shape. An approach based on the Hough transform is as follows: 1) Compute the gradient of an image and threshold it to obtain a binary image. 2)Specify subdivisions in the ρθ-plane. 3)Examine the counts of the accumulator cells for high pixel concentrations. 4)Examine the relationship (principally for continuity) between pixels in a chosen cell. Thresholding Suppose that an image, f(x,y), is composed of light objects on a dark background, and the following figure is the histogram of the image. Then, the objects can be extracted by comparing pixel values with a threshold T. Thresholding Thresholding Thresholding It is also possible to extract objects that have a specific intensity range using multiple thresholds. Extension to color images is straightforward: There are three color channels, in each one specify the intensity range of the object… Even if objects are not separated in a single channel, they might be with all the channels… Application example: Detecting/Tracking faces based on skin color… Thresholding Non-uniform illumination may change the histogram in a way that it becomes impossible to segment the image using a single global threshold. Choosing local threshold values may help. Thresholding Thresholding Adaptive thresholding Thresholding Almost constant illumination Separation of objects… Region-Oriented Segmentation Region Growing  Region growing is a procedure that groups pixels or subregions into larger regions.  The simplest of these approaches is pixel aggregation, which starts with a set of “seed” points and from these grows regions by appending to each seed points those neighboring pixels that have similar properties (such as gray level, texture, color, shape).  Region growing based techniques are better than the edge- based techniques in noisy images where edges are difficult to detect. Region-Oriented Segmentation Region-Oriented Segmentation Exercise Region-Oriented Segmentation Region Splitting  Region growing starts from a set of seed points.  An alternative is to start with the whole image as a single region and subdivide the regions that do not satisfy a condition of homogeneity. Region Merging  Region merging is the opposite of region splitting.  Start with small regions (e.g. 2x2 or 4x4 regions) and merge the regions that have similar characteristics (such as gray level, variance).  Typically, splitting and merging approaches are used iteratively. Example Region-Oriented Segmentation Segment the image shown by using the split and merge procedure discussed in Section 10.4. Let Q ( Ri ) = TRUE if all pixels in Ri have the same intensity. Show the quadtree corresponding to your segmentation. Exercise Apply region split and merge algorithm on the following image and obtain the segmented image. Introduction---Morphology Operations Terminology: Morphology: a broad set of image processing operations that process images based on shapes. Morphological operations apply a structuring elements to an input image, creating an output image of the same size. Properties: Morphological operations simplify images, and quantify and preserve the main shape characteristics of objects.  Morphological Image Processing Set Theory Fundamentals Given that A is a set in Z2and a=(a1,a2), then a is an element in A: a A a is not an element in A: a A given sets A and B, A is said to be the subset of B: AB The union of A and B is denoted by: C A B The intersection of A and B is denoted by: D A B Two sets are disjoint/mutually exclusive if A  B  The complement of set A is the set of elements not contained in A, A c    A The difference of two sets: A  B    A,   B  A  B c  Morphological Image Processing Set Theory Fundamentals Given 2 sets A and B  Morphological Image Processing Set Theory Fundamentals The reflection of set B is defined by: Bˆ    b, for b  B The translation of set A by point z=(z1,z2) is defined by: ( A) z   a  z , for a  A Translation of A by z. Reflection of B Morphological Image Processing Logic operation involving Binary Images Given 1-bit binary images, A and B, the basic logical operations are illustrated: Note that the black indicates binary 1 and white indicates binary 0 here. Structuring element (SE)  small set to probe the image under study  for each SE, define origin  shape and size must be adapted to geometric properties for the objects 72  Examples: Structuring Elements origin 73 Basic idea in parallel for each pixel in binary image: check if SE is ”satisfied” output pixel is set to 0 or 1 depending on used operation 74 Example Origin of B visits every element of A At each location of the origin of B, if B is completely contained in A, then the location is a member of the new set, otherwise it is not a member of the new set. 75  Basic morphological operations Erosion Dilation keep general shape but combine to smooth with respect to Opening object Closening background 76 Erosion Does the structuring element fit the set? erosion of a set A by structuring element B: all z in A such that B is in A when origin of B=z shrink the object 77 78 Erosion 79 Erosion 80 Erosion A⊖B= { z|( B ) z ⊆ A } 81 Dilation Does the structuring element hit the set? the dilation of A by B can be understood as the locus of the points covered by B when the center of B moves inside A. A  B {z|(Bˆ )z  A Φ} grow the object 82 83 Dilation 84 Dilation 85 Dilation B = structuring element A  B {z|(Bˆ )z  A Φ} 86 Dilation : Bridging gaps 87 88 89 90 91 Applications erosion removal of structures of certain shape and size, given by SE Dilation filling of holes of certain shape and size, given by SE 92 Exercise Apply Dilation and Erosion on given image and consider first element of structuring element as origin. Exercise Perform the operation F = (I⨁S)ӨS S I Combining erosion and dilation WANTED: remove structures / fill holes without affecting remaining parts SOLUTION: combine erosion and dilation (using same SE) 95 Erosion : eliminating irrelevant detail Opening erosion followed by dilation, denoted ∘ A ∘ B=( A⊖B ) ⊕B eliminates protrusions breaks necks smoothes contour 97 Opening 98 Opening 99 Opening A ∘ B=( A⊖B ) ⊕B A  B {( B ) z | ( B) z  A}  Opening example Opening with a 11 pixel diameter disc: 3x9 and 9x3 Structuring Element Perform Opening on the following considering first pixel as origin. Closing dilation followed by erosion, denoted A⋅B=( A⊕B )⊖B smooth contour fuse narrow breaks and long thin gulfs eliminate small holes fill gaps in the contour 103 Closing 104 Closing 105 Closing A⋅B=( A⊕B )⊖B 106 Another closing example Closing operation with a 22 pixel disc, closes small holes in the foreground. And another… Threshold, closing with disc of size 20. Note that opening is the dual of closing i.e. opening the foreground pixels with a particular structuring element is equivalent to closing the background pixels with the same element. Perform Closing on the following imageand considering first pixel as origin of structuring element.  Morphological Image Processing Hit-or-Miss Transform (Template Matching) Hit-or-miss transform can be used for shape detection/ Template matching. Given the shape as the structuring element B1 the Hit-or-miss transform is defined by: c A * B ( A  B1 )  ( A  B2 ) Where B2 =W-X and B1=X. W is the window enclosing B1. Windowing is used to isolate the structuring element/object. B2=W-X, used as the second structuring element. Complement of B1 Shape that we are searching for Used as the structuring element (B 1=X)  Morphological Image Processing Hit-or-Miss Transform c A * B ( A  B1 )  ( A  B2 ) B2 B1 Complement of A Erosion of A by B1 Erosion of comp of AC by B2 The location of the matched object/shape,  Morphological Image Processing Basic Morphological Algorithms Boundary Extraction: The boundaries/edges of a region/shape can be extracted by first applying erosion on A by B and subtracting the eroded A from A.  ( A)  A  ( A  B) Ex 1: 3x3 Square structuring element is used Ex 2: The same structuring element in Ex1 is used. for boundary extraction. Note that thicker boundaries can be obtained by increasing the size of structuring element. Exercise: Detect Boundary of the object with 3x3 cross structural element 0 0 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 Morphological Image Processing Basic Morphological Algorithms Region Filling: Region filling can be performed by using the following definition. Given a symmetric structuring element B, one of the non-boundary pixels (X k) is consecutively diluted and its intersection with the complement of A is taken as follows: c k 1,2,3,... X k ( X k  1  B )  A terminates when X k  X k  1 X 0 1 (inner pixel ) Following consecutive dilations and their intersection with the complement of A, finally resulting set is the filled inner boundary region and its union with A gives the filled region F(A). F ( A)  X k  A  Morphological Image Processing Basic Morphological Algorithms Region Filling: This region is filled first. Filling of all the other regions A non-boundary pixel Ex 1: X0=1 (Assume that the shaded boundary points are 1 and the white pixels are 0)  Morphological Image Processing Basic Morphological Algorithms Connected Component Extraction: The following iterative expression can be used to determine all the pixels in component Y which is in A. k 1,2,3,... X k ( X k  1  B )  A terminates when X k  X k  1 X 0 1 (boundary pixel ) X0=1 corresponds to one of the pixels on the component Y. Note that one of the pixel Result of first iteration locations on the component must be known. Known pixel, p Consecutive dilations and their intersection with A, yields all elements of component Y. Result of second iteration Result of last iteration  Morphological Image Processing Basic Morphological Algorithms Connected Component Extraction: Input image (Chicken fillet) Thresholded image 15 connected components with different number of pixels After erosion by 5x5 square structuring element of 1’s  Morphological Image Processing Basic Morphological Algorithms Thinning: Thinning of A by the structuring element B is defined by: A  B A  ( A  * B) hit-or-miss transform/template matching Note that we are only interested in pattern matching of B in A, so no background operation is required of the hit-miss-transform. {B} {B1 , B 2 , B 3 ,..., B n } The structuring element B consists of a sequence of structuring elements, where B i is the rotated version of Bi-1. Each structuring elements helps thinning in one direction. If there are 4 structuring elements thinning is performed from 4 directions separated by 90 o. If 8 structuring elements are used the thinning is performed in 8 directions separated by 45o. The process is to thin A by one pass with B1, then the result with one pass of B2, and continue until A is thinned with one pass of Bn. A  {B} ((...(( A  B1 )  B 2 )...)  B n ) Morphological Image Processing Basic Morphological Algorithms Thinning: The following set of structuring elements are used for thinning operation.... If there is no change any more. Declared to be the thinned object