Geekly Articles each Day
📜 ⬆️ ⬇️

SSP - Own lossless image compression algorithm

Finally, it became possible to publish the algorithm I developed once. The algorithm was developed for an automatic screenshots program. For convenience, further descriptions of it will call it - SSP (sciner screenshot packer). SSP can be fairly compared with PNG, so in the article I will make comparisons with it.

The algorithm has two modes of compression:
  1. lossless - in which, the image after decompression will be restored to within a bit;
  2. with losses - which does not reduce the quality of the picture, just in it just before compression, the image is translated to the YcbCr palette
    Only by changing the palette can significantly improve compression. I use the following factors:
    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
If you try to compress the test image -
image
We obtain the following results:
183 960 - The size of the original PNG file
155 932 - SSP (compression occurs in 0.2 seconds)
122 593 - SSP (lossy, lossy)

Very interesting results are obtained by compressing the next image.
www.libpng.org/pub/png/img_png/16million-pschmidt.png
59852 - PNG
1428 - SSP
')
The algorithm contains the following steps:
  1. The image is decoded into an RGB array;
  2. If the lossy mode is selected, then recoding into the YcbCr palette is performed;
  3. The image is filtered by Paeth filter (prediction of the value by a simple linear function);
  4. Removing duplicate pixels is not a particularly complicated way:
    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 coding (Burrows-Wheeler transform), namely, the best implementation in the world — Archon, by Dmitry Malyshev;
  6. Next comes my function, which removes the most frequently used byte from the received after the previous step and builds the bitmap of the positions from which this byte was removed. This stage is run 3 times (experimentally selected value);

    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. And the final stage can be compressed by any universal algorithm (Huffman, arithmetic, zip). I prefer to compress Lzma.
Download the compressor for play, you can here - http://www.sendspace.com/file/nv2suu

In addition to this algorithm, the bins also have a Jpeg implemented in their own way, as well as an algorithm for wave compression of images with losses like Jpeg2000.

Source: https://habr.com/ru/post/113668/

More articles:


All Articles