에지 검출 그리고 허프 변환

Edge Detection 에지 ? 명확하지 않고 애매하다 일반적으로, 에지는 밝기 값이 급격히 변하는 픽셀

Discontinuities B A C D A: 깊이(거리)가 급격히 변하는 위치 B: 서로 다른 물체 표면의 경계

Illusory Edges Kanizsa Triangles

Another One

Goal 의미있는(?) 에지를 검출하는 알고리즘 개발

Edgels 에겔(edgel, edge element) = 작은 영역 안에서 밝기 값의 급격한 변화 에겔의 구성 요소 에겔은 마스크(작은 영역)를 이용하여 검출 에겔의 구성 요소 방향(orientation) 크기(magnitude) 위치(position)

Outline 일차 미분 연산을 이용한 에지 검출 캐니 에지 검출(Canny edge detector) 1x2, Roberts, Sobel, Prewitt 캐니 에지 검출(Canny edge detector) 허프 변환 – 투표에 의한 Line 검출 Circle 검출 Other shapes 검출

Locating Edgels f(x) = step edge maximum 1st Derivative f ’(x) 밝기 값의 급격한 변화 => 높은 미분 값=> 차연산(difference) f(x) = step edge 1st Derivative f ’(x) maximum

Reality

Properties of an Edge Original Orientation Orientation Position Magnitude

Quantitative Edge Descriptors 에지 방향 에지 법선 방향(Edge Normal) - 밝기 값 변화가 최대로 일어나는 방향 에지 방향 - 에지 법선 방향에 직교 방향 에지 위치 에지 픽셀 좌표 - (x,y) 에지 크기 / 에지 세기 에지 위치에서 법선 방향으로 밝기 변화 값

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

Real Image

Edge Detection: Typical 단계 1. 잡음 제거 에지는 보존하면서 잡음 제거 잡음 모델을 백색 가우시안(white Gaussian) 분포를 갖는다고 가정 단계 2. 에지 크기 및 에지 방향 계산 수직/수평 방향의 차-연산 마스크를 이용한 회선 연산 단계 3. 에지 위치 판정 에지 크기 및 방향을 근거로 에지 픽셀 결정 주변 픽셀의 에지 크기와 비교하여 에지 크기가 최대값을 갖지 않는 픽셀의 에지 크기를 0으로 설정 임계 값 이상의 에지 크기를 갖는 픽셀을 에지로 판정

Edge Detection Methods 1차 미분 연산자 미분 연산 마스크를 이용한 회선 연산 캐니 에지 검출기

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

Gradient of a Function 영상 함수 f 가 연속 함수라고 가정하면, (Dx, Dy) = (x,y) 위치에서 함수 f 값의 변화도 = 함수 f의 기울기 크기 : 방향 : Q = 함수 f 의 최대 변화 방향 S = Q 방향에서 함수 f의 변화 정도 Dx Dy q = tan-1 ( )

Geometric Interpretation 영상 함수 I(i,j)는 연속 함수가 아닌 이산 함수 따라서 기울기에 대한 근사값을 구해야 …..

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 이산 영상 함수 I(x,y) Derivatives Differences 1 -1 -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 [ 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 Edge Magnitude = Edge Direction = S1 + S2 2 tan-1 S1 S2

Anatomy of the Sobel 소벨 커널은 분리 가능 스므딩과 차연산의 결합 - + 1/4 1/4 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

Prewitt Example Santa Fe Mission Prewitt Horizontal and Vertical Edges Combined

Edge Thresholding 특정 임계 값을 전체 영상에 적용 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차원 영상에 커널(-1 -1 -1 -1 0 1 1 1 1) 적용 Image Pixels Operator Response

Non-Maximal Suppression 스텝 에지에 대한 연산자 적용 결과는 에지 크기는 점진적으로 증가하고 점진적으로 감소 이웃 영역에서 에지 크기가 최대 값이 아닌 위치의 에지 크기를 0으로 설정 적절한 이웃 픽셀은 (비-최대값 억제 작업을 적용할)? 중심 픽셀의 에지 방향에 위치하고, 에지 방향이 같고, 기울기의 방향(+ or -)이 같은 픽셀 이어야 한다

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.

Basic Algorithm 가우시안 함수를 일차 미분한 값과 유사한 값을 갖는 마스크 사용하는 것이 가장 바람직하다 캐니 알고리즘 영상을 스므딩한 후 차연산을 적용하여 에지 크기와 에지 방향을 구한다 가우시안 스므딩 + 2x2 마스크를 이용한 차연산 비-최대값 억제 연산 수행 에지 픽셀들을 연결하기 위해 두 개의 임계값 사용 (hysteresis thresholding)

Hysteresis Thresholding 두 임계값 사용 알고리즘: high & low high 임계값 이상의 에지 크기를 갖는 픽셀을 에지로 선언 low 임계값 이하의 에지 크기를 갖는 픽셀을 비-에지로 선언 low 임계값 이상의 에지 크기를 갖고 에지 픽셀에 인접한 픽셀을 에지로 선언 에지 선언 작업을 반복적으로 진행 강한 에지(strong edges)에서 출발하여 에지 성장(grow out) 작업 반복 수행 알고리즘 매개변수: s (가우시안 커널의 표준편차) low 임계값 T1 high 임계값 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

2D Gaussian Distribution 2차원 가우시안 함수:

s Defines Kernel ‘Width’

Creating Gaussian Kernels 2차원 가우시안 함수로 부터 마스크의 가중치 계산: 위 식을 이용하여 마스크의 (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 : -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) 생성 가능 2차원 가우시안 함수를 1차원 가우시안 함수로 분리 가능

Why Gaussian for Smoothing 분리 가능

Color Edge Detection R, G, B 채널에 에지 검출 수행 후 결합 각 채널의 미분 값을 결합하여 에지 검출 수행

From Edgels to Lines 검출된 에지 픽셀들로 부터 이들을 연결하는 직선 성분을 구하는 방법 ?

Edgels to Lines 허프 변환의 기본 개념: 직선을 점으로 사상하는 공간(매개변수 공간) 생성 각 에지 픽셀에 대해 대응되는 매개변수 공간의 매개변수에 투표 진행 가장 많은 표를 받은 매개변수를 갖는 직선 선정 에지 점들을 그룹화하는 문제를 매개 변수 공간에서 피크 점을 찾는 문제로 변환하여 해결

Edgels to Lines 영상 공간의 두 에지 점 P(x,y) and P’(x’,y’) : P ' 에지 점 P=(x,y)을 통과하는 직선은 y=mx + b, m 과 b는 다양한 값을 가질 수 있다 에지 점 P’에 대해서도 같은 처리 가능 매개변수 공간이 두 변수 (m,b)를 갖도록 설정 후 투표 진행 P P ' L x y

Parameter Space b x,y; x',y' are fixed b = -mx+y b’ = -m’x'+y' m (m ,b   b m b = -mx+y b’ = -m’x'+y' x,y; x',y' are fixed (m ,b ) L 1 2

General Idea 기본 개념 : 허프 공간 (m, b) 이산적인 2차원 배열로 구현 영상 공간의 각 에지 점에 대응되는 허프 공간의 변수들(매개 변수)에 투표 진행

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 매개변수 양자화 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 무한대 기울기를 갖는 수직선 문제 직선에 대한 다른 매개 변수 사용 r = x cos q + y sin q r 극 좌표계 사용 y r = x cos q + y sin q r 2 r q 1 2 q 1 x

Why? 극 좌표계 (r,q) 의 효율성 : 유한 범위: 0 £ r £ Ö(row2+col2), 0 £ q £ 2p 유일성: 각 직선을 하나의 값으로 표현

Alternate Representation 영상 공간의 직선은 허프 공간 (r,q) 에서 사인 커브 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 에지 방향 정보 ? Image 각 에지 점을 허프 공간에서 하나의 점으로 변환 가능 제약 사항으로 활용 가능 ! 각 에지 점을 허프 공간에서 하나의 점으로 변환 가능 Image Origin is arbitrary The three edges have same (r, q)

Post Hough 허프 변환은 영상 공간에서 에지 점들의 위치 정보 상실: 직선 성분을 영상 공간에 적절히 위치시키기 위해서는 후처리 필요 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” 설정 정렬된 두 인접 에지 점의 간격이 max gap 보다 크면, 서로 다른 직선 성분에 속하는 점으로 판정 (option)직선 성분에 속하는 에지 점들의 좌표 값을 이용하여 직선 적합 (straight-line fitting) 작업

Example: Finding a Circle 3 개의 매개 변수를 갖는 원 검출 중심점 (a,b) 반지름 r 원 함수 f(x,y,r,a,b) = (x-a)2+(y-b)2-r2 = 0 Task: 영상 공간의 에지 점들로 부터 반지름 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