Feature Extraction Lecture 4 에지 검출

Edge Detection 에지에 대한 정의 ? 에지에 대한 일반적인 정의는 명확하지 않음 컴퓨터 비전에서는 에지를 밝기 값이 급격하게 변하는 픽셀로 해석

Discontinuities B A C D A: Depth discontinuity: abrupt depth change in the world B: Surface normal discontinuity: change in surface orientation C: Illumination discontinuity: shadows, lighting changes D: Reflectance discontinuity: surface properties, markings

Illusory Edges 대부분의 알고리즘에서는 착시에 의한 에지 (Illusory edges) 검출 작업이 불가능 하다 Kanizsa Triangles 대부분의 알고리즘에서는 착시에 의한 에지 (Illusory edges) 검출 작업이 불가능 하다 이를 위해서는 영상 이외의 추가적인 정보를 활용하여야 한다 (인지 기반 군집화 기술 등)

Another One

Goal 영상에서 “주요한” 에지 성분들을 검출하는 알고리즘의 설계 “주요한”의 의미는 ? “주요한”의 의미는 에지 검출 알고리즘의 내부에서 매개변수에 의해 결정될 수 있음

Edgels 지역적 에지 (edge) 또는 에겔 (edgel, edge pixel)은 영상 내 작은 영역 안에서 픽셀 값의 급격한 변화로 정의 에겔은 이웃 영역 안에서 검출 가능하다는 의미 에겔이 윤곽석 (contour), 경계선 (boundary), 또는 직선 성분 (line)을 의미하지는 않음 에겔들로 부터 그러한 구조들이 만들어 질 수 있음 에겔이 갖는 특성은 방향 (Orientation) 크기/세기 (Magnitude) 위치 (Position)

Outline 1차 미분에 기반한 에지 검출기 Canny 에지 검출기 2차 미분에 기반한 에지 검출기 수학 이론 1x2, Roberts, Sobel, Prewitt Canny 에지 검출기 2차 미분에 기반한 에지 검출기 Laplacian, LOG / DOG 허프 변환 (Hough Transform)에 의한 검출-투표 (voting) 기반 Lines Circles Other shapes

Locating Edgels f(x) = step edge maximum 1st Derivative f ’(x) Rapid change in image => high local gradient => differentiation f(x) = step edge 1st Derivative f ’(x) maximum 2nd Derivative -f ’’(x) zero crossing

Reality

Properties of an Edge Original Orientation Orientation Position Magnitude

Quantitative Edge Descriptors 에지 방향 에지 법선 (Normal) – 밝기 값 변화가 최대로 일어나는 방향의 단위 벡터 에지 방향 – 에지 법선에 수직인 단위 벡터 에지 위치 에지가 검출된 영상 내의 위치 (에지 위치 표시를 위해 통상적으로 이진 영상 사용) 에지 세기/크기 지역적 명암 대비 또는 기울기와 관련됨 – 에지 법선 방향으로 얼마나 급격하게 밝기 값이 변화하는 가를 나타냄

Edge Degradation in Noise Increasing noise Ideal step edge Step edge + noise

Real Image

Edge Detection: Typical 잡음 억제 (Noise Smoothing) 진짜 에지 성분을 보존하면서 최대한 잡음 억제 백색 가우시안 잡음 (white Gaussian) 가정 에지 성분 개선 (Edge Enhancement) 에지 성분에 반응하는 필터 설계 : 필터 출력 값이 에지 픽셀에서는 높고 기타 픽셀에서는 낮도록 설계 에지 위치 결정 (Edge Localization) 어떤 픽셀이 에지 성분에 해당되고 어떤 픽셀이 잡음에 해당되는 지를 결정 1-픽셀 두께의 가늘고 긴 에지 검출 (nonmaximum suppression) 임계값을 설정하고 에지 필터의 출력과 임계값을 비교하여 에지 선언 (thresholding)

Edge Detection Methods 1st Derivative Estimate Gradient edge detection Compass edge detection Canny edge detector (*) 2nd Derivative Estimate Laplacian Difference of Gaussians Parametric Edge Models (*)

Gradient Methods F(x) Edge= sharp variation x F’(x) Large first derivative x

Gradient of a Function f 를 (x,y) 공간에서의 연속 함수 (continuous function)라 하면, (Dx, Dy) = x 와 y 방향으로의 함수 값의 변화량 (Dx, Dy) = 함수 f의 기울기 (gradient) 크기 (magnitude) : 방향 (orientation) : Q = 함수 f 가 최대로 변하는 방향 S = 함수 f의 변화량 Dx Dy q = tan-1 ( )

Geometric Interpretation But 영상 I(i,j) 는 연속 함수가 아니고 이산 함수 (discrete) Therefore 기울기 (gradient)에 대한 이산적 근사값 필요

Discrete Approximations df(x) dx = lim Dx 0 f(x + Dx) - f(x) Dx f(x) df(x) dx f(x) - f(x-1) 1 @ x-1 x Convolve with -1 1

In Two Dimensions Discrete image function I 미분 (Derivatives) 차분 (Differences) 1 -1 -1 1 DjI = DiI =

1x2 Example 1x2 Vertical 1x2 Horizontal Combined

Smoothing and Edge Detection 미분 연산은 매우 잡음에 민감한 연산 에지는 공간적으로 고주파 성분에 해당됨 에지 검출기는 잡음에 민감하고 잡음을 강화시키는 역할 평균 연산이 잡음을 억제시킴 공간적 평균 연산은 마스크를 이용하여 구현 가능 에지 검출 연산을 평균 (스므딩) 연산과 결합

Effect of Blurring Original Orig+1 Iter Orig+2 Iter Image Edges Thresholded Edges

Combining the Two 아래 마스크는 양 쪽 (위, 아래)의 평균을 차분하는 효과

Many Different Kernels 변수 마스크 (커널)의 크기 마스크에 할당된 가중치 1x2 커널 1 -1 -1 1 DjI = DiI =

Roberts Cross Operator 에지 방향에 대한 정보는 제공하지 않음 S = [ I(x, y) - I(x+1, y+1) ]2 + [ I(x, y+1) - I(x+1, y) ]2 or S = | I(x, y) - I(x+1, y+1) | + | I(x, y+1) - I(x+1, y) | 1 0 0 -1 0 1 -1 0 +

Sobel Operator -1 -2 -1 0 0 0 1 2 1 -1 0 1 -2 0 2 S1= S2 = 에지 크기 = -1 -2 -1 0 0 0 1 2 1 -1 0 1 -2 0 2 S1= S2 = S1, S2 represent response to the kernels. Not the kernel themselves 에지 크기 = 에지 방향 = S1 + S2 2 tan-1 S1 S2

Anatomy of the Sobel 2D 소벨 커널은 1D 연산으로 분할 가능 ! 평균 연산과 차분 연산의 결합 - + 1/4 2D 소벨 커널은 1D 연산으로 분할 가능 ! Explain how this is done. 1/4 평균 연산과 차분 연산의 결합

Prewitt Operator -1 -1 -1 0 0 0 1 1 1 -1 0 1 P1= P2 = Edge Magnitude = -1 -1 -1 0 0 0 1 1 1 -1 0 1 P1= P2 = P1, P2 represent response, not the kernels Edge Magnitude = Edge Direction = P1 + P2 2 tan-1 P1 P2

Large Masks What happens as the mask size increases?

Large Kernels 7x7 Horizontal Edges only 13x13 Horizontal Edges only

Compass Masks 나침반 방향에 맞추어진 8개의 마스크 사용Use eight masks aligned with the usual compass directions 반응값이 최대가 되는 마스크 선택 에지 방향의 선택된 마스크의 방향

Many Different Kernels Frei & Chen

Robinson Compass Masks -1 0 1 -2 0 2 0 1 2 -1 0 1 -2 -1 0 1 2 1 0 0 0 -1 -2 -1 2 1 0 1 0 -1 0 -1 -2 2 0 -2 -1 0 -1

Analysis of Edge Kernels 일반적으로, 3 x 3 크기의 마스크가 2 x 2 마스크 보다 좋은 성능을 보임 Prewitt2 와 Sobel 마스크가 다른 마스크에 비해 상대적으로 좋은 성능을 보임 잡음이 많은 영상에서는 3 x 3 보다 큰 마스크가 더 좋은 성능을 보임 크기가 큰 마스크에서는 중앙 위치에서 거리에 반비례하여 가중치를 할당하는 방식이 효과적임

Demo in Photoshop You may try different operators in Photoshop, but do your homework by programming … …

Prewitt Example Santa Fe Mission Prewitt Horizontal and Vertical Edges Combined

Edge Thresholding Global approach T=128 T=64 64 128 Edge Histogram See Haralick paper for thresholding based on statistical significance tests.

Non-Maximal Suppression 에지 검출기의 마스크 크기가 큰 경우에, 기울기를 구하기 위해 지역적인 마스크를 사용하기 때문에, 그리고 픽셀 값 자체의 문제 때문에 에지 검출기는 1-픽셀 두께의 결과를 만들지 못할 수 있다 중복 에지를 제거하여 위의 문제를 해결하는 방법은 ?

Non-Maximal Suppression 목표: 지역적 분석에 기초하여 군더더기 에지는 제거하고 최적 에지만 보존 아래 1-차원 영상과 크기가 9인 에지 마스크를 생각하자 : {-1 -1 -1 -1 0 1 1 1 1} Image Pixels Operator Response

Non-Maximal Suppression 스텝-에지 (step edge)에 대해 에지 검출기의 반응은 점진적 증가 또는 점진적 감소 현상을 보임 반응값이 지역적 최대가 아닌 경우에는 그 값을 영으로 셋팅 최대값 판정을 위한 적절한 지역적 이웃 픽셀은 ? 에지 방향에 위치하지 않아야 하며, 같은 에지 방향 (edges orientation)을 가지며, 같은 기울기 방향 (gradient direction = gradient sign)을 가져야 한다

Non-Maximal Suppression Algorithm: 1. In parallel, at each pixel in edge image, apply selection window W as a function of edge orientation: definitely consider these X don't consider these edges ? maybe consider these, depending on algorithm Window W ••••••••• Central Edge

Non-Maximal Suppression 2. Eliminate from further consideration all E(n,m), (n,m) in W, (n,m) ≠ (i,j) for which: sign E(n,m) ≠ sign E(i,j) {different gradient directions} or q (n,m) ≠ q (i,j) {different edge orientations} 3. Of the remaining edges, set E(i,j) = 0 if, for some (n,m) in W, |E(n,m)| >|E(i,j)| 4. Apply conventional edge amplitude thresholding, if desired. Many variations on the basic algorithm.

Canny Edge Detector 가장 많이 사용되는 에지 검출기 LF. Canny, "A computational approach to edge detection", IEEE Trans. Pattern Anal. Machine Intelligence (PAMI), vol. PAMI vii-g, pp. 679-697, 1986. 다음과 같은 에지 검출 기준에 따라 설계됨: Good detection. There should be a minimum number of false negatives and false positives. Good localization. The edge location must be reported as close as possible to the correct position. Only one response to a single edge. Cost function which could be optimized using variational methods

Basic Algorithm 가우시안 스무딩 (잡음 제거) 후 미분 연산이 에지 검출에 매우 효과적인 절차로 확인됨 Canny Algorithm 에지 크기와 에지 방향을 구하기 위해, 영상에 대한 스무딩 작업 후에 차분 연산 적용 가우시안 스무딩 + 2x2 차분 연산 ‘비-최대값 억제 절차’를 적용하여 영상 기울기가 최대인 픽셀들만 선택 ‘이력 임계 방법 (Hysteresis thresholding)’을 적용하여 연결된 에지 픽셀들 생성

Hysteresis Thresholding 두 개의 임계값 (high & low) 사용하여 에지 픽셀 결정 : 에지 세기가 임계값 high 보다 큰 픽셀은 에지 픽셀로 에지 세기가 임계값 low 보다 작은 픽셀은 에지가 아닌 픽셀로 에지 세기가 임계값 low 보다 크면서 이웃 픽셀이 에지 픽셀인 경우에는 에지 픽셀로 결정 점진적으로 (Iteratively) 에지 픽셀의 수가 증가됨 강한 에지 (strong edges) 에서 출발하여 에지가 성장됨 더 이상 에지 픽셀 수가 증가하지 않으면 반복 알고리즘에 사용되는 변수: s (width of Gaussian kernel) low threshold T1 high threshold T2

Canny Results s=1, T2=255, T1=1 I = imread(‘image file name’); BW1 = edge(I,'sobel'); BW2 = edge(I,'canny'); imshow(BW1) figure, imshow(BW2) ‘Y’ or ‘T’ junction problem with Canny operator

Canny Results s=1, T2=255, T1=220 s=1, T2=128, T1=1 s=2, T2=128, T1=1 M. Heath, S. Sarkar, T. Sanocki, and K.W. Bowyer, "A Robust Visual Method for Assessing the Relative Performance of Edge-Detection Algorithms" IEEE Transactions on Pattern Analysis and Machine Intelligence, Vol. 19, No. 12, December 1997, pp. 1338-1359. http://marathon.csee.usf.edu/edge/edge_detection.html

Edges from Second Derivatives 차분 연산은 영상에 대한 1차 미분을 근사화 f(x) = step edge GRADIENT METHODS 1st Derivative f’(x) maximum 2nd Derivative f’’(x) zero crossing

Second Derivatives 2차 미분 = 1차 미분의 변화량 1차 미분의 최대점 = 2차 미분의 영-교차점 1차 미분의 최대점 = 2차 미분의 영-교차점 이산 신호에 대해서는, 차분 연산이 미분 연산을 근사화 1차원 함수 : D f(i) = D f(i+1) - D f(i) 2 = f(i+1) - 2 f(i) - f(i-1) Mask:

Laplacian Operator 2차원 함수 f(x,y) : f(x,y)의 2차 편미분은 등방향성 (isotropic)을 갖지 않음 등방향성을 갖는 2차미분 연산자로 라플라시안 (Laplacian) 사용 : 라플라시안에 대한 2차원 이산 근사화 :

Example Laplacian Kernels 5x5와 9x9에 있어서 가장 이상적인 근사화는 아니지만 비교적 좋은 성능 보임

Example Application 5x5 Laplacian Filter 9x9 Laplacian Filter

Detailed View of Results

Interpretation of the Laplacian 1차원 이산 라플라시안 : 다시 쓰면 : -5를 끄집어 내면 : 라플라시안 = 중심 픽셀 (i,j) 의 값에서 이웃의 평균 픽셀 값을 뺀 후에 -5 를 곱한 값 이웃을 어떻게 정의 ? 그리고 평균 값 계산은 ? looks like a window sum

Enhancement using the Laplacian 라플라시안을 이용한 영상 화질 개선 (영상 선명화) : 픽셀 (i,j)이 평평한 영역의 가운데 또는 긴 램프 (ramp) 영역의 중간에 위치하면 : I-Ñ2I = I(I,j) 픽셀 (I,j)이 램프 영역의 아래 쪽 끝 또는 에지에 위치하면 : I-Ñ2I < I(I,j) 픽셀 (I,j)이 램프 영역의 위 쪽 끝 또는 에지에 위치하면 : I-Ñ2I > I(i.j) Effect is one of deblurring the image

Laplacian Enhancement Blurred Original 3x3 Laplacian Enhanced

Noise 2차 미분은 1차 미분과 같이 잡음을 증폭시키는 효과 문제점 : 스무딩 필터은 2차 미분 연산을 스무딩 연산과 결합하여 수행 문제점 : 최적의 스무딩 필터는 ? 주어진 크기 (smoothing scale)로 스무딩 한 후에 어떻게 밝기값 변화를 감지하나 ? 여러 크기 (multiple scales)로 스무딩하여 얻어진 결과들을 어떻게 결합하나 ? 스무딩 필터은 크기를 조정할 수 있어야 하고 가중치의 변화가 (있다면) 완만하고 영상에서 필터의 위치를 지정할 수 있어야 한다 위의 특성을 만족하는 필터는 가우시안 :

2D Gaussian Distribution 2차원 가우시안 분표: 가우시안 분포에 기초하여 폭이 s 에 의해 결정되는 가우시안 필터 구현 :

s Defines Kernel ‘Width’

Creating Gaussian Kernels 필터 마스크의 가중치는 가우시안 분포에서 구해짐 : 다시 쓰면 : 크기가 nxn 인 마스크의 각 위치 (I,j)에서 가중치 계산을 수행하며 (0,0) 위치에서는 가중치 1을 할당 k 는 값의 크기를 조정하는 W(i,j) = k * exp (- ) i2 + j2 2 s2 = exp (- ) i2 + j2 2 s2 W(i,j) k

Example s = 2. and n = 7 : 2 -3 -2 -1 1 2 3 i j

Example Plot of Weight Values 7x7 Gaussian Filter

Kernel Application 7x7 Gaussian Kernel 15x15 Gaussian Kernel

Why Gaussian for Smoothing 가우시안은 다음과 같은 특성을 가짐 가우시안과 가우시안을 회선 연산하면 결과 역시 가우시안 이러한 특성을 선형 크기 공간 (linear scale space) 이라 함 효율성 : 분리 가능

Why Gaussian for Smoothing 분리 가능

Ñ2G Filter Marr and Hildreth approach: 단계-2 의 수식을 다시 쓰면 : 1. Apply Gaussian smoothing using s's of increasing size: 2. Take the Laplacian of the resulting images: 3. Look for zero crossings. 단계-2 의 수식을 다시 쓰면 : 즉, 가우시안의 라플라시안의 필터 마스크로 사용하여 영상과 회선 연산 수행

Mexican Hat Filter Laplacian of the Gaussian Ñ2G 는 원주 상에서 대칭 값을 가짐 Ñ2G 는 멕시칸 모자 (Mexican-hat) 필터라고 함

s2 Controls Size s2 = 0.5 s2 = 1.0 s2 = 2.0

Kernels 17 x 17 5x5 휴면 비전 시스템의 망막 주변에서의 셀 (영상 수용체) 들의 분포와 비교 ?

Example 13x13 Kernel

Example 13 x 13 Hat Filter Thesholded Positive Thesholded Negative Zero Crossings

Scale Space 17x17 LoG Filter Thresholded Positive Zero Crossings Thresholded Negative Zero Crossings

Scale Space s2 = 2 s2 = 2 s2 =2 2 s2 = 4

Color Edge Detection 일반적인 방법 각 R, G, B 채널에서의 에지 검출 결과를 통합 각 채널에서의 차분 연산 결과를 통하여 에지 검출

Hierarchical Feature Extraction 대부분의 특징들은 기본 특징 (edges, corners, regions)을 적절히 결합하여 구성된다 그룹화 (grouping) : 어떤 기본 특징들을 결합하여 하나의 그룹을 형성할 것 인가 ? 비전 시스템의 중간단계 처리과정 (intermediate-level)에 해당됨 모델 적합 (Model Fitting): 그룹은 어떤 구조에 의해 가장 잘 설명될 수 있는가 ? 매우 단순한 문제를 생각하자 …..

From Edgels to Lines 지역적 에지 성분들이 주어진 상황에서 : 이들로부터 하나의 구조 (예를 들어, 직선)를 표현하기 위해서는 ? 에지 성분들을 직선들로 그룹화하는 방법은 ?

Edgels to Lines 지역적 에지 성분들이 주어지면 좀 더 긴 직선 성분을 구하는 방법은 개략적인 개념: 에지 방향 정보가 주어질 수도 있고 아닐 수도 있고 좀 더 긴 직선 성분을 구하는 방법은 개략적인 개념: 직선을 점으로 매핑하는 새로운 공간을 선정 각 에지 점에 대해 그 점을 통과하는 직선에 해당되는 점 (새로운 공간에서)에 투표 새로운 공간에서 많은 투표를 받은 점에 해당되는 직선을 선택 허프 변환 (Hough transform) 의 기본 개념은 에지점들을 그룹화하는 문제를 새로운 공간에서 피크점을 찾는 문제로 바꾸어 해석

Edgels to Lines 영상 공간에서 두 에지점 P(x,y) 와 P’(x’,y’) : 에지점 P=(x,y) 를 통과하는 직선은 y=mx + b, 물론 기울기와 절편 m 과 b를 적절히 선택해야 함 에지점 P’에 대하여도 동일한 방식 수식 y=mx + b 은 새로운 공간 (파라미터 공간, (m,b) 공간)에서 하나의 직선에 해당됨 P P ' L x y

Parameter Space 매개변수 공간에서 두 직선 L1과 L2의 교점 (m,b)는 (x,y) 공간에서 두 점 (x,y) 과 (x',y')을 통과하는 직선의 매개변수 (절편과 기울기)를 나타낸다 영상 공간에서 동일 직선 상에 놓인 에지점들이 많을수록 매개변수 공간에서는 더 많은 직선들이 같은 점을 교차하게 된다 b m b = -mx+y b’ = -m’x'+y' x,y; x',y' are fixed (m ,b ) L 1 2

General Idea 개략적 개념: (m,b) 허프-공간은 영상 공간의 직선을 점으로 나타내는 공간이다 허프-공간의 각 축 (m and b)을 적절한 간격으로 양자화 하여 2차원 배열을 만든다 영상 평면의 각 에지점에 대해 대응되는 허프 공간의 직선에 투표 진행한다 (직선에 해당되는 (m,b) 배열 요소들에게 투표)

Hough Transform Line Detection Algorithm: Hough Transform Quantize b and m into appropriate 'buckets'. Need to decide what’s ‘appropriate’ Create accumulator array H(m,b), all of whose elements are initially zero. For each point (i,j) in the edge image for which the edge magnitude is above a specific threshold, increment all points in H(m,b) for all discrete values of m and b satisfying b = -mj+i. Note that H is a two dimensional histogram Local maxima in H corresponds to colinear edge points in the edge image.

Quantized Parameter Space Quantization b m single votes two votes The problem of line detection in image space has been transformed into the problem of cluster detection in parameter space

Example 영상 평면에서 직선을 찾는 문제를 매개변수 공간에서 군집 검출 문제로 변환 Image Edges Accumulator Array Result

Problems 수직선의 기울기는 무한대 값을 갖는다 직선을 다른 형태의 매개변수로 표현 극 좌표계 (polar coordinate) 표현 y r = x cos q + y sin q r 2 r q 1 2 q 1 x

Why? (r,q) 은 매우 효율적인 매개변수 공간 : Small: only two parameters (like y=mx+b) Finite: 0 £ r £ Ö(row2+col2), 0 £ q £ 2p Unique: only one representation per line

Alternate Representation 영상공간의 한 점은 (r,q) 공간에서 사인 곡선 (sinusoid) 에 대응된다 (m,b) 공간에 적용되는 알고리즘과 동일한 알고리즘 적용 가능 r = x cos q + y sin r q 1 1 1 r = x cos q + y sin q 2 2 2 q 2 p

Example x y P = (4, 4) P = (-3, 5) 1 2 P r q ( r, q )

Real Example Image Edges Accumulator Array Result

Modifications 앞에서 설명한 알고리즘은 에지 위치 (i,j)에 대한 정보만 사용 에지 방향에 대한 정보는 ? 좀 더 구체적인 제약조건으로 활용 가능 ! 에지 방향 정보를 이용하여 q 값 예측 가능 예측된 q 값을 이용하면 영상 공간의 한 점이 허프 공간의 한 점에 대응된다 Image Origin is arbitrary The three edges have same (r, q)

Post Hough 허프 변환은 영상 공간에서의 위치 정보를 상실 : 따라서 영상공간에서의 추가적인 작업 필요 예를 들어, 연결된 성분 (connected components) 찾는 작업 Heikki Kälviäinen, Petri Hirvonen, L. Xu and Erkki Oja, “Probabilistic and nonprobabilistic Hough Transforms: Overview and comparisons”, Image and vision computing, Volume 13, Number 4, pp. 239-252, May 1995. both sets contribute to the same Hough maxima.

Hough Fitting 허프 공간에서 한 군집에 속한 에지들을 영상 공간에서 정렬시킨다 정렬된 x 값의 간격 검사 각 에지점을 q 만큼 회전 시킨다 회전된 에지점을을 x 좌표값에 따라 정렬시킨다 정렬된 x 값의 간격 검사 간격에 대한 임계값 “max gap”을 설정한다 정렬된 두 에지점의 x 좌표값의 차이가 임계값 “max gap” 보다 크면, 두 점을 분리하여 새로운 직선 성분 생성한다 각 직선 성분의 그룹에 포함된 에지점들을 모아서 직선 성분의 시작과 끝점을 구한다

Generalizations 허프 변환 기법은 직선 이외에도 임의의 매개변수를 갖는 커브에도 적용 가능 : 허프 변환의 성능은 매개변수에 대한 양자화 정도에 의해 결정된다 : 양자화 레벨 수가 너무 적은 경우 : 피크가 넓은 영역으로 나타남 양자화 레벨 수가 너무 많은 경우 : 피크가 잘 만들어지지 않음 커브를 표현하는 매개변수의 개수에 따라 매개변수 공간의 누적 배열의 차원이 기하급수적으로 증가하여 실제 구현이 불가능해질 수 있음 f(x,a) = 0 parameter vector (axes in Hough space)

Example: Finding a Circle Circles have three parameters Center (a,b) Radius r Circle f(x,y,r,a,b) = (x-a)2+(y-b)2-r2 = 0 Task: 에지점 (x,y)에 대한 정보가 주어지면, 원의 중심은 어디에 ? 에지 영상에서 반지름 r (주어진 값)을 갖는 원을 찾는 문제 (원의 중심을 찾는 문제)

Finding a Circle (i-a)2+(j-b)2-r2 = 0 fixed (i,j) Circle Center Image Parameter space (a,b) fixed (i,j) (i-a)2+(j-b)2-r2 = 0 Parameter space (a,b) Parameter space (a,b) Circle Center (lots of votes!)

Finding Circles 반지름 r 값이 주어지지 않으면, 누적 배열은 3차원으로 구성된다 에지 방향에 대한 정보가 주어지면, 계산 복잡도를 대폭 줄일 수 있다 허프 변환을 여러 형태로 확장하여 다양한 문제 해결에 사용 가능하다 : Ballard, D. H. Generalizing the Hough Transform to Detect Arbitrary Shapes, Pattern Recognition 13:111-122, 1981. Illingworth, J. and J. Kittler, Survey of the Hough Transform, Computer Vision, Graphics, and Image Processing, 44(1):87-116, 1988 We have an additional constraint : 2(x-a) dx + 2(y-b) dy = 0 (y-b) / (x-a) = = - dx/dy = Gy/Gx = tan (theta) => b= B(a,theta, x,y), b is a function of a at each point (x,y) with edge gradient orientation theta => Only search in (a, r) space