Automatic Image Stitching

This is a successor note of and .

To complete the task of achieving full automatic stitching without exhaustively searching all possible layouts, an algorithm must be designed to:

1. Find the real neighbors among images
2. Come up with the right order of stitching
3. Find the root image to start with

Verify neighbors

After matching the descriptors and then using RANSAC to filter the best matches, we got the inliers and outliers. The inliers are the features that lie close to their targets after transformation, while the outliers are those that lie inside the overlapped area but are far from their targets.

The sum of inliers and outliers is the total features in the overlapped area of a pair of images. We denote the sum of features as $n_f$, and the number of inliers as $n_i$. Only when they follow the inequation below can these two images be considered neighboring images:

$$n_i>8.0+0.30\ast n_f$$

The above inequation comes from their paper (Brown & Lowe, 2007). In an earlier publication from the same team, the magic numbers are slightly different (Brown et al., 2003):

$$n_i>5.9+0.22\ast n_f$$

Note

This verification model is to compare the probabilities that this set of inliers/outliers was generated by a correct image match or by a false image match.

Given ground truth relations, the chance of each feature being an inlier/outlier is modeled as independent Bernoulli.

The first one works pretty well in my experiments. I further define a relation weight $R$ that indicates how much they correlate to each other:

$$R=\frac{n_i}{8.0+0.30\ast n_f}$$

Maximum spanning tree

After we verified the potential relationship between the unordered images, a graph with undirected edges is established. We need to remove the redundant edges and turn the graph into a tree with only one root. Also, there is only one path to each node. The root is then set as the canvas.

We only need to keep the edges with the largest weight $R$. In other words, we hope our tree has the largest sum of weights among all the candidate routes.

It naturally brought me to the maximum spanning tree problem. The more popular way of addressing it is minimum spanning tree (MST). There are a bunch of toolboxes on MST. If you’re using MATLAB like me, check minspantree. If you want to implement by yourself, check my note .

We can simply multiply -1 to the relation weights $R$ to turn it into a MST problem. The following graph shows the weights in $-R$. Smaller weights indicates closer neighbors. (Does it match your intuition?)

Figure 1: Photos taken at University Town

Find the root

To decide which node should be the root of the tree, I chose to calculate the maximum steps to the leaves, and then select the one with the shortest maximum steps:

$$\text{root}=\arg \underset{i}{\max }\left[\underset{j}{\max }\left(\text{step}({\text{node}}_i,{\text{node}}_j)\right)\right]$$

After setting the root as canvas, I carry out the transformation one-by-one from the root (image in the center) to each node (neighboring images) using recursion.

Figure 2: Image 2 as root

Showcase

Somewhere I couldn’t remember

Figure 3: Five photos numbered 1-5 from L to R

7 out of 10 edges are established.

p7_unordered_stitching

>> p7_unordered_stitching
   Loading image 1/5... Done.
   Loading image 2/5... Done.
   Loading image 3/5... Done.
   Loading image 4/5... Done.
   Loading image 5/5... Done.
   Checking image 1 & 2... w 1.8248 n 100N 156	Matched.
   Checking image 1 & 3... w 0.43269 n 18N 112	Denied.
   Checking image 1 & 4... w 0.22059 n 6N 64	Denied.
   Checking image 1 & 5... w 0.33613 n 4N 13	Denied.
   Checking image 2 & 3... w 2.6952 n 459N 541	Matched.
   Checking image 2 & 4... w 2.3648 n 258N 337	Matched.
   Checking image 2 & 5... w 1.3731 n 46N 85	Matched.
   Checking image 3 & 4... w 2.8626 n 527N 587	Matched.
   Checking image 3 & 5... w 1.8122 n 83N 126	Matched.
   Checking image 4 & 5... w 1.8966 n 88N 128	Matched.

Figure 4: The graph I used for MST (weights are represented by $R$)

Figure 5: MST with the highest overall relation weight

Figure 6: Simplified MST

The root is node 3.
The farthest distance from root is 2.

Figure 7: Resulting panoramic

GeoSpy

With Ayer Rajah Telephone Exchange and Kent Vale in it, maybe it’s from Blue Horizon?

Yosemite

Figure 8: Since it’s a straight panoramic, it’s is not hard … Right?

Figure 9: The root is found to be 2. Let’s transform images 1, 3, and 4

Stephen Riady Center

Figure 10: Overlaps exist among all of them

Figure 11: Node 1 is the root. Adding 2, 4, and then 3

Further readings

There might be some better solutions for unordered image stitching, (Qu et al., 2020) for example.

There are some topics that I couldn’t cover in the coursework, like Bundle Adjustment, Panorama Straightening, Gain Compensation, Multi-Band Blending, etc (Brown & Lowe, 2007). Some are tackling different challenges, like (Zhang & Liu, 2014).

Note that these are just half of the assignments of EE5731 😭. I spent the whole month working on these. If you made the same decision as I did, reconsider your strategy.

References

Brown, M., & Lowe, D. G. (2007). Automatic panoramic image stitching using invariant features. International Journal of Computer Vision, 74, 59–73.

Brown, M., Lowe, D. G., & others. (2003). Recognising panoramas. ICCV, 3, 1218.

Qu, Z., Li, J., Bao, K.-H., & Si, Z.-C. (2020). An unordered image stitching method based on binary tree and estimated overlapping area. IEEE Transactions on Image Processing, 29, 6734–6744.

Zhang, F., & Liu, F. (2014). Parallax-tolerant image stitching. Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, 3262–3269.