Straight Line Detection
Sketch of the algorithm, as implemented in the
program:
- Extract and load a picture from the geometry.zip file
- Form a real-valued equivalent of the picture for speed
- Determine maximum and minimum values in the equivalent
- Define a threshold as: (minimum + maximum)/2
- Collect dark pixels ≤ threshold
- Preliminary contouring with threshold for the purpose to find an overall
contour length
- Estimate the length of the skeleton line as half the overall contour length
- Define the overall thickness as the area (number of dark pixels) divided by
the length of the skeleton line (or do better than that)
- Estimate the spread for Gaussian smoothing as: thickness/(2√3)
- Define a mask for Gaussian smoothing of the dark regions. With the mask:
- Calculate the derivatives of the Gaussian Self Energy Function as described
in the
theory,
everywhere in the dark pixels region
- Sort the pixels with respect to the magnitude of the first derivatives i.e.
the gradients. Save only the skeleton length of those most close to zero
- (Note: this can actually be replaced by any procedure capable of selecting
straight line supporting points in the picture)
- Calculate the Jacobians for the saved points and throw away those with too
much symmetry (: degenerated)
- We are left with less ("minder") but more "relevant" points
- The eigenvectors at the relevant points are an estimate for the direction
(or preferrably: the normal) of a straight line through the points, eventually
- Define the fuzzy equivalence of points (p) and (q) as exp(-A2/2)
, where A = ux(px-qx)
+ uy(py-qy) and (u) is the normal of
the line through (p). Repeat:
- Calculate the fuzzy equivalences for all of the points (p) and (q). This
results in the main bottleneck: a matrix [ p , q ] with mainly zeroes in it
- Because it's impossible to store such a huge matrix, it must be
re-calculated row by row, each time when data are needed
- The row with the greatest sum (of supporting points, including their
Gaussian weights) is taken as the best candidate
- The supporting points are employed for calculating a Best Fit Straight Line
with a Least Squares method, according to
theory
and best practice
- Once they have been used, supporting points should not be employed again.
So they are thrown away
- The last six steps are repeated with each mouse click, until the user
finds that results become questionable