Warning: this document is still work in progress. Feel free to send comments but do not consider it final material.

Libcaca study: the science behind colour ASCII art

This document is an attempt at extending the leverage of skilled resources by uncovering and addressing the challenges the industry faces today in the area of colour ASCII art generation.

Seriously, guys. If you think that what libcaca does is easy, you either don’t know what you are talking about, or we want you in the team.

Foreword

Meet Lena. She will guide us through this document, because the seriousness of a scientific document in the area of computer graphics can be measured by the number of times Lena appears in it. She truly is the Mona Lisa of image processing. [2]

This document makes a lot of assumptions, such as the fact that input images are made of pixels that have either one (grey level) or three (red, green and blue) values uniformly spread between 0 and 1 (with regards to human contrast perception). Real life is more complicated than that, but that is beyond the scope of this document for now.

Table of contents

• 1. Colour quantisation
  • 1.1. Black and white thresholding
  • 1.2. Greyscale thresholding
  • 1.3. Dynamic thresholding
  • 1.4. Random dithering
• 2. Halftoning
  • 2.1. Halftoning patterns
  • 2.2. Screen artifacts
  • 2.3. Ordered dithering
  • 2.4. Random ordered dithering
  • 2.5. Non-rectangular dither tiles
  • 2.6. Supercell dithering
  • 2.7. Void and cluster method
• 3. Error diffusion
  • 3.1. Floyd-Steinberg and JaJuNi error diffusion
  • 3.2. Floyd-Steinberg derivatives
  • 3.3. Changing image parsing direction
  • 3.4. Variable coefficients error diffusion
  • 3.5. Block error diffusion
  • 3.6. Sub-block error diffusion
  • 3.7. Direct binary search
• 4. Model-based dithering
  • 4.1. Gaussian human visual system model
  • 4.2. Direct binary search
  • 4.3 Comparing dithering algorithms
• 5. Greyscale dithering
  • 5.1. Introducing gamma
  • 5.2. Gamma correction
  • 5.3. Greyscale sub-block error diffusion
• 6. Colour dithering
  • 6.1. Separate-space dithering
  • 6.2. Accounting for other dimensions
  • 6.3. Reducing visual artifacts
  • 6.4. Colour sub-block error diffusion
• 7. Photographic mosaics
  • 7.1. Image classification
  • 7.2. Error diffusion
  • 7.3. Colour ASCII art
• Bibliography
• Source code