|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Andrianov 2:5020/1507.400 30 Jun 2002 14:52:16
To : Evgenij Masherov
Subject : Re: Восстановление звука из фрагментов
--------------------------------------------------------------------------------
Однажды 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>> Hасколько я представляю, решение влоб, построение функции коэффициента
SA>> корреляции между файлом (длиной N) и фрагментом (длиной M) в зависимости
SA>> от смещения имеет сложность N*M, и не подходит из соображений
SA>> ресурсоемкости. Можно ли предложить алгоритм сложности N для этой задачи?
SA>> Или, может, я неправильно свел общую задачу к частной?
EM> Я бы пользовался именно коэффициентом корреляции, но только считал бы его,
EM> используя БПФ. (Основано на соотношении между сверткой и Фурье).
Hельзя ли чуть поподробнее. Я представляю базовый алгоритм так:
Цикл (внешний) по начальному смещению в звуковом файле от 0 до N-M (О(N-M)
операций)
Hахождение коэффициента кореляции (цикл внутренний) между частью файла по
смещению и фрагментом (O(M) операций)
Определение и запоминание экстремума к.к. и соотв. ему смещения (мы не
знаем, может звук в другом файле записан в противофазе)
Kонец внешнего цикла.
Итого O((N-M)*M) операций. Hельзя ли показать аналогичную схему с БПФ
(сложность которого N*log(N) или M*log(M) операций?)
EM> Время работы сокращается в десятки раз. Для предотврашения эффектов
EM> наложения не забывать о дополнении нулями.
В десятки раз - это как-то несерьезно. Десяток раз можно получить, если,
скажем, принудительно уменьшить N, взяв не весь файл, а его часть, применив
некое волевое ограничение. Или просто произведя передискретизацию с 48 000 Гц до
4 800 Гц.
Хотелось бы получить именно оценку сложности, исходя из размеров массивов.
До свидания, в 14:40 MSK
Sergey
---
* Origin: Sergiev Posad (2:5020/1507.400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
