یک الگوریتم هیبرید برای ساده‌سازی سرزمین
الموضوعات :
فهیمه دباغی زرندی
1
(دانشگاه ولی عصر (عج))
محمد قدسی
2
(دانشگاه صنعتی شریف)
الکلمات المفتاحية: سرزمین ساده‌سازی سطح نامنظم مثلث‌بندی‌شده خوشه‌بندی هیبرید الگوریتم‌های حریصانه,
ملخص المقالة :
با پیشرفت تکنولوژی و مجهزشدن دوربین‌های تصویربرداری، دقت تصاویر موجود افزایش یافته است. بالارفتن دقت تصاویر نقش مهمی در کیفیت تجزیه و تحلیل آنها دارد اما این دقت که به واسطه افزایش نقاط موجود در تصویر و بالارفتن حجم اطلاعاتی آن حاصل شده است، مشکلات بسیاری را در خصوص نگهداری و سرعت پردازش تصاویر به وجود آورده و به همین دلیل مسأله ساده‌سازی سرزمین مطرح شده است (معمولاً یک سرزمین به صورت مجموعه‌ای از n نقطه در فضای سه‌بعدی تعریف می‌شود). هدف مسأله ساده‌سازي اين است که تعدادي از نقاط يک سرزمين حذف شود به نحوي که خطاي سرزمين پس از ساده‌سازي، بيشتر از ميزان تعيين‌شده نباشد. خطاي ساده‌سازي به دو صورت تعريف مي‌شود، يکي اين که پس از ساده‌سازي، m نقطه با حداقل خطا در سرزمين وجود داشته باشد (m<=n) يا اين که حداکثر خطا پس از ساده‌سازي به ازاي کمترين تعداد نقاط، epsilon باشد (0> (epsilon. اين مسأله در حوزه مسایل ان پي- سخت قرار دارد. در اين مقاله، يک الگوريتم هیبرید براي ساده‌سازي سرزمین مطرح شده است که در سه مرحله ساده‌سازی را انجام می‌دهد. ابتدا سرزمین مربوط بر اساس یکی از روش‌های خوشه‌بندی به تعدادی خوشه تقسیم می‌شود، سپس هر خوشه بر اساس یک الگوریتم ساده‌سازی به صورت مجزا ساده می‌شود و در نهایت خوشه‌های ساده‌شده با هم ادغام می‌شوند. این الگوریتم از نظر زمان اجرا در رده مسایل O(n2n) قرار دارد. در انتهای مقاله، الگوریتم مطرح‌شده روی سرزمین‌های واقعی مورد آزمایش قرار گرفته و نتایج با استفاده از معیارهای موجود تحلیل شده است.
[1] P. K. Agarwal and S. Surii, "Surface approximation and geometrics partitions," in Proc. 5th ACM-SIAM Symp. Discrete Algorithms, pp. 24-33, 1994.
[2] M. Garland and P. S. Heckbert, "Fast polygonal approximation of terrains and height fields," in Technical Report, CMU-CS-95-181, 1995.
[3] M. de Berg, O. Cheong, M. van Kreveld, and M. Overmars, Computational Geometry, Springer-Verlag New York Inc, 3rd Edition, May 2008.
[4] J. Gudmundsson, M. Hammar, and M. van Kreveld, "Higher order delaunay triangulations," Computational Geometry: Theory and Applications, vol. 23, no. 1, pp. 85-98, Jul. 2002.
[5] M. Van Kreveld and R. I. Silveira, "Optimal higher order delaunay triangulations of polygons," Computational Geometry: Theory and Applications, vol. 42, no. 8, pp. 803-813, Oct. 2009.
[6] I. Dong Yun, K. Choo, and S. Uk Lee, "Mesh simplification using the edge attributes," EURASIP J. Appl. Signal Process., vol. 2002, no. 1, pp. 1102-1115, Jan. 2002.
[7] C. Chuon and S. Guha, "Volume cost based mesh simplification," in Proc. Int. Conf. on Computer Graphics, Imaging and Visualization, pp. 164-169, 11-14 Aug. 2009.
[8] Y. Guoqing, C. Zhun, and W. Mao, "The new triangulation-simplify algorithm of tin," in Proc. Int. Conf. on Computer Graphics and Virtual Reality, CGVR'06, pp. 79-85, 2006.
[9] M. Garland and P. S. Heckbert, "Surface simplification using quadric error metrics," in Proc. of the 24th Annual Conf. on Computer Graphics and Interactive Techniques, SIGGRAPH'97, pp. 209-216, New York, NY, US, 1997.
[10] W. Zhao, T. Tang, H. Gong, F. Duan, and Y. Mo, "Dynamic data retrieval and distance decay of triangulated irregular network (TIN)," Annals of GIS, vol. 12, no. 1, pp. 21-26, 2006.
[11] W. Xie and J. Lu, "An improved simplification algorithm of 3d terrain visualization model," in Proc. IAPRS Integrated System for Spatial Data Production, Custodian and Decision Support, pp. 545-548, 20-23 Aug. 2002.
[12] J. Wang, L. Wang, J. Li, and I. Hagiwara, "A feature preserved mesh simplification algorithm," J. of Engineering and Computer Innovations, vol. 2, no. 6, pp. 98-105, Jun. 2011.
[13] M. Garland and P. S. Heckbert, "Surface simplification using quadric error metrics," in Proc. 24th Annual Conf. on Computer Graphics and Interactive Techniques, SIGGRAPH '97, 1997.
[14] P. S. Heckbert and M. Garland, "Optimal triangulation and quadric-based surface simplification," J. of Computational Geometry: Theory and Applications, vol. 14, no. 1-3, pp. 49-65, Nov. 1999.
[15] J. Wei and Y. Lou, "Feature preserving mesh simplication using feature sensitive metric," J. of Computer Science and Technology, vol. 25, no. 3, pp. 595-605, May 2010.
[16] ف. دباغی و م. قدسی، "یک الگوریتم تقریبی برای ساده‌سازی سرزمین،" شانزدهمین کنفرانس ملی سالانه انجمن کامپیوتر ایران، دانشگاه صنعتی شریف، تهران، صص. 595-591، 1389.
[17] P. K. Agarwal and P. K. Desikan, "An efficient algorithm for terrain simplification," in Proc. 8th ACM-SIAM Symp. on Discrete Algorithms, pp. 139-147, 1997.
[18] Software, Lakes Environmental, Web gis. http://www.webgis.com/
