Comments 18
Такой же алгоритм можно эффективно использовать в системах голосового распознавания, только нет необходимости разбивать символы. Достаточно сравнивать распознанные и эталонные строки. Например, для IVR с заранее известными именами и фамилиями сотрудников.
В целом, для Левенштейна ещё полезно сравнивать найденную минимальную дельту с предельным значением допустимым (например, не более 4 расхождений от эталона) и выдавать ошибку в противном случае. Иначе система будет давать случайный результат на входное значение, не совпадающее с эталоном даже теоретически (на входе была цифра, а ожидали только буквы, например).
В целом, для Левенштейна ещё полезно сравнивать найденную минимальную дельту с предельным значением допустимым (например, не более 4 расхождений от эталона) и выдавать ошибку в противном случае. Иначе система будет давать случайный результат на входное значение, не совпадающее с эталоном даже теоретически (на входе была цифра, а ожидали только буквы, например).
Так как мы заранее знаем где у нас находится символ, вырезать определенную область не составит труда.А всегда ли так будет? Учитывая, что
входные данные в виде отсканированных изображений документовДокумент же можно криво положить, испачкать и пр. Я очень редко встречал, чтобы отсканированные документы были идеально выровнены. Обычно люди об этом не задумываются и сканируют как попало.
В итоге от небольшого поворота документа вся логика распознавания системы порушится, т.к. буква тоже изменит положение, её бинарная строка от этого сильно изменится и, соответственно, расстояние поползёт вверх относительно «правильного» эталона, что приведёт к ошибочному распознаванию, или нераспозанаванию вообще.
Надо быть очень уверенным в правильности локализации символа, чтобы пользоваться описанным методом.
Полностью согласен с Вашим утверждением, но в статье заведомо сделал допущение и упрощение задачи, чтобы акцентировать внимание на конкретику алгоритма.
Есть множество нюансов в каждой отдельной задаче, которые влияют на выбор инструментов и подходов к решению.
В нашем случае, к примеру, приходилось распознавать символы из документа, который формировался в другой системе в формате png (то есть не сканированный документ, а сформированный автоматически). Этот факт облегчал нам задачу поиска положения символов.
Спасибо
Есть множество нюансов в каждой отдельной задаче, которые влияют на выбор инструментов и подходов к решению.
В нашем случае, к примеру, приходилось распознавать символы из документа, который формировался в другой системе в формате png (то есть не сканированный документ, а сформированный автоматически). Этот факт облегчал нам задачу поиска положения символов.
Спасибо
Ну если это сформированный документ, то тогда всё хорошо. Знал бы об этом, не писал бы свой комментарий)
Вообще, в такой постановке задачи первым делом приходит на ум сумма абсолютной попиксельной разницы между интересующей частью изображения и заранее заготовленными шаблонами. Там, где она меньше всего (ещё лучше, если около ноля), тот вариант и выбрать. Получится чуть проще и оптимизированней.
Но с расстоянием Левенштейна подход интересный.
Вообще, в такой постановке задачи первым делом приходит на ум сумма абсолютной попиксельной разницы между интересующей частью изображения и заранее заготовленными шаблонами. Там, где она меньше всего (ещё лучше, если около ноля), тот вариант и выбрать. Получится чуть проще и оптимизированней.
Но с расстоянием Левенштейна подход интересный.
Типичные проблемы, насколько я понимаю — смешение +-1 пиксель для символа в «сетке распознавания». Ливенштейн для такого способа формирования «строки» и таких типичных проблем не подходит. Можно формировать строки в виде смещений, для простоты — построчно перенумеровав все ячейки сетки и выписывая смещения до следующей «черной» точки.
Для символа «минус», который в сетке занимает 2 строки в матрице 10x10 где-то в середине «сетки» получится что-то вроде `XXX, 1,1,1,1,1,4,1,1,1,1,1` — `XXX` — это начальная «черная» точка распознаваемого символа. При таком способе формирования строки — ливенштен будет достаточно адекватен.
Для символа «минус», который в сетке занимает 2 строки в матрице 10x10 где-то в середине «сетки» получится что-то вроде `XXX, 1,1,1,1,1,4,1,1,1,1,1` — `XXX` — это начальная «черная» точка распознаваемого символа. При таком способе формирования строки — ливенштен будет достаточно адекватен.
Если в Вашей задаче есть сложность в определении положения считываемых символов или другие проблемы типа качество, рукописность, разный масштаб символов, то, конечно, данный метод либо нужно серьезно доработать повышая эффективность и решая, в первую очередь, проблему смещения и качества символов, либо же смотреть в сторону других методов.
Применение данного метода сводится к эффективному решению узкой задачи, с более менее известными входными данными.
Спасибо
Применение данного метода сводится к эффективному решению узкой задачи, с более менее известными входными данными.
Спасибо
А можно поподробнее насчёт множества готовых библиотек? Я знаю только Tesseract и не сказал бы, что он крут (когда я его смотрел года 3-4 назад) он умел вытащить только голый текст, но не мог например распознать таблицу как таблицу (с сохранением структуры и пониманием, какой текст в какой ячейке сидит). Либо я не разобрался, как это сделать с его помощью.
Tesseract распознает текст, у него нету задачи как таковой распознавать объекты вроде таблицы, формулы и т.д.
А есть что-то Open Source, хотя бы отдаленно сопоставимое с Fine Reader? (с распознаваением текста как RTF, т.е. с картинками, таблицами, форматированием)
не встречал, только какие то платные продукты, которые к сожалению, не намного лучше распознают чем Open Source.
FineReader, как библиотека в своем базовом варианте тоже не очень умеет в таблицы. Мы писали свой алгоритм разбора таблица. С ячейками особой сложности не было, была сложность с многоуровневыми заголовками.
Зато есть копеечный Amazon Textract, который распознает типовые документы (типа визитных карточек, и всяких форм)
Не всегда возможно данные выгружать на какие-то облака для распознавания. Требуется локальное решение. Да и речь не о типовых формах, а о нормальных документах (текст+таблицы, каждый документ в среднем на 30 листов текста, самих документов сотни в день).
Он не очень-то копеечный (особенно в сравнении с Azure Form Recognizer).
Идея классная, только надо её проверять, искать контрпримеры
По сути вы получили что-то вроде 1-nn с метрикой вроде манхэттоновского расстояния. Возьмите несколько образцов / добавьте к образцам аугументацию — будет работать с слегка повёрнутыми/смазанными/повреждёнными изображениями. Зачем заморачиваться с расстоянием левенштейна, если можно взять более просто считающуюся метрику и получить тот же результат?
Статья про то, как криво написать свой template matching https://docs.opencv.org/master/d4/dc6/tutorial_py_template_matching.html
Sign up to leave a comment.
Распознавание символов методом наименьшего расстояния Левенштейна