With written text, you would expect that at least some the letters from one shred would continue on its neighbors. I don't see why the similarity metric would not work. Also normally you have a pretty high contrast between the letter and the background, unlike the image that was used in the example.