خواندن خودکار نقشه‌های دستی فرش

فاتح, منصور; کبیر, احسان‌اله

تعداد نشریات	43
تعداد شماره‌ها	1,705
تعداد مقالات	13,969
تعداد مشاهده مقاله	33,511,023
تعداد دریافت فایل اصل مقاله	13,277,197

خواندن خودکار نقشه‌های دستی فرش

هوش محاسباتی در مهندسی برق

مقاله 2، دوره 3، شماره 2، شهریور 1391، صفحه 30-15 اصل مقاله (729.41 K)

نوع مقاله: مقاله پژوهشی فارسی

نویسندگان

منصور فاتح^* ¹؛ احسان‌اله کبیر²

¹دانشجوی دکتری، دانشکده مهندسی برق و کامپیوتر- دانشگاه تربیت مدرس- تهران- ایران

²- استاد، دانشکده مهندسی برق و کامپیوتر- دانشگاه تربیت مدرس- تهران- ایران

چکیده

چکیده: نقشه‌های فرش به دو دسته‌ چاپی و دستی تقسیم می‌شوند. مقالاتی در رابطه با خواندن خودکار نقشه‌های چاپی ارائه شده است. اما به علت سختی کار، تا کنون روشی برای خواندن خودکار نقشه‌های دستی فرش ارائه نشده است. به همین علت، موضوع این تحقیق جدید به‌شمار می‌رود. در این مقاله روشی برای خواندن خودکار نقشه‌های دستی ارائه شده است که از 4 مرحله‌ی کلی: کاهش رنگ اولیه، تک رنگ کردن هر خانه، بخش‌بندی به روش رشد ناحیه و کاهش رنگ نهایی با روش C-میانگین تشکیل شده است. این روش متناسب با کاربرد ارائه شده و به همین علت از دقت مناسبی برخوردار است. برای هشتاد قسمت از نقشه‌های مختلف، دقت الگوریتم حدود 95 درصد است. به عبارت دیگر، رنگ 95 در صد از خانه‌های نقشه‌ها به درستی تعیین شده است. در این مقاله سعی شده است تا الگوریتمی با دقت و سرعت مناسب، برای خواندن خودکار نقشه‌های دستی فرش ارائه شود. روش ارائه شده در این مقاله کاملاً خودکار نیست و تعداد رنگ‌های نقشه، باید توسط کاربر به عنوان ورودی به الگوریتم داده شود.

کلیدواژه‌ها

C-میانگین؛ خواندن خودکار؛ نقشه‌ دستی؛ کاهش رنگ؛ بخش‌بندی؛ C؛ میانگین

اصل مقاله

[1]

تصاویر با رنگ‌های واقعی به طور معمول شامل هزاران رنگ هستند و 24 بیت را به هر پیکسل اختصاص می‌دهند. نمایش، ذخیره‌سازی، انتقال و پردازش این تصاویر مشکل است. به این علت، کوانتیزاسیون (کاهش^{^[2]}) رنگ به عنوان مرحله‌ پیش‌پردازش تصاویر مختلف استفاده می‌شود[1]. کاربردهای کوانتیزاسیون رنگ در پردازش تصاویر و گرافیک، شامل: فشرده‎سازی[2]، ناحیه‌بندی[3]‌، آشکارسازی متن[4]، آنالیز بافت رنگ[5]، نقشاب‌زنی^{^[3]}[6] و بازیابی مبتنی بر محتواست[7]. در این تحقیق، هدف خواندن خودکار نقشه‌های دستی است که در بخش اولیه کار از روش‌های کوانتیزاسیون رنگ برای نزدیک شدن به رنگ‌های نهایی نقشه استفاده می‌شود. از این رو، در ادامه به اجمال، روش‌های کوانتیزاسیون رنگ را معرفی می‌کنیم.

فرآیند کوانتیزاسیون رنگ اساساً از دو مرحله‌: طراحی پالت(انتخاب مجموعه کوچکی از رنگ‌های تصویر اصلی) و نگاشت رنگ(جایگزین کردن رنگ‌های تصویر با رنگ‌های پالت) تشکیل شده است. در بیشتر کاربردها، پیکسل‌های 24 بیتی در تصویر اصلی، به 8 بیت یا کمتر کاهش می‌یابند[8].

روش‌های کوانتیزاسیون رنگ می‌توانند به دو گروه دسته‌بندی شوند: روش‌های مستقل از تصویر که یک پالت عمومی بدون در نظر گرفتن مشخصات تصویر هستند[9] و روش‌های وابسته به تصویر که یک پالت وفقی را مشخص می‌کنند. هدف این روش‌ها کاهش تعداد رنگ‌های تصویر با کمترین اعوجاج است[8]. بنابراین، کاهش رنگ باید به‌ گونه‌ای باشد که تفاوت بین تصویر اصلی و تصویر کوانتیزه شده تا حد امکان از لحاظ شهودی قابل درک نباشد[10].

بسیاری از روش‌های کوانتیزاسیون رنگ وابسته به تصویر در سه دهه‌ اخیر گسترش یافته‌اند. این روش‌ها می‌توانند به دو دسته‌ی روش‌های پیش خوشه‌یابی^{^[4]} و پس خوشه‌یابی^{^[5]} تقسیم شوند[1]. روش‌های پیش خوشه‌یابی اساساً مبتنی بر آنالیز آماری توزیع رنگ تصویر هستند. روش‌های پیش خوشه‌یابی افرازی با یک خوشه، شامل تمام پیکسل‌های تصویر آغاز می‌شوند. این خوشه‌ اولیه، تا K خوشه تقسیم می‌شود[8]. روش‌های تقسیم‌کننده شناخته شده، شامل برش میانه^{^[6]}[11]، Octree [12]، کمینه‌سازی واریانس^{^[7]}[13]، برش مرکزی^{^[8]}[14]، جداسازی دودویی[15] و الگوریتم rwm-cut [16] هستند. بیشتر کارهای اخیر در این رابطه را می‌توان در مراجع [17، 18، 19، 20 و 21]یافت. در دسته‌ دیگر، روش‌های پیش خوشه‌یابی تجمعی با N خوشه اولیه آغاز می‌شوند. این خوشه‌ها به هم می‌پیوندند تا در نهایت K خوشه نهایی تشکیل شوند. کارهای مربوط به این روش را می‌توان در مراجع [22، 23، 24، 25 و 26] یافت. روش‌های پس خوشه‌یابی، با یک پالت اولیه شروع می‌کنند و با تکرارهای پشت سر هم پالت اولیه را اصلاح می‌کنند تا میانگین مربعات خطا، MSE، کمینه شود. این تکنیک‌ها به قیمت افزایش زمان محاسبه، ممکن است ما را به جواب بهینه برسانند. البته، این روش‌ها وابسته به شرایط اولیه هستند. بنابراین، در عمل پالت اولیه با استفاده از تکنیک‌های پیش‌خوشه‌یابی ساخته و سپس با الگوریتم‌های خوشه‌یابی بهینه می‌شود[27]. الگوریتم‌های خوشه‌یابی منطبق بر کوانتیزاسیون رنگ شامل k-means[28، 29 و 30]، Minimax[31]، یادگیری رقابتی[32 و 33]، C-میانگین فازی[34 و 35]، BIRCH[36] و نگاشت خود سامان [10، 37 و 38] هستند.

برخی از روش‌های کاهش رنگ، اطلاعات رنگ و اطلاعات مکانی پیکسل ها را با هم در نظر می‏گیرند. این روش‌ها نسبت به روش‌های دیگر نتایج مناسبتری دارند. از جمله این روش‏ها می‏توان به الگوریتم کلونی مورچه ها و کاهش رنگ سازگار به کمک شبکه عصبی خود سامان اشاره کرد[10، 39 و 40]. علاوه‌بر روش‌های کاهش رنگ، برخی از روش‌های ناحیه‌بندی تصویر نیز اطلاعات رنگ و اطلاعات مکانی پیکسل ها را با هم در نظر می‏گیرند که این رویکرد در خواندن خودکار نقشه راهگشاست. غالباً در نقشه‌های قالی هر ناحیه دارای رنگ خاصی است. از این رو استفاده از روش‌های ناحیه‌بندی مبتنی بر رنگ، برای کاهش تعداد رنگ‌های موجود در هر ناحیه مفید است. این رویکرد، به علت استفاده‌ توام از اطلاعات رنگ و مکان پیکسل‌ها، دقت الگوریتم نهایی خواندن خودکار نقشه‌ فرش را افزایش می‌دهد. در ادامه، روش‌های ناحیه‌بندی به اجمال معرفی می‌شوند.

هدف اصلی ناحیه‌بندی تصویر، بخش‌بندی تصویر به ناحیه‌های گسسته‌ای است که از لحاظ دیداری متفاوتند. مشخصات محاسبه شده در این بخش‌ها همگن^{^[9]} هستند. البته، در این تحقیق این مشخصات شامل رنگ هستند. با این ناحیه‌بندی، آنالیز تصویر (پردازش، شناسایی و طبقه‌بندی شی) آسانتر می‌شود[41، 42 و 43]. ‌

ناپیوستگی و مشابهت پیکسل‌ها در ارتباط با پیکسل‌های همسایه دو مشخصه اصلی استفاده شده در بسیاری از روش‌های ناحیه‌بندی تصویر هستند. تکنیک‌های مبتنی بر لبه و مرز از مشخصه‌ ناپیوستگی پیکسل‌ها و تکنیک‌های مبتنی بر ناحیه از مشخصه‌ مشابهت پیکسل‌ها برای بخش‌بندی تصویر استفاده می‌کنند[44]. تکنیک جداسازی ناحیه بر اساس آستانه‌گذاری در هیستوگرام نیز از تکنیک‌های ساده‌ ناحیه‌بندی است[41]. تکنیک‌های پیوندی از دیگر روش‌های ناحیه‌بندی تصویر به شمار می‌روند که از تجمع تکنیک‌های مبتنی بر لبه و ناحیه مشتق شده‌اند[43].

از منظر استفاده از کاربر، سه راه برای تشکیل پالت رنگ وجود دارد که استفاده از آنها به نوع کاربرد بستگی دارد: 1- بهترین پالت رنگ بدون پیش فرض تعداد رنگ‌ها مشخص شود؛ 2- بهترین پالت رنگ با تعداد رنگ از پیش تعیین شده مشخص شود؛ 3- پالت با استفاده از رنگ‌های انتخابی کاربر مشخص شود. روش‌های زیادی برای کاهش یا کوانتیزه کردن رنگ در هر سه راه، پیشنهاد شده است[27 و 36]. در این مقاله بهترین پالت رنگ با تعداد رنگ از پیش تعیین شده مشخص می‌شود.

با توجه به اینکه خواندن نقشه‌ فرش، از جمله موضوعات نو به شمار می‌رود، در این مقاله ابتدا شرحی مختصر در رابطه با مبانی خواندن خودکار نقشه‌ فرش در بخش 2 و سپس مراحل آن توضیح داده می‌شود. سپس در بخش 3، روش پیشنهادی در این تحقیق متشکل از 4 مرحله، شرح داده می‌شود و در ادامه، در بخش 4 مشخصات مجموعه تصاویر استفاده شده، شرح داده می‌شود. در بخش 5 نتایج الگوریتم پیشنهادی بررسی و مقایسه‌ای با یکی از نرم‌افزارهای معروف انجام می‌شود. در بخش 6 نیز نتیجه‌گیری کلی ارائه می‌شود.

1- مبانی خواندن خودکار نقشه‌ فرش

نقشههای فرش به دو دسته تقسیم میشوند: الف) نقشههایی که طراحان به روش سنتی به صورت دستی ترسیم میکنند که به نقشههای دستی معروفند؛ ب) نقشههایی که طراحان به وسیله رایانه ترسیم میکنند که در چاپخانه یا به وسیله چاپگر چاپ میشوند و به نقشههای چاپی موسومند. در این تحقیق هدف خواندن خودکار نقشه‌های دستی است.

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

روش پیشنهادی برای خواندن خودکار نقشه‌ فرش شامل چهار مرحله است: 1- رنگ پیکسل‌های تصویر به تعداد رنگ‌های کمتر کاهش می‌یابند. در این مرحله تعداد رنگ‌های تصویر 3 تا 4 برابر تعداد رنگ‌های اصلی تصویر می‌شود.2- خطوط نقشه، شامل خطوط باریک و خطوط ضخیم مشخص می‌شوند و رنگ پیکسل‌های درون هر خانه‌ به یک رنگ، نگاشت می‌شوند. در واقع، آنچه در تمام نقشه‌های فرش مشاهده می‌شود، خط‌های راست افقی و عمودی هستند که از تلاقی آنها خانه‌هایی با اندازه‌های یکسان به وجود می‌آیند. اندازه خانه‌ها در نقشه‌های مختلف، با توجه به رجِ آن نقشه‌ها متفاوت است[45]. 3- بر اساس تکنیک مبتنی بر ناحیه، بخش‌بندی تصویر انجام می‌شود. 4- رنگ پیکسل‌های تصویر به تعداد رنگ‌های کمتر(30 تا 40 درصد بیشتر از رنگ‌های اصلی) و با دقت بالا کاهش یابند. در این مرحله از یافتن بهترین پالت با تعیین تعداد رنگ‌ها استفاده می‌شود. دیاگرام خواندن خودکار نقشه‌ فرش در شکل (1) نشان داده شده است.

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

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

شکل (1): چارت خواندن خودکار نقشه قالی

باید توجه داشت که تاکنون، نرم‌افزار مناسبی برای کاهش رنگ در نقشه‌های فرش ارائه نشده است. مرحله‌ کاهش رنگ توسط کاربر انجام می‌شود که وقت و هزینه زیادی می‌برد[27 و 46] که با روش ارائه شده در این تحقیق سعی در رفع این مشکل شده است. البته، در سال‌های اخیر برخی از الگوریتم‌ها، نظیر C-میانگین به منظور کاهش رنگ در نقشه‌های چاپی فرش ارائه شده است[27 و 45] که این روش‌ها در نقشه‌های دستی کارا نیستند که به علت شرایط متفاوت مساله است.

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

از لحاظ صنعتی، در بازار ایران، نرم‌افزارهای بوریا[46] و نقش‌ساز[47] مهمترین نرم‌افزارهای طراحی فرش هستند. این نرم‌افزارها، کاهش به 256 رنگ را بخوبی انجام می‌دهند ولی برای کاهش رنگ به تعداد کمتر، خطای زیادی دارند که باید کاربر آنها را برطرف کند.

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

همان گونه که در شکل (2) مشخص است، دو مشکل اصلی برای کاهش رنگ در نقشه‌های دستی وجود دارد که در ادامه به آنها اشاره می‌شود: 1- نقشه‌های دستی به طور یکنواخت رنگ نمی‌شوند و سیری یک رنگ خاص در نقاط مختلف نقشه متفاوت است. با توجه به این عدم یکنواختی برای هر رنگ، تخصیص رنگ مناسب به هر خانه دشوار است. 2- از طرف دیگر باید توجه داشت که برای انجام عملیات کاهش رنگ در نقشه، ابتدا باید نقشه اسکن شود و حاصل این اسکن نقشه‌ای با فراوانی رنگی 256 یا بیشتر خواهد بود. این فراوانی باید با دقت کامل، کاهش داده شود تا کمترین میزان خطا در نقشه‌ نهایی وجود داشته باشد. روش ارائه شده در این تحقیق سعی در رفع هر دو مشکل دارد.

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

شکل (2): تصویر قسمتی از یک نقشه فرش که با درجه تفکیک 200dpi اسکن شده است[48].

2- روش پیشنهادی

همان گونه که در بخش قبل اشاره شد، خواندن خودکار نقشه فرش شامل پنج مرحله‌ اصلی کاهش رنگ اولیه، یافتن خطوط نقشه، تک رنگ کردن هر خانه، بخش‌بندی و کاهش رنگ نهایی به کمک روش C-میانگین است. در این قسمت به شرح جزئیات هر یک از این مراحل (زیر بخش‌های خواندن خودکار نقشه فرش) می‌پردازیم.

2-1- کاهش رنگ اولیه نقشه

اولین مشکل کاهش رنگ در نقشه‌های قالی، اسکن تصویر با تعداد رنگ 256 یا بیشتر است. شایان ذکر است که اگر اسکن نقشه با تعداد رنگ کمتری انجام شود، بخشی از رنگ‌های نقشه، دچار خطا می‌شوند. برای اینکه در روش‌های کاهش رنگ، سرعت الگوریتم بالا برود و الگوریتم نهایی از دقت مناسبی برخوردار باشد، ابتدا تعداد رنگ‌های نقشه را با روشی مناسب کاهش می‌دهیم. برای پیدا نمودن روش مناسب، نیاز است الگوریتم‌های مختلف کاهش رنگ بر روی نقشه‌های مختلف اعمال شوند. در این بخش روش‌های کمینه‌سازی واریانس، C-میانگین و C-میانگین فازی ارزیابی شده‌اند.

ابتدا به بررسی نتایج روش کمینه‌سازی واریانس[13] برای کاهش رنگ می‌پردازیم. شایان ذکر است که این روش در مقایسه با روش‌های C-میانگین[28،29،30] و C-میانگین فازی[34،35] از سرعت بالاتری برخوردار است و در بخش‌هایی که دقت استفاده از روش‌های مختلف، تفاوت چندانی ندارد، استفاده از این روش ارجح است. در شکل (3) با الگوریتم حداقل کردن واریانس، تعداد رنگ‌های تصویر به 128، 64، 32 و 24 کاهش یافته‌اند.

همان گونه که در شکل (3) مشاهده می‌شود، در کاهش تعداد رنگ‌ها به 24 و 32، تصویر با تخریب مواجه شده است و برخی از قسمت‌ها به اشتباه رنگ شده‌اند(مکان‌هایی که با بیضی در شکل مشخص شده‌اند). تصویر اصلی شامل 10 رنگ سفید، مشکی، آبی کم‌رنگ، آبی پر رنگ، قهوه‌ای، قرمز، سبز، زرد، صورتی، نارنجی است و با کاهش رنگ به کمتر از چهار برابر رنگ‌های اصلی تصویر تخریب شده است.

128

شکل (3): کاهش تعداد رنگ‌های شکل (2) به 128، 64، 32 و 24 با روش حداقل کردن واریانس. تعداد رنگ‌های هر تصویر در زیر آن مشخص شده است.

در این قسمت به بررسی نتایج حاصل از روش C-میانگین فازی برای کاهش رنگ می‌پردازیم. در شکل (4) با الگوریتم C-میانگین فازی، تعداد رنگ‌های تصویر به 64 و 48 کاهش یافته‌اند. همان گونه که در شکل (4) مشاهده می‌شود، در کاهش رنگ به این روش، تصویر با تخریب مواجه شده است و برخی از قسمت‌ها به اشتباه رنگ شده‌اند(مکان‌هایی که با بیضی در شکل مشخص شده‌اند).

شکل (4): کاهش تعداد رنگ‌های شکل (2) به 64 و 48 با روش C- میانگین فازی

در این بخش به بررسی نتایج حاصل از روش C-میانگین برای کاهش رنگ می‌پردازیم. در شکل (5) با الگوریتم C-میانگین تعداد رنگ‌های تصویر به 128، 64، 32 و 24 کاهش یافته‌اند. همان گونه که در شکل (5) مشاهده می‌شود، در کاهش رنگ به 24 رنگ‌، تصویر با کمی تخریب مواجه شده است و برخی از قسمت‌ها به اشتباه رنگ شده‌اند(مکان‌هایی که با بیضی در شکل مشخص شده‌اند).

128

شکل (5): کاهش تعداد رنگ‌های شکل (2) به 128، 64، 32 و 24با روش C- میانگین

باید توجه داشت که الگوریتم حداقل کردن واریانس روشی سریع و الگوریتم C- میانگین روشی کند است. با توجه به این نکته، می‌توان ابتدا با روش‌های سریع مانند روش‌های جداسازی (روش حداقل نمودن واریانس) تعداد رنگ را به 6 الی 8 برابر رنگ‌های قالی کاهش داد و سپس در ادامه با روش C- میانگین تعداد رنگ‌ها معادل با 2 تا 3 برابر رنگ‌های قالی شوند. این الگوریتم برای هشتاد قطعه نقشه ارزیابی شد و نتایج مناسبی را به همراه داشت که نتایج در شکل (6) برای سه نقشه‌ مختلف نشان داده شده است. در این نقشه‌ها، ابتدا با الگوریتم کمینه‌سازی واریانس تعداد رنگ‌ها به 64 کاهش یافت و سپس با روش C- میانگین تعداد رنگ‌ها به 32 رسید که نتایج مناسبی را به همراه داشته است.

شکل (6): کاهش رنگ با روش ترکیبی حداقل کردن واریانس و C- میانگین. تصاویر سمت چپ، دارای تعداد رنگ میلیونی و تصاویر سمت چپ دارای 32 رنگ هستند.

2-2- تک رنگ کردن هر خانه

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

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

در این تحقیق، برای پیدا کردن خطوط باریک و ضخیم در نقشه‌های قالی از الگوریتم مبتنی بر هیستوگرام استفاده شده است[49، 50]. در شکل (7) نتیجه‌ حاصل از الگوریتم هیستوگرام برای تعیین خطوط نشان داده شده است.

شکل (7): تصویر قسمتی از نقشه فرش پس از یافتن خطوط باریک و ضخیم

روش‌های مختلفی برای تعیین نگاشت رنگ هر خانه وجود دارد. در کارهای قبلی، با استفاده از فیلتر میانه، رنگ مناسب برای هر خانه انتخاب می‌شد [45]. رنگ خطوط سیاه، بر روی رنگ نواحی اطراف آنها تاثیر میگذارد. از این رو، در این روش، رنگ هر خانه با توجه به مربعی که به اندازه 3 پیکسل از هر خط فاصله دارد، معین میشد. نتیجه‌ حاصل از این روش در شکل (8) نشان داده شده است.

شکل (8): تصویری معادل با شکل (7) پس از تک‌رنگ کردن خانه های نقشه با روش فیلتر میانه

همان گونه که در شکل (8) مشاهده می‌شود، برخی خانه‌ها اشتباه رنگ شده‌اند. همچنین، در این روش، برخی پیکسل‌های هر خانه کنار گذاشته می‌شوند و از اطلاعات آنها استفاده نمی‌شود. برای حل این مشکلات با استفاده از روش کمینه‌سازی واریانس، رنگ‌های هر خانه به 2 رنگ کاهش می‌یابند و سپس رنگی که دارای بیشترین فراوانی است، برای هر خانه انتخاب می‌شود. باید توجه داشت بسیار کم پیش می‌آید که بیش از 2 رنگ برای هر خانه وجود داشته باشد. از این رو، رنگ‌های هر خانه به 2 رنگ کاهش می‌یابند. در این روش، رنگ هر خانه با توجه به مربعی که به اندازه 3 پیکسل از هر خط فاصله دارد، معین میشود. نتیجه‌ اعمال الگوریتم حداقل نمودن واریانس برای نگاشت رنگ هر خانه به پیکسل در شکل (9) نشان داده شده است.

شکل (9): تصویری معادل با شکل (7) بعد از نگاشت هر خانه به یک پیکسل با کمک حداقل کردن واریانس

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

شکل (10): تصویری معادل با شکل (7) بعد از نگاشت هر خانه به یک پیکسل با کمک حداقل کردن واریانس و تعیین رنگ هر خانه با توجه به مربعی با فاصله 1 پیکسل از هر خط.

برای افزایش دقت الگوریتم در این مرحله، تغییراتی را اعمال کرده‎ایم. هر خانه‌ای که دارای رنگی با فراوانی بیش از 60 درصد بود، رنگ می‌شود و خانه‌های باقیمانده با دو نماینده رنگ معرفی می‌شوند. در شکل (11) خانه‌های سبز با دو نماینده رنگی به مرحله‌ بعد معرفی می‌شوند.

شکل (11): تعیین رنگ هر خانه با توجه به فراوانی رنگی بیش از 60% یک رنگ و معرفی دو نماینده برای خانه‌های دیگر(سبز رنگ)

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

(1)

در رابطه‌ بالا k=1,2 نشان دهندة نماینده‌های هر خانه، i=-1,0,1 و j=-1,0,1 موقعیت خانه‌های همسایه (البته (i,j)=(0,0) جزو نقاط نیست)، R, G, B مولفه‌های رنگی و dist معیار فاصله هستند که برای هر خانه dist شامل 16(با توجه به وجود 8 خانه همسایه و 2 نماینده برای هر خانه) عدد است.

تغییرات حاصل از این بخش در شکل (12) نشان داده شده است.

شکل (12): تعیین رنگ هر خانه با توجه به فراوانی رنگی بیش از 60% یک رنگ و معیار فاصله رنگی از خانه‌های همسایه

2-3- بخش‌بندی به روش رشد ناحیه

تکنیک‌های بخش‌بندی تصویر به سه گروه کلی تقسیم می‌شوند. این تکنیک‌ها شامل بخش‌بندی مبتنی بر آستانه‌گذاری، بخش‌بندی مبتنی بر لبه و بخش‌بندی مبتنی بر ناحیه هستند. در تمام این تکنیک‌ها سعی بر این است که بخش‌بندی با دقت بالایی انجام پذیرد، اما ممکن است مشکلاتی در بخش‌بندی ایجاد شود که این مشکلات شامل موارد زیر است[44]:

q ناحیه بخش‌بندی شده ممکن است کوچکتر یا بزرگتر از ناحیه‌ اصلی باشد.

q لبه‌های ناحیه بخش‌بندی شده ممکن است متصل نباشند.

q لبه‌های کاذب ایجاد و لبه‌های واقعی گم شوند.

در روش بخش‌بندی مبتنی بر آستانه، مقدار آستانه به دو صورت کلی و موضعی اعمال می‌شود. به علت دشواری تعیین مقدار آستانه دقیق، این روش از دقت بالایی برخوردار نیست، اما در عوض سرعت بالایی دارد.

تکنیک‌های بخش‌بندی مبتنی بر مرز، از دقت مناسبی برای بخش‌بندی برخوردارند. در این روش‌ها، تعداد اشیای جذاب در تصویر معادل تعداد مرزهای بسته فرض می‌شوند و بخش‌بندی تصویر با این فرض انجام می‌پذیرد. در این تکنیک‌ها، از الگوریتم‌های گرادیان و لاپلاسین برای تشخیص مرز استفاده می‌شود[44].

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

الگوریتم رشد ناحیه در این تحقیق مطابق با شکل (13) طراحی شده است. همان گونه که در شکل (13) مشاهده می‌شود، در بخشی از الگوریتم، فاصله‌ رنگی هر پیکسل از پیکسل‌های همسایه، با مقدار آستانه مقایسه می‌شود و در صورتی که این فاصله از مقدار آستانه کمتر بود، برچسب یکسان به پیکسل‌ها اختصاص می‌یابد. این فاصله در دستگاه RGB همانند رابطه 1 محاسبه می‌شود. در این بخش دو سؤال مهم وجود دارد:

1- اندازه همسایگی مناسب چقدر است؟

2- مقدار آستانه چقدر است؟

در این تحقیق به‌ازای هر پیکسل، پنجره‌ مربعی 5*5 با مرکز پیکسل مربوطه لحاظ می‌شود که پیکسل‌های موجود در این پنجره به عنوان پیکسل‌های همسایه شناخته می‌شوند.

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

(2)

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

پس از برچسب‌زنی تمام پیکسل‌ها، پالت نهایی با توجه به مقدار میانگین رنگی تمام پیکسل‌های با برچسب یکسان، تعیین می‌شود و سپس نگاشت رنگ‌های پالت به رنگ هر پیکسل صورت می‌پذیرد.

شکل (13): چارت مربوط به الگوریتم رشد ناحیه

در شکل (14) نتیجه اعمال الگوریتم رشد ناحیه، در یکی از نقشه‌های فرش نشان داده شده است.

شکل (14): تصویر مربوط به اعمال الگوریتم رشد ناحیه به شکل (11).

2-4- کاهش رنگ به روش C- میانگین

در انتها با روش C-میانگین کاهش رنگ نهایی در تصویر انجام می‌شود. در این روش تعداد رنگ‌های نهایی 40 تا 50 درصد بیشتر از تعداد رنگ‌های اصلی هستند. باید توجه داشت که هنگام عملیات نگاشت خانه به پیکسل و کاهش رنگ در نقشه‌های دستی، رنگ‌هایی ایجاد می‌شوند که دارای تفاوت رنگی زیادی از رنگ‌های اصلی هستند. در صورت اعمال الگوریتم کاهش رنگ با تعداد رنگ نهایی معادل با رنگ‌های اصلی، این رنگ‌ها هنگام عملیات کاهش رنگ از میان نمی‌روند و برخی رنگ‌های اصلی تصویر حذف می‌شوند. از این رو، تعداد رنگ‌های نهایی 40 تا 50 درصد بیشتر از تعداد رنگ‌های اصلی در نظر گرفته می‌شوند تا رنگ‌های اصلی حذف نشوند.

در شکل (15) نتیجه اعمال الگوریتم C-میانگین، در یکی از نقشه‌های فرش نشان داده شده است. این نقشه دارای 10 رنگ اصلی است که به علت جلوگیری از ایجاد خطای ناشی کاهش رنگ، تعداد رنگ‌های اصلی 15 در نظر گرفته شده‌اند.

شکل (15): تصویر مربوط به اعمال الگوریتم C-میانگین به شکل (14).

3- داده‌های مورد استفاده در این تحقیق

در این بخش به شرح مجموعه تصاویر استفاده شده در این تحقیق می‌پردازیم. مجموعه‌ تصاویر نقشه‌های فرش، به صورت آزاد وجود ندارد و مجموعه تصاویر موجود با چندین نقشه‌ فرش، با مبالغی بالا به فروش می‌رسند. از این رو، مجموعه تصاویر مربوط به این تحقیق، توسط اینجانب و محققان قبلی [45] به مرور زمان و با مذاکره با استادان فرش و شرکت‌های مربوطه[46،47] تهیه شده است. مجموعه تصاویر تهیه شده شامل 80 قطعه نقشه از 10 نقشه‌ فرش متفاوت است. نقشه‌های استفاده شده در این تحقیق، شامل نقشه‌هایی از اقلیم کرمان، اصفهان، تبریز، کاشان و قم هستند. خصوصیات قطعات نقشه‌ استفاده شده در این تحقیق، شامل موارد زیر است:

اندازه‌ این قطعه‌ها بین 25*25 تا 45*45 خانه است.
این نقشه‌ها با درجه تفکیک dpi300 اسکن شده‌اند.
فضای رنگی این نقشه‌ها RGB است.
تعداد رنگ‌های موجود در این قطعات بین 5 تا 15 رنگ هستند.

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

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

4- نتایج پیاده‌سازی

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

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

برای کاهش رنگ در تصویر، الگوریتم‌های متنوعی وجود دارد که کد برخی از این الگوریتم‌ها یا نرم‌افزار مبتنی‌بر برخی از این الگوریتم‌ها به صورت رایگان در سایت‌های مختلف اینترنتی قابل دسترسی است. نرم‌افزار Layer Pilot نرم‌افزاری مناسب برای کاهش رنگ است و از آنجا که از وجود کاربر بهره می‌برد، نتایج مناسبی بدست می‌دهد. در ادامه، به بررسی نتایج کاهش رنگ در نقشه‌های فرش با این نرم‌افزار پرداخته می‌شود. شمای کلی این نرم‌افزار در شکل (17) نشان داده شده است[51]. البته، در مرجع [27] روشی برای خواندن خودکار نقشه‌های چاپی فرش ارائه شده است. این روش را نیز بر روی نقشه‌های دستی اعمال نمودیم که نتایج مطلوبی نداشت. به همین علت، نرم‌افزار Layer Pilot با الگوریتم پیشنهادی در این مقاله مقایسه می‌شود. نتیجه اعمال روش مرجع [27] بر روی یکی از نقشه‌ها در شکل (18) نشان داده شده است.

الف

شکل (16): الف) تصویر قطعه‌ای از نقشه فرش دستی؛ ب) تصویر حاصل از کاهش رنگ اولیه؛ ج) تصویر حاصل از مرحله‌ نگاشت هر خانه به یک پیکسل؛ د) تصویر حاصل از اعمال الگوریتم رشد ناحیه؛ ه) تصویر نهایی حاصل از الگوریتم C- میانگین با 13 رنگ نهایی

‌

شکل (17): نمای کلی از نرم‌افزار Layer Pilot

شکل (18): نتایج حاصل از اعمال الگوریتم مرجع [27] برای کاهش رنگ در نقشه‌ دستی فرش.

نرم‌افزار Layer Pilot از اطلاعات مکانی پیکسل‌ها استفاده نمی‌کند و به دخالت کاربر نیاز دارد. در واقع، برای تشکیل پالت اولیه رنگ، کاربر بر روی نقاط مختلف تصویر با رنگ‌های مختلف کلیک می‌کند و پالت اولیه رنگ را تشکیل می‌دهد و سپس نرم‌افزار تعداد رنگ‌های تصویر را کاهش می‌دهد. تعداد رنگ‌های داده شده به نرم‌افزار توسط کاربر انتخاب و سعی می‌شود که رنگ‌های اصلی نقشه باشد. نتایج حاصل از اعمال نرم‌افزار Layer Pilot برای کاهش رنگ نقشه‌های فرش، در شکل (19) نشان داده شده است. برای تشکیل پالت اولیه در این تصاویر برای هر رنگ بر روی دو نقطه از تصویر کلیک شده است تا دقت در تشکیل پالت اولیه بالا رود. همان گونه که در شکل (19) نشان داده شده است، پس از اجرای این نرم‌افزار، خطا در برخی از رنگ‌های پیکسل‌ها وجود دارد که مسأله‌ای نامطلوب به شمار می‌رود. دقت حاصل با نرم‌افزار Layer Pilot برای نقشه‌های موجود در پایگاه داده، کمتر از 85% است.

با مقایسه الگوریتم پیشنهادی در این تحقیق با نرم‌افزار Layer Pilot، مشاهده می‌شود که کاهش رنگ نقشه‌های فرش با الگوریتم پیشنهادی در این تحقیق، دارای دقت بالاتری است. ارائه‌ روشی متناسب با کاربرد، از مهمترین دلایل وجود دقت بالاتر برای روش پیشنهادی است. بیشتر الگوریتم‌های کاهش رنگ بدون توجه به کاربرد کاهش رنگ را انجام می‌دهند که در صورت نیاز به دقت بالا، امری نامطلوب به‌شمار می‌رود. روش پیشنهادی در این تحقیق متناسب با کاربرد کاهش رنگ در نقشه‌های فرش، ارائه شده که به شکل مؤثری دقت را افزایش می‌دهد.

همچنین، از دیگر مزیت‌های روش پیشنهادی استفاده از کاربر تنها در مشخص کردن تعداد رنگ است، در صورتی که در نرم‌افزار Layer Pilot هم برای تعداد رنگ و هم برای تشکیل پالت نهایی از کاربر کمک خواسته می‌شود. در واقع روش پیشنهادی در این تحقیق تقریباً خودکار است که مزیتی مهم به‌شمار می‌رود.

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

شکل (19): نتایج حاصل از نرم‌افزار Layer Pilot برای کاهش رنگ در نقشه‌ دستی فرش.

5- نتیجه‌گیری

با بررسی نتایج حاصل از روش پیشنهادی خواندن خودکار نقشه فرش، بر روی 30 نقشه دستی برچسب خورده، دقتی معادل با حدود 95% حاصل شد که دقت مناسبی است. در این تحقیق، هدف خواندن خودکار نقشه فرش بود تا کاربر زمان کمتری را برای ایجاد نقشه‌ دیجیتالی نهایی نماید. همچنین، این کار با دقت بالایی انجام می‌پذیرد که در مواردی حتی از دقت ایجاد نقشه‌ دیجیتالی توسط کاربر نیز بیشتر است.

خواندن خودکار نقشه فرش از مراحل مختلفی تشکیل شده است که استفاده نکردن از روشی مناسب در هر بخش دقت الگوریتم را به شدت پایین می‌آورد. از این رو در هر بخش از الگوریتم سعی شده است تا روشی با دقت بالا استفاده شود. الگوریتم‌های استفاده شده در هر بخش، با توجه به مساله طراحی شده‌اند و از این رو الگوریتم نهایی، دارای دقت بالایی است. همچنین، در بخش کاهش رنگ نیز، روش پیشنهادی متناسب با کاربرد طراحی شده که در مقایسه با دیگر روش‌های کاهش رنگ از دقت بالایی برخوردار است. ارزشمندی این روش به لحاظ استفاده محدود از کاربر است (تنها در تعیین تعداد رنگ نهایی). در روشهای دیگر کاهش رنگ[20و5،6،7،11،12]، استفاده از کاربر به عنوان یکی از موارد پایهای برای الگوریتم به شمار میرود، و بدون استفاده از کاربر دقت نهایی الگوریتم پایین است؛ حال آنکه با ارائه روش پیشنهادی در این مقاله، علاوه بر استفاده محدود از کاربر دقت الگوریتم بالاست. در روش پیشنهادی، از پالت تطبیقی استفاده می‌شود و جستجو برای پیدا کردن بهترین مجموعه رنگ انجام می‌پذیرد. در این روش، تعداد رنگ تصویر ورودی توسط کاربر مشخص و تعداد رنگ نهایی با توجه به این مقدار، مشخص میشود.

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

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

[1]تاریخ ارسال مقاله : 22/3/1391

تاریخ پذیرش مقاله : 8/8/1391

نام نویسنده مسئول : منصور فاتح

نشانی نویسنده مسئول : ایران– تهران – دانشگاه تربیت مدرس–

دانشکده مهندسی برق و کامپیوتر

[2] Reduction

[3] Watermarking

[4] Preclustering

[5] Postclustering

[6] Median-cut algorithm

[7] Variance minimization

[8] Center-cut algorithm

[9] homogeneous

مراجع

–210, 1997.

[26] Brun, L., Mokhtari, M., "Two High Speed Color Quantization Algorithms", in: Proc. of the 1st Int. Conf. on Color in Graphics and Image Processing, 116–121, 2000.

[27] ایزدی پور، ا.، کبیر، ا.ا.، " ارائه روشی برای خواندن خودکار نقشه چاپی فرش و مقایسه آن با روش خوشه‌یابی میانگینC-"، نشریه مهندسی برق و مهندسی کامپیوتر ایران ، 8(1): 56-48، بهار سال 1389.

[28] Huang, Y.-L., Chang, R.-F., "A Fast Finite-State Algorithm for Generating RGB Palettes of Color Quantized Images", Journal of Information Science and Engineering Vol. 20, No. 4, pp. 771–782, 2004.

[29] Hu, Y.-C., Lee, M.-G., "K-means Based Color Palette Design Scheme with the Use of Stable Flags", Journal of Electronic Imaging Vol. 16, No. 3, pp. 033003, 2007.

[30] Hu, Y.-C., Su, B.-H., "Accelerated K-means Clustering Algorithm for Colour Image Quantization", Imaging Science Journal Vol. 56, No. 1, pp. 29–40, 2008.

[31] Xiang, Z., "Color Image Quantization by Minimizing the Maximum Intercluster Distance", ACM Trans. On Graphics Vol. 16, No, 3, pp. 260–276, 1997.

[32] Celebi, M. E., "An Eﬀective Color Quantization Method Based on the Competitive Learning Paradigm", in:Proc. of the 2009 Int. Conf. on Image Processing, Computer Vision, and Pattern Recognition, Vol. 2, pp. 876–880, 2009.

[33] Celebi, M. E., Schaefer, G., "Neural Gas Clustering for Color Reduction", in: Proc. of the 2010 Int. Conf. on Image Processing,Computer Vision, and Pattern Recognition, pp. 429 – 432, 2010.

[34] Ozdemir, D., Akarun, L., "Fuzzy Algorithm for Color Quantization of Images", Pattern Recognition Vol. 35, No. 8, pp. 1785–1791, 2002.

[35] Schaefer, G., Zhou, H., "Fuzzy Clustering for Colour Reduction in Images", Telecommunication Systems Vol. 40, (1-2), pp. 17–25, 2009.

[36] Bing, Z., Junyi, S., Qinke, P., "An Adjustable Algorithm for Color Quantization", Pattern Recognition Letters Vol. 25, No. 16, pp. 1787–1797, 2004.

[37] Dekker, A., "Kohonen Neural Networks for Optimal Colour Quantization", Network: Computation in Neural Systems Vol. 5, No. 3, pp. 351–367, 1994.

[38] Chang, C.-H., Xu, P., Xiao, R., Srikanthan, T.,"New Adaptive Color Quantization Method Based on Self-Organizing Maps", IEEE Trans. on Neural Networks Vol. 16, No. 1, pp. 237–249, 2005.

[39] Atsalakis, A., Papamarkos, N.,"Color reduction and estimation of the number of dominant colors by using a self-growing and self-organized neural gas", Engineering Applications of Artificial Intelligence Vol. 19, pp. 769–786, 2006.

[40] Ghanbarian, A. T., Kabir, E., Charkari, N. Mp., "Color reduction based on ant colony", Pattern Recognition Letters Vol. 28, pp. 1383–1390, 2007.

[41] FREIXENET, J., MUNOZ, X., RABA, D., MARTI, J., CUFI, X., "Yet Another Survey on Image Segmentation: Region and Boundary Information Integration", Springer, pp. 408–422, 2002.

[42] LUCCHESE, L., MITRA, S. K.,"Colour image segmentation: A state-of-the-art survey", INSA-A, Vol. 67, Nol. 2, pp. 207 – 221, 2001.

[43] WANG, Y., GUO, Q., ZHU, Y.,"Medical image segmentation based on deformable models and its applications", Springer, pp. 209-260, 2007.

[44] Zuva, T., Olugbara, O. O., Ojo, S. O., Ngwira, S. M.,"Image Segmentation, Available Techniques, Developments and Open Issues", Journal on Image Processing and Computer Vision Vol. 2, No. 3, pp. 20-29, March 2011.

[45] ایزدی پور، احمد، کبیر، احسان اله،"شناسایی خودکار خطوط نقشه فرش"، اولین کنگره مشترک سیستم‌های فازی و هوشمند،7، 86، مشهد مقدس،7 شهریور 1386.

[46]بوریا (www.booria.com/carpetdesigner.htm).

[47]مرکز کنترل کامپیوتر ایران، نرم‌افزار نقش‌ساز (www.centraltouch.com).

[48] شرکت سهامی فرش ایران (www.irancarpet.ir).

[49] Zheng, Y., Li, H., Doermann, D.,"A Model-based Line Detection Algorithm in Documents", Proceedings of the Seventh International Conference on Document Analysis and Recognition, ICDAR 2003.

[50] Sun, J., Zhou, F., Zhou, J.," A new fast line detection algorithm", Systems and Control in Aerospace and Astronautics, pp. 830 –833, 0-7803-9395-3, 2006.

[51] http://www.colorpilot.com/layer.html

آمار

تعداد مشاهده مقاله: 1,622

تعداد دریافت فایل اصل مقاله: 703

سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

خواندن خودکار نقشه‌های دستی فرش

1- مبانی خواندن خودکار نقشه‌ فرش

2- روش پیشنهادی

2-1- کاهش رنگ اولیه نقشه

2-2- تک رنگ کردن هر خانه

2-3- بخش‌بندی به روش رشد ناحیه

2-4- کاهش رنگ به روش C- میانگین

3- داده‌های مورد استفاده در این تحقیق

4- نتایج پیاده‌سازی

5- نتیجه‌گیری