Оптимизированное последовательное преобразование среднего квантования

Алгоритм последовательного преобразования среднего квантования (SMQT) — это нелинейное преобразование, которое раскрывает организацию или структуру данных и удаляет такие свойства, как усиление и смещение. В статье под названием «Последовательное преобразование среднего квантования» SMQT «применяется в обработке речи и обработке изображений». Алгоритм применительно к изображениям «может рассматриваться как прогрессивный акцент на деталях изображения».

Согласно другому документу под названием «Операторы тонального отображения на основе SMQT для изображений с высоким динамическим диапазоном», это даст «изображение с улучшенными деталями». В статье описываются два метода применения этого преобразования к изображению.

1. Примените SMQT к яркости каждого пикселя — он описывает формулу для получения яркости из RGB каждого пикселя.

2. Примените SMQT к каждому каналу RGB отдельно — для каналов R, G и B по отдельности.

На следующем рисунке показан результат двух методов:

Применяя второй метод к изображению театра Брюин ночью, мы можем увидеть, как алгоритм постепенно увеличивает детали изображения и выявляет детали, изначально скрытые темнотой:

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

Алгоритм SMQT

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

Предположим, у нас есть следующий вектор (вы можете думать о нем как о массиве):

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

Шаги, связанные с применением алгоритма SMQT:

1. Вычислите среднее значение вектора, которое в данном случае равно 29,58.

2. Разделите вектор на две части, оставив числа меньше или равные 29,58 в левой половине, а числа больше в правой половине:

   15	4	0	5	18	32	48	60	64	59	47	31
   0	0	0	0	0	1	1	1	1	1	1	1

   Вторая строка — это код, который мы создадим для каждого значения. Значения ниже или равные 29,58 получают 0 в своем коде, а числа больше 29,58 получают 1 (это двоичный код).

3. Теперь оба получившихся вектора разбиваются индивидуально рекурсивным образом по одному и тому же правилу. В нашем примере среднее значение первого вектора равно (15 + 4 + 0 + 5 + 18) / 5 = 8,4, а среднее значение второго вектора равно (32 + 48 + 60 + 64 + 59 + 47 + 31) / 7 = 48,7. Каждый из этих двух векторов далее разбивается еще на два вектора, и к каждому добавляется второй бит кода в зависимости от его сравнения со средним значением. Вот результат:

   4	0	5	15	18	32	47	31	48	60	64	59
   00	00	00	01	01	10	10	10	11	11	11	11

   Обратите внимание, что 0 снова был добавлен для чисел, меньших или равных среднему (для каждого вектора), и 1 для чисел, превышающих среднее значение.

4. Этот алгоритм повторяется рекурсивно:

   0	4	5	15	18	32	31	47	48	60	64	59
   000	001	001	010	011	100	100	101	110	111	111	111

   0	4	5	15	18	31	32	47	48	60	59	64
   0000	0010	0011	0100	0110	1000	1001	1010	1100	1110	1110	1111

   0	4	5	15	18	31	32	47	48	59	60	64
   00000	00100	00110	01000	01100	10000	10010	10100	11000	11100	11101	11110

   На данный момент каждый вектор имеет только один элемент. Таким образом, к каждому последующему шагу будет добавляться 0, поскольку число всегда будет равно самому себе (условие для 0 состоит в том, что число должно быть меньше или равно среднему, то есть самому себе).

Пока у нас есть уровень квантования L=5. Если бы мы собирались использовать L=8, мы должны были бы добавить три 0 к каждому коду. Результатом преобразования каждого кода из двоичного в целочисленный (для L=8) будет:

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

Обратите внимание, что в результирующем векторе:

• Выигрыш убрали. Первоначальный коэффициент усиления был низким, его диапазон варьировался от 0 до 64. Теперь его коэффициент усиления колеблется от 0 до 240, что составляет почти весь 8-битный диапазон. Говорят, что усиление удаляется, потому что не имеет значения, умножаем ли мы все элементы исходного вектора на число, например 2, или делим все на 2, выходной вектор будет примерно таким же. Его диапазон будет примерно равен всему диапазону целевого вектора (8 бит для L=8). Если мы умножим входной вектор на два, выходной вектор на самом деле будет таким же, потому что на каждом шаге одни и те же числа, которые были ниже или выше среднего, будут продолжать оставаться ниже или выше его, и мы добавим те же 0 или 1 к выходу. Только если мы его поделим, результат будет примерно таким же, а не совсем таким же, потому что нечетные числа, такие как 15, придется округлять, и тогда расчеты могут отличаться. Мы перешли от темного изображения к изображению с пикселями в диапазоне от темных цветов (0) до более светлых цветов (240), используя весь диапазон.
• Смещение устранено, хотя в этом примере мы его не наблюдаем. Это связано с тем, что у нас нет смещения, поскольку наше самое низкое значение равно 0. Если бы у нас действительно было смещение, оно было бы удалено. Если мы возьмем любое число «К» и добавим его к каждому элементу входного вектора, вычисление чисел выше и ниже среднего на каждом шаге не изменится. Вывод останется прежним. Это также сделало бы изображения, которые слишком яркие, чтобы стать изображениями, которые варьируются от темных до светлых цветов.
• У нас есть изображение с улучшенными деталями. Обратите внимание, что для каждого рекурсивного шага мы на самом деле увеличиваем детали и строим вывод, максимально раскрывая эти детали. А поскольку мы будем применять эту технику к каждому каналу RGB, мы раскроем как можно больше деталей, хотя и потеряем информацию об исходных тонах каждого цвета.

Учитывая изображение, подобное вектору пикселей RGB, каждая точка которого представляет собой 8 бит для R, 8 для G и 8 для B; мы можем извлечь из него три вектора, по одному для каждого цвета, и применить алгоритм к каждому вектору. Затем мы снова формируем вектор RGB из этих трех выходных векторов, и у нас есть изображение, обработанное SMQT, как это сделано с изображением Bruin Theater.

Сложность

Алгоритм требует, чтобы для каждого уровня квантования (L) N элементов должны быть проверены на первом проходе, чтобы найти среднее значение для каждого вектора, а затем на втором проходе каждый из этих N элементов должен быть сравнен с соответствующим средним значением в чтобы разбить каждый вектор по очереди. Наконец, N элементов должны быть заменены их кодами. Следовательно, сложность алгоритма составляет O((L*2*N) + N) = O((2*L + 1)*N), то есть O(L*N).

График, извлеченный из статьи, соответствует сложности O(L*N). Чем ниже L, тем быстрее обработка приблизительно линейным образом (большее количество кадров в секунду). Для повышения скорости обработки в документе предлагается снизить значения L: «выбор более низкого уровня L может быть прямым путем к снижению скорости обработки, но с ухудшением качества изображения».

Улучшение

Здесь мы найдем способ повысить скорость без снижения качества изображения. мы проанализируем процесс преобразования и найдем более быстрый алгоритм. Чтобы получить более полное представление об этом, давайте рассмотрим пример с повторяющимися числами:

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

Для простоты предположим, что на входе может быть от 0 до 31, а на выходе от 0 до 7 (L=3), как видно из примера.

Обратите внимание, что вычисление среднего значения первого вектора (16 + 25 + 31 + 31 + 25 + 16 + 7 + 1 + 1 + 7) / 10 = 16 дает тот же результат, что и вычисление среднего значения всего последнего вектора, поскольку это точно такой же вектор с элементами в другом порядке: (1 + 1 + 7 + 7 + 16 + 16 + 25 + 25 + 31 + 31) / 10 = 16.

На втором шаге мы должны рекурсивно вычислить каждый вектор. Таким образом, мы вычисляем среднее значение серых входных данных, которые являются первыми 6 элементами ((16 + 16 + 7 + 1 + 1 + 7)/6 = 8), и среднее значение пустого ввода, которое является последними 4 элементами. ((25 + 31 + 31 + 25) / 4 = 28):

Еще раз отметим, что если мы используем последний вектор, тот, который полностью упорядочен, результаты будут такими же. Для первых 6 элементов имеем: ((1 + 1 + 7 + 7 + 16 + 16) / 6 = 8), а для последних 4 элементов: ((25 + 25 + 31 + 31) / 4 = 28) . Поскольку это просто дополнение, порядок слагаемых не имеет значения.

То же самое относится и к следующему шагу:

Расчеты такие же, как и с последним вектором: ((7+1+1+7)/4=4) будет равно ((1+1+7+7)/4=4).

И то же самое применимо к остальным векторам и шагам.

Вычисление среднего — это просто сумма значений элементов в интервале, деленная на количество элементов в интервале. Это означает, что мы можем предварительно вычислить все эти значения и избежать повторения этого вычисления L раз.

Давайте посмотрим, как применить то, что мы будем называть алгоритмом FastSMQT, к нашему примеру:

1. Создайте таблицу с 32 столбцами и 3 строками, как показано ниже. Первая строка в таблице представляет индекс таблицы (от 0 до 31), и ее не обязательно включать при кодировании таблицы. Но это явно показано, чтобы упростить следование примеру.

2. Повторите N элементов один раз, считая частоту каждого значения. В нашем примере элементы 1, 7, 16, 25 и 31 имеют частоту 2. Все остальные элементы имеют частоту 0. Этот шаг имеет сложность O(N).

3. Теперь, когда вектор частот заполнен, нам нужно повторить этот вектор (вектор частот, а не входной вектор). Мы больше не итерируем N элементов, а R (R находится в диапазоне: 2 ^ L), что в данном случае равно 32 (от 0 до 31). При обработке пикселей N может быть много миллионов (мегапикселей), но обычно R равно 256 (по одному вектору на каждый цвет). В нашем примере это 32. Следующие две строки таблицы мы будем заполнять одновременно. Первая из этих строк (вторая в таблице) будет иметь сумму частот до сих пор. Вторая (третья таблицы) будет иметь сумму значений всех элементов, которые появились до сих пор.

   В нашем примере, когда мы доходим до 1, мы помещаем 2 во вторую строку таблицы, потому что до сих пор появилось две единицы. И мы также помещаем 2 в третью строку таблицы, потому что 1 + 1 = 2. Мы продолжаем писать эти два значения на каждой из следующих позиций, пока не дойдем до 7. Поскольку число 7 встречается дважды, мы добавляем 2 к аккумулятор второй строки, потому что теперь появилось пока 4 числа (1, 1, 7, 7). И мы добавляем 7 + 7 = 14 к третьей строке, в результате чего 2 + 14 = 16, потому что 1 + 1 + 7 + 7 = 16. Мы продолжаем этот алгоритм, пока не закончим итерацию этих элементов. Сложность этого шага составляет O(2^L), что в нашем случае равно O(32), а при работе с пикселями RGB — O(256).

   я	0	1	2	...	6	7	8	...	15	16	17	...	24	25	26	...	30	31
   н	0	2	0	...	0	2	0	...	0	2	0	...	0	2	0	...	0	2
   n-кумулятивный	0	2	2	...	2	4	4	...	4	6	6	...	6	8	8	...	8	10
   сумма	0	2	2	...	2	16	16	...	16	48	48	...	48	98	98	...	98	160

4. Следующим шагом будет удаление из таблицы столбцов с элементами, имеющими частоту 0, и, чтобы пример был понятнее, мы также удалим вторую строку, так как она больше не актуальна, как вы увидите.

   я	1	7	16	25	31
   н	2	4	6	8	10
   сумма	2	16	48	98	160

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

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

   Сначала нам нужно вычислить среднее значение всех выборок. Мы можем легко найти его по формуле: sum[31] / n[31] = 160 / 10 = 16. Итак, мы разбиваем таблицу на два вектора и начинаем писать двоичный код для каждого:

   я	1	7	16	25	31
   н	2	4	6	8	10
   сумма	2	16	48	98	160
   код	0	0	0	1	1

   Теперь снова разбиваем каждый вектор. Среднее значение первого вектора равно: sum[16] / n[16] = 48 / 6 = 8. Среднее значение второго вектора равно: (sum[31] – sum[16]) / (n[31] – n[16]) = (160 – 48) / (10 – 6) = 112 / 4 = 28.

   я	1	7	16	25	31
   н	2	4	6	8	10
   сумма	2	16	48	98	160
   код	00	00	01	10	11

   Остается разделить только один вектор. Среднее значение: сумма[7]/n[7] = 16/4 = 4.

   я	1	7	16	25	31
   н	2	4	6	8	10
   сумма	2	16	48	98	160
   код	000	001	010	100	110

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

   Сложность этого шага составляет O(L*(2^L)), что для L=8 и в практических целях обработки изображений составляет O(8*(256)) = O(2048) = константа.

6. Последний шаг — еще раз перебрать N элементов, заменив элемент его кодом для каждого элемента: element[i] = code[i]. Сложность O(N). Сложность FastSMQT составляет O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)) .

Параллелизм

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

Чтобы распараллелить алгоритм SMQT, когда мы делим вектор на две части, мы можем обрабатывать каждый подвектор в новом ядре, если ядро ​​доступно (фактически один подвектор в текущем ядре, а другой в новом ядре). Это можно делать рекурсивно, пока мы не достигнем общего количества доступных ядер. Замена значений кодами также может выполняться параллельно for.

Алгоритм FastSMQT также может быть распараллелен. На первом этапе входной вектор необходимо разделить на количество доступных ядер (C). Для каждой из этих частей должен быть создан один вектор подсчета частот, который заполняется параллельно. Затем мы добавляем значения этих векторов в один результирующий вектор частот. Следующий шаг, который можно распараллелить, — последний, когда мы подставляем значения их кодами. Это можно сделать параллельно для .

Сравнение сложности

Общая сложность исходного алгоритма SMQT составляет O((2*L + 1)*N), то есть O(L*N).

Сложность FastSMQT составляет O(N) + O(2^L) + O(L*(2^L)) + O(N) = O(2*N) + O((L + 1)*(2 ^L)) = O(N + L*(2^L)).

При фиксированном L сложность становится равной O(N) для обоих. Но константа, которая умножает N, для FastSMQT намного меньше, и, как мы увидим, это сильно влияет на время обработки.

На следующем графике сравнивается производительность алгоритмов SMQT и FastSMQT для L=8, что имеет место при обработке изображений. График показывает время (в миллисекундах), которое требуется для обработки N элементов. Обратите внимание, что сложность (с константами) SMQT для L=8 составляет O(17*N), а для FastSMQT — O(2*N + 2304).

Чем больше N, тем больше времени требуется SMQT для обработки изображения. С другой стороны, для FastSMQT рост намного медленнее.

Для еще больших значений N разница в производительности становится более очевидной:

Здесь SMQT требует до нескольких секунд для обработки определенных изображений, в то время как FastSMQT по-прежнему находится в зоне «несколько миллисекунд».

Даже с несколькими ядрами (в данном случае с двумя) FastSMQT явно превосходит простой SMQT:

FastSMQT не зависит от L. SMQT, с другой стороны, линейно зависит от значения L. Например, при N = 67108864 время выполнения SMQT увеличивается с увеличением значения L, а FastSMQT — нет:

Заключение

Не все методы оптимизации применимы для всех алгоритмов, и ключ к улучшению производительности алгоритма часто скрыт в некотором понимании того, как работает алгоритм. Этот алгоритм FastSMQT использует возможности предварительного вычисления значений и природу вычислений средних значений. В результате он обеспечивает более быструю обработку, чем исходный SMQT. На скорость не влияет приращение L, хотя L не может быть намного больше обычного 8, потому что использование памяти 2 ^ L, что для 8 является приемлемым 256 (количество столбцов в нашей таблице частот), но прирост производительности имеет очевидную практическую пользу.

Это улучшение скорости позволило MiddleMatter реализовать алгоритм в приложении для iOS (и в приложении для Android), который улучшает изображения и видео, снятые в условиях низкой освещенности. Благодаря этому улучшению стало возможным выполнять обработку видео в приложении, что в противном случае было бы слишком медленным для устройств iOS.

Код C++ для алгоритмов SMQT и FastSMQT доступен на GitHub.