Join
today

Boliven PRO is more than just patent search

  • Build and save lists using the powerful Lists feature
  • Analyze and download your search results
  • Share patent search results with your clients

Patents »

US5819289: Data embedding employing degenerate clusters of data having differences less than noise value

Share

Filing Information

Inventor(s) Sanford, II; Maxwell T. · Theodore G. Handel ·
Assignee(s) The Regents of the University of California ·
Attorney/Agent(s) Milton D. Wyrick ·
Primary Examiner Paul R. Lintz ·
Application Number US8855243
Filing date 05/13/1997
Issue date 10/06/1998
Predicted expiration date 04/02/2016
U.S. Classifications 707/104  · 707/100  ·
International Classifications G06F 1730  ·
Kind CodeA
International Classifications 707104;100 ·
Related U.S. Application DataBACKGROUND OF THE INVENTION
FIELD OF THE INVENTION
The present application is a continuation-in-part application out of continuation-in-part application Ser. No. 08/626,836, filed Apr. 2, 1996 now abandoned.
18 Claims, No Drawings


Abstract

A method of embedding auxiliary information into a set of host data, such as a photograph, television signal, facsimile transmission, or identification card. All such host data contain intrinsic noise, allowing pixels in the host data which are nearly identical and which have values differing by less than the noise value to be manipulated and replaced with auxiliary data. As the embedding method does not change the elemental values of the host data, the auxiliary data do not noticeably affect the appearance or interpretation of the host data. By a substantially reverse process, the embedded auxiliary data can be retrieved easily by an authorized user.

Independent Claims | See all claims (18)

  1. 1. A method of embedding auxiliary data into host data comprising the steps of:creating a digital representation of said host data in the form of elements having numerical values and containing a noise component;creating a digital representation of said auxiliary data in the form of a sequence of individual bit values;evaluating said noise component of said digital representation of said host data;comparing the values of said elements with said noise component to determine degenerate clusters of four or more said elements having numerical values which differ by less than said value of said noise component;replacing individual values of said elements with equivalent values taken from said degenerate clusters of said elements in order to embed bit values of said auxiliary data corresponding to said sequence of bit values of said auxiliary data; andoutputting said host data with said auxiliary data embedded into said host data as a file.
  2. 4. A method of constructing auxiliary data from host data containing a noise component comprising the steps of:constructing from said host data a bit sequence indicative of said embedded auxiliary data, and which allows for verification of said host data;interpreting said host data to determine host element degenerate clusters and two or more pairs which differ by less than said noise component and which correspond to bit values of said auxiliary data;identifying said auxiliary data using said bit sequence; and constructing said auxiliary data as a file.
  3. 13. Apparatus for embedding auxiliary data into host data that can be serialized to a sequence of host-data element values:input port means receiving said individual host-data element values in an ordered sequence;key-pair table, key-table, and key-value means receiving said embedding pair candidate values, and retaining said key-pair table, key-table, and key-value for reference purposes;input port means presenting host-data and auxiliary data values in an ordered sequence;output port means presenting modified host-data values or constructed auxiliary data values in an ordered sequence.
  4. 16. Apparatus for constructing auxiliary data from a key-pair table, or a key-table embedded into individual frames of host data presented in sequence to said input port:look-up table means receiving said key-pair table from said input port containing individual host-data values for extracting said key-pair table and outputting a key-pair index corresponding to each of said host-data values from said input port sequence of host data; andauxiliary data construction means comparing said key-pair table with said input port host-data values and using said key-pair table to construct said auxiliary data from said embedded host-data data and presenting said auxiliary data to said output port.

References Cited

U.S. Patent Documents

Document NumberAssigneesInventorsIssue/Pub Date
US5434649 Canon Kabushiki Kaisha Hasuo et al. Jul 1995
US5493677 Systems Research & Applications Corporation Balough et al. Feb 1996
US5530759 International Business Machines Corporation Braudaway et al. Jun 1996
US5568570 Eastman Kodak Company Rabbani Oct 1996
US5613004 The Dice Company Cooperman et al. Mar 1997
US5617119 Systems Research & Applications Corporation Briggs et al. Apr 1997
US5636292 Digimarc Corporation Rhoads Jun 1997
US5646997 Barton Jul 1997
US5659726 Sanford, II et al. Aug 1997
US5664018 Leighton Sep 1997
US5687236 The Dice Company Moskowitz et al. Nov 1997
US5689587 Massachusetts Institute of Technology Bender et al. Nov 1997
US5699427 International Business Machines Corporation Chow et al. Dec 1997
US5710834 Digimarc Corporation Rhoads Jan 1998
US5727092 The Regents of the University of California Sanford, II et al. Mar 1998
US5734752 Xerox Corporation Knox Mar 1998

Other Publications

Boland, "Watermarking Digital Images for Copyright Protection", Fifth International Conference on Image Processing and Its Applications, 4-6 Jul. 1995, pp. 326-330.
Cox et al., "A Secure, Imperceptible, Yet Perceptually Salient, Spread Spectrum Watermark for Multimedia", Southcon/96 Conference Record, Orlando Florida, 25-27 Jun. 1996, pp. 192-197.
O'Ruanaidh et al, "Watermarking Digital Images for Copyright Protection", IEE Proceedings-Vision, Image, and Signal Processing, vol. 143, No. 4, Aug. 1996, pp. 250-256.
Komatsu et al, "Authentication System Using Concealed Image in Telematics", Memoirs of the School of Science and Engineering, Waseda University, No. 52, Oct., 1988, pp. 45-60.
M.T. Sanford et al., "The Data Embedding Method", SPIE vol. 2615, 23 Oct. 1995, pp. 226-259.
Tanaka et al., A Visual Retrieval System With Private Information for Image Database, Proceedings, International Conference on DSP Applications and Technology, Oct. 1991, pp. 415-421.
Van Schyndel et al., "A Digital Watermark", Proceedings ICIP-94, Austin, Texas, 13-16 Nov. 1994.
Jochen Rindfrey, "Towards an Equitable System for Access Control and Copyright Protection in Broadcast Image Services; The Equicrypt Approach", Intellectual Property Rights and New Technology, Proceedings of the Conference, (Verlag (Munchen, 1995), pp. 1-1.
Macq et al., "Cryptology for Digital TV Broadcasting", Proceedings of the IEEE, vol. 83, No. 6, Jun. 1995, pp. 944-957.

Referenced By

Document NumberAssigneeInventorsIssue/Pub Date
SG80664 HITACHI LTD HIROSHI YOSHIURA et al. May 2001
US6130741 Eastman Kodak Company Xin Wen et al. Oct 2000
US6332031 Digimarc Corporation Geoffrey Rhoads et al. Dec 2001
US6065119 The Regents of the University of California Sandford, II; Maxwell T. et al. May 2000
US6094483 Research Foundation of State University of New York Jiri Fridrich et al. Jul 2000
US6122403 Digimarc Corporation Geoffrey B. Rhoads Sep 2000
US6021196 The Regents University of California Sandford, II; Maxwell T. et al. Feb 2000
US6211919 Tektronix, Inc. Scott E. Zink et al. Apr 2001
US6052486 QuickBut, Inc. Kenneth Charles Knowlton et al. Apr 2000
US6917724 Digimarc Corporation Phillip Andrew Seder et al. Jul 2005
US6434701 Kwan Software Engineering, Inc. John Man Kwong Kwan Aug 2002
US6519351 Hitachi, Ltd. Hiroyuki Kimura et al. Feb 2003
US6608919 Digimarc Corporation Adnan M. Alattar Aug 2003
US6690813 Hitachi, Ltd. Hiroyuki Kimura et al. Feb 2004
US6804377 Digimarc Corporation Alastair M. Reed et al. Oct 2004
US6711276 Hitachi, Ltd. Hiroshi Yoshiura et al. Mar 2004
US6700990 Digimarc Corporation Geoffrey B. Rhoads Mar 2004
US6768809 Digimarc Corporation Geoffrey B. Rhoads et al. Jul 2004
US6850626 Digimarc Corporation Geoffrey B. Rhoads et al. Feb 2005
US6788800 DigiMarc Corporation J. Scott Carr et al. Sep 2004
US7305615 Gigalogix, Inc. Richard Ross Dec 2007
US7424130 Sony Corporation Tetsujiro Kondo et al. Sep 2008
US7486799 Digimarc Corporation Geoffrey B. Rhoads Feb 2009
US6625297 Digimarc Corporation Brett A. Bradley Sep 2003
US6636615 Digimarc Corporation Geoffrey B. Rhoads et al. Oct 2003
US6590996 Digimarc Corporation Alastair M. Reed et al. Jul 2003
US6567531 Sony Corporation Tetsujiro Kondo et al. May 2003
US6823075 Digimarc Corporation Burt W. Perry Nov 2004
US6775392 Digimarc Corporation Geoffrey B. Rhoads Aug 2004
US7050201 Digimarc Corporation Adnan M. Alattar May 2006
US6993149 Digimarc Corporation Hugh L. Brunk et al. Jan 2006
US7171016 Digimarc Corporation Geoffrey B. Rhoads Jan 2007
US7424131 Digimarc Corporation Adnan M. Alattar et al. Sep 2008
US6535614 Hitachi, Ltd. Hiroyuki Kimura et al. Mar 2003
US6556688 Seiko Epson Corporation Viresh Ratnakar Apr 2003
US6744906 Digimarc Corporation Geoffrey B. Rhoads et al. Jun 2004
US6836564 Denso Corporation Osamu Katayama et al. Dec 2004
US7194624 HARRIS SCOTT C Scott C. Harris Mar 2007
US7508944 Digimarc Corporation Hugh L. Brunk Mar 2009
US7587368 David Paul Felsher Sep 2009
US6553129 Digimarc Corporation Geoffrey Rhoads Apr 2003
US6718047 Digimarc Corporation Geoffrey B. Rhoads Apr 2004
US7055034 Digimarc Corporation Kenneth Lee Levy May 2006
US6694042 Digimarc Corporation Phillip Andrew Seder et al. Feb 2004
US6522766 Seiko Epson Corporation Viresh Ratnakar Feb 2003
US6829368 Digimarc Corporation Joel R. Meyer et al. Dec 2004
US6993153 Digimarc Corporation Brett A. Bradley Jan 2006
US7181017 David Felsher Robert H. Nagel et al. Feb 2007
US7421436 International Business Machines Corporation Timo J. Salo et al. Sep 2008
US6611607 Digimarc Corporation Bruce L. Davis et al. Aug 2003
US6577746 Digimarc Corporation Douglas B. Evans et al. Jun 2003
US6567533 Digimarc Corporation Geoffrey B. Rhoads May 2003
US6721440 Digimarc Corporation Alastair M. Reed et al. Apr 2004
US6804376 Digimarc Corporation Geoffrey B. Rhoads et al. Oct 2004
US6763124 Digimarc Corporation Osama M. Alattar et al. Jul 2004
US6574350 Digimarc Corporation Geoffrey B. Rhoads et al. Jun 2003
US6917691 Digimarc Corporation Douglas B. Evans et al. Jul 2005
US6763122 Tony Rodriguez et al. Jul 2004
US6643383 Institut Eurecom Jean-Luc Dugelay Nov 2003
US6965682 DAVIS BRUCE L Bruce L. Davis et al. Nov 2005
US6975746 Digimarc Corporation Bruce L. Davis et al. Dec 2005
US7430566 Microsoft Corporation Mingjing Li et al. Sep 2008
US6614914 Digimarc Corporation Geoffrey B. Rhoads et al. Sep 2003
US6792535 Kwan Software Engineering, Inc. John Man Kwong Kwan Sep 2004
US6965697 Sony Corporation Tetsujiro Kondo et al. Nov 2005
US7054463 Digimarc Corporation Geoffrey B. Rhoads et al. May 2006
US6404899 International Business Machines Corporation Saurabh Agarwal et al. Jun 2002
US6728390 Digimarc Corporation Geoffrey B. Rhoads et al. Apr 2004
US7870388 Illinois Computer Research, LLC Scott C. Harris Jan 2011
US7908641 Infineon Technologies AG Wieland Fischer Mar 2011
US7724901 Olympus Corporation Takashi Ishikawa May 2010
US7738711 Sony Corporation Tetsujiro Kondo et al. Jun 2010
US7773770 Digimarc Corporation Douglas B. Evans et al. Aug 2010
US7778438 MyPort Technologies, Inc. Michael F. Malone Aug 2010
US7778440 Myport Technologies, Inc. Michael F. Malone Aug 2010
US7788684 Verance Corporation Rade Petrovic et al. Aug 2010
US6681028 Digimarc Corporation Tony F. Rodriguez et al. Jan 2004
US7027614 Digimarc Corporation Alastair M. Reed Apr 2006
US6381341 Digimarc Corporation Geoffrey B. Rhoads Apr 2002
US6424725 Digimarc Corporation Geoffrey B. Rhoads et al. Jul 2002
US6408082 Digimarc Corporation Geoffrey B. Rhoads et al. Jun 2002
US7362879 Digimarc Corporation Douglas B. Evans et al. Apr 2008
US7512793 Scott C. Harris Mar 2009
US7958365 Digimarc Corporation Hugh L. Brunk Jun 2011
US8028228 Richard A. Ross Sep 2011
US8068638 Myport Technologies, Inc. Michael F. Malone et al. Nov 2011
US8095795 Digimarc Corporation Kenneth L. Levy Jan 2012
US8078648 Microsoft Corporation Andrew V. Kadatch et al. Dec 2011
US8135169 Myport Technologies, Inc. Michael F. Malone Mar 2012
US8250365 Scott C. Harris Aug 2012
US8175329 Digimarc Corporation Adnan M. Alattar May 2012
US8285995 Kwan Software Engineering, Inc. John Man Kwong Kwan Oct 2012
US8280103 Verance Corporation Rade Petrovic et al. Oct 2012
US8300274 Digimarc Corporation Adnan M. Alattar Oct 2012
US8538066 --
US8533481 --
US8374385 --
US8451086 --
US8549307 --
US8509477 --

Patent Family