Structure from motion
for omnidirectional multi‐
multi‐camera
system and its applications
Vision and Media Computing Lab.
Graduate School of Information Science
Nara Institute of Science and Technology (NAIST)

Tomokazu Sato

Applications of omnidirectional
video using 3‐
3‐D structure

Overview of this talk
SFM and PnP for multi-camera system
SFM (Structure from motion)
PnP (Perspective n point) problem

GPS integration to SFM
Applications of omnidirectional SFM

Visual‐SLAM (online SFM) andVisual‐its application for video mosaic(1) OmniOmni--directional teletelepresence system without
invisible area
(2) NovelN
Novell-view
isynthesisth i fromfomni--directional video using aomni
deformable 33--D mesh model(3) Feature landmark based
marker--less augmented realitymarker* T. Sato, A. Iketani, S. Ikeda, M. Kanbara, N. Nakajima, and N. Yokoya: ‘Video
mosaicing for curved documents by structure from motion’, ACM SIGGRAPH2006,Sketches, Aug. 2006.

SFM and Reprojection error

PnP problem and Reprojection error

World coordinate system
Extrinsic camera parameter M

3D coordinate offeature pointunknown

unknownx p ' = (u ' , v' )x p = (u, v)

Sum of re-projection errors: E = ∑ | x p '− x p |2→ minp

Multiple images are necessary to solve this problem.

S p = ( x, y , z )2D projection of S pknown

x p ' = (u ' , v' )Cameracoordinate
systemDetected Position of p

3D coordinate offeature point

unknownS p = ( x, y , z )2D projection of S p

Cameracoordinate
systemWorld coordinate system
Extrinsic camera parameter M

Detected Position of px p = (u, v)

Sum of re-projection errors: E = ∑ | x p '− x p |2→ minp

Single images is sufficient to solve this problem.

1

Extrinsic camera parameter estimation(PnP and SFM)

Extrinsic camera parameter estimation(PnP and SFM)

• PnP problem (Perspective n Point problem)• PnP problem (Perspective n Point problem)

is for pairs of known 3-D positions and their 2-D observations.

is for pairs of known 3-D positions and its 2-D observation.

• Algebraic solution with minimum features (P3P, P4P, etc)
• Linear solution for arbitral number of features (PnP)• Non-linear minimization of reprojection errors• Algebraic solution with minimum features (P3P, P4P, etc)
• Linear solution for arbitral number of features (PnP)• Non-linear minimization for reprojection errors(Forfinal refinement,refinement
it needs good initial guess)
Solution for multi
multi‐cameracamerasystem(For final refinement,refinement it needs good initial guess)• SfM (Structure from Motion)• SfM (Structure from Motion)is for unknown 3-D positions and their 2-D observations.

is for unknown 3-D positions and its 2-D observation.

• Factorization-based method (For video, batch processing)• Visual-SLAM (For video, real-time)• Ego-motion estimation (For sufficiently long baseline image pairs)• Non-linear minimization of reprojection errors• Factorization-based method (For video, batch processing)• Visual-SLAM (For video, real-time)• Ego-motion estimation (For sufficiently long baseline image pairs)• Non-linear minimization of reprojection errors(For final refinement, it needs good initial guess)(For final refinement, it needs good initial guess)

Extension with GPS

Linear solution for PnP problem
in OMS (1/2)

Basic strategy for visualvisual‐‐SLAM
Given 3-D positions of features(Reference points)

Feature tracking
Camera parameter
estimation solving PnP
Camera unitsof OMS

3-D position updatefor image features
Camera positions and postures(Camera parameters)

Iterate for each frame

We minimize distances between projecting lines and 3‐
3‐D
position of features instead of reprojection errors.

Bundle adjustment
9Linear solution for PnP problem
in OMS (2/2)

10

Tracking of image features withreference points

They can be computedfrom observations* Tomokazu Sato, S. Ikeda, and N. Yokoya ‘Extrinsic camera parameter recovery
from multiple image sequences captured by an omni-directional multi-camerasystem’, Proc. ECCV, May. 2004.

2

Estimated camera path

In case 3D reference points
are unavailable
Feature tracking
Camera parameter
estimation solving
g PnP
3-D position updatefor image features
3D positions of features
are initialized as they
are on the sphere.

Tracking of image features without
reference points

Overview of this talk
SFM and PnP for multi-camera system
SFM (Structure from motion)
PnP (Perspective n point) problem

Local bundle adjustment
Iterate for each frame

Global bundle adjustment

14

Estimated camera path
without 3D reference points

Extension of SFM

Camera parameter estimationfrom video images andaccuracy
y considered GPS

GPS integration to SFM
Applications of omnidirectional SFM

Hideyuki Kume,
Tomokazu Sato,
Sato, Naokazu Yokoya* ‘Extrinsic camera parameter estimation using video images and GPS
considering GPS positioning accuracy’, Proc. ICPR2010, Aug. 2010
(accepted, to apper)3

How should we design
the penalty term for GPS data?

Extension of objective function
Penalty term for GPS positioning is added to objective function.
E = ∑ Φ i + ω ∑ Ψii∈F

Reprojection error

F : Group of input frames
Fg : Group of frames in which

Penalty term for
GPS positioning1
Φi =∑ μ j (qij − qˆij ) 2
Pi j∈Pi

Red axis：East, Green axis：South, Blue axis：Vertical upω : weighti∈Fg

GPS data is acquired

Pi ：Group of feature points
tracked in the i -th frame
μ j ：Confidence of feature j

Camera coordinate system
Feature j
Projected position ：q̂ij

Detected position：19qijqij − qˆij

Acquired positions in RTK-fix mode
Length of axe：1 [m]1122xi + yi )2n + (zi )2n,r( p)h( p)Acquired positions in RTK-float mode
Length of axe：10 [m]Assumption of normal distribution for GPS error in not effective
20for random walking errors for short time video streams.

Penalty term for GPS positioning
Ψi = (Positions are measured in fixed position using RTK‐GPS(TOPCON GR‐3) for 5 hours⎛ xi ⎞⎜ ⎟⎜ yi ⎟−1⎜ z ⎟ = M i d − gi .
⎜ i⎟⎜1⎟⎝ ⎠Estimated camera paths

n :Large given number
p : Confidence of GPS

Large number, if GPS is outside the cylinder

Ψi =Almost 00, otherwise

GPS coordinate systemz

Camera coordinate system

Miy (East)

x (South)GPS position in
GPS coordinate system： gi

GPS position incamera coordinate system： d2h( p)21M i−1d − gir ( p)Quantitative evaluation：Proposed method：Compared method [Anai et al., 09]
Pyramid ：Camera posture：Acquired GPS positions：Ground truth：RTK-fix：RTK-float
22

Overview of this talkPosition error [m]A: Vision only
B: Vision + GPS [Yokochi 06]
w/o confidence info.
with normal distribution
C: Vision + GPS [Anai 09]
with confidence info.
and normal distribution

Position error [mm]Frame number

SFM and PnP for multi-camera system
SFM (Structure from motion)
PnP (Perspective n point) problem

GPS integration to SFM

D: Proposed method

3500.03000.02500.0Applications of omnidirectional SFM

2000.01500.01000.0500.00.0ABCMethods

D提案手法
234

Invisible area in OMS

Application 1/3

Complete video capturing forall the direction by OMS isessentially difficult.

Omni--directional telepresence system
Omni
without invisible areaby image completion
Omnidirectional telepresence systemusing video captured by OMS.

Koutaro Machikita
Machikita,, Norihiko Kawai,
Tomokazu Sato,
Sato, Naokazu Yokoya

Invisible area in the video
decreases a reality

Image completion technique thatrelying only for geometric info.
often generates unnatural images.

* ‘Generation of an omnidirectional video without invisible areas using
image inpainting’, Proc. ACCV2009, Sep. 200926

Image from Google’s street viewResult in telepresence system

Exemplar based image completion(image inpaintinginpainting)) methods[Wexler et al., 2004][Kawai et al., 2008]

28

Processes for image completion
1. Camera parameter
estimation for omni-video

2. Estimation of ground surface
and image projection to it

Image completion based on pattern similarity
I (x) ： Pixel value for x⎡2⎤
E = ∑ wxi ⎢ ∑{I f (xi + p) − I k (t (xi ) + p)} ⎥ t (x) ： Corresponded pixel
position with xxi ∈Ω'⎣p∈W⎦wx : Weight for x

Energy is defined as weighted sum of SSD.

3. Determination of data region
using geometric infomation

4. Image completion byusing pattern similarity

Data region

Exemplar foreach pixelxt (x)Target framefReference frame kFollowing two processes are repeated until energy convergence.
TargetReference frame

TargetReference frame 29

Searching for similar pattern

Update for pixel value

30

5Completed result for projected images

Our method

Before and after completionin panoramic image

The method that uses only
geometric information
31

Result in telepresence system

32

Application 2/3

Novel-view synthesisNovelfrom omnidirectional videousing a deformable 33--D mesh model
Hiroyuki Koshizawa,Koshizawa, Takuya Ibuki,Tomokazu Sato,Sato, Naokazu Yokoya* ‘Omnidirectional free-viewpoint rendering using a deformable 3-D meshmodel’, Int. J. of Virtual Reality, Vol. 9, No. 1, pp. 37-44, March 2010.
33

Generated video image
for zigzag camera path

Flow diagram of proposed method
Acquisition of input data
Video capturing
Camera parameter estimationC

Depth map generation

Free-viewpoint Rendering
S

Generation of view-dependent 3-D modelbuilding

Selection of depth maps
Mesh model initialization / deformation

5m

View-dependent texture mapping
Selection of appropriate textures

Original camera-path
Virtual camera

Texture mapping
Viewpoint change by user
3536

6

Flow diagram of proposed method
Acquisition of input data

Flow diagram of proposed method
Acquisition of input data

Video capturing

Video capturing

Camera parameter estimation

Camera parameter estimation

Depth map generation

Depth map generation

Free-viewpoint Rendering

Free-viewpoint Rendering

Generation of view-dependent 3-D model

Generation of view-dependent 3-D model

Selection of depth maps
Mesh model initialization / deformation

Selection of depth maps
Mesh model initialization / deformation

Virtual viewpoint

View-dependent texture mapping

Virtual viewpoint

View-dependent texture mapping

Selection of appropriate textures
Texture mapping

Selection of appropriate textures
Texture mapping
Viewpoint change by user

Viewpoint change by user
37

Mesh deformation
using multiple depth maps

38

Generated video for circular path
1m
Virtualviewpoint

Originalcamera
path

Route forvirtual camera

Virtualviewpoint

Original camera path

Each vertex on mesh is moved so as to minimize energyfunction that expresses consistency of the depth maps.

Application 3/3

Example of AR: Virtual sightseeing

Feature landmark based
augmented reality

Takafumi Taketomi
Taketomi,,
Tomokazu Sato,Sato, Naokazu Yokoya* ‘Real-time camera position and posture estimation using a featurelandmark database with priorities’, Proc. ICPR2008, Dec. 2008.

7

Construction of landmark database
Feature point

Landmark(x, y, z)

Camera parameter estimation
using landmark database

3D position+
Visual information

Feature points (2D)
correspondences

Register
3D position and image patternsof feature points are once
stored to database.

Landmark
database

Human navigation
using Augmented Reality

Detected Landmarks

Landmark (3D)
Cameraparameter
Capturea image
Landmark
database

Application for car AR navigation

Navigation information
shown to the user

Intuitive navigation can be achieved in mobile phones.
Computational cost：cost：59ms for 1 frame (17 fps)
（CPU: Core 2 Extreme 2.93GHz, Memory: 2GB）
2GB）

Application for Pre‐
Pre‐Visualization

Summary Introduction of omnidirectional SFM
 PnP Solution for OMS
 Visual SLAM for OMS

 GPS integration to SFM Cylinder whose size is changed depending on
measurementt confidence
fidisi usedd ffor penalty
lt term.
t

 Applications of omnidirectional SFM
 Video generation without invisible area
 Novel view synthesis
 Landmark based Augmented Reality

E‐mail: tomoka‐s@is.naist.jp
URL: http://yokoya.naist.jp/~tomoka‐s/index‐e.html

8