如何最佳地确定图像中的边缘？

Question

我最近遇到了裁剪和调整图像大小的问题。我需要裁剪图像的“主要内容”，例如，如果我有与此类似的图像： < img src="https://i.sstatic.net/vNoAK.jpg" alt="替代文本">
_{（来源：msn.com）}

结果应该是包含 msn 内容且没有白边（左和右）的图像。

我在 X 轴上搜索第一个和最后一个颜色变化，在 Y 轴上搜索相同的内容。问题是，逐行遍历图像需要一段时间。对于 2000x1600px 的图像，最多需要 2 秒才能返回 CropRect => x1,y1,x2,y2 数据。

我尝试对每个坐标进行遍历并在找到的第一个值上停止，但它在所有测试用例中都不起作用..有时返回的数据不是预期的数据，并且操作的持续时间相似..

任何想法如何减少“主要内容”周围矩形的遍历时间和发现时间？

public static CropRect EdgeDetection(Bitmap Image, float Threshold)
        {
            CropRect cropRectangle = new CropRect();
            int lowestX = 0;
            int lowestY = 0;
            int largestX = 0;
            int largestY = 0;

            lowestX = Image.Width;
            lowestY = Image.Height;

            //find the lowest X bound;
            for (int y = 0; y < Image.Height - 1; ++y)
            {
                for (int x = 0; x < Image.Width - 1; ++x)
                {
                    Color currentColor = Image.GetPixel(x, y);
                    Color tempXcolor = Image.GetPixel(x + 1, y);
                    Color tempYColor = Image.GetPixel(x, y + 1);
                    if ((Math.Sqrt(((currentColor.R - tempXcolor.R) * (currentColor.R - tempXcolor.R)) +
                        ((currentColor.G - tempXcolor.G) * (currentColor.G - tempXcolor.G)) +
                        ((currentColor.B - tempXcolor.B) * (currentColor.B - tempXcolor.B))) > Threshold)) 
                    {
                        if (lowestX > x)
                            lowestX = x;

                        if (largestX < x)
                            largestX = x;
                    }

                    if ((Math.Sqrt(((currentColor.R - tempYColor.R) * (currentColor.R - tempYColor.R)) +
                        ((currentColor.G - tempYColor.G) * (currentColor.G - tempYColor.G)) +
                        ((currentColor.B - tempYColor.B) * (currentColor.B - tempYColor.B))) > Threshold))
                    {
                        if (lowestY > y)
                            lowestY = y;

                        if (largestY < y)
                            largestY = y;
                    }
                }                
            }

            if (lowestX < Image.Width / 4)
                cropRectangle.X = lowestX - 3 > 0 ? lowestX - 3 : 0;
            else
                cropRectangle.X = 0;

            if (lowestY < Image.Height / 4)
                cropRectangle.Y = lowestY - 3 > 0 ? lowestY - 3 : 0;
            else
                cropRectangle.Y = 0;

            cropRectangle.Width = largestX - lowestX + 8 > Image.Width ? Image.Width : largestX - lowestX + 8;
            cropRectangle.Height = largestY + 8 > Image.Height ? Image.Height - lowestY : largestY - lowestY + 8;
            return cropRectangle;
        }
    }

Answer 1

一种可能的优化是使用 Lockbits直接访问颜色值，而不是通过慢得多的 GetPixel。

LockBits 上的 Bob Powell 页面 是很好的参考。

另一方面，我的测试表明，如果您尝试编写与 GetPixel 等效的 GetPixelFast 并将其作为替代品放入，与 Lockbits 相关的开销会使该方法变慢。相反，您需要确保所有像素访问都是在一次点击中完成，而不是多次点击。如果您不锁定/解锁每个像素，这应该非常适合您的代码。

这是一个示例

BitmapData bmd = b.LockBits(new Rectangle(0, 0, b.Width, b.Height), System.Drawing.Imaging.ImageLockMode.ReadOnly, b.PixelFormat);

byte* row = (byte*)bmd.Scan0 + (y * bmd.Stride);

//                           Blue                    Green                   Red 
Color c = Color.FromArgb(row[x * pixelSize + 2], row[x * pixelSize + 1], row[x * pixelSize]);

b.UnlockBits(bmd);

还有两件事需要注意：

1. 此代码不安全，因为它使用指针
2. 此方法取决于位图数据中的像素大小，因此您需要从 bitmap.PixelFormat 派生 PixelSize

Answer 2

GetPixel 可能是您的罪魁祸首（我建议运行一些分析测试来追踪它），但您可以像这样重构算法：

1. 从左到右和从右到左扫描第一行（y = 0）并记录第一个和最后一个边缘位置。没有必要检查所有像素，因为您需要的是极端边缘。
2. 扫描所有后续行，但现在我们只需要从最后一个已知的最小边缘开始向外搜索（从中心到边缘）。我们想要找到极值边界，因此我们只需要在可以找到新极值的区域中搜索即可。
3. 对列重复前两个步骤，建立初始极值，然后使用这些极值迭代限制搜索。

如果您的图像通常主要是内容，这应该会大大减少比较次数。最坏的情况是完全空白的图像，对于这种情况，这可能比穷举搜索效率低。

在极端情况下，图像处理也可以受益于并行性（分割图像并在多核 CPU 上的多个线程中处理它），但这是相当多的额外工作，您仍然可以进行其他更简单的更改。线程开销往往会限制该技术的适用性，并且如果您希望“实时”运行此东西，并专门重复处理传入数据（以弥补初始设置成本），那么线程开销会很有帮助。

Answer 3

这不会使订单变得更好......但是如果您对阈值进行平方，则不需要进行平方根，这是非常昂贵的。

这应该会显着提高速度。