Note: Descriptions are shown in the official language in which they were submitted.
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
PIECEWISE PLANAR RECONSTRUCTION OF THREE-DIMENSIONAL
SCENES
BACKGROUND
[0001] Conventionally, a computer's rendering engines may be configured to
provide
automatic feature matching or feature extraction that recovers camera
calibrations and a
sparse structure of a scene from an unordered collection of two-dimensional
images. The
conventional rendering engine may use the camera calibrations, sparse scene
structure, and
the two-dimensional images to triangulate the location of each pixel in a
three-dimensional
space. The pixels are rendered in the triangulated locations to form a three-
dimensional
scene.
[0002] However, the quality and detail of the generated three-dimensional
scenes often
suffers from various drawbacks. For instance, the conventional rendering
engines may
render textureless or non-Lambertian surfaces captured in the two-dimensional
images as
holes. The holes are covered by interpolating the depth of neighboring pixels.
But the
conventional rendering engine's interpolation may erroneously reproduce flat
surfaces
with straight lines as bumpy surfaces in the three-dimensional scene. The
conventional
rendering engine may also erroneously introduce jaggies in the three-
dimensional scene
because of unreliable matching of the non-Lambertian surfaces, occlusions,
etc.
[0003] The quality and detail of the conventional rendering engines
significantly degrades
when generating three-dimensional scenes of architectural scenes, urban
scenes, or scenes
with man-made objects having plentiful planar surfaces. Moreover, the
reconstruction of
the three-dimensional scene from a sparse collection of two-dimensional images
is not
navigable in a photorealistic manner because the assumptions of the
conventional
computer vision algorithms executed by the conventional rendering engines are
not
designed to work well for scenes containing man made surfaces.
SUMMARY
[0004] Embodiments of the invention overcoming these and other problems in the
art
relate in one regard to a computerized reconstruction system, computer-
readable media,
and computer-implemented method to generate navigable, photo-realistic scenes
from a
collection of two-dimensional images. The computerized reconstruction system
recovers a
dense, piecewise planar reconstruction of a scene captured from the collection
of two-
dimensional images.
[0005] The computerized reconstruction system identifies a discrete set of
three-
dimensional plane candidates. The computerized reconstruction system generates
the
1
CA 02760973 2017-01-25
51045-135
discrete set of three-dimensional plane candidates based on a sparse point
cloud of the scene
and sparse three-dimensional line segments reconstructed from multiple views
captured in the
collection of two-dimensional images. In turn, a piecewise planar depth map is
recovered for
each image by solving a multi-label Markov Random Field (MRF) optimization
problem
using graph-cut based energy minimization techniques. The computerized
reconstruction
system projects the original two-dimensional images onto the recovered planar
depth maps to
generate a rendering of the three-dimensional scene.
[0005a] According to one aspect of the present invention, there is provided a
computer-
implemented method to select planes that are used to render a navigable three-
dimensional
scene from a collection of images stored in an electronic database, the
computer-implemented
method comprising: receiving the collection of images from the electronic
database;
extracting scene information from the collection of images, wherein the scene
information
includes camera calibrations, a three-dimensional point cloud, three-
dimensional line
segments, and data for multi-view correspondence of points and lines;
detecting vanishing
directions within each image in the collection of images using edge detection
and
two-dimensional line segment extraction; identifying each plane in the
navigable
three-dimensional scene based on the vanishing directions and the scene
information; and
generating a Markov Random Field distribution to assign pixels to each plane
based on
minimization functions applied to the Markov Random Field distribution to
optimize a global
cost of assigning the pixel to a plane in the navigable three-dimensional
scene.
[0005b] According to another aspect of the present invention, there is
provided one or more
computer-readable memories having stored thereon computer-executable
instructions, that
when executed perform a method that assigns pixels from two-dimensional images
to three-
dimensional planes when rendering a navigable three-dimensional scene from a
collection of
two-dimensional images stored in an electronic database, the computer-
executable
instructions comprising: receiving the collection of two-dimensional images;
generating a set
of three-dimensional planes from scene information extracted from the two-
dimensional
images, wherein the scene information includes vanishing directions, lines,
and three-
dimensional points; generating a Markov Random Field using the scene
information and the
2
CA 02760973 2016-09-28
51045-135
generated three-dimensional planes; and assigning pixels to the generated
planes to minimize
an energy function represented by the Markov Random Field, which provides
depth maps for
the two-dimensional images, wherein the depth maps are used to render a
navigable
three-dimensional scene.
[0005c] According to still another aspect of the present invention, there is
provided a
computer system having memories and processors that are configured to generate
a navigable
three-dimensional scene from a collection of two-dimensional images, the
computer system
comprising: a plane generator configured to generate a set of three-
dimensional planes from
the scene information extracted from the two-dimensional images; an
optimization engine
configured to estimate a depth map for each of the two-dimensional images and
to define
global and local boundary constraints for assigning pixels from the two-
dimensional images to
the generated planes; and a reconstruction engine to create multiple planar
polygons from the
generate planes, interpolated views, and cross fade views from each image in
the collection
based on the depth maps for the three-dimensional scene.
[0005d] According to yet another aspect of the present invention, there is
provided a
computer-implemented method to select planes that are used to render a
navigable three-
dimensional scene from a collection of images stored in an electronic
database, the computer-
implemented method comprising: receiving, by a computer processor, the
collection of
images from the electronic database; extracting, by the computer processor,
scene information
from the collection of images; detecting, by the computer processor, vanishing
directions
within each image in the collection of images using edge detection and two-
dimensional line
segment extraction to form orthogonal triplets having at least two orthogonal
vanishings
directions; identifying, by the computer processor, each plane in the
navigable
three-dimensional scene based on the vanishing directions and the scene
information; and
generating, by the computer processor, a Markov Random Field distribution to
assign pixels
to each plane based on minimization functions applied to the Markov Random
Field
distribution to optimize a global cost of assigning the pixel to a plane in
the navigable three-
dimensional scene, wherein a portion of the global cost of plane-pixel
assignments is
represented by smoothness terms included in the minimization functions applied
to a Markov
Random Field distribution graph, the smoothness terms are calculated to prefer
transitions
2a
CA 02760973 2016-09-28
,
51045-135
between planes at pixels corresponding to discontinuities at two-dimensional
lines that are
consistent with the vanishing directions orthogonal to the normal vector of an
occluding
plane.
[0005e] According to a further aspect of the present invention, there is
provided one or more
computer-readable memories having stored thereon, computer-executable
instructions, that
when executed, to perform a method that assigns pixels from two-dimensional
images to
three-dimensional planes when rendering a navigable three-dimensional scene
from a
collection of two-dimensional images stored in an electronic database, the
computer-
executable instructions comprising: receiving the collection of two-
dimensional images;
generating a set of three-dimensional planes from scene information extracted
from the
two-dimensional images; generating a Markov Random Field using the scene
information and
the generated three-dimensional planes; assigning pixels to the generated
planes to minimize
an energy function represented by the Markov Random Field, which provides
depth maps for
the two-dimensional images, wherein data terms penalize assigning a pixel in
one image to a
plane if the corresponding pixel in neighboring images did not choose the same
plane during
an iterative pass on each two-dimensional image; and rendering a three-
dimensional scene
using the depth map and projections of the two-dimensional images onto their
corresponding
depth maps, wherein cross fading between multiple two-dimensional images
allows smooth
view interpolation for each of the two-dimensional images in the collection.
[0005f] According to yet a further aspect of the present invention, there is
provided a
computer system having memories and processors that are configured to generate
a navigable
three-dimensional scene from a collection of two-dimensional images, the
computer system
comprising: a plane generator configured to generate a set of three-
dimensional planes from
the scene information extracted from the two-dimensional images; an
optimization engine
configured to estimate a depth map for each of the two-dimensional images and
to define
global and local boundary constraints for assigning pixels from the two-
dimensional images to
the generated planes; and a reconstruction engine to create multiple planar
polygons from the
generated planes, interpolate views, and cross fade views from each image in
the collection
based on the depth maps for the three-dimensional scene.
2b
CA 02760973 2016-09-28
51045-135
[0006] This summary is provided to introduce a selection of concepts in a
simplified form that
are further described below in the detailed description. This summary is not
intended to
identify key features or essential features of the claimed subject matter, nor
is it intended to be
used in isolation as an aid in determining the scope of the claimed subject
matter.
BRIEF DESCRIPTION OF THE DRAWINGS
[0007] Fig. 1 is a network diagram that illustrates an exemplary computing
system in
accordance with embodiments of the invention;
[0008] Fig. 2 is an image diagram that illustrates exemplary two-dimensional
images in
accordance with embodiments of the invention; Fig. 2A-B illustrate two-
dimensional images
captured by a camera, in accordance with embodiments of the invention;
[0009] Fig. 3 is a plane diagram that illustrates exemplary three-dimensional
planes in
accordance with embodiments of the invention; Fig. 3A illustrates the
structure from motion
feature extraction and camera calibration determinations, in accordance with
embodiments of
the invention; Fig. 3B illustrates the three-dimensional lines generated by a
computerized
reconstruction server, in accordance with embodiments of the invention; Figs.
3C-3E
illustrates candidate planes for the different three-dimensional viewpoints
generated by the
computerized reconstruction server, in accordance with embodiments of the
invention;
[0010] Fig. 4 is a three-dimensional scene diagram that illustrates an
exemplary scene
generated by the computing system in accordance with embodiments of the
invention; Fig. 4A
illustrates a depth map generated by the computerized reconstruction server,
in accordance
with embodiments of the invention; Fig. 4B illustrates proxy meshes generated
by the
computerized reconstruction server, in accordance with embodiments of the
invention;
Fig. 4C illustrates textured proxy meshes generated by the computerized
reconstruction
server, in accordance with embodiments of the invention;
[0011] Fig. 5 is a vanishing direction diagram that illustrates detection of
vanishing direction
within two-dimensional images in accordance with embodiments of the
2c
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
invention; Fig. 5A illustrates an exemplary two dimensional image that is
processed by the
computerized reconstruction system to extract vanishing directions, in
accordance with
embodiment of invention; Fig. 5B illustrates the orientation of each cluster
of vanishing directions
extracted from the two-dimensional image, in accordance with embodiments of
the invention; Fig.
5C illustrates an exemplary reconstruction of a three-dimensional scene
rendered by the
computerized server, in accordance with embodiments of the invention;
[0012] Fig. 6 is a normal orientation diagram that illustrates probable
distribution of
surface normals in accordance with embodiments of the invention; FIG. 6A
illustrates a
measure of the covariance for three-dimensional points, in accordance with
embodiments of the
invention; FIG. 6B illustrates the distribution of the normal for the planes
that pass through a
three-dimensional point, in accordance with embodiments of the invention;
[0013] Fig. 7 is a distribution histogram that illustrates probable
distribution of the
orientation of the planes or three-dimensional lines in accordance with
embodiments of the
invention; Fig. 7A illustrates a histogram that represents the distribution of
normals based on
votes from three-dimensional points, in accordance with embodiments of the
invention; FIG. 7B
illustrates a histogram that represents the distribution of normals based on
votes from the three-
dimensional lines, in accordance with embodiments of the invention;
[0014] Fig. 8 is a visibility diagram that illustrates scene information
extracted from the
two-dimensional images in accordance with embodiments of the invention;
[0015] Fig. 9 is a graph diagram that illustrates assignment of pixels to
labels that
represent planes using a Markov Random Field representation and graph cut
minimization
in accordance with embodiments of the invention;
[0016] Fig. 10 is a photo-consistency diagram that illustrates the
relationship between
two-dimensional images used to generate the three-dimensional scenes in
accordance with
embodiments of the invention; Fig. 10A illustrates an exemplary reference
image, in
accordance with embodiments of the invention; Fig. 10B illustrates an
exemplary warped
neighbor image that is used by the computerized reconstruction system, in
accordance
with embodiments of the invention; Fig. 10C illustrates a measure of the photo
consistency between the reference image and the warped image determined by the
computerized reconstruction server, in accordance with embodiments of the
invention;
[0017] Fig. 11 is a boundary diagram that illustrates crease edges
corresponding to the
intersection of a pair of planes and occlusion boundaries for planes in the
three-
dimensional scene in accordance with embodiments of the invention; FIG. 11A
illustrates
3
CA 02760973 2016-09-28
51045-135
crease edges, in accordance with embodiments of the invention; FIG. 11B
illustrates
occlusion boundaries in accordance with embodiments of the invention;
[0018] Fig. 12A-B are transition diagrams that illustrate navigation between
view points
in a three-dimensional playhouse scene, in accordance with embodiments of the
invention;
[0019] Fig. 13A-B are transition diagrams that illustrate navigation between
view points
in the three-dimensional shed scene, in accordance with embodiments of the
invention;
[0020] Fig. 14A-B are transition diagrams that illustrate navigation between
view points
in the three-dimensional arch scene, in accordance with embodiments of the
invention;
[0021] Fig. 15A-B are transition diagrams that illustrate navigation between
view points
in the three-dimensional castle scene, in accordance with embodiments of the
invention;
[0022] Fig. 16A-B are transition diagrams that illustrate navigation between
view points
in the three-dimensional room scene, in accordance with embodiments of the
invention;
[0023] Fig. 17A-E are transition diagrams that illustrate navigation between
view points in
the three-dimensional lobby scene, in accordance with embodiments of the
invention;
[0024] Fig. 18 is a logic diagram that illustrates a method to select planes
that are used to
render a navigable three-dimensional scene from a collection of images stored
in an
electronic database in accordance with embodiments of the invention; and
[0025] Fig. 19 is a logic diagram that illustrates a method that assigns
pixels from two-
dimensional images to three-dimensional planes when rendering a navigable
three-
dimensional scene from a collection of two dimensional images stored in an
electronic
database.
DETAILED DESCRIPTION
[0026] This patent describes the subject matter for patenting with specificity
to meet
statutory requirements. However, the description itself is not intended to
limit the scope
of this patent. Rather, the inventors have contemplated that the claimed
subject matter
might also be embodied in other ways, to include different steps or
combinations of steps
similar to the ones described in this document, in conjunction with other
present or future
technologies. Moreover, although the terms "step" and "block" may be used
herein to
connote different elements of methods employed, the terms should not be
interpreted as
implying any particular order among or between various steps herein disclosed
unless and
except when the order of individual steps is explicitly described. Further,
embodiments
are described in detail below with reference to the attached drawing figures.
4
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
[0027] Embodiments of the invention provide a computerized reconstruction
system that
generates navigable three-dimensional scenes from a collection of two-
dimensional
images. The two-dimensional images are processed by the computerized
reconstruction
system to extract matching features, camera calibrations, and geographic or
spatial
information. In turn, the computerized reconstruction system automatically
detects
vanishing directions from the two-dimensional images. The matching features,
camera
calibrations, spatial information, and vanishing directions are used by the
computerized
reconstruction system to generate a set of plane candidates for the three-
dimensional
scene. The probable orientation for the set of plane candidates is determined
and a
Markov Random Field is generated by the computerized reconstruction system. In
turn, a
minimization function corresponding to the Markov Random Field is used by the
computerized reconstruction system to generate the three-dimensional scene
from the two-
dimensional images by assigning pixels from the two-dimensional images to the
set of
candidate planes.
[0028] As one skilled in the art will appreciate, the computerized
reconstruction system
may include hardware, software, or a combination of hardware and software. The
hardware includes processors and memories configured to execute instructions
stored in
the memories. In one embodiment, the memories include computer-readable media
that
store a computer-program product having computer-useable instructions for a
computer-
implemented method. Computer-readable media include both volatile and
nonvolatile
media, removable and nonremovable media, and media readable by a database, a
switch,
and various other network devices. Network switches, routers, and related
components are
conventional in nature, as are means of communicating with the same. By way of
example, and not limitation, computer-readable media comprise computer-storage
media
and communications media. Computer-storage media, or machine-readable media,
include media implemented in any method or technology for storing information.
Examples of stored information include computer-useable instructions, data
structures,
program modules, and other data representations. Computer-storage media
include, but
are not limited to, random access memory (RAM), read only memory (ROM),
electrically
erasable programmable read only memory (EEPROM), flash memory or other memory
technology, compact-disc read only memory (CD-ROM), digital versatile discs
(DVD),
holographic media or other optical disc storage, magnetic cassettes, magnetic
tape,
magnetic disk storage, and other magnetic storage devices. These memory
technologies
can store data momentarily, temporarily, or permanently.
5
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
[0029] FIG. 1 is a network diagram that illustrates an exemplary operating
environment
100, according to an embodiment of the present invention. The operating
environment
100 shown in FIG. 1 is merely exemplary and is not intended to suggest any
limitation as
to scope or functionality. Embodiments of the invention are operable with
numerous other
configurations. With reference to FIG. 1, the operating environment 100
includes a
computerized reconstruction server 110, two-dimensional images 120, three-
dimensional
scenes 130, a laptop 140, multimedia capture devices 150 and 160, a file
server 170, a
personal computer 180, a satellite 190, and a mobile device 195 in
communication with
one another through a network 113.
[0030] The computerized reconstruction server 110 is configured to generate a
navigable
three-dimensional scene 130. The computerized reconstruction server 110
includes a
plane generator 111, an optimization engine 112, a reconstruction engine 113,
and
multimedia indices 114. The computerized reconstruction system may receive a
request to
generate a three-dimensional scene 130 from a computing device (e.g., laptop
140,
multimedia capture devices 150 and 160, file server 170, personal computer
180, satellite
190, and mobile device 195). The requests may include a collection of two-
dimensional
images 120 that is transmitted to the computerized reconstruction server 110.
The
computerized reconstruction server stores the collection of two-dimensional
images 120 in
the multimedia indices 114.
[0031] The plane generator 111 is configured to identify candidate planes from
camera
and scene information included in the two-dimensional images 120. In turn, the
plane
generator 111 determines the probable orientation for each candidate plane,
and clusters
the candidate planes sharing similar probable orientations. In some
embodiments, the
plane generator 111 creates a ground plane and back plane to represent the
boundaries of
the three-dimensional scene 130.
[0032] The plane generator 111 extracts global scene information from the two
dimensional images 120. The global scene information, may includes three
dimensional
points and coordinates, vanishing directions, three-dimensional line segments,
and
measure of the correspondence of three-dimensional points, three-dimensional
lines, and
vanishing directions from multiple views of a scene captured in the two-
dimensional
images 120. In one embodiment, the plane generator 111 executes a modified
Random
Sample Consensus (RANSAC) algorithm to detect the candidate planes using the
global
scene information.
6
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
[0033] The plane generator 111 may extract the three-dimensional points and
coordinates
from the two-dimensional images 120 and any associated metadata provided by
the
camera that captured the scene. The metadata provided by the camera may
include
location information, distance information, and any other camera calibration
information.
Thus, the plane generator 111 may use the metadata and two-dimensional images
120 to
generate a spatial three-dimensional point for the each pixel in the two-
dimensional image.
In some embodiments, the plane generator 111 groups pixels into super-pixels
based on
similarity.
[0034] The vanishing directions in the scene captured by the two-dimensional
images 120
are detected by the plane generator 111. In one embodiment, an edge detection
algorithm
is executed by the plane generator 111 to detect the vanishing directions in
the two-
dimensional images 120. The edge detection algorithm provides two-dimensional
line
segments included in the two-dimensional image 120. The two-dimensional line
segments
are connected to form an edge map for each image in the collection of two-
dimensional
images. And the lines or line segments in each edge map that correspond to
parallel lines
in three dimensions are detected by the plane generator 111. Vanishing points
in the
images correspond to vanishing directions in the three-dimensional scene. The
plane
generator 111 performs a mean-shift clustering on the unit sphere of vectors
corresponding
to the vanishing directions. The clusters that have a large number of
vanishing directions
are retained by the plane generator 111 and the sparse clusters are discarded.
The plane
generator 111 identifies a representative vanishing direction for each cluster
using each
two-dimensional line segment from the different views of the scene included in
the cluster.
In some embodiments, the plane generator 111 inspects the set of vanishing
directions for
pairs that are almost orthogonal to each other and adds a third vanishing
direction that
completes an orthogonal triplet unless the orthogonal triplet is already
present in the set.
[0035] The three-dimensional line segments are constructed by the plane
generator 111,
which uses epipolar constraints and the global scene information to identify
matching line
segments. The plane generator 111 searches for pairs of two-dimensional line
segments
having similar vanishing directions and with proximal matching points of
interest in the
scene captured by the two-dimensional image. The multiple matching pairs of
two-
dimensional lines are linked together and the plane generator 111 verifies the
consensus
for the three-dimensional line from a number of views of the scene captured by
the two-
dimensional image. In some embodiments, the number of views used for
verification is at
least four. The three-dimensional lines are computed by triangulating the two-
dimensional
7
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
segment pairs and finding the pair that has the overall minimum reprojection
error within
the linked two-dimensional segments. In turn, the plane generator 111
determines the
endpoints of the three-dimensional line segment via interval analysis. In some
embodiments, the plane generator 111 looks for two-dimensional segments that
are not
constrained by the identified vanishing directions. These additional two-
dimensional
segments (outliers) are clustered based on their direction and covariance.
[0036] The plane generator 111 determines the orientation of the planes and
probable
location of each three-dimensional point based on the generated three-
dimensional lines
and the identified vanishing directions. A set of likely plane orientations {
hi } is generated
by the plane generator 111 by evaluating the cross-product of every pair of
vanishing
direction. In certain embodiments, plane orientations hi within five degrees
of each other
are treated as duplicates. The plane generator 111 sorts the set of likely
plane orientations
{hi} based on saliency. The saliency of each plane orientation hi is measured
by counting
size of the clusters associated with the corresponding pair of vanishing
directions.
[0037] The probable location of each three-dimensional point is determined by
the plane
generator 111. In one embodiment, a three-dimensional Mahalonobis distance is
computed by the plane generator 111 for each three-dimensional point to
determine
whether the three-dimensional point belongs to one or more plane hypothesizes
represented by the three-dimensional lines and vanishing directions. The
Mahalonobis
distance measures the covariance (uncertainty) of the three-dimensional point
and
corresponding fitting error of the plane hypothesis. In certain embodiments,
the plane
generator 111 identifies an approximate uncertainty for each three-dimensional
point Xk
by computing a vector Wk oriented along the mean viewing direction of the
scene captured
by the two-dimensional images 120. The magnitude of the vector IV' k
corresponds to the
projected uncertainty of a pixel in the two-dimensional images 120. The
magnitude of the
vector Wk may be used by the plane generator 111 to evaluate the uncertainty
of the plane
hypothesizes.
[0038] The surface normal for each three-dimensional point Xk is determined by
the
plane generator 111 based on a discrete likelihood distribution over the set
of plane
orientations { hi }. Each oriented plane passing through the three dimensional
point Xk is
given a score by the plane generator 111 based on the number of neighboring
three-
dimensional points around the three-dimensional point Xk and the robust
variance along
8
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
one dimension of the oriented plane. The plane generator 111 assigns a surface
normal to
each three-dimensional point having a dense neighborhood with unique peaks
along one
dimension of the oriented plane likelihood distribution. The surface normal
assigned to
the three-dimensional point restricts the assignment of the corresponding
three-
dimensional point to three-dimensional planes. In some embodiment, the plane
generator
111 uses line direction of a three-dimensional line to decide which planes the
three-
dimensional line may vote for during assignment of planes and three-
dimensional lines.
Similarly, the surface normal of a three-dimensional point may be used by the
plane
generator 111 to decide which planes the three-dimensional point may vote for
during
assignment of three-dimensional points to planes.
[0039] Each three-dimensional point and three-dimensional line are used by the
plane
generator 111 to determine the planes of a scene captured by the two-
dimensional image
120. The plane generator 111 builds two histograms (Hi' Hi2) to measure the
votes for
each orientation hi received from the three-dimensional points and three-
dimensional
lines. The plane generator 111 counts a vote from each three-dimensional point
and three-
dimensional line when a location associated with the cameras that captured the
corresponding two-dimensional image 120 is positioned in front of the plane.
The plane
generator 111 does not count a vote for each three-dimensional point and three-
dimensional line having estimated normals that fail to match the orientation
hi of the
plane. In some embodiments, the plane generator 111 filters each three-
dimensional point
and three-dimensional line having estimated normals that fail to match the
orientation hi
of the plane.
[0040] In one embodiment, three-dimensional points and three-dimensional lines
are
sampled by the plane generator 111 to obtain a representative collection of
three-
dimensional points and three-dimensional lines that are used to create the
histograms (Hi'
Hi2). The set of samples (51) for the three-dimensional points are constructed
by the
following S1 ={xk:xk = h = Xk}. The set of samples (S2) for the three-
dimensional lines
are constructed by the following S2 = {yk : yk = h = Yk}, where Yk represents
the three-
dimensional lines.
[0041] Each three-dimensional point sample xk is represented by an adaptive
Gaussian
kernel of size (Wk = hi ). The size of the kernel is adapted by the plane
generator 111 to
9
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
account for the uncertainty associated with each three-dimensional point. The
plane
generator 111 assigns a weight (W) to control the smoothness of histogram Hi2.
In turn,
the plane generator 111 creates a one-dimensional subspace orthogonal to ñ and
projects
each three-dimensional point sample xk in the one-dimensional subspace to
determine if
the three-dimensional point samples share the orientation hi . For each match,
the count in
the histogram Hi2 for the current orientation hi increases.
[0042] Each three-dimensional line sample yk is represented by an adaptive
Gaussian
kernel of size (lYk1W1715k = ñ). The size of the kernel is adapted to account
for the
uncertainty associated with each three-dimensional line. W is weight assigned
to controls
the smoothness of histogram Hi2. In turn, the plane generator 111 creates a
one-
dimensional subspace orthogonal to hi and projects each three-dimensional line
sample
yk in the one-dimensional subspace to determine if the three-dimensional line
sample
shares the orientation hi . For each match, the count in the histogram Hi2 for
the current
orientation hi increases.
[0043] The plane generator 111 detects local peaks in both histogram (Hi1
Hi2). In
certain embodiments, the plane generator counts peaks in Hi2 when a three-
dimensional
line has multiple 2) unique directions all orthogonal to hi because
multiple parallel
three-dimensional lines are often accidentally co-planar and non parallel
lines are less
likely to be coplanar unless a real plane exists in the scene. Also, the plane
generator 111
performs non-maximal suppression to avoid generating candidate planes that are
too close.
In turn, the candidate planes are generated based on any combination of peak
orientations,
three-dimensional points, and three-dimensional lines.
[0044] In other embodiments, the plane generator 111 provides additional
planes for
outlier portions of a scene captured by the two-dimensional images 120, ground
planes,
and back planes. Outlier portions are regions of the two-dimensional image 120
having
sparse global scene information. The plane generator 111 may execute a random
sampling
of three-dimensional points and vanishing directions using a two-point or
three-point
RANSAC algorithm. In turn, the uncertainty of the associated three-dimensional
points is
calculated by the plane generator 111 and the orientation of the additional
planes passing
through the three-dimensional points is determined to identify a set of
candidate planes.
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
[0045] The plane generator 111 also computes a ground plane and back-plane for
each
view of the two-dimensional image captured by the camera. The ground plane is
estimated by selecting the up vector orthogonal to the side vector of the
camera. The
ground plane is identified as a plane orthogonal to the up vector and having
95% of the
three-dimensional points positioned above the plane. In turn, the plane
generator 111
refines the ground plane to better represent the ground in the three-
dimensional scene.
[0046] The back plane is estimated by selecting the vector orthogonal to the
optical axis of
the camera. The back plane is identified as a plane orthogonal to the optical
axis and
having 95% of the three-dimensional points positioned in front of the plane.
In turn, the
plane generator 111 may optimize the back plane to better represent the back
ground in
three-dimensional scene.
[0047] The optimization engine 112 is configured to generate a depth map for
each two-
dimensional image using the candidate planes provided by the plane generator
111. The
optimization engine 112 generates a Markov Random Field (MRF) using the
candidate
planes and the pixels in the two-dimensional image. The optimization engine
112
generates a graph having nodes that represent pixels and planes. The graph
also included
edges that connect the nodes of the graph. Each edge is associated with a cost
that
represents the penalty for assigning different plane labels to the two pixels
that the edge
connects. The optimization engine 112 evaluates an objective function that
measures the
consistency of plane label assignment to pixels in the image. In some
embodiments, the
optimization engine 112 uses an energy function E to determine the optimal
labeling of
the pixels.
[0048] The energy function E represents a log likelihood of a posterior
probability
distribution in a MRF defined on the underlying pixel data with a neighborhood
system
(e.g. A 4-connected neighborhood considers all vertical and horizontal
neighbor pixels).
The optimization engine 112 may evaluate E(1)=EDp(1p)+Evp,q(lp,/q). Each plane
P PA'
P corresponds to a label 1. Each pixel corresponds to a point p in the image
and may be
assigned a label /p . The set of labels is finite and is chose from a closed
set /p c L. The
energy function E includes a data term and a smoothness term. The data term D
p allows
the optimization engine 112 to measure the cost (penalty) of pixel p being
assigned the
label /p . The smoothness term V p,q, allows the optimization engine 112 to
encourage a
piecewise smooth labeling (i.e. regularizes the solution) by assigning a cost
whenever
11
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
neighboring pixels p and q are assigned labels /p and 'q' respectively. In
certain
embodiments, Vp,g, is a metric and the optimization engine 112 may execute an
expansion
move algorithm to compute a label assignment that is within a provable
distance from a
global optimum.
[0049] In some embodiments, the optimization engine 112 may select labels /p
for a
subset of planes M c P. The subset of planes is denoted by M =}mi},i =1....N
and each
selected plane mi faces the camera and lies within the view frustum of the
camera. The
optimization engine 112 may sort the planes mi based on density of pixels
associated with
a location that corresponds to the location of the plane mi . Additionally,
the optimization
engine may include the ground plane and back plane in the subset of planes M
based on
the location of the horizon in the collection of two-dimensional images.
[0050] In one embodiment, the optimization engine 112 measures Dp by combining
multi-view photo consistency, geometric proximity of three-dimensional points
and lines,
and ray visibility of the three-dimensional points and planes. Dp measures the
cost of
assigning label /p (i.e. plane mp ) to pixel p. Dp=Dpi (1p)+Dp2(1p)+D3p(ip),
where Dpi
is the multi-view photo-consistency , Dp2 is the geometric proximity of sparse
three-
dimensional points and lines, and D3p measures free space violations based ray
visibility
of three-dimensional points and planes. In an embodiment, the optimization
engine 112
may densely measure Dpi at each pixel, and employ sparse constraints to
measure Dp2 and
D3 at specific pixels in one or more two-dimensional images 120.
[0051] The optimization engine 112 measures the multi-view photo-consistency
Dpi by
selecting a number of views from neighboring images of a reference image and
measures
the similarity between the views of the neighboring images and the reference
image. In
one embodiment, the optimization engine 112 selects k(10) neighboring images
I, for a
reference image 'r= In turn, the optimization engine 112 generates
homographies by the
plane mp to warp each neighboring image I, into the reference image 'r= The
warped
image /7 and the reference image /, are used by the optimization engine 112 to
measure
a Normalized Cross Correlation (NCC) at each pixel p in a pxp path of the
warped
12
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
image /7 and the reference image /, . In some embodiments, p = 9 and the NCC
measure the similarity of pixels of the reference image wr(p) and pixels of
the warped
image w j(p) . The optimization engine 112 may account for the uncertainty in
the
location of the candidate planes with a disparity range d. The disparity range
gp may be
centered around plane nep and the optimization engine 112 may search for a
best match
within the disparity range. In some embodiments, the optimization engine
rectifies the
two-dimensional images (/,, /7) when seeking for the best match. The measure
of NCC
associated with each plane is
M1(p)= max(NCC(wr(p),1 v JO), where
q = (p ¨ d, p + d). The similarity measure for each neighbor image is averaged
in the
overall measure of similarity that is used to evaluate
D.
Di (1v
) = ¨K (1¨ exp( (1¨ m(p))2)) where a = .8 and K = 300. In an embodiment, the
optimization engine 112 may treat occlusions in the images as outliers when
evaluating the
similarity scores.
[0052] The optimization engine 112 measures the geometric proximity of sparse
three-
dimensional points and lines D. . The optimization engine 112 selects each
three-
dimensional point identified as an inlier of plane mp . In turn, the closest
three-
dimensional point on the plane nep is selected by the optimization engine 112.
The three-
dimensional points that are the inlier of the plane nep and on the plane nep
are projected
on a reference three-dimensional view at pixels q and , respectively. The
optimization
engine 112 evaluates D_;:, (/,) = max(100, d(q,q')2) for all pixels p within a
three by three
window around q to determine the geometric proximity of the three-dimensional
point.
The optimization engine 112 measures the geometric proximity of sparse three-
dimensional lines Dp2 using the endpoints of the three-dimensional line and
evaluating the
reprojection error of each endpoint.
[0053] The optimization engine 112 measures the free space violations based on
ray
visibility of three-dimensional points and planes and D. . The optimization
engine 112
assigns a large penalty to pixel-plane assignments that violate a free-space
constraint. A
three-dimensional point X or line segment L matched to a view captured by one
or more
two dimensional images should be visible in the corresponding views in the
three-
13
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
dimensional scene. The optimization engine 112 identifies the three-
dimensional point X
or line segment L that should be visible and identifies rays that correspond
to the three-
dimensional point X or line segment L. The optimization engine 112 locates any
planes
that intersect the three-dimensional point X or line segment L and applies a
free-space
violation penalty. In one embodiment, the set of three-dimensional points F on
each plane
m that represents the location where a ray plane intersection occurs is
identified by the
optimization engine 112. In turn, D ( /p ) = K is assigned by the optimization
engine 112
for each N e F that projects into a view of the three-dimensional scene for
all pixels p in
a three by three window around pixel q associated with the three-dimensional
point. N.
[0054] The smoothness terms V p,q, are assigned by the optimization engine 112
to
efficiently assign pixels and labels at boundaries in the three-dimensional
scene. The
optimization engine 112 encourages piecewise constant labeling with suitable
discontinuities. The smoothness terms impose geometric constraints derived
from plane
arrangements and vanishing directions that enable the optimization engine 112
to recover
accurate label boundaries. In some embodiments, the optimization engine 112 is
configured to identify occlusion edges and crease edges in the two-dimensional
images
that are part of the three-dimensional scene. The depth maps associated with
the three-
dimensional scene may include both occlusion edges and crease edges, which may
represent the planar discontinuities. At the occlusion edges both plane labels
and scene
depths differ at pixels moving across the occlusion edge. Occlusion edges may
occur
anywhere in the two-dimensional images. But for planar scenes the occlusion
edges
typically coincide with visible two dimensional line segments in the two-
dimensional
images. At the creases edges only the plane labels differs for pixels across
the crease
edge. The crease edge between a pair of plane labels coincides with the
projection of a
three-dimensional intersection line of the two corresponding planes and is
therefore
always a straight line segment.
[0055] In another embodiment, the optimization engine 112 may simultaneously
estimate
the planar geometry for each two-dimensional image in the collection of two-
dimensional
images. The estimated planar geometry of the three-dimensional scene may have
inconsistencies. The optimization engine 112 detects the inconsistencies by
rendering a
ray through a pixel in each two-dimensional image to a candidate plane
corresponding to
that pixel to locate a three-dimensional point. The optimization engine 112
may reproject
the three-dimensional point onto a pixel in a neighboring image to determine
if the plane
14
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
assigned to the pixel in the neighboring image corresponding to the three-
dimensional
point matches the candidate plane in the original two-dimensional image. The
optimization engine 112 may deal with inconsistencies by adding smoothness
terms that
penalize inconsistent pixel-plane assignments. For each possible plane choice
at a pixel, a
smoothness term that connects the plane to the corresponding pixel in a
neighboring image
is determined. If the pixel-plane assignment in the corresponding neighboring
pixel
disagrees, then a penalty is added as a smoothness term to the global cost
calculated by an
optimization function employed by the optimization engine 112.
[0056] In one embodiment, the optimization engine 112 detects the occlusion
edges and
crease edges by identifying line segments in the two-dimensional images. The
label
boundaries that pass through two-dimensional line segments are used to locate
the
occlusion and crease edges. In some embodiments, vanishing directions are used
by the
optimization engine to signal a preference for straight line occlusion edges.
[0057] The optimization engine 112 evaluates a piecewise definition for the
smoothness
terms in the three-dimensional scene. The neighboring planes lp and /q
associated with
neighboring pixels (p, q) are used to evaluate the smoothness terms.
[0058] / = /q then V (/p /q ) = 0.
P
iff(19,q,1 p,1q)e s1
[0059] /p # /q then V p,q(1 p ,1q) = 22 iff(p,q,1p,lq)e S2 or if
(p,q) e S3 .
23 otherwise
[0060] In some embodiments, 2 = 1000, 2 = 1200, and 23 = 2000.
[0061] The optimization engine 112 determines a set of crease lines ILO for
all plane
pairs ( mj) in the subset of planes M and selects the planes /, and 11
that are within the
boundaries of the two-dimensional image. For each plane /, and / j , the
optimization
engine 112 locates pairs of neighboring pixels (p,q) in the two-dimensional
image, where
p and q are on different sides of /, and / j . The optimization engine 112
creates a set S1
with a four-tuple combination of (p,q,1,1 j).
[0062] The optimization engine 112 determines a set of occlusion lines {Lik} .
Vanishing
directions orthogonal to the normal for each plane mi are used to locate the
occlusion
lines. The two-dimensional line segments that support the identified vanishing
directions
are used to locate pairs of neighboring pixels (p, q) in the two-dimensional
image, where
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
p and q are on different sides of /, and /k . The optimization engine 112
creates a set S2
with a four-tuple combination of ( p,q,1õ11). The set S2 is populated by the
optimization
engine 112, which back projects a ray from the midpoint ofp and q to obtain a
list of
planes {mk } that are beyond {m,} when sorted based on distance from the
camera.
[0063] The remaining two-dimensional line segments are identified by the
optimization
engine 112. And a set S3 of the neighboring pixels (p, q) that support the two
dimensional lines is generated. The smoothness term allows the optimization
engine 112
to effectively represent planes with discontinuities included in the three-
dimensional
scene.
[0064] The reconstruction engine 113 is configured to provide navigation
within the three-
dimensional scene based on the optimizations on the three-dimensional planes
and
associated pixels provided by the optimization engine. In one embodiment, a
graph-cut
optimization provides the depth maps and proxy meshes that are used to
generate the
navigable three-dimensional scene. The reconstruction engine 113 may convert
each label
image in the collection of two-dimensional images to a two-dimensional
triangulation. In
some embodiments, the reconstruction engine uses a polyline simplification on
the label
boundaries to generate the triangulation of the two-dimensional image. In
turn, the
triangulation of the two-dimensional images is mapped by the reconstruction
engine 113
directly to a set of three-dimensional triangles that are formed from the
planes
corresponding to labels.
[0065] In turn, projective texture mapping is applied to the set of three-
dimensional
triangles by the reconstruction engine 113 to allow view interpolation among
multiple
two-dimensional images. During view interpolation, the reconstruction engine
113
projectively texture maps each two-dimensional image onto its corresponding
proxy
meshes.
[0066] The texture mapping performed by the reconstruction engine 113 may
produce
blended and cross-faded planes that represent the three-dimensional scene. The
blended
colors ( C1, C2) for each pixel are determined by reconstruction engine, which
evaluates
the following:
(1¨/1)C1 + pC2
[0067] C =, where 0 p 1
(1¨ ,u)a + ,ua 2
16
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
1 if pixies have valid depth after warping
[0068] and al and a2 = .
0 otherwise
[0069] The reconstruction engine 113 is configured to provide transitions with
pixels in
the interpolated views of the three-dimensional scene covered only by one
source image to
be rendered at full opacity throughout the transitions. The reconstruction
engine 113
linearly cross-fades pixels with contributions from multiple images during the
view
interpolation. The cross-fading preformed by the reconstruction engine 113
prevents the
viewer from focusing on disoccluded regions of a two-dimensional image that
are filled in
by the other two-dimensional image.
[0070] A user may provide a collection of two-dimensional images to the
computerized
reconstruction server that reconstructs a three-dimensional scene.
Alternatively, the user
may execute a three-dimensional reconstruction program on a local computer to
reconstruct a three-dimensional scene from two-dimensional images located on
the local
computer. The three-dimensional scene is navigable and provides the user with
an
immersive experience of the scene captured by the two-dimensional images.
[0071] Fig. 2 is an image diagram that illustrates exemplary two-dimensional
images in
accordance with embodiments of the invention. The two-dimensional images
capture
different views of a home. In one embodiment, the two-dimensional images of
FIG. 2A
and 2B are captured by a camera. In turn, the two-dimensional images are
processed by
the computerized reconstruction server to generate a three-dimensional scene.
[0072] In some embodiments, the three-dimensional scene is reconstructed by
performing
structure from motion on each two-dimensional image to extract image features
and
camera calibrations. In turn, the image features and camera calibrations are
used by the
computerized reconstruction server to identify candidate planes for the three-
dimensional
scene. The plane candidates are organized by the computerized reconstruction
server and
rendered based on overall global consistency within the three-dimensional
scene.
[0073] Fig. 3 is a plane diagram that illustrates exemplary three-dimensional
planes in
accordance with embodiments of the invention. FIG. 3A illustrates the
structure from
motion feature extraction and camera calibration determinations performed by
the
computerized reconstruction server on the two-dimensional images that capture
different
views of the scene. The image features (e.g., lines, points, colors, pixels,
etc.) and camera
calibrations (e.g., orientation, location, etc.) are used to generate three-
dimensional lines
and planes. FIG. 3B illustrates the three-dimensional lines generated by the
computerized
17
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
reconstruction server. FIG. 3C-3E illustrates the candidate planes for the
different three-
dimensional viewpoints generated by the computerized reconstruction server.
[0074] The computerized reconstruction server generates a depth map and proxy
mesh of
the three-dimensional scene based on the image features and camera
calibrations. In turn,
the three-dimensional scene is rendered using estimated three-dimensional
planes, depth
maps, and proxy meshes. In some embodiment, the computerized reconstruction
system
colors the three-dimensional scene and provides transitions between viewpoints
associated
with the three-dimensional scenes.
[0075] Fig. 4 is a three-dimensional scene diagram that illustrates an
exemplary scene
generated by the computing system in accordance with embodiments of the
invention.
The computerized reconstruction system generates the depth map illustrated in
FIG 4A for
the views of the three-dimensional scene. In turn, proxy meshes are used by
the
computerized reconstruction system to provide texture to the three-dimensional
scene.
The proxy meshes are illustrated in FIG. 4B. The computerized reconstruction
server also
performs texture mapping on the proxy meshes. A texture mapped proxy mesh is
illustrated in FIG 4C.
[0076] In one embodiment, the computerized reconstruction system detects
vanishing
directions in the two-dimensional image. The computerized reconstruction
server
constructs three-dimensional lines based on the vanishing directions. In turn,
the
vanishing directions and three-dimensional lines and points are used to
generate candidate
planes, which define the proxy mesh for the three-dimensional scene.
[0077] Fig. 5 is a vanishing direction diagram that illustrates detection of
vanishing
directions within two-dimensional images in accordance with embodiments of the
invention. A two dimensional image is received by the computerized
reconstruction
system. FIG. 5A illustrates an exemplary two dimensional image that is
processed by the
computerized reconstruction system to extract vanishing directions. FIG. 5B
illustrates the
orientation of each cluster of vanishing directions extracted from the two-
dimensional
image. The computerized reconstruction server identifies the three-dimensional
lines that
corresponds to the vanishing directions and the corresponding image features.
FIG. 5C
illustrates an exemplary reconstruction of a three-dimensional scene rendered
by the
computerized server using the vanishing directions and the generated three-
dimensional
lines.
[0078] The computerized reconstruction server adjusts the three-dimensional
scenes based
on the uncertainty associated with the depth maps for the three-dimensional
scenes. The
18
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
plane detection performed by the computerized reconstruction server accounts
for this
uncertainty by computing a vector along the viewing direction of a three-
dimensional
point located on or proximate to a plane generated by the computerized
reconstruction
server. In turn, the computerized reconstruction server estimates a normal to
the surface
of the three-dimensional point to estimate the orientation of a plane passing
through the
three-dimensional point.
[0079] Fig. 6 is a normal orientation diagram that illustrates probable
distribution of
surface normals in accordance with embodiments of the invention. The
computerized
reconstruction system determines the covariance ( ) for each three-dimensional
point
around a three-dimensional point Xk. FIG. 6A illustrates a measure of the
covariance Wk
for three-dimensional points around the three-dimensional point Xk. Also, the
computerized reconstruction server evaluates a distribution of the surface
normals
among the three-dimensional points proximate to Xk. The normals are used to by
the
computerized reconstruction system to determine an orientation of the plane
that passes
through the three-dimensional point Xk. FIG. 6B illustrates the distribution
of the normal
for the planes that pass through three-dimensional point Xk.
[0080] In some embodiments, the distribution of the normal do not have strong
unique
peaks and votes from multiple viewpoints and associated image features are
used to
estimate the orientation of the plane. The computerized reconstruction server
may collect
votes regarding the orientation of the plane from three-dimensional points and
lines. In
turn, the distribution of the votes are used to determine the orientation of
the planes.
[0081] Fig. 7 is a distribution histogram that illustrates probable
distribution of the
orientation of the planes or three-dimensional lines in accordance with
embodiments of the
invention. The distribution of the votes from the three-dimensional points and
lines are
evaluated by the computerized reconstruction server in a histogram. FIG. 7A
illustrates
histogram Hi1 that represents the distribution of normals based on votes from
the three-
dimensional points. FIG. 7B illustrates histogram Hi2 that represents the
distribution of
normals based on votes from the three-dimensional lines. The dominate normals
are
assigned as orientations to the planes identified by the computerized
reconstruction server.
[0082] The computerized reconstruction server executes a graph-cut
optimization that
considers ray visibility when assigning pixels to planes. The ray visibility
information
19
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
extracted from the two dimensional images and corresponding three-dimensional
lines and
points are used as data terms in the objective function utilized to perform
the graph-cut
optimizations. Any plane that intersects a visibility ray from the plane
corresponding to
the three-dimensional line or point to the corresponding viewpoint is assigned
a penalty.
[0083] Fig. 8 is a visibility diagram that illustrates scene information
extracted from the
two-dimensional images in accordance with embodiments of the invention. The
plane mi
is associated with three-dimensional line L and three-dimensional point X The
three-
dimensional line L and three-dimensional point X are visible at multiple
viewpoints. A
plane mk intersects a visibility ray from the plane mi to the corresponding
viewpoints.
The optimization function executed by the computerized reconstruction system
will assign
the plane mk a high visibility cost because it intersects the visibility rays
between the
viewpoints and the plane mi .
[0084] The three-dimensional pixels and planes are organized in a graph by the
computerized reconstruction server. A graph-cut optimization is executed by
the
computerized reconstruction system to select the optimal assignment of pixels
to planes.
The graph-cut optimization evaluates data terms and smoothness terms
associated with
each edge connecting a plane and a pixel.
[0085] Fig. 9 is a graph diagram that illustrates assignment of pixels to
labels that
represent planes using a Markov Random Field representation and graph cut
minimization
in accordance with embodiments of the invention.
[0086] The graph includes nodes corresponding to the pixels in the two-
dimensional
images and labels corresponding to planes in the three-dimensional scene. The
graph may
represent the Markov Random Field for the three-dimensional scene. Each pixel
1(i,j) is
assigned to a plane P(i,j). The edge connecting the pixel 1(i,j) and plane
P(i,j) is assigned a
cost based on the data terms and smoothness terms evaluated by the
computerized
reconstruction system. The cut cost is the sum of the edges that are removed
or cut. The
edges connecting the pixels 1(i,j) and planes P(i,j) are removed to minimize
the objective
function that measures the overall cost of assigning each pixel to a plane in
the three-
dimensional scene.
[0087] In some embodiments, the computerized reconstruction system measures
photo-
consistency by warping a neighboring image in the collection of two-
dimensional images.
In turn, the computerized reconstruction server measures the similarity
between the
warped and image and the neighboring image. The similarity score for multiple
neighbors
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
are averaged by the computerized reconstruction system to evaluate the photo-
consistency
measure, which is used as a data term in the graph-cut optimization.
[0088] Fig. 10 is a photo-consistency diagram that illustrates the
relationship between
two-dimensional images used to generate the three-dimensional scene in
accordance with
embodiments of the invention. The computerized reconstruction server
identifies a
reference image selected from the collection of two-dimensional images. FIG.
10A
illustrates an exemplary reference image. In turn, the neighboring two-
dimensional
images are selected and warped to calculate the photo-consistency. FIG. 10B
illustrates an
exemplary warped neighbor image that is used by the computerized
reconstruction system.
FIG. 10C illustrates a measure of the photo consistency between the reference
image and
the warped image determined by the computerized reconstruction server.
[0089] The smoothness terms of the graph-cut optimization are used to ensure
pixels and
planes are assigned to ensure smooth boundary transitions.
The computerized
reconstruction server identifies the crease lines and occlusion lines included
in the two
dimension. In turn, the computerized reconstruction server evaluates the
smoothness
terms based on the locations of the pixels and planes associated with the
crease lines,
occlusion lines, and other lines in the two-dimensional scene.
[0090] Fig. 11 is a boundary diagram that illustrates crease edges
corresponding to the
intersection of a pair of planes and occlusion boundaries for planes in the
three-
dimensional scene in accordance with embodiments of the invention.
[0091] The computerized reconstruction server identifies crease lines in the
two
dimensional images. The crease lines are illustrated in FIG. 11A. The crease
lines are
used to calculate a smoothness term for the boundary between the planes that
create the
crease line. The computerized reconstruction server identifies the occlusion
lines in the
two-dimensional images. The occlusion lines are illustrated in FIG. 11B. The
occlusion
lines are used to calculate a smoothness term for the boundary associated with
the planes
that create the occlusion line.
[0092] The proxy mesh is generated based on the pixel and plane assignments
provided by
the computerized reconstruction server. In turn, the computerized
reconstruction server
maps textures to planes in the proxy mesh and displays the textured mapped
mesh to a
user. The computerized reconstruction system also interpolates views of the
three-
dimensional scene to provided navigation within the three-dimensional scene.
21
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
[0093] Fig. 12-17 are transition diagrams that illustrates possible navigation
between view
points in various three-dimensional scenes in accordance with embodiments of
the
invention.
[0094] In some embodiment, the computerized reconstruction server performs a
method to
render a navigable three-dimensional scene. A collection of two-dimensional
images are
received and processed to extract image features and camera calibrations. The
computerized reconstruction server identifies three-dimensional lines captured
in the scene
by a camera and uses the vanishing directions, image features, and camera
calibrations to
generate multiple planes for the three-dimensional scene.
[0095] Fig. 18 is a logic diagram that illustrates a method to select planes
that are used to
render a navigable three-dimensional scene from a collection of images stored
in an
electronic database in accordance with embodiments of the invention. The
method begins
in step 1810. In step 1820, a collection of images is received from the
electronic database
by the computerized reconstruction server. In step 1830, the computerized
reconstruction
server extracts scene information from the collection of images. The scene
information
may include camera calibrations, a three-dimensional point cloud, three-
dimensional line
segments, and data for multi-view correspondence of points and lines.
[0096] In turn, the computerized reconstruction server detects vanishing
directions within
each image in the collection of images using edge detection, in step 1840. The
vanishing
directions are vectors representing the direction of parallel lines included
in the collection
images. The vanishing directions are derived from the directions of parallel
three-
dimensional lines estimated from the collection of two-dimensional images.
Alternatively,
the vanishing directions may be estimated from two-dimensional line
intersections
extracted from two-dimensional images in the collection of two-dimensional
images. In
one embodiment, mean shift clustering is used by the computerized
reconstruction server
to select vanishing directions for different views captured by the collection
of two-
dimensional images.
[0097] In step 1850, the computerized reconstruction server identifies each
plane in the
navigable three-dimensional scene based on the vanishing directions and the
scene
information. In an embodiment, the computerized reconstruction server
determines a set
of plane orientations based on a cross product of each possible pair of
vanishing directions
extracted from the collection of images. Additionally, dominant planes for the
three
dimensional scene may be identified by the computerized reconstruction server.
22
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
[0098] In step 1860, the computerized reconstruction server generates a Markov
Random
Field distribution to assign pixels to each plane based on minimization
functions applied to
the Markov Random Field distribution. The minimization functions optimize a
global cost
of assigning the pixel to a plane in the navigable three-dimensional scene.
The pixels are
included in a three-dimensional point cloud and assigned to each of the
dominant planes
based on, among other things, photo-consistency across multiple views included
in the
collection of images. In some embodiments, the pixels in the image vote for
planes that
correspond to camera orientation. Alternatively, the pixels in each image in
the collection
of images iteratively vote to determine the plane-pixel assignments that
minimize the
global cost. In certain embodiments, the minimization functions select cut
costs for the
Markov Random Field distribution graph that are constrained by the smoothness
terms.
The selected cut costs of the Markov Random Field distribution graph may be
tallied by
the computerized reconstruction server to arrive at a global cost.
[0099] In one embodiment, a portion of the global cost of plane-pixel
assignments is
represented by a smoothness term included in the minimization functions
applied to a
Markov Random Field distribution graph. The computerized reconstruction server
may
calculate smoothness terms in the Markov Random Field distribution graph
having planes
and pixels to prefer transitions corresponding to discontinuities at two-
dimensional lines
that are consistent with the vanishing directions orthogonal to the normal
vector of an
occluding plane. The computerized reconstruction server may calculate
smoothness terms
to penalize assigning a pixel in one image to a plane if the corresponding
pixel in
neighboring images did not choose the same plane. . The computerized
reconstruction
server may calculate smoothness terms to prefer transitions corresponding to
two-
dimensional lines in the image.
[00100] The computerized reconstruction server renders the pixels on the
assigned
planes. The method ends in step 1870.
[00101] The computerized reconstruction server assigns pixels based on
optimizations performed on a graph that represents the possible assignments of
the pixels
and planes. The computerized reconstruction server attempts to minimize the
cost of each
assignment between a pixel and plane. The cost of the assignment is
represented by an
objective function that include data terms and smoothness terms.
[00102] Fig. 19 is a logic diagram that illustrates a method that
assigns pixels from
two-dimensional images to three-dimensional planes when reconstruction a
navigable
three-dimensional scene from a collection of two dimensional images stored in
an
23
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
electronic database. The method begins in step 1910. In step 1920, the
computerized
reconstruction server receives the collection of two-dimensional images.
The
computerized reconstruction system generates a set of three-dimensional planes
from
scene information extracted from the two dimensional images, in step 1930. The
scene
information includes vanishing directions, lines, and three-dimensional
points.
[00103]
In turn, a Markov Random Field is generated by the computerized
reconstruction server using the scene information and the generated three-
dimensional
planes, in step 1940. In step 1950, the computerized reconstruction system
assigns pixels
to the generated planes to minimize an energy function represented by the
Markov
Random Field, which provides depth maps for the two-dimensional images.
[00104]
The Markov Random Field is optimized based on data terms that set
conditions for assigning pixels and smoothness terms that set conditions for
transitioning
between planes. In some embodiments, during pixel assignment the computerized
reconstruction system checks data terms for multi-view photo-consistency,
geometric
proximity of sparse three-dimensional points and lines, and free space
violations derived
from ray visibility of the three-dimensional points and lines. The data terms
penalize
assigning a pixel to a plane that would occlude a three-dimensional point or
line that was
observed in the image or the data terms encourage assigning a pixel to a plane
that is
consistent with a three-dimensional point or line that was observed in the
image. In
another embodiment, the data terms penalize assigning a pixel in one image to
a plane if
the corresponding pixel in neighboring images does not choose the same plane
during an
iterative pass on each two-dimensional image in the collection of two-
dimensional images.
[00105]
The smoothness terms prefer transitions between planes along the lines
where the planes intersect. The smoothness terms also prefer transitions
corresponding to
discontinuities at two-dimensional lines that are consistent with the
vanishing directions
orthogonal to the normal vector of an occluding plane. The smoothness terms
prefer
transitions corresponding to two-dimensional lines in the image. The
smoothness terms
penalize assigning a pixel in one image to a plane if the corresponding pixel
in
neighboring images did not choose the same plane during a simultaneous pass on
two-
dimensional images in the collection of two-dimensional images.
[00106]
The depth maps are generated by the computerized reconstruction system
based on the pixel-plane assignments and are used to render a navigable three
dimensional
scene. In some embodiments, the computerized reconstruction system corrects
the depth
map and boundaries by identifying occlusion lines and crease lines. A three
dimensional
24
CA 02760973 2011-11-03
WO 2010/147929 PCT/US2010/038594
scene is rendered by the computerized reconstruction server using the depth
map and
projections of the two dimensional images. The two-dimensional image
projections are
cross faded to allow smooth view interpolation for each of the two-dimensional
images in
the collection that are part of the three-dimensional scene. The method ends
in step 1960.
[00107] In summary, a computerized reconstruction server and client that
execute
automatic methods for computing piecewise planar, dense depth maps that are
used for
image-based rendering of large unordered two-dimensional images are provided.
The
three-dimensional scenes rendered by the computerized reconstruction server
are reliable
and photorealistic because the computerized reconstruction server exploits
global scene
information to generated the three-dimensional scene. The computerized
reconstruction
server recovers a set of dominant scene planes based on robust plane-fitting
of three-
dimensional points and lines while utilizing strong vanishing directions to
infer plane
orientations. The Markov Random Field (MRF) graph and corresponding
optimization are
executed by the computerized reconstruction server to generate piecewise
planar depth
maps that incorporate geometric constraints derived from discontinuities for
polygonal
and rectilinear shapes included in the two-dimensional images. Furthermore,
ray visibility
of three-dimensional points and lines are used by the computerized
reconstruction server
to enforce free space constraints and holes are minimized in scenes with non-
Lambertian
and textureless surfaces.
[00108] The foregoing descriptions of the embodiments of the invention are
illustrative, and modifications in configuration and implementation are within
the scope of
the current description. For instance, while the embodiments of the invention
are
generally described with relation to FIGS. 1-19, those descriptions are
exemplary.
Although the subject matter has been described in language specific to
structural features
or methodological acts, it is understood that the subject matter defined in
the appended
claims is not necessarily limited to the specific features or acts described
above. Rather,
the specific features and acts described above are disclosed as example forms
of
implementing the claims. The scope of the embodiment of the invention is
accordingly
intended to be limited only by the following claims.
25
