CBIR: Content Based Image Retrieval

نمونه کد مثلث دیلانی و گراف ورونی آن

;rand('state',0)

;x = rand(1,10)

;y = rand(1,10)

;TRI = delaunay(x,y)

subplot(1,2,1),...

triplot(TRI,x,y)

;axis([0 1 0 1])

;hold on

;plot(x,y,'or')

hold off

;[vx, vy] = voronoi(x,y,TRI)

subplot(1,2,2),...

plot(x,y,'r+',vx,vy,'b-'),...

axis([0 1 0 1])


مثلث‌ دیلانی (دلونی)

در ریاضیات و هندسه محاسباتی یک مثلث دیلانی برای یک مجموعه از نقاط به نام P در یک صفحه، یک مثلث‌بندی به نامDT(P) است به نحوی که هیچ یک از نقاط P درون هیچ‌ یک از دایره‌های محیطی مثلثهای DT(P) نباشد. این مثلث‌بندی کمینه‌ی زاویه‌های مثلثها را به بیشترین مقدار ممکن می‌رساند و به این ترتیب از به وجود آمدن مثلث‌های باریک جلوگیری می‌کند. این مثلث‌بندی توسط بوریس دیلانی  در سال ۱۹۳۴ ابداع شده است[1]. برای چهار یا تعداد بیشتری نقطه روی یک دایره یکسان (به عنوان مثال راس های یک مستطیل) تثلیث دیلانی یکتا نیست : هر دو تثلیث ممکن که چهار ضلعی را به دو مثلث تقسیم کنند و شرط دیلانی حاصل شود به عنوان مثال فرض اینکه اگر تمام دایره های محیطی مثلث ها درون تهی باشند. با در نظر گرفتن کره های محاطی ایده ی تثلیث دیلانی به سه یا تعداد بیشتری بعد تعمیم می یابد. تعمیم به سیستم متریک نسبت به سیستم اقلیدسی ترجیح داده می‌شود ولی در این موارد (اقلیدسی) تثلیث دیلانی الزاماً وجود ندارد یا یکتا نیست.

همانطور که گفته شد با داشتن P نقطه و محاسبه دوایر محیطی می توان مثلث های دیلانی را ترسیم کرد حال اگر مراکز این دوایر محیطی را به هم متصل نماییم گرافی به دست می آید که به آن دیگرام ورونی گفته می شود. تصاویر ذیل بیانگر مثلث های دیلانی با تمام دایره های محیطی و مراکزشان و دیاگرام ورونی می باشد.

            


تثلیث دیلانی درمدل سازی موقعی که مجموعه ای از نقاط داده شده اند یک مجموعه ی خوبی از مثلث ها را تولید می کند که می‌تواند به عنوان چند ضلعی در مدل استفاده شود. به طور خاص تثلیث دیلانی سعی دارد از مثلث های باریک استفاده نکند. تثلیث دیلانی می‌تواند برای مشخص کردن چگالی یا شدت نقاط در مدل سازی نقاط به معنی Delaunay tessellation field estimator استفاده شوند.

در نرم افزار متلب نیز با استفاده از دستور delaunay(x,y) می توان نسبت به محاسبه مثلث های دیلانی اقدام کرد که در آن x و y بیانگر مشخصات نقاط می باشند. (دوآرایه که مشخصات نقاط در آنها ذخیره شده است) و با دستور  voronoi(x,y,TRI) نیز گراف ورونی را نیز محاسبه نمود که TRI مشخصات مثلث های دیلانی می باشد. دیلانی چند بعدی نیز وجود دارد که توضیح آن از حوصله این نوشتار خارج است. نمونه کد مربوط به تشکیل مثلث ها و گراف نیز در قسمت برنامه نویسی آمده است


شبکه های عصبی کانولوشن

 

همانطور که می دانیم بسیاری از داده های مهم دنیای واقعی به شکل نمودار ها یا شبکه ها وجود دارند به عنوان مثال: شبکه های اجتماعی[1]، نمودارهای دانش[2]، شبکه های پروتئین[3]، شبکه جهانی وب[4] و غیره

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

مقدمه کوتاه به مدل شبکه عصبی بر روی نمودار
حلقه های گراف طیفی و گراف شبکه های کانولوشنی(GCNs)[5]
تهیه گراف با یک مدل ساده GCN  مرتبه1
GCN ها به عنوان تعمیم الگوریتم Weisfeiler-Lehman

 

به طور کلی کار با مدل های عصبی شناخته شده مانند RNN یا CNN  بر روی نمودارهای خودساخته یک مشکل چالش برانگیز است.

در حال حاضر، اغلب مدلهای شبکه عصبی دارای معماری مشترکی می باشند و و از فیلترها به صورت پارامتریک و به طور معمول در همه نقاط در گراف استفاده می شود. برای همه این مدلها، هدف تابعی است که پس از آموزش مدل، یک سیگنال یا ویژگی را گرفته و مقداری متناظر آن ایجاد کند به عبارتی G=(V,E) که مقادیر زیر را دریافت می کند.

ویژگی xi  برای هر گره iدر ماتریس ویژگی X:N*D خلاصه می شود که در آن N تعداد گره ها و D تعداد ویژگی های ورودی است
توصیف کننده به شکل یک ماتریس نمایش داده می شود که اغلب ماتریس متقارن A نام دارد. خروجی نودها هم به صورت Z تعریف می شود که یک ماتریس N*F  است که در آن F تعداد ویژگی های خروجی متناظر هر نود می باشد.

هر لایه شبکه عصبی را می توان به صورت یک تابع غیر خطی به شکل  H(l+1)=f(H(l),A) بیان کرد که در آن H(0)=X و H(l)=Z و l هم بیانگر تعداد لایه های شبکه عصبی می باشد.

 

یک نمونه ساده از GCN

فرض کنیم ()(lW)(lHAσ(=(,A)(lH) f  که در آن )l(W مقدار وزن لایه l از شبکه عصبی است و σ(0) هم یک مقدار غیر خطی همانند  [6]ReLU است.

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

1-منظور از عمل ضرب با A به این معنی است که برای هر گره، تمام بردارهای ویژگی همه گره های همسایه را جمع می کنیم، اما نه خود گره را به عبارتی حلقه در گراف وجود ندارد.

2- مقدار ماتریس A نرمال نشده است لذا ضرب آن باعث تغییر در وزن در بردارهای ویزگی می شود.لذا از   استفاده می کنیم که در آن D ماتریس قطری درجه گره است و برای نرمال سازی متقارن از فرمول زیر استفاده می نماییم.

بنابراین تابع ما به صورت زیر خواهد بود

 مقدار   حاصل جمع ماتریس A با ماتریس I (واحد) می باشد و مقدار    ماتریس قطری   است.

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

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

مطالب ارائه شده تا اینجا به این فرم بود که مقادیر متمایز بودند و همه به صورت پارامتریک ارائه شده بود. با اضافه کردن برچسب هایی به مدل امکان اضافه نمودن آموزش به مدل وجود دارد که برای این منظور می بایست از الگوریتم های یادگیری نیمه متمرکز[7] استفاده نماییم.



[1] Social networks

[2] Knowledge graphs

[3] Protein-interaction networks

[4] World Wide Web

[5] Graph Convolutional Networks

[6] Rectified Linear Unit

[7] Semi-supervised learning

گراف 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



بازیابی تصویر محتوا محور از منظر ویکیپدیا


بازیابی تصویر مبتنی بر محتوا  CBIR[1] به عنوان پرس و جو با محتوای تصویر QBIC[2] شناخته شده است.بازیابی اطلاعات بصری مبتنی بر محتوا CBVIR[3] راهکاری است برای استفاده از تکنیک های بینایی کامپیوتری برای رفع مشکل بازیابی تصویر  برای جستجوی تصاویر دیجیتال در پایگاه داده های بزرگ. "مبتنی بر محتوا " به این معنی است که جستجو بر اساس محتوا باشد به جای ابرداده مانند کلمات کلیدی، برچسب ها و یا توصیف های مرتبط با تصویر. اصطلاح در این مقوله "محتوا" ممکن است به رنگ ها، شکل ها، بافت ها و یا هر گونه اطلاعات دیگر که می تواند از تصویر به دست آید اشاره کند. بازیابی تصویر مبتنی بر محتوا اثر بخش و مفید است زیرا جستجوهایی که به طور کامل به فراداده متکی هستند وابسته به کیفیت و کامل بودن آن می باشند.

 

تاریخچه

اصطلاح "بازیابی تصویر مبتنی بر محتوا" در سال 1992 هنگامی که توسط T.Kato برای توصیف آزمایشات مربوط به بازیابی خودکار تصاویر از یک پایگاه داده بر اساس رنگ ها و شکل های موجود استفاده شد بر می گردد. از آن به بعد، این اصطلاح برای توصیف روند بازیابی تصاویر مورد نظر از یک مجموعه بزرگ بر اساس ویژگی های تصویری هماهنگ استفاده شده است. تکنیک ها، ابزارها و الگوریتم هایی که استفاده می شوند، از روش هایی مانند آمار، تشخیص الگو، پردازش سیگنال و دید کامپیوتری بهره می گیرند. اولین سیستم CBIR تجاری توسط آی بی ام توسعه یافته QBIC  نامیده شد.

 

پیشرفت فنی

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

 

روش های موجود

الف- ارزیابی معنایی[4]

بازیابی معنایی با یک درخواست کاربر مانند "پیدا کردن عکسهای ابراهیم لینکلن" آغاز می شود. انجام این نوع از برای کامپیوترها بسیار دشوار است زیرا لینکلن همیشه تصویر حاصل از یک دوربین نیست. بنابراین بسیاری از سیستم های CBIR به طور کلی از ویژگی های سطح پایین مانند بافت، رنگ و شکل استفاده می کنند. و از این ویژگی ها و یا ترکیب آنها برای مطابقت با ویژگی هایی (مانند چهره، اثر انگشت یا تطبیق شکل) استفاده می شود. به طور کلی، بازیابی تصویر نیاز به همکاری انسان برای شناسایی و درک مفاهیم بالاتر دارد.

 

ب- روش بازخورد (ارتباط دوسویه ماشین و انسان)

ترکیبی از تکنیک های جستجوی CBIR که کاربر را قادر به جستجوهای پیشرفته می کند. در این روش کاربر به تدریج نتایج جستجوی خود را با علامت گذاری تصاویر در نتایج به عنوان "مرتبط"، "غیر مرتبط" یا "خنثی" علامت گذاری کرده و سپس از آنها در جستجوهای جدید استفاده می شود. تاکنون نمونه هایی از این نوع سیستم و رابط ساخته شده است.

 

ج- یادگیری ماشین / تکراری

یادگیری ماشین و استفاده از تکنیک های تکراری در CBIR شایع تر است.

 

ه- سایر روشهای پرس و جو

سایر روشهای پرس و جو عبارتند از: مرور دسته بندی های سفارشی / سلسله مراتبی، پرس و جو در منطقه تصویر (به جای کل تصویر)، پرس و جو با چند تصویر نمونه، پرس و جو با طرح بصری، پرس و جو با مشخصات مستقیم از ویژگی های تصویری و پرس و جو چندجمله ای مانند ترکیب لمس، صدا و غیره

 

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

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

 

ح- بافت

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

     ماتریس همبستگی

     قانون بافت انرژی

     تبدیل موجک

 

ط- شکل

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

 

ارزیابی بازیابی تصویر

معیار ارزیابی روش های بازیابی تصویر را می توان دقت و فراخوانی آنها تعریف کرد هرچند که در اکثر سیستم های CBIR  از چند تکنیک به طور همزمان برای بازیابی تصویر استفاده می شود.

 

منبع

https://en.wikipedia.org/wiki/Content-based_image_retrieval

 



[1] Content-based image retrieval

[2] Query by image content

[3] content-based visual information retrieval

[4] Semantic retrieval

1 2 3 4 >>