If you took a relatively smooth image like a picture of a sky with a lot of high frequency (e.g. sensor) noise I'd expect this method to fail to be exact. Havi

If you took a relatively smooth image like a picture of a sky with a lot of high frequency (e.g. sensor) noise I'd expect this method to fail to be exact. Having a sparse representation in a DCT basis would be an even better metric. You want the unshredding which makes the (e.g.) 8-pixel wide horizontal DCT's have the lowest norm. Because this metric depends on more than just pairs of lines though it's not obvious how to construct an efficient TSP out of it. One could easily take a TSP solution and post process using the DCT metric, testing out all possible swaps (or near ties in the TSP solution).