Compression d'image grace au VQ
et recherche de similarité entre deux images

preambule

• vous avez lu et vous avez tout compris : vous pouvez sauter la partie VQ
• vous avez lu et vous avez rien compris : allez, session de ratrapage

index

1. VQ
   1. Qu'est ce que le VQ ?
   2. Quantisons une image..
      1. tranformer les elements de l'image en vecteur a 12 dimensions
      2. calculer le codebook
      3. condition d'arrets
      4. compresser l'image
      5. choix de la pattern
      6. Resultat de la compression
      7. Performances
   3. Taille du codebook : que choisir ?
   
   
2. Recherche de similarité entre deux images
   1. introduction
   2. entropie marginale
   3. entropie jointe
   4. interpretation
   
   
3. Conclusion

1) VQ

1.1) Qu'est ce que le VQ ?

1.2) Quantisons une image

1.2.1) Tranformer les elements de l'image en vecteur à 12 dimensions

struct SQuant
{
	float data[12];
};

struct RGB
{
 unsigned char r,g,b;
}

int width,height;	//taille de l'image
RGB *bitmap		//pointeur vers ladite image

int widthQ  = width  / 2;
int widthQ  = height / 2;

SQuant * quant = new SQuant[widthQ   *heightQ  ];	// on a donc autant de SQuant que de block de 2x2 pixels
							// Attention ! ces SQuant ne sont pas notre codebook !
SQuant * tmpQuant = quant ;

for (int i = 0 ; i < height;i+=2)
{
	for (int j = 0 ; j < width;j+=2)
	{
		tmpQuant->data[0] = (float)bitmap[i][j].r;
		tmpQuant->data[1] = (float)bitmap[i][j].g;
		tmpQuant->data[2] = (float)bitmap[i][j].b
 
		tmpQuant->data[3] = (float)bitmap[i][j+1].r;
		tmpQuant->data[4] = (float)bitmap[i][j+1].g;
		tmpQuant->data[5] = (float)bitmap[i][j+1].b	
	
		tmpQuant->data[6] = (float)bitmap[i+1][j].r;
		tmpQuant->data[7] = (float)bitmap[i+1][j].g;
		tmpQuant->data[8] = (float)bitmap[i+1][j].b

		tmpQuant->data[9]   = (float)bitmap[i+1][j+1].r;
		tmpQuant->data[10]  = (float)bitmap[i+1][j+1].g;
		tmpQuant->data[11]  = (float)bitmap[i+1][j+1].b;
		tmpQuant++;
	}
}

1.2.2) calculer le codebook

struct SCodebookentry
{
  SQuant vector;
  SQuant sum;
  SQuant farthest;
  int  	nbhit;
  float	maxDistance;
 };

SCodebookentry *codebook = new SCodebookentry[codebookSize];
memset(codebook, 0, sizeof(codebook) * codebookSize);

float distance = sqrt( ( quant.data[0] - entry.vector.data[0])² + 
                      ( quant.data[1] - entry.vector.data[1])²  +
                       .....+( quant.data[11] - entry.vector.data[11])²);

for (int i=0;i< widthQ * heightQ;i++)
{
	float distance;
	SCodebookEntry *c = findClosest(quant+i,&distance);	//cherche le vecteur dans le codebook le plus proche
	c->nbHit++;						//augmente le nombre de "hit" dudit vecteur
	addVector( c->totalVector,quant[i]);			//et dans la foulée on ajoute le vecteur courant au champ
								//totalvector du codebookEntry choisi (expl later)
	
	if (c->maxDistance < distance)				//pour la suite on va aussi avoir besoin
	{							//du point le plus eloigne pour chaque codebookentry
		c->maxDistance = distance;			//donc la on en garde une trace, aussi
		c->farthest = quant[i];
	}
}

SCodebookEntry *  findClosest(SQuant * quant,float * distance)
{
	float distanceMin,tmpdistance;
	distanceMin =50000000 ;	//truc bidon, mais gros

	int index;

	for (int i=0;i< codebookSize;i++)
	{
		tmpDistance = vectorDistance(codebook[i].vector,quant);	//calcul la distance entre les deux vecteurs
		if (tmpDistance < distanceMin)				//si c'est plus proche....
		{
			distanceMin = tmpDistance;			//...alors on maj nos variables et 
			index = i;					//on stocke l'indice
		}
	}
	*distance = distanceMin;
	return codebookSize+index;
}

• trouver codebookentry qui correspond le plus
• ajouter le quant courant au codebook entry

for (int i=0;i < codebooksize;i++)
{	
	codebookEntry[i].vector = codebookentry[i].totalVector / codebookEntry[i].totalHit
}

for (int i=0;i < codebooksize;i++)
{	
	if (codebookEntry[i].nbhit != 0)
		codebookEntry[i].vector = codebookentry[i].totalVector / codebookEntry[i].totalHit;
	else
	{
		codebookEntry *q = findfarthest();
		codebookEntry[i].vector = q->farthest;
		q->distanceMax = 0;		//on remet a 0 histoire de disqualifier cette entree lors de potentielles recherches ulterieure
	}
}

1.2.3) Condition d'arret

1.2.4) Compresser l'image

1.2.5) Choix de la pattern

1.2.6)Résultat de la compression

1.2.7) Performances

__forceinline float vectorDistance3dnow(SQuant *src,SQuant *src2)
{

 _asm
 {
	mov eax,src;
	mov ecx,src2;

	//copie du premier quant dans les registres MMX / 3dnow
	movq mm0,[eax];
	movq mm1,[eax+8];
	movq mm2,[eax+16];
	movq mm3,[eax+24];
	movq mm4,[eax+32];
	movq mm5,[eax+40];

	//soustraction des deux vecteurs
	
	pfsub mm0,[ecx];
	pfsub mm1,[ecx+8];
	pfsub mm2,[ecx+16];
	pfsub mm3,[ecx+24];
	pfsub mm4,[ecx+32];
	pfsub mm5,[ecx+40];

	//mise au carre
	pfmul mm0,mm0;
	pfmul mm1,mm1;
	pfmul mm2,mm2;
	pfmul mm3,mm3;
	pfmul mm4,mm4;
	pfmul mm5,mm5;

	//et addition de tout ca
	pfacc mm1,mm0
	pfacc mm2,mm1
	pfacc mm3,mm2
	pfacc mm4,mm3
	pfacc mm5,mm4
	pfacc mm5,mm5;
	movd eax,mm5
  }
}	

1.3) Taille du codebook : que choisir ?

2) Recherche de similarités entre deux images

2.1) Introduction

2.2) Entropie marginale

float value = 0;

for (int i=0;i < 256;i++)
{
  value += histo2d[i][0];
}

if (value)
{
 	float pX= value / (float)(width * heiht);
	HX -= pX*logf(pX);           		
}

    float HX=0;

    for (i = 0;i<256;i++)
    {
        float value=0;

        for (int j=0;j<256;j++)
            value+=lp2dHistogram[j][i];
  
        if (value)
        {
 		float pX= value / (float)(width * height);
		HX -= pX*log(pX);           
        }
    }

2.3) Entropie Jointe

float HXY = 0.0f;

for (i = 0;i<256;i++)
{
    for (int j=0;j<256;j++)
    {
       float value=(float)lp2dHistogram[i][j];
        
       if (value)
       {
         float pXY= value / (float) (width * height);
         HXY -= pXY*log(pXY);           
       }
    }
}

float result = (HX + HY) / HXY;

2.4) Interpretation

entropie = 0;
codebooksize = 64;

tant que entropie < 1.3

compresserVQ(codebookSize);
calculer entropie;
codebooksize * = 2;

fin tant

conclusion

thks a nico pour la relecture de cette doc