Watermark design and detection have been studied as two separate problems so far. However, we show that, if the watermarking algorithm is based on the watermark detection method, then significant gains can be achieved. With a watermark detector based on a sequential hypothesis test rather than a fixed sample size test, the number of watermark pixels can be reduced almost by a factor of two for small detection error probabilities. This is because, the sequential hypothesis test requires less (average) number of pixels to detect the presence/absence of a watermark compared to a fixed sample size detector. The savings in the number of pixels to be watermarked results in an increased immunity to host signal attacks such as cropping. Degradation in the signal quality due to redundant watermarking is also minimized. Further, applications such as DVD require minimal amount of watermarking. The computational efficiency of the proposed watermark detector can also be exploited to efficiently search for watermarks in large image databases.