Straight Line Detection

Sketch of the algorithm, as implemented in the program:
  1. Extract and load a picture from the geometry.zip file
  2. Form a real-valued equivalent of the picture for speed
  3. Determine maximum and minimum values in the equivalent
  4. Define a threshold as: (minimum + maximum)/2
  5. Collect dark pixels ≤ threshold
  6. Preliminary contouring with threshold for the purpose to find an overall contour length
  7. Estimate the length of the skeleton line as half the overall contour length
  8. Define the overall thickness as the area (number of dark pixels) divided by the length of the skeleton line (or do better than that)
  9. Estimate the spread for Gaussian smoothing as: thickness/(2√3)
  10. Define a mask for Gaussian smoothing of the dark regions. With the mask:
  11. Calculate the derivatives of the Gaussian Self Energy Function as described in the theory, everywhere in the dark pixels region
  12. 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
  13. (Note: this can actually be replaced by any procedure capable of selecting straight line supporting points in the picture)
  14. Calculate the Jacobians for the saved points and throw away those with too much symmetry (: degenerated)
  15. We are left with less ("minder") but more "relevant" points
  16. The eigenvectors at the relevant points are an estimate for the direction (or preferrably: the normal) of a straight line through the points, eventually
  17. 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:
  18. 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
  19. Because it's impossible to store such a huge matrix, it must be re-calculated row by row, each time when data are needed
  20. The row with the greatest sum (of supporting points, including their Gaussian weights) is taken as the best candidate
  21. The supporting points are employed for calculating a Best Fit Straight Line with a Least Squares method, according to theory and best practice
  22. Once they have been used, supporting points should not be employed again. So they are thrown away
  23. The last six steps are repeated with each mouse click, until the user finds that results become questionable