مفاهیم توپولوژی دیجیتال

چکیده

در مقاله‌ی قبلی که برای مخاطبان متفاوتی نوشته شده است [کامپیوترها و گرافیک 13(2) (۱۹۸۹) ۱۶۶-۱۵۹] نخستین مولف یک گروه بنیادی دیجیتال را تعریف کرد ـ یک نظیر، برای تصاویر دیجیتال دودویی، از گروه بنیادی. در حالت کلی تعریف گروه بنیادی دیجیتال با تغییر شکل پیوسته همراه است. اما یک تعریف بدیل، گسسته، از گروه بنیادی دیجیتال ارایه شد برای فضاهای تصویر دیجیتال قویاً نرمال که در همان مقاله تعریف شدند. مقاله‌ی مزبور همچنین یک «نظیر پیوسته»   را برای هر تصویر دیجیتال دودویی   روی یک DPS (DPS = فضای تصویر دیجیتال) تعریف کرد.   یک چندوجهی است که با «پر کردن شکاف‌ها»ی بین نقاط سیاهِ (۱های) تصویر دیجیتال دودویی   به یک شیوه‌ی خاص ساخته می‌شود. انواع دیگر نظیر پیوسته را دو مولف اول پیشتر مورد استفاده قرار داده‌اند. پژوهشگران، در جستجوی ساده‌ترین و کارآمدترین الگوریتم برای انجام عملیات پردازش تصویر، بسیاری از ترکیبات متفاوت تورین‌ها و روابط مجاورت را مد نظر قرار داده‌اند. تقریباً همه‌ی آن ترکیب‌ها یکریخت به حالت‌های خاصی از مفهوم یک DPS قویاً نرمال هستند. آورده‌ی اصلی مقاله‌ی حاضر اثباتی است بر این که گروه‌های بنیادی دیجیتالِ تصاویر دیجیتال دودویی روی یک DPS قویاً نرمال، طبیعتاً یکریخت هستند به گروه‌های بنیادی نظیرهای پیوسته‌ی تصاویر دیجیتال. از این نتیجه استفاده می‌کنیم تا ثابت کنیم که روی یک DPS قویاً نرمال، تعاریف گسسته و پیوسته‌ی گروه بنیادی دیجیتال هم‌ارز اند، تا یک یکریختی گروه طبیعی. همچنین نشان می‌دهیم که بسیاری از نتایج توپولوژیک که در صفحه‌ی اقلیدسی یا ۳فضای اقلیدسی برقرار اند، نظیرهایی دارند که در هر DPS قویاً نرمالی برقرار هستند. نتایج ما حاکی از آن است که یک DPS قویاً نرمال یک حوزه‌ی مناسب برای مطالعه‌ی عملیات پردازش تصویر مرتبط با توپولوژی مانند نازک‌سازی، ردگیری مرز و پر کردن کانتور است. تعاریف گروه بنیادی دیجیتال، DPS قویاً نرمال و نظیر پیوسته در این مقاله گنجانده شده‌اند تا این مقاله خودبسنده باشد.

۱. مقدمه

این مقاله درباره‌ی گروه بنیادی دیجیتال، فضاهای تصویر دیجیتال قویاً نرمال، و نظیر  پیوسته‌ی    از یک تصویر دیجیتال دودویی   روی یک فضای تصویر دیجیتال قویاً نرمال است. این مفاهیم توپولوژی دیجیتال در [۱۱] ارایه شدند، مقاله‌ای که برای مخاطبان متفاوتی نوشته شده است. گروه بنیادی دیجیتال، یک نظیر است برای تصاویر دودویی دیجیتالِ  گروه بنیادی، درست همان‌طور که همبندی دیجیتال (مثلاً ۴- یا ۸-همبندی) یک نظیر است برای تصاویر دودویی دیجیتالِ مفهوم توپولوژیک همبندی. اهمیت گروه بنیادی در توپولوژی چندوجهی سه‌بعدی حاکی از آن است که گروه بنیادی دیجیتال یک مفهوم مفید از توپولوژی سه‌بعدی دیجیتال خواهد بود. در حقیقت، گروه بنیادی دیجیتال یک کاربرد بی‌واسطه در نظریه‌ی الگوریتم‌های نازک‌سازی تصویر سه‌بعدی دارد. چرا که برای حفظ «تونل‌ها» یک الگوریتم نازک‌سازی سه‌بعدی باید گروه‌های بنیادی دیجیتال را در تصویر دودویی دیجیتال ورودی حفظ کند. برای بحث بیشتر این موضوع [۱۱، بخش 2.3؛ ۱۸، بخش ۱۰؛ ۱۴] را ببینید.پژوهشگران، در پی ساده‌ترین و کارآمدترین الگوریتم‌ها برای انجام عملیات پردازش تصویر مانند نازک‌سازی و ردگیری مرز، ترکیبات متفاوت فراوانی از روابط تورین‌ها و مجاورت را مد نظر قرار داده‌اند. تقریباً همه‌ی آن ترکیب‌ها یک‌ریخت به موارد خاصی از مفهوم یک فضای تصویر دیجیتال قویاً نرمال هستند.نظیر پیوسته‌ی   یک تصویر دیجیتال دودویی   روی یک فضای تصویر دیجیتال قویاً نرمال، یک چندوجهی است که با «پر کردن شکاف‌ها» بین نقاط سیاهِ   بر طبق تعدادی قاعده‌ی کاملاً طبیعی ساخته شده است. نتیجه‌ی اصلی مقاله‌ی ما، قضیه‌ی 6٫1٫1 در بخش ۶، نشان می‌دهد که گروه‌های بنیادی   و مکمل آن، طبیعتاً یکریخت به گروه‌های بنیادی دیجیتالِ   و تصویر دیجیتال دودویی مکمل   هستند. این گواهی است بر این که گروه بنیادی دیجیتال به شکل مناسبی تعریف شده است. قضیه‌ی 6٫1٫1 همچنین نشان می‌دهد که   به طرق مفید دیگری، شبیه به   است. ما در بخش ۷ از قضیه‌ی 6٫1٫1 به شکل گسترده استفاده می‌کنیم تا یک فضای تصویر دیجیتال قویاً نرمال را ایجاد کنیم که دارای ویژگی‌های «توپولوژیک» خوبی است که آن را به یک حوزه‌ی مناسب برای مطالعه‌ی عملیات پردازش تصویر مرتبط با توپولوژی تبدیل می‌کند. همچنین، از گزاره‌ی 7٫9٫1 نتیجه می‌شود که برای فضاهای تصویر دیجیتال قویاً نرمال، تعریف «پیوسته»ی گروه بنیادی دیجیتال [۱۱، تعریف 3٫3٫4] معادل  تعریف گسسته‌ی گروه در [۱۱، بخش 4٫4] است.برای آن‌که این مقاله را خودـ‌شامل بکنیم، بسیاری از تعاریفی که در [۱۱] آمده‌اند را در بخش‌های ۳ تا ۵ گنجانده‌ایم.

Abstract

Kong, T.Y., A.W. Roscoe and A. Rosenfeld, Concepts of digital topology, Topology and its Applications 46 (1992) 219-262. In an earlier paper written for a different readership [Computers and Graphics 13(2) (1989) 159-1661 the first author defined a digitalfundamentalgroup-an analog, for binary digital pictures, of the fundamental group. In general the definition of the digital fundamental group involves continuous deformation. But an alternative, discrete, definition of the digital fundamental group was proposed for the strongly normal digital picture spaces defined in the same paper. The above-mentioned paper also defined a “continuous analog” C(p) for each binary digital picture B on such a DPS (DPS = digital picture space). C(p) is a polyhedron constructed by “filling in the gaps” between black points (l’s) of the binary digital picture B in a specific way. Other kinds of continuous analog had previously been used by the first two authors. In seeking the simplest and most efficient algorithms for performing image processing operations, researchers have considered many different combinations of grids and adjacency relations. Almost all of those combinations are isomorphic to special cases of the concept of a strongly normal DPS. The main contribution of the present paper is a proof that the digital fundamental groups of binary digital pictures on a strongly normal DPS are naturally isomorphic to the fundamental groups of the digital pictures’ continuous analogs. We use this result to establish that on a strongly normal DPS the discrete and continuous definitions of the digital fundamental group are equivalent, up to a natural group isomorphism. We also show that many topological results which hold in the Euclidean plane or Euclidean 3-space have analogs that hold in every strongly normal DPS. Our results suggest that a strongly normal DPS is a suitable domain for studying topologyrelated image processing operations such as thinning, border tracking and contour filling. The definitions of digital fundamental group, strongly normal DPS and continuous analog are included in this paper so as to make it self-contained.

1. Introduction

This paper is about the digital fundamental group, strongly normal digital picture spaces, and the continuous analog C( L?) of a binary digital picture ?? on a strongly normal digital picture space. These concepts of digital topology were introduced in [ll], a paper written for a different readership.’ The digital fundamental group is an analog for binary digital pictures2 of the fundamental group, just as digital connectedness (e.g., 4- or S-connectedness) is an analog for binary digital pictures of the topological notion of connectedness. The importance of the fundamental group in 3-d polyhedral topology suggests that the digital fundamental group will be a useful concept of 3-d digital topology. In fact the digital fundamental group has an immediate application to the theory of 3-d image thinning algorithms. For in order to preserve “tunnels” a 3-d thinning algorithm must preserve the digital fundamental groups of the input binary digital picture. See [ll, Section 2.3; 18, Section 10; 141 for further discussion of this topic. In seeking the simplest and most efficient algorithms for performing image processing operations such as thinning and border tracking, researchers have considered many different combinations of grids and adjacency relations. Almost all of those combinations are isomorphic to special cases of the concept of a strongly normal digital picture space. The continuous analog C(9) of a binary digital picture ?? on a strongly normal digital picture space is a polyhedron constructed by “filling in the gaps” between black points of L!? in accordance with a number of fairly natural rules. The principal result of our paper, Theorem 6.1.1 in Section 6, shows that the fundamental groups of C(Y) and its complement are naturally isomorphic to the digital fundamental groups of Y and the complementary binary digital picture @. This is evidence that the digital fundamental group has been appropriately defined. Theorem 6.1.1 also shows that C(9) is analogous to 9 in other useful ways. In Section 7 we make extensive use of Theorem 6.1.1 to establish that a strongly normal digital picture space has the good “topological” properties which make it a suitable domain for studying topology-related image processing operations. Also, it follows from Proposition 7.9.1 that for strongly normal digital picture spaces the “continuous” definition of the digital fundamental group [ll, Definition 3.3.41 is equivalent3 to the discrete definition of the group in [ll, Section 4.41. To make this paper self-contained, many of the definitions given in [l l] are included in Sections 3-5.

چکیده

۱. مقدمه

۲. تورین‌های استاندارد و روابط مجاورت

۳. فضاهای تصویر دیجیتال دودویی و تصاویر دیجیتال دودویی

۳.۱. انتخاب بازنمود

۳.۲. فضاهای تصویر دیجیتال دودویی

۳.۳. تصاویر دیجیتال دودویی

۳.۴. همبندی. مولفه‌ها. مسیرها. خم‌های ساده‌ی بسته

۳.۵. مرزها. احاطه. حفره‌ها و کاواک‌ها. پس‌زمینه

۳.۶. فضاهای منظم تصویر دیجیتال

۳.۷. ـ‌گشت‌ها و ـ‌دورها؛ گروه‌های بنیادی دیجیتال

۴. فضاهای تصویر دیجیتال قویاً نرمال

۴.۱. بحث کلی

۴.۲. تعریف یک DPS قویاً نرمال

۴.۳ مثال‌هایی از DPSهای قویاً نرمال

۴.۴. گشت‌ها و دورهای دیجیتال سیاه؛ گروه بنیادی دیجیتال گسسته

۵. نظیرهای پیوسته‌ تصاویر دیجیتال

۵.۱. ویژگی‌های نظیر پیوسته

۵.۲. مکعب‌های واحد معمولی و ویژه‌ی شبکه. ـ‌سادک‌ها

۵.۳. مجموعه‌نقاط سیاه و سفید افزوده؛ ـ‌سادک‌های سیاه، سفید و نیم‌سیاه

۶. قضیه‌ اصلی

۶.۱. بیان نتیجه

۶.۲. همریختی‌های خوش‌تعریف

۶.۳. Tـ‌مجاورت، Tـ‌گشت‌ها، Tـ‌دورها و ـ‌گشت‌ها

۶.۴. اثبات قضیه‌ی اصلی

۷. ویژگی‌های توپولوژیک فضاهای تصویر دیجیتال قویاً نرمال

۷.۱. مقدمات

۷.۲. قضیه‌ی یک خم جردن دیجیتال

۷.۳. گراف مجاورت. نرمال بودن ضعیف

۷.۴. همبندی مرزها

۷.۵. استقلال توپولوژیک مولفه‌های متمایز I

۷.۶. استقلال توپولوژیک مولفه‌های متمایز II

۷.۷ مشخصه‌ی اویلر. تونل‌ها

۷.۸. محاسبه‌ مشخصه‌های اویلر

۷.۹. هم‌ارزی تعاریف گسسته و پیوسته‌ی گروه بنیادی دیجیتال

۸. نکات پایانی

Abstract

1. Introduction 

2. Standard grids and adjacency relations 

3. Binary digital picture spaces and binary digital pictures 

3.1. Choice of representation 

3.2. Binary digital picture spaces 

3.3. Binary digital pictures 

3.4. Connectedness. Components. Paths. Simple closed curves 

3.5. Borders. Surrounding. Holes and cavities. The background 

3.6. Regular digital picture spaces 

3.7. P-walks and LP-loops; the digital fundamental group 

4. Strongly normal digital picture spaces 

4.1. General discussion 

4.2. Dejinition of a strongly normal DPS 

4.3. Examples of strongly normal DPSs 

4.4. Black digital walks and loops; the discrete digital fundamental group 

5. Continuous analogs of digital pictures 

5.1. Continuous analog properties 

5.2. Ordinary and special unit lattice cubes. ??-simplexes 

5.3. The augmented black and white point sets; black, white and semi-black 9’-simplexes 

5.4. C(P) and C’(g) 

6. The main theorem 

6.1. Statement of the result 

6.2. Well-dejned homomorphisms 

6.3. T-adjacency, T-walks, T-loops and T-walks 

6.4. Proof of the main theorem 

7. Topological properties of strongly normal digital picture spaces 

7.1. Introductory remarks 

7.2. A digital Jordan curve theorem 

7.3. The adjacency graph. Weak normality 

7.4. Connectedness of borders 

7.5. Topological independence of distinct components I 

7.6. Topological independence of distinct components II 

7.7. The Euler characteristic. Tunnels 

7.8. Computing Euler characteristics 

7.9. Equivalence of the discrete and continuous definitions of the digital fundamental group 

8. Concluding remarks