← Computação

Simulador de estimativa de movimento

Simule a estimativa de movimento entre quadros, a correspondência de blocos, os padrões de busca e os resíduos de compressão.

A carregar a simulação interativa...

A busca rápida nunca olha a maior parte da janela

A estimativa de movimento é o gargalo da compressão de vídeo. Um macrobloco de tamanho 16x16 é comparado ao quadro de referência dentro de uma janela de busca para encontrar o candidato com a menor soma das diferenças absolutas (SAD). A busca completa exaustiva avalia todas as (2r+1)² posições, o que é lento. Algoritmos rápidos como a busca em diamante e hexagonal avaliam apenas uma fração dos pontos, deslocando o centro de busca de forma iterativa e parando quando o mínimo está no centro do padrão. Passe o mouse sobre qualquer bloco para ver sua janela de busca e as avaliações de candidatos em tempo real.

Por que enviar movimento, não pixels

Quadros de vídeo consecutivos são quase idênticos, então, em vez de guardar cada quadro por inteiro, um codec descreve o quadro atual como pedaços do anterior que se deslocaram. Cada bloco de 16×16 recebe um vetor de movimento apontando para sua melhor correspondência, mais um pequeno resíduo com aquilo que o deslocamento não conseguiu explicar. A lição: panorâmicas suaves de câmera comprimem lindamente, pois um único vetor substitui milhares de pixels.

Vetores de movimento não são movimento real

O codificador nunca pergunta o que de fato se moveu: ele apenas caça o bloco de menor SAD. Por isso, em regiões planas ou ruidosas, o vetor vencedor pode apontar para um lugar absurdo, nada parecido com o deslocamento verdadeiro. Aumente o controle de ruído e veja o campo de vetores se espalhar em puro caos. É por isso que vetores de movimento servem mal como fluxo óptico, mas perfeitamente para compressão: eles obedecem à taxa de bits, não à física.

UMA ETAPA DE UMA CADEIA — O QUE ENTRA, O QUE SAI E O QUE QUEBRA DEPOIS

Onde isto fica no pipeline de codificação

Um codificador de vídeo não é um algoritmo, mas oito etapas numa ordem fixa, e a ordem não é arbitrária: cada etapa existe porque a anterior tornou o seu trabalho possível. Esta ferramenta modela uma delas. A cadeia abaixo liga às outras sete.

Simulador de estimativa de movimento — descobre para onde cada bloco se moveu e codifica a diferença em vez do bloco

O que entra
Um quadro P ou B junto com os seus quadros de referência.
O que sai
Um vetor de movimento por bloco e um resíduo — exatamente aquilo que a predição errou.
O que a etapa seguinte pressupõe
A quantização recebe um resíduo, não uma imagem. Resíduos ficam perto de zero em quase todo lugar, e é justamente por isso que quantizá-los sai barato.
O que dá errado aqui
Uma correspondência ruim não produz uma imagem errada, produz uma imagem cara. O resíduo carrega mais energia, e o mesmo ajuste de quantizador emite então mais bits. Esta etapa muda o tamanho da saída, não os seus ajustes.
Etapa anterior: Estrutura GOP Etapa seguinte: Quantização

Problema resolvido na íntegra

  1. A janela de pesquisa derivada de 225 posições por bloco 5 passos

    Uma pesquisa de movimento completa testa 225 posições por bloco, 14 400 no total. Determine a janela de pesquisa a partir daí e o que se ganha com uma pesquisa rápida.

    1. 225 é um quadrado perfeito, e essa é a pista: a pesquisa é uma janela quadrada de 15 por 15 deslocamentos candidatos, o que significa de −7 a +7 píxeis em cada direção.

      full search over ±7 px in each axis: 15×15=225 positions per block\text{full search over}\ \pm7\ \text{px in each axis}:\ 15\times15=225\ \text{positions per block}

    2. Dividir o total pela contagem por bloco dá o número de blocos em que o fotograma foi dividido.

      14 400225=64 blocks\frac{14\,400}{225}=64\ \text{blocks}

    3. O custo cresce com o quadrado do raio de pesquisa, pelo que alargar a janela torna-se rapidamente dispendioso: um raio de 7 custa 225 posições, um raio de 15 custa 961, um raio de 31 custa 3969.

      cost∝(2R+1)2: R=7⇒225,R=15⇒961,R=31⇒3969\text{cost}\propto(2R+1)^2:\ R=7\Rightarrow225,\quad R=15\Rightarrow961,\quad R=31\Rightarrow3969

    4. Essa relação quadrática é a razão pela qual existem pesquisas rápidas. Uma pesquisa em três passos amostra nove pontos, refina e repete — 27 posições em vez de 225.

      three-step search: 3 stages×9 points=27\text{three-step search}:\ 3\ \text{stages}\times9\ \text{points}=27

    5. Oito vezes mais económica, e não equivalente: desce em direção a um mínimo local e pode ignorar a melhor correspondência real se a superfície de erro tiver mais do que uma depressão.

      22527=8.3× fewer, and it can miss the true minimum\frac{225}{27}=8.3\times\ \text{fewer, and it can miss the true minimum}

    Resposta

    A ferramenta indica 14400 pontos pesquisados, à razão de 225,0 por bloco. Aqui está todo o dilema prático da codificação de vídeo: a busca exaustiva é ótima, mas o seu custo cresce com o quadrado do raio. Por isso, todos os codificadores recorrem a uma heurística e aceitam que, por vezes, será escolhido um vetor pior. Parte do preço do erro vê-se na linha Energia residual (EQM): um vetor inadequado deixa um resíduo maior, o que exige mais dados para a codificação. A busca rápida de movimento não é uma mera aproximação destinada a poupar tempo; é uma aposta em que os bits perdidos com vetores imperfeitos serão menos úteis do que se forem aplicados noutro ponto.

    full search is O(R2) per block; fast searches trade optimality for 8×\text{full search is}\ O(R^2)\ \text{per block};\ \text{fast searches trade optimality for}\ 8\times
Referências (2)

· Verificado com fontes publicadas. Correções bem-vindas.