Digital watermarking is a process for modifying physical or electronic media to embed a hidden machine-readable code into the media. The media may be modified such that the embedded code is imperceptible or nearly imperceptible to the user, yet may be detected through an automated detection process. Most commonly, digital watermarking is applied to media signals such as images, audio signals, and video signals. However, it may also be applied to other types of media objects, including documents (e.g., through line, word or character shifting), software, multi-dimensional graphics models, and surface textures of objects.
Digital watermarking systems typically have two primary components: an encoder that embeds the watermark in a host media signal, and a decoder that detects and reads the embedded watermark from a signal suspected of containing a watermark (a suspect signal). The encoder embeds a watermark by subtly altering the host media signal. The reading component analyzes a suspect signal to detect whether a watermark is present. In applications where the watermark encodes information, the reader extracts this information from the detected watermark.
Several particular watermarking techniques have been developed. The reader is presumed to be familiar with the literature in this field. Particular techniques for embedding and detecting imperceptible watermarks in media signals are detailed in the assignee's U.S. Pat. Nos. 6,122,403 and 6,614,914, which are hereby incorporated by reference.
Integrating a hardware watermark reader in imaging devices (cameras, scanners, printers, fax machines, copiers) cellular phones, PDA devices may soon be necessary. Currently, most of these devices have no digital rights management (DRM) and hence can freely download music, video, and pictures from the Internet. An integrated watermark reader not only would enforce DRM in these devices, but also it would enable new applications. Such applications may potentially change the usage habit and pattern of these devices. For example, the imaging device integrated in most of these devices could be used with a watermarked advertisement and a built-in global positioning system (GPS) to guide the user to the nearest store where the advertised goods are currently available or on sale.
Low-cost stand-alone watermark readers will also be developed soon to harness the power of the millions of watermark-enhanced identity cards already deployed in the USA and around the world. These readers will be essential in enforcing the law and reducing identity thefts. Also, the ubiquitous deployment of these readers will enable and empower a new wave of applications.
Cellular phones and PDA devices, however, have some limitations when used with sophisticated watermark detectors operating on large images. These limitations include the type and speed of the processor used in these devices, the amount of available memory, the system bandwidth, and the operating system controlling these devices.
Usually, cellular phones and PDA devices employ fixed-point processors such as Intel's StrongARM or XScale processors, which have a clock speed in the 100-400 MHz range. This speed is only a fraction of the speed of mainstream processors typically found in PCs. This speed limits the amount of computations and their precision, which the watermark detector is allowed to perform.
These devices also have limited DRAM and system bandwidth. Currently, PDA devices have 32 MB of memory, but cellular phones have about 6 MB only. About half of the memory available on cellular phones is used by the operating system. Also, most of these devices have about 20 MHz of system bandwidth. The low bandwidth combined with the lack of memory can be a major bottleneck for real-time detection of the watermarks embedded in large images via cellular phones and PDA devices.
Moreover, these devices use either a primitive native operating system such as MS SmartPhone, Symbian, and Brew, or a Java-based operating system such as Doja or J2ME. Although native operating systems allow the execution of a watermark detector written in a compiled language such as C, Java-based operating systems require Java implementations of the detector. Such an implementation is not as efficient as a C implementation, especially for sophisticated signal processing algorithms such as watermark detectors.
Although a watermark detector can be implemented in a customized chip, the cost of implementing a complex algorithm can be prohibitive. A field programmable gate array (FPGA) or application-specific integrated circuit (ASIC) can be used for this purpose. Such a chip can be integrated with the cellular phone, PDA device, or stand-alone watermark reader. However, complex watermarking algorithms may require a large number of gates and excessive on-chip memory and system bandwidth, which tremendously increases the cost of this dedicated chip. This cost, however, can be reduced substantially by reducing the data that the watermark detector operates on and the computations it performs on this data.
This document describes a block-based watermark detector and reader that use a hierarchical search strategy to quickly zoom into the image region with the strongest watermark. This approach reduces the computations and the amount of data the detector operates on, which, in turn, reduces the processor speed, the memory, and the bandwidth requirement of the detector. This design makes the detector suitable for the aforementioned real-time software and low-cost hardware implementations.
Further features and combinations will become even more apparent with reference to the following detailed description and accompanying drawings.