توپولوژی دیجیتال
توپولوژی دیجیتال با خصوصیات و شکل تصاویر دیجیتال دو بعدی یا سه بعدی اشیا در رابطه با خصوصیات توپولوژیکی (همبندی) یا شکل توپولیژیکی (مرزها) سروکار دارد. مفاهیم و نتایج توپولوژی برای تعیین و تأکید بر الگوریتم‌های مهم آنالیز تصویر به کار می‌روند.
توپولوژی دیجیتال ابتدا در اواخر ۱۹۶۰ توسط محقق آنالیز تصویر کامپیوتری ازریل روزنفلد (۱۹۳۱–۲۰۰۴) مطالعه شد. نشریات او در این زمینه نقش اساسی در ایجاد و گسترش این رشته داشت. اصطلاح توپولوژی دیجیتال نیز ابتکار خود روزنفلد بود که آن را برای اولین بار در سال ۱۹۷۳ در یکی از نشریات خود به کار برد.
یکی از نتایج مهم در توپولوژی دیجیتال می‌گوید که تصاویر دودویی دو بعدی به انتخاب اختیاریِ ۴-مجاورت یا ۸-مجاورت احتیاج دارد تا دوگانگی اساسی توپولوژیکی، همبندی و جدایی را تضمین کند. تصاویر دیجیتال آرایه‌های مستطیلی از اعداد نامنفی‌اند. برای آنالیز یک عکس دیجیتال معمولاً آن را به قسمت‌های مختلف قسمت بندی می‌کنند و خصوصیات مختلف و رابطهٔ بین بخش‌های را بررسی و مقایسه می‌کنند. پردازش تصویر دیجیتال یا پردازش تصویر، کاربرد وسیعی در زمینه‌های مختلف از جمله در دادوستد، صنعت، پزشکی و علوم محیط زیست دارد.
تجزیهٔ تصاویر به ناحیه‌ها یا اشیاء و پیش زمینه، قطعه بندی نام دارد. یک تصویر با نمونه برداشتن از مقادیر روشنی آن در نقاط گسسته ی یک شبکه بندی و تبدیل این مقادیر به ارقام در تعداد متناهی از نقاط، به کامپیوتر داده می‌شود. نتیجهٔ این فرایند تصویر دیجیتال است که آرایهٔ مستطیلی از مقادیر گسسته‌است. عناصر این آرایه پیکسل (مخفف عناصر تصویر) نامیده می‌شوند. مقدار یک پیکسل سطح خاکستری آن نامیده می‌شود. قطعه بندی اساساً فرایند طبقه‌بندی پیکسل‌ها در کلاس هاست. یک روش ساده برای این کار آستانه‌ای سازی است. در این روش پیکسل‌ها را بر اساس این که سطح خاکستریشان از یک سطح آستانه‌ای مفروض t فراتر می‌رود یا نه، طبقه‌بندی می‌کنند. وقتی یک عکس به زیرمجموعه‌ها قسمت بندی می‌شود، می‌توان آن را با خصوصیات این زیرمجموعه‌ها و روابط بینشان توصیف کرد. برخی از این خصوصیات به سطح خاکستری نقاط زیرمجموعه بستگی دارند ولی برخی دیگر خصوصیات هندسی هستند که فقط به موقعیت نقاط بستگی دارند.
ابتدا مفهوم همبند بودن را برای زیرمجموعه‌های تصویر 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=formula_1,formula_2,…,formula_3=Q است به‌طوری‌که formula_4همسایهٔ formula_5 باشد.
فرض کنیم S یک زیرمجموعه از Img باشد. برای دوری از حالات خاص فرض می‌کنیم S شامل مرز Img نیست.
تعریف۴: می‌گوییم P و Q در Sمتصل (همبند) هستند اگر یک مسیر از P به Q وجود داشته باشد به‌طوری‌که همهٔ نقاط مسیر نقاطی از S باشند.
گزاره: همبندی یک رابظهٔ هم‌ارزی است.
تعریف۵: دسته‌های هم‌ارزی تعریف شده با این رابطه سازه‌های S نامیده می‌شوند. اگر S فقط یک سازه داشته باشد همبند نامیده می‌شود. اگر Sc متمم S باشد، سازهٔ یکتایی از Sc که شامل مرز Img است، پیش زمینه S نامیده می‌شود. هر سازهٔ دیگری که وجود داشته باشد سوراخ نامیده می‌شود. اگر S هیچ سوراخی نداشته باشد تماماً همبند نامیده می‌شود.
یکی از روش‌های متداول آنالیز تصویر در پردازش تصویر دیجیتال، نازک کردن مجموعه‌های دیجیتال نقاط به مقدار ایده‌آل است.
تعریف: فرض کنیم S زیرمجموعه‌ای از Img باشد، S کمان نامیده می‌شود اگر همبند باشد و همهٔ نقاط آن جز دو نقطه انتهایی دقیقاً دو همسایه داشته باشند و دو نقطهٔ انتهایی فقط یک همسایه. کمان مسیری است که نه خودش را قطع می‌کند و نه به خود مماس می‌شود. اگر نقاط کمان را با formula_6,…, formula_7 نامگذاری کنیم آن گاه formula_8 همسایه formula_9 است اگر و فقط اگر i=j±۱.
گزاره: یک خم حداکثر یک سوراخ دارد.
قضیه: یک خم دقیقاً یک سوراخ دارد.
S زیر مجموعه‌ای از Img است مرزِ S مجموعه‌ای از نقاط S است که در مکمل آن ۴-همسایه دارند.
تعریف: اگر C یک سازهٔ S و D یک سازهٔ Sc باشد. D-مرزِ C مجموعه‌ای از نقاط C است که در دی ۴-همسایه دارند. این مرز را با formula_10 نشان می‌دهیم.
اکنون الگوریتمی را توضیح می‌دهیم که متوالیاً از همهٔ نقاط D-مرزِ C عبور می‌کند. این الگوریتم که formula_11 نام دارد نشان می‌دهد که چگونه با داشتن یک جفت نقطه (formula_12,formula_13) جفت نقطهٔ جدید (formula_14,formula_15) پیدا می‌شوند. ۸-همسایه‌های formula_12 را در خلاف جهت عقربه‌های ساعت که با formula_13 شروع می‌شوند را formula_18=formula_13, formula_20,…,formula_21 می‌نامیم. فرض کنیم formula_22 اولین R ای باشد که در C است و یک ۴-همسایهٔ formula_12 باشد. چنین formula_22ای باید وجود داشته باشد چون سی ۴-همبند است و بیشتر از یک نقطه دارد. اگر formula_25 در D باشد، formula_14 را formula_22 می‌گیریم و formula_15 را formula_25، در غیر این صورت formula_14 را formula_25 و formula_15 را formula_33 می‌گیریم. اگر برای یک i مثبت formula_12 برابر formula_35 شد و یکی از formula_18,…, formula_22 برابر formula_38، کار تمام است.