Хотя я не уверен, как перевести следующий алгоритм в GA (и я не уверен, почему вам нужно использовать GA для этой проблемы), и я мог бы не согласиться с предложением этого, здесь идет речь.
Простая техника, которую я бы предложил, это подсчитать количество черных пикселей в строке. (На самом деле это плотность темных пикселей в ряду.) Для этого требуется очень мало операций, и с помощью нескольких дополнительных вычислений нетрудно найти пики в гистограмме суммы пикселей.
Необработанная гистограмма будет выглядеть примерно так: профиль в левой части экрана показывает количество темных пикселей в строке. Для наглядности фактическое количество нормировано для растяжения до x = 200.
После добавления некоторой дополнительной простой обработки (описанной ниже) мы можем сгенерировать подобную гистограмму, которая может быть обрезана до некоторого порогового значения. Остались пики, указывающие на центр строк текста.
Оттуда очень просто найти линии: просто обрезать (порог) гистограммы при некотором значении, таком как 1/2 или 2/3 максимума, и при необходимости проверить, что ширина пика на вашем пороге отсечения равна некоторое минимальное значение w.
Одна из реализаций полного (но все еще простого!) Алгоритма для нахождения лучшей гистограммы выглядит следующим образом:
- Выполняйте бинаризацию изображения с использованием порога «скользящего среднего» или аналогичного метода локальной пороговой обработки в случае, если стандартный порог Оцу, работающий с пикселями вблизи краев, не является удовлетворительным. Или, если у вас хорошее черно-белое изображение, просто используйте 128 в качестве порога бинаризации.
- Создать массив для хранения вашей гистограммы. Длина этого массива будет высотой изображения.
- Для каждого пикселя (x, y) в бинаризованном изображении найдите количество темных пикселей выше и ниже (x, y) на некотором радиусе R. То есть подсчитайте количество темных пикселей из (x, y - R) до x (y + R) включительно.
- Если количество темных пикселей в пределах вертикального радиуса R равно или больше R, то есть, по крайней мере, половина пикселей темная, то у пикселя (x, y) достаточно вертикальных темных соседей. Увеличьте количество бинов для строки y.
- По мере продвижения по каждой строке отслеживайте крайнее левое и правое значения x для пикселей с достаточным количеством соседей. Пока ширина (справа - слева + 1) превышает некоторое минимальное значение, делите общее количество темных пикселей на эту ширину. Это нормализует счет, чтобы обеспечить включение коротких строк, таких как самая последняя строка текста.
- (Необязательно) Сгладьте полученную гистограмму. Я просто использовал среднее значение для 3 строк.
«Вертикальный отсчет» (шаг 3) исключает горизонтальные штрихи, которые оказываются расположенными выше или ниже центральной строки текста. Более сложный алгоритм будет просто проверять непосредственно сверху и снизу (x, y), а также в верхний левый, верхний правый, нижний левый и нижний правый.
С моей довольно грубой реализацией в C # я смог обработать изображение менее чем за 75 миллисекунд. В C ++ и при некоторой базовой оптимизации я почти не сомневаюсь, что время можно значительно сократить.
Этот метод гистограммы предполагает, что текст горизонтальный. Поскольку алгоритм достаточно быстрый, у вас может быть достаточно времени для вычисления гистограммы количества пикселей с шагом каждые 5 градусов от горизонтали. Ориентация сканирования с наибольшим различием пика / впадины будет указывать на вращение.
Я не знаком с терминологией GA, но если то, что я предложил, имеет какую-то ценность, я уверен, что вы можете перевести это в термины GA. В любом случае, я все равно заинтересовался этой проблемой, так что я мог бы также поделиться.
РЕДАКТИРОВАТЬ: возможно, для использования GA, лучше думать о «расстоянии с предыдущего темного пикселя в X» (или вдоль угла тета) и «расстоянии с предыдущего темного пикселя в 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;