دانلود مقاله پیادهسازی الگوریتم Chain Code بر روی FPGA

بخشی از مقاله

چکیده:

در این مقاله به بررسی نحوۀ پیادهسازی الگوریتم chain code بر روی FPGA میپـردازیم. الگـوریتم chain code یکی از الگوریتمهای کد کردن تصویر میباشد که برای کد کردن لبههای یـک شـیء در تصـویر اسـتفاده مـیشـود.

همچنین این الگوریتم میتواند عرض، ارتفاع، محیط و مساحت شیء را نیز به دست آورد. این الگوریتم در پردازش تصـویر و شناسایی و مقایسه شیءها و الگوها با هم کاربرد بسیاری دارد. در این پـروژه ابتـدا الگـوریتم chain code بـا اسـتفاده از VHDL که زبان توصیف سختافزار میباشد، شبیهسازی شده و سپس برنامه نوشته شـده بـه زبـان VHDL بـر روی مـدل Spartan-II از FPGA های شرکت Xilinx پیادهسازی میشود.

پردازندۀ مذکور قابلیت تولید chain code را برای یک تصویر با ابعاد حداکثر 256*256 پیکسل سیاه و سفید دارا میباشد که البته در صورت نیاز این ابعاد قابل گسترش میباشند. همچنین این پردازنده، طول، عرض، محـیط و مسـاحت شیء موجود در تصویر را نیز علاوه بر تولید کد به دست میآورد.

کلمات کلیدی:

پردازش تصویر - پردازش بلادرنگ - VHDL - FPGA - Chain Code

1) مقدمه:

در پردازش تصویر گاه لازم است که تصویر را کد کنیم. الگوریتمهای کد کردن تصویر با استفاده از بخشبندی تصویر تلاش می کنند تا خصوصیات بخشهای مهم و شناخته شدۀ تصویر را به گونه ای مؤثر و به نحوی که بازسازی مجدد تصویر با دقت کافی امکانپذیر باشد، توصیف کنند. الگوریتمهای متعددی برای کد کردن تصویر وجود دارد. الگوریتم [1] chain code یکی از الگوریتمهای کد کردن تصویر می باشد. در این الگوریتم که برای کد کردن لبههای یک شیء استفاده میشود، هریک از پیکسلهای لبه شیء با یکی از 8 بردار جهت نشان داده شده در شکل 1 بیان میشوند. به این

ترتیب با تخصیص کد به هریک از این بردارهای جهت میتوان لبه یک شیء را کدگذاری کرد. از طرف دیگر، با استفاده از chain code میتوان ویژگیهای آماری متعددی از شیء از قبیل طول، عرض، محیط و مساحت را محاسبه نمود. از این پارامترها میتوان در مراحل نهایی پردازش تصویر برای شناسایی و تصمیمگیری در مورد تصویر و همچنین مقایسه میان اشیاء مختلف موجود در تصاویر استفاده کرد. در ضمن باید به این نکته توجه داشت که الگوریتم chain code تنها بر روی تصاویر باینری قابل پیادهسازی است.

1 2 3
0 4
7
6 5

شکل :1 جهتها در الگوریتم chain code

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

در این مقاله ابتدا الگوریتم chain code را برای پیادهسازی روی FPGA طراحی می کنیم و سپس به بررسی الگوریتم برنامه مربوط به پیاده سازی الگوریتم فوق میپردازیم. در انتها نیز، نتایج به دست آمده از پیاده سازی بررسی می شود.

2) طراحی الگوریتم Chain Code برای پیادهسازی روی : FPGA

با مشاهده پیرامون یک شیء توپر، می توان ملاحظه کرد که خصوصیات chain code یک ناحیه بسته در صورتی که نقطه شروع آن در نظر گرفته نشود، منحصر به فرد است و کد حاصل از الگوریتم برای یک پیکسل، تنها به همان پیکسل و 8 پیکسل همسایه آن بستگی دارد. با توجه به این امر، برای پیادهسازی الگوریتم chain code بر روی FPGA، کافی است که فرمولی برای یافتن کد مربوط به یک پیکسل به طور مستقل با در نظر گرفتن پیکسلهای همسایه بیابیم. به این ترتیب برای یافتن کد بعدی، کافی است که جهت کد فعلی را دنبال کرده تا به پیکسل بعدی لبه برسیم.

در ابتدا خاطر نشان میشود که فرض ما برای طراحی الگوریتم [2] chain code ، توپر بودن شیء است و همچنین فرض می کنیم که تنها یک شیء در داخل تصویر وجود دارد. ضمناً جهت حرکت روی لبه برای یافتن chain code را نیز در خلاف جهت عقربههای ساعت در نظر میگیریم.

برای تولید کد مربوط به یک پیکسل به صورت زیر عمل میکنیم

با توجه به حالتهای مختلف پیکسلهای همسایه و با توجه به جهت حرکت روی لبه که در خلاف جهت عقربههای ساعت میباشد، حداکثر 8 کلاس مختلف برای تشخیص موقعیت پیکسل بعدی روی لبه وجود دارد که در شکل

2 نشان داده شده است. در این شکل، منظور از P پیکسل قبلی روی لبه ، منظور از © پیکسل روی لبه در حال پراسس فعلی

و منظور از X پیکسلهای خالی هستند.

1 2 4
5 X X X 1
4 X © X 2
X 1 X X


6 P X 1 1 2 4
X 6 © 2 X © 2 © 6
2 1 6 1 X

شکل : 2 کلاسهای اولویت جهت

برای هریک از کلاسها، جستجو برای یافتن پیکسل بعدی لبه، همیشه از اولویتهای داده شده در شکل 2 تبعیت می کند. اگر مجموع 8 کلاس فوق برای یافتن کد بعدی در نظر گرفته شود، ملاحظه میشود که از مجموع 512 ترکیب مختلف در پنجرۀ همسایگی تنها 13 ترکیب برای جهتهای زوج و 14 ترکیب برای جهتهای فرد قابل قبول خواهد بود.

به عنوان نمونه در شکل 3 ترکیبهای قابل قبول برای کد جهت“0” و کد جهت “1” نشان داده شدهاند. با توجه به شکل ملاحظه می شود که در هریک از حالتها همیشه چهار بیت از پنجرۀ همسایگی با توجه به جهت ثابت است و فقط پنج بیت دیگر تغییر میکنند.