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

From

Sergey Andrianov (2:5020/1507.400)

To

Evgenij Masherov

Date

2002-06-30T14:52:16Z

Area

RU.ALGORITHMS

Здравствуй, Evgenij!

Однажды 29-Jun-02  в 09:31   Evgenij Masherov (2:5020/175.2)
написал       Sergey Andrianov    по поводу
-=-   Восстановление звука из фрагментов  -=-

 
SA>>    Есть общая задача: восстановить некоторый звук (возможно, несколько
SA>> часов при оцифровке 44100-48000 Гц) из нескольких перекрывающихся во
SA>> времени фрагментов, записанных независимо, т.е. с различными амплитудой и
SA>> фазой оцифровки, а также дополнительными шумами и, возможно, искажениями
SA>> из-за mp3-сжатия. 
SA>>    Представляется, что ее можно свести к последовательности частных
SA>> задач: в некотором звуковом файле (PCM) найти с точностью до целого
SA>> смещение от начала, по которому находится некоторый его фрагмент (на
SA>> самом деле фрагмент взят из перекрывающейся части другого файла) с
SA>> измененной амплитудой фазой и добавлением некоторых шумов и искажений.
SA>> Далее перенормировку амплитуды и сшивку считаю тривиальными. 
SA>>    Насколько я представляю, решение влоб, построение функции коэффициента
SA>> корреляции между файлом (длиной N) и фрагментом (длиной M) в зависимости
SA>> от смещения имеет сложность N*M, и не подходит из соображений
SA>> ресурсоемкости. Можно ли предложить алгоритм сложности N для этой задачи?
SA>>    Или, может, я неправильно свел общую задачу к частной?

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

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

   Итого O((N-M)*M) операций. Нельзя ли показать аналогичную схему с БПФ (сложность которого N*log(N) или M*log(M) операций?)


EM> Время работы сокращается в десятки раз. Для предотврашения эффектов наложения не 
EM> забывать о дополнении нулями.

   В десятки раз - это как-то несерьезно. Десяток раз можно получить, если, скажем, принудительно уменьшить N, взяв не весь файл, а его часть, применив некое волевое ограничение. Или просто произведя передискретизацию с 48 000 Гц до 4 800 Гц.
   Хотелось бы получить именно оценку сложности, исходя из размеров массивов.



                  До свидания,  в  14:40 MSK
                                 Sergey

---
 * Origin: Sergiev Posad (2:5020/1507.400)