Note: This is incomplete. The images shown here are for presentational purposes only; they do not look like this on NES.
I've been screwing around more with image processing. This time, reducing a full-color image to something that could potentially be displayed on an NES. (Don't ask why; it's part of a project that I will discuss some time later.)
So here is what I've done so far:
I wrote an algorithm to select the most suitable NES palette for an image. The full NES palette is made of 55 colors (64 if you include the duplicates) a channel additive can also be used to increase the channel intensities (called "emphasis") across the full palette. If these are included in the count, you get about 55*8 = 440 colors (512 total if you count the duplicates).
The palette selected in the first step of the algorithm is the emphasis setting (one of 8 possibilities). Then it gathers information about the colors used in the image to select which colors will appear in the final output.
Finally, it runs a low-pass filter over the new palette to reduce the colors which are not often used. And then removes any remaining colors that are considered too "near" to neighboring colors and are not used as often. After these color reduction steps you are left with a 13-color image.
The 13-color image is dithered to approximate the original colors, but dithering is optional. The dithering can also be controlled to apply more or less error correction, as desired.
So here's some pretty pictures!
First, the original test image I used to develop the algorithm:
My first attempt at standard dithering gave me this result (~36 colors):
My first reduction to 13 colors... The highlights (especially in the feather thing on the hat) have been washed out:
After adding the low-pass filter, the highlights came back, and it's still 13 colors!
My next test image:
First attempt at color reduction, very grainy:
Same attempt, just with dithering disabled:
Again, no dithering, but with a different emphasis setting:
After messing with the dithering settings, I created this:
Noticing how bad the dithering got, I decided to set auto-levels on the test image to stretch the midtones near black and white. The advantage to this is that it creates an image with more primary colors; thus, less dithering is required to get a suitable result.
More dither setting adjustments, and I think this one is the best:
Same settings, without dithering:
Obviously, it still needs work to be properly NES-compatible. First, a background color must be selected. This one is easy; just choose the color that's used in the image the most! Next, the image must be broken into 8x8-pixel tiles. Then some color reduction must be done on the tile: 3 colors + the background tile. This will create a single background palette; there are only four such palettes available, so color reduction needs to be done wisely.
The reduction to tile palettes could be very tricky, since 13 colors must be distributed evenly among them. For example, here's some ASCII art to illustrate how the full background palette is created:
[BG] [BG] [BG] [BG]
Where "BG" represents the first color (color 0), and the numbers 1 - 12 represent the remaining 12 colors. The tricky part is, once this palette is created, it is immutable: you can change it mid-frame for some additional color depth, but I want to avoid this as much as possible. Also notice that these colors cannot move. For example, if you have a tile using palette 0 (BG + colors 0 - 3) Those are the only colors that tile can use. You can't have a tile that uses color 3 and color 4 or similar; the colors cannot cross the boundaries, so to speak. This makes the final color reduction quite critical. Poorly chosen palette optimization will lead to a bad resulting image.