مرکز منطقه ای اطلاع رسانی علوم و فناوری فصلنامه مهندسی برق و مهندسی کامپيوتر ايران 16823745 12 2 2014 9 21 A Hybrid Algorithm for Terrain Simplification یک الگوریتم هیبرید برای ساده‌سازی سرزمین 12 22 fa فهیمه دباغی زرندی محمد قدسی 2015 11 29 Terrain simplification problem is one of fundamental problems in computational geometry and it has many applications in other fields such as geometric information systems, computer graphics, image processing. Terrain is commonly defined by a set of n points in three dimension space. Major goal of terrain simplification problem is removing some points of one terrain so that maximum error of simplified surface is a certain threshold. There are two optimization goals for this problem: (1) min-k, where for a given error threshold , the goal is to find a simplification with the minimum number of points for which the error is that most , and (2) min-, where for a given number n, the goal is to find a simplification of at most m points that has the minimum simplification error. Simplification problem is NP-hard in optimal case. In this paper we present a hybrid algorithm for terrain simplification that performs in three phases. First, terrain is divided to some clusters, then any cluster is simplified independently and finally, the simplified clusters are merged. Our algorithm solves the problem in . The proposed algorithm is implemented and verified by experiments. با پیشرفت تکنولوژی و مجهزشدن دوربین‌های تصویربرداری، دقت تصاویر موجود افزایش یافته است. بالارفتن دقت تصاویر نقش مهمی در کیفیت تجزیه و تحلیل آنها دارد اما این دقت که به واسطه افزایش نقاط موجود در تصویر و بالارفتن حجم اطلاعاتی آن حاصل شده است، مشکلات بسیاری را در خصوص نگهداری و سرعت پردازش تصاویر به وجود آورده و به همین دلیل مسأله ساده‌سازی سرزمین مطرح شده است (معمولاً یک سرزمین به صورت مجموعه‌ای از n نقطه در فضای سه‌بعدی تعریف می‌شود). هدف مسأله ساده‌سازي اين است که تعدادي از نقاط يک سرزمين حذف شود به نحوي که خطاي سرزمين پس از ساده‌سازي، بيشتر از ميزان تعيين‌شده نباشد. خطاي ساده‌سازي به دو صورت تعريف مي‌شود، يکي اين که پس از ساده‌سازي، m نقطه با حداقل خطا در سرزمين وجود داشته باشد (m<=n) يا اين که حداکثر خطا پس از ساده‌سازي به ازاي کمترين تعداد نقاط، epsilon باشد (0> (epsilon. اين مسأله در حوزه مسایل ان ‌پي- سخت قرار دارد. در اين مقاله، يک الگوريتم هیبرید براي ساده‌سازي سرزمین مطرح شده است که در سه مرحله ساده‌سازی را انجام می‌دهد. ابتدا سرزمین مربوط بر اساس یکی از روش‌های خوشه‌بندی به تعدادی خوشه تقسیم می‌شود، سپس هر خوشه بر اساس یک الگوریتم ساده‌سازی به صورت مجزا ساده می‌شود و در نهایت خوشه‌های ساده‌شده با هم ادغام می‌شوند. این الگوریتم از نظر زمان اجرا در رده مسایل O(n2n) قرار دارد. در انتهای مقاله، الگوریتم مطرح‌شده روی سرزمین‌های واقعی مورد آزمایش قرار گرفته و نتایج با استفاده از معیارهای موجود تحلیل شده است. http://ijece.org/fa/Article/Download/28081