# Reconstruct text pages cut by shredder

Q1: I have a page of printed text file, but it was cut by a paper shredder (from top to bottom). You can download all the paper fragment here. There are some examples of them. How can I reconstruct it?

Q2: This time, the situation is even worse - the page was cut by a shredder twice (from top to bottom and from left to right) ! Download Link.

My code for Q1:

filenames = FileNames["*.bmp", "C:\\Users\\Liao\\Desktop\\B\\file1"];
pics = Import /@ filenames;
binarypic = Binarize[#, 0.9] & /@ pics;
binarydata = ImageData /@ binarypic;
leftandrightdata =
MapIndexed[{#2[[1]], #1[[All, 1]], #1[[All, -1]]} &, binarydata];
result = {};
firstPic = Select[leftandrightdata, ! MemberQ[#[[2]], 0] &][[1, 1]];
start = leftandrightdata[[firstPic]];
DeleteCases[leftandrightdata, start] //.
x_ /; Length[x] > 0 :> (sort =
SortBy[x, HammingDistance[#[[2]], start[[3]]] &];
AppendTo[result, start = sort[[1]]]; Rest[sort]);
Extract[pics,
Prepend[List /@ result[[All, 1]], {firstPic}]] // ImageAssemble


This code maybe dizzy for you, but it doesn't matter. The core idea is simple and straightforward, which use HammingDistance to determing whether two images can be combined together.

But for Q2, I can't really find a good way to solve it.

-
how did you manage to put that stripes to the shredder? :p –  Kuba Sep 19 '13 at 4:58
@Kuba It's a tough work! Well, actually it's a problem from a Mathematical Contest in Modeling. Now the contest have finished, so I post it here, looking forward to funny and exellent anwsers. –  mm.Jang Sep 19 '13 at 5:27
You can try ImmageAssemble at each permutation, then TextRecognize -> DictionaryLookup -> Length. I think it would be fun-compact-neverending :) –  Kuba Sep 19 '13 at 10:13
@Kuba It's too horrible to imagine what will happen :p –  mm.Jang Sep 19 '13 at 14:54
Can you upload the files in a non .rar format? Perhaps a .zip or .tar.gz? –  rm -rf Sep 20 '13 at 3:17

Q1

pics = Binarize /@ (Import /@ FileNames["*.bmp"]);

(*extracting edges*)
left = ImageData[#][[All, 1]] & /@ pics;
right = ImageData[#][[All, -1]] & /@ pics;


Let's find the left edge, here I'm assuming that it is all white. So if

pics // First // ImageDimensions

{72, 1980}


and an image is binarized then the left edge is:

Total /@ left // Position[#, 1980, 1] &

{{4}}


Instead of HammingDistance I'm calculating Norm:

cons = {4};
Do[
With[{dists = Norm[right[[cons[[-1]]]] - #] & /@ left},
AppendTo[cons, Position[dists, Min@dists, 1][[1, 1]] ]
]
, {Length@pics - 1}]

ImageAssemble@pics[[cons]]


-

Greedy algorithm (1D & 2D)

SetDirectory@NotebookDirectory[];
data = N@ImageData@Import[#] & /@ FileNames["*.bmp"] // DeveloperToPackedArray;
n = Length[data];


The matching of two edges is defined by the property

$$\frac{\mathop{\rm Var} [e_1+e_2]}{\mathop{\rm Var} [e_1-e_2]}$$

where $\mathop{\rm Var}[X]$ is the variance of $X$

r = 7;
var[list_] :=
Total[#, {3, 4}] &[(Transpose[list, {1, 2, 4, 3}] -
Mean@Transpose[list, {2, 3, 1, 4}])^2];
corr[list1_, list2_] :=
var@GaussianFilter[list1 + list2, {{0, 0, r, 0}}]/(0.0001 +
var@GaussianFilter[list1 - list2, {{0, 0, r, 0}}]);


Here r=7 is the radius of smoothing. It is very helpfull for real images (see below). 0.0001 is a small number to prevent division by zero.

The comparison each tile with each other:

top = corr[ConstantArray[data[[All, 1]], n],
Transpose@ConstantArray[data[[All, -1]], n]];
bottom = Transpose[top];
left = corr[ConstantArray[data[[All, All, 1]], n],
Transpose@ConstantArray[data[[All, All, -1]], n]];
right = Transpose[left];


Tiles in the resulting mosaic and possible positions of the next tiles:

tiles = SparseArray[{}, {2 n, 2 n}];
next = {};


The addition of the tile num to the position {i,j} of the resulting mosaic and the update of next tiles:

add[num_, {i_, j_}] := (next = DeleteCases[next, {i, j}];
tiles[[i, j]] = num;
left[[num, All]] = right[[num, All]] = top[[num, All]] = bottom[[num, All]] = 0.0;
If[tiles[[##]] == 0 && Not@MatchQ[next, {##}], AppendTo[next, {##}];] &
@@@ {{i, j + 1}, {i, j - 1}, {i + 1, j}, {i - 1, j}})


Quality of the matching of all possible tiles at the position {i,j} is just the sum of the matching with neighbors:

quality[i_, j_] :=
If[#2 != 0, #[[All, #2]], 0 #[[All, 1]]] & @@@ {{left,
tiles[[i, j + 1]]}, {right, tiles[[i, j - 1]]}, {top,
tiles[[i + 1, j]]}, {bottom, tiles[[i - 1, j]]}} // Total;


Addition of two tiles with the best matching:

(add[#1, {n, n}]; add[#2, {n, n + 1}]) & @@@ Position[left, Max[left]];


Addition of n-2 remaining tiles to the best positions:

Do[add[#2, next[[#]]] & @@ First@Position[#, Max[#]] &[quality @@@ next], {n - 2}];


The result for Q1:

view[margins__] :=
Image@Flatten[#, {{1, 3}, {2, 4}}] &@
Map[If[# <= 0, 1 + 0 data[[1]], data[[#]]] &,
tiles[[#1 ;; #2, #3 ;; #4]] &[margins], {2}]

view[Min[#1], Max[#1], Min[#2], Max[#2]] & @@ Transpose@tiles["NonzeroPositions"]


Unfortunately Q2 have too many blank edges to reconstruction so I use Lena photo

data = N@ImageData /@ #[[PermutationList@RandomPermutation@Length[#]]] &@
Flatten@ImagePartition[ExampleData[{"TestImage", "Lena"}], 64];


After repeating the steps above we got the result

Without smoothing of edges (see r above) the matching fails because of noise and fine structure (especially in the hat).

-
Cool! But my bounty has expired......:-/ –  mm.Jang Oct 10 '13 at 6:11
@mm.Jang If the bounty is expired the reputation is losted? I have never started a bounty. –  ybeltukov Oct 10 '13 at 19:21
Very nice! My suggestion for the blank edges may be to give them huge (unnatural) weights, that way it avoids connecting any white edges, if there is no way to move across a image with blank edges (in the case of the letter) it may be a natural gap. –  lalmei Nov 1 '13 at 16:13
I'm trying to understand your weights between edges better (specifically how those transpose's are acting on the image data), since I'm not very familiar with image analysis. Are you taking a variance over each color channel ? then summing ? –  lalmei Nov 4 '13 at 17:15
@lalmei Yes, I sum squares of every edge pixel and each color channel (Total with parameter {3,4}). Transpose` is a bit complicated, but it helps me to subtract the mean value (also with each channel separately). –  ybeltukov Nov 4 '13 at 17:23