استنتاج شبکه‌های جاده‌ای هدایت‌شده از ردیابی GPS با تراز کردن مسیر

خلاصه

این مقاله روشی را برای استنتاج شبکه‌های جاده‌ای از ردیابی GPS پیشنهاد می‌کند. این شبکه‌ها شامل تقاطع‌های بین جاده‌ها، اتصال بین تقاطع‌ها و مسیرهای ترافیکی احتمالی بین تقاطع‌هایی هستند که مستقیماً به هم متصل هستند. این تقاطع ها با شناسایی و خوشه بندی نقاط عطف، که مکان هایی هستند که جهت حرکت در ردیابی GPS تغییر می کند، محلی سازی می شوند. ما ساختار شبکه‌های جاده‌ای را با تقسیم‌بندی تمام ردیابی‌های GPS برای شناسایی این تقاطع‌ها استنباط می‌کنیم. سپس می توانیم هم یک ماتریس اتصال از تقاطع ها و هم یک مسیر GPS نماینده کوچک برای هر بخش جاده تشکیل دهیم. بخش جاده بین هر جفت تقاطع متصل به طور مستقیم با استفاده از یک سری مکان های جغرافیایی نشان داده می شود. که از تمام مسیرهای این بخش جاده با تراز کردن آنها با استفاده از الگوریتم زمان تابش پویا (DTW) به طور میانگین محاسبه می شوند. سهم ما دو برابر است. ابتدا، ما تقاطع‌های احتمالی را با خوشه‌بندی نقاط عطف روی ردیابی GPS تشخیص می‌دهیم. دوم، هندسه بخش‌های جاده بین تقاطع‌ها را با تراز کردن مسیرهای GPS نقطه به نقطه با استفاده از استراتژی «کشش و سپس فشرده‌سازی» بر اساس الگوریتم DTW استنباط می‌کنیم. این رویکرد نه تنها تخمین جاده را با میانگین‌گیری مسیرهای تراز شده امکان‌پذیر می‌کند، بلکه یک تحلیل آماری عمیق‌تر بر اساس هم‌ترازی زمانی هر مسیر، به عنوان مثال واریانس سرعت در طول یک بخش جاده را نیز امکان‌پذیر می‌کند. ما هندسه بخش های جاده بین تقاطع ها را با تراز کردن مسیرهای GPS نقطه به نقطه با استفاده از استراتژی “کشش و سپس فشرده سازی” بر اساس الگوریتم DTW استنباط می کنیم. این رویکرد نه تنها تخمین جاده را با میانگین‌گیری مسیرهای تراز شده امکان‌پذیر می‌کند، بلکه یک تحلیل آماری عمیق‌تر بر اساس هم‌ترازی زمانی هر مسیر، به عنوان مثال واریانس سرعت در طول یک بخش جاده را نیز امکان‌پذیر می‌کند. ما هندسه بخش های جاده بین تقاطع ها را با تراز کردن مسیرهای GPS نقطه به نقطه با استفاده از استراتژی “کشش و سپس فشرده سازی” بر اساس الگوریتم DTW استنباط می کنیم. این رویکرد نه تنها تخمین جاده را با میانگین‌گیری مسیرهای تراز شده امکان‌پذیر می‌کند، بلکه یک تحلیل آماری عمیق‌تر بر اساس هم‌ترازی زمانی هر مسیر، به عنوان مثال واریانس سرعت در طول یک بخش جاده را نیز امکان‌پذیر می‌کند.

کلید واژه ها:

استنتاج نقشه ؛ استخراج تقاطع ; تراز مسیر

1. معرفی

استنتاج خودکار نقشه راه یک ابزار مهم در زمینه سیستم های حمل و نقل هوشمند (ITS) است: این امکان را می دهد که مناطق جغرافیایی ناشناخته (مثلاً در کشورهای در حال توسعه) به سرعت نقشه برداری شوند [1 ، 2 ، 3 ، 4 ] . می تواند نقشه های موجود را به روز کند [ 5 ، 6 ]. و همچنین اطلاعاتی در مورد تراکم ترافیک [ 7 ] ارائه می دهد که می تواند در ناوبری [ 8 ] و برای برنامه ریزی شهری استفاده شود [ 9 ، 10 ].

نقشه‌های راه قبلاً از طریق نقشه‌برداری جغرافیایی کار فشرده با استفاده از تلسکوپ‌ها، سکستانت‌ها و سایر دستگاه‌ها ساخته می‌شدند. امروزه این روش ها با وسایل نقلیه نقشه برداری سیار جایگزین شده اند که می توانند کل شهرها را با دقت بالا ترسیم کنند [ 11 ]. با این حال، کمپین های نقشه برداری موبایل گران هستند، و در نتیجه، داده ها به ندرت به روز می شوند. علاوه بر این، نقشه‌برداری موبایل اطلاعات مرتبط با ترافیک، مانند تراکم ترافیک به عنوان تابعی از زمان، مسیرهای ترجیحی مسافران و تأخیرهای ناشی از ترافیک را ارائه نمی‌کند.

به لطف استفاده همه جانبه از دستگاه‌های سیستم موقعیت‌یابی جهانی (GPS)، نقشه‌های جاده دیجیتال اکنون می‌توانند از مسیرهای GPS کاربران مختلف جاده استخراج شوند [ 12 ، 13 ]. از آنجایی که دستگاه‌های جی‌پی‌اس دستی در دهه گذشته به طور فزاینده‌ای محبوب شده‌اند، داده‌های جغرافیایی نه تنها از خودروها، تاکسی‌ها و کامیون‌ها، بلکه از دوچرخه‌سواران و عابران پیاده نیز به راحتی قابل دستیابی هستند. این فراوانی داده‌های جغرافیایی مشتق‌شده از GPS، توسعه هر دو پروژه نقشه‌برداری با منبع جمعی [ 14 ، 15 ] و همچنین محصولات تجاری را تحریک کرده است. تحقیق در مورد تجزیه و تحلیل ردیابی GPS بر ساختن نقشه های راه [ 16 ] و یادگیری حالت های تحرک افراد [ 17] متمرکز شده است.]. تحقیقات دیگر بر محاسبه بهترین مسیر بین دو مکان [ 9 ، 18 ، 19 ] یا یافتن کارآمدترین مسیر برای کامیون زباله [ 8 ] متمرکز است.

شبکه‌های جاده‌ای یک جنبه حیاتی برای بهینه‌سازی مسیر و برنامه‌ریزی مسیر هستند. در این مقاله، ما یک روش جدید برای استنتاج ساختار شبکه جاده‌ای از ردیابی‌های مختلف GPS، از جمله شناسایی تقاطع‌ها، اتصال بین تقاطع‌ها و جاده‌های هدایت‌شده پیشنهاد می‌کنیم. ما با محاسبه جهت حرکت کاربران در هر نقطه از ردیابی GPS شروع می کنیم. سپس تقاطع‌ها با خوشه‌بندی «نقاط عطف» پیدا می‌شوند، که ما آن‌ها را به‌عنوان مکان‌های جغرافیایی خاصی که در آن کاربران تغییر جهت می‌دهند، تعریف می‌کنیم. اتصال بین هر جفت تقاطع سپس از ردیابی خام GPS استنتاج می شود، که به مسیرهای مربوط به بخش های جاده بین هر جفت تقاطع متصل تقسیم می شود. سرانجام، مسیرهای هر بخش جاده با استفاده از روشی مبتنی بر تاب‌خوردگی زمانی دینامیکی (DTW) تراز می‌شوند و سپس میانگین‌گیری می‌شوند تا به طور دقیق بخش جاده را محلی‌سازی کنند. بر اساس تراز مسیر، میانگین سرعت و واریانس سرعت در طول هر بخش جاده قابل تجزیه و تحلیل است.

این مقاله توسعه‌ای از کار است که در ابتدا در کنفرانس سیستم‌های حمل‌ونقل هوشمند IEEE در سال 2014 منتشر شد [ 20 ]. در این مقاله، روش‌های تشخیص تقاطع و تراز چند مسیر را با عمق بیشتری شرح می‌دهیم. ما همچنین روش تشخیص تقاطع خود را با حذف تقاطع‌های جعلی ناشی از پیچ‌های جاده که در کار قبلی ما وجود داشت، بهبود می‌بخشیم. ما پیچ ها را از تقاطع ها با استفاده از این شهود متمایز می کنیم که کاربران جاده می توانند جهت را در تقاطع ها به روش های مختلف تغییر دهند، اما همیشه در پیچ های جاده در یک جهت حرکت می کنند. سپس دقت شبکه جاده‌ای استخراج‌شده را از نظر توپولوژیکی و جغرافیایی با استفاده از متریک F-score [ 21] ارزیابی می‌کنیم.]، که هم دقت و هم یادآوری را در نظر می گیرد. علاوه بر این، ما آمار ترافیک زمانی را برای هر بخش جاده با استفاده از مسیرهای GPS مرتبط آن محاسبه می‌کنیم. به عنوان مثال، ما می توانیم سرعت متوسط و تغییرات سرعت را تعیین کنیم که برای تجزیه و تحلیل ترافیک مفید است.

ادامه مقاله به شرح زیر تدوین شده است. در بخش بعدی، کار مرتبط با استنتاج نقشه راه را معرفی می کنیم. در بخش 3 ، نحوه استخراج تقاطع ها از نقاط عطف، نحوه کاوش اتصال آنها و در نهایت، نحوه تراز کردن چندین مسیر غیرخطی در زمان با استفاده از استراتژی “کشش و سپس فشرده سازی” را توضیح می دهیم. در بخش 4 ، ما دقت توپولوژیکی و جغرافیایی یک شبکه جاده را که با استفاده از روش ما استنباط شده است، ارزیابی می کنیم. در نهایت، در بخش 5 ، نتایج تجربی خود را نشان می‌دهیم.

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

هدف از استنتاج شبکه جاده ای این است که به طور خودکار یک نمودار هدایت شده از ردیابی خام GPS تولید کند که هندسه و توپولوژی جاده ها را نشان می دهد. بسته به نحوه پردازش ردیابی های GPS، روش های استنتاج شبکه جاده ای را می توان به طور کلی به دو گروه طبقه بندی کرد:

روش‌های عمل بر روی یک تصویر باینری ایجاد شده از ردیابی GPS: این روش‌ها ابتدا منطقه جغرافیایی تحت پوشش ردیابی GPS را به شبکه‌ای دو بعدی از سلول‌ها تقسیم می‌کنند و تراکم هسته (KD) نقاط داده ردیابی را برای هر سلول تخمین می‌زنند [ 1 , 3 ، 5 ، 22 ]. سپس یک نمایش دودویی از تمام آهنگ‌ها با اعمال یک آستانه در تخمین KD تولید می‌شود. این روش ها در نحوه استخراج خطوط مرکزی جاده از تصویر باینری حاصل متفاوت است. دیویس و همکارانبرای استخراج مجموعه‌ای از چند ضلعی‌های بسته که طرح کلی مناطق جاده‌ها را توصیف می‌کنند، یک دنباله‌روی کانتور را روی تصویر دودویی اعمال کنید و سپس خطوط مرکزی جاده را با تولید یک نمودار Voronoi از خطوط که لبه‌های جاده را توصیف می‌کند، محاسبه کنید [3 ] . چن و همکاران از یک رویکرد پردازش تصویر برای استخراج نقشه راه از تصویر باینری استفاده کنید [ 22 ]. ابتدا، عملیات اتساع مورفولوژیکی و بستن برای ادغام نقاط داده گسسته ردیابی GPS استفاده می شود. سپس از عملیات نازک‌سازی برای تولید اسکلت در امتداد خطوط مرکزی جاده استفاده می‌شود. شی و همکاران روشی بسیار مشابه با رویکرد چن [ 22 ] پیشنهاد می کنند، اما آنها سعی می کنند گذرگاه ها را از اسکلت شبکه راه ها استخراج کنند [ 5]]. Biagioni و Eriksson با اعمال یک آستانه ساده در KDE یک تصویر نقشه باینری تولید نمی کنند، زیرا یک آستانه نمی تواند هم دقت بالا و هم پوشش بالای نقشه راه را بدست آورد. برای حل این مشکل، آنها از تکنیک اسکلت سازی در مقیاس خاکستری برای استخراج یک اسکلت بدون آستانه از KDE استفاده می کنند [ 16 ].
روش‌های مبتنی بر KDE از آستانه‌گذاری رنج می‌برند، زیرا یک آستانه بالاتر لبه‌های جعلی تولید می‌کند. با این حال، یک آستانه پایین تر، مسیرها را در مناطق پراکنده به عنوان سر و صدا نادیده می گیرد، که منجر به شناسایی ناموفق جاده هایی می شود که اغلب از آنها عبور نمی شود. اگرچه هندسه شبکه جاده‌ها با استفاده از مکان‌های جغرافیایی در امتداد خطوط مرکزی جاده ساخته شده است، توپولوژی شبکه جاده‌ای که توسط اتصالات بین جاده‌ها شکل می‌گیرد، به طور کامل در تجزیه و تحلیل جاده مبتنی بر تصویر باینری که قبلا ذکر شد، تجزیه و تحلیل نمی‌شود. توپولوژی شبکه راه برای بهینه سازی مسیر و برنامه ریزی مسیر ضروری است. در این مقاله، ما بر روی مسیرها (موقعیت های فضایی به عنوان تابعی از زمان) به طور مستقیم به منظور استخراج تقاطع های جاده ها و تجزیه و تحلیل اتصال آنها با استفاده از ردیابی GPS عمل می کنیم.
روش‌های کار بر روی نقاط داده ردیابی GPS: اکثر محققان ردیابی‌های GPS را به قطعات مسیر برای هر بخش جاده تقسیم می‌کنند و نمایش هر بخش جاده را از قطعات مسیر مطابق با آن استنباط می‌کنند. در این روش‌ها، تقاطع‌ها قبل از تولید بخش جاده شناسایی می‌شوند و اتصال بین تقاطع‌ها برای تقسیم ردیابی GPS در هر بخش جاده مفید است. با توجه به مجموعه‌ای از قطعات مسیر، روش‌های متنوعی، از برازش منحنی گرفته تا تقسیم‌بندی نمودار، برای استخراج یک بخش راهنما از قطعات مسیر مربوطه آن پیشنهاد شده‌اند. این رویکردها را می توان بر اساس مبانی الگوریتمی به سه دسته تقسیم کرد.

–

روش‌های برازش منحنی: Edelkamp و Schroedl از یک الگوریتم K-means برای خوشه‌بندی نقاط داده آثار GPS خام هر دو بخش جاده‌ها و تقاطع‌ها بر اساس اندازه‌گیری فاصله استفاده می‌کنند. خطوط مرکزی جاده با استفاده از یک رویکرد برازش اسپلاین برای هر بخش جاده از نقاط داده GPS مربوط به آن تولید می‌شوند [ 2 ، 18 ].

–

روش های توپولوژیکی: موریس و همکاران. [ 23 ] یک نمودار توپولوژیکی برای نمایش شبکه فیزیکی ردیابی های GPS بسازید. یک نمودار اولیه از نقاط تعامل و خطوط اتصال بین تمام مسیرها ایجاد می شود. این خطوط اتصال برای استخراج یک نمایش واحد برای هر بخش جاده با استفاده از یک الگوریتم نمودار، مانند کاهش موازی، کاهش چهره، کاهش سریال و انقباض لبه کاهش می‌یابد.

–

روش‌های ادغام ردیابی: Karagiorgou و Pfoser تقاطع‌ها را با خوشه‌بندی پیچ‌ها بر اساس مکانشان تشخیص می‌دهند و نوع پیچ و مسیرهای بین تقاطع‌ها را دسته‌بندی می‌کنند تا آنها را در بخش‌های جاده ادغام کنند [24 ] .

محققان دیگر ترجیح می‌دهند که یک ردیابی GPS را در یک زمان پردازش کنند تا آن را به شبکه جاده‌ای اضافه کنند، به جای پردازش چند قطعه مسیر برای یک بخش جاده. Cao و Krumm [ 4 ] پیشنهاد می‌کنند که ردیابی GPS را با استفاده از شبیه‌سازی نیروهای فیزیکی در میان ردیابی‌ها، که اثرات نویز GPS را کاهش می‌دهد، و ردیابی‌های GPS تمیز شده را با حریصانه در یک نمودار ادغام می‌کنند. لبه‌های هر ردیابی GPS خام به نمودار اضافه می‌شوند، مگر اینکه لبه‌ای با موقعیت و یاتاقان مشابه از قبل در نمودار در حال ساخت وجود داشته باشد. سپس تقاطع ها از نمودار تولید شده شناسایی می شوند. روش بسیار مشابهی توسط Niehoefer و همکاران استفاده شده است. ، که هر اثر جدید را با یک نقشه موجود ادغام می کند و موقعیت جاده های موجود را به روز می کند [ 10]. همه روش‌های ذکر شده در بالا از تولید لبه‌های جاده‌ای جعلی از ردیابی GPS با خطای بالا رنج می‌برند.

ما روشی را برای استنباط توپولوژی شبکه جاده از طریق شناسایی تقاطع پیشنهاد می کنیم و به استخراج نمایش هندسی هر بخش جاده با تراز مسیر ادامه می دهیم. اولین مشارکت ما تشخیص تقاطع ها با خوشه بندی نقاط عطف در ردیابی GPS و استفاده از این تقاطع های شناسایی شده برای تقسیم ردیابی GPS به قطعات مربوط به بخش های جاده است. ما همچنین یک استراتژی “کشش و سپس فشرده سازی” برای DTW ارائه می دهیم تا همه مسیرها را برای هر بخش جاده تراز کند. مسیرهای پیچ و تاب تولید شده در طول تراز برای استخراج یک مسیر متوسط استفاده می شود تا به عنوان یک نمایش هندسی برای هر بخش جاده عمل کند. این مسیرهای پیچ و تاب همچنین می توانند برای تجزیه و تحلیل زمانی مسیرها، مانند واریانس سرعت، استفاده شوند.

به طور خلاصه، مشارکت های اصلی ما دو برابر است. ابتدا، ما روشی را برای تشخیص تقاطع ها با خوشه بندی نقاط عطف در داده های مسیر پیشنهاد می کنیم. دوم، ما یک استراتژی “کشش و سپس فشرده سازی” را برای تراز کردن تمام مسیرها برای هر بخش جاده با استفاده از DTW معرفی می کنیم، و مسیرهای پیچ و تاب تولید شده برای استنتاج هندسه بخش جاده استفاده می شود. نتایج ما عملکرد بهتری را با حذف بسیاری از جاده‌های جعلی و همچنین مکان‌های جغرافیایی دقیق‌تر برای جاده‌های شناسایی‌شده نشان می‌دهد. Biagioni به طور مقایسه ای برخی از روش های موجود برای استنتاج شبکه راه را ارزیابی کرد [ 16 ]. ما روش خود را با کار Biagioni بر روی همان مجموعه داده GPS در این مقاله مقایسه می کنیم.

3. استنباط شبکه راه

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

تقاطع ها: تقاطع های جاده ای با موقعیت جغرافیایی آنها نشان داده می شوند $q = {(x, y)}^{T}$ ، که در آن x و y مختصاتی در طول و عرض جغرافیایی هستند. تقاطع را می توان به عنوان مکانی تعریف کرد که در آن کاربران می توانند مسیرها را به روش های مختلف تغییر دهند، بدون توجه به تعداد بخش های جاده ای که در یک تقاطع خاص ملاقات می کنند. تقاطع ها از پیچ ها در جاده ها منحصر به فرد هستند، که فقط به کاربران اجازه می دهد یک تغییر جهت را ایجاد کنند.
نمودار اتصال: اگر یک جفت تقاطع مستقیماً توسط یک بخش جاده که شامل هیچ تقاطع دیگری نباشد، به هم متصل شوند، نمودارهای اتصال جاده کدگذاری می‌کنند. این نمودارها با یک باینری نمایش داده می شوند $M \times M$ ماتریس اتصال C ، با M تعداد تقاطع ها. طبق تعریف، $C_{i, j} = 1$ اگر تقاطع‌های i و j مستقیماً توسط یک بخش جاده به هم متصل شوند. در مقاله ما، C نامتقارن است، به عنوان مثال ، $C_{i, j}$ می تواند متفاوت باشد $C_{j, i}$ به دلیل ترافیک یک طرفه علاوه بر این، فرض می‌کنیم که عناصر مورب اصلی C صفر هستند، یعنی یک تقاطع به خودش متصل نیست.
بخش های جاده: بخش های جاده هدایت شده R جفت تقاطع ها را به هم متصل می کنند. هندسه هر بخش جاده با استفاده از یک توالی از مکان های جغرافیایی نشان داده شده است. در این مقاله، میانگین سرعت و واریانس سرعت در طول هر بخش جاده با استفاده از ردیابی GPS تجزیه و تحلیل خواهد شد. با این حال، نوع جاده و تعداد خطوط جاده مورد تجزیه و تحلیل قرار نخواهد گرفت.

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

دوم، ما تمام ردیابی های GPS را بر اساس تقاطع های شناسایی شده تقسیم بندی می کنیم. کاربران دستگاه‌های GPS اغلب مسیرهای مختلفی را به سمت یک مقصد دنبال می‌کنند و ردیابی‌های GPS متفاوتی با سرعت‌ها و مکان‌های متغیر ایجاد می‌کنند. با این حال، همه ردیابی ها بخش های مشترک مربوط به بخش های جاده را به اشتراک خواهند گذاشت.

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

3.1. تشخیص نقطه عطف

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

شکل 1. مروری بر روش پیشنهادی.

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

بنابراین، جهت حرکت کاربر در

(x_{a}, y_{a})

به صورت زیر محاسبه می شود:

با توجه به یک نقطه در ردیابی GPS،

(x_{a}, y_{a})

، نقطه دوم را انتخاب می کنیم،

(x_{b}, y_{b})

، یعنی 2 متر جلوتر در همان مسیر. اگر چنین نقطه ای وجود نداشته باشد، نقطه مجاور بعدی را انتخاب می کنیم. جهت حرکت کاربر در

(x_{a}, y_{a})

به صورت زیر محاسبه می شود:

θ آ = ⎧ ⎩ ⎨ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ ⎪ آرکتان y ب - y آ ایکس ب - ایکس آ آرکتان y ب - y آ ایکس ب - ایکس آ + π آرکتان y ب - y آ ایکس ب - ایکس آ - π - π 2 + π 2 ایکس ب > ایکس آ y ب \geq y آ ، ایکس ب < ایکس آ y ب < y آ ، ایکس ب < ایکس آ y ب > y آ ، ایکس ب = ایکس آ y ب < y آ ، ایکس ب = ایکس آ

(1)

جایی که $θ_{a} \in [- π, π]$ ( $- π$ غرب است، رادیان در خلاف جهت عقربه های ساعت).

جهت حرکت کاربر،

θ_{b}

، در نقطه

(x_{b}, y_{b})

به طور مشابه با استفاده از نقطه بعدی در ردیابی GPS که در فاصله ثابتی قرار دارد محاسبه می شود. اگر جهت تغییر کند

Δ θ_{b} = θ_{b} - θ_{a}

بین نقاط

(x_{a}, y_{a})

(x_{b}, y_{b})

از یک آستانه از پیش تعریف شده فراتر می رود، سپس به عنوان یک نقطه عطف در نظر گرفته می شود.

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

شکل 2. نمونه ای از چرخش. بخشی از ردیابی GPS در اطراف یک تقاطع با یک خط سیاه با دایره هایی که موقعیت ضبط داده ها را نشان می دهد و فلش هایی که جهت حرکت را در هر نقطه نشان می دهد نشان داده می شود.

خروجی این مرحله مجموعه ای از نقاط عطف است

{p^{(v)}, v = 0, \dots V - 1}

، که با بررسی تغییر جهت حرکت در هر نقطه در امتداد تمام ردیابی های GPS به همراه نشانگرهای باینری از ورود کاربر به تقاطع شناسایی می شوند.

{e_{1}^{v}, v = 0, \dots V - 1}

یا از تقاطع خارج می شود

{e_{2}^{(v)}, v = 0, \dots V - 1}

در یک نقطه عطف خاص، جایی که

e_{1}^{(v)} \in [0, 1]

e_{2}^{(v)} \in [0, 1]

e_{1}^{(v)} = 1

نشان می دهد که کاربر در نقطه عطف v وارد یک تقاطع می شود و صفر نشان دهنده عدم ورود است. در بخش بعدی توضیح می‌دهیم که چگونه این نقاط عطف در تقاطع‌ها دسته‌بندی می‌شوند.

3.2. استخراج تقاطع

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

P_{i} = {p_{i}^{(n)}

n = 0 \dots | P_{i} | - 1}

، با

| P_{i} |

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

الگوریتم 1 نقاط عطف خوشه.

ورودی:

{p^{(v)}

v = 0 \dots V - 1}

خروجی:

{P_{i} : | P_{i} | > T_{min}

i = 0 \dots I - 1}

1: مقداردهی اولیه

P_{u n} \leftarrow {p^{(v)}

v = 0 \dots V - 1}

i \leftarrow 0

2: برای هر کدام

p \in P_{u n}

انجام دادن

P_{o u t} = \emptyset

P_{i} = {p}

4: برای هر کدام

p^{'} \neq p \in P_{u n}

انجام دادن

5: اگر

\frac{1}{| P_{i} |} \sum_{p^{″} \in P_{i}} d (p^{'}, p^{″}) \leq d_{t h r e}

سپس

d_{t h r e}

آستانه از پیش تعریف شده برای میانگین فاصله اقلیدسی است.

P_{i} \leftarrow P_{i} \cup {p^{'}}

7: پایان اگر

8: پایان برای

P_{u n} = P_{u n} \ P_{i}

10: پایان برای

برای حذف پیچ‌های جاده‌ای که اشتباهاً شناسایی شده‌اند از خوشه‌ها، جایی که کاربران جاده ممکن است جهت حرکت خود را نیز تغییر دهند، باید نوع پیچ‌های هر خوشه را با استفاده از ورودی بررسی کنیم (با

e_{1}^{(v)} = 1

) و نقاط عطف خروجی (با

e_{2}^{(v)} = 1

) همانطور که در مرحله قبل توضیح داده شد. همانطور که در شکل 3 نشان داده شده است، نقاط عطف ورودی و خروجی را انتخاب کرده و جهت آنها را به طور جداگانه برای هر خوشه از نقاط عطف خوشه بندی می کنیم. اگر جهت ورود و خروج ثابت بماند (برای یک قطعه جاده یک طرفه) یا مخالف باشد (برای یک قطعه جاده دو طرفه)، این خوشه حذف خواهد شد، زیرا نقاط عطف در این خوشه در یک خم قرار دارند. یک تقاطع

در نهایت، مکان های فضایی

q_{m}

خوشه ها با میانگین گیری نقاط عطف در هر خوشه به دست می آیند. نتیجه مجموعه ای از تقاطع ها است

Q = {q_{m}, m = 0, \dots, M - 1}

3.3. تجزیه و تحلیل اتصال و تقسیم بندی ردیابی GPS

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

شکل 3. تشخیص خم. خمیدگی ها با بررسی مسیرهای ورود و خروج شناسایی می شوند.

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

{r^{(n)}, n = 0, \dots, N - 1}

، با آهنگ n متشکل از

L_{n}

نکته ها

r^{(n)} = (r^{(n)} (0), \dots, r^{(n)} (L_{n} - 1))

. به طور مشخص،

r^{(n)} (i) = (x^{(n)} (i), y^{(n)} (i))

از طول و عرض جغرافیایی نقطه i در مسیر n تشکیل شده است .

3.4. تراز مسیر

برای همان بخش جاده، مسیرهای GPS از همان دو تقاطع شروع و پایان می‌یابند. اگرچه مسافت جغرافیایی که هر مسیر طی می کند مشابه طول بخش جاده است، تراکم نقطه GPS مکانی مسیرها متفاوت است زیرا وسایل نقلیه می توانند با سرعت های مختلف حرکت کنند. اگر کاربر با سرعت بیشتر در جاده ها حرکت کند، نقاط GPS کمتری ثبت می شود و بالعکس. وظیفه اصلی این بخش یافتن تناظرهای نقطه ای بین تمام مسیرها و میانگین گیری آنها برای تشکیل یک نمایش واحد از بخش جاده است. با این حال، به دلیل سرعت‌های متفاوت در هر مسیر، تشخیص دقیق نقاط مربوطه دشوار است. برخی از روش‌های ساده‌لوحانه می‌توانند مطابقت‌های زمانی ناسازگار ایجاد کنند. در این مقاله برای حل این مشکل از زمان تابش پویا (DTW) استفاده می کنیم. ما با توضیح اصل DTW برای استفاده با تراز دو مسیر شروع می کنیم و سپس با استفاده از استراتژی “کشش و سپس فشرده سازی” خود برای تراز چند مسیر، رویکرد را تعمیم می دهیم. میانگین مسیر با استفاده از ترازهای مسیرها محاسبه خواهد شد.

3.4.1. تراز دو مسیر با استفاده از DTW

DTW یک الگوریتم هم ترازی سری زمانی است که در اصل برای تشخیص گفتار توسعه یافته است [ 25 ]. سعی می‌کند یک هم‌ترازی زمانی بین دو سیگنال پیدا کند که اندازه‌گیری شباهت بین نمونه‌های دو سیگنال را با تاب برداشتن محور زمانی آنها به حداکثر می‌رساند.

با توجه به دو آهنگ از نقاط

(r^{(0)} (0), \dots, r^{(0)} (L_{0} - 1)

(r^{(1)} (0), \dots, r^{(1)} (L_{1} - 1)

و اندازه گیری فاصله بین جفت نقطه، مشکل یافتن بهترین هم ترازی را می توان به عنوان یافتن یک ارتباط توصیف کرد.

(l_{0} (0), \dots, l_{0} (K_{0} - 1))

(l_{1} (0), \dots, l_{1} (K_{0} - 1))

که فاصله کل را به حداقل می رساند.

D Γ (r (0) ، r (1)) = △ دقیقه (ل 0 ، ل 1) \in Γ \sum ک 0 = 0 ک 0 - 1 ∥ ∥ r (0) (ل 0 (ک 0)) - r (1) (ل 1 (ک 0)) ∥ ∥ 2

(2)

جایی که $l_{0} (k_{0})$ و $l_{0} (k_{0})$ موارد زمانی مربوطه را مرتبط کنید $l_{0}$ از آهنگ اول و $l_{1}$ از آهنگ دوم همه این گونه انجمن ها مجاز نیستند. به طور خاص، ما فقط مسیرهای پیچ و تاب را در نظر می گیریم که به زیرمجموعه Γ از همه انجمن های ممکن تعلق دارند و محدودیت های زیر را برآورده می کنند:

شرایط مرزی: مسیر Warp باید از ابتدای هر سری زمانی شروع شود و در پایان هر سری زمانی پایان یابد: $l_{0} (0) = 0$ ، $l_{0} (K_{0} - 1) = L_{0} - 1$ ، $l_{1} (0) = 0$ و $l_{1} (K_{0} - 1) = L_{0} - 1$ .
یکنواختی: مسیر تاب باید در هر دو محور زمانی به صورت یکنواخت بدون کاهش باشد: $l_{0} (k_{0}) \leq l_{0} (k_{0} + 1)$ و $l_{1} (k_{0}) \leq l_{1} (k_{0} + 1)$ .
تداوم: هر دو مرحله مجاور مسیرهای پیچ و تاب دنبال می شوند $(l_{0} (k_{0}) - l_{0} (k_{0} - 1), l_{1} (k_{0}) - l_{1} (k_{0} - 1)) \in {(0, 1), (1, 0), (1, 1)}$ . با این محدودیت، مسیر تار برای هر مسیر حداکثر یک نقطه در یک زمان حرکت می کند.

پس از محاسبه توابع

l_{0} (k_{0})

l_{1} (k_{0})

، آهنگ ها

r^{(0)}

r^{(1)}

اکنون به این معنا تراز شده‌اند که در همان شاخص k به موقعیت‌های مکانی نزدیک می‌رسند و در نتیجه مسیرهای تابدار جدید با

K_{0}

نکته ها

r_{1}^{(0)} = (r_{1}^{(0)} (0), \dots, r_{1}^{(0)} (K_{0} - 1))

r_{1}^{(1)} = (r_{1}^{(1)} (0), \dots, r_{1}^{(1)} (K_{0} - 1))

، جایی که

r_{1}^{(0)} (k_{0}) = r^{(0)} (l_{0} (k_{0}))

r_{1}^{(1)} (k_{0}) = r^{(1)} (l_{1} (k_{0}))

. برای به دست آوردن یک تراز بهینه، این احتمال وجود دارد که این مسیرهای تابدار دارای نقاط تکراری باشند.

برای تراز کردن دو مسیر با استفاده از DTW، ابتدا ماتریس فاصله را محاسبه می کنیم

D_{L_{0} \times L_{1}}^{(1)}

برای هر جفت نقطه GPS در هر دو مسیر، جایی که عنصر

d^{(1)} (l_{0}, l_{1})

در

l_{0}

ردیف -امین و

l_{1}

– ستون از

D^{(1)} L_{0} \times L_{1}

نشان دهنده فاصله بین

(l_{0})

نقطه -ام در آهنگ

r^{(0)}

(l_{1})

نقطه -ام در آهنگ

r^{(1)}

. سپس ماتریس فاصله انباشته شده را محاسبه می کنیم

D_{L_{0} \times L_{1}}^{(2)}

از ماتریس فاصله

D_{L_{0} \times L_{1}}^{(1)}

، جایی که عنصر

d^{(2)} (l_{0}, l_{1})

در

(l_{0}, l_{1})

که در

D_{L_{0} \times L_{1}}^{(2)}

با افزودن مقدار محاسبه می شود

d^{(1)} (l_{0}, l_{1})

همراه با حداقل مقدار

\{d^{(2)} (l_{0} - 1, l_{1}), d^{(2)} (l_{0}, l_{1} - 1), d^{(2)} (l_{0} - 1, l_{1} - 1)\}

سپس مسیرهای پیچ و تاب از ماتریس انباشته جستجو می شوند

D^{(2)}

به ترتیب نزولی، با شروع در

d^{(2)} (L_{0}, L_{1})

و به پایان می رسد

d^{(2)} (1, 1)

تحت شرایط مرزی مرحله قبل

(w^{(0)} (k_{0} - 1), w^{(1)} (k_{0} - 1)

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

\{d^{(2)} (l_{0} - 1, l_{1}), d^{(2)} (l_{0}, l_{1} - 1), d^{(2)} (l_{0} - 1, l_{1} - 1)\}

. این تضمین می کند که روند جستجو شرایط تداوم و یکنواخت را برآورده می کند.

نمونه ای از تراز کردن دو مسیر در شکل 4 نشان داده شده است . 18 امتیاز در مسیر وجود دارد

r^{(0)}

، که با یک خط آبی با مربع نشان می دهد که موقعیت نقاط داده را نشان می دهد. مسیر

r^{(1)}

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

r^{(0)}

و عمودی برای Track است

r^{(1)}

. بهترین تراز آهنگ

r^{(0)}

r^{(1)}

را می توان به عنوان یافتن مسیری از طریق شبکه از شبکه پایین سمت چپ توصیف کرد

(1, 1)

به شبکه سمت راست

(18, 19)

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

شکل 4. نمونه ای از تراز دو مسیر. ( الف ) عناصر در دو مسیر با استفاده از DTW با فاصله بین این عناصر به عنوان ویژگی جفت می شوند. ( ب ) مسیر پیچ و تاب با محور افقی و عمودی نشان دهنده شاخص زمانی مسیر است

r^{(0)}

و آهنگ

r^{(1)}

بصورت جداگانه.

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

r^{(n)}

به تمام مسیرهای دیگر متعلق به همان بخش جاده به عنوان محاسبه می شود

\sum_{m \neq n, m = 0}^{m = N_{i} - 1} S (r^{(n)}, r^{(m)})

، در حالی که

S (r^{(n)}, r^{(m)})

میانگین فاصله فضایی بین دو مسیر است.

اس (r (n) ، r (متر)) = △ 1 ک D Γ (r (n) ، r (متر))

(3)

که در آن K طول مسیرهای تاب آنها است.

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

3.4.2. استراتژی “کشش و سپس فشرده سازی”.

رویه DTW فقط امکان تراز کردن دو مسیر را می دهد. برای جفت مسیرهای مختلف، مسیرهای پیچ و تاب آنها و طول مسیرهای تابدار می تواند متفاوت باشد. بنابراین، یافتن یک مسیر نرمال شده برای تراز کردن همه جفت‌های ممکن از مسیرها با هم دشوار است. ما اکنون یک استراتژی “کشش و سپس فشرده سازی” را برای فعال کردن تراز چند مسیر همه مسیرها پیشنهاد می کنیم. این استراتژی از دو عملیات مختلف تشکیل شده است، یک (1) عملیات کشش و سپس یک (2) عملیات فشرده سازی، همانطور که در زیر توضیح داده شده است.

(1) کشش: مسیر

r^{(0)}

با

L_{0}

امتیاز و آهنگ

r^{(1)}

با

L_{1}

نقاط به دنبال تاب

(r^{(0)} (l_{0} (0)), \dots, r^{(0)} (l_{0} (K_{0} - 1)))

و آهنگ

(r^{(1)} (l_{1} (0)), \dots, r^{(1)} (l_{1} (K_{0} - 1)))

به طور جداگانه با استفاده از DTW برای کشش هر دو مسیر برای مهار

K_{0}

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

K_{0} ⩾ L_{0} a n d K_{0} ⩾ L_{1}

که به آن “کشش” می گویند.

(2) فشرده سازی: برخی از نقاط یک مسیر با همان نقطه در مسیر دیگر مطابقت دارند، که منجر به تناظر چند به یک بین نقاط داده در مسیرهای کشیده می شود. ما مسیرهای کشیده شده را با کوچک کردن نقاط داده آنها فشرده می کنیم، که از همان نقطه داده در مسیر اصلی منحرف شده اند. ما فقط نقطه ای را با کمترین فاصله تا نقطه مربوطه در مسیر کشیده دیگر نگه می داریم. به این ترتیب، آهنگ های کشیده شده است

(r^{(0)} (l_{0} (0)), \dots, r^{(0)} (l_{0} (K_{0} - 1)))

(r^{(1)} (l_{1} (0)), \dots, r^{(1)} (l_{1} (K_{0} - 1)))

به Track فشرده می شوند

r_{c}^{(0)}

r_{c}^{(1)}

با

J_{0}

نقاط، ایجاد مسیرهای فشرده سازی

w_{c}^{(0)}

w_{c}^{(1)}

، جایی که

r_{c}^{(0)} (j_{0}) = r^{(0)} (l_{0} (k_{0} (j_{0})))

r_{c}^{(1)} (j_{0}) = r^{(1)} (l_{1} (k_{0} (j_{0})))

w_{c}^{(0)} (j_{0}) = l_{0} (k_{0} (j_{0}))

w_{c}^{(1)} (j_{0}) = l_{1} (k_{0} (j_{0}))

l_{0} (k_{0} (j_{0}))

شاخص موقعیت مکانی است

j_{0}

-مین نقطه از مسیر فشرده

r_{c}^{(0)}

در آهنگ اصلی

r^{(0)}

و شاخص موقعیت مکانی است

j_{0}

-مین نقطه از مسیر فشرده

r_{c}^{(1)}

در آهنگ اصلی

r^{(1)}

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

J_{0} ⩽ L_{0} a n d J_{0} ⩽ L_{1}

3.4.3. تراز چند آهنگ

ما با استفاده از استراتژی «کشش و سپس فشرده‌سازی» چندین مسیر را تراز می‌کنیم تا همه آهنگ‌ها را یکی یکی از اولین تا آخرین آهنگ به‌طور متوالی پردازش کنیم.

بلوک 1 در شکل 5 روش ارائه شده در زیر را نشان می دهد:

(الف) آهنگ

r^{(0)}

با

L_{0}

امتیاز و آهنگ

r^{(1)}

با

L_{1}

نقاط ورودی به ماژول “کشش و سپس فشرده سازی” هستند تا آهنگ های یک بار فشرده شده را بدست آورید.

r_{c}^{(0)}

r_{c}^{(1)}

. مسیرهای فشرده سازی

w_{c}^{(0)}

w_{c}^{(1)}

شاخص های مکان Track را شرح دهید

r_{c}^{(0)}

و آهنگ

r_{c}^{(1)}

در آهنگ های اصلی،

r^{(0)}

r^{(1)}

، به طور جداگانه، که در آن c به معنای یک بار فشرده سازی در اینجا است.

(ب) آهنگ یک بار فشرده

r_{c}^{(1)}

و آهنگ

r^{(2)}

ورودی های ماژول “کشش و سپس فشرده سازی” هستند که منجر به دوبار فشرده شدن آهنگ می شود

r_{2 c}^{(1)}

و آهنگ یکبار فشرده شده

r_{c}^{(2)}

، جایی که

2 c

یعنی اینجا دوبار فشرده شده. مسیرهای فشرده سازی

w_{2 c}^{(1)}

شاخص های زمانی مسیر دوبار فشرده شده را ذخیره کنید

r_{2 c}^{(1)}

در مسیر یکبار فشرده شده

r_{c}^{(1)}

w_{c}^{(2)}

برای شاخص های زمانی مسیری که یک بار فشرده شده است

r_{c}^{(2)}

در آهنگ اصلی

r^{(2)}

r_{c}^{(n)}

و آهنگ جدید

r^{(n + 1)}

، به ماژول “کشش و سپس فشرده سازی” تا آخرین آهنگ وارد می شوند

r^{(N - 1)}

پردازش می شود.

خروجی های بلوک 1 تراک های یک بار فشرده شده برای اولین و آخرین تراک هستند

r_{c}^{(0)}

r_{c}^{(N - 1)}

، آهنگ های دوبار فشرده شده برای آهنگ های دیگر

{r_{2 c}^{(n)}, n = 1, \dots, N - 2}

، مسیرهای فشرده سازی

{w_{c}^{(n)}, n = 0, \dots, N - 1}

، که شاخص های زمانی تراک های یک بار فشرده شده را در مسیرهای اصلی و مسیرهای فشرده نگه می دارد.

{w_{2 c}^{(n)}, n = 1, \dots, N - 2}

برای نمایه‌های مکان آهنگ‌های دوبار فشرده‌شده در مسیرهای یک‌بار فشرده‌شده.

شکل 5. تراز چند مسیر. در بلوک 1، مسیرها یک به یک به ترتیب تصادفی با استفاده از “کشش و سپس فشرده سازی” تراز می شوند و مسیرهای میانی را تولید می کنند. بلوک 2 نحوه یافتن مسیرهای نرمال شده را نشان می دهد که برای تراز کردن همه مسیرها با مطابقت یک به یک در بین نقاط با استفاده از مسیرهای میانی تولید شده در بلوک 1 استفاده می شود.

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

r_{2 c}^{(n)}

را می توان به راحتی مکان یابی کرد. بدون مرحله فشرده‌سازی، مسیرها با مکاتبات چند به یک طولانی‌تر و طولانی‌تر می‌شوند، زیرا مسیرهای جدید با استفاده از DTW تاب می‌خورند که منجر به افزایش هزینه‌های محاسباتی می‌شود.

بلوک 2 نحوه یافتن مسیرهای نرمال شده را نشان می دهد

{w^{(n)}, n = 0, \dots, N - 1}

که با استفاده از مسیرهای میانی، تمام مسیرها را با تناظر یک به یک در میان نقاط تراز می کند

{w_{t}^{(n)}, n = N - 2, \dots, 1}

، و در نتیجه آهنگ های عادی شده است

{g^{(n)}, n = 0, \dots N - 1}

با همان طول مسیر نرمال شده

w^{(n)}

اطلاعات مکان نقاط مسیر نرمال شده را حفظ می کند

g^{(n)}

در آهنگ اصلی

r^{(n)}

در میان آهنگ های خروجی از بلوک 1، آخرین آهنگ یک بار فشرده شده

r_{c}^{(N - 1)}

با

J_{N - 2}

امتیاز کوتاه ترین مسیر است، از آن زمان

J_{n}

همیشه کوتاهتر از

J_{n - 1}

. در روش ما،

r_{c}^{(N - 1)}

به عنوان مسیر عادی گرفته می شود

g^{(N - 1)}

برای آهنگ

r^{(N - 1)}

. برای آهنگ های دیگر، نقاط داده ای که مطابقت دارند

g^{(N - 1)}

ابتدا از مسیرهای دوبار فشرده شده انتخاب می شوند. شاخص های زمانی نقاط داده از

g^{(n)}

که در

r_{c}^{(n)}

با استفاده از یک مسیر میانی ایندکس می شوند

w_{t}^{(n)}

، جایی که t به یک مسیر میانی موقت اشاره دارد. شاخص های زمانی نقاط داده از

g^{(n)}

در مسیر ورودی اصلی

r^{(n)}

را می توان با استفاده از مسیر میانی پیدا کرد

w_{t}^{(n)}

و مسیر پیچ و تاب

w_{c}^{(n)}

w (n) تی = ⎧ ⎩ ⎨ w (ن - 2) 2 ج w (n) 2 ج (w (n + 1) تی) n = N - 2 n = N - 3 ، \dots ، 1

(4)

w (n) = ⎧ ⎩ ⎨ w (ن - 1) ج w (n) ج (w (n) تی) n = N - 1 n = N - 2 ، \dots ، 0

(5)

مسیر عادی شده

g^{(n)}

با انتخاب به دست می آید

K = J_{N - 2}

امتیاز از

r^{(n)}

با توجه به مسیر تاب نرمال شده آن

w^{(n)}

، یعنی _

g^{(n)} = r^{(n)} (w^{(n)})

شکل 6. مثالی از تراز چهار مسیر. ( الف ) نقاط داده آهنگ ها را در طول زمان نشان می دهد. در شکل 2، آهنگ ها

r^{(0)}

r^{(1)}

کشیده و فشرده می شوند و در نتیجه

r_{c}^{(0)}

r_{c}^{(1)}

، با خطوط سیاه نشان دهنده ارتباط آنها است. یک آهنگ یکبار فشرده شده و یک آهنگ جدید به ماژول “کشش و سپس فشرده سازی” وارد می شوند تا مطابقت یک به یک بین آهنگ های زیرشکل های 3 و 4 را بیابند. شکل فرعی 5 نحوه انجام مسیر نرمال شده را توسط خطوط اتصال پیدا کنید. ( ب ) نشان می دهد که چگونه نقاط داده مسیرهای نرمال شده از مسیرهای اصلی در طول مسیر نرمال شده انتخاب شده و با استفاده از خطوط سیاه به هم متصل می شوند.

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

r^{(0)}

r^{(1)}

ورودی های ماژول “کشش و سپس فشرده سازی” هستند که منجر به

r_{c}^{(0)}

r_{c}^{(1)}

که به صورت دایره ای نشان داده شده اند و با خطوط مشکی به هم متصل می شوند. پنج امتیاز در

r^{(0)}

و یکی در

r^{(1)}

حذف می شوند. شکل فرعی بعدی نتایج Tracks را نشان می دهد

r_{c}^{(1)}

r^{(2)}

تراز به عنوان خطوط متصل از

r_{2 c}^{(1)}

به

r_{c}^{(2)}

. در شکل فرعی چهارم،

r_{2 c}^{(2)}

r_{c}^{(3)}

کشیده و فشرده می شوند

r_{c}^{(2)}

r^{(3)}

بصورت جداگانه. نقاط داده سایر آهنگ ها که مطابقت دارند

r_{c}^{(3)}

می توان با دنبال کردن خطوط اتصال، یعنی مسیرهای فشرده سازی، از پایین به بالا قرار گرفت. شکل 6 ب مکان فیزیکی نقاط برای هر مسیر را نشان می دهد. در این چهار مسیر به ترتیب 16، 13، 14 و 10 امتیاز وجود دارد. پس از تراز، 9 نقطه داده در هر آهنگ نگهداری می شود که با یکدیگر مرتبط هستند.

3.5. تحلیل آماری

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

{g^{(n)}, n = 0, \dots, N - 1}

با طول K یکسان ، که طبق مسیرهای تاب نرمال شده تاب می‌خورند

{w^{(n)}, n = 0, \dots, N - 1}

، آهنگ متوسط

g = (g (0), \dots, g (K - 1))

می توان از مسیرهای نرمال شده در امتداد مسیرهای پیچ و تاب استخراج کرد.

g (k) = 1 ن \sum n = 0 ن - 1 g (n) (ک)

(6)

با توجه به سرعت در هر نقطه از مسیر نرمال شده

(s^{(n)} (0), \dots, s^{(n)} (K - 1)

، جایی که

n = 0, \dots, N - 1}

، سرعت متوسط،

μ (k)

و واریانس سرعت،

δ (k)

، در امتداد مسیر میانگین به صورت زیر محاسبه می شود:

μ (k) = 1 ن \sum n = 0 ن - 1 س (n) (ک)

(7)

δ (k) = 1 ن \sum n = 0 ن - 1 (س (n) (k) - μ (k)) 2

(8)

جایی که $k = 0, \dots, K - 1$ .

4. ارزیابی عملکرد الگوریتم

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

4.1. محاسبه دقت توپولوژیکی

تقاطع های ما از ردیابی GPS استخراج شده است. به دلیل دقت و نقاط پرت محدود در ردیابی های GPS، هم ممکن است تقاطع های «جعلی» را که در نقشه حقیقت زمینی وجود ندارند شناسایی کنیم، و هم ممکن است نتوانیم برخی از تقاطع های واقعی را شناسایی کنیم (به عنوان مثال، که در نقشه حقیقت زمین وجود دارد . ). دقت تقاطع ها به سه جنبه اصلی بستگی دارد: تعداد تقاطع های “همسان” که با موفقیت شناسایی می شوند، تعداد تقاطع های “جعلی” و تعداد تقاطع های “مفقود شده”.

در این مقاله از دو پارامتر برای تعیین کمیت دقت تقاطع ها استفاده می کنیم:

i_{s}

، نسبت تقاطع های “جعلی” و

i_{m}

، نسبت تقاطع های “فقدان” [ 16 ]; هر دو در زیر تعریف شده اند.

من س = من س من س + من ج من متر = من متر من متر + من ج

(9)

جایی که $I_{s}$ تعداد تقاطع های جعلی است، $I_{c}$ تعداد تقاطع هایی که به درستی تطبیق داده شده اند و $I_{m}$ تعداد تقاطع های غیر همسان، به عنوان مثال ، از دست رفته.

امتیاز F شناخته شده ، بر اساس ترکیبی از دقت و یادآوری، به عنوان نمره کیفیت کلی استفاده می شود:

اف من = 2 ( 1- _ من س ) ( 1 - من متر ) ( 1- _ من س ) + ( 1 - من متر )

(10)

مقادیر بالاتر از

F_{i}

-score نشان می دهد که تشخیص تقاطع دقیق تر است [ 21 ].

مشابه شاخص های کیفیت تقاطع، ما همچنین شاخص های کیفیت را برای اتصال بین تقاطع ها تعریف می کنیم:

r_{s}

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

r_{m}

نسبت بخش‌های جاده‌ای «مفقودشده» که در نقشه حقیقت زمینی وجود دارد، اما شناسایی نمی‌شوند، و

F_{r}

امتیاز F مربوطه

4.2. ارزیابی دقت جغرافیایی

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

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

یک راه حل جزئی می تواند اعمال DTW برای تراز کردن سری های دو نقطه و تاب برداشتن آنها به سری های جدید با طول یکسان، سپس محاسبه معیار کیفیت در آن بخش های مسیر تاب خورده باشد. با این حال، این مشکل را به طور کامل حل نمی کند، زیرا سری های تاب خورده فقط می توانند حاوی نقاط تکرار شونده باشند، اما هرگز نمی توانند داده های از دست رفته را “پر کنند”. بنابراین، شکاف‌های زمانی بزرگ در حقیقت زمین یا داده‌های استنباط‌شده می‌تواند منجر به فواصل مکانی بزرگ بین حقیقت زمین و داده‌های استنتاج شده شود، حتی اگر بخش‌های مسیر در غیر این صورت بسیار مشابه باشند. به عنوان مثال، نقاط اول و دوم جاده تولید شده در شکل 7a با استفاده از DTW با اولین نقطه روی حقیقت زمین تطبیق داده می شود، زیرا هیچ نقطه نزدیکتری روی حقیقت زمین یافت نمی شود. فاصله بین این نقاط جفت شده در واقع بزرگتر از فاصله واقعی بین بخش جاده تولید شده و حقیقت زمینی آن است [ 27 ].

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

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

5. آزمایشات

یک مجموعه داده از 889 GPS ردیابی در طول 118 ساعت از شاتل های دانشگاه ایلینویز برای آزمایش الگوریتم پیشنهادی استفاده می شود. این مجموعه داده را می توان به صورت عمومی در وب سایت آزمایشگاه BITS آنها [ 28]. داده‌های GPS توسط رانندگان شاتل دانشگاه جمع‌آوری می‌شوند که یک آیفون دارند که برنامه ردیابی آزمایشگاه BITS را اجرا می‌کند. اگرچه برنامه آیفون آنها هر ثانیه موقعیت مکانی GPS خود را به سرور خود ارسال می کند، سرور گاهی اوقات داده های GPS را دریافت نمی کند که منجر به فاصله نمونه گیری متفاوتی از 1 ثانیه تا 29 ثانیه می شود (میانگین: 3.61 ثانیه؛ انحراف استاندارد: 3.67 ثانیه). اگرچه ضبط‌های GPS آنها از یک دستگاه است، روش ما به نرخ نمونه‌گیری یکسانی نیاز ندارد. شاتل های شرکت کننده از هر دو منطقه با ساختمان های کم ارتفاع و سایر مناطق با خطای GPS قابل توجه به دلیل ساختمان های بلند حرکت می کنند. ردیابی خام GPS با خطوط سیاه در شکل 8 نشان داده شده است .

برای اندازه‌گیری دقت شبکه جاده‌ای که از ردیابی شاتل ایجاد می‌شود، OpenStreetMap را به عنوان نقشه حقیقت زمینی انتخاب می‌کنیم. اگرچه خطای موقعیتی ردیابی GPS در OpenStreetMap تقریباً 10 تا 20 متر است، اما به دلیل دسترسی منبع باز و پوشش وسیع، همچنان به عنوان حقیقت اصلی برای تحقیقات در تولید شبکه جاده ای استفاده می شود. از آنجایی که شاتل ها همه خیابان ها را در OpenStreetMap کاوش نکردند [ 29 ]، شبکه جاده ای تولید شده تنها جایی که شاتل ها رفتند را پوشش می دهد. نقشه حقیقت زمینی به صورت دستی به خیابان هایی کاهش می یابد که در واقع توسط شاتل ها عبور کرده اند. شکل 9 نقشه حقیقت زمین را با دایره های قرمز برای تقاطع ها و خطوط سیاه با دایره های سیاه و سفید برای بخش های جاده نشان می دهد.

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

شکل 9. نقشه حقیقت زمین. نقشه حقیقت زمینی هدایت شده به صورت دستی از طریق کاهش نقشه خیابان باز این منطقه به خیابان هایی که شاتل ها از آن عبور می کنند ساخته شده است.

5.1. نتایج با استفاده از روش ما

5.1.1. نقاط عطف و تقاطع استنباط شده

در شکل 8 ، نقاط عطف استخراج شده از همه 889 ردیابی GPS به صورت نقاط قرمز نشان داده شده است. مکان هایی که بسیاری از نقاط عطف جمع می شوند و به عنوان تقاطع تشخیص داده می شوند، در شکل 8 با نقاط سبز نشان داده شده اند . گاهی اوقات، نقاط عطف جدا شده به دلیل خطاهای GPS یا پوشش ناکافی از شاتل شناسایی می شوند. این نقاط عطف جدا شده به عنوان تقاطع در الگوریتم ما در نظر گرفته نمی شوند. شکل 8 تقاطعی را نشان می دهد که ظاهراً بین آن وجود دارد

q_{14}

q_{15}

. با این حال، با استفاده از روش ما، هیچ تقاطعی در آنجا شناسایی نمی‌شود، زیرا تنها چند نقطه عطف مجزا وجود دارد.

در این مکان، شاتل همیشه بدون تغییر جهت حرکت می کند، احتمالاً به دلیل وجود یک پل. علاوه بر این، دو تقاطع در نقشه حقیقت زمین در اطراف محل تقاطع استخراج شده وجود دارد

q_{26}

با استفاده از روش ما ما متوجه شدیم که نقاط عطف در یک گروه قرار دارند

q_{26}

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

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

q_{22}

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

q_{18}

، چرخش به راست در

q_{22}

به

q_{24}

. بنابراین، تقاطع شناسایی شده است

q_{22}

به سمت جهت حرکت کرد

q_{24}

. میانگین فاصله بین تقاطع های شناسایی شده و حقیقت زمین آنها است

22.69

متر

شکل 10 a مسیرها را به صورت خطوط سرخابی نشان می‌دهد، برای جاده‌هایی که از تقاطع‌های شاخص پایین‌تر شروع می‌شوند و به تقاطع‌هایی با شاخص بالاتر ختم می‌شوند. شکل 10 ب جاده های تولید شده از این مسیرها را با فلش هایی نشان می دهد که جهت جاده ها را نشان می دهد. در حالی که مسیرهای نشان داده شده با خطوط آبی در شکل 10 ج برای جاده ها از تقاطع های شاخص بالاتر به تقاطع های شاخص پایین تر و شکل 10 d برای جاده های هدایت شده تولید شده از این مسیرها هستند. در مجموع 38 جاده در شکل 10 ب و 39 در شکل 10 د استخراج شده است که به این معنی است که 77 جفت تقاطع به طور مستقیم به یکدیگر متصل می شوند. از شکل 10، همچنین می دانیم که برخی از جاده ها یک طرفه هستند، به عنوان مثال بخش جاده بین تقاطع اول و سوم. شاتل ها همیشه از

q_{1}

به

q_{3}

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

q_{22}

q_{29}

در هر دو جهت با توجه به ردیابی GPS آنها. با این حال، همانطور که در شکل 9 نشان داده شده است، هیچ بخش جاده ای بین آنها در نقشه حقیقت زمینی وجود ندارد . این می تواند ناشی از ساخت و ساز موقت جاده باشد. مجموعه داده شیکاگو در آوریل 2011 ثبت شد، اما OpenStreetMap در آگوست 2014 مشاهده شد. با بررسی این بخش جاده در نمای خیابان Google در نزدیک‌ترین تاریخ‌ها به تاریخ دسترسی، جاده بین تقاطع

q_{22}

q_{29}

در می 2011 قابل دسترسی بود، اما به دلیل ساخت و ساز جاده در اکتبر 2014 مسدود شد.

شکل 10. جاده های هدایت شده. ( الف ) بخشی از مسیرها را نشان می‌دهد که برای تولید جاده‌های هدایت‌شده در ( ب ) میانگین می‌شوند. ( ج ) قسمت دیگر مسیرها را نشان می‌دهد که برای تولید جاده‌های هدایت‌شده در ( d ) میانگین می‌شوند.

5.1.2. جاده های استنباط شده

شکل 10 جاده های هدایت شده را در هر جهت به طور جداگانه نشان می دهد.

برای هر بخش جاده، سرعت متوسط و تغییرات سرعت در امتداد نقاط داده میانگین مسیر محاسبه شده در بخش 3.5 در شکل 11 نشان داده شده است . رنگ نقاط نشان دهنده نقاط قوت سرعت است و عرض باند در اطراف مسیر متوسط نشان دهنده تغییر سرعت است.

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

شکل 12 دقت توپولوژیکی شبکه جاده تولید شده را نشان می دهد، شکل 12 a دقت تقاطع ها و شکل 12 b دقت اتصال را نشان می دهد. آستانه تطبیق به عنوان فاصله مجاز بین تقاطع ها و موقعیت آنها در نقشه حقیقت زمین تعریف می شود. ما می توانیم ببینیم که با کمترین آستانه تطبیق 5 متری نشان داده شده در شکل 12الف، هیچ تقاطع منطبقی شناسایی نشد. در این حالت، تمام تقاطع های موجود در شبکه راه های تولید شده به عنوان تقاطع های جعلی و تمام تقاطع های موجود در نقشه حقیقت زمینی به عنوان تقاطع های گمشده طبقه بندی می شوند. همانطور که آستانه تطبیق بزرگتر می شود، تقاطع های بیشتری شناسایی شده و با حقیقت زمین مطابقت داده می شود و در نتیجه کاهش می یابد.

i_{s}

i_{m}

و بالاتر

F_{i}

. شکل 12 ب دقت اتصال بین تقاطع های شناسایی شده را نشان می دهد. در شبکه جاده های تولید شده ما، هیچ لبه کاذب وجود ندارد، اگرچه گاهی اوقات، تقاطع ها به اشتباه متصل می شوند. چنین خطاهایی بر روی

F_{r}

عدد. با آستانه تطبیق 5 و 10 متری، تنها چند تقاطع در شبکه جاده تولید شده و نقشه حقیقت زمینی مطابقت داده شده است. با این حال، این تقاطع ها به یکدیگر متصل نیستند، بنابراین هیچ نتیجه کمی در این دو آستانه در شکل 12 ب نشان داده نشده است.

شکل 11. تجزیه و تحلیل آماری. سرعت و تغییرات سرعت در امتداد بخش جاده از تقاطع

q_{3}

به

q_{1}

به تصویر کشیده می شوند.

شکل 12. ارزیابی دقت توپولوژیکی. ( الف ) دقت تقاطع های ایجاد شده را نشان می دهد. ( ب ) دقت اتصال بین تقاطع ها را نشان می دهد. با فواصل تطبیق متفاوت بین تقاطع های ایجاد شده و حقیقت زمینی آنها. هرچه امتیاز F بزرگتر باشد، دقیق تر است.

با 50 متر به عنوان آستانه تطبیق برای تقاطع ها، 77 جاده هدایت شده در مقاله ما شناسایی شده است. میانگین فاصله بین تمام جاده های تولید شده و حقیقت زمینی آنها برای توصیف دقت جغرافیایی شبکه جاده تولید شده استفاده می شود که به صورت محاسبه می شود.

7.35

متر

5.1.4. بحث در مورد اینکه ترتیب همسویی چگونه بر نتایج تأثیر می گذارد

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

نتایج نشان داده شده در شکل 10 با استفاده از ترتیبی بر اساس امتیاز شباهت آنها به مسیرهای دیگر که به عنوان مجموع امتیاز شباهت آنها به هر آهنگ دیگر محاسبه می شود، از مسیرها استخراج می شود. برای ارزیابی کمی تأثیر، ما همچنین آهنگ ها را با تراز کردن آنها در 50 ترتیب تصادفی دیگر، میانگین گرفتیم. میانگین فاصله بین قطعه جاده تولید شده و حقیقت زمین آن با 50 مرتبه مختلف محاسبه شده و در شکل 13 نشان داده شده است . محور افقی و عمودی به ترتیب شاخص ترتیب تراز و فاصله را نشان می دهد. مهم نیست که کدام ترتیب برای تراز کردن مسیرها انتخاب شده است، فاصله از بخش جاده تولید شده تا حقیقت زمین همیشه در اطراف است.

7.38

m با حداکثر مقدار

7.85

متر و حداقل مقدار

6.81

m، که به این معنی است که ترتیب تراز تأثیر قابل توجهی در میانگین گیری مسیرها ندارد.

شکل 13. تأثیر ترتیب تراز. مهم نیست که مسیرها به چه ترتیبی در یک راستا قرار دارند، میانگین فاصله بین تمام جاده های تولید شده و حقیقت زمینی آنها در اطراف است.

7.37

m پایدار است، به این معنی که ترتیب تراز به طور قابل توجهی بر تراز مسیر تأثیر نمی گذارد.

5.2. مقایسه با سایر روش ها

نتایج ما با روش‌های موجود به شرح زیر مقایسه می‌شوند: روش برازش منحنی پیشنهاد شده توسط Schroedl [ 2 ]، روش مبتنی بر KDE توسط Davies [ 3 ] و همچنین روش ادغام ردیابی پیشنهاد شده توسط Cao [ 4 ]. از آنجایی که ارزیابی‌های کمی و کیفی این سه الگوریتم موجود در Biagioni و Eriksson در [ 16 ] با استفاده از همان مجموعه داده‌های شاتل پردیس شیکاگو مانند ما انجام شده است ، می‌توانیم نتایج الگوریتم‌های آنها را مستقیماً با الگوریتم خود مقایسه کنیم.

شکل 14 نتایج همان دو مثالی را نشان می دهد که بیاجیونی در مقاله خود استفاده کرده است [ 16 ]، یک مثال با ردیابی GPS با خطای بالا، در حالی که دیگری با ردیابی GPS با خطای پایین. هم Schroedl و هم Cao با استفاده از ردیابی GPS با خطای بالا در شکل 14 a لبه های جاده های جعلی تولید کردند، در حالی که الگوریتم ما، بر اساس تشخیص تقاطع، توپولوژی جاده را با موفقیت بدون افزودن لبه های اضافی استخراج کرد. اگرچه دیویس جاده‌های تمیزی را نیز تولید کرد، روش ما همچنان بهتر از روش اوست، زیرا جاده‌های تولید شده ما هدایت‌شده هستند، در حالی که او فقط جاده‌های هدایت نشده را استخراج می‌کرد.

شکل 14 الف بخشی از مسیرها را نشان می دهد که برای تولید جاده های هدایت شده در شکل 14 ب به طور متوسط محاسبه شده اند. شکل 14 ج بخش دیگری از مسیرها را نشان می دهد که برای تولید جاده های هدایت شده در شکل 14 د.

شکل 14. مقایسه با روش های دیگر. ( الف ) برخی از ردیابی های GPS با خطای بالا را نشان می دهد که برای استخراج جاده های هدایت شده در ( b ) استفاده می شود. ردیابی در ( c ) خطای نسبتاً کمی دارد و در نتیجه جاده‌های جهت‌دار در ( d ) می‌شوند.

علاوه بر این، 83 درصد از جاده‌ها در فاصله 10 متری از حقیقت زمین شناسایی می‌شوند که از همه روش‌های ذکر شده در بالا که امتیاز F کمتر از آن است، بهتر عمل می‌کند.

0.7

با آستانه تطبیق 15 متری، همانطور که در شکل 6 در [ 16 ] نشان داده شده است.

6. نتیجه گیری و کار آینده

ما یک رویکرد جدید برای استنباط یک شبکه جاده‌ای با استخراج تقاطع‌ها، استنباط توپولوژی آنها و بخش‌بندی بخش‌های جاده بین تقاطع‌ها با استفاده از ردیابی GPS ارائه کرده‌ایم. ما همچنین با استفاده از استراتژی «کشش و سپس فشرده‌سازی»، نمایش‌های هندسی هر بخش جاده را با تراز کردن و میانگین‌گیری مسیرها برای هر بخش جاده تشکیل می‌دهیم. مسیرها، نقطه به نقطه، از طریق عملیات “کشش” ما در بعد زمانی با استفاده از DTW تراز می شوند، و نقاط اضافی با استفاده از عملیات “فشرده سازی” ما حذف می شوند، که منجر به مطابقت یک به یک بین نقاط در تمام نقاط می شود. آهنگ های. تراز مسیر همچنین برای تجزیه و تحلیل آماری بیشتر مسیرها، مانند تجزیه و تحلیل سرعت و دینامیک زمان سفر در مکان های خاص، مفید است.

اگرچه الگوریتم ما از سایر روش‌های موجود بهتر عمل می‌کند، استراتژی «فشرده‌سازی» ما نقاط داده کمتری را به‌عنوان نمایش جاده تولید می‌کند، اگر در هر مسیری از دست دادن داده‌های GPS کوچک وجود داشته باشد یا فرکانس نمونه‌گیری برخی از مسیرها کمتر از سایرین باشد. این امر به این دلیل است که مسیرهایی با از دست دادن داده های GPS زیاد یا با فرکانس نمونه برداری فوق العاده کم به عنوان نقاط پرت دسته بندی می شوند و با سایر مسیرها تراز نمی شوند. بنابراین، در آینده، ما بر تراز کردن مسیرها بدون استراتژی “فشرده سازی” و بنابراین، حفظ تناظر چند به یک در بین نقاط در همه مسیرها تمرکز خواهیم کرد. علاوه بر این، به جای منطق دو ارزشی در روش فعلی، روی استنباط آماری وجود و پوشش تقاطع ها و بخش های جاده با استفاده از روش احتمالی کار خواهیم کرد.

منابع

بیاجیونی، جی. اریکسون، جی. استنتاج نقشه در مواجهه با نویز و نابرابری. در مجموعه مقالات بیستمین کنفرانس بین المللی پیشرفت در سیستم های اطلاعات جغرافیایی، ردوندو بیچ، کالیفرنیا، ایالات متحده آمریکا، 7-9 نوامبر 2012. ACM: نیویورک، نیویورک، ایالات متحده آمریکا، 2012; صص 79-88. [ Google Scholar ]
شرودل، اس. واگستاف، ک. راجرز، اس. لنگلی، پی. Wilson, C. استخراج ردیابی GPS برای اصلاح نقشه. حداقل داده بدانید. کشف کنید. 2004 ، 9 ، 59-87. [ Google Scholar ] [ CrossRef ]
داویکس، جی. برسفورد، آر. Hopper، A. مقیاس پذیر، توزیع شده، تولید نقشه بلادرنگ. محاسبات فراگیر IEEE 2006 ، 5 ، 47-54. [ Google Scholar ]
کائو، ال. Krumm, J. از ردیابی GPS تا نقشه راه قابل مسیریابی. در مجموعه مقالات هفدهمین کنفرانس بین المللی ACM SIGSPATIAL در مورد پیشرفت در سیستم های اطلاعات جغرافیایی، سیاتل، WA، ایالات متحده آمریکا، 4-6 نوامبر 2009.
شی، دبلیو. شن، اس. Liu, Y. تولید خودکار نقشه شبکه جاده از GPS عظیم، مسیرهای خودرو. در مجموعه مقالات دوازدهمین کنفرانس بین المللی IEEE در مورد سیستم های حمل و نقل هوشمند، سنت لوئیس، MO، ایالات متحده آمریکا، 4 تا 7 اکتبر 2009.
ساتو، جی. تاکاهاشی، تی. ایده، من. Murase، H. تشخیص تغییر در مناظر خیابانی از توالی های تصویر همه جهته هماهنگ شده با GPS. در مجموعه مقالات هجدهمین کنفرانس بین المللی IEEE در مورد شناسایی الگوها، هنگ کنگ، چین، 20-24 اوت 2006.
ولاهوگیانی، EI; Karlaftis، MG; Golias، JC شبکه های عصبی بهینه شده و فرا بهینه شده برای پیش بینی جریان ترافیک کوتاه مدت: یک رویکرد ژنتیکی. ترانسپ Res. قسمت C Emerg. تکنولوژی 2005 ، 13 ، 211-234. [ Google Scholar ] [ CrossRef ]
Syberfeldt، A. Persson، L. استفاده از جستجوی اکتشافی برای شروع جمعیت ژنتیکی در بهینه سازی مبتنی بر شبیه سازی مسائل مسیریابی خودرو. در مجموعه مقالات کنفرانس شبیه سازی صنعتی، EUROSIS-ETI، Loughborough، انگلستان، 1-3 ژوئن 2009.
Schultes، D. برنامه ریزی مسیر در شبکه های جاده ای. Ph.D. پایان نامه، موسسه فناوری کارلسروهه، کارلسروهه، آلمان، 2008. [ Google Scholar ]
نیهوفر، بی. بردا، ر. ویتفلد، سی. بائر، اف. Lueert، O. تولید نقشه جامعه GPS برای روش های مسیریابی پیشرفته بر اساس جمع آوری ردیابی توسط تلفن های همراه. در مجموعه مقالات اولین کنفرانس بین المللی IEEE در زمینه پیشرفت در ارتباطات ماهواره ای و فضایی، کولمار، فرانسه، 20-25 ژوئیه 2009.
کوکو، ا. آندری، CO; Salminen، VM; کارتینن، اچ. چن، ی. رونهولم، پی. Hyyppä، H.; Hyyppä، J.; چن، آر. هاگرن، اچ. و همکاران سیستم نقشه برداری محیط جاده موسسه ژئودتیک فنلاند âĂŤFGI Roamer. بین المللی قوس. فتوگرام حسگر از راه دور اسپات. Inf. علمی 2007 ، 36 ، 241-247. [ Google Scholar ]
بلنز، آر. Vlassenroot، S. گوتاما، اس. جمع آوری و تجزیه و تحلیل داده های رفتار سفر جمعیت با استفاده از گوشی های هوشمند. در مجموعه مقالات پنجمین روز تحقیقات حمل و نقل BIVEC-GIBET، نامور، بلژیک، 25 مه 2011.
لی، دی. هان، ام. سیستم نقشه ایمنی دوچرخه بر اساس شبکه حسگر به کمک گوشی هوشمند. Adv. علمی تکنولوژی Lett. 2013 ، 42 ، 38-43. [ Google Scholar ]
هاکلی، م. Weber, P. Openstreetmap: نقشه های خیابانی تولید شده توسط کاربر. محاسبات فراگیر IEEE 2008 ، 7 ، 12-18. [ Google Scholar ] [ CrossRef ]
Haklay, M. اطلاعات جغرافیایی داوطلبانه چقدر خوب است؟ مطالعه تطبیقی مجموعه داده‌های OpenStreetMap و Ordnance Survey. محیط زیست طرح. B طرح. دس 2010 ، 37 ، 682-703. [ Google Scholar ] [ CrossRef ]
بیاجیونی، جی. اریکسون، جی. استنباط نقشه های راه از ردیابی سیستم موقعیت یابی جهانی. ترانسپ Res. ضبط J. Transp. Res. هیئت 2012 ، 2291 ، 61-71. [ Google Scholar ] [ CrossRef ]
ژنگ، ی. لی، کیو. چن، ی. Xie، X. Ma, WY درک تحرک بر اساس داده های GPS. در مجموعه مقالات دهمین کنفرانس بین المللی محاسبات همه جا حاضر، سئول، کره، 21 تا 24 سپتامبر 2008.
ادلکمپ، اس. Schrödl, S. برنامه ریزی مسیر و استنتاج نقشه با ردیابی موقعیت یابی جهانی. در علوم کامپیوتر از دیدگاه ; Springer: برلین، آلمان؛ هایدلبرگ، آلمان، 2003; صص 128-151. [ Google Scholar ]
شما، س. کروم، جی. توموگرافی ترانزیت با استفاده از جغرافیای زمان احتمالی: برنامه ریزی مسیرها بدون نقشه راه. J. Locat. سرویس مبتنی بر 2014 ، 8 ، 211-228. [ Google Scholar ] [ CrossRef ]
Xie، X. فیلیپس، دبلیو. ویلارت، پی. آقاجان، ح. استنتاج شبکه راه از ردیابی GPS با استفاده از الگوریتم DTW. در مجموعه مقالات هفدهمین کنفرانس بین المللی IEEE در مورد سیستم های حمل و نقل هوشمند (ITSC)، چینگدائو، چین، 8 تا 11 اکتبر 2014. ص 906-911.
لیو، بی. داده کاوی وب . Springer: برلین، آلمان؛ هایدلبرگ، آلمان، 2007. [ Google Scholar ]
چن، سی. Cheng، Y. تولید نقشه دیجیتال جاده ها با داده های GPS چند مسیری. در مجموعه مقالات کارگاه بین المللی IEEE در مورد فناوری آموزشی و آموزش، 2008. و کارگاه بین المللی 2008 در زمینه علوم زمین و سنجش از دور، شانگهای، چین، 21-22 دسامبر 2008.
موریس، اس. موریس، ا. Barnard, K. کتابخانه های دیجیتالی دنباله دار. در مجموعه مقالات چهارمین کنفرانس مشترک ACM/IEEE-CS در کتابخانه های دیجیتال، توسان، AZ، ایالات متحده آمریکا، 7 تا 11 ژوئن 2004. ACM: نیویورک، نیویورک، ایالات متحده آمریکا، 2004. [ Google Scholar ]
کاراگیورگو، اس. Pfoser، D. در مورد ردیابی وسایل نقلیه مبتنی بر داده تولید شبکه جاده ای. در مجموعه مقالات بیستمین کنفرانس بین المللی پیشرفت در سیستم های اطلاعات جغرافیایی، ردوندو بیچ، کالیفرنیا، ایالات متحده آمریکا، 7 تا 9 نوامبر 2012.
Berndt، دی جی; کلیفورد، جی. استفاده از تاب خوردگی زمانی پویا برای یافتن الگوها در سری های زمانی . KDD: سیاتل، WA، ایالات متحده آمریکا، 1994. [ Google Scholar ]
Greenfeld، JS تطبیق مشاهدات GPS با مکان‌های روی نقشه دیجیتال. در مجموعه مقالات هشتاد و یکمین نشست سالانه هیئت تحقیقات حمل و نقل، واشنگتن دی سی، ایالات متحده آمریکا، 13 تا 17 ژانویه 2002.
Calcagno، P. Chilès، JP; کوریو، جی. گیلن، الف. مدل‌سازی زمین‌شناسی از داده‌های میدانی و دانش زمین‌شناسی: بخش اول. روش مدل‌سازی جفت‌یابی درونیابی میدان پتانسیل سه بعدی و قوانین زمین‌شناسی. فیزیک سیاره زمین. اینتر 2008 ، 171 ، 147-157. [ Google Scholar ] [ CrossRef ]
آزمایشگاه سیستم های شبکه ای BITS. در دسترس آنلاین: http://bits.cs.uic.edu/ (در 24 اوت 2015 قابل دسترسی است).
نقشه خیابان باز در دسترس آنلاین: http://www.openstreetmap.org/ (در 24 آگوست 2015 قابل دسترسی است).

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

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

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

09120049370

8 صبح تا 12 شب

09120049370

خلاصه

1. معرفی

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

3. استنباط شبکه راه

3.1. تشخیص نقطه عطف

3.2. استخراج تقاطع

3.3. تجزیه و تحلیل اتصال و تقسیم بندی ردیابی GPS

3.4. تراز مسیر

3.4.1. تراز دو مسیر با استفاده از DTW

3.4.2. استراتژی “کشش و سپس فشرده سازی”.

3.4.3. تراز چند آهنگ

3.5. تحلیل آماری

4. ارزیابی عملکرد الگوریتم

4.1. محاسبه دقت توپولوژیکی

4.2. ارزیابی دقت جغرافیایی

5. آزمایشات

5.1. نتایج با استفاده از روش ما

5.1.1. نقاط عطف و تقاطع استنباط شده

5.1.2. جاده های استنباط شده

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

5.1.4. بحث در مورد اینکه ترتیب همسویی چگونه بر نتایج تأثیر می گذارد

5.2. مقایسه با سایر روش ها

6. نتیجه گیری و کار آینده

منابع

قبلیبه سوی پروتکل کتابخانه طیفی گونه های گیاهی استاندارد برای نقشه برداری گیاهی: مطالعه موردی در بوته زار پارک ملی دونا

بعدیروش انتخاب مسیر بهینه بر اساس پیچ های تقاطع های جاده ای: مطالعه موردی در حمل و نقل محموله های بزرگ

بدون نظر

دیدگاهتان را بنویسید لغو پاسخ