English 中文(简体)
How to recognize rectangles in this image?
原标题:

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 is the BBC website here http://www.bbc.co.uk/


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!

最佳回答

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): alt text
(source: splintec.com)

问题回答

I believe you are looking for the generalized Hough transform.

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.

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 OpenCV Object Detection - Center Point

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

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

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.

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

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    




相关问题
Calculating corresponding pixels

I have a computer vision set up with two cameras. One of this cameras is a time of flight camera. It gives me the depth of the scene at every pixel. The other camera is standard camera giving me a ...

Image comparison algorithm

I m trying to compare images to each other to find out whether they are different. First I tried to make a Pearson correleation of the RGB values, which works also quite good unless the pictures are a ...

How to recognize rectangles in this image?

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

Resources for Image Recognition

I am looking for a recommendation for an introduction to image processing algorithms (face and shape recognition, etc.) and wondered if anyone had an good recommendations, either for books, ...

How to programmatically disable the auto-focus of a webcam?

I am trying to do computer vision using a webcam (the model is Hercules Dualpix). I know it is not the ideal camera to use, but I have no choice here. The problem is the auto-focus makes it hard/...

Computing object statistics from the second central moments

I m currently working on writing a version of the MATLAB RegionProps function for GNU Octave. I have most of it implemented, but I m still struggling with the implementation of a few parts. I had ...

Viola-Jones face detection claims 180k features

I ve been implementing an adaptation of Viola-Jones face detection algorithm. The technique relies upon placing a subframe of 24x24 pixels within an image, and subsequently placing rectangular ...

Face detection and comparison

I m running a small research on face detection and comparison for my article. Currently, I m using rapid face detection based on haar like features based on OpenCV cascade (I ll implement learning ...

热门标签