第3卷第4期 智能系统学报 Vol 3 Ng 4 2008年8月 CAA I Transactions on Intelligent Systems Aug 2008 一种基于对数极坐标变换的快速目标 识别算法 严江江，丁明跃，周成平 (华中科技大学图像信息处理与智能控制教育部重点实验室，湖北武汉430074) 摘要：在目标识别的过程中，观察目标图像相对于基准目标图像会存在尺度、方向和位置的变化，使得识别速度和 准确率降低.针对这一问题，提出了一种快速对数极坐标变换算法，加快了从笛卡儿坐标转换到对数极坐标的过程。 通过采用双轴投影相似度分析算法对目标图像进行匹配，进一步加快了识别速度，同时保证了匹配的可靠性.理论 分析和试验结果表明，该算法在计算效率和目标识别正确率方面具有较好的性能 关键词：对数极坐标变换；目标识别；图像匹配，快速变换 中图分类号：TP391.4文献标识码：A文章编号：16734785(2008)04037007 A fast target recogn ition a lgorithm based on LPT YAN Jiang-jiang,D ING M ing-yue,ZHOU Cheng p ing (State Education Comm ission Key Lab for mage Processing and Intelligent Control,Huazhong University of Science and Technolgy, W uhan 430074,China) Abstract:In the course of target recognition,recognition peed and accuracy decreases if the scale,orientation and position of the target mage changes with respect to the reference mage This paper presents a fast lg polar trans- fomation (LPT)algorithm,which speeds up processing fiom Cartesian coordinates to log polar coordinates as well as speeding up mage matching by using a dual-axis pojection algorithm.The new algorithm greatly accelerates tar get recognition and ensures the reliability ofmatches Theoretical analysis and experments showed that thismethod has better perfomance in both recognition speed and accuracy Keywords:bgpolar transfomation;target recognition;mage matching fast transfomation 在图像处理领域，目标识别是一项极其重要的 transfomation,LPT)可以解决这个问题.对数极坐标 研究内容，其应用包括机器视觉、成像制导和文字识 变换源于人类视觉中视网膜皮层映射关系的研 别等.一般的目标识别过程是计算观察图像与基准 究]，人们将其广泛应用于目标识别、目标跟踪、 图像的相似度，这种方法称之为模板匹配”通常 运动检测、脸部检测等领域3)笛卡儿坐标系下目 情况下目标图像相对于基准目标图像会发生尺度、 标的尺度和旋转变化映射到对数极坐标系，表现为 方向、位置的变化，通过对数极坐标变换(log-polar 目标区域的水平和垂直方向的平移，而目标的轮廓 收稿日期：2007-12-19 区域保持不变.利用这种特性可以对目标进行匹配 基金项目：国家自然科学基金重点资助项目(60135020FF030405). 通信作者：严江江.Email yisaltriver@yahoo com.cn 和识别， 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
第 3卷第 4期 智 能 系 统 学 报 Vol. 3 №. 4 2008年 8月 CAA I Transactions on Intelligent System s Aug. 2008 一种基于对数极坐标变换的快速目标 识别算法 严江江 ,丁明跃 ,周成平 (华中科技大学 图像信息处理与智能控制教育部重点实验室 ,湖北 武汉 430074) 摘 要 :在目标识别的过程中 ,观察目标图像相对于基准目标图像会存在尺度、方向和位置的变化 ,使得识别速度和 准确率降低. 针对这一问题 ,提出了一种快速对数极坐标变换算法 ,加快了从笛卡儿坐标转换到对数极坐标的过程. 通过采用双轴投影相似度分析算法对目标图像进行匹配 ,进一步加快了识别速度 ,同时保证了匹配的可靠性. 理论 分析和试验结果表明 ,该算法在计算效率和目标识别正确率方面具有较好的性能. 关键词 :对数极坐标变换 ;目标识别 ;图像匹配 ;快速变换 中图分类号 : TP391. 4 文献标识码 : A 文章编号 : 167324785 (2008) 0420370207 A fast target recogn ition algor ithm based on LPT YAN Jiang2jiang, D INGM ing2yue, ZHOU Cheng2p ing ( State Education Comm ission Key Lab for Image Processing and Intelligent Control, Huazhong University of Science and Technology, W uhan 430074, China) Abstract: In the course of target recognition, recognition speed and accuracy decreases if the scale, orientation and position of the target image changes with respect to the reference image. This paper p resents a fast log2polar trans2 formation (LPT) algorithm, which speeds up p rocessing from Cartesian coordinates to log2polar coordinates as well as speeding up image matching by using a dual2axis p rojection algorithm. The new algorithm greatly accelerates tar2 get recognition and ensures the reliability of matches. Theoretical analysis and experiments showed that thismethod has better performance in both recognition speed and accuracy. Keywords: log2polar transformation; target recognition; image matching; fast transformation 收稿日期 : 2007212219. 基金项目 :国家自然科学基金重点资助项目 (60135020FF030405). 通信作者 :严江江. E2mail: yjsaltriver@yahoo. com. cn. 在图像处理领域 ,目标识别是一项极其重要的 研究内容 ,其应用包括机器视觉、成像制导和文字识 别等. 一般的目标识别过程是计算观察图像与基准 图像的相似度 ,这种方法称之为“模板匹配 ”. 通常 情况下目标图像相对于基准目标图像会发生尺度、 方向、位置的变化 ,通过对数极坐标变换 ( log2polar transformation,LPT)可以解决这个问题. 对数极坐标 变换源于人类视觉中视网膜皮层映射关系的研 究 [ 122 ] ,人们将其广泛应用于目标识别、目标跟踪、 运动检测、脸部检测等领域 [ 325 ] . 笛卡儿坐标系下目 标的尺度和旋转变化映射到对数极坐标系 ,表现为 目标区域的水平和垂直方向的平移 ,而目标的轮廓 区域保持不变. 利用这种特性可以对目标进行匹配 和识别
第4期 严江江，等：一种基于对数极坐标变换的快速目标别算法 ·371· 通常目标识别算法在速度上都有很高的要求 r In(),0 arctan(y/x).(1) 本文提出了一种新的快速LPT算法，通过减少采样 由于图像是离散栅格化表示的，原图像的像素直接 点数目和采用查找表方法来减少运算量.在此基础 生成对数极坐标LP)图像的输出像素，这无法保证 上进一步提出了一种双轴投影相似度分析算法对目 LP图像的像素都能被映射到.本文采用间接重采样 标进行匹配识别，通过统计轴向投影量将二维图像 法61来获得LP图像 的匹配识别转换为一维的轴向投影匹配识别，可同 首先设定LP图像的大小，然后计算LP图像中 时获得较高的计算效率和较好的正确识别率 的点(：)映射到原图像中的点坐标(x以，其计算 1快速识别算法及其实现 公式为 x=ep(y·cos0,y=ep(y·sin0,2) 笛卡儿坐标系中的点(x,以映射到对数极坐标 最后将(xy以的值取整后赋给(x): 系中的点(r)的计算公式为 (a)原图像 b)LP图像 (©)原图像采样点图 图1原始目标图像及其LP图像以及构造LP图像的原图像采样点图 Fig I Input mage,bgpolar mage,and sampling points of input mage to construct the bogpolar mage 本文只针对二值图像进行处理.从图1(c)中 ξ=o·R (5 看到，极坐标原点处的采样最为密集，采样密度沿中 如果w=05有S=M5=M,这时号=R2. 心向外围递减，这样LP图像对目标的平移将会相 即LPT的运算量减少了一半.实际应用中，S需要计 当敏感.将采样原点取在目标形心的位置来消除目 算才能得到，但基准图的S是预先知道的，可以通过 标平移的影响，物体形心的确定参见文献[7]图1基准图的S估算出的值.考虑到图像是栅格化表 (b)中黑白相间的地方就是图1(a)中目标轮廓区 示，(：)为LP图中整数值的坐标，而LP图像的大 域在LP平面的映射.在LP图像中，往往只对目标 小是事先确定的，则每次计算的输入参数和结果也 轮廓感兴趣，因为它反映了目标的形状，而对靠近采 是确定的.如果事先使用一个表来记录式2)中的 样原点的图像部分则不感兴趣.如果对靠近采样原 输入参数和结果，在以后计算的过程中就只需要通 点的区域不采样或者少采样，就可以减少LPT的运 过输入参数来查找表中对应的结果即可，这样式 算量.因此，只对满足式(3)的点作式(2)的变换. (2)中复杂的自然幂函数和三角函数运算就转换成 r≥ 3) 了读取内存地址中内容的操作相当于加法运算， 以R代表LP图距离轴长度，M表示原图像中 这将大大加快获得LP图像的速度 离采样原点最远的距离，S表示目标边界离采样原 由于极坐标原点取在目标的形心位置，消除了 点最近的距离，则通过式(4)确定： 目标平移的影响，因此只需要考虑目标发生尺度和 专=n 旋转变化的情况.极坐标系下的点(P,)转换到对 ·R 4) In(M) 数极坐标下的对应点为(x),即r=n(P以.设目标 令S=”,其中0≤w<1,则式(4)可写成： 的尺度变化因子为k旋转变化因子为中，则(：)发 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
通常目标识别算法在速度上都有很高的要求 , 本文提出了一种新的快速 LPT算法 ,通过减少采样 点数目和采用查找表方法来减少运算量. 在此基础 上进一步提出了一种双轴投影相似度分析算法对目 标进行匹配识别 ,通过统计轴向投影量将二维图像 的匹配识别转换为一维的轴向投影匹配识别 ,可同 时获得较高的计算效率和较好的正确识别率. 1 快速识别算法及其实现 笛卡儿坐标系中的点 ( x, y)映射到对数极坐标 系中的点 ( r,θ)的计算公式为 r = ln ( x 2 + y 2 ) ,θ = arc tan ( y / x). (1) 由于图像是离散栅格化表示的 ,原图像的像素直接 生成对数极坐标 (LP)图像的输出像素 ,这无法保证 LP图像的像素都能被映射到. 本文采用间接重采样 法 [ 6 ]来获得 LP图像. 首先设定 LP图像的大小 ,然后计算 LP图像中 的点 ( r,θ)映射到原图像中的点坐标 ( x, y) ,其计算 公式为 x = exp ( r) ·cosθ, y = exp ( r) ·sinθ, (2) 最后将 ( x, y)的值取整后赋给 ( r,θ). 图 1 原始目标图像及其 LP图像以及构造 LP图像的原图像采样点图 Fig. 1 Input image, log2polar image, and samp ling points of input image to construct the log2polar image 本文只针对二值图像进行处理. 从图 1 ( c)中 看到 ,极坐标原点处的采样最为密集 ,采样密度沿中 心向外围递减 ,这样 LP图像对目标的平移将会相 当敏感. 将采样原点取在目标形心的位置来消除目 标平移的影响 ,物体形心的确定参见文献 [ 7 ]. 图 1 ( b)中黑白相间的地方就是图 1 ( a)中目标轮廓区 域在 LP平面的映射. 在 LP图像中 ,往往只对目标 轮廓感兴趣 ,因为它反映了目标的形状 ,而对靠近采 样原点的图像部分则不感兴趣. 如果对靠近采样原 点的区域不采样或者少采样 ,就可以减少 LPT的运 算量. 因此 ,只对满足式 (3)的点作式 (2)的变换. r ≥ξ. (3) 以 R 代表 LP图距离轴长度 , M 表示原图像中 离采样原点最远的距离 , S 表示目标边界离采样原 点最近的距离 ,则 ξ通过式 (4)确定 : ξ = ln (S ) ln (M ) ·R. (4) 令 S =M ω ,其中 0≤ω < 1,则式 (4)可写成 : ξ =ω·R. (5) 如果 ω = 0. 5,有 S =M 0. 5 = M ,这时 ξ= R /2, 即 LPT的运算量减少了一半. 实际应用中 , S需要计 算才能得到 ,但基准图的 S是预先知道的 ,可以通过 基准图的 S估算出 ξ的值. 考虑到图像是栅格化表 示 , ( r,θ)为 LP图中整数值的坐标 ,而 LP图像的大 小是事先确定的 ,则每次计算的输入参数和结果也 是确定的. 如果事先使用一个表来记录式 ( 2)中的 输入参数和结果 ,在以后计算的过程中就只需要通 过输入参数来查找表中对应的结果即可 , 这样式 (2)中复杂的自然幂函数和三角函数运算就转换成 了读取内存地址中内容的操作 (相当于加法运算 ) , 这将大大加快获得 LP图像的速度. 由于极坐标原点取在目标的形心位置 ,消除了 目标平移的影响 ,因此只需要考虑目标发生尺度和 旋转变化的情况. 极坐标系下的点 (ρ,θ)转换到对 数极坐标下的对应点为 ( r,θ) ,即 r = ln (ρ). 设目标 的尺度变化因子为 k,旋转变化因子为ψ,则 ( r,θ)发 第 4期 严江江 ,等 :一种基于对数极坐标变换的快速目标别算法 ·371·
·372· 智能系统学报 第3卷 生尺度和旋转变化后的对应点为(，0)，可由式 N (6)计算得到： =2a助 r'=In(k.p)In(k)In(p)In(k)+r. =,明 (7) 0’=0+ 6) 0,f入，)=0 可以看出，目标的尺度变化相当于在距离轴上平移了 式中 L入，)= 1,f入，0)>0 n(k)个单位，而目标的旋转变化相当于在角度轴上 入∈1,2，R,0∈f1,2,N} 平移了中个单位，图2清晰地表明了这种关系 式中：R、N分别代表LP图距离轴和角度轴长度 目标的识别通过LPT转化成LP图与基准LP图 f入，)为点八，)的值.在LP图中，目标轮廓右边 的目标轮廓的匹配问题.如果在一个场景中存在多个 距离轴投影统计量为0，而目标轮廓左边距离轴投 待识别目标，则分别对每一个目标进行匹配识别即 影统计量为N,从距离轴最大值逆向开始计算距离 可.本文基准图为图1(a),基准LP图为图1(b),LP 轴投影，通过0和N这2个阈值就可以分割出目标 平面水平方向为距离轴方向，垂直方向为角度轴方 轮廓区域，分割完毕即停止计算.如图3所示，图3 向.为了减少目标轮廓提取的计算量，本文提出了一 (a)~(c)上半部分为距离轴投影曲线，下半部分为 种逆向距离轴投影分割方法，用T1和t。分别表示LP 通过计算投影统计量分割出来的目标轮廓区域： 图在距离轴和角度轴上的投影统计量. (a)尺度和旋转变化目标 6)目标放大1.5倍 (c)目标旋转90° 图像和非目标图像 (d)目标放大1.5倍并旋转225 (e)非日标图像 图2尺度和旋转变化对应的对数极坐标变换图 Fig 2 The LPT mage for object's scaling and rotating change 用经典相关匹配算法81是不能直接对分割出 则作下一步的相似度计算.其中，W。和W,分别为 来的目标轮廓区域进行比较的，需要作一些相应处 LP图和基准LP图的目标轮廓区域宽度，δ为先验 理.式2计算时存在坐标取整过程，目标尺度和旋 知识，本文中6取值为3为了对目标轮廓区域进行 转变化可能会造成目标轮廓区域的采样误差，造成 匹配分析并减少计算量，设计了双轴投影相似度分 分割出的宽度不一致，如果宽度相差过大，则直接判 析算法，首先用式(7)得到目标轮廓区域在距离轴 定不是目标.如果满足 和角度轴上的投影，再与基准LP图相应投影进行 |Wp·W,|≤8 8) 匹配分析.文献[9对距离轴投影进行相似度分析 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
生尺度和旋转变化后的对应点为 ( r′,θ′) , 可由式 (6)计算得到 : r′= ln ( k·ρ) = ln ( k) + ln (ρ) = ln ( k) + r, θ′=θ+ψ. (6) 可以看出,目标的尺度变化相当于在距离轴上平移了 ln ( k)个单位,而目标的旋转变化相当于在角度轴上 平移了ψ个单位,图 2清晰地表明了这种关系. 目标的识别通过 LPT转化成 LP图与基准 LP图 的目标轮廓的匹配问题. 如果在一个场景中存在多个 待识别目标 ,则分别对每一个目标进行匹配识别即 可. 本文基准图为图 1 ( a) ,基准 LP图为图 1 ( b) , LP 平面水平方向为距离轴方向,垂直方向为角度轴方 向. 为了减少目标轮廓提取的计算量,本文提出了一 种逆向距离轴投影分割方法,用τλ 和τθ分别表示 LP 图在距离轴和角度轴上的投影统计量. τλ = ∑ N θ=1 L (λ,θ) , τθ = ∑ R λ=1 L (λ,θ). (7) 式中 : L (λ,θ) = 0, f (λ,θ) = 0; 1, f (λ,θ) > 0. λ ∈ { 1, 2, …, R },θ∈ { 1, 2, …, N }. 式中 : R、N 分别代表 LP图距离轴和角度轴长度 , f (λ,θ)为点 (λ,θ)的值. 在 LP图中 ,目标轮廓右边 距离轴投影统计量为 0,而目标轮廓左边距离轴投 影统计量为 N,从距离轴最大值逆向开始计算距离 轴投影 ,通过 0和 N 这 2个阈值就可以分割出目标 轮廓区域 ,分割完毕即停止计算. 如图 3所示 ,图 3 ( a) ～( c)上半部分为距离轴投影曲线 ,下半部分为 通过计算投影统计量分割出来的目标轮廓区域. 图 2 尺度和旋转变化对应的对数极坐标变换图 Fig. 2 The LPT image for object’s scaling and rotating change 用经典相关匹配算法 [ 8 ]是不能直接对分割出 来的目标轮廓区域进行比较的 ,需要作一些相应处 理. 式 (2)计算时存在坐标取整过程 ,目标尺度和旋 转变化可能会造成目标轮廓区域的采样误差 ,造成 分割出的宽度不一致 ,如果宽度相差过大 ,则直接判 定不是目标. 如果满足 : | W p - W q | ≤δ, (8) 则作下一步的相似度计算. 其中 , W p 和 W q 分别为 LP图和基准 LP图的目标轮廓区域宽度 ,δ为先验 知识 ,本文中 δ取值为 3. 为了对目标轮廓区域进行 匹配分析并减少计算量 ,设计了双轴投影相似度分 析算法 ,首先用式 ( 7)得到目标轮廓区域在距离轴 和角度轴上的投影 ,再与基准 LP图相应投影进行 匹配分析. 文献 [ 9 ]对距离轴投影进行相似度分析 ·372· 智 能 系 统 学 报 第 3卷
第4期 严江江，等：一种基于对数极坐标变换的快速目标别算法 ·373· 就得出目标匹配的结果，虽然保证了运算量的降低， 在给定的阈值下不相似，则直接判定不是目标，相似 但不具有鲁棒性，因为仅仅由距离轴投影相似并不 则再比较角度轴投影.角度轴投影如图4所示 能完全说明图像的相似.本文首先判断距离轴投影， 80 6 60 6 40 20 20 04 20 40 60 40 60 80 20 40 60 (a)基准LP图目标轮廓 (b)图2(d)目标轮廊 (c)图2(e)目标轮廓 图3逆向距离轴投影分割方法 Fig 3 The segnentation method based on converse distance axis projection 20 10 20 40y6080 20 40 6080 (a)图3(a)角度轴投影 (b)图3)角度轴投影 20 10 20 40x6080 40 80 120160 (c)图3(c)角度轴投影 (@)基准角度轴投影曲线 图4角度轴投影曲线 Fig 4 The projective curve of the angle axis 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
就得出目标匹配的结果 ,虽然保证了运算量的降低 , 但不具有鲁棒性 ,因为仅仅由距离轴投影相似并不 能完全说明图像的相似. 本文首先判断距离轴投影 , 在给定的阈值下不相似 ,则直接判定不是目标 ,相似 则再比较角度轴投影. 角度轴投影如图 4所示. 图 3 逆向距离轴投影分割方法 Fig. 3 The segmentation method based on converse distance axis p rojection 图 4 角度轴投影曲线 Fig. 4 The p rojective curve of the angle axis 第 4期 严江江 ,等 :一种基于对数极坐标变换的快速目标别算法 ·373·
·374· 智能系统学报 第3卷 将图4(a)进行复制扩展，就得到了基准角度轴 匹配曲线，如图4(d)所示.在给定的阈值下，距离轴 算，一次N,运算相当于k+22m)+)次 和角度轴投影与基准投影均相似，则判定是目标；否 基本运算，一次N。运算相当于k+22m+1 则不是.相似度比较算法采用常用的平均绝对差算 次基本运算，其中k为计算机中泰勒级数计算到足 法，公式定义为 够精确时n的取值，则常用LPT算法共需要4k+ 1+w+1 D,=1·∑IN(d-N, (9) m 12m+2)次基本运算，观察图像大小为256× 式中如果是距离轴投影比较，m=min(W,W,),1= 256LP图像9090，取W。=W,=30,0=05.R= 1,2,:Wp,Wg|+1:如果是角度轴投影比较，m= P=90,k取值为15表1为算法的计算效率对比情 W。,I=1,2,W。N。(、N,(分别表示LP图和 况.在以上试验条件下，本文LPT算法相对于常用 基准LP图的轴向投影量，设定相似度阈值为·，如 LPT算法速度提高了大约3000倍，匹配算法相对于 果距离轴和角度轴投影均有min(D,)≤o,则停止 常用相关匹配算法速度提高了30倍左右， 计算，并认定是目标 表1算法的计算效率对比 2算法复杂度与分析 Table 1 The com parison of calculational effic iency 算法 基本运算次数 要得出识别结果，需4个步骤：1)得到观察图 常用LPT算法 12279600 像LP图；2)分割出观察图像LP图中的目标轮廓区 本文LPT算法 4050 域：3计算目标轮廓区域在距离轴和角度轴上的投 相关匹配识别算法 486090 影统计量：4)与基准LP图作比较 本文匹配算法 16351 分别对每步所需计算量进行分析，1)查找表方 对于有不同噪声背景的观察图像，生成LP图像 法中取内存地址内容运算相当于加法运算，需要 时会将噪声带入，如图5(a)~(b),采用填充和去除 (1-ω)·R·P次加法运算；2)计算轴向投影量相 当于加法运算，最多需要(1-⊙)·R·P次加法运 孤立点的方法可消除噪声的影响，如图5(c)所示 算：3)距离轴投影在第2步中已经计算，这一步需 用图2(b)~(d)、去除噪声后的图5(c)与基准 要W。·P次加法运算；4)由式(9)取极限情况，对距 LP图作相似度计算，结果如表2所示.其中，W,= 离轴投影，需要2·(W。-W,|+1)·min(Wp,W,) 32W,为观察LP图目标轮廓区域宽度，距离轴和角 次加法运算和(W。-W。)次乘法运算，对角度轴， 度轴的minD)为式(9)计算出来的各自平均绝对 需要2·P)·P次加法运算和P次乘法运算：将加 差的最小值 法和乘法都作为基本运算，则本文算法共需要 表2相似度分析 [2(1-o)R+2P+W。+11·P+(1W。+W,|+1)· Table 2 The analysis of si ilrity [2 n in (W,W,)+1次基本运算 图序 We 距离轴D, 角度轴D, 图2b) 31 19032 08222 3试验结果与分析 图2(c 33 37500 23556 图2(d 之 22188 13444 常用LPT算法是自然幂和三角函数运算组成 图5(c 31 33000 26778 的复杂运算，将自然幂函数、正弦函数和余弦函数展 开成泰勒级数，分别记为NE、Ns、Nc,根据泰勒展开 本文共采用3组不同图像进行了实验.第1组 是40张目标作各种尺度和旋转变化的图像，使用最 式，一次NE运算相当于k+ 公2m+业次基本运 近邻插值方法：第2组是90张加入了各种不同噪声 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
将图 4 ( a)进行复制扩展 ,就得到了基准角度轴 匹配曲线 ,如图 4 ( d)所示. 在给定的阈值下 ,距离轴 和角度轴投影与基准投影均相似 ,则判定是目标 ;否 则不是. 相似度比较算法采用常用的平均绝对差算 法 ,公式定义为 Dl = 1 m · ∑ l+m +1 i = l | Np ( i) - Nq |. (9) 式中 :如果是距离轴投影比较 , m =m in (W p , W q ) , l = 1, 2, …, |W p , W q | + 1 ;如果是角度轴投影比较 , m = W p , l = 1, 2, …, W p . Np ( i) 、Nq ( i)分别表示 LP图和 基准 LP图的轴向投影量 ,设定相似度阈值为 σT ,如 果距离轴和角度轴投影均有 m in (Dl ) ΦσT ,则停止 计算 ,并认定是目标. 2 算法复杂度与分析 要得出识别结果 ,需 4个步骤 : 1)得到观察图 像 LP图 ; 2)分割出观察图像 LP图中的目标轮廓区 域; 3)计算目标轮廓区域在距离轴和角度轴上的投 影统计量; 4)与基准 LP图作比较. 分别对每步所需计算量进行分析 , 1)查找表方 法中取内存地址内容运算相当于加法运算 , 需要 (1 -ω) ·R ·P次加法运算; 2)计算轴向投影量相 当于加法运算 ,最多需要 ( 1 -ω) ·R ·P次加法运 算; 3)距离轴投影在第 2步中已经计算 ,这一步需 要W p ·P次加法运算; 4)由式 ( 9)取极限情况 ,对距 离轴投影 ,需要 2·( |W p - W q | + 1) ·m in (W p , W q ) 次加法运算和 ( |W p - W q | )次乘法运算 ,对角度轴 , 需要 (2·P) ·P次加法运算和 P次乘法运算;将加 法和乘法都作为基本运算 , 则本文算法共需要 [2 (1 -ω) R + 2P +W p + 1 ]·P + ( |W p +W q | + 1) · [2m in (W p , W q ) + 1 ]次基本运算. 3 试验结果与分析 常用 LPT算法是自然幂和三角函数运算组成 的复杂运算 ,将自然幂函数、正弦函数和余弦函数展 开成泰勒级数 ,分别记为 NE、NS、NC ,根据泰勒展开 式 ,一次 NE 运算相当于 k + ∑ k n =2 (2n + 1) 次基本运 算 ,一次 NS运算相当于 k + ∑ k n =2 (2 (2n - 1) + 1) 次 基本运算 ,一次 NC 运算相当于 k + ∑ k n =2 [ 2 (2n) + 1 ] 次基本运算 ,其中 k为计算机中泰勒级数计算到足 够精确时 n的取值 , 则常用 LPT算法共需要 4k + ∑ k n =2 (12n + 2) 次基本运算. 观察图像大小为 256 × 256, LP图像 90 ×90,取 W p =W q = 30,ω = 0. 5, R = P = 90, k取值为 15. 表 1为算法的计算效率对比情 况. 在以上试验条件下 ,本文 LPT算法相对于常用 LPT算法速度提高了大约 3 000倍 ,匹配算法相对于 常用相关匹配算法速度提高了 30倍左右. 表 1 算法的计算效率对比 Table 1 The com par ison of ca lcula tiona l effic iency 算法 基本运算次数 常用 LPT算法 12 279 600 本文 LPT算法 4 050 相关匹配识别算法 486 090 本文匹配算法 16 351 对于有不同噪声背景的观察图像 ,生成 LP图像 时会将噪声带入 ,如图 5 ( a) ～( b) ,采用填充和去除 孤立点的方法可消除噪声的影响 ,如图 5 ( c)所示. 用图 2 ( b) ～( d)、去除噪声后的图 5 ( c)与基准 LP图作相似度计算 ,结果如表 2所示. 其中 , W q = 32. W p 为观察 LP图目标轮廓区域宽度 ,距离轴和角 度轴的 m in (Dl )为式 ( 9)计算出来的各自平均绝对 差的最小值. 表 2 相似度分析 Table 2 The ana lysis of sim ilar ity 图序 W p 距离轴 Dl 角度轴 Dl 图 2 ( b) 31 1. 903 2 0. 822 2 图 2 ( c) 33 3. 750 0 2. 355 6 图 2 ( d) 32 2. 218 8 1. 344 4 图 5 ( c) 31 3. 300 0 2. 677 8 本文共采用 3组不同图像进行了实验. 第 1组 是 40张目标作各种尺度和旋转变化的图像 ,使用最 近邻插值方法;第 2组是 90张加入了各种不同噪声 ·374· 智 能 系 统 学 报 第 3卷
第4期 严江江，等：一种基于对数极坐标变换的快速目标别算法 ·375 的目标变化图，加入的噪声包括高斯噪声、椒盐噪声 “组中正确识别的图像数除以每组总图像数即为识 和加性噪声：第3组是50张非基准目标图像，其中 别正确率」 3张有代表性图像如图6所示：实验结果见表3，每 (a)带噪声观察图像 (b)带噪声LP图像 (c)去除噪声后的LP图像 图5有噪声的观察图像及其带噪声LP图像和去除噪声后的LP图像 Fig 5 The input mage,the logpolar mage with noise and the bgpolar mage with non-noise (a)图像1 (b)图像2 (c)图像3 图6非基准目标图 Fig 6 mages of non-object 表3目标识别正确率 一种快速的改进算法，使其在计算效率上相对于常 Table 3 Results of the recogn ition correct rate 用算法有了较大的提高.同时本文利用对数极坐标 正确识别率/% 平面目标的尺度和旋转不变性，提出了一种双轴投 组别 0,=20,=30,=40,=5 影相似度分析算法对分割出来的目标轮廓区域进行 第1组 325 75 95 975 相似度分析，增加了其可靠性.将二维图像的匹配运 第2组288 755 944 977 算转换成2个轴向的一维投影匹配运算，减少了图 第3组100100 100 100 像匹配的运算量，对目标识别尤其是快速目标识别 从表3可以看到，噪声对识别正确率几乎没有 提供了一个有效的途径 影响.因为本文方法是针对目标轮廓的，在噪声不破 参考文献： 坏目标轮廓提取的情况下是不影响识别正确率的， [1 ]SCHWARTZ E L Spatial mapp ing in the prmate sensory 阈值·，的选取很重要，在试验中取4或5就可以达 projection:analytic structure and relevance b perception 到较高的识别正确率.对于非基准目标图，大多数不 [J].Bological Cybemetics,1977,25:181-194 满足式(8)，少量满足式(8)的相似度又不满足阈值 2]SCHWARTZ EL,GREVE D N,BONMASSAR G Space- 条件，所以取得了很高的识别正确率 variant active vision:definition,overview and example[J] 4结束语 Neural Networks,1995,8(7):1297-1308 [3]B ISHAY M,PETERS R A L KAMWAMURA K Object 针对常用的对数极坐标变换算法，本文提出了 detection in indoor scenes using bg polar mapping[C]// 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
的目标变化图 ,加入的噪声包括高斯噪声、椒盐噪声 和加性噪声;第 3组是 50张非基准目标图像 ,其中 3张有代表性图像如图 6所示;实验结果见表 3,每 一组中正确识别的图像数除以每组总图像数即为识 别正确率. 图 5 有噪声的观察图像及其带噪声 LP图像和去除噪声后的 LP图像 Fig. 5 The input image, the log2polar image with noise and the log2polar image with non2noise 图 6 非基准目标图 Fig. 6 Images of non2object 表 3 目标识别正确率 Table 3 Results of the recogn ition correct ra te 组别 正确识别率 / % σT = 2 σT = 3 σT = 4 σT = 5 第 1组 32. 5 75 95 97. 5 第 2组 28. 8 75. 5 94. 4 97. 7 第 3组 100 100 100 100 从表 3可以看到 ,噪声对识别正确率几乎没有 影响. 因为本文方法是针对目标轮廓的 ,在噪声不破 坏目标轮廓提取的情况下是不影响识别正确率的. 阈值σT 的选取很重要 ,在试验中取 4或 5就可以达 到较高的识别正确率. 对于非基准目标图 ,大多数不 满足式 (8) ,少量满足式 (8)的相似度又不满足阈值 条件 ,所以取得了很高的识别正确率. 4 结束语 针对常用的对数极坐标变换算法 ,本文提出了 一种快速的改进算法 ,使其在计算效率上相对于常 用算法有了较大的提高. 同时本文利用对数极坐标 平面目标的尺度和旋转不变性 ,提出了一种双轴投 影相似度分析算法对分割出来的目标轮廓区域进行 相似度分析 ,增加了其可靠性. 将二维图像的匹配运 算转换成 2个轴向的一维投影匹配运算 ,减少了图 像匹配的运算量 ,对目标识别尤其是快速目标识别 提供了一个有效的途径. 参考文献 : [ 1 ] SCHWARTZ E L. Spatial mapp ing in the p rimate sensory p rojection: analytic structure and relevance to percep tion [J ]. Biological Cybernetics, 1977, 25: 1812194. [ 2 ] SCHWARTZ E L, GREVE D N, BONMASSAR G. Space2 variant active vision: definition, overview and examp le[J ]. Neural Networks, 1995, 8 (7) : 129721308. [ 3 ]B ISHAY M, PETERS R A I, KAMWAMURA K. Object detection in indoor scenes using log2polar mapp ing [ C ] / / 第 4期 严江江 ,等 :一种基于对数极坐标变换的快速目标别算法 ·375·
·376· 智能系统学报 第3卷 Proceedings of IEEE Intemational Conference on Robotics 成像制导中的应用[J]字航学报，2005,26(3)：330- and Automation San Dieg,CA,USA,1994:775-780 333 [4]SLVA C,SANTOS-V CTOR J.Egomotion estmaton using WANG Li,L I Yanjun,ZHANG Ke The app lication of tar bgpolar mages [C]//Sixth Intemational Conference on get recognition algrithm based on bgpolar transomation Computer V ision Bombay,India,1998:967-972 for maging guidance[J].Joumal ofAstonautics,2005,26 [5 ESCOBAR M J,RU IZDEL-SOLAR J.Biobgically based (3):330-333 face recognition using Gabor filters and bgpolar mages 作者简介： [C]//Intemational Joint Conference on Neural Neworks 严江江，男，1979年生，博士研究 (CNN2002).Honolulu,U4,2002:1143-1147 生，主要研究方向为飞行器任务规划、 [6]HOTTA K,KUR ITA T,M ISH MA T Scale invariant face 智能搜索、计算机视觉等.发表学术论 detection method using higherorder local autocorrelation 文6篇 features extracted from bgpolar mage [C]//Proceedings of the 3rd IEEE Intemational Conference on Face Ges- 丁明跃，男，1961年生，特聘教授、博 ture Recognition Nara,Japan,1998:70-75. 士生导师，EEE高级会员，SPE会员，湖 [7吗月霞，刘波.用MS320C50实现图像目标的形心捕 北省青年科协副会长，湖北省宇航学会 获[J]光子学报，2001(4)：455-459 副理事长，主要研究方向为图像处理与 FENG Yuexia,LU ba The poid capturing of mage object 分析、计算机视觉及应用、医学图像处理 is realized using TMS320C50 [J].Acta Photnica Sinica, 和任务规划等.发表学术论文200余篇， 2001(4):455-459 其中被SCLEL,ISTP收录130余篇， [8 TANG Minshou The application of correlation matching 周成平，男，1957年生，副教授，主 technique in mage guidance[C]//Proceeding of CSAA 1st 要研究方向为图像处理、计算机视觉、 Electronic Conference of the Youth Los Angeles,USA, 任务规划等.先后获航天部、教育部科 1994 技进步三等奖各一项，发明专利一项： [9王立，李言俊，张科.对数极坐标变换识别算法在 发表学术论文30余篇。 2008 Iterna tional Conference on Itelligent Com putation Technology and Automation 2008年智能计算技术与自动化国际会议 2008 Intemational Conference on Intelligent Computation Technology and Automation (IC CTA 2008)will be held on 20~22 October,2008 in Changsha,China C TA08 ams to provide a high-level intemational form for scientists,engineers,and educaors to present the state of the art of intelligent computation and automation research and applications in diverse fields The conference will feature plenary speeches given by renowned scholars and reg- ular sessions with broad coverage The conference proceedingswill be published by IEEE Computer Society All papers accepted will be included in IEEE Xp bre and arranged for indexing by both EI Compendex and ISTP. Ema il:icicta@126 com W ebsite:http://www.icicta org/index asp 1994-2009 China Academic Journal Electronic Publishing House.All rights reserved.http://www.cnki.net
Proceedings of IEEE International Conference on Robotics and Automation. San D iego, CA, USA, 1994: 7752780. [ 4 ] SILVA C, SANTOS2V ICTOR J. Egomotion estimation using log2polar images [ C ] / / Sixth International Conference on Computer V ision. Bombay, India, 1998: 9672972. [ 5 ] ESCOBAR M J, RU IZ2DEL2SOLAR J. Biologically based face recognition using Gabor filters and log2polar images [ C ] / / International Joint Conference on Neural Networks ( IJCNN2002). Honolulu, USA, 2002: 1143 21147. [ 6 ] HOTTA K, KUR ITA T, M ISH IMA T. Scale invariant face detection method using higher2order local autocorrelation features extracted from log2polar image [ C ] / / Proceedings of the 3 rd IEEE International Conference on Face & Ges2 ture Recognition. Nara, Japan, 1998: 70275. [ 7 ]冯月霞 , 刘 波. 用 TMS320C50实现图像目标的形心捕 获 [J ]. 光子学报 , 2001 (4) : 4552459. FENG Yuexia, L IU bo. The poid cap turing of image object is realized using TMS320C50 [J ]. Acta Photonica Sinica, 2001 (4) : 4552459. [ 8 ] TANG M inshou. The app lication of correlation matching technique in image guidance[C ] / / Proceeding of CSAA 1st Electronic Conference of the Youth. Los Angeles, USA, 1994. [ 9 ]王 立 , 李言俊 , 张 科. 对数极坐标变换识别算法在 成像制导中的应用 [J ]. 宇航学报 , 2005, 26 ( 3) : 3302 333. WANG L i, L I Yanjun, ZHANG Ke. The app lication of tar2 get recognition algorithm based on log2polar transformation for imaging guidance[J ]. Journal ofA stronautics, 2005, 26 (3) : 3302333. 作者简介 : 严江江 ,男 , 1979 年生 ,博士研究 生 ,主要研究方向为飞行器任务规划、 智能搜索、计算机视觉等. 发表学术论 文 6篇. 丁明跃 ,男 , 1961年生 ,特聘教授、博 士生导师 , IEEE高级会员 , SP IE会员 ,湖 北省青年科协副会长 ,湖北省宇航学会 副理事长 ,主要研究方向为图像处理与 分析、计算机视觉及应用、医学图像处理 和任务规划等.发表学术论文 200余篇 , 其中被 SCI, EI, ISTP收录 130余篇. 周成平 ,男 , 1957年生 ,副教授 ,主 要研究方向为图像处理、计算机视觉、 任务规划等. 先后获航天部、教育部科 技进步三等奖各一项 ,发明专利一项 ; 发表学术论文 30余篇. 2008 Interna tiona l Conference on Intelligent Computa tion Technology and Automa tion 2008年智能计算技术与自动化国际会议 2008 International Conference on Intelligent Computation Technology and Automation ( ICICTA 2008) will be held on 20～22 October, 2008 in Changsha, China. IC ICTA08 aim s to p rovide a high2level international forum for scientists, engineers, and educators to p resent the state of the art of intelligent computation and automation research and app lications in diverse fields. The conference will feature p lenary speeches given by renowned scholars and reg2 ular sessions with broad coverage. The conference p roceedingswill be published by IEEE Computer Society. A ll papers accep ted will be included in IEEE Xp lore and arranged for indexing by both EI Compendex and ISTP. E2ma il: icicta@126. com W ebsite: http: / /www. icicta. org/index. asp ·376· 智 能 系 统 学 报 第 3卷
