CBIR: Content Based Image Retrieval

الگوی باینری محلی (Local binary patterns)


الگوی باینری محلی اولین بار به عنوان یک توصیف کننده ی الگوی غیرحساس به چرخش برای تصاویر طیف خاکستری معرفی شد. این الگوریتم با آستانه گیری همسایگی 3×3 برای هر پیکسل مرکزی با شدت سطح خاکستری Pc، تعداد 8 پیکسل همسایگی آن  Pn که مقدار n از صفر تا هفت می باشد را محاسبه نموده و نتیجه را به عنوان یک عدد باینری بر میگرداند.

یک مثال با استفاده از این تکنیک در متلب را می توان به صورت زیر تعریف نمود:

مرحله اول: ابتدا دو تصویراولیه در متلب خوانده میشود

brickWall = imread('bricks.jpg');

rotatedBrickWall = imread('bricksRotated.jpg');

 

تصویر اول ، تصویر اصلی و تصویر دوم تصویر دوران یافته تصویر اول میباشد.اکنون تصویر سومی که متفاوت از این دو تصویر است را در متلب میخوانیم:

carpet = imread('carpet.jpg’);

 

مرحله دوم: اکنون به کمک تکنیک LBP ویژگی های باقت تصویر را استخراج میکنیم:

lbpBricks1 = extractLBPFeatures(brickWall,'Upright',false);

lbpBricks2 = extractLBPFeatures(rotatedBrickWall,'Upright',false);

lbpCarpet = extractLBPFeatures(carpet,'Upright',false);

 

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

brickVsBrick = (lbpBricks1 - lbpBricks2).^2;

brickVsCarpet = (lbpBricks1 - lbpCarpet).^2;

 

اگر این مربع خطا را ترسیم کنیم مقدار آن برای تصویر اول نسبت به تصویر دوم کمتراز تصویر سوم است.

figure

bar([brickVsBrick; brickVsCarpet]','grouped’);

title('Squared Error of LBP Histograms’);

xlabel('LBP Histogram Bins’);

legend('Bricks vs Rotated Bricks','Bricks vs Carpet’);



بردار ویژگی LBP در ساده ترین شکل آن به روش زیر ایجاد می شود:

پنجره مورد آزمایش را به سلول های مختلف تقسیم کنید( به عنوان مثال16 *16 پیکسل برای هر سلول انتخاب شود)
برای هر پیکسل در یک سلول، پیکسل را با هر یک از 8 همسایه خود (در سمت چپ، چپ وسط، چپ پایین، راست بالا و غیره) مقایسه کنید. پیکسل ها را در امتداد یک دایره دنبال نمایید. به عنوان مثال در جهت عقربه های ساعت یا خلاف آن.

جایی که ارزش پیکسل مرکز بزرگتر از مقدار همسایه است عدد صفر و در غیر اینصورت عدد 1 را بنویسید. نتیجه آن یک عدد دودویی 8 رقمی است که معمولا برای راحتی تبدیل به decimal می شود.

 

هیستوگرام را برای تمامی سلول ها محاسبه و در صورت لزوم می توان آنها را نرمال کرد. هیستوگرام های نرمالیزه شده از تمام سلول ها یک بردار ویژگی برای کل تصویر ارائه می دهد


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

 

نمونه کد تولیدی برای الگوریتم روش دایره ای به صورت ذیل می باشد:




function LBP_Im = LBP(Input_Im, R)

 if size(Input_Im, 3) == 3

     Input_Im = rgb2gray(Input_Im);

end;

L = 2*R + 1; %% The size of the LBP label

C = round(L/2);

Input_Im = uint8(Input_Im);

row_max = size(Input_Im,1)-L+1;

col_max = size(Input_Im,2)-L+1;

LBP_Im = zeros(row_max, col_max);

for i = 1:row_max

    for j = 1:col_max

         A = Input_Im(i:i+L-1, j:j+L-1);

        A = A+1-A(C,C);

        A(A>0) = 1;

       LBP_Im(i,j) = A(C,L) + A(L,L)*2 + A(L,C)*4 + A(L,1)*8 + A(C,1)*16 + A(1,1)*32 + A(1,C)*64 + A(1,L)*128;

    end;

end;

 

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

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

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

            


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

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


گراف 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 نشان داده می شوند و بیانگر تعداد مجموعه های بسته است که در تصویر تشخیص داده می شوند. این مجموعه ها نه تنها بافت را تعریف می کنند، بلکه موقعیت آنها در تصویر را نیز نشان می دهند. شناسایی بافت های خاص در یک تصویر با استفاده از مدل سازی بافت به عنوان یک تغییر در سطح خاکستری دو بعدی حاصل می شود. روشهای دیگر طبقه بندی بافتها عبارتند از: