首页 > 图书中心 > 数字图像的计算几何、拓扑和物理及其应用

前言

前    言

  本书介绍数字图像和视频帧图像序列中计算几何学、拓扑学和物理学的内容。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. Edelsbrunner, H.: Geometry and topology for mesh generation. In: Cambridge Monographs on Applied and Computational Mathematics, vol. 7, pp. xii+177. Cambridge University Press, Cambridge, UK (2001), Zbl 1039.55001

2. Ziegler, G.: Lectures on polytopes, In: Graduate Texts in Mathematics, vol. 152. pp. x+370. Springer, New York (1995). ISBN: 0-387-94365-X, MR1311028

3. Peters, J.: Foundations of computer vision. In: Computational Geometry, Visual Image Structures and Object Shape Detection, Intelligent Systems Reference Library, vol. 124, pp. i-xvii, 432. Springer International Publishing, Switzerland (2017). https://doi.org/10.1007/ 978-3-319-52483-2, Zbl 06882588 and MR3768717

4. Alexandroff, P.: Elementary concepts of topology, 63pp., Dover Publications, Inc., New York (1965). In: Translation of Einfachste Grundbegriffe der Topologie, Springer, Berlin (1932), translated by Alan E. Farley, Preface by D. Hilbert, MR0149463

5. Alexandroff, P.: ?ber den algemeinen dimensionsbegriff und seine beziehungen zur elementaren geometrischen anschauung. Math. Ann. 98, 634 (1928)

6. Cooke, G., Finney, R.: Homology of cell complexes. In: N.E. Steenrod, (ed.) Based on lectures by Princeton University Press and University of Tokyo Press, Princeton, N.J., USA; Tokyo, Japan, pp. xv+256 (1967), MR0219059

7. Borsuk, K.: On the imbedding of systems of compacta in simplicial complexes. Fund. Math. 35, 217–234 (1948), MR0028019

8. Borsuk, K.: Theory of shape. Monografie matematyczne, Tom 59. In: Mathematical Monographs, vol. 59, PWN—Polish Scientific Publishers (1975), MR0418088. Based on K. Borsuk, Theory of shape, Lecture Notes Series, No. 28, Matematisk Institut, Aarhus Universitet, Aarhus (1971), MR0293602

9. Borsuk, K., Dydak, J.: What is the theory of shape? Bull. Austral. Math. Soc. 22(2), 161–198 (1980), MR0598690

10. Edelsbrunner, H., Harer, J.: Computational topology. An introduction. Amer. Math. Soc., Providence, RI pp. xii+241 (2010). ISBN: 978-0-8218-4925-5, MR2572029

11. Munch, E.: Applications of persistent homology to time varying systems. Ph.D. thesis, Duke University, Department of Mathematics (2013). Supervisor: J. Harer, MR3153181

12. Nye, J.: Natural focusing and fine structure of light. Caustics and dislocations, pp. xii+328. Institute of Physics Publishing, Bristol (1999), MR1684422

13. Susskind, L.: The Black Hole War, pp. 470. Back Bay Books, New York, NY, USA (2008)

14. Peters, J.: Proximal planar shape signatures. Homology nerves and descriptive proximity. Advan. Math: Sci. J. 6(2), 71–85 (2017), Zbl 06855051

15. Peters, J.: Proximal planar shapes. Correspondence between triangulated shapes and nerve complexes. Bull. Allahabad Math. Soc. 33, 113–137 (2018), MR3793556, Zbl 06937935, Review by D. Leseberg (Berlin)

16. Giblin, P.: Graphs, Surfaces and Homology, pp. Xx+251, 3rd edn. Cambridge University Press, Cambridge, GB (2016). ISBN: 978-0-521-15405-5, MR2722281, first edition in 1981, MR0643363

17. Betti, E.: Sopra gli spazi di un numero qualunque di dimensioni [italian]: above the spaces of any number of dimensions. Annali di Matematica Pura ed Applicata 4(1), 140–158 (1870)

18. Tucker, W., Bailey, H.: Topol. Sci. Am. 182(1), 18–25 (1950). http://www.jstor.org/stable/ 24967355

19. Salepci, N., Welshinger, J.Y.: Tilings, packings and expected betti numbers in simplicial complexes. arXiv 1806(05084v1), 1–28 (2018)

20. Pranav, P., Edelsbrunner, H., van de Weygaert, R., Vegter, G.: The topology of the cosmic web in terms of persistent betti numbers. Mon. Not. R. Astron. Soc. 1–31 (2016). https:// www.researchgate.net

21. Kaczynski, T., Mischaikov, K., Mrozek, M.: Computational homology, Appl. Math. Sci. 157, pp. xvii+480. Springer, New York, NY (2004). ISBN 0-387-40853-3/hbk, Zbl 1039.55001

22. Concilio, A.D., Guadagni, C., Peters, J., Ramanna, S.: Descriptive proximities. Properties and interplay between classical proximities and overlap. Math. Comput. Sci. 12(1), 91–106(2018), MR3767897, Zbl 06972895

23. Zeng, W., Gu, X.: Ricci flow for shape analysis and surface registration. theories, algorithms and applications, pp. Xii+139. Springer, Heidelberg (2013). ISBN: 978-1-4614-8780-7, MR3136003

24. Beer, G., Di Concilio, A., Di Maio, G., Naimpally, S., Pareek, C., Peters, J.: Somashekhar naimpally, 1931–2014. Topol. Appl. 188, 97–109 (2015). http://doi.org/10.1016/j.topol. 2015.03.010, MR3339114

25. Peters, J., Naimpally, S.: Applications of near sets. Notices Am. Math. Soc. 59(4), 536–542 (2012). http://doi.org/10.1090/noti817, MR2951956

26. Concilio, A.D., Guadagni, C.: Bornological convergences and local proximity spaces. Topol. Appl. 173, 294–307 (2014), MR3227224

27. Concilio, A.D., Guadagni, C., Peters, J., Ramanna, S.: Descriptive proximities i: properties and interplay between classical proximities and overlap. Math. Comput. Sci. 12(1), 91–106 (2018), ArXiv 1609.06246v1, MR3767897

28. Peters, J., Guadagni, C.: Strongly proximal continuity & strong connectedness. Topol. Appl. 204, 41–50 (2016), ArXiv 1504.02740, MR3482701

29. Guadagni, C.: Bornological convergences on local proximity spaces and xl- metric spaces. Ph.D. thesis, pp. 79. Università degli Studi di Salerno, Salerno, Italy (2015). Supervisor: A. Di Concilio

30. Concilio, A.D., Gerla, G.: Quasi-metric spaces and point-free geometry. Math. Struct. Comput. Sci. 16(1), 115–137 (2006), MR2220893

31. Peters, J., Tozzi, A.: Quantum entanglement on a hypersphere. Int. J. Theor. Phys. 55(8), 3689–3696 (2016), Zbl 1361.81025, MR3518899

32. Worsley, A.: Harmonic quintessence and the derivation of the charge and mass of the electron and the proton and quark masses. Phys. Essays 24(2), 240–253 (2011). https://doi.org/ 10.4006/ 1.3567418

33. Worsley, A.: The formulation of harmonic quintessence and a fundamental energy equivalence equation. Phys. Essays 23(2), 311–319 (2010). https://doi.org/10.4006/ 1.3392799

34. Worsley, A., Peters, J.: Enhanced derivation of the electron magnetic moment anomaly from the electron charge from geometric principles. Appl. Phys. Res. 10(6), 24–28 (2018). https://doi.org/10.5539/apr.v10n6p24

35. Yurkin, Peters, J., Tozzi, A.: A novel belt model of the atom, compatible with quantum dynamics. J. Sci. Eng. Res. 5(7), 413–419 (2018)

36. ?nan, E.: Approximately groups in proximal relator spaces. Commun. Fac. Sci. Univ. Ank. Ser. A1. Math. Stat. 68(1), 572–582 (2019), MR3827537

37. Peters, J., ?nan, E.: Strongly proximal edelsbrunner-harer nerves. Proc. Jangjeon Math. Soc. 19(3), 563–582 (2016), MR3618825

38. ?nan, E., ?ztürk, M.: Near groups on nearness approximation spaces. Hacettepe J. Math. Stat. 41(4), 545–558 (2012), MR3060371, MR3241196

39. Peters, J., ?nan M.A. ?ztürk, E.: Monoids in proximal banach spaces. Int. J. Algebra 8(18), 869–872 (2014)

40. Peters, J., ?nan M.A. ?ztürk, E.: Spatial and descriptive isometries in proximity spaces. Gen. Math. Notes 21(2), 125–134 (2014)

41. ?ztürk, M., U?kun, M., ?nan, E.: Near groups of weak cosets on nearness approximation spaces. Fund. Inform. 133(4), 443–448 (2014), MR3285076

42. Peters, J., ?ztürk, M.A., U?kun M.: Exactness of homomorphisms on proximal groupoids. Fen Bilimleri Dergisi X(X), 1–14 (2014)

43. Peters, J., ?ztürk, M., U?kun, M.: Klee-phelps convex groupoids. arXiv 1411(0934), 1–5 (2014). Published in Mathematica Slovaca 67 (2017), no. 2.397–400

44. ?ztürk, M., ?nan, E., Tekin, O., Peters, J.: Fuzzy proximal relator spaces. Neural Comput. Appl. (2018). https://doi.org/10.1007/s00521-017-3268-1

45. Zaka, O., Peters, J.: Isomorphic-dilations of the skew-fields constructed over parallel lines in the desargues affine plane. arXiv 1904(01469), 1–15 (2019)

46. Pawlak, Z.: Classification of objects by means of attributes. Pol. Acad. Sci. PAS 429 (1981)

47. Or?owska, E., Peters, J., Rozenberg, G., Skowron, A.: In memory of professor zdzis?aw pawlak. Fund. Inform. 75(1–4), vii–viii (2007), MR2293685

48. Peters, J.: How near are Zdzis?aw Pawlak’s paintings? Study of merotopic distances between digital picture regions-of-interest. In: A. Skowron, Z. Suraj (eds.) Rough Sets and Intelligent Systems, pp. 89–114. Springer (2012)

49. Peters, J., Skowron, A., Stepaniuk, J.: Nearness of visual objects. Application of rough sets in proximity spaces. Fundam. Inf. 128(1–2), 159–176 (2013), MR3154898

50. Peters, J., Skowron, A., Stepaniuk, J.: Nearness of objects: Extension of approximation space model. Fundam. Inf. 79(3–4), 497–512 (2007), MR2346263

51. Wolski, M.: Toward foundations of near sets: (pre-)sheaf theoretic approach. Math. Comput. Sci. 7(1), 125–136 (2013), MR3043923

52. Dochviri, I.: On submaximality of bitopological saces. Kochi J. Math. 5, 121–128 (2010), MR2656713, Zbl 1354.54027

53. Dochviri, I., Peters, J.: Topological sorting of finitely many near sets. Math. Comput. Sci. 10 (2), 273–277 (2016), Zbl 1345.54020, MR3507604

54. Peters, J., Dutta, H.: Equivalence of planar ?Cech nerves and complexes. Natl. Acad. Sci. Lett. (2019). https://doi.org/10.1007/s40009-019-0790-y, ISSN 2250-1754

55. Henry, C.: Near sets: Theory and applications. Ph.D. thesis, Univ. of Manitoba, Dept. Elec. Comp. Engg. (2010). http://130.179.231.200/cilab/. Supervisor: J.F. Peters

56. Henry, C., Ramanna, S.: Signature-based perceptual nearness: application of near sets to image retrieval. Math. Comput. Sci. 7(1), 71–85 (2013), MR3043919

57. Henry, C., Ramanna, S.: Quantifying nearness in visual spaces. Cybern. Syst. 44(1), 38–56 (2013)

  

  1  非常感谢Arturo Tozzi的这张照片。

---------------

------------------------------------------------------------

---------------

------------------------------------------------------------

IV

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

V

前    言

版权所有(C)2023 清华大学出版社有限公司 京ICP备10035462号 京公网安备11010802042911号

联系我们 | 网站地图 | 法律声明 | 友情链接 | 盗版举报 | 人才招聘