解决QR拼图的算法

我正在构建算法，以从相同大小的瓦片数量自动解决/重建QR码。

我的方法：

1. 获得3个正方形中的一个：位置正方形
2. 使用ImageMagic以某种方式获取外部黑色边框的宽度

给出的例子是14px x 14px （更新：它可能是13px×13px）

3. 将其设置为常量：BLOCK_SIZE
4. 开始循环匹配VALID磁贴和已编译的QR码块

VALID是：无与伦比的，而不是3个角落瓷砖（大黑方块）中的任何一个

4.1。 渲染已编译的qr块和1个随机有效磁贴的所有可能组合，直到找到匹配为止

4.2如果找到匹配（可以通过已编译/组合的QR码块的一侧放置图块），则记录匹配

4.3比赛条件：

没有黑色区域的宽度和高度符合以下等式：

AREA_HEIGHT % BLOCK_SIZE == 0 && AREA_WIDTH % BLOCK_SIZE == 0 

现在出现了一些实施并发症：

1. 如何实现匹配tile到tile的算法（或者已编译/组合的QR码块）？

我认为ImageMagic可以解决它。 目标是获得原始的QR码。

ZIP中的QR瓷砖示例

UPDATE

正如我所看到的那样，解决方案缩小以使ImageMagick扫描并找出是否可以将两个图块组合在一起而不破坏QR码的规则。 算法应该尝试并排放置2个区块并扫描边界区域。 诀窍是测量连接瓷砖的黑线/块的宽度和高度。 怎么做？

UPDATE2

如果使用2列宽度为1px的磁贴匹配，则在某些情况下还不够。 例如，两种算法都将这2个图块连接到：

有效

和

无效

正如你在INVALID中看到的那样，第二个瓦片的一部分（右边的那个）被红色箭头去掉了，但是由于1px算法的比较 – 算法并不关心这种情况。 Hance无效QR。

UPDATE3

http://dropcanvas.com/6bl6v

档案包含：

• join.png无效

• 有效的join.png

• src1.png

• SRC2，invalid.png

• SRC2，valid.png

• invalid.png

如果您的算法将加入src1.png和src2-invalid.png则会失败。 这是关于连接的瓷砖最终会产生有效的QR。 我希望你明白我的观点。

UPDATE4

我测试并获得正确的解决方案后，我会接受一个答案。 可能需要一些时间……

更新5：测试

Mark的解决方案似乎一切都是正确的。

Answer 1

我试过这个如下。

1. 浏览所有PNG并提取其北，东，南和西边缘。 如果任何PNG有两个白边，告诉用户它是一个角落。 如果任何PNG有一个白边，告诉用户它是一个边缘。

2. 浏览所有边缘部分。 将每个转换为PBM格式文件并剥离标题和新行，使其只是一个80位长的字符串，每个数字为零或一个为黑色或白色。 计算字符串的校验和，然后反转字符串以考虑正在翻转或旋转的图像，然后重新计算校验和。 将校验和和管道打印成sort以便匹配的边缘一起出现。

这是代码：

 #!/bin/bash # Remove any edges generated in previous runs of this script rm *_[NESW]*png 2> /dev/null rm *_[NESW]*txt 2> /dev/null DEBUG=1 # Process all PNGs for f in *.png; do echo "Processing $f ..." # Get basename of image base=$(basename -s .png "$f") # Get width and height - not actually used at the moment read wh <<< $(identify -format "%w %h" "$f") [ $DEBUG -gt 0 ] && echo " width:$w" [ $DEBUG -gt 0 ] && echo " height:$h" # Extract North edge convert "$f" +repage -crop x1+0+0 +repage "${base}_N.png" [ $DEBUG -gt 0 ] && echo " North edge extracted" # Extract East edge convert "$f" +repage -gravity east -crop 1x+0+0 -rotate 90 +repage "${base}_E.png" [ $DEBUG -gt 0 ] && echo " East edge extracted" # Extract South edge convert "$f" +repage -gravity south -crop x1+0+0 +repage "${base}_S.png" [ $DEBUG -gt 0 ] && echo " South edge extracted" # Extract West edge convert "$f" +repage -gravity west -crop 1x+0+0 -rotate 90 +repage "${base}_W.png" [ $DEBUG -gt 0 ] && echo " West edge extracted" # Test if corner or edge piece n=0 for edge in NESW; do name="${base}_${edge}.png" min=$(identify -format "%[min]" "$name") if [ $min -gt 0 ]; then ((n++)) e=$name fi done [ $n -eq 1 ] && echo " $e is edge-piece" [ $n -eq 2 ] && echo " $name is corner-piece" done EDITED FROM HERE --- # Now convert all edges to text, forwards and backwards to allow rotation for f in *_[NESW].png; do base=$(basename -s png "$f") # Convert to PBM format, remove 2 header lines and make into one line string str=$(convert "$f" -compress none pbm: | sed "1,2d" | tr -d "\n ") echo "$str:$f" str=$(rev <<< $str) echo "$str:$f (flipped)" done | sort 

部分输出（节省空间）

 Processing 4555-18116-29.png ... width:80 height:80 North edge extracted East edge extracted South edge extracted West edge extracted 4555-18116-29_S.png is edge-piece Processing 5004-10810-17642.png ... width:80 height:80 North edge extracted East edge extracted South edge extracted West edge extracted 5004-10810-17642_W.png is corner-piece Processing 5167-27533-24066.png ... width:80 height:80 North edge extracted East edge extracted South edge extracted West edge extracted Processing 5774-30645-16062.png ... width:80 height:80 North edge extracted East edge extracted South edge extracted West edge extracted 0a7bb6f610c0f1a6da4794ea7ae00f00:10297-13918-3702_W.png (flipped) 0a7bb6f610c0f1a6da4794ea7ae00f00:11976-7751-26756_E.png (flipped) <-- this image is identical to the one above as the md5 checksum on the left is the same 0ce419e072c7ea5d14e3525d4afe150e:11976-7751-26756_W.png (flipped) 0ce419e072c7ea5d14e3525d4afe150e:13858-18007-13070_E.png (flipped) <-- this image is identical to the one above as the md5 checksum on the left is the same 0ce419e072c7ea5d14e3525d4afe150e:20056-20936-29071_S.png 0ce419e072c7ea5d14e3525d4afe150e:24658-20374-23042_E.png (flipped) 0ce419e072c7ea5d14e3525d4afe150e:24658-20374-23042_S.png 0ce419e072c7ea5d14e3525d4afe150e:27206-10104-18226_N.png 0ce419e072c7ea5d14e3525d4afe150e:30261-16558-25650_N.png 

笔记

请注意，这假设您没有在@YvesDaoust标识的QR码的各个“字段”之间完全平铺图像。

此外，代码的某些部分是冗余的，因为我正在与代码同时开发算法 - 我认为-rotates和+repages是不必要的，并且事情可以进行更多优化但是没有表明需要速度题。 北，东，南和西边缘也可以在单个IM命令中提取。 我获得的宽度和高度未使用，因此可以从代码中删除。

此外，md5校验和并不是必需的， sort将无论如何将0001110001010110放在另一个字符串旁边而不需要校验它们。

根据请求，我正在上传完整的解决方案。 我删除了md5校验和的东西，因为它是不必要的。 您需要向右滚动才能看到下面的文件名：

 00000000000000000000000000000000000000000000000000000000000000000000000000000000:10297-13918-3702_N.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:10297-13918-3702_N.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:11976-7751-26756_N.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:11976-7751-26756_N.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:13858-18007-13070_N.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:13858-18007-13070_N.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:16369-21469-8252_E.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:16369-21469-8252_E.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:18056-16294-30425_S.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:18056-16294-30425_S.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:20021-11440-20836_S.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:20021-11440-20836_S.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:20056-20936-29071_W.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:20056-20936-29071_W.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:21875-14159-1067_E.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:21875-14159-1067_E.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:22806-3380-17484_W.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:22806-3380-17484_W.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:24426-18830-5627_E.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:24426-18830-5627_E.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:24658-20374-23042_N.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:24658-20374-23042_N.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:24658-20374-23042_W.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:24658-20374-23042_W.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:27206-10104-18226_S.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:27206-10104-18226_S.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:27206-10104-18226_W.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:27206-10104-18226_W.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:30261-16558-25650_W.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:30261-16558-25650_W.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:31250-3578-9750_E.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:31250-3578-9750_E.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:31250-3578-9750_N.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:31250-3578-9750_N.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:4555-18116-29_S.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:4555-18116-29_S.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:5004-10810-17642_E.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:5004-10810-17642_E.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000000000000000000:5004-10810-17642_S.png 00000000000000000000000000000000000000000000000000000000000000000000000000000000:5004-10810-17642_S.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000111111111111100:21875-14159-1067_S.png (flipped) 00000000000000000000000000000000000000000000000000000000000000000111111111111100:5004-10810-17642_N.png (flipped) 00000000000000000000000000000000000000000000000000000000000001111111111111111111:28824-13023-24184_W.png (flipped) 00000000000000000000000000000000000000000000000000000000000001111111111111111111:5774-30645-16062_E.png (flipped) 00000000000000000000000000000000000000000000000000000000000011111111111111111111:13789-10513-4721_E.png 00000000000000000000000000000000000000000000000000000000000011111111111111111111:32078-14314-1511_W.png 00000000000000000000000000000000000000000000000000000001111111111111000000000000:11976-7751-26756_W.png 00000000000000000000000000000000000000000000000000000001111111111111000000000000:13858-18007-13070_E.png 00000000000000000000000000000000000000000000000000000001111111111111000000000000:20056-20936-29071_S.png (flipped) 00000000000000000000000000000000000000000000000000000001111111111111000000000000:24658-20374-23042_E.png 00000000000000000000000000000000000000000000000000000001111111111111000000000000:24658-20374-23042_S.png (flipped) 00000000000000000000000000000000000000000000000000000001111111111111000000000000:27206-10104-18226_N.png (flipped) 00000000000000000000000000000000000000000000000000000001111111111111000000000000:30261-16558-25650_N.png (flipped) 00000000000000000000000000000000000000000000000000000001111111111111000000000000:31250-3578-9750_W.png 00000000000000000000000000000000000000000000000000000011111111111110000000000000:16369-21469-8252_N.png 00000000000000000000000000000000000000000000000000000011111111111110000000000000:18056-16294-30425_W.png (flipped) 00000000000000000000000000000000000000000000000000000011111111111110000000000000:27206-10104-18226_E.png (flipped) 00000000000000000000000000000000000000000000000000000011111111111110000000000000:31250-3578-9750_S.png 00000000000000000000000000000000000000000000001111111111111111111111111111111111:10297-13918-3702_S.png 00000000000000000000000000000000000000000000001111111111111111111111111111111111:28824-13023-24184_N.png 00000000000000000000000000000000000001111111111111111111111111000000000000000000:20021-11440-20836_N.png (flipped) 00000000000000000000000000000000000001111111111111111111111111000000000000000000:26507-21853-11958_S.png (flipped) 00000000000000000000000000000000000001111111111111111111111111111111111111100000:15816-4564-31665_W.png 00000000000000000000000000000000000001111111111111111111111111111111111111100000:17636-24599-1877_E.png 00000000000000000000000000000000000001111111111111111111111111111111111111111111:21875-14159-1067_W.png 00000000000000000000000000000000000001111111111111111111111111111111111111111111:26507-21853-11958_E.png 00000000000000000000000000000000000011111111111111111111111110000000000000000000:13789-10513-4721_S.png 00000000000000000000000000000000000011111111111111111111111110000000000000000000:17636-24599-1877_N.png 00000000000000000000000000000001111111111111000000000000000000000000001111111111:22161-18187-20222_W.png 00000000000000000000000000000001111111111111000000000000000000000000001111111111:28824-13023-24184_E.png 00000000000000000000000000000011111111111111111111111111111111111111100000000000:15816-4564-31665_E.png (flipped) 00000000000000000000000000000011111111111111111111111111111111111111100000000000:26507-21853-11958_W.png (flipped) 00000000000000000000000000000111111111111111111111111111111111111111000000000000:20056-20936-29071_N.png (flipped) 00000000000000000000000000000111111111111111111111111111111111111111000000000000:22806-3380-17484_S.png (flipped) 00000000000000000000000000001111111111111111111111111111111111111110000000000000:18056-16294-30425_E.png (flipped) 00000000000000000000000000001111111111111111111111111111111111111110000000000000:4555-18116-29_W.png (flipped) 00000000000000000000000000111111111111100000000000001111111111111000000000000011:16369-21469-8252_S.png (flipped) 00000000000000000000000000111111111111100000000000001111111111111000000000000011:24426-18830-5627_N.png (flipped) 00000000000000000000000001111111111111111111111111111111111111110000000000000000:10297-13918-3702_W.png (flipped) 00000000000000000000000001111111111111111111111111111111111111110000000000000000:11976-7751-26756_E.png (flipped) 00000000000000000000000111111111111100000000000001111111111111111111111111111111:13789-10513-4721_N.png 00000000000000000000000111111111111100000000000001111111111111111111111111111111:5774-30645-16062_S.png 00000000000000000000111111111111100000000000000000000000000111111111111100000000:15816-4564-31665_N.png 00000000000000000000111111111111100000000000000000000000000111111111111100000000:32078-14314-1511_S.png 00000000000000000000111111111111100000000000001111111111111111111111111100000000:13789-10513-4721_W.png (flipped) 00000000000000000000111111111111100000000000001111111111111111111111111100000000:22806-3380-17484_E.png (flipped) 00000000000000000001111111111111111111111111000000000000000000000000000000000000:13789-10513-4721_S.png (flipped) 00000000000000000001111111111111111111111111000000000000000000000000000000000000:17636-24599-1877_N.png (flipped) 00000000000000000011111111111100000000000000000000000000111111111111111111111111:22161-18187-20222_S.png 00000000000000000011111111111100000000000000000000000000111111111111111111111111:5167-27533-24066_N.png 00000000000000000011111111111111111111111110000000000000000000000000000000000000:20021-11440-20836_N.png 00000000000000000011111111111111111111111110000000000000000000000000000000000000:26507-21853-11958_S.png 00000000000000001111111111111111111111111111111111111110000000000000000000000000:10297-13918-3702_W.png 00000000000000001111111111111111111111111111111111111110000000000000000000000000:11976-7751-26756_E.png 00000000000001111111111111000000000000000000000000000000000000000000000000000000:16369-21469-8252_N.png (flipped) 00000000000001111111111111000000000000000000000000000000000000000000000000000000:18056-16294-30425_W.png 00000000000001111111111111000000000000000000000000000000000000000000000000000000:27206-10104-18226_E.png 00000000000001111111111111000000000000000000000000000000000000000000000000000000:31250-3578-9750_S.png (flipped) 00000000000001111111111111000000000000011111111111110000000000000111111111111111:21875-14159-1067_N.png (flipped) 00000000000001111111111111000000000000011111111111110000000000000111111111111111:24426-18830-5627_S.png (flipped) 00000000000001111111111111000000000000011111111111111111111111111111111111111100:20021-11440-20836_W.png 00000000000001111111111111000000000000011111111111111111111111111111111111111100:4555-18116-29_E.png 00000000000001111111111111111111111111111111111111110000000000000000000000000000:18056-16294-30425_E.png 00000000000001111111111111111111111111111111111111110000000000000000000000000000:4555-18116-29_W.png 00000000000001111111111111111111111111111111111111111111111111111111111111111100:20021-11440-20836_E.png 00000000000001111111111111111111111111111111111111111111111111111111111111111100:5004-10810-17642_W.png 00000000000011111111111110000000000000000000000000000000000000000000000000000000:11976-7751-26756_W.png (flipped) 00000000000011111111111110000000000000000000000000000000000000000000000000000000:13858-18007-13070_E.png (flipped) 00000000000011111111111110000000000000000000000000000000000000000000000000000000:20056-20936-29071_S.png 00000000000011111111111110000000000000000000000000000000000000000000000000000000:24658-20374-23042_E.png (flipped) 00000000000011111111111110000000000000000000000000000000000000000000000000000000:24658-20374-23042_S.png 00000000000011111111111110000000000000000000000000000000000000000000000000000000:27206-10104-18226_N.png 00000000000011111111111110000000000000000000000000000000000000000000000000000000:30261-16558-25650_N.png 00000000000011111111111110000000000000000000000000000000000000000000000000000000:31250-3578-9750_W.png (flipped) 00000000000011111111111110000000000000111111111111111111111111111111111111111000:22806-3380-17484_N.png 00000000000011111111111110000000000000111111111111111111111111111111111111111000:30261-16558-25650_S.png 00000000000011111111111111111111111111000000000000011111111111111111111111111111:10297-13918-3702_E.png (flipped) 00000000000011111111111111111111111111000000000000011111111111111111111111111111:13858-18007-13070_W.png (flipped) 00000000000011111111111111111111111111111111111111100000000000000000000000000000:20056-20936-29071_N.png 00000000000011111111111111111111111111111111111111100000000000000000000000000000:22806-3380-17484_S.png 00000000000111111111111100000000000000000000000000000000000000111111111111100000:17636-24599-1877_W.png 00000000000111111111111100000000000000000000000000000000000000111111111111100000:20056-20936-29071_E.png 00000000000111111111111100000000000001111111111111000000000000111111111111111111:13858-18007-13070_S.png (flipped) 00000000000111111111111100000000000001111111111111000000000000111111111111111111:22161-18187-20222_N.png (flipped) 00000000000111111111111111111111111111111111111111000000000000000000000000000000:15816-4564-31665_E.png 00000000000111111111111111111111111111111111111111000000000000000000000000000000:26507-21853-11958_W.png 00000000001111111111111000000000000000000000000000000000000001111111111111000000:30261-16558-25650_E.png (flipped) 00000000001111111111111000000000000000000000000000000000000001111111111111000000:5774-30645-16062_W.png (flipped) 00000000001111111111111000000000000000000000000001111111111111111111111111000000:17636-24599-1877_S.png 00000000001111111111111000000000000000000000000001111111111111111111111111000000:18056-16294-30425_N.png 00000000001111111111111000000000000011111111111110000000000001111111111111000000:11976-7751-26756_S.png 00000000001111111111111000000000000011111111111110000000000001111111111111000000:5774-30645-16062_N.png 00000000001111111111111000000000000011111111111111111111111110000000000000111111:16369-21469-8252_W.png (flipped) 00000000001111111111111000000000000011111111111111111111111110000000000000111111:22161-18187-20222_E.png (flipped) 00000000111111111111100000000000000000000000000111111111111100000000000000000000:15816-4564-31665_N.png (flipped) 00000000111111111111100000000000000000000000000111111111111100000000000000000000:32078-14314-1511_S.png (flipped) 00000000111111111111100000000000000000000000000111111111111111111111111110000000:15816-4564-31665_S.png (flipped) 00000000111111111111100000000000000000000000000111111111111111111111111110000000:4555-18116-29_N.png (flipped) 00000000111111111111100000000000001111111111111000000000000011111111111110000000:32078-14314-1511_E.png 00000000111111111111100000000000001111111111111000000000000011111111111110000000:5167-27533-24066_W.png 00000000111111111111111111111111110000000000000000000000000000000000000001111111:28824-13023-24184_S.png (flipped) 00000000111111111111111111111111110000000000000000000000000000000000000001111111:32078-14314-1511_N.png (flipped) 00000000111111111111111111111111110000000000000111111111111100000000000000000000:13789-10513-4721_W.png 00000000111111111111111111111111110000000000000111111111111100000000000000000000:22806-3380-17484_E.png 00000001111111111111000000000000011111111111110000000000000111111111111100000000:32078-14314-1511_E.png (flipped) 00000001111111111111000000000000011111111111110000000000000111111111111100000000:5167-27533-24066_W.png (flipped) 00000001111111111111111111111111100000000000000000000000000111111111111100000000:15816-4564-31665_S.png 00000001111111111111111111111111100000000000000000000000000111111111111100000000:4555-18116-29_N.png 00000011111111111110000000000000000000000000000000000000011111111111110000000000:30261-16558-25650_E.png 00000011111111111110000000000000000000000000000000000000011111111111110000000000:5774-30645-16062_W.png 00000011111111111110000000000001111111111111000000000000011111111111110000000000:11976-7751-26756_S.png (flipped) 00000011111111111110000000000001111111111111000000000000011111111111110000000000:5774-30645-16062_N.png (flipped) 00000011111111111111111111111110000000000000000000000000011111111111110000000000:17636-24599-1877_S.png (flipped) 00000011111111111111111111111110000000000000000000000000011111111111110000000000:18056-16294-30425_N.png (flipped) 00000111111111111100000000000000000000000000000000000000111111111111100000000000:17636-24599-1877_W.png (flipped) 00000111111111111100000000000000000000000000000000000000111111111111100000000000:20056-20936-29071_E.png (flipped) 00000111111111111111111111111100000000000001111111111111111111111111111111111111:26507-21853-11958_N.png 00000111111111111111111111111100000000000001111111111111111111111111111111111111:5167-27533-24066_S.png 00000111111111111111111111111111111111111110000000000000000000000000000000000000:15816-4564-31665_W.png (flipped) 00000111111111111111111111111111111111111110000000000000000000000000000000000000:17636-24599-1877_E.png (flipped) 00011111111111111111111111111111111111111100000000000001111111111111000000000000:22806-3380-17484_N.png (flipped) 00011111111111111111111111111111111111111100000000000001111111111111000000000000:30261-16558-25650_S.png (flipped) 00111111111111100000000000000000000000000000000000000000000000000000000000000000:21875-14159-1067_S.png 00111111111111100000000000000000000000000000000000000000000000000000000000000000:5004-10810-17642_N.png 00111111111111111111111111111111111111111000000000000011111111111110000000000000:20021-11440-20836_W.png (flipped) 00111111111111111111111111111111111111111000000000000011111111111110000000000000:4555-18116-29_E.png (flipped) 00111111111111111111111111111111111111111111111111111111111111111110000000000000:20021-11440-20836_E.png (flipped) 00111111111111111111111111111111111111111111111111111111111111111110000000000000:5004-10810-17642_W.png (flipped) 11000000000000011111111111110000000000000111111111111100000000000000000000000000:16369-21469-8252_S.png 11000000000000011111111111110000000000000111111111111100000000000000000000000000:24426-18830-5627_N.png 11111100000000000001111111111111111111111111000000000000011111111111110000000000:16369-21469-8252_W.png 11111100000000000001111111111111111111111111000000000000011111111111110000000000:22161-18187-20222_E.png 11111110000000000000000000000000000000000000001111111111111111111111111100000000:28824-13023-24184_S.png 11111110000000000000000000000000000000000000001111111111111111111111111100000000:32078-14314-1511_N.png 11111110000000000000000000000000011111111111111111111111111111111111111111111111:24426-18830-5627_W.png (flipped) 11111110000000000000000000000000011111111111111111111111111111111111111111111111:5167-27533-24066_E.png (flipped) 11111111110000000000000000000000000011111111111110000000000000000000000000000000:22161-18187-20222_W.png (flipped) 11111111110000000000000000000000000011111111111110000000000000000000000000000000:28824-13023-24184_E.png (flipped) 11111111111111100000000000001111111111111000000000000011111111111110000000000000:21875-14159-1067_N.png 11111111111111100000000000001111111111111000000000000011111111111110000000000000:24426-18830-5627_S.png 11111111111111111100000000000011111111111110000000000000111111111111100000000000:13858-18007-13070_S.png 11111111111111111100000000000011111111111110000000000000111111111111100000000000:22161-18187-20222_N.png 11111111111111111110000000000000000000000000000000000000000000000000000000000000:28824-13023-24184_W.png 11111111111111111110000000000000000000000000000000000000000000000000000000000000:5774-30645-16062_E.png 11111111111111111111000000000000000000000000000000000000000000000000000000000000:13789-10513-4721_E.png (flipped) 11111111111111111111000000000000000000000000000000000000000000000000000000000000:32078-14314-1511_W.png (flipped) 11111111111111111111111100000000000000000000000000111111111111000000000000000000:22161-18187-20222_S.png (flipped) 11111111111111111111111100000000000000000000000000111111111111000000000000000000:5167-27533-24066_N.png (flipped) 11111111111111111111111111111000000000000011111111111111111111111111000000000000:10297-13918-3702_E.png 11111111111111111111111111111000000000000011111111111111111111111111000000000000:13858-18007-13070_W.png 11111111111111111111111111111110000000000000111111111111100000000000000000000000:13789-10513-4721_N.png (flipped) 11111111111111111111111111111110000000000000111111111111100000000000000000000000:5774-30645-16062_S.png (flipped) 11111111111111111111111111111111110000000000000000000000000000000000000000000000:10297-13918-3702_S.png (flipped) 11111111111111111111111111111111110000000000000000000000000000000000000000000000:28824-13023-24184_N.png (flipped) 11111111111111111111111111111111111110000000000000111111111111111111111111100000:26507-21853-11958_N.png (flipped) 11111111111111111111111111111111111110000000000000111111111111111111111111100000:5167-27533-24066_S.png (flipped) 11111111111111111111111111111111111111111110000000000000000000000000000000000000:21875-14159-1067_W.png (flipped) 11111111111111111111111111111111111111111110000000000000000000000000000000000000:26507-21853-11958_E.png (flipped) 11111111111111111111111111111111111111111111111000000000000000000000000001111111:24426-18830-5627_W.png 11111111111111111111111111111111111111111111111000000000000000000000000001111111:5167-27533-24066_E.png 

Answer 2

这是一个更好的算法，我已编写脚本：

1. 从每个图块中，从每个边缘剪掉1像素的行或列，并将其输出为ImageMagick的特殊*.text格式，使用指示其各自的左/右或上/下边缘原点的名称。

2. 转换每个这样的列/行，创建其*.txt的md5sum并按字母顺序对它们进行排序。

3. 确定哪些MD5总和相同。

4. 从相同的MD5总和确定适合相应边界的候选者。

代码段

 for i in {1,2,3,4,5}*.png; do convert ${i}[1x80+0+0] +repage left---edge-${i/.png/.text} convert ${i}[1x80+79+0] +repage right--edge-${i/.png/.text} convert ${i}[80x1+0+0] +repage top----edge-${i/.png/.text} convert ${i}[80x1+0+79] +repage bottom-edge-${i/.png/.text} done 

这样的文本文件可能看起来的一个例子是：

 cat right--edge-5167-27533-24066.text # ImageMagick pixel enumeration: 1,80,255,gray 0,0: (0,0,0) #000000 gray(0) 0,1: (0,0,0) #000000 gray(0) 0,2: (0,0,0) #000000 gray(0) 0,3: (0,0,0) #000000 gray(0) 0,4: (0,0,0) #000000 gray(0) 0,5: (0,0,0) #000000 gray(0) 0,6: (0,0,0) #000000 gray(0) 0,7: (255,255,255) #FFFFFF gray(255) 0,8: (255,255,255) #FFFFFF gray(255) 0,9: (255,255,255) #FFFFFF gray(255) 0,10: (255,255,255) #FFFFFF gray(255) 0,11: (255,255,255) #FFFFFF gray(255) 0,12: (255,255,255) #FFFFFF gray(255) 0,13: (255,255,255) #FFFFFF gray(255) 0,14: (255,255,255) #FFFFFF gray(255) 0,15: (255,255,255) #FFFFFF gray(255) 0,16: (255,255,255) #FFFFFF gray(255) 0,17: (255,255,255) #FFFFFF gray(255) 0,18: (255,255,255) #FFFFFF gray(255) 0,19: (255,255,255) #FFFFFF gray(255) 0,20: (255,255,255) #FFFFFF gray(255) 0,21: (255,255,255) #FFFFFF gray(255) 0,22: (255,255,255) #FFFFFF gray(255) 0,23: (255,255,255) #FFFFFF gray(255) 0,24: (255,255,255) #FFFFFF gray(255) 0,25: (255,255,255) #FFFFFF gray(255) 0,26: (255,255,255) #FFFFFF gray(255) 0,27: (255,255,255) #FFFFFF gray(255) 0,28: (255,255,255) #FFFFFF gray(255) 0,29: (255,255,255) #FFFFFF gray(255) 0,30: (255,255,255) #FFFFFF gray(255) 0,31: (255,255,255) #FFFFFF gray(255) 0,32: (255,255,255) #FFFFFF gray(255) 0,33: (0,0,0) #000000 gray(0) 0,34: (0,0,0) #000000 gray(0) 0,35: (0,0,0) #000000 gray(0) 0,36: (0,0,0) #000000 gray(0) 0,37: (0,0,0) #000000 gray(0) 0,38: (0,0,0) #000000 gray(0) 0,39: (0,0,0) #000000 gray(0) 0,40: (0,0,0) #000000 gray(0) 0,41: (0,0,0) #000000 gray(0) 0,42: (0,0,0) #000000 gray(0) 0,43: (0,0,0) #000000 gray(0) 0,44: (0,0,0) #000000 gray(0) 0,45: (0,0,0) #000000 gray(0) 0,46: (0,0,0) #000000 gray(0) 0,47: (0,0,0) #000000 gray(0) 0,48: (0,0,0) #000000 gray(0) 0,49: (0,0,0) #000000 gray(0) 0,50: (0,0,0) #000000 gray(0) 0,51: (0,0,0) #000000 gray(0) 0,52: (0,0,0) #000000 gray(0) 0,53: (0,0,0) #000000 gray(0) 0,54: (0,0,0) #000000 gray(0) 0,55: (0,0,0) #000000 gray(0) 0,56: (0,0,0) #000000 gray(0) 0,57: (0,0,0) #000000 gray(0) 0,58: (0,0,0) #000000 gray(0) 0,59: (0,0,0) #000000 gray(0) 0,60: (0,0,0) #000000 gray(0) 0,61: (0,0,0) #000000 gray(0) 0,62: (0,0,0) #000000 gray(0) 0,63: (0,0,0) #000000 gray(0) 0,64: (0,0,0) #000000 gray(0) 0,65: (0,0,0) #000000 gray(0) 0,66: (0,0,0) #000000 gray(0) 0,67: (0,0,0) #000000 gray(0) 0,68: (0,0,0) #000000 gray(0) 0,69: (0,0,0) #000000 gray(0) 0,70: (0,0,0) #000000 gray(0) 0,71: (0,0,0) #000000 gray(0) 0,72: (0,0,0) #000000 gray(0) 0,73: (0,0,0) #000000 gray(0) 0,74: (0,0,0) #000000 gray(0) 0,75: (0,0,0) #000000 gray(0) 0,76: (0,0,0) #000000 gray(0) 0,77: (0,0,0) #000000 gray(0) 0,78: (0,0,0) #000000 gray(0) 0,79: (0,0,0) #000000 gray(0) 

As you can see, it is a textual description for each pixel’s color of the extracted column (where the pixel coordinates are given in the first field of each line of text). The first line indicates which color space is used.

*Sort MD5 sums alphabetically

When sorting the MD5 sums of these text files alphabetically, it should be immediately obvious where there are identical pixel color rows and columns:

 md5sum *.text | sort 

结果：

(I manually added a few comments at the end of some lines.)

 09c0670b59c03fb3d6f8116ee0fe35a2 bottom-edge-10297-13918-3702.text 09c0670b59c03fb3d6f8116ee0fe35a2 top----edge-28824-13023-24184.text 10be914aa8b6aaa8c0e35a4a93421f3a left---edge-20056-20936-29071.text #left edge of QR 10be914aa8b6aaa8c0e35a4a93421f3a left---edge-22806-3380-17484.text #left edge of QR 10be914aa8b6aaa8c0e35a4a93421f3a left---edge-24658-20374-23042.text #left edge of QR 10be914aa8b6aaa8c0e35a4a93421f3a left---edge-27206-10104-18226.text #left edge of QR 10be914aa8b6aaa8c0e35a4a93421f3a left---edge-30261-16558-25650.text #left edge of QR 10be914aa8b6aaa8c0e35a4a93421f3a right--edge-16369-21469-8252.text #right edge of QR 10be914aa8b6aaa8c0e35a4a93421f3a right--edge-21875-14159-1067.text #right edge of QR 10be914aa8b6aaa8c0e35a4a93421f3a right--edge-24426-18830-5627.text #right edge of QR 10be914aa8b6aaa8c0e35a4a93421f3a right--edge-31250-3578-9750.text #right edge of QR 10be914aa8b6aaa8c0e35a4a93421f3a right--edge-5004-10810-17642.text #right edge of QR 217c799ce772d99e11b7ba2a04f42bb7 bottom-edge-11976-7751-26756.text 217c799ce772d99e11b7ba2a04f42bb7 top----edge-5774-30645-16062.text 2c96cebc6cc175b54cae54f1a27771fa bottom-edge-24426-18830-5627.text 2c96cebc6cc175b54cae54f1a27771fa top----edge-21875-14159-1067.text 3088414b0fe1190bbd4ed9315d86a0ac left---edge-13789-10513-4721.text 3088414b0fe1190bbd4ed9315d86a0ac right--edge-22806-3380-17484.text 3755d45bb6ad21b70f545f39c5550eda left---edge-17636-24599-1877.text 3755d45bb6ad21b70f545f39c5550eda right--edge-20056-20936-29071.text 41fc32b4b70622b4aff7d9e81f81daad left---edge-13858-18007-13070.text 41fc32b4b70622b4aff7d9e81f81daad right--edge-10297-13918-3702.text 480bed740a716fa10593ba061c5b6df5 left---edge-5004-10810-17642.text 480bed740a716fa10593ba061c5b6df5 right--edge-20021-11440-20836.text 55cc4713ee13ebbeb5c2e212e430da94 bottom-edge-28824-13023-24184.text 55cc4713ee13ebbeb5c2e212e430da94 top----edge-32078-14314-1511.text 62fecd6971445d4176a842727767d3f7 left---edge-4555-18116-29.text 62fecd6971445d4176a842727767d3f7 right--edge-18056-16294-30425.text 69565761226f122f98267862108119a6 left---edge-21875-14159-1067.text 69565761226f122f98267862108119a6 right--edge-26507-21853-11958.text 72cec2b0a518c2cce7204188923d9f79 left---edge-26507-21853-11958.text 72cec2b0a518c2cce7204188923d9f79 right--edge-15816-4564-31665.text 7343348f1b10e47b33e0bde47b455c2b left---edge-16369-21469-8252.text 7343348f1b10e47b33e0bde47b455c2b right--edge-22161-18187-20222.text 7661c257d28e1916208ed2a70989e42d bottom-edge-13789-10513-4721.text 7661c257d28e1916208ed2a70989e42d top----edge-17636-24599-1877.text 7d2a0d7aae6dc017ffa7af7180b1c017 left---edge-5167-27533-24066.text 7d2a0d7aae6dc017ffa7af7180b1c017 right--edge-32078-14314-1511.text 85b744d1774cd4ebe50f0cc40d10b491 left---edge-18056-16294-30425.text 85b744d1774cd4ebe50f0cc40d10b491 right--edge-27206-10104-18226.text 88942ff37ce0e884d1995a6dd11708d6 left---edge-10297-13918-3702.text 88942ff37ce0e884d1995a6dd11708d6 right--edge-11976-7751-26756.text 9185daee4fdcea482c9fa805bba40346 bottom-edge-31250-3578-9750.text 9185daee4fdcea482c9fa805bba40346 top----edge-16369-21469-8252.text 9b8a7f18e4ebbc7249e5f26ac18190a8 left---edge-28824-13023-24184.text 9b8a7f18e4ebbc7249e5f26ac18190a8 right--edge-5774-30645-16062.text 9bd8f7a474229aefd988c4231f3b26f4 bottom-edge-21875-14159-1067.text 9bd8f7a474229aefd988c4231f3b26f4 top----edge-5004-10810-17642.text a1778c1a468c122bf408a9c2bec9135c bottom-edge-13858-18007-13070.text a1778c1a468c122bf408a9c2bec9135c top----edge-22161-18187-20222.text a4f3eee0e523f1b343d292987da297b3 bottom-edge-20056-20936-29071.text a4f3eee0e523f1b343d292987da297b3 bottom-edge-24658-20374-23042.text a4f3eee0e523f1b343d292987da297b3 top----edge-27206-10104-18226.text a4f3eee0e523f1b343d292987da297b3 top----edge-30261-16558-25650.text af851da184ea6d6586c64aaefdc6875b bottom-edge-22806-3380-17484.text af851da184ea6d6586c64aaefdc6875b top----edge-20056-20936-29071.text b4047de9fb6458ebfde5b3a11b40241a left---edge-5774-30645-16062.text b4047de9fb6458ebfde5b3a11b40241a right--edge-30261-16558-25650.text b58fe9214967f6d2311e11cb0bf1acc4 left---edge-15816-4564-31665.text b58fe9214967f6d2311e11cb0bf1acc4 right--edge-17636-24599-1877.text bef4d7004da4f5de4ca5beeabc1222e8 bottom-edge-5774-30645-16062.text bef4d7004da4f5de4ca5beeabc1222e8 top----edge-13789-10513-4721.text c042d1cd3dfb339177e8da3c2907d58e bottom-edge-15816-4564-31665.text c042d1cd3dfb339177e8da3c2907d58e top----edge-4555-18116-29.text c5f38ebda77190495d77df1fb7002d1e bottom-edge-32078-14314-1511.text c5f38ebda77190495d77df1fb7002d1e top----edge-15816-4564-31665.text c61f738453fa3a86b52b2de5c0d43530 left---edge-20021-11440-20836.text c61f738453fa3a86b52b2de5c0d43530 right--edge-4555-18116-29.text c772762652d22cbf228e57f0dcf1a3b4 bottom-edge-22161-18187-20222.text c772762652d22cbf228e57f0dcf1a3b4 top----edge-5167-27533-24066.text cfaa399406e0be3d07297f23c684e7c3 left---edge-11976-7751-26756.text cfaa399406e0be3d07297f23c684e7c3 left---edge-31250-3578-9750.text cfaa399406e0be3d07297f23c684e7c3 right--edge-13858-18007-13070.text cfaa399406e0be3d07297f23c684e7c3 right--edge-24658-20374-23042.text d39c2a0c14c20b66b441d368c164171d bottom-edge-18056-16294-30425.text #bottom edge of QR d39c2a0c14c20b66b441d368c164171d bottom-edge-20021-11440-20836.text #bottom edge of QR d39c2a0c14c20b66b441d368c164171d bottom-edge-27206-10104-18226.text #bottom edge of QR d39c2a0c14c20b66b441d368c164171d bottom-edge-4555-18116-29.text #bottom edge of QR d39c2a0c14c20b66b441d368c164171d bottom-edge-5004-10810-17642.text #bottom edge of QR d39c2a0c14c20b66b441d368c164171d top----edge-10297-13918-3702.text #top edge of QR d39c2a0c14c20b66b441d368c164171d top----edge-11976-7751-26756.text #top edge of QR d39c2a0c14c20b66b441d368c164171d top----edge-13858-18007-13070.text #top edge of QR d39c2a0c14c20b66b441d368c164171d top----edge-24658-20374-23042.text #top edge of QR d39c2a0c14c20b66b441d368c164171d top----edge-31250-3578-9750.text #top edge of QR d71e7b561d2cc251c962a843daff53bb bottom-edge-5167-27533-24066.text d71e7b561d2cc251c962a843daff53bb top----edge-26507-21853-11958.text d7ffe4aaf744387e7fa9db32271247e0 bottom-edge-26507-21853-11958.text d7ffe4aaf744387e7fa9db32271247e0 top----edge-20021-11440-20836.text da2aa01201b3da20a970928bc2bdef36 bottom-edge-30261-16558-25650.text da2aa01201b3da20a970928bc2bdef36 top----edge-22806-3380-17484.text dd86f02cfc0e260463c75ae5b8709f33 bottom-edge-16369-21469-8252.text dd86f02cfc0e260463c75ae5b8709f33 top----edge-24426-18830-5627.text dfdaa88ebf33284ac0367f92060cd060 bottom-edge-17636-24599-1877.text dfdaa88ebf33284ac0367f92060cd060 top----edge-18056-16294-30425.text f8e2f384f2269e086dc00fb6ff0b3f41 left---edge-32078-14314-1511.text f8e2f384f2269e086dc00fb6ff0b3f41 right--edge-13789-10513-4721.text fa59372704f3b48912a33f3780e9dce7 left---edge-22161-18187-20222.text fa59372704f3b48912a33f3780e9dce7 right--edge-28824-13023-24184.text fff7e26c6f9852fcfa51e79d154dc58a left---edge-24426-18830-5627.text fff7e26c6f9852fcfa51e79d154dc58a right--edge-5167-27533-24066.text 

One can immediately identify the following pattern:

1. 10 identical MD5 sums of d39c2a0c14c20b66b441d368c164171d
2. 10 identical MD5 sums of 10be914aa8b6aaa8c0e35a4a93421f3a
3. 20 pairs of identical MD5 sums for left/right edges
4. 20 pairs of identical MD5 sums for top/bottom edges

In the case of ‘1.’ and ‘2.’ it is easy to see that these are all-white edges, representing left/right/top/bottom pieces of the complete QR.

The rest of the matches, ‘3.’ and ‘4.’ make it easy to fit each individual tile to a left or right “partner” in a deterministic way.

---

更新

I’ve not seen Mark’s answer until now. But I see his approach is similar to mine.

I’m not willing to add my complete script to produce the final re-composed QR code though.

So if Mark’s solution includes this, he should get the approvement for the correct answer.

Answer 3

This one was easy, if one uses all the info available in the individual tile PNGs:

The QR reader says: http://www.oracle.com/javaone/index.html

It took me less than 3 minutes to come up with the solution — mainly because I had to type the respective command with one hand while being on the phone at the same time….

How did you produce the tiles?

更新

Now that @RCola has finally answered my question ( “How did you produce the tiles?” ), I’ll reveal how I came up so fast with the correct QR code image.

I did not use an algorithm as he had asked for. I used a “side-channel” attack, by-passing any need to think about such an algorithm.

This side-channel used an “information leak” which was contained in the tile images provided in @RCola’s ZIP file. This info is leaked when running a simple identify command. Here I run it not as a ‘simple’ command, but — to make the leaked information more obvious — as a command that forces a specific output format:

 identify -format "%f : %g\n" {1,2,3,4,5}*.png 10297-13918-3702.png : 400x400+160+0 11976-7751-26756.png : 400x400+80+0 13789-10513-4721.png : 400x400+80+160 13858-18007-13070.png : 400x400+240+0 15816-4564-31665.png : 400x400+160+240 16369-21469-8252.png : 400x400+320+80 17636-24599-1877.png : 400x400+80+240 18056-16294-30425.png : 400x400+80+320 20021-11440-20836.png : 400x400+240+320 20056-20936-29071.png : 400x400+0+240 21875-14159-1067.png : 400x400+320+240 22161-18187-20222.png : 400x400+240+80 22806-3380-17484.png : 400x400+0+160 24426-18830-5627.png : 400x400+320+160 24658-20374-23042.png : 400x400+0+0 26507-21853-11958.png : 400x400+240+240 27206-10104-18226.png : 400x400+0+320 28824-13023-24184.png : 400x400+160+80 30261-16558-25650.png : 400x400+0+80 31250-3578-9750.png : 400x400+320+0 32078-14314-1511.png : 400x400+160+160 4555-18116-29.png : 400x400+160+320 5004-10810-17642.png : 400x400+320+320 5167-27533-24066.png : 400x400+240+160 5774-30645-16062.png : 400x400+80+80 

(The same information would be contained in the output of identify {1,2,3,4,5}*.png — it would just not jump out so obviously.)

What does this show? The %g percent-escape prints the geometry information about the canvas associated with the PNG tile:

1. 400x400 is the overall size of this tile’s canvas. It is obvious, that this was the size of the original PNG representing the complete QR code.
2. +X+Y is the offset associated with this tile on the complete canvas.

Using this info makes it extremely easy to directly know which PNG tile has to be placed on which location of the puzzle:

• +0+0 obviously has to go to the top left corner
• +0+80 obviously goes just below that
• +80+0 obviously goes just right of the top left corner
• …and so on and so forth, until
• +320+320 goes into bottom right corner

The OP could have avoided that side-channel info leak (which in this case gives the complete game away) by adding the +repage parameter to the IM command he used to produce the tiles.

In order to “repair” the leaky tiles he provided and produce more challenging ones I did this:

  mkdir challenge for i in {1,2,3,4,5}*.png; do convert $i +repage challenge/$i done 

---

更新2

(In answer to the comment which despaired about the failure to “see” the info with the help of a hex editor…)

The same info as identify reveals could be obtained with the help of exiftool too (albeit in a less “accessible” form):

 exiftool 11976-7751-26756.png | grep -E '(Virtual Image|Width|Height|Offset)' Image Width : 80 Image Height : 80 Image Offset : 80, 0 (pixels) Virtual Image Width : 400 Virtual Image Height : 400 

Answer 4

I understand about nothing of your explanations but for matching tiles it suffices to compare the pixels along the common edge. This is because the splits are made across the QR cells, not between them.

You can work filling the array row by row, every time trying all unused blocks until you find a match. Actually several matches could arise by coincidence, so it is advisable to continue the search even after a match has been found. This will lead to a recursive implementation.

The corners and their immediate neighbors are easier to place by hand. With a little scrutiny, you can also find the blocks with the timing pattern.