Отправляет email-рассылки с помощью сервиса Sendsay

Фрактальное сжатие изображений

Рассылка закрыта

Вы можете найти рассылки сходной тематики в Каталоге рассылок.

  Май 2010   →
 1
 2
 3
 4
 5
 6
 7
07.05.2010
06:31:56
12:08:23
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
Автор
smkibermax@inbox.ru

Статистика

3 подписчиков
0 за неделю
←   Все выпуски   →

Тестируем программу Артема Петрова.


Обзор фрактального кодека Артёма Петрова

Автор: Максим Лович - 07.05.2010
Оригинал статьи на fic.bos.ru
Статья, содержащая ссылку: http://stanislaw.ru/rus/research/fractal.asp#p2
Ссылка на архив (программа и исходники):
Внешняя ссылка на архив. Скачать архив с данного ресурса (правой кнопкой, сохранить как).

Наконец нашел время потестить реализацию фрактального кодека от Артёма Петрова.
Распаковываем архив, имеем FractalPacker.exe – консольный фрактальный энкодер, Run.bat – пример вызова консольного энкодера, FractView.exe – оконное приложение просмотра сжатого изображения, а также папка Sources, очевидно, с исходниками.
Для начала попробуем сжать что-нибудь. Открываем батник и видим следующее:

REM Параметры:
REM - имя входного файла
REM - имя выходного файла
REM - размер ранговой области
REM - шаг поиска домена
REM - точность (максимальное СКО)
REM - 1- искать лучший домен, 0 - искать  домен удовлетворяющий макс. СКО
FractPacker.exe input.bmp output.fif [8,4,0.005,1]

Что ж, все очень хорошо расписано. К сожалению, само тестовое изображение автор не приложил, поэтому возьмем стандартное изображение Lena.bmp из библиотеки Calgary Corpus. Программа, как выяснилось, работает только с True Color изображениями. Переписываем батник следующим образом:

FractPacker.exe lena.bmp lena.fif [8,4,0.005,1]

И запускаем… Сжатие идет очень долго, я успеваю выпить чашку кофе и немного вздремнуть… Но, автор об этом предупреждал: «…вариант реализации описанного выше алгоритма, который не отличаеться ни скоростью, ни высоким качеством, но тем не менее может служить несложным средством исследования…»
Что ж, пока наше изображение 512x512 пикселей, 24 бит на пиксель сжимается, попробуем взглянуть на исходники. Начнем с энкодера.

Похоже все это дело написано на VC++ 6 (кэп был здесь). Запускать студию желания нет, с учетом того, что комп нагружен сжатием. Поэтому посмотрим на них через Notepad++.

FractPacker.cpp наибольший размер имеет, с него и начнем. Видим две структуры: одна для RGB пикселя, вторая – для RGB-битмапа. Функция загрузки битмапа написана довольно грамотно, мне нравится. Добираемся до самого компрессора. Функция bool Compress(…) является основной для вызова процесса сжатия. Само сравнение ранговых блоков с доменами происходит в void CalcForRang(Square &square). Внутри нее сразу создаются 7 преобразованных копий переданного рангового блока, и начинается поиск домена.

Похоже, надо было отключить опцию «искать лучший домен» при вызове консольки, поскольку полный перебор идет для каждого рангового блока (т.е. 8-ми его копий) по всем доменным блокам. Если бы я выбрал поиск домена, удовлетворяющего максимальному СКО, то процесс шел бы быстрее. Да и шаг доменных блоков в 4 пикселя существенно увеличивает перебор, стоило поставить 16 или хотя бы 8. Ну да ладно, оценим что может данных кодер максимально при ранговых областях 8x8 пикселей.

Что здесь еще интересного?
Функция bool Square::CalcUV(const Square& square,double &U,double &V) находит коэффициенты преобразования.

bool Square::CalcUV(const Square& square,double &U,double &V)
{
            BYTE *pr,*pd;
            if (square.Div==0)
            {
                        U=0;
                        V=square.Mean;
            }
            else
            {
                        pr=pData;       
                        pd=square.pData;
                        double SumMul=0;
                        for (int i=0;i<ushBufSize;i++)
                        {
                                   SumMul+=(*pr) * (*pd);
                                   pr++;pd++;
                        };
                        U=(ushBufSize*SumMul-square.Summa*Summa)/square.Div;
                        V=(Summa-square.Summa*U)/ushBufSize;
            };

            if (U>MAX_U || U<MIN_U || V>MAX_V || V<MIN_V) return false;

            return true;
};




То есть обычные форумулы для нахождения коэффициентов изменения контраста и сдвига по яркости, минимизирующих СКО.

Далее выполняются преобразования над доменным блоком с учетом этих коэффициентов:

void Square::BrightTransform(Square & SquareUV,double U, double V)
{
            BYTE *pd=pData;
            BYTE *pdn=SquareUV.pData;

            INT Val;
            for (int i=0;i<ushBufSize;i++)
            {
                        Val=(*pd)*U+V;
                        if (Val>255) *pdn=255;
                        else if  (Val<0) *pdn=0;
                        else  *pdn=(BYTE) Val;
                        pd++;                         
                        pdn++;                       
            };
};

И считается расстояние между новыми блоками:

double Square::CalcDistance(Square& square)
{
            BYTE *p1,*p2;
            p1=pData;
            p2=square.pData;
            double Sum=0,Sl;
           
            for (int i=0;i<ushBufSize;i++)
            {
                        Sl= (INT)*p1-(INT)*p2;
                        Sum+=Sl*Sl;              
                        p1++;
                        p2++;
            }
            return Sum/(double)ushBufSize;
};

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


То есть вполне обычный (классический) процесс сжатия.

Если не не найдено подходящего доменного блока, то ранговый блок разбивается на 4 подблока (если размер подблока будет не меньше 2x2 пикселя). Реализация квадродерева.

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

Структура файла. Если дисперсия рангового блока равна нулю, то пишется значение 2 (2 бита) и среднее пикселей (8 бит). Иначе при нахождении подходящего домена записываются его координаты X и Y (количество бит в зависимости от размеров изображения и блоков (формула: log2(m_nDomainsX)). Затем записываем код аффинного преобразования (3 бита). Теперь необходимо записать коэффициенты изменения контраста (в данном случае U) и сдвига по яркости (в данном случае V). Изменение контраста преобразуется по формуле: (U * (3.3/10.0) * 127.0) и занимает не более 7 бит. Смысл в этом такой: в данной реализации установлены ограничения на коэффициенты: 0<=U<=3.0 и -255 <= V <= 255. Поэтому преобразование позволяет уложить коэффициент U в 7 бит, под V выделяется 8 бит плюс 1 бит под знак (итого 9 бит).

Примечание: в книге Ювала Фишера "Fractal Image Compression: Theory and Application" '94 говорится об оптимальном ограничении коэффициента изменения контраста в 1.2, таким образом, размер файла можно еще больше уменьшить.

Должен сказать, что качество написания кода весьма хорошее, на мой взгляд. Есть комментарии, все очень хорошо структурировано и понятно, а главное, грамотно написано. Так что данные исходники отлично подойдут для начинающий фрактальных сжимальщиков и просто для тех, кто хочет уметь правильно программировать на ЯВУ (языках высокого уровня).

Попробуйте переписать данный код для изображений в градациях серого (8 бит/пиксель), уберите часть преобразований, т.к. 8 – это много, 4-х, на мой взгляд, вполне хватит. И получится достаточно качественный скелет для дальнейшей работы. Кроме того сжимается RGB-формат изображения. Лишено смысла сжимать цветное изображение в формате RGB. Проще проверить компрессор на изображении в масштабе серого – это в три раза ускорит процесс сжатия. Цветные картинки лучше переводить в другой формат, например, YUV, и экономить время на сжатии U и V компонент.

Наконец-то дождались энкодер. Открываем изображение в просмотрщике:


Рис. Фрактальное сжатие с параметрами [8,4,0.005,1]

Таблица результатов


Компрессор 		Время сжатия
 Размер файла
 SSIM
 PSNR
Фр. [8,4,0.005,1]
 71 минута
 80 кб
 0,9222
 33,6358
Фр. [8,16,0.005,0]
 73 секунды
 86,9 кб
 0,8529
 31,9199
Фр. [8,16,0.005,1]
 135,36 секунд
 86,9 кб
 0,9121
 33,2496
JPEG
менее секунды
 97 кб
 0,9795
 44,0542
JPEG (низкое)
 менее секунды
 39,1 кб
 0.9303
 37.2824
JPEG (среднее)
 менее секунды
 49,3 кб
 0.9475
 37.2824

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


Рис. Фрактальное сжатие с параметрами [8,16,0.005,0]

MLovic_APetrovCodecTest_lena_8_16_1.png

Рис. Фрактальное сжатие с параметрами [8,16,0.005,1]


Рис. JPEG с параметрами по умолчанию (Paint)
В избранное