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

8

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.

Denis Dollfus
fuente
1
¿Esto parece un problema de juguete o un desafío de piratería? Al menos parece no estar relacionado con el cifrado de video del mundo real, porque sería terrible para el ancho de banda y no muy seguro, mientras que cifrar el flujo de bytes usando, por ejemplo, AES es rápido y confiable. Supongo que una pregunta inmediata es: ¿Tiene datos reales y un problema que resolver, o está preguntando en resumen, simplemente por interés?
Neil Slater
Correcto, las aplicaciones potenciales no están relacionadas con el descifrado / pirateo, sino que realmente apuntan a aplicar técnicas de visión por computadora a cualquier dominio donde los datos no estén organizados como imágenes ... organizando los datos como imágenes de todos modos. Entonces, si el problema del juguete se puede resolver en videos, creo que podría tener desarrollos interesantes aplicados a datos 2D no nativos.
Denis Dollfus
Parece interesante, aunque pienso mucho en una forma de "pruébelo y vea si funciona, descubra alguna teoría más tarde". No hay ninguna razón en mi mente para sospechar que la correlación entre las características en un conjunto de datos arbitrarios debería permitir la construcción de un gráfico similar a una cuadrícula. Aunque para los conjuntos de datos donde lo hizo, puedo ver el razonamiento en el que podría ser útil utilizar el análisis de imágenes en los datos reorganizados. Que alguien haya visto o no este descifrado de píxeles depende de si se relacionaría con algún problema útil o interesante. No puedo pensar en uno, pero no soy un investigador. . .
Neil Slater
Me encontré con un problema similar pero en un contexto diferente: dsp.stackexchange.com/questions/59808/…
Dilawar el

Respuestas:

3

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/

Emre
fuente
4

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.F1,...,FyonortemetroPAGSPAGS

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 .PAGS(F1),...,PAGS(Fnorte)QQPAGS=yoQ(PAGS(F1))=F1Fyo

Deje que Sea elposibles funciones de permutación de los píxeles.Q1,...,Qmetro!metro!metro

El objetivo es seleccionar la única De manera que .j{1,...,metro!}QjPAGS=yo

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.QjQj(PAGS(Fyo))Qj(PAGS(Fyo)Qj(PAGS(Fyo+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 ).norte=2F1=F2Qj(F1)=Qj(F2)=F1=F2jjjQjmetro!=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.QjO(metro!×norte)

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.jQj

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).

mjul
fuente
La mención del enemigo me hizo preguntarme si uno podría forjar una película revuelta que tuviera dos soluciones que parecieran películas reales.
Denis Dollfus
Este es el núcleo del problema que estoy enfrentando en este momento: dsp.stackexchange.com/questions/59808/… . Aunque puedo suponer que la actividad (en el video vinculado a esta publicación) es de repuesto y agrupada.
Dilawar