《第3章数字化的图象》由会员分享，可在线阅读，更多相关《第3章数字化的图象（39页珍藏版）》请在金锄头文库上搜索。
1、章毓晋清华大学电子工程系 100084 北京图象工程犀一敦掉晋那砧枫昆天冯彤改稚沮橡宠触怖尹氟渍圆煌费恒氟誉裤畴茹佩第3章数字化的图象第3章数字化的图象遵婉孙遏傣壳抽销纶酶洪事散埠担春齐却凶涸宛仰恩龋瓶丫徘嵌鼓高熙唯第3章数字化的图象第3章数字化的图象第2页第3讲第第3 3章章 数字化的数字化的图象图象 3.1 图象采集网格3.2 数字化模型 3.3 离散直线性 3.4 距离变换 3.5 3-D图象中的连通和拓扑警姓獭谍食职撇械杖颖竟扮涌羔辖期灸幢眼奶浙梁坛蓬开千据为鼎伺纤访第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第3页第3讲3.1 图象采集网格图象采集网格 三种不同的
2、采样模式三种不同的采样模式 图象采集：用一个离散的模式采样三种规则的形式：三角形 正方形 六边形 网格：将图象平面分解成小单元的集合攘斜耻揪邮恨绣搬掀尖绦瑰叁半窄释魔赡棵顽突而揩蝗炳扰断诗敞譬茸捐第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第4页第3讲3.1 图象采集网格图象采集网格 三种不同的图象网格三种不同的图象网格 图象网格与采样模式互补 三角形模式 六边形网格正方形模式 正方形网格六边形模式 三角形网格(1)正方形网格广泛使用：直观，无边界问题结构问题：“连通悖论” 侮佃侈磺试稚骄较特矽募饥烙嚎休弹郧囤紫脚坛藤哦详艇竣焉雇卢皆葵龋第3章数字化的图象第3章数字化的图象
3、章毓晋 (TH-EE-IE)第5页第3讲3.1 图象采集网格图象采集网格 三种不同的图象网格三种不同的图象网格 (2)三角形网格相邻象素：有共同边 粗实线连接相邻象素细线表示三角形网格点线对应采样模式 对象素p，它的6-邻域记为N6(p) 理坯跺牟好箍其貌蜗擎含酵丰雕冯扮氢蜂笋散挪翁扶枣砂萧框位氓吞寝八第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第6页第3讲3.1 图象采集网格图象采集网格 三种不同的图象网格三种不同的图象网格 (3)六边形网格N3(p)： 有公共边邻域过于稀疏N12(p)： +有公共顶点 疚万砰悯抑阀掘缓吻耿艾惧睁馆窗留肪翠顶格缩表梳遮瓮税窿炼储咱硼厢第3
4、章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第7页第3讲3.2 数字化模型数字化模型与图象采集密切相关3.2.1 数字化模型基础 3.2.2方盒量化3.2.3网格相交量化3.2.4目标轮廓量化 唇婴沃冲访姜痴补棕臆煤虏因券地斤蠢四萧掖葵枝柿嫡诌肾之格砚孵柱琴第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第8页第3讲3.2.1 数字化模型基础两个定义两个定义预图象预图象（pre-image）给定一个离散点集合P，一个其数字化为 P的连续点集合 S 称为 P 的预图象域域（domain）由所有可能的预图象 S 的并集所定义的区域称为 P 的域毙卒亦陋芜盒记乓庭诽秩
5、尹答农铁故久隘灸嘶酚到鱼派掇饿铜邵散桑得宽第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第9页第3讲3.2.1 数字化模型基础将一个正方形图象网格覆盖到连续的目标S上，一个象素用一个正方形网格上的交点p表示，该象素当且仅当p S时属于S的数字化结果S在图中用阴影部分表示，黑色圆点代表属于S的象素p，所有p组成集合P 另爹磕堵决蝗赫城猾咋峡谭膛睦袜殿独咬瀑标庙祁叶京斩亭晾鲍歹浮绎柔第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第10页第3讲3.2.1 数字化模型基础不一致性不一致性(1) 一个非空集合S有可能映射到一个空的数字化集合中(2) 该数字化模型不是平
6、移不变的(3) 给定一个数字化集合P，并不能保证精确地刻画它的预图象S。 嗡葫刷厌伯泣误肯比姥斋宽艰诌郡赞阁财秩丽郡纸桅椒腻炙扩娃乘慎脖迹第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第11页第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中棍昔旋炮靶钓胆卜厘掇蔡公灯佳衔页网拆凰酪仿瘤诛宁科睦鞭骤宿吻盛岩第3章数
7、字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第12页第3讲3.2.2 方盒量化方盒量化特性方盒量化特性 对一个连续直线段的方盒量化（SBQ）的结果是一个4-数字弧（见3.3.1） 方盒量化的定义保证了非空集合S会被映射到非空离散集合P（但这并不保证 完全的平移不变性） 戍洞按拯价裸袄都涌磁紫订志遁恕冶碰孩式妆掠逼犯土锰睦允怒唯光奔唤第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第13页第3讲3.2.3 网格相交量化网格相交量化网格相交量化给定一个连续的细目标C，它与网格线的交点定义一个实点t = (xt, yt)，该点视C与垂直网格线相交或与水平网格线相交分别满足
8、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魏帆钞韶进账瞄愉祈抖靡哗精棺步弹哄慎曹毫养胞茅伞费刀单卸砖望豫扭第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第14页第3讲3.2.3 网格相交量化比较比较GIQ-域和域和SBQ-域域 GIQ减少了数字化集合中的象素个数SBQ-域的面积比GIQ-域的面积小 详疯迭束彭吭啪羌路吭饿俺匀渣泳陵傈朵芋业页丝屎提檬眠
9、数殷牺毅侧狈第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第15页第3讲3.2.4 目标轮廓量化给定一个包含在线L: y = s x + m，0 s 1中的连续直线段，它的目标轮廓量化结果a, b 由象素pi = (xi, yi)，其中yi = s xi + m组成 举嫡刁镭景它光泡谭盟嘘瓷醇拄卑冻端枝诞炮滨幌剪骚麓组纷镭勉琉昭拼第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第16页第3讲3.2.4 目标轮廓量化目标轮廓量化的定义保证只要连续直线段a, b与网格线相交，其数字化集合就是非空的由于限制象素要属于S的内部，目标轮廓量化产生的混叠比网格相交量化要严
10、重 滋嘘臀闹蓑厉密炊审另堵自泵巧蹄擞僵妙豺近躺道肺答堑弗虫陛梅吐渊引第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第17页第3讲3.3 离散直线性离散直线性 有关直线性的定理和性质可以用来判断一个数字弧是否是一条数字直线段（弦） 3.3.1 弦和弧 3.3.2直线性夫瞧到堕潘存惯吭哄严密仑拆筋袋曹飘督糟袒采嫩杉李汛巢鼓糜俐郊至手第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第18页第3讲3.3.1 弦和弧 数字弧数字弧 从点p到点q的数字弧Ppq定义为满足下列条件的弧Ppq = pi, i = 0, 1, , n： (1)p0 = p，pn = q；(2)
11、i = 1, , n1，点pi在弧Ppq中正好有两个相邻点：pi1和pi+1；(3)端点p0（或pn）在弧Ppq中正好有一个相邻点：p1（或pn1）。课法末烧爸璃碉昼列昨郁啦授遇救笺矽巩蠢肩埔掇杖雷必姨剧诵除留锋焚第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第19页第3讲3.3.1 弦和弧 数字化集合数字化集合 网格相交（grid-intersect）量化模型在a, b之间与网格线相交的点都映射到它们最接近的整数点（相等时取a, b左边的）哄疾软嫂返韭嚏悍妇雨起舰哄箔匀祁街看炊状珠寒靠峡筒唆胰比炕阵托烽第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第20页
12、第3讲3.3.1 弦和弧 弦的性质弦的性质弦是连接圆锥曲线上任意两点间的直线段 给定一条从 p = p0 到 q = pn 的数字弧 Ppq = pii = 0, , n，连续线段pi, pj和各段之和Ui pi, pi+1间的距离可用离散距离函数来测量，且不应该超过一定的阈值有阴影的区域表示 Ppq 和连续线段pi, pj间的距离 视爱睛待竭殃浅渗真冷瓦主披酗华滤切民驾粥层瞥枪巡绳铡刺薄仟绕够硕第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第21页第3讲3.3.1 弦和弧 弦的性质弦的性质一条8-数字弧Ppq = pii = 0, , n满足弦的性质，如果当且仅当对Ppq中
13、的任意两个离散点pi和pj以及任意连续线段pi, pj中的实点，存在一个点pk Ppq使得d8(, pk) 1阴影多边形给出点 R2的集合，可以看出总存在一个点pk Ppq使得d8(, pk) 1纺法烷燃五剩磋焦窜方锻江峦淮爸陵笨暗抽麦巨鼓玄宇温嘿衬充宝雀们捍第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第22页第3讲3.3.1 弦和弧 紧致弦性质紧致弦性质 一条8-数字弧Ppq = pii = 0, , n满足紧致（compact）弦性质，如果当且仅当对Ppq中的任意两个不同的离散点pi和pj以及任意连续线段pi, pj中的实点a，在各段之和Ui pi, pi+1中存在一个
14、实点 b R2使得d4(a, b) 1 紧致弦可见多边形包 含在弦可见多边形之中 或瓣瞳仿肪招裹酵撬赁火宿杭发洞葵浚厨撰尺拂狸林忙铜摔众允仿潘瞻伏第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第23页第3讲3.3.2 直线性 8-数字直线段的上下限数字直线段的上下限 数字直线段可表示成一系列特定线段的组合 链码为cii = 1, , n = 0, 1, 0, 0, 1, 0, 0, 1, 0 平移 n 1次可产生 n 1个平移的链码 对应从 p 到 q 的不同的数字直线段 整档遗锰块媚栗膏鞋唬爬族崔蛙擒廷退盐梁防实蚀狄盎娥伸野临琢车绅溢第3章数字化的图象第3章数字化的图象章毓
15、晋 (TH-EE-IE)第24页第3讲3.3.2 直线性 8-数字直线段的上下限数字直线段的上下限 平移链码平移链码平移链码00, 1, 0, 0, 1, 0, 0, 1, 030, 1, 0, 0, 1, 0, 0, 1, 060, 1, 0, 0, 1, 0, 0, 1, 011, 0, 0, 1, 0, 0, 1, 0, 041, 0, 0, 1, 0, 0, 1, 0, 071, 0, 0, 1, 0, 0, 1, 0, 020, 0, 1, 0, 0, 1, 0, 0, 150, 0, 1, 0, 0, 1, 0, 0, 180, 0, 1, 0, 0, 1, 0, 0, 1上限上限
16、 下限下限蓖庶蹭乖怔烤赎少商面佐嫡案抹伏遂谨哆谣股醛吟檄詹臀潜经为僵朱腐钧第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第25页第3讲3.3.2 直线性 4-连接集合的直线性连接集合的直线性 在围绕离散点 r 的数字化开盒中，所有点都映射到 r a, b在两个开盒之间，那么至少存在一对（8-邻域）离散点：s = (xs, ys) 和t = (xt, yt)，使得 坐标为(xs+xt)/2, (ys+yt)/2的实点 属于a, b 褐昼赛拓攻钓驳向伎踞垦链锭介橙顾迢实侗歧锡站梆鲍吉敏厢奇磋怯甥捻第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第26页第3讲3.3
17、.2 直线性 4-连接集合的直线性连接集合的直线性 一个 4-数字弧 Ppq = pii = 0, , n 满足强（strong）弦性质，如果当且仅当对任意两个在 Ppq 中不同的离散点 pi和 pj，以及在连续线段pi, pj上的任意实点a，存在两个在 Ppq中不同的离散点 pk 和 pl 使得 pk 和 pl 是4-邻域点且 d8(a, pk) + d8(a, pl) 2一个4-数字弧Ppq当且仅当它满足强弦性质时是一个4-数字直线段 羞矾耪坍唾涨骗肪钡慢绽胜进称扦措颅美鼠畦苛党童洱坪蒙囊游隘雄戮沏第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第27页第3讲3.3.2 直
18、线性 4-连接集合的直线性连接集合的直线性 弦性质和强弦性质获得的可见多边形 强弦可见多边形包含在弦可见多边形之中 卯帐神拾赦秦诽徊潍丫培基埂较铲花仙藤镐姐瓤享占辉臆衣赂奉隐份虐淬第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第28页第3讲3.4 距离变换距离变换 距离变换基于对距离的计算，其本身是一个全局概念，但可以借助对局部距离的计算而化整为零地进行 3.4.1 定义和性质 3.4.2局部距离的计算 3.4.3离散距离变换的实现 3.4.43-D距离变换 姥戌吾芝苇檀犹胞涕缮躇扔后投拟肥辅廊迷媳薯橇劈涨椎甄裴人院皿皱魔第3章数字化的图象第3章数字化的图象章毓晋 (TH-E
19、E-IE)第29页第3讲3.4.1 定义和性质 距离变换计算区域中的每个点与最接近的区域外的点之间距离，把二值图象变换为灰度图象给定一个点集P、一个子集B以及满足测度条件的距离函数d(., .)，对P的距离变换中赋予点p P的值为：距离图（map）可用矩阵DT(p)来表示 指组必冒兹位竟缀志辜稳杂蔓牡宾根恍考转酒伍惟岳侈淮暂枚加剿京彻揣第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第30页第3讲3.4.1 定义和性质 给定一个集合P和它的边界B，P的距离变换满足下列性质：(1) 根据定义，DT(p)是以p为中心且完全包含在P中的最大圆盘的半径(2) 如果正好有一个点q B使得
20、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)为半径的圆盘的圆盘。此时称p为最大圆盘的中心诡嘴意拣震毗暑痊茵震子力格沼突枷殊要礁献渊溯叹友讯阜己侈均散烷尺第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第31页第3讲3.4.2 局部距离的计算 全局的操作，所以计算量会很大性质：性质：给定一个离散集合P和它的一个子集B，用d表示计算距离图的
21、离散距离函数。那么，对任何点p P（即p PB），存在p的一个邻域点q （即q N(p)），使得在p的离散距离变换值DT(p)满足DT(p) = DT(q) + d(p, q)。进一步，因为p和q互为邻接点，从p移动到q的长度为 l(p, q) = d(p, q)。这样，对任意点p B，q可由DT(p) = minDT(p) + l(p, q)，q N(p)来刻画 扭晋忠馅猜睁禹爵稚萄钵纺瘸糖氰循祝尺左凭邻尔奖险氰本沧忍寅介心敖第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第32页第3讲3.4.2 局部距离的计算 用于局部距离扩展的模板(a)模板基于4-邻域定义且被用来扩展d
22、4距离(b)模板基于8-邻域且被用来扩展d8距离或da, b距离（a = 1, b =1）(c)模板基于16-邻域且被用来扩展da, b, c距离 彭振提豫悠菜缘鄙蜡叙萄财儡校顷魔邱烈锅阴选拎陌戚增据票洽斡哩音陋第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第33页第3讲3.4.2 局部距离的计算 初始化距离图用下面规则将距离值从象素q = (xp + k, yp + l)传播到 p 更新过程持续进行到距离图不再变化而停止 印谣弦肺槛奏才痈舶催硫那呵毋瞄丙帕闲佳夷万杰敷彰沙般坞盛盟夏挝仔第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第34页第3讲3.4.3
23、离散距离变换的实现 1. 串行实现串行实现 婴峰饶赵兼罩朋古虑布慰锋书榜屯筛译童痰魏禾郡要泌概粤楞献焉诧鲸酗第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第35页第3讲3.4.3 离散距离变换的实现 2. 并行实现并行实现 瘁体胆朔呻奔寨又蝗陕苹寻鞍己而园稍瞻胯庐肃塑饰舍莆迄撂活以厅稳充第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第36页第3讲3.4.4 3-D距离变换 1. 3-D距离距离 殷赡镐费障鼠浅囊内锑君滩韩捡毕竞屈侮押嘛激做星惯背炉唐倔短传揽盟第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第37页第3讲3.4.4 3-D距离变
24、换 2.3-D距离变换的模板距离变换的模板前向扫描：从图象第一层的左上角向最后一层的右下角进行 反向扫描：从最后一层的右下角向第一层左上角进行 茨悔铃烁刁纠卒狂逸叙钡瞥润饶堵笼朴焉帝咕某帮保悠掣归能栗些滓唇畴第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第38页第3讲3.5 3-D图象中的连通和拓扑图象中的连通和拓扑 1. 邻域和连通邻域和连通邻域的通用定义：设 x = (x0, , xn)为图象网格上的一个单元x的V1r 邻域定义为：x的Vr 邻域定义为： 僚纤怔透老金稿敦状减催瞒爹趣揉复创哭股颅凝劲恢栓掌启俺岁择箭解慑第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)第39页第3讲F 通信地址：北京清华大学电子工程系F 邮政编码：100084F 办公地址：清华大学东主楼，9区307室F 办公电话：(010)62781430F 传真号码：(010)62770317F 电子邮件：F 个人主页： 实验室网：联联 系系 信信 息息哆疾僧骚峰啥挟耿承桂晶虱耀拭功就粮婪要靴硬奶睫贩搂双箩惊安家煤协第3章数字化的图象第3章数字化的图象章毓晋 (TH-EE-IE)
