Jump to content
    

Придумал алгоритм интерполяции. Протестируем результаты?

Какая-такая -"Эта"?

Вы меня убиваете (без Котельникова).

Функция номер раз - кусочно-линейная.

Функция номер два - кусочно-квадратичная.

Дальше сами... Единственность опровергнута? Ваша.

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

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

Номер два - аналогично, может быть, не так очевидно, но гарантированно...

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

Share this post


Link to post
Share on other sites

des00:

все переходит к набору сумматоров + сдвиги

 

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

Share this post


Link to post
Share on other sites

это же просто и уже обсуждаллсь на форуме, умножьте все коэффициенты на 6, в результате этого коэффициенты фильтра будут 1,2,3,6, за счет операции рекомбинации, аналогичной описанной в статье, все переходит к набору сумматоров + сдвиги. что просто реализуется на любой платформе. остается только рассчет полинома. как уже сказал 3 умножения. В кол-ве сложений ошибся, признаюсь. Считать, сколько их там, с учетом оптимальной рекомбинации лень.

 

в результате такой "моидификации", коэффициент усиления преобразования интерполятора будет 6. легко переводиться в 6/8. И совсем привередливым, кому хочеться получить 1цу, приводиться простым делением через умножение.

 

В идеале, конечно хотелось бы получить Ку=1.

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

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

 

P.S. Мне считать не лень, но я не смог увидеть преимуществ в кол-ве операций. Может, неправильно считал...

Share this post


Link to post
Share on other sites

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

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

Номер два - аналогично, может быть, не так очевидно, но гарантированно...

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

1.Котельников никак и никого не учил оцифровывать.

2. Ни про какие частоты в разложении в ряд Фурье интерполяции нет никакого дела. Мухи отдельно. Ладно?

3. Изломы имеются только в точках пересечения прямых. Если новую функцию там не определять, то какие изломы?

Вы же сомневаетесь в их существовании для кусочно-квадратичной.

Так объясните, что есть та самая правильная интерполяция?

Лучше формулой. А то я Ваши слова плохо понимаю.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

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

А Вы знаете целевую функцию? Зачем Вам тогда интерполяция - просто вычислите значения функции в нужных точках...

Share this post


Link to post
Share on other sites

1. Котельников никак и никого не учил оцифровывать.

2. Ни про какие частоты в разложении в ряд Фурье интерполяции нет никакого дела. Мухи отдельно. Ладно?

3. Изломы имеются только в точках пересечения прямых. Если новую функцию там не определять, то какие изломы?

Вы же сомневаетесь в их существовании для кусочно-квадратичной.

Так объясните, что есть та самая правильная интерполяция?

Лучше формулой. А то я Ваши слова плохо понимаю.

1. Без комментариев :)

2. Есть очень тесная связь, для ЦОС.

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

Вместо формул (я же уже дал ссылку, там русским по белому написано!) картинку покажу.

post-10362-1333903108_thumb.jpg

Share this post


Link to post
Share on other sites

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

 

После интерполяции должен остаться такой же спектр в исходной полосе. А за ее пределами нулевой.

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

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

Edited by sup-sup

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites

Спасибо за дельные рекомендации, померю по возможности.

 

ЗЫ to all - вы меня только пожалуйста не бейте :) Я тут ещё почитал немного интернетов, и понял что я придумал так называемую "интерполяцию сплайнами Катмулла-Рома", точнее один из её вариантов :) И ещё и проанализировал её в сравнении с Лагранжем по максимальной и средней ошибке :) Я действительно не знал об этом раньше (я бы до таких фамилий никогда не додумался :) ), но раз дело такое - как обещал, выкладываю код, сравните по быстродействию с Фарроу:

SHORT InterpolateKatmullRom(int t, SHORT y0, SHORT y1, SHORT y2, SHORT y3)
{	int y, a0, a1, a2, a3;

y = y2 - y1;
a0 = y1;
a1 = (y2 - y0)>>1;
a3 = (y3 - y0);
a3 = (a3 - y)>>1;
a3 = (a3 - y);
a2 = y - a3 - a1;

y = a3*t;
y = y>>16;
y = (y + a2)*t;
y = y>>16;
y = (y + a1)*t;
y = y>>16;
y =  y + a0;

if (y > 32767) y = 32767;
else if (y < -32768) y = -32768;

return (SHORT)y;
}

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

 

Еще раз прошу прощения у общественности за внесенный переполох и самонадеянную претензию на ноу-хау :) В любом случае спасибо, это была интересная практика!

Share this post


Link to post
Share on other sites

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

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

Share this post


Link to post
Share on other sites

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

Хорошо, пусть будет ограничение :)

 

ЗЫ есть у меня ещё одна идейка :) Надо бы её проверить теперь, благо, спасибо Термиту, я уже знаю как навскидку проверять разные алгоритмы интерполяции, и проверялка уже написана. Только хорошо бы выполнить 4 условия:

1) формализовать её сначала математически а потом в коде

2) победить Фарроу по отклонениям

3) оптимизировать по операциям чтобы было в разумных пределах

4) самое главное - чтобы это потом не оказалось методом какого-нибудь Фермана-Зингельшухера :)

 

Начинаю серию №2, надеюсь реализовать её тоже.

Share this post


Link to post
Share on other sites

_Ivana. Интересно было бы посмотреть на спектр сигнала полученного вашим интерполятором, при интреполяции в несколько раз, при условии на вход подается синус, частота которого близка к 1/2 частоты дискретизации. Например 0.49 частоты дискретизации. Оценить уровень аллиаса, который при этом получится.

А если серьезно...

Как то давно, на первом курсе института был у меня такой случай. Выполняли достаточно простенькое задание. Зову препода - типа сделал. Он подходит проверять. Вводит начальные значения. Получает результат. Вводит другие значения - программа отрабаывает не правильно. Ну я соответственно исправляю. Опять зову. Он опять вводит несколько вариантов исходных данных. Программа в очередной раз ломается. Я опять исправляю. Опять зову. Опять вводит несколько вариантов. Программа работает. Препод в задумчивости.. Пробует еще несколько вариантов. Программа работает. Препод задумчиво, со звуком "ХМ" лезет в код. Изучает внимательно. Вводит очередные исходные данные - программа ломается. На что он с криком "Ура" заставляет снова думать.

Мораль:

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

Share this post


Link to post
Share on other sites

_Ivana. Интересно было бы посмотреть на спектр сигнала полученного вашим интерполятором, при интреполяции в несколько раз, при условии на вход подается синус, частота которого близка к 1/2 частоты дискретизации. Например 0.49 частоты дискретизации. Оценить уровень аллиаса, который при этом получится.

Запросто. Чуть позже, как будет время.

Мораль:

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

В данный момент размышления следующие. Фарроу (Лагранж 3-го порядка) - это имхо по сути (хотя многие могут со мной не согласиться) тот же кубический сплайн. Локальный, определяемый для 4-х точек, но действующий только на средний интервал из 3-х. Точно так же, как и сплайны Эрмита, например. Тот факт, что Лагранж при построении проходит через все 4 точки, не дает значения интерполирующей функции в левом и правом интервалах, поскольку при интерполяции собственно самих этих боковых интервалов (когда они являются центральными) полином проходит совершенно не так, как проходит в случае если интервал является правым или левым относительно центрального. Значит нельзя считать условие прохождение полинома через крайние точки самым оптимальным с точки зрения построения сплайна. Я придумал (а Катмулл и Ром до меня) другие условия: сплайн проходит через 2 точки и имеет определенные производные в них же, так чтобы полученная функция имела непрерывную первую производную. Сначала я придумал считать значение этой производной, как тангенс угла-биссектрисы исходных двух (словами трудно объяснить, надо на графике показывать). Только что проверил этот вариант - при малых дискретизациях ошибка выше Катмулла-Рома, при увеличении начиная где-то с 12 точек почти полностью сливается с Катмуллом-Ромом (график ниже). Но само значение производной рассчитывается через тангенсы-арктангенсы и достаточно сложно. Это и была моя вторая идея, которую я проверил только что. А потом я придумал считать производную как тангенс наклона соседних точек - собственно то, что потом узнал как Катмулла-Рома.

 

ЗЫ сейчас я пытаюсь построить интерполяцию кубическим сплайном, зная точные значения производной искомой функции в точках отсчета. И сравнить её с Фарроу. Если она окажется лучше (а я на это рассчитываю), тогда мои предположения насчет неидеальности условия на сплайн Лагранжа-Фарроу верны, и может быть можно будет придумать ещё какой-нибудь вариант расчета производных по заданным отсчетам, который приводил бы к бОльшей точности чем Фарроу и был бы не очень громоздок.

 

Собственно, на текущий момент мысли таковы. А снизу - график ошибки Фарроу, Катмулла-Рома и метода "биссектрисы" (как я его называю :) ) И обещанный ресемплинг синуса 3920Гц с исходных 8000 до 44100 :)

 

Upd: добавлен график сравнения ошибок 4-х методов: зеленый - Катмулла-Рома, синий - Фарроу, желтый - полиномами Лагранжа 4 степени, красный - кубическими сплайнами при условии точного знания производной интерполируемой функции во точках отсчета. Получается, красный - теоретически возможный предел для сплайнов 3-го порядка с условиями по производным в точках отсчета. Но достаточно хороший предел, надо сказать, можно к нему и постремиться :) Осталось только придумать красивую и точную процедуру угадывания производных. Я придумал пока две - одна оказалась Катмуллом-Ромом, другая - сложнее неё и не лучше по результатам. Может придумаю ещё :)

post-66710-1333983043_thumb.jpg

post-66710-1333985978_thumb.jpg

post-66710-1333996855_thumb.jpg

Edited by _Ivana

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
×
  • Create New...