Cheap and Secure Web Hosting Provider : See Now

[Solved]: Rearrange pixels to maximize visually distinguishable pattern

, , No Comments
Problem Detail: 

I have a dataset full of 0s and 1s, and when I visualize it with t-SNE, which does dimensionality reduction. There is clearly some structure in it as shown below. Each color corresponds to a particular category. There are 10 categories, and there are roughly 180 data points for each category. Each data point is a 64-dimension vector, i.e. there are 64 features. The category information is NOT used by t-SNE, and the coloring is applied after t-SNE run is done.

enter image description here

Since the dataset is all 0s and 1s, and each data point is a 64 vector, so I thought I could plot them as 8x8 dimension binary images as shown below. I have plotted 3 examples for each category

enter image description here

If you compare among images in a single column, there appear to be some similarity sort of. If you compare among images in a single row, they look random to me. My question is that is there such an algorithm for rearranging the pixels, which is equivalent to reordering the elements in the original 64-dimension vector, so that MAXimize the visual similarity among images in each column (i.e. make them look as similar as possible) while MINimizing the visual similarity among images in each row (i.e. make them look as different as possible)? The whole point to make it easy to spot visual patterns for different categories if possible.

Update:

Thank you for @aelguindy's answer. For the record, I posted what the images look like before scrambling.

enter image description here

This notebook shows how the scrambled version is generated. This dataset is only for experiment. I have another real dataset of 0s and 1s that have nothing to do with hand-written images, of which I was trying to find visual patterns if possible.

Asked By : zyxue

Answered By : aelguindy

This will not be an algorithm in the usual sense. It's a bunch of heuristics that you may find useful. The main difficulty comes from the undefined nature of the phrase "visually similar".

If I understand your question correctly. You have a few separate problems:

Defining what pairwise "visual similarity" is

You are looking for a function $S$ of two vectors to the interval $[0, 1]$. I imagine that you want it to ideally satisfy the following:

  • $S(\vec{x}, \vec{x}) = 1$, which means that a vector is most visually similar to itself.
  • $S(\vec{x}, \vec{y}) = S(\vec{y}, \vec{x})$, which means that measuring similarity between $x, y$ does not depend on their order.
  • $S(\vec{1}, \vec{0}) = 0$, which means that the most unsimilar vectors are the all-ones-vector and all-zeroes-vector.

Even with these restrictions you have a lot of choices. You can just count the number of matching pixels, but a one pixel shift in the image could give you maximum mismatch even if the images are visually very similar.

One simple heuristic that may suffice is counting all matching pixels. Then adding the number of $2\times2$ squares having a matching number of ones (sliding the comparison over all possible sub-squares), ..etc. You can try giving less weight to bigger squares. If you normalize by the maximum value you get (which is computed by comparing an image to itself). You get a value from 0 to 1. It's clear that this satisfies the assumptions above and captures similarity better than just comparing pixels.

These ideas are just examples of what you can do. If you experiment a bit, you can find some interesting $S$'s that capture your personal notion of visual similarity.

Deciding what you want to maximize for the data set.

Now assuming you have such an $S$, the question becomes what do you want to optimize. For a column (resp row), you can compute the sum or the median or the minimum (resp maximum). You can try to maximize the average column similarities minus the average row similarities or something of that sort.

Again, for an abstract $S$ that is not perfectly defined, you need to try different options and see what works best. As a guideline, optimizing for median vaguely means you optimize the common case, while allowing for outliers.

Quickly computing a permutation on $[1 \dots 64]$ that maximizes this quantity.

For some choice of $S$ and a choice of optimization criterion, it is extremely unlikely that you will find an efficient algorithm that finds the permutation optimizing that criterion. As you noticed in your question, the number of permutation grows very quickly with the size of the image.

One common heuristic that works quite well and is really easy to code, is local search. The idea is:

// Obj(p) is the criterion to be maximized. opt = null for t trials: p = random permutation for s steps: p' = copy p randomly swap two (or three) elements of p' if Obj(p') > Obj(p): p = p' if Obj(p) > Obj(opt): opt = p

This usually works well in practice. You have the knobs s and t that control the running time, you can even run the different trials fully in parallel. Increasing them usually yields better and better results. t controls the number of "starting points" for the search, which s controls the depth of the search. Again, you will need to experiment a bit.

Hope this helps.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/65239

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback