نگاهی به ریاضیات پیشرفته/توپولوژی دیجیتال

توپولوژی دیجیتال به خواص و شکل تصاویر دیجیتالی دو بعدی یا سه بعدی اشیاء در رابطه با خواص توپولوژیکی (اتصال) یا شکل توپولوژیکی (مرزها) می‌پردازد. مفاهیم و نتایج توپولوژی برای تعریف و تأکید بر الگوریتم‌های مهم تجزیه و تحلیل تصویر استفاده می‌شود. توپولوژی دیجیتال اولین بار در اواخر دهه ۱۹۶۰ توسط محقق تجزیه و تحلیل تصویر کامپیوتری ازریل روزنفلد (۱۹۳۱-۲۰۰۴) مورد مطالعه قرار گرفت. انتشارات او در این زمینه نقش اساسی در ایجاد و گسترش این حوزه داشت. اصطلاح توپولوژی دیجیتال نیز ابتکار خود روزنفلد بود که برای اولین بار در سال ۱۹۷۳ در یکی از انتشارات خود از آن استفاده کرد. یک نتیجه مهم در توپولوژی دیجیتال بیان می‌کند که تصاویر باینری دو بعدی به انتخاب اختیاری ۴ مجاورت یا ۸ مجاورت نیاز دارند تا از دوگانگی توپولوژیکی اولیه الحاق و جداسازی اطمینان حاصل شود. تصاویر دیجیتال آرایه‌های مستطیلی از اعداد غیر منفی هستند. برای تجزیه و تحلیل یک عکس دیجیتال معمولاً آن را به قسمت‌های مختلف و ویژگی‌های مختلف تقسیم می‌کنند و رابطه بین قسمت‌ها بررسی و مقایسه می‌شود. پردازش تصویر دیجیتال یا پردازش تصویر کاربرد گسترده‌ای در زمینه‌های مختلف از جمله تجارت، صنعت، پزشکی و علوم محیطی دارد.

نتایج اساسی

یک نتیجه اولیه (اولیه) در توپولوژی دیجیتال می‌گوید که تصاویر دوبعدی دوبعدی به استفاده جایگزین از مجاورت ۴ یا ۸ یا «اتصال پیکسل» (برای «شی» یا «غیر شی» نیاز دارند. پیکسل) برای اطمینان از دوگانگی توپولوژیکی اصلی جداسازی و اتصال. این استفاده جایگزین مربوط به باز یا بسته است در ۲ بعدی توپولوژی سلول شبکه‌ای تنظیم می‌شود و نتیجه به ۳ بعدی تعمیم می‌یابد: استفاده جایگزین ۶ یا ۲۶ مجاورت مطابقت دارد برای باز یا بسته کردن مجموعه‌ها در سه بعدی توپولوژی سلول شبکه. توپولوژی سلول شبکه همچنین برای تصاویر دو بعدی یا سه بعدی چند سطحی (به عنوان مثال، رنگی) اعمال می‌شود. به عنوان مثال بر اساس یک ترتیب کلی از مقادیر تصویر ممکن و به کار بردن یک قانون حداکثر برچسب (به کتاب Klette و Rosenfeld، ۲۰۰۴ مراجعه کنید). توپولوژی دیجیتال بسیار با توپولوژی ترکیبی مرتبط است. تفاوت‌های اصلی بین آنها عبارتند از:

1. توپولوژی دیجیتال عمدتاً اشیاء دیجیتالی را که توسط سلول‌های شبکه تشکیل می‌شوند مطالعه می‌کند
2. توپولوژی دیجیتال نیز با منیفولدهای غیر اردن «منیفولد ترکیبی» نوعی منیفولد است که گسسته سازی یک منیفولد است. این معمولاً به معنای منیفولد خطی تکه‌ای ساخته شده توسط کمپلکس‌های ساده است. یک منیفولد دیجیتال نوع خاصی از منیفولد ترکیبی است که در فضای دیجیتال یعنی فضای سلول شبکه‌ای تعریف می‌شود. یک شکل دیجیتالی قضیه گاوس-بونت این است: فرض کنید «M» یک ۲ بعدی دیجیتال بسته منیفولد در مجاورت مستقیم باشد (یعنی سطح (۶٬۲۶) در سه بعدی). فرمول جنس است: $g=1+(M_{5}+2M_{6}-M_{3})/8$،

که در آن $M_{i}$ مجموعه‌ای از نقاط سطحی را نشان می‌دهد که هر کدام دارای نقاط مجاور "i" در سطح هستند (چن و رونگ، ICPR 2008). اگر M به سادگی متصل باشد، یعنی $g=0$، سپس $M_{3}=8+M_{5}+2M_{6}$. (ویژگی اویلر را نیز ببینید)

همبندی

ابتدا مفهوم همبند بودن را برای زیرمجموعه‌های تصویر Img به صورت فرمول بیان می‌کنیم. فرض می‌کنیم Img یک ارائه از نقاط شبکه بندی با مختصات صحیح (x,y) باشد که x و y اعدادی طبیعی در یک بازه بسته هستند.

تعریف۱: ۴-همسایه‌های (x,y) چهار نقطهٔ مجاور عمودی و افقی به آن یعنی (x±۱,y) و (x, y±۱) هستند.

تعریف ۲: ۸-همسایه‌های (x,y) شامل ۴-همسایه‌ها و نقاط مجاور قطری آن (x+1, y±۱) و (x-1, y±۱) هستند.

اگر نقاط P و Q از Img همسایه باشند به آن‌ها ۴-مجاور یا ۸-مجاور می‌گوییم.

تعریف۳: P و Q نقاطی در Img هستند، منظور از مسیر از P تا Q دنباله‌ای از نقاط مانند P=$P_{0}$,$P_{1}$,…,$P_{n}$=Q است به‌طوری‌که $P_{i}$همسایهٔ $P_{i-1}$ باشد.

فرض کنیم S یک زیرمجموعه از Img باشد. برای دوری از حالات خاص فرض می‌کنیم S شامل مرز Img نیست.

تعریف۴: می‌گوییم P و Q در Sمتصل (همبند) هستند اگر یک مسیر از P به Q وجود داشته باشد به‌طوری‌که همهٔ نقاط مسیر نقاطی از S باشند.

گزاره: همبندی یک رابظهٔ هم‌ارزی است.

تعریف۵: دسته‌های هم‌ارزی تعریف شده با این رابطه سازه‌های S نامیده می‌شوند. اگر S فقط یک سازه داشته باشد همبند نامیده می‌شود. اگر Sc متمم S باشد، سازهٔ یکتایی از Sc که شامل مرز Img است، پیش زمینه S نامیده می‌شود. هر سازهٔ دیگری که وجود داشته باشد سوراخ نامیده می‌شود. اگر S هیچ سوراخی نداشته باشد تماماً همبند نامیده می‌شود.

دنبال کردن مرز مشخصه دنباله

S زیر مجموعه‌ای از Img است مرزِ S مجموعه‌ای از نقاط S است که در مکمل آن ۴-همسایه دارند.

تعریف: اگر C یک سازهٔ S و D یک سازهٔ Sc باشد. D-مرزِ C مجموعه‌ای از نقاط C است که در دی ۴-همسایه دارند. این مرز را با $C_{D}$ نشان می‌دهیم.

اکنون الگوریتمی را توضیح می‌دهیم که متوالیاً از همهٔ نقاط D-مرزِ C عبور می‌کند. این الگوریتم که $BF_{4}$ نام دارد نشان می‌دهد که چگونه با داشتن یک جفت نقطه ($P_{i}$,$Q_{i}$) جفت نقطهٔ جدید ($P_{i+1}$,$Q_{i+1}$) پیدا می‌شوند. ۸-همسایه‌های $P_{i}$ را در خلاف جهت عقربه‌های ساعت که با $Q_{i}$ شروع می‌شوند را $R_{i1}$=$Q_{i}$, $R_{i2}$,…,$R_{in}$ می‌نامیم. فرض کنیم $R_{ij}$ اولین R ای باشد که در C است و یک ۴-همسایهٔ $P_{i}$ باشد. چنین $R_{ij}$ای باید وجود داشته باشد چون سی ۴-همبند است و بیشتر از یک نقطه دارد. اگر $R_{ij-1}$ در D باشد، $P_{i+1}$ را $R_{ij}$ می‌گیریم و $Q_{i+1}$ را $R_{ij-1}$، در غیر این صورت $P_{i+1}$ را $R_{ij-1}$ و $Q_{i+1}$ را $R_{ij-2}$ می‌گیریم. اگر برای یک i مثبت $P_{i}$ برابر $P_{0}$ شد و یکی از $R_{i1}$,…, $R_{ij}$ برابر $Q_{0}$، کار تمام است.

منابع

ویکی‌پدیای فارسی

ویکی‌پدیای انگلیسی