Methods and apparatus for characterizing media are described. An example apparatus includes a transformer to convert at least a portion of a block of audio into a frequency domain representation including a plurality of frequency components; a decision metric processor to: define a band of frequency components having real and imaginary spectral components, define a plurality of frequency bins within the band, determine respective difference functions for each of the frequency bins using a product of the real and imaginary spectral components of a corresponding group of the frequency bins, the corresponding group for a first one of the frequency bins including at least the first one of the frequency bins and a second one of the frequency bins selected based on the first frequency bin, and determine a decision metric by summing the difference functions; and a signature determiner to determine a signature based on the decision metric.