7.2. ДИСКРЕТИЗАЦИЯ И ТОПОЛОГИЯ

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

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

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

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

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

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

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

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

Рис. 7.2. Примеры трудностей, возникающих при задании критериев дискретизации изображений; при дискретизации левого рисунка области А и В поддаются обнаружению, а при дискретизации правого рисунка они пропускаются

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

С практической точки зрения главной проблемой при дискретизации изображений класса 2 является сохранение формы областей. Для обеспечения последнего необходимо, чтобы связные области непрерывного изображения оставались связными на

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

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

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

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

ясность используемой терминологии. Говорят, что два множества А и В топологически эквивалентны, если между Л и В существует некоторое взаимно-однозначное отображение, причем как отображение А в В, так и обратное отображение из В в А непрерывны ([7.4, р. 87]). Поскольку при обработке изображений обычно встречается топология, индуцированная евклидовой метрикой, то топологическая эквивалентность означает существование такого взаимно-однозначного отображения, при котором точки, расположенные вблизи друг от друга, отображаются в точки, расположенные вблизи друг от друга, и наоборот. Содержательно это означает, что одно множество можно отобразить на другое при помощи растяжения и сжатия, не допуская при этом никаких разрывов и разрезов. Следовательно, область, в которой имеется дыра, не может быть топологически эквивалентна области, не имеющей дыры, поскольку соответствующее преобразование потребовало бы проведения разреза.

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

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