==============
Fancy QR Codes
==============
:CreationDate: 2016-11-10 17:06:20
:Id: SW/fancy-qr-codes
:tags: - software
       - perl

You may have seen `sylnsfar's "Artistic QR Code" library
<https://github.com/sylnsfar/qrcode>`_. It produces non-standard QR
codes that incorporate arbitrary pictures, but are nonetheless
machine-readable [#]_.

Of course, I had to understand how it worked ☺

It doesn't take much to find that the magic happens in the ``combine``
function in |myqrpy|_::

  if ver > 1:
    aloc = alig_location[ver-2]
    for a in range(len(aloc)):
      for b in range(len(aloc)):
        if not ((a==b==0) or (a==len(aloc)-1 and b==0) or (a==0 and b==len(aloc)-1)):
          for i in range(3*(aloc[a]-2), 3*(aloc[a]+3)):
            for j in range(3*(aloc[b]-2), 3*(aloc[b]+3)):
              aligs.append((i,j))

  for i in range(qr.size[0]-24):
    for j in range(qr.size[1]-24):
      if not ((i in (18,19,20)) or (j in (18,19,20)) or (i<24 and j<24) or (i<24 and j>qr.size[1]-49) or (i>qr.size[0]-49 and j<24) or ((i,j) in aligs) or (i%3==1 and j%3==1) or (bg0.getpixel((i,j))[3]==0)):
        qr.putpixel((i+12,j+12), bg.getpixel((i,j)))

That code is full of magic numbers, and the multiple nested loops
don't really help legibility much. What's going on in there?

To understand where those numbers came from, I studied `a QR code
tutorial <https://www.thonky.com/qr-code-tutorial/>`_. The most useful
page for our purposes is `the one that explains "function patterns"
<https://www.thonky.com/qr-code-tutorial/module-placement-matrix>`_.

Everything in that function assumes a 3-pixel QR module, so:

* the first block collects the placements of the alignment
  patterns
  
  * but only if the code is large enough to need them (``ver > 1``)
  * and ignoring those that would collide with finder patterns
    (``(a==b==0) or (a==len(aloc)-1 and b==0) or (a==0 and
    b==len(aloc)-1)`` means "top-left, top-right, bottom-left corners")

* the second block replaces pixels in the QR code (``qr.putpixel``)
  with pixels from the fancy picture (``bg.getpixel``) if:

  * they're not in timing patterns (``(i in (18,19,20)) or (j in
    (18,19,20))``)
  * they're not in finder patterns (``(i<24 and j<24) or (i<24 and
    j>qr.size[1]-49) or (i>qr.size[0]-49 and j<24)``)
  * they're not in alignment patterns (``(i,j) in aligs``)
  * and two more conditions I'll explain later

So all those magic numbers define the placements of finder / timing /
alignment patterns: those *really* have to be there, otherwise the
scanning / recognition code won't even realise it's looking at a QR
code.

The last two conditions are::

  (i%3==1 and j%3==1) or (bg0.getpixel((i,j))[3]==0)

The second one skips transparent pixels in the picture (``bg0`` is a
ARGB-version of the input picture ``bg``, and the pixel value at
position 3 is the alpha value).

The first one makes sure to leave the central pixel of each 3×3 QR
module untouched: we want the QR data to remain there!

.. _`the procedure outlined before`:

So, another way to get the same result would be:

* paint a normal black & white QR code
* layer the fancy picture on top of it, honouring the alpha channel
* paint all non-data modules on top
* paint the data modules on top, but only their central pixels

Of course, it's not trivial to know whether a module is part of the
data or of a function pattern, but we're in luck: the |libqrencode|_ C
library `provides us with that information
<https://fukuchi.org/works/qrencode/manual/structQRcode.html#details>`_!
It generates the QR code as a matrix of bytes, and each byte is a
bitfield::

 MSB 76543210 LSB
     |||||||`- 1=black/0=white
     ||||||`-- data and ecc code area
     |||||`--- format information
     ||||`---- version information
     |||`----- timing pattern
     ||`------ alignment pattern
     |`------- finder pattern and separator
     `-------- non-data modules (format, timing, etc.)

The Perl modules |text-qrcode|_ and |imager-qrcode|_ wrap that
library, but do not expose the internal byte matrix. So of course I
wrapped it again myself ☺

|alien-qrencode|_ uses |alien-base|_ to install |libqrencode|_, then
|data-qrcode|_ binds it via |inline-module|_ and provides a Perlish
API (see `the test file </cgit/Data-QRCode/tree/t/qrcode.t>`_ for an
example).

Now, we only need to deal with the actual images: let's use |imager|_,
which seems simple and flexible enough. The `actual code
</cgit/Imager-QRCode-Fancy/tree/lib/Imager/QRCode/Fancy.pm>`_ is maybe
too flexible, but the core of the logic is::

   my $back_image = qr_image($qr_code);

   return $back_image unless $fancy_picture;

   my $front_image = qr_dots_image($qr_code);

   my $target = Imager->new(xsize=>$size,ysize=>$size);
   $target->paste(src => $back_image);
   $target->compose(src => $fancy_picture);
   $target->compose(src => $front_image);

   return $target;

which is a direct translation of `the procedure outlined
before`_.

Once we've installed |alien-qrencode|_, |data-qrcode|_, and
|qr-fancy|_, we can say:

.. parsed_literal::

   perl `overlay-qr.pl`_ 'https://pokketmowse.deviantart.com/art/In-the-Kawaii-of-the-Beholder-177076230' `kawaii-beholder.png`_ `kawaii-beholder-qr.png`_

and get this:

.. image:: kawaii-beholder-qr.png

Or maybe:

.. parsed_literal::

   perl `overlay-qr.pl`_ 'Squirrel Girl is the best' `squirrel-girl.png`_ `squirrel-girl-qr.png`_

and get this:

.. image:: squirrel-girl-qr.png

Notice how the size of the "dots" adapts to the resolution of the
picture (although it could be smarter), and how transparency is
maintained.

.. [#] more or less: I think you need a high-enough-resolution camera
       and some pretty forgiving recognition code

.. _myqrpy: https://github.com/sylnsfar/qrcode/blob/master/MyQR/myqr.py#L51
.. |myqrpy| replace:: ``myqr.py``

.. _libqrencode: https://fukuchi.org/works/qrencode/index.html.en
.. |libqrencode| replace:: ``libqrencode``

.. _`text-qrcode`: https://metacpan.org/pod/Text::QRCode
.. |text-qrcode| replace:: ``Text::QRCode``

.. _`imager-qrcode`: https://metacpan.org/pod/Imager::QRCode
.. |imager-qrcode| replace:: ``Imager::QRCode``

.. _`alien-qrencode`: /cgit/Alien-QREncode/
.. |alien-qrencode| replace:: ``Alien::QREncode``

.. _`data-qrcode`: /cgit/Data-QRCode/
.. |data-qrcode| replace:: ``Data::QRCode``

.. _`qr-fancy`: /cgit/Imager-QRCode-Fancy/
.. |qr-fancy| replace:: ``Imager::QRCode::Fancy``

.. _`inline-module`: https://metacpan.org/pod/Inline::Module
.. |inline-module| replace:: ``Inline::Module``

.. _`alien-base`: https://metacpan.org/pod/Alien::Base
.. |alien-base| replace:: ``Alien::Base``

.. _imager: https://metacpan.org/pod/Imager
.. |imager| replace:: ``Imager``

.. _`overlay-qr.pl`: overlay-qr.pl
.. _`kawaii-beholder.png`: kawaii-beholder.png
.. _`kawaii-beholder-qr.png`: kawaii-beholder-qr.png
.. _`squirrel-girl.png`: squirrel-girl.png
.. _`squirrel-girl-qr.png`: squirrel-girl-qr.png