mutiple curve fitting in binary images

Question

I have a binary image which contains 0s and 1s only. There are few trend lines in the image as shown below, is there any way to extract those lines from the image?

Answer 1

Yes, one way to extract the lines would be to use a RANSAC algorithm iteratively.

It identifies the points that are close to a model function and then removes them from the image. This allows to extract a separate line in the next iteration.

Use y = a?x + b as model function (where x and y are the image coordinates and a should come out as close to ?1).

An implementation would work roughly as follows:

1. Convert the image to a representation that allows you to treat it as a set S of points where the value is 1 (in the simplest case, a list or set of (x, y) tuples).

2. Pick one point (x₀, y₀) from S randomly and determine b₀ such that y₀ = ?x₀ + b₀ (i.e., draw a line with slope a₀ = ?1 through the chosen point).

3. Find all points (x, y) in S that are "close" to the line y = a₀?x + b₀ and add them to a new set L.

   (For example by using the condition |a₀?x + b₀ ? y| < t for some threshold value t. Given that the lines in the image are vertically spaced by about 85, t = 20 might be a good choice.)

4. Repeat steps 2 and 3 several times and remember the value for b₀ where L contained the most points.

5. Refine a₀ and b₀, e.g. by doing a least-squares fit of the model function to all points in L, to obtain final values a and b (this step is optional, you could just use a₀ and b₀ directly). Now you have found one line.

6. Remove all points in L from S.

7. Repeat from step 2 as many times as needed to find all lines in the image. At the end there are only "noise" points left in S.