4.7. ОБЕСПЕЧЕНИЕ ДОСТОВЕРНОСТИ РЕЗУЛЬТАТОВ ЧТЕНИЯ

Автоматический ввод изображений с документов, выполненных вручную, предполагает применение мер, обеспечивающих помехозащищенность процесса. Очевидно, что создание процесса обработки изображения невозможно без серьезного изучения дефектов изображений и причин их возникновения. Многие авторы [20, 27] уделяют достаточно серьезное внимание этим

вопросам. Учитывая опыт разработки систем ввода документов в ЭВМ, все разнообразные варианты можно свести к следующим видам помех: топологические, метрические, топологический шум, фоновый шум.

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

Кратко охарактеризуем вышеназванные классы вариаций. Топологические помехи характеризуют индивидуальный стереотип начертания тех или иных элементов изображения человеком. Это наклон символов, характерный для данного исполнителя, набор элементов, из которых состоят символы, и способ сочленения в символе (рис. 4.29).

Рис. 4.29. Топологические вариации изображения: а — вариация набора элементов и их сочленений; б — вариация наклона

Рис. 4.30. Проявление топологического шума в изображениях символов

Метрические вариации объединяют изменения в начертании изображения по размерам символов, толщине линии, а также в их ориентации (повороты).

Топологический шум включает все, что называют разрывами линии, «недоводами» и «переводами», недопустимыми смыканиями фрагментов изображений (рис. 4.30).

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

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

Рис. 4.31. Классы вариаций в изображениях и причины, их вызывающие

Эти причины зачастую, по-разному сочетаясь, вызывают все многообразие вариаций в изображениях. На рис. 4.31 представлены причинно-следственные связи вариативности изображений. В связи с тем, что в значительной мере на практике причины вариативности изображений неустранимы, необходимо развивать процессы обработки, устойчивые по отношению к вариативности. Следует отметить, что меры борьбы с фоновым шумом в достаточной мере исследованы [20]. Менее изученными являются топологические вариации, и особенно топологический шум. Начнем с топологического шума и рассмотрим разрывы в символах.

Разделим множество всех разрывов линий в изображениях символов на два класса. В А-класс включим разрывы, не нарушающие связность фрагмента соответствующего символа, а в 5-класс — разрывы, нарушающие связность. Примеры изображений, содержащих А-разрывы, показаны на рис. 4.32, а содержащих Б-разрывы — на рис. 4.33-

Рис. 4.32. Разрывы А-класса

Рис. 4.33. Разрывы В-класса

Разрывы А-класса встречаются лишь в символах, где изображение включает контурную лйнию как фрагмент. Примером подобных символов являются А, Б, В, Д, О, Р. Не всякий разрыв в таких символах относится к A-классу (сравним изображение буквы Б на рис. 4.33 и 4.32). Для того чтобы разрыв принадлежал к А-классу, необходимо, чтобы он разрывал ту часть линии фрагмента, которая входит в его контурную часть (рис. 4.32). Нарушение этого условия делает разрыв принадлежащим к В-классу (рис. 4.33). Именно по этой причине любое нарушение связности линии в символах, не содержащих контуров, относится к В-классу (рис. 4.32, буква Г).

Борьба с помехами А-класса заставляет нас предпринять специальные меры, обеспечивающие успех на этапе распознавания. При ликвидации помех В-класса меры принимаются на этапе отделения символов.

Рассмотрим случай А-разрывов. Любая помеха этого класса вносит изменение в ПФ описания символа. Если сравнивать описание символа без разрыва с описанием того же символа с разрывом (ограничимся рассмотрением случая с одним разрывом), то отличие будет состоять в том, что в первом описании число граничных контуров будет на один больше, чем у второго. Дело в том, что Л-разрыв объединяет две изолированные границы в одну. Таким образом, описание символа существенно изменяется, а это приводит к тому, что либо мы должны быть готовы к отказу от распознавания в случае А-разрыва, либо включить в таблицу эталонов такие описания, которые соответствуют символам с типичными А-разрывами, что может увеличивать общее число эталонов во много раз. Любое из названных последствий достаточно неприятно, поэтому рассмотрим, каким образом можно выявлять А-разрывы и ликвидировать их.

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

Такое определение заключает в себе отыскание областей изображения, которые могут быть местами разрыва. Если разрыв обнаружен по признаку близости пары углов то его ликвидация вполне аналогична операции разделения контура на два, осуществляемая при решении задачи разделения контура на элементарные отрезки (см. § 4.4). Рисунок 4.34 иллюстрирует эту процедуру.

Если выявлен разрыв по признаку близости угла контура отрезку прямой, опирающемуся на пару элементов то ликвидация разрыва начинается с включения в ГК дополнительного угла а, между элементами Элемент должен размещаться на отрезке, соединяющем центры углов значение равно 180°, а расстояние меньше Д). После явного включения а, в ситуация сведена к близости углов Рисунок 4.35 иллюстрирует процедуру ликвидации А-разрыва для рассмотренной ситуации.

Рис. 4.34. Ликвидация разрыва по признаку близости пары углов

Рис. 4.35. Ликвидация разрыва по признаку близости угла к отрезку прямой

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

где — минимальное значение для множества точек, являющихся центрами угловых элементов, входящих в контур g; отношение означает, что некоторая дуга контура охватывает некоторую часть контура (рис. 4.36).

Рис. 4.36. Отношение охвата: а — охват имеется; б — охват отсутствует

Рис. 4.37. Символы с разрывами В-класса

При обнаружении отношений 1), 2), 3) (рис. 4.37) обследованию следует подвергать не все пары граничных контуров, а лишь ближайшие. Информацию о контурах, являющихся ближайшими соседями, можно получать в процессе построения ПФ.

Отношения 1), 2), 3) не выявляют все разрывы -класса (рис. 4.38). Для обнаружения таких дефектов необходимо граничные контуры символьного типа, соседствующие по строке, подвергнуть испытанию на предельные габаритные соотношения. Для этого в объединенном множестве угловых элементов пары контуров отыскиваются максимальные и минимальные значения их координат Если где — предельные габариты, установленные для символа, результат проверки положителен, т. е. пара контуров может относиться к одному символу. Отметим, что проверка на предельные габариты необходима при выявлении отношений 1), 2), 3) между парой контуров.

Рис. 4.38. Символы с разрывами В-класса

Дальнейший процесс предполагает для найденной группы ГК, рассматриваемых нами в качестве фрагментов одного и того же символа, организовать поиск места разрыва. Для рассматриваемой ситуации определение разрыва отличается от предложенного выше для А-класса лишь тем, что принадлежат различным контурам (первый случай) или принадлежит одному контуру, — другому (второй случай).

Ликвидация самого разрыва сводится к процессу объединения двух контуров в один в области пары углов а, (первый случай) либо пары а, (второй). Операция А объединения контуров в области пары порождающая результирующий контур g, рассмотрена в § 4.4.

Результат любой процедуры ликвидации разрыва при применении автоматической процедуры его обнаружения должен проверяться обращением к распознавателю. Успех в распознавании символа подкрепляет правильность гипотезы об обнаруженном разрыве. Тем не менее, целесообразно и при успешном распознавании формировать сообщение оператору о символах на документе, в которых был ликвидирован разрыв.

Остановимся на проблеме борьбы с ложными примыканиями — разновидностью топологического шума. Ложное примыкание символов следует разделить на два типа: примыкание символьного и несимвольного фрагментов, примыкание двух либо более символов. Начнем с выявления ложного примыкания символа к несимвольной части изображения.

Обнаружение такого типа дефекта в изображении строится на определении понятия символа при его отделении (см. § 4.4) и на предположении, что вероятность ложного примыкания в двух и более местах для одного символа ничтожно мала. Тогда обнаружение

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

Само разделение исходного граничного контура g на два контура, один из которых символьный, осуществляется операцией Рисунок 4.39 иллюстрирует отделение оимвола от несимвольного фрагмента.

Рис. 4.39. Отделение символа от иесимвольного фрагмента: а — исходный фрагмент, б — фрагмент после отделения

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

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

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

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

Рис. 4 40. Макросимволы, образованные парой соседних символов при их ложном примыкании в одной точке

Рис. 4.41. Макросимволы, образованные парой соседних символов при их ложном примыкании в двух точках

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

Рис. 4.42. Ситуация маловероятного сопряжения двух фрагментов в точке ложного примыкания

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

Рис. 4 44. Рассечение макросимвола, показанного на рис. 4.43, на два фрагмента

Следовательно, если в макросимволе отыскивать области ложного примыкания, удовлетворяющие сформулированным выше требованиям, то им в контуре ПФ макросимвола будут соответствовать пары угловых элементов, соседствующие через черную область. Например, для макросимвола (рис. 4.43) возможно всего пять сечений, удовлетворяющих такому принципу. Эти сечения образованы для всех пяти пар угловых элементов контура: 2—10,

2—4, 4—10, 5—9, 6—8. Число пар возможных сечений можно сократить, примяв во внимание, что интересующие нас сечения должны разделять фрагмент на левую часть и правую. Этому требованию не удовлетворяет пара 2—4. Результат разделения исходного макросимвола (рис. 4.43) на два фрагмента показан на рис. 4.44. Из рисунка видно, что такое разделение является неподходящим. Во избежание рассмотрения подобных пар, необходимо потребовать, чтобы сечение разделяло два элемента, один из которых должен заведомо относиться к контуру левого из символов макросимвола, а другой — к правому. В качестве такого сечения можно рассматривать элементы контура ПФ макросимвола с минимальным и максимальным значениями абсциссы. Для макросимвола на рис. 4.43 это элементы с номерами 7 и 11. Поскольку пара 2—4 не разделяет элементы 7, 10, то она должна быть исключена из рассмотрения. Таким образом, остаются сечения 2—10, 4—10, 5—9, 6—8. Соответствующие им фрагменты, получаемые при рассечении фрагмента макросимвола, показаны на рис. 4.45.

Рис. 4.45. Рассечение макросимвола, изображенного на рис. 4 43, на пары фрагментов

Для каждого из полученных фрагментов необходимо выполнить процедуру распознавания такого фрагмента как символа. Если результат успешен для каждого из них, то можно считать соответствующее рассечение удачным, приводящим к исключению ложного примыкания. Для примера, показанного на рис. 4.43, подходящим является сечение 5—9 (соответствующее рассечение приведено на рис. 4.45, в), а остальные сечения не подходят, поскольку попытка распознавания каждого из порождаемых при этом фрагментов (рис. 4.45, а, б, г) приводит к отказу.

Столь простой исход, полученный для рассмотренного макросимвола, возможен не всегда. Для иллюстрации этого утверждения рассмотрим изображение на рис. 4.46. Элементы 1 и 5 разделяют сечения 2—10, 3—9, 4—8. На рис. 4.47 показаны пары связных фрагментов, полученных из исходного изображения и соответствующие элементам описка допустимых сечений. Сечение 2—10 (рис. 4.47, а) является неподходящим, так как оба порождаемые им фрагмента не опознаются как символы. Сечение 3—9 порождает фрагменты изображений символов «Г» и «И» (рис. 4.47, а), а сечение 4—8 приводит к паре символов «П» и «Л» (рис. 4.47, в). Таким образом, в списке допустимых сечений несколько сечений могут оказаться подходящими. В такой ситуации выходом из положения

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

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

Рис. 4.47. Рассечение макросимвола, приведенного на рис. 4.46, на пары фрагментов

Рис. 4.48. Макросимвол, образованный за счет ложного примыкания двух символов и его рассечение, не нарушающее связности фрагмента а — макросимвол, б — макросимвол после рассечения его фрагмента

Рис. 4.49. Рассечение макросимвола, показанного на рис. 4.48, а на пары несвязных фрагментов

Существует еще одна возможность сокращения списка исходных сечений макросимвола, основанная на предположении о том, что ошибка касания двух символов может быть лишь в одном месте и, следовательно, ее можно ликвидировать одним сечением фрагмента. С учетом оказанного, из исходного описка следует удалить сечения, которые не нарушают связность исходного фрагмента. Примерами таких сечений являются: 5—20, 6—21, 7—22, 8—23, 9—24, 11—20 фрагмента на рис. 4.48, а. Для пары 5—20 результат рассечения исходного фрагмента показан на рис. 4.48, б. Перечисленные сечения, как не нарушающие связности исходного контура, не могут разделять никакие два элемента исходного контура и, следовательно, не должны включаться в исходный список. Легко заметить, что речь идет о сечениях, рассекающих участки замкнутых в кольцо линий. Формальным их признаком является

то, что они образованы парой элементов, входящих в различные контуры. В нашем примере ПФ состоит из двух контуров, один из которых содержит элементы с номерами от 1 до 12, а другой — от 20 до 24. Таким образом, в исходный описок следует включить лишь два сечения, разделяющие элементы 1 и 7: 2—12 и 3—11. Испытания для этой пары сечений (рис. 4.49) показывают, что сечение 3—11 подходит, так как порождает строку «ГР» (рис. 4.49,6), а сечение 2—12 не подходит (рис. 4.49, а).

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

Исходный список сечений, разделяющих элементы 1 и 9, имеет вид: 5—18, 7—14, 8—10, 8—12. Пары фрагментов, соответствующие этим сечениям, приведены на рис. 4.51: два первых не искажают смысла (рис. 4.51, а, б), а два последних являются неподходящими (рис. 4.51, в, г). Что касается первых двух, то для них необходимо продолжить исследования неопознанных фрагментов.

Рис. 4.50. Макросимвол, образованный за счет ложного примыкания трех символов

Рис. 4.51. Рассечение макросимвола, приведенного на рис 4 50, на пары несвязных фрагментов

На рис. 4.52 изображены неопознанные фрагменты, для которых тоже следует продолжить распознавание. Список для первого фрагмента (рис. 4.52, а), разделяющий элементы 40 и 9, имеет вид: 7—14, 8—10, 8—12. Соответствующие пары фрагментов, порожденные этими сечениями, показаны на рис. 4.53. Сечение 7—14 является подходящим и порождающим строку «ТК» Остальные сечения не подходят. Следовательно, исходный фрагмент (см. рис. 4.50) разделяется на символы, образующие строку «ОТК».

Список для фрагмента (см. рис. 4.52,б), разделяющий элементы 2 и 41, состоит из одного элемента: 5—18. Испытание этого сечения дает ответ, что оно подходит и порождает строку символов «ОТ». Таким образом, и в этом случае приходим к выводу, что исходный фрагмент порождает строку символов «ОТК».

Рис. 4 52. Макросимволы, полученные в результате отделения символа от макросимвола на рис. 4 50: а - правый макросимвол, б — левый макросимвол

Рисунок 4.54 показывает дерево вариантов для рассмотренного макросимвола.

Рис. 4.53. Рассечение макросимвола, показанного на рис. 4.52, а, на пары несвязных фрагментов

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

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

к увеличению числа эталонов для одного и того же символа в таблице эталонов распознавания.

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

Рис. 4.54. Дерево перебора вариантов рассечения макросимвола на рис 4 50

Рис. 4.55. Допустимые изо бражения символа

Пусть эталон представляет собой описание символа в полигональной форме, которое дополнено параметрическим описанием, т. е. каждому элементу ГК полигональной формы сопоставлен диапазон допустимых значений параметров. Хотя каждому угловому элементу можно сопоставить набор параметров, ограничимся одним углом элемента ГК. Задавая минимальное и максимальное значения углов в эталоне, обеспечиваем тем самым топологическую вариативность. Пусть, например, для буквы «Г» эталонное описание имеет вид: Такому описанию удовлетворяет целый класс изображений символа «Г», отличающихся друг от друга наклоном отрезков прямых, из которых составлен символ Примеры допустимых изображений для символа «Г», удовлетворяющих эталонному описанию, приведенному выше, содержатся на рис 4 55

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