|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 02 Jul 2002 15:16:33
To : Sergey Andrianov
Subject : Re: Восстановление звука из фрагментов
--------------------------------------------------------------------------------
Sun Jun 30 2002 14:52, Sergey Andrianov wrote to Evgenij Masherov:
SA>>> Есть общая задача: восстановить некоторый звук (возможно, несколько
SA>>> часов при оцифровке 44100-48000 Гц) из нескольких перекрывающихся во
SA>>> времени фрагментов, записанных независимо, т.е. с различными амплитудой
SA>>> и фазой оцифровки, а также дополнительными шумами и, возможно,
SA>>> искажениями из-за mp3-сжатия.
SA>>> Представляется, что ее можно свести к последовательности частных
SA>>> задач: в некотором звуковом файле (PCM) найти с точностью до целого
SA>>> смещение от начала, по которому находится некоторый его фрагмент (на
SA>>> самом деле фрагмент взят из перекрывающейся части другого файла) с
SA>>> измененной амплитудой фазой и добавлением некоторых шумов и искажений.
SA>>> Далее перенормировку амплитуды и сшивку считаю тривиальными.
SA>>> Hасколько я представляю, решение влоб, построение функции
SA>>> коэффициента корреляции между файлом (длиной N) и фрагментом (длиной
SA>>> M) в зависимости от смещения имеет сложность N*M, и не подходит из
SA>>> соображений ресурсоемкости. Можно ли предложить алгоритм сложности N
SA>>> для этой задачи?
SA>>> Или, может, я неправильно свел общую задачу к частной?
EM>> Я бы пользовался именно коэффициентом корреляции, но только считал бы
EM>> его, используя БПФ. (Основано на соотношении между сверткой и Фурье).
SA> Hельзя ли чуть поподробнее. Я представляю базовый алгоритм так:
SA> Цикл (внешний) по начальному смещению в звуковом файле от 0 до N-M
SA> (О(N-M) операций)
SA> Hахождение коэффициента кореляции (цикл внутренний) между частью
SA> файла по смещению и фрагментом (O(M) операций)
SA> Определение и запоминание экстремума к.к. и соотв. ему смещения
SA> (мы не знаем, может звук в другом файле записан в противофазе)
SA> Kонец внешнего цикла.
SA> Итого O((N-M)*M) операций. Hельзя ли показать аналогичную схему с БПФ
SA> (сложность которого N*log(N) или M*log(M) операций?)
EM>> Время работы сокращается в десятки раз. Для предотврашения эффектов
EM>> наложения не забывать о дополнении нулями.
SA> В десятки раз - это как-то несерьезно. Десяток раз можно получить,
SA> если, скажем, принудительно уменьшить N, взяв не весь файл, а его часть,
SA> применив некое волевое ограничение. Или просто произведя
SA> передискретизацию с 48 000 Гц до 4 800 Гц.
SA> Хотелось бы получить именно оценку сложности, исходя из размеров
SA> массивов.
Основано на теореме о соответствии ПФ от свертки произведению ПФ свертываемых.
Берем два отрезка, дополняем нулями (чтобы свертка не была циклической),
считаем от них БПФ, перемножаем, обратное БПФ - и имеем корреляционную
функцию.
Время работы N*log(N).
Для 8000 точек (1 сек в обычном телефоне)
3 БПФ от 16384 точек (16384*14*(примерно 10 операций на бабочку))= 7 млн
операций
Hапрямую - 8000*8000*(2 операции)=128 млн.
Примерно 1:18
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
