Beautification of QR Code

Beautification of QR Code

Shreyas J

Student,M.Tech ,Computer Science

T. John Institute Of Technology Bengaluru, India

Dr. Mahesh T R

Head Of The Department,Computer Science

T. John Institute Of Technology Bengaluru,India

Ms. Roopashree S

Asst. Professor,Computer Science

1. John Institute Of Technology Bengaluru,India

   AbstractQuick Response (QR) code is extensively used matrix bar code with the increasing population of smartphones. QR code usually consists of random textures which are not suitable for incorporating with other visual designs e.g. name card and business advertisement poster. Such short- comings of noise-like looks of QR codes are overcome by proposing a systematic QR code beautication framework where the visual appearance of QR code is composed of visually meaningful patterns selected by users, and more importantly, the correctness of message de- coding is kept intact. The proposed work makes QR code from machined-codable only (i.e. standardized random texture) to a personalized form with human visual pleasing appearance.

   KeywordsAesthetic, mobile, QR code, Reed-Solomon codes, saliency, simulated annealing optimization.

   1. INTRODUCTION

      QR code is an matrix bar code containing much more amount of information than its 1D counterpart. It is an information container which can be captured and decoded by smart phones directly. The error correcting capability of OR code since Reed-Solomon (RS) codes have already been integrated into them. Tedious typing of users on the small screen of smart phones are avoided by QR codes. QR code were built based on various sizes in many applications [1]-[5].

      QR code is the most widely been applied to numerous printed materials like posters, books or magazines. The cost of information transfer via QR code is extremely low as it is based on its visual appearance when compared with other technologies where specic hardware are always required.

      When QR code is inserted into the host material like poster

      the noise-like appearance of QR code will disturb the visual design. The major challenge in decoding the QR code on the

      basis of appearance is producing the visual pleasant appearance and not affecting the accuracy of the decoded message. One of the common approaches [6], [7] enforced the QR design on embedding an icon directly. This approach introduces invalid code words in the resultant QR code, where the changeable area is bounded by the error correction capability, that is, the maximum area is usually less than 30% of the whole QR code area (which is determined by the max- imum error correction level of the QR code). In order to deal

      with this problem, an appearance-based QR code beautier is

      Fig. 1. (a) A normal binary QR code. (b) The beautied QR code produced by our approach. The embedded message is taken from http://ieeexplore.ieee. org. Notice that (b) might be decoded a little bit slower because of the nder patterns (pleaserefertoFig.2) are smaller than that of the normal QR codes

      Proposed. This framework can embed visual pleasant images into QR codes without violating the specication for decoding. Several studies [6][11] addressed on the research topics of QR code beautication. The proposed method demonstrate a large changeable area in an asymptotic sense, as compared with existing approaches. Notice that the saliency regions of beautifying the embedded patterns are also taken into consideration during the QR code beautifying process, which generates more visual pleasant results. Fig.1 illustrates an example of applying proposed algorithm to embed the head image of Marilyn Monroe to a standard QR code.

   2. BACKGROUDS OF QR CODE GENERATION

      QR code is a two-dimensional bar code consisting of black and white square blocks where the smallest block (black or white) is dened as the module of a standard QR code. The code word of a QR code consists of 8 bits where one module represents the value of 1 bit (white for logical 0 and black for logical 1). The size of a QR code is determined by the ver- sion number V , V 40 , which corresponds to the size of (17 4V ) (17 4V ) modules. The structure and the

      embedded error correction code of a standard QR code is briefed as following:

      • Structure of QR code

        The nder patterns are located at the three corners in Fig.2. The nder pattern is the most important pattern which enables the detection of the position of a QR code. Besides

        the nder patterns, there are timing pattern, version information and format information areas. For a QR code with version number, there will be alignment patterns for correcting the warping effect.

        TABLE I

        A LIST ABOUT THE NUMBERS OF DATA CODEWORDS AND ERROR CORRECTION CODEWORDS FOR

        DIFFERENT QR CODE CONFIGURATIONS WITH DIFFERENT ERROR TOLERANCE LEVELS

        Fig. 2. The descriptions and locations of function patterns of a standard QR code.

        The nder pattern, timing pattern and alignment pattern are called function patterns of a QR code. The other regions within the green color surrounded square are dened as encoding regions which can be used to store the information and the error correction code words.

      • Error Correction

      QR code utilizes RS codes for providing error correcting capability where the code words are represented by

      and appeared in consecutive modules. There are 4 error

      1. Data Analysis Stage: The information is analyzed in the data analysis stage which determines the error correction level and the encoding mode (e.g. numeric, alphanumeric). The suitable version and the capacity of QR code are decided in this stage.

      2. Data Encoding Stage: At the data encoding stage, the embedding information is encoded into a bit stream according to the associated encoding mode, the terminator symbols (0000) is added to the end of the bit stream, and then the resultant bit stream is converted to 8-bit data code words. If the number of code words do not reach the capacity of the corresponding QR code, padding code words are added.

      3. Error Correction Encoding Stage: In order to resist the noise during QR code acquisition, RS code is integrated into the standard QR code. RS code is utilized to detect and correct noise induced errors. RS code is very useful for correcting burst errors and is one kind of non-binary linear block codes, where denotes the length of the coding block and represents the length of message (i.e.the number of data code

         correction levels (i.e. L , M , Q and H from low to high)

         which can recover 7%, 15%, 25% and 30% error code words of the whole QR code. A QR code contains multiple RS

         words). The length of parity code word is n k

         correct up to t error, where t is calculated as

         t n k

         RS code can

         (1)

         codes, where one RS code is sufcient to store the message in

         2

         general. The remaining RS codes are usually used to store non meaningful messages.

         QR code with version number and correction level is

         and x

         values

         denotes the largest integer smaller than x. The

         denoted as (10, L). Table I shows a list about the numbers of data code words and error correction code words for different QR code congurations with different error tolerance levels. Since the target of QR code beautication is to nd the valid code words for achieving visual pleasing appearance within the search space, Table I describes the difculty of QR code

         of n and k are xed in standard QR codes for a given version number and an errr correction level. The errors are detected by checking the syndromes, denoted as S(x) , which are calculated by multiplying the parity-check matrix, H , with a

         given RS code word, C(x) , that is

         beautication because of tremendous number of possible

         S(x) H (x).C(x)

         (2)

         combinations.

         A. The Flow of QR Code Generation

         Fig. 3 illustrates the ow chart for generating a standard QR code, which includes the data analysis, the data encoding, the error correction encoding, and the placement and masking stages.

         The dimension of the parity check matrix H is (n k) n , and C(x) is an n 1 column vector. The verication process of legal RS code words can be represented as:

         1 1

         …

         1 c1

         0

         different regions of a QR code. Fig. 4 shows an example of

         n 1

         n 2

         …

         1 c = 0

         the place- ments of a given message which consists of data

         2

         code words (i.e. the information code words and the padding

         …

         …

         …

         … …

         …

         n k 1 n 1

         ( n k 1 )n 2

         …

         1 c

         0

         code words)

         n

         where is primitive root in a finite field F, and both and F are specied in the QR code standard. Notice that both the addition and multiplication operations here are dened over the nite eld F instead of the real eld R.

      4. Placement and Masking Stage: There are 3 kinds of code words (information, padding and parity) embedded in

         Fig. 3. The flow chart of a standard binary QR code generation.

         Ri , Rp and Re respectively.

         Fig. 5. The 8 mask patterns defined in the QR code standard.

         The masking operation is utilized to eliminate the situations that the appearance of the encoded code words in the placement regions are identical to those of the function patterns. Fig. 5 shows the 8 mask patterns that are used in QR code generation [12]. The masking operation (i.e. XORing a

         chosen mask pat- tern) is the main reason for producing the noise-like appearance of QR code.

   3. RELATED WORK

      There are lots of studies [6][11], [13], [14] dealt with the QR code beautication by using different approaches. These research works can be classied into three categories: direct embedding, masking effect elimination in padding regions, and modifying the RS codes.

      • Direct Embedding

        Brute force embedding [9]-[11] will introduce invalid code words in the generated QR codes. This approach has to incorporate the highest error correction level.

      • Masking Effect Elimination in Padding Regions

        The embedded message is separated from the padding data with specied termination symbols. The decoded message will not be affected by the values in the padding regions.

      • RS Code Modification

      The research works [8], [14] proposed modifying the RS codes to beautify the corresponding QR code which provides a more exible approach as compared with the other beautication methods.

      However, these studies did not take the saliency of the em- bedding image into consideration. The proposed system deals with the QR code beautication by seamlessly incorporating the saliency perception in to a global optimization process.

   4. THE PROPOSED METHOD

      A standard QR code only denes the binary QR code. The issue of embedding color images into a QR code will be addressed. The incorporation of QR code beautication and simulated annealing will be demonstrated.

      Fig. 6. The flow chart of the proposed QR code beautifier.

      1. Saliency Consideration and Formulation

         module mj is equivalent to changing the value of one bit in an RS code- word (one code word is represented by 8 bits). The positions of the corresponding 8 modules of the i-th RS code

         word Ci are denoted as a data block Bi .

         For an n, k -RS code without embedding message, let

         A denote the set of randomly selected k RS code words

         computed to assist the saliency consideration. The computation of saliency map SI is conducted as: set SI ( pj ) 1(or 0) if the image pixel p j belongs to the foreground (or background). The fore- ground/background separation is achieved based on the widely used segmentation

         tools. The edge map EI is generated by using an edge

         c

         with assigned values from the image I and Uc represent the set of the remaining n k code words whose values are

         detector, such as the widely used canny edge detector.

         In order to minimize the visual saliency perception distortion in IQ , the corresponding energy (or distortion)

         computed by substituting the assigned values of Ac into (3).

         function can be dened as:

         The values of n and k are determined by the current QR code parameters (i.e. the version number and the error correction level). The target of QR code beautication is therefore

         e(I, IQ ) 1Dh (IQ I ) 2 Dh (S1 S1 ) 3 Dh (E1 E1 ) (4)

         Q Q

         Q Q

         where Dh represents the Hamming distance and 1~3 are the

         equivalent to nd an optimal Ac which minimizes the visual distortion.

         weighting coefcients.

         Notice that IQ is determined by the selection of Ac. As a

         The visual importance (or saliency) of a pixel p j should

         result, the QR code beautification can therefore be formulated

         as an optimization problem, that is,

         therefore be taken into consideration for the selection of

         Ac .

         min e ( I , IQ ). (5)

         The saliency map SI

         and edge map EI

         of an image I are Ac

         Since the space of Ac is in the order of Cnk=

         C Q

         C Q

         Algorithm: Simulated annealing optimization 1: AC A0 ;e e(I,I0 )

         2: u 0

         3: while u < umax do

         4: T (umax u/ umax)

         next

         next

         5: Ac Neighbor(AC) 6: enext e(I,IQnext)

         c

         c

         7: if p(e, enext, T) > R(0,1) then 8: AC A next ; e enext 9: end if

         10: u (u+1) 11: end while

         Algorithm 2 Swapping Algorithm

         n! k!(n-k!))

         • Neighbor(Ac)

           We try to make the neighboring state of still contains the visual salient regions with high probability. The selection of is based on the weight of RS codeword , which can be computed by the Hamming

           weight of block , that is

           Ws(Ci)=1+Wh (Si (Bi)), (6)

           where denotes the Hamming weight and rep- resents the block in the saliency map . Equation

           (6) implies that the weight of RS codeword is pro- portional to the visual saliency of it, and the constant 1 is added to avoid the denominator becoming zero in the step 4 of Algorithm 2. The initial is generated by randomly choosing among the codewords with probabil- ities proportional to the associated image saliency (i.e. ).

           The codewords in are generated by swapping the elements between and . The swapping algorithm is described in Algorithm 2.

           P (e , enext , T)

           1: VC is a queue with sorted code words in US by ws

           descending order

           2: for all Cu Vc do

           3: Randomly select a codeword Ca Ac

           4: If(ws( Cu ) / ws (Ca)+ws(Cu))>r(01) then 5: Ac U {Cu} \ {Ca}

           6: Uc U {Ca} \ {Cu}

           7: end if

           8: end for

      2. Incorporation With Simulated Annealing Optimization

         In order to deal with these challenges and achieve the goal of generating visual pleasant QR codes, simulated annealing (SA) optimization is chosen as our optimization mechanism, where the visual saliency consideration is also integrated seamlessly. SA optimization is a global optimization mech- anism which can achieve the global optimal solution with probability 1 with the expense of long execution time. In gen- eral usage, the global optimization will be early terminated when the results are good enough. SA optimization is chosen because we can easily integrate the saliency consideration during optimization.

         Algorithm 1 showsthe SA optimization adopted for beauti- fying the QR code. The components contained in Algorithm 1 are detailed in the following:

         r(0,1)

         The random number represents a real number randomly selected from the range with uniform distribution.

         P (e , enext , T)denotes the acceptance probability which is

      3. QR Code Beautification With Color Image

         The original standard QR code only defined in binary format, where the interpretation of image colors is done and depends on the QR decoder used. A QR code decoder will convert the color image into binary image before conducting the message decoding. We can reduce the noises induced from the conver-sion of color image to binary image by incorporating a better equipped decoder. However, the color conversion process may be different from decoder to decoder. Therefore, we take the color conversion of the open source QR decoder4 as our reference.

      4. Maximization of Beautification Regions

      The changeable regions of a QR code are limited to the padding codeword region, , and the parity codeword re- gions, , in our work. We can further enlarge the changeable regions by incorporating with the direct embedding method. The data codeword regions can be directly modified as long as the induced error can be recovered. Fig. 7 demonstrates an example of beautification region enlargement where the visual quality of QR code is further improved, within the error correction capability. Table II compares the asymptotic sizes of changeable regions that can be achieved for different QR code beautification methods.

   5. EXPERIMENTAL RESULTS

      Fig. 8 shows part of the test data, where a (15, )-QR code is used during the experiments and the direct embedding is not

      applied. We empirically set , and in

      (4) during QR code beautification. Both the subjective and the

      objective metrics will be applied to evaluate the performance of the proposed QR code beautification framework.

      Fig. 7. (a) A beautified QR code without introducing any error codewords.

      (b) Visual noise reduction by introducing error codewords. (c) The marked square shows the visual difference between (a) and (b).

      The research work [8] is the latest publication about QR code beautifica-tion which provides more flexibility and larger changeable area than those of previous works. It is our belief that the research work [8] is the state-of- the-art in the area of QR code beauti-fication. Therefore, it is realized and taken as our comparison target. There are 3 methods proposed in the research work [8] where only method 1 is compared in this work. This is because method 1 is the core basis of method 2 (user intervention is in-volved) and method 3 (fine-resolution version replacement is included). In other words, both method 2 and method 3 can be treated as the extensions of method 1; therefore, only the core algorithm, method 1 is chosen as the reference for comparison. Notice that, in the comparison, the same experimental assign- ments, such as setting the modules to be a visual pleasing image and restricting the system behavior follows (3), are assumed to both approaches. That is, only the selection procedures of the modules are different in the experiment.

      1. Correctness of QR Code Decoding and Corresponding Performances

         The correctness of decoded messages have been verified on several different mobile phones and QR code decoders, which are reported in Table III. The beautified QR codes with color image embedding will have slightly lower successful decoding rate as compared with their binary counterparts. The perfor-mance loss might come from the pre- described mismatch of color conversion among the decoders of different smart phones. Notice that the successful decoding rates are the same for both our method and the research work [8], since the decoding error is only introduced from the color mismatch between the actual QR decoders on the mobile phones and the reference QR decoder (i.e. Google ZXing) adopted in this work. Table III demonstrates decoding rates of both Binary and Color (15, ) and (15, ) QR codes, in which the embedded lengths are different (please refer

         Fig. 8. Some examples of beautified QR codes. (a) The QR codes are generated by [8], and (b) the QR codes generated by our approach. The embedded message is http://ieeexplore.ieee.org, and a (15, )-QR code is used.

         to Table I for details). Notice that, even though the embedded message lengths are different, the successful decoding rates of (15, ) and (15, ) QR codes are the same. For QR codes with larger version sizes (say ), the correctness of decoding will be reduced signifi cantly, because the corresponding mod-ules on a QR code are too small to be recognized correctly for

         a normal mobile phone. This unstable decoding behavior also occurs in traditional QR codes without beautification, when the version size is too large.

      2. Comparison of Time Complexity and Visual Quality

         Fig. 9 demonstrates the comparison results of time

         com-plexity and that of visual quality between the proposed method and the research work [8]. Fig. 9(a) shows that the visual quality of the proposed method for the whole QR code is slightly lower than that of the study [8]. However, Fig. 9(b) demonstrates the visual quality of our method for the salient regions is almost 10 times better than that of [8]. Notice that, in these comparisons, the visual quality is measured by the Hamming distance between the original image and the designed QR code . Fig. 10 illustrates the visual differences of the beautified QR codes and the corresponding noise distributions between our method and the research work.

         Fig. 9 also shows that the visual quality (in terms of Ham- ming distance) is getting converged when the iteration number is greater than 600. The absolute execution time of the proposed method is about 10 second on a PC with MATLAB implemen-tation, when the iteration number equals to 600. The proposed method processes the codewords sequentially and iteratively where the maximum iteration number in our experiment is set to 1000.

      3. Experiments on Various QR Code Configurations

         To examine the impact of QR code configuration on the per- formance of QR code beautification, the required time com- plexity and the visual distortion of the proposed algorithm for various QR code configurations (i.e. different settings of QR code with different sizes of embedded messages) are investi- gated. We increase the size of the embedded message to 5% and 20% of the total information capacity of a given QR code ver- sion, and evaluate the visual distortion (in terms of Hamming distance) on

         Fig. 9. The comparison of time complexity and the visual quality between the proposed method and the research work [8]. -axis represents the averaged number of iterations among the test data and -axis shows the Hamming distance between and . The visual distortion is expressed based on

         1. the whole QR code and (b) the salient regions of image .

            Fig. 10. (a) The beautified QR code generated by [8]. (b) The beautified QR code generated by our approach. (c) The noise distribution of (a). (d) The noise distribution of (b).

            the salient and the whole regions for each one of the QR codes (from (15, ) to (35, )), listed in Table IV.

            Table IV demonstrates the required time complexity and the corresponding visual distortion for various QR code configu-rations. In fact, the required time complexity of the proposed approach is about V , where is the size (version size)

            maximum iteration number is set to 1000 initially, we examine the convergence of each codeword based on the corresponding Hamming distance, and the codeword with converged result (i.e., the corresponding Hamming distance is less than a given threshold or the distance remains the same for a few itera-tions successively) will be skipped during the computation. The

            numbers of early converged codewords are also listed in Table IV. Notice that theQR codes with higher error correction levels or larger embedded message lengths will have more number of early converged codewords. The visual quality (in terms of Hamming distance) of a QR codes embedded with a large-sized message is difficult to be

            improved, the

            Fig. 11. The distortions in the salient regions of the above two enlarged and beautified QR code examples are (a) 0.33% and (b) 29.91%, respectively. Notice that these QR codes may take a longer time for decoding (or not decodable) due to their large version sizes.

            corresponding visual quality will easily reach to a fixed state, and therefore, early terminate the optimization process. Of course, QR codes embedded with short URLs will converge quickly, since almost all the area of QR codes are changeable and can be assigned with the visual pleasing images at early stages of optimization. The time complexity and the visual distortion reported in Table IV can be used as references for users to select proper configurations of the proposed QR code beautification schemes. We also compare the visual appearance results between the previous work [8] and our method when the embedded message size is enlarged (i.e. 20% of the total capacity) and the results are illustrated in Table V. As compared with the previous work [8], the proposed method improves the visual appearance significantly in the salient regions with the expense of little increased distortion in the whole region even if the embedded message size is enlarged.

      4. Subjective Evaluation

      We invited 20 participants (12 males and 8 females) with ages, ranging from 23 to 55 who are not engaged in this work. We ask the participants rating about the attractiveness, clearness

      the annoyance level of noise, and the visual similarity between and . The scores are ranged from 1 to 7 points to express the level of opinions. The subjective evaluation results, presented in Fig. 12, show that the proposed method performs statistically significant better than [8] in all aspects. This result reflects that the proposed method does successfully address the issues of visual saliency perception

      Fig. 12. The comparison of user study between the work [8] and our ap- proach. The user study shows that our approach is statistical significantly

      better in all aspects.

   6. DISCUSSION

      The color image beautification will be affected by two major factors: the resolution of QR code and the color conversion. Since one module (i.e. the smallest block) in a QR code corresponds to one pixel of a color image, the available resolution of QR code is quite limited; therefore, the color image embedded in a QR code should be resized to fit the resolution of the cor-responding QR code. Of course, we can increase the version of QR code to obtain higher resolution for better color image rep-resentation, but the increased version of QR code will impose a burden on QR code decoder, which may result in a longer de-coding time or even un-decodable fault. In our experiences, a normal QR code decoder may not capable of decoding the QR codes with version size larger than 20. Of course, the decoding ability depends on the capability of equipped QR code decoder on the mobile phone.

      SA optimization framework is adopted in this work because the saliency considerations can be seamlessly integrated into the choice of neighboring states (c.f. (6)). Since SA optimiza- tion has an explicit state transition behavior as compared with other optimization methods (e.g. Neural Networks), we can inte-grate the saliency consideration into the state transition behavior easily. We do believe that SA optimization is just one of the pos-sible solutions to accomplish the required beautification task. The ease of implementation and the ability to achieve seamless integration makes SA on the top of the candidate list. Actually, as long as the saliency considerations can be successfully in-corporated into the optimization procedure, other optimization approaches, such as Genetic Algorithm and Neural Networks, may also be utilized in the proposed framework.

   7. CONCLUSION

In this paper, we present a systematic framework for QR code beautification. We integrate the visual saliency consideration seamlessly with simulated annealing optimization. The beautified QR code is evaluated by both subjective and objective metrics which all show the superiority of the proposed method. Since QR code has already been ubiquitously utilized in this mobile computing era, the beautification of QR code is a problem with high impact. This work can greatly enhance the aesthetic perception of QR codes for users. We expect this work can extend the usage of QR codes in various mobile multimedia applications.

ACKNOWLEDGMENT

The authors would like to thank the anonymous reviewers for their valuable comments and suggestions to improve the quality of this work.

REFERENCES

1. G. O. Young, Synthetic structure of industrial plastics (Book style with paper title and editor), in Plastics, 2nd ed. vol. 3, J. Peters, Ed. New York: McGraw-Hill, 1964, pp. 1564.

2. W.-K. Chen, Linear Networks and Systems (Book style). Belmont, CA: Wadsworth, 1993, pp. 123135.

3. H. Poor, An Introduction to Signal Detection and Estimation. New York: Springer-Verlag, 1985, ch. 4.

4. B. Smith, An approach to graphs of linear forms (Unpublished work style), unpublished.

5. E. H. Miller, A note on reflector arrays (Periodical styleAccepted for publication), IEEE Trans. Antennas Propagat., to be published.

6. J. Wang, Fundamentals of erbium-doped fiber amplifiers arrays (Periodical styleSubmitted for publication), IEEE J. Quantum Electron., submitted for publication.

7. C. J. Kaufman, Rocky Mountain Research Lab., Boulder, CO, private communication, May 1995.

8. Y. Yorozu, M. Hirano, K. Oka, and Y. Tagawa, Electron spectroscopy studies on magneto-optical media and plastic substrate interfaces(Translation Journals style), IEEE Transl. J. Magn.Jpn., vol. 2, Aug. 1987, pp. 740741 [Dig. 9th Annu. Conf. Magnetics Japan, 1982, p. 301].

9. M. Young, The Techincal Writers Handbook. Mill Valley, CA: University Science, 1989.

10. J. U. Duncombe, Infrared navigationPart I: An assessment of feasibility (Periodical style), IEEE Trans. Electron Devices, vol. ED- 11, pp. 3439, Jan. 1959.

11. S. Chen, B. Mulgrew, and P. M. Grant, A clustering technique for digital communications channel equalization using radial basis function networks, IEEE Trans. Neural Networks, vol. 4, pp. 570578, July 1993.

12. R. W. Lucky, Automatic equalization for digital communication, Bell Syst. Tech. J., vol. 44, no. 4, pp. 547588, Apr. 1965.

13. S. P. Bingulac, On the compatibility of adaptive controllers (Published Conference Proceedings style), in Proc. 4th Annu. Allerton Conf. Circuits and Systems Theory, New York, 1994, pp. 816.

14. G. R. Faulhaber, Design of service systems with priority reservation, in Conf. Rec. 1995 IEEE Int. Conf. Communications, pp. 38.

15. W. D. Doyle, Magnetization reversal in films with biaxial anisotropy, in 1987 Proc. INTERMAG Conf., pp. 2.2-12.2-6.