数学形态学骨架化及重建.pdf

第2卷 第10期 1997年10月 中国图象图形学报 Journal of I mage and Graphics Vol 2 No 10 Oct 1997 收稿日期 199621229 收到修改稿日期 1997205204 数学形态学骨架化及重建 周 南 崔 屹 北京邮电大学机电工程系 北京 100088 摘 要 给出了用数学形态学方法获取二值图象骨架 及利用骨架完全或部分重建图象的算法和实例 关键词 数学形态学 骨架 图象重建 1 引 言 骨架是图象几何形态的一种重要拓扑描述 利 用骨架表示原始图象 可以在保持图象重要拓扑特 征的前提下 减少图象中的冗余信息 因此 被广泛 应用于生物形状描述 模式识别 工业检测 定量金 相以及图象压缩编码等领域 用骨架描述图象的方法最早是由Blum提出来 的 1 他使用了中轴的概念 在t 0时刻 将图象边 界上所有点同时点燃 火焰以相同速度向图象内部 蔓延 当波前相遇时 火焰熄灭 火焰熄灭处所有点 的集合就构成了中轴 即骨架S KF 如果x为中轴 上的点 t为火焰从点燃到在x点处熄灭所经历的 时间 则t与x之间的关系可用函数m id x 表示 即t m id x 函数m id x 称为中轴函数 可以用 于图象重建 骨架还可用最大圆盘的概念来定义 设D为图 象S中的一个内切圆盘 即至少有两点与图象边界 相切 如果D不是图象S内部任何其它圆盘的子 集 则称为最大圆盘 此时骨架S KM 可定义为图象 内部所有最大圆盘圆心的集合 最大圆盘的半径可 用于图象的重建 上面两种方式定义的骨架在多数情况下满足关 系 S KF S KM 在特殊情况下有 S KF S KM 差异 主要出现在端点处 2 故一般地有S KF 0S r X 图5 离散图象X的骨架化及重建 结构元素B为方形 Fig 5 Skeletonization and reconstruction of digital i mage 其中Sr X 可用下面的形态学运算得到 Sr X X rB X rB drB 1 r 0 且 X rB 式中 结构元素B为一单位圆盘 d r为一微小正实 数 r为一实数且r 0 显然rB为半径为r的圆 d rB是半径为d r的微小圆盘 运算X rB表示rB 对X的腐蚀 表示集差 drB为d rB对 的开运算 即 d rB d rB 附录给出了对公 式 1 的证明 图3 形态学图象重建 Fig 3 I mage reconstruction 利用骨架子集Sr X 及其相应的最大圆盘rB 可按下式唯一地重建原始图象 X r 0 S r X rB 2 如果只对部分骨架子集使用式 2 则可部分重建图 象 在图象压缩中 可以用此方法达到控制图象压缩 失真度和压缩率的目的 处理离散图象时 由 于在离散平面中不存在 精确的圆盘 可用其它形 状来近似 对于采样栅格 为正六角形的离散图象 可取等边六边形作为近 似圆盘 在直角栅格中可 采用图4所示的结构元 素近似圆盘 a 圆形 b 方形 c 菱形 号表示原点 图4 数字圆盘 Fig 4 D igital disks 若X为Z2上的离散二值图象 并且非空有界 则X的形态学骨架S K X 可表示为 S K X N n 0S n X 3 式中Sn X X nB X nB B 4 n N时 X nB 0 Sn X 表示X的第n个骨架子集 表示集差 B 表示半径为1的数字圆盘 nB表示半径为n的数字 圆盘 n 0时 nB为原点象素 N表示X中最大的 最大圆盘的半径 可以看出S K X 是N 1个骨架 子集的并 离散二值图象X可以利用骨架子集Sn X 的 索引n 通过对N 1个子集做膨胀实现完全重建 X N n 0 S n x nB 5 如果只使用N k个骨架子集 如取n k N 则 可以部分地重建目标 X N n k S n x nB XkB 6 图5给出了离散二值图象骨架化及重建的示例 3 形态学骨架化及重建的快速算法 利用形态学方法进行骨架化运算时 随着n的 317第10期 周南等 数学形态学骨架化及重建 1994 2009 China Academic Journal Electronic Publishing House All rights reserved 增大 运算量呈平方增长 因此有必要寻求快速算 法 考虑N N大小的二值图象X 结构元素为图 4所示的圆形 如果直接计算X B 需要作21次基 本运算 将B按图6所示方式分解 即将B分解为 B B1 B2 B3 则X B X B1 B2 B3 X B1 B2 B3 只需要进行 3 3 5 N 2 次基本 运算 计算复杂度降低45 结构元素B越复杂 运 算效率提高幅度越显著 基于上述考虑 在形态学骨 架计算中 将nB分解为 nB B B B B n 7 则式 4 可表示为 S0 X X X B B S1 X X B X B B B SN X X B B N X B B N B B 8 B B1 B2 B3 图6 圆形结构元素的分解 Fig 6 Structuring element decomposition 将式 8 代入式 5 便可得到X的骨架 图象重建 时 可采用相同的方法 即 Sn X nB Sn X B B n个 9 代入式 5 得 X SN x B SN 1 x B SN 2 x B S0 x 10 图7给出了计算图象的骨架子集 及利用骨架 子集重建原始图象的快速算法 在使用上述分解方 法时 如果基本结构元素B可分解成为更简单的结 构元素 算法的速度还会有更大的提高 图8和图9 给出了利用上述快速算法获取二值图象形态学骨架 并重建的实例 图8中 a 为原始图象 b 为形态学 骨架 结构元素为圆形 c 为形态学骨架 结构元 素为菱形 d 用图c部分重建的图象 舍去前三级 骨架点 图9中 a 为原始图象 b 为形态学骨架 结构元素为方形 c 为形态学骨架 结构元素为 圆形 d 用图c部分重建的图象 舍去前六级骨架 点 图7 骨架化和重建的快速算法流程图 Fig 7 Fast algorithm s of skeletonization and reconstruction 图8 用形态学方法获取汉字骨架并重建 Fig 8 Skeleton and reconstruction of Chinese characters 参 考 文 献 1 Blum H A Transformation for Extracting New Descriptors of Shape Models for the Perception of Speech and V isual Form s 417 中国图象图形学报 第2卷 1994 2009 China Academic Journal Electronic Publishing House All rights reserved 图9 用形态学方法获取二值图象骨架并重建 Fig 9 Skeleton and reconstruction of a binary i mage 1967 2 Serra J I mage Analysis and M athematical Morphology Academ ic Press 1983 3 M arogosP A SchaferRW MorphologicalSkeleton Representation and Coding of BinaryI mages IEEE Trans Acoust Speech and Signal Processing Vol 1986 ASSP 34 5 1228 1244 4 Kenji Shoji Generalized Skeleton Representation and Adaptive Pretangular Decomposition of Binary I mage SP IE Vol 1769 I mage A lgebra andMorphological I mage Processing III 1992 附 录 A 对公式 1 的证明 假设Sr X 为X的骨架子集 则对公式 1 的 证明可以从两方面考虑 1 Sr X 中的点必定是X内半径为r的最大 圆盘的圆心 2 X内所有以r为半径的最大圆盘的圆心所 组成的集合必为Sr X 证明 1 根据式Sr X X rB X rB drB 可 以得到Sr X X rB 对于 x Sr X 有x X rB 根据腐蚀定义 可以得到rBx X rBx表示对 rB作关于x的平移 即rBx为X内的圆盘 假设rBx不是X内的最大圆盘 则在X内必然 存在一个圆盘 r d r By d r 0 使得rBx r d r By因为 r d r By X 所以y X r d r B 由关系式rBx r d r By根据形态学运算的 递增性得 rBx rB r d r By rB 根据腐蚀运算的平移不变性得 rB rB x r d r B rB y 即x d rBy 因为y X r d r B 有 d rB y X r d r B d rB X rB d rB d rB X rB drB 即x X rB drB 根据 X rB drB X rB Sr X 可以推导 出x Sr X 与前提条件x Sr X 相悖 所以假设 不成立 rBx是X内的最大圆盘 2 假设rBx是X内的最大圆盘 而且x Sr X 即x X rB 且x Xr X 根据Sr X X rB X rB drB 可以得 到x X rB drB 根据膨胀定义 可得rBx X rB drB rB X r d r B r d r B 对所有y X r d r B 有 r d r By X r d r B r d r B 则rBxr 所以对任意x总存在y使得 rBx r d r By 所以rBx不是最大圆盘 假设不成 立 证毕 周南 北京市邮政科学研究所 硕士 目前研究方向数学形态学图象处理 517第10期 周南等 数学形态学骨架化及重建 1994 2009 China Academic Journal Electronic Publishing House All rights reserved Skeleton ization and Reconstruction via MathematicalM orphology Zhou N an Cui Yi B eijing U niversity of Posts and T elecomm unications B eijing 100088 Abstract This paper presents algorithm s and applications of acquiring skeleton of binary image and completely or partially reconstructing binary image fromits skeleton using mathematical morphology method Keywords M athematicalmorphology Skeleton Reconstruction 上接700页 贾晓光 毕业于哈尔滨工业大学无线电系获学士和硕士学位 留学英国南安普敦大学电 子学与计算机科学系获博士学位 现在是哈尔滨工业大学航天学院教授她目前从事图象处 理 基于图象特征信息的目标提取与识别 卫星及有效载荷的电子系统 以及卫星应用的研 究和开发 The Up to date Development of Data Compression Techn iques in Space based Remote Sensing Jia Xiaoguang W ang L ei D ep t of A stronautio E lectroics Op to2E lectronic Engineering H arbin Institute of T echnology H aerbin 150001 Abstract The state2of2the2art of image compression techniques are summarized in the paper whilst the emphasis is specially on those for data from space2borne remote sensors Suggestions of using various techniques in space2based remote sensing are proposed The system configurations on space2based lossless and lo