PHP - 检测图像周围的空白区域的快速方法？

Question

我需要一种非常快速的方法来检测图像周围的空白区域，具体而言，我需要每个边缘（例如左侧、顶部、右侧、底部）第一个非白色像素开始的坐标。

ImageMagick太慢了，使用GD在每条边上循环每个像素并查看它是否为白色也是如此。我必须处理大约5亿张图像，因此每微秒都很重要。

顺便说一下，图像只有黑白两色。

如果有一款外部应用程序可以做到这一点，并且我可以在PHP中使用exec执行它，那么那就好了。

- Alasdair

---

这听起来需要并行处理。如果你把它分配给一堆服务器 - 或者甚至是一组台式电脑 - 你会得到更快的处理速度。话虽如此，你尝试过从 SSD 或 RAM 磁盘使用 imagemagick 吗？ - halfer

你能否更详细地描述一下这些图片的外观？我有一个算法想法，但不确定是否适用。我感兴趣的是您图片中的常见形状。大多数是旋转/稍微变形的矩形形状吗？大多数是圆形的吗？还是完全不可预测的（如X、E、T等）？ - KillerX

一个“bunch”里有多少台服务器？;) - halfer

我不认为PHP是这个任务的合适工具。如果你有那么多图片，应该使用本地语言，并利用每种特定文件格式的性能技巧。 - Gleno

@Gleno，它并不是非常适合，但这就是我正在使用的。C++会更好，汇编语言比那更好，只做我想要的事情的专用操作系统内核甚至更好，但出于实际目的，我正在使用PHP。无论如何，PHP只是将大部分由其他用C或C++编写的应用程序完成的工作整合在一起——只是碰巧PHP被用于这一部分。 - Alasdair

Answer 1

你是否有关于图像的额外信息可以用来帮助？例如，图像是从白色开始变成黑色然后保持黑色吗？还是任何像素都可以是白色或黑色，事实上任何一个像素是白色或黑色并不能告诉你其他像素的情况？如果任何像素都可以是白色或黑色，那么我认为你只能通过循环检查每个像素，直到找到第一个非白色像素。

如果你知道如果从左边数第五个像素是白色，则0-4肯定也是白色，那么你可能可以使用某种修改过的二进制搜索类型来检查更少的像素（因为在这种情况下，你可以跳过检查0-4，只需检查5，然后检查10，如果5是白色而10是黑色，则你知道该点在5-10之间，然后你可以分割差异并检查7等等，直到找到它们改变的点）。我认为你可能会在速度和准确性之间进行权衡。最准确的方法是从极端开始，沿着每一列和行切割，检查每个像素。一旦在一列中发现命中，就找到了一侧的边缘。由于每个检查是独立的，因此可以并行进行。你可能可以通过仅检查每n个像素来加快速度，但这很有可能偶尔会失败，特别是对于如此大的数据集。这可能是可以接受的，也可能不可接受。你可以通过在找到匹配区域周围进行检查来改进这一点，以检查匹配是否准确。因此，如果你每3个像素检查一次，并在第15个像素处找到一个命中，则检查14以查看它是否命中（如果14是，则检查13）。使用这种方法，你可能可以少做一些检查。

- Sam Holder

---

黑色像素自然倾向于成块出现，因此我可以跳过每隔一个像素，甚至只检查3个像素中的1个。除此之外，图像上可能是文本、绘画或抖动照片。 - Alasdair

Answer 2

一个算法可以用于处理大多数连续较暗像素边框的情况： 左侧：

1. 取中间像素并开始检查右侧的像素，直到找到黑色像素。
2. 然后向上/向下移动，直到遇到黑色像素
3. 当您找到黑色像素时，请向左移动，直到您找到白色像素
4. 重复步骤2、3，直到到达顶部/底部

当然，如果存在空隙（如文本），则此方法无效。

- KillerX

---

事实是...图像中间可能有一个大的白色空白，只有黑色像素在角落周围。 - Alasdair

理论上，您可以从顶部的10％开始，向右移动到宽度的50％。如果您没有撞到任何东西，请向上移动一行，然后向下移动2行等等... 您很可能仍需要覆盖比逐行/逐列扫描少的像素。 - KillerX