Lien de la note Hackmd

Scalable video recording

Scalability referes to the capacity of recovering physically meaningful image or video information from deconding only partial compressed bitstreams

• Quality scalability:
  • finer to finer quantizations
• Spatial scalability:
  • different spatial resolutions (Laplacian, Pyramid, …)
• Temporal scalability:
  • we can jump frames and add the missing ones progressively
• Frequency scalability:
  • lower frequencies to higher frequencies
• Combination of basic schemes
• Granularity: coarse vs fine ones

Object-based scalability: different resolutions for different objects

2D motion vs optical flow

On a une sphere en train de tourner sans illumination: dans le flux video, il n'y a pas de difference.

Prenons ensuite une sphere dont la source lumineuse bouge: l'information visuelle changera.

The observed of apparent 2D motion is called optical flow

Optical flow equation and ambiguity in motion estimation

• Imaginons une sequence video
  $\psi (x,y,t)$
• On image un point
  $(x,y)$ deplace en
  $(x+d_x,y+d_y)$ au temps
  $t+d_t$

Under the constant intensity assumption, the images of the same object point at different times have the same luminance value

$$\psi (x+d_x,y+d_y,t+d_t)=\psi (x,y,t)$$

On fait un developpement de Taylor:

$$\psi (x+d_x,y+d_y,t+d_t)=\psi (x,y,t)+\frac{\partial \psi }{\partial x}{d}_x+\frac{\partial \psi }{\partial y}{d}_y+\frac{\partial \psi }{\partial t}{d}_t$$

On obtient:

$$\frac{\partial \psi }{\partial x}{d}_x+\frac{\partial \psi }{\partial y}{d}_y+\frac{\partial \psi }{\partial t}{d}_t=0$$

Definisson

$v_x=\frac{d_x}{d_t}$,

$v_y=\frac{d_y}{d_t}$,

$v_t=\frac{d_{x}t}{d_t}=1$

$$\frac{\partial \psi }{\partial x}{v}_x+\frac{\partial \psi }{\partial y}{v}_y+\frac{\partial \psi }{\partial t}=0$$

Qui peut etre ecrit:

$$\mathrm{\nabla }{\psi }^{T}v+\frac{\partial \psi }{\partial t}=0$$

Avec

${\psi }^T$ le gradient spatial

The flow vector

$v$ at any point

$x$ can be decomposed into 2 orthogonal components:

$$v=v_n{e}_n+v_t{e}_t$$

As we can observe, when a straight edge moves in the plane, we can only detect the normal

$v_n$ of its motion vector !

Because

$\mathrm{\nabla }\psi =\Vert \mathrm{\nabla }\psi \Vert e_n$ the optical flow equation can be rewritten as:

$$v_n\Vert \mathrm{\nabla }\psi \Vert +\frac{\partial \psi }{\partial t}=0$$

Avec

$\Vert \mathrm{\nabla }\psi \Vert$ la magnitude du vecteur gradient.

Les consequences de ces equations sont:

1. A chaque pixel
   $x$
2. We can compute

$$v_n=-\frac{\frac{\partial \psi }{\partial t}}{\Vert \mathrm{\nabla }\psi \Vert }$$

• This ambuigity in estimationg the motion vector is known as the aperture problem
• The motion can be estimated uniquely only if the aperture contains at least 2 different gradient directions

General methodologies

• We consider the ME between 2 given frames,
  $\psi (x,y,t_1)$ and
  $\psi (x,y,t_2)$

The problem is referred as to as forward motion estimation

Notation

Comment encoder les vecteurs de mouvements ?
Ils ne sont pas les memes en fonction de l'espace, il faut les encoder de facon parametrique.

Fonction mapping: nouvelle position

$$w(x,a)=x+d(x,a)$$

Avec le parametre

$a$ qui encode le mouvement, ca nous donne la nouvelle position.

$$a=[a_1,a_2,\dots ,a_n{]}^T$$

Motion representation

Different representations de mouvement.

Image b: pixel-based

• On a un vecteur pour chaque pixel de l'image

Image c: on va la faire en TP

• On suppose qu'on fait un decoupage par bloc
• On fait un vecteur de mouvement par bloc

Pour le champ de vecteur, comment est-ce qu'on parametrise ?

Translations
Polynomial motions
Rotations
…

On estime que l'image est faite de pixel et on fait de la pixel-wise

Ca fait 2 millions d'inconnues a trouver

On rajoute de la regularite.

En general, on decoupe en regions.

On estime d'abord le mouvement ou une region ?

Approche par blocs

On decompose l'image en blocs (ex: pour une image

$100\times 100$, en

$33\times 33$)

On a des blocs qui vont se superposer car le mouvement n'est pas uniforme

Et on s'en fout !

On a egalement des coins qui ont bouges.

Il faut faire de la descente de gradient

• Les version les plus simples qu'on peut imaginer c'est en terme de translation
• Les blocs sont un bon compromis entre la precision et la complexite

It can induce warping effects

Motion esimation criteria

Displaced Frame Difference (DFD):

$$E_{DFD}(a)=\sum _{x\in \mathrm{\Lambda }}|{\psi }_2(w(x,a))-{\psi }_1(x){|}^p$$

where

$\mathrm{\Lambda }$ is the domain of all pixels in

${\psi }_1$ and

$p$ a positive number

• When
  $p=1$, the above error is called mean absolute difference (MAD) and when
  $p=2$ Mean Squared Error (MSE)
• The error image
  $e(x,a)={\psi }_2(w(x,a))-{\psi }_1(x)$ is usually called displaced frame difference (DFD) image
• When
  $a$ is optimal (
  $p=2$)

$$\frac{\partial E_{DFD}}{\partial a}=2\sum _{x\in \mathrm{\Lambda }}({\psi }_2(w(x,a))-{\psi }_1(x))\frac{d(w(x,a))}{da}\mathrm{\nabla }{\psi }_2(w(x,a))=0$$

Prenons un cas plus simple

$$\frac{\partial \psi }{\partial t}{d}_t={\psi }_2(x)-{\psi }_1(x)$$

It is equivalent to minimize:

$$E_{flow}=\sum _{x\in \mathrm{\Lambda }}|\mathrm{\nabla }{\psi }_1(x{)}^{T}d(x,a)+{\psi }_2(x)-{\psi }_1(x){|}^p$$

This solution verifies when

$p=2$

$$\frac{\partial E_{flow}}{\partial a}=2\sum _{x\in \mathrm{\Lambda }}(\mathrm{\nabla }{\psi }_1(x{)}^{T}d(x,a)+{\psi }_2(x)-{\psi }_1(x))\frac{\partial d(x,a)}{da}\mathrm{\nabla }{\psi }_i(x)$$

We can add a penalty term in our equation to enforce the smoothness of our vector field (i.e. must vary smoothly)

$$E_s=\sum _{x\in \mathrm{\Lambda }}\sum _{y\in N_x}\Vert d(x,a)-d(y,a){\Vert }^2$$

We want to minimize:

$$E_{total}=E_{DFD}+w_s{E}_s$$

with

$w$ the weighting coefficient.

• We have to regularize but not too much (to avoid over-blurring)

Minimzation methods

On va surtout regarder la methode exhaustive

• La methode de gradient
• La methode de Newton-Raphson

Avec la descente de gradient et le probleme de dimensionnalite, on tombe souvent sur des minimums locaux et non globaux

• One important search strategy is to use a multi-resolution representation of the motion field and conduct the search in a hierarchical manner
• The basic idea is to first search the motion parameters in a coarse resolution, propagate this solution into a finer resolution, and then refine the solution in the finer resolution
• It can combat the slowness of exhaustive search methods

Regularization

$$E=\sum _{x\in \mathrm{\Lambda }}(\frac{\partial \psi }{\partial x}{v}_x+\frac{\partial \psi }{\partial y}+\frac{\partial \psi }{\partial t}{)}^2+w_s(\Vert \mathrm{\nabla }{v}_x{\Vert }^2+\Vert \mathrm{\nabla }{v}_y{\Vert }^2)$$

Block matching algorithm (BMA)

• Les blocs peuvent etre de forme polygonale
  • On prend en pratique des carres
• On suppose qu'on fait de la translation

The Exhaustive Search Block Matching Algorithm (EBMA)

Under the block-wise translation model

$$w(x;a)=x+d_{m}x\in B_m$$

Then the error can be written:

$$E(d_m,\mathrm{\forall }m\in \mathcal{M})=\sum _{m\in \mathcal{M}}\sum _{x\in B_m}|{\psi }_2(x+d_m)-{\psi }_1(x){|}^p$$

We can estimate the MV for each block individually

$$E_m(d_m)=\sum _{x\in B_m}|{\psi }_2(x+d_m)-{\psi }_1(x){|}^p$$

Deformable block matching algorithm

$$d_m(x)=\sum _{k=1}^K{\mathrm{\Phi }}_{m,k}(x)d_{m,k}x\in B_m$$

Le deplacement au bloc

$m$ de

$x$ est une somme ponderee des deplacements en 4 coins

Node-based motion representation

• Nodal MVs vs Polynomial coefficients
  • Nodal
    • Stabilite

Motion estimation using node-based model

$$a=[d_k;k\in \mathcal{K}]$$

$$E(a)=\sum _{x\in B}({\psi }_2(w(x,a))-{\psi }_1(x){)}^2$$

where:

$$w(x,a)=x+\sum _{k\in \mathcal{K}}{\varphi }_k(x)d_k$$

Mesh-based motion estimation

• Dans le cas des blocs: estime independants et deformes
• Mesh: maillage sur l'image et on se permet de les deplacer en meme temps
  • Tout est corrole

Contrainte a connaitre: on ne veut pas que nos 2 carres s'inversent

• On a souvent des discontinuetes au niveau des edges
• Plus on augmente le nombre de noeuds, plus on a une estimation precise
  • Mais la puissance de calcul explose

Global motion estimation

Plusieurs methodes existent

Est-ce qu'on est dans le cadre ou pas d'avoir uniquement la camera qui bouge ?

Au foot et tennis, une grande partie du decor est stable

Region-based motion estimation

Est-ce qu'on separe en region ou on estime le mouvement ?

3 approches possibles

Multi-resolution motion estimation

• Various ME approaches can be reduced to solving an error minimization problem
• Major difficulties
  • Many local minima in the gradient-descent case
  • Not easy to reach the global minimum
  • Computation high

Pyramide laplacienne: on decompose l'image en bandes de frequence