원 호프 변환

Circle Hough Transform
기능 검출
에지 검출
코너 검출
블럽 검출
능선 검출
하프 변환
구조 텐서
아핀 불변 피쳐 검출
기능 설명
공간 축척

Circle Hough Transform(CHT)은 불완전한 영상에서 원을 검출하기 위한 디지털 영상 처리에 사용되는 기본 특징 추출 기법입니다.원 후보는 Hough 매개변수 공간에서 "투표"한 다음 누적기 행렬에서 로컬 최대값을 선택하여 생성됩니다.

이것은 Hough 변환의 전문화입니다.

이론.

2차원 공간에서는 원을 다음과 같이 설명할 수 있습니다.

여기서 (a,b)는 원의 중심이고 r은 반지름입니다.2D 점(x,y)이 고정된 경우 (1)에 따라 파라미터를 찾을 수 있습니다.파라미터 공간은 (a, b, r)의 3차원입니다.그리고 (x, y)를 만족시키는 모든 매개변수는 정점이 (x, y, 0)인 역직각 원뿔의 표면에 놓인다.3D 공간에서 원 매개변수는 2D 원의 점에 의해 정의된 많은 원뿔 표면의 교차로 식별할 수 있습니다.이 과정은 두 단계로 나눌 수 있습니다.첫 번째 단계는 반지름을 고정하고 2D 매개변수 공간에서 최적의 원의 중심을 찾는 것입니다.두 번째 단계는 1차원 매개변수 공간에서 최적의 반지름을 찾는 것입니다.

반지름이 R인 매개 변수 찾기

반지름이 고정된 경우 파라미터 공간이 2D(원 중심 위치)로 줄어듭니다.원래 원의 각 점(x, y)에 대해 (1)에 따라 반지름이 R인 (x, y)을 중심으로 하는 원을 정의할 수 있습니다.매개변수 공간에 있는 모든 원의 교차점은 원래 원의 중앙점에 해당합니다.

Circle Hough transform of four points on a circle

원본 영상(왼쪽)에서 원의 점 4개를 고려합니다.원 Hough 변환은 오른쪽에 표시됩니다.반지름은 이미 알고 있는 것으로 간주됩니다.원본 영상에서 4개의 점(흰 점) 중 각(x,y)에 대해 반지름이 r인 (x,y)를 중심으로 하는 Hough 파라미터 공간에서 원을 정의할 수 있습니다.누적 행렬은 교차점을 추적하기 위해 사용된다.매개 변수 공간에서 원이 통과하는 포인트의 투표 수가 1씩 증가합니다.그러면 로컬 최대점(오른쪽 그림 중앙의 빨간색 점)을 찾을 수 있습니다.최대값의 위치(a, b)는 원래 원의 중심이 될 것이다.

반지름이 R인 여러 원

동일한 기법으로 동일한 반지름을 가진 여러 원을 찾을 수 있습니다.Fig 4: Circle Hough transform of four points on 3 circles

축전지 매트릭스(오른쪽 그림)에는 최소 3개의 국소 최대점이 있습니다.

누적 매트릭스 및 투표

실제로 파라미터 공간에서의 교차점을 구하기 위해 누산기 행렬이 도입된다.우선 격자를 사용하여 파라미터 공간을 "버킷"으로 나누고 격자에 따라 누적 매트릭스를 생성해야 합니다.누적기 행렬의 요소는 매개변수 공간의 해당 그리드 셀을 통과하는 매개변수 공간의 "원" 수를 나타냅니다.이 숫자는 "투표 번호"라고도 불립니다.처음에 매트릭스 내의 모든 요소는 0입니다.그런 다음 원래 공간의 각 "엣지" 점에 대해 매개변수 공간에 원을 공식화하고 원이 통과하는 그리드 셀의 투표 수를 늘릴 수 있습니다.이 과정을 "투표"라고 합니다.

투표 후 누적 매트릭스에서 로컬 최대값을 찾을 수 있습니다.로컬 최대값의 위치는 원래 공간의 원 중심에 해당합니다.

반지름을 알 수 없는 원 매개 변수 찾기

파라미터 공간이 3D이기 때문에 축전지 매트릭스도 3D가 됩니다.가능한 반지름을 통해 반복할 수 있습니다. 각 반지름에 대해 이전 기술을 사용합니다.마지막으로 3D 어큐뮬레이터 매트릭스에서 로컬 최대값을 찾습니다.축전지 어레이는 3D 공간에서 A[x,y,r]이어야 합니다.투표는 각 픽셀, 반지름 및 세타 A[x,y,r] += 1에 대해 실시해야 합니다.

알고리즘:

  1. 각 A[a,b,r] = 0에 대하여
  2. 이미지 가우스 블러링에 대한 필터링 알고리즘을 처리하고, 이미지를 그레이스케일(그레이스케일링)로 변환하고, Canny 연산자로 만들고, Canny 연산자는 이미지에 가장자리를 제공합니다.
  3. 축전지 내의 가능한 모든 원에 투표합니다.
  4. 누적기 A의 로컬 최대 투표 원은 원에 Hough 공간을 제공합니다.
  5. 누적기의 최대 투표 원은 원을 나타냅니다.

최적 후보 증가: 

각 A[a,b,r] = 0; // 처음에 0으로 채우는 3D 행렬을 인스턴스화합니다. 각 셀(x,y)에 대해 각 세타 t = 0 ~ 360 // 가능한 세타 0 ~ 360 b = y – r * sin (t * PI / 180); // 중심(라디안까지)의 극좌표 //x rtA[a,b,r] +=1; //종단부

예

신발 자국에서 동그라미 찾기

Find circles in a shoe-print

원본 그림(오른쪽)은 먼저 임계값 및 가우스 필터를 사용하여 이진 이미지(왼쪽)로 변환됩니다.그런 다음 캐니 에지 검출을 사용하여 에지(중간)를 찾습니다.그런 다음 모든 모서리 점이 Circle Hough 변환에 의해 기본 원 구조를 찾는 데 사용됩니다.

제한 사항

CHT의 파라미터 공간은 3차원이기 때문에 많은 저장과 계산이 필요할 수 있습니다.더 큰 그리드 크기를 선택하면 이 문제가 개선될 수 있습니다.

그러나 적절한 그리드 크기를 선택하는 것은 어렵습니다.그리드가 너무 거칠면 많은 서로 다른 구조가 단일 버킷에 해당하기 때문에 투표의 큰 값을 잘못 얻을 수 있습니다.그리드가 너무 미세하면 정확히 정렬되지 않은 토큰에서 생성된 투표가 서로 다른 버킷에 포함되고 투표가 많은 버킷이 없기 때문에 구조를 찾을 수 없습니다.

또한 CHT는 노이즈에 대해 그다지 견고하지 않습니다.

내선번호

적응형 Hough 변환

J. Ilingworth와 J. Kittler는 Hough Transform을 효율적으로 구현하기 위해 이 방법을 도입했습니다.AHT는 소규모 어큐뮬레이터 어레이와 유연한 반복적 "미세화" 축적 및 검색 전략을 사용하여 Hough 파라미터 공간에서 중요한 피크를 식별합니다.이 방법은 스토리지 요건과 계산 요건 모두에서 표준 Hough Transform 구현보다 훨씬 우수합니다.

어플

인원수 계산

또, 화상의 동그라미와 같은 헤드이기 때문에, [2]화상의 헤드를 검출하기 위해서 CHT 를 사용할 수 있어 화상중의 인원을 카운트 할 수 있다.

뇌동맥류 검출

MHCT(수정된 Hough Circle Transform)는 DSA(디지털 감산 혈관 조영)에서 추출한 영상에 동맥류 유형을 감지하고 분류하는 데 사용됩니다.

[3]

구현코드

「 」를 참조해 주세요.

레퍼런스

  1. ^ J. Ilingworth와 J. Kittler, "어댑티브 하프 트랜스폼", PAMI-9, 호: 5, 1987, 페이지 690-698
  2. ^ Hong Liu, Yueliang Qian 및 Shouun Lin, "감시 비디오에서 HOW Circle Transform을 사용하여 인물 검출"
  3. ^ Mitra, Jubin 등. "수정된 Hough circle 변환을 사용하여 뇌동맥류를 검출하기 위한 계층 산의 피크 트레킹." 컴퓨터 비전과 이미지 분석에 관한 ELCVIA 전자 편지 12.1(2013).http://elcvia.cvc.uab.es/article/view/v12-n1-mitra-chandra-halder