Find rectangle on scanned image

Find rectangle on scanned image

Post by Nicholas S » Sat, 30 Apr 2005 09:48:50

Hey all,

I'm trying to locate the corners of a black (scaled, rotated between 5
and 40 degrees) rectangle on a scanned white page. I can find at least
one pixel of this rectangle, and I thought that I'd use the following
strategy to find the corners of the rectangle:

1. Identify all pixels in the rectangle (floodfill).
2. Find the top-most, left-most, right-most and bottom-most pixel.
3. If topmost.x<rightmost.x then begin
TopLeft=topmost;
TopRight=rightmost;
BottomLeft=leftmost;
BottomRight=bottommost
end else begin
Topleft=leftmost;
TopRight=topmost;
BottomLeft=bottomost;
BottomRight=rightmost;
end;

Is there any better way of doing this?

Cheers,
Nicholas Sherlock

 
 
 

Find rectangle on scanned image

Post by Nicholas S » Sat, 30 Apr 2005 09:54:50


Whoops, these should be the steps.

Cheers,
Nicholas Sherlock

 
 
 

Find rectangle on scanned image

Post by Nils Haec » Sun, 01 May 2005 00:50:12

...XX.........
..XXXXXX......
.XXXXXXXXXX...
XXXXXXXXXXXXXX
...XXXXXXXXXX.
......XXXXXX..
.........XX...

Hi Nick,

Suppose you have the rectangle above, assuming you already found the outer
bounds.

I would just search the 4 edges like this:

leftupper edge: take two points, in first row the most left pixel, in first
column most upper pixel
(0, 3) and (3, 0)

right upper side: first row most right pixel, last column most upper pixel
(0, 4) and (3, 13)

etc.

You will get four lines, from which you can then create the intersections.
Google for line-line intersection code.

Kind regards,

Nils
 
 
 

Find rectangle on scanned image

Post by Mattias An » Sun, 01 May 2005 04:32:39


One approach would be to use the Hough transform. The Hough transform can
find certain geometric features in an image, such as lines and circles.

The algorithm for detecting straight lines can be outlined as follows:

1) First you filter the image with an edge detection algorithm. Many
different algorithms exists for this purpose. There is one algorithm known
as "Canny's edge detector", which is quite powerful.

2) Now, for each pixel, you need to store the set of feasible lines that can
pass through it somehow. Of course there are infinitely many such lines, so
you need to perform some kind of discretization.

We know from basic algebra that a line can be explicitly determined in the
following parametric form:

y = ax + b

By varying the constants a and b we can find any number of lines passing
through the point (x, y). However, for our purpose, it turns out that the
following parametric representation is better:

rho = x cos(theta) + y sin(theta)

since now we do not need to worry about the fact that the constant a
approaches infinity for completely vertical lines. If we discretize theta
into a fixed number of angles, then we can also determine the corresponding
values of rho for the point (x, y). Now, the trick is to accumulate a
two-dimensional matrix at the positions (rho, theta) for each coordinate (x,
y) that corresponds to an edge pixel. This way certain combinations of (rho,
theta) will appear more frequently when they lie on the same line.

3) Finally you should find the largest values in the accumulated matrix.
These corresponds to the (rho, theta) values that are most likely to
represent a line. Thus, you can now use this information for finding the
corners in a rotated rectangle or some other polygonal object (i.e. by
looking at the intersections of the lines).

Here is a small example application I wrote for Graphics32:

http://www.yqcomputer.com/

Cheers,
Mattias Andersson
 
 
 

Find rectangle on scanned image

Post by Nils Haec » Sun, 01 May 2005 08:16:51

Hi Mattias,

Interesting.. However, the link doesn't seem to work. Can you check it?

Kind regards,

Nils

"Mattias Andersson" < XXXX@XXXXX.COM > schreef in bericht
 
 
 

Find rectangle on scanned image

Post by Mattias An » Sun, 01 May 2005 19:34:22

Hi Nils,

I've checked it, and it works. Could you try once more?

Kind regards,

Mattias
 
 
 

Find rectangle on scanned image

Post by Nils Haec » Mon, 02 May 2005 00:57:58

Yes, now it works again, thanks!

Nils

"Mattias Andersson" < XXXX@XXXXX.COM > schreef in bericht
 
 
 

Find rectangle on scanned image

Post by Nils Haec » Mon, 02 May 2005 01:24:02

I've looked at it in detail and it is pretty amazing that this works :)

An extra step to make the lines more accurate could be:
- Threshold the hough map, and create blob regions of the values above the
threshold.
- Calculate for each region found (corresponding to a line) the center of
gravity with subpixel accuracy.

That way, you'll find lines even with higher accuracy then possible with the
discretisation. Also, you'll avoid drawing more than one line for each edge.

I guess for circular hough you do the same: trying to find possible circles
that go through that point?

Nils

"Mattias Andersson" < XXXX@XXXXX.COM > schreef in bericht
 
 
 

Find rectangle on scanned image

Post by Mattias An » Mon, 02 May 2005 05:30:19


Sounds like an interesting approach, but I'm not fully convinced that the
center of gravity will yield the best estimation. I think it would be better
to examine the maximum value in each region instead (since the intensity
values are not located radially symmetric around the maximum value).


Yes, exactly -- in this case you will get a slightly different parameter
space. I found this page which outlines the idea quite neetly:

http://www.yqcomputer.com/ ~ths/rt2/col/h7/7contourENG.html

If you want to find circles with a fixed radius, then you need a
two-dimensional parameter space. For circles with arbitrary radius you need
one more parameter, so you will perform accumulation in a three-dimensional
parameter space. You can do this in even higher dimensions (e.g. for
ellipses), but this would mean you would need an accumulator matrix of size
n^d, and the computations would be rather expensive.

Mattias
 
 
 

Find rectangle on scanned image

Post by Mattias An » Mon, 02 May 2005 10:05:40


Sounds like an interesting approach, but I'm not fully convinced that the
center of gravity will yield the best estimation. I think it would be better
to examine the maximum value in each region instead (since the intensity
values are not located radially symmetric around the maximum value).


Yes, exactly -- in this case you will get a slightly different parameter
space. I found this page which outlines the idea quite neatly:

http://www.yqcomputer.com/ ~ths/rt2/col/h7/7contourENG.html

If you want to find circles with a fixed radius, then you need a
two-dimensional parameter space. For circles with arbitrary radius you need
one more parameter, so you will perform accumulation in a three-dimensional
parameter space. You can do this in even higher dimensions (e.g. for
ellipses), but this would mean you would need an accumulator matrix of size
n^d, and the computations would be rather expensive.

Mattias