300 |
B. Bustos and I. Sipiran |
witnessed the achieved benefits of fields such as medicine, engineering, art, entertainment, and security, by the development of shape retrieval and recognition techniques. What is more, the interest in computer vision applications based on shape matching is becoming increasingly evident. It is easy to see the great potential that 3D information can provide and how it can be used to complement 2D images and video processing, in order to improve the effectiveness of high-level vision tasks. We believe that 3D information will be used commonly in the future and processes such as retrieval and recognition will be the basis for cutting-edge applications.
Likewise, it is beneficial to have a large catalog of techniques, because we can select an appropriate technique depending of the application context. Often we can combine techniques to improve the performance in general. In this chapter, we selected four techniques, which were explained in detail in Sect. 7.3. The depth buffer descriptor is an effective method based on extracting information of projections. Interestingly, this is one of the most effective methods yet simple, although it just supports a global similarity model. One way of supporting a certain level of partial similarity is by using local features extracted from shapes. Although the amount of information to be extracted increases, it is the cost to be paid for supporting nonglobal similarity models.
The other three presented techniques assume a non-global similarity model by extracting local descriptors which can be used to do the matching. The first of these is the spin image approach, which has proven to be effective in 3D shape recognition. Its versatility for describing shapes from different aspects has made it a standard technique for recognition tasks and new approaches often compare their results against results using spin images. Nevertheless, its dependency on uniform meshes and normals computation is restrictive. A small difference in calculating normals can produce different spin images, limiting its effectiveness.
Both salient spectral geometric features and heat kernel signature approaches make extensive use of a mathematical tool which has proven to be powerful for shape analysis, namely the Laplace-Beltrami operator. This operator has desirable properties which makes it a valuable tool for shape matching, in addition to the high effectiveness achieved in shape retrieval. Nevertheless, a weak point of this tool is its high computational cost which makes it an interesting challenge to be tackled in the future.
As can be noted, there is a lot of work to be done in proposing new approaches to improve the effectiveness and the efficiency of 3D shape matching, and studying new paradigms, some of which we mention in Sect. 7.4. We are convinced that the future of this research field is promising and the growth in scientific and technological productivity will remain thanks to the enormous efforts that the research communities in various fields are providing.
As expected, the increasing interest of research communities in shape retrieval and recognition has allowed a rapid advance, both in theory (new approaches) and appli-
7 3D Shape Matching for Retrieval and Recognition |
301 |
cations. Obviously, due to space limitations, all the material could not be addressed in this chapter, so this section is devoted to present additional material for interested readers.
A good starting point to introduce the reader further to the subject of shape retrieval and recognition are the surveys [26, 28, 55, 100]. Early evaluations of algorithms were also presented in the reports [15, 25, 27, 42]. For recent experimentation with state-of-the-art techniques, we recommend the reports of the SHREC contest [1]. For instance, recent SHREC tracks are: robust correspondence benchmark [22], robust large-scale shape retrieval benchmark [23], robust feature detection and description benchmark [17, 21], non-rigid 3D shape retrieval [73, 74], and generic 3D warehouse [105]. These reports represent a good reference for reviewing recent approaches and their performance evaluation.
More advanced and recent approaches have been presented, such as retrieval of 3D articulated objects [4], retrieval by similarity score fusion [5], discriminative spherical wavelet features [65], spherical parameterizations [66], compact hybrid shape descriptor [85], matching of point set surfaces [93], probability density-based shape descriptor [6], and spin images for shape retrieval [7, 8, 37], just to name a few. Another interesting approach is to refine the retrieval results using user information about how relevant the results were with a certain query. This approach is commonly called relevance feedback and it was properly applied by Leng and Qin [70], and Giorgi et al. [48] in shape retrieval tasks.
As stated in Sect. 7.4, partial matching is a challenging and still open problem. Nevertheless, some attempts have been proposed in order to tackle this problem. Among the main approaches are objects as metric spaces [20], priority-driven search [43], shape topics [76], reeb pattern unfolding [102], partial matching for real textured 3D objects [58], regularized partial matching of rigid shapes [19], and matching of 3D shape subparts [78]. Additionally, a good reference for non-rigid shape retrieval is due to Bronstein et al. [24].
The use of machine learning techniques has also been involved in shape retrieval and recognition. For instance, the boosting approach [63], supervised learning of similarity measures [64], unsupervised learning approach [80], learning of semantic categories [81], learning of 3D face models [101], face recognition by SVM classification [13], and the neurofuzzy approach [68]. These approaches need some background in pattern recognition and machine learning theory.
For readers interested in the Laplace-Beltrami operator and its applications in shape retrieval and recognition, we recommend the papers by Belkin et al. [11, 12], Bobenko [16], Chuang et al. [34], Ghaderpanah et al. [46], Levy [71], Rustamov [95], Wu et al. [109], and Xu [110, 111]. These papers have highly mathematical content, so it is recommended for a more advanced level of research.
On the other hand, in addition to the applications listed in Sec. 7.1, in the papers by Perakis et al. [89], Zhou et al. [116] and Giorgi et al. [47], we can find applications to face recognition, and in the work by Wessel et al. [107], the authors presented a benchmark for retrieval of architectural data.
302 |
B. Bustos and I. Sipiran |
1.Explain the difference between shape retrieval and shape recognition and give an example application of each.
2.Why is the matching of shapes that can deform (such as bending deformation) more difficult in general than matching of rigid shapes?
3.Why is the matching using partial views of an object (for example, when using single viewpoint 3D scans) more difficult in general than when the complete object surface is available in the query shape?
4.What properties of shape descriptor are desirable when addressing partial matching problems and non-rigid matching problems?
5.Describe the “bag of features” approach to shape retrieval.
1.In the interest point detection of the salient spectral geometric features, the authors recommended to set the number of eigenvectors in the process to 100. Implement the interest point detection method using a higher number of eigenvectors. Investigate the relation between the number of eigenvectors, the number of interest points detected and the magnitude of the scales of them.
2.Consider a neighborhood where four points are coplanar and three of them form an equilateral triangle. The forth point lies in the barycenter of the triangle. Let a be the length of a triangle’s side. Compare the triangle area with the following quantities:
•Voronoi region of p by using only Eq. (7.21).
•Voronoi region of p taking into account the obtuse triangles as described in Sec. 7.3.3.
Argue why it is necessary to be aware of obtuse triangles while calculating the Voronoi region area.
3.Prove that the Laplace-Beltrami operator is not invariant to scale changes. Additionally, suppose a uniform mesh which have edges with the same length denoted by a. Conjecture what happens with the operator when a tends to zero.
4.Explain why the quantity Kt (x, y) is a good choice for the spatial factor in shape Google technique?
5.The direction of the normal in the spin images defines a horizontal line in the middle of the spin image. A little variation in this normal modifies the image, rotating the pixels around the central point in the first column of the image. Propose a method to tackle with little variation of the normals.
6.The spin image in a point p depends of the direction of its normal. Let suppose an object A with normals computed in each vertex and an object B, equal to A, with opposite normals. Propose a variation to spin image computation in order to generate the same descriptor for corresponding points in A and B.
7 3D Shape Matching for Retrieval and Recognition |
303 |
7.Implement the spin images construction modifying the accumulation method. Instead of using bilinear interpolation, use a Gaussian weight centered in the corresponding pixel. Is this method more robust against noise and normal variations?
1.SHREC—Shape Retrieval Contest: http://www.aimatshape.net/event/SHREC
2.CGAL, Computational Geometry Algorithms Library: http://www.cgal.org
3.Adan, A., Adan, M.: A flexible similarity measure for 3D shapes recognition. IEEE Trans. Pattern Anal. Mach. Intell. 26(11), 1507–1520 (2004)
4.Agathos, A., Pratikakis, I., Papadakis, P., Perantonis, S.J., Azariadis, P.N., Sapidis, N.S.: Retrieval of 3D articulated objects using a graph-based representation. In: Spagnuolo, M., Pratikakis, I., Veltkamp, R.C., Theoharis, T. (eds.) Proc. Workshop on 3D Object Retr. (3DOR), pp. 29–36. Eurographics Association, Geneve (2009)
5.Akgül, C.B., Sankur, B., Yemez, Y., Schmitt, F.: Similarity score fusion by ranking risk minimization for 3D object retrieval. In: Perantonis, S.J., Sapidis, N., Spagnuolo, M., Thalmann, D. (eds.) Proc. Workshop on 3D Object Retr. (3DOR), pp. 41–48. Eurographics Association, Geneve (2008)
6.Akgul, C.B., Sankur, B., Yemez, Y., Schmitt, F.: 3D model retrieval using probability densitybased shape descriptors. IEEE Trans. Pattern Anal. Mach. Intell. 31(6), 1117–1133 (2009)
7.Assfalg, J., Bimbo, A.D., Pala, P.: Spin images for retrieval of 3D objects by local and global similarity. In: Int. Conf. Pattern Recognit., pp. 906–909 (2004)
8.Assfalg, J., D’Amico, G., Bimbo, A.D., Pala, P.: 3D content-based retrieval with spin images. In: Proc. IEEE Int. Conf. Multimedia and Expo, pp. 771–774. IEEE Press, New York (2004)
9.Atmosukarto, I., Wilamowska, K., Heike, C., Shapiro, L.G.: 3D object classification using salient point patterns with application to craniofacial research. Pattern Recognit. 43(4), 1502– 1517 (2010)
10.Baeza-Yates, R.A., Ribeiro-Neto, B.A.: Modern Information Retrieval. ACM Press/AddisonWesley, New York (1999)
11.Belkin, M., Sun, J., Wang, Y.: Discrete Laplace operator on meshed surfaces. In: Teillaud, M., Welzl, E. (eds.) Proc. Symposium on Comput. Geom, pp. 278–287. ACM, New York (2008)
12.Belkin, M., Sun, J., Wang, Y.: Constructing Laplace operator from point clouds in rd. In: Mathieu, C. (ed.) Proc. ACM-SIAM Symposium on Discrete Algorithms, pp. 1031–1040. SIAM, Philadelphia (2009)
13.Berretti, S., Bimbo, A.D., Pala, P., Silva-Mata, F.: Face recognition by SVMs classification and manifold learning of 2D and 3D radial geodesic distances. In: Perantonis, S.J., Sapidis, N., Spagnuolo, M., Thalmann, D. (eds.) Proc. Workshop on 3D Object Retr. (3DOR), pp. 57– 64. Eurographics Association, Geneve (2008)
14.Besl, P.J., McKay, N.D.: A method for registration of 3D shapes. IEEE Trans. Pattern Anal. Mach. Intell. 14(2), 239–256 (1992)
15.Bimbo, A.D., Pala, P.: Content-based retrieval of 3D models. ACM Trans. Multimed. Comput. Commun. Appl. 2(1), 20–43 (2006)
16.Bobenko, A.I.: Delaunay triangulations of polyhedral surfaces, a discrete Laplace-Beltrami operator and applications. In: Teillaud, M., Welzl, E. (eds.) Proc. Symposium on Comput. Geom., p. 38. ACM, New York (2008)
17.Boyer, E., Bronstein, A.M., Bronstein, M.M., Bustos, B., Darom, T., Horaud, R., Hotz, I., Keller, Y., Keustermans, J., Kovnatsky, A., Litman, R., Reininghaus, J., Sipiran, I., Smeets, D., Suetens, P., Vandermeulen, D., Zaharescu, A., Zobel, V.: SHREC 2011: robust feature de-
304 |
B. Bustos and I. Sipiran |
tection and description benchmark. In: Proc. Workshop on 3D Object Retrieval (3DOR’11). Eurographics Association, Geneve (2011). doi:10.2312/3DOR/3DOR11/071-078
18.Bronstein, A., Bronstein, M., Kimmel, R.: Numerical Geometry of Non-rigid Shapes. Springer, Berlin (2008)
19.Bronstein, A.M., Bronstein, M.M.: Regularized partial matching of rigid shapes. In: Forsyth, D.A., Torr, P.H.S., Zisserman, A. (eds.) Proc. Eur. Conf. Comput. Vis. (ECCV). Lecture Notes in Computer Science, vol. 5303, pp. 143–154. Springer, Berlin (2008)
20.Bronstein, A.M., Bronstein, M.M., Bruckstein, A.M., Kimmel, R.: Partial similarity of objects, or how to compare a centaur to a horse. Int. J. Comput. Vis. 84(2), 163–183 (2009)
21.Bronstein, A.M., Bronstein, M.M., Bustos, B., Castellani, U., Crisani, M., Falcidieno, B., Guibas, L.J., Kokkinos, I., Murino, V., Sipiran, I., Ovsjanikov, M., Patanè, G., Spagnuolo, M., Sun, J.: SHREC 2010: robust feature detection and description benchmark. In: Proc. Workshop on 3D Object Retrieval (3DOR’10). Eurographics Association, Geneve (2010)
22.Bronstein, A.M., Bronstein, M.M., Castellani, U., Dubrovina, A., Guibas, L.J., Horaud, R., Kimmel, R., Knossow, D., von Lavante, E., Mateus, D., Ovsjanikov, M., Sharma, A.: SHREC 2010: robust correspondence benchmark. In: Proc. Workshop on 3D Object Retrieval (3DOR’10). Eurographics Association, Geneve (2010)
23.Bronstein, A.M., Bronstein, M.M., Castellani, U., Falcidieno, B., Fusiello, A., Godil, A., Guibas, L., Kokkinos, I., Lian, Z., Ovsjanikov, M., Patanè, G., Spagnuolo, M., Toldo, R.: SHREC 2010: robust large-scale shape retrieval benchmark. In: Proc. Workshop on 3D Object Retrieval (3DOR’10). Eurographics Association, Geneve (2010)
24.Bronstein, A.M., Bronstein, M.M., Kimmel, R.: Topology-invariant similarity of nonrigid shapes. Int. J. Comput. Vis. 81(3), 281–301 (2009)
25.Bustos, B., Keim, D., Saupe, D., Schreck, T.: Content-based 3D object retrieval. IEEE Comput. Graph. Appl. 27(4), 22–27 (2007)
26.Bustos, B., Keim, D.A., Saupe, D., Schreck, T., Vranic, D.V.: Feature-based similarity search in 3D object databases. ACM Comput. Surv. 37(4), 345–387 (2005)
27.Bustos, B., Keim, D.A., Saupe, D., Schreck, T., Vranic, D.V.: An experimental effectiveness comparison of methods for 3D similarity search. Int. J. Digit. Libr. 6(1), 39–54 (2006)
28.Campbell, R.J., Flynn, P.J.: A survey of free-form object representation and recognition techniques. Comput. Vis. Image Underst. 81(2), 166–210 (2001)
29.Chaouch, M., Verroust-Blondet, A.: 3D model retrieval based on depth line descriptor. In: Proc. IEEE Int. Conf. Multimedia and Expo, pp. 599–602. IEEE Press, New York (2007)
30.Chen, D.Y., Tian, X.P., Shen, Y.T., Ouhyoung, M.: On visual similarity based 3D model retrieval. Comput. Graph. Forum 22(3), 223–232 (2003)
31.Chen, H., Bhanu, B.: Human ear recognition in 3D. IEEE Trans. Pattern Anal. Mach. Intell. 29(4), 718–737 (2007)
32.Chen, H., Bhanu, B.: Efficient recognition of highly similar 3D objects in range images. IEEE Trans. Pattern Anal. Mach. Intell. 31(1), 172–179 (2009)
33.Chua, C.S., Jarvis, R.: Point signatures: a new representation for 3D object recognition. Int. J. Comput. Vis. 25(1), 63–85 (1997)
34.Chuang, M., Luo, L., Brown, B.J., Rusinkiewicz, S., Kazhdan, M.M.: Estimating the Laplace-Beltrami operator by restricting 3D functions. Comput. Graph. Forum 28(5), 1475– 1484 (2009)
35.Cyr, C.M., Kimia, B.B.: A similarity-based aspect-graph approach to 3D object recognition. Int. J. Comput. Vis. 57(1), 5–22 (2004)
36.Daras, P., Zarpalas, D., Tzovaras, D., Strintzis, M.G.: Shape matching using the 3D radon transform. In: Proc. Int. Symposium on 3D Data Proces., Vis. and Transm., pp. 953–960. IEEE Computer Society, Los Alamitos (2004)
37.de Alarcón, P.A., Pascual-Montano, A.D., Carazo, J.M.: Spin images and neural networks for efficient content-based retrieval in 3D object databases. In: Lew, M.S., Sebe, N., Eakins, J.P. (eds.) Proc. ACM Int. Conf. on Image and Video Retrieval (CIVR). Lecture Notes in Computer Science, vol. 2383, pp. 225–234. Springer, Berlin (2002)