¿Formas de reconstruir píxeles mezclados de un archivo de video?

Suponga que tiene un archivo de video cuyo orden de píxeles se ha barajado una vez. Es decir, un orden aleatorio se definió una vez y se aplicó a todos los marcos.

¿Existe algún enfoque conocido para recuperar el orden inicial de píxeles?

Tengo algunas ideas sobre cómo recuperar la topología inicial colocando píxeles cuyos valores están correlacionados en el espacio y el tiempo más juntos. Me pregunto si esto ha sido estudiado y si se publicaron algoritmos eficientes.

Además, este problema puede considerarse como una forma de proyectar en una matriz 2D un conjunto de valores que varían en el tiempo para poder aplicar técnicas de visión por computadora (como CNN), con el supuesto de que estos valores están de alguna manera correlacionados.

Este es un problema combinatorio fascinante. Presentaría cada píxel usando su trayectoria temporal completa, luego los incrustaría en una cuadrícula usando los k vecinos más cercanos. El objetivo real es maximizar la probabilidad de que el video sea una secuencia de imágenes naturales (de la vida real), que puede probar con un clasificador, pero puede escapar con solo un costo de suavidad; digamos, la suma de las diferencias entre píxeles adyacentes. Una vez que haya comenzado a completar la cuadrícula, las restricciones de suavidad reducirán el espacio de búsqueda (ya que un píxel tendrá que estar cerca de varios otros píxeles), acelerando así las cosas, suponiendo que esté utilizando una estructura de datos eficiente para consultar a los vecinos más cercanos; ver por ejemplo http://www.itu.dk/people/pagh/SSS/ann-benchmarks/

No existe una solución general a esto, incluso si agregamos algunos supuestos sobre la distribución de, por ejemplo, colores y formas en las imágenes o el acoplamiento temporal, como los marcos consecutivos que son similares.

Problema

Deje que sean los cuadros originales, cada uno con píxeles. Sea la permutación que se aplica a los píxeles de cada cuadro antes de que los obtengamos. Puedes pensar en como el libro de códigos del enemigo.$F_1,\dots,F_i$$n$$m$$P$$P$

Ahora, como entrada estamos recibiendo . El objetivo es encontrar la permutación inversa para restaurar las imágenes. Por lo tanto, es el mapa de identidad y, por ejemplo, . Tenga en cuenta que no conocemos ninguno de los cuadros correctos .$P(F_1),\dots,P(F_n)$$Q$$QP=I$$Q(P(F_1))=F_1$$F_i$

Deje que Sea elposibles funciones de permutación de los píxeles.$Q_1,...,Q_{m!}$$m!$$m$

El objetivo es seleccionar la única De manera que .$j\in\{1,\dots,m!\}$$Q_jP=I$

Sin solución general

Según nuestro modelo estadístico, esto significa seleccionar que maximiza la probabilidad de que se extraiga de la misma distribución que las estadísticas de referencia para imágenes y las estadísticas temporales entre cuadros consecutivos y que es nuestro conocimiento previo.$Q_j$$Q_j(P(F_i))$$Q_j(P(F_{i})$$Q_j(P(F_{i+1})$

Hay un contraejemplo canónico donde el enemigo te da una película revuelta con dos cuadros donde todos los píxeles son del mismo color, entonces , y para cada . Por lo tanto, para todos los , las estadísticas dentro del cuadro y entre cuadros son equipables para cada y no nos brindan información para seleccionar la permutación de probabilidad máxima (excepto en el caso degenerado donde ).$n=2$$F_1=F_2$$Q_j(F_1)=Q_j(F_2)=F1=F2$$j$$j$$j$$Q_j$$m!=1$

Por lo tanto, no podemos garantizar la unicidad y el problema no se puede resolver sin más suposiciones.

Supuestos adicionales

Es interesante ver si podemos resolver el problema agregando más restricciones.

Si restringimos al enemigo a que solo nos envíe películas "reales" y suponiendo que haya suficientes píxeles y marcos diferentes para que un único con la máxima probabilidad, aún tendríamos que calcular estadísticas para permutado marcos para encontrar el máximo.$Q_j$$O(m! \times n)$

Esto es descifrar códigos de fuerza bruta.

Para beneficiarse de las redes neuronales, y de la retropropagación en particular, necesitaríamos una función de pérdida diferenciable con respecto a la entrada (que es una codificación de o nuestra permutación ). La pregunta, entonces, sería ver si se puede encontrar dicha función.$j$$Q_j$

De lo contrario, el problema es más similar al criptoanálisis en el caso especial donde sabemos que el libro de códigos del enemigo es una permutación del texto claro (o imagen clara).