Распознавание текста в ABBYY FineReader (1/2)

    Содержание
    imageРаспознавание текста в ABBYY FineReader (1/2)
    imageРаспознавание текста в ABBYY FineReader (2/2)

    Систему распознавания текста в FineReader можно описать очень просто.

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



    Выглядит очень просто, но дьявол, как обычно, кроется в деталях.

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



    В этой статье мы начнём рассказ про распознавание текста от уровня строки и ниже.

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

    Граф линейного деления


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

    Так вот, пусть есть черно-белое изображение строки текста. Нужно его поделить на слова, а слова — на символы для распознавания. Базовая идея, как обычно, очевидна – ищем на изображении строки вертикальные белые просветы, а дальше кластеризуем их по ширине: широкие просветы – это пробелы между словами, узкие – между символами.



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



    Решений у проблемы, в общем, два. Решение первое – считать некую «видимую» ширину просветов. Человек может практически любой текст, даже на незнакомом языке, точно поделить на слова, а слова — на символы. Это происходит потому, что мозг фиксирует не вертикальное расстояние между символами, а некий видимый объем пустого пространства между ними. Решение хорошее, мы его, конечно, используем, только работает оно не всегда. К примеру, текст может быть повреждён при сканировании и некоторые нужные просветы могут уменьшиться или, наоборот, сильно увеличиться.

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





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

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

    Для каждой дуги в графе нужно определить её качество. Если мы работаем с графом линейного деления слова на символы, то каждая дуга у нас – это символ. В роли качества дуги мы используем уверенность распознавания символа (как её посчитать — поговорим позднее). А если работаем с ГЛД на уровне строки, то каждая дуга этого ГЛД – вариант распознавания слова, который в свою очередь был получен из символьного графа. То есть нам нужно уметь оценивать общее качество полного пути в графе линейного деления.

    Качество полного пути в графе мы будем определять как сумму качества всех дуг МИНУС штраф за весь вариант. Почему именно минус? Это дает нам возможность быстро оценить максимально возможное качество варианта пути по сумме качества дуг этого пути, а это значит, что большинство вариантов мы будем отсекать еще до подсчета общего качества варианта.

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

    Гипотезы изображения


    Прежде чем мы спустимся на уровень распознавания отдельных слов, у нас есть еще одна тема, которая не обсуждалась, – гипотезы изображения фрагмента.

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

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

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



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

    В результате обработка гипотез выглядит так:

    1. По изображению сгенерировать наиболее подходящую гипотезу.
    2. Исправить искажения от выбранной гипотезы.
    3. Распознать полученное изображение.
    4. Оценить качество распознавания.
    5. Если качество распознавания улучшилось, то оценить, нужно ли применять новые гипотезы к измененному изображению.
    6. Если качество ухудшилось, то вернуться к исходному изображению и попробовать применить к нему какую-либо другую гипотезу.








    На изображениях показано последовательное применение гипотез белого шума и сжатого текста.

    Оценка качества слова


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

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

    Чуть раньше мы говорили, что любые оценки за слово целиком должны быть отрицательными, чтобы у нас нормально работал перебор по ГЛД. Сейчас нам это начнет активно мешать, поэтому давайте зафиксируем, что у нас есть некая заранее определенная максимальная положительная оценка слова, слову мы даем положительные бонусы, а финальный отрицательный штраф определяем как разность набранных бонусов и максимальной оценки.

    Ок, пусть мы распознаём фразу «Вася прилетает рейсом SU106 в 23.55 20/07/2015». Мы, конечно, можем оценивать здесь качество каждого слова по общим правилам, но это будет достаточно странно. Скажем, и SU106 и Вася вполне понятные в данной строке слова, но очевидно, что правила образования у них разные и, по идее, верификация тоже должна быть разной

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

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





    Из самой постановки задачи формируются наши требования к архитектуре модели. Модель должна уметь:

    • Быстро сказать, подходит или нет для нее вариант слова. Стандартная проверка включает все проверки разрешенных наборов символов для каждой буквы в слове. Скажем, в словарном слове пунктуация должна быть только в начале или в конце, а в середине слова набор пунктуации сильно ограничен, и сочетание пунктуации сильно ограничено (супер-способность?!), а в модели числа в основном должны быть цифры, кроме разрешенного в данном языке символьного суффикса (10-ое, 10th).
    • Уметь по своей внутренней логике оценить качество распознаваемого слова. К примеру, слово из словаря должно явно оцениваться выше, чем просто набор символов.


    При оценке качества модели не стоит забывать, что наша задача в итоге – сравнивать модели между собой, поэтому их оценки должны быть согласованы. Более-менее нормальный способ этого добиться – это относиться к оценке модели как к оценке вероятности построить слово по данной модели. Скажем, словарных слов в обычном языке достаточно много, и получить словарное слово при неправильном распознавании несложно. А вот собрать нормальный, подходящий под все правила телефонный номер уже гораздо сложнее.

    В итоге при распознавании некоторого фрагмента строки у нас получается примерно такая схема:



    Отдельным пунктом при оценке вариантов распознавания идут дополнительные эмпирические штрафы, не вписывающиеся ни в концепцию моделей, ни в оценку распознавания. Скажем, «ООО Рога и копыта» и «000 Рога и копыта» выглядят как два одинаково нормальных варианта (особенно если в шрифте 0 (ноль) и О (буква О) слабо отличаются пропорциями). Но при этом достаточно очевидно, какой вариант распознавания должен быть правильным. Для таких небольших конкретных знаний о мире сделана отдельная система правил, которая может дополнительно штрафовать не понравившиеся ей варианты после оценок моделей.

    Про само распознавание поговорим уже в следующей части этого поста. Подписывайтесь на блог компании, чтобы не пропустить :)
    ABBYY
    121,00
    Решения для интеллектуальной обработки информации
    Поделиться публикацией

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

      +4
      про граф интересно вы придумали, для поиска пробелов; я вот к этой проблеме подходил с другой стороны, от машинного обучения, для начала взял статистики n-грам и нагенерил большое количество строк, используя марковскую генерацию, получил кучу строк статистически валидных в языковой модели, разной длины, стиля, шрифта и размера. затем для каждой тройки символ_межсимвольноеРастояние_символ вычислил ряд фич и одно наблюдение у меня было эти фичи и различные статистики строки, которые использовались для нормализации фич, дабы получить какую то инвариантность относительно размера. потом нагенерил для каждого наблюдения некоторые совместные фичи от базовых фич. и в обучил несколько деревьев решений на разных метриках, и выбрал лучшее, оказалось что существует одна комплексная фича и порог для нее, такой что именно отсеивания по порогу было достаточно что бы классифицировать правильно 99.9% тестовой выборки.

      получалось что то в этом роде
      image


      но там как видите есть другая проблема — это склейки символов, было бы интересно почитать как вы разделяете символы которые образуют одну связную компоненты
        +3
        Коллега 57Ded в общем все правильно ответил — для склеек мы смотрим горизонтальный профиль фрагмента и находим на нем подозрительные точки локальных минимумов. Для каждой возможно точки порезки мы еще ищем путь порезки — сверху до низу с минимальным разрезанием черного и без сильных скачков. И все такие точки порезки добавляются в ГЛД как отдельные вершины.
        Ну и два дополнительных очень полезных чита:
        1. Некоторые пары символов лучше распознавать сразу целиком как один символ без порезки. Потому что в типографиях они печатаются вместе (это то, что называется лигатурами) — fi, fl, ft, ...
        2. Для некоторых символов уже на этапе формирования варианта распознавания слова стоит сгенерить вариант, как если бы в букве была незамеченная порезка. Скажем, если видим букву «m» — стоить проверить варианты распознавания с «r»+«n»

          +3
          Кстати — идея нагенерить с помощью Марковских цепей примеров для машинного обучения очень крутая. Мы используем отдельные классификаторы, чтобы подтвержать линии порезки между некоторыми парами символов. Но количество пар ограничено — просто потому что в нормальных текстах количество встречающихся пар сильно меньше возможно и распределено очень неравномерно — поэтому приходится обходится только совсем частыми парами для обучения.
          +2
          Пока автор молчит, попробую ответить частично.
          Посмотрите на пятую сверху иллюстрацию, с ГЛД для слов PREFACE и Cambridge. Синие вертикальные черточки под текстом — это гипотезы вершин символьного ГЛД, соответствующие возможным местам порезки склеенных букв. Эти гипотезы выдвинули, исследуя проекцию слова на горизонтальную ось (сама проекция нарисована как раз под этими черточками). Какие из вершин выберут в итоге, описано сразу после иллюстраций в посте.
            –17
            Для описания алгоритмов лучше всего проходит исходный код. Не виде в посте ссылки на репозиторий. Плохо.
              +16
              Я бы выложил исходный код, но он:
              1. Закрыт. Хорошо это или плохо — тема для длинного и скучного холивара, но на данный момент это такой факт.
              2. Чтобы в нашем коде разобраться и понять что же там за алгоритмы в основе используются нужно много бессонных ночей. У меня эти ночи были — поверьте словесное описание иногда бывает сильно проще и понятнее.

              Но вообще спасибо за замечание — может быть в других статьях я попробую сложные вещи хотя бы псевдокодом описывать (помимо текста), для удобства восприятия.
                –5
                Тогда не обижайтесь на шпыняние за закрытые исходники.
                +3
                Если бы тебе приходилось видеть и разбираться в сложных проектах, где алгоритм не очевиден и сильно зависит от разных многих внешних параметров, которые ещё надо как-то добыть, то ты бы так не говорил.
                Словесное описание практически всегда проще, чем исходный код.
                  +1
                  Сегодня сдавал в универе лабу по поиску пути на графе. Так уболтал препода, вырисовывая на бумажке свой алгоритм, что даже забыл показать код, так поставил оценку. Так что описание всегда интереснее и занимательнее, чем сам код.
                    0
                    > Так уболтал препода, вырисовывая на бумажке свой алгоритм, что даже забыл показать код.
                    Ждём с нетерпением компилятор от ABBYY
                      0
                      А это идея!
                      Семантический анализатор у нас уже (ABBYY Compreno). До компилятора осталась всего ничего.
              • НЛО прилетело и опубликовало эту надпись здесь
                  0
                  Если текст в строке написан разным шрифтом, то у нас есть специальный механизм, который пытается такие строки поделить на части с одинаковым размером шрифта — еще до разбиения строки на слова. Но даже если этот алгоритм не сработал, то особой проблемы не будет — большинство методов дальше все равно закладываются что какие-то символы могут больше или меньше, чем средняя высота символов в слове.
                  +8
                  image

                  Забавляют такие скриншоты в статьях.

                  1. Проверка орфографии отключается.
                  2. Проверка орфографии иногда бывает права...
                    –4
                    Не отключается, просто встретился не основной язык.
                      +1
                      Мой фэйл. Поправлено.

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

                    Самое читаемое