matching.cpp

这是一个用c++编写的实现指纹识别的程序

#include "stdafx.h"
#include "Matching.h"
#include "enhancement.h"
#include <math.h>

/* match
 * give the similarity value between tho minutae arrays
 */
float match1( int **minArr1, int minCount1, int **minArr2, int minCount2 ){

	int i,j, x, y, x2, y2;
	float value, thisValue, newValue, returnValue;
	int mean1x , mean1y, mean2x, mean2y;

	mean1x = mean1y = mean2x = mean2y =0;

	// find means
	for(i=0; i<minCount1; i++){
		mean1x += minArr1[i][0];
		mean1y += minArr1[i][1];
	}
	mean1x = mean1x / minCount1;
	mean1y = mean1y / minCount1;

	for(i=0; i<minCount2; i++){
		mean2x += minArr2[i][0];
		mean2y += minArr2[i][1];
	}
	mean2x = mean2x / minCount2;
	mean2y = mean2y / minCount2;



	// deviate arr1 my meandiff
	for(i=0; i<minCount1; i++){
		minArr1[i][0] -= (mean1x - mean2x);
		minArr1[i][1] -= (mean1y - mean2y);
	}

	value = 0;
	for( i=0; i< minCount1; i++){
		x = minArr1[i][0];
		y = minArr1[i][1];
		thisValue = 0;
		for( j=0; j< minCount2; j++){
			x2 = minArr2[j][0];
			y2 = minArr2[j][1];
			newValue = 1.0f / (float)( pow((x2 -x)*(x2 -x) + (y2 -y)*(y2 -y),0.2) +1);
			if( newValue > thisValue ) 
				thisValue = newValue;
		}
		value += thisValue;
	}
	returnValue = value / minCount1;

	value = 0;
	for( i=0; i< minCount2; i++){
		x = minArr2[i][0];
		y = minArr2[i][1];
		thisValue = 0;
		for( j=0; j< minCount1; j++){
			x2 = minArr1[j][0];
			y2 = minArr1[j][1];
			newValue = 1.0f / (float)( pow((x2 -x)*(x2 -x) + (y2 -y)*(y2 -y),0.3) +1);
			if( newValue > thisValue ) 
				thisValue = newValue;
		}
		value += thisValue;
	}
	returnValue += value / minCount2;

	return (returnValue * 50.0f );
}

/* match3
 * based on quad tree
 */

struct SQuad{
	int score[4]; // scores for 4 quaderants
	int pos[2];
	SQuad *quad[4];
};


/* make quad tree
 *		q2	|	q1
 *		-----------
 *		q3	|	q4
 */
SQuad* makeQuadTree( int **minArr, int minCount, int xf, int yf, int xt, int yt){

	int i, j, temp;
	int centerx, centery;
	int myArr[400];
	int myArrCount = 0;

	// select the valid minutaes
	for( i=0; i<minCount; i++){
		if( minArr[i][0] > xf && minArr[i][0] < xt && minArr[i][1] > yf && minArr[i][1] < yt )
			myArr[myArrCount++] = i;
	}

	if( myArrCount == 0)
		return NULL;

	SQuad *q = new SQuad;
	for(i=0; i<4; i++)
		q->quad[i] = NULL;

	// quad center is the median pixel in the region
	// sort the minutaes by x co-ordinates
	for( i=0; i<myArrCount; i++){
		for( j=i+1; j<myArrCount; j++){
			if( minArr[ myArr[i] ][0] > minArr[ myArr[j] ][0] ){
				temp = myArr[i];
				myArr[i] = myArr[j];
				myArr[j] = temp;
			}
		}
	}
	centerx  = minArr[ myArr[ (myArrCount)/2 ] ][0];
	centery  = minArr[ myArr[ (myArrCount)/2 ] ][1];

	// quad1 
	q->score[0] = 0;
	for( i=0; i<minCount; i++){
		if( minArr[i][0] > centerx && minArr[i][0] < xt && minArr[i][1] > yf && minArr[i][1] < centery )
			q->score[0]++;
	}
	q->quad[0] = makeQuadTree( minArr, minCount, centerx, yf, xt, centery);

	// quad2 
	q->score[1] = 0;
	for( i=0; i<minCount; i++){
		if( minArr[i][0] > xf && minArr[i][0] < centerx && minArr[i][1] > yf && minArr[i][1] < centery )
			q->score[1]++;
	}
	q->quad[1] = makeQuadTree( minArr, minCount,xf, yf, centerx, centery);

	// quad3
	q->score[2] = 0;
	for( i=0; i<minCount; i++){
		if( minArr[i][0] > xf && minArr[i][0] < centerx && minArr[i][1] > centery && minArr[i][1] < yt)
			q->score[2]++;
	}
	q->quad[2] = makeQuadTree( minArr, minCount, xf, centery, centerx, yt);

	// quad4
	q->score[3] = 0;
	for( i=0; i<minCount; i++){
		if( minArr[i][0] > centerx && minArr[i][0] < xt && minArr[i][1] > centery && minArr[i][1] < yt)
			q->score[3]++;
	}
	q->quad[3] = makeQuadTree( minArr, minCount, centerx, centery, xt, yt);

	return q;
}

float compareQuadTrees( SQuad *q1, SQuad *q2, int level){

	int i;
	float differance = 0.0f, returnVal = 0.0f;

	if( q1 == NULL || q2 == NULL )
		return 13.0f;

	for( i=0; i<4; i++){
		//differance += (abs( q1->score[i] - q2->score[i] )) * (level + 1 ) ;
		differance += pow( (abs( q1->score[i] - q2->score[i] )) , (level + 1 ) );
	}

	returnVal = 1/(differance * pow(4, level) + 1);

	for(i=0; i<4; i++ )
		returnVal += compareQuadTrees( q1->quad[i], q2->quad[i], level +1 );

	return returnVal;
}


float match3( int **minArr1, int minCount1, int **minArr2, int minCount2 ){

	SQuad *q1 = NULL, *q2= NULL;

	q1 = makeQuadTree( minArr1, minCount1 , 0, 0, 255, 255);
	q2 = makeQuadTree( minArr2, minCount2 , 0, 0, 255, 255);

	return compareQuadTrees( q1, q2 , 0) / (compareQuadTrees( q1, q2 , 0) + compareQuadTrees( q2, q2 , 0) ) * 200.0f;

}

float match2( int **thinArr1,int row1,int col1,int **thinArr2,int row2,int col2)
{
	int shiftX,shiftY,k,l;
	int roundScore=0;
	float maxScore=0,score=0;

	enhancement *enh = new enhancement();
	enh->Create(137,NULL);
	enh->SetWindowText(" Image Mapping ");
	enh->ShowWindow(SW_SHOW);
	enh->m_prog.SetRange32(0,100);

	for(shiftX=0;shiftX<row1;shiftX++)
	{
		
		for(shiftY=0;shiftY<col1;shiftY++)
		{
			enh->m_prog.SetPos(  float(shiftX*row1 + shiftY)/float(row1*col1)*100.0f );
			for(k=0;k<row2-shiftX;k++)
			{
				for(l=0;l<col2-shiftY;l++)
				{
					if(thinArr1[k+shiftX][l+shiftY]==1 && thinArr2[k][l]==1)
					{
						roundScore++;
					}
				}
			}

			score = (roundScore*100.0f);
			score = score/((row1-shiftX)*(col1-shiftY));
			roundScore=0;
			if(score > maxScore)
			{
				maxScore = score;
			}
		}
	}

	enh->DestroyWindow();
	//maxScore = (roundScore*100);
	//maxScore = maxScore/(row1*col1);
	return maxScore;
}

/* removeNoise
 * remove the noise minutae points from an array of 255x255
 */

// thickness of the noise region
// #define NOISE_THICKNESS 15

void removeNoise( unsigned char **arr,int NOISE_THICKNESS )
{

	int minx, maxx, miny, maxy;
	int i, j;

	minx = miny = 255;
	maxx = maxy = 0;

	// find min and max pts
	for( i=0; i<255; i++)
	{
		for( j=0; j<255; j++)
		{
			if(arr[i][j] == 1)
			{
				if( i<minx) minx = i;
				else if( i>maxx) maxx = i;
				if( j<miny) miny = j;
				else if( j>maxy) maxy = j;
			}
		}
	}

	// remove the noise of thickness NOISE_THICKNESS
	for(i=minx; i<minx+NOISE_THICKNESS; i++)
		for(j=0; j<255; j++)
			arr[i][j] = 0;
	for(j=miny; j<miny+NOISE_THICKNESS; j++)
		for(i=0; i<255; i++)
			arr[i][j] = 0;
	for(i=maxx; i>maxx-NOISE_THICKNESS; i--)
		for(j=0; j<255; j++)
			arr[i][j] = 0;
	for(j=maxy; j>maxy-NOISE_THICKNESS; j--)
		for(i=0; i<255; i++)
			arr[i][j] = 0;

}