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

[ViKo]

Какая-такая -"Эта"?
Вы меня убиваете (без Котельникова).
Функция номер раз - кусочно-линейная.
Функция номер два - кусочно-квадратичная.
Дальше сами... Единственность опровергнута? Ваша.

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

[thermit]

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

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

[NiceParty]

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

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

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

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

[Tanya]

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

1.Котельников никак и никого не учил оцифровывать.
2. Ни про какие частоты в разложении в ряд Фурье интерполяции нет никакого дела. Мухи отдельно. Ладно?
3. Изломы имеются только в точках пересечения прямых. Если новую функцию там не определять, то какие изломы?
Вы же сомневаетесь в их существовании для кусочно-квадратичной.
Так объясните, что есть та самая правильная интерполяция?
Лучше формулой. А то я Ваши слова плохо понимаю.

[_Ivana]

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

[Pavel_SSS]

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

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

[ViKo]

1. Котельников никак и никого не учил оцифровывать.
2. Ни про какие частоты в разложении в ряд Фурье интерполяции нет никакого дела. Мухи отдельно. Ладно?
3. Изломы имеются только в точках пересечения прямых. Если новую функцию там не определять, то какие изломы?
Вы же сомневаетесь в их существовании для кусочно-квадратичной.
Так объясните, что есть та самая правильная интерполяция?
Лучше формулой. А то я Ваши слова плохо понимаю.

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

Эскизы прикрепленных изображений

 

[sup-sup]

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

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

Сообщение отредактировал sup-sup - Apr 8 2012, 17:59

[ViKo]

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

[_Ivana]

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

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

CODE

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;
}

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

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

[ViKo]

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

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

[_Ivana]

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

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

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

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

[Михаил_K]

_Ivana. Интересно было бы посмотреть на спектр сигнала полученного вашим интерполятором, при интреполяции в несколько раз, при условии на вход подается синус, частота которого близка к 1/2 частоты дискретизации. Например 0.49 частоты дискретизации. Оценить уровень аллиаса, который при этом получится.
А если серьезно...
Как то давно, на первом курсе института был у меня такой случай. Выполняли достаточно простенькое задание. Зову препода - типа сделал. Он подходит проверять. Вводит начальные значения. Получает результат. Вводит другие значения - программа отрабаывает не правильно. Ну я соответственно исправляю. Опять зову. Он опять вводит несколько вариантов исходных данных. Программа в очередной раз ломается. Я опять исправляю. Опять зову. Опять вводит несколько вариантов. Программа работает. Препод в задумчивости.. Пробует еще несколько вариантов. Программа работает. Препод задумчиво, со звуком "ХМ" лезет в код. Изучает внимательно. Вводит очередные исходные данные - программа ломается. На что он с криком "Ура" заставляет снова думать.
Мораль:
Вы бы описали свой алгоритм, а люди бы посмотрели на него, и сказали бы свое мнение. Не исключаю, что то, что вы придумали - уже известно, и имеет определенные границы применения, либо определенные "грабли".

[thermit]

http://electronix.ru/forum/index.php?showt...t&p=1046889

Собственно,мнение тут одно: Все уже давно придумано.

Сообщение отредактировал thermit - Apr 9 2012, 14:02

[_Ivana]

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

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

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

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

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

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

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

Сообщение отредактировал _Ivana - Apr 9 2012, 18:40

Эскизы прикрепленных изображений