2.4. Теорема отсчетов для двумерных сигналов

Дискретизацию двумерных сигналов и изображений чаще всего основывают на теореме отсчетов, обобщенной на двумерный случай, поскольку во всех практических задачах можно считать, что спектр изображений отличен от нуля только на ограниченном участке частотной плоскости. Однако двумерная теорема отсчетов богаче одномерной, так как двумерный интервал является существенно более сложным математическим объектом, чем одномерный [26].

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

Для этого достаточно пропустить сигнал с периодически продолженным спектром (рис. 2.1, б)

через двумерный фильтр с частотной характеристикой

где

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

Рис. 2.1.

Как следует из свойств двумерного преобразования Фурье (см. табл. 1.3, строка 13), спектру (2.13) соответствует

дискретный сигнал

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

где — импульсная реакция восстанавливающего фильтра — фурье-преобразование функции

Формула (2.17) выражает двумерную теорему отсчетов для случая дискретизации изображений на прямоугольном растре.

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

Более плотной упаковки спектров, чем на рис. 2.1, б, и соответственно менее плотного расположения отсчетов при дискретизации изображения со спектром, показанным

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

Рис. 2.2.

Соотношение между периодами продолжения спектра в косоугольной системе координат и шагом дискретизации дано в табл. 1.3, строка 18.

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

Рассмотрим спектр на рис. 2.3, а, отличный от нуля только на заштрихованном участке. Этот участок вписывается в квадрат. На рис. 2.3, б показана плотная упаковка спектральной плоскости, полученная наложением двух периодически повторенных в декартовой системе координат и повернутых на 90° один относительно другого исходных спектров рис. 2.3, а. Каждому из периодически повторенных спектров соответствует дискретное изображение с расположением отсчетов в узлах квадратной решетки, как показано на рис. 2.3, в. Эти два дискретных изображения, повернутые, как и их спектры, на 90° друг относительно друга (допустим вокруг точки О,

как на рис. 2.3, в), при наложении складываются. В результате получается новый дискретный сигнал, отсчеты которого равны, очевидно, попарным суммам отсчетов исходного изображения. Способ образования этих пар при повороте растра относительно точки О (рис. 2.3, в) иллюстрируется рис. 2.3, в-д. На рис. 2.3, в линиями соединены узлы растра, которые при повороте на 90° накладываются один на другой. Из рисунка видно, что узлы образуют группы по четыре, в которых происходит циклическая перестановка узлов при повороте, как показано стрелками на рис. 2.3, г.

Рис. 2.3.

Пусть — отсчеты в каждой группе, образованные в результате наложения отсчетов исходного изображения. Из рис. 2.3, г видно, что при повороте по часовой стрелке

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

Отсюда следует, что в каждой группе из четырех отсчетов (рис. 2.3, в) один отсчет является излишним: его можно вычислить по (2.19), зная три другие отсчета. Таким образом, за счет плотной упаковки поворотом экономится 25% отсчетов. Эти излишние отсчеты показаны на рис. 2.3, в незачерненными кружками, которые, как это видно из рисунка, заполняют нижнюю плоскости, как бы выпадающую тем самым из дискретизации.

Рис. 2.4.

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

Любопытный пример плотной упаковки на плоскости дает узор голландского художника Эшера, показанный на рис. 2.4. Он состоит из трех узоров, построенных периодическим продолжением фигуры ящерицы в гексагональной системе координат. Два узора повернуты на 60° по и против часовой стрелки относительно третьего и сдвинуты на полпериода по одной из координатных осей. В результате достигается плотная упаковка плоскости. Каждому из узоров, если

рассматривать его как периодическое продолжение спектра некоторого сигнала, соответствует дискретный сигнал с расположением отсчетов в узлах гексагональной решетки, причем узорам, повернутым на ±60°, соответствуют сигналы, отсчеты которых домножаются на комплексную экспоненту, зависящую от их координат (за счет сдвига в соответствии с теоремой сдвига, см. табл. 1.3, строка 8). Можно показать, что при наложении двух повернутых на 60° гексагональных растров отсчеты распадаются на группы по 6 отсчетов, суммируемых попарно. В результате из каждых шести сумм одна оказывается излишней: ее можно вычислить по остальным пяти (аналогично предыдущему случаю квадратного растра). Таким образом, при плотной упаковке спектров, показанной на рис. 2.4, экономится отсчетов исходного гексагонального растра.

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

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