DEPTH MAP INPAINTING AND SUPER-RESOLUTION BASED ON INTERNAL STATISTICS
OF GEOMETRY AND APPEARANCE
Satoshi Ikehata†, Ji-Ho Cho‡ and Kiyoharu Aizawa††The University of Tokyo, ‡Vienna University of Technology
ABSTRACT
Depth maps captured by multiple sensors often suffer frompoor resolution and missing pixels caused by low reflectivity and occlusions in the scene. To address these problems,
we propose a combined framework of patch-based inpainting
and super-resolution. Unlike previous works, which reliedsolely on depth information, we explicitly take advantage ofthe internal statistics of a depth map and a registered highresolution texture image that capture the same scene. We
account these statistics to locate non-local patches for holefilling and constrain the sparse coding-based super-resolution
problem. Extensive evaluations are performed and show thestate-of-the-art performance when using real-world datasets.
Index Terms— depth-map super-resolution, depth-map
inpainting, ToF sensor, sparse Bayesian learning
1. INTRODUCTION
Dynamic 3D scene geometry acquisition methods are a major research topic in image processing and computer vision.
Various depth acquisition methods have been proposed todate; these can generally be categorized into two approaches:
passive and active. While passive approaches generate a disparity map of the scene by multiple image correspondences
and triangulation [1, 2], active sensors, e.g., time-of-flight(ToF) cameras, measure the distance from the camera to theobjects directly using active infrared illumination. In reality,
however, depth maps acquired by these sensors often contain
unreliable areas where the scene contains occluded regions
or objects with low reflectivity. Also, a depth map captured
by a ToF camera has very low-resolution (e.g., 176×144
in Swiss Ranger SR4000). Some extra image processing
steps are therefore required: depth map inpainting and superresolution.
While image inpainting methods have been studied [3,4, 5], there is very little available literature on depth-map
inpainting [6]. To the best of our knowledge, there is nowork which uses a registered high-resolution texture image
for depth-map inpainting. In contrast, many works on depthmap super-resolution exist, and they are mainly categorizedThis work was partially supported by the Grants-in-Aid for JSPS Fellows(No. 248615) and the Austrian Science Fund (FWF, M1383-N23).

into two classes. One class determines depth values at interpolated coordinates of the input domain in the manner of
local filtering [7, 8, 9] or Markov random field (MRF) modeling [10, 11], which uses a registered high-resolution texture
image to preserve sharp boundaries. While effective, thisapproach is critically sensitive to the texture image quality.
The second class is motivated by image super-resolution literature, which explicitly considers the low-resolution image
generation process. Some algorithms in this class reconstruct a high-resolution depth map of a static scene by fusing
multiple low-resolution depth maps that were observed together [12, 13]. More recently, learning-based single image
super-resolution techniques were integrated into depth-map
super-resolution to handle dynamic scenes. Aodha et al. [14]learned the statistics of low-resolution and high-resolution
depth patches from external training sets and used them to
upsample a new low-resolution depth map in the MRF formation. In contrast, Li et al. [15] derived a mapping function
from a low-resolution depth patch and its correspondingcolor patch to a high-resolution depth patch via sparse coding. However, they require a large number of external clean
training sets and time-consuming dictionary learning for eachmagnification factor. Also, the external statistics merely capture the co-occurring structures of depth and texture because
each scene in the training set is completely different.
In this paper, we propose a new method for depth map
inpainting and super-resolution which can produce a densehigh-resolution depth map from a corrupted low-resolution
depth map and its corresponding high-resolution texture image. Both steps use the internal statistics of the input geometry and appearance (i.e., recurrence of the co-occurring
structures of depth/texture patches), which are learned directly from the input depth/texture images. We account for
the registered texture image to locate non-local patches forhole filling and constrain the sparse coding problem withpatch-based super-resolution.
2. PROPOSED METHOD
In this section, we formulate a combined framework fordepth-map inpainting and super-resolution. Let Dl0 andIl1 be a low-resolution depth map and a registered highresolution texture image, and let Dl1 be a high-resolution

depth map. We denote the hole and source regions in Dl0 as
H and S(, Dl0 \ H). The problem is how to reconstruct
Dl1 from Dl0 and Il1 while filling H in Dl0 . We solve these
problems separately under these assumptions: (1) The relative position between the color and depth cameras is known;(2) The missing pixel region in the input depth map is known.

Here, NH is the number of missing pixels in xH i , and M isa sampling matrix which extracts xH i ∩ S. The weighting
factors wD and wI reasonably quantify the trustworthiness ofthe depth/texture information as follows:



NC
,
(5)
1
−
wD = 1 − NpH
2
NC
max

2.1. Patch-based depth map inpainting using internal
statistics of geometry and appearance
We extract two different sets, V, W , of the overlapped p × p
depth patches xS i ∈ Rp×p , xH i ∈ Rp×p from Dl0 asV,{xS i |i = 1, · · · , n, xS i ∈ S},W,{xH i |i = 1, · · · , m, {xH i ∩ S} 6= ∅, {xH i ∩ H} 6= ∅}.

(1)

In general patch-based image inpainting methods [3], hole regions in xH i are restored iteratively by example-based synthesis where a missing structure is propagated from a source
patch (xS i ) with a partially similar structure. Once one patch
is inpainted, it is used as a new source, and all inpainted
patches are finally merged into a completely reconstructed
depth map. While effective, this propagation scheme is sensitive to the filling order, which is inevitable when the missing
region is larger than a patch size. To overcome this difficulty,
our method utilizes another source, i.e. the texture image.
We divide the low-resolution texture image (Il0 ), which is
downsampled from Il1 , into overlapped patches yS i ∈ Rp×p
and yH i ∈ Rp×p with spatial positions that are the same asxS i and xH i . xi ∈ {xS i , xH i } and yi ∈ {yS i , yH i } represent the same scene in the different domains (i.e., in geometry and appearance), and thus their structures are likely to becorrelated with each other. We observe that this relationshiptends to recur again in the close vicinity of the same images,
which implies that if the structures of two sufficiently close
depth patches are similar, then corresponding texture patches
are also similar and vice versa (i.e., yi ' yj ↔ xi ' xj ). We
confirmed these statistics by simple inpainting experiments
shown in Fig. 1, where missing regions in a depth patch weresynthesized from the nearest neighbor depth patch, where thedistance was defined by depth or corresponding texture information. We found that appropriate depth patches could
be retrieved even in depth-less areas using texture information; however, texture information did not contribute when
the patch was extracted from a distant region.
Following observations above, we find a pair of xH i ∈W and xS j ∈ V with the smallest depth/texture combined
distance defined as follow,
f (xH i , xS j ) = wD dD (xH i , xS j ) + wI dI (yH i , yS j ), (2)where yH i and yS j are extracted at same positions of xH iand xS j , and dD and dI are defined as,
1
kM (xH i − xS j )k22 ,dD (xH i , xS j ) , p2 −NH

dI (yH i , yS j ), p12 kyH i − yS j k22 .

(3)
(4)

2

= e−kyhc −ysc k2 /2σy .

wI

(6)

Here σy is a variance in the Gaussian function (4.0 in our
implementation), Nc counts the connections of holes amongfour neighbors and NCmax is the maximum possible number of connections. wD is designed from our observations
such that the depth patch is informative when the number ofholes is small and the holes are sparsely distributed rather
than concentrated locally. yhc and ysc are the center positions of yH i and yS j . wI reflects our observation that thecorrelation between depth and texture decreases as the spatial
distance between yH i and yS j increases. Once every yH ifind their corresponding yS j , hole regions are synthesizedby overlapped nearest neighbor source patches via a votingbased approach [16] to acquire a final purified depth map. After the low-resolution depth map is restored, super-resolution
is applied to it, and is discussed in the next section.
2.2. Patch-based super-resolution using internal statistics
of geometry and appearance
A recent study of the internal statistics of a natural image [17]stated that most small image patches in a natural image tend
to recur redundantly inside the image across different scales.
This observation forms the basis of the internal examplebased single image super-resolution approach [18, 17], and
we also learn a set of high-resolution/low-resolution pairsof depth patches implicitly by using patch repetitions acrossmultiple image scales,
X , {(xi , yi )|i = 1, · · · , n, xi ∈ Dl−1 , yi ∈ Dl0 }.
2

2

(7)

Here yj ∈ Rh ×1 and xi ∈ Rl ×1 are vector representations of all possible h × h and l × l overlapped depth patches
that are extracted from the same position of Dl0 and Dl−1 ,which is a depth map downsampled from Dl0 by the magnification factor r (= h/l). Let p denote a l × l depth patch in
Dl0 to be upsampled. We can search for similar patches fromthe learned patches (xi , i = 1, · · · , k) in Dl−1 (e.g., using ak-approximate nearest neighbor search [19]) and their corresponding high-resolution patches (yi , i = 1, · · · , k) provide astrong prior indication of the appearance of a high-resolution
unknown patch (y ∗ ) in Dl1 . However, simply averaging thesehigh-resolution patches (yi ) to recover an overall estimate of(y ∗ ) like [17] is problematic for depth-map super-resolution
because of its blurring effect (which stems from multiple inconsistent high-resolution interpretations). However, only using the best patch reconstructs a false high-resolution edge

(a) Input color image(b) Input depth map(c) Inpainted by depth(d) Inpainted by texture(e) Ours(f) Wohlberg [5]Fig. 1. Experimental results of patch-based depth map inpainting. Hole regions were synthesized by the nearest neighborpatches in the same image, which were found by using (c) depth information only, (d) texture information only, (e) both depth
and texture information (proposed method). And we show the inpainted result by the method of Wohlverg [5] in (f).
when there is no ideally similar low-resolution patch in X. To
overcome these issues, we instead solve the following problem:µ1(8)
min 2 kp − φL αk22 + 2 kq − ψH αk22 + λkαk0 .
α lh2Here, φL ∈ Rl ×k is a matrix which consists of p’s k-nearest
2
neighbors (i.e., φL , [x1 , · · · , xk ]) and ψH ∈ Rh ×k is amatrix consisting of vectorized h × h texture patches in Il1
2
with the same location of each xi (i = 1, · · · , k). q ∈ Rh ×1
is a high-resolution texture patch in Il1 with the same location as p. α ∈ Rk×1 is a coefficient vector and µ and λ aretrade-off parameters which are fixed as 0.05 and 10−6 in our
implementation, respectively. k · k0 is an `0 -norm penalty,
which counts the number of non-zero entries in the matrix.
The process contains two essential elements. First, we introduce a sparsity penalty which is applied to α to reconstruct
a high-resolution depth patch with the smallest possible combination of learned patches. This penalty avoids the visual
artifacts caused by multiple inconsistent high-resolution interpretations, especially in the case of large k. Second, we
introduce a texture constraint which quantifies the observed
internal statistics that the geometry and appearance of thesame scene should be correlated with each other. Intuitively,
the coefficients (α) are recovered such that the target depth
patch (p) is synthesized from the sparsest possible combination of learned depth patches (φL α) and the reconstructedhigh-resolution texture patch (ψH α) is consistent with theregistered high-resolution texture image (Il1 ). Then, Eq. (8)can be transformed into the standard description of sparse
coding as,
min kb − Aαk22 + λkαk0 ,
(9)
α

√
√
where b , [p/l, µq/h]T and A , [φL /l, µψH /h]T .
Eq. (9) entails a difficult combinatorial optimization problem
that must be solved efficiently at every patch. In most superresolution literature, it is common to replace the discontinuous non-convex `0 norm with the convex surrogate `1 norm.
However, we instead apply a hierarchical Bayesian approximation called sparse Bayesian learning (SBL) to estimate αwhich has been proved to give a better approximation of `0
norm [20].

2.3. Recovery of α and merging of high-res patches
SBL [21] assumes a standard Gaussian likelihood function for
the first-level diffuse errors giving p(b|α) = N (b; Aα, λI),2222where I ∈ R(h +l )×(h +l ) is the identity matrix. We thenapply independent zero-mean Gaussian prior distributions to
α as p(α) = N (α; 0, Γ). Γ , [γ1 , · · · , γn+1 ]T is a nonnegative vector of the variances in one-to-one correspondencewith elements of α. A small or zero-valued variance of γi
implies that the associated αi is constrained to be near zero.
Combining the likelihood and the prior using Bayes’ ruleleads to the posterior distribution p(α|b) ∝ p(b|α)p(α). The
main issue for estimation of α is the value of the unknown
parameter Γ. Without prior knowledge of the locations of thezero coefficients, the empirical Bayesian approach to learning Γ is to maximize the resulting likelihood function withrespect to Γ [21]. Equivalently, we minimize,Z
L(Γ) , − log p(b|α)p(α)dα(10)≡ log |Σb | + bT Σ−1b b withΣb , AΓAT + λI,

with respect to Γ. While L(Γ) is non-convex, optimization can be accomplished by adapting the majorizationminimization approach from [20]. This technique essentiallyinvolves the construction of rigorous upper bounds on two
terms in Eq. (11). While space precludes a detailed treatmentin this paper, the resulting update rules for the (k + 1)-th
iteration are given by
γi

(k+1)

→


2
(k)
(k)
αi
+ zi , ∀i,zi (k+1)

→

γi

(k+1)

→

α

(k) 2

Γ(k+1) = diag[γ (k+1) ],− γi ATi (λI + AΓ(k) AT )−1 Ai ,−1Γ(k) AT λI + AΓ(k) AT
b.
(k)

(11)

Note that each γi is initialized with a random value. These
expressions only require O(k) computations, and are guaranteed to reduce L(Γ) until a fixed point Γ∗ is reached.
When a collection of overlapped patches {yi∗ = φH α∗i |i =1, · · · , n}, where φH is the high-resolution pairs of φL , isreconstructed, we merge them into a single high-resolution
depth map. Because simple averaging of the depth values over
the overlapping regions is sensitive to outliers, we introduce aweighting factor calculated from the photo-consistency of thereconstruction. The value of j-th pixel in the high-resolution
depth map Dlj1 is calculated as:
Dlj1 =

1
Nj

X

e

−

Ph2
∗
2
j=1 (IH i,j −IH i,j )2σISyi∗ ,(12)∀yi∗ |Dlj ∩yi∗ 6=∅
1
Ph2

∗

Table 1. Performance comparison with four real datasets.
Root mean square error (RMSE)

Ave. running time

art mebius fountain herzjesu

Ours (full configuration), k=20 1.19 0.61
Ours (w/o constraints), k=20 1.75 1.30
ScSR [22]2.82 3.10
WMF [9]1.46 1.04
PbsSR [14]13.9 14.4
NN
14.2 14.8

1.34
1.69
8.70
1.62
0.50
1.60

1.51
1.56
6.58
1.74
0.78
1.69

1162 (sec)1960 (sec)
275 (sec)
429 (sec)

2

i,j −IH i,j )P − j=1 (IH2σI
where Nj ,e
, S is a sampling operator which extracts the corresponding element in yi∗ . Hi,j isthe j-th element in the reconstructed texture patch that corresponds to a depth patch (yi∗ ) and σI is the variance of theGaussian function (5.0 in our implementation). Intuitively,
we have high confidence in the value when the distance between the reconstructed texture and the original one is small.

3. RESULTS
In this section, we quantitatively evaluate our method using
real data. All experiments were performed on an Intel Core
i7-2640M (2.80 GHz, single thread) machine with 8 GB of
RAM and were implemented in MATLAB.
First, we evaluated our inpainting algorithm from visualinspection of the inpainted results of a manually scratched art
dataset (See Fig. 1). We observed that our method works
for large missing regions, while the state-of-the-art image inpainting method [5] has considerable trouble with them.
Second, we compared our method with three state-ofthe-art SR algorithms: sparse coding based image superresolution (ScSR) [22], patch-based synthesis (PbsSR) [14],and weighted mode filtering (WMF) [9], and also compared
it with nearest neighbor interpolation (NN). We also applied
our method without the texture/sparsity constraints to confirm their contributions to our method. Note that only our
method and WMF use a registered texture image, and external dictionary learning is required in ScSR and PbsSR. In
our implementation, we use l = 3 and k = 20, and use theefficient PatchMatch algorithm [19] to find the k-NN patches.
For ScSR and PbsSR, we used the authors’ implementations
with their default parameter settings and dictionaries, which
are available from their websites. For WMF, we used theparameters described in the original paper, except that weset σI = σS = 15, which worked better than the originalvalues (σI = 6 and σS = 7). Each algorithm is evaluated interms of root mean square error(RMSE) and elapsed time forfour datasets, comprising art and mebius from the Middlebury stereo dataset (which are downsampled to 347× 277),
and the fountainP11 (using only the 6th image) and herzjesuP8 (using only the 5th image) datasets from [23] (which
are downsampled to 345× 230) with a magnifying factor of
4. To make fair comparisons, inpainting is skipped in thisexperiment and the missing pixels in the ground truth depth
map are neglected when calculating the RMSE. The results
are illustrated in Table 1 and Fig. 3. We show that our method

Input and ground truth depth map

Registered Color ImageOurs

ScSR [22]

WMF [9]PbsSR [14]Fig. 2. Reconstructed 4× depth maps of art dataset.

outperforms all of the state-of-the-art algorithms on the art
and mebius datasets and shows the 2nd best performance on
the fountain and herzjesu datasets while ScSR suffers fromblurring effects, WMF appears to be sensitive to texture edges
and PbsSR has problems around the object boundaries.
4. CONCLUSION
In this paper, we have proposed depth-map inpainting andsuper-resolution algorithms which explicitly capture the internal statistics of a depth-map and its registered texture image and have demonstrated their state-of-the-art performance.
The current limitation is that we have assumed the accurate
registration of the texture image and have not assumed thepresence of sensor noise. In future work, we will evaluate ourmethod’s robustness to these problems to assess its handlingof more practical situations.

5. REFERENCES[1] D. Scharstein, R. Szeliski, and R. Zabih, “A taxonomy and evaluation of dense two-frame stereo correspondence algorithms,” in proc. of Workshop on Stereo
and Multi-Baseline Vision. IEEE, 2001.
[2] S. M. Seitz, B. Curless, J. Diebel, D. Scharstein, andR. Szeliski, “A comparison and evaluation of multi-view
stereo reconstruction algorithms,” in proc. of Computer
Vision and Pattern Recognition. IEEE, 2006.
[3] P. Perz and K. Toyama, “Region filling and object removal by exemplar-based image inpainting,” Transactions on Image Processing, vol. 13, no. 9, pp. 1200–
1212, 2004.
[4] A. Criminisi, P. Perez, and K. Toyama, “Region fillingand object removal by exemplar-based image inpainting,” Transactions on Image Processing, vol. 13, no. 9,
pp. 1200–1212, 2004.

[13] S. Schuon, C. Theobalt, J. Davis, and S. Thrun, “Lidarboost: Depth superresolution for tof 3d shape scanning,” in proc. of Computer Vison and Pattern Recognition. IEEE, 2009.
[14] O. M. Aodha, N. D. F. Campbell, A. Nair, and G. J.
Brostow, “Patch based synthesis for single depth image
super-resolution,” in proc. of European Conference on
Computer Vision, 2012.
[15] Y. Li, T. Xue, L. Sun, and J. Liu, “Joint example-based
depth map super-resolution,” in proc. of International
Conference on Multimedia and Expo. IEEE, 2012.
[16] C. Barnes, E. Ahechtman, A. Finkelstein, and D. B.
Goldman, “Patchmatch: A randomized correspondence
algorithm for structural image editing,” Transactions on
Graphics (Proc. SIGGRAPH), vol. 28, no. 3, 2009.
[17] M. Zontak, “Internal statistics of a single natural image,” in proc. of Computer Vision and Pattern Recognition. IEEE, 2011.

[5] B. Wohlberg, “Inpainting by joint optimization of linear
combinations of exemplars,” Signal Processing Letters,
vol. 18, no. 1, pp. 75–78, 2011.

[18] D. Glasner, S. Bagon, and M. Irani, “Super-resolution
from a single image,” in proc. of International Conference onf Computer Vision. IEEE, 2009.

[6] A. V. Bhavsar and A. N. Rajagopalan, “Range map
superresolution-inpainting, and reconstruction fromsparse data,” Computer Vision and Image Understanding, vol. 116, no. 4, pp. 572–591, 2012.

[19] C. Barnes, E. Shechtman, D. B. Goldman, and
A. Finkelstein, “The generalized patchmatch correspondence algorithm,” in proc. of European Conference on
Computer Vision, 2010.

[7] A. K. Riemens, “Multistep joint bilateral depth upsampling,” in proc. of Visual Communications and Image
Processing. SPIE, 2009.

[20] D. Wipf, B. D. Rao, and S. Nagarajan, “Latent variablebayesian models for promoting sparsity,” Transactions
on Information Theory, vol. 57, no. 9, 2011.

[8] K. He, J. Sun, and X. Tang, “Guided image filtering,” inproc. of 11th European Conference on Computer Vision.
IEEE, 2010.

[21] M. Tipping, “Sparse bayesian learning and the relevance
vector machine,” J. Mach. Learns. Res., vol. 1, pp. 211–
244, 2001.

[9] D. Min, J. Lu, and M. N. Do, “Depth video enhancement
based on weighted mode filtering,” Transactions on Image Processing, vol. 21, no. 3, pp. 1176–1190, 2012.

[22] J. Yang, J. Wright, t. Huang, and Y. Ma, “Image superresolution via sparse representation,” Transactions on
Image Processing, vol. 19, no. 11, pp. 2861–2873, 2010.

[10] J. Lu, D. Min, R. S. Pahwa, and M. N. Do, “A revisit
to mrf-based depth map super-resolution and enhancement,” in proc. of International Conference on Acoustics, Speech and Signal Processing. IEEE, 2011.

[23] C. Strecha, W. V. Hansen, L. V. Gool, P. Fua, andU. Thoennessen, “On bench marking camera calibration and multi-view stereo for high resolution imagery,”in proc. of Computer Vision and Pattern Recognition,
2008.

[11] J. Park, H. Kim, Y-W. Tai, M. S. Brown, and I. Kweon,“High quality depth map upsampling for 3d-tof cameras,” in proc. of International Conference on Computer
Vision, 2011.
[12] C. Theobalt, J. Davis, and S. Thrun, “High-quality
scanning using time-of-flight depth superresolution,” inComputer Society Conference on Computer Vision and
Pattern REcognition Workshops. IEEE, 2008.