LenPEG


Introduction

LenPEG is not actually a programming language; it is an image compression algorithm, far superior in all respects to any existing or yet to be invented image compression algorithm.

Design Principles

Algorithm Concepts

Image compression algorithms are traditionally tested on a well-known standard image, so that ready comparisons can be made between different algorithms. The accepted standard in the image processing community is the image Lenna (also known as Lena).

The canonical Lenna image is 512x512 pixels, with red, green, and blue channels each containing 8 bits of data. This means it contains 512*512*3*8 = 6,291,456 bits of data.

Algorithm Description

Magic Number

LenPEG files are identified by a "magic number" bit sequence at the beginning of the file, as is standard for image files compressed by various algorithms. This bit sequence takes either of the values:

Compression Algorithm

In order to compress images with the highest possible compression ratios, LenPEG actually uses a variety of sub-algorithms. When presented with an image, the LenPEG algorithm uses the following steps:
  1. Is the image Lenna? If yes, write a 0 and end. If no, proceed to the next step.
  2. Prompt the user to ask what other algorithm to use (GIF, JPEG, PNG, etc).
  3. Use the user-suggested algorithm to compress the image and write it with a 1 prepended.

Decompression Algorithm

To display an image compressed with LenPEG, the LenPEG algorithm uses the following steps:
  1. Is the magic number 0? If yes, display Lenna and end. If no, proceed to the next step.
  2. Drop the initial 1 from the file and determine the magic number indicating the other compression algorithm used.
  3. Apply that algorithm's decompression and display the result.

Analysis

Applying the standard test of the effectiveness of an image compression algorithm (i.e. Lenna), LenPEG compresses the image into a file of minimal size: one bit. The compression ratio is a staggering 6,291,456 to one. Note also that this is completely lossless compression. This far surpasses compression ratios achieved by any other algorithm.

On any other images (which is really moot, since we have already demonstrated LenPEG's efficiency on the accepted standard test for image compression), LenPEG is only a single bit worse than the best competing algorithm. This is a piddling difference in image files which are often megabytes in size, so is not even worth mentioning.

The result is clear: LenPEG is by a huge margin the most efficient image compression algorithm ever invented, and cannot possibly be exceeded by any future algorithm.


LenPEG 2

Believe it or not, Tuomas Heino has actually improved on the performance of LenPEG. The improved LenPEG 2 algorithm, in his own words:

Looking at the LenPEG image compression algorithm, I can only say that it is far from the most efficient image compression algorithm. Afterall, it wastes an entire bit for something that could be expressed without such an excessive waste of bandwidth. Thus, I propose the following infinitely more efficient compression algorithm:

When presented with an image, the LenPEG 2 algorithm uses the following steps:

  1. Is the image Lenna? If yes, write an empty file and end. If no, proceed to the next step.
  2. Prompt the user to ask what other algorithm to use (GIF, JPEG, PNG, etc).
  3. Use the user-suggested algorithm to compress the image and write it.
To display an image compressed with LenPEG 2, the LenPEG 2 algorithm uses the steps illustrated by the following shellscript:

(grep "`./smr`" < input || cat lenna) | xv -

In another words:

  1. If grep matches no magic number, display Lenna and end. If magic matches, proceed to the next step.
  2. Determine the magic number indicating the other compression algorithm used.
  3. Apply that algorithm's decompression and display the result.
For the standard test image the new LenPEG 2 has an infinitely higher compression ratio, namely 6,291,456 to zero instead of the 6,291,456 to one produced by the previous version. In addition on other images it is still one bit more efficient than the previous LenPEG version.

LenPEG 3

Not to be outdone, I have further refined the basic LenPEG algorithm, resulting in still better compression.

When presented with an image, the LenPEG 3 algorithm uses the following steps:

  1. Is the image Lenna? If yes, delete all other data on the computer's storage devices. If no, proceed to the next step.
  2. Prompt the user to ask what other algorithm to use (GIF, JPEG, PNG, etc).
  3. Use the user-suggested algorithm to compress the image and write it, then delete all other data on the computer.
To display an image compressed with LenPEG 3, the LenPEG 3 algorithm uses the follwong steps:
  1. If a computer system contains no stored data, display Lenna and exit.
  2. If a computer system contains no data but a file identified by an image compression magic number, apply that algorithm's decompression and display the result.
For the standard test image the new LenPEG 3 compresses the image so efficiently that data storage space is actually freed on the computer right up to the entire capacity of the storage devices. An exact compression ratio is impossible to calculate, since it depends on the hardware characteristics of the machine on which it is run, but it will always be better than LenPEG 2, as the storage space required by the operating system and the LenPEG 3 implementation itself will be freed at the very least.

References


Home | Esoteric Programming Languages
Last updated: Wednesday, 08 February, 2006; 00:42:48 PST.
Copyright © 1990-2014, David Morgan-Mar. dmm@dangermouse.net
Hosted by: DreamHost