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

Question

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

Я работаю над быстрым распознаванием шрифтов на экране и добился очень хороших результатов.

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

В основном это 8-связанный код цепочки, который выглядит примерно так:

  3  2  1
   \ | /
  4-- --0
   / | \
  5  6  7

Так что, если у меня есть «а», после всех моих преобразований (включая преобразование в черно-белое), я получаю что-то вроде этого:

11110
00001
01111
10001
10001
01110

Тогда его внешний контур может выглядеть следующим образом (я может ошибиться здесь, это контурная схема ASCII-искусства, и мой «алгоритм» может ошибиться в контуре, но это не главное для моего вопроса) :

 XXXX
X1111X
 XXXX1X
X01111X
X10001X
X10001X
 X111X
  XXX

После X я получаю код цепочки, который будет:

0011222334445656677

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

(Кстати, есть суперэффективная реализация, чтобы найти код цепочки, где вы просто берете 8 смежных пикселей «X», а затем просматриваете таблицу поиска 256, если у вас есть 0,1, 2,3,4,5,6 или 7)

Однако теперь мой вопрос: из этого кода цепочки 0011222334445656677, как мне найти, что у меня есть «а»?

Потому что, например, если мое 'a' выглядит так:

11110
00001
01111
10001
10001
01111  <-- This pixel is now full

Тогда мой код цепи теперь: 0002222334445656677

И все же это тоже «а».

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

Я был так далеко, и теперь я застрял ...

(Кстати, мне не нужна 100% эффективность, и такие вещи, как дифференцирование «0» от «O» или «o», на самом деле не проблема)

Answer 1

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

Введите:

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

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

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

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

Answer 2

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

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

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

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

Обновление : Одна яркая идея только что пришла мне в голову :) Вы можете сосчитать количество монотонных последовательностей в цепочке, например, для цепочки 000111222233334443333222444455544443333 (aбыстрый тупой пример, который на самом деле не соответствует ни одной букве* 44443333,
0001112222333344433332224444555 44443333 ,

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

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

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

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

Answer 3

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

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

Answer 4

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

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

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

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

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

Случайный чат (игнорировать):

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

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

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