Comments 59
так кем разработан этот таинственный алгоритм? и чем он принципиально отличается от конкурентов? и к чему список литературы? а вообще статья доходчивая, спасибо
общая концепция алгоритма разработана мной совместно с моим коллегой в рамках государственного заказа «разработка системы OCR в открытых кодах». Принципиальные отличия — использование теории нечеткости вместо теории вероятностей, что позволяет улучшить качество распознавания. Теория вероятности, которая служит зачастую основой для таких систем с нейронными сетями не может быть применена хотя бы из за банального несоответствия требованию ТВ о сумме вероятностей=1. Сегментация на последнем этапе, отсутствие конечной сегментации по символам, вместо нее — границы разбиения с уровнем возможности. Распознавание типа написания, размера шрифта с использованием метода вычисления прироста энтропии, простого вычисления энтропии. Автоматизированный поиск наиболее эффективных признаков, не из эвристических соображений, а методом ген. оптимизации и кластеризации, что позволяет существенно улучшить результаты распознавания и сделать систему инвариантной к шуму, сдвигам и прочим нежелательным последствиям. Спасибо.
И чем полезна эта статья? Описаны этапы распознавания сканированного текста и никакой конкретики.
Что много в последние время на Хабре студентов со своими дипломными работами.
Что много в последние время на Хабре студентов со своими дипломными работами.
Статья без кусочка PHP-кода уже не подходит?
На самом деле дипломные работы не должны заслуживать такого пренебрежительного отношения. В нормальной системе образования дипломная работа представляет собой более-менее серьёзный исследовательский проект.
На диплом для специалиста/магистра пойдет. А для кандидата/PhD слабовато
Занимался как-то распознаванием текста, подача пикселей на вход нейросети — не самая лучшая затея, поскольку входы нейросети должны быть инвариантны относительно сдвига, толщины и любых других параметров, которые могут изменяться. Нейросеть — это большая штука, тупо для апроксимации функции многих переменных(в вашем случае набора яркости пикселей). И, например, если у вас нечетко центрируется буква, то нейросеть будет воспринимать одну букву, поданую на вход несколько раз с изменением некоторых параметров как серое пятно.
В классическом распознавании текста используются более четкие параметры, определяющие объект практически однозначно. Для буквы — это например количество пересечений по горизонтали, вертикали, количество «дыр» в букве, центр масс и т.д., зависит от фантазии. В таком случае вы сможете распознавать даже рукописный текст.
В классическом распознавании текста используются более четкие параметры, определяющие объект практически однозначно. Для буквы — это например количество пересечений по горизонтали, вертикали, количество «дыр» в букве, центр масс и т.д., зависит от фантазии. В таком случае вы сможете распознавать даже рукописный текст.
Что касается инвариантности, совершенно верно подмечено, только в том случае, если вы потом это не стремитесь использовать в своих целях. В данном алгоритме сегментация производится таким образом, что буква обрезается со всех сторон, потом масштабируется до входного размера окна. Далее для борьбы со сдвигами применяется считывание информации признаками, именно то что вы говорите только в терминах яркости пикселей, например усредненной яркости по некоторым областям. Области эти определяются не случайно, а методом генетической оптимизации с использованием кластеризации. Таким образом мы получаем наиболее эффективные признаки, те, что позволяют отделить одни буквы друг от друга, но инвариантны к сдвигам. Что касается размера шрифта, то тут такое различие нам на руку. Так как такие нейросети обученные на различные размеры шрифта объединяются в сложные классификаторы, которые с помощью вычисления энтропии на высоких уровнях позволяют узнать какой шрифт, какого размера, какого стиля написания перед нами. Это возможно ввиду особенностей масштабирования шрифтов различных размеров.
Я не в этой теме, но метод описанный Petrify выглядит более жизнеспособным. А как ваш метод будет работать если текст написан, к примеру, 4-я разными шрифтами один из которых авторский — помесь comic sans и monotype corsiva. В этом случае ваша нейронная сеть что будет делать?.. Где-то на Хабре была статья о разработке программы для некоего старого старого планшета, там разработчик(и) пришли к однозначному выводу, что гораздо эффективнее и менее затратно считать «палочки», пересечения, пустоты и т.п… Всем шрифтам и начертаниям не обучить…
Вообще говоря единственно верного решения в данной области быть не может. Если предположить, что такое решение есть, то всякие исследования и разработки становятся ненужными. Однако количество исследований в данной области зарубежными и нашими разработчиками поражает своими объемами. Если распознавать палочки и пересечения, то очень сложно и практически не возможно будет опознать шрифт, которым все это написано. Что касается авторских шрифтов, это действительно проблема, может быть решена динамическим, возможно интерактивным, обучением системы. На самом деле если дать какой-нибудь средненькой OCR шрифт своего дизайна, она вряд ли с ним справится, если шрифт является не похожим на те, что она знает. Да и стоит ли такие экзотичные шрифты знать OCR, тексты бумажные в основном содержат до десятка шрифтов. Ну по несколько разновидностей их написания. Не так уж много вариантов.
А как вы боритесь с переобучением нейронной сети, принимающей на вход сырые пиксели? Насколько я знаю подавляющее большинство распознавалок все же используют метрики.
На вход подается нормированное децентрированное значение яркости пиксела в градациях серого. Процесс переобучения отслеживается с помощью метода раннего останова. Что за метрики имеются ввиду?
Такие параметры изображения, как количество углов, изгибов, измерения толщины линии и прочее.
Тут тогда и деревом решений можно обойтись, только обобщение на неизвестных шрифтах будет никакое. А толщина линий может варьироваться от стиля написаний, она не показательна или от размера шрифта и не поймешь от чего. Так что отдельно использовать только такой способ я не вижу смысла, как дополнительный модуль, да, он имеет место.
ну, а где рабочий вариант?
Система как коробочный продукт не создана, находится в состоянии исследовательских приложений и алгоритмов, не пригодна для тестирования пользователем. Поэтому статья называется методы, а не реализация системы.
пффф
«система в исходных кодах» — скоро сможете выложить код?
Система как коробочный продукт пока не существует. И тестировать пока нечего, потому что все что сейчас имеется это набор программ, которые способны удовлетворить только исследовательские цели. Но никак не тестирование в открытом доступе. Поэтому говорить о сроках, когда будет доступно тестирование коробки очень рано.
Действительно, может ну его, список литературы-то, меленько ссылочки и ладно. А вот про таинственный алгоритм по-подробнее?
<...>для оценки эффективности выполнения НИР по теме «разработка алгоритма распознавания печатных кириллических символов»
Зачет-то хоть получили? :-)
на месте HR Abbyy я бы проверил достоверность приведенных здесь результатов работы некоего алгоритма, и, убедившись в достоверности, заинтересовал бы интересным предложением работы.
Abby тут даже читать нечего, потому что их система заставляет смотреть на нее с широко открытым ртом и удивляться как она так хорошо справляется с задачами различной сложности. Чего не скажешь об аналогах в открытых кодах, где есть над чем поработать.
Вы видимо еще не имели опыта проведения собеседований — сейчас найти просто адекватного заданной теме человека огромная проблема, не говоря уж о «с опытом» или «правильно образованного», причем даже в действительно хорошую и перспективную компанию с компенсациями выше среднего по рынку.
Просто вменяемых людей мало, поверьте. Поэтому и ценится это.
Просто вменяемых людей мало, поверьте. Поэтому и ценится это.
Большое спасибо за поддержку!
Да незачто, бросьте.
И, кстати, если действительно скромничаете и работа в конторе аля Abbyy была бы интересна — послушайте совета, оставьте стеснение с неуверенностью в себе и закиньте удочку, даже если открытые вакансии не впечатлили — все получится, хорошая работа часто на кончиках пальцев у правильных людей;)
И, кстати, если действительно скромничаете и работа в конторе аля Abbyy была бы интересна — послушайте совета, оставьте стеснение с неуверенностью в себе и закиньте удочку, даже если открытые вакансии не впечатлили — все получится, хорошая работа часто на кончиках пальцев у правильных людей;)
Хоть и не уполномочен говорить от имени компании, но присоединюсь к точке зрения cheldey.
;)
;)
Кто-нибудь может прояснить про продукт CuneiForm, когда-то попробовал, результаты были действительно, 50%, вообще ничего не распозналось. Должен же он в каких-то случаях работать?
Ну, сравнение с CuneiForm тут явно некорректное — он может быть просто не заточен на распознавание текста при разрешении 96 dpi или вы ему неправильно указали разрешение. Говорить, что в по результатам двух тестов у вас примерно в 2 раза больше правильно распознанных слов — это неприкрытая подтасовка. Ну можно тупо смаштабировать этот текст до размеров, которые ожидает на входе CuneiForm, и окажется, что он распознает не хуже, чем при разрешении 180 dpi. Скажем, для ABBYY FineReader заявлено, что оптимальным для него разрешением является 300 dpi, думаю, что для CuneiForm есть похожие требования. Просто ABBYY FineReader программа коммерческая и должна работать хорошо всегда. Поэтому она поступает интеллектуально, и в случае, если изображение имеет явно недостаточное или неверное значение разрешения, просто подбирает оптимальный масштаб для распознавания сама.
Что касается полученных результатов, то для диплома они, наверное, вполне неплохие, но о том, чтобы конкурировать хотя бы с CuneiForm, тут не может быть и речи. Чтобы это стало понятно всем, я немного перепишу ваши результаты для разрешения 180 dpi.
FineReader — 0.0% ошибок
CuneiForm — 0.5% ошибок
Ваш алгоритм — 2.8% ошибок
Точность измерения тут порядка 0.2% (1 ошибка = 0.17%).
При этом FineReader и CuneiForm заточены под распознавание более-менее любых шрифтов, а вы тестировали свою программу примерно на той же базе, что и обучали (изменение dpi примерно в 2 раза при неизменной гарнитуре). Если вам подсунуть незнакомый шрифт, то результаты, скорее всего, будут сильно хуже (для FineReader и CuneiForm они тоже могут немного ухудшиться, т.к. на Arial и Times New Roman они, конечно, тоже настраивались, но они настроены не только на них, а ваш алгоритм — только на них).
В общем, выходит, что даже имея преимущества (в виде совпадения базы для настройки и для тестирования), вы по количеству ошибок в 5-6 раз проигрываете CuneiForm и примерно в 50 — FineReader. При этом даже наивный растровый эталон может дать здесь результат лучше вашего (это я на самом деле на обум говорю, и проводить эксперимент мне лень, но не вижу, почему бы в данном примере растровый эталон мог работать хуже).
Что касается полученных результатов, то для диплома они, наверное, вполне неплохие, но о том, чтобы конкурировать хотя бы с CuneiForm, тут не может быть и речи. Чтобы это стало понятно всем, я немного перепишу ваши результаты для разрешения 180 dpi.
FineReader — 0.0% ошибок
CuneiForm — 0.5% ошибок
Ваш алгоритм — 2.8% ошибок
Точность измерения тут порядка 0.2% (1 ошибка = 0.17%).
При этом FineReader и CuneiForm заточены под распознавание более-менее любых шрифтов, а вы тестировали свою программу примерно на той же базе, что и обучали (изменение dpi примерно в 2 раза при неизменной гарнитуре). Если вам подсунуть незнакомый шрифт, то результаты, скорее всего, будут сильно хуже (для FineReader и CuneiForm они тоже могут немного ухудшиться, т.к. на Arial и Times New Roman они, конечно, тоже настраивались, но они настроены не только на них, а ваш алгоритм — только на них).
В общем, выходит, что даже имея преимущества (в виде совпадения базы для настройки и для тестирования), вы по количеству ошибок в 5-6 раз проигрываете CuneiForm и примерно в 50 — FineReader. При этом даже наивный растровый эталон может дать здесь результат лучше вашего (это я на самом деле на обум говорю, и проводить эксперимент мне лень, но не вижу, почему бы в данном примере растровый эталон мог работать хуже).
Ну чтож вы в самом деле — это ж не коробка, а студенческое исследование.
Докучи еще и «точность» в десятых частях процента — ну стыдно жеж…
Докучи еще и «точность» в десятых частях процента — ну стыдно жеж…
Это не заявление о новой чудо системе, это предложение некоторых методов распознавания текста в комплексе. Я не говорю о том, что эта система лучше Cuneiform во всем, хотя бы потому что она еще не создана, лишь замечено что существуют такие случаи, когда система справляется с задачей лучше Cuneiform, а в остальных случаях может сравниться с ним по качеству. Речь идет не о коробочном продукте, а об алгоритмах, которые могут быть использованы в такой системе. Наивный растр быстро упирается в свой потолок на шрифтах, а данный подход позволяет очень хорошо масштабировать систему на большое число различных шрифтов с возможностью их распознавания. Ничто не мешает дообучить систему работать с другими наборами шрифтами. Использование многоуровневых классификаторов позволяет говорить о возможности масштабирования системы.
Ну, меня немного возмутило некоторое промежуточное подведение итогов, по которому этот алгоритм якобы примерно в 2 раза лучше CuneiForm. У случайного читателя могло сложится ложное впечатление о состоянии дел в индустрии распознавания. Немного смущает ещё и 100-процентный результат FineReader — это говорит о том, что база для тестирования выбрана плохо и не способна зарегистрировать ошибки даже там, где они в принципе есть (ну не бывает пока 100% качества на реальных документах, пока программа хуже человека работает и заметить это можно).
В остальном я против данного алгоритма ничего не имею, хотя статью читал по диагонали и о её полезности судить не возьмусь. Если этот подход лучше растрового эталона, то и тестировать её надо на таких примерах, где это будет видно. Важный недостаток растра — он не работает для незнакомых шрифтов. Этот алгоритм, на первый взгляд, тоже не должен, потому я про растр и написал. Создание системы распознавания, которая умеет обрабатывать произвольные, в т.ч. незнакомые гарнитуры — это задача гораздо более сложная, чем распознавание фиксированного набора гарнитур. Если данный алгоритм с этой задачей справляется, то это хорошее достижение и надо именно это и тестировать. Но приведённые результаты о таких возможностях алгоритма ничего сказать не могут.
В остальном я против данного алгоритма ничего не имею, хотя статью читал по диагонали и о её полезности судить не возьмусь. Если этот подход лучше растрового эталона, то и тестировать её надо на таких примерах, где это будет видно. Важный недостаток растра — он не работает для незнакомых шрифтов. Этот алгоритм, на первый взгляд, тоже не должен, потому я про растр и написал. Создание системы распознавания, которая умеет обрабатывать произвольные, в т.ч. незнакомые гарнитуры — это задача гораздо более сложная, чем распознавание фиксированного набора гарнитур. Если данный алгоритм с этой задачей справляется, то это хорошее достижение и надо именно это и тестировать. Но приведённые результаты о таких возможностях алгоритма ничего сказать не могут.
Может быть подвидение итогов в виде таблиц бросается в глаза, но потом следует словесное объяснение, что это не заслуга чудо-алгоритма, а вполне адекватная реакция на такую выборку. Что касается возможности распознавания неизвестных шрифтов, то данный подход позволяет говорить о неплохих возможностях в данном направлении. Нейронные сети при верно выбранной модели обладают хорошими свойствами к обобщению. А большое число экспертов-нейронных сетей с различными системами выбора позволяют еще больше расширить ее генерализационные способности.
было бы адекватно — указать те цифры что привел товарищ mkal.
Ну это не совсем верно в результат закладывать качество исходных материалов. Тогда система получается должна хорошо работать только на идеальном варианте, а на искаженном зашумленном, низкого разрешения она может работать плохо, потому что при таком соотнесении результатов все равно они имеют маленький вес в общей картинке.
1. Там нейросеть. На не очень хороших признаках. Растр лучше.
2. Посмотри на сегментатор. С этим не живут.
3. С Cuneiform ты прав, лажа написана.
Да и вообще точность измерения — не до десятых долей процента.
2. Посмотри на сегментатор. С этим не живут.
3. С Cuneiform ты прав, лажа написана.
Да и вообще точность измерения — не до десятых долей процента.
чёрт, смягчил выражение. Вобщем, признаки не просто «не очень хорошие»…
Это вы про какую систему? Я не совсем понял. Что не так с сегментатором?..
Про Вашу. Априорно сегментировать, доползая до слов — не очень живой механизм. И слова «Данная структура легко может быть расширена для поддержки других уровней разбиения, например колонок, таблиц.» вызывают большие сомнения.
Что касается первого замечания, оно очень интересное. Мы над такой возможностью не думали. Потому что то, что мы видели из наработок таких систем, обычно идут даже дальше и доползают до букв! Сегментация слов не представляет никакой трудности, слова легко отделяются друг от друга. Система на этом шаге не ошибается с высокой степенью возможности. Поправьте меня, если я не вижу проблемы.
Масштабируемость системы до уровня колонок и таблиц вопрос соотнесения уровней/ глубины узла в дереве и объекта на странице. Вот распознавание таблиц — это отдельная песня. Про которую не скажешь, что это легко масштабируется. А резать колонки в дерево сложности не представляет. Опять же буду рад любым замечаниям на близорукость и непредвидение подводных камней.
Масштабируемость системы до уровня колонок и таблиц вопрос соотнесения уровней/ глубины узла в дереве и объекта на странице. Вот распознавание таблиц — это отдельная песня. Про которую не скажешь, что это легко масштабируется. А резать колонки в дерево сложности не представляет. Опять же буду рад любым замечаниям на близорукость и непредвидение подводных камней.
Про слова:
1. Разрядка. Когда интервалы между буквами увеличены
2. Уменьшенные пробелы. Многие текстовые процессоры пробелы ужимают до невозможности.
Очень часто найти границу, начиная с которой цепочки символов следует считать разными словами довольно сложно. А бывает и просто невозможно.
Про колонки. Бывает, что межколоночное расстояние не сильно больше обыкновенного пробела. Не сказать, чтобы редко. И чтобы его поймать нужно собирать статистику от многих строк.
Не говоря уже о том, что несколько колонок от таблицы сложно отличить.
1. Разрядка. Когда интервалы между буквами увеличены
2. Уменьшенные пробелы. Многие текстовые процессоры пробелы ужимают до невозможности.
Очень часто найти границу, начиная с которой цепочки символов следует считать разными словами довольно сложно. А бывает и просто невозможно.
Про колонки. Бывает, что межколоночное расстояние не сильно больше обыкновенного пробела. Не сказать, чтобы редко. И чтобы его поймать нужно собирать статистику от многих строк.
Не говоря уже о том, что несколько колонок от таблицы сложно отличить.
Вообще говоря адекватно предположить такие трудности, но вопрос в том насколько они часто будут возникать в реальных условиях, чтобы алгоритм затачивать под них. Конечно, если речь не идет о каком-нибудь гиганте этой индустрии, когда многие другие проблемы решены и хотелось бы, чтобы и такой текст распознавался. Пока наше предположение в том, что такой текст достаточно редок, что им можно пренебречь.
«Гигант индустрии» не имеет права пренебрегать этими проблемами прежде всего потому, что для их решения надо будет пересматривать архитектуру. А частотность проблемы зависит от выборки документов. Скажем так, с некоторой вероятностью вы вообще никак не сможете обработать Самый Важный В Жизни Документ, для настройки на который было бы не жалко потратить 2-3 недели разработки.
Ну, я свое субъективное мнение об этом алгоритме решил не высказывать, ибо оно не на опыте основано. Мало ли, какие чудеса можно изобрести. Так что я старался обойтись более мягкими и по возможности объективными выражениями.
Вы считаете растр покажет результаты лучше, чем описанный алгоритм? А почему выбранные признаки, которые выбирались не случайно, а путем оптимизации внутренней/внешней энтропии, «не очень хорошие» по вашему мнению? Спасибо.
«Значение каждого признака является функцией от яркостей некоторого подмножества пикселей изображения»
Магия какая-то. Наивный растр намного более предсказуемый. Хотя, конечно, требует аккуратной бинаризации, это да.
Магия какая-то. Наивный растр намного более предсказуемый. Хотя, конечно, требует аккуратной бинаризации, это да.
Никакой магии. Совершенно. Некоторое подмножество на самом деле оказывается прямоугольной областью. Функция — например усреднение. Тогда, наделяя рецепторное поле множеством таких пересекабщихся областей, мы можем выделить признаки, которые схожи для одинаковых букв и наоборот являются различными для разных букв. Как мы это будем делать? Мы будем считать информативность/энтропию по отношению к одному классу и энтропию по отношению ко всем остальным классам/буквам для каждой такой области. Выберем те области, которые являются критичными по данному оптимизационному критерию и никакой магии — получим оптимальный набор признаков.
Может быть не по теме говорю, но…
Ещё классный способ распознавания текстов придумали создатели reCAPTCHA (студенты Университета Карнеги — Меллон). Кому интересно: www.google.com/recaptcha
Это между прочим не просто антиспамбот, но ещё и полезный для науки — 1 слово машина знает, а второе не знает, берёт его из древней книги и даёт пользователям на распознание.
Ещё классный способ распознавания текстов придумали создатели reCAPTCHA (студенты Университета Карнеги — Меллон). Кому интересно: www.google.com/recaptcha
Это между прочим не просто антиспамбот, но ещё и полезный для науки — 1 слово машина знает, а второе не знает, берёт его из древней книги и даёт пользователям на распознание.
Очень интересный подход. Я всегда думал, что это только антиспам. Там и статьи имеются научные, надо ознакомиться, спасибо.
habrahabr.ru/blogs/webdev/8877/ — здесь есть мини-описание на русском
Talk is cheap. Show me the code.
Мне кажется интересным будет создание свободных методик распознавания не столько печатного текста, а текста и образов вообще — например на снимках. Задача выделения тут будет гораздо сложнее и интереснее, а главное полезнее. Уже писали про переводчик для айфона, другие идеи использования тоже легка приходят в голову.
Картинки пропали, не могли бы перезалить?
Sign up to leave a comment.
Методы распознавания текстов