허프 변환
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
허프 변환은 이미지 내에서 특정 모양을 감지하는 데 사용되는 컴퓨터 비전 기술이다. 1962년 처음 개발되어 거품 상자 사진의 기계 분석에 적용되었으며, 직선, 원, 타원 등 다양한 형태를 찾을 수 있도록 발전했다. 허프 변환은 이미지 공간을 파라미터 공간으로 변환하여, 특정 형태에 해당하는 파라미터 값들을 찾아낸다. 이러한 변환을 통해 이미지의 노이즈에 강건하며, 부분적으로 가려진 형태도 감지할 수 있다. 일반화된 허프 변환은 복잡한 형태 감지에 활용되며, 커널 기반 허프 변환과 같은 변형을 통해 성능을 개선하기도 한다. 하지만, 파라미터 수가 많아질수록 효율성이 감소하고, 입력 데이터의 품질에 크게 의존하는 한계를 지닌다.
더 읽어볼만한 페이지
| 허프 변환 | |
|---|---|
| 개요 | |
| 종류 | 특징 추출 |
| 분야 | 컴퓨터 비전, 이미지 처리 |
| 개발자 | 폴 허프 |
| 개발일 | 1962년 |
| 상세 정보 | |
| 목적 | 이미지에서 단순한 모양(직선, 원, 타원 등) 감지 |
| 작동 원리 | 파라미터 공간에서 투표를 통해 모양의 존재 여부 결정 |
| 장점 | 이미지의 노이즈나 가려짐에 강건함 여러 모양을 동시에 감지 가능 |
| 단점 | 계산 비용이 높음 파라미터 공간의 해상도에 따라 성능이 달라짐 |
| 응용 분야 | 차량 번호판 인식 얼굴 인식 의료 영상 분석 자율 주행 |
| 변환 과정 | |
| 1단계 | 에지 검출 (캐니 에지 검출기 등 사용) |
| 2단계 | 파라미터 공간 설정 (예: 직선의 경우 기울기-절편 공간) |
| 3단계 | 각 에지 점에 대해 파라미터 공간에 투표 |
| 4단계 | 누적된 투표 결과에서 지역 최대값을 찾아 모양 결정 |
| 추가 정보 | |
| 일반화된 허프 변환 | 임의의 모양 감지에 사용 |
| 확률적 허프 변환 | 계산 효율성을 높임 |
2. 역사
허프 변환은 1959년 폴 허프(Paul Hough)가 거품 상자 사진의 기계 분석을 위해 처음 고안하였으며, 1962년 "복잡한 패턴을 인식하기 위한 방법 및 수단"이라는 이름으로 미국 특허를 받았다. 초기 허프 변환은 직선에 대한 기울기-절편 매개변수를 사용했기 때문에 변환 공간이 무한대가 되는 문제가 있었다.
허프 변환이 현대적 형태로 발명된 과정은 2009년 P. E. Hart의 논문에 자세히 나와 있다.[3]
[3]
2. 1. 초기 역사 (1960년대 ~ 1970년대)
허프 변환은 1962년 미국 특허("Method and Means for Recognizing Complex Patterns"「복잡한 패턴을 인식하는 수법」)를 얻었으며, 처음에는 거품 상자 사진의 기계 분석을 위해 발명되었다. 이 특허는 직선을 기울기와 절편으로 매개변수화하는 방법을 담고 있었는데, 기울기가 무한대가 될 수 있어(세로축에 평행한 경우) 변환 공간이 무한대가 될 수 있다는 문제점이 있었다.오늘날 보편적으로 사용되는 로-세타(r, θ) 매개변수화는 이러한 문제점을 해결하여 어떤 경우에도 적용 가능하다. 이는 1972년 Duda와 Hart의 논문에서 처음 기술되었다.[1] 이 로-세타 매개변수화는 1930년대부터 라돈 변환에 이미 표준으로 사용되었다.
O'Gorman과 Clowes의 변형은 1976년에 발표되었다.[2]
참고 문헌
2. 2. 발전과 응용 (1980년대 ~ 현재)
허프 변환은 1962년에 "복잡한 패턴을 인식하는 수법"(Method and Means for Recognizing Complex Patterns)이라는 이름으로 미국 특허를 받았다. 이 특허는 직선을 기울기와 절편으로 매개변수화했는데, 기울기가 무한대가 될 수 있어(세로축에 평행한 경우) 변환 공간이 무한대가 되는 문제점이 있었다.오늘날 널리 사용되는 로-세타(ρ, θ) 매개변수화는 1972년 Duda와 Hart의 논문에서 제시되었다.[1]
: Duda, R. O. and P. E. Hart, "Use of the Hough Transformation to Detect Lines and Curves in Pictures," ''Comm. ACM, Vol. 15'', pp. 11–15 (January, 1972).
이는 적어도 1930년대부터 라돈 변환에 이미 표준으로 사용되었다.[1]
O'Gorman과 Clowes는 1976년 논문에서 특징점들의 동일선상 성질을 이용해 그림의 가장자리를 찾는 방법을 제안했다.[2]
: Frank O'Gorman, MB Clowes: Finding Picture Edges Through Collinearity of Feature Points. IEEE Trans. Computers 25(4): 449-456 (1976)
허프 변환이 어떻게 발명되었는지에 대한 자세한 내용은 2009년 Hart의 논문에 나와 있다.[3]
3. 이론
허프 변환은 이미지 공간의 점들을 매개변수 공간으로 변환하여 직선, 원 등의 형태를 찾는 기법이다.
평면 위의 점 (xi, yi)를 지나는 모든 직선은 그림 1과 같이 표시할 수 있으며, 식 xcosθ + ysinθ = r ([식 1])로 표현할 수 있다. [그림 2]와 [식 1]을 보면 x와 y는 변수, θ와 r은 상수이며, θ의 범위는 [0,π]이다.
[식 1]에서 점 (x, y)를 지나는 무수히 많은 직선을 표현할 때, x와 y는 상수가 되고 θ와 r은 변수가 된다. 이 때 θ와 r을 축으로 하는 평면에서 [식 1]은 사인 곡선과 같은 형태를 띈다.
[그림 3]의 곡선 a는 (x0, y0)를 지나는 모든 직선을 나타낸다. 여러 점이 있을 경우, 각 점은 r, θ 평면 상에서 곡선을 형성한다. 이 곡선들의 교점은 여러 점이 하나의 직선 위에 있음을 의미한다. 즉, n개의 곡선이 한 점에서 만나면 n개의 점이 하나의 직선 위에 있다는 뜻이다.
이러한 과정을 통해, 이미지의 "특징점"을 가장 많이 통과하는 직선을 결정할 수 있다. 즉, 해당 이미지에 가장 잘 맞는 직선을 찾는 것이다.
허프 변환은 최대 우도 추정으로 해석될 수 있는데, 이는 이미지 공간의 확률 분포를 형태 공간으로 변환하는 역변환으로 볼 수 있다.[8] 구체적으로, 허프 변환은 근사 나이브 베이즈 분류기 추론을 수행하며, 형태 공간에서 로그 우도의 피크를 선택하여 최대 우도 추정을 수행한다.[8]
어떤 점을 잡든지, 그 점을 통과하는 직선은 무한히 존재하며, 각각이 다양한 방향을 향한다. 표준적인 허프 변환에서는, 하나의 직선을 두 개의 파라미터 ''r'' 및 ''θ''로 나타낸다. ''r''은 원점에서 문제의 직선에 그은 법선의 길이, ''θ''는 그 법선과 x축 사이의 각도를 나타낸다. 이와 같이 표현하면, 직선의 방정식은 다음과 같다.
:
따라서, 이미지 상의 모든 직선에, (''r, θ'')의 짝을 대응시킬 수 있다. 이고 이거나, 혹은 이고 이면, 어떤 직선에 대한 (''r, θ'')의 짝은 유일하게 결정된다. 바꿔 말하면, ''θ''에 직각이고, 원점에서 ''r''의 거리에 있는 것으로 직선을 표현하는 것이다. (''r, θ'')의 짝의 집합이 이루는 평면을, "허프 공간"이라고 부르기도 한다. 이러한 표현 방식을 취한다는 점에서, 허프 변환은 라돈 변환과 개념적으로 매우 가깝다.[20]
3. 1. 직선 검출
한 평면 위에 놓여 있는 점들의 집합 P에서 원소 (xi, yi)를 지나는 모든 직선은 그림 1과 같이 표시할 수 있다.
어떤 점을 지나는 직선은 다음 식 xcosθ + ysinθ = r 로 표시될 수 있다. 위의 [그림 2] 그래프와 [식 1]을 보면 x와 y는 변수, θ와 r은 상수임을 알 수 있다. (기본적으로 θ 의 범위는 [0,π]이다. 그래야만 직선이 유일하게 결정되기 때문이다.)
디지털 이미지의 자동 분석에서 직선을 검출하는 경우가 자주 발생한다. 허프 변환의 목적은 매개변수화된 이미지 객체 집합에 대해 명시적인 투표 절차를 수행하여 가장자리 점을 객체 후보로 그룹화하는 것이다.[6] 허프 변환의 가장 간단한 경우가 직선 검출이다.
일반적으로 직선은 매개변수 공간에서 점 (''b'', ''m'')으로 표현될 수 있다. 그러나 수직선은 기울기 매개변수 ''m''의 무한대 값을 발생시키는 문제를 야기한다. 따라서 계산상의 이유로 Duda와 Hart[6]는 헤세 노멀 폼을 사용할 것을 제안했다.
:
여기서 는 원점에서 직선까지의 거리이고, 는 축과 원점을 연결하는 선 사이의 각도이다.
따라서 이미지의 각 선에 쌍 를 연결하는 것이 가능하다. 평면은 때때로 2차원 직선 집합에 대한 ''허프 공간''이라고 불린다. 이 표현은 허프 변환을 2차원 라돈 변환에 개념적으로 매우 가깝게 만든다.[7]
평면에 주어진 ''단일 점''에 대해, 해당 점을 통과하는 ''모든'' 직선 집합은 (''r'', ''θ'') 평면에서 해당 점에 고유한 사인파에 해당한다. 직선을 형성하는 두 개 이상의 점 집합은 해당 선에 대한 (''r'', ''θ'')에서 교차하는 사인파를 생성한다. 따라서 공선점 감지 문제는 동시 곡선을 찾는 문제로 변환될 수 있다.
어떤 점을 잡든지, 그 점을 통과하는 직선은 무한히 존재하며, 각각이 다양한 방향을 향한다. 이것이 허프 변환의 기본 원리이다. 허프 변환의 목적은, 이러한 직선들 중에서, 이미지의 "특징점"을 가장 많이 통과하는 것을 결정하는 데 있다. 즉, 해당 이미지에 가장 잘 맞는 직선을 찾는 것이다.
두 점이, 다양한 직선들 중, 동일한 직선 위에 놓여 있다는 것을 명확히 하기 위해서는, 직선과 직선 사이의 비교가 가능하도록 직선을 표현할 필요가 있다. 표준적인 허프 변환에서는, 하나의 직선을 두 개의 파라미터로 나타낸다. 파라미터는 통상적으로 ''r'' 및 ''θ''라고 불리며, 각각 원점에서 문제의 직선에 그은 법선의 길이와 각도를 나타낸다. 이와 같이 표현하면, 직선의 방정식은 다음과 같다.
:
따라서, 이미지 상의 모든 직선에, (''r, θ'')의 짝을 대응시킬 수 있다. 이고 이거나, 혹은 이고 이면, 어떤 직선에 대한 (''r, θ'')의 짝은 유일하게 결정된다. 바꿔 말하면, ''θ''에 직각이고, 원점에서 ''r''의 거리에 있는 것으로 직선을 표현하는 것이다. (''r, θ'')의 짝의 집합이 이루는 평면을, "허프 공간"이라고 부르기도 한다. 이러한 표현 방식을 취한다는 점에서, 허프 변환은 라돈 변환과 개념적으로 매우 가깝다.[20]
평면 상의 한 점을 통과하는 직선은 무한히 존재한다. 문제되는 점의 이미지 상에서의 좌표를 라고 하자. 이 점을 통과하는 모든 직선은, 다음 식을 따른다.
:
이는 (''r, θ'') 평면 상의 하나의 정현 곡선에 해당하며, 이미지 상의 점이 결정되면 유일하게 결정된다. 두 점에 대응하는 곡선을 겹쳐서 그렸을 경우, 허프 공간 내에서 두 곡선이 교차하는 점은, 이 두 점을 동시에 통과하는 직선에 대응한다. 일반화하면, (이미지 상에서의) 직선 상의 점의 집합은, 해당 직선에 대응하는 허프 공간 내의 한 점에서 교차하는 정현 곡선의 집합을 생성한다.
[그림 3]에서 보는 곡선 a는 (x0,y0)를 지나는 모든 선들을 표현한다. 여러 개의 점이 있을 경우 각각의 점은 [그림 3]와 같은 r,theta평면 상에서 곡선들을 갖게 될 것이다.
(x0,y0)를 지나는 모든 선들이 r,theta평면에서 하나의 곡선으로 표현된다.
(x1,y1)를 지나는 모든 선들이 r,theta평면에서 또 하나의 곡선으로 표현된다.
(x2,y2)를 지나는 모든 선들이 r,theta평면에서 또 하나의 곡선으로 표현된다.
...
(xi,yi)를 지나는 모든 선들이 r,theta평면에서 또 하나의 곡선으로 표현된다.
r,theta평면에서 곡선들이 있는데, 이 곡선들의 교점은 두 곡선이 공통된 값을 갖는다는 것을 의미한다. 예를 들어 곡선 a1 과 곡선 a2가 있다고 가정하고, 각 식을 정리하면 다음과 같다.
- a1: x1*cosθ + y1*sinθ = r
- a2: x2*cosθ + y2*sinθ = r
이 두 곡선이 교점이 생겼다는 것은 (x1,y1)을 지나는 직선들 중 하나의 직선과 (x2,y2)을 지나는 직선들 중 하나의 직선이 같아졌다는 것을 뜻한다. 즉 점(x1,y1)과 점(x2,y2) 은 하나의 같은 점 선 위에 있다는 것이다.
그러면 만약 곡선 3개가 한 점에서 만났다는 것은 점 3개가 하나의 직선 위에 있다는 것을 뜻한다.
한마디로 말하면, n개의 곡선이 한 점에서 만나면 n개의 점이 하나의 직선 위에 있다는 것을 뜻한다.
즉, 해당 교점의 좌표(r,theta평면 위의)를 가지고 (xy평면에)직선을 그리면 n개의 점을 가지고 있는 직선을 그릴 수 있는 것이다. 위와 같은 과정을 통해 우리는 어떤 선 위에 점이 몇 개 올라와 있는지 그 개수를 파악할 수 있게 되었다.
코딩할 때에는 이미지가 디지털 이미지와 같이 정수로 끊어지기 때문에 어떤 픽셀에서 몇 번 겹쳐지는가에 대해서 파악하기 쉽다.
3. 2. 확률적 해석
허프 변환은 이미지 공간의 확률 분포를 형태 공간으로 변환하는 역변환으로 해석할 수 있으며, 형태 감지를 최대 우도 추정으로 해석할 수 있다. 이때 형태 공간은 주어진 형태를 로 매개변수화하고, 집합 에서 값을 취한다.구체적으로, 허프 변환은 근사 나이브 베이즈 추론을 수행한다. 형태 공간에 균일한 사전 확률을 가정하고, 부분적으로 가려진 형태를 감지하기 위해 긍정적인 증거만 고려하고 모든 부정적인 증거는 무시한다.
형태 공간에서 로그 우도를 가산 상수까지 더한다. 이미지 공간의 모든 픽셀이 독립적인 증거를 제공하여 우도가 곱해지고, 로그 우도가 더해진다는 "나이브 베이즈" 가정을 따른다. 가산 상수의 자유는 형태 공간의 "배경 픽셀"에 대해 아무런 연산을 수행하지 않도록 한다.
마지막으로, 형태 공간에서 로그 우도의 피크를 선택하여 최대 우도 추정을 수행한다.[8]
3. 3. 원 및 기타 형태 검출
허프 변환은 디지털 이미지 분석에서 직선, 원, 타원과 같은 간단한 모양을 감지하는 데 사용되는 기법이다. 이미지 데이터나 가장자리 감지의 결함으로 인해 발생할 수 있는 누락된 점이나 잡음 문제를 해결하는 데 유용하다.원 허프 변환 알고리즘은 다음과 같은 단계를 거쳐 원을 감지한다.
1. 2차원 누산기 공간을 만들고 각 셀을 0으로 초기화한다.
2. 이미지의 각 가장자리 점 (i, j)에 대해, 원의 방정식 을 사용하여 원의 중심이 될 수 있는 모든 셀 (a, b)의 값을 증가시킨다.
3. 각 가능한 a 값에 대해 방정식을 만족하는 모든 가능한 b 값을 찾는다.
4. 누산기 공간에서 국지적 최대값을 찾는다. 이 셀들이 감지된 원을 나타낸다.
만약 찾으려는 원의 반지름을 미리 알지 못하는 경우에는 3차원 누산기 공간을 사용하여 임의의 반지름을 가진 원을 검색할 수 있다. 하지만 이는 계산 비용이 더 많이 든다. 이 방법은 원의 영역이 누산기 공간 내에 충분히 남아 있는 한, 누산기 공간의 일부가 아닌 원도 감지할 수 있다.
허프 변환은 거리 영상 또는 3차원 점 구름에서 3차원 객체(평면 및 원통)를 감지하는 데에도 사용될 수 있다. 평면 감지를 위한 고전적인 허프 변환의 확장은 평면의 방정식 를 이용하며, 3차원 허프 공간을 사용한다. 하지만 이 방법은 수평에 가까운 평면은 잘 감지하지만, 수직에 가까운 평면은 감지 성능이 저하되는 문제가 있다.[14]
일반화된 평면 감지를 위해서는 평면을 법선 벡터 (구면 좌표 사용)과 원점으로부터의 거리 로 매개변수화하여 3차원 허프 공간을 생성한다. 각 점은 허프 공간에서 사인 곡선 표면에 투표하고, 이러한 표면들의 교차점이 평면의 존재를 나타낸다.[15]
허프 변환은 2단계 접근 방식을 통해 점 구름에서 원통형 객체를 찾는 데에도 사용된다. 첫 번째 단계는 원통의 방향을 찾고, 두 번째 단계는 위치와 반경을 찾는다.[17]
허프 변환은 원뿐만 아니라 매개변수로 표현할 수 있는 모든 형태에 적용할 수 있다. 예를 들어, 타원은 중심과 반지름을 나타내는 세 개의 매개변수를 사용하여 3차원 허프 공간에서 찾을 수 있다. 더 복잡한 도형에는 일반화 허프 변환이 사용되며, 이는 템플릿 매칭과 유사한 방식으로 작동한다.
4. 구현
허프 변환에 사용되는 원 데이터는 일반적으로 "생" 이미지이며, 보통 윤곽선 감지를 수행한다. 따라서 변환되는 점의 집합이 반드시 모든 이미지의 적절한 윤곽선이라고 할 수는 없다. 변환 처리는 임의의 수의 "빈(bin)"(구분)으로 양자화되며, 각 빈은 이미지의 윤곽선이 될 수 있는 하나의 직선을 근사적으로 나타낸다. 중요한 점(또는 "특징점") 각각은 자신을 통과하는 직선을 나타내는 빈의 집합에 "투표"한다. 모든 특징점에 대해 "투표"를 실행하면(각 빈의 값을 단순히 더해나감) 하나의 배열이 생성되며, 그 배열로부터 원래 이미지 데이터에 가장 잘 맞는 직선을 얻을 수 있다.
배열에서 큰 값을 갖는 빈을 찾아내면, 일련의 적절한 직선과 그 (근사적인) 기하학적 정의를 구할 수 있다. "피크"를 구하는 가장 간단한 방법은 어떤 임계값을 적용하는 것이지만, 경우에 따라 다른 방법을 사용하면 더 좋은 결과를 얻을 수 있다. 이 방법으로는 직선의 길이 정보를 얻을 수 없으므로, 다음 단계에서 어떤 직선의 어떤 부분이 이미지에 해당하는지 찾아내야 한다.
5. 변형 및 확장
허프 변환은 다양한 형태로 변형 및 확장되어, 단순한 직선 검출을 넘어 더 복잡한 형태를 찾는 데 사용된다.
O'Gorman과 Clowes는 이미지 강도의 국부 기울기를 이용하여 선을 감지하는 방법을 개선했다. 이 방법은 기울기 방향을 20° 이내로 추정하여 계산 시간을 줄이고, 실제 선에 해당하는 스파이크(뾰족한 부분)의 가시성을 향상시킨다.[1]
커널 기반 허프 변환(KHT)은 방향성 타원 가우시안 커널을 사용하여 투표함으로써 성능을 향상시키고 가짜 선 감지에 대한 변환을 더 강력하게 만든다.[10]
3차원 커널 기반 허프 변환(3DKHT)은 평면 영역에 대한 빠른 허프 변환 투표 전략을 기반으로 하며, 대규모 데이터 세트에서 평면 특징을 빠르게 감지하는 데 사용될 수 있다.[11]
일반화된 허프 변환은 매개변수로 표현할 수 있는 모든 모양을 찾는 데 사용될 수 있다.[12] 예를 들어, 원은 중심과 반지름을 나타내는 세 개의 매개변수를 사용하여 3차원 허프 공간에서 찾을 수 있다. 더 복잡한 모양의 경우, 일반화된 허프 변환[13]이 사용되며, 특징은 미리 정의된 조회 테이블을 사용하여 모양의 특정 위치, 방향 및/또는 크기에 대해 투표할 수 있다.
5. 1. 기울기 정보 활용
O'Gorman과 Clowes는 이미지 강도의 국부 기울기가 가장자리에 수직이라는 점을 이용하여 선을 감지하는 개선된 방법을 제안했다. 가장자리 감지는 일반적으로 강도 기울기 크기를 계산하므로, 기울기 방향은 부수적으로 얻어진다. 좌표 (''x,y'')가 선 위에 있다면, 국부 기울기 방향은 해당 선의 ''θ'' 매개변수를 제공하고, ''r'' 매개변수는 즉시 얻어진다.[1] 기울기 방향은 20° 이내로 추정할 수 있으며, 이는 정현파 추적을 180°에서 약 45°로 단축시킨다. 이는 계산 시간을 줄이고, 불필요한 투표 수를 줄여 이미지에서 실제 선에 해당하는 스파이크의 가시성을 향상시킨다.[1]5. 2. 커널 기반 허프 변환 (KHT)
Fernandes와 Oliveira는[10] 비교적 큰 이미지(예: 1280×960)에서도 소프트웨어 구현을 통해 실시간 성능을 달성할 수 있는 허프 변환을 위한 향상된 투표 방식을 제안했다. 커널 기반 허프 변환(KHT)은 Duda와 Hart가 제안한 것과 동일한 파라미터화를 사용하지만, 대략적으로 공선형인 픽셀 클러스터에서 작동한다. 각 클러스터에 대해, 해당 클러스터와 관련된 최적 선에 대한 불확실성을 모델링하는 방향성 타원 가우시안 커널을 사용하여 투표가 이루어진다. 이 접근 방식은 투표 방식의 성능을 크게 향상시킬 뿐만 아니라 훨씬 더 깔끔한 누산기를 생성하며 가짜 선 감지에 대해 변환을 더 강력하게 만든다.5. 3. 3차원 커널 기반 허프 변환 (3DKHT)
림버거(Limberger)와 올리베이라[11]는 샘플 수에 대해 의 비용으로 구성된 정형적 기법을 제안했으며, 비교적 큰 데이터 세트(3.4 GHz CPU에서 최대 개 지점)에 대해 실시간 성능을 달성했다. 이는 커널 기반 허프 변환(KHT)에서 영감을 얻어 평면 영역에 대한 빠른 허프 변환 투표 전략을 기반으로 한다. 이 3차원 커널 기반 허프 변환(3DKHT)은 대략 공면 샘플의 클러스터를 분할하는 빠르고 강력한 알고리즘을 사용하며, 삼변량 가우시안 커널을 사용하여 () 구형 누산기에 개별 클러스터(개별 샘플 대신)에 투표한다. 이 접근 방식은 RHT 및 RANSAC과 같은 포인트 클라우드에서 평면 감지를 위한 기존의 (비결정론적) 기술보다 수십 배 빠르며 데이터 세트 크기에 따라 더 잘 확장된다. 이는 대규모 데이터 세트에서 평면 특징의 빠른 감지가 필요한 모든 응용 분야에 사용될 수 있다.5. 4. 일반화된 허프 변환
위에서 설명한 변환 버전은 직선을 찾는 데만 적용되지만, 유사한 변환을 사용하여 일련의 매개변수로 표현할 수 있는 모든 모양을 찾을 수 있다. 예를 들어, 원은 중심과 반지름을 나타내는 세 개의 매개변수 집합으로 변환될 수 있으므로 허프 공간은 3차원이 된다. 임의의 타원과 곡선도 이와 같은 방식으로 찾을 수 있으며, 매개변수 집합으로 쉽게 표현할 수 있는 모든 모양도 마찬가지이다.[12]평면에서 더 복잡한 모양(즉, 2D 공간에서 분석적으로 표현할 수 없는 모양)의 경우, 일반화된 허프 변환[13]이 사용되며, 이를 통해 특징은 미리 정의된 조회 테이블을 사용하여 모양의 특정 위치, 방향 및/또는 크기에 대해 투표할 수 있다. 허프 변환은 감지된 가장자리의 모든 픽셀로부터 기여를 누적한다. 위의 방법은 직선을 감지하는 데에만 유용하지만, 한 쌍의 매개변수로 표현할 수 있는 형태에 대해서는 모두 유사한 변환 방법을 적용할 수 있다. 예를 들어 (평면상의) 원은 중심과 반지름을 나타내는 세 개의 매개변수로 변환할 수 있으므로, 3차원 허프 공간을 사용하게 된다. 임의의 타원도 매개변수 쌍으로 쉽게 표현할 수 있으므로 마찬가지이다. 더 복잡한 도형에는 일반화 허프 변환이 사용된다. 이 방법은 미리 준비된 참조용 테이블을 이용하여, 특징점이 미리 준비된 형태에 대해 그 위치, 방향, 스케일링을 투표할 수 있도록 한 것으로, 템플릿 매칭에 가까운 방법이다.
6. 한계
허프 변환의 한 가지 흔한 변형은 세부 사항을 상세히 설명하는 것이다. 즉, 한 단계에서 가장 높은 개수를 가진 빈을 찾는 것은 다음 단계에서 검색되는 값의 범위를 제한하는 데 사용될 수 있다.[19]
허프 변환을 위한 고차원 매개변수 공간은 속도가 느릴 뿐만 아니라, 사전 고려 없이 구현될 경우 사용 가능한 메모리를 쉽게 초과할 수 있다. 프로그래밍 환경에서 가상 메모리를 통해 사용 가능한 메모리 공간보다 큰 배열 할당을 허용하더라도, 누산기 배열이 임의 접근 방식으로 사용되어 인덱스에서 인덱스로 건너뛸 때 연속된 메모리에 거의 머물지 않으므로 필요한 페이지 스와핑 횟수가 매우 많아진다.[19]
800x600 이미지에서 타원을 찾는 작업을 생각해 보자. 타원의 반지름이 주축을 따라 정렬되어 있다고 가정하면 매개변수 공간은 4차원이다. (''x'', ''y'')는 타원의 중심을 정의하고, ''a''와 ''b''는 두 반지름을 나타낸다. 중심이 이미지 내 어디든 있을 수 있도록 허용하면 0
이렇게 구상된 프로그램은 충분한 메모리를 할당받지 못할 가능성이 크다. 이것이 문제를 해결할 수 없다는 의미는 아니지만, 누산기 배열의 크기를 제한하여 실행 가능하게 만드는 새로운 방법을 찾아야 한다는 의미이다. 예를 들어 다음과 같은 방법이 있다.[19]
위의 예시에 이러한 제약 조건 중 처음 세 개만 적용하면 누산기 배열의 크기가 거의 1000배 감소하여 현대 컴퓨터의 메모리에 훨씬 더 적합한 크기로 줄어든다.[19]
허프 변환은 많은 수의 투표가 올바른 빈에 속하여 배경 잡음 속에서 해당 빈을 쉽게 감지할 수 있을 때만 효율적이다. 이는 빈이 너무 작아서는 안 된다는 의미이며, 그렇지 않으면 일부 투표가 인접한 빈에 떨어져 주요 빈의 가시성을 감소시키기 때문이다.[19]
또한, 파라미터 수가 많을 때(즉, 일반적으로 세 개 이상의 파라미터를 사용하여 허프 변환을 사용할 때), 단일 빈에 투표된 평균 수는 매우 낮으며, 이미지의 실제 도형에 해당하는 빈이 반드시 주변 빈보다 훨씬 더 많은 수의 투표를 갖는 것처럼 보이지 않는다. 복잡성은 각 추가 파라미터에 대해 의 비율로 증가하며, 여기서 는 이미지 공간의 크기이고 은 파라미터의 수이다. (Shapiro and Stockman, 310) 따라서 허프 변환은 선이나 원 이외의 것을 감지하는 데 매우 신중하게 사용해야 한다.[19]
마지막으로, 허프 변환의 효율성은 입력 데이터의 품질에 크게 의존한다. 허프 변환이 효율적이려면 가장자리가 잘 감지되어야 한다. 잡음이 있는 이미지에 대한 허프 변환의 사용은 매우 섬세한 문제이며 일반적으로 노이즈 제거 단계를 먼저 사용해야 한다. 레이더 이미지의 경우와 같이 이미지에 스페클이 손상된 경우, 라돈 변환은 합산을 통해 노이즈를 감쇠시키기 때문에 때때로 선을 감지하는 데 선호된다.[19]
참조
[1]
서적
Computer Vision
Prentice-Hall, Inc.
2001
[2]
논문
Extending the Hough transform to recognize and approximate space curves in 3D models
2024-09-01
[3]
간행물
Use of the Hough Transformation to Detect Lines and Curves in Pictures
Comm. ACM
1972-01
[4]
특허
Method and means for recognizing complex patterns
1962-12-18
[5]
간행물
Machine Analysis of Bubble Chamber Pictures
http://inspirehep.ne[...]
Proc. Int. Conf. High Energy Accelerators and Instrumentation
1959
[6]
웹사이트
Use of the Hough Transformation to Detect Lines and Curves in Pictures
http://www.ai.sri.co[...]
Artificial Intelligence Center
1971-04
[7]
웹사이트
A short introduction to the Radon and Hough transforms and how they relate to each other
http://citeseerx.ist[...]
[8]
서적
Procedings of the British Machine Vision Conference 1990
British Machine Vision Association
1990
[9]
웹사이트
Hough Transform for Straight Lines
http://www.cvmt.dk/e[...]
2011-12-16
[10]
논문
Real-time line detection through an improved Hough transform voting scheme
[11]
논문
Real-Time Detection of Planar Regions in Unorganized Point Clouds
https://lume.ufrgs.b[...]
[12]
논문
A general framework for subspace detection in unordered multidimensional data
[13]
논문
Generalizing the Hough transform to detect arbitrary shapes
[14]
간행물
3D Building Model Reconstruction from Point Clouds and Ground Plans
https://pdfs.semanti[...]
International Archives of the Photogrammetry, Remote Sensing and Spatial Information Sciences
2001-10-22
[15]
간행물
Automatic reconstruction of industrial installations – Using point clouds and images
http://www.ncg.knaw.[...]
Publications on Geodesy 62, Delft
2008-12-01
[16]
논문
Global Correlation Clustering Based on the Hough Transform
[17]
간행물
Efficient hough transform for automatic detection of cylinders in point clouds
https://pdfs.semanti[...]
Proceedings of the 11th Annual Conference of the Advanced School for Computing and Imaging (ASCI '05)
2005-06
[18]
서적
Object recognition supported by user interaction for service robots
[19]
웹사이트
Image Transforms - Hough Transform
http://homepages.inf[...]
Homepages.inf.ed.ac.uk
2009-08-17
[20]
특허
http://www.j-tokkyo.[...]
国際電気通信基礎技術研究所
[21]
보고서
即効型地域新生コンソーシアム研究開発 柔軟変形物ハンドリング用ビジョンチップの研究開発報告書
http://www.mint.se.r[...]
新エネルギー・産業技術総合開発機構
[22]
웹사이트
解説記事
http://www.mathworks[...]
MATLAB
[23]
웹사이트
ftp://59.67.107.52/S[...]
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com