如何对图像块进行排序以最小化它们之间的差异？

Question

我有一个小图像块列表。它们都是相同的尺寸（例如：16x16）。它们是黑白的，像素值在 0-255 之间。我想对这些图像进行排序，以尽量减少它们之间的差异。

我的想法是计算相邻块之间像素的 mean absolute difference (MAD)（例如：块 N 与块 N+1，块 N+1 与块 N+2，.. .). 由此我可以计算出这些 MAD 值的总和（例如：sum = mad1 + mad2 + ...）。我想要的是找到最小化该总和的顺序。

之前：

之后：（这是手工完成的，只是为了提供一个示例，这些块的顺序可能更好，尤其是那些带有垂直条纹的块）

Answer 1

基于 RaymoAisla 评论指出这类似于 Travelling salesman problem, I have decided to implement a solution using Nearest neighbour algorithm。虽然不完美，但效果很好 :

这是代码：

from PIL import Image
import numpy as np

def sortImages(images):  #Nearest neighbour algorithm
    result = []
    tovisit = range(len(images)) 

    best = max(tovisit, key=lambda x: images[x].sum()) #brightest block as first
    tovisit.remove(best)
    result.append(best)

    while tovisit: 
        best = min(tovisit, key=lambda x: MAD(images[x], images[best])) #nearest neighbour
        tovisit.remove(best)
        result.append(best)
    return result  #indices of sorted image blocks

def MAD(a, b): #mean absolute distance
    return np.absolute(a - b).sum()

images = ... #should contains b&w images only (eg : from PIL Image)
arrays = [np.array(x).astype(int) for x in images] #convert images to np arrays
result = sortImages(arrays)

如何对图像块进行排序以最小化它们之间的差异？

How to sort image blocks by to minimize the differences between them?

language-agnostic

sorting

image-processing