Shape intrinsic fingerprints for free-form object matching

ABSTRACT

This paper presents matching and similarity evaluation methods between two NURBS surfaces, and their application to copyright protection of digital data representing solids or NURBS surfaces. Two methods are employed to match objects: the moment and the curvature methods. The moment method uses integral properties, i.e. the volume, the principal moments of inertia and directions, to find the rigid body transformation as well as the scaling factor. The curvature method is based on the Gaussian and the mean curvatures to establish correspondence between two objects. The matching algorithms are applied to problems of copyright protection. A suspect model is aligned to an original model through the matching methods so that similarity between two models can be assessed to determine if the suspect model contains part(s) of the original model, which may be stored in an independent repository. Three types of tests, the weak, intermediate and strong tests, are proposed for similarity assessment between two objects. The weak and intermediate tests are performed at node points obtained through shape intrinsic wireframing. The strong test relies on isolated umbilical points which can be used as fingerprints of an object for supporting an ownership claim to the original model. The three tests are organized in two decision algorithms such that they produce systematic and statistical measures for a similarity decision between two objects in a hierarchical manner. Based on the systematic and statistical evaluation of similarity, a decision can be reached whether the suspect model is an illegal copy of the original model.

REFERENCES

• 1: Oliver Benedens, Geometry-Based Watermarking of 3D Models, IEEE Computer Graphics and Applications, v.19 n.1, p.46-55, January 1999 [doi>10.1109/38.736468]
• 2: R. Bergevin, D. Laurendeau, and D. Poussart. Estimating the 3D rigid transformation between two range views of a complex object. In Proc. of 11th IAPR Intern. Conf. on Pattern Recognition. Conference A : Computer Vision and Applications, vol. 1, pp. 478--482, The Hague, The Netherlands, 1992. IEEE Computer Society Press.
• 3: M. V. Berry and J. H. Hannay. Umbilic points on Gaussian random surfaces. Journal of Physics A., 10(11):1809--1821, 1977.
• 4: Paul J. Besl , Neil D. McKay, A Method for Registration of 3-D Shapes, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.2, p.239-256, February 1992 [doi>10.1109/34.121791]
• 5: W. Blaschke and K. Leichtweiss. Elementare Differential Geometrie. Springer-Verlag, Berlin, 1973.
• 6: Richard J. Campbell , Patrick J. Flynn, A survey of free-form object representation and recognition techniques, Computer Vision and Image Understanding, v.81 n.2, p.166-210, February 1, 2001 [doi>10.1006/cviu.2000.0889]
• 7: C. S. Chua and R. Jarvis. 3D free-form surface registration and object recognition. International Journal of Computer Vision, 17(1):77--99, 1996.
• 8: T. Dokken. Finding intersections of B-spline represented geometries using recursive subdivision techniques. Computer Aided Geometric Design, 2(1-3):189--195, September 1985.
• 9: Z. Duric, N. F. Johnson, and S. Jajodia. Recovering watermarks from images. Technical Report: ISE-TR-99-04, the Center for Secure Information Syhstems, George Mason University, 1999.
• 10: C. Fornaro and A. Sanna. Public key watermarking for authentication of CSG models. Computer Aided Design, 32(12):727--735, 2000.
• 11: J. M. Galvez and M. Canton. Normalization and shape recognition of three-dimensional objects by 3D moments. Pattern Recognition, 26(5):667--681, 1993.
• 12: R. A. Jinkerson, S. L. Abrams, L. Bardis, C. Chryssostomidis, A. Clement, N. M. Patrikalakis, and F.-E. Wolter. Inspection and feature extraction of marine propellers. Journal of Ship Production, 9(2):88--106, May 1993.
• 13: N. F. Johnson, Z. Duric, and S. Jajodia. A role for digital watermarking in electronic commerce. ACM Computing Survey, To appear. See also http://www.jjtc.com/pub/.
• 14: S. Kanai, H. Date, and T. Kishinami. Digital watermarking for 3D polygons using multiresolution wavelet decomposition. In Proc. of the Sixth IFIP WG 5.2/GI Intern. Workshop on Geometric Modelling: Fundamentals and Applications, Tokyo, December, 1998, pp. 296--307, 1998.
• 15: K. H. Ko, T. Maekawa, and N. M. Patrikalakis. An algorithm for optimal free-form object matching. Computer Aided Design, 2003, in press.
• 16: K. H. Ko, T. Maekawa, N. M. Patrikalakis, H. Masuda, and F.-E. Wolter. Shape intrinsic watermarks for 3D solids. In Proceedings of the 2003 NSF Design, Service and Manufacturing Grantees and Research Conference, Birmingham, Alabama, January 2003.
• 17: T. Maekawa. Computation of shortest paths on free-form parametric surfaces. Journal of Mechanical Design, Trans. of the ASME, 118(4):499--508, 1996.
• 18: T. Maekawa and J. S. Chalfant. Computation of inflection lines and geodesics on developable surfaces. Mathematical Engineering in Industry, 7(2):251--267, 1998.
• 19: T. Maekawa and N. M. Patrikalakis. Interrogation of differential geometry properties for design and manufacture. The Visual Computer, 10(4):216--237, 1994.
• 20: T. Maekawa, N. M. Patrikalakis, F.-E. Wolter, and H. Masuda. Shape-intrinsic watermarks for 3-D solids. MIT Technology Disclosure Case 9505S, September 2001. Patent Attorney Docket No. 0050.2042-000. Application pending, January 7, 2002.
• 21: T. Maekawa , F.-E. Wolter , N. M. Patrikalakis, Umbilics and lines of curvature for shape interrogation, Computer Aided Geometric Design, v.13 n.2, p.133-161, March 1996 [doi>10.1016/0167-8396(95)00018-6]
• 22: R. Ohbuchi, H. Masuda, and M. Aono. Watermarking three-dimensional polygonal models through geometric and topological modifications. IEEE Journal on Selected Areas in Communications, 16(14):551--560, 1998.
• 23: Ryutarou Ohbuchi , Hiroshi Masuda , Masaki Aono, A Shape-Preserving Data Embedding Algorithm for NURBS Curves and Surfaces, Proceedings of the International Conference on Computer Graphics, p.180, June 07-11, 1999
• 24: N. M. Patrikalakis and L. Bardis. Localization of rational B-spline surfaces. Engineering with Computers, 7(4):237--252, 1991.
• 25: N.M. M. Patrikalakis , Nicholas M. Patrikalakis, Shape Interrogation for Computer Aided Design and Manufacturing, Springer-Verlag New York, Inc., Secaucus, NJ, 2002
• 26: Emil Praun , Hugues Hoppe , Adam Finkelstein, Robust mesh watermarking, Proceedings of the 26th annual conference on Computer graphics and interactive techniques, p.49-56, July 1999 [doi>10.1145/311535.311540]
• 27: W. H. Press, S. A. Teukolsky, W. T. Vetterling, and B. P. Flannery. Numerical Recipes in C. Cambridge University Press, 1988.
• 28: Richard J. Prokop , Anthony P. Reeves, A survey of moment-based techniques for unoccluded object representation and recognition, CVGIP: Graphical Models and Image Processing, v.54 n.5, p.438-460, Sept. 1992 [doi>10.1016/1049-9652(92)90027-U]
• 29: Hanan Samet , Robert E. Webber, Hierarchical Data Structures and Algorithms for Computer Graphics. Part I., IEEE Computer Graphics and Applications, v.8 n.3, p.48-68, May 1988 [doi>10.1109/38.513]
• 30: Evan C. Sherbrooke , Nicholas M. Patrikalakis, Computation of the solutions of nonlinear polynomial systems, Computer Aided Geometric Design, v.10 n.5, p.379-405, Oct. 1993 [doi>10.1016/0167-8396(93)90019-Y]
• 31: D. J. Struik. Lectures on Classical Differential Geometry. Addison-Wesley, Cambridge, MA, 1950.
• 32: T. M. Tucker and T. R. Kurfess. Newton methods for parametric surface registration. Part I. Theory. Computer-Aided Design, 35(1):107--114, 2003.
• 33: K. Yin, Z. Pan, J. Shi, and D. Zhang. Robust mesh watermarking based on multiresolution processing. Computers & Graphics, 25:409--420, 2001.
• 34: J. Zhou, E. C. Sherbrooke, and N. M. Patrikalakis. Computation of stationary points of distance functions. Engineering with Computers, 9(4):231--246, 1993.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.3 Clustering
          Subjects: Similarity measures

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

  K. Computing Milieux
  K.5 LEGAL ASPECTS OF COMPUTING
      K.5.1 Hardware/Software Protection
          Subjects: Copyrights

General Terms:
Algorithms

Keywords:
NURBS, fingerprints, localization, matching, partial matching, registration, similarity, umbilics