가속 세그먼트 테스트의 특징

Features from accelerated segment test

가속 세그먼트 테스트(FAST)의 피쳐는 코너 감지 방법으로, 피쳐 포인트를 추출하는 데 사용할 수 있으며, 나중에 많은 컴퓨터 비전 작업에서 객체를 추적하고 매핑하는 데 사용될 수 있다.FAST 코너 검출기는 원래 에드워드 로스텐과 톰 드러먼드에 의해 개발되었으며 2006년에 출판되었다.[1]FAST 코너 검출기의 가장 유망한 장점은 연산 효율이다.그 이름을 언급하면, SIFT, SUSAN, Harris 검출기가 사용하는 Gaussian (DoG)의 차이와 같이, 많은 잘 알려진 특징 추출 방법보다 실제로 빠르다.더욱이 머신러닝 기법을 적용하면 연산 시간과 자원의 측면에서 우수한 성능을 실현할 수 있다.FAST 코너 검출기는 이러한 고속 성능 때문에 실시간 비디오 처리 애플리케이션에 매우 적합하다.

세그먼트 테스트 검출기

FAST 코너 검출기에서 사용하는 픽셀

FAST 코너 검출기는 16픽셀의 원(반경 3의 브레센햄 원)을 사용하여 후보 포인트 p가 실제로 코너인지 여부를 분류한다.원의 각 픽셀은 시계방향으로 정수 번호 1에서 16까지 라벨이 붙어 있다.원의 N 연속 픽셀 집합이 모두 후보 픽셀 p(I로p 표시됨)의 강도에 임계값 t를 더한 값 또는 후보 픽셀 p에서 임계값 t를 뺀 강도보다 모두 어두운 경우, p는 코너로 분류된다.조건은 다음과 같이 기재할 수 있다.

  • 조건 1: N 연속 픽셀 S 집합,∀ { S x > I + 임계값p 또는 > I + t )
  • 조건 2: N 연속 픽셀 S 집합, { S < -

그래서 두 가지 조건 중 어느 한쪽이 충족되면 p후보는 코너로 분류할 수 있다.N, 연속 픽셀 수 및 임계값 t를 선택하는 트레이드오프가 있다.한편으로, 검출된 코너 포인트의 수가 너무 많으면 안 되는 반면, 높은 성능은 계산 효율을 희생시켜서는 안 된다.기계학습의 향상 없이 N은 보통 12로 선택된다.비코너 포인트를 배제하기 위해 고속 시험 방법을 적용할 수 있다.

고속시험

비코너 포인트를 거부하는 고속 테스트는 픽셀 1, 9, 5 및 13의 4가지 예시 픽셀을 검사하여 작동한다.왜냐하면 후보 코너보다 모두 밝은지 어두운지 적어도 12개의 연속 픽셀이 있어야 하기 때문에, 이 4가지 예시 픽셀 중에서 후보 코너보다 밝은지 어두운 픽셀이 적어도 3개 이상 있어야 하기 때문이다.먼저 픽셀 1과 9를 검사하는데, I와1 I가9 모두 [Ip - t, Ip + t] 안에 있다면 후보 p는 코너가 아니다.그렇지 않으면 픽셀 5와 13은 그 중 3개가p I + t보다 밝은지 또는p 어두운지 여부를 추가로 검사한다. 만약 그 중 3개가 더 밝은지 어두운지 나머지 픽셀은 최종 결론을 위해 검사한다.그리고 그의 첫 논문에서 발명가에 따르면 후보 코너 픽셀을 확인하기 위해 평균 3.8픽셀이 필요하다고 한다.[2]각 후보 코너당 8.5픽셀에 비해 3.8픽셀은 정말 큰 폭으로 감소해 높은 실적 개선 효과를 볼 수 있다.

그러나 이 테스트 방법에는 다음과 같은 몇 가지 약점이 있다.

  1. N < 12에 대해서는 고속 시험을 잘 일반화할 수 없다.N < 12인 경우, 후보 p가 코너일 가능성이 있으며, 시험 픽셀 4개 중 2개만이 Ip - t보다 밝은p I + t 또는 어두운 검정색일 수 있다.
  2. 검출기의 효율성은 이러한 선택된 시험 픽셀의 선택과 순서에 따라 달라진다.그러나 선택된 픽셀이 코너 외관 분포에 대해 우려하는 최적의 픽셀일 가능성은 낮다.
  3. 여러 형상이 서로 인접하여 감지됨

머신러닝으로 개선

초고속 시험의 처음 두 약점을 해결하기 위해, 기계 학습 접근법을 도입하여 검출 알고리즘을 향상시킨다.이 기계 학습 접근법은 두 단계로 운영된다.첫째로, 지정된 N의 코너 탐지는 대상 애플리케이션 도메인에서 선호하는 교육 이미지 세트에 대해 처리된다.모서리는 문자 그대로 16픽셀의 링을 추출하고 강도 값을 적절한 임계값과 비교하는 가장 간단한 구현을 통해 감지된다.

p후보자의 경우 원 x ∈ {1, 2, 3, ..., 16}의 각 위치는 p→x로 나타낼 수 있다.각 픽셀의 상태는 다음p→x 세 가지 상태 중 하나여야 한다.

  • d, Ip→x ≤ Ip - t (더 어둡다)
  • s, Ip - tp→x ≤ Ip ≤ I + t (비슷한)
  • bp→xp, I≥ I + t (브래이터)

그런 다음 x(모든 P에 대해 동일) 파티션 P(모든 교육 이미지의 모든 픽셀 집합)를 3개의 하위 집합(Pd, Ps, Pb)으로 선택하여 다음 작업을 수행하십시오.

  • Pd = {p ∈ P : Sp→x = d }
  • Ps = {p ∈ P : Sp→x = s }
  • Pb = {p ∈ P : Sp→x = b }

둘째, 의사결정 트리 알고리즘, ID3 알고리즘을 16개 위치에 적용하여 최대 정보 이득을 얻는다.K는 p가 코너인지 여부를p 나타내는 부울 변수가 되게 하고, K의p 엔트로피는 p가 코너인지의 정보를 측정하는 데 사용된다.픽셀 Q 집합의 경우 KQ(정규화되지 않음)의 총 엔트로피는 다음과 같다.

  • H(Q) = ( c + n ) 로그2(c + n )- 나막신2 - nlogn2.
    • 여기서 c = { i ∈ Q: K는i true}(코너 수)
    • 여기서 n = { i ∈ Q: K는i false}(비코너 수)

정보 이득은 다음과 같이 나타낼 수 있다.

  • Hg= H(P) - H(Pb) - H(Ps) - H(P) - H(Pd)

정보 이득을 최대화할 수 있는 각 x를 선택하기 위해 각 하위 집합에 재귀적 프로세스를 적용한다.예를 들어, 처음에 x는 P를 가장d 많은 정보를 가지고 Ps, P, P로b 분할하기 위해 선택된다. 그리고 각 부분 집합에d 대해 다른s y는b 가장 많은 정보 이득을 얻기 위해 선택된다(y는 x와 같을 수 있다는 주의).이 재귀적 프로세스는 엔트로피가 0일 때 끝나므로 해당 부분 집합의 모든 픽셀이 코너 또는 비코너로 된다.

생성된 이 의사결정 트리는 C와 C++와 같은 프로그래밍 코드로 변환될 수 있는데, 이는 중첩된 if-else 문들의 묶음일 뿐이다.최적화 목적으로, 프로파일 가이드 최적화는 코드를 컴파일하는 데 사용된다.준수된 코드는 나중에 다른 영상에 대해 코너 검출기로 사용된다.

이 결정 트리 알고리즘을 사용하여 검출된 코너는 세그먼트 테스트 검출기를 사용한 결과와 약간 달라야 한다.의사결정 트리 모델은 가능한 모든 코너를 커버할 수 없는 훈련 데이터에 의존하기 때문이다.

비최대 억제

세그먼트 테스트는 코너 응답 기능을 계산하지 않기 때문에 비최대 억제 기능을 결과 기능에 직접 적용할 수 없다.단, N이 고정된 경우, 각 픽셀 p에 대해 코너 강도는 p를 코너로 만드는 t의 최대값으로 정의된다.따라서 다음과 같은 두 가지 접근법을 사용할 수 있다.

  • p가 여전히 코너인 가장 큰 t를 찾기 위해 바이너리 검색 알고리즘을 적용할 수 있다.따라서 매번 의사결정 트리 알고리즘에 대해 다른 t가 설정된다.그것이 가장 큰 t를 찾았을 때, 그것이 가장 큰 강점으로 간주될 수 있다.
  • 또 다른 접근방식은 반복 방식으로, 매번 t가 시험에 합격하는 최소값으로 증가된다.

FAST-ER: 반복성 향상

FAST-ER 검출기는 메타휴리스틱 알고리즘을 사용하여 FAST 검출기를 개선한 것으로, 이 경우 시뮬레이션된 어닐링이다.최적화 후 의사결정 트리의 구조가 최적화되고 반복성이 높은 지점에 적합하도록 한다.그러나 시뮬레이션된 어닐링은 메타휴리스 알고리즘이므로, 매번 알고리즘은 다른 최적화된 의사결정 트리를 생성한다.따라서 실제 최적화에 가까운 솔루션을 찾기 위해서는 효율적으로 많은 양의 반복을 하는 것이 좋다.로스텐에 따르면 3GHz에서 펜티엄 4에서 200시간 정도 걸리는 데 이는 10만 번 반복 100회 반복으로 FAST 검출기를 최적화한다.

다른 디텍터와의 비교

로스텐의 연구에서 FAST 및 FAST-ER 검출기는 여러 데이터셋에서 평가되며 DoG, Harris, Harris-Laplace, Shi-Tomasi 및 SUSAN 코너 검출기와 비교된다.[3]

검출기(FAST 제외)에 대한 파라미터 설정은 다음과 같다.

검출기 파라미터 설정 가치
개
옥타브당 척도 3
초기 블러 σ 0.8
옥타브스 4
수잔. 거리 임계값 4.0
해리스, 시토마시 블러 σ 2.5
해리스 라플라스 초기 블러 σ 0.8
해리스 블러 3
옥타브스 4
옥타브당 척도 10
일반 매개변수 ε 5픽셀
  • 반복성 테스트 결과는 모든 데이터셋에 걸쳐 프레임당 0-2000개 코너에 대한 반복성 곡선 아래의 평균 영역으로 표시된다(적층 노이즈 제외:
검출기 A
FAST-ER 1313.6
FAST-9 1304.57
개 1275.59
시앤토마시 1219.08
해리스 1195.2
해리스 라플라스 1153.13
FAST-12 1121.53
수잔. 1116.79
무작위 271.73
  • 3.0GHz 펜티엄 4-D 컴퓨터에서 속도 테스트를 수행했다.데이터 세트는 교육 세트와 테스트 세트로 나뉜다.훈련 세트는 해상도가 992×668픽셀인 101개의 단색 이미지로 구성된다.테스트 세트는 단색 352×288 비디오의 4968 프레임으로 구성되어 있다.그 결과는 다음과 같다.
검출기 교육 세트 픽셀 비율 테스트 세트 픽셀 속도
FAST n=9 188 179
FAST n=12 158 154
원본 FAST n=12 79 82.2
FAST-ER 75.4 67.5
수잔. 12.3 13.6
해리스 8.05 7.90
시토마시 6.50 6.50
개 4.72 5.10

참조

  1. ^ Rosten, Edward; Drummond, Tom (2006). "Machine Learning for High-speed Corner Detection". Computer Vision – ECCV 2006. Lecture Notes in Computer Science. Vol. 3951. pp. 430–443. doi:10.1007/11744023_34. ISBN 978-3-540-33832-1. S2CID 1388140.
  2. ^ 에드워드 로스텐, 증강현실을 위한 실시간 비디오 주석
  3. ^ 에드워드 로스텐, 더 빠르고 더 나은: 코너 탐지에 대한 기계 학습 접근 방식

참고 문헌 목록

  • Rosten, Edward; Reid Porter; Tom Drummond (2010). "FASTER and better: A machine learning approach to corner detection". IEEE Transactions on Pattern Analysis and Machine Intelligence. 32 (1): 105–119. arXiv:0810.2434. doi:10.1109/TPAMI.2008.275. PMID 19926902.

외부 링크