@torrie15 апр 2010 в 05:32

Распознаем текст, используя расстояние Хэмминга

6 мин

39K

Искусственный интеллект

+82

Комментарии 34

@Xternal 15 апр 2010 в 05:37

Не читал, но тема для меня актуальная. Позже. Плюсую :)

НЛО прилетело и опубликовало эту надпись здесь

@Darkened 15 апр 2010 в 07:03

О, спасибо, за топик про IT!
И что ни слова про гаджеты.

@impwx 15 апр 2010 в 07:17

Интересная статья, спасибо.

P.S. на предпоследнем скриншоте в верхнем левом углу надпись «Emo1» :D

@fleshy 15 апр 2010 в 09:40

эмо один и ему грустно

НЛО прилетело и опубликовало эту надпись здесь

@impwx 15 апр 2010 в 15:26

Спасибо, r'g!

НЛО прилетело и опубликовало эту надпись здесь

@rufus 19 апр 2010 в 16:18

Капитан Очевидность

@SerrNovik 15 апр 2010 в 07:17

А на сколько все это актуально? Уже давно считал эту проблему эффективно решенной и если нужна такая функциональность можно быстро найти уже реализованный кусок кода/библиотеку/детально расписанный алгоритм.

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

@RomanL 15 апр 2010 в 07:20

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

@YourDestiny 15 апр 2010 в 07:22

спасибо за статью, как раз начал искать информацию на эту тему :)

@hardex 15 апр 2010 в 07:25

Delphi и блок-схемы… узнаю первокурсника :/
а сама статья хорошая, спасибо

@torrie 15 апр 2010 в 07:33

Вопрос языка, как вопрос религии, каждому своё.
Блок-схема наглядно показывает суть алгоритма.
Перваков нынче под дотНет штампуют; ничего плохого в этом не вижу, как и ничего хорошего. Если честно, без разницы на чем писать.

@hardex 15 апр 2010 в 07:38

Просто такое ощущение, что схему рисовал Капитан собственной персоной

@DLag 15 апр 2010 в 08:57

Это говорит только о наглядности схемы.

@iwuvjhdva 15 апр 2010 в 09:06

Интересная статья около этой темы, часть ее посвящена различиям между языками программирования.
www.paulgraham.com/avg.html

НЛО прилетело и опубликовало эту надпись здесь

@mad8vad 15 апр 2010 в 11:25

А мы для микроконтроллеров на асме писали

НЛО прилетело и опубликовало эту надпись здесь

@navoshta 15 апр 2010 в 07:49

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

@lsdima 15 апр 2010 в 08:07

Но ведь этот алгоритм работает только с участием человека (нужно предварительно выделить границы объекта). Или я ошибаюсь?

@navoshta 15 апр 2010 в 08:13

Ну в общем-то да, на то он и интерактивный, только выделяются не границы, а «семена», т.е. какие-либо начальные пиксели на объекте и на фоне. Это можно сделать программно, указывая, к примеру, самые темные как начальные пиксели объекта, а самые светлые — как начальные фона.

@dimag0g 15 апр 2010 в 08:46

Вы не расстояние Хэмминга считаете, а что-то своё. В расстоянии Хэмминга никаких квадратов нет.

@dimag0g 15 апр 2010 в 09:09

И кстати, эта формула вообще ничего не даёт распознаванию. Для чёрно-белых картинок (суть двоичных n-мерных пространств) все расстояния изоморфны друг другу. Замените φ на 1/R или √(1/R), и результат распознавания не изменится.

@eng 15 апр 2010 в 09:19

Предположу, что в данном случае расстояние Хемминга = R. И это просто число различающихся пикселей. Чем их меньше, тем больше похожи два образца.

@dimag0g 15 апр 2010 в 09:36

Именно так, Вы не ошиблись. Только я пойму никак, Вы мне вопрос задаёте, возражаете, поддерживаете моё мнение, или Вы просто ответили на второй комментарий вместо первого?

@eng 15 апр 2010 в 09:54

Поддерживаю Ваше мнение.

@Levsha100 15 апр 2010 в 12:40

Жаль, что ничего нового для себя не нашел, но автору спасибо.
~~Писал подобный распознаватель еще в начале 10-го класса.~~

@varagian 15 апр 2010 в 15:45

Если тема Вам действительно интересна, то могу порекомендовать для изучения вот это:
ru.wikipedia.org/wiki/Байесовская_сеть_доверия

@AlexPet 15 апр 2010 в 19:13

Самая красивая теория (не факт что самая пригодная, но пять лет назад авторы веряли, что вероятность схожа с нейронными сетями) из того что видел — двухмерное динамическое программирование. Основано на (скрытых) марковских случайных полях ((H)MRF). Ознакомиться с ними можно хотя бы здесь.

@d9k 16 апр 2010 в 11:03

Delphi- «чем старее, тем лучше»?))

@Nevkontakte 16 апр 2010 в 17:18

В летней школе в прошлом году мы делали похожий проект.
Идея была аналогичная, только при этом еще на изображение накладывались несколько фильтров (которые можно было настраивать) для улучшения картинки и минимизации шумов-мусора.
Кроме того, для обработки сложных букв использовался такой подход:
1) Проходится вся страница, выделяются все буквы и части букв, распознаются. Символы-кандидаты на знаки препинания и точки над Ё и Й выделяются в отдельный список («плохие символы» в нашей тогдашней терминологии :-) ).
2) Потом они распределяются по строкам исходя из позиции на картинке.
3) Последовательно применяются пост-обработчики, которые пытаются найти и сшить соседние символы-части букв Ы и т. п.
4) Далее начинается обработка «плохих символов».
4.1) Просматриваются все символы, распознанные как И и Е. Если рядом с ними оказываются точки и черточки в нужных количествах, то они превращаются в Й и Ё, а использованные «плохие символы» удаляются из списка.
4.2) Потом из оставшихся «плохих символов» конструируются сложные знаки препинания типа двоеточий и равенств и они распихиваются в места в соответствии с положением на картинке.
4.3) Оставшиеся плохие символы считаются самостоятельными знаками препинания и размещаются по строкам опять же согласно их положению на картинке.
5) Коррекция регистра — заглавные буквы в середине слова переводятся в строчные, строчные буквы, имеющие схожее начертание с их заглавными вариантами, перед которыми есть точка, вопросительный или восклицательный знак, переводятся в заглавные. При этом учитывается размер образа корректируемой буквы по сравнению с соседними.
6) Нереализованный, хоть и запланированный этап — спелл-чекер для пущего повышения праавильности распознавания.

@zeromodule 19 апр 2010 в 17:30

Спасибо за статью, но как буква "А" может кому-то напоминать пароходик?

Зарегистрируйтесь на Хабре, чтобы оставить комментарий