November 27, 2008
Line Detection
Brief Description
While edges (i.e. boundaries between regions with relatively distinct graylevels) are by far the most common type of discontinuity in an image, instances of thin lines in an image occur frequently enough that it is useful to have a separate mechanism for detecting them. Here we present a convolution based technique which produces an image description of the thin lines in an input image. Note that the Hough transform can be used to detect lines; however, in that case, the output is a parametric description of the lines in an image.
How It Works
Connected Components Labeling
Connected component labeling works by scanning an image, pixel-by-pixel (from top to bottom and left to right) in order to identify connected pixel regions, i.e. regions of adjacent pixels which share the same set of intensity values V. (For a binary image V={1}; however, in a graylevel image V will take on a range of values, for example: V={51, 52, 53, …, 77, 78, 79, 80}.)
Connected component labeling works on binary or graylevel images and different measures of connectivity are possible. However, for the following we assume binary input images and 8-connectivity. The connected components labeling operator scans the image by moving along a row until it comes to a point p (where p denotes the pixel to be labeled at any stage in the scanning process) for which V={1}. When this is true, it examines the four neighbors of p which have already been encountered in the scan (i.e. the neighbors (i) to the left of p, (ii) above it, and (iii and iv) the two upper diagonal terms). Based on this information, the labeling of p occurs as follows:
- If all four neighbors are 0, assign a new label to p, else
- if only one neighbor has V={1}, assign its label to p, else
- if more than one of the neighbors have V={1}, assign one of the labels to p and make a note of the equivalences.
After completing the scan, the equivalent label pairs are sorted into equivalence classes and a unique label is assigned to each class. As a final step, a second scan is made through the image, during which each label is replaced by the label assigned to its equivalence classes. For display, the labels might be different graylevels or colors.
Common Variants
A collection of morphological operators exists for extracting connected components and labeling them in various ways. A simple method for extracting connected components of an image combines dilation and the mathematical intersection operation. The former identifies pixels which are part of a continuous region sharing a common set of intensity values V={1} and the latter eliminates dilations centered on pixels with V={0}. The structuring element used defines the desired connectivity.
2-D Image Fourier Transform
- FT is used if we want to access the geometric characteristics of a spatial domain image.
- In most implementations the Fourier image is shifted in such a way that the DC-value (i.e. the image mean) F(0,0) is displayed in the center of the image. The further away from the center an image point is, the higher is its corresponding frequency
We will now experiment with some simple images to better understand the nature of the transform.
The image
shows 2 pixel wide vertical stripes. The Fourier transform of this image is
If we look carefully, we can see that it contains 3 main values: the DC-value and, since the Fourier image is symmetrical to its center, two points corresponding to the frequency of the stripes in the original image. Note that the two points lie on a horizontal line through the image center, because the image intensity in the spatial domain changes the most if we go along it horizontally.
Similar effects as in the above example can be seen when applying the Fourier Transform to
The magnitude of the Fourier Transform:
We can see that, again, the main components of the transformed image are the DC-value and the two points corresponding to the frequency of the stripes. However, the logarithmic transform of the Fourier Transform,
shows that now the image contains many minor frequencies. The main reason is that a diagonal can only be approximated by the square pixels of the image, hence, additional frequencies are needed to compose the image. The logarithmic scaling makes it difficult to tell the influence of single frequencies in the original image. To find the most important frequencies we threshold the original Fourier image at 5% of the main peak.
Compared to the original Fourier image, several more points appear. They are all on the same diagonal as the three main components, i.e. they all originate from the periodic stripes. The represented frequencies are all multiples of the basic frequency of the stripes in the spatial domain image.
Finally, we present an example (i.e. text orientation finding) where the Fourier Transform is used to gain information about the geometric structure of the spatial domain image. Text recognition using image processing techniques is simplified if we can assume that the text lines are in a predefined direction. Here we show how the Fourier Transform can be used to find the initial orientation of the text and then a rotation can be applied to correct the error. We illustrate this technique using
a binary image of English text. The logarithm of the magnitude of its Fourier transform is
and
is the thresholded magnitude of the Fourier image. We can see that the main values lie on a vertical line, indicating that the text lines in the input image are horizontal.
If we proceed in the same way with
which was rotated about 45°, we obtain
and
in the Fourier space. We can see that the line of the main peaks in the Fourier domain is rotated according to rotation of the input image. The second line in the logarithmic image (perpendicular to the main direction) originates from the black corners in the rotated image.
Common variants of DFT: DCT
The main advantages of the DCT are that it yields a real valued output image and that it is a fast transform. A major use of the DCT is in image compression — i.e. trying to reduce the amount of data needed to store an image. After performing a DCT it is possible to throw away the coefficients that encode high frequency components that the human eye is not very sensitive to. Thus the amount of data can be reduced, without seriously affecting the way an image looks to the human eye.
Template Matching
From the text below, we located areas where they have a high degree of correlation and similarity with the template “A”. There is a high degree of correlation in places where there is high degree of similarity.
Places with high correlation is indicated by bright white spots. However, the image is upside-down and left-side right. Rotating the image of the correlation would correspond would yield a direct correspondence with the places in the original text.
Edge Detection
We performed edge-detection using vertical, and horizontal filters using the command imcorrcoef(). This command is similar to template matching but instead uses a kernel template, and doesn’t care with the size of the template and the image.
let=imread(”L.bmp”);
let=im2gray(let);
hor = [-1 -1 -1; 2 2 2; -1 -1 -1];
vert= [-1 2 -1; -1 2 -1;-1 2 -1];
von = [-1 -1 -1; -1 8 -1; -1 -1 -1];
pattern=von //im2gray(vert);
c=imcorrcoef(let, pattern);
imshow(c);
always love – nada surf
rating: 1 star
lyrics:
To make a mountain of
your life Is just a choice
But I never learned enough
To listen to the voice that told me..
Always love…
Hate will get you every time
Always love…
Don’t wait till the finish line
Slow demands come around
Squeeze the air and keep the rest out
It helps to write it down
Even when you then cross it out
Always love…
Hate will get you every time
Always love…
Even when you wanna fight
Self-directed lies
I want to know what it’d be like to
Aim so high above
Any card that you get dealt you…
Always love…
Hate will get you every time
Always love…
Hate will get you
I’ve been held back by something
Yeah, you said to me quietly on the stairs,
I’ve been held back by something
Yeah, you said to me quietly on the stairs
You said…
Hey, you good ones
To make a mountain of your life
Is just a choice
But I never learned enough
To listen to the voice that told me
Always love…
hate will get you every time
Always love…
hate will get you?
I’ve been held back by something
Yeah, you said to me quietly on the stairs,
I’ve been held back by something
Yeah, you said to me quietly on the stairs
You said . . .
Hey, you good ones
I…
seafood soup
Ingredients:
fish, shrimp, (fish ball, etc)
tofu, pickle, seaweed
tomato, bambooshoot, medlar (枸杞), chilli
Directions:
boil, and add some salt.