This is the author's version of an article that has been published in this journal.

Changes were made to this version by the publisher prior to publication.

The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
1

Two-Layer QR Codes
Tailing Yuan, Yili Wang, Kun Xu, Member, IEEE, Ralph R. Martin, Shi-Min Hu, Senior Member, IEEE

Abstract—A quick-response code (QR code) is a two- with a top layer and a bottom layer. Each layer contains
dimensional code akin to a barcode which encodes a message a matrix of modules. The bottom layer modules are black
of limited length. In this paper, we present a variant of QR or white, while the top layer modules may be transparent,
code, a two-layer QR code. Its two-layer structure can display
two alternative messages when scanned from two different allowing the code to appear differently from different viewing
directions. We propose a method to generate such two-layer directions. The two-layer QR code can thus display two valid
QR codes encoding two given messages in a few seconds. We QR codes, encoding two different messages, by changing the
also demonstrate the robustness of our method on both synthetic view.
and fabricated examples. All source code will be made publicly
Our method is thus more generally applicable than [1], [2]
available. 1
and could be used in almost any real-world scenarios where
Index Terms—QR code, Two-layer QR code, barcode two messages are needed. These might include providing
alternative payment methods, giving different app download
I. I NTRODUCTION links for different operating systems, providing explanatory
quick response code (QR code) is a two-dimensional text in different languages, or giving multiple stories for an
A barcode, consisting of black and white squares, called
modules. It encodes information such as a URL or a text
exhibit in a museum. Another possible use is in gaming, where
two or more people sit at a table opposite each other. A two-
message. By scanning a QR Code using a mobile phone, a layer QR code on the table would naturally be scanned from
user can get immediate access to its content. QR codes have different directions, e.g., to provide separate messages to a
been widely used in numerous applications such as advertising card dealer and other card players. For puzzle games, scanning
and digital payments, as they are easy to create and scan. from the left could show puzzle questions, and scanning from
A QR code can encode only a single message. However, en- the right could give the answers. Using a single code ensures
coding two or more messages is useful in many scenarios. For that the questions will always be correctly associated with
example, a store may provide alternative payment methods, an the answers, which may not always occur if two separate QR
app may need different download links for different operating codes are used (one may get lost, become defaced, etc.).
systems, and an exhibition item may have descriptions in mul- As well as explaining the structure of our two-layer QR
tiple languages. While previous work [1], [2] has considered code, we also give a fully automatic algorithm to create a two-
combining two messages in one QR code, they target particular layer QR code encoding two given messages. Specifically, we
applications. The former targets separate public and private optimize the module values of both layers, with the aim of
messages, and requires a specialized reader for the latter. maximizing its error correction capacity while also encoding
The second uses device characteristics (such as its operating the two messages. For speed, we have developed a two-step
system) to determine which alternative message to retrieve; the optimization scheme and merge and reduce operators to reduce
user is not involved in selecting which alternative message is the solution space. The optimization problem is then solved
desired. Such specific usages do not encompass all applications by simulated annealing in just a few seconds. We also show
of QR codes needing multiple messages. how to physically fabricate a two-layer QR code.
Various kinds of art exhibit different effects when viewed Our two-layer QR codes can also be combined with ex-
or illuminated from different angles or distances, such as isting QR code beautification approaches, to display a visual
lenticular images [3] which can change the displayed image logo within the QR code display area. We demonstrate the
depending on the viewing angle, hybrid images [4] which have robustness of our method on a variety of examples, including
different interpretations depending on the viewing distance, both synthetic and fabricated ones.
and shadow art sculptures [5] which cast different meaningful
shadows under different lighting directions.
Inspired by such work [3]–[5], we present a variant of QR II. R ELATED W ORK
code called two-layer QR code, in which two messages are A. QR Code Beautification
stored and can be retrieved separately from two different view-
ing directions. It is a specially designed two-layer structure, Although a QR code is machine readable, it appears as a
random pattern of black and white modules and is not visually
Tailing Yuan, Kun Xu, Shi-Min Hu are with the Department of Computer meaningful. To address this, various works have considered
Science and Technology, Tsinghua University, Beijing, 100084 CN. Kun Xu
is the corresponding author, email: xukun@tsinghua.edu.cn. QR code beautification, allowing e.g. the embedding of visual
Yili Wang is with the Department of Foreign Languages and Literatures, information such as a logo within a QR code. QR code
Tsinghua University, Beijing, 100084 CN. beautification approaches are generally based on one of 3
Ralph R. Martin was with the School of Computer Science and Informatics,
Cardiff University, UK. techniques: direct superimposition, module modification and
1 https://github.com/yuantailing/two-layer-qrcode padding editing.

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
 This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
2

1) Direct superimposition: One way to achieve QR code general scenarios; users are required to install a specialized
beautification is to directly superimpose a logo or a pattern decoding App for the private message.
onto a QR code [6]–[9]. Superimposing a logo will damage In [2], two App download links can be combined into
some codewords but as long as this is within the error one QR code, including e.g. one link for iOS and another
correction capacity, the QR code can still be correctly decoded. for Android. This work does not modify QR code design or
Different schemes have been proposed to find appropriate po- structure: the QR code simply stores only a single link to an
sitions, orientations, and scales of superimposed logos without external server. The linked webpage is redirected to the desired
damaging the code. Samretwit and Wakahara [10] measured download link as determined by the operating system of the
the reliability of a superimposed QR code at different positions device scanning the QR code. While working well for this
and scales. As an alternative to superimposition, Baharav target usage, it has limited use in general scenarios. An Internet
and Kakarala [11] achieved QR code beautification by image connection is required for message selection, while standard
blending. QR code decoding can be done offline. Users are not involved
2) Module modification: A QR code remains decodable in choosing the message decoded, which is determined solely
as long as the values in the central pixels of each module by the device characteristics (unless additional information is
are unchanged. Several beautification approaches [12]–[19] input). For example, this approach cannot readily use a single
have been proposed, in which carefully crafted modules, QR code for the puzzle game scenario (provide either the
usually of a smaller size and only covering the central pixels, puzzle questions or answers).
replaces the original modules. For example, Chu et al. [12] While the above methods [1], [2] are specialized for partic-
generated halftone QR codes by subdividing modules into ular applications, our method is more general and flexible.
3 × 3 submodules. Lin et al. [13] embellished QR codes by We allow two arbitrary messages, and the user can freely
superimposition as well as stylizing module shape based on choose which message to read simply by viewing our code
a specified exemplar. Gao et al. [14] showed how to embed from different viewing directions, using any standard QR code
QR codes into color images, making QR code perceptually reader. Changing viewing angles to obtain different messages
invisible to humans but still machine-readable. provides a natural, simple interface which is easy to learn and
3) Padding editing: If the length of the encoded message to perform, and follows standard QR code practice. We do not
is less than the code’s capacity, padding bits follow in each require an Internet connection, external server, or specialized
data codeword. The values of these padding bits can be freely readers.
changed without altering the message. By taking advantage of A disadvantage of our two-layer QR codes is that they
this property, Fujita et al. [20] use non-systematic encoding require fabrication rather than simple printing. However, this
of the Reed-Solomon code to allow free editing of a selected only causes more work for the content provider (who creates
area without reducing the code’s error correction capability. the code), while users (who scan the code) can use existing
Other methods [21]–[27] have been proposed for generating QR code readers. The only difference to them is that the code
colored QR codes by combining padding editing and module is scanned from the left or right directions instead of from the
modification. front. We believe this is a reasonable trade-off for the potential
benefits obtained.
The remainder of the paper is organized as follows. We
B. QR Code Alternatives briefly review standard QR codes in Section III, then explain
Various alternative 2D barcode formats have been proposed the basis of our two-layer QR codes in Section IV. We
for different purposes. Picture-embedding 2D barcodes like present an algorithm for their generation in Section V. We
2-D image code [28], PiCode [29], and RA (Robust and provide experimental results in Section VI and an evaluation
Aesthetic) code [30] have been proposed to embed images in in Section VII. Finally, we conclude the paper in Section VIII.
2D barcodes. Colored QR codes [31]–[33] have been proposed
to increase data capacity by using more color channels. Yang III. QR C ODE BASICS
et al. [34] proposed ARTcode, which look like an image,
retaining aesthetic content and decoding feasibility in one To aid understanding, and introduce terminology, we briefly
visual pattern. However, a common drawback of all such codes remind the reader of the structure and operation of an original
is that additional software is needed when decoding. QR code.
1) Structure: A QR code is a 2D image consisting of
black and white squares: see Figure 1. Its parameters and
C. QR Codes combining two messages components include:
Other previous works [1], [2] have considered how to • A module is the smallest element (black or white square)
combine two messages into one QR code. The two-level QR of the QR code. Each module represents 1 bit of data,
code (2LQR) [1] stores a public message and an additional i.e., a black module represents 1 while a white module
private message. The messages are of different kinds. The represents 0.
public message can be read by any QR code reader, but the • A codeword consists of 8 modules and represents 8 bits
private message can only be read by a specialized reader. This of data.
method is designed specifically for private message sharing • An error correction block, or block for short, consists of
and document authentication. However, it is not suited to a sequence of codewords. A block represents a message

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
 This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
3

Finder pattern
left view: "IEEE" right view: "TIP"
Format information
Data codewords
Error correction codewords

Alignment pattern

top layer
Fig. 1. QR code structure. Finder patterns and alignment patterns are located bottom layer
at fixed positions. The format information records the error correction level
and data masking pattern. A codeword consists of 8 modules and represents Fig. 2. A two-layer QR code consists of a top layer and a bottom layer with
8 bits of data. a small gap between them. The bottom layer is composed of black and white
modules, while the modules of the top layer may also be transparent. When
scanned from the left view, this QR code appears as a standard QR code
encoding the string “IEEE”; when scanned from the right, it appears as a QR
with a specific length. The codewords within it comprise code encoding a different string, “TIP”. In all figures, transparent modules
data codewords and error correction codewords. The are shown in translucent green to make them visible; in the actual QR code
former represent the underlying message, while the latter they are transparent.
are Reed-Solomon [35] checksums computed from the
data codewords, helping to make the QR code robust to
noise and damage. A block with p codewords in total, out alignment patterns. The value of each module is obtained by
of which k are data codewords, can be correctly recovered binarization. Next, the EC level and data masking pattern are
if it has no more than b(p − k)/2c incorrect codewords. obtained from the format information. The bit sequence of
• Finder patterns and alignment patterns are located at the message may then be recovered block by block, the error
fixed positions and are used to locate and orient the QR correction codewords helping to repair noise and damage.
code when scanning.
• Format information stores parameters describing the QR
code, including its error correction level (EC level) and IV. T WO -L AYER QR C ODE
data masking pattern. The EC level determines the level
In this section, we introduce our two-layer QR codes, which
of error tolerance, via the numbers of data codewords
aim to display two valid QR codes when scanned from two
and error correction codewords in each block. Four EC
different views. It has a specially designed structure, which
levels (L, M , Q, and H) exist, with increasing reliability
consists of a top layer and a bottom layer. The bottom layer
but decreasing data capacity. One of 8 predefined data
is composed of black and white modules, which is similar to
masking patterns must be selected. A further parameter,
a standard QR code. The top layer has a similar number of
version, defines the size of the QR code: a QR code
modules (see later), but some of them may be transparent. The
having version V has (4V + 17) × (4V + 17) modules.
space between the two layers allows our proposed structure
The version and EC level together determine the data
to have different appearances when scanned from different
capacity of a QR code, i.e., the length of the message it
directions. Figure 2 shows the structure of a two-layer QR
can represent.
code.
Further details can be found in the specification ISO/IEC The bottom and top layers are designed as follows. The
18004:2015 [36]. bottom layer has N ×N modules. Each module on the bottom
2) Message encoding: To encode a given message as a QR layer is colored white (for 0) or black (for 1). The top layer
code, it is first converted to a sequence of bits using one of has (N + 1) × N modules, with N + 1 and N in x and y
four encoding modes: numeric, alphanumeric, byte, and Kanji. directions respectively. Each of its modules may be white (0),
Different modes use different character sets, with different black (1), or transparent (t). The top and bottom layers are
numbers of bits for each character. Suitable values of version aligned along the y-axis but symmetrically offset by 0.5 units
and EC level are selected, based on message length and desired along the x-axis (where the width of a module is 1 unit). A
reliability. Next, the sequence is put into data codewords typical case is a QR code with version 5, which has N = 37.
in each block in a particular order, and corresponding error When viewed from a carefully chosen direction from the left
correction codewords are computed. Finally, the modules are side, the projected offset between top and bottom layers will
bit-wise XORed with one of the eight predefined data masking change exactly to 0. Similarly, when viewed from a specific
patterns, using the one which best avoids adjacent modules direction from the right side, the projected offset changes
appearing in the same color. exactly to 1. See Figure 3. Let Lt (i, j) be the value of module
3) Message decoding: To decode a message in a scanned (i, j) in the top layer (1 ≤ i ≤ N + 1, 1 ≤ j ≤ N ), and
QR code, the code is first located by use of the finder and Lb (i, j) be the value of module (i, j) in the bottom layer

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
 This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
4

left view: right view: require that the same messages can still be decoded from the
Ol (i, j) = 1 Or (i, j) = 0 0 viewing patterns as from the target patterns. At the same time,
1 we should maximize the reliability of the viewing patterns, i.e.
transparent their ability to still be correctly decodable when damaged. To
measure the reliability of a two-layer QR code, we define its
effective recovery ratio E to be:
row j
Lt (i, j) Lt (i + 1, j)
E = min D(Osi , Tsi ), (2)
i,s

Lb (i, j) bottom layer top layer where Osi denotes the i-th block in one pattern Os (Os ∈
{Ol , Or }, either the left viewing pattern Ol or the right view-
Fig. 3. Each module on the bottom or top layer affects two different modules ing pattern Or ), Tsi denotes the i-th block in the corresponding
in the viewing patterns. The color of module Lb (i, j) affects the colors of
Ol (i, j) and Or (i, j).
target pattern (which covers the same area as Osi ), and D(·)
is the remaining recovery ratio for each block. The effective
recovery ratio E is thus computed as the minimum of the
remaining recovery ratios over all blocks of the two viewing
patterns. The remaining recovery ratio D for a block Osi is
defined as:

D(Osi , Tsi ) = b(p − k)/2c − δ(Osi , Tsi ) /p, (3)

bottom layer top layer left view right view
Fig. 4. A generated two-layer QR code. Left to right: bottom layer, top layer,
left view, and right view. These two views show QR codes representing the
where p and k respectively denote the number of codewords in
strings “Two-Layer QR Code” and “Computer Science” respectively. total, and of data codewords in this block. Here, b(p − k)/2c
is the maximum allowed number of mismatched codewords
that still allows correct decoding from the QR code structure,
(1 ≤ i, j ≤ N ). The left and right viewing patterns, Ol and while δ(Osi , Tsi ) denotes the number of codewords in block Osi
Or respectively, can be computed to be: which mismatch those in block Tsi (a codeword consists of 8
( modules: if any of its modules mismatches, then the codeword
Lb (i, j) if Lt (i, j) = t (transparent) mismatches). The remaining recovery ratio D represents the
Ol (i, j) = ,
Lt (i, j) otherwise remaining error capacity of a block.
Formally, we may now consider generation of a two-layer
(
Lb (i, j) if Lt (i + 1, j) = t (transparent)
Or (i, j) = . QR code as an optimization problem. Given two target patterns
Lt (i + 1, j) otherwise
Tl and Tr , the goal is to find top and bottom layer patterns
(1) Lt and Lb by minimizing an objective function:
Without further constraints, the left and right viewing patterns
are not necessarily valid QR codes. In Section V, we describe min −E, (4)
Lt ,Lb
a generation algorithm for two-layer QR codes which ensures
both left and right viewing patterns are valid QR codes. where E is the effective recovery ratio defined in Equation 2. It
An example of a generated two-layer QR code is shown in is computed by comparing the module values in target patterns
Figure 4. (Tl and Tr ) with those in the viewing patterns (Ol and Or ),
which are computed from the top and bottom layer patterns
(Lt and Lb ) according to Equation 1.
V. G ENERATION A LGORITHM
Equation 4 represents a combinatorial optimization problem.
A. Problem Definition Since the top layer Lt and the bottom layer Lb contain N (N +
Given two target messages, our goal is to generate top 1) and N 2 modules, with 3 and 2 possible module values,
2
and bottom layer patterns (Lt and Lb ) such that the left and respectively, the size of the solution space is 2N 3N (N +1) ,
right viewing patterns (Ol and Or ) encode the two desired which is far too large to explore exhaustively. We need a more
messages. We first use conventional QR code generation efficient approach.
algorithms [36] to convert each message into a standard QR Recall the definitions of the effective recovery ratio E and
code, which we refer to as left and right target patterns (Tl remaining recovery ratio D in Equations 2 and 3. They are
and Tr ), respectively. They must have the same version (i.e. computed from the set of all mismatched codewords in the
size) but the EC levels and data masking patterns may differ. viewing patterns, which we call the full mismatched codeword
For now, we restrict their EC levels and data masking patterns set. We observe that E can be computed in two steps, firstly
to be the same. We will discuss how to handle cases when obtaining the full mismatched codeword set by comparing
they are different in Section VI-A2. module values of viewing and target patterns, and secondly,
A strict requirement would demand that the viewing patterns computing E from the full mismatched codeword set. We
should exactly match the target patterns (i.e., Ol = Tl , Or = will show how to make use of this separation property in the
Tr ), but this is in practice impossible to achieve. Instead, we following subsections.

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
 This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
5

left target top layer different combinations of values for Lt and Lb . The viewing
Tl (0, 0) Tl (1, 0) Tl (2, 0) fixed Lt (1, 0) fixed fixed
patterns should have the same values as the target patterns
interleaved row
wherever possible, i.e. we desire Ol (i, j) = Tl (i, j) and
right target bottom layer fixed fixed Lt (1, 0) Lb (1, 0) fixed Lb (2, 0) fixed
Or (i, j) = Tr (i, j). It is clear that in all cases, setting
Tr (0, 0) Tr (1, 0) Tr (2, 0) fixed Lb (1, 0) Lb (2, 0)
| {z } |{z} Lb (i, j) = 1 is always better than Lb (i, j) = 0. Hence, Lb (i, j)
segment segment
may be fixed as Lb (i, j) = 1, without further optimization.
Fig. 5. Fixed modules and segments.
We determine all fixed modules and fix their values accord-
ingly.
TABLE I
2) Segments: Consider the j-th rows of Lt and Lb . We may
M ODULE VALUES WITH DIFFERENT COMBINATIONS OF VALUES FOR Lt interleave their modules to form an interleaved row:
AND Lb WHEN Tl (i, j) = Tr (i, j) = 1.
{Lt (0, j), Lb (0, j), Lt (1, j), . . . , Lb (N − 1, j), Lt (N, j)},
Lb (i, j) = 0 Lb (i, j) = 1
in which top layer modules and bottom layer modules alter-
Ol (i, j) 0 0 nate. The value of a viewing pattern module is determined
Lt (i + 1, j) = 0
Or (i, j) 0 0
by two neighboring modules in an interleaved row (i.e., one
Lt (i, j) = 0 Ol (i, j) 0 0
Lt (i + 1, j) = 1
Or (i, j) 1 1 top layer module and one bottom layer module). Therefore,
Ol (i, j) 0 0 after dividing the interleaved row into segments, we could
Lt (i + 1, j) = t
Or (i, j) 0 1 determine each module value in the viewing pattern from just
Lt (i + 1, j) = 0
Ol (i, j) 1 1 one corresponding segment instead of the whole row. This
Or (i, j) 0 0 allows us to analyze the reliability of each segment separately.
Lt (i, j) = 1 Lt (i + 1, j) = 1
Ol (i, j) 1 1 3) Partial mismatched codeword set: Each segment may
Or (i, j) 1 1
contain mismatched modules, resulting in mismatched code-
Ol (i, j) 1 1
Lt (i + 1, j) = t
Or (i, j) 0 1 words. These form its partial mismatched codeword set. We
Ol (i, j) 0 1 obtain the full mismatched codeword set by computing the
Lt (i + 1, j) = 0
Or (i, j) 0 0 union of the partial mismatched codeword sets of all segments.
Lt (i, j) = t Ol (i, j) 0 1
Lt (i + 1, j) = 1
Or (i, j) 1 1
Ol (i, j) 0 1 C. Two-Step Optimization
Lt (i + 1, j) = t
Or (i, j) 0 1 By making use of segments, the optimization problem in
Equation 4 can be solved using a two-step scheme.
1) Candidate family: A candidate family is the set con-
B. Fixed Modules and Segments
taining all possible partial mismatched codeword sets for a
We next introduce concepts of fixed modules, interleaved segment (a set of sets). In the first step, we obtain a candidate
rows, segments, and partial mismatched codeword sets. Fixed family for each segment, by iterating through all combinations
modules are modules whose value can be directly set without of a segment’s module values. Note that different combinations
optimization. An interleaved row is formed by interleaving of module values may result in duplicate partial mismatched
modules in a row of the top layer with those in the same codeword sets, which lead to the same full mismatched code-
row of the bottom layer. A segment is an array of contiguous word set, and thus the same effective recovery ratio E. Hence,
modules in an interleaved row terminated by fixed modules. in a candidate family, we only store unique partial mismatched
See Figure 5. Each segment may contain mismatched modules, codeword sets, and remove any duplicates.
resulting in mismatched codewords, which are grouped into Below we show an example of computing a candidate
the partial mismatched codeword set for the segment. The family. Consider a very simple segment A with two modules,
full mismatched codeword set is the union of the partial one from the top layer and one from the bottom layer.
mismatched codeword sets of all segments. There are 6 possible combinations of module values: {c1 , c2 }
We now explain how to compute all of the above. (c1 ∈ [0, 1, t], c2 ∈ [0, 1]). Suppose the partial mismatched
1) Fixed modules: We observe that there are two cases codeword set for each value combination is as below:
when we can directly find the values of some modules, the
P ({0, 0}): {Cl1 }, P ({1, 0}): {Cr2 }, P ({t, 0}): {Cl1 },
fixed modules, in Lt and Lb without the need for optimization.
These two cases are: P ({0, 1}): {Cl1 }, P ({1, 1}): {Cr2 }, P ({t, 1}): ∅,
Case 1: if Tl (i, j) = Tr (i, j) = c (where c = 0 or 1), Lb (i, j) where P (·) is the partial mismatched codeword set for a
can be fixed likewise: Lb (i, j) = c. specific combination of module values, Cli is the i-th codeword
Case 2: if Tl (i, j) = Tr (i − 1, j) = c, Lt (i, j) can be fixed of the left target, and Crj is the j-th codeword of the right
likewise: Lt (i, j) = c. target; P ({0, 0}) = {Cl1 } means that setting the module
Proof: Consider Case 1 (the proof for Case 2 is similar). values of the segment to {0, 0} causes one codeword Cl1 to be
Without loss of generality, suppose Tl (i, j) = Tr (i, j) = 1. mismatched. The candidate family S for segment A is, after
According to Equation 1, the values of Ol (i, j) and Or (i, j) removing duplicates:
(and these two modules only) depend on the value of Lb (i, j).
In Table I, we provide the values of Ol (i, j), Or (i, j) for S = {∅, {Cl1 }, {Cr2 }}.

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
 This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
6

This candidate family is a set of 3 different partial mismatched family with size m1 m2 . However, the merged candidate family
codeword sets. may possibly be further reduced. For example, consider two
We compute the candidate families for all segments accord- candidates S1 and S2 both with size 2:
ingly.
2) Optimization on candidate families: In the second step, S1 = {{Cl1 }, {Cr2 }}, S2 = {{Cl1 }, {Cr3 }}. (7)
we solve the optimization problem in Equation 4. Instead of
The merged candidate family S is:
simultaneously determining values for all modules in Lt and
2
Lb , a problem of size 2N 3N (N +1) , we operate on segments, S = {{Cl1 }, {Cl1 , Cr2 }}, {Cl1 , Cr3 }, {Cr2 , Cr3 }}.
and aim to determine a combination of partial mismatched
codeword sets, i.e. to select one partial mismatched codeword Its size is 4 but it can be decreased to 2 by applying the reduce
set for each segment from its candidate family. These give the operator:
full mismatched codeword set and hence the effective recovery reduce
S −−−→ S = {{Cl1 }, {Cr2 , Cr3 }}.
ratio E.
Let u be the number of segments, Ai be the i-th segment For convenience, we define two candidate families to be
(1 ≤ i ≤ u), Si be its candidate family as computed in the first mergeable if at least one identical codeword is contained in
step, and kSi k be the size of Si . The optimization problem in both. For example, S1 and S2 in Equation 7 both contain
Equation 4 is reduced to: the same codeword Cl1 , so S1 and S2 are mergeable. If two
min −E, (5) candidate families are not mergeable, there is no benefit in
s merging them.
where s = {s1 , . . . , su } is an unknown index vector to 3) Merge and reduce procedure: We now show how to
be found, and si gives the index of the selected partial systematically make use of the merge and reduce operators,
mismatched codeword set from the i-th candidate family Si starting from the initial set of all candidate families computed
(1 ≤ si ≤ kSi k). as in Section V-C, i.e., Ω = {S1 , . . . , Su }.
For each candidate family Si , there are kSi k choices for We repeatedly apply reduce and merge operators to the
the partial mismatched codeword set. Hence, the complexity candidate families in Ω, as follows:
of the solution space of the problem in Equation 5 is: • Reduce all candidate families in Ω.
• Repeat
Y
kSi k. (6)
1≤i≤u – Shuffle the ordering of all candidate families in Ω.
– For each mergeable pair S1 , S2 of candidate families
This two-step scheme greatly reduces the size of the solution
space. ∗ If kS1 k × kS2 k < threshold m then
· S ← Merge(S1 , S2 )
D. Merge and Reduce · Remove S1 and S2 from Ω
· S ← Reduce(S)
To further reduce the solution space and accelerate opti-
· Add S to Ω
mization, we introduce two operators on candidate families:
· Goto Repeat
the reduce operator and the merge operator.
1) Reduce operator: Given a candidate family S, let P1 ∗ End If
and P2 be two different partial mismatched codeword sets – End For
in S. If P1 $ P2 , P2 is a redundant partial mismatched • Until there are no more pairs in Ω that can be merged.
codeword set in S, since choosing P1 would always give A naive implementation of enumerating over all mergeable
fewer mismatches than choosing P2 . Hence P2 can safely be pairs of candidate families takes u(u − 1)/2 pairwise tests,
ignored. Reducing a candidate family means removing all such where u is the number of candidate families. We improve the
redundant mismatched codeword sets from it. An example of algorithm performance by building an index from codewords
reducing a candidate family is given below: to candidate families, which quickly allows us to find all
reduce
S = {{Cl1 }, {Cl1 , Cr2 }} −−−→ S = {{Cl1 }}. mergeable pairs. Furthermore, the merge size threshold m is
used to avoid very large candidate families: applying reduce
Reducing a candidate family decreases its size and hence the and merge operators to a very large candidate family may even
size of the solution space. reduce overall performance. In our implementation, the merge
2) Merge operator: The merge operator takes two candi- size threshold is set to m = 300. We will evaluate different
date families as input and combines them into one candidate choices of m in Section VII-A1.
family. Given two candidate families S1 and S2 , the merged
candidate family S is given by:
E. Simulated Annealing
S = {P1 ∪ P2 |P1 ∈ S1 , P2 ∈ S2 }.
The solution space of the problem in Equation 5 is still too
At a first glance, the merge operator does not seem to decrease large to be fully explored even after the merge and reduce
the size of the solution space, since it converts two candidate procedure. To quickly obtain an approximate solution, we use
families (S1 with size m1 and S2 with m2 ) into a candidate simulated annealing [37].

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
 This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
7

1) Simulated annealing: We aim to simultaneously max- 3) Data masking patterns: The above process is carried
imize the minimum of the remaining recovery ratio D for out 8 times for the 8 different data masking patterns, and
all blocks. Optimization techniques like simulated annealing the solution with the highest recovery ratio from all 8 data
which implicitly rely on the use of derivatives E are unlikely masking patterns is selected; it is done in parallel using 8
to work well in this case, since E does not necessarily change threads.
if only small changes are made to the index vector s. Hence,
we slightly modified the optimization target in Equation 5 to:
F. Beautification
min −E 0 , (8)
s Two-layer QR codes also support beautification, e.g. to add
where E is defined as:
0 a given logo. Beautification is done during preprocessing.
Given a reference image, we first beautify the input left and
right target patterns using an existing QR code beautification
X
E 0 = min D(Osi , Tsi ) + λ D(Osi , Tsi ). (9)
i,s
i,s method [20]. We then optimize the top and bottom layers as
usual.
E 0 is composed of two terms. The first term is just E: the However, since we use the same reference image to beautify
minimum of the remaining recovery ratio D for all blocks. the left and right target patterns, many modules in the left and
The second term is the sum of the remaining recovery ratio right target patterns are identical, resulting in a large number
D for all blocks. of fixed modules. As a result, beautification reduces the search
We incorporate the second term to improve the derivative space and also potentially increases the recovery ratio.
properties of the overall optimization target, making it more
suitable for simulated annealing. Recall that our target is
to maximize E (minimize −E) as given in Equation 5. VI. R ESULTS AND FABRICATION
Maximizing the second term (by definition, the sum of all
D) shares a similar goal to maximizing E (by definition, the A. Results
minimum of all D): a small sum cannot, in general, give a We tested our method on a PC with a 3.5 GHz Intel Core i7-
large minimum. In practice, we set the weight parameter λ to 5930K CPU and 32 GB RAM. We implemented our algorithm
a small value (λ = 0.1) to ensure that the second term makes in C++. All two-layer QR codes shown in the paper were
only a small contribution, and E 0 is still dominated by E. generated within a few seconds; the time needed to generate
We start with a random choice for s. On each iteration, a and beautify the input target patterns was less than 5 ms and
neighborhood is computed by reassigning the indices of the can be ignored.
selected mismatched codeword set for several candidate fam- 1) Diverse examples: To show the robustness of our algo-
ilies (i.e. we change the values of si for some i, 1 ≤ i ≤ u). rithm in handling diverse examples, we generated 12 examples
The temperature is initialized to 1.0 and decays by 0.999 every of two-layer QR codes: see Figures 6 and 7. Their versions and
20 iterations. The acceptance probability function is set to: EC levels range from (2, M ) to (17, H); 6 of the 12 examples
  0
Enew − Eold0
 are beautified.
min 1, exp , We show 4 examples in Figure 6. Messages are encoded in
T
alphanumeric mode. The top two rows of Figure 6 show two
where Eold0
and Enew
0
are the energies before and after examples encoding the same messages, with different versions
transition, respectively; T is the temperature. Iteration stops and different EC levels. As EC level increases, the results
when there has been no further energy decrease for the last become more reliable with larger effective recovery ratio, but
140,000 iterations (i.e. the temperature has decayed by about a larger version value is required to encode the message.
10−3 ). Note that E 0 is only used in the acceptance probability However, a larger version value requires smaller modules (for
function. We record the solutions in all iterations and adopt the same overall physical size of QR code), which makes the
the solution with the highest actual energy E. codes harder to scan reliably. There is thus a trade-off between
2) Module determination: Having obtained the partial mis- the EC level and version.
matched codeword set for each candidate family, the next The bottom two rows of Figure 6 provide two more
step is to determine corresponding module values. For each beautified examples encoding the same messages, with the
segment, there may be multiple module value combinations same versions but different EC levels. It shows that better
which result in the same partial mismatched codeword set. We reliability can also be achieved for beautified examples by
prefer the combination with the highest number of transparent increasing EC level. However, a higher EC level requires more
modules on the top layer, because more transparent modules error correction codewords, resulting in fewer modules being
will lead to fewer occlusions, producing fewer shadows and available to meet beautification design requirements (if we
and potentially fewer scanning errors. keep the version value unchanged). Therefore, an appropriate
After determining all module values for the segments, EC level should be chosen to balance aesthetics and reliability.
we further change the values of fixed modules on the top Further 8 examples are shown in Figure 7. Here, the
layer to transparent if doing so does not introduce additional examples are encoded in byte mode. Our method can robustly
mismatched codewords. handle these diverse examples.

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
 This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
8

EC message effective
version bottom layer top layer left view right view
level length recovery ratio

2 Q 27, 23 3
44

3 H 27, 23 5
35

10 L 27, 37 4
87

10 M 27, 37 9
69

Fig. 6. Four examples of two-layer QR codes with different versions and different EC levels. Left to right: version, EC level, string lengths of the two encoded
messages, generated bottom and top layers, left and right views, and the effective recovery ratio. Messages are encoded in alphanumeric mode. Messages
encoded in the top 2 rows: left view: “A B C D E F G H I J K L M N”, right view: “O P Q R S T U V W X Y Z”. Messages encoded in the bottom 2
rows: left view: “HTTP://WWW.TSINGHUA.EDU.CN/”, right view: “TSINGHUA UNIVERSITY. BEIJING . CHINA”.

2) Different EC levels and different data masking patterns: the run-time stage, after EC levels are provided by users,
The EC level and data masking pattern (short as ‘mask’) of we need to determine which combination to use. We iterate
a QR code are stored in the format information. As shown over combinations of the selected EC levels and all masks.
in Figure 1, format information is located next to the finder For each combination, we run the optimization and obtain
patterns. It contains 15 bits of data and can tolerate up to 3 an effective recovery ratio. The combination with the highest
bit errors. Format information is identified by a scanner before effective recovery ratio is selected. If multiple combinations
message decoding, and its correctness is important. result in the same effective recovery ratio, the one with the
As explained in Section V-A, our generation algorithm fewest error bits in format information is selected.
restricts the left and right views to have the same EC levels Figure 8 shows an example using different EC levels. In this
and masks. However, Our algorithm could be slightly modified example, the EC levels of the left and right views are user-
to support different EC levels, and different masks, by taking specified to be H and M , respectively, to allow different error
format information into account. To do so, care must be taken correction capacities. The resulting effective recovery ratio is
in dealing with format information, since differences in EC 2/39 (left 2/39, right 3/49).
levels and masks can introduce errors in format information. To allow left and right views to have different masks, we
To achieve this, we slightly modify our algorithm in two have to iterate over 8×8 combinations of masks and select the
ways. Firstly, we add a precomputation stage. For all combi- combination with the highest effective recovery ratio. Using
nations of different EC levels and different masks (42 × 82 = such a different mask scheme thus requires approximately
1024 combinations in total), we precompute the optimal values 8× as much computation as the original same mask scheme
for those top and bottom layer modules which affect format described in Section V-E3, where both views use the same
information, using exhaustive search. For each combination, mask.
the associated module values which give the fewest error Figure 9 (bottom) shows an example of using different
bits are considered as optimal and kept. These precomputed masks, while the same masks are used in Figure 9 (top); other
module values are considered as fixed modules and their values settings and encoded messages are unchanged. In this example,
are not changed during later optimization. Secondly, during while the result with different masks achieves a better effective

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
 This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
9

EC message effective
version bottom layer top layer left view right view
level length recovery ratio

2 M 17, 21 1
44

8 Q 95, 83 3
40

12 H 147, 133 5
42

17 H 256, 256 4
43

9 L 44, 20 2
146

13 L 48, 44 6
133

13 M 6, 8 9
60

16 Q 35, 14 9
43

Fig. 7. Further examples of two-layer QR codes. Left to right: version, EC level, string lengths of the two encoded messages, generated bottom and top
layers, left and right views, and the effective recovery ratio. Messages are encoded in byte mode.

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
 This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
10

EC message effective
version bottom layer top layer left view right view
level length recovery ratio

39 , 49
2 3

7 H, M 39, 122
overall: 2
39

Fig. 8. Example whose views have different EC levels. EC level: H (left view), M (right view). Messages are encoded in byte mode. Left:
“https://www.iso.org/standard/62021.html”, right: “Information technology -- Automatic identification and data capture techniques -- QR Code bar code
symbology specification”. Time taken: 0.635 s.

effective
EC msg.
type ver. bottom layer top layer left view right view recovery
level len.
ratio

same
4 H 50, 50 2
mask 25

different
4 H 50, 50 3
mask 25

Fig. 9. Examples whose views have (top row) the same data masks (pattern 010), and (bottom row) different masks (left: 100, right: 011). Both encode the
same messages, randomly generated strings of length 50, in alphanumeric mode. Time taken: 0.412 s (same masks), 2.726 s (different masks).

recovery ratio (3/25) than when using the same mask (2/25), a transparent plastic sheet and the bottom layer pattern on
it additionally introduces 1 bit error in format information. paper. We then paste these two patterns onto the two sides of
We tested the different mask scheme described above for a transparent acrylic plate with a thickness of h = 3 mm. We
all 14 examples in Figures 6–9. Perhaps surprisingly, except set the width of the top layer modules to wt = 1.5 mm.
for one example in Figure 9, the different mask scheme An example of a fabricated two layer QR code is shown in
performed no better than the same mask scheme, i.e. the Figure 10.
optimal combination turned out to be a pair of identical masks. 2) Module widths: Intuitively, it is clear that the bottom
To assess scanning robustness, we conducted a synthetic layer modules should be a little larger than the top layer
scanning comparison between the different mask scheme and modules to achieve the best alignment, due to the foreshort-
the same mask scheme. See Figure 18. The success rates of ening effect of perspective projection. We next consider how
these two schemes were nearly the same. to set the size of the bottom layer modules in terms of camera
We believe the reasons are twofold. Firstly, the padding distance and position.
codewords are probably the same when we apply the same Figure 11 illustrates a typical use case and the camera
mask scheme, while different masks may cause potential position. Suppose the field of view angle of the camera is
conflicts in padding codewords. Secondly, different masks may 30°, and it has an aspect ratio of 1:1. Let the distance from the
make scanning less robust because the use of different masks camera to the center of the top layer pattern be d, the width of
may cause errors in the format information. the top layer pattern be w, and the polar and azimuthal angles
Overall, since the different mask scheme has limited benefits of the camera direction be θ and φ, respectively. We denote the
but greatly increases the computation required, we suggest refractive index of the acrylic plate by n, which has a typical
using the same masks for both left and right QR codes. Unless value of n = 1.5. Since the QR code pattern usually covers
explicitly stated otherwise, all results in the paper thus use the the majority of the captured image when scanning, the camera
same mask scheme. distance d is likely to satisfy 2.4w ≤ d ≤ 3.6w, and so we
may assume d = 3w. (In computing module widths, without
B. Fabrication loss of generality, we also assume the camera is to the right
1) Manufacture: We now consider the fabrication of a of the QR plate, i.e. θ > 0)
real two-layer QR code. We print the top layer pattern on The best camera direction corresponds to a viewing direc-

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
 This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
11

Fig. 10. A fabricated two-layer QR code. Fig. 12. Synthetic images of two-layer QR codes with corrected (left)
and uncorrected bottom module widths (right). Both are taken from the
optimal camera directions. Left: the bottom module width is computed using
camera Equation 11. Right: the bottom module width is set equal to the top module
z width. The modules in the left image are better aligned.

1.5 NeoReader
ZXing

median time cost (s)

QR Droid
d
1.0 i-nigma
y
θ
φ 0.5
x
h
0.0
(5, H) (5, Q) (10, H) (10, M) * (10, L) *
w
Fig. 13. Median scanning times using each reader app for 5 fabricated
Fig. 11. Camera position. examples with varying parameters of version and EC level. ‘*’ refers to a
beautified two-layer QR code.

tion in which the central point of a top layer module just

occludes the central point of the corresponding bottom layer (referred to as corrected bottom module width), while the
module. Given the widths of the bottom layer modules along right image ignores perspective projection and simply sets
x- and y-axes, respectively, denoted wbx , wby , the best camera bottom module width equal to top module width (referred to as
direction is (see the supplementary document for detailed uncorrected bottom module width). The close-ups in Figure 12
derivations of formulae in this section): help to verify that the modules in the left image are better
  aligned.
n(w x
/2) 3) Scanning time: We printed and fabricated five different
θ = arcsin  q b  , φ = 0°, (10) two-layer QR codes. We then invited 5 users to scan the
2
h + (wbx /2)
2
fabricated two-layer QR codes with 4 widely used mobile
where n and h are the refractive index and thickness of phone QR code reader applications (NeoReader, ZXing, QR
the transparent acrylic plate, respectively. Given the camera Droid, and i-nigma). The mobile phone used was a MEIZU
direction, for best alignment between the top and bottom PRO 6s, running Android 7.1.1 (Flyme 6.3.0.2A). Each user
layers, the widths of bottom layer modules (wbx and wby ) are was asked to scan each code twice: the user was asked to align
given by: the camera with the center of the two-layer QR code first, and
  3/2  then turn left (first scan) or right (second scan) to scan the
2 x
h + (wb /2)
2 2
cos θ  two-layer QR code. The scanning process was recorded by a
wbx = wt 1 + √ , screen capture plugin, and the scanning interaction time for

nd h (11) each view was also recorded. In the experiment, the two-layer
QR codes were scanned successfully and decoded correctly in
wbx
 
wby = wt 1 + . every case. Figure 13 gives, for each example, for each reader
2d sin θ app, the median scanning times for the 5 users. The results
While Equations 10 and 11 show how to compute the optimal demonstrate that our fabricated two-layer QR codes can easily
θ, wbx and wby , they are nonlinear. We initialize wbx = wt = be scanned in practice.
1.5 mm and compute these values iteratively. The resulting The supplementary video illustrates the fabricated examples
optimal values are: θ ≈ ±21.57° for version 5 QR code, and and the scanning process.
θ ≈ ±21.49° for version 10 QR code. 4) Instructions for users: Given familiarity with standard
Figure 12 shows two synthetic images of two-layer QR QR codes, users might at first try to scan two-layer QR
codes. The left image takes perspective projection into account codes from the front. Therefore, we recommend placing clear
and sets the bottom module width according to Equation 11 guidance besides such new QR codes to explain how to use

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
 This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
12

them. For example, a two-layer QR code describing an exhibit

in a museum could be accompanied by text labels and arrows
saying ‘English (scan this way)’ pointing from the left, and
‘Chinese (scan this way)’ pointing from the right.

VII. E VALUATION
A. Parameter Evaluation
In this section, we evaluate how features and parameters
in our algorithm affect correction capability and run time.
The features include the merge and reduce operators, and the
parameters are the merge size threshold m and the weight λ Fig. 14. Two synthetic images of the same two-layer QR code, rendered
from different camera directions with different noise levels. Left: θ = −15°,
in simulated annealing. φ = 2°, σ = 32, d = 2.4w, right: θ = 18°, φ = −10°, σ = 16, d = 2.4w.
For each experiment, for each example in Figures 6 and 7,
we ran our algorithm 100 times. The run time and effective
recovery ratio were recorded. In each case, if the effective encodable message length for this setting. We then ran our
recovery ratio was not less than the desired effective recov- algorithm. The generation was considered to be successful
ery ratio (i.e., the median effective recovery ratios over all if the effective recovery ratio E was non-negative when
experiments for an example), we considered the output to be simulated annealing terminated.
acceptable. Finally, we give the acceptability rate and average Table III shows the success rate of our algorithm and the
run time for each example for a given experimental setup. In corresponding message length for each parameter setting. It
some cases, no additional merging occured on increasing the demonstrates that our algorithm is robust for arbitrary input
threshold m, so the acceptability rate and run time remained messages if version and EC level are chosen appropriately.
unchanged. We mark these cases as ‘same’. Our algorithm is always successful for EC levels Q and H. In
Next, we explain each experiment in detail. contrast, the success rate is low for EC levels L and M , which
1) Merge and reduce operators: Table II (top 7 rows) show provide smaller error correction capability. The table suggests
results concerning the merge and reduce process, including: that it is more robust to use EC levels Q or H.
whether or not merge operators and reduce operators were We provide some sample two-layer QR code examples
used, and the value of the merge size threshold m. which encode randomly generated messages in the supple-
The results indicate that use of reduce and merge operators mentary document.
significantly increases the acceptability rate and decreases
run time. Without reduce and merge operators, it is hard to C. Scanning Robustness
generate acceptable results for complex examples (see Table II
(rows 1 and 2)). For the merge size threshold, m = 300 is We implemented a simple ray tracer to render synthetic
a reasonable compromise, since it achieves a nearly optimal two-layer QR codes. Gaussian noise with standard deviation
acceptability rate, and larger m does little but increase run σ was added to each pixel on the top layer, bottom layer, and
time. In fact, the results show that varying m has little effect on the transparent plate, respectively. We assume the plate has a
the algorithm. Varying m between 30 and 3000 always results transmittance of 0.75. Figure 14 shows two synthetic images
in an acceptability rate over 99%, while run time changes by of the same code rendered from different camera directions
under 10%. There is little to be gained by adjusting m for with different noise levels.
different cases. To test scanning robustness, we conducted experiments with
2) Simulated annealing process: Table II (bottom 4 rows) two settings of version and EC level: (5,H) and (10,H).
shows the effect of changing the simulated annealing weight For each setting, we generated one thousand two-layer QR
parameter λ in the modified optimization target (Equation 9). codes encoding randomly generated messages with appropriate
The results show that using the modified optimization target length. We used the ray tracer to render synthetic images of
(λ > 0) leads to much larger acceptability rates than the these two-layer QR codes from different camera directions
original optimization target (λ = 0) for complex examples. with different noise levels. The synthetic images were rendered
However, for λ > 0, we observe that increasing λ improves with a resolution of 960 × 960 pixels, and were resized to 5
computational efficiency but reduces the acceptability rate. We different resolutions (160, 240, 320, 400 and 480 pixels) using
suggest setting λ = 0.1 provides a good trade-off. bilinear interpolation. Scanning was considered successful if
one of the 5 resized images could be correctly decoded by the
open-source QR code reader ZXing 2 .
B. Robustness for Arbitrary Input Messages
1) Camera direction: Figure 15 shows how the success
We conducted an experiment to evaluate the robustness of rate changes with camera direction. Rows 1 and 3 show
our algorithm for arbitrary input messages. We tested different how success rate η varies with polar angle θ, while rows 2
settings of version (1, 5, 10, 15, and 20) and EC level (L, M , and 4 show how success rate η varies with azimuthal angle
Q, and H). φ. When computing success rate η for a polar angle θ, we
For each parameter setting, we first generated 1,000 pairs
of random messages in alphanumeric mode with maximal 2 ZXing: https://code.google.com/p/zxing

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
 This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
13

TABLE II
E VALUATION OF MERGE AND REDUCE OPERATORS ( TOP 7 ROWS ), AND EVALUATION OF MODIFIED OPTIMIZATION TARGET ( BOTTOM 4 ROWS ). W E GIVE
ACCEPTABILITY RATE ( ABOVE ) AND AVERAGE RUN TIME ( BELOW, IN SECONDS ), FOR EACH EXAMPLE , FOR EACH SETTING . ‘*’ REFERS TO A
BEAUTIFIED TWO - LAYER QR CODE .

Fig. 6 Fig. 6 Fig. 6 Fig. 6 Fig. 7 Fig. 7 Fig. 7 Fig. 7 Fig. 7 Fig. 7 Fig. 7 Fig. 7
row 1 row 2 row 3 row 4 row 1 row 2 row 3 row 4 row 5 row 6 row 7 row 8
(2,Q) (3,H) (10,L)∗ (10,M )∗ (2,M ) (8,Q) (12,H) (17,H) (9,L)∗ (13,L)∗ (13,M )∗ (16,Q)∗
no reduce, no merge 74% 81% 0% 0% 77% 0% 0% 0% 29% 0% 0% 0%
λ = 0.1 0.770 0.948 - - 0.638 - - - 2.089 - - -
reduce, no merge 100% 100% 22% 83% 100% 89% 100% 60% 100% 100% 100% 31%
λ = 0.1 0.493 0.399 0.384 0.381 0.313 0.843 1.516 2.768 0.855 0.398 0.325 0.487
reduce, merge 100% 100% 99% 100% 100% 99% 100% 100% 100% 100% 100% 100%
m = 30, λ = 0.1 0.463 0.354 0.340 0.347 0.265 0.640 1.091 2.024 0.791 0.363 0.293 0.449
reduce, merge 100% 100% 99% 100% 100% 100% 100% 100% 100% 100%
same same
m = 100, λ = 0.1 0.444 0.338 0.332 0.241 0.617 1.023 1.857 0.793 0.362 0.436
reduce, merge 100% 100% 100% 99% 100% 99% 100%
same same same same same
m = 300, λ = 0.1 0.422 0.332 0.243 0.619 1.018 1.827 0.782
reduce, merge 100% 100% 100% 99% 100% 100% 100%
same same same same same
m = 1000, λ = 0.1 0.431 0.335 0.234 0.622 1.028 1.858 0.790
reduce, merge 100% 100% 100% 100% 100%
same same same same same same same
m = 3000, λ = 0.1 0.455 0.343 0.663 1.099 2.059
reduce, merge 100% 100% 99% 100% 100% 1% 0% 0% 100% 100% 100% 100%
m = 300, λ = 0 0.426 0.329 0.351 0.358 0.244 0.599 - - 0.787 0.368 0.286 0.437
reduce, merge 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100% 100%
m = 300, λ = 0.03 0.430 0.340 0.343 0.353 0.242 0.652 1.103 1.935 0.792 0.367 0.283 0.426
reduce, merge 100% 100% 100% 100% 100% 98% 100% 100% 100% 100% 100% 100%
m = 300, λ = 0.20 0.425 0.325 0.333 0.342 0.244 0.604 0.978 1.792 0.786 0.365 0.288 0.447
reduce, merge 100% 100% 100% 100% 100% 96% 100% 100% 100% 100% 100% 100%
m = 300, λ = 0.50 0.418 0.319 0.336 0.371 0.234 0.580 0.937 1.714 0.782 0.364 0.292 0.467

TABLE III bottom module width (green curve), respectively. The results
ROBUSTNESS FOR ARBITRARY INPUT MESSAGES : SUCCESS RATE OF OUR show that using corrected bottom module width (Equation 11)
ALGORITHM , AND CORRESPONDING MAXIMAL ALPHANUMERIC MODE
MESSAGE LENGTH FOR DIFFERENT SETTINGS OF VERSION AND EC LEVEL . increases success rate and improves scanning robustness.
In all plots of Figures 15–17, we also provide scanning
EC Level H Q M L success rates for standard QR codes (blue curves). Compared
Version suc. rate len suc. rate len suc. rate len suc. rate len
1 100% 10 100% 16 95.3% 20 4.6% 25 to standard QR codes, two-layer QR codes have a lower
5 100% 64 100% 87 18.4% 122 0.0% 154 success rate due to damage introduced during the generation
10 100% 174 100% 221 0.4% 311 0.0% 395 process. However, they still retain a high success rate if camera
15 100% 321 100% 426 0.0% 600 0.0% 758
distance and direction are appropriately set.
20 100% 557 100% 702 0.0% 970 0.0% 1249
4) Same versus different masks: While the different mask
scheme described in Section VI-A2 can slightly increase
the effective recovery ratio, it can also introduce errors in
randomly selected azimuthal angle φ ∈ [−2°, 2°] accordingly format information. To demonstrate how it affects scanning
to a uniform distribution. Similarly, when computing η for an robustness overall, in Figure 18, we plot success rate η against
azimuthal angle φ, the polar angle θ was randomly sampled polar angle θ using the different mask scheme (orange curve)
from ±[20°, 22°]. In both cases, d was randomly sampled and the same mask scheme (blue curve), respectively. Their
from [2.4w, 3.6w]. The results show that scanning from di- scanning success rates are almost identical. Since the different
rections with polar angle θ ∈ ±[10°, 30°] and azimuthal angle mask scheme brings few benefits but requires 8 times the
[−15°, 15°] is relatively successful. computation, we prefer the same mask scheme.
2) Camera distance: Figure 16 shows how the success rate
changes with camera distance for different noise levels. When VIII. C ONCLUSION
computing success rate η for a camera distance d, we randomly This paper has presented two-layer QR codes which can
selected polar angle θ ∈ ±[20°, 22°] and azimuthal angle encode two independent messages. They can be decoded
φ ∈ [−2°, 2°]. The results indicate that restricting camera separately by changing scanning directions. We have given
distance d ∈ [2.4w, 3.6w] is a good choice for scanning in an automatic algorithm for generating such codes, and demon-
the presence of noise (see Figure 16, right two columns). As strated the robustness of the proposed approach. Beautification
d further increases, the success rate drops as the QR code can be used with these codes, as for standard QR codes. In
becomes smaller and harder to recognize. future, we hope to extend this method to allow more than two
3) Bottom module width: In Figure 17, we plot success messages to be encoded in such a specially designed two-layer
rate η against polar angle θ and azimuthal angle φ, using the structure, and to incorporate more types of code beautification
corrected bottom module width (orange curve) and uncorrected techniques.

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
 This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
14

(5, H), = 0 (5, H), = 16 (5, H), = 32 (5, H), = 48

1.0
one-layer
0.8 two-layer
success rate

0.6
0.4
0.2
0.0
40 20 0 20 40 40 20 0 20 40 40 20 0 20 40 40 20 0 20 40

(5, H), = 0 (5, H), = 16 (5, H), = 32 (5, H), = 48

1.0
one-layer
0.8 two-layer
success rate

0.6
0.4
0.2
0.0
40 20 0 20 40 40 20 0 20 40 40 20 0 20 40 40 20 0 20 40

(10, H), = 0 (10, H), = 16 (10, H), = 32 (10, H), = 48

1.0
one-layer
0.8 two-layer
success rate

0.6
0.4
0.2
0.0
40 20 0 20 40 40 20 0 20 40 40 20 0 20 40 40 20 0 20 40

(10, H), = 0 (10, H), = 16 (10, H), = 32 (10, H), = 48

1.0
one-layer
0.8 two-layer
success rate

0.6
0.4
0.2
0.0
40 20 0 20 40 40 20 0 20 40 40 20 0 20 40 40 20 0 20 40

Fig. 15. Scanning robustness with respect to camera direction. Orange curves: success rate (η) versus camera direction for two-layer QR codes. Blue curves:
success rate for standard QR codes for comparison.

(5, H), = 0 (10, H), = 0 (5, H), = 32 (10, H), = 32

1.0
one-layer
0.8 two-layer
success rate

0.6
0.4
0.2
0.0
1.2 2.4 3.6 4.8 6.0 1.2 2.4 3.6 4.8 6.0 1.2 2.4 3.6 4.8 6.0 1.2 2.4 3.6 4.8 6.0
d/w d/w d/w d/w

Fig. 16. Scanning robustness with respect to camera distance. Orange curves: success rate (η) versus camera distance for two-layer QR codes. Blue curves:
success rate for standard QR codes for comparison.

ACKNOWLEDGMENT R EFERENCES

[1] I. Tkachenko, W. Puech, C. Destruel, O. Strauss, J.-M. Gaudin, and

C. Guichard, “Two-level QR code for private message sharing and
This work was supported by the National Natural Science document authentication,” IEEE Transactions on Information Forensics
Foundation of China (Project Number 61822204, 61521002), a and Security, vol. 11, no. 3, pp. 571–583, 2016.
[2] “hotapp.” [Online]. Available: https://www.hotapp.cn/
research grant from the Beijing Higher Institution Engineering
[3] “Lenticular printing.” [Online]. Available: https://en.wikipedia.org/wiki/
Research Center, and the Tsinghua-Tencent Joint Laboratory Lenticular printing
for Internet Innovation Technology. [4] A. Oliva, A. Torralba, and P. G. Schyns, “Hybrid images,” ACM

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
 This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
15

(5, H), = 0 (5, H), = 16 (10, H), = 0 (10, H), = 16

1.0
one-layer
0.8 corrected
module width
uncorrected
success rate

0.6 module width

0.4
0.2
0.0
40 20 0 20 40 40 20 0 20 40 40 20 0 20 40 40 20 0 20 40

(5, H), = 0 (5, H), = 16 (10, H), = 0 (10, H), = 16

1.0
one-layer
0.8 corrected
module width
uncorrected
success rate

0.6 module width

0.4
0.2
0.0
40 20 0 20 40 40 20 0 20 40 40 20 0 20 40 40 20 0 20 40

Fig. 17. Scanning robustness with respect to bottom module width. Orange curves: success rate for two-layer QR codes with corrected bottom module width
computed by Equation 11. Green curves: success rate for two-layer QR codes with uncorrected bottom module width (equal to top module width). Blue
curves: success rate for standard QR codes.

(5, H), = 0 (5, H), = 32 (10, H), = 0 (10, H), = 32

1.0
same mask
0.8 different mask
success rate

0.6
0.4
0.2
0.0
40 20 0 20 40 40 20 0 20 40 40 20 0 20 40 40 20 0 20 40

(5, H), = 0 (5, H), = 32 (10, H), = 0 (10, H), = 32

1.0
same mask
0.8 different mask
success rate

0.6
0.4
0.2
0.0
40 20 0 20 40 40 20 0 20 40 40 20 0 20 40 40 20 0 20 40

Fig. 18. Scanning robustness with respect to mask schemes. Blue curves: success rate (η) for two-layer QR codes generated using the same mask scheme.
Orange curves: success rate (η) for two-layer QR codes generated using the different mask scheme. Their scanning success rates are almost identical.

Transactions on Graphics, vol. 25, no. 3, pp. 527–532, Jul. 2006. of multiplexed image in QR code,” in 2011 Third International Confer-
[Online]. Available: http://doi.acm.org/10.1145/1141911.1141919 ence on Intelligent Networking and Collaborative Systems. IEEE, 2011,
[5] N. J. Mitra and M. Pauly, “Shadow art,” ACM Transactions on pp. 552–557.
Graphics, vol. 28, no. 5, pp. 156:1–156:7, Dec. 2009. [Online]. [11] Z. Baharav and R. Kakarala, “Visually significant QR codes: Image
Available: http://doi.acm.org/10.1145/1618452.1618502 blending and statistical analysis,” in 2013 IEEE International Conference
[6] S. Ono, K. Morinaga, and S. Nakayama, “Two-dimensional barcode on Multimedia and Expo (ICME). IEEE, 2013, pp. 1–6.
decoration based on real-coded genetic algorithm,” in Evolutionary [12] H.-K. Chu, C.-S. Chang, R.-R. Lee, and N. J. Mitra, “Halftone QR
Computation, 2008. CEC 2008.(IEEE World Congress on Computational codes,” ACM Transactions on Graphics (TOG), vol. 32, no. 6, p. 217,
Intelligence). IEEE Congress on. IEEE, 2008, pp. 1068–1073. 2013.
[7] ——, “Animated two-dimensional barcode generation using optimiza- [13] Y.-S. Lin, S.-J. Luo, and B.-Y. Chen, “Artistic QR code embellishment,”
tion algorithms–redesign of formulation, operator, and quality evalua- in Computer Graphics Forum, vol. 32, no. 7. Wiley Online Library,
tion,” Journal of Advanced Computational Intelligence and Intelligent 2013, pp. 137–146.
Informatics, vol. 13, no. 3, pp. 245–254, 2009. [14] Z. Gao, G. Zhai, and C. Hu, “The invisible QR code,” in Proceedings
[8] S. Ono and S. Nakayama, “Fusion of interactive and non-interactive of the 23rd ACM international conference on Multimedia. ACM, 2015,
evolutionary computation for two-dimensional barcode decoration,” in pp. 1047–1050.
IEEE Congress on Evolutionary Computation. IEEE, 2010, pp. 1–8. [15] G. J. Garateguy, G. R. Arce, D. L. Lau, and O. P. Villarreal, “QR images:
[9] M. Kamizono, K. Shimomura, M. Tajiri, and S. Ono, “Two-dimensional Optimized image embedding in QR codes,” IEEE transactions on image
barcode decoration using module-wise non-systematic coding and coop- processing, vol. 23, no. 7, pp. 2842–2853, 2014.
erative evolution by user and system,” in Proceedings of the Genetic and [16] C. Fang, C. Zhang, and E.-C. Chang, “An optimization model for
Evolutionary Computation Conference 2016. ACM, 2016, pp. 245–252. aesthetic two-dimensional barcodes,” in International Conference on
[10] D. Samretwit and T. Wakahara, “Measurement of reading characteristics Multimedia Modeling. Springer, 2014, pp. 278–290.

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.
 This is the author's version of an article that has been published in this journal. Changes were made to this version by the publisher prior to publication.
The final version of record is available at http://dx.doi.org/10.1109/TIP.2019.2908490
16

[17] S. Wang, T. Yang, J. Li, B. Yao, and Y. Zhang, “Does a QR code Tailing Yuan is a PhD student in the Department
must be black and white?” in 2015 International Conference on Orange of Computer Science and Technology, Tsinghua
Technologies (ICOT). IEEE, 2015, pp. 161–164. University. He received his bachelor’s degree from
[18] A. Mittal, “Generating visually appealing QR codes using colour image the same university in 2016. His research interests
embedding,” The Imaging Science Journal, vol. 65, no. 1, pp. 1–13, include computer graphics and computer vision.
2017.
[19] L. Lin, S. Wu, S. Liu, and B. Jiang, “Interactive QR code beautifica-
tion with full background image embedding,” in Second International
Workshop on Pattern Recognition, vol. 10443. International Society
for Optics and Photonics, 2017, p. 1044317.
[20] K. Fujita, “Expansion of image displayable area in design QR code and
its applications,” in Forum on Information Technology 2011 (FIT2011),
2011.
[21] S.-S. Lin, M.-C. Hu, C.-H. Lee, and T.-Y. Lee, “Efficient QR code
beautification with high quality visual content,” IEEE Transactions on
Multimedia, vol. 17, no. 9, pp. 1515–1524, 2015.
[22] Y. Zhang, S. Deng, Z. Liu, and Y. Wang, “Aesthetic QR codes based on Yili Wang is a senior undergraduate student in the
two-stage image blending,” in International Conference on Multimedia Department of Foreign Languages and Literatures,
Modeling. Springer, 2015, pp. 183–194. Tsinghua University. She plans to pursue a PhD
[23] M. Kuribayashi and M. Morii, “Enrichment of visual appearance of degree in computer science in future. Her research
aesthetic QR code,” in International Workshop on Digital Watermarking. interests include computer graphics and image edit-
Springer, 2015, pp. 220–231. ing.
[24] S. Qiao, X. Fang, B. Sheng, W. Wu, and E. Wu, “Structure-aware QR
code abstraction,” The Visual Computer, vol. 31, no. 6-8, pp. 1123–1133,
2015.
[25] L. Li, J. Qiu, J. Lu, and C.-C. Chang, “An aesthetic QR code solution
based on error correction mechanism,” Journal of Systems and Software,
vol. 116, pp. 85–94, 2016.
[26] M. Kuribayashi, E.-C. Chang, and N. Funabiki, “Watermarking with
fixed decoder for aesthetic 2D barcode,” in International Workshop on
Digital Watermarking. Springer, 2016, pp. 379–392.
[27] M. Kuribayashi and M. Morii, “Aesthetic QR code based on modified Kun Xu is an associate professor in the Department
systematic encoding function,” IEICE Transactions on Information and of Computer Science and Technology, Tsinghua
Systems, vol. 100, no. 1, pp. 42–51, 2017. University. Before that, he received his bachelor and
[28] J.-C. Liu and H.-A. Shieh, “Toward a two-dimensional barcode with doctor degrees from the same university in 2005
visual information using perceptual shaping watermarking in mobile and 2009, respectively. His research interests include
applications,” Optical Engineering, vol. 50, no. 1, p. 017002, 2011. realistic rendering and image/video editing.
[29] C. Chen, W. Huang, B. Zhou, C. Liu, and W. H. Mow, “PiCode:
A new picture-embedding 2D barcode,” IEEE Transactions on Image
Processing, vol. 25, no. 8, pp. 3444–3458, 2016.
[30] C. Chen, B. Zhou, and W. H. Mow, “RA code: a robust and aesthetic
code for resolution-constrained applications,” IEEE Transactions on
Circuits and Systems for Video Technology, 2017.
[31] M. E. V. Melgar, A. Zaghetto, B. Macchiavello, and A. C. Nascimento,
“CQR codes: Colored quick-response codes,” in 2012 IEEE Second In-
ternational Conference on Consumer Electronics-Berlin (ICCE-Berlin).
IEEE, 2012, pp. 321–325.
[32] H. Blasinski, O. Bulan, and G. Sharma, “Per-colorant-channel color bar- Ralph R. Martin recently retired after a long career
codes for mobile applications: An interference cancellation framework,” in visual computing, and is now an emeritus profes-
IEEE Transactions on Image Processing, vol. 22, no. 4, pp. 1498–1511, sor of Cardiff University. He is currently enjoying
2013. life in the Welsh countryside.
[33] H. J. Galiyawala and K. H. Pandya, “To increase data capacity of QR
code using multiplexing with color coding: An example of embedding
speech signal in QR code,” in India Conference (INDICON), 2014
Annual IEEE. IEEE, 2014, pp. 1–6.
[34] Z. Yang, Y. Bao, C. Luo, X. Zhao, S. Zhu, C. Peng, Y. Liu, and X. Wang,
“ARTcode: preserve art and code in any image,” in Proceedings of the
2016 ACM International Joint Conference on Pervasive and Ubiquitous
Computing. ACM, 2016, pp. 904–915.
[35] I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields,”
Journal of the society for industrial and applied mathematics, vol. 8,
no. 2, pp. 300–304, 1960.
[36] “Information technology – automatic identification and data capture Shi-Min Hu received the PhD degree from Zhejiang
techniques – QR code bar code symbology specification,” https://www. University, in 1996. He is currently a professor in the
iso.org/standard/62021.html, pp. 1–117, 2015. Department of Computer Science and Technology,
[37] S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by Tsinghua University, Beijing. His research interests
simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, 1983. include digital geometry processing, video process-
ing, rendering, computer animation, and computer-
aided geometric design. He has published more than
100 papers in journals and refereed conference.
He is editor-in-chief of the Computational Visual
Media, and on editorial board of several journals,
including the IEEE Transactions on Visualization
and Computer Graphics and the Computer Aided Design and Computer &
Graphics.

Copyright (c) 2019 IEEE. Personal use is permitted. For any other purposes, permission must be obtained from the IEEE by emailing pubs-permissions@ieee.org.