عنوان پایان‌نامه
ارائه روشی جهت استخراج محور مرکزی بر مبنای دیا گرام های ورو نوی
- رشته تحصیلی
- مهندسی عمران-سیستمهای اطلاعات جغرافیایی(GIS)
- مقطع تحصیلی
- کارشناسی ارشد
- محل دفاع
- کتابخانه پردیس 2 فنی شماره ثبت: 2215;کتابخانه مرکزی -تالار اطلاع رسانی شماره ثبت: 55533
- تاریخ دفاع
- ۱۴ شهریور ۱۳۹۱
- دانشجو
- مهران قندهاری
- استاد راهنما
- فرشاد حکیم پور, فرید کریمی پور
- چکیده
- محور مرکزی که برای هر جسم، منحصر¬به¬فرد و از لحاظ توپولوژیکی هم¬ارز با جسم اولیه می¬باشد عبارت است از مکان هندسی مراکز تمامی دوایری که در داخل جسم قرار دارد و بر حداقل دو نقطه¬ی مرزی مماس است. این ساختار دارای کاربردهای فراوانی در تحلیل تصاویر می¬باشد و همچنین از آن می¬توان به عنوان ابزاری مفید در بستر سامانه¬ی اطلاعات مکانی، جهت ایجاد ارتباط بین اشیاء مکانی بهره برد که از نمونه¬ی آن¬ها می¬توان به استخراج حوضه¬ی آبریز اشاره کرد. روش¬های مختلفی برای استخراج محور مرکزی ارائه شده است، که تمرکز اصلی این تحقیق بر روی الگوریتم-هایی می¬باشد که در آن¬ها محور مرکزی با استفاده از مجموعه¬ای از نقاط نمونه¬برداری شده از جسم استخراج می¬شود. نقاط نمونه¬برداری شده از یک جسم (در صورتی که به اندازه¬ی کافی چگال باشند) حاوی اطلاعاتی در مورد آن جسم هستند. این نقاط دارای اطلاعات توپولوژیکی و ترتیب خاصی نبوده و صرفاً مجموعه¬ای از نقاط دارای مختصات می-باشند. البته استخراج محور مرکزی، از هر مجموعه¬ی نقاطی امکان¬پذیر نیست، بلکه نیاز به اعمال شرایطی بر روی این نقاط می¬باشد. مشکل اصلی روش¬های موجود برای محاسبه¬ی محور مرکزی، حساسیت بالای آن¬ها به نویز و اعوجاجات مرزی بوده و انجام یک مرحله¬ی پالایش در آن¬ها ضروری است. هدف از پالایش، زدودن شاخه¬های اضافی محور مرکزی و حفظ شاخه¬های اصلی می¬باشد. با این حال، روش¬های پالایش که در اکثر الگوریتم¬ها به صورت یک مرحله¬ی پیش¬پردازشی یا پس¬پردازشی انجام می¬شود، باعث حذف و یا کوتاه¬سازی شاخه¬های اصلی محور مرکزی، ایجاد گسستگی در ساختار اصلی و تغییرات توپولوژیکی و هندسی در ساختار محور مرکزی می¬شوند. در این تحقیق، به منظور غلبه بر مشکلات روش¬ها¬ی قبلی، روشی جدید بر مبنای دیاگرام¬های ورونوی ارائه خواهد شد که در آن نقاط نمونه¬برداری شده قبل از استخراج محور مرکزی برچسب¬گذاری می¬شوند. عملیات پالایش در این روش به صورت پیش¬پردازش و یا پس¬پردازش نمی¬باشد، بلکه همزمان و همراه با محاسبه¬ی محور مرکزی انجام می¬گردد. ساختار مفهومی و نتایج این روش حاکی از پایداری، انعطاف¬پذیری، دقت و صحت بالای آن، حتی با وجود نویز و اعوجاجات مرزی می¬باشد. برای بررسی قابلیت استفاده عملی از الگوریتم پیشنهادی در بستر سامانه¬ی اطلاعات مکانی، از این الگوریتم جهت استخراج حوضه¬ی آبریز از شبکه¬ی رودخانه¬ها استفاده شد. نتایج به دست آمده برای استخراج حوضه¬ی آبریز اصلی با استفاده از روش پیشنهادی، نشان¬دهنده¬¬ی دقت کلی 96.43% و ضریب کاپا 95.67% در مقایسه با نتایج روش مبتنی بر مدل رقومی ارتفاعی زمین با دقت کلی 99.20% و ضریب کاپا 98.76% می¬باشد. این نکته از آن جهت حائز اهمیت است که در روش¬های تعیین حوضه¬های آبریز، هدف ارائه¬ی یک الگوریتم دقیق بر اساس پردازش داده¬های ارتفاعی می‌باشد، حال آنکه به دلیل حجم بالای داده¬های مدل رقومی زمین، در اکثر مواقع نیاز به زمان‌های طولانی محاسبه می¬باشد. در حالیکه در روش مبتنی بر الگوریتم پیشنهادی این تحقیق، علاوه بر حفظ دقت نتایج، به دلیل استفاده از داده¬های برداری شبکه رودخانه¬ها، زمان مورد نیاز برای ارائه نتایج نیز به میزان قابل توجهی کاهش می¬یابد.
- Abstract
- The Medial Axis (MA) that is unique for a given shape and is topologically equivalent to its shape is considered as the locus of the centers of circles that are tangent to shape boundary in two or more points, where all such circles are contained in shape. The MA is used in a variety of applications especially in image analysis and also it can be used in Geospatial Information System (GIS) for applications such as watershed delineation. Many methods have been proposed in order to extract the MA. They can he classified in Discrete, Semi-continuous and Continuous (Exact); the focus of this research is on the semi-continuous methods that the shape is defined by a set of sample points on the shape boundary and, then, the MA is approximated. The quality of the approximated MA depends, among other parameters, on the density of sample points. The proper density of sample points vary for different parts of the curve: simple parts can be reconstructed from fewer samples, while other parts may need to be approximated by more sample points. The semi-continuous methods are extremely sensitive to noise and boundary perturbations, which produce many irrelevant branches in the MA. Filtering extraneous branches is a common solution to handle this issue; It may be applied as a pre-processing step through simplifying (smoothing) the boundary, or as a post-processing step through pruning, which eliminates the irrelevant branches of the extracted MA. However, filtering may alter the topological or geometrical structure of the MA. This research reviews the semi-continuous methods that approximate the MA from sample points using Voronoi-diagram. Furthermore, we introduce the most commonly used methods for filtering irrelevant branches of the MA, and discuss their main issues. This investigation has led us to proposing a new MA approximation algorithm that avoids irrelevant branches through applying a pre-processing step that labels the sample points. Each main part of the shape is considered as a labeled curve segment. The results illustrate that our method is stable, easy to implement, robust and able to handle sharp corners and open curves, even in the presence of significant noise and perturbations. For evaluating the practical usability of the proposed algorithm in GIS, this algorithm is used to delineate the watershed of the river network. The proposed approach is used in a case study and the results are compared with a DEM-based method. The results of applying the proposed method indicate the overall accuracy of 96.43% and kappa coefficient of 95.67% as compared with the result of DEM-based method with the overall accuracy of 99.20% and kappa coefficient of 98.76%. Although numerous studies have been done to improve the accuracy of watershed delineation, there are a few attempts for increasing the efficiency of these methods. Even though the output of the proposed method may not be as accurate as DEM-based methods, it can be efficiently used when DEM data is either inaccessible or in a poor quality.
