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

From

Sergey Andrianov (2:5020/1507.400)

To

All

Date

2002-06-28T22:05:56Z

Area

RU.ALGORITHMS

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

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

                  До свидания,  в  21:56 MSK
                                 Sergey

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