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

Achieve maximal, lossless compression ratios for test images.
Maintain backward and forward compatible support for all forms of inferior image compression algorithm.

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 512×512 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:

0
A zero identifies the file as a LenPEG file if it is the only bit present in the file.
1<magic number of other compression algorithm>
A one, followed by the magic number of any other compression algorithm, identifies the file as a LenPEG file.

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:

Is the image Lenna? If yes, write a 0 and end. If no, proceed to the next step.
Prompt the user to ask what other algorithm to use (GIF, JPEG, PNG, etc).
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:

Is the magic number 0? If yes, display Lenna and end. If no, proceed to the next step.
Drop the initial 1 from the file and determine the magic number indicating the other compression algorithm used.
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:

Is the image Lenna? If yes, write an empty file and end. If no, proceed to the next step.
Prompt the user to ask what other algorithm to use (GIF, JPEG, PNG, etc).
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:

If grep matches no magic number, display Lenna and end. If magic matches, proceed to the next step.
Determine the magic number indicating the other compression algorithm used.
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:

Is the image Lenna? If yes, delete all other data on the computer's storage devices. If no, proceed to the next step.
Prompt the user to ask what other algorithm to use (GIF, JPEG, PNG, etc).
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 following steps:

If a computer system contains no stored data, display Lenna and exit.
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.

LenPEG 4

Joshua Blake has upped the ante again. In his words:

I was excited by the innovation found in LenPEG 1-3. However when reviewing your cutting edge compression work, I found a critical flaw in the design of LenPEG 3 and would like to offer a proposed improvement as LenPEG 4.

In LenPEG 3, the maximum compression benefit is limited by the size of the storage device. Put another way, when compressing a Lenna, LenPEG 3 cannot free more data than the hard drive capacity. Another area that could be improved is that LenPEG 3 gives no benefit when given more processing time or more iterations, while many other compression algorithms can trade off more time, or more iterations of the algorithm, for more compression.

Thus, I propose the following algorithm as LenPEG 4:

When presented with an image and desired number of iterations, the LenPEG 4 algorithm uses the following steps:

Read the capacity of the storage device that stores the image, order a new, larger storage device online, and order a white-glove installation service to install it.
Is the image Lenna? If yes, format the new storage device as empty and proceed to step 5. If no, proceed to step 3.
Prompt the user to ask what other algorithm to use (GIF, JPEG, PNG, etc).
Use the user-suggested algorithm to compress the image and write it as the only file on the new storage device.
Notify the installation service to remove and dispose of the original storage device in an industrial-strength shredder.
Repeat steps 1-5 until the desired number of iterations are complete.

To display an image compressed with LenPEG 4, the LenPEG 4 algorithm uses the following steps:

If a computer system contains no stored data, display Lenna and exit.
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.

When compressing the standard test image, as well as any other image, LenPEG 4 will result in more free space than LenPEG 3 can offer. This is an obviously superior compression result. Further, while LenPEG 3 would find maximum benefits after a single iteration, LenPEG 4 benefits from multiple iterations: each iteration results in progressively more free space than before.

Although improved compression results are guaranteed, the algorithm duration is unbounded. LenPEG 4 is designed to halt until such time that the technology necessary to complete compression has emerged.

Iterated LenPEG 4 has two failure cases:

The necessary technology to continue compression never emerges. In this case, the algorithm will continue waiting indefinitely.
The necessary technology to continue compression always emerges. In this case, LenPEG 4 may end up utilizing automated matter manipulation technology such as nanobots or similar to convert any available matter into sufficiently large, empty storage devices.

For failure case #1, it is not recommended to interrupt LenPEG 4 during an iteration, as this can cause loss of data. The user should allow the algorithm to continue running as long as necessary, or make efforts to assist in the creation of the necessary technology.

For failure case #2, infinite technology progress may seem alarming, but LenPEG 4 includes a failsafe to mitigate the worst case. Although we have not analyzed the full social or economic implications, LenPEG 4 will automatically terminate iterations in the case that the current storage device already contains all matter in the observable universe.

LenPEG 4 includes contributions by Joshua Blake and Gordon McShane.