چارچوب تشخیص اشیا ویولا-جونز

چارچوب تشخیص اشیاء Viola-Jones یک چارچوب تشخیص اشیاء در تصویر مبتنی بر یادگیری ماشین با ارائه نرخ تشخیص بلادرنگ است که در سال ۲۰۰۱ توسط پاول ویولا و مایکل جونز ارائه شد. اگر چه این چارچوب می‌تواند برای تشخیص انواع اشیاء آموزش داده شود، در ابتدا به منظور تشخیص چهره توسعه داده شده بود و اولین الگوریتم تشخیص چهرهٔ بلادرنگ به شمار می‌رود.  

مقاله‌ی اصلی سه نوآوری کلیدی ارائه می‌کرد. اولین نوآوری استفاده از نمایشی برای تصویر به نام تصویر انتگرالی بود که به کمک آن امکان محاسبه‌ بسیار سریع ویژگی‌های مورد نیاز برای تشخیص در زمان ثابت فراهم می‌گردید. نوآوری دوم توسعه‌ یک الگوریتم یادگیری ماشین مبتنی بر آدابوست به منظور انتخاب مجموعه‌ای کوچک اما کارا از میان مجموعه بزرگی از ویژگی‌های تصویری بود و نوآوری سوم ارائه‌ یک معماری آبشاری به منظور ترکیب بهینه‌ٔ مجموعه‌ای از الگوریتم‌های طبقه‌بند آماری بود که به موجب آن قسمت‌های پس زمینه‌ٔ تصویر با الگوریتمهای طبقه‌بندی سریع دور ریخته می‌شوند و الگوریتمهای پیچیده‌تر طبقه بندی روی قسمتهای مهمتر تصویر تمرکز می‌کنند. با وجود اینکه تا کنون الگوریتمهای بسیار زیادی به منظور تشخیص چهره توسعه داده شده‌اند می‌توان گفت از این میان الگوریتم ویولا جونز بیشترین تاثیر را بر دهه‌های پیش روی خود داشت و قادر بود با سرعت بسیار زیاد دقت مطلوبی در مکان‌یابی چهره ارائه دهد.

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

الگوریتم ویولا-جونز نیاز به نمای کامل صورت از جلو دارد. بنابراین برای تشخیص، کل چهره باید به سمت دوربین باشد و نباید به اطراف منحرف شود. در حالی که به نظر می‌رسد این محدودیت‌ها تا حدودی باعث کاهش کارایی الگوریتم می‌شوند در بسیاری از کاربردها این میزان کارایی قابل قبول است. از مزایای چارچوب ارائه شده این است که برای تشخیص چهره در مقیاس‌ مختلف می‌توان به جای مقیاس تصویر، مقیاس ویژگی‌های استفاده شده را عوض کرد و همچنین می‌توان این الگوریتم را برای تشخیص اشیاء دیگری همچون خودرو آموزش داد.  

این الگوریتم به میزان قابل قبولی Robust است به این معنا که حساسیت بالا (مثبت صحیح) و تشخیص بالا (منفی صحیح) دارد و همچنین پردازش آن به صورت بلادرنگ صورت می‌گیرد.  

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

اجزاء چارچوب 

الگوریتم ویولاجونز با پیروی از کار Papageorgiou و دیگران به جای استفاده از مقادیر تک تک پیکسل‌های تصویر اقدام به استخراج ویژگی‌های مستطیلی شبه‌ Haar می‌کند که با الهام از توابع پایه‌‌ٔ موجک هار شکل گرفته‌اند و قبلاً در حیطهٔ تشخیص اشیاء مبتنی بر تصویر مورد استفاده قرار گرفته‌ بودند اما ویژگی‌های مورد استفادهٔ ویولا و جونز معمولاً پیچیده تر هستند. شکل سمت چپ نشانگر چهار نوع مختلف از ویژگی‌های مورد استفاده در چارچوب است. ارزش هر ویژگی مشخص شده برابر با مجموع تمام مقادیر پیکسل‌های داخل مستطیل‌های روشن است که از مجموع تمام پیکسل‌های داخل مستطیل‌های تیره کاسته می‌شوند.  

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

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

ویژگی‌های شبه Haar 
ویژگی‌های شبه Haar عبارتند از نواحی روشن و تیره‌ٔ مستطیل شکلی که بر روی زیر پنجرهٔ ۲۴ در ۲۴ پیکسل مورد بررسی (نامزد احتمالی در برگیرندهٔ صورت) تعریف شده‌اند. ارزش هر ویژگی مشخص شده برابر با مجموع تمام مقادیر پیکسل‌های داخل مستطیل‌های روشن است که از مجموع تمام پیکسل‌های داخل مستطیل‌های تیره کاسته می‌شوند. سایر نقاط عکس که خارج از این مستطیل‌ها قرار دارند در محاسبه‌ٔ ویژگی در نظر گرفته نمی‌شوند. به این ترتیب برای هر پنجرهٔ ۲۴ در ۲۴ پیکسل متناظر با یک ویژگی یک عدد به عنوان ارزش این ویژگی محاسبه میشود. موضوعی که موفقیت این ویژگی‌های مستطیل شکل را تضمین می‌کند استفاده از ویژگی‌های کمابیش مشترک چهره‌های انسانی است. 

تمامی چهره‌های انسانی دارای ویژگی‌های کمابیش مشابهی هستند. این قواعد می‌تواند با استفاده از ویژگی‌های شبه Haar تطبیق داده شوند. به عنوان مثال چند ویژگی مشترک برای چهره‌های انسانی عبارتند از: 
 ناحیهٔ پل بینی از چشم‌ها روشن‌تر است.
ناحیهٔ فرورفتگی چشم‌ها تیره‌تر از گونه‌ها است. 

ترکیب خواص زیر ویژگی‌های مشترک صورت‌های انسانی را تشکیل می‌دهند: 
 محل و اندازهٔ: چشم‌ها، دهان، پل بینی
 ارزش: جهت گرادیانِ مقادیر پیکسل‌ها

ویژگی‌هایی که ویولا و جونز استفاده می‌کنند دارای نواحی مستطیل شکل تیره و روشنی هستند که با مساحت برابر به صورت افقی یا عمودی در کنار هم قرار دارند. این ویژگی‌ها بر سه دسته هستند (تصاویر سمت راست):  

 ویژگی‌های دو-مستطیلی که شامل دو مستطیل با مساحت برابر در کنار یکدیگر به صورت افقی یا عمودی هستند.
 ویژگی‌های سه-مستطیلی که مقادیر دو مستطیل کناری را از مستطیل وسط کم می‌کند.
 ویژگی‌های چهار-مستطیلی که به صورت قطری در کنار یکدیگر قرار گرفته‌اند.

این سه نوع ویژگی در مکان‌های مختلف زیرپنجره‌ٔ ۲۴ در ۲۴ پیکسلی تعریف می‌شوند و تعداد آنها از ۱۸۰ هزار عدد بیشتر است. بنابراین نه تنها نیاز به روشی سریع برای ارزیابی مقادیر هر یک از این ویژگی‌ها احساس می‌شود، بلکه می‌بایست زیر مجموعه‌ٔ موثرتری از این ویژگی‌ها انتخاب شود که در ارزیابی تصویر نهایی مورد استفاده قرار گیرد.

تصویر انتگرالی 
همان طور که اشاره شد تعداد ویژگی‌های مورد استفاده در چارچوب ویولا-جونز متجاوز از ۱۸۰ هزار فیلتر است. به همین دلیل بدون استفاده از روشی سریع به منظور ارزیابی این ویژگی‌ها امکان آموزش الگوریتمهای طبقه بندی به منظور انتخاب زیرمجموعه‌ای موثر از این ویژگی‌ها و همچنین امکان ارزیابی بلادرنگ آنها روی زیر پنجره‌های نهایی تصویر وجود نخواهد داشت. همان طور که اشاره شد مقدار هر یک از این ویژگی‌ها از تفاضل مجموع مقادیر پیسکل‌های داخل نواحی تیره از مجموع مقدایر پیکسل‌های داخل نواحی روشن بدست می‌آید. 

ارزش ویژگی = Σ (پیکسل‌های در ناحیه سفید) - Σ (پیکسل در ناحیه سیاه) 

ویولا و جونز نشان دادند که چگونه می‌توان با استفادهٔ کارا از تصویر انتگرالی ویژگی‌های مستطیلی را در زمانی ثابت ارزیابی کرد، این روش مزیت سرعت ارزیابی قابل توجهی را نسبت به سایر ویژگی‌های پیچیدهٔ جایگزین فراهم آورد و استفاده از تصویر انتگرالی را در بینایی رایانه‌ای تثبیت کرد چرا که محاسبه‌ٔ تصویر انتگرالی تنها با یک بار عبور از روی تصویر اصلی قابل انجام است. 

در یک تصویر انتگرالی مقدار هر پیکسل برابر با مجموع تمام پیکسلهای بالا و سمت راست این پیکسل روی تصویر اصلی به علاوه‌ٔ مقدار خود پیکسل روی تصویر اصلی است: 

 

که در آن  تصویر انتگرالی و  تصویر اصلی است. با استفاده از دو رابطه‌ٔ بازگشتی زیر می‌توان تصویر انتگرالی را تنها با یک بار عبور از روی تصویر اصلی ساخت: 

 

که در آن  مقدار تجمعی سطری و  و  است. 

همان طور که در تصویر چپ نمایش داده شده است، با استفاده از تصویر انتگرالی می‌توان مجموع مقادیر داخل هر ناحیه‌‌ٔ مستطیلی روی تصویر اصلی را تنها با مقادیر چهار پیکسل روی تصویر انتگرالی محاسبه کرد. از آنجا که نواحی مستطیلی هر یک از ویژگی‌های شبه‌ Haar همیشه در مجاورت یکدیگر قرار دارند، مثلا برای محاسبهٔ هر ویژگی دو-مستطیلی تنها به مقادیر شش پیکسل، برای محاسبهٔ هر ویژگی سه-مستطیلی تنها به مقادیر هشت پیکسل و برای محاسبهٔ هر ویژگی چهار-مستطیلی تنها به مقادیر نه پیکسل از تصویر انتگرالی نیاز است.

الگوریتم یادگیری 
سرعتی که ویژگی‌ها ممکن است مورد ارزیابی قرار گرفته شوند به تعداد کافی آن‌ها را جبران نمی‌کند . با این حال، به عنوان مثال، در یک زیر پنجره 24x24 پیکسل استاندارد، مجموعه ای از ویژگی‌های محتمل به بزرگی   وجود دارد و برای بررسی همه آن‌ها در هنگام تست یک تصویر گران تمام خواهد شد. بنابراین، چارچوب تشخیص ابعاد الگوریتم یادگیری AdaBoost را به کار می‌گیرد تا هم بهترین ویژگی‌ها را انتخاب کند و هم طبقه‌بندی‌هایی را یاد دهد که از آن‌ها استفاده می‌شود. این الگوریتم طبقه‌بندی "قوی" را به عنوان ترکیبی خطی از طبقه‌بندی‌های ساده "وزن ضعیف" ایجاد می‌کند. 

 

هر طبقه‌بندی ضعیف یک تابع آستانه بر اساس ویژگی است . 

 

مقدار آستانه و قطب  در رشته مشخص شده‌اند ،

به همراه ضرایب .

در اینجا یک نسخه ساده الگوریتم یادگیری گزارش شده‌است: 

ورودی: مجموعه ای از  دنباله عکس‌های مثبت و منفی با برچسب‌های خود  . اگر تصویر  یک چهره باشد ، اگر نه  . 

مقدار دهی اولیه : تعیین یک وزن  برای هر تصویر i.

برای هر ویژگی با  وزن‌ها را طوری تقسیم کنید که جمع آن‌ها یک شود. 

ویژگی را برای هر تصویر در مجموعه دنباله اعمال کنید، سپس آستانه بهینه و قطبش  پیدا کنید که خطای طبقه‌بندی وزن دار را به حداقل می‌رساند. یعنی …

جایی که

وزن هر را به که با معکوس نرخ خطا متناسب است . در این روش بهترین مرتب‌کننده‌ها بیشتر در نظر گرفته می‌شوند.

وزن‌های تکرار بعدی، برای مثال . ، برای تصاویر i که به درستی طبقه‌بندی شده‌اند، کاهش می‌یابد.

طبقه‌بندی‌کننده نهایی را تنظیم کنید.

معماری آبشار 
 به‌طور متوسط فقط 0.01٪ از تمام زیر پنجره‌ها مثبت هستند (چهره ها) 
 زمان محاسبات یکسان بر تمام زیر پنجره‌ها صرف می‌شود 
 بیشترین زمان را صرفاً در مورد زیر پنجره‌های بالقوه مثبت می‌گذرانند. 
 یک طبقه‌بندی ساده 2 ویژگی می‌تواند نرخ تشخیص تقریباً 100٪ را با نرخ FP 50٪ به دست آورد. 
 این طبقه‌بندی می‌تواند به عنوان اولین لایه از یک سری برای فیلتر کردن بیشتر پنجره‌های منفی عمل کند 
 دومین لایه با 10 ویژگی می‌تواند پنجره‌های "سخت تر" منفی را که از لایه اول باقی مانده است، برطرف کند و ... 
 یک آبشار از طبقه‌بندی‌های پیچیده به تدریج پیچیده تر می‌شود تا به نرخ‌های تشخیص بهتری دست یابد. ارزیابی طبقه‌بندی‌های قوی تولید شده توسط فرایند یادگیری می‌تواند به سرعت انجام شود، اما به اندازه کافی سریع نیست که در لحظه اجرا شود. به همین دلیل، طبقه‌بندی‌های قوی به منظور پیچیدگی در یک آبشار مرتب می‌شوند، جایی که هر یک از طبقه‌بندی‌های پی در پی فقط برای نمونه‌های انتخاب شده که از طریق طبقه‌بندی‌های پیشین عبور می‌کنند، بررسی می‌شود. اگر در هر مرحله در آبشار، یک طبقه‌بندی‌کننده زیر پنجره تحت بازرسی را رد کند، پردازش بیشتر صورت نمی‌گیرد و همچنان به جستجوی پنجره بعدی ادامه می‌دهد. آبشار به شکل یک درخت انحطاط یافته‌است. در مورد چهره، اولین طبقه‌بندی‌کننده در آبشار - به نام اپراتور مراقبت - تنها از دو ویژگی برای دستیابی به نرخ منفی کاذب تقریباً 0٪ و نرخ مثبت کاذب 40٪ استفاده می‌کند.  تأثیر این طبقه‌بندی‌کننده تنها کاهش تقریبی تعداد دفعاتی است که کل آبشار مورد ارزیابی قرار می‌گیرد. 

در آبشار، هر مرحله شامل یک طبقه‌بندی‌کننده قوی است. بنابراین تمام ویژگی‌ها در چند مرحله گروه‌بندیمی‌شوند که در آن هر مرحله دارای تعداد خاصی از ویژگی‌ها است. 

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

یک چارچوب ساده برای آموزش آبشار در زیر آورده شده‌است: 
 f = حداکثر نرخ مثبت کاذب قابل قبول در هر لایه. 
 d = حداقل میزان تشخیص قابل قبول در هر لایه. 
 Ftarget = نرخ کلی مثبت کاذب را هدف قرار می‌دهد. 
 P = مجموعه ای از نمونه‌های مثبت 
 N = مجموعه ای از نمونه‌های منفی. 

 F(0) = 1.0; D(0) = 1.0; i = 0

 while F(i)> Ftarget
     increase i
     n(i) = 0; F(i)= F(i-1)

     while F(i)> f × F(i-1)
       increase n(i)
       use P and N to train a classifier with n(I) features using AdaBoost
       Evaluate current cascaded classifier on validation set to determine F(i) and D(i)
       decrease threshold for the ith classifier 
         until the current cascaded classifier has a detection rate of at least d × D(i-1) (this also affects F(i))
       N = ∅
       if F(i)> Ftarget then 
         evaluate the current cascaded detector on the set of non-face images 
         and put any false detections into the set N.
معماری آبشاری مفهومی جالب برای عملکرد طبقه بنده‌ای فردی دارد. از آنجا که فعال‌سازی هر طبقه‌بندی‌کننده به‌طور کامل به رفتار سلف خود وابسته است، نرخ کاذب مثبت برای یک آبشار کلی عبارت است از: 

به‌طور مشابه، میزان تشخیص برابر است با: 

بنابراین برای مطابقت با نرخ‌های مثبت کاذب که معمولاً توسط ردیاب‌های دیگر بدست می‌آیند، هر طبقه‌بندی‌کننده می‌تواند با داشتن عملکرد ضعیف نامناسب دور شود. برای مثال برای یک آبشار ۳۲ مرحله‌ای برایدستیابی به نرخ مثبت کاذب ۱۰ - ۶، هر طبقه‌بندی‌کننده تنها به نرخ مثبت کاذب حدود ۶۵ % دست می‌یابند. در زمان مشابه، در عین حال، هر طبقه‌بندی‌کننده باید به‌طور استثنایی قادر به دستیابی به نرخ‌های تشخیص مناسب باشد. برای مثال، برای دستیابی به نرخ تشخیص حدود ۹۰ %، هر طبقه‌بندی‌کننده درآبشاری ذکر شده نیاز به دستیابی به نرخ تشخیص تقریباً ۹۹.۷ % دارد. [ ۷ ]

استفاده از Viola-Jones برای ردیابی شیء 
در فیلم برداری از اشیا متحرک، لازم است که فرد تشخیص اشیا را برای هر فریم اعمال کند. در عوض می‌توان از الگوریتم‌های ردیابی مانند الگوریتم klt برای تشخیص ویژگی‌های برجسته درون جعبه bounding وپی‌گیری حرکت آن‌ها بین فریم‌ها استفاده کرد. این کار نه تنها سرعت ردیابی را با حذف نیاز به ردیابی اشیا درهر فریم بهبود می‌بخشد، بلکه مقاومت را نیز به خوبی بهبود می‌بخشد، چون ویژگی‌های برجسته انعطاف‌پذیری یبیشتری نسبت به چارچوب تشخیص ویولا جونز [Viola-Jones] برای چرخش و تغییرات فوتومتریک دارند. [ ۸ ]

منابع

پیوند به بیرون 
 اسلایدها ارائه چارچوب 
 اطلاعات مربوط به توابع پایه هار 
 Extension از چارچوب Viola-Jones با استفاده از ویژگی SURF 
 IMMI - Rapidminer Image Mining Extension - ابزار منبع باز برای استخراج عکس 
 تشخیص چهره واقعی در زمان واقعی  
 یک الگوریتم بهبود یافته در detector شی Viola-Jones 
 نقل قول الگوریتم Viola-Jones در Google Scholar 
  - توضیح Adaboost از ppt توسط چینگ چن، آزمایشگاه Discovery، دانشگاه اتاوا و سخنرانی ویدئویی توسط رامسری گوتام.

پیاده سازی 
 اجرای الگوریتم تشخیص چهره Viola-Jones توسط Ole Helvig Jensen 
 MATLAB: ،  
 OpenCV: اجرا به عنوان cvHaarDetectObjects() . 
 تشخیص آبشاری هار در OpenCV 
 آموزش مرتب سازی آبشاری در OpenCV

بینایی رایانه‌ای
تشخیص حرکت
صفحات با ترجمه بازبینی‌نشده
علوم رایانه
مقاله‌های با کد مثال