Tiens, un extrait du fichier README PcTV v0.94
C'est assez vieux (ça date de 97) mais ça explique bien l'algo (je pense pas que ça ai changé, il doit juste y avoir quelques trucs périmés mais bon ...)
D'abord un peu d'historique, puis la theorie :
-----------------------------------------------------------------Qu'est ce que PcTV :
-----------------------------------------------------------------Ce projet etait au depart (et il l'est toujours !) un soft de television de type 100hz sous DOS en plein ecran qui remplacerait l'execrable soft fourni sous Windows 95 avec la carte Miro PCTV. En effet, sous Windows 95, l'image est floue et moche parce que le soft filtre trop l'image et gere mal l'entrelacement des trames paires et impaires. C'est dommage, car le chip BT848 est un excellent composant, tres parametrable, mais pas vraiment facile d'acces pour un programmeur.
Comme je suis un peu curieux, je me suis amuse a implementer un algorithme qui effectue une fonction inverse de cryptage (a double cle) concernant un procede d'emission video, et qui etait decrite sur une page web quelque part sur Internet, et en partant d'un algorithme existant deja (je remercie au passage la personne qui me l'a donne, et qui se reconnaitra). Ce procede utilise une cle fixe et une cle variable :
- PcTV a besoin de la cle fixe, qui doit lui etre fournie sous la forme d'un fichier texte appele "key.txt" dans le repertoire de PcTV. Il s'agit tout simplement d'un fichier texte contenant 256 lignes, chaque ligne comportant un nombre compris entre 0 et 31. Libre a vous d'utiliser les valeurs que vous voulez du moment que ces valeurs ne correspondent pas a des valeurs utilisees pour la diffusion de chaines de television a peage. Ne me demandez pas de tels fichiers, je ne sais pas si ils existent, je n'en possede pas, et au cas ou vous en trouveriez je ne suis pas interesse et je ne pourrais que formuler l'avertissement suivant : ce logiciel ne doit pas etre utilise pour regarder des chaines de television pour lesquelles un abonnement est necessaire dans votre pays, a moins (peut-etre) que vous ne possediez deja un tel abonnement et que vous utilisez ce logiciel uniquement dans un but educatif
- pour ce qui est de la cle variable, PcTV se charge de la retrouver tout seul comme un grand.
......
-----------------------------------------------------------------Un peu de theorie :
-----------------------------------------------------------------La cle variable possede 32768 combinaisons, et le travail de l'algorithme consiste a retrouver le plus vite possible la bonne. L'algorithme repose sur le principe suivant : "si deux lignes eloignees l'une de l'autre sur l'image initiale se retrouvent cote a cote en appliquant une certaine cle variable, alors il y a des chances que cette cle soit la bonne". Bien entendu, deux lignes ne suffisent pas pour certifier qu'une cle variable est la bonne. Par la suite, j'appelerai ces couples de lignes des "candidates".
Mais comment savoir si deux lignes sont cote a cote ? En calculant par exemple leur "taux de correlation" : si la somme des valeurs absolues de la difference de luminance de chaque pixel des deux lignes est "petite" alors il y a des chances que ces lignes soient proches. Le succes de cette methode depend du fait que la plupart des lignes de l'image soient relativement differentes. C'est en general le cas en video, sauf lorsque l'image est tres uniforme (par exemple un fond de couleur), ou lorsqu'il y a des symetries verticales (une figure geometrique de couleur uniforme et a bords verticaux).
En gros, on peut considerer que plus l'image est "diversifiee", mieux ca marche.
Pour valider une cle variable, il faut donc :
- selectionner un certain nombre de "candidates" pour un code donne. Cette notion s'appelle la "taille de bloc". Plus la taille de bloc est petite, plus l'algorithme est rapide, mais moins il est fiable. Une taille de bloc de 10 correspond a 10 lignes candidates par code variable
- retenir la cle variable qui obtient le meilleur score de correlation pour tous ses "candidates" (il suffit de sommer les taux de correlations individuels).
Bien entendu, le nombre total de "candidates" necessaire est tres superieur a la "taille de bloc", et plus le nombre de "candidates" est grand, plus l'algorithme est lent, mais il est aussi plus fiable. Il existe des moyens de regler le ratio "nombre de candidates" / "taile de bloc" (voir les options de la ligne de commande). D'autre part, le nombre de pixels pour calculer les taux de correlation est inferieur au nombre de pixels par ligne (option - step). Bien sur, plus on prend de pixels, plus c'est fiable, mais moins ca va vite.
Tous ces parametres influent donc enormement sur la vitesse de l'algorithme.
Pour donner un ordre d'idee, avec une taille de bloc de 12, 800 candidates, et 4 pixels sur 16 (pctv -step 3), il faut pour chaque image :
- calculer 800 taux de correlation (soit 800*2*(768*4/16)=307200 pixels a traiter)
- scorer 32768*12=393216 possibilites.
Multipliez ca par 25 et ce donne une idee des traitements necessaires pour traiter une seconde de video en temps reel.
A cela s'ajoute (en 16 bits couleurs) :
- 440k*25 = 11M transferes du bus PCI vers la memoire par la carte BT848
- 11M transferes depuis la memoire vers la carte video.
Ca nous fait 22M/s soit 2/3 de la bande passante du bus PCI (deux fois moins en 8 bits). L'utilisation d'un bus AGP doit diviser par deux l'occupation du bus PCI. L'occupation du bus a un impact non negligeable sur les performances de l'algorithme, c'est ce qui explique en partie la perte de framerate entre les versions 8, 16 et 32 bits.
....
. Et puis y'a "Austin Powers" qu'avait écrit des truc sympa aussi 
.
D
