Line Follower based on Image Processing

Question

I’m starting to work on a line follower project but it is required that I use image processing techniques. I have a few ideas to consider, but I would like some input as there are some doubts I would like to clarify. This is my approach to solve this problem: I first read the image, then apply thresholding to detect the object (the line). I do color filtering and then edge detection. After this I start to do image classification to detect all the lines, then extrapolate those lines to only output/detect parallel lines (like a lane detection algorithm). With this parallel lines I can calculate the center to maintain my vehicle centered and the angle to make turns.

I do not know the angles in the path so the system must be able to turn any angle, that’s why I will calculate the angle. I have included a picture of a line with a turn, this is the kind of turns I will be dealing with. I have managed to implement almost everything. My main problem is in the change of angle, basically the turns. After I have detected the parallel lines, how can I make my system know when is time to make a turn? The question might be kind of confusing, but basically the vehicle will be moving forward as long the angle is near to zero. But when the vehicle approach a turn, it might detect two set of parallel lines. Maybe I can define a length of the detected lines that will define whether or not the vehicle must move forward?

Any ideas would be appreciated.

Answer 1

If you have two lines (the center line of each path):

y1 = m1 * x + b1
y2 = m2 * x + b2

They intersect when you choose an x such that y1 and y2 are equal (if they are not parallel of course, so m1 != m2)

m1 * x + b1 = m2 * x + b2

(do a bunch of algebra)

x  = (b2 - b1) / (m1 - m2)
(y should be the same for both line formulas)

When you are near this point, switch lines.

NOTE: This won't handle the case of perfectly vertical lines, because they have infinite slope, and no y-intercept -- for that see the parametric form of lines. You will have 2 equations per line:

x = f1(t1)
y = f2(t1)

and

x = f3(t2)
y = f4(t2)

Set f1(t1) == f3(t2) and f2(t1) == f4(t2) to find the intersection of non-parallel lines. Then plug t1 into the first line formula to find (x, y)

Answer 2

Basically the answer by Lou Franco explains you how to get the intersection of the two center line of each path and then that intersection is a good point to start your turn.

I would add a suggestion on how to compute the center line of a path.

In my experience, when working with floating point representation of lines extracted from images, the lines are really never parallel, they just intersect usually at a point that falls out of the image (maybe far away).

The following C++ function bisector_of_lines is inspired by the method bisector_of_linesC2 found at CGAL source code.

A line is expressed as a*x+b*y+c=0, the following function constructs the bisector of the two lines p and q.

line p is pa*x+pb*y+pc=0

line q is qa*x+qb*y+qc=0

The a, b, c of the bisector line are the last three parameters of the function: a, b and c.

In the general case, the bisector has the direction of the vector which is the sum of the normalized directions of the two lines, and which passes through the intersection of p and q. If p and q are parallel, then the bisector is defined as the line which has the same direction as p, and which is at the same distance from p and q (see the official CGAL documentation for CGAL::Line_2<Kernel> CGAL::bisector).

void
bisector_of_lines(const double &pa, const double &pb, const double &pc,
            const double &qa, const double &qb, const double &qc,
            double &a, double &b, double &c)
{
  // We normalize the equations of the 2 lines, and we then add them.
  double n1 = sqrt(pa*pa + pb*pb);
  double n2 = sqrt(qa*qa + qb*qb);
  a = n2 * pa + n1 * qa;
  b = n2 * pb + n1 * qb;
  c = n2 * pc + n1 * qc;

  // Care must be taken for the case when this produces a degenerate line.
  if (a == 0 && b == 0) {// maybe it is best to replace == with https://stackoverflow.com/questions/19837576/comparing-floating-point-number-to-zero
    a = n2 * pa - n1 * qa;
    b = n2 * pb - n1 * qb;
    c = n2 * pc - n1 * qc;
  }
}