The joy of validating technical research

Recently, I became obsessed with the idea of a Pokemon breeding game. Like those old creature simulators Grophland and Howrse, what if you could breed for unique coat colors? In the normal Pokemon games, there are only a few variations of Pokemon colors, dubbed shiny and regional variants.

Could I simulate coat color breeding with simplified genetics? Maybe. Before I get ahead of myself, I’m going to try something easier: generating randomly colored Pokemon. I just need the ability to swap palettes.

random_rgb(rattata)

Ok, that was easy enough. Looks a bit unnatural, so the next step would be toning down the possible colors. Something about parametrizing genetic factors… *mumble mumble*. I won’t be covering that in this post, because I encountered a far more interesting issue: reading someone else’s document.

Precision Decision #

If I want to design a function that can input a bajillion genes, and spit out a coat color manifestation, I need to be able to represent melanin, which is a pigment. The most common way to represent colors for computer rendering is the Red-Green-Blue (RGB) color model. However, it’s not intuitive to manipulate. As an artist, I am used to thinking in terms of pigments and intensity. Hence, for my purposes, the Hue-Value-Saturation (HSV) model is easier to grasp. Still, computers display color through photons, and photons are best represented by RGB. Any HSV calculations or manipulations have to be converted to RGB in the end.

I need a way to freely convert between RGB and HSV. There are libraries that already have these conversion theorems implemented, such as Python’s built-in colorsys.

Unfortunately, colorsys uses float numbers, so there is a possibility of introducing rounding errors. I had some issues where, after performing multiple conversions between HSV and RGB, the color would drift. For example, #4E1F8D would become #4E1F8F, where the color would be off by 1 digit. This can be solved if you properly round floats before converting to integers, but then you’d have to remember to do it for every operation. I want less things to worry about…

In real life, randomness and mutations are inevitable, but for a game, and especially for a breeding mechanic, I don’t want unintentional randomness. I need to convert between RGB and HSV with whole numbers, so no decimals allowed.

An internet search brought me the research paper “Integer-Based Accurate Conversion between RGB and HSV Color Spaces” by Vladimir Chernov and co.

This looks promising! Since I am a degenerate who only knows how to copy others, I decided to copy the author’s source code. Luckily, this paper mentions open source: “The source code of all the tests can be found in the author’s repository [21]. The code is published under open source license.”

Hooray! I click on the reference… and the repository is gone.

On a positive note, the algorithm is fully explained in the research paper. If I follow the researchers’ steps, I’ll be able to figure it out. Right?

Hiccups #

Within the first step, I encountered a problem.

1. Find the maximum (M), minimum (m) and middle (c) of R, G, and B.

The middle?? What does that mean? Nowhere in the paper is the defintion of middle mentioned.

What is the middle of RGB? Average? Mean, median mode? Since RGB can be visualized as a coordinate in a 3D cube, does it mean the midpoint distance of the RGB vector?

(probably overthinking it)

The search for meaning #

In Python and most programming languages, there are max([r,g,b]) and min([r,g,b]) functions which pick the biggest and smallest numbers of a set. Self-explanatory. However there’s no mid([r,g,b]) function.

I reread the paper just to make sure I didn’t miss anything. The word middle only appears twice in my CTRL + F search. Not many results for mid either. The closest human-like explanation is:

The middle component and sector offset are determined according to previously found maximum (M) and minimum (m).

I still don’t get it, so “google” time.

My search lead to some cool answers: Bitwise XOR operator ^ to calculate middle in Java. Fasinating syntax. I got sidetracked and read about bitwise shift operators. I will not remember what I’ve learned, though, because I cannot ever remember which side of an equation is right or left.

In a moment of clarity, I searched for the most basic of terms, the author’s name and repository: chernov colormath. Scrolling through the results quite far, I found a Q&A forum: “How to calculate mid value of RGB image in matlab?”

The top answer by Walter Roberson contains a link to the source code by the authors of the paper. Scored gold!

The middle is the median of the R, G, B tuple. If you have RGB(100, 20, 60) where the highest value is Red @ 100, and the lowest value is Green @ 20, then the middle is Blue @ 60. The remainder that is neither the max nor the min, hence, known as the “middle.”

I ported the algorithms to Python. The RGB to HSV algorithm worked great. The reverse conversion from HSV to RGB failed.

Now what?

The Chernov paper claims that the algorithm works, with no loss or errors. If this claim is true, my only recourse is to examine the source code instead of the paper.

Long story short, I examined their source code and derived the missing step: sector inversion inverse.

if I == 1 or I == 3 or I == 5
  then F = E * (I + 1) - H

It should be performed as a part of step 5:

With the missing piece found, I implemented their HSV to RGB algorithm in Python:

E = 65537

def hsv_to_rgb(h, s, v) -> tuple[int, int int]:
    """Note that the hsv must be in the form given in the Chernov paper,
    which is ([0-393222], [0-65535], [0-255])
    NOT the typical ([0-359, [0-100], [0-100])"""
    
    delta = ((s * v) >> 16) + 1
    minimum = v - delta 

    if h < E:
        i=0
    elif h >= E and h < 2 * E:
        i=1
    elif h >= 2 * E and h < 3 * E:
        i=2
    elif h >= 3 * E and h < 4 * E:
        i=3
    elif h >= 4 * E and h < 5 * E:
        i=4
    else:
        i=5

    # The missing step: sector inversion inverse
    if i == 1 or i == 3 or i == 5:
        f = E * (i + 1) - h
    else:
        f = h - (E * i)

    mid = ((f * delta) >> 16) + minimum

    if i == 0:
        return v, mid, minimum
    elif i == 1:
        return mid, v, minimum
    elif i == 2:
        return minimum, v, mid
    elif i == 3:
        return minimum, mid, v
    elif i == 4:
        return mid, minimum, v
    else:
        return v, minimum, mid

The rest of my code can be found here.

What is sector inversion inverse? #

The HSV space can be visualized as a pyramid racetrack. 3D coordinates have negative and postive axes.

If the sector (a slice of the hexagon) is located in a negative coordinate space, then you want to pick an easier starting point. Kinda like when describing a point on a circle, a -540° rotation is the same as 180°. The hue value H wraps around, so you want to normalize it.

The variable I represents one of 6 sectors. F is a mysterious value that relies on the correct negative sign. Then perform the opposite–invert the inverse–for the HSV algorithm, because it’s a backtrack of the RGB conversion algorithm. That’s my limited understanding.

Takeaways #

I learned a lot from trying to reproduce someone else’s research, and it requires the utmost of patience. Would I have been able to figure out the missing step without the source code? Maybe if I stared at the paper long enough.

Or I might’ve have to retrace everything, which means stepping into the authors’ shoes, adopt the prior model of triple experts, figure out why they made certain decisions, and arrive at the same conclusion. Sounds easy.

Giving up is an option. I could just live with floating-point rounding errors, forever checking if I handled integers correctly.

AI to the rescue…? #

During my entire research phase, I did not use artifical intelligence at all. When I was writing this article, I thought about how I failed to make use of the available tools at my disposal. Could I have asked ChatGPT to help me determine the meaning of “middle”?

Close, but no cigar. The explanation of “median value that divides the range of 0 to 255 into two equal halves” would’ve confused me more. If I used ChatGPT’s definition, I probably wouldn’t have gotten anywhere.

How about the HSV to RGB algorithm?

Long story short, ChatGPT gave me an algorithm (lines 156-182) that was wrong. Maybe if I was better at prompt writing, I’d get more accurate results.

It’s hard enough to write in a way that a human understands. How much harder is it to write something a robot can understand?

References #

Chernov, Vladimir, Jarmo Alander, and Vladimir Bochko. “Integer-Based Accurate Conversion between RGB and HSV Color Spaces.” Computers & Electrical Engineering 46, no. C (August 2015): 328–37. https://doi.org/10.1016/j.compeleceng.2015.08.005.