二维混合瓦片的逆向工程 [英] Reverse engineering of mixed tiles of QR code

问题描述

我有25个瓷砖，每个94x94px，以前分割的QR码（470x470px）。我需要通过将所有可能的图块组合成一个图像来恢复QR码。 3个瓷砖假设是位于NW，NE和SW角落的锚或大方块。因此，我们剩下22个未知位置的瓷砖。如何使用ImageMagick生成所有可能的组合？

更新：

我的第一个方法是生成文本文件（稍后将作为输入提供给 - 根据知识共享署名 - 相同方式共享3.0）：

也许OP有机会放置正确的和/或合理的版本和格式信息模式，以及对齐和时间模式（在3 位置之上他已经知道的模式）...

对我来说最有希望的策略似乎按以下顺序进行：

1. 首先确定包含路线模式的这六个瓷砖


2. 了解您需要多少选择这两个（在先前确定的六个）对齐图案瓦片中h介于3个位置模式图块之间（记住：他们也需要提供有效的计时模式）


3. 你能支付吗？你现在的硬盘存储？ ： - ）

Trivia事实：在470x470模块的QR码中应该出现 7 * 7 - 3 = 49 -3 = 46 对齐模式。

---

更新3

OP提供 ZIP文件，里面有5个单独的图块，文件名下 tile_0.png ， tile_1.png ，... tile_24.png ，现在看来这项工作比我原先估算的要容易得多。我没有考虑到什么（OP的问题也不清楚，或者我做了什么错误的假设）：

1. 原始二维码包含完整的相当区域。


2. 25个分离的图块不会沿着QR 模块边框急剧切割，但是直接通过这些模块的肉。

这两个事实共同使得它更容易拼凑他提出了这个难题。

为了让每个人都了解25件作品的样子，我创建了一个网格，具有以下特点：

1. 每个图块都使用其原始文件的名称进行注释。


2. 每个图块分隔3个像素来自下一行和下一列。


3. 有一个彩色背景，可以清楚地显示（白色）安静区条。

（ 更新 - 不幸的是，OP编辑编辑我的插图并用25个瓷砖中的9个用大黑方块遮盖，这样你就再也看不到它的样子了。但如果你很聪明...... :)结果如下：

看着这些瓷砖，考虑到可见的白色静区边缘条，以下内容可以马上说明：

假设每个瓷砖的方向仍然是原始的...

1. tile_24.png 属于最终二维码图片的右上角。


2. tile_11.png 属于最终二维码图片的左上角。


3. tile_6.png 属于最终QR码图片的左下角。


4. tile_4.png 属于最终二维码图片的右下角。


5. 12个图块， tile_8.png ， tile_9.png ， tile_10.png ， tile_13.png ， tile_14.png ， tile_15.png ， tile_16.png ， tile_17.png ， tile_18.png ， tile_19.png ， tile_22 .png 和 tile_23.png ，因为他们的安静区域边缘条属于边缘位置。


6. 还有更多限制（例如 tile_17.png ， tile_22.png 和 tile_13.png 属于到顶部边缘，17可能在第二个位置，旁边是11）...


7. ...但我不会在这里解决完整的难题。

更新4

嗯...只是盯着上面的图片大约5分钟并且需要更多笔记，我想出了这个：

 
 11 17 22 13 24 
 18 21 7 2 9 
 14 0 20 3 10 
 15 5 1 12 23 
 6 16 8 19 4 
 

这是我在这件事上的最后一个暗示。 ： - ）

---

_{我甚至不知道奖项是什么： - （}    

I have 25 tiles, each 94x94px, of previously splitted QR code (470x470px). I need to recover QR code by combining all possible tiles into one image. 3 tiles suppose to be "anchors" or big squares located at NW, NE and SW corners. Therefore we have remaining 22 tiles with unknown position. How to generate all possible combinations using ImageMagick?

UPDATE:

My first approach is to generate text file (which later will be fed to ImageMagick as input) with all combinations, taking into account static squares (NW, NE and SW corners). I struggle to understand how to interact with IM command line interface. How to pass text file with commands to tell IM what to do?

UPDATE 2

Thanks Kurt Pfeifle for clarification. Indeed it would take enormous amount of time and resources to go this way. Maybe I can do it in old fashioned way. The way all puzzles get solved: print out, cut manually to 25 tiles, and combine it. I know this may sound ridiculous on SO but that is only possible solution at the moment I can think of. If I decide to go this way I nee to know the rules how QR code is generated. I know about location of big squares at 3 sides. What else do I have to know?

Maybe there is more elegant way to do it? (Please don't suggest split to tiles and import to Photoshop. Tried. Wasted a lot of time.)

UPDATE 3

Here is the QR code and tiles I split it using ImageMagick.

QR code and tiles

UPDATE 4

I suspect that QR have been rotated 180 degrees CW because big squares has white space which most likely located at NE, SW and SE corners. I am not sure about if rotation to each tile was applied but as far as I worked with them in Photoshop, at least 7 aligned without rotation (*not 100% sure though)....

UPDATE 5

As I understand writing algorithm would be a bit tricky but much more helpful than doing brute-force search. The constraints should be like:
1. the width and height of lines of 2 connected blocks must correspond to some range of px (ex.: cannot connect 2 blocks if it produces 1px line or dot)

UPDATE 6

Thank You, Sir! I started from wrong assumption about corner elements, that was my problem leading me to nowhere. After I got idea how corner elements should be placed at other is a few minutes work in Photoshop. Although even with wrong placement of corner blocks I got to point where around 10 elements was aligned right into one big block. Now I challenge to come up with algorithm to align these tile completely automatically based on set of rules (Python+ ImageMagick's MagickWand API)

解决方案

The task ahead is a special case of a general mathematical field, combinatorics. (Sorry, I'm not a native English speaker, and I'm not a mathematician either. So I'm not sure if this is the correct English technical term for the field.)

Combinatorics has a few generally proofed rules about how many combinations/orders of N distinct objects are possible if there are N slots for the objects and each object must be placed into one slot at a time.

Take the most simple example first: 1 element, 1 slot. There is only one option.

Next, two elements: a + b, and two slots: 1 + 2. There are two options:

1. a,b
2. b,a.

Three elements: a + b + c, and three slots: 1 + 2 + 3. There are now six options:

1. a,b,c
2. a,c,b
3. b,a,c
4. b,c,a
5. c,a,b
6. c,b,a.

This general rule (which can easily be proven by applying the generic mathematical proof method of complete induction) is:

"For N elements, there are N! different arrangements."

where N! denotes the factorial of N, meaning to be the product of all positive integers less than or equal to N. For example:

5! = 5 * 4 * 3 * 2 * 1 = 120

As you can see the factorial function is growing rather fast... :-)

Your general requirement is equivalent to put 22 tiles into 22 positions. A quick -- har!,har! :) -- calculation shows that

22! = 1.124.000.727.777.607.680.000

22! is (coincidentally!) 22 digits long. It also contains 4 trailing zeroes (which constitute 18.18% of the whole number).

So I propose some job sharing between us:

1. Your part is this: please start to generate or write the "textfile with all the combinations" you suggested in your question.
2. My part: I will, by the time you're done with it, be able to provide you a simple shell script to generate all the QR codes you are looking at.

But before you start to write your textfile with all the combinations, please consider this:

1. My script will read the text file as input line by line.
2. Each line will run trigger 1 ImageMagick command to generate the appropriate QR code image.
3. So you need to provide a text file that holds 1.124.000.727.777.607.680.000 different lines.
4. Since all your text file's lines need to be different from each other (otherwise they'll represent dublettes of two or more combinations), they need a minimum of 23 bytes (22 bytes to name the 22 different tile names -- you can be lazy and name them as single letters -- plus an EOL/CR/NL character).
5. Hence, your text file size is a minimum of 2.4728016 * 10²² Bytes long.
6. So make sure, before you start writing the file, that your computer has enough hard disk space to hold that file.
7. The disk needs to be able to hold 23 billion of TeraBytes (for your text file alone)! That is 23 ZetaBytes (How much storage, again, is the NSA creating for itself in its new data center in Bluffdale?)
8. Oh, and while you're at it, when shopping for large harddisks: maybe you can also consider the space that we'll need for all the QR code images which my ImageMagick script will generate...

I guess you have already a strategy how to select the one (or the few) correct sample(s) out of the totality of eventually re-stitched together QR code you are looking for.

---

Update

I do not want to be totally mean to you. :-)

Maybe you have some other means to reduce the number of 22 "uncertain" tiles... In that case the following hints will help you to arrange all 25 tiles as a 5x5 grid into one image.

Create a 5x5 montage of 25 different images

ImageMagick has the montage command. This allows you to stitch together different images into lines, columns or grids as one single image.

1. Create 25 different images first.
   (These will represent 25 different values of gray, as 100x100 pixels of gray patches.)

    for i in $(seq -w 1 25); do
      saturation="$(( $(echo x${i} | sed 's#x0*##') * 10 ))"
      color="srgb(${saturation},${saturation},${saturation})"
   
      convert          \
        -size 100x100  \
         xc:"${color}" \
         graypatch_${i}.png
     done
   

2. Tile these 25 images into two different grids.
   (The first grid will be ordered along the gray values, the second one will be random.)

    montage            \
      -geometry +1+1   \
       graypatch_*.png \
       grid1.png
   
    montage            \
      -geometry +1+1   \
       $(ls -1 graypatch_*.png | sort -R) \
       grid2.png
   

The -geometry +1+1 parameters are not really required. I only put them in in order to get the small white space into the grid...

The first montage command uses the 25 gray patches as input in the order the shell expands the * wildcard. This order will be alphabetical. Alphabetical order will at the same time match an order of increasing darkness of the gray value, due to the algorithm I chose for the creation of the original 25 patches.

This is the resulting grid1.png:

The first grid is indeed ordered according to the "25 Shades of Grey" (heh,heh!).

This is the resulting grid2.png:

The trick here was to use sort -R. (Note, that the -R for random sorting is only for GNU sort.)

Putting 3 patches into a fixed positions (NW, NE and SW corners)

As the previous examples demonstrate:

1. If you have 25 images, montage will automatically create a 5x5 grid.
2. The individual images will be positioned in the order they appear on the command line: left-to-right first, then top-to-bottom.

Assuming, you name the 3 tiles with fixed positions as:

• 1.jpg, 2.jpg and 3.jpg

Assuming, you name the 22 tiles with "uncertain" positions as:

• {a,b,c,d,e,f,g,...u,v,w}.jpg

Then:

1. To position 1.jpg into the NW corner, put it as the first image on the command line.
2. To position 2.jpg into the NE corner, put it as the fifth image on the command line.
3. To position 1.jpg into the SW corner, put it as the twentyfirst image on the command line.

The rest of your 22 JPEGs you can place into the other positions as you like.

But remember: you have 1.124.000.727.777.607.680.000 different choices for these... :-)

---

Update 2

The OP has added some more info (though not all that was requested):

• Each individual tile has 94x94 pixels.
• The complete QR-Code has 470x470 pixels.

His idea to *"solve it as all puzzles are solved: print out, cut manually to 25 tiles, and combine it" does not look too promising to me...

However, here is some structural information which may help to fix a few of the 22 undetermined tiles into a specific location (or rule them out for other places when puzzling). It is a 45x45 QR code example (originally provided on Wikipedia as "QR Code Structure Example 3" by Bobmath - Licensed under Creative Commons Attribution-Share Alike 3.0):

Maybe the OP has a chance to put correct and/or plausible version and format information patterns in place, as well as alignment and timing patterns (on top of the 3 position patterns he already knows)...

The most promising strategy to me seems go forward in the following order:

1. Identify these six tiles which contain the alignment patterns first
2. Find out how many choices you have to place these two (out of the previously identified six) alignment pattern tiles which go in between the 3 position pattern tiles (remember: they need to provide a valid timing pattern too)
3. Can you pay your hard disk storage now? :-)

Trivia fact: in a 470x470 module QR code there should appear 7 * 7 - 3 = 49 -3 = 46 alignment patterns.

---

Update 3

After OP provided a ZIP file with the 5 individual tiles inside, under the filenames tile_0.png, tile_1.png, ... tile_24.png, it now looks that the job is much easier than I originally reckoned. What I had not taken into account (what also was not clear from the OP's question, or what I made wrong assumptions about):

1. The original QR code contains the full "quite zone".
2. The 25 separated tiles are not cut sharply along the QR module borders, but right through the meat of these modules.

These two facts together make it much more easy to piece together the puzzle he posed.

To give everyone an idea of how the 25 pieces look like, I've created a grid of them, with the following characteristics:

1. Each tile is annotated with the name of its originating file.
2. Each tile is separated 3 pixels apart from the next rows and next columns.
3. There is a colored background to clearly show the (white) "quiet zone" strips.

(Update -- unfortunately, the OP edited my illustration and masked 9 out of 25 tiles with a big black square, so you won't be able to see what it looked like any more. But if you are clever... :) Here is the result :

Looking at these tiles, taking into account the white "quiet zone" edge strips where they are visible, the following things can be stated right away:

Assuming each tile's orientation is still the original one...

1. tile_24.png belongs into the top right corner of the final QR code image.
2. tile_11.png belongs into the top left corner of the final QR code image.
3. tile_6.png belongs into the bottom left corner of the final QR code image.
4. tile_4.png belongs into the bottom right corner of the final QR code image.
5. 12 tiles, tile_8.png, tile_9.png, tile_10.png, tile_13.png, tile_14.png, tile_15.png, tile_16.png, tile_17.png, tile_18.png, tile_19.png, tile_22.png and tile_23.png, due to their quiet zone edge strip belong to an edge position.
6. There are even more restrictions (such as "tile_17.png, tile_22.png and tile_13.png belong to the top edge, with 17 probably at second position, next to 11")...
7. ...but I won't solve the complete puzzle here.

Update 4

Hmmm... just staring at above image for about 5 minutes and taking some more notes, I came up with this:

 11  17  22  13  24
 18  21   7   2   9
 14   0  20   3  10
 15   5   1  12  23
  6  16   8  19   4

That's my last hint in this matter. :-)

---

_{I don't even know what the award is :-(}     

这篇关于二维混合瓦片的逆向工程的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！