第 16 卷 第 10 期 2004 年 10 月
计算机辅助设计与图形学学报
J OU RNAL OF COMPU TER2A IDED DESIGN & COMPU TER GRAPHICS
Vol116 , No110
Oct1 , 2004
灰度图像质心快速算法
王 冰 职秦川 张仲选 耿国华 周明全
1362
计算机辅助设计与图形学学报
2004 年
NN
∑∑ m 10 =
i f ( i , j) ,
j =1 i =1
NN
∑∑ m 01 =
j f ( i , j) 1
j =1 i =1
ic =
m 10 m 00
(4)
jc =
m 01 m 00
(5)
点 p ( ic , jc) 即为质心坐标1
令
N
∑q) 和中心矩 (μpq) 定义为
∞∞
∫∫ m pq =
x pyqf ( x , y) d x d y ,
- ∞- ∞
∞∞
∫∫ μpq =
( x - x ) p ( y - y) qf ( x , y) d x d y ,
- ∞- ∞
其中 p 和 q 是非负的整数1 对离散化的数字图像 ,
m 03 , m 12 , m 21) 描述物体的方位和斜度[1 ]1 基于低
阶的 10 个矩 , Hu[2 ] 给出一组不变矩 , 不变矩有平 移 、旋转 、缩放不变的特性1 不变矩独特的特性获得 广大图像处理工作者的青睐 ,并在图像分类 、模式识 别 、计算机视觉等图像处理和分析领域获得广泛的 应用1 由于求矩过程复杂 , 运算量大 , 限制了它的应 用1 自 20 世纪 80 年代以来 , 快速求矩算法不断涌 现1 从算法原理分析 ,文献[3 26 ]基于 δ方法将图像 分解为行 ,图像的质心或矩是各行质心或矩的综合 ; 文献[7 29 ]运用格林理论方法 ,该方法基于格林公式 f ( x , y) d x d y = ∮[ M d x + N d y ] , 把一个图像函数 求质心或矩的二重积分转换为对图像边缘的一重积 分 ;文献[10 211 ]采用图像变换方法将图像函数转换 为其他函数 ,利用变换后函数的独有特性简化计算1 在这些算法中 ,大都计算到第 3 阶矩1 由于第 0 、第 1 阶矩 (即求物体的质心) 具有最为基础和最为广泛的 应用 ,并且由矩和中心矩定义知 ,质心又是求中心矩 的基础 ,人们对快速求取质心或前 2 阶矩给予更多 的关注[12214 ]1 文献 [ 12 214 ]介绍和发展了一种称之 为快速搜索质心算法 , 利用目标质心与目标上所有 各点间距离之和值最小的原理 , 快速求取质心1 从 算法适用性上看 ,以上算法大都适用于二值图像 ,只 有文献[9 ,11 ]中算法适用于灰度图像1 由于实际中 的图像大都是灰度图像 , 因此对灰度图像求质心具 有更广泛的用途和实际的意义1 本文提出一种基于 函数转换的求质心算法 ( Function Transformation Al2 gorit hm ,F TA) ,该算法适用于灰度图像1 和其他求 灰度图像质心算法相比 ,本文算法具有更高的计算 效率1
设
f 1 ( n) = [5 ,4 ,6 ,2 ,3 ] ,
f 2 ( n) = [1 ,3 ,4 ,2 ,5 ]1 则
F1 ( n) = [1 , - 2 ,4 , - 1 ,3 ] ,
F2 ( n) = [1 ,4 ,8 ,10 ,15 ]1
N
∑f 1 ( n) f 2 ( n) = 5 ×1 + 4 ×3 +
可见 ,质心即是第 0 和第 1 阶矩1
通常 ,前 10 个矩 ( p + q ≤3) 获得最为广泛的应
原稿收到日期 :2003206220 ;修改稿收到日期 :20032102131 本课题得到国家自然科学基金 (60271032) 资助1 王 冰 ,男 ,1954 年生 ,副教授 , 主要研究方向为图像处理和分析 、计算机视觉 、模式识别及算法1 职秦川 ,男 ,1964 年生 ,硕士 ,讲师 ,主要研究方向为图像处理 、计算机图形学 等1 张仲选 ,男 ,1962 年生 ,硕士 ,讲师 ,主要研究方向为图像处理 、信息安全等1 耿国华 ,女 ,1955 年生 ,博士 ,教授 ,博士生导师 ,主要研究方向 为人工智能 、信息技术1 周明全 ,男 ,1954 年生 ,教授 ,博士生导师 ,主要研究方向为图像处理和分析 、虚拟现实 、可视化技术1
令 S (1 , j) = f (1 , j)
(12)
S ( i , j) = S ( i - 1 , j) + f ( i , j) ,
i = 2 ,3 , …, N ; j = 1 ,2 , …, N
(13)
首先证明式 (10)1
证明1 按照式 ( 12) , ( 13) , 并注意到式 ( 6) , 式
1
此时 ,
N
N
∑ ∑ f 1 ( n) f 2 ( n) =
F1 ( n) F2 ( n) = F2 ( N )
n =1
n =1
(2)
如果 f 1 ( n) = n ,则
- 1 , n = 1 ,2 , …, N - 1
F1 ( n) =
1
N, n = N
此时 ,
N
N
∑ ∑ f 1 ( n) f 2 ( n) =
以上二式变为
NN
∑∑ m pq =
ipjqf ( i , j) ,
j =1 i =1
NN
∑∑ μpq =
( i - ic) p ( j -
j =1 i =1
其中 ( ic , jc) 为质心坐标 ,且
jc) qf ( i , j) ,
ic = m 10 / m 00 , jc = m 01 / m 001
(10)
N- 1
∑ m 10 j = N ×S ( N , j) -
S ( i , j)
(11)
i =1
式 (10) , (11) 中的 S ( N , j) 相当于式 (2) 的 F2 ( N ) ,
S ( i , j) 相当于式 (3) 的 F2 ( n) 1
下面证明式 (10) , (11)1
n =1
6 ×4 + 2 ×2 + 3 ×5 = 60 ,
N
∑F1 ( n) F2 ( n) = 1 ×1 - 2 ×4 +
n =1
4 ×8 - 1 ×10 + 3 ×15 = 601
如果 f 1 ( n) = 1 ,则
0 , n = 1 ,2 , …, N - 1
F1 ( n) = 1 , n = N
(6)
i =1
N
∑ m 10 j = i f ( i , j)
(7)
i =1
则
N
∑ m 00 =
m 00 j
(8)
j =1
N
∑ m 10 =
m 10 j
(9)
j =1
注意到式 (6) 满足式 (2) 的条件 , 式 (7) 满足式 (3) 的
条件1 从式 (2) , (3) 有
m 00 j = S ( N , j)
Key words geomet ric moment s ; center of mass ; fast algorit hm ; pattern recognition ; computational co mple xit y
1 引 言
对一幅 2D 连续图像 f ( x , y) ( ≥0) , p + q 阶矩
F1 ( n) F2 ( n)
(1)
n =1
n =1
其中 ,
F1 ( n) = f 1 ( n) - f 1 ( n + 1) ,
F2 ( n) = F2 ( n - 1) + f 2 ( n) ,
F2 (0) = 0 ,
f 1 ( N + 1) = 01 式 (1) 证明见正文后附录1
下面验证式 (1) 的正确性1
© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
10 期
王 冰等 :灰度图像质心快速算法
1361
用 ,而且它们都有实在的物理意义10 阶矩 ( m 00) 为 物体的质量 ; 1 阶矩 ( m 10 , m 01) 表示物体的质心 ; 2 阶矩 ( m 20 , m 02 , m 11 ) 表示旋转半径 ; 3 阶矩 ( m 30 ,
运算1
212 算法原理
几何矩 m pq ( p , q = 1 ,2 , …) 定义为
NN
∑∑ m pq =
ipjqf ( i , j) ,
j =1 i =1
则第 0 阶和第 1 阶矩为
NN
∑∑ m 00 =
f ( i , j) ,
j =1 i =1
© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
2 算 法
211 基本思想
设有二 个 大 小 同 为 N 的 一 维 数 组 f 1 ( n ) 和 f 2 ( n) , n = 1 , 2 , …, N 1 则这两个数组的乘积等于
将其中的一个数组 f 1 ( n) 差分与另一个数组 f 2 ( n) 累进求和后的乘积 ,即
N
N
∑ ∑ f 1 ( n) f 2 ( n) =
(西北大学计算机科学系 西安 710069)
摘 要 对矩因子 x pyq 做差分变换为函数 F1 () ,将图像函数 f ( x , y) 做累进求和变换为函数 F2 ()1 用 F1 () 和 F2 () 相乘求取质心1 由于 0 阶和 1 阶矩因子中的 p , q 不大于 1 ,经差分后的 F1 () 除右端点外 ,其值都为 1 ,乘 1 的运算当 然可以不做 ,从而消去了乘法运算1 对任意大小和任意级别的灰度图像 ,乘除法运算次数仅为 3 次 ,而加法运算次数 也有降低1 文中算法计算结果精确 ,其运算效率高于已有其他算法1