허프 변환: 컴퓨터 비전에서 Hough 변환의 마법 공개

By Fouad Sabry

무릎  변환이란 무엇입니까

무릎 변환은 이미지 분석, 컴퓨터 비전 및 디지털 이미지 처리에 사용되는 특징 추출 기술입니다. 이 기술의 목적은 투표 절차를 통해 특정 종류의 모양 내에서 개체의 불완전한 인스턴스를 찾는 것입니다. 이 투표 절차는 매개변수 공간에서 수행되며, 여기서 객체 후보는 무릎 변환 계산 알고리즘에 의해 명시적으로 구성된 소위 누산기 공간에서 로컬 최대값으로 얻어집니다.

이점

(I) 다음 주제에 대한 통찰력 및 검증:

1장: 무릎 변환

2장: 일반화 허프 변환

3장: 무작위 허프 변환

4장: 원형 허프 변환

5장: 선 감지

6장: 3차원 투영

7장: 매개변수 방정식

8장: 방정식

9장: 타원

10장: 시소이드

(II) 허프 변환에 관한 대중의 주요 질문에 답합니다.

(III) 다양한 분야에서 허프 변환을 사용하는 실제 사례.

누구 이 책은

전문가, 학부생 및 대학원생, 열성팬, 취미생활자, 그리고 모든 종류의 허프 변환에 대한 기본 지식이나 정보를 넘어서고 싶은 사람들을 위한 것입니다.

• Language: 한국어
• Publisher: 10 억 지식이 걸립니다 [Korean]
• Release date: Apr 28, 2024

Book preview

1 장 : 허프 변환

Hough 변환은 디지털 이미지 처리, 컴퓨터 비전 및 이미지 분석 분야에서 일반적인 특징 추출 방법입니다. 이 방법은 투표 시스템을 사용하여 특정 양식 클래스에 속하는 개체의 불완전한 인스턴스를 식별합니다. Hough 변환 계산 알고리즘은 소위 누산기 공간에서 객체 후보가 국소 최대값으로 발견되는 매개변수 공간에서 이 투표를 수행합니다.

원래 Hough 변환은 그림에서 직선을 찾는 데 중점을 두었지만 이후 원 및 타원과 같은 직사각형이 아닌 형태의 중심을 찾는 것을 포함하도록 확장되었습니다. 1972년 Richard Duda와 Peter Hart는 현재 널리 사용되는 일반화된 Hough 변환을 개발했습니다. 1981년 임의의 모양을 감지하기 위한 허프 변환 일반화라는 제목의 저널 기사에서 Dana H. Ballard는 컴퓨터 비전 분야에 변환을 소개했습니다.

자동 버블 챔버 이미지 분석에 사용하기 위해 처음 개발되었습니다(Hough, 1959).

1962년 미국 원자력위원회(U.S. Atomic Energy Commission)에 제출된 미국 특허 3,069,654는 복잡한 패턴을 인식하기 위한 방법 및 수단(Method and Means for Recognizing Complex Patterns)으로 허프 변환(Hough transform)을 기술하고 있습니다. 이 특허는 선에 대한 기울기-절편 파라미터화를 특이하게 사용하여 기울기가 무한할 수 있기 때문에 무한 변환 공간을 생성합니다.

현재 모든 곳에서 사용되는 rho-theta 매개 변수화에 대한 초기 설명은 다음에서 찾을 수 있습니다.

두다, RO; Hart, P. E. (1972년 1월). Hough 변환을 사용하여 그림의 선과 곡선 감지. 통신 ACM. 15:11–15 참조. doi:10.1145/361237.361242입니다. S2CID 1105637.

1930년대가 되어서야 라돈 변환의 표준이 되었음에도 불구하고.

O'Gorman-Clowes 변형에 대한 설명은 다음에서 찾을 수 있습니다.

오고먼, 프랭크; 클로즈, MB (1976). 특징점의 공선성을 통한 사진 가장자리 찾기. IEEE Trans. 전산. 25 (4): 449–456. doi:10.1109/TC.1976.1674627입니다. S2CID 10851078.

현재 Hough 변환이 어떻게 개발되었는지는 에 설명되어 있습니다.

Hart, P. E. (2009년 11월). 허프 변환이 발명된 방법(PDF). IEEE 신호 처리 매거진. 26 (6): 18–22. doi:10.1109/msp.2009.934181입니다. S2CID 16245096. 2018년 5월 16일에 원본 문서 (PDF)  에서 보존된 문서.

선, 원, 타원과 같은 기본 모양을 감지하는 것은 디지털 이미지의 자동 분석에서 공통적인 과제입니다. 이미지 공간에서 원하는 곡선 위에 놓인 사진 포인트 또는 픽셀을 검색할 때 가장자리 검출기를 예비 단계로 사용할 수 있습니다. 그러나 이미지 데이터 또는 에지 검출기의 결함으로 인해 에지 검출기에서 획득되는 이상적인 선/원/타원과 잡음이 있는 에지 점 사이에 필요한 곡선 및 공간적 변동에 누락된 점 또는 픽셀이 있을 수 있습니다. 이 때문에 추출된 모서리 특징을 직선, 곡선 또는 타원의 모음으로 적절하게 분류하는 것이 어려울 수 있습니다. 이 문제를 해결하기 위해 Hough 변환은 매개 변수가 있는 그림 개체 집합에서 명시적 투표 메커니즘을 사용하여 인접한 가장자리 점 쌍을 개체 후보로 분류합니다(Shapiro and Stockman, 304).

허프 변환은 직선 감지에 가장 쉽게 적용됩니다. 매개 변수 공간의 점 (b, m)은 직선 y = mx + b를 나타냅니다. 그러나 수직선에서 문제가 발생합니다. 그 결과 기울기 매개변수인 m이 무한 값을 갖게 됩니다. 따라서 Duda와 Hart는 컴퓨팅의 효율성을 위해 헤세 정규형을 제안했습니다.

{\displaystyle r=x\cos \theta +y\sin \theta ,}

여기서 r 는 원점에서 직선에서 가장 가까운 점까지의 거리이고,  는 \theta 축과 원점과 가장 가까운 점을 연결하는 선 x 사이의 각도 입니다.

이 모양의 직관성은 평면 방정식과 같은 방식으로 선의 모든 벡터가 원점에서 오는 길이의 직선에 수직(직교)이어야 한다는 것입니다 r .

기능선의 교차점과 원점에서 오는 수직선이 에 있다는 것을 쉽게 알 수 있습니다 {\displaystyle P_{0}=(r\cos \theta ,r\sin \theta )} .

따라서 선의 모든 점에 대해 P 벡터는 {\displaystyle P-P_{0}} 벡터와 직교해야 합니다 {\displaystyle P_{0}-0=P_{0}} .

따라서 함수 라인의 {\displaystyle P=(x,y)} 모든 점에 대해 방정식이 {\displaystyle (P-P_{0})\cdot P_{0}=0} 충족되어야 한다는 것을 알 수 있습니다.

따라서 {\displaystyle P\cdot P_{0}=P_{0}\cdot P_{0}} .

{\displaystyle P=(x,y)} 이후 및 {\displaystyle P_{0}=(r\cos \theta ,r\sin \theta )} , 우리는 .

{\displaystyle r(x\cos \theta +y\sin \theta )=r^{2}(\cos ^{2}\theta +\sin ^{2}\theta )}

이후 {\displaystyle \cos ^{2}\theta +\sin ^{2}\theta =1} 로, 우리는 의 최종 형태를 얻습니다 {\displaystyle x\cos \theta +y\sin \theta =r} .

따라서 이미지의 각 라인과 한 쌍을 연결할 수 있습니다 (r,\theta ) .

평면 (r,\theta ) 은 2차원의 직선 집합에 대해 Hough 공간 이라고도 합니다.

Hough 변환은 그 묘사 덕분에 개념적으로 2차원 라돈 변환에 가깝습니다.

실제로 라돈 변환과 허프 변환은 수학적으로 동일하지만 두 변환과 관련된 고유한 계산 의미가 있습니다.

작업할 평면 점이 하나뿐인 경우 (r, t) 좌표계의 정현파 곡선은 해당 위치 θ) 평면을 통과하는 직선의 모음이며, 당시에는 특이 평면입니다.

점 모음을 가져와서 직선으로 배열 하면 해당 선의 (r, θ)에서 만나는 정현파가 생깁니다.

따라서 동일 선상 위치 식별은 동시 곡선에 대한 검색으로 다시 진술될 수 있습니다.

에 의해 매개 변수화 된 형상이 주어지 {\displaystyle (a_{1},...,a_{t})} 면 형상 공간이라는 집합의 값을 취 S 하면 Hough 변환을 형상 감지를 위한 최대 가능성 추정의 한 형태로 S 형상 공간에 대한 이미지 공간의 확률 분포의 역 변환으로 해석할 수 있습니다.

Hough 변환은 기본적으로