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

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

یا به‌طور کلی برای تعریف توپولوژی دیجیتال داریم که: تجزیه و تحلیل یک تصویر دیجیتال معمولاً شامل تقسیم آن به قطعات و اندازه‌گیری خصوصیات مختلف و روابط بین این قطعات است. به‌طور خاص، فرد اغلب می‌خواهد مؤلفه‌های همبند زیرمجموعه یک تصویر را جدا کند، تا روابط مجاورت بین این مؤلفه‌ها را تعیین نموده، مرزهایشان را ردیابی و رمزگذاری کند؛ الگوریتم‌های استانداردی برای انجام همه‌ی این وظایف وجود دارد. اما برای اثبات اینکه آن‌ها کار می‌کنند، لازم است برخی از خصوصیات توپولوژیکی زیرمجموعه تصویر دیجیتال ایجاد شود که این خصوصیات بنام توپولوژی دیجیتال یاد می‌گردد.

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

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

تجزیهٔ تصاویر به ناحیه‌ها یا اشیاء و پیش زمینه، قطعه بندی نام دارد. یک تصویر با نمونه برداشتن از مقادیر روشنی آن در نقاط گسسته ی یک شبکه بندی و تبدیل این مقادیر به ارقام در تعداد متناهی از نقاط، به کامپیوتر داده می‌شود. نتیجهٔ این فرایند تصویر دیجیتال است که آرایهٔ مستطیلی از مقادیر گسسته‌است. عناصر این آرایه پیکسل (مخفف عناصر تصویر) نامیده می‌شوند. مقدار یک پیکسل سطح خاکستری آن نامیده می‌شود. قطعه بندی اساساً فرایند طبقه‌بندی پیکسل‌ها در کلاس هاست. یک روش ساده برای این کار آستانه‌ای سازی است. در این روش پیکسل‌ها را بر اساس این که سطح خاکستریشان از یک سطح آستانه‌ای مفروض 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= $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}$ ) پیدا می‌شوند. ۸-همسایه‌های $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}$ ، کار تمام است.

منابع