Сжатие изображений с использованием вейвлет

    Вейвлетное сжатие — общее название класса методов кодирования изображений, использующих двумерное вейвлет-разложение кодируемого изображения. Обычно подразумевается сжатие с потерей качества. В статье не будет приведено сложных математических формул, всю теорию можно почитать по ссылкам внизу статьи. Здесь только практика!

    Отличие от JPEG


    Алгоритм JPEG, в отличие от вейвлетного, сжимает по отдельности каждый блок исходного изображения размером 8 на 8 пикселов. В результате при высоких степенях сжатия на восстановленном изображении может быть заметна блочная структура. При вейвлетном сжатии такой проблемы не возникает, но могут появляться искажения другого типа, имеющие вид «призрачной» ряби вблизи резких границ.
    Считается, что такие артефакты в среднем меньше бросаются в глаза наблюдателю, чем «квадратики», создаваемые JPEG.

    Пример


    Для примера сильно сожмем одно и тоже изображение приблизительно до одного размера:

    В начале с использованием JPEG:
    7959 байт
    (7959 байт)

    затем алгоритмом вейвлетного сжатия JPEG 2000:
    7813 байт
    (7813 байт)

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

    Еще один пример сжатия другого изображения, с сведением размера файлов до 3кб каждый:

    JPEG
    (JPEG)

    JPEG 2000
    (JPEG 2000)

    Чем это является?


    Реализованный мною метод по сути является аналогом известного алгоритма вейвлетного сжатия JPEG 2000, так и не заменившего популярного JPEG. Несколько лет назад я его релиализовал на VisualBasic6.0, но специально для понимания исходных кодов большей частью аудитории я переписал его на C#.
    В представленной реализации я использовал быстрый лифтинг дискретного биортогонального CDF 9/7 вейвлета, используемый в алгоритме сжатия изображений JPEG 2000. Реализацию на Си можно скачать здесь.

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


    Чтобы не раздувать код, я не стал переносить возможность сжатия изображений любого размера и с любым соотношением сторон. Поэтому он может сжимать только квадратные изображения, размером сторон 256х256, 512x512, 1024x1024, 2048x2048 и т.д. Также я убрал оптимизацию по использованию памяти и сохранение/считывание header-а файла с коэффициентами использованными при сжатии. Иначе код опять бы неоправданно раздулся.

    Основной сценарий сжатия:

    1. Загружаем изображение из файла;
    2. Конвертируем загруженное изображение в байтовый массив RGB-значений;
    3. Перекодируем RGB в YCrCb с квантованием итоговых цветовых компонентов;
    4. Применяем вейвлет;
    5. Переводим многомерный массив в одномерный (плоский);
    6. Сжимаем полученный поток любыми доступными средствами (например GZip).
    Коэффициенты для сжатия в представленном коде подобраны с целью получения минимального по размеру выходного файла, но с возможностью, что-то разглядеть.

    Код компрессора (C#)


    Я не являюсь асом в C#, поэтому возможно в коде есть места, где можно было воспользоваться стандартными методами .Net.

    using System;
    using System.Collections.Generic;
    using System.Text;
    using System.Drawing;
    using System.Drawing.Imaging;
    using System.Runtime.InteropServices;
    using System.IO.Compression;
    using System.IO;
    
    namespace WaveleteCompression
    {
    
        class wvCompress
        {
    
            // Константы 
            public const int WV_LEFT_TO_RIGHT = 0;
            public const int WV_TOP_TO_BOTTOM = 1;
    
            public byte[] run(string path)
            {
    
                // Загружаем изображение из файла
                Bitmap bmp = new Bitmap(path, true);
    
                // Конвертируем загруженное изображение в байтовый массив
                byte[, ,] b = this.BmpToBytes_Unsafe(bmp);
    
                // Применение вейвлета
                byte[] o = this.Compress(b, bmp.Width, bmp.Height);
    
                // Сохранение в RAW без пост-сжатия
                FileStream f = new System.IO.FileStream(path + ".raw", FileMode.Create, FileAccess.Write);
                f.Write(o, 0, o.Length);
                f.Close();
    
                // Сжатие полученного массива обычным Gzip-ом и сохранение в файл
                // Если для сжатия использовать что нить другое вместо GZIP, то можно получить файл размером еще в 2 раза меньше
                string outGZ = path + ".gz";
                FileStream outfile = new FileStream(outGZ, FileMode.Create);
                GZipStream compressedzipStream = new GZipStream(outfile, CompressionMode.Compress, true);
                compressedzipStream.Write(o, 0, o.Length);
                compressedzipStream.Close();
    
                // возвращаем несжатый GZip-ом массив
                return o;
    
            }
    
            private byte[] Compress(byte[, ,] rgb, int cW, int cH)
            {
                // Значения, для квантования коэффициентов вейвлета
                int[] dwDiv = { 48, 32, 16, 16, 24, 24, 1, 1 };
                int[] dwTop = { 24, 32, 24, 24, 24, 24, 32, 32 };
                int SamplerDiv = 2, SamplerTop = 2;
                // Проценты квантования Y, cr, cb компонентов цвета
                int YPerec = 100, crPerec = 85, cbPerec = 85;
                int WVCount = 6; // количество уровней свертки вейвлета
                // Перекодирование RGB в YCrCb
                double[, ,] YCrCb = YCrCbEncode(rgb, cW, cH, YPerec, crPerec, cbPerec, cW, cH);
                // Применяем вейвлет свертку поочередно к каждому цветовому каналу
                for (int z = 0; z < 3; z++)
                {
                    // Каждый канал сворачиваем указанное количество раз
                    for (int dWave = 0; dWave < WVCount; dWave++)
                    {
                        int waveW = Convert.ToInt32(cW / Math.Pow(2, dWave));
                        int waveH = Convert.ToInt32(cH / Math.Pow(2, dWave));
                        if (z == 2)
                        {
                            // Канал с компонентом Y квантуем на меньшее значение,
                            // т.к. в нем лежит структура изображения (яркостная составляющая), а в других каналах даныые о цветах
                            YCrCb = WaveletePack(YCrCb, z, waveW, waveH, dwDiv[dWave], dwTop[dWave], dWave);
                        }
                        else
                        {
                            YCrCb = WaveletePack(YCrCb, z, waveW, waveH, dwDiv[dWave] * SamplerDiv, dwTop[dWave] * SamplerTop, dWave);
                        }
                    }
                }
                // конвертация массива в одномерный
                byte[] flattened = doPack(YCrCb, cW, cH, WVCount);
                return flattened;
    
            }
    
            /* Процедура упаковывает массив типа Double в массив типа Byte
            За счет наличия в массиве большого количества значений умещающихся в пределы байта.
            В начале все Double приводятся к типу Short.
            Затем значения, неумещающиеся в тип байт дописываются в конец выходного потока, а заместо них в масив байтов
            записывается значение 255 */
            private byte[] doPack(double[, ,] ImgData, int cW, int cH, int wDepth)
            {
                short Value;
                int lPos = 0;
                int size = cW * cH * 3;
                // резервирование для short значений
                int intCount = 0;
                short[] shorts = new short[size];
                byte[] Ret = new byte[size];
                // проход массива постепенно по вейвлет-уровням
                for(int d = wDepth-1; d >= 0; d--)
                {
                    int wSize = (int)Math.Pow(2f, Convert.ToDouble(d));
                    int W = cW / wSize;
                    int H = cH / wSize;
                    int w2 = W / 2;
                    int h2 = H / 2;
                    // левый верхний угол
                    if (d == wDepth - 1)
                    {
                        for (int z = 0; z < 3; z++)
                        {
                            for (int j = 0; j < h2; j++)
                            {
                                for (int i = 0; i < w2; i++)
                                {
                                    Value = (short)Math.Round(ImgData[z, i, j]);
                                    if ((Value >= -127) && (Value <= 127))
                                    {
                                        Ret[lPos++] = Convert.ToByte(Value + 127);
                                    }
                                    else
                                    {
                                        Ret[lPos++] = 255;
                                        shorts[intCount++] = Value;
                                    }
                                }
                            }
                        }
                    }
                    // правый верхний + правый нижний
                    for (int z = 0; z < 3; z++)
                    {
                        for (int j = 0; j < H; j++)
                        {
                            for (int i = w2; i < W; i++)
                            {
                                Value = (short)Math.Round(ImgData[z, i, j]);
                                if ((Value >= -127) && (Value <= 127))
                                {
                                    Ret[lPos++] = Convert.ToByte(Value + 127);
                                }
                                else
                                {
                                    Ret[lPos++] = 255;
                                    shorts[intCount++] = Value;
                                }
                            }
                        }
                    }
                    // левый нижний
                    for (int z = 0; z < 3; z++)
                    {
                        for (int j = h2; j < H; j++)
                        {
                            for (int i = 0; i < w2; i++)
                            {
                                Value = (short)Math.Round(ImgData[z, i, j]);
                                if ((Value >= -127) && (Value <= 127))
                                {
                                    Ret[lPos++] = Convert.ToByte(Value + 127);
                                }
                                else
                                {
                                    Ret[lPos++] = 255;
                                    shorts[intCount++] = Value;
                                }
                            }
                        }
                    }
                }
                // склеивание двух массивов (byte[] и short[]) в один
                int shortArraySize = intCount * 2;
                Array.Resize(ref Ret, Ret.Length + shortArraySize);
                Buffer.BlockCopy(shorts, 0, Ret, Ret.Length - shortArraySize, shortArraySize);
                // возвращаем результирующий плоский массив
                return Ret;
            }
    
            private double[, ,] WaveletePack(double[, ,] ImgArray, int Component, int cW, int cH, int dwDevider, int dwTop, int dwStep)
            {
                short Value;
                int cw2 = cW / 2;
                int cH2 = cH / 2;
                // подсчет коэффициента квантования
                double dbDiv = 1f / dwDevider;
                ImgArray = Wv(ImgArray, cW, cH, Component, WV_TOP_TO_BOTTOM);
                ImgArray = Wv(ImgArray, cH, cW, Component, WV_LEFT_TO_RIGHT);
                // квантование
                for (int j = 0; j < cH; j++)
                {
                    for (int i = 0; i < cW; i++)
                    {
                        if ((i >= cw2) || (j >= cH2))
                        {
                            Value = (short)Math.Round(ImgArray[Component, i, j]);
                            if (Value != 0)
                            {
                                int value2 = Value;
                                if (value2 < 0) { value2 = -value2; }
                                if (value2 < dwTop)
                                {
                                    ImgArray[Component, i, j] = 0;
                                }
                                else
                                {
                                    ImgArray[Component, i, j] = Value * dbDiv;
                                }
                            }
                        }
                    }
                }
                return ImgArray;
            }
    
            // Быстрый лифтинг дискретного биортогонального CDF 9/7 вейвлета
            private double[, ,] Wv(double[, ,] ImgArray, int n, int dwCh, int Component, int Side)
            {
    
                double a;
                int i, j, n2 = n / 2;
                double[] xWavelet = new double[n];
                double[] tempbank = new double[n];
    
                for (int dwPos = 0; dwPos < dwCh; dwPos++)
                {
                    if (Side == WV_LEFT_TO_RIGHT)
                    {
                        for (j = 0; j < n; j++) {
                            xWavelet[j] = ImgArray[Component, dwPos, j];
                        }
                    }
                    else if (Side == WV_TOP_TO_BOTTOM)
                    {
                        for (i = 0; i < n; i++) {
                            xWavelet[i] = ImgArray[Component, i, dwPos];
                        }
                    }
    
                    // Predict 1
                    a = -1.586134342f;
                    for (i = 1; i < n - 1; i += 2) {
                        xWavelet[i] += a * (xWavelet[i - 1] + xWavelet[i + 1]);
                    }
    
                    xWavelet[n - 1] += 2 * a * xWavelet[n - 2];
    
                    // Update 1
                    a = -0.05298011854f;
                    for (i = 2; i < n; i += 2) {
                        xWavelet[i] += a * (xWavelet[i - 1] + xWavelet[i + 1]);
                    }
                    xWavelet[0] += 2 * a * xWavelet[1];
    
                    // Predict 2
                    a = 0.8829110762f;
                    for (i = 1; i < n - 1; i += 2) {
                        xWavelet[i] += a * (xWavelet[i - 1] + xWavelet[i + 1]);
                    }
                    xWavelet[n - 1] += 2 * a * xWavelet[n - 2];
    
                    // Update 2
                    a = 0.4435068522f;
                    for (i = 2; i < n; i += 2) {
                        xWavelet[i] += a * (xWavelet[i - 1] + xWavelet[i + 1]);
                    }
                    xWavelet[0] += 2 * a * xWavelet[1];
    
                    // Scale
                    a = 1f / 1.149604398f;
                    j = 0;
    
                    // умножаем нечетные на коэффициент "а"
                    // делим четные на коэффициент "а"
                    if (Side == WV_LEFT_TO_RIGHT)
                    {
                        for (i = 0; i < n2; i++) {
                            ImgArray[Component, dwPos, i] = xWavelet[j++] / a;
                            ImgArray[Component, dwPos, n2 + i] = xWavelet[j++] * a;
                        }
                    }
                    else if (Side == WV_TOP_TO_BOTTOM)
                    {
                        for (i = 0; i < n2; i++) {
                            ImgArray[Component, i, dwPos] = xWavelet[j++] / a;
                            ImgArray[Component, n2 + i, dwPos] = xWavelet[j++] * a;
                        }
                    }
    
                }
                return ImgArray;
            }
    
            // Метод перекодирования RGB в YCrCb
            private double[, ,] YCrCbEncode(byte[, ,] BytesRGB, int cW, int cH, double Ydiv, double Udiv, double Vdiv, int oW, int oH)
            {
                double vr, vg, vb;
                double kr = 0.299, kg = 0.587, kb = 0.114, kr1 = -0.1687, kg1 = 0.3313, kb1 = 0.5, kr2 = 0.5, kg2 = 0.4187, kb2 = 0.0813;
                Ydiv = Ydiv / 100f;
                Udiv = Udiv / 100f;
                Vdiv = Vdiv / 100f;
                double[, ,] YCrCb = new double[3, cW, cH];
                for (int j = 0; j < oH; j++)
                {
                    for (int i = 0; i < oW; i++)
                    {
                        vb = (double)BytesRGB[0, i, j];
                        vg = (double)BytesRGB[1, i, j];
                        vr = (double)BytesRGB[2, i, j];
                        YCrCb[2, i, j] = (kr * vr + kg * vg + kb * vb) * Ydiv;
                        YCrCb[1, i, j] = (kr1 * vr - kg1 * vg + kb1 * vb + 128) * Udiv;
                        YCrCb[0, i, j] = (kr2 * vr - kg2 * vg - kb2 * vb + 128) * Udiv;
                    }
                }
                return YCrCb;
            }
    
            private unsafe byte[, ,] BmpToBytes_Unsafe(Bitmap bmp)
            {
                BitmapData bData = bmp.LockBits(new Rectangle(new Point(), bmp.Size), ImageLockMode.ReadOnly, PixelFormat.Format24bppRgb);
                // number of bytes in the bitmap
                int byteCount = bData.Stride * bmp.Height;
                byte[] bmpBytes = new byte[byteCount];
                Marshal.Copy(bData.Scan0, bmpBytes, 0, byteCount); // Copy the locked bytes from memory
                // don't forget to unlock the bitmap!!
                bmp.UnlockBits(bData);
                byte[, ,] ret = new byte[3, bmp.Width, bmp.Height];
                for (int z = 0; z < 3; z++)
                {
                    for (int i = 0; i < bmp.Width; i++)
                    {
                        for (int j = 0; j < bmp.Height; j++)
                        {
                            ret[z, i, j] = bmpBytes[j * bmp.Width * 3 + i * 3 + z];
                        }
                    }
                }
                return ret;
            }
    
        }
    }

    Код декомпрессора


    Естественно декомпрессор делает все в обратном порядке.
    Как я уже писал выше, в угоду читабельности кода я не стал делать сохранение в файл header-а.
    Поэтому в методе run() жестко забиты размеры декодируемого изображения и коэффициенты для декодирования вейвлета.

    using System;
    using System.Collections.Generic;
    using System.Text;
    
    namespace WaveleteCompression
    {
        class wvDecompress
        {
    
            // Константы
            public const int WV_LEFT_TO_RIGHT = 0;
            public const int WV_TOP_TO_BOTTOM = 1;
    
            public byte[] run(byte[] compressed)
            {
                int z;
                int dwDepth = 6; // количество уровней свертки вейвлета (чем их больше, тем лучше жмется)
                // жестко забитые размеры изображения
                int w = 512;
                int h = 512;
                // по сути размер изображения и вот эти коэффициенты должны браться из заголовка(header) сжатого файла
                int[] dwDiv = { 48, 32, 16, 16, 24, 24, 1, 1 }, dwTop = { 24, 32, 24, 24, 24, 24, 32, 32 };
                int SamplerDiv = 2, YPerec = 100, crPerec = 85, cbPerec = 85;
    
                double[,,] yuv = doUnPack(compressed, w, h, dwDepth);
    
                // Развертка вейвлета
                for(z = 0; z < 2; z++)
                {
                    for(int dWave = dwDepth - 1; dWave >= 0; dWave--)
                    {
                        int w2 = Convert.ToInt32(w / Math.Pow(2, dWave));
                        int h2 = Convert.ToInt32(h / Math.Pow(2, dWave));
                        WaveleteUnPack(yuv, z, w2, h2, dwDiv[dWave] * SamplerDiv);
                    }
                }
                z = 2;
                for(int dWave = dwDepth - 1; dWave >= 0; dWave--)
                {
                    int w2 = Convert.ToInt32(w / Math.Pow(2, dWave));
                    int h2 = Convert.ToInt32(h / Math.Pow(2, dWave));
                    WaveleteUnPack(yuv, z, w2, h2, dwDiv[dWave]);
                }
                // YCrCb декодирование + разложение изображения в плоский массив
                byte[]  rgb_flatened = this.YCrCbDecode(yuv, w, h, YPerec, crPerec, cbPerec);
                return rgb_flatened;
            }
    
            // Данная процедура является обратной процедуре DoPack в классе wvCompress.
            // Она обратно переводит его в (short)double-тип из типа byte[]
            private static double[, ,] doUnPack(byte[] Bytes, int cW, int cH, int dwDepth)
            {
                int lPos = 0;
                byte Value;
                int intIndex = 0;
                // размер итогового изображения в байтах
                int size = cW * cH * 3;
                // временный массив для результирующих коэффициентов свернутого вейвлета
                double[,,] ImgData = new double[3, cW, cH];
    
                int shortsLength = Bytes.Length - size;
                short[] shorts = new short[shortsLength / 2];
                Buffer.BlockCopy(Bytes, size, shorts, 0, shortsLength);
    
                for (int d = dwDepth - 1; d >= 0; d--)
                {
                    int wSize = (int)Math.Pow(2, d);
                    int W = cW / wSize;
                    int H = cH / wSize;
                    int w2 = W / 2;
                    int h2 = H / 2;
                    // левый верхний
                    if (d == dwDepth - 1)
                    {
                        for (int z = 0; z < 3; z++)
                        {
                            for (int j = 0; j < h2; j++)
                            {
                                for (int i = 0; i < w2; i++)
                                {
                                    Value = Bytes[lPos++];
                                    if(Value == 255)
                                    {
                                        ImgData[z, i, j] = shorts[intIndex++];
                                    }
                                    else
                                    {
                                        ImgData[z, i, j] = Value - 127;
                                    }
                                }
                            }
                        }
                    }
                    // верхний правый + нижний правый
                    for (int z = 0; z < 3; z++)
                    {
                        for (int j = 0; j < H; j++)
                        {
                            for (int i = w2; i < W; i++)
                            {
                                Value = Bytes[lPos++];
                                if(Value == 255)
                                {
                                    ImgData[z, i, j] = shorts[intIndex++];
                                } else {
                                    ImgData[z, i, j] = Value - 127;
                                }
                            }
                        }
                    }
                    // левый нижний
                    for (int z = 0; z < 3; z++)
                    {
                        for (int j = h2; j < H; j++)
                        {
                            for (int i = 0; i < w2; i++)
                            {
                                Value = Bytes[lPos++];
                                if (Value == 255)
                                {
                                    ImgData[z, i, j] = shorts[intIndex++];
                                }
                                else
                                {
                                    ImgData[z, i, j] = Value - 127;
                                }
                            }
                        }
                    }
                }
                // возвращаем результат
                return ImgData;
            }
    
            // Функция развертки вейвлета
            private void WaveleteUnPack(double[,,] ImgArray, int Component, int cW, int cH, int dwDevider)
            {
                int cw2 = cW / 2, ch2 = cH / 2;
                double dbDiv = 1f / dwDevider;
                // деквантование значений
                for(int i = 0; i < cW; i++)
                {
                    for(int j = 0; j < cH; j++)
                    {
                        if ((i >= cw2) || (j >= ch2))
                        {
                            if (ImgArray[Component, i, j] != 0)
                            {
                                ImgArray[Component, i, j] /= dbDiv;
                            }
                        }
                    }
                }
                // Развертка вейвлета
                for(int i = 0; i < cW; i++)
                {
                    reWv(ref ImgArray, cH, Component, i, WV_LEFT_TO_RIGHT);
                }
                for(int j = 0; j < cH; j++)
                {
                    reWv(ref ImgArray, cW, Component, j, WV_TOP_TO_BOTTOM);
                }
            }
    
            // Процедура обратного быстрого лифтинга дискретного биортогонального CDF 9/7 вейвлета
            private void reWv(ref double[, ,] shorts, int n, int z, int dwPos, int Side)
            {
    
                double a;
                double[] xWavelet = new double[n];
                double[] tempbank = new double[n];
    
                if(Side == WV_LEFT_TO_RIGHT)
                {
                    for(int j = 0; j < n; j++)
                    {
                        xWavelet[j] = shorts[z, dwPos, j];
                    }
                }
                else if (Side == WV_TOP_TO_BOTTOM)
                {
                    for(int  i = 0; i < n; i++)
                    {
                        xWavelet[i] = shorts[z, i, dwPos];
                    }
                }
    
                for(int i = 0; i < n / 2; i++)
                {
                    tempbank[i * 2] = xWavelet[i];
                    tempbank[i * 2 + 1] = xWavelet[i + n / 2];
                }
                for(int i = 0; i < n; i++)
                {
                    xWavelet[i] = tempbank[i];
                }
    
                // Undo scale
                a = 1.149604398f;
                for(int  i = 0; i < n; i++)
                {
                    if(i % 2 != 0)
                    {
                        xWavelet[i] = xWavelet[i] * a;
                    } else {
                        xWavelet[i] = xWavelet[i] / a;
                    }
                }
    
                // Undo update 2
                a = -0.4435068522f;
                for (int i = 2; i < n; i += 2)
                {
                    xWavelet[i] = xWavelet[i] + a * (xWavelet[i - 1] + xWavelet[i + 1]);
                }
                xWavelet[0] = xWavelet[0] + 2 * a * xWavelet[1];
    
                // Undo predict 2
                a = -0.8829110762f;
                for (int i = 1; i < n - 1; i += 2)
                {
                    xWavelet[i] = xWavelet[i] + a * (xWavelet[i - 1] + xWavelet[i + 1]);
                }
                xWavelet[n - 1] = xWavelet[n - 1] + 2 * a * xWavelet[n - 2];
    
                // Undo update 1
                a = 0.05298011854f;
                for (int i = 2; i < n; i += 2)
                {
                    xWavelet[i] = xWavelet[i] + a * (xWavelet[i - 1] + xWavelet[i + 1]);
                }
                xWavelet[0] = xWavelet[0] + 2 * a * xWavelet[1];
    
                // Undo predict 1
                a = 1.586134342f;
                for (int i = 1; i < n - 1; i += 2)
                {
                    xWavelet[i] = xWavelet[i] + a * (xWavelet[i - 1] + xWavelet[i + 1]);
                }
                xWavelet[n - 1] = xWavelet[n - 1] + 2 * a * xWavelet[n - 2];
    
                if(Side == WV_LEFT_TO_RIGHT)
                {
                    for (int j = 0; j < n; j++)
                    {
                        shorts[z, dwPos, j] = xWavelet[j];
                    }
                }
                else if(Side == WV_TOP_TO_BOTTOM)
                {
                    for(int i = 0; i < n; i++)
                    {
                        shorts[z, i, dwPos] = xWavelet[i];
                    }
                }
            }
    
            // Метод перекодирования YCrCb в RGB
            private byte[] YCrCbDecode(double[, ,] yuv, int w, int h, double Ydiv, double Udiv, double Vdiv)
            {
                byte[] bytes_flat = new byte[3 * w * h];
                double vr, vg, vb;
                double vY, vCb, vCr;
                Ydiv = Ydiv / 100f;
                Udiv = Udiv / 100f;
                Vdiv = Vdiv / 100f;
                for(int j = 0; j < h; j++)
                {
                    for (int i = 0; i < w ; i++)
                    {
                        vCr = yuv[0, i, j] / Vdiv;
                        vCb = yuv[1, i, j] / Udiv;
                        vY = yuv[2, i, j] / Ydiv;
                        vr = vY + 1.402f * (vCr - 128f);
                        vg = vY - 0.34414f * (vCb - 128f) - 0.71414f * (vCr - 128f);
                        vb = vY + 1.722f * (vCb - 128f);
                        if (vr > 255) {vr = 255;}
                        if (vg > 255) {vg = 255;}
                        if (vb > 255) {vb = 255;}
                        if (vr < 0) {vr = 0;}
                        if (vg < 0) {vg = 0;}
                        if (vb < 0) {vb = 0;}
                        bytes_flat[j * w * 3 + i * 3 + 0] = (byte)vb;
                        bytes_flat[j * w * 3 + i * 3 + 1] = (byte)vg;
                        bytes_flat[j * w * 3 + i * 3 + 2] = (byte)vr;
                    }
                }
                return bytes_flat;
            }
    
        }
    }


    Исходные коды проекта на C#



    github

    Ссылки

    1. Вейвлет
    2. Сжатие с использованием вейвлет
    3. JPEG 2000
    4. JPEG
    5. Дискретное вейвлет-преобразование
    6. Lifting scheme
    UPD:
    mikhanoid: 1.149604398, -0.4435068522, -0.8829110762 и т.д. — коэффиценты из значений функций вейвлет-базиса в определённых точках. Почитать в общем виде: Lifting scheme
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 77

      –17
      Спрячьте, пожалуйста, картинки под кат — не у всех быстрые и безлимитные интернеты.
        +4
        Средний размер страницы в интернете — порядка 30 Кб.
        Размеры картинок в статье — по 50 Кб (мелкие не беру в рассчет).
        Итого просмотр картинок обошелся вам в просмотр трех страниц — ну, очень много, чесслово :-)

        P.S. А отключать картинки не судьба?
          +29
          В статье про сжатие изображений, фраза про то, что стоит прятать сжатые картинки под кат, вам кажется нормальной?
            –7
            Грустно когда не могут уловить юмор =\

            Тема и результат интересный, с точки зрения практики уже не актуальный.
              +5
              медленный небезлимитный интернет = у вас нет интернета
              +2
              Надо все-таки подшаманить алгоритм, чтобы картинки снизу вверх подгружались, для небыстрого интернета :)
              • UFO just landed and posted this here
                +4
                Средний размер страницы в интернете — порядка 30 Кб.
                Вы меня сейчас сильно удивили. Это исследование или ваше ощущение, потому что мои ощущения, что эта цифра больше на порядок.
                  0
                  Видимо имелся ввиду желаемый максимум.

                  Лет 5 назад читал статью art_lomov, в ней он оперировал такими же цифрами, если я сейчас не путаю.
                    0
                    Думаю, лет 5 назад желаемый максимум был сильно ниже. С тех пор каналы расширились и безлимит подешевел.
                    +1
                    Не поверите =)
                    Размер текущей страницы 36 676 байт + 2 картинки в общей сумме 36 676 байт
                    Похоже человек проверил перед тем как сказать.
                      0
                      Картинки в общей сумме 1 042 814 байт
                        0
                        Я про средний.
                        0
                        Я вот, кстати, производил замеры год назад.

                        Медианный размер страницы, по 200 000 сайтам в рунете: 27 679 символов.
                          0
                          Я не понял что вы считали. Какие символы? Это был UTF-8? Однобайтовые кодировки? Вы считали объём текста или учитывали полный размер страницы?
                            0
                            Полный объем страницы (со всей разметкой).

                            Считал в символах, как раз чтобы избежать вопросов с кодировкой. Соответственно, в CP1251 это составило 27,796 байт (с записью отсутствующих символов энтитями), в UTF-8 составило 31,241 байт (поскольку русскоязычные страницы).
                              0
                              Уточню: страница — это размер тела HTTP-ответа. То есть весь HTML (или что там). Без заголовков, но и без запроса и подсчета зависимостей — скриптов, css, картинок.
                                0
                                А, ну так надо полную страницу, а не просто весь текст. Ведь никто не грузит страницу без всех зависимостей, разве нет?
                                  +1
                                  Перечитайте комментарий, с которого вы сами начали эту ветку. Страница отдельно, картинки отдельно. Как бы-то ни было, размер не отличается «на порядок».
                                    0
                                    Как бы-то ни было, размер не отличается «на порядок».
                                    Это вряд ли.

                                    webo.in/articles/habrahabr/43-average-web-page-growth/

                                    «Размер средней веб-страницы увеличился более чем втрое с 2003 года. С 2003 по 2008 годы она увеличилась в размере с 93,7Кб до более 312Кб (см. рисунок 1)».
                                      0
                                      * пожимает плечами *

                                      Возьмите и сами посчитайте; это несложно.
                                    0
                                    Если уж сильно хочется, можете добавить медианный размер стилей и ява-скрипта — около 8 Кб.
                        +2
                        1) отключи картинки в браузере
                        2) используй загрузку изображений только из кэша
                        3) подгружай необходимые изображения по мере надобности
                        4)…
                        5) PROFIT!!!
                          +3
                          Слишком тонко :)
                          +2
                          А где же одно из главных отличий сжатия на основе вейвлетов — возможность получать результат постепенно, увеличивая детализацию с приходом новых данных?

                          А еще где-то я слышал, что гугл этим делом балуется для своих сервисов вроде просмотра пдфов в гдоках, так что может не такое оно уже и непопулярное:)
                            +1
                            А jpeg 2000 поддерживается браузерами?
                              0
                              Не знаю учитывая возраст стандарта не удивлюсь этому. Попробуйте а то у меня только мобильный девайс под рукой.
                                +2
                                Я слышал только о нативной поддержке (без плагинов) только WebKit.
                                +1
                                А для этого жать результаты преобразования нужно не GZip'ом. Например, как это сделано в EZW или SPIHT кодерах. Gzip тут совсем не в тему.
                                  0
                                  Не совсем понял при чем тут GZip. Тот же SPIHT как раз на вейвлетах и основан, а гзип — это универсальный алгоритм для всего и вся.
                                    0
                                    В кодеке, исходники которого приведены в статье, все в результате жмется именно gzip'ом )
                                      0
                                      А… я просто Ваш коммент как прямой ответ на свой коммент прочитал и долго думал, где я упомянул гзип:)
                                    0
                                    Если сжимать чем-то другим, то пришлось бы в листинг добавить кучу кода. Я же хотел его оставить минимальным.
                                      0
                                      Вам предложение — код перенести на GitHub, а в статье дать обзорное описание метода сжатия вейвлетами. Пелена кода не способствует быстрому пониманию среди новичков, а GitHub по-любому удобнее Хабра для работы с кодом.
                                        0
                                        Это уже будет совсем другая статья. Хорошо, я попробую ее написать в ближайшее время. Как вижу, тема многим интересна.
                                    0
                                    >А где же одно из главных отличий сжатия на основе вейвлетов — возможность получать результат
                                    >постепенно, увеличивая детализацию с приходом новых данных?

                                    А как progressive jpeg связан с вейвлетами?
                                      +1
                                      А кто сказал, что он связан? Похожий результат не значит одинаковые алгоритмы. Подходы то различные кардинально. Вот Вам ссылочка на статью со сравнением: статья
                                    –5
                                    Ответьте пожалуйста на вопрос, почему в тексте указаны размеры ~7.8, а на самом деле,

                                    Первый 7,8 KБ (7 959 байт)
                                    второй 55 KБ (55 361 байт)

                                      +10
                                      Это наверно потому, что второй тоже в jpg, чтобы любой браузер понял и показал. Будь он в JPEG2000, было бы все как надо, но посмотреть мы не смогли бы.
                                        +9
                                        По-хорошему, хотя бы картинку в jpeg2k стоило бы в png потом пережать, чтобы и браузер без сомнений показал, и качество именно jpeg2k увидеть, не боясь, что обычный jpeg к ней добавит ещё чего-то от себя.
                                          0
                                          Я его сжал с качеством 98%, поэтому картинка вполне достоверная.
                                          0
                                          Совершенно верно.
                                        +1
                                        Вы бы написали что такое вейвлет, немного про Добеши. Задача сжатия картинки вейвлетами Добеши различных степеней у меня была на третьем курсе.
                                          0
                                          Всю теорию можно почитать по ссылкам внизу статьи. Здесь только практика.
                                            +2
                                            Скажу честно: в википедии теория крайне скупа и, глядя на ваш код, лично мне весьма сложно понять, что к чему и где можно найти «почему так».
                                          +3
                                          А что такое «быстрый лифтинг дискретного биортогонального CDF 9/7 вейвлета»?
                                            +4
                                            Это особая форма алгоритма подсчёта коэффицентов. Вообще, автору минус, ибо не понятно, к чему эти полукилометровые листинги без объяснения того, что же они делают. Там математика не такая уж и сложная.
                                              +1
                                              Скажите, а есть более подробные статьи по этой теме? Например, код быстрого лифтинга изобилует всяческими a = -1.586134342f; Что это? Почему?
                                                +1
                                                Это коэффиценты из значений функций вейвлет-базиса в определённых точках. А почитать, конечно, есть, даже в общем виде: en.wikipedia.org/wiki/Lifting_scheme
                                                  0
                                                  Как раз оно и есть.
                                                    0
                                                    Я чуть выше уже отмечал, что общие пояснения мало что объясняют. Меня интересует «подноготная», что за вейвлет-базис, что за функции базиса. Если вы даете ответы, скажите, вы действительно нашли их в материале по той ссылке, которую дали мне?
                                                      0
                                                      Ну, я же предполагал, что Вам про вэйвлет-преобразование известно, но не известно про схемы лифтинга. В этой статье на Википедии есть хорошая ссылка «Comprehencive introduction...», где многое объясняется. Но если Вам вообще про вейвлеты надо, то эта тематика так и называется: вейвлет-преобразование. Про него много в интернете. Топикстартеру, конечно, надо бы было хотя бы некие базовые вещи написать.
                                                        0
                                                        Понял, спасибо за наводку.
                                              +6
                                              Жаль, что jpeg2000 так и не поддержали браузеры, очень интересный и удобный формат для изображений, не говоря уже о лучшем визуальном качестве.

                                              На сколько я знаю, его сейчас активно используют в различных ММО играх, где контент создают сами пользователи, например SecondLife. Благодаря возможности постепенно увеличивать детализацию по мере подгрузки, текстуры на объектах появляются почти сразу, и со временем становятся четче.

                                              Правда для реализации «прогрессивной» загрузки поток после вейвлет преобразования организуют особым образом: сначала идут старшие биты низких частот, потом младшие биты низких частот, затем идут более высокие частоты и так далее. На любом этапе загрузку можно остановить и получить законченную картинку с нужной детализацией. То есть можно ограничивать качество загружаемых текстур непосредственно на клиенте, в то время как на сервере будет только один файл.
                                                0
                                                Браузеры (а пока это лишь Chrome и Opera) поддерживают WebP, тоже вроде неплохой вариант.
                                                А в играх я ещё встречал JNG — jpeg в контейнере png, который позволяет сохранять прозрачность и др.
                                                +1
                                                приложите, пожалуйста, рядом с jpeg / jpeg 2000 результаты работы вашего алгоритма. Или результат полностью идентичен jpeg 2000?
                                                  0
                                                  Результаты очень схожи.
                                                    +2
                                                    Хотелось бы увидеть результат, одно дело на словах, совсем другое дело увидеть глазами. Еще не совсем понятно (может я придираюсь), почему изображения к статье сжаты по схеме 5/3 если речь идет о 9/7? Возможно вы использовали кодер основанный на референсном JasPer, он по умолчанию использует для сжатия с потерями и без целочисленное преобразование 5/3, для 9/7 нужно использовать параметр mode=real, правда не все программы использующие эту реализацию кодера позволяют применить дополнительные параметры. Реализация кодера от Kakadu Software, на мой взгляд, лучшая как по скорости, так и по качеству сжатия, этот кодер используется в ACDSee, которая по качеству сжатия заняла первое место в сравнении кодеков JPEG2000 от MSU Graphics & Media Lab.
                                                      0
                                                      Я использовал лишь тот листинг на Си, на который есть ссылка в статье.
                                                        0
                                                        CDF 5/3 в JPEG2000 используется для безпотерьного сжатия. Для сжатия с потерями в нем используется как раз 9/7
                                                          +2
                                                          Стандарт не обязывает использовать исключительно 9/7 для сжатия с потерями. Многие кодеры используют 5/3 для сжатия без потерь и с потерями. В частности JasPer по умолчанию использует 5/3 в обоих случаях (о чем я и написал), если не указать явно какое преобразование использовать.

                                                          image
                                                          Разница не очень большая, но она есть.
                                                            0
                                                            Согласен, просто я имел в виду стандарт JPEG 2000.
                                                            The JPEG 2000 compression standard uses the biorthogonal CDF 5/3 wavelet (also called the LeGall 5/3 wavelet) for lossless compression and a CDF 9/7 wavelet for lossy compression.
                                                            en.wikipedia.org/wiki/Cohen-Daubechies-Feauveau_wavelet
                                                        0
                                                        Тоже интересно посмотреть.
                                                        А размеры тоже очень похожи?
                                                          +1
                                                          Да. Естественно заменив GZip на более серьезный компрессор.

                                                          Вот сравнение, правда при сжатии в JPEG 2000 не получилось сжать до точно такого-же размера. Разница составила 165 байт.


                                                          (JPEG 2000, 9 409 байт)


                                                          (представленный здесь алгоритм, 9 244 байта)
                                                            0
                                                            В данном случае в качестве пост-компрессора я использовал алгоритм Eliminator, затем LZMA.
                                                      0
                                                      Так я не понял, какой вывод — jpg на сайте можно пережимать или нет?)
                                                      +11
                                                      Раз уже такой случай, разрешите и мне тоже пропиариться:
                                                      EPSILON — (Yet Another Wavelet Coder) — epsilon-project.sourceforge.net/

                                                      1. Библиотека используется в GIS-движке GDAL:
                                                      www.gaia-gis.it/raster_benchmark/color-ortho-epsilon.html
                                                      www.gdal.org/frmt_epsilon.html

                                                      2. Поддерживает ~30 вейвлетных фильтров (в том числе фильтр Добеши 9/7 упомянутый в статье)

                                                      3. Работает с изображениями любой формы и любого размера (>>4Gb)

                                                      4. Три механизма распараллеливания:
                                                      — можно собрать многопоточную версию (POSIX threads)
                                                      — можно собрать MPI-версию (протестировано на реальном кластере в МГУ)
                                                      — можно собрать кластерную версию (простой TCP-демон)

                                                      Также можно собрать обычную однопоточную последовательную версию без наворотов

                                                      5. Лицензия LGPL3

                                                      6. Есть тесты на Perl для каждого из билдов.

                                                      7. Можно заранее указывать желаемую степень сжатия.

                                                      8. Есть официальные DEBы для Debain & Ubuntu, есть RPM-ы для шапочек

                                                        0
                                                        Жму руку! У вас есть все. Интересно будет поковырять сырцы.
                                                          +1
                                                          Спасибо! Будут вопросы — предложения, обращайтесь)
                                                          +1
                                                          Если кому интересно, то есть LGPL библиотека для вейвлетного сжатия (не в JPEG2000):
                                                          www.libpgf.org
                                                          Свой код можно не открывать, если указали в About, что используете PGF.
                                                            0
                                                            Спасибо за инфо, надо посмотреть
                                                          +2
                                                          есть такая книжка «Вейвлеты в компьютерной графике»

                                                          скачать можно, например, здесь
                                                            0
                                                            А можно поинтересоваться — каков смысл данной статьи? «Вейвлеты для самых маленьких»?
                                                            Про теорию не рассказано, нормального сравнения с другими алгоритмами нет.
                                                            ИМХО данную статью можно на code.google.com постить, а не на хабр.
                                                              0
                                                              Я чота не понял, а чем собс-но гоголькод не угодил-то?
                                                                0
                                                                Да гуглькод не причем. Просто личные проектики нужно хостить на нем и ему подобных.

                                                            Only users with full accounts can post comments. Log in, please.