Методы обхода плоскости

Задача обхода плоскости возникает при обработке двумерных данных. Цель: создание одномерного массива D из двумерного массива S. Причем если предполагается последующее сжатие D, то желательно создавать его так, чтобы "разрывов" было как можно меньше: каждый следующий эле­мент Д, заносимый в D на i-m шаге, является соседним (в плоскости) для предыдущего, занесенного в D на (/-1)-м шаге, Д./.

Змейка (зигзаг-сканирование)

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

На иллюстрации показан порядок выборки элементов из плоскости (с последующим занесением в одномерный массив). Значение из ячейки массива S, помеченной на рисунке номером i, заносится в D[i].

Змейка выгодна в случаях, когда в одном из углов "особенность", на­пример сосредоточены самые крупные коэффициенты. Применяется в алго­ритме JPEG для обхода квадрантов (размером 8x8 точек).

Обход строками

Самый тривиальный метод. Именно он используется в самых распро­страненных графических форматах (BMP, TGA, RAS...) для хранения эле­ментов изображений.

борку в обратном направлении:

Точек "разрыва" нет, в отличие от варианта без разворотов. Совершенно аналогично можно делать обход столбцами.

Упражнение. Нарисуйте пример обхода плоскости столбцами с разворотами.

Обход полосами

Чаще всего сжатие лучше, если каждая область двумерного массива S не рассредоточена (равномерно "размазана") по всему одномерному D, а скон­центрирована в D компактно. В случае обхода строками понятие "области" отсутствует: каждый элемент считается "областью". Пытаясь обходить плоскость квадратами размером NxN, приходим к идее обхода горизонталь­ными "полосами" шириной N:

В данном примере ширина полосы N=3. Если N=1, получаем обход строками.

Полосами с разворотами

То же самое, но с разворотами и столбцов внутри полос, и направлений самих полос:

Разрывов опять нет, но теперь еще и каждая точка принадлежит к облас­ти, записанной в D компактно, без разрывов: ее элементы расположены внутри одного интервала (£>[/], /)[i+l], ■••, D[i+f\) и элементов из других об­ластей внутри этого интервала нет. Примеры таких областей - каждый из четырех углов размером 3x3 элемента.

Упражнение. Нарисуйте схему обхода квадрата 7x7 полосами шириной 3 с разворотами. Какой вариант лучше: 3+3+1 или 3+2+2? Какие области заносят­ся в D компактно?

Обход решетками

Для первой порции берем элементы из каждого N-ro столбца каждой М-й строки. Для второй - то же, но со сдвигом на один столбец. Так же и для следующих, а затем - со сдвигом на одну, две, (М-1) строки. Например, если M=N=2, то имеем 4 порции:

То есть плоскость разбивается на прямоугольники размера MxN, задается обход плоскости прямоугольниками, а также обход внутри самих прямо­угольников и далее делается "одновременный" обход по каждому из них: сначала выбираются их первые элементы, затем вторые, третьи, и т. д., до последнего.

Обход решетками с учетом значений элементов

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

Допустим, атрибуты распределены так:

Тогда имеет смысл дальше действовать так:

То есть сначала обходим квадраты с атрибутом "R", затем с атрибутом "G" и, наконец, с "L".

Контурный обход

Часть элементов принадлежит к одной группе, часть - к другой, причем контур задан:

36 элементов - из группы "1", а 12 - из группы "2".

Очевидно, что имеет смысл отдельно оформить элементы группы "1"

и затем точно так же остальные элементы, принадлежащие к группе "2"

Контурный обход с неизвестными контурами

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

Обходим плоскость "столбцами с разворотами" и, обнаруживая элемент

другой группы (в элементах 9, 10, 14...), также делаем разворот на 180°. За­тем (шаги 45-48) обходим оставшуюся часть плоскости, содержащую (предположительно) элементы другой группы. В итоге имеем:

■ среди первых 36 элементов 4 из группы "2", а 32 из группы "1";

■ из последних 12 элементов 8 из группы "2", а 4 из группы" 1".

В первой части 4/36=1/9 "исключений", во второй - 4/12=1/3. А если бы делали просто обход "столбцами с разворотами":

В итоге:

■ среди первых 33 элементов 12 из группы "2", а 21 из группы "1";

■ из последних 15 элементов все из группы" 1".

То есть в большей части получившегося блока - более чем 1/3 "исключений".

"Квадратная змейка"

Рекурсивный метод для квадратных областей.

Если принять левый верхний элемент за первый, то для квадрата 2x2 возможны два варианта обхода без разрывов:

То есть либо первый переход внутри квадрата был сверху вниз, тогда пя­тым шагом будет переход к левому верхнему элементу квадрата справа

(или к правому нижнему элементу квадрата сверху). Либо, наоборот, пер­вый переход внутри квадрата был вправо, тогда пятым шагом будет пере­ход к квадрату снизу (или слева). Переформулируем так:

■ если нужно выйти к правому (или верхнему) квадрату, то первый шаг -вниз, если к нижнему (или левому), то первый шаг - вправо;

■ пройденным путем однозначно задается, к какому квадрату нужно вый­ти в каждый конкретный момент;

■ только в самом начале есть выбор одного из двух вариантов обхода. Например:

Первый шаг внутри квадрата 2x2 был вправо, - значит, в результате об­хода этого квадрата 2x2 мы должны выйти к нижнему квадрату 2x2.

Первый шаг перехода от 2x2 к 2x2 внутри 4x4 был вниз, - значит, мы должны выйти к правому 4x4.

Первый переход внутри квадрата 16x16 был вправо, - значит, в резуль­тате обхода 16x16 мы должны прийти к нижнему, и т. д.

Разрывов нет, и каждый элемент принадлежит к области, записанной компактно.

ЭД. Упражнение. Определите, какие числа должны быть в незаполненных клетках примера. Нарисуйте другой пример: при выборе второго элемента квадрата делаем переход не слева направо, а сверху вниз.

Для квадрата 3x3 можно взять такие два "шаблона":

Первое правило будет "противоположным" первому правилу случая 2x2, но остальные два - такие же:

■ если нужно выйти к правому (или верхнему) квадрату, то первый шаг - вправо, если к нижнему (или левому), то первый шаг - вниз;

■ пройденным путем однозначно задается, к какому квадрату нужно вый­ти в каждый конкретный момент;

■ только в самом начале есть выбор одного из двух вариантов.

Но для 3x3 есть еще и такие варианты:

Видно, что они совершенно эквивалентны, т. е. взаимозаменяемы, по­скольку в обоих случаях мы выходим в правый нижний угол. Точно так же эквивалентны и два варианта обхода ими квадрата 9x9:

И

Совершенно аналогично для 5x5, и затем 25x25 и т. д.

Если требуется обойти квадрат размера NxN, сначала определяем, про­изведением каких простых чисел является N, затем задаем порядок этих чи­сел в произведении (а для каждого нечетного множителя еще и направление обхода). Таким образом будет задан процесс обхода.

Если К, равное числу двоек в произведении, больше одного: К>1, то сторона самого мелкого квадрата должна быть 2^К"' или 2^К элементов. На­пример, если К.=3, то обход без разрывов 2x3x2x2 (от самого мелкого 2x2 к 6x6, затем к 12x12 и, наконец, к 24x24) невозможен:

Каждая ячейка этой таблицы - квадрат 2x2; нижние 5 строк пропущены: перейти к двум нижним квадратам 12x12 без разрыва не сможем.

Других ограничений при обходе "квадратной змейкой" нет.

Каждый квадрат со стороной L>2 можно обходить обычной змейкой, а не "квадратной". Это выгодно в том случае, если наиболее различаю­щиеся элементы сгруппированы в противоположных углах квадрата.

S*. Упражнение. Нарисуйте порядок обхода квадрата 25x25, а затем - квадрата 12x12. Убедитесь, что разрывов нет и каждый элемент принадлежит к компакт­но записанной области.

Обход по спирали

Обход по спирали довольно тривиален. Строится квадрат 3x3, затем 5x5, затем 7x7,9x9 и т. д.:

Если же строить круги радиуса 2, 3,4 и т. д., неизбежно будут присутст­вовать точки разрыва. Спираль может быть и сходящейся. Суть ее можно показать с помощью этой же иллюстрации, только направление движения обратное: от 49 к 1. Кроме того, она может быть с разворотами:

Направление изменяется в точках, расположенных на диагонали: в дан­ном примере это "25" и "41".

Общие моменты для прямоугольных методов

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

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

Общие моменты для методов сложной формы

Может возникнуть необходимость помечать уже обработанные точки плоскости, чтобы избежать лишних вычислений, предотвращающих по­вторное их занесение в D. Тогда есть два основных варианта: либо добавить по одному "флаговому" биту для каждой точки плоскости, либо выбрать (или добавить) значение для "флага", показывающего, что точка уже внесе­на в D, и записывать это значение на место уже внесенных точек.