Loop homography rejects large numbers of valid pairs

[Bob-O-Rama]

Project with 20 x 20, lrtb pattern, 30% overlap, 1:1 aspect ratio tiles. AKAZE and ORB identify many valid pairs, about 70% of valid pairs are rejected by loop homograph.

On inspecting logs it is seen that none of the loops are valid and the pair is voted as bad.

INFO: Pair ( 5, 6 ) Loop = {4,5,6,25,4} Error = 1006.49 INFO: Pair ( 5, 6 ) Loop = {5,25,6,5} Error = 1009.01 INFO: Pair ( 5, 6 ) Loop = {26,5,6,27,26} Error = 1009.18 INFO: Pair ( 5, 6 ) Loop = {5,26,6,5} Error = 1009.6 INFO: Pair ( 5, 6 ) Loop = {5,26,27,6,5} Error = 1010.43 INFO: Pair ( 5, 6 ) Loop = {25,4,5,6,25} Error = 1011.01 INFO: Pair ( 5, 6 ) Loop = {25,5,6,26,25} Error = 1013.64 INFO: Pair ( 5, 6 ) Loop = {5,25,26,6,5} Error = 1014.07 INFO: Pair ( 5, 6 ) Loop = {24,5,6,25,24} Error = 1742.9 INFO: Pair ( 5, 6 ) Loop = {6,25,26,5,6} Error = 2022.4 INFO: Pair ( 5, 6 ) Loop = {26,5,6,25,26} Error = 2027.1 INFO: Pair ( 5, 6 ) Loop = {26,5,6,7,26} Error = 2039.51 INFO: Pair ( 5, 6 ) Loop = {5,6,7,26,5} Error = 2039.51 INFO: Pair ( 5, 6 ) Loop = {5,24,25,6,5} Error = 2467.58

INFO: Pair ( 5, 6 ) Votes: Bad = 1 L2 = 0 L1 = 0 L0 = 0 Status: PAIR BAD

This seems related:

INFO: Pair ( 24, 25 ) Loop = {24,4,5,25,24} Error = 2407.03

However all of the individual pairs seem valid:

[Bob-O-Rama]

The spread of control the points is also odd.

[Bob-O-Rama]

Issue of bands of control points noted above appears to be in the decimation algorithm. To de-aggregate the control points, the resulting control points are divided into N x N pixel zones. The default is 100 x 100, but can be user specified. The "best" control points are selected from each zone. To ensure the desired spread of the resulting control points over the overlap area, a pseudo random deterministic pattern is used to randomize the zone order when building the final list of surviving control points. It appears as if this process is favoring a particular horizontal or vertical zone index. This results in a narrow stripe of control points. Fewer zones means more control points are selected from those zones used, encouraging the small scale clumping.

[Bob-O-Rama]

Possible workaround to control point banding: specify --cellsize N where N is a small prime number, like 23.

This did not resolve the overarching issue of many pairs being rejected.

[Bob-O-Rama]

Adjusting the hash to be a repeatable permutation based on std::shuffle and std::mt19937 resolved the control point banding issue. This did not resolve the --loopfilter issue.

[Bob-O-Rama]

What is happening is that an image is being paired with multiple essentially identical images owing to the pattern being approximately the same size as the tiles. Here is an example of the pairing of one image to its next row neighbors:

In this instance loop homography fails to resolve conflicting overlap. The correct pair is 4-->24. The current algorithm is not capable of reliably identifying the correct one. If the tiles have perfect horizontal and vertical alignment, as from a robotic stage, using --rowsizetolerance 0 would eliminate pairs 4-->23 and 4-->25 which would "solve" the problem.

For example, in the series c test tiles, loop 4-->5-->25-->24-->4 would be valid. as would many of of the ilk N-->N+1-->N+21-->N+20-->N. It may be that these loop options are not being checked.

[Bob-O-Rama]

The 4-->5-->25-->24-->4 loop shows an error of 1000+, but each pair appears to be properly aligned individually. Its not obvious as to what is causing the huge error with the transitive error calculation. Added trace level output so the homography matrix and the test point can be followed.

[Bob-O-Rama]

The loop homography reports an invalid pair because a sub loop reports an error.

**transitiveErrorSub({26,6,7,27,26}) :** 


transitiveError(): --> 
transitiveError(): reference = [690, 690]
transitiveError() called with i_h.size()= 3 for test point [690, 690]
transitiveError(): H = [1.002605745500076, 0.001591172622851868, -0.3738258350806647;
 0.0002014433705316523, 1.005307258132265, 981.8172964537838;
 6.514998717109656e-08, 2.112931523591115e-06, 1.002063436408982]
transitiveError(): H = [ 1.00261, 0.000201443, 6.515e-08; 
transitiveError(): H =   0.00159117, 1.00531, 2.11293e-06; 
transitiveError(): H =   -0.373826, 981.817, 1.00206 ] 
transitiveError(): test = [690.061, 1669.66]
transitiveError(): H = [0.9948528757613174, 6.226743229854836e-05, -974.9365522670332;
 -0.002949833199869741, 0.9954920836405535, 3.381731371894061;
 -4.26466672804291e-06, 4.259534572939009e-07, 1]
transitiveError(): H = [ 0.994853, -0.00294983, -4.26467e-06; 
transitiveError(): H =   6.22674e-05, 0.995492, 4.25953e-07; 
transitiveError(): H =   -974.937, 3.38173, 1 ] 
transitiveError(): test = [-288.968, 1667.2]
transitiveError(): H = [1.007584942589885, 0.001320661935426213, -31.41240396120758;
 3.218793766390294e-05, 1.009445389447971, -992.6817705047151;
 -8.845435091623245e-08, 6.219448161092597e-06, 1]
transitiveError(): H = [ 1.00758, 3.21879e-05, -8.84544e-08; 
transitiveError(): H =   0.00132066, 1.00945, 6.21945e-06; 
transitiveError(): H =   -31.4124, -992.682, 1 ] 
transitiveError(): test = [-317.075, 683.159]
transitiveError(): retval = [1007.07, 6.84088]
transitiveError(): <-- 
**transitiveErrorSub({26,6,7,27,26}) : {26,6,7,26} Error: 251.774**

transitiveError(): --> 
transitiveError(): reference = [690, 690]
transitiveError() called with i_h.size()= 4 for test point [690, 690]
transitiveError(): H = [1.002605745500076, 0.001591172622851868, -0.3738258350806647;
 0.0002014433705316523, 1.005307258132265, 981.8172964537838;
 6.514998717109656e-08, 2.112931523591115e-06, 1.002063436408982]
transitiveError(): H = [ 1.00261, 0.000201443, 6.515e-08; 
transitiveError(): H =   0.00159117, 1.00531, 2.11293e-06; 
transitiveError(): H =   -0.373826, 981.817, 1.00206 ] 
transitiveError(): test = [690.061, 1669.66]
transitiveError(): H = [0.9948528757613174, 6.226743229854836e-05, -974.9365522670332;
 -0.002949833199869741, 0.9954920836405535, 3.381731371894061;
 -4.26466672804291e-06, 4.259534572939009e-07, 1]
transitiveError(): H = [ 0.994853, -0.00294983, -4.26467e-06; 
transitiveError(): H =   6.22674e-05, 0.995492, 4.25953e-07; 
transitiveError(): H =   -974.937, 3.38173, 1 ] 
transitiveError(): test = [-288.968, 1667.2]
transitiveError(): H = [1.000497224547401, 0.0004205214268396044, -0.4585596839062586;
 2.286166647784805e-05, 1.000922968268016, -981.0187008697391;
 -6.087082027104293e-09, 4.417018914884956e-07, 1]
transitiveError(): H = [ 1.0005, 2.28617e-05, -6.08708e-09; 
transitiveError(): H =   0.000420521, 1.00092, 4.41702e-07; 
transitiveError(): H =   -0.45856, -981.019, 1 ] 
transitiveError(): test = [-288.656, 687.21]
transitiveError(): H = [0.9995215343098456, -8.946113326387571e-05, 979.5720748478334;
 -0.000180243576902284, 0.9994562830638866, 0.02943099112890966;
 -4.590926859083848e-07, -1.868647031456075e-08, 0.9995500664877957]
transitiveError(): H = [ 0.999522, -0.000180244, -4.59093e-07; 
transitiveError(): H =   -8.94611e-05, 0.999456, -1.86865e-08; 
transitiveError(): H =   979.572, 0.029431, 0.99955 ] 
transitiveError(): test = [691.221, 687.145]
transitiveError(): retval = [-1.2207, 2.8551]
transitiveError(): <-- 
transitiveErrorSub({26,6,7,27,26}) : {26,6,7,27,26} Error: 0.621023


transitiveError(): --> 
transitiveError(): reference = [690, 690]
transitiveError() called with i_h.size()= 4 for test point [690, 690]
transitiveError(): H = [0.9948528757613174, 6.226743229854836e-05, -974.9365522670332;
 -0.002949833199869741, 0.9954920836405535, 3.381731371894061;
 -4.26466672804291e-06, 4.259534572939009e-07, 1]
transitiveError(): H = [ 0.994853, -0.00294983, -4.26467e-06; 
transitiveError(): H =   6.22674e-05, 0.995492, 4.25953e-07; 
transitiveError(): H =   -974.937, 3.38173, 1 ] 
transitiveError(): test = [-289.211, 690.064]
transitiveError(): H = [1.000497224547401, 0.0004205214268396044, -0.4585596839062586;
 2.286166647784805e-05, 1.000922968268016, -981.0187008697391;
 -6.087082027104293e-09, 4.417018914884956e-07, 1]
transitiveError(): H = [ 1.0005, 2.28617e-05, -6.08708e-09; 
transitiveError(): H =   0.000420521, 1.00092, 4.41702e-07; 
transitiveError(): H =   -0.45856, -981.019, 1 ] 
transitiveError(): test = [-289.435, -290.236]
transitiveError(): H = [0.9995215343098456, -8.946113326387571e-05, 979.5720748478334;
 -0.000180243576902284, 0.9994562830638866, 0.02943099112890966;
 -4.590926859083848e-07, -1.868647031456075e-08, 0.9995500664877957]
transitiveError(): H = [ 0.999522, -0.000180244, -4.59093e-07; 
transitiveError(): H =   -8.94611e-05, 0.999456, -1.86865e-08; 
transitiveError(): H =   979.572, 0.029431, 0.99955 ] 
transitiveError(): test = [690.517, -290.087]
transitiveError(): H = [1.002605745500076, 0.001591172622851868, -0.3738258350806647;
 0.0002014433705316523, 1.005307258132265, 981.8172964537838;
 6.514998717109656e-08, 2.112931523591115e-06, 1.002063436408982]
transitiveError(): H = [ 1.00261, 0.000201443, 6.515e-08; 
transitiveError(): H =   0.00159117, 1.00531, 2.11293e-06; 
transitiveError(): H =   -0.373826, 981.817, 1.00206 ] 
transitiveError(): test = [690.448, 689.299]
transitiveError(): retval = [-0.448425, 0.700745]
transitiveError(): <-- 
transitiveErrorSub({26,6,7,27,26}) : {6,7,27,26,6} Error: 0.166388

transitiveErrorSub({26,6,7,27,26}) : 5 Sub-chains,  Worst: {6,7,27,6} Error: 252.341

[Bob-O-Rama]

( "Error" reported in debug output was computed as an average, there were inconsistencies in the way the debug output reported this info between various versions of sibling functions. Correcting some of that. )

[Bob-O-Rama]

Take loop R1C1 --> R1C2 --> R2C2 --> R2C1 --> R1C1 with overlapping edges. The overall loop is low error. However sub loops, such as R1C1 --> R1C2 --> R2C2 --> R1C1 would include a pair ( e.g. R2C2 --> R1C1 ) overlapped via a corner. It appears in the series c and series d test tile sets the corners are misaligned. The subloop check requires all sub-loops be consistent as well. This specifically to catch these sorts of situations. This requirement may be too strict.

The takaway is that the loop homography code is working, its just algorithmically not doing what we want in this case. Next steps would be determining why the corner overlaps are bad, confirming that --rowsizetolderance 0 which would eliminate corner overlaps "fixes" the issue.

[Bob-O-Rama]

The current algorithm cannot distinguish between what appear to be well aligned images. Essentially there are three equally good pairs for this particular test case. Using --rowsizetolerance 0 does in fact eliminate the spurious pairs. This made visible several other secondary issues with this tile set. Namely that the these blurry images push the limits of Akaze.