3
$\begingroup$

A formal description of the problem:

Given a set $P$ of $n^k$ points in $d$ dimensional space, what algorithm can I use to find a mapping between them and points on a $n \times n \times n...$ grid in $k$ dimensional space so that points that are close together in $P$ map to points that are likely to be close together on the grid?

An example of the problem:

Suppose I want to create a 4096 by 4096 image with every possible color that can be stored as a 24-bit RGB value (8 bits per color channel). $P$ is the set of all points in RGB colorspace when using 8 bits per channel, and the grid I'm mapping it to is the image. How can I do this so similar colors end up close together?

I came up with a solution involving a genetic algorithm: it swaps pixels, then compares how similar they are to the other pixels in that region. This solution, however, is very computationally intensive, and requires a lot of time to produce good results. Below is an image generated using the genetic algorithm.

Around 5 minutes of computation on four cores

The genetic algorithm I coded has already been heavily optimized at all levels. It's coded in C++; rather than swapping a single pixel it analyzes groups of 64 randomly selected pixels and uses the Hungarian Algorithm to find the optimal way to swap all pixels in the group; the fitness function has been written to allow multiple pixels to be tested at one location with each pixel adding practically no additional computational cost; I've been able to parallelize it too. The above picture is the result of 5 minutes of work. After a few hours of computation it produces this:

enter image description here

Although I'm hoping to find a faster and more elegant way to go about solving this problem.

Using the image analogy, the metric I'm using to calculate fitness is pretty simple. The fitness of the total image is the sum for every pixel of the color distance squared divided by the image distance squared to all the other pixels. To calculate color distance, just treat the color as a vector in 3-dimensional space (red is x, green is y, blue is z) and find the euclidean distance. The image distance is just the distance between two pixels in the image. If $g$ is the function that maps points in $P$ onto the grid, then the fitness is:

$$\sum_{p \in P} \sum_{q\in P \mid q \neq p} \frac{\left\lVert p-q\right\rVert^2}{\left\lVert g(p)-g(q)\right\rVert^2}$$

(In the image example, $g(p)$ returns the x and y coordinates of the pixel with the color whose red, green, and blue channels match $p$)

This function is very expensive to calculate, however there are a number of optimizations that can be made to speed up the calculation a lot, and in general it's not important to calculate the actual fitness; just the change in fitness that would result from swapping some group of pixels (which makes the computation a lot faster). If someone knows of a better metric to use please let me know!

$\endgroup$
  • $\begingroup$ I have probably misunderstood previously the problem given. Localisation is a method of grouping close data to be in close bins so you do not have to check vast amount of points. Contraction, or quantisation here would change larger spectrum of colors to smaller ones, preserving as much as possible. But now, from the image it looks like SOM (self organising map). I see the connection between images, but I do not fully understand from what data the first one was produced and what is the goal. I think that your question is clear (just not for me). Do you have at hand some 8x8 example with data? $\endgroup$ – Evil Jul 6 '17 at 23:00
  • $\begingroup$ The first image was produced using the same process as the last image; just with a lot fewer iterations. At the very start of the algorithm, an image containing all the colors to be used in the final image is generated and then the pixels are randomly shuffled (resulting in an image that's basically just noise). Pixels are then swapped in large groups, with the swapping being done so as to maximize the fitness function. The first few iterations produce very noisy results, but as it progresses the noise is slowly removed. I generated the images as a way to visually judge how the algorithm. $\endgroup$ – J. Antonio Perez Jul 6 '17 at 23:06
  • $\begingroup$ Look at t-SNE, nonlinear dimensionality reduction, and techniques for visualizing high-dimensional data. Is that the sort of thing you're looking for? $\endgroup$ – D.W. Jul 7 '17 at 1:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.