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

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

...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

..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

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

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

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

Kind regards,

Nils

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

Hi Nils,

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

Kind regards,

Mattias

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

Kind regards,

Mattias

Yes, now it works again, thanks!

Nils

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

Nils

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

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

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

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

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

1. GDI+ - finding a rectangle inside another rectangle

2. How often will a full scan find malware that a quick scan didn't find?

3. regionprops to find the dimension of a rectangle image

4. Rectangles, rectangles and more rectangles!

5. Best fit of rectangles in a bigger rectangle already having prefilled rectangles

6. To find scan path(pattern)in an image

7. find lost text when scanned image was imported

8. how to find my scanned saved image

9. Scans with Microsoft Document Imaging are blank yet Fax and Scan w

10. Windows Fax and Scan: Preview or scan images as separate files

11. Source Rectangle and Target Rectangle

12. A Rectangle Contains/touches other Rectangle

13. how Can i convert from rectangle to rectangle F

14. Looking for rectangle in generalized rectangle

15. table in rectangle causes rectangle to resize

10 post • Page:**1** of **1**