بخشی از مقاله
چکیده
در این مقاله، یک الگوریتم جدید برای تقریب منحنی های دیجیتال ارائه می دهیم که بر پایه ی ارزش دهی پیکسلهای منحنی استوار می باشد. منحنی تقریبی به گونه ای است که دارای پهنای یک پیکسلی است. مثالهایی برای بررسی کارایی این روش و مقایسه آن با روش هایی که در نرم افزار متلب وجود دارد، ارائه می شود.
١ مقدمه
یک منحنی دیجیتال از دید ر یاضی، به صورت یک سطح یا به عبارت دیگر یک نوار مسطح است نه یک منحنی - شکل١ - . بنابراین در تقریب این نوع منحنی ها، به وضوح منحنی های متفاوتی وجود دارد که خود می توانند به عنوان یک تقریب از این منحنی در نظر گرفته شوند - شکل١-الف - . از دید ریاضی استخراج یک منحنی از دل این سطح - سایش منحنی - ، به طوری که اطلاعات با ارزش منحنی اولیه، مانند انحنا، شیب و غیره را در خود داشته باشد، از اهمیت فراوانی برخوردار است؛ زیرا با استفاده از این منحنی می توان به الگوشناسی، توصیف اشیا و منحنی ها پرداخت. همچنین در زمینه هایی مثل فشرده سازی با قابلیت بازسازی از شکل فشردهشده ی آن، رباتیک، مکانیزاسیون و بینایی ماشین نیز کاربرد دارد.
مقالات گوناگونی وجود دارد که به تقریب اشیاء و یا منحنی های داخل یک تصویر می پردازند که حاصل همه آنها یک تقریب چند وجهی از مرزهای شی یا منحنی مسطح است ]١، ٣.[ این نوع تقریب ها از جهات بسیاری حائز اهمیت است ولی تقریب حاصل منحنیی نیست که بتوان آن را یک تقریب از منحنی داده شده در نظر گرفت. در ]٢[ نیز با تکیه بر بررسی موضعی موقعیت پیکسل های مرزی منحنی تحت عنوان پوشش سلولی یا پاکت سلولی به تقریب مرزهای منحنی می پردازد و نتیجه حاصل یک منحنی است که ضخامت آن یک پیکسل بوده و مرزهای شکل را مشخص می کند. با توجه به منحنی های ب، ج و د - شکل ١ - ، در نگاه اول بدست آوردن چنین منحنیی کار بسیار ساده ای است و می توان با روش های زیر بدست آید.
١- استفاده از خط راهنمای عمودی - از هر پیکسل به صورت عمودی بطرف بالا - پایین - حرکت می کنیم تا به نقطه مرزی برسیم و آن نقطه را به عنوان نقطه ای از تقریب ثبت می کنیم - یا خط راهنمای افقی - شکل ١ تقریب قرمز رنگ در منحنی های ج و د - .
٢- استفاده از میانگین سطری یا ستونی - شکل ١ تقریب آبی رنگ در منحنی های ج و د - .
٣- استفاده از هر دو خط راهنمای عمودی و افقی با هم. در این روش، تشخیص اینکه چه وقت از خط راهنمای عمودی یا خط راهنمای افقی استفاده کنیم خود یک مشکل بزرگ است و در مواردی هم با وجود تشخیص درست، منحنی حاصل ناپیوسته می شود.
۴- استفاده از مرز داخلی، خارجی، پایینی، بالایی، چپی یا راستی به عنوان تقریب مناست - شکل ١ الف - . ۵- استفاده از جعبه ابزار مطلب. این روش های ساده شاید برای بعضی از نمودارهای ساده تقریب خوبی بدست آورد، ولی برای هر یک از این روش ها مثالهای ساده ی زیادی وجود دارد که کارامدی آنها را زیر سوال می برد. در این مقاله، روشی ارائه می دهیم که همه این موارد را پوشش داده و برای نمودارهای پیچیده تر نیز نتیجه قابل قبولی بدست می آورد و در انتها برای آزمایش این روش، حروف تایپ شده را تقریب میزنیم.
٢ تقریب منحنی دیجیتال
مجموعه R را به ترتیب صعودی مرتب می کنیم. در سراسر این مقاله از A به عنوان ماتریس نظیر تصویر ورودی الگوریتم استفاده می شود. A ماتریسی است که درایه های نظیر منحنی، ٠ و بقیه درایه ها ١ می باشند. همچنین از ماتریس B به عنوان ماتریس ارزش پیکسلها، استفاده می شود که با استفاده از الگوریتم ١ بدست می آید. شکل ٢، خروجی الگوریتم ١ را برای منحنی های ”R” و ”+” نشان می دهد.
