章毓晋图像分析课件-03.pdf

1?章毓晋?清华大学电子工程系 100084 北京图象工程（中）章毓晋 (TH-EE-IE)第2页第3章第3章数字化的图象第3章数字化的图象•图象工程：数字化图象（digitalized image）•图象分析：离散目标空间离散点的集合•数字拓扑（digital topology）研究离散目标内部点之间的局部性质•离散几何（discrete geometry）刻画离散目标的几何性质（全局）章毓晋 (TH-EE-IE)第3页第3章第3章数字化的图象第3章数字化的图象3.1 图象采集网格3.2 数字化模型3.3 离散直线性3.4 距离变换3.5 3-D图象中的连通和拓扑章毓晋 (TH-EE-IE)第4页第3章3.1 图象采集网格图象采集网格三种不同的采样模式三种不同的采样模式图象采集：用一个离散的模式采样三种规则的形式：三角形正方形六边形网格：将图象平面分解成小单元的集合章毓晋 (TH-EE-IE)第5页第3章3.1 图象采集网格图象采集网格三种不同的图象网格三种不同的图象网格图象网格与采样模式互补三角形模式 ⇔ 六边形网格正方形模式 ⇔ 正方形网格六边形模式 ⇔ 三角形网格(1)正方形网格广泛使用：直观，无边界问题结构问题：“连通悖论” {第10章}章毓晋 (TH-EE-IE)第6页第3章3.1 图象采集网格图象采集网格三种不同的图象网格三种不同的图象网格(2)三角形网格相邻象素：有共同边• 粗实线连接相邻象素• 细线表示三角形网格• 点线对应采样模式对象素p，它的6-邻域记为N6(p) p2章毓晋 (TH-EE-IE)第7页第3章3.1 图象采集网格图象采集网格三种不同的图象网格三种不同的图象网格(3)六边形网格N3(p)： 有公共边邻域过于稀疏N12(p)： +有公共顶点pp章毓晋 (TH-EE-IE)第8页第3章3.2 数字化模型数字化模型与图象采集密切相关3.2.1 数字化模型基础3.2.2方盒量化3.2.3网格相交量化3.2.4目标轮廓量化章毓晋 (TH-EE-IE)第9页第3章3.2.1 数字化模型基础两个定义两个定义预图象预图象（pre-image）给定一个离散点集合P，一个其数字化为 P的连续点集合 S 称为 P 的预图象域域（domain）由所有可能的预图象 S 的并集所定义的区域称为 P 的域章毓晋 (TH-EE-IE)第10页第3章3.2.1 数字化模型基础将一个正方形图象网格覆盖到连续的目标S 上，一个象素用一个正方形网格上的交点p表示， 该象素当且仅当p ∈ S时属于S的数字化结果S在图中用阴影部分表示，黑色圆点代表属 于S的象素p，所有p组成集合P章毓晋 (TH-EE-IE)第11页第3章3.2.1 数字化模型基础不一致性不一致性(1) 一个非空集合S有可能映射到一个空的数字化集 合中(2) 该数字化模型不是平移不变的 (3) 给定一个数字化集合P，并不能保证精确地刻画 它的预图象S章毓晋 (TH-EE-IE)第12页第3章3.2.1 数字化模型基础数字化模型应有的一些特征：数字化模型应有的一些特征：(1)对一个非空的连续集合的数字化结果应是 非空的(2)数字化模型应该尽可能对平移不变（即混 叠效应尽可能小）(3)给定一个数字化集合P，其各个预图象应在 一定准则下相似。

更严格地说，P的域应该 有限且越小越好3章毓晋 (TH-EE-IE)第13页第3章3.2.2 方盒量化•一种数字化模型•对任何象素pi= (xi, yi)，都有一个对应的数字 化盒 Bi= (xi– 1/2, xi+ 1/2) × (yi– 1/2, yi+ 1/2)•数字化盒等价于中心为象素位置的分割多边 形一个象素pi当且仅当Bi∩ S ≠ ∅时（即它对应的数字化盒Bi与S相交）处在S的数字化集合P中章毓晋 (TH-EE-IE)第14页第3章方盒量化方盒量化（SBQ）特性特性•考虑Bi= (xi– 1/2, xi+ 1/2) × (yi– 1/2, yi+ 1/2)的 闭包[Bi] = [xi– 1/2, xi+ ½] × [yi– 1/2, yi+ 1/2]•方盒量化的定义保证了非空集合S会被映射到 非空离散集合P（但这并不保证 完全的平移不变性）右图：9，6，9，63.2.2 方盒量化章毓晋 (TH-EE-IE)第15页第3章3.2.3 网格相交量化网格相交量化（网格相交量化（GIQ））给定一个连续的细目标C，它与网格线的交点定义一个实点t = (xt, yt)，该点视C与垂直网格线相交或与水平网格线相交分别满足xt∈ I 或yt∈ I。

这个点t ∈ C将被映射到一个网格点pi= (xi, yi)，这里t ∈ (xi– 1/2, xi+ 1/2) × (yi– 1/2, yi+ 1/2)在特殊情况（如xt= xi+ 1/2或yt= yi+ 1/2）下，取落在左边的点pi属于离散集合P章毓晋 (TH-EE-IE)第16页第3章3.2.4 目标轮廓量化给定一个包含L: y = σ x + μ，0 ≤σ≤ 1 中的连续直线段，它的目标轮廓量化结果[α, β ]由 象素pi= (xi, yi)，其中yi= ⎣σ xi+ μ⎦组成图3.2.8图3.2.9(a)章毓晋 (TH-EE-IE)第17页第3章3.2.4 目标轮廓量化目标轮廓量化的定义保证只要连续直线段[a, b]与网格线相交，其数字化集合就是非空的由于限制象素要属于S的内部，目标轮廓量化产生的混叠比网格相交量化要严重章毓晋 (TH-EE-IE)第18页第3章3.3 离散直线性离散直线性有关直线性的定理和性质可以用来判断一个 数字弧是否是一条数字直线段（弦）3.3.1 弦和弧3.3.2直线性4章毓晋 (TH-EE-IE)第19页第3章3.3.1 弦和弧数字弧数字弧从点p到点q的数字弧Ppq定义为满足下列条件 的弧Ppq= {pi, i = 0, 1, …, n}：(1)p0= p，pn= q；(2)∀ i = 1, …, n–1，点pi在弧Ppq中正好有两个 相邻点：pi–1和pi+1；(3)端点p0（或pn）在弧Ppq中正好有一个相邻 点：p1（或pn–1）。

章毓晋 (TH-EE-IE)第20页第3章3.3.1 弦和弧数字化集合数字化集合网格相交（grid-intersect）量化模型在[α, β ]之间与网格线相交的点都映射到它们 最接近的整数点（相等时取[a, b]左边的）qp αβxy章毓晋 (TH-EE-IE)第21页第3章3.3.1 弦和弧弦的性质弦的性质弦是连接圆锥曲线上任意两点间的直线段给定一条从 p = p0 到 q = pn的数字弧 Ppq= {pi}i = 0, …, n，连续线段[pi, pj]与各段之和∪∪i[pi, pi+1]间的距离可用离散距离函数来测量，且不应该超过一定的阈值有阴影的区域表示 Ppq和连续线段[pi, pj]间的距离qppijpqjppip章毓晋 (TH-EE-IE)第22页第3章3.3.1 弦和弧弦的性质弦的性质一条8-数字弧Ppq= {pi}i = 0, …, n满足弦的性质，如果 当且仅当对Ppq中的任意两个离散点pi和pj以及任意连续线段[pi, pj]中的实点ρ，存在一个点pk∈ Ppq使得d8(ρ, pk) < 1阴影多边形给出 点ρ∈ R2的集合， 可以看出总存在 一个点pk∈ Ppq 使得d8(ρ, pk) < 1qp章毓晋 (TH-EE-IE)第23页第3章3.3.1 弦和弧弦的性质弦的性质弦性质不满足的示例（即Ppq不是一个直线段）ρ∈ [p1, p8]可使得对任意 k = 0, …, n，都有d8(ρ, pk) ≥1。

换句话说，ρ处在正确的多边形（可见多边形）之外如在该多边形中，从 p1看不到 p8（反过来也一样）p1q8ppρ章毓晋 (TH-EE-IE)第24页第3章3.3.2 直线性8-数字直线段的上下限数字直线段的上下限数字直线段可表示成一系列特定线段的组合{第8章}链码为{ci}i = 1, …, n= {0, 1, 0, 0, 1, 0, 0, 1, 0} 平移 n – 1次可产生 n – 1个平移的链码对应从 p 到 q 的不同的数字直线段pqp5章毓晋 (TH-EE-IE)第25页第3章3.3.2 直线性8-数字直线段的上下限数字直线段的上下限p (b){0, 0, 1, 0, 0, 1, 0, 0, 1}8{0, 0, 1, 0, 0, 1, 0, 0, 1}5{0, 0, 1, 0, 0, 1, 0, 0, 1}2{1, 0, 0, 1, 0, 0, 1, 0, 0}7{1, 0, 0, 1, 0, 0, 1, 0, 0}4{1, 0, 0, 1, 0, 0, 1, 0, 0}1{0, 1, 0, 0, 1, 0, 0, 1, 0}6{0, 1, 0, 0, 1, 0, 0, 1, 0}3{0, 1, 0, 0, 1, 0, 0, 1, 0}0链码平移链码平移链码平移上限上限—下限下限‐―章毓晋 (TH-EE-IE)第26页第3章3.3.2 直线性4-连接集合的直线性连接集合的直线性在围绕离散点 r 的数字化开盒中，所有点都映射到 r[α, β]在两个开盒之间，那么至少存在一对（8-邻域）离散点：s = (xs, ys)和t = (xt, yt)，使得坐标为[(xs+xt)/2, (ys+yt)/2]的实点属于[α, β]qp αβxyr章毓晋 (TH-EE-IE)第27页第3章3.3.2 直线性4-连接集合的直线性连接集合的直线性一个 4-数字弧 Ppq= {pi}i = 0, …, n 满足强（strong）弦性质，如果当且仅当对任意两个在 Ppq中不同的离散点 pi和pj，以及在连续线段[pi, pj]上的任意实点α，存在两个在Ppq中不同的离散点 pk和 pl 使得 pk和 pl 是4-邻域点且d8(α, pk) + d8(α, pl) < 2一个4-数字弧Ppq当且仅当它满足强弦性质时是一个4-数字直线段章毓晋 (TH-EE-IE)第28页第3章3.3.2 直线性4-连接集合的直线性连接集合的直线性由强弦性质引入的可见多边形是集合{α}∈ R2的并集两个4-邻域点pk进行并集操作而和pl的可能的布局得到的可见多边形qp(b)(a)pkpkplpl章毓晋 (TH-EE-IE)第29页第3章3.3.2 直线性4-连接集合的直线性连接集合的直线性强弦性质不成立的示例4-数字弧Ppq不是一个4-数字直线段（点a ∈ [p2, q]处于可见多边形的外边 ）qpp2α章毓晋 (TH-EE-IE)第30页第3章3.4 距离变换距离变换距离变换基于对距离的计算，其本身是一个 全局概念，但可以借助对局部距离的计算而化整 为零地进行3.4.1 定义和性质3.4.2局部距离的计算3.4.3离散距离变换的实现3.4.43-D距离变换6章毓晋 (TH-EE-IE)第31页第3章3.4.1 定义和性质距离变换计算区域中的每个点与最接近的区 域外的点之间距离，把二值图象变换为灰度图象给定一个点集 P、一个子集 B以及满足测度 条件的距离函数d(., .)，在对 P的距离变换中赋予 点 p ∈ P的值为：距离图（map）可用矩阵[DT(p)]来表示章毓晋 (TH-EE-IE)第32页第3章3.4.1 定义和性质•给定一个集合P和它的边界B，对P的距离变 换满足下列性质：(1) 根据定义，DT(p)是以p为中心且完全包含在P中的最大 圆盘的半径（即到B的最小距离）(2) 如果正好有一个点q ∈ B使得DT(p) = d(p, q)，那么就存 在一个点r ∈ P，使得中心在r半径为DT(r)的圆盘完 全包含中心在p以DT(p)为半径的圆盘（示意图？）(3) 反过来，如果至少有两个点q和q' 在B中使得DT(p) = d(p, q) = d(p, q')，那么就不存在完全包含在P中且能 完全包含中心在p以DT(p)为半。