Как выбрать метод интерполяции

Как выбрать метод интерполяции изображений? (Emgu/OpenCV)

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

  • CV_INTER_LINEAR
  • Я грубо понимаю линейную интерполяцию, но могу только догадываться, что такое кубика или область. Я подозреваю, что NN выступает за ближайшего соседа, но я могу ошибаться.

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

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

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

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

    Кубическая интерполяция (вероятно, фактически «бикубическая») использует одну из многих возможных формул, которые включают несколько соседних пикселей. Это намного лучше для сжатия изображений, но вы по-прежнему ограничены в том, сколько вы можете уменьшить без потери информации. В зависимости от алгоритма, вы можете уменьшить свои изображения на 50% или 75%. Основным недостатком этого подхода является то, что он намного медленнее.

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

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

    Метод CV_INTER_NN на самом деле является ближайшим соседом, это самый базовый метод, и вы получите более резкие края (ни один фильтр нижних частот не будет применяться). Однако этот метод просто напоминает «масштабирование» изображения, отсутствие визуального улучшения.

    Spline Toolbox

    Интерполяция функций интерполяционными полиномами

    В вычислительной математике существенную роль играет интерполяция функций, т.е. построение по заданной функции другой (как правило, более простой), значения которой совпадают со значениями заданной функции в некотором числе точек. Причем интерполяция имеет как практическое, так и теоретическое значение. На практике часто возникает задача о восстановлении непрерывной функции по ее табличным значениям, например полученным в ходе некоторого эксперимента. Для вычисления многих функций оказывается эффективно приблизить их полиномами или дробно-рациональными функциями (см., например [1] Ссылка в списке литературы). Теория интерполирования используется при построении и исследовании квадратурных формул для численного интегрирования, для получения методов решения дифференциальных и интегральных уравнений.

    Все перечисленные выше вопросы рассмотрены в классических учебниках по численным методам (см., например, [2-5] Ссылки в списке литературы). Цель этого раздела — демонстрация возможностей MATLAB для изучения вопросов, возникающих при интерполяции функций, в основном при помощи интерполяционных полиномов. В данном разделе приводятся необходимые сведения об интерполяции функций и при помощи небольших программ, написанных на языке пакета MATLAB, изучаются проблемы, возникающие при интерполяции функций. Простота языка пакета MATLAB в сочетании с широким набором его функций, в том числе и графических, позволяет вместо написания собственных программ интерполяции и визуализации результатов сосредоточиться на исследовании большого числа примеров, что может быть использовано при проведении лабораторных работ по численным методам для студентов технических факультетов вузов и институтов.

    Задача интерполяции функции, интерполяционные полиномы

    Пусть на отрезке [a,b] задана функция ?(x). Задача интерполяции (или интерполирования) состоит в построении функции g(x), совпадающей с заданной ?(x) в некотором наборе точек <x1,x2. xn+1> из отрезка [a,b] (эти точки называются узлами интерполяции), т.е. должны выполняться условия:

    где yk — известные значения функции ?(x) в точках xk. Функция g(x) называется интерполянтом функции ?(x).

    Пример интерполяции с четырьмя узлами приведен на следующем рисунке

    из которого видно, что узлы интерполяции не обязательно должны располагаться равномерно на отрезке [a,b].

    Если ?(x) табличная функция, скажем полученная из эксперимента, т.е. известны только ее значения yk в точках xk, то, вообще говоря, о качестве полученного приближения судить трудно. Однако, если значения ?(x) могут быть вычислены в любой точке отрезка [a,b], то в этом случае можно исследовать качество получающегося приближения, например найдя максимальное уклонение функции g(x) от функции ?(x). На качество приближения сильное влияние оказывает количество и расположение узлов, а также гладкость функции ?(x). Эти вопросы и будут численно исследованы в следующих разделах.

    Мы рассмотрим только линейную интерполяцию, т.е. такую, при которой функция g(x) разыскивается в виде линейной комбинации некоторых функций

    где для k=1,2. n+1: ?k(x) — заданные функции, а ak — искомые коэффициенты.

    Ясно, что из постановки задачи интерполяции (т.е. из совпадения значений интерполянта g(x) и интерполируемой функции ?(x) в точках xk) следует, что коэффициенты ak определяются из решения следующей системы линейных алгебраических уравнений:

    или в развернутой форме

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

    Очень часто в качестве системы функций ?k(x) выбирают полиномы, например степени x, именно:

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

    является определителем Вандермонда, который, как известно, равен

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

    Можно рассуждать и по-другому. Предположим, что есть два интерполяционных полинома gk и hk степени n такие, что для произвольного набора значений выполняются равенства g(xk) = h(xk) = yk) для всех k=1,2. n+1, т.е. для n+1-ой точки. Тогда их разность hkgk является полиномом степени не выше n, но обращается в ноль в n+1-ой точке. По известной теореме алгебры у полинома степени n не может быть больше чем n корней, следовательно hkgk ? 0 и hk ? gk. Единственность установлена. А так как полином единственный, то у соответствующей системы линейных алгебраических уравнений есть только одно решение (для произвольной правой части). Из результатов линейной алгебры известно, что у системы может быть либо бесконечное число решений при некоторых правых частях, либо единственное, для произвольной правой части. Последнее как раз и выполняется.

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

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

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

    Установим зависимость числа обусловленности этой матрицы от числа узлов интерполяции, предполагая, что они распределены равномерно на отрезке [-1,1]. Для этого напишем небольшую программу в MATLAB, в которой в цикле по числу узлов генерируются матрицы, находится их число обусловленности при помощи функции cond и строится график зависимости числа обусловленности матрицы от количества узлов

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


    Зависимость числа обусловленности матрицы от количества узлов интерполяции

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

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

    Интерполяционный полином в форме Лагранжа

    Итак, мы ищем полином Ln(x) степени не выше n, значения которого совпадают со значениями yk заданной функции ?(x) в узлах xk, где k=1,2. n+1 и все узлы различны.

    Одним из способов записи интерполяционного полинома является форма Лагранжа. Предположим, что для k=1,2. n+1 функции Фn(x) являются полиномами степени n, которые обладают следующим свойством

    будет как раз тем, который нам и нужен, поскольку это полином степени не выше n и Ln(xk) = yk для всех k=1,2. n+1.

    Функции Фn(x) строятся легко. Действительно, функция

    является полиномом степени n, который обращается в ноль для всех xj не равных xk. В точке xk она принимает значение

    или, что то же самое:

    Для примера построим графики функций Фn(x) для пяти узлов, равномерно распределенных на отрезке [0,1], для чего можно воспользоваться следующей небольшой программой:

    На следующем рисунке приведены полученные графики Фn(x) для k=1,2,3,4,5, узлы отмечены красными маркерами. Видно, что каждая из функций Фn(x) равна единице только в одном из узлов интерполяции, а в остальных она равна нулю.


    Графики Фn(x) для k=1,2,3,4,5.

    Итак, интерполяционный полином в форме Лагранжа имеет вид

    или в развернутой форме:

    Вычисление интерполяционного полинома в форме Лагранжа

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

    то для вычисления каждого из n+1-го произведений

    требуется n делений, n-1 умножение и 2n сложений (вычитаний). Далее, когда произведения найдены, для вычисления суммы требуется n+1 умножений и n сложений. Т.е. получается, что для каждого значения x вычисление Ln(x) требует порядка n? операций.

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

    за n-1 умножений, n сложений и 1 деление (эта операция делается для данного интерполяционного полинома только один раз перед вычислением его значений в точках), а затем находить значения интерполяционного полинома по формуле

    При таком способе вычисления значения интерполяционного полинома в точке требуется предварительная работа порядка n? операций, зато для каждого значения x время вычисления интерполяционного полинома требует порядка n операций. В знаменателе в выражении для функции s(x) находится разность x — xk, однако при x = xk значение интерполяционного полинома вычислять не требуется, оно известно и равно yk.

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

  • в функции lagrange — первый способ;
  • в функции lagrangef — второй способ;
  • Входные массивы x и y должны содержать значения xk и yk, соответственно, для всех k=1,2. n+1. Входной аргумент xx функций lagrange и lagrangef может быть массивом значений аргумента, для которых требуется вычислить значение интерполяционного полинома. Тогда в выходном аргументе yy вернется массив соответствующих значений полинома. При программировании функций lagrange и lagrangef не потребовалось делать цикла по элементам массива xx благодаря поддержке поэлементных операции при работе с массивами в MATLAB.

    Примечание (про поэлементные операции).
    Для массивов в MATLAB допустимы поэлементные умножение, деление и возведение в степень. Для этих операций применяются, соответственно, следующие сочетания (с точкой): .* , ./ , .^. Приведем несколько примеров поэлементных операций с векторами:

    При программировании интерполяционного полинома по второму способу в функции lagrangef не делалась проверка на равенство x какому-либо узлу, поскольку в MATLAB операция деления на ноль допустима (при делении на ноль числа не равного нулю получается Inf, а при делении нуля на ноль получается NaN, т.е Not a Number, не число).

    В качестве тестового примера проинтерполируем функцию sin x на отрезке [1,9] с шагом 2 и построим графики sin x и полученного интерполяционного полинома. В данном случае будет 5 узлов и, следовательно, интерполяционный полином получится 4-ой степени. Для построения графика интерполяционного полинома вычислим его значения при помощи функции lagrange в 1000 равномерно отстоящих друг от друга точках на отрезке [1,9].

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


    Интерполяция функции sin x полиномом 4-ой степени

    Хорошим тестовым примером для функций lagrange и lagrangef является приближение полиномиальной функции. Выберем в качестве интерполируемой функции полином пятой степени

    p5(x) = 4x 5 — 3x 4 + 14x 3 — 22x 2 — x + 5

    и проинтерполируем его полиномом пятой степени L5(x) на отрезке [-1, 1.5]. Для интерполяции понадобится шесть узлов, мы выберем их равноотстоящими на этом отрезке и проведем интерполяцию при помощи интерполяционного полинома в форме Лагранжа, вычисляемого приведенной выше функцией lagrange. Мы выведем не только график исходного полинома p5(x) и график интерполяционного полинома L5(x), но и график ошибки, т.е. разности p5(x) — L5(x).

    В результате получаем, что график интерполяционного полинома пятой степени практически совпадает с графиком исходного полинома, однако ошибка вовсе не равна нулю. Она имеет порядок 10 -14 , что объясняется ошибками округлений при вычислениях значений интерполяционного полинома. Более того, график распределения ошибки имеет характерный вид — в середине интервала ошибка меньше, чем по краям.


    Интерполяция полинома пятой степени по шести узлам

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

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

    Сначала проинтерполируем полином

    на отрезке [-1, 1.5] с тремя равноотстоящими узлами и получим интерполяционный полином L2(x) второй степени, затем с четырьмя и пятью равноотстоящими узлами и получим, соответственно, полиномы L3(x) и L4(x) третьей и четвертой степени.

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


    Интерполирование полинома пятой степени с тремя, четырьмя и пятью узлами

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

    на отрезке [-1, 1.5] с десятью, двадцатью и тридцатью равноотстоящими узлами и получим, интерполяционные полиномы L9(x), L19(x) и L29(x), соответственно, девятой, девятнадцатой и двадцать девятой степени.

    В результате мы видим, что ошибки округлений при вычислении значений интерполяционного полинома приводят к тому, что ошибка интерполирования растет (порядка 10 -14 для интерполяционного полинома 9-ой степени, порядка 10 -11 для интерполяционного полинома 19-ой степени и порядка 10 -9 для интерполяционного полинома 29-ой степени), хотя она должна была бы равняться нулю (при вычислениях в точной арифметике). Заметим, что характер распределения ошибки сохраняется — чем ближе к границам отрезка интерполирования, тем ошибка больше.


    Поведение ошибки для интерполяционных полиномов L9(x), L19(x), L29(x)

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

    который мы будем интерполировать полиномами на отрезке [-1, 1.5] с числом узлов интерполирования, изменяющимся от двух до ста. Т.е. наша цель — получить график зависимости от степени интерполяционного полинома n. Для этого в цикле по числу узлов интерполяции будем строить интерполяционный полином и вычислять максимальное уклонение его от p5(x), определяя это уклонение по 1000 равномерно отстоящим точкам на отрезке [-1, 1.5].

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


    Зависимость ошибки интерполяции от степени интерполяционного полинома

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

    Ошибка интерполяции, чебышевские узлы

    При исследовании ошибки интерполяции важно ограничится некоторым классом функций, поскольку значения произвольной функции могут сколь угодно сильно отличаться от значений ее интерполянта в точках, лежащих между узлами интерполяции. Мы будем предполагать, что на отрезке интерполирования [a,b] интерполируемая функция ?(x) имеет непрерывные производные до n-го порядка, а ее n-ая производная дифференцируема на отрезке [a,b]. Так же важно предположить, что все вычисления производятся без ошибок округления, поскольку, как было показано в предыдущем разделе Вычисление интерполяционного полинома в форме Лагранжа, ошибки округления сильно влияют на качество интерполяции при высоких степенях интерполяционных полиномов.

    Погрешность интерполирования функции ?(x) интерполяционным полиномом Ln(x) n-ой степени в точке x выражается следующим образом [3]

    где — некоторая точка из промежутка [a,b] и ?n+1(x) — полином степени n + 1, определяемый по формуле

    Значение ? вообще говоря неизвестно, однако, если известно максимальное значение на отрезке [a,b]:

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

    Продемонстрируем использование этой оценки для проверки ошибки интерполяции на примере интерполяции функции ?(x) = sinx на отрезке [-?,?] интерполяционным полиномом 4-ой степени с равномерно отстоящими пятью узлами интерполяции. Для вычисления интерполяционного полинома L4(x) воспользуемся функцией lagrange, текст которой приведен в разделе Вычисление интерполяционного полинома в форме Лагранжа. Сначала зададим узлы интерполяции и вычислим в них значения функции sinx:

    Теперь найдем значение yy интерполяционного полинома L4(x) и ошибку интерполяции err в точке :

    Вычислим правую часть оценки est с учетом того, что производные функции sinx не превосходят единицу, т.е. заменим Mn+1 на 1:

    Видим, что est (оценка) больше, чем err (ошибка интерполяции) при x = .

    Мы проделали проверку оценки ошибки в точке, а следующие команды приводят к построению графиков ошибки интерполяции функции ?(x) = sinx и ее оценки сверху на отрезке [-?,?] интерполяционным полиномом 4-ой степени с равномерно отстоящими пятью узлами интерполяции.


    График ошибки интерполяции и ее оценки сверху

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

    обращается в ноль, т.к.

    Если нас интересует максимальное уклонение интерполяционного полинома от интерполируемой функции, то в последней оценке можно взять максимум по x:

    Из этой оценки видно, что мы можем управлять максимальной ошибкой за счет подходящего выбора узлов интерполяции. Цель выбора узлов интерполяции <x1,x2. xn+1> — сделать максимальное значение модуля полинома

    на отрезке [a,b] как можно меньше. Разумеется, эта задача имеет смысл только если мы можем вычислять интерполируемую функцию ?(x) в любых точках на отрезке [a,b]. Если функция задана таблично, то такой возможности нет.

    Ограничимся сначала случаем a = -1, b = 1. Известно, что если узлы интерполяции <x1,x2. xn+1> являются корнями полинома Чебышева степени n + 1, то величина принимает наименьшее возможное значение по сравнению с любым другим выбором набора узлов интерполяции.

    Полиномы Чебышева, предложенные и исследованные П.Л. Чебышевым в середине 19-го века, определяются следующим образом:

    Очевидно, что для k = 1 функция T1(x) действительно является полиномом первой степени, поскольку

    В случае k = 2 тоже очевидно, что T2(x) есть полином второй степени, если воспользоваться известным тригонометрическим тождеством

    положив ? = arccos x. Тогда получаем

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

    При помощи этого рекуррентного соотношения можно последовательно получить формулы для полиномов Чебышева любой степени. Из этого рекуррентного соотношения видно, что коэффициент при старшей степени x k равен 2 k-1 .

    В MATLAB полиномы Чебышева можно вывести при помощи Symbolic Math Toolbox, обратившись к функции Maple, которая называется ChebyshevT и функции simplify (для вызова функций Mаple из MATLAB предназначена функция maple):


    Графики полиномов Чебышева

    Корни полинома Чебышева легко найти, решив уравнение

    из которого видно, что полином Tk(x) имеет ровно k различных корней, расположенных на отрезке [-1,1]:

    которые и следует выбирать в качестве узлов интерполирования. Корни полиномов Чебышева расположены симметрично относительно нуля на отрезке [-1,1] и неравномерно — чем ближе к краям отрезка, тем корни расположены плотнее.

    Максимальное значение модуля полинома Чебышева равно 1 и достигается в точках .

    Если мы положим

    для того, чтобы коэффициент при старшей степени полинома ?k(x) был равен 1 (по определению полинома ?k(x)), то получим, что

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

    т.е. полиномы Чебышева являются полиномами наименее уклоняющимися от нуля.

    Таким образом, выбор в качестве узлов интерполирования корней полинома Чебышева является наилучшим в смысле минимизации правой части оценки

    которая теперь приобретает вид:

    Продемонстрируем преимущество выбора корней полиномов Чебышева в качестве узлов интерполяции. Для примера будем интерполировать функцию ?(x) = sinx на отрезке [-1,1] полиномами различных степеней для равноотстоящих и чебышевских узлов и сравнивать получающуюся ошибку интерполяции, строя графики ошибки Ln(x) — sin(x). Для этого можно воспользоваться последовательностью команд, приведенной ниже, в которой следует изменять значение k (т.е. число узлов интерполяции).

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


    Ошибки интерполяции для 7 узлов


    Ошибки интерполяции для 10 узлов


    Ошибки интерполяции для 13 узлов

    Мы рассмотрели выбор чебышевских узлов, когда отрезок, на котором производится интерполирование функции, есть [-1,1]. Переход к общему случаю интерполирования функции на произвольном отрезке [a,b] не представляет никаких трудностей. Достаточно сделать линейную замену переменных, переводящую отрезок [-1,1] в отрезок [a,b]. Такая замена выражается следующей простой формулой:

    Тогда для произвольного отрезка [a,b] чебышевскими узлами интерполяции будут узлы, вычисляемые по формуле:

    где m = 0,1. k-1. Здесь k — число узлов интерполяции, т.е. k = n + 1, где n — степень интерполяционного полинома Ln(x).

    Оценка ошибки интерполяции для отрезка [a,b] приобретает вид:

    где

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

    на отрезке [-2,3]. Будем выводить график ошибки интерполирования для различного числа равноотстоящих и чебышевских узлов, для чего в приведенной ниже программе следует менять значение переменной k.

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


    Ошибки интерполяции для 7 узлов


    Ошибки интерполяции для 10 узлов


    Ошибки интерполяции для 13 узлов

    Сходимость интерполяционного полинома

    Важно определить, что мы понимаем под сходимостью интерполяционного полинома Ln(x) к интерполируемой функции ?(x).

    Говорят, что интерполяционный полином Ln(x) сходится к ?(x) в точке x, если

    и интерполяционный полином Ln(x) равномерно сходится к ?(x), если

    Отметим, что из поточечной сходимости не следует равномерная и, если нет поточечной сходимости, то нет и равномерной.

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

    Мы начнем изучение сходимости интерполяционного полинома с классического примера Рунге (1901г.). Рунге исследовал интерполяцию полиномами функции

    с равноотстоящими узлами на отрезке [-1,1] и доказал, что вблизи границ этого отрезка при x>0.72 погрешность интерполяции ?(x)-Ln(x) неограниченно увеличивается с увеличением степени интерполяционного полинома n.

    Проинтерполируем функцию Рунге r(x) на отрезке [-1,1], увеличивая число равноотстоящих узлов, и отобразим графически функцию r(x) и интерполяционные полиномы на одних осях, а погрешности интерполирования на других осях в одном графическом окне.

    В результате получаем, что погрешность интерполирования вблизи границ промежутка при |x|>0.72 растет с ростом степени интерполяционного полинома.


    Функция Рунге и интерполяционные полиномы (сверху), ошибка интерполяции (снизу).

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

    Рассмотрим еще один пример, исследованный Бернштейном в 1916г. Бернштейн рассматривал приближение функции ?(x)=|x| на отрезке [-1,1] интерполяционными полиномами с равноотстоящими узлами и показал, что в этом случае не будет даже поточечной сходимости ни в одной точке отрезка [-1,1], кроме ±1.

    Приблизим функцию ?(x)=|x| на отрезке [-1,1] интерполяционными полиномами с равноотстоящими узлами, последовательно увеличивая число узлов интерполирования, и построим график зависимости погрешности интерполирования ?(x)-Ln(x) для x=0.9 от степени интерполяционного полинома, т.е. график зависимости ?(0.9)-Ln(0.9) от n.

    В результате получаем, что в точке x=0.9 интерполяционный полином Ln(x) не сходится к функции ?(x)=|x|, т.е. нет даже поточечной сходимости, следовательно равномерной сходимости также нет.


    Зависимость ?(0.9)-Ln(0.9) от n для ?(x)=|x|.

    Приведем несколько классических теорем о сходимости интерполяционных полиномов, в которых имеется ввиду, что интерполяция осуществляется на бесконечной последовательности, состоящей из наборов узлов интерполирования (интерполяционных сеток):

    Здесь верхний индекс обозначает номер интерполяционной сетки, а нижний — номер узла.

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

    Теорема (Фабер).
    Для любой последовательности интерполяционных сеток найдется некоторая непрерывная функция ?(x), для которой последовательность соответствующих интерполяционных полиномов не сходится равномерно к ?(x).

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

    Теорема (Марцинкевич).
    Для каждой непрерывной функции ?(x) существует последовательность интерполяционных сеток, такая, что построенные по этой последовательности интерполяционные полиномы равномерно сходятся к функции ?(x).

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

    Если ?(x) целая функция, то тогда последовательность интерполяционных полиномов, построенных по любой последовательности сеток с узлами из отрезка [a,b], сходится равномерно к ?(x) на [a,b].

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

    Очевидно, что функция ?(x) непрерывна вместе со всеми своими производными на отрезке [-1,1] (да и вообще для любого x). Однако, если брать такую последовательность интерполяционных сеток, что все ее узлы принадлежат отрезку [-1,0], то тогда всегда Ln(x) ? 0 и для любого x > 0 никакой сходимости не будет.

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

    Теорема.
    Если у функции ?(x) существует ограниченная на отрезке [a,b] производная ?'(x), а последовательность интерполяционных сеток состоит из наборов чебышевских узлов, то последовательность соответствующих интерполяционных полиномов равномерно сходится к ?(x) на отрезке [a,b].

    Анализ применимости методов интерполяции и экстраполяции для решения задачи восстановления изображения Текст научной статьи по специальности « Математика»

    Аннотация научной статьи по математике, автор научной работы — Щерба Евгений Викторович

    Похожие темы научных работ по математике , автор научной работы — Щерба Евгений Викторович,

    Текст научной работы на тему «Анализ применимости методов интерполяции и экстраполяции для решения задачи восстановления изображения»

    ?АНАЛИЗ ПРИМЕНИМОСТИ МЕТОДОВ ИНТЕРПОЛЯЦИИ И ЭКСТРАПОЛЯЦИИ ДЛЯ РЕШЕНИЯ

    ЗАДАЧИ ВОССТАНОВЛЕНИЯ ИЗОБРАЖЕНИЯ

    Евгений Викторович Щерба (аспирант, e-mail: [email protected])

    Омский государственный технический университет

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

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

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

    При осуществлении криптографического анализа системы защиты канала передачи видеоинформации на основе схемы с разделением секрета (СРС) был поставлен вопрос о возможности восстановления исходного изображения на основе некоторого количества его проекций, т.е. некоторого сегмента исходного изображения [2]. Основной подход к решению данной задачи, предложенный в ряде работ, заключается в применении к восстанавливаемому изображению методов интерполяции и экстраполяции [3, 4]. Целью данной статьи является анализ возможностей этих методов в контексте безопасного применения системы защиты. Необходимость анализа также обоснована поиском метода образования проекций из исходного изображения, сводящего эффективность методов восстановления к минимуму.

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

    e(x, у) = f(x, у) — f(x, у I

    а средняя квадратичная ошибка (СКО) через ее квадрат, то есть дисперсию ошибки:

    Критерий минимума квадрата СКО (e ® min), используемый в данной статье для сравнения методов восстановления, является наиболее универсальным и распространенным критерием качества восстановления [5].

    1. Интерполяция на «равномерной сетке»

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

    По своей сути билинейная интерполяция представляет собой расширение линейной интерполяции для функций от двух переменных. Пусть необходимо найти значение функции h(x,y) в произвольной точке (x’, у). Значения функции h(x,y) в каждой из четырех точек, ближайших к точке (x’, у), являются известными. Поэтому искомое значение этой функции в точке с координатами (x’,у’) может быть получено по известным значениям в четырех соседних точках с помощью выражения:

    h (x’, у ) = ax + Ьу + cx у + d, (3)

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

    Альтернативой билинейной интерполяции на равномерной сетке может выступать метод интерполяции бикубическим сплайном (рис. 1в).

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

    Рис. 1. Пример интерполяции на «равномерной сетке»:

    1а — исходное изображение, 1б — результат билинейной интерполяции,

    1в — результат интерполяции бикубическим сплайном

    мальным. Естественный путь минимизировать отклонение V» — построить прогноз наилучший в среднеквадратичном смысле:

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

    1. Произвести М сплайн интерполяций для получения вектора значений Ь(х^,у), /’ = 0. М -1.

    2. Построить одномерный кубический сплайн по полученным значениям.

    3. Произвести сплайн интерполяцию искомого значения И(х,у)

    Бикубическая интерполяция сплайнами позволяет добиться минимума «равномерной сетке».

    є при интерполяции на

    2. Экстраполяция Пусть теперь необходимо найти значение функции И(х,у) в точке (х’, у ), которая лежит вне пределов области заданных значений И(х, у). В этом случае необходимо решать задачу экстраполяции. В некоторых случаях при экстраполяции изображений неплохие результаты могут быть получены с помощью линейного прогнозирования [6, 7]. Пусть ^> -последовательность измерений набора значений некоторой величины г, обозначаемого > и связанного с ней случайным шумом:

    Основная идея линейного прогнозирования заключается в линейном представлении некоторого истинного произвольного значения г* через последовательность значений ^>:

    Необходимо найти такие коэффициенты ё*а, чтобы отклонение V* в некотором смысле было мини-

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

    Рис. 2. Пример экстраполяции линейным прогнозированием: 2а — исходное изображение, 26-результат экстраполяции

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

    Существует ли способ ещё сильнее снизить эффективность представленных решений при восстановлении разрывов?

    Относительный размер разрыва (в долях от размера изображения)

    Для билинейной интерполяции

    Для бикубической сплайн-интерполяции

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

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

    Как выбрать метод интерполяции

    Большинство геометрических преобразований, таких как поворот, масштабирование или компенсация дрейфа используют или зависят от интерполяции данных. Также некоторые другие операции, например, извлечение профилей, могут работать со значениями между отдельными пикселями и, следовательно, использовать интерполяцию. Поскольку данные СЗМ снимаются в относительно редко расположенных точках по сравнению с измеряемыми деталями (полные изображения обычно содержат всего лишь сотни пикселей в высоту и ширину), используемые методы интерполяции могут стать критичными для правильного количественного анализа свойств данных. В Gwyddion реализовано несколько методов интерполяции [1] и в большинстве модулей, где она требуется, можно выбрать используемый метод.

    Здесь мы описываем принципы и свойства методов одномерной интерполяции. Все реализованные методы двумерной интерполяции поддерживают разделение переменных и, следовательно, сводятся к соответствующим методам одномерной интерполяции. В настоящий момент доступны следующие методы интерполяции:

    Интерполяция округлением (также называемая интерполяцией до ближайшего соседнего) – простейший метод, значения текущего местоположения округляются до целых и, таким образом, определяется ближайшее значение в точке с целыми координатами. Её степень многочлена = 0, регулярность C -1 и порядок 1.

    Линейная интерполяция между двумя ближайшими значениями. Значение z в точке с относительными координатами x получается с помощью уравнения

    где z 0 и z 1 — значения в предыдущей и следующей точке, соответственно. Степень многочлена 1, регулярность C 0 , порядок 2. Она идентична B-сплайну второго порядка.

    Кубическая интерполяция (точнее интерполяция Кея (Key) с a = ?1/2 который имеет наиболее высокий порядок интерполяции) также использует значения в точках перед предыдущей и после следующей z -1 и z 2 , соответственно. Другими словами оно имеет носитель длины 4. Значение затем получается по формуле

    — веса интерполяции. Степень интерполяции Кея равна 3, регулярность C 1 и порядок 3.

    Интерполяция по Шауму (точнее, интерполяция Шаума четвёртого порядка) также имеет носитель длины 4. Веса интерполяции —

    Степень полинома 3, регулярность C 0 и порядок 4.

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

    для k = -1, 0, 1, 2 , где r -1 = 1 + x , r 0 = x , r 1 = 1 ? x , r 2 = 2 ? x . Её порядок = 1.

    Однако, они применяются не напрямую к значениям функции, как выше, а к коэффициентам интерполяции, рассчитанным из значений функции [1]. Степень полинома 3, регулярность C 2 и порядок 4.

    Однако, они применяются не напрямую к значениям функции, как выше, а к коэффициентам интерполяции, рассчитанным из значений функции [1]. Степень полинома 3, регулярность C 0 и порядок 4.

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

    Источники

    [1] P. Thevenaz, T. Blu, M. Unser: Interpolation revisited. IEEE Transactions on medical imaging, Volume 10, Number 7, July 2000, 739

    23690 просмотра

    5 ответа

    6949 Репутация автора

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

    1. CV_INTER_NN (по умолчанию)
    2. CV_INTER_CUBIC
    3. CV_INTER_AREA

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

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

    Тогда мой вопрос: каковы плюсы и минусы каждого метода интерполяции? Чем они отличаются и какую мне использовать?

    Ответы (5)

    21 плюса

    61941 Репутация автора

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

    Кубическая интерполяция (вероятно, фактически «бикубическая») использует одну из многих возможных формул, которые включают несколько соседних пикселей. Это намного лучше для сжатия изображений, но вы по-прежнему ограничены в том, сколько вы можете уменьшить без потери информации. В зависимости от алгоритма, вы можете уменьшить свои изображения на 50% или 75%. Основным недостатком этого подхода является то, что он намного медленнее.

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

    Обновление: эта ссылка дает более подробную информацию (включая пятый тип, не включенный в ваш список):

    10 плюса

    1788 Репутация автора

    Используемый метод интерполяции зависит от того, чего вы пытаетесь достичь:

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

    Метод CV_INTER_NN на самом деле является ближайшим соседом, это самый простой метод, и вы получите более острые края (фильтр нижних частот применяться не будет). Однако этот метод просто похож на «масштабирование» изображения, без визуального улучшения.

    1 плюс

    81841 Репутация автора

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

    Извините, что нет правильного ответа — поэтому есть выбор

    6 плюса

    749 Репутация автора

    Алгоритмы: (описания взяты из документации OpenCV)

  • INTER_NEAREST — интерполяция ближайшего соседа
  • INTER_LINEAR — билинейная интерполяция (используется по умолчанию)
  • INTER_AREA — повторная выборка с использованием отношения площади пикселя. Это может быть предпочтительный метод для прореживания изображений, поскольку он дает результаты без муаров. Но когда изображение увеличено, оно похоже на метод INTER_NEAREST.
  • INTER_CUBIC — бикубическая интерполяция в окрестности 4×4 пикселей
  • INTER_LANCZOS4 — интерполяция Ланцоша в окрестности 8×8 пикселей

Если вы хотите больше скорости, используйте метод Nearest Neighbor.

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

Вы можете найти подробный анализ скорости сравнения здесь

Ниже приведено сравнение скорости на изображении 400 * 400 пикселей, полученном по вышеуказанной ссылке.

Читайте так же:

  • Как сделать квартиру по фэн шую Как обустроить дом по принципам фэн-шуй, если вы в начале пути Вы точно слышали о фэн-шуй, но вряд ли вдавались в подробности этого понятия. Фэн-шуй — это древняя китайская практика, […]
  • Как научиться продавать товары Как научиться продавать товары или услуги? В этой статье мы поговорим о том, как научиться продавать товары и услуги, и что нужно для того, чтобы стать успешным продавцом. Как утверждают […]
  • Как называется человек который любит издеваться над собой Как называется человек который любит издеваться над собой Людей, которые любят одиночество, обычно называют интровертами. Это те самые персонажи мемов с теплым пледом, чашкой горячего кофе […]
  • Обычаи народов кубани википедия Кубанские казаки – не русские? Как передает издание «Живая Кубань», по мнению некоторых кубанских казаков, результаты переписи 2010 года в отношении количества казаков в регионе не […]
  • Что делать если фотоаппарат фотографирует мутно Выходят мутные фотографии, можете что-то посоветовать? На страницу 1 , 2 След. Для печати Автор Сообщение AlexY [ ] Местный житель Сообщения: 1809Откуда: минск […]
  • Коллекционные ножи история и традиции Перечень Тестовых Серий Страница 1 из 1 [ Сообщений: 2 ] Похожие темы Автор Ответы Просмотры Последнее сообщение Продаю рейки из серий "Севастополь" и "Повелитель морей" 04 ноя […]

Leave a Reply

Ваш адрес email не будет опубликован. Обязательные поля помечены *