Efficient Multiview Stereo by Random-Search and Propagation
Youngjung Uh
Yonsei University
Seoul, Korea

Yasuyuki Matsushita
Microsoft Research Asia
Beijing, China

Hyeran Byun
Yonsei University
Seoul, Korea

youngjung.uh@yonsei.ac.kr

yasumat@microsoft.com

hrbyun@yonsei.ac.kr

Abstract

matches, and that propagating the sparse good matches canefficiently overwrite nearby bad matches thanks to the local coherence of an image. The use of this scheme in
the MVS context has a few advantages. First, it can significantly reduce the number of photo-consistency evaluations by the random-search, unlike point-wise local optimization approaches. Second, local smoothness is implicitly enforced by the propagation in an efficient manner. As
a result, the computational demands can be significantly reduced by our method in comparison with recent efficient
MVS approaches (e.g., 3× faster than [11]). Finally, ourapproach is robust against errors in the initial guess; in fact,
our method is able to begin with any random guess of the
3D points.
While the random-search and propagation scheme has
these advantages, it is not straightforward to apply it in the
MVS context where a 3D point is reconstructed via multiview photo-consistency. Shen [27] utilizes such a scheme
to speed up depth-map estimation on each pair of images
and merges the resulting point cloud by checking occlusions
with neglecting the multi-view photo-consistency, which isfound often important in previous studies [8, 33]. Unlike
binocular stereo matching where the PatchMatch scheme
has been successfully applied [3, 4, 14], our case requires
to handle significant view-point variations in both angle anddistance and resolution gaps caused by them, and interview propagation needs to be carefully designed for efficient and effective 3D reconstruction. This paper presents
an approach to address these issues and develops an efficient
MVS method. The proposed method is evaluated using
Middlebury multiview stereo benchmark and a few different
outdoor multi-view images. Our experiment shows the effectiveness of the proposed method in comparison with previous state-of-the-art methods in efficiency and accuracy.

We present an efficient multi-view 3D reconstruction
method based on randomization and propagation scheme.
Our method progressively refines 3D point estimates by randomly perturbing the initial guess of 3D points and propagates photo-consistent ones to their neighbors. In contrast
to previous refinement methods that perform local optimization for a better photo-consistency, our randomization approach takes lucky matchings for reducing the computational complexity. Experiments show favorable efficiencyof the proposed method with the accuracy that is close to
the state-of-the-art methods.

1. Introduction
Multi-view stereo (MVS) reconstructs dense 3D points
from a set of calibrated images by estimating correspondences across the images. Much progress has been madeon improving the quality of 3D reconstruction, and it is getting close to that of laser scans in recent approaches [5, 11].
However, the computational complexity becomes one of
the major limiting factors for MVS methods when a large
amount of data needs to be processed. Improving the computational efficiency of MVS is actively investigated by several recent works [7, 15, 27, 33].
The major reason why a conventional MVS demands
a high computational cost is that, for each hypothesized
3D point, its photo-consistency needs to be evaluated using multiple views that see the 3D point. The number of theoperations is proportional to the amount of hypothesized 3D
points and the number of views. Thus, reducing the number of photo-consistency assessment is one of the keys togreater efficiency.
In this paper, we present an efficient MVS method basedon a random-search and propagation scheme. The randomsearch and propagation approach is shown useful in the
recent PatchMatch method [2], also in its application tobinocular-stereo [4]. The heart of PatchMatch method is theobservation that random sampling can sometimes find good

2. Related work
MVS has been extensively studied in the literature andcompared using comprehensive benchmark datasets [25,30]. This section reviews some of the works that are closely
related to our work.
1Efficiency of MVS has been pursued in a few different
Initialization
Random Search
Propagation
Filteringapproaches. One class of methods casts the MVS problem into a combination of local (typically, pairwise) stereo
iteration
matching and merging processes. The merging process, ofFigure 1: Flow chart of the proposed method. Latter threeten referred to as depth-map merging, has been approachedcomponents are iterated. See Sec. 3 for more details.
using various different ways. Li et al. [18] efficiently merge
Initialization
Random-Search
Propagation
Filtering
depth-maps in a bundle optimization scheme by ensuring
static handheld camera. Furthermore, a live 3D reconstrucdepth consistency across multiple views. Bradley et al. [5]tion on mobile phones has been introduced by Tanskanen etmerge depth-maps into a point cloud by estimating local
al. [32], where the embedded inertial sensor is used forsurface normal and performing fast meshing in a low didetermining camera poses. However, these methods are
mensional space. Merrell et al. [19] present a method for Initialization
Random-Search
Propagation
Filtering
limited to low-resolution or short-baseline settings, which
real-time visibility-based fusion of depth-maps by reducing
make them efficient andtractable but inapplicable to morenumber of depth hypothesis.
iteration
general cases.
Another class of approaches performs clustering of inIn contrast to these approaches, we aim at reducing
put images such that highly redundant computations can be
the computational cost by neglecting costly yet smallavoided [10] or independent parts can be handled in paralgain computations using the random-search and propagalel [9, 13, 35]. Furukawa et al. [10] perform clustering using
tion scheme, motivated by the recent success of PatchMatch
three cues; compactness, size, and coverage. By introductechnique [2] and its applications. Bleyer et al. [4] apply
ing a function that measures the expected reconstruction acthe PatchMatch method to binocular stereo matching withcuracy, they minimize the total number of images from theslanted support windows and have shown accurate estimaclusters subject to the function with pre-defined maximum
tion results. It is further improved by combination withnumber of images per cluster. Consequently, they reduced
a belief propagation-based solution method by Besse etcomputational cost by half for St. Peter’s Basilica dataset1 .
al. [3]. Furthermore, Heise et al. [14] impose regulariza3D reconstruction using a massive amount of community
tion with the Huber norm to achieve the state-of-the-art acphoto collections has been shown by Goesele et al. [13].
curacy in Middlebury stereo benchmark [24] for 0.5-pixel
Their method selects a small set of views among candidate
accuracy.
views for matching in order to speed up the depth computation, by a criterion designed to prefer views that are
3. Proposed methodphotometrically consistent and provide a sufficiently wide
range of observation. Frahm et al. [9] propose appearanceOur method is built upon random-search and propagabased clustering by extracting global appearance descriptor
tion scheme and consists of four steps: (1) initialization, (2)gist [21] for each image and verifying the clusters via epiporandom-search, (3) propagation, and (4) filtering as illuslar geometric consistency. They improve performance bytrated in Figure 1. We use a small 3D patch that is definedleveraging the constraints from appearance clustering andfor a 3D point. The patch is a rectangular plane that is delocation independence, and by performing computation in a
fined by its center position (corresponding to the 3D point),
parallel manner at the cluster level.
normal direction, and the number of grid points and size. In
Parallelism is indeed an important aspect for an efficientthe initialization step, patches are first assigned random poMVS method. Some of the computation blocks, such as imsitions and normals. From those randomized patches, a set
age re-projection and visibility checking, are naturally parof best patch candidates is then selected by evaluating eachallelized as shown in [15, 22]. Li et al. [18] use a track,
patch’s photo-consistency across all the views, and the rest
which refers to a set of pixel matches, for performing opof the patches are removed. In the random-search step, thetimization at the track-level in parallel. Agarwal et al. [1]original patches are perturbed and assigned new positions
show city-level reconstructions in a day by designing paraland normals. Patches are then propagated to their neighlel image matching pipeline. Furukawa et al. [10] propose
bors in the 3D coordinates, regulated by the input image
a merging algorithm that is designed to run on individual
coordinates. Finally, the filtering step eliminates outliers.
MVS points in a parallel manner.
The steps from the random-search to the filtering are iterRecent progress in GPU parallelization has made realated until convergence. In what follows, we describe ourtime 3D reconstruction possible. Newcombe and Davi3D patch model and explain the details of each step.
son [20] present a rapid and dense reconstruction methodof scenes browsed by a live camera using a base mesh and3.1. Patch model and photo-consistency
its warped depth maps. Stühmer et al. [31] show the reconOur patch is a local 3D plane defined in the world costruction of a scene with small displacements from nearlyordinates system. It is represented as p(c, n) ∈ P, where
1 http://grail.cs.washington.edu/rome/rome/index 5.html
c ∈ R3 is the 3D position of the patch center, n ∈ R3 is thenormal direction. µ × µ grid points are defined on the patch
plane, and the interval between each grid point is adaptively
determined using the rays spanned at the pixel interval fromthe closest image. The grid points are projected onto theimage coordinates, and corresponding pixel intensities are
sampled to create an observation vector for each view.
Photo-consistency score of patch p is calculated as follows. We collect a set of visible images V(p) for patch p
by evaluating visibility using camera’s field of view and theangle between patch’s surface normal and the ray direction
from the camera. From V(p), we select the closest view as
the reference image R(p) by evaluating the projected areasof the patch with a unit area. Once the reference image R(p)is determined, the 3D patch grid is created as described2
above, and an observation vector f ∈ Rµ is generated foreach image in V(p). Using the observation vectors, we define the photo-consistency cost E(p) as the average of one
minus normalized cross-correlation (NCC) scores between
the reference and other observation vectors, fr and fi , and
*
+
X
fbr
fbi
1
1−
,
, (1)
E(p) =|V(p) \ R(p)|kfbr k kfbi ki∈V(p)\R(p)where h·, ·i represents the inner product of vectors, b
f = f −fand f represents average of the observations in the vector.
In this manner, the greater photo-consistency results in thelower cost E(p). To increase the robustness against occluded views, we remove the NCC scores from the above
calculation that are smaller than the pre-defined threshold α. In addition, to avoid the aperture problem, we set
E(p) = ∞ when fr is textureless, i.e., the magnitude of thereference vector fbr is close to zero.
In our method, we use a view-dependent candidate patch
map Bi ∈ PW ×H , which has the same dimensions (W, H)
as the image of camera i. It retains the visible patch thathas the highest photo-consistency, i.e., smallest E(p), foreach ray from each camera i. The view-dependent candidate patch map B is used for achieving computational efficiency, by working in a set of image coordinates, rather thandirectly in the world 3D coordinates. A similar concept has
been used in PMVS [11], which stores all the patches thatthe ray penetrates, but our candidate patch map B stores
only the best one for each ray (or none for the ray that does
not intersect any patch). Our method updates the candidate patch maps B whenever patches p are updated. We use
a vector x = (x, y) ∈ Z2+ for indicating the coordinatesof the candidate patch map Bi , and use Bi (x) for indicating the corresponding patch p that is stored in the candidate
patch map Bi at location x.

3.2. Initialization
In the initialization step, a set of 3D points are randomly
generated, and for each 3D point, a 3D patch p is assigned.

Algorithm 1 random-search
Input: Original patch p(t) , camera i, ray r through target
pixel, range parameters rc , φ, θ, ψ, threshold 
Output: New patch p(t+1)
1: while (rc > ) do
2:
Pick random ∆d ∈ [−rc , rc ] 3:Pick random(∆φ , ∆θ , ∆ψ )T ∈ −(φ, θ, ψ)T , (φ, θ, ψ)T
R := Rx (∆φ )Ry (∆θ )Rz (∆ψ )cp0 := cp + ∆d r
np0 := Rnp
7:
if E(p0 ) < E(p(t) ) using Eq. (1) then8:p(t+1) := p09:
end if10:(rc , φ, θ, ψ) := (rc , φ, θ, ψ)/2
11: end while
4:
5:
6:

Algorithm 2 spatial propagation(t)

Input: Candidate patch maps {Bi }, cameras {i}, propagation direction w ∈ {−1, 1}(t+1)
Output: Updated candidate patch maps {Bi}
1: for each image Ii do
2:
ci := position of camera i
3:for each pixel location x(= (x, y)) do
4:
X0 := {(x + w, y), (x, y + w)}
5:for each x0 ∈ X0 do(t)
6:b0 := Bi (x0 )7:r0 = (b0 − ci )/||b0 − ci ||8:d := (cb0 − ci )T nb0 /(r0T nb0 )9:
cp0 := ci + dr0
10:
np0 := nb0(t)
11:if E(p0 ) < E(Bi (x0 )) then(t+1) 012:Bi(x ) := p013:
end if14:
end for15:
end for
16: end for
The patches p are further assigned random orientations n.
In case no prior information is given about the scene, ourmethod begins with randomly producing 3D points in abounding box or intersection of multiview frustum. If someknowledge about the scene is available, e.g., sparse correspondences obtained in the structure-from-motion process [29, 34], our method takes them as input and generates
additional random 3D points around the original ones.

3.3. Random-search
Our method uses a random-search approach for generating more diverse patches around the previous candidates asshown in Figure 2a. Unlike previous approaches that com-

Perturbed
patches
Perturbed
patches
Perturbed
patches
with
lower
cost
with
lower
cost
with
lower
cost
Existing
patches
Existing
patches
Existing
patchescameracameracameracameracameracamera(a) Random-search

Sourcepatch
Sourcepatch
Sourcepatch
updated
and
its
plane
updatedandplane 𝐵𝐵𝑖𝐵
updatedanditsits
plane
𝑖isis
𝑖is

cameracameracameracameracameracameraNew
New
patches
Newpatches
patches
fromfromcamera
camera𝑖𝑖
fromcamera𝐵𝐵𝑗𝑗isisupdated
updatedupdatedcamera𝑗𝑗𝑗
cameracameracamera𝑖𝑖𝑖
cameracameracameracameracamera𝑗𝑗𝑗
camera𝑖𝑖𝑖
cameracamera(c) View propagation(b) Spatial propagation

Figure 2: Illustration of essential steps. (a) An existing patch is replaced with a better one that is randomly produced byperturbation. (b) From an existing patch, new patches are generated from left to right on its extended plane. (c) The newly
propagated patches are further propagated to another view j to update Bj .
putes local optima using gradient descent, our method attempts to efficiently find a sub-optimal solution in a randomization scheme. In addition, because of the randomization, the method has a chance of escaping from local minima, which is potentially non-optimal.
We use the candidate patch maps B for generating newpatches. For each view i, we pick a patch p stored in(t)
Bi (x), where (t) indicates the result of the t-th iteration. A new patch p0 is created by perturbing p’s positionand normal. The perturbation of the position is performed
along the ray of pixel x in camera i, whose displacement∆d ∈ R is randomly chosen within the perturbation range[−rc , rc ]. With this displacement, the new patch’s position cp0 becomes cp0 = cp + ∆d r. The surface normal
is perturbed using a rotation matrix R ∈ SO(3) that is randomly
defined by a predefined
range of the Euler angles−(φ, θ, ψ)T , (φ, θ, ψ)T . The new patch’s surface normal
np0 is thus defined as np0 = Rnp . The photo-consistencyof the new patch p0 is then evaluated, and if it is better thanthat of the original patch p, Bi is updated and stores p0 . The
procedure is summarized in Algorithm 1.

target coordinates x0 , and a new patch p0 is defined. The
new patch’s location cp0 is determined by the intersectionof patch p and the camera ray through the target coordinates x0 . The surface normal of the new patch p0 is maintained the same as the source patch p. Subsequently, photoconsistency of the new patch E(p0 ) is compared to that ofthe patch that has been defined at the same coordinates, i.e.,(t)
E(Bi (x0 )). Then, the candidate patch map Bi is updated(t+1) 0to contain p0 at Bi(x ) and the patch p is removed if
0E(p ) shows the better photo-consistency (lower score of
E). To avoid unreliable propagations, the propagation is
terminated if the angle between the patch normal np andthe ray direction r is greater than a pre-defined thresholdθp . The procedure is summarized in Algorithm 2.

3.4. Propagation
This step propagates patches to its neighbors using thecandidate patch maps B. This operation is similar to theoriginal PatchMatch method [2]; however, to apply the procedure in the context of MVS, we take a two-step approachfor the propagation. Namely, the patches are first propagated to their neighbors in each candidate patch map Bi ,and further propagated across different views i.
The spatial propagation is performed on each candidate
patch map Bi , starting from the top-left to bottom-right corner in odd iterations, and then the backward direction ineven iterations, as done in [2]. As shown in Figure 2b, a(t)source patch p of Bi (x) is propagated to its neighboring

Before & after filtering

Figure 3: Effect of filtering. Left: observation, middle: before filtering, right: after filtering. More details become
visible after the filtering.
Once the spatial propagation is performed for each Bi ,inter-view propagation takes place to further propagate
patches to Bj as shown in Figure 2c. Every new patch p0
retained in Bit+1 is projected onto all the other cameras j tolocate their target coordinates u. If the new patch p0 has abetter photo-consistency than the patch of Bj (u), the patch

is replaced with the new one at Bj (u) where u is projectionof the patch p0 . At the same time, the patch that is overwritten at Bj (u) is removed from all the other candidate patch
maps.

DatasettempleSR
16 images

3.5. Filtering

templeR
47 images

To remove the artifacts caused by wrong propagations, we use two filtering methods after the propagation
step. The first filtering is the one used in Furukawa andPonce’s method [11] for discarding visibility-inconsistentpatches and neighbor-inconsistent patches. In addition,
we use smoothness-based trimming as the second filtering.
Smoothness ζp of a patch p is defined by the angle between
its normal np and the average normal n̄p in the fixed-size
window Wp as ζp = arccos(nTp n̄p ). We also simply discard
patches that show greater angles than a pre-defined threshold θζ . More details become visible after these two filtering
steps as in Figure 3.

4. Experimental Results
In this section, we assess the performance of our method
using public datasets provided by Seitz et al. [26] andStrecha [30], and our own street side dataset. The accuracyof our method is evaluated using the Middlebury multi-view
stereo evaluation score and its relative error to the groundtruth. The measurement of computational cost for Middlebury dataset is performed using the normalized time in acertain fixed environment provided by Middlebury evalutempleRing
ation system. Except for Middlebury dataset,
our experiments including comparison with PMVS are performed onan Intel Xeon CPU E5-2690 2.90GHz (32 cores) with PPL2
for parallelization, where we set the number of iterations ofrandom-search, propagation, and filtering to 4.
Throughout the experiments, we use the following parameters. The resolution of the grid µ (in Sec.dinoRing
3.1) is fixed
to 7, the threshold α for the energy E(p) of Eq. (1) is set
to 0.7. The maximum angle θp (in Sec. 3.4) between np
and the ray r from the camera is set to 60 degrees. The
smoothness threshold for filtering θζ in Sec. 3.5 is set toarccos 0.85. Perturbation ranges of surface normal are set
to φ = θ = ψ := π. Because the size of the target objects
varies (inferred by camera parameters), we change the parameters of the perturbation range rc of position and threshold  depending on the dataset: (rc , ) = (0.01, 0.001) for
the Middlebury dataset, (0.1, 0.03) for Fountain-P11, and(0.1, 0.03) for Herzjesu.
Quantitative evaluation procedures for MVS methods areprovided in the Middlebury benchmark [25, 26]. First,
we show the benchmark for accuracy and completeness inTable 1 in comparison with other state-of-the-art methods
2 Parallel
Patterns Library(PPL),
us/library/dd492418.aspx

http://msdn.microsoft.com/en-

dinoSR
16 images

dinoR
48 images

nIter
GenPatch
nPatchPSR
nTriangle
GenPatch
nPatchPSR
nTriangle
GenPatch
nPatchPSR
nTriangle
GenPatch
nPatchPSR
nTriangle

1
0:11
55K
0:59
0.8M
1:39
119K
1:11
1.3M
0:15
99K
1:19
1.1M
2:33
176K
1:22
1.8M

2
0:21
106K
1:11
0.9M
3:07
251K
1:44
2.0M
0:32
190K
1:22
1.5M
5:01
380K
1:57
2.9M

3
0:33
194K
1:20
1.6M
4:37
476K
2:22
3.7M
0:49
337K
1:59
2.6M
7:25
734K
3:00
5.2M

4
0:45
232K
1:21
1.7M
6:10
549K
2:12
4.0M
1:07
387K
1:57
2.8M
9:57
837K
3:39
5.6M

Table 2: Running time (min:sec) with respect to thevarying number of patches and triangles over iterations. (GenPatch:generating patches, nP:number of patches,
PSR:Poisson surface reconstruction, nT:number of triangles)

Initial guess

Iteration 1

Iteration 2

Iteration 3

Iteration 4

Figure 4: Our reconstruction results over iterations on the
Middlebury dataset. From totally random initial guessin a bounding box, our method iteratively refine the 3D
shape. Meshes are generated with Poisson surface reconstruction [16]. Top: TempleRing data, bottom: DinoRing
data.

along with the normalized computation time. It shows theefficiency of the proposed method without a significant lossof accuracy and completeness. Table 2 shows componentwise running time with respect to the varying number ofpatches and triangles over iterations. Figure 4 shows theevolution of our 3D reconstruction over iterations. Our
method faithfully recovers 3D shape in several iterations,even with starting from the totally random initial guess. For
the TempleRing and DinoRing datasets of Middlebury [25],our method runs in a couple of minutes for patch optimization followed by a couple of minutes of Poisson surface re-TempleMethodOurs
Furukawa3 [11]Hiep [15]Bradley [5]Campbell [6]Goesele [12]Li [18]Kolev3 [17]Processor
CPU
CPU
GPU
CPU
CPU
CPU
CPU
CPU

Acc
0.51
0.47
0.45
0.57
0.48
0.61
0.64
0.7

Ring
Comp
96.4
99.6
99.8
98.1
99.4
86.2
98.2
98.3

Time
7.4
211
1.5
11.4
59
2040
3.6
539

Dino

SparseRing
Acc Comp Time
1.23
90.2
1.9
0.63
99.3
129
0.48
93.7
3.5
0.53
98.6
22.5
0.87
56.6
687
0.97
92.7
114

Acc
0.32
0.28
0.53
0.39
0.46
0.43
0.42

Ring
Comp
97.3
99.8
99.7
97.6
57.8
99.7
99.5

Time
12.1
301
1.5
23.5
2516
5.9
470

Acc
0.42
0.37
0.38
0.56
0.48

SparseRing
Comp Time
96.7
2.7
99.2
152
94.7
7
26.0
843
98.6
100

Table 1: Quantitative evaluations using the Middlebury dataset [25] with default thresholds(Acc:90%, Comp:1.25mm). Eachcolumn for each dataset shows accuracy in mm, (Acc: the lower the better), completeness in % (Comp: the higher the better),and normalized running time in minutes (Time).
100

cumulative error
distribution(%)
cumulative error distribution

cumulative error distribution

and Herzjesu-P8, for evaluating the performance of our
90 method. Figure 5 shows the cumulative histogram of error ratio in depth to the ground truth, i.e., e = (dr − dg )/dg ,8080
where dr is the depth estimate and dg is the ground truth.
70
70 It shows our result has similar accuracy with PMVS. The
PMVS
PMVS
qualitative results are also
shown in Figure 6. They show
60
Ours
60
Ours
good overall reconstruction of the scenes that is close to50
50 PMVS [11], while the level of reconstruction details is
40
40 varying due to the fact that our propagation assumes local
0.1 0.3 0.5 0.7 0.9 1.1 1.3 1.5
0.1smoothness
0.3 0.5 0.7
0.9 1.1in 1.3
1.5
as shown
the close-up
views.
error range(%)
error range(%)
We also use a more life-like street side scene dataset(a) Fountain-P11
that we recorded for evaluating our method. The dataset
100
is recorded in a rather uncontrolled setting, and a structurefrom-motion technique [28] has been used for recovering
90
camera poses. In Figure 7, we show the subset of input
80
images and the reconstruction result in comparison with70
PMVS [11], performed via VisualSFM [34]. The experPMVS
PMVS
iments are performed with the consistent parameters for
Ours
60
Ours
the both methods, e.g., minimum number of supporting
50
images= 2, threshold for one minus NCC score= 0.7.
40Computation time on this dataset is 26 and 83 minutes for
0.9 1.1 1.3 1.5
0.1 0.3 0.5 0.7 0.9 1.1 1.3 1.5
our method and PMVS, respectively. Our result showsnge(%)
error range(%)
comparable overall reconstruction quality to PMVS’s re(b) Herzjesu-P8
sult. While the details are better recovered by PMVS, ourmethod recovers larger areas (e.g., left most building) with
Figure 5: Quantitative evaluation of our method compared
denser points from the same set of input images and paramto PMVS [11] on two data sets of [30]. The last(15th ) bin
eters. The larger coverage area of our method comes fromcollects the pixels with error ratio greater than 1.5%.
the difference in the initialization step. While PMVS limits the points to be generated from feature matching acrossimages, our method initializes the points by random search
construction [16] that generates millions of triangles. Ourover the candidate area.
CPU implementation is slower than the GPU implementation of Hiep et al. [15] with a GeForce 8800 GTX that has
5. Discussions
128 stream processors. While we cannot directly compare
the performance with their method due to the difference of
By taking the random-search and propagation approach,CPU and GPU implementations, our method shows perforwe have developed an efficient MVS method. The result
mance improvement over other CPU implementations.
shows that the proposed method achieves high efficiency
We also use Strecha’s MVS dataset [30], Fountain-P11
with accuracy that is close to the state-of-the-art methods.
90

100

a

b

e
c

d

a

a’

b

b’

c

c’

d

d’

e

e’

Figure 6: Result of our method on two data sets of [30];
Fountain-P11 (11 images) and Herzjesu-P8 (8 images). A
subset of the input images are shown on the top left corner, reconstruction results are shown on the top right corner,
their close-up views (a – e), and PMVS [11] results of corresponding regions (a’ – e’) are shown, respectively, at thebottom.
In situations where a large amount of data needs to be processed, we believe that our method has a particular strength.
Our method is indeed highly pararllelizable: The randomsearch step can be implemented in a parallel manner foreach 3D point, the spatial propagation step can use the jump
flood scheme [23], and view-propagation step can also run
in a parallel manner for each image. This motivates us for
our future work of GPU implementation of additional parallelizable parts including NCC computation and image reprojection.
One of the drawbacks of our method is that its running time depends on the number of candidate patch maps
(equivalent to the number of input images). This issue could
be addressed by incorporating image selection techniquessuch as [9, 10]. Another limitation is that our propagation
step relies on local smoothness of the scene, therefore, small

Figure 7: Street scene reconstruction result from 30 images
in resolution of 6M. The first row shows some of the input
images. The second row shows the point cloud recovered byour method, and the bottom one shows PMVS [11] result.
objects or high-frequency details in a small region are difficult to be reconstructed in case their corresponding image
areas are small. Our future work includes further improving the accuracy of these regions by adaptively increasing
the number of random-search operations.

Acknowledgements
This work was supported by the National Research
Foundation of Korea (NRF) grant funded by the Korean
government(MEST) (No. NRF-2013R1A2A1A01015870).
Part of this work has been done while the first author isvisiting MSRA as a research intern.

References[1] S. Agarwal, N. Snavely, I. Simon, S. M. Seitz, andR. Szeliski. Building rome in a day. In Proc. of Int’l Conf.
on Computer Vision (ICCV), pages 72–79. IEEE, 2009. 2[2] C. Barnes, E. Shechtman, A. Finkelstein, and D. B. Goldman. Patchmatch: A randomized correspondence algorithm for structural image editing. ACM Trans. on Graph.,28(3):24, 2009. 1, 2, 4
[3] F. Besse, C. Rother, A. W. Fitzgibbon, and J. Kautz. Pmbp:
Patchmatch belief propagation for correspondence field estimation. In Proc. of British Machine Vision Conf. (BMVC),
2012. 1, 2
[4] M. Bleyer, C. Rhemann, and C. Rother. Patchmatch stereo- stereo matching with slanted support windows. In Proc. of
British Machine Vision Conf. (BMVC), 2011. 1, 2

[5] D. Bradley, T. Boubekeur, and W. Heidrich. Accurate multiview reconstruction using robust binocular stereo and surface
meshing. In Proc. of IEEE Conf. on Computer Vision and
Pattern Recognition (CVPR), pages 1–8, 2008. 1, 2, 6
[6] N. D. Campbell, G. Vogiatzis, C. Hernández, and R. Cipolla.
Using multiple hypotheses to improve depth-maps for multiview stereo. In Proc. of European Conf. on Computer Vision(ECCV), pages 766–779, 2008. 6[7] J. Y. Chang, H. Park, I. K. Park, K. M. Lee, and S. U. Lee.
Gpu-friendly multi-view stereo reconstruction using surfel
representation and graph cuts. Computer Vision and Image
Understanding, 115(5):620–634, 2011. 1[8] Y. Deng, Y. Liu, Q. Dai, Z. Zhang, and Y. Wang. Noisy
depth maps fusion for multiview stereo via matrix completion. Selected Topics in Signal Processing, IEEE Journal of,
6(5):566–582, 2012. 1[9] J.-M. Frahm, P. Fite-Georgel, D. Gallup, T. Johnson,
R. Raguram, C. Wu, Y.-H. Jen, E. Dunn, B. Clipp, S. Lazebnik, and M. Pollefeys. Building rome on a cloudless day. In
Proc. of European Conf. on Computer Vision (ECCV), pages
368–381, 2010. 2, 7
[10] Y. Furukawa, B. Curless, S. M. Seitz, and R. Szeliski. Towards internet-scale multi-view stereo. In Proc. of IEEE
Conf. on Computer Vision and Pattern Recognition (CVPR),
pages 1434–1441, 2010. 2, 7
[11] Y. Furukawa and J. Ponce. Accurate, dense, and robust multiview stereopsis. IEEE Trans. Pattern Anal. Mach. Intell.,32(8):1362–1376, 2010. 1, 3, 5, 6, 7
[12] M. Goesele, B. Curless, and S. M. Seitz. Multi-view stereo
revisited. In Proc. of IEEE Conf. on Computer Vision and
Pattern Recognition (CVPR), volume 2, pages 2402–2409,
2006. 6[13] M. Goesele, N. Snavely, B. Curless, H. Hoppe, and S. M.
Seitz. Multi-view stereo for community photo collections.
In Proc. of Int’l Conf. on Computer Vision (ICCV), 2007. 2[14] P. Heise, S. Klose, B. Jensen, and A. Knoll. Pm-huber:
Patchmatch with huber regularization for stereo matching.
In Proc. of Int’l Conf. on Computer Vision (ICCV), 2013. 1,
2[15] V. H. Hiep, R. Keriven, P. Labatut, and J.-P. Pons. Towards high-resolution large-scale multi-view stereo. In Proc.
of IEEE Conf. on Computer Vision and Pattern Recognition(CVPR), pages 1430–1437, 2009. 1, 2, 6
[16] M. Kazhdan, M. Bolitho, and H. Hoppe. Poisson surface reconstruction. In Proc. of Sympdium on Geometry Processing,
2006. 5, 6
[17] K. Kolev, T. Pock, and D. Cremers. Anisotropic minimal
surfaces integrating photoconsistency and normal information for multiview stereo. In Proc. of European Conf. on
Computer Vision (ECCV), pages 538–551. Springer, 2010. 6[18] J. Li, E. Li, Y. Chen, L. Xu, and Y. Zhang. Bundled depthmap merging for multi-view stereo. In Proc. of IEEE Conf.
on Computer Vision and Pattern Recognition (CVPR), pages
2769–2776, 2010. 2, 6
[19] P. Merrell, A. Akbarzadeh, L. Wang, P. Mordohai, J.-M.
Frahm, R. Yang, D. Nistér, and M. Pollefeys. Real-time
visibility-based fusion of depth maps. In Proc. of Int’l Conf.
on Computer Vision (ICCV), 2007. 2[20] R. A. Newcombe and A. J. Davison. Live dense reconstruction with a single moving camera. In Proc. of IEEE Conf.
on Computer Vision and Pattern Recognition (CVPR), pages
1498–1505. IEEE, 2010. 2[21] A. Oliva and A. Torralba. Modeling the shape of the scene: A
holistic representation of the spatial envelope. Int’l Journalof Computer Vision, 42(3):145–175, 2001. 2[22] J.-P. Pons, R. Keriven, and O. Faugeras. Modelling dynamic
scenes by registering multi-view image sequences. In Proc.
of IEEE Conf. on Computer Vision and Pattern Recognition(CVPR), volume 2, pages 822–827, 2005. 2[23] G. Rong and T.-S. Tan. Jump flooding in gpu with applications to voronoi diagram and distance transform. In Proc. of
Symposium on Interactive 3D Graphics and Games, pages
109–116, 2006. 7[24] D. Scharstein and R. Szeliski. A taxonomy and evaluationof dense two-frame stereo correspondence algorithms. Int’l
Journal of Computer Vision, 47:742, 2002. 2[25] S. Seitz, B. Curless, J. Diebel, D. Scharstein, and R. Szeliski.
Middlebury stereo vision webpage.
http://www.
middlebury.edu/stereo. 1, 5, 6
[26] S. M. Seitz, B. Curless, J. Diebel, D. Scharstein, andR. Szeliski. A comparison and evaluation of multi-view
stereo reconstruction algorithms. In Proc. of IEEE Conf.
on Computer Vision and Pattern Recognition (CVPR), pages
519–528, 2006. 5[27] S. Shen. Accurate multiple view 3d reconstruction using
patch-based stereo for large-scale scenes. IEEE transactions
on image processing, 22(5):1901–1914, 2013. 1[28] N. Snavely, S. M. Seitz, and R. Szeliski. Photo tourism: exploring photo collections in 3d. In ACM Trans. on Graph.,volume 25, pages 835–846, 2006. 6[29] N. Snavely, S. M. Seitz, and R. Szeliski. Modeling the worldfrom internet photo collections. Int’l Journal of Computer
Vision, 80(2):189–210, 2008. 3[30] C. Strecha. Dense mvs dataset.
http://cvlabwww.epfl.ch/˜strecha/
multiview/denseMVS.html. 1, 5, 6, 7
[31] J. Stühmer, S. Gumhold, and D. Cremers. Real-time dense
geometry from a handheld camera. In Pattern Recognition,
pages 11–20. Springer, 2010. 2[32] P. Tanskanen, K. Kolev, L. Meier, F. Camposeco, O. Saurer,and M. Pollefeys. Live metric 3d reconstruction on mobile
phones. In Proc. of Int’l Conf. on Computer Vision (ICCV).
IEEE, 2013. 2[33] E. Tola, C. Strecha, and P. Fua. Efficient large scale multiview stereo for ultra high resolution image sets. Machine
Vision and Applications, 23(5):903–920, 2012. 1[34] C. Wu. Visualsfm: A visual structure from motion system.
http://ccwu.me/vsfm/, 2011. 3, 6[35] A. Zaharescu, C. Cagniart, S. Ilic, E. Boyer, R. Horaud, et al.
Camera-clustering for multi-resolution 3–d surface reconstruction. In Workshop on Multi-camera and Multi-modal
Sensor Fusion Algorithms and Applications-M2SFA2 2008,2008. 2