Я пишу простое решение для распознавания текста для конечного набора символов.То есть я точно знаю, как будут выглядеть все 26 букв алфавита.Я использую C # и могу легко определить, следует ли рассматривать данный пиксель как черный или белый.
Я генерирую матрицу из черных / белых пикселей для каждого отдельного символа.Так, например, буква I (заглавная i) может выглядеть следующим образом:
01110
00100
00100
00100
01110
Примечание: все точки, которые я использую позже в этом посте, предполагают, что верхний левый пиксель равен (0,0), нижний правый пиксель (4, 4).1 представляют черные пиксели, а 0 представляют белые пиксели.
Я бы создал соответствующую матрицу в C # следующим образом:
CreateLetter("I", new List<List<bool>>() {
new List<bool>() { false, true, true, true, false },
new List<bool>() { false, false, true, false, false },
new List<bool>() { false, false, true, false, false },
new List<bool>() { false, false, true, false, false },
new List<bool>() { false, true, true, true, false }
});
Я знаю, что, вероятно, мог бы оптимизировать эту часть, используя несколькоразмерный массив вместо этого, но давайте сейчас проигнорируем это для иллюстративных целей.Каждая буква имеет одинаковые размеры, 10px на 11px (10px на 11px - это фактические размеры символа в моей настоящей программе. Я упростил это до 5px на 5px в этой публикации, так как «рисовать» буквы с помощью 0 гораздо прощеи 1 на меньшем изображении).
Теперь, когда я даю ему часть изображения размером 10 на 11 пикселей для анализа с помощью оптического распознавания символов, необходимо выполнить каждую букву (26) на каждом пикселе (10).* 11 = 110), что означало бы 2860 (26 * 110) итераций (в худшем случае) для каждого отдельного символа.
Я думал, что это можно оптимизировать путем определения уникальных характеристик каждого символа.Итак, предположим, например, что набор символов состоит только из 5 различных букв: I, A, O, B и L. Они могут выглядеть следующим образом:
01110 00100 00100 01100 01000
00100 01010 01010 01010 01000
00100 01110 01010 01100 01000
00100 01010 01010 01010 01000
01110 01010 00100 01100 01110
После анализа уникальногохарактеристики каждого персонажа, я могу значительно сократить количество тестов, которые необходимо выполнить, чтобы проверить для персонажа.Например, для символа «я» я мог бы определить его уникальные характеристики как наличие черного пикселя в координате (3, 0), поскольку ни один другой символ не имеет такой пиксель как черный.Таким образом, вместо проверки 110 пикселей на соответствие для символа «I», я уменьшил его до 1 пиксельного теста.
Вот как это может выглядеть для всех этих символов:
var LetterI = new OcrLetter() {
Name = "I",
BlackPixels = new List<Point>() { new Point (3, 0) }
}
var LetterA = new OcrLetter() {
Name = "A",
WhitePixels = new List<Point>() { new Point(2, 4) }
}
var LetterO = new OcrLetter() {
Name = "O",
BlackPixels = new List<Point>() { new Point(3, 2) },
WhitePixels = new List<Point>() { new Point(2, 2) }
}
var LetterB = new OcrLetter() {
Name = "B",
BlackPixels = new List<Point>() { new Point(3, 1) },
WhitePixels = new List<Point>() { new Point(3, 2) }
}
var LetterL = new OcrLetter() {
Name = "L",
BlackPixels = new List<Point>() { new Point(1, 1), new Point(3, 4) },
WhitePixels = new List<Point>() { new Point(2, 2) }
}
Это сложно сделать вручную для 5 символов и становится тем сложнее, чем больше количество добавляемых букв.Вы также хотите гарантировать, что у вас есть минимальный набор уникальных характеристик буквы, поскольку вы хотите максимально оптимизировать ее.
Я хочу создать алгоритм, который будет определять уникальные характеристики всехбуквы и будет генерировать код, аналогичный приведенному выше.Затем я использовал бы эту оптимизированную черно-белую матрицу для идентификации символов.
Как мне взять 26 букв, у которых заполнены все их черные / белые пиксели (например, кодовый блок CreateLetter), и преобразовать их в оптимизированныйнабор уникальных характеристик, которые определяют букву (например, новый кодовый блок OcrLetter ())?И как я могу гарантировать, что это наиболее эффективный набор уникальных характеристик (например, вместо определения 6 баллов в качестве уникальных характеристик, может быть способ сделать это с 1 или 2 баллами, как буква «я» в моемПример был в состоянии).
Альтернативное решение, которое я придумал, заключается в использовании хеш-таблицы, которая сократит ее с 2860 итераций до 110 итераций, что в 26 раз меньше.Вот как это может работать:
Я бы заполнил его данными, подобными следующим:
Letters["01110 00100 00100 00100 01110"] = "I";
Letters["00100 01010 01110 01010 01010"] = "A";
Letters["00100 01010 01010 01010 00100"] = "O";
Letters["01100 01010 01100 01010 01100"] = "B";
Теперь, когда я добираюсь до места на изображении для обработки, я преобразую его встроку, такую как: "01110 00100 00100 00100 01110" и просто найдите ее в хэш-таблице.Это решение кажется очень простым, однако для генерации этой строки для каждой буквы требуется 110 итераций.
В больших обозначениях O алгоритм такой же, поскольку O (110N) = O (2860N) = O (N) для обработки N букв на странице. Тем не менее, он все еще улучшается с постоянным коэффициентом 26, что является значительным улучшением (например, вместо того, чтобы занимать 26 минут, это займет 1 минуту).
Обновление: Большинство предоставленных решений пока не решают проблему определения уникальных характеристик персонажа и скорее предоставляют альтернативные решения. Я все еще ищу это решение, которое, насколько я могу судить, является единственным способом добиться самой быстрой обработки распознавания.
Я только что нашел частичное решение:
Для каждого пикселя в сетке сохраняйте буквы с черным пикселем.
Используя эти буквы:
I A O B L
01110 00100 00100 01100 01000
00100 01010 01010 01010 01000
00100 01110 01010 01100 01000
00100 01010 01010 01010 01000
01110 01010 00100 01100 01110
У вас будет что-то вроде этого:
CreatePixel(new Point(0, 0), new List<Char>() { });
CreatePixel(new Point(1, 0), new List<Char>() { 'I', 'B', 'L' });
CreatePixel(new Point(2, 0), new List<Char>() { 'I', 'A', 'O', 'B' });
CreatePixel(new Point(3, 0), new List<Char>() { 'I' });
CreatePixel(new Point(4, 0), new List<Char>() { });
CreatePixel(new Point(0, 1), new List<Char>() { });
CreatePixel(new Point(1, 1), new List<Char>() { 'A', 'B', 'L' });
CreatePixel(new Point(2, 1), new List<Char>() { 'I' });
CreatePixel(new Point(3, 1), new List<Char>() { 'A', 'O', 'B' });
// ...
CreatePixel(new Point(2, 2), new List<Char>() { 'I', 'A', 'B' });
CreatePixel(new Point(3, 2), new List<Char>() { 'A', 'O' });
// ...
CreatePixel(new Point(2, 4), new List<Char>() { 'I', 'O', 'B', 'L' });
CreatePixel(new Point(3, 4), new List<Char>() { 'I', 'A', 'L' });
CreatePixel(new Point(4, 4), new List<Char>() { });
Теперь для каждой буквы, чтобы найти уникальные характеристики, вам нужно посмотреть, к каким корзинам она принадлежит, а также количество других символов в корзине. Итак, давайте возьмем пример «я». Мы переходим ко всем сегментам, к которым он принадлежит (1,0; 2,0; 3,0; ...; 3,4), и видим, что один с наименьшим количеством других символов равен (3,0). Фактически, он имеет только 1 символ, то есть в данном случае это должно быть «я», и мы нашли нашу уникальную характеристику.
Вы можете сделать то же самое для пикселей, которые будут белыми. Обратите внимание, что bucket (2,0) содержит все буквы, кроме «L», это означает, что его можно использовать в качестве теста белого пикселя. Точно так же (2,4) не содержит «A».
Контейнеры, которые содержат либо все буквы, либо ни одну из букв, могут быть немедленно отброшены, поскольку эти пиксели не могут помочь определить уникальную характеристику (например, 1,1; 4,0; 0,1; 4,4).
Это становится сложнее, когда у вас нет 1-пиксельного теста для буквы, например, в случае «O» и «B». Давайте пройдемся по тесту на 'O' ...
Содержится в следующих контейнерах:
// Bucket Count Letters
// 2,0 4 I, A, O, B
// 3,1 3 A, O, B
// 3,2 2 A, O
// 2,4 4 I, O, B, L
Кроме того, у нас также есть несколько тестов белых пикселей, которые могут помочь: (Я перечислил только те, которые отсутствуют не более 2). Недостающий счет был рассчитан как (5 - Bucket.Count).
// Bucket Missing Count Missing Letters
// 1,0 2 A, O
// 1,1 2 I, O
// 2,2 2 O, L
// 3,4 2 O, B
Итак, теперь мы можем взять самый короткий черный пиксель (3,2) и увидеть, что когда мы проверяем (3,2), мы знаем, что это либо «А», либо «О». Поэтому нам нужен простой способ определить разницу между буквой «А» и буквой «О». Мы могли бы искать черный пиксельный сегмент, который содержит «О», но не «А» (например, 2,4), или белый пиксельный сегмент, который содержит «О», но не «А» (например, 1,1). Любой из них можно использовать в сочетании с (3,2) пикселем, чтобы однозначно идентифицировать букву «О» только с двумя тестами.
Это похоже на простой алгоритм, когда есть 5 символов, но как бы я это сделал, если перекрываются 26 букв и намного больше пикселей? Например, предположим, что после (3,2) пиксельного теста было найдено 10 различных символов, которые содержат пиксель (и это было наименьшим из всех сегментов). Теперь мне нужно найти отличия от 9 других персонажей, а не только от 1 другого персонажа. Как бы я достиг своей цели - получить как можно меньше проверок и убедиться, что я не выполняю посторонние тесты?