یک رویکرد ارزیابی جدید برای الگوریتم‌های ساده‌سازی خط به سمت تجسم نقشه برداری

خلاصه

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

کلید واژه ها:

نقشه برداری ; ساده سازی خط ؛ آستانه ساده سازی ; شاخص ارزیابی ساده سازی

1. معرفی

کاربرد روش‌های ساده‌سازی خط بر روی نقشه‌های برداری موضوع مهمی در زمینه تعمیم نقشه‌کشی است. ساده‌سازی خطوط نقش مهمی در ارائه نقشه‌های برداری چند مقیاسی دارد. ارائه یک نقشه در مقیاس مربوط به اندازه بزرگنمایی یک منطقه در برنامه های نقشه دیجیتال مفید است. تعمیم نقشه‌کشی و به‌ویژه ساده‌سازی خط، زمانی که نقشه‌های برداری از طریق اینترنت منتقل یا مقیاس‌گذاری مجدد می‌شوند، یک تکنیک ضروری است، زیرا مجموعه داده‌های بزرگ معمولاً منجر به زمان انتظار طولانی‌تر می‌شوند [1 ]]. جزئیات یک نقشه برداری را می توان به تدریج حذف کرد تا مجموعه ای از نقشه های چند مقیاسی با ساده سازی خط تولید شود، که می تواند به کوتاه کردن زمان پاسخ در برنامه های نقشه دیجیتال کمک کند. بنابراین، ساده‌سازی خط یکی از مهم‌ترین رویکردها برای تسهیل تجسم نقشه‌های برداری از طریق اینترنت است. رویکرد ساده‌سازی خط همچنین می‌تواند در بهبود کارایی بزرگ‌نمایی و کوچک‌نمایی نقشه‌های برداری در WebGIS استفاده شود. با این حال، قدرت هندسی ساده سازی خط یک مسئله ضروری است. یک کاربرد کم توان از فرآیند ساده سازی خط احتمالاً نمی تواند اندازه نقشه های برداری را تا حد زیادی کاهش دهد. در مقابل، ساده سازی بیش از حد خط ممکن است به اعوجاج نقشه های برداری منجر شود. بدیهی است که مقدار مناسبی از ساده سازی خط،

از دهه 1960، الگوریتم های ساده سازی بسیاری در زمینه تعمیم نقشه کشی پیشنهاد شده است. به عنوان مثال، الگوریتم داگلاس-پیکر (DP) [ 2 ]، که یک خط را بر اساس فاصله عمودی ساده می کند. الگوریتم Reumann-Witkam (RW) [ 3 ]، که یک خط را بر اساس توابع زاویه چرخش ساده می کند [ 4 ]. الگوریتم Li-Openshaw [ 5 ] که یک خط را بر اساس شعاع ساده می کند. الگوریتم ساده سازی خط مترقی [ 6 ]، که یک خط را بر اساس یک منطقه ساده می کند. علاوه بر موارد ذکر شده در بالا، الگوریتم های کمتر محبوب دیگری نیز وجود دارد، از جمله الگوریتم Lang [ 7 ]، الگوریتم محدود زاویه [ 8]]، الگوریتم Sleeve-fitting [ 9 ]، الگوریتم Visvalingam-Whyatt (VW) [ 10 ]، الگوریتم ساده سازی دایره [ 11 ]، و تعمیم نقشه برداری بر اساس مدل مار B-spline [ 12]]. هدف از ساده سازی خطوط کاهش تعداد نقاط با حذف برخی از نکات بی اهمیت است، اما بدون از بین بردن شکل اساسی خطوط در فرآیند. تعداد نقاط حذف شده توسط شاخصی به نام آستانه ساده سازی در اکثر الگوریتم های ساده سازی تعیین می شود. آستانه ساده سازی می تواند فاصله عمودی، شعاع یا مساحت باشد. آستانه‌های ساده‌سازی مختلف، نقاط قوت مختلف ساده‌سازی را منعکس می‌کنند و به نسبت‌های فشرده‌سازی متفاوت و سطوح مختلف جزئیات نقشه‌های برداری منجر می‌شوند. قدرت ساده سازی بیشتر می تواند به تعمیم بیش از حد منجر شود و باعث اعوجاج خط شود و قدرت ساده سازی کمتر ممکن است نتواند به طور موثر اندازه یک نقشه برداری را کاهش دهد. از این رو، نحوه یافتن قدرت مناسب ساده سازی باید بیشتر در برنامه های کاربردی نقشه برداری دیجیتالی مورد بحث قرار گیرد. بر اساس قدرت ثابت ساده‌سازی، مقایسه الگوریتم‌های ساده‌سازی خط معنادارتر خواهد بود.

2. کارهای مرتبط

ارزیابی عملکرد یک الگوریتم ساده سازی خط به ویژگی های هندسی یک منحنی و تغییر موقعیت های نقطه بستگی دارد [ 13 ]. بسیاری از محققان مدل های مختلفی را برای اندازه گیری دقت هندسی ساده سازی خط پیشنهاد کردند. Veregin [ 14 ] اثرات ساده سازی را با کمی کردن خطای موقعیتی الگوریتم های ساده سازی خط (به ویژه الگوریتم DP) بررسی کرد. خطای موقعیت یک خط را می توان در سطح کل با استفاده از منحنی های فرکانس تجمعی و محدودیت های اطمینان آنها مدل کرد. سپس سطح ساده‌سازی را می‌توان شناسایی کرد و اکثر رئوس در فرآیند دستیابی به یک استاندارد دقت موقعیتی خاص حذف می‌شوند. شی و چونگ [ 15 ، 16] عملکرد نه الگوریتم ساده سازی خط را ارزیابی کرد. آنها از دو اندازه گیری جامع، از جمله جابجایی و اعوجاج شکل، برای ارزیابی الگوریتم های ساده سازی خودکار خط با در نظر گرفتن دقت موقعیت و زمان پردازش استفاده کردند. مطالعه آنها نشان می دهد که الگوریتم DP دقیق تر است، اما الگوریتم Lang و الگوریتم Zhao-Saalfeld کاربردی تر هستند زیرا زمان کمتری دارند. با در نظر گرفتن تأثیرات بر دقت فضایی و رابطه فضایی، ژو و وو [ 17 ، 18] یک سری فاکتورهای ارزیابی برای دقت هندسی، از جمله سینوسیته، خطای موقعیت و خطای انتشار را پیشنهاد کرد. نتایج آنها نشان داد که الگوریتم DP و الگوریتم دایره از نظر دقت هندسی و توانایی حفظ ویژگی های هندسی خطوط بهتر هستند. چن و زو [ 19] دو نوع الگوریتم ساده‌سازی خط را با ملاحظات مبتنی بر اختلاف مساحت، نسبت خمش، نسبت حداکثر خم به زاویه، تغییر- روند صعودی، انسجام نتیجه و خود تقاطع ارزیابی کرد. الگوریتم DP و الگوریتم پرتو نور در شش جنبه مختلف مقایسه شد و الگوریتم DP بهتر از الگوریتم دیگر تعیین شد. به منظور اطمینان از شباهت بین خط اصلی و ساده شده، تشابه شکل ویژگی های برداری یکی دیگر از معیارهای مهم ارزیابی در تعمیم نقشه است. لیو و لو [ 20] مدلی از شباهت شکل برای ویژگی های خط بر اساس سری فوریه پیشنهاد کرد. درجه تشابه در شکل به صورت فاصله اقلیدسی نشان داده می شود. با مدل شباهت، شش الگوریتم ساده‌سازی خط مورد ارزیابی قرار گرفت. الگوریتم DP و الگوریتم Lang در حفظ ویژگی‌های شکل بهتر تعیین شدند. کائو و لی [ 21 ] همچنین روشی را برای اندازه گیری شباهت شکل خطوط پیشنهاد کردند. شباهت کلی شکل و دقت مشابه در مطالعه آنها در نظر گرفته شده است. علاوه بر این، کائو [ 22 ] مدلی را پیشنهاد کرد که از ملاحظات وزن برای اندازه‌گیری شباهت هنگام انتقال داده‌های برداری فضایی به‌صورت تدریجی استفاده می‌کند. از نظر نقشه بارگیری و انتقال اطلاعات، دنگ و فن [ 23] مجموعه ای از عوامل ارزیابی را بر اساس سه سطح اطلاعاتی (عنصر، همسایگی و کلیت) پیشنهاد کرد و این عوامل را در داده های مربوط به شبکه رودخانه به کار برد. ثابت شد که این عوامل ارزیابی دارای مزایایی در اندازه گیری تغییر شکل خطوط هستند. گوو و شن [ 24] پیچیدگی زمانی چندین الگوریتم ساده سازی خط معمولی را تجزیه و تحلیل کرد و الگوریتم های ساده سازی خط را به دو دسته تقسیم کرد: الگوریتم های خطی و الگوریتم های غیرخطی. الگوریتم های خطی مانند الگوریتم Lang، الگوریتم دایره و الگوریتم Li-Openshaw به زمان کمتری برای انجام تست های خود نیاز دارند. الگوریتم های غیر خطی در زمان ساده سازی متفاوت هستند. با این حال، کارایی الگوریتم DP از نظر زمان آزمایش مورد نیاز بسیار بالاتر از الگوریتم Progressive است.

به طور خلاصه، بیشتر مطالعات بالا بر روی اندازه گیری خطای هندسی بین شکل اصلی و شکل ساده شده آن متمرکز شده اند. این روش های ارزیابی ابتدا نسبت تراکم را ثابت می کنند، سپس سایر عوامل (مانند زمان مورد نیاز، تفاوت و غیره) را با هم مقایسه می کنند. با این حال، ما معتقدیم که درجه تفاوت بین شکل اصلی و شکل ساده شده آن توسط قدرت ساده سازی تعیین می شود. هر چه قدرت ساده سازی انجام شده بیشتر باشد، تفاوت مورد انتظار بین نسخه اصلی و ساده شده خط(ها) بیشتر است. مقایسه الگوریتم‌های ساده‌سازی خط با قدرت ساده‌سازی ثابت، ارزیابی بین روش‌ها را معقول‌تر می‌کند. علاوه بر این، درجه ساده شدن یک خط باید با اهداف برنامه تعیین شود. مثلا، تجسم نقشه برداری در مقیاس 1:1000000 به قدرت ساده سازی کمتری نسبت به تجسم آن در مقیاس 1:250000 نیاز دارد. بنابراین نحوه تعیین قدرت ساده سازی در مقیاس های مختلف نیز باید در نظر گرفته شود. با توجه به تجسم نقشه برداری دیجیتال، پارامترهای فیزیکی دستگاه های نمایشگر، مقیاس نقشه هدف و توانایی چشم انسان در تشخیص پیکسل های یک نمایشگر به منظور تعیین قدرت مناسب ساده سازی خط در نظر گرفته می شود. همچنین، عملکرد الگوریتم های ساده سازی خط باید بر اساس قدرت ثابت ساده سازی ارزیابی شود. بخش بعدی عواملی را معرفی می‌کند که می‌توان از آنها در تعیین قدرت ساده‌سازی استفاده کرد و در ادامه یک روش ارزیابی برای ساده‌سازی خط معرفی می‌شود.بخش 4 . در نهایت، بحثی انجام شده و در بخش 5 نتیجه گیری شده است .

3. روش ارزیابی بر اساس قدرت ثابت ساده سازی

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

3.1. عوامل مرتبط با ساده سازی

3.1.1. وضوح صفحه نمایش (H _res × V _res )

وضوح نمایشگر به معنای تعداد کل پیکسل ها در هر یک از ابعاد است. به طور معمول، یک دستگاه نمایشگر دارای یک بعد افقی و یک بعد عمودی است که به ترتیب با H _res × V _res با واحدها در پیکسل مشخص می شود. هر چه یک دستگاه نمایشگر دارای وضوح بالاتر باشد، اثر ظریفتری دارد. بنابراین، نمایشگرهایی با رزولوشن بالاتر تفاوت ظاهری بیشتری را بین خط اصلی و نسخه ساده شده آن نشان می‌دهند. در این شرایط، ممکن است نیاز به یک ساده سازی کمتر قوی برای کاهش تفاوت های ظاهری وجود داشته باشد. بنابراین لازم است هنگام تعیین آستانه مناسب الگوریتم های ساده سازی، وضوح نمایشگر در نظر گرفته شود.

3.1.2. اندازه نمایشگر (D _scr )

اندازه نمایش به معنای اندازه فیزیکی یک صفحه نمایش است. معمولاً با اندازه مورب دستگاه های نمایشگر اندازه گیری می شود که با D _scr در اینچ نشان داده می شود. با وضوح نمایشگر یکسان، صفحه نمایش های بزرگتر دارای اندازه پیکسل بزرگتری هستند.

3.1.3. پیکسل در هر اینچ (PPI)

پیکسل در اینچ (PPI) یک نشانگر برای اندازه گیری تراکم پیکسلی دستگاه های نمایشگر است. PPI را می توان با اندازه صفحه نمایش در اینچ و وضوح صفحه محاسبه کرد. فرمول PPI به شرح زیر است:

PPI = اچ r e s 2 + V r e s 2 - - - - - - - - - - \sqrt D s c r

(1)

که در آن H _re وضوح افقی در پیکسل، V _re وضوح عمودی بر حسب پیکسل، و D _scr اندازه مورب بر حسب اینچ است. با PPI بالاتر، تصاویر یا نمودارهای نمایش داده شده در یک نمایشگر واضح تر ظاهر می شوند. طول فیزیکی یک پیکسل، که با _پیکسل D نشان داده می شود ، بر اساس PPI محاسبه می شود. وضوح فضایی، که منجر به قدرت های مختلف ساده سازی می شود، با طول پیکسل تعیین می شود. طول پیکسل را می توان به صورت زیر محاسبه کرد:

D p i x e l = 1 PPI (اینچ) = 0.0254 PPI (m) = 25.4 PPI (میلی متر)

(2)

3.1.4. مقیاس نقشه (مقیاس)

مقیاس نقشه به معنای نسبت فاصله روی نقشه مربوط به فاصله روی زمین است. جزئیات داده های برداری با مقیاس نقشه متفاوت است. نقشه ها در مقیاس های مختلف، نقاط قوت مختلف ساده سازی را منعکس می کنند، همانطور که در شکل 1 نشان داده شده است . مقیاس نقشه با PPI و وضوح فضایی رابطه کمی دارد که در ادامه به آن پرداخته خواهد شد. معمولاً مقیاس نقشه شرط اولیه در کاربردهای عملی است. بنابراین، مقیاس نقشه هدف ساده سازی را مشخص می کند.

3.1.5. وضوح فضایی پیکسل ها ( _پیکسل SR )

وضوح فضایی یا وضوح زمین، فاصله واقعی پیکسل ها را توصیف می کند. این می تواند توانایی در تشخیص جزئیات ویژگی های برداری را منعکس کند. وضوح فضایی پیکسل ها با مقیاس نقشه (مقیاس) و طول فیزیکی پیکسل ها ( _پیکسل D ) مرتبط است. رابطه کمی بین آنها به شرح زیر است:

اس آر p i x e l = D p i x e l مقیاس = 0.0254 PPI \times مقیاس (m) = 0.0254 \times D s c r مقیاس \times اچ r e s 2 + V r e s 2 - - - - - - - - - - \sqrt (متر)

(3)

3.1.6. وضوح چشم انسان

درک بصری چشم انسان نیز یکی از جنبه های ضروری برای در نظر گرفتن در تجسم نقشه های برداری دیجیتال است. حداقل زاویه ای که چشم غیر مسلح انسان می تواند تشخیص دهد حدود 1 دقیقه قوس بر اساس معیار رایلی است. بنابراین، چشم انسان احتمالاً نمی تواند دو جسم را که از فاصله بسیار نزدیک می شوند تشخیص دهد. مدل ساده یک سیستم بینایی انسان در شکل 2 نشان داده شده است .

حداقل فاصله چشم انسان برای تشخیص، که با _چشم D در شکل 2 نشان داده شده است، را می توان با حداقل زاویه تشخیص (θ) و فاصله بین چشم ها و صفحه ( d _مشاهده ) به صورت زیر محاسبه کرد:

D e y ه = 2 \times د o b s e r v e \times برنزه θ 2 = 2 \times برنزه 1 120 \times د o b s e r v e = 0.000291 \times د o b s e r v e (میلی متر)

(4)

وقتی که $d_{o b s e r v e}$ به عنوان 600 (mm) نشان داده می شود، که استاندارد اعمال شده است، D _eye 0.1746 (mm) خواهد بود.

از آنجایی که پیکسل ها کوچکترین واحد صفحه نمایش هستند، در آزمایش های عملی از تعداد پیکسل ها برای جایگزینی _چشم D استفاده می شود . تعداد پیکسل ها ( _چشم N ) مربوط به _چشم D به صورت زیر محاسبه می شود:

ن e y ه = ⌈ D e y ه D p i x e l ⌉ = ⌈ 0.000291 \times د o b s e r v e \times PPI 25.4 ⌉ = ⌈ 0.1746 \times PPI 25.4 ⌉

(5)

جایی که نماد ⌈ $\frac{D_{e y e}}{D_{p i x e l}}$ ⌉ به معنای گرد کردن N _چشم به حداقل عدد صحیح بزرگتر از $\frac{D_{e y e}}{D_{p i x e l}}$ ، و $D_{p i x e l}$ طول فیزیکی پیکسل ها بر حسب میلی متر است. فرمول (5) حداقل تعداد پیکسل هایی را که چشم انسان می تواند تشخیص دهد را نشان می دهد. همانطور که در شکل 3 نشان داده شده است ، با صفحه های شبکیه که در آنها PPI به طور معمول بیش از 200 است، N _چشم 2 خواهد بود . با صفحه نمایش های معمولی که در آن PPI کمتر از 145 است، N _چشم 1 خواهد بود. نتایج فوق بر اساس افرادی است که 600 میلی متر از صفحه نمایش فاصله دارند.

3.2. استحکام مناسب ساده سازی خط

با عوامل مرتبط با ساده‌سازی بالا، آستانه فاصله زمین ( _زمین D ) را بر اساس در نظر گرفتن N _چشم پیشنهاد می‌کنیم تا قدرت ساده‌سازی مناسب را پیدا کنیم. ( _زمین D ) با فرمول زیر تعریف می شود:

D g د____= اس آر p i x e l \times ن e y ه = 0.0254 PPI \times مقیاس \times ن e y ه (متر)

(6)

که در آن _پیکسل SR وضوح فضایی است و _چشم N حداقل تعداد پیکسل هایی است که چشم انسان می تواند تشخیص دهد. زمین D نشان دهنده حداکثر فاصله افست بین یک خط اصلی و معادل ساده شده آن است _.حفظ فاصله افست خطوط ساده شده در _زمین D می تواند تضمین کند که آنها به طور کلی مشابه خطوط اصلی باقی می مانند. بنابراین، _زمین D به منظور محدود کردن استحکام ساده سازی اعمال شده در این مطالعه استفاده می شود.

فاصله افست یک خط در حال ساده سازی را می توان در شکل 4 نشان داد . چند خط اصلی با خطوط جامد سبز و چند خط ساده شده آن با خط نقطه قرمز مشخص می شود. d _i نشان دهنده فاصله افست است. برای یک خط کامل، حتی یک نقشه برداری، مفهوم فاصله افست متوسط در مطالعه ما پیشنهاد شده است که با نشان داده می شود

\bar{d}

به شرح زیر است:

د ¯ = \sum n 1 د من n

(7)

که در آن _{d i} فاصله افست پاره ^خطi و n تعداد پاره خط است. با میانگین فاصله افست، تفاوت بین یک خط اصلی و نسخه ساده شده آن کمی سازی می شود. به عبارت دیگر، میانگین فاصله افست تفاوت بین آنها را قابل اندازه گیری می کند.

در راستای تجسم نقشه برداری، هدف از ساده سازی این است که خطوط ساده شده از نظر ظاهری تفاوت ظاهری با خطوط اصلی نداشته باشند. هنگامی که میانگین فاصله افست برابر با _زمین D در مقیاس نقشه مشخص است، به این معنی که قدرت ساده سازی خط به محدودیت تفاوتی می رسد که توسط چشم انسان قابل تشخیص است، نقاط حذف شده به حداکثر می رسد. همان زمان. بنابراین، آستانه ساده سازی مربوط به میانگین فاصله افست، قدرت مناسب ساده سازی خط است.

3.3. رویکرد ارزشیابی بر اساس قدرت ثابت ساده سازی

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

طبق بخش 3.2 ، اگر فاصله افست متوسط کمتر یا مساوی با _زمین D باشد ، تفاوت بین خط اصلی و خط ساده شده آن توسط چشم انسان به سختی قابل درک است. میانگین فاصله افست در این موقعیت هدف ساده سازی خط در مقیاس نقشه مربوطه است. برای به دست آوردن میانگین فاصله افست که نزدیکترین فاصله به _زمین D است ، روشی را برای تقریب متوالی برای یافتن آستانه ساده سازی مناسب پیشنهاد می کنیم. مراحل به شرح زیر است:

مرحله 1: یک سری از آستانه های ساده سازی را راه اندازی کنید:

G = {G_{1}, G_{2}, \dots, G_{i}, \dots, G_{n}}

، و آستانه های مجاور در فواصل مساوی تنظیم می شوند، یعنی،

G_{2} - G_{1} = G_{3} - G_{2} = \dots = G_{n} - G_{n - 1}

. تعداد اولیه عناصر G برابر است با تعداد پاره خط. G ₁ که حداقل مقدار مجموعه G است ، عنصر شروع است. G _n که حداکثر مقدار مجموعه G است ، عنصر پایانی است.

مرحله 2: مجموعه ای از نتایج ساده شده را برای هر یک از آستانه ها دریافت کنید: G _i (

G_{i} \in G

مرحله 3: میانگین فاصله افست بین یک خط اصلی و ساده شده آن را به ترتیب محاسبه کنید و مجموعه ای از فاصله افست متوسط را بدست آورید:

\bar{d} = {\bar{d_{1}}, \bar{d_{2}}, \dots, \bar{d_{i}}, \dots, \bar{d_{n}}}

. هر فاصله افست (

\bar{d_{i}}

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

مرحله 4: پیدا کردن

\bar{d_{t}}

نزدیکترین به _زمین D در میان عناصر

\bar{d}

. در ضمن، آستانه ساده سازی را پیدا کنید

G_{t}

مربوط به

\bar{d_{t}}

مرحله 5: مرحله 1 تا 5 را به صورت بازگشتی در داخل تکرار کنید

[G_{t}, G_{t + 1}]

تا زمانی که G _t تقریباً برابر با G _t₊₁ باشد ، به این معنی که میانگین فاصله افست زیر آستانه ساده سازی

G_{t}

مساوی یا بسیار نزدیک به _زمین D است .

مراحل فوق نه تنها برای یافتن آستانه ساده سازی مناسب مفید هستند

G_{t},

بلکه برای ارزیابی الگوریتم‌های ساده‌سازی که تحت یک قدرت ثابت ساده‌سازی انجام می‌شوند نیز مفید است.

4. آزمایش و نتایج

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

4.1. داده های تجربی و محیط

داده های آزمایشی 1:1،000،000 داده راه آهن چین از دهه 1980 بود که دارای 504 ویژگی چند خطی است. تعداد مختصات نقطه داده ها 7296 است. چهار الگوریتم: الگوریتم DP، الگوریتم پیشرو، الگوریتم زاویه و الگوریتم دایره به زبان پایتون با کتابخانه منبع باز GDAL (کتابخانه انتزاعی داده های مکانی) پیاده سازی شدند. پنج مقیاس نقشه در آزمایش انتخاب شد. آنها 1:2،500،000، 1:5،000،000، 1:10،000،000، 1:25،000،000، و 1:50،000،000 بودند. اندازه صفحه نمایش کامپیوتر با 19 اینچ بود

1440 \times 900 screen resolution

. با فرمول های (1) و (2)، PPI صفحه نمایش 90 و طول فیزیکی پیکسل بود.

(D_{p i x e l})

0.2822 میلی متر بود. ما در آزمایش فاصله بین چشم انسان و صفحه نمایش را 600 میلی متر تعریف کردیم. بنابراین حداقل فاصله ای که چشم انسان قادر به تشخیص آن بود بر حسب فرمول (4) 0.1746 میلی متر و تعداد پیکسل های متناظر با فرمول (5) 1 بود. بنابراین، همانطور که در جدول 1 نشان داده شده است، پنج فاصله زمین ( _زمین D ) را به دست آوردیم که به ترتیب با پنج مقیاس نقشه تعیین شده مرتبط هستند.

4.2. نتایج ساده سازی

انواع آستانه چهار الگوریتم ساده سازی عبارتند از فاصله عمودی، مساحت، زاویه و شعاع. همانطور که در جدول 2 نشان داده شده است، ما پنج آستانه برای هر یک از الگوریتم های ساده سازی با مقیاس های پنج گانه نقشه به دست آوردیم . ما مقادیر آستانه دقیقی را برای الگوریتم های Angle در مقیاس نقشه 1:5 M و 1:10 M دریافت نکردیم. با تجزیه و تحلیل بیشتر بر اساس فاصله افست متوسط، منحنی میانگین فاصله افست متفاوت با آستانه در شکل 5 نشان داده شده است . با توجه به جدول 1 ، مقادیر _زمین Dدر 1:5 متر و 1:10 متر به ترتیب 1411 متر و 2822 متر هستند، اما پرش از 1265 متر به 4714 متر در فاصله افست متوسط به ترتیب بین 2.8 درجه و 3.0 درجه اتفاق افتاد که منجر به شکست ما شد. مقادیر آستانه مناسب در مقیاس 1:5 M و 1:10 M. این ممکن است توسط داده های تجربی، که در آن زاویه اکثر مثلث های محصور شده توسط نقاط مجاور حدود 2.8 درجه است، مطرح شود.

نتایج ساده سازی داده های راه آهن چین در شکل 6 نشان داده شده است . خطوط سیاه خطوط اصلی و خطوط قرمز خطوط ساده شده هستند. شکل نشان می دهد که اکثر خطوط ساده شده به خوبی با خطوط اصلی مطابقت دارند.

4.3. نتایج ارزیابی

به منظور مقایسه عملکرد چهار الگوریتم، سه شاخص انحراف معیار، نسبت فشرده سازی و زمان ساده سازی برای ارزیابی الگوریتم های خط انتخاب شدند.

4.3.1. انحراف استاندارد میانگین فاصله افست

شکل 7 نتیجه انحراف معیار فاصله افست متوسط را نشان می دهد. الگوریتم DP، الگوریتم پیشرونده و الگوریتم دایره در انحراف استاندارد فاصله افست متوسط عملکرد خوبی دارند. _{آنها در مقایسه با مقدار زمین} D در جدول 1 تفاوت آشکاری ندارند . انحراف استاندارد فاصله افست متوسط برای الگوریتم DP کمترین است. انحراف استاندارد فاصله افست متوسط در الگوریتم Angle بالاترین میزان است، به خصوص زمانی که مقیاس نقشه کوچک می شود. این نشان می‌دهد که برخی از بخش‌های خط ساده‌سازی شده وجود دارد که هنگام استفاده از الگوریتم Angle از قسمت‌های اصلی دور می‌شوند، همانطور که در شکل 8 با خط سبز دایره‌شده نشان داده شده است.

4.3.2. نسبت تراکم

نسبت فشرده سازی چهار الگوریتم ساده سازی در شکل 9 نشان داده شده است . با کوچکتر شدن مقیاس نقشه، نسبت فشرده سازی بالا می رود. الگوریتم DP و الگوریتم Progressive قابلیت یکسانی در نسبت تراکم دارند. همچنین، آنها بهتر از دو الگوریتم دیگر هستند، با نسبت تراکم تقریباً 55٪ تا 85٪. شکل 9 همچنین نشان می دهد که الگوریتم Circle نسبت فشرده سازی پایینی دارد زمانی که مقیاس نقشه 1:2.5 M است و الگوریتم Angle بدون توجه به مقیاس نقشه نسبت فشرده سازی بالایی ندارد.

4.3.3. زمان ساده سازی

شکل 10 نتیجه زمان ساده سازی چهار الگوریتم را نشان می دهد. بدیهی است که الگوریتم Progressive به زمان بیشتری نیاز دارد. زمان ساده‌سازی الگوریتم DP با مقیاس‌های مختلف نقشه تغییرات جزئی را تجربه می‌کند. الگوریتم Angle و Circle به زمان‌های ساده‌سازی مشابهی نیاز دارند و زمان ساده‌سازی این الگوریتم‌ها در بین چهار الگوریتم کوتاه‌ترین است. علاوه بر این، زمان‌های ساده‌سازی الگوریتم زاویه و الگوریتم دایره با مقیاس‌های مختلف نقشه فقط کمی متفاوت است.

5. بحث و نتیجه گیری

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

(1) الگوریتم DP و الگوریتم Progressive در حفظ شکل یک خط بهتر هستند و هر دوی آنها نسبت فشرده سازی بهتری در تمام مقیاس های نقشه در آزمایش دارند. الگوریتم پیشرو در مقایسه با الگوریتم DP به زمان ساده سازی طولانی تری نیاز دارد. عملکرد خوب در حفظ شکل تأیید می کند که هر دوی این دو الگوریتم در حفظ ویژگی های کلی خطوط خوب هستند. تفاوت این دو الگوریتم در زمان ساده سازی را می توان با پیچیدگی زمانی تأیید کرد. پیچیدگی زمانی الگوریتم DP است

O (n \log n)

، و پیچیدگی زمانی الگوریتم Progressive است

O (n^{2})

(2) الگوریتم Angle بازده زمانی بالاتری دارد. با این حال، این یک الگوریتم پایدار نیست. ممکن است آستانه ساده سازی برای برخی از مقیاس های نقشه مناسب نباشد. علاوه بر این، نسبت تراکم این الگوریتم نسبتاً کمتر از سایر الگوریتم‌ها است. در شرایط نادر، ممکن است اعوجاج قابل توجهی رخ دهد.

(3) الگوریتم Circle بازده زمانی بالاتری نیز دارد و پیچیدگی زمانی آن نیز بیشتر است

O (n \log n)

. اثر ساده سازی این الگوریتم بسیار خوب است. مشاهده می شود که الگوریتم Circle در مقیاس های کوچک نقشه عملکرد بهتری دارد و در مقیاس های بزرگ نقشه نسبت فشرده سازی پایینی دارد. از آنجایی که شعاع دایره‌ها در مقیاس‌های نقشه بزرگ‌تر به تدریج کوچک‌تر می‌شود، احتمال قرار گرفتن نقاط در داخل دایره‌ها در مقیاس‌های نقشه بزرگ‌تر کم می‌شود. بنابراین، تعداد کمی از نقاط در مقیاس های نقشه بزرگتر حذف می شود و نسبت فشرده سازی برآورده نمی شود.

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

منابع

جونز، CB; مارک ور، جی. تعمیم نقشه در عصر وب. بین المللی جی. جئوگر. Inf. علمی 2005 ، 19 ، 859-870. [ Google Scholar ] [ CrossRef ]
داگلاس، دی اچ. الگوریتم های Peucker، TK برای کاهش تعداد نقاط مورد نیاز برای نمایش یک خط دیجیتالی یا کاریکاتور آن. کارتوگر. بین المللی جی. جئوگر. Inf. جئوویس. 1973 ، 10 ، 112-122. [ Google Scholar ] [ CrossRef ]
رومان، ک. Witkam، APM بهینه سازی تقسیم بندی منحنی در گرافیک کامپیوتری. در مجموعه مقالات سمپوزیوم محاسباتی بین المللی، داووس، سوئیس، 4 تا 7 سپتامبر 1973; صص 467-472.
Rangayan, RM; گولیاتو، دی. د کاروالیو، جی دی. سانتیاگو، S. تقریب چند ضلعی خطوط بر اساس تابع زاویه چرخش. جی. الکترون. Imaging 2008 , 17 , 023016. [ Google Scholar ]
لی، ز. Openshaw, S. یک اصل طبیعی برای تعمیم عینی نقشه های دیجیتال. کارتوگر. Geogr. Inf. سیستم 1993 ، 20 ، 19-29. [ Google Scholar ] [ CrossRef ]
چینگ شنگ، جی. براندنبرگر، سی. Hurni، L. یک الگوریتم ساده سازی خط مترقی. ژئو اسپات. Inf. علمی 2002 ، 5 ، 41-45. [ Google Scholar ] [ CrossRef ]
Lang, T. قوانین برای طراحان روبات. Geogr. Mag. 1969 ، 42 ، 50-51. [ Google Scholar ]
مک مستر، RB تعمیم خودکار خط. کارتوگر. بین المللی جی. جئوگر. Inf. جئوویس. 1987 ، 24 ، 74-111. [ Google Scholar ] [ CrossRef ]
ژائو، ز. Saalfeld، A. الگوریتم‌های ساده‌سازی چند خط آستین با زمان خطی. در مجموعه مقالات کنوانسیون سالانه و مقالات فنی نمایشگاه (AutoCarto)، سیاتل، WA، ایالات متحده آمریکا، 7-10 آوریل 1997. جلد 13، ص 214-223.
Visvalingam، M. وایات، تعمیم خط JD با حذف مکرر نقاط. کارتوگر. J. 1993 ، 30 ، 46-51. [ Google Scholar ] [ CrossRef ]
کیان، اچ. لیو، ی. ژانگ، ال. نیو، اچ. تحقیق الگوریتم تعمیم نقشه بر اساس کاراکترهای دایره ای. هیدروگر. Surv. نمودار 2005 ، 25 ، 14-17. (به زبان چینی) [ Google Scholar ]
گیلبرت، ای. Saux, E. تعمیم کارتوگرافی خطوط بر اساس یک مدل مار B-Spline. بین المللی جی. جئوگر. Inf. علمی 2008 ، 22 ، 847-870. [ Google Scholar ] [ CrossRef ]
بالبوآ، JLG؛ لوپز، FJA تشخیص الگوی سینوسیتی ویژگی های جاده برای اهداف تقسیم بندی در تعمیم نقشه برداری. تشخیص الگو 2009 ، 42 ، 2150-2159. [ Google Scholar ] [ CrossRef ]
Veregin، H. کمی سازی خطای موقعیتی ناشی از ساده سازی خط. بین المللی جی. جئوگر. Inf. علمی 2000 ، 14 ، 113-130. [ Google Scholar ] [ CrossRef ]
Cheung، CK; Shi, W. برآورد عدم قطعیت موقعیت در ساده سازی خط در GIS. کارتوگر. J. 2004 , 41 , 37-45. [ Google Scholar ] [ CrossRef ]
شی، دبلیو. Cheung، CK ارزیابی عملکرد الگوریتم های ساده سازی خط برای تعمیم برداری. کارتوگر. J. 2006 ، 43 ، 27-44. [ Google Scholar ] [ CrossRef ]
زو، KP; Wu, F. مدل انتشار خطا الگوریتم‌های ساده‌سازی ویژگی‌های خطی. Geomat. Inf. علمی دانشگاه ووهان 2007 ، 32 ، 932-935. (به زبان چینی) [ Google Scholar ]
وو، اف. Zhu، KP ارزیابی دقت هندسی الگوریتم‌های ساده‌سازی ویژگی‌های خطی. Geomat. Inf. علمی دانشگاه ووهان 2008 ، 33 ، 600-603. (به زبان چینی) [ Google Scholar ]
چن، بی. زو، KP; Xue، BX تجزیه و تحلیل و ارزیابی الگوریتم های ساده سازی ویژگی های خطی. J. Zhengzhou Inst. Surv. نقشه 2007 ، 24 ، 121-124. (به زبان چینی) [ Google Scholar ]
لیو، رایانه شخصی؛ لو، جی. Ai, TH; Li, C. Line دارای مدل ارزیابی جامع بر اساس شباهت شکل است. Geomat. Inf. علمی دانشگاه ووهان 2012 ، 37 ، 114-117. (به زبان چینی) [ Google Scholar ]
کائو، ZZ; لی، ام سی; Xu, JH اندازه گیری شباهت گرافیکی در مقیاس بندی متقابل. علمی Surv. نقشه 2013 ، 38 ، 131-132. (به زبان چینی) [ Google Scholar ]
Cao، ZZ یک مدل اندازه‌گیری شباهت برای انتقال با وضوح چندگانه مجموعه داده‌های منحنی از طریق اینترنت. Geomat. Inf. علمی دانشگاه ووهان 2014 ، 39 ، 1257-1260. (به زبان چینی) [ Google Scholar ]
دنگ، م. فن، ZD; لیو، HM ارزیابی عملکرد الگوریتم های ساده سازی خط بر اساس محتوای اطلاعات سلسله مراتبی. Acta Geod. کارتوگر. گناه 2013 ، 42 ، 767-773. (به زبان چینی) [ Google Scholar ]
Guo، LS; شن، جی. Zhu, W. پیچیدگی زمانی الگوریتم‌های ساده‌سازی ویژگی‌های خطی. J. Zhengzhou Inst. Surv. نقشه 2012 ، 29 ، 226-230. (به زبان چینی) [ Google Scholar ]

شکل 1. نمایش داده های برداری در مقیاس های مختلف.

شکل 2. مدل ساده چشم انسان.

شکل 3. حداقل تعداد پیکسل هایی که چشم انسان می تواند تشخیص دهد.

شکل 4. میانگین فاصله افست یک چند خط.

شکل 5. منحنی فاصله های افست متوسط که با آستانه های ساده سازی متفاوت است.

شکل 6. نتایج ساده سازی چهار الگوریتم.

شکل 7. انحراف استاندارد فاصله افست متوسط چهار الگوریتم ساده سازی.

شکل 8. نتایج ساده سازی چهار الگوریتم در مقیاس نقشه 1:25,000,000.

شکل 9. نسبت فشرده سازی چهار الگوریتم ساده سازی.

شکل 10. زمان های ساده سازی مورد نیاز توسط چهار الگوریتم ساده سازی.

جدول 1. فواصل مربوط به حداقل پیکسل های قابل تفکیک.

جدول 2. آستانه ساده سازی چهار الگوریتم ساده سازی.

© 2016 توسط نویسندگان؛ دارنده مجوز MDPI، بازل، سوئیس. این مقاله یک مقاله با دسترسی آزاد است که تحت شرایط و ضوابط مجوز Creative Commons Attribution (CC-BY) (http://creativecommons.org/licenses/by/4.0/) توزیع شده است.

;کاربردهای GIS مقالات

درخواست مشاوره

09120049370

8 صبح تا 12 شب

09120049370

خلاصه

1. معرفی

2. کارهای مرتبط