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;

 

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

;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