（生物医学工程专业论文）基于矩的图像分析和快速算法.pdf

东南大学硕士学位论文 a b s t r a c t t he s i st i t l e ：m o m e n t b a s e di m a g ea n a l y s i sa n df a s tc o m p u t a t i o no fm o m e n t i v a r i a n t s m a s f e rn a m e ：q i nl e i s u p e r v i s o rn a m e ：s h u h u a z h o n g s c h o o ln a m e ：s o u t h e a s t u n i v e r s i t y m o m e n tf u n c t i o ni sa ni m p o r t a n tt o o li ni m a g ea n a l y s i sa n dh a sb e e nw i d e l y u s e di nt h ef i e l do fc o m p u t e rv i s i o n ，i m a g ep r o c e s s i n ga n dp a t t e mr e c o g n i t i o n e x a m p l e so f m o m e n tb a s e df e a t u r ed e s c r i p t o r si n c l u d ec a r t e s i a ng e o m e t r i c a lm o m e n t ， o r t h o g o n a lm o m e n t a n dw a v e l e tm o m e n t c a r t e s i a ng e o m e t r i c a lm o m e n t ，b e c a u s eo f i t s s i m p l ef o r m ，h a sb e e nw e l ls t u d i e d t nr e c e n ty e a r s ，m o m e n tw i t ha no r t h o g o n a l b a s i ss e t ( e g ，l e g e n d r ea n dz e m i k ep o l y n o m i a l s ) b e c o m e sm o r ea c t i v eb e c a u s eo f t h e i rg o o dp r o p e r t i e s t h e yh a v es m a l ln o i s ys e n s i b i l i t y , c a nb ea p p l i e dt or e c o n s t r u c t o b j e c td i r e c t l ya n dr e p r e s e n ti m a g ew i m am i n i m a la m o u n to fi n f o r m a t i o nr e d u n d a n c y b u tt h e s ek i n d so fm o m e m sc a l lo n l ye x t r a c tg l o b a lf e a t u r e sf r o m i m a g e s ，s ow a v e l e t n l o n l e n ta p p e a r e d ，t h em o s ti m p o r t a n ta d v a n t a g eo fi ti st h a tw a v e l e tm o m e n tc a n e x t r a c tl o c a lf e a t u r e sf r o mi m a g e s ，s oi ti sav e r yu s e f u l d e s c r i p t o r i n p a t t e r n r e c o g n i t i o n t h i sd i s s e r t a t i o n m a i n l y f o c u s e so nm o m e n tb a s e d i m a g ea n a l y s i s a n d a p p l i c a t i o n ，i n c l u d i n g s o m e a l g o r i t h m s f o re f f i c i e n t c o m p u t a t i o n o f l e g e n d r e n l o n l e l l t s ，m o m e n t - b a s e dm e t h o df o r t e m p l a t em a t c h i n g ，a n d t h e a p p l i c a t i o n o f w a v e l e tm o m e n ti np a t t e r nr e c o g n i t i o n o nt h ea s p e c to ff a s ta l g o r i t h m ，w eu s ei m a g eb l o c k st o r e p r e s e n ti m a g e s a n d t h e np r o p o s et w on e w a l g o r i t h m sf o rf a s tc o m p u t a t i o no fl e g e n d r em o m e n t ，w h i c h a r ei n t e g r a lm e t h o da n dc m n u l a t i v em e t h o d r e s p e c t i v e l y a st o t e m p l a t em a t c h i n g ，w eu s eat w os t a g em e t h o d i nt h ef i r s t s t a g e ，t h e m a t c h i n gc a n d i d a t e sa r es e l e c t e du s i n ga c o m p u t a t i o n a l l yl o wc o s tf e a t u r e f r e q u e n c y d o m a i nc a l c n l a t i o ni s a d o p t e dt or e d u c et h ec o m p u t a t i o n a lc o s tf o rt h i ss t a g e i nt h e s e c o n ds t a g e ，r o t a t i o ni n v a r i a n tt e m p l a t em a t c h i n gi sp e r f o r m e d o n l yo nt h em a t c h i n g c a n d i d a t e su s i n gz e r n i k em o m e n t s t h i s a l g o r i t h mi sv e r yf a s ta n da c e u r a t e w ca l s od i ds o m ew o r ko nt h ea p p l i c a t i o no f w a v e l e tm o m e n t s w ec h o o s et 1 1 e i i - 基于矩的图像分析和快速算法 c u b i cb s p l i n ew a v e l e t sa n dh a a rw a v e l e t st oc o n s t r u c tw a v e l e tm o m e m s r e s p e c t i v e l y t h e ya r e n o to n l yi n v a r i a n tt o t r a n s l a t i o n ，s c a l i n ga n dr o t a t i o nb u ta l s o h a v et h e m u l t i r e s o l u t i o n p r o p e r t i e s w h i c ha r es u i t a b l ef o rc l a s s i f y i n g v e r ys i m i l a ro b j e c t s b e c a u s eo ft h e i ra d v a n t a g e s ，w eu s et h e mi nc h i n e s ec h a r a c t e r sr e c o g n i t i o n t h e r e s u l t ss h o wt h a tw a v e l e tm o m e n ti s r e a l l yv e r y u s e f u la n db e t t e rt h a nz e r n i k e t 1 1 0 m e n t k e yw o r d s ： m o m e n t o r t h o g o n a l m o m e n t l e g e n d r em o m e mz e m i k e m o m e mw a v e l e tw a v e l e t m o m e mf a s t a l g o r i t h m t e m p l a t em a t c h i n g p a t t e r nr e c o g n i t i o n i i i 兰二兰丝望 一 第一章绪论 1 9 6 2 年，h u 吣1 成功地将矩应用到图像分析领域中，并且提出了7 个几何矩 的0 j 变量，他的方法是建立于1 9 世纪数学家b o o l e ，c a y l e y , 和s y l v e s t e r 的工作之 1 勺。 至今为止，常见的矩描述子大致可以分为以下几种： 1 几何矩叫1 2 l f 交矩( 包括l e g e n d r e 矩和z e m i k e 矩) 6 1 3 旋转矩 1 3 , 1 4 1 4 复数矩 5t c h e b i c h e v 矩【9 】 6 小波矩1 6 1 这几种矩各有优点，后面几种都是在h u 提出的几何矩后，人们针对其中存 在的不足提出的不同方面的优化，正交矩的优点是具有很少的信息冗余度，且反 变换形式非常简单，旋转矩的优点是旋转不变性，t c h e b i c h e f 矩处理离散图像效 果精确，而小波矩则包含t d , 波的多分辨率特征，大大加强了矩特征对图像结构 精细特征的把握能力。 关于矩方法的研究，由于其计算的复杂性，很多人着手于研究它们的快速算 法，而从结果来看对几何矩的快速算法研究得比较多，对其他矩的研究就相对 少点。 关于矩应用的研究，在加快矩计算速度的基础上，矩的应用领域 3 , 4 , 1 0 - 1 2 1 也更 加j 泛，在模式识别、图像分析、边界检测、以及最近的研究热点一基于内容的 图像检索( c o n t e n t b a s e di m a g er e t r i e v a l ) 5 1 等许多领域都有应用。 1 1 各种形式矩的介绍 1 1 1 几何矩( g e o m e t r i cm o m e n t ) 的介绍 改连续情况下二维图像函数为舡力 m 。| = l 。x p y qf q ，y ) & a y 则它的p + g ) 阶几何矩定义如下： p ，q = 0 , 1 2 ，0 0( 1 1 ) 从以上的定义可以看出，几何矩本身有着自己的物理意义，如零阶矩表示物 体的质量，一阶矩表示物体的质心，二阶矩表示物体的方向等等。经过上述变换， 劁f 织的形状函数可以认为是由变换系数 锄组成的无限集合，这些系数是由图像 东南大学硕士学位论文 鬲数投影到一组二维多项式基函数上形成的。 在连续情况下，图像函数舷力相应的p 叼阶中心矩定义为： 玎矿( z ；) p - y ) 9 f ( x , y ) d x d y j _ 【；| = 坠m o o ，歹= 石m o l 。 对j 。一幅m x n 的离散图像卵，d ，它的p + q 阶几何矩定义为： m ，。= j 9 f ( i ，) 其；h i m ，j n ，p q 为常数。 ( 1 2 ) ( 1 - 3 ) 令。= 瓷，= 半，经过一系列的代数恒等变换，h u 推倒出 了七个对于位移、缩放和旋转变化都不变的绝对不变式。 m 1 = 2 0 + 0 2 m 2 = 2 0 p 0 2 ) 2 十4 成 m ，= ( 3 0 3 p 1 2 ) 2 + ( 3 卢2 1 ) 2 m 4 = ( 3 0 + 1 2 ) 2 + ( 2 l 十卢0 3 ) 2 纛丢2 ( 竺乏；趁 譬暑徽竺艺筝z ) 2 - ：3 ( + g 风”+ g ，0 3 r1 m a ， 十( 3 ：l 一硒3 ) 2 l + ) 3 ( + 。2 ) 2 一2 i + 风3 ) 2 】 、 m 6 = ( 掣2 0 一掣0 2 ) ( 3 0 + “2 ) 2 一( 掣2 1 十0 3 ) 2 】 + 4 。( ，如o + “2 ) 2 ( 2 i + ) m 7 = ( 3 p 1 2 一工) ( 3 0 + 2 ) 【( + 1 2 ) 2 3 ( 2 + ) 2 】 + ( 地。一3 1 2 ) ( 2 l + ) p ( 声岛。+ “2 ) 2 一( 2 i + 玩) 2 其中m r 讹具有镜像不变性，而m 7 在镜像变换时则变为一a 幻。它们在边缘提取、 矧像匹配及目标识别中具有广泛的应用。 虽然几何矩的基函数是完备的，但是它不正交，所以包含很多冗余信息，因 此y e a g u e 在此基础上提出了正交矩。 1 1 2 l e g e n d r e 矩( l e g e n d r em o m e n t ) 的介绍 + 叮) 阶的l e g e n d r e 矩定义为： 丑矿盟掣j = ，j ：! i 己( z ) 只( 卅( t y ) d x d y ，( 1 - 5 ) ，0 ( y ) 为p 阶l e g e n d r e 多项式，其定义为： 苎二童堕笙 尸p ( x ) = c 。x c 矿卜忙1 ，2 古矿揣舞厕一舢数a l0，p一，为奇数 l e g e n d r e 多项式在 一1 ，1 范围内构成一组完备正交基： f 、巴( x ) ( x ) 疵2i 詈五占”( 1 - 7 ) 由于l e g e n d r e 多项式的正交性，l e g e n d r e 矩的反变换形式就非常简单： 厂( t y ) = 五。p p ( x ) ( y ) ( 1 _ 8 ) 但是在实际应用中，我们只计算k 阶有限个l e g e n d r e 矩的值，因此反变换 时就只是近似式： f ( x ，y ) * 丑。0 一。( x ) 只 ) ( 1 9 ) 比较几何矩和l e g e n d r e 矩的形式，我们就可以发现它们之间具有非常简单 的关系： k ：鱼型 譬坠旦杰兰c 。c 社m 业 ( 1 1 0 ) 举例来说， = f 4 ，2 m = ( 3 4 ) m ) o ，2 0 _ = ( 3 4 ) m o l ， 加= ( 5 t 4 ) 3 2 m 2 0 - ( 1 2 ) m o o 】， z i i 一 q m hr 。2 = ( 5 1 4 ) 0 2 ) m o ，- ( 1 2 ) m o o 。 很明显，l e g e n d r e 矩仅与同阶和更小阶的几何矩有关，反之亦然。 1 1 3z e r n i k e 矩( z e r n i k em o m e n t ) 的介绍 ，阶z e r n i k e 矩的定义为： a 。，= 【( ”十1 ) ，万 j j ，( x ，_ y ) ( p ，臼) r d x d y ( 1 - 1 1 ) j 川t l = o ，1 , 2 ，。，为满足以下条件的正、负整数： ，7 _ l ，| i se v e n ，悱” ( 1 1 2 ) ，弋- pk ，印就是著名的z e r n i k e 多项式，其形式为： r ，( r ，y ) = ( p s i n 护，p e o s o ) = r 。，( p ) e x p ( i l o )( 1 - 1 3 ) 返，生函数在单位圆上是完备的，并且满足以下关系： k ，( _ y ) 1 + t ( y ) d x d y 2 牙伽+ 1 ) 民n 氏 在这个公式中，积分是在单位圆，2 三内的。 多项武r 。0 ) 的定义为： 。(p)=”萎111)l2一l：i三；匝二(n巧-s)! p ”h2 喜b n * p f 1 1 4 ) ( 1 1 s ) 其中一n 为偶数。由上式，我们可以推倒出z e m i k e 矩和几何矩之间的关系 纠”圳石痞吝扣，”( ； ( m 刚。一。：川一。 小峋 其中叮= ( k - | ! ) 2 。以下我们举一些例子来看看两者之间的关系： a 0 。= t o o 石= 1 石， a l l = a l l = 0 ， a 2 2 = 3 ( s x 0 2 一x 2 0 一2 i t 1 1 ) 石， a 2 0 = 3 ( 2 2 2 0 + 2 , u 0 2 一1 ) ，r ， 爿3 3 = 4 【风3 3 x 2 l + i ( 1 x 一3 9 i 2 ) 】万，( 1 - 1 7 ) a 3 l = 1 2 ，x 0 3 + 2 1 一f ( ，+ “2 ) 】，j r ， a 4 4 = 5 【柏一6 x 2 2 + 0 4 + 4 1 ( 2 ”一“3 ) 】，丌， a 。2 = 5 4 u t 0 4 一) + 3 ( i x 2 0 一，眈) 一2 i 4 ( t 3 i + 1 3 ) 一3 1 1 】 石， a 4 。= 5 1 6 ( 4 0 + 2 x 2 2 + 0 4 ) 一6 ( 2 2 0 + 0 2 ) + l 】万 z e r n i k e 矩之所以被很多入用来做为模式识别的工具是因为它具有很好的旋 转小变性，证明如下： 我们用l o , 口+ 。来表示图像沿着中心旋转倥角后的密度函数，则舷目+ 。 的z e r n i k e 矩变成： a 。j = 【( ”+ 1 ) ，疗】f f ( z ，y ) r o ，( p ，p + 口) + 葫c 砂= a 。je x p ( 一j l g ) ( 1 1 8 ) 换句话说，z e r n i k e 矩的模是旋转不变的，因为似。i i = p 一。 z e r n i k e 矩的反变换形式也非常简单，图像函数贴d 可以由下式表示： ( r ，y ) = a 。( n 目) ( 1 1 9 ) 1 1 4 旋转矩( r o t a t i o n a lm o m e n t ) 的介绍 阶数为n 的旋转矩的定义为： d 矿r ”f “。，p c 。s 臼) ，s i no ) r d r d o ( 1 2 0 ) 塑二皇堕笙 ，f 0 ，j ，2 , 3 ，m ，f 为任意整数。 旋转矩与几何矩同样也存在关系 z ，。；= = ；q ；j 刍t ( q ，) ( 1 。， z z 。：，一。：，+ 。 1 1 5 复数矩( c o m p l e xm o m e n t ) 的介绍 ( ，+ 们阶的复数矩定义为： c ，。= 二( x + 妒) ( x i y ) 9 ，( 墨y ) & d y 同样，复数矩也可以表示成几何矩的形式： c 。= 委p 台q ( ，p m qm 七c 矿。一圳 1 1 6c h e b y s h e v 矩( c h e b y s h e vm o m e n t ) 的介绍 ( 1 2 1 ) ( 1 - 2 2 ) ( 1 - 2 3 ) 上述z e r n i k e 和l e g e n d r e 矩等采用连续的正交多项式作为基础系，具体计算 时需要：( 1 ) 对连续的积分作数值上的近似，也就是离散化；( 2 ) 坐标空间归一化。 对积分做离散化造成了z e r n i k e 矩和l e g e n d r e 矩计算上的不精确，而坐标变化则 消耗了更多计算时间。c h e b y s h e v 矩采用离散的正交多项式作为基础系，本身就 是离散的形式，因而避免了离散化带来的误差，另外，计算c h e b y s h e v 矩的时候 不需要对坐标做变换，就减少了计算时间，而且凭借c h e b y s h e v 多项式本身的对 称性，计算时间也可以大大减少p 1 。 c h e b y s h e v 矩的基函数为离散的正交c h e b y s h e v 多项式，后者满足： t ，( x ) f 目( x ) = p ( p ，n ) 8 ，q 0 p ，g n 一1 。2 。 。，( 1 2 4 ) 一i ，、2 、， 其中：p ( p ，) = ，( x ) c h e b y s h e v 多项式为： “妒鸯矿。“瑚 m z s ， ，+ g 阶c h e b y s h e v 矩定义如下： 7 j 。= l o ( p ，n ) p ( q ，) r ，( x ) f 。 ) ，( e 只g = o ，l 一2 ，n l ( t - 2 6 ) 东南大学硕士学位论文 反变换如下： n - 1 n 一2 f ( x ，y ) = l 。f 。( r ) f 。( y )( 1 2 7 ) m = on = o 由于c h e b y s h e v 矩本来就是以离散形式提出的，因而不需要对坐标做任何近 1 l j , 并l i 变换，所以它对于处理数字图像具有比较好的精确性。 1 1 7 小波矩( w a v e l e tm o m e n t ) 的介绍 小波矩的定义为”0 j ： 。2js q ( r ) 杪。( r ) r d r ( 1 2 8 ) s 。( r ) = j ，( r ，o ) e s q o d 0( 1 2 9 ) 。( r ) = 2 m 2 ( 2 4 r 一以) f 1 3 0 ) 其中m = 0 ，1 ，2 ，3 ，n = 0 ，1 2 ，2 m 1 ，q = 0 ，1 ，2 ，3 。q j ( r ) 为小波母函数。 小波矩也可以写成： 。= jj ( r ，臼妒。p ) e j q 8 r d r d o( 1 31 ) 从上面的定义中，我们可以看到小波矩和z e r n i k e 矩一样具有旋转不变性， 其证明与z e r n i k e 矩的旋转不变性证明类似。倘若图像旋转p 角，那么旋转后 的小波矩为： c 。= j i f ( r ，臼沙。( f ) e j q ( o + f 1 ) r d r d o = e , n , q e ”9( 1 3 2 ) k 。| l = | 阪。8 ( 1 3 3 ) 同时，由于小波的多分辨率特性，它还可以很好的提取图像的局部信息，这 列。模式识别是很有用处的。 对于小波矩我们在后面还有更进一步的叙述，所以在此就不多赘述。 1 2 本文工作及论文组织 本课题的重点是讨论矩的快速算法以及矩在模式识别中的应用。具体的工作 1 l e g e n d r e 矩快速算法的研究 2 z e r n i k e 矩在模板匹配中的应用 第一章绪论 一-_一 3 基于小波矩的图形识别 参考文献 11m kh u ，”p a t t e r nr e c o g n i t i o nb ym o m e n t si n v a r i a n t s ”，p r o c i r e ，v 0 1 4 9 ， p p 1 4 2 8 ，s e p t1 9 6 1 2 m k h u ，”v i s u a lp a t t e r nr e c o g n i t i o nb ym o m e n ti n v a r i a n t s ”，r e t r a n so n j ”加，m a r i o nt h e o r y ，v o li t - 8 ，p p 1 7 9 - 1 8 7 ，f e b1 9 6 2 i3 1sa d u d a n i ，e ta l ，”a i r c r a f ti d e n t i f i c a t i o nb y m o m e n ti n v a r i a n t s ”，i e e et r a n so n c o m l ) u l e r s ，v o lc 一2 6 ，n o 1 ，p p 3 9 4 5 ，j a n u a r y19 7 7 l4 1 s p e i ，c ，l i n ， n o r m a l i z a t i o n o fr o t a t i o n a l l y s y m m e t r i cs h a p e s f o r p a t t e r n r e c o g n i t i o n ”，p a t t e r nr e c o g n i t i o n ，v 0 1 2 5 ，p p 9 1 3 9 2 0 ，1 9 9 2 【5 e b i g o r g n e ，e ta l ，“a ni n v a r i a ml o c a lv e c t o rf o rc o n t e n t b a s e di m a g er e t r i e v a l ”， 1 5 ”i n t e r n a t i o n a lc o n f e r e n c eo n p a t t e r nr e c o g n i t i o n ，v 0 1 1 ，p p 1 0 1 9 - 1 0 2 2 ，2 0 0 0 【6 6m r t e a g u e ，”i m a g ea n a l y s i sv i at h eg e n e r a lt h e o r yo fm o m e n t s ”，jo p t , s o c a m v 0 1 7 0 ，n o 8 ，p p 9 2 0 * 9 2 9 ，a u g u s t1 9 8 0 7 1 ak h o t a n z a d ，e ta l ，“i n v a f i a n ti m a g er e c o g n i t i o nb yz e r n i k em o m e n t s ”，i e e e t r a n ，o np a t t e r na n a l y s i sa n dm a c h i n ei n t e l l i g e n c e ，v 0 1 1 2 ，n o 5 ，p p 4 8 9 4 9 7 ，m a y 1 9 9 0 【8 jm p a w l a k ，“o n t h er e c o n s t r u c t i o na s p e c t so fm o m e n td e s c r i p t o r s ”，i e e et r a n ， o nm f l _ ) r m a t i o nt h e o r y ，v 0 1 3 8 ，n o 6 ，p p1 6 9 8 - 1 7 0 8 ，n o v e m b e r1 9 9 2 p 】r m u k u n d a n ，e ta t ，“i m a g ea n a l y s i sb yt c h e b i c h e fm o m e n t s ，i e e et r a n so n i n a g e p r o c e s s i n g , v 0 1 1 0 ，n o 9 ，s e p t e m b e r2 0 0 1 10 1s a ，d u d a n i ，k j b r e e d i n ga n dr b m c g h e e ，”a i r c r a f ti d e n t i f i c a t i o nb y i l l o m g l l ti v a r i a n t s ”，i e e et r a n s0 nc o m p u t e r s , v 0 1 c 一2 6 ，n o 1 ，p p 3 9 - 4 5 ，j a n u a r y 1 9 7 7 1 l l sm a i t r a ，“m o m e n ti n v a r i a n t s ”，p r o c 1 e e e ，v 0 1 6 7 ，p p 6 9 7 6 9 9 ，a p r i l19 7 9 i2 1s o b e i k a s i m ，e ta l ，“p a t t e mr e c o g n i t i o nw i t hm o m e n ti n v a r i a n t s ：ac o m p a r a t i v e s t u d ya n dn e wr e s u l t s ”，p a t t e r nr e c o g n i t i o n ，v 0 1 2 4 ，n o 1 2 ，p p 1 1 1 7 - 1 1 3 8 ，1 9 9 l fi3 cht h e ，rtc h i n ，“q ni m a g ea n a l y s i sb yt h em e t h o d so fm o m e n t s ”，t e e e h t t n s o p a t t e r na n a l y s i sa n dm a c h i n ei n t e l l i g e n c e ，v 0 1 1 0 ，n o 4 ，p p 4 - 9 6 - 5 1 3 j u l y - 7 东南大学硕士学位论文 1 9 8 8 14 s s r e d d i ，“r a d i a la n da n g u l a rm o m e n ti n v a r i a n t sf o ri m a g ei d e n t i f i c a t i o n ” 1 e i z el e a n so n p a t t e r na n a l y s i s a n dm a c h i n e i n t e l l i g e n c e ，v 0 1 p a m i - 3 ，n o2 ， p p2 4 0 2 4 2 ，m a r c h19 8 1 15 ys a b u m o s t a f aa n dd p s a l t i s ，“i m a g en o r m a l i z a t i o nb y c o m p l e xm o m e n t s ” i e e e t r a n s o n p a t t e r n a n a l y s i s a n d m a c h i n e i n t e l l i g e n c e ，v 0 1 p a m i 一7 ，p p4 6 5 5 ，j a n j 9 8 5 16 】ds h e n ，h o r a c eh s i p ，“d i s c r i m i n a t i v ew a v e l e t s h a p ed e s c r i p t o r s f o r r e c o g n i t i o n o f 2 一dp a t t e r n s ”，p a t t e r n r e c o g n i t i o n ，v o l3 2 ，p p 1 5 1 1 6 5 ，1 9 9 9 ，8 第= 章l e g e n d r e 的快速算法研究 第二章l e g e n d r e 矩的快速算法研究 i 自从h u 1 2j 提出矩的不变量以来，矩在模式识别、图像分析等许多领域【3 4 i 都有广泛的应用。迄今为止，常见的矩描述子大致可以分为以下几种：几何矩、 正交矩( l e g e n d r e 矩、z e r n i k e 矩) 、复数矩和旋转矩。其中由于几何矩 6 1 0 】提出 的时间最早且形式简单，对它的研究最为充分。而正交矩描述的图像虽然具有最 少的信息冗余度，但由于它的复杂性，有关正交矩的快速算法的研究还很少 1 0 - t 2 】。 s h u 等人【l l 】针对边界为多边形的二值图象采用格林公式将面积分转化为对边界 的线积分，然后采用迭代方法进行计算，使计算复杂度由d ( o ) 降低到0 ( v ) ：z h o u 等人【1 2 j 把基于象素点的二维l e g e n d r e 矩转换为线段的形式来计算，在计算出所 有线段的积分后，使用扩展的h a t a m i a n 滤波方法来计算一维的l e g e n d r e 矩，也 有效地缩短了计算时间。本章旨在提出两种基于图像块描述方法的计算l e g e n d r e 矩的快速算法。 对一幅图像最普通的描述方法是一个二维数组，每个元素都表示其中相关点 的灰度，对于二值图像来说，元素值就是1 或者0 。这样描述图像的方法就使得 计算的时候一次只能计算一个象素点，于是很多的研究都把眼光放在如何更方 便、快速地描述一幅图像上。目前对图像的描述主要存在两种方法：基于边界的 描述方法和基于区域的描述方法，如链码描述方法【7 l 和块描述方法阳】，它们都对特 定的算法起到了很好的作用。s p i l i o t i s 等人【引将图像块描述方法应用到几何矩的 汁算巾，减少了计算复杂度，缩短了计算时间。本文旨在把图像块描述方法推广 到l e g e n d r e 矩的计算中，并在此基础上提出两种快速算法。 2 1 图像块描述方法 剥。一幅二值图像他”来说，我们假定物体点的值为1 ，而背景点的值为0 ， 即： ，c x ，y ，= 翼芒。 le l ”d 为同标区域。 j f i 于= 值图像的这种性质，我们可以知道，在二值图像中必然存在很多值为 1 的矩形，这些矩形在本文中就称作樊，它们的边平行于图像的轴，并且包含整 数个级素。最为极端的情况就是，一个块只包含一个象素。 如果说我们将图像表示成一系列块，这些块互不重叠，也就是说物体的每个 东南大学硕士学位论文 象素部属于一个块且仅属于一个块，那么我们就把图像的这种表示方式称为留缪 贸赭述方琅聊q 舻b l o c k r e p r e s e n t a t i o n ) 。根据以上说法，我们可以确切的给出图 像块描述方法的定义： 1 图像块是图像中的一个矩形区域，边平行于图像的轴，并且一个块中的 象索具有相同的灰度值。 2 如果一幅图像用图像块来表示，并且每个象素都属于且只属于一个块， 那就说这个图像是用块来描述的。 根据以上这两个定义，我们可以看出图像块描述方法并不具有唯一性，也就 是说，当我们给定一副图像的时候，我们可以有很多种方式将其进行分块，并且 都同时满足以上两个条件。实际上。虽然具有不同的分块方式，但是这对图像块 描述方法的应用并没有什么影响。 在本章中，我们采用一种简单并且快速的分块方式。我们对每行y 都进行扫 描，将该行中扫描的区间与上面一次分块的结果做比较，以确定该区间是属于上 个块还是新块的开始。 具体算法如下： 步骤l ：对图，的每一行j ，进行扫描，找到第y 行的目标区问。 步骤2 ：将这些区间和那些含有第弘，行象素的块进行比较。 步骤3 ：如果一个区间和任何块都不匹配，那么这就是一个新块。 步骤4 ：如果该区间和某个块匹配，那么此块的最后一行就是第y 行。 循环这四个步骤直至图像最后一行。 通过上述方法，我们就可以得到一系列的块，用块来描述这幅二值图像就是 f ( x ，y ) = 地：j = o ，1 ，k l j( 2 1 ) 其中七是块的个数。对每个块我们都只需要记录四个坐标，即块的左上角坐 标和右下角坐标。这个分块的算法速度计算复杂度比较低，因为它只需要对图像 进行扫描和判断，并不需要进行任何运算，因而速度也很快。图2 1 ，是用该算法 划字母j 分块后的结果： 图2 - 1 ，字母j 的分块结果 这种方法并不是最优的分块方法，在o r l o w s k i t l 4 1 的文章中提出了新的优化的 i 矧像分块方式，但是，虽然这种优化的分块方式可以节省点分块后的计算量， 第= 章l e g e n d r e 的快速算法研究 却增加了分块时的计算量，所以本文并未采用他的分块方法，而是选择了这种简 单有效的方法。 2 2l e g e n d r e 矩的计算 对于一密度函数为以ty ) 的二维图像，其p - i - q ) 1 ：f fl e g e n d r e 正交矩的定义为： 矿鲤三尝堑业此o ( r ) 只( 彬( w ) d x d y ，( 2 - 2 ) 式中，_ ) 为p 阶l e g e n d r e 多项式，其定义为： 聃，= 古静，。矗锅x p - 2 k ，x e h 川任s ， 对于数字图像，双重积分可以由双重求和来近似，通常采用如下形式： 五。：盟掣芝芝，( x i , y s ) p a 一) 巴 ，) x a y ，1 ( 2 - 4 ) 其中a x = 蔚+ l - x i = 2 n , a y = y s + , - y = 2 n ，分别代表在x 和y 方向上的取样间隔。 对二值图像来说，互。就可简化为： 互。= 芈k 萎- i n 萎- i 啪) ， ( 2 - 5 ) 在计算过程中，我们使用l e g e n d r e 多项式的叠代性质： 只= 等垆，( 圹鬲, 只一，川( 2 - 6 ) 其t n ( z ) = 1 , p l ( x ) = x 。 2 2 1 累加方法 对二值图像进行分块，如果分成k 块，那么l e g e n d r e 矩的值就可以写成( 2 5 ) q 变化形式 ， ，。：芝霞：下( 2 p + 1 ) ( 2 q + 艺- 芝芝o ( z ) o ( 力( 2 - 7 ) i = 0 jv i = 0 h l ， y = y l j 1 。_ _ | 1 ( 。，y 地) 和( x ：j ，儿， ) 分别是一个块的左上角和右下角坐标。 巾 二块为矩形，故而对于第b ，块： 东南大学硕士学位论文 1 2b l ，2 “ “2b i r1 乃。= 巴( x ) 0 ( y ) = 0 ( x ) 【尸q ( y ) + p d y 。h + 1 ) + + p d y ： ) j x = 。l , b iy = y l b ,”4 ( 2 8 ) 。2b ly2 - = 0 ( x ) ) = p ，) ( 6 ，) 。2 x 1hyy i “ 于是求k 阶l e g e n d r e 矩的问题就转化为先用( 2 - 8 ) 式求出每个块的l e g e n d r e 矩的值，然后将各块的值相加，再乘以系数坚旦三；! ；望业的问题。 v 一 对于( 2 - 8 ) 式的计算可以分成两部分，即： x 2 , b iy 2 “ s p ( 6 。) = 0 ( x ) ，( 6 ，) = 名 ) ( 2 9 ) 。2 “y 3 m 由于( 2 9 ) 式中两者的计算方式一样，因此我们只考虑其中的一个求和式。 记民，= x ： 一一 + l 为块的长度即象素点个数，则 ，( ”：薹b g 。+ 皿)( 2 - 1 0 ) j = o 采用s h u 等人“1 提出的计算l e g c n d r e 多项式的公式： p a x + a ) = ( d ) 巴一，( x ) ，w i t h 筋( 出) = l ，砌0( 2 1 1 ) 其中( 订) 的表达式见 1 1 。 利用硝( 出) = 1 我们可以得到： 匕。b ，+ ( ，+ 1 ) r ) 一0 。b 。b + ，缸j = 匕+ 1 ( r + r + j a r ) 一巴“( x 1 乜+ ，羔) = 硝“( 缸) 0 。，( 一 + 弘r ) 一0 + 。( 一“+ 缸) ，= o p + i = ( 出) 0 + ，( r + 弘x ) ，i 将( 2 1 1 ) 式等式两边从j = 0 到一l j 求和得到 ，) j j + 0 ，。+ d b , a v ) 一o + 。g ) ：6 o r 1 + 1 硝+ ( 缸) 0 。，( + 肚) j = o i = 1 引入记号 吒( 也) = 名+ b q + 气缸) 一0 + 。b 。) ( 2 1 2 ) ( 2 - 1 3 ) r 2 1 4 ) 第二章l e g e n d r e 的快速算法研究 二是 p + l“i 1 f + i ，：( 6 ，) = 硝“( 血)