Performance improvement - faster simple line detector

[ShaharMS]

Progress:

• [x] Convert recursion to iteration.
• [x] Int16Point2D
• [x] Cache already checked-against points.
• [x] Smarter line direction handling: choosing pre-calculated direction.
• [x] Choose an order of importance when checking for other points surrounding the current one
• [ ] Check against lines originating from the same pixel simultaneously. (?)
• [ ] Make the algorithm also perform actions on the image, such as setting black pixels where lines were detected to avoid reading the same line multiple times
• [ ] Move the looping part to the algorithm itself to let it handle where it wants to check for points
• [x] Gap checks, direction prediction on gap checks
• [ ] Merge similar lines, or add checks for the removal of similar lines.

Results:

• [x] Surpass performance of previous algorithm implementation by at least a factor of 3
• [x] Detect "basic" lines (0, 90, 180, 270 degrees)
• [x] Detect skewed lines
• [x] Detect slightly curved lines

[Wither362]

• [ ] Check against lines originating from the same pixel simultaneously. (?)

That can't be, Haxe is not a multiple line code, it would be almost simultaneously, but not exactly simultaneous

[ShaharMS]

• [ ] Check against lines originating from the same pixel simultaneously. (?)

That can't be, Haxe is not a multiple line code, it would be almost simultaneously, but not exactly simultaneous

By simultaneously i mean queuing more than one line to be checked at each pixel check. the current implementation explores the first potential line it finds, and that means it might miss a potentially good point to track another line from. The wanted implementation checks for as many lines as possible, and queues all of them for exploration.

[Wither362]

• [ ] Make the algorithm also perform actions on the image, such as setting black pixels where lines were detected to avoid reading the same line multiple times

I have an idea for doing that: what if we have another image that is the exact same one, but in this one we can add black points? For no conflicts with the original image

[Wither362]

How do you want to do that the code detects the slightly curved lines? Because that's gonna be difficult if the code doesn’t allow float values…

[ShaharMS]

slightly curved lines should be detectable because of the nature of interpretive line detectors

How do you want to do that the code detects the slightly curved lines? Because that's gonna be difficult if the code doesn’t allow float values…

curved line detection is more of a side effect of interpretive line detectors, so that shouldn't be that hard

[ShaharMS]

ive just realized about 80% of the time is spent doing edge detection, which is both really good and really bad because:

• good - that means the algorithm is about 3x faster than its previous counterpart
• bad - i need to find a way to either:
  • switch to another form of edge detection
  • optimize the hell out of canny edge detection

[Wither362]

ive just realized about 80% of the time is spent doing edge detection, which is both really good and really bad because:

• good - that means the algorithm is about 3x faster than its previous counterpart

• bad - i need to find a way to either:

  • switch to another form of edge detection
  • optimize the hell out of canny edge detection

Buff, that looks like hell dude, if you need help with optimizing, tell it to me!

[ShaharMS]

ive just realized about 80% of the time is spent doing edge detection, which is both really good and really bad because:

• good - that means the algorithm is about 3x faster than its previous counterpart

• bad - i need to find a way to either:

  • switch to another form of edge detection
  • optimize the hell out of canny edge detection

Buff, that looks like hell dude, if you need help with optimizing, tell it to me!

thanks for suggesting, turns out the slow part of canny edge detection was the gaussian blur. i implemented another, faster version of the gaussian blur that uses two, one-dimensional kernels instead of a two-dimensional one. 800ms speedup🤯

[ShaharMS]

it looks like i have another problem - the algorithm tries to detect lines from every single edge pixel, which means it detects a bunch of overlapping lines (in my tests, it detects 2732 lines, which is insane that it does that in ~300ms in a 600x450 image, but very unnecessary...)

[Wither362]

it looks like i have another problem - the algorithm tries to detect lines from every single edge pixel, which means it detects a bunch of overlapping lines (in my tests, it detects 2732 lines, which is insane that it does that in ~300ms in a 600x450 image, but very unnecessary...)

Oh my goodness…

[ShaharMS]

i think this is done! test image takes 3x time less than before, the system is no longer recursive, and a bunch of extra things were implemented. The change-log will be done on main. thanks @Wither362 for your help :)

[ShaharMS]

finally, merging into main :D