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

В настоящее время я пытаюсь реализовать кодер PNG в C ++ на основе 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? Большое спасибо!

Ответы на вопрос(2)

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

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

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

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

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

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

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

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

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

Удачи!

 Pascal31 мая 2012 г., 07:54
Хорошо, я полагаю, что это слишком сложно / требует много времени для распараллеливания сжатия с раздувом. Но не может ли распараллеливание произойти на более высоком уровне? Если я разделю изображение на несколько частей и позволю libpng сгенерировать фрагменты IDAT для каждой части, а затем склеить их вместе, будут ли какие-либо проблемы для программы просмотра PNG?
 31 мая 2012 г., 09:07
@Pascal: попробуй! :-) Но я не думаю, что это сработает, поскольку данные в блоках IDAT не будут разделены на один сжатый поток zlib (как и ожидалось), а объединят несколько потоков zlib. При этом вы, вероятно, могли бы удалить заголовок и нижний колонтитул zlib из каждого раздела и создать свой собственный верхний и нижний колонтитул zlib для всех данных. Вам нужно будет объединить контрольные суммы Adler-32, но я думаю, что это действительно сработает! Хотя вам понадобится доступ к сжатым данным, прежде чем они попадут в блок IDAT, я не уверен, как это сделать с помощью libpng ...
Решение Вопроса

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

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

 09 июл. 2012 г., 06:13
+1 Круто, я рад, что ты заставил его работать!

Ваш ответ на вопрос