[sadeghnejad@ut.ac.ir]

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

تبدیل وکتور به رستر شامل دو مرحله است که عبارتند از:
1.Rasterization / Scan Conversion
2.Line Thicking

این فرآیند شامل عملیات ثانویه ی Line Smoothing نیز می باشد.

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


۱- Rasterization / Scan Conversion

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

الف) Pigeonhole sort :

در این روش قسمتی از حافظه ی مرکزی رزرو می شود و بعد با تخصیص موقعیت هر بردار (h,v,o) فایل رستری ساخته می شود. این روش روش ساده ای است ولی از نظر ضای ذخیره سازی ناکارا است. برای کاهش ناکارایی فضای ذخیره سازی می توان از لم های زیر بهره جست:

- اکثریت مختصات داده ها واحد است مگر در تقاطع خطوط. لذا داده هایی که مختصاتشان واحد نمی باشد به عنوان تقاطع خوط قابل تشخیص هستند.

- می توان محدودیت های شناخته شده ای را روی داده اعمال کرد مانند Minimum Bounding Box ، چگالی کلی و تعداد کلی نقاط داده.

با اعمال هر یک از لم های فوق زمان عملیات افزایش می یابد. لذا باید بالانسی در اعمال این لم ها برقرار کرد.

روش Pigeonhole را می توان به دو صورت زیر بهبود داد:

ب)Matrix Subdivision

در این روش داده به patch ها یا swatch هایی تقسیم می شود. بنابراین الگوریتم از لحاظ حافظه ی لازم بهبود می یابد. ولی از طرف دیگر زمان لازم نیز افزایش می یابد. استفاده از swatch نسبت به استفاده از patch به زمان کمتر و حافظه ی بیشتری نیاز دارد.

ج)Direct Coordinate

در این روش پیکسل های متقاطع براساس x و y سورت می شوند. این روش یک سورت دوطرفه است و باعث کاهش سرعت می شود.

روش بهینه بین روش های ب و ج است.

۲- Line Thicking

اغلب برای خروجی های کارتوگرافی لازم است. در ایم مرحله خطوط با ضخامت های مختلف از داده skeletonize شده به دست می آید. دو دسته روش برای این کار وجود دارد:
1.روش الگوریتمی مانند روش های Template و Line-Fill.
2.روش های غیر الگوریتمی مانند روش های hardware و photographic .

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

الف – ۱) Template Algorithm

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

در حالت line following افزونگی اتفاق می افتد. برای حل این مشکل از یکی از راه حل های زیر استفاده می شود:
•استفاده از increment های ۲ یا ۳ سلولی
•template تهی
•استفاده از نصف شکل : در این صورت realign خطوط، پیچیده و زمانبر است.



الف – ۲ ) Double Line-Fill Algorithm

در این روش با استفاده از line following دو خط ایجاد می شود و سپس فضای بین دو خط پر می شود. مشکلاتی که در این روش با آنها روبرو می شویم عبارتند از:
•ایجاد دو خط مشکلاتی مشابه مشکلات استفاده از template را دارد.
•محاسبه ی فاصله و زاویه ی نسبی در هر increment مشکل است.
•سرعت الگوریتم پایین است.
•به گذر جداگانه ای برای پر کردن ناحیه بین خطوط نیاز داریم.

ب) روش های الگوریتمی:

این روش ها کارایی بیشتر و هزینه ی بیشتری دارند. ولی در مقابل به زمان کمتری نیاز دارند. دو روش در این زمینه وجود دارد که عبارتند از:
1.روش سخت افزاری : از اندازه ی spot قابل تعدیلی در پلات استفاده می کند.
2.روش photographic : به صورت اپتیکی خط را بعد از پلات ضخیم می کند.