Pallet Swapping

In this session, we’re going to look at a technique which can be used to alter sprites in games, specially vector-style or pixel-art images.

Note	you can find the sample code for this session on the Github Server

Identifying the pallet

Our first step in the process is to identify what colours have been used in the images. To do this, we’re going to store an array of the colours we’ve seen so far, and if the colour is not in the list we’ve seen, we will add it to the list.

Note

This approach has horrible performance, there are better ways to do this (ie, using a map or set), but we’ve not looked at these types yet. As a result, we’re going to do this, 'the old fashioned way'. There are ways to improve the performance of this approach, which we’ll consider later as extention tasks.

This approach works best on images with a limited pallet. Luckly, I’ve already identified a suitable set of images for you to use. Kenney offers Pixel-Art assets under a public domain (CC-0) licence.

Writing our function

We’re going to refer to the set of colours used in an image as its pallet. Some image formats (gif, indexed PNG) actually do this internally to save space. The image is then represented as a sequence of pallet indexes. Some very old graphics hardware also did this (and could do the technique we’re discussing today in hardware).

For our purposes, we need a function that:

Takes an image as an argument
Returns an array containing the list of colours for that image, terminated by our sentinel value

The basic idea is that, if the image contained three colours, (255, 0, 0), (0, 255, 0), and (0, 0, 255) then we would expect an array back that looked like this:

Index	0	1	2	3	4…N
value	(255, 0, 0)	(0, 255, 0)	(0, 0, 255)	Sentinel	??

Index

4…N

value

(255, 0, 0)

(0, 255, 0)

(0, 0, 255)

Sentinel

Storing our pallet

If we were using a map, we could resize the array dynamically as required. We’ve not learnt about dynamically-sized types (Maps, Lists, Sets, etc…) yet, so whatever we use will need to have a fixed size.

We’ll be using arrays for this purpose, which have a fixed size when they are created. We don’t know ahead of time how many colours we’re going to need. We need to make it 'big enough' for any possible number of colours we will encounter.

To create an array, we use the following syntax:

// NOTE: SIZE_HERE is actually the size, like 10 or 100.
int[] myValue = new int[SIZE_HERE];

We don’t want to store int, our array will be of SkColor. How many colours could our images have?

Array Size

Example 1. How many colours could there be in the image?

In the worst case, every single pixel is a different colour. This would mean there are width*height colours in the image. We also could use the maximum possible number of colours (256 * 256 * 256), but that is probably excessive for our purposes. Most pixel art images (classical ones at least) use very restrictive pallets.

Rather than use this 'worst case' estimate, lets assume that any image that contains more than 100 colours is not worth trying to perform pallet swapping on, as we will have too many colours to consider. As a result, I’m going to create an array that is 101 (100 colours plus our 'end marker').

Note

this is considered a fairly lazy technique in some circles. You could dynamically resize the array as needed, or once we know the final size we could copy the data into an array that’s just big enough. For this program, it’s not worth considering. Besides, for audio, we’ll probably be using fixed-size buffers anyway.

Sentinel Values

Because we’re not going to be altering the size of our arrays to make them the right size, we need a way of being able to mark the end of the array. We could pass the size of the array around as required, but instead, I want us to consider one of the things mentioned when we were talking about strings.

Just like when I was talking about storing strings, we’re going to put a special value at the end of the array to indicate that there are no more colours in the array. This is similar to how \0 indicates the end of a string in some languages. This use of an 'end marker' is more commonly referred to as a Sentinel value, so that’s what I’ll call it for the rest of the session.

Example 2. What value should we use as our sentinel?

Well, we want something that won’t happen in our images very much. We could use some obscure colour, but I’m going to use SkColors.empty which corresponds to all channels being 0 (R,G,B,A). Using zero in this way has a few advantages:

firstly its consistent with how strings behave
it’s also the default value that colours get set to, so our array should contain this by default (although in my sample code I explicitly set this to be sure).

Planning our function

Ok, so we know the how big our array will be, and we know what information we need. Here is what our function signature looks like:

public static SKColor[] GetPalletColours(SKBitmap image)

What steps do we need to perform to process this image?

Click to reveal the answer

Here are the steps I’ve identified:

Create an array to store our pallet
loop through the image, pixel by pixel
1. if this is our sentinel value, skip (we can’t store this!)
2. If this is a colour we’ve not seen before:
  1. add it to the pallet

A few of these steps will require a bit more thought that would first appear. How do we know if we’ve already seen this colour? How do we keep track of how may colours we’ve already seen? A few of these steps we should already be familiar with from previous sessions (looping through the image).

We can use a technique we’ve already encountered for figuring our if our pallet contains this colour, search. Specifically, linear search. In theory, we could also use binary search if we were careful about inserting items into the array. That would make the code a lot more complicated though, and as we’re dealing with such small values (N less than 100), it’s not worth the extra effort.

Sub Task 1: Pallet Length

In languages like C, which use the 'array of characters' representation of strings, this is how functions like strlen are implemented (which additional optimisations for faster performance). You can see this in glibc.

Before we move on to how this impacts our linear search implementation. I want to consider the case where we want to know how many colours are already in our array. We need to loop through the array, and when the current index is our sentinel value (SkColors.Empty), stop - returning the current index.

Here is one possible implementation of this idea:

public static int PalletLength(SKColor[] pallet) {
	for (int i = 0; i < pallet.Length; i++) {
		if (pallet[i] == SKColors.Empty) {
			return i;
		}
	}
	return 101;
	//return MAX_PALLET_SIZE;
}

Sub Task 2: Linear search

Next, we’re going to implement linear search. I’ve provided a method stub for this in the code for this session. You can use the code above to help you.

static int FindPalletIndex(SKColor[] pallet, SKColor search) {
	// Steps:
	// Loop through the pallet - if we encounter the sentinel value then break;
	// if we see search, then return the current index

	// end of the array and no match
	return -1;
}

Implementing the method

We’ve now got everything we need to implement our pallet method. I’m going to give you a partial implementation, you need to sort out the parts of the code labelled TODO:

public static SKColor[] GetPalletColours(SKBitmap image)
{
	// TODO create an array of SKColor, at least 101 in size.

	// we'll use an int to keep track of how many items are in the pallet aready
	int size = 0;

	for (int x = 0; x < image.Width; x++) {
		for (int y = 0; y < image.Height; y++) {
			var colour = image.GetPixel(x, y);

			// we need to be careful about our sentinel value being in the image...
			if (colour == SKColor.Empty) {
				continue;
			}

			// TODO use `FindPalletIndex` function from earlier to check if the colour is already in pallet (ie, it returns -1).
			// TODO if it is *NOT* then add colour to pallet at index _size_ and add one to size
		}
	}

	// TODO set the last unused index (size) to be SkColors.Empty

	return pallet;
}

Outputting the pallet

We will output the pallet to terminal/console so we can see what colours are present. We also could dump this to a 1 pixel by N image if we want to see these visually.

You should know how to do this for a single colour (Formatting) from the first session we did together. You will also need to loop through the pallet, stopping at the sentinel value.

I’ve provided you with a class that contains utility functions, named SKUtils. This contains some of the operations we’ve been doing a lot over the past few sessions (opening image files, saving them) as well as some functions for outputting a text file which contains pallet data. It also contains a method to read this file back.

Using the main method I’ve provided and the following image file, check your code works as you expect:

This is what that pallet output should look like:

pallet.txt

  R   G   B   A     Hex
200 224 255 255 #C8E0FF
192  62  65 255 #C03E41
 62  71  81 255 #3E4751
 44  51  58 255 #2C333A
245  92  92 255 #F55C5C
255 255 255 255 #FFFFFF

I’m outputting the standard red, green, and blue channels. I’m also outputting the alpha (transparency) channel. I was hoping to avoid that for this session, but some of my sample images where encoding some very strange things in the channel, so I needed to match on it as well. You can treat this as if it was another colour channel. We probably don’t need to modify this.

Tip	you could in theory use the alpha channel matching to replace a transparent background with a solid colour. Some older sprite-based games actually have a 'mask' image of the background pixels (1 bit texture).

I’m outputting the hex values so I can figure out which colour is which using a graphics program (or by putting them into a search engine). The file reader does not care about these, it’s just to make our lives easier. Try checking some of these values. We’re looking for the red colours and we want to leave the others (windows, tyres, etc…) untouched.

Performing the swap

We have outputted the colours in the image. We can then modify the red, green and blue values in this text file and use it for performing the swap. I’ve replaced the red colours with blue ones to generate a blue version of this sprite. This is my modified pallet file:

pallet_blue.txt

  R   G   B   A     Hex
200 224 255 255 #C8E0FF
62  133  192 255 #C03E41
 62  71  81 255 #3E4751
 44  51  58 255 #2C333A
92  155  245 255 #F55C5C
255 255 255 255 #FFFFFF

I’ve provided a function which can read files in this format, and return a SkColor array in the same format as the pallet (sentinel at the end). The basic idea is that we will extract the pixel colour from the image, find the index in the original pallet array which corresponds to this colour, then find the corresponding index in our replacement pallet. Do this for every pixel and we have swapped the image.

There are a few special cases we need to be aware of:

If original image contains our sentinel value, we cannot tell the difference between it and the end of array marker.
- We will skip any pixel in the image that is the sentinel value, leaving it unchanged.
If the pallets are not the same length, then this approach will fail.
- I’ve ignored this issue. I have an extension task for it later.
If the image we are swapping contains a colour which was not in the original image, we don’t know what to replace it with.
- I’ve ignored this issue. I have an extension task for it later.

If you handle these cases well, and your images are all have the same pallet (ie, all images use the same reds for team colours), it makes it reasonably easy to swap these pallets our as required. A modification of this idea is how The Dwarves of Glistenveld makes team colours work. It’s also been used for animations in the past, with some really quite cool effects. Some games also use this techique for avatar customisation (eg, allowing eye and hair colour customisation). We also do this in TDOG for dwarf hair colour.

Pallet Index

The first function we will need to write for this part is a function which can find a colour at a given index. We can reuse FindPalletIndex from earlier, which is why I made the function return the index rather than true or false.

Swap Function

This is what the swap algorithm might look like:

public static void SwapPallet(SKBitmap image, SKColor[] original, SKColor[] newPallet) {
	for (int x = 0; x < image.Width; x++) {
		for (int y = 0; y < image.Height; y++) {
			var colour = image.GetPixel(x, y);

			// TODO if this pixel is the sentinel (SKColors.Empty) value, continue

			// TODO, implement pallet swapping:
			// get the index of `colour` in the original pallet, using `FindPalletIndex` save it to a variable called `index`
			// get the colour at `index` in newPallet and save it into a variable called newColour
			// use SetPixel(x,y, newColour) to update the pixel
		}
	}
}

If you run this code, providing the blue pallet from earlier, you should get the following image:

Extension Tasks

If you are feeling overwhelmed

Prompt the user for the filename for the modified image
Try modifying the code to skip any colour which is not present in the pallet (ie, FindPalletIndex returns -1).
Modify the code in the Main method to give the user the option to load the pallet from disk, rather than always fetching it from the image, you can use my code to help guide you
Check your modifications work by removing the non-changed lines from both pallet files and reruning the script.

If you are feeling confident

Derive the new filename based on the path the user has provided, if they provide D:/images/test.png, then you should calculate the new filename as D:/images/test_swapped.png
Handle user input errors more gracefully. If the user provides a filename that does not exist, then prompt them again. hint: File.Exists
Alter the flow of the main method for processing multiple files:
- Users should be asked if they want to generate a new pallet, if they say yes ask for the source file and generate the pallet file, then exit.
- If they say no, prompt them for the existing source and replacement pallet files to use
- Ask them repeatedly for a new file to convert, using the logic above, generate swapped image files, named automatically
- Allow the user to finish processing by typing 'STOP'

You can use the kenney.nl Vechile pixel pack for testing

(Advanced) If you want a challenge

Do the above tasks first.
Using both my worksheet 2 unit tests and the handful of tests I have provided for this session as inspiration, write unit tests for the methods.
Find possible issues with the functions that you or I have implemented (consider edge cases and how they should be handled)
Fix the edge cases in the code and re-run your tests
Using the manual for SkiaSharp, figure out how to generate a graphical representation of the pallet and output it to disk as pallet.png (similar to my test.png image you used for greyscale conversion).