Image analysis – Applications
Reexamination Certificate
2000-11-07
2004-11-02
Mariam, Daniel (Department: 2621)
Image analysis
Applications
C713S176000
Reexamination Certificate
active
06813368
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to improved methods and apparatus for protecting digital information from copying, and more particularly to electronic techniques for watermarking maps and other structured data.
BACKGROUND OF THE INVENTION
With the widespread availability of digital information and the ease of copying such information, the problem of protecting that information from illicit copying has gained new prominence. A widely used method for addressing this problem is watermarking. This technique is also called fingerprinting and involves embedding hidden information into the data which encodes ownership and copyright information. Data suspected of being pirated can then be tested for this hidden information, determining if the data is copyrighted. Furthermore, by embedding unique hidden information into each copy, pirated data can be traced back to its original purchaser.
This approach has been applied to a wide range of media, such as images, audio, video, and the like. More recently, intellectual property protection problems related to VLSI design, such as placement and routing design data and implementations of finite state machines, have also been addressed in this fashion. In addition, there are cryptographic protocols which address related issues, such as how to distribute copies with guarantees of anonymity and reliable authentication.
SUMMARY OF THE INVENTION
The present invention addresses the application of watermarking techniques to protect map and other structured data. Consider the following situation, by way of example. Through expensive surveys, a company, referred to as the owner of the map, compiles accurate map data, represented by a weighted graph where nodes represent locations, edges represent links between locations, and the weights represent the distance between adjacent locations. This data is then sold to other parties called providers who provide end users access to it. This access is generally indirect in the sense that the provider allows the end users to query pairs of nodes, such as a starting point like New York City and an ending point like Chicago. The provider then responds to each query with appropriate information related to the pair, such as the distance between the nodes, or a shortest route, or both. This situation already exists for maps of the US roadway system, with companies such as MapQuest acting as map owners, web sites like Yahoo! acting as providers, and end users across the Internet accessing the data. In such a context, protecting the underlying data presents a variety of problems. For example, a watermark cannot distort the underlying data in a way that eliminates the value of the map, or which is easily detectable and countered. In addition, it is not hard to envision similar situations or data structures for which these problems could arise, such as providing routing information on a network.
A more complete understanding of the present invention, as well as further features and advantages of the invention, will be apparent from the following Detailed Description and the accompanying drawings.
REFERENCES:
patent: 5721788 (1998-02-01), Powell et al.
patent: 5742892 (1998-04-01), Chaddha
patent: 5825892 (1998-10-01), Braudaway et al.
patent: 6301368 (2001-10-01), Bolle et al.
Pieprzyk, “Fingerptints for Copyright Software Protection,” 1999, ISW'99, LNCS 1729, pp. 178-190.*
Tomboulian, “Overview and Extensions of a System for Routing Directed Graphs on SIMD Architectures” 1988, IEEE, pp. 63-67.*
Ohbuchi et al., “Watermarking Three-Dimensional Polygonal Models Through Geometric and Topological Modification,” IEEE, 1999, pp. 551-560.*
Su et al., “Blind digital watermarking for cartoon and map images,” Proc. SPIE vol. 3657: Security and Watermarking of Multimedia Contents, Jan. 25-27, 1999, pp. 296-306.*
Ohbuchi et al., “Watermarking Three-Dimensional Polygonal Models,” Proc. 5th ACM International Conference Multimedia, Nov. 9-13, 1997, pp. 261-272.*
Yeo et al., “Watermarking 3D Objects for Verification,” IEEE, Jan./Feb. 1999, pp. 36-45.*
Benedens, “Geometry-Based Watermarking of 3D Models,” IEEE, Jan./Feb. 1999, pp. 46-55.*
Joe Kilian, F. Thomson Leighton, Lesley R. Matheson, Talal G. Shamoon, Robert E. Tarjan, Francis Zane, “Resistance of Digital Watermarks to Collusive Attacks”, Princeton Computer Science Technical Report TR-585-98, 1998, pp. 1.
Emil Praun, Hugues Hoppe and Adam Finkelstein, “Robust Mesh Watermarking”, Princeton Computer Science Technical Report TR-593-99, 1999, pp. 1-21.
Joe Kilian, F. Thomson Leighton, Lesley R. Matheson, Talal G. Shamoon, Robert E. Tarjan and Francis Zane, “Resistance of Digital Watermarks to Collusive Attacks”, ISIT 1998, Cambridge MA, USA, Aug. 16-Aug. 21.
Ingemar J. Cox, Joe Kilian, F. Thomson Leighton and Talal Shamoon, “Secure Spread Spectrum Watermarking for Multimedia”, IEEE Transactions on Image Processing, vol. 6, No. 12, pp. 1673-1687, Dec. 1997.
Dan Boneh and James Shaw, “Collusion-Secure Fingerprinting for Digital Data”, IEEE Transactions on Information Theory, vol. 44, No. 5, pp. 1897-1905, Sep. 1998.
Andrew B. Kahng, Stefanus Mantik, Igor L. Markov, Miodrag Potkonjak, Paul Tucker, Huijuan Wang and Gregory Wolfe, “Robust IP Watermarking Methodologies for Physical Design”, In Proceedings of the 35thDesign Automation Conference Proceedings, pp. 782-787, San Francisco, CA, Jun. 1998.
Neal R. Wagner, “Fingerprinting”, In Procedings of the 1983 IEEE Symposium on Security and Privacy, pp. 18-22, Apr. 1993.
A.B. Kahng, J. Lach, W.H. Mangione-Smith, S. Mantik, I.L. Markov, M. Potkonjak, P. Tucker, H. Wang and G. Wolfe, “Watermarking Techniques for Intellectual Property Protection”, In Proceedings of the 35thAnnual Design Automation Conference, pp. 776-781, San Francisco, CA, Jun. 1998.
Gang Qu and Miodrag Potkonjak, “Analysis of Watermarking Techniques for Graph Coloring Problem”, International Conference on Computer Aided Design, San Jose, California, ACM 1998, pp. 190-193.
Arlindo L. Oliveira, “Robust Techniques for Watermarking Sequential Circuit Designs”, In Proceedings of the 36thAnnual Design Automation Conference, pp. 837-842, New Orleans, LA, Jun. 1999.
Khanna Sanjeev
Zane, Jr. Francis Xavier
Lucent Technologies - Inc.
Mariam Daniel
Patel Shefali
LandOfFree
Methods and apparatus for watermarking maps and other... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Methods and apparatus for watermarking maps and other..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Methods and apparatus for watermarking maps and other... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3318425