数字图像的计算几何、拓扑和物理及其应用

本书对视觉场景中有关计算几何学、拓扑学和物理学的内容进行了全面和深入介绍，有助于从数学和物理的角度来认识许多图像技术。本书主要内容围绕对目标形状信息的检测、表达和描述展开，讨论了单元复合形、细丝、涡旋和骨架涡旋、形状指纹、测地轨迹、自由阿贝尔群、神经复合形、形状持久性、接近性和近似描述接近性、聚类和形状类别、平铺定理和表面形状覆盖等许多概念和方法。本书还给出了使用基于这些概念和方法的图像技术在形状跟踪、法医学形态理论、零镜头识别、物理目标形状分类及视频帧中形状的近似描述性接近度等方面的应用事例。
本书可作为信号与信息处理、通信与信息系统、电子与通信工程、模式识别与智能系统、计算机科学技术以及应用数学和视觉认知学等学科大学高年级本科生或研究生专业课教材和教学参考书，还可供涉及图像技术应用行业（如工业自动化、电视广播、机器人、电子医疗设备、生物医学、遥感测绘、勘探采矿、智能交通、安全监控、法医取证、星际探测和军事侦察等）的科技工作者科研参考。

本书是一本介绍与图像和视频相关的计算几何学，拓扑学和物理学知识及其应用的书籍，也是从数学和物理的角度，对图像和视频的处理、分析、理解进行深入介绍的书籍。

本书从学习图像技术的角度对计算几何学，拓扑学和物理学的相关内容进行了深入的探讨，一方面有助于信号与信息处理和计算机科学技术等专业背景的人员加强对图像技术原理更深层的认识，另一方面也为数学和物理专业背景的人员进入图像技术和计算机视觉领域有很好的引导作用。

　　本书介绍数字图像和视频帧图像序列中计算几何学、拓扑学和物理学的内容。Edelsbrunner [1]的网格生成几何和Ziegler [2]的多胞形几何为本书所研究的三角视觉场景的几何结构提供了计算几何学方法的坚实基础。平面多胞形是由覆盖多边形内部的闭合半平面相交所定义的填充多边形。此外，可以在Peters [3]的计算机视觉几何基础中找到本书中对计算几何的介绍。它是由亚历山德罗夫[4，5]（由Cooke和Finney [6]巧妙地扩展和阐述）、Borsuk [7，8，9]所引入的单元复合形拓扑结构，最近由Edelsbrunner和Harer提出的这种拓扑结构[10]以及由Munch [11]在持久性同源性方面的工作为视觉场景的计算拓扑学的介绍性研究提供了坚实的基础。这种拓扑形式探索了视觉场景中常见的构造、形状和结构。结合视觉场景的固有几何和拓扑结构，则需要考虑对视频中记录的结构和事件产生的计算物理学以及随之而来的关于光的精细结构的敏感性。Nye [12]介绍了我们所关注的光和光焦散的精细结构。对光焦散的考虑导致了突变理论和光焦散折叠和尖端的出现，从而在三角化数字图像中引入了光学涡旋神经。在这种情况下，计算物理学与在视频帧图像中光结构的编排研究是同义词。这种光结构的编排表现为一系列从表面形状反射和折射的光的快照，为研究视觉场景中出现的结构和形状提供了坚实的基础。

　　研究图像目标形状在视频帧图像序列以及记录视觉场景中表面形状变化的照片序列中的持久性非常重要。表面形状会出现、经历各种光线和表面条件的变化、并最终消失。人们通常倾向于在视觉场景中寻找不寻常的物体（自然的和人工的），这是一种对视觉场景中连续变化和观察到的成分的瞬间持久性的默认认识。换句话说，重要的是需考虑视觉场景形状的时空特性。这既指对视觉场景的理解不仅包括对视觉场景的几何和拓扑的研究，也包括对光物理学、光子在视觉场景中与曲面碰撞的特性和能量的考虑。

　　如果考虑对表面形状的描述和从照片中（特别是在视频帧图像中）记录的表面形状反射的光，物理学就会进入图像。计算机工程也通过对光子学和反射光捕获设备的研究而进入图像。就数字图像的物理学而言，能量的变形特性很重要。有关这种能量观点的更多信息，请参见Susskind [13，§7，p.126]。

　　计算几何学有助于捕获嵌入在图像目标形状中的细粒度结构。计算拓扑学能够捕捉和分析嵌入在三角化视觉场景几何结构中的单元复合形（顶点、线段、填充三角形、循环、涡旋、神经的集族）里发现的近邻（参见Peters [14，15]）。单元复合形的同源性（亚历山德罗夫拓扑学方法的后代[4]）在这里是一个重要的组成部分。同源性是一个数学框架，它关注空间是如何连通的，并利用代数结构，如群和映射，将空间中具有拓扑意义的子集相互联系起来[10，§IV.1，p.79]。

　　群G是一个非空集，它配备了一个结合的二元运算○，其中有一个恒等元素e并且G中的每个成员a都有一个逆b，即a ○ b = e。循环群H是这样一个群，其中G的每个成员都可以写成称为生成元的单个元素的正整数幂。一个循环群是阿贝尔群，只要对于G中的每对元素，都有a ○ b = b ○ a。自由阿贝尔群是一个有多个生成元的阿贝尔群，即该群中的每个元素都可以写成?igi，这里生成元gi都在G中。从同源性观点对循环群的介绍可参见Giblin [16，A.1，p.216]。

　　实际上，同源性是洞察视觉场景中的各个部分如何相互连通的来源。循环群有助于以简洁的方式表示视觉场景中的各个部分是如何相互连通并接合在一起的。具有多个生成元的循环群也是指定感兴趣表面形状的重要特征的一个来源，该特征即贝蒂数（Betti number，自由阿贝尔群中生成元数量的计数）。H. Poincaré根据文章[17]为纪念Enrico Betti命名了这个数。数字图像的计算几何学、拓扑学和物理学的重点是有限空间。

　　贝蒂观察到，有限空间具有与其维度大小和元素形状无关的属性。这些属性仅指其各部分的连通方式……[17，§3，p.143]。有限有界空间区域的特性倾向于通过覆盖空间的单元复合形中的通道所连通的顶点来揭示。（例如，参见覆盖由图1中的表面形状占据的有界区域的通道的连通涡旋）。有关这方面的更多信息，请参见Tucker和Bailey [18]、Salepci和Welshinger [19]以及Pranav、Edelsbrunner、van de Weygaert和Vegter [20]。

图1　覆盖形状的嵌套、非重叠涡旋

　　Kaczynski、Mischaikov和Mrozek [21]对同源性的计算方法进行了深入研究。这里的重点是辨别和跟踪、分析和表达以及近似移动表面形状的接近性。为了应对一个视觉场景中（从一个视频帧图像到另一个视频帧图像）的连续形状变化，描述性邻近空间上的特征矢量为我们提供了一种表示形状变化的方法，这些变化要么彼此靠近，要么有时相距很远。有关这方面的更多信息，请参阅Di Concilio、Guadagni、Peters和Ramanna [22]。

什么是平面上的表面形状？

平面上的表面形状是欧氏平面上由简单封闭曲线（形状轮廓）限定的具有非空内部（形状内容）的有限区域。

　　在欧氏平面中，几何结构包括顶点、线段和实心三角形（三边多面体）。多胞形是封闭半平面的交集[2]。单个多胞形是一个空间区域，内部充满，四周都有边界。在拓扑设置中，重点是将视觉场景区域分解为非常简单的多胞形，例如易于测量和分析的填充三角形。这种拓扑的基本成分是单纯复合形、形状理论和持久同源性。

　　这项工作背后的秘密是将封闭的数字图像区域分解成一组形状复合形，这些形状复合形为形状分析提供了基础。形状复合形用嵌套的，通常不重叠的涡旋集族（参见图?1）对形状进行覆盖。图2(b)中显示了对图2(a)1中那不勒斯花卉的部分三角剖分样本的分解。最终结果是用例如花瓣与填充三角形（单纯复形）的集族对图像场景形状的覆盖。在每个复合形中构成神经结构的三角形集族具有共同的顶点。例如，图2(b)中覆盖白花的复合形为我们提供了一种测量、比较、描述和分类花瓣所占据场景片段的方法。一般来说，形状分析的目标是分类、比较、量化异同，并测量形状之间的距离[23]。在本书中，重点是计算拓扑在视觉场景形状分析中的应用。

(a) 视觉场景

(b) 形状复杂性

图2　覆盖场景形状的单纯复形样本

　　对于三角化视觉场景中的单元复合形，场景形状被称为神经复合形（参见图3）的填充三角形簇所覆盖。设K是点集的有限集族。集族K的神经（用Nrv K表示）由K的所有非空子集族组成，这些子集族具有非空交集[10，§III.2，p.9]。每条神经都有其独特的形状。例如，图2(b)中覆盖花部分的神经的形状来自围绕单个顶点的填充三角形。在三角化表面上，亚历山德罗夫神经复合形A（用Nrv A表示）是具有公共顶点的三角形集族[4，§33，p.39]（参见图4）。

图3　样本重叠的神经复合形

图4　亚历山德罗夫神经复合形

　　本书不仅介绍了数字图像中的计算几何学、拓扑学和物理学的基础知识，而且还给出了许多实际应用。应用包括：

　　应用1：单元分裂轨迹：3.13节，应用3.13。

　　应用2：最大重心星状神经：4.3节，应用4.3。

　　应用3：跟踪视频帧图像形状的变化：4.13节。

　　应用4：法医学形态理论中的光学涡流神经：4.14节。

　　应用5：时空涡旋循环：重叠电磁涡旋：5.7节，应用5.7。

　　应用6：嵌套非同心涡旋特征矢量集族的比较：5.11节，应用5.11。

　　应用7：基于强描述性连通性的零镜头识别：5.13节，应用5.13。

　　应用8：物理目标形状分类中的描述近似性：6.5节，应用6.5。

　　应用9：视频帧图像中形状的近似描述性接近度：7.8节，应用1。

　　应用10：视频中尖端神经系统形状分类的近似描述接近度：8.13节，应用2。

　　本书中的章节源于我在过去几年中为本科生和研究生讲授的计算机视觉课程的笔记。本书中的许多主题得益于我与一些研究人员、研究生和博士后的讨论和交流，特别是Sheela Ramanna、Somashekhar Amrith Naimpally（1931—2014）[24, 25]，Anna Di Concilio [26, 27]，Clara Guadagni [28, 29]，Luigi Guadagni、Fabio Marino、Giuseppe Di Maio、Giuseppe Gerla [30]，Gerald (Jerry) Beer、Arturo Tozzi [31]，Romi Tozzi（斐波那契数8和∞）和鼓舞人心的Vittorio Tozzi、Andrew Worsley [32, 33, 34]，Alexander Yurkin [35]，Ebubekir ?nan [36, 37, 38, 39, 40, 41]，Mehmet Ali ?zturk [42, 43, 44]，Mustafa U?kun [43]，?zlem Tekin [44]，Orgest Zaka [45]，Brent Clark（阿基米德世界移动支点的回声），Zdzis?aw Pawlak [46, 47, 48]，Andrzej Skowron [49, 50]，Jaros?aw Stepaniuk、Jan G. Bazan、Marcin Wolski [51]，Piotr Wasilewski、Ewa Or?woska、W. Pedrycz、William (Bill) Hankley（时间逻辑），David A. Schmidt（集合理论），Joe Campbell、Rich McBride、Iraklii Dochviri [52, 53]，Hemen Dutta [54]，Maciej Borkowski、Surabhi Tiwari、Sankar K. Pal、Cenker Sengoz、Doungrat Chitcharoen、Chris Henry [55, 56, 57]，Dan Lockery 以及 M. Zubair Ahmad、Arjuna P.H. Don、Maxim Saltymakov、Enoch A-iyeh、Randima Hettiarachchi、Dat Pham、Braden Cross、Homa Fashandi、Diba Vafabakhsh、Amir H. Meghdadi、Enze Cui、Liting Han、Fatemeh Gorgannejad、Maryam Karimi和Susmita Saha。

　　我还要感谢M. Zubair Ahmad、Sheela Ramanna和Fatemeh Gorgannejad，他们对本书的部分内容提供了非常有帮助的见解、建议和更正。

　　本书的目标读者是工程、数学和物理科学的三年级和四年级本科生、一年级研究生，以及计算几何学、拓扑学、物理学、数字图像处理和计算机视觉领域的研究人员。对每个主要章节主题，给出了相关的算法。以下符号用于表示各章习题的难度级别：

　　：快速、易于解决；

：深入、全面。

温尼伯，加拿大 詹姆斯F.彼得斯

第1章 视觉场景中的计算几何学、拓扑学和物理学 1

1.1 引言 1

1.2 镶嵌平面有限有界区域 3

1.3 表面平铺的计算几何 6

1.4 平面表面的镶嵌 7

1.5 多胞形及其边界、孔、内部和路径 7

1.6 沃罗诺伊区域及其种子点 11

1.7 沃罗诺伊区域特性 12

1.8 沃罗诺伊区域同伦类型特性 15

1.9 矩形沃罗诺伊区域 16

1.10 质心作为形状内部的种子点 18

1.11 基于质心的图像场景形状镶嵌 19

1.12 计算几何和拓扑中的单元复合形 21

1.13 涡旋复合形和形状持久性条形码 23

1.14 与Ghrist条形码相似的形状条形码 23

1.15 矩形网格上的德劳内三角剖分 27

1.16 源自质心德劳内三角形的条形码 29

1.17 沃罗诺伊区域上的德劳内三角形 31

1.18 视觉场景的德劳内三角剖分 32

1.19 视觉场景中源自沃罗诺伊区域的德劳内三角剖分 34

1.20 基于辐条的单元复合形神经 35

1.21 神经辐条构造 36

1.22 德劳内三角剖分的性质 39

1.23 亚历山德罗夫神经 41

1.24 视频帧图像上亚历山德罗夫神经的拆分可行性问题 44

1.25 彩色像素波长 48

1.26 骨架对上的连通接近性 50

1.27 CW复合形及其来源 52

1.28 基于复合形亚历山德罗夫-霍夫拓扑的图像分割 55

1.29 德劳内三角剖分的收缩特性 57

1.29.1 德劳内三角形重心回缩 57

1.29.2 亚历山德罗夫神经核回缩 58

1.30 资料来源和进一步阅读 59

参考文献 62

第2章 形状内的单元复合形、细丝、涡旋和形状 68

2.1 引言：三角形有界平面区域上的路径连通顶点 68

2.2 表面形状、孔和涡旋 68

2.3 视频帧图像、豪斯道夫空间和CW复合形 69

2.4 单元复合形的有限闭包和弱拓扑性质 71

2.5 定向细丝骨架 72

2.6 骨架神经 73

2.7 光子能量和骨架神经能量 77

2.8 骨架神经的能量 78

2.9 骨架神经的接近性 79

2.10 骨架涡旋的诞生 80

2.11 碰撞骨架涡旋 82

2.12 部分为骨架神经的碰撞骨架涡旋 82

2.13 双子座复合形和双子座神经结构 84

2.14 定向细丝骨架 86

2.15 资料来源、参考文献和其他阅读材料 87

参考文献 88

第3章 骨架涡旋上的三个形状指纹、测地轨迹和自由阿贝尔群 91

3.1 引言：空间的形状 91

3.2 在三角化表面形状上发现定向细丝骨架的生成元 92

3.3 图像几何学：研究图像目标形状的方法 94

3.4 从图像形状分析角度看CTdi 96

3.5 单元、单元复合形，循环和边界 96

3.6 在图像形状上绘制的定向弧上旋转 98

3.7 单元复合形中形状循环的构建 100

3.8 闭合连通的路径：图像形状中孔的边界 101

3.9 映射到神经复合形的形状顶点 102

3.10 形状映射到具有顶点中心的球 104

3.11 切赫神经中的多个球 105

3.12 切赫复合形：切赫神经重叠 106

3.13 同源映射和神经之间的轨迹 107

3.14 形状之间的测地线轨迹 109

3.15 基本形状 111

3.16 形状接近性：将互相邻近的形状集族缝合在一起 114

3.17 从形状轮廓和骨架派生的循环群 115

3.18 在骨架涡旋上的自由阿贝尔群 119

3.19 图像目标形状上的边界链 121

3.20 链、循环、边界和同源群 123

3.21 细丝骨架循环群 124

3.22 骨架涡旋和骨架神经自由阿贝尔群 126

3.23 Betti-Nye光学涡旋神经和持久贝蒂数 127

3.24 视为相交等势线的光涡旋神经 129

3.25 资料来源、参考文献和其他阅读材料 134

参考文献 135

第4章 神经复合形给出的图像形状信息 139

4.1 引言 139

4.2 亚历山德罗夫重心星神经 140

4.3 视频帧图像上的范多胞形 141

4.4 源自相交多胞形的骨架神经 142

4.5 视频帧图像骨架神经复合形的自由阿贝尔群表示 144

4.6 神经复合形系统 146

4.7 神经复合形系统星系 147

4.8 重心骨架神经复合形系统 149

4.9 细丝辐条形状和闭包的重要性 150

4.10 循环细丝骨架形状 153

4.11 光涡旋神经中的Nye咖啡杯焦散 154

4.12 尖端细丝作为反射光的通路 156

4.13 贝蒂数和光涡旋神经的咖啡杯焦散尖端定理 157

4.14 资料来源和进一步阅读 160

参考文献 164

第5章 表面形状及其接近性 166

5.1 引言 166

5.2 接近景观 168

5.3 什么是接近空间 168

5.4 切赫接近性和斯米尔诺夫接近性度量 169

5.5 连通接近性空间 170

5.6 涡旋神经接近性空间 174

5.7 强[重叠]连通接近性空间 177

5.8 描述接近性 180

5.9 艾哈迈德描述性并集 181

5.10 子复合形聚类 181

5.11 描述连通接近性 186

5.12 强描述连通接近性 189

5.13 零样本分类 193

5.14 具有近端相关器的涡旋循环空间 193

5.15 资料来源和进一步阅读 195

参考文献 197

第6章 Leader聚类和形状类别 201

6.1 引言 201

6.2 描述接近性 202

6.3 尖端细丝矢量之间的夹角 206

6.4 尖端细丝的重要性 207

6.5 基于描述接近性的形状类 207

6.6 用强描述性形状类别精确确定形状内部的重要性 210

6.6.1 构造强描述接近性类别的步骤 210

6.6.2 重新讨论强描述接近性公理 211

6.7 光涡旋神经形状类别 212

6.8 源自骨架和涡旋神经的连通性接近形状类 214

6.9 描述性CW复合形和强描述连通接近性形状类 215

6.10 样本强描述连通性形状类 219

6.11 资料来源和进一步阅读 220

参考文献 220

第7章 形状及其近似描述接近性 222

7.1 引言 222

7.2 近似描述性交集 223

7.3 近似接近法中的步骤 226

7.4 基于切赫接近性的近似接近性 228

7.5 近似强描述接近性 229

7.6 对神经形状之间可能的近似强 描述接近性进行检查的步骤 230

7.7 形状及其近似描述接近类 232

7.8 构建近似描述性光涡旋神经类的步骤 232

7.9 形状的近似强描述性连通类 237

7.10 构造近似强描述性连通形状类的步骤 242

7.11 近似强描述性连通的神经形状的特征 242

7.12 资料来源和进一步阅读 245