# Patent

## Title
Digital watermarking applications

## Abstract

In one aspect, assembly of multi-part food packaging is checked by reference to payloads of steganographically-encoded digital watermarks printed across plural components of the packaging. Marking all surfaces of the packaging components allows arbitrary orientation of feed stock in assembly equipment, and wide latitude in placement of inspection cameras along the packaging line. In another aspect, a scanner at a retail checkout station is alert to any gap detected in steganographic encoding on retail product packaging and, if found, alerts an operator to possible presence of an adhesive label with a misleading barcode. A great variety of others features and arrangements are also detailed.

## Background
RELATED APPLICATION DATA
This application claims priority to provisional application 62/129,655, filed Mar. 6, 2015, the disclosure of which is incorporated by reference.


INTRODUCTION
Digital watermarking is an information hiding technology useful, e.g., in steganographically encoding printed items to convey plural symbol payloads. For example, artwork printed on the packaging of a retail product can be digitally watermarked with a payload that includes the product's GTIN (Global Trade Identification Number) identifier. Known digital watermarking methods include those detailed in U.S. Pat. Nos. 6,590,996, and 8,199,969, in published application 20140052555, and in pending patent applications Ser. No. 14/616,686, filed Feb. 7, 2015, and 62/106,685, filed Jan. 22, 2015.
In accordance with one aspect of the present technology, digital watermarking is employed to ensure that items that are to be combined with each other are properly-matched. A particular example is food containers, and their lids.
In accordance with another aspect of the present technology, digital watermarking is employed to reduce a growing type of retail fraud—barcode switching.
The foregoing and additional features and advantages of the present technology will be more readily apparent from the following Detailed Description, which proceeds with reference to the accompanying drawings.



BRIEF DESCRIPTION OF THE DRAWINGS
FIGS. 1 and 2 show food packaging in which a labeled lid is applied to a labeled food container.
FIG. 3 shows a bottle of catsup employing three distinct labels.
FIG. 4 illustrates a data structure used in certain embodiments of the technology.
FIG. 5 is a block diagram showing an environment in which certain embodiments of the technology can be employed.
FIG. 6 is a diagram of components in an exemplary embodiment.
FIG. 7 is a diagram illustrating a processing architecture for controlling recognition units within an exemplary system.
FIG. 8 is diagram illustrating software modules that operate on a sequence of image frames to detect and extract digital payloads from images of objects within the frames.
FIGS. 9A and 9B illustrate image portions of an object in different frames captured from a field of view of an imager.
FIG. 10 is a block diagram of a signal encoder for encoding a digital payload signal into an image signal, such as artwork for product packaging
FIG. 11 is a block diagram of a compatible signal decoder for extracting the digital payload signal from a captured image signal.
FIG. 12 is a flow diagram illustrating operations of a signal generator.
FIG. 13 is a diagram illustrating embedding of an auxiliary signal into host image signal.
FIG. 14 is a flow diagram illustrating a method for decoding a payload signal from a host image signal.



DETAILED DESCRIPTION
Food is commonly packaged on automated manufacturing lines, which may fill and cap hundreds or thousands of containers per hour. An example is fresh salsa. A conveyor arrangement successively presents paper or plastic tubs under a filling nozzle, which dispenses a set amount (e.g., 16 oz.) of salsa from a reservoir. At a later station, a flat lid is press-applied. Further down the line the capped container passes by an inkjet printing mechanism that spray-paints an expiration date and lot code onto each container or lid. After such printing, the container passes into a bundler that secures the lid by applying and heat-shrinking a ring of security tape.
Similar arrangements are employed with yogurt, ice cream, sour cream, dips (e.g., bean dip, onion dip), and many jarred foods including baby food, etc.
Some consumers have food allergies or other sensitivities, making it essential that foodstuffs be labeled properly. Yet in the busy-ness of a manufacturing plant, and given human imperfection, it sometimes happens that wrong lids are applied. For example, a lid may indicate that it caps a gluten-free variant of a producer's bean dip, yet be applied mistakenly to a container of bean dip marked as including gluten. Likewise, a lid indicating “Chocolate Ice Cream” may be applied to a tub labeled and containing chocolate peanut ice cream. In addition to gluten and peanuts, such issues similarly arise with casein, dairy, high fructose corn syrup, and GMO marking, etc.
To address this problem, one aspect of the present technology employs digital watermarks encoded in artwork formed on food lids and containers. Each such watermark conveys a payload including, e.g., the GTIN for the product with which the packaging is to be used. For example, a producer's chocolate ice cream product may have the GTIN 0087932602588. This number is included in the payload of a digital watermark encoded in the artwork for the ice cream container, and this same number is included in the payload of a digital watermark encoded in the (different) artwork for the ice cream lid.
On the manufacturing line, a first camera inspects each tub just before it is filled, and a second camera inspects each lid just before it is applied. A software-programmed processor decodes the digital watermark payload from each image, and ensures they match. (A further check can be made to ensure that the GTINs encoded in the tub artwork and lid artwork properly match an identifier for the foodstuff being dispensed into the container.) If a mismatch is detected, an alarm is sounded, and the packaging line is halted. Plant personnel can then investigate the mismatch, and correct the material flow as appropriate (e.g., replacing wrong lids with correct lids in the lid hopper).
In one particular embodiment, the containers are generally cylindrical (i.e., they are rotationally-symmetric about a central axis) and the lids are round, as shown in FIG. 1). This has an advantage in that, regardless of the camera's mounting position in the packaging line, the face of the container closest to the camera will present a strip of watermarked artwork that is generally squarely-facing the camera, enabling the watermark to often be decoded without geometrically altering the image to correct for viewpoint distortion.
In another particular embodiment, the containers are generally rectangular, as are the lids, as shown in FIG. 2. This has a different advantage: a surface expanse of the container extends in a single plane, so that depiction of the surface in the captured imagery has a generally uniform (sometimes affine) distortion. Compensation of such distortion is straightforward by reference to spatial frequency-domain markers within the digital watermark signal, providing a relatively large area of distortion-corrected artwork from which the digital watermark payload can be decoded.
In another embodiment, rather than sense watermarked information from the components before they are combined, the checking is done after combination. In the salsa example, one or more cameras captures imagery depicting both the top and side of a finished foodstuff container to check, e.g., that the watermark payload encoded in the lid artwork matches the watermark payload encoded in the container artwork.
Sometimes an extension string of several symbols is appended to the product's GTIN identifier to distinguish product or label variants. Alternatively a code distinct from the GTIN can be employed. Some producers have proprietary codes that can be used for such purpose, such as the IRMS (Individual Raw Material Specification) numbers (also called the GCAS or PCEM codes) issued by Proctor and Gamble.
The present technology is also useful in checking that multiple adhesive labels applied to a common product are combined appropriately.
Consider a bottle of catsup, or a jug of laundry detergent, that bears several labels, e.g., one label for a front surface of the container, a second label for a back surface, and a third label on the neck. (A barcode encoding the product's GTIN may appear on only one of the labels—typically the second.) FIG. 3 is exemplary, and shows a front label 41 and a neck label 42 on a bottle of catsup. (The back label is not depicted.)
Again, it is important that such labels be used in consistent groupings. Each different label (including each label revision) can be assigned a distinct identifier, and printing on the label can convey such identifier. Small Data Matrix barcodes have been used for such a purpose in the past, but are visually distracting, and occupy real estate that the producer would prefer to apply to communications with the consumer.
In accordance with an example of the present technology, artwork for each label steganographically encodes a corresponding identifier for that label. The encoding can convey both the identifier for that label, and the GTIN for the product. These two data can be combined into a single payload, and represented by a single watermark pattern included in the label artwork. Alternatively, the two data can be conveyed in separate watermark patterns—both of which are included in the label artwork.
A reference data structure can establish permitted combinations of labels on a product. For example, such a data structure can detail a label's identifier, together with identifiers of all other labels with which it properly may be combined. To illustrate, the neck label 42 in FIG. 4 (which includes text “GREAT TOMATO TASTE”) can be used on all varieties of bottled catsup, but the front label 41 (which touts, e.g., no salt, and no high fructose corn syrup) is suitable for use on a much smaller range of products.
FIG. 4 illustrates a table stored in memory, which may serve as such a data structure.
In a product packaging line, cameras capture imagery of the plural labels applied to a product, e.g., labels A, B and C. An associated computer system then checks label A against the data structure to confirm that its combination with label B is permissible. In particular, it searches the first column of the illustrated table for an instance of the label A identifier. If found, it then searches the text in the adjoining cell in the second column to locate the label B identifier. If the label B identifier is not found, the system declares an error and takes a corresponding action (e.g., issuing an alert to an operator, halting the manufacturing line, etc.)
The system similarly checks to validate label A's combination with label C Likewise, label B is checked for use with C. (Further checks are theoretically redundant, but can be useful in revealing inconsistencies in the data structure, e.g., checking label B for use with label A, and checking label C for use with labels A and B.)
The table data structure of FIG. 4 is simple and suitable in some applications. In other applications, however, more sophisticated structures are used. For example, a database may store business rules defining permitted uses for each label—and associated exceptions. The rules for neck label 41 may indicate its general applicability on essentially all bottles of catsup, but may further specify that such label not be applied on the second Thursday of each month—when the manufacturing line is to turn out pallets of catsup destined for a big box retailer who has specified that no neck labels are to be present in its inventory.
Another application of such technology is in assuring that the latest version of artwork is applied. Product packaging is commonly revised, e.g., to comply with new labelling laws, to adopt updated product artwork, etc. Again the problem of mis-matching arises.
An exemplary situation is ingredient substitution. For instance, a producer may alter a food product's composition by changing an artificial coloring agent from FD&C Blue No. 1 to FD&C Blue No. 2. The product's GTIN may be unchanged. Yet the producer needs to ensure that labels bearing updated artwork—listing FD&C Blue No. 2—are applied to all product packaged after the changeover date.
When the producer generates new artwork for the revised product label, e.g., including FD&C Blue No. 2 in the printed list of ingredients, a new watermark payload is encoded in a steganographic digital watermark pattern. Inspection equipment on the manufacturing line is simultaneously programmed to change its conformance check to no longer look for the former label (identified by a former payload), but to instead look for the new label (identified by the new payload). As before, if the inspection system detects non-conforming labels, a corresponding action is taken (e.g., issuing an alert to an operator, halting the manufacturing line, etc.).
Here, as in other embodiments, the inspection can take place after the labels have been applied to the product. Alternatively, inspection can occur upstream, e.g., examining rolled label feedstock that is provided to multiple label applicator machines, before these machines apply labels to the product.
In exemplary embodiments, 64-bit payloads are encoded in the label artwork. Applicant has found this payload capacity is large enough to represent both a GTIN identifier and a revision code, but is short enough so that each bit can be robustly encoded, to ensure that each bit is reliably decoded. Smaller or larger payloads can naturally be used, depending on the particular application scenario.
Food containers are just one example of how such technology can be applied. More generally, whenever items are combined, the issue of compatibility arises. Consider precision mechanical components that are machined to fit each other within tight tolerances. A “lot” can define a group of such components. A first component from one “lot” may not fit as well with a second component from a second “lot,” due to changes in the machinery on which the components were manufactured, differences in thermal properties of materials, etc. So another use of the present technology is in identifying the “lot” to which different components belong, so they can be used in conjunction with components from the same, or a known-compatible, lot.
Related to lot coding is date coding. It may be desirable that items used together have certain commonalities in date parameters, e.g., checking that each is within a permitted date range, or checking that the items' date parameters differ by less than a threshold amount.
Another application is compatible material composition. In mechanical assemblies, for example, it is desirable that each of the metal components be comprised of the same alloy, to assure similar wear and thermal properties. A simple example: using a stainless steel bolt with a galvanized steel nut is undesirable. Again, such information can be encoded on the components (e.g., by texturing) and checked to ensure that paired components are properly matched, either before or after pairing.
Another aspect of the present technology concerns deterring retail fraud.
It has been reported that some criminals conspire to defraud merchants by applying adhesive barcode labels that mis-identify products, permitting the products to be purchased at self-checkout stations for less than their true value. The products thus-purchased can then be resold on online auction sites, or on the black market.
A simple example is a barcode label encoding the GTIN of a $10 dollar bottle of wine, which is applied to a $50 bottle of wine in a supermarket. A conspirator (who may be the person who applied the fraudulent labels, or an accomplice who arrives later) purchases three such bottles for $30, and leaves the store with $150 in merchandise.
Audacious criminals may try the ruse even at checkout stands staffed by store personnel (e.g., at busy big box retailers). The merchandise there can be much more expensive than at groceries. For example, a box containing a high end Hoover Wind Tunnel vacuum cleaner, which retails for $250, may be marked with a barcode identifying it as a low end model in the same product line, retailing for $79. If the staff is busy enough, they might not notice—or give a thought—to an adhesively-applied barcode.
In accordance with this aspect of the technology, a checkout system is equipped with one or more cameras that capture imagery from products presented for checkout, to decode a steganographic watermark conveying a GTIN identifier. The captured image data can likewise be analyzed to detect the presence of a barcode (1D or 2D), and decode its payload. If a GTIN is decoded from both a product watermark and a product barcode, the values are compared. If there is a mismatch, a signal is issued to store staff, alerting them to the possible presence of a fraudulent barcode label adhered to the packaging.
A variant embodiment detects such tampering by a telltale void in the watermark signal detected from product packaging.
Watermark encoding typically spans the full-extent of retail product packaging. In the rare cases where a region of the artwork is un-watermarked (or the watermark cannot be decoded), such region is usually irregularly shaped. (One example is where a cardboard carton has been accidentally scraped, and part of the printing has been torn-off.)
In accordance with this embodiment, imagery depicting the package is analyzed to identify any region on the product surface where a watermark is not detected. If such region is found, a further check is made to determine whether the region is rectangular in shape (e.g., bounded by orthogonal pairs of parallel edges). If so, this void in watermark signal is consistent with application of a rectangular barcode label over the packaging artwork. (Since such a label would not bear the same GTIN-encoded watermark as spans the rest of the packaging, it appears as an absence of the expected watermark signal.) Again, a signal is issued to store staff, to alert them to possible presence of a fraudulent barcode.
FIG. 5 shows a retail self-checkout station that includes a scanner station incorporating the just-described technology.
The following sections more particularly detail exemplary embodiments, e.g., for encoding identifiers on product packaging (e.g., labels and containers), and later decoding same (e.g., at a point of sale terminal or in a machine vision system that inspects operation of a manufacturing line).
Vision equipment employed in manufacturing line inspection systems typically includes an image capture system and an associated source of illumination. The image capture system is comprised of optical elements, such as a lens, mirror(s), 2D imager (e.g., CMOS camera), which together enable capture of views of an object from a (usually fixed) vantage point. This vantage point is often quite close to the subject being imaged, e.g., as close as an inch or so.
Such systems capture frames in range of around 10 to 90 frames per second. In some systems, processing of a frame must be completed prior to the arrival of the next frame. In such case, the system has from 10 to 100 ms to decode any code depicted in the captured frame.
For the sake of illustration, FIG. 6 is a diagram of components in such a system.
Please also see the specification of assignee's co-pending application Ser. No. 14/842,575, HARDWARE-ADAPTABLE WATERMARK SYSTEMS, which is hereby incorporated by reference. This specification describes hardware configurations for reading machine readable data encoded on objects, including configurations usable with vision systems for manufacturing line inspection.
Referring to FIG. 6, the system has a bus 100, to which many devices, modules, etc., (each of which may be generically referred as a “component”) are communicatively coupled. The bus 100 may combine the functionality of a direct memory access (DMA) bus and a programmed input/output (PIO) bus. In other words, the bus 100 facilitates both DMA transfers and direct processor read and write instructions. In one embodiment, the bus 100 is one of the Advanced Microcontroller Bus Architecture (AMBA) compliant data buses. Although FIG. 6 illustrates an embodiment in which all components are communicatively coupled to the bus 100, one or more components may be communicatively coupled to a separate bus, and may be communicatively coupled to two or more buses. Although not illustrated, the system can optionally include one or more bus controllers (e.g., a DMA controller, an I2C bus controller, or the like or combination thereof), through which data can be routed between certain of the components.
The system also includes at least one processor 102. Processor 102 may be a microprocessor, mobile application processor, etc., known in the art (e.g., a Reduced Instruction Set Computer (RISC) from ARM Limited, the Krait CPU product-family, X86-based microprocessor available from the Intel Corporation including those in the Pentium, Xeon, Itanium, Celeron, Atom, Core i-series product families, etc.). The processor may also be a Digital Signal Processor (DSP) such the C6000 DSP category from Texas Instruments. FIG. 6 shows a second processor behind processor 102 to illustrate that the system may have plural processors, as well as plural core processors. Other components on the bus 100 may also include processors, such as DSP or microcontroller.
Processor architectures used in current vision systems include, for example, ARM (which includes several architecture versions), Intel, and TI C6000 DSP. Processor speeds typically range from 400 MHz to 2+ Ghz. Some arrangements employ ARM NEON technology, which provides a Single Instruction, Multiple Data (SIMD) extension for a class of ARM processors.
The processor 102 runs an operating system, and runs application programs and, manages the various functions of the device. The processor 102 may include or be coupled to a read-only memory (ROM) (not shown), which stores an operating system (e.g., a “high-level” operating system, a “real-time” operating system, a mobile operating system, or the like or combination thereof) and other device firmware that runs on the system.
The system also includes a volatile memory 104 electrically coupled to bus 100 (also referred to as dynamic memory). The volatile memory 104 may include, for example, a type of random access memory (RAM). Although not shown, the system includes a memory controller that controls the flow of data to and from the volatile memory 104. Current systems typically have around 500 MiB of dynamic memory, and around 8 KiB of stack.
The depicted embodiment also includes a storage memory 106 connected to the bus. The storage memory 106 typically includes one or more non-volatile semiconductor memory devices such as ROM, EPROM and EEPROM, NOR or NAND flash memory, or the like or combinations thereof, and may also include alternative storage devices, such as, for example, magnetic or optical disks. The storage memory 106 is used to store one or more items of software. Software can include system software, application software, middleware, one or more computer files (e.g., one or more data files, configuration files, library files, archive files, etc.), one or more software components, or the like or stack or other combination thereof.
Examples of system software include operating systems (e.g., including one or more high-level operating systems, real-time operating systems, mobile operating systems, or the like or combination thereof), one or more kernels, one or more device drivers, firmware, one or more utility programs (e.g., that help to analyze, configure, optimize, maintain, etc., one or more components of the system), and the like. Suitable operating systems include but are not limited to Windows (multiple versions), Linux, iOS, Quadros, and Android.
Compilers used to convert higher level software instructions into executable code for these devices include: Microsoft C/C++, GNU, ARM, and Clang/LLVM. Examples of compilers used for ARM architectures are RVDS 4.1+, DS-5, CodeSourcery, and Greenhills Software.
Also connected to the bus 100 is an imager interface 108. The imager interface 108 connects one or more one or more imagers 110 to bus 100. The imager interface supplies control signals to the imagers to capture frames and communicate them to other components on the bus. In some implementations, the imager interface also includes an image processing DSP that provides image processing functions, such as sampling and preparation of groups of pixel regions from the 2D sensor array (blocks, scanlines, etc.) for further image processing. The DSP in the imager interface may also execute other image pre-processing, recognition or optical code reading instructions on these pixels. The imager interface 108 also includes memory buffers for transferring image and image processing results to other components on the bus 100.
Though one imager 110 is shown in FIG. 6, the system may have additional imagers. Each imager is comprised of a digital image sensor (e.g., CMOS or CCD) or like camera having a two-dimensional array of pixels. The sensor may be a monochrome or color sensor (e.g., one that employs a Bayer arrangement), and operate in a rolling and/or global shutter mode. Examples of these imagers include model EV76C560 CMOS sensor offered by e2v Technologies PLC, Essex, England, and model MT9V022 sensor offered by On Semiconductor of Phoenix, Ariz. Each imager 110 captures an image of its view or views of a view volume of the imager, as illuminated by an illumination source. The imager captures at least one view. Plural views (e.g., view1 112 and view2 114) are captured by a single imager in systems where optical elements, such as mirrors and beam splitters are used to direct light reflected from different sides of an object in the view volume to the imager.
Also coupled to the bus 100 is an illumination driver 116 that controls and illumination sources 118. Typical systems employ Light Emitting Diodes (LEDs) as illumination sources. In one typical configuration, red LEDs are paired with a monochrome camera. The illumination driver applies signals to the LEDs to turn them on in a controlled sequence (strobe them) in synchronization with capture by an imager or imagers. In another configuration, plural different color LEDs may also be used and strobed in a manner such that the imager(s) selectively capture images under illumination from different color LED or sets of LEDs. See, e.g., Patent Application Publication 2013-0329006, entitled COORDINATED ILLUMINATION AND IMAGE SIGNAL CAPTURE FOR ENHANCED SIGNAL DETECTION, and Ser. No. 14/836,878, entitled SENSOR-SYNCHRONIZED SPECTRALLY-STRUCTURED-LIGHT IMAGING which are hereby incorporated by reference. The latter captures images in plural different spectral bands beyond standard RGB color planes, enabling extraction of encoded information as well as object recognition based on pixel samples in more narrow spectral bands at, above and below the visible spectrum.
In another configuration, a broadband illumination source is flashed and image pixels in different bands, e.g., RGB, are captured with a color image sensor (e.g., such as one with a Bayer arrangement). The illumination driver may also strobe different sets of LED that are arranged to illuminate particular views within the view volume (e.g., so as to capture images of different sides of an object in the view volume).
The illustrated system also includes at least one communications module 118, each comprised of circuitry to transmit and receive data through a wired or wireless link to another device or network. One example of a communication module is a connector that operates in conjunction with software or firmware in the system to function as a serial port (e.g., RS232), a Universal Serial Bus (USB) port, and an IR interface. Another example of a communication module is a universal interface driver application specific integrated circuit (UIDA) that supports plural different host interface protocols, such as RS-232C, IBM46XX, or Keyboard Wedge interface. The system may also have communication modules to support other communication modes, such as USB, Ethernet, Bluetooth, Wifi, infrared (e.g., IrDa) or RFID communication.
Also connected to the bus 100 is a sensor interface module 122 communicatively coupled to one or more sensors 124. Some configurations have data capture sensors such as RFID or NFC readers or the like for reading codes from products.
The sensor interface module 122 may also optionally include cache or other local memory device (e.g., volatile memory, non-volatile memory or a combination thereof), DMA channels, one or more input buffers, one or more output buffers to store and communicate control and data signals to and from the sensor.
Finally, the system may be equipped with a variety of user input/output devices, connected to the bus 100 via a corresponding user I/O interface 126. Examples include indicator lights or display 128 and/or speaker 130. The system may also have a display and display controller connecting the display device to the bus 100. For I/O capability, the system has a touch screen for both display and user input.
FIG. 7 is a diagram illustrating a processing architecture for controlling visual recognition units within an inspection system. The processing architecture comprises a controller and recognition units. Each of these elements is a logical processing module implemented as a set of instructions executing on a processor in the system, or implemented in an array of digital logic gates, such as a Field Programmable Gate Array (FPGA) or Application Specific Integrated Circuit (ASIC). Each of the modules may operate within a single component (such as a processor, FPGA or ASIC), within cores of a plural core processor, or within two or more components that are interconnected via the bus 100 or other interconnect between components in the system hardware of FIG. 6. The implementer may create the instructions of each module in a higher level programming language, such as C/C++ and then port them to the particular hardware components in the architecture of choice.
In this example, we show a controller and three recognition units. There may be more or less of each in a given implementation. The controller 140 is responsible for sending recognition tasks to recognition units (142, 144 and 146), getting the results of those tasks, and then executing logic to determine the identifier to be sent to a central control computer. The controller module 140 communicates with the recognition units (142-146) via communication links 148, 150, 152. The manner in which the controller communicates with the recognition units depend on the implementation of each. To communicate with an FPGA, the controller communicates through a memory buffer, e.g., via the bus 100.
To communicate among software processes, the controller process employs inter-process communication (IPC). The particular form of IPC depends in part on the operating system executing in the scanner. For a Unix OS or Unix derivatives, IPC may be implemented with sockets.
Finally, controller and recognition units may be implemented within a single software process in which communication among software routines within the process is implemented with shared memory. Within a process, the software program of each recognition units may be executed serially and report its results back to the controller. Recognition units may also be executed as separate threads of execution. The operating system manages pre-emptive multi-tasking and multi-threading (if employed) for software processes and threads. The operating system also manages concurrent execution on processes on processors, in some implementations in which more than one processor is available for the controller, recognition units, and other image processing.
A recognition unit executes instructions on an image block provided to it to recognize an object or objects in the image block and return a corresponding recognition result. For optical codes like barcodes and digital watermark data carriers (sometimes referred to as “Digimarc Barcodes”), the recognition result comprises the digital payload extracted from the carrier, which may be formatted as a string of binary or M-ary symbols or converted to a higher level code such as a GTIN data structure in accordance with the GS1 specification for GTINs. Recognition units that perform optical code reading include, for example, optical code readers for 1-dimensional optical codes like UPC, EAN, Code 39, Code 128 (including GS1-128), stacked codes like DataBar stacked and PDF417, or 2-dimensional optical codes like a DataMatrix, QR code or MaxiCode.
FIG. 8 is diagram illustrating software modules 160, 162 that operate on a sequence of image frames 164 to detect and extract digital payloads from images of objects within the frames. Controller 160 is an example of a controller 140 in the architecture of FIG. 7. This diagram illustrates the interaction of a controller with one particular implementation of a recognition unit 162. In this instance, the controller 160 and recognition unit are software processes. In one embodiment, they execute on distinct processors within the scanner. For example, they execute either in the separate processors 102, 102a, or the controller executes in processor 102 and recognition unit executes in a processor within the imager interface 108 (e.g., DSP). In another embodiment, they execute within the same processor, e.g., processor 102, or within a DSP in the imager interface 108.
In still another embodiment, the controller executes in processor 102, and the instructions of the recognition unit are implemented within an FPGA or ASIC, which is part of another component, such as the imager interface, or a separate component on bus 100.
The software process of the recognition unit 162 performs a form of recognition that employs digital watermark decoding to detect and extract watermark payloads from encoded data tiles in the image frames 164. The term “frame” refers to a group of pixels read from a 2D sensor array for a time period in which a 2D image is captured on the sensor array. Recall that the sensor may operate in rolling shutter or global shutter mode. In some implementations, selected rows of the sensor array are sampled during a capture period and stored in a memory buffer (e.g., in the imager interface), which is accessed by the recognition unit(s). In others, an entire frame of all pixels in the sensor array are sampled and stored in a frame buffer, which is then accessed by the recognition unit(s). The group of pixels sampled from a frame may include plural views of the viewing volume, or a part of the viewing volume.
The recognition unit 162 has the following sub-modules of instructions: interface 166 and watermark processors 168, 170, 172. The interface comprises software code for receiving calls from the controlling and returning recognition results from shared memory of the software process of the recognition unit 162. Watermark processors are instances of watermark decoders.
When a container moves into the field of view of the camera, controller 160 invokes the recognition unit 162 on image frames containing the object. Via interface 166, the controller 160 calls the recognition unit 162, providing the frames 164 by supplying an address of or pointer to them in the memory of the scanner (image buffer in e.g., either volatile memory 104 or memory buffers in imager interface 108). It also provides other attributes, such as attributes of the view from which the frame originated.
The recognition unit proceeds to invoke a watermark processor 168-172 on frames in serial fashion. Watermark processors 1-3 operate on frames 1-3, and then process flow returns back to watermark processor 1 for frame 4, and so on. This is just one example of process flow in a serial process flow implementation. Alternatively, watermark processors may be executed concurrently within a process as threads, or executed as separate software processes, each with an interface and watermark processor instance.
The recognition unit 162 provides the extracted payload results, if any, for each frame via communication link as described above. The controller analyzes the results from the recognition unit and other recognition units and determines when and what to report to the POS terminal. Each watermark processor records in shared memory of the recognition unit 162 its result for analyzing the image block assigned to it. This result is a no detect, a successful read result along with decoded payload, or payloads (in the event that plural watermark payloads are detected within a frame). Optionally the watermark processor provides orientation parameters of the decoded payload, which provide geometric orientation and/or position of the tile or tiles from which the payload is decoded.
FIGS. 12A and 12B illustrate image portions 180, 182 in different frames captured from a field of view of an imager. An object 184 is moving through this field of view in these frames. Here, we use the phrase, “image portion,” to reflect that the image portion of a frame is not necessarily co-extensive with the entire pixel array of an imager. As noted, an imager may capture plural views of the object 184 per frame, and the image portion may correspond to one particular view of plural different views captured by the image sensor array for a frame. Alternatively, it may encompass plural views imaged within a frame. Also, frames from different imagers may be composited, in which case, the image portion may include a portion of frames composited from different imagers. Nevertheless, FIG. 9A depicts an image block from a frame at a first capture time, and FIG. 9B represents an image block from a second, later capture time.
For sake of illustration, we use an example where the imager has a frame capture rate of 100 frames per second. Thus, a new frame is available for sampling as fast as every 10 ms. The rate at which the controller provides frames or portions of frames to each recognition unit may not be as high as the frame rate. Thus, the frames illustrated here need not be strictly adjacent in a video sequence from the sensor, but are within a time period in which an object 184 moves through the field of view of the scanner. The object movement may be from a conveyor or other material handling equipment that moves a container through a field of view of the imager. Image portion 180 at frame time, T1, includes an image captured of at least a first part of object 184. This object has encoded data tiles having a first payload 186a, 186b, and encoded data tile 188a having a second payload. Image block 182, at a later frame time, T2, depicts that the object 184 has moved further within the field of view of the scanner. At T2, more tiles are captured, such as 186c having the same payload as 186a and 186b, and 188b having the same payload as 188a. 
Signal Encoder and Decoder
FIG. 10 is a block diagram of a signal encoder for encoding a digital payload signal into an image signal. FIG. 11 is a block diagram of a compatible signal decoder for extracting the digital payload signal from an image signal.
While the signal encoder and decoder may be used for communicating a data channel for many applications, the objective for use in physical objects is robust signal communication through images formed on and captured from these objects. Signal encoders and decoders, like those in the Digimarc Barcode Platform from Digimarc Corporation, communicate auxiliary data in a data carrier (watermark) within image content. Encoding and decoding is applied digitally, yet the signal survives digital to analog transformation and analog to digital transformation. For example, the encoder generates a modulated image that is converted to a rendered form, such as a printed label. Prior to decoding, a receiving device has an imager to capture the modulated signal, convert it to an electric signal, which is digitized and then processed by the decoder.
Inputs to the signal encoder include a host image 220 and auxiliary data payload 222. The objectives of the encoder include encoding a robust signal with desired payload capacity per unit of host signal (e.g., the spatial area of a two-dimensional tile), while maintaining perceptual quality. In some cases, there may be very little variability or presence of a host signal. In this case, there is little host interference on the one hand, yet little host content in which to mask the presence of the data channel within an image. Some examples include a package design that is devoid of much image variability (e.g., a single, uniform color). See, e.g., patent applications Ser. No. 14/725,399, filed May 29, 2015, and 62/303,320, filed Mar. 3, 2016, both entitled SPARSE MODULATION FOR ROBUST SIGNALING AND SYNCHRONIZATION and both incorporated herein by reference.
The auxiliary data payload 222 includes the variable data information to be conveyed in the data channel, possibly along with other protocol data used to facilitate the communication. The protocol of the auxiliary data encoding scheme comprises the format of the auxiliary data payload, error correction coding schemes, payload modulation methods (such as the carrier signal, spreading sequence, encoded payload scrambling or encryption key), signal structure (including mapping of modulated signal to embedding locations within a tile), error detection in payload (CRC, checksum, etc.), perceptual masking method, host signal insertion function (e.g., how auxiliary data signal is embedded in or otherwise combined with host image signal in a package or label design), and synchronization method and signals.
The protocol defines the manner in which the signal is structured and encoded for robustness, perceptual quality or data capacity. For a particular application, there may be a single protocol, or more than one protocol, depending on application requirements. Examples of multiple protocols include cases where there are different versions of the channel, different channel types (e.g., several digital watermark layers within a host). Different versions may employ different robustness encoding techniques or different data capacity. Protocol selector module 224 determines the protocol to be used by the encoder for generating a data signal. It may be programmed to employ a particular protocol depending on the input variables, such as user control, application specific parameters, or derivation based on analysis of the host signal.
Perceptual analyzer module 226 analyzes the input host signal to determine parameters for controlling signal generation and embedding, as appropriate. It is not necessary in certain applications, while in others it may be used to select a protocol and/or modify signal generation and embedding operations. For example, when encoding in host color images that will be printed, the perceptual analyzer 156 is used to ascertain color content and masking capability of the host image. The output of this analysis, along with the rendering method (printing device) and rendered output form (e.g., ink and substrate) is used to control auxiliary signal encoding in particular color channels (e.g., one or more channels of process inks, Cyan, Magenta, Yellow, or Black (CMYK) or spot colors), perceptual models, and signal protocols to be used with those channels. Please see, e.g., our work on visibility and color models used in perceptual analysis in our U.S. applications Ser. No. 14/616,686 (now published as US 2015-0156369), Ser. No. 14/588,636 (now published as US 2015-0187039), and Ser. No. 12/337,029 (now published as US 2010-0150434), and Ser. No. 13/975,919, and in U.S. Pat. No. 7,352,878, which are hereby incorporated by reference.
The perceptual analyzer module 226 also computes a perceptual model, as appropriate, to be used in controlling the modulation of a data signal onto a data channel within image content as described below.
The signal generator module 228 operates on the auxiliary data and generates a data signal according to the protocol. It may also employ information derived from the host signal, such as that provided by perceptual analyzer module 226, to generate the signal. For example, the selection of data code signal and pattern, the modulation function, and the amount of signal to apply at a given embedding location may be adapted depending on the perceptual analysis, and in particular on the perceptual model and perceptual mask that it generates. Please see below and the incorporated patent documents for additional aspects of this process.
Embedder module 230 takes the data signal and modulates it into an image by combining it with the host image. The operation of combining may be an entirely digital signal processing operation, such as where the data signal modulates the host signal digitally, may be a mixed digital and analog process or may be purely an analog process (e.g., where rendered output images, with some signals being modulated data and others being host image content, such as the various layers of a package design file).
There are a variety of different functions for combining the data and host in digital operations. One approach is to adjust the host signal value as a function of the corresponding data signal value at an embedding location, which is limited or controlled according to the perceptual model and a robustness model for that embedding location. The adjustment may be altering the host image by adding a scaled data signal or multiplying by a scale factor dictated by the data signal value corresponding to the embedding location, with weights or thresholds set on the amount of the adjustment according to the perceptual model, robustness model, and available dynamic range. The adjustment may also be altering by setting the modulated host signal to a particular level (e.g., quantization level) or moving it within a range or bin of allowable values that satisfy a perceptual quality or robustness constraint for the encoded data.
As detailed further below, the signal generator produces a data signal with data elements that are mapped to embedding locations in a tile. These data elements are modulated onto the host image at the embedding locations. A tile is a pattern of embedding locations. The tile derives its name from the way in which it is repeated in contiguous blocks of a host signal, but it need not be arranged this way. In image-based encoders, we commonly use tiles in the form of a two dimensional array (e.g., 128 by 128, 256 by 256, 512 by 512) of embedding locations. The embedding locations correspond to host signal samples at which an encoded signal element is embedded in an embedding domain, such as a spatial domain (e.g., pixels at a spatial resolution), frequency domain (frequency components at a frequency resolution), or some other feature space. We sometimes refer to an embedding location as a bit cell, referring to a unit of data (e.g., an encoded bit or chip element) encoded within a host signal at the location of the cell. Again please see the documents incorporated herein for more information on variations for particular type of media.
The operation of combining may include one or more iterations of adjustments to optimize the modulated host for perceptual quality or robustness constraints. One approach, for example, is to modulate the host image so that it satisfies a perceptual quality metric as determined by perceptual model (e.g., visibility model) for embedding locations across the signal. Another approach is to modulate the host image so that it satisfies a robustness metric across the signal. Yet another is to modulate the host image according to both the robustness metric and perceptual quality metric derived for each embedding location. The incorporated documents provide examples of these techniques. Below, we highlight a few examples. See, e.g., U.S. application Ser. No. 13/975,919. See also, U.S. application Ser. No. 14/588,636, entitled FULL-COLOR VISIBILITY MODEL USING CSF WHICH VARIES SPATIALLY WITH LOCAL LUMINANCE (published as 2015-0187039), and U.S. Provisional application 62/152,745, entitled DATA HIDING USING EQUAL VISIBILITY EMBEDDING FOR COLOR DESIGNS, filed Apr. 24, 2015, which are hereby incorporated by reference.
For color images, the perceptual analyzer generates a perceptual model that evaluates visibility of an adjustment to the host by the embedder and sets levels of controls to govern the adjustment (e.g., levels of adjustment per color direction, and per masking region). This may include evaluating the visibility of adjustments of the color at an embedding location (e.g., units of noticeable perceptual difference in color direction in terms of CIE Lab values), Contrast Sensitivity Function (CSF), spatial masking model (e.g., using techniques described by Watson in US Published Patent Application No. US 2006-0165311 A1, which is incorporated by reference herein), etc. One way to approach the constraints per embedding location is to combine the data with the host at embedding locations and then analyze the difference between the encoded host with the original. The perceptual model then specifies whether an adjustment is noticeable based on the difference between a visibility threshold function computed for an embedding location and the change due to embedding at that location. The embedder then can change or limit the amount of adjustment per embedding location to satisfy the visibility threshold function. Of course, there are various ways to compute adjustments that satisfy a visibility threshold, with different sequence of operations. See, e.g., our U.S. application Ser. Nos. 14/616,686, 14/588,636 and 13/975,919, Patent Application Publication 20100150434, and U.S. Pat. No. 7,352,878, already incorporated herein.
The embedder also computes a robustness model. The computing of a robustness model may include computing a detection metric for an embedding location or region of locations. The approach is to model how well the decoder will be able to recover the data signal at the location or region. This may include applying one or more decode operations and measurements of the decoded signal to determine how strong or reliable the extracted signal. Reliability and strength may be measured by comparing the extracted signal with the known data signal. Below, we detail several decode operations that are candidates for detection metrics within the embedder. One example is an extraction filter which exploits a differential relationship to recover the data signal in the presence of noise and host signal interference. At this stage of encoding, the host interference is derivable by applying an extraction filter to the modulated host. The extraction filter models data signal extraction from the modulated host and assesses whether the differential relationship needed to extract the data signal reliably is maintained. If not, the modulation of the host is adjusted so that it is.
Detection metrics may be evaluated such as by measuring signal strength as a measure of correlation between the modulated host and variable or fixed data components in regions of the host, or measuring strength as a measure of correlation between output of an extraction filter and variable or fixed data components. Depending on the strength measure at a location or region, the embedder changes the amount and location of host signal alteration to improve the correlation measure. These changes may be particularly tailored so as to establish relationships of the data signal within a particular tile, region in a tile or bit cell pattern of the modulated host. To do so, the embedder adjusts bit cells that violate the relationship so that the relationship needed to encode a bit (or M-ary symbol) value is satisfied and the thresholds for perceptibility are satisfied. Where robustness constraints are dominant, the embedder will exceed the perceptibility threshold where necessary to satisfy a desired robustness threshold.
The robustness model may also model distortion expected to be incurred by the modulated host, apply the distortion to the modulated host, and repeat the above process of measuring detection metrics and adjusting the amount of alterations so that the data signal will withstand the distortion. See, e.g., earlier-cited patent application Ser. Nos. 14/616,686, 14/588,636 and 13/975,919 for image related processing.
This modulated host is then output as an output image signal 232, with a data channel encoded in it. The operation of combining also may occur in the analog realm where the data signal is transformed to a rendered form, such as a layer of ink or coating applied by a commercial press to a substrate. Another example is a data signal that is overprinted as a layer of material, engraved in, or etched onto a substrate, where it may be mixed with other signals applied to the substrate by similar or other marking methods. In these cases, the embedder employs a predictive model of distortion and host signal interference, and adjusts the data signal strength so that it will be recovered more reliably. The predictive modeling can be executed by a classifier that classifies types of noise sources or classes of host image and adapts signal strength and configuration of the data pattern to be more reliable to the classes of noise sources and host image signals that the encoded data signal is likely to be encounter or be combined with.
The output 232 from the embedder signal typically incurs various forms of distortion through its distribution or use. For printed objects, this distortion occurs through rendering an image with the encoded signal in the printing process, and subsequent scanning back to a digital image via a camera or like image sensor.
Turning to FIG. 11, the signal decoder receives an encoded host signal 240 and operates on it with one or more processing stages to detect a data signal, synchronize it, and extract data. This signal decoder corresponds to a type of recognition unit in FIG. 7 and watermark processor in FIG. 8.
The decoder is paired with an input device in which a sensor captures an analog form of the signal and an analog to digital converter converts it to a digital form for digital signal processing. Though aspects of the decoder may be implemented as analog components, e.g., such as preprocessing filters that seek to isolate or amplify the data channel relative to noise, much of the decoder is implemented as digital signal processing modules that implement the signal processing operations within a scanner. As noted, these modules are implemented as software instructions executed within the scanner, an FPGA, or ASIC.
The detector 242 is a signal processing module that detects presence of the data channel. The incoming signal is referred to as a suspect host because it may not have a data channel or may be so distorted as to render the data channel undetectable. The detector is in communication with a protocol selector 244 to get the protocols it uses to detect the data channel. It may be configured to detect multiple protocols, either by detecting a protocol in the suspect signal and/or inferring the protocol based on attributes of the host signal or other sensed context information. A portion of the data signal may have the purpose of indicating the protocol of another portion of the data signal. As such, the detector is shown as providing a protocol indicator signal back to the protocol selector 244.
The synchronizer module 246 synchronizes the incoming signal to enable data extraction. Synchronizing includes, for example, determining the distortion to the host signal and compensating for it. This process provides the location and arrangement of encoded data elements within the host signal.
The data extractor module 248 gets this location and arrangement and the corresponding protocol and demodulates a data signal from the host. The location and arrangement provide the locations of encoded data elements. The extractor obtains estimates of the encoded data elements and performs a series of signal decoding operations.
As detailed in examples below and in the incorporated documents, the detector, synchronizer and data extractor may share common operations, and in some cases may be combined. For example, the detector and synchronizer may be combined, as initial detection of a portion of the data signal used for synchronization indicates presence of a candidate data signal, and determination of the synchronization of that candidate data signal provides synchronization parameters that enable the data extractor to apply extraction filters at the correct orientation, scale and start location of a tile. Similarly, data extraction filters used within data extractor may also be used to detect portions of the data signal within the detector or synchronizer modules. The decoder architecture may be designed with a data flow in which common operations are re-used iteratively, or may be organized in separate stages in pipelined digital logic circuits so that the host data flows efficiently through the pipeline of digital signal operations with minimal need to move partially processed versions of the host data to and from a shared memory unit, such as a RAM memory.
Signal Generator
FIG. 12 is a flow diagram illustrating operations of a signal generator. Each of the blocks in the diagram depict processing modules that transform the input auxiliary data (e.g., GTIN or other item identifier) into a digital payload data signal structure. For a given protocol, each block provides one or more processing stage options selected according to the protocol. In processing module 300, the auxiliary data payload is processed to compute error detection bits, e.g., such as a Cyclic Redundancy Check, Parity, check sum or like error detection message symbols. Additional fixed and variable messages used in identifying the protocol and facilitating detection, such as synchronization signals may be added at this stage or subsequent stages.
Error correction encoding module 302 transforms the message symbols of the digital payload signal into an array of encoded message elements (e.g., binary or M-ary elements) using an error correction method. Examples include block codes, BCH, Reed Solomon, convolutional codes, turbo codes, etc.
Repetition encoding module 304 repeats and concatenates the string of symbols from the prior stage to improve robustness. For example, certain message symbols may be repeated at the same or different rates by mapping them to multiple locations within a unit area of the data channel (e.g., one unit area being a tile of bit cells, as described further below).
Repetition encoding may be removed and replaced entirely with error correction coding. For example, rather than applying convolutional encoding (1/3 rate) followed by repetition (repeat three times), these two can be replaced by convolution encoding to produce a coded payload with approximately the same length.
Next, carrier modulation module 306 takes message elements of the previous stage and modulates them onto corresponding carrier signals. For example, a carrier might be an array of pseudorandom signal elements, with equal number of positive and negative elements (e.g., 16, 32, 64 elements), or other waveform. We elaborate further on signal configurations below.
Mapping module 308 maps signal elements of each modulated carrier signal to locations within the channel. In the case where a digital host signal is provided, the locations correspond to embedding locations within the host signal. The embedding locations may be in one or more coordinate system domains in which the host signal is represented within a memory of the signal encoder. The locations may correspond to regions in a spatial domain, temporal domain, frequency domain, or some other transform domain. Stated another way, the locations may correspond to a vector of host signal features, which are modulated to encode a data signal within the features.
Mapping module 308 also maps a synchronization signal to embedding locations within the host signal, for embodiments employing an explicit synchronization signal. An explicit synchronization signal is described further below.
To accurately recover the payload, the decoder must be able to extract estimates of the coded bits at the embedding locations within each tile. This requires the decoder to synchronize the image under analysis to determine the embedding locations. For images, where the embedding locations are arranged in two dimensional blocks within a tile, the synchronizer determines rotation, scale and translation (origin) of each tile. This may also involve approximating the geometric distortion of the tile by an affine transformation that maps the embedded signal back to its original embedding locations.
To facilitate synchronization, the auxiliary signal may include an explicit or implicit synchronization signal. An explicit synchronization signal is an auxiliary signal separate from the encoded payload that is embedded with the encoded payload, e.g., within the same tile). An implicit synchronization signal is a signal formed with the encoded payload, giving it structure that facilitates geometric/temporal synchronization. Examples of explicit and implicit synchronization signals are provided in our previously cited U.S. Pat. Nos. 6,614,914, and 5,862,260.
In particular, one example of an explicit synchronization signal is a signal comprised of a set of sine waves, with pseudo-random phase, which appear as peaks in the Fourier domain of the suspect signal. See, e.g., U.S. Pat. Nos. 6,614,914, and 5,862,260, describing use of a synchronization signal in conjunction with a robust data signal. Also see U.S. Pat. No. 7,986,807, which is hereby incorporated by reference.
Our US Publication 20120078989, which is hereby incorporated by reference, provides additional methods for detecting an embedded signal with this type of structure and recovering rotation, scale and translation from these methods.
Examples of implicit synchronization signals, and their use, are provided in U.S. Pat. Nos. 6,614,914 and 5,862,260, as well as U.S. Pat. Nos. 6,625,297 and 7,072,490, and U.S. application Ser. No. 14/724,729, which are hereby incorporated by reference.
Signal Embedding in Host
FIG. 13 is a diagram illustrating embedding of an auxiliary signal into host signal. As shown, the inputs are a host signal block (e.g., blocks of a host digital image, such as container or label artwork) (320) and an encoded auxiliary signal (322), which is to be inserted into the signal block. The encoded auxiliary signal may include an explicit synchronization component, or the encoded payload may be formulated to provide an implicit synchronization signal. Processing block 324 is a routine of software instructions or equivalent digital logic configured to insert the mapped signal(s) into the host by adjusting the corresponding host signal sample(s) at an embedding location according to the value of the mapped signal element. For example, the mapped signal is added/subtracted from corresponding a sample value, with scale factor and threshold from the perceptual model or like mask controlling the adjustment amplitude. In implementations with an explicit synchronization signal, the encoded payload and synchronization signals may be combined and then added, or added separately with separate mask coefficients to control the signal amplitude independently.
Applying the method of FIG. 12, the product or label identifier (e.g., in GTIN format) are formatted into a binary sequence, which is encoded and mapped to the embedding locations of a tile. For sake of illustration, we describe an implementation of a tile having 256 by 256 embedding locations, where the embedding locations correspond to spatial domain embedding locations within an image. In particular, the spatial locations correspond to pixel samples at a configurable spatial resolution, such as 100-400 DPI. In this example, we will explain the case where the spatial resolution of the embedded signal is 300 DPI, for an embodiment where the resulting image with encode data is printed on a package or label material, such as a paper, plastic or like substrate. The payload is repeated in contiguous tiles each comprised of 256 by 256 of embedding locations. With these embedding parameters, an instance of the payload is encoded in each tile. The physical size of a tile depends on the size of the elemental encoding unit being used (e.g., a single pixel, or a square array of pixels—such as 4×4). Depending on the parameters chosen, each printed tile may range from less than half an inch on a side, to an inch or more. The particular parameters are selected in accordance with the constraints of the particular environment (e.g., reading distance and imaging resolution). Desirably, multiple tiles are redundantly arrayed across the artwork, providing added robustness. An alternative to achieving desired payload capacity is to encode a portion of the payload in smaller tiles, e.g., 128 by 128, and use a protocol indicator to specify the portion of the payload conveyed in each 128 by 128 tile. Erasure codes may be used to convey different payload components per tile and then assemble the components in the decoder, as elaborated upon below.
Following the construction of the payload, error correction coding is applied to the binary sequence. This implementation applies a convolutional coder at rate 1/4, which produces an encoded payload signal of 4096 bits. Each of these bits is modulated onto a binary antipodal, pseudorandom carrier sequence (−1, 1) of length 16, e.g., by multiplying or XORing the payload bit with the binary equivalent of chip elements in its carrier to yield 4096 modulated carriers, for a signal comprising 65,536 elements. These elements map to the 65,536 embedding locations in each of the 256 by 256 tiles.
An alternative embodiment, for robust encoding on packaging employs tiles of 128 by 128 embedding locations. Through convolutional coding of an input payload at rate 1/3 and subsequent repetition coding, an encoded payload of 1024 bits is generated. Each of these bits is modulated onto a similar carrier sequence of length 16, and the resulting 16,384 signal elements are mapped to the 16,384 embedding locations within the 128 by 128 tile.
There are several alternatives for mapping functions to map the encoded payload to embedding locations. In one, these elements have a pseudorandom mapping to the embedding locations. In another, they are mapped to bit cell patterns of differentially encoded bit cells as described in Ser. No. 14/724,729, incorporated above. In the latter, the tile size may be increased to accommodate the differential encoding of each encoded bit in a pattern of differential encoded bit cells, where the bit cells corresponding to embedding locations at a target resolution (e.g., 300 DPI).
Our patent applications Ser. No. 14/725,399 and 62/303,320, incorporated above, describe methods for inserting auxiliary signals in areas of package and label designs that have little host image variability. These methods are particularly useful for labels.
For an explicit synchronization signal, the mapping function maps a discrete digital image of the synchronization signal to the host image block. For example, where the synchronization signal comprises a set of Fourier magnitude peaks or sinusoids with pseudorandom phase, the synchronization signal is generated in the spatial domain in a block size coextensive with the 256 by 256 tile (or other tile size, e.g., 128 by 128) at target embedding resolution.
Various detailed examples of encoding protocols and processing stages of these protocols are provided in our prior work, such as our U.S. Pat. Nos. 6,614,914, 5,862,260, and 6,674,876, which are hereby incorporated by reference, and US Patent Publications 20100150434 and Ser. No. 14/725,399, previously incorporated. More background on signaling protocols, and schemes for managing compatibility among protocols, are provided in U.S. Pat. No. 7,412,072, which is hereby incorporated by reference.
One signaling approach, which is detailed in U.S. Pat. Nos. 6,614,914, and 5,862,260, is to map elements to pseudo-random locations within a channel defined by a domain of a host signal. See, e.g., FIG. 9 of U.S. Pat. No. 6,614,914. In particular, elements of a watermark signal are assigned to pseudo-random embedding locations within an arrangement of sub-blocks within a block (referred to as a “tile”). The elements of this watermark signal correspond to error correction coded bits output from an implementation of stage 304 of FIG. 12. These bits are modulated onto a pseudo-random carrier to produce watermark signal elements (block 306 of FIG. 12), which in turn, are assigned to the pseudorandom embedding locations within the sub-blocks (block 308 of FIG. 12). An embedder module modulates this signal onto a host signal by increasing or decreasing host signal values at these locations for each error correction coded bit according to the values of the corresponding elements of the modulated carrier signal for that bit.
While the watermark signal is most commonly integrated into the artwork, and is printed with the same inks as are used to print the artwork, in other embodiments this need not be the case. One such arrangement prints a watermark pattern in an ink (e.g., a varnish) that seems transparent to human inspection but that actually effects a narrowband modulation within the visible light spectrum, and can be discerned by computer analysis of captured imagery. Details of such arrangements are provided in our patent application 62/263,369, filed Dec. 4, 2015, entitled DIGITAL WATERMARKING AND DATA HIDING WITH NARROW-BAND ABSORPTION MATERIALS, which is incorporated herein by reference. Another such arrangement employs an ink that is transparent (clear) to visible light but absorbs wavelengths in the ultraviolet or infrared range. Because such watermarks employ inks not otherwise used for the packaging artwork, they can be applied separately—either before or after printing of the visible artwork.
Combinations of such arrangements can also be employed. For example, a GTIN identifier can be encoded in a watermark integrated with, and printed with, the packaging artwork. And a second identifier (e.g., a label identifier) can be applied by the method of just-cited application 62/263,369.
If two watermarks are applied separately, they can be applied so as to be mis-aligned (e.g., with a spatial offset between their respective tile origins). If printed on rolling presses, such offset can be randomized by having the two patterns applied by rollers of slightly different diameters. Due to varying diameters of such rollers, miles of material may be printed before the two rollers return to an original relative alignment. Such randomization of the spatial offset effects a form of virtual serialization, by which one instance of a package can be optically identified, and distinguished from another instance of the same package. For additional details on such technology, please see our application Ser. No. 14/446,068 (now published as US Patent Application 2015-0016664), which is incorporated herein by reference.
Signal Decoding
FIG. 14 is a flow diagram illustrating a method for decoding a payload signal from a captured image frame. This method is a particular embodiment of a recognition unit of FIG. 7, and a watermark processor of FIG. 8. Implementations of recognition unit and watermark processors available from Digimarc Corporation include:
Digimarc Mobile Software Development Kit; and
Digimarc Embedded Systems SDK.
The Embedded Systems SDK is the one typically integrated into machine vision systems for manufacturing line inspection.
Corresponding encoder embodiments available from Digimarc Corporation include:
Digimarc Barcode SDKs
Digimarc Barcode Plugin
Returning to FIG. 14, the frames are captured at a resolution preferably near the resolution at which the auxiliary signal has been encoded within the original image (e.g., 300 DPI). An image up-sampling or down-sampling operation may be performed to convert the image frames supplied by the imager to a target resolution for further decoding.
The resulting image blocks supplied to the decoder from these frames may potentially include an image with the payload. At least some number of tiles of encoded signal may be captured within the field of view, if an object portion with encoded data is being imaged. Otherwise, no encoded tiles will be present. The objective, therefore, is to determine as efficiently as possible whether encoded tiles are present.
In the initial processing of the decoding method, it is advantageous to select frames and blocks within frames that have image content that are most likely to contain the encoded payload. From the image passed to the decoder, the decoder selects image blocks for further analysis. The block size of these blocks is set large enough to span substantially all of a complete tile of encoded payload signal, and preferably a cluster of neighboring tiles.
For more on block selection, please see co-pending U.S. application Ser. No. 14/332,739, entitled FEATURE-BASED WATERMARK LOCALIZATION IN DIGITAL CAPTURE SYSTEMS (published as 20150030201), which is hereby incorporated by reference.
Please also see provisional application 62/174,454, entitled IMAGE BLOCK SELECTION FOR EFFICIENT TIME-LIMITED DECODING, which is hereby incorporated by reference, for more on block selection where processing is time is more limited.
The first stage of the decoding process filters the image to prepare it for detection and synchronization of the encoded signal (402). The decoding process sub-divides the image into blocks and selects blocks for further decoding operations. For color images, a first filtering stage converts the input color image signal (e.g., RGB values) to a color channel or channels where the auxiliary signal has been encoded. See, e.g., 20100150434 for more on color channel encoding and decoding. For an image captured under red illumination by a monochrome scanner, the decoding process operates on this “red” channel sensed by the imager. Some imagers may pulse LEDs of different color to obtain plural color or spectral samples per pixel as described in our Patent Application Publication 2013-0329006, entitled COORDINATED ILLUMINATION AND IMAGE SIGNAL CAPTURE FOR ENHANCED SIGNAL DETECTION, which is hereby incorporated by reference.
A second filtering operation isolates the auxiliary signal from the host image. Pre-filtering is adapted for the auxiliary signal encoding format, including the type of synchronization employed. For example, where an explicit synchronization signal is used, pre-filtering is adapted to isolate the explicit synchronization signal for the synchronization process.
In some embodiments, the synchronization signal is a collection of peaks in the Fourier domain. Prior to conversion to the Fourier domain, the image blocks are pre-filtered. See, e.g., the LaPlacian pre-filter in U.S. Pat. No. 6,614,914. A window function is applied to the blocks and then a transform to the Fourier domain, applying an FFT. Another filtering operation is performed in the Fourier domain. See, e.g., pre-filtering options in U.S. Pat. Nos. 6,988,202, 6,614,914, 20120078989, which are hereby incorporated by reference.
For more on filters, also see U.S. Pat. No. 7,076,082, which is hereby incorporated by reference. This patent describes a multi-axis filter, e.g., an oct-axis filter. Oct axis compares a discrete image sample with eight neighbors to provide eight compare values (e.g., +1 for positive difference, −1 or negative difference), and sums the compare values. Different arrangements of neighbors and weights may be applied to shape the filter according to different functions. Another filter variant is a cross shaped filter, in which a sample of interest is compared with an average of horizontal neighbors and vertical neighbors, which are then similarly summed.
Next, synchronization process (404) is executed on a filtered block to recover the rotation, spatial scale, and translation of the encoded signal tiles. This process may employ a log polar method as detailed in U.S. Pat. No. 6,614,914 or least squares approach of 20120078989 to recover rotation and scale of a synchronization signal comprised of peaks in the Fourier domain. To recover translation, the phase correlation method of U.S. Pat. No. 6,614,914 is used, or phase estimation and phase deviation methods of 20120078989 are used.
Alternative methods perform synchronization on an implicit synchronization signal, e.g., as detailed in Ser. No. 14/724,729.
Next, the decoder steps through the embedding locations in a tile, extracting bit estimates from each location (406). This process applies, for each location, the rotation, scale and translation parameters, to extract a bit estimate from each embedding location (406). In particular, as it visits each embedding location in a tile, it transforms it to a location in the received image based on the affine transform parameters derived in the synchronization, and then samples around each location. It does this process for the embedding location and its neighbors to feed inputs to an extraction filter (e.g., oct axis or cross shaped). A bit estimate is extracted at each embedding location using filtering operations, e.g., oct axis or cross shaped filter (see above), to compare a sample at embedding locations with neighbors. The output (e.g., 1, −1) of each compare operation is summed to provide an estimate for an embedding location. Each bit estimate at an embedding location corresponds to an element of a modulated carrier signal.
The signal decoder estimates a value of each error correction encoded bit by accumulating the bit estimates from the embedding locations of the carrier signal for that bit (408). For instance, in the encoder embodiment above, error correction encoded bits are modulated over a corresponding carrier signal with 16 elements (e.g., multiplied by or XOR with a binary anti-podal signal). A bit value is demodulated from the estimates extracted from the corresponding embedding locations of these elements. This demodulation operation multiplies the estimate by the carrier signal sign and adds the result. This demodulation provides a soft estimate for each error correction encoded bit.
These soft estimates are input to an error correction decoder to produce the payload signal (410). For a convolutional encoded payload, a Viterbi decoder is used to produce the payload signal, including the checksum or CRC. For other forms of error correction, a compatible decoder is applied to reconstruct the payload. Examples include block codes, BCH, Reed Solomon, Turbo codes.
Next, the payload is validated by computing the check sum and comparing with the decoded checksum bits (412). The check sum matches the one in the encoder. For the example above, the decoder computes a CRC for a portion of the payload and compares it with the CRC portion in the payload.
At this stage, the payload is stored in shared memory of the decoder process. The recognition unit in which the decoder process resides returns it to the controller via its interface. This may be accomplished by various communication schemes, such as IPC, shared memory within a process, DMA, etc.
Concluding Remarks
Having described and illustrated the principles of our inventive work with reference to illustrative examples, it will be recognized that the technology is not so limited.
For example, while the first embodiments (e.g., food packaging technology) were described with reference to digital watermark technology, one or more of the components may be otherwise-marked, such as with an RFID chip, a barcode identifier, or any other known marking technology. Again, the marking can convey a GTIN or other identifier that is compared with the identifier read from a complementary component, to assure they correspond in an expected manner.
Similarly, while the second embodiments (e.g., detecting barcode labeling fraud) relied on digital watermarking to identify the retail product, such identification can be performed otherwise, e.g., with object recognition, optical character recognition, RFID chip, etc.
Reference was made to GTIN identifiers. GTIN is a standard, established by GS1. GS1 is a not-for-profit international organization that develops and maintains standards for supply and demand chains. With over a million member companies around the world, GS1—and its standards—are familiar to artisans in the field. The GTIN standard is detailed in a lengthy written specification (“GS1 General Specifications”) that is freely available from GS1 on its web site (presently at www<dot>gs1<dot>org/barcodes-eperfid-id-keys/gs1-general-specifications). The current version of this standard (Release 16.0, ratified January, 2016) is incorporated herein by reference.
Various object recognition (sometimes termed image fingerprinting) techniques are known. SIFT, SURF, ORB and CONGAS are some of the most popular algorithms. (SIFT, SURF and ORB are each implemented in the popular OpenCV software library, e.g., version 2.3.1. CONGAS is used by Google Goggles for that product's image recognition service, and is detailed, e.g., in Neven et al, “Image Recognition with an Adiabatic Quantum Computer I. Mapping to Quadratic Unconstrained Binary Optimization,” Arxiv preprint arXiv:0804.4457, 2008.) Still other image fingerprinting techniques are detailed in patent publications 20090282025, 20060104598, WO2012004626 and WO2012156774 (all by LTU Technologies of France).
In the detailed embodiments, the watermark payloads conveyed one or more literal identifiers, such as a GTIN identifier. This is not essential. In other embodiments, a watermark can convey an index value, which is used to access a corresponding entry in a data structure (e.g., database) containing further information. Thus, the index value CD398 may correspond to a database record containing the GTIN identifier 0087932602588. Such arrangement requires a database lookup to resolve the watermark payload, but allows greater amounts of information to be represented by the watermark payload.
Software instructions for implementing the detailed functionality can be authored by artisans without undue experimentation from the descriptions provided herein, e.g., written in C, C++, Visual Basic, Java, Python, Tcl, Perl, Scheme, Ruby, etc., in conjunction with associated data. Smartphones and other devices according to certain implementations of the present technology can include software modules for performing the different functions and acts.
Software and hardware configuration data/instructions are commonly stored as instructions in one or more data structures conveyed by tangible media, such as magnetic or optical discs, memory cards, ROM, etc., which may be accessed across a network. Some embodiments may be implemented as embedded systems—special purpose computer systems in which operating system software and application software are indistinguishable to the user (e.g., as is commonly the case in basic cell phones). The functionality detailed in this specification can be implemented in operating system software, application software and/or as embedded system software.
Different of the functionality can be implemented on different devices. For example, in a system in which a point of sale terminal communicates with a central store computer, different tasks can be performed exclusively by one device or the other, or execution can be distributed between the devices. Extraction of watermark information from imagery is one example of a process that can be distributed in such fashion. Thus, it should be understood that description of an operation as being performed by a particular device (e.g., a point of sale terminal) is not limiting but exemplary; performance of the operation by another device (e.g., a remote server), or shared between devices, is also expressly contemplated.
In like fashion, description of data being stored on a particular device is also exemplary; data can be stored anywhere: local device, remote device, in the cloud, distributed, etc.
Reference to “steganographic” means the marking is commonly imperceptible, i.e., it is not noticeable to a viewer examining watermarked packaging from a typical viewing distance (e.g., 20 inches) with retail lighting of conventional intensity.
This specification has discussed several different embodiments. It should be understood that the methods, elements and concepts detailed in connection with one embodiment can be combined with the methods, elements and concepts detailed in connection with other embodiments. While some such arrangements have been particularly described, many have not—due to the large number of permutations and combinations. Applicant similarly recognizes and intends that the methods, elements and concepts of this specification can be combined, substituted and interchanged—not just among and between themselves, but also with those known from the cited prior art. Moreover, it will be recognized that the detailed technology can be included with other technologies—current and upcoming—to advantageous effect. Implementation of such combinations is straightforward to the artisan from the teachings provided in this disclosure.
While this disclosure has detailed particular ordering of acts and particular combinations of elements, it will be recognized that other contemplated methods may re-order acts (possibly omitting some and adding others), and other contemplated combinations may omit some elements and add others, etc.
Although disclosed as complete systems, sub-combinations of the detailed arrangements are also separately contemplated (e.g., omitting various of the features of a complete system).
While certain aspects of the technology have been described by reference to illustrative methods, it will be recognized that apparatuses configured to perform the acts of such methods are also contemplated as part of applicant's inventive work. Likewise, other aspects have been described by reference to illustrative apparatus, and the methodology performed by such apparatus is likewise within the scope of the present technology. Still further, tangible computer readable media containing instructions for configuring a processor or other programmable system to perform such methods is also expressly contemplated.
The present specification should be read in the context of the cited references. Those references disclose technologies and teachings that the applicant intends be incorporated into embodiments of the present technology, and into which the technologies and teachings detailed herein be incorporated.
To provide a comprehensive disclosure, while complying with the statutory requirement of conciseness, applicant incorporates-by-reference each of the documents referenced herein. (Such materials are incorporated in their entireties, even if cited above in connection with specific of their teachings.) These references disclose technologies and teachings that can be incorporated into the arrangements detailed herein, and into which the technologies and teachings detailed herein can be incorporated. The reader is presumed to be familiar with such prior work.
The claims submitted with this application address just a small fraction of the patentable inventions disclosed herein. Applicant expects many more, and broader, claims will be issued from this patent family.
In view of the wide variety of embodiments to which the principles and features discussed above can be applied, it should be apparent that the detailed embodiments are illustrative only, and should not be taken as limiting the scope of the invention. Rather, applicant claims as the invention all such modifications as may come within the scope and spirit of the following claims and equivalents thereof.

## Claims

1. A method including:
at a checkout station in a retail store, capturing image data from packaging of products presented by customers for checkout;
processing first captured image data to produce map data identifying locations on first packaging where a steganographic watermark signal is detected, and locations where it is absent;
processing second captured image data to produce map data identifying locations on second packaging where a steganographic watermark signal is detected, and locations where it is absent; and
issuing a signal to store staff about the first product packaging, but not issuing a signal to the store staff about the second product packaging, because said map data produced from the first captured image data indicates a telltale void in the watermark signal that is consistent with application of a rectangular barcode label over the first packaging, whereas said map data produced from the second captured image data indicates a void in the watermark signal that is irregularly shaped, and thus not consistent with application of a rectangular barcode label over the second packaging.

2. The method of claim 1 in which the method is practiced at a self-checkout station in the retail store.

3. A checkout system in a retail store, including:
a first area for placement of customer-selected products to be purchased;
a second, bagging, area for bagging of said products;
a camera system disposed between the first and second areas;
a processor, configured by software instructions stored in a memory, to perform actions including:
processing image data, captured by the camera system from product packaging, to decode GTIN data encoded in a steganographic digital watermark on product packaging;
processing said image data to decode GTIN data encoded in a barcode on said product packaging;
comparing the GTIN data decoded from the steganographic digital watermark with the GTIN data decoded from the barcode;
determining, through said comparing, that there is a mismatch between GTIN data decoded from the barcode and GTIN data decoded from the steganographic digital watermark; and
issuing a signal to store staff, to alert said staff to the possible presence of an adhesive barcode label on said packaging.

4. A self-checkout system according to claim 3.

5. A checkout system for a retail store comprising a processor, a memory, and a camera, the memory containing instructions configuring the system to perform actions including:
with the camera, capture image data from packaging of products presented by customers for checkout;
process first captured image data to produce map data identifying locations on first packaging where a steganographic watermark signal is detected, and locations where it is absent;
process second captured image data to produce map data identifying locations on second packaging where a steganographic watermark signal is detected, and locations where it is absent; and
issue an alert signal about the first product packaging, but not issuing an alert signal about the second product packaging, because said map data produced from the first captured image data indicates a telltale void in the watermark signal that is consistent with application of a rectangular barcode label over the first packaging, whereas said map data produced from the second captured image data indicates a void in the watermark signal that is irregularly shaped, and thus not consistent with application of a rectangular barcode label over the second packaging.

6. A checkout method practiced in a retail store using a camera-equipped system including one or more hardware processors, the method comprising the acts:
capturing imagery depicting packaging of a retail product presented for purchase by a customer at said store, using said camera;
processing the captured imagery with the one or more processors, to decode GTIN data encoded in a steganographic digital watermark on the product packaging;
processing the captured imagery with the one or more processors, to decode GTIN data encoded in a barcode on the product packaging;
comparing the GTIN data decoded from the steganographic digital watermark with the GTIN data decoded from the barcode;
determining, through said comparing, that there is a mismatch between GTIN data decoded from the barcode and GTIN data decoded from the steganographic digital watermark; and
issuing an alert signal indicating the mismatch to an authority.