Maneiras de reconstruir pixels embaralhados de um arquivo de vídeo?

Suponha que você tenha um arquivo de vídeo cuja ordem de pixels foi embaralhada uma vez. Ou seja, uma ordem aleatória foi definida uma vez e aplicada a todos os quadros.

Existe alguma abordagem conhecida para recuperar a ordem inicial de pixels?

Tenho algumas idéias para recuperar a topologia inicial, colocando pixels cujos valores estão correlacionados no espaço e no tempo mais próximos. Gostaria de saber se isso foi estudado e se algoritmos eficientes foram publicados.

Além disso, esse problema pode ser pensado como uma maneira de projetar para uma matriz 2D um conjunto de valores variando no tempo, a fim de poder aplicar técnicas de visão computacional (como a CNN), com a suposição de que esses valores estão de alguma forma correlacionados.

Este é um problema combinatório fascinante. Eu caracterizaria cada pixel usando sua trajetória temporal completa e os incorporaria em uma grade usando os k vizinhos mais próximos. O objetivo real é maximizar a probabilidade de o vídeo ser uma sequência de imagens naturais (da vida real), que você pode testar com um classificador, mas pode conseguir sair com apenas um custo de suavidade; digamos, a soma das diferenças entre os pixels adjacentes. Depois de começar a preencher a grade, as restrições de suavidade reduzirão o espaço de pesquisa (já que um pixel precisará estar próximo a vários outros pixels), acelerando as coisas, assumindo que você esteja usando uma estrutura de dados eficiente para consultar os vizinhos mais próximos; veja, por exemplo, http://www.itu.dk/people/pagh/SSS/ann-benchmarks/

Uma solução geral para isso não existe, mesmo se adicionarmos algumas suposições sobre a distribuição de, por exemplo, cores e formas nas imagens ou acoplamento temporal, como quadros consecutivos semelhantes.

Problema

Seja os quadros originais, cada um com pixels. Seja a permutação aplicada aos pixels de cada quadro antes de obtê-los. Você pode pensar em como o livro de códigos do inimigo.$F_1,\dots,F_i$$n$$m$$P$$P$

Agora, como entrada, estamos recebendo . O objetivo é encontrar a permutação inversa para restaurar as imagens. Portanto, é o mapa de identidade e, por exemplo, . Observe que não conhecemos nenhum dos quadros corretos .$P(F_1),\dots,P(F_n)$$Q$$QP=I$$Q(P(F_1))=F_1$$F_i$

Seja Seja opossíveis funções de permutação dos pixels.$Q_1,...,Q_{m!}$$m!$$m$

O objetivo é selecionar o único Para que .$j\in\{1,\dots,m!\}$$Q_jP=I$

Nenhuma solução geral

Sob nosso modelo estatístico, isso significa selecionar o que maximiza a probabilidade de que seja extraído da mesma distribuição que as estatísticas de referência para imagens e as estatísticas temporais entre os quadros consecutivos e que é o nosso conhecimento prévio.$Q_j$$Q_j(P(F_i))$$Q_j(P(F_{i})$$Q_j(P(F_{i+1})$

Há um contra-exemplo canônico em que o inimigo mostra um filme embaralhado com dois quadros em que todos os pixels são da mesma cor, então , e para todo . Assim, para todos os , as estatísticas in-frame e inter-frame são equivalentes para cada e não nos fornecem informações para selecionar a permutação de probabilidade máxima (exceto no caso degenerado em que ).$n=2$$F_1=F_2$$Q_j(F_1)=Q_j(F_2)=F1=F2$$j$$j$$j$$Q_j$$m!=1$

Portanto, não podemos garantir exclusividade e o problema é insolúvel sem outras suposições.

Suposições adicionais

É interessante ver se podemos resolver o problema adicionando mais restrições.

Se restringirmos o inimigo a nos enviar apenas filmes "reais" e assumirmos que existem pixels e quadros diferentes suficientes para que um único com probabilidade máxima, ainda teremos que calcular estatísticas para permutado quadros para encontrar o máximo.$Q_j$$O(m! \times n)$

Isso é quebra de código de força bruta.

Para nos beneficiarmos das redes neurais e da propagação de retorno em particular, precisaríamos de uma função de perda diferenciável em relação à entrada (que é uma codificação de ou nossa permutação ). A questão, então, seria ver se essa função pode ser encontrada.$j$$Q_j$

Caso contrário, o problema é mais semelhante à análise criptográfica no caso especial em que sabemos que o livro de códigos do inimigo é uma permutação de texto não criptografado (ou imagem clara).