0

I am not familiar with the problem I am about to describe here. So sorry about the wrong terminology.

What I am looking for is an algorithm (preferably a library in C/C++) to identify the straight part out of a curved line. Input curved line is defined using a set of ordered points in (x,y) form. I found some articles about Hough transform and one libray OpenCV. It seems to be possible to use OpenCV but looks a overkill. What I need is a very efficient algorithm to handle one simple curved line. Any ideas how to do it? Thanks.

Update: see example below, the goal is to identify the red part enter image description here
As some pointed out that the straight part may not extactly straight, i.e. I may need some tolerance of deviations here.

Orunner
  • 404
  • 4
  • 13
  • may you show us an example? Is it one line in set of point? Is it a real straight line ? or approximately a straight line ? – Humam Helfawi Jan 04 '16 at 11:40
  • Unfortunately SO is the wrong place to ask this sort of question. While we would gladly help you work through any issues you might have coding around such a library, finding it is outside the scope of this site. – Mad Physicist Jan 04 '16 at 11:40
  • 1
    You can take a look [here](http://ubee.enseeiht.fr/vision/ELSD/), there's a link to C source code also. Or [here](http://ltilib.sourceforge.net/doc/html/index.shtml) also with C++ code. Or [here](http://www.sciencedirect.com/science/article/pii/S0167865511001772) or [here](http://www.ipol.im/pub/art/2012/gjmr-lsd/article.pdf) However, this question is too broad and unclear for StackOverflow. Try to get a better understanding of the problem and come back if you have questions about programming. – Miki Jan 04 '16 at 12:02
  • 1
    If that's your input, you can simply find points with a pairwise distance large enough – Miki Jan 04 '16 at 13:03

3 Answers3

3

Compute the slopes between consecutive points O(N).

If 3 consecutive points have almost the same slope between the two pairs than the 3 points are almost on the same line (minus rounding errors). So to find straight lines just look for sections of consecutive points where the slopes are almost equal. You can do this in one pass through the points O(N).

If you have many points you can run into the case that the curve is so slight that it's less than the rounding error you allow when you compare the slopes. If you see this add another check to compare with the first slope in the straight line to make sure you don't compound errors.

If you need something more comprehensive or faster consider using OpenCV.

Sorin
  • 11,863
  • 22
  • 26
3

Let's say you have 3 consecutive points (x1,y1), (x2,y2), and (x3,y3)

Calculate (y1-y2)*(x3-x2) + (x2-x1)*(y3-y2)

If this is positive, then the curve is turning left at (x2,y2), and if it's negative then it's turning right. If it's zero , then the curve is straight at (x2,y2)

To find truly straight sections, you can look for points where this is zero. You probably really want to find the place where it changes from turning left to turning right.

If you want an actual measure of how much it turns, then divide by length(segment1)*length(segment2) the result is the sin of the turning angle.

Matt Timmermans
  • 53,709
  • 3
  • 46
  • 87
2

I do not know why I am in a case of endless love with RANSAC those days.. I am even tried to use it while cooking. However, RANSAC with fit-line model may be the best solution for your problem. Since you have many outliers (non straight line points) and you have a good inliers(straight line points). Here you can find a ready implementation in C++. RANSAC-like implementation for arbitrary 2D sets

Community
  • 1
  • 1
Humam Helfawi
  • 19,566
  • 15
  • 85
  • 160