Efficient L-Shape Fitting for Vehicle Detection Using Laser Scanners(2017) 논문 리뷰

딥러닝 모델을 사용하지 않고, Point Cloud 데이터에서 Vehicle을 찾고자 한 시도가 있었습니다. 기본적으로 고전적인 알고리즘을 활용하고 있습니다. LiDAR 데이터 특성에 맞게 적용한 부분에 대해 중점적으로 설명드리겠습니다. 

 

Segmentation

  Point Cloud 데이터를 취득하면, 각 Point를 Cluster로 묶어야 합니다. 즉 같은 Object에 속하는 Point끼리 묶어 Cluster를 만들어야 하며 이러한 과정을 Segmentation이라 합니다. 해당 논문에서는 Object로 Vehicle만 다루고 있습니다. Segmentation 알고리즘을 아래 pseudo code로 나타냈습니다. 기본 아이디어는 distance threshold(r)를 이용한다는 것입니다. 각 scan point에 대해 K-D tree를 이용해 neighboring points를 찾고, 거리가 r보다 작으면 cluster로 묶습니다. (참고로 scan ordering index를 알고 있다면 해당 과정을 더 빠르게 할 수 있습니다.) cluster 내에 포함된 어떠한 point와 거리가 r보다 작다면 cluster로 묶습니다. 이러한 과정을 cluster가 더 이상 커지지 않을 때까지 반복합니다. 

  해당 알고리즘이 Adaptive한 이유는 distance threshold(r) 값이 Point와 LiDAR 거리에 비례하여 정해지기 때문입니다 (line8). 이렇게 하는 이유는 LiDAR에서 먼 Point일수록 수평방향으로 Point간 거리가 커지기 때문입니다. 

 

L-Shape Fitting

Cluster를 얻었다면, 해당 Points에 가장 잘 fitting되는 Rectangle을 찾는 것이 목표입니다. Fitting Performance를 평가하는 고전적인 평가 기준은 Least-squares 입니다. 따라서 정석적으로 최적화 문제를 풀어야 하지만, combinatorial complexities에 의해 해를 구하기 어렵고 Real-time application에 활용할 수 없습니다. 

그래서 해당 논문에서는 Search-Based Algorithm을 사용합니다. 기본 아이디어는 모든 가능한 direction에 대해 Fitting을 시도한다는 것입니다. direction이 정해지면, Cluster의 Points를 모두 포함하는 Rectangle을 쉽게 구할 수 있고, 각 Point와 Rectangle 4개 edge간 거리를 계산할 수 있습니다. 이런 방식으로 least squared error를 갖는 optimal direction을 구할 수 있습니다. 

해당 논문에서는 squared error를 최소화하기 위해 사용하는 Criterion(line 7)으로 3가지를 제시하고 있습니다. (각 Criterion은 장점과 단점을 갖고 있습니다.)

1) Rectangle area Minimization

2) Points-to-Edges Closeness Maximization

3) Points-to-Edges squared error Minimization

 

3개의 Criterion 

 

Experimental Results

각 Criterion에 대한 평가는 얼마나 효율적으로 계산하는지, 얼마나 정확한지로 하였습니다.

1.  Computation Effieiency

실 도로에서 약 10,000번의 scan을 하고, 계산 시간을 구했을 때 Variance Criterion의 경우가 가장 시간이 많이 걸렸습니다. 그 이유는 분산을 계산할 때 시간이 많이 걸리기 때문입니다. 

Computation Time

2. Rectangle Fitting Correctness

---

https://www.youtube.com/watch?v=qPkvNidYnAA