Pattern Matching Compression

Overview

Details

Publications

Developers

Still Frames

Videos

Statistics

Future

There have been many issues that have to be dealt with before one can remove the need for downloading an application. Compression style, decompression speed and bandwith would only be a start. For the sake of thisapplication will begin with a single image and then work our way up to a video segment.

The image is compressed based on three ways : pattern matching, two dimentional run length encoding (2D RLE) and single pixels. There are no X and Y positions stored in the file to allow for more compression. To solve the problem of location, the image is always scanned from upper left to lower right. Going in order, pattern references are the only sections of data that have X and Y position referencing to the section that closely matches the current location. That is because the section pattern is made by a previous match in the image. Two dimentional run length encoding has a width and a height with the added information of how it is to be shaded, much like Phong shading. The last element is a single pixel and its shade.

The method used to determine which of the three compression styles would best fit is done by allowing a look ahead, sub-sectioning and the about of random noise that will be allowed. The look ahead will remember its current information but shift the desired number pixels around the current point to see if there is a better fit else where. Sub-sectioning is used for pattern matching which allows for more accurate but larger sections to be found. This can work for better and worse, depending on the image. The amount of random noise has the largest effect on the compression of the image. Random noise will determine the size, shading, and effectiveness of the compression.

All of the information in the compressed file has to be interpreted bitwise, allowing the data to become a little more compressed. Although, the compressed file structure has an impact on how efficient the decompressor will be. Bitwise compression/decompressio can be simple, as long as all other problems are solved before implimenting. The use of arithmetic encoding is the final step to compressing the file. This is the part in which the file becomes greatly reduced and furthar more compressed.

After parsing off the bits needed to determine which of the three instructions it should be, the decompressor parses off another set of bits based on the instruction. Each instruction has its own number of bits needed to complete the set of data. The information will then be drawn to a image buffer. This will repeat until all of the instruction have been completed or the current X, Y position is beyond the lower right most corner. The image buffer is then dumped to the canvas for the viewer to see.

If the data is a video stream, it will reset the position back to the upper left corner and repeat the same steps as before. The only difference is the pattern matching references point to the previous image instead of the current image it is drawing.

Some details in the compressor/decompressor are there controlling factor for the quality of the compressed image. Also, there are bandwith adjustments built into the decompressor. Threading has been implimented for the sake of speed to allow the decompressor to read, decompress and draw to the screen all at the same time. The source code for the decompressor is short, the applet is small in size allowing the viewer to download it quickly enough to not be noticed.