A continuous function for defining unique values to a 1024x1024 image with a 24 bit 3 color channel image

Question

I need to generate a color map which I am not sure exist. I have a 1024x1024 image which would contain 2^20 pixels. I have 3 color channels which each have 8 bits which would leave us with 2^24 possible colors. This means that there would actually be enough different pixel values for a unique value for a 4096x4096. This problem is easy to solve with non continuous colors where you simply use 4 bits of the final channel on both of the first two channels to create two 12 bit channels.

Here is an example of the non-continuous version:

Each of the individual sub-squares has a different blue value which gives us a unique value. This may be hard to see with the eye, as they are only changing by a very small amount. Using this technique, it is easy to fill up an entire 4096x4096 with unique, mathematically predictable colors.

Unfortunately, I have a new constraint where all three channels of the map must remain continuos. What I mean by this is that each individual neighboring pixels channel value does not change by more than one in value. For instance, a pixel with a red value of 10 may have direct neighbors with a red value of either 9, 10 or 11 The reason for this constraint is that when sampling from this texture, individual neighboring pixels may be sub-sampled and linear interpolated together and when going along the edge of the sub-boxes, this would result in inaccurate values.

To put it in a slightly different way, I need a function f and f^-1

f(x, y) = r, g, b

f^-1(r, g, b) = x, y (only existing in the original x,y range)

with r, g, b, being 8 bit numbers (the integers 0 - 255) and x and y being 10 bit numbers (the integers 0 - 1023). All neighboring r,g,b values must be continuous. By continuous, I mean that each individual neighboring pixels channel value does not change by more than one in each channel. Do such functions exist, and if so, what are they?

Answer 1

This problem is very roughly analogous to having a square piece of paper and you want to fold it so that it fits into a cube, except both the paper and cube are discrete, and the folds of the paper can pass through themselves under certain conditions. I'll just post the image now and maybe later post a more thorough explanation if there is interest. The image may be wrong, I've only proved it correct, not checked it.

Here's the python code, including tests and image creation. I think it displays the transpose of the image pasted into this answer. The logic is not so complicated; basically you fold the image like a map to fit into the rgb color box.

from itertools import islice
import numpy as np
import Image

def first_fold():
    r"""

          x       x
         / \     / \
    x   x   x   x   x
    |   |   |   |   |
    x   x   x   x   x
    |   |   |   |   |
    .   .   .   .   .
    .   .   .   .   .
    .   .   .   .   .
    |   |   |   |   |
    x   x   x   x   x
    |   |   |   |   |
    x   x   x   x   x
     \ /     \ /
      x       x

    """
    segment_length = 204
    q = 0

    while True:
        for i in range(segment_length):
            yield q, 1 + i
        q += 1

        yield q, 1 + segment_length
        q += 1

        for i in range(segment_length):
            yield q, segment_length - i
        q += 1

        yield q, 0
        q += 1


def second_fold():
    """

          aabbccddeeff
         a bacbdcedfe f
        a b cadbecfd e f
       a b c daebfc d e f
      a b c d eafb c d e f
     a b c d e fa b c d e f
    a b c d e f  a b c d e f

    """
    segment_length = 136
    k = 6
    q = 0

    while True:
        for i in range(segment_length):
            yield q, k + i
        q += 1

        for i in range(k):
            yield q + i, k + segment_length + i
        q += k
        for i in range(k):
            yield q + i, k + segment_length + (k-1) - i
        q += k

        for i in range(segment_length):
            yield q, k + segment_length - 1 - i
        q += 1

        for i in range(k):
            yield q + i, (k - 1) - i
        q += k
        for i in range(k):
            yield q + i, i
        q += k


def good_image(image):
    arr = np.asarray(image)
    n = arr.shape[0]
    if arr.shape != (n, n, 3):
        return False
    colors = set(tuple(x) for x in arr.reshape(n*n, 3))
    if len(colors) != n*n:
        return False
    if (arr < 0).any():
        return False
    if (arr > 255).any():
        return False
    e = np.abs(arr[1:, :, :] - arr[:-1, :, :])
    if (e > 1).any():
        return False
    e = np.abs(arr[:, 1:, :] - arr[:, :-1, :])
    if (e > 1).any():
        return False
    return True

def bad_image(image):
    return not good_image(image)

def main():

    assert(good_image([
        [[1, 1, 1], [1, 2, 1]],
        [[1, 1, 2], [2, 2, 2]]]))

    assert(good_image([
        [[0, 0, 0], [0, 1, 0]],
        [[0, 0, 1], [1, 1, 1]]]))

    assert(good_image([
        [[2, 20, 200], [1, 19, 199]],
        [[1, 19, 200], [2, 19, 200]]]))

    assert(bad_image([
        [[1, 1, 1], [1, 2, 1]],
        [[1, 2, 1], [2, 2, 2]]]))

    assert(bad_image([
        [[0, 0, 0], [0, -1, 0]],
        [[0, 0, -1], [-1, -1, -1]]]))

    assert(bad_image([
        [[255, 255, 255], [255, 256, 255]],
        [[255, 255, 256], [256, 256, 256]]]))

    assert(bad_image([
        [[2, 20, 200], [1, 19, 199]],
        [[1, 19, 200], [2, 19, 201]]]))

    assert(bad_image([
        [[2, 20, 200], [1, 19, 200]],
        [[1, 19, 199], [2, 19, 201]]]))

    n = 1024
    arr = np.zeros((n, n, 3), dtype=int)
    for u, (q, x) in islice(enumerate(first_fold()), n):
        for v, (a, b) in islice(enumerate(second_fold()), n):
            y = q + a
            z = b
            arr[u, v, :] = (x, y, z)

    assert(good_image(arr))

    img = Image.fromarray(arr.astype(np.uint8))
    img.show()


main()

By the way, you can get a 2048x2048 solution by changing only three constants: segment_length 136->204, k 6->11, n 1024->2048. This still uses only 1/4 of the available colors, and to exceed 1/2 you will need deeper changes than changing constants.

The reason for the 1/2 barrier is that this method uses twice the color density near creases of the second fold than at less interesting parts of the image.

Answer 2

Unless I'm missing something in your conditions, it seems that a pair of 12-bit Gray Codes can be used to do what you desire on a $2^{12}\times 2^{12}$ board (which you could then take any $2^{10}\times 2^{10}$ sub-board of this board for your purposes).

Let $G_0...G_{4095}$ be a 12-bit Gray code. To each pixel $(x,y)$ in your $2^{12}\times 2^{12}$ board, split the concatenation $G_xG_y$ into 3 8-bit substrings; these will be the channel colors. Within a given row, the first 12 bits of the 24 channel bits are constant (so the red channel is constant across rows) and there is exactly one bit that changes between $(x,y)$ and $(x,y+1)$ in the second 12 bits (so only one of the three channels is changing, although as $y$ moves along that channel will sometimes be the blue channel (when the difference of $G_y$ and $G_{y+1}$ is in the final 8 bits) and sometimes in the green channel (when the difference of $G_y$ and $G_{y+1}$ is in the first 4 bits). Similarly, down columns the blue channel is constant and the red and green channels are changing depending on where the difference between $G_x$ and $G_{x+1}$ occurs. Furthermore it is trivial to invert this mapping given an RGB point; simply split the green channel between the left and right, then look up the position of each 12-bit half in the original Gray Code.

Incidentally you can make many such mappings from this Gray Code method by mixing where the bits from $G_x$ and $G_y$ go in the RGB coordinates while still maintaining the stronger condition that exactly one channel changes from one bit to a neighboring bit. For example, sending the bits of $G_x$ to the even position bits of the RGB bits and the bits of $G_y$ to the odd position bits is one way to allow all three channels to change within each row or column.