허프 변환(Hough transform)은 이미지 분석, 컴퓨터 비전, 패턴 인식, 디지털 이미지 처리에서 사용되는 특징 추출 기법이다. 그 목적은 투표 절차를 통해 특정 모양 클래스에 속하는 객체의 불완전한 사례를 찾는 것이다. 이 투표 절차는 매개변수 공간에서 수행되며, 알고리즘이 명시적으로 구축한 누산기 공간에서 객체 후보가 국소 최댓값으로 얻어진다. 수학적으로는 평면에서의 라돈 변환(Radon transform)으로, 적어도 1917년부터 알려져 있었지만, 허프 변환은 특히 이미지 분석에서의 사용을 지칭한다.
고전적 허프 변환은 이미지에서 직선을 식별하는 데 초점을 맞췄지만, 이후 임의의 모양, 가장 일반적으로 원이나 타원의 위치를 식별하도록 확장되었다. 오늘날 보편적으로 사용되는 변환은 1972년 리처드 두다(Richard Duda)와 피터 하트(Peter Hart)가 발명했으며, 이들은 이를 폴 허프(Paul Hough)의 1962년 관련 특허에 따라 "일반화된 허프 변환"이라고 불렀다. 이는 데이나 H. 발라드(Dana H. Ballard)가 1981년 저널 논문 "임의 모양을 감지하도록 허프 변환 일반화"를 통해 컴퓨터 비전 커뮤니티에 널리 알려졌다.
역사
허프 변환은 1959년 폴 허프가 버블 챔버 사진의 기계 분석을 위해 처음 발명했다. 1962년 미국 특허 3,069,654로 특허를 받았으며, "복잡한 패턴 인식을 위한 방법 및 수단"이라는 이름으로 미국 원자력 위원회에 양도되었다. 이 특허는 직선에 대해 기울기-절편 매개변수화를 사용했는데, 기울기가 무한대가 될 수 있어 변환 공간이 무한해지는 문제가 있었다.
오늘날 보편적으로 사용되는 rho-theta 매개변수화는 1972년 리처드 두다와 피터 하트의 논문 "사진에서 선과 곡선을 감지하기 위한 허프 변환 사용"에서 처음 설명되었으며, ACM 커뮤니케이션즈에 게재되었다. 이 매개변수화는 적어도 1930년대부터 라돈 변환에서 이미 표준이었다. 프랭크 오고먼(Frank O'Gorman)과 M.B. 클로우스(M.B. Clowes)는 1976년 IEEE 트랜잭션스 온 컴퓨터에 "특징점의 공선성을 통한 그림 가장자리 찾기"라는 제목의 변형을 게재했다. 현대적 형태가 어떻게 발명되었는지에 대한 이야기는 피터 하트의 2009년 IEEE 시그널 프로세싱 매거진 기사 "허프 변환이 어떻게 발명되었는가"에 자세히 설명되어 있다.
이론
디지털 이미지의 자동 분석에서 직선, 원, 타원과 같은 단순한 모양을 감지하는 하위 문제가 자주 발생한다. 에지 검출기는 원하는 곡선 위의 이미지 점을 얻기 위한 전처리 단계로 사용될 수 있다. 그러나 이미지 데이터나 에지 검출기의 불완전성으로 인해 이상적인 모양과 잡음이 있는 에지 점 사이에 누락된 점이나 공간적 편차가 있을 수 있다. 허프 변환은 매개변수화된 이미지 객체 집합에 대해 명시적 투표 절차를 수행하여 이를 해결하며, 에지 점을 객체 후보로 그룹화할 수 있게 한다.
직선 감지
가장 단순한 경우는 직선 감지이다. 일반적으로 직선 y = mx + b는 매개변수 공간의 점 (b, m)으로 표현될 수 있지만, 수직선은 기울기 값이 무한대가 되어 문제가 발생한다. 두다와 하트는 헤세 정규형을 사용할 것을 제안했다: r = x cos(theta) + y sin(theta). 여기서 r은 원점에서 직선의 가장 가까운 점까지의 거리이고, theta는 x축과 원점을 그 가장 가까운 점에 연결하는 선 사이의 각도이다. 직선 위의 모든 벡터는 원점에서 길이 r의 선분에 수직이다. 교차점은 P0 = (r cos(theta), r sin(theta))에 있다. 직선 위의 임의의 점 P에 대해 벡터 P - P0는 P0에 직교해야 하며, (P - P0) dot P0 = 0을 강제하며, 이는 r(x cos(theta) + y sin(theta)) = r^2(cos^2(theta) + sin^2(theta))로 단순화된다.
알고리즘 및 투표 절차
실제로 허프 변환은 매개변수 공간을 누산기 배열로 이산화한다. 이미지의 각 에지 점에 대해 알고리즘은 해당 점을 통과하는 모양에 대응할 수 있는 모든 가능한 매개변수 값(예: 직선의 r과 theta)을 계산하고 해당 누산기 셀을 증가시킨다. 모든 점을 처리한 후 누산기의 국소 최댓값은 가능성 있는 모양 후보를 나타낸다. 이 투표 절차는 모양의 모든 점이 완벽하게 정렬될 필요가 없으므로 잡음과 누락된 데이터에 강건하다.
확장 및 응용
1981년 데이나 발라드가 도입한 일반화된 허프 변환은 기준점과 에지 방향 테이블을 사용하여 임의의 모양으로 기법을 확장한다. 이를 통해 직선, 원, 타원을 넘어 복잡한 모양을 감지할 수 있다. 이 변환은 자율 주행, 의료 영상, 산업 검사와 같은 분야에서 널리 적용되었다. Computer vision 시스템에서는 에지 검출 알고리즘과 결합되어 디지털 이미지 처리 파이프라인에서 객체를 식별하는 데 자주 사용된다. 라돈 변환에서의 수학적 기반은 이를 Machine learning 및 Artificial intelligence 응용 프로그램에서 사용되는 더 넓은 이미지 분석 기법과 연결한다.
한계 및 변형
고전적 허프 변환의 한계 중 하나는 특히 고차원 매개변수 공간에서의 계산 비용이다. 확률적 허프 변환과 허프 원 변환과 같은 변형이 효율성을 개선하기 위해 개발되었다. 확률적 버전은 에지 점의 하위 집합을 샘플링하여 계산을 줄이는 반면, 원 변환은 3차원 매개변수 공간(중심 x, 중심 y, 반지름)을 사용한다. 이러한 변형은 opencv와 같은 라이브러리에서 일반적으로 구현되며, Robotics 및 자율 주행 차량을 포함한 실시간 시스템에서 사용된다.
같이 보기
- radon-transform
- edge-detection
- Computer vision
- image-processing