چارچوب تشخیص اشیا ویولا-جونز
چارچوب تشخیص اشیاء Viola-Jones یک چارچوب تشخیص اشیاء در تصویر مبتنی بر یادگیری ماشین با ارائه نرخ تشخیص بلادرنگ است که در سال ۲۰۰۱ توسط پاول ویولا و مایکل جونز ارائه شد. اگر چه این چارچوب می‌تواند برای تشخیص انواع اشیاء آموزش داده شود، در ابتدا به منظور تشخیص چهره توسعه داده شده بود و اولین الگوریتم تشخیص چهرهٔ بلادرنگ به شمار می‌رود.
مقاله‌ی اصلی سه نوآوری کلیدی ارائه می‌کرد. اولین نوآوری استفاده از نمایشی برای تصویر به نام تصویر انتگرالی بود که به کمک آن امکان محاسبه‌ بسیار سریع ویژگی‌های مورد نیاز برای تشخیص در زمان ثابت فراهم می‌گردید. نوآوری دوم توسعه‌ یک الگوریتم یادگیری ماشین مبتنی بر آدابوست به منظور انتخاب مجموعه‌ای کوچک اما کارا از میان مجموعه بزرگی از ویژگی‌های تصویری بود و نوآوری سوم ارائه‌ یک معماری آبشاری به منظور ترکیب بهینه‌ٔ مجموعه‌ای از الگوریتم‌های طبقه‌بند آماری بود که به موجب آن قسمت‌های پس زمینه‌ٔ تصویر با الگوریتمهای طبقه‌بندی سریع دور ریخته می‌شوند و الگوریتمهای پیچیده‌تر طبقه بندی روی قسمتهای مهمتر تصویر تمرکز می‌کنند. با وجود اینکه تا کنون الگوریتمهای بسیار زیادی به منظور تشخیص چهره توسعه داده شده‌اند می‌توان گفت از این میان الگوریتم ویولا جونز بیشترین تاثیر را بر دهه‌های پیش روی خود داشت و قادر بود با سرعت بسیار زیاد دقت مطلوبی در مکان‌یابی چهره ارائه دهد.
مسئله تشخیص چهره یکی از مسائل شناخته‌شده‌ بینایی رایانه‌ای است. مسئله‌ مورد نظر چهره انسان را در تصاویر دیجیتال مکان‌یابی می‌کند. فرآیند تشخیص چهره به دو سوال پاسخ می‌دهد: اول اینکه آیا چهره‌ای در یک تصویر و یا دنباله‌ای از تصاویر ویدئویی وجود دارد؟ دوم اینکه این چهره در کجای تصویر واقع شده است؟ اغلب انسان‌ها می‌توانند این کار را به آسانی انجام دهند، اما یک کامپیوتر نیاز به دستورالعمل‌های دقیق و پیچیده‌ای دارد. پیچیدگی مسئله با تفاوت مقیاس تصویر، زاویه‌ تصویربرداری، شرایط نوری متفاوت و پوشیده بودن قسمتی از چهره چند برابر می‌شود. با وجود اینکه تا کنون الگوریتمهای بسیار زیادی به منظور تشخیص چهره توسعه داده شده‌اند می‌توان گفت از این میان الگوریتم ویولا جونز بیشترین تاثیر را بر دهه‌های پیش روی خود داشت و قادر بود و اولین الگوریتم بلادرنگ مکان یابی چهره با دقتی مطلوب به شمار می‌رود.
الگوریتم ویولا-جونز نیاز به نمای کامل صورت از جلو دارد. بنابراین برای تشخیص، کل چهره باید به سمت دوربین باشد و نباید به اطراف منحرف شود. در حالی که به نظر می‌رسد این محدودیت‌ها تا حدودی باعث کاهش کارایی الگوریتم می‌شوند در بسیاری از کاربردها این میزان کارایی قابل قبول است. از مزایای چارچوب ارائه شده این است که برای تشخیص چهره در مقیاس‌ مختلف می‌توان به جای مقیاس تصویر، مقیاس ویژگی‌های استفاده شده را عوض کرد و همچنین می‌توان این الگوریتم را برای تشخیص اشیاء دیگری همچون خودرو آموزش داد.
این الگوریتم به میزان قابل قبولی Robust است به این معنا که حساسیت بالا (مثبت صحیح) و تشخیص بالا (منفی صحیح) دارد و همچنین پردازش آن به صورت بلادرنگ صورت می‌گیرد.
از نقاط ضعف این الگوریتم می‌توان به حساسیت به شرایط نوری و اندازه‌ٔ چهره در تصویر اشاره کرد. این الگوریتم همچنین در تشخیص چهره‌های چرخیده دچار مشکل می‌شود و ممکن است یک چهره را به عنوان چند چهره در همپوشانی زیرپنجره‌های مورد جستجو پیدا کند. علی‌رغم همه‌ٔ این موارد و توسعه‌ٔ روشهای جدید تشخیص چهره با استفاده از یادگیری عمیق که در تشخیص چهره از همه‌‌ٔ نژادها، در تمامی زوایا بدون حساسیت به مقیاس تصویر و شرایط نوری از کارایی بسیار بالایی برخوردار هستند، نوآوری‌هایی که در این چارچوب ارائه شد امروزه هنوز هم در سایر مسائل بینایی رایانه‌ای به وفور مورد استفاده قرار می‌گیرد.
الگوریتم ویولاجونز با پیروی از کار Papageorgiou و دیگران به جای استفاده از مقادیر تک تک پیکسل‌های تصویر اقدام به استخراج ویژگی‌های مستطیلی شبه‌ Haar می‌کند که با الهام از توابع پایه‌‌ٔ موجک هار شکل گرفته‌اند و قبلاً در حیطهٔ تشخیص اشیاء مبتنی بر تصویر مورد استفاده قرار گرفته‌ بودند اما ویژگی‌های مورد استفادهٔ ویولا و جونز معمولاً پیچیده تر هستند. شکل سمت چپ نشانگر چهار نوع مختلف از ویژگی‌های مورد استفاده در چارچوب است. ارزش هر ویژگی مشخص شده برابر با مجموع تمام مقادیر پیکسل‌های داخل مستطیل‌های روشن است که از مجموع تمام پیکسل‌های داخل مستطیل‌های تیره کاسته می‌شوند.
ویژگی‌های مستطیلی از این نوع در مقایسه با گزینه‌هایی مانند فیلترهای قابل هدایت که در تحلیل بافت و فشرده‌سازی تصویر استفاده می‌شوند بسیار ابتدایی به شمار می‌روند. اگرچه این ویژگی‌ها به لبه‌های عمودی و افقی و سایر ساختارهای ساده‌ٔ تصویری حساس هستند، با این وجود این حساسیت به هیچ عنوان انعطاف پذیر نیست. بر خلاف فیلترهای قابل هدایت تنها جهتی که می‌توان برای ویژگی‌های شبه Haar در نظر گرفت افقی، عمودی و قطری است اما تعداد بسیار زیاد این ویژگی‌ها توصیف قابل قبولی از تصویر ارائه می‌کند و استفاده از آن‌ها و ارزیابی سریع آن‌ها با استفاده از تصویر انتگرالی این محدودیت انعطاف را به میزان قابل قبولی جبران می‌کند.
به منظور ارزیابی ویژگی‌های مستطیلی شبه ‌Haar در زمان ثابت از تصویر انتگرالی استفاده می‌شود. پس از ساخته شدن تصویر انتگرالی مقدار هر کدام از این ویژگی‌ها فارغ از مکان و اندازهٔ آنها در تصویر با جمع و تفریق حداکثر نه عدد قابل محاسبه است. پس از ارزیابی تمام ویژگی‌ها، مجموعه‌ای از کاراترین آنها به کمک الگوریتم یادگیری ماشین آدابوست انتخاب شده و مورد استفاده قرار می‌گیرند. این چارچوب همچنین از یک معماری آبشاری برای پیداکردن سریع مناطق جالب توجه تصویر بهره می‌گیرد که امکان تشخیص چهره‌ٔ بلادرنگ را فراهم می‌کند. بنابراین اجزای این چارچوب عبارتند از:
ویژگی‌های شبه Haar عبارتند از نواحی روشن و تیره‌ٔ مستطیل شکلی که بر روی زیر پنجرهٔ ۲۴ در ۲۴ پیکسل مورد بررسی (نامزد احتمالی در برگیرندهٔ صورت) تعریف شده‌اند. ارزش هر ویژگی مشخص شده برابر با مجموع تمام مقادیر پیکسل‌های داخل مستطیل‌های روشن است که از مجموع تمام پیکسل‌های داخل مستطیل‌های تیره کاسته می‌شوند. سایر نقاط عکس که خارج از این مستطیل‌ها قرار دارند در محاسبه‌ٔ ویژگی در نظر گرفته نمی‌شوند. به این ترتیب برای هر پنجرهٔ ۲۴ در ۲۴ پیکسل متناظر با یک ویژگی یک عدد به عنوان ارزش این ویژگی محاسبه میشود. موضوعی که موفقیت این ویژگی‌های مستطیل شکل را تضمین می‌کند استفاده از ویژگی‌های کمابیش مشترک چهره‌های انسانی است.
تمامی چهره‌های انسانی دارای ویژگی‌های کمابیش مشابهی هستند. این قواعد می‌تواند با استفاده از ویژگی‌های شبه Haar تطبیق داده شوند. به عنوان مثال چند ویژگی مشترک برای چهره‌های انسانی عبارتند از:
ترکیب خواص زیر ویژگی‌های مشترک صورت‌های انسانی را تشکیل می‌دهند:
ویژگی‌هایی که ویولا و جونز استفاده می‌کنند دارای نواحی مستطیل شکل تیره و روشنی هستند که با مساحت برابر به صورت افقی یا عمودی در کنار هم قرار دارند. این ویژگی‌ها بر سه دسته هستند (تصاویر سمت راست): این سه نوع ویژگی در مکان‌های مختلف زیرپنجره‌ٔ ۲۴ در ۲۴ پیکسلی تعریف می‌شوند و تعداد آنها از ۱۸۰ هزار عدد بیشتر است. بنابراین نه تنها نیاز به روشی سریع برای ارزیابی مقادیر هر یک از این ویژگی‌ها احساس می‌شود، بلکه می‌بایست زیر مجموعه‌ٔ موثرتری از این ویژگی‌ها انتخاب شود که در ارزیابی تصویر نهایی مورد استفاده قرار گیرد.
همان طور که اشاره شد تعداد ویژگی‌های مورد استفاده در چارچوب ویولا-جونز متجاوز از ۱۸۰ هزار فیلتر است. به همین دلیل بدون استفاده از روشی سریع به منظور ارزیابی این ویژگی‌ها امکان آموزش الگوریتمهای طبقه بندی به منظور انتخاب زیرمجموعه‌ای موثر از این ویژگی‌ها و همچنین امکان ارزیابی بلادرنگ آنها روی زیر پنجره‌های نهایی تصویر وجود نخواهد داشت. همان طور که اشاره شد مقدار هر یک از این ویژگی‌ها از تفاضل مجموع مقادیر پیسکل‌های داخل نواحی تیره از مجموع مقدایر پیکسل‌های داخل نواحی روشن بدست می‌آید.
ارزش ویژگی = Σ (پیکسل‌های در ناحیه سفید) - Σ (پیکسل در ناحیه سیاه)
ویولا و جونز نشان دادند که چگونه می‌توان با استفادهٔ کارا از تصویر انتگرالی ویژگی‌های مستطیلی را در زمانی ثابت ارزیابی کرد، این روش مزیت سرعت ارزیابی قابل توجهی را نسبت به سایر ویژگی‌های پیچیدهٔ جایگزین فراهم آورد و استفاده از تصویر انتگرالی را در بینایی رایانه‌ای تثبیت کرد چرا که محاسبه‌ٔ تصویر انتگرالی تنها با یک بار عبور از روی تصویر اصلی قابل انجام است.
در یک تصویر انتگرالی مقدار هر پیکسل برابر با مجموع تمام پیکسلهای بالا و سمت راست این پیکسل روی تصویر اصلی به علاوه‌ٔ مقدار خود پیکسل روی تصویر اصلی است:
formula_1
که در آن formula_2 تصویر انتگرالی و formula_3 تصویر اصلی است. با استفاده از دو رابطه‌ٔ بازگشتی زیر می‌توان تصویر انتگرالی را تنها با یک بار عبور از روی تصویر اصلی ساخت:
formula_4formula_5
که در آن formula_6 مقدار تجمعی سطری و formula_7 و formula_8 است.
همان طور که در تصویر چپ نمایش داده شده است، با استفاده از تصویر انتگرالی می‌توان مجموع مقادیر داخل هر ناحیه‌‌ٔ مستطیلی روی تصویر اصلی را تنها با مقادیر چهار پیکسل روی تصویر انتگرالی محاسبه کرد. از آنجا که نواحی مستطیلی هر یک از ویژگی‌های شبه‌ Haar همیشه در مجاورت یکدیگر قرار دارند، مثلا برای محاسبهٔ هر ویژگی دو-مستطیلی تنها به مقادیر شش پیکسل، برای محاسبهٔ هر ویژگی سه-مستطیلی تنها به مقادیر هشت پیکسل و برای محاسبهٔ هر ویژگی چهار-مستطیلی تنها به مقادیر نه پیکسل از تصویر انتگرالی نیاز است.
سرعتی که ویژگی‌ها ممکن است مورد ارزیابی قرار گرفته شوند به تعداد کافی آن‌ها را جبران نمی‌کند . با این حال، به عنوان مثال، در یک زیر پنجره 24x24 پیکسل استاندارد، مجموعه ای از ویژگی‌های محتمل به بزرگی وجود دارد و برای بررسی همه آن‌ها در هنگام تست یک تصویر گران تمام خواهد شد. بنابراین، چارچوب تشخیص ابعاد الگوریتم یادگیری AdaBoost را به کار می‌گیرد تا هم بهترین ویژگی‌ها را انتخاب کند و هم طبقه‌بندی‌هایی را یاد دهد که از آن‌ها استفاده می‌شود. این الگوریتم طبقه‌بندی "قوی" را به عنوان ترکیبی خطی از طبقه‌بندی‌های ساده "وزن ضعیف" ایجاد می‌کند.
هر طبقه‌بندی ضعیف یک تابع آستانه بر اساس ویژگی formula_10است .
مقدار آستانه formula_12و قطب formula_13 در رشته مشخص شده‌اند ،
به همراه ضرایب formula_14.
در اینجا یک نسخه ساده الگوریتم یادگیری گزارش شده‌است:
ورودی: مجموعه ای از دنباله عکس‌های مثبت و منفی با برچسب‌های خود formula_15 . اگر تصویر یک چهره باشد formula_16، اگر نه formula_17 formula_17.
مقدار دهی اولیه : تعیین یک وزن formula_19 برای هر تصویر i.
برای هر ویژگی با formula_10 وزن‌ها را طوری تقسیم کنید که جمع آن‌ها یک شود.
ویژگی را برای هر تصویر در مجموعه دنباله اعمال کنید، سپس آستانه بهینه و قطبش formula_21 پیدا کنید که خطای طبقه‌بندی وزن دار را به حداقل می‌رساند. یعنی …
formula_22جایی که
formula_23
وزن هر formula_14را به formula_25که با معکوس نرخ خطا متناسب است . در این روش بهترین مرتب‌کننده‌ها بیشتر در نظر گرفته می‌شوند.
وزن‌های تکرار بعدی، برای مثال . formula_26، برای تصاویر i که به درستی طبقه‌بندی شده‌اند، کاهش می‌یابد.
طبقه‌بندی‌کننده نهایی را تنظیم کنید.
formula_27در آبشار، هر مرحله شامل یک طبقه‌بندی‌کننده قوی است. بنابراین تمام ویژگی‌ها در چند مرحله گروه‌بندیمی‌شوند که در آن هر مرحله دارای تعداد خاصی از ویژگی‌ها است.
هر مرحله وظیفه دارد تعیین کند که آیا یک زیر پنجره معین، قطعاً یک صورت نیست یا ممکن است یکصورت باشد. یک زیر پنجره داده‌شده فوراً به عنوان صورتی که در هر کدام از مراحل شکست می‌خورد، کنارگذاشته می‌شود.
یک چارچوب ساده برای آموزش آبشار در زیر آورده شده‌است:
معماری آبشاری مفهومی جالب برای عملکرد طبقه بنده‌ای فردی دارد. از آنجا که فعال‌سازی هر طبقه‌بندی‌کننده به‌طور کامل به رفتار سلف خود وابسته است، نرخ کاذب مثبت برای یک آبشار کلی عبارت است از:
به‌طور مشابه، میزان تشخیص برابر است با:
بنابراین برای مطابقت با نرخ‌های مثبت کاذب که معمولاً توسط ردیاب‌های دیگر بدست می‌آیند، هر طبقه‌بندی‌کننده می‌تواند با داشتن عملکرد ضعیف نامناسب دور شود. برای مثال برای یک آبشار ۳۲ مرحله‌ای برایدستیابی به نرخ مثبت کاذب ۱۰ - ۶، هر طبقه‌بندی‌کننده تنها به نرخ مثبت کاذب حدود ۶۵ % دست می‌یابند. در زمان مشابه، در عین حال، هر طبقه‌بندی‌کننده باید به‌طور استثنایی قادر به دستیابی به نرخ‌های تشخیص مناسب باشد. برای مثال، برای دستیابی به نرخ تشخیص حدود ۹۰ %، هر طبقه‌بندی‌کننده درآبشاری ذکر شده نیاز به دستیابی به نرخ تشخیص تقریباً ۹۹.۷ % دارد. [ ۷ ]
در فیلم برداری از اشیا متحرک، لازم است که فرد تشخیص اشیا را برای هر فریم اعمال کند. در عوض می‌توان از الگوریتم‌های ردیابی مانند الگوریتم klt برای تشخیص ویژگی‌های برجسته درون جعبه bounding وپی‌گیری حرکت آن‌ها بین فریم‌ها استفاده کرد. این کار نه تنها سرعت ردیابی را با حذف نیاز به ردیابی اشیا درهر فریم بهبود می‌بخشد، بلکه مقاومت را نیز به خوبی بهبود می‌بخشد، چون ویژگی‌های برجسته انعطاف‌پذیری یبیشتری نسبت به چارچوب تشخیص ویولا جونز [Viola-Jones] برای چرخش و تغییرات فوتومتریک دارند. [ ۸ ]