2

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

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]

kaustubh
  • 31
  • 1
  • 4
  • 5
    How do you expect to achieve this precision? The outer lines have a length of about 260 px. You can detect a position on the line only with an error of ± 0.5 px (the image is not suitable for subpixel methods). This alone results in an uncertainty of at least `arc tan(0.5 / 260) = 0.1°`. – Nico Schertler Mar 10 '16 at 14:56
  • what do you want to achieve? I can't think of any application where you need such accuracy for a DMC. share more information please – Piglet Mar 10 '16 at 20:32
  • Added answer with I think fast enough approach. The precision problem is still there and greatly depends on the quality of a fit and input image resolution/quality. btw looks like some SMD/BGA placing application or am I wrong? – Spektre Mar 10 '16 at 21:44
  • @NicoSchertler true, i intend to 1. Increase the resolution of the image 2. increase the size of the out lines in the increased resolution. Though all these will still not contribute to the precision needed, i am hoping the presence of 8 lines will average out the errors and give a better result. – kaustubh Mar 12 '16 at 13:02
  • @Spektre i need this to find the orientation of the AGV system, which localizes based on the data matrix and navigates to the next such data matrix based on the orientation of this one, which makes the precision a prerequisite, otherwise i won't end up on the next such sticker! – kaustubh Mar 12 '16 at 13:08
  • @kaustubh weird I did not see notification. anyway if resulting precision is not enough you still have approximate position so you can scan cone or circle around it (depends on if the distance is known) – Spektre Mar 16 '16 at 10:52

2 Answers2

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:

  3. segmentate the image into regions

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

    regions

    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:

    Or use approximation search and fit something like

    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)

Community
  • 1
  • 1
Spektre
  • 49,595
  • 11
  • 110
  • 380
  • thanks for the suggestion. Let me try this out and i shall let you know if it works in the time constraint. in case required i can identify bottle necks and iterate on the solution. – kaustubh Mar 12 '16 at 13:12
0

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.

Piglet
  • 27,501
  • 3
  • 20
  • 43