Эффективные способы определить наклон изображения

Прежде всего должен сказать, что идея мне нравится. Но мне никогда раньше не приходилось этого делать, и я не уверен, что можно предложить для повышения надежности. Первое, что я могу об этом подумать, - это идея выбросить статистические аномалии. Если наклон внезапно резко меняется, то вы знаете, что нашли белый участок изображения, который переходит в перекос по краям (это не каламбур) ваших результатов. Так что вы захотите как-то выбросить это.

Но с точки зрения производительности есть ряд оптимизаций, которые вы могли бы сделать, которые могут сложиться.

А именно, я бы изменил этот фрагмент из вашего внутреннего цикла с это:

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, имеют небольшие накладные расходы каждый раз, когда вы их вызываете. Поэтому сохраните эти значения в своих переменных до начала циклов. Когда я имею дело с вложенными циклами, я всегда говорю себе, что нужно оптимизировать все внутри самого внутреннего цикла за счет всего остального.

Также ... как предложил Винко Врсалович, вы можете взглянуть на его альтернативу GetPixel, чтобы получить еще один импульс. по скорости.

Измерение угла каждой линии кажется излишним, особенно с учетом производительности GetPixel.

Интересно, повезет ли вам с производительностью, если вы отыщете белый треугольник в верхнем левом или верхнем правом углу (в зависимости от направления наклона) и измерите угол гипотенузы. Весь текст должен располагаться на странице под одним углом, и верхний левый угол страницы не будет обманут нисходящими элементами или пробелами содержимого над ним.

Еще один совет, который следует учитывать: вместо размытия работайте в пределах сильно уменьшенное разрешение. Это даст вам и более гладкие данные, которые вам нужны, и меньшее количество вызовов GetPixel.

Например, я однажды сделал процедуру обнаружения пустой страницы в .NET для отправленных по факсу файлов TIFF, которая просто преобразовала всю страницу в один пиксель и проверила значение для порогового значения белого.

и верхний левый угол страницы не будет обманут нисходящими элементами или пробелами содержимого над ним.

Еще один совет, на который следует обратить внимание: вместо размытия работайте с сильно уменьшенным разрешением. Это даст вам и более гладкие данные, которые вам нужны, и меньшее количество вызовов GetPixel.

Например, я однажды сделал процедуру обнаружения пустой страницы в .NET для отправленных по факсу файлов TIFF, которая просто преобразовала всю страницу в один пиксель и проверила значение для порогового значения белого.

и верхний левый угол страницы не будет обманут нисходящими элементами или пробелами содержимого над ним.

Еще один совет, на который следует обратить внимание: вместо размытия работайте с сильно уменьшенным разрешением. Это даст вам и более гладкие данные, которые вам нужны, и меньшее количество вызовов GetPixel.

Например, я однажды сделал процедуру обнаружения пустых страниц в .NET для отправленных по факсу файлов TIFF, которые просто преобразовали всю страницу в один пиксель и протестировали значение для порогового значения белого.

Я внес некоторые изменения в свой код, и он определенно работает намного быстрее, но не очень точен.

Я сделал следующие улучшения:

• Использование Предложение Винко , я избегаю 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, я не писал свою собственную функцию размытия.

  Выбранный путь довольно хорош для жадного алгоритма.

• Как Тоаомалкстер предложил , выбор минимального / максимального наклона наивен. Простая линейная регрессия позволяет лучше аппроксимировать наклон пути. Кроме того, я должен сократить путь после того, как убегу от края изображения, иначе путь будет охватывать верхнюю часть изображения и давать неправильный уклон.

Код

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, в результате чего код недооценивает фактический наклон изображения.

Нет заметной разницы в точности наклона при выборе случайной выборки точек против выборки всех точек, потому что соотношение "плоских" путей, выбранных случайной выборкой, такое же, как соотношение "плоских" путей во всем изображении.

Ваш последний вывод меня немного смущает. Когда вы наложили синие линии на исходное изображение, вы немного сместили его? Похоже, синие линии находятся примерно на 5 пикселей выше центра текста.

Не уверен в этом смещении, но у вас определенно есть проблема с тем, что производная линия "дрейфует" под неправильным углом. Кажется, у него слишком сильное смещение в сторону создания горизонтальной линии.

Интересно, может ли увеличение окна маски с 3 пикселей (центр, один вверху, один внизу) до 5 улучшить это (два вверху, два внизу). Вы также получите этот эффект, если последуете совету Ричардталлента и уменьшите размер изображения.

What are your constraints in terms of time?

The Hough transform is a very effective mechanism for determining the skew angle of an image. It can be costly in time, but if you're going to use Gaussian blur, you're already burning a pile of CPU time. There are also other ways to accelerate the Hough transform that involve creative image sampling.