Pull to refresh

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

Reading time 6 min
Views 6.1K
Наконец–то появилась возможность опубликовать разработанный мною когда-то алгоритм. Алгоритм был разработан для программы автоматического снятия скриншотов. Для удобства дальнейшего его описания буду называть его – 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(+ 0)<br/>
            g = ByteArray(+ 1)<br/>
            b = ByteArray(+ 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.
Tags:
Hubs:
+76
Comments 53
Comments Comments 53

Articles