Rectangle detection in "real life" images

Question

I have seen a lot of posts here and on SO and on various websites, using Matlab, OpenCV, name it, on how to detect rectangles in an image. I have done it myself too, using Matlab. My usual steps were:

1. Grayscale the image (if not done)
2. Blur the image (if needed)
3. Apply an edge detector (e.g. Canny, LoG, etc., tried a lot of them)
4. Apply the various steps of Hough Transform to find lines
5. Use some logic in order to tell which line combinations are forming rectangles

I have no problem with these. The problem is that (and with most of other posts I found) it works with relatively simple images, generally synthetics one with few textures, or with high contrast (like a black rectangle surrounding text on a white sheet of paper). Well, maybe that's only me, but I can't make it work with more complex images, where the edgemap might be quite noisy, where I can't afford to manually tune all sort of parameters and thresholds to "make it work".

Here is a dummy project to illustrate the kind of situation I want to address. Imagine that I have a lot of books (dozens) layered and overlapping on a table and I have a camera above, at the right distance to view all of the scene and only the scene. There is no distortion of lens, no blur from the lighting and the resolution is pretty good. The books may be rotated at any angle, they may be of different sizes (though one could assume there is a min and max size), their cover may or may not be different from each others, with possibly images, text, etc. but no colour information is present.

I want to be able to identify the location of every book in that scene. Then, knowing their location, I will be able to extract the appearance of their covers and maybe retrieve their names from a database using these covers (just an example, this part is not important now). Oh, I cannot turn the problem around and use the database to search for the presence of a given book (it would be quite long and I try to constrain this example to rectangle detection).

Now, imagine that, given all the information known about the problem at hand, I conclude that the best solution would be to search for the presence of rectangles in the scene, knowing that books are indeed rectangles and finding all the rectangle could give me a good start. Oh, and I want to do it in real time.

What would you do? I have looked at a some papers from the literature, a lot are doing contour detection to detect horses, mugs, bottles, but they are quite slow to detect the shapes and more I have noticed that often just plain simple rectangles are, well, too simple, not enough distinctive for the algorithms to find.

I am not looking for a ready made answer. I just wonder if anyone has a thought on this. I have not included a list of papers or implementation I tested partly because this question is quite long enough and also I don't want to orient the answers. Remember, this example is made up and what I really want is to detect rectangles. And, disclosure, eventually in my career I assume I will have to detect rectangles (or other shapes) so I was quite ashamed that I wasn't able to do it on real images with the knowledge I have right now :S

Thanks

Answer 1

I think you would use a 2D Matched Filter. You would convolve your image with a series of rectangles. The peaks in the resulting images would be the location of your books. You could do this quickly in by Fourier transforming your image and using the known function for a rectange in 2D Fourier space (its two sinc functions, multiplied).

Answer 2

I have been working on a similar problem of detection of rectangular contours that may also be fragmented or incomplete. In my case the application is detection of so called livestock enclosures in remotely sensed image, see Web: https://www.mmsp.uni-konstanz.de/research/projects/completed-research-projects/detection-of-archaeological-sites-in-high-resolution-remotely-sensed-imagery/ On this website you can find a sequence of papers on that topic, but you might be mostly interested in the latest one.

My problem is even harder because these contours are faint, may be incomplete or fragmented and appear on complex cluttered background. As you have mentioned there is no on-the-shelf algorithm for detection of “real” distorted rectangles of various sizes. You are also very right saying that rectangles are too simple – not enough distinctive for algorithms that detect more complex unique shapes. This is especially true if you have complex background. Another problem with many already developed algorithms is the necessity for the large number of training examples.

The approach I have developed (see the web site for details) is tailored to my task of detection of individual rectangular contours in large images. It may be too sensitive for other applications with many close to each other rectangles. In that case it may detect false rectangles in between real ones if they are sufficiently aligned.