高效确定图像倾斜的方法

Question

我正在尝试编写一个程序，以编程方式确定任意图像的倾斜或旋转角度。

图像具有以下属性：

• 由浅色背景上的深色文本组成
• 偶尔包含仅以90度角交叉的水平或垂直线条。
• 倾斜角度在-45到45度之间。
• 请参考此图片（它被倾斜了2.8度）。

到目前为止，我想出了这个策略：从左到右绘制路径，始终选择最近的白色像素。可以预期，从左到右的路径将更喜欢沿图像的倾斜线路跟随文本行之间的路径。

下面是我的代码：

private bool IsWhite(Color c) { return c.GetBrightness() >= 0.5 || c == Color.Transparent; }

private bool IsBlack(Color c) { return !IsWhite(c); }

private double ToDegrees(decimal slope) { return (180.0 / Math.PI) * Math.Atan(Convert.ToDouble(slope)); }

private void GetSkew(Bitmap image, out double minSkew, out double maxSkew)
{
    decimal minSlope = 0.0M;
    decimal maxSlope = 0.0M;
    for (int start_y = 0; start_y < image.Height; start_y++)
    {
        int end_y = start_y;
        for (int x = 1; x < image.Width; x++)
        {
            int above_y = Math.Max(end_y - 1, 0);
            int below_y = Math.Min(end_y + 1, image.Height - 1);

            Color center = image.GetPixel(x, end_y);
            Color above = image.GetPixel(x, above_y);
            Color below = image.GetPixel(x, below_y);

            if (IsWhite(center)) { /* no change to end_y */ }
            else if (IsWhite(above) && IsBlack(below)) { end_y = above_y; }
            else if (IsBlack(above) && IsWhite(below)) { end_y = below_y; }
        }

        decimal slope = (Convert.ToDecimal(start_y) - Convert.ToDecimal(end_y)) / Convert.ToDecimal(image.Width);
        minSlope = Math.Min(minSlope, slope);
        maxSlope = Math.Max(maxSlope, slope);
    }

    minSkew = ToDegrees(minSlope);
    maxSkew = ToDegrees(maxSlope);
}

这在一些图像上效果很好，在另一些图像上效果不佳，而且速度较慢。

是否有更高效、更可靠的方法来确定图像的倾斜？

- Juliet

---

我喜欢这段代码如何混合使用snake_case、camelCase和PascalCase，而且都在一小块代码中。显然我写了太多的F#。 - Juliet

你为什么要使用 decimal？它对计算斜率的精度没有太大帮助，而且在传递给 atan 方法时还必须将其强制转换回 double。 - Cecil Has a Name

@Cecil：将一系列的浮点数相加和除以可能引起精度问题。最好的方法是先使用小数进行计算，然后在最后转换为浮点数，这样可以避免不必要的麻烦。 - Juliet

谷歌和谷歌学术为“文档斜角”提供了无数相关结果（感谢关键词，plinth）。你在那里寻找算法思路了吗？ - lguy

很棒的讨论！谢谢。不只是选择下一个白色像素，为什么不选择下一个离其区域相邻的黑色像素最远的白色像素呢？字体高度大小的区域应该能很好地工作。使用卷积核可以很快地完成这个过程。 - Perry Horwich

Answer 1

我已经对我的代码进行了一些修改，它运行得更快了，但是不够准确。

我做了以下改进：

• 使用Vinko的建议，我避免使用GetPixel而是直接使用字节处理，现在代码运行速度符合我的要求。

• 我的原始代码只是使用“IsBlack”和“IsWhite”，但这不够精细。原始代码通过图像跟踪以下路径：

  http://img43.imageshack.us/img43/1545/tilted3degtextoriginalw.gif

  请注意，许多路径通过文本。通过将我的中心、上方和下方路径与实际亮度值进行比较并选择最亮的像素。基本上，我将位图视为高度图，并且从左到右的路径沿着图像的轮廓走，结果是更好的路径：

  http://img10.imageshack.us/img10/5807/tilted3degtextbrightnes.gif

  如Toaomalkster所建议的，高斯模糊可以平滑高度图，我得到了更好的结果：

  http://img197.imageshack.us/img197/742/tilted3degtextblurredwi.gif

  由于这只是原型代码，我使用GIMP模糊图像，我没有编写自己的模糊函数。

  所选路径对于贪婪算法来说相当不错。

• 如Toaomalkster所建议的，选择最小/最大斜率是幼稚的。简单的线性回归提供了路径斜率更好的近似值。此外，一旦我跑出图像边缘，我应该缩短路径，否则路径将紧贴图像顶部并给出错误的斜率。

代码

private double ToDegrees(double slope) { return (180.0 / Math.PI) * Math.Atan(slope); }

private double GetSkew(Bitmap image)
{
    BrightnessWrapper wrapper = new BrightnessWrapper(image);

    LinkedList<double> slopes = new LinkedList<double>();

    for (int y = 0; y < wrapper.Height; y++)
    {
        int endY = y;

        long sumOfX = 0;
        long sumOfY = y;
        long sumOfXY = 0;
        long sumOfXX = 0;
        int itemsInSet = 1;
        for (int x = 1; x < wrapper.Width; x++)
        {
            int aboveY = endY - 1;
            int belowY = endY + 1;

            if (aboveY < 0 || belowY >= wrapper.Height)
            {
                break;
            }

            int center = wrapper.GetBrightness(x, endY);
            int above = wrapper.GetBrightness(x, aboveY);
            int below = wrapper.GetBrightness(x, belowY);

            if (center >= above && center >= below) { /* no change to endY */ }
            else if (above >= center && above >= below) { endY = aboveY; }
            else if (below >= center && below >= above) { endY = belowY; }

            itemsInSet++;
            sumOfX += x;
            sumOfY += endY;
            sumOfXX += (x * x);
            sumOfXY += (x * endY);
        }

        // least squares slope = (NΣ(XY) - (ΣX)(ΣY)) / (NΣ(X^2) - (ΣX)^2), where N = elements in set
        if (itemsInSet > image.Width / 2) // path covers at least half of the image
        {
            decimal sumOfX_d = Convert.ToDecimal(sumOfX);
            decimal sumOfY_d = Convert.ToDecimal(sumOfY);
            decimal sumOfXY_d = Convert.ToDecimal(sumOfXY);
            decimal sumOfXX_d = Convert.ToDecimal(sumOfXX);
            decimal itemsInSet_d = Convert.ToDecimal(itemsInSet);
            decimal slope =
                ((itemsInSet_d * sumOfXY) - (sumOfX_d * sumOfY_d))
                /
                ((itemsInSet_d * sumOfXX_d) - (sumOfX_d * sumOfX_d));

            slopes.AddLast(Convert.ToDouble(slope));
        }
    }

    double mean = slopes.Average();
    double sumOfSquares = slopes.Sum(d => Math.Pow(d - mean, 2));
    double stddev = Math.Sqrt(sumOfSquares / (slopes.Count - 1));

    // select items within 1 standard deviation of the mean
    var testSample = slopes.Where(x => Math.Abs(x - mean) <= stddev);

    return ToDegrees(testSample.Average());
}

class BrightnessWrapper
{
    byte[] rgbValues;
    int stride;
    public int Height { get; private set; }
    public int Width { get; private set; }

    public BrightnessWrapper(Bitmap bmp)
    {
        Rectangle rect = new Rectangle(0, 0, bmp.Width, bmp.Height);

        System.Drawing.Imaging.BitmapData bmpData =
            bmp.LockBits(rect,
                System.Drawing.Imaging.ImageLockMode.ReadOnly,
                bmp.PixelFormat);

        IntPtr ptr = bmpData.Scan0;

        int bytes = bmpData.Stride * bmp.Height;
        this.rgbValues = new byte[bytes];

        System.Runtime.InteropServices.Marshal.Copy(ptr,
                       rgbValues, 0, bytes);

        this.Height = bmp.Height;
        this.Width = bmp.Width;
        this.stride = bmpData.Stride;
    }

    public int GetBrightness(int x, int y)
    {
        int position = (y * this.stride) + (x * 3);
        int b = rgbValues[position];
        int g = rgbValues[position + 1];
        int r = rgbValues[position + 2];
        return (r + r + b + g + g + g) / 6;
    }
}

代码很不错，但并非十分出色。大量的空格导致程序绘制出相对平坦的线条，在斜率接近0的情况下，代码会低估图像的实际倾斜度。

通过选择随机样本点和对所有点进行采样来测量倾斜度的准确性没有明显差异，因为随机采样选择的“平坦”路径比例与整个图像中的“平坦”路径比例相同。

- Juliet

---

如果你在想，我正在以一种奇怪的方式混合小数和双精度浮点数来保证精度。当使用双精度浮点数计算线性回归时，我总是得到NaN，但是使用小数却可以正常工作。 - Juliet

Answer 2

GetPixel很慢。你可以使用这里列出的方法，获得数量级的加速。

- Vinko Vrsalovic

Answer 3

首先，我必须说我喜欢这个想法。但我以前从未做过这样的事情，也不确定应该提出什么建议来提高可靠性。我能想到的第一件事是排除统计异常值的想法。如果斜率突然急剧变化，那么您就知道找到了图像的白色部分，它倾斜到边缘，扭曲了您的结果。因此，您需要以某种方式将其排除。

但从性能的角度来看，您可以进行许多优化，这可能会累加起来。

即，我会将您内部循环的代码片段从以下内容更改为：

Color center = image.GetPixel(x, end_y);
Color above = image.GetPixel(x, above_y);
Color below = image.GetPixel(x, below_y);

if (IsWhite(center)) { /* no change to end_y */ }
else if (IsWhite(above) && IsBlack(below)) { end_y = above_y; }
else if (IsBlack(above) && IsWhite(below)) { end_y = below_y; }

转换为：

变为：

Color center = image.GetPixel(x, end_y);

if (IsWhite(center)) { /* no change to end_y */ }
else
{
    Color above = image.GetPixel(x, above_y);
    Color below = image.GetPixel(x, below_y);
    if (IsWhite(above) && IsBlack(below)) { end_y = above_y; }
    else if (IsBlack(above) && IsWhite(below)) { end_y = below_y; }
}

这个方法产生的效果相同，但应该会大大减少对GetPixel的调用次数。此外，在开始疯狂循环之前，请考虑将不变的值存储在变量中。例如，像image.Height和image.Width这样的东西每次调用时都会有一些开销。因此，在循环开始之前，请将这些值存储在自己的变量中。当处理嵌套循环时，我总是告诉自己要优化最内层循环中的所有内容，而不顾其他一切。

此外...正如Vinko Vrsalovic所建议的那样，您可以查看他提供的GetPixel替代方案，以获得更快的速度。

- Steve Wortham

---

因为 IsBlack == !IsWhite，所以 IsBlack 的返回值可以被缓存并用于两个 if 语句。 - strager

Answer 4

如果文本是左对齐（右对齐），您可以通过测量图像的左（右）边缘和两个随机位置的第一个暗像素之间的距离，并从中计算出斜率来确定斜率。进行额外的测量可以降低误差，但需要更多时间。

- CannibalSmith

---

如果你选择这条路线，我建议你选择大约10到20个随机样本点，然后排除统计异常值（即落在文本行之间的样本）。然后剩下的样本应该会画出一条相当直的线，你可以用它们来计算斜率。 - Steve Wortham

根据有限的实验，我选择随机样本点与采样所有点并没有得到更好的结果。图像中的空白区域，例如分段间的空格，采用接近零的斜率进行采样。由于随机采样将按比例选择整个图像中“平坦”路径的频率，因此我不会得到更好的近似，只会得到一个非确定性的结果。然而，我发现在平均值标准差范围内对所有路径进行平均可以给我更好的整体平均值。 - Juliet

Answer 5

乍一看，你的代码看起来过于幼稚。这就解释了为什么它不总是有效。

我喜欢 Steve Wortham 建议的方法，但如果你有背景图像，它可能会遇到问题。

另一个经常帮助处理图像的方法是先将它们模糊。如果你足够模糊你的示例图像，每行文本将变成模糊的平滑线条。然后，你可以应用某种算法基本上进行回归分析。有很多方法可以做到这一点，在网上也有很多例子。

边缘检测可能有用，但也可能会引起更多的问题。

顺便说一下，如果你努力搜索代码，高斯模糊可以实现得非常高效。否则，我相信有很多库可供使用。最近没怎么做这方面的事情，所以手头没有任何链接。但是搜索图像处理库将会给你带来好的结果。

我假设你正在享受解决这个问题的乐趣，所以这里没有太多实际实现的细节。

- Toaomalkster

Answer 6

在时间方面，你有什么限制吗？

Hough变换是一种非常有效的机制，用于确定图像的倾斜角。它可能会花费很多时间，但如果您要使用高斯模糊，则已经消耗了大量的CPU时间。还有其他加速Hough变换的方法，涉及创造性的图像采样。

- plinth

Answer 7

测量每条线的角度似乎有些过头了，特别是考虑到GetPixel的性能。

我想知道是否可以通过在左上角或右上角（取决于倾斜方向）寻找一个白色三角形并测量斜边的角度来获得更好的性能。所有文本应该遵循页面上相同的角度，而页面的左上角不会被上面内容的下降字符或空格所干扰。

另一个要考虑的提示：与其模糊处理，不如在大大降低分辨率的情况下进行处理。这将为您提供所需的更平滑数据，并减少GetPixel调用次数。

例如，我曾经在.NET中为传真TIFF文件制作了一个空白页检测程序，它只是将整个页面重新采样到一个像素，并测试白色的阈值值。

- richardtallent

Answer 8

非常酷的路径查找应用程序。 我想知道这种方法是否会对您特定的数据集有帮助或伤害。

假设有一张黑白图像：

• 将所有黑色像素投影到右侧（东）。这应该会得到一个大小为IMAGE_HEIGHT的一维数组。将数组称为CANVAS。
• 在投影所有像素到东边时，数值上跟踪每个CANVAS箱中有多少像素被投影。
• 旋转图像任意角度并重新投影。
• 选择在CANVAS值的最高峰和最低谷的结果。

我想，如果实际上您必须考虑实际的-45->+45度倾斜，这种方法可能不起作用。如果实际数字更小（+/- 10度），那么这可能是一个相当好的策略。一旦您有了初始结果，您可以考虑使用更小的角度增量重新运行以微调答案。因此，我可能会尝试编写一个接受浮点度数刻度作为参数的函数，以便我可以使用相同的代码运行粗略和精细的传递（或粗略或精细的光谱）。

这可能会消耗大量计算资源。为了优化，您可以考虑选择图像的一部分进行投影-测试-旋转-重复操作。

- Perry Horwich

Answer 9

最近你的输出结果有点让我困惑。 当你在原始图像上叠加蓝色线条时，是否稍微偏移了一下？看起来蓝线大约比文本中心高出5个像素。

不确定那个偏移量，但你的衍生线条明显存在“漂移”，角度不正确。它似乎过于偏向生成水平线条。

我想知道将你的掩模窗口从3个像素（中心、上方和下方各一个）增加到5个像素（上下各两个）是否可以改善这个问题。如果你按照richardtallent的建议缩小图像，也会产生这种效果。

- Toaomalkster