Понимание цепных кодов Freeman для OCR

Ответ 1

Вам нужна функция d, которая измеряет расстояние между цепными кодами. После того, как найти письмо с заданным кодом цепи, просто:

Input:

• нормализованные цепные коды S для набора возможных букв (обычно коды каина для A-Z, a-z, 0-9,...)
• код цепи x буквы, которая должна быть обнаружена и которая может быть слегка деформирована (код цепи не будет соответствовать коду цепи в наборе S)

Алгоритм будет перебирать множество возможных цепочечных кодов и вычислять расстояние d(x,si) для каждого элемента. Буква с наименьшим расстоянием будет выходом алгоритма (идентифицированная буква).

Я бы предложил следующую функцию distance: Для двух цепных кодов добавьте разности длин в каждом направлении: d(x,si) = |x0-si0| + |x1-si1| + .. + |x7-si7|. x0 - это число 0s в цепочном коде x, si0 - это число 0s в цепочном коде si и т.д.

Пример лучше объяснит, о чем я думаю. На следующем рисунке представлены буквы 8, B и D, четвертая буква - немного деформированная 8, которая должна быть идентифицирована. Буквы написаны с помощью Arial с размером шрифта 8. Вторая строка изображения увеличена в 10 раз, чтобы лучше видеть пиксели.

Я вручную вычислил (надеюсь, правильно) нормализованные коды цепи, которые:

8:  0011223123344556756677
B:  0000011222223344444666666666
D:  00001112223334444666666666
8': 000011222223344556756666 (deformed 8)

Различия в длине (абсолют):

direction | length         | difference to 8'
          | 8 | B | D |  8'|   8 |  B |  D |
----------+---+---+---+----+-----+----+-----
        0 | 2 | 5 | 4 |  4 |   2 |  1 |  0 |
        1 | 3 | 2 | 3 |  2 |   1 |  0 |  1 |
        2 | 3 | 5 | 3 |  5 |   2 |  0 |  2 |
        3 | 3 | 2 | 3 |  2 |   1 |  0 |  1 |
        4 | 2 | 5 | 4 |  2 |   0 |  3 |  2 |
        5 | 3 | 0 | 0 |  3 |   0 |  3 |  3 |
        6 | 3 | 9 | 9 |  5 |   2 |  4 |  4 |
        7 | 3 | 0 | 0 |  1 |   2 |  1 |  1 |
----------+---+---+---+----+-----+----+-----
                        sum   10 | 12 | 14 |

8' имеет наименьшее расстояние до цепного кода 8, поэтому алгоритм идентифицирует букву 8. Расстояние до буквы B не намного больше, но это потому, что деформированный 8 выглядит почти как B.

Этот метод не является масштабирующим инвариантом. Я думаю, что есть два варианта преодоления этого:

• Для разных размеров шрифтов, имеющих разные наборы нормализованных цепочечных кодов
• Один набор нормализованных цепочечных кодов большого размера (например, 35x46 пикселей) и масштабирование входной буквы (которая должна быть идентифицирована) для этого большего размера.

Я не совсем уверен, что функция расстояния достаточно хороша для набора всех буквенно-цифровых букв, но я надеюсь на это. Чтобы свести к минимуму ошибку при идентификации письма, вы можете включить другие функции (а не только коды цепочки) на этап классификации. И снова вам понадобится дистанционная мера - на этот раз для векторов признаков.

Ответ 2

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

Используя код цепи, вы можете подсчитать некоторые свойства символа, например. число оборотов формы 344445, 244445, 2555556, 344446 (произвольное число 4s), т.е. "шипы" на букве. Скажем, в коде цепи есть 3 раздела, которые выглядят так. Итак, это почти наверняка "W"! Но это хороший случай. Вы можете подсчитывать числа разных видов вращения и сравнивать их с ранее сохраненными значениями для каждой буквы (что вы делаете вручную). Это довольно хороший классификатор, но, конечно, этого недостаточно. Невозможно отличить "D" и "O", "V" и "U". И многое зависит от вашего воображения.

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

Надеюсь, что это ответ на ваш вопрос хотя бы частично.

Обновление: Одна яркая идея только что пришла мне в голову:) Вы можете подсчитать количество монотонных последовательностей в цепочке, например, для цепочки 000111222233334443333222444455544443333 (быстрый тупой пример, на самом деле не соответствует какой-либо букве), который у нас есть 00011122223333444 3333222444455544443333,
00011122223333444 3333222 444455544443333,
000111222233334443333222 4444555 44443333,
0001112222333344433332224444555 44443333,

то есть. четыре монотонные подпоследовательности.

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

Некоторые проблемы и идеи:

• Цепочка является циклической в ​​некотором смысле, поэтому вам нужно иметь дело с обнаружением монотонности на концах цепочки (чтобы избежать ошибок "один за другим" ),
• Некоторые артефакты должны учитываться, например, если вы знаете, что письмо достаточно велико (например, высота 20 пикселей), вы хотели бы игнорировать прерывание монотонности менее трех элементов, например:)

Ответ 3

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

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

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

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

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

Некоторые случайные chit chat (игнорировать):

Я бы не использовал нейронные сети, потому что я их не понимаю и поэтому не люблю их. Тем не менее, меня всегда впечатляет работа группы Джефф Хинтонс http://www.youtube.com/watch?v=VdIURAu1-aU.

Как-то он работает в сетях, которые могут распространять информацию назад (глубокое обучение). Говорит о нем, где он дает возможность узнать, что сеть узнала о знании. Это означает, что он устанавливает один из выходных нейронов в "2", и сеть будет генерировать изображения вещей, которые, по его мнению, являются двумя на входных нейронах.

Я нашел это очень круто.

Ответ 4

В прошлом месяце я имел дело с одной и той же проблемой. Теперь я решил эту проблему по цепочке цепочек ветерок.

Код цепи ветерок - это двоичный код цепи. Затем я разрезал его на 5 частей. Очевидно, что число 0-9 имеет свой собственный символ в другой части.