Материал: Системы технического зрения. Литвиненко А.М., Машаров А.В

Эта функция определена для всех х и у, но особый для нас интерес представляют ее значения в точках решетки (х, у) = (kw, lh). Мы можем преобразовать ее к виду

(x,у) = (kw, lh) получаем fkl. Между точками решетки f (x, y) интерполируется с помощью ядра преобразования, равного произведению двух членов вида sin (x)/x и sin (y)/y.

Иной подход состоит в рассмотрении функции, получаемой

умножением f (x, y) на пространственно дискретизирующую функцию

так что преобразование Фурье произведения f (x, y) на д(х, у) является диcкретизованным фурье-образом F(u, v) функции f(х, у), а

218

именно

F (2 k / w,2 l / h) (u 2 k / w, 2 l / h)

k l

2.3.3. Теорема отсчетов

Из сказанного выше видно, что функция с ограниченным частотным спектром полностью определяется отсчетами в узлах регулярной решетки. Этот результат известен как теорема отсчетов. Если F (и, v) = О при | u | / w или | | / h , то f(х, у)

можно восстановить по набору значений f(kw, lh), где k, I пробегают все целые числа. На самом деле мы даже располагаем явной интерполяционной формулой, не содержащей преобразования Фурье,

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

/ 2 , где , — длина волны, соответствующая максимальной присутствующей в спектре частоте. Если 5 — интервал между отсчетами, то результат можно сформулировать в терминах частоты Найквиста / . Чтобы верно восстановить сигнал по отсчетам, он должен содержать частоты, не превосходящие частоты Найквиста.

Из теоремы отсчетов становятся ясными те опасности,

219

которые подстерегают нас при применении обсуждаемого» метода к функциям, не удовлетворяющим указанному ограничению. Информация теряется, и исходную функцию восстановить нельзя. Конкретно происходит следующее: при дискретизации высокие частоты становятся неотличимыми от частот, лежащих в допустимом диапазоне. Это выглядит так, будто эти частоты «загоняются назад» под отметку В. Иначе это называется эффектом наложения, поскольку гармоника с частотой w > В порождает те же отсчеты, что и гармоника с частотой 2В — w.

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

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

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

220

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

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

Функции с ограниченным спектром являются «гладкими», поскольку их производные высокого порядка ограничены по амплитуде. Например, преобразованием Фурье функции

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

221

Оказывается, другие схемы расположения отсчетов обладают определенными преимуществами. Например, мы можем использовать шестиугольные элементы изображения, лежащие на треугольной решетке. Если спектр изображения ограничен условием р < В, то при таком разбиении потребуется меньшее число отсчетов. Указанный срез по частоте, обладающий круговой симметрией, выглядит здесь более естественным, чем срез в виде прямоугольника, хорошо согласующийся с прямоугольным способом разбиения. Разница между двумя разбиениями возникает из-за различия между участками частотной области, которые можно восстановить без искажения. Для квадратного разбиения этот участок имеет форму квадрата. Чтобы в квадрат можно было вписать круг радиусом р < R, его стороны должны иметь длину 2р. В случае гексагонального разбиения указанный участок имеет форму шестиугольника. Чтобы подобный же круг можно было вписать в шестиугольник, достаточно, чтобы размер максимального

поперечного сечения был равен 4 / 3 .

2.3.4. Дискретное преобразование Фурье

Преобразование Фурье дискретного изображения является периодическим. Если это изображение рассматривать как часть продолженного до бесконечности периодического изображения, то его преобразование

Фурье оказывается также дискретным[58,59]. Таким образом, как изображение, так и его фурье-образ периодичны и дискретны. Оба полностью определяются конечным набором значений. Если изображение задается значениями fkl функции f(x, у) в точках (kw, lh), k = 0, 1,...,М-1, l = 0 1,..., N-1, то прямое преобразование Фурье можно записать в виде

222

а обратное – в виде

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

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

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

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

223

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

Ранее мы убедились в том, что как свертке в пространственной области отвечает умножение в частотной области, так умножению в пространственной области отвечает свертка в частотной области. Следовательно, преобразование Фурье промодулированного

изображения равно умноженной на 4 2 свертке фурье-образа исходного изображения с фурье-образом функции выделения окна. Тем самым фурье-образ исходного изображения несколько смазывается в результате применения операции выделения окна. Для приведенной выше функции выделения окна преобразование Фурье имеет вид

соседних значений, находящихся в рамке размера 3x3. Вес центральной ячейки составляет 1/4, четырех ячеек, примыкающих по сторонам,- 1/8,

а четырех угловых ячеек - 1/16. Такую схему свертки можно

224

представить следующей маской:

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

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

Быстрое преобразование Фурье (БПФ) требует для вычисления всех значений всего лишь 4MNlog2MN умножений за счет более эффективного использования промежуточных результатов. Поэтому оказывается целесообразным вычислять свертку путем выполнения преобразования Фурье, умножения и обратного преобразования. Несмотря на это, многие современные аппаратные решения в параллельных устройствах направлены на поддержку прямых методов вычисления свертки.

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

225

Здесь каждое из fkl — случайная величина, независимая от остальных. Допустим, что fu могут принимать комплексные значения. Тогда

также случайная величина, имеющая случайную фазу, если фаза fkl случайна. Поэтому каждое значение Fmn получается суммированием MN независимых случайных величин.

Теперь, если еще предположить, что fkl распределены нормально с нулевым средним и стандартным отклонением , то Fmm как нетрудно заключить, также имеют среднее значение, равное

нулю. Стандартное отклонение будет равно 1/ MNа, поскольку

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

стандартным отклонением 1/ MN .

2.3.5. Круговая свертка

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

226

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

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

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

2.4.Края и их обнаружение

2.4.1. Края и их обнаружение

227