Сейчас посмотрю синусоиды на глаз, и попробую ещё кое-что. Блин, мой косяк!!! Маза-фаза.... Предыдушим полиномиальным спектрам не верить! буду искать ошибку...

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

А во-вторых, смотря для чего эту интерполяцию использовать.
Для апсемплинга от 48кГц к 192кГц она не подходит. Поэтому используют стандартные sinc-и, но они требуют существенно большего объема вычислений.
Если же использовать интерполяцию для ресемплинга аудио, например от 44100 к 48000, то результат получается вполне сносным.
Я отслушивал результаты подобного ресемплинга. Для ряда применений этого может оказаться вполне достаточным.

Попросите топикстартера сделать спектрограммы ресемплинга 8кГц синуса из 44100 (чтобы соблюсти пропорцию частоты сигнала и дискретизации) в 48000 по разным вариантам полиномиальной интерполяции. Думаю, это будет интересным.

P.S. Пока писал, топикстартер уже нашел у себя ошибку

Вроде теперь на глаз все без выбросов (при попытке увеличить точность в интеджерах вылетал за их пределы).
Новые графики: Катмулл-Ром, Фарроу и линейка. Надеюсь, это будет больше похоже на правду

А теперь сделайте, чтобы этих палок не было!
"вы знаете какое-нибудь другое мирное русло, в которое я мог бы направить свой избыток энергии, и которое было бы не менее интересно и увлекательно?" По-моему - очень достойное занятие.

Каких палок? Выбросов на синусоиде? Сделал уже. И спектры привел уже по интерполяции без выбросов. У меня алгоритм в целых числах считает, и до последнего времени я использовал 15бит точности задания времени, все было хорошо, но мне пожадничалось и захотелось 16, я добавил разрядов, а ваш пример как раз показал что надо оставить 15бит Спасибо Вам за такой тест на ошибку Теперь все красиво.
А насчет отсутствия палок в спектре, боюсь тут я бессилен Судя по картинкам синусоиды, интерполируется она настолько хорошо, насколько может по данным алгоритмам.

Нет, лишних палок в спектре. Должна остаться только одна 1kHz.

А что синус такой кривой? Непорядок.

Ну насчет палок в спектре и кривоты синуса - повторюсь, кажется это уже не ко мне. По 4 точкам при 5 отсчетах на период что Катмулл-Ром что Фарроу интерполируют именно так. Это же вам не синк 64-точечный в конце концов!

5 отсчетов на период здесь не при чем. Как уже говорил, они однозначно определяют функцию.
Насчет кривого синуса - очень сомнительно, что это лучшее, на что способна полиномиальная интерполяция.
А насчет палок - если вам достаточно такого звука, то можно успокоиться. Гармоники... все равно ухом не расслышать. Ну, будет чуть звонче с гармониками... Но мне, кажется, вы не захотите остановиться на сделанном. При вашей-то энергии.

upd. Посмотрел на линейную интерполяцию. Да, пожалуй полиномами не вытянуть синус по пяти точкам.

А вот тут вы и становитесь заложником собственных убеждений! ОНИ однозначно определяют функцию, только если эти ОНИ - ВСЕ точки выборки! И причем тут как раз именно то. что при полиномиальной интерполяции мы считаем значение только по N окрестным - в данном случае всего 4-м точкам Можно посчитать полином хоть по 20 точкам. но во первых это сложнее. а во вторых - ХУЖЕ по результатам - в силу математики осцилляций и потери точности при расчетах больших степеней.

А насчет звука - повторю предложенное 7 страниц назад - присылайте вавку, ресемплю вам её и послушаете на какой хотите аудиофильской аппаратуре Смею предположить, что результат "кривого синуса" вас может сильно удивить

А по скольким будет НЕ хуже, а ЛУЧШЕ? Как насчет восьми?

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

P.S. "Даю установку" - CIC, CIC, CIC!

Вам уже писали, что через эти 5 точек можно провести бесконечное множество функций. Так что никакой однозначности тут нет.

http://www.exponenta.ru/educat/systemat/ch...shin/theory.asp

А насчет пилы и прямоугольника - тестирование на аппаратуре высокого класса показывает явно недостатки линейной интерполяции, Фарроу и Катмулл-Ром я не отличаю от оригинала, хотя знакомый аудиофил говорит только что-то про "размытость сцены" , а Лагранжем 4-го порядка и он доволен

"Понтовался" ваш аудиофил. Откуда в монозвуке "сцена" и ее размытость?

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

Когда ж вы успели? Еще час назад ваш алгоритм "колбасило неподецки"? Вы такой результат "аудиофилу" подсунули? Тогда он много нового мог услышать!

Предложение перестать понтоваться и внимательно читать написанное - в силе
Час назад - колбасило. А вчера, позавчера и ранее - не колбасило Потому что только сегодня с ура я решил вдруг его ещё "усовершенствовать". Так что результат подсовывался вполне корректный.

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

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

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

А по поводу интерполяции полиномами больших степеней - вспомнил былое ... Как году так в 92-м, во время обучения в универе, развлекался следующим образом - написал программу на Паскале, с выводом графиков (решение системы 10*10 конечно вызывал библиотеку ). Задаю 10 точек - точно по прямой линии. итоговый полином - прямая линия. Чуть-чуть смещаю одну из точек вверх или вниз, буквально на немножко - и начинается такое, что просто было страшно. Реально на самом деле страшно становилось - от осознания того факта, к каким ужасным последствиям может приводить одна малейшая неточность.

Если речь о ВЧ-палках, то из любопытства синком попробуйте. Ширину синка возьмите в районе точек 20-100, в зависимости от точек на период синуса (при 2.5 - 100, чем больше точек в синусе, тем уже синк).

Это так, для понимания "бессилен". По поводу боольшого кол-ва вычислений, ясен пень

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

Синк пока не пробовал, попробую. Для начала на своем 1С симуляторе
Но я верю что там будет все хорошо и при 2 отсчетах на период. Синк же ведь такой баян, который можно растянуть насколько размаха рук хватит И точность можно повышать до любых значений, просто растягивая этот баян шире Кстати, интересно будет посмотреть на работу синка при 1.3 точки на период А при локальных алгоритмах, которые принципиально оперируют только несколькими окрестными точками, совершенно другая ситуация - и это понятно всему здравомыслящему человечеству

Кстати, на примере Катмулла-Рома и Фарроу, я понял еще одну очевидную вещь - можно и к Лагранжу 4-го порядка приделать его "близнеца" - Катмулла-Рома 4-го порядка, с заданием условий по производным в конечных точках, чтолько точек будет не 4 а 5. И к Лагранжу любого порядка можно таким образом приделать своего Катмулла-Рома того же порядка. Причем, я предполагаю что математика расчета будет проще по сравнению с Лагранжем. Также предполагаю что точность в свою очередь будет похуже. Вот это я и проверю в 1С

2 _Ivana,
http://ru.wikipedia.org/wiki/Сплайн_Эрмита

Спланы Катмулла-Рома частный случай Эрмита. попробуйте О результатах расскажите

Вы сперва разберитесь в т.Котельникова и сотоварищей. Чтоб такие наполеоновские планы на всеобщее оборзерние выставлять

Даже для ровно 2.0 точек на период нет никакой гарантии достоверности. Для 2.1 можно, но ширина синка от 20 периодов и чем их больше, тем меньше ВЧ гармоник. Вобщем, чем ближе к 2.0 тем шире нужен синк. Меньше 2.0 сделать принципиально невозможно.

2 SFx я уже пробовал и с известными значениями производных (график ошибки приводил), и угадывать их по другим алгоритмам. Если вашу википедийную ссылку применить к равномерным интервала дискретизации, то среднее арифметическое производных на двух соседних отрезках даст именно Катмулла-Рома. Более того, к нему же приводит попытка интерполяции этих 3-х точек параболой. То что там называется "кардинальным сплайном" я конечно тоже попробую, но навскидку мне кажется результаты будут хуже чем просто Катмулл-Ром. Я пробовал несколько вариантов "угадывания" производной в средней точке по 3-м точкам (используя информацию о значении средней), но на практике все они или были сильно хуже, или асимптотически стремились к Катмуллу-Рому, который информацию об этой средней точке не использует!

GetSmart да-да, вы правы. Видимо я злоупотребляю смайликами в своих постах, и становится непонятно когда а шучу. Хотя после шутки в виде предложения интерполировать по 4-м локальным точкам синус частотой 0.49 частоты дискретизации я думал мне тоже можно предложить попробовать интерполировать синком 0.7 частоты дискретизации

Попробовал т.н. "кардинальный сплайн" - результаты похожи на то, что мы вводим в Катмулла-Рома некий коэффициент погрешности, который при равенстве нулю дает самый лучший результат. Я не понял его глубокого смысла.
Собственно, если у кого есть идеи как ещё можно рассчитать производную в точке по значениям её и окрестных отсчетов - вэлкам, буду проверять.
А пока сравнительные графики ошибки Лагранжа 3-го и 4-го порядков и Катмулла-Рома 3-го и 4-го порядков. Если при расчете последнего я не ошибся, то его результат довольно странный.

Спасибо за поддержку в нужный момент Если я не ошибаюсь, то мне все-таки удалось победить Фарроу на отдельно взятой территории. Кубическим сплайном, как ни странно Так что объем вычислений примерно тот же. Более того, я могу влиять на степень отклонения от Фарроу от нулевой до например представленной на картинке и больше А при малых ошибках, как вы правильно заметили, и погрешности округлений будут сравнимы, и другие источники подтянутся. Добавил рядом график с шагом поменьше, чтобы было более понятно поведение ошибки.

upd: а ещё вот такие интересные картинки могу получить. То есть, я могу достичь любого предела абсолютной ошибки за меньшее количество отсчетов на период чем Фарроу

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

Картина пикселями "кубический сплайн Фермана-Зингельшухера (красный) побеждает Фарроу (зеленый) на всем поле, требуя при этом примерно столько же вычислений"

И снова здравствуйте
И снова я придумал очередной алгоритм Точнее - несколько, но последний настолько меня вдохновляет, что я снова пишу сюда.
Сразу про количество операций. Допустим в сравнении с Фарроу - Лагранжем 3. Хотя при самом подходе к расчету количества операций выяснились забавные "особенности" - некоторые считают извлечение квадратного корня и сложение отдельными операциями, хотя понятно что они требуют существенно разных машинных ресурсов, а другие считают например что Лагранж - 3 рассчитывается "за 3 умножения и 3 сложения", хотя ровно столько требуется для расчета его полинома, а расчет коэффициентов наверное считается что не занимает операций совсем Я рискну высказать свое мнение насчет количества операций и в Фарроу и моего алгоритма. Итак,

Фарроу:
1 умножение на константу
2 сдвига (умножения/деления на степени 2)
3 умножения на переменную
12 сложений (одно на приведение параметра)

Мой алгоритм:
1 умножение на константу
3 сдвига (умножения/деления на степени 2)
3 умножения на переменную
12 сложений

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

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

И конечно же графики ошибки моего алгоритма (красный) в сравнении с Фарроу (зеленый) и Лагранжем 4-го порядка (синий):


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

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

Не надо никаких спектров. В источниках, где как-то рассматриваются интерполяторы, обычно укзывается 2 характеристики:
- Набор АЧХ и ФЧХ в зависимости от значения задержки
- Сложность

Эта статья вроде была в открытом доступе где-то
http://ieeexplore.ieee.org/xpl/login.jsp?t...%2F01203780.pdf

Успехов



"...Доктора,
Профессора,
Медицинская сестра,
Академик по Китам,
Академик по Котам,
С ними семьдесят студентов,
Тридцать пять корреспондентов,
Два редактора с корректором,
Кинохроника с прожектором,
Юные натуралисты
И другие специалисты. "

Timmy,

Точно утверждать пока не возьмусь, но мне кажется что и в моем случае этот метод сработает. Кстати, я ещё немножко оптимизировал свой алгоритм - убрал один сдвиг.

Это графики максимального модуля отклонения (максимальной ошибки), рассчитанные экспериментальным путем.

Fat Robot
Спасибо за ссылку, попробую разобраться.

ЗЫ: я очень хорошо понимаю и разделяю Ваше насмешливо-несерьезное отношение к званиям, регалиям и авторитетам. Но среди них по статистике тоже иногда попадаются достаточно неглупые люди, в моем случае их оказалось примерно 2.5 человека И мне было интересно и познавательно с ними пообщаться. А насчет перечисленного Вами видового разнообразия - то оно в не меньшей мере представлено и на этом форуме Хочу спросить к какой категории вы относите себя, но из благодарности за помощь и ссылку воздержусь А с другой стороны - куда мне было ещё обращаться? Где вот лично Вы были все предыдущие 9 страниц моих эпических плаваний?

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

ok!

_Ivana,

1. Я был занят другими делами, не менее интересными, чем обсуждение интерполяторов на интернет-форуме. Только недавно стал на перископную глубину подниматься. Извините, что подвел Вас. Целых 9 страниц... Не ожидал, что Вы такой плодовитый.

2. То, что Вы используете все возможные способы получения информации, - это прекрасно и похвально. Серьезно. А вот то, что Вы напускаете туману "кое-что сделал, но не скажу" при обсуждении - это не серьезно и детский сад.

3. Вы очень глубоко смотрите и видите то, чего нет. Это цитата из детского стиха:Борис Заходер "Кит и Кот". Не более того.

И да.. Освойте Матлаб. Как инструмент, он весьма хороший.

Успехов

_Anatoliy, спасибо. Скиньте ваш номер сотового в личку, положу на него 300р (если не ошибаюсь).

Fat Robot

Я не настолько наивен и меркантилен, чтобы лелеять надежду получить от этого материальную выгоду. Но чего я действительно не хочу - это чтобы написанное в интернете на весь мир кто-то бы выдал за свои разработки. Я понимаю что такая позиция не лучшим образом свидетельствует о моем моральном облике. Я помню стих 74 Дхаммапады ( http://dhamma.ru/canon/kn/dhp/dhammapada.htm ), глава о глупцах:

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

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

Спасибо,этого не нужно.Мне было бы гораздо интересней ознакомиться с Вашим алгоритмом.

так вот как оказывается называется реализация интерполятора которую реализовал давным давно %)

Обещанная банальная и наивная статья
Здоровая и конструктивная критика да и прочие впечатления приветствуются

Посмотрел частотные характеристики фильтра Фарроу третьего порядка и сплайна вида [1/5, 1/5]. Привожу графики АЧХ и ГВЗ для временного сдвига 0.25 дискрета. Смотрел при разных значениях x и думаю, в этом что-то есть, интересно, что скажут Гуру.

UPD: Привожу группы характеристик АЧХ, ФЧХ, ГВЗ для Фарроу 3 и [1/5, 1/5] при изменении x от 0 до -1 для Фарроу и от 0 до 1 для сплайна.

ToR_TDA спасибо что подключились и проводите сравнительный анализ. Я пока правда с трудом понимаю связь АЧХ и ФЧХ с алгоритмами интерполяции, поэтому ничего дельного сказать не могу Только вижу что Фарроу чуть хуже по линейности АЧХ, существенно лучше по линейности ФЧХ и примерно так же по ГВЗ. Как интерпретировать эти данные? Это показатели некоего фильтра, которым становится интерполятор, при условии смещения сетки дискретизации без изменения её шага? И в идеале должна быть линейная АЧХ и ФЧХ, а "фильтр" не должен вносить изменений в сигнал?
ЗЫ в какой программе Вы анализируете и строите эти графики?

Я то же не спец в этом, но представляю себе характеристику идеалного интерполятора в следующем виде: АЧХ - прямая линия (без наклонов и неравномерности), ФЧХ - линейна т. е. прямая линия с постоянным наклоном (если смотреть линейный масштаб по частоте), ГВЗ - это показатель (если можно так говорить) нелинейности ФЧХ и временного сдвига. Таким образом, чем лучше интерполятор, тем более его характеристики приближены к идеальным и все это должно выполняться при разных значениях x.
По поводу АЧХ - Фарроу хуже, что видно из графиков, на счет ФЧХ и ГВЗ (они напрямую и наглядно связаны) мне не совсем ясно, но вроде как Фарроу лучше.
Я использую программу MicroCAP и в ней собрал два фильтра Фарроу отсюда и сплайн по вашим формулам, меняя x получаю группы характеристик.


UPD: Да, мы смещаем сетку на произвольное время меньшее, чем период дискретизации.

Прочитал по диагонали http://www.dsplib.ru/content/filters/linphase/linphase.html
Вообще, там есть что почитать Навскидку получается, что требование линейности ФЧХ важно для постоянства ГВЗ, как её производной, а угол наклона определяет только саму величину ГВЗ. Значит может и не так страшно, что у Фарроу меньше угол наклона ФЧХ, по линейности они примерно одинаковы.

ЗЫ да и вообще мне смутно кажется, что величина ГВЗ определяется количеством отсчетов, необходимым для получения значения значит у синка или после фильтра по БПФ она будет просто огромная, и это не страшно, главное чтобы постоянная от частоты входного сигнала. Тогда понятно почему у Фарроу ГВЗ меньше - он использует меньше точек

После Вашего комментария я то же это понял) Сам наклон ФЧХ (величина ГВЗ) не столь важен, это только задержка до получения результата на выходе. Важнее постоянство этого наклона в частотной области. Частотная область как 1/f связана с числом отсчетов на период интерполируемого (ресэмплируемого) сигнала. Если частота дискретизации равна 1, то при частоте 0.5 мы получим 2 отсчета на период, и искажения выхода будут определяться искажениями АЧХ и ФЧХ при этой частоте.

Подумал тут на досуге... Если мы будем строить сплайн Эрмита, при этом первые производные в краях интервала будем брать как первые производные интерполяционной кривой (допустим, Лагранжа, хотя можно и любой другой, например моих i-сплайнов) но при условии исключения одной или двух центральных точек интервала, то будет ли это тем мифическим сплайном Акимы который спасает от осцилляций в области выбросов (при наличии последних)? Надо где-то найти почитать про сплайн Акимы, а то есть риск что я его тоже заново "изобрету"

ЗЫ забавно, в данной работе http://www.ncsystems.ru/user/files/Conference/Obuhov.pdf господин Обухов под видом сплайна Акимы подает нам сплайн Катмулла-Рома, причем делая это в рамках "Госконтракта № 14.740.11.0541 на проведение НИР в рамках ФЦП «Научные и научно-педагогические кадры инновационной России» на 2009 – 2013 годы." Либо это "нанотехнологии такие", либо одно из двух Где же правда в век Кали? Продолжаем искать....

ЗЗЫ вот здесь больше похоже на правду http://www.iue.tuwien.ac.at/phd/rottinger/node60.html и судя по всему не то что я подозревал а немного похитрее
А вот тут должно быть правдее некуда http://student.ndhu.edu.tw/~u9111023/akima.pdf
Пока искал, обнаружил немало забавных фамилий помимо Катмулла с Ромом: Кочанек-Бартельс, Fritsch–Carlson и несколько других необычных слов Судя по всему, много народу увлекалось этими игрушками...

А интересно Хироши Акима писал в 1970 году, например

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

Решил. Графики интерполяционной кривой и её 1 и 2 производных при 16 точках на период. Можно тригонометрию проверять на память, чему равна производная синуса и косинуса
UPD: да там и 3 производная оказывается тоже очень даже ничего (график справа) Хотя, некоторых это может ввести в понятное недоумение - как же это, кубический сплайн и такая 3-я производная? Отвечу - в Кали-Югу и не такое бывает Сам удивляюсь.

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

Ivana,

вы еще занимаетесь методами интерполяции или уже забросили это ?

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

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

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

Ага,у меня тоже меньше 6-ти сложений не получилось,видимо предел.