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

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

[[پرونده:Res6.jpg|700px|بندانگشتی|وسط|جایگزین=تشخیص چهره به کمک الگوریتم هیستوگرام گرادیان‌های جهت‌دار|تشخیص چهره به کمک الگوریتم هیستوگرام گرادیان‌های جهت‌دار]]

[[Robert K. McConnell|رابرت کی مک کانل]] از [[Wayland Research Inc.|شرکت تحقیقاتی Wayland]] اولین بار مفاهیم پشت HOG را بدون استفاده از اصطلاح HOG در یک درخواست ثبت اختراع در سال ۱۹۸۶ توصیف کرد.<ref>{{Cite web|url=http://www.google.co.uk/patents/US4567610|title=Method of and apparatus for pattern recognition}}</ref> در سال ۱۹۹۴ این مفاهیم توسط آزمایشگاه تحقیقاتی [[میتسوبیشی الکتریک]] مورد استفاده قرار گرفت.<ref>{{Cite web|url=http://www.merl.com/publications/TR94-03|title=Orientation Histograms for Hand Gesture Recognition}}</ref> با این حال، زمانی که [[Navneet Dalal|ناونیت دالال]] و [[Bill Triggs|بیل تریگز]]، محققان مؤسسه ملی تحقیقات علوم کامپیوتر و اتوماسیون فرانسه (INRIA)، کار تکمیلی خود را در مورد توصیفگرهای HOG در [[کنفرانس بینایی رایانه‌ای و بازشناخت الگو|کنفرانس بینایی کامپیوتری و تشخیص الگو]] (CVPR) ارائه کردند، استفاده از آن در سال ۲۰۰۵ گسترده شد). در این کار آنها بر روی تشخیص عابر پیاده در تصاویر ایستا تمرکز کردند، اگرچه از آن زمان آزمایش‌های خود را گسترش دادند تا تشخیص انسان در فیلم‌ها و همچنین انواع حیوانات و وسایل نقلیه رایج در تصاویر ثابت را شامل شود.

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

توصیفگر HOG چند مزیت کلیدی نسبت به سایر توصیفگرها دارد. از آنجایی که بر روی سلول‌های محلی کار می‌کند، به جز برای شی گرایی، نسبت به تبدیل‌های هندسی و فتومتریک ثابت است. چنین تغییراتی فقط در مناطق فضایی بزرگتر ظاهر می‌شود. علاوه بر این، همان‌طور که دالال و تریگز کشف کردند، نمونه‌برداری فضایی درشت، نمونه‌گیری جهت‌گیری دقیق و نرمال‌سازی فتومتریک محلی قوی اجازه می‌دهد تا زمانی که عابران پیاده وضعیت تقریباً عمودی خود را حفظ کنند، حرکات بدن فردی نادیده گرفته شود؛ بنابراین توصیفگر HOG به ویژه برای تشخیص انسان در تصاویر مناسب است.<ref>{{Cite web|url=http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf|title=Histograms of Oriented Gradients for Human Detection|page=2}}</ref>

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

: <math>[-1, 0, 1]\text{ and }[-1, 0, 1]^\top.\,</math>

دالال و تریگز ماسک‌های پیچیده‌تر دیگری مانند ماسک سوبل ۳×۳ یا ماسک‌های مورب را آزمایش کردند، اما این ماسک‌ها عموماً در تشخیص انسان در تصاویر ضعیف‌تر عمل کردند. آنها همچنین قبل از استفاده از ماسک مشتق، محو کردن گاوسی را آزمایش کردند، اما به‌طور مشابه دریافتند که حذف هر گونه محوی در عمل بهتر کار می‌کند.<ref>{{Cite web|url=http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf|title=Histograms of Oriented Gradients for Human Detection|page=4}}</ref>

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

=== بلوک‌های توصیفگر ===
برای در نظر گرفتن تغییرات در روشنایی و کنتراست، نقاط قوت گرادیان باید به صورت محلی نرمال شوند، که مستلزم گروه‌بندی سلول‌ها با هم در بلوک‌های بزرگتر و به هم متصل مکانی است. سپس توصیفگر 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 حاوی سلول‌هایی با کانال‌های جهت‌گیری متعدد هستند، در حالی که بافت‌های شکل تنها از یک تعداد وجود لبه در فرمول‌بندی خود استفاده می‌کنند.<ref>{{Cite web|url=http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf|title=Histograms of Oriented Gradients for Human Detection|page=6}}</ref>

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

: L2-norm: <math>f = {v \over \sqrt{\|v\|^2_2+e^2}}</math>

: L1-norm: <math>f = {v \over (\|v\|_1+e)}</math>

: L1-sqrt: <math>f = \sqrt{v \over (\|v\|_1+e)}</math>

در آزمایش‌های خود، دالال و تریگز دریافتند که طرح‌های L2-norm و L1-sqrt عملکرد مشابهی را ارائه می‌دهند، در حالی که L1-norm عملکرد کمی کمتر قابل اعتماد را ارائه می‌دهد. با این حال، هر سه روش بهبود بسیار قابل توجهی را نسبت به داده‌های غیرعادی نشان دادند.<ref>{{Cite web|url=http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf|title=Histograms of Oriented Gradients for Human Detection|page=6}}</ref>

=== تشخیص اشیا ===
توصیفگرهای HOG می‌توانند به عنوان ویژگی برای الگوریتم [[یادگیری ماشینی|یادگیری ماشین]] برای تشخیص شی مورد استفاده قرار گیرند. دالال و تریگز از توصیفگرهای HOG به عنوان ویژگی در [[ماشین بردار پشتیبانی|ماشین بردار]] پشتیبان (SVM) استفاده کردند.<ref>{{Cite web|url=http://lear.inrialpes.fr/people/triggs/pubs/Dalal-cvpr05.pdf|title=Histograms of Oriented Gradients for Human Detection|page=1}}</ref> با این حال، توصیفگرهای HOG به یک الگوریتم یادگیری ماشین خاص گره‌خورده نیستند.

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

== پیشرفتهای بعدی ==
به‌عنوان بخشی از کارگاه کلاس‌های اشیاء تصویری پاسکال در سال ۲۰۰۶، دالال و تریگز نتایجی را در مورد اعمال هیستوگرام توصیفگرهای گرادیان جهت‌یافته برای اشیاء تصویری غیر از انسان، مانند اتومبیل، اتوبوس و دوچرخه، و همچنین حیوانات معمولی مانند سگ، گربه، ارائه کردند. و گاوها آنها با نتایج خود پارامترهای بهینه برای فرمولاسیون بلوک و نرمال‌سازی را در هر مورد گنجاندند. تصویر مرجع زیر برخی از نمونه‌های تشخیص آنها را برای موتور سیکلت نشان می‌دهد.<ref>{{Cite web|url=http://www.pascal-network.org/challenges/VOC/voc2006/slides/dalal.pdf|title=Object Detection using Histograms of Oriented Gradients|accessdate=2007-12-10|archiveurl=https://web.archive.org/web/20131205153059/http://pascallin.ecs.soton.ac.uk/challenges/VOC/voc2006/slides/dalal.pdf|archivedate=2013-12-05}}</ref>

به عنوان بخشی از [[کنفرانس اروپایی بینایی رایانه‌ای|کنفرانس اروپایی بینایی کامپیوتری]] (ECCV) در سال ۲۰۰۶، دالال و تریگز با کوردلیا اشمید همکاری کردند تا آشکارسازهای HOG را برای مشکل تشخیص انسان در فیلم‌ها و ویدیوها به کار ببرند. آنها توصیفگرهای HOG را روی فریم‌های ویدیویی جداگانه با هیستوگرام‌های حرکتی داخلی تازه معرفی شده خود (IMH) روی جفت فریم‌های ویدیویی بعدی ترکیب کردند. این هیستوگرام‌های حرکتی داخلی از قدرهای گرادیان میدان‌های [[شار نوری (بصری)|جریان نوری]] به دست آمده از دو فریم متوالی استفاده می‌کنند. سپس این بزرگی‌های گرادیان به همان شیوه‌ای استفاده می‌شوند که از داده‌های تصویر استاتیک در رویکرد توصیفگر HOG تولید می‌شوند. هنگام آزمایش بر روی دو مجموعه داده بزرگ که از چندین فیلم گرفته شده بودند، روش ترکیبی HOG-IMH یک نرخ اشتباه تقریباً ۰٫۱ را در یک فیلم به دست آورد. <math>10^{-4}</math> نرخ مثبت کاذب<ref>{{Cite web|url=http://www.acemedia.org/aceMedia/files/document/wp7/2006/eccv06-inria.pdf|title=Human Detection Using Oriented Histograms of Flow and Appearance|accessdate=2007-12-10|archiveurl=https://web.archive.org/web/20080905123659/http://www.acemedia.org/aceMedia/files/document/wp7/2006/eccv06-inria.pdf|archivedate=2008-09-05}} (original document no longer available; [http://lear.inrialpes.fr/pubs/2006/DTS06/eccv2006.pdf similar paper] {{Webarchive|url=https://web.archive.org/web/20230128214153/http://lear.inrialpes.fr/pubs/2006/DTS06/eccv2006.pdf |date=۲۸ ژانویه ۲۰۲۳ }})</ref>

== جستارهای وابسته ==
* [[تشخیص گوشه]]
* [[استخراج ویژگی]]
* [[تبدیل ویژگی مقیاس‌نابسته|تبدیل ویژگی تغییرناپذیر مقیاس]]

== منابع ==
{{پانویس|۲}}

== پیوند به بیرون ==
* 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/ {{Webarchive|url=https://web.archive.org/web/20100505083112/http://pascal.inrialpes.fr/data/human/|date=۲۰۱۰-۰۵-۰۵}} راه برگشت - مجموعه داده‌های تصویر انسانی INRIA
* http://cbcl.mit.edu/software-datasets/PedestrianData.html - مجموعه داده تصویر عابر پیاده MIT
[[رده:کشف ویژگی‌ها]]