8
$\begingroup$

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:

non-continuous map

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?

$\endgroup$
15
  • 1
    $\begingroup$ how can you hope for an invertible relation from $2^{24}$ to $2^{20}$ elements? $\endgroup$ Sep 23, 2014 at 19:15
  • 8
    $\begingroup$ Put differently: You look for an injective mapping $f:2^{10}\times 2^{10} \to 2^8\times 2^8\times 2^8$ which is Lipschitz continuous with constant 1 where we put the $1$-norm on $2^{10}\times 2^{10}$ and the $\infty$-norm on $2^8\times 2^8\times 2^8$. $\endgroup$
    – Dirk
    Sep 24, 2014 at 6:24
  • 2
    $\begingroup$ @David, I have a question meant to ensure that Dirk's interpretation is correct. What do you mean by neighbouring pixels? Do you mean pixels which share an edge, or do you also allow pixels which are located diagonally from each other (only share a vertex)? $\endgroup$ Sep 24, 2014 at 14:18
  • 2
    $\begingroup$ @RicardoAndrade - For my application, the diagonals would not matter, as they could be no more than 2 different given the direct neighbor rule of a difference of 1. $\endgroup$
    – David
    Sep 24, 2014 at 17:54
  • 1
    $\begingroup$ @PerAlexandersson - Ok, not all combinations 2^216 may be a bit much, but I could test different starting values and positions and get a decent idea. $\endgroup$
    – David
    Sep 24, 2014 at 18:27

2 Answers 2

7
$\begingroup$

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.

enter image description here

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.

$\endgroup$
4
  • $\begingroup$ On first look, this seems to be a solution! I've up voted and will accept tomorrow after doing some verification. Thanks for the amazing answer! $\endgroup$
    – David
    Sep 25, 2014 at 4:37
  • 1
    $\begingroup$ Haha, +1 for quoting D. Knuth. $\endgroup$ Sep 25, 2014 at 6:11
  • $\begingroup$ Can you include the proof that it is correct? The origami analogy was also what I am thinking about, but I had some difficulties at the corners where multiple folds meet. Even just some pseudo-code (instead of the full Python code) with comments would be great! $\endgroup$ Sep 25, 2014 at 7:24
  • $\begingroup$ @WillieWong For this problem I doubt there is a correctness proof more convincing than an example that can be checked by computer, but more comments could be added, especially regarding the tricks to deal with corner creases. $\endgroup$
    – guest
    Sep 25, 2014 at 14:54
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ It is worth noting that if you want to allow more than one channel at a time to change in each direction, but still maintain that at most 1 bit changes within each channel, you can start with a pair of (8,4)-Gray Codes, one for each direction. Then, for example, let the $R$-channel bits be determined by the high bits of each of the 8 symbols (thought of as elements of $\{0,1\}^3$) coming from the two codes, and similarly the $G$-channel bits be determined by the middle bits, and the $B$-channel bits determined by the low bits. $\endgroup$
    – ARupinski
    Sep 24, 2014 at 20:44
  • $\begingroup$ I think i may have jumped too quickly and not understood what you were saying. I am going to try and implement this. I will either accept the answer or edit my question including a picture of why this doesn't work after I test. $\endgroup$
    – David
    Sep 25, 2014 at 1:19
  • $\begingroup$ I was unfamiliar with Gray Codes. Looking at them, it became apparent that this would unfortunately not work. The reason being that this is an engineering problem and we have no control over some parts of the generating software and the graphics hardware. Because of this, we cannot interpret this as Gray codes and going from a number like 0010 to 0110 would be a jump of 4. The sub-pixel value between these two pixels could then be interpreted as any value in between which would not map to the correct position. Let me know if this does not make sense or you feel I am incorrect. Thanks! $\endgroup$
    – David
    Sep 25, 2014 at 1:39
  • 3
    $\begingroup$ Also, just to clarify, its not a change of one bit per channel that is the restraint. Its that the value may not change more than 1 in value. So a pixel with a red value of 10 may have direct neighbors of either 9, 10 or 11. $\endgroup$
    – David
    Sep 25, 2014 at 1:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.