See chapter 7 up to section 7.5 in your textbook
In the field of Image Processing, the extraction of geometric features from images is very common problem. Over the years, several different approaches have been devised to extract these features.
These different approaches can be characterized and classified in several different ways.
Some of the techniques involve global examination of the image, while others only involve local examination of each pixel in the image.
Typically, the first step in the process is to perform some form of edge detection on the image, and to generate a new Binary edge image that provides the necessary segmentation of the original image.
Edge detection algorithms operate on the premise that each pixel in a grayscale digital image has a first derivative, with regard to the change in intensity at that point, if a significant change occurs at a given pixel in the image, then a white pixel is placed in the binary image, otherwise, a black pixel is placed there instead.
In general, the gradient is calculated for each pixel that gives the degree of change at that point in the image. The question basically amounts to how much change in the intensity should be required in order to constitute an edge feature in the binary image.
A threshold value, T, is often used to classify edge points.
Some edge finding techniques calculate the second derivative to more accurately find points that correspond to a local maximum or minimum in the first derivative. This technique is often referred to as a Zero Crossing because local maxima and minima are the places where the second derivative equal zero, and its left and right neighbors are non-zero with opposite signs.
The Image Processing Toolbox's edge function provides several derivative estimators based on the criteria just you learned above.
For some of these estimators, it is possible to specify whether the edge detector is sensitive to horizontal or vertical edges or to both. The general syntax for the edge function is:
[g, t]= edge(f, 'method', parameters ... , options ... );where
f
is the input image. The most popularly used approaches
are listed in the following table. Additional approaces and control parameters
are discussed in MATLAB's documentation. Your lab instructor will give you a
tour of some of the details of the three approaches below in the lab
lecture.
In the output, g is a logical array with 1's at the locations where edge points were detected in f and 0's elsewhere. Parameter t is optional, it gives the threshold used by edge to determine which gradient values are strong enough to be called edge points.
Edge Detector | Basic Properties |
---|---|
Sobel | Finds edges using the Sobel approximation to the derivatives. |
Canny | Finds edges by looking for local maxima of the gradient of f(x,y). The gradient is calculated using the derivative of a Gaussian filter. The method uses two thresholds to detect strong and weak edges, and includes the weak edges in the output only if they are connnected to strong edges. Therefore, this method is more likely to detect true weak edges. |
Zero Crossing | Finds edges by looking for zero crossings after filtering f(x,y) with a user defined filter. This method is often combined with the Laplacian of a Gaussian filter, but any filter that approximates the second derivative of the image's data will do. If you don't provide your own filter, Zero Crossing uses the equivalent of this filter: H = FSPECIAL('log', 13, 2); See also the log section of help FSPECIAL. |
Now let us try those different methods and parameters to see what is the difference between them:
T=100; f=zeros(128,128); f(32:96,32:96)=255; [g1, t1]=edge(f, 'sobel', 'vertical'); imshow(g1); t1
sigma=1; f=zeros(128,128); f(32:96,32:96)=255; [g3, t3]=edge(f, 'canny', [0.04 0.10], sigma); figure,imshow(g3); t3
See chapter 9 up to section 9.3 in your textbook
The Hough Transform (HT) is a robust method for finding lines in images that was developed by Paul Hough.
The main idea for the HT is as follows:
To implement this algorithm we quantize the parameter space by using a 2D array of counters, where the array coordinates represent the parameters of the line. This is commonly known as an accumulator array.
The HT method for finding lines in images generally consists of the following three stages:
The MATLAB has a function called hough that computes the Hough Transform.
In the following example, we will illustrate the use of function hough on a simple binary image.
Type in the following commands. After typing each imshow, explain to yourself why you are seeing the new curve on the Hough transform.
f=zeros(101,101); f(1,1)=1; H=hough(f); imshow(H,[]) f(101,1)=1; H=hough(f); imshow(H,[]) f(1,101)=1; H=hough(f); imshow(H,[]) f(101,101)=1; H=hough(f); imshow(H,[]) f(51,51)=1;
The last imshow
should looks like this:
Let's try a more complex shape, the edge detected square from the examples above:
%generate the picture f=zeros(128,128); f(32:96,32:96)=255; %find edges sigma=1; [g3, t3]=edge(f, 'canny', [0.04 0.10], sigma); %Do the Hough transform [H t r] = hough(g3); %r and c store column labels... %Display the transform in such a way that we can draw points on it later... imshow(H, [], 'XData', t, 'YData', r ); %Add axis labels to the picture xlabel('\theta'), ylabel('\rho'); axis on, axis normal;
You result should look like this:
Now that you know how to do a Hough transform, the next step is to find line candidates by doing peak detection.
MATLAB provides us a function named houghpeaks to do this. The syntax is:
PEAKS = houghpeaks(H, numpeaks);where H is the Hough Transfrom matrix, and numpeaks is the maximum number of peak locations to look for. Be aware that peaks suppresses other peaks that are close to a peak just detected, and that if peaks are too weak, they will not be detected. These behaviours can be controlled with parameters. Consult the help file for houghpeaks for details.
Continuing the sample from above:
%detect four peaks P = houghpeaks(H,4); %draw peaks over Hough transform %don't replace the picture when we start to draw hold on; plot( t( P(:,2) ), r( P(:,1) ), 's', 'color', 'green');
You result should look like this:
Study help houghpeaks
if you want to see a more complex example.
Once a set of candidate peaks has been identified in the Hough transform, it remains to be determined if there are line segments associated with those peaks, as well as start and ending points.
For each peak, the first step is to find the location of all nonzero pixels in the image that contributed to that peak and construct line segments based on those pixels. The houghlines function can do this.
Learning the details of this function from help houghlines
is left to you as an exercise.
See section 10.3 in Digital Image Processing Using Matlab
Image thresholding plays a very important role in image segmentation.
In this section we discuss one way of choosing the threshold automatically.
An algorithm like the following can be used to choose a threshold, T
automatically:
T
. A possible initial value is the midpoint between the minimum and maximun intensity values in the image.T
. This will produce two groups of pixels:
G1
consisting of all pixels with intensity values > TG2
, consisting of pixels with values < T
.x1
and x2
for the pixels in regions G1
and G2
.T=1/2(x1+x2)
T
in successive iterations is smaller than a predifined parameter T0
.The above iterative method can be implemented as follows:
T=0.5*(double(min(f(:)))+double(max(f(:)))); done = false; while ~done g = f >= T; Tnext = 0.5*(mean(f(g))+mean(f(~g))); done = abs (T-Tnext) < 0.5; T = Tnext; end
where g is a binary mask, f(g) is a subset of f defined by g.
You can also use IPT's function graythresh to reach the same goal.
T = graythresh(f)
Image 1 |
Image 2 |