如何根据像素的相似性将像素成对排列
我想要实现的是两个图像文件之间的转换。图像 A 中的像素移动并重新排列以形成图像 B。想象一下形成图像 B 的一团粒子云（由 A 图像的像素组成）。
到目前为止，我已经考虑过遍历图像 A 并将它们与图像 B 中的像素进行比较；最相似的像素从数组中取出（也包含它们的 x,y 坐标）并放入另一个数组中。所以，最后，我得到了两幅图像中相似的像素对。然后我只需要创建动画/可能的色彩平衡（显然所有对都不会包含相同的像素），这相当容易。
问题是找到像素对的算法。对于 100 像素 x 100 像素的小图像，需要 50 005 000 次比较，对于更大的图像则不可能。
将图片分成簇？任何想法将不胜感激。
what I want to achieve is a transition between two image files. The pixels from the image A move and rearrange themselves to form the image B. Imagine a cloud of particles (that is made from the A image's pixels) that forms into the picture B.
So far I have thought of going through all the pixels in image A and comparing them to pixels in image B; pixels that are the most similar are taken out of the arrays (with their x,y coordinates, too) and put into another array. So, in the end, I have pairs of pixels from both images that are similar. Then I only have to create the animation / possible color balancing (obviously all the pairs won't consist of identical pixels), which is fairly easy.
The problem is the algorithm that finds pixel pairs. For a small 100px x 100px image it would take 50 005 000 comparisons, for larger it would be impossible.
Dividing pictures in clusters? Any ideas will be appreciated.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我想说，首先按色调匹配像素，然后是饱和度，最后是亮度，您可能会获得最佳结果。如果我是对的，那么优化的最佳选择就是首先转换为 HSV。到达那里后，您可以对像素进行排序并对结果进行二分搜索以找到您的像素对。
我想说，您可能希望在找到的结果周围另外搜索固定窗口，以匹配彼此距离最近的像素。这可能会使最终的转变更加连贯。
I'd say that you're likely to achieve the best result matching up pixels by hue first, then saturation, finally luminance. If I'm right, then your best bet for optimization would be to convert to HSV first. Once there, you can just sort your pixels and binary search the results to find your pairs.
I'd say you'd may want to additionally search a fixed window around the result you find, to match up pixels that are least distance away from each other. That may make the resulting transition more coherent.
您可能想看看匈牙利算法，它减少了 100x100 的实际比较量像素到 10000 - 之后您有 O(n^3) 时间来查找最佳匹配。基本上，根据相似性为每个像素组合赋予一个“成本”，然后通过算法发送（倒置）成本矩阵，以获得从 A 到 B 的像素的最佳分配。
但它仍然可能是计算量太大而计算量太少。增益，取决于你是否需要实时。即，此类工作不一定需要最佳匹配，只需足够好 - 尽管如此，它可以作为寻找计算强度较低的方法的起点。
有关各种语言的实现，请参阅链接文章的底部 - 实现起来并不那么简单。
You may want to take a look at the Hungarian algorithm, which reduces the amount of actual comparisons for 100x100 pixels to 10000 - and after that you have O(n^3) time for finding the optimal matches. Basically, give each pixel combination a "cost" based on similarity and then send the (inverted) cost matrix through the algorithm to get the optimal assignment of pixels from A to pixels from B.
But it still might be too much computation for too little gain, depending on whether you need real time. I.e. this kind of work doesn't necessarily need an optimal match, just good enough - still, it may work as a point of origin in terms of finding less computationally intensive methods.
See bottom of the linked article for implementations in various languages - it's not entirely trival to implement.