Lossless embedding of data in digital objects

Apparatus for losslessly embedding a message into a digital object comprised of samples, said apparatus comprising:

• means for extracting from said object a first subset having the property that it can be randomized while preserving the perceptual quality of said object;
• means for applying a discrimination function to portions of the first subset to classify a regularity of said portion, said discrimination function for a plurality of portions being represented as a vector;
• means for reversibly modifying said first subset based on said message and said discrimination function;
• means for losslessly compressing said modified first subset and said vector to form a second subset;
• means for inserting said second subset into said object in place of said first subset to form a transformed object, whereby said message is effectively transmitted and extracted by transmitting said transformed object and extracting said second subset therefrom;
• and
• means for restoring said object by (1) decompressing said compressed bitstream, (2) restoring said first subset, and (3) reinserting said first subset into said object.

A computer-readable storage medium embodying program instructions for a method for losslessly embedding a message into a digital object comprised of samples, said method comprising the steps of:

• extracting from said object a first subset having the property that it can be randomized while preserving the perceptual quality of said object;
• applying a discrimination function to portions of the first subset to classify a regularity of said portion, said discrimination function for a plurality of portions being represented as a vector;
• reversibly modifying said first subset based on said message and said discrimination function;
• losslessly compressing said modified first subset and said vector to form a second subset;
• inserting said second subset into said object in place of said first subset to form a transformed object, whereby said message is effectively transmitted and extracted by transmitting said transformed object and extracting said second subset therefrom;
• and
• restoring said object by decompressing said compressed bitstream, restoring said first subset, and reinserting said first subset into said object.