Функция пригодности
(1/(HeigthRange + SpacesRange)
Ответ 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;
