§ 11. Дискретизация, интерполяция и экстраполяция

Чтобы производить какие-либо численные расчеты с некоторой измеренной величиной (или математической функцией), ее следует дискретизовать. Рассмотрим, например, дискретизацию спектра в частотной плоскости. «Разрешение», соответствующее процедуре дискретизации, можно описать аппаратной (instrument) функцией устройства, осуществляющего дискретизацию. Чувствительность этого устройства может зависеть от положения в частотной плоскости точки растра и поэтому мы укажем в обозначении аппаратной функции аргумент: Отсчет функции в точке растра и, определяется как

Заметим, что выражение (11.1) зависит только от точки и, в силу принятого нами определения функции Величину

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

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

где одномерные аппаратные функции, скажем, вида где «эффективная ширина» каждой функции. Все эти функции сводятся к дельта-функиии при Выполняются следующие соотношения:

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

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

Из изложенного нами в первых двух абзацах § 10 следует, что формула

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

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

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

поскольку тогда выражение (11.6) сводится к значению при

Пытаться охватить все К заданных отсчетов одной интерполяционной формулой, такой, как (11.6), имеет смысл лишь в том случае, если функция монотонно уменьшается или осциллирует, затухая, относительно убывающего среднего значения с возрастанием величины и Именно так ведут себя функции определенные соотношением (6.4) и очень часто возникающие в формулах, подобных формуле (10.4). Однако интерполяция функциями допустима только тогда, когда интерполируемая функция ограничено по полосе, т. е. фурье-образ тождественно равен нулю за пределами некоторого кадра. Необходимо также иметь достаточно хорошие оценки размеров этой области (см. § 7), чтобы интерполяция была успешной.

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

Вероятно, проше всего добиться, чтобы интерполяционные функции удовлетворяли условию (11.10), если разделить их и -зависимости:

причем

где верхним индексам отвечают значения соответственно. К сожалению, соотношения (11.12) совместимы с соотношением (11.10) только тогда, когда точки растра лежат на прямоугольной сетке. Заметим, что две функции под знаком суммы в формуле (11.8) точно описываются соотношением (11.11), если величины и равны соответственно. Использование функций оправдано только тогда, когда выполняются условия (10.1) и (11.7). Если не имеется априорной оценки размеров изображения или если просто некоторая функция двух произвольных параметров (обозначаемых для удобства через ), форму которой необходимо оценить по заданным отсчетам, то может оказаться более целесообразным применить полиномы Лагранжа. Рассмотрим подмножество одно значение индекса к множества точек растра, в котором прямоугольные координаты точки и. равны все точки и лежат на прямой линии, проходящей параллельно оси и на расстоянии от нее. Форму функции на этой линии можно задать следующим образом:

где заданный отсчет, соогветстпуюший точке растра и А, а lagrange; есть полином Лагранжа. определяемый следующим образом:

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

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

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

( — константы). В формуле (11.15) подразумевается, что начало координат сдвинуто в окрестность точки интерполяции. Чтобы Оценить величину , нужно сначала вычислить коэффициенты путем подстановки в левую часть равенства (11.5) заданных отсчетов, а в правую — координат точек растра. Обозначая декартовы координаты точки и, через и получаем

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

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

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

где при всех значениях индекса Далее по формуле (11.13) оценивают мнимую часть величины при значениях и, близких к «усредненной» -координате «линии», взяв значение при котором

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

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

интерполяция. Вопросы, связанные с реализацией алгоритмов интерполяции на прямоугольных сетках, рассматриваются в § 45 47.

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

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

где области, которые совместно составляют область не пересекаясь:

где — символ пустою множества. Нижний индекс в формуле (11.19) означает «заданное» (от а индекс «оцениваемое»

На основе алгоритма Герхберга оценивается функция [здесь принимается, что поскольку изображение имеет только вещественные значения, см. § 8], протяженность которой в частотной плоскости достаточна для того, чтобы можно было с приемлемой точностью восстановить размеры кадра изображения (см. § 7) Предварительная оценка истинного изображения определяется следующим образом:

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

Первая оценка изображения представляет собой неотрицательную часть оценки ) на Первая оценка функции

определяется как

Оценка (11.22) складывается затем с исходными данными, т. е. с и путем преобразования Фурье вычисляется вторая предварительная оценка изображения (которую мы тоже обозначим через чтобы избежать усложнения индексов]:

Вторая оценка истинного изображения, снова обозначаемая через находится как та часть функции которая лежит в пределах кадра У. и вышеупомянутого порогового значения. Тем самым мы устанавливаем итерационный цикл, поскольку можно подставить новую оценку в формулу (11.22) и получить новую оценку а последнюю снова подставить в формулу (11.23) и т. д. Такой процесс продолжается до тех пор, пока величина

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

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

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