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

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

رابرت کی مک کانل از شرکت تحقیقاتی Wayland اولین بار مفاهیم پشت HOG را بدون استفاده از اصطلاح HOG در یک درخواست ثبت اختراع در سال 1986 توصیف کرد. ^[۱] در سال 1994 این مفاهیم توسط آزمایشگاه تحقیقاتی میتسوبیشی الکتریک مورد استفاده قرار گرفت. ^[۲] با این حال، زمانی که ناونیت دالال و بیل تریگز ، محققان موسسه ملی تحقیقات علوم کامپیوتر و اتوماسیون فرانسه ( INRIA )، کار تکمیلی خود را در مورد توصیفگرهای HOG در کنفرانس بینایی کامپیوتری و تشخیص الگو (CVPR) ارائه کردند، استفاده از آن در سال 2005 گسترده شد.). در این کار آنها بر روی تشخیص عابر پیاده در تصاویر ایستا تمرکز کردند، اگرچه از آن زمان آزمایش های خود را گسترش دادند تا تشخیص انسان در فیلم ها و همچنین انواع حیوانات و وسایل نقلیه رایج در تصاویر ثابت را شامل شود.

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

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

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

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

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

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

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

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

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

مرحله دوم محاسبه، ایجاد هیستوگرام سلولی است. هر پیکسل درون سلول بر اساس مقادیر یافت شده در محاسبه گرادیان، یک رای وزنی برای یک سطل هیستوگرام مبتنی بر جهت گیری می دهد. سلول‌ها می توانند مستطیل یا شعاعی شکل باشند و کانال های هیستوگرام به طور مساوی بین 0 تا 180 درجه یا 0 تا 360 درجه پخش می شوند، بسته به اینکه گرادیان "بدون جهت" یا "جهت‌دار" باشد. دالال و تریگز دریافتند که گرادیان‌های بدون علامت مورد استفاده در ارتباط با 9 کانال هیستوگرام در آزمایش‌های تشخیص انسان خود بهترین عملکرد را داشتند، در حالی که اشاره کردند که گرادیان‌های جهت‌دار منجر به پیشرفت‌های قابل‌توجهی در تشخیص برخی کلاس‌های دیگر شی، مانند اتومبیل یا موتور سیکلت می‌شوند.

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

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

بلوک‌های دایره‌ای HOG (C-HOG) را می‌توان در دو نوع یافت: آنهایی که دارای یک سلول منفرد و مرکزی هستند و آنهایی که دارای یک سلول مرکزی تقسیم زاویه‌ای هستند. علاوه بر این، این بلوک های C-HOG را می توان با چهار پارامتر توصیف کرد: تعداد سطل های زاویه ای و شعاعی، شعاع سطل مرکزی و ضریب انبساط برای شعاع سطل های شعاعی اضافی. دالال و تریگز دریافتند که دو نوع اصلی عملکرد یکسانی ارائه می دهند و دو سطل شعاعی با چهار سطل زاویه ای، شعاع مرکزی 4 پیکسل و ضریب گسترش 2 بهترین عملکرد را در آزمایش خود ارائه می دهند (برای دستیابی به عملکرد خوب، بالاخره از این پیکربندی استفاده کنید). همچنین، وزن دهی گاوسی هنگام استفاده همراه با بلوک های 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 و توصیف‌گرهای زمینه شکل مقایسه کردند. موجک های هار تعمیم یافته، موجک های هار گرا هستند و در سال 2001 توسط موهان، پاپاجئورگیو و پوجیو در آزمایش های تشخیص اشیاء خود استفاده شدند. توصیفگرهای PCA-SIFT مشابه توصیفگرهای SIFT هستند، اما در این که تجزیه و تحلیل مؤلفه اصلی برای وصله‌های گرادیان نرمال شده اعمال می‌شود، متفاوت هستند. توصیفگرهای PCA-SIFT برای اولین بار در سال 2004 توسط Ke و Sukthankar مورد استفاده قرار گرفت و ادعا شد که بهتر از توصیفگرهای SIFT معمولی عمل می کند. در نهایت، زمینه‌های شکل از سطل‌های دایره‌ای استفاده می‌کنند، مشابه مواردی که در بلوک‌های C-HOG استفاده می‌شوند، اما فقط آرا را بر اساس حضور لبه جدول‌بندی می‌کنند، و هیچ حساسیتی نسبت به جهت‌ ندارند. زمینه های شکل در ابتدا در سال 2001 توسط Belongie، Malik و Puzicha استفاده شد.

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

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

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