Segmentation techniques are used in methods for embedding and detecting digital watermarks in multimedia signals, such as images, video and audio. A digital watermark embedder segments a media signal into arbitrary shaped regions based on a signal characteristic, such as a similarity measure, texture measure, shape measure or luminance or other color value extrema measure. The attributes of these regions are then used to adapt an auxiliary signal such that it is more effectively hidden in the media signal. In one example implementation, the segmentation process takes advantage of a human perceptibility model to group samples of a media signal into contiguous regions based on their similarities. Attributes of the region, such as its frequency characteristics, are then adapted to the frequency characteristics of a desired watermark signal. One embedding method adjusts a feature of the region to embed elements of an auxiliary signal, such as an error correction encoded message signal. The detecting method re-computes the segmentation, calculates the same features, and maps the feature values to symbols to reconstruct an estimate of the auxiliary signal. The auxiliary signal is then demodulated or decoded to recover the message using error correction decoding/demodulation operations.