Duan Jianmin, Wang Changren, Ren Lu, Liu Dan
(Departemen Ilmu Informasi, Universitas Teknologi Beijing, Beijing 100124)
Untuk mengekstrak informasi area drivable di depan mobil nirawak, diusulkan algoritma untuk mengekstraksi informasi area drivable berbasis multilayer lidar. Pertama, roadside point set diperoleh sesuai dengan karakteristik data pengembalian radar yang digabungkan dengan data distribusi kepadatan interval, dan roadside point yang diperoleh dikelompokkan dengan algoritma OPTICS berdasarkan bobot KNN jarak Euclidean. Kemudian, gunakan metode kuadrat terkecil agar sesuai dengan trotoar di kedua sisi. Akhirnya, titik awan rintangan di jalan dikelompokkan oleh algoritma OPTICS yang ditingkatkan, dan posisi, jarak, ukuran dan informasi lain dari rintangan diperoleh dengan perhitungan. Menggunakan metode distribusi kepadatan interval data untuk mengekstrak titik pinggir jalan tidak terpengaruh oleh halangan dan titik perkerasan, sedangkan algoritma OPTICS yang ditingkatkan tidak lagi tunduk pada kendala Eps, dan dapat secara akurat membedakan titik kebisingan, yang memecahkan masalah informasi hambatan yang diekstraksi karena kebisingan. Pertanyaan tepatnya. Eksperimen kendaraan nyata telah membuktikan keefektifan dan kinerja algoritma secara real-time.
Kendaraan tak berawak; lidar multilayer; area yang dapat dilalui; distribusi kepadatan data; algoritma OPTICS
Nomor Klasifikasi Perpustakaan Cina: TN958.98
Kode identifikasi dokumen: SEBUAH
DOI: 10.16157 / j.issn.0258-7998.170392
Format kutipan berbahasa Mandarin: Duan Jianmin, Wang Changren, Ren Lu, dkk. Algoritma ekstraksi informasi area mengemudi berdasarkan multilayer lidar. Electronic Technology Application, 2017, 43 (10): 78-82.
Format kutipan bahasa Inggris: Duan Jianmin, Wang Changren, Ren Lu, dkk. Algoritma ekstraksi informasi area mengemudi berbasis multi-layer lidar. Application of Electronic Technique, 2017, 43 (10): 78-82.
0 Kata Pengantar
Dengan perkembangan masyarakat yang berkelanjutan, semakin banyak sarjana di seluruh dunia mulai melakukan penelitian tentang mengemudi tanpa awak, di antaranya teknologi radar telah menarik lebih banyak perhatian. Literatur menggunakan karakteristik yang konsisten dari data titik lereng untuk mengekstrak titik pinggir jalan, tetapi algoritme mudah dipengaruhi oleh titik jalan dan titik hambatan dan perlu diproses secara hierarki, sehingga akurasi dan kinerja waktu nyata tidak dapat memenuhi persyaratan. Literatur menggunakan lompatan data ketinggian balik lidar untuk mengekstrak titik pinggir jalan, yang sangat tidak stabil karena hambatan. Adapun algoritma pengelompokan, karena data lidar terutama muncul dalam kluster, metode pengelompokan berbasis kepadatan cocok untuk data lidar, dan algoritma OPTICS adalah metode pengelompokan berbasis kepadatan yang khas. Literatur menggunakan strategi reorganisasi urutan hasil untuk meningkatkan algoritma OPTICS, tetapi dalam aplikasi praktis, tidak mungkin untuk membedakan suara tiba-tiba dari titik data lidar, sehingga hasil ekstraksi hambatan tidak akurat.
Makalah ini pertama-tama menggunakan distribusi kepadatan interval data untuk mengekstrak titik-titik pinggir jalan dan menggunakan metode kuadrat terkecil agar sesuai dengan pinggir jalan untuk membedakan area yang dapat dilalui, dan kemudian menggunakan algoritma OPTICS yang ditingkatkan untuk mengelompokkan data yang dikembalikan secara real time di area yang dapat dilalui. Terakhir, validitas dan performa real-time dari algoritme yang diusulkan diverifikasi oleh eksperimen kendaraan nyata.
1 Preprocessing data Lidar
1.1 Analisis data Lidar
Artikel ini menggunakan lidar empat baris IBEO LUX 2010 yang diproduksi oleh perusahaan IBEO Jerman. Dibandingkan dengan lidar baris tunggal, radar jenis ini memiliki keunggulan volume data yang besar, akurasi deteksi yang tinggi, dan jarak deteksi yang jauh. Parameter utamanya ditunjukkan pada Tabel 1.
Informasi yang dikembalikan oleh radar empat baris terutama mencakup informasi nomor seri, nomor lapisan pindai, jarak, dan koordinat posisi. Analisis karakteristiknya adalah sebagai berikut:
(1) Scan Lidar dari kiri ke kanan, dan jumlah data yang dikembalikan di setiap frame pada dasarnya sama;
(2) Data yang dikembalikan oleh lidar berubah sesuai dengan perubahan pemandangan di depan, dan jumlah serta bentuk titik pemindaian untuk setiap hambatan berbeda;
(3) Ketika lidar memindai ke tepi jalan, data yang dikembalikan ditandai dengan koordinat sumbu x yang jarang dan koordinat sumbu y yang tersusun rapat.
1.2 Pemrosesan awal data
Untuk mendeteksi area drivable dan informasi halangan di depan kendaraan, lidar ditempatkan di tengah-tengah bagian depan kendaraan Berdasarkan pengalaman sebelumnya, ketinggian pemasangan radar diatur ke 0.846 m. Diagram posisi pemasangan ditunjukkan pada Gambar 1.
2 Metode pengolahan data Lidar
2.1 Distribusi kepadatan interval data satu dimensi
Asumsi (x1, y1), (x2, y2), (x3, y3), ..., (xn, yn), n R adalah data titik-titik pinggir jalan pengembalian radar, menurut karakteristiknya, salah satu data dimensional D = { y1, y2, y3, ..., yn}, n R pada dasarnya sama. Distribusi kepadatan probabilitas dari interval data adalah kepadatan data yang dikembalikan oleh radar yang jatuh dalam interval tertentu. Rumusnya adalah:
Dalam rumus, dan adalah dua titik akhir dari interval tertentu, num (yi) adalah jumlah data yang jatuh dalam interval tertentu, dan penyebut adalah jumlah dari jumlah data; P adalah jumlah total data dalam interval tertentu Kemungkinan. Jika keseluruhan data dibagi menjadi j interval, jumlah probabilitasnya adalah 1.
2.2 Algoritma OPTICS
Algoritma OPTICS (Order Point to Identify the Cluster Structure) adalah algoritma pengelompokan berbasis kepadatan. Algoritme ini merupakan perpanjangan dari algoritme DBSCAN. Algoritme ini menyortir data dalam kumpulan objek data dan mengeluarkan daftar objek yang diurutkan (pengurutan kluster). Daftar ini berisi semua informasi yang digunakan untuk mengekstrak kluster, yaitu objek data klasifikasi. Berikut adalah dua definisi yang diperkenalkan dalam algoritma OPTICS:
Definisi 1 jarak inti (jarak inti)
Dengan asumsi bahwa radius minimum titik P berisi m tetangga adalah jarak min (P), maka jarak inti titik P dapat didefinisikan sebagai:
Definisi 2 jarak jangkauan (RD)
Dengan asumsi bahwa P adalah salah satu titik tetangga dari titik o, definisi jarak yang dapat dicapai antara P dan o adalah:
Langkah-langkah implementasi metode pengelompokan OPTICS tradisional ditunjukkan pada Gambar 2. Keuntungan dari algoritma OPTICS adalah tidak sensitif terhadap parameter input, tetapi ketika input Eps dan Eps yang sebenarnya besar, efek pengelompokan masih terpengaruh, dan algoritme tidak dapat menangani noise. membedakan.
2.3 Grafik KNN berdasarkan jarak Euclidean tertimbang
Setelah menghitung distribusi kerapatan data dari data radar dalam data radar aktual, ekstrak kumpulan titik dari setiap area puncak, hitung nilai varians dari koordinat horizontal dan vertikal, dan kemudian hitung jarak Euclidean tertimbang antar titik data.
KNN akan menghitung matriks jarak Distk * k dari titik-titik data yang dipindai oleh radar aktual sesuai dengan jarak Euclidean tertimbang, dan kemudian menyusun setiap dimensi dalam Distk * k dalam urutan menaik untuk membentuk urutan (Distk * k), dan terakhir mengurutkan (Distk * k) Setiap data dimensi dalam) digambar ke dalam grafik KNN.
2.4 Pemasangan Kotak Terkecil
Dalam makalah ini, menurut karakteristik jalan percobaan, karena sebagian besar titik kerb di kedua sisi jalan percobaan terdistribusi secara linier, metode kuadrat terkecil digunakan untuk menyesuaikan secara linier titik-titik kerb yang diambil di kedua sisi jalan. Metode kuadrat terkecil adalah metode pengoptimalan matematis yang menemukan kecocokan fungsi terbaik dari data dengan meminimalkan jumlah kuadrat kesalahan. Ekspresi yang umum digunakan untuk pemasangan linier adalah y = kx + h, berikut adalah rumus solusi untuk parameter k dan h:
Dalam rumusnya, n melambangkan jumlah titik yang akan dipasang, (xi, yi) adalah nilai koordinat titik yang akan dipasang, k adalah kemiringan, dan h adalah perpotongan.
3 Metode ekstraksi informasi area yang dapat dilalui
3.1 Algoritma OPTICS yang ditingkatkan berdasarkan jarak Euclidean tertimbang
Meskipun algoritme OPTICS tradisional dapat mengatasi beberapa masalah algoritme pengelompokan tradisional lainnya, algoritme ini masih memiliki beberapa kekurangan.Misalnya, dalam proses aktual penyaringan poin inti, OPTICS menentukan lokasi poin inti dengan memilih Eps yang sesuai. Namun, pemilihan Eps yang tidak tepat menimbulkan noise, yang sangat mengurangi sensitivitas algoritme terhadap noise dan membuat pengelompokan menjadi tidak akurat. Selain itu, jika rentang Eps dipilih secara membabi buta, efek pengelompokan juga akan terpengaruh.
Untuk memperbaiki kekurangan dari OPTICS, makalah ini mengusulkan perbaikan algoritma OPTICS berdasarkan weighted Euclidean distance KNN. Algoritma ini tidak memerlukan parameter input Eps, tetapi membentuk grafik tetangga terdekat k ( KNN) untuk menentukan hasil clustering dan membedakan noise point. Langkah-langkah spesifiknya ditunjukkan pada Gambar 3.
Menurut Gambar 3, algoritma OPTICS yang ditingkatkan dapat langsung melakukan clustering tanpa memilih Eps. Langkah-langkah khusus pemisahan kebisingan berdasarkan KNN jarak Euclidean tertimbang pada diagram alir adalah sebagai berikut:
(1) Hitung jarak Euclidean tertimbang antara setiap titik di setiap jenis titik data untuk membentuk matriks jarak Distk * k;
(2) Urutkan jarak setiap dimensi dalam matriks jarak dalam urutan menaik ke bentuk sortir (Distk * k);
(3) Karena jarak antara titik gangguan dan titik lainnya lebih besar dari ambang batas, maka perlu ditentukan apakah jarak minimum antara titik ini dan titik lain lebih besar dari ambang batas, jika lebih besar, titik tersebut merupakan gangguan.
3.2 Algoritma ekstraksi tepi jalan berdasarkan distribusi kepadatan interval data satu dimensi
Melalui analisis data point cloud yang dikembalikan oleh lidar, dapat diketahui bahwa point cloud meliputi titik jalan, titik pinggir jalan di kedua sisi, bunga dan tumbuhan disekitarnya, dan titik hambatan. Tetapkan k interval jarak yang sama, dalam interval ini gunakan persamaan (2) untuk mencari kepadatan titik data radar di setiap interval. Mengambil sumbu horizontal nol sebagai titik demarkasi, interval di mana kepadatan maksimum dan kepadatan maksimum kedua di kedua sisi berada diekstraksi. Dari pengalaman, perbedaan ketinggian antara titik perkerasan dan titik tepi jalan sekitar 20 cm, dan titik perkerasan dapat dihilangkan berdasarkan perbedaan ketinggian tersebut. Setelah mendapatkan titik tepi jalan, gunakan algoritme OPTICS yang ditingkatkan untuk mengelompokkan titik tepi jalan, dan terakhir gunakan metode kuadrat terkecil agar sesuai dengan tepi jalan, dan hitung informasi tepi jalan.
3.3 Ekstraksi informasi hambatan di area yang dapat dilalui
Melalui informasi tepi jalan yang diperoleh maka lebar jalan dapat ditentukan. Jika diasumsikan bahwa kisaran titik pinggir jalan kiri dan kanan dijumlahkan secara berurutan, maka kisaran area yang dapat dilalui dapat diperoleh sesuai dengan delimitasi horizontal dan rumus (8):
Dalam rumusnya, Croad adalah area mengemudi, dan Cnoise adalah lingkungan sekitarnya.
Menurut kombinasi informasi lebar kendaraan tak berawak dan informasi lebar area yang dapat diekstraksi, ungkapannya adalah:
Setelah mengekstraksi area yang bisa dilalui, poin yang tersisa adalah rintangan dan kebisingan. Titik-titik hambatan terutama meliputi: pejalan kaki, kendaraan bermotor, sepeda, dll. Informasi atribut utama dari halangan dinyatakan sebagai jarak, sudut, titik pusat, dll. Algoritma OPTICS yang ditingkatkan digunakan untuk mengelompokkan rintangan di area yang dapat dilalui, dan jarak, sudut setiap jenis rintangan dan koordinat x, y, z dari titik pusat rintangan diekstraksi. Dapatkan panjang, lebar, jarak, sudut dan kecepatan rintangan melalui perhitungan di dalam kelas.
4 Hasil uji kendaraan nyata
4.1 Kondisi dan platform percobaan
Platform eksperimental dalam makalah ini adalah kendaraan tanpa awak yang dikembangkan secara independen oleh BJUT-IV (Kendaraan Cerdas Teknologi Universitas Beijing). Lidar empat baris IBEO-LUX dipasang di tengah ujung depan kendaraan untuk mengumpulkan data eksperimen. Ketinggian pemasangan radar adalah 0,846 m. Adegan percobaan adalah jalan di kampus, seperti yang ditunjukkan pada Gambar 4.
4.2 Hasil percobaan ekstraksi pinggir jalan di area yang dapat dilalui kendaraan
Gambar 5 menunjukkan hasil percobaan ekstraksi tepi jalan di daerah yang dapat dilalui.
Gambar 4 bagian kiri adalah adegan percobaan 1, dan kondisi jalan tidak ada kendaraan yang melintas. Gambar 5 (b) menunjukkan titik data asli, titik data asli meliputi titik pinggir jalan, titik jalan, pepohonan disekitarnya, dan jaring besi. Titik data radar pada gambar dibagi menjadi 4 lapisan, yang diwakili oleh titik yang ditunjukkan oleh panah pada gambar. Gambar 5 (a) adalah histogram dari distribusi kepadatan data dari nilai y dari data yang dikembalikan radar, di mana nol adalah titik demarkasi, dua interval yang mendekati nol dalam 4 rentang adalah interval titik tepi jalan, dan dua lainnya adalah batas lapangan . Berdasarkan histogram kepadatan, kita dapat dengan jelas menganalisis kisaran titik tepi jalan di sebelah kiri dan kisaran titik tepi jalan di sebelah kanan. Dengan memilih kepadatan interval, situasi yang ditunjukkan pada Gambar 5 (c) diperoleh. Dua kolom titik pada gambar merupakan hasil ekstraksi kepadatan interval berdasarkan data satu dimensi. Gambar 5 (d) adalah pengelompokan titik-titik pinggir jalan yang diekstraksi melalui algoritma OPTICS yang ditingkatkan oleh KNN berdasarkan bobot jarak Euclidean Kotak elips pada gambar tersebut untuk secara jelas menunjukkan hasil pengelompokan dari kedua jenis tersebut. Akhirnya, titik-titik tepi jalan yang diekstraksi pada kedua sisi dipasang secara linier dengan metode kuadrat terkecil, dan hasilnya ditunjukkan pada Gambar 5 (e). Hasil ekstraksi kerb menunjukkan lebar jalan 10,48 m, jarak sisi kiri kendaraan dengan kerb 6,64 m, dan jarak sisi kanan kendaraan dengan kerb 3,83 m. Pada adegan percobaan aktual, lebar jalan aktual diperoleh dengan pengukuran sekitar 10,5 m, dan perbedaan antara hasil ekstraksi dan lebar sebenarnya hanya 0,02 m, dan tingkat deteksi informasi lebar jalan 99,8%, yang memenuhi kebutuhan aplikasi praktis.
4.3 Hasil percobaan ekstraksi rintangan di area yang dapat dilalui
Hasil ekstraksi hambatan pada area yang dapat dilalui ditunjukkan pada Gambar 6, dan sisi kanan Gambar 4 adalah adegan percobaan 2, di mana terdapat pejalan kaki dan mobil. Gambar 6 (a) adalah diagram KNN jarak Euclidean tertimbang dari frame 47. Bagian yang jarang dari gambar tersebut adalah noise yang disebutkan dalam teks, dan bagian lainnya adalah efek clustering. Gambar 6 (b) menunjukkan situasi di mana rintangan di jalan terdeteksi menggunakan algoritma OPTICS tradisional pada kerangka kendaraan ke-47 selama mengemudi. Dapat dilihat dari gambar bahwa, karena noise pada data lapisan ketiga selama proses pemindaian radar, efek clustering terpengaruh dan akurasi clustering berkurang. Gambar 6 (c) menunjukkan pengaruh penggunaan KNN berdasarkan weighted Euclidean distance untuk memperbaiki algoritma OPTICS untuk frame data ke 47. Algoritma tersebut dapat menghindari pengaruh kebisingan jalan, dan dapat secara akurat mengelompokkan hambatan, dan hambatan tersebut dapat diperoleh melalui perhitungan Atribut utama pejalan kaki yang terdeteksi panjang = 0,1 m, lebar = 0,3 m, panjang kendaraan yang terdeteksi adalah panjang = 3,3 m, lebar = 1,7 m, termasuk jarak radar dengan halangan di depan, hasil deteksi Ini pada dasarnya konsisten dengan ukuran pengukuran sebenarnya dan memenuhi persyaratan pengujian.
Gambar 6 (d) menunjukkan hasil deteksi algoritma OPTICS tradisional pada frame 45. Pada gambar tersebut, kebisingan jalan dianggap sebagai kendala, yang mempengaruhi akurasi clustering. Gambar 6 (e) menunjukkan kerangka data ke-45 menggunakan algoritma OPTICS yang ditingkatkan dengan hasil yang baik. Melalui hasil eksperimen di atas, dapat dibuktikan bahwa efektivitas dan kinerja real-time dari algoritma ekstraksi area mengemudi yang diusulkan dalam makalah ini telah meningkat.
5. Kesimpulan
Algoritma ekstraksi informasi area yang dapat dilalui yang diusulkan dalam makalah ini mencakup ekstraksi tepi jalan area yang dapat dilalui dan ekstraksi hambatan.Dalam ekstraksi tepi jalan, distribusi kepadatan interval data satu dimensi digunakan untuk menentukan data radar, dan titik-titik tepi jalan diekstraksi melalui kisaran yang ditentukan. Metode ini mengekstrak titik-titik tepi jalan berdasarkan kepadatan data untuk menghilangkan pengaruh hambatan jalan pada ekstraksi titik tepi jalan, dan memproses banyak lapisan data pada saat yang bersamaan, sehingga mengurangi kerumitan. Algoritma KNN yang ditingkatkan OPTICS berdasarkan jarak Euclidean tertimbang digunakan untuk mengelompokkan awan titik hambatan di jalan, dan posisi, jarak, ukuran dan informasi lain dari hambatan diperoleh melalui perhitungan. Algoritme OPTICS yang ditingkatkan tidak lagi dibatasi oleh Eps, dan dapat secara akurat membedakan titik-titik noise, meningkatkan akurasi ekstraksi hambatan. Algoritme yang diusulkan dapat secara efektif memahami informasi area yang dapat dilalui di depan kendaraan tanpa pengemudi, memberikan informasi yang efektif untuk lapisan pengambilan keputusan tanpa pengemudi, dan juga meningkatkan keselamatan kendaraan tanpa pengemudi.
referensi
DAHLKAMP H, KAEHLER A, BRADSKI G. Deteksi jalan monokuler yang diawasi sendiri di medan gurun. Prosiding Robotika: Sains dan Sistem. Philadelphia: MIT Press, 2006: 115-121.
Wang Xin, Li Gao, Zhu Wanli, dll. Penelitian Pemodelan dan Optimasi Manajemen Energi Kendaraan Listrik Hibrid Paralel, Teknik Kontrol, 2014 (3): 357-360.
Yang Xiangjun. Deteksi dan pelacakan jalan berdasarkan lidar empat baris. Hangzhou: Universitas Zhejiang, 2013.
Liu Zi, Tang Zhenmin, Ren Mingwu. Algoritme deteksi batas jalan secara real-time berdasarkan 3D lidar Jurnal Sains dan Teknologi Universitas Huazhong (Edisi Ilmu Pengetahuan Alam), 2011 (S2): 351-354.
Zeng Yiling, Xu Hongbo, Bai Shuo Peningkatan algoritma OPTICS dan aplikasinya dalam pengelompokan teks Journal of Chinese Information Processing, 2008 (1): 51-55, 60.
Zhuang Xiuhua. Penelitian tentang deteksi rintangan dan pelacakan berdasarkan lidar satu baris. Changsha: Universitas Hunan, 2014.
Dang Qiuyue, Lu Yueming Metode pengenalan cluster otomatis berdasarkan grafik jangkauan OPTICS Aplikasi Komputer, 2012 (S2): 19-21, 47.
Wang Pin, Huang Yan Penerapan algoritma OPTICS ditingkatkan dalam pengenalan modulasi Teknik dan Aplikasi Komputer, 2011 (16): 141-143.
Sun Tianyu, Sun Wei, Xue Min. OPTICS clustering dan model probabilistik wilayah target untuk beberapa pelacakan target bergerak. Chinese Journal of Image and Graphics, 2015 (11): 1492-1499.
Chen Yanli, Hong Long, Jin Dawen, dkk. Algoritme analisis pengelompokan berbasis kepadatan yang sederhana dan efektif. Jurnal Universitas Pos dan Telekomunikasi Nanjing, 2005 (4): 24-29.
Duan Jianmin, Li Longjie, Zheng Kaihua. Deteksi area jalan yang dapat dilalui di depan berdasarkan lidar 4-jalur on-board.Teknologi Otomotif, 2016 (2): 55-62.
Zou Leqiang Prinsip kuadrat terkecil dan penerapannya yang sederhana.Informasi Teknologi dan Sains, 2010 (23): 282-283.
Ding Keliang, Shen Yunzhong, Ou Jikun. Pemasangan Garis Lurus Kotak Terkecil Global. Jurnal Universitas Teknik Liaoning (Edisi Ilmu Pengetahuan Alam), 2010 (1): 44-47.
Cheng Yumin. Kemajuan Riset dan Review Moving Least Squares. Computer Aided Engineering, 2009 (2): 5-11, 20.
Duan Jianmin, Zheng Kaihua, Li Longjie, dkk. Algoritma ekstraksi informasi jalan berdasarkan multilayer lidar. Control Engineering, 2016 (4): 468-473.
- Paten baru Samsung terungkap! Sebuah smartphone tanpa batas sejati dengan tampilan layar di sekeliling tubuh
- Cara merancang dan memverifikasi algoritme pelacakan multi-target dengan kotak alat sistem penggerak otomatis | Kursus Terbuka Buat Keras