Быстрое отображение формы волны в C/C++

Question

Я заинтересован в реализации аудиоредактора на C или C++ в Windows и Linux. Я не могу понять, как отображать осциллограмму достаточно быстро в полностью увеличенном виде. Я не ищу информацию о быстрых методах буфера кадров. Это вопрос об алгоритмах и структурах данных, чтобы эффективно определять, что отображать.

Скажем, я хочу иметь возможность редактировать 5-канальный 48-КГц, 24-битный звук продолжительностью 2 часа. Это 5 гигабайт выборочных данных. Я хочу, чтобы можно было полностью уменьшить масштаб с одного пикселя на выборку, пока все данные образца не будут видны сразу. Я хочу, чтобы приложение чувствовало отзывчивость, даже на медленной машине, например, для аргументов, Atom 1 ГГц. Когда я говорю отзывчивый, я бы хотел, чтобы обновления графического интерфейса, как правило, возникали в течение 1/30 секунды ввода пользователя.

Наивная реализация будет сканировать каждый образец во всей форме волны при принятии решения о том, что делать для полностью уменьшенного представления - ему нужно найти максимальные и минимальные значения выборки для всех выборок, «покрытых» каждой шириной пикселя дисплей. Я написал простое приложение, чтобы проверить скорость этого подхода. Я тестировал с 1-часовым, моно, 16-битным, 44,1 кГц образцом на моем 3,5-ГГц Xeon в 2015 году. Это занимает 0,12 секунды. Это сотни раз слишком медленно.

Вы можете представить себе сохранение кеша с уменьшенными данными, но я не вижу, как избежать повторного вычисления всего кеша после большинства вставок или удалений. Похоже, что должен быть лучший способ.

Вот диаграмма, показывающая, что я хочу добиться:

Это как дисплей в большинстве имеющихся в настоящее время аудио редакторы работ. Пользователи, вероятно, ожидают такого поведения. Я тестировал с Audacity, и он работает таким образом (хотя он также показывает что-то вроде среднего для образцов в более светлом цвете). Он может обрабатывать произвольные вставки в большие звуки, казалось бы, мгновенно. Я не буду читать 75 мегабайт исходного кода, чтобы узнать, как он это делает.

EDIT:

Различные люди предложили схемы, которые включают только с учетом подмножества образцов при показе Уменьшенном вид. Я пришел к выводу, что я не хочу этого делать, потому что он теряет слишком много полезной информации. Например, в том числе все образцы важны, если вы ищете глюк в звуке, например, щелчок в конвертации винила. В худшем случае, если сбой всего один образец длинный, я все равно хочу получить гарантию, что он будет показан в полностью увеличенном виде.

Answer 1

После прочтения ответа Питера Стокса я придумал следующую схему. Я думаю, что позволит отображать расчет примерно в 500 раз быстрее, чем наивная схема, и не должен добавлять заметных затрат на вставку или удаление. Накладные расходы памяти составляют менее 1%.

Звуковые данные будут выделены блоками из 131072 сэмплов, чтобы вставки и удаления не требовали перераспределения и копирования всего звука. Когда звук будет загружен первым, каждый блок будет полностью заполнен (за исключением, возможно, последнего). Вставки и удаления приведут к некоторой фрагментации. Для простоты я организую, чтобы начало каждого блока всегда содержало действительные данные образца, и любые пробелы будут в конце блока.

Каждый блок имеет две связанные с ним таблицы поиска, один для максимальных значений и один для мин. Каждый элемент в справочных таблицах соответствует 1024 образцам.

На рисунке ниже показано, как рассчитать максимальное значение для одной ширины пикселя дисплея. Он показывает несколько блоков, относящихся к расчету. Он предполагает, что нет «фрагментации».

После вставки, ситуация несколько сложнее. Теперь у двух блоков есть недопустимые регионы. В таблице поиска max есть записи, которые теперь соответствуют частичной области выборок.Значение для этих записей можно найти, просто взяв максимум образцов, которые являются.

Answer 2

Когда зум находится в точке, где у вас есть несколько выборок на пиксель, не стоит точно вычислять среднее значение выборки для каждого пикселя. Пользователь не может точно выровнять инструментальные средства графического интерфейса на этом уровне масштабирования, поэтому это не выгодно. Пользователь просто нуждается в качественном представлении.

Я бы просто выделил один образец на пиксель экрана для области окна, пропустив ненужные образцы.

Что-то вроде этого полностью непроверенного кода:

std::vector<double> samples(1024*1024); // [-1.0 < s < 1.0] 

int window_x = 1024; // window size in pixels 
int window_y = 768; // window size in pixels 

// visit every window pixel 
for(int x = 0; x < window_x; ++x) 
{ 
    // select relevant sample for the current screen pixel x 
    double s = samples[(x * samples.size())/window_x]; 

    int y = (window_y/2) * s; // get y size for sample value 

    // draw sample point/line at coordinate (x, f(y)) 
    gd.draw_line(x, (window_y/2) - y, x, (window_y/2) + y); 
} 

Очевидно, что вы также должны учитывать окно прокрутки и т.д. ...

Answer 3

Может быть, вы могли бы использовать технику MIP-отображение из графика, торговые используя больше памяти для более быстрой скорости?

Если у вас есть 32 образца, сохраните кэш с уменьшенными размерами x2, x4, x8, ... Сохранение этих данных займет то же место, что и исходные данные (16 + 8 + 4 + 2 + 1 выборки) ,

визуально направляющий выступ, с . представляющий собой сохраненную точку данных (мин/макс значение выборки), а также _ образцы, покрытые предыдущим .:

1st level: ................ 
2nd level: ._._._._._._._._ 
3rd level: .___.___.___.___ 
4th level: ._______._______ 
5th level: ._______________ 

Затем просто запросить соответствующий уровень MIP-карту для уровень масштабирования.

Да, при вставке/удалении образцов вам нужно будет заново создать кеп mip-map (или его часть).

Но, может быть, использование памяти делает это не подходящим для вас?

---

Редактировать

Если добавление и удаление является частой операцией и делает перерасчет кэша нежелательного (и вы хотите точно даунсамплинг по интервалам, а не только в отдельных точках), то вы могли бы измените подход mip-mapping для хранения данных, выровненных по локальным точкам min/max, а не по времени.

Использование --------|-------- для обозначения локального мин/макс на интервале, вот графическое представление:

       --------|-------- 
    --------|-------- 
        --------|-------- 
            --------|-- 
------|-------- 
            . 
      .      . . 
.  . . . .   .  . .  . 
. ... . . . . . . .. . .  .  . . . 
    .  .  . . . . . . .  . . . 
        .   . .   . 
           . 
--------|-------- 
      --------|-------- 
            --------|----- 
         --------|-------- 

Затем добавление и удаление только требует повторного расчета непосредственных локальных участков в начале и в конце добавленный/удаленный раздел.

Возможно, вам захочется проиндексировать локальные значения min/max, поэтому вам не нужно много искать. Более сложная схема для реализации - может быть, не стоит для вас?