FINAL REPORT FOR AWARD # 0010127 Takashi Maekawa ; MIT Shape Intrinsic Watermarks for 3D Solids Participant Individuals: CoPrincipal Investigator(s) : Nicholas M Patrikalakis Graduate student(s) : Kwanghee Ko Undergraduate student(s) : Emily L Canfield Graduate student(s) : Yoshiyuki Furukawa Undergraduate student(s) : Megumi Ando Partner Organizations: University of Tokyo: Personnel Exchanges Dr. H. Masuda is an Associate Investigator in this project. As he is a foreign collaborator, his cost is not charged to the NSF budget. Dr. Masuda's doctoral graduate student Mr. Y. Furukawa stayed at MIT for two months using their own funding. He investigated discrete differential geometry issues for watermarking polyhedral surfaces using our facilities. University of Hannover: Personnel Exchanges Dr. F. -E. Wolter of University of Hannover is an Associate Investigator (AI) in this project. As he is a foreign collaborator, his cost is not charged to the NSF budget. Dr. Wolter visited MIT for about a month using his own funding. He has participated in patent preparation and in writing progress reports and papers from the project. Activities and findings: Research and Education Activities: Recently copyright issues for digital contents are becoming a serious problem. Especially when the copyrighted digital contents are exposed to the internet, they are an easy target for malicious parties to produce pirate digital contents for unauthorized sales. Digital watermarking, defined as a process to embed data called watermark into a digital content to protect the copyright of the owners, is becoming an active research topic. There exist studies on digital watermarking techniques for 3D polygonal models, prompted by the increasing popularity of virtual reality modeling language (VRML) and standardization of MPEG-4. Unfortunately, these techniques cannot be applied directly to computer aided design (CAD) based objects, which are usually represented by Non-Uniform Rational B-Spline (NURBS) surfaces. Moreover existing watermarking techniques, such as embedding data by slightly changing the control points, putting some pattern in the mesh, are vulnerable to coordinate transformation, random noise and malicious action of the user. The objective of this project is to develop an intrinsic watermark technique for solids bounded by NURBS surfaces. The key idea is to extract intrinsic properties of solids, which are not affected by coordinate transformations, random noise and malicious action of the user. This watermark can be destroyed only if the digital model describing the shape is changed so much that the newly represented object cannot any longer be considered approximately identical to the original solid in the database. In order to accomplish the above objectives, the following research and education activities have been undertaken. First year: 1. We conducted an extensive literature review on object matching as well as on digital watermarking. 2. We developed tools to support scaling and localization of solid models. For a smooth surface we used commercial software to handle scaling and localization, while for triangular faceted surfaces we have implemented an algorithm based on a paper by Cattani and Paoluzzi [1]. 3. We constructed curvature line network on a NURBS surface. Lines of curvature provide a method to describe the variation of principal curvatures across a surface. They are intrinsic to the surface and do not depend on coordinate transformations, and parametrization of the surface. 4. We started a preliminary investigation on estimating accurate normal vectors at the vertices of a polyhedral mesh. This provides the basis for studying the discrete differential geometry of polyhedral surfaces. Also we started a preliminary investigation for evaluating the principal directions at the vertices. 1] C. Cattani and A. Paoluzzi ``Boundary integration over linear polyhedra'', Computer-Aided Design, 22 (2) pages 130-135, March 1990. Second year: 1. We performed research on umbilical points and developed a new algorithm which is efficient for extracting lines or regions of umbilical points such as planes or spheres. 2. We developed an algorithm to create a surface intrinsic wireframe of a NURBS surface using lines of curvature and geodesic curves. It provides various functions to allow a user to construct the intrinsic wireframe interactively. 3. We developed new surface matching methods which cover partial surface matching with scaling effects and no initial information on correspondence. 4. We developed decision algorithms for similarity using three hierarchical tests that include the weak, intermediate and strong tests. Third year: 1. We performed numerical experiments with a variety of models to demonstrate the performance of the proposed algorithms. 2. We continued research on robust computation of intrinsic properties on faceted surfaces. 3. We compiled overall project results for documentation and presentation. Findings: Below we summarize the conclusions that have emerged from our activities. The numeration corresponds to the one in activities. First year: 1. The literature survey has been compiled into a doctoral thesis proposal by K. Ko, currently being completed. 2. The attached Figure 1 shows two surfaces rendered by wireframes with their net of control points. A smaller surface on the right is constructed by approximating the large surface on the center, and then scaled, rotated and translated. Now we will show how the copied surface is matched with the original surface. We first evaluate the global or integral properties of surfaces including centroids and moments of inertia. Once we know the centroids and principal directions of both surfaces, we translate and rotate the copied surface so that it matches the centroid and orientation of the original surface (see attached Figure 2 (a) and (b)). Finally we uniformly scale the copied surface, using the 1/2 power of the ratios of the areas of the two surfaces (see attached Figure 2 (c)). 3. The attached Figure 3 (a) shows the orthogonal network of the lines of curvature of the original surface, while on (b), principal directions of the copied surface at orthogonally projected grid points of the network of lines of curvature of the original surface are shown. We can observe the presence of three star-type umbilics on the original as well as on the copied surface. Also the similarity of the principal directions on both surfaces clearly indicates that (b) is a copy of (a). 4. Topic is still under investigation and we do not have concrete results. Second year: 1. Complete information on umbilical points is essential for surface intrinsic wireframing and matching using umbilical points. Therefore, robust and efficient detection of umbilical points is an important part in the project. The Interval Projected Polyhedron (IPP) algorithm can calculate isolated umbilical points efficiently, while it is not appropriate for extracting lines and regions of umbilical points, which can be efficiently handled by a new algorithm using the concept of adaptive quadtree decomposition. A governing equation for umbilical points is formulated in Bernstein form. The parametric domain of the equation is subdivided into four subdomains using the De Casteljau algorithm. Each subregion is tested such that the subquadrants which do not contain umbilical points are eliminated using convex hull properties. The attached Figure 4-a is a schematic diagram of the adaptive quadtree decomposition. The marked squares indicate the domains which may contain umbilical points. Figure 4-b shows an example of isolated umbilical points on the uv domains and the surface. The surface is a bicubic Bezier surface which has five isolated umbilical points. An example of a line of umbilical points is presented in Figure 4-c. The input surface is a developable cubic-linear surface and has an inflection line at u=0.5754 as shown in Figure 4-c. An example of extraction of a planar region is shown in Figure 4-d. It is a bi-cubic B-spline surface which is partially planar. Due to the local properties of the B-spline, the effects of change of the control points are limited to specific subregions defined by knot values. 2. The first year's work on construction of the intrinsic wireframe is extended so that a new algorithm has been developed to enable a user to create an intrinsic wireframe of a NURBS surface interactively. Since we found out that lines of curvature in the neighborhood of umbilical points as well as boundary lines cannot be handled in an appropriate manner, we adopted geodesic lines for those areas to complete intrinsic wireframing. Figure 5-a shows an example of intrinsic wireframing. This example has 413 nodes, 356 quadrilateral and 14 triangular elements. A computer program was developed to integrate all algorithms to generate wireframe of a NURBS surface. It consists of two windows. One serves to visualize a surface and wireframe in 3D space, and the other, which is denoted as the control window, serves to provide an interface for a user to interact with the wireframe model when user input is needed. The visualization window is created based on OpenGL. It provides functions for rotation and scaling for better visualization. The control window has a parametric domain. It shows the current status of the parametric domain during wireframing. Several options are provided for interactive operation. The language used in the development is C++. A set of window managing libraries, Qt-2.3.1, are used for graphical user interface. Figures 5-b and 5-c show intermediate results of our algorithms. 3. After reviewing the literature on object matching extensively, we concluded that the partial matching problem with scaling effects and no initial correspondence information has not been investigated so far. To solve this problem, as a first step, we developed two approaches to establish correspondences between two objects with no initial correspondence information when no scaling effect is involved. One method, called the KH method, uses surface intrinsic properties, i.e. the Gaussian and mean curvatures. It is designed to solve a global/partial matching problem with no prior information on correspondence or transformation. Unlike the ICP algorithm whose convergence to the global optimum heavily depends on the starting position for the iteration, the KH method does not experience such problems. The other method is to use qualitative properties of umbilical points to find correspondence information between two objects. This method can be used only when isolated generic umbilical points exist on both objects. The scope of matching is extended to include uniform scaling effects. Two approaches are proposed for the solution to global/partial matching problems with scaling effects. The first method uses the qualitative and quantitative properties of isolated generic umbilical points, which behave as fingerprints of a surface. Correspondence between two objects is established by matching the qualitative properties of umbilical points, and a scaling factor can be recovered from the normal curvature values at the corresponding umbilical points. The second method uses a one-dimensional optimization scheme, or the golden section search based on the KH method, which only requires an initial interval for the scaling factor so that the solution process becomes simplified compared to iterative optimization algorithms such as the ICP which needs a good initial value of the scaling factor as well as the rigid body transformation. The golden section search yields a scaling factor, a rotation matrix and a translation vector which minimize a squared distance objective function. The proposed methods can deal with two cases: 1) the point vs. NURBS surface case and 2) the NURBS surface vs. NURBS surface case. An example of partial matching without scaling effects is tested via the ICP algorithm by Besl and McKay (1992) for comparison purposes. Since no good initial position or transformation is available, the current position in Figure 6-a is used as a starting state. The proposed method produces a good result as shown in Figure 6-b. The ICP algorithm converges to a local minimum which is shown in Figure 6-c. Obviously, the figure shows that the ICP algorithm fails in this situation, which means that the success of the ICP algorithm heavily depends on the starting position or initial transformation. No such problems are encountered in the proposed method, which does not require good initial estimates. Figure 6-d shows a global matching example without scaling effects for two bicubic B-spline surface patches. Three reference points are selected, which are marked with circles in the figure. Figure 6-d-(c) shows the matched results of the two surfaces. Figure 6-e shows partial matching of two NURBS surfaces without scaling effects. A partial matching example with scaling effects and no prior information on correspondence is provided in Figure 6-f. 4. Two similarity decision algorithms, Algorithm 1 (Figure 7-e) and Algorithm 2 (Figure 7-f) are proposed which include three hierarchical tests (weak test (distances), intermediate test (principal curvatures and directions), and strong test (umbilical points)) for checking two geometric objects for similarity. Each test is performed at the points which are selected independently of representation methods and parametrization. The reference points for the tests are obtained from the node points of shape intrinsic wireframe of a surface using lines of curvature and geodesic curves. Partial matching of a surface can also be assessed (providing a method for solving the partial surface overlap problem). The matching and similarity decision algorithms are applied to protection of intellectual property by assessing the similarity between an original object and a suspect one. Using the proposed matching methods, one can align them and determine if the suspect model contains part(s) of the original model, which may be stored in an independent repository. Based on systematic and statistical evaluation of the similarity, a decision can be made whether the suspect model is an illegal copy of the original model. The two proposed similarity decision algorithms are demonstrated with the bottle example used for the moment method. After aligning the two solids A and B shown in Figure 7-d, we are ready to assess the similarity between them. Here, part of the bounding surfaces are used for similarity checking. The surfaces are represented as bicubic B-splines and one surface has 64 (8 X 8) and the other 144 (12 X 12) control points. Both surfaces are enclosed in a rectangular box of 25.0mm X 23.48mm X 11.0mm. The 429 node points are used from the wireframe given in Figure 5-a. The quantities for each test are calculated and summarized in Table 1. The epsilon-offset criterion measures the Euclidean distances between two surfaces at the reference points. The criteria for the maximum and minimum principal curvatures are the differences of the maximum and minimum principal curvature values between two surfaces at the reference points, and the principal direction criterion reflects the differences of the principal direction angles between two surfaces at the reference points. All umbilical points on the two surfaces are located as shown in Figure 7-a. Table 1 -------------------------------------------------------------------- Criteria | Max | Average | STD -------------------------------------------------------------------- epsilon-offset (mm) | 0.03456 | 0.00814 | 0.00665 Maximum principal curvature (mm^{-1}) | 0.07872 | 0.01572 | 0.01530 Minimum principal curvature (mm^{-1}) | 0.10577 | 0.01411 | 0.02165 Principal direction (rad) | 0.70052 | 0.05657 | 0.11385 -------------------------------------------------------------------- The Euclidean distances of the corresponding umbilical points are summarized in Table 2. Table 2 ------------------------------------------------------------ | 1 | 2 | 3 ------------------------------------------------------------ Distances (mm) | 0.08099 | 0.02954 | 0.08115 ------------------------------------------------------------ Statistical information given in Table 1 is obtained using Algorithm 2. Unlike Algorithm 1 which uses a maximum value for each test, Algorithm 2 considers not only maximum values but also averages and standard deviations. Moreover, at each test, under a given tolerance, we can examine the distribution of epsilon over the surface so that we can quantify the similarity between two surfaces and we can see which part is different. Suppose that we have 0.01 as a tolerance for the weak test and we subdivide the uv region into 400 square sub-regions (each box size of 0.05 X 0.05). The total number of sub-regions which contain footpoints Pi satisfying epsilon_i > 0.01 is 31. Therefore, we can conclude that two surfaces are similar at 92.25% under the weak test with tolerance 0.01 and sub-region of size 0.05 X 0.05. This can be visualized as in Figure 7-b-(A). Here, the boxes indicate the regions which have at least one point with deviation larger than the tolerance 0.01. The intermediate test using the maximum principal curvature is visualized in Figure 7-b-(B). Under the intermediate test for the maximum principal curvature with a tolerance 0.03, the similarity between two surfaces is calculated to be at 91.25%. The results for the intermediate tests of the minimum principal curvature and the principal direction are shown in Figure 7-c-(A) and 7-c-(B). The similarity values for each case are 96.0% with a tolerance 0.03 and 95.50% with a tolerance 0.06. The strong test can also be performed based on the umbilical points for both surfaces as shown in Figure 7-a. Three star type umbilical points are identified for each surface, and the Euclidean distances between the corresponding umbilical points are calculated as in Table 2. The types of the corresponding umbilical points match, and the position differences are small compared to the size of the object. Therefore, we may conclude that the solid B is derived from the solid A under the strong test. Third year: 1. One of the results of the second year, the matching method based on umbilical points, was theoretically justified for its use in matching problems. This method employed ensembles of isolated umbilical points that have stable patterns useful to recognize that a surface patch had been obtained by a small perturbation of another surface patch having an equivalent collection of finitely many (isolated) stable umbilical points. Our proposal involving use of the "pattern of stable umbilical points" in order to support the recognition of surface patches may raise some questions concerning its usefulness. The reason for those doubts is that if we consider surfaces that are infinitely often continuously differentiable then the structure of their respective sets of umbilical points may be quite complicated. Within the family of general infinitely often differentiable surfaces it is possible to construct very small perturbations that will change surfaces having only finitely many (stable) umbilics into new surfaces having infinitely many isolated stable umbilical points that may occur in quite complex geometric arrangements. (Here a simple construction of surface with infinitely many isolated stable umbilics may e.g. be achieved by attaching a sequence of infinitely many very small shrinking bumps to a cylindrical surface patch.) The latter construction and complex arrangements of umbilical points are possible due to the fact that the differentiability class C-infinity still allows e.g. all kinds of infinitely many arbitrarily small local perhaps oscillatory surface deformations. However, if we restrict our attention to Bézier or B-spline surface patches of limited degree then the number of isolated umbilical points is limited as well. Here the maximal number of isolated umbilical points existing on the Bézier surface patch can be estimated from above using the degree information of the Bézier surface patch or the information on the number of control points. A similar estimation is possible for B-spline surface patches as well. Hence working with Bézier surface patches yields a finiteness condition for the number of umbilics. In case we perturb e.g. the Bézier surface patch within the family of Bézier surface patches of the same degree, then we shall obtain new patches with a finite maximal number of isolated umbilics as well. The latter maximal number has the same bound as the one being valid for the unperturbed Bézier surface patch. Such a surface perturbation can be realized by deforming the original surface patch via perturbing all control points of the original Bézier surface patch. Such perturbations are very specialized and restrictive in comparison to the general case where we may consider general surfaces that have regular parametrizations being infinitely often differentiable. However, from a practical point of view the restriction to the family of Bézier surface patches even with degree restrictions is justified in an engineering context. Hence, here it is practically correct to consider only the restricted metamorphosis -possibilities- of an ensemble of finitely many stable umbilics located on the original Bézier surface patch. This definitely excludes inconvenient pathologies that would otherwise be possible. Moreover the preceding considerations should help to illuminate a posteriori why the diagnostic tool employing the pattern of (finitely many) isolated stable umbilics is relevant in supporting the diagnosis that a Bézier surface patch is obtained via a fairly small deformation (within the Bézier family) from the given original Bézier surface patch. 2. The umbilical point method discussed in the second year report was examined in detail. When isolated generic umbilical points exist on the surfaces of two objects, they can be used to establish correspondence between the objects. Conceptually, a matching algorithm using generic isolated umbilical points is straightforward. The basic idea is to find a pair of umbilical points which have the same type. If we have more than three matching pairs of umbilical points, then we can easily find a rigid body transformation in the least squares sense. When there are less than two pairs, we match the normal vectors and align the radiating patterns of lines of curvature at the corresponding umbilical points. In most cases, the number of generic isolated umbilical points is small. Therefore, a brute force search scheme to find matching pairs of umbilical points can be employed without loss of performance. This method is demonstrated with an example as follows: Suppose we have a set of data points rA and a surface rB as shown in Figures 8-a and 8-b. The surface rB shown in Figure 8-a is a bicubic B-spline surface patch with 64 (8 x 8) control points enclosed in a box of 25mm x 23.48mm x 11mm. It has three star type umbilical points as shown in Figure 8-a. The point set rA shown in Figure 10 is approximated with a bicubic B-spline surface patch of 256 (16 x 16) control points. It has one umbilical point of star type as shown in Figure 8-b. Angle distributions at the umbilical points are computed and it is found that the star type umbilical point on rA matches the center umbilical point on rB. Then, surface rA is translated and rotated by using the positions of the corresponding umbilical points and the normal vectors at the umbilical points to match surface rB as shown in Figure 8-c. 3. The similarity decision algorithms presented in the second year report are further tested with more examples. -------------- New addition ------------ Final year: 1. Mathematical theory for umbilical points is further investigated using a complex plane transformation. The local surface near an umbilical point can be represented as a height function or the Monge form with respect to a local coordinate system as follows: r = (x,y,h(x,y)) The function h(x,y) is Taylor expanded at the origin of the local coordinate system, which is given by h(x,y) = -k/2 (x^2 + y^2) + 1/6 (ax^3 + 3bx^2y + 3cxy^2 + dy^3) + O(4), ------ (1) where k is the normal curvature at the umbilical point. From equation (1), we observe that the local surface structure is determined by the coefficients of the cubic terms, which reflect the properties of each umbilical point. In order to further analyze how the coefficients (a,b,c,d) behave depending on umbilical points, we have to transform the cubic terms of (1) by using a complex number xi = x + iy. Let us set C(x,y) = ax^3 + 3bx^2y + 3cxy^2 + dy^3. Then using xi, we rewrite C(x,y) as follows: _ __ __ _ __ C'(xi) = a' xi^3 + 3 b' xi^2 xi + 3 b' xi xi^2 + a' xi^3 where a'= [(a-3c)+i(d-3b)]/8 b'= [(a+c) +i(b+d) ]/8. Here a bar above a character indicates the complex conjugate. We can make the coefficient of xi^3 be equal to 1 without compromising the local structure of the surface near the umbilical point by rotating the coordinate system around the normal vector. After normalizing the coefficient of xi^3, the expression C'(xi) becomes _ ___ ___ ___ C"(eta) = eta^3 + 3w eta^2 eta + 3 w eta eta^2 + eta^3, where _ w = b' a'^{-1/3} a'^{-2/3}. This series of transformation is equivalent to the parametrization of the cubic polynomial C(x,y) with respect to a single complex variable w. Depending on the surface structure, two characteristic lines are obtained which subdivide the complex domain w into subregions as shown in Figure 9. Lemon type umbilical points are mapped outside the deltoid indicated by "L", Monstar type ones inside the deltoid and outside the circle denoted by "MS", and Star type ones inside the circle denoted by "S". Umbilical points which are mapped onto each dividing line are of non-generic type and they require higher derivative terms for further analysis. This mapping is independent of scaling of a surface. Therefore, we can establish correspondence between two umbilical points irrespective of scaling values. The example shown in Figures 8-a through 8-c illustrates this mapping. The surface rB contains three umbilical points which are mapped into the circle in the complex domain as three points as shown in Figure 10. This indicates that those umbilical points are of star type. There is one umbilical point on the approximated surface rA (Figure 8-b), which is mapped into a point inside the circle as shown in Figure 10. It turns out that the umbilical point from rA matches the center umbilical point of rB since both are mapped onto the same point in the complex domain as shown in Tables 3 and 4. Table 3 Umbilics and w values for rB ----------------------------------------- No. | (u,v) | w = (x,y) ----------------------------------------- 1 | (0.743, 0.028) | (0.094, -0.069) 2 | (0.861, 0.5) | (0.151, -0.261) 3 | (0.748, 0.972) | (0.094, 0.069) ----------------------------------------- Table 4 An umbilic and w value for rA ----------------------------------------- No. | (u,v) | w = (x,y) ----------------------------------------- 1 | (0.207, 0.685) | (0.151, -0.261) ----------------------------------------- So we can establish the correspondence between two umbilical points, estimate a scaling factor by using the ratio of normal curvatures and compute the rigid body transformation which aligns the two surfaces as closely as possible. 2. After analyzing the KH matching algorithm, we found out that solving a system of bivariate polynomial equations, which is the core part of the KH method, is causing the major bottleneck of the whole process. We use the IPP algorithm to find roots of the system of equations and it has O(m^4) complexity per step in the KH method, where m is the maximum degree of the variables in the equations. For a rational surface patch, the degrees are exceptionally high (e.g. 44 for a cubic rational Bezier patch) such that the computation time could be unacceptable for practical purposes. To lessen the computational burden of the IPP algorithm, we can use low-degree approximation of the Gaussian and mean curvature functions. Using approximation techniques such as the multilevel B-spline approximation by Lee et al. [1] or the low degree approximation of high degree B-spline surfaces by Tuohy and Bardis [2], we can approximate high degree Gaussian and mean curvature functions with low degree bicubic B-spline functions. Then we use these low degree curvature functions (m = 3) as input to the IPP algorithm. [1] S. Lee, G. Wolberg, and Y. S. Shin. Scattered data interpolation with multilevel B-splines. IEEE Transactions on Visualization and Computer Graphics, 3(3):228-244, 1997 [2] S. T. Tuohy and L. Bardis. Low degree approximation of high degree B-spline surfaces. Engineering with Computers, 9(4):198-209, 1993. Training and Development: Undergraduate student Emily L. Canfield (who is a Mathematics major) has learned the basics of representation of curves and surfaces as well as differential geometry of curves and surfaces. Also she has been exposed to programming in the C language and use of MATLAB, VRML viewer, and latex. Ms. Canfield was paid by the MIT UROP Program. Undergraduate student Megumi Ando (who is a Mathematics major) has learned the basics of differential geometry and optimization techniques. She has improved her skills in the C language and learned the use of MATLAB and latex. Ms. Ando was paid by the MIT UROP Program. Graduate student Kwanghee Ko has strengthened his knowledge on differential geometry of curves and surfaces, numerical methods, data structures and C++ programming skills. Also he has developed skills of presentation as well as writing. He gave a presentation of the results from the project and his doctoral thesis at an international conference "ACM Symposium on Solid Modeling and Applications, 2003". Graduate student Yoshiyuki Furukawa has strengthened his knowledge on discrete differential geometry of curves and surfaces, and learned more advanced numerical methods. Mr. Furukawa's expenses were paid by University of Tokyo. Journal Publications: K. H. Ko, T. Maekawa, N. M. Patrikalakis, H. Masuda, and F.-E. Wolter. "Shape Intrinsic Properties for Free-Form Object Matching", ASME Transactions, Journal of Computing and Information Science in Engineering. Vol. 3, No. 4, pp. 325-333, December 2003. K. H. Ko, T. Maekawa and N. M. Patrikalakis, "An Algorithm for Optimal Free-Form Object Matching", Computer-Aided Design, Vol. 35, No. 10, pp. 913-923, September 2003. K. H. Ko, T. Maekawa and N. M. Patrikalakis, "Algorithms for Optimal Partial Matching of Free-Form Objects with Scaling Effects" , Graphical Models, In press. 2004. Book(s) of other one-time publications(s): K. H. Ko, "Algorithms for Three-Dimensional Free-Form Object Matching", bibl. PhD Thesis, (2003). K. H. Ko, T. Maekawa, N. M. Patrikalakis, H. Masuda and F.-E. Wolter, "Shape Intrinsic Fingerprints for Free-Form Object Matching", Proceedings of the Eighth ACM Symposium on Solid Modeling and Applications. G. Elber and V. Shapiro, editors. pp. 196-207. Seattle, Washington, June 2003. NY: ACM, 2003. Other Specific Products: Other inventions We filed a patent ``Shape-Intrinsic Watermarks for 3-D Solids'' by T. Maekawa, N. M. Patrikalakis, F.-E. Wolter and H. Masuda. MIT Technology Disclosure Case 9505S, September 2001. Patent Attorney Docket No. 0050.2042-000, January 7, 2002. Preliminary positive response and comments received in April 2004 with rebuttal submitted in May 2004. Application pending. Contributions: Contributions within Discipline: The problem we are attacking could also be rephrased as follows: We want to develop methods for deciding if two complex solid object representations define, up to a certain accuracy, the same object. We want to be able to test this regardless of the particular representation of A and B. Hence we are looking for efficient computational methods that check approximate shape equality for solids regardless of their given representation, scaling and positioning in space. If the creation of the solid's shape is the value that must be protected, we certainly must be able to decide if a given solid shape could be called rightly a copy of another solid shape. In some meta-sense we are looking for an intrinsic watermark inherently connected with the value of the solid digital model, i.e. this intrinsic watermark is its approximate shape identity! This watermark can be destroyed only if the digital model describing the shape is changed so much that the newly represented object cannot any longer be considered approximately identical to the object A in the database. New matching methods were developed which allow us to compare not only solids but also NURBS surfaces. Moreover they can deal with a partial matching problem with scaling effects and no initial correspondence information, which is not solved by the various alternate methods published so far. They can be used for ownership protection of free-form NURBS surfaces as well as solid objects. They also can be used to develop a full automatic surface inspection system, which requires accurate matching between two objects. Successful development of our project ``Shape Intrinsic Watermarks for 3D Solids'' will have a broad impact on our modern rapidly changing information society. The proposed method will be useful to help protect ownership of expensive digital data models of an original solid model when it is officially registered with an acknowledged agency. Hence, with the development of those methods proposed in this proposal, one would be in the position to settle legal disputes in some cases that appear to be beyond the scope of currently available methods and systems. Contributions to Other Disciplines: Another possible commercial application is the use in 3D digital catalogs. Recently techniques for digital solid shape identification are in great demand. For example, in electronic commerce through the internet, a 3D digital catalog could allow customers to search for merchandise similar to a specific design. Our novel technique can be applied in this context as well. The new matching methods developed in this project can be also applied to medical imaging useful for clinical diagnosis, therapy planning, therapy evaluation, etc, and molecular biology where a geometric fit between parts of the boundaries of two molecules is sought. Contributions to Education and Human Resources: We had two female undergraduate students (Mathematics majors) involved in this project, who have learned the basics of differential geometry and improved their programming skills in C, and were exposed to engineering research activities. Some aspects of this research are reflected in the teaching of the interdeparmental course 'Computation Geometry' (13.472J/2.158J/1.128J/16.940J a joint class in Ocean, Mechanical, Civil and Aeronautics departments at MIT) including advanced differential geometry, matching and inspection. Materials from the results of this project were used for the course offered Spring 2003 and are also expected to be included in the same course in Spring 2005. Contributions to Resources for Science and Technology: We have created a project web page through which we plan to distribute our results and software. http://deslab.mit.edu/DesignLab/Watermarking/ Contributions Beyond Science and Engineering: An effort has been made to disseminate our results to other researchers and commercial users, such as developers of CAD/CAM systems. Example companies with which we have established contacts include Solidworks Inc. and the Boeing Aircraft Company. We plan to disseminate our work to commercial practice through specialized agreements to commercial companies once our patent application is fully approved. Special Requirements for Annual Project Report: Unobligated funds: less than 20 percent of current funds Categories for which nothing is reported: Participants: Other Collaborators Outreach Activities Products: Internet Dissemination Special Reporting Requirements Animal, Human Subjects, Biohazards