에지와 영역


에지와 영역

에지와 영역은 쌍대 문제, 다른 접근방법 사용

  • 에지와 영역은 같은 문제를 다른 방향으로 푼다고 볼 수 있음
  • 에지 : 특성이 다른 곳 검출
  • 영역 : 유사한 화소를 묶음

사람은 의미분할에 능숙

  • 사람은 머리속에 기억된 물체 모델을 활용하여 의미 분할

에지 검출 알고리즘

미분

  • 변수 x가 미세하게 증가했을 때 함수 변화량을 측정
  • 미분을 디지털 영상에 적용하면 한 화소가 변할때 얼마나 바뀌는가로 변함
  • 실제 구현은 필터 u로 컨볼루션(u를 에지 연산자로 부름) \(f'(x) = \frac{f(x + \delta x) - f(x)}{\delta x} = f(x+1) - f(x)\)

에지 연산자

  • 현실 세계의 램프 에지
    • 명암이 몇 화소에 걸쳐 변함
  • 1차 미분과 2차 미분
  • 2차미분 \(f''(x) = \frac{f'(x) - f'(x - \delta)}{\delta} = f'(x) - f'(x-1) = (f(x+1) - f(x)) - (f(x) - f(x-1)) = f(x+1) - 2f(x) + f(x-1)\)

  • 1차미분과 2차미분 차이
    • 2차미분을 하면 이 식을 구하는 필터를 한번에 구할 수 있음

에지 검출

  • 1차 미분에서 봉우리 찾기
  • 2차 미분에서 영교차 찾기

1차 미분에 기반한 에지 연산자

  • 실제 영상에 있는 잡음을 흡수하기 위해 크기가 2인 필터를 크기 3으로 확장
  • 또한 1차원을 2차원으로 확장 \(f'_x (y, x) = f(y, x+1) - f(y, x-1) \\ f'_y (y, x) = f(y+1, x)-f(y-1,x)\)

에지 강도와 에지 방향

  • 에지 강도 : 에지일 가능성을 나타냄 \(s(y, x) = \sqrt{f'_x (y, x)^2 + f'_y(y, x)^2}\)
  • 그레이디언트 방향 : 에지방향은 그래디언트 방향을 90도 회전한 방향으로 정의 \(d(y, x) = arctan \left(\frac{f'_y (y, x)}{f'_x (y, x)}\right)\)
  • 그레이디언트 방향과 에지 방향은 270도 차이

소벨 연산자의 적용

import cv2 as cv
img = cv.imread('img.jpg')
gray = cv.cvtColor(img, cv.COLOR_BGR2GRAY)

grad_x = cv.Sobel(gray, cv.CV_32F, 1, 0, ksize = 3) #소벨연산자 적용
grad_y = cv.Sobel(gray, cv.CV_32F, 0, 1, ksize = 3)

sobel_x = cv.convertScaleAbs(grad_x) #절댓값을 치해 양수 영상으로 변환
sobel_y = cv.convertScaleAbs(grad_y)

edge_strength = cv.addWeighted(sobel_x, 0.5, sobel_y, 0.5, 0) #에지 강도 계산

cv.imshow('original', gray)
cv.imshow('sobelx', sobel_x)
cv.imshow('sobely', sobel_y)
cv.imshow('edge strength', edge_strength)

cv.waitKey()
cv.destroyAllWindows()
  • Sobel 함수로 x방향의 연산자를 적용. cv.CV_32F:결과 영상을 32비트 실수 맵에 저장하라는 의미. 1, 0은 x방향 연산자를 사용하라는 의미. ksize = 3 : 3X3크기를 사용하라는 의미
  • cv.convertScaleAbs : 음수가 포함된 맵에 절댓값을 취해 양수로 변환.
    • 이 함수는 부호 없는 8비트 형인 CV_8U맵을 만듬. np.clip(a, 0, 255)처럼 값을 기록.
  • addWeighted : sobel_x, sobel_y에 각각 0.5를 곱해서 더한 결과를 edge_strength객체에 저장
    • 이 함수는 addWeighted(A, a1, B, b1, c)이럴 경우 A x a1 + B x b1 + c를 계산
    • A와 B가 같은 데이터형이면 결과 영상은 같은 데이터형, 둘이 다른 데이터형이면 오류 발생

캐니 에지

에지 검출을 최적화 문제로 품

  • 최소 오류율, 위치 정확도, 한 두께라는 세 가지 기준으로 목적 함수 정의
  • 한 두께 에지를 출력하기 위해 비최대 억제 적용
    • 에지 방향에 수직인 두 이웃 화소의 에지 강도가 자신보다 작으면 에지로 살아남고 그렇지 않으면 에지 아닌 화소로 바뀐다.
  • 거짓 긍정을 줄이기 위해 두 개의 이력 임계값 사용
    • 에지 강도가 \(T_{high}\) 이상인 에지에서 에지 추적 시작
    • 이후 추적은 \(T_{low}\) 이상인 에지를 대상으로 진행

캐니 에지 실험

import cv2 as cv
img = cv.imread('img.jpg')

gray = cv.cvtColor(img, cv.COLOR_BGR2GRAY)

canny1 = cv.Canny(gray, 50, 150) #Tlow가 50, Thigh가 150
canny2 = cv.Canny(gray, 100, 200)

cv.imshow('original', gray)
cv.imshow('canny1', canny1)
cv.imshow('canny2', canny2)

cv.waitKey()
cv.destroyAllWindows()

최소 오류율 : 거짓 긍정

  • 실제로는 부정, 긍정으로 판단
  • 에지 검출에서 에지가 아니지만 에지로 판단

위치 정확도

  • 에지가 참 에지와 가까워야함
  • 검출기에 의한 에지와 진짜 에지의 중심거리가 최소가 되어야함

한 두께

  • 참 에지 점에 대해 한 점만을 반환 해야함
  • 에지 점이 하나만 있는 곳에서 여러개를 식별하지 않아야 함

4단계 연산을 거침

  • 1단계 - 가우시안 필터링 : 블러링을 통해 잡음을 제거
  • 2단계 - 그래디언트 계산 : 소벨 마스크 필터링을 통해 그래디언트의 크기와 방향을 계산
  • 3단계 - 비최대 억제 : 그래디언트 크기가 국지적으로 최대인 픽셀을 에지 픽셀로 설정
  • 4단계 - 히스테리시스 에지 트래킹 : 2개의 임계값을 사용
    • 높은 임계값 $T_{high}$ 보다 크면 최종적인 에지로 판단
    • 낮은 임계값 $T_{low}$ 보다 낮으면 에지가 아닌 것으로 판단
    • 두 값 사이에 있는 픽셀은 연결된 에지 픽셀이 강한 에지(높은 임계값 이상)인 경우에 에지로 판단

에지 검출 방법은 명암 변화에만 의존

  • 물체 경계에 나타난 에지와 그림자로 인해 발생한 가짜 에지 구분에 약함
  • 인접한 두 물체가 비슷한 명암을 가지면 구분이 힘듬
  • 사람의 경우에는 물체의 모양과 겉모습을 동시에 사용
    • 주위 환경의 변화에도 성능 저하가 적음
  • 에지 검출에 대한 연구는 캐니 이후 뚜렷한 개선이 없음

직선 검출

에지 맵에서 에지는 1 그 외 화소는 0

  • 에지를 명시적으로 연결하여 경계선을 찾고 직선으로 변환
  • 이후 처리 단계인 물체 표현이나 인식에 유리

8-연결된 에지 화소를 연결해 경계(윤곽)선 구성

경계선 검출

  • canny 방법으로 에지 맵 생성
  • 에지 맵에서 경계선을 찾아서 저장
    • 경계선을 찾을 이미지를 넣으면 바깥 경계와 안쪽 경계를 계층적으로 찾아줌
    • RETR_LIST는 바깥 경계인 에지에 해당하는 픽셀의 위치를 리스트로 만듬
    • CHAIN_APPROX_NONE은 에지로 분류된 모든 픽셀의 위치를 기록
  • drawContours에지로 설정된 경계선을 그려줌
    • 이미지, 경계선 값(list), 경계선 인덱스, 색상, 두께의 값을 입력
    • 경계선 인덱스 -1은 경계선 값으로 선택된 값 전체를 이미지 위에 그려줌

경계선 검출 코드

import cv2 as cv
import numpy as np

img = cv.imread('img.jpg')
gray = cv.cvtColor(img, cv.COLOR_BGR2GRAY)
canny = cv.Canny(gray, 100, 200)

contour, hierarchy = cv.findContours(canny, cv.RETR_LIST, cv.CHAIN_APPROX_NONE)

lcontour = []
for i in range(len(contour)):
  if contour[i].shape[0] > 100:
    lcontour.append(contour[i])

cv.drawContours(img, lcontour, -1, (0, 255, 0), 3)

cv.imshow('original with contours', img)
cv.imshow('canny', canny)

cv.waitKey()
cv.destroyAllWindows()
  • findContours함수로 경계선을 찾아 contour객체에 저장
    • cv.RETR_LIST : 구멍이 있는 경우 바깥쪽 경계선과 그 안에 있는 구멍의 경계선을 계층적으로 찾는 방식 지정. 이렇게 설정하면 맨 바깥쪽 경계선만 찾음
    • cv.CHAIN_APPROX_NONE : 경계선을 표현하는 방식 지정한것. 이렇게 설정하면 모든 점을 기록
      • cv.CHAIN_APPROX_SIMPLE로 설정하면 직선에 대해서는 양 끝점만 기록
      • cv.CHAIN_APPROX_TC89_L1, cv.CHAIN_APPROX_TC89_KCOS : 이렇게 설정하면 Teh-Chin 알고리즘으로 굴곡이 심한 점을 찾아 그들만 기록
  • for문 부분은 길이가 50이상인 경계선만 골라 lcontour에 저장함
    • findContours함수는 시작점부터 끝점까지 추적한 다음 역추적하여 시작정으로 돌아오도록 경계선 표현. 그래서 100으로 설정하여 실제로는 50 이상인 경계선만 남김
  • drawContours로 영상에 경계선을 그림
    • 세번째 인수를 -1로 설정 : 모든 경계선을 그림. 양수로 설정하면 해당 번호에 해당하는 경계선 하나만 그림
    • 네번째, 다섯번째는 색과 두께 지정

허프 변환

  • 허프 변환은 끊긴 에지를 모아 직선 또는 원 등을 검출
  • 직선 검출의 원리
    • 각각의 점에 대해 (b, a)공간에 직선 \(b = -ax_i + y_i\)를 그림
    • (b,a)공간에서 직선이 만나는 점을 절편과 기울기로 취함. 만나는 점은 투표로 알아냄

허프 변환 구현

  • (b, a)공간을 이산화하고 누적 배열 만들어 투표를 기록
  • 직선은 자신이 지나는 칸에 1만큼씩 투표
  • 다수 표를 얻은 점을 결정할 때 비최대 억제를 적용하여 지역 최대점(극점) 찾음
  • 극좌표에서 정의된 직선의 방정식 사용
    • \[x\sin(\theta) + y\cos(\theta) = \rho\]
  • 문제점 많은 점이 존재, 점들이 완벽한 일직선 X
  • 문제점 투표의 결과로 만들어진 배열에 잡음이 많음
  • 문제점 기울기가 a가 무한대인 경우 투표 불가능

원 검출을 위한 허프 변환은 3차원 누적 배열 사용

  • \[(x-a)^2 + (y-b)^2 = r^2\]

HoughCircles 함수

  • 이미지, 변형 알고리즘, 배열의 크기, 원 중심 사이의 최소 거리, 캐니 알고리즘의 강한 에지 임계치, 비최대 억제 임계치, 원의 최소 반지름, 원의 최대 반지름
  • 배열의 크기값 1인 경우 입력영상과 같은 크기
  • 함수의 결과는 찾은 원의 중심과 반지름 값
import cv2 as cv
img = cv.imread('img.jpg')
gray = cv.cvtColor(img, cv.COLOR_BGR2GRAY)

apples = cv.HoughCircles(gray, cv.HOUGH_GRADIENT, 1, 200, param1 = 150,\
             param2 = 20, minRadius = 50, maxRadius = 120)
for i in apples[0]:
  cv.circle(img, (int(i[0]), int(i[1])), int(i[2]), (255,0,0),2)

cv.imshow('apple detection', img)

cv.waitKey()
cv.destroyAllWindows()
  • HoughCircles : 첫번째 인수인 명암 영상에서 원을 검출, 중심과 반지름을 저장한 리스트를 반환. 두번째 인수는 여러 변형 알고리즘 중의 하나를 지정
    • cv.HOUGH_GRADIENT : 에지 방향정보를 추가로 사용하는 방법
    • 세번째 인수는 누적 배열의 크기를 지정, 1로 설정하면 입력 영상과 같은 크기를 사용
    • 네번빼 인수는 원 사이의 최소 거리를 지정. 작을수록 많은 원이 검출됨
    • 다섯번째 인수 : 캐니 에지 알고리즘이 사용하는 Thigh
    • 여섯번째 인수는 비최대 억제를 적용할 때 쓰는 임곗값
    • 일곱, 여덟 : 원의 최소와 최대 반지름 지정

RANSAC

허프 변환과 최소평균제곱오차

  • 두 가지 방법 모두 아웃라이어에 강인하지 않은 추정 기법
  • 아웃라이어를 걸러내는 기능이 전혀 없음(모든 점에 같은 기회 부여)

강인한 추정 기법

  • 예) 물건의 길이를 5번 측정한 결과 {16, 1, 1, 1, 1}에 평균 적용하면 4, 중앙값 적용하면 1. 중앙값은 강인한 추정 기법

RANSAC은 강인한 추정 기법

  • RANSAC은 구체적인 문제에 두루 활용할 수 있는 메타 알고리즘
  • 난수를 생성하여 추정하는 일을 충분히 많이 반복하고 가장 신뢰할 수 있는 값 선택
  • 임의의 두 점을 연결한 선분의 일정한 폭에 포함되는 점의 개수가 적으면 후보에서 제외

영역 분할

  • 영역 분할은 물체가 점유한 영역을 구분하는 작업
    • 에지가 완벽하면 영역 분할은 불필요 하지만, 폐곡선을 형성하지 못하면 영역 분할이 안된 것
    • 사람은 물체의 3차원 모델을 사용하고 주의 집중을 적용하여 의미 분할 수행
    • 명암 또는 컬러만 보고 영역을 결정하기 때문에 의미 분할 불가능
  • 단순한 분할의 예
    • 스캔한 책의 영상 또는 컨베이어 벨트 위를 흐르는 물체의 영상-> 단순한 알고리즘도 좋은 성능을 보임
  • 영역 분할 알고리즘
    • 워터셰드 알고리즘 적용

슈퍼 화소 분할

  • 슈퍼 화소는 화소보다 크지만 물체보다 작은 자잘한 영역으로 과잉 분할
  • SLIC 알고리즘
    • k-평균 군집화와 비슷하게 동작
    • 화소 할당 단계 : 화소 근처 4개 군집 중심과의 거리를 계산해서 가장 가까운 곳으로 할당
    • 군집 중심 갱신하는 단계 : 화소의 평균으로 계산해서 군집 중심을 갱신
    • 군집의 중심의 이동량의 평균이 임계치 보다 작으면 수렴으로 판단하여 알고리즘 중단

SLIC알고리즘으로 슈퍼 화소 분할

import skimage
import numpy as np
import cv2 as cv

img = skimage.data.coffee()
cv.imshow('coffee image', cv.cvtColor(img, cv.COLOR_RGB2BGR))

slic1 = skimage.segmentation.slic(img, compactness = 20, n_segments = 600)
sp_img1 = skimage.segmentation.mark_boundaries(img, slic1)
sp_img1 = np.uint8(sp_img1*255.0)

slic2 = skimage.segmentation.slic(img, compactness = 40, n_segments = 600)
sp_img2 = skimage.segmentation.mark_boundaries(img, slic2)
sp_img2 = np.uint8(sp_img2*255.0)

cv.imshow('sp', cv.cvtColor(sp_img1, cv.COLOR_RGB2BGR))
cv.imshow('sp', cv.cvtColor(sp_img2, cv.COLOR_RGB2BGR))

cv.waitKey()
cv.destroyAllWindows()
  • slic함수로 슈퍼 화소 분할 수행, 결과를 slic1객체에 저장
    • compactness : 슈퍼 화소의 모양을 조절. 값이 클수록 네모에 가까운 모양이 만들어짐/ 슈퍼화소의 색상 균일성은 희생됨
    • n_segments : 슈퍼화소의 개수를 지정. 여기선 600개로 지정함
  • np.uint8 : 0~1사이의 실수로 표현된 sp_img1을 0~255 사이로 바꾸고 uint8형으로 변환

최적화 분할

  • 지금까지 분할 알고리즘은 지역적 명암 변화만 살피기 때문에 한계
  • 전역적 정보를 고려하여 문제 해결
    • 지역적으로 색상 변화가 약하지만 전역적으로 유리하다면 물체 경계로 간주
    • 영상을 그래프로 표현하고 최적화 알고리즘으로 분할 문제를 품
      • 슈퍼 화소를 대상으로 계산할 경우 대상이 되는 노드의 개수를 줄일 수 있음

영상의 그래프 표현

  • 화소 또는 슈퍼화소를 노드로 취함
  • 두 노드의 유사도를 계산하여 에지에 부여
    • f(v)는 v에 해당하는 화소의 색상(r, g, b)과 위치 (x, y)를 결합한 5차원 벡터
    • v가 슈퍼노드인 경우 화소의 평균을 사용
  • 두 노드의 거리 \(d_{pq} = \begin{cases}||f(v_p) - f(v_q)||,\ v_q \in neighbor(v_p) \\ \infty ,\ otherwise \end{cases}\)
  • 두 노드의 유사도 \(s_{pq} = \begin{cases}D - d_{pq} or 1/e^{d_{pq}},\ v_q \in neighbor(v_p) \\ 0,\ otherwise \end{cases}\)

  • 이 때 D는 \(d_{pq}\)의 가능한 최대값, \(neighbor(v_p)\)는 8연결성 또는 지정한 거리 \(\gamma\)이내의 값들의 집합

정규화 절단 알고리즘

  • cut은 다음과 같이 정의 \(cut(C_1,\ C_2) = \sum_{v_p \in C_1, v_q \in C_2}s_{pq}\)

  • 영상을 두 영역으로 분할했을 때 분할의 좋은 정도를 측정해 주는 목적 함수
    • 제대로 된 분할에서 C1에 속한 화소와 C2에 속한 화소의 유사도가 작고 함수의 결과값도 작아짐
    • C1과 C2가 클수록 cut값이 증가 -> cut을 사용한 분할 알고리즘은 영역을 자잘하게 분할하는 경향
  • ncut은 cut을 정규화하여 영역의 크기에 중립이 되게 해줌 \(ncut(C_1, C-2) = \frac{cut(C_1, C_2)}{cut(C_1, C)} + \frac{cut(C_1, C_2)}{cut(C_2, C)}\)
    • 식에서 \(C \equiv C_1 \cup C_2\)이고, 전체 영역에서 C1을 분할하는 것과 C2를 분할하는 것을 가중치로 사용하여 영역의 크기가 커지면 반영 비율이 적어지는 효과
  • ncut을 빨리 계산하는 효율적 알고리즘이 개발되어 있음
    • skimage.graph
정규화 절단 알고리즘
import skimage
import numpy as np
import cv2 as cv
import time

coffee = skimage.data.coffee()

start = time.time()
slic = skimage.segmentation.slic(coffee, compactness = 20, n_segments = 600, start_label = 1)

g = skimage.future.graph.rag_mean_color(coffee, slic, mode = 'similarity')
ncut = skimage.future.graph.cut_normalized(slic, g)
print(coffee.shape, time.time() - start)

marking = skimage.segementation.mark_boundaries(coffee, ncut)
ncut_coffee = np.uint8(marking*255.0)

cv.imshow('normalized', cv.cvtColor(ncut_coffee, cv.COLOR_RGB2BGR))

cv.waitKey()
cv.destroyAllWindows()
  • rag_mean_color : 슈퍼화소를 노드로 사용, similarity를 에지 가중치로 사용한 그래프를 구성하여 g객체에 저장
  • cut_normalized : slic1, g객체 정보를 이용하여 정규화 절단 수행
  • mark_boundaries : 경계선 주변에 색상 적용 -> 경계를 시각적으로 강조. 여기선 ncut을 활용하여 경계선을 그림

대화식 분할

  • 앞에서 다룬 분할 알고리즘은 영상 전체를 여러 개의 영역으로 분할
  • 때로 한 물체의 분할에만 관심이 있는 응용이 있음
    • 예) 특정 물체를 오려내고 다른 물체로 대치
    • 사용자가 초기 정보를 입력하면 반자동 분할해주는 여러 알고리즘이 있음

능동 외곽선(스네이크)

  • 물체 내부에 초기 곡선을 지정하면 곡선을 점점 확장하여 물체 외곽선으로 접근
  • 곡선이 꿈틀대변서 에너지가 최소인 상태를 찾아가기 때문에 스네이크라 칭함

곡선 표현 방법

  • 곡선을 표현하기 위해 스플라인 곡선을 고안
  • 스플라인은 주어진 점을 지나는 부드러운 곡선을 다항식으로 표현하는 것
  • 영상에너지, 내부에너지, 도메인 에너지로 구성

  • 식 \(E(g) = \displaystyle \sum_{l = 0}^n \left(e_{image}(g(l)) + e_{internal}(g(l)) + e_{domain}(g(l))\right)\)
  • 영역 분할을 최소 에너지를 갖는 곡선을 찾는 문제로 공식화 \(\hat{g} = \argmin_gE(g)\)
  • 사용자가 지정한 초기 곡선 g0에서 시작하여 g1, g2로 발전해 감

Williams의 알고리즘

  • Kass의 스네이크 알고리즘을 개선

GrabCut

네트워크 흐름

  • 여러 지점을 거치는 물이나 전기 흐름을 그래프로 표현하고 병목 지점을 찾아 흐름을 개선하는 문제
  • Greig는 네트워크 흐름 알고리즘을 여상 복원에 적용하여 컴퓨터 비전에 끌어들임
  • 이후 스테레오와 영역 분할 등에 널리 활용

GrabCut

  • 사용자가 붓으로 물체와 배경을 초기 지정
  • 붓으로 선택된 화소를 가지고 물체 히스토그램과 배경 히스토그램을 만듦
  • 나머지 화소들은 두 히스토그램과 유사성을 따져 물체일 확률과 배경일 확률을 추정
  • 이 확률 정보를 이용하여 물체 영역과 배경 영역을 갱신

영역 특징

특징의 불변성과 등변성

  • 변환을 해도 값이 변하지 않으면 불변성이 있는 특징
  • 변환에 따라 값이 따라 변하면 등변성이 있는 특징
  • 명암 변화에 둔감한 광도 불변성도 중요

    과업에 따라 특징을 선택하는 일이 중요

모멘트와 모양 특징

  • 영역 R의 모멘트 \(m_{qp}(R) = \sum_{y, x \in R}y^q x^p\)

  • 모멘트를 이용한 다양한 특징

    • 면적 : \(a = m_{00}\)
    • 중점 : \((\dot{y}, \dot{x}) = \left(\frac{m_{10}}{a}, \frac{m_{01}}{a}\right)\) \(\mu_{qp} = \sum_{(y, x) \in R}(y - \dot y)^q(x - \dot x)^p\)

    • 열분산 : \(v_{cc} = \frac{\mu_{20}}{a}\)
    • 행분산 : \(v_{rr} = \frac{\mu_{02}}{a}\)
    • 열행분산 : \(v_{rc} = \frac{\mu_{11}}{a}\)

영역의 둘레와 둥근 정도

  • 둘레 : \(p = n_{even} + n_{odd}\sqrt2\)
  • 둥근 정도 : \(r = \frac{4\pi a}{p^2}\)

주축의 방향

\(\theta = \frac{1}{2}arctan\left(\frac{2\mu_{11}}{\mu_{20} - \mu_{02}}\right)\)

텍스처 특징. 텍스처는 일정한 패턴의 반복

  • 에지 통계량으로 텍스처 특징을 측정 \(T_{edge} = (busy,mag(i), dir(j)),\ 0 \leq i \leq q - 1,\ 0 \leq j \leq 7\)
  • LBP(local binary pattern)와 LTP(local ternary pattern)
    • LBP는 중심 화소와 주위 화소의 명암 값을 비교해서 텍스처 측정. 256차원 특징 벡터
    • LTP는 작은 명암 변화에 민감한 LBP단점 개선. 512차원 특징 벡터