Распараллеливание создания файлов PNG с помощью C++, libpng и OpenMP

В настоящее время я пытаюсь реализовать кодировщик PNG на С++ на основе libpng, который использует OpenMP для ускорения процесса сжатия. Инструмент уже может генерировать файлы PNG из различных форматов изображений. Я загрузил полный исходный код на pastebin.com, чтобы вы могли увидеть, что я уже сделал: http://pastebin.com/8wiFzcgV

Все идет нормально! Теперь моя проблема состоит в том, чтобы найти способ распараллелить создание фрагментов IDAT, содержащих сжатые данные изображения. Обычно функция libpng png_write_row вызывается в цикле for с указателем на структуру, содержащую всю информацию о файле PNG, и указателем строки с пиксельными данными одной строки изображения.

(строка 114-117 в файле Pastebin)

//Loop through image
for (i = 0, rp = info_ptr->row_pointers; i < png_ptr->height; i++, rp++) {
    png_write_row(png_ptr, *rp);
}

Затем Libpng сжимает одну строку за другой и заполняет внутренний буфер сжатыми данными. Как только буфер заполняется, сжатые данные сбрасываются блоком IDAT в файл изображения.

Мой подход заключался в том, чтобы разделить изображение на несколько частей и позволить одному потоку сжимать строку с 1 по 10, а другому потоку — с 11 по 20 и так далее. Но поскольку libpng использует внутренний буфер, это не так просто, как я сначала думал :) Мне каким-то образом нужно заставить libpng записывать сжатые данные в отдельный буфер для каждого потока. После этого мне нужен способ объединить буферы в правильном порядке, чтобы я мог записать их все вместе в выходной файл изображения.

Итак, у кого-нибудь есть идея, как я могу сделать это с OpenMP и некоторыми настройками libpng? Большое тебе спасибо!


c++ openmp parallel-processing png libpng
person Pascal    schedule 31.05.2012    source источник

Ответы (2)


arrow_upward
11
arrow_downward

Это слишком долго для комментария, но и не совсем ответ -

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

На высоком уровне изображение представляет собой набор строк пикселей (обычно 32-битные значения, представляющие кортежи RGBA).

К каждой строке может быть независимо применен фильтр — единственная цель фильтра состоит в том, чтобы сделать строку более "сжимаемой". Например, фильтр «sub» делает значение каждого пикселя разницей между ним и тем, что слева от него. Это дельта-кодирование может показаться глупым на первый взгляд, но если цвета между соседними пикселями похожи (что, как правило, так и есть), то результирующие значения очень малы, независимо от реальных цветов, которые они представляют. Такие данные легче сжимать, потому что они гораздо более повторяющиеся.

Спускаясь на уровень ниже, данные изображения можно рассматривать как поток байтов (строки больше не отличаются друг от друга). Эти байты сжимаются, образуя другой поток байтов. Сжатые данные произвольно разбиваются на сегменты (куда угодно!), каждый из которых записывается в один блок IDAT (вместе с небольшими накладными расходами на каждый блок, включая контрольную сумму CRC).

Самый нижний уровень подводит нас к самой интересной части, а именно к самому шагу сжатия. Формат PNG использует формат сжатых данных zlib. Сама zlib — это всего лишь оболочка (с дополнительной бухгалтерией, включая контрольную сумму Adler-32) вокруг реального формата сжатых данных, deflate (архивные файлы также используют это). deflate поддерживает два метода сжатия: кодирование Хаффмана (которое уменьшает количество битов, необходимых для представления некоторой строки байтов, до оптимального числа, учитывая частоту, с которой каждый отдельный байт встречается в строке) и кодирование LZ77 (которое позволяет дублировать строки, которые уже были произошла ссылка вместо того, чтобы дважды записываться в вывод).

Сложность распараллеливания сжатия deflate заключается в том, что, как правило, сжатие одной части входного потока требует, чтобы предыдущая часть также была доступна на случай, если на нее нужно будет сослаться. Но так же, как PNG может иметь несколько фрагментов IDAT, deflate разбивается на несколько "блоков". Данные в одном блоке могут ссылаться на ранее закодированные данные в другом блоке, но не должны (конечно, это может повлиять на степень сжатия, если это не так).

Таким образом, общая стратегия распараллеливания дефляции состоит в том, чтобы разбить входные данные на несколько больших разделов (чтобы степень сжатия оставалась высокой), сжать каждый раздел в серию блоков, а затем склеить блоки вместе ( на самом деле это сложно, поскольку блоки не всегда заканчиваются на границе байта, но вы можете поместить пустой несжатый блок (тип 00), который будет выровнен по границе байта между разделами). Однако это не тривиально и требует контроля над самым низким уровнем сжатия (создание блоков deflate вручную), создание надлежащей оболочки zlib, охватывающей все блоки, и заполнение всего этого фрагментами IDAT.

Если вы хотите использовать свою собственную реализацию, я бы посоветовал прочитать мой собственный zlib реализация /deflate (и как я его использую), который я специально создал для сжатия PNG (он написан на Haxe для Flash, но его сравнительно легко портировать на C++). Поскольку Flash является однопоточным, я не делаю распараллеливания, но разбиваю кодирование на практически независимые разделы («виртуально», потому что между разделами сохраняется дробное состояние байтов) на несколько кадров, что в значительной степени составляет то же самое.

Удачи!

person Cameron    schedule 31.05.2012
comment
Хорошо, я думаю, что распараллелить сжатие deflate для меня становится слишком сложным/отнимающим много времени. Но разве распараллеливание не может происходить на более высоком уровне? Если я разделю изображение на несколько частей и позволю libpng сгенерировать фрагменты IDAT для каждой части, а затем склей их вместе, возникнут ли какие-либо проблемы для средства просмотра PNG? - person Pascal; 31.05.2012
comment
@Паскаль: Попробуй! :-) Но я не думаю, что это сработает, поскольку данные в чанках IDAT будут не одним сжатым потоком zlib, разделенным (как ожидалось), а несколькими конкатенированными потоками zlib. При этом вы, вероятно, могли бы удалить заголовок и нижний колонтитул zlib из каждого раздела и создать свой собственный заголовок и нижний колонтитул zlib для всех данных. Вам нужно будет объединить контрольные суммы Adler-32, но я думаю, что это действительно сработает! Хотя вам потребуется доступ к сжатым данным, прежде чем они попадут в фрагмент IDAT, я не знаю, как это сделать с помощью libpng... - person Cameron; 31.05.2012

arrow_upward
5
arrow_downward

Наконец-то я распараллелил процесс сжатия. Как упомянул Кэмерон в комментарии к его ответу, мне пришлось удалить заголовок zlib из zstreams, чтобы объединить их. Удаление нижнего колонтитула не требовалось, поскольку zlib предлагает параметр Z_SYNC_FLUSH, который можно использовать для всех фрагментов (кроме последнего, который должен быть записан с помощью Z_FINISH) для записи на границу байта. Таким образом, вы можете просто объединить выходные потоки впоследствии. В конце концов, контрольная сумма adler32 должна быть рассчитана по всем потокам и скопирована в конец объединенных z-потоков.

Если вас интересует результат, вы можете найти полное доказательство концепции по адресу https://github.com/anvio/png-parallel

person Pascal    schedule 01.07.2012