Disclaimer

I am not a Rust developer. I am probably doing several things either poorly or not idiomatically. Don’t use this to learn Rust, but it’s probably a reasonable use of the strategy pattern in general.

All code referenced in this post available at this repo

Pixel Swapping

Several years ago I ran across this problem on the code golf stack exchange and it has stuck with me as an interesting problem. I come back to it now and then as a nontrivial problem to use as a basis for learning new language features. It’s particularly interesting because there is no “right” answer, and lots of ways to try to solve it.

The core idea is that we want to take the pixels from picture A and use them to make picture B. As an example, using Starry Night to create Mona Lisa can be done like this:

Strategies

The Default Strategy

Let’s see where the lowest-effort strategy gets us. Start at the upper left pixel, iterate over each pixel in order, find the closest pixel in our source palette, place the pixel and remove it from the source palette.

Not great. We can do better.

Center-Out Strategy

The middle of the image is probably the most important to get right. Instead of starting in the upper left, just start in the middle and work outward.

Better, but what else can we try?

Single Shuffle Strategy

Don’t prioritize any specific part of the picture. Just shuffle the pixels and fill in the best match from the palette and hope that it works out.

Different, probably better for this particular set of inputs at least.

Repeated Random Substitution Strategy

Finding the best pixel choice from a palette for a given goal RGB value is slow. What if we just try picking two random pixels and switching them if it brings the overall RGB values closer to the goal, and do that like a whole bunch of times?

For some sets of inputs, this ends up better than the single shuffle. For some sets of inputs, it ends up worse.

Using the strategies

Which should we use, then?

All of them! Or, implement them all and pick out which to use at runtime rather than compile time. It’s a user problem if they pick the wrong tool for the job.

MapStrategy trait

We will be making use of a MappedPixel struct, which contains the source coordinates, destination coordinates, and colors.

First, make a trait that requires a struct to implement a function that takes in an image as a source and an image as a destination, and returns a vector of MappedPixel. How that is implemented is irrelevant, as long as we get a populated vector back.

pub trait MapStrategy {
    fn map_pixels(source: &RgbaImage, destination: &RgbaImage) -> Vec<MappedPixel>;
}

Create a struct for the strategy that we want to implement and implement the trait.

pub struct ShuffleStrategy;

impl super::MapStrategy for ShuffleStrategy {
    fn map_pixels(source: &RgbaImage, destination: &RgbaImage) -> Vec<MappedPixel> {
        let mut palette = MappedPixel::map_source_pixels(source);
        let mut dest_palette = MappedPixel::map_source_pixels(destination);
        dest_palette.shuffle(&mut thread_rng());

        dest_palette.iter().for_each(|x| {
            let index = MappedPixel::find_closest_pixel(&x, &palette);
            palette[index].dest_x = x.src_x;
            palette[index].dest_y = x.src_y;
            palette[index].used = true;
        });

        return palette;
    }
}

Create a Mapper struct

This feels like I should be able to do something like pub struct PixelMapper<T:MapStrategy> or something, but I could not for the life of me get the compiler to agree so maybe someone can email me the correct way to do this. I just powered through.

I created a struct that just had a string field for the name that we will call as a command line argument and the function that we’ll call to execute the mapping strategy.

pub struct PixelMapper {
    pub name: String,
    pub map_strategy: fn(&RgbaImage, &RgbaImage) -> Vec<MappedPixel>,
}
impl PixelMapper {
    pub fn new(name: String, map_strategy: fn(&RgbaImage, &RgbaImage) -> Vec<MappedPixel>) -> Self {
        Self { name, map_strategy }
    }
}

Initialize the strategy options

Create a function that initializes all of the strategies that we have available to use. Give the strategy a name and a reference to the function to call. The list is shortened for readability.

fn initialize_strategies() -> Vec<PixelMapper> {
    let mut strategies = Vec::new();
    strategies.push(PixelMapper::new(
        "default".to_string(),
        DefaultStrategy::map_pixels,
    ));
    strategies.push(PixelMapper::new(
        "random".to_string(),
        RandomStrategy::map_pixels,
    ));
    strategies.push(PixelMapper::new(
        "center".to_string(),
        CenterOutStrategy::map_pixels,
    ));
    //[...]
    return strategies;
}

Create an execution function

Create a function that accepts the strategies that we initialized and a key to decide which one to execute, as well as the arguments that will need to be passed on to the chosen function. It returns an Option<Vec<MappedPixel>> as it could return None if the key is not found

This is where you can do some logic to decide on the best strategy to implement if not taking it as a user input. For example, you could instead check the size of the images and default to the Repeated Random Substitution strategy over a given size, as the runtime is exponential and larger images take a long time with the other strategies.

fn execute_strategy(
    strategy_name: &str,
    strategies: &Vec<PixelMapper>,
    source: &RgbaImage,
    dest: &RgbaImage,
) -> Option<Vec<MappedPixel>> {
    return match strategies.iter().find(|x| x.name == strategy_name) {
        Some(x) => Some((x.map_strategy)(source, dest)),
        None => None,
    };
}

Finally, use it

With all of these pieces in place, the main function is relatively small. The first half is just parsing the arguments and loading the images. We then just take the images and arguments and pass them off to the execution function.

    match execute_strategy(strategy_name, &strategies, &source_img, &dest_img) {
        Some(mut x) => MappedPixel::save(
            &dest_img.width(),
            &dest_img.height(),
            &mut x,
            format!("output/{0}.png", strategy_name),
        ),
        None => {
            let names: Vec<String> = strategies.iter().map(|x| x.name.clone()).collect();
            println!("Strategy options are: {:?}", names.join(", "));
            return;
        }
    }

As a very useful side effect of having the strategies collected into one vector, we can provide the user with an error message telling what the available strategies are.

❯ cargo run images/starrynight.png images/monalisa.png outside
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 0.09s
     Running `target/debug/pixel_swap images/starrynight.png images/monalisa.png outside`
Strategy options are: "default, random, center, green, shuffle"