SURFACE COMPLETION BY MINIMIZING ENERGY BASED ON SIMILARITY OF SHAPE
Norihiko Kawai, Tomokazu Sato and Naokazu Yokoya
Graduate School of Information Science, Nara Institute of Science and Technology
8916-5 Takayama, Ikoma, Nara 630-0192, Japan
norihi-k,tomoka-s,yokoya@is.naist.jp
ABSTRACT
3D mesh models generated with range scanner or video images often have holes due to many occlusions by other objects
and the object itself. This paper proposes a novel method tofill the missing parts in the incomplete models. The missingparts are filled by minimizing the energy function, which isdefined based on similarity of local shape between the missing region and the rest of the object. The proposed method
can generate complex and consistent shapes in the missing
region. In the experiment, the effectiveness of the method is
successfully demonstrated by applying it to complex shapeobjects with missing parts.
Index Terms— Surface Completion, 3D Inpainting, Energy Minimization, Pattern Similarity
1. INTRODUCTION
3D models of real environments are widely used for entertainment and digital archives. Thus, automatic generation of
3D models by using range scanner and video images has beeninvestigated. Such methods can obtain whole 3D models bymeasuring the target objects from multiple view points and integrate the partial shapes. However, when the target is a large
and complex environment such as an outdoor scene, it is difficult to generate the complete 3D models without holes due
to many occlusions. For this problem, lots of surface completion methods which fill the missing regions and obtain complete 3D mesh models have been proposed. These methods
are classified into two categories: One is based on considering the smoothness of surface shape and the other is based onusing example shapes.
As methods considering the smoothness of surface shape,
partial differential equation, moving least squares and Willmore flow have been used for filling holes [1, 2, 3]. Thesemethods can fill the missing regions with smooth surface
patches. Although they are effective for small holes in a 3Dmodel, unnatural shapes may be generated when the missing
parts are large and surrounding shape is complex because themethods cannot generate a complex surface. As another approach considering the smoothness, volumetric-based methods have been proposed [4, 5]. Davis et al. [4] have filledholes by diffusing the signed distance function. This method

largely depends on the location and the number of measuring
points. Thus, it is difficult to obtain good results when the location is grossly one-sided and the number is small. Podolak
et al. [5] have used the graph cut to interpolate a surface.
Though this method can generate a continuous surface, togenerate complex shapes in the missing region, user’s manual
inputs are required.
On the other hand, in order to generate complex shapes inmissing regions, the methods using example shapes on otherparts of the object (data region) have been proposed [6, 7, 8,9, 10]. These methods calculate the similarity between thelocal surface shape around the missing regions and that in thedata region and fill the missing regions by copying the mostsimilar surface patches successively. The methods can generate complex surfaces. However, a discontinuous surface iseasily generated on the seam in the completed model.
In this paper, to solve these problems, the energy function
which represents the non-plausibility of surface shape is defined using the similarity between the local surface shapes ofthe missing and data regions. By minimizing the energy forwhole the missing region, the model without discontinuous
surface shapes can be generated as an optimal solution.
2. SURFACE COMPLETION BY MINIMIZINGAN ENERGY FUNCTION
Fig. 1 illustrates the flow diagram of the proposed method.
First, a user manually selects missing regions to be repaired
in a model (a). Next, initial points and faces are generated
to the missing regions (b). Finally, by repeating addition anddeletion of points considering density of points (c) and updating positions of points by minimizing energy (d), whole surface is optimally completed. In the following sections, first,
the energy function is defined based on local shape similarity
SSD in Section 2.1. Next, Section 2.2 describes the procedurethat minimizes the energy function.
2.1. Energy function based on similarity of local shape
As illustrated in Fig. 2, first, a 3D model is divided into region¼
including the missing region selected by a user and thedata region  which is the rest of the object. The plausibility
in the missing region is defined by using surface shape inStartSurface
in data region(a) Specify target regionx f (p )Normalvector

M f (p )pf (p)(b) Generate initial points and faces

Matrix for surface alignment(c) Add and delete pointsg (p i )y f (p )Normal vector(d) Update positions of points by minimizing energy

M f (p )p g (p i ) z pNoz f (p )ypIs energy converged?
YesEndxppiFig. 1. Flow diagram of the proposed method.

p = M f ( p )p f (p)Points in missing region

Data region

ΩFig. 3. Alignment of point clouds and surface for similarity
measure of local shape.

ΦΩ′Missingregion

Area Af (p )Area Appf (p)Similar shape pairFig. 2. Missing and data regions in a 3D model.
the data region . Here, ¼ is the expanded area of region. ¼ is determined so that a spherical area with constantradius in the region ¼ includes at least one of the points in theregion . The energy function is defined as the weighed sumof SSD between the point set around the point p in the region¼and surface shape around the point fp in the region  asfollows: p fp
  p¾ª¼ p

(1)

ª p

p¾

¼

Here, the weight  p is set as  if p is inside of the region¼
because positions of points in this region are fixed: otherwise p is set as ½ ¾  ( is the distance from the boundaryof , and ½ and ¾ are constants) because positions of points
around the boundary have higher confidence than those in thecenter of the missing region. In Eq. (1), the weight is normalized because the weight of each point change due to themovement of points. fp in the data region  denotes thecentral point of the spherical area whose local shape is themost similar to that of point p. The point fp for minimizing is determined as follows:fp  p p ¼

¨p¼ ¾

(2)

In this paper, p fp that represents the similarity oflocal shape between the missing and data regions is definedas the sum of distances between the points in the area p
whose central point is p and the aligned surface around fp
as follows:  p  M gp  ¾ (3)p fp   f´pµp
pp 
¾p

where Mf´pµp denotes the matrix for surface alignment asshown in Fig. 3. M f´pµp gp  is a point on the aligned surface
in the data region which exists in the normal direction ofthe point p  ( p ).  p  is the number of points in thespherical area p .
Matrix for surface alignment M f´pµp is defined as follows:Mf´pµp 
xpypzp ppp ½
  x ´pµy ´pµz ´pµ (4)
 f´pµ f´pµ  f´pµwhere xp  yp  zp  and xf´pµ  yf´pµ  zf´pµ  are basis vectors for
p and fp), and  p  p  p  and  f´pµ  f´pµ  f´pµ  are 3D positions of p and fp in global coordinate system, respectively.
In this study, zp is determined as the unit normal vector of thepoint p. xp and yp is calculated as Eqs. (5) and (6).

     zp       zp yp  zp  xp xp (5)(6)

xf´pµ , yf´pµ and zf´pµ are also determined in the same way.
2.2. Energy minimization: Update of positions of points
After generating initial points and faces in missing regions,
positions of points are updated so as to minimize the energyfunction  defined in Eq. (1) using a framework of greedy
algorithm. In our definition of the energy  , the energy foreach point can be treated independently if similar shape pairs(p, fp) determined by Eq. (2) can be fixed. Thus, the following two processes are repeated until the energy converges:(i) update of similar shape pairs fixing positions of points, and(ii) parallel update of all the positions of points fixing similar
shape pairs.

Similar shape pairΦΩ′pif (p i )pg i (p)Area ApM f ( p s ) p s g s (p)M f (p i ) pi g i (p)Aligned surface inthe data region

Fig. 4. Relationship between points in energy calculation.
In the process (i) above, the update of the similar shapepair is performed by calculating fp fixing the positions of
all the points in the missing region with Eq. (2). Concretely,
 is calculated by Eq. (3) for all the points in the data region  and the point which gives a minimum SSD value is determined as the most similar point fp. In the process (ii), thepositions of all the points p in the missing region are updated
in parallel so as to minimize the energy defined by Eq. (1).
In the following, we describe the method for calculating thepositions of points p for fixed similar shape pairs. First, theenergy  is resolved into the element energy  p for eachpoint in the missing region. As shown in Fig. 4, the target
point to be updated is p, and the position of the point inside aspherical area p can be expressed as p  and is corresponded
to fp  by Eq. (2). In this case, the point corresponding tothe point p is g p. Now, the element energy  p can bedefined in terms of p, g  p and matrix Mf´p µp for surfacealignment as follows:  p g p ¾  p   p  Mf´p µp pp ¾p(7)

The relationship between the total energy  and the element
energy  p for each point can be written as follows: p   (8)ªp p i p Points ins
the missing region
tpt(p s , p )t(pi , p )p0Normal vector of p ：n pFig. 5. Conversion of parameters.
Here, by the assumption that the normal vector n p does notchange after updating the position of p, all the parameters in p except p are constants. In addition, the change of  pdose not affect the element energy of other points. Thus, byminimizing the element energy  p independently, wholeenergy  can be minimized. The parameter  p that minimizes p is calculated as follows:p ´p pµp  p

p p ¾p

¾(12)

p

From Eqs. (9), (10) and (12), the position of p that minimizes p is calculated as follows:p  p Mf´p µp g ppp  p
¾p

¾(13)

p

Actually, the value in Eq. (13) is an approximate solution because the normal vector n p changes due to the update of thepositions of p. However, a good solution can be obtained as
the energy converges because the change of the normal vector
becomes smaller as the energy converges.

p ¾ is the energy for the points in the region¼, and istreated as a constant because positions of points and all thesimilar shape pairs are fixed in this region in the process (ii).
Here, note that all the corresponding points M f´p µp g p(p  p ) exist in the normal direction of point p. Thus,
as shown in Fig. 5, points p and M f´p µp g p can be represented by using the normal vector n p of p, an arbitrary point
p¼ in the normal direction of p and parameters  p and ´p pµas follows:p  p¼  p np Mf´p µp g p  p¼  ´p pµ np (9)(10)

By substituting them into Eq. (7), the element energy is represented as follows: p  pp ¾p¾

 p  p  ´p pµ  (11)3. EXPERIMENTTo demonstrate the effectiveness of the proposed method, we
have applied the method to two surface models. They havedifferent characteristics as shown in Figs. 6(a) and 7(a). The
missing region of each model were given manually. In the experiment, as the initial points in the missing region, the gravity point of the boundary points of the missing region and the
median points between the gravity point and each boundary
point were given. Faces were generated so as to connect thesepoints.
Model A is a bowl model that has a smooth curved surface
and raised edges along the curve around the missing region.
Fig. 6(b) shows the model with initial points and faces. The
initial model is not natural due to rectilinear faces. By refining
this initial model with our method, as illustrated in Fig. 6(c),the missing region is completed with a smooth curved surface
similar to the surface in the data region. Raised edges are(a) Model with a hole(b) Initial model(a) Model with a hole(b) Initial model(c) Completed model(d) Completed solid and meshmodel from a different angle(c) Completed modelFig. 6. Completion for a bowl with a hole (Model A).
also reconstructed and totally the completed model looks very
natural.
Model B is Stanford Bunny that has a rugged surface anda dent edge between the body and the leg of the bunny aroundthe missing region. By refining the surface from the initialmodel shown in Fig. 7(b), a natural rugged surface is generated and a dent edge is connected in the missing region asshown in Fig. 7(c). The completed solid and mesh modelfrom a different angle is shown in Fig. 7(d). Mesh arrangement looks also natural on the rugged face and the dent edge.
4. CONCLUSION
In this paper, we have presented a novel method for surface
completion based on energy minimization. In the experiment
for two kinds of shape objects, our method have generated thecomplex and natural surface shapes in the missing regions. Infuture work, our method will be applied to 3D models forlarge environments such as outdoor scenes. A surface completion method for shape and color should also be investigated.

Acknowledgement
This research was partially supported by the Ministry of Education, Science, Sports and Culture, Grant-in-Aid for Scientific Research (A), 19200016, and Young Scientists (B),20700162.
5. REFERENCES[1] J. Verdera, V. Caselles, M. Bertalmio, and G. Sapiro, “Inpainting Surface Holes,” in Proc. Int, Conf. on Image Processing,
2003, vol. 2, pp. 903–906.

Fig. 7. Completion for Bunny with a hole (Model B).
[2] J. Wang and M.M. Oliveira, “A Hole-Filling Strategy for Reconstruction of Smooth Surfaces in Range Images,” in Proc.
SIBGRAPI, 2003, pp. 11–18.
[3] H. Xie, K.T. McDonnell, and H. Qin, “A Finite Element
Method for Surface Restoration with Smooth Boundary Conditions,” Computer Aided Geometric Design, vol. 21, No. 5,pp. 427–445, 2004.
[4] J. Davis, S.R. Marschner, M. Garr, and M. Levoy, “FillingHoles in Complex Surfaces Using Volumetric Diffusion,” inProc. Int. Symp. on 3D Data Processing, Visualization andTransmission, 2002, pp. 428–438.
[5] J. Podolak and S. Rusinkiewicz, “Atomic Volumes for Mesh
Completion,” in Proc. Eurographics Symp. on Geometry Processing, 2005, pp. 33–41.
[6] A. Sharf, M. Alexa, and D. Cohen-Or, “Context-based SurfaceCompletion,” in Proc. ACM SIGGRAPH, 2004, pp. 878–887.
[7] M. Pauly, “Example-Based 3D Scan Completion,” in Proc.
Eurographics Symp. on Geometry Processing, 2005, pp. 23–32.
[8] V. Kraevoy and A. Sheffer, “Template-Based Mesh Completion,” in Proc. Eurographics Symp. on Geometry Processing,
2005, pp. 13–22.
[9] T.P Breckon and R. B. Fisher, “Plausible 3D Colour Surface
Completion Using Non-parametric Techniques,” in Proc. Int.
Conf. on the Mathematics of Surfaces, 2005, pp. 102 – 120.
[10] S. Park, X. Guo, H. Shin, and H. Qin, “Surface Completion for
Shape and Appearance,” Int. J. of Computer Graphics, vol. 22,
No. 3, pp. 168 – 180, 2006.