14 March 2012

Быстрое сжатие изображений по алгоритму JPEG на CUDA

High performanceGPGPUImage processing
Краткое содержание: Создан быстрый кодер FVJPEG для сжатия изображений по алгоритму JPEG на видеокартах NVIDIA. Значительное ускорение получено при распараллеливании алгоритма, его реализации и оптимизации с помощью технологии CUDA. По скорости сжатия кодер FVJPEG превосходит все существующие в настоящее время программные и аппаратные решения для компрессии изображений по алгоритму Baseline JPEG.

При сравнении алгоритмов сжатия изображений с потерями, практически всегда обсуждаются степень сжатия и качество получаемой картинки, а вот время компрессии почему-то считается второстепенным показателем. По всей видимости, для большинства приложений этот подход справедлив, но существуют ситуации, когда время сжатия может быть очень важным. Например, при сжатии больших массивов изображений или при работе с оборудованием, способным генерировать огромные объёмы данных, для которых требуется компрессия в режиме реального времени. Такова ситуация при сжатии серий изображений от высокоскоростных видеокамер. Поток данных от типичной быстрой камеры может достигать величины 625 Мбайт в секунду (разрешение 1280 х 1024, 8 бит, 500 кадров в секунду) и выше. Существуют высокоскоростные видеокамеры, которые в онлайне пишут данные через фреймграббер PCI-Express 2.0 x8 в оперативную память компьютера со скоростью 2,4 Гбайт в секунду. Для работы с такими потоками требование распараллеливания алгоритма обработки данных не нужно даже обсуждать — это должно быть по определению. Поэтому для выбора быстрого алгоритма сжатия были сформулированы следующие критерии:

  • возможность распараллеливания алгоритма как для кодирования, так и для декодирования
  • возможность сжатия изображений в 10-20 раз с потерями при приемлемом качестве
  • вычислительная сложность алгоритма должна быть как можно меньше
  • деление задачи на максимально возможное количество подзадач
  • минимальные требования к размеру быстрой памяти для одного потока обработки данных

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

Для начала изучим бенчмарки скорости (производительности) сжатия изображений с потерями по алгоритму Baseline JPEG при условии, что изображение уже загружено в оперативную память и нужно сделать только компрессию. Не будем следовать широко распространённому методу, когда делают сравнение полученного решения с заведомо слабыми конкурентами, поэтому в качестве соперников рассмотрим самые быстрые на сегодня коммерческие решения для многоядерных CPU:

Кодер JPEG из PICTools Photo от компании Accusoft Pegasus (сжатие с производительностью 150-250 Мбайт в секунду, 8 бит, степень сжатия ~ 50%)

Кодер JPEG из IPP-7.0 от компании Intel: uic_transcoder_con.exe, version 7.0 build 205.85, [7.7.1058.205], name ippjy8-7.0.dll+, date Nov 27 2011, 64-бит, официальных данных по скорости сжатия нет, результаты тестирования приведены далее)

Кодер JPEG от компании Norpix для работы со скоростными видеокамерами (сжатие с производительностью 200-250 Мбайт в секунду, 8 бит, степень сжатия неизвестна)

К сожалению, проверить эти данные нет возможности за исключением кодера IPP-7, который сам сообщает о времени кодирования, поэтому просто поверим написанному. Для более подробного анализа также нет данных по производительности каждой стадии алгоритма обработки, поэтому придётся ограничить сравнение только общими показателями производительности при одинаковых параметрах сжатия. Кодек JPEG от Kakadu найти не удалось, так как теперь эта компания выпускает только кодек JPEG2000, а скорость сжатия у libjpeg_simd-6b и libjpeg-turbo оказалась очень низкой.

Поскольку речь идёт о реализации стандарта Baseline JPEG с фиксированными таблицами квантования и Хаффмана, то качество сжатого изображения и коэффициент сжатия однозначно определяются параметрами компрессии, поэтому нет необходимости в измерениях PSNR и в визуальной оценке качества. Тем не менее, измерения PSNR и визуальная оценка качества проводились для всех тестов.

Результаты у лучших коммерческих решений на многоядерных CPU впечатляющие, поэтому очень интересно попытаться их превзойти. Для этого рассмотрим вариант сжатия изображений на видеокарте по алгоритму Baseline JPEG с помощью технологии NVIDIA CUDA. Поскольку стоит задача получения максимальной производительности, то и «железо» должно быть соответствующим. NVIDIA GeForce GTX 580 вполне подойдёт.

В этой области исследований обнаружилось немало проектов и научных работ, утверждающих, что алгоритм JPEG нельзя распараллелить полностью из-за стадии энтропийного кодирования. Поэтому за рубежом были созданы гибридные решения, когда дискретное косинусное преобразование выполнялось на видеокарте, а остальные вычисления делали на CPU. Таким образом, ускорялось выполнение только одной стадии, очевидным образом подходящей для GPU. В итоге добивались небольшого увеличения скорости кодирования, но полученные результаты не смогли соперничать по скорости компрессии с лучшими многопоточными решениями на CPU. Найти информацию о производительных кодерах JPEG на базе видеокарт NVIDIA или ATI, к сожалению, не удалось.

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

  • Загрузка данных из оперативной памяти в видеокарту (Host-to-Device transfer)
  • Преобразование RGB->YCbCr (не нужно для 8-битных изображений)
  • Разбиение изображения на блоки 8х8
  • Смещение (вычитание 128) для каждого пиксела
  • Дискретное косинусное преобразование (DCT) для каждого блока
  • Квантование (Quantization) для каждого блока
  • Переупорядочивание (Zig-zag) для каждого блока
  • Дельта-кодирование (DPCM) для DC от каждого блока
  • Кодирование серий (RLE) для AC от каждого блока
  • Кодирование по Хаффману (Huffman) для AC от каждого блока
  • Установка рестарт-маркеров RSTn для групп блоков
  • Формирование выходного файла: склеивание данных от сжатых блоков, добавление заголовка JFIF
  • Выгрузка JPEG файлов из видеокарты в оперативную память (Device-to-Host transfer)

Вся эта схема была реализована на CUDA. Одна из основных идей стандартного алгоритма JPEG состоит в разбиении изображения на блоки 8х8 с последующей независимой обработкой данных с помощью дискретного косинусного преобразования, что по сути является схемой параллельного алгоритма. Распараллеливание дискретного косинусного преобразования уже было известно и полученные результаты по производительности были намного лучше у GPU, чем у CPU. Стадия дельта-кодирования (DPCM) коэффициентов DC тоже может быть распараллелена. Кодирование серий (RLE) и кодирование по Хаффману выполняются независимо для данных каждого блока 8х8, поэтому они тоже параллелятся. В завершение нужно записать сжатые данные от каждого блока в выходной файл, сформировать из него изображение формата JPEG и отправить файл в оперативную память компьютера. Так что можно утверждать, что практически вся схема кодирования по алгоритму JPEG успешно распараллеливается и этот алгоритм можно целиком реализовать на GPU.

Остаётся вопрос о реализации декодирования. Для этого в стандарте JPEG изначально были предусмотрены маркеры, которые дают возможность выполнять декодирование с произвольного места сжатого изображения, а не только последовательно. К сожалению, в большинстве реализаций на CPU алгоритма сжатия JPEG этих маркеров нет, поэтому в таких ситуациях первая стадия декодирования выполняется последовательно и «чужие» изображения будут декодироваться относительно медленно (PhotoShop ставит эти маркеры при кодировании). Если же при кодировании маркеры были поставлены, то перед началом декодирования делается быстрый поиск всех установленных маркеров и после этого становится возможным выполнять декодирование параллельным образом. В описанной выше схеме сжатия делается установка маркеров после определённого количества блоков 8х8 и в итоге процесс декодирования также получается параллельным. Тем не менее, вопросы декодирования остаются за рамками данной статьи.

Для тестирования программы были выбраны следующие стандартные условия:
  • 8-битные тестовые изображения
  • степень сжатия 50-100%
  • размеры изображений по горизонтали и по вертикали должны быть кратны 8
  • размер исходного файла не более 64 Мбайт

Для тестирования использовалась такая конфигурация компьютера:
  • ASUS P6T Deluxe V2 LGA1366, X58, ATX Core i7 920, 2.67 GHz, DDR-III 6 GB.
  • Видеокарты для вычислений: GeForce GT 240 (cc = 1.2, 96 ядер) или GeForce GTX 580 (cc = 2.0, 512 ядер).
  • Операционная система Windows-7, 64-bit, CUDA 4.1, driver 286.19

Тестовые 8-битные изображения использовались общепринятые (lenna.bmp, boats.bmp), из IPP (uic_test_image.bmp), а cathedral.bmp и big_building.bmp взяты здесь

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

Общее время работы кодека FVJPEG в Windows измерялось с помощью функции QueryPerformanceCounter(). Время выполнения отдельных функций на видеокарте измерялось с помощью профайлера NVIDIA. Результаты профайлера необходимы для детального анализа скорости сжатия каждой стадии алгоритма, что представляет интерес прежде всего для разработчиков. Количество повторов (опция многих программ для увеличения точности измерения времени) во всех тестах равно единице, поскольку повторение вычислений над одними и теми же данными не имеет никакого практического смысла. Таким образом, основной задачей было исследование реальных рабочих режимов функционирования кодировщиков и предельных значений производительности сжатия. Для малых изображений есть разброс 10-20% по скорости кодирования, поэтому брались самые высокие результаты в серии тестов. В тестах участвовали кодер FVJPEG на видеокартах NVIDIA GeForce GT 240 и GeForce GTX 580, а также кодер JPEG из IPP-7.0 на Core i7 920.

В таблице 2 приведены результаты измерений для скорости сжатия по алгоритму JPEG для видеокарты NVIDIA GeForce GT 240 в мегабайтах в секунду для различных 8-битных изображений в зависимости от степени сжатия:
скорость сжатия для видеокарты NVIDIA GeForce GT 240

В таблице 3 приведены результаты измерений скорости сжатия в JPEG для видеокарты NVIDIA GeForce GTX 580 в мегабайтах в секунду:
скорость сжатия для видеокарты NVIDIA GeForce GTX 580

Очень важно, что при измерении скорости сжатия учитывалось время копирования данных на видеокарту и обратно. Дело в том, что время копирования данных в память видеокарты обычно оказывается одной из самых длительных операций при реализации алгоритма сжатия в JPEG на GPU. Если же оценить производительность кодирования без учёта загрузки данных в память видеокарты, т.е. если мы хотим измерить именно производительность вычислений при сжатии изображений с потерями, то для достаточно больших изображений и при степени сжатия 50% получаем скорость компрессии в JPEG порядка 10 Гбайт в секунду и более для GeForce GTX 580. Этот результат является прекрасной иллюстрацией высочайшей эффективности параллельных вычислений на мощных видеокартах.

Для сравнения с кодером из Intel IPP-7.0 (update 6) был использован тот же самый набор изображений и те же самые степени сжатия, что и в тестах для видеокарт NVIDIA. Командная строка имела такой вид: uic_transcoder_con.exe -otest.jpg -ilenna.bmp -t1 -q50 -n8, что означает сжатие изображения lenna.bmp, создание нового изображения test.jpg, используемый алгоритм Baseline JPEG (-jb), измерение времени выполнения программы с повышенной точностью (-t1), степень сжатия 50% (-q50) при распараллеливании на 8 потоков (-n8). Режим работы -m для повторения процедуры сжатия не использовался, поскольку нет практических задач для повторного сжатия одного и того же изображения.

В таблице 4 приведены результаты для производительности кодера JPEG из IPP-7.0 (скорость сжатия Мбайт в секунду / время сжатия изображения в миллисекундах):
скорость сжатия кодера JPEG из IPP-7.0 на CPU Core i7 920

При использовании тестового изображения из IPP-7.0 и при одинаковых параметрах сжатия (uic_test_image.bmp, 1280 x 960, 8 бит, степень сжатия 50%, что соответствует компрессии в 8,1 раз), на видеокарте GeForce GTX 580 получена производительность 2,25 Гбайт в секунду, что заметно лучше (быстрее в 6,7 раз), чем 332 Мбайт в секунду на CPU Core i7 920 при распараллеливании на 8 потоков для кодера JPEG из IPP-7.0. Полученная производительность кодера IPP-7.0 в два раза ниже даже по сравнению с довольно слабой видеокартой GeForce GT 240, которая при тех же параметрах даёт скорость компрессии 680 Мбайт в секунду.

На графике 1 указаны результаты по скорости сжатия тестового изображения cathedral.bmp (2000 x 3008, 8 бит) на видеокартах GeForce GT 240, GeForce GTX 580 (кодер FVJPEG) и CPU Core i7 920 (кодер JPEG из IPP-7.0) для разных значений степени сжатия по алгоритму Baseline JPEG:
Скорость сжатия 8-битного изображения cathedral.bmp в JPEG на GeForce GT 240,  GeForce GTX 580 и CPU Core i7 920

С помощью профайлера NVIDIA были сделаны измерения длительности каждой стадии алгоритма кодирования. В таблице 5 приведены бенчмарки для времени сжатия по алгоритму Baseline JPEG с используемыми по умолчанию таблицами квантования и Хаффмана, при разных степенях сжатия, для видеокарты NVIDIA GeForce GTX 580. Изображение cathedral.bmp, разрешение 2000 х 3008, 8 бит, в скобках после степени сжатия указано, во сколько раз сжимается это изображение:
Время выполнения основных стадий сжатия JPEG на видеокарте GeForce GTX 580

Таким образом, мы видим, насколько быстро может выполняться на видеокарте каждая стадия алгоритма сжатия JPEG: загрузка исходных данных, дискретное косинусное преобразование, кодирование серий, кодирование по Хаффману и выгрузка сжатого изображения. При оценке скорости энтропийного кодирования нужно различать вклад от кодирования серий и кодирования по Хаффману. Дело в том, что на разных стадиях алгоритма JPEG размер данных разный, а это важно при расчёте производительности. Для кодирования по Хаффману в качестве нижней оценки скорости кодирования можно разделить размер сжатого файла на время выполнения. Для вычисления точного значения скорости выполнения каждой стадии сжатия нужно измерять не только время, но и размер исходных данных на каждом этапе расчётов.

Таким образом, показана принципиальная возможность очень быстрого сжатия изображений на видеокарте по алгоритму JPEG, причём для довольно широкого класса графических карт NVIDIA, в том числе бюджетных и даже мобильных. При этом полученные результаты заметно превосходят те бенчмарки по скорости кодирования в JPEG, которые мы видели для самых быстрых решений на многоядерных CPU.

Анализ времени выполнения каждой стадии алгоритма JPEG на видеокарте даёт следующую картину: одна из самых медленных операций – это загрузка данных из оперативной памяти компьютера в видеокарту. Для больших изображений скорость как загрузки, так выгрузки данных имеют порядок 6 Гбайт/с. Это ограничение обусловлено пропускной способностью шины PCI-Express 2.0, а значительное ускорение в принципе может быть возможно лишь при переходе на следующее поколение PCI-Express (с Gen2 на Gen3). Время загрузки изображения и время выполнения дискретного косинусного преобразования зависят только от размера изображения. В то время как кодирование серий и кодирование по Хаффману зависят от конкретных данных самого изображения, степени сжатия и от размера данных на данном этапе сжатия.

Важным моментом для увеличения производительности является размер изображения. Чем больше размер изображения, тем больше скорость сжатия на видеокарте. По всей видимости, это связано с тем, что данных в небольшом изображении не хватает для полной загрузки видеокарты и часть вычислительных мощностей простаивает. Если же использовать относительно большие кадры (4 Мегабайта и более), то получаем полную загрузку и производительность сжатия на видеокарте увеличивается. Тем не менее, и для небольших изображений есть вариант ускорения: можно загружать одновременно сразу несколько кадров и кодировать их параллельно. Таким образом можно загрузить видеокарту полностью и получить максимальную производительность даже для изображений небольшого размера. Поэтому скорость сжатия для серий небольших кадров будет близкой к тем результатам, которые получены для больших одиночных изображений. Такой режим работы для одновременной загрузки и сжатия нескольких изображений уже протестирован и будет включён в финальную версию кодека FVJPEG.

Также хотелось бы отметить, что результаты, полученные на видеокарте GeForce GTX 580 для скорости сжатия изображений по алгоритму JPEG с потерями, превосходят по производительности все известные аппаратные решения по сжатию изображений на ПЛИС (FPGA) для того же самого алгоритма. Одни из самых быстрых систем сжатия изображений на ПЛИС по алгоритму JPEG предлагают следующие компании:

Barco BA116 JPEG Encoder (High speed baseline DCT-based JPEG color encoder) — функция аппаратного кодирования в JPEG для FPGA, производительность до 140 Мбайт/с.

Cast Inc. (JPEG-C Baseline JPEG Compression Codec Core) — функция аппаратного сжатия в джипег для FPGA, производительность до 275 Мбайт/с для Xilinx Virtex-6, до 280 Мбайт/с для Altera FPGA Stratix IV.

Visengi (JPEG / MJPEG Hardware Compressor IP Core) — функция аппаратного кодирования в джипег для FPGA Virtex-5, производительность до 405 Мбайт/с.

Alma-Tech (SVE-JPEG-E, SpeedView Enabled JPEG Encoder Megafunction) — функция аппаратного сжатия по Baseline JPEG для FPGA Altera/Xilinx, производительность до 500 Мбайт/с.

На специализированных выставках встречались сообщения от частных компаний о создании кодировщиков JPEG на ПЛИС с производительностью до 680 Мбайт в секунду (четыре отдельных блока, работающих параллельно и дающих по 170 Мбайт в секунду каждый), но подробностей про такие решения найти не удалось.

Сравнивая программный кодер на GPU с аппаратными кодерами JPEG на ПЛИС, стоит отметить, что кроме более высокой производительности полученного решения на GPU, по сравнению с Verilog/VHDL, код на Си для CUDA намного более понятный и приспособленный к модификации для создания на его базе новых, более сложных систем обработки и сжатия изображений. Понятно, что у ПЛИС есть свои плюсы, но мы ограничимся лишь рассмотрением вопроса скорости вычислений.

Для полноты картины нужно не забывать и о существующих недостатках технологий параллельных вычислений на видеокарте. Во-первых, вычисления на видеокарте имеют смысл только для распараллеливаемых алгоритмов, что означает, что для многих последовательных алгоритмов такой возможности просто нет, поэтому для их реализации однозначно потребуется программное обеспечение для CPU. Также технология CUDA может быть использована только в видеокартах производства NVIDIA, а самые последние достижения (технология Fermi) доступны только для последних моделей видеокарт. В принципе, существует стандарт OpenCL, который подходит для видеокарт различных производителей, но он не даёт максимальной производительности для видеокарт NVIDIA и вообще, универсальность такого типа решения для всех существующих архитектур видеокарт пока кажется спорной. Важно, что у потоковых мультипроцессоров на видеокартах очень малый размер быстрой разделяемой памяти, что вносит дополнительные ограничения на используемые алгоритмы и их эффективность, а доступная (относительно медленная) память GDDR5 на данный момент не более 6 Гигабайт на видеокарту, в то время как для CPU размер оперативной памяти может превышать сотню гигабайт. Чтобы получить высокую производительность, необходимо добиться максимальной загрузки видеокарты, а это возможно только для параллельных алгоритмов и для больших объёмов данных. Для вычислений на GPU всегда нужно сначала копировать данные в видеокарту, что вносит дополнительную задержку и увеличивает время расчётов. Поэтому при проектировании высокопроизводительного решения на видеокарте нужно принимать во внимание разнообразные особенности алгоритма и возможности его реализации в конкретном «железе».

В данной статье представлено решение для быстрого сжатия 8-битных изображений по стандартному алгоритму JPEG на одной видеокарте. В резерве остались различные способы масштабирования производительности для такого решения, поскольку уже сейчас у NVIDIA есть технология распараллеливания таких задач на несколько видеокарт, что в принципе может дать возможность для дальнейшего кратного увеличения скорости сжатия. Использование более мощных видеокарт вроде GeForce GTX 590 также должно привести к улучшению результатов. Ещё существует потенциальная возможность для ускорения алгоритма при распараллеливании стадий копирования и вычислений. Следующее, более мощное поколение видеокарт NVIDIA тоже может рассматриваться в контексте увеличения производительности сжатия. Таким образом, технологии параллельных вычислений на видеокартах дают широкие возможности для создания быстрых алгоритмов обработки данных и по-прежнему есть что улучшать и куда стремиться. Также представляют большой интерес для дальнейших исследований оптимизация полученного решения, другие алгоритмы для быстрого сжатия изображений и видео (MJPEG), в том числе и без потерь.

Программное обеспечение для сжатия изображений на видеокарте, описанное в статье, является результатом предварительных исследований и пока не существует в виде законченного коммерческого продукта. Релиз кодека FVJPEG и соответствующего SDK для быстрого сжатия изображений на GPU NVIDIA по алгоритму Baseline JPEG для Windows/Linux ожидается в ближайшее время.
Tags:codec JPEGCUDAFastvideo JPEG codec for GPUFVJPEGGPGPUGPUOpenCLCPUFPGANVIDIAGeForceHPChigh speed JPEG encoder on GPUparallel computationsbenchmarkGPU programmingfast lossy compressionperformance of JPEG implementationsDCTRLEHuffmanhigh speed cameraбыстрое сжатие изображенийкодек джипегпараллельные вычисленияскорость кодированиявысокоскоростная видеокамеравысокопроизводительные вычисления
Hubs: High performance GPGPU Image processing
+44
18.2k 125
Comments 49
Popular right now
Профессия iOS-разработчик
November 30, 202075,000 ₽SkillFactory
Основы HTML и CSS
November 30, 2020FreeНетология
SMM-менеджер
November 30, 202059,998 ₽GeekBrains
Курс по аналитике данных
November 30, 202053,500 ₽SkillFactory
Frontend-разработчик с нуля
November 30, 202077,940 ₽Нетология
Top of the last 24 hours