Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?

enter image description here

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.

enter image description here

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.

share|improve this question
2  
how did you manage to put that stripes to the shredder? :p –  Kuba Sep 19 '13 at 4:58
1  
@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
2  
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
2  
Can you upload the files in a non .rar format? Perhaps a .zip or .tar.gz? –  rm -rf Sep 20 '13 at 3:17
show 13 more comments

2 Answers 2

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]]

enter image description here

share|improve this answer
add comment

Greedy algorithm (1D & 2D)

Data loading:

SetDirectory@NotebookDirectory[];
data = N@ImageData@Import[#] & /@ FileNames["*.bmp"] // Developer`ToPackedArray;
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"]

enter image description here

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

enter image description here

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.