Certain forms of distortion make it difficult to recover hidden data embedded in an audio or image signal by quanitzation techniques. To compensate for this distortion, an embedded data reader analyzes a statistical distribution (e.g., a histogram) of feature samples (124) in an audio or image signal suspected of having hidden auxiliary data to derive an estimate of quantizers used to encode a reference signal (126). The estimated quantizers then recover the reference signal (126), and the reader uses the reference signal (126) to determine and compensate for geometric or temporal distortion, like spatial scaling and rotation of image data, and time scale and speed changes of audio data. After compensating for such distortion, the reader can then more accurately recover hidden message data using quantization techniques to extract the message. The reference signal (126) is preferably repeated in blocks of the image or audio data to enable synchronization at many points in an image or audio data stream. An adaptive embedding and reading technique is used to adaptively define the quantization bins for regions of a host media signal based on signal statistics for each of the regions.