如上图所示,经典的指纹比对算法
是先将指纹图像进行预处理
提取得到特征点,每个特征点有位置信息和方向信息
针对左右两个指纹图像对应的特征点集
不妨假设左边的指纹为L,右边的指纹为R
则L中的每个特征点,只能对应R上的一个特征点,或者是不存在对应的特征点
同理,R中的每个特征点,只能对应L上的一个特征点,或者不存在对应的特征点
我们称(Li,Rj)为对应特征点对,Li为L中的一个特征点,Rj为R中的一个特征点
如果(Li,Rj)和(Lp,Rq)存在如下冲突情况:
Li==Lp 或者Rj==Rq
即存在一个特征点对应两个不同的特征点的情况,需要进行去重。
如果(Li,Rj)和之前选定的点对(Lp,Rq)冲突,按如下规则进行去重:
如果Lp>Li 且 Rq>Rj, 则替换
#include <iostream> using namespace std; int n,m; int a[100],b[100]; int x,y,ans=0; int main() { scanf("%d%d",&n,&m); for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); if(a[x]<y && _____(1)______) { if(a[x]>0) b[a[x]]=0; if(b[y]>0) _____(2)______; a[x]=y; ______(3)_____; } } for(int i=1;_____(4)_____;i++) { if(a[i]==0) ++ans; if(______(5)_______) ++ans; } printf("%d\n",ans); return 0; }