第5卷　第2期中央民族大学学报(自然科学版)1996年　指纹与地图图像的处理Ξ安思危　王杨　吕宏伯(北京工业大学,北京100022)丁志海　金辉　马冬云　孙玉洁(中央民族大学,北京100081)摘 要 比较研究了指纹处理与地图处理的各种方法,提出了消除噪声的定向平均值滤波方法、图像二值化的神经网络方法、指纹特征提取方法、地图图元提取方法以及恢复灰值地图的3次样条插值多层迭加方法.关键词:　数字图像处理;指纹处理;地图处理11前 言 指纹处理和地图处理是数字图像处理中的两个课题[1,2],它们都有着丰富的内容和重要的应用.指纹和地图都是线画类图像,但是原始形态和处理目标不尽相同,对它们的处理既有共同点,也有差异.原始指纹图像是灰值图,处理目的是得到二值线画并提取图像特征供识别用,处理过程包括图像分割,去噪声,二值化,细化,特征提取;经扫描输入的地图已是由线条、文字和图形符号(统称图元)组成的图像,处理目的主要是压缩存储.因此,主要环节是细化和矢量化.另外,如果地图是等高线图,还需要由其恢复地形图即灰值图像.本文系统介绍各环节的实现方案和对多种算法的比较研究.在去噪声部分,我们提出了定向平均值滤波法,在二值化中提出了神经网络法,在地图处理中提出了区分图元方案和恢复地形图的合理方法.21指纹和地图图像处理方案211　图像分割　有256个灰度等级的原始图像分割步骤如下:(1)平滑　用每像素5×5邻域内的平均灰度代替中心点灰度.(2)二值化　作上图的灰度-频数直方图(双峰),以谷点灰度为阈值作二值化.(3)修补　用数学形态学[3]中的闭运算填补洞孔,用开运算消除边界毛刺.(4)分割　用二值图与原图像作“与”运算,结果使背景灰度为0而保留了原图像.(5)增强　作目标图像的灰度直方图,设其面积为S,求灰度值g1使0～g1段面积S1满Ξ本文1996年3月25日收到足S 1 S 小于阈值t (例如,t =0101),而0～g 1+1段面积S ′1使S ′1 S Εt ,同理取g 2(考虑g 2～255段),令g ′=tg ,tg 1+(g -g 1)[255+(g 2-g 1-255)t ](g 2-g 1),255-(255-g )t ,　0Φg Φg 1g 1<g <g 2g 2Φg Φ255 为使图像在视觉上比较柔和,再作一次线性变换g ″=28+200g ′ 255,将灰度变化范围限制在28到228之间.212　消除噪声　我们对以下各方法进行了比较研究和实验:(1)平均值滤波　取每像素的n ×n 窗口邻域,n =3,5,7,…,设其中灰度平均值为a ,当中心点灰度f (x ,y )满足 f (x ,y )-a <Ε(Ε是阈值)时用a 代替f (x ,y ).(2)最频值滤波　同上,但a 取窗口中各点灰度最频值.(3)中值滤波　同上,a 取各点灰度中值,这时也可用以(x ,y )为中心的十字形邻域.(4)频域滤波　对图像作F F T 后用低通滤波.以下两种方法属于数学形态学[3,4],(5)复合极值滤波　一维滤波有两种形式:极小极大顺序滤波:g mM (x )=m in n -k Φj Φn m ax j -k +1Φi Φj f (i )极大极小顺序滤波:g M m (x )=m ax n -k Φj Φn m in j -k +1Φi Φj f (i )n 为窗口宽度而k 是一定值,取上述两形式之一沿水平、铅直方向各作一次便完成二维滤波.(6)可分离中值滤波　设X 为平面点集,Β为结构元素,1<Λ(Β)=k <+∞,Λ(1)为点数,则x 关于Β的顺序形态变换定义为点集X ○Β={x Λ(x ∩Βδx )Εk -(k -1)p }p =0,1(k -1),…,1,Βδx 为将Β起点平移到x 后反射所得元素,X ○Β是Βδx 中至少含有X 的k -(k -1)p 个点的那些x 之集,设Β=Β1∪Β2,Β1⊥Β2,则对图像f 的可分离中值滤波定义为(f ○Β1)○Β2,p =015,例如,取Β1={(-1,0),(0,0),(1,0)},Β2={(0,-1),(0,0),(0,1)}或Β1={(-1,0),(0,-1),(0,0),(0,1),(1,0)},Β2={(-1,-1),(-1,1),(0,0),(1,-1),(1,1)}等.以上各方法对于指纹图像都不够理想,原因是图中线条细而密集,窗口大小不易选取.(7)模板匹配　用27个模板,每个模板为14×14的0-1图像,描述一种纹路(水平、铅直等).对每个像素,在其邻域上用各模板(原模板及其平移、旋转等)匹配,选出适配模板与原邻域进行“与”运算.本方法效果较好,为进一步改善效果,我们提出以下方法,它是模板匹配与平均值滤波的结合.(8)定向平均滤波　选8个方向,与x 轴夹角分别为k ×2215°,k =0,1,…,7,每次开10×10窗口,沿每方向计算相邻两像素灰度差绝对值累计和,取使和最小的方向为本窗口纹路方向v ,对窗口内每像素求过该点沿v 的各点灰度平均值,用以取代该点原灰度值,然后,将窗口平移6行(列),已经平滑的像素保留在新的窗口中.本方法既消除了孤立噪声,又平滑了线条边界,获得了满意的效果.213　灰值图像二值化721　第2期安思危等:指纹与地图图像的处理我们比较研究了以下各种方法:(1)固定阈值法　当f (x ,y )<t 时将f (x ,y )变为0,否则将f (x ,y )变为255,t 是给定的阈值.(2)P ——参数法　由参数p 确定t (例如通过灰度直方图),p 表示目标子图像所占面积比例,对指纹图像可取p ≈50◊.(3)灰度直方图法　取灰度直方图谷点灰度为t .(4)微分直方图法　用3×3L ap lacian 算子对原图像进行处理后,再用P ——参数法二值化,对指纹图像p ∈[019,1].(5)灰度差直方图法　作(x ,y )的邻域A ,设(x ′,y ′)是A 中任意点,记∆=f (x ,y )-f (x ′,y ′),分别求d 1=6∆>0∆和d 2=6∆>0 ∆ ,分别作d 1,d 2值直方图并取其峰值点对应灰度值t 1,t 2,最后取阈值t =t 1+t 22.(6)熵方法[5]　作原图像灰度直方图,求灰度t ′使0～t ′-1段对应的直方图面积S ″ΦS 2而0～t ′段对应面积S ′>S 2,S 是直方图总面积,计算熵a ′=6g <t ′(h (g ) log 2h (g ))6g <255(h (g ) log 2h (g ))g 是灰度值,h (g )是对应于g 的频数.取a =S ′- S ′-a ′ ,求阈值t 使0～t 段直方图面积>a ,0～t -1段对应面积Φa .(7)判别分析法[6]　设全体像素灰度均值m t ,用阈值k 将图像二值化为两类时,第i 类像素个数、灰度均值和方差分别为Ξθi (k ),m i (k ),∆i (k ),i =1,2,则类内方差∆2Ξθ=62i =1Ξθi ∆2i ,类间方差∆2B =62i =1Ξθi (m i -m t )2=Ξθ1Ξθ2(m 1-m 2)2,求k 使∆2B 或∆2B ∆2Ξθ最大,取k 为阈值t .以上各方法中,执行效果以2,3,6较好,但各方法都未摆脱对一维灰度空间分类的局限.为实现在高维空间的非线性分类,我们提出以下的神经网络方法,网络采用多层前向模型和误差反向传播学习算法[7],输入分量n I =4,输出分量n 0=1,隐层数为1,隐层神经元个数据经验取n H =(8n I +n 0)2=16.4个输入分量分别选取如下:g 1——(x ,y )的3×3邻域中各点灰度平均值,g 2—7×7邻域除去3×3邻域后所余点灰度平均值,g 3—9×9邻域中过(x ,y )沿纹路方向v (见212(8))各点灰度平均值,g 4—同上,沿两侧各点灰度平均值.取g 1,g 2的目的为减少残存噪声影响,取g 3,g 4旨在突出小范围内纹路性质和目标与背景差别,各输入值均经归一化使之在[0,1]内变化.输出值范围为[-0.5,0.5],先将取值在[-0.5,-0.25],[0.25,0.5]范围内的像素二值化:两种情况分别对应于0,255,其它点灰度不变,对所得图像再作一次分类并以0为阈值对全图二值化.训练样本取400个像素,目标点、背景点各占一半,取自已经分割但尚未去噪声的图像,在486型机、Q u ick C 环境下训练时间约两小时,迭代350次,绝对误差总和Ε<010001,测试图像共七幅,测试结果对七幅图像均优于上述其他方法.214　细化与矢量化821中央民族大学学报(自然科学版)第5卷　本文不采取在灰度图上的细化方法,例如[8],以防在二值化时损失信息.二值图像细化算法中,H ild tch 法、D eu tch 法、R osenf eld 的8连通法、P av lid is 的经典方法和异步细化法、Z hang 的快速并行法、N accache 的S P TA 法等结果都可满足要求:保持线条形状特征,使细化后的线条为连通,不使笔画断开,不去掉端点和节点,在去掉上下(左右)边缘时不去掉左右(上下)角点,后几项要求是出于图元中不可能有文字和符号.本文所采取的方法之一是设某点灰度为p 1而3×3邻域中各点灰度排列如下:p 9p 2p 3p 8p 1p 4p 7p 6p 5其中每p i =0或1.作两次迭代,第一次迭代中当且仅当同时满足以下条件时将删去(变为0):(1)　2<Β(p 1)Φ6,(2)　A (p 1)=1,(3)　p 2 p 4 p 6=0,(4)　p 4 p 6 p 8=0,A (p 1)为序列p 2p 3…p 9中出现序偶01的个数,Β(p 1)为p 1的灰度非0邻点数.在第二次迭代中(1),(2)不变,(3),(4)分别改为(3′)p 2・p 4・p 8=0和(4′)p 2・p 6・p 8=0.不断重复上述过程直到图像中不再有可删去点.采用本文的去噪声和二值化方法,细化后不会出现断线,但需要消除短线和小回路:(1)去短线:从每个端点开始跟踪线条并记录长l ,若在l <l t 时达到另一端点或分支点,则消除被跟踪的线,否则停止跟踪.(2)去一分支点的小回路:从每分支点出发跟踪,若在l <l t 时达到出发点,则消除被跟踪线.(3)去两分支点的小回路:两个分支点间有两条路,删去较长的一条.(4)去三个分支点的小回路:从三个分支点A ,B ,C 出发分别向回路外跟踪一定长找到对应三点A ′,B ′,C ′,若A ′,B ′是三点中距离最短的两点,则删除A ,B 间的线条,其他情况同理.下一步是通过跟踪实现矢量化:(1)从上到下,从左到右找到线上一点p ,记录p 的位置并将p 的灰度置0.(2)以p 为当前点按F ree m an 链码搜索找到下一灰度非0点,作为新的当前点.(3)若已找到p ,p ′而当前点是p ″,检查pp ′,p ′p ″链码方向.若方向相同,只需将p ′灰度置0,否则要记录p ′位置后再将其灰度置0.(4)重复执行(2)和(3)直到无法再进行:当前点是端点、边界点或者出发点(闭曲线),记录末端.(5)重复执行(1)到(4)直到全部点灰度已为零.这时整幅图像已用矢量形式压缩存储完毕.跟踪时的两个技巧是:第一、开始前对图像加一边框,其上各点灰度置零,以避免对边界点的特殊判断.第二、对每当前点经常不必判断全部8个邻点.例如,由p 出发找到p ′后,p ′的某些方向的邻点不必再检查,因为它们分别是p 和已被检查过的点.以上是指纹和地图处理中的主要环节.921　第2期安思危等:指纹与地图图像的处理31特殊问题的讨论311　指纹特征提取　指纹分为平斗、左箕、右箕等七类,第一类又分18小类.指纹分析可使用树状自动机、神经网络等工具.提取特征时首先应找出特殊像素即端点、分支点和桥.由此,特征提取转化为寻找端点和分支点,因为桥由两个分支点构成.考虑线上任意—点p的3×3邻域,其中只有一个非0点时p为非特征点,恰有三个非0点时p是分支点.还应注意,不要把指纹图像边界上的端点当做特征点.对每个端点考虑一适当的方形邻域并统计其中灰度非0的点数n,只有当n大于阈值时被考虑点才是指纹内的端点而不是边界点.312　地图中文字与符号处理　对地图中的图元处理顺序为:符号(图标、图例)、文字、线条.处理结果是记录它们各自所在的位置.(1)符号处理:因为符号形状已知且有限,可用模板匹配进行提取.用一模板从上到下,从左到右遍历图像并计算被覆盖部分图像与模板的相似度R,当R大于某阈值时记录此位置,并从图像中删除对应子图像.当然,对多个模板应取使R最大的一个.图像f与模板t的距离平方为d2(△x,△y)=6[f(x,y)-t(x-△x,y-△y)]26指6m△x=-m6n△y=-n,展开d2并忽略6t2(x-△x,y-△y)(常数)和6f2(x,y)(近似于常数)得到相似度公式R(△x,△y)=6f(x,y)t(x-△x,y-△y) 然后除以6t(x,y)使之归一化,阈值通常取017到019间的数.(2)文字处理:文字主要指汉字,统计各汉字笔划和“笔段”(例如,笔划“乙”分解为4笔段),GB2312280的6763个汉字中笔段数不少于7的字数约占97◊,因此可用每像素邻域中灰度非0点个数作为区分汉字与线条的依据.本项研究只限于提取和存储文字,所以,当文字倾斜或彼此粘连时都不影响提取.例如,沿某方向倾斜和彼此粘连的一串字经提取后留下的是沿同方向分布、彼此可相交的一串窗口,标志字的位置.313　由等高线地图恢复灰值地图　已知图中各等高线和高程,要求由此求出图中每点高程,从而得到表示地形的灰值图.(1)8方向加权平均:从(x,y)出发沿8方向搜索直到找到最近控制点,设第i控制点高程为f i,到(x,y)距离为r i,则(x,y)点高程估计为f(x,y)=67i=0f i r2i 67i=01r2i 本方法精度不高,特别,在一封闭等高线内各点高程相等,所以不能正确地描述峰或谷.需要注意,沿4个倾斜方向搜索时对扫描线上每点要同时考虑其两邻点.例如,沿45°搜索时对每(x′,y′)要考虑(x′+1,y′)和(x′,y′+1),以防止出现穿等高线而过的情况.(2)3次样条插值:对任y沿水平方向扫描得n+1个控制点,x0<x1<…<x n,用3次031中央民族大学学报(自然科学版)第5卷　样条插值求线上其他点高程,插值函数S (x )满足(1)在[x j ,x j +1]上为3次多项式,记作S j (x ),j =0,1,…,n -1;(2)S j (x )=f j ,j =0,1…,n ,f j 为(x j ,y )点高程;(3)S (k )j (x j +1)=S (k )j +1(x j +1),j =0,1,…,n -2,k =0,1,2;(4)自由边界条件S ″(x 0)=S ″(x n )=0.S (x )的解法可见[16],[17].x 0,x n 是边界点,没有等高线通过时用8方向加权平均求高程估计值(只需取3或5方向).不断改变y 求出所有点高程,还可沿不同方向扫描插值并进行多层面叠加,结果更为精确.(3)双线性Β样条有限元法:插值函数为5(x ,y )=6n x i =16n yj =1f ij (x i ,y j )5i (x )5j (y )5i (x )在[x i -1,x i +1]上为两个线段(x i -1,0),(x i ,1)和(x i ,1),(x i +1,0),在区间外为零函数,5j (y )同理.问题归结为解Π=6sk =1v 2k p k +6n x -1i =26n y j =1v 2x (x i ,y j ) p s +6n x i =16n y -1j =2v 2y (x i ,y j ) p s =m in 其中v k =6i 6j f ij 5i (x k )5j (y k )-h k 表示点k 处计算高程与测量高程之差,v x (x i ,y j )为(x i ,y j )处函数沿x 方向曲率,v y 同理,p k ,p s 为权值,求解过程见[18]～[20].经比较,方法(2)精度较高而且计算较为方便.作者感谢中国科学院遥感技术研究所朱重光、郭军和中央民族大学张成国等教授的指导.参考文献[1]　徐建华,图像处理与分析,北京:科学出版社,19921[2]　林春蔚等,C 环境下地图图像矢量化及图形编辑技术实例,北京:海洋出版社,19931[3]　唐常青、吕宏伯、张方、黄铮,数学形态学方法及应用,北京:科学出版社,19901[4]　吴敏金,图像形态学,上海科技大学出版社1[5]　T .Pun ,“En trop ic T h resho lding ,A new A pp roach ”,CG IP V o l .16,pp .210-239,19811[6]　大津展之,“判别および最小2乘基准た基づく自动しきら值选定法”,电子通信学会论文志(D ),J 63-D ,4,pp .349-356,19801[7]　何明一,神经计算原理、语言、设计、应用,西安电子科技大学出版社.[8]　横井,岛胁,福村,“标本化された二值图形の … ⁄ な性质にについご”,电子通信学会论文志(D ),J 56-D ,N o .11,pp .662-669,1973.[9]　H ildtch ,C .J .,L inear akeleton s from square cupboards ,M ach ine In telligence I V ,B .M eltzer ,U nversity P ress ,Edinbu rge ,1969.[10]　D eu tch ,E .S .,T h inn ing algo rithm s on rectanglu lar ,hexagonal ,and triangu lar arrays ,Comm un ica 2ti on s of A C M ,15,9,1972.[11]　Stefanelli ,R .and Ro senfelid ,Som e parallel th inn ing algo rithm fo r digital p ictu res ,J .A ssoc .Compu t .M arch .,18,2,1971.[12]　T .Pavlidis ,计算机图形显示和图像处理的算法,北京:科学出版社,19871[13]　T .Y .Zhang and C .Y .Suen ,“A Fast parallel A lgo rithm fo r T h inn ing D igital’Pattern s.”,CA C M 27,N o .3,pp .236-239,1984.[14]　N .J .N accache and R .Sh inghal ,“SPTA :A p ropo sed algo rithm fo r th inn ing b inarypattern s ”,IEEE T ran s .on System s ,M an ,and Cybernetics ,V o l .S M C -14,N o .3,pp .409131　第2期安思危等:指纹与地图图像的处理231中央民族大学学报(自然科学版)第5卷　-418,1984.[15]　阮秋琦,数字图像处理基础1北京:中国铁道出版社.[16]　袁奇荪,计算几何造型学基础1北京:航空工业出版社,19871[17]　孙家永日,样条函数与计算几何,北京:科学出版社,19821[18]　战同胜,数值与计算,大连理工大学出版社,19911[19]　徐萃薇,计算方法引论,北京:高等教育出版社,19851[20]　柯正谊,数字地面模型,北京:中国科学技术出版社,19931 The Processi ng for F i nger-pr i n ts　and M aps I magesA n　Si w ei W ang　Yang L u　Hongbuo(B eij ing P oly technic U niversity,B eij ing100022)D ing　Zh ihai J in　H u i M a　Dongyun Sun　Yu jie(Central U niversity f or N ationalities,B eij ing100081)Abstract A fter comparing and studing m any m ethods u sed in finger2p rin ts and m ap s p rocessing,th ispaper p resen ts som e new m ethods as fo llow s:1T he o rien tati on average filter to remove no ise,1N eu ral netw o rk fo r i m age b inary,1T he ex tracti on of finger2p rin ts characters,1T he ex tracti on of the m ap elem en ts,1T he cub ic sp line in terpo lati on m u ltilayer superpo siti on to resto re the grey level m ap s.Keywords:　digital i m age p rocessing;finger2p rin ts p rocessing;m ap s p rocessing。