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

امیدوارم که مفید باشد

 

لگچرهای کتاب آقای گنزالس

تعداد فایل : 17 عدد

فرمت: pdf

زبان : انگلیسی

نویسنده: گنزالس

پسورد فایل: behsanandish.com

دانلود

 

______________________________________

 

مفاهیم پایه پردازش تصویر دانشگاه شهید بهشتی

تعداد صفحه: 109 صفحه

فرمت: pdf

زبان : فارسی

نویسنده: ‫احمد محمودی ازناوه‬

پسورد فایل: behsanandish.com

دانلود

فهرست مطالب:
‫• مقدمه اي بر پردازش تصوير‬
‫– كاربردهاي پردازش تصوير‬
‫• ساختار تصوير ديجيتال‬
‫• تصاوير رنگي‬
‫• حساسيت چشم‬
‫– تباين‬
‫• حسگرهاي تصوير‬
‫• آشنايي با ‪Matlab‬‬
‫• آشنايي با فضارنگها‬

 

______________________________________

 

 

واژه نامه پردازش سیگنال و پردازش تصویر

واژه نامه پردازش سیگنال و پردازش تصویر حاوی لغات و اصطلاحات تخصصی استفاده شده در زمینه پردازش تصویر و پردازش سیگنال است.

نویسنده: خانم شهره کسائی

دانشگاه صنعتی شریف

تعداد صفحات: 20

 

پسورد فایل: behsanandish.com

دانلود

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

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

الگوریتم‌های DSP مدت زیادی است که در کامپیوترهای استاندارد همه منظوره، یا بر روی پردازش‌گرهای معروف به پردازشگرهای سیگنال دیجیتال (DSP) یا با استفاده از سخت‌افزارهای خاص مثلمدارهای مجتمع با کاربرد خاص (ASIC) اجرا می‌شوند. امروزه تکنولوژی‌های دیگری نیز برای پردازش سیگنال دیجیتال مورد استفاده قرار می‌گیرند که شامل میکروپروسسورهای چندمنظوره قدرتمند،اف‌پی‌جی‌ای (FPGA)، کنترل‌کننده سیگنال دیجیتال (بیشتر برای کاربردهای صنعتی مثل کنترل موتور) هستند.

حوزه‌های DSP

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

نمونه‌برداری از سیگنال

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

نمونه‌برداری معمولاً در دو مرحله انجام می‌شود : گسسته‌سازی و مدرج کردن. در مرحله گسسته‌سازی، فضای سیگنال (فضایی که سیگنال در آن وجود دارد) به کلاس‌هاس هم‌ارز افراز می‌شود و مدرج کردن نیز با جایگزینی سیگنال اصلی با سیگنال متناظر در کلاس‌های هم‌ارز انجام می‌پذیرد.

در مرحله مدرج کردن، مقادیر سیگنال نماینده (به انگلیسی: Representative Signal) توسط مقادیر زیر مجموعه یک مجموعه متناهی تقریب زده می‌شوند.

قضیه نمونه‌برداری نایکوئیست-شنون بیان می‌کند که سیگنال را می‌توان از روی سیگنال نمونه‌برداری شده به طور دقیق بازسازی کرد، اگر فرکانس نمونه‌برداری بزرگتر از دو برابر بالاترین مؤلفه فرکانسی سیگنال باشد. در عمل، غالباً فرکانس نمونه‌برداری را بزرگتر از دو برابر پهنای باند لازم در نظر می‌گیرند.

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

مفهوم حوزه‌ی زمان و فرکانس

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

  • “فیلتر خطی”: یک تبدیل خطی است که بر روی نمونه های ورودی اعمال میشود؛ سایر فیلترها “غیرخطی” هستند. فیلترهای خطی از قاعده ی جمع آثار پیروی میکنند؛ به این معنی که اگر یک سیگنال ورودی، ترکیب وزنداری از سیگنال های مختلف باشد، سیگنال خروجی از ترکیب خطی خروجی های همان سیگنال ها، با وزنهای مشابه ورودی، حاصل میشود.
  • “فیلتر علی”: فیلتر علی فقط از نمونه های قبلی در سیگنال های ورودی و خروجی استفاده میکند. اما، در فیلترهای “غیرعلی”، نمونه های آینده ی ورودی نیز به کار گرفته می شوند. با اضافه کردن تأخیر به یک فیلتر غیرعلی میتوان آنرا به یک فیلتر علی تبدیل نمود.
  • “فیلتر غیر متغیر با زمان”: ویژگی های این فیلتر با زمان تغییر نمیکند. اما، فیلترهایی مانند فیلتر تطبیقی، با زمان تغییر میکنند.
  • “فیلتر پایدار”: خروجی یک فیلتر پایدار با گذشت زمان به یک مقدار ثابت همگرا میشود یا در محدوده ی متناهی باقی می ماند. اما، یک فیلتر “ناپایدار” در پاسخ به یک ورودی محدود (متناهی) یا حتی صفر، ممکن است منجر به تولید خروجی هایی نامتنهای شود.
  • “فیلتر با پاسخ ضربه ی محدود (FIR)”: این فیلتر فقط از نمونه های سیگنال ورودی استفاده میکند، اما، فیلتر با پاسخ ضربه ی نامحدود (IIR) علاوه بر نمونه های ورودی، از نمونه های گذشته ی خروجی نیز استفاده میکند. فیلترهای FIR همواره پایدار هستند، اما، فیلترهای IIR ممکن است ناپایدار شوند.

فیلترها را میتوان به روشهای مختلفی بازنمایی کرد: 1- با استفاده از دیاگرام بلوکی برای نشان دادن مراحل مختلف الگوریتم به منظور ایجاد یک دستورالعمل برای پیاده سازی سخت افزاری فیلتر. 2- با توصیف فیلتر با استفاده از معادلات تفاضلی یا به کمک مجموعه ی قطب ها و صفرهای سیستم. برای فیلترهای FIR، میتوان از پاسخ های ضربه یا پله نیز برای توصیف فیلتر استفاده کرد.

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

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

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

فیلترینگ سیگنال، به ویژه در کابردهای غیر زمان واقعی (non- real time)،میتواند با انتقال سیگنال به حوزه ی فرکانس و اعمال یک فیلتر مناسب بر آن و سپس برگرداندن سیگنال حاصل به حوزه ی زمان انجام شود. این عملیات، سریع بوده (زمان اجرا متناسب است با (n log n) ) و می توان فیلتر را با تقریب خوبی به شکلهای مختلف طراحی نمود.

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

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

بسط فوریه و مفهوم حوزه زمان (منحنی قرمز) و فرکانس (منحنی آبی).

تحلیل در حوزه {\displaystyle Z\,}

در حالی که فیلترهای آنالوگ معمولاً در صفحه{\displaystyle s\,} تحلیل می‌شوند، فیلترهای دیجیتال در صفحه {\displaystyle z\,} یا حوزه دیجیتال و با استفاده از تبدیل {\displaystyle Z\,} تحلیل می‌شوند.

بسیاری از فیلترها را می‌توان در حوزه{\displaystyle Z\,} (یک فرامجموعه از اعداد مختلط در حوزه فرکانس) توسط تابع تبدیلشان تحلیل کرد. یک فیلتر می‌تواند توسط مجموعه مشخصه‌اش شامل صفرها و قطب‌ها در حوزه{\displaystyle z\,} تحلیل شود.

کاربردها

بیشترین کاربردهای DSP شامل پردازش سیگنال صوتی، فشرده‌سازی داده‌های صوتی، پردازش تصویر دیجیتال، فشرده‌سازی ویدیو، پردازش صدا، تشخیص صدا، ارتباط دیجیتال، رادار، سونار، زلزله‌شناسی و داروسازی است. مثال‌های خاص شامل فشرده‌سازی صحبت و انتقال در تلفن همراه، هم‌نواسازی مطابق اتاق برای صدا در کاربردهای شباهت زیاد به اصل و تقویت صدا، پیش بینی وضع هوا، پیش‌بینی اقتصادی، پردازش داده زلزله، تحلیل و کنترل روال‌های صنعتی، انیمیشن‌های تولید شده توسط رایانه در فیلم‌ها، عکس‌برداری پزشکی مثل پویش‌های CAT و MRI، فشرده‌سازیMP3، دستکاری تصویر، هم‌نواسازی و هم‌گذری بلندگوهای با کیفیت بالا، و افکت صوتی برای تقویت‌کننده (الکترونیک) گیتار برقی است.

منبع

 

تاریخچه

(آنالیز موجک) ایده ی نمایش یک تابع برحسب مجموعه ی کاملی از توابع اولین بار توسط ژوزف فوریه، ریاضیدان و فیزیکدان بین سال های ۱۸۰۶-۱۸۰۲ طی رساله ای در آکادمی علوم راجع به انتشار حرارت، برای نمایش توابع بکار گرفته شد. در واقع برای آنکه یک تابع(f(x به شیوه ای ساده و فشرده نمایش داده شود فوریه اساسا ثابت کرد که می توان از محور هایی استفاده کرد که بکمک مجموعه ایی نامتناهی از توابع سینوس وار ساخته می شوند. بعبارت دیگر فوریه نشان داد که یک تابع (f(x را می توان بوسیله ی حاصل جمع بی نهایت تابع سینوسی و کسینوسی به شکل (sin(ax و (cos(ax نمایش داد. پایه های فوریه بصورت ابزار هایی اساسی، با کاربردهای فوق العاده متواتر در علوم، در آمده اند، زیرا برای نمایش انواع متعددی از توابع و در نتیجه کمین های فیزیکی فراوان بکار می روند.
با گذشت زمان ضعف پایه های فوریه نمایان شد مثلا دانشمندان پی بردند پایه های فوریه و نمایش توابع سینوس وار در مورد سیگنال های پیچیده نظری تصاویر، نه تنها ایده آل نیستند بلکه از شرایط مطلوب دورند، بعنوان مثال به شکل کارآمدی قادر به نمایش ساختارهای گذرا نظیر مرزهای موجود در تصاویر نیستند. همچین آنها متوجه شدند تبدیل فوریه فقط برای توابع پایه مورد استفاده قرار می گیرد و برای توابع غیر پایه کار آمد نیست.(البته در سال ۱۹۴۶ با استفاده از توابع پنجره ای، که منجر به تبدیل فوریه ی پنجره ای شداین مشکل حل شد.)
در سال ۱۹۰۹ هار اولین کسی بود که به موجک ها اشاره کرد. در سال های ۱۹۳۰ ریاضیدانان به قصد تحلیل ساختارهای تکین موضوعی به فکر اصلاح پایه های فوریه افتادند. و بعد از آن در سال ۱۹۷۰ یک ژئوفیزیکدان فرانسوی به نام ژان مورله متوجه شد که پایه های فوریه بهترین ابزار ممکن در اکتشافات زیر زمین نیستند، این موضوع در آزمایشگاهی متعلق به الف آکیلن منجر به یکی از اکتشافات تبدیل به موجک ها گردید.
در سال ۱۹۸۰ ایومیر ریاضیدان فرانسوی، نخستین پایه های موجکی متعامد را کشف کرد(تعامد نوعی از ویژگی ها را بیان می کند که موجب تسهیلات فراوانی در استدلال و محاسبه می شود، پایه های فوریه نیز متعامدند.) در همین سال ها مورله مفهوم موجک و تبدیل موجک را بعنوان یک ابزار برای آنالیز سیگنال زمین لزره وارد کرد و گراسمن فیزیکدان نظری فرانسه نیز فرمول وارونی را برای تبدیل موجک بدست آورد.
در سال ۱۹۷۶ میرو و مالت از پایه های موجک متعامد توانسنتد آنالیز چند تفکیکی را بسازند و مالت تجزیه موجک ها و الگوریتم های بازسازی را با بکار بردن آنالیز چند تفکیکی بوجود آورد. در سال ۱۹۹۰ مورنزی همراه با آنتوان موجک ها را به دو بعد و سپس به فضاهایی با ابعد دیگر گسترش دادند و بدین ترتیب بود که آنالیز موجکی پایه گذاری گردید.

 آشنایی

آنالیز موجک (Wavelet Analysis) یکی از دستاوردهای نسبتا جدید و هیجان انگیز ریاضیات محض که مبتنی بر چندین دهه پژوهش در آنالیز همساز است، امروزه کاربردهای مهمی در بسیاری از رشته های علوم و مهندسی یافته و امکانات جدیدی برای درک جنبه های ریاضی آن و نیز افزایش کاربردهایش فراهم شده است.
در آنالیز موجک هم مانند آنالیز فوریه با بسط تابع ها سروکار داریم ولی این بسط برحسب «موجک ها» انجام می شود.
موجک تابع مشخص مفروضی با میانگین صفر است و بسط برحسب انتقالها و اتساعهای این تابع انجام می گیرد، بر خلاف چند جمله ای های مثلثاتی، موجک ها در فضا بصورت موضعی بررسی می شوند و به این ترتیب ارتباط نزدیکتری بین بعضی توابع و ضرایب آن ها امکان پذیر می شود و پایداری عددی بیشتری در باز سازی و محاسبات فراهم می گردد. هر کاربردی را که مبتنی بر تبدیل سریع فوریه است می توان با استفاده از موجک ها فومول بندی کرد و اطلاعات فضایی (یا زمانی) موضعی بیشتری بدست آورد. بطور کلی، این موضوع بر پردازش سیگنال و تصویر و الگوریتم های عددی سریع برای محاسبه ی عملگرهای انتگرالی اثر می گذارد.
آنالیز موجک حاصل ۵۰ سال کار ریاضی (نظریه ی لیتلوود – پیلی و کالدرون – زیگموند) است که طی آن، با توجه به مشکلاتی که در پاسخ دادن به ساده ترین پرسش های مربوط به تبدیل فوریه وجود داشت، جانشینهای انعطاف پذیر ساده تری از طریق آنالیز همساز ارائه شدند. مستقل از این نظریه که درون ریاضیات محض جای دارد، صورتهای مختلفی از این رهیافت چند مقیاسی (multi Scale) را در طی دهه ی گذشته در پردازش تصویر، آکوستیک، کدگذاری(به شکل فیلترهای آیینه ای متعامد و الگوریتمهای هرمی)، و استخراج نفت دیده ایم.

 کاربردها

آنالیز موجک همراه با تبدیل سریع فوریه در تحلیل سیگنالهای گذرایی که سریعا تغییر می کنند، صدا و سیگنالهای صوتی، جریان های الکتریکی در مغز، صداهای زیر آبی ضربه ای و داده های طیف نمایی NMR، و در کنترل نیروگاههای برق از طریق صفحه ی نمایش کامپیوتر بکار رفته است. و نیز بعنوان ابزاری علمی، برای روشن ساختن ساختارهای پیچیده ای که در تلاطم ظاهر می شوند، جریان های جوی، و در بررسی ساختارهای ستاره ای از آن استفاده شده است. این آنالیز به عنوان یک ابزار عددی می تواند مانند تبدیل سریع فوریه تا حد زیادی از پیچیدگی محاسبات بزرگ مقیاس بکاهد، بدین ترتیب که با تغییر هموار ضریب، ماتریس های متراکم را به شکل تنکی که به سرعت قابل محاسبه باشد در آورد. راحتی و سادگی این آنالیز باعث ساختن تراشه هایی شده است که قادر به کدگذاری به نحوی بسیار کارا، و فشرده سازی سیگنالها و تصاویرند.
آنالیز موجک امروزه کاربردهای فراوانی پیدا کرده است که از آن جمله می توان به کاربرد آن در تصویر برداری پزشکی (MRI) و سی تی اسکن (CAT)، جداسازی بافت های مغزی از تصاویر تشدید مغناطیس، تشخیص خودکار خوشه های میکروکلسیفیکاسیون، تحلیل تصاویر طیفی تشدید مغناطیسی (MR Spectrorscopy) و عملکردهای تشدید مغناطیسی (F MRI) اشاره کرد.

منبع


موجک

موجک (Wavelet) دسته‌ای از توابع ریاضی هستند که برای تجز‌یه سیگنال پیوسته به مؤلفه‌های فرکانسی آن بکار می‌رود که رزولوشن هر مؤلفه برابر با مقیاس آن است. تبدیل موجک تجزیه یک تابع بر مبنای توابع موجک می‌باشد. موجک‌ها (که به عنوان موجک‌های دختر شناخته می‌شوند) نمونه‌های انتقال یافته و مقیاس شده یک تابع (موجک مادر) با طول متناهی و نوسانی شدیداً میرا هستند. چند نمونه موجک مادر در شکل زیر نمایش داده شده‌اند.

مِیِر

مورله

کلاه مکزیکی

تبدیل‌های موجک

تعداد زیادی تبدیل موجک وجود دارد که لیست آن را می‌شود در فهرست تبدیل‌های مرتبط با موجک مشاهده نمود. معمول‌ترین این تبدیل‌ها عبارتند از:

  • تبدیل موجک پیوسته (Continuous wavelet transform (CWT
  • تبدیل موجک گسسته (Discrete wavelet transform (DWT
  • تبدیل سریع موجک (Fast wavelet transform (FWT
  • Lifting scheme
  • تجزیه بسته‌های موجک(Wavelet packet decomposition (WPD
  • تبدیل موجک ساکن (Stationary wavelet transform (SWT

موجک‌ها و معادلات اتساع
موجک‌ها بر مبنای دو عمل اصلی قرار دارند:

  • انتقال (Translation)

[عکس: 34b5ae95f23a0378679d434d7cea3360.png]

  • اتساع (Dilation)

[عکس: a9be4f8956d1bb85c9e932c584196743.png]

مقایسه با تبدیل فوریه

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

تاریخچه

در تاریخ ریاضیات مبادی و ریشه‌های متعددی را می‌توان برای موجک‌ها سراغ گرفت.

کارهای قبل از ۱۹۳۰
مربوط به قبل از ۱۹۳۰ (م) می‌توان به آنالیز فرکانس‌ها اشاره کرد، که به وسیلهٔ فوریه شروع شد.
استفاده از واژهٔ موجک‌ها، برای اولین بار، در یکی از ضمیمه‌های تز آلفرد هار (۱۹۰۹ م) ظاهر شد. امروزه هم، این موجک‌ها به همان نام یعنی به موجک‌های هار معروف اند. موجک‌های هار دارای دامنهٔ تعریف فشرده (compact) بوده، و غیر مشتق‌پذیر به صورت پیوسته هستند.

کارهای مربوط به دهه ۱۹۳۰
در این دهه چند گروه پیرامون موضوع نمایش توابع با به کارگیری پایه‌های با مقیاس متغیر برای تنیدن فضاهای توابع تحقیق می‌نمودند.

موجک‌های متعامد

با دیدی کلی می‌توان اظهار داشت که پایه‌های متعامد حالتی بهینه برای تنیدن فضاهای برداری (چه فضاهای با ابعاد متناهی و چه فضاهای بی نهایت بعدی) و انجام محاسبات ارائه می‌نمایند. لذا همواره تمایل و تلاش در این راستا قرار داشته که یا مجموعه پایه‌ها از آغاز متعامد انتخاب شود و یا آن که با شیوه‌هایی نظیر گرام اشمیت آنها را به سوی تعامد سوق داد.

موجک هار

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

منبع

تشخیص خودکار پلاک خودرو سامانه‌ای برای خواندن پلاک وسیله نقلیه با استفاده از نویسه‌خوان نوری است. شماره پلاک خودرو یکی از مناسب‌ترین اقلام اطلاعاتی جهت احراز هویت خودروها می‌باشد. تشخیص خودکار شماره پلاک خودرو سامانه‌ای کاملاً مکانیزه است که با استفاده ازپردازش تصویر خودروهای عبوری از یک مکان، شماره پلاک آنها را استخراج می‌کند. برای استفاده از این سامانه، نیازی به نصب و تجهیز خودروها به وسیلهٔ دیگری (مانند GPS یا برچسب‌های رادیویی- RFID Tag) وجود ندارد. این سامانه با استفاده از دوربین‌های مخصوص، تصویری از خودرو در حال عبور اخذ می‌کند و آن تصویر را جهت پردازش توسط نرم‌افزار تشخیص پلاک خودرو به رایانه ارسال می‌کند. از این سامانه می‌توان در زمینه‌های امنیتی و ترافیکی بسیار بهره گرفت.

             

 

امکانات سیستم های تشخیص پلاک خودرو به روش پردازش تصویر

امکان تشخیص تمامی اعداد و حروف پلاک و شناسایی منطقه پلاک صادرشده امکان تشخیص تمامی پلاکهای موجود در کشور امکان دریافت عکس از دوربین های رنگی و سیاه و سفید و IR تحت شبکه تشخیص محل پلاک در عکس امکان تشخیص چندین پلاک در یک عکس امکان ارتباط با بانک اطلاعاتی سیستم پارکینگ جهت کنترل تردد خودروهای تعریف شده امکان ارسال اطلاعات خودروهای ممنوعه در بانک اطلاعاتی سیستم از طریق شبکه، GPRS ، SMS و MMS

اطلاعات فنی سیستم تشخیص پلاک خودرو

امکان تشخیص پلاک از فیلم زنده در دوربین های تحت شبکه و DVR سرعت بسیار بالا در تشخیص پلاک (کمتر از 200 میلی ثانیه) دقت بالا و امکان تشخیص چندین پلاک در یک عکس

 

کاربردهای سامانهٔ تشخیص پلاک

کنترل و اخذ عوارض ورود به محدوده طرح ترافیک

امروزه شهرهای بسیاری ورود خودروها به منطقه مرکزی شهر را به منظور کنترل ترافیکِ آن محدود ساخته‌اند. از آنجا که استفاده از روش‌های سنتی (قرار دادن نیروهای پلیس در تمامی مبادی محدوده) هم پر هزینه و هم کم دقت است، راه حل‌های جدیدی برای کنترل و اخذ عوارض ورود به محدوده پرتردد شهرها پیشنهاد شده است. یکی از این راه حل‌ها (که برای مثال در استکهلم[۳] و لندن[۴] استفاده می‌شود) استفاده از فناوری تشخیص پلاک خودرو است. در این راه حل، دوربین‌های تشخیص پلاک خودرو در تمامی مبادی طرح نصب می‌شوند و ورود هر خودرو به محدوده طرح ثبت می‌شود. سپس مانند روش اخذ عوارض، فرصتی به راننده داده می‌شود تا عوارض ورود به طرح را تا زمان مقرر پرداخت کند. در غیر اینصورت، راننده طبق قانون جریمه خواهد شد.

اخذ عوارض جاده‌ها و بزرگراه‌ها به صورت خودکار

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

محاسبه مدت سفر

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

اندازه‌گیری سرعت متوسط خودروها

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

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

امکانات جانبی سامانه تشخیص خودکار شماره پلاک خودرو

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

منبع


هم چنین نوشته هایی با عناوین پروژه + آموزش تشخیص پلاک خودرو با پردازش تصویر (پلاک خوان رایگان) و مقاله بررسی سامانه های تشخیص خودکار پلاک خودرو  و مقالات داخلی و خارجی در زمینه تشخیص پلاک خودرو جهت دسترسی علاقمندان در سایت قرارداده شده است.

می توانید به منظور آشنایی با یکی از دقیقترین و سریعترین سامانه های جامع کنترل تردد خودرو (پلاک خوان) به لینک :سامانه جامع کنترل تردد خودرو بهسان(پلاک خوان) مراجعه فرمایید.

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

استگانوگرافی، برگرفته از دو کلمه‌ایونانی stego به معنای پوشیده و graphy به معنای نوشتن است؛ بنابراین کل کلمه به معنای پوشیده‌نویسی یا پنهان‌نگاری می‌باشد.

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

کلمات معادل

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

تفاوت پنهان نگاری(Steganography) و رمزنگاری(Cryptography)

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

روش‌های پنهان‌نویسی

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

open space methods

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

syntactic methods

در این روش از تغییر punctuations و همین‌طور از تغییر متن تا آنجا که معنا عوض نشود، استفاده می‌شود. مثلاً:

Bread, butter, and milk

Bread, butter and milk

semantic methods

در این روش از کلمات مترادف استفاده می‌شود.

پوشیده‌نویسی در صدا

محدودیت مهم در مورد صدا این است که بعد از پوشیده‌نویسی صدا باید همچنان قابل شنیدن باشد. یک مورد دیگر آن است که اکثر فایلهای صوتی توسط الگوریتمهای فشردهسازی فشرده می‌شوند و نباید در حین این فشرده‌سازی داده‌های مخفی ما ازبین برود. تکنیک‌هایی مانند «bitstream watermarking» و «PCM watermarking» برای این‌کار استفاده می‌شوند.

در تکنیک «bitstream watermarking» داده‌ها در یک فایل صوتی فشرده‌شده ذخیره می‌شوند. البته باید توجه نمود که دو پارامتر «sample quantization» و «sample rating» و همچنین نوع انتقال صوت در انتخاب تکنیک مناسب (تکنیک‌هایی مانند Spread Spectrum , Encoding, Phase Coding و Echo Data Hiding) نقش تعیین‌کننده‌ای دارد.

پوشیده‌نویسی در تصویر

پوشیده‌نویسی در تصویر را می‌توان به دو دسته کلّی تقسیم کرد:

دسته نخست: Spatial Domain Techniques

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

دسته دوم: (Spread Spectrum Techniques(frequency domain

این روش‌ها برای تصاویر با پسوند JPEG، که فشرده‌اند مناسب هستند و در این دسته یک تابع تبدیل مانند (DCT(Discrete Wavelet Transform یا (FFT(Fast Fourier Transform بر روی تصویر اعمال می‌شود. ضرایب مهم (coefficient) انتخاب می‌شوند. برای آن که در نهایت داده‌های ما در برابر تغییراتی که بر عکس ممکن است پیش بیایند مقاوم باشند (مثلاً مهاجم‌ها نتوانند داده‌های ما را به راحتی حذف کنند و سپس داده‌ها در دامنهٔ DCT یا FFT از طریق تغییر ضرایب درج می‌شوند. در نهایت تبدیل معکوس DCT یا FFT به ما تصویر حاوی داده را می‌دهد.

پوشیده نویسی در فیلم

پوشیده‌نویسی در فیلم مانند پوشیده‌نویسی در تصویر است، چراکه فیلم دنباله‌ای از تصاویر است، تکنیک DCT در آنجا نیز کاربرد دارد. نکته مهم در پوشیده‌نویسی در فیلم این است که نباید bit-rate فیلم تغییر کند.

روش (DWT (Discrete Wavelet Transform نیز درمخفی کردن داده‌ها در فیلم استفاده می‌شود. باید فشرده بودن فایل‌ها که در مورد فایلهای صوتی مطرح است، این‌جا هم رعایت شود.

تقابل امنیت، ظرفیت و مقاومت

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

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

تعریف پنهان شکنی

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

منبع

 

چکیده

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

مقدمه

Steganography در یونانی به معنای پوشیده شده یا نوشتن مخفیانه است. هدف  steganography این است که پیغامی را در یک پیغام دیگر ِ بی خطر به روشی ذخیره کند که دشمن پی به وجود پیغام اولی در پیغام دوم نبرد. جوهر های نامرئی یکی از عمومی ترین ابزارها برای steganography هستند استگانوگرافی موضوعی است که به ندرت از طریق هواخواهان امنیتی فناوری اطلاعات مورد توجه قرار گرفته است. در حقیقت  پنهان نگاری (نهان نگاری) پروسه ای است که در طی آن یک داده را در دیگر شکل های دیگر داده ای مثل فایل های عکس یا متن مخفی می کنند. معروف ترین و رایج ترین متد مخفی کردن داده در فایلها بکارگیری تصاویر گرافیکی به عنوان مکان‌هایی مخفی می باشد.

تاریخچه

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

استگانوگرافی چیست؟

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

تفاوت پنهان نگاری(steganogrphy) و رمزنگاری(Cryptography)

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

شمای کلی استگانوگرافی

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

انواع مختلف استگانوگرافی

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

تشریح تکنیک هایSteganography

فرمول کلی برای تابع Steganography این چنین است: شی ای که قراراست اطلاعات در آن نگهداری شود + اطلاعاتی که باید مخفی شوند + الگوریتم مورد نظر = شی مورد نظر که اطلاعات در آن مخفی شده اند. فایلی که برای مخفی کردن اطلاعات به کار می رود، می تواند یک تصویر، فایل صوتی و یا یک فایل ویدئویی باشد. درعین حال دو روش معمول برای Steganography وجود دارد که عبارتند از : Injection,LSB.

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

Injection‎ : روشی ساده است که برمبنای آن، ‌اطلاعاتی که قراراست مخفی شوند را در یک فایل تزریق می کنند. مهمترین مسأله در این روش،‌ افزایش حجم فایل است

Steganography در فرمت های مختلف:

Steganography در تصاویر

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

Steganography درصوت

برای این منظور نیز از روشی مشابه روش LSB استفاده می کنند. البته مشکل استفاده از بیت های کم ارزش در یک فایل صوتی، این است که تغییرات در این بیت ها نیز برای گوش انسان قابل تشخیص است . در حقیقت Spread Spectrum روش دیگری برای مخفی نمودن اطلاعات در یک فایل صوتی است. دراین روش، یک نویز به طور تصادفی در سراسر فایل پخش می شود و اطلاعات در کنار این نویزها قرارداده می شوند. Echo data hiding نیز روش دیگری برای مخفی نمودن اطلاعات در یک فایل صوتی است. این روش از اکو (پژواک) در فایل استفاده می کند تا بتواند اطلاعات را مخفی نماید. دراین وضعیت با اضافه کردن صداهای اضافی به بخش های اکو، می توان اطلاعات را در این قسمت ها مخفی نمود.

Steganography در ویدئو

برای این کار ، معمولاً از روش DCT استفاده می شود. این تکنیک شبیه تکنیک LSB است. یک فایل ویدئویی از تعدادی تصاویر پشت سرهم تشکیل شده است که این تصاویر به نام فریم شناخته می شوند. بنابراین کافی است که اطلاعات خود را درهر فریم یک فایل ویدئویی ، ‌به روش LSB مخفی نماییم.

تشریح تکنیک LSB بر روی یک فایل تصویری

هر فایل تصویری صرفاً یک فایل دودویی است که حاوی رنگ یا شدت نور هر پیکسل برحسب عددی دودویی است. تصاویر معمولاً از فرمت ۸ بیتی یا ۲۴ بیتی استفاده می کنند. در فرمت ۸ بیتی، تنها قادر به استفاده از ۲۵۶ رنگ برای هرپیکسل هستیم ( از این ۸ بیت، هر بیت می تواند یکی از مقادیر ۰ یا ۱ را برگزیند که در مجموع ۲ به توان ۸، ‌یعنی ۲۵۶ رنگ مختلف داریم). درفرمت ۲۴ بیتی نیز هرپیکسل از۲ به توان ۲۴ بیت رنگ می تواند استفاده کند. در این فرمت، هرپیکسل از۳ بایت ۸ بیتی استفاده می کند. هر بایت نشان دهنده شدت روشنایی یکی از سه رنگ اصلی آبی، قرمز و سبز است. به عنوان نمونه،‌رنگ ها در فرمت html بر اساس فرمت ۲۴ بیتی است، ‌که هر رنگ، کدی بر مبنای ۱۶ دارد که از ۶ کاراکتر تشکیل شده است.دو کاراکتر اول، مربوط به رنگ قرمز، دو کاراکتر دوم مربوط به رنگ آبی و دو کاراکتر سوم، مربوط به رنگ سبز است . برای نمونه برای ساختن رنگ نارنجی، باید مقادیر شدت روشنایی رنگ های قرمز، ‌سبز و آبی ، به ترتیب ۱۰۰% و۵۰% و۰ باشد که در html با #FF7FOO قابل تعریف است.

همچنین اندازه یک تصویر، به تعداد پیکسل ها در تصویر بستگی دارد. برای نمونه، برای تصویری با رزولوشن ۴۸۰× ۶۴۰ که از فرمت ۸ بیتی استفاده می کند،‌ اندازه تصویر باید حدود ۶۴۰*۴۸۰*Byte=307KB باشد. به عنوان مثالی دیگر، تصویری با رزولوشن ۱۰۲۴*۷۶۸ که ازفرمت ۲۴ بیتی استفاده می کند، اندازه تصویر باید حدود ۱۰۲۴*۷۶۸*۳Byte=2.36MB باشد. البته این اعداد درصورتی صادق هستند که هیچ فشردگی بر روی فایل اعمال نشده باشد. لازم به ذکراست، ‌فرمت های تصویری GIF وBMP ، 8 بیتی بوده و از روش Lossless (روشی در گرافیک برای فشرده سازی تصاویراست که درآن تمام اطلاعات تصویرحفظ می شود و فقط از تعداد محدودی ازاطلاعات استفاده می شود و در برنامههای خاصی، اطلاعات حفظ شده قابل بازیابی است بنابراین از کیفیت تصویر نیز کاسته نمی شود) استفاده می کنند.

درمقابل، فرمت JPEG ازروش Lossy(دراین روش بخشی ازاطلاعات تصویر برای همیشه ازبین می رود)استفاده می کند. در Steganographyاز فرمت های GIF وBMP به دلیل ویژگی هایی که دارند، استفاده می شوند. ساده ترین راه برای پیاده سازی Steganography استفاده ازبیت های کم ارزش هرپیکسل یا همان روش(Least significant bit insertion) است. برای این منظور اطلاعات را به دو صورت دودویی درآورده و در بیت های کم ارزش پیکسل های تصویر قرار می دهیم . البته ما خواهان این هستیم که تصویر مورد نظر نیز زیاد تغییری نداشته باشد. بنابراین اگر از فرمت ۲۴ بیتی برای این کار استفاده کنیم، چشم انسان قادر به شناسایی این تغییر در تصویر نیست. فرض کنید که سه پیکسل مجاور هم داریم که به صورت زیر کد شده اند: سبز آبی قرمز ۱۱۰۰۱۰۰۱ ۰۰۰۰۱۱۰۱ ۱۰۰۱۰۱۰۱ پیکسل ۱ ۱۱۰۰۱۰۱۰ ۰۰۰۰۱۱۱۱ ۱۰۰۱۰۱۱۰ پیکسل ۲ ۱۱۰۰۱۰۱۱ ۰۰۰۱۰۰۰۰ ۱۰۰۱۱۱۱۱ پیکسل ۳ حال فرض کنید که می خواهیم ۹ بیت اطلاعات ۱۰۱۱۰۱۱۰۱را در این پیکسل ها مخفی نماییم (فرض میشود که این ۹ بیت اطلاعات رمزنگاری شده، یک پیام باشند). حال اگر ازروش LSB استفاده شود و این ۹ بیت در بیت های کم ارزش بایت های این سه پیکسل قرارداده شوند،‌ جدول زیر را خواهیم داشت . سبز آبی قرمز ۱۱۰۰۱۰۰۱ ۰۰۰۰۱۱۰۰ ۱۰۰۱۰۱۰۱ پیکسل ۱ ۱۱۰۰۱۰۱۱ ۰۰۰۰۱۱۱۰ ۱۰۰۱۰۱۱۱ پیکسل ۲ ۱۱۰۰۱۰۱۱ ۰۰۰۱۰۰۰۰ ۱۰۰۱۱۱۱۱ پیکسل ۳ ملاحظه می شود که فقط ۴ بیت تغییر داده شده اند و این لطمه زیادی به تصویر وارد نمی کند، به طوری که چشم اصلاً قادر به تشخیص این تغییرات نیست. به عنوان مثال، تغییربیت رنگ آبی از ۱۱۱۱۱۱۱۱ به ۱۱۱۱۱۱۱۰ اصلاًبرای چشم قابل تشخیص نیست. ناگفته نماند تصاویر سیاه وسفید نیز برای Steganography بسیار مناسب هستند. حال شاید خواهان مخفی کردن یک متن در یک تصویر باشیم. در این وضعیت هر کاراکتر، یک بایت( ۸ بیت)فضا اشغال می کند. از آنجا که این بیت ها را باید درون پیکسل های تصویری قرار دهیم، می بایست این هشت بیت را به بسته های ۱ بیتی تقسیم نماییم و هر بیت را در بیت های سطح پایین یکی ازسه رنگ اصلی پیکسل ها،‌ قرار دهیم با این شیوه، کلمات تمامی زبان هایی را که با ساختار ASCII یا UTF-8 سازگارند، می توان درون تصاویر جاسازی نمود.

پیاده سازی تکنیک LSB

برای این کار معمولاً از فرمت BMF 24 بیتی استفاده می شود. در واقع در این روش معمولاً از دو بیت کم ارزش هر یک از بایت های پیکسل استفاده می شود. این کار به این دلیل است که در یک تصویر، تعداد زیادی کاراکتر را بتوان جا داد همچنین متنی را که قرار است در تصویر مخفی شود، به کد ASCII تبدیل می کنند. سپس هر کاراکتر را به بسته های ۲ بیتی تقسیم می کنند، یعنی هر کاراکتر از ۴ بسته ۲ بیتی تشکیل می شود. سپس این بسته های ۲ بیتی را در دو بیت کم ارزش هر یک از بایت های یک پیکسل،‌ پخش می کنند. یعنی برای هر کاراکتر، ما احتیاج به ۴ بایت از اطلاعات تصویر داریم، که ۳ بایت آن از یک پیکسل بدست می آید و بایت چهارم هم از پیکسل دیگر گرفته می شود. برای راحتی کار، معمولاً بسته های ۲ بیتی را در اولین پیکسل جا سازی می کنند و به همین ترتیب پیش می روند تا تمام متن در تصویر جاسازی گردد. استخراج اطلاعات پنهان شده برای استخراج متون مخفی شده در تصویر عملیات زیر را به ترتیب انجام می دهیم: استخراج بیت های استفاده شده ادغام بیت ها و تبدیل آنها به بایت تبدیل بایت ها به کاراکتر مشاهده کامل متن جا سازی شده

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

نتیجه گیری:

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

 

 

 

معایب و مزایای خوشه‌بندی k-میانگین

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

به منظور ارزیابی نتایج خوشه‌بندی از معیارهای متفاوتی کمک گرفته می‌شود. ممکن است از قبل برچسب خوشه‌ها مشخص باشد و بخواهیم کارایی الگوریتم را با توجه به مقایسه برچسب‌های واقعی و حاصل از خوشه‌بندی، اندازه‌گیری کنیم. در این حالت، شاخص‌های ارزیابی بیرونی، بهترین راهنما و معیار برای سنجش صحت نتایج خوشه‌بندی محسوب می‌شوند. معمولا به این برچسب‌ها، استاندارد طلایی (Golden Standard) و در کل چنین عملی را ارزیابی Benchmark می‌گویند. برای مثال شاخص رَند (Rand Index) یکی از این معیارها و شاخص‌های بیرونی است که از محبوبیت خاصی نیز برخوردار است.

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

منبع


KMeans شاید ساده‌ترین الگوریتمِ خوشه‌بندی باشد که در بسیاری از مواقع جزوِ بهترین الگوریتم‌های خوشه‌بندی نیز هست. این الگوریتم از دسته الگوریتم‌هایی است که بایستی تعداد خوشه‌ها (گروه ها) را از قبل به او گفته باشیم. فرض کنید یک سری داده داریم و مانندِ درسِ شبکه های عصبی دو دسته داده داریم (پراید و اتوبوس) با این تفاوت که در یک مسئله‌ی خوشه‌بندی، نمی‌دانیم که کدام پراید است کدام اتوبوس؟ و فقط یک سری داده با دو ویژگی (طول ماشین و ارتفاع ماشین) در اختیار داریم. اجازه دهید اینبار این دو دسته را بدون دانستنِ برچسبِ آن ها بر روی نمودار رسم کنیم (برای اینکه بدانید چگونه این نمودار رسم می شود و بُعدهای مختلف آن چگونه ساخته می‌شود، درسِ شبکه‌ی عصبی را خوانده باشید) به صورت ساده، ما یک تعداد ماشین (اتومبیل) داریم که هر کدام ارتفاع و طولِ مشخصی را دارند. آن‌ها را به این گونه در دو بُعد در شکلِ زیر نمایش می‌دهیم):

برای مثال، ماشین شماره‌ی ۴#، دارای طولِ ۹ و ارتفاع ۴ است. در الگوریتمِ KMeans بایستی تعدادی نقطه در فضا ایجاد کنیم. تعداد این نقاط باید به تعداد خوشه‌هایی که می‌خواهیم در نهایت به آن برسیم، باشد (مثلا فرض کنید می‌خواهیم داده‌ها را به ۲خوشه تقسیم‌بندی کنیم، پس ۲نقطه به صورت تصادفی در فضای ۲بُعدیِ شکلِ بالا رسم می‌کنیم). شکل زیر را نگاه کنید:

الان ما دو نقطه‌ی سبز و قرمز انتخاب کردیم و این دو نقطه را جایی در فضا (به صورت تصادفی) قرار دادیم. حال فاصله‌ی هر کدام از نمونه‌ها را (۷ماشین) با این دو نقطه حساب می‌کنیم. برای این کار می‌توانیم از فاصله منهتن (Manhatan) استفاده کنیم. در واقع برای هر کدام از نمونه‌ها نسبت به دو نقطه‌ی سبز و قرمز در هر بُعد، با هم مقایسه کرده و از هم کم (تفاضل) میکنیم، سپس نتیجه‌ی کم کردنِ هر کدام از بُعد ها را با یکدیگر جمع میکنیم.

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

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

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

دورِ دوم نیز به اتمام رسید و به نظرْ الگوریتم خوشه‌های خوبی را تشخیص داد. ولی اجازه بدهید یک دور دیگر نیز الگوریتم را ادامه دهیم. مانند شکل زیر دور سوم را انجام می شود (یعنی نقاطِ قرمز و سبز به مرکز خوشه‌ی خود (در مرحله‌ی قبلی) می‌روند و فاصله‌ی هر کدام از نمونه‌ها دوباره با نقاطِ قرمز و سبز (در محلِ جدید) محاسبه شده و هر کدام همرنگِ نزدیک‌ترین نقطه‌ی قرمز یا سبز می‌شود):

همان طور که می‌بینید در انتهای دورِ سوم، تغییری در خوشه‌ی هر کدام از نمونه‌ها رخ نداد. یعنی سبزها سبز ماندند و قرمزها، قرمز.این یکی از شروطی است که می‌تواند الگوریتم را خاتمه دهد. یعنی الگوریتمْ وقتی به این حالت رسید که در چند دورِ متوالی تغییری در خوشه‌ی نمونه‌ها (در این‌جا ماشین‌ها) به وجود نیامد، یعنی الگوریتمْ دیگر نمی‌تواند زیاد تغییر کند و این حالتِ پایانی برای خوشه‌هاست. البته می‌توان شرطی دیگر نیز برای پایان الگوریتم در نظر گرفت. برای مثال الگوریتمْ حداکثر در ۲۰دورِ متوالی می‌تواند عملیات را انجام دهد و دورِ ۲۰ام آخرین دورِ الگوریتم خواهد بود و الگوریتم دیگر بیشتر از آن پیشروی نخواهد کرد. به طور کل در الگوریتم‌های مبتنی بر دور (Iterative Algorithms) می‌توان تعدادِ دورها را محدود کرد تا الگوریتمْ بی‌نهایت دور نداشته باشد.

همان طور که دیدیم، این الگوریتم می‌تواند یک گروه‌بندیِ ذاتی برای داده‌ها بسازد، بدون اینکه برچسب داده‌ها یا نوع آن‌ها را بداند.

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

منبع


مروری بر الگوریتم K-Means

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

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

در شکل زیر نمونه‌ای از خوشه‌بندی نشون داده شده که در اون داده‌ها به سه خوشه تقسیم‌ و به کمک سه رنگ نمایش داده شدن.

برای درک بهتر نحوه کار الگوریتم K-Means از مثال زیر استفاده می‌کنم:

فرض می‌کنیم که مجموعه داده‌ای داریم که شامل هر ۷ رکورد هست و همه رکوردهای اون ۲ ویژگی یا خصوصیت A و B رو دارن. (دز این‌جا میتونیم این ویژگی‌ها رو به عنوان طول و عرض در یک صفحه دو بعدی در نظر بگیریم)

رکورد A B
۱ ۱.۰ ۱.۰
۲ ۱.۵ ۲.۰
۳ ۳.۰ ۴.۰
۴ ۵.۰ ۷.۰
۵ ۳.۵ ۵.۰
۶ ۴.۵ ۵.۰
۷ ۳.۵ ۴.۵

فرض می‌کنیم که قراره داده‌ها به ۲ خوشه تقسیم بشن. پس برای این منظور به صورت تصادفی ۲ رکورد رو به عنوان مرکز این ۲ خوشه در نظر می‌گیریم.

رکورد مختصات
خوشه ۱ ۱ (۱.۰ و ۱.۰)
خوشه ۲ ۴ (۷.۰ و ۵.۰)

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

خوشه ۱ خوشه ۲
گام رکورد مرکز خوشه رکورد مرکز خوشه
۱ ۱ (۱.۰ و ۱.۰) ۴ (۷.۰ و ۵.۰)
۲ ۱ و ۲ (۱.۵ و ۱.۲) ۴ (۷.۰ و ۵.۰)
۳ ۱ و ۲ و ۳ (۲.۳ و ۱.۸) ۴ (۷.۰ و ۵.۰)
۴ ۱ و ۲ و ۳ (۲.۳ و ۱.۸) ۴ و ۵ (۶.۰ و ۴.۲)
۵ ۱ و ۲ و ۳ (۲.۳ و ۱.۸) ۴ و ۵ و ۶ (۵.۷ و ۴.۳)
۶ ۱ و ۲ و ۳ (۲.۳ و ۱.۸) ۴ و ۵ و ۶ و ۷ (۵.۴ و ۴.۱)

پس در ادامه مرکزهای خوشه‌ها به صورت زیر در میان.

رکورد مرکز خوشه
خوشه ۱ ۱ و ۲ و ۳ (۲.۳ و ۱.۸)
خوشه ۲ ۴ و ۵ و ۶ و ۷ (۵.۴ و ۴.۱)

در ادامه فاصله داده‌ها تا این مرکز‌های خوشه‌های جدید به شکل جدول زیر در میان.

رکورد فاصله تا خوشه ۱ فاصله تا خوشه ۲
۱ ۱.۵ ۵.۴
۲ ۰.۴ ۴.۳
۳ ۲.۱ ۱.۸
۴ ۵.۷ ۱.۸
۵ ۳.۲ ۰.۷
۶ ۳.۸ ۰.۶
۷ ۲.۸ ۱.۱

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

رکورد مرکز خوشه
خوشه ۱ ۱ و ۲ خوشه ۱
خوشه ۲ ۳ و ۴ و ۵ و ۶ و ۷ خوشه ۲

و کل این فرایند و مراحل تا زمانی انجام میشه که تغییر و جابجایی در خوشه‌ها اتفاق نیفته.

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

پیاده‌سازی الگوریتم  K-Means به زبان Java

 

import java.util.ArrayList;
public class KMeans_Ex {
    private static final int NUM_CLUSTERS = 2;    // Total clusters.
    private static final int TOTAL_DATA = 7;      // Total data points.
    private static final double SAMPLES[][] = new double[][]{{1.0, 1.0},
            {1.5, 2.0},
            {3.0, 4.0},
            {5.0, 7.0},
            {3.5, 5.0},
            {4.5, 5.0},
            {3.5, 4.5}};
    private static ArrayList    < Data >    dataSet = new ArrayList   < Data >  ();
    private static ArrayList   < Centroid >    centroids = new ArrayList   < Centroid >  ();
    private static void initialize() {
        System.out.println("Centroids initialized at:");
        centroids.add(new Centroid(1.0, 1.0)); // lowest set.
        centroids.add(new Centroid(5.0, 7.0)); // highest set.
        System.out.println("     (" + centroids.get(0).X() + ", " + centroids.get(0).Y() + ")");
        System.out.println("     (" + centroids.get(1).X() + ", " + centroids.get(1).Y() + ")");
        System.out.print("\n");
        return;
    }
    private static void kMeanCluster() {
        final double bigNumber = Math.pow(10, 10);    // some big number that's sure to be larger than our data range.
        double minimum = bigNumber;                   // The minimum value to beat.
        double distance = 0.0;                        // The current minimum value.
        int sampleNumber = 0;
        int cluster = 0;
        boolean isStillMoving = true;
        Data newData = null;
        // Add in new data, one at a time, recalculating centroids with each new one.
        while (dataSet.size()  <  TOTAL_DATA) {
            newData = new Data(SAMPLES[sampleNumber][0], SAMPLES[sampleNumber][1]);
            dataSet.add(newData);
            minimum = bigNumber;
            for (int i = 0; i  <  NUM_CLUSTERS; i++) {
                distance = dist(newData, centroids.get(i));
                if (distance < minimum) {
                    minimum = distance;
                    cluster = i;
                }
            }
            newData.cluster(cluster);
            // calculate new centroids.
            for (int i = 0; i  <  NUM_CLUSTERS; i++) {
                int totalX = 0;
                int totalY = 0;
                int totalInCluster = 0;
                for (int j = 0; j   < dataSet.size(); j++) { if (dataSet.get(j).cluster() == i) { totalX += dataSet.get(j).X(); totalY += dataSet.get(j).Y(); totalInCluster++; } } if (totalInCluster >    0) {
                    centroids.get(i).X(totalX / totalInCluster);
                    centroids.get(i).Y(totalY / totalInCluster);
                }
            }
            sampleNumber++;
        }
        // Now, keep shifting centroids until equilibrium occurs.
        while (isStillMoving) {
            // calculate new centroids.
            for (int i = 0; i  <  NUM_CLUSTERS; i++) {
                int totalX = 0;
                int totalY = 0;
                int totalInCluster = 0;
                for (int j = 0; j   < dataSet.size(); j++) { if (dataSet.get(j).cluster() == i) { totalX += dataSet.get(j).X(); totalY += dataSet.get(j).Y(); totalInCluster++; } } if (totalInCluster >   0) {
                    centroids.get(i).X(totalX / totalInCluster);
                    centroids.get(i).Y(totalY / totalInCluster);
                }
            }
            // Assign all data to the new centroids
            isStillMoving = false;
            for (int i = 0; i   <   dataSet.size(); i++) {
                Data tempData = dataSet.get(i);
                minimum = bigNumber;
                for (int j = 0; j   <   NUM_CLUSTERS; j++) {
                    distance = dist(tempData, centroids.get(j));
                    if (distance   <   minimum) {
                        minimum = distance;
                        cluster = j;
                    }
                }
                tempData.cluster(cluster);
                if (tempData.cluster() != cluster) {
                    tempData.cluster(cluster);
                    isStillMoving = true;
                }
            }
        }
        return;
    }
    /**
     * // Calculate Euclidean distance.
     *
     * @param d - Data object.
     * @param c - Centroid object.
     * @return - double value.
     */
    private static double dist(Data d, Centroid c) {
        return Math.sqrt(Math.pow((c.Y() - d.Y()), 2) + Math.pow((c.X() - d.X()), 2));
    }
    private static class Data {
        private double mX = 0;
        private double mY = 0;
        private int mCluster = 0;
        public Data() {
            return;
        }
        public Data(double x, double y) {
            this.X(x);
            this.Y(y);
            return;
        }
        public void X(double x) {
            this.mX = x;
            return;
        }
        public double X() {
            return this.mX;
        }
        public void Y(double y) {
            this.mY = y;
            return;
        }
        public double Y() {
            return this.mY;
        }
        public void cluster(int clusterNumber) {
            this.mCluster = clusterNumber;
            return;
        }
        public int cluster() {
            return this.mCluster;
        }
    }
    private static class Centroid {
        private double mX = 0.0;
        private double mY = 0.0;
        public Centroid() {
            return;
        }
        public Centroid(double newX, double newY) {
            this.mX = newX;
            this.mY = newY;
            return;
        }
        public void X(double newX) {
            this.mX = newX;
            return;
        }
        public double X() {
            return this.mX;
        }
        public void Y(double newY) {
            this.mY = newY;
            return;
        }
        public double Y() {
            return this.mY;
        }
    }
    public static void main(String[] args) {
        initialize();
        kMeanCluster();
        // Print out clustering results.
        for (int i = 0; i    <    NUM_CLUSTERS; i++) {
            System.out.println("Cluster " + i + " includes:");
            for (int j = 0; j    <    TOTAL_DATA; j++) {
                if (dataSet.get(j).cluster() == i) {
                    System.out.println("     (" + dataSet.get(j).X() + ", " + dataSet.get(j).Y() + ")");
                }
            } // j
            System.out.println();
        } // i
        // Print out centroid results.
        System.out.println("Centroids finalized at:");
        for (int i = 0; i    <    NUM_CLUSTERS; i++) {
            System.out.println("     (" + centroids.get(i).X() + ", " + centroids.get(i).Y() + ")");
        }
        System.out.print("\n");
        return;
    }

 

پیاده‌سازی الگوریتم K-Means به زبانPython

 

import math
NUM_CLUSTERS = 2
TOTAL_DATA = 7
LOWEST_SAMPLE_POINT = 0  # element 0 of SAMPLES.
HIGHEST_SAMPLE_POINT = 3  # element 3 of SAMPLES.
BIG_NUMBER = math.pow(10, 10)
SAMPLES = [[1.0, 1.0], [1.5, 2.0], [3.0, 4.0], [5.0, 7.0], [3.5, 5.0], [4.5, 5.0], [3.5, 4.5]]
data = []
centroids = []
class DataPoint:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def set_x(self, x):
        self.x = x
    def get_x(self):
        return self.x
    def set_y(self, y):
        self.y = y
    def get_y(self):
        return self.y
    def set_cluster(self, clusterNumber):
        self.clusterNumber = clusterNumber
    def get_cluster(self):
        return self.clusterNumber
class Centroid:
    def __init__(self, x, y):
        self.x = x
        self.y = y
    def set_x(self, x):
        self.x = x
    def get_x(self):
        return self.x
    def set_y(self, y):
        self.y = y
    def get_y(self):
        return self.y
def initialize_centroids():
    # Set the centoid coordinates to match the data points furthest from each other.
    # In this example, (1.0, 1.0) and (5.0, 7.0)
    centroids.append(Centroid(SAMPLES[LOWEST_SAMPLE_POINT][0], SAMPLES[LOWEST_SAMPLE_POINT][1]))
    centroids.append(Centroid(SAMPLES[HIGHEST_SAMPLE_POINT][0], SAMPLES[HIGHEST_SAMPLE_POINT][1]))
    print("Centroids initialized at:")
    print("(", centroids[0].get_x(), ", ", centroids[0].get_y(), ")")
    print("(", centroids[1].get_x(), ", ", centroids[1].get_y(), ")")
    print()
    return
def initialize_datapoints():
    # DataPoint objects' x and y values are taken from the SAMPLE array.
    # The DataPoints associated with LOWEST_SAMPLE_POINT and HIGHEST_SAMPLE_POINT are initially
    # assigned to the clusters matching the LOWEST_SAMPLE_POINT and HIGHEST_SAMPLE_POINT centroids.
    for i in range(TOTAL_DATA):
        newPoint = DataPoint(SAMPLES[i][0], SAMPLES[i][1])
        if (i == LOWEST_SAMPLE_POINT):
            newPoint.set_cluster(0)
        elif (i == HIGHEST_SAMPLE_POINT):
            newPoint.set_cluster(1)
        else:
            newPoint.set_cluster(None)
        data.append(newPoint)
    return
def get_distance(dataPointX, dataPointY, centroidX, centroidY):
    # Calculate Euclidean distance.
    return math.sqrt(math.pow((centroidY - dataPointY), 2) + math.pow((centroidX - dataPointX), 2))
def recalculate_centroids():
    totalX = 0
    totalY = 0
    totalInCluster = 0
    for j in range(NUM_CLUSTERS):
        for k in range(len(data)):
            if (data[k].get_cluster() == j):
                totalX += data[k].get_x()
                totalY += data[k].get_y()
                totalInCluster += 1
        if (totalInCluster    >     0):
            centroids[j].set_x(totalX / totalInCluster)
            centroids[j].set_y(totalY / totalInCluster)
    return
def update_clusters():
    isStillMoving = 0
    for i in range(TOTAL_DATA):
        bestMinimum = BIG_NUMBER
        currentCluster = 0
        for j in range(NUM_CLUSTERS):
            distance = get_distance(data[i].get_x(), data[i].get_y(), centroids[j].get_x(), centroids[j].get_y())
            if (distance     <     bestMinimum):
                bestMinimum = distance
                currentCluster = j
        data[i].set_cluster(currentCluster)
        if (data[i].get_cluster() is None or data[i].get_cluster() != currentCluster):
            data[i].set_cluster(currentCluster)
            isStillMoving = 1
    return isStillMoving
def perform_kmeans():
    isStillMoving = 1
    initialize_centroids()
    initialize_datapoints()
    while (isStillMoving):
        recalculate_centroids()
        isStillMoving = update_clusters()
    return
def print_results():
    for i in range(NUM_CLUSTERS):
        print("Cluster ", i, " includes:")
        for j in range(TOTAL_DATA):
            if (data[j].get_cluster() == i):
                print("(", data[j].get_x(), ", ", data[j].get_y(), ")")
        print()
    return
perform_kmeans()
print_results()

 

در این الگوریتم وقتی مرکز خوشه محاسبه میشه خیلی پیش میاد که این مرکز خوشه محاسبه‌شده در بین داده‌های واقعی موجود نباشه و صرفا یه میانگین محسوب میشه که همین موضوع باعث مقاوم نبودن این الگوریتم در برابر داده‌های پرت مبشه. برای حل این مشکل الگوریتمی پیشنهاد شده به نام K-Medoids که در این الگوریتم مرکز خوشه جدید وقتی محاسبه میشه خودش هم در بین داده‌های اصلی موجود هست. با کمی تغییر در الگوریتم K-Means می‌تونیم K-Medoids رو هم داشته باشیم.

این برنامه در سایت گیتلب قابل دسترس هست و شما می‌تونید اون رو تغییر بدین و بهترش کنید.

 

پیاده‌سازی الگوریتم KMEANS به زبان JAVA در گیتلب

پیاده‌سازی الگوریتم KMEANS به زبان PYTHON در گیتلب

منبع

از مهم‌ترین تکنیک‌های عملی داده‌کاوی که کاربرد زیادی در علوم مختلف دارد، می توان به «خوشه بندی k-میانگین» (K-means Clustering)  اشاره کرد، که با توجه به بار محاسباتی زیاد آن، استفاده از کامپیوتر در انجام این فرآیند، کمک شایانی به کاربران می‌کند. در این راستا زبان برنامه‌نویسی و محاسباتی R قابلیت انجام این گونه محاسبات را دارد و به محققین در تحلیل خوشه‌بندی تفکیکی بر مبنای روش K-میانگین، کمک شایانی می‌کند. در این متن به بررسی روش خوشه‌بندی با استفاده از دستورات مربوط به این زبان برنامه‌نویسی می‌پردازیم و با البته با مفاهیم اولیه خوشه‌بندی k-میانگین نیز آشنا می‌شویم.

خوشه‌بندی k-میانگین

روش‌‌ها و الگوریتم‌های متعددی برای تبدیل اشیاء به گروه‌های همشکل یا مشابه وجود دارد. الگوریتم k-میانگین یکی از ساده‌ترین و محبوب‌ترین الگوریتم‌هایی است که در «داده‌کاوی» (Data Mining) بخصوص در حوزه «یادگیری نظارت نشده» (Unsupervised Learning) به کار می‌رود.

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

الگوریتم خوشه‌بندی k-میانگین از گروه روش‌های خوشه‌بندی تفکیکی (Partitioning Clustering) محسوب می‌شود و درجه پیچیدگی محاسباتی آن برابر با O(ndk+1) است، به شرطی که n تعداد اشیاء، d بعد ویژگی‌ها و k تعداد خوشه‌ها باشد. همچنین پیچیدگی زمانی برای این الگوریتم برابر با O(nkdi) است، که البته منظور از i‌ تعداد تکرارهای الگوریتم برای رسیدن به جواب بهینه است.

در خوشه‌بندی k-میانگین از بهینه‌سازی یک تابع هدف (Object Function) استفاده می‌شود. پاسخ‌های حاصل از خوشه‌بندی در این روش، ممکن است به کمک کمینه‌سازی (Minimization) یا بیشینه‌سازی (Maximization) تابع هدف صورت گیرد. به این معنی که اگر ملاک «میزان فاصله» (Distance Measure) بین اشیاء باشد، تابع هدف براساس کمینه‌سازی خواهد بود پاسخ عملیات خوشه‌بندی، پیدا کردن خوشه‌هایی است که فاصله بین اشیاء هر خوشه کمینه باشد. در مقابل، اگر از تابع مشابهت (Dissimilarity Function) برای اندازه‌گیری مشابهت اشیاء استفاده شود، تابع هدف را طوری انتخاب می‌کنند که پاسخ خوشه‌بندی مقدار آن را در هر خوشه بیشینه کند.

خوشه‌بندی k-میانگین روش‌‌ها و الگوریتم‌های متعددی برای تبدیل اشیاء به گروه‌های همشکل یا مشابه وجود دارد. الگوریتم k-میانگین یکی از ساده‌ترین و محبوب‌ترین الگوریتم‌هایی است که در «داده‌کاوی» (Data Mining) بخصوص در حوزه «یادگیری نظارت نشده» (Unsupervised Learning) به کار می‌رود. معمولا در حالت چند متغیره، باید از ویژگی‌های مختلف اشیا به منظور طبقه‌بندی و خوشه‌ کردن آن‌ها استفاده کرد. به این ترتیب با داده‌های چند بعدی سروکار داریم که معمولا به هر بعد از آن، ویژگی یا خصوصیت گفته می‌شود. با توجه به این موضوع، استفاده از توابع فاصله مختلف در این جا مطرح می‌شود. ممکن است بعضی از ویژگی‌های اشیا کمی و بعضی دیگر کیفی باشند. به هر حال آنچه اهمیت دارد روشی برای اندازه‌گیری میزان شباهت یا عدم شباهت بین اشیاء است که باید در روش‌های خوشه‌بندی لحاظ شود. الگوریتم خوشه‌بندی k-میانگین از گروه روش‌های خوشه‌بندی تفکیکی (Partitioning Clustering) محسوب می‌شود و درجه پیچیدگی محاسباتی آن برابر با O ( n d k + 1 ) است، به شرطی که n تعداد اشیاء، d بعد ویژگی‌ها و k تعداد خوشه‌ها باشد. همچنین پیچیدگی زمانی برای این الگوریتم برابر با O ( n k d i ) است، که البته منظور از i‌ تعداد تکرارهای الگوریتم برای رسیدن به جواب بهینه است. در خوشه‌بندی k-میانگین از بهینه‌سازی یک تابع هدف (Object Function) استفاده می‌شود. پاسخ‌های حاصل از خوشه‌بندی در این روش، ممکن است به کمک کمینه‌سازی (Minimization) یا بیشینه‌سازی (Maximization) تابع هدف صورت گیرد. به این معنی که اگر ملاک «میزان فاصله» (Distance Measure) بین اشیاء باشد، تابع هدف براساس کمینه‌سازی خواهد بود پاسخ عملیات خوشه‌بندی، پیدا کردن خوشه‌هایی است که فاصله بین اشیاء هر خوشه کمینه باشد. در مقابل، اگر از تابع مشابهت (Dissimilarity Function) برای اندازه‌گیری مشابهت اشیاء استفاده شود، تابع هدف را طوری انتخاب می‌کنند که پاسخ خوشه‌بندی مقدار آن را در هر خوشه بیشینه کند. معمولا زمانی که هدف کمینه‌سازی باشد، تابع هدف را «تابع هزینه» (Cost Function) نیز می‌نامند. روش خوشه بندی k-میانگین، توسط «مک‌کوئین» (McQueen) جامعه شناس و ریاضیدان در سال ۱۹۶۵ ابداع و توسط دیگر دانشمندان توسعه و بهینه شد. برای مثال در سال 1957 نسخه‌ دیگری از این الگوریتم به عنوان الگوریتم استاندارد خوشه‌بندی k-میانگین، توسط «لوید» (Lloyd) در آزمایشگاه‌های بل (Bell Labs) برای کدگذاری پالس‌ها ایجاد شد که بعدها در سال 1982 منتشر گردید. این نسخه از الگوریتم خوشه‌بندی، امروزه در بیشتر نرم‌افزارهای رایانه‌ای که عمل خوشه‌بندی k-میانگین را انجام می‌دهند به صورت استاندارد اجرا می‌شود. در سال 1956 «فورجی» (W.Forgy) به طور مستقل همین روش را ارائه کرد و به همین علت گاهی این الگوریتم را با نام لوید-فورجی می‌شناسند. همچنین روش هارتیگان- ونگ (Hartigan-Wong) که در سال ۱۹۷۹ معرفی شد یکی از روش‌هایی است که در تحقیقات و بررسی‌های داده‌کاوی مورد استفاده قرار می‌گیرد. تفاوت در این الگوریتم‌ها در مرحله آغازین و شرط همگرایی الگوریتم‌ها است ولی در بقیه مراحل و محاسبات مانند یکدیگر عمل می‌کنند. به همین علت همگی را الگوریتم‌های خوشه‌بندی k-میانگین می‌نامند. روش خوشه‌بندی k-میانگین فرض کنید مشاهدات ( x 1 , x 2 , … , x n ) که دارای d بعد هستند را باید به k بخش یا خوشه تقسیم کنیم. این بخش‌ها یا خوشه‌ها را با مجموعه‌ای به نام S = { S 1 , S 2 , … , S k } می‌شناسیم. اعضای خوشه‌ها باید به شکلی از مشاهدات انتخاب شوند که تابع «مجموع مربعات درون خوشه‌ها» (within-cluster sum of squares- WCSS) که در حالت یک بعدی شبیه واریانس است، کمینه شود. بنابراین، تابع هدف در این الگوریتم به صورت زیر نوشته می‌شود. a r g m i n S k ∑ i = 1 ∑ x ∈ S i ∥ x − μ i ∥ 2 = a r g m i n S k ∑ i = 1 | S i | Var S i در اینجا منظور از μ i میانگین خوشه S i و | S i | تعداد اعضای خوشه iام است. البته می‌توان نشان داد که کمینه کردن این مقدار به معنی بیشینه‌سازی میانگین مربعات فاصله بین نقاط در خوشه‌های مختلف (between-Cluster sum of Squares- BCSS) است زیرا طبق قانون واریانس کل، با کم شدن مقدار WCSS، مقدار BCSS افزایش می‌یابد، زیرا واریانس کل ثابت است. در ادامه به بررسی روش خوشه بندی k-میانگین به روش لوید-فورجی (استاندارد) و هارتیگان-ونگ می‌پردازیم. خوشه‌بندی k-میانگین با الگوریتم لوید (Lloyd’s Algorithm) به عنوان یک الگوریتم استاندارد برای خوشه‌بندی k-میانگین از الگوریتم لوید بخصوص در زمینه علوم کامپیوتر، استفاده می‌شود. ابتدا به علائمی که در این رابطه به کار می‌رود، اشاره می‌کنیم. m ( i ) j : میانگین مقدارهای مربوط به خوشه jام در تکرار iام از الگوریتم را با این نماد نشان می‌دهیم. S ( i ) j : مجموعه اعضای خوشه jام در تکرار iام الگوریتم. الگوریتم لوید را با توجه به نمادهای بالا می‌توان به دو بخش تفکیک کرد. ۱- بخش مقدار دهی ( A s s i g n m e n t S t e p )، ۲- بخش به روز رسانی (Update Step). حال به بررسی مراحل اجرای این الگوریتم می‌پردازیم. در اینجا فرض بر این است که نقاط مرکزی اولیه یعنی m ( 1 ) 1 , m ( 1 ) 2 , ⋯ , m ( 1 ) k داده شده‌اند. بخش مقدار دهی: هر مشاهده یا شی را به نزدیکترین خوشه نسبت می‌دهیم. به این معنی که فاصله اقلیدسی هر مشاهده از مراکز، اندازه گرفته شده سپس آن مشاهده عضو خوشه‌ای خواهد شد که کمترین فاصله اقلیدسی را با مرکز آن خوشه دارد. این قانون را به زبان ریاضی به صورت S ( t ) i = { x p : ∥ ∥ x p − m ( t ) i ∥ ∥ 2 ≤ ∥ ∥ x p − m ( t ) j ∥ ∥ 2 ∀ j , 1 ≤ j ≤ k } می‌نویسیم. بخش به روز رسانی: میانگین خوشه‌های جدید محاسبه می‌شود. در این حالت داریم: m ( t + 1 ) i = 1 | S ( t ) i | ∑ x j ∈ S ( t ) i x j توجه داشته باشید که منظور از | S ( t ) i | تعداد اعضای خوشه iام است. الگوریتم زمانی متوقف می‌شود که مقدار برچسب عضویت مشاهدات تغییری نکند. البته در چنین حالتی هیچ تضمینی برای رسیدن به جواب بهینه (با کمترین مقدار برای تابع هزینه) وجود ندارد. کاملا مشخص است که در رابطه بالا،‌ فاصله اقلیدسی بین هر نقطه و مرکز خوشه ملاک قرار گرفته است. از این جهت از میانگین و فاصله اقلیدسی استفاده شده که مجموع فاصله اقلیدسی نقاط از میانگینشان کمترین مقدار ممکن نسبت به هر نقطه دیگر است. نکته: ممکن است فاصله اقلیدسی یک مشاهده از دو مرکز یا بیشتر، برابر باشد ولی در این حالت آن شئ فقط به یکی از این خوشه‌ها تعلق خواهد گرفت. تصویر زیر یک مثال برای همگرایی الگوریتم لوید محسوب می‌شود که مراحل اجرا در آن دیده می‌شود. همانطور که مشخص است الگوریتم با طی ۱۴ مرحله به همگرایی می‌رسد و دیگر میانگین خوشه‌ها تغییری نمی‌یابد. البته ممکن است که این نقاط نتیجه تابع هزینه را بطور کلی (Global) کمینه نکنند زیرا روش k-میانگین بهینه‌سازی محلی (Local Optimization) را به کمک مشتق‌گیری و محاسبه نقاط اکستریمم اجرا می‌کند. K-means_convergence همگرایی الگوریتم k-میانگین نکته: به نقاط مرکزی هر خوشه مرکز (Centroid) گفته می‌شود. ممکن است این نقطه یکی از مشاهدات یا غیر از آن‌ها باشد. مشخص است که در الگوریتم لوید، k مشاهده به عنوان مرکز خوشه‌ها (Centroids) در مرحله اول انتخاب شده‌اند ولی در مراحل بعدی، مقدار میانگین هر خوشه نقش مرکز را بازی می‌کند. خوشه‌بندی k-میانگین با الگوریتم هارتیگان-ونگ (Hartigan-Wong) یکی از روش‌های پیشرفته و البته با هزینه محاسباتی زیاد در خوشه‌بندی k-میانگین، الگوریتم هارتیگان-ونگ است. برای آشنایی با این الگوریتم بهتر است ابتدا در مورد نمادهایی که در ادامه خواهید دید توضیحی ارائه شود. ϕ ( S j ) : از این نماد برای نمایش «تابع هزینه» برای خوشه S j استفاده می‌کنیم. این تابع در خوشه‌بندی k-میانگین برابر است با: ϕ ( S i ) = ∑ x ∈ S j ( x − μ j ) 2 S j : از آنجایی که هدف از این الگوریتم، تفکیک اشیاء به k گروه مختلف است، گروه‌ها یا خوشه‌ها در مجموعه‌ای با نام S قرار دارند و داریم، S = { S 1 , S 2 , ⋯ , S k } . μ j : برای نمایش میانگین خوشهjام از این نماد استفاده می‌شود. بنابراین خواهیم داشت: μ j = ∑ x ∈ S j x n j n j : این نماد تعداد اعضای خوشه jام را نشان می‌دهد. بطوری که j = { 1 , 2 , ⋯ , k } است. البته مشخص است که در اینجا تعداد خوشه‌ها را با k‌ نشان داده‌ایم. مراحل اجرای الگوریتم در خوشه‌بندی k-میانگین با الگوریتم هارتیگان می‌توان مراحل اجرا را به سه بخش تقسیم کرد: ۱- بخش مقدار دهی اولیه ( A s s i g n m e n t S t e p ) ، ۲- بخش به روز رسانی ( U p d a t e S t e p )، ۳- بخش نهایی (Termination). در ادامه به بررسی این بخش‌ها پرداخته می‌شود. بخش مقدار دهی اولیه: در الگوریتم هارتیگان-ونگ، ابتدا مشاهدات و یا اشیاء به طور تصادفی به k گروه یا خوشه تقسیم می‌شوند. به این کار مجموعه S با اعضایی به صورت { S j } j ∈ { i , ⋯ , k } مشخص می‌شود. بخش به روز رسانی: فرض کنید که مقدارهای n و m از اعداد ۱ تا k انتخاب شده باشد. مشاهده یا شیئ از خوشه nام را در نظر بگیرید که تابع Δ ( m , n , x ) = ϕ ( S n ) + ϕ ( S m ) − Φ ( S n ∖ { x } ) − ϕ ( S m ∪ { x } ) را کمینه سازد، در چنین حالتی مقدار x از خوشه nام به خوشه mام منتقل می‌شود. به این ترتیب شی مورد نظر در S m قرار گرفته و خواهیم داشت x ∈ S m . بخش نهایی: زمانی که به ازای همه n,m,x مقدار Δ ( m , n , x ) بزرگتر از صفر باشد، الگوریتم خاتمه می‌یابد. نکته: منظور از نماد ϕ ( S n ∖ { x } ) محاسبه تابع هزینه در زمانی است که مشاهده x از مجموعه S n خارج شده باشد. همچنین نماد ϕ ( S m ∪ { x } ) به معنی محاسبه تابع هزینه در زمانی است که مشاهده x به خوشه S m اضافه شده باشد. در تصویر زیر مراحل اجرای الگوریتم هارتیگان به خوبی نمایش داده شده است. هر تصویر بیانگر یک مرحله از اجرای الگوریتم است. نقاط رنگی نمایش داده شده، همان مشاهدات هستند. هر رنگ نیز بیانگر یک خوشه است. در تصویر اول مشخص است که در بخش اول از الگوریتم به طور تصادفی خوشه‌بندی صورت پذیرفته. ولی در مراحل بعدی خوشه‌ها اصلاح شده و در انتها به نظر می‌رسد که بهترین تفکیک برای مشاهدات رسیده‌ایم. در تصویر آخر نیز مشخص است که مراکز خوشه‌ها، محاسبه و ثابت شده و دیگر بهینه‌سازی صورت نخواهد گرفت. به این ترتیب پاسخ‌های الگوریتم با طی تکرار ۵ مرحله به همگرایی می‌رسد. hartigan algorithm الگوریتم هارتیگان بخش مقدار دهی اولیه hartigan algorithm الگوریتم هارتیگان تکرار ۱ hartigan algorithm الگوریتم هارتیگان تکرار ۲ hartigan algorithm الگوریتم هارتیگان تکرار ۳ hartigan algorithm الگوریتم هارتیگان تکرار ۴ hartigan algorithm الگورییتم هارتیگان تکرار ۵ اجرای این الگوریتم‌ها با استفاده از دستورات زبان برنامه‌نویسی R برای استفاده از دستورات و فرمان‌های مربوط به خوشه‌بندی k-میانگین، باید بسته یا Package مربوط به خوشه‌بندی kmeans به اسم stats را در R نصب کرده باشد. البته از آنجایی این بسته بسیار پرکاربرد است،‌ معمولا به طور خودکار فراخوانی شده است. کدهای زیر نشانگر استفاده از الگوریتم خوشه‌بندی توسط روش‌های مختلف آن است. library(stats) data=iris[,1:4] method=c("Hartigan-Wong", "Lloyd", "MacQueen") k=3 kresults1=kmeans(data,k,algorithm = method[1]) kresults2=kmeans(data,k,algorithm=method[2]) kresults3=kmeans(data,k,algorithm=method[3]) kresults1 kresults2 kresults3 1 2 3 4 5 6 7 8 9 10 11 12 library(stats) data=iris[,1:4] method=c("Hartigan-Wong", "Lloyd", "MacQueen") k=3 kresults1=kmeans(data,k,algorithm = method[1]) kresults2=kmeans(data,k,algorithm=method[2]) kresults3=kmeans(data,k,algorithm=method[3]) kresults1 kresults2 kresults3 با توجه به داده‌های iris که مربوط به اندازه و ابعاد کاسبرگ و گلبرگ سه نوع گل مختلف است، خوشه‌بندی به سه دسته انجام شده است. اطلاعات مربوط به ۱۰ سطر اول این مجموعه داده،‌ به صورت زیر است. با اجرای کدهای نوشته شده، خوشه‌بندی انجام شده و نتابج تولید می‌شوند. به عنوان مثال می‌توان خروجی را برای kresult1 که انجام خوشه بندی توسط الگوریتم هارتیگان است به صورت زیر مشاهده کرد: iris clustering همانطور که دیده می‌شود، در سطر اول تعداد اعضای هر خوشه، نمایش داده شده است. در بخش دوم که با سطر ۱ و ۲ و ۳ مشخص شده،‌ مراکز هر سه خوشه برحسب ویژگی‌های (طول و عرض کاسبرگ و طول و عرض گلبرگ) محاسبه شده و در قسمت Cluster Vector نیز برچسب خوشه هر کدام از مشاهدات دیده می‌شود. در انتها نیز مجموع مربعات فاصله درون خوشه‌ای (مجموع فاصله هر مشاهده از مرکز خوشه) استخراج شده و درصد یا شاخص ارزیابی خوشه‌بندی بر اساس نسبت مربعات بین خوشه‌ها به مربعات کل دیده می‌شود. این مقدار برای این حالت برابر ۸۸.۴٪ است که نشان می‌دهد بیشتر پراکندگی (total_ss) توسط پراکندگی بین خوشه‌ها (between_ss) بیان شده است. پس به نظر خوشه‌بندی مناسب خواهد بود. پس اختلاف بین گروه‌ها ناشی از خوشه‌های است که مشاهدات را به دسته‌‌های جداگانه تفکیک کرده. همچنین در کدها مشخص است که تعداد خوشه‌های در متغیر k ثبت و به کار رفته است. در شکل دیگری از دستور kmeans می‌توان به جای معرفی تعداد خوشه‌ها از مراکز دلخواه که با تعداد خوشه‌ها مطابقت دارد، استفاده کرد. برای مثال اگر برنامه به صورت زیر نوشته شود، الگوریتم ابتدا نقاط معرفی شده را به عنوان نقاط مرکزی (Centroids) به کار گرفته و سپس مراحل بهینه سازی را دنبال می‌کند. از آنجا که سه نقطه مبنا قرار گرفته، الگوریتم متوجه می‌شود که باید مشاهدات به سه خوشه تفکیک شود. library(stats) data=iris[,1:4] method=c("Hartigan-Wong", "Lloyd", "MacQueen") c1=c(6,4,5,3) c2=c(5,3,1,0) c3=c(6,2,4,2) centers=rbind(c1,c2,c3) kresults1=kmeans(x = data,centers = centers,algorithm = method[1]) kresults2=kmeans(x = data,centers = centers,algorithm=method[2]) kresults3=kmeans(x = data,centers = centers,algorithm=method[3]) kresults1 kresults2 kresults3 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 library(stats) data=iris[,1:4] method=c("Hartigan-Wong", "Lloyd", "MacQueen") c1=c(6,4,5,3) c2=c(5,3,1,0) c3=c(6,2,4,2) centers=rbind(c1,c2,c3) kresults1=kmeans(x = data,centers = centers,algorithm = method[1]) kresults2=kmeans(x = data,centers = centers,algorithm=method[2]) kresults3=kmeans(x = data,centers = centers,algorithm=method[3]) kresults1 kresults2 kresults3 در تصویر زیر نتیجه خوشه بندی k-میانگین را برای داده‌های iris توسط یک نمودار مشاهده می‌کنید. البته باید توجه داشت که این نمودار دو بعدی است در حالیکه داده‌ها، دارای چهار ویژگی هستند. به کمک روش‌های آماری مانند تجزیه به مولفه‌های اصلی (PCA) ابعاد مسئله کاهش یافته تا در سه بعد روی نمودار نمایش داده شود. سمت راست تصویر گروه‌های واقعی و سمت چپ نتیجه خوشه‌بندی دیده می‌شود. نقاطی که در خوشه‌ها به درستی تشخیص داده نشده‌اند، باعث افزایش خطای خوشه‌بندی خواهند شد. کاربردها از الگوریتم خوشه‌بندی k-میانگین در «بخش‌بندی بازار کسب و کار» (market Segmentation)، «دسته‌بندی مشتریان» (Customer Segmentation)، «بینایی رایانه‌ای» (Computer Vision) و «زمین‌آمار (Geostatistics) استفاده می شود. برای مثال در تشخیص تعداد رنگ و یا فشرده سازی تصاویر برحسب رنگ‌ها می‌توان از این الگوریتم‌ها استفاده کرد. در تصویر بالا گل رز زرد رنگی دیده می‌شود که در یک محیط سبز قرار گرفته است. با استفاده از الگوریتم‌های خوشه‌بندی می‌توان تعداد رنگ‌ها را کاهش داده و از حجم تصاویر کاست. در تصویر زیر دسته بندی رنگ‌های گل رز دیده می‌شود. در این تصویر، هر طیف رنگ براساس میزان رنگ قرمز و سبز، بوسیله «سلول‌های ورونوی» (Voronoi Cell) تقسیم‌بندی شده است. این تقسیم‌بندی می‌تواند توسط الگوریتم‌ها خوشه‌بندی k-میانگین صورت گرفته باشد. در کل تصویر نیز، طیف رنگ‌های مختلف برای تصویر گل رز در یک «نمودار ورونوی» (Voronoi diagram) نمایش داده شده است که خوشه‌ها را بیان می‌کند. معایب و مزایای خوشه‌بندی k-میانگین از آنجایی که در این روش خوشه‌بندی، محاسبه فاصله بین نقاط توسط تابع فاصله اقلیدسی انجام می‌شود، از این الگوریتم‌ها به صورت استاندارد، فقط برای مقدارهای عددی (و نه ویژگی‌های کیفی) می‌توان استفاده کرد. از طرف دیگر با توجه به محاسبات ساده و سریع آن‌ها،‌ پرکاربرد و موثر است. از طرف دیگر نسخه‌های تعمیم یافته از روش خوشه بندی k-میانگین نیز وجود دارد که با توابع فاصله دیگر مانند فاصله منهتن و یا فاصله‌هایی که برای داده‌های باینری قابل استفاده است، مراحل خوشه‌بندی را انجام می‌دهد. به منظور ارزیابی نتایج خوشه‌بندی از معیارهای متفاوتی کمک گرفته می‌شود. ممکن است از قبل برچسب خوشه‌ها مشخص باشد و بخواهیم کارایی الگوریتم را با توجه به مقایسه برچسب‌های واقعی و حاصل از خوشه‌بندی، اندازه‌گیری کنیم. در این حالت، شاخص‌های ارزیابی بیرونی، بهترین راهنما و معیار برای سنجش صحت نتایج خوشه‌بندی محسوب می‌شوند. معمولا به این برچسب‌ها، استاندارد طلایی (Golden Standard) و در کل چنین عملی را ارزیابی Benchmark می‌گویند. برای مثال شاخص رَند (Rand Index) یکی از این معیارها و شاخص‌های بیرونی است که از محبوبیت خاصی نیز برخوردار است. از طرف دیگر اگر هیچ اطلاعات اولیه از ساختار و دسته‌بندی مشاهدات وجود نداشته باشد، فقط ملاک ارزیابی، می‌تواند اندازه‌هایی باشد که میزان شباهت درون خوشه‌ها و یا عدم شباهت یا فاصله بین خوشه‌ها را اندازه می‌گیرند. بنابراین برای انتخاب بهتر و موثرترین روش خوشه‌بندی از میزان شباهت درون خوشه‌ها و شباهت بین خوشه‌ها استفاده می‌شود. روشی که دارای میزان شباهت بین خوشه‌ای کم و شباهت درون خوشه‌ای زیاد باشد مناسب‌ترین روش خواهد بود. این معیارها را به نام شاخص‌های ارزیابی درونی می‌شناسیم. به عنوان مثال شاخص نیم‌رخ (silhouette) یکی از این معیارها است که شاخصی برای سنجش مناسب بودن تعلق هر مشاهده به خوشه‌اش ارائه می‌دهد. به این ترتیب معیاری برای اندازه‌گیری کارایی الگوریتم خوشه‌بندی بدست می‌آید. اگر این مطلب برایتان مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند: مجموعه آموزش‌های یادگیری ماشین و بازشناسی الگو مجموعه آموزش‌های آمار، احتمالات و داده‌کاوی آموزش خوشه بندی K میانگین (K-Means) با نرم افزار SPSS آموزش خوشه بندی تفکیکی با نرم افزار R آموزش خوشه بندی سلسله مراتبی با SPSS آشنایی با خوشه‌بندی (Clustering) و شیوه‌های مختلف آن روش‌ های ارزیابی نتایج خوشه‌ بندی (Clustering Performance) — معیارهای درونی (Internal Index) روش‌ های ارزیابی نتایج خوشه‌ بندی (Clustering Performance) — معیارهای بیرونی (External Index) ^^ telegram twitter به اشتراک بگذارید: منبع وبلاگ فرادرسWikipedia بر اساس رای 1 نفر آیا این مطلب برای شما مفید بود؟ بلیخیر نظر شما چیست؟ نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند * متن نظر * نام شما * ایمیل شما * پایتخت ایران کدام شهر است؟ برچسب‌ها clusterClusteringclustering algorithmcost functiondata miningforgy algorithmhartigan-wong algorithmk-meanslloyd algorithmmaximizationMcQueen algorithmminimizationpartitioning algorithmunsupervise learningتابع هدفتابع هزینهتعداد خوشهخوشه بندیخوشه بندی K میانگینخوشه بندی در آمارخوشه‌بندیخوشه‌بندی k-میانگینمربعات بین خوشهمربعات درون خوشهمعیارهای ارزیابی خوشه عضویت در خبرنامه ایمیل * آموزش برنامه نویسی آموزش متلب Matlab نرم‌افزارهای مهندسی برق نرم‌افزارهای مهندسی عمران نرم‌افزارهای مهندسی مکانیک نرم‌افزارهای مهندسی صنایع

 

معمولا زمانی که هدف کمینه‌سازی باشد، تابع هدف را «تابع هزینه» (Cost Function) نیز می‌نامند.

روش خوشه بندی k-میانگین، توسط «مک‌کوئین» (McQueen) جامعه شناس و ریاضیدان در سال ۱۹۶۵ ابداع و توسط دیگر دانشمندان توسعه و بهینه شد. برای مثال در سال 1957 نسخه‌ دیگری از این الگوریتم به عنوان الگوریتم استاندارد خوشه‌بندی k-میانگین، توسط «لوید» (Lloyd) در آزمایشگاه‌های بل (Bell Labs) برای کدگذاری پالس‌ها ایجاد شد که بعدها در سال 1982 منتشر گردید. این نسخه از الگوریتم خوشه‌بندی، امروزه در بیشتر نرم‌افزارهای رایانه‌ای که عمل خوشه‌بندی k-میانگین را انجام می‌دهند به صورت استاندارد اجرا می‌شود. در سال 1956 «فورجی» (W.Forgy) به طور مستقل همین روش را ارائه کرد و به همین علت گاهی این الگوریتم را با نام لوید-فورجی می‌شناسند. همچنین روش هارتیگان- ونگ (Hartigan-Wong) که در سال ۱۹۷۹ معرفی شد یکی از روش‌هایی است که در تحقیقات و بررسی‌های داده‌کاوی مورد استفاده قرار می‌گیرد. تفاوت در این الگوریتم‌ها در مرحله آغازین و شرط همگرایی الگوریتم‌ها است ولی در بقیه مراحل و محاسبات مانند یکدیگر عمل می‌کنند. به همین علت همگی را الگوریتم‌های خوشه‌بندی k-میانگین می‌نامند.

روش خوشه‌بندی k-میانگین

فرض کنید مشاهدات  که دارای d بعد هستند را باید به k بخش یا خوشه تقسیم کنیم. این بخش‌ها یا خوشه‌ها را با مجموعه‌ای به نام  می‌شناسیم. اعضای خوشه‌ها باید به شکلی از مشاهدات انتخاب شوند که تابع «مجموع مربعات درون خوشه‌ها» (within-cluster sum of squares- WCSS) که در حالت یک بعدی شبیه واریانس است، کمینه شود.

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

الگوریتم K-means

در اینجا منظور از  میانگین خوشه  و   تعداد اعضای خوشه iام است. البته می‌توان نشان داد که کمینه کردن این مقدار به معنی بیشینه‌سازی میانگین مربعات فاصله بین نقاط در خوشه‌های مختلف (between-Cluster sum of Squares- BCSS) است زیرا طبق قانون واریانس کل، با کم شدن مقدار WCSS، مقدار BCSS افزایش می‌یابد، زیرا واریانس کل ثابت است.

در ادامه به بررسی روش خوشه بندی k-میانگین به روش لوید-فورجی (استاندارد) و هارتیگان-ونگ می‌پردازیم.

خوشه‌بندی k-میانگین با الگوریتم لوید (Lloyd’s Algorithm)

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

mj(i): میانگین مقدارهای مربوط به خوشه jام در تکرار iام از الگوریتم را با این نماد نشان می‌دهیم.

Sj(i): مجموعه اعضای خوشه jام در تکرار iام الگوریتم.

الگوریتم لوید را با توجه به نمادهای بالا می‌توان به دو بخش تفکیک کرد. ۱- بخش مقدار دهی ()، ۲- بخش به روز رسانی (Update Step). حال به بررسی مراحل اجرای این الگوریتم می‌پردازیم. در اینجا فرض بر این است که نقاط مرکزی اولیه یعنی  داده شده‌اند.

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

توجه داشته باشید که منظور از Si(t| تعداد اعضای خوشه iام است. الگوریتم زمانی متوقف می‌شود که مقدار برچسب عضویت مشاهدات تغییری نکند. البته در چنین حالتی هیچ تضمینی برای رسیدن به جواب بهینه (با کمترین مقدار برای تابع هزینه) وجود ندارد. کاملا مشخص است که در رابطه بالا،‌ فاصله اقلیدسی بین هر نقطه و مرکز خوشه ملاک قرار گرفته است. از این جهت از میانگین و فاصله اقلیدسی استفاده شده که مجموع فاصله اقلیدسی نقاط از میانگینشان کمترین مقدار ممکن نسبت به هر نقطه دیگر است.

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

تصویر زیر یک مثال برای همگرایی الگوریتم لوید محسوب می‌شود که مراحل اجرا در آن دیده می‌شود. همانطور که مشخص است الگوریتم با طی ۱۴ مرحله به همگرایی می‌رسد و دیگر میانگین خوشه‌ها تغییری نمی‌یابد. البته ممکن است که این نقاط نتیجه تابع هزینه را بطور کلی (Global) کمینه نکنند زیرا روش k-میانگین بهینه‌سازی محلی (Local Optimization) را به کمک مشتق‌گیری و محاسبه نقاط اکستریمم اجرا می‌کند.

 

K-means_convergence

همگرایی الگوریتم k-میانگین

 

نکته: به نقاط مرکزی هر خوشه مرکز (Centroid) گفته می‌شود. ممکن است این نقطه یکی از مشاهدات یا غیر از آن‌ها باشد. مشخص است که در الگوریتم لوید، k مشاهده به عنوان مرکز خوشه‌ها (Centroids) در مرحله اول انتخاب شده‌اند ولی در مراحل بعدی، مقدار میانگین هر خوشه نقش مرکز را بازی می‌کند.

خوشه‌بندی k-میانگین با الگوریتم هارتیگان-ونگ (Hartigan-Wong)

یکی از روش‌های پیشرفته و البته با هزینه محاسباتی زیاد در خوشه‌بندی k-میانگین، الگوریتم هارتیگان-ونگ است. برای آشنایی با این الگوریتم بهتر است ابتدا در مورد نمادهایی که در ادامه خواهید دید توضیحی ارائه شود.

فرمول 4  از این نماد برای نمایش «تابع هزینه» برای خوشه فرمول 5 استفاده می‌کنیم. این تابع در خوشه‌بندی k-میانگین برابر است با:

فرمول 6

 

فرمول 5 : از آنجایی که هدف از این الگوریتم، تفکیک اشیاء به k گروه مختلف است، گروه‌ها یا خوشه‌ها در مجموعه‌ای با نام S قرار دارند و داریم، فرمول 7

فرمول 8: برای نمایش میانگین خوشهjام از این نماد استفاده می‌شود. بنابراین خواهیم داشت:

فرمول 9

فرمول 11این نماد تعداد اعضای خوشه jام را نشان می‌دهد. بطوری که فرمول 10  است. البته مشخص است که در اینجا تعداد خوشه‌ها را با k‌ نشان داده‌ایم.

مراحل اجرای الگوریتم

در خوشه‌بندی k-میانگین با الگوریتم هارتیگان می‌توان مراحل اجرا را به سه بخش تقسیم کرد: ۱- بخش مقدار دهی اولیه (Assignment Step(   ،- ۲ بخش به روز رسانی (Update Step)، ۳- بخش نهایی (Termination). در ادامه به بررسی این بخش‌ها پرداخته می‌شود.

  1. بخش مقدار دهی اولیه: در الگوریتم هارتیگان-ونگ، ابتدا مشاهدات و یا اشیاء به طور تصادفی به k گروه یا خوشه تقسیم می‌شوند. به این کار مجموعه S با اعضایی به صورت فرمول 12  مشخص می‌شود.
  2. بخش به روز رسانی: فرض کنید که مقدارهای n و m از اعداد ۱ تا k انتخاب شده باشد. مشاهده یا شیئ از خوشه nام را در نظر بگیرید که تابع  فرمول 13 را کمینه سازد، در چنین حالتی مقدار x از خوشه nام به خوشه mام منتقل می‌شود. به این ترتیب شی مورد نظر در  فرمول 20 قرار گرفته و خواهیم داشت  فرمول 15 .
  3. بخش نهایی: زمانی که به ازای همه n,m,x مقدار  فرمول 16  بزرگتر از صفر باشد، الگوریتم خاتمه می‌یابد.

نکته: منظور از نماد  فرمول 17  محاسبه تابع هزینه در زمانی است که مشاهده x از مجموعه  فرمول 18  خارج شده باشد. همچنین نماد  فرمول 19 به معنی محاسبه تابع هزینه در زمانی است که مشاهده x به خوشه  فرمول 20  اضافه شده باشد.

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

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

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

 

hartigan-step-1

الگوریتم هارتیگان بخش مقدار دهی اولیه

hartigan-step-2

الگوریتم هارتیگان تکرار 1

 

hartigan-step-3

الگوریتم هارتیگان تکرار 2

 

hartigan-step-5

الگوریتم هارتیگان تکرار 3

 

hartigan-step-4

الگوریتم هارتیگان تکرار 4

 

hartigan-step-6

الگوریتم هارتیگان تکرار 5

 

اجرای این الگوریتم‌ها با استفاده از دستورات زبان برنامه‌نویسی R

برای استفاده از دستورات و فرمان‌های مربوط به خوشه‌بندی k-میانگین، باید بسته یا Package مربوط به خوشه‌بندی kmeans به اسم stats را در R نصب کرده باشد. البته از آنجایی این بسته بسیار پرکاربرد است،‌ معمولا به طور خودکار فراخوانی شده است. کدهای زیر نشانگر استفاده از الگوریتم خوشه‌بندی توسط روش‌های مختلف آن است.

library(stats)
data=iris[,1:4]
method=c("Hartigan-Wong", "Lloyd",
"MacQueen")
k=3
kresults1=kmeans(data,k,algorithm = method[1])
kresults2=kmeans(data,k,algorithm=method[2])
kresults3=kmeans(data,k,algorithm=method[3])

kresults1
kresults2
kresults3
با توجه به داده‌های iris که مربوط به اندازه و ابعاد کاسبرگ و گلبرگ سه نوع گل مختلف است، خوشه‌بندی به سه دسته انجام شده است. اطلاعات مربوط به ۱۰ سطر اول این مجموعه داده،‌ به صورت زیر است.

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

iris clustering

همانطور که دیده می‌شود، در سطر اول تعداد اعضای هر خوشه، نمایش داده شده است. در بخش دوم که با سطر ۱ و ۲ و ۳ مشخص شده،‌ مراکز هر سه خوشه برحسب ویژگی‌های (طول و عرض کاسبرگ و طول و عرض گلبرگ) محاسبه شده و در قسمت Cluster Vector نیز برچسب خوشه هر کدام از مشاهدات دیده می‌شود. در انتها نیز مجموع مربعات فاصله درون خوشه‌ای (مجموع فاصله هر مشاهده از مرکز خوشه) استخراج شده و درصد یا شاخص ارزیابی خوشه‌بندی بر اساس نسبت مربعات بین خوشه‌ها به مربعات کل دیده می‌شود. این مقدار برای این حالت برابر ۸۸.۴٪ است که نشان می‌دهد بیشتر پراکندگی (total_ss) توسط پراکندگی بین خوشه‌ها (between_ss) بیان شده است. پس به نظر خوشه‌بندی مناسب خواهد بود. پس اختلاف بین گروه‌ها ناشی از خوشه‌های است که مشاهدات را به دسته‌‌های جداگانه تفکیک کرده.

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

 

library(stats)
data=iris[,1:4]
method=c("Hartigan-Wong", "Lloyd",
         "MacQueen")
c1=c(6,4,5,3)
c2=c(5,3,1,0)
c3=c(6,2,4,2)
centers=rbind(c1,c2,c3)
kresults1=kmeans(x = data,centers = centers,algorithm = method[1])
kresults2=kmeans(x = data,centers = centers,algorithm=method[2])
kresults3=kmeans(x = data,centers = centers,algorithm=method[3])

kresults1
kresults2
kresults3
در تصویر زیر نتیجه خوشه بندی k-میانگین را برای داده‌های iris توسط یک نمودار مشاهده می‌کنید. البته باید توجه داشت که این نمودار دو بعدی است در حالیکه داده‌ها، دارای چهار ویژگی هستند. به کمک روش‌های آماری مانند تجزیه به مولفه‌های اصلی (PCA) ابعاد مسئله کاهش یافته تا در سه بعد روی نمودار نمایش داده شود. سمت راست تصویر گروه‌های واقعی و سمت چپ نتیجه خوشه‌بندی دیده می‌شود. نقاطی که در خوشه‌ها به درستی تشخیص داده نشده‌اند، باعث افزایش خطای خوشه‌بندی خواهند شد.

کاربردها

از الگوریتم خوشه‌بندی k-میانگین در «بخش‌بندی بازار کسب و کار» (market Segmentation)، «دسته‌بندی مشتریان» (Customer Segmentation)، «بینایی رایانه‌ای» (Computer Vision) و «زمین‌آمار (Geostatistics) استفاده می شود. برای مثال در تشخیص تعداد رنگ و یا فشرده سازی تصاویر برحسب رنگ‌ها می‌توان از این الگوریتم‌ها استفاده کرد.

 

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

 

 

در این تصویر، هر طیف رنگ براساس میزان رنگ قرمز و سبز، بوسیله «سلول‌های ورونوی» (Voronoi Cell) تقسیم‌بندی شده است. این تقسیم‌بندی می‌تواند توسط الگوریتم‌ها خوشه‌بندی k-میانگین صورت گرفته باشد. در کل تصویر نیز، طیف رنگ‌های مختلف برای تصویر گل رز در یک «نمودار ورونوی» (Voronoi diagram) نمایش داده شده است که خوشه‌ها را بیان می‌کند.

 

خوشه بندی k میانگین (k-means Clustering) قسمت 1
خوشه بندی k میانگین (k-means Clustering) قسمت 2

چکیده

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

ﮐﻠﯿﺪواژه ﻫﺎ

اﻧﻄﺒﺎق ﺗﺼﻮﯾﺮ، ﺷﻨﺎﺳﺎﯾﯽ وﯾﮋﮔﯽ ﻫﺎ، ﺗﻄﺒﯿﻖ، ﺑﺮآورد ﻣﺪل ﺗﺒﺪﯾﻞ، اﻟﮕﻮرﯾﺘﻢ SIFT

مقدمه

اﻧﻄﺒﺎق ﺗﺼﻮﯾﺮ، ﻓﺮآﯾﻨﺪ روی ﻫﻢ ﮔﺬاﺷﺘﻦ دو ﯾﺎ ﭼﻨﺪ ﺗﺼﻮﯾﺮ از ﯾﮏ صحنه است ﮐﻪ در ﺷﺮاﯾﻂ ﻣﺨﺘﻠﻒ ﺗﺼﻮﯾﺮﺑﺮداری (زﻣﺎن ﻫﺎی ﻣﺘﻔﺎوت، زواﯾﺎی ﻣﺘﻔﺎوت، ﺣﺴﮕﺮ ﻫﺎی ﻣﺘﻔﺎوت و ﻧﻮع و ﻣﺎﻫﯿِﺖ ﻣﻨﻄﻘﻪ ی ﺗﺼﻮﯾﺮﺑﺮداری ﺷﺪه) ﮔﺮﻓﺘﻪ ﺷﺪه اﻧﺪ و اﯾﻦ ﻓﺮآﯾﻨﺪ از ﻧﻈﺮ ﻫﻨﺪﺳﯽ، دو ﺗﺼﻮﯾﺮ ﻣﺮﺟﻊ و ﺣﺲ ﺷﺪه را ﻫﻢ ﺗﺮاز می ﮐﻨﺪ. اﯾﻦ ﻓﺮآﯾﻨﺪ، ﯾﮏ ﻣﺮﺣﻠﻪ ی ﭘﯿﺶ ﭘﺮدازش در ﺗﺤﻠﯿﻞ ﺗﺼﺎوﯾﺮاﺳﺖ.

در واﻗﻊ ﺷﺮاﯾﻂ ﻣﺨﺘﻠﻒ ﺗﺼﻮﯾﺮﺑﺮداری ﺳﺒﺐ اﯾﺠﺎد اﺧﺘﻼﻓﺎت ﻗﺎﺑﻞ ﺗﻮﺟﻪ ﺑﯿﻦ ﺗﺼﺎوﯾﺮمی ﺷﻮد و ﺑﻪ ﺻﻮرت ﮐﻠﯽ اﯾﻦ اﺧﺘﻼف را می ﺗﻮان ﺑﻪ ﭼﻬﺎردﺳﺘﻪ ی ﻫﻨﺪﺳﯽ، ﻣﺸﮑﻼت رادﯾﻮﻣﺘﺮی، ﻣﺸﮑﻼت ﺑﺎﻓﺖ و ﺗﻐﯿﯿﺮ ﻣﻨﺎﻇﺮ ﺗﻘﺴﯿﻢ ﮐﺮد. مشکلاتی ﻣﺎﻧﻨﺪ اﺧﺘﻼﻓﺎت ﻣﻘﯿﺎس ﺗﺼﺎوﯾﺮ، اﺧﺘﻼﻓﺎت ﭼﺮﺧﺸﯽ ﺗﺼﺎوﯾﺮ و ﺗﻐﯿﯿﺮ ﺷﮑﻞ ﻫﺎی ﻧﺎﺷﯽ از ﺗﻐﯿﯿﺮ ﻣﻮﻗﻌﯿﺖ اﺧﺬ ﺗﺼﻮﯾﺮ را مشکلات ﻫﻨﺪﺳﯽ ﻣﯽﮔﻮﯾﻨﺪ.
اﯾﻦ اﺧﺘﻼﻓﺎت در ﺗﺼﺎوﯾﺮ پزشکی، ﺑﺮ اﺳﺎس ﺣﺮﮐﺎت ﻏﯿﺮارادی (ﻣﺎﻧﻨﺪ ﺗﻨﻔﺲ، ﺿﺮﺑﺎن ﻗﻠﺐ و…) ﺣﺮﮐﺎت ارادی (ﻣﺎﻧﻨﺪ ﺟﺎﺑﺠﺎﯾﯽ ﺑﯿﻤﺎر) و در ﺗﺼﺎوﯾﺮ دﯾﮕﺮ ﺑﺮ اﺳﺎس ﺣﺮﮐﺖ دورﺑﯿﻦ ﺑﻪ وﺟﻮد ﻣﯽ آﯾﻨﺪ. ﻧﻮﯾﺰ، ﺗﻔﺎوت ﺷﺪت روﺷﻨﺎﯾﯽ، ﻣﻮﻗﻌﯿﺖ ﻣﻨﺎﺑﻊ روﺷﻨﺎﯾﯽ در ﺻﺤﻨﻪ و اﺧﺬ ﺗﺼﻮﯾﺮ درﺣﺴﮕﺮ ﻫﺎ و ﺑﺎﻧﺪﻫﺎی ﻃﯿﻔﯽ ﻣﺘﻔﺎوت، ﺳﺒﺐ اﯾﺠﺎد ﺗﻐﯿﯿﺮاﺗﯽ در ﺷﺪت روﺷﻨﺎﯾﯽ ﺗﺼﻮﯾﺮ می ﺷﻮد ﮐﻪ ﺑﻪ ﻣﺸﮑﻼت رادﯾﻮﻣﺘﺮی ﻣﻌﺮوف می ﺑﺎﺷﻨﺪ. ﺗﺼﺎوﯾﺮ، ﻣﻤﮑﻦ اﺳﺖ دارای ﺳﻄﻮﺣﯽ ﺑﺎ ﺑﺎﻓﺖ ﺿﻌﯿﻒ (ﻣﺎﻧﻨﺪ
درﯾﺎ ) ﺑﺪون ﺑﺎﻓﺖ و ﺑﺎﻓﺖ ﻫﺎی ﺗﮑﺮاری (ﻣﺎﻧﻨﺪ ﺳﺎﺧﺘﻤﺎن ﻫﺎی ﻣﺸﺎﺑﻪ) ﺑﺎﺷﺪ که مشکلات بافت نامیده می شوند. ویژگی های متحرک ( مانند حرکت وسایل نقلیه) و تغییراتی که در اثر گذر زمان در تصاویر (مانند تغییرات فصلی) وجود دارد، سبب تغییرات مناظر می شود. بر اساس مشکلات ذکر شده، جهت افزایش دقت در پردازش تصاویر، ضروری است فرآیند انطباق انجام شود. باید توجه کرد که هریک از الگوریتم های انطباق، تنها برای انطباق نوع مشخصی از تصاویر طراحی شده اند چرا که هر الگوریتم انطباق تصویر تنها برای حل نوع مشخصی از مشکلات هندسی، رادیو متری و مشکلات بافت و غیره کاربرد دارد.

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

نمودار تعداد مقالات بر حسب سال

 

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

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

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

2- کاربردهای انطباق تصویر

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

1-2- زوایای متفاوت

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

2-2- زمان های متفاوت

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

یک نمونه از انطباق در زوایای مختلف

 

حسگرهای متفاوت

در این دسته، هدف انطباق تصاویری است که از یک صحنه به وسیله حسگرهای متفاوت و در یک زمان یکسان گرفته شده است که به این نوع تصاویر، تاویر چند مودی می گویند. در این دسته از روش ها، هدف اصلی به دست آوردن اطلاعات کامل تر و دقیق تری از یک صحنه است که در تصاویر پزشکی و سنجش از دور اپتیکی و سنجش از دور SAR کاربرد دارد. برای مثال، تعیین موقعیت آناتومی یک تومور در پزشکی بسیار مهم است. تمایز بین تومور و بافت پیرامون آن، در تصاویر سی تی اسکن(CT) کم است. از طرفی تصاویر MRI توانایی خوبی در به تصویر کشیدن بافت های نرم دارند، در حالی که CT بافت سخت و SPECT ،PET کارکردها و فیزیولوژی را به خوبی در بدن نشان می دهند. استفاده هم زمان از تصاویر چند مودی در کنار هم کمک شایانی در فرآیند تشخیص و درمان برای پزشکان دارد. در این زمینه، طی سالیان متمادی، روش های گوناگون و متنوعی ارائه شده است. در شکل 4 نمونه ای از این نوع انطباق مشاهده می شود.

حالت های متفاوت تصویر شبکیه

 

4-2- انطباق تصویر به مدل

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

انطباق تصویر با حسگرهای متفاوت

 

3- انطباق تصاویر و مراحل آن

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

دیاگرام مراحل انطباق تصویر

1-3- شناسایی ویژگی ها

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

شناسایی ویژگی ها در تصویر مرجع و حس شده

 

1-1-3- روش های مبتنی بر ناحیه

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

2-1-3- روش های مبتنی بر ویژگی

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

– ویژگی های نقطه ای

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

شناساگر گوشه مُراوِک

ایده مُراوِک برای تشخیص گوشه، استفاده از یک پنجره ی باینری کوچک (برای مثال 3*3) با مرکزیت پیکسل مورد بررسی است. با حرکت دادن این پنجره در چهار جهت اصلی (u,v) = (1,0) , (1,1) , (-1,-1) , (0, 1) میزان تغییرات شدت روشنایی بررسی می شود. اگر این میزان، در چهار جهت بررسی شده نسبت به سایر همسایه ها بیشتر باشد، آن پیکسل به عنوان گوشه در نظر گرفته می شود. این شناساگر دارای نقاط ضعفی است عبارت اند از:

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

شناساگر هریس

شناساگر هریس توسط کریس هریس در سال 1988 پیشنهاد شد. این شناساگر، برای شناسایی گوشه از یک پنجره دایره ای هموار برای مثال پنجره گوسی استفاده می کند و سپس با استفاده از بسط تیلور، پنجره را در تمام جهت ها حرکت می دهد و مقدار شدت روشنایی را در تمام جهان بررسی می کند. این شناساگر، نسبت به مقیاس تغییر پذیر است یعنی ممکن است یک پیکسل در یک مقیاس تصویر به عنوان گوشه در نظر گرفته شود، اما همان پیکسل در مقیاس دیگر همان تصویر به عنوان گوشه در نظر گرفته نشود. یانگ و همکاران در سال 2013 برای انطباق تصاویر از الگوریتم هریس برای شناسایی ویژگی ها استفاده کردند. ژانگ و همکاران در سال 2013 از الگوریتم هریس برای شناسایی ویژگی ها در انطباق غیر سخت تصاویر ریه که با CT گرفته شده اند، استفاده کردند.

برای حل مشکل نقطه ضعف ذکر شده شناساگر هریس، یک الگوریتم به نام تبدیل ویژگی مقیاس ثابت پیشنهاد شد. در ادامه به بررسی بیشتر این الگوریتم پرداخته می شود. 

الگوریتم تبدیل ویژگی مقیاس ثابت

این الگوریتم در سال 2004 توسط لاو جهت انجام فرآیند تشخیص الگو در تصاویر اپتیکی ارائه شده است. الگوریتم SIFT هم شناساگر و هم توصیفگر است که مرحله استخراج ویژگی در آن خود شامل سه مرحله است؛ که مرحله استخراج اکسترمم های فضای مقیاس، بهبود دقت موقعیت و حذف اکسترمم های ناپایدار و در آخر تخصیص جهت به هر ویژگی که ایجاد شده است. الگوریتم SIFT دارای محدودیت هایی است که برای بهبود دادن این الگوریتم جهت ارتقاء دقت انطباق باید به نوع تصویر هم توجه کرد، زیرا انحراف هایی که بین تصاویر وجود دارد، با توجه به ماهیت تصاویر ممکن است، متفاوت باشد. در تصاویر سنجش از دور SAR به دلیل وجود نویز اسپکل و همچنین استفاده از فضای مقیاس گوسی در SIFT باعث می شود اغلب لبه ها و جزئیات ظریف در تصویر از بین برود که تأثیر قابل توجهی در تشخیص ویژگی ها دارد. برای غلبه بر مشکلات ذکر شده در  تصاویر سنجش از دور SAR، بهبود هایی در الگوریتم SIFT انجام شده است که در ادامه به بعضی از آن ها اشاره می شود. 

فلورا دلینگر و همکاران در سال 2015 جهت بهبود الگوریتم SIFT در تصاویر سنجش از دور SAR روش SAR-SIFT را معرفی کردند. این روش از دو مرحله کلی تشکیل شده است که ابتدا از روش نسبت به جای روش تفاضل برای محاسبه گرادیان استفاده می کند که این سبب می شود مقدار گرادیان در مناطق همگن تحت شرایط بازتاب مختلف فرقی نداشته باشد. سپس برای تطبیق تصاویر سنجش از دور SAR از یک الگوریتم SIFT مانند استفاده می شود که در این الگوریتم، برای شناسایی نقاط کلیدی از فضای مقیاس لاپلاس گوسی و برای تعیین جهت و ایجاد توصیفگرها از یک پنجره ی مدور استفاده می کند. این روش جهت انطباق تصاویر با زاویه متفاوت مناسب نیست. وانگ و همکاران در سال 2012 روش BFSIFT برای انطباق تصاویر سنجش از دور SAR را پیشنهاد کردند. در این روش، برای حفظ جزئیات در تصاویر سنجش از دور SAR فضای مقیاس گوسی ناهمسانگرد جایگزین فضای مقیاس گوسی در الگوریتم SIFT شده است که این فضای مقیاس با استفاده از فیلتر دوطرفه ایجاد شده است. از مزایای این روش، کاهش اثر نویز اسپکل در انطباق تصویر است اما زمان اجرا آن زیاد می باشد. جیان وی فن و همکاران در سال 2015 روش تبدیل ویژگی مقیاس ثابت مبتنی بر انتشار غیرخطی و تجانس فاز را برای انطباق تصویر سنجش از دور SAR پیشنهاد کردند. در این روش از انتشار غیرخطی جهت حفظ جزئیات مهم و ظریف در تصویر و از عملگر نسبت میانگین وزن شده نمایی برای محاسبه اطلاعات گرادیان و سپس از تجانس فاز برای حذف نقاط پرت استفاده می کند. از مزایای این روش، اندازه گرادیان در مناطق همگن تحت شرایط بازتاب مختلف اندکی تفاوت دارد اما برای تعیین جهت گرادیان معیار مناسبی ندارد. فنگ وانگ و همکاران در سال 2015، روش تبدیل ویژگی مقیاس ثابت گوسی ناهمسانگرد وفقی را برای انطباق تصاویر سنجش از دور SAR پیشنهاد کردند. در این روش، از فیلتر گوسی ناهمسانگرد در فضای مقیاس SIFT و تطبیق پایداری جهت گیری متعادل به ترتیب برای حفظ لبه ها و جزئیات مهم تصویر و حذف تطبیق های نادرست استفاده می کند. در این روش لبه ها در تصویر سنجش از دور SAR حفظ می شوند و در نهایت باعث ارتقا دقت انطباق تصویر سنجش از دور SAR می شود اما در این روش اندازه گرادیان در مناطق همگن تحت شرایط بازتاب مختلف، متفاوت است.

الگوریتم SIFT، در تصاویر سنجش از دور اپتیکی، دارای دو مشکل اصلی است که عبارت از کنترل پذیری پایین آن در تعداد ویژگی ها و عدم توجه به کیفیت و توزیع ویژگی های استخراج شده می باشد. ییکی از پارامترهای موثر در کنترل تعداد ویژگی ها در الگوریتم SIFT، میزان آستانه تمایز ویژگی ها (Tc) است که به علت حساسیت بسیار بالای آن در تعداد ویژگی های نهایی استخراج شده، در تصاویر مناسب نیست. در ضمن به علت عدم توجه این الگوریتم به مسئله توزیع مکانی و توزیع مقیاس ویژگی ها در اغلب موارد، پراکندگی ویژگی های استخراج شده، نامناسب است. 

در روشی برای استخراج ویژگی های SIFT با توزیع مکانی پیشنهاد شده است که در این روش به جای استخراج اکسترمم های تصویر DOG در همسایگی 26 تایی خود، همسایگی های بزرگتری (66 تایی) پیشنهاد کردند. با وجود مزایای این همسایگی بزرگ عتر، این روش دارای معایبی نیز می باشد. یکی از معایب این است که احتمال دارد باعث حذف بعضی از ویژگی های با کیفیت ولی با ساختار کوچک تصویر شوند. همچنین افزایش پیچیدگی محاسباتی آن نیز، بیشتر از الگوریتم SIFT پایه است. در روش SIFT تکرارشونده