Using flood-fill to detect corners of a rectangle

243 views Asked by At

I am trying to find corners of a square, potentially rotated shape, to determine the direction of its primary axes (horizontal and vertical) and be able to do a perspective transform (straighten it out).

From a prior processing stage I obtain the coordinates of a point (red dot in image) belonging to the shape. Next I do a flood-fill of the shape on a thresholded version of the image to determine its center (not shown) and area, by summing up X and Y of all filled pixels and dividing them by the area (number of pixels filled).

Given this information, what is an easy and reliable way to determine the corners of the shape (blue arrows)?

I was thinking about keeping track of P1, P2, P3, P4 where P1 is (minX, minY), P2 is (minX, maxY), P3 (maxY, minY) and P4 (maxY, maxY), so P1 is the point with the smallest value of X encountered, and of all those P, the one where Y is smallest too. Then sort them to get a clock-wise ordering. But I'm not sure if this is correct in all cases and efficient.

PS: I can't use OpenCV.

Situation

2

There are 2 answers

2
fana On

Looking your image, direction of 2 axes of the 2D pattern coordinate system will be able to be estimated from histogram of gradient direction.

When creating such histogram, 4 peeks will be found clearly.

  • If the image captured from front (image without perspective, your image looks like this case), Ideally, the angles between adjacent peaks are all 90 degrees. directions of 2 axes of the pattern coordinate system will be directly estimated from those peaks. After that, 4 corners can be simply estimated from "Axis aligned bounding box" (along the estimated axis, of course).

  • If not (when image is a picture with perspective), 4 peaks indicates which edge line is along the axis of the pattern coordinates. So, for example, you can estimate corner location as intersection of 2 lines that along edge.

0
Alex Suzuki On

What I eventually ended up doing is the following:

  1. Trace the edges of the contour using Moore-Neighbour Tracing --> this gives me a sequence of points lying on the border of rectangle.

  2. During the trace, I observe changes in rectangular distance between the first and last points in a sliding window. The idea is inspired by the paper "The outline corner filter" by C. A. Malcolm (https://spie.org/Publications/Proceedings/Paper/10.1117/12.939248?SSO=1).

This is giving me accurate results for low computational overhead and little space.