---
profile: elgora_markdown_bounty_challenge_v0
escrow_amount: "27182818"
submission_deadline: 1792954800
payout_policy: winner_take_all
constraints:
  max_extracted_bytes: 50000000
  required_files: [codec.tar.gz, FORMAT.md, REPORT.md, RUN.md, results.csv, camera_r0125.frc, camera_r0250.frc, camera_r0500.frc, astronaut_r0125.frc, astronaut_r0250.frc, astronaut_r0500.frc, coffee_r0125.frc, coffee_r0250.frc, coffee_r0500.frc, chelsea_r0125.frc, chelsea_r0250.frc, chelsea_r0500.frc, coins_r0125.frc, coins_r0250.frc, coins_r0500.frc, brick_r0125.frc, brick_r0250.frc, brick_r0500.frc, grass_r0125.frc, grass_r0250.frc, grass_r0500.frc, gravel_r0125.frc, gravel_r0250.frc, gravel_r0500.frc, text_r0125.frc, text_r0250.frc, text_r0500.frc, cliffs_r0125.frc, cliffs_r0250.frc, cliffs_r0500.frc, wave_r0125.frc, wave_r0250.frc, wave_r0500.frc, diatoms_r0125.frc, diatoms_r0250.frc, diatoms_r0500.frc]
---

# Build a coding-efficient, parallel fractal image codec

## Summary

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.

## Challenge details

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.

## What you need to submit (Deliverables)

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.

| Deliverable | Required content |
|---|---|
| `codec.tar.gz` | Complete source and build files for the submitted encoder and decoder. |
| `RUN.md` | Exact build commands and command templates for encoding a PGM or PPM to a byte budget with a chosen thread count; decoding a bitstream; decoding from initial value 0 or 255; and reporting bit accounting. Identify the encoder settings used for the submitted bitstreams and for the trial encodes defined below. |
| `FORMAT.md` | Complete bitstream specification, including the header, color conversion, partitions and syntax elements, probability models, entropy coder, decoding iteration and stopping rule, and any post-filter. |
| `REPORT.md` | Design and color handling; entropy coding and a fixed-width comparison for the same scored symbols; parallel-search design; the Solver's own one-, two-, and four-thread timings and memory observations; rate–distortion results by image class; relevant prior work or a statement that a technique is original; and limitations. |
| `results.csv` | One row per image and rate, with columns `image,rate,bytes,psnr_db,ssim`. |
| 36 `.frc` files | One complete bitstream for each named image and rate, named `<image>_<rate>.frc`, within its applicable byte budget. |

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.

## Inputs, Materials and References

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](https://files.pythonhosted.org/packages/a1/b4/2528bb43c67d48053a7a649a9666432dc307d66ba02e3a6d5c40f46655df/scikit_image-0.26.0.tar.gz), SHA-256 `f5f970ab04efad85c24714321fcc91613fcb64ef2a892a13167df2f3e59199fa`, at `scikit_image-0.26.0/src/skimage/data/<name>.png`. They are public domain or CC0.

| Image | Type | Size | Class | PNG SHA-256 | Reference PGM/PPM SHA-256 |
|---|---|---|---|---|---|
| `camera` | grayscale | 512×512 | natural | `b0793d2adda0fa6ae899c03989482bff9a42d3d5690fc7e3648f2795d730c23a` | `4b96b14e4109a9658060595334308437b37f9e50b041b8470325062df7bbb6e0` |
| `astronaut` | color | 512×512 | natural | `88431cd9653ccd539741b555fb0a46b61558b301d4110412b5bc28b5e3ea6cb5` | `07b5a5bf3b50328f1fa86ed445d32031588049d28add8eacaa382f683c933b07` |
| `coffee` | color | 600×400 | natural | `cc02f8ca188b167c775a7101b5d767d1e71792cf762c33d6fa15a4599b5a8de7` | `5b1aa7688d0032aa8eadb0653ede10e970bcd2d563fc4b6fa80863ad41d584a8` |
| `chelsea` | color | 451×300 | natural | `596aa1e7cb875eb79f437e310381d26b338a81c2da23439704a73c4651e8c4bb` | `2862a7e906f546a2a38b0e1e04c31bf09ff2fa6f8e230aaffc95cccde833c047` |
| `coins` | grayscale | 384×303 | natural | `f8d773fc9cfa6f4d8e5942dc34d0a0788fcaed2a4fefbbed0aef5398d7ef4cba` | `42e0981b0db2d8d002c60ac1a824dcf687a41963f2ff9f1ef8452e731339f3b2` |
| `brick` | grayscale | 512×512 | texture | `7966caf324f6ba843118d98f7a07746d22f6a343430add0233eca5f6eaaa8fcf` | `4da5f43be132f4cca6ed8270231afd3fc1f665e1da78c85ccddb7919ba94e2b0` |
| `grass` | grayscale | 512×512 | texture | `b6b6022426b38936c43a4ac09635cd78af074e90f42ffa8227ac8b7452d39f89` | `b785a42c32108ef2fb16b0695b59ab3cd136d7ad7f79ab5b7932a88922823ed4` |
| `gravel` | grayscale | 512×512 | texture | `c48615b451bf1e606fbd72c0aa9f8cc0f068ab7111ef7d93bb9b0f2586440c12` | `8683a35abc2a122a3547b6a15dbd9b8a80ed5b645c0905929747c7993dc4948b` |
| `text` | grayscale | 448×172 | text | `bd84aa3a6e3c9887850d45d606c96b2e59433fbef50338570b63c319e668e6d1` | `130b47f9dedfe6008128fa9b8372d3934e709dd1239d63e571799956348fc487` |

### 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.

| Image | Class and source | Source SHA-256 | Source size and mode | Reference size | Reference PPM SHA-256 |
|---|---|---|---|---|---|
| `cliffs` | [ESA/Webb `weic2205a`](https://esawebb.org/media/archives/images/original/weic2205a.tif), CC BY 4.0; credit NASA, ESA, CSA, STScI | `591c5b9f712816805c3dc4a6ff17844bbb41b27cd455a9ca3f85e0c53c24beed` | 143651652 bytes; RGB 14575×8441 | 6000×4000; left 4287, top 2220 | `bea7f052aa3b45a7506692eec58232e772acc19fbe4f41ae36140b99d190cd5a` |
| `wave` | [Hokusai, *Under the Wave off Kanagawa*, Met object 45434](https://images.metmuseum.org/CRDImages/as/original/DP130155.jpg), Open Access CC0 | `cbb9988f2f18b9180a1cc0cf5dbb0e3bbf8f2e85d17930cf6ca9ab36fac36303` | 2342637 bytes; RGB 3859×2594 | 3859×2594 | `953820fe3f50d8ec73c3c9f9e1410ed8ceebf59e287ef0dddad5cb4520c9f5fd` |
| `diatoms` | [*Diatoms through the microscope*, Wikimedia Commons](https://upload.wikimedia.org/wikipedia/commons/3/31/Diatoms_through_the_microscope.jpg), public domain | `3028fe3ed4db37afc63f0289f0e70e3f7e9877b925c184b9206ae5ed6b6916bc` | 1307414 bytes; RGB 1796×1180 | 1796×1180 | `e55bf0f8f38dfebf8f548dec639ab350c4e2118425ce77e9d9edad967df6caff` |

### Rates

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

| Rate name | Bits per pixel |
|---|---|
| `r0125` | 0.125 |
| `r0250` | 0.25 |
| `r0500` | 0.5 |

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.

## Acceptance Criteria

The **verification subset** is `camera`, `grass`, `text`, and `astronaut`, each at all three rates.

1. **Complete and buildable.** The deliverables are present and complete, and the submitted source builds as described in `RUN.md`. The source and observed behavior meet the self-containment, CPU, and parallel-search requirements in Challenge details.
2. **Valid scored bitstreams.** All 36 submitted bitstreams fit their respective budgets and decode with the submitted decoder to the specified image type and dimensions. The resulting images, not the Solver's reported metrics, determine scored quality.
3. **Fractal format and convergence.** `FORMAT.md`, the source, and the submitted bitstreams establish the fractal and adaptive-coding requirements in Challenge details. For every verification-subset bitstream and `cliffs_r0250.frc`, decoding from all-0 and all-255 initial images must produce outputs differing by at most 1 in every sample.
4. **Bit accounting.** For the bitstreams in criterion 3, the reported syntax-category bits, including header and any termination or padding bits, must sum to within the larger of 1% of file size in bits or 64 bits of the actual file size in bits. `FORMAT.md` must explain how bits are attributed when entropy-coder overhead is shared among categories.
5. **Working trial encoder.** Using the submitted source and the settings identified in `RUN.md`, the encoder must produce a bitstream for each verification-subset image and rate at the specified budget with four threads, and must also produce `camera` at `r0250` with one thread. Each trial bitstream must decode correctly and meet the same format requirements as a submitted bitstream. Its PSNR must be no more than 0.25 dB below the corresponding submitted bitstream's measured PSNR. Trial files do **not** have to match submitted files byte for byte or match trial files produced on another machine or thread count. This criterion tests the submitted encoder's ability to produce the claimed class of result; it does not require identical optimisation decisions.
6. **Accurate report.** `results.csv` must give each submitted file's actual byte size and measured PSNR and SSIM, within 0.01 dB and 0.0005 respectively. `REPORT.md` must cover the topics specified under Deliverables, and its method and performance claims must not materially conflict with the source or observed behavior.
7. **Quality floor.** The submitted bitstreams' quality score $Q$, defined below, must be at least $-1.00$ dB.

A failed trial encode is a failure of criterion 5, not a zero speed score. The trial-quality allowance accommodates differences in valid encoder outputs; it does not permit a different codec or an encoder that cannot produce comparably good bitstreams.

### Scoring

**Image quality.** PSNR is $10\log_{10}(255^2/\mathrm{MSE})$, with MSE over all samples of the reference and decoded images, including all RGB channels for color, capped at 100 dB. SSIM uses scikit-image 0.26.0 `structural_similarity(reference, decoded, data_range=255, gaussian_weights=True, sigma=1.5, use_sample_covariance=False)`, with `channel_axis=2` for color.

For each of the 36 submitted bitstreams, subtract the corresponding fixed JPEG-reference PSNR in the table below from its measured PSNR. $Q$ is the arithmetic mean of those 36 differences. Trial encodes are not substituted into $Q$.

The JPEG reference uses Pillow 12.3.0 with libjpeg-turbo 3.1.4.1: baseline JPEG, grayscale or YCbCr 4:2:0, `optimize=True`, at the highest quality setting from 1 through 95 whose file fits the budget. Each table cell is budget in bytes / JPEG quality setting / PSNR in dB / SSIM.

| Image | `r0125` | `r0250` | `r0500` |
|---|---|---|---|
| `camera` | 4096 / q6 / 26.99 / 0.7272 | 8192 / q14 / 29.29 / 0.8161 | 16384 / q34 / 31.57 / 0.8869 |
| `astronaut` | 4096 / q2 / 21.67 / 0.6347 | 8192 / q7 / 25.47 / 0.7714 | 16384 / q21 / 29.49 / 0.8736 |
| `coffee` | 3750 / q4 / 22.42 / 0.5609 | 7500 / q9 / 25.67 / 0.6808 | 15000 / q22 / 28.32 / 0.7973 |
| `chelsea` | 2114 / q4 / 23.79 / 0.5962 | 4228 / q11 / 28.82 / 0.7744 | 8456 / q27 / 32.02 / 0.8717 |
| `coins` | 1818 / q3 / 22.55 / 0.6001 | 3636 / q8 / 25.72 / 0.7130 | 7272 / q20 / 28.23 / 0.8132 |
| `brick` | 4096 / q5 / 27.90 / 0.8431 | 8192 / q15 / 34.02 / 0.9339 | 16384 / q51 / 39.03 / 0.9725 |
| `grass` | 4096 / q2 / 18.49 / 0.4057 | 8192 / q4 / 19.85 / 0.5545 | 16384 / q9 / 22.30 / 0.7337 |
| `gravel` | 4096 / q2 / 19.79 / 0.4953 | 8192 / q4 / 21.64 / 0.6315 | 16384 / q10 / 25.21 / 0.8002 |
| `text` | 1204 / q5 / 26.69 / 0.7101 | 2408 / q11 / 30.23 / 0.8014 | 4816 / q29 / 33.75 / 0.8804 |
| `cliffs` | 375000 / q17 / 34.04 / 0.9001 | 750000 / q42 / 37.44 / 0.9339 | 1500000 / q75 / 39.52 / 0.9496 |
| `wave` | 156410 / q4 / 22.66 / 0.5653 | 312820 / q11 / 27.27 / 0.6728 | 625640 / q23 / 29.77 / 0.7775 |
| `diatoms` | 33113 / q6 / 26.77 / 0.7398 | 66227 / q17 / 32.27 / 0.8684 | 132455 / q48 / 36.61 / 0.9249 |
**Relative speed and memory.** Speed and memory affect a Guardian's comparison
of accepted Submissions; neither has an absolute passing threshold. For each
Guardian's comparison, all accepted Submissions are benchmarked on that
Guardian's same x86-64 CPU machine under the same software and resource
conditions. A Guardian does not compare its elapsed times or peak resident
memory figures with another Guardian's figures. Different Guardians may
therefore assign different ranks.

For each of the 12 four-thread trial encodes in criterion 5, elapsed time is
the median of three measurements. $T$ is the sum of those 12 medians. $M$ is
the largest peak resident memory measurement among those trial encodes and the
36 ordinary decodes used in criterion 2. Elapsed time and peak resident memory
are measured with `/usr/bin/time -f "%e %M"`. Initial-value and bit-accounting
decodes do not contribute to $M$.

Within a Guardian's comparison, rank accepted Submissions by increasing $T$
and, separately, by increasing $M$. Equal measured values share the better
rank. A speed rank expresses order, not the magnitude of the time difference;
no Solver-side timing is used to assign it.

For each Guardian's comparison, the final score is

$$
F=Q-0.10(\text{speed rank}-1)-0.10(\text{memory rank}-1).
$$

Use unrounded measurements and scores for comparisons; display $F$ and $Q$
to 0.01 dB and mean SSIM to four decimal places.

## How is the winner selected?

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.

## Disqualification Conditions

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.

## Out Of Scope

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