Есть ли эффективный алгоритм для сегментации рукописного текста?

Ответ 1

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

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

Необработанная гистограмма будет выглядеть примерно так, где в профиле вдоль левой стороны отображается количество темных пикселей в строке. Для видимости фактическое количество нормализуется для растягивания до x = 200.

После добавления дополнительной простой обработки (описанной ниже) мы можем создать такую ​​гистограмму, которая может быть обрезана с некоторым пороговым значением. Остаются пики, указывающие центр строк текста.

Оттуда просто найти линии: просто клип (пороговое значение) гистограммы при некотором значении, таком как 1/2 или 2/3 максимум, и, необязательно, проверить, что ширина пика на пороге отсечения равна некоторое минимальное значение w.

Одна реализация полного (еще более простого!) алгоритма для поиска более удобной гистограммы такова:

• Выполнить бинаризацию изображения с использованием порога "скользящей средней" или аналогичного метода локального порога в случае, если стандартный порог Otsu, работающий на пикселях вблизи краев, не является удовлетворительным. Или, если у вас есть хорошее черно-белое изображение, просто используйте 128 в качестве порога бинаризации.
• Создайте массив для хранения вашей гистограммы. Эта длина массива будет высотой изображения.
• Для каждого пикселя (x, y) в двоичном изображении найдите количество темных пикселей выше и ниже (x, y) на некотором радиусе R. То есть подсчитайте количество темных пикселей из (x, y - R) до x (y + R) включительно.
• Если количество темных пикселей в пределах вертикального радиуса R равно или больше R - то есть, по крайней мере половина пикселей темная, то пиксель (x, y) имеет достаточные вертикальные темные соседи. Увеличьте количество бункеров в строке y.
• По мере продвижения по каждой строке отслеживайте самые левые и самые правые значения x для пикселей с достаточным количеством соседей. Пока ширина (справа - слева + 1) превышает некоторое минимальное значение, разделите общее количество темных пикселей на эту ширину. Это нормализует счет, чтобы включить короткие строки, такие как самая последняя строка текста.
• (Необязательно) Сгладьте полученную гистограмму. Я просто использовал среднее значение в 3 строках.

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

С моей довольно грубой реализацией на С# я смог обработать изображение менее чем за 75 миллисекунд. В С++ и с некоторой базовой оптимизацией я не сомневаюсь, что время можно значительно сократить.

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

Я не знаком с терминологией GA, но если то, что я предложил, имеет какую-то ценность, я уверен, что вы можете перевести его в условия GA. В любом случае, я все равно интересовался этой проблемой, поэтому я мог бы также поделиться.

EDIT: возможно, для использования GA, лучше подумать с точки зрения "расстояния с предыдущего темного пикселя в X" (или вдоль угла theta) и "расстояния с предыдущего темного пикселя в Y" (или вдоль угла [theta-pi/2]). Вы также можете проверить расстояние от белого пикселя до темного пикселя во всех радиальных направлениях (чтобы найти петли).

byte[,] arr = get2DArrayFromBitamp();   //source array from originalBitmap
int w = arr.GetLength(0);               //width of 2D array
int h = arr.GetLength(1);               //height of 2D array

//we can use a second 2D array of dark pixels that belong to vertical strokes
byte[,] bytes = new byte[w, h];         //dark pixels in vertical strokes


//initial morph
int r = 4;        //radius to check for dark pixels
int count = 0;    //number of dark pixels within radius

//fill the bytes[,] array only with pixels belonging to vertical strokes
for (int x = 0; x < w; x++)
{
    //for the first r rows, just set pixels to white
    for (int y = 0; y < r; y++)
    {
        bytes[x, y] = 255;
    }

    //assume pixels of value < 128 are dark pixels in text
    for (int y = r; y < h - r - 1; y++)
    {
        count = 0;

        //count the dark pixels above and below (x,y)
        //total range of check is 2r, from -r to +r
        for (int j = -r; j <= r; j++)
        {
            if (arr[x, y + j] < 128) count++;
        }

        //if half the pixels are dark, [x,y] is part of vertical stroke
        bytes[x, y] = count >= r ? (byte)0 : (byte)255;
    }

    //for the last r rows, just set pixels to white
    for (int y = h - r - 1; y < h; y++)
    {
        bytes[x, y] = 255;
    }
}

//count the number of valid dark pixels in each row
float max = 0;

float[] bins = new float[h];    //normalized "dark pixel strength" for all h rows
int left, right, width;         //leftmost and rightmost dark pixels in row
bool dark = false;              //tracking variable

for (int y = 0; y < h; y++)
{
    //initialize values at beginning of loop iteration
    left = 0;
    right = 0;
    width = 100;

    for (int x = 0; x < w; x++)
    {
        //use value of 128 as threshold between light and dark
        dark = bytes[x, y] < 128;  

        //increment bin if pixel is dark
        bins[y] += dark ? 1 : 0;    

        //update leftmost and rightmost dark pixels
        if (dark)
        {
            if (left == 0) left = x;    
            if (x > right) right = x;   
        }
    }

    width = right - left + 1;

    //for bins with few pixels, treat them as empty
    if (bins[y] < 10) bins[y] = 0;      

    //normalize value according to width
    //divide bin count by width (leftmost to rightmost)
    bins[y] /= width;

    //calculate the maximum bin value so that bins can be scaled when drawn
    if (bins[y] > max) max = bins[y];   
}

//calculated the smoothed value of each bin i by averaging bin i-1, i, and i+1
float[] smooth = new float[bins.Length];

smooth[0] = bins[0];
smooth[smooth.Length - 1] = bins[bins.Length - 1];

for (int i = 1; i < bins.Length - 1; i++)
{
    smooth[i] = (bins[i - 1] + bins[i] + bins[i + 1])/3;
}

//create a new bitmap based on the original bitmap, then draw bins on top
Bitmap bmp = new Bitmap(originalBitmap);

using (Graphics gr = Graphics.FromImage(bmp))
{
    for (int y = 0; y < bins.Length; y++)
    {
        //scale each bin so that it is drawn 200 pixels wide from the left edge
        float value = 200 * (float)smooth[y] / max;
        gr.DrawLine(Pens.Red, new PointF(0, y), new PointF(value, y)); 
    }
}

pictureBox1.Image = bmp;

Ответ 2

После того, как я некоторое время спотыкался об этом, я обнаружил, что мне просто нужно подсчитать количество переходов для каждой строки, то есть переход от белого к черному будет считаться одним, а переход с черного на белый будет увеличиваться на еще раз. Выделив каждую строку счетчиком 66, я получил почти 100% -ную точность, за исключением нижней строки.

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

Ответ 3

IMHO с изображением, которое было бы настолько сложно сделать на 100% отлично. Мой ответ - дать вам альтернативную идею.

Идея 1: Создайте свою собственную версию ReCaptcha (чтобы разместить свой собственный сайт-про-сайт) - и сделайте ее забавной игрой. "Как вырезать слово (все края должны быть белыми) с некоторым допуском для перекрывающихся символов сверху и снизу строк )".

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

Идея 3: Исследование того, как google/recaptcha обошел его

Идея 4: Получите SDK для фотошопа и освойте его функциональность. Инструмент "Извлечь края"

Идея 5: Нарисуйте кучи изображений по оси Y, которые должны помочь, примените алгоритм, затем уменьшите измерения местоположения и примените их на изображении нормального размера.