Methods for embedding arbitrary digital data within an iconic representation of a document page image are summarized. The result of the encoding is a small iconic image containing the iconic data as small rectangular blocks of pixels, along with a mixture of reduced document image components such as graphics, text and images. As a first step in ensuring data recovery, the encoder verifies that the iconic image can contain the entire message, and that it can be decoded correctly from the noiseless pre-printing image. To retrieve the message, the data must be separated from the other components in the iconic image and decoded. The decoder is assumed to have no prior information about the location of data within the icon, the encoding channels in which it is encoded, or other meta-data about the message, such as the size or the amount of error-correction encoding. There are three major steps in the decoding process: segmentation, to identify and serialize the datablocks in the icon; measurement of encoding parameters, including determination of the encoding channels; and extraction of the message. Errors can be introduced into the decoding process at a number of places, and it is necessary to provide mechanisms for detecting and correcting them. For the parameters used here, datablocks from icons generated at reductions of up to 7x are robustly decoded, and error-free message decoding is typically achieved for icons derived from arbitrary pages of scanned documents.