A digital image signal based on transformed in frequency, thereby providing partitioned frequency components. Characteristic information is calculated in accordance with a coefficient at a first frequency domain that is selected from among the partitioned frequency components. A coefficient at a second frequency domain is handled in accordance with predetermined rules, thereby embedding the characteristic information into the coefficient at the second frequency domain. The second frequency domain is selected from among areas that differ from the first frequency domain. The frequency coefficients that exhibit several frequency components are encoded in a predetermined manner, thereby producing compressed image data.