Kodewerx

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:



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.

_________________
I have to return some video tapes.

Feed me a stray cat.

This looks similar to something I was going to have to screw with.

There's these images for GBA games formatted such that they are for 16 color mode, but may be up to (256 - 16) colors. Each tile in the image has one of the 16 palettes available for the BG. These palettes are optimized, of course, such that the images are usually around (160 - 16) colors (10 palettes).

Now, the first step to optimization is obvious. The colors only have 16 bits to represent them, so all colors in the base image being converted from full color to this format should have the last 3 bits of the red, green and blue intensity values removed. This reduces the image to 32768 colors, which is a lot more colors than what can be represented due to the 16 color mode setting, which disables use of background colors in the palettes (these are full screen images, so there is no need for transparency).

Now, when these images are on screen, no palettes are being used for anything else and, since they're full screen images, no other imagery is displayed anyway. I could just as easily modify the game to use 256 or 32768 color mode and be on my merry way.

But for the purposes of learning, I'd rather mess with deriving an optimization algorithm similar to what Intelligent Systems may have used. I've already done something like that for making it possible to insert battle animations into the game in question:

Xeldimation

The black caped dude is something I animated personally with my own meager art skills and hacked into the game. This should be easier, right?

Perhaps. Anyway, the full color image has to be reduced to at most 240 colors. No idea how to do that. Suppose I have, though. Now I need each tile to be reduced to only using 15 colors! What's more, the collection of all palettes must be 16 or less, which means there can only be up to 16 unique palettes for each tile to choose from. Within each tile, I could do something similar to the reduction from 256 to 240 colors, and then among the sets of palettes, I could apply similar logic to reduce the number of palettes from whatever it is to 16. But would this be optimal? It sounds too naive to be.

Thoughts?

_________________

Always keep in mind the ability to change palettes after each scanline. If you know where your image is going to go on the screen, and it's not horizontally aligned with something else using those colours, you can do as you please.
You also have the possibility of layering sprites over the image. And modifying sprites after each scanline.

_________________
143
HyperNova Software is now live (but may take a few tries to load) currently down; check out my PSP/DS/Game Boy/Windows/Linux homebrew, ROM hacks, and Gameshark codes!

Zeld: The color reduction problem you are facing is similar to the next steps I will be taking. You'll start out simply with the conversion from RGB24 -> RGB15 (or BGR15? I forget the exact color format on GBA) Depending on how many tiles your resulting image will be, color reduction will come down to only two requirements: 1) Stay within 16 colors per-tile, 2) stay within the maximum amount of palettes (8? 16?)

For example, if you had 16 palettes to use and a 4x4 tile image, your troubles would be over, because your image would not have to share any palettes between those tiles. But as the need to share palettes arises, you will want to look into some form of tile-level analysis of the image. As an example of this, assume you can use a total of 8 palettes in an 8x8 tile image; Finding the optimum palette distribution comes down to trying to squeeze similar colors together for a single palette which can be shared by up to 8 tiles (assuming an even distribution; every 8 tiles shares one of the 8 palettes). This can be done most effectively, I believe, by grouping tiles together which use fewer colors; two tiles each use only 6 colors, that gives you the chance to share four colors between the tiles, and each tile can have two totally unique colors. That just comes down to averaging similar colors or dithering the tile pixels to achieve the right look.

Just some ideas, you've probably already had similar epiphanies.

HyperHacker: Yes, those can be done. Mid-frame palette changes are tricky, because the CPU runs slower than the PPU. I believe it's one PPU clock cycle (one pixel output) for every three CPU clock cycles. Depending where in the scanline the IRQs occur (I'm thinking MMC5, due to its "ExAttributes" feature -- where the scanline counter IRQs occur near the start of drawing the line) you may have as little as 8 PPU cycles to finish changing the first palette. This assumes the left border is enabled, and the IRQ handler starts running just as the PPU wants to output its first pixel for the scanline. Changing the emphasis mid-frame is a bad idea, because the results are horrible -- I've already tested it like the images above.

Sprites are OK, but you are limited to 8 per scanline. Sprites also cannot be adjusted unless in V-blank, as I recall. There are only 64 total (either 8x8 pixels or 8x16 pixels).

These options are possible, but then again, I want to make the images non-static (able to scroll around and such things). The extra complexity won't help here.

_________________
I have to return some video tapes.

Feed me a stray cat.

Man, NES is weak. I was all about Game Boy. You can do all sorts of trippy shit on that that games never really took advantage of. Someday I should write a game that does.

Scrolling of course is entirely possible if you just update your effects to match. Also a while back on SMW Central someone posted a tool that could convert PNG images to backgrounds suitable for insertion into Super Mario World. That involved many similar tasks; eliminating redundant tiles and reducing colours. You might talk to them.

Now you've got me wanting to see what does happen when you change the emphasis mid-scanline. (Surprised you can do such a silly thing at all. O.o)

_________________
143
HyperNova Software is now live (but may take a few tries to load) currently down; check out my PSP/DS/Game Boy/Windows/Linux homebrew, ROM hacks, and Gameshark codes!

I looked at the image format more closely and learned that I actually have only 8 palettes to work with, leaving me with only 120 colors possible in an optimal case.

So here's the steps to the reduction I've conceived:

First, the image needs to be reduced from 0x1000000 colors to 0x8000 (32768). For each red, green and blue intensity I'll add 4 (half of the lowest significant bit) and then remove the last 3 bits (rounding being handled by the prior addition).

After that, I'll probably requantize the palette from 0x8000 colors to the optimal maximum, 120. There can't be more than 120 colors and I don't know that any colors will be removed from the entire palette when color reduction per-tile is done.

Each individual tile will need to be requantized to 15 colors or less, and while I'm doing this, I'll probably extract the palette for that tile and sort it.

Once I've done every tile, I'll have a collection of all the palettes for each, and will need to reduce the palette count to 8. With the palettes sorted (and the pixel values in each tile rearranged to match), I'll implement your suggestion and combine all palettes that are able to be without incident, and then I was thinking I could compare palettes easily, with them already sorted, to have more commonly occurring palettes "absorb" palettes that are very similar to them, which should be identified easily because the internally sorted palettes could be sorted themselves.

_________________

It has been used in demos and homebrews for a "transparent water" effect. Adjusting the background X-scroll per scanline to give an additional "wavy" effect is usually employed to simulate refraction. Adjusting both the X- and Y-scroll properly can simulate the refraction of light even better. But you still can't make sprites "wavy" without either modifying CHR-RAM or bankswitching CHR-ROM. Emphasis looks nice when used in this manner.

Other than that, the only use of the emphasis bits (that I am aware) is what I'm using it for; color matching.



I don't recommend the pre-rounding step. Imagine your color was full white (#FFFFFF) and you add 4 to each color component. Now your color is full black (#000000) due to integer overflow. The most correct way is just right-shifting by 3. Essentially: floor(component / 8)

If you were doing the opposite conversion (BGR15 -> RGB24) then I would recommend scaling with this algorithm:

(component * 0xFF) / 0x1F

Or, alternatively for speed reasons, this slight variation:

(component << 3) | (component >> 2)

These two algorithms produce very similar colors over the complete range of inputs (0x00 - 0x1F per component). I believe there are only four differences in the outputs, and the error is only +/-1. Some examples:

in: 0x1F, out: 0xFF
in: 0x10, out: 0x83 (slow) | 0x84 (fast)
in: 0x0F, out: 0x7B
in: 0x00, out: 0x00

This table demonstrates one of the errors, at middle-gray. On the other hand, consider just shifting: 0x1F to result in 0xF8 ... a full 7 points off full intensity, which was originally intended. In other words, rounding is far more important when scaling up.


The rest of your theory is sound; let me know how it works for you!

_________________
I have to return some video tapes.

Feed me a stray cat.

I'm not that stupid!



Way ahead of you, bro. I've needed 24->15 and 15->24 bpp conversion code for a while, and I've had it for just as long. Since about the beginning of December...last year.


Never mind; it seems a collaborator modified my code, when refactoring it, to no longer do the "(component << 3) | (component >> 2)" style upscaling, which it originally did. I had seen on another forum (Just Us League; XKeeper's site) that your suggestion was the proper way to go about the conversion, but of course, when I do "strange things" in my code, anyone refactoring it just assumes it's extraneous and removes it. Unfortunately, only one person has ever refactored my code for me, so...urgh, I was NOT happy to see that just now.


Much better. *whew*


Nice table; I didn't realize that the shifting thing was actually just a speedier version of something more representative of what was taking place.

I've updated my previous post, actually; I'm having trouble using the optimized palette I've extracted for dithering purposes.

_________________

Do you use any source control? It might be helpful with multiple people working on the project.


And since you insist on rounding for your down-scaling, how are you handling the non-linear scale that it introduces? I can present some data to show you what I mean by that:

For all input component values, there are 8 steps available to create a specific output (for example, any of the inputs 0x7C ... 0x83 will output 0x10), with two exceptions:
1) Output 0x00 can only be produced within a range of 4 steps for input: 0x00 ... 0x03.
2) Output 0x1F is given the largest range of 12 steps for input: 0xF4 ... 0xFF.

You can imagine what this would look like if it were graphed...

_________________
I have to return some video tapes.

Feed me a stray cat.

Okay, that's tossed.

Now, can you help with the dithering? I tried applying this, but the pseudo code there is clearly flawed (wouldn't be the first time Wikipedia had inaccurate pseudo code) and my corrections to it, while seemingly working, didn't produce good looking images.

What are YOU using? If you can't tell me that, then what's the "common dithering algorithm" you started with?

Basically, what do I do with my optimized palette once I have it?

_________________

I guess I didn't link to my sources.

Everything I learned about dithering came from the libcaca wiki. In particular, the section on error diffusion. The simplest dithering algorithm (which is what I started with) is "Filter Lite." It uses this matrix:



For every pixel, you take half of the error (the difference between the original and color-reduced pixels) and add that to the pixel directly following. At the same time, add one quarter of that error to the pixels directly below, and its preceding pixel. I even opted to make the matrix simpler for many of the screenshots included in the original post:



Just add half of the error to two pixels: one following, one directly below. The result was quite acceptable.

To calculate the error, I simply subtracted the "paletted" (color-reduced) pixel components from the corresponding original pixel components. Something like this:



Then when you're doing the dither (this pseudo-code is for the pixels where you are distributing half of the total error):



Where clamp() simply keeps the component within the range 0x00 ... 0xFF.


So, the basic flow of dithering algorithms do pretty much what wikipedia describes:
1) Get the original pixel from the image
2) Find the closest matching color in your reduced palette
3) Calculate the error
4) Put the closest color into the image
5) Update the surrounding pixels by distributing fractions of the error to them

Step 5 is the crucial element: Since you are only replacing pixels which have not been processed yet, they will receive slightly different colors from your palette (either darker or lighter) on the following iterations to keep the overall image appearing like it still has the same shades. The libcaca "study" article has better information on the subject. Something else you will want to use: "serpentine parsing" (also described in the article) to avoid generating artifacts by the error distribution.

_________________
I have to return some video tapes.

Feed me a stray cat.

I JUST got my Floyd-Steinberg dithering algorithm fixed before I came here and saw your post.

Turns out, I had originally used the entire color integer for determining the error, and the first time I did that I was even applying the addition of the product of the coefficient and the error directly to the integer. That was stupid, and I was wondering why wikipedia made it seem correct in the rather nondescript pseudo code. I finally decided "okay, that must not be what they meant, because it makes no sense" and separated the errors between the individual R, G and B intensities.

Finally I realized that while I had accurately handled overflow, as I had predicted it would occur, I had forgotten to handle underflow (I forgot I was adding negative values, too!). After accounting for underflow as well, I got it working rather nicely.

My matrix, as you might know if you saw anything about Floyd-Steinberg in your research, is

[0][0][0]
[-][X][7]
[3][5][1]

With the likely not optimal palette optimization (paradox much?) code I have, this dithering algorithm yields rather impressive results, or at least, competes with the image editing utility that I would be using externally when not trying to have all of the reduction functionality in one place. Next up is requantizing within tiles, and finally...the hard part, reducing the total number of 16 color palettes to 8.

Edit: Haha, 1337th post.

_________________

That's why you explain what you're doing with a comment.

_________________
143
HyperNova Software is now live (but may take a few tries to load) currently down; check out my PSP/DS/Game Boy/Windows/Linux homebrew, ROM hacks, and Gameshark codes!

I believe it would be easiest [for me] to reduce the image to black-and-white. Since NES only has 6 shades of gray, I can squeeze them all into an optimized background palette with ease. The palette is optimized such that each 4-color palette shares at least one shade (not counting the background color) with every other palette. This is what it looks like, using black as the background (common) color:


And with white as the background color:


The idea is that adjacent tiles in the image need to share some colors between them. But each tile should also be given the chance to display its own unique colors. If, for example, adjacent tiles only shared one color (the background color) then the image would (more often than not) have very sharply-defined tile edges. This is because the tiles cannot happily blend into one another, due to the restriction of only sharing a single color. To put it shortly: the more colors each tile shares, the smoother the image will be; but with a lowered color depth. This is the balance I wish to achieve with full-color images.

But for black-and-white images, this should be a piece of cake! Or at least, that's the theory. And you can imagine based on the example palettes above that it's indeed true. I would bet that using the same pattern on any arbitrary 6-color palette would also work, but 6-color palettes are generally bad for full-color reproduction. To remedy this, I've come up with a few possible patterns for 10- and 11-color palettes (remember, 13 colors is the maximum supported on NES without any fancy mid-frame effects) optimized for sharing colors between tiles. Here they are in ASCII glory:


The 11-color pattern shares a color (not including the background!) between palette #0 and #1, and a different color between #2 and #3. It does not share colors between #0 and #2, #0 and #3, #1 and #2, or #1 and #3. The 10-color pattern only changes that limitation by sharing yet a different color between #1 and #2. The 6-color patterns (see images with black-and-white patterns above) are the only ones that can share at least one color between all four of the background palettes. This is the compromise (balance) to be made: more color-sharing, or more overall colors?

10 is close to the median between the minimum (6) and maximum (13) for NES (the actual median is 9). So that's probably the pattern that I will use first. Arranging the colors within that pattern should be a matter of placing the most distant colors into the unique slots: [2][3][5][7][8][9]. Note that by "distance" I mean distance based on the 3-dimensional HSV scale, and not the "most or least used colors" scale.

That's the theory. I'll test the NES 6-shades-of-gray pattern with per-tile color reduction, as my next task. And then probably the 6-color pattern with color just to see what it looks like. Screenshots and further analysis to follow.

_________________
I have to return some video tapes.

Feed me a stray cat.

This didn't seem reasonable or efficient, and I had another idea that was faster/easier to code that I tried.

Basically, after requantizing the whole image to 120 colors and each tile to 15, I requantize a copy of the 120 color image before requantization of the individual tiles to 8 colors. However, as a boon of using the median cut algorithm, instead of actually using just those 8 colors, I can grab the entire box that reduces to each of those 8 colors and use the pixels in that box to be one of the 8 palettes I'm allowed.

The image keeps a lot of detail in a lot of places and does a good job with the colors, with one predictable flaw: the tiles are VERY distinct. It's...ugly.

I had an idea earlier for having the 8 palettes be less than 15 colors each and share some colors between them. This guarantees the image won't be 120 unique colors as is the optimum scenario, but it should smooth out transitions between tiles. Actual images in this format in the game I'm hacking don't even use all 8 palettes sometimes. Usually they only use 6, which allows for 6 * 15 = 90 colors, and one of the images I looked at used only 83 unique colors of a possible 90.

I don't have any solid ideas on how to decide which colors to share between which palettes or how many colors should be shared (although I can determine the latter by looking at some output with different settings applied). If you have any ideas, that'd be great. If not, well, I'll mess with it some more and let you know how that turns out.

_________________

You'll have to explain that with some pictures and maybe pseudo code.

_________________
I have to return some video tapes.

Feed me a stray cat.

Which part? The goal? My current approach? Or both?

My current approach...if you don't get the terminology regarding the median cut algorithm, there's lots of articles about it. I imagine you already understand that stuff what with the whole "color reduction for NES" thing that started this thread, unless you wound up using octrees or something less well known.

As for the goal...


See how different tiles of that image use different palettes from the 8 I have in that red box? Also note how 2 of the 8 palettes aren't even being used. I need a way to take an image with about 80 colors and pick the 8 palettes (120 colors, only "about 80" of which are unique) that optimally represent the image so that when each tile is recolored to use one of those palettes, the result won't look like a blocky piece of crap.

This example uses 87 of a possible 90 colors. Very optimal...

_________________

Actually, I'd like to see the following statements visualized step-by-step (or similar) in a series of screenshots with annotation. Because reading just this much is difficult to follow:


...


My best idea (so far) to this end is attempting to match colors at just the edges of tiles; ignore pixels in the center. However, I haven't even got this far in my NES color reduction project.

I ran into an obstacle where the optimal palette for some tiles is not one that's actually available. You'll see in my black-and-white palette examples above, that not all combinations are used, because that's impractical/impossible while keeping a high-ish total color depth. Using just the tile edges in this case might also be applicable, though. At least it will help to ensure you pick the closest possible match that will allow for smooth transitions after requantizing the tile(s).

_________________
I have to return some video tapes.

Feed me a stray cat.

The image walkthrough will have to wait, as I have another thing I'd like to try. Focusing on the tile boundaries seems to be the only way to advance this application, but instead of considering matching colors on boundaries, I thought about adding an extra dithering step.

When the final 8 palettes are decided, the palette of those 8 most similar to that of an individual tile is determined and the tile is recolored to use this palette. During this process, each color in the tile is replaced with the color in the new palette that it is most similar to, even if other colors have already been replaced with that color from the new palette. This means that if the palette is a poor match, flat areas of color appear that detriment the image's smoothness.

I'm thinking that if the above color process were modified to dither the tile to account for the quantization errors resulting from the naive recoloring, the individual tiles that would be looking bad would look much better. If it isn't significant enough of an improvement, then the dithering will have to be modified to account for inter-tile errors. This border-crossing dithering will hopefully help smooth the tile transitions.

Edit: This is the method in my code that is doing all the work, with a lot of extra fluff cropped out.

At line 9, "startImage" is reduced to 40 colors. Why 40? Because each palette can have 15 colors, there's 8 palettes, and 10 of the slots in the palettes need to be left empty for colors that will be shared.

Following that, the array of the tiles is filled with 15 color versions of each tile (line 28 is the end of this). The tiles are treated as having 15 colors with no background color, unlike they usually would be when calling my GBA_Image class's BufferedImage constructor.

I take startImage, which is currently a 40 color image, and "reduce it to 8 colors". This becomes "tempReducer". These 8 colors are each the average of 5 colors (probably similar if not the same as the 5 colors in each of the 8 palettes I'm building).

3 of those 10 spaces in each of the 8 incomplete palette are filled with the average color of the palettes immediately left and right of the palette being filled in the array of palettes, which I've noticed will have palettes that are more similar closer together in the array as a side effect of the color reduction code. This entails lines 60 through 81 in that sample source.

The remaining 7 colors in the 8 incomplete palettes are filled by taking the average color of the palette being filled and averaging it with each average color of the other 7 palettes, except with "weights" applied to the two colors. The weights are the frequencies the colors in the palettes occurred, so the averaging is biased toward more important colors. Lines 83 through 119 handle this.

Now I have 8 palettes with 15 colors each, the BG color in this case being negligible as the image is intended to be full screen with no transparency. I proceed to assign each tile in the image the palette of these 8 that best suits it, and recolor each color in that image with the color that is best suited to it from the assigned palette, regardless of whether other colors are better matches (this was mentioned earlier). The last block of code in the sample source handle this.

Finally, I have all the data in a form that can fit in the GBA's VRAM, and render it for debugging purposes. To my dismay, the images aren't quite as tolerable as I would hope, but they're so much better than what I was getting originally.

If you need more explanation on anything other than the median cut algorithm I'm using for color reduction, just ask. If you need some pictures illustrating what median cut is doing, might I suggest reading this?

An image from the previous link that might help you understand more quickly:



The rectangular prisms in the lower right of that image are determined by dividing the color space along the median (center of the array of colors) after sorting the color space (array) along the widest axis (e.g. if the greatest intensity difference among all the colors is a difference in red intensity, you sort the colors by their red intensity). These rectangular prisms are called "boxes", the colors they represent are the average of all the colors they contain, and the colors within them are what I've been referring to.

_________________

Just one problem: Your pastebin is expired.

_________________
I have to return some video tapes.

Feed me a stray cat.

Blargh. I must have set it for a day instead of a month or forever like I should have.

Well, you can find the full code in the source here. D/L that, unzip it, go to src/Graphics/CG_Image.java and have a look at the "initFromImage" method.

Here's a video of my progress (image of interest first seen about 10 seconds in):

Custom CG

_________________

ZOMG, boobies.

It's a bit difficult to tell from the video compression, but it looks fairly good. Raw screen shots, maybe?

_________________
I have to return some video tapes.

Feed me a stray cat.

Raw, eh? Sure. But it's not nearly as good as it looks in the video. The lower quality of the video codec makes it harder to see the issues.

Before:


After:

_________________

Exactly.

Thanks for that, now I have a much better idea of your descriptions. Yes, you can clearly see where it needs work, but the result is still impressive for such an early attempt.

On the subject, I was thinking just the other day about a way to actually make my own algorithm actually work. Sadly, it's a brute force algorithm, but at least it will bring results.

My thought is, NES only has four available background palettes to choose from, per tile. Knowing that, I can choose the "best" matching palette by dithering the image four different times (one for each BG palette) and calculating the overall error per tile. From the beginning:

1) Reduce the original image to gray scale. (I'm fond of using the luminance component after converting the RGB to CCIR 601 (with gamma correction); the result is sharp and looks a lot more like the saturation has been set to 0, than the much simpler HSL/HSV calculation of luminance/value.
2) Build a complete background palette. This can either be a simple pattern like the gray scale pattern a few posts above, or an optimal series of patterns can be produced by analyzing the gray scale image; either will function about the same.
3) Reduce the gray scale image to four colors using one of the BG palettes, with dithering enabled.
4) Calculate the overall error on every tile; the total error will be far greater when dithering is disabled.
5) Repeat steps 3-4 for all four BG palettes.
6) For each tile in the output image, pick the corresponding tile from the four dithered images; choose the one with the lowest amount of error.

Unless I'm mistaken, this should turn up decent results on NES-compatible 6-color gray scale images. I would like to try this idea when I have time. If it works out well enough, I will see what can be done about reducing the amount of overhead (dithering the image 4 times is way too much -- but you can see why I called this a "brute force" algorithm). Then attempt to do the same with full-color palettes.

_________________
I have to return some video tapes.

Feed me a stray cat.

That does sound pretty brutal, yeah.

I know in my particular case I can eliminate the tiling by increasing the number of shared colors, but the image loses a lot of detail when I do this. I still haven't tried dithering across the entire set of 600 tiles. I tried dithering with each tile when assigning the final palette and it made the image look like a series of horizontal bars. Even though dithering isn't intended to be done for individual sections of an image, as it neglects the likely large errors that will occur on the corners of the previously dithered sections, I don't think it should be turning up bars like that. But I know my dithering code works because it's used for the first reduction to ~120 colors.

Whatever; I have New Super Mario Bros. Wii, lots of free time to play it and evidence that what I have so far works fine on images more suited to the game I'm hacking. Off to stomp goombas~

_________________

Remember to do your dithering with the "serpentine parsing" method, as it will reduce the amount of pattern artifacts. I've also tried per-tile dithering, and the result was less than spectacular. Patterns were mostly apparent at the tile edges. If at all possible, you must distribute quantization error to all pixels; don't bother artificially restricting yourself to tile boundaries.

_________________
I have to return some video tapes.

Feed me a stray cat.

Yes, yes, I know. I'm just not sure how to refactor my code yet to allow crossing tile boundaries during the final dithering stage.

As for serpentine dithering, I've been doing that since the beginning. I have my code set up such that I can switch to other dithering schemes by modifying arrays defined at the top of the code, but the serpentine parsing is done inline.

_________________