IEEE TRANSACTION ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

1

Multiview Rectification of Folded Documents
Shaodi You, Member, IEEE, Yasuyuki Matsushita, Member, IEEE, Sudipta Sinha, Member, IEEE
Yusuke Bou, Member, IEEE, Katsushi Ikeuchi, Fellow, IEEE,
Abstract—Digitally unwrapping images of paper sheets is crucial for accurate document scanning and text recognition. This
paper presents a method for automatically rectifying curved or folded paper sheets from a few images captured from multiple
viewpoints. Prior methods either need expensive 3D scanners or model deformable surfaces using over-simplified parametricrepresentations. In contrast, our method uses regular images and is based on general developable surface models that canrepresent a wide variety of paper deformations. Our main contribution is a new robust rectification method based on ridge-aware
3D reconstruction of a paper sheet and unwrapping the reconstructed surface using properties of developable surfaces via `1
conformal mapping. We present results on several examples including book pages, folded letters and shopping receipts.
Index Terms—Robust digitally unwarpping, ridge-aware surface reconstruction, mobile phone friendly algorithms

F

1

I NTRODUCTION

Digitally scanning paper documents for sharing andediting is becoming a common daily task. Such paper sheets are often curved or folded, and proper
rectification is important for high-fidelity digitizationand text recognition. Flatbed scanners allow physicalrectification of such documents but are not suitablefor hardcover books. For a wider applicability of
document scanning, it is wanted a flexible techniquefor digitally rectifying folded documents.
There are two major challenges in document image
rectification. First, for a proper rectification, the 3D
shape of curved and folded paper sheets must be
estimated. Second, the estimated surface must be flattened without introducing distortions. Prior methods
for 3D reconstruction of curved paper sheets either
use specialized hardware [1], [2], [3] or assume simplified parametric shapes [4], [5], [6], [7], [8], [9], [2],such as generalized cylinders (Fig. 2a). However, thesemethods are difficult to use due to bulky hardware or
make restrictive assumptions about the deformationsof the paper sheet.
In this paper, we present a convenient method for
digitally rectifying heavily curved and folded paper
sheets from a few uncalibrated images captured witha hand-held camera from multiple viewpoint. Our
method uses structure from motion (SfM) to recoveran initial sparse 3D point cloud from the uncalibrated
images. To accurately recover the dense 3D shapeof paper sheet without losing high-frequency struc• S. You is with Data61-CSIRO, Australia; and Australian National
University, Australia. E-mail: youshaodi@gmail.com• Y. Matsushita is with Osaka University, Japan.
E-mail: yasumat@ist.osaka-u.ac.jp• S. Sinha is with Microsoft Research Redmond, USA.
E-mail: sudipta.sinha@microsoft.com• Y. Bou is with Microsoft, Japan. E-mail: yusuketa@microsoft.com• K. Ikeuchi is with Microsoft Research Asia, China.
E-mail: katsushi.ikeuchi@outlook.jp

tures such as folds and creases, we develop a ridgeaware surface reconstruction method. Furthermore, toachieve robustness to outliers present in the sparse
SfM 3D point cloud caused by repetitive document
textures, we pose the surface reconstruction task as
a robust Poisson surface reconstruction based on `1
optimization. Next, to unwrap the reconstructed surface, we propose a robust conformal mapping methodby incorporating ridge-awareness priors and `1 optimization technique. See Fig. 1 for an overview.
The contributions of our work are threefold. First,
we show how ridge-aware regularization can be used
for both 3D surface reconstruction and flattening (conformal mapping) to improve accuracy. Our ridgeaware reconstruction method preserves the sharp
structure of folds and creases. Ridge-awareness priors act as non-local regularizers that reduce global
distortions during the surface flattening step. Second,
we extend the Poisson surface reconstruction [10]and least-squares conformal mapping (LSCM) [11]algorithms by explicitly dealing with outliers using `1
optimization. Finally, we describe a practical system
for rectifying curved and folded documents that canbe used with ordinary digital cameras.

2

R ELATED W ORK

The topic of digital rectification of curved and folded
documents has been actively studied in both the computer vision and document processing communities.
It is common to model paper sheets as developablesurfaces which have underlying rulers corresponding
to lines with zero Gaussian curvature. Many existing methods assume generalized cylindrical surfaces
where the paper is curved only in one direction
and thus can be parameterized using a 1D smoothfunction. Such surfaces do not require an explicit
parameterization of the rulers. See Fig. 2a for an
example. A variety of existing techniques recover

IEEE TRANSACTION ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

2

Dewarp(a) Multi-view images(b) Structure from motion(c) Ridge-aware reconstruction(d) Robust unwrapping(e) Dewarp

Fig. 1. Our technique recovers a ridge-aware 3D reconstruction of the document surface from a sparse 3D point cloud. The
final rectified image is then obtained via robust conformal mapping.

(a) Generalized
cylindrical surface(b) Cylinder-likedevelopable surface(c) Generaldevelopable surface

Fig. 2.

Developable surfaces with underlying rulers (lines
with zero Gaussian curvature) and fold lines (ridges) shownas dotted and solids lines respectively. Examples of (a)smooth parallel rulers, (b) smooth rulers not parallel to eachother and (c) rulers and ridges in arbitrary directions.

surface geometry using this assumption. Shape fromshading methods were first used by Wada et al. [4],Tan et al. [12], [13], Courteille et al. [14] and Zhang etal. [5] whereas shape from boundary methods were
explored by Tsoi et al. [15], [6]. Binocular stereo matching with calibrated cameras was used by Yamashita etal. [16], Koo et al. [7] and Tsoi et al. [6]. Shape from textlines is another popular method for reconstructing
the document surface geometry [17], [12], [18], [19],[20], [21], [8], [22], [9], [23], [24], [25]. However, thesemethods assume that the document contains wellformatted printed characters.
Some recent methods relax the parallel ruler assumption (see Fig. 2b). However, the numerous parameters in these models makes the optimization
quite challenging. Liang et al. [26] and Tian et al. [27]use text lines. Although these methods can handle asingle input image, the strong assumptions on surface
geometry, contents and illumination limit the applicability. Meng et al.designed a special calibrated active
structural light device to retrieve the two parallel
1D curvatures [2], the surface can be parameterized
by assuming appropriate boundary conditions andconstraints on ruler orientations. Perriollat et al.[28]use sparse SfM points but assume they are reasonably
dense and well distributed. Their parameterization issensitive to noise and can be unreliable when the 3d
point cloud is sparse or has varying density.
For rectification of documents with arbitrary distortion and content (Fig. 2c), other methods require specialized devices and use non-parametric approaches.

Brown et al. [3] use a calibrated mirror system toobtain 3D geometry using multi-view stereo. They
unwrap the reconstructed surface using constraints
on elastic energy, gravity and collision. The model is
not ideal for paper documents because developablesurfaces are not elastic. Later, they propose using
dense 3D range data [29] after which they flatten thesurface using least square conformal mapping [11].
Zhang et al. [30] also use dense range scans and use
rigid constraints instead of elastic constraints withthe method proposed in [3]. Pilu [1] assumes thata dense 3D mesh is available and minimizes theglobal bending potential energy to flatten the surface.
None of these existing methods are as practical andconvenient as our method that only requires a handheld camera and a few images.

3 P ROPOSED M ETHOD
Our method has two main steps – 3D document
surface reconstruction and unwrapping of the reconstructed surface. For now, we assume that a set ofsparse 3D points on the surface are available. Next, we
describe our new algorithms for ridge-aware surface
reconstruction and robust surface unwrapping.
3.1 Ridge-aware surface reconstructionDense methods are favored for 3D scanning of foldedand curved documents [31], [32]. This is because existing methods for surface reconstruction from sparse 3D
points tend to produce excessive smoothing and failto preserve sharp creases and folds, i.e., ridges on thesurface. Such methods are typically also inadequate
for dealing with noisy 3D points caused by repetitive textures present in documents. We address theseissues by developing a robust ridge-aware surface
reconstruction method for sparse 3D points. Specifically, we extend the Poisson surface reconstruction
method [10] by incorporating ridge constraints andby adding robustness to outliers.
Robust Poisson surface reconstruction. We denotea set of N sparse 3D points obtained from SfM
as {x̂n , ŷn , ẑn }, n = 1, 2, · · · , N , where only 3D points
triangulated from at least three images are retained.
For our input images, N typically lies between 700 to
2000. For a selected reference image (and viewpoint),
we use a depth map parameterization z(x, y) for the
document surface. We aim to estimate depth at the

IEEE TRANSACTION ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

3

While this problem (Eq. (6)) does not have aclosed form solution, we use a variant of iteratively
reweighted least squares (IRLS) [34] for deriving thesolution. By rewriting the data terms in Eq. (6) as aweighted `2 norm using a diagonal matrix W withpositive values on the diagonal, we have>z∗=argmin (ẑ − PΩ z) W> W (ẑ − PΩ z) + λz> D> Dz. (7)(a) Inputz(b) Robust Poisson reconstruction

In contrast to Equation (6), the data term now uses
`2 norm instead of `1 norm. We solve this problem(Equation (7)) using alternation as described next.

(c) Ridge candidates(d) Ridge-aware reconstruction

Fig. 3. Example of ridge-aware 3D surface reconstruction.
mesh grid vertices zi (xi , yi ), where i is the meshgrid index, 1 ≤ i ≤ I. Our method computes the>
optimal depth values z∗ = [z1 , . . . , zI ] by solving thefollowing optimization problem.
z∗ = argmin Ed (z) + λEs (z).
(1)
zHere, Ed and Es are the data and smoothness terms
respectively and λ is a parameter to balance thetwo terms. The original Poisson surface reconstruction
method uses the squared `2 -norm for both terms.
Instead, we propose using the `1 -norm for the data
term Ed to deal with outliers.
X
Ed (z) =kẑn − zi k1 .
(2)nThis encourages the estimated depth zi to be consistent with zˆn , the observed depth of the nearest 3D
point.
We rewrite Eq. (2) in vector form.
Ed (z) = kẑ − PΩ zk1 ,(3)
where PΩ is a permutation matrix that selects andaligns observed entries Ω by ensuring correspondence
between ẑn and zi . The smoothness term Es is definedusing the squared Frobenius norm of the gradient of
depth vector z along x and y in camera coordinates.
 2
 2∂ z ∂2z
Es (z) = k∇2 zk2F =,.
(4)∂x2 ∂y 2 F
By preparing a sparse derivative matrix D that
replaces the Laplace operator ∇2 in a linear form,




2

 di,j = −1

0


D=


2
d
=
i+I,j

−1

0

if i = jif zj is left/right to zi otherwise
if i = jzj is above/below zi
otherwise





,

(5)

2I×I

we have a special form of the Lasso problem [33].
z∗ = argmin kẑ − PΩ zk1 + λkDzk22 .
(6)z

Step 1: Update z∗
2
Eq. (7) can be as z = argminz k Az − b k2 ,
 rewritten
WPΩWẑand b =
and 02I×1 iswhere A = √02I×1
λD
a zero vector of length 2I. This is a squared `2 sparselinear system. It has the closed form solutionz∗ = [A> A + αI]−1 A> b,(8)

where I is the identity matrix, α is a regularization
parameter (we use α = 1.0e-8).
Step 2: Update W
We initialize W to the identity matrix. During each
iteration, each diagonal element wi of W is updated
given the residual r = WPΩ z∗ − Wb, as follows.
1
,
(9)
wi =
|ri | + 
Here, ri is the i-th element of r and  is a small positive
value (we use  = 1.0e-8). These steps are repeateduntil convergence; namely, until the estimate at t-th
iteration z∗(t) becomes similar to the previous estimatez∗(t−1) , i.e., kz∗(t) −z∗(t−1) k2 < 1.0e-8. Figure 3.b shows
an example of the reconstructed mesh.
Ridge-aware reconstruction. Developable surfaces
are ruled [35], i.e., contain straight lines on the surface
as shown in Fig. 2. Our method exploits this geometricproperty as described in this section. Unlike existing
parameterization-based methods which only handlesmooth rulers, [26], [27], [2], [28], extracting arbitrarycreases and ridges is more difficult when only sparse
3D points are available. In particular, the sparse SfM
points can be quite noisy. We propose a sequential
approach by first detecting ridges on the mesh z∗
that was obtained using our robust Poisson reconstruction method. After selecting the ridge candidates,
we instantiate additional linear ridge constraints andincorporate them into the linear system that was
solved earlier. This sequential approach is quite general and avoids overfitting. It also avoids spurious
ridge candidates arising due to noise.
For each point z(x, y) on the mesh z∗ , we computethe Hessian K as follows.
#" 22
K(z) =

∂ z
∂x2
∂2z
∂x∂y

∂ z
∂x∂y
∂2z
∂y 2

.

(10)

IEEE TRANSACTION ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

Based on the following Eigen decomposition of K(z),


κ1 0
>
K(z) = [p1 , p2 ][p1 , p2 ] ,
(11)
0 κ2
we obtain principal curvatures κ1 and κ2 (|κ1 | ≤ |κ2 |)and the corresponding eigenvectors p1 and p2 .
The value of κ1 is equal to zero at all points on adevelopable surface. Thus, at any point zi , a straightline along direction p1 must lie on the surface. As
discussed earlier and shown in Fig. 2, the curvature
along the ridge is zero while the curvature orthogonal
to the ridge reaches a local extremum. We use thisobservation to select ridge candidates using the valueof |κ2 |. Mesh points zi (xi , yi ) with |κ2 (i)| greater than
the threshold κth are selected as ridge candidates. (seeFigure 3c for an example). The associated smoothness
constraints in Eq. (4) are adjusted as follows.
d˜i,j = ϕ(hp1 , e1 i)di,j(12)
d˜i+I,j = ϕ(hp1 , e2 i)di+1,j ,where h , i is the inner product and e1 = [1, 0]> , e2 =[0, 1]> are orthonormal bases. ϕ(·) is a convex monox2−1, which places
tonic function defined as ϕ(x) = ββ−1
a greater weight β  1 along the ridge and smaller
weight orthogonal to it. We also consider two more
directional smoothness constraints similar to thosestated √in √Eq. (12), for thetwo√ diagonal directions
√
2
2 >
2
e3 = [ 2 , 2 ] and e4 = [ 2 , − 22 ]> .
Finally, we modify Es (z) defined in Eq. (4) byadding these ridge constraints and solve a new sparselinear system (similar to the earlier one) to obtain the
final reconstruction. Figure 3d shows that this method
can preserve accurate folds and creases.

3.2

Surface Unwrapping

Given the 3D surface reconstruction, our next stepis to unwrap the surface. We take a conformal mapping approach to this problem, amongst which, Least
Squares Conformal Mapping (LSCM) [11], [29] is asuitable choice. However, it is not resilient to the presence of outliers and susceptible to global distortion
which can occur due to the absence of long-range
constraints. We address both these issues and extend
LSCM by incorporating an appropriate robustifier aswell as ridge constraints to reduce global drift.
Conformal Mapping. For our mesh topology, each 3D
point zi (xi , yi ), i = 1, . . . , I, on the grid on z forms
two triangles, one with its upper and left neighbor,the other with its lower and right neighbor on thegrid. The triangulated 3D mesh is denoted as {T , z}.
A conformal map will produce an associated 2D
mesh with the same connectivity but with 2D vertex
positions such that the angle of all the triangles are
best preserved. We denote the 2D mesh as {T , u},where u = (ui , vi ).
For a particular 3D triangle t with vertices at(x1 , y1 , z1 ), (x2 , y2 , z2 ), and (x3 , y3 , z3 ), we seek its

4𝐍𝐘
𝑥2 , 𝑦2 , 𝑧2

𝐁

𝑥1 , 𝑦1 , 𝑧1𝐀

𝑥3 , 𝑦3 , 𝑧3

𝐗
Obtain local basis:𝐀 = 𝑥3 , 𝑦3 , 𝑧3 − 𝑥1 , 𝑦1 , 𝑧1
𝐁 = 𝑥2 , 𝑦2 , 𝑧2 − 𝑥1 , 𝑦1 , 𝑧1
𝐍 = 𝐀 × 𝐁/ 𝐀 × 𝐁
𝐗 = 𝐀/ 𝐀
𝐘=𝐍×𝐗

Coordinates in local basis(𝑋1 , 𝑌1 ) = (0, 0)(𝑋2 , 𝑌2 ) = (𝐁 ⋅ 𝐗, 𝐁 ⋅ 𝐘)
(𝑋3 , 𝑌3 ) = (𝐀 ⋅ 𝐗, 0)

Fig. 4. Vertices of a triangle in a local coordinate basis.
associated 2D vertex positions ((u1 , v1 ), (u2 , v2 ) and(u3 , v3 )) under the conformal map. Using a local 2D
coordinate basis for triangle t, the conformality constraint is captured by the following linear equations.
1  ∆X1
∆Y1
S

∆X2
∆Y2

∆X3
∆Y3

−∆Y1
∆X1

−∆Y2
∆X2

−∆Y3
∆X3


ut = 0, (13)Here, ut = [u1 , u2 , u3 , v1 , v2 , v3 ]> , S is the areaof t, ∆X1 = (X3 − X2 ), ∆X2 = (X1 − X3 ) and∆X3 = (X2 − X1 ) (∆Y is similarly defined). Notethat variables (X1 , Y1 ), (X2 , Y2 ), and (X3 , Y3 ) wereobtained from t’s vertex coordinates (see Fig. 4).
Putting together the constraints for all the triangles,
we have the following sparse linear system.
Cu = 0.

(14)

Using indices i and j to index the I vertices andJ triangles respectively, the 2J × 2I matrix C in
Equation (14) has the following non-zero entries.
cj,i = ∆X
Sj ,cj+J,i = ∆YSj ,cj,i+I = − ∆Y
Sj
cj+J,i+I = ∆X
Sj

(15)

Ridge constraints. Notice that the original conformal mapping has only local constraints, which will
result in global distortion, Fig. 5.f. To reduce global
distortions during unwrapping, we add ridge andboundary constraints to constrain the solution further.
We take into consideration two facts. First, theridge lines remain straight after flattening but should
essentially become invisible on the flattened surface.
Second, the conformal mapping constraint Eq. (13)applies to beyond triangles. In particular, it is true forthree collinear points. Therefore, we propose using thecollinearity property to derive non-local constraints
during flattening. and add it to our conformal map
estimation problem. Referring to Fig. 4, and imagine
the collinear case, that is when point (x2 , y2 , z2 ) is also
lying on the X axis; in such case, Y2 = Y1 = Y3 = 0.
In addition, the area of the triangle T is zero. Hence,
the ridge constraints can be written in a form similar
to Eq. (13).
hi∆X1 ∆X2 ∆X3
0
0
0
0
0
0
∆X1 ∆X2 ∆X3 uR = 0. (16)IEEE TRANSACTION ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

5

iterative reweighted least squares method [34]. Figure 5 shows a result from the conventional LSCM (`2
method) and our proposed `1 method.

(a) RA (ours) + L1 (ours)(b) RA (ours) + Geo(c) RA (ours) + L2(d) Po + L1(ours)(e) Po + Geo(f) Po + L2

Fig. 5.

Rectification results from combination of methods. Acronyms RA and Po denote our ridge-aware method
and Poisson reconstruction respectively. L1 denotes our `1
conformal mapping method with non-local constraints; L2
indicates LSCM [29] and Geo indicates geodesic unwrapping [30].

where uR = [u1 , u2 , u3 , v1 , v2 , v3 ]> are the targeted 2D
coordinates similarly defined as ut . We select ridge
candidates in the same way as we did earlier duringreconstruction. However, this step is now more accurate because the surface is well reconstructed. For eachridge candidate (vertex), we find two farthest ridge
candidates along the ridge line in opposite directions
and instantiate the above mentioned constraint for
the three points. We assume that the boundary of
the flattened 2D document image has straight line
segments (they need not be straight lines on the 3D
surface). These boundary constraints can be expressedin a form similar to Eq. (16). We incorporate allridge and boundary constraints into a system of linear
equations.
Ru = 0.

(17)

Robust conformal mapping. We propose using an`1 norm instead of the standard squared `2 norm to
make conformal mapping robust to outliers. Putting
together Eqs. (14) and (17) in the `1 sense, we haveu∗ = argmin k Cu k1 +γ k Ru k1 ,

(18)

u

where γ balances the ridge and boundary constraints.
To avoid the trivial solution u = 0, we fix two
points of u to (ui , vi ) = (0, 0) and (uj , vj ) = (0, 1).
Equation (18) is then rewritten asu∗ = argmin k Cu k1 +γ k Ru k1 +θ k Efix k22 ,

(19)

u

where Efix is the energy function for the two fixed
points. We solve the objective function using the

3.3 Implementation details
Sparse 3D reconstruction. We recover the initial
sparse 3D point cloud using SfM. While any existing SfM method is applicable, we use the popularincremental SfM technique et al. [36] in our system.
We typically capture five to ten still images for eachdocument from different viewpoints. Capturing theseimages or equivalently a set of burst photos or a shortvideo clip only takes a few seconds. After running
SfM, we segment the document from the backgroundsurface in the reference image using a simple method
based on color difference and edge detection. In our
experiments, we assumed that the document has asufficiently different color from the background andtherefore the document boundary is visible with sufficient contrast. Figure 1a shows an input example andthe corresponding reconstruction.
Image warping. After recovering the flattened meshgrid u = {ui , vi }, we unwrap the input image withthe maximum document area in pixels. To obtaincorrespondence between the input image and {ui , vi },we project the 3D mesh points {zi (xi , yi )} into theimage to obtain image coordinates {x̃i , y˜i } using thecamera pose estimated using SfM. We then warp
the image according to the correspondence between{x̃i , y˜i } and {ui , vi } with bilinear interpolation.

4

E XPERIMENTS

We perform qualitative and quantitative evaluation
on a wide variety of input documents. The first setof experiments show that our method can handle
different paper types, document content and various
types of folds and creases. Next, we report a quantitative evaluation based on known ground truth using
local and global metrics where we demonstrate thesuperior performance and advantages of our method
over existing methods [29], [30], [28]. In all the experiments, we set parameters as follows: λ = 1e-5, β = 40,
γ = 1e3, θ = 1e2 and κth = 0.006. Our method
is insensitive to these parameters. Varying λ, γ, θ byfactors of 0.1 – 1.0 or varying β or κth by 50% fromthese settings did not change the result significantly.
4.1

Test Data

The first six out of the 12 test sequences (I – VI) contain documents with no fold lines, one fold line, twoto three parallel fold lines, and two to three crossing
fold lines respectively. The other six sequences (VII– XII) contain documents with an increasing numberof fold lines. Irregular fold lines were intentionallyadded to make the rectification more challenging.
All documents were either placed on a planar or
curved background surface. Sequence VII contains a

IEEE TRANSACTION ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

6

I

II

III

IV

V

VI

VII

VIII

IX

X

XI

XII

Fig. 6. [O UR RESULTS] Original images are shown in rows 1 and 3 and our rectification results are shown in rows 2 and 4.
shopping receipt on a paper roll whereas II and VIII
contain pages from a book. Sequences III, IV, IX and
X contain letters folded within envelopes. Sequence V,
VI, XI and XII contain examples of documents folded
inside a purse or notebook. The input images as wellas the results from our method are shown in Fig. 6.
Our method does not rely on the content, formatting,layout or color of the document. Thus, it is generally
applicable as long as a sufficient number of sparse
keypoints in the input images are available for SfM.

Global distortion metric. We first register the rectified
image to the ground truth by estimating a global
affine transform T estimated using SIFT keypoint
correspondences in these images [37].
"
#
a1
a3
0

T=

a2
a4
0

t1
t2
s

,

(20)

This is achieved by minimizing the squared error.
T∗ = argmin k Tp − p̂ k22 .

(21)

T

4.2

Quantitative Evaluation Metrics

We quantitatively evaluate the global and local distortion between the ground truth digital image andour rectified result using local and global metrics. The
digital version of six out of the 12 test documents wereavailable. We treat those images as ground truth andresize them by setting their height to 1000 pixels.

where, p and p̂ denote corresponding 2D keypoint positions using homogenous coordinates. We compute
the global distortion metric G as follows.
G = (a1 a4 − a2 a3 )/s2
G = max (G, 1/G).

(22)

A perfect result has G = 1; and larger values indicate
more distortion (see comparative results in Fig. 7).

IEEE TRANSACTION ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE
Distortion
1.14
1.12
1.1
1.08
1.06
1.04
1.02
1

7

Input
Data I

Data IIIRA + L1 (proposed)

Data IV

Data VI

RA + Geo

Data X

RA + L2

Mesh (Perriollat)

Mesh (proposed)

Data XIIPo + L1

Po + Geo

Global distortion evaluation metric
1
0.8
0.6
0.4
0.2
0

Frequency

1

Data I

Frequency
Data III

0.8

1Frequency
Data IV

0.8

0.6

0.6

0.4

0.4

0.2

0.2

0
Error
Error
1 4 7 10 13 16 1922
1 4 7 10 13 16 1922
1 4 7 10 13 16 19
22
Error
Frequency
Frequency
Frequency
111Data X
Data VI
Data XII
0.8
0.8
0.8
0

0.8
0.7
0.6
0.5
0.4
0.3
0.2
0.1
0

0.6
0.4

0.6

0.6
0.4

1

2

0.2

0.2

0

0
Error
1 4 7 10 13 16 19
22
RA + L1 (proposed)

3

4

5

6

7

8

9

10

11

12

13

14

15

0.4

16

17

18

19

20

0.2
0
Error
1 4 7 10 13 16 19
22
RA + L2

RA + Geo

Error
1 4 7 10 13 16 19
22
Po + L1

Po + Geo

Local distortion evaluation metricFig. 7.

Distortion metrics for datasets shown in Fig. 6.
Abbreviations are consistent with Fig. 5 and the text.

Local distortion metric. After warping the rectified
image with the affine transform T, we have removed
the global distortion as well as the scaling, rotation,and translation of the rectified image. After that,
we further evaluate the remaining local distortion.
We register the resulting image with the groundtruth using SIFT-flow [38] for dense registration. This
flow map is used to compute the local distortion
metric which cannot be removed by global affine
warping. The frequency distribution of local displacements are shown in lower figure in Fig. 7 andcompared with existing methods. We found dense
registration to be more useful for an unbiased evaluation than sparse SIFT keypoint-based registration because sparse methods are more likely to ignore many
matches if the result contains large deformations.
4.3

Comparison with existing methods

We first compare with three methods [28], [29], [30]on various real images and then use syntheticallygenerated data to further compare with the methods
designed for dense 3D point data [29], [30].
Perriollat et al. [28]. Their method explicitly parameterizes smooth rulers but cannot handle our document
images with creases and folds. Our method works fineon their dataset and produces a more accurate result
than the one obtained by running their code 1 (seeFig. 8). Although our result has minor artifacts due
to self-occlusion and fore-shortening, the flattening
result is quite accurate.
1. Their result shown here was generated by the original codeprovided by the authors. These result do not agree with the resultsin their paper. This is probably due to a difference in initialization.

Dewarp (Perriollat)

Dewarp (proposed)

Fig. 8. Comparison with Periollat et al.’s method [28].
Brown et al. [29], Zhang et al. [30]. We compare
to both methods using our sequences where groundtruth is available (Fig. 6). Since they require 3D range
data, we use our reconstructed surface as their input and compare the surface flattening quality. We
also compare our ridge-aware reconstruction to thestandard Poisson reconstruction method. As shownin Fig. 7, the global and local distortion metrics introduced earlier are used in the evaluation. Our method
has higher accuracy in terms of both metrics. Resultsfrom various methods have been compared in Fig. 5.
Evaluation on synthetic data. We compared our
method with [29], [30] on synthetically generated
dense 3D points because these methods require dense
3D points. We vary the point cloud size from 2K to300K (common in 3D range data) and inject varying
levels of Gaussian noise. The results from the threemethods are compared in Figure 9. These experiments
show that with low noise and high point density, allthree methods are comparable in accuracy. However,when the points are sparser or when the noise levelis higher, our method is more accurate than priormethods [29], [30].

5C ONCLUSION AND F UTURE W ORK

In this paper, we propose a method for automatically rectifying curved or folded paper sheets froma small number of images captured from different
viewpoints. We use SfM to obtain sparse 3D points
from images and propose ridge-aware surface reconstruction method which utilizes the geometric property of developable surface for accurate and dense
3D reconstruction of paper sheets. We also robustify
the algorithms using `1 optimization techniques. After
recovering surface geometry, we unwrap the surface
by adopting conformal mapping with both local andnon-local constraints in a robust estimation framework. In the future we will address the correctionof photometric inconsistencies in the document image
caused by shading under scene illumination.

1.2
1.1

Zhang et al.

1.007 1.042 1.167 1.371 1.635 2.070
1.003 1.016 1.062 1.133 1.231 1.342
1.001 1.005 1.017 1.035 1.061 1.096
1.000 1.001 1.004 1.009 1.015 1.0230123Noise Level

1

1

1

1

0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

0.6

0.6

0.4

1

1.1

150K

1.007 274.5 N/A N/A N/A N/A
1.019 22.50 1187 N/A N/A N/A
1.029 2.497 21.05 265.0 1230 3823
1.034 1.333 2.783 8.738 29.50 85.32
0123Noise Level

0.4

0.2
0

5

10

0

0.4

0.2
0

5

10

0

0.4

0.2
0

5

10

0

0.2
0

5

10

0

1

0.8

0.8

0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

0.6

0.6

0.4

0.4

0.4

0.4

0.4

0.2

0.2

0.2

0.2

0.2

0

5

10

0

Error

0

5

10

0

0

5

10

0

0

5

10

0

10

0

1

1

1

1

1

0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

0.6

0.6

0.4

0.4

0.4

0.4

0.4

0.2

0.2

0.2

0.2

0.2

5

10

0

Error

0

5

10

0

0

5

10

0

0

5

10

0

10

0

1

1

1

1

0.8

0.8

0.8

0.8

0.8

0.8

0.6

0.6

0.6

0.6

0.6

0.6

0.4

0.4

0.4

0.4

0.4

0.2

0.2

0.2

0.2

0.2

0

(a) Global distortion evaluation metric

10

Error

0

0

5

1

10

0

0

5

2

10

0

0

5

10

0

0

5

10

0

5

10

5

10

0.2
5

1

5

10

0.4

0

1

0

5

0.2
5

0.8

0

0

0.4

0

0.8

0

1

0

1

Frequency

1.2

10

Error

1

Frequency
1

Brown et al.

0.4

0.2
5

1

0

Points
2K
9K
36K
150K

0.4

0

1

0

1.1

Brown et al.

1
0.8

Frequency
1

1.2

Zhang et al.

1

0.8

0

1

8

Proposed

Frequency

0.2

9K

Points
2K
9K
36K
150K

Proposed
1.030 1.031 1.036 1.034 1.028 1.029
1.007 1.017 1.020 1.015 1.017 1.004
1.011 1.012 1.012 1.014 1.013 1.012
1.013 1.014 1.015 1.015 1.014 1.0170123Noise Level

36K

Points
2K
9K
36K
150K

2K Points

IEEE TRANSACTION ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE

0.4
0.2
0

3

5

4

10

0

0

Noise Level(b) Local distortion evaluation metricFig. 9. (a) Comparison of the global distortion metric between our method (top) and Zhang et al. [30] and Brown et al.[29]with varying point density and noise. Here lower values indicate higher accuracy. (b) Frequency distribution of local distortion
metrics for the associated experiments. Our method is more accurate when input point are sparser or have more noise.

R EFERENCES[1]

M. Pilu, “Undoing paper curl distortion using applicablesurfaces,” in CVPR, 2001.
[2] G. Meng, Y. Wang, S. Qu, S. Xiang, and C. Pan, “Active
flattening of curved document images via two structured
beams,” in CVPR, 2014.
[3] M. S. Brown and W. B. Seales, “Image restoration of arbitrarily
warped documents,” TPAMI, vol. 26, no. 10, 2004.
[4] T. Wada, H. Ukida, and T. Matsuyama, “Shape from shadingwith interreflections under a proximal light source: Distortionfree copying of an unfolded book,” IJCV, vol. 24, no. 2, 1997.
[5] L. Zhang, A. M. Yip, M. S. Brown, and C. L. Tan, “A unified
framework for document restoration using inpainting andshape-from-shading,” Pattern Recognition, vol. 42, no. 11, 2009.
[6] Y.-C. Tsoi and M. S. Brown, “Multi-view document rectification using boundary,” in CVPR, 2007.
[7] H. I. Koo, J. Kim, and N. I. Cho, “Composition of a dewarped
and enhanced document image from two view images,” TIP,
vol. 18, no. 7, 2009.
[8] N. Stamatopoulos, B. Gatos, I. Pratikakis, and S. J. Perantonis, “Goal-oriented rectification of camera-based document
images,” TIP, vol. 20, no. 4, 2011.
[9] Z. Zhang, X. Liang, and Y. Ma, “Unwrapping low-rank textures on generalized cylindrical surfaces,” in ICCV, 2011, pp.
1347–1354.
[10] M. Kazhdan, M. Bolitho, and H. Hoppe, “Poisson surface
reconstruction,” in Fourth Eurographics symposium on Geometry
processing, 2006.
[11] B. Lévy, S. Petitjean, N. Ray, and J. Maillot, “Least squares
conformal maps for automatic texture atlas generation,” in
ACM TOG, vol. 21. ACM, 2002.
[12] Z. Zhang, C. Lim, and L. Fan, “Estimation of 3d shape of
warped document surface for image restoration,” in ICPR,
2004.
[13] C. L. Tan, L. Zhang, Z. Zhang, and T. Xia, “Restoring warped
document images through 3d shape modeling,” TPAMI,
vol. 28, no. 2, 2006.
[14] F. Courteille, A. Crouzil, J.-D. Durou, and P. Gurdjos, “Shapefrom shading for the digitization of curved documents,” Machine Vision and Applications, vol. 18, no. 5, 2007.
[15] Y.-C. Tsoi and M. S. Brown, “Geometric and shading correction
for images of printed materials: a unified approach using
boundary,” in CVPR, 2004.
[16] A. Yamashita, A. Kawarago, T. Kaneko, and K. T. Miura,“Shape reconstruction and image restoration for non-flat surfaces of documents with a stereo vision system,” in ICPR, 2004.
[17] H. Cao, X. Ding, and C. Liu, “A cylindrical surface model torectify the bound document image,” in ICCV, 2003.
[18] H. Ezaki, S. Uchida, A. Asano, and H. Sakoe, “Dewarping of
document image by global optimization,” in ICDAR, 2005.
[19] A. Ulges, C. H. Lampert, and T. M. Breuel, “Document image
dewarping using robust estimation of curled text lines,” in
ICDAR, 2005.

[20] S. Lu, B. M. Chen, and C. C. Ko, “A partition approach for the
restoration of camera images of planar and curled document,”
Image and Vision Computing, vol. 24, no. 8, 2006.
[21] B. Fu, M. Wu, R. Li, W. Li, Z. Xu, and C. Yang, “A model-based
book dewarping method using text line detection,” in 2nd Int.
Workshop on Camera Based Document Analysis and Recognitionl,
2007.
[22] G. Meng, C. Pan, S. Xiang, J. Duan, and N. Zheng, “Metricrectification of curved document images,” TPAMI, vol. 34,
no. 4, 2012.
[23] C. Liu, Y. Zhang, B. Wang, and X. Ding, “Restoring cameracaptured distorted document images,” IJDAR, vol. 18, no. 2,
2014.
[24] B. S. Kim, H. I. Koo, and N. I. Cho, “Document dewarping
via text-line based optimization,” Pattern Recognition, 2015.
[25] D. Salvi, K. Zheng, Y. Zhou, and S. Wang, “Distance transform
based active contour approach for document image rectification,” in WACV, 2015.
[26] J. Liang, D. DeMenthon, and D. Doermann, “Geometric rectification of camera-captured document images,” TPAMI, vol. 30,
no. 4, 2008.
[27] Y. Tian and S. G. Narasimhan, “Rectification and 3d reconstruction of curved document images,” in CVPR, 2011.
[28] M. Perriollat and A. Bartoli, “A computational model ofbounded developable surfaces with application to imagebased three-dimensional reconstruction,” Computer Animation
and Virtual Worlds, vol. 24, no. 5, 2013.
[29] M. S. Brown, M. Sun, R. Yang, L. Yun, and W. B. Seales,“Restoring 2d content from distorted documents,” TPAMI,
vol. 29, no. 11, 2007.
[30] L. Zhang, Y. Zhang, and C. L. Tan, “An improved physicallybased method for geometric restoration of distorted document
images,” TPAMI, vol. 30, no. 4, 2008.
[31] H. Avron, A. Sharf, C. Greif, and D. Cohen-Or, “ 1-sparsereconstruction of sharp point set surfaces,” ACM TOG, 2010.
[32] A. C. Öztireli, G. Guennebaud, and M. Gross, “Feature preserving point set surfaces based on non-linear kernel regression,” in Computer Graphics Forum, vol. 28, no. 2. Wiley Online
Library, 2009.
[33] R. Tibshirani, “Regression shrinkage and selection via thelasso,” Journal of the Royal Statistical Society. Series B (Methodological), 1996.
[34] E. J. Candes, M. B. Wakin, and S. P. Boyd, “Enhancing sparsity
by reweighted `1 minimization,” Journal of Fourier analysis andapplications, vol. 14, no. 5-6, 2008.
[35] E. Portnoy, “Developable surfaces in hyperbolic space,” Pacific
Journal of Mathematics, vol. 57, no. 1, 1975.
[36] R. I. Hartley and A. Zisserman, Multiple View Geometry in
Computer Vision, 2nd ed. Cambridge University Press, ISBN:
0521540518, 2004.
[37] D. G. Lowe, “Distinctive image features from scale-invariant
keypoints,” IJCV, vol. 60, no. 2, 2004.