[3주차] Ch03 - 에지 검출

IkSun·2023년 4월 21일

Compute Vision & DNN

목록 보기

3/5

CH3

학습목차

에지 검출의 기초 & 영교차 이론 (계산 시간 감소)

캐니 에지 & 컬러 에지

선분 검출

지역 연산, 전역 연산, if-else 룰, 결과 품질을 결정하는 파라미터

Preview

에지의 유용성
- "물체의 경계" 를 표시해줌
- 매칭에 용이한 선분이나 곡선으로 변환 가능
- 8비트를 1비트로 표현하기 떄문에 사이즈를 1/8 줄일 수 있다.
에지의 한계
- 실종된 에지 (거짓 부정 FalseNegative), 거짓 에지 (거짓 긍정 FalsePositive) 발생
- 이들 오류를 어떻게 최소화할것인가?

1

1. 에지 검출의 기초 & 영교차 이론 (계산 시간 감소)

에지 검출의 기초

원리 : 물체의 경계는 변화가 크다 $\to$ 에지 검출 알고리즘은 명암, 컬러, 텍스처의 변화량을 측정하여 변화량이 큰 곳을 에지로 검출한다.

1.1) 디지털 영상의 미분

1차원
- 연속 공간에서 미분 : $f'(x) = \lim_{\delta x \to \infty}\frac{f(x+\delta x - f(x)}{\delta x}$
  - 컴퓨터 비전에서 다루는 디지털 영상은 연속 공간이 아닌, 이산 공간에서 정의된다.
  - 이산공간에서 가장 작은 단위는 1이므로 $\delta x=1$ 이라고 가정하고 이분을 디지털 영상에 적용하면,
- 이산(디지털) 공간에서의 미분 : $f'(x) = \frac{f(x+\delta)- f(x)}{\delta x} = f(x+1) - f(x)$
  - 이 식은 마스크 $[-1][1]$ 로 영상 $f$ 를 컨볼루션하는 것과 같다.
  - 이 연산에 사용된 마스크는 에지를 찾는 데 활용할 수 있으므로 실제 구현은 필터 $u$ 로 하고, 이를 에지 연산자 라고도 부른다.

1.2) 에지 모델과 연산자

계단 에지와 램프 에지를 가진 영상에서 에지 검출 과정
- 1) 1차 미분에서 봉우리 찾기 (ex. 소벨 필터)
  - 계단 에지 : 위치 3 $\to$ 4 에서 봉우리가 나타난다(두꼐가 1이므로 찾기 쉬움)
  - 램프 에지 : 봉우리(값이 줄어드는)가 7~10 에 걸쳐있어 두께가 4.
- 2) 2차 미분에서 영교차 찾기 (ex. LOG)
  - $[1, -2, 1]$ 필터로 구현
  - 에지의 정확한 위치를 찾기 위해 2차 미분
  - 계단 에지 : 두께가 2가 되는데, 4는 -4로 바뀌어 그 사이 영교차 발생.
  - 램프 에지 : 에지가 시작하는 위치 7에서 -1 이 나타나고, 끝나느 위치에 10에서 1이 나타나, 그 사이에 영교차가 발생.
- 3) 또는 두꺼운 에지에서 위치 찾기 적용
하지만 현실에서 에지 검출을 할 때에는
- 에지 연산자를 적용하기 전 불완전한 광학 때문에 발생하는 잡음을 누그러뜨리는 스무딩 연산 적용이 필요
  - 예) 이상적으로는 100 100 100 170 170 170 ... $\to$ 실제는 98 97 101 102 168 170 169 ...
- $\triangle x = 2$ 인 연산자로 확장
- 2차원으로 확장
  - 2 차원 영상 f(y,x) 는 y 방향의 편도 함수와 x 방향의 편도 함수를 구한다. 이 둘은 그레디언트 벡터를 형성하며 줄여서 그레디언트라 부른다,
  - y 방향으로 또는 x방향으로의 명암값의 변화를 탐지하기 위해 다음과같이 마스크를 설정할 수 있다
- 위 식들은 이론상 합리적으로 보이지만 실제로는 잡음을 대처하지 못하므로 마스크를 dxd 크기의 정방형으로 확장하여 스무딩 효과를 지니도록 함 (총합은 0)

1.3) 에지 강도와 에지 방향(1차 미분)

에지 검출 연산
- 그레디언트 : $\nabla f = (\frac{\partial f}{\partial y}, \frac{\partial f}{\partial x}) = (d_{y}, d_{x})$
- 에지 강도 : $S(y,x) = magnitude(\nabla f) = \sqrt{d_{y}^{2}+d_{x}^{2}}$ (에지일 가능성 또는 신뢰도)
- 그레디언트 방향 : $D(y,x) = arctan(\frac{d_{y}}{d_{x}}) = tan^{-1}(\frac{d_{y}}{d_{x}})$
  - 그림은 어두운 배경에 밝은 물체가 놓여있다고 가정한 것이고, 그림에 표시된 경계선 상의 한 점에 마스크를 적용하면 음수가 되어 $dx$ 는 왼쪽을 가리키고 $dy$ 는 양수가 되어 아래쪽을 가지킨다.
  - $dx$ 와 $dy$ 에 따라 그레디언트 방향이 정해지고 그에 수직을 이루도록 에지 방향이 결정된다.
  - 에지 방향은 그 방향을 바라보고 섰을 때 왼쪽은 밝고 오른쪽은 어두운 것이다.
  - 이렇게 구한 에지 방향은 $[0, 360 ^\circ]$ 범위를 갖는데, 이 범위는 보통 8-방향으로 양자화 된다.
예시
- 풀이
  - $(5,3)$ 위치의 화소를 각각 필터 $m_y$ 와 $m_x$ 와 컨볼루션 한 결과 $d_y = -4$ , $d_x = 2$ 가 나온다.
  - $S(5,3) = \sqrt{d_y^{\ 2} + d_x^{\ 2}}$ = 4.47
  - $D(5,3)$ = 63.4 도
- 결과
  - 에지 강도 맵을 보면 사람과 배경의 경계는 심한 명암 변화 때문에 강한 에지가 나타나고, 사람 내부는 약한 에지가 분포한다.
  - (c)는 수직 방향의 명암 변화에 반응하고, (d)는 수평 방향으로 반응함을 확인할 수 있다.

영교차 이론

1980 년에 Marr 와 Hildreth 가 개발 [Marr80]

이전에는 주로 소벨을 사용

1.4) 가우시안과 다중 스케일 효과

가우시안을 사용하는 이유
- 1) 미분은 잡음을 증폭시키므로 스무딩 적용이 중요함, 가우시안 스무딩은 잡음에 대처하는 효과가 있다.
  - 아래 그림은 명암 5를 갖는 균일한 영역에 $9$ 라는 소금, $1$ 이라는 후추가 섞인 솔트페퍼 잡음을 보여준다.
  - 1차 미분과 2차 미분을 거치면서 잡음의 값이 커지고, 폭도 넓어진다. $\to$ 이런식으로 노이즈를 정리해주는 작업을 해준다.
- 2) 가우시안의 매개변수 $\sigma$ 를 조절하여 다중 스케일 효과를 얻는데 있다.
  - 즉, $\sigma$ 를 크게 하면 큰 물체의 에지만, 작게 하면 물체 디테일한 에지까지 추출
- 3) 에지의 세밀함 조절 가능
  - $\sigma$ 를 작게 하면, 작은 객체도 잡을 수 있고, $\sigma$ 를 크게 하면 디테일은 버리고 큰 객체 에지를 잡을 수 있다.

가우시안 필터
- 1차원 가우시안 커널 : $G(x) = \frac{1}{\sqrt{2\pi} \sigma}$ $e^{-\frac{x^{2}}{2 \sigma^{2}}}$
  - $\sigma$ 로 스케일 조절 : 시그마가 클수록 좌우로 넓게 펴지며, 봉우리는 낮아진다.
- 2차원 가우시안 확장 : $G(y,x) = \frac{1}{\sqrt{2\pi} \sigma^{2}}$ $e^{-\frac{y^{2}+x^{2}}{2 \sigma^{2}}}$
- 이산 공간 (픽셀) 에서 구현
  - 마스크의 크기가 작으면 오차, 크면 계산 시간이 과다
  - 샘플링할 때 적절한 마스크 크기를 선택 : 6 $\sigma$ 와 같거나 큰 가장 작은 홀수
    - 예)
      $\sigma = 0.5$ 면, $3 \times 3$ 크기의 마스크 사용
      $\sigma = 2.0$ 이면, $2 \times 6 = 12$ 와 같거나 큰 가장 작은 홀수는 $13$ 이므로 $13 \times 13$ 크기의 마스크를 사용할수있다.

1.5) LOG 필터

2차 미분에서 영교차 검출
LOG 필터 설계
- 입력 영상에 가우시안 G를 적용한 후, 결과에 라플라시안을 다시 적용하는 두 단계의 비효율성
  - 계산 시간 과다
  - 이산화에 따른 오류 누적
- LOG 필터를 이용한 한 단계(가우시안 + 라플라시안) 처리하여 스무딩과 2차 미분을 동시에 할 수 있다.
  - 가우시안에 라플라시안을 적용한 $LOG^{Laplacian \ of \ Gaussian}$ 연산자 또는 $LOG$ 필터라 부른다.
  - $LOG(y,x) = \nabla^{2}(G(y,x) \circledast f(y,x)) = (\nabla^{2}G(y,x)) \circledast f(y,x)$ 이 식을 정리하면,
  - $\nabla^{2} G(y,x) = (\frac{y^{2}+x^{2}-2\sigma^{2}}{\sigma^{4}})$ $G(y,x)$
  - 가우시안 G에 계수를 곱한 꼴이 되었고, 가운데 값이 음수값을 가지고 주변 부분에 가장 큰 양수를 갖는 모양으로 log 필터를 생성한다.
LOG 필터를 사용한 에지 검출 예제
- 오른쪽에 적혀있는 LOG 필터를 적용해서 컨볼루션을 구해본다.
- 빨간색 동그라미 위치의 화소가 엣지인지 아닌지 판결하기 위해서 주변에 있는 4개의 쌍이 부호가 같은지 다른지 확인
- 부호가 다른 짝이 2개가 있으므로 (하지만 0과 비교할때는 부호가 다르다고 하지 않는다)
- 따라서 에지로 판단하여 0을 1로 표시해준다.
다음 그림은 LOG 필터를 같은 영상에 적용한 결과
- 시그마가 작을 때에는 아주 세밀한 에지까지 검출된 반면, 시그마가 커지면 세밀한 부분은 점점 사라지고 큰 규모의 에지 구조만 남는다.
- 시그마를 변화하면서 T 값을 static으로 고정하거나, T 값을 dynamic 하게 변경해줄 수 있고, static 으로 했을때 칼 자루 부분이 보임

2

2. 캐니 에지 & 컬러 에지

2.1) 케니 에지

캐니 에지
- 앞 절은 '그럴 듯 해보이는' 에지 연산자 사용
- 에지 검출을 최적화 문제로 해결
- 세가지 기준
  - 1) 최소 오류율 : 거짓 긍정과 거짓 부정이 최소여야 한다. 즉, 없는 에지가 생성되거나 있는 에지를 못 찾는 경우를 최소로 유지해야 한다.
  - 2) 위치 정확도 : 검출된 에지는 실제 에지의 위치와 가급적 가까워야 한다.
  - 3) 에지 두께 : 실제 에지에 해당하는 곳에는 한 두께의 에지만 생성해야 한다.
- 그리디 알고리즘에 기반한 "근사해 $^{\ approximation}$ "으로 구현
- 케니 에지 검출 알고리즘
- 비최대 억제
  - 비 최대 억제는 화소 $p$ 에 대해 두 이웃 화소를 조사하는데, $p$ 의 에지 강도가 두 이웃보다 크면 에지가 되고 그렇지 않으면 억제된다.
  - 지역 최대 점만 에지로 검출하므로, 얇은 두께의 에지 이미지를 생성
  - 이렇게 생성된 에지 맵에는 거짓 긍정이 많이 포함됨
- 이력 임계값
  - 캐니 알고리즘은 두개의 임계값 $T_{high}$ 와 $T_{low}$ 를 쓰는 이력 임계값 방법을 적용하여 거짓 긍정 줄임
  - 에지 추적은 $T_{high}$ ( $T_{low}$ 의 2~3배로 설정)를 넘는 화소(즉 신뢰도가 높은 화소)에서 시작,
    - 예) $[$ 2.5 배 $]$ $low = 0.05,high = 0.125$
  - 추적 도중에는 $T_{low}$ 적용(즉, 이웃 화소가 추적 이력이 있르면 신뢰도가 낮더라도 에지로 간주)

알고리즘

가우시안 필터링(Gaussian filtering)
이미지에 가우시안 필터를 적용하여 노이즈를 제거합니다. 가우시안 필터는 이미지의 부드러운 부분에 대한 정보를 보존하면서 노이즈를 제거할 수 있는 필터입니다.

경계 강도 계산(Computing gradient magnitude and direction)
Sobel 필터를 사용하여 이미지에서 경계의 강도와 방향을 계산합니다. 이 단계에서는 수평, 수직 방향의 그래디언트 값을 계산하고, 그 두 값을 이용하여 경계의 강도와 방향을 계산합니다.

비최대 억제(Non-maximum suppression)
비최대 억제는 이미지에서 경계가 아닌 지역을 제거하여 정확한 경계를 얻기 위해 사용됩니다. 이 단계에서는 각 픽셀에 대해 그 픽셀과 방향이 일치하는 이웃 픽셀들의 경계 강도를 비교하여 경계가 아닌 지역을 제거합니다.

이력 임계값 적용(Hysteresis thresholding)
최종적으로, 이력 임계값을 사용하여 검출된 경계들을 최종적으로 선별합니다. 이 단계에서는 경계 강도가 임계값보다 큰 픽셀들을 강한 경계로 선택하고, 이에 연결되는 약한 경계들을 추가적으로 선택합니다.

$T_{high}$ 보다 높고 본인이 방문했는지를 함수로 확인하여 이웃하는 8개의 화소를 다 확인해서 $low$ 보다 큰지 체크

시그마가 커질수록 디테일이 사라지는 현상을 확인할 수 있다.

왼쪽과 오른쪽은 각각 이력 입계값이 높고 낮음에 따른 결과를 비교한 것이다. 오른쪽이 왼쪽의 두배이며 $T_{low}$ 는 $T_{high}$ 의 $2.5$ 배로 설정하였다. 예를 들어 시그마가 2.0 일때 왼쪽은 $(T_{low}, T_{high}) = (0.125, 0.05)$ 이고 오른쪽은 $(0.25, 0.1)$ 이다. 임계값이 높을 때 그 임계값보다 높은 것만 에지로 검출하기 때문에 에지가 적게 검출된다.

2.2) 컬러 에지

가장 쉽게 하는 방법은 컬러 영상을 Gray 영상으로 바꿔 캐니 알고리즘을 적용할 수 있지만
컬러 영상을 직접 추출 하고싶다면, RGB 채널에 독립적으로 에지를 검출한 후, 그 결과를 OR 를 통해 하나로 결합하는 것도 방법
- 하지만, 에지 불일치 발생

3

3. 선분 검출

에지 맵 $\to$ 에지 토막 $\to$ 선분

3.1) 에지 연결과 선분 근사

에지 연결과 표현
- 에지를 표현하는 가장 간단한 방법은 에지 화소의 좌표를 체인 코드를 통한 토막낸 에지를 순서대로 배열로 저장 $\to$ 메모리 절약
- 끝점과 분기점이 만나면 하나의 토막으로 생각
- 에지 맵이 주어졌을 때, 에지 토막 5개가 만들어진다.
세선화
- 2~3 두께 에지를 "1두께"로 변환
- 최소 8-연결성 보장
SPTA 세선화 [Naccache84]
- 주어진 픽셀 위치가 p 라고 할 때 3x3 마스크를 씌워서 조건문 확인
- 1 은 에지라는 말, 0은 에지가 아니라는 말, x 는 둘다 상관 없다는 말
- 4개의 마스크 중 하나라도 해당된다면 세선화 하지 않음(엣지가 끊어지기 때문에), 즉 전부 매칭 되지 않으면 세선화를 적용
  - 4가지의 if-else 문
에지 추적
- 두꼐가 2~3개 짜리를 두께 1 로 만들어주는 세선화 진행
- 그리고 아까 설명한 분기점과 끝점을 추적하는 에지 추적하는 방법
- 분기점 후보를 조사한 후, 각 점에 3x3 윈도우를 씌운 후 전환 횟수가 가장 큰 점을 분기점으로 선정
- 전환 횟수는 다음과 같이 에지에서 비에지로 시계방향으로 가는 점의 개수
- 전환 횟수가 1 인 지점은 끝점, 3 이상인 지점은 분기점으로 판단한다. 즉 b가 분기점
- 에지 토막 검출 알고리즘
선분 근사
- 추적에 의한 에지 토막들을 연결했으면, 이를 직선으로 근사화되어 직선 토막으로 변환 될 수 있다.
- 두 끝점을 잇는 직선으로부터 가장 먼 점까지의 거리 h 가 임계값 $T$ 이내가 될 때까지 선분 분할을 재귀적으로 반복 (diveide-and-conquer)
  - T는 선분의 품질을 결정하는 파라미터

3.2) 허프 변환

허프 변환
- 에지 연결 과정(3x3 필터/마스크/윈도우 등 "지역" 연산) 없이 선분 검출
  - "전역" 연산 (전체 공간 조사 like 히스토그램) 을 이용한 지각 군집화
  - 즉, 사람이 일직선상에 있다고 자각하는 점들을 한 곳에 모으는 원리
- "영상" 공간 $y-x$ 를 "기울기/절편" 공간 $b-a$ 로 매핑 (like 시간 공간 $\to$ 주파수 공간)
- 연결관계가 명확하지 않거나 잡음으로 인해 에지들이 작은 조각으로 끊어지는 경우에 변환한다.
- 문제1: 수직선의 기울기가 $\infin$ $\to$ 극좌표계로 해결
  - 점들간의 기울기를 구할 때, 기울기가 정의되지 않는 어려움을 극좌표계 사용하여 해결
  - 왼쪽의 직교 좌표계에서의 점은 극좌표계에서 여러개의 선으로 정의가 된다.
  - 밀집된 곳 찾기
    - 양자화된 누적 배열 이용하여 해결
  - 방정식으로 표현되는 어떠한 도형도 검출 가능 : 예) 원 검출
    - 3차원 누적 배열 사용 : $(y-b)^2 + (x-a)^2 = r^2$
- 예제
  - 직교 좌표계에서 세 점이 에지로 나왔는데, 약간 노이즈가 있어서 직선으로 표현되지 않는다면
  - 극좌표계 활용 : A 라는 누적 배열로 양자화를 하여 세 점의 자취를 누적시켜 지역 최대점 3을 갖는 (6,6) 에 해당하는 직선을 검출

3.3) RANSAC

RANSAC $^{random \ sample \ consensus}$
- 허프 변환의 군집화 개념을 확장
- 인라이어 $^{inlier}$ 를 찾아 (즉, 아웃 라이어 $^{outlier}$ 제거) 어떤 모델을 적합시키는 방법
- 난수 생성하여 인라이어 군집을 찾기 떄문에 임의성을 지님 $\to$ 수행 떄마다 다른 결과 도출
선분 검출에 RANSAC 적용
- 모델은 직선의 방정식 $y=ax+b$
- 1차 시도 : 두 파란 점를 인라이어로 하겠다 가정하면, 직선을 그어, 그 직선에 가깝다면 인라이어로 구분
- 2차 시도 : 다른 두 점을 연결, 인라이어가 더 많아 졌다.
  - 즉, 이런 인라이어들을 한번에 지나는 직선을 표현