# Morphable 3D-Mosaics: A Hybrid Framework for Photorealistic Walkthroughs of Large Natural Environments

Authors: Nikos Komodakis; Georgios Tziritas
Journal: Advances in Multimedia
 (2008)

---

## Abstract

This paper presents a hybrid (geometry- & image-based) framework suitable for providing photorealistic
walkthroughs of large, complex outdoor scenes at interactive frame rates. To this end, based just on a sparse
set of real stereoscopic views from the scene, a set ofmorphable 3D-mosaics is automatically constructed
first, and then, during rendering, a continuous morphing between those 3D-mosaics that are nearby to the
current viewpoint is taking place. The morphing is both photometric, as well as geometric, while we also
ensure that it proceeds in a physically valid manner, thus remaining transparent to the user. The effectiveness
of our framework has been demonstrated in the 3D visual reconstruction of the Samaria Gorge in Crete,
which is one of the largest and most beautiful gorges in Europe.


---

## Body

## 1. Introduction

One of the main
research problems in computer graphics is the creation of modeling and
rendering  systems capable to provide photorealistic
representations of complex, real-world environments. Minimal human intervention
during the modeling process and operation in real time during rendering, a
property that allows walkthroughs at interactive frame rates, are some of the
desirable characteristics for such systems. Two are the most prominent
approaches that have been proposed so far in this regard. The first, more
traditional, way of building this type of systems is by taking a purely
geometric approach. In this case, a full 3D geometric model of the whole scene
is constructed first, and that model is then used for the rendering of the
scene afterwards. One big advantage of this approach is that it offers great
flexibility with respect to manipulating or editing the scene's properties. For
example, due to a full 3D model being available, operations such as altering
the viewpoint of the camera, changing the position of light sources, modifying
part of the geometry, and so forth can be attained very easily in this case.
The price for this flexibility, however, lies in constructing the underlying 3D
model of the scene needed in the first place. Unless done automatically, this
can be an extremely time consuming and daunting task, especially for
large-scale scenes. Due to this fact, a lot of effort went recently into how to
obtain such a geometric model automatically by using only real images as input
[1, 2]. This task is now known as multiple
view geometry in the computer vision literature, and has been a very active
research topic over the last years [3–5]. A characteristic method in this regard is the work of
Pollefeys et al. [6] on
3D reconstruction from hand-held cameras, as well as the work of Debevec et al.
[7] on recovering the
geometry of architectural-type scenes, just to name a few of the proposed
methods. For scenes with irregular geometry, however, such as outdoor scenes,
or scenes with trees and plants, extracting an accurate 3D model still remains
a very difficult task in the general case.Relatively recently, however, it was realized by
researchers that geometry is often unnecessary for obtaining a realistic
representation of the scene [8]. As a result, the so-called image-based rendering
(IBR) methods have emerged. These methods completely skip the geometric
modeling of the scene and, instead, concentrate just on how to fill the image
pixels corresponding to a novel view. In this case, geometric modeling is
replaced by simply capturing a dense set of real images, with each one of these
images associated to a different view of the scene. When given a novel view,
these methods then try to synthesize it simply by (appropriately) resampling
the previously captured set of views. Intuitively, IBR methods can be thought
of as trying to assemble a puzzle. The puzzle to be assembled is the novel view
itself, while the pieces of the puzzle correspond to the pixels contained in
the captured views. Since the invention of the concept of image-based
rendering, many such methods have been proposed (see [9] for an excellent survey),
with Lightfield [10]
and Lumigraph [11]
being two of the most characteristic examples in this regard. The biggest
advantage of all IBR techniques is the extremely high level of photorealism
they can attain (since they make use of actual images of the scene). The price
for this, however, is the huge amount of data (i.e., input images) often
required by IBR methods, which actually forms one of their main disadvantages.
To see why this needs to be so in general, it is worth considering another
interpretation of IBR techniques. According to it, these methods try to
reconstruct the so-called plenoptic function [12]. This is a 7-dimensional
function 𝒫(𝒱x,𝒱y,𝒱z,θ,ϕ,λ,t), which models a 3D dynamic environment by recording the light rays at
every space location (𝒱x,𝒱y,𝒱z),
towards every possible direction (θ,ϕ),
over any range of wavelengths λ and at any time t.
Each time we capture an image by a camera, the light rays passing through the
camera's center of projection are recorded and so that image can be considered
as a specific sample of the plenoptic function. In this context, image-based
rendering can be interpreted as a signal processing task, that is, that of reconstructing
a continuous signal (in this case the plenoptic function) based only on a
discrete set of samples from that signal. Given the high dimensionality of
the plenoptic function, the reason why a huge number of input images is, in
general, required by IBR techniques then follows directly from the well-known
Nyquist theorem.This issue with the huge amount of input data is also
one of the reasons why the great majority of existing IBR techniques apply only
to scenes of either small or medium scale. On the contrary, much fewer IBR
methods have been proposed for the case of large-scale scenes. Motivated by
this fact, the work presented in this article describes a novel, hybrid (i.e.,
both geometry-based and image-based) system, that can deal efficiently with the
visual reconstruction of large-scale, natural outdoor environments. We note
that this reconstruction is always photorealistic, while its visualization can
take place at interactive frame rates, that is, in real time. For reducing the
otherwise huge amount of input data, our system makes use of a new compact data
representation of a 3D scene, calledmorphable 3D-mosaics [13, 14]. As we will see, this scene
representation consists of a set of morphable (both geometrically and
photometrically) 3D models. Furthermore, these morphable models are constructed
automatically based just on a sparse set of real stereoscopic views. Due to the
above-mentioned properties, our system can be extremely useful in applications
such as 3DTV, gaming, virtual reality, and so on, where one seeks to create a
3D depth impression of the observed scene. In fact, the latter has been one of
the starting motivations for our system, which has thus already been used as a
part of a 3D virtual reality installation in the Natural History Museum of
Crete with the goal of providing a lifelike virtual tour of the Samaria Gorge
(one of the largest and most magnificent gorges in Europe).Besides the proposal of a novel hybrid representation
for a 3D scene, our system also includes the following new algorithms and
techniques as part of its image-based modeling and rendering pipeline: (1) a
robust photometric morphing procedure that is based on automatically extracting
a dense field of 2D correspondences between wide-baseline images (Section5.1),
(2) an efficient geometric morphing algorithm based on estimating 3D
correspondences between local geometric models (Section 5.2), (3) a robust
algorithm for constructing 3D panoramas by combining local 3D models (Section
7) and (4) a highly optimized rendering pipeline that runs entirely on the
GPU (thanks to employing pixel and vertex shaders for the morphing), while it
also uses decimated, but visually correct, 3D geometric models (Section 6).Of course, besides our system, other IBR techniques
for large-scale scenes exist as well. To this end, work on unstructured/sparse
lumigraphs has been proposed by various authors. One such example is the work
of Buehler et al. [15]. These authors make use of a fixed geometric proxy
that supposedly describes the global geometry of the scene in order to reduce
the required amount of input data. However, this assumption of a fixed
geometric proxy is not adequate in our case. Hence, contrary to [15], our system actually uses
view-dependent geometry due to the continuous geometric morphing taking place.
Another example of a sparse lumigraph is the work of Schirmacher et al.
[16]. Although
multiple geometric proxies are allowed in this work, any possible
inconsistencies existing between these proxies (e.g., due to errors) are not
taken into account during rendering. This is again in contrast to our work,
where an “optical flow” estimation between wide-baseline images is used for
dealing with this issue. Furthermore, this estimation significantly reduces the
required number of input views (and hence the amount of input data). For these
reasons, if any of the above two approaches were to be applied to large-scale
scenes, like those handled in our case, many more images (than ours) would then
be needed. In addition, due to our rendering path, which can be highly
optimized in modern graphics hardware, we can achieve very high frame rates
during rendering, whereas the corresponding frame rates listed, for example, in
[16] are much lower
due to an expensive barycentric coordinate computation that needs to take
place. In the “interactive visual tours” approach [17], video (from multiple
cameras) is being recorded as one moves along predefined paths inside a real
world environment, and then image-based rendering techniques are used for
replaying the tour and allowing the user to move along those paths. In this
way, virtual walkthroughs of large scenes can be generated. However, a
specialized acquisition system is needed in this case, whereas our method requires
using just off the shelf digital cameras. Also, in the “sea of images”
approach [18], a set
of omnidirectional images are captured for creating interactive walkthroughs of
large, indoor environments. However, this set of images needs to be very dense
with an image spacing of about 1.5 inches. Finally, the authors in [19] have proposed an IBR system
for providing constrained interactive walkthroughs inside large and complex
virtual environments.


## 2. Overview of the Morphable 3D-Mosaics Framework

As already
mentioned, our system is capable of providing photorealistic walkthroughs of
large-scale scenes at interactive frame rates. Assuming, for simplicity, that during the
walkthrough the user motion takes place along a predefined path inside the
environment (we note, of course, that our system
can be readily extended to handle the case where the stereoscopic views have
been captured not just along a predefined path, but throughout the
scene), the input to our system is then a sparse
set of stereoscopic views captured at certain locations (calledkey-positions hereafter) along that path (see Figure 1). Considering, initially, the case
where only one view per key-position exists, a series of local 3D models is then constructed based on these stereoscopic views. There exists one model
per view, and each local model is assumed to approximately capture the
photometric and geometric properties of the scene only at a local level. Then,
instead of trying to create a global 3D model out of all these local models (a
task that can prove to be extremely difficult in many cases, requiring a very
accurate registration between local models), we rather follow a different
approach, which is that of creating a series of so-called morphable
3D-models. The key idea then is that, during the transition between any two
successive key-positions (say pos1, pos2) along the path, one of these morphable
3D-models, say ℒ1→2,
is displayed by the rendering process (see Figure 1). At position pos1,
this model coincides with the local model ℒ1 at that position, while, as we are approaching pos2,
it is gradually transformed into the next local model ℒ2,
coinciding with that upon reaching key-position pos2.
Therefore, during the rendering process, and as the user traverses the predefined
path, a continuous morphing between successive local 3D models takes place all
the time. It is important to note that this morphing between local models is
both photometric, as well as geometric. Moreover, due to the way the morphable
models are constructed, we ensure that the morphing always proceeds in a
physically-valid manner, thus remaining transparent to the user of the system.
For this purpose, algorithms for extracting 2D correspondences between
wide-baseline images, as well as algorithms for establishing 3D correspondences
between local geometric models, are proposed and implemented. These are used
for estimating the photometric and geometric morphings, respectively.Figure 1
Initially, a
sparse set of stereoscopic views is captured at key-positions along the path.
Based on these stereoscopic views, a series of local 3D models is then
constructed. As the user traverses the path, a morphable 3D model is displayed
during rendering. In this manner, a continuous morphing between successive
local models takes place at any time, with this morphing being both photometric
as well as geometric.Our system can be also extended to handle the
existence of multiple stereoscopic views per key position, all of them related
by a pure rotation of the stereoscopic camera. In this case, there will also be
multiple local models per key-position. Therefore, before applying the morphing
procedure, a so-called3D-mosaic per key-position needs to be
constructed as well. Each 3D-mosaic will simply comprise the multiple local
models at the corresponding key-position and, intuitively, will itself be a
larger local model covering a wider field of view. Morphing can then proceed in
the same way as before, with the only difference being that these 3D-mosaics
will be the new local 3D models to be used during the stage of morphing (in
place of the smaller individual ones). Hence, in this case, a morphable 3D
mosaic (instead of a morphable 3D model) is said to be created by the
algorithm.Based on the above discussion, it follows that the 3D
modeling pipeline of our framework consists of the stages that are listed
below.(i)
Local models construction: this
construction is accomplished based on the stereoscopic views that have been
captured at key-positions along the path.(ii)
Relative pose estimation: a coarse
estimation of the relative rotation and translation between successive local
models takes place during this stage.(iii)
Generation of morphable models: this
task amounts to estimating the photometric as well as geometric morphings
between successive local models.(iv)
3D mosaics generation: during this
stage, a 3D mosaic is generated at each key-position by aggregating all local
models corresponding to that position. During the next
sections, each one of the above tasks will be described briefly, while the
various algorithmic choices that have been made in each case will be justified
and explained.


## 3. Local 3D Models Construction

As already mentioned in the previous section, a
set of local 3D models needs to be extracted during the first stage of the 3D
modeling pipeline. There will be one local 3D model per stereoscopic view (and
hence per key position as well, since we initially assume there is a one-to-one
correspondence between key-positions and stereoscopic views). Such a 3D model
is supposed to provide both a photometric as well as a geometric representation
of the scene, but only at a local level (i.e., only near the corresponding
key-position along the path). To this end, a stereo matching procedure is
applied between the leftℐleft and right ℐright images of the stereoscopic view, so that pixel
correspondences between the 2 images are extracted [20]. Based on these
correspondences (and assuming a calibrated pair of cameras), a 3D
reconstruction can then take place via triangulation (i.e., by intersecting in
3D space the camera rays passing through corresponding pixels). In this manner,
the 2D maps 𝒳k, 𝒴k,
and 𝒵k are produced that contain, respectively, the x,y,z coordinates of the reconstructed 3D points for
each pixel in the left image (e.g., see the depth map in Figure 2). Without
loss of generality, we will assume that these geometric maps are defined only
over a region ℛk on the image plane, and this region will be
referred to as their domain hereafter.Figure 2
A geometric
depth map𝒵k of a local model is shown on the left (this
map is assumed to be defined only over region ℛk on the image plane). By combining this
geometric map with a photometric map, a local 3D model can be created, which
can be used for providing rendered views of the scene around the key-position
of the local model. One such view is shown here.These maps will form the local geometric
representation of the scene, whereas the left imageℐleft will be used as the corresponding photometric
representation ℐk (i.e., ℐk=ℐleft). The set ℒk={𝒳k,𝒴k,𝒵k,ℐk,ℛk} will thus make up what we will hereafter refer
to as a local modelℒk.
In fact, this term will always implicitly refer to such a set of elements. As
its name suggests, such a model can be used for reproducing a photorealistic
reconstruction of the real scene, but only in a local region around the model's
key-position posk (e.g., see the right image in Figure 2). In
fact, it is only at this local region in 3D space where this model will be used
during rendering, which is exactly why the geometric maps of a local model do
not have to provide a very accurate representation of the whole scene's
geometry.For solving the stereo matching problem, we estimate a
discrete disparity field by minimizing the energy of a 2nd-order Markov random
field. The nodes of this MRF are the pixels of the left image, while the labels
belong to a discrete set of disparities{0,1,…,dmax},
where dmax represents the maximum allowed disparity. We
then seek to assign a label dp to each node p so that the following MRF energy is
minimized:(1)E({dp})=∑pVp(dp)+∑(p,q)∈ℵVpq(dp,dq),where the symbol ℵ denotes a set of interacting pairs of pixels
on the image grid (a 4-neighborhood system is assumed).The single node potentialVp(dp) for assigning disparity dp to pixel p is going to be set as Vp(dp)=wp⋅|ℐright(p−dp)−ℐleft(p)|2.
The factor wp expresses a confidence measure and is used for
giving less weight to pixels that are less reliable for matching (e.g., their
neighborhood in the image has uniform intensity). Its value is set based on the
minimum eigenvalue of the following autocorrelation matrix G:(2)G=[∑ℐx2∑ℐxℐy∑ℐxℐy∑ℐy2].Here, (ℐx,ℐy) represents the left image gradient, while the
sums are taken over a small window around the point p in the left image. The minimum eigenvalue is a
measure of the “cornerness” of point p and will be large in regions with high texture
variation, but will be small in uniform regions. Regarding the pairwise
potentials Vpq(⋅,⋅),
these are set equal to the following truncated quadratic function: Vpq(dp,dq)=min(μ,|dp−dq|2),
where μ denotes the maximum allowed discontinuity
penalty that can be imposed. For optimizing the energy of the above discrete
MRF, the recently proposed primal-dual algorithms of Komodakis et al. [21, 22] have been used, which can
guarantee an approximately optimal solution for a very wide range of MRFs. For
turning the resulting discrete disparity field into a continuous one (which
will yield a local 3D model that is better for visualization purposes), a
continuous optimization scheme (e.g., a simple gradient descent) can be applied
afterwards as well.


## 4. Relative Pose Estimation between Successive Local Models

Given any two
successive local modelsℒk, ℒk+1 along the path, a rough estimation of their
relative 3D poses  (i.e., their 3D rotations and
translations) needs to take place as well. Note that, similarly
to the estimation of the models' geometry, only a very coarse and approximate
estimation of the 3D pose is needed. Again, the reason is because this pose is
not going to be used for performing an exact registration into a global 3D
coordinate system, but merely for facilitating the morphing procedure that will
take place later (i.e., during the next stage). One way for obtaining such a
rough estimate is by, for example, computing a sparse set of approximate pixel
correspondences between the photometric images ℐk, ℐk+1 of models ℒk, ℒk+1.
Based on these correspondences, the so-called fundamental matrix (that
relates points in images ℐk, ℐk+1) can be computed, from which one can easily
extract an approximate estimation of the relative 3D pose [3].Therefore, the pose estimation problem is reduced to
that of extracting a sparse set of correspondences betweenℐk, ℐk+1.
A usual method for tackling the latter problem is the following: first a set of
interest-points in ℐk are extracted (using an interest-point
detector). Then for each interest-point, say p,
a set of candidate points CANDp inside a large rectangular region SEARCHp of ℐk+1 are examined and the best one is selected
according to a similarity measure. Usually the candidate points are extracted
by applying an interest-point detector to region SEARCHp as well.However, unlike left/right images of a stereoscopic
view,ℐk and ℐk+1 are separated by a wide baseline. Simple
measures like correlation have been proved extremely inefficient in such cases.
Assuming a smooth predefined path (and therefore a smooth change in orientation
between ℐk, ℐk+1), it is safe to assume that the main
difference at an object's appearance in images ℐk and ℐk+1 comes from the forward camera motion along the
Z axis (looming). The idea for extracting valid correspondences is then based
on the following observation: the dominant effect of an object being closer to
the camera in image ℐk+1 is that its image region in ℐk+1 appears scaled by a certain scale factor s>1,
that is, if p∈ℐk, q∈ℐk+1 are corresponding pixels: ℐk+1(sq)≈ℐk(p).
So an image patch of ℐk at p should look similar to an image patch of an
appropriately rescaled (by s−1) version of ℐk+1.Of course, the scale factors varies across the image. Therefore, the
following strategy, for extracting reliable matches, can be applied.(1)
Quantize the scale space ofs to a discrete set of values S={sj}j=0n,
where 1=s0<s1<⋯<sn.(2)
Rescaleℐk+1 by the inverse scale sj−1 for all sj∈S to get rescaled images ℐk+1sj.
For any q∈ℐk+1, p∈ℐk,
let us denote by  PATCHk+1sj(q) a (small) fixed-size patch around the projection of q on Ik+1sj and by PATCHk(p) an equal-size patch of ℐk at p.(3)
Given any pointp∈ℐk and its set of candidate points CANDp={qi} in ℐk+1,
use correlation to find among the patches at any qi and across any scale sj,
the one most similar to the patch of ℐk at p:(3)(q′,s′)=argmaxqi,sjcorr(PATCHk+1sj(qi),PATCHk(p)).This way, apart
from a matching pointq′∈ℐk+1,
a scale estimate s′ is provided for point p as well.The above
strategy has been proved very effective, giving a high percentage of exact
matches even in cases with very large looming. Such an example can be seen in
Figure3.(a) Imageℐk along with computed optical flow vectors (blue
segments) for all points marked white. (b) Image ℐk+1 along with matching points (also marked white)
for all marked points of (a). A few epipolar lines are also shown. 10 scales S={1,0.9−1,…,0.1−1} have been used during matching.
(a)(b)


## 5. Estimation of Morphable 3D Models

The output of
the previous stage will thus be a series of approximate local 3D models (along
with approximate estimates of the relative pose between every successive two).
Rather than trying to create a consistent global model by combining all local
ones (a rather tedious task, requiring among others high-quality geometry and
pose estimation), we will, instead, follow a different approach, which is based
on the following observation. Letℒk={𝒳k,𝒴k,𝒵k,ℐk,ℛk},  ℒk+1={𝒳k+1,𝒴k+1,𝒵k+1,ℐk+1,ℛk+1} be any two  successive local models along the
path and let also posk, posk+1 be their corresponding key-positions. Near
position posk,
the model ℒk is ideal for representing the surrounding
scene. However, as we move forward along the path and approach key-position posk+1 of next model ℒk+1,
the photometric and geometric properties of the environment are much better
captured by that model. Compare, for example, the fine details of the rocks
that are revealed in image ℐk+1 of Figure 4 (i.e., the photometric image of
the next local model), but are not visible in image ℐk of that figure (i.e., the photometric image of
the previous local model). Hence, during the transition from posk to posk+1,
we will try to gradually morph model ℒk into a new destination model, which
should coincide with ℒk+1 upon reaching position posk+1.
(In fact, only part of this destination model can coincide with ℒk+1 since, in general, models ℒk, ℒk+1 will not represent exactly the same part of
the scene.) This morphing should be geometric, as well as photometric (the
latter wherever possible), and should proceed in a physically valid way. For
this reason, we will use what we call a morphable 3D-model:(4)ℒmorph=ℒk∪{𝒳dst,𝒴dst,𝒵dst,ℐdst}.As can be seen, in addition to
including all the geometric and photometric maps of model ℒk (called the source maps hereafter), ℒmorph also consists of some additional destination
maps: these are the geometric maps 𝒳dst,𝒴dst,𝒵dst,
as well as the photometric map ℐdst,
containing, respectively, the destination 3D vertices and colors for all points
of the source model ℒk.
Note that both the source and destination maps are defined over the same domain ℛk.
Hence, at any time during the rendering process, the 3D coordinates and colors
of the morphable model ℒmorph will be given by(5)[𝒳morph(p)𝒴morph(p)𝒵morph(p)ℐmorph(p)]=(1−α)⋅[𝒳k(p)𝒴k(p)𝒵k(p)ℐk(p)]+α⋅[𝒳dst(p)𝒴dst(p)𝒵dst(p)ℐdst(p)],∀p∈ℛk,where α is a parameter determining the amount of
morphing (with α=0 at posk, α=1 at posk+1 and 0<α<1 in between). Therefore, specifying ℒmorph simply amounts to filling-in the values of the
destination maps {𝒳,𝒴,𝒵,ℐ}dst at each p∈ℛk.Figure 4
When seeking a correspondence for a pixelp of image ℐk,
we reproject that pixel onto image ℐk+1 (using the approximate geometry of the local
models and their relative pose) and then restrict our search only in a small
region SEARCHp around the reprojection point. Furthermore, to
take scale differences into account, we search not only inside region SEARCHp of image ℐk+1,
but also inside the projection of SEARCHp onto the images ℐk+1s,
which are rescaled versions of image ℐk+1,
that is, we search not only for a corresponding pixel, but also for a scale
estimate. In fact, all the possible pixel-scale combinations will form the
candidate labels of pixel p and to choose the best one of them, we will
use an MRF optimization procedure.For this purpose, a 2-step procedure will be followed,
depending on whether a point inℒk has a physically corresponding point in ℒk+1 or not.(1)
The main idea is that if a point inℒk has a physical correspondence in ℒk+1,
that correspondence can be directly used to fill the destination maps.
Specifically, let Ψ denote the subset of region ℛk,
consisting of all those
p's for which there exists a
physical correspondence in ℒk+1 (i.e., region Ψ refers to that part of the scene which is
common to both models ℒk, ℒk+1). Let also uk→k+1 be a function that maps each p∈Ψ⊂ℛk to its counterpart in Rk+1.
Since model ℒk (after morphing) should coincide with ℒk+1,
it must then hold as follows:
(6)[𝒳dst(p)𝒴dst(p)𝒵dst(p)ℐdst(p)]=[𝒳k+1(uk→k+1(p))𝒴k+1(uk→k+1(p))𝒵k+1(uk→k+1(p))ℐk+1(uk→k+1(p))],∀p∈Ψ.This means that, for all p∈Ψ,
the destination maps at p can be filled simply by copying the
appropriate values from the maps of model ℒk+1.
As a result, all points of ℒk in region Ψ can be transformed both photometrically as
well as geometrically.(2)
The rest of the points ofℒk (i.e., all points defined over region Ψ¯=ℛk−Ψ) do not have counterparts in model ℒk+1.
Hence, no photometric morphing is possible to be applied to those points. As a
result, these points will retain their color value from model ℒk,
or(7)ℐdst(p)=ℐk(p),∀p∈Ψ¯.Nevertheless we still need to
apply geometric morphing to them, so that no distortion/discontinuity in the 3D
structure is observed during the transition from posk to posk+1.
This means that we will still have to fill-in the destination 3D coordinates
(i.e., the destination geometric maps) for all p∈Ψ¯.The 2 important remaining issues (that also constitute
the core of the morphing procedure) are as follows:(i)
how to compute the mappinguk→k+1.
This is equivalent to estimating a 2D displacement field (also called optical
flow field hereafter) between images ℐk and ℐk+1,(ii)
and how to obtain the missing values of the
destination geometric-maps forp∈Ψ¯.
These values will be needed for fully specifying the geometric morphing of
model ℒk over the whole domain ℛk=Ψ∪Ψ¯. Both of these
issues will be the subject of the two sections that are following.


## 5.1. Photometric Morphing via Optical Flow Estimation

In general,
obtaining a reliable, dense optical flow field between imagesℐk and ℐk+1 is a particularly difficult problem. In fact,
without additional input, usually only a sparse set of optical flow vectors can
be obtained in the best case. The main difficulties stem from the fact that,
unlike the left and right images of a stereo pair, images ℐk and ℐk+1 are separated by a wide baseline (since they
are captured at totally different positions posk, posk+1).(i)
On the one hand, this means that the resulting
displacement vectors can be large, which, in turn, implies that, when searching
for the correspondence of a pixelp∈ℐk,
one needs to examine a very large region of image ℐk+1 (the search region corresponding to pixel p will be denoted by SEARCHp hereafter). In this manner, however, the chance of an erroneous
optical flow vector increases significantly (and so does the computational
cost).(ii)
On the other hand, for extracting pixel
correspondences, one usually needs to compare patches from imagesℐk and ℐk+1 (where the assumption is that patches
associated with corresponding pixels should look similar to each other). In the
case of wide-baseline images, however, simple similarity measures for comparing
patches (such as the correlation between patches) will typically produce very
inaccurate correspondences, when used naively. The reason is that, due to the
wide baseline, the appearance of a patch may change significantly from one
image to the next (e.g., the patch may have been rescaled and thus appear
larger). Therefore, more appropriate similarity measures have to be used in
this case.(iii)
Finally, even if both of the above problems
are solved, optical flow estimation is inherently an ill-posed problem and so
additional regularization assumptions need to be imposed.For dealing with the first of these issues, we
will make use of the underlying geometric maps𝒳k, 𝒴k, 𝒵k of model ℒk,
as well as the relative pose between views ℐk and ℐk+1.
Theoretically, by using these quantities, we can find the correspondence of a
pixel p of ℐk by reprojecting it onto image ℐk+1.
However, since all of the above quantities have been estimated approximately,
this only allows us to narrow the search region SEARCHp to a smaller region around the reprojection point, for example, see
Figure 4 (in fact, the search region can be further restricted by taking its
intersection with a small zone around the epipolar line corresponding to p). In addition, since we are interested in
searching only for pixels of ℐk+1 that belong to region ℛk+1 (this is where ℒk+1 is defined), the final search region for p will be SEARCHp∩ℛk+1.
If the resulting region is empty, then no optical flow vector will be estimated
and pixel p will be considered as not belonging to region Ψ.For dealing with the second problem, we will use a
technique similar to the one described in Section4 for getting a sparse set
of correspondences. As already stated therein, the dominant effect due to a
looming of the camera is that pixel neighborhoods in image ℐk+1 are scaled by a factor varying across the
image. The solution proposed therein (and which we will also follow here) was
to compare image patches of ℐk with patches not only from ℐk+1 but also from rescaled versions of the latter
image. We will again use a discrete set of scale factors 𝒮={1=s0<s1<⋯<sn} and ℐk+1s will denote image ℐk+1 rescaled by s−1.However, even after the above enhancements, estimating
correspondences independently for each pixel will produce a lot of errors. This
is because optical flow estimation is an inherently ill-posed problem. Hence,
to obtain high-quality results, one needs to regularize this problem by taking
advantage of the fact that optical flow vectors at neighboring pixels typically
exhibit a high correlation. Discrete Markov random fields (MRFs) [23] are ideal candidates for
modeling this type of local correlations and have also been used with great
success in many other cases. For this reason, we will reduce optical flow
estimation to a discrete MRF optimization task, that is to a discrete labeling
problem. In this case, based on our earlier discussion, each label l=(ux,uy,s)∈ℝ2×𝒮 will consist not only of an optical flow
vector (ux,uy),
but also of a scale factor s∈𝒮 (hereafter, the optical flow vector of any
label l will be denoted by u(l) and its scale by s(l)). Furthermore, the labels that can be
assigned to a pixel p∈ℐk will belong to the set LABELSp={p′−p:p′∈SEARCHp}×𝒮.
This definition of set LABELSp simply encodes the fact that, when seeking a
correspondence for a pixel p of image ℐk,
we are allowed to search across all scales s∈𝒮 (i.e., in all images Ik+1s), but only inside region SEARCHp at each scale (see Figure 4).Given all these label sets, getting then an optical
flow field is equivalent to picking one element from the cartesian productLABELS=∏p∈ΨLABELSp.
In MRF optimization, this is typically done by trying to choose an element l={lp}p∈Ψ that minimizes the MRF energy. This energy is
defined as follows:E({lp})=∑p∈ΨVp(lp)+∑(p,q)∈ℵVp,q(lp,lq).Here, the functions Vp(⋅), Vpq(⋅,⋅) denote, respectively, the so-called unary and
pairwise MRF potentials, while ℵ denotes all pairs of neighboring pixels in
region Ψ.
These two functions serve a different role in MRF optimization: the terms Vp(lp) try to penalize labelings {lp} that do not fit well to the observed data,
whereas the terms Vpq(lp,lq) try to enforce smoothness between labels lp, lq of neighboring pixels. In our case, each term Vp(lp) will measure the dissimilarity between
corresponding patches according to label lp.
According to that label, a patch around p∈ℐk will correspond to a patch around p′=p+u(lp)∈ℐk+1 that has been rescaled by s(lp).
Hence, to determine Vp(lp),
pixel p′∈ℐk+1 is projected onto the rescaled image ℐk+1s(lp) and a fixed size patch, denoted by PATCHk+1s(lp)(p′),
is taken around this projection. We then compare this patch with an equal-size
patch PATCHk(p) around p∈ℐk,
or(8)Vp(lp)=∥PATCHk(p)−PATCHk+1s(lp)(p′)∥1,where ∥⋅∥1 denotes the l1-norm and thus Vp(lp) measures the sum of absolute intensity
differences between corresponding patches.On the other hand, as already mentioned, the role
of the pairwise termsVpq(⋅,⋅) is to regularize the solution by imposing
smoothness on the resulting optical flow vectors. These terms can be defined
using the following truncated distances:(9)Vpq(lp,lq)=λ0min(∥u(lp)−u(lq)∥,μ0)+λ1min(∥s(lp)−s(lq)∥,μ1). As can be seen, these terms
penalize labelings that assign discontinuous displacements or discontinuous
scale factors to neighboring pixels (note that, due to the truncation by μ0 and μ1,
some discontinuities are still allowed to exist, e.g., at the boundary between
2 objects). Minimizing the resulting MRF energy is in general NP-hard. Yet,
there exist optimization techniques, which can provably guarantee approximately
optimal solutions [21, 22, 24]. Foe example, Figure 5 contains the resulting optical
flow for images ℐk, ℐk+1 of Figure 4. For comparison, we also show the
corresponding optical flow when no search across scale takes place, that is 𝒮={1}.
As expected, in this case, the optical flow vectors are quite noisy in regions
undergoing a large change of scale due to the camera motion. When using the
fast optimization algorithms from [21], convergence is very fast (only a few iterations are
needed) and the average running time per iteration is on the order of a few
seconds.On the top
row, we show again the two imagesℐk, ℐk+1 from Figure 4 along with computed optical flow
vectors (blue segments) for a sparse set of points (a few epipolar lines are
also shown in ℐk+1). In both of these images, the yellow square
around a point is proportional to the point's estimated scale factor (10 scales S={1,0.9−1,…,0.1−1} have been used). On the bottom row, we show
the estimated scale factors for all the points in region Ψ,
as well as the corresponding optical flow magnitudes at these points. Regarding
optical flow, two results are shown: when using 10 possible scales S={1,0.9−1,…,0.1−1},
as well as when using just one scale S={1}.
As expected, in the latter case, the estimated flow is quite noisy, since the
algorithm fails to produce exact optical flow for points that actually undergo
a large change of scale. We note that darker pixels (in a grayscale image)
correspond to smaller values.
(a)(b)(c)(d)(e)


## 5.2. Geometric Morphing

After estimating functionuk→k+1,
we may apply (6) to all points in region Ψ.
This allows us to copy values from the geometric maps of model ℒk+1 in order to fill-in region Ψ of the destination geometric maps 𝒳dst, 𝒴dst, 𝒵dst.
For notational convenience, the resulting partially complete geometric maps,
that is with known values only in region Ψ,
will be denoted by 𝒳^dst, 𝒴^dst, 𝒵^dst (e.g., see the middle image in Figure 6). To
completely specify morphing, it only remains to fill-in the destination
geometric maps over the rest of their domain, that is, over region Ψ¯=ℛk−Ψ.
For this, we need to specify the corresponding destination 3D vertices for all
points of ℒk in Ψ¯.
Since these points do not have a physically corresponding point in ℒk+1,
we cannot apply (6) to get a destination 3D coordinate from model ℒk+1.
A naive solution to deal with this would be to simply apply no geometric
morphing to these points, that is to allow the destination 3D vertices of these
points to coincide with their source vertices in ℒk.
In that case, we would end up with destination geometric maps:(i)
whose values inΨ would have been copied from model ℒk+1,(ii)
but whose values inΨ¯ would have been copied from model ℒk.Figure 6
In the middle,
we show an incomplete destination depth map𝒵^dst,
whose region Ψ has been filled-in by using the optical flow
from Figure 5 and applying (6). On the left, we show the full destination depth
map that has been produced by extending 𝒵^dst to region Ψ¯=ℛk−Ψ without using geometric morphing. Notice the
discontinuities existing along the boundary ∂Ψ¯.
On the right, we show the full destination depth map that has been produced
when geometric morphing has been enabled. As can be seen, no discontinuities
exist along the boundary ∂Ψ¯ in this case.In this manner, however, the resulting
destination maps𝒳dst, 𝒴dst, 𝒵dst would contain discontinuities along the common
boundary (say ∂Ψ¯) of regions Ψ and Ψ¯ (e.g., see the left image in Figure 6), thus
leading to very annoying discontinuity artifacts (holes) during the morphing
procedure (e.g., see the left image in Figure 7). This would indeed be the
case, since the geometries of both ℒk and ℒk+1 (as well as their relative poses)
have been estimated only approximately and thus these models may not match
perfectly to each other.We show rendered views of a morphable 3D-model during
the transition from one key-position (corresponding to imageℐk in Figure 4) to another key-position
(corresponding to image ℐk+1 in Figure 4). On t(a) we show the result
produced when no geometric morphing is applied to points in Ψ¯ (notice the resulting discontinuity, i.e.,
hole). On (b) we render the same view, but this time we also apply
geometric morphing to points in Ψ¯ (no discontinuities/holes exist in this case).
A zoomed version of this view is also shown on (c). Although, as
mentioned, there is no geometric discontinuity, yet there is a difference in
texture resolution between the left part of the image (points in Ψ¯) and the right part (points in Ψ), since only points of the latter part are
morphed photometrically.
(a)(b)(c)Instead, the
proper way to fill-in the destination vertices at regionΨ¯ is based on the observation that a physically
valid destination 3D model should satisfy the following 2 conditions.(1)
Along the boundary ofΨ¯,
no discontinuity in its 3D structure should exist, that is the values of 𝒳dst, 𝒴dst, 𝒵dst at ∂Ψ¯ should coincide with the already filled-in
values of 𝒳^dst, 𝒴^dst, 𝒵^dst at ∂Ψ¯.(2)
In the interior ofΨ¯,
the relative 3D structure of the destination model should coincide with the
relative 3D structure of the source model ℒk (since these two models are assumed to be
related by a rigid transformation). Put otherwise, the relative 3D structure of ℒk should be preserved during morphing, or, at
least, it should not be distorted too much.In mathematical
terms, the first condition obviously translates to(10)𝒳dst∣∂Ψ¯=𝒳^dst∣∂Ψ¯,𝒴dst∣∂Ψ¯=𝒴^dst∣∂Ψ¯,𝒵dst∣∂Ψ¯=𝒵^dst∣∂Ψ¯,whereas the second condition,
that is that of preserving the relative 3D structure of ℒk during morphing, implies(11)[𝒳dst(p)−𝒳dst(q)𝒴dst(p)−𝒴dst(q)𝒵dst(p)−𝒵dst(q)]=[𝒳k(p)−𝒳k(q)𝒴k(p)−𝒴k(q)𝒵k(p)−𝒵k(q)],∀p,q∈Ψ¯which is easily seen to be
equivalent to(12)[∇𝒳dst(p)∇𝒴dst(p)∇𝒵dst(p)]=[∇𝒳k(p)∇𝒴k(p)∇𝒵k(p)],∀p∈Ψ¯. Therefore, based on the above
conditions, the destination vertices can be extracted by independently solving
3 similar optimization problems (one problem per 3D coordinate). For instance, the
missing values of 𝒵dst can be estimated by solving the following
optimization problem:(13)min𝒵dst∫∫Ψ¯∥∇𝒵dst(p)−∇𝒵k(p)∥2dp,s.t.𝒵dst∣∂Ψ¯=𝒵^dst∣∂Ψ¯.The finite-difference
discretization of  (13) (using the underlying pixel grid) yields a quadratic
optimization problem, which can be reduced to a sparse (banded) system of
linear equations, that can then be solved easily. Alternatively, one needs to
observe that a function minimizing (13) is also a solution to the following
Poisson equation with Dirichlet boundary conditions [25, 26]:(14)Δ𝒵dst=div(∇𝒵k),subject to𝒵dst∣∂Ψ¯=𝒵^dst∣∂Ψ¯.Therefore, in this case, the
missing values of the destination geometric maps can be filled by
independently
solving 3 Poisson equations of the above type (note that these equations can be
solved very efficiently, e.g., the needed time is at most only a few seconds).
See the right image in Figure 6 for a destination depth map produced with this
method. Also, the middle image of Figure 7 contains a corresponding rendering.


## 6. Rendering Pipeline

An important
advantage of our framework is that, regardless of the scene's size, only one
“morphable 3D-model”ℒmorph needs to be displayed at any time during
rendering, that is, the rendering pipeline has to execute the geometric and
photometric morphings for only one local model ℒk (as described in Section 5). This makes our
system extremely scalable to large-scale scenes. In addition to that, by
utilizing the enhanced capabilities of modern 3D graphics hardware, both types
of morphing can admit a GPU implementation, thus making our system ideal for 3D
acceleration and capable of achieving very high frame rates during rendering.More specifically, for implementing the photometric
morphing of modelℒk, multitexturing needs to be employed as a first step. To this end, both
images ℐk, ℐk+1 will be used as textures and each 3D vertex
whose corresponding 2D point p∈ℐk is located inside region Ψ will be assigned 2 pairs of texture
coordinates: the first pair will coincide with the image coordinates of point p∈ℐk while the second one will be equal to the
image coordinates of the corresponding point uk→k+1(p)∈ℐk+1 (see (6)). Then, given these texture
coordinates, a so-called pixel-shader (along with its associated vertex-shader)
[27] can simply blend
the two textures in order to implement (on the GPU) the photometric morphing
defined by (5). Pixel and vertex shaders are user defined scripts that are
executed by the GPU for each incoming 3D vertex and output pixel, respectively.
One possible implementation of such scripts, for the case of photometric
morphing, is shown  on the left side of Figure
8 where, for this specific example, the OpenGL Shading Language
(GLSL) [27] has been
used for describing the shaders. As for the 3D vertices which are associated to
points located inside region Ψ¯,
the situation is even simpler since no actual photometric morphing takes place
in there (see (3)) and so only image ℐk needs to be texture-mapped onto these
vertices.(a): Pixel shader code (and the associated vertex shader
code), written in GLSL (OpenGL Shading Language), for implementing the
photometric morphing. (b): Skeleton code in C for applying vertex blending in
OpenGL.
(a)(b)On the other hand, for implementing the geometric
morphing, the following procedure is used: two 2D triangulations of regionsΨ, Ψ¯ are first generated resulting into two 2D
triangle meshes triΨ, triΨ¯.
Based on these triangulations and the underlying geometric maps of ℒk,
two 3D triangle meshes meshΨk, meshΨ¯k are constructed. Similarly, using triΨ, triΨ¯ and the destination geometric maps 𝒳dst, 𝒴dst, 𝒵dst,
two more 3D triangle meshes meshΨdst, meshΨ¯dst are constructed as well. It is then obvious
that geometric morphing (as defined by (5)) amounts to a simple vertex
blending operation, that is, meshes meshΨk, meshΨ¯k are weighted by 1−α,
meshes meshΨdst, meshΨ¯dst are weighted by α, and the resulting weighted vertices are then
added together. Vertex blending, however, is an operation that is directly
supported by all modern GPUs and, as an example, Figure 8 (right box) contains skeleton code in C showing how one can
implement vertex blending using the OpenGL standard.Therefore, based on the above observations, rendering
a morphable model simply amounts to feeding into the GPU just 4 textured
triangle meshes. This is, however, a rendering path which is highly optimized
in all modern GPUs and, therefore, a considerable amount of 3D acceleration can
be achieved in this manner during the rendering process.


## 6.1. Decimation of Local 3D Models

Up to now, we have assumed that a full local 3D model
is constructed each time, that is, all points of the image grid are included as
vertices in the 2D triangulationstriΨ, triΨ¯.
However, we can also use simplified versions of these 2D triangle meshes,
provided, of course, that these simplified meshes approximate well the
underlying geometric maps [28]. In fact, due to our framework's structure, a great
amount of simplification can be achieved and the reason is that a simplified
model ℒk′ has to be a good approximation to the full
local model ℒk only in the vicinity of posk (remember that model ℒk is being used only in a local region around posk). Based on this observation, the following
iterative procedure is being used for the simplification of the 2D meshes: at
the start of each iteration, there exists a current 2D Delaunay triangulation trii which has as vertices only a subset of the
points on the image grid. Based on trii,
an error function e(p) is defined over the image grid which is
measuring how well the current meshi approximates the underlying geometric maps
(here meshi denotes the 3D surface defined by trii). To each triangle, say T,
of trii we then associate the following two
quantities: e(T)=maxp∈Te(p) (i.e., the maximum geometric error across T) and p(T)=argmaxp∈Te(p) (i.e., the interior point of T achieving this maximum error). At each
iteration the triangle Tmax=argmaxT∈triie(T) of maximum error is selected and its point p(Tmax) is added as a new vertex in the triangulation.
This way a new Delaunay triangulation trii+1 is given as input to the next iteration of the
algorithm and the process repeats until the maximum error maxT∈triie(T) falls below a user specified threshold emax,
which basically controls the total amount of simplification to be applied to
the local model. Our algorithm is initialized with a sparse Delaunay
triangulation tri0 and the only restriction imposed on tri0 is that it should contain the edges along the
boundary between regions Ψ and Ψ¯ (i.e., a constrained Delaunay triangulation
has to be used) so that there are no cracks at the boundary of the
corresponding meshes.For completely specifying the decimation process, all
that remains to be defined is the error functione(p).
One option would be to set e(p)=∥dev(p)∥,
where dev(p)=∥meshi(p)−[𝒳k(p)𝒴k(p)𝒵k(p)]∥ denotes the geometric deviation at p between meshi and the underlying geometric maps (meshi(p) is the 3D point defined by meshi at p). This, however, would not result in the
greatest possible geometric decimation. The key observation for managing to
increase the geometric simplification of meshi,
relies on the fact that meshi needs to provide a good approximation of ℒk only in a local region between positions posk and posk+1 of the path. As a result, we can choose to
relate e(p) to the maximum projection error only at these
locations. More specifically, we set(15)e(p)=max(PROJ_ERRposk,PROJ_ERRposk+1),where proj_errposk and  proj_errposk+1 denote the maximum projection error at
positions posk and posk+1 respectively, that is,(16)PROJ_ERRposk=maxp∈Ik∥PROJposk(DEV(p))∥,PROJ_ERRposk+1=maxp∈Ik+1∥PROJposk+1(DEV(p))∥.In practice, this definition of
the error e(p) has managed to achieve much larger reductions
in the geometric complexity of the local 3D models, without sacrificing the
visual quality of the resulting renderings, thus giving excellent results.
Furthermore, the user-defined threshold emax can now be expressed in pixel units and can
thus be set in a far more intuitive way by the user. An example of a simplified
local model that has been produced in this manner is shown in Figure 9, in
which case emax has been set equal to 0.5 pixels. We should
finally note that by using the simplified local 3D models one can reduce the
rendering time even further, thus achieving even higher frame rates, for
example, over 50 fps.(a) Estimated disparity field corresponding to a local 3D modelℒk. (b) Resulting full 3D model produced when a nondecimated 2D triangulation of the
geometric maps has been used.    (c) Simplified 3D model of ℒk produced using a decimated 2D triangulation
where the emax threshold has been set equal to 0.5
pixels.
(a)(b)(c)


## 7. 3D-Mosaics Construction

For
simplicity, up to this point we have been assuming that, during the image
acquisition process, only one stereoscopic image has been captured per
key-position along the path. Our framework, however, can be readily extended to
the case where multiple stereoscopic views (and hence multiple local models)
exist per key-position, related to each other by a pure rotation of the stereoscopic
camera. Such a scenario can be useful, for example, when an extended field of
view is required during the virtual walkthrough (as in VR installations with
large screens). To reduce this case to the one already examined, it suffices
that a single local model (called3D-mosaic hereafter) is constructed at
each key-position. This can be done by assembling all individual local models
at that position, which, as we will see, is an easy task, since these models
differ only by a rotation. Then, at any time during the rendering process,
instead of morphing the individual local models, a morphing between successive
3D-mosaics should take place, as before. For this reason, the term morphable
3D-mosaic is used in this case.Intuitively, each 3D-mosaic should correspond to a
local model produced from a stereoscopic camera with a wider field of view.
Technically, letℒki={𝒳ki,𝒴ki,𝒵ki,ℐki,ℛki},
with i∈{1,…,n},
be the individual local models at the kth key-position. Then, constructing a 3D
mosaic ℒmos={𝒳mos,𝒴mos,𝒵mos,ℐmos,ℛmos} corresponds to filling-in the geometric and
photometric maps of ℒmos based on all maps from {ℒki}i.
To this end, the rotation Rij between each pair of local models ℒki, ℒkj needs to be estimated first. This can be done
very accurately, since no depth information is required for this task.
Essentially, estimating Rij is equivalent to estimating a 2D projective
transformation Hij (the infinite homography induced by the plane
at infinity [3])
relating pixels in photometric images ℐki, ℐkj (and for this, just a sparse set of pixel
correspondences between ℐki, ℐkj needs to be established).The estimated transformationsHij (for all i, j) can then be used for aligning the maps of
all local models {ℒki}i into a common image plane. Furthermore, these
aligned maps can be fused to produce the maps of model ℒmos.
Although this suffices for the construction of the photometric map ℐmos,
it turns out that, before fusing the geometric maps, for example, 𝒵ki to produce 𝒵mos,
an additional rectification step needs to be applied to all these maps 𝒵ki,
so that they become geometrically consistent with each other (recall that the
geometry of each ℒki has been estimated only approximately). To
this end, an operator RECTIFY(𝒵ki→𝒵kj) is defined, whose role is to modify 𝒵ki so that it coincides with 𝒵kj at the intersection ℛki∩ℛkj (this ensures geometric consistency between 𝒵ki, 𝒵kj), but without the relative 3D structure of 𝒵ki in region ℛki−ℛkj being distorted too much. This operator RECTIFY(𝒵ki→𝒵kj) can be easily seen to reduce to solving the
following optimization problem:(17)𝒵ki=argmin𝒵∫∫ℛki∥∇𝒵(p)−∇𝒵ki(p)∥2dp,s.t.𝒵|ℛki∩ℛkj=𝒵k|ℛki∩ℛkjj. This problem is similar to the
problem (13) studied in the previous section, and can thus be reduced to a
Poisson partial differential equation. Obviously, geometric consistency is
ensured simply by applying operator RECTIFY(⋅) to all pairs 𝒵ki, 𝒵kj with i<j,
that is, by solving a set of Poisson PDEs. See Figure 10 for some results
produced with this method.On (a) we show a portion of a 3D-mosaic
constructed by combining two local models. We show the result both when no
geometric rectification is applied to the local models and also when we do
apply a geometric rectification. In the former case, notice the geometric
inconsistency at the boundary between the two local models. On t(b) we
show another 3D-mosaic that has been constructed by combining three local
models.
(a)(b)As already mentioned, an important property of our
geometric rectification algorithm is that the true relative 3D structure is
preserved in the resulting 3D mosaic. This is in deep contrast to other methods
for fusing geometric maps, such as feathering. This is illustrated with the
following toy example. Let us assume that we have 2 local models,ℒleft, ℒright,
that must be fused to produce a 3D mosaic. The true geometry of the 3D mosaic
should consist of a planar object at a constant depth 𝒵true.
Due to noisy observations, however, the left half of this planar object
(corresponding to local model ℒleft) was estimated to have depth 𝒵left=𝒵true−ϵ0,
while the right half of the object (corresponding to local model ℒright) was estimated to have depth 𝒵right=𝒵true+ϵ1.
It is easy to verify that, no matter what the values of ϵ0, ϵ1 are, the 3D mosaic produced by our fusion
algorithm will always be a planar object with constant depth. On the other
hand, when using a feathering-like method, that is, when a weighted linear
combination of 𝒵left, 𝒵right is used for creating the mosaic's depth map,
this depth map will exhibit a high distortion at a zone around the middle of
the object, that is, around the common boundary of ℒleft and ℒright.
Inside this zone, the resulting 3D mosaic will have depths that vary from 𝒵true−ϵ0 to 𝒵true+ϵ1,
and will thus appear highly distorted to the human eye, when visualized. Not
only that, but the higher the error (i.e., the values of ϵ0, ϵ1), the higher the distortion will be. In fact,
since this error is typically proportional to how far the object is from the
camera, this value can be really high for large natural scenes, as is the
distortion in this case.


## 8. Visual Reconstruction of the Samaria Gorge

The “morphable 3D-mosaics” framework has been
successfully applied to the visual 3D reconstruction of the well-known Samaria
Gorge in Crete (a gorge which was recently awarded by the Council of Europe
with a Diploma First Class, as being one of Europe's most beautiful spots).
Based on this 3D reconstruction, and by also using a 3D virtual reality
installation, the ultimate goal of that work has been to provide a lifelike
virtual tour of the Samaria Gorge to all visitors of the National History
Museum of Crete, located in the city of Heraklion. To this end, the most
beautiful spots along the gorge have been selected and for each such spot a
predefined path, that was over 100 meters long, was chosen as well. About 15
key-positions have been selected along each path and approximately 45
stereoscopic views have been acquired at these positions, with 3 stereoscopic
views per position (in this manner, a field of view, that was approximately120o wide, has been covered). Using the
reconstructed morphable 3D-mosaics, a photorealistic walkthrough of the Samaria
Gorge has been obtained, which was visualized at interactive frame rates by
means of a virtual reality system. The hardware equipment that has been used
for the virtual reality system was a common PC (with a Pentium 4 2,4 GHz CPU on
it), which was connected to a single-channel stereoscopic projection system
from Barco. The projection system was consisting of a pair of circular
polarized LCD projectors (Barco Gemini), an active-to-passive stereo converter,
as well as a projection screen, while the rendering was done just on a single
GeForce 6800 3D graphics card (installed on the PC). For the stereoscopic
effect to take place, 2 views (corresponding to the left and right eyes) were
rendered by the graphics card at any time (e.g., see Figure 11) and so the
museum visitors were able to participate in the virtual tour simply by wearing
stereo glasses that were matched to the circular polarization of the
projectors.Two stereoscopic views as would be rendered by the VR system (for
illustration purposes these are shown in the form of red-blue images).
(a)(b)Despite the fact that a common graphics card has
been used, very high frame rates, of about 25 fps in stereo mode (i.e., 50 fps
in monomode), were obtained. On the one hand, this is due to the fact that,
regardless of the actual size of the scene, only one morphable 3D-model needs
to be displayed at any time during rendering. This is an important advantage,
which makes our framework extremely scalable to large-scale scenes. On the
other hand, the achieved frame rates are also due to the highly optimized
rendering pipeline of our system. The reason for this, is that both the
photometric as well as the geometric morphings can be implemented directly on
the GPU. For example, the photometric morphing operation (associated with, say,
morphable modelℒk→k+1) reduces to defining a simple so-called pixel
shader. This is a user-defined script that is automatically executed by the GPU
for each output pixel. In this case, that script should simply be responsible
for blending corresponding pixels (as specified by uk→k+1) from photometric images ℐk and ℐk+1.
Similarly, geometric morphing amounts to a simple vertex blending operation,
that is, an operation that is directly supported by all modern GPUs. Hence,
rendering a morphable model essentially reduces to feeding a textured triangle
mesh into the GPU (with pixel and vertex shaders being applied to this mesh).
This is, of course, a highly optimized rendering path in all modern GPUs, and
thus a considerable amount of acceleration can be attained in this manner.Sample results from the visual
reconstruction of the Samaria gorge are shown in Figure12. That figure
contains some rendered views that were generated in real time as the virtual
camera traversed a path through the so-called Iron Gates area, which is
one of the most famous parts of the gorge. A corresponding video, with just a
short clip from a virtual tour into the Samaria Gorge, is also available at the
URL in [29]. Also,
Figure 13 contains some rendered views of the gorge, where a synthetically
generated volumetric fog has been added to the scene to further enhance the
visual experience of the virtual tour.Figure 12
Some rendered
views that are produced as the virtual camera traverses a path through the
so-called “Iron Gates” area, which is the most famous part of the Samaria
Gorge. In this case, the virtual camera passes through multiple morphable 3D
models.One of the additional benefits of having a virtual 3D reconstruction of
the gorge is the ability, for example, to add synthetic visual effects. Here,
for instance, a synthetically generated volumetric fog has been added to the
scene.
(a)(b)(c)


## 8.1. Extensions

Another
difficulty that we had to face, during the visual reconstruction of the Samaria
Gorge, was related to the fact that a small river was passing through a certain
part of the gorge. This was a problem for the construction of the corresponding
local 3D models as our stereo matching algorithm could not possibly extract
disparity (i.e., find correspondences) for the points on the water surface.
This was the case because the water was not always static and, furthermore, the
sun reflections that existed on its surface were violating the Lambertian
assumption during stereo matching (see Figure14(a)). Therefore, the disparity
for all pixels lying on the water had to be estimated in a different way. To
this end, since the water surface was approximately planar, we made the
assumption that a 2D homography (i.e., a 2D projective transformation
represented by a 3×3 homogeneous matrix ℋwater) can directly map the left-image pixels that
lie on the water to their corresponding points in the right image. For
estimating ℋwater,
we took advantage of the fact that most left-image pixels that are located on
the ground next to the river lie approximately at the same plane as the water
surface and, in addition to that, stereo matching can extract valid
correspondences for these pixels, as they are not on the water. A set {glefti}i=1K of such pixels in the left image is thus
extracted and their matching points {grighti}i=1K in the right image are also computed based on
the already estimated disparity maps. Using this sparse set of matches, the
matrix ℋwater can then be easily recovered via using an
RANSAC-based procedure to cope with outliers in the matches {glefti,grighti}.
Inlier matches found by RANSAC can then be used for refining the estimation of ℋwater by minimizing the total reprojection error E(ℋwater),
that is, the sum of distances between {ℋwater⋅glefti}i=1K and {grighti}i=1K (note that points glefti and grighti are represented in homogeneous
coordinates):(18)E(ℋwater)=∑i∥ℋwater⋅glefti−grighti∥.Given the matrix ℋwater,
the disparity of an image point p on the water surface can then be set equal to ℋwater⋅p−p.
An example of a disparity field that has been estimated with this method can be
seen in Figure 14(c). We should note that, by using a similar method, a 2D
homography ℋwaterk→k+1,
mapping pixels of ℐk lying on the water to their corresponding
pixels in image ℐk+1,
can be computed as well. In this way, we can achieve estimating an optical flow
field uk→k+1 for all the pixels of image ℐk that are lying on the water surface.(a) The left
image of a stereoscopic image pair that has been captured at a region passing
through a small river. (b) The estimated disparity by using a
stereo matching procedure. As expected, the disparity field contains a lot of
errors for many of the points on the water surface. This is true especially for
those points that lie near the sun reflections on the water. (c) The corresponding disparity when a
2D homography is being used to fill the left-right correspondences for the
points on the water. In this case, the water surface is implicitly approximated
by a 3D plane.
(a)(b)(c)


## 9. Conclusions and Discussion

In conclusion, we have presented a new approach
for obtaining photorealistic and interactive walkthroughs of large, outdoor
scenes. To this end, a novel hybrid data structure has been proposed, called
“morphable 3D-mosaics”. The resulting framework offers a series of important
advantages. (1) To start with, no global 3D model of the environment
needs to be assembled, a process which can be extremely cumbersome and
error-prone, especially for large-scale scenes, where many local models need to
be registered to each other. (2) Furthermore, rendering such a global
model would make a very inefficient operation, with no inherent support for
scalability, thus leading to very low frame rates for large-scale scenes. On
the contrary, our method is extremely scalable to large-scale environments, as
only one morphable 3D-model needs to be displayed at any time. (3) On
top of this, it also makes use of a rendering path, which is highly optimized
in modern 3D graphics hardware. (4) Not only that, but by utilizing an
image-based data representation, our framework is also capable of fully
reproducing the photorealistic richness of the scene. (5) As another
advantage, the data acquisition process is very easy (e.g., collecting the
stereoscopic images for a path over 100 meters long took us only about 20
minutes), while it also requires no special or expensive equipment (but just a
pair of digital cameras and a tripod). (6) Finally, our framework makes
up an end-to-end system, thus providing an almost automated processing of the
input data, which are just a sparse set of stereoscopic images from the scene.In the future, we intend to eliminate the need for
calibrating the stereoscopic camera, as well as to allow the stereo baseline to
vary during the acquisition of the stereoscopic views (these enhancements would
allow for an even more flexible data acquisition process). Another issue that
we wish to investigate is the ability of capturing the dynamic appearance of
any moving objects, such as moving water or grass, that are frequently encountered
in outdoor scenes (instead of just rendering these objects as static). To this
end, we plan to enhance our “morphable 3D-mosaic” framework, so that it can
also make use of real video textures that have been previously captured inside
the scene. Finally, a current limitation of our method is that it assumes that
the lighting conditions across the scene are not drastically different
(something which is not always true in outdoor environments). One possible
approach to deal with this issue is by obtaining the radiometric response
function of each photograph. In this case, when constructing the morphable 3D
models, one should also use the estimated response functions so as to
compensate for the image differences due to the varying lighting conditions.



---

*Source: 697454-2008-06-16.xml*