Reconstructing a screen of permuted pixels
Summary
Given a video with the pixel locations randomly permuted (once, for the entire video), can we (efficiently) reconstruct the original picture?
Let:
- $n=w\times h$ pixels.
- $m=\text{number of frames}$
Details
- You are given an LCD screen with $n = w \times h$ pixels, that has been altered so that the pixel locations are permuted, once, in some random manner.
- Watching a video on this LCD screen would obviously result in quite a garbled picture.
- The permutation is mapped by some unknown function, we shall call $\text{permute}\left(x_0,y_0\right) \implies (x,y)$
- Each pixel on the screen has some permuted coordinate $(x,y)$ and some unknown original coordinate $(x_0,y_0)$ (such that $\text{permute}\left(x_0,y_0\right)=(x,y)$).
- You (and your computer) are given to watch a particular video of an average film (movie) of average length, with $m$ frames, and having the same resolution as the LCD screen; however for simplicity, assume the video will be in grayscale (for example, each pixel is a single color in the range $[0,256)$).
- You do not know *which* film is being played.
- You (and your computer) can rewatch the garbled film as many times as you like.
- As a frame of reference, you are also informed which pixel is the lowest location in the original non-permuted screen (i.e you are given the values $x$ and $y$, such that $(x_0,y_0) =(0,0)$, and $\text{permute}\left(0,0\right)=(x,y)$).
Goal
- Algorithm to (efficiently) compute the mapping of the pixels to their original locations.
- Can this be done in $o\left(n^2\right)$ space (i.e in better than $\mathcal O\left(n^2\right)$ space?)
- Can this be done in $o\left(n^2f(m)\right)$ time?
- I'm not sure how to ask this question correctly, but I am mostly wondering about reducing the $n^2$ factor.
- Is this a known problem, or similar to any known problems?
PS. What about same question but for the case of binary images for each frame instead of grayscale.
Appendix
Figure 1 Example permuted "LCD screen", side view
Figure 2 Example permuted "LCD screen", front view
Figure 3 Example video frame (color)
Figure 4 Example permuted video frame (color)
Figure 5 Example video frame (grayscale)
Figure 6 Example permuted video frame (grayscale)
Figure 7 Example video frame (binary, using most-significant-bitplane)
Figure 8 Example permuted video frame (binary)
Related source codes are on gist.github.com
Credits:
- Images courtesy of NASA (NASA GoPro footage from EVA 30). More info on archive.org. Licensed under the Creative Commons Public Domain Mark 1.0 license)