Electronic watermarks in digital documents can be detected, even if the content of the digital documents has been subjected to distortion or other attempts to hide or destroy the watermarks. One method involves inputting the distorted image and comparison information, the comparison information including at least one of the original image or information used for embedding the electronic watermark; dividing a domain of the original image into a plurality of patches, based on the comparison information; inputting affine parameters of a predetermined patch from among the patches in the original image; extracting a patch candidate from the distorted image; using a predetermined electronic watermark detection method, judging whether the patch candidate in the distorted image adequately correlates with a neighboring patch in the original image; when the judging indicates an adequate correlation, outputting a part of the electronic watermark. Another method involves determining a correspondence between patches in an original image having n patches, and patches in a distorted image; more specifically, the method involves inputting predetermining affine parameters of one of the plurality of predetermined patches; setting the input predetermining affine parameters of the one of the plurality of patch as initial affine parameters for investigating a new patch; and investigating a correspondence of the new patch of the distorted image and the new patch of the original image by slightly modifying the set input predetermining affine parameters.