This is going to be a saga length blabby post so apologies in advance. Also, to forestall the "But Bob, many other stitching tools do a way better job..." etc. Yes, I am aware. "Thank you, noted!" LOL
Now let me now tell you about how I reinvented the wheel... Lets confront the enemy, repeated features, these are larger scale. Often they are small RAM / ROM cells. These sorts of tiles rarely stitch well in Hugin, they can plausibly overlap in dozens of different ways. For example this grid of identical ALU's covering about 12 tiles:
Hugin's cpfind either failed to find any control points, or would pair tiles in impossible or bizarre ways.
The initial concept was to "simply" implement "better" feature detector methods wrapped in a way to accept cpfind's command line. That and use some brute force to eliminate impossible pairs based on things like shooting pattern and overlap. That was easy to code, actually. But every time I would improve things, I would find another deal breaking issue.
Here is how project code name cvfind evolved... ( see what I did there? cvfind? )
Round 1: Implemented most of the different types of feature detection, description, and matching methods supported by opencv library: SIFT, ORB, AKAZE, blobs, lines, corners, ... its endless. I had no idea which ones might be better, cutting and pasting is easy, and I sort of went nuts and ended up with them all.
Which is best? ORB generally finds a lot of features fast, but has the same allergy to lines SIFT has. AKAZE is vastly slower but is insanely robust and finds features anywhere there is texture. If I can let it run over night, I use AKAZE. cvfind also lets you used any combination of them, because why not.
I went into into Hugin, detect control points using cvfind, and it worked!!! All images connected, lots of control points. I had a cpfind replacement. Done. Right? I'm done, right? Ya... no...
Welcome to the ( homography ) matrix:
With my victory lap interrupted by the Dr. Strange's CPU or whatever that is I started reallizing this was actually a hard problem.
While it found valid pairs where cpfind did not - owing to the different detectors looking for features in areas SIFT skipped over - it also found a ton of bad pairs in these godforsaken repeating patterns that previously had no control points. The false negative rate was through the roof.
In the markup below, each fine line is a "match" - as you can see, raw matches are often totally bogus, so the RANSAC used by cpfind and cvfind basically resulted in the same mess. I basically recreated cpfind - flaws and all. Ugh!
Round 2: Implemented distance filtered trial homography. cpfind and version cvfind above treated all matches as equals, then RANSACed them assuming "God would sort it all out." But that's stupid. For tiling, "good" control points will all share a common distance and direction between the respective coordinates in the pairs images. Good control points will not be in areas where overlap is impossible based on the shooting patterns. etc...
I do dozens of trial homography solutions for subsets of control points grouped by distance. ( Slope could also have been used, but it worked less well. ) Most of these trials fail because there is no way to overlap the images while registering them N pixel distance apart. The strongest trials represent the most plausible overlaps. Most of the time a very clear winner emerges - and the situation reduces to the cpfind scenerio. After implementing this, I got Hugin to stitch the top few rows without editing the resulting project:
This version eliminated impossible overlaps based on the user explicitly telling cvfind "there would be approximately N images per row, and the shooting patterns is right to left, top to bottom" for example. Its like the multirow and linearsearch options in cpfind on steroids.
For the 240 tile project there should be about 900 good pairs, I only found 780. While I went from 100 bad pairs to about 20, it was still a complete disaster stitch-wise. As little as i pad pair can cause this mishap. I was having difficulty telling if the pairs were real or not - even after staring at the control point editor! Often a central tile would be shifted slightly, by one RAM row or colum, and perfectly match the pattern in two adjacent tiles. It was super frustrating.
Round 3: Loop homography!!! It occurred to me that the definition of a "valid" pair ( say image A and image B ) is there is an homography solution ( via RANSAC ) that maps control points ( identical points on the actual subject ) from A to B.
Once the homography matrix is found, you can take a point on A, throw it up against the homography matrix, and find the corresponding coordinates in B, eyeball both patches and observe they are the same.
Now lets say image B is paired with C. Similarly, there is a homography matrix for projecting points from B into C... and C is paired with D and so on. You can mentally construct some loops from these overlapping images:
So take an image and find neighbors which are transitively paired with each other in a loop like fashion.
A-->B-->C-->D-->E-->A
you have a loop of pairs. If all of the homography matrices are consistent - that is to say, all the links in the chain are valid pairs - one "should" be able to take a point in A and sequentially project it from pair to pair to pair ... and finally back to its original location in A. Once I had this epiphany, I was able to hard code some stuff and get the first real success: this 74 tile thing which the tool just got right with no editing of the project being required. With no bad pairs, it just worked:
Suppose there were a bad pair, say B-->C was shifted or overlapped wrong. Serially projecting the trial point through the bad pair shifts the coordinates significantly. For a loop of valid pairs, the total RMS error from A...to A' is maybe 5 pixels distance. For for a misalignment in one pair, ~2000! Its an elegantly sensitive consistency check.
Another property of these "valid" loops is that all sub loops must also be valid. I return the worst error for the loop and all possible sub loops, e.g. A-->B-->C-->A. The longer the loops the more potent the test. On the 240 image project, I only needed 5 pairs per loop to catch all of them. The test is computationally easy, each check from pair to pair is about a microsecond. None of this requires opencv to implement and could easy be built into Hugin. For a 240 image project with 900 pairs, checking thousands of loops per image it takes like 5 seconds.
The "other" nice thing about this is if you DO validate a loop, all of the pairs in the chain can be assume valid. After the first pass we eliminate all bad pairs - goodbye, good riddance. The remaining pairs are inherently good - that is to say have overlaps which are mutually consistent. This is huge because in one pass you basically eliminate the biggest problem, other than a lack of control points.
Round 4: Loop trial homography . The loop homography detailed above finds and remove bad pairs. But in many cases they were not "bad" but merely "misunderstood." LOL! Merely overlapped badly, shifted because of the fine repeating patterns on the chip. One of the initial trial homography solutions ( groups matches with of similar distance ) are actually valid, just not the "best." If you could find the "correct" homography between them, it would be a good pair! But how can you do that? They all look plausible?
Well, loop homography, of course! "Valid" pairs have a final homography solution we accept as gospel truth. Bad pairs have a number of trial homographies. So we conduct the loop test again, but this time trying each of the trials we conducted earlier with the bad pair in a loop of known good pairs. In may cases this identifies a valid homography for the "bad" pair consistent with the overlap of its neighbors by trying every possible overlap between the images. This recovers most of the "bad" pairs! Now we have MORE valid pairs to support future repair efforts. Since its a 5 second process, I run it until no pairs can be repaired.
This gets us most valid pairs, but not all... There is an option to tell cvfind "good enough, you can stop now!" but ... why not go nuts? Are there more valid pairs we can find? Yes:
Round 5: Repair. Because SIFT and ORB sometimes do not find enough matches for a pair to be identified, it would be great to take these very weak pairs and run a more intensive feature detection process. It will take a suspected potential pair that failed the above steps and run AKAZE against it. This is time consuming. But results in another 5-10% valid pairs being discovered. So why not.
At this point the 240 time project "just worked" without any futzing in hugin. Alignment was good, some pixel peeping stitch error, but otherwise pretty good.
But wait ... there's more...
It currently works as a replacement for cpfind with a cacophony of command line options, some of which specify things that are project specific and cannot be represented in the Hugin UI. I think some of that can be concealed in comments in the project to make the cpfind compatability more convincing.
You point the tool at your existing Hugin project file, it grinds through the images, feature detection, the loop homography validation, and burps out an edited project. You open it in Hugin and business as usual. No futzing, no wondering which of 1000 pairs might be bad. It generally just "works." But the other thing you can do with it is have it process an existing project and treat the existing control points as if they were freshly detected including the loop homography magic to reject bad pairs. I have a couple totally unstitchable projects I've accumulated. or ones which took hours of labor to fix. It took all of 5 minutes and it fixed them.
The remaining work is severe code cleanup. Half the code base can easily go away. Its basically a pile of spaghetti and debugging code while I was still trying to figure out these issue, and how opencv works. Its sort of a train wreck. Its also hard to "share" as a binary, so currently would need to be built from the dumpster fire source.
Finally, yes, these are problems addressed on other stitching / tiling systems. Its an interesting puzzle to figure out. Also the general method for finding bad pairs absolutely should be something added to Hugin, IMO. Its a great method that would spare us a lot of suffering. So I'll be suggesting that.
"Thank you for attending my TED talk"