Il est possible d'optimiser MoreTV par Fantasio
Vous pouvez récuperer ce fichier ici: fantasio.zip
Pour contacter Fantasio, utilisez le
Forum84085 de Bravenet
Rappel :
======
L'algorithme d'encodage NagraVision utilise une table de permutations des lignes de
l'image recue pour fabriquer l'image en clair.
Il y a 2^15 permutations possibles soit 32768.
Chaque permutation donne pour chaque numero de ligne recue sa position dans l'image en
clair.
L'algorithme de MoreTV 2.83 : (sans tous les details)
=====================
Pour MoreTV Fast et pour le mode Turbo je ne sais pas parce qu'on n'a pas les sources!.
L'algorithme utilise par More TV (2.83) s'appuie sur un essai exhaustif des permutations
possibles pour choisir la "meilleure".
Pour juger si une permutation est meilleure qu'une autre, on prend l'image en clair qui
resulterait du decodage.
Le critere utilise pour determiner la meilleure permutation est le suivant
:
La meilleure permutation est celle qui produit l'image en clair la plus
"vraisemblable".
Dans une image reelle de la vraie vie vue a travers la petite lucarne, deux lignes
adjacentes se ressemblent beaucoup.
Pour juger de la vraisemblance d'une image, More TV calcule la somme de la valeur absolue
des differences entre les lignes en clair adjacentes produites.
Algorithme bestial :
Pour chaque permutation :
Produire l'image en clair.
Valeur = 0.
Pour chaque ligne J de l'image en clair {
Difference =0
Pour chaque pixel I de la ligne n {
Difference = Difference + ABS(valeur_du_pixel[I,J] -
valeur_du_pixel[I+1,J]
}
Valeur = valeur + difference
}
More TV prend enfin comme "bonne" permutation celle qui donne la valeur la plus
faible.
En realite, il y un certain nombre d'optimisations qui ont ete appliquees :
1- Au lieu de faire le calcul de difference sur toutes les lignes de l'image en clair, on
ne calcule que sur un sous ensemble de lignes bien choisi.
2 - Pour chaque ligne, le calcul de difference se fait seulement sur un nombre reduit de
pixels.
3 - au lieu de recalculer les differences entre deux lignes a chaque permutation, on
calcule une fois pour toutes les differences entre les couples de lignes possibles (a
chaque image quand meme) et on n'a plus qu'a faire la somme des differences pour les
couples de lignes concernes par une
permutation.
Choix des couples de lignes :
L'utilisateur indique un nombre N de "couples". En realite, MoreTV construit une
liste de couples de lignes a comparer en se debrouillant pour que pour chaque permutation,
il y ait exactement N comparaisons de lignes a faire. Cette liste est construite une fois
pour toutes (Indexation).
Caracterisation de l'algorithme :
=======================
La liste des couples fait N*32768 entrees de 2*8bits. Pour N=24 cela fait 1572864 octets,
a balayer a chaque demi image soit 50 fois par secondes soit 78 mega octets.
De plus, la facon dont la liste des couples est construite conduit a les disperser sur
l'ensemble de l'image cryptee.
La proposition du nouvel algorithme :
==========================
On peut utiliser un algorithme statistique qui conduit a :
1) utiliser moins de lignes de l'image recue (de preference dans la zone centrale).
2) mieux utiliser le cache memoire Mais qui necessite plus de memoire vive au total.
D'autre part, des simulations sur les images Canal Z de TU.CHEMNITZ.DE permettent de
penser qu'il est plus fiable que celui de More TV.
Description :
=========
Soit C l'image recue, et chaque ligne recue C(i) ou i est sa position. C(0) = premiere
ligne, C(1) deuxieme etc...du haut vers le bas de l'image.
Soit P l'image en clair a produire, comportant les lignes P(j), avec j de 0 a 287.
On recherche une permutation T(i) = j qui donne pour chaque ligne recue sa position dans
l'image finale.
L'idee est de choisir N lignes adjacentes parmi les C(i) dans la region centrale de
l'image cryptee.
Pour chacune de ces lignes :
1) on la compare a toutes les lignes C(i+Delta) avec delta allant de -D a +D. D etant un
entier arbitrairement choisi.
(En fait, on la compare au D lignes suivantes et au D lignes precedentes dans l'image
cryptee).
On choisit la ligne qui ressemble le plus parmi toutes celles la. Appelons la C(z).
On consulte alors la liste de toutes les permutations possibles, et on accorde un vote a
toutes les permutations pour lesquelles la ligne cryptee numero i et la ligne cryptee
numero z sont voisines dans l'image en clair (c'est a dire : T(z) = T(i)+1 ou T(z) =
T(i)-1).
On fait ceci pour chacune des N lignes.
2) Au final, on choisit comme permutation la plus probable celle qui obtient le plus grand
nombre de votes.
Commentaires :
============
La probabilite d'avoir la bonne cle augmente tres rapidement lorsqu'on augmente N ou D.
Sur l'une des images tests, N=4 et D=32 suffit pour obtenir la bonne cle.
En pratique, N=20 et D=10 devraient etre de bons choix. Cela conduit a moins de 200
comparaisons de lignes.
On peut encore optimiser l'algorithme pour l'adapter aux caracteristiques des tables de
permutation. Par exemple, les permutations generees par KEY2.txt comportent tres peu
de couples (I,I+2*X).
Bien entendu, toutes les optimisations de l'algorithme de MoreTV peuvent etre utilisees
(precalcul des comparaisons de lignes, precalcul des tables, sous echantillonage des
lignes dans les comparaisons...).
Les raisons pour lesquelles ca devrait etre plus rapide :
Les deux algorithmes ne permettent pas d'exploiter les caches memoire des cartes meres.
Dans ces conditions, celui qui parcourt le moins de memoire par image est le plus rapide.
1- Les lignes choisies par l'algorithme proposees sont toutes voisines, et chaque couple
n'est examine qu'une fois.
2- Lors du comptage des votes (c.a.d pour chaque couple(i,z) trouve incrementer le nombre
de votes des cles possibles), on parcourt seulement a peu pres 400Koctets de memoire (au
lieu de 1,5 mega pour MoreTV).
En revanche, la table des votes est tres grande et peut occuper jusqu'a 8 mega en memoire,
meme si pour chaque demi image on n'en utilise que 300K dans le pire des cas.
Divers : Suggestion a essayer pour enlever les lignes violettes
=============================================
Les lignes violettes sont dues au decodage du Secam. En fait, si on voit des lignes
violettes, c'est que le tuner marche bien!
Plutot que d'attenuer les couleurs, on pourrait lorsqu'on trouve une ligne violette,
simplement utiliser les couleurs de la ligne precedente dans l'image en clair, ou encore,
faire la moyenne des couleurs de la ligne precedente et de la ligne suivante.
Pseudo code pour la sortie des lignes vers l'ecran : Si (la ligne est violette) alors
transferer le canal Y (luminance) tel quel, transferer les canaux U et V de la ligne
precedente.
sinon transferer les canaux Y,U,V tels quels.
Fantasio
|
