Re: Восстановление звука из фрагментов

From

Evgenij Masherov (2:5020/175.2)

To

Sergey Andrianov

Date

2002-07-02T15:16:33Z

Area

RU.ALGORITHMS

From: "Evgenij Masherov" <EMasherow@nsi.ru>

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>>>    Насколько я представляю, решение влоб, построение функции
 SA>>> коэффициента  корреляции между файлом (длиной N) и фрагментом (длиной
 SA>>> M) в зависимости  от смещения имеет сложность N*M, и не подходит из
 SA>>> соображений  ресурсоемкости. Можно ли предложить алгоритм сложности N
 SA>>> для этой задачи?
 SA>>>    Или, может, я неправильно свел общую задачу к частной?

 EM>> Я бы пользовался именно коэффициентом корреляции, но только считал бы
 EM>> его,  используя БПФ. (Основано на соотношении между сверткой и Фурье). 

 SA>    Нельзя ли чуть поподробнее. Я представляю базовый алгоритм так:
 SA>    Цикл (внешний) по начальному смещению в звуковом файле от 0 до N-M
 SA> (О(N-M) операций)
 SA>        Нахождение коэффициента кореляции (цикл внутренний) между частью
 SA> файла по смещению и фрагментом (O(M) операций)
 SA>        Определение и запоминание экстремума к.к. и соотв. ему смещения
 SA> (мы не знаем, может звук в другом файле записан в противофазе)
 SA>    Kонец внешнего цикла.

 SA>    Итого O((N-M)*M) операций. Нельзя ли показать аналогичную схему с БПФ
 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 млн
операций
Напрямую - 8000*8000*(2 операции)=128 млн.
Примерно 1:18

Евгений Машеров АКА СанитарЖеня

--- ifmail v.2.15dev5
 * Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)