Object Detection using Hough Transform (II)

In previous post we've compare the Hough Matrix of a single dot, 2 dots and a single line. In this post, we'll look into more shapes:

a. Square Object

The right hand plot shows the frequencies of an intensity occurs in the Hough Matrix. It can also interpreted as: Number of lines that cross the number of points shown in the x-axis. For e.g.: for a dot, number of lines that cross one point is 180, for 2 dots image, number of lines that cross one point is 358, while number of lines that cross 2 points are 1. (refer to previous post)

For a square object, numbers of lines that cross 1 point, 2 points.....until n points in which n is the lenght of the square (approximately) would be almost the same. This could be noticed in the right figure.

b. Round Object

For a round object, numbers of lines that cross 1 point, 2 points.....until n points in which n is the diameter of the round object (approximately) would be increase in exponently. This could be noticed in the right figure.

Well, there are much more information we could get from the Hough Matrix, and what I written here might be wrong in someway, so try it out by using different images with 1 dot, 2 dots, 3 dots... using the code provided in the previous post, you would find more and more useful information from the plots!

Object Detection using Hough Transform (I)

Hough Transform convert the binary image from x-y plane to rho-theta plane. This series of examples are going to show some properties that we can observe from the hough matrix and classify some simple object shapes based on it. For more information on the Hough Transform, you can use any searh engine such as google or yahoo to searh for the keyword: "Hough Transform".

1. Original image and convert to binary image
S = imread('img1.bmp');
S = im2bw(S);
imshow(S);

2. Perform Hough Transform and show the result
[H, theta,rho]=hough(S);
figure;
imshow(H,[],'xdata',theta,'ydata',rho);
xlabel('\theta'),ylabel('\rho')
axis on, axis normal;
title('Hough Matrix');

3. Count the "frequency" of the intensity of the Hough Matrix.
clear data;
for cnt = 1:max(max(H))
data(cnt) = sum(sum(H == cnt));
end
figure;
plot(data,'.');

The codes are applied to different images to compare the differences of
the Hough Matrix on different objects' shapes.

Some simple objects' shape and their Hough Matrix are as follow:

a. Single Point

To obtain the Hough Transform, draw lines from -90 to 90 degree that cross the dot, follow by drawing a Perpendicular line from the upper left of the image to the line, and measure the lenght(rho) and the angle (theta) of the Perpendicular line.

The "hough" function will perform this for every 1 degree, and hence, for a single dot, the there will be 180 of '1' in the "Hough Matrix".

b. Two Points

When there are two points on an image, the Hough Matrix consist of 2 lines, and interect at a point which is a line that link the 2 points together in x-y plane (left figure).

Since there is only one intersection (only one line that link 2 points together), the frequencies of '1' in Hough Matrix is 358, while the frequencies of '2' is 1 in the Hough Matrix. (the '1' and '2' indicates how many time a rho-theta appear in the Hough Matrix)

c. Line

A line consists of numbers of points, ideally (the line is 45 degree) the intersection in the Hough Matrix will have the intensity same as the line lenght.

Hough Transform always used to detect lines in a real image, in which the edges always distorted. A higher value in the Hough Matrix indicates the higher possibility of the existence of a straight line.

More objects shapes will be shown in the next post...

Maple for Image Processing?

Can Maple used for Image Processing?

Maple is the tool for solving mathematical problems and creating interactive technical applications. My experience with Maple is that --> a symbolic software.

However, when I did a search on "maple image processing", I found the following link:
Image Processing with Maple

Seems like the new version of Maple (or even older version) support basic image processing function, and it might be supporting more and more in the future...

Some other software for image processing could be found at the sidebar, or you can simply do a search using google or yahoo..

Keyword to search for : Matlab, Maple, Mathematica, Math Software, Image Processing Software, Image Analysis...

Which Software to Use?

What Software Should be Used for Image Processing?

There are numbers of different software for engineering, each has its' capability and weakness. Most of the examples here use Matlab because I deal alot with Matlab in University.

However, I won't say there are no other software better than Matlab, but i still believe:-

"Choose the Software you're familiar with, know your direction and how far the software can accompany you along the way..."

A good article comparing 3 famous software:

3Ms for Instruction: Reviews of Maple, Mathematica, and Matlab

Happy programming.

Drawing Circles Around Round Object

Drawing shapes to highlight certain objects could be done in several ways. Previous examples illustrate few ways of drawing object by overwriting pixel value as well as by adding a "patch" on top of an image. This example shows how to draw circles around a round object just simply using "plot" command

1. Original image

S = imread('pic13.jpg');
S = im2bw(S);
S2 = ~S;
imshow(S2);


2. Extracting required objects' properties. Required properties are centroid and the area of the round objects. The area property is used to compute the radius of the object.

S3 = bwlabel(S2);
S4 = regionprops(S3,'Centroid','area');
R = sqrt(S4(1).Area/pi);
h = S4(1).Centroid(1);
k = S4(1).Centroid(2);

3. Drawing circles around 1st object with different radius by refering to the radius of the object.

ratio = [2 1.5 1];
nR = round(R*ratio);
t = 0:pi/20:2*pi;
x1 = (h+nR'*cos(t))';
y1 = (k+nR'*sin(t))';
hold on;
plot(x1,y1);

Drawing Transparent Object

In one of the previous post (Drawing Shapes by Overwriting Pixel Value), a method of drawing transparent object had been illustrated using "Overwriting Pixel Value" technique. In this example, another method will be introduced without overwriting pivel value, but drawing a "Patch" on top of the image.

1. Original image

S = imread('pic12.jpg');
S = im2bw(S);
S2 = S;
imshow(S2);


2. Define transparent object properties

transparency = 0.5;
facecolor = [0 1 0];
edgecolor = [0 1 0];

3. Creating and drawing transparent object

x = [0 20 20 0];
y = [0 0 20 20];
z = [1 1 1 1];
tcolor(1,1,1:3) = facecolor;

h = patch(x,y,z,tcolor,'FaceAlpha',transparency,'edgecolor',edgecolor);


4. To move the object, simply set the "Xdata" and "Ydata" of the object without deleting current object and redrawing a new onject

set(h,'Xdata',x+20);
set(h,'Ydata',y+20);

Detecting Objects' Shape(III) : Triangle Object

This example illustrates a simple method in detecting triangle object. This method is slightly different from the methods used for round object and square object detection in which the area and the perimeter of the objects are used to calculate the "score" of similarity. Instead, this method uses the "extrema" points of an object to determine whether the object is triangle.

1. Original image and the negative image (value 0 represent background while 1 represents object).

S = imread('pic11.jpg');
S = im2bw(S);
S2 = ~S;
imshow(S2);



2. Labeling the objects in the image. The advance programming language will support this function and label the objects.

S3 = bwlabel(S2);
imshow(S3,[]);

3. In this example of triangle object detection, only one object property is extracted --> "Extrema".

S4 = regionprops(S3,'Extrema','Centroid');

The “Centriod” is just used for labeling purpose. Following figure shows what “Extrema” of an object is:
4. Ideally, a triangle will only have 3 extrema points. However, due to the imperfection of a binary object, a few of close-by points might exist instead of one.
For example eight extrema points of a triangle are: (135.5,11.5),(136.5,11.5),(157.5,45.5),(157.5,47.5),(157.5,47.5),(112.5,4 7.5),(112.5,47.5),(112.5,45.5) first 2 points are referring to the upper corner of the triangle but the values are different. This applied to point 3 to 5 and points 6-8 too.

In order to solve this problem, we need to cluster the points to their group based on the location of the points. Different ways could be used for clustering but since our topic is about image processing, image processing method will be used to group the similar points together.

In this method, a morphology technique --> dilation will be used. Firstly, the extrema points will be used to construct an image. The coordinates of the extrema points will be converted to points in an image. Let's look into one of the object for illustration:

a. Create morphological structuring element.

se = strel('disk',5);

b. Round the extrema points for 5th object (pixel value must be integer)

temp = round(S4(5).Extrema);

c. Remap the coordinates by referring to the minimum values of x and y

temp(:,1) = temp(:,1) - min(temp(:,1)) + 1;
temp(:,2) = temp(:,2) - min(temp(:,2)) + 1;

d. Create a zero matrix (black image)

mask = zeros(max(temp(:,1)),max(temp(:,2)));

e. Convert the coordinates to "objects" in the black image

for cnt2 = 1:8
mask(temp(cnt2,1),temp(cnt2,2))=1;
end
imagesc(mask);

f. Do note that some of the points are close together; use the image dilation technique to group close-by points.

mask2 = imdilate(mask,se);
imagesc(mask2);

g. Count number of real extrema points in the image

[labeled,numObjects] = bwlabel(mask2,8);
disp(numObjects);

3

5. The following codes perform calculation for all objects

se = strel('disk',5);
for cnt = 1:length(S4)
temp = round(S4(cnt).Extrema);
temp(:,1) = temp(:,1) - min(temp(:,1)) + 1;
temp(:,2) = temp(:,2) - min(temp(:,2)) + 1;
mask = zeros(max(temp(:,1)),max(temp(:,2)));
for cnt2 = 1:8
mask(temp(cnt2,1),temp(cnt2,2))=1;
end
mask2 = imdilate(mask,se);
[labeled,numObjects(cnt)] = bwlabel(mask2,8);
end

disp(numObjects);
5 3 4 6 3 4

score = (numObjects == 3);

6. Display the result visually

imshow(S2)
for cnt = 1:length(S4)
text(S4(cnt).Centroid(1),S4(cnt).Centroid(2),num2str(score(cnt)),'color','red');
end

Detecting Objects' Shape(II) : Square Object

Detecting square object could be done in similar way we used to detect the round object. What we need to know is just the the formula for the area and the perimeter of a square object which is A = w^2 and P = 4*w.


1. Original image and the negative image (value 0 represent background while 1 represent oject).
S = imread('pic10.jpg');
S = im2bw(S);
S2 = ~S;
imshow(S2);


2. Labeling the objects in the image. The advance programming language will support this function and label the objects.
S3 = bwlabel(S2);
imshow(S3,[]);

3. Some properties of the objects are extracted using the command. In this example, we just use the area and perimeter for our calculation.
S4 = regionprops(S3,'Area','Perimeter','centroid');

4. Now, evaluate the "squareness" of the objects. this is evaluated by only 1 criteria in this example:
a. Calculate the length or width of the object by using the formulas of area and perimeter, comparing the result and the square objects would have higher score than others. Do note that instead of for loop, the code below is a vectorized code.
score = (min(sqrt([S4.Area]),[S4.Perimeter]/4)./(max(sqrt([S4.Area]), ...[S4.Perimeter]/4))).^2;

5. Display the result visually
imshow(S2)
for cnt = 1:length(S4)
text(S4(cnt).Centroid(1),S4(cnt).Centroid(2),num2str(score(cnt)),'color','red');
end


Do note that this example assumes perfect images. For more accurate results, more properties can be compared by using more criteria. The example above is done using MATLAB®.


MATLAB® is registered trademarks of The MathWorks.

Detecting Objects' Shape(I) : Round Object

With the powerful technical computing language, the job of detection an object's shape no longer require lengthy codes. What important is the fundamental of mathematic that define the properties of the shape of objects. Let's look into the detection of round object in this section.

1. Original image and the negative image (value 0 represent background while 1 represents object).

S = imread('pic9.jpg');
S = im2bw(S);
S2 = ~S;
imshow(S2);




2. Labeling the objects in the image. The advance programming language will support this function and label the objects automatically.
S3 = bwlabel(S2);
imagesc(S3);



3. Getting the properties of the objects that require for calculation, which are: the longest and shortest diameter for the object, the area and the perimeter of the object, and the centroid of the object.
S4 = regionprops(S3,'MinorAxisLength','MajorAxisLength','Area','Perimeter','centroid');

4. Now, evaluate the "roundness" of the objects. this is evaluated by 3 criteria:
a. Comparing the longest and shortest diameter for the object,
b. Comparing the Area with the formula pi*r^2.
c. Comparing the Perimeter with the formula 2*pi*r
The "scores" are normalized so that 1 represent "best fit"

for cnt = 1:length(S4)
score1(cnt) = abs(1-(S4(cnt).MajorAxisLength-S4(cnt).MinorAxisLength)...
/max([S4(cnt).MajorAxisLength,S4(cnt).MinorAxisLength]));
score2(cnt) = abs(1 - abs(pi*((mean([S4(cnt).MajorAxisLength,...
S4(cnt).MinorAxisLength]))/2)^2-S4(cnt).Area)/S4(cnt).Area);
score3(cnt) = abs(1 - abs(pi*(max([S4(cnt).MajorAxisLength,...
S4(cnt).MinorAxisLength]))-S4(cnt).Perimeter)/S4(cnt).Perimeter);
end
score = mean([score1;score2;score3]);

5. Display the result visually

imshow(S2)
for cnt = 1:length(S4)
text(S4(cnt).Centroid(1),S4(cnt).Centroid(2),num2str(score(cnt)),'color','red');
end

Playing with “Edge Detection”

A lot of articles explain what is edge detection, how to apply it, and the usage of it. Different edge detection techniques such as sobel, prewitt, and canny are easily found from any image processing software.

However, when we really want to perform edge detection for certain purpose, the problems arise. Look at the following example:

1. Original image
S = imread('pic8.jpg');
imshow(S);

2. Edge detection using different methods
S2 = rgb2gray(S);
figure,edge(S2,'sobel');
figure,edge(S2,'prewitt');
figure, edge(S2,'canny');

It seems like great but the usage of these output are useless until we really know what we want to do. For exmaple, we want to find the white rabbit, we need to perform some pre-processing before the edge detection so that we can fully utilize the function to suite to our needs.

3. Edge detection for the white rabbit
Since we know the RGB value for white color is [255,255,255], we can pre-process the image to extract the white color region from the image.

Sw = S(:,:,1)>200 & S(:,:,2)>200 & S(:,:,3)>200;
edge(double(Sw));

Well, it seems like make more sense. Let's have a look on how to perform edge detection on the black rabbit:

4. Edge detection for the black rabbit

Sb = S(:,:,1)<40 & S(:,:,2)<40 & S(:,:,3)<40;

The post processing can be used to remove unwanted noise.

Panoramic Picture Creation

This example illustrates simple method of panoramic picture creation using sum of absolute differences. It assumes no zooming, rotational variation in 2 images.

1. Reading Images for processing
S1 = imread('p1.jpg');
S2 = imread('p2.jpg');

2. Showing Images
1st Image

imshow(S1);



2nd Image

imshow(S2);



3. Extract red layer of the image for processing using Sum of Absolute Differences (SAD)
S1r = S1(:,:,1);
S2r = S2(:,:,1);

4. Sum of Absolute Differences (SAD) of a selected block is from each image are computed.
sz = 50;
roi2 = S2r(1:sz,1:sz);
[x,y]=size(S2r);
for cnt = y:-1:x/2
roi1 = S1r(1:sz,cnt-sz+1:cnt);
data(y-cnt+1)=sum(sum(abs(double(roi2)-double(roi1))));
end

5. Finding minimum error among all comparison
plot(data)
[minval,ind] = min(data);
hold on;
plot(ind,minval,'r*');





6. Combine the images at the minimum error region.
Sc = S1(1:end,1:y-sz-ind+1,:);
Sfinal = [Sc S2];

7. Final Result
figure;
imshow(Sfinal);

Character Recognition Example (III):Training a Simple NN for classification

After preprocess the image, the training dataset is used to train "classification engine" for recognition purpose. In this example, a multi-layer feed-forward back-propagation Neural Network will be used.

1. Read the image
I = imread('sample.bmp');

2. Image Preprocessing
This cell of codes will extract all the components (objects) as descript in section II.

img = edu_imgpreprocess(I);
for cnt = 1:50
bw2 = edu_imgcrop(img{cnt});
charvec = edu_imgresize(bw2);
out(:,cnt) = charvec;
end

3. Creating Vectors data for the Neural Network (objects)
These few line of codes creates training vector and testing vector for the neural network. This is to match the input accepted by the neural network function. The front 4 rows will be used to train the network, while the last row will be used to evaluate the performance of the network. (Please refer to part I and II for the dataset)

P = out(:,1:40);
T = [eye(10) eye(10) eye(10) eye(10)];
Ptest = out(:,41:50);

4. Creating and training of the Neural Network
Create and Train NN. The "edu_createnn" is a function file to create and train the network by accepting the training-target datasets

net = edu_createnn(P,T);

TRAINGDX, Epoch 0/5000, SSE 100.603/0.1, Gradient 46.9458/1e-006
TRAINGDX, Epoch 20/5000, SSE 38.3704/0.1, Gradient 1.1137/1e-006
TRAINGDX, Epoch 40/5000, SSE 39.4562/0.1, Gradient 0.485735/1e-006
TRAINGDX, Epoch 60/5000, SSE 39.5979/0.1, Gradient 0.387782/1e-006
TRAINGDX, Epoch 80/5000, SSE 39.6081/0.1, Gradient 0.387929/1e-006
TRAINGDX, Epoch 100/5000, SSE 39.5559/0.1, Gradient 0.445316/1e-006
TRAINGDX, Epoch 120/5000, SSE 39.2765/0.1, Gradient 0.758668/1e-006
TRAINGDX, Epoch 140/5000, SSE 35.941/0.1, Gradient 1.34484/1e-006
TRAINGDX, Epoch 160/5000, SSE 23.9786/0.1, Gradient 2.73872/1e-006
TRAINGDX, Epoch 180/5000, SSE 1.57322/0.1, Gradient 0.898383/1e-006
TRAINGDX, Epoch 196/5000, SSE 0.0909575/0.1, Gradient 0.0769913/1e-006
TRAINGDX, Performance goal met.




5. Testing the Neural Network
Simulate the testing dataset

[a,b]=max(sim(net,Ptest));
disp(b);

1 2 3 4 5 6 7 8 9 10



Do note that there might be some misclassifications on the simulated result with different training properties. The accuracy could be improved by better features extraction techniques as well as the selection of NN's properties.

* MATLAB® is the registered trademarks for The MathWorks, Inc

The relevant files can be found at:
(link to the files will be provided soon…)

Character Recognition Example (II):Automating Image Pre-processing

Most of the time we would like to automate our image pre-processing stage especially during the data extraction for database. In other words, the program should be able to extract the characters one by obe and map the target output for training purpose. The following code shows the example:

1. Read Image
This cell of codes read the image to MATLAB workspace

I = imread('sample.bmp');
imshow(I)

2. Convert to grayscale image
This cell of codes convert the RGB to gray

Igray = rgb2gray(I);
imshow(Igray)


3. Convert to binary image
This cell of codes convert the gray to binary image

Ibw = im2bw(Igray,graythresh(Igray));
imshow(Ibw)


4. Edge detection
This cell of codes detect the edge of the image

Iedge = edge(uint8(Ibw));
imshow(Iedge)

5. Morphology
This cell of codes perform the image dilation and image filling on the image

Image Dilation

se = strel('square',2);
Iedge2 = imdilate(Iedge, se);
imshow(Iedge2);


Image Filling

Ifill= imfill(Iedge2,'holes');
imshow(Ifill)


6. Blobs analysis
This cell of codes find all the objects on the image, and find the properties of each object.

[Ilabel num] = bwlabel(Ifill);
disp(num);
Iprops = regionprops(Ilabel);
Ibox = [Iprops.BoundingBox];
Ibox = reshape(Ibox,[4 50]);
imshow(I)

50


7. Plot the Object Location
This cell of codes plot the object locations

hold on;
for cnt = 1:50
rectangle('position',Ibox(:,cnt),'edgecolor','r');
end


By this, we are able to extract the character and pass to another stage for "classification" or "training" purpose. (To be continue...)

* MATLAB® is the registered trademarks for The MathWorks, Inc

The required files can be found at:
(link for the required files will be provided soon...)

Character Recognition Example (I): Image Pre-processing

This example illustrates simple way of character recognition. It just serves as a kick start for beginers by introducing them simple coding in MATLAB for character recognition.

Some useful example for image pre-processing before the recognition stage is shown as follow:

1. Manual Cropping
This cell of codes allow the user to crop the image manually, which is important proccess especially the programmer would like to manipulate the data more in details.

img = imread('sample.bmp');
imshow(img)
imgGray = rgb2gray(img);
imgCrop = imcrop(imgGray);
imshow(imgCrop)


2. Resizing
This cell of codes magnify the image for 5 times. Resize function is important when the size of the character are not standard, especially in the handwritting recognition program.

imgLGE = imresize(imgCrop, 5, 'bicubic');
imshow(imgLGE)



3. Rotation
This cell of codes rotate the image for 35 degree. Some of the printed documents might not in the right degree as expected. This operation coulf make the character to our desired angle.

imgRTE = imrotate(imgLGE, 35);
imshow(imgRTE)



4. Binary Image
This cell of codes convert the image to binary image. Definitely, the speed and also the accuracy will increse if this operation is perform properly.

imgBW = im2bw(imgLGE, 0.90455);
imshow(imgBW)

Detecting Object in an Image

1. How to detect an object in an image?
Determining the features from the object that you want to detect is the key. The feature in this case is something that differentiates the object from others, such as color, shape, size, etc…

2. What are the techniques for object detection?
The image processing techniques such as morphology or color processing usually did this job. A simple example in MATLAB® of detecting ‘white rabbit’ is shown as follow, in this case, ‘color’ is the feature used to distinguish the white rabbit from other:

% Original Image
S = imread('pic3b.jpg');
imshow(S);

% Gray scale image
S2 = rgb2gray(S);
imshow(S2);

% Find the white color
S3 = S2>180;
imshow(S3);

% Morphology technique, image erosion to erase the unwanted components
se = strel('line',10,90);
S4 = imerode(S3,se);
se = strel('line',10,0);
S4 = imerode(S4,se);
imshow(S4)

% Labeled the component(s), and plot the centroid on the original image
S5 = bwlabel(S5);
[x,y]=find(S6==1);
imshow(S)
hold on;plot(mean(y),mean(x),'r*')

More information of image processing techniques can be found by searching "morphology", "morphological" from the search engine or the google search bar at the right hand site of this page.

* MATLAB® is the registered trademarks for The MathWorks, Inc

Drawing Shapes by Overwriting Pixel Value

1. How to highlight certain portion on an image?
The basic concept of highlighting part of an image is “Overwriting Pixel Value” on the image. We start from the basic idea on how to mask portion of image with blank sub-image (black color sub-image). Fig 1 shows the image with the size of 128x128x3 in which 3 represent s RGB. (In grayscale image 3 layers are the same). The image at the right hand site shows a blank sub-image is placed at the upper left of the original image. The MATLAB® code to perform the operation are as follow:

S = imread('t3.jpg');
imshow(S);
Sblack = uint8(zeros(20,20,3));
S2 = S;
S2(1:20,1:20,:) = Sblack;
imshow(S2);

Fig 1

2. How to create a color mask rather than black color mask?
Since the 3 layers of image matrix represent RGB layers of the image, we can create the red color mask using following command, and the results are shown in fig 2.

Sred = Sblack;
Sred(:,:,1)=255;
S2 = S;
S2(1:20,1:20,:) = Sred;
imshow(S2);

Fig 2


3. How to create a transparent mask?
Simple enough, just play with the values R value, and perform the image addition rather than overwriting the value as follow:

Sred = Sblack;
Sred(:,:,1)=200;
S2 = S;
S2(1:20,1:20,:) = S2(1:20,1:20,:) + Sred;
imshow(S2);

Fig 3

4. Finally, how to create an outline for the image?

linelength = 10;
Sblack = uint8(zeros(128+linelength*2,128+linelength*2,3));
S2 = Sblack;
S2((1+linelength):(end-linelength),(1+linelength):(end-linelength),:)=S;
imshow(S2);

Fig 4

The “linelength” variable is the outline length in pixel.

* MATLAB® is the registered trademarks for The MathWorks, Inc