یک نمونه پروژه تشخیص جعل کپی حرکت به روش DCT

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

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

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

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

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

این تبدیل ها در مراحل اولیه به بلاک ها و یا کل تصویر اعمال می شود.

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

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

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

در قسمت بعد به توضیح توابع مورد استفاده شده در این پروژه می پردازیم.

برای دانلود رایگان این پروژه و مقالاتش اینجا را کلیک کنید.

انواع روش های خوشه بندی سلسله مراتبی:

1) روش پایین به بالا (تجمعی Agglomerative):

در این روش ابتدا داده‌ها به عنوان خوشه‌ای مجزا در نظر گرفته می‌شود و در طی فرایندی تکراری در هر مرحله خوشه‌هایی که شباهت بیشتری با یکدیگر دارند با هم ترکیب می‌شوند تا در نهایت یک خوشه و یا تعداد مشخصی خوشه حاصل شود. از انواع الگوریتمهای خوشه‌بندی سلسله مراتبی متراکم شونده رایج می‌توان از الگوریتمهای Single-Link، Average-Linkو  Complete-Link نام برد. تفاوت اصلی در بین تمام این روشها به نحوة محاسبه شباهت بین خوشه‌ها مربوط می‌شود. که در بخشهای بعد به تشریح هر یک پرداخته خواهد شد.

فلوچارت این روش :

مثال 1)

گام های این روش را با ذکر یک مثال بیان می کنیم:(_خوشه بندی با روش پیوند مینگین انجام شده)

شباهت بین دو خوشه در روش Average-Link برابر است با میانگین فاصلة بین داده‌های دو خوشه.

گام اول:

الگوریتم، تعداد N خوشه (به تعداد مشاهدات) را در نظر می گیرد و برای تمام N خوشه ماتریس فاصله را حساب می کند.

مثال: 5 مشاهده= 5 خوشه داریم

ماتریس فاصله( هر درایه:میزان عدم تشابه یعنی فاصله ی مشاهدات)

گام دوم:

 در ماتریس فاصله به دنبال کمترین مقدار فاصله ها بین خوشه ها هستیم پس دو مشاهده ای که کمترین میزان فاصله را داراست باهم ادغام شده و تشکیل خوشه ای جدید را میدهند در این مثال دو مشاهده a و b تشکیل خوشه می دهند.

پس خوشه های پایان گام اول : {aوb} ، {c} ،{d} ، {e} می باشند.

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

هر درایه= مقادیر میزان عدم تشابه (  فاصله) خوشه ها

گام سوم:

کمترین فاصله مربوط به دو خوشه {d}و {e} می باشد پس خوشه جدید {d،e}.

متوسط میزان فاصله خوشه ها:

گام چهارم:

گامهای 2 و 3 تا زمانی که تنها یک خوشه که شامل تمامی مشاهدات است به همین منوال ادامه پیدا می کند.

برای نمایش بهتر اطلاعات از نمودار کمک میگیریم.

مثال 2)

یک مثال دیگر از این نوع خوشه بندی که با پیوند تکی انجام شده:

شباهت بین دو خوشه در روش Single-Link برابر است با کمترین فاصلة بین داده‌های دو خوشه.

در این مثال 6 نمونه داده و ماتریس فاصله ی آنها در جدول 1 نشان داده شده است:

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

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

با توجه به جدول ۳ مشخص است که خوشه‌های (۳ و ۵) و ۴ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با کمترین فاصلة بین (۳ و ۵) و یا ۴ از سایر خوشه‌ها. نتیجه در جدول ۴ نشان ‌داده شده است.

با توجه به جدول ۴ مشخص است که خوشه‌های (۱ و ۲) و ۶ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با کمترین فاصلة بین (۱ و ۲) و یا ۶ از سایر خوشه‌ها. نتیجه در جدول ۵ نشان ‌داده شده است.

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

مثال 3)

یک مثال دیگر از این روش که با پیوند کامل انجام شده است:

شباهت بین دو خوشه در روش Complete-Link برابر است با بیشترین فاصلة بین داده‌های دو خوشه.

در این قسمت سعی شده است تا در مثالی با فرض داشتن ۶ نمونه داده و ماتریس فاصلة بین آنها که در جدول ۶ نشان ‌داده شده است، نحوة اعمال روش خوشه‌بندی Complete-Link بهتر تشریح شود.

در ابتدا هر داده به عنوان یک خوشه در نظر گرفته می‌شود و یافتن نزدیکترین خوشه در واقع یافتن کمترین فاصلة بین داده‌های بالا خواهد بود. با توجه به جدول ۶ مشخص است که داده‌های ۳ و ۵ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با بیشترین فاصلة بین ۳ و یا ۵ از سایر خوشه‌ها. نتیجه در جدول ۷ نشان ‌داده شده است.

با توجه به جدول ۷ مشخص است که داده‌های ۱ و ۲ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با بیشترین فاصلة بین ۱ و یا ۲ از سایر خوشه‌ها. نتیجه در جدول ۸ نشان ‌داده شده است.

با توجه به جدول ۸ مشخص است که خوشه‌های (۳ و ۵) و ۴ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با بیشترین فاصلة بین (۳ و ۵) و یا ۴ از سایر خوشه‌ها. نتیجه در جدول ۹ نشان ‌داده شده است.

با توجه به جدول ۹ مشخص است که خوشه‌های (۱ و ۲) و ۶ کمترین فاصله را دارا هستند. و در نتیجه آنها را با هم ترکیب کرده و خوشة جدیدی حاصل می‌شود که فاصلة آن از سایر خوشه‌ها برابر است با بیشترین فاصلة بین (۱ و ۲) و یا ۶ از سایر خوشه‌ها. نتیجه در جدول ۱۰ نشان ‌داده شده است.

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

2) روش بالا به پایین (تقسیم کننده Divisive):

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

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

عیب این روش:

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

یکی از الگوریتم های معروفDIANA(Divisive Analysis) .

فلوچارت این روش:

نمودار مثال 1 برای این روش به این صورت است:

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

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

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

منبع:

دانلود خوشه بندی و روشهای آن

دانلود تحلیل خوشه بندی(ppt)

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

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

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

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

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

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

دندوگرام یک نمودار دو بعدی است که هم به صورت عمودی هم افقی می توان آنرا رسم کرد نتایج در هر دو صورت یکسان است.

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

خوشه بندی سلسله مراتبی در داد  با بُعد بالا، به دلیل زمان زیادی که صرف محاسبات می نماید، مقرون به صرفه و گاهی نیز قابل محاسبه نیست. البته این مشکل را با خوشه بندی K-MEANS رفع می کنند.

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

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

منبع:

دانلود خوشه بندی و روشهای آن

دانلود خوشه بندی K-means  و سلسله در نرم افزارها

دانلود تحلیل خوشه بندی(ppt)

خوشه بندی k-means

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

این روش روشی انحصاری و مسطح محسوب می شود.

برای این الگوریتم شکل های مختلفی بیان شده است. ولی همه ی آنها دارای روال تکراری هستند که برای تعدادی ثابت از خوشه ها سعی در تخمین موارد زیر دارند:

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

 

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

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

منبع:

دانلود خوشه بندی و انواع روش های ان

دانلود خوشه بندی K-means  و سلسله در نرم افزارها