An image size reduction unit reduces the image size of an input image signal, thereby generating a size-reduced image signal. A specific frequency component extraction unit extracts a specific frequency component signal from the size-reduced image signal. A phase controller controls the phase of the specific frequency component signal. A correlator computes a cross-correlation value between the phase-controlled specific frequency component signal and size-reduced image signal. A watermark information estimation unit estimates, from the cross-correlation value, watermark information embedded in the input image signal.