تبدیل رستر به وکتور

از آنجایی که اغلب داده های ورودی و خروجی به فرمت رستر و پردازش ها روی داده های وکتور است لذا برای پردازش ها به تبدیل رستر به وکتور و برای پلات کردن به تبدیل وکتور به رستر نیازمندیم.

روش های الگوریتمی و سخت افزاری مختلفی برای این منظور وجود دارد. فاکتورهایی که روی زمان و هزینه ی این عملیات اثر دارند عبارتند از پیچیدگی ذات مسئله، کمبود الگوریتم های کارا، انتخاب نامناسب الگوریتم ها، ترجمه ی ضعیف الگوریتم ها به کدهای کامپیوتری و ترکیبی از این عوامل.

تا وقتی که فرآیند تبدیل در سطح تئوری موردتوجه قرار گیرد مشکلات سیستماتیک اجتناب پذیر نمی باشد و علت مشکلات performance دقیقا قابل تشخیص نیست.

در تبدیل رستر به وکتور سه عملیات اساسی داریم که عبارتند از:

1. Skeletonization /Line Thining
2. Line Extraction / Vectorization
3. Topology Reconstruction

دو عملیات فرعی دیگر نیز وجود دارد که عبارتند از:

1. Line Smoothing
2. Spike and Gap Removal

1-  Skeletonization / Line Thining

فرآیند کاهش خطوط به ضخامت واحد در قدرت تفکیک داده شده است. سه روش برای انجام آن وجود دارد که عبارتند از:Medial Axis, Balooning, Peeling

الف) Peeling

فرض می شود که همه ی داده ها به صورت یک ماتریس باینری نمایش داده شده اند (۰ برای پس زمینه و ۱ برای موقعیت های اشغال شده). در این روش عملیات از هر دو طرف خط شروع می شود. در اینجا از ماتریس ۸همسایگی استفاده می شود.

اگر سه معیار زیر برآورده شود پیکسل مرکزی حذف می شود:

• پیکسل مرکزی تنها پیکسل اشغال شده در ماتریس نباشد.
• پیکسل مرکزی به سلول های همسایه متصل نباشد
• حذف آن منجر به تغییر پیوستگی خط نشود (یک junction نباشد)

مزایا:

• پردازش موازی (رستر به رستر به جای خط به خط) امکان پذیر است.
• Line junction ها تشخیص داده می شوند.
• طول کلی خط و چگالی خط کمترین تاثیر را در زمان اجرا دارد.

معایب:

• سرعت اجرا با ضخامت خط رابطه ی مستقیم دارد.
• به تغییرات محلی در ضخامت بسیار حساس است.
• در جایی که ضخامت بیشتر از ۴ پیکسل است یا در تقاطع های گرد و کلفت تشخیص نقطه ی مر کزی مشکل می باشد.

ب) Balooning

دوال Peeling است. در آن ناحیه های بین خطوط تا وقتی که خطوط جداکننده ی بین آنها دیگر نتواند بدون ایجاد شکستگی در مرز کاهش یابد گسترش می یابد. شامل دو مرحله است:

در مرحله ی اول از ماتریس ۴همسایگی استفاده می شود. نسبت به مرحله ی دوم سرعت این مرحله بیشتر و دقت آن کمتر است. در این مرحله مناطق باز بین خطوط ضخیم با تعقیب لبه های داخلی هر منطقه ی باز در جهت مشابه به صورت متناوبی گسترش می یابد. در این مرحله از همان سه معیار Peeling استفاده می شود.

در مرحله ی دوم از ماتریس ۸همسایگی استفاده می شود لذا دقت استخراج نودها بیشتر است و از یک گذر دوم برای چک تقاطع خطوط برای بازسازی توپولوژی استفاده می شود.

معایب:

• در یک زمان تنها یک سمت از یک خط مورد توجه قرار می گیرد.
• ممکن است موقعیت نقاط اشتباه به دست آید.
• می توان آن را در روش Peeling برای افزایش سرعت عملیا اعمال کرد.

ج) Medial Axis

در این روش حداکثر فاصله ی همه ی نقاط از همه ی لیه های خط اصلی به دست می آید. شامل ۴ گذر است. در گذر اول مقدار هر پیکسل اشغال شده برابر با حداقل بین مقدار پیکسل بالایی + ۱ و مقدار پیکسل پایینی + ۱ درنظر گرفته می شود. در گذر دوم مقدار هر پیکسل برابر با حداقل بین مقدار خود پیکسل، مقدار پیکسل سمت راست آن + ۱ و مقدار پیکسل سمت چپ آن + ۱ درنظر گرفته می شود. دو فرآیند اضافی نیز برای استخراج binary skeleton اعمال می شود. در نتیجه مقدار هر پیکسل برابر با تعداد پیکسل هایی است که آن پیکسل از نزدیکتری پیکسل غیر خط فاصله دارد.

مزایا:

• این روش نسبت به روش های قبلی سریعتر است.
• در این روش به بیش از ۴ گذر نیاز نداریم.
• نسبت به روش Peeling ضخامت خط تاثیر کمتری روی سرعت دارد.

معایب:

• تعدادسلول های اشغال شده و ضخامت کلی خط روی کارایی کلی روش اثر دارد.
• نودهای خیلی ضخیم می توانند منجر به خطا شوند.
• طبیعت sequential دارد و نمی توان از الگوریتم های موازی برای آن استفاده کرد.

۲-Line Extraction / Vectorization

سری خاصی از داده ها یا مختصات ها را که یک پاره خط را تشکیل می دهند مشخص می کند. دو روش برای این عملیات وجود دارد:

1. Line Following / Line Tracking Approach
2. Scan-Line Approach

حال به توضیح هر یک از روش های فوق می پردازیم:

الف) Line Following / Line Tracking Approach

هر خطی به صورت پیکسل به پیکسل در هر جهت تعقیب می شود تا به انتهای خط برسیم و سپس آن خط از ورودی حذف می شود. لذا یک خط بیش از یکبار trace نمی شود. در این روش به فضای حافظه ی زیادی نیاز نداریم. در این روش می توان ورودی را به مستطیل ها یا patch های تقسیم کرد و عملیات را روی آنها انجام داد (devide & compure).

مزایا:

• از نظر مفهومی ساده است.
• به صورت اتوماتیک به توپولوژی توجه می کند.

معایب:

• پیاده سازی آن مشکل است.
• در نودها و تقاطع ها این پرسش مطرح است که کدام شاخه را تعقیب کنیم.
• زمان اجرا با طول کلی خط رابطه ی مستقیم دارد.
• هنگامی که تعداد خطوط اسکن زیاد است خطوط سرگردان زیادی وجود دارد.

ب) Scan-Line Approach

به ترتیب خطوط اسکن عملیات صورت می گیرد. در هر خط اسکن همه ی خطوطی که با خط اسکن داده شده متقاطع هستند به صورت همزمان پردازش می شوند. در اینجا هر خط اسکن تنها یک بار خوانده می شود.  خطوط به هم پیچیده ی واحد به عنوان چند پاره خط شناسایی می شوند. برای تصحیح این امر باید آنها را در تقاطع خطوط به هم متصل کرد یا به عنوان یک مرحله ی جداگانه آنها را دوباره به هم وصل کرد.

مزایا:

• این روش نسبت به روش قبل هنگام مواجهه با حجم عظیم داده دارای کارایی بیشتری است.
• پیچیدگی این روش کمتر است.

معایب:

• این روش برای (درک) انسان ناآشنا است.

۳- Topology Reconstruction

فرآیند تعیین روابط توپولوژی (همسایگی) بین همه ی خطوط است. این مرحله در واقع محصول فرعی line thining یا line extraction می باشد. تقاطع خطوط قبل از این مرحله تشخیص داده شده است، نوع (T,X,+,Y) و موقعیت همه ی تقاطع ها در جدول جداگانه ای مشخص می شود لذا از این جدول برای بازسازی توپولوژی استفاده می شود.

Integrated task

در صورت اعمال یکپارچه ی روش های مختلف در مراحل مختلف پردازش کلی آسان و موثر می شود و کارایی افزایش می یابد. مزایای آن بیشتر از حالتی است که تنها از یک روش در هر مرحله استفاده می شود. یک مثال از این فرآیند ترکیب روش های Scan Line و Vector Line Following است.

 مشکلات تبدیل رستر به وکتور

این روش ها در صورت مواجهه با شرایط زیر با مشکلاتی روبرو می شوند:

• وقتی که خطوط ضخیم داشته باشیم.
• وقتی که حجم داده زیاد باشد.
• وقتی که کیفیت خط پایین باشد، مثلا در صورت وجود گپ در خط یا تغییر ضخامت خط یا در تقاطع های گرد.

همچنین راهنمایی های کلی در customise کردن تکنیک ها برای کاربرد خاص وجود ندارد.

مقایسه ی کارایی روش های مختلف در تبدیل رستر به وکتور

تاکنون برای مقایسه این روش ها آماره های کارایی مناسبی از نظر تئوری یا تجربی ارائه نشده است. در این زمینه تنها می توان به عبارات کلی زیر اشاره کرد:

- کارایی از نظر سرعت

سرعت کلی پردازش با تعداد دفعاتی که هر رستر از حافظه ی ثانویه فراخوانده می شود رابطه ی معکوس دارد. لذا فرآیند های تکراری از این لحاظ خوب نمی باشند. سرعت کلی برخی الگوریتم ها با طول کلی خط رابطه ی مستقیم دارد. لذا با توجه به این معیار به نظر می رسد که روش scan line بهتر از روش line following می باشد.

- کارایی از نظر space

با توجه به این معیار به نظر می رسد که روش های وکتور مبنا بهتر از روش scan line عمل می کنند.

با توجه به مطالب فوق به این نتیجه می رسیم که ما باید به صورت همزمان به این موترد توجه کنیم و سپس در مورد انتخاب روش مناسب تصمیم گیری کنیم.

پیاده سازی تبدیل رستر به وکتور

در پیاده سازی های صورت گرفته از ترکیبات مختلفی از الگوریتم ها و روش ها استفاده شده است. از جمله ی این موارد می توان به موارد زیر اشاره کرد:

• Canada Geographic Information System در کانادا
• Scanline System در آفریقای جنوبی
• Arlip System در آلمان