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

[_Ivana]

Пару дней назад пришлось вникнуть в азы ЦОС на примере ресемплинга. Почитал пару-тройку страничек в инете, про двойной апсемплинг, оконные функции, полиномы Лагранжа-Фарроу и т.п. И придумал свой алгоритм Без таблиц, на чистой математике. По объему операций существенно меньше Фарроу. Реализовал его, как обычно, сначала на 1С Посмотрел графики. Потом перевел в целочисленную математику и с помощью коллеги наваял программку - ресемплер wav файлов. С заданием частоты ресемплинга и выбором варианта - своего или Фарроу.

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

ЗЫ поскольку я совершенный дилетант в сабжевом вопросе, я вполне допускаю что этот алгоритм уже давно придуман до меня. Но навскидку я не нашел ничего похожего.

Графические примеры работы алгоритмов: точки 50, 70, 20, края диапазона добиты нулями. График - ось абсцисс вниз, ординат - вправо.
Фарроу:

CODE

      *--- 0
     *
    *
   *
   *
  *
  *
   *
   *
    *
      *--- 0
          *
              *
                   *
                        *
                             *
                                   *
                                        *
                                             *
                                                   *
                                                        *--- 50
                                                            *
                                                               *
                                                                  *
                                                                     *
                                                                        *
                                                                          *
                                                                           *
                                                                            *
                                                                            *
                                                                            *--- 70
                                                                        *
                                                                    *
                                                               *
                                                          *
                                                     *
                                                *
                                          *
                                    *
                               *
                          *--- 20
                      *
                   *
                 *
              *
            *
           *
         *
        *
      *
      *--- 0
     *
     *
    *
    *
    *
    *
     *
     *
     *

Мой алгоритм:

CODE

      *--- 0
     *
     *
    *
   *
  *
  *
  *
  *
   *
      *--- 0
         *
             *
                  *
                       *
                             *
                                   *
                                         *
                                               *
                                                   *
                                                        *--- 50
                                                           *
                                                               *
                                                                  *
                                                                     *
                                                                        *
                                                                          *
                                                                            *
                                                                            *
                                                                            *
                                                                            *--- 70
                                                                         *
                                                                      *
                                                                 *
                                                           *
                                                     *
                                               *
                                         *
                                   *
                              *
                          *--- 20
                      *
                   *
                 *
              *
            *
           *
         *
        *
       *
      *--- 0
     *
    *
    *
    *
    *
     *
     *
     *
     *

За качество обоих графиков извиняйте - они в псевдографике с грубым "разрешением", на самом деле они более красивые

Сообщение отредактировал _Ivana - Apr 7 2012, 12:31

[_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

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

 

[Михаил_K]

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

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