برای انجام پردازش بر روی نقشه قالی، فرض می‌شود که نقشه قالی از ترکیب آرایه­های مختلف تشکیل شده است و از قرار گرفتن این آرایه­ها کنارهم، باغی ایرانی برای نقشه قالی شکل گرفته است. هنگام طراحی نقشه قالی معمولا آن را به چند قسمت تقسیم می­کنند که در شکل (1، یک قسمت از 6 قسمت نقشه یک قالی نشان داده شده است. این نقشه از مجموعه ای از گل‌ها، برگ­ها و شاخه­هایی که آنها را به هم پیوند می­دهند، تشکیل شده است که هریک از این عناصر به تنهایی آرایه خوانده می­شود. در شکل (1نمونه‌هایی از آرایه‌های تشکیل دهنده شکل (1، به صورت جداگانه نشان داده شده است.

چنانچه هریک از این آرایه­ها توسط رایانه شناخته شوند، با استفاده از این شناخت و ترکیب آن با رنگ­های مورد استفاده در قالی و هچنین طرح­های مورد استفاده، می‌توان نقشه قالی را به صورت خودکار تحلیل کرد؛ مثلا می‌توان با داشتن فایل‌های تصویری مختلف نقشه­های قالی ایران مشخص کرد که هر تصویر متعلق به کدام مرکز قالیبافی ایران است و یا با ترکیب آرایه­ها و اضافه کردن و یا جایگزین کردن آن در طرحی از قالی، طرح نو دیگری را به وجود آورد و همچنین، روش­های دیگری که هنگامی که راه شناخت و تحلیل آرایه­ها به صورت خودکار باز شد، می‌توانند ایجاد و استفاده شوند]4[.

شکل (1): قسمتی از یک نقشه دستی قالی]4[.

شکل(2): نمونه‌هایی از آرایه‌های موجود در نقشه قالی شکل (1) الف) شکوفه؛ ب) غنچه؛ ج) شاه عباسی و د)  نیم برگ]4[.

یکی از کاربردهای مهم توصیف تصویر، جستجوی یک تصویر در بین مجموعه تصاویر است. معمولا علاقه مندیم که توصیفگر انتخابی، در مقابل تغییرات مقیاس، چرخش و جابه‌جایی مقاوم باشد. همچنین، روشی که در عین سادگی، توصیف مناسبی برای شکل‌های مورد نظر ما داشته باشد ارجح و برتر است. تبدیل موجک نسبت به چرخش، انتقال و تغییر مقیاس حساس است. برای پایا شدن در مقابل این تغییرات از خروجی تبدیل موجک ویژگی‌های مناسبی استخراج می­شود. از تبدیل فوریه برای حذف اثر انتقال و از تبدیل ملین برای حذف اثر چرخش و تغییر مقیاس استفاده می­شود. این دو تبدیل در کنار هم به اختصار [1]FMT نامیده می­شوند. تئوری این تبدیل در] 12،13 [شرح داده شده است. این روش در مقایسه با روش‌های دیگر کمترین پیش پردازش را نیاز دارد. مجموعه توصیفگر FMT با تبدیل موجک، توصیفگر [2]WFMT نامیده می­شود] 14 [که در این مقاله از آن استفاده می­شود. از تبدیل موجک برای مقاوم شدن در مقابل نویز و اعوجاج استفاده شده است] 14[. همچنین، به علت کاهش ابعاد تصویر توسط تبدیل موجک، سرعت پردازش نیز افزایش می­یابد.

1- مروری بر کارهای دیگران

در زمینه بازنمایی گل قالی، غالبی از توصیفگر فوریه بر روی کانتور گل استفاده کرده است]4[. اما در زمینه توصیفگری که شامل جزییات داخلی گل قالی نیز باشد تاکنون کاری انجام نشده است. کارهایی که به نظر می‌رسد بیشترین تشابه را با این کار داشته باشند، بازنمایی لوگو، اثر انگشت، کف دست و از این قبیل است. نمونه ای از گل‌های مورد نظر ما در شکل  نشان داده شده است.

شکل (3): نمونه گل‌های قالی؛ الف) و د) گل شاه عباسی؛ ب) گل اسلیمی و ج) گل نرگس.

کارهایی که روی لوگو انجام شده است، عمدتا دو روش هستند که برخی براساس کانتور هستند که مناسب کار ما نیستند و برخی که بر اساس ناحیه هستند، برای داده‌های ما کارایی ندارند. کاری که از نظر جزییات، بیشترین شباهت را به کار ما دارد، بازنمایی اثر انگشت است و روش کار در این مقاله بر اساس ایده‌هایی است که از روش‌های به کار برده شده برای اثرانگشت گرفته شده است.

یکی از روش‌هایی که برای کار ما مناسب است استخراج ویژگی از زیر باندهای تبدیل موجک است. در سال 2003 هنری سلواراج[3]]18[ از این روش برای بازشناسی اثر انگشت استفاده کرده است. در سال 2001 ماریوس تیکو[4]]20[ با استفاده از موجک­های مختلف و دسته بند  k-NNنرخ بازشناسی نسبتا خوبی به دست آورده است. در سال 2010 سانجکار[5] نیز با استفاده از موجک­ هار از همین روش در بازشناسی اثر انگشت استفاده کرده است]21[.در ]22[ نیز این روش به کار برده شده است.

روش دیگر استفاده از تبدیل موجک و تبدیل فوریه-ملین است. در سال 2008 اسماعیل[6] و رمضان[7] از این روش برای بازشناسی اثر انگشت استفاده کرده اند]23[. در اینجا به جای اینکه در ابتدا از تصویر تبدیل موجک گرفته شود، از خروجی تبدیل فوریه-ملین تبدیل موجک گرفته شده است و در انتها از دسته بند  k-NNبرای دسته بندی استفاده شده است. در سال 2007 نبیل[8] از این روش برای تطابق اثر انگشت استفاده کرده است]24[. همچنین در کنار فوریه-ملین، ویژگی­های انحراف معیار زیر باندهای موجک و انرژی تصویر نیز در بازشناسی به کار برده شده است. نبیل با به کار گرفتن این روش به نرخ بازشناسی نسبتا بالا و سرعت پردازش خوبی دست یافته است. در سال 2003 جین[9] در یک مقاله به طور مفصل این روش را تشریح کرده است]14[. برای بازشناسی نیز از دسته بند  k-NNو فاصله اقلیدسی استفاده شده است. همچنین، در سال 2009، چنگ[10] از تبدیل‌های گابور و موجک برای استخراج بردار ویژگی از اثر انگشت استفاده کرده است]25[.

2- معرفی توصیفگرهای انتخاب شده

توصیفگر اول که بر مبنای استخراج ویژگی از زیر باندهای تبدیل موجک است، بدین صورت است که ابتدا تصویر را با استفاده از تبدیل موجک تا چند مرحله تجزیه می­کنیم. در در شکل (4) مراحل تجزیه تا سه مرحله نشان داده شده است.

شکل (4):اعمال تبدیل موجک با پایه دابیشی2 بر روی گل قالی تا مرحله سوم.

پس از تجزیه توسط موجک از زیر باندهای به دست آمده (یعنیLLk , LHk , HLk , HHk  ;در اینجا برای k=1,2,3 ) برای استخراج ویژگی استفاده می‌کنیم. در هر مرحله تعداد چهار زیرباند داریم و اگر تا مرحله jام تصویر را تجزیه کنیم، به تعداد4j  زیر باند می‌رسیم. در هر زیرباند، دو ویژگی میانگین و انحراف معیار زیر‌باند حساب می‌شود و با استفاده از یک دسته بند تصاویر دسته بندی می‌شوند. دیاگرام این روش در شکل  نشان داده شده است.

شکل (5): استخراج ویژگی با زیر باندهای تبدیل موجک]22[.

برای بهبود نرخ بازشناسی می‌توان ماتریس هم رخدادی[11] را برای زیرباند‌هایی که در مرحله اول تجزیه می‌شوند، حساب کرد. چند ویژگی حاصل از ماتریس‌های هم رخدادی مانند بیشینه احتمال[12]، تباین[13]، آنتروپی[14]، انرژی[15]، همگنی محلی[16] و برجستگی خوشه‌ای[17] توسط هارالیک[18] در سال 1973 معرفی شده اند]19[.

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

شکل (6): بلوک دیاگرام تولید ویژگی WFMT بر گرفته از ]19[.

3- معرفی مجموعه داده

برای تهیه مجموعه گل‌ها، از نقشه‌های دستی قالی، کتاب‌ها و مجلات استفاده شده است. بیشتر این داده­ها از منابع مذکور روبش شده و برخی نیز از روی پشت قالی به صورت دستی کشیده شده­اند. گل­هایی که در دسترس بوده است، مجموعه‌ای است که غالبی آنها را جمع آوری کرده است]4[. در پژوهشی که او انجام داده]4[ جزییات داخلی گل‌ها حذف شده‌اند و تنها کانتور آنها مد نظر بوده است.

به دلیل اینکه پردازش‌های انجام شده روی داده برای به دست آوردن کانتور بوده، این پردازش‌ها برای کار ما مناسب نیست. بنابراین، در این مقاله با توجه به اینکه جزییات داخلی مد نظر است، پردازش‌های مناسب را برای آماده سازی تصاویر انجام می‌دهیم. همچنین، تعدادی گل نیز به مجموعه گل­های جمع آوری شده اضافه شده است.

پس از جمع آوری داده توسط غالبی، با استفاده از نظرهای اساتید قالی، گل‌ها به چند شاخه و زیر شاخه تقسیم شده اند. در شکل  ساختار بندی مجموعه نشان داده شده است. در این ساختار گل‌ها به چهارده زیر شاخه انتهایی تقسیم شده اند. آرایه‌ها به دو بخش اسلیمی و ختایی تقسیم شده است. شاخه اسلیمی دارای سه زیر بخش ماری، ساده و دهان‌اژدری است. شاخه ختایی دارای سه زیر بخش غنچه، برگ و گل‌هاست. زیر بخش غنچه دارای سه زیر بخش سه برگ، دو برگ و تک برگ است. زیربخش برگ دارای سه زیربخش نیمه برگ، کنگری و بادامی است. زیربخش گل‌ها دارای دو زیربخش شاه‌عباسی و گرد است. زیر بخش گل گرد نیز دارای سه زیر بخش گل‌پنج‌پر ، گل نرگس و گل شکوفه است. به این علت که گل‌های غنچه سه برگ دارای دو دسته­ی متفاوت از هم هستند، این گل به دو کلاس تقسیم شد که در نهایت گل­ها به چهارده کلاس تقسیم شدند.

شکل (7): ساختار بندی مجموعه گل‌های قالی ]4[.

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

شکل (8): گل‌های اولیه که از نقشه‌های قالی جدا شده اند.

شکل (9): گل‌های رنگی که از کتاب‌ها روبش شده اند.

شکل (10): گل‌های خاکستری که دارای لبه‌های واضحی هستند و از مجلات روبش شده‌اند.

به این علت که عکس‌ها از منابع مختلف جمع آوری شده‌اند، اندازه آنها با هم یکی نیست. از آنجایی که در این مقاله بر روی خود تصویر کار می­شود، برای استخراج ویژگی نیاز است عکس­ها هم اندازه باشند. به همین علت، در ابتدا اندازه تمام عکس­های اصلی روبش شده، به 256x256 تبدیل شد و در مرحله بعد گل­های رنگی نیز به خاکستری تبدیل شدند.

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

شکل (11): گل‌ها پس از تبدیل شدن به باینری برای 14 کلاس

از تعداد نمونه موجود برای هر کلاس، نیمی از آنها به عنوان نمونه‌های یادگیری و نیمی دیگر به عنوان نمونه‌های آزمایش در نظر گرفته شده اند. در جدول تعداد نمونه‌های مربوط به هر آرایه، برای این مجموعه داده نشان داده شده است. برخی از گل‌ها تنوع کمتری دارند و برخی نیز مانند گل شاه‌عباسی از تنوع بیشتری برخودارند و به همین جهت نمونه­های بیشتری از آن تهیه شده است.

جدول (1): تعداد نمونه‌های موجود از هر آرایه

4- نحوه بازنمایی و بازشناسی

برای بازنمایی، از توصیفگرهای موجک و WFMT استفاده می­کنیم. همچنین برای به دست آوردن میزان کارایی توصیفگر از بازشناسی استفاده می­کنیم. برای بازشناسی ابتدا برای هر کلاس چند نماینده انتخاب می­شود و به ورودی توصیفگر داده می­شود و خروجی حاصل از توصیفگر در پایگاه داده ذخیره می­شود. نماینده­ها از نمونه­های یادگیری انتخاب می­شوند. پس از اینکه پایگاه داده آماده شد، از نمونه­های آزمایش نیز به توصیفگر داده می­شود و خروجی آن با پایگاه داده مقایسه می­شود و به هر کلاسی که نزدیک بود، به آن کلاس تخصیص می‌دهیم. برای ارزیابی نرخ بازشناسی از K-NN استفاده شد که بیشترین نرخ بازشناسی با معیار فاصله مانهاتان به دست آمد. برای K>2، هر کلاس که بیشترین تخصیص را داشت به آن کلاس تعلق می‌گیرد و اگر دو کلاس به تعداد مساوی امتیاز آوردند کلاسی که میانگین فاصله کمتری دارد گل به آن اختصاص می‌یابد.

برای انتخاب نماینده به صورت زیر عمل میکنیم. ابتدا نمونه­های یادگیری هر کلاس را با استفاده از الگوریتمK-Means  به چند خوشه تقسیم می‌کنیم و اگر فاصله مرکز دو خوشه، از دو برابر فاصله دورترین داده خوشه کمتر باشد آن دو خوشه را یکی می­کنیم، تا جایی که مراکز خوشه­ها به اندازه کافی از هم فاصله داشته باشند. سپس از هر خوشه نمونه­ای را که به میانگین نمونه­های آن خوشه نزدیکتر است، به عنوان نماینده آن خوشه در نظر می­گیریم و نماینده خوشه­ها را به عنوان نماینده­های آن کلاس در هنگام بازشناسی در نظر می­گیریم. در نتیجه هر کلاس بیش از یک نماینده دارد. با این روش نماینده­های مناسب برای هر کلاس انتخاب می­شود که در شکل  نشان داده شده‌اند.

شکل (12): نماینده های انتخاب شده و تعداد آنها

دیاگرام نحوه بازنمایی نشان داده شده است. در شکل نیز دیاگرام نحوه بازشناسی نشان داده شده است. همان طور که نشان داده شده است، ابتدا نماینده‌ها انتخاب می‌شوند و سپس دسته­بندی انجام می‌شود.

شکل (13): نحوه بازنمایی

شکل (14): نحوه بازشناسی

5- نتایج بازنمایی و بازشناسی

برای بازنمایی از دو روش که شرح داده شد، استفاده شده است. همچنین، برنامه های این دو روش در محیط نرم افزار متلب پیاده سازی شد و نتایج آن در ادامه توضیح داده می‌شود.

5-1- نتایج بازشناسی با توصیفگر موجک (روش اول)

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

شکل (15): دیاگرام دسته­بندی با موجک

اگر یک مرحله تجزیه کنیم، بردار ویژگی چهار تایی خواهد شد و نرخ بازشناسی کم خواهد شد. برای بزرگتر از پنج مرحله نیز نرخ بازشناسی کم خواهد شد. بیشترین نرخ بازشناسی با چهار مرحله به دست آمد که در نرخ بازشناسی به ازای موجک‌های مختلف نشان داده شده است. همچنین، بهترین پایه موجک که بالاترین نرخ بازشناسی را می‌دهد، دابیشی8 است.

جدول(2): نرخ بازشناسی با ویژگی انحراف معیار موجک در چهار مرحله تجزیه(به درصد).

5-2- نتایج بازشناسی با فوریه - ملین (روش دوم)

دیاگرام این روش در شکل  نشان داده شده است. در اینجا از توصیفگر  WFMTاستفاده شد. میزان نرخ بازشناسی برای موجک­های مختلف آزمایش شد و بهترین نتیجه با موجک خانواده دابیشی2 به دست آمد که نرخ بازشناسی به 81.5 درصد رسید. همان‌طور که مشاهده می‌شود، نرخ بازشناسی برای پایه­های موجک مختلف، متفاوت است. در جدول نرخ بازشناسی به ازای موجک‌های مختلف نشان داده شده است.

جدول (3): نرخ بازشناسی توصیفگر فوریه-ملین بر پایه­های موجکمختلف در سطح3 (به درصد).

6- بررسی نتایج

در Error! Not a valid bookmark self-reference.نتایج نرخ بازشناسی برای توصیفگرهای استفاده شده، نشان داده شده است. همچنین، در هر سه روش، دسته بندی به یک شکل انجام گرفته است.

7- خطاها

ماتریس سردرگمی نمایش خوبی از خطاها را نشان می‌دهد. در Error! Reference source not found. ماتریس سردرگمی برای توصیفگر موجک و در Error! Reference source not found. ماتریس سردرگمی برای توصیفگر فوریه-ملین نشان داده شده است.

گل­هایی که با هم اشتباه می­شوند در بخش زیر آورده شده­اند. سایر خطاها تا حدودی متفرقه هستند.

جدول (4) مقایسه نرخ بازشناسی

جدول (5) ماتریس سردرگمی برای توصیفگر موجک

جدول (6) ماتریس سردرگمی برای توصیفگر فوریه-ملین