Открыть список
Как стать автором
Обновить

SSP — Собственный алгоритм сжатия изображений без потерь

Алгоритмы
Наконец–то появилась возможность опубликовать разработанный мною когда-то алгоритм. Алгоритм был разработан для программы автоматического снятия скриншотов. Для удобства дальнейшего его описания буду называть его – SSP (sciner screenshot packer). SSP можно справедливо сопоставить PNG, поэтому в статье я буду проводить сравнения именно с ним.

Алгоритм имеет два режима компресии:
  1. без потерь – в котором, изображения после декомпресии будет восстановлено с точностью до бита;
  2. с потерями – который не уменьшает качества картинки, просто в нем непосредственно перед сжатием, изображение переводится палитру YcbCr
    Только лишь за счет изменения палитры удается существенно улучшить сжатие. Использую следующие коэффициенты:
    cY = 0.30078125 * R + 0.5859375 * G + 0.11328125 * B
    cCb = -0.171875 * R - 0.33984375 * G + 0.51171875 * B + 128
    cCr = 0.51171875 * R - 0.4296875 * G - 0.08203125 * B + 128
Если попробовать сжать тестовую картинку –
image
Получим следующие результаты:
183 960 – Размер оригинального PNG–файла
155 932 – SSP (сжатие происходит за 0,2 секунды)
122 593 – SSP (lossy, с потерями)

Очень интересные результаты получаются при сжатии следующего изображения.
www.libpng.org/pub/png/img_png/16million-pschmidt.png
59852 – PNG
1428 – SSP

Алгоритм содержит следующие этапы:
  1. Изображение декодируется в RGB массив;
  2. Если выбран режим с потерями, то производится перекодировка в палитру YcbCr;
  3. Производится фильтрация изображения фильтром Paeth (предсказание значения по простой линейной функции);
  4. Удаление повторяющихся пикселей не особо сложным способом:
    For i = 4 To UBound(ByteArray) Step 4<br/>
    R = ByteArray(i + 0)<br/>
    g = ByteArray(i + 1)<br/>
    b = ByteArray(i + 2)<br/>
    If Not (lR = R And Lg = g And lB = b) Or (Cnt >= MAX_ITERATE) Then<br/>
    If Cnt = MAX_ITERATE Then Cnt = 0<br/>
    ByteArray(pos + 0) = lR<br/>
    ByteArray(pos + 1) = Lg<br/>
    ByteArray(pos + 2) = lB<br/>
    ByteArray(pos + 3) = Cnt<br/>
    lR = R<br/>
    Lg = g<br/>
    lB = b<br/>
    pos = pos + 4<br/>
    Cnt = 1<br/>
    Else<br/>
    Cnt = Cnt + 1<br/>
    End If<br/>
    Next
  5. кодирование BWT (Преобразование Барроуза — Уилера), а именно — лучшая в мире реализация – Архон, автор — Дмитрий Малышев;
  6. Далее идет моя функция, убирающая из полученного после предыдущего шага самый часто используемый байт и строящая битовую карту позиций, откуда убирали этот байт. Этот этап прогоняется 3 раза (экспериментально подобранное значение);

    Dim i As Long
    Dim iCnt As Long
    Dim SizeStream() As Byte
    Dim NewStream() As Byte
    Dim SizeLength As Long
    Dim SizeLengthReal As Long
    Dim NewLength As Long
    Dim NewLengthReal As Long
    Dim BitPos As Long
    Dim size As Long
    Dim Freq(255) As Long
    Dim FreqChar As Byte
    Dim FreqCount As Long
    Dim CurChar As Long
    Dim NewCount As Long
    Dim AddChar As Long
    Dim LastChar As Long
    Dim BitOr(7) As Byte

    size = UBound(bts) + 1

    SizeLengthReal = 1024
    ReDim SizeStream(SizeLengthReal)

    NewLengthReal = 1024
    ReDim NewStream(NewLengthReal)

    For i = 0 To 7
    BitOr(i) = (2 ^ i)
    Next

    For i = 0 To size - 1
    CurChar = bts(i)
    Freq(CurChar) = Freq(CurChar) + 1
    Next

    For i = 0 To 255
    If Freq(i) > FreqCount Then
    FreqCount = Freq(i)
    FreqChar = i
    End If
    Next

    For i = 0 To size - 1

    CurChar = bts(i)

    If (CurChar <> FreqChar) Then
    AddChar = AddChar Or BitOr(BitPos)
    End If

    BitPos = BitPos + 1
    If BitPos = 8 Then
    SizeStream(SizeLength) = AddChar
    If SizeLength + 10 > SizeLengthReal Then
    SizeLengthReal = SizeLengthReal * 2
    ReDim Preserve SizeStream(SizeLengthReal)
    End If
    SizeLength = SizeLength + 1
    BitPos = 0
    AddChar = 0
    End If

    If (CurChar <> FreqChar) Then
    NewStream(NewLength) = CurChar
    If NewLength + 10 > NewLengthReal Then
    NewLengthReal = NewLengthReal * 2
    ReDim Preserve NewStream(NewLengthReal)
    End If
    NewLength = NewLength + 1
    End If
    LastChar = CurChar

    Next

    '***
    'If AddChar <> 0 Then
    SizeStream(SizeLength) = AddChar
    SizeLength = SizeLength + 1
    'End If

    ReDim Preserve bts((SizeLength + NewLength + 4 + 1 + 4))

    Call CopyMemory(bts(0), FreqChar, 1)
    Call CopyMemory(bts(1), size, 4)
    Call CopyMemory(bts(5), SizeLength, 4)
    Call CopyMemory(bts(9), SizeStream(0), SizeLength)
    Call CopyMemory(bts(9 + SizeLength), NewStream(0), NewLength)

    Erase SizeStream, NewStream
  7. И заключительным этапом можно оставшееся сжать любым универсальным алгоритмом (Huffman, арифметик, zip). Я предпочитаю сжимать Lzma.
Скачать компрессор для поиграться можно здесь – http://www.sendspace.com/file/nv2suu

Кроме этого алгоритма в закромах также есть реализованный своим путем Jpeg, а также алгоритм волнового сжатия изображений с потерями наподобии Jpeg2000.
Теги:сжатиекомпрессияизображениеpngалгоритмssp
Хабы: Алгоритмы
Всего голосов 84: ↑80 и ↓4 +76
Просмотры5.7K

Похожие публикации

Аналитик по разработке алгоритмов
от 130 000 ₽2050-ИнтеграторСанкт-ПетербургМожно удаленно
Data Scientist / ML engineer
от 140 000 до 180 000 ₽anonym.networkМожно удаленно
Data Scientist
от 70 000 до 120 000 ₽DDoS-GUARDРостов-на-ДонуМожно удаленно
Distributed Systems Engineer
от 8 000 $Cube.jsМожно удаленно
Разработчик С++ в команду Navi
от 180 000 ₽2GISМожно удаленно

Лучшие публикации за сутки