پیاده سازی الگوریتم گوشه یابی هریس

 پیاده سازی الگوریتم گوشه یابی هریس با استفاده از خط لوله و موازی سازی

مرضیه بنیادی
دانشگاه صنعتی اصفهان، marzieh.bonyadi@ec.iut.ac.ir

چکیده -یافتن گوشه های موجود در تصویر یکی از پیش پردازش های لازم برای بسیاری از الگوریتم های پردازش تصویر مانند تشخیص ویژگی، ردیابی حرکت و تطبیق تصاویر است. الگوریتم هریس به دلیل مقاوم بودن در برابر اعمال چرخش و تبدیل روی تصویر برای این کار الگوریتم محبوبی است. در این مقاله دو معماری مختلف بر اساس دو سخت افزار ارائه می شود. در معماری اول از FPGA برای طراحی یک ساختار خط لوله با عملکرد بی درنگ استفاده شده است. این طراحی 3 خط لوله دارد. وضوح تصویر آن 640×480 در نظر گرفته شده است. سیستم طراحی شده توان پردازش 33/0 پیکسل در هر پالس ساعت را با فرکانس کاری 100 مگاهرتز دارد. معماری دوم برای پردازنده CSX700 یک طراحی بسیار کم مصرف و موازی را به وجود می آورد. در این طراحی با پیاده سازی کارامد به سرعت 465 فریم بر ثانیه برای تصاویر 480×640 و 142 فریم بر ثانیه برای تصاویر720×1280 دست می یابیم.
کلید واژه- الگوریتم گوشه یابی هریس، خط لوله، معماری موازی ، CSX700، FPGA.

1- مقدمه
گوشه یابی یکی از روش های پرکاربرد در پردازش تصویر است. در بسیاری از کاربری های بینایی ماشین، گوشه یابی یک پیش پردازش مهم است. از این کاربری ها می توان به تشخیص ویژگی، ردیابی حرکت، تطبیق تصویر و شناسایی اشیا اشاره کرد [1]. الگوریتم های گوشه یابی به دو دسته تقسیم می شوند: گروه اول الگوریتم های مبتنی بر کانتور هستند. در این دسته فضاهای انحنا برای دسته بندی لبه ها و گوشه ها تشکیل می شوند. گروه دوم الگوریتم های مبتنی بر شدت روشنایی تصویرر هستند. این دسته از لحاظ محاسباتی هزینه کمتری دارند و البته نسبت به دسته اول موفقیت کمتری در تشخیص دارند [2].
الگوریتم های گوشه یابی معمولا در دو مرحله مستقل پیاده سازی می شوند: محاسبه میزان قوی بودن گوشه و حذف نتایجی که بیشینه نیستند. الگوریتم های سوزان، مراوک و هریس مثال هایی از این دست الگوریتم ها هستند. در مرحله محاسبه میزان قدرت گوشه به هر پیکسل مقدار حاصل از تابع گوشه یابی تخصیص داده می شود که به آن مقدار گوشه بودن گفته می شود. عموما این مرحله با تخصیص مقادیر بالا به بسیاری از پیکسل های اطراف گوشه های تصویر به پایان می رسد. برای تعیین تنها یک پیکسل به عنوان گوشه، در مرحله دوم پیکسل با بیشترین مقدار گوشه بودن در یک همسایگی انتخاب می شود و به عنوان پیکسل گوشه در نظر گرفته می شود. در آخر الگوریتم مطمئن می شود که تمام مقادیر غیربیشینه در همسایگی حذف شده اند و پیکسل صحیح به عنوان گوشه دقیق انتخاب شده است [4].
در میان الگوریتم های موجود، الگوریتم گوشه یابی هریس به علت مقاوم بودن در برابر چرخش، تغییر اندازه، تغییر روشنایی محیط و نویز تصویر از محبوبترین الگوریتم هاست [3]. از آنجا که گوشه یابی یکی از مراحل ابتدایی کاربری های مختلف است، کارایی آن می تواند کارایی تمام سیستم را تحت الشعاع قرار دهد. بنابراین الگوریتم های مبتنی بر شدت روشنایی هم باید تا حد امکان سریع شود.
در بخش دوم مقاله راجع به جزییات الگوریتم هریس توضیح داده می شود. در بخش سوم معماری اول و معماری دوم با جزییات کامل بحث می شود. در بخش چهارم منابع محاسباتی مورد استفاده و کارایی معماری های ارائه شده بررسی می شود و در بخش پنجم نتیجه گیری مقاله ارائه خواهد شد.
2- مروری بر الگوریتم هریس
الگوریتم گوشه یابی هریس با تکیه بر این فرض عمل می کند که یک گوشه گرادیان های قوی در تمام جهات دارد [1]. همچنین عمل فیلتر کردن با فیلتر گاوسی برای رفع نویزهای تصویر انجام می شود. مراحل این الگوریتم به صورت زیر هستند:
1- محاسبه گرادیان: در دو راستای X و Y از تصویر مشتق گرفته می شود. محاسبه دو گرادیان با کانولوشن دو ماتریس همسایگی 3×3 از پیکسل مورد نظر و یک پنجره ماسک گرادیان می تواند انجام گیرد. بر اساس گرادیان های افقی و عمودی مقادیر (1) به دست می آید:

(1)

2- نرم کردن با فیلتر گاوسی: نرم کردن با فیلتر گاوسی بر سه تصویر گرادیان محاسبه شده اعمال می شود. پردازش شامل کانولوشن ماتریس گاوسی و همسایگی پیکسل های متناظر در سه تصویر گرادیان است. سه تصویر نتیجه به ترتیب I2x، I2y و Ixy نام دارد.
3- اندازه گیری هریس: برای محاسبه اندازه هریس، ماتریس S استفاده می شود:
(2)
مقادیر ویژه این ماتریس مشخص می کند که هر پیکسل قسمتی از یک سطح هموار، یک لبه یا یک گوشه است [1]. این مقدار برابر است با:
(3)
که k عددی ثابت است که مقدار آن میتواند بین 04/0 تا 06/0 انتخاب شود. اگر مقدار به دست آمده مثبت و از مقدار آستانه بزرگتر باشد آن پیکسل یک گوشه است. همچنین اگر منفی باشد و از یک مقدار آستانه کوچکتر باشد این پیکسل یک لبه است. این الگوریتم به صورت رابطه 4 برای تصاویر رنگی اصلاح شده است:[2]
(4)
4- آستانه گیری: پیکسل گوشه با مقادیر بالای معیار هریس خود را نشان می دهد. بنابر این اعمال یک آستانه می تواند نتایج نامرتبط را به راحتی حذف کند.
5- حذف گوشه های ضعیف: پیکسل گوشه با بزرگترین مقدار معیار هریس در ناحیه ای که اکثر پیکسل های آن گوشه ارزیابی شده اند معین می گردد [1].
3- معماری های پیشنهادی
در این قسمت دو معماری با دو سخت افزار مختلف ارائه می گردد.
3-1- معماری مبتنی بر استفاده از FPGA
عبارت با عنوان SOGP_xx نام گذاری می شود و به همین ترتیب برای بقیه عبارات عناوین SOGP_xy و SOGP_yy در ادامه استفاده می شود. از امکان تولید حافظه نرم افزار طراحی شرکت XILINX برای تولید ماژول واسط DDR2 استفاده شده است. برای دستورات خواندن و نوشتن خارجی این ماژول بافرهای FIFO دارد که در هر پالس ساعت می تواند یک دستور خواندن یا نوشتن را ISSUE کند.
یک محدودیت الگوریتم آن است که قبل از محاسبه ماتریس S تمام مجموع گرادیان ها در پنجره W باید محاسبه شوند. محدودیت دیگر آن است که قبل از حذف گوشه های ضعیف هر قسمت تصویر، مقدار معیار هریس تمام پیکسل های تصویر باید معلوم باشد. پس ما الگوریتم را به سه فاز مجزای خط لوله تقسیم می کنیم. اولین ماژول به جمع گرادیان ها اختصاص می یابد. ماژول دوم مقادیر خروجی ماژول اول را می گیرد و R را تولید می کند. ماژول سوم ماژول حذف گوشه های ضعیف است. برای این منظور دو معماری ممکن است که در تصویر 1 به نمایش در آمده است. اگر از معماری چپ استفاده کنیم باید از سه BRAM، یکی برای داده خام و دو BRAM برای داده های پردازش شده استفاده شود. این کار سبب از بین رفتن تاخیر اولیه می شود. در گزینه دوم تنها از یک BRAM استفاده می شود. گزینه اول زمان نهایی پردازش را سه برابر کاهش می دهد اما سه برابر بیشتر بلوک حافظه مصرف می کند. معماری پیشنهادی بر اساس روش دوم است تا منابع کمتری از FPGA به کار گرفته شوند.
ماژول های واسط برای دریافت یک باره تصویر به کار گرفته شده اند. از آنجا که پالس ساعت دوربین با حافظه یکسان نیست و این دو با هم سنکرون نیستند باید از بافر استفاده کرد. بنابراین در هنگام انتقال تصویر از BRAM دوربین، از این بافرها استفاده می شود. هر BRAM قادر به ذخیره سازی 1 سطر تصویر است.
داده خام هم مانند داده پردازش شده درون حافظه ذخیره می شود تا زمان مورد نیاز برای خواندن داده به حداقل برسد. همچنین داده ها چه خام چه پردازش شده اگر متعلق به چند ستون متوالی باشد درون حافظه در همان سطر و در ستون صحیح قرار داده می شود. بدین ترتیب در هنگام خواندن حافظه تعداد تاخیر اولیه دسترسی به سطر مینیمم می شود. ساختار کلی طرح پیاده شده در شکل 2 نمایش داده شده است.
قبل از پردازش داده ماژول واسط، داده های تصویر را به صورت همزمان می گیرد. سپس ماژول واسط این داده ها را در DDR2 ذخیره می کند. پس از ذخیره شدن تصویر، ماژول واسط ورودی ماژول های محاسباتی را تامین می کند. در وهله اول، ماژول واسط، اطلاعات خام را از DDR2 با واسط حافظه تولیدشده می خواند و اطلاعات را به BRAM ها می دهد تا خوراک خط لوله ها فراهم شود. BRAMها داده را به ماژول های SOGP منتقل می کنند و ماژول واسط منتظر نتیجه ماژول SOGP در بافر داده ماژول SOGP می شود. این بافرهای داده در انتهای ماژول های خط لوله به صورت موقت نتیجه را ذخیره می کنند. ماژول واسط تا پر شدن بافرهای داده با داده هایی که به تازگی پردازش شده اند منتظر می ماند؛ تا عملیات نوشتن کارآمد انجام گیرد. عملیات نوشتن هنگامی کارامد خواهد بود که اکثر اطلاعاتی که آنها را در حافظه می نویسیم اطلاعات تازه به دست آمده باشند. پس از آنکه تمام داده های SOGP تمام پیکسل ها محاسبه شدند و در DDR2 نوشته شدند ماژول واسط شروع به خواندن اطلاعات SOGP می کند و BRAM ها را پر می کند که ورودی ماژول اندازه گیری گوشه بودن را فراهم می کند. پس از آنکه نتایج ماژول اندازه گیری گوشه بودن آماده شد در DDR2 نوشته می شود و ماژول حذف نتایج ضعیف به طریق مشابه کار می کند. پیکسل های تصویر چپ که مشخصات گوشه را داشته باشند وقتی معین می شوند که ماژول حذف نتایج ضعیف خروجی ماژول میزان گوشه بودن را پردازش می کند و نتایج در BRAM نوشته می شود. برای هر تصویر سیستم قادر به ثبت 1024 گوشه است. وقتی مختصات گوشه ها داخلBRAM ها نوشته شد تمام گوشه ها روی تصویر نمایش داده می شود.
پس از آزمایش های تجربی روی تصاویر، پنجره 7×7 در فاز حذف نتایج ضعیف و ماسک های 5×5 برای ماژول های SOGP و میزان گوشه بودن استفاده شد. برای مینیمم کردن مصرف منابع محاسباتی، محاسبات با عدد صحیح انجام شدند. در هنگام محاسبه SOGP برای کاهش نویز از ماسک هایی استفاده شد که ضرایب با توزیع گاوسی اصلاح شده با سیگمای 2/1 داشت. در شکل 3 ماسک های افقی و عمودی در چپ و وسط نشان داده شده است و ماسک راست مربوط به کل پنجره است. K در اینجا 0625/0 در نظر گرفته شد که معادل است. پیاده سازی ضرب با این ثابت متناظر با یک شیفت ساده بدون نیاز به سخت افزار اضافه است.
ماژولSOGP
این ماژول مسئول محاسبه SOGPxx، SOGPyy و SOGPxy پیکسل ها به صورت موازی با ماسک های گرادیان 5×5 است. این ماژول 5 پیکسل واقع در یک ستون از 5 سطر متوالی را در هر پالس ساعت می خواند. برای ذخیره شدت روشنایی 5 شیفت رجیستر دارد که به آنها شیفت رجیسترهای شدت روشنایی می گوییم. برای ماکزیمم کردن بازدهی خط لوله 5 مقدار باید در هر پالس ساعت به 5 شیفت رجیستر داده شود. برای این کار از BRAMهای FPGA استفاده شد. 6 BRAM که هرکدام ظرفیت ذخیره یک سطر از روشنایی ها، مرکب از 15 بیت را دارد. BRAM ها طوری طراحی شده اند که تعداد بیت هایی که می توان در یک پالس ساعت در آنها نوشت از تعداد بیت هایی که می توان از آنها خواند بیشتر است. بنابراین اشغال بودن خط لوله تمام ماژول ها امکان پذیر است. برای پردازش داده های یک تصویر ابتدا شدت روشنایی های 5 سطر اول تصویر از DDR2 خوانده می شود. به واسطه ماژول واسط روی BRAMها نوشته می شود. پس از آنکه تمام BRAM ها پر شدند شیفت رجیسترهای SOGP با داده های ستون های متوالی شروع به کار می کنند تا SOGP سطر سوم را محاسبه کنند. همزمان ششمین BRAM با ششمین سطر تصویر پر می شود. نتایج SOGP نیز همزمان به داخل DDR2 می ریزد. این ششمین BRAM قبل از آنکه 5 BRAM اول برای ماژول SOGP استفاده شوند پر می شود. چون بافرهای داده برای بالا بردن بازدهی نوشتن استفاده شده اند و تعداد بیت قابل نوشتن بر روی BRAM از تعداد قابل خواندن در یک دور کمتر است. پس از آنکه تمام 5 BRAM به ماژول SOGP داده شدند، روشنایی ششمین سطر تصویر داده می شود تا با روشنایی سطوح 2 تا 5 در نظر گرفته شود و محاسبات انجام شود. و به همین ترتیب محاسبات ادامه می یابد. در ماژول SOGP شیفت رجیستر دیگری وجود دارد که یک بیت از داده را در سلول خود نگهداری می کند. این شیفت رجیستر، برای علامت دادن به واسط استفاده می شود که اعلام می کند که ماژول SOGP دارای اطلاعات پردازش شده و بامعنا است. تعداد سلول های این شیفت رجیستر 10 است. اولین سلول از شیفت رجیستر به یکی از ورودی های ماژول SOGP متصل است و سلول آخر به یکی از خروجی های ماژول SOGP متصل است. ورودی به وسیله ماژول واسط وقتی وارد می شود که شیفت رجیسترهای ماژول SOGP از داده پردازش شده و بامعنا پر شده باشند. بیت 1 شده شیفت می یابد و داده ها در همین حین در هر پالس ساعت در ماژول SOGP پردازش می شود.
داده پردازش شده و بیت 1 شده به صورت همزمان به خروجی می رسند که به ماژول واسط اجازه می دهد داده پردازش شده را با چک کردن خروجی ماژول SOGP که به خروجی آخرین سلول شیفت رجیستر مرجع متصل است دریافت کند. SOGP طراحی شده شامل 10 مرحله است که هر یک در یک پالس ساعت به پایان می رسد. در 5 مرحله اول 6 زیرماژول موازی برای محاسبه گرادیان های Rx، Ry، Gx، Gy، Bx و By وجود دارد. با استفاده از این گرادیان ها SOGP ها در 5 مرحله بعدی در زیرماژول دیگری محاسبه می شوند. زیر ماژول مسئول محاسبه Rx در شکل 4 نشان داده شده است.
برای این محاسبه ها تمام گرادیان ها به ضرب کننده های موازی با تاخیر اولیه 3 پالس ساعت داده می شود. حاصل ضرب ها در مرحله 9 و 10 دو به دو جمع می شوند. به وسیله خروجی شیفت رجیستر مرجع مطلع می شود که داده بامعنا در خروجی ماژول SOGP موجود است. ماژول واسط در رجیسترهای 256 بیتی نتایج را ذخیره میکند. وقتی رجیستر پر می شود نتایج در DDR2 نوشته می شود.
ماژول میزان گوشه بودن
ساختار ماژول میزان گوشه بودن مشابه ماژول SOGP است. در هر پالس ساعت قادر به دریافت 5 نتیجه از یک ستون در 5 سطر متوالی یک تصویر است. در محاسبه میزان گوشه بودن ماسک 5×5 گاوسی مورد استفاده قرار می گیرد. بنابراین 5 شیفت رجیستر با 5 سلول برای ذخیره و شیفت SOGP ها
شکل 4- زیرماژول مربوط به محاسبه Rx

استفاده می شود. این شیفت رجیسترها مشابه شیفت رجیسترهای ماژول SOGP هستند. اما ظرفیت هر سلول آن 45 بیت است. برای تغذیه این رجیسترها مانند ساختار تغذیه ماژول SOGP از BRAM استفاده شده است. 6 BRAM قبلی به همراه 12 BRAM جدید مورد استفاده قرار می گیرند. در هنگام محاسبه میزان گوشه بودن های یک پیکسل در یک سطر 15 BRAM استفاده می شوند و 3 تای باقی‎مانده با مقادیر جدید SOGP پر می شوند. بنابراین این امکان وجود دارد که ماژول میزان گوشه بودن با 15×15 بیت داده در هر دور تغذیه شود. علاوه بر این شیفت رجیستر مرجع دیگری شامل 11 مرحله در این ماژول استفاده شده است. در 6 مرحله اول مقادیر AB و C در 3 زیر ماژول به صورت موازی محاسبه می شوند. در 5 مرحله بعدی میزان گوشه بودن ها با استفاده از مقادیر به دست آمده محاسبه می شوند. زیر ماژولی که A را محاسبه می کند در شکل 5 نشان داده شده است. در مرحله اول مقادیر SOGPxx پیکسل ها که در شیفت رجیسترهای SOGP است آورده می شود. این مقادیر باید در 3 و 6 و 12 ضرب شوند. بقیه مقادیر که باید با ضرایبی از 2 ضرب شوند دو به دو جمع شده و عملیات شیفت به جای ضرب بر آنها اعمال می شود. از مرحله 2 تا مرحله 6 تمام ضرایب مقادیر SOGPxx دو به دو جمع می شوند تا A را تولید کنند. در مرحله 6، 24 بیت A تولید شده است. اما تنها 21 بیت کم ارزش آن و 1 بیت علامت معنادارند. چون مایل به قرار دادن المان تقسیم نیستیم با 6 بار شیفت 22 بیت معنادار A که متناظر با تقسیم بر 64 است این کار را انجام می دهیم. در نتیجه A 16 بیتی در مرحله 6 تولید می شود. 2 آینه موازی این ماژول وجود دارند. که B و C را محاسبه می کنند.

پس از آنکه این مقادیر محاسبه شدند به زیرماژول های دیگر که مسئول محاسبه خود میزان گوشه بودن هستند می روند. در مرحله 7 ضرب مقادیر A×B و C2 انجام می شود. علاوه بر آن A+B محاسبه می شود تا محاسبه 2(A+B) در مرحله 8 آغاز شود. تمام المان های ضرب استفاده شده 3 پالس ساعت تاخیر اولیه دارند. در مرحله 10، ضربها پایان می یابد و جمع انجام می شود. ضرب (A+B) قبل از مرحله 11 پایان می یابد. از آنجا که k هم فرض شد نیازی به سخت افزار اضافه برای تقسیم نیست. در مرحله 11 تفریق 2(A+B) از AB+C2 انجام می گیرد. از آنجا که اگر این مقدار حاصله مثبت و از یک مقدار آستانه بیشتر باشد گوشه ارزیابی می شود در همین مرحله مقایسه انجام می شود و بعد از آن نوشتن مقادیر در بافر ماژول واسط انجام می شود. همچنین اگر این مقادیر منفی و از یک آستانه کوچکتر باشند در بافر داده صفر نوشته می شود. در غیر این صورت مقدار 32 بیتی میزان گوشه بودن بدون بیت علامت در بافرهای داده نوشته می شود. پس از آنکه بافرهای داده پر شد مقادیر در DDR2 نوشته می شود. بدین ترتیب فاز دوم الگوریتم هم به انجام می رسد.
ماژول حذف نتایج ضعیف
کار این ماژول حذف نتایج ضعیف گوشه بودن در یک پنجره 7×7 است. 7 شیفت رجیستر که هر یک 7 سلول 32 بیتی دارد. استفاده می شوند. BRAM ها که بقیه ماژول های خط لوله را تغذیه می کردند در این ماژول هم برای تغذیه شیفت رجیسترها استفاده می شوند. 16 BRAM از 18 BRAM قبل استفاده می شوند. وقتی ماژول حذف نتایج ضعیف فعال است 14 BRAM ماژول را تغذیه می کنند و دو واحد دیگر برای ذخیره مقادیر محاسبه شده مراحل قبل سطرهای متوالی استفاده می شوند. در ماژول حذف نتایج ضعیف 48 مقایسه کننده موازی تعبیه شده است. در هر پالس ساعت ماژول قادر به دریافت 7 مقدار برای پیکسل های درون یک ستون با سطرهای متوالی و ذخیره آنها در شیفت رجیستر های ماژول است. در هنگام تشخیص گوشه های هر سطر، میزان گوشه بودن مرکز هر پنجره با دیگر المان های پنجره مقایسه می شود. مختصات گوشه های پیدا شده در BRAM جدایی ذخیره می شوند [2].
3-2- استفاده از یک پردازنده چند هسته ای
در این قسمت پیاده سازی سریع الگوریتم هریس روی CSX700 بحث می شود. این پردازنده دارای حداکثر قدرت محاسباتی GFLOS 96 است و کمتر از 9 وات مصرف توان دارد که می توان گفت یکی از بهترین کارایی ها را با معیار GFLOPS/Watt دارد.
معماری CSX700
این پردازنده دو هسته مشابه دارد که هر یک واسط حافظه DDR2 و 128 کیلو بایت SRAM دارد که به آن حافظه خارجی می گویند. هر هسته یک واحد کنترل مانند RISC دارد که واحد اجرایی mono نام دارد که با یک معماری موازی SIMD که واحد اجرایی poly نام دارد جفت شده اند.
واحد اجرایی poly شامل 96 المان پردازشی است. هر المان پردازشی 128 بایت فایل رجیستر، 6 کیلو بایت SRAM، یک ALU یک جمع و ضرب کننده صحیح و یک واحد محاسبه اعشاری دارد. این اجزا با یکدیگر به صورت موازی کار می کنند و در هر پالس ساعت یک نتیجه حاصل می کنند. اما عملیات سریال، مانند یک جمع یا یک ضرب 4 پالس ساعت برای اجرا زمان نیاز دارد. از آنجا که ممکن است تبدیلات کد کامپایلر همواره بهینه نباشد بخشی از کد به زبان اسمبلی خود CSX نوشته شده است.
واحد اجرا شامل یک واحد ورودی/خروجی قابل برنامه ریزی است. معماری واحد اجرای poly، واحد محاسباتی و ورودی و خروجی را قادر می سازد که به صورت موازی با هم کار کنند. یعنی باعث همپوشانی زمان محاسبه و ارتباط می شود. همچنین یک باس مخصوص که مسیر سوازل نامیده شده، فایل های رجیستر واحدهای محاسباتی همسایه را به هم مرتبط می کند. یعنی رجیسترها قادرند همزمان از همسایه خود داده بگیرند و به همسایه خود داده بدهند.
پیاده سازی موازی پیشنهادی
با در نظر گرفتن معماری CSX مدل محاسباتی با داده موازی در نظر گرفته شد. ابتدا درباره استراتژی تجزیه داده بحث می کنیم. با وجود یک تصویر و تعدادی المان محاسباتی می توانیم تصویر را به صورت سطری نواری، سطری دوره ای و یا بلوکی وارد کنیم. برای هر یک از این روش ها معایب و مزایایی وجود دارد که در ادامه می آید. برای مقایسه باید این پارامترها مورد ارزیابی قرار گیرند:1- میزان فضای حافظه مورد نیاز برای هر المان محاسباتی 2- میزان ارتباط با حافظه خارجی و3- زمان ارتباط داخلی هر المان محاسباتی. در ادامه c و r تعداد ستون ها و سطرهای ماتریس تصویر را نشان می دهند. بر اساس الگوریتم هریس، یک مجموعه عملیات باید حول یک پیکسل در یک پنجره انجام گیرند. در حقیقت هریس پنجره هایی استفاده می کند که می توانند در سه مرحله اندازه های مختلف داشته باشند: مشتق جزیی، نرم کردن با فیلترهای گاوسی و حذف نتایج ضعیف. W مجموع اندازه این سه پنجره است. p هم تعداد المان های محاسباتی را نشان می دهد. در انتها در هر ارتباط با حافظه هر المان m بایت داده را یا درون حافظه خارجی می ریزد یا از آن می گیرد. Π فضایی از حافظه است که برای محاسبه ماتریس هریس m پیکسل نیاز است.
توزیع بلوکی: تصویر به p بلوک تقسیم می شود. هر بلوک از تصویر به یک المان محاسباتی می رود. و هر بلوک با زوج مرتب (i, j) مشخص می شود. شکل 6 داده های مرزی مورد نیاز را نشان می دهد.

شکل 6-توزیع بلوکی
برای آنکه دو محاسبه گر همسایه از داده مرزی استفاده کنند دو راه وجود دارد یکی آن که هر دو مستقلا این داده را از طریق ارتباط با حافظه خارجی دریافت کنند و دیگر آن که داده مشترک به یکی از همسایه ها داده شود و از طریق مسیر سوازل به محاسبه گر همسایه سپرده شود. روش اول زمان بیشتر و روش دوم فضای حافظه بیشتری برای محاسبه گر نیاز دارد تا بتواند داده را آنگونه که در ادامه گفته شده ذخیره کند. برای پردازش اولین ستون در هر المان محاسباتی به آخرین ستون المان قبلی نیاز است. اما المان های قبلی هنوز این اطلاعات را دریافت نکرده اند. پس المان محاسباتی باید تا رسیدن این اطلاعات پردازش های ستون اول را انجام ندهد. همچنین برای پردازش داده آخرین ستون داده به داده ای که به المان محاسباتی بعدی فرستاده شده نیاز است. این مقدار باید در حافظه ذخیره شود که خود حافظه محدود است. باید به یاد داشته باشیم که در معماری CSX فاصله میان دو المان همسایه به اندازه d است و هر بلوک c/d ستون دارد.
توزیع نواری سطری: به هر المان محاسباتی r/p سطر داده می شود. برای داده های مرزی هر المان محاسباتی به سطر آخر المان قبلی و سطر اول المان بعدی احتیاج دارد. در حقیقت مانند توزیع بلوکی می توان دو راهکار داشت. که مزایا و معایب آن نیز گفته شد.
توزیع سطری دوره ای: به هر المان محاسباتی یک سطر داده می شود. چون به هر المان یک سطر داده شده هریک از المان ها باید با المان دیگری در فاصله حداکثر نصف اندازه پنجره ارتباط داشته باشند. در این وضعیت هر المان زمانی به داده نیاز پیدا می کند که همسایه آن کار پردازشی خود را روی آن داده تمام کرده است. پس مسیر سوازل بدون نیاز به فضای حافظه poly می تواند استفاده شود.
در دو توزیع ابتدایی با بالا رفتن اندازه پنجره میزان نیاز به حافظه poly به صورت خطی افزایش می یابد. با اینکه روش سطری چرخشی ω/2 برابر نسبت به روش سطری نواری از ارتباطات میان المان های محاسباتی استفاده می کند اما با توجه به کاهش نیاز به حافظه ploy این بالاسری قابل اغماض است. پس این نوع توزیع داده انتخاب می شود.
پیاده سازی موازی الگوریتم گوشه یاب هریس
از آنجا که هر هسته CSX از 96 المان محاسباتی تشکیل شده است تصویر ورودی به گروه های 96 سطری تقسیم می شود. محاسبه هر گروه یک جاروب را به دنبال دارد و این جاروب ها متوالی انجام می شود. همچنین برای مصرف دو هسته پردازنده، تصویر به دو قسمت تقریبا مساوی تقسیم می شود. اولین سطر به اولین هسته تخصیص می یابند و و بقیه به هسته دوم تخصیص می یابند. فرستادن خطوط مرزی به هر دو هسته باعث می شود محاسبات دو هسته به صورت محلی انجام گیرد.
الگوی ارتباطی حافظه:
در این پیاده سازی ارتباط و همپوشانی محاسبات لحاظ شده است و هیچ یک از المان های محاسباتی به انتظار دریافت داده از حافظه خارجی بیکار نمی شوند.( به استثنای ابتدای کار سیستم) هر سطر تصویر به اندازه های مساوی مثلا 32 یا 64 پیکسل تقسیم می شود. پس از دریافت اولین بسته از داده در حالیکه هر المان محاسباتی کار پردازشی خود را بر روی داده آماده انجام می دهد باقی بسته های داده وارد سیستم می شوند.
برای محاسبه مشتق جزیی از عملگر پریویت استفاده شده است. این عملگر از دو ماسک 3×3 استفاده می کند که با تصویر اصلی کانوالو می شوند. این ماسک های کانولوشن جدایی پذیرند. یعنی می توانند به صورت ضرب خارجی دو وکتور بیان شوند.
پس مشتق x و y می توانند این گونه محاسبه شوند که اول در یک جهت کانوالو صورت گیرد و سپس داده به همسایه شود و در راستای دیگر کانوالو شود. از آنجا که کرنل گاوسی هم جدایی پذیر است می توان کانولوشن دو بعدی را به صورت دو کانولوشن 1 بعدی انجام داد. در مرحله بعد، بیشترین مقدار شاخص هریس در پنجره های 3×3 تعیین می شود. ابتدا هر المان مقدار ماکزیمم همسایگی 3×1 را می یابد و سپس هر المان محاسباتی مقادیر بیشینه را به دو همسایه اش می فرستد. با دریافت مقادیر ماکزیمم دو سطر همسایه مقدار ماکزیمم در یک همسایگی 3×3 به دست می آید. [3]
4- نتایج و ارزیابی
در این بخش به ارزیابی نتایج پیاده سازی می پردازیم. به دلیل پیشنهاد دو معماری این بخش به دو قسمت تقسیم می شود.
4-1- ارزیابی نتایج معماری مبتنی بر FPGA
در جدول 1 میزان منابع مصرفی معماری دیده می شود. بر اساس این جدول ماژول های خط لوله و ساختارهای تغذیه آنها 17% رجیسترهای موجود، 14%LUTهای موجود، 25% واحدهای DSP و 38% BRAMهای FPGA را استفاده کرده اند. از سوی دیگر، ماژول واسط که عملکردها را کنترل می کند تقریبا 32% رجیسترها، 49% LUTهای موجود را مصرف می کند. تمام ماژول های طراحی بیش از نصف BRAMهای FPGA را مصرف می کنند. بنابراین نمی توان برای هر ماژول یک مجموعه BRAM در نظر گرفت که در معماری پیشنهادی اولیه وجود داشت. همچنین بازدهی این معماری خط لوله طراحی شده در جدول 2 آمده است. فرکانس کاری ماکزیمم کل طراحی 123 مگاهرتز است. بنابراین در پیاده سازی پالس ساعت سیستم را 100 مگاهرتز در نظر می گیریم. زمان اجرا برای تصاویر استریو با رزولوشن 640×480، 1856550 پالس ساعت است. که به این معناست که سیستم قادر به پردازش33/0 پیکسل در هر پالس ساعت است. این متناظر با زمان اجرای 57/18 میلی ثانیه با پالس ساعت 100 مگاهرتز است. زمان اجرای یک تصویر برابر 29/9 میلی ثانیه است.

زمان اشغال خط لوله توسط هر ماژول تقریبا 3/1 کل زمان است. چون ماژول ها تا خوراک اطلاعاتشان فراهم نشود نمی توانند کار کنند. اگر می توانستیم برای هر ماژول مجموعه BRAMهای مستقل استفاده کنیم آنگاه موفق به بالا بردن میزان اشغال خط لوله توسط ماژول ها می شدیم [2].
4-2- ارزیابی و نتایج معماری دوم
برای ارزیابی کارایی، دو معماری با اندازه پنجره گاوسی 3×3 و 5×5 پیاده سازی شد. چون روش موازی ما انعطاف مناسبی فراهم می کند می تواند به تصاویر با اندازه های مختلف اعمال شود. کارایی الگوریتم های پیاده سازی شده با تاخیر اولیه نرخ تصویر و GFLOPS معین برای وضوح های مختلف تصویر در جدول 3 آمده است. چگالی محاسبات یعنی تعداد عملیات بر پیکسل 3×3 و 5×5، 40 و 64 است. GFLOPS به اندازه تصویر هم وابسته است. چون در پردازش آخرین گروه سطرهای داده بعضی از المان های محاسباتی ممکن است بیکار بمانند. و تعداد آنها وابسته به اندازه تصویر است [3].
5- نتیجه گیری
در این مقاله دو معماری کامل برای یکی از پیش پردازش های لازم در بسیاری از ماژول های پردازش تصویر یعنی گوشه یابی با الگوریتم هریس ارائه شد. اولین معماری بر اساس سخت افزار FPGA و با خط لوله بهینه شده برای تصاویر رنگی ارائه شد. در هنگام طراحی معماری تصمیم بر طراحی با بالاترین کارایی و کمترین منابع بوده است. معماری طراحی شده تنها به یک DDR2 نیازمند است و از پالس ساعت 100 مگاهرتز استفاده می کند. برای پیاده سازی این معماری متشکل از 3 ماژول خط لوله 25% از منابع FPGA کوچک XC5VLX50 کافی است. معماری قادر به پردازش 33/0 پیکسل در هر پالس ساعت است.
معماری دوم بر مبنای یک پردازنده دو هسته ای ارائه شد. این معماری با ساختار SIMD و بسیار سریعتر از یک پیاده سازی

بی درنگ است. با توجه به ویژگی های CSX700 استراتژی هایی برای پیاده سازی موازی الگوریتم هریس پیشنهاد شد. این معماری قادر به کار با فرکانس کاری 465 فریم بر ثانیه برای تصاویر با وضوح 480×640 و 142 فریم بر ثانیه برای تصویری با وضوح 720×1280 است.
6- مراجع

[1]
Amaricai A., Gavriliu C., Boncalo O., "An FPGA Sliding Window-Based Architecture Harris Corner Detector," in International Conference on Field Programmable Logic and Applications, 2014.
[2]
Aydogdu M., Demirci M.,Kasnakoglu C., "Pipelining Harris Corner Detection with a Tiny FPGA for a Mobile Robot," in IEEE International Conference on Robotics and Biomimetics (ROBIO), 2013.
[3]
Hosseini F., Fijany A.,Fontaine J., "Highly parallel implementation of Harris Corner detector on CSX SIMD architecture," in Euro-Par Parallel Processing Workshops, 2011.
[4]
Teixeira L., Celes Filho W., Gattass M., "Accelerated Corner-Detector Algorithms," in British Machine Vision Conference, 2008.

30 اردیبهشت تا 1 خرداد 1393، دانشگاه شهید بهشتی

4

8