[ViKo 1]

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

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

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

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

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

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

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

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

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

[thermit 1]

des00:

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

 

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

[NiceParty 0]

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

 

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

 

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

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

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

 

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

[Tanya 4]

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

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

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

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

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

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

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

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

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

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

[_Ivana 0]

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

[Pavel_SSS 0]

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

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

[ViKo 1]

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

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

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

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

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

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

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

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

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

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

[sup-sup 0]

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

 

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

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

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

Изменено 8 апреля, 2012 пользователем sup-sup

[ViKo 1]

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

[_Ivana 0]

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

 

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

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

 

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

[ViKo 1]

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

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

[_Ivana 0]

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

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

 

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

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

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

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

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

 

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

[kuzis 0]

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

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

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

Мораль:

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

[thermit 1]

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

 

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

Изменено 9 апреля, 2012 пользователем thermit

[_Ivana 0]

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

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

Мораль:

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

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

 

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

 

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

 

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

Изменено 9 апреля, 2012 пользователем _Ivana