Measuring rectangles at odd angles with a low resolution input matrix (Linear regression classification?)

Question

I'm trying to solve the following problem:

Given an input of, say,

0000000000000000
0011111111110000
0011111111110000
0011111111110000
0000000000000000
0000000111111110
0000000111111110
0000000000000000

I need to find the width and height of all rectangles in the field. The input is actually a single column at a time (think like a scanner moves from left to right) and is continuous for the duration of the program (that is, the scanning column doesn't move, but the rectangles move over it).

In this example, I can 'wait for a rectangle to begin' (that is, watch for zeros changing to 1s) and then watch it end (ones back to zeros) and measure the piece in 'grid units'. This will work fine for the simple case outlined above, but will fail is the rectangle is tilted at an angle, for example:

0000000000000000
0000011000000000
0000111100000000
0001111111000000
0000111111100000
0000011111110000
0000000111100000
0000000011000000

I had originally thought that the following question would apply:

http://stackoverflow.com/questions/1726632/dynamic-programming-largest-square-block

but now i'm not so sure.

I have little to no experience with regression or regression testing, but I think that I could represent this as an input of 8 variables.....

Well to be honest i'm not sure how I would do this at all. The sizes that this part of the code extracts need to be fitted against rectangles of known sizes (ie, from a database).

I initially thought I could feed the known data as training exercises and store the positive test results, but I'm really not sure where to go from here.

Thanks for any advice you might have.

Answer 1

Collect the transition points (from a 1 to a 0 or vice-versa) as you're scanning, then figure the length and width either directly from there, or from the convex hull of each object.

If rectangles can overlap, then you'll have bigger issues.

Answer 2

I posed this question to a friend, and he suggested:

1. When seeing a 1 for the first time, store it as a new shape. Flood fill it to the right, and add those points to the same shape.
2. Any input pixel that is'nt in a shape now is a new shape. Do the same flood fill.
3. On the next input column, flood again from the original shape points. Add new pixels to the corresponding shape
4. If any flood fill does not add any new pixels for two consecutive columns, you have a completed shape. Move on, and try to determine it's dimensions

This then leaves us with getting the dimensions for a shape we isolated (like in example 2).

For this, we thought up:

1. If the number of leftmost pixels in the shape is below the average number of pixels per column, then the peice is probably rotated. Thus, find the corners by getting the outermost pixels. Use distance formula between all of them. Largest = hypotenuse, others = width or height.
2. Otherwise, this peice is probably perfectly aligned, so the corners are probably just the topleft most pixel, bottom right most pixel, etc

What do you all think?

Answer 3

I'd take following steps:

1. get all columns together in a matrix (this is needed for proper filtering)
2. now apply a filter (need to google for it a bit) to sharpen edges and corners
3. create some structure to hold data for next steps (this can have many different solutions, choose your favorite and/or optimal)
4. scan vertically (column by column) and for each segment of consequent 'ones' found in a column (segment means you have found it's start end end y coordinates) do:
   1. check that this segment overlaps some segment in the previous column
   2. if it does not, consider this a new rect. Create a rect object and assign it's handle to the segment. for the new rect, update it's metrics (this operation takes just the segment's coordinates - x, ymin, ymax, and will be discussed later)
   3. if it does, assume this is the same rect, take the rect's handle, assign this handle to the current segment then get the rect by it's handle and update it's metrics

That's pretty it. After this you will have a pool of rect objects each having four coordinates of its corners. Do some primitive math to approximate rect's width and height.
So where is the magic? Well, it all happens in the update rect metrics routine.

For each rect we have 13 metrics:

• min X => ymin1, ymax1
• max X => ymin2, ymax2
• min Y => xmin1, xmax1
• max Y => xmin2, xmax2
• average vertical segment length

First of all we have to determine if this rect is properly aligned within our scan grid. To do this we compare values average vertical segment length and max Y - min Y. If they are the same (i'd choose a threshold around 97%, and then tune it for the best results), then we assume the following coordinates for our rect:

1. (min X, max Y)
2. (min X, min Y)
3. (max X, max Y)
4. (max X, min Y).

In other case out rect is rotated and in this case we take it's coordinates as follows:

1. (min X, (ymin1+ymax1)/2)
2. ((xmin1+xmax1)/2, min Y)
3. (max X, (ymin2+ymax2)/2)
4. ((xmin2+xmax2)/2, max Y)