6.6. АЛГОРИТМЫ РАСЩЕПЛЕНИЯ — СЛИЯНИЯ

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

Отметим, что в данном случае дерево используется не для преобразования изображения, а для управления обходом. Так, на уровне q, где квадраты содержат 2x2 пикселов, значение критерия однородности области вычисляется по всем пикселам, а среднее значение по квадрату не используется. Результатом снова является изображение с изменяющейся четкостью, однако в данном случае мы получаем лишь один экземпляр, а не последовательность изображений, как в описанном выше случае. На рис. 6.9 приведен соответствующий пример

Можно построить алгоритмы, отправными точками которых служат отдельные пикселы и которые выполняют только процедуры слияния. Можно построить также алгоритмы, которые применяются к полному изображению и выполняют только процедуры расщепления. Алгоритмы первого типа обладают тем недостатком, что на отдельных пикселах невозможно проверить выполнение многих критериев однородности области. Недостатком алгоритмов второго типа является необходимость выполнения большего объема вычислений, поскольку процедура расщепления более трудоемка, чем процедура слияния (см. задачу 6.8).

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

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

Рис. 6.9. (см. скан) Использование тетрарного дерева в алгоритме расщепления — слияния. Критерий однородности области основан на вычислении матрицы совместной встречаемости уровней серого тона Границы квадратов наложены на исходное изображение. Первоначально изображение было разделено на 64 квадрата, из которых часть была подвергнута слиянию, а часть расщеплению

Для каждого квадрата необходимо предусмотреть заголовок, указывающий размеры и положение, выраженные через косудинаты х, у на плоскости. Если изображение имеет размеры то для представления его размера и положения достаточно затрачивать по бит. Таким образом, можно ограничиться затратой бит на квадрат для описания координат его левого верхнего угла и длины стороны. Можно воспользоваться также системой индексации, описанной в разд. 6.4. В этом случае заголовок будет представлять собой метку, состоящую максимум из символов. Поскольку в качестве таких символов используется одно из чисел: О, 1, 2 или 3, то для его представления достаточно иметь два бита. Представление информации о длине метки требует, однако, затраты бит на каждую метку. Для работы с метками с фиксированной длиной можно воспользоваться заполнением свободных мест в метке другим символом, например числом 4, что потребует увеличения затрат памяти до 3 бит на символ. Итак, в зависимости от используемой системы представления на заголовок приходится расходовать или бит, где обозначает длину соответствующей метки. Хотя при использовании заголовков в виде меток с переменной длиной затраты памяти снижаются, соответствующее увеличение сложности реализации, возможно, не компенсируется экономией памяти.

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

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

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

Алгоритм 6.6 воспроизводит основную процедуру обхода изображения размерами в случае, когда просмотр изображения начинается с уровня содержащего квадратов с размерами каждый. (Таким образом, полное изображение соответствует нулевому уровню, а отдельные пикселы — Алгоритм строит не полное дерево, а лишь его необходимые части. Он работает со связным списком элементы которого соответствуют вершинам тетрарного дерева, упорядоченным таким образом, что четыре последовательно расположенные вершины имеют на дереве одного и того же предка. Поскольку индекс используемый при просмотре списка, записывается по основанию 4, координаты х, у левого верхнего угла квадрата определяются непосредственно (см. рис. 6.4). В самом деле, если — разряды индекса перечисленные, начиная с младшего, то справедливы приведенные ниже уравнения (6.3).

Алгоритм 6.6. Процедуры расщепления — слияния, основанные на использовании тетрарного дерева

Обозначения. Связный список содержит координаты левого верхнего угла и размеры квадратов, а также указатели на предшествующий и следующий элементы. Индекс записывается по основанию 4. Входными данными служит набор квадратов, соответствующих некоторому уровню тетрарного дерева. Выходными данными служит другой набор квадратов, соответствующих другим уровням дерева. Условия на шагах 4 и 11 и условия на шагах 8 и 13 предусматривают вызов какой-либо процедуры проверки однородности области.

(см. скан)

(см. скан)

где символ обозначает наибольшее целое число, меньшее или равное х. Координаты могут принимать значения от 0 до В примере на рис. 6.4 , а индекс 213 соответствует

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

Предполагается, что имеется некоторый критерий однородности области, позволяющий определить, следует ли слить группу областей или расщепить отдельную область. (Подобные критерии были рассмотрены в разд. 4.4.) Алгоритм осматривает область таким образом, что при расщеплении немедленно проверяется однородность ее первой дочерней подобласти.

Описанный алгоритм можно использовать не только для сегментации изображений, но и для решения иных задач. В разд. 17.2 описано его применение для решения задачи разделения видимых и невидимых элементов объекта, однако при этом никаких слияний не производится (см. также задачу 6.9).