일반화 Houghough 변환

1981년 Dana H. Ballard에 의해 도입된 일반화 Hough 변환(GHT)은 템플릿 ^[1]매칭 원리를 사용하여 Hough 변환을 수정한 것입니다.Hough 변환은 초기에 분석적으로 정의된 모양(예: 선, 원, 타원 등)을 감지하기 위해 개발되었습니다.이러한 경우, 우리는 형상에 대한 지식을 가지고 이미지에서 형상의 위치와 방향을 찾는 것을 목표로 합니다.이 수정을 통해 Hough 변환을 사용하여 모델로 설명된 임의 개체를 탐지할 수 있습니다.

이미지에서 개체(모델로 설명됨)를 찾는 문제는 이미지에서 모델의 위치를 찾으면 해결할 수 있습니다.일반화 Hough 변환을 사용하면 모델의 위치를 찾는 문제가 모델을 이미지에 매핑하는 변환 매개 변수를 찾는 문제로 변환됩니다.변환 파라미터의 값을 지정하면 이미지에서의 모델 위치를 결정할 수 있습니다.

GHT의 원래 구현에서는 에지 정보를 사용하여 에지 포인트의 방향에서 쉐이프의 참조 포인트로의 매핑을 정의합니다.화소가 흑백이 될 수 있는 바이너리 화상의 경우, 화상의 모든 흑화소가 원하는 패턴의 흑화소가 될 수 있기 때문에 Hough 공간에 기준점의 궤적을 작성한다.영상의 모든 픽셀은 해당 기준점에 대해 투표합니다.Hough 공간의 최대점은 영상에서 패턴의 가능한 기준점을 나타냅니다.이 최대값은 Hough 공간을 스캔하거나 각각 검은색 ^[2]픽셀에 해당하는 완화된 방정식 세트를 풀어서 찾을 수 있습니다.

역사

멀린과 파버는^[3] 원하는 곡선을 분석적으로 설명할 수 없을 때 Hough 알고리즘을 사용하는 방법을 보여 주었다.그것은 번역에 한정되어 회전과 스케일 변화를 설명하지 않는 ^[4]발라드 알고리즘의 선구자였다.

멀린-파버 알고리즘은 엣지 픽셀이 많은 이미지에서는 반복적인 픽셀 배열로 인해 잘못된 포지티브가 많이 발견되므로 실제 이미지 데이터에는 실용적이지 않습니다.

일반화 하프 변환 이론

Hough 알고리즘을 비직교 곡선으로 일반화하기 위해 Ballard는 일반화된 형상에 대해 다음 파라미터를 정의합니다. 여기서 y는 형상의 기준 원점이고, θ는 방향이며, s = (s_x, s_y)는 두 개의 직교 스케일 계수를 설명합니다.알고리즘은 에지 픽셀 데이터로부터 주어진 형상에 대한 최적의 파라미터 세트를 계산할 수 있습니다.이들 파라미터의 상태는 동일하지 않습니다.기준 원점 위치 y는 가능한 에지 픽셀 방향의 R 테이블이라는 템플릿 테이블로 설명합니다.다음으로 추가 파라미터의 계산은 이 테이블에 대한 간단한 변환에 의해 이루어집니다.임의 도형에 대한 주요 일반화는 방향 정보를 사용하는 것입니다.파라메트릭 곡선 대신 임의의 형상 및 그 위에 고정된 기준점이 주어지면 변환 단계에서 경계 화소에 의해 제공되는 정보는 R테이블 형태로 기억된다.테스트 영상의 모든 모서리 점에 대해 R 테이블에서 점의 속성이 조회되고 기준점이 검색되며 누적기 매트릭스라는 매트릭스의 적절한 셀이 증가합니다.누적기 매트릭스에서 최대 '표'가 있는 셀은 테스트 영상에서 객체의 고정 기준의 가능한 존재 지점이 될 수 있습니다.

R 테이블 구축

셰이프에 대한 기준점 y를 선택합니다(일반적으로 셰이프 내부에서 선택됨).각 경계점 x에 대해 영상에 표시된 대로 경사 방향인 θ(x)와 r = y – x를 계산합니다.r을 ɸ의 함수로 저장합니다.θ의 각 인덱스는 r의 값을 많이 가질 수 있습니다.고정 기준과 가장자리 점 사이의 좌표 차이((x_c – x_ij),( y_c_ij - y)) 또는 반경 거리와 그 사이의 각도(r_ij_ij, α)로 저장할 수 있습니다. 각 점에 대해 이렇게 하면 R 테이블은 템플릿 개체를 완전히 나타냅니다.또한 생성 단계는 반전할 수 없기 때문에 이미지 내의 다른 위치에서 개체 발생을 현지화하는 데 사용할 수 있습니다.

일반화 Hough 변환을 위한 형상 검출 기하학

i	ɸ_i	R_{ɸ_i}
1	0	(r₁₁,α₁₁) (r₁₂,α₁₂)...(r_1n,α_1n)
2	Δɸ	(r₂₁,α₂₁) (r₂₂,α₂₂)...(r_2m,α_2m)
3	2 ★★★	(r₃₁,α₃₁) (r₃₂,α₃₂)...(r_3k,α_3k)
...	...	...

오브젝트 현지화

화상내의 각 엣지 픽셀 x 에 대해서, 구배 θ 를 구하고, 어큐뮬레이터 어레이 A(화상의 최대 사이즈로 초기화)내의 대응하는 모든 점 x+r 를 증가시킨다(r 는 θ 로 인덱스 된 테이블 엔트리, 즉 r(ɸ)).이러한 진입점은 각각 기준점에 대해 가능한 위치를 제공합니다.일부 가짜 점이 계산될 수 있지만, 영상에 개체가 존재하면 기준점에서 최대값이 발생합니다.A의 Maxima는 도형의 가능한 인스턴스에 해당합니다.

규모와 방향의 일반화

고정된 형상 방향의 경우, 축전지 배열은 기준점 좌표로 2차원적이었습니다.임의 방향 θ 및 축척 s의 모양을 검색하려면 이 두 매개변수가 모양 설명에 추가됩니다.이제 어큐뮬레이터 어레이는 파라미터(y, s, θ)에 대응하는 4차원으로 구성됩니다.R-표는 또한 다른 방향과 축척이 표의 쉽게 계산된 변환에 해당하므로 더 큰 치수 공간을 증가시키는 데 사용할 수 있습니다.형상 S에 대한 특정 R-테이블을 R(ɸ)로 나타낸다.이 테이블에 대한 간단한 변환으로 동일한 모양의 크기 조정 또는 회전 인스턴스를 탐지할 수 있습니다.예를 들어, 형상이 s로 스케일링되고 이 변환이 T로_s 표시되는 경우_s, T[R(s)] = sR(s) 즉, 모든 벡터는 s로 스케일링됩니다.또, 오브젝트를 θ 회전시켜, 이 변환을 T로_θ 나타내면_θ, T[R(r)] = Rot{R[(r)mod2θ], θ}, 즉 모든 인덱스를 - θ 모듈로2θ씩 증분하고, 적절한 벡터 r을 구하여 θ만큼 회전시킨다.일반화된 Hough 변환의 구성을 설명하는 데 유용한 또 다른 특성은 참조점의 변경입니다.새로운 기준점 θ를 y-solid = z로 선택하고 싶을 경우 R-테이블에 대한 수정은 R(solid)+z로 주어지며, 즉 표의 각 벡터에 z가 더해진다.

모서리 쌍을 사용하는 대체 방법

한 쌍의 에지 픽셀을 사용하여 파라미터 공간을 줄일 수 있습니다.R 테이블과 위에서 설명한 속성을 사용하여 각 에지 픽셀은 =(y, s, θ)의 4차원 축전지 공간에서 표면을 정의합니다.다른 방향의 2개의 엣지 픽셀은 θ에 대해 같은 양만큼 회전하는 동일한 표면을 나타낸다.이 두 지표면이 교차하는 경우 교차하는 점은 셰이프에 대해 가능한 매개변수 a에 해당합니다.따라서 이론적으로 영상 공간의 두 점을 사용하여 파라미터 공간의 궤적을 단일 점으로 줄일 수 있습니다.그러나 매개변수 공간에서 두 표면의 교차점을 찾기 어렵기 때문에 대부분의 경우 이 접근방식을 실행할 수 없다.

컴포지트 도형

형상 S가 부분 S₁, S₂, ..로 이루어진 복합 구조를 갖는 경우.S_N 및 S, S₁, S₂, .. 도형의 기준점.S는_N 각각 y, y₁, y₂, ..y이며_n, 스케일링 팩터 s 및 방향 $R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}$ 에 대해 일반화 Hough 변환_s R(1000)은 R $R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}$ $R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}$ $T$ { $R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}$ $R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}$ [ $R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}$ $R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}$ $=$ $R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}$ $R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}$ $R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}$ $R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}$ k ( $R_{\phi }=T_{s}\left\{T_{\theta }\left[\bigcup _{k=1}^{N}R_{s_{k}}(\phi )\right]\right\}$ ] $}$ { $displaystyle R_{\phi$ } \ $treft$ \ $t$ 로 주어진다. $T_{\theta }\left$ [\ $bigcup$ _ ${k=1}^{N}R_{s_{k}(phi)\right]\right$ 이 변환의 우려 사항은 기준 선택이 정확도에 큰 영향을 미칠 수 있다는 것입니다.이를 극복하기 위해 Ballard는 합성 평활 템플릿을 사용하여 결과 축적기를 평활할 것을 제안했습니다.합성 평활 템플릿 H(y)는 하위 형상의 개별 평활 템플릿의 합성곱으로 제공됩니다. $H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})$ ( $H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})$ ) $H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})$ i $H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})$ $H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})$ N $H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})$ ( $H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})$ - $H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})$ ) $H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})$ { $displaystyle$ H ( y ) = \ $sum$ _ { $H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})$ i $H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})$ = $1$ }^{ $N$ _ { i } ( y - y $H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})$ { $i$ } $H(y)=\sum _{i=1}^{N}h_{i}(y-y_{i})$ )그런 다음 개선된 누적기를 A = A*H로_s 나타내며 A의_s 최대값은 가능한 형상 인스턴스에 해당합니다.

공간 분해

전역 Hough 변환이 분리된 하위 영역의 로컬 Houg 변환의 합계에 의해 얻어질 수 있다는 것을 관찰하면서 Heather와^[5] Yang은 이미지를 하위 이미지로 재귀적으로 세분화하고 각각 자체 파라미터 공간을 가지며 쿼드 트리 구조로 구성하는 방법을 제안했다.이것에 의해, 메모리 코스트가 약간 증가해, 회선 세그먼트의 엔드 포인트의 검출 효율이 향상해, 노이즈가 많은 상황에서 회선을 추출할 때의 견고성과 신뢰성이 향상됩니다.

실행

실장에서는, 다음의 ^[6]방정식을 사용합니다.

$x=x_{c}+x'\ 또는 \x_{c}=x-x'$

$\displaystyle y=y_{c}+y' 또는 \y_{c}=y-y'}$

$\displaystyle \cos(\pi -\alpha)=xtext{or}\x'=r\cos(\pi -\alpha)=-r\cos(\alpha)}$

$\sin(\pi -\alpha)=ysinr(\text{or}\y'=r\sin(\pi -\alpha)$

위의 방정식을 조합하면 다음과 같이 됩니다.

$x_{c}=x+r\cos(\alpha)$

$\displaystyle y_{c}=y+r\sin(\alpha)}$

R-테이블

(0) Canny edge detector와 같은 엣지 검출 알고리즘을 사용하여 샘플 형상 이미지를 엣지 이미지로 변환한다.

(1) 기준점(예: (x_c, y_c))을 선택한다.

(2) 기준점에서 경계선까지 선을 긋는다.

(3) 컴퓨팅 »

(4) 기준점(x_c, y_c)을 ɸ의 함수로 R()) table에 저장한다.

검출:

(0) Canny edge detector와 같은 엣지 검출 알고리즘을 사용하여 샘플 형상 이미지를 엣지 이미지로 변환한다.

(1) 어큐뮬레이터 테이블을 초기화합니다.A [ x_cmin . . x_cmax ] [ y_cmin_cmax . y ]

(2) 각 엣지 포인트(x, y)에 대하여

(2.1) 경사각도 θ를 이용하여 θ 아래에 지수화된 모든 (α, r) 값을 R-표에서 취득한다.

(2.2) 각 (α,r)에 대해 기준점 후보를 계산한다.

x_c = x + r cos(α)

y_c = y + r sin(α)

(2.3) 카운터의 증가(투표):

++A([x_c][y_c])

(3) 물체 윤곽선의 가능한 위치는 A[x_c][y_c]의 국소 최대값으로 나타낸다.

A[x_c][y_c]> T인 경우 오브젝트 윤곽선은 (x_c, y_c)에 있습니다.

일반적인 케이스:

물체가 회전 δ 및 균일한 스케일링을 거쳤다고 가정합니다.

(x440, y440) --> (x440, y440)

x440 = (x440cos(δ) – y440sin(δ))s

y = (x sin sin ( θ ) + y cos cos ( θ ) s

x'를 x'로, y'를 y'로 치환:

x_c = x – x orた_c = x - (x-cos(δ) – y-sin(δ)s

y_c = y – y 또는 y_c = y - (x-sin(δ) + y-cos(δ)s

(1) 어큐뮬레이터 테이블을 초기화합니다.A_cmin [ x_cmin . . x_cmax ] [ y_min . . y_cmax ] [ q . .q_max_max ][ s_min . s ]

(2) 각 엣지 포인트(x, y)에 대하여

(2.1) 구배각θ를 이용하여 R-table에서 (α, r) 값을 모두 취득한다.

(2.2) 각 (α, r)에 대해 기준점 후보를 계산한다.

x140 = r cos(α)

y440 = r sin(α)

for(Ω = θ_min, θ_max 、 + + + )

(s = s_min; s_max ≤ s; s++)의 경우

x_c = x - (x-cos(δ) – y-sin(δ)s

y_c = y - (x-sin(δ) + y-cos(δ)s

++(A[x_c][y_c][]][s]

(3) 물체 윤곽선의 가능한 위치는 A[x_c][y_c][]][s]의 국소 최대값으로 나타낸다.

A[x_c][y_c][]][s]> T일 경우 물체 윤곽선은 (x_c, y_c)에 위치하고 회전 θ을 거친 후 s로 스케일링됩니다.

장점과 단점

이점

부분 또는 약간 변형된 형태(즉, 폐색 시 인식에 강력함)에 강하다.
영상에 추가 구조가 있는 경우 강력합니다.
그것은 소음에 강하다.
동일한 처리 경로 동안 여러 개의 도형이 발생할 수 있습니다.

단점들

객체 방향과 규모를 고려해야 할 때 첨예해지는 상당한 계산 및 저장 요건이 있습니다.

「」를 참조해 주세요.

레퍼런스

^ D.H. Ballard, "임의의 형상을 검출하기 위한 Hough 변환의 일반화", 패턴 인식, Vol.13, No.2, p.111-122, 1981
^ Jaulin, L.; Bazeille, S. (2013). Image Shape Extraction using Interval Methods (PDF). In Proceedings of Sysid 2009, Saint-Malo, France.
^ Merlin, P. M.; Farber, D. J. (January 1975). "A Parallel Mechanism for Detecting Curves in Pictures". IEEE Transactions on Computers. C-24 (1): 96–98. doi:10.1109/t-c.1975.224087. ISSN 0018-9340.
^ L. Davis, "계층적 일반화 Hough 변환 및 선분 기반 일반화 Hough 변환", 텍사스 컴퓨터 사이언스 대학, 1980년 11월
^ J.A. Heather, Sue Dong Yang, "Hough Transform의 공간 분해", 제2회 캐나다 컴퓨터 및 로봇 비전 컨퍼런스, 2005.
^ 발라드와 브라운, 섹션 4.3.4, Sonka 등, 섹션 5.2.6
^ A. A. 카심, T.Tan, K. H. Tan, "효율적인 일반 Hough 변환기법의 비교 연구", 이미지 및 비전 컴퓨팅, 제17권, 제10호, 737-748페이지, 1999년 8월
^ L. Davis와 S.Yam, "형상 인식을 위한 일반적인 Hough-like 변환"Texas Computer Sciences 대학, TR-134, 1980년 2월

외부 링크

일반화된 Hough transform http://docs.opencv.org/master/dc/d46/classcv_1_1GeneralizedHoughBallard.html의 OpenCV 구현
일반화된 Hough transforms 튜토리얼 및 구현
실용적인 범용 Hough 변환 구현 http://www.irit.fr/ ~ Julien . Pinquier / Docs / Hough _ transform . html
일반화된 Hough 트랜스폼의 FPGA 구현, IEEE 디지털 라이브러리 http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=5382047&url=http%3A%2F%2Fieeexplore.ieee.org%2Fxpls%2Fabs_all.jsp%3Farnumber%3D5382047
MATLAB의 일반화된 Hough 변환 구현 http://www.mathworks.com/matlabcentral/fileexchange/44166-generalized-hough-transform

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

[2] Jaulin, L.; Bazeille, S. (2013). Image Shape Extraction using Interval Methods (PDF). In Proceedings of Sysid 2009, Saint-Malo, France.

[3] Merlin, P. M.; Farber, D. J. (January 1975). "A Parallel Mechanism for Detecting Curves in Pictures". IEEE Transactions on Computers. C-24 (1): 96–98. doi:10.1109/t-c.1975.224087. ISSN 0018-9340.

[4] L. Davis, "계층적 일반화 Hough 변환 및 선분 기반 일반화 Hough 변환", 텍사스 컴퓨터 사이언스 대학, 1980년 11월

[5] J.A. Heather, Sue Dong Yang, "Hough Transform의 공간 분해", 제2회 캐나다 컴퓨터 및 로봇 비전 컨퍼런스, 2005.

[6] 발라드와 브라운, 섹션 4.3.4, Sonka 등, 섹션 5.2.6

[7] A. A. 카심, T.Tan, K. H. Tan, "효율적인 일반 Hough 변환기법의 비교 연구", 이미지 및 비전 컴퓨팅, 제17권, 제10호, 737-748페이지, 1999년 8월

[8] L. Davis와 S.Yam, "형상 인식을 위한 일반적인 Hough-like 변환"Texas Computer Sciences 대학, TR-134, 1980년 2월

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

Search

일반화 Houghough 변환

네임스페이스

더

목차

역사

일반화 하프 변환 이론

R 테이블 구축

오브젝트 현지화

규모와 방향의 일반화

모서리 쌍을 사용하는 대체 방법

컴포지트 도형

공간 분해

실행

장점과 단점

이점

단점들

관련 작업

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

일반화 Houghough 변환

역사

일반화 하프 변환 이론

R 테이블 구축

오브젝트 현지화

규모와 방향의 일반화

모서리 쌍을 사용하는 대체 방법

컴포지트 도형

공간 분해

실행

장점과 단점

이점

단점들

관련 작업

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.