[패턴인식] 에지 검출(1) : 에지 검출의 기초, 영교차 이론

Edge Detection

목차

0. Preview

1. 에지 검출의 기초

2. 영교차 이론

3. 캐니 에지

4. 컬러 에지

5. 선분 검출

 

 

0. Preview

---

 

• 에지의 유용성
  • 물체의 경계를 표시해 줌
  • 매칭에 용이한 선분이나 곡선으로 변환 가능

  • 

    원래영상과 에지 영상

• 에지의 한계
  • 실종된 에지(거짓 부정, False Negative), 거짓 에지(거짓 긍정,False Positive) 발생
  • 이들 오류를 어떻게 최소화할 것인가?

 

1. 에지 검출의 기초

---

• 원리
  • 물체 내부나 배경은 변화가 없거나 작은 반면, 물체 경계는 변화가 큼
  • 이 원리에 따라 에지 검출 알고리즘은 명암, 컬러 또는 텍스처의 변화량을 측정하고, 변화량이 큰 곳을 에지로 검출

1.1 디지털 영상의 미분

• 1차원($tan\theta $ = 기울기 = 변화량)
  • 연속 공간에서의 미분
    • $tan\theta $ = 기울기 = 변화량
    • $S\prime(x) = \frac{ds}{dx} = \lim_{\delta x \to 0} \frac{s(x+\delta x) - s(x)}{\delta x}$
  • 디지털(이산) 공간에서 미분
    • $f\prime(x) = \frac{df}{dx} =  \frac{f(x+\delta x) - f(x)}{\delta x} = f(x+1) - f(x)$
    • 이에 해당하는 마스크 = [-1,1] <- 에지 연산자에 해당

  • 

    미분과 에지 검출

     
    • $f -> f\prime$ : $f(x+1) - f(x)$
    •  $ f\prime -> | f\prime|$ : 위 (b)그림에서는 threshold = 3으로, 3보다 큰 값은 $| f\prime| =1$, 작은 값은 $| f\prime| =0$으로 이진화 됨  

 

1.2 에지 모델과 연산자

• 계단 에지(Step Edge)와 램프 에지(Ramp Edge)
  • 자연 영상에서는 주로 램프 에지가 나타남

  • 

    에지 모델

• 2차 미분
  • $f\prime\prime(x)=\frac{d^2f}{dx^2} = f\prime(x)-f\prime(x-1)$
  • $= (f(x+1)-f(x)) -  (f(x)-f(x-1))$
  • $= f(x+1) + f(x-1) -2f(x)$
  • 이에 해당하는 마스크 = [1,-2, 1] 
• 램프 에지에서의 미분의 반응
  

  • 

    램프 에지에서 1차와 2차 미분의 반응

  • 2차 미분 결과 '영교차(zero crossing point)'를 경계지점으로 설정
• 에지 검출 과정
  • 1차 미분에서 봉우리 또는 2차 미분에서 영교차를 찾음
  • 두꺼운 에지에서 위치 찾기 적용
• 현실에서는 잡음(Noise) 때문에 스무딩(Smoothing)이 필요함
  • 예:) 100 100 100 170 170 170 -> 98 97 101 102168 170
  • $\delta x = 2$인 연산자로 확장
    • 고화질일 경우 픽셀 간의 사이가 촘촘하므로 차이가 별로 나지 않아  $\delta x$(offset)을 키워야 함
    • $f\prime(x) = \frac{df}{dx} = \frac{f(x+1) - f(x-1)}{2}$
    • 이에 해당하는 마스크 = [-1, 0, 1]
  • 2차원으로 확장

    • 

• 정방향으로 확장하여 에지 검출 

  • 

    에지 연산자

  • 로버츠(Roberts) 마스크 
    • 장점: 크기가 작아 연산이 적으므로, 빠른 속도로 동작하며 주변과 관계없이 확실한 에지 추출에 좋음
    • 단점: 돌출된 값을 평균할 수 없으며 잡음에 민감함
  • 프레윗(Prewitt) 마스크
    • 장점: 돌출된 값을 잘 평균화
    • 단점: 대각선보다 수평/수직에 놓인 에지에 민감(값이 일렬로 나열되어 있으므로)
  • 소벨(Sobel) 마스크
    • 장점: 돌출된 값을 잘 평균화하며, 모든 방향의 에지 검출이 가능하며 잡음에 강하다
    • 단점: 대각선 방향에 놓인 에지에 민감함

 

1.3 에지 강도와 에지 방향

• 에지 검출 연산
  • 그레디언트(Gradient) : $\nabla f = (\frac{\partial f}{\partial y}, \frac{\partial f}{\partial x}) = (d_y, d_x)$
  • 에지 강도(대각 계산, Euclid 거리와 비슷) : $S(y,x) = magnitude(\nabla f) = \sqrt{d_y^2 + d_x^2}$
  • 그레이언트 방향(각도계산) : $D(y,x) = arctan(\frac{d_y}{d_x}) = tan^-1(tan \theta) = \theta$
    • 에지방향은 그레디언트 방향에 수직에 해당함
  •   

    

    에지방향과 8-방향 양자화

• 예제. 아래의 (5,3) 위치에 있는 화소에 대해 소벨 에지 연산자를 적용하여 그레디언트, 에지 강도, 에지 방향을 계산해보자

  • 

    
    
    

  • 

  • 에지 방향은 그레디언트 방향에 수직이므로 $90도 = |그레디언트 방향| + 에지 방향 = 63.4 + \theta$
  • 따라서 에지 방향은 $\theta = 26.6$이며, 양자화하면 0도~45도는 1에 해당하므로 '1'이 된다
• 에지 검출 연산 관련 예시

  • 

    에지 검출과 관련된 맵

 

2. 영교차 이론

---

• 1980년에 Marr과 Hildreth가 개발[Marr80]
  • 이전에는 주로 소벨을 사용

2.2 가우시안과 다중 스케일 효과

• 가우시안을 사용하는 이유
  • 미분은 잡음을 증폭시키므로 스무딩 적용이 중요함

    • 

      미분에 의한 잡음 증폭

  • $\sigma$ 를  조절하여 다중 스케일 효과
    • 에지의 세밀함 조절 가능
    • $\sigma$ 가 커질수록 해상도와 고주파는 낮아짐

    • 

      다중 스케일 에지 효과

• 가우시안(Gaussian)
  • $G(x) = \frac{1}{\sqrt{2 \pi}\sigma}e^{-\frac{x^2}{2\sigma^2}}$
  • $\sigma$ 로 스케일 조절 
    • $\sigma$  가 커질수록 표준편차는 작아지며, $\sigma$ 가 작아질 수록 중앙값은 커진다

    • 

      가우시안 커널

• 2차원 가우시안
  • $G(y,x) = \frac{1}{2 \pi \sigma^2}e^{-\frac{y^2+x^2}{2\sigma^2}}$
  • $\sigma = 2.0$ 일때 가우시안 함수

  • 

    2차원 가우시안 함수

• 이산 공간에서 구현
  • 마스크 크기가 작으면 오차, 크면 계산 시간 과다
  • $6 \sigma $ 와 같거나 큰 가장 작은 홀수로 $\sigma = 3.0$이면 19*19 마스크 사용

2.3 LOG 필터

• Marr-Hildreth 에지 검출 알고리즘[Marr80]
  • 2차 미분에서 영교차 검출
  • 알고리즘
    1. $\sigma$ 크기의 가우시안으로 입력 영상 f를 스무딩(지역통과 필터링)
    2. 결과 영상에 라플라시안 연산자를 적용하여 2차 미분을 구한다
    3. 결과 영상에서 영교차를 찾아 에지로 설정하고 나머지는 비에지로 설정
• 라플라시안(Laplacian)

  • 

• LOG(Laplacian of Gaussian) 필터
  • 입력 영상에 가우시안G를 적용한 후, 결과에 라플라시안을 다시 적용하는 두 단계의 비효율성
    • 계산 시간 과다
    • 이산화에 따른 오류 누적
  • LOG 필터를 이용한 한 단계 처리

    • 

    • 원래는 가우시안 마스크에 이미지f를 convolution을 한 후에 2차 미분을 하는 두 단계였으나, 가우시안 마스크에 이차 미분한 마스크 상태로 이미지f에 한 번만 convolution을 함
    • LOG 필터를 사용한 에지 검출 알고리즘
      1.  $\sigma$ 크기의 LOG 필터를 입력 영상 f에 적용
      2. 결과 영상에서 영교차를 찾아 에지로 설정하고, 나머지는 비에지로 설정

      3. 

         LOG 필터

  • 영교차 검출
    1. 여덟개의 이웃 중에서 마주보는 동-서, 남-북, 북동-남서, 북서-남동의 화소 쌍 네 개를 조사
    2. 그들 중 2개 이상이 서로 다른 부호 가지는 값 확인
    3. 부호가 다른 쌍의 값 차이가 임계값 T를 넘을 경우 가운데 화소는 영교차 점에 해당
  • 예시 : 8x8 원래 영상f에 $\sigma = 0.5$ 의 3x3 LOG 연산자를 적용하여 얻은 영상이 g이다. g의 (6,3)의 영교차 여부를 따져보자

    • 

      
      
      • (6,3) 화소의 북-남 ,북서-남동의 화소 쌍이 서로 다른 부호를 가짐
      • 이들의 화소의 값차이는 각각 7.6442, 5.2379이다
      • 임계값 T= 1.0일 때, 두 값 모두 T를 넘으므로 이 화소는 영교차 점이 된다
    • 아래는 T = 1.0으로 구한 에지 영상 b이다

      • 

  • LOG 필터를 사용한 다중 스케일 에지 검출 예시 

    • 

      다중 스케일 에지 검출

    • $\sigma $ 값이 커질수록 false edge와 true edge 둘 다 작아진다

 

 

<3. 캐니에지 ~ >부터는 다음 게시글에서 계속...

https://codingsmu.tistory.com/106?category=983612 

[패턴인식] 에지 검출(2) : 캐니 에지, 컬러 에지, 선분 검출