Rapport Projet IF4-ARCH

Rapport Projet IF4-ARCH

Implémentation et optimisation d’une chaîne de traitement d’image sur DSP

TMS320C6437

Décembre 2011 – Janvier 2012

Ch

apit

re :

Intr

od

uct

ion

2

2 Projet IF4-ARCH Thibault Jacquemin – Mathieu Marleix

Table des matières

Introduction ............................................................................................................................................. 3

I. Préparation théorique ..................................................................................................................... 4

I. 1. Caractéristique de l’architecture système.................................................................................... 4

I. 2. Estimation de l’effort de calcul ..................................................................................................... 5

A. Filtre de Deriche ...................................................................................................................... 5

B. Dérivateur de Robert ............................................................................................................... 6

C. Transformée de Hough ............................................................................................................ 6

D. Tableau récapitulatif des coûts ............................................................................................... 7

II. Premières implémentations basiques ................................................................................................ 8

II. 1. Implémentation du fichier d’appel des différents opérateurs .................................................... 8

II. 2. Optimisation Garcia Lorca du Filtre de Deriche ........................................................................ 10

A. Principe ...................................................................................................................................... 10

B. Code source ............................................................................................................................... 11

II. 3. Opérateur de Roberts ................................................................................................................ 13

II. 4. Binarisation ................................................................................................................................ 13

II.4. Transformé de Hough ................................................................................................................. 14

II. 5. Données expérimentales ........................................................................................................... 16

III. Nouvelles implémentations et optimisations ................................................................................. 17

III.1. Optimisation de O’Gorman et Clowes de la transformée de Hough ........................................ 17

III.2. Utilisation des Look-Up Tables pour les fonctions trigonométriques ....................................... 18

III.3. Optimisations mathématiques .................................................................................................. 19

A. Valeur absolue : ..................................................................................................................... 19

B. Racine carrée : ....................................................................................................................... 19

C. Arctangente : ......................................................................................................................... 20

D. Sinus/Cosinus ........................................................................................................................ 20

III.3. Optimisations des branchements.............................................................................................. 21

A. Cas des sauts conditionnels : ................................................................................................. 21

B. Cas des boucles : ................................................................................................................... 21

Conclusion ............................................................................................................................................. 22

Sources bibliographiques ...................................................................................................................... 24

Annexes photographiques .................................................................................................................... 25

Code ....................................................................................................................................................... 26

1. Première implémentation ......................................................................................................... 26

2. Dernière implémentation .......................................................................................................... 35

Ch

apit

re :

Intr

od

uct

ion

3


Introduction Ce projet de quatrième année d’ingénieur en majeur informatique à ESIEE Paris a pour vocation

l’implémentation puis l’optimisation d’une chaîne de traitement d’image sur DSP TMS320C6437 à

l’aide des différentes techniques d’optimisations vues au cours de l’unité d’IF4-ARCH. Ce projet peut

être résumé par le diagramme suivant :

Figure 1 . Schéma des opérateurs

A partir d’une image d’entrée capturée par un périphérique de type caméra, on vient détecter les différents contours présents à l’aide d’un filtre de Deriche composé d’un lissage et d’une dérivation. On sélectionne les maximas locaux du gradient avec un seuillage et on vient ensuite détecter les points alignés grâce à une application de transformée de Hough pour finalement dessiner les lignes dominantes présentes sur l’image de sortie.

Ch

apit

re :

Pré

par

atio

n t

héo

riq

ue

4


I. Préparation théorique Une analyse de la plateforme de travail fournie étant nécessaire pour pouvoir fournir

l’implémentation puis l’optimisation du code demandé, nous avons donc examiné la configuration de

celle-ci. Le matériel fournis est une carte TMS320C6437 EVM DAVINCI de Texas Instrument

possédant un processeur DSP de type 6XXXX. On utilisera donc l’outil Code Composer Studio de

Texas Instrument pour les besoins de développement. La base du projet étant fournie, il n’est pas

nécessaire de procéder à la configuration d’un nouveau projet en rentrant les différents paramètres

de carte. Seul les paramètres nécessaires au lancement d’une version release seront rajoutés pour

permettre des relevés en situation réelle.

I. 1. Caractéristique de l’architecture système

Les différentes informations sur le DSP 6437 sont stockées dans des fichiers de configuration à savoir

TP_DSP.tcf situé dans la configuration Bios et TP_DSP.cmd situé à la racine du projet.

La fréquence relative au processeur 594 MHz et celui-ci possède 8 voies. 5 zones mémoires sont disponibles, celles dédiées au cache, dont nous laisserons la gestion au compilateur, deux mémoires internes à savoir la L1DSRAM et l’IRAM ainsi qu’une mémoire externe, la DDR2. Les différentes informations relatives à la mémoire sont résumées dans le tableau de la tableau 1 ci-dessous.

Mémoire Taille Utilisation Attribution

cache_L1D 32KB, créat ion de tas non autorisée

Cache

cache_L1P 32KB, créat ion de tas non autorisée

Cache

L1DSRAM 80KB, tas 8K Données L1Buffer

IRAM 128KB, taille de tas 8K,

Code et données L2Buffer

DDR2 128MB,tas 16MB Code et données ExtBuffer

Tableau 1. Zone mémoire du TMS320C6437

Ch

apit

re :

Pré

par

atio

n t

héo

riq

ue

5


I. 2. Estimation de l’effort de calcul

Avant une première implémentation de la chaine de traitement, on cherche de visualiser l’effort

nécessaire à la carte lors du traitement de l’image pour attester de la faisabilité de l’implémentation

ainsi que de la pertinence de son implémentation sur le matériel choisi.

On va donc mesurer les différents paramètres lié aux opérateurs de notre chaine de traitement au

travers d’une présentation des différents opérateurs utilisés.

A. Filtre de Deriche

La détection de contour est une étape préliminaire de nombreux traitement d’image. Ici cette

opération est effectuée via un filtre de Deriche. Celui-ci est dérivé du filtre de Canny étendu aux

réponses infinies. Le filtre de Deriche est donc un filtre à réponse impulsionnelle infinie. Deux étapes

sont mises en place pour parvenir au traitement final : un lissage et une dérivation.

Le traitement d’une image est indépendant de la précision demandée et le paramètre α ajuste la

largeur de la fenêtre du filtre. Les équations utilisées par la première versions de celui-ci sont telles

que décrites par la figure 2.

Figure 2. Formule de lissage et dérivation

Le parcours de l’image est fait plusieurs fois et peut être résumé par le schéma suivant :

Ch

apit

re :

Pré

par

atio

n t

héo

riq

ue

6


B. Dérivateur de Robert

L’opérateur de Robert est inclus dans le filtre de Deriche, il nous permet de calculer le gradient de

l’image à l’aide de deux masques de convolution tel que : Le désavantage majeur de cet opérateur

est sa forte sensibilité au bruit.

Figure 3 . Masque de convolutions

L’implémentation de celui après filtrage par l’opérateur permet de réduire la perturbation subis par

celui-ci.

C. Transformée de Hough

La transformé de Hough permet de détecter les lignes dominantes dans une image.

Les droites sont décrites en coordonnées polaires suivant la formule suivante :

Y sin t + X cos t = R

Le but de l’algorithme va être de reconstituer ces droites à partir des points de contour.

Pour chaque point, nous allons parcourir toutes les valeurs de t possibles et calculer la valeur de R

correspondante, puis nous allons incrémenter un tableau de compteurs, appelé accumulateur,

dépendant de ces 2 paramètres.

Ainsi des points alignés augmenteront la même case du tableau, et il suffit dès lors de détecter les

plus fortes cases de l’accumulateur pour reconstituer les droites correspondantes sur l’image de

sortie.

Cette reconstitution se fait par exemple en parcourant les abscisses de l’image de sortie, et en

calculant l’ordonnée correspondant avec la formule ci-dessus, puis en passant le pixel ciblé dans une

autre couleur.

Ch

apit

re :

Pré

par

atio

n t

héo

riq

ue

7


D. Tableau récapitulatif des coûts

Tableau 2. Tableau des différents coûts d’implémentation des opérateurs

Version non optimisée Lissage Dérivation Transformée Hough

NB d’opérations par pixel 16 MULT, 14 ADD 10 MULT, 10 ADD (1 sin, 1 cos, 2 MULT, 1 ADD) *180

Nombre d’opération 45 MOPS 30 MOPS Si 20% pixels à traiter

3,1*10^5 sin,cos + 162 MOPS

Occupation mémoire Deux images et 4

lignes en mémoires

Deux images et 4

lignes en mémoires

Deux images. 180 accès en

mémoire par point

Ch

apit

re :

II. P

rem

ière

s im

plé

men

tati

on

s b

asiq

ues

8


II. Premières implémentations basiques La première étape de notre projet fût de proposer une implémentation basique des opérateurs à

partir de code MATLAB fournis, ce principe étant basé sur les méthodes de travail en entreprise.

Cette implémentation se base donc sur plusieurs fichiers liés aux différents opérateurs ainsi que sur

le fichier d’appel aux différentes fonctions.

II. 1. Implémentation du fichier d’appel des différents opérateurs

On joint le code du fichier fonction.c au moment de l’implémentation basique.

1. Code source - fonction.c

//Allocation memoire et la structure qui contiendra l'image FVID_alloc( ccdcHandle, &FBAddr );

FVID_alloc( ccdcHandle, &FBAddrimageOut );

//=====BOUCLE ACQUISITION & COPIE & AFFICHAGE DES IMAGES=========

// 1)Acquisition

for( i = 0; i < numOfIterations; i++ ) {

if ( IOM_COMPLETED != FVID_exchange( ccdcHandle, &FBAddr ) ) {

return;

}

// fin Acquisition

// 2)Traitement

// a)Sauvegarde de l'image pour traitement

for( j = 0; j < HAUTEUR; j++ ) {

for( k = 0; k < LARGEUR ; k++ ) {

imageIn[j*LARGEUR + k] = (Uint8) ((((Uint16*)FBAddr-

>frameBufferPtr)[j*720 + k]) >> 8);

}

}

memcpy(imageGrey,imageIn,NB_ELT);

// fin Sauvegarde

ts = C64P_getltime();

deriche(imageIn, imageOut, LARGEUR, HAUTEUR, GAMMA);

te = C64P_getltime();

//LOG_printf( &trace, " Nbcycles Deriche = %u", te - ts );


robertsG(imageOut, imageIn, LARGEUR, HAUTEUR);


//LOG_printf( &trace, " Nbcycles Roberts = %u", te - ts );


binarisation(imageIn, imageOut, LARGEUR, HAUTEUR, SEUIL);


//LOG_printf( &trace, " Nbcycles Seuillage = %u", te - ts );


hough(imageOut, imageIn, LARGEUR, HAUTEUR, VOTES, trace);


Ch

apit

re :

II. P

rem

ière

s im

plé

men

tati

on

s b

asiq

ues

9


// c) Affichage du résultat


for( k = 0; k < LARGEUR ; k++ ) {

((Uint16*)FBAddrimageOut->frameBufferPtr)[j*720 + k] =

((((Uint16)imageIn[j*LARGEUR + k])<<8) | 0x0080);

}

}

// fin Affichage

// fin Traitement

// 3)Affichage :

if ( IOM_COMPLETED != FVID_exchange( vid0Handle, &FBAddrimageOut ) ) {

return;

}

// fin Affichage

}

//====FIN BOUCLE ACQUISITION & TRAITEMENT & AFFICHAGE DES IMAGES========

FVID_free(vid0Handle, FBAddr);

FVID_free(vid0Handle, FBAddrimageOut);

// Free Memory Buffers

for( i=0; i< NO_OF_BUFFERS; i++ ) {

FVID_free( ccdcHandle, ccdcAllocFB[i] );

FVID_free( vid0Handle, vidAllocFB[i] );


}

free(imageIn);

free(imageOut);

free(imageGrey);

// Delete Channels

FVID_delete( ccdcHandle );

FVID_delete( vid0Handle );

FVID_delete( vencHandle );

On observe ici les différents appels aux fonctions codées durant cette partie, les déclarations et les

libérations de mémoire propres aux structures utilisées.

Ch

apit

re :

II. P

rem

ière

s im

plé

men

tati

on

s b

asiq

ues

10


II. 2. Optimisation Garcia Lorca du Filtre de Deriche

A. Principe

Nous avons directement implémenté l’optimisation de Garcia Lorca au sein de notre code. On avait

cependant deux choix d’implémentation à savoir utiliser deux filtres du premier ordre ou un seul

filtre du second ordre. Les schémas représentatifs des deux implémentations possible sont tel que

présentés ci-dessous.

Figure 4 . Implémentation FGL 2nd ordre

Figure 5 . Implémentation FGL 1er ordre

Ch

apit

re :

II. P

rem

ière

s im

plé

men

tati

on

s b

asiq

ues

11


Le nombre d’opération nécessitée par ces deux implémentations pouvant être résumé par le tableau

3 1 nous a permis faire notre choix quant à notre choix d’implémentation.

Tableau 3. Complexité filtre de Deriche

En examinant le détail des résultats du nombre d’opérations, nous avons choisi une implémentation

du filtre de Deriche à l’aide de filtre du second ordre nécessitant moins d’opération que deux filtres

du premier ordre.

B. Code source

2. Code source - Filtre Deriche

#include "projet.h"

void deriche(Uint8 *in, Uint8 *out, Uint32 largeur, Uint32 hauteur, float

gamma) {

int i,j;

double g1 = (1-gamma)*(1-gamma);

double g2 = 2*gamma;

double gg = gamma*gamma;

double *X = (double*) malloc(largeur*hauteur*sizeof(double));

double *Y = (double*) malloc(largeur*hauteur*sizeof(double));

// Horizontal smoothing

for (i=0; i<largeur; i++) { // for every line :

// Filtre causal

X[i] = g1*((double)in[i]);

X[largeur+i] = g1*((double)in[largeur+i]+ (g2 * X[i]));

for (j=2; j<hauteur; j++) {

X[j*largeur+i]= (g1*((double)in[j*largeur+i]) + (g2*X[(j-

1)*largeur+i]) + (gg*X[(j-2)*largeur+i]));

}

// Filtre anticausal

Y[((hauteur-1)*largeur+i)] = g1*X[(hauteur-1)*largeur+i];

Y[(hauteur-2)*largeur+i] = g1*X[(hauteur-2)*largeur+i] +

g2*Y[(hauteur-1)*largeur+i];

for (j=hauteur-3; j>=0; j--) {

Y[j*largeur+i] = g1*X[j*largeur+i] +

g2*Y[(j+1)*largeur+i] + gg*Y[(j+2)*largeur+i];

}

}

for( j = 0; j < largeur*hauteur; j++ ) {

out[j] = (Uint8)Y[j];

}

Ch

apit

re :

II. P

rem

ière

s im

plé

men

tati

on

s b

asiq

ues

12


// Transposing matrix Y into matrix X

for (i=0; i<largeur; i++) {


X[j*largeur+i] = Y[i*hauteur+j];

}

}

// Vertical smoothing

for (j=0; j<hauteur; j++) { // for every line :

// Filtre causal

Y[j] = g1*X[j];

Y[hauteur+j] = g1*X[hauteur+j]+ (g2 * Y[j]);


Y[i*hauteur+j]= (g1*X[i*hauteur+j]) + (g2 * Y[(i-

1)*hauteur+j]) + (gg*Y[(i-2)*hauteur+j]);

}


out[(largeur-1)*hauteur+j] = g1*Y[(largeur-1)*hauteur+j];

out[(largeur-2)*hauteur+j] = g1*Y[(largeur-2)*hauteur+j] +

g2*out[(largeur-1)*hauteur+j];

for (i=largeur-3; i<=0; i--) {

out[i*hauteur+j] = g1*Y[i*hauteur+j] +

g2*out[(i+1)*hauteur+j] + gg*out[(i+2)*hauteur+j];

}

}

free(X);

free(Y);

}

On remarque une utilisation de double pour stocker les valeurs des différentes variables, la précision

d’un type float étant insuffisante pour le fonctionnement de l’algorithme. Le déroulement du code

est semblable au schéma de la figure 1 : on observe un traitement par filtre du second ordre pour

chacun des différents blocs (utilisation des termes de rang i – 1 et i – 2). On observe bien d’autre

part le changement de type de parcours entre le vertical s’effectuant sur les lignes et l’horizontal

s’effectuant sur les colonnes.

Ch

apit

re :

II. P

rem

ière

s im

plé

men

tati

on

s b

asiq

ues

13


II. 3. Opérateur de Roberts

3. Code source – Opérateur de Roberts

#include "projet.h"

void robertsG(Uint8 *in, Uint8 *out, Uint32 largeur, Uint32 hauteur) {

Uint32 i,j;



out[j*largeur+i] = (Uint8)sqrt(pow(-in[j*largeur+i] +

in[j*largeur+i+1] - in[(j+1)*largeur+i] + in[(j+1)*largeur+i+1],2) + pow(-

in[j*largeur+i] + in[(j+1)*largeur+i] - in[j*largeur+i+1] +

in[(j+1)*largeur+(i+1)],2));

}

}

}

On voit donc le calcul de la norme du gradient après application des deux matrices données dans la

partie précédente. On intègre les opérations de manière directe offrant un rendement plus

important que celui de l’utilisation de tableaux stockant les valeurs.

II. 4. Binarisation

4. Code source - Binarisation

#include "projet.h"

void binarisation(Uint8 *in, Uint8 *out, Uint32 largeur, Uint32 hauteur,

Uint32 threshold) {

Uint32 j;

for( j = 0; j < hauteur*largeur; j++ ) {

if (in[j] > threshold) {

out[j] = 255;

}

else {

out[j] = 0;

}

}

}

Le code de la fonction binarisation étant relativement simple, on parcourt chaque pixel de l’image

d’entrée auquel on binarise en fonction de sa valeur et du seuil fourni.

Ch

apit

re :

II. P

rem

ière

s im

plé

men

tati

on

s b

asiq

ues

14


II.4. Transformé de Hough

5. Code source – Transformé de Hough

#include "projet.h"

void hough(Uint8 *in, Uint8 *out, Uint32 largeur, Uint32 hauteur, Uint32

ecartVote, LOG_Obj trace) {

Uint32 i,j,x,y,rho=0,angle=0,AccMax=0,rho_idx=0,maxrho =

(Uint32)ceil(sqrt(largeur*largeur + hauteur*hauteur));

double angler=0;

// Accumulator initialization

Uint32 *Acc = (Uint32*)malloc(MAXTHETA*maxrho*sizeof(Uint32));

for(j=0; j<maxrho*MAXTHETA;j++){

Acc[j]=0;

}

// Compute Hough transform for every in(x,y)>0

for (j=1; j<hauteur-2; j++) {

for (i=1; i<largeur-2; i++) {

if (in[j*largeur+i] == 255) {

for (angle=0; angle<MAXTHETA; angle++) {

angler = angle*PI/MAXTHETA;

rho_idx = (Uint32)_round(((double)j*sin(angler) +

(double)i*cos(angler) + (double)maxrho)/2);

if (rho_idx<maxrho && rho_idx>0) {

Acc[rho_idx*MAXTHETA+angle]++;

if (Acc[rho_idx*MAXTHETA+angle] > AccMax) {

AccMax = Acc[rho_idx*MAXTHETA+angle];

}

}

}

}

}

}

AccMax -= ecartVote;

Cette première partie de la fonction, exhaustive, est très coûteuse. On balaie 180 fois chaque pixel,

entrainant une perte de temps très grande.

De plus, les points stockés dans l’accumulateur ne sont pas ne représentent pas toujours un

maximum : le fait qu’on balaie 180 fois l’image induit une zone autour de chaque maximum où les

valeurs de l’accumulateur seront fortes également. Pour éviter cela, on met en place une condition

permettant de calculer la valeur maximale de l’accumulateur et par la suite, de réduire l’intervalle de

valeurs sélectionnées en fonction de celui-ci.

Ch

apit

re :

II. P

rem

ière

s im

plé

men

tati

on

s b

asiq

ues

15


// Draw Hough lines

for (rho_idx=0; rho_idx<maxrho; rho_idx++) {

// Case theta = 0

if (Acc[rho_idx*MAXTHETA] > AccMax) {


rho = rho_idx*2 - maxrho;

for(x=0;x<largeur;x++) {

out[x]=255;

}

}

// Others angles






y = (Uint32)_round(((double)rho -

(double)x*cos(angler))/sin(angler));

if(y<hauteur && y>0) {

out[y*largeur+x]=255;

}

}

}

}

}

free(Acc);

}

Ci-dessus la deuxième partie de la fonction Hough dessinant les lignes. On aurait pu choisir de

parcourir les ordonnées au lieu des abcisses puisque hauteur < largeur. Cependant la formule des x

seraient la suivante :

x = (Uint32)_round(((double)rho - (double)y*sin(angler))/cos(angler));

A cause du cosinus au dénominateur, il aurait fallu mettre un test supplémentaire, effectué sur

toutes les valeurs de l’angle, pour détecter quand celui-ci vaudrait 90°. Cela aurait généré des

branchements inutiles et donc une perte de temps en aléas de contrôle.

Ch

apit

re :

II. P

rem

ière

s im

plé

men

tati

on

s b

asiq

ues

16


II. 5. Données expérimentales

On analyse les différents relevés obtenus après cette première implémentation exhaustive de la

chaine de traitement demandée.

6. Données brut obtenues en sortie des logs de CCS

0 Nbcycles Deriche = 145046563 1 Nbcycles Roberts = 1207611674 2 Nbcycles Seuillage = 3176913 3 Nbcycles Hough = 106866192 4 Nbcycles Deriche = 149488462 5 Nbcycles Roberts = 863721150 6 Nbcycles Seuillage = 3182477 7 Nbcycles Hough = 947340410 8 Nbcycles Deriche = 149458890 9 Nbcycles Roberts = 866845390 10 Nbcycles Seuillage = 3182835 11 Nbcycles Hough = 942295372 12 Nbcycles Deriche = 149525186 13 Nbcycles Roberts = 886553884 14 Nbcycles Seuillage = 3188353 15 Nbcycles Hough = 967283294 16 Nbcycles Deriche = 149489526 17 Nbcycles Roberts = 894002428 18 Nbcycles Seuillage = 3183023 19 Nbcycles Hough = 1002057158 20 Nbcycles Deriche = 149471624 21 Nbcycles Roberts = 892816446 22 Nbcycles Seuillage = 3186293 23 Nbcycles Hough = 1034116454 24 Nbcycles Deriche = 149497514 25 Nbcycles Roberts = 889956944 26 Nbcycles Seuillage = 3189473 27 Nbcycles Hough = 1016613556 28 Nbcycles Deriche = 149494314 29 Nbcycles Roberts = 880040054 30 Nbcycles Seuillage = 3182701 31 Nbcycles Hough = 964789164

Opérateur Nombre cycle moyen/pixel Charge lors de l’exécution (%)

Deriche 2482 7,65

Roberts 15378 47,38

Seuillage 53 0,16

Hough 14545 44,81

TOTAL 32458 100%

Tableau 4. Interprétation des résultats

On observe que l’opérateur du gradient de Roberts génère environ la moitié du temps d’exécution.

Néanmoins, cela est dû à l’utilisation des fonctions de la librairie <math.h> générant des coûts très

lourd (la fonction pow() essentiellement).

Ch

apit

re :

III.

No

uve

lles

imp

lém

enta

tio

ns

et

op

tim

isat

ion

s

17


III. Nouvelles implémentations et optimisations

III.1. Optimisation de O’Gorman et Clowes de la transformée de Hough

Le but est d’approximer l’angle servant à représenter la droite en utilisant le gradient local au point

concerné (autrement dit, la valeur du vecteur normal à la droite en ce point). Cela permet de passer

une seule fois sur chaque pixel et non 180 fois !

L’inconvénient de cette méthode est qu’il faut stocker

les valeurs des gradients horizontaux et verticaux au

moment où l’on exécute la dérivation, mais aussi utiliser

une division et la fonction arctangente pour calculer

l’angle.

Θ = arctan ( Gx / Gy )





angler = atan2(Gy[j*largeur+i],Gx[j*largeur+i]);

angle = angler/PI*MAXTHETA;





}

}

}

}

Nouvelle version de la boucle calculant l’accumulateur.

L’autre avantage est aussi que les zones de maxima sont plus nettes, plus fines.

Toutefois on s’est sommes aperçu qu’il manquait la moitié des lignes sur le résultat obtenu. Nous avons donc pris la décision de stocker les angles de -2 π à 2 π avec de plus la transformation suivante : si le rayon est négatif, on prend alors son opposé et on ajoute π à l’angle. C’est un tableau 2 fois plus grand mais on verra dans la suite que l’on dispose de techniques pour minimiser son impact.

Ch

apit

re :

III.

No

uve

lles

imp

lém

enta

tio

ns

et

op

tim

isat

ion

s

18


III.2. Utilisation des Look-Up Tables pour les fonctions trigonométriques

Sans compter l’arctangente appelée une fois, les fonctions sinus et cosinus sont appelées 4 fois dans

la transformé de Hough. On peut gagner du temps en évitant de recalculer les valeurs de ces deux

fonctions en les calculant et les stockant au début du programme.

Certes, cela implique un coût mémoire mais c’est toujours la rapidité qui reste notre objectif premier

(une autre alternative consisterait a utilisé une approximation polynomiale de ces 2 fonctions

détaillée dans la suite).

#pragma DATA_SECTION( tSin, ".L1Buffer" )

double tSin[MAXTHETA+1];

#pragma DATA_SECTION( tCos, ".L1Buffer" )

double tCos[MAXTHETA+1];

Déclaration des tables : situées dans la mémoire interne, leur appel n’en sera que plus rapide.

for( i = 0; i <= MAXTHETA; i++ ){

tSin[i] = sin((double)i*PI/MAXTHETA);

tCos[i] = cos((double)i*PI/MAXTHETA);

}

Initialisation des tables

hough(imageIn, imageGrey, LARGEUR, HAUTEUR, VOTES, Gx, Gy, tSin, tCos);

Utilisation : passage des pointeurs sur les LUT en paramètre

rho_idx = (Int32)((double)j*tSin[angle] + (double)i*tCos[angle] +

(double)maxrho + 1) >>1;

Exemple d’appel dans la transformée de Hough

Ch

apit

re :

III.

No

uve

lles

imp

lém

enta

tio

ns

et

op

tim

isat

ion

s

19


III.3. Optimisations mathématiques

Les fonctions trigonométriques ne sont pas les seules à faire appel à la librairie math.h.

Tout d’abord, les fonctions simples nécessitant un simple changement d’écriture :

Code original Nouveau code

pow(x,2) x*x round(x) x + 0.5 ceil(x) x + 0.9

Pour ceil() et round(), on utilise le fait qu’un nombre décimal soit tronqué au moment de sa

conversion en entier en C.

Nous allons ensuite redéfinir les fonctions suivantes :

A. Valeur absolue : Déjà utilisée lors du TP sur l’implémentation du filtre de Sobel, cette fonction n’utilise qu’une

soustraction et 2 opérations logiques. Elle permet aussi d’éviter un branchement.

Uint32 mAbs(double d) {

// MSB extended to the long word

Uint32 abs = (Uint32) d, mask = abs >> 31;

// Do nothing if d>0 ; negate and add 1 if d<0

return abs = (abs ^ mask) - mask;

}

B. Racine carrée : Nous allons, pour ce faire, passer par la racine carrée inverse qui bénéficie d’une

optimisation bien plus puissante basée sur une constante « magique » attribuée à Greg

Walsh, le développeur de Quake III. On récupère ensuite la racine carrée en multipliant son

inverse par x plutôt que de diviser 1 par cette dernière.

Le gain de cette méthode est de 183% par rapport à l’appel à la fonction sqrt() de la librairie

pour une erreur absolue maximale de l’ordre de 10-6.

A noter que l’on n’utilise cette fonction que pour calculer la diagonale dans la transformée

de Hough. Pour le calcul du gradient, on utilise l’approximation abs(Gx) + abs(Gy) corrigeable

en baissant le seuil à l’étape suivante.

double invSqrtD(const double x) {

const double xhalf = 0.5F*x;

union // get bits for floating value

{

double x;

long i;

} u;

u.x = x;

u.i = SQRT_MAGIC_D - (u.i >> 1); // gives initial guess y0

return u.x*(1.5F - xhalf*u.x*u.x);// Newton step, repeating increases

accuracy

}

Uint32 fastSqrtD(const double x) {

return (Uint32)(x * invSqrtD(x));

}

Ch

apit

re :

III.

No

uve

lles

imp

lém

enta

tio

ns

et

op

tim

isat

ion

s

20


C. Arctangente : Il aurait été possible d’utiliser une LUT pour cette fonction également. Cependant, il aurait

fallu dans notre cas stocker 255² = 65025 valeurs si nous voulions traiter toutes les situations.

Dans son livre Streamlining Digital Signal Processing - A Tricks of the Trade Guidebook,

Richard G. Lyons fait la comparaison entre plusieurs approximations polynomiales de la

fonction arctangente. Celle qui suit présente le meilleure compromis rapidité/ précision avec

un gain de 267% par rapport à la fonction de la librairie standard et une erreur absolue

maximale de 0.0038 radians (0.22 °). Il a fallu rajouter également une détection du quadrant

dans lequel le calcul s’effectue pour renvoyer la bonne valeur.

double fastAtan2(double y, double x) {

abs_y = (double)mAbs(y)+1e-10 // kludge to prevent 0/0 condition

if (x>=0) {

// if in quad I

r = (x - abs_y) / (x + abs_y);

angle = PI/4*r + 0.273*r*(1 - mAbs(r));

}

else {

// if in quad II

r = (x + abs_y) / (abs_y - x);

angle = PI/2 + PI/4*r + 0.273*r*(1 - mAbs(r));

}

if (y < 0)

return(-angle); // negate if in quad III or IV

else

return(angle);

}

D. Sinus/Cosinus Bien que nous ayons utilisé des LUT pour ces deux fonctions, il aurait été possible d’utiliser

une approximation polynomiale. L’approximation présentée requière 2 multiplications et 1

addition pour une erreur absolue maximale de 0.056 radians ou 5 multiplications et 3

additions pour une erreur absolue maximale de 0.001 radians.

double sine(double x) {

const double B = 4/pi;

const double C = -4/(pi*pi);

double y = B * x + C * x * abs(x);

#ifdef EXTRA_PRECISION

// const double Q = 0.775;

const double P = 0.225;

y = P * (y * abs(y) - y) + y; // Q * y + P * y * abs(y)

#endif

return y; }

Pour le cosinus, il suffit de réaliser une translation sur x.

double cosine(double x) {

x -= (x > PI)*2*PI;

return sine(x);

}

Ch

apit

re :

III.

No

uve

lles

imp

lém

enta

tio

ns

et

op

tim

isat

ion

s

21


III.3. Optimisations des branchements

Pour éviter de perdre du temps en aléas de contrôle, il fallait éviter au maximum les branchements,

aussi bien dans les boucles qu’avec des sauts conditionnels

A. Cas des sauts conditionnels : Dans la majorité des cas, il n’y a qu’une opération ou deux après une condition. Dès lors, on

peut se contenter du bit renvoyé par le test.

Ci-dessous, un exemple avec le seuillage après calcul du gradient.

out[i] = (Uint8)(256 - (G > threshold)); //seuillage

B. Cas des boucles : Tout d’abord, il faut veiller à parcourir les images en ligne car le chargement des pixels

voisins est déjà fait et le programme évite alors de devoir faire un saut dans la mémoire.

Mis à part lors des copies des flux vidéo dans les tableaux, les blocs de mémoire utilisés sont

continus. Il est alors possible de remplacer les deux boucles imbriquées par une seule boucle,

ce qui évitera autant de branchements que la taille du compteur de la boucle externe.

De plus, il est possible d’éviter au programme de devoir recalculer les indices de chaque case

d’une itération à la suivante (ou mieux encore d’un pixel voisin à un autre). On économise

ainsi des multiplications (ou des additions) superflues. Attention toutefois avec cette

optimisation : le compilateur a bien souvent sa propre manière d’optimiser les compteurs et

le faire à sa place peut provoquer l’allongement du temps de traitement quand on spécifie

des options d’optimisation à un niveau trop bas au compilateur.

Enfin, on notera l’utilisation possible de la pragma UNROLL pour tenter de dérouler les

boucles sans avoir pu constater un réel gain sur l’ensemble du programme.

Ci-dessous un exemple de toutes ses optimisations sur le filtre de Roberts (seuillage inclus) :

void robertsG(Uint8 *in, Uint8 *out, Uint32 largeur, Uint32 hauteur,

Uint32 threshold, double *Gx, double *Gy) {

const Uint32 NB_ELMT = largeur*hauteur;

Uint32 i,G;

Uint8 *pi, *ps;

pi = in; ps = pi + largeur;

for (i=0; i<NB_ELMT; i++) {

Gx[i] = - pi[0] + pi[1] - ps[0] + ps[1];

Gy[i] = - pi[0] - pi[1] + ps[0] + ps[1];

G = (Uint32)(mAbs(Gx[i]) + mAbs(Gy[i]));


++pi;++ps;

}

Ch

apit

re :

Co

ncl

usi

on

22


Conclusion Ce projet nous a permis de nous rendre compte comment l’optimisation de code pouvait intervenir

sur le rendus des résultats obtenus. De même nous avons pu voir que les limitations matérielles

imposées par l’architecture jouaient un rôle majeur dans le choix des implémentations et

développement des algorithmes mis en œuvre. La départ d’une base de code MATLAB nous a permis

de nous placer en situation réel d’un développement en entreprise ayant un modèle mathématique

validé et devant le transposer sur une architecture particulière. Ce projet nous à donc permis de

mettre en action à la fois nos compétence en architecture mais aussi en optimisation, points

centraux du cours d’IF4-ARCH.


Deriche 2295 31,65

Roberts (Seuillage inclus) 3509 48,56

Hough 1430 19,79

TOTAL 7227 100

Tableau 4. Interprétation des résultats après la première série d’optimisations

Opérateur Gain (%)

Deriche 108

Roberts (Seuillage inclus) 440

Hough 1017

TOTAL 449

Tableau 5. Gain obtenu après la première série d’optimisations

Ch

apit

re :

Co

ncl

usi

on

23



Deriche 2287 31,77

Roberts (Seuillage inclus) 2289 31,67

Hough 1516 20,99

TOTAL 6101 100

Tableau 6. Interprétation des résultats après la deuxième série d’optimisations

Opérateur Gain (%)

Deriche 109

Roberts (Seuillage inclus) 674

Hough 959

TOTAL 532

Tableau 7. Gain obtenu après la deuxième série d’optimisations

Graphe 1. Comparaison des résultats obtenus

Ch

apit

re :

Co

ncl

usi

on

24


Sources bibliographiques

Thierry Grandpierre, TD Implantation du filtre de Deriche sur DLX, http://www.esiee.fr/~grandpit/IF4-ARCH-TD-DericheDLX.pdf

Eva Dokladalova, Méthodologie d’optimisation IF-4ARCH 2010-2011,

http://dokladae.free.fr/wp-content/uploads/cours_2010_2011.pdf 1: F. Lohier, L. Lacassagne, P. Garda, Programming techniques for real time software

Implementation of optimal edge detectors: a comparison between state of the Art DSP and RISC architectures, DSP World, 1998

http://www.ief.upsud.fr/~lacas/Publications/DSPWorld98.pdf

Eva Dokladalova, Projet IF4-ARCH Méthodologie d’optimisation, 2011/2012

http://dokladae.free.fr/wp-content/uploads/projet-if4_2011-2012.pdf

Edouard Ritz, Tomasz Marszal , Epaisseur et localisation des contours des detecteurs par

derivation (Sobel, Prewitt, Roberts) ou par gradient morphologique, 1998,

http://perso.telecom-paristech.fr/~maitre/BETI/localisation_et_epaisseur/

Richard G. Lyons, Streamlining Digital Signal Processing – A Tricks of the Trade Guidebook, 2007

Chris Lomont, Fast Inverse Square Root, 2003,

http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf

Explications sur l’approximation polynomial du sinus et du cosinus

http://devmaster.net/forums/topic/4648-fast-and-accurate-sinecosine/

http://www.esiee.fr/~grandpit/IF4-ARCH-TD-DericheDLX.pdf

http://dokladae.free.fr/wp-content/uploads/cours_2010_2011.pdf

http://www.ief.upsud.fr/~lacas/Publications/DSPWorld98.pdf

http://dokladae.free.fr/wp-content/uploads/projet-if4_2011-2012.pdf

http://perso.telecom-paristech.fr/~maitre/BETI/localisation_et_epaisseur/

http://devmaster.net/forums/topic/4648-fast-and-accurate-sinecosine/

Ch

apit

re :

An

nex

es p

ho

togr

aph

iqu

es

25


Annexes photographiques

Image originale

Image après lissage

Image après filtre de Deriche

Image après transformée de Hough

Ch

apit

re :

Co

de

26


Code

1. Première implémentation

#include <math.h>

#include <tistdtypes.h>

#include <log.h>

#define MAXTHETA 180

#define PI 3.14159265


gamma);


Uint32 threshold);

void robertsG(Uint8 *in, Uint8 *out, Uint32 largeur, Uint32 hauteur);


votes, LOG_Obj trace);

Projet.h

#include "projet.h"


gamma) {

int i,j;








// Filtre causal






}



Y[(hauteur-2)*largeur+i] = g1*X[(hauteur-2)*largeur+i] + g2*Y[(hauteur-

1)*largeur+i];


Y[j*largeur+i] = g1*X[j*largeur+i] + g2*Y[(j+1)*largeur+i] +

gg*Y[(j+2)*largeur+i];

}

}

for( j = 0; j < largeur*hauteur; j++ ) {


}

Ch

apit

re :

Co

de

27





X[j*largeur+i] = Y[i*hauteur+j];

}

}



// Filtre causal

Y[j] = g1*X[j];

Y[hauteur+j] = g1*X[hauteur+j]+ (g2 * Y[j]);


Y[i*hauteur+j]= (g1*X[i*hauteur+j]) + (g2 * Y[(i-

1)*hauteur+j]) + (gg*Y[(i-2)*hauteur+j]);

}


out[(largeur-1)*hauteur+j] = g1*Y[(largeur-1)*hauteur+j];

out[(largeur-2)*hauteur+j] = g1*Y[(largeur-2)*hauteur+j] +

g2*out[(largeur-1)*hauteur+j];

for (i=largeur-3; i<=0; i--) {

out[i*hauteur+j] = g1*Y[i*hauteur+j] +

g2*out[(i+1)*hauteur+j] + gg*out[(i+2)*hauteur+j];

}

}

free(X);

free(Y);

}

Deriche_GL.c

#include "projet.h"

void robertsG(Uint8 *in, Uint8 *out, Uint32 largeur, Uint32 hauteur) {

Uint32 i,j;



out[j*largeur+i] = (Uint8)sqrt(pow(-in[j*largeur+i] +

in[j*largeur+i+1] - in[(j+1)*largeur+i] + in[(j+1)*largeur+i+1],2) +

pow(-in[j*largeur+i] + in[(j+1)*largeur+i] - in[j*largeur+i+1] +

in[(j+1)*largeur+(i+1)],2));

}

}

}

RobertsG.c

Ch

apit

re :

Co

de

28


#include "projet.h"


Uint32 threshold) {

Uint32 j;

for( j = 0; j < hauteur*largeur; j++ ) {

if (in[j] > threshold) {

out[j] = 255;

}

else {

out[j] = 0;

}

}

}

Binarisation.c

#include "projet.h"


votes, LOG_Obj trace) {

//We assume here that the dimensions of in and the ones of the RGB image

are the same

Uint32 i,j,x,y,rho=0,angle=0,AccMax=0,rho_idx=0,maxrho =

(Uint32)ceil(sqrt(largeur*largeur + hauteur*hauteur));

double angler=0;


Uint32 *Acc = (Uint32*)malloc(MAXTHETA*maxrho*sizeof(Uint32));

for(j=0; j<maxrho*MAXTHETA;j++){

Acc[j]=0;

}









//LOG_printf( &trace, "(%u)",rho_idx);




AccMax = Acc[rho_idx*MAXTHETA+angle];

}

}

}

}

}

}

Ch

apit

re :

Co

de

29


//LOG_printf( &trace, "%u",AccMax);

// Draw Hough lines



if (Acc[rho_idx*MAXTHETA+angle] > AccMax-30) {



LOG_printf( &trace, "(%u,%u)",rho,angle);


y = (Uint32)_round(((double)rho -

(double)x*cos(angler))/sin(angler));

//LOG_printf( &trace, "(%e,%e)", x, y);



}

}

}

}

}

free(Acc);

}

Hough.c

/* T. Jacquemin & M. Marleix :

Version 3 qui fait acquisition YUV puis seuillage puis affichage

*/

#include <std.h>

#include <stdlib.h>

#include <gio.h>

#include <log.h>

#include "psp_vpfe.h"

#include "psp_vpbe.h"

#include "fvid.h"

#include "psp_tvp5146_extVidDecoder.h"

#include <IMG_sobel.h>

#include <soc.h>

#include <cslr_ccdc.h>

#include "projet.h"

//pour logger ce qui se passe avec log.h (voir DSPBIOS)

extern LOG_Obj trace; // BIOS LOG object

/* extrait de l'exemple EDMA3 :

// 48K L1 SRAM [0x10f04000, 0x10f10000), 0xc000 length

// 32K L1 Dcache [0x10f10000, 0x10f18000), 0x8000 length

// 128K L2 SRAM [0x10800000, 0x10820000), 0x20000 length

// 128M DDR2 [0x80000000, 0x88000000), 0x8000000 length are cacheable

*/

Ch

apit

re :

Co

de

30


#define NO_OF_BUFFERS (2u)

// Global Variable Defined

static PSP_VPSSSurfaceParams *ccdcAllocFB[NO_OF_BUFFERS]={NULL};

static PSP_VPSSSurfaceParams *vidAllocFB[NO_OF_BUFFERS] ={NULL};

static FVID_Handle ccdcHandle;

static FVID_Handle vid0Handle;

static FVID_Handle vencHandle;

/*Pour stockage de l'image en niveaux de gris */

#define LARGEUR 300

#define HAUTEUR 200

#define NB_ELT LARGEUR*HAUTEUR

#define SEUIL 160

#define GAMMA 0.2

#define VOTES 100

//#define ALLOC_STATIC

#define ALLOC_DYNAMIC

static PSP_VPFE_TVP5146_ConfigParams tvp5146Params = {

TRUE, // enable656Sync

PSP_VPFE_TVP5146_FORMAT_COMPOSITE, // format

PSP_VPFE_TVP5146_MODE_AUTO // mode

};

static PSP_VPFECcdcConfigParams ccdcParams = {

PSP_VPFE_CCDC_YCBCR_8, // dataFlow

PSP_VPSS_FRAME_MODE, // ffMode

480, // height

720, // width

(720 *2), // pitch

0, // horzStartPix

0, // vertStartPix

NULL, // appCallback

{

PSP_VPFE_TVP5146_Open, // extVD Fxn

PSP_VPFE_TVP5146_Close,

PSP_VPFE_TVP5146_Control,

},

0 //segId

};

static PSP_VPBEOsdConfigParams vid0Params = {

PSP_VPSS_FRAME_MODE, // ffmode

PSP_VPSS_BITS16, // bitsPerPixel

//PSP_VPBE_RGB_888, //ajout TG

PSP_VPBE_YCbCr422, // colorFormat

(720 * (16/8u)), // pitch

0, // leftMargin

0, // topMargin

720, // width

480, // height

0, // segId

PSP_VPBE_ZOOM_IDENTITY, // hScaling

PSP_VPBE_ZOOM_IDENTITY, // vScaling

PSP_VPBE_EXP_IDENTITY, // hExpansion

PSP_VPBE_EXP_IDENTITY, // vExpansion

NULL // appCallback

};

Ch

apit

re :

Co

de

31


static PSP_VPBEVencConfigParams vencParams = {

PSP_VPBE_DISPLAY_NTSC_INTERLACED_COMPOSITE // Display Standard

};

#ifdef ALLOC_STATIC

#define EDMA3_CACHE_LINE_SIZE_IN_BYTES (128u)

//Buffer : imageIn

// buffer in L1 SRAM, 32K

//#pragma DATA_SECTION( imageIn, ".L1Buffer" )



// buffer in DDR2, 32M

#pragma DATA_SECTION( imageIn, ".ExtBuffer" )

//#pragma DATA_ALIGN( imageIn, EDMA3_CACHE_LINE_SIZE_IN_BYTES );

Uint8 imageIn[NB_ELT];

//Buffer : imageOut

//buffer in L1 SRAM, 32K

//#pragma DATA_SECTION( imageOut, ".L1Buffer" )




#pragma DATA_SECTION( imageOut, ".ExtBuffer" )

//#pragma DATA_ALIGN( imageOut, EDMA3_CACHE_LINE_SIZE_IN_BYTES );

Uint8 imageOut[NB_ELT];

//Buffer : imageGrey


//#pragma DATA_SECTION( imageGrey, ".L1Buffer" )




#pragma DATA_SECTION( imageGrey, ".ExtBuffer" )

//#pragma DATA_ALIGN( imageGrey, EDMA3_CACHE_LINE_SIZE_IN_BYTES );

Uint8 imageGrey[NB_ELT];

#endif

void start_boucle() {

PSP_VPBEChannelParams beinitParams;

PSP_VPFEChannelParams feinitParams;

GIO_Attrs gioAttrs = GIO_ATTRS;

PSP_VPSSSurfaceParams *FBAddr = NULL;

PSP_VPSSSurfaceParams *FBAddrimageOut = NULL;

Uint32 i,j,k;

Uint32 te,ts;

Uint32 numOfIterations = 10000;

#ifdef ALLOC_DYNAMIC

Uint8 *imageIn = (Uint8*)malloc(NB_ELT*sizeof(Uint8));

Uint8 *imageOut = (Uint8*)malloc(NB_ELT*sizeof(Uint8));

Uint8 *imageGrey= (Uint8*)malloc(NB_ELT*sizeof(Uint8));

#endif

//Init CSL du DMA

edma3init();

Ch

apit

re :

Co

de

32


// Create ccdc channel

feinitParams.id = PSP_VPFE_CCDC;

feinitParams.params = (PSP_VPFECcdcConfigParams*)&ccdcParams;

ccdcHandle = FVID_create( "/VPFE0", IOM_INOUT, NULL, &feinitParams,

&gioAttrs);

if ( NULL == ccdcHandle) {

return;

}

// Configure the TVP5146 video decoder

if( FVID_control( ccdcHandle,

VPFE_ExtVD_BASE + PSP_VPSS_EXT_VIDEO_DECODER_CONFIG,

&tvp5146Params) != IOM_COMPLETED ) {

return;

} else {

for ( i=0; i < NO_OF_BUFFERS; i++ ) {

if ( IOM_COMPLETED == FVID_alloc( ccdcHandle, &ccdcAllocFB[i] ) ) {

if ( IOM_COMPLETED != FVID_queue(ccdcHandle, ccdcAllocFB[i] ) ) {

return;

}

}

}

}

// Create video channel

beinitParams.id = PSP_VPBE_VIDEO_0;

beinitParams.params = (PSP_VPBEOsdConfigParams*)&vid0Params;

vid0Handle = FVID_create( "/VPBE0", IOM_INOUT,NULL, &beinitParams,

&gioAttrs );

if ( NULL == vid0Handle ) {

return;

} else {

for ( i=0; i<NO_OF_BUFFERS; i++ ) {

if ( IOM_COMPLETED == FVID_alloc( vid0Handle, &vidAllocFB[i] ) ) {

if ( IOM_COMPLETED != FVID_queue( vid0Handle, vidAllocFB[i]) ) {

return;

}

}

}

}

// Create venc channel

beinitParams.id = PSP_VPBE_VENC;

beinitParams.params = (PSP_VPBEVencConfigParams *)&vencParams;

vencHandle = FVID_create( "/VPBE0", IOM_INOUT, NULL, &beinitParams,

&gioAttrs);

if ( NULL == vencHandle ) {

return;

}

//Allocation memoire et la structure qui contiendra l'image

FVID_alloc( ccdcHandle, &FBAddr );


//BOUCLE ACQUISITION & COPIE & AFFICHAGE DES IMAGES

// 1)Acquisition



return;

}

// fin Acquisition

Ch

apit

re :

Co

de

33


// 2)Traitement



for( k = 0; k < LARGEUR ; k++ ) {

imageIn[j*LARGEUR + k] = (Uint8) ((((Uint16*)FBAddr-

>frameBufferPtr)[j*720 + k]) >> 8);

}

}


// fin Sauvegarde

// b.1)Copie

/*

for( j = 0; j < NB_ELT; j++ ) {

imageOut[j] = imageIn[j];

}

*/

// fin Copie

// b.2)Filtre de Sobel

/*


//sobel(imageIn,imageOut,LARGEUR,HAUTEUR); //version 鬨ves

IMG_sobel(imageIn,imageOut,LARGEUR,HAUTEUR); //version pr魣ompil饍


LOG_printf( &trace, " Nbcycles = %u", te - ts );

*/

// fin Sobel




LOG_printf( &trace, " Nbcycles Deriche = %u", te - ts );


robertsG(imageOut, imageIn, LARGEUR, HAUTEUR);


LOG_printf( &trace, " Nbcycles Roberts = %u", te - ts );


binarisation(imageIn, imageOut, LARGEUR, HAUTEUR, SEUIL);


LOG_printf( &trace, " Nbcycles Seuillage = %u", te - ts );


hough(imageOut, imageIn, LARGEUR, HAUTEUR, VOTES, trace);


LOG_printf( &trace, " Nbcycles Hough = %u", te - ts );

// c) Affichage du resultat


for( k = 0; k < LARGEUR ; k++ ) {

((Uint16*)FBAddrimageOut->frameBufferPtr)[j*720 + k] =

((((Uint16)imageIn[j*LARGEUR + k])<<8) | 0x0080);

}

}

// fin Affichage

// fin Traitement

Ch

apit

re :

Co

de

34


//LOG_printf( &trace, " Affichage iteration = %u", i );

// 3)Affichage :

if ( IOM_COMPLETED != FVID_exchange( vid0Handle, &FBAddrimageOut ) )

{

return;

}

// fin Affichage

}

//FIN BOUCLE ACQUISITION & TRAITEMENT & AFFICHAGE DES IMAGES








}

free(imageIn);

free(imageOut);

// Delete Channels




return;

}

Fonctions.c

Ch

apit

re :

Co

de

35


2. Dernière implémentation


double invSqrtD(const double x);

Uint32 fastSqrtD(const double x);

Uint32 mAbs(double d);

double fastAtan2(double y, double x);

double sine(double x);

double cosine(double x);

mMath.h

#include "mMath.h"

// For Magic Derivation see:

// Chris Lomont

// http://www.lomont.org/Math/Papers/2003/InvSqrt.pdf

// Credited to Greg Walsh.

// 64 Bit float magic number

#define SQRT_MAGIC_D 0x5fe6ec85e7de30da

double invSqrtD(const double x) {

const double xhalf = 0.5F*x;

union // get bits for floating value

{

double x;

long i;

} u;

u.x = x;

u.i = SQRT_MAGIC_D - (u.i >> 1); // gives initial guess y0

return u.x*(1.5F - xhalf*u.x*u.x);// Newton step, repeating increases

accuracy

}

Uint32 fastSqrtD(const double x) {

return (Uint32)(x * invSqrtD(x));

}

Uint32 mAbs(double d) {

Uint32 abs = (Uint32) d, mask = abs >> 31; // MSB extended to the

long word

return abs = (abs ^ mask) - mask; // Do nothing if d>0 ; negate and

add 1 if d<0

}

Ch

apit

re :

Co

de

36


double fastAtan2(double y, double x) {

abs_y = (double)mAbs(y)+1e-10 // kludge to prevent 0/0 condition

if (x>=0)

{

// if in quad I

r = (x - abs_y) / (x + abs_y);

angle = PI/4*r + 0.273*r*(1 - mAbs(r));

}

else

{

// if in quad II

r = (x + abs_y) / (abs_y - x);

angle = PI/2 + PI/4*r + 0.273*r*(1 - mAbs(r));

}

if (y < 0)

return(-angle); // negate if in quad III or IV

else

return(angle);

}

double sine(double x) {

const double B = 4/pi;

const double C = -4/(pi*pi);

double y = B * x + C * x * abs(x);

#ifdef EXTRA_PRECISION

// const double Q = 0.775;

const double P = 0.225;

y = P * (y * abs(y) - y) + y; // Q * y + P * y * abs(y)

#endif

return y;

}

double cosine(double x) {

x -= (x > PI)*2*PI;

return sine(x);

}

mMath.c


#include <log.h>

#include "mMath.h"

#define MAXTHETA 256

#define PI 3.14159265

#define I_PI 0.31830989

#define GREY


gamma);


Uint32 threshold, double *Gx, double *Gy);

void hough(Uint8 *in, Uint8 *out, Uint32 largeur, Uint32 hauteur, Int32

ecartVote, double *Gx, double *Gy, double *tSin, double *tCos);

Projet.h

Ch

apit

re :

Co

de

37


#include "projet.h"


gamma) {

const Uint32 TAILLE = hauteur*largeur;

int i,j,k;







/*


// Filtre causal






}



Y[(hauteur-2)*largeur+i] = g1*X[(hauteur-2)*largeur+i] +

g2*Y[(hauteur-1)*largeur+i];


Y[j*largeur+i] = g1*X[j*largeur+i] + g2*Y[(j+1)*largeur+i] +

gg*Y[(j+2)*largeur+i];

}

}

*/

k=0;



// Filtre causal

X[k] = g1*((double)in[k]);k++;

X[k] = g1*((double)in[k])+ g2*X[k-1];k++;


X[k]= g1*((double)in[k]) + g2*X[k-1] + gg*X[k-2];k++;

}


k--;

Y[k] = g1*X[k];k--;

Y[k] = g1*X[k] + g2*Y[k+1];k--;

for (i=largeur-3; i>=0; i--) {

Y[k] = g1*X[k] + g2*Y[k+1] + gg*Y[k+2];k--;

}

k+=largeur+1;

}

Ch

apit

re :

Co

de

38


/*

for( j = 0; j < TAILLE; j++ ) {


}

*/

/*


k=0;



X[i*hauteur+j] = Y[k++];

}

}

*/


k=0;



X[i*hauteur+j] = Y[j*largeur+i];

}

}

/*


k=0;


// Filtre causal

//k=j;

Y[k] = g1*X[k];k+=hauteur;

Y[k] = g1*X[k]+ g2*Y[k-hauteur];k+=hauteur;


Y[k]= g1*X[k] + g2*Y[k-hauteur] + gg*Y[k-

2*hauteur];k+=hauteur;

}


k-=hauteur;

out[k] = g1*Y[k];k-=hauteur;

out[k] = g1*Y[k] + g2*out[k+hauteur];k-=hauteur;

for (i=largeur-3; i>=0; i--) {

out[k] = g1*Y[k] + g2*out[k+hauteur] + gg*out[k+2*hauteur];k-

=hauteur;

}

k+=hauteur+1;

}

*/

k=0;



// Filtre causal

Y[k] = g1*X[k];k++;

Y[k] = g1*X[k] + g2*Y[k-1];k++;


out[k]= g1*Y[k] + g2*X[k-1] + gg*X[k-2];k++;

}

Ch

apit

re :

Co

de

39



k--;

out[k] = g1*Y[k];k--;

out[k] = g1*Y[k] + g2*out[k+1];k--;


out[k] = g1*Y[k] + g2*out[k+1] + gg*out[k+2];k--;

}

k+=hauteur+1;

}

free(X);

free(Y);

}

Deriche_GL.c

#include "projet.h"


Uint32 threshold, double *Gx, double *Gy) {

const Uint32 NB_ELMT = largeur*hauteur;

Uint32 i,G;

Uint8 *pi, *ps;

pi = in; ps = pi + largeur;

for (i=0; i<NB_ELMT; i++) {

Gx[i] = - pi[0] + pi[1] - ps[0] + ps[1];

Gy[i] = - pi[0] - pi[1] + ps[0] + ps[1];

G = (Uint32)(mAbs(Gx[i]) + mAbs(Gy[i]));


++pi;++ps;

}

}

RobertsG.c

#include "projet.h"

void hough(Uint8 *in, Uint8 *out, Uint32 largeur, Uint32 hauteur, Int32

vote, double *Gx, double *Gy, double *tSin, double *tCos) {

//We assume here that the dimensions of in and the ones of the RGB image

are the same

int rho=0,angle=0,rho_idx=0,maxrho =

(Int32)(fastSqrtD(hauteur*hauteur+largeur*largeur) + 0.9);

Uint32 i,j,x,y,ctr=largeur;

const Uint32 NB_ELMT = maxrho*MAXTHETA;

const Uint32 TAILLE = hauteur*largeur;

//Int32 AccMax=0;

double angler=0;


Uint32 *Acc = (Uint32*)malloc(NB_ELMT*sizeof(Uint32));

for(j=0; j<NB_ELMT;j++){

Acc[j]=0;

}

Ch

apit

re :

Co

de

40





if (in[++ctr] == 255) {

angler = atan2(Gy[ctr],Gx[ctr]);

angler += (angler<0)*PI;

angle = (angler*I_PI)*MAXTHETA;

rho_idx = (Int32)((double)j*tSin[angle] +

(double)i*tCos[angle] + (double)maxrho + 1) >>1;

Acc[(Uint32)((angle+(rho_idx>0)*PI)*maxrho+mAbs(rho_idx))]++;

/*if (rho_idx<maxrho && rho_idx>0) {

Acc[angle*maxrho+rho_idx]++;


AccMax = Acc[angle*maxrho+rho_idx];

}

}*/

}

}

ctr += 2;

}

// Draw Hough lines

// Case theta = 0


if (Acc[rho_idx] > vote) {

rho = (Int32)(rho_idx<<1) - maxrho;

for(y=rho; y<TAILLE; y+=largeur) {

out[y]=255;

}

}

}

// Others angles

ctr = maxrho;



if (Acc[ctr++] > vote) {


rho = (Int32)(rho_idx<<1) - maxrho;


y = (Int32)(((double)rho -

(double)x*cos(angler))/sin(angler)+0.5);


#ifdef GREY

out[y*largeur+x]=0;

#else


#endif

}

}

}

}

}

free(Acc);

}

Hough.c

Ch

apit

re :

Co

de

41


/* T. Jacquemin & M. Marleix :

Version 3 qui fait acquisition YUV puis seuillage puis affichage

*/

#include <std.h>

#include <stdlib.h>

#include <gio.h>

#include <log.h>

#include "psp_vpfe.h"

#include "psp_vpbe.h"

#include "fvid.h"

#include "psp_tvp5146_extVidDecoder.h"

#include <IMG_sobel.h>

#include <soc.h>

#include <cslr_ccdc.h>

#include "projet.h"

//pour logger ce qui se passe avec log.h (voir DSPBIOS)

extern LOG_Obj trace; // BIOS LOG object

/* extrait de l'exemple EDMA3 :

// 48K L1 SRAM [0x10f04000, 0x10f10000), 0xc000 length

// 32K L1 Dcache [0x10f10000, 0x10f18000), 0x8000 length

// 128K L2 SRAM [0x10800000, 0x10820000), 0x20000 length

// 128M DDR2 [0x80000000, 0x88000000), 0x8000000 length are cacheable

*/

#define NO_OF_BUFFERS (2u)

// Global Variable Defined

static PSP_VPSSSurfaceParams *ccdcAllocFB[NO_OF_BUFFERS]={NULL};

static PSP_VPSSSurfaceParams *vidAllocFB[NO_OF_BUFFERS] ={NULL};

static FVID_Handle ccdcHandle;

static FVID_Handle vid0Handle;

static FVID_Handle vencHandle;

/*Pour stockage de l'image en niveaux de gris */

#define LARGEUR 300

#define HAUTEUR 200

#define NB_ELT LARGEUR*HAUTEUR

#define SEUIL 15

#define GAMMA 0.2

#define VOTES 10

//#define ALLOC_STATIC

#define ALLOC_DYNAMIC

static PSP_VPFE_TVP5146_ConfigParams tvp5146Params = {

TRUE, // enable656Sync

PSP_VPFE_TVP5146_FORMAT_COMPOSITE, // format

PSP_VPFE_TVP5146_MODE_AUTO // mode

};

Ch

apit

re :

Co

de

42


static PSP_VPFECcdcConfigParams ccdcParams = {

PSP_VPFE_CCDC_YCBCR_8, // dataFlow

PSP_VPSS_FRAME_MODE, // ffMode

480, // height

720, // width

(720 *2), // pitch

0, // horzStartPix

0, // vertStartPix

NULL, // appCallback

{

PSP_VPFE_TVP5146_Open, // extVD Fxn

PSP_VPFE_TVP5146_Close,

PSP_VPFE_TVP5146_Control,

},

0 //segId

};

static PSP_VPBEOsdConfigParams vid0Params = {

PSP_VPSS_FRAME_MODE, // ffmode

PSP_VPSS_BITS16, // bitsPerPixel

//PSP_VPBE_RGB_888, //ajout TG

PSP_VPBE_YCbCr422, // colorFormat

(720 * (16/8u)), // pitch

0, // leftMargin

0, // topMargin

720, // width

480, // height

0, // segId

PSP_VPBE_ZOOM_IDENTITY, // hScaling

PSP_VPBE_ZOOM_IDENTITY, // vScaling

PSP_VPBE_EXP_IDENTITY, // hExpansion

PSP_VPBE_EXP_IDENTITY, // vExpansion

NULL // appCallback

};

static PSP_VPBEVencConfigParams vencParams = {

PSP_VPBE_DISPLAY_NTSC_INTERLACED_COMPOSITE // Display Standard

};

#pragma DATA_SECTION( tSin, ".L1Buffer" )

double tSin[MAXTHETA+1];

#pragma DATA_SECTION( tCos, ".L1Buffer" )

double tCos[MAXTHETA+1];

#ifdef ALLOC_STATIC

#define EDMA3_CACHE_LINE_SIZE_IN_BYTES (128u)

//Buffer : imageIn






#pragma DATA_SECTION( imageIn, ".ExtBuffer" )

//#pragma DATA_ALIGN( imageIn, EDMA3_CACHE_LINE_SIZE_IN_BYTES );

Uint8 imageIn[NB_ELT];

Ch

apit

re :

Co

de

43


//Buffer : imageOut






#pragma DATA_SECTION( imageOut, ".ExtBuffer" )

//#pragma DATA_ALIGN( imageOut, EDMA3_CACHE_LINE_SIZE_IN_BYTES );

Uint8 imageOut[NB_ELT];

//Buffer : imageGrey






#pragma DATA_SECTION( imageGrey, ".ExtBuffer" )

//#pragma DATA_ALIGN( imageGrey, EDMA3_CACHE_LINE_SIZE_IN_BYTES );

Uint8 imageGrey[NB_ELT];

#endif

void start_boucle() {

PSP_VPBEChannelParams beinitParams;

PSP_VPFEChannelParams feinitParams;

GIO_Attrs gioAttrs = GIO_ATTRS;

PSP_VPSSSurfaceParams *FBAddr = NULL;

PSP_VPSSSurfaceParams *FBAddrimageOut = NULL;

Uint32 i,j,k,ctr,ctrCam;

Uint32 te,ts;

Uint32 numOfIterations = 10000;

Uint16 *pIn, *pOut;

#ifdef ALLOC_DYNAMIC

Uint8 *imageIn = (Uint8*)malloc(NB_ELT*sizeof(Uint8));

Uint8 *imageOut = (Uint8*)malloc(NB_ELT*sizeof(Uint8));

#ifdef GREY

Uint8 *imageGrey= (Uint8*)malloc(NB_ELT*sizeof(Uint8));

#endif

double *Gx = (double*)malloc(NB_ELT*sizeof(double));

double *Gy = (double*)malloc(NB_ELT*sizeof(double));

#endif

//Init CSL du DMA

edma3init();

// Create ccdc channel

feinitParams.id = PSP_VPFE_CCDC;

feinitParams.params = (PSP_VPFECcdcConfigParams*)&ccdcParams;

ccdcHandle = FVID_create( "/VPFE0", IOM_INOUT, NULL, &feinitParams,

&gioAttrs);

if ( NULL == ccdcHandle) {

return;

}

Ch

apit

re :

Co

de

44


// Configure the TVP5146 video decoder

if( FVID_control( ccdcHandle,

VPFE_ExtVD_BASE + PSP_VPSS_EXT_VIDEO_DECODER_CONFIG,

&tvp5146Params) != IOM_COMPLETED ) {

return;

} else {

for ( i=0; i < NO_OF_BUFFERS; i++ ) {

if ( IOM_COMPLETED == FVID_alloc( ccdcHandle, &ccdcAllocFB[i] ) ) {

if ( IOM_COMPLETED != FVID_queue(ccdcHandle, ccdcAllocFB[i] ) ) {

return;

}

}

}

}

// Create video channel

beinitParams.id = PSP_VPBE_VIDEO_0;

beinitParams.params = (PSP_VPBEOsdConfigParams*)&vid0Params;

vid0Handle = FVID_create( "/VPBE0", IOM_INOUT,NULL, &beinitParams,

&gioAttrs );

if ( NULL == vid0Handle ) {

return;

} else {

for ( i=0; i<NO_OF_BUFFERS; i++ ) {

if ( IOM_COMPLETED == FVID_alloc( vid0Handle, &vidAllocFB[i] ) ) {

if ( IOM_COMPLETED != FVID_queue( vid0Handle, vidAllocFB[i]) ) {

return;

}

}

}

}

// Create venc channel

beinitParams.id = PSP_VPBE_VENC;

beinitParams.params = (PSP_VPBEVencConfigParams *)&vencParams;

vencHandle = FVID_create( "/VPBE0", IOM_INOUT, NULL, &beinitParams,

&gioAttrs);

if ( NULL == vencHandle ) {

return;

}

//Allocation memoire et la structure qui contiendra l'image

FVID_alloc( ccdcHandle, &FBAddr );


//Initialisation des LUT du sinus et du cosinus

for( i = 0; i <= MAXTHETA; i++ ){

tSin[i] = sin((double)i*PI/MAXTHETA);

tCos[i] = cos((double)i*PI/MAXTHETA);

}

//BOUCLE ACQUISITION & COPIE & AFFICHAGE DES IMAGES

// 1)Acquisition



return;

}

// fin Acquisition

Ch

apit

re :

Co

de

45


pIn = (Uint16*)FBAddr->frameBufferPtr;

pOut = (Uint16*)FBAddrimageOut->frameBufferPtr;

// 2)Traitement


ctr = 0; ctrCam = 0;


for( k = 0; k < LARGEUR ; k++ ) {

imageIn[ctr++] = (Uint8) (pIn[ctrCam++] >> 8);

}

ctrCam += 720 - LARGEUR;

}

#ifdef GREY


#endif

// fin Sauvegarde

// b.1)Copie

/*

for( j = 0; j < NB_ELT; j++ ) {

imageOut[j] = imageIn[j];

}

*/

// fin Copie

// b.2)Filtre de Sobel

/*


//sobel(imageIn,imageOut,LARGEUR,HAUTEUR); //version 鬨ves

IMG_sobel(imageIn,imageOut,LARGEUR,HAUTEUR); //version pr魣ompil饍


LOG_printf( &trace, " Nbcycles = %u", te - ts );

*/

// fin Sobel




LOG_printf( &trace, " Nbcycles Deriche = %u", te - ts );


robertsG(imageOut, imageIn, LARGEUR, HAUTEUR, SEUIL, Gx, Gy);


LOG_printf( &trace, " Nbcycles Roberts = %u", te - ts );

#ifdef GREY


hough(imageIn, imageGrey, LARGEUR, HAUTEUR, VOTES, Gx, Gy, tSin,

tCos, trace);



Ch

apit

re :

Co

de

46


// c) Affichage du resultat



for( k = 0; k < LARGEUR ; k++ ) {

pOut[ctrCam++] = ((((Uint16)imageGrey[ctr++])<<8) | 0x0080);

}

ctrCam += 720 - LARGEUR ;

}

#else


hough(imageIn, imageOut, LARGEUR, HAUTEUR, VOTES, Gx, Gy, trace);



// c) Affichage du r鳵ltat



for( k = 0; k < LARGEUR ; k++ ) {

pOut[ctrCam++] = ((((Uint16)imageOut[ctr++])<<8) | 0x0080);

}

ctrCam += 720 - LARGEUR ;

}

#endif

// fin Affichage

// fin Traitement

//LOG_printf( &trace, " Affichage iteration = %u", i );

// 3)Affichage :

if ( IOM_COMPLETED != FVID_exchange( vid0Handle, &FBAddrimageOut ) )

{

return;

}

// fin Affichage

}

//FIN BOUCLE ACQUISITION & TRAITEMENT & AFFICHAGE DES IMAGES








}

free(imageIn);

free(imageOut);

#ifdef GREY

free(imageGrey);

#endif

free(Gx);

free(Gy);

// Delete Channels




return;

}

Fonctions.c

Documents

Rapport Projet IF4-ARCH