Распознавание цифр с помощью простейшей статистики и анализа топологии

[amarao]

Это работает только для заданных шрифтов. Например, цифра 4 может как иметь замкнутый контур, так и не иметь. Кто-то может использовать ЖКИ-шный 9-сегментный шрифт, а кто-то помещать в 0 точку или шрих…

Хотя сама идея интересна — и если её чуть-чуть развить (т.е. научить компьютер «понимать» особенности буквы), возможно, заработает.

[Akr0n]

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

[amarao]

От руки? Ну это смерть всему живому, потому что я на письме очень редко делаю замкнутые кривые (т.е. 6 ближе к букве «С», аналогично и 9). Верх 8'ки практически никогда не замкнут.

[Akr0n]

Есть такое дело. Примочки типа «автозамыкания» контура, поворота рисунка и т.д. можно сверху навесить.

[Volshebnyi]

С автозамыканием 5 и 6 будут почти неотличимы. А также 8 и 9.

[Akr0n]

Точно настраивать пороги. В конечном итоге всегда приходиться чем-то жертвовать в такого рода алгоритмах.

[sergei-grigorev]

Алгоритм немножко хромает. Частенько вместо цифры 7 — получаю цифру 1

habreffect.ru/files/641/e666ae9cd/zoomit.png

[Akr0n]

Да… вот с 7 и 1 туговато… Там четверти рассчитаны, что ножка цифры 7 сильнее уходит влево. У вас попало на правую половинку.

[tibalt]

дык их и в жизни не всегда отличишь, в зависимости от подчерка

[alexxxst]

И как же надо поДчеркнуть, чтобы не отличить?
P.S. ПОЧЕРК.

[megazhuk]

Спасибо! Статья будет полезна, как одна из вводных статей по теме распознавания образов. Все просто, четко и ясно. Пытался что то похожее выдумывать (только более путаное — углы, вектора и т.п.), но при отладке (или обучении системы) терпения не хватало и начинал заново и еще более путанее ))

[Akr0n]

Рад, что кому-то пригодится:)

[samlabs821]

А можно соурс код?

[Akr0n]

Эм… Дело было давно, дело было на Delphi… Думаю любой из присутствующих, за пару часов напишет гораздо лучше :)

[NecroHill]

присутствующий я тут, но не напишу и за месяц ))

[Aquahawk]

Супер! Просто и со вкусом. Очень элегантное решение.

[braintorch]

Может быть, у меня такая манера написания цифр, но для меня процент правильных ответов составил в районе 5-10%.

[DnV]

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

[Volshebnyi]

Помнится, тут описывали шикарнейший алгоритм распознавания символов с капчи —
1) убираем шум фильтром, изображение переводим в черно-белое, и находим прямоугольные области, с наибольшим количеством черных точек.
2) Возвращаем исходное изображение и «вырезаем» найденные области
3) Распознаем штук 50 символов самостоятельно и оставляем их в качестве контрольных
4 ) Отдаем все последующие символы в руки распознавалке, чтобы сравнивала с каждой из контрольных групп

[AgentSmith]

А ссылку можно?

[Volshebnyi]

Нашел

[psylostlife]

[n1kka]

Вы просто неправильно рисуете «девятку», вот как надо :D

[AgentSmith]

Можно поподробнее про п.3?:
3. Для более высокой точности распознавания, исследуется топология. С помощью рекурсивной функции подсчитывается количество замкнутых областей.
Как подсчитать количество замкнутых областей?

[Volshebnyi]

Волновым алгоритмом, скорее всего.
Вот вам почти рабочий код на Python. Закрашенные квардраты — pixel.type = «wall»

#Получаем ближайшие пиксели
def getNearestPixels(pixel):
  return [near for near in image \
    if abs(pixel.coords.x-near.coords.x)==1 or abs(pixel.coords.y-near.coords.y)==1
  ]

#Заменяем все соседние empty тоже на wavy и возвращаем количество изменений
def DoWave():
  isChanged = False
  wavy = [pixel for pixel i image if pixel.type is "wavy"]
  for pixel in wavy:
    for near in getNearestPixels(pixel.coords)
      if near.type is empty:
        near.type = "wavy"
        isChanged = True
  return isChanged

#Обходим все и считаем сколько раз вызван волновой алгоритм
counter = 0 
for pixel in image:
  empty = [pixel for pixel in image if pixel.type is "empty"]
  if pixel is empty:
    isImageChanged = True
    pixel.type = "wavy";
    while isImageChanged:
      isImageChanged = doWave()
    counter +=1

[Volshebnyi]

Щерт =)
if abs(pixel.coords.x-near.coords.x)==1 and abs(pixel.coords.y-near.coords.y)==1

[Volshebnyi]

Нет, писать скрипты за минуту для наглядности — не мой стиль. Почему-то на практике подобные ошибки значительно реже, а тут минимум две в 20 строчках.

[n1kka]

Есть бага, если в цифре сделать пробел, т.е. не дорисовать один квадратик, то картинки по разному будут определяться, вот примеры:

[NecroHill]

это не баг, это фича.
хватит цыфири уродовать )

[n1kka]

моя третья картинка, где 9 определилась как 0 тоже фича? :)

[n1kka]

Причем «девять» нарисована почти идеально (:

[AgentSmith]

Хватит уже придираться!
Надо радоваться тому, что такой простой алгоритм справляется с такой сложной задачей, как распознавание символов, пусть даже в таком частном исполнении.
Для множества задач этого хватит за глаза.

[Akr0n]

=)) Дело в том, что нужно обязательно замыкать 9, 6, 0 и 8. Причем даже отдельный пиксель уже считается отдельной замкнутой областью. Ну не делал я к алгоритму антивандальных примочек… каюсь…

[n1kka]

Моя третья картинка замкнута :) Видимо он «ушко» девятки путает с нулем…

[Akr0n]

Ушки он не ищет. Просто по идее ушко должно как можно меньше попадать в нижнюю половинку рисунка. Желательно вообще не попадать)

[psylostlife]

<цитата написал=«автор»>Вообще имеются в виду только рукописные цифры.</цитата>

А по поводу девяток — нормально написаны, я не знаю что нужно быть за роботом, чтобы идеально, пиксель в пиксель писать под шаблон компьютерного шрифта :)

[psylostlife]

Поигравшись с программой в итоге сделал для себя вывод, что использование для рукописного текста врятли представляется возможным — программа заточена под один «шрифт» и к тому же почерк ловит только каллиграфический.

А задумка интересная. Желаю автору развить её дальше.

[SkyLine]

Поддерживаю. У нас в вузе например стало модным последнее время в качестве курсовых по программированию делать разные сайты, которые похожи один на один как две капли воды, и не представляют никакого интереса как в плане теоретическом, так и практическом. Ни для студента, ни для преподавателя. Сабж же — пример пусть и не на 100%, но успешной работы, к которой была приложена не только рука, но и голова. При желании ее можно развить в собственный движок распознавания образов. Кстати сравнение с образцом можно тоже добавить для случаев, когда статистика не однозначна.

[fabela_arbaro]

Напомнило метод, совмещающий попиксельное сравнение и разбиение по областям. Имхо даёт результат лучше, даже для рукописного текста aimatrix.nm.ru/aimatrix/SimpleOCRAlgorithm.htm

[pda1983]

>>Метод может показаться слишком тупым, и тем не менее он работает! Если не стоит задачи обмануть алгоритм, процент верных распознаваний очень высок.
Почему же тупой? Нормальный метод, хотя и требует некоторой доработки. А вот заявление про высокий процент распознаваний слишком оптимистичное :)
На сколько я могу судить, метод считает, что контур не замкнут, даже если разрыв в 1-2 точки, в результате вырастает процент ошибок.
Сам писал в студенческие годы нечто похожее.
За следующими дополнениями:
1) изображение «нормировалось», т.е. приводились к единому размеру и пропорциям
2) контуры замыкались, если разрыв в них мал относительно длины контура
3) статистика бралась не по четвертям, а по половинкам (верхней и нижней), четверти пробовал, но у меня как-то с ними хуже работало.

[RazB0YniK]

Попробовал попробовал. =)
Мою девятку он тоже далеко не с первого раза понял.

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

[vyacheslav84]

[Akr0n]

Еще можно так :)

[Vanger13]

Можно править описание — три замкнутые области — это «2» :)

[Akr0n]

Три замкнутые области — это ":)"

[abyrvalg]

Просто это не результат распознавания, а оценка вашего художества :)

[bagyr]

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

[Vanger13]

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

[bagyr]

Я имел ввиду какую-то обратную связь (какую — неважно, можно и простую, что-то вроде MSE, например) чтобы автоматически корректировать эту таблицу, да и на других наборах символов кроме [0-9] погонять было бы интересно.
Алгоритм хорош придельной наглядностью, но без математики не взлетит.

[ilesik]

Я когда-то реализовывал похожий алгоритм.
Ко всем параметрам определения можно добавить еще несколько:
1) количество прямых и их длительность. явно отделяет 1, 7, 5 от всего остального
2) количество и длинна «полукругов» (не замкнутых) — 2, 3, 5 от всего остального
3) количество соприкосновений с границей четверти. тоже очень четко отделяет 8, 6, 9, 0 от 1, 7,
4) количество несвязанных «кусков» в четверти. явно видно что у 2-ки в 3-й четверти их 2

… еще там с 5 шут было не помню уже, и работало достаточно неплохо.

[shattl]

Yep!


p.s. Дадите исходники-то? Для исследовательских целей only.

[Error_403_Forbidden]

видимо, деление на 0
y2 — y1 = 0

[Kotofot]

:)

[Kotofot]

капризный тег попался…
gyazo.com/e5f1322c4764740f7c419e2e702d42bb.png

[GamePad64]

Про такой алгоритм известно очень давно. Для winmobile даже есть программа рукописного ввода на нём основанная:
softsearch.ru/programs/249-679-esperanto-download.shtml
Отличия: панель ввода делится на 9 зон и есть возможность определять буквы (с самообучением естессно).