Algorithm to solve QR puzzle

2020-07-27 16:31发布

站内文章 / Java
162 0 0

问题:

I am building algorithm to automatically solve / rebuild QR code from number of tiles of equal size.

My approach:

  1. Get one of 3 side squares : Position squares
  2. Get the width of outer black border somehow using ImageMagic

Which for given example is 14px x 14px (UPDATE: it might be 13px by 13px)

  1. Set it as a constant: BLOCK_SIZE
  2. Start cycle matching VALID tiles and already compiled block of QR code

VALID is : unmatched AND not any of 3 corner tiles (big black squares)

4.1. Render all possible combinations of already compiled qr block AND 1 random valid tile from until the match found

4.2 If match found (tile can be placed by one of sides of already compiled/combined block of QR code) then record match

4.3 Match conditions:

There are no BLACK areas which have width and height conform to this equation:

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

Now there are some implementation complications arise:

  1. How to implement algorithm which matches a tile to tile (OR already compiled/combined block of QR code)?

I think ImageMagic can solve it. The goal is to get original QR code.

Example QR tiles in ZIP

UPDATE

As I see the solution narrows down to make ImageMagick scan and find if two tiles can be put together without breaking rules of QR code. Algorithm should try to put 2 tiles side by side and scan border areas. The trick is to measure width and height of black lines/blocks of joined tiles. How to do it?

UPDATE2

Comparison if tiles match using 2 columns of width 1px is not enough in some cases. For example, both algorithms will join this 2 tiles into:

VALID

and

INVALID

As you seen in INVALID, there is part of 2nd tile (the one on the right) was removed as denoited by red arrows, but since comparison done by 1px - algorithm doesn't care abuot this case. Hance invalid QR.

UPDATE3

http://dropcanvas.com/6bl6v

Archive containing:

  • invalid join.png

  • valid join.png

  • src1.png

  • src2-invalid.png

  • src2-valid.png

  • invalid.png

If your algorith will join src1.png and src2-invalid.png it fails. It's about if joined tiles will produce valid QR in the end. I hope you got my point.

UPDATE4

I will accept an answer after I test and get correct solution. It might take some time....

UPDATE 5 : TESTING

Everything seems correct with Mark's solution.

回答1:

I had a try at this as follows.

  1. Go through all PNGs and extract their North, East, South and West edges. If any PNG has two white edges, tell user it is a corner-piece. If any PNG has one white edge, tell user it is an edge-piece.

  2. Go through all edge pieces. Convert each one into a PBM format file and strip the headers and new lines so that it will just be an 80 digit long string, each digit a zero or a one for black or white. Calculate checksum of the string and then reverse the string to account for the image being flipped or rotated and then recalculate the checksum. Print out the checksums and pipe into sort so that matching edges come out together.

Here is the code:

#!/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 w h <<< $(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 N E S W; 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

Partial Output (to save space)

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

Notes

Note that this assumes you have not tiled the images EXACTLY between the individual "fields" of the QR codes as identified by @YvesDaoust.

Also, some parts of the code are redundant, as I was developing the algorithm at the same time as the code - I think the -rotates and +repages are unnecessary and things could be optimised more but there was no indicated need for speed in the question. The North, East, South and West edges could be extracted in a single IM command too. The width and height that I obtained are unused so could be removed from the code.

Also, the md5 checksum is not really necessary, sort will place 0001110001010110 next to another string the same anyway without needing to checksum them.

Per request, I am uploading the complete solution. I removed the md5 checksum stuff as it was unnecessary. You will need to scroll right to see the filenames below:

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


回答2:

Here is a better algorithm, which I scripted already:

  1. From each tile, shave off a 1 pixel row or column from each edge, and output it to ImageMagick's special *.text format, using names which indicate their respective left/right or top/bottom edge origin.

  2. Convert each such column/row, create the md5sum of its *.txt and sort these alphabetically.

  3. Determine which MD5 sums are identical.

  4. Determine from the identical MD5 sums the candidates which would fit at the respective border.

Code snippet

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

One example how such a text file may look is this:

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

Results:

(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.

Update

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.



回答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?

Update

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

Update 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


回答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.



标签： java algorithm imagemagick
举报

收藏的人(0)

Ta的文章 更多文章
登录 后发表评论
0条评论
还没有人评论过~