c# - C# 中的快速子图像比较

Question

我正在研究 photographic mosaic算法。涉及 4 个步骤:

1. 确定分割区域
2. 确定每个分割区域的每个候选图像的成本
3. 确定每个候选图像到每个分割区域的最佳分配
4. 渲染照片马赛克。

整个过程相对简单，但是第 2 步涉及将 n 个图像与 m 个片段进行比较，其中 n >> m。这是迄今为止最耗时的步骤。

这是我为每个段候选对执行的过程:

1. 确定候选图像是否与片段尺寸兼容。如果不是，则假定分配被禁止。
2. 使用通过 Graphics.DrawImage(Image, Rectangle, Rectangle, GraphicsUnit) 创建的中间子图片 Bitmap，我将位图数据转换为红色、绿色和原始图像片段的蓝色 int[,] 矩阵。我使用 LockBits() 方法而不是 GetPixel() 方法，因为它要快得多。为了减少计算时间，这些矩阵只有大约 3x3 或 5x5，而不是原始片段的完整维度。
3. 我对候选图像执行相同的过程，创建红色、绿色和蓝色 3x3 或 5x5 int[,] 矩阵。
4. 从 cost = 0 开始，我将源和候选图像片段的红色、绿色和蓝色值的差异量级添加到成本中。这些绝对差的总和就是分配成本。

实际上，我使用所有 16 个 RotateFlipType 转换检查每个候选图像，因此需要进行 16*n*m 次比较，其中 n = 片段数，m = 放置区域数.

我想知道我是否可以对每个图像进行 FFT，而不是比较每个像素，我只比较低频分量，因为高频分量不会对输出产生实质性影响。另一方面，很多开销仍然存在，例如获取子图像并将它们转换为矩阵，我的直觉告诉我光谱比较会比 25 个 int 值的基本比较慢.

Answer 1

起初我会做一个巨大的加速

1. 为每张图片创建信息，例如:

   平均颜色，r/g/b 直方图我认为每个 channel 8 或 16 个点就足够了。您可以添加任何其他信息(最暗/最亮的颜色，...)但它应该是旋转/翻转不变的

2. 按平均颜色对图像进行索引排序

   将 R、G、B 限制为只有几个位，例如 4 ...，并从中创建单个整数，例如

   col=R+(G<<4)+(B<<8);
   

   最后索引排序按此数量使用的图像

3. 比较

   因此 二分搜索 索引排序图像(如果您为每个减少的颜色创建索引表，那么这也将减少到 O(1))并且只查找与您的片段具有接近或相等平均颜色的图像。

   然后从这些图像中找到与直方图最接近的匹配项，然后将您所有的应用到这些图像上...

   直方图比较可以通过相关系数或任意距离，或统计偏差...

   至于您问题的 FFT 部分，我认为评论或多或少已经回答了。是的，你可以使用它，但我认为这太过分了。开销很大，但您可以将图像重新调整为低分辨率并对其使用FFT，或者只比较低分辨率图像

[注释]

同样使用HSV代替RGB可以提高视觉相似度