Smoothly Varying Affine Stitching
Wen-Yan Lin1
1

Siying Liu1

Institute for Infocomm Research

Yasuyuki Matsushita22

Tian-Tsong Ng1

Microsoft Research Asia

{wdlin, sliu, ttngg}@i2r.a-star.edu.sg

3

National University of Singapore

yasumat@microsoft.com

Abstract
Traditional image stitching using parametric transforms
such as homography, only produces perceptually correctcomposites for planar scenes or parallax free camera motion between source frames. This limits mosaicing to source
images taken from the same physical location. In this paper, we introduce a smoothly varying affine stitching field
which is flexible enough to handle parallax while retaining
the good extrapolation and occlusion handling propertiesof parametric transforms. Our algorithm which jointly estimates both the stitching field and correspondence, permits
the stitching of general motion source images, provided thescenes do not contain abrupt protrusions.

1. Introduction
Image stitching has long been of interest in graphics andvision. Its primary goal is the integration of multiple images
into a single seamless mosaic. This serves many purposes,
such as increasing the effective field of view, motion summarization and clean plate photography. Typically, stitchingrelies on an underlying transform which warps pixels fromone coordinate frame to another. As the transformationmust ensure perceptually accurate alignment of large (often quarter image width or greater) non-overlapping image
regions, it must be robust to large view point changes andbe able to generalize (interpolate and extrapolate) the motion over significant occlusion. To handle uncontrolled outdoor environments, the transform must also accommodate
illumination changes and independent motion. For robust
warping, mosaicing algorithms have traditionally sought toparameterize the warping field using a sparse set of global
transformation parameters, such as the 3×3 affine or homographic matrix. This sparse parametrization ensures robustness at the expense of flexibility and is only accurate
for a limited set of scenes and motions. For example, thecommonly used homographic transforms are only accurate
for planar scenes or parallax free camera motion between
source frames i.e. the photographer’s physical location must

Loong-Fah Cheong3

eleclf@nus.edu.sg

be fixed and only rotational motion is permitted.

(a) Input Images(b) Stitching result

Figure 1. A girl passing the time by playing chess with herself, an
example of our image stitching algorithm.

Dornaika et al. [8] highlighted that ideally, an image
stitching algorithm would allow for both general motion andscene structure. As affine and homographic stitching canbe considered a special case of a 3-D world’s re-projection,
a number of works [8, 21, 16] have proposed combining
image stitching with 3-D reconstruction to enable the handling of parallax in general motion source images. However, using pre-computed 3-D points has a number of drawbacks. Firstly, 3-D reconstruction is only defined on theoverlapping sections of the source image, making it difficult to integrate the non-overlapping regions, which is theprimary objective of image stitching. Secondly, as notedby Liu et al. [16], the 3-D reconstruction pipeline is brittle,
with its main components, accurate camera pose recovery
and outlier free matching, still being active research issues.
Thirdly, camera pose computation deteriorates if the motion
contains too strong a rotational element or if the overlapping
image regions are of inadequate size, both of which occur
frequently in image stitching.
To achieve flexibility, we look to the 2D non-rigid warping approaches such as thin plate spline [4, 23], as-rigidas-possible warping [13] and motion coherence [19]. Theyeschew the sparsity of parametric warping in favor of considering warping as a general matching problem with asmoothness constraint. This provides the flexibility needed
to handle most motion types but at the expense of motion
generalization over occluded regions. Hence, while warp-

ing algorithms may be used as a form of interpolation, they
are seldom directly employed to solve traditional two view
stitching problems. In this paper, we seek to adapt thewarping framework to take advantage of the fact that manyscenes can be modeled as having smoothly varying depth.
This permits a general stitching algorithm which does not
require an explicit 3-D reconstruction.
Our formulation is based upon the affine transform. A
global affine transformation defines a set of shear, rotation, scaling and translational parameters, which preserve
collinearity and the ratios of distances along a line. The
general shape preservation property of the affine transformmeans that even when image pairs are not strictly related bya global affine matrix, it can still capture the gist of the camera motion induced deformation, such as whether the scene
is translating upwards or side ways. Thus, provided motion
discontinuities are not too extreme, a global affine transformation can be considered a parametric warping [12] whichapproximates the motion field and is utilized in a number ofapplications as a first approximation [26, 11]. This suggeststhat we can relax the affine constraint while retaining muchof its strong motion generalization properties.
In this paper, we replace the global affine transformation with a smoothly varying affine stitching field which isdefined over the entire coordinate frame. Every point has
an associated affine parameter which is biased towards a
pre-computed global affine transform and smoothness is enforced on the deviation of each affine parameters from theglobal affine. This model has two major advantages. Firstly,
it is flexible enough to handle most kinds of motions, provided the scene contains no major protrusions Secondly,
affine parameters can generalize the motion of a image region. Hence, a region of rather un-smooth 2D motion flow(such as a strong sheer, or forward translation) can becomesmooth if described using an affine stitching field, since all
pixels in that region can be assigned a single, constant affine
parameter. This makes the affine stitching field very smoothand thus, easily extrapolated over the non-overlapping regions.
To robustly compute the desired affine stitching fieldover large displacements, illumination change and occlusion noise, we utilize local view invariant feature descriptors like SIFT [17]. Unfortunately, dense feature descriptors such as those used in SIFT flow [15], introduce a lot of
localization error as neighboring pixels are likely to sharesimilar feature descriptors, thus making accurate dense descriptor based matching difficult. Instead, we rely on asparse set of corner features (with associated SIFT descriptors) to compute the stitching field, which has an additional
advantage in terms of computation time. While one can extrapolate a stitching field from pre-computed point matches,
this is extremely vulnerable to outlier matches and a varying stitching field does not permit RANSAC based outlier

rejection. Instead, we observe that a good stitching field canhelp validate existing correspondence and determine additional ones. These correspondences can in turn refine thestitching field. We exploit the inter-connectedness of these
problems by jointly estimating both the matching and thestitching field. This prevents outlier matches, provides significantly more matches and yields a better stitching field.
To summarize our contribution:1) We introduce a flexible image stitching algorithm thatretains much of the motion generalization properties associated with global parametric transforms like affine/ homography. This permits the handling of general scenes and motions provided there are no abrupt protrusions. While ourresults do not always conform to the ground truth, it provides a good approximate which enables the creation of aperceptually correct composite.
2) We explore a range of applications made possible bythis flexibility. These include novel scene generation illustrated in fig 1, computation of point correspondence andmosaicing of panoramas from translational motion.

1.1. Related Works
Our stitching field is related to the affinely overparameterized optical flow algorithm of Tal et al. [20].
However, it is unclear how the framework of [20] can beadapted to the utilization of sparse high dimensional features and a bias towards a pre-defined affine. Instead, we
utilize the motion coherence framework of Yuille et al. [27]and Myronenko et al. [19] to fit the affine stitching field.
Our work is also related to the 3-D reconstruction
based image stitching methods mentioned in the introduction. These techniques have difficulty integrating the nonoverlapping image regions. While this is not important for
applications like Liu et al.’s [16] work on 3-D video stabilization, it is the central issue in forming large panoramas.
A simple solution is to utilize an additional image [8], sothat regions viewed by at least two images increase. However, this approach also increases the non-overlapping regions which cannot be mosaiced. An alternative is offeredby Qi et.al. [21], where the 3-D reconstruction is used togenerate virtual cameras from which strips are cut to ensure a smooth transition between the non-overlapping regions. This averages the error over the mosaic rather thanattempting to align the images and is unsatisfactory because
the error is incurred in the constrained overlapping region,
rather than the unconstrained non-overlapping region. The
lack of an underlying warping field also makes handling ofocclusions and illumination change difficult and limits thealgorithms applicability to other image editing task.
There are also works which seek to attain a perceptually
accurate large field of view image through inputs other thanconventional image stills. An interesting work is that ofKopf et al. [14] who generated virtual cameras from a seriesInput Images

Our stitching ﬁeld

Our warping

Naive stitching ﬁeld

Naive warping

Base Image

X-direction

Warped Base Image

X-direction

Warped Base Imageai(3), ai(6)ai(2), ai(5)Target Image

Y-direction

Overlay

Y-direction

Overlayai(1), ai(4)Visualization of stitchingﬁeld. The 6-D warpingﬁeld is separated into
two 3-D ﬁelds for X- andY- directions.

Figure 2. The affine stitching field transfers the base image to the target. The color coded deviation of each point’s affine parametersfrom the global affine is overlaid on the base image. Affine parameters are divided into 2 groups according to the axis they operate on.
Parameters in each group are assigned to one RGB color channel. The deviation from the global affine is proportional to color brightness.
We present both our method and a naive method where the stitching field is computed by averaging the affine parameters computed form
correspondences within a window. Observe that the naive method’s stitching field is strongly biased towards regions where there are many
correspondences. This makes it difficult to extrapolate the field to occluded regions such as the girl. Our algorithm can create a smooth
field (seen in the color transitions) over the right angled corner, and has better extrapolation ability.

of “bubbles” (360o panoramas), thus creating a long street
view. Carrol et al. [6] introduced a warping which enables
the un-distortion of a very wide angled image if the user
defines a number of straight lines. For video sequences,
Rav-Acha et al. [22] showed it is possible to leverage on
the trackability and redundancy present in closely spaced
video frames to incrementally stitch a large mosaic fromgeneral motion. However, it does not extend to the large
displacement two view stitching considered in this paper.
There are also a large number of works which seek
to refine conventional parametric image stitching. Interested readers can refer to the comprehensive tutorial by
Szeliski [24] for an overview of such image stitching andblending techniques.
Finally, the field of image stitching is also related tovarious large displacement matching works such as thoseby Bhat et al. [3] and Fraundorfer et al. [10] and Brox etal. [25]. However, the focus of these works is on matching,rather than interpolation and extrapolation and as such, are
not directly applicable to the image stitching domain.

2. Our Approach
A naive method of computing an affine stitching fieldwould be to compute local affine parameters from SIFT correspondences within a sliding window. These affine parameters could then be averaged to give a smooth, dense affine
stitching field with the parameters for non-overlapping regions obtained by extrapolation. This method produce a
good, smooth stitching field in regions where the point correspondence is fairly plentiful. However, the performance
declines significantly for regions where there are few/ no

FeatureMatching

Base

TargetStitching
Global affine

Smoothly varying affine

Stitched
OutputFigure 3. System overview. Point correspondence is used to obtaina global affine which our relaxes to form a smooth affine stitching
field. The images are warped together and their overlapping regions blended to form a composite.

point correspondences and the extrapolation is generally
poor. The reason is as follows. For any point (or small
patch), there are many possible affines that can approximate its motion. Pre-computing an affine from correspondence forces us to choose one of the possibilities. While thischoice may be locally optimal, it may not extrapolate wellover the rest of the scene. The result is an affine stitching
field that fits the regions of dense correspondence very well
but does not give due weight to the sparser correspondencesfrom the outlying regions. This problem is illustrated in fig
2, where even though we use a fairly large window (whichhelps avoid local over-fitting) with a length of a quarter image width, the affine stitching field computed still has difficulty extrapolating over regions with few correspondence.
In contrast, our problem is formulated as finding thesmoothest stitching field which can align the feature pointsof both images. This avoids a hard pre-assignment of theaffine parameters, while the choice of stitching field carries
within it an implicit extrapolation. An overview of our system is given in figure 3.
Our formulation’s primary constraint consist of two setsof unmatched SIFT feature points. We denote the M features from the first, base image as b0i , while the N features from the second, target image, are denoted as t0j .
The first two entries of the b0i , t0j vectors represent image coordinates, with the remaining entries containing SIFT
feature descriptors (This concatenation is done for notational simplicity and the necessary associated normalization is discussed in section 3). The stitching of the b0i ’s
to t0j ’s is defined using a continuous affine stitching fieldv(z2×1 ) : R2 → R6 , which represents the deviation from a
global affine aglobal . Mathematically, this is expressed as(∆ai )6×1 = v b0i(1) ; b0i(2) ,(1)where ∆ai is the deviation of feature i’s affine ai term fromthe global affine, given by ai = aglobal + ∆ai .
We use bi to represent the stitched feature points. bi
value depends only on the affine ai term associated withthe stitching field v(.) and their original position b0i . This
relationship can be expressed by the affine transformai(1)bi =  ai(4)
0S×2

ai(2)
ai(5)


02×S 
IS×S




ai(3)
b0i +  ai(6)  .
0S×1

(2)

To facilitate easy reference to these affine parameters, we
also define matrices
AM ×6 = [a1 , ..., aM ]T , ∆AM ×6 = [∆a1 , ..., ∆aM ]T .

We relate the base point set’s alignment to the target point
set, using the conditional probability based on a robust
gaussian mixture
P (t01:N |b1:M ) =

N
Y

M
X

j=1

i=1

!
g(t0j − bi , σt )!
+ 2κπσt2,

regularization term biases the affine stitching field towards
the global affine and ensures smooth transition between theconstrained stitching field in the overlapping regions and theextrapolated stitching field in the occluded regions. While
A is a discrete quantity and the stitching field v(.) is continuous, the regularization term can be re-expressed in terms of
A by choosing the smoothest stitching field which satisfies
eqn (1). This yields
Z|v 0 (ω)|2dω ,(5)Ψ(A) = min0v 0 (ω)R2 g (ω)
We combine the negative log of eqn (3) with the regularization term in eqn (5) and a λ weighting term, to form asingle cost function,
E(A) = −

log

j=1

M
X

!
g(t0j − bi , σt )!
+ 2κπσt2+ λΨ(A)i=1(6)which can then be minimized with respect to the variables
in A. Our minimization employs an EM style formulation,
successfully used in [19].

2.1. Minimization
We follow a minimization procedure which computes an
Ak+1 , using the M × 6 linear equations defined by Ak in
eqn (8). Compared to Ak , Ak+1 lowers the overall cost costdefined in eqn (6). The process is iterated until convergence.
We defineφij (bi , t0j ) = g(t0j − bi , σt ),φij (bi , t0j )2.
φl lj (bl , t0j ) + 2κπσtφij (A, t0j ) = P(7)Note that the second function’s argument is given as A because, as can be seen from eqn (2), the bi are base features
after being warped by A and are wholly dependent on theA.
Using Jensen’s inequality, we can write(3)

E(Ak+1 ) − E(Ak )

kzk2

− 2σ2

is a gaussian function and κ conwhere g(z, σ) = e
trols the strength of a uniform function which thickens thegaussian mixtures tails. κ is usually set to 0.5.
Apart from SIFT features, we also desire to incorporate
a number of soft constraints. As mentioned earlier, we assume that the stitching field is a relaxation of a single global
affine. Hence, we impose a smoothness constraint on thedeviation of each points affine parameters from the global
affine. We incorporate these soft constraints into a smoothZ
ing regularization term|v 0 (ω)|2
dω,
(4)
0
R2 g (ω)
where v 0 (ω) denotes the fourier transform of the continuous stitching field v(.) and g 0 (ω) represents the fouriertransform of a gaussian with spatial distribution γ. The

N
X

N X
M
X

φij (bk+1, t0j )
i
k
φ
(b
,
t
ij
0j )
i
j=1 i=1
+ λ Ψ(Ak+1 ) − Ψ(Ak )≤−φij (Ak , t0j )log=∆E(Ak+1 , Ak ).

From the above, we know ∆E(Ak , Ak ) = 0. Hence,an Ak+1 which minimizes ∆E(Ak+1 , Ak ) will ensureE(Ak+1 ) ≤ E(Ak ).
Dropping all the terms in ∆E(Ak+1 , Ak ) which are independent of Ak+1 , we obtain a simplified cost functionNM

t0j − bk+1
1 XXi
φij (Ak , t0j )Q=
2 j=1 i=1
σt2

2

+ λΨ(Ak+1 ).

Using a proof similar to that in Myronenko et al.[19], weshow in the appendix that the regularization term Ψ(A)has the simplified form Ψ(A) = tr(∆AT G−1 ∆A) where
G is a M × M matrix, whose elements are given by
G(i, j) = g(b0i(1:2) − b0j(1:2) , γ). Substitute this definition of Ψ(A) into Q, take partial differentiation of Q withrespect to Ak+1 and post multiply G throughout, we have


T
δQ
= c1 c2 . . . cM + 2λ ∆Ak+1 G−1
k+1
δA
T
= C + 2λ ∆Ak+1 G−1 = 06×M
T=>CG + 2λ ∆Ak+1 = 06×M ,(8)NX
φij (Ak , t0j )D(bk+1− t0j )V(b0i ).
ci =
i
2
σ
t
j=1
D(.), V(.) are simultaneous truncation and tiling operators.
They re-arrange only the first two entries of an input vectorz (where z must have a length greater or equal to 2) to form
the respective output matricesz(1) I3×3
03×3

03×3
z(2) I3×3



z(1)

1

D(z)6×6 =V(z)6×1 =

z(2)



z(1)

z(2)

1

T

From the definition of A in (2), we know that bk+1
cani
be expressed as a linear combination of the entries of Ak+1 .
Hence, eqn (8) produces M × 6 linear equations which canbe used to estimate Ak+1 . Ak+1 is used to estimate Ak+2
and the process is repeated until convergence.
After convergence, the continuous stitching field v(.) at
any point z2×1 can be obtained from A using a weighted
sum of gaussian given byT

WM ×6 = [w1 , ...wM ] = G+ ∆A,v(z2×1 ) =MXwi g(z −b0i(1)b0i(2)

T

, γ),

(9)

Input: Base image features bi , target image features
tj , global affine matrix aglobal
while σt above threshold do
while No convergence do
Use eqn (7) to evaluate φij (bki , t0j ) from Ak ;Use eqn (8) to determine Ak+1 fromφij (bki , t0j )endAnneal σt = ασt , where α < 1.
end
Output: Aconverged
Figure 4. Algorithm to compute stitching field.

smaller values of σt . Each step in this annealing processuses the previously calculated stitching field is as an initialization. We begin with σt = 1 and decrement it by afactor of 0.97, until σt = 0.1. The progressively smaller σtvalues increase the penalty for deviation between the target
and base point sets, forcing the stitching field to evolve until the base point coordinates register onto the target points,
resulting in a “match”.Using an i7 computer running matlab, the algorithm can typically compute the registration of1200 SIFT features in 8 minutes.
For notational simplicity, SIFT descriptors and point coordinates are condensed into a single vector. This implies
a need for normalization. The point coordinates for the target and base points are normalized to have zero mean, unit
variance, thus making the remaining parameter settings invariant to image size. We normalize the SIFT descriptors
to have magnitudes of 10σt , which gives good empirical results. The smoothing weight λ and outlier handling term
κ are assigned values of 10, 0.5 respectively. The γ term
which penalizes un-smooth flow, is set to 1. Finally, we
blend the images into a single mosaic, using the poisson
blending with optimal seam finding algorithm of [7].

i=1where G+ is the pseudo-inverse of G and the 6 × 1, wi
vectors can be considered weights for the gaussians. The
detailed proof is given in the appendix.

3. Implementation
We now discuss our system implementation. A process
overview is given in fig 3, with stitching field computation
algorithmized in fig 4. In the formulation section, we have a
global affine, aglobal acting as a regularization term. aglobal
is computed from SIFT correspondences using RANSAC[9] for outliers removal. As aglobal ’s regularization role lies
in ensuring a smoother stitching field, its precise value is
not important. All the ai vectors in A are initially set toaglobal . The affine stitching field is then computed by repeatedly minimizing the cost in eqn (6) with increasingly

4. Analysis
The computed smooth affine stitching field is a “sparse”
representation of the true warping function and errors will
be incurred by smoothing over depth boundaries and generalization from a small set of feature points. In figure 5, we
use two simulated scenes. The first is a simple “V” scene,
while the second contains significant depth discontinuities.
The scenes are projected onto 500 × 500 pixel images. Our
computed warping has an avergae error of 1.92, 4.57 pixels. This is small, considering we generalized the motion of
0.25 megapixels using 625 feature points, a ratio of 1 : 400.
In fig 6, we provide a qualitative error analysis. The
stitched images are overlayed. In the overlapping region,
the green color channel is from the base image while thered and blue channels come from the target image. This

allows a visualization of alignment errors. While our algorithm incurs some errors along depth boundaries, they canbe removed by blending.
Base Model

Target Modeldiffers from a “cut and paste” method of overlaying an object onto a background image. In “cut and paste”, the overlay must be a discrete object such as a man or a car, with noattached background. As our stitching algorithm automatically warps the appended region to fit smoothly with thetarget image, “re-shooting” allows the overlay of an entire
region, including the complex background and the subjects’interactions with it.
Image Integration

Mean flow: 26.9 pixels

Mean error: 1.92 pixels
(a)

(b)

Mean flow: 70.87 pixels Mean error: 4.57 pixels
Figure 5. Quantitative analysis of our algorithm’s motion generalization ability. The camera rotates 0.3 radians about the object.
Using 625 uniformly distributed, unique features, we generalize
the motion of a 500 × 500 image (0.25 megapixels), a 1:400 ratio.
Input Images

SummerAutumn

Past (1920)

Present(c)

After Blending

OverlayOurs(d)Homography

Figure 6. Results before and after poisson blending. For the preblended images, the overlapping regions take the green color channel from the base image and the red, blue channels from the target
image. This enables visualization of alignment errors. Our algorithm incurs some errors along the depth boundaries. However,after blending, the results are perceptually accurate. The homographic mosaicing, incurs much larger errors and even after applying the same blending, clear artifacts remain.

5. Applications
Our algorithm’s flexibility means that it can stitch images even when the photographer does not maintain a fixed
position. This opens up a range of different possibilities.

5.1. Re-shootBae et al.[2], noted that if the photographer has moved
away from the original location, it is difficult to recover
the exact view point. Our algorithm’s good motion generalization and flexible stitching capability mean we can“re-shoot” a scene to incorporate information from different
time instances. Observe that image editing using “re-shoot”

Figure 7. “Re-shoot” permits the integration of image pairs to create novel composites where the subject is interacting with the environment. This is not possible using conventional ”cut and paste”
image fusing methodology. (a) A girl passing the time by playing
chess with herself. (b) Two people alternating as photographers
to obtain a group photo. (c) The changing seasons at the famous
Kiyomizu temple in Japan. (d) The passage of time at the Archbishop’s palace in Prague.

In the first two scenes of fig 7, we insert a person into
an image where he/she was not originally present and conversely, remove a person from the image. This allows interesting compositions such as a girl playing chess with herself in a cafe and permits two people to alternate as photographers to obtain a group photo. The following two
scenes of fig 7 test our algorithm’s limit by using internet
images. These are much more challenging because photometric changes affect the SIFT feature invariance our al-gorithm depends on. However, it permits more dramaticeffects such as integration of summer time vista with thespectacular autumn foliage at Kiyomizu temple in Japan, as
well as an image of a young couple walking from Prague’s
present into its past. We believe that our algorithm can beadapted to permit changes in the SIFT feature which would
significantly improve its performance on internet images.
Technical discussion: “Re-shoot” is more challenging
than panorama formation as the available blending region isnarrow and the amount of occlusion typically very large. To
ensure image consistency, we normalize the image colors.
Poisson blending with optimal cut is employed [7] and followed by an additional alpha blending to merge the colors.
It is carried out on a 25 pixel wide boundary along a user
defined transfer region. For the shots using internet images,
the blending boundary is set to be 50 pixels wide to accommodate the photometric variations and color normalization
is discarded. In the Prague scene, the global affine was not
pre-computed (due to a shortage of reliable matches) but
set to an identity matrix. A more sophisticated blending for“re-shoot” can by obtained from [1].

(a)

Input
ImagesOurs(b)AutoStitch(c)

Close-up View(d)5.2. Panoramic stitching
Our algorithm can be used for panorama creation. Itsability to handle general motion allows image stitchingfrom un-conventional sequences, such as a series of images
taken from different windows of a high-rise flat. As most
windows are set back from the facade, this is not possible
with homographic mosaicing [5] which requires a large unoccluded rotational field of view from a single window. Results are shown in fig 8. Observe that many of the views
have only limited overlap, making camera pose recovery
and hence mosaicing via 3-D reconstruction difficult.

(a)
Input Images
Ours

(b)
Ground-truth

AutoStitch

5.3. Matching
Our algorithm can serve as a matcher across two views
that can be related by a smoothly varying affine field (it will
not match independent motion). As it matches features asa set, rather than individually, there is reduced dependency
on feature descriptor uniqueness. In fig 9 we show that applying our algorithm with traditional SIFT descriptors [17],we can obtain 40% more matches. This is more than using
a nearest neighbor matcher with more sophisticated A-SIFT[18] descriptors.

6. Conclusion
We present an image stitching algorithm based on asmoothly varying affine field. It is significantly more tolerant to parallax than traditional homographic stitching but
retains much of homographies ability to generalize motion
over occlusion. Its flexibility enables integration of views
taken from different physical locations, permitting a number of interesting applications like panorama creation from(c)Figure 8. Results of panoramic stitching. Input images in (a) aretaken from a series of windows. Our mosaic in (b) is perceptually
accurate while homographic mosaicing using AutoStitch [5] in (c)has difficulty merging the fore-ground buildings.

a translating camera or integration of images taken at different times. It can also accommodate other heuristics such as
requiring straight lines to warp to straight lines, which may
be considered in future work. Our algorithm’s primary limitation is the violation of affine coherence at depth boundaries. While our results show these errors are often smallenough to be blended over, explicit detection and handlingwould be better. In this regard, our results provide an excellent starting point for further refinement.

45
676
1108

276
489

1107
881
482
11

672
671
670

56

480
474 866
867
272
27
1093
864
863
472
1090
1089 42666
140271187
478
664
479
1082
470
270
41 850
40
646
135
1075
640
139
138
3501073 639
1071
348
642 1072
841
631
346
845
91
267
266
183
637
844
1070 349
1069
834
89 458
186
132
137
136
840
134
351
55
54
833
1053
61
462
819
133
90
617
4
456
1061
53
52
105451264
22 1055
624
84
453
452
625
61687 1050
176
623
454 615
1029
1044
262
448
21 609
793
339
338
801
177
258
79 426334 440
1027
323
790
432
1007
325 586
587
56

666
664
479

478

48

27

474
272
867
864
863
1090
108
187
271
1082
470
850
138
139
646
1075
642
845
351
844
350 1073 6
137 840637
136
62
1072
10702671069
841 1071
349 91
134
55
54
633
346
53
52
834
833
90
2
133
132 1
264
1061
5
8
456
624
1055
1054 5123
22
54 615617
1053
616 87 1050
819
453
452
262
1044
21
448
609
1093
472

140

41
40

4

339
258338
177
440
1027

176
102
801

432
790
325
1007

No. of matches: Ours 360 A-SIFT 257 SIFT 215
87
60
61

1195
1194
1196
369
368
874
1190
367
500
1186
1185
251
1184
362
668
870
869
499
1182
1181
1178
1177
667
64 358 35763
859
857
1164
1163 1162
853852850662
496493
495
494
124
123
492 849
491
248
1157
489
6601156121
1151
4884861145
487
1148
1147
351
350
1146
831
830
655
654
827
826
8485
829
28
1141
1140
1130

1110
458
457
615
451
611
798
604
446
81 229
55
779
1059
1060

79

793
426
32

587
586

848

1136
1135
645
642
475
44
470
340
813
112688468
336 1121
1115172625
1113
3341111
456
616
1104
1101
1097
610
801
328
608
606
1078 54
1074
786
22
10
1

1034

85763
1164
1163 1162
853852850662
496493
495
494
124
123
492 849
491
248
1157
489
6601156
121
1151
488
487
1148
1147
351
350
1146
1145
486
831
830
655
654
827829
826
8
28
485
1141
1140
1130

1110
458
457
615
451
611

No. of matches: Ours 386 A-SIFT 318 SIFT 270

604
446
798
55 229
81
1059
779
1060

848

1135
1136
64
470
642
475
813
340
4
1126 88
468
336
1121
1115
625
1113
172
334
1111
616
456
1097
1104
801610 1101
328608
606
1078

1034

Figure 9. We show the results obtained by using our algorithm
as a matcher, compared against conventional nearest neighbor
SIFT [17] and A-SIFT [18] feature matching. Although we use
traditional SIFT [17] descriptors, we can obtain more matches
than applying nearest neighbor matching to the more sophisticated
A-SIFT descriptor. The above figures show that the additional
matches do not come at the expense of accuracy and the matching is stable to significant occlusion.

Acknowledgement This work is partially supported byproject grant NRF2007IDM-IDM002-069 on Life Spaces fromIDM Project Office, Media Development Authority of Singapore

References[1] A. Agarwala, M. Dontcheva, M. Agrawal, S. Drucker,
A. Colburn, B. Curless, D. Salesin, and M. Cohen. Interactive digital photomontage. ACM Trans. Graph., 2004.
[2] S. Bae, A. Agarwala, and F. Durand. Computational rephotography. ACM Trans. Graph., 29(3):1–15, 2010.
[3] P. Bhat, K. C. Zheng, N. Snavely, and A. Agarwala. Piecewise image registeration in the presence of multiple large
motions. CVPR, 2006.
[4] F. L. Bookstein. Principal warps: Thin-plate splines andthe decomposition of deformations. PAMI, 11(6):567–585,
1989.
[5] M. Brown and D. Lowe. Automatic panoramic image stitching using invariant features. IJCV, 1(74):59–73, 2007.

[6] R. Carroll, M. Agrawala, and A. Agarwala. Optimizing
content-preserving projections for wide-angle images. ACM
Trans. Graph., 2009.
[7] L. H. Chan. and A. A. Efros. Automatic generation of an
infinite panorama. Technical Report, 2007.
[8] F. Dornaika and R. Chung. Mosaicking images with parallax.
Signal Processing: Image Communication, 2004.
[9] M. A. Fischler and R. C. Bolles. Random sample consensus: A paradigm for model fitting with applications to image
analysis and automated cartography. Comm. of the ACM,
24:381–395, 1981.
[10] F. Fraundorfer, K. Schindles, and H. Bischof. Piecewise planar scene reconstruction from sparse correspondance. Imageand Vision Computing, 24(4), 2006.
[11] G. L. Gimel’farb and J. Q. Zhang. Initial matching ofmultiple-view images by affine approximation of relative distortions. Proc of International Workshops on Advances in
Pattern Recognition, 2000.
[12] C. Glasbey and K. Mardia. A review of image warping methods. In Journal of Applied Statistics, 1998.
[13] T. Igarashi, T. Moscovich, and J. F. Hughes. As-rigid-aspossible shape manipulation. ACM Trans. Graph., 24:1134–
1141, July 2005.
[14] J. Kopf, B. Chen, R. Szeliski, and M. Cohen. Street slide:
Browsing street level imagery. ACM Trans. Graph., 2010.
[15] C. Liu, J. Yue, A. Torralba, J. Sivic, and W. T. Freeman. Siftflow: Dense correspondence across different scenes. ECCV,
2008.
[16] F. Liu, M. Gleicher, H. Jin, and A. Agarwala. Contentpreserving warps for 3d video stabilization. ACM Trans.
Graph., 2009.
[17] D. G. Lowe. Distinctive image features from scale-invariant
keypoints. IJCV, 60(2):91–110, 2004.
[18] J. Morel and G. Yu. Asift: A new framework for fully affine
invariant image comparison. SIAM Journal on Imaging Sciences, 2(2):438–469, 2009.
[19] A. Myronenko, X. Song, and M. Carreira-Perpinan. Nonrigid point set registration: Coherent point drift. NIPS, 2007.
[20] T. Nir, A. M. Bruckstein, and R. Kimmel.
Overparameterized variational optical flow. IJCV, 2007.
[21] Z. Qi and J. Cooperstock. Overcoming parallax and sampling
density issues in image mosaicing of non-planar scenes.
BMVC, 2007.
[22] A. Rav-Acha, P. Kohli, C. Rother, and A. Fitzgibbon. Unwrap mosaics: a new representation for video editing. ACM
Trans. Graph., 27(3):1–11, 2008.
[23] R. Sprengel, K. Rohr, and H. S. Stiehl. Thin-plate spline approximation for image registration. In Proc. of Engineeringin Medicine and Biology Society, 1996.
[24] R. Szeliski. Image alignment and stitching a tutorial. 2005.
[25] T.Brox and J.Malik. Large displacement optical flow: Descriptor matching in variational motion estimation. PAMI,
2010.
[26] K. Uno and H. Miiket. A stereo vision through creating avirtual image using affine transformation. MVA, 1996.
[27] A. L. Yuille and N. M. Grywacz. The motion coherence theory. ICCV, 1988.

7. Appendix A: Affine CoherenceThis appendix deals with how the smoothness function can be simplified into a more computationally tractable form.
At the minima, the derivative of the energy term in (6) withto the stitching field v 0 (.), must be zero. Hence,
R respect02πι<µi ,ω>utilizing the fourier transform relation, (∆ai )6×1 = v(µi ) = R2 v (ω)edω, where µi = [ b0i(1) b0i(2) ]T , weobtain the constraint
δE(v 0 )= 06×1 , ∀z ∈ R2
δv 0 (z)ZM Xδv 0 (ω) 2πι<µi ,ω>g(t0j − bi , σt )
dω
diag
(D(b
−
t
)V(b
))
e
i
0j
0i
Z
0
N
σt2
X
R2 δv (z)
δ |v 0 (ω)|2
i=1
=> −
+
λ
dω = 06×1
00M
X
R2 δv (z) g (ω)
j=1
2
g(t0j − bi , σt ) + 2κπσt
i=1
M 
X

=> −

N
X
j=1

i=1

g(t0j − bi , σt )
σt2
M
X



diag (D(bi − t0j )V(b0i )) e2πι<µi ,z>+ 2λg(t0j − bi , σt ) + 2κπσt2

v 0 (−z)= 06×1g 0 (z)i=1(10)D(.), V(.) are simultaneous truncation and tiling operators. They re-arrange only the first two entries of an input vector z(where z must have a length greater or equal to 2) to respectively form the 6 × 6 and 6 × 1 output matricesz(1) I3×3
03×3
03×3 z(2) I3×3
V(z)6×1 = z(1) z(2) 1 z(1)

D(z)6×6 =

z(2)

1

T

diag(.) is a diagonalization operator which converts a k dimensional vector z into a diagonal matrix, such that


z(1)
 0

diag(zk×1 ) =  .
 ..
0

z(2)
..
.

···
···
..
.

0
0
..
.

0

···

z(k)

0







.

k×k

Simplifying eqn (10), we obtain
−2λ

M
X

wi e2πι<µi ,z> + 2λi=1v 0 (−z)=0g 0 (z)where the six dimensional vectors wi act as placeholders for the more complicated terms in (10).
Substituting z with −z into the preceding equation and making some minor rearrangements, we havev 0 (z) = g 0 (−z)

MXwi e−2πι<µi ,z> .

i=1

where the six dimensional vectors, wi , can be considered as weights which parameterize the stitching field.
Using the inverse Fourier transform relation
Z
wiT wj g 0 (z)e+2πι<µj −µi ,z> dz = wiT wj g(µj − µi , γ),
R2

(11)

and eqn (11), we can rewrite the regularization term of eqn (6) asZ(v 0 (z))T (v 0 (z))∗Ψ(A) =dz
g 0 (z)R2
PM PM
Z
g 0 (z)2 i=1 j=1 wiT wj e+2πι<µj −µi ,z>dz=
g 0 (z)
R2
M X
M Z
X
=
wiT wj g 0 (z)e+2πι<µj −µi ,z> dz
i=1 j=1

(12)

R2

T

= tr(W GW),
where
WM ×6 = [w1 , ..., wM ]T ,G(i, j) = g(µi − µj , γ).
Taking the inverse Fourier transform of eqn (11), we obtainv(z) = g(z, γ) ∗MXwi δ(z − µi ) =

i=1

M
X

wi g(z − µi , γ).

(13)

i=1

As ∆aj = v(µj ),∆A = GW.

(14)

Substituting eqn (14) into (12), we see that the regularization term Ψ(A), has the simplified form used in the main bodyΨ(A) = tr(WT GW) = tr(∆AT G−1 ∆A).

(15)

It can also be seen from eqn (14) that the stitching field v(.) can be defined in terms of A. This is done by using thematrices ∆A, G to define define the weighting matrix W via,
W = G+ ∆A.
This allows the definition of the stitching field at any point z2×1 using equation (13).

(16)

8. Appendix B: Additional Results
8.1. Panorama Creation
It is possible to stitch together fairly large panoramas using our algorithm. In figure 10, we show an extended version of
the panorama used in the main body.

Figure 10. Long panoramic view

8.2. Protrusion Handling
While strong depth deviation is our algorithm’s weak point, it is often possible for the post-blending results to be visuallypleasing. This is illustrated in figure 11, where the tree is quite far in front than the store.

8.3. Re-Shoot“Re-shoot” is quite stable to changes in the environment. In figure 12, we integrate images taken a few months apart,both before and after the workspace was occupied. Observe that there have been many modifications to the equipment in theroom after it was occupied by a new worker. To re-assure the readers that the introductory image does not consist of a purerotation, we also include the result of stitching the images using auto-stitch in fig 13.

9. Comparison with other warping techniques
Finally, we compare our results with some of those obtained using other warping techniques. In figure 14, we compare
our affine based relaxation of a global affine, to a motion coherence based relaxation. Observe that our approach gives
better extrapolation ability. In figure 15, we compare against SIFT flow [15] and large displacement optical flow [25], tworecently developed dense matching techniques. These algorithms are not designed for image stitching and do not give good
extrapolation.

Figure 11. While we incur clear errors, the mixture of our warping and a blending algorithm could still recover a somewhat pleasing mosiac
from an image pair where the frontal tree represents a major protrusion.

Figure 12. Combing images taken a few months apart, before and after a office worker occupied his work station.

Figure 13. Auto-stitch result on the introductory image.

Figure 14. Left: Relaxing a global affine using normal coherence. Right: Our affine coherence relaxation.

Warped image 2

SIFT flow [15]Large displacement flow [25]

Our Sparse SIFT warping

Figure 15. Computing the warping using dense SIFT features in the SIFT flow algorithm of [15], large displacement optical flow [25] andour algorithm. Our results are perceptually more pleasing and easier to mosaic. Our warping also extrapolates the motion for occluded
regions. These results are for the image pair shown in figure 1