توپولوژی دیجیتال

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

توپولوژی دیجیتال با خصوصیات و شکل تصاویر دیجیتال دو بعدی یا سه بعدی اشیا در رابطه با خصوصیات توپولوژیکی (همبندی) یا شکل توپولیژیکی (مرزها) سروکار دارد. مفاهیم و نتایج توپولوژی برای تعیین و تأکید بر الگوریتم‌های مهم آنالیز تصویر به کار می‌روند.

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

یکی از نتایج مهم در توپولوژی دیجیتال می‌گوید که تصاویر دودویی دو بعدی به انتخاب اختیاریِ ۴-مجاورت یا ۸-مجاورت احتیاج دارد تا دوگانگی اساسی توپولوژیکی، همبندی و جدایی را تضمین کند. تصاویر دیجیتال آرایه‌های مستطیلی از اعداد نامنفی اند. برای آنالیز یک عکس دیجیتال معمولاً آن را به قسمت‌های مختلف قسمت بندی می‌کنند و خصوصیات مختلف و رابطهٔ بین بخش‌های را بررسی و مقایسه می‌کنند. پردازش تصویر دیجیتال یا پردازش تصویر، کاربرد وسیعی در زمینه‌های مختلف از جمله در دادوستد، صنعت، پزشکی و علوم محیط زیست دارد.

تجزیهٔ تصاویر به ناحیه‌ها یا اشیاء و پیش زمینه، قطعه بندی نام دارد. یک تصویر با نمونه برداشتن از مقادیر روشنی آن در نقاط گسسته ی یک شبکه بندی و تبدیل این مقادیر به ارقام در تعداد متناهی از نقاط، به کامپیوتر داده می‌شود. نتیجهٔ این فرایند تصویر دیجیتال است که آرایهٔ مستطیلی از مقادیر گسسته‌است. عناصر این آرایه پیکسل(مخفف عناصر تصویر) نامیده می‌شوند. مقدار یک پیکسل سطح خاکستری آن نامیده می‌شود. قطعه بندی اساساً فرایند طبقه بندی پیکسل‌ها در کلاس هاست. یک روش ساده برای این کار آستانه‌ای سازی است. در این روش پیکسل‌ها را بر اساس این که سطح خاکستریشان از یک سطح آستانه‌ای مفروض t فراتر می‌رود یا نه، طبقه بندی می‌کنند. وقتی یک عکس به زیرمجموعه‌ها قسمت بندی می‌شود، می‌توان آن را با خصوصیات این زیرمجموعه‌ها و روابط بینشان توصیف کرد. برخی از این خصوصیات به سطح خاکستری نقاط زیرمجموعه بستگی دارند ولی برخی دیگر خصوصیات هندسی هستند که فقط به موقعیت نقاط بستگی دارند.

همبندی[ویرایش]

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

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

تعریف ۲: ۸-همسایه‌های (x,y) شامل ۴-همسایه‌ها و نقاط مجاور قطری آن (x+۱, y±۱) و (x-۱, 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 کمان نامیده می‌شود اگر همبند باشد و همهٔ نقاط آن جز دو نقطه انتهایی دقیقاً دو همسایه داشته باشند و دو نقطهٔ انتهایی فقط یک همسایه. کمان مسیری است که نه خودش را قطع می‌کند و نه به خود مماس می‌شود. اگر نقاط کمان را با Q_ n,…, Q_ 1 نامگذاری کنیم آن گاه Q_ i همسایه Q_ j است اگر و فقط اگر i=j±۱.

گزاره: یک خم حداکثر یک سوراخ دارد.

قضیه: یک خم دقیقاً یک سوراخ دارد.

دنبال کردن مرز[ویرایش]

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}) پیدا می‌شوند. 8-همسایه‌های P_i را در خلاف جهت عقربه‌های ساعت که با Q_i شروع می‌شوند را R_{i1}=Q_i, R_{i2},…,R_{in} می‌نامیم. فرض کنیم R_{ij} اولین R ای باشد که در C است و یک 4-همسایهٔ P_i باشد. چنین R_{ij}ای باید وجود داشته باشد چون سی 4-همبند است و بیشتر از یک نقطه دارد. اگر 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، کار تمام است.

منابع[ویرایش]