9
$\begingroup$

Suppose that you have a video file which pixel order has been shuffled once. That is, a random order have been defined once and applied to all frames.

Does it exist some known approach for retrieving the initial order of pixels?

I have some ideas around retrieving the initial topology by placing pixels which values are correlated in space and time closer together. I wonder if this has been studied and if efficient algorithms were published.

Also this problem can be thought of as a way to project to a 2D matrix a set of values varying in time in order to be able to apply computer vision techniques (like CNN), with the assumption that these values are indeed somehow correlated.

$\endgroup$
  • 1
    $\begingroup$ This seems like a toy problem or hacking challenge? At least it seems unrelated to real-world video encryption, because it would terrible for bandwidth and not very secure, whilst encrypting the byte stream using e.g. AES is fast and reliable. I suppose one immediate question is: Do you have actual data and a problem to solve, or are you asking in the abstract, just out of interest? $\endgroup$ – Neil Slater Sep 30 '17 at 16:04
  • $\begingroup$ Right, the potential applications is not related to decryption / hacking but really aim at applying computer vision techniques to any domain where data is not organized as images... by organizing data as images anyway. So, if the toy problem can be solved on videos, I believe it could have interesting developments applied to non-natively-2D data. $\endgroup$ – Denis Dollfus Sep 30 '17 at 20:22
  • $\begingroup$ Seems interesting, although I think very much in a "try it and see if it works, figure out any theory later" kind of way. There's no reason in my mind to suspect that correlation between features in an arbitrary data set should allow construction of a grid-like graph. Although for data sets where it did then I can see the reasoning where it could be useful to use image analysis on the re-arranged data. Whether or not anyone has looked at this unscrambling of pixels depends whether it would relate to any useful or an interesting problem - I cannot think of one, but I'm no researcher . . . $\endgroup$ – Neil Slater Sep 30 '17 at 20:49
  • $\begingroup$ I just ran into similar problem but in different context: dsp.stackexchange.com/questions/59808/… $\endgroup$ – Dilawar Jul 30 '19 at 4:50
4
$\begingroup$

This is a fascinating combinatorial problem. I would featuring each pixel using its full temporal trajectory, then embed them in a grid using the k nearest neighbors. The real goal is to maximize the likelihood of the video being a sequence of natural (real life) images, which you can test with a classifier, but you might be able to get away with just a smoothness cost; say, the sum of differences between adjacent pixels. Once you have started filling in the grid, smoothness constraints will reduce the search space (since a pixel will have to be close to multiple other pixels), thus speeding things up, assuming you are using an efficient data structure for querying the nearest neighbors; see for example http://www.itu.dk/people/pagh/SSS/ann-benchmarks/

| improve this answer | |
$\endgroup$
5
$\begingroup$

A general solution to this does not exist, even if we add some assumptions about the distribution of e.g. colours and shapes in the images or temporal coupling such as consecutive frames being similar.

Problem

Let $F_1,\dots,F_i$ be the $n$ original frames, each with $m$ pixels. Let $P$ be the permutation that is applied to the pixels of each frame before we get them. You can think of $P$ as the enemy's code-book.

Now, as input we are receiving $P(F_1),\dots,P(F_n)$. The goal is to find the inverse permutation $Q$ to restore the images. Thus $QP=I$ is the identity map and for example $Q(P(F_1))=F_1$. Note that we do not know any of the correct frames $F_i$.

Let $Q_1,...,Q_{m!}$ be the $m!$ possible permutation functions of the $m$ pixels.

The goal is to select the unique $j\in\{1,\dots,m!\}$ so that $Q_jP=I$.

No General Solution

Under our statistical model this means selecting the $Q_j$ which maximises the likelihood that $Q_j(P(F_i))$ is drawn from the same distribution as the reference statistics for images and the temporal statistics between consecutive frames $Q_j(P(F_{i})$ and $Q_j(P(F_{i+1})$ which is our prior knowledge.

There is a canonical counter-example where the enemy gives you a scrambled movie with two frames where all the pixels are the same colour, so $n=2$, $F_1=F_2$ and $Q_j(F_1)=Q_j(F_2)=F1=F2$ for every $j$. Thus, for all $j$, the in-frame and inter-frame statistics are equiprobable for each $j$ and give us no information to select the maximum likelihood permutation $Q_j$ (except in the degenerate case where $m!=1$).

Thus, we cannot guarantee uniqueness and the problem is unsolvable without further assumptions.

Further Assumptions

It is interesting to see if we can solve the problem by adding more constraints.

If we restrict the enemy to only sending us "real" movies and assuming there are enough different pixels and frames to so that a unique $Q_j$ with maximum likelihood exists, we would still have to calculate statistics for $O(m! \times n)$ permuted frames to find the maximum.

This is brute force code-breaking.

In order to benefit from neural networks, and back-propagation in particular, we would need a differentiable loss function with respect to the input (which is an encoding of $j$ or our permutation $Q_j$). The question then, would be to see if such a function can be found.

Otherwise the problem is more similar to cryptanalysis in the special case where we know that the enemy's code book is a permutation of the clear-text (or clear-image).

| improve this answer | |
$\endgroup$
  • $\begingroup$ The mention of enemy made me wonder whether one could forge a scrambled movie that would have two solutions that would both look like real movies. $\endgroup$ – Denis Dollfus Nov 10 '17 at 12:27
  • $\begingroup$ This is core of the problem I am facing right now: dsp.stackexchange.com/questions/59808/… . Though I can assume that activity (in the video linked to this post) is spare and clustered. $\endgroup$ – Dilawar Jul 30 '19 at 4:53

Your Answer

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

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