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

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

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

Ответ 2

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

Ответ 3

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

Ответ 4

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

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

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

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 для еще одного повышения скорости.

Ответ 5

На первый взгляд ваш код выглядит чересчур наивным. Это объясняет, почему это не всегда работает.

Мне нравится подход Стив Уордам, но при возникновении фоновых изображений могут возникнуть проблемы.

Другой подход, который часто помогает с изображениями, - сначала размыть их. Если вы достаточно размываете образ вашего примера, каждая строка текста будет как размытая плавная линия. Затем вы применяете какой-то алгоритм для в основном делают регрессионный анализ. Там много способов сделать и множество примеров в сети.

Обнаружение края может быть полезным, или это может вызвать дополнительные проблемы, которые стоят.

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

Я предполагаю, что вам нравится получать удовольствие от решения этого вопроса, поэтому не так много в фактической реализации detalis здесь.

Ответ 6

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

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

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

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

Ответ 7

Каковы ваши ограничения с точки зрения времени?

Преобразование Хафа - очень эффективный механизм определения угла наклона изображения. Это может быть дорогостоящим во времени, но если вы собираетесь использовать размытие Gaussian, вы уже сжигаете кучу времени процессора. Существуют также другие способы ускорения преобразования Hough, которые включают в себя выборку творческого изображения.

Ответ 8

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

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

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

Ответ 9

Очень крутой поиск пути. Интересно, поможет ли этот другой подход или вред вашему конкретному набору данных.

Предположим, что черно-белое изображение:

• Проецируйте все черные пиксели вправо (EAST). Это должно дать результат одномерного массива с размером IMAGE_HEIGHT. Вызовите массив CANVAS.
• Когда вы проецируете все пиксели EAST, проследите за численностью количества пикселей в каждом бункере CANVAS.
• Поверните изображение произвольным числом градусов и перепроектируйте.
• Выберите результат, который дает максимальные пики и наименьшие долины для значений в CANVAS.

Я предполагаю, что это не сработает, если на самом деле вам приходится учитывать реальный -45 → +45 градусов наклона. Если фактическое число меньше (? +/- 10 градусов), это может быть довольно хорошая стратегия. После того, как вы достигнете конечного результата, вы можете рассмотреть возможность повторного запуска с меньшим шагом в градусах для точной настройки ответа. Поэтому я мог бы попытаться написать это с помощью функции, которая приняла float degree_tick как парм, чтобы я мог запускать как грубый, так и мелкий проход (или спектр грубости или тонкости) с тем же кодом.

Это может быть дорогостоящим. Чтобы оптимизировать, вы можете рассмотреть возможность выбора части изображения для прогона-теста-поворота-повтора.