SURFACE COMPLETION OF SHAPE AND TEXTURE BASED ON ENERGY MINIMIZATION
Norihiko Kawai∗ , Avideh Zakhor

Tomokazu Sato, Naokazu Yokoya

EECS Department
University of California, Berkeley
Berkeley, California, USA

Graduate School of Information Science
Nara Institute of Science and Technology
8916-5 Takayama, Ikoma, Nara, Japan

ABSTRACTIn this paper, we propose a novel surface completion methodto generate plausible shapes and textures for missing regionsof 3D models. The missing regions are filled in by minimizing two energy functions for shape and texture, which are bothbased on similarities between the missing region and the restof the object; in doing so, we take into account the positive
correlation between shape and texture. We demonstrate theeffectiveness of the proposed method experimentally by applying it to two models.
Index Terms— Surface Completion, Shape and Texture,
Energy Minimization
1. INTRODUCTION
Surface completion is a technique for filling in missing regions in 3D models caused by sensing errors and occlusions
in measuring target objects. Surface completion methods canbe broadly classified into two categories: one uses information around missing regions and the other uses exemplars in
the rest of the object, referred to as data region. The former methods [1–4] fill in missing regions with smooth surface
patches using partial differential equations or signed distancefield. These methods are effective for small gaps but cannot generate complex shapes. Therefore, the latter methods
such as [5–10] have recently been developed so as to generatecomplex shapes in missing regions.
A number of surface completion algorithms in recentyears have dealt with both shape and color, rather than shapealone [6–8]. These methods calculate the similarities ofshape and color between missing and data regions, and generate complex shape and texture by copying the similar patch
to the missing region. For instance, in [6], one similar patch
whose size is almost the same as a missing region is required
to exist in the model. In [7, 8], similar local patches are
successively copied to the missing region from the outer tothe inner part; as such, a discontinuous surface may be generated on the seam in the completed model. Also, sample∗ Rsearch Fellow supported by the Ministry of Education, Science, Sportsand Culture, Grant-in-Aid for JSPS Fellows, 21-8045.

shape and color are selected from the same position in thesemethods. While there is correlation between shape and colorof many objects, similar shapes do not necessarily always
have the same texture. Therefore, unnatural shape and color
could potentially be generated due to the limited available
exemplars.
In this paper, we propose a surface completion method bytaking into account shape and texture simultaneously. Specifically, we minimize two energy functions for shape and texture
by extending our previous energy function in [9, 10], which isonly based on the shape similarity between missing and dataregions. In this paper, shape and color in missing regions
are determined as a global solution by minimizing the twoenergy functions in an iterative fashion. In addition, sample
shapes and textures can be selected from different positions,while the positive correlation between shape and texture istaken into account. Target models in this research consist ofvertices, triangles and texture images where the correspondence of coordinates between vertices and texture images isassumed to be known.
2. PROPOSED APPROACH
Our surface completion process can be described as follows:(a) the user manually selects missing regions to be repaired ina model; (b) initial position and color are assigned to vertices
and triangles in the missing regions; (c) the position and colorof vertices in the missing region are updated iteratively so as
to minimize the two energy functions. Section 2.1 describes
the energy function, and Section 2.2 describes the minimization of the energy functions.
2.1. Energy functions for shape and texture similarity
As illustrated in Fig. 1, a 3D model is first divided into region Ω which includes missing region Ω selected by the user,and data region Φ which is the remainder of the object. Ω isdetermined so that spherical patch Api with radius l and central vertex pi ∈ Ω , includes at least one vertex in region Ω.
Two energy functions, Es for shape and Et for texture, aredefined based on the weighted sum of shape similarity SSDsand texture similarity SSDt between vertices in region Ω andApnData region ΦSimilar
textureBasis vectors

pnApm

patchpm

SimilarshapeMissingregion ΩpiApi

Alignment

Texture image

I ( h ( p j , pi , p k ))Ω′h( p j , p i , p k )I (pk )

pkpi ∈ΩEt =pi ∈Ωλpi (SSDt (pi , pn ) + βSSDs (pi , pn ))/pi ∈Ω (1)λpi ,pi ∈Ω(2)In the above energy functions, there are four kinds of variables: vertex’s 3D position pi , intensity I(pi ) of vertex pi ,position pm of similar shape, and position pn of similar texture in region Φ corresponding to vertex pi . Weight wpi is set
to 1 if pi ∈ Ω ∩ Ω because the positions of vertices in this region are known and fixed; otherwise wpi is set to c−d whered is the minimum number of links from all vertices on theboundary of Ω to vertex pi , and c is a positive constant; thisis because the confidence level is higher for position of vertices near the boundary than those in the center of the missing region. Weight λpi is defined in a similar way as wpi .
Weights α and β are the relative importance of shape versus
texture similarity in searching for similar shape and texture.
The minimization is done with respect to all the vertices in Ω.
Eqs. (1) and (2) are normalized with respect to sum of weights
because the weight of each vertex changes in the energy minimization process. In the following, the similarity measures
SSDs and SSDt are described in detail.
As shape similarity SSDs , we employ the same measure
as our previous method [10]. Concretely, the surface around
pj in data region Φ is aligned to vertices around pi in Ωso that 3D position and basis vectors of vertex pj overlap
those of vertex pi as shown in Fig. 2. The basis vectors are
determined using directions of normal and principal curvatures [10]. We refer to the normal basis vector of a vertex as
its ”normal vector”. SSD(pi , pj ) is computed as the sum ofdistances between vertices in spherical patch Api with radiusl and central vertex pi ∈ Ω , and the aligned surface aroundpj ∈ Φ as follows:  pk − h(pj , pi , pk ) 2,SSDs (pi , pj ) =N (Api )(3)pk ∈Api

where h(pj , pi , pk ) is the 3D position of the intersection of
the aligned surface with the normal line for vertex pk ∈ Api .

Surface in Φpi

vertices in Ω′Fig. 1. Missing and data regions in a 3D model.
surface in data region Φ. In doing so, the positive correlation
between shape and texture is taken into account as follows:Es =
wpi (SSDs (pi , pm )+αSSDt (pi , pm ))/wp i ,Basisvectors

pjFig. 2. Alignment of vertices and surface for similarity measure of shape and texture.
By normal line for pi , we mean the line passing through pi inthe direction of normal vector for pi . N (Api ) is the number ofvertices in spherical patch Api . As shown in Fig. 2, intuitively
SSD(pi , pj ) represents the distance between all neighboring
points to pi , namely pk , and their projection onto the aligned
surface corresponding to point pj in the data region.
Similarly, texture similarity SSDt is defined as the sum ofdifference in color between vertices in patch Api and texture
on aligned surface around pj as follows:
SSDt (pi , pj ) =  I(pk ) − I(h(pj , pi , pk )) 2, (4)N (Api )pk ∈Api

2.2. Energy minimization
After initializing vertices’ positions and colors in the missing
region as in step (b), they are iteratively updated in step (c)so as to minimize Es and Et jointly. Step (c) consists of fiveprocesses. In the first three processes, we calculate the optimal positions of vertices in Ω so as to minimize Es , and in
the second two processes, we calculate the optimal colors ofvertices in Ω so as to minimize Et . Specifically, the following
processes are iterated until convergence: (c-1) parallel searchfor similar shape patches; (c-2) parallel update of positions ofall vertices in Ω; (c-3) inserting and merging of vertices in Ω;(c-4) parallel search for similar texture patches; (c-5) parallel
update of colors of all vertices in Ω.
In practice, the update of vertex positions for minimizing Es influences energy Et and vice versa. However, suchinfluences are decreased with iterations as each energy term
converges. In the following subsections, each process is described in more detail.
2.2.1. Minimizing energy for shape
This subsection describes the method for minimizing energy
Es for shape, covering processes (c-1) through (c-3). In process (c-1), a data region is searched for the most similar shape
patch keeping positions and colors of vertices in Ω fixed. The
position p̂i of the shape patch most similar to the patch aroundpi ∈ Ω is determined by the following equation:p̂i = argmin(SSDs (pi , pm ) + αSSDt (pi , pm )).
pm ∈Φp̂ k(5)Here, correlation between shape and texture is taken into account by calculating not only shape similarity but also texture
similarity.
In process (c-2), the positions of all vertices in the missing region are updated in parallel in the similar way to [10].
In the following, we briefly describe the method for calculating the position of vertex pi when the position of the mostsimilar shape patch is known. Here, SSDt in Es can be ignored because colors of vertices are fixed. Energy Es can be
decomposed into element energy Es (pi ) (∀pi ∈ Ω) which
includes only position pi as a parameter:
w pk
 pi − h(pˆk , pk , pi ) 2 . (6)Es (pi ) =N (Api )pk ∈Api

The relationship between energy Es and element energyEs (pi ) can then be expressed as follows:Es =Es (pi ) + C,(7)pi ∈Ωwhere C is constant denoting the energy for the vertices in region Ω ∩ Ω ; this is because the positions of vertices are fixedand known in this region in the process (c-2). Our approach tominimize Es is to minimize each element energy Es (pi ) independently. To do so, we note in Fig. 3 that all the corresponding points h(p̂k , pk , pi ) (∀pk ∈ Api ) exist on the normal line
for vertex pi because of the definition of h(p̂k , pk , pi ). Therefore, assuming the normal vector of pi does not change after
updating the positions of neighboring points to pi , the position pi that minimizes Es (pi ) can be approximated as follows:pi ≈wpk h(p̂k , pk , pi )/wp k .
(8)
pk ∈Api

Surface in Φpk ∈Api

In practice, the value in Eq. (8) is only an approximate solution to minimize Es (pi ) because the normal direction doeschange due to the update of the positions of vertices. Nevertheless, a reasonably good solution can be obtained as theenergy converges because the change in the normal vector becomes smaller as the energy converges.
In process (c-3), the spatial distribution of vertices in Ω ismade uniform by inserting and merging vertices while taking
into account their density; this is because the update of vertex positions in process (c-2) biases the spatial distribution.
In particular, we employ upper and lower thresholds for thelength of a side of a triangle. If a side is longer than the upper
threshold, a vertex is added to the midpoint of the side. The
color of the new vertex is calculated by averaging colors oftwo vertices on the side. If a side is shorter than the lower
threshold, two vertices on the side are merged and the newvertex is put on the midpoint of the side. The color is theaverage of colors of the two vertices.

h( pˆ k , p k , pi )Normal line for p i

pi p kvertices in Ω′

Fig. 3. Corresponding points on the normal line for vertex pi .
2.2.2. Minimizing energy for texture
After the update of vertices’ positions in Ω, colors of verticesin Ω are updated so as to minimize energy Et for texture,
covering processes (c-4) and (c-5). In process (c-4), a dataregion is searched for the most similar texture patch keeping
positions and colors of vertices in Ω fixed. Here, correlationbetween shape and texture is taken into account as well as
searching for similar shapes. The position p̃i of the texture
patch most similar to the texture around pi ∈ Ω is determinedby the following:p̃i = argmin(SSDt (pi , pn ) + βSSDs (pi , pn )).
pn ∈Φ

(9)

In process (c-5), the color of all vertices in the missing region are updated in parallel using the same idea as in process(c-2). Here, SSDs in Et can be ignored. Energy Et can also
be decomposed into element energy Et (pi ) as follows:Et (pi ) =pk ∈Apiλpk
 I(pi ) − I(h(p̃k , pk , pi )) 2 .
N (Api )(10)
Therefore, color I(pi ) that minimizes Et (pi ) is calculated asfollows:
λpk I(h(p̃k , pk , pi ))/λ pk .
(11)
I(pi ) =pk ∈Api

pk ∈Api

2.2.3. Coarse-to-fine approach
In order to efficiently complete the missing regions and avoid
local minima, a coarse-to-fine approach is employed for energy minimization. Here, every time the energy converges, radius l of spherical patch Api is decreased, and the number ofvertices in region Ω used for calculating energy is increased
by changing the thresholds in process (c-3) for density of vertices. In addition, a pyramid for the texture image is generated
offline and the resolution of a texture image is increased fromthe coarse to fine.
3. EXPERIMENTS
To demonstrate the effectiveness of the proposed method, we
have applied the method to two models: an indoor modelwith 453,281 vertices which is created using indoor localization and modeling algorithm [11] as shown in Fig. 4(a), and a(a) Indoor model with holes(a) Bowl model with a hole(b) Completed model (β =0.5)(c) Completed model (β = 0)(d) Completed model (b) withno texture(b) Completed model(c) Close-up of a hole(d) Close-up of a completed
holeFig. 4. Completion for a indoor model with holes.
small bowl model with 4,680 vertices as shown in Fig. 5(a).
A missing region of the bowl model is generated manually. In
the experiments, the average position and color of the boundary vertices of the missing region are used as an initial vertex’s position and color in the missing region. We use a PC
with Core i7 1.6GHz CPU and 8GB of memory.
As for the completion of the indoor model, the entire
model is divided into multiple partial sub-models each with
only one hole. Then each hole is filled in individually.
Fig. 4(b) shows the completed model, and Figs. 4(c) and4(d) show the close-up of one of the holes before and after
completion. From these figures, we can confirm that natural
shapes and textures are generated in the holes. It took 13,868
seconds to complete the all holes for this model.
As for the completion for the bowl model which has asmooth curved surface and bumps along the texture edges, weshow two kinds of results using different weights β for SSDs
in Et . In the completed model of Fig. 5(b) with β = 0.5,
texture edges are generated in the missing region. On theother hand, plausible edges are not generated in the completed
model of Fig. 5(c) with β = 0. From this difference in results,
we can confirm that taking into account correlation between
shape and texture similarity is effective. However, the generated texture is slightly blurred because the resolution of texture is higher than the resolution of vertices. Finally, Fig. 5(d)shows the completed model in Fig. 5(b) without texture. As
seen, natural shapes are generated in the missing region. It
took 512 seconds to complete the hole for this model.
4. CONCLUSIONSIn this paper, we have presented a novel method for surface
completion of shape and texture based on energy minimiza-Fig. 5. Completion for a bowl model with a hole.
tion and demonstrated its effectiveness experimentally on twodatasets. Future work involves increased resolution of generated texture. In addition, our method can be applied to 3Dmodels for large environments such as outdoor scenes.
5. REFERENCES[1] J. Davis, S.R. Marschner, M. Garr, and M. Levoy, “Filling Holes inComplex Surfaces Using Volumetric Diffusion,” in Proc. Int. Symp. on
3DPVT, 2002, pp. 428–438.
[2] J. Verdera, V. Caselles, M. Bertalmio, and G. Sapiro, “Inpainting Surface Holes,” in Proc. ICIP, 2003, vol. 2, pp. 903–906.
[3] R. Furukawa, T. Itano, A. Morisaka, and H. Kawasaki, “Improved
Space Carving Method for Merging and Interpolating Multiple Range
Images Using Information of Light Sources of Active Stereo,” in Proc.
ACCV, 2007, pp. 206–216.
[4] R. Sagawa and K. Ikeuchi, “Hole Filling of a 3D Model by Flipping
Signs of a Signed Distance Field in Adaptive Resolution,” IEEE Trans.
on PAMI, pp. 686–699, 2008.
[5] A. Sharf, M. Alexa, and D. Cohen-Or, “Context-based Surface Completion,” in Proc. ACM SIGGRAPH, 2004, pp. 878–887.
[6] S. Park, X. Guo, H. Shin, and H. Qin, “Surface Completion for Shapeand Appearance,” in Int. J. of Computer Graphics, 2006, vol. 22, No.
3, pp. 168 – 180.
[7] T.P Breckon and R. B. Fisher, “Plausible 3D Colour Surface Completion Using Non-parametric Techniques,” in Proc. Int. Conf. on theMathematics of Surfaces, 2005, pp. 102 – 120.
[8] J. Dong, S. Ma, L. Li, and Z. Yu, “Hole Filling on Three-Dimensional
Surface Texture,” in Proc. ICME, 2007, pp. 1299–1302.
[9] N. Kawai, T. Sato, and N. Yokoya, “Surface Completion by Minimizing
Energy Based on Similarity of Shape,” in Proc. ICIP, 2008, pp. 1532–1535.
[10] N. Kawai, T. Sato, and N. Yokoya, “Efficient Sufrace Completion Using Principal Curvature and Its Evaluation,” in Proc. ICIP, 2009, pp.
521–524.
[11] G. Chen, J. Kua, S. Shum, N. Naikal, M. Carlberg, and A. Zakhor, “Indoor Localization Algorithms for a Human-Operated Backpack System,” in Proc. Int. Symp. on 3DPVT, 2010.