Implementation notes
Image mixer.
----------------------------------------------------------------------
0. Concept
We can treat groups of 2x2 pixels as a "macro" pixel. That is, any
pixel in this macro pixel can have random intensities, and when viewed
from a distance, our eyes will not see the individual colors. Instead,
we will see something more like the average of the four pixels.
This is not new, pointillism has been around since the 19th century, and
the screen phosphors do this all the time. Unlike the pointillists
though, I am interested in these individual sub-pixels: since we will
not see them, this is ripe opportunity for hiding an image in plain
sight, and this is what I set out to do.
----------------------------------------------------------------------
1. Mixing images
Given 4 pixels, their average intensity is (ignoring gamma correction
and so forth):
p = (a + b + c + d) / 4
Assuming that we want to encode a hidden image in one of those pixels,
we will make one of those pixels (such as "a") the intensity of our
hidden image, and adjust the other 3 pixels to compensate. One
arrangement is as follows:
p1 = (p0 + px + px + p1) / 4
px = (3 * p1 - p0) / 2
p0 is a pixel from the "hidden" or secondary image.
p1 is the corresponding pixel from the primary image.
px is the value needed to compensate for the difference.
To mix two images, we will keep the original p0 and p1 pixels, and
insert two px pixels to compensate, creating one 2x2 macro pixel for
each pixel in the original images. It's not quite this straightforward
though, since the value of px may be outside the range of valid pixel
values, so we need to compress the range of the input p0 and p1 values
to make sure that all px values falls within range.
Assuming that the valid range is [0,255], px is guaranteed to be within
range if all p0 and p1 values are within [64,191]. But simply scaling
the images like that is a waste of intensity levels if the input images
were already similar to start with, and it's especially a waste if both
inputs were already within [64,191]. We would like to compute the
scaling factors to minimize changes in the original intensity values.
If we plot all possible p0 and p1 combinations, we get a graph similar
to the following:
+------------+
^ | / /|
| | / / |
p0 | / / |
| / / |
|/ / |
+------------+
p1 -->
All values within the parallelogram will produce px values that are are
within [0,255] range, anything in the triangles on the two sides will
produce out of range values.
The scaling algorithm works as follows:
1. Scan over both input images to get all (p0,p1) combinations. This
tells us all the points that are in the graph above, and therefore
all the points outside of the parallelogram.
2. Search for scaling factors (min_p0,max_p0) and (min_p1,max_p1) that
would allow all points to fit within the parallelogram. This
involves testing 256^2 points for each scaling factor combination,
and there are 64^4 possible scaling factors. A brute force search
here would be slightly expensive, but we can cut down the search
space by observing that if some max_p value doesn't work, any greater
max_p will not work either, and similarly for min_p. This means we
can use binary search. The end result runs quite fast.
After computing the scaling factors, a second pass trivially interleaves
the two images together to form the final image. Dithering is used to
compensate for the reduction in intensity levels, for a minor boost in
output image quality.
----------------------------------------------------------------------
2. Finally...
This program only exists to provide sample data for Akari. So happens
that the functionality here matches Chinatsu's reputation for art, so
after implementing the algorithm described above, I thought, oh well,
why not, and created an ASCII art based on Chinatsu.
After figuring out the image mixing bits, this program was fairly
straightforward to write. All edits from beginning to end are captured
in edit.html.
If I had time, I might have made ASCII art for the other Yuruyuri
characters as well. But mostly I am happy with what I got ^_^;