How to recognize rectangles in this image?

Question

Hi,

I have a image with horizontal and vertical lines. In fact, this image is the BBC website converted to horizontal and vertical lines. My problem is that I want to be able to find all the rectangles in the image. I want to write a computer program to find all the rectangles. Does anyone know how to do this or suggest ideas on how to get started? This task is easy for me as a person to find the visual rectangles, but I am not sure how to describe it as a program.

Image at http://www.ironnine.com/rectangles.png is the BBC website here http://www.bbc.co.uk/

Thanks, Philip

---

Update to this, I wrote the code which converts the BBC website image to the horizontal and vertical line, the problem is these lines do not completely meet at the corners and sometimes they do not completely form a rectangle. Thanks!

Answer 1

iterate from left to right until you hit a color pixel then use modified flood fill algorithm. more info on the algo flood fill @ wiki

Answer 2

another approach would be to find ANY colored pixel on the image then go with

while(pixel under current is colored)
{
  lowest pixel coordinate = pixel under current
  current = pixel under
}

then do the same upwards. now u have defined a single line. then use ends of the lines to approx match lines into rectangles. if they are not pixel perfect you could do some kind of tresholding.

Answer 3

The flood fill would work, or you could use a modification of an edge tracking algorithm.

what you do is: create a 2d array (or any other d2 data struct)- each row represents a horizontal pixel line on screen, and each column a vertical line

iterate through all the pixels, left to right, and whenever you find a coloured one add its coordinates to the array

iterate through the array and findying lines and storing the begin and end pixel for each one (different data structure)

knowing that the begin of each line is its left/top pixel, you can easily check to see if any 4 lines comprise a rectangle

Answer 4

Assuming it's a reasonably noise free image (not a video of a screen) then one of the simple floodfill algorithms should work. You might need to run a dilate/erode on the image to close up the gaps.

The normal way to find lines is a Hough transform ( then find lines at right angles) Opencv is the easiest way.

Take a look at this question http://stackoverflow.com/questions/279410/opencv-object-detection-center-point

Answer 5

There are several different approaches to your problem. I'd use a morphological image processing tool like this one. You will have the flexibility to define "rectangle" even something that not "exactly closed" (where the fill algorithm will fail).

Another possibility could be to use a machine learning approach, which basically is more data-driven than definition-driven like the previous one. You'll have to give your algorithm several "examples" of what a rectangle is, and it will eventually learn (with a bias and an error rate).

Answer 6

I believe you are looking for the generalized Hough transform.

Answer 7

In computer vision there is a algorithm called Generalized Hough Transform which maybe can solve your problem. There should be open source code having implemented this algorithm. Just search for it.

Answer 8

To get from the image you have with the nearly touching horizontal and vertical lines to just the rectangles:

1. Convert to binary (i.e. all lines are white, the rest is black)
2. Perform a Binary dilation (here you make every pixel that touches a white pixel in the source image or is a white pixel in the source image white. Touch is straight only (so each pixel "touches" the pixels to its left, right, above and below it) this is called "4-connected"
3. repeat step 3 a few times if the gaps between the ends are larger then 2 pixels wide, but not too often!
4. Perform a skeleton operation (here you make every pixel in the output image black if it is a white pixel in the source image that touches at least one black pixel and the white pixels it touches (in the source image) all touch eachother. Again touch defined with 4-connectedness. See sample below.
5. Repeat step 4 untill the image doesn't change after a repeat (all white pixels are line ends or connectors)

This will, with a bit of luck, first show the boxes with thick fat lines, leaving thick fat artifacts all over the image (after step 3) and then then after step 5 all thick fat artifacts will have been removed, while all boxes remain. You need to tweek the number of repeats in step 3 for best results. If you're interested in image morphology, this is the book of a really good introductory course I took.

Sample: (0=black, 1=white, pixels in the center of each 3x3 block are being considered, input left, output right)

011 => 011    
011 => 001  all other white pixels touch, so eliminate      
011 => 011    

010 => 010    
010 => 010  top pixel would become disconnected, so leave      
010 => 010    

010 => 010    
010 => 000  touches only one white pixel, so remove     
000 => 000    

010 => 010    
111 => 111  does not touch black pixels, leave    
010 => 010    

010 => 010    
011 => 011  other pixels do not touch. so leave    
000 => 000

Answer 9

Opencv (image processing and computer vision library written in c) has implementation for hough transform (the simple hough transform find lines in an image, while the generalized one finds more complex objects) so that could be a good start. For the rectangles which do have closed corners there are also corner detectors such as cornerHarris which can help.

I ran the houghlines demo provided with opencv and here's the result on the image you gave (detected lines marked in red):