Quasi-homography warps in image stitching
Nan Li Yifang Xu Chao Wang

	






Quasi-homography Warps in Image Stitching
    Nan Li, N. Li is with the Center for Applied Mathematics, Tianjin University, Tianjin 300072, China. E-mail: nan@tju.edu.cn.Yifang Xu^*, and Chao Wang
Y. Xu is with the Center for Combinatorics, Nankai University, Tianjin 300071, China. Email: xyf@mail.nankai.edu.cn.
C. Wang is with the Department of Software, Nankai University, Tianjin 300071, China. Email: wangchao@nankai.edu.cn.
    January 27, 2017
====================================================================================================================================================================================================================================================================================================================================================================================================





The naturalness of warps is gaining extensive attentions in image stitching.
Recent warps such as SPHP and AANAP, use global similarity warps to mitigate projective distortion (which enlarges regions), however, they necessarily bring in perspective distortion (which generates inconsistencies). In this paper, we propose a novel quasi-homography warp, which effectively balances the perspective distortion against the projective distortion in the non-overlapping region to create a more natural-looking panorama. Our approach formulates the warp as the solution of a bivariate system, where perspective distortion and projective distortion are characterized as slope preservation and scale linearization respectively. Because our proposed warp only relies on a global homography, thus it is totally parameter-free. A comprehensive experiment shows that a quasi-homography warp outperforms some state-of-the-art warps in urban scenes, including homography, AutoStitch and SPHP. A user study demonstrates that it wins most users' favor, comparing to homography and SPHP.




Image stitching, image warping, natural-looking, projective distortion, perspective distortion.








§ INTRODUCTION

Image stitching plays an important role in many multimedia applications, such like panoramic videos <cit.>, virtual reality <cit.>. Conventionally, image stitching is a process of composing multiple images with overlapping fields of views, to produce a wide-view panorama <cit.>, where the first stage is to determine a warp for each image and transform it into a common coordinate system, then the warped images are composed <cit.> and blended <cit.> into a final mosaic.
Evaluations of warping include the alignment quality in the overlapping region and the naturalness quality in the non-overlapping region.

Early warps focus on the alignment quality, which is measured in two different aspects:

  
  * (global) the root mean squared error on the set of feature correspondences,
  
  * (local) the patch-based mean error along a stitching seam.

Global warps such as similarity or homography warps <cit.>, aim to minimize alignment errors between overlapping pixels via a uniform transformation. Homography is the most frequently used warp, because it is the most flexible planar transformation which preserves all straight lines. For a better global alignment quality, recent spatially-varying warps <cit.> use multiple local transformations instead of a single global one to address the large parallax issue in the overlapping region. Some seam-driven warps <cit.> address the same problem by pursuing a better local alignment quality in the overlapping region, such that there exists a local region to be seamlessly
blended.


Recent warps concentrate more on the naturalness quality, which is embodied in two consistency properties:

  
  * (local) the region of any object should be consistent with its appearance in the original,
  
  * (global) the perspective relation of the same object should be consistent between different images.

Violations of consistencies lead to two types of distortion:

  
  * (projective) the region of an object is enlarged, compared to its appearance in the original (see people and trees in Fig. <ref>(a)),
  
  * (perspective) the perspectives of an object in two images are inconsistent with each other (see buildings and signs in Fig. <ref>(b)).

Similarity warps automatically satisfy the local consistency, since they purely involve translation, rotation and uniformly scaling, but may suffer from perspective distortion.
Homography warps conventionally satisfy the global consistency, if a good alignment quality is guaranteed,
but may suffer from projective distortion.
Warps such like the shape-preserving half-projective (SPHP) warp <cit.> and the adaptive as-natural-as-possible (AANAP) warp <cit.> use a spatial combination of homography and similarity warps to mitigate projective distortion in the non-overlapping region.
Other warps address the same problem via a joint optimization of alignment and naturalness qualities, which either constrains the warp resembles a similarity as a whole <cit.>, or constrains the warp preserves detected straight lines <cit.>.

In this paper, we propose a quasi-homography warp, which balances the projective distortion against the perspective distortion in the non-overlapping region, to create a more natural-looking mosaic (see Fig. <ref>(c)). Our proposed warp only relies on a global homography, thus it is totally parameter-free. The rest of the paper is organized as follows. Section <ref> describes some recent works. Section <ref> provides a naturalness analysis of image warps, where Section <ref> presents two intuitive tools to demonstrate projective distortion and perspective distortion via mathematical derivations. Section <ref> and <ref> employ such tools to analyze homography and SPHP warps in aspects of local and global consistencies. Our quasi-homography warp is defined as a solution of a bivariate system in Section <ref>, which is based on a new formulation of homography in Section <ref>. Implementation details (including two-image stitching and multiple-image stitching) and method variations (including orientation rectification and partition refinement) are proposed in Section <ref>. Section <ref> presents a comparison experiment and a user study, which demonstrate that the quasi-homography warp not only outperforms some state-of-the-art warps in urban scenes, but also wins most users' favor. Finally, conclusions are drawn in Section <ref> and some mathematical formulas are explained in Appendix.




§ RELATED WORK

In this section, we review some recent works of image warps in aspects of alignment and naturalness qualities respectively. For more fundamental concepts about image stitching, please refer to a comprehensive survey <cit.> by Szeliski.



 §.§ Warps for Better Alignment

Conventional stitching methods always employ global warps such as similarity, affine and homography, to align images in the overlapping region <cit.>. Global warps are robust but often not flexible enough to provide accurate alignment. Gao et al. <cit.> proposed a dual-homography warp to address scenes with two dominant planes by a weighted sum of two homographies. Lin et al. <cit.> proposed a smoothly varying affine (SVA) warp to replace a global affine warp with a smoothly affine stitching field, which is more flexible and maintains much of the motion generalization properties of affine or homography. Zaragoza et al. <cit.> proposed an as-projective-as-possible (APAP) warp in a moving DLT framework, which is able to accurately register images that differ by more than a pure rotation. Lou et al. <cit.> proposed a piecewise alignment method, which approximates regions of image with planes by incorporating piecewise local geometric models.

Other methods combine image alignment with seam-cutting approaches <cit.>, to find a locally registered area which is seamlessly blended instead of aligning the overlapping region globally. Gao et al. <cit.> proposed a seam-driven framework, which searches a homography with minimal seam costs instead of minimal alignment errors on a set of feature
correspondences. Zhang and Liu <cit.> proposed a parallax-tolerant warp, which combines homography and content-preserving warps to locally register images. Lin et al. <cit.> proposed a seam-guided local alignment warp, which iteratively improves the warp by adaptive feature weighting according to the distance to current seams.



 §.§ Warps for Better Naturalness

Many efforts have been devoted to mitigate distortion in the non-overlapping region for creating a natural-looking mosaic. A pioneering work <cit.> uses spherical or cylindrical warps to produce multi-perspective results to address this problem, but it necessarily curves straight lines.

Recently, some methods take advantage of global similarity (preserves the original perspective) to mitigate projective distortion in the non-overlapping region. Chang et al. <cit.> proposed a SPHP warp that spatially combines a homography warp and a similarity warp, which makes the homography maintain good alignment in the overlapping region while the similarity keep the original perspective in the non-overlapping region. Lin and Pankanti <cit.> proposed an AANAP warp, which combines a linearized homography warp and a global similarity warp with the smallest rotation angle to create natural-looking mosaics.

Other methods model their warps as mesh deformations via energy minimization, which address naturalness quality issues by enforcing different constraints. Chen et al. <cit.> proposed a global-similarity-prior (GSP) warp, which constrains the warp resembles a similarity as a whole. Zhang et al. <cit.> proposed a warp that produces an orthogonal projection of a wide-baseline scene by constraining it preserves extracted straight lines,
and allows perspective corrections via scale preservation.






§ NATURALNESS ANALYSIS OF IMAGE WARPS

This section describes a naturalness analysis of image warps. First, the global consistency is characterized as line-preserving, where the perspective distortion is illustrated through a mesh-to-mesh transformation, and the local consistency is characterized as uniformly-scaling, where the projection distortion is demonstrated via the linearity of a scaling function. Then, we analyze the naturalness of homography and SPHP warps by these tools.



 §.§ Mathematical Setup

Let I and I^' denote the target image and the reference image respectively.
A warp ℋ is a planar transformation <cit.>, which relates pixel coordinates (x,y)∈ I to (x',y')∈ I^', where

    {[ x^'=f(x,y); y^'=g(x,y) ]..


If ℋ is of global consistency, then it must be line-preserving, i.e., a straight line l={(x+z,y+kz)|z∈ℝ}∈ I should be mapped to a straight line l^'={(x^'+z^',y^'+k^'z^')|z^'∈ℝ}∈ I^'. Actually, the calculation of the slope k^' provides a criterion to validate line-preserving, i.e., ℋ is line-preserving, if and only if

    k^' = g(x+z,y+kz)-g(x,y)/f(x+z,y+kz)-f(x,y)

is independent of z. Its proof is easy. Given a point (x,y)∈ I and a slope k, then they define a straight line l={(x+z,y+kz)|z∈ℝ}∈ I. If k^' calculated by (<ref>) is a constant, then l is mapped to a straight line l^'={(x^'+z^',y^'+k^'z^')|z^'∈ℝ}∈ I^', which is defined by (x',y')∈ I^' and k^'.
Since k^' only depends on (x,y) and k, we denote it by slope(x,y,k).

Suppose ℋ is line-preserving and 𝒞^1 continuous, then

    slope(x,y,k)     =lim_z→0g(x+z,y+kz)-g(x,y)/f(x+z,y+kz)-f(x,y)
        =g_x(x,y)+kg_y(x,y)/f_x(x,y)+kf_y(x,y),

where f_x,f_y,g_x,g_y denote the partial derivatives of f and g.
In fact, there exists a mesh-to-mesh transformation that maps all horizontal lines and vertical lines to straight lines with slopes

    slope(x,y,0)     =g_x(x,y)/f_x(x,y),


    slope(x,y,∞)     =g_y(x,y)/f_y(x,y),

which are independent of x and y respectively.
Consequently, any point (x,y)∈ I can be expressed as the intersection point of a horizontal line and a vertical line, which is corresponding to the point (x^',y^')∈ I^' as the intersection point of two lines with slopes slope(x,y,0) and slope(x,y,∞). In the rest of the paper, we constantly employ this mesh-to-mesh transformation to demonstrate perspective distortion comparisons among different warps (see Fig. <ref>).

On the other side, if ℋ is of local consistency, then it must be uniformly-scaling. Actually, the local consistency automatically holds for similarity warps, because they purely involve translation, rotation and uniformly scaling. Suppose ℋ is not only line-preserving but also uniformly-scaling, then a line segment s={(x+z,y+kz)|z∈[z_1,z_2]}∈ I should be mapped to a line segment s^'={(x^'+z^',y^'+k^'z^')|z^'∈[z^'_1,z^'_2]}∈ I^' with a uniform scaling factor.
Conversely, the linearity of a scaling function on arbitrary line is a necessary condition of the local consistency.

By assuming cameras are oriented and motions are horizontal, there should exist a horizontal line l_x={(x,y_*)|x∈ℝ}∈ I which remains a horizontal line l_x^'={(x^',y_*^')|x^'∈ℝ}∈ I^', if a good alignment is guaranteed. In fact, l_x is roughly located in the horizontal plane of cameras, and y_* satisfies

    slope(x,y_*,0)=g_x(x,y_*)/f_x(x,y_*)=0.

Given a point (x_*,y_*)∈ l_x, then for ∀(x,y_*)∈ l_x, |f(x,y_*)-f(x_*,y_*)| should equal to a uniform scaling factor times |x-x_*|. In other words, f(x,y_*) should be linear in x. In the rest of the paper, we constantly employ the linearity to demonstrate projective distortion comparisons among different warps (see Fig. <ref>).

Some other notations are stated as follows. Let 𝒪 denote the overlapping region and l_y={(x_*,y) | y∈ℝ} denote a vertical line which divides ℝ^2 into half spaces R_O={(x,y)|x≤ x_*} and R_Q={(x,y)|x_*< x}, such that 𝒪⊂ R_O. Our proposed warp ℋ_† is a spatial combination of a homography warp ℋ_0 within R_O and a squeezed homography warp ℋ_* within R_Q, where R_O^' and R_Q^' are respective half spaces after warping.



 §.§ Naturalness Analysis of Homography

A homography warp ℋ_0 is the most flexible warp for better alignment, which is normally defined as

    f_0(x,y)     =h_1x+h_2y+h_3/h_7x+h_8y+1,
    
      g_0(x,y)     =h_4x+h_5y+h_6/h_7x+h_8y+1,

where h_1-h_8 are eight parameters. It is easy to certify that ℋ_0 is line-preserving, since the slope k^' in (<ref>) is independent of z. To illustrate the property more intuitively, we draw a mesh-to-mesh transformation (see Fig. <ref>(b)), where horizontal lines and vertical lines are mapped to straight lines with slopes

    slope(x,y,0)     =(h_4h_8-h_5h_7)y+(h_4-h_6h_7)/(h_1
    h_8-h_2h_7)y+(h_1-h_3h_7),
    slope(x,y,∞)     =(h_4h_8-h_5h_7)x+(h_6h_8-h_5)/(h_1
    h_8-h_2h_7)x+(h_3h_8-h_2).


Under the assumption that cameras are oriented and motions are horizontal, for l_x={(x,y_*)|x∈ℝ}∈ I, we derive

    y_* =h_6h_7-h_4/h_4h_8-h_5h_7,

by solving the equation (<ref>). For ∀(x,y_*)∈ l_x,

    f_0(x,y_*)=h_1x+h_2y_*+h_3/h_7x+h_8y_*+1,

is non-linear in x when h_7≠0 (see Fig. <ref>(b)), which indicates the invalidation of uniformly-scaling.

In summary, homography warps conventionally satisfy the global consistency if a good alignment is guaranteed, however they usually suffer from projective distortion in the non-overlapping region (see Table <ref>).
For example, the people and the tree are enlarged in Fig. <ref>(a) comparing to the original.



 §.§ Naturalness Analysis of SPHP


To overcome such drawbacks of homography warps, Chang et al. <cit.> proposed a shape-preserving half-projective (SPHP) warp, which is a spatial combination of a homography warp and a similarity warp, to create a natural-looking
multi-perspective panorama.

Specifically, after adopting the change of coordinates, SPHP divides ℝ^2 into three regions. 1. R_H={(u,v)|u≤ u_1}, where a homography warp is applied to achieve a good alignment. 2. R_S={(u,v) | u_2≤ u}, where a similarity warp is applied to mitigate projective distortion. 3. R_T={(u,v) | u_1<u<u_2}, a buffer region where a warp is applied to gradually change a homography warp to a similarity warp. Consequently, a SPHP warp 𝒲 is defined as

    w(u,v)={[    H(u,v), (u,v)∈ R_H;    T(u,v), (u,v)∈ R_T;    S(u,v), (u,v)∈ R_S ].,

where u_1 and u_2 are parameters, such that 𝒲 can approach a similarity warp as much as possible. Note that, the change of coordinates plays an important role in SPHP, since a similarity simply combines a homography via a single partition line.

Both homography and similarity are line-preserving, thus 𝒲 is certainly of global consistency in R_H and R_S respectively. However, 𝒲 may suffer from line-bending within R_T, because of its non-linearity.
Moreover, perspectives of R_H and R_S may contradict each other.
For example, parallels remain parallels in R_S, while they do not in R_H (see Fig. <ref>(c)).
𝒲 is certainly of local consistency in R_S, because a similarity warp is applied (see Fig. <ref>(c)).

In summary, SPHP warps achieve the alignment quality as good as homography warps in R_H, and the local consistency as good as similarity warps in R_S. However, SPHP warps may suffer from line-bending in R_T and perspective distortion between R_H and R_S (see Table <ref>). Note that, the non-linearity of T(u,v) in R_T merely blends certain lines in theory, but it is still possible to preserve visible straight lines in practice. Many results in <cit.> justify that SPHP is capable of doing so. Unfortunately, it will get worse for urban scenes, which are filled with visible lines and visible parallels (see the sign in Fig. <ref>(b)).
It is also worth noting that, SPHP creates a multi-perspective panorama, thus different perspectives may contradict each other (see buildings in Fig. <ref>(b)).

These naturalness analysis of homography and SPHP warps motivate us to construct a warp, which achieves a good balance between the perspective distortion and the projective distortion in the non-overlapping region,
via relaxing the local and global consistencies such that they are both partially satisfied.







§ PROPOSED WARPS

This section presents how to construct a warp for balancing perspective distortion against projective distortion
in the non-overlapping region. First, we propose a different formulation of the homography warp to characterize the global consistency as slope preservation while the local consistency as scale linearization respectively. Then, we describe how to adopt this formulation to present a quasi-homography warp, which squeezes the mesh of the corresponding homography warp but without varying its shape.



 §.§ Review of Homography

Given eight parameters h_1-h_8, we formulate a homography warp ℋ_0 in another way, as the solution of a bivariate system

    y^'-g_0(x_*,y)/x^'-f_0(x_*,y)   =slope(x,y,0),
    y^'-g_0(x,y_*)/x^'-f_0(x,y_*)   =slope(x,y,∞),

where (x_*,y) and (x,y_*) are projections of a point (x,y) onto l_y={(x_*,y) | y∈ℝ} and l_x={(x,y_*) | x∈ℝ} respectively (see Fig. <ref>(a)). Besides, equations of f_0, g_0 and slope(x,y,0), slope(x,y,∞) are given in (<ref>,<ref>,<ref>,<ref>).

Our formulation (<ref>,<ref>) is equivalent to (<ref>,<ref>).
In fact, it is easy to check that (<ref>,<ref>) is a solution of (<ref>,<ref>). Furthermore, it is the unique solution, because the Jacobian is invertible if and only if slope(x,y,0)≠slope(x,y,∞).
Then, comparing with (<ref>,<ref>), our formulation (<ref>,<ref>) characterizes the global consistency as slope preservation while the local consistency as scale linearization respectively. Intuitively, slope(x,y,0) and slope(x,y,∞) formulate the shape of the mesh, while f_0(x,y_*) and g_0(x_*,y) formulate the density of the mesh (see Fig. <ref>(b)). It should be noticed that we made no assumptions on x_* or y_* in the above analysis. In the next subsection, we will assume that l_y isolates the overlapping region 𝒪 and l_x remains horizontal under ℋ_0, for stitching multiple images captured by oriented cameras via horizontal motions.



 §.§ Quasi-homography

Our proposed warp makes use of the formulation (<ref>,<ref>) to balance perspective distortion
against projective distortion in the non-overlapping region. First, we divide ℝ^2 by the vertical line  l_y={(x_*,y) | y∈ℝ} into half spaces R_O={(x,y)|x≤ x_*} and R_Q={(x,y)|x_*< x}, where the overlapping region 𝒪⊂ R_O.
Then, we formulate our warp ℋ_† as the solution of a bivariate system

    y^'-g_0(x_*,y)/x^'-f_0(x_*,y)   =slope(x,y,0),
    y^'-g_0(x,y_*)/x^'-f_†(x,y_*)   =slope(x,y,∞),

where y_* satisfies (<ref>) and f_† (x,y_*) is defined as

    f_† (x,y_*)=
    
    f_0(x,y_*), if (x,y_*)∈ R_O,
    
    f_*(x,y_*), if (x,y_*)∈ R_Q,


    f_*(x,y_*)=f_0(x_*,y_*)+f_0^'(x_*,y_*)(x-x_*),

on the horizontal line l_x={(x,y_*) | x∈ℝ}.
In fact, f_*(x,y_*) is the first-order truncation of the Taylor's series for f_0(x,y_*) at x=x_*,
which successfully makes f_† (x,y_*) piece-wise 𝒞^1 continuous and linear in x within R_Q.

Because the Jacobian of (<ref>,<ref>) is invertible, it possesses a unique solution ℋ_† as

    ℋ_†={[       ℋ_0, (x,y)∈ R_O;       ℋ_*, (x,y)∈ R_Q ].,

where

    x^'=f_†(x,y)     =
    f_0(x,y), if (x,y)∈ R_O,
    
     f_*(x,y), if (x,y)∈ R_Q,
    
      y^'=g_†(x,y)     =
    g_0(x,y), if (x,y)∈ R_O,
    
     g_*(x,y), if (x,y)∈ R_Q,

where f_*(x,y) and g_*(x,y) are rational functions in variables x and y, whose coefficients are polynomial functions in h_1-h_8 and x_*.
The detailed derivations are presented in Appendix.
In fact, the warp ℋ_† just squeezes the meshes of homography in the horizontal direction but without varying its shape (see Fig. <ref>(c)). In this sense, we call ℋ_† a quasi-homography warp that corresponds to a homography warp ℋ_0. A quasi-homography warp maintains good alignment in R_O as a homography warp, and it mitigates perspective distortion and projective distortion simultaneously via slope preservation and scale linearization in R_Q. Intuitively, ℋ_† relaxes arbitrary line-preserving to only preserving the shape of the mesh (see Fig. <ref>(d)), while relaxes uniformly-scaling everywhere to only uniforming the density of the mesh on l_x in R_Q (see Fig. <ref>(d)).

On the other hand, since ℋ_† just squeezes the mesh of ℋ_0 but without varying its shape, ℋ_† is an injection if ℋ_0 is an injection.
Given (x^',y^')∈ R_O^', then (x,y)∈ R_O is determined by ℋ_0^-1. Given (x^',y^')∈ R_Q^', then (x,y)∈ R_Q is determined by solving (<ref>,<ref>) (regard x,y as unknowns)

    x     =(m_1x^2+m_2x+m_3), 
     y     =(h_6h_7-h_
    4)x'+(h_1-h_3h_7)y'+(h_3h_4-h_1h_6)/(h_4h_8-h_5h_7)x'+(h_2h_7-h_1h_8)y'+(h_1h
    _5-h_2h_4),

where m_1-m_3 are polynomial functions in x',y',x_*, and h_1-h_8. The detailed derivations are presented in Appendix.

Note that, though both SPHP and quasi-homography warps adopt a spatial combination of a homography warp and another warp to create more natural-looking mosaics, their motivations and frameworks are different. SPHP focuses on the local consistency, to create a natural-looking multi-perspective
panorama. Quasi-homography concentrates on balancing global and local consistencies, to generate a natural-looking single-perspective panorama. SPHP introduces a change of coordinates such that a similarity combines a homography via a single partition line, and a buffer region such that a homography gradually changes into a similarity. Quasi-homography reorganizes homography's point correspondences via solving the bivariate system (<ref>,<ref>), where the shape is preserved and the size is squeezed.

It is worth noting that the construction of quasi-homography makes no assumptions on the special horizontal line l_x and the vertical partition line l_y. For stitching multiple images captured by oriented cameras via horizontal motions, the horizontal line that remains horizontal best measures the projective distortion. Therefore, quasi-homography can preserve horizontal lines or nearly-horizontal lines better than SPHP (see result comparisons in Section <ref>), and ordinary users prefer such stitching results in urban scenes (see user study in Section <ref>).

In summary, quasi-homography warps achieve a good alignment quality as homography warps in R_O, while partially possess the local consistency and the global consistency in R_Q, such that perspective distortion and projective distortion are balanced (see Table <ref>). Note that the warp may still suffer from diagonal line-bending and vertical region-enlarging within R_Q, because line-preserving and uniformly-scaling are relaxed to partially valid. Please see more details in Section <ref>.




§ IMPLEMENTATION

In this section, we first present more implementation details of our quasi-homography in two-image stitching and multiple-image stitching, then we propose two variations of the method including orientation rectification and partition refinement.



 §.§ Two-image Stitching

Given a pair of two images, which are captured by oriented cameras via
horizontal motions, if a homography warp ℋ_0 can be estimated with a good alignment quality in the overlapping region, then a quasi-homography warp ℋ_† can be calculated, which smoothly extrapolates from ℋ_0 in R_O into ℋ_* in R_Q. A brief algorithm is given in Algorithm <ref>.




 §.§ Multiple-image Stitching

Given a sequence of multiple images, which are captured by oriented cameras via horizontal motions, our warping method consists of three stages. In the first stage, we pick a reference image as a standard perspective, such that other images should be consistent with it. Then we estimate a homography warp for each image and transform them in the coordinate system of the reference image via bundle adjustment as in <cit.> and calculate pairwise quasi-homography warps of adjacent images. Finally, we concatenate other images to the reference one by a chained composite map of pairwise quasi-homgraphy warps.

Fig. <ref> illustrates an example of the concatenation procedure for stitching five images. First we select I_3 as the reference one such that perspectives of other four images should agree with it.
Then we estimate homography warps ℋ_0^1→3, ℋ_0^2→3, ℋ_0^4→3, ℋ_0^5→3 via bundle adjustment <cit.> and calculate pairwise quasi-homography warps ℋ_†^1→2, ℋ_†^2→3, ℋ_†^4→3, ℋ_†^5→4. Finally, we concatenate I_1 and I_5 to I_3 by

    ℋ_†^1→3=ℋ_†^2→3∘ℋ_†^1→2,
    ℋ_†^5→3=ℋ_†^4→3∘ℋ_†^5→4.

Therefore, the concatenation warp for every image is a chained composite map of pairwise quasi-homography warps.




 §.§ Orientation Rectification

In urban scenes, users accustom to taking pictures by oriented cameras via horizontal motions, hence any vertical line in the target image is expected to be transformed to a vertical line in the warped result. However, it inevitably sacrifices the alignment quality in the overlapping region.

In order to achieve orientation rectification, we incorporate an extra constraint in the homography estimation, which constrains that the external vertical boundary of the target image preserves vertical in the warped result.

Then for a homography warp ℋ_0 as (<ref>,<ref>), it should satisfy

    f_0(w,0)=f_0(w,h) ⇔ h_8=h_2(h_7w+h_9)/h_1w+h_3,

where w and h are the width and the height of I respectively.
A global homography is then estimated by solving

    min∑_i=1^N a_i h^2 s.t.  h=1, h_8=h_2(h_7w+h_9)/h_1w+h_3.

 Because the quasi-homography warp just squeezes the mesh of a homography warp but without varying its shape,
 the external vertical boundary still preserves vertical (see Fig. <ref>).




 §.§ Partition Refinement

In our analysis of quasi-homography warps in Section <ref>, the uniform scaling factor on the special horizontal line l_x in R_Q depends on the linearized scaling function (<ref>). Moreover, it depends on the determination of the partition point (x_*,y_*). In fact, the factor is more accurate if (x_*,y_*) is better aligned.

Hence, we replace the partition line l_y closest to the border of the overlapping region and the non-overlapping region, by it closest to the external border of the seam for further refinement (see Fig. <ref>).




§ EXPERIMENTS

We experimented our proposed method on a range of images captured through both rear and front cameras in urban scenes. In our experiments, we employ SIFT <cit.> to extract and match features, RANSAC <cit.> to estimate a global homography, and seam-cutting <cit.> to blend the overlapping region. Codes are implemented in OpenCV 2.4.9 and generally take 1s to 2s on a desktop PC with Intel i5 3.0GHz CPU and 8GB memory to stitching two images with 800× 600 resolution by Algorithm <ref>, where the calculation of the quasi-homography warp only takes 0.1s (including the forward map and the backward map). We used the codes of AutoStitch[http://matthewalunbrown.com/autostitch/autostitch.html] and SPHP[http://www.cmlab.csie.ntu.edu.tw/∼frank/] from the authors' homepage in the experiment.



 §.§ Result Comparisons

We compared our quasi-homography warp to state-of-the-art warps in urban scenes, including homography,  AutoStitch and SPHP. Because our method focuses on the naturalness quality in the non-overlapping region, we only compare with methods using global homography alignment in the overlapping region,
while not comparing to methods using spatially-varying warps.
Nevertheless, some urban scenes with repetitive structures still cause alignment issues <cit.>, which may limit the application of our method.
Therefore, we use a more robust feature matching method RepMatch <cit.>, and a more robust RANSAC solution USAC <cit.> for estimating a global homography, to generalize our proposed method in urban scenes. Non-planar scenes may cause outlier removal issues <cit.>, but fortunately, <cit.> justifies that a simple RANSAC-driven homography still works reasonably well even for such cases.

In order to highlight the comparison of the naturalness quality in the non-overlapping region, for homography, SPHP and quasi-homography, we use the same homography alignment and the same seam-cutting composition in the overlapping region.

Fig. <ref> illustrates a naturalness comparison for stitching two and three images from data sets of DHW <cit.> and SPHP <cit.>.
Homography preserves straight lines, but it enlarges the regions of cars and people. SPHP preserves respective perspectives, but it causes contradictions in the ground and wires.
AutoStitch uses a spherical projection to produce a multi-perspective stitching result. Quasi-homography uses a planar projection to produce a single-perspective stitching result, which appears as oriented line-preserving and uniformly-scaling. More results from other data sets including DHW <cit.>, SPHP <cit.>, GSP <cit.> and APAP <cit.> are available in the supplementary material.

Fig. <ref> illustrates a naturalness comparison for stitching two sequences of ten and nine images. Homography stretches cars, trees and people. AutoStitch presents a nonlinear-view stitching result.  Quasi-homography creates a natural-looking linear-view stitching result. More results for stitching long sequences of images are available in the supplementary material.





 §.§ User Study

To investigate whether quasi-homography is more preferred by users in urban scenes, we conduct a user study to compare our results to homography and SPHP. We invite 17 participants to rank 20 unannotated groups of stitching results, including 5 groups from the front cameras and 15 groups from rear ones. For each group, we adopt the same homography alignment and the same seam-cutting composition, and all parameters are set to produce optimal final results. In our study, each participant ranks three unannotated stitching results in each group, and a score is recorded by assigning weights 4, 2 and 1 to Rank 1, 2 and 3. Twenty groups of stitching results are available in the supplementary material.

Table <ref> shows a summary of rank votes and total scores for three warps, and the histogram of three scores is shown in  Fig. <ref> in three aspects. This user study demonstrates that stitching results of quasi-homography warps win most users' favor in urban scenes.



.52
Score results of user study.

0.48
Methods     4cResults
 2-5
     Rank 1     Rank 2     Rank  3     Total score
 Homography     69     210     61       757
 SPHP <cit.>     19     56     265     453
 Quasi-homography     252     74     14       1170
 

.475





    < g r a p h i c s >

Histogram of scores.





 §.§ Failure Cases

Experiments show that quasi-homography warps usually ba-lance the projective distortion against the perspective distortion in the non-overlapping region, but there still exist some limitations. For example, diagonal lines may not stay straight anymore and regions of objects may suffer from vertical stretches (especially for stitching images from different planes). Two of failure examples are shown in Fig. <ref>.



§ CONCLUSION


In this paper, we propose a quasi-homography warp, which balances the perspective distortion against the projective distortion in the non-overlapping region, to create natural-looking single-perspective panoramas. Experiments show that stitching results of quasi-homography outperform some state-of-the-art warps under urban scenes, including homography, AutoStitch and SPHP. A user study demonstrates that quasi-homography wins most users' favor as well, comparing to homography and SPHP.

Future works include generalizing quasi-homography warps into spatially-varying warping frameworks like in <cit.> to improve alignment qualities as well in the overlapping region, and incorporating our method in SPHP to create more natural-looking multi-perspective panoramas. Multimedia applications that are relevant to image stitching could also be considered, such as feature selection <cit.>, video composition <cit.>, cross-media stitching <cit.> and action recognition <cit.>.

[]
The forward map (<ref>,<ref>) and the backward map (<ref>,<ref>) of a quasi-homography warp (<ref>,<ref>) are solved by the computer algebra system Maple via commands

    solve({(<ref>),(<ref>)},{x^',y^'}),

where x^',y^' are unknowns and x,y,x_*,y_*,h_1-h_8 are parameters,

    solve({(<ref>),(<ref>)},{x,y})

where x,y are unknowns and x',y',x_*,y_*,h_1-h_8 are parameters.

Because the analytic solutions of (<ref>,<ref>) contain over one thousand monomials, we omitted their complicated expressions here.
A maple worksheet is available to download at the page http://cam.tju.edu.cn/ nan/QH.htmlhttp://cam.tju.edu.cn/%7enan/QH.html for readers to verify the correctness.
Actually, if the parameters h_1-h_8 and a pair of x,y or x^',y^' are given, we plug their values into (<ref>,<ref>) or (<ref>,<ref>) then solve the forward or the backward map directly, without using these analytic solutions.
A symbolic proof for the line-preserving property of homography warps and the equivalence of two homography formulations are  included in the worksheet as well.








IEEEtran

10
	
	url@samestyle
	
	
	
	
	
	
	Tzavidas2005Multicamera
	S. Tzavidas and A. K. Katsaggelos, “A multicamera setup for generating stereo
	panoramic video,” IEEE Transactions on Multimedia, vol. 7, no. 5, pp.
	880–890, 2005.
	
	Sun2005Region
	X. Sun, J. Foote, D. Kimber, and B. S. Manjunath, “Region of interest
	extraction and virtual camera control based on panoramic video capturing,”
	IEEE Transactions on Multimedia, vol. 7, no. 5, pp. 981–990, 2005.
	
	Gaddam2016Tiling
	V. R. Gaddam, M. Riegler, R. Eg, and P. Halvorsen, “Tiling in interactive
	panoramic video: Approaches and evaluation,” IEEE Transactions on
		Multimedia, vol. 18, no. 9, pp. 1819–1831, 2016.
	
	Shum2005A
	H. Y. Shum, K. T. Ng, and S. C. Chan, “A virtual reality system using the
	concentric mosaic: construction, rendering, and data compression,”
	IEEE Transactions on Multimedia, vol. 7, no. 1, pp. 85–95, 2005.
	
	Tang2005A
	W. K. Tang, T. T. Wong, and P. A. Heng, “A system for real-time panorama
	generation and display in tele-immersive applications,” IEEE
		Transactions on Multimedia, vol. 7, no. 2, pp. 280–292, 2005.
	
	Zhao2013Cube2Video
	Q. Zhao, L. Wan, W. Feng, and J. Zhang, “Cube2Video: Navigate between cubic
	panoramas in real-time,” IEEE Transactions on Multimedia, vol. 15,
	no. 8, pp. 1745–1754, 2013.
	
	szeliski2006image
	R. Szeliski, “Image alignment and stitching: A tutorial,” Found. Trends
		Comput. Graph. Vis., vol. 2, no. 1, pp. 1–104, 2006.
	
	peleg1981elimination
	S. Peleg, “Elimination of seams from photomosaics,” Comput. Graph.
		Image Process., vol. 16, no. 1, pp. 90–94, 1981.
	
	duplaquet1998building
	M.-L. Duplaquet, “Building large image mosaics with invisible seam lines,” in
	Proc. SPIE Visual Information Processing VII, 1998, pp. 369–377.
	
	davis1998mosaics
	J. Davis, “Mosaics of scenes with moving objects,” in Proc. IEEE Conf.
		Comput. Vis. Pattern Recog., June. 1998, pp. 354–360.
	
	efros2001image
	A. A. Efros and W. T. Freeman, “Image quilting for texture synthesis and
	transfer,” in Proc. ACM SIGGRAPH, 2001, pp. 341–346.
	
	mills2009image
	A. Mills and G. Dudek, “Image stitching with dynamic elements,” Image
		Vis. Comput., vol. 27, no. 10, pp. 1593–1602, 2009.
	
	burt1983multiresolution
	P. J. Burt and E. H. Adelson, “A multiresolution spline with application to
	image mosaics,” ACM Trans. Graphics, vol. 2, no. 4, pp. 217–236,
	1983.
	
	Perez:2003
	P. Pérez, M. Gangnet, and A. Blake, “Poisson image editing,” ACM
		Trans. Graphics, vol. 22, no. 3, pp. 313–318, 2003.
	
	levin2004seamless
	A. Levin, A. Zomet, S. Peleg, and Y. Weiss, “Seamless image stitching in the
	gradient domain,” in Proc. Eur. Conf. Comput. Vis., May 2004, pp.
	377–389.
	
	hartley2003multiple
	R. Hartley and A. Zisserman, Multiple view geometry in computer
		vision.1em plus 0.5em minus 0.4emCambridge univ. press, 2003.
	
	gao2011constructing
	J. Gao, S. J. Kim, and M. S. Brown, “Constructing image panoramas using
	dual-homography warping,” in Proc. IEEE Conf. Comput. Vis. Pattern
		Recog., Jun. 2011, pp. 49–56.
	
	lin2011smoothly
	W.-Y. Lin, S. Liu, Y. Matsushita, T.-T. Ng, and L.-F. Cheong, “Smoothly
	varying affine stitching,” in Proc. IEEE Conf. Comput. Vis. Pattern
		Recog., Jun. 2011, pp. 345–352.
	
	zaragoza2013projective
	J. Zaragoza, T.-J. Chin, M. S. Brown, and D. Suter, “As-projective-as-possible
	image stitching with moving DLT,” in Proc. IEEE Conf. Comput. Vis.
		Pattern Recog., Jun. 2013, pp. 2339–2346.
	
	Lou2014Image
	Z. Lou and T. Gevers, “Image alignment by piecewise planar region matching,”
	IEEE Transactions on Multimedia, vol. 16, no. 7, pp. 2052–2061, 2014.
	
	gao2013seam
	J. Gao, Y. Li, T.-J. Chin, and M. S. Brown, “Seam-driven image stitching,”
	Eurographics, pp. 45–48, 2013.
	
	zhang2014parallax
	F. Zhang and F. Liu, “Parallax-tolerant image stitching,” in Proc. IEEE
		Conf. Comput. Vis. Pattern Recog., May 2014, pp. 3262–3269.
	
	lin2016seam
	K. Lin, N. Jiang, L.-F. Cheong, M. Do, and J. Lu, “SEAGULL: Seam-guided
	local alignment for parallax-tolerant image stitching,” in Proc. Eur.
		Conf. Comput. Vis., Oct. 2016.
	
	chang2014shape
	C.-H. Chang, Y. Sato, and Y.-Y. Chuang, “Shape-preserving half-projective
	warps for image stitching,” in Proc. IEEE Conf. Comput. Vis. Pattern
		Recog., May 2014, pp. 3254–3261.
	
	lin2015adaptive
	C.-C. Lin, S. U. Pankanti, K. N. Ramamurthy, and A. Y. Aravkin, “Adaptive
	as-natural-as-possible image stitching,” in Proc. IEEE Conf. Comput.
		Vis. Pattern Recog., Jun. 2015, pp. 1155–1163.
	
	Chen:2016:NIS
	Y.-S. Chen and Y.-Y. Chuang, “Natural image stitching with the global
	similarity prior,” in Proc. Eur. Conf. Comput. Vis., 2016, pp.
	186–201.
	
	zhang2016multi
	G. Zhang, Y. He, W. Chen, J. Jia, and H. Bao, “Multi-viewpoint panorama
	construction with wide-baseline images,” IEEE Trans. Image Process.,
	vol. 25, no. 7, pp. 3099–3111, 2016.
	
	boykov2001fast
	Y. Boykov, O. Veksler, and R. Zabih, “Fast approximate energy minimization via
	graph cuts,” IEEE Trans. Pattern Anal. Mach. Intell., vol. 23,
	no. 11, pp. 1222–1239, Nov. 2001.
	
	agarwala2004interactive
	A. Agarwala, M. Dontcheva, M. Agrawala, S. Drucker, A. Colburn, B. Curless,
	D. Salesin, and M. Cohen, “Interactive digital photomontage,” ACM
		Trans. Graphics, vol. 23, no. 3, pp. 294–302, 2004.
	
	kwatra2003graphcut
	V. Kwatra, A. Schödl, I. Essa, G. Turk, and A. Bobick, “Graphcut textures:
	image and video synthesis using graph cuts,” ACM Trans. Graphics,
	vol. 22, no. 3, pp. 277–286, 2003.
	
	Eden:2006
	A. Eden, M. Uyttendaele, and R. Szeliski, “Seamless image stitching of scenes
	with large motions and exposure differences,” in Proc. IEEE Conf.
		Comput. Vis. Pattern Recog., vol. 2, Jun. 2006, pp. 2498–2505.
	
	Brown:2007
	M. Brown and D. G. Lowe, “Automatic panoramic image stitching using invariant
	features,” Int. J. Comput. Vis., vol. 74, no. 1, pp. 59–73, 2007.
	
	lowe2004distinctive
	D. G. Lowe, “Distinctive image features from scale-invariant keypoints,”
	Int. J. Comput. Vis., vol. 60, no. 2, pp. 91–110, 2004.
	
	fischler1981random
	M. A. Fischler and R. C. Bolles, “Random sample consensus: a paradigm for
	model fitting with applications to image analysis and automated
	cartography,” Commun. ACM, vol. 24, no. 6, pp. 381–395, 1981.
	
	zaragoza2014projective
	J. Zaragoza, T.-J. Chin, Q.-H. Tran, M. S. Brown, and D. Suter,
	“As-projective-as-possible image stitching with moving DLT,” IEEE
		Trans. Pattern Anal. Mach. Intell., vol. 36, no. 7, pp. 1285–1298, 2014.
	
	kushnir2014epipolar
	M. Kushnir and I. Shimshoni, “Epipolar geometry estimation for urban scenes
	with repetitive structures,” IEEE Trans. Pattern Anal. Mach. Intell.,
	vol. 36, no. 12, pp. 2381–2395, 2014.
	
	lin2016repmatch
	W.-Y. Lin, S. Liu, N. Jiang, M. N. Do, P. Tan, and J. Lu, “RepMatch: Robust
	feature matching and pose for reconstructing modern cities,” in Proc.
		Eur. Conf. Comput. Vis., 2016, pp. 562–579.
	
	raguram2013usac
	R. Raguram, O. Chum, M. Pollefeys, J. Matas, and J.-M. Frahm, “USAC: a
	universal framework for random sample consensus,” IEEE Trans. Pattern
		Anal. Mach. Intell., vol. 35, no. 8, pp. 2022–2038, 2013.
	
	Tran2012
	Q.-H. Tran, T.-J. Chin, G. Carneiro, M. S. Brown, and D. Suter, “In defence of
	RANSAC for outlier rejection in deformable registration,” in Proc.
		Eur. Conf. Comput. Vis., 2012, pp. 274–287.
	
	yang2013feature
	Y. Yang, Z. Ma, A. G. Hauptmann, and N. Sebe, “Feature selection for
	multimedia analysis by sharing information among multiple tasks,” IEEE
		Transactions on Multimedia, vol. 15, no. 3, pp. 661–669, 2013.
	
	VideoPuzzle
	Q. Chen, M. Wang, Z. Huang, Y. Hua, Z. Song, and S. Yan, “VideoPuzzle:
	Descriptive one-shot video composition,” IEEE Transactions on
		Multimedia, vol. 15, no. 3, pp. 521–534, Apr. 2013.
	
	Xu2016
	Y. Yan, F. Nie, W. Li, C. Gao, Y. Yang, and D. Xu, “Image classification by
	cross-media active learning with privileged information,” IEEE
		Transactions on Multimedia, vol. 18, no. 12, pp. 2494–2502, Dec. 2016.
	
	action
	Y. Li, P. Li, D. Lei, Y. Shi, and L. Tan, “Investigating image stitching for
	action recognition,” Multimedia Tools and Applications, Aug. 2017.
	[Online]. Available: <https://doi.org/10.1007/s11042-017-5072-4>
	





