هیستوگرام گرادیان‌های جهت‌دار

هیستوگرام گرادیان‌های گرا (HOG) یک توصیفگر ویژگی است که در بینایی کامپیوتری و پردازش تصویر به منظور تشخیص اشیا استفاده می‌شود. این تکنیک، جهت‌گیری گرادیان را در بخش‌های محلی یک تصویر شمارش می‌کند. این روش شبیه هیستوگرام‌های جهت‌گیری لبه، توصیف‌گرهای تبدیل ویژگی تغییرناپذیر مقیاس، و زمینه‌های شکل است، اما از این جهت متفاوت است که بر روی شبکه‌ای متراکم از سلول‌های با فاصله یکنواخت محاسبه می‌شود و از نرمال‌سازی کنتراست محلی همپوشانی برای بهبود دقت استفاده می‌کند.

رابرت کی مک کانل از شرکت تحقیقاتی Wayland اولین بار مفاهیم پشت HOG را بدون استفاده از اصطلاح HOG در یک درخواست ثبت اختراع در سال ۱۹۸۶ توصیف کرد.^[۱] در سال ۱۹۹۴ این مفاهیم توسط آزمایشگاه تحقیقاتی میتسوبیشی الکتریک مورد استفاده قرار گرفت.^[۲] با این حال، زمانی که ناونیت دالال و بیل تریگز، محققان مؤسسه ملی تحقیقات علوم کامپیوتر و اتوماسیون فرانسه (INRIA)، کار تکمیلی خود را در مورد توصیفگرهای HOG در کنفرانس بینایی کامپیوتری و تشخیص الگو (CVPR) ارائه کردند، استفاده از آن در سال ۲۰۰۵ گسترده شد). در این کار آنها بر روی تشخیص عابر پیاده در تصاویر ایستا تمرکز کردند، اگرچه از آن زمان آزمایش‌های خود را گسترش دادند تا تشخیص انسان در فیلم‌ها و همچنین انواع حیوانات و وسایل نقلیه رایج در تصاویر ثابت را شامل شود.

تئوری[ویرایش]

تفکر اساسی پشت توصیفگر هیستوگرام گرادیان‌های جهت دار این است که ظاهر و شکل شی محلی در یک تصویر را می‌توان با توزیع گرادیان‌های شدت یا جهت‌های لبه توصیف کرد. تصویر به مناطق کوچک متصل به نام سلول تقسیم می‌شود و برای پیکسل‌های درون هر سلول، یک هیستوگرام از جهت‌های گرادیان کامپایل می‌شود. توصیفگر الحاق این هیستوگرام‌ها است. برای دقت بهتر، هیستوگرام‌های محلی را می‌توان با محاسبه اندازه‌گیری شدت در ناحیه بزرگ‌تری از تصویر، به نام بلوک، و سپس با استفاده از این مقدار برای عادی‌سازی تمام سلول‌های داخل بلوک، با کنتراست نرمال کرد. این عادی سازی منجر به تغییرناپذیری بهتری نسبت به تغییرات در روشنایی و سایه می‌شود.

توصیفگر HOG چند مزیت کلیدی نسبت به سایر توصیفگرها دارد. از آنجایی که بر روی سلول‌های محلی کار می‌کند، به جز برای شی گرایی، نسبت به تبدیل‌های هندسی و فتومتریک ثابت است. چنین تغییراتی فقط در مناطق فضایی بزرگتر ظاهر می‌شود. علاوه بر این، همان‌طور که دالال و تریگز کشف کردند، نمونه‌برداری فضایی درشت، نمونه‌گیری جهت‌گیری دقیق و نرمال‌سازی فتومتریک محلی قوی اجازه می‌دهد تا زمانی که عابران پیاده وضعیت تقریباً عمودی خود را حفظ کنند، حرکات بدن فردی نادیده گرفته شود؛ بنابراین توصیفگر HOG به ویژه برای تشخیص انسان در تصاویر مناسب است.^[۳]

پیاده‌سازی الگوریتم[ویرایش]

محاسبه گرادیان[ویرایش]

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

[-1,0,1]{\text{ and }}[-1,0,1]^{\top }.\,

دالال و تریگز ماسک‌های پیچیده‌تر دیگری مانند ماسک سوبل ۳×۳ یا ماسک‌های مورب را آزمایش کردند، اما این ماسک‌ها عموماً در تشخیص انسان در تصاویر ضعیف‌تر عمل کردند. آنها همچنین قبل از استفاده از ماسک مشتق، محو کردن گاوسی را آزمایش کردند، اما به‌طور مشابه دریافتند که حذف هر گونه محوی در عمل بهتر کار می‌کند.^[۴]

سطل‌بندی جهت‌ها[ویرایش]

مرحله دوم محاسبه، ایجاد هیستوگرام سلولی است. هر پیکسل درون سلول بر اساس مقادیر یافت شده در محاسبه گرادیان، یک رای وزنی برای یک سطل هیستوگرام مبتنی بر جهت‌گیری می‌دهد. سلول‌ها می‌توانند مستطیل یا شعاعی شکل باشند و کانال‌های هیستوگرام به‌طور مساوی بین ۰ تا ۱۸۰ درجه یا ۰ تا ۳۶۰ درجه پخش می‌شوند، بسته به اینکه گرادیان «بدون جهت» یا «جهت‌دار» باشد. دالال و تریگز دریافتند که گرادیان‌های بدون علامت مورد استفاده در ارتباط با ۹ کانال هیستوگرام در آزمایش‌های تشخیص انسان خود بهترین عملکرد را داشتند، در حالی که اشاره کردند که گرادیان‌های جهت‌دار منجر به پیشرفت‌های قابل‌توجهی در تشخیص برخی کلاس‌های دیگر شی، مانند اتومبیل یا موتور سیکلت می‌شوند.

بلوک‌های توصیفگر[ویرایش]

برای در نظر گرفتن تغییرات در روشنایی و کنتراست، نقاط قوت گرادیان باید به صورت محلی نرمال شوند، که مستلزم گروه‌بندی سلول‌ها با هم در بلوک‌های بزرگتر و به هم متصل مکانی است. سپس توصیفگر HOG بردار متصل شده اجزای هیستوگرام سلولی نرمال شده از تمام مناطق آن بلوک است. این بلوک‌ها معمولاً همپوشانی دارند، به این معنی که هر سلول بیش از یک بار به توصیفگر نهایی کمک می‌کند. دو هندسه بلوک اصلی وجود دارد: بلوک‌های مستطیلی R-HOG و بلوک‌های دایره ای C-HOG. بلوک‌های R-HOG به‌طور کلی شبکه‌های مربعی هستند که با سه پارامتر نشان داده می‌شوند: تعداد سلول در هر بلوک، تعداد پیکسل در هر سلول و تعداد کانال در هر سلول هیستوگرام. در آزمایش تشخیص انسان دالال و تریگز، پارامترهای بهینه چهار سلول ۸×۸ پیکسل در هر بلوک (۱۶×۱۶ پیکسل در هر بلوک) با ۹ کانال هیستوگرام یافت شد. علاوه بر این، آنها دریافتند که با اعمال یک پنجره مکانی گاوسی در هر بلوک قبل از جدول‌بندی آرای هیستوگرام به منظور وزن کمتر پیکسل‌ها در اطراف لبه بلوک‌ها، می‌توان بهبود جزئی در عملکرد به دست آورد. بلوک‌های R-HOG کاملاً شبیه به توصیف‌کننده‌های تبدیل ویژگی تغییرناپذیر مقیاس (SIFT) هستند. با این حال، علی‌رغم شکل‌گیری مشابه، بلوک‌های R-HOG در شبکه‌های متراکم در یک مقیاس منفرد بدون هم‌ترازی جهت محاسبه می‌شوند، در حالی که توصیفگرهای SIFT معمولاً در نقاط تصویر کلیدی پراکنده و تغییرناپذیر مقیاس محاسبه می‌شوند و برای تراز کردن جهت‌گیری می‌چرخند. علاوه بر این، بلوک‌های R-HOG به همراه برای رمزگذاری اطلاعات فرم فضایی استفاده می‌شوند، در حالی که توصیفگرهای SIFT به تنهایی استفاده می‌شوند.

بلوک‌های دایره‌ای HOG (C-HOG) را می‌توان در دو نوع یافت: آنهایی که دارای یک سلول منفرد و مرکزی هستند و آنهایی که دارای یک سلول مرکزی تقسیم زاویه‌ای هستند. علاوه بر این، این بلوک‌های C-HOG را می‌توان با چهار پارامتر توصیف کرد: تعداد سطل‌های زاویه ای و شعاعی، شعاع سطل مرکزی و ضریب انبساط برای شعاع سطل‌های شعاعی اضافی. دالال و تریگز دریافتند که دو نوع اصلی عملکرد یکسانی ارائه می‌دهند و دو سطل شعاعی با چهار سطل زاویه ای، شعاع مرکزی ۴ پیکسل و ضریب گسترش ۲ بهترین عملکرد را در آزمایش خود ارائه می‌دهند (برای دستیابی به عملکرد خوب، بالاخره از این پیکربندی استفاده کنید). همچنین، وزن دهی گاوسی هنگام استفاده همراه با بلوک‌های C-HOG هیچ فایده ای نداشت. بلوک‌های C-HOG شبیه به توصیف‌کننده‌های زمینه شکل به نظر می‌رسند، اما به شدت از این نظر متفاوت هستند که بلوک‌های C-HOG حاوی سلول‌هایی با کانال‌های جهت‌گیری متعدد هستند، در حالی که بافت‌های شکل تنها از یک تعداد وجود لبه در فرمول‌بندی خود استفاده می‌کنند.^[۵]

نرمال‌سازی بلوکی[ویرایش]

دالال و تریگز چهار روش مختلف را برای نرمال‌سازی بلوک بررسی کردند. اگر $v$ بردار غیر نرمال شده حاوی تمام هیستوگرام‌ها در یک بلوک معین باشد، $\|v\|_{k}$ k -norm برای آن باشد $k={1,2}$ و $e$ مقداری ثابت کوچک باشد. سپس ضریب عادی سازی می‌تواند یکی از موارد زیر باشد:

L2-norm:

f={v \over {\sqrt {\|v\|_{2}^{2}+e^{2}}}}

L1-norm:

f={v \over (\|v\|_{1}+e)}

L1-sqrt:

f={\sqrt {v \over (\|v\|_{1}+e)}}

در آزمایش‌های خود، دالال و تریگز دریافتند که طرح‌های L2-norm و L1-sqrt عملکرد مشابهی را ارائه می‌دهند، در حالی که L1-norm عملکرد کمی کمتر قابل اعتماد را ارائه می‌دهد. با این حال، هر سه روش بهبود بسیار قابل توجهی را نسبت به داده‌های غیرعادی نشان دادند.^[۶]

تشخیص اشیا[ویرایش]

توصیفگرهای HOG می‌توانند به عنوان ویژگی برای الگوریتم یادگیری ماشین برای تشخیص شی مورد استفاده قرار گیرند. دالال و تریگز از توصیفگرهای HOG به عنوان ویژگی در ماشین بردار پشتیبان (SVM) استفاده کردند.^[۷] با این حال، توصیفگرهای HOG به یک الگوریتم یادگیری ماشین خاص گره‌خورده نیستند.

کارایی[ویرایش]

در آزمایش اصلی تشخیص انسان، دالال و تریگز بلوک‌های توصیفگر R-HOG و C-HOG خود را با موجک‌های هار تعمیم‌یافته، توصیف‌گرهای PCA-SIFT و توصیف‌گرهای زمینه شکل مقایسه کردند. موجک‌های هار تعمیم یافته، موجک‌های هار گرا هستند و در سال ۲۰۰۱ توسط موهان، پاپاجئورگیو و پوجیو در آزمایش‌های تشخیص اشیاء خود استفاده شدند. توصیفگرهای PCA-SIFT مشابه توصیفگرهای SIFT هستند، اما در این که تجزیه و تحلیل مؤلفه اصلی برای وصله‌های گرادیان نرمال شده اعمال می‌شود، متفاوت هستند. توصیفگرهای PCA-SIFT برای اولین بار در سال ۲۰۰۴ توسط Ke و Sukthankar مورد استفاده قرار گرفت و ادعا شد که بهتر از توصیفگرهای SIFT معمولی عمل می‌کند. در نهایت، زمینه‌های شکل از سطل‌های دایره‌ای استفاده می‌کنند، مشابه مواردی که در بلوک‌های C-HOG استفاده می‌شوند، اما فقط آرا را بر اساس حضور لبه جدول‌بندی می‌کنند، و هیچ حساسیتی نسبت به جهت ندارند. زمینه‌های شکل در ابتدا در سال ۲۰۰۱ توسط Belongie, Malik و Puzicha استفاده شد.

پیشرفتهای بعدی[ویرایش]

به‌عنوان بخشی از کارگاه کلاس‌های اشیاء تصویری پاسکال در سال ۲۰۰۶، دالال و تریگز نتایجی را در مورد اعمال هیستوگرام توصیفگرهای گرادیان جهت‌یافته برای اشیاء تصویری غیر از انسان، مانند اتومبیل، اتوبوس و دوچرخه، و همچنین حیوانات معمولی مانند سگ، گربه، ارائه کردند. و گاوها آنها با نتایج خود پارامترهای بهینه برای فرمولاسیون بلوک و نرمال‌سازی را در هر مورد گنجاندند. تصویر مرجع زیر برخی از نمونه‌های تشخیص آنها را برای موتور سیکلت نشان می‌دهد.^[۸]

به عنوان بخشی از کنفرانس اروپایی بینایی کامپیوتری (ECCV) در سال ۲۰۰۶، دالال و تریگز با کوردلیا اشمید همکاری کردند تا آشکارسازهای HOG را برای مشکل تشخیص انسان در فیلم‌ها و ویدیوها به کار ببرند. آنها توصیفگرهای HOG را روی فریم‌های ویدیویی جداگانه با هیستوگرام‌های حرکتی داخلی تازه معرفی شده خود (IMH) روی جفت فریم‌های ویدیویی بعدی ترکیب کردند. این هیستوگرام‌های حرکتی داخلی از قدرهای گرادیان میدان‌های جریان نوری به دست آمده از دو فریم متوالی استفاده می‌کنند. سپس این بزرگی‌های گرادیان به همان شیوه‌ای استفاده می‌شوند که از داده‌های تصویر استاتیک در رویکرد توصیفگر HOG تولید می‌شوند. هنگام آزمایش بر روی دو مجموعه داده بزرگ که از چندین فیلم گرفته شده بودند، روش ترکیبی HOG-IMH یک نرخ اشتباه تقریباً ۰٫۱ را در یک فیلم به دست آورد. $10^{-4}$ نرخ مثبت کاذب^[۹]

جستارهای وابسته[ویرایش]

منابع[ویرایش]

↑ "Method of and apparatus for pattern recognition".
↑ "Orientation Histograms for Hand Gesture Recognition".
↑ "Histograms of Oriented Gradients for Human Detection" (PDF). p. 2.
↑ "Histograms of Oriented Gradients for Human Detection" (PDF). p. 4.
↑ "Histograms of Oriented Gradients for Human Detection" (PDF). p. 6.
↑ "Histograms of Oriented Gradients for Human Detection" (PDF). p. 6.
↑ "Histograms of Oriented Gradients for Human Detection" (PDF). p. 1.
↑ "Object Detection using Histograms of Oriented Gradients" (PDF). Archived from the original (PDF) on 2013-12-05. Retrieved 2007-12-10.
↑ "Human Detection Using Oriented Histograms of Flow and Appearance" (PDF). Archived from the original (PDF) on 2008-09-05. Retrieved 2007-12-10. (original document no longer available; similar paper بایگانی‌شده در ۲۸ ژانویه ۲۰۲۳ توسط Wayback Machine)

پیوند به بیرون[ویرایش]

http://www.mathworks.com/matlabcentral/fileexchange/33863 پیاده‌سازی برای Matlab (فایل mex)
https://www.cs.cmu.edu/~yke/pcasift/ - کد برای تشخیص اشیاء PCA-SIFT
http://lear.inrialpes.fr/software/ - ابزار نرم‌افزاری برای تشخیص اشیاء HOG (صفحه اصلی تیم تحقیقاتی)
https://web.archive.org/web/20100502032344/http://www.navneetdalal.com/software - نرم‌افزار Toolkit for HOG Object Detection (صفحه اصلی Navneet Dalal)
http://dlib.net/imaging.html#scan_fhog_pyramid - نرم‌افزار C++ و Python Toolkit برای تشخیص اشیاء HOG
http://pascal.inrialpes.fr/data/human/ بایگانی‌شده در ۲۰۱۰-۰۵-۰۵ توسط Wayback Machine راه برگشت - مجموعه داده‌های تصویر انسانی INRIA
http://cbcl.mit.edu/software-datasets/PedestrianData.html - مجموعه داده تصویر عابر پیاده MIT

[1] "Method of and apparatus for pattern recognition".

[2] "Orientation Histograms for Hand Gesture Recognition".

[3] "Histograms of Oriented Gradients for Human Detection" (PDF). p. 2.

[4] "Histograms of Oriented Gradients for Human Detection" (PDF). p. 4.

[5] "Histograms of Oriented Gradients for Human Detection" (PDF). p. 6.

[6] "Histograms of Oriented Gradients for Human Detection" (PDF). p. 6.

[7] "Histograms of Oriented Gradients for Human Detection" (PDF). p. 1.

[8] "Object Detection using Histograms of Oriented Gradients" (PDF). Archived from the original (PDF) on 2013-12-05. Retrieved 2007-12-10.

[9] "Human Detection Using Oriented Histograms of Flow and Appearance" (PDF). Archived from the original (PDF) on 2008-09-05. Retrieved 2007-12-10. (original document no longer available; similar paper بایگانی‌شده در ۲۸ ژانویه ۲۰۲۳ توسط Wayback Machine)

[۱]

[۲]

[۳]

[۴]

[۵]

[۶]

[۷]

[۸]

[۹]