Tutorial: Finding Rectangles with NO OpenCV
Task: For any given image write a program to find all rectangular objects which are darker than the background. Draw the located rectangles on the output image.
Method: Linear Hough transform with advanced filtering
Restrictions: Solid colour rectangles only, Many wide-bordered rectangles slow down the program
Tutorial type: Algorithm oriented, written in Python
Requirements: Python 2.7, Numpy 1.9.2, Matplotlib 1.4.3, OpenCV 2.3 (used for Canny only!)
The tutorial code is written in Python, but it's well readable and can be implemented in Matlab, R, JAVA or any other programming language. In order to understand the subject more all the functions are built bottom-up with no outside resources used. Some examples of how the program performs are presented below:
To find partly not visible rectangles there is possibility to slightly modify the code.
First we open an image, convert it to grayscale, blur and find edges. This is the only place where we will be using OpenCV. Image blurring and finding edges are crucial to the success of finding rectangles.
Here is the saved output files for both original and edged versions.
Hough Transform and Clustering
For Hough transformation we will define our own function:
The full function looks like this:
Some questions that may arise from the code:
Why Hough matrix has such dimensions? Dimension 1 ranges are defined by maximum value for sin(x)+cos(x) which is sqrt(2). So it's maximum is (numColumnsImage+numRowsImage)*sqrt(2). Dimension 2 is theta which ranges from -90 to 90 in degrees. Every dimension has it's resolution which is taken as parameter to the function, which divides the number of points we will count.
Why we use thresholdPixels? We want to consider only points that are edges and in some cases edged image may be not boolean and we want to filter it by threshold.
Why we use filtering? Well, it's unnecessary, but it speeds up the program significantly. On the other hand it sometimes might produce wrong results, for example when we have multiple rectangles in the image, where their contour lines are very nearby in Hough space (same angle, or nearby r value [r=x*cos(th)+y*sin(th)]).
Next chapter will describe filtering in details.
Clustering and Filtering
We have 7 real lines in our image. We may choose appropriate thresholdVotes parameter to filter out unnecessary points in Hough plane, but usually the process is automatic and the program does not know the correct thresholdVotes value. For this reason we got 1060 of points after Hough transform and only 26 points after using clustering and filtering. So we have 19 false-positives for now. Points higher than thresholdVotes in Hough plane before and after filtering look like that:
The results on the image looks like this - found lines before and after filtering:
For easy plotting found lines in Hough space knowing rho and theta we define our own function plotHoughLines:
Find Corners from Hough Lines
Continue the main program using found rho and theta for every found line. Next steps are to find all parallel lines, to pair them, find perpendicular pairs, and solve linear equations to find corners at each intersection.
Filter Wrong and Duplicate Rectangles
This part consists of four types of filtering to avoid false-positives. We will discuss each of them one by one.
Remove if small: This is the most simple check, where the rectangle is deleted if any of it's sides is shorter than specific value. In our case we choose it to be 20 pixels.
Remove if standard deviation inside rectangle is high: If standard deviation is high, that may mean that rectangles has ended somewhere inside area of our corners. But this check is the one which restricts the code work only with solid rectangles.
Remove if brighter: The requirement by task is fulfilled by checking the outer color of the rectangle. It is completed by selecting four points outside rectangle in the line from the midpoint to all for middles of sides.
Remove if many in same place: After all the filtering there still is a problem where many rectangles are correctly found, but the lines differs by few pixels. We run extra check to leave only rectangles best fitting the edged image.
Here is the final result:
Other Custom Functions Used
Here we define some other custom function that we used in the tutorial.
Length between two points (given coordinates) in Cartesian plane
Find all unique rows in a list by first reordering each row ascending
Reorder corners of quadrangle in such a way that nearby corners follows each other
Get angle in radians between two vectors defined by points in coordinate system (absolute value or signed value)
Convert rgb image to grayscale
Blur image using flat 2x2 kernel (averaging)
Download the Code
The source code is available on GitHub.