Fast algorithm to detect the inclination of the lines in the image

Question

My requirement is to find the inclination of the lines (all 8 lines) surrounding the data matrix, as shown in the edge detected image:

The two main restrictions:

• The inclination detected should have precision of at least 0.1 deg (the best achievable in this image)
• Time taken should be less than 30 ms

I am implementing the algo on a Blackfin DSP, and have used Blackfin image processing toolbox.

I tried using Hough transform and Contour detection to find out the lines and thus their inclinations however the time limit exceeds. Any suggestions to use a different algorithm or optimize this one would help.

[for my use case the higher the angle precision the better, I am targeting at least 0.02 - 0.05 with a higher resolution image]

Answer 1

1. find bounding box

   scan all points and found xmin,ymin,xmax,ymax of set pixels

2. find the gaps

   cast scan lines through half of bounding box remembering/measure the gap sizes. To avoid line miss (due to holes) you can cast more scan lines or scan with wider ray.

   If you need some examples for ray cast/scanning see:

   • How to find horizon line efficiently in a high-altitude photo?

3. segmentate the image into regions

   just shrink bounding box by some fraction (50%) of a gap ... something like this:

   

   forming 8 rectangular regions each one with single line without noise from the edges.

4. regress/fit lines

   The idea is to make a list of all set pixels for each region separately and fit a line that has smallest distance to all of them.

   I would try to use this:

   • Given n points on a 2D plane, find the maximum number of points that lie on the same straight line

   Or use approximation search and fit something like

   • Curve fitting with y points on repeated x positions

   just ignore the curvature and fit line equation parameters directly instead cubics.

   After the lines are fitted you can compute their slope directly by atan2(dy,dx)

Answer 2

A fast and easy approch would be to scan every line and column for the first and second white pixel starting from left, right, top and bottom. Then simply use some robust line fit algorithm to get the lines.

Unless you did not already try to do that you can reduce the data for Hough transform or other algorithms by cropping the image down to DMC size.

The required angle accuracy cannot be achieved as you don't have enough resultion. And even if you had your results would suffer from any noise and outliers.