گراف Elastic

EGM[1] به صورت یک گراف برچسب دار[2] معرفی می شود که نود ها در آن بیانگر بافت بوده و بر اساس موجک گابور می باشند. یال ها نیز بیانگر فاصله نودها در تصویر هستند. لازم به ذکر است که تصویر مجموعه ای از بافت ها می باشد که به هم متصل هستند. زمانی که یک بخش در تصویر شناسایی می شود این بخش در گراف برچسب دار ذخیره شده که به آن گراف مدل[3] می گویند. این گراف بهترین روش برای بیان بافت ها می باشد.

EBGM[4] یک توسعه از EGM است برای کلاس های اشیاء که دارای ساختار های مشترک می باشند. همانند تصاویر صورت که دارای موقعیت‍های یکسان می باشند. همه مقادیر در این کلاس ها یک نمودار را می سازند که به وسیله آن نمودارهای گروه[5] که از ساختارهای مشابه ساخته می‍شود تولید می گردد. از این نمودارها، یک گراف چندگانه از همان ساختار ایجاد می شود، با گره هایی که بافت های محلی هر شی در کلاس را نشان می دهند که به عنوان مثال می توان به تمام انواع چشم چپ اشاره کرد. یال ها نیز نشان دهنده فاصله متوسط بین گره ها می باشند. به عنوان مثال میانگین فاصله بین دو چشم را می توان نام برد. در حالت کلی بافت چشم ها می تواند از یک چهره و بافت دهان از چهره دیگر گرفته شود تا چهره جدیدی را نشان دهد که دارای مشخصات دو چهره ذخیره شده است. بدین ترتیب، یک گراف ترکیبی انتزاعی برای نمایش کلاسهای شیء به جای اشیاء خاص وجود خواهد داشت. EBGM  تنها می تواند در مورد اشیاء با ساختار مشترک استفاده شود، مانند تصویر چهره از روبرو که عملا با به اشتراک گذاشتن مجموعه ای از نشانه ها مانند نوک بینی و یا گوشه های چشم بوجود می آید.

یکی از ابزارهای مناسب برای EBGM استفاده از موجک گابور[6] می باشد که از رابطه زیر به دست می آید

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

برای محاسبه کانولوشن[7]  از تبدیل فوریه آن به فرم زیر استفاده می شود:

استفاده از سری فوق با مقادیر استاندارد باعث تولید 40 مقدار برای هر پیکسل از تصویر می شود که تعداد 40 مقدار آن واقعی و تعداد  40 مقدار هم تخمینی است به مجموعه این مقادیر جت[8] گفته می شود.

نحوه کار  EGM به شکل زیر است:

1-     حرکت عمومی[9] : که در آن تصویر بررسی شده و موقعیت اشیاء در آن مشخص می شود. اسکن معمولا بر روی یک شبکه مستطیل شکل از موقعیت ها با فاصله بزرگ مثلا 10 پیکسل انجام می شود.

2-     مقیاس حرکت[10]: برای پیدا کردن اندازه مناسب و نسبت ابعاد شی به کار می رود. در این مرحله گراف تصویر به صورت افقی و عمودی مقیاس گرفته تا میزان شباهت آن با گراف مدل مشخص شود.

3-     حرکت محلی[11]: در این مرحله انتقال تمام گره ها به صورت محلی برای مشخص شدن انطباق یا تفاوت ها انجام می شود. در نهایت این حرکت محلی به صورت تصادفی باعث پیدا کردن بهترین انطباق می گردد البته این روش می بایست برای همه نود ها انجام پذیرد.

EGM دو فایده عمده دارد:

الف- نمودار برای اشیاء جدید می تواند به روش مکانیزه ایجاد شود.

ب- نیازی نیست که هر مدل واحد در گالری را با تصویر مقایسه کنیم.

یک گراف تصویر می تواند مستقل از یک مدل پایه ساخته شود و فقط مقایسه گراف برای هر مدل انجام می گیرد که باعث کاهش حجم محاسبات می شود. هنگامی که ما وسیله ای برای تولید و مقایسه نمودارهای تصویر داریم، تشخیص چهره ها در یک شکل یکنواخت راحت است.
در حالیکه تشخیص چهره در بین جنبه های مختلف، پیچیده تر می باشد. برای روشن شدن موضوع فرض کنید ما 1000 تصویر چهره داریم، به عنوان مثال همه به طور مستقیم به دوربین نگاه می کنند و بوسیله نام شخص این تصاویر مشخص می شوند. این مجموعه تصاویر گالری را تشکیل می دهد. برای تشخیص چهره ما به روش زیر عمل می کنیم:

مرحله 1: ساخت یک گراف چهره

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

مرحله 2: ساختن نمودار گروه چهره

 نمودار که در بالا تعریف شده است می تواند به عنوان یک گراف دسته ای با یک نمونه در آن معرفی شود. اگر تصویر دوم منطبق بر تصویر اول نباشد کیفیت تطابق پایین است. فرض کنیم تصویر نوک بینی بر روی گونه منطبق شده باشد که نیاز به تغییر می باشد که پس از تغییر تصویر مورد نظر به صورت دستی می توان آن را تایید نمود و به مجموعه گراف اضافه کرد. با تکرار این فرآیند گراف رشد کرده و دقت تصاویر آن بیشتر می‌شود که تعداد انجام این کار 100 مورد می باشد.

مرحله 3: ساختن گالری گراف ها[12]

حال 900 تصویر باقیمانده را با گراف های موجود به صورت اتوماتیک مطابقت می دهیم. در نهایت می توانیم همه 1000 تصویر را به صورت مکانیزه بررسی کنیم.

مرحله 4: ساخت گراف کاوشگر[13]

فرض کنید ما یک تصویر جدید داریم و باید تصویر را در گالری پیدا کنیم. ابتدا باید یک گراف برای تصویر ایجاد کنیم. این فرایند دقیقا همانطور که برای تصاویر مدل انجام می شود صورت می پذیرد.

مرحله 5: مقایسه با تمام نمودارهای مدل

گراف تصویر با تمام نمودارهای مدل مقایسه می شود و در نتیجه 1000 مقدار شباهت به دست می آید.

مرحله 6: شناسایی

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

از این روش می توان برای شناسایی تصاویر مرد و زن و یا فرد با عینک و بدون عینک و ریش دار و بدون ریش استفاده کرد. از این روش برای تشخیص تصاویر با معلولیت های خاص هم می توان استفاده نمود.  به عبارتی امکان استفاده از آن در علوم پزشکی نیز وجود دارد.

---

[1] Elastic Graph Matching

[2] Labeled graphs

[3] Model graph

[4] Elastic Bunch Graph Matching

[5] Bunch graph

[6] Gabor Wavelets

[7] Convolution

[8] Jet

[9] Global Move

[10] Scale Move

[11] Local Move

[12] Gallery of Graphs

[13] Probe Graph