自动将位图裁剪到最小尺寸？

Question

假设我有一个32bpp ARGB模式的System.Drawing.Bitmap。这是一个大位图，但它主要是完全透明的像素，而实际图像只占据其中较小的一部分。

有什么快速算法可以检测“真实”图像的边界，以便我可以裁剪掉周围所有的透明像素吗？

或者，.Net中是否已经有可用于此的函数？

- Blorgbeard

---

截止线是直的吗？如果是，从左到右和从上到下读取像素会非常快。 - Mitchel Sellers

如果它是正方形，你可能可以节省更多时间，并从中心向外在所有4个边上进行二分搜索（至少减少像素询问）。 - Brad Christie

这个小的嵌入式图像里面也可以有透明像素吗？ - Andrew Garrison

不幸的是，图像可以是任何形状。 - Blorgbeard

@Andrew：是的，它也可能包含透明像素。 - Blorgbeard

我看不到比O(n^2)更好的解决方法。 - Andrew Garrison

Answer 1

基本思路是检查图像的每个像素，以找到图像的顶部、左侧、右侧和底部边界。为了高效地完成这个任务，不要使用 GetPixel 方法，因为它相当慢。改用 LockBits 方法。

以下是我提出的实现方法：

static Bitmap TrimBitmap(Bitmap source)
{
    Rectangle srcRect = default(Rectangle);
    BitmapData data = null;
    try
    {
        data = source.LockBits(new Rectangle(0, 0, source.Width, source.Height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);
        byte[] buffer = new byte[data.Height * data.Stride];
        Marshal.Copy(data.Scan0, buffer, 0, buffer.Length);
        int xMin = int.MaxValue;
        int xMax = 0;
        int yMin = int.MaxValue;
        int yMax = 0;
        for (int y = 0; y < data.Height; y++)
        {
            for (int x = 0; x < data.Width; x++)
            {
                byte alpha = buffer[y * data.Stride + 4 * x + 3];
                if (alpha != 0)
                {
                    if (x < xMin) xMin = x;
                    if (x > xMax) xMax = x;
                    if (y < yMin) yMin = y;
                    if (y > yMax) yMax = y;
                }
            }
        }
        if (xMax < xMin || yMax < yMin)
        {
            // Image is empty...
            return null;
        }
        srcRect = Rectangle.FromLTRB(xMin, yMin, xMax, yMax);
    }
    finally
    {
        if (data != null)
            source.UnlockBits(data);
    }

    Bitmap dest = new Bitmap(srcRect.Width, srcRect.Height);
    Rectangle destRect = new Rectangle(0, 0, srcRect.Width, srcRect.Height);
    using (Graphics graphics = Graphics.FromImage(dest))
    {
        graphics.DrawImage(source, destRect, srcRect, GraphicsUnit.Pixel);
    }
    return dest;
}

这段代码可能还可以优化，但我不是GDI+专家，所以在继续研究之前，这已经是我最好的了...

---

编辑：实际上，有一种简单的方法可以进行优化，即不扫描图像的某些部分：

1. 从左到右扫描，直到找到一个非透明像素；将(x, y)存储到(xMin, yMin)
2. 从上到下扫描，直到找到一个非透明像素（仅对x>= xMin）; 将y存储到yMin
3. 从右到左扫描，直到找到一个非透明像素（仅对y>= yMin）; 将x存储到xMax
4. 从下到上扫描，直到找到一个非透明像素（仅对xMin <= x <= xMax）; 将y存储到yMax

---

编辑2：以下是上述方法的实现:

static Bitmap TrimBitmap(Bitmap source)
{
    Rectangle srcRect = default(Rectangle);
    BitmapData data = null;
    try
    {
        data = source.LockBits(new Rectangle(0, 0, source.Width, source.Height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);
        byte[] buffer = new byte[data.Height * data.Stride];
        Marshal.Copy(data.Scan0, buffer, 0, buffer.Length);

        int xMin = int.MaxValue,
            xMax = int.MinValue,
            yMin = int.MaxValue,
            yMax = int.MinValue;

        bool foundPixel = false;

        // Find xMin
        for (int x = 0; x < data.Width; x++)
        {
            bool stop = false;
            for (int y = 0; y < data.Height; y++)
            {
                byte alpha = buffer[y * data.Stride + 4 * x + 3];
                if (alpha != 0)
                {
                    xMin = x;
                    stop = true;
                    foundPixel = true;
                    break;
                }
            }
            if (stop)
                break;
        }

        // Image is empty...
        if (!foundPixel)
            return null;

        // Find yMin
        for (int y = 0; y < data.Height; y++)
        {
            bool stop = false;
            for (int x = xMin; x < data.Width; x++)
            {
                byte alpha = buffer[y * data.Stride + 4 * x + 3];
                if (alpha != 0)
                {
                    yMin = y;
                    stop = true;
                    break;
                }
            }
            if (stop)
                break;
        }

        // Find xMax
        for (int x = data.Width - 1; x >= xMin; x--)
        {
            bool stop = false;
            for (int y = yMin; y < data.Height; y++)
            {
                byte alpha = buffer[y * data.Stride + 4 * x + 3];
                if (alpha != 0)
                {
                    xMax = x;
                    stop = true;
                    break;
                }
            }
            if (stop)
                break;
        }

        // Find yMax
        for (int y = data.Height - 1; y >= yMin; y--)
        {
            bool stop = false;
            for (int x = xMin; x <= xMax; x++)
            {
                byte alpha = buffer[y * data.Stride + 4 * x + 3];
                if (alpha != 0)
                {
                    yMax = y;
                    stop = true;
                    break;
                }
            }
            if (stop)
                break;
        }

        srcRect = Rectangle.FromLTRB(xMin, yMin, xMax, yMax);
    }
    finally
    {
        if (data != null)
            source.UnlockBits(data);
    }

    Bitmap dest = new Bitmap(srcRect.Width, srcRect.Height);
    Rectangle destRect = new Rectangle(0, 0, srcRect.Width, srcRect.Height);
    using (Graphics graphics = Graphics.FromImage(dest))
    {
        graphics.DrawImage(source, destRect, srcRect, GraphicsUnit.Pixel);
    }
    return dest;
}

当然，如果非透明部分很小，那么不会有显着的增益，因为它仍将扫描大部分像素。但是，如果非透明部分很大，只有围绕非透明部分的矩形将被扫描。

- Thomas Levesque

---

顺便说一句，我刚意识到有一种更简单的方法来裁剪图像，而不需要使用 Graphics：return source.Clone(srcRect, source.PixelFormat); - Thomas Levesque

很好的解决方案，非常有帮助，但我发现我的图片被裁剪了一个像素太多。在逻辑上你的方法是正确的，但我已经将调用Rectangle.FromLTRB更改为**srcRect = Rectangle.FromLTRB(xMin, yMin, xMax + 1, yMax + 1)**，现在它完美地运行了。 - Joel P.

感谢您提供的代码！然而default(Rectangle)也是错误的。Windows不允许少于一个像素的位图。它会尝试失败等。 - Bitterblue

@Bitterblue，不用担心，因为“srcRect”的初始值在使用之前总是被覆盖。 - Thomas Levesque

@ThomasLevesque 不，它并不总是被覆盖。例如，data = source.LockBits(...); 可能会抛出异常，而 srcRect = ... 则位于 try 块的最后。就像我拼错的那样（^^）：“如果 try 失败等”。 - Bitterblue

@Bitterblue，如果在try块中抛出异常，则将执行finally块，并且异常将向上传播到堆栈。永远不会到达使用srcRect的地方。 - Thomas Levesque

Answer 2

我想建议采用分治法的方法：

1. 将图像从中间（例如垂直方向）分割
2. 检查切割线上是否有非透明像素（如果有，记下边界框的最小/最大值）
3. 再次将左半部分垂直分割
4. 如果切割线包含非透明像素 -> 更新边界框
5. 如果没有，则可以丢弃最左侧的一半（我不知道图片是什么样子的）
6. 继续处理左右两半（您已经说明图像在中间某处），直到找到图像的最左边界
7. 对右半部分执行相同的操作

- bjoernz

---

我认为你的第五点是错误的：可能会有几个具有非透明像素的不同区域，因此在剪切线上没有非透明像素并不意味着什么。 - Thomas Levesque

谢谢bjoernz，但是二分查找并不总适用于我的图像——例如，可能存在由空格隔开的两个图像。 - Blorgbeard