Only check for QR code combinations if the combination is reasonably square

[KyleMaas]

This changes the behavior of the linescan detector so it discards combinations of locator candidates which are not at least reasonably square. This cuts down significantly on the processing time for images which contain multiple QR codes (or at least where there are many detected locator candidates where combinations are invalid).

[piderman314]

Hey, thanks for your pull request. I've had a look and I'm not sure why you made this change. If you look in find_qr_internal you will see that there already is a check for the squareness (perpendicularity) of the finders using the cross product, which in my opinion is clearer. Can you provide some extra reasoning? Did you find your method to be more reliable?

[KyleMaas]

I didn't find it to be more reliable so much as generally faster with huge combinations of locator candidates.

My test image had eight QR codes in it, with only half of them valid. Several locator candidates were found inside of the valid QR codes. It took forever to churn through the all the possible alignment combinations that the cross-product version let through without it.

For one thing, since it knows the which edges are perpendicular first, it doesn't try find_qr_internal more than once per combination like find_qr does. It's also a little more aggressive about culling invalid candidates. Could that logic be integrated into find_qr_internal alongside the cross product version? Possibly, although you'd still be potentially checking all three combinations of vertices looking for a perpendicular edge since the cross product is in find_qr_internal instead of find_qr.

There might be a better way to do this. But this helped quite a bit for me, so I figured I'd pass it along.

[piderman314]

Alright, I see what you mean. I'm a bit worried over the readability of the code so I'll have a more detailed look over the weekend.

[KyleMaas]

Sounds like a plan. Feel free to rewrite it in a more readable way. You may even be able to reuse the square roots from the cross product code to make it run a little faster, provided the code could be restructured a bit. I'm fairly new to Rust, and while mathematically I knew what I wanted and it seemed to work well, I tried to minimize the number of changes to do that, and it could probably use some work from someone with a bit more experience in making it more Rust-y.

[piderman314]

Could you maybe provide an example of the sort of image you are trying to decode so I can see what's going on?

Fundamentally our approaches are the same, the complexity of the operation is still O(n^3) since the three candidate loops are still present. So mabye your tolerances are slightly more strict so it has fewer false positives?

[KyleMaas]

I'll see what I can do. It's for a project I intend to open source, but it's nowhere near where I'd want it public yet. But I'll see if I can figure out a synthetic test image.

[KyleMaas]

When I was testing before, I had debug-images on, and it was notably faster with this. Testing again with debug-images off (so I/O is less of a factor), this is consistently slower by about 3%. Maybe it was thinning out some of the possibilities but taking more time doing it, resulting in fewer images to save with debug-images but slower processing without? I don't know, but I don't figure it's worth putting any more time into since that'd be off in production builds anyway.