NAIST-IS-DD0661201

Doctoral Dissertation

Video Mosaicing Based on Structure from
Motion for Geometric Distortion-Free
Document Digitization

Akihiko Iketani

August 21, 2008
Department of Information Systems
Graduate School of Information Science
Nara Institute of Science and Technology

A Doctoral Dissertation
submitted to Graduate School of Information Science,
Nara Institute of Science and Technology
in partial fulﬁllment of the requirements for the degree ofDoctor of ENGINEERING
Akihiko Iketani
Thesis Committee:
Professor Naokazu Yokoya
Professor Hirokazu Kato
Associate Professor Kazumasa Yamazawa
Assistant Professor Tomokazu Sato

(Supervisor)(Co-supervisor)(Co-supervisor)(Co-supervisor)Video Mosaicing Based on Structure from
Motion for Geometric Distortion-Free
Document Digitization∗
Akihiko Iketani

Abstract
This thesis describes a novel video mosaicing method which is capable ofgenerating a geometric distortion-free mosaic image. Video mosaicing, which
stitches partial images of a target into a larger image called a mosaic image, hasbeen used to obtain high resolution images of documents. Generally, mosaic
images are prone to two types of geometric distortions: perspective distortion
which appears when the target document is not fronto-parallel to the camera’s
image plane, and curvature distortion which is caused by projecting curved
surface of the target document to the image plane of the camera.
This thesis ﬁrst focuses on a ﬂat document, and proposes a perspective
distortion-free video mosaicing method for ﬂat documents. In the proposed
method, extrinsic camera parameters are estimated for each frame by applying structure from motion technique to the captured video. Using estimatedextrinsic camera parameters, the method dewarps all the frame images andsynthesizes them on a virtual fronto-parallel plane to generate a super-resolved
mosaic image without perspective distortion.
Then, this method for ﬂat documents is extended to deal with curved documents. This extended method generates a virtually ﬂattened mosaic image of acurved surface. In this method, ﬁrst, extrinsic camera parameters, along with∗

Doctoral Dissertation, Department of Information Systems, Graduate School of Information Science, Nara Institute of Science and Technology, NAIST-IS-DD0661201, August21, 2008.

i

3-D feature positions are estimated by structure from motion. Then, by ﬁtting
a parameterized surface to the 3-D features, the shape of the curved document
is estimated. Using the estimated shape and extrinsic camera parameters, all
the frame images are dewarped to remove curvature distortion and synthesizedon a virtual plane to generate a mosaic image without curvature distortion.
Experiments on both ﬂat and curved documents have been performed using
a prototype system. In each experiment, the mosaic image has been proved tobe distortion-free by quantative analysis on distortion.
This work diﬀers from previous works in document digitization in that it
does not require any special hardware equipment besides a video camera. This
makes the method suitable for mobile solution, and is one step forward toubiquitous document digitization.

Keywords:
document digitization, geometric distortion, video mosaicing, extrinsic camera
parameter estimation, super resolutionii

Acknowledgements
This work was completed under the supervision of Professor Naokazu Yokoya
and Assistant Professor Tomokazu Sato of the Graduate School of Information
Science at the Nara Institute of Science and Technology.
I would especially like to thank my advisor, Professor Naokazu Yokoya,
who has been a great source of support and guidance throughout my Ph.D.
study. Without the continuous encouragement and advice of Professor Yokoya,
I could never have completed this thesis. I would also like to thank AssistantProfessor Tomokazu Sato, who has also been a wonderful source of support
and guidance throughout this study.
I am deeply grateful to Professor Hirokazu Kato and Associate Professor
Kazumasa Yamazawa, who has given me insightful comments on this research
as members of the thesis committee.
I have also beneﬁted greatly through being able to meet and work with anumber of people during my doctoral work at the Nara Institute of Science andTechnology. Assistant Professor Masayuki Kanbara and Assistant Professors
Sei Ikeda of the Graduate School of Information Science at the Nara Institute of
Science and Technology provided helpful comments and invaluable discussions
since the beginning of the joint project with NEC Corporation. I would also
like to thank all the members of the Vision and Media Computing Laboratoryof the Graduate School of Information Science at the Nara Institute of Scienceand Technology for their friendship and support.
I would also like to acknowledge the help and support from my supervisorsand colleagues in NEC Corporation. Doctor Keiji Yamada of C&C Innovation Laboratories has given me an opportunity to start this work as the jointiii

project of NEC Corporation and the Graduate School of Information Scienceat the Nara Institute of Science and Technology, and has guided me in the earlyyears of this study. Mr. Noboru Nakajima has given me numerous advices andguidance throughout this study. I would like to thank Mr. Atsushi Kashitani
and Mr. Toshihiko Hiroaki of Common Platform Software Research Laboratories for their supervision and continuous understanding in this work. I would
also like to thank all the members of Common Platform Software ResearchLaboratories who has supported and helped me to ﬁnish this work.
Finally, I especially want to thank my wife, Akiko, for understanding, supporting and encouraging me during my Ph.D. study.

iv

Contents
Abstracti

Acknowledgementsiii

List of Figuresvii

List of Tablesxi

1 Introduction
1
1.1. Previous Works in Camera-based Document Digitization . . . . 3
1.1.1 Document Digitization for Flat Documents . . . . . . . . 4
1.1.2 Document Digitization for Curved Documents . . . . . . 7
1.2. Positioning of This Study . . . . . . . . . . . . . . . . . . . . . 10
1.3. Outline of This Thesis . . . . . . . . . . . . . . . . . . . . . . . 10
2 Video Mosaicing for Flat Document13
2.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
2.2. Overview of the Method . . . . . . . . . . . . . . . . . . . . . . 14
2.3. Extrinsic Camera Parameter Estimation . . . . . . . . . . . . . 14
2.3.1 Deﬁnition of Extrinsic Camera Parameter and Error Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.3.2 Initial Estimation of Extrinsic Camera Parameters . . . . 19
2.3.3 Detection of Reappearing Features . . . . . . . . . . . . 22
2.3.4 Reﬁnement of Estimated Camera Parameters . . . . . . 22
2.4. Generation of Super-resolved Mosaic Image . . . . . . . . . . . . 24v

2.5. Prototype System . . . . . . . . . . . . . . . . . . . . . . . . . .
2.5.1 User Interface for Video Mosaicing . . . . . . . . . . . .
2.5.2 Implementation of Video Mosaicing System . . . . . . .
2.6. Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.6.1 Experiment on Synthetic Data . . . . . . . . . . . . . . .
2.6.2 Experiment on Document (Sequence 1) . . . . . . . . . .
2.6.3 Experiment on Photograph (Sequence 2) . . . . . . . . .
2.6.4 Experiment on Picture Scroll . . . . . . . . . . . . . . .
2.6.5 Quantitative Evaluation of Distortion . . . . . . . . . . .
2.7. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

25
25
27
30
30
31
33
34
34
49

3 Video Mosaicing for Curved Document51
3.1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
3.2. Overview of the Method . . . . . . . . . . . . . . . . . . . . . . 52
3.3. Extension for Curved Target . . . . . . . . . . . . . . . . . . . . 53
3.3.1 Initial 3-D Reconstruction by Feature Tracking . . . . . 53
3.3.2 Detection of Reappearing Features . . . . . . . . . . . . 55
3.3.3 Global Optimization . . . . . . . . . . . . . . . . . . . . 55
3.3.4 Target Shape Estimation by Surface Fitting . . . . . . . 55
3.3.5 Mosaic Image Generation . . . . . . . . . . . . . . . . . 58
3.4. Prototype System for Curved Document . . . . . . . . . . . . . 60
3.5. Experiments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
3.5.1 Experiment on Book (Sequence 1) . . . . . . . . . . . . . 62
3.5.2 Experiment on Label on Wine Bottle (Sequence 2) . . . 64
3.5.3 Quantitative Evaluation of Distortion . . . . . . . . . . . 65
3.6. Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
4 Conclusion

79

References

81

List of Publications

85

vi

List of Figures
1.1
1.2
1.3
1.4
1.5

Concept of ubiquitous document digitization. . . . . . . . . . . .
Geometric distortion in document images. . . . . . . . . . . . .
Concept of video mosaicing. . . . . . . . . . . . . . . . . . . . .
Mosaic image with perspective distortion. . . . . . . . . . . . . .
Mosaic image of curved surface by homography based method. .

2.1
2.2
2.3
2.4
2.5

2
3
5
7
9

Flow diagram of video mosaicing for ﬂat target. . . . . . . . . . 15
Mosaic image plane and camera. . . . . . . . . . . . . . . . . . . 15
Reprojection error. . . . . . . . . . . . . . . . . . . . . . . . . . 18
Initial assumption on the camera and the mosaic image plane. . 20
Detection of reappearing features. (a) camera path, posture andfeature positions on mosaic image plane, (b) sampled framesof input image sequence, (c) templates of the same feature in
diﬀerent images, (d) templates projected to a mosaic image plane. 23
2.6 User interface for video mosaicing. 1: input image and tracked
feature points. 2: estimated camera path and posture. 3: preview of generating a mosaic image. 4: capturing image area on
mosaic image. 5: instruction for speed of camera motion. . . . 26
2.7 Two-stage implementation in prototype system. . . . . . . . . . 28
2.8 Overview of the prototype system. . . . . . . . . . . . . . . . . 29
2.9 Evaluation of camera parameter estimation (simulation). . . . . 32
2.10 Sampled frames of input image sequence (Sequence 1). . . . . . 36
2.11 Tracked features in input image sequence (Sequence 1). . . . . . 37
2.12 Estimated extrinsic camera parameters and feature positions(Sequence 1). . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
vii

2.13 Generated super-resolved mosaic image (Sequence 1). . . . . . .
2.14 Comparison of input image and super-resolved mosaic image(Sequence 1). . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.15 Sampled frames of input image sequence (Sequence 2). . . . . .
2.16 Tracked features in input image sequence (Sequence 2). . . . . .
2.17 Estimated extrinsic camera parameters and feature positions(Sequence 2). . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.18 Generated super-resolved mosaic image (Sequence 2). . . . . . .
2.19 Comparison of input image and super-resolved mosaic image(Sequence 2). . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.20 Sampled frames of input image sequence (Picture Scroll). . . . .
2.21 Tracked features in input image sequence (Picture Scroll). . . .
2.22 Estimated extrinsic camera parameters and feature positions(Picture Scroll). . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.23 Generated mosaic image (Picture Scroll). . . . . . . . . . . . . .

39

3.1
3.2
3.3
3.4
3.5
3.6
3.7
3.8

53
56
60
63
63
66
67

Flow diagram of video mosaicing for curved target. . . . . . . .
Target shape estimation by polynomial surface ﬁtting. . . . . . .
Angle formed by surface normal and camera orientation. . . . .
Thick bound book with curved surface (Sequence 1). . . . . . .
Label on a wine bottle (Sequence 2). . . . . . . . . . . . . . . .
Sampled frames of input image sequence (Sequence 1). . . . . .
Tracked features in input image sequence (Sequence 1). . . . . .
Estimated extrinsic camera parameters and 3-D positions of features (Sequence 1). . . . . . . . . . . . . . . . . . . . . . . . . .
3.9 Target shape estimated from 3-D feature points (Sequence 1). .
3.10 Unwrapped mosaic image before shade correction(Sequence 1). .
3.11 Unwrapped mosaic image after shade correction(Sequence 1). . .
3.12 Sampled frames of input image sequence (Sequence 2). . . . . .
3.13 Tracked features in input image sequence (Sequence 2). . . . . .
3.14 Estimated extrinsic camera parameters and 3-D positions of features (Sequence 2). . . . . . . . . . . . . . . . . . . . . . . . . .
3.15 Target shape estimated from 3-D feature points (Sequence 2). .
viii

40
41
42
43
44
45
46
47
48
48

68
69
70
71
72
73
74
75

3.16 Unwrapped mosaic image (Sequence 2). . . . . . . . . . . . . . . 76

ix

List of Tables
2.1
2.2
2.3

Speciﬁcations of a video mosaicing system for ﬂat target. . . . 29
Conﬁguration of simulation. . . . . . . . . . . . . . . . . . . . . 31
Distances of adjacent grid points in generated mosaic images[pixels(percentage from average)] . . . . . . . . . . . . . . . . . 35

3.1
3.2

Speciﬁcations of a video mosaicing system for curved target. . . 61
Distances of adjacent grid points on the mosaic image [pixels(percentage from ave.)] (Book). . . . . . . . . . . . . . . . . . . 65

xi

Chapter 1
Introduction
Document digitization technology has enabled us to store thousands of pages ofprinted and written documents in a small piece of storage device in a computer,and to share them on the Internet with people over the world. For many years,
ﬂat-bed scanners have been commonly used for this purpose for their image
quality. Flat-bed scanners, however, are usually large and heavy, and are only
available in limited situations such as in oﬃce environments. On the other
hand, portable imaging devices such as digital cameras and cellular phones
with a built-in camera have become so popular, and there is increasing interestin using these devices as alternatives to ﬂat-bed scanners. Combined withwireless connection, these devices will turn into portable facsimile machines
which allow us to scan and send documents anytime, anywhere. The conceptof this ubiquitous document digitization is shown in Figure 1.1.
Camera-based document digitization, however, has several problems to besolved. One of the most critical problems is the resolution of the image acquiredwith these devices. For example, 10M pixel cameras enable full A4 pages to besampled at about 320 dots per inch (dpi), whereas standard ﬂat-bed scanners
enable sampling at a few thousands dpi.
Another problem is the geometric distortion in the acquired image. There
are two types of geometric distortions. One is perspective distortion, whichappears when the target document is not fronto-parallel to the camera’s image
plane. An example of this perspective distortion is shown in Figure 1.2(a). Due
1

scan document withportable imaging device

share document withpeople in distant places
immediately
Figure 1.1. Concept of ubiquitous document digitization.

to the perspective distortion, lines of text and page boundary are no longer
parallel in the captured image.
The other type of geometric distortion is curvature distortion, which is
caused by projecting curved surface of the target document to the image planeof the camera. This type of distortion is commonly observed for a boundbook, as shown in Figure 1.2(b). Distortion due to the curvature of the target
is evident in the curved lines of text and contour.
Various methods have been proposed to overcome the problems in resolution and distortion. In this chapter, we ﬁrst review previous works in camerabased document digitization. Then the positioning of this research against
previous works is deﬁned. Finally, the outline of this thesis is given.

2

(a) Perspective Distortion(b) Curvature Distortion

Figure 1.2. Geometric distortion in document images.

1.1. Previous Works in Camera-based Document Digitization

Previous document digitization methods can be classiﬁed into the following
two types: methods for ﬂat surface and those for curved surface. The ﬁrst
type of methods assumes the target document is on a plane. This is a common
assumption which holds when the document is printed on a sheet of paper andis placed on a ﬂat surface, e.g. desk, wall, etc. The other type of methods
relaxes the above assumption of ﬂat surface to curved surface. This kind of
surface is often observed when the target is a thick bound book and is opened
on a desk. In the following sections, both types of methods are reviewed anddiscussed.
31.1.1 Document Digitization for Flat Documents
In this section, we will have a review on camera-based document digitization
methods for ﬂat documents.
As described earlier, document images will undergo perspective distortion
when the target document is not fronto-parallel to the camera’s image plane.
Various methods have been proposed to correct this perspective distortion.
The most straightforward approach is to utilize the contour of the target toestimate the perspective. If the document can be assumed to be on a plane,
the transformation from the document plane to the image plane can be model
ed by a homography, which is deﬁned by eight coeﬃcients. The correctionof perspective distortion can be accomplished once the eight unknowns arefound. Since four pairs of corresponding points are suﬃcient to solve the eight
unknowns, Jung et al. [JKH02] extract four corners on the rectangular boundary of the target to obtain four pairs of correspondences, and estimate thehomography for distortion correction. This method, however, is only applicable when the rectangular boundary is captured in the image. It should also be
noted that this method is very prone to error if the detection of four corners
is unreliable.
Other methods utilise vanishing points to correct perspective distortion.
As described in [Rot00], from vanishing points, which are the intersectionsof 3-D orthogonal lines, the perspective distortion can be recovered. In text
documents, such orthogonal lines is abundantly obtained as parallel text lines,
column edge lines, and page boundary lines. Thus, two vanishing points, one
in the horizontal direction and the other in the vertical direction, can be robustly estimated. Myers et al. [MBLH01] ﬁrst detect text lines in the image
by connected component analysis after binarizing the image. Then, each text
line is rotated and the horizontal projection proﬁle is analyzed to ﬁnd the top
and baseline for each text line. Similarly, by analyzing the vertical projection
proﬁle, the vertical edge lines is found. Finally, the horizontal and verticalvanishing points are determined as the intersections of horizontal and verticallines, respectively. Once the horizontal and vertical vanishing points are found,homography that maps the vanishing points back to inﬁnity can be computed.
4

Frame images in
the captured video(partial images ofthe document)

Mosaic image
constructed bystitching all theframe images

Figure 1.3. Concept of video mosaicing.

By dewarping the image with this homography, perspective distortion is corrected. Although these methods are robust compared to the methods basedon four point correspondences, they are only applicable to documents withtext lines. In case of documents with ﬁgures or photos, detection of vanishingpoints would be unreliable, and thus, these methods would fail in correcting
perspective distortion.
So far, we have focused on methods for correcting perspective distortion. In
the rest of this section, we will review methods to solve the resolution problem
in camera-based document digitization. Various techniques have been proposed to solve the resolution problem. Among them, a video mosaicing technique is one of the most promising solutions. In video mosaicing, as shown in
Figure 1.3, partial images of the document are captured as a video sequence,and multiple frame images are stitched seamlessly into one large, high resolution image called a mosaic image. Conventional methods usually carry out
5pairwise registration between two successive images, and construct a mosaic
image by warping all the images to a reference frame (in general, the ﬁrst
frame). Szeliski [Sze94] has developed a method based on homography. In thismethod, for every pair of consecutive frames, the homography which minimizes
the sum of squared diﬀerences between the two frames is estimated.
After his work, various extensions to this method have been proposed[CKH+ 98, TSTT00, HCBH00, LQST01, MJ02, KH03, BCR02, GS03]. Oneof the major extensions is the use of image features instead of all the pixels inimages in order to reduce computational cost [CKH+ 98, TSTT00, HCBH00].
Some methods introduce a global optimization process of homographies after pairwise registration in order to reduce cumulative errors in the estimatedhomographies [MJ02, SHK98]. This process is sometimes called bundle adjustment.
Video mosaicing methods provide a simple way to construct a high resolution document image with a low resolution camera. The drawback in video
mosaicing is that the user has to take special care in setting the camera’s image plane in the reference frame to be fronto-parallel to the document plane.
Otherwise, the resultant mosaic image would suﬀer from the same type of
perspective distortion as described earlier. Figure 1.4 shows an example ofa mosaic image with perspective distortion. In this ﬁgure, the region corresponding to the reference frame is shown in a white rectangle. As can beseen, perspective distortion has been induced in the reference frame. Since
all the other images are aligned to this reference frame, the same perspective
distortion is observed all over the resultant mosaic image.
Combining video mosaicing with the above mentioned distortion correction
methods can solve this problem. Liang et al. [LDD06] ﬁrst correct perspective
distortion in each frame image by utilizing vanishing points, and then synthesize these images to obtain perspective distortion-free mosaic image. Thismethod, however, shares the same limitation as the above mentioned distortion correction methods in that it can only be applied to documents with textlines. It should also be noted that the detection of vanishing points, carriedout in each frame individually, can be unstable since only a small number ofpartial text lines are present in each image.
6

Figure 1.4. Mosaic image with perspective distortion.

1.1.2 Document Digitization for Curved Documents
In this section, camera-based document digitization methods for curved documents are reviewed.
As described earlier, the curvature of the document causes non-linear distortion in the captured image, as shown earlier in Figure 1.2(b). In the ﬁeldof document analysis, various methods to remove this curvature distortion
have been proposed. These methods can be classiﬁed into the following two
types: methods based on 3-D shape measurement and those based on a priori
knowledge on documents.
The ﬁrst type of methods measures the surface shape or image deformationby special hardware equipment and restores the ﬂattened image of the document. Brown and Seales [BS01] measure the shape of the document using a slit
7

light projection device. Then, an elastic mesh model is ﬁtted to the 3-D shape,and by pushing the mesh down to a plane, the ﬂattened image of the page is
obtained. Pilu [Pil01] ﬁts an applicable surface model, where the distances
between mesh nodes are ﬁxed, to the 3-D shape acquired by slit light projection device. This mesh model is ﬂattened by an iterative process. Doncescu
et al. [21] employ a light grid projector which is set up on a scanning table.
They ﬁrst project the light grid on a plane and record the position of each grid
point as its initial position. Then, the same light grid is projected on a curved
document. By morphing the captured image so that the grid points on the
document is transformed to their initial positions, they correct the curvature
distortion in the image. Note that in this method, the surface shape is not
explicitly measured. Yamashita et al. [YKKM04] recover the range data of
the surface by stereo vision system. After ﬁtting NURBS surface to the range
data, a ﬂattened document image is restored by expanding the surface. Although these methods are applicable to arbitrarily curved surface, they require
special and usually heavy hardware equipment, which makes them diﬃcult tobe applied for mobile solution.
The other type of methods restores a distortion-free image from a single
input image using a priori knowledge on documents. The methods proposed by
Cao et al. [CDL03] and Liang et al. [LDD05] assume the target document iscomposed of horizontal text lines, and extracts baseline for every text line using
a morphological method. A distortion-free image of the target is generated bywarping the captured image so that all the baselines are parallel to one another.
Brown and Tsoi [BT04] assume the contour of the page is captured in theimage, and warps the image so that the contour is transformed into a rectangle.
Although these methods are capable of removing curvature distortion froma single input image and do not require any special hardware equipments,
they can only be applied to targets which fulﬁll the underlying assumptions.
Moreover, the resolution of the acquired image is limited to that of the camera
itself.
Video mosaicing, described earlier in Section 1.1.1, might be considered asa good solution to acquire higher resolution images. However, video mosaicing
methods, which are based on homography estimation, are only applicable when8

Figure 1.5. Mosaic image of curved surface by homography based method.

the target is a plane, or when the optical center of camera is approximately
ﬁxed throughout the video capturing. If the target is a curved surface, theabove assumption no longer holds, thus will cause misalignment of images in
the resultant mosaic image. Figure 1.5 shows a mosaic image of a book shownin Figure 1.2(b) generated by a conventional homography based method. As
can be seen, misalignment of images has caused distortion and blur in the mosaic image. Although there are some video mosaicing methods which can deal
with curved surface, they require an active camera and a slit light projection
device [GS03], or manual measurement of the surface shape [PBCP96].
9

1.2. Positioning of This StudyIn the above sections, previous works in camera-based document digitization
for ﬂat and curved documents have been reviewed and discussed. Video mosaicing methods seem to be promising in that they enable document digitization with high resolution which goes beyond that of the camera itself. Thesemethods, however, are prone to perspective and curvature distortion, as shownin Figures 1.4 and 1.5. Although various methods have been proposed to correct these geometric distortions, they require special hardware equipments
which make them diﬃcult to be applied for mobile solution, or assume speciﬁc
structures in documents, e.g. text lines, rectangular boundary, etc., which limits the type of documents they can be applied to. In summary, there has been
no work proposed on video mosaicing that can deal with geometric distortion
without using any special hardware equipments besides the camera.
The goal of this study is to develop a video mosaicing method which only
requires a camera and is capable of generating a geometric distortion-free mosaic image. Details of the proposed method will be described in this thesis.
This method is based on a structure-from-motion technique, which recovers
extrinsic camera parameters as well as sparse 3-D scene geometry from animage sequence in real time. Using the 3-D geometry recovered by the algorithm, a mosaic image without perspective distortion is generated for a ﬂat
document. For a document composed of curved surfaces, mosaic images ofvirtually ﬂattened pages are generated. Note that unlike previous distortion
correction methods which make use of speciﬁc structures in documents, e.g.
text lines or boundary of the document, the proposed method is capable ofcorrecting geometric distortion regardless to the content of documents.

1.3. Outline of This Thesis
The rest of this thesis is structured as follows. This thesis ﬁrst focuses on a ﬂat
document, and proposes a perspective distortion-free video mosaicing methodfor ﬂat documents in Chapter 2. Experimental results on ﬂat documents areshown and are quantitatively evaluated. Real-time implementation issues are10

also discussed. In Chapter 3, the above method for ﬂat documents is extended
to deal with curved documents. With this extension, a curvature distortionfree mosaic image can be generated for curved documents. Experiments are
performed on curved documents to evaluate the feasibility of the method.
Finally, conclusion of this thesis and future works are given in Chapter 4 .

11

Chapter 2
Video Mosaicing for Flat
Document
2.1. Introduction
This chapter describes a perspective distortion-free video mosaicing methodfor ﬂat documents. In this method, extrinsic camera parameters, instead ofhomographies, are estimated for each frame by applying a structure-frommotion technique [SKYT02] to the captured video. Using estimated extrinsic
camera parameters, the method dewarps all the frame images and synthesizes
them on a virtual rectiﬁed image plane to generate a perspective distortion-freemosaic image.
Two assumptions are made in this method. One is that the target document
is planar. The other is that intrinsic camera parameters are known in advance,and remain ﬁxed throughout image capturing.
In the following sections, ﬁrst, the overview of the method is given(Section 2.2),
and then each process composing the method is described in detail (Section 2.3,
2.4). After describing real-time implementation issue and the prototype system based on this method (Section 2.5), experimental results on ﬂat documents
using the prototype system is shown (Section 2.6). Finally, the conclusion ofthis chapter is given (Section 2.7).
13

2.2. Overview of the Method
The ﬂow of the proposed method is given in Figure 2.1. As can be seen,
the whole process is composed of two processes: extrinsic camera parameter
estimation (A) and mosaic image generation (B).
In extrinsic camera parameter estimation (A), ﬁrst, initial estimation of
extrinsic camera parameter is carried out for each frame by tracking image
features in the input video (a). Then, reappearing features are detected (b),and are utilized to globally optimize the estimated parameters to minimize thecumulative estimation error in the whole input sequence (c).
In mosaic image generation (B), all the images are projected and synthesized on a virtual rectiﬁed plane using the estimated extrinsic camera parameters. Finally, a super-resolved mosaic image is generated by an iterative backprojection algorithm.
In the following sections, each process in the proposed method is describedin detail.

2.3. Extrinsic Camera Parameter Estimation
This section describes the procedure to estimate extrinsic camera parameters.
As shown in Figure 2.1, this process is composed of 3 processes: (a) initial
estimation of extrinsic camera parameters by tracking image features, (b) detection of reappearing features and (c) reﬁnement of the estimated camera
parameters. Before describing these processes, ﬁrst, extrinsic camera parameters and an error function to be minimized are deﬁned. Then, process (a) to(c) are described in detail.

14

(A) Extrinsic camera parameter estimation(a) Initial estimation by tracking features
Iterate from first frame to last frame(b) Detection of re-appearing features(c) Refinement of estimated camera parameters(B) Generation of mosaic image
Figure 2.1. Flow diagram of video mosaicing for ﬂat target.

Mosaic image plane(xp, yp)M1(u1p, v1p)
First frame

MfM2(ufp, vfp)
(u2p, v2p)
2nd frame

f-th frame

Figure 2.2. Mosaic image plane and camera.

2.3.1 Definition of Extrinsic Camera Parameter and Error Function
In this method, as shown in Figure 2.2, the extrinsic camera parameter Mf
for the f -th frame is deﬁned as a transformation between the coordinates on
the mosaic image plane and the f -th frame image plane. Mf is a simpliﬁed
version of a standard extrinsic camera parameter Mfullf commonly used incomputer vision. In this section, we will see how the standard Mfullf can be
simpliﬁed to Mf , and how lens distortion is dealt with in this deﬁnition. An
error function used for the estimation of Mf is also described.
15

Generally, an extrinsic camera parameter Mfullf for the the f -th framethat transforms the world coordinate system to the camera coordinate system
is given by a 3 × 4 matrix with 6 degree of freedom as follows:⎛

c1 c3 + s1 s2 s3⎜⎜
Mfullf = ⎝ −s1 c3 + c1 s2 s3
c2 s3

s1 c2
c1 c2
−s2

−c1 s3 + s1 s2 c3
s1 s3 + c1 s2 c3
c2 c3

si = sin (rif ), ci = cos (rif )(i = 1, 2, 3),

⎞

t1f
⎟
t2f ⎟
⎠,
t3f

(2.1)

(2.2)

where (t1f , t2f , t3f ) are camera position parameters, and (r1f , r2f , r3f ) are camera posture parameters representing yaw, pitch, roll of a camera, respectively.
If we consider an ideal camera with the focal length of 1 and without lensdistortion, arbitrary 3-D point Sp = (xp , yp , zp ) is projected to x̂f p = (ûf p , v̂f p )on this ideal image coordinate by the following equation:
⎛

⎛

⎞

⎞

xp
⎜
⎟
ûf p
⎜ y ⎟
⎜
⎟
p
⎜
⎟
⎟
⎟,
a⎜
⎝ v̂f p ⎠ = Mfullf ⎜⎜ zp ⎟
⎝
⎠
1
1

(2.3)

where a is a parameter. Since the target is assumed to be a plane, without
losing generality, we deﬁne the plane as z = 0, and set the z element of arbitrary
3-D positions on the target plane to 0. This degenerates 3-D coordinate Sp =(xp , yp , zp ) to 2-D coordinate (xp , yp ), and simpliﬁes the above equations asfollows:⎛⎞
c1 c3 + s1 s2 s3 s1 c2 t1f
⎜
⎟
⎟
(2.4)
Mf = ⎜⎝ −s1 c3 + c1 s2 s3 c1 c2 t2f ⎠ ,c2 s3−s2 t3f
⎛

⎞

⎛

⎞

ûf p
xp
⎜
⎟
⎜
⎟
⎟
⎜
⎟
a⎜
⎝ v̂f p ⎠ = Mf ⎝ yp ⎠ .
1
1

(2.5)

The transformation matrix Mf in Eqs. (2.4) and (2.5) is the extrinsic camera
parameter employed in this method, and is estimated for every frame in the
input sequence.
16

So far, we have considered an ideal camera without lens distortion. In
practice, however, we cannot neglect the eﬀect of lens distortion, which induces
displacement between the ideal image coordinate x̂f p = (ûf p , v̂f p ) and thecorresponding coordinate xf p = (uf p , vf p ) on the real image. According toTsai’s camera model [Tsa86], the relationship between these two coordinatesis given by a set of intrinsic camera parameters as follows:(ûf p , v̂f p ) = R(uf p − cu )


r=

ccdu
ccdv
, R(vf p − cv ),scru F su
scrv FR = (1 + k1 r2 + k2 r4 ),

(2.6)
(2.7)



2
2
ccdu
ccdv
(uf p − cu ) +(vf p − cv ) ,scru su
scrv

(2.8)

where F is the focal length, su is the aspect ratio of the CCD sensor element,(cu , cv ) is the position of optical center, (ccdu , ccdv ) is the CCD size, (scru , scrv )is the image resolution and (k1 , k2 ) are distortion parameters.
In this method, the ideal image coordinate x̂f p is precalculated for every
real image coordinate xf p by applying the above transformation before it isfurther transformed by Eq. (2.5). For simplicity, however, this transformationis omitted in the rest of this thesis.
Finally, an error function used for extrinsic camera parameter estimation
is deﬁned. In general, the projected position x̂f p of feature p to the f -th image
frame does not coincide with the actually detected position xf p = (uf p , vf p )on the ideal image coordinate, as shown in Figure 2.3, due to errors in featuredetection, extrinsic camera parameter and 3-D feature position estimation. In
this method, the squared distance between them, called reprojection error, isdeﬁned as follows for feature p on the f -th frame:
Ef p = |x̂f p − xf p |2
= {(ûf p − uf p )2 + (v̂f p − vf p )2 }.

(2.9)(2.10)In the following sections, we will see how this reprojection error is employed
to estimate Mf and Sp .

17

worldcoordinate
extrinsic camera
parameter Mf

detected
position x̂ p

3D feature
position Sp

projected
position x’p

cameracoordinate

Figure 2.3. Reprojection error.

18

2.3.2 Initial Estimation of Extrinsic Camera Parameters
Extrinsic camera parameter estimation starts from computing initial estimateof Mf for each frame. This is carried out by structure from motion method
proposed in [SKYT02]. Given an initial value for M1 , i.e. extrinsic camera
parameter for the ﬁrst frame, and (xp , yp ) for every feature captured in the ﬁrst
frame, Mf for each frame, along with (xp , yp ) for each feature on the target,
are iteratively estimated.The ﬂow of this process is as follows.
In the ﬁrst frame (f = 1), as shown in Figure 2.4, it is assumed that the
focal plane of the camera is approximately parallel to the target and that the
viewpoint of the camera is a certain distance, say d, away from the mosaic
image plane z = 0. Based on this assumption, the extrinsic camera parameterfor the ﬁrst frame is given as follows:
⎛

⎞

1 0 0
⎜
⎟
⎜
M1 = ⎝ 0 1 0 ⎟⎠.
0 0 −d

(2.11)For each feature p in the ﬁrst frame, which is detected by Harris corner detector[HS88], its position (xp , yp ) on the mosaic image plane is given by the same
assumption as follows:
⎛
⎞
⎛
⎞
x
û
d
p
1p
⎝
⎠=⎝
⎠.
(2.12)
ypv̂1p dNote that these are only initial values, which will be corrected in the reﬁnement process (Figure 2.1(c)).
In the subsequent frames (f > 1), Mf is estimated by iterating the following
steps for each frame.
Tracking of image features: All the image features in the previous frame
are tentatively tracked to the current frame using a standard templatematching. In order to prevent drift problem in feature tracking, interest
points detected by Harris corner detector [HS88] are used as candidate
positions for matching.
After this tentative tracking, outliers of corresponding points are detected by the RANSAC approach [FB81]. For every feature detected as
19mosaic image
plane z = 0

viewpointz = -d

v

Sp

y

x̂ p
o

u

x

z

Figure 2.4. Initial assumption on the camera and the mosaic image plane.

an outlier, its corresponding point is re-searched in a limited searchingarea which is computed by a temporal camera parameter estimated using
inlier points.

Extrinsic camera parameter estimation: Extrinsic camera parameter Mf
is estimated using the tracked position (uf p , vf p ) in the image plane andits corresponding position (xp , yp ) in the mosaic plane. In this step, thesum of reprojection errors for all the features in the f -th frame i Ef i
is minimized to estimate an extrinsic camera parameter Mf of the current frame. Since this is a non-linear minimization problem, special carehas to be taken to avoid local minima. In this method, ﬁrst, approximated solution is computed as an initial estimate by linear algorithm[SKYT02]. Then, starting from this initial estimate, camera position(t1f , t2f , t3f ) and camera posture (r1f , r2f , r3f ) which minimize the error function are estimated by Levenberg-Marquardt algorithm. Finally,
the extrinsic camera parameter Mf is obtained by the the estimated(t1f , t2f , t3f , r1f , r2f , r3f ) and Eq. (2.4). Note that for the position (xp , yp )20

in the mosaic image plane, the estimated result in the previous iteration
is used.
Estimation of feature position on mosaic plane: The position of each feature p in the mosaic image plane is computed and reﬁned in every frameby minimizing the error function fi=1 Eip . This error function is also
minimized by Levenberg-Marquardt algorithm after the linear estimation of the approximated solution.
Deletion and Addition of features: Selecting good features for tracking isessential in obtaining accurate estimates of camera parameters. In thisstep, a set of image features to be tracked is automatically updated by
testing multiple criteria for each feature. Here, the conﬁdence measurefor each feature is deﬁned as an inverse of the variance of its reprojection
error in each frame. If an image feature satisﬁes either of the following
conditions, the feature is considered unreliable and is deleted from theset of features to be tracked.
• Conﬁdence measure is under a given threshold.
• Matching error in template matching is more than a given threshold.
On the other hand, if a feature candidate detected by Harris cornerdetector [HS88] satisﬁes the all the conditions below, it is added to theset of features to be tracked.
• Conﬁdence measure is over a given threshold.
• Matching error in template matching is less than a given threshold.

By iterating the above steps, extrinsic camera parameters Mf and 3-Dfeature positions Sp are estimated.

21

2.3.3 Detection of Reappearing Features
Figure 2.5 (a) shows an example of camera path in video mosaicing. Due to thiscamera motion, most of the image features come into the image, move across
toward the end of the image, and disappear. Some features, however, reappear
in the image as shown in Figure 2.5 (b). In this step, these reappearing features
are detected, and distinct tracks belonging to the same reappearing feature arelinked to form a single long chain. This will give tighter constraints amongcamera parameters in temporally distinct frames, and thus makes it possible
to suppress cumulative errors in the global optimization step described later.
Reappearing features are detected by examining the similarity of the patterns among features belonging to distinct tracks. The problem here is thateven if two patterns belong to the same feature on the target, they can havediﬀerent appearance due to perspective distortion, as shown in Figure 2.5. To
remove this eﬀect, ﬁrst, templates of all the features are projected to the mosaic image plane. Then, feature pairs whose distance in 3-D space is less thana given threshold are selected. For each feature, a set of multi-scale templates
are generated, and in each scale, the similarity of the templates are evaluatedwith the normalized cross correlation function. If the correlation of templates
in every scale is higher than a certain threshold, the feature pair is regarded
as reappearing features, and tracks belonging to each feature are merged intoa single track.

2.3.4 Refinement of Estimated Camera Parameters
Since the initial estimation of extrinsic camera parameters described in Section
2.3.2 is an iterative process, its result is subject to cumulative errors. In thisprocess, the cumulative errors is minimized over the whole input images using
bundle adjustment [TMHF99].
The estimation error E is given by the sum of reprojection errors as follows:E=fp

Ef p .

(2.13)

E becomes larger as more error is accumulated in initial estimate. Moreover, if
the assumption that the focal plane of the camera in the ﬁrst frame is parallel
22

Compensate forDistortion

(a)

(b)

(c)

Matching(d)Figure 2.5. Detection of reappearing features. (a) camera path, posture andfeature positions on mosaic image plane, (b) sampled frames of input image
sequence, (c) templates of the same feature in diﬀerent images, (d) templates
projected to a mosaic image plane.

to the target is violated, E becomes even larger. Thus, by minimizing the error
function E with respect to the camera parameters Mf and the feature positions(xp , yp ), cumulative errors are minimized, and in case where the focal plane of
the camera in the ﬁrst frame is not parallel to the target, the correct extrinsic
camera parameters are estimated. Again, this is a non-linear minimization
problem, which is solved by Levenberg-Marquardt algorithm. Here, the initial
parameters for this optimization are given by the process described in 2.3.2.

Note that in this bundle adjustment process, reappearing features detectedin the previous step are utilized to chain input images of non-successive frames.
Reappearing feature detected in step (c) and its corresponding feature aretreated as single feature to compute the error function E. Since these feature chains give strong geometric constraints for extrinsic camera parameters,
accurate camera parameters can be acquired.
23

2.4. Generation of Super-resolved Mosaic Image

In the ﬁnal process, a super-resolved mosaic image is generated using theestimated extrinsic camera parameters. Here, the iterative back projection
algorithm [IP91] is employed to generate a super-resolved mosaic image.
First, an initial mosaic image S (0) is generated as follows. All the frame
images are projected onto the mosaic image plane using Eq. (2.5) with theextrinsic camera parameters Mf estimated in the previous step, and blended.
Here, the blended image is resampled on ﬁner grid so that the size of a single
pixel in the input image equals to n × n pixels (n > 1) in the mosaic image.
This n is referred to as magniﬁcation ratio.
Then, the following process is iterated to estimate the super-resolved mosaic
image. Starting with the initial mosaic image S (0) , the imaging process issimulated using geometric transformation and point spread function (PSF) to(0)
obtain a set of low resolution images {If }, each of which corresponds to theobserved input image {If }. If S (0) is the correct super-resolved image, the(0)simulated image {If } must be identical to {If }. On the other hand, as the(0)estimation error in S (0) becomes large, so does the diﬀerence between {If } and(0){If }. Thus, the diﬀerence images {If − If } are computed, and each value
in the diﬀerence images is back-projected and added onto its corresponding
pixels in S (0) . This process is repeated iteratively until the super-resolved
image converges.
It is known that there exists a certain limit on the magniﬁcation ratio nin the super-resolution technique [BK02]. Here, the magniﬁcation ratio n is
empirically determined to 2.0. As for the PSF, Capel [CZ00] has proved that
PSF can be approximated by the Gaussian function. In the proposed method,
the Gaussian function with standard deviation of 0.7 pixel is employed as thePSF.
24

2.5. Prototype System
This section describes a prototype system based on the proposed method.
In video mosaicing, user operation for moving the camera over the target document plays an important role in accomplishing the task of document
digitization eﬃciently and accurately. In this sense, video mosaicing systemis, by nature, an interactive system which involves man and machine. This
important fact, however, has not been focused in previous works of video mosaicing. In this section, ﬁrst, we will have further discussion on this topic, andpropose an ideal user interface for video mosaicing. Then, we will see how
the proposed method and the proposed user interface are implemented in the
prototype system.

2.5.1 User Interface for Video Mosaicing
In video mosaicing, the most eﬃcient way to move the camera would be theone that enables to capture a set of input images which satisﬁes the following
conditions:• Input images exhaustively cover the target document.
• The region captured in each input image is mutually exclusive to one
another.
Input images satisfying the former condition can be captured if the user memorizes which part of the target is already captured, and decides where thecamera should be moved in the next frame to capture a new region on the target. This, however, becomes extremely hard when the number of the captured
images gets larger.
The latter condition can be satisﬁed if the user moves the camera faster sothat overlapping regions among the input images become as small as possible.
Faster camera motion, however, degrades the quality of the mosaic image since
the error of estimated camera parameters increases due to tracking errors anddecrease in the number of frames where each feature is tracked. These twofacts imply that there exists an optimal speed for camera motion in terms of
25

1

3

4

2
5

Figure 2.6. User interface for video mosaicing. 1: input image and tracked
feature points. 2: estimated camera path and posture. 3: preview of generatinga mosaic image. 4: capturing image area on mosaic image. 5: instruction forspeed of camera motion.

accuracy and eﬃciency. Moving the camera with this optimal speed, however,requires a special training on video mosaicing, which is not a realistic solution.
In order to solve these problems, a novel user interface for video mosaicing
is proposed. The proposed user interface is shown in Figure 2.6. During image
acquisition, a preview of the mosaic image under construction is rendered in
the right side window (Figure 2.6(3)). This preview is updated every frame inreal time using captured images and the estimated camera parameters. The
region corresponding to the current frame is highlighted in the mosaic image
to help the user to recognize which part of the target is currently captured(Figure 2.6(4)). With this preview, the user can easily recognize which partof the document is still left to be captured, and ﬁgure out where to move26

the camera in the subsequent frames, thus can capture input images which
exhaustively cover the whole target.
In addition to the preview image, a speed indicator which shows the current
speed of the camera is shown at the bottom of the right window (Figure 2.6(5)).
In this speed indicator, the current speed of the camera is shown by an arrow
mark on a speed gauge, and the gauge is divided into 3 sections : “too slow”,“best speed”(optimal), and “too fast”. With this speed indicator, the user
can move the camera with the optimal speed. Here, the optimal speed wasdetermined by an experiment on synthetic data with ground truth. The detailof this experiment is described in Section 2.6.
The user can also take a look at currently captured images and estimatedcamera path in the left side windows (Figure 2.6(1), (2), respectively), if necessary.

2.5.2 Implementation of Video Mosaicing System
The most important factor of the proposed user interface is that real-time
feedback is given to the user. To realize this in the prototype system, theprocesses of the proposed method is implemented in two stages: real-timestage and oﬀ-line stage, as is shown in Figure 2.7.
In the real-time stage (Figure 2.7 (1)), a user captures a target document
using a handheld camera. In this stage, initial estimates of the extrinsic camera
parameters for each frame as well as the 2-D position of each image feature are
estimated in real time by the process proposed in Section 2.3.2 (a). The system
also renders the user interface described above (b). Here, the preview of thegenerated mosaic image is rendered as follows. For each frame, the captured
image is resized into a lower resolution image and stored to texture memory.
Every stored texture is warped to the mosaic image plane by texture mapping
using Eq. (2.5) with the initial estimate of extrinsic camera parameters. Although cumulative errors are introduced in the initial estimate of the extrinsic
camera parameters, their accuracy is suﬃcient for the purpose of rendering acoarse preview of the mosaic image.
In the oﬀ-line stage (Figure 2.7 (2)), reappearing features are detected (c),27

(1) Real-time Stage(a) Camera parameter estimation by tracking features(b) Generation of preview image and instruction for a user
Iterate from first frame to last frame(2) Off-line Stage(c) Detection of re-appearing features(d) Refinement of estimated camera parameters(e) Generation of super-resolved mosaic image

Figure 2.7. Two-stage implementation in prototype system.

the estimated viewpoint and 2-D position of each feature are reﬁned (d), anda super-resolved mosaic image without perspective distortion is generated (e).
The overview of the prototype system is shown in Figure 2.8. The system
is composed of a laptop PC and a hand-held IEEE1394 CCD camera. The
speciﬁcations of the system are shown in Table 2.1. Note that intrinsic parameters of the video camera are calibrated by Tsai’s method [Tsa86] in advance,
and they are ﬁxed throughout the image capturing.
Experiments performed by this prototype system is described in the following section.

28

Figure 2.8. Overview of the prototype system.

Table 2.1. Speciﬁcations of a video mosaicing system for ﬂat target.
Laptop PC
CPU
Pentium-M 1.6GHz
Memory1GBIEEE1394 camera (Aplux C104T)
Resolution
640×480 pixels
View angle
31.7◦ × 24.1◦
Maximum frame rate
15 frames/sec

29

2.6. Experiments
Experiments are performed by the prototype video mosaicing system to evaluate the feasibility of the proposed method.
First, an experiment on synthetic data with ground truth is performed
to evaluate the accuracy of extrinsic camera parameter estimation, and to
determine the optimal speed described in Section 2.5.1.
Then, experiments are performed on three kinds of ﬂat printed paper togenerate super-resolved mosaic images. The ﬁrst target is a printed A4 size
document (sequence 1). The second target is a printed photograph on an A4
size paper (sequence 2). In these experiments, the distortion in the resultant
mosaic images is evaluated quantitatively to see if the perspective distortionis removed by the proposed method. The last experiment is performed on a
picture scroll, approximately 440 cm long (sequence 3).

2.6.1 Experiment on Synthetic Data
In this experiment, extrinsic camera parameters are estimated by applying
the proposed method to synthetic data, and the accuracy of the estimation
is evaluated by comparing the estimated parameters with the ground truth.
From this experimental result, the optimal speed described in Section 2.5.1 isdetermined.
First, in order to generate synthetic feature tracks, a simulation is carriedout with a virtual camera that has the same parameters as the camera shownin Table 2.1 and feature points randomly scattered on a virtual mosaic image plane. In this simulation, the virtual camera is moved over the virtual
mosaic image plane at constant speed. In each frame, feature points on themosaic plane are projected onto the virtual camera image. To simulate errors
in feature detection and tracking, Gaussian noise is added to the projected
positions. Finally, by quantitizing the positions to integer, synthetic feature
tracks are obtained.
These synthetic data are generated for diﬀerent camera speed. For eachcamera speed, camera parameters are estimated by the proposed method and30

the errors in camera position and posture is evaluated by comparing the estimated parameters with the ground truth.
The conﬁguration of this simulation is shown in Table 2.2. All these parameters are simulation of typical conﬁguration in real experiments.
The estimation errors in camera position and posture for diﬀerent camera speed are shown in Figure 2.9 (a), (b), respectively. We can see thatthe estimation error monotonously increases as the speed of the camera getsfaster. More speciﬁcally, both errors for camera position and posture drastically increase when the camera speed is faster than 4 mm/frame. On the other
hand, the errors are almost constant when the camera speed is slower than 2
mm/frame. According to these results, the optimal speed for the camera isdetermined to 2 mm/frame.

2.6.2 Experiment on Document (Sequence 1)
As shown in Figure 2.10, the target paper of document is captured as 640×480
images of 120 frames using our system. Note that in every frame, the camera
was tilted backward against the target document, which caused perspective
distortion in every input image. Cross marks in Figure 2.11 indicate featurepoints which are automatically detected and used for extrinsic camera parameter estimation. In this experiment, 94 image feature points are tracked perframe on average. After the real-time stage, reappearing features are detected
and cumulative errors are minimized over the whole input. The number ofdetected reappearing features is 90 in this experiment, and the average reprojection error of the features before and after reﬁnement are 0.88 pixel and 0.73
pixel, respectively.
Figure 2.12 illustrates the acquired extrinsic camera parameters and theTable 2.2. Conﬁguration of simulation.
Distance between camera and mosaic plane 200mm
Average number of detected feature points
90
Average reprojection error
0.8 pixel

31

Estimation error ofcamera position [mm]

1.5
1.2
0.9
0.6
0.3
0
0.1

1

10

Speed of camera motion (mm/frame)

Estimation error ofcamera posture [degree](a) error in position
0.5
0.4
0.3
0.2
0.1
0
0.1

1

10

Speed of camera motion (mm/frame)(b) error in posture
Figure 2.9. Evaluation of camera parameter estimation (simulation).

feature positions on the mosaic image plane after the reﬁnement process. The
curved line shows the estimated camera path and pyramids show the camera
postures in every 10 frames. In Figure 2.12, we can see that the camera
orientations are tilted backward against the target. This coincides with the
conﬁguration of the camera in this experiment.
Finally, a super-resolved mosaic image is generated by 3 iterations of backprojection as shown in Figure 2.13. The size of the image is 2533 × 2920. We
can conﬁrm that perspective distortion has been removed in the ﬁnal mosaic
image. The advantage of our method over homography based methods isobvious when this result is compared with the mosaic image shown in Figure
1.4, which was generated by a homography based method using the same input
images and the same feature tracks as this experiment. Quantitative evaluationof the distortion in the mosaic image will be shown in Section 2.6.5.
32

A close shot of an input image and the corresponding region in superresolved mosaic image are compared in Figure 2.14. As can be seen, texts
which are almost unreadable in the input image are restored in the superresolved mosaic image.
The performance of our system for this sequence is as follows: 9 fps forimage acquisition and initial parameter estimation, 1 second for detecting reappearing features in 120 frames, 27 seconds for camera parameter reﬁnement,
and 240 seconds for generation of super-resolved mosaic image.

2.6.3 Experiment on Photograph (Sequence 2)
As shown in Figure 2.15, the target photograph is captured as 640×480 imagesof 150 frames. Cross marks in Figure 2.16 indicate feature points which areautomatically detected and used for extrinsic camera parameter estimation.
The average number of tracked features is 97 points per frame. After thedetection of 142 re-appearing features, the extrinsic parameters are reﬁned.
The average re-projection error of the features is minimized from 0.84 pixel to0.78 pixel by camera parameter reﬁnement.
Figure 2.17 shows the extrinsic camera parameters and the feature positions
on the mosaic image plane after reﬁnement.
The super-resolved mosaic image after 3 iterations is shown in Figure 2.18.
The size of the image is 2019 × 2758. An input image and the super-resolved
mosaic image are compared in Figure 2.19. As can be seen, the detail structureof the glasses and the face has been restored in the super-resolved mosaic image.
The performance of the system for this sequence is as follows: 9 fps forimage acquisition and initial parameter estimation, 1 second for detecting reappearing features in 120 frames, 10 seconds for camera parameter reﬁnement,
and 220 seconds for super-resolution. Note that the computational time forcamera parameter reﬁnement is much shorter than that for the experiment on
a document. This is caused by the diﬀerence of camera conﬁguration in theﬁrst frame. In this experiment, the camera posture in the ﬁrst frame was set
so as to satisfy the parallel assumption described in Section 2.3.2. This gives agood initial estimate, and thus helps the error function to be minimized more33

quickly in the reﬁnement process.

2.6.4 Experiment on Picture Scroll
In this experiment, a picture scroll, approximately 440 cm long, is captured
as 640 × 480 pixel images of 500 frames. Sampled frames of the captured
images are shown in Figure 2.20. Tracked feature points are depicted withcross marks in Figure 2.21. Figure 2.22 illustrates the estimated extrinsic
camera parameters and the feature positions on the mosaic image plane after
the reﬁnement process. The curved line shows the estimated camera path andpyramids show the camera postures in every 50 frames.
The super-resolved mosaic image is shown in Figure 2.23. The resolutionof the image is 12800 × 1825 pixels. This image resolution was determined by
the limitation of the memory resource in the prototype system.
Despite the long input sequence, our system successfully generates a mosaic
image without perspective distortion. It should be noted that in homography
based method, long input sequence would result in severe perspective distortion, since the perspective distortion tends to increase toward the end of themosaic image. This result also shows the advantage of our method over homography based methods.

2.6.5 Quantitative Evaluation of Distortion
In the experiments on a document and a photograph described in Sections 2.6.2
and 2.6.3, plus marks (+) have been printed on the target papers at every
40mm grid positions. By measuring the distances between every adjacent grid
positions, the distortions in the generated mosaic images are quantitatively
evaluated.
First, the positions of the plus marks on the generated mosaic image are
acquired manually. Then, the distances between adjacent plus marks are thencomputed in the unit of pixel. The average, maximum, minimum and standard
deviation of the distances are shown in Table 2.3. The percentage of each value
against the average distance is also shown in parenthesis. Here, the standard
34

deviation can be considered as the average distortion in the mosaic image, andit was only 0.68% and 0.62 for a document and a photograph, respectively.
With these results, we can conclude that perspective distortion in the mosaic
images has been successfully removed by the proposed method.
Table 2.3. Distances of adjacent grid points in generated mosaic images [pixels(percentage from average)]targetaveragemaximum minimum standard deviation
Document 359.8(100.0) 364.0(100.9) 354.0(98.4)
2.43(0.68)
Photograph 328.6(100.0) 333.0(101.3) 325.0(98.9)
2.06(0.62)

35

1st frame

68th frame

17th frame

85th frame

34th frame

102th frame

51th frame

120th frame

Figure 2.10. Sampled frames of input image sequence (Sequence 1).

36

1st frame

68th frame

17th frame

85th frame

34th frame

102th frame

51th frame

120th frame

Figure 2.11. Tracked features in input image sequence (Sequence 1).

37(a) top view(b) side view
Figure 2.12. Estimated extrinsic camera parameters and feature positions(Sequence 1).
38

Figure 2.13. Generated super-resolved mosaic image (Sequence 1).

39(a) Input original image(b) Super-resolved image
Figure 2.14. Comparison of input image and super-resolved mosaic image(Sequence 1).

40

1st frame

84th frame

21th frame

105th frame

42th frame

126th frame

63th frame

150th frame

Figure 2.15. Sampled frames of input image sequence (Sequence 2).

41

1st frame

84th frame

21th frame

105th frame

42th frame

126th frame

63th frame

150th frame

Figure 2.16. Tracked features in input image sequence (Sequence 2).

42(a) top view(b) side view
Figure 2.17. Estimated extrinsic camera parameters and feature positions(Sequence 2).

43Figure 2.18. Generated super-resolved mosaic image (Sequence 2).

44(a) Input original image(b) Super-resolved image
Figure 2.19. Comparison of input image and super-resolved mosaic image(Sequence 2).

45

1st frame

280th frame

70th frame

350th frame

140th frame

420th frame

210th frame

490th frame

Figure 2.20. Sampled frames of input image sequence (Picture Scroll).

46

1st frame

280th frame

70th frame

350th frame

140th frame

420th frame

210th frame

490th frame

Figure 2.21. Tracked features in input image sequence (Picture Scroll).

47

48
Figure 2.23. Generated mosaic image (Picture Scroll).

Figure 2.22. Estimated extrinsic camera parameters and feature positions (Picture Scroll).

2.7. Conclusion
In this chapter, a perspective distortion-free video mosaicing method for ﬂat
documents is described. In the proposed method, extrinsic camera parameters,
instead of homographies, are estimated for each frame by applying structurefrom motion technique to the captured video. Using estimated extrinsic camera
parameters, the method dewarps all the frame images and synthesizes themon a virtual rectiﬁed image plane to generate a super-resolved mosaic image
without perspective distortion.
A novel user interface for video mosaicing is also proposed. In this userinterface, a preview of the mosaic image under construction is rendered in realtime. In addition to the preview, a speed indicator to guide the user to movethe camera with optimal speed is shown. With this user interface, camera
motion which is not only eﬃcient, but also gives accurate camera parameter
estimation can be easily achieved by the user.
The proposed method, along with the user interface is implemented on a
prototype system. In order to realize real-time processing, a two-stage implementation of the method is employed in the prototype system.
Experiments on ﬂat documents are performed using the prototype system.
In each experiment, the mosaic image has been proved to be distortion-free by
quantitative analysis on distortion. It should also be noted that high resolution
image up to 23M pixels (in the experiment on a picture scroll), which goes
far beyond the resolution of the camera used in the experiments, has been
generated by the proposed method.
The limitation of the method is that it can only be applied to ﬂat documents. In the real world, however, there are many documents with curved
surface, e.g. thick bound book. In the following chapter, the video mosaicing
method is extended to deal with documents with curved surface.

49Chapter 3
Video Mosaicing for Curved
Document
3.1. Introduction
In the previous section, video mosaicing for ﬂat document has been described.
In this chapter, we extend the method to deal with documents with curved
surface. The goal is to generate mosaic images of virtually ﬂattened pages for
documents with curved surface.
In case of curved surface, geometric distortion induced by the curvature of
the target will be present in each input image. In order to generate mosaic
images of virtually ﬂattened pages, this curvature distortion in input images
has to be corrected before blending the input images on a mosaic image plane.
In this method, structure from motion technique is employed to the input
images to estimate extrinsic camera parameters and feature positions, as is in
the method for ﬂat documents. This time, however, 3-D position is estimatedfor each feature, since features no longer lie on 2-D plane but on 3-D surface.
After estimating the shape of the curved surface from the 3-D feature positions,the method dewarps all the frame images and synthesizes them on a mosaic
image plane to generate a virtually ﬂattened image of the curved surface.
Two assumptions are made in this method. One is that the curve of thetarget lies along one direction. The other is that intrinsic camera parameters51are known in advance, and remain ﬁxed throughout image capturing, as is
assumed in the method for ﬂat targets.
In the following sections, ﬁrst, the overview of the methods is given(Section 3.2),
and then we will see how the previous method for ﬂat targets is extended for
curved targets (Section 3.3). After describing the prototype system based on
this method (Section 3.4), experimental results on curved documents is shown(Section 3.5). Finally, the conclusion of this chapter is given (Section 3.6).

3.2. Overview of the Method
The ﬂow of the proposed method is given in Figure 3.1. As can be seen, thewhole process is composed of three processes: initial 3-D reconstruction by
feature tracking (A), parameter reﬁnement and target shape estimation (B)and mosaic image generation (C).
In initial 3-D reconstruction process (A), estimation of extrinsic camera
parameters along with 3-D feature positions on the target is carried out by
tracking image features in the input video. In parameter reﬁnement and target
shape estimation process (B), reappearing features are detected (a), and theinitial estimates of camera parameters and 3-D feature positions are reﬁned
by global optimization (b). Then, surface parameters are estimated by ﬁtting
a parameterized 3-D surface to estimated 3-D feature points (c). These three
process are iterated until convergence. Finally, a geometric distortion-freemosaic image is generated. A postprocess is applied to remove the shade on
the mosaic image (C).
The major diﬀerences between this method and the previous method for
ﬂat targets can be summarized as follows:• Extension to deal with 3-D feature positions instead of 2-D positions(Figure 3.1(A),(a) and (b)).
• Processes speciﬁcally designed for curved surface (Figure 3.1(c) and (B)).
52

(A) Initial 3-D reconstruction by feature tracking(B) Parameter refinement and target shape estimation(a) Detection of reappearing features(b) Global optimization

Iterate untilconvergence(c) Surface fitting to feature points(C) Mosaic image generation
Figure 3.1. Flow diagram of video mosaicing for curved target.

In the following sections, each process in the proposed method is described,
focusing on the extensions described above.

3.3. Extension for Curved Target
3.3.1 Initial 3-D Reconstruction by Feature Tracking
This process is almost identical to the initial estimation of extrinsic camera
parameter for ﬂat targets described in Section 2.3.2, except that 3-D positionis estimated for each feature and that standard extrinsic camera parameter
Mfullf is estimated for each frame.
Let us recall the general deﬁnition of extrinsic camera parameter in Eq. (2.1)
and (2.2):⎛

c1 c3 + s1 s2 s3⎜⎜
Mfullf = ⎝ −s1 c3 + c1 s2 s3
c2 s3

s1 c2
c1 c2
−s2

−c1 s3 + s1 s2 c3
s1 s3 + c1 s2 c3
c2 c3

si = sin (rif ), ci = cos (rif )53(i = 1, 2, 3),

⎞

t1f
⎟
t2f ⎟
⎠,
t3f

(3.1)

(3.2)

where (t1f , t2f , t3f ) are camera position parameters, and (r1f , r2f , r3f ) are camera posture parameters representing yaw, pitch, roll of a camera, respectively.
3-D point Sp = (xp , yp , zp ) is projected to x̂f p = (ûf p , v̂f p ) on the ideal image
coordinate by the following equation:
⎛

⎛

⎞

⎞

xp
⎜
⎟
ûf p
⎜
⎟
⎜
⎟
⎜ yp ⎟⎜⎟⎟,a ⎝ v̂f p ⎠ = Mfullf ⎜⎜ zp ⎟
⎝
⎠
1
1

(3.3)

where a is a parameter. In this process for curved targets, this 3-D coordinate
Sp = (xp , yp , zp ) instead of 2-D coordinate (xp , yp ) is estimated for each featurepoint on the target. Accordingly, Mfullf instead of simpliﬁed Mf for ﬂattarget is estimated.
In the same manner as for ﬂat targets, the process is composed of initialization step for the ﬁrst frame (f = 1), and an iterative step for the subsequent
frames (f > 1). In the ﬁrst frame, assuming that the focal plane in the ﬁrst
frame is parallel to the target and that the distance between the target andthe viewpoint of the camera is d, Mfullf is initialized as follows:⎛⎞

1 0 0 0⎜⎟⎜
Mfull1 = ⎝ 0 1 0 0 ⎟⎠.
0 0 1 −d(3.4)

Based on the same assumption, 3-D position for each feature point p detectedin the ﬁrst frame is given as follows:
⎛

⎞

⎛

⎞

xp
û1p d⎜⎟⎜⎟⎜ y ⎟ = ⎜ v̂ d ⎟ .
⎝ p ⎠⎝ 1p ⎠
0zp(3.5)

Note that these are only initial values, which will be corrected in the reﬁnement
process (Figure 3.1(d)).
Despite these diﬀerences, the process for subsequent frames (f > 1) is thesame as the one for ﬂat targets. Readers are encouraged to refer to Section 2.3.2
for the detail.
54

3.3.2 Detection of Reappearing Features
Reappearing features are detected by the process described in 2.3.3 with anextension to deal with curved surface. The ﬂow of this process is as follows.
First, templates of all the features are projected to the ﬁtted surface (described later) to remove the geometric distortion induced by the curvature of
the target. Then, feature pairs whose distance in 3-D space is less than a given
threshold are selected and tested with the normalized cross correlation function in multiple scales. If the correlation is higher than a certain threshold,the feature pair is regarded as reappearing features and tracks belonging toeach feature are merged into a single track.
The diﬀerence between this process and the process for ﬂat targets in Section 2.3.3 is that templates for features are projected to the ﬁtted surface
instead of the mosaic image plane. This surface, however, is unknown in theﬁrst iteration of steps (a) to (c), since it will be obtained in the later process(c) by ﬁtting a parameterized 3-D surface to estimated 3-D feature points.
Thus, this step will be skipped in the ﬁrst iteration of steps (a) to (c).

3.3.3 Global Optimization
In order to remove cumulative errors in the initial estimates of extrinsic camera
parameters and 3-D feature points, global optimization on these parameters is
carried out by the same process described in Section 2.3.4.
Let us recall the estimation error E deﬁned in Eq. 2.13:
E=

p

f

Ef p .

(3.6)

This error function E is minimized with respect to the camera parameters
Mfullf and the feature positions (xp , yp , zp ) to obtain globally optimized estimates of these parameters.

3.3.4 Target Shape Estimation by Surface Fitting
In this step, assuming the curve of the target lies along one direction, thetarget shape is estimated using 3-D feature points optimized in the previous
55

Vmin: direction of minimum
principal curvatures of the targetm

Vmax: direction of maximum
principal curvatures of the targetndirection of minimum
curvature of Rp
direction of maximum
curvature of Rp

Sp
Rp

N: Normal of projection plane

Plane P
V2

V1: first principal directionof projected points

y = f (x )Projected points
Figure 3.2. Target shape estimation by polynomial surface ﬁtting.

step (b). This step is a process speciﬁcally designed for curved targets.
First, as shown in Figure 3.2, the principal direction of curvature is computed from the 3-D point clouds. Next, 3-D position of each feature pointis projected to a plane perpendicular to the direction of minimum principal
curvatures. Finally, a polynomial equation of variable order is ﬁtted to theprojected 2-D coordinates, and the target shape is estimated. These steps will
be described in detail.
Let us consider for each 3-D point Sp = (xp , yp , zp ) a point cloud Rp which
consists of feature points lying within a certain distance from Sp , as shown56

in Figure 3.2. First, the directions of maximum and minimum curvatures
are computed for each Rp using local quadratic surface ﬁt. For a target whose
curve lies along one direction, as assumed in this paper, the minimum principal
curvature must be 0, and its direction must be the same for all the featurepoints. In practice, however, there exists some ﬂuctuation in the directions ofminimum curvature, due to the estimation errors. Thus, a voting method isapplied to eliminate outliers and to determine the dominant direction Vmin =(vmx , vmy , vmz ) of minimum principal curvatures on the target.
Next, 3-D position Sp for each feature point is projected to a plane whose
normal vector N coincides with Vmin ; i.e. P (x, y, z) = vmx x+vmy y +vmz z = 0.
The projected 2-D coordinate (x̄p , ȳp ) of Sp is given as follows:
⎛

⎞

⎛

⎞

x̄
V1 ⎠
⎝ p ⎠=⎝
Sp ,
ȳp
V2

(3.7)

where V1 is a unit vector parallel to the principle axis of inertia of the projected
2-D coordinates (x̄, ȳ), and V2 is a unit vector which is perpendicular to V1
and Vmin ; i.e. V2 = V1 × N (see Figure 3.2).
Finally, the target shape parameter (a0 , a1 , · · · , am ) is obtained by ﬁtting
the following variable-order polynomial equation to the projected 2-D coordinates (x̄, ȳ).
qȳ = f (x̄) =i=0

ai x̄i .

(3.8)

q which minimize the following criteria G-AIC is determined as the optimalorder. Using geometric AIC [Kan98], the optimal order q in the above equation
is determined as q which minimizes the following criteria:
G-AIC = J + 2(N (m − r) + q + 1)2 ,(3.9)

where J is the residual, N is the number of points, m is the dimension ofobserved data, and r is the number of constraint equations in ﬁtting Eq. (3.8)
to the projected 2-D coordinates. , called noise level, is the average error of
the estimated feature position along ȳ axis. Here, the order q is independentof m, r, N , thus the actual criteria to be minimized is given as follows:
G = J + 2q2 .
57(3.10)

In our method, the noise level  is approximated as follows: = Cl,(3.11)

where l is the average of the depth of each feature point in camera coordinateof every frame, and C is a constant, which is empirically set to 0.007.
In case of a target with multiple curved surfaces, the target is ﬁrst divided
with a line where the normal vector of the locally ﬁtted quadratic surface varies
discontinuously, and then the shape parameter is computed for each part of
the target.
The shape of the target estimated in this step is used for generating a geometric distortion-free mosaic image in the next process, as well as for removing
the geometric distortion in the reappearing feature detection process describedin Section 3.3.2.

3.3.5 Mosaic Image Generation
Finally, a mosaic image is generated by using extrinsic camera parameters andsurface shape parameters. In this step, ﬁrst, a curvature distortion-free, or an
unwrapped mosaic image is generated. Then, a postprocess is applied to themosaic image to remove the shade induced by the curved shape of the target.
Before we describe the actual process for mosaic image generation, we ﬁrst
deﬁne the relationship between the 2-D coordinate on the mosaic image andits corresponding 2-D coordinates on input images. Let us consider a 2-D coordinate (m, n) on the unwrapped mosaic image as shown in Figure 3.2. Here,the relation between (m, n) and its corresponding 3-D coordinate (x̄, f (x̄), z̄)on the ﬁtted surface is given as follows:(m, n) = (

x̄
0

1+{

d
f (x)}2 dx, z̄).
dx

(3.12)The relationship between the 3-D coordinate (x̄, f (x̄), z̄) on the ﬁtted surface
and its corresponding 2-D coordinate (uf , vf ) on the f -th image plane is given58

by the following equation:
⎛

⎞

⎛

⎞⎛

⎞

uf
V1
x̄
⎜
⎟
⎜
⎟⎜
⎟
⎜
⎟
⎜
⎟
⎜
a ⎝ vf ⎠ = Mfullf ⎝ V2 ⎠ ⎝ f (x̄) ⎟
⎠,
z̄
1
N

(3.13)

where a is a parameter.
Now that we know the relationship between the 2-D coordinate (m, n)on the mosaic image and its corresponding 2-D coordinates (uf , vf ) on input
images, the mosaic image can be generated as follows. First, for each pixel(m, n) on the unwrapped mosaic image, the corresponding coordinate (uf , vf )in each input image is computed by Eq. (3.12) and (3.13). Then, the averageof the pixel values at all the corresponding coordinates is computed, and isdetermined as the pixel value at (m, n) on the unwrapped mosaic image. As
shown in Figure 3.3, the resolution of the target captured in the input image
decreases as the angle formed by the surface normal and the line from thetarget to the focal point of the camera, depicted by θf , increases. Thus, in thecomputation of the average of the pixel values, each pixel value is weighted
according to θf .
The concrete formulation of the computation of I(m, n), the pixel value at(m, n) on the unwrapped mosaic image is given as follows:I(m, n) =1
f Wf

Wf = K −θf ,Wf If (uf , vf ),(3.14)

f(3.15)

where If (uf , vf ) is the corresponding pixel value at (uf , vf ) in the f -th input
image, K is a constant which is empirically set to 104 , and θf is the angle
formed by the surface normal at (x̄, f (x̄), z̄) and the line from (x̄, f (x̄), z̄) to
the focal point in the f -th frame.
After the unwrapped mosaic image is generated by the above process, a
postprocess is applied to remove the shade on the mosaic image induced by
the curved shape of the target. Here, the following assumptions are made:the target is a Lambertian surface with the background having the maximum
intensity on the target, and the target is illuminated by a parallel light source.
59

surface
normalθf( x , f ( x ), z )target surface
Figure 3.3. Angle formed by surface normal and camera orientation.

As is described in Section 3.3.4, the vertical direction in the mosaic image
coordinate (m, n) is deﬁned to coincide with the direction of the minimum
principle curvature of the target. Thus, under a parallel light source, the eﬀect
of shade is uniform for pixels having the same m coordinate on the mosaic
image. If we can assume that, in any column of the mosaic image, there exists
at least one pixel belonging to the background, the true pixel value Inew (m, n)
without shade can be computed by the following equation:
Inew (m, n) =Imax I(m, n),max(I(m + u, n + v); ∀(u, v) ∈ W )(3.16)

where W is a rectangular window whose height is larger than its width, e.g.
a window with the size of 5 × 500 pixel, and Imax is the maximum possible
intensity value of an image (typically 255).

3.4. Prototype System for Curved Document
This method for curved document has been developed on a prototype system.
The system is composed of a laptop PC and a hand-held IEEE1394 CCD
camera, whose intrinsic parameters are calibrated by Tsai’s method [Tsa86] in60

advance, and are ﬁxed during the image capturing. The speciﬁcations of thesystem are shown in Table 3.1.
To enable real-time processing, two stage implementation is employed again.
In the real-time stage, while the user captures a target document using a handheld camera, initial 3-D reconstruction by feature tracking is carried out. The
rest of the processes, i.e. detection of reappearing features, global optimization, surface ﬁtting and mosaic image generation is executed in the oﬄine
stage.
Experiments performed by this prototype system is described in the following section.
Table 3.1. Speciﬁcations of a video mosaicing system for curved target.
Laptop PC
CPU
Pentium-M 2.1GHz
Memory2GBIEEE1394 camera (Aplux C104T)
Resolution
640×480 pixels
View angle
31.7◦ × 24.1◦
Maximum frame rate
15 frames/sec

61

3.5. Experiments
Two experiments are performed by the prototype video mosaicing system toevaluate the feasibility of the proposed method. The ﬁrst experiment is performed on a thick bound book with two pages of curved surface, shown in
Figure 3.4 (sequence 1). The distortion in the resultant mosaic images is evaluated quantitatively in the same manner with the experiments on ﬂat targets
in Section 2.6. The second experiment is performed on a label on a wine bottle
shown in Figure 3.5 (sequence 2).

3.5.1 Experiment on Book (Sequence 1)
The target document captured in this experiment is shown in Figure 3.4. The
target is a thick bound book composed of 2 pages of curved surfaces: one page
with texts and the other with pictures and ﬁgures. Plus marks (+) are printed
on both pages at every 40mm grid positions for quantitative evaluation.
The target is captured as 640 × 480 pixel images of 300 frames. Sampled
frames of the captured images are shown in Figure 3.6. Cross marks in Figure 3.7 indicate feature points which are automatically detected and used for
extrinsic camera parameter estimation.
3-D reconstruction result obtained by the proposed method is shown in
Figure 3.8. The curved line shows the camera path, pyramids show the camera
postures in every 10 frames, and the point cloud shows 3-D positions of featurepoints. As can be seen, the point cloud coincides with the shape of the thickbound book.
The shape of the target is estimated after 3 time iterations of reappearing feature detection and surface ﬁtting process. The estimated shape of thetarget is shown in Figure 3.9. In the proposed method, the optimal order ofthe polynomial surface ﬁtted to the target is automatically determined by geometric AIC [Kan98]. In this experiment, the order is 5 and 4 for the left andright pages, respectively.
The unwrapped mosaic images before and after removing shade are shownin Figure 3.10 and 3.11, respectively. The resolution of the mosaic image is62Figure 3.4. Thick bound book with curved surface (Sequence 1).

Figure 3.5. Label on a wine bottle (Sequence 2).

3200 × 2192. As can be seen, the distortion on the target has been removed
in the resultant image. Quantitative evaluation of the distortion in the mosaic
images will be given in Section 3.5.3.
The performance of our system in this experiment is as follows: 22 seconds
for initial 3-D reconstruction, 188 seconds for camera parameter reﬁnement
and surface ﬁtting and 410 seconds for generating the ﬁnal mosaic image.

63

3.5.2 Experiment on Label on Wine Bottle (Sequence 2)

The target in this experiment is a label on a wine bottle, as shown in Figure 3.5.
This target is composed of drawings and few lines of texts. Some of them, e.g.
the contour of the label, the text line which says “TYRRELL’S WINES”, arecurved by design. This makes it diﬃcult for conventional distortion correction
methods to perform successfully, since they assume that bunches of straightlines are present in the document.
The target is captured as 640 × 480 pixel images of 100 frames. Sampled
frames of the captured images are shown in Figure 3.12. Cross marks in
Figure 3.13 indicate feature points which are automatically detected and used
for extrinsic camera parameter estimation.
3-D reconstruction result obtained by the proposed method is shown in
Figure 3.14. The curved line shows the camera path, pyramids show the camera
postures in every 10 frames, and the point cloud shows 3-D positions of featurepoints.
The shape of the target is estimated after 3 time iterations of reappearing
feature detection and surface ﬁtting process. The estimated shape of the target
is shown in Figure 3.15. In this experiment, the optimal order of the polynomial
surface ﬁtted to the target is 2.
The unwrapped mosaic images is shown in Figure 3.16. The resolution of
the mosaic image is 3200 × 2343. The process for removing shade describedin 3.3.5 has not been applied for this target, since specular reﬂection has been
observed in the input images.
It should be noted that, although the target had few lines structures, someof which are not even straight, the distortion has been successfully removed by
the method. This result shows the advantage of our method over conventional
distortion correction methods which rely on bunches of straight lines in adocument.
643.5.3 Quantitative Evaluation of Distortion
We evaluate the distortion in the mosaic image generated for a book (Figure 3.11 using the same method as described in Section 2.6.5.
For each page, the distortion in the mosaic image is evaluated by the distances between every pair of adjacent plus marks (+). The average, maximum,
minimum and standard deviation of the distances are shown in Table 3.2. The
percentage of each value against the average distance is shown in parenthesis.
In this experiment, the average distortion is 1.11% and 0.81% for the left
and right page, respectively. It should be noted that the method performed
equally well on both pages, regardless to their content. However, the maximum
distortion of 2.8% and 2.2%, which are relatively large, are obtained for theleft and right page, respectively. These large distortions are observed in thearea close to the boundary between both pages. The reason for this is that,in this area, the angle formed by the surface normal and the optical axis of
the camera is nearly 90 degrees, which causes error in feature tracking andthus degrades the accuracy of 3-D reconstruction. This is the drawback of our
method which carries out 3-D reconstruction by feature points. Utilizing othertypes of image feature, e.g. line and arc segments, besides feature points canbe a promising solution for this problem.
Table 3.2. Distances of adjacent grid points on the mosaic image [pixels (percentage from ave.)] (Book).
page
averagemaximum
minimum
std. dev.
left 338.5(100.0) 348.0(102.8) 331.0(97.8) 3.77(1.11)
right 337.6(100.0) 345.0(102.2) 331.1(98.1) 2.75(0.81)

65

1st frame

112nd frame

28th frame

140th frame

56th frame

168th frame

84th frame

200th frame

Figure 3.6. Sampled frames of input image sequence (Sequence 1).

66

1st frame

112nd frame

28th frame

140th frame

56th frame

168th frame

84th frame

200th frame

Figure 3.7. Tracked features in input image sequence (Sequence 1).

67(a) frontal view(b) side view
Figure 3.8. Estimated extrinsic camera parameters and 3-D positions of features (Sequence 1).

68Figure 3.9. Target shape estimated from 3-D feature points (Sequence 1).

69

70

Figure 3.10. Unwrapped mosaic image before shade correction(Sequence 1).

71

Figure 3.11. Unwrapped mosaic image after shade correction(Sequence 1).

1st frame

58nd frame

15th frame

72th frame

29th frame

86th frame

43th frame

100th frame

Figure 3.12. Sampled frames of input image sequence (Sequence 2).

72

1st frame

58nd frame

15th frame

72th frame

29th frame

86th frame

43th frame

100th frame

Figure 3.13. Tracked features in input image sequence (Sequence 2).

73

(a) frontal view(b) side view
Figure 3.14. Estimated extrinsic camera parameters and 3-D positions of features (Sequence 2).

74Figure 3.15. Target shape estimated from 3-D feature points (Sequence 2).

75

76
Figure 3.16. Unwrapped mosaic image (Sequence 2).

3.6. Conclusion
In this chapter, a geometric distortion-free video mosaicing method for curved
documents is described. In the proposed method, extrinsic camera parameters,
along with 3-D feature positions are estimated by applying structure frommotion technique to the captured video. By ﬁtting a parameterized surface
to the 3-D features, the shape of the curved document is estimated. Using
the estimated shape and extrinsic camera parameters, all the frame images
are dewarped and synthesized on a virtual plane to generate a mosaic image
without curvature distortion.
A prototype system based on the proposed method has been developed, andis tested in experiments on documents with curved surface. Quantitative evaluation on distortion shows that the resultant mosaic image is distortion-free.
The advantage of the proposed method over conventional distortion correction
using text-lines has been shown in the experiment on a document with few
texts.
The limitation of the method is that, since it carries out 3-D reconstruction by feature points, the accuracy of 3-D reconstruction is degraded in theboundary between pages in a bound book, which results in distortion in thisarea. Utilizing other types of image feature, e.g. line and arc segments, besides
feature points can be a promising solution for this problem. Considering photoconsistency among pixels which fall onto to the same coordinate on the mosaic
image can further improve the accuracy of 3-D reconstruction.

77

Chapter 4
Conclusion
In this thesis, a novel video mosaicing method which is capable of generating
a geometric distortion-free mosaic image has been presented.
In general, video mosaicing is prone to two types of distortion. One isperspective distortion, which appears when the target document is not frontoparallel to the camera’s image plane. The other is curvature distortion, whichis caused by projecting curved surface of the target document to the image
plane of the camera.
This thesis ﬁrst focused on a ﬂat document, and proposed a perspective
distortion-free video mosaicing method for ﬂat documents. In this method,
extrinsic camera parameters are estimated for each frame by applying structurefrom motion technique to the captured video. Using estimated extrinsic camera
parameters, the method dewarps all the frame images and synthesizes themon a virtual fronto-parallel plane to generate a super-resolved mosaic image
without perspective distortion. A novel user interface to guide the user tocapture video sequence which gives eﬃcient and accurate camera parameter
estimation has also been proposed. Experiments on ﬂat documents have been
performed using a prototype system. In each experiment, the mosaic image
has been proved to be distortion-free by quantitative analysis on distortion.
High resolution image up to 23M pixels, which goes far beyond the resolutionof the camera, has been generated by the proposed method.
Then, this method for ﬂat documents was extended to deal with curved doc79

uments. This extended method generates a virtually ﬂattened mosaic imageof a curved surface. In this method, ﬁrst, extrinsic camera parameters, alongwith 3-D feature positions are estimated by structure from motion. Then, by
ﬁtting a parameterized surface to the 3-D features, the shape of the curved
document is estimated. Using the estimated shape and extrinsic camera parameters, all the frame images are dewarped to remove curvature distortionand synthesized on a virtual plane to generate a mosaic image without curvature distortion. This method was also tested in experiments on documentswith curved surface. Quantitative evaluation on distortion has shown that theresultant mosaic image is distortion-free.
This work diﬀers from previous works in document digitization in that it
does not require any special hardware equipment besides a video camera. This
makes the method suitable for mobile solution, and is one step forward toubiquitous document digitization.
The limitation of the method is that, since it carries out 3-D reconstruction by feature points, the accuracy of 3-D reconstruction is degraded in theboundary between pages in a bound book, which results in distortion in thisarea. Utilizing other types of image feature, e.g. line and arc segments, besides feature points can be a promising solution for this problem. Considering
photo consistency among pixels which fall onto to the same coordinate on themosaic image can further improve the accuracy of 3-D reconstruction. This
will remain as a future work in this study.
Another future work is the reduction of the computational time in the ofﬂine stage. Implementation on GPUs is expected to reduce the computationaltime drastically, since they allow parallel processing.

80References[BCR02]U. Bhosle, S. Chaudhuri, and S.D. Roy. A Fast Method for Image
Mosaicing Using Geometric Hashing. IETE J. of Research, Special
Issue on Visual Media Processing, Vol. 48, No. 3-4, pp. 317–324,
2002.

[BK02]

S. Baker and T. Kanade. Limits on super-resolution and how tobreak them. IEEE Trans. Pattern Analysis and Machine Intelligence, Vol. 24, No. 9, pp. 1167–1183, 2002.

[BS01]

M.S. Brown and W.B. Seales. Document Restoration Using 3D
Shape: A General Deskewing Algorithm for Arbitrarily Warped
Documents. In Proc. IEEE Int. Conf. on Computer Vision, Vol.
2, pp. 367–374, 2001.

[BT04]

M.S. Brown and Y.C. Tsoi. Undistorting Imaged Print Materials
using Boundary Information. In Proc. Asian Conf. on Computer
Vision, Vol. 1, pp. 551–556, 2004.

[CDL03]

H. Cao, X. Ding, and C. Liu. A Cylindrical Surface Model to
Rectify the Bound Document Image. In Proc. IEEE Int. Conf. on
Computer Vision, Vol. 1, pp. 228–233, 2003.

[CKH+ 98] N. Chiba, H. Kano, M. Higashihara, M. Yasuda, and M. Osumi.
Feature-based Image Mosaicing. In Proc. IAPR Workshop on Machine Vision Applications, pp. 5–10, 1998.
81

[CZ00]

D. Capel and A. Zisserman. Super-resolution enhancement of text
image sequence. In Proc. IAPR Int. Conf. on Pattern Recognition,
Vol. 1, pp. 600–605, 2000.

[FB81]

M.A. Fischler and R.C. Bolles. Random Sample Consensus: A
Paradigm for Model Fitting with Applications to Image Analysis
and Automated Cartography. Communications of the ACM, Vol.
24, No. 6, pp. 381–395, 1981.

[GS03]

P. Grattoni and M. Spertino. A Mosaicing Approach for the Acquisition and Representation of 3D Painted Surfaces for Conservation
and Restoration Purpose. Machine Vision and Applications, Vol.
15, No. 1, pp. 1–10, 2003.

[HCBH00] C.T. Hsu, T.H. Cheng, R.A. Beuker, and J.K. Hong. Featurebased Video Mosaicing. In Proc. IEEE Int. Conf. on Image Processing, Vol. 2, pp. 887–890, 2000.
[HS88]

C. Harris and M. Stephens. A combined corner and edge detector.
In Proc. Alvey Vision Conf., pp. 147–151, 1988.

[IP91]

M. Irani and S. Peleg. Improving Resolution by Image Registration. CVGIP: Graphical Models and Image Processing, Vol. 53,
No. 3, pp. 231–239, 1991.

[JKH02]

K. Jung, K.I. Kim, and J.H. Han. Text extraction in real scene
images on planar planes. In Proc. IAPR Int. Conf. on Pattern
Recognition, pp. 469–472, 2002.

[Kan98]

K. Kanatani. Geometric Information Criterion for Model Selection. Int. J. of Computer Vision, Vol. 26, No. 3, pp. 171–189,
1998.

[KH03]

D.W. Kim and K.S. Hong. Fast Global Registration for Image
Mosaicing. In Proc. IEEE Int. Conf. on Image Processing, Vol. 2,
pp. 295–298, 2003.
82

[LDD05]

J. Liang, D. DeMenthon, and D. Doermann. Unwarping images ofcurved documents using global shape optimization. In Proc. Int.
Workshop on Camera-based Document Analysis and Recognition,
pp. 25–29, 2005.

[LDD06]

J. Liang, D. DeMenthon, and D. Doermann. Camera-Based Document Image Mosaicing. In Proc. IAPR Int. Conf. on Pattern
Recognition, pp. 476–479, 2006.

[LQST01]

M. Lhuillier, L. Quan, H. Shum, and H.T. Tsui. Relief Mosaicing
by Joint View Triangulation. In Proc. IEEE Int. Conf. on Computer Vision and Pattern Recognition, vol. 1, pp. 785–790, 2001.

[MBLH01] G.K. Myers, R.C. Bolles, Q.T. Luong, and J.A. Herson. Recognition of text in 3-D scenes. In Proc. Symposium on Document
Image Understanding Technology, pp. 85–99, 2001.
[MJ02]

P.F. McLauchlan and A. Jaenicke. Image Mosaicing Using Bundle
Adjustment. Image and Vision Computing, Vol. 20, pp. 751–759,
2002.

[PBCP96] W. Puech, A.G. Bors, J.M. Chassery, and I. Pitas. Mosaicingof Paintings on Curved Surfaces. In Proc. IEEE Workshop on
Applications of Computer Vision, pp. 44–49, 1996.
[Pil01]

M. Pilu. Undoing Paper Curl Distortion Using Applicable Surfaces. In Proc. IEEE Conf. on Computer Vision and Pattern
Recognition, Vol. 1, pp. 67–72, 2001.

[Rot00]C. Rother. A new approach for vanishing point detection in architectural environments. In Proc. British Machine Vision Conf.,
Vol. 1, pp. 382–391, 2000.

[SHK98]

H. S. Sawhney, S. Hsu, and R. Kumar. Robust Video Mosaicing
through Topology Inference and Local to Global Alignment. In
Proc. European Conference on Computer Vision, Vol. 2, pp. 103–
119, 1998.
83

[SKYT02] T. Sato, M. Kanbara, N. Yokoya, and H. Takemura. Dense 3-D
Reconstruction of an Outdoor Scene by Hundreds-baseline Stereo
Using a Hand-held Video Camera. In Int. J. of Computer Vision,Vol. 47, No. 1-3, pp. 119–129, 2002.
[Sze94]R. Szeliski. Image Mosaicing for Tele-Reality Applications. In
Proc. IEEE Workshop on Applications of Computer Vision, pp.
230–236, 1994.

[TMHF99] B. Triggs, P. McLauchlan, R. Hartley, and A. Fitzgibbon. Bundle
adjustment a modern synthesis. In Proc. Int. Workshop on Vision
Algorithms, pp. 298–372, 1999.
[Tsa86]

R.Y. Tsai. An eﬃcient and accurate camera calibration techniquefor 3d machine vision. In Proc. IEEE Conf. on Computer Vision
and Pattern Recognition, pp. 364–374, 1986.

[TSTT00] S. Takeuchi, D. Shibuichi, N. Terashima, and H. Tominage. Adaptive Resolution Image Acquisition Using Image Mosaicing Technique from Video Sequence. In Proc. IEEE Int. Conf. on Image
Processing, vol. 1, pp. 220–223, 2000.
[YKKM04] A. Yamashita, A. Kawarago, T. Kaneko, and K. Miura. Shape Reconstruction and Image Restoration for Non-ﬂat Surfaces of Documents with a Stereo Vision System. In Proc. IAPR Int. Conf. on
Pattern Recognition, Vol. 1, pp. 482–485, 2004.

84

List of Publications
Journal Papers
1. A. Iketani, A. Nagai, Y. Kuno, and Y. Shirai. Real-time surveillancesystem detecting persons in complex scenes. Real-Time Imaging, Vol. 7,
No. 5, pp. 433-446, Oct. 2001.
2. A. Iketani, T. Sato, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya.
Super-Resolved Video Mosaicing for Documents by Camera Parameter
Estimation. Transactions of the Institute of Electronics, Information andCommunication Engineers of Japan, Vol. J88-D-II, No. 8, pp. 14901498, Aug. 2005 (in Japanese) (Chapter 2).
3. T. Sato, A. Iketani, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya.
Video Mosaicing for Curved Documents Based on Structure from Motion.
Transactions of the Institute of Electronics, Information and Communication Engineers of Japan, Vol. J90-D, No. 8, pp. 1900-1911, Aug. 2007
(in Japanese) (Chapter 2).

Technical Letters
1. T. Sato, A. Iketani, S. Ikeda, M. Kanbara, N. Nakajima, N. Yokoya,
and K. Yamada. High-resolution Video Mosaicing for Documents by
Estimating Camera Parameters. Information Technology Letters, Vol.
2, pp. 163-164, Sep. 2003 (in Japanese) (Chapter 2).
85

2. A. Iketani, T. Sato, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya.
Super-Resolved Video Mosaicing Based on Camera Parameter Estimation. Information Technology Letters, Vol. 3, pp. 165-168, Sep. 2004 (inJapanese) (Chapter 2).

International Conferences
1. A. Iketani, A. Nagai, Y. Kuno, and Y. Shirai. Detecting persons onchanging background. In Proc. IAPR Int. Conf. on Pattern Recognition, pp. 74-76, Aug. 1998.
2. A. Iketani, Y. Kuno, N. Shimada, and Y. Shirai. Real-Time Surveillance
System Detecting Persons in Complex Scenes. In Proc. Int. Conf. on
Image Analysis and Processing, pp. 1112-1115, Sep. 1999.
3. T. Sato, S. Ikeda, M. Kanbara, A. Iketani, N. Nakajima, N. Yokoya, andK. Yamada. High-resolution video mosaicing for documents and photos
by estimating camera motion. In Proc. SPIE Electronic Imaging, Vol.
5299, pp. 246-253, Jan. 2004 (Chapter 2).
4. A. Iketani, T. Sato, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya.
Super-resolved video mosaicing for documents by extrinsic camera parameter estimation. In Proc. Int. Conf. on Computer Vision andGraphics, pp. 327-336, Sep. 2004 (Chapter 2).
5. A. Iketani, T. Sato, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya.
Video mosaicing for curved surface by 3D reconstruction using featurepoints. In CD-ROM Proc. IEEE Int. Conf. on Computer Vision(ICCV2005), Demonstrations, Oct. 2005 (Chapter 3).
6. A. Iketani, T. Sato, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya.
Super-resolved video mosaicing for documents based on extrinsic camera parameter estimation. In Proc. Asian Conf. on Computer Vision(ACCV2006), Vol. 2, pp. 101-110, Jan. 2006 (Chapter 2).
86

7. T. Sato, A. Iketani, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya.
Mobile video mosaicing system for ﬂat and curved documents. In Proc.
Int. Workshop on Mobile Vision (IMV2006), pp. 78-92, May 2006
(Chapter 2, 3).
8. A. Iketani, T. Sato, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya.
Video mosaicing for curved documents based on structure from motion.
In Proc. IAPR Int. Conf. on Pattern Recognition (ICPR2006), Vol. 4,
pp. 391-396, Aug. 2006 (Chapter 3).
9. T. Sato, A. Iketani, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya.
Video mosaicing for curved documents by structure from motion. In
ACM SIGGRAPH2006, Sketches, Aug. 2006 (Chapter 3).
10. A. Iketani, T. Sato, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya.
Video mosaicing based on structure from motion for distortion-free document digitization. In Proc. Asian Conf. on Computer Vision (ACCV2007),Vol. 2, pp. 73-84, Nov. 2007 (Chapter 3).

Domestic Conferences
1. A. Iketani and M. Hashimoto. Person Extraction and Shadow Elimination Using Background Subtraction of Color and Edges. In Proc.
the 2000 Institute of Electronics, Information and Communication Engineers, General Conference, No. D-12-133, Mar. 2000 (in Japanese).
2. A. Iketani, N. Nakajima, R. Hiraike, and K. Yamada. Multiple NonRigid Object Tracking Using Backward Region Classiﬁcation. In Proc.
the 2003 Institute of Electronics, Information and Communication Engineers, General Conference, No. D-12-139, Mar. 2003 [IEICE Young
Researcher’s Award] (in Japanese).
3. A. Iketani, N. Nakajima, T. Sato, S. Ikeda, M. Kanbara, N. Yokoya,
and K. Yamada. Video Mosaicing and Superresolution with Handheld
Camera. In Proc. Forum on Information Technology (FIT2003), Vol.
87

3, No. I-028, Sep. 2003 [FIT Young Researchers Award] (in Japanese)(Chapter 2).
4. A. Iketani, N. Nakajima, T. Sato, S. Ikeda, M. Kanbara, N. Yokoya, andK. Yamada. Video Mosaicing and Super Resolution for Documents by
Camera Parameter Estimation. In Technical Report of the Institute ofElectronics, Information and Communication Engineers of Japan, Pattern Recognition and Media Understanding (PRMU), PRMU2003-223,
pp. 49-54, Feb. 2004 [PRMU Award] (in Japanese) (Chapter 2).
5. A. Iketani, N. Nakajima, T. Sato, S. Ikeda, M. Kanbara, N. Yokoya,
and K. Yamada. Super-Resolution Video Mosaicing for Documents by
Camera Parameter Estimation. In Proc. Meeting on Image Recognition
and Understanding (MIRU2004), Vol. 1, pp. 505-510, July 2004 (inJapanese) (Chapter 2).
6. T. Sato, A. Iketani, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya.
Super-resolved Video Mosaicing for Plane Objects by Extrinsic Camera
Parameter Estimation. In Proc. Symposium on Pattern Measurement,
pp. 13-20, Nov. 2004 (in Japanese) (Chapter 2).
7. T. Sato, A. Iketani, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya.
Video Mosaicing for Curved Surface by 3-D Reconstruction Using Feature Points. In Proc. the 2005 Institute of Electronics, Information andCommunication Engineers, General Conference, No. D-12-12, Mar. 2005
(in Japanese) (Chapter 3).
8. T. Sato, A. Iketani, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya.
Super-Resolution Video Mosaicing for Documents by Camera Parameter
Estimation. In Proc. Meeting on Image Recognition and Understanding(MIRU2005), pp. 1638-1639, Jul. 2005 (in Japanese) (Chapter 2).
9. T. Sato, A. Iketani, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya.
Video Mosaicing for Curved Surface Based on Structure from Motion. In
88Technical Report of the Institute of Electronics, Information and Communication Engineers of Japan, Pattern Recognition and Media Understanding (PRMU), PRMU2005-203, pp. 7-12, Feb. 2006 (in Japanese)(Chapter 3).
10. T. Sato, A. Iketani, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya.
Video Mosaicing for Curved Documents Based on Structure from Motion.
In Proc. Meeting on Image Recognition and Understanding (MIRU2006),
pp. 98-105, Jul. 2006 (in Japanese) (Chapter 3).

Awards
1. Young Researcher’s Award of Institute of Electronics, Information andCommunication Engineers (IEICE), 2003.
2. Young Researcher Award of Forum on Information Technology (FIT),
2003.
3. Award of Pattern Recognition and Media Understanding (PRMU), 2004.

89