랜덤화 Hough 변환

Hough 변환은 많은 컴퓨터 비전 구현 또는 이미지로부터의 데이터 마이닝에서 중요한 단계인 객체 검출을 위한 기술입니다.특히 랜덤화 하프 변환은 기존의 하프 변환에 대한 확률론적 변형이며 곡선(직선, 원, 타원 등)^[1]을 검출하는 데 일반적으로 사용된다.Hough 변환(HT)의 기본 개념은 이미지 내의 모든 잠재적 곡선에 대해 투표 절차를 구현하는 것이며, 알고리즘의 종료 시 이미지에 존재하는 곡선은 상대적으로 높은 투표 점수를 가집니다.RHT(Randomized Hough transform)는 분석 곡선의 기하학적 특성을 이용하여 영상의 모든 픽셀에 대해 계산 비용이 많이 드는 투표 프로세스를 수행하지 않도록 함으로써 시간 효율을 향상시키고 원래 알고리즘의 저장 요건을 줄이려고 한다는 점에서 HT와는 다릅니다.

동기

Hough 변환(HT)은 곡선 검출에 널리 사용되고 있습니다만, 다음의 2개의 큰 ^[2]결점이 있습니다.우선, 화상내의 0이 아닌 각 화소에 대해서, 투표 절차중에 기존의 커브와 용장 커브 양쪽의 파라메타가 축적된다.둘째, 어큐뮬레이터 어레이(또는 Hough 공간)는 휴리스틱 방식으로 사전 정의된다.정확도가 높을수록 더 높은 파라미터 분해능을 정의해야 합니다.이러한 두 가지 요구로 인해 일반적으로 실제 애플리케이션에서는 스토리지 요구 사항이 크고 속도가 느려집니다.따라서 RHT는 이 문제에 대처하기 위해 도입되었습니다.

실행

HT와 비교하여 RHT는 일부 분석 곡선이 곡선의 특정 개수의 점에 의해 완전히 결정된다는 사실을 이용한다.예를 들어 직선은 2개의 점으로, 타원(또는 원)은 3개의 점으로 결정할 수 있습니다.타원 검출의 경우 RHT의 기본 개념을 설명하기 위해 사용할 수 있습니다.전체 프로세스는 일반적으로 다음 3단계로 구성됩니다.

임의로 선택한 점으로 타원형을 맞춥니다.
어큐뮬레이터 어레이 및 해당 점수를 업데이트합니다.
점수가 사전 정의된 임계값보다 높은 생략형을 출력합니다.

타원 피팅

타원을 정의하기 위한 하나의 일반적인 $a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1$ 은 $a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1$ a $a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1$ - $a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1$ ) $a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1$ + $a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1$ b ( $a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1$ - $a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1$ p ) $a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1$ + $a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1$ ( $a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1$ - $a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1$ ) 2 $a(x-p)^{2}+2b(x-p)(y-q)+c(y-q)^{2}=1$ 1 \ $display$ a ( x - p )^{ $2}$ + $2$ b ( x - p ) + $c$ ( y - $q$ )^2 $= 1$ 입니다.

제한: $ac-b^{2}>0$ $ac-b^{2}>0$ - $ac-b^{2}>0$ 2 $ac-b^{2}>0$ > $ac-b^{2}>0$ { $display$ style $ac$ - b^ {2 $}$ > $0$ }

그러나 타원에 대한 세 가지 점과 이 점의 접선을 알고 있다면 타원은 완전히 판별할 수 있다.

RHT는 타원에서 세 점을 무작위로 선택하는 것으로 시작합니다.X, X₂, X로₃ 합시다₁.첫 번째 단계는 이 세 개의 점의 접선을 찾는 것입니다.인접한 픽셀의 작은 창에 대해 최소 제곱 기법을 사용하여 직선을 적합시켜 찾을 수 있습니다.

다음 단계에서는 접선의 교차점을 찾습니다.이는 이전 단계에서 찾은 선 방정식을 풀면 쉽게 수행할 수 있습니다.다음으로 교차점을 T와₂₃ T로 하고₁₂ $X_{1}X_{2}$ $X_{1}X_{2}$ X2 $({$ X_ ${1$ } $X_{2}})$ $X_{2}X_{3}$ $X_{2}X_{3}$ $({$ X_ ${2}X_{3})$ 의 $X_{2}X_{3}$ 중간점을 M과₂₃ M으로 합니다₁₂.그러면 타원의 중심은 $T_{12}M_{12}$ $({$ })와 $T_{{12}}M_{{12}}$ $T_{23}M_{23}$ $({$ 의 교점에 놓이게 되며, 교차점의 좌표는 선 방정식을 풀어서 알 수 있으며, 자세한 과정은 생략한다.

이전 단계에서 찾은 타원 중심 좌표를 (x₀, y₀)로 합니다.그런 다음 중심은 x $x'=x-x_{0}$ $=$ $x'=x-x_{0}$ - $x'=x-x_{0}$ 0 {\ $displaystyle$ x'= $x-x_{$ 0 $x'=x-x_{0}$ }} $y'=y-y_{0}$ $=$ $y'=y-y_{0}$ - $y'=y-y_{0}$ 0 {\ $displaystyle$ y $'=y_{$ 0 $y'=y-y_{0}$ }}을 $x'=x-x_{0}$ 하여 원점으로 변환하여 타원 방정식을 다음과 같이 단순화할 수 있습니다.

${{displaystyle 도끼'^{2}+2bx'y'+cy'^{2}=1}$

이제 위의 방정식에₂₃ X, X, X의 좌표를₁ 대입함으로써 나머지 타원 파라미터인 a, b, c를 풀 수 있습니다.

축적하다

이전 단계에서 결정된 타원 파라미터에 따라 어큐뮬레이터 어레이를 갱신할 수 있다.기존의 Hough 변환과 달리 RHT는 "버킷의 그리드"를 어큐뮬레이터 어레이로 유지하지 않습니다.대신 먼저 새로 검출된 타원과 축적기 배열에 이미 저장되어 있는 타원의 유사도를 계산합니다.다른 메트릭을 사용하여 유사도를 계산할 수 있습니다.유사도가 미리 정의된 임계값을 초과하는 한 누적기의 값을 두 줄기의 평균으로 바꾸고 점수에 1을 더합니다.그렇지 않으면 이 타원을 누적기의 빈 위치로 초기화하고 1점을 할당합니다.

종료

한 후보 타원의 점수가 임계값을 초과하면 이미지에 존재하는 것으로 판단되며(즉, 이 타원이 감지됨), 알고리즘이 다른 잠재적 타원을 더 빨리 탐지할 수 있도록 이미지 및 축척기 배열에서 제거해야 합니다.알고리즘은 반복 횟수가 최대 제한에 도달하거나 모든 타원이 검출되면 종료됩니다.

RHT ^[3]유사 코드:

(타원이 발견되고 최대 에폭에 도달하지 않음) {용(고정 반복 횟수) {잠재 타원을 찾습니다. (타원이 누산기의 타원과 유사함) 그런 다음 누산기의 하나를 두 개의 평균 타원으로 교체하고 1을 점수에 추가합니다. 그렇지 않으면 삽입1의 점수로 누름판의 빈 위치에 타원을 배치; } 가장 좋은 점수를 가진 타원을 선택하여 최적의 타원 테이블에 저장; 이미지에서 가장 좋은 타원의 픽셀 제거; 누름판을 비웁니다. }

레퍼런스

^ D.H. Ballard, "임의의 형상을 검출하기 위한 Hough 변환의 일반화", 패턴 인식, Vol.13, No.2, p.111-122, 1981
^ L. 쉬, E.오자, 그리고 P.Kultanan, "새로운 곡선 검출 방법: RHT(Randomized Hough transform)", 패턴 기록. 11번지, 1990년, 331-338번지
^ S. Inverso, "랜덤화 Hough 변환을 사용한 타원 검출", www.saminverso.com/res/vision/EllipseDetectionOld.pdf,, 2002년 5월 20일

[1] D.H. Ballard, "임의의 형상을 검출하기 위한 Hough 변환의 일반화", 패턴 인식, Vol.13, No.2, p.111-122, 1981

[2] L. 쉬, E.오자, 그리고 P.Kultanan, "새로운 곡선 검출 방법: RHT(Randomized Hough transform)", 패턴 기록. 11번지, 1990년, 331-338번지

[3] S. Inverso, "랜덤화 Hough 변환을 사용한 타원 검출", www.saminverso.com/res/vision/EllipseDetectionOld.pdf,, 2002년 5월 20일

[1]

[2]

[3]

Search

랜덤화 Hough 변환

네임스페이스

더

목차

동기

실행

타원 피팅

축적하다

종료

레퍼런스