Generalizations of the Kuznetsov-Tsybakov problem for generating image-like 2D barcodes

Many two-dimensional (2D) barcodes, such as quick response (QR) codes, lack user-friendly appearance. Our goal in this paper is to generate 2D barcodes that “look” like recognizable images or logos. Standard steganographic methods hide a message (payload) in an image usually by modifying bits in a specific way using predetermined pixels of the image. This approach cannot be directly used for very low bit rates commonly used in 1 bit per pixel 2D barcodes. It is possible to produce barcodes in which the grayness of a pixel in an image is interpreted as the probability of assigning a value (black or white) to the corresponding pixel of the encoded message (payload). This can be viewed as statistical constraints enforced on the encoded bit-sequence. Using an information theoretic approach, Kuznetsov and Tsybakov have shown that this can be done for a specific case of constraints almost without any loss of capacity. In this paper, we propose generalizations of this approach with weaker constraints as an application to generating 2D barcodes that resemble images. We describe a coding framework, various types of constraints, a practical approximation and some example 2D barcodes generated from our implementation.