Выделение и представление картинок на немонохромных изображениях.
Аннотация
Одной из вспомогательных задач, решаемых при распознавании символов, является выделение зон исходного изображения, без изменений переносимых в результат распознавания страницы. В статье изложено решение этой задачи в рамках общей схемы выделения и представления фонов. Процедура ориентирована прежде всего на обработку изображений в цветовой шкале со многими градациями. Однако она применима также к бинарным изображениям и к серым изображениям, полученным сглаживанием бинарных.
Картинки. Предварительное обсуждение
Для начала попытаемся разобраться с предметом. Статья посвящена картинкам. Картинка есть то, что человек воспринимает как картинку. Изъяном этого, на взгляд автора, превосходного определения является вовсе не кажущаяся неоперациональность. Напротив, последовательно операционализуя его, мы узнаем чрезвычайно много о восприятии и что-то о картинках. Изъян в том, что статья посвящена картинкам в распознавании символов. В таком контексте картинками лучше всего назвать то, что не поддается надежному распознаванию. Технические доуточнения, которые придется сделать, чтобы, например, отделить картинки от грязи (типа «картинка не может быть менее чем...», «картинка обладает неоднородностью в большом» и т. д.), всецело, но неявно опираются на первое определение. В действительности связь двух определений гораздо глубже – оба они определяют картинку через процесс восприятия, во втором случае довольно специфический, и ничего не говорят о – привносящих дополнительную путаницу в понимание предмета – способах представления картинок.
Как мы увидим, не существует соответствия между «картинками» (по первому определению) и представлением страницы в процессе и результате распознавания. Для внутреннего представления нетекстовых элементов достаточно фигур и растров, а картинка – с позиций внутреннего представления – оказывается избыточной и порой дорогостоящей сущностью. Например, на странице изображена картинка – черный и белый треугольники на прямоугольном красном фоне. При машинной обработке она будет представлена как три фигуры. В таком виде она попала бы в описание страницы. Однако, коль скоро это одна картинка, то для обеспечения последующей работы с ней как с единым целым придется представить ее в виде растра.
К сожалению, даже возможность идеальной автоматической реконструкции страницы не избавляет от необходимости насильственно устанавливать соответствие внутреннего представления и картинок, обусловленное не внутренне – компактностью представления или точностью воспроизведения, а сугубо внешне – участием человека либо в технологической цепочке распознавания, либо в (художественном) редактировании результатов распознавания.
Картинки vs фоны
Если способность системы распознавания различать картинки и символы необходима для качественного распознавания, то нужна ли ей способность различать картинки и фоны? Покажем, что различие картинок и фонов неверифицируемо, а бинарное деление «фон–картинка» недостаточно для представления объектов, включающих текст и графику.
Под фоном понимается в некотором смысле однородная область, содержащая объекты из алфавита распознавания – символы при распознавании символов, изображения самолетов, утюгов или мячей при распознавании образов. С картинкой, а точнее с разграничением картинки и фона, дело обстоит сложнее. Достаточно задаться вопросом, может ли картинка содержать распознаваемые (в обоих смыслах – и как подлежащие и как доступные распознаванию) символы, оставаясь при этом целостной картинкой, а не фоном. Репродукции, на которых изображен мальчик, пишущий «миру–мир», или лавка с вывеской «СЕЛЬПО», убеждают в возможности положительного ответа. В этом случае текст, существующий как часть картинки, не подлежит распознаванию. С другой стороны, скажем в рекламной практике, картинки часто используются в качестве фона для текста. В таком случае текст не является частью картинки и должен быть распознан, подвергнут лингвистической обработке (орфографическому исправлению, переводу на другой язык и т. д.) и восстановлен на фоне картинки с сохранением некоторых атрибутов, например, шрифта и цвета.
Но тогда где же граница между фоном и картинкой и если она есть, то чем определяется? В зависимости от контекста восприятия конкретного изображения, один и тот же текст может выступать и как неотъемлемая часть картинки и как текст на ее фоне. В свою очередь, и контекст восприятия одного и того же изображения различен для разных культур или эпох. Например, мадонна Рафаэля с помещенной поверху италоязычной рекламой памперсов воспринимается как фон для текста рекламы. Размещая ту же рекламу в русскоязычном издании, мы без колебаний дадим текст по-русски, оставив неизменным фон – мадонну. Теперь предположим, что Рафаэль вдруг оказался утрачен и стерт из памяти, зато археологи обнаружили картон с изображением мадонны и текстом о подгузниках. Безусловно, перед нами произведение искусства и оно воспринимается как целое. Однако, не допуская и мысли о замене «в теле изображения» итальянского текста на русский, мы заинтересуемся смыслом текста и не будем возражать против того, чтобы картинку сопровождал перевод.
Продолжая список изображений с текстом – иконы, лубки, карикатуры или полотна И. Кабакова, мы будем иметь дело с тремя интерпретациями изображения. В одном случае мы предпочтем рассматривать его как (1) текст на фоне картинки, в другом – как (2) целостный объект, который должен быть сохранен без изменений и без распознавания, и в третьем как (3) целостный объект, который должен быть сохранен без изменений, но сопровождаемый как сноской экстрагированным из него текстом. Замечательно, что не существует эффективных универсальных правил различения названных ситуаций. Тогда воспроизведение изображений при распознавании требует возможности при желании распознавать текст на изображении (случаи 1 и 3), сохранять изображение в неизменном виде (случаи 2 и 3) либо элиминируя из него распознанный текст (случай 1). В последнем случае необходимо уметь заполнять дыры в изображении, возникающие при удалении символов.
Восстановление и сохранение фона
Рассмотрим ситуацию «текст на фоне» – не важно, на фоне картинки или просто фоне. Пусть из фона каким-то образом уже выделены компоненты, часть из которых распознана как текст. После распознавания этот текст будет воспроизведен на том же фоне заново, но уже в отличном от исходного начертании и расположении. Строго говоря, желательно удалить из исходного изображения точки, принадлежащие не компонентам, по которым распознаны символы, а самим распознанным символам. Действительно, компоненты распознавания и точки символов на исходном изображении суть сильно пересекающиеся, но все же не совпадающие наборы, особенно если изображение не бинарно, отчего граничные точки символов могут оказаться отнесенными к фону, а не компонентам распознавания. Поэтому, удаляя распознанные компоненты мы, с одной стороны, оставим на изображении какие-то точки самих символов, а с другой – удалим лишние точки, ошибочно включенные в компоненты.
Однако ограничимся задачей интерполяции фона в точках, принадлежащих элиминируемым компонентам. Задача может решаться либо глобально, либо локально – по точкам фона, попадающим в достаточно узкую окрестность элиминированных компонент. Достоинства локального подхода – простота и скорость. Но если необходимо восстановить в пропусках такие регулярности как, например, текстура (неизбежно сопутствующим чему злом будет восстановление возникающих при цветной печати муаров), то необходимо прибегнуть к автокорреляционному анализу фона или его аналогу. Это исключит противоречия, свойственные локальному подходу. Так, если фон содержит вертикальные полоски, одну из которых частично перекрывает элиминированная компонента, то при горизонтальной локальной интреполяции полоска восстановлена не будет, при вертикальной – будет, при интерполяции по близости будут восстановлены размытые края полоски.
Но даже выбрав локальный подход, все равно придется определить одну глобальную цветовую (яркостную) характеристику – однородность фона «в большом», то есть определить, достаточно ли изохромны участки фона, зрительно воспринимаемые как имеющие размер, а не как одна точка. Необходимость этой характеристики объясняется используемыми формами представления фонов. Учитывая, что экспорт внутрисистемных представлений возможен в двух видах – аналитическом, при котором все точки задаваемой фигуры окрашиваются одним цветом, и растровом, для внутреннего представления информации о фонах избраны те же две структуры – фигура и растр. Фигура и растр – формы представления, «картинка» – феномен восприятия и никак не соотносятся друг с другом. Обе структуры (фигура и растр) могут представлять как фон, так и не-фон. Если фон анизохромен, он должен быть представлен в растровом виде. Поэтому обнаружив даже простейшую, но заметную цветовую неоднородность фона, например, линейное изменение от темно-зеленого слева к светло-зеленому справа, фон придется аппроксиморовать в дырах и сохранить в растровом виде. Обе структуры, фигура и растр, допускают привязку к ним вложенных данных – фигур, растров или текста и при наличии такой привязки считаются фоном, текстонесущий фон имеет особую маркировку.
Сборка растров и цветная фрагментация
Процедура выявления фонов (см. публикуемую в настоящем сборнике статью «Выделение, снятие и представление фонов») выделяет на изображении цветные/яркостные компоненты, части которых присваивается признак фона (в том числе текстонесущего), а остальные (не-фоны) называются простыми. По построению компоненты накрывают не все исходное изображение, между ними существуют зазоры. Фон может быть многокомпонентным и тогда всем его компонентам приписывается один идентификатор. Сборка многокомпонентного фона производится по геометрической и – в геометрически ближайших точках – цветовой близости компонент. И фоны и простые компоненты могут быть как изо-, так и анизохромными, на что указывает специальный признак.
Рассмотрим дерево вложенности компонент, в котором компонентам одного фона соответствует одна вершина. Дерево имеет фиктивный корень, которому присвоен признак изохромности (далее вершины с признаком изохромности будем называть изохромными, а с признаком анизохромности – анизохромными). Нужно сжать дерево так, чтобы объединить рассыпанные на компоненты куски картинок в единые картинки. Для этого последовательно пройдем ярусы дерева, начиная с предпоследнего (под которым, только нижний ярус) и кончая корнем. Обход яруса состоит в том, что для каждой расположенной на нем вершины-родителя берем все непосредственно подчиненные ей вершины, над которыми выполняем некоторые операции, затем переходим к следующей вершине-родителю, расположенной на том же ярусе, и т. д. Рассмотрим очередной шаг процедуры – выбраны все вершины, непосредственно подчиненные текущей вершине-родителю.
Сборка растров может выполняться до этапа распознавания (предварительная цветная фрагментация) и после распознавания (окончательная цветная фрагментация). Эти варианты специфичны для двух технологических цепочек обработки страницы – человеко-машинной и полностью автоматической. Начнем со сборки растров после распознавания. Это значит, что о фоне можно достаточно уверенно сказать, является ли он текстонесущим, а среди простых компонент выделить те, что образуют символы. Такие простые компоненты исключим из рассмотрения. Возникающие при элиминировании символов дыры в фонах к моменту окончательной сборки растров должны уже быть закрашены – явно (для анизохромных фонов) или неявно (для изохромных, для которых само задание цвета фона автоматически означает закраску дыр).
Если анизохромному родителю подчиняется анизохромная вершина, она выбрасывается, а висящее под ней поддерево подклеивается под родителя. Если анизохромному родителю подчинена изохромная вершина, содержащая в своем поддереве текстонесущий фон (в частности, сама являющаяся текстонесущим фоном), то подчиненная вершина сохраняется. Для подчиненных изохромных вершин, не содержащих таких поддеревьев, решение об отбрасывании или сохранении вершины зависит от сложности формы соответствующей вершине фигуры, числа таких вершин и заполненности ими фона-родителя. Решение принимается применительно ко всем таким вершинам – либо они все целиком устраняются, либо все сохраняются.
Если родитель изохромен, то подчиненные текстонесущие изохромные вершины сохраняются. Остальные подчиненные вершины разбиваются на группы смежных. Если родителем является не корень и родитель не охватывает (почти) всю страницу, а группы состоят из более чем одной вершины достаточно сложной формы, то все эти вершины устраняются, а родителю присваивается признак анизохромности. Если родитель является корнем или имеет размер близкий к странице, то группы, достаточно удаленные от других рассматриваются по отдельности. Если структура группы проста (например, группа – два граничащих прямоугольника), то вершины группы сохраняются. При сложной структуре группы или сложной форме ее компонент вершины группы склеиваются в одну анизохромную вершину.
Получившиеся в результате анизохромные вершины запоминаются как растры, остальные – как фигуры. Это представление используется для реконструкции страницы, например, при экспорте результатов распознавания во внешний редактор.
Вернемся к допущению о том, что сборка растров производится после распознавания. Оно реалистично только для полностью автоматической (пакетной) обработки. Напротив, при человеко-машинной обработке этап цветной фрагментации должен быть не завершающим, а первичным. На этом этапе пользователь, в частности, должен решить, как интерпретировать текст на фоне картинки.
Цена перехода окончательной к предварительной цветной фрагментации не столь велика как можно ожидать. В самом деле, фоны и простые компоненты в любом случае выделяются в самом начале обработки страницы. Разница в том, что до распознавания неизвестно, какие фоны являются текстонесущими и какие простые компоненты сооответствуют символам. Это не мешает выделить фрагменты, используя схему, близкую к схеме окончательной фрагментации, заменив в последней «текстонесущие фоны» на «фоны», оставив в дереве все простые компоненты и запретив подклейку фоновых вершин к родителям (последняя операция специфична для окончательной сборки, нужна для упрощения хранения растров и сопряжена с утратой информации о фоне). Очевидное и существенное различие предварительной от окончательной фрагментации – незавершенная сборка «бестекстовых картинок», содержащих анизохромные фоны, не могущие быть объединены пока не выяснится, что они не содержат текста.
Результат сборки фрагментов предъявляется пользователю, которому помимо стандартных действий над фрагментами должна быть предоставлена возможность указать один из трех вариантов интерпретации фрагмента. Снятие/объединение фрагментов также рассматривается как форма указания на интерпретацию. Так, снятие вложенного фрагмента может перенести на него атрибут охватывающего, если атрибут задан явно или автоматически определен как атрибут растровой интерпретации. Например, на странице имеется картинка с текстовой врезкой. Пусть автоматически выделены два фрагмента – картинка и фон врезки. Пользователь снял второй фрагмент. Затем в результате бинаризации и распознавания автоматически был определен тип первого – анизохромный фон без вложенного текста. Исходя из этого типа, снятый фрагмент без всякого анализа объединяется с картинкой.
