6.7. ПОСТРОЧНОЕ КОДИРОВАНИЕ И ГРАФ СМЕЖНОСТИ СТРОК

Если некоторое изображение не удается поместить в оперативную память, то часто его просмотр осуществляется вдоль строк, параллельных заданному направлению (растровая развертка). Этот способ просмотра изображения является также общепринятым в телевизионных системах. Изображение класса 2 можно закодировать, представив его последовательностью длин участков определенного цвета или яркости. Подобную информацию выгоднее всего хранить лишь для первого участка каждой строки, а для остальных участков следует запоминать только отклонения длины и яркости (или код цвета). Такой способ представления изображения часто называют кодированием с переменной длиной кодовой последовательности (КПДКП), хотя первоначально этот термин использовался лишь применительно к двухуровневым изображениям, при работе с которыми хранить необходимо только информацию о длине. Этот способ можно использовать и для кодирования изображений класса 1, при этом диапазоны изменения значений уровней яркости аппроксимируются их средним значением. Размер памяти, необходимой для хранения значений длин и яркостей, составляет на одну строку, где — число интервалов в строке, а обозначают те же величины, что и в предыдущем разделе. При типичном числе уровней серого тона, равном восьми, экономия памяти достигается, если меньше числа пикселов, составляющих строку, разделенного на два. Таким образом, использование кодирования с переменной длиной кодовой последовательности может привести к существенной экономии памяти, и при таком представлении изображений целесообразно применять алгоритмы анализа изображений и машинной графики непосредственно к закодированным данным, не прибегая к восстановлению исходного изображения.

Описание многих алгоритмов обработки изображений, предусматривающих использование КПДКП, упрощается при

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

Рис. 6.10 (см. скан) Пример смежности строк

На рис. 6.10 приведен пример Проекции интервалов частично перекрываются при одновременном выполнении следующих неравенств:

где — координаты концевых точек интервалов.

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

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

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

Утверждение 6.2. Если вершина ГСС имеет порядки то она соответствует локальному максимуму по вертикали. Если вершина имеет порядки то она соответствует локальному минимуму по вертикали.

При решении некоторых прикладных задач полезным оказывается следующий результат, относящийся к ГСС, строящимся для нескольких различных цветов Пусть на изображении присутствуют только два цвета, X и Y, и пусть ГСС для цвета X строится в соответствии с неравенствами (6.4), а для цвета используются уже нестрогие неравенства (допускаются равенства), так что вершины, соответствующие интервалам, соприкасающимся лишь одним углом, оказываются связанными. (Смысл введения этого допущения раскрывается в разд. 7.2.) Соответствующая конструкция представлена на рис. 611.

Утверждение 6.3. Если вершина ГСС, соответствующего цвету X, имеет порядки то в ГСС, соответствующему цвету У, на строке, смежной снизу со строкой рассматриваемой вершины ГСС для цвета X, найдется вершина, имеющая порядки Аналогичным образом, при в ГСС для цвета У на строке, смежной сверху со строкой рассматриваемой вершины ГСС для цвета X, найдется вершина, имеющая порядки . В обоих случаях справедливы обратные утверждения.

Доказательство. Приведем доказательство утверждения, относящегося к нижнему порядку, большему единицы. Пусть — концевые точки интервала цвета X, соответствующего вершине, имеющей нижний порядок, больший единицы (см. рис. 6.11,а). Это означает, что на смежной снизу строке имеются концевые точки интервалов удовлетворяющие следующим неравенствам:

Отметим, что является правой, — левой концевой точкой интервалов цвета Х (см. рис. 6.11, а). Следовательно, интервал должен иметь цвет У. Он будет связан с интервалами того же цвета, находящимися на смежной сверху строке, в том и только том случае, если выполняется одно из следующих неравенств:

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

Рис. 6.11. Иллюстрация к утверждению 63. а — обозначения, используемые при доказательстве утверждения, б — общая конструкция

Допустим, с другой стороны, что интервал имеет нулевой верхний порядок Из этого следует, что неравенства (6.6) не могут выполняться Таким образом, неравенства (6 5) — истинны, и, следовательно, существует интервал цвета X, нижний порядок которого больше единицы Аналогичное доказательство можно провести для случая верхнего порядка, большего единицы.

Из утверждения 6.3 следует, что интервалы цвета X, у которых верхний или нижний порядок превосходит единицу, соответствуют тем частям изображения, где область цвета У имеет либо максимум по вертикали, над которым располагается интервал цвета X (например, вершины А и С на рис. 6.11, б6), либо минимум по вертикали, под которым располагается интервал цвета X (например, вершины на рис. 6.11, б).