Binary Robust Independent Elementary Features (BRIEF)는 binary descriptor를 이용하는 알고리즘이다. 지난 게시글에서 설명을 하지 않고 넘어갔는데, descriptor는 이미지를 설명하는 특징 벡터 또는 해당 연산을 수행하는 알고리즘을 칭하는 말이다. 이 알고리즘 또한 SIFT를 개선하는 움직임에서 시작되었다. 처음 제안 된 binary descriptor로, 2010년에 제안되었다.
Smoothing Kernel
BRIEF는 이미지 픽셀 레벨에서 binary descriptor 작업을 하므로, 노이즈에 민감한(noise-sensitive) 특징을 보인다. 이는 keypoint를 pre-smooting을 하면서 개선이 가능하다.
Gaussian kernel을 사용해서 smoothing을 진행, 아래 표는 gaussian kernel의 표준편차($σ$)를 조정하여 결과를 비교한 표이다.
matching이 어려울 수록 성능을 올리는데 smoothing이 중요한 역할을 한다.
인식률은 1~3 범위에서 상대적으로 일정하게 유지되며, 실제로 2를 사용한다.
참고로 keypoint는 patch와 유사한 개념이다. 기준이 되는 pixel이 keypoint이고, 주변 픽셀을 포함한 범위가 patch이다.
Binary Descriptor (이진 기술자)
이전에 다룬 SIFT와 SURF 둘 다 메모리를 매우 많이 소모하고, 이는 feature matching 시간이 더 오래 걸리는 원인이 된다. BRIEF는 이러한 문제를 줄이고자 하는데, 어떤 방식으로 했는지 살펴본다.
Binary Feature Vector
Descriptor에 사용되는 바이트 수
SIFT: 128 차원 벡터를 사용 => 부동 소수점 숫자를 사용하므로 512 바이트가 소모
SURF: 최소 64차원 벡터를 사용 => 256 바이트 이상 소모
keypoint 마다 descriptor가 적용되므로, 매우 많은 메모리를 소모하게 된다.
=> 128 차원, 64차원 등의 모든 차원에서 실제로 매칭을 모두 필요로 하는가? -> X
=> 따라서, 압축이 가능하다.
검출 된 keypoint에 대한 descriptor를 생성 => keypoint 주변 영역의 픽셀을 다른 픽셀과 비교하여 어느 부분이 더 밝은지 찾아 이진 형식으로 저장한다.
주변 영역보다 어두우면 1,나머지는 0
위 예시에서 255가 90보다 크므로 0이 된다.
모든 픽셀에 대해서 descriptor를 수행하지 않고, $s_1$, $s_2$를 선택하여 구한다.
기준은 어떻게 되는가? => Sampling Geometries
BRIEF는 keypoint를 찾는 방법은 제공하지 않는다. 따라서, 다른 논문에서 제시한 방법을 기반으로 keypoint를 찾고, descriptor를 적용하는데 이용할 수 있다.
Sampling Geometries
픽셀을 선택하는데 임의의 쌍을 선택하는 방법은 5가지가 있다. 아래의 5가지 sampling 방법 중 한 가지를 선택하여 사용한다.
patch의 크기가 $(SxS)$일 때, keypoint는 patch의 중앙에 위치한다.
Uniform(G I): x, y 픽셀 모두 균일한 분포 또는 주변의 $s/2$만큼의 spread에서 선택한다. $(x, y)$ pair는 패치 경계에 놓일 수 있다. (spread: 산포도)
Gaussian(G II): x, y 픽셀에 대해서 Gaussian 분포에 따라 선택하거나, 주변 $0.04*S^2$ spread에서 선택한다.
Gaussian(G III): 무작위 쌍의 첫 픽셀 x는 $0.04S^2$의 표준편차 혹은 spread를 사용하여 keypoint를 중심으로 하는 Gaussian 분포에서 그려진다. 두 번째 픽셀 y는 $0.01S^2$의 표준편차 또는 spread를 갖는 Gaussian 분포에서 그려진다. 이로 인해서 pair가 좀 더 localize 된다. 패치 외부의 pair는 가장자리로 고정된다.
Coarse Polar Grid(G IV): x, y 필셀 모두 spatial quantization(공간 양자화)를 coarse polar grid의 분리된 위치에서 선택된다.
Coarse Polar Grid(G V): 첫 번째 픽셀 x는 (0, 0)에 위치하고, 두 번째 픽셀은 coarse polar grid의 분리된 위치에서 선택된다.
Oriented FAST Robusted BRIEF (ORB)는 앞서 설명한 BRIEF의 확장 버전이다. 이미지 회전에 강한 성질을 가진다. FAST의 keypoint 추출 + BRIEF의 DESCRIPTOR를 통해서 방향과 스케일에 대한 불변성을 얻었다고 한다. SIFT와 SURF는 특허가 걸려 있어서 상업적 용도로 사용이 안되는데, ORB는 가능하다.
Keypoint 추출
FAST로 keypoint를 추출한다. 간단히 복습하자면
어떤 점 p에 대해서 p를 중심으로 하는 반지름 3인 원 상의 16개 픽셀 값에 대해서
일정 값 이상 밝거나 어두운 픽셀이 n개 이상 연속된 경우 코너이다.
p가 코너로 인식되면 인접한 주변 점들도 코너로 검출되는 경우가 많으므로 후처리를 한다.
FAST로 추출한 keypoint를 Harris Corner Detection으로 Top N개 점을 찾는다.
Harris Corner Detection: 픽셀간의 기울기 (극점)을 이용해서 코너를 찾는 알고리즘
FAST는 자체적으로 코너를 만들어내지 않기 때문에 코너를 추출하기 위함
피라미드 구조를 사용하여 Multi-Scale 특징점을 계산한다.
이러한 구조는 SIFT와 유사한 듯.. 이전에 공부했던 내용을 복습하는 기분이다.
FAST는 방향에 대한 계산이 포함되지 않는다. => Centroid 방법을 사용해 방향성을 구함
패치 중앙에 모서리가 있는 경우, intensity를 가중치로 하는 중앙점을 계산한다.
Orientation($θ$): 코너의 중심점(O) -> 패치 중앙점(C) 방향
Rotation Invariance(회전 불변성)을 개선하기 위해서 반경 r의 영역에 있어야 하는 x, y로 모멘트 계산
=> FAST에 방향성을 더한 O-FAST keypoint dectector
Descriptor 계산
SURF, BRIEF에서도 언급 되었 듯이 SIFT는 128차원을 사용, 연산 속도가 느린 단점이 있다. Descriptor 자체가 많은 비트를 가지고 있어야 하기 때문에 SURF에서도 큰 개선을 보이지는 않았으나, 위에서 설명한 BRIEF의 이진화(binarize)가 대안으로 따라온다.
keypoint 주변의 랜덤한 픽셀 쌍을 선택
첫 번째 픽셀은 keypoint를 중심으로 하는 가우시안 분포에서 선택한다.
두 번째 픽셀은 첫 번째 픽셀을 중심으로 2배 큰 분산을 가지는 분포에서 선택한다.
첫 번째 픽셀이 두 번째 픽셀보다 밝다면 1, 아니라면 0을 부여한다.
이를 128번 반복 -> 128bit 벡터 생성
BRIEF는 시점, 조명, 블러에 강인하지만 회전에는 약한 성질을 보인다. ORB에서는 각도를 12도로 고정한 상태에서 모든 BRIEF 패턴을 계산, 속도를 빠르게 하는 Steered BRIEF 방식을 R-BRIEF라는 이름으로 적용하였다.
Feature matching
ORB를 사용해서 feature matching을 하는 방법을 설명한다.
Feature extractor에서 image feature를 찾는다.
Descriptor로 벡터를 추출, 이를 입력된 이미지의 feature와 비교한다.
비교 결과가 좋은 good matching을 추출한다.
입력된 이미지의 keypoint와 유사한 feature의 keypoint 값이 여러 개 존재할 수 있음
적당한 keypoint를 골라내는 작업 => NNDR(Nearest Neighbor Distance Ratio)
$$NNDR = {{distance\ to\ best\ match}\over {distance\ to\ second\ best\ match}}$$
snaag
commented
8 months ago
오늘은 마지막 BRIEF, ORB를 끝으로 드디어 특징 추출을 마무리할 것이다. 이 다음은 feature matching이다.
BRIEF
Binary Robust Independent Elementary Features (BRIEF)는binary descriptor를 이용하는 알고리즘이다. 지난 게시글에서 설명을 하지 않고 넘어갔는데, descriptor는 이미지를 설명하는 특징 벡터 또는 해당 연산을 수행하는 알고리즘을 칭하는 말이다. 이 알고리즘 또한 SIFT를 개선하는 움직임에서 시작되었다. 처음 제안 된 binary descriptor로, 2010년에 제안되었다.Smoothing Kernel
BRIEF는 이미지 픽셀 레벨에서 binary descriptor 작업을 하므로, 노이즈에 민감한(noise-sensitive) 특징을 보인다. 이는 keypoint를 pre-smooting을 하면서 개선이 가능하다.
Gaussian kernel을 사용해서 smoothing을 진행, 아래 표는 gaussian kernel의 표준편차($σ$)를 조정하여 결과를 비교한 표이다.참고로
keypoint는 patch와 유사한 개념이다. 기준이 되는 pixel이 keypoint이고, 주변 픽셀을 포함한 범위가 patch이다.Binary Descriptor (이진 기술자)
이전에 다룬 SIFT와 SURF 둘 다 메모리를 매우 많이 소모하고, 이는 feature matching 시간이 더 오래 걸리는 원인이 된다. BRIEF는 이러한 문제를 줄이고자 하는데, 어떤 방식으로 했는지 살펴본다.
Binary Feature Vector
Descriptor에 사용되는 바이트 수
SIFT: 128 차원 벡터를 사용 => 부동 소수점 숫자를 사용하므로 512 바이트가 소모SURF: 최소 64차원 벡터를 사용 => 256 바이트 이상 소모keypoint마다 descriptor가 적용되므로, 매우 많은 메모리를 소모하게 된다. => 128 차원, 64차원 등의 모든 차원에서 실제로 매칭을 모두 필요로 하는가? -> X => 따라서, 압축이 가능하다.검출 된 keypoint에 대한 descriptor를 생성=> keypoint 주변 영역의 픽셀을 다른 픽셀과 비교하여 어느 부분이 더 밝은지 찾아 이진 형식으로 저장한다.주변 영역보다 어두우면 1,나머지는 0
Sampling Geometries
픽셀을 선택하는데 임의의 쌍을 선택하는 방법은 5가지가 있다. 아래의 5가지 sampling 방법 중 한 가지를 선택하여 사용한다.
patch의 크기가 $(SxS)$일 때, keypoint는 patch의 중앙에 위치한다.
Uniform(G I): x, y 픽셀 모두 균일한 분포 또는 주변의 $s/2$만큼의 spread에서 선택한다. $(x, y)$ pair는 패치 경계에 놓일 수 있다. (spread: 산포도)Gaussian(G II): x, y 픽셀에 대해서 Gaussian 분포에 따라 선택하거나, 주변 $0.04*S^2$ spread에서 선택한다.Gaussian(G III): 무작위 쌍의첫 픽셀 x는 $0.04S^2$의 표준편차 혹은 spread를 사용하여 keypoint를 중심으로 하는 Gaussian 분포에서 그려진다.두 번째 픽셀 y는 $0.01S^2$의 표준편차 또는 spread를 갖는 Gaussian 분포에서 그려진다. 이로 인해서 pair가 좀 더 localize 된다. 패치 외부의 pair는 가장자리로 고정된다.Coarse Polar Grid(G IV): x, y 필셀 모두 spatial quantization(공간 양자화)를 coarse polar grid의 분리된 위치에서 선택된다.Coarse Polar Grid(G V):첫 번째 픽셀 x는 (0, 0)에 위치하고, 두 번째 픽셀은 coarse polar grid의 분리된 위치에서 선택된다.아래는 각각의 geometry 방식에 따른 recognition 범위이다.
참고
ORB
Oriented FAST Robusted BRIEF (ORB)는 앞서 설명한 BRIEF의 확장 버전이다. 이미지 회전에 강한 성질을 가진다.FAST의 keypoint 추출 + BRIEF의 DESCRIPTOR를 통해서 방향과 스케일에 대한 불변성을 얻었다고 한다. SIFT와 SURF는 특허가 걸려 있어서 상업적 용도로 사용이 안되는데, ORB는 가능하다.Keypoint 추출
FAST로 keypoint를 추출한다. 간단히 복습하자면FAST로 추출한 keypoint를
Harris Corner Detection으로 Top N개 점을 찾는다.피라미드 구조를 사용하여Multi-Scale 특징점을 계산한다.FAST는 방향에 대한 계산이 포함되지 않는다. =>
Centroid 방법을 사용해 방향성을 구함intensity를 가중치로 하는 중앙점을 계산한다.Rotation Invariance(회전 불변성)을 개선하기 위해서 반경 r의 영역에 있어야 하는 x, y로 모멘트 계산=> FAST에 방향성을 더한 O-FAST keypoint dectector
Descriptor 계산
SURF, BRIEF에서도 언급 되었 듯이 SIFT는 128차원을 사용, 연산 속도가 느린 단점이 있다. Descriptor 자체가 많은 비트를 가지고 있어야 하기 때문에 SURF에서도 큰 개선을 보이지는 않았으나, 위에서 설명한
BRIEF의이진화(binarize)가 대안으로 따라온다.BRIEF는 시점, 조명, 블러에 강인하지만 회전에는 약한 성질을 보인다. ORB에서는 각도를 12도로 고정한 상태에서 모든 BRIEF 패턴을 계산, 속도를 빠르게 하는 Steered BRIEF 방식을 R-BRIEF라는 이름으로 적용하였다.
Feature matching
ORB를 사용해서 feature matching을 하는 방법을 설명한다.
NNDR(Nearest Neighbor Distance Ratio)$$NNDR = {{distance\ to\ best\ match}\over {distance\ to\ second\ best\ match}}$$NNDR이 작을 수록 good matching이다.참고