fix arithmetic overflow; fix pattern_table entry test

smroid commented 8 months ago

Bug fixes:

Fix numpy int64 overflow when multplying combined edge values by _MAGIC_RAND
When inserting into pattern_catalog, empty element sensing was incorrect

Improvements:

Update _insert_at_index() and use it during pattern insertion.
Use _key_to_index() both at database creation and at centroid solving.

smroid commented 7 months ago

The benefit of this PR is that it allows database to be generated using smaller pattern_max_error value, which yields fewer pattern hash collisions and thus mostly faster solves.

For default pattern_max_error (.005):

Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt60_Azi135_Try1.jpg T_solve: 24.250897113233805 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt40_Azi45_Try1.jpg T_solve: 28.012210968881845 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt40_Azi-45_Try1.jpg T_solve: 15.787745825946331 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt60_Azi-135_Try1.jpg T_solve: 6.789639126509428 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/test_5mp_g100_e50ms.bmp T_solve: 66.68631779029965 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt60_Azi45_Try1.jpg T_solve: 8.471244014799595 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt60_Azi-45_Try1.jpg T_solve: 138.35741393268108 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/test2_g100_e50ms.bmp T_solve: 10.17110701650381 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt40_Azi-135_Try1.jpg T_solve: 25.422268081456423 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt40_Azi135_Try1.jpg T_solve: 24.622891563922167

For pattern_max_error=.002:

Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt60_Azi135_Try1.jpg T_solve: 26.223158929497004 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt40_Azi45_Try1.jpg T_solve: 18.905695993453264 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt40_Azi-45_Try1.jpg T_solve: 8.898829109966755 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt60_Azi-135_Try1.jpg T_solve: 6.0626487247645855 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/test_5mp_g100_e50ms.bmp T_solve: 25.81766527146101 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt60_Azi45_Try1.jpg T_solve: 5.9181880205869675 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt60_Azi-45_Try1.jpg T_solve: 43.391029350459576 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/test2_g100_e50ms.bmp T_solve: 18.884362187236547 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt40_Azi-135_Try1.jpg T_solve: 20.267082378268242 Solving for image at: /home/pi/projects/tetra3_fix1/examples/data/2019-07-29T204726_Alt40_Azi135_Try1.jpg T_solve: 11.51554798707366

gustavmpettersson commented 7 months ago

Hi smroid,

Thanks for finding another sneaky bug in the code! As discussed offline, I'd like to keep the indexing as numpy variables to be able to vectorise the lookups at a later date. Having the generator use arbitrary size python ints and the solver potentially running into int64 overflow was overlooked. It seems it should not affect databases generated with the default pattern_max_error so that's lucky.

In the branch indexing_bug I've implemented pretty much your fix but with np.uint64 declared variables throughout (which turned out to be messier than I planned, as numpy will promote any operations between np.uint64 and a signed integer to a float variable).

Let me know what you think, it would be great if you could rerun your test scenario on that branch too.

gustavmpettersson commented 7 months ago

The fix has been merged to master with the consistent use of np.uint64 data types. Closing this PR. Thanks!

esa / tetra3

fix arithmetic overflow; fix pattern_table entry test #25