Build a coding-efficient, parallel fractal image codec

Build a self-contained fractal image codec for 8-bit grayscale and RGB images. The submitted bitstreams are judged on image quality at fixed byte budgets. Within each Guardian’s evaluation, faster encoding and lower memory use improve a submission’s score by their rank among accepted submissions; there is no absolute speed or memory threshold.

A partitioned iterated function system (PIFS) represents image regions with maps from larger domain regions of the same image. The decoder reconstructs the image from the attractor of the maps. This bounty seeks better rate–distortion performance through fractal coding, adaptive entropy coding, and parallel CPU domain–range search.

The codec must meet these requirements:

1. Fractal reconstruction. Every decoded pixel must be reconstructed from the bitstream's PIFS attractor, by iteration or an exact equivalent. Partition geometry, domain pool, transforms, and the affine sample map are the Solver's choice. A deterministic deblocking post-filter is permitted if FORMAT.md specifies it and it uses only the bitstream. A separately coded DCT, wavelet, vector-quantised, neural, or other non-fractal residual layer is not permitted.
2. Grayscale and color. The encoder accepts the specified binary PGM and PPM inputs; the decoder outputs the corresponding type and dimensions. The Solver chooses how to code color. Each coded image plane must use the reconstruction in item 1. FORMAT.md must specify any color conversion and chroma sampling.
3. Adaptive entropy coding. The bitstream begins with a header of at most 64 bytes. The header may contain only a format identifier and version, image dimensions and type, color/chroma format, and coding parameters applying to the entire image. All per-region syntax, including partition decisions, domain selections, isometries, scaling, and offsets, must be coded with an adaptive arithmetic, range, or ANS coder. Fixed-width per-region fields outside the header do not qualify.
4. Rate control. The encoder accepts a byte budget and produces a complete bitstream no larger than that budget. The bitstream includes everything needed to decode it, including image dimensions.
5. Self-containment. The encoder reads the input image and its command-line options; the decoder reads the bitstream and its command-line options. Solution-specific data, including constant tables built into the codec, may total at most 64 KiB. Corpus image data may not be built in. Neither program may obtain image data or solution-specific logic from another source while running.
6. Parallel CPU search. Domain–range search must use CPU threads when encoding with more than one thread. GPU and other accelerator code are not permitted. The encoder must support one-thread and four-thread operation. Its bitstreams need not be identical across runs, thread counts, or machines; each output must independently meet the applicable validity, budget, and trial-quality requirements below.
7. Buildability. The source must build on x86-64 Linux using the commands in RUN.md. Publicly available compilers and general-purpose libraries are permitted; RUN.md must identify their versions. All solution-specific code must be submitted.

The decoder must support an initial image with every sample set to either 0 or 255, and report bit accounting for at least the header, partition, domain-selection, isometry, scaling, and offset categories.

Every item below is mandatory and must be present as bytes in the Submission. codec.tar.gz must contain the complete encoder and decoder source and build files. Its archive members must be plain filenames, without directory paths.

The submitted .frc files determine the scored image quality. The encoder source and trial encodes establish that the Submission also provides a functioning implementation of the claimed codec; trial encodes do not replace or rescore the submitted .frc files.

The following twelve images are the required evaluation inputs. The specified hashes identify the source files and the authoritative PGM or PPM reference images. A grayscale source is converted to binary PGM with header P5\n<width> <height>\n255\n followed by its 8-bit pixels. An RGB source is converted to binary PPM with header P6\n<width> <height>\n255\n followed by its interleaved 8-bit RGB pixels. No rescaling or color adjustment is applied.

Small images

These PNGs are in the scikit-image 0.26.0 source release, SHA-256 f5f970ab04efad85c24714321fcc91613fcb64ef2a892a13167df2f3e59199fa, at scikit_image-0.26.0/src/skimage/data/<name>.png. They are public domain or CC0.

High-resolution images

Pillow 12.3.0 decodes each source file. cliffs uses its central 6000×4000 region, with left coordinate floor((width − 6000) / 2) and top coordinate floor((height − 4000) / 2). wave and diatoms use the entire decoded image.

Rates

For every image, the whole-file byte budget is floor(rate × width × height / 8), counting pixels rather than color channels.

Background reading, not additional acceptance requirements: Jacquin, “Image coding based on a fractal theory of iterated contractive image transformations,” 1992; Fisher, Fractal Image Compression: Theory and Application, 1995; Saupe, “Accelerating fractal image compression by multi-dimensional nearest neighbor search,” 1995; Ruhl and Hartenstein, “Optimal fractal coding is NP-hard,” 1997; Hamzaoui and Saupe, “Fractal image compression,” 2006; Duda, “Asymmetric numeral systems,” 2013; and Marpe, Schwarz, and Wiegand, “Context-based adaptive binary arithmetic coding,” 2003.

Each Guardian independently selects its highest-scoring eligible Submission using the measurements and ranks from that Guardian's comparison. An exact tie in $F$ goes to higher unrounded $Q$, then higher unrounded mean SSIM, then smaller combined size of the 36 submitted bitstreams, then the lowest Solver address in ascending lowercase hexadecimal order. If exactly one Submission is accepted, it is that Guardian's selection. If none is accepted, the selection is no_valid_submission.

Guardians' independent selections need not agree. Elgora's existing Guardian verdict and finalization rules determine the bounty's final outcome; this challenge does not change those rules.

An established failure of an acceptance criterion makes a Submission ineligible, regardless of its potential score. Material use of built-in corpus image data, a non-fractal reconstruction layer, external solution-specific logic, a GPU or other accelerator, or behavior that differs materially between a measured trial encode and an ordinary trial encode is also ineligible.

Alpha channels, high bit depth, lossless coding, video, hybrid codecs with a non-fractal residual layer, fractal zoom, and beating JPEG 2000.