Line Segment Detection

논문 : Probabilistic lane detection and lane tracking for autonomous vehicles using a cascade particle filter

Line detection 및 기타 알고리즘 코드, 논문 : (Faster) Line segment detection OpenCV C++ source code

논문 : Line segment detection using weighted mean shift procedures on a 2D slice sampling strategy

 

Line Segment Weighted Mean Shift

 

1. 요약 。Sobel 연산을 사용하여 Gradient 영상을 사용 ( Gx, Gy, G) 。G 영상은 Weight와 후보 영역을 검사하기 위함( G 영상의 픽셀 전체 평균보다 G가 클 경우에 Line Segment를 시작) 。Gx, Gy는 방향(angle)을 추론하는데 사용 。Mean Shift는 시작점과 끝점을 좀 더 정확하게 찾을때 사용. - 즉, 현재 포인트(시작점)를 기준으로 일정 영역 내부에서 시작점과 유사한 방향을 갖는 점들로 Mean Shift를 수행하고, 수렴하는 점을 현재 포인트로 정함 - 다시 말해서 좀 더 정확하게 선의 시작점을 찾기 위함인듯 함. 。grow - 시작점이 주어지면 해당 점으로부터, 확장을 수행( Bresenham 알고리즘) -  。Sobel

LSD : a Line Segment Detector

[ Paper ] [ Code(C) ]

1. Abstract LSD 는 정확한 결과를 주는 선형시간의 라인 세그먼트 검출기이다. 이것은 파라미터없이 디지털 영상에서 처리할 수 있도록 고안되었다.  1. Introduction - LSD는 영상에서 지역적으로 직선을 검출하는 것을 목표로 한다. 이것을 line segment라고 부르겠다. Contour는 그레이 영상에서 어두운 부분에서 밝은 부분으로 빠르게 변화하는 구간이다. 반대도 마찬가지이다. 따라서 그라디언트와 level-line은 아주 중요한 컨셉이다.  이 알고리즘은 level-line field를 계산하기 위해, 각 픽셀에서 level-line angle를 계산함으로써 시작한다. 그러면, 이러한 필드는 어떤 임계값 t를 기준으로 유사한 level-line angle을 갖는다면, 연결된 영역으로 분할한다. 그림 2와 같이, 이러한 연결된 영역을 line support regions이라 불려진다.   각 line support region은 line segment의 후보이다. 대응하는 기하학적 객체( 이 경우에는 사각형)은 반드시 line segment로 할당된다. line support region의 주축은 사각형의 주방향으로 사용된다. 사각형의 크기는 그림 3과 같이 전체 영역을 커버할 수 있는 크기로 선택된다. 각 사각형은 검증 절차를 따른다. 그림 4와 같이, 사각형 내부에서 level line angle이 사각형의 각도를 기준으로 tolerance t에 속하는 각 픽셀을 정렬된 포인트(aligned points)라 한다. 사각형의 내부의 전체 픽셀 수를 n이라고하고, 정렬된 포인트의 수를 k라 한다. 그리고, 이것은 검출된 line segment가 사각형인지 아닌지 검증하기 위해 사용된다. 검증 단계는 Contrario 방법에 기반하며, [3,4]번 논문에 기반한다. Contrario에 대한 간략한 설명 .... line segment의 경우에서, 우리는 aligned points의 수를 사용한다. 우리는 contraro model에서 line segment는 관찰된 line segment와 같이, 좀 더 많은 aligned points를 가지는 이벤트를 고려한다. 이미지 i와 사각형 r이 주어졌을때, 우리는 aligned points의 수 k(r,i)와 사각형 r 내부의 전체 픽셀 수 n(r)를 주목한다. 그러면 관찰된 것과 같이, 기대되는 event의 수는 N_test * P_H0 [ ( k(r,I) > k(r,i) ] 이며, 여기서 N_test는  2. Algorithm 2.1 Image Scaling 2.2 Gradient Computation 2.3 Gradient Pseudo-Ordering 2.4 Gradient Threshold 2.5 Region Growing 2.6 Rectangular Approximation 2.7 NFA Computation 2.8 Aligned Points Density 2.9 Rectangle Improvement 2.10 Computaion Complexity

제목

 

1. 입력 영상을 가우시안 마스크를 통해 0.8로 다운 샘플링 2. Line Angle 영상 생성 2 x 2 Pixel Window A B C D gx = B+D - (A+C) gy = C+D - (A+B) angle = atan2(gx, -gy) g = sqrt ( (gx*gx + gy*gy)/4.0 ) 3. gradient의 max 값으로 정규화하고, 이를 gradient가 큰 순서대로 정렬함. - 그림과 같은 순서로 동작한다. 먼저 ①과 같이, Gradient의 값과 MaxG(Gradient 영상에서의 최대값)를 이용해서 bin의 위치를 결정한다. Bin의 위치가 결정되면, List Structure의 주소값을 Start Address와 End Address에 저장한다. 왜냐하면, 현재 bin index를 갖는 Gradient값이 처음이므로, 초기화 해준다고 생각하자. 그리고, 다음 픽셀을 같은 방식으로, Bin의 위치를 선택하고, 만약 해당 bin에 속하는 픽셀이 있는 경우, End Address를 참조하여 lint->next에 현재 주소를 저장해놓는다. 그리고, End Address는 다른 픽셀이 해당 Bin에 속할 경우 연결을 위해, 자신의 주소로 대체하여 저장한다. 예를 들어, 쉽게 설명하면, G(0,0)의 bin 인덱스가 5라고, 가정하면, list(0)의 주소가 Start Address와 End Address에 저장된다. 그리고, 같은 방법으로 진행하다가 G(1, 1)의 Bin 인덱스가 5가 또 나온 경우, End Address->next에 현재 list(7)의 주소를 저장한다. 결국 End Address는 list(0)을 나타내므로, list(0)에 list(7)을 연결한다는 의미이다. 그리고 마지막으로 bin이 5일 경우인 다른 화소들을 위해, list(7)의 주소는 End Address에 저장된다. 그렇게 해야 나중에 또 다른 화소가 bin 5에 속할 경우, list(0)->list(7)->list(x)와 같이 연결 할 수 있기 때문이다. - 이러한 작업이 완료되면, 각각 bin에 속하는 list들이 생성되었을 것이다. 이제, 이것을 하나의 list로 구성하는 작업을 수행해야한다. gradient가 큰 순서로 선을 검출하기 때문에, bin 인덱스가 큰 위치의 list 구조를 가장 처음에 놓는다. 그리고, 다음 list 구조를 이전 리스트 구조 뒤에 연결한다. 이렇게 함으로써 gradient가 큰 위치대로 list가 구성된다.