GEODESIC NEIGHBORHOODS FOR PIECEWISE AFFINE INTERPOLATION OF SPARSE DATA Gabriele Facciolo and Vicent Caselles Departament de Tecnologies de la Informaci´o i les Comunicacions, Universitat Pompeu Fabra - Barcelona gabriele.facciolo@upf.edu, vicent.caselles@upf.edu Abstract We propose a new interpolation method for sparse data that al- lows incorporation of geometric information of a reference image u. The idea consists in deﬁning a geodesic Voronoi cell for each data sample, and ﬁt a model to interpolate inside each cell. A geodesic distance permits both: to effectively adapt the shape of the cells to the image structures; and to compute a set of neighboring samples that are used for ﬁtting a piecewise afﬁne model at each cell. Objective Interpolate a set of range measurements (LIDAR or sparse disparity data [1]) using the additional knowledge provided by a photograph u of the scene. Samples with known depth (5% of the total pixels). Reference image u. Interpolated samples. Lambertian hypothesis: a uniform surface with a constant angle has a constant inten- sity in the image. Allows to extrapolate information across uni- form regions of the image. Geodesic Voronoi Cells and Neighborhoods We use the geodesic distance to incorporate the radiometric information provided by the im- age u into the interpolation as in [2]. Reference Image u(x) : Ω→R+, with Ω⊂R2. Positions of the samples Λ ⊂Ω. Depth values of samples G(λ) : Λ →R, λ ∈Λ. Curve C(p) : [0, 1] →Ω, and Cs,t curve con- necting s and t. Geodesic distance between s and t measures the minimum variation of u between s and t d(s, t) = min Cs,t Z 1 0 |∇u · ˙Cs,t(p)| + ε| ˙Cs,t(p)|dp Observe: The shortest path is the one with less discontinuities of u along it. Geodesic Voronoi diagram of the sites in Λ, successfully accounts for discontinuities in the image. Geodesic neighborhood GNK(p) of the point p, is the set formed by the K-nearest (in the geodesic sense) samples of Λ to the point p. Samples in GNK(p) are likely to have the same model as p. Reference image Samples & Voronoi cells Geodesic Voronoi cells Geodesic Neighborhood Robust afﬁne plane interpolation using GNK Proﬁle: Linear blend of the 5 nearest (geodesic) samples Proﬁle: Afﬁne plane estim. using the same 5 samples For each point p ∈Λ we ﬁt an afﬁne plane trough GNK(p). Then we extended the plane to the entire cell, the initial piecewise afﬁne model H is the union of all the cells. If GNK(p) contains outlier samples (that do not belong to the same surface as p) then the result will be bi- ased. To remove these outliers we use a modiﬁed RANdom SAmple Consensus (RANSAC) [4]. Constrained region merging Problem: When interpolating noisy data • the model of each cell is independently estimated, • adjacent cells may end up with different models. Our solution: Merge adjacent regions with compati- ble models, and compute a common model to reduce noise effects. Result without merging Before merging After merging Simpliﬁed Mumford-Shah [5] minimizes E(B, f) = P R∈P(Ω) RErr(R, f) + λ R B g(s)ds, λ ≥0. • Error term: RErr(X, f) = P x∈X∩Λ |fX(x) −H(x)|2 H: the initial plane interpolation fX: the afﬁne model for the region X • Boundary lenght: g(s) is big at poorly contrasted bound- aries and small at well contrasted ones. • Also constrained by the segments of the original image [6]. • Greedy algorithm: merges pair of regions while the error term is small. Results Image Sample Positions Result model Regions Discussion • Method for interpolating range data that incorporates the geometric infor- mation provided by an image of the scene. • Geodesic neighborhoods constitute a fast and robust tool for modelling the local information, it can be adapted to other (non-afﬁne) models [3]. • Poor results for badly contrasted edges between strongly textured regions. More results at: http://gpi.upf.edu/static/geoint . References 1. N. Sabater, A. Almansa, and J-M. Morel, “Rejecting wrong matches in stereovision,” CMLA Preprint, 2008. 2. L. Yatz