ASCII Art

I've been looking at ASCII art recently - at least in the context of
converting images into ASCII-rendered versions of the original. This has
resulted in a few simple projects including one where I rendered a webcam
video feed as ASCII in a terminal. One of the challenges I faced in that
project was finding the correct size of the font to get reasonable results; a
standard 80 x 24 terminal left a lot to be desired in terms of the final text
rendering of a video frame. It was easy enough to simply resize the
font/terminal to get what I wanted but it wasn't a very elegant solution and
didn't translate very well to other projects (where the render target was not
a terminal, for example). 

To address that limitation I ended up writing a dynamic font 'renderer'[1] -
this post describes some aspects of that project.

The interesting parts (to me) include the font rendering/scaling,
the tiling of the image parts, and the interesting combinations of rendering.

Dealing With Fonts

This was mainly familiarizing myself with the FreeType font library and how
to load and render fonts in memory. I could have just taken one of the many
already existing ASCII-to-grayscale mappings but I wanted the ability to
provide a few additional features that required more than that (e.g. custom 
character sets and non-fixed-width fonts).

So, rather than use an fixed set of characters I dynamically compute
the average brightness of a particular character set (for a given font) and
use that to select glyphs to replace image pixels.

In addition to which font and glyphs to use I also dynamically scale
the glyphs used based on properties of each region of an image. The FreeType 
font library supports this directly allowing me to render a glyph at whatever
size I specify; I can then 'copy' those pixels directly to the translated image.

Image Tiling

I used a windowing mechanism to select the size of the font to use. Given an
image, I subdivide the image into N rows and M columns and in each N,M cell
select a font size (more on how a size is selected later).

Then, within that cell, compute the properties of the region for each character
glyph and translate that source image region to an ASCII character that most
closely matches the average greyscale value of that region.

This nested tiling approach allows for selecting font sizes in any number of
ways. For example, selecting a random font size within each N,M cell of the
image results in the following.

Zooming in on a section of that images highlights a few things about this
approach:

there is flexibility of rendering each region in isolation
clipping at the edges of regions will start to produce artifacts in the 
output image due to discontinuities between the glyphs
as you approach a glyph size of 1x1 you approach a pixel-level copy of
the original image region

Of course, just like the impetus for this project, there is something left to
be desired about the resolution of the final image. Select a size too large
and there is loss of detail; too small and the 'ascii' effect is dimished. 

So I started experimenting with ways to quantify the amount of resolution
in a section of the image and how to translate that to font size.

Rendering

Finding the right way to encode resolution turned out to be a bit of a rabbit
hole for me. I started with the idea of using the entropy of each window but
broadened my search to frequency- and thresholding-based techniques.

RMS

A basic root mean square approach captured some of the contrast in the image
but it wasn't sufficient for what I wanted.

Frequency Domain

After a bit of research I came across a paper "Contrast in Complex Images" by 
Eli Peli which discussed how the human eye perceives contrast and various ways 
to compute that spatially across an image. It fit nicely into the notion of a 
subdivided image and provided an equation to compute sub-cell contrast based on 
high-frequency components in an image.

Essentially this consists of taking the DFT of an image, running that through
a high-pass filter, and computing the inverse DFT of the filtered content.
This is closely related to edge detection but maintains more high-frequency
information (as you can see in the examples below).

This worked well for some images, but the residual information created some 
noise for certain image types. Consider the two images: kitten and wave.

The contrast is easier to identify in the kitten but the wave is a bit more
challenging.

Thresholding

Finally, I ended up using a tunable threshold technique where I convert the
image to B/W based on some threshold brightness and use the proximity to this
threshold value as an indicator of the amount of contrast in each window. This
ultimately ended up working fairly well for the effect I was looking for
preserving much of the data of the frequency-based approach but without the
residual noise.

[1] I say renderer but I use libfreetype to do all the heavy lifting of
pixel-level character rendering.

Affine Transformation

I've been working on a personal project for data presentation and exploration. It is very much a work in progress but as part of the development I've come across some interesting little technical problems to solve. I hope to eventually have a longer series of posts along the lines of 'building your own data tools;' however, until I find the time to give that the attention it needs, I plan on posting some smaller entries centered around these technical problems.

One of the early challenges I came across when plotting data was mapping the input values to the fixed amount of space I had on screen. For example, if I generate a window that is 600px wide I can only support a range of input values less than or equal to 600 (using a naive approach of each value in the range maps to a pixel on screen). Supporting an input range greater than 600 values requires some level of mapping between the input values and the available pixels on the screen. There are simple conversions for specific input ranges (e.g. when the range is close to a multiple of the number of pixels) but a more general solution is necessary to handle arbitrary input data sets.

The way I ended up solving this was to use an affine transformation to map the input domain to a fixed pixel range. This is how scales work in D3.js if you are familiar with that JavaScript library. For example, if my input values come from [-100, 100] but I need my output values to fall within [28,63] then applying this transformation would look something like the image below:

Notice that the minimum value in the input interval (-100) maps directly to the minimum value in the output interval (28). Values along the input interval are mapped to the output interval preserving the relative position within each. The equation to do this is:

\[ range_{x} = (domain_{x} - domain_{a}) * ((range_{b} - domain_{a}) / (domain_{b} - domain_{a})) + range_{a} \]

Where domain and range are defined by the intervals \([domain_{a}, domain_{b}]\) and \([range_{a},range_{b}]\), respectively. Neither the domain nor the range is required to have a 0 as one of the endpoints and the intervals can be either increasing or decreasing. This generality is helpful in a variety of contexts. For example:

Setting Borders

The viewport used to plot data may not always use all available pixels of the window; multi-plot windows or viewports that have a border are two examples. In the case where there is a border around the plot (allowing for labels and tick marks) that area should not be considered as part of the range of the viewport. Instead, a window with 600px width that uses 30px on either side for border should use a range of [30,570] - the equation above makes this easy.

Inverted Axis

In most window coordinate systems the origin is at the top left of the screen. That means increasing y-axis values (from the window perspective) are typically decreasing data set y-axis values. Using a negative range makes this translation simple. Consider a 600px window height: mapping a domain to the range [600,0] automatically handles the inverted axis problem.

Another way that this simplifies things is when there is a need to 'flip' the layout of a graph. For example, in the two images below the data is the same; the only difference is the range. Having the ability to easily manipulate target ranges for the input data allows me to cycle through multiple views of the same data without much work on the backend.

 

Visualizing Network Traversal

As part of an experiment I was doing related to network traversal I started to trying to visualize coverage of a network by a single visitor traveling through the nodes. The idea was to set a gradient between two colors and as a node was visited more times it would slowly take on a change in color over the gradient. If the goal was to visit each node N times, then the visualization would indicate current progress as a 'heat map' of the network according to the number of visits to each node.

The outputs were interesting in that controlling the traversal policy would change the distribution of color over the image. This is perhaps obvious given the experimental construct but still provided an alternate mechanism for 'measuring' the accuracy of the traversal. For example, if the goal is to cover the network as evenly as possible during the traversal, the kurtosis of a distribution then becomes a measure of how close one is to this goal.

To demonstration this I set up an NxN grid network and ran three example traversals over that grid. I captured the 'heat map' when the median of all the visit values for the nodes was at half of the target visits. The results are below.

Random Choice Walk:
At any node, a visitor will choose to move up, down, left, or right by random selection.

Backpressure Walk:

Uses a notion of backpressure to control the traversal. At each node, a visitor checks for the the least visited neighboring node and travels there.

Teleportation:
Not really a traversal, I just did it to see what it would look like. At each node, a visitor chooses a random node within the grid and jumps there directly.