TD SystemVerilog : filtre médian

Un fitre médian

 

Le filtre médian est utilisé en traitement d'images pour "nettoyer" les images en éliminant certains défauts parasites. L'algorithme du filtrage médian est très simple : chaque pixel de l'image à filtrer est remplacé par la valeur médiane des pixels voisins. L'image est ainsi transformée par le filtre médian en une autre image de même taille. Pour chaque pixel P de l'image d'origine on crée une liste des pixels situés dans un voisinage 3x3 autour de P. Les 9 pixels de la liste sont ensuite triés dans l'ordre de leurs valeurs numériques. La valeur médiane est celle du pixel situé au milieu de la liste triée. Le pixel P de l'image filtrée prend alors pour valeur la valeur médiane. Dans notre cas nous supposerons que les images sont représentées en 256 niveaux de gris. Les valeurs des pixels sont donc comprises entre 0 (noir) et 255 (blanc).

Considérons la situation représentée par la figure ci-dessous :

 

Notons [X,Y] le pixel situé à l'intersection de la ligne X et de la colonne Y d'une image.

La valeur du pixel [4,5] de l'image filtrée est déterminée en considérant le voisinage 3x3 du pixel [4,5] de l'image source, soit la liste de pixels {[3,4],[3,5],[3,6],[4,4],[4,5],[4,6],[5,4],[5,5],[5,6]}.

La liste des valeurs de ces 9 pixels est, dans notre exemple, {122,94,247,78,34,45,207,103,18}. La liste ordonnée de ces mêmes valeurs devient {18,34,45,78,94,103,122,207,247}. La valeur médianne de la liste est 94 et le pixel de l'image filtrée prendra donc la valeur 94.

Nous allons concevoir, simuler et synthétiser un module capable d'extraire la valeur médiane d'une liste de 9 pixels.

L'algorithme de tri:

Pour notre opérateur nous avons besoin d'implémenter matériellement un algorithme de tri.
On vous propose d'implémenter un simple algorithme de tri avec un nombre d’itérations constant.

for pos in 0 ... PixNum-2
begin
  for pix_idx in pos+1 ... PixNum-1
  begin
    if (V[pos] < V[pix_idx])  Exchange(V[pos],V[pix_idx])
  end
  med = V[PixNum/2]
end

À chaque itération le maximum des valeurs non triées est placé à la position "pos".
À la fin la valeur médiane se trouve à la position dont l'indice est médian (PixNum/2) (5e position (pos=4) pour 9 pixels).
On peut arrêter l'algorithme à cette étape

Comme nous n'avons besoin que de la valeur médiane, nous pouvons diviser par 2 le nombre d'étapes.
Et comme nous n'avons pas besoin des valeurs supérieures au médian, l'algorithme peut être adapté comme suit:

for iter in 0 ... PixNum/2
begin
  for pix_idx in 1 ... PixNum-iter-1
  begin
    if (V[0] < V[pix_idx])  Exchange(V[0],V[pix_idx])
  end
  med = V[0]
 // On écrase V[0] en décalant les pixels
  V[0:PixNum-1] = {V[1:PixNum-1],0}
end

À la fin de chaque cycle de comparaison, on écrase la maximum contenu dans V[0] et on décale toutes les valeurs pour que la comparaison se fasse toujours avec l'élément en position 0.

Cet algorithme n'est pas forcement le plus efficace pour une implémentation logicielle mais il a deux avantages pour une implémentation matérielle:
 le nombre d'étapes est constant
 les opérations effectuées à chaque cycle sont simple et identiques


Pour implémenter matériellement cet algorithme nous allons passer par les étapes suivantes:

  1. Construire l'opérateur de comparaison et d'échange (MCE) utilisé à chaque étape
  2. Décrire le chemin de données et la façon avec laquelle les pixels sont mémorisés
  3. Décrire le séquenceur (machine à états finis)

 

0. Préparation des répertoires de travail

Les outils utilisés générant de nombreux fichiers, il est fortement conseillé de structurer vos répertoires de travail de la façon suivante:

  • Créez un répertoire "median".
  • Dans ce répertoire créer un sous-répertoire "src". C'est dans ce répertoire que vous créerez vos fichiers source. Vous leur donnerez l'extension ".sv".
  • Créer un deuxième sous-répertoire : "simulation" qui servira pour l'outil de simulation "Modelsim"
  • Créer enfin un troisième sous-répertoire : "synthese" qui servira pour l'outil de synthèse "Precision"

IMPORTANT:

  • Respectez les noms des modules tels qu'indiqués dans le texte (en respectant la casse (majuscule/minuscule)) .
  • Chaque module doit être dans un fichier de même nom.
  • Ne pas ajouter de modules en dehors de ceux indiqués dans le texte.

1. Préparation de l'environnement de simulation

L'outil de simulation organise les modules compilés dans une bibliothèque. Par défaut la bibliothèque de travail s'appelle "work". Avant de pouvoir compiler vos fichiers vous devez créer cette bibliothèque. Pour ce fait, dans le répertoire "simulation" exécuter la commande suivante:

vlib work

Un répertoire "work" est créé qui contiendra le résultat des compilations que vous ferez.

Pour compiler un fichier SystemVerilog, vous devez être dans le répertoire qui contient la bibliothèque "work" (c'est à dire le répertoire "simulation"). La compilation se fait en utilisant la commande "vlog" comme suit:

vlog +acc ../src/VOTRE_FICHIER.sv

L'option "+acc" rend visible tous les objets internes de vos modules au moment de la simulation et évite qu'il ne disparaissent du fait des optimisation de l'outil.

Pour lancer le simulateur, exécuter la commande "vsim".

Juste vérifier la syntaxe....

Si vous voulez juste vérifier la syntaxe, sans lancer le simulateur, vous pouvez utiliser l'outil verilator. C'est un outil open source qui permet, entre autre de vérifier la syntaxe. Il suffit pour cela de lancer la commande suivante:

verilator --lint-only <VOS FICHIERS À TESTER>
Il est généralement disponible dans les paquets standards des distributions Linux et on peut même l'interfacer avec son éditeur de texte favori (vim, emacs ou atom) pour vérifier la syntaxe durant la frappe.

2. Le module de comparaison et d'échange

Nous allons commencer par concevoir un module de comparaison et d'échange (MCE) dont l'interface est la suivante :

 

NOM Type Direction Description
A Bus 8bits Entrée Un pixel
B Bus 8bits Entrée Un pixel
MAX Bus 8bits Sortie Le plus grand des deux pixels A et B
MIN Bus 8bits Sortie Le plus petit des deux pixels A et B

 

Le module MCE est entièrement combinatoire. Il compare les deux pixels d'entrée A et B puis dépose le plus grand sur sa sortie MAX et le plus petit sur sa sortie MIN.

2.1 Ecriture du code SystemVerilog

Concevez le module MCE en respectant les règles suivantes:

  • N'utiliser que des affectations concurrentes de type "assign" (pas de blocs "always" ou "initial").
  • Réaliser un module dont la taille des données est paramétrable avec une taille par défaut de 8 bits.

Sauvez votre fichier, compilez-le et corrigez les erreurs éventuelles.

2.2 Simulation de MCE

Créez un environnement de simulation pour le module MCE (un testbench). Votre environnement devra présenter 1000 couples de valeurs aléatoires en entrée du module MCE. Après avoir présenté chaque couple de valeur il devra laisser s'écouler une unité de temps et vérifier automatiquement que les sorties de MCE sont bien les sorties attendues.

Pour générer les entrées vous aurez besoin de la tâche système "$random". Pour vérifier automatiquement les sorties de MCE vous décrirez l'algorithme de comparaison et d'échange d'une façon différente de celle que vous avez utilisée pour MCE.

La simulation devra s'arrêter automatiquement (tâche système "$stop") lorsque le comportement de MCE n'est pas le comportement attendu. Dans ce cas l'environnement devra afficher un message d'erreur indiquant les valeurs attendues et les valeurs observées (tâche système "$display").

La simulation devra également s'arrêter automatiquement lorsque les 1000 couples de valeurs aléatoires auront été présentés et les sorties de MCE vérifiées (tâche système "$finish").

Sauvez votre fichier, compilez-le et corrigez les erreurs éventuelles.

Attention, pour gagner du temps vous pouvez utiliser l'environnement de simulation que nous avons préparé pour vous en l'adaptant à vos besoins. Si vous choisissez cette option essayez néanmoins de bien comprendre la solution qui vous est proposée.

Lancer l'outil de simulation en executant la commande suivante dans le répertoire "simulation"

vsim NOM_DU_MODULE_TESTBENCH

La fenêtre du simulateur devrait apparaitre.

Lancez la simulation en utilisant utilisant les boutons de contrôle de la simulation ou en entrant dans la console la commande "run"

run # execute un cycle de simulation
run 20us # executer pour une durée de 20us
run -all # executer jusqu'à la fin

Modifiez votre code pour corriger les erreurs éventuelles à l'exécution.

Pour recompiler, vous pouvez retapper la commande "vlog" dans la console ou dans l'onglet "Library" du "Workspace", dans la bibliothèque "work" selectionner votre module, après une clic droit, un sous-menu apparaît, lancez la commande recompile.

Pour ajouter des signaux dans la fenêtre des chronogrammes, sélectionnez l'instance à laquelle ils appartiennent dans l'onglet "Sim" du Workspace, les signaux apparaitront dans la fenêtre "Objects" puis glissez/déposez les dans la fenêtre "Wave".

2.3 Synthèse et optimisation de MCE

  • Sauvegardez les fichiers nécessaires à la synthèse dans le répertoire "median/synthese"
  • Placez vous dans le répertoire ".../median/synthese" et modifiez les variables TOP_MODULE et SOURCE_FILES du fichier Makefile pour l'adapter a votre configuration. Dans notre cas, TOP_MODULE=MCE et SOURCE_FILES=MCE.sv (attention, ne pas laisser d'espace à la fin).
  • Exécutez la synthèse avec la commande make.
  • Observez les éventuels messages d'erreur et corrigez votre code en conséquence.
  • Dans l'onglet "Design Analysis" l'élément "Report Area" contient des informations sur la complexité du résultat de la synthèse. Pour les FPGA de type Altera, cette complexité est estimée en nombre de cellules logiques (LUTs), bascule D (Registers) et mémoire (Memory Bits). Votre unité de comparaison et d'échange ne devrait par comporter plus de 24 cellules logiques. Si tel n'est pas le cas, votre code est sous-optimal. Modifiez votre code pour remédier à ce problème.
  • Les résultats de synthèse sont stockés dans le sous répertoire MCE du répertoire médian/synthèse. Vous pouvez nettoyer votre répertoire synthèse avec Make clean
  • A chaque modification de votre code vous devrez simuler à nouveau MCE pour vérifier que la fonctionnalité est préservée.

3. L'opérateur de tri médian

Pour extraire la valeur médiane de 9 pixels nous allons concevoir un opérateur séquentiel utilisant un module MCE (et un seul). Son interface est la suivante :

 

Nom Type Direction Description
DI Bus 8 bits Entrée Le bus par lequel arrivent les pixels
DSI Signal 1 bit Entrée Indique qu'un pixel est présent sur l'entrée DI. Actif à 1
BYP Signal 1 bit Entrée Un signal de commande qui modifie le comportement de l'opérateur (voir plus loin)
CLK Signal 1 bit Entrée L'horloge. MED est un opérateur synchrone sur front montant de CLK
DO Bus 8 bits Sortie Lorsque MED a terminé son tri ce bus présente la valeur médiane des 9 pixels

Les communications entre MED et le monde extérieur sont de la forme suivante :

Le monde extérieur présente 9 pixels à MED (P0, P1, ..., P8), un pixel par période d'horloge. Pendant les 9 périodes d'horloges le signal DSI est maintenu à 1. Les 9 périodes d'horloge sont nécessairement consécutives.

Après avoir reçu le dernier des 9 pixels MED extrait la valeur médiane et la présente sur le bus DO. Ce calcul prend plusieurs périodes d'horloge. Lorsque MED a terminé son calcul et présenté la valeur médiane sur le bus DO le monde extérieur peut présenter une nouvelle série de 9 pixels.

On supposera dans toute la suite que le monde extérieur respecte ce protocole et attend réellement la fin du calcul en cours avant de présenter une nouvelle série.

L'architecture de MED est la suivante :

Les objets nommés MUX sont des multiplexeurs de 2 mots de 8 bits vers un mot de 8 bits. Les objets nommés R0, R1, ..., R8 sont des registres 8 bits. Etudiez cette architecture et réfléchissez à la façon dont le monde extérieur, en pilotant correctement les entrées DI, DSI et BYP peut obtenir la valeur médiane de 9 pixels.

3.1 Ecriture du code SystemVerilog

Concevez le module MED en respectant les règles suivantes:

  • La largeur des données traitées doit être paramétrable (8 par défaut)
  • Le nombre de donnée traitées doit être paramètrable (9 par défaut)

Sauvez votre fichier, compilez-le et corrigez les erreurs éventuelles.

3.2 Simulation de MED

Créez un environnement de simulation pour le module MED en vous inspirant de l'environnement de simulation de MCE.

Sauvez votre fichier, compilez-le et corrigez les erreurs éventuelles. Lancez la simulation et modifiez votre code pour corriger les erreurs éventuelles à l'exécution.

Attention, pour gagner du temps vous pouvez utiliser l'environnement de simulation que nous avons préparé pour vous en l'adaptant à vos besoins. Si vous choisissez cette option essayez néanmoins de bien comprendre la solution qui vous est proposée.

3.3 Synthèse et optimisation de MED

 

  • Placez vous dans le répertoire "median/synthese" et modifiez les variables TOP_MODULE et SOURCE_FILES du fichier Makefile pour l'adapter a la nouvelle configuration. Dans notre cas, TOP_MODULE=MED et SOURCE_FILES = MCE.sv MED.sv (l'ordre n'est pas important)
  • Lancez la synthèse avec la commande make. Les résultats de compilation sont stockés dans le sous répertoire MED du répertoire median/synthèse. Vous pouvez nettoyer votre répertoire synthèse avec Make clean
  • Observez les éventuels messages d'erreur et corrigez votre code en conséquence.
  • A chaque modification de votre code vous devrez simuler à nouveau MED pour vérifier que la fonctionnalité est préservée.
  • Analyser la complexité obtenue après synthèse. Déterminez notamment le nombre de bascules D générées (Registers), et vérifiez la cohérence du résultat avec ce que vous imaginez obtenir. Si tel n'est pas le cas, votre code doit être sous_optimal, voir erroné.
  • Dans l'onglet "Design Analysis" l'élément "Report Timing" contient des informations sur la fréquence de fonctionnement maximale de l'ensemble ainsi que le chemin critique.

4. L'opérateur complet

L'opérateur complet est composé de MED et d'une structure de contrôle. Son interface est la suivante :

 

Nom Type Direction Description
DI Bus 8 bits Entrée Le bus par lequel arrivent les pixels
DSI Signal 1 bit Entrée Indique qu'un pixel est présent sur l'entrée DI. Actif à 1
nRST Signal 1 bit Entrée Signal de réinitialisation asynchrone. Actif à 0
CLK Signal 1 bit Entrée L'horloge. MEDIAN est un opérateur synchrone sur front montant de CLK
DO Bus 8 bits Sortie Lorsque MEDIAN a terminé son tri ce bus présente la valeur médiane des 9 pixels
DSO Signal 1 bit Sortie Indique que MEDIAN présente la valeur médiane sur DO. Actif à 1

4.1 Ecriture du code SystemVerilog

Concevez le module MEDIAN.

Vous utiliserez une instance du module MED à laquelle vous ajouterez les processus nécessaires à la génération des signaux BYP et DSO. Sauvez votre fichier, compilez-le et corrigez les erreurs éventuelles.

Voici une suggestion d'algorithme pour déterminer la valeur médiane (vous pouvez utiliser votre propre algorithme original, ou tenter de l'étendre à une version générique...). 

Durant le tri (soit après la fin du chargement des registres), le signal BYP doit prendre les états suivants:

  • Etape 1 :
    • 8 periodes a 0 : le max des 9 données est dans le registre R8 de MED
    • 1 periode a 1  :  le max  est écrasé , les registres R1 à R8 contiennent les 8 données restantes, R0 ne contient plus de donnée utile.
  • Etape 2 :
    • 7 periodes a 0 : le max des 8 données restantes est dans dans le registre R8 de MED
    • 2 periodes a 1 : le max  est écrasé , les registres R2 à R8 contiennent les 7 données restantes, R0 et R1  ne contiennent plus de données utiles.
  • Etape 3 :
    • 6 periodes a 0 : le max des 7 données restantes est dans dans le registre R8 de MED
    • 3 periode a 1  : le max  est écrasé , les registres R3 à R8 contiennent les 6 données restantes, R0,R1 et R2 ne contiennent plus de données utiles.
  • Etape 4:
    • 5 periodes a 0 : le max des 6 données restantes est dans dans le registre R8 de MED
    • 4 periode a 1  : le max  est écrasé , les registres R4 à R8 contiennent les 5 données restantes, R0,R1,R2 et R3 ne contiennent plus de données utiles.
  • Etape 5:
    • 4 periodes a 0 : le max des 6 données restantes est dans dans le registre R8 de MED : c'est le MEDIAN...
       
  • Concevez le module MEDIAN qui instancie module MED ainsi que la logique séquentielle de contrôle (machine à état, compteurs...).
  • Le nombre de données tratées ne sera pas paramétrable (9).

4.2 Simulation de MEDIAN

Créez un environnement de simulation pour le module MEDIAN en vous inspirant de l'environnement de simulation de MED.

Sauvez votre fichier, compilez-le et corrigez les erreurs éventuelles. Lancez la simulation et modifiez votre code pour corriger les erreurs éventuelles à l'exécution.

Attention, pour gagner du temps vous pouvez utiliser l'environnement de simulation que nous avons préparé pour vous en l'adaptant à vos besoins. Si vous choisissez cette option essayez néanmoins de bien comprendre la solution qui vous est proposée.

4.3 Synthèse et optimisation de MEDIAN

  • Placez vous dans le répertoire "median/synthese" et modifiez les variables TOP_MODULE et SOURCE_FILES du fichier Makefile pour l'adapter a la nouvelle configuration. Dans notre cas, TOP_MODULE=MEDIAN et SOURCE_FILES = MCE.sv MED.sv MEDIAN.sv
  • Lancez la synthèse avec la commande make. Les résultats de compilation sont stockés dans le sous répertoire MEDIAN du répertoire médian/synthèse. Vous pouvez nettoyer votre répertoire synthèse avec Make clean
  • Observez les éventuels messages d'erreur et corrigez votre code en conséquence.
  • A chaque modification de votre code vous devrez simuler à nouveau MEDIAN pour vérifier que la fonctionnalité est préservée.
  • Analyser la complexité obtenue après synthèse ainsi que la fréquence maximum atteinte et vérifiez le respect des contraintes temporelles.

4.4 Simulation de MEDIAN après synthèse

  • Lancez le placement/routage:
    • Dans l'onglet "Quartus II Modular"  de Precision appuyez sur "Run Quartus II"
  • Recopiez les fichiers MEDIAN.vo et MEDIAN_v.sdo situés dans MEDIAN/simulation/modelsim dans votre répertoire simulation.
  • Compiler MEDIAN.vo en utilisant la commande "vlog"

Pour cette simulation vous avez besoin des modèles de simulation pour les cellules de la technologie utilisée. Sur les machines des salles de TP, la bibliothèque correspondante a été pré-compilée. Pour que Modelsim puisse la retrouvez au moment de la simulation il faut lui ajouter cette information.

  • Dans le dossier de simulation faites:
vmap cycloneii_ver /comelec/softs/opt/altera/altera13.0sp1/sim_lib/verilog_libs/cycloneii_ver

Cette commande va vous créer un fichier modelsim.ini contenant la référence à la bibliothèque pré-compilée.

  • Exécutez la simulation en précisant qu'on utilise des primitives ALTERA (dans notre cas celles du cyclone II) en exécutant la commande suivante:
vsim MEDIAN_tb -L cycloneii_ver
  • Que pensez vous de la durée de la simulation ? Que contient le fichier "MEDIAN.vo" ?
    • L'option -L de la commande vsim permet de préciser la bibliothèque (Library) des primitives de la technologie utilisée.

4.5 Simulation de MEDIAN sur une image

Pour finir vous pouvez tester votre filtre median sur une véritable image :

 

Bogart, the original Bogart bruité Bogart filtré

Pour ce faire:

  • Sauvez cet environnement de simulation dans votre répertoire de fichiers sources "median/src".
  • Sauvez également ce fichier de données d'entrées dans le répertoire "/median/simulation" sous le nom "bogart_bruite.hex".
  • Recompilez le fichier "MEDIAN.sv".
  • Compilez le fichier "MEDIAN_IMAGE_tb.sv" et simulez.

Attention, la simulation est nettement plus longue ... Lorsqu'elle sera terminée vous pourrez voir l'image filtrée dans le fichier "/median/simulation/bogart_filtre.pgm" (utilisez la commande "display bogart_filtre.pgm).

 

 

 

Fichier attachéTaille
Binary Data MCE_tb.sv2.31 Ko
Binary Data MEDIAN_IMAGE_tb.sv1.88 Ko
Binary Data MEDIAN_tb.sv1.31 Ko
Binary Data MED_tb.sv4.75 Ko
Binary Data bogart-bruite.hex196 Ko
Fichier synthese.tgz1.2 Ko