（基础数学专业论文）基于局部灰度信息的图像匹配.pdf

j 复旦大学硕士学位论文 、 一= 二_ 一 摘要 本文对相差对比度变换以及旋转、相似和平移组合变换的两幅图像之间的匹配 问题进行了研究。 文中对二维景物成像几何模型进行了简单推导，得出由于成像条件的变化，在 一定的条件下对同一景物所摄的两幅图像将相差个旋转、相似和平移的组合变 换。了使光滑、去噪后的两幅图像不改变原先相差的变换关系，我们选用了较 新的a m s s 滤波算子。有别于一般的利用图像的微分特征找特征点的方法，本文卜下 提出了利用图像局部范围内的灰度分布信息选取特征点的新方法，并讨论了该方 法在相应的几何和灰度变换下的一些不变性。f 通过给每个特征点赋予一个伴随的 特征向量，我们定义了特征点问的差异函数，并利用它对两幅图像的特征点进行 了匹配。因为特征点问的匹配不可能作到完全准确，本习介绍了有意义事件的概 念，并采用了主要基于统计思想的投票方法，从而从特征点的匹配结果中决定出 几何变换的参数。如何评价匹配结果至今仍无一个很好的量化定义，本文使用了 一种基于直观视觉的办法作为评判的标准。 关键词：尺度空间；不变性；特征点；有意义事件；投票 分类号t p 3 9 t 4 1 复旦大学硕士学位论文 a b s t r a c t i m a g em a t c h i n gb a s e d o nl o c a lg r a yi n f o r m a t i o n i nt h i sp a p e rw ec o n s i d e ram a t c h i n gp r o b l e mo ft w oi m a g e st h a ta r ed i f f e r e n t f r o mac o n t r a s tt r a n s f o r ma n dac o m p o u n dt r a n s f o r mc o n s i s t so fr o t a t i o n ，s i m i l a r i t y a n dt r a n s l a t i o n i nt h ep a p e rw eg i v eab r i e fd e d u c i n go ft h eg e o m e t r i cm o d e lf o rt h ei m a g i n go f t w o d i m e n s i o n a lo b j e c t ，w eo b t a i nt h a tu n d e rc e r t a i na s s u m p t i o n st h et w oi m a g e s o ft h es a m eo b j e c tw i l ld i f f e rb yac o m p o u n dt r a n s f o r m i no r d e rt or e t a i nt h e t r a n s f o r mr e l a t i o n s h i pb e t w e e nt w o o r i g i n a li m a g e s ，w e c h o o s ean e w o p e r a t o ra m s s a st h ef i l t e rw ep r o p o s ean e wm e t h o dt h a tu t i l i z e st h el o c a lg r a yd i s t r i b u t i o n o fe a c hi m a g et os e l e c tt h ec h a r a c t e r i s t i cp o i n t so ft w oi m a g e s b yd e f i n i n gt h e d i f f e r e n c ef u n c t i o no ft w oc h a r a c t e r i s t i cp o i n t s ，w ef i r s td ot h em a t c h i n ga m o n gt h e c h a r a c t e r i s t i cp o i n t s u s i n gav o t i n gm e t h o dw ed e t e r m i n et h ep a r a m e t e r so ft h e t r a n s f o r m sf r o mt h em a t c h i n gr e s u l to ft h ec h a r a c t e r i s t i cp o i n t s ac r i t e r i ab a s e d o ns u b j e c t i v ev i s i o ni su s e dt oe v a l u a t et h ef i n a lm a t c h i n gr e s u l t k e y w o r d s s e a 1 es p a c e ；i n v a r i a n c e ；c h a r a c t e r i s t i cp o i n t ；m e a n i n g f u le v e n t ；v o t e l l 复旦大学硕士学位论文 第0 章引言 摄像机位置的移动，焦距的调整，以及景物照明情况的变化，甚至于不同像 机成像系统的传感器对明暗对比的非线性响应关系的不同，都会造成对同景物 所摄图像间，相差一个几何变换或对比度变换( 也叫灰度变换) 。识别出这些相 差某种变换的图像，实际上是描述的同一件事物，是图像匹配的主要任务。如在 遥感图像处理中需要把不同波段传感器对同一景物拍得的多光谱图像按像点一一 套准，然后根据像点的性质进行地物分类；如在不同时间对同一地面拍摄的两幅 照片，经套准后可找出其中那些特征有了变化的像点，就可以用来分析图中哪些 部分发生了变化；而利用放在一定间距处的两只传感器对同一物体摄得的两幅照 片，找出对应点后可算出物体离开摄像机的距离，即物体的深度信息；还有数字 视频处理中，对序列图像匹配求光流场等，图像匹配技术都起着非常重要的作 用。 0 1 基本概念和术语 先让我们回顾一下图像处理中的一些基本概念和术语。 定艾o 1 ( 灰度图像) 所谓一幅灰发图像是指定义在平面区域上的二元 实函凯( z ，y ) ，“：r 2 _ r 。有时为书写方凰( 。，y ) 也写砌f x ) ，x 表示句 量( 。，) 7 。 通常u 的定义域为r 2 中的有界区域n ，“的值域为r 的一段有界闭区间， 值u ( z ，) 即为图像 在( 。，) 丁点处的灰度值。一般假定“( 。，y ) c ( r 2 ) ，m 2 。 我们知道，计算机所能处理的信息必须是离散的数字化信息，因此必须对所拍 摄的照片( 连续化的信息) 进行采样和量化，变成一幅离散化的图像，才能加 一 。 复旦大学硕士学位论文 以存储和处理。设原始照片为( z ，) ，u ：【o ，n 】【o ，b 】斗【o ，f | 、b 、沩大于。的 实数。将区间【o ，a l 、【o ，6 j 、【o ，f 】分别m 、n 、等份，m 、n 、k 为正整数。假设 值u 、丽i a 、碧) 在区间【等，号k + 广l1 ) 之中，定义离散化的图像“d ( i ，j ) = 南。可见离散化后的 图像基本上反映了原始图像的信息，当m 、n 、k 取得充分大时，从人眼主观看 来，两者已没有什么区别，但作理论分析时应注意到它们之间的差别。 定艾0 2 ( 几伺变换) 设r 为某一平面几伺变换。n 为平面上某区域图像u 和”分 别定义在区域j 1 、t n 上，i 留：x - - - + x 7 ，其中x 、x 7 表示句量( z ，) r 、( 。7 ，y 1 ) 丁， 震x f 2 有”( x7 ) = “( x ) ，别称图像u g v 相差一个几何变换r ，或者说图像”是图 像“经变换r 得到的，记 = t “。 般情况下，这种变换t 可能是很复杂的非线性变换，研究中出现较多的是射 影变换，在一些特殊情况下，射影变换退化成为仿射变换，甚至简化为旋转、相 似、平移变换的组合，由于后两种变换相对要简单些，对它们的研究也较多。本 论文所研究的主要是旋转、相似、平移变换组合的情形。由于三维景物成像中有 透视失真、运动遮挡、阴影混入和噪声干扰等不利因素，三维图像匹配至今任公 认的技术难题。本文仅对二维景物成像作了研究，在第l 章中对二维景物成像几何 模型作了简单推导，并给出了相应的射影变换退化成仿射变换的充要条件，以及 该变换成为旋转、相似、平移组合变换的一个充分条件。 定义0 ，3 ( 对比度变换) u 、”是定义在平面区域q 上的两幅灰发图像。若存在一 个增函数g ( t ) ，g ：r r ，使得，x f ! 有”( x ) = u ( x ) ，则称图像u 雨耜羞一个 对比凌变换g ，或称图像 是由图像u 施加对比度变换g 得到的记 = gu ，g 称为 对比度变换函数有时也叫作灰度变换函数， 对比度变换函数g 可推广到更一般的上半连续非减函数类。为研究的需要，常 假勘( f ) c 1 ( r ) 。在图像处理中，为增强主观可视效果，常对图像施加某种特 定的对比度变换，以改善它的灰度分布情况。但对比度变换的存在也增加了图像 匹配的难度。对于相差一个对比度变换g 的两幅图像，理论上可以通过一种对比度 正规化的方法，使它们各自经过相应的对比度变换后变为同一幅图像，该图像具 有平均的灰度分布。但由于实际处理中都是离散化的数字图像，再加上噪声的影 响，这样处理后的效果并不理想。本论文将在后续章节中给予一定的讨论。 2 复旦大学硕士学位论文 0 2匹配问题的提出 现在假设有两幅灰度图像“和”，分别定义在平面矩形区域n ，和n z 上，若存在 某对比度变换跏以及某旋转、相似、平移的组合变换蜀，使得蜀n cn 。，晶n ， n 2 ，t o ：x _ x ，且v x n l 有 ( x 7 ) = 9 ( “( x ) ) ，试问如何从图像和”出发，决 定出适当的孔和卯，使得图像“和”能够匹配的很好。 我们知道任一旋转、相似、平移的组合变换t ，都可以写成以下形式： ( 辂丁( ；) = t ( 篇等) ( i ) + ( ：) ( 0 1 ) 因此，变换t 可以由旋转角口、相似比和平移向星a ，6 ) 7 这四个参数唯一确定。 如果我们在图像“和”中能找到两组映射点对x l7 = t o x 。、x 27 = t o x 2 ，就可以用 它们所确立的方程求出相应的目。、和f 口o ，b o ) t ，从而确定变换。在第3 章中， 我们将用选取特征点和特征点匹配的方法来找映射点对。但在实际中一般不可 能找到准确的映射点对x 、x 7 ，使得x 7 = t 0 x ，通常我们只能找到点对x 、0 ，满 足1 0 一孔x 0 。在景物所在平面中建立一个二维直角坐标系，设该坐标系 原点的三维坐标为( 。o ，y o ，z o ) 7 ，z 轴方向单位向量为( n 。，a z ，a 3 ) t ，y 轴方向单位向 量为( 6 1 ，b 2 ，b a ) 7 ，即有a 12 + a 2 2 + a 32 = b l2 + b 2 2 + b a 2 = 1 ，口1 b l + n 2 6 2 + a 3 b 3 = 0 。 则景物平面中坐标为( n ，6 ) r 的点，在三维坐标系中为点 n ( 兰) + 。( 墨) + ( 圣) 一( ；) = m ( ；) 于= 是有 m ( 小n ( ：小(分( ：) = ( ： b l 。o 如珈 | ) ( | ) 自，= a a 3 + b b 3 + 却一，= ( 。3 k 询一，) j b i( 1 2 ) ，、， 复旦大学硕士学位论文 由( 1 2 ) 等 结合( 11 ) 便有 记 一k = ( 一挚一争一 一 印 m = jo 。 i 纽 ， 6 1 b 2 一h ， 6 1 b 2 一虹 ，銎) 引理1 1 若景物所在乎面刁：通过焦点( o ，0 ，) 丁，贝p 矩阵m 必可逆。 证明：只需证d e t m o 即可。 ( 1 3 ) a e t ，= 一；a e t ( i i 耋：。蒌，) 但由于点( o ，0 ，) t 不在景物平面上，故向量( z 。，y o ，z o ) 7 一( 0 ，0 ，) 7 不可能表示 为( a l ，n 2 ，a 3 ) 了1 、( 6 。，b 2 ，6 3 ) 7 的线性组合，也就是说向量( n l ，口2 ，。3 ) 7 、( 6 - ，6 2 ，6 3 ) 7 、( z o ，踟，缅一，) 7 线性无关。所以d e t m 0 ，矩阵m 可逆。 一般来说景物平面不通过摄像机的焦点这个假设总是成立的，因此由目 理1l ，矩阵m 总是可逆的。 1 2 条件变化对成像的影响 当摄像机的位置、焦距发生变化时，景物和像机的相对位置有所变化，可 以等价地看作摄像机的成像平面不动，摄像机的焦距和景物的位置发生了变 化。设焦点变为( o ，0 ，7 ) 7 ，景物平面的原点变为( z 。7 ，y o ，z 0 7 ) r ，z 轴单位向量变 5 、i，il 一 、 ) ，_一， 剐 翥专 垫 复旦大学硕士学位论文 一一 为( 。，。2 ，口。，) r ，轴单位向量变为( 6 t 7 ，幻，b 3 ) 7 。设景物平面上坐标为( 。，6 ) 1 的 点，相应的成像点为( 。，9 ，o ) 7 ，类似于等式( 1 3 ) 的推导，则必j r 使得 “强一洲i ) 记 由( 1 37 ) 和( 1 3 ) 习 设 则有 于是有 n 1 7 5 l 兰 ， b l b 2 7 一址 | 。 z 。， 蜘， l 一孚 ”肌一肌 a 1 1 a i 2 m ，m ：i 蚴 i 盘。n 。 fr 7 = 。a 。! ，! x 。+ + a 。l 。2 ，z + + a 。l i 3 1 ，= 篆毫筹怒 因此变觚( i ) 一( ) 为射影娥 f 1 4 ) 引理1 2 上述射影变换t ：x - - - + x 是仿射变换的充分必要条件是j 0 使 得专( a 3 t , b 。，幻一，) = ( “。，b ，z o 一，) 。 证明：由( 1 4 ) 式易知，变换r 是仿射变换的充要条件为：a 3 1 = a 3 2 = 0 ，a 3 3 0 6 ”曲 扣扣 硝叫扩 扣扣 芦p ” i i | | | “ 彳 ， 女 ，1_f，r、_i 复旦大学硕士学位论文 即有 e 3 丁a = n 3 3的丁错e 3 t m 7 m = 3 3 e 3 t 错e 3 t m 7 = a 3 3 e 3 下m 一专( d ，6 3 ，。，忙k - ；( a 3 , b 3 , z o - ，) 其中k = a 3 3 0 。 注：由引理l2 易见下面几种情况下，t 为仿射变换 1 f 斗+ o 。，7 _ 一。，该情形对应于实际中的如卫星图像。 2 a 。7 = 6 。= a 。= b 。= 0 ，这种情况相当于保持成像平面与景物平面始终平 行。 3 a 。7 = a 。，b 。7 = b 3 ，z o7 一f = 劲一，该情况相当于景物所在平面可以绕舛由旋 转或平移，但必须满足。o7 一，7 = z 0 一f 。 引理1 3 当a 3 ，= b 37 = a 3 = b 3 = 0 时，射影变换t ：x x 7 堪化为旋转、相似、 平移变换的组合， 证明：此时有 f a l m = in 。 1 0 b lz u 6 2蜘l o 一孚 记 印= ( 。a 。l 乏) 易见q 、q 都为正交阵。，下设有d e t 印 情况。 7 0 1 7 m 7 ：i 以 io b 1 7 b 2 7 0 。o 7 “ l 一三q ! 上j f 的转反有面平物景虑巧考不吖以即 ，f-i_l、 ， l i | = q e如 、itliij， 、-， 蜘 ， q 高尚 旷 o ，jjl_lj_ill、 | | m 出求町 复旦大学硕士学位论文 一一 从而 一1 = “萎篙 x o y o 训 于是有。，：。：0 ( ：) ：q ，q 一- ：q ，q 丁 口3 1 = 牡3 2 = l “j = 。q 一1 = q _ q 1 可见，矩阵( ：) 为正交阵，而且d e t ( ：) = d e t q d e t q = - 由( 1 4 ) 和( 1 5 ) 爿 f 一1 ：土”- y ， 0 3 3 i a 2 1驯；) 屯) ( 1 5 ) 所以变换t ：x _ x 7 为旋转、相似、平移变换的组合。 由以上的推导过程可知，一股来说我们需要在相差一个射影变换的情况下研究 图像的匹配问题，但总的说来射影变换情况比较复杂，目前人们研究较多的还是 仿射变换下的情形，尤其是旋转、相似、平移变换组合的情形。本文将在相差旋 转、相似、平移组合变换的情形下研究两幅图像的匹配问题。 8 复旦大学硕士学位论文 第2 章图像的光滑和去噪 2 1尺度空间及不变性的定义 实际中产生和获得的图像，由于成像系统、底片质量及其它一些因素的影响， 总或多或少，不可避免地带有一些噪声。因此，光滑和去噪几乎成了图像处理的 一个必备过程。从数学上来说，所谓对图像的光滑和去噪就是指用某个滤波算 子正对函数u o f x ) 作用从而得到新的函数( 丑t o ) ( x ) 的过程，通常我们把得到的新 函数( 咒“。) ( x ) 记为“( t ，x ) 。为了方便对叠代滤波算子的渐近行为进行区分和模型 化，文献 2 s l 进了一个叫作尺度空间( s t a l es p a c e ) 的抽象框架： 定义2 1 ( 尺度空问s c a l es 2 ，a c e ) 所谓尺度空问是指一族依赖于尺度( s c a l e ) 参数t 的图像光滑算子正。对于任意一个图像t o ( x ) ，( 正u o ) ( x ) = w t ，x ) 表示图 像u o ( x ) 在尺度域e 被光滑化后的图像。 从图像处理的实际背景出发，文献【2 】对尺度空间又添加了金字塔( p y r a m i d a l ) 结构、局部比较原则( l o c a lc o m p a r i s o np r i n c i p l e ) 和正则性( r e g u l a r ) 等 比较自然的假设，并把具有金字塔结构、局部比较原则和正则性这三个假 设的尺度空间称作是因果( c a u s a l ) 的。正则性假设使得尺度空间和某个函 数联系起来，而因果性的假设则更进一步将尺度空间和某个微分方程联系 起来。为适应图像处理的需要，文献【2 】提出了微分方程的粘性解( v i s c o s i t y s o l u t i o n ) 的概念，并证明了在一定的条件下，如果尺度空间是因果的， n - ( t ，x ) = ( 正“。) ( x ) 是相应微分方程的粘性解。如著名的高斯滤波器就是一 个尺度空间的例子，置：斗g 。 “o ，g 。( x ) = 南e 一哥，而其相应的微分方程 即为我们所熟知的热传导方程苎号= u ( t ，x ) 。 在引言里所提出的匹配问题中，图像“和”相差几何变换和9 0 ，因此我们希 望光滑和去噪的过程能够不影响这种关系，即在滤波算子丑和丑，分别对“和”作用 9 复旦大学硕士学位论文 后，丑“和丑，。仍保持相差变换死和跏。这就要求我们所采用的滤波算子，或者说 尺度空间 正) 。2 0 具有某些不变性。 定义2 2f 平移不变性) 先定义平移算子7 = ：( 7 = u ) ( x ) = t ( x z ) 。若对于任意 二维向置z 及t o 有正，( 7 = u ) = 7 = ( 丑“) ，则称尺度空间 噩) t 蛰是平移不变的。 定义2 3 ( 欧氏不变性) 我们用r 同时表示芷交变换算予和其相应的芷交矩 阵，( r “) ( x ) = u ( r x ) 。若对于任一正交交换尼黜o 有丑( r “) = r ( 正。“) ， 则称尺度空间 丑) t o 是欧氏不变的。 定义2 4 ( 相似不变性) v a 0 ，定义相似变换算子以：( 风u ) ( x ) = u ( a x ) 。 若 0 、t 0 ，3 t ， o 使得风( 正，u ) = 正( 风) ，且t 印，a ) 关于a 在a = l 处 可微，v t o 函数圣( t ) = 嚣( t ，1 ) 连续且为正数，则称尺度空间 正) c 2 0 是相似不变 的。 定义2 5 ( 仿尉不变性) a 为非异阵，仿影变换算子a 定义为( a “) ( x ) = “( a x ) 。若尺度空间 瓦) ，= 。具有相似不变性，对任一仿射变换a ，相应的函数”，a ) 可 以延拓成函数t 俅，a ) ，满足f ”，a ) = t 心，a i d ) ，且v a ，t o 彳 a ( 正，“) = 正( a “) ，t ，- t ”，a ) ，则称尺度空问 正 t o 是仿射不变的。 定义2 6 ( 对比度不变性) 若对于任意对比度变换g 及t o 都葡- ( 丑) = 正( g u ) ，则称尺度空问t 正 f 0 是对比度不变的。 2 2 线性滤波器和a m s s 算子 我们通常采用的线性滤波器，其主要操作就是用一个正的可积函数去和图 像作卷积，这个正的可积函数被称作卷积核。当卷积核采用高斯函数g t ( 。，y ) = 南e 一匀乒时，该滤波器就是所谓的高斯滤波器。尽管线性滤波器操作简单，且 有着系统、深厚的理论基础和较为广泛的应用，但它们一般都不具有对比度不变 性，特别的： 引理2 1 高斯滤波第子正：“。一g 。tu 。，g 。( z ，y ) = 丽1 e 一掣所对应的尺度空 间不具备对比度不变性。 1 0 复旦大学硕士学位论文 证明：若记= g ( u 。) ，v ( t ，x ) = ( 正) ( x ) ，易见“( t ，x ) = ( 正1 1 0 ) ( x ) 和v ( t ，x ) 都 是热传导方程 掣= 姚x ) ( 2 1 ) 口t 的解，且其初值分别为u o 和u o 。设g c 2 ( i t ) 掣= 掣刮瓮叫ua ta t 。、7a t a g ( 噩“o ) = a g ( u ) = g t ( “) “+ 矿( 1 1 ) 1 d 1 1 2 一般来说夕“( u ) l d u l 2 0 ，于是g ( 正1 1 0 ) 一般不满足方程( 2 1 ) ，但正( g 1 1 0 ) = 以口 总是方程( 2 1 ) 的解，因此g ( 正u o ) 正( g 1 1 0 ) ，即尺度空间不具有对比度不变 性。 由此可见，在图像匹配中使用高斯滤波器类的线性滤波器不太合适，我 们需要采用一种非线性的滤波器。事实上，同时满足上述各种不变性定义的 尺度空间从某种意义上来说是唯一的，它就是文献【2 】中提出的a m s s ( a f f i n e m o r p h o l o g i c a ls c a l es p a c e ) 算子。a m s s 算子定义为噩：1 1 0 一己u o ，其中正 u o 满足微分方程 c q l l 面2 i( 2 2 ) 容易算得c u r v ( u ) = 以”黑，由方程( 2 ，2 ) 粘性解的存在唯一性不难验i j e a m s s 算 子具有前面定义的各种不变性，且可以算出相似不变性定义中的函数t ”，a ) = a ；t 。设图像“和”满足”= g ( t - “) ，9 为对比度变换函数，r 具有( 0 1 ) 所示形式。变 换? 可以等价地用组合变换7 = 风r 来表示，由a m 甜算子所具有的各种不变性 可以证明正 = g ( t ( 丑，“) ) ，其中t = a t 。因此对图像u 和”的匹配可以等 价地转化为对图像丑，“和正”作匹配，而后两幅图像由于己经过了滤波处理， 数据显得更加可信一点。但需要指出的是，在匹配之前我们并不知道相似比 的 大小，因此无法事先确定正确的t 7 值，也就无法得到正确的处理后的图像正，“。 一种办法是在相似比的可能范围内，对每个值都去做一份；另一种就是使用较小 的t ，从而t 7 也很小，丑和正，差异不是很大，因此可以近似地用t 代替t 7 。本论文采 用了后一种方法。为方便起见，经过光滑处理后的图像我们仍然用u 和”来表示， 以后章节中提到的图像“和v 若无特别说明均指的是这种经过光滑处理后的图像。 复旦大学硕士学位论文 3 1概述 第3 章特征点的选取和匹配 一幅图像包含有大量的信息，哪些才是反映它本质特征的呢? 换句话说，如何 才能区分这幅图像和另一幅图像是否描述的同一景物呢。在我们的匹配问题中， 两幅图像假定相差变换孔和g o ，当然我们可以拿所有可能的旋转角口、相似比、 平移向量( n ，b ) t 和对比度变换g 去做实验，看两幅图像在相应的变换下是否吻合的 很好，从而确定出最好的那组日、k 、( n ，6 ) t 和g ，但这样做即便可行的话，也太耗 费时间了，而且你还必须有个好的评判标准来决定什么叫做匹配的很好，遗憾 的是这样一个好的评判标准，目前也很难找到。 一般来说，我们总是先从图像中以某种方式找出一些能够表现图像特征的点 来，这些点的集合叫做特征点集。于是对两幅图像的匹配，可以先从相应的两个 特征点集的匹配做起，在特征点集的匹配中，找出合适的变换t 和g ，再运用到两 幅原始图像上去。特征点的选取应有一些适当的要求： 特征点集中的点应当足够多，又不宜太多。点数太少不能满足统计的需要， 太多的点又会造成巨大的计算量，影响匹配算法的速度。 特征点不应都聚集在一个很小的局部范围内，它们之间最好能保持一个适当 的距离。特征点间距离太小会影响计算的精度。 特征点的选取应当具备变换t 和g 下的不变性。即图像u 和”若相差变换丁和g ， 那么“的特征点集在t 下的像应该正好是 的特征点集，或至少它们的交集足够 大。 特征点的选取应具备一定的稳定性，对噪声的影响不敏感。 1 2 复旦大学硕士学位论文 3 2 特征点的选取 那么，什么样的点可以作为特征点呢，有许多不同的做法。例如可利用图像的 整体信息，如找质心点等，但若图像t 在t 下的像仅仅是u 的一部分时，那么由于 整体信息的不一致，这种做法变的不可行，况且9 的存在也使得诸如质心点之类的 对应变的毫无意义。因此对于我们所研究的匹配问题来说，只能利用图像的局部 信息来选取特征点。一般认为图像中的边缘部分包含了图像的重要信息，特别是 物体的轮廓线，正是把它和背景区分开来的重要依据。但是对于什么样的点是边 缘点，至今仍没有一个一致可接受的科学定义。通常认为一幅图像u ( x ) ，在边缘 点x 处应有比较大的梯度值i d u ( x ) l ，而且满足某种局部最大原则。c a n n y 的方法 中，把边缘点定义为那些梯度值在该点梯度方向上达到最大值的点，换句话说， 边缘点x 必须满足： 茜( o 卜o ，( t ) = i d u l ( x + 南2 ) ( 3 1 ) 但这个特征点的定义并非对比度变换下不变的。设u ( x ) = 9 ( “( x ) ) ，f ( t ) = i d v l ( x + 尚t ) ，则 丽o f = 掣刮瓦o f ( t ) 拶i ( 3 2 ) 若x 为“的边缘点，由( 3 1 ) 和( 3 、2 ) 可知筹( o ) = g “( u ) i d 训2 ，因为g “( u ) f d “j 2 不必 定为0 ，所以一般等( o ) 0 ，也就是说x 一般不再是”的特征点。其它一些边缘检 测方法，如h l d r e t h - m a r r 方法等也具有同样的缺点。实际上，如果不对灰度变 换函数g 加上某些限制条件，恐怕很难找出一个适当的边缘定义，请看下面的 例子：设增函数f ( x ) c 2 【o ，q ，值域为【o ，n ，8 r + ，则，“( o ) 亦为增函数。 定义图像u ( z ，y ) = f ( x ) ，对比度变换9 ( t ) = f “( t ) ，图像”( 。，y ) = 9 ( u ( z ，) ) ， 则”( z ，y ) = g ( ，( z ) ) = f “( ，( z ) ) = z 。对于图像札( z ，y ) 来说，由于，( z ) 可任意选 择，因此可构造出具有明显边缘存在的图像来，但图像v ( x ，y ) 的灰度值却总是 沿z 方向均匀变化的，很难说其中有边缘存在。这个例子说明，允许g 的一般性将 会把一幅很有特征的图像变的毫无特征，因此我们必须对g 有所限制。在c a n n y 的 方法中，如假定g ”( f ) 兰0 ，即9 ( t ) 具有耐+ 6 的线性形式，则边缘点的定义是g 不变 的，但这种假定未免太严格了些，事实上在实际中也很难保证变换g 的严格线性， 因此至少也应该允许它是近似线性的。既然直接找边缘点不太行，还是让我们先 看看到底什么是对比度变换下不变的东西。 。麓 1 3 复旦大学硕士学位论文 对于实函数“( x ) 以及a 一r ，一r = ru 一o o ，+ o 。) ，定义它的a 水平集为集 合) ( “： x l u ( x ) a ) ，易见) ( 一。= r ，x + 。= 0 。函数的水平集具有下列重要 的性质。 性质i ：函数的水平集全体完全描述了函数的信息。通过公式u ( x ) = s u p a l x y 。“ 我们可以从水平集的集合重建函数u ( x ) 。 性质2 ：函数的水平集在对比度变换下是总体不变的。两个函数u 和”具有总体 上一样的水平集，是指，弘使得x u v = m u ，反之亦然。易见若”= 9 ( u ) ，则“ 和v 具有总体一样的水平集。 性质3 ：若函数“和”具有总体上一样的水平集，则存在实的非减函数g ：r 一 瓦使得 = 9 ( “) ，而且夕可以由公式9 ( a ) = s u p # j x ，”3 鼽 ) 所确定。 实际上，上述的灰度变换9 可以推广到更一般的形式，即假设9 是非减的 上半连续函数，详细情形可参见【2 】，为了讨论简单起见，下面仍假设9 是增 函数。由以上性质可见，函数的水平集不但完全刻划了函数本身，而且是 灰度变换下不变的。对于我们所考虑的匹配问题，若找一子区域f 2cn - ， 则nc n 2 ， f n = 9 0 ( t o u ) l 矗n ，由性质2 知蜀。训n 和 l 而n 应有总体一样的 水平集。是我们所要求的，事先并不知道，但容易发现，由于蜀可逆，“i 。的 水平集和蜀“l 。的水平集在几何变换死下一一对应，也就是说u i 。的水平集 和叫。的水平集在相差变换死的意义下，应有总体一样的水平集。反之，我们若 找到一对子区域nc n 。、n c 吼，使得u i 。和 i 。，在相差某个丁变换下具有总体一 样的水平集，则有n 7 = t n ，t 叫。，和”i 。，具有总体一样的水平集，由性质3 ，存 在灰度变换g ，使得”i n ，= g 一( t u ) in ，。这里的g 、t 很有可能正是整体匹配所 要找的蜘和孔，但也可能不是，原因是图像中可能存在一些相同的局部区域。但 是若能找到大量这样的子区域对q 、q 7 ，从某种统计的意义出发，一定会帮助找 到整体匹配所需要的变换伪和死。 考虑到变换是旋转、相似和平移的组合，我们选取子区域n 为以x 为圆 心，r 为半径的圆盘区域，记为d ( x ，r ) 。若设x 在变换晶下的像为x ，相似比 为，易见d ( x ，r ) 在下的像为d ( x ，k o r ) ，仍为圆盘区域。因此，对于图像“中 任一圆盘区域d ( x - ，r - ) cn - ，我们可以在图像”中尝试所有的圆盘区域d ( x 。，r ：) c n ：，看“i d ( x 1 。) 和”d ( 。是否匹配，匹配的标准则是它们的水平集是否在相差 某个几何变换下总体致。当然，我们不可能对所有的圆盘区域d ( x 。，r ，) c n t 都到图像”中去找匹配，我们希望x ，只取那些比较有特征的点，而在决 1 4 复旦大学硕士学位论文 一 定“f d ( 。) 和”b ( x 2 ，。) 是否匹配时，考察各自所有的水平集也显得比较费事， 不如分别挑出某个特定的能反映各自特征的水平集来看是否匹配。为了精确化这 些想法，先引进一些记号： a 。( a ) = m ( x , x u ) ( 3 3 ) a 。( a ) 表示了图像u 的a 水平集的测度( 面积) ，可看作是图像“的灰度分布函数， 聊h l 脚i r a 堂号掣= 一掣 ( 3 a ) 矾( ) 则反映了图像“的灰度值的分布密度， 直方图。当“为离散函数时( 数字图像) ， 点个数，而上乙( a ) = a 。( a ) 一凡( a + i ) 。 因此甄。( a ) 通常也被称作图像 的灰度 氐( a ) 定义为灰度值大于等于a 的像素 观察一幅图像的边界轮廓部分，即物体与背景区分的部分，发现灰度值在边 界附近变化剧烈，而各自在物体和背景内部部分的灰度值则变化平缓。若取边界 部分一块圆盘区域d ( x ，r ) ，作它的灰度直方图，会发现如图3l 一样两峰夹一谷 的灰度分布模式，两个峰分别对应于物体和背景，谷则对应于边界部分。取谷 底所对应的灰度值作域值，将该圆盘图二值化，则圆盘图被分为黑白两部分， 黑白交界处则形成了一个合理的边界。由此，我们可以对一幅图像珏来定义它的 特征点集。对于“定义域n 。中的任点x ，考察“限制在d ( x ，r ) cn ，上的灰度直方 图矾( a ) ，矾( a ) 的定义域总假设为i o ，d 】，d 为某有限正实数，记 口1 = i n f ) - i 日j ( a ) o a 2 = s u p a i f j f ：( a ) o )( 3 5 ) 易见0 8 l 1 ，0s fsd ( 3 6 ) 0 g 1 ，0s f s d ( 3 7 ) 复旦大学硕士学位论文 一 图3 1 定义3 1 若存在o f 1 如f 3 0 ，且v z 】，z 2 f 0 ，d | 有 去s 搿1 + s ( 3 9 ) l + 一9 7 ( t 2 ) 一。 r 。7 其中为某大于0 的常数。以后我们所讨论的灰度变换g ，都是指满足上述要求 的g 。现考虑图像“和口仅相差灰度变换g ，由( 3 8 1 龇( f ) ) ( 如。h h ) ) i 箫小：咱) = 鬻吲f ) a - - a 1 ) 其中【a l ，a z 】，再由( 3 9 ) 得到 r i 风( 2 ) ( a 2 一n 一) s 玩国( f ) ) ( 9 ( o 。) 一夕( a ，) ) ( 1 + 5 ) 风( f ) ( a 。一a 一) 对直方图风( a ) 作检测时，用雨1 p 、( 1 十e ) q 分别代替( 3 6 ) 、( 3 7 ) 式中的p 和g ， 注意到眉点乙q ) 幽= 君凰( a ) 以，则厦。( a ) 在嗷有峰( 谷) 时，凰( a ) 在g ( ，) 处也 必然有峰( 谷) ，故若王l ( a ) 具有双峰夹一谷的分布模式，则矾( a ) 也必然一样， 所以当x 是“的r 特征点时，x 必然也是的r 特征点。这样，在对灰度变换函数g 作 了限制以后，适当调整参数p 、q ，可使得r 特征点的定义是灰度变换下不变的。 1 7 复旦大学硕士学位论文 假设我们先验地知道变换蜀所相应的相似比k 的范围为 h ，南2 】，对于图像“， 固定半径r ，以上为检测步长，按照定义3 2 找出它的所有r 特征点作为图像的特征 点集，再逐点检测图像”，找出其所有的r 特征点，r 7 f hr 七z r 】，作为图像 的特 征点集。综合上面几段的讨论，我们知道这样选出的特征点集满足本章开头所提 出的那些要求。 3 3 特征点的匹配 引进函数u 。( y ) = “( x + y ) ，v y d ( 0 ，r ) ，则“x ，相当于把子图像u i d ( ”1 作了平 移一x ，即把x 平移到了坐标原点，相应的“w 的a 水平集也相当于把子图像“i d ( 。) 的a 水平集作了平移一x 。容易证明 引理3 , 1 “l d ( ”) 和u l d ( x ， ，) 相差变换t 、9 等价于”和”x ，r ，相差变换亍、9 。其中t 如 式n 所定义，t 烈由下式所定义 v ( z ，) 丁d ( o ，r ) ， 亍 ( i ) = e c o s o s i n o l- 删s i n8 ) ( ：) 州 易见当“x ，与”；，相差变换了碍口g 时，r 7 = r ，且v a ，水平集n “”和x 口( ) ”。，相 差变换亍，简记为芋( x u ”) = x 口( ” x ，小 对于图像”中的任一r 特征点x ，由定义3 i ，有相应的f 。、f 。，记f = 学，则 每个r 特征点都可以用行向量( u ，。，y ，r ，f ) 来表示，其中z 、y 表示点x 的横、纵坐标 值，该行向量可称之为r 特征点x 的伴随特征向量。 回到我们所考虑的匹配问题，若x 为图像“的r 特征点，x = t o x ，r ，= r ， 则由有关特征点定义的讨论知道，x 7 必为图像 的r 特征点，u l d f 。) 和”b f x ，) 相 差变换霸、g o ，由引理3 1 ，等价的有u 和_ ，相差变换瓦、g o ，所以v a ，有- o ( x u x ，) = ) ( ( ) ”x ，r ，特别的必有死( x j u ”) = x m ( j ) ”一，n 珈( f ) 未必一定等 于f 7 ，但注意到卯( f ) 、f 7 都表示”限制在d ( x 7 ，r 7 ) 上的灰度直方图的谷底部分，若简 记a ( a ) = m ( 孙，) 、( a ) = 一! 鲁，也就是说，跏( f ) 、f 都表示日( a ) 值很小的 地方，因此l a d ) 一a ( 卯( f ) ) i = l ( f ) h ( a ) d a 会很小，于是m ( _ 0 ( ”) x f ，u 。，) 很小，其中a 口= ( a b ) u ( b a ) 。为方便起见，我们引进二值化算子昆： 1 8 复旦大学硕士学位论文 “_ 历“，它由下式所定义： c 酬y ，= ： y x a u ( 3 1 1 ) yg x “ 弓i 理3 2t 鼬、”分别定义在区域n 、t n 上，t 为可_ 逆几何变换，且辛知= g ( t u ) ，9 为增函数，则有m ( t ( x l 。u ) l ：”) = t p i t 。( 蜀。“) 一b t ：v d y 。 证明：容易证明二值化算子以与算子t 交换，即有b ( t u ) = t ( 毋u ) ，则 i 丁( 目。u ) 一目：”l = i b t 。( t u ) 一b t ，0 ( t “) ) i = i 岛，( t u ) 一岛一- ( f 。) ( f u ) i ( 3 1 2 ) 不妨设“sg - 1 ( f 2 ) ，由( 3 ，1 2 ) 式，容易发现当且仅当y x “( t u ) 一，( f ：) ( t “) 的时 候，i t ( 目，“) 一且：u = 1 ，而其它情形则等于o 。于是 y 椰阳) 一刚匆2 k 川k 叫f 2 j m ) 匆 = m ( m 。( t u ) x a - ( 1 2 ) ( t u ) ) = m ( m ，( t u ) a x g - , ( t “) ) 注意至0 x f 。( t u ) = t ( x ，。“) ，x g t ( f ：) ( t u ) ) = x f ：( 9 ( 丁“) ) = x f ： ，所以丁nf t ( 目。“) 一 b t 。”i d y = r n ( t ( x l 。“) u ) 。 定义3 3 泛图缭“、口分别启义在乎厨区鸢抑i 、n 2 上，丁n i c t n 2 ，且”f t n 。= g ( t u ) ，其中变换t 具有j e ( o 1 ) 所示形式，9 2 对比度函数。我们说图像u 序打特征 点x 与图像 的r 特征点x 7 相对应，是撒7 = t x ，r = k r ，u i d ( x ，) 彳如i d ( 。，) 相差变 换t 、g 。 因此在我们的匹配问题中，当图像的r 特征点x 与图像 的r 特征点x 7 相对应 时，必有m ( 弱( m u 。) 叫一，) 彳艮小，由引理3 2 ，即积分d ( o ，) i 死( b f 让x r ) 一 目， 。，r f l d y 很小。 定义3 4 对于图像u 中任一r 特征点x ，特征向量v = ( u ，z ，r ，f ) ，以及图像u 中任 一r 7 特征点x 。，特征f 句量v 7 = ( ”，z 7