Принципы интерполяции для двухмерных сигналов

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

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

В основе двухмерной интерполяции, применяемой к зображениям, как двухмерным сигналам, лежат принципы одномерной интерполяции. Функция одной переменной , представленная в дискретной форме , где , может быть замененаполиномом n-й степени – аналоговой функцией

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

Задача полиномиальной интерполяции – нахождение коэффициентовинтерполяционного полинома (1) -го порядка при опорных значениях. Точность восстановления исходной функцииинтерполянтом увеличивается при увеличении порядка полинома и числаопорных отсчетов.Это справедливо до тех пор, покаиспользуемые опорные отсчеты являются значениями одной алгебраическойфункции, т.е.функции, котораяможет быть представлена ввиде многочлена -й степени:

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

Последовательное применение одномерных интерполяций для получениязначения пространственного интерполяционного отсчета сохраняетназвание базовой одномерной интерполяции с приставкой “би”, например,билинейная, бикубическая и т.д.Результат или качество интерполяции проявляется, в основном, на контурахизображения, для которых потеря информации при ограничениипространственного спектра сигнала, например, при сканировании,наиболее значительна. Для полинома нулевой степени характернообразование ступенчатого контура, а для полиномов более высокихстепеней – образование зоны размытия, закон изменения сигнала в которой соответствует используемому полиному.

Простейший вариант интерполяции соответствует случаю, когдаинтерполяционные значения рассчитываются по единственному опорномузначению для всего интервала интерполяции. Для одномерного сигнала этозначение и, соответственно, интерполяционный полиномнулевого порядкаи представленный им интерполянт – это константа для данного интервала интерполяции.Такой метод интерполяции называется ступенчатой интерполяцией и,несмотря на большие погрешности, используется при аппаратной ипрограммной реализации благодаря своей простоте. На рис.1 показанпример ступенчатой интерполяции для одномерного сигнала.

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

апертурой сканирования (рис.2);

интервалом пространственной дискретизации элементарной площадкой полиграфического растра.

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

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

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

,(3)

где: - разрядный коэффициент -го разряда кода сигнала; - величина оптического параметра, соответствующаяединице младшего разряда прямого двоичного кода; - значение оптического параметра – представителя для всего пространственного интервала дискретизации.

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

Для линейной интерполяции используется многочлен первой степени:

Рис.2

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

Рис. 3

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

Рис.4

Интерполяция при масштабировании цифрового растрового изображения

В общем виде цифровое растровое изображение может быть представлено двумяматрицами одинакового размера:

1) Матрицей дискретных значений сигналов, упорядоченных по строкам истолбцам по их реальному положению в границахизображения:

2) Матрицей координат, соответствующих отсчетам пространственнойдискретизации с постоянными интервалами

где: - число элементов в строке изображения (по координате , - число строк в изображении (по координате .

Задача масштабирования в растровой графике может быть решенаумножением матрицы координат на скалярный коэффициент масштабирования

,

в результате чего образуется новая матрица (7), равная по размеру исходной матрице (6):

где: - интервал пространственной дискретизации по координате после масштабирования, - интервал пространственной дискретизации по координате после масштабирования.

Матрица (7) остается равновеликой сматрицей (6) и каждому пространственному отсчетуновой матрицы соответствует значение сигнала. Размер изображения в данном случаеизменяетсяза счет масштабирования интервала пространственнойдискретизации при сохранении числа элементов матрицы . Этот принципмасштабирования применяется в профессиональных системахподготовки полиграфических изображений при наличии рабочего процессасизвестными параметрами – коэффициентом масштабирования и линиатурой полиграфического растра . В этом случае шаг пространственной дискретизациипри сканировании исходного изображениявыбирается исходя из соотношения (8):

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

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

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

После преобразования матрица координат принимает вид:

где: - число элементов в строке масштабированного изображения (по координате ); - число строк масштабированного изображения (по координате ).

Матрица значений сигнала (5) приводится в соответствие с матрицей координат (9) методом интерполяции.

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

При умножении числа элементов строки на масштабный коэффициент образуется новая длина строки

Рис.5

На рис.5 показан принцип одномерного масштабирования растровогоизображения по координате x с коэффициентом . Работа алгоритмаинтерполяции рассмотрена для i-ой строки исходного изображения (Рис.5-A). Ниже на рис.5-B показана i-я строка послемасштабирования при сохранении интервала пространственнойдискретизациии на рис.5-C та же масштабированнаястрока, физический размер которой приведен к исходному, что позволяет оценить пространственное положение опорных отсчетови отсчетов перевыборки. Такое преобразование, не изменяющее физического размера изображения, приводит к перевыборке с новым интервалом пространственной дискретизации и используется наряду с масштабным преобразованием как в сторону увеличения числа интервалов дискретизации, так и в сторону уменьшения. В последнем случае при повторной дискретизации (перевыборке) выполняется ограничение пространственного спектра изображения в соответствии с условиями применимости спектрального критерия Котельникова.

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

Алгоритм решает две задачи:определение индексов интервала опорных значений, покоторым выполняется расчет каждого значения перевыборкиисобственно расчет интерполяционного значения сигналапо положению отсчета перевыборкивинтервале.

Определение взаимного расположения опорных отсчетов и отсчетов перевыборки

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

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

Текущий номер отсчета перевыборки по координате умножается на величину, обратную масштабному коэффициенту: (12) Значение – это фактически результатизмерения шкалы пространственной дискретизации C шкалой A (Рис.5). Например, для 7-го отсчетаперевыборки.

В полученном результате выделяется целая часть – номерпервого опорного отсчета интервала интерполяции. Для рассматриваемогочисленного примера . При отсутствии дробной части отсчет перевыборки совпадает с опорнымотсчетом. Например 8-й отсчет перевыборки представлен 6-м опорнымотсчетом (Рис.5). Вторая граница интервала интерполяции – (.

В значении выделяется дробная часть - величинаотносительного смещения отсчета перевыборки в интервале интерполяции. Для 7-го отсчета перевыборки .

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

Расчет интерполяционных значений

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

(13)

где: - относительное смещение значенияпространственной переменнойвпределахинтервалаинтерполяции, определенное в первой части алгоритма.

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

(14)

По полученной из выражений (13) и (14) паре значений определим значение отсчетаперевыборки при билинейной интерполяции по двум переменным:

(15)

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

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