모양 컨텍스트

Shape context

형상 컨텍스트객체 인식에 사용되는 형상 설명자다. 세르게 베인티지텐드라 말릭은 2000년 논문 '모양 문맥과의 매칭'에서 이 용어를 제안했다.[1]

이론

형상 문맥은 형상 유사성을 측정하고 점 대응의 회복을 가능하게 하는 형상을 기술하는 한 방법이다.[1] 기본적인 생각은 형상의 윤곽에서 n개의 점을 선택하는 것이다. 형상의 각 pi 점에 대해 pi 다른 모든 점에 연결하여 얻은 n - 1 벡터를 고려하십시오. 이 모든 벡터들의 집합은 그 시점에서 국부화된 형태에 대한 풍부한 설명이지만 너무 상세하다. 상대적 위치에 대한 분포가 견고하고, 콤팩트하며, 차별성이 높은 서술자라는 것이 핵심 생각이다. 따라서i, p 점의 경우, 나머지 n - 1 점의 상대 좌표에 대한 거친 히스토그램,

의 형상 컨텍스트로 정의된다 그 쓰레기통은 보통 통나무극 공간에서 균일하게 취해진다. 형상 컨텍스트가 풍부하고 차별적인 설명자라는 사실은 아래 그림에서 볼 수 있는데, 여기서 문자 "A"의 서로 다른 두 버전의 형상 컨텍스트가 나타난다.

Shapecontext.jpg

(a)와 (b)는 두 도형의 샘플링된 가장자리 지점이다. (c)는 도형 컨텍스트를 계산하는 데 사용되는 로그 추적 빈의 다이어그램이다. (d)는 (a)에 원으로 표시된 점, (e)는 (b)에 다이아몬드로 표시된 점, (f)는 삼각형에 대한 것이다. 알 수 있듯이 (d)와 (e)는 밀접하게 연관된 두 점에 대한 형상 컨텍스트이기 때문에 상당히 유사한 반면, (f)의 형상 컨텍스트는 매우 다르다.

피쳐 설명자가 유용하려면 특정 침입자가 있어야 한다. 특히 번역, 스케일링, 작은 동요, 그리고 용도에 따라 회전하는 것에 불변할 필요가 있다. 번역적 불변은 자연스럽게 문맥을 형성하게 된다. 척도 불변도는 모든 반지름 거리를 형상 내 모든 사이의 평균 거리 α {\displaystyle 정규화하여 얻지만 중위수 거리도 사용할 수 있다.[1][4] 형상 컨텍스트는 합성 포인트 세트 일치 실험을 사용하여 변형, 잡음 및 특이치에[4] 강한 것으로 실증적으로 입증된다.[5]

형태 맥락에서 완전한 회전 불변도를 제공할 수 있다. 한 가지 방법은 (점들이 가장자리에서 선택되기 때문에) 해당 지점의 접선 방향에 상대적인 각도를 측정하는 것이다. 이것은 완전히 순환 불변 설명자를 낳는다. 그러나 물론 일부 국소 형상은 동일한 프레임에 대해 측정하지 않으면 차별적 힘을 상실하므로 항상 이 기능이 필요한 것은 아니다. 실제로 많은 애플리케이션은 "6"을 "9"와 구별하는 것과 같은 회전 불변성을 금지한다.

쉐이프 매칭

형상 일치를 위해 형상 컨텍스트를 사용하는 전체 시스템은 다음 단계로 구성된다( 단계는 구현 세부사항 섹션에서 자세히 설명함).

  1. 알려진 셰이프의 가장자리에 있는 점 집합과 알 수 없는 셰이프의 다른 점 집합을 임의로 선택하십시오.
  2. 1단계에서 찾은 각 점의 형상 컨텍스트를 계산하십시오.
  3. 알려진 형상부터 알 수 없는 형상 위의 점까지 각 점을 일치시킨다. 일치 비용을 최소화하려면 먼저 알려진 도형의 가장자리를 알 수 없는 도형으로 휘는 변환(예: 아핀, 얇은 스플라인 등)을 선택하십시오(본질적으로 두 도형을 정렬). 그런 다음 알 수 없는 모양에서 알려진 셰이프의 각 뒤틀린 점과 가장 근접하게 일치하는 점을 선택하십시오.
  4. 두 도형의 각 점 쌍 사이의 "모양 거리"를 계산한다. 형상 컨텍스트 거리, 영상 외관 거리 및 벤딩 에너지(두 형상을 정렬하기 위해 얼마나 많은 변환이 필요한지 측정)의 가중 합계를 사용하십시오.
  5. 알 수 없는 형상을 식별하려면 가장 가까운 분류기를 사용하여 형상의 거리를 알려진 객체의 형상의 거리와 비교하십시오.

구현 상세 내역

1단계: 형상 모서리 점 목록 찾기

접근방식은 물체의 형상이 물체의 내부 또는 외부 등고선에 있는 점의 유한 부분 집합에 의해 본질적으로 포착된다고 가정한다. 이것들은 캐니 에지 검출기를 사용하여 가장자리에서 무작위적인 점 집합을 선택하는 것만으로 얻을 수 있다. 이러한 점은 필요하지 않으며 일반적으로 곡률의 최대치 또는 변곡점과 같은 키 포인트에 해당되지 않는다는 점에 유의하십시오. 중요하지는 않지만 대략 균일한 간격으로 모양을 표본으로 추출하는 것이 바람직하다.[2]

2단계: 쉐이프 컨텍스트 계산

이 단계는 이론 섹션에 자세히 설명되어 있다.

3단계: 비용 매트릭스 계산

K-bin 히스토그램(즉, 형상 컨텍스트) g(k)와 h(k)를 정규화한 두 을 고려한다. 형상 컨텍스트는 히스토그램으로 표현되는 분포이므로, χ2 검정 통계량을 다음 두 점을 일치시키는 "형상 컨텍스트 비용"으로 사용하는 것은 당연하다.

이 값의 범위는 0부터 1까지입니다.[1] 모양 컨텍스트 비용 외에도 외관에 따른 추가 비용이 추가될 수 있다. 예를 들어, 접선 각도 차이 측정(특히 숫자 인식에 유용함)이 될 수 있다.

이것은 각도가 { 1인 단위 벡터 사이의 단위 원 내 화음의 절반 길이로, 1}와 2 {\\theta 값도 0부터 1까지이다. 이제 두 점을 일치시키는 총 비용은 두 가지 비용의 가중 합이 될 수 있다.

이제 첫 번째 형태에 대한i 각 점 p와 두 번째 형태에 대한 점 qj 대해 설명한 대로 비용을 계산하고 C라고i,j 부른다. 이것이 비용 매트릭스다.

4단계: 총 비용을 최소화하는 매칭 찾기

일치 결과

자, 총 매칭 비용을 최소화하는 형상 1i 각 포인트 p와 형상 2의 qj 매칭하는 일대일 매칭i p,

필요하다. 이 작업은 보다 효율적인 알고리즘이 있지만 헝가리 방법하여O ( ){\ 수행할 수 있다.[6] 특이치를 강력하게 처리하려면, 일정하지만 상당히 많은 비용을 수반하는 "더미" 노드를 비용 매트릭스에 추가할 수 있다. 이렇게 하면 실제 일치 항목이 없을 경우 일치 알고리즘이 특이치를 "더미"에 일치시킬 수 있다.

5단계: 모델링 변환

두 형상상의 유한한 점 집합 사이의 대응 집합을 고려할 때, T: 2 → T^{2 \mathb {R} 한 형상에서 다른 형상까지 어떤 점이라도 매핑할 것으로 추정할 수 있다. 이 변환에는 아래에 설명된 몇 가지 선택사항이 있다.

아핀

어핀 은 표준 선택이다: ( p)= A + . A 변환 오프셋 벡터 o에 대한 최소 제곱 솔루션은 다음을 통해 얻는다.

Q{\displaystyle Q\!}에 대해서도 비슷한 표정으로 어디서 P는(1p11p12⋮ ⋮ ⋮ 1pn1p와 2){\displaystyle P={\begin{pmatrix}1&, p_{11}&, p_{12}\\\vdots, \vdots, \vdots \\1& &, p_{n1}& &, p_{n2}\end{pmatrix}}}. Q+{\displaystyle Q^{+}\!}은 pseudoinve.Q{의 rse \displa Q.

얇은 판 스플라인

얇은 스플라인(TPS) 모델은 쉐이프 컨텍스트 작업을 할 때 변환에 가장 널리 사용되는 모델이다. 2D 변환은 두 개의 TPS 함수로 분리하여 좌표 변환을 모델링할 수 있다.

여기x and과 ƒy 각각은 다음과 같은 형태를 가진다.

함수 (r) 은(는) ) =r 2 2 에 의해 정의된다 매개변수에 대한 해결 방법에 대한 정확한[7][8] 세부사항은 다른 곳에서 찾을 수 있지만, 그것은 본질적으로 방정식의 선형 시스템을 푸는 것을 포함한다. 벤딩 에너지(점들을 정렬하기 위해 얼마나 많은 변환이 필요한지 측정)도 쉽게 얻을 수 있을 것이다.

정규화된 TPS

위의 TPS 공식은 두 형상에서의 점 쌍에 대한 정확한 일치 요구사항을 가지고 있다. 소음이 많은 데이터의 경우 이 정확한 요구 사항을 완화하는 것이 가장 좋다. If we let denote the target function values at corresponding locations (Note that for , would the x-coordinate of the point cor 응답하고 대해 , y 이(가) 응답하여 요구량을 최소화하도록 완화함

서 I (는) 벤딩 에너지이며 (는) 정규화 매개 변수라고 한다. H[[]를 최소화하는 이 ƒ은 상당히 간단한 방법으로 찾을 수 있다.[9] , ) ( , y ) 에 대해 좌표 정규화를 사용하는 경우 스케일 invariance가 유지된다. 그러나 원래 비정규화된 좌표를 사용하는 경우에는 정규화 파라미터를 정규화할 필요가 있다.

많은 경우, 사용된 변환과 무관하게, 해당 서신의 초기 추정치는 변환의 품질을 떨어뜨릴 수 있는 일부 오류를 포함하고 있다. 만약 우리가 대응점을 찾고 변환을 추정하는 단계들을 반복한다면, 우리는 이 문제를 극복할 수 있을 것이다. 일반적으로 합리적인 결과를 얻기 위해서는 세 번의 반복이 전부다.

6단계: 형상 거리 계산

이제 두 형상 P P Q Q 사이의 형상 모수 거리는 다음과 같은 세 가지 잠재적 항으로 가중치가 부여된다

쉐이프 컨텍스트 거리: 최상의 일치점에 대한 쉐이프 컨텍스트 일치 비용의 대칭적인 합계:

여기서 T(·)는 Q의 점을 P의 점에 매핑하는 추정 TPS 변환이다.

화면표시 비용: 이미지 대응 방법을 설정하고 한 이미지를 다른 이미지와 일치하도록 적절히 반전시킨 후 화면표시 비용을 해당 이미지 포인트를 중심으로 가우스 윈도우의 밝기 차이를 제곱한 합으로 정의할 수 있다.

여기서 Q 는 회색 수준 이미지( 는 뒤틀린 이미지)이고 G G은 가우스 윈도우 기능이다.

변환 비용: 최종 비용 ( , ) 는 두 이미지를 정렬하기 위해 얼마나 많은 변환이 필요한지 측정한다. TPS의 경우 벤딩 에너지로 할당된다.

이제 두 형상 사이의 거리를 계산하는 방법이 생겼으니 여기서 계산한 형상 거리로 정의된 거리를 가지고 가장 가까운 이웃 분류기(k-NN)를 사용할 수 있다. 이를 다른 상황에 적용한 결과는 다음 절에 제시되어 있다.

결과.

숫자 인식

저자인 Serge MelicieJitendra MalikMNIST 데이터베이스에서 그들의 접근법을 시험했다. 현재 데이터베이스에서 50개 이상의 알고리즘이 테스트되었다. 데이터베이스에는 6만 개의 예제가 있는 교육용 세트와 1만 개의 예시가 있는 테스트 세트가 있다. 이 접근방식의 오류율은 2만 건의 교육 사례와 3-NN을 사용했을 때 0.63%였다. 발행 당시에는 이 오류율이 가장 낮았다. 현재 가장 낮은 에러율은 0.18%[10]이다.

실루엣 유사성 기반 검색

저자들은 MPEG-7 형상 실루엣 데이터베이스를 실험해 유사성 기반 검색 성능을 측정하는 코어 실험 CE-Shape-1 파트 B를 수행했다.[11] 데이터베이스는 70개의 형상 범주와 형상 범주당 20개의 이미지를 가지고 있다. 검색 방식의 성능은 각 이미지를 쿼리로 사용하고 상위 40개 일치 항목에 있는 올바른 이미지 수를 세어 테스트한다. 이 실험을 위해 저자들은 각 모양에서 표본 추출한 점의 수를 늘렸다. 또한 데이터베이스의 도형이 때때로 회전하거나 뒤집혔기 때문에, 저자들은 기준 도형과 쿼리 도형 사이의 거리를 조회 도형 사이의 최소 도형 거리로 정의하고 변경되지 않은 참조, 수직 도형 또는 수평 도형 도형 도형 도형을 정의했다.[1][2][3][4] 이런 변화로 2002년 최고였던 76.45%의 회수율을 얻었다.

3D 객체 인식

형상 컨텍스트에 대해 수행된 다음 실험은 콜롬비아 객체 이미지 라이브러리(COIL-20)에 있는 20개의 일반적인 가정용 물체와 관련되었다. 각 개체는 데이터베이스에 72개의 보기를 가지고 있다. 실험에서, 방법은 각 물체에 대해 동일한 간격으로 다수의 뷰에 대해 훈련되었고, 나머지 뷰는 테스트에 사용되었다. 1-NN 분류기가 사용되었다. 저자들은 또한 형상의 맥락 유사성과 성능을 향상시킨 k-medoid 클러스터링에 기초한 편집 알고리즘을 개발했다.[4]

상표검색

모양 컨텍스트는 데이터베이스에서 쿼리 상표로 가장 가까운 일치 상표(상표 침해 탐지 시 유용함)를 검색하는 데 사용되었다. 알고리즘에 의해 시각적으로 유사한 상표가 누락되지 않았다(작성자가 수동으로 검증함).[2]

외부 링크

참조

  1. ^ a b c d e S. Belongie & J. Malik (2000). "Matching with Shape Contexts". IEEE Workshop on Contentbased Access of Image and Video Libraries (CBAIVL-2000). doi:10.1109/IVL.2000.853834.
  2. ^ a b c d S. Belongie; J. Malik & J. Puzicha (April 2002). "Shape Matching and Object Recognition Using Shape Contexts" (PDF). IEEE Transactions on Pattern Analysis and Machine Intelligence. 24 (4): 509–521. doi:10.1109/34.993558.
  3. ^ a b S. Belongie; J. Malik & J. Puzicha (July 2001). "Matching Shapes" (PDF). Eighth IEEE International Conference on Computer Vision (July 2001).
  4. ^ a b c d S. Belongie; J. Malik & J. Puzicha (2000). "Shape Context: A new descriptor for shape matching and object recognition" (PDF). NIPS 2000.
  5. ^ H. Chui & A. Rangarajan (June 2000). "A new algorithm for non-rigid point matching". CVPR. 2. pp. 44–51. doi:10.1109/CVPR.2000.854733.
  6. ^ R. Jonker & A. Volgenant (1987). "A Shortest Augmenting Path Algorithm for Dense and Sparse Linear Assignment Problems". Computing. 38 (4): 325–340. doi:10.1007/BF02278710.
  7. ^ M.J.D. Powell (1995). "A Thin Plate Spline Method for Mapping Curves into Curves in Two Dimensions". Computational Techniques and Applications (CTAC '95). doi:10.1142/9789814530651.
  8. ^ J. Duchon (1977). "Splines Minimizing Rotation-Invariant Semi-Norms in Sobolev Spaces". Constructive Theory of Functions of Several Variables. Lecture Notes in Mathematics. 571: 85–100. doi:10.1007/BFb0086566. ISBN 978-3-540-08069-5.
  9. ^ G. Wahba (1990). Spline Models for Observational Data. Soc. Industrial and Applied Math.
  10. ^ Kowsari, Kamran; Heidarysafa, Mojtaba; Brown, Donald E.; Meimandi, Kiana Jafari; Barnes, Laura E. (2018-05-03). "RMDL: Random Multimodel Deep Learning for Classification". Proceedings of the 2018 International Conference on Information System and Data Mining. arXiv:1805.01890. Bibcode:2018arXiv180501890K. doi:10.1145/3206098.3206111.
  11. ^ S. Jeannin & M. Bober (March 1999). "Description of core experiments for MPEG-7 motion/shape. Technical Report ISO/IEC JTC 1/SC 29/WG 11 MPEG99/N2690, MPEG-7, Seoul". Cite 저널은 필요로 한다. journal= (도움말)