Наконец–то появилась возможность опубликовать разработанный мною когда-то алгоритм. Алгоритм был разработан для программы автоматического снятия скриншотов. Для удобства дальнейшего его описания буду называть его – SSP (sciner screenshot packer). SSP можно справедливо сопоставить PNG, поэтому в статье я буду проводить сравнения именно с ним.
Алгоритм имеет два режима компресии:
Получим следующие результаты:
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
Алгоритм содержит следующие этапы:
Кроме этого алгоритма в закромах также есть реализованный своим путем Jpeg, а также алгоритм волнового сжатия изображений с потерями наподобии Jpeg2000.
Алгоритм имеет два режима компресии:
- без потерь – в котором, изображения после декомпресии будет восстановлено с точностью до бита;
- с потерями – который не уменьшает качества картинки, просто в нем непосредственно перед сжатием, изображение переводится палитру 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
Получим следующие результаты:
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
Алгоритм содержит следующие этапы:
- Изображение декодируется в RGB массив;
- Если выбран режим с потерями, то производится перекодировка в палитру YcbCr;
- Производится фильтрация изображения фильтром Paeth (предсказание значения по простой линейной функции);
- Удаление повторяющихся пикселей не особо сложным способом:
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 - кодирование BWT (Преобразование Барроуза — Уилера), а именно — лучшая в мире реализация – Архон, автор — Дмитрий Малышев;
- Далее идет моя функция, убирающая из полученного после предыдущего шага самый часто используемый байт и строящая битовую карту позиций, откуда убирали этот байт. Этот этап прогоняется 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
- И заключительным этапом можно оставшееся сжать любым универсальным алгоритмом (Huffman, арифметик, zip). Я предпочитаю сжимать Lzma.
Кроме этого алгоритма в закромах также есть реализованный своим путем Jpeg, а также алгоритм волнового сжатия изображений с потерями наподобии Jpeg2000.