Is there any super fast algorithm for finding LINES on picture?
Asked Answered
O

4

22

So I have Image like this

 CG generated bathroom
(source: de-viz.ru)

I want to get something like this (I hevent drawn all lines I want but I hope you can get my idea)

 Black & White CG generated bathroom with some red lines  between tiles
(source: narod.ru)

I need some super fast algorithm for finding all straight lines on it. I want to give to algorithm parameters like min length and max line distortion. I want to get relative to picture pixel coords start and end points of lines.

So on this picture to find all lines between tiles and thouse 2 black lines on top.

So I need algorithm for super fast finding straight lines of different colors on picture.

Is there any such algorithm? (super duper fast=)

Ohg answered 8/4, 2010 at 0:6 Comment(3)
Could you mark the lines you want to find? What do you mean "dalles"? Tiles?Unsuccess
dalles = Tiles in my dictionary...) yes) I want for example ALL straight lines with width of less then 25 pixels and with min length of 100 pixels.Ohg
first link is dead.Handball
S
17

You need to use sophisticated image processing methods such as Canny Edge Detection, Marr-Hildreth edge detection, Gaussian Filtering and Hough Transform etc.

But existence of "super fast" method is highly unlikely.

Minimum complexity of most of the image processing algorithms is at least O(N^2).

By "super fast" I mean at most O(1) ;)

Some links that might help:

  1. http://www.sci.utah.edu/~cscheid/spr05/imageprocessing/project4/
  2. http://www.contrib.andrew.cmu.edu/~suppe/mobot/
  3. http://www.dunwich.org/baptiste/sic/ecms/ecpublis.html#2
  4. http://wayback.archive.org/web/20090304153603/http://hdebruijn.soo.dto.tudelft.nl/jaar2006/alders.htm
Solita answered 8/4, 2010 at 8:29 Comment(2)
Link 2 requires authorization and link 4 is 404'd. Thanks for the othersNullify
Ah I see my father has been linked [4], I'll let him know. :-) A better link for that is: alternatievewiskunde.nl/jaar2006/delphi.htm , where you can also find source code and other stuff.Dari
U
5

I think you need a Hough transform or a Radon transform. Read the articles I've linked and feel free to ask any questions :)

Unsuccess answered 8/4, 2010 at 0:26 Comment(2)
Hough Transform is quite slow... And I have to work with 2k live video... Looking into Radon now...Ohg
..not if you tune it to your particular problem. You can pre-calculate some of the math tables to improve performance if you reduce the accuracy a littleRahm
F
1

Consider the contour dots algorithm described in http://outliner.codeplex.com/ It will produce the vector-described edges in the form of Bezier curves organized in strokes. You need some effort to choose the most straigh strokes (the end points are ready to use). This algoritms is quite fast but not super duper.

Fakery answered 11/4, 2011 at 5:34 Comment(0)
M
0

I don't know how well it will work in your application, but you might try some sort of edge detection approach. Not sure how to convert those edges into vectors, if that's what you're looking for, but this might be a place to start. Anyway, some of the edge detection algorithms (e.g. the Discrete Laplace Operator) are pretty quick on moderm computing architectures.

Oh, and if you do that, you probably want to convert the image to YCbCr and just use the luma (Y) component. That's also a fast operation

Mirk answered 8/4, 2010 at 0:48 Comment(1)
No need to convert to YCbCr if all you are after is the intensity value.Entozoic

© 2022 - 2025 — McMap. All rights reserved.