.:رویال آی تی:.

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

فهرست مطالب

فصل اول

۱-۱-مقدمه

۱-۱-مقدمه     ۲

۲-۱-انواع روش های مورداستفاده درPRا       ۲

۳-۱-سیستم های تشخیص الگو       ۵

۴-۱-گروه بندی(دسته بندی)سیستم های PRا     ۷

۵-۱-کاربردها   ۸

ابعاد گرفGa

فصل دوم

۱-۲-تاریخچهSSRP:

۱-۲-تاریخچه SSPRا       ۱۱

۲-۲-تاسیس کمیته تکنیکیIAPR(Techunical Committee)TC2ا     ۱۲

مدلM1 و دومدل دیگرM2 و M3 که هرکدام دارای فاصله رابطه ای ۱ با مدل M1 می باشند.

فصل سوم

۱-۳-مقدمه

۱-۳-مقدمه ۱۶

۲-۳-تعاریف اولیه ۱۶

۳-۳-بازنمایی داده ها   ۱۷

۴-۳-الگوریتم های تطبیق گراف   ۱۸

۱-۴-۳-Optimal Algorithmsا       ۱۸

۲-۴-۳-Discrete Relaxationا           ۱۹

۳-۴-۳-Error-Tolerant Algorithmsا           ۱۹

۴-۴-۳-Maximal Cliqueا           ۲۱

فصل چهارم

۱-۴-تعایف اولیه

۱-۴-تعاریف اولیه     ۲۶

۲-۴-توصیف وتطابق رابطه ای   ۲۶

۱-۲-۴-Relation(رابطه)     ۲۷

۲-۲-۴-همومورفیسم رابطه ای ۲۷

۳-۲-۴-مونورفیسم رابطه ای ۳۰

۴-۲-۴-ایزومورفیسم رابطه ای       ۳۰

۳-۴-توصیف رابطه ای وفاصله رابطه ای   ۳۲

۱-۳-۴-فاصله رابطه ای   ۳۳

۴-۴-توصیف رابطه ای وفاصله رابطه ای ویژگی دار ۳۶

۱-۴-۴-توصیف رابطه ای ویژگی دار ۳۷

۵-۴-الگوریتم مورداستفاده برای انجام تطابق رابطه ای     ۳۸

۱-۵-۴-جستجوی درختی بازگشتی       ۳۹

۲-۵-۴-جستجوی درختی بازگشتی باForward Checkingا     ۴۱

۶-۴-الگوریتم های موازی ۴۴

منابع وماخذ       ۴۶

فهرست شکل ها

۱-۱-مراحل ۳گانه تطابق الگو   ۷

۱-۳-نمایش انسان توسط گراف ۱۸

۲-۳-عملگرهای اصلاح درمجموعه نودویال   ۲۱

۳-۳-گراف انجمنی   ۲۲

۴-۳-کلیک ها استخراج شده   ۲۳

۱-۴-ترکیب یک رابطه باینری بانگاشتhا       ۲۸

۲-۴-همومورفیسم رابطه ایh ازR به Sا         ۲۹

۳-۴-مونورفیسم رابطه ایh ازR بهSا       ۳۰

۴-۴-ایزومورفیسم رابطه ایhاز R بهSا             ۳۱

۵-۴-مونومورفیسم رابطه ایh از R بهSا       ۳۱

۶-۴-روابط مربوط به نگاشتfا         ۳۴

۴-۷مدل های m1 و m2ا       ۳۶

۴-۸-همومورفیسم حاصل ازجستجوی درختی   ۴۰

مقدمه

تشخیص الگو دربرگیرنده دوعمل اساسی ومهم می باشد:توصیف ودسته بندی.وقتی یک جسم ناشناخته رابعنوان ورودی به سیستم میدهیم ابتدا یک توصیف ازاین جسم توید میشود.دوراهکار کلی برای پیاده سازی سیستم های تشخیص الگو وجود دارد.۱٫تشخیص الگوی آماری۲٫تشخیص الگوی ساختاری،هرکدام ازاین دو روش تکنیک های متفاوتی رابرای عمل توصیف وکلاسه بندی بکار میبرند.روشهای آماری بااستفاده از تئوری های تصمیم گیری وبراساس ویژگی های کمیتی استخراج شده از ورودی فرآیند کلاسه بندی راانجام میدهند.روش های ساختاری برمبنای ویژگی های شکل شناسی و خصوصیات ساختاری جسمم ونحوه ارتباط آنها باهم عمل توصیف ورودی وتشخیص گروه مربوط به آن راپیاده سازی میکند.راهکارهای ترکیبی وجوه مختلف ازتشخیص الگوی ساختاری وآماری راباهم بکار میبرند.برای سادگی فرض میکنیم ورودی های مابصورت تصاوی ۲بعدی می باشند که هدف اصلی پیداکردن یک تطابق ایده آل مابین اجزای مختلف تصویر است.یکی ازبهترین روش های موجود بازنمایی اجزای تصویری استفاده ازتوری گراف ها می باشد در این ساختار مجموعه نقاط ویژگی بدست آمده ازهرجزء تصویری رابعنوان نودهای گراف درنظر میگیریم ویالهای گراف بیان کننده ارتباط بین این نقاط ویژگی هستند،بنابراین هدف اصلی ما بصورت زیر مطرح میشود:پیداکردن یک نگاشت بین دومجموعه نوها ازدوگراف که مشخص کننده حداکثر ارتباط بین گره های ویژگی میباشد.ازآنجاکه گراف وخصوصیات آن یک مفهوم کلیدی برای حل مساله فوق می باشد وازطرفی باتوجه به تنوع گراف ویژگی دار را به صورتG=(V,E,A) تعریف میکنیم که V مجموعه نودها وEمجموعه یالها وA مجموعه ویژگی هاست.به ازای هریک مقدار ویژگیA_e به آن نسبت می دهیم،که میتواند یک ویاچند عدد حقیقی ویا به صورت بردار تعریف بشود.

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

Duda و Heart(1973)PR راتشخیص الگو توسط ماشین در محیط های مختلف نویزی دانستند.Pavlidis(1977) درکتاب خودPR رااینگونه تعریف کرد:کلمهpattern برگرفته ازواژهpatron(به معنی نگهدار) می باشد یعنی آن چیزی که ازیک مثال کپی شده است.Watanabe(1985) ادعا کرد که میتوانPR رابعنوان یک مسئله گروه بندی درنر گرفت که این گروه بندی ازطریق استنتاج،آنالیزهای ساختاری وروش های متمایز کننده انجام میشود.Fukunaga(1990) تعریف تکنیکی تری ارائه داد:PR عبارتست از محاسبه وتخمین یک تابع چگالی درفضاهایی باابعاد بالا وتقسیم این فضا به نواحی مختلف وکلاس های مشخص.Robert.P.W.Duin(2002) ماهیتPR راازدیدگاه مهندسی اینگونه تعریف کرد:هدف نهایی در PR طراحی ماشین هایی است که بتوانند خلاء بین تحقیقات نظری وکاربردعملی راازمیان بردارند.Sergious Theodoridis(2003):PR شاخه ای ازعلم است که هدف آن کلاسه بندی اجسام به گروه های متعدد می باشد،همچنینPR شاخه مهمی ازسیستم های هوش ماشینی است که برای کاربردهای تصمیم گیری ساخته میشوند.

سابقه Syntactical Pattern Recognition به اواسط دهه۶۰ برمیگردد.زمانی که مفهوم یادگیری ماشین چالش اصلی درمباحث تشخیص وتطابق الگوبود.استخراج ویژگی از داده های خام باید بصورت اتوماتیک انام میشد،تاClassifier ها بتوانند اینfeature رادسته بندی کنند درابتدا چندین تکنیک آمای برای حل این مشکل پیشنهاد شد.اما بزودی سختی کار وپیچیدگی استخراج برخی ازاین ویژگی های آماری خودرا نشان داد.درواقع ساختاری جدید برای بازنماییfeature های پیچیده تر مورد نیازبود.این ساختار می بایست بتواند اجزای تشکیل دهنده یک شی رادریک تصویر درجهات مختلف فضایی توصی کند.ازاینجا بود که برای اولین بارfeature های نحوی(Syntactic) بوجود آمد.این مفهوم توسط افرادی چونR.kirsch و R.leddyو Nararimhan و A.show در دهه۶۰مطرح وبه تشخیص الگوی نحوی معروف شد.(Syntactical Pattern Recognition)

تئوری زبان های formal ازجمله ابزازهایی بودک ه برای عملیات ترکیب وجمع آوری سمبل ها،روباط داخلی بین آنها،تحلیل وآنالیز برروی آنها واستخراج قواعدا گرامی وزیانی ازیک مجموعهSample مورداستفاده قرار گرفت.king sun-Fu وهمکارانش اولین تحقیقات دراین زمینه راانجام دادند و مقالات متعددی رادرسال۱۹۷۰ بچاپ رساندند.زبانهایformal ابزاری برای استخراج وحل مشکل مربوط به feature های سمبلیکی هستند.اما بعدا مشخص شد،زمانی که بامسئله تحلیل ،بررسی feature ها وتوصیف رابطه بین آنها سروکار داشته باشیم،ساختارهای ریاضی دیگری وجود دارند که بخوبی قادر به حل این مسائل هستد.مانند درخت ها،رشته ها،گراف هاو… این حوضه خاص ازPattern Recognition راتطبیق الگوی ساختاری (Structural Pattern Recognitin)می نامیم که اولین بار توسطTheo Pavlidis درسال۱۹۷۱ درقالب یک مقاله ارائه شد.عنوان مقاله”Structural Psttern Recognition:Primitives as Juxtaposition Relation” بود.کلمهSSPR سرنام اختصار کلماتSyntactical and Structural Pattern Recognition می باشد،که در اولین گردهمایی تشخیص الگوی ساختاری درسال۱۹۸۱ درنیویورک بوجود آمد.این کارگاه آموزشی توسط افراد سرشناسی چونPavlidis برگزار گردید ومورد حمایت مالی سازمانNSF(National Science Foundation) قرارگرفته بوددرآنجا چندین گروه کاری مختلف تشکیل شد.یکی ازمهمترین نتایج سمینار این بود که تکنیک های SSPR میتوانند برای حل کردن گستره وسیعی ازمسائل مربوط به Pattern Recognition مورداستفاده قرار بگیرند.

تشخیص اتوماتیک تصاویر یکی از زیرشاخه های پیچیده درPR است که دسترسی به ان نیازمند طی روال های پیچیده ای است.یکی از چالش های مهم وتاثیر گذار درتشخیص تصاویر،چگونگی بازنمایی اطلاعات به درون سیستم های اطلاعاتی می باشد.استفاده ازگراف یکی ازابزارهای بسیار مناسب برای نمایش اطلاعات ساختار که درفیلد های متعدد کامپیوتری مانند شکبه ها،تحلیل تصاویر،تشخیص الگو و… مورداستفاده قرار میگیرد.دربازنمایی تصاویر گراف هر ناحیه خاص ازتصویر راتسوط نوهای گراف،وروابط ساختای بین این اجزاء راتوسط یال ها نمایش میدهیم.کاربرد چنین ساختاری برای نمایش داده ها،منج به طرح مساله مطابقت گراف ها میشود.بنابراین صورت مساله تغییریافته،بصورت زیر در می آید:بدست آوردن نگاشتی یک به یک درفضای مساله برای تطبیق دوگراف،۱گراف مدل و ۲گراف Data که نمایش دهند تصویر مساله می باشد.دریک جستجوی کامل ودقیق معمولا به دنبال نگاشت یک به یک(Isomorphism) هستیم تااینکه بتوانیم نمونه دقیق ومنحصر بفردی ازگراف مدل رادرتصویر پیداکنیم،که اغلب اوقات امکان پذیرنیست.دلیل اصلی این امر خروجی های غیردقیق ازفاز قبلی (قطعه بند تصاویر)است که به علت وجود نویز دردنیای واقعی وتصاویر دریافتی اجتناب ناپذیربه نسر می آید.بنابراین گراف های حاصل ازتصویر ورودی معمولا کج شکل ومعیوب هستند.البته تکنیک های خاصی برای برخورد بااین مشکل وجود دارند که درادامه به آنها خواهیم پرداخت.

توصیف رابطه ای ازیک شی(Relational Description) عبارت است ازشرح وتوصیف کردن یک شی برحسب خصوصیات واجزایش وهمچنین روابط داخلی بین این از اجزاءا.Relational Matching:فرایند مقایسه وتحلیل دوتوصیف رابطه ای ازدوجسم مختلف برای تعیین و تشخیص ارتباط بین اعضای این دوشی واینکه این دوشی تاچه اندازه به هم شبیه هستند.Relational Matching کاربردهای متنوعی دارد،ازجمله درتشخیص اشیاء،Stero Vision ویابرای سازماندهی مدل های بانک اطلاعاتی.درفعالیت ها مربوط به بینایی سطح بالا عملیات تطابق(Matching) واستنتاج(reasoning) اهمیت بالایی دارند.یکی ازکاربردهیا بینایی سطح بالااین است که اشیا موجود دریک صحنه دلخواه راتشخیص دهد ومضمون وموضوع کلی صحنه راتعیین کند.ازطرفی کلاسه بندی اشیا ساده وبدون پیچیدگی دریک تصویر بااستفاده از تکنیک های آماری هم امکان پذیراست ولی شناسایی اجسام پیچیده ای که دارای اعضای مختلفی درجهات متفاوت فضایی هستند،نیازمند راه حل های دیگری می باشد.همچنین اگربخواهیم علاوه برتشخیص اشیاء زوایا وفاصله های بین اجزاء موجود درتصویر را اندازه گیری کنیم.دراین مورد نیز روش های آمای ناکافی هستند.وقتی که بخواهیم یک تفسیر کلی ازتمام صحنه داشته باشیم،ابتدا باید وابستگی های داخلی بین اجزاء و اشیا تصویر،وهمچنین روابط فضایی بین آنها را به دست آوریم.درتمامی این مراحل،مفهومRalational Matching مورداستفاده واقع میشود.دراین فصل چند الگوریتمRalational Matching مورد استفاده واقع میشود.دراین فصل چندالگوریتم Ralational Matching که از Discrete Ralaxation استفاده میکننند رامورد بررسی قرار میدهیم.

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

۶۳ صفحه

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