Crazy Lazy Coder

2020.04.20 - [영상처리] - Canny Edge Detection (Python)

예전에 개발한 Canny Edge Detection을 수정한 버전이다.

코드

수정된 코드는 Convolution 부분을 행렬연산으로 치환하여 더 빠른 속도를 보여준다.

이전의 코드는 Convolution시 영상 내부의 픽셀에 대해서만 연산을 수행했기 때문에, Kernel크기가 커지면 영상 테두리 쪽의 일부 픽셀은 무시되었다.

수정한 코드는 Zero-padding을 Kernel 크기 별로 원본 영상에 추가하여 연산을 수행하므로 모든 픽셀을 Convolution에 포함시킨다.

import cv2 as cv
import numpy as np

def DistanceTransform(img):
    assert type(img) is np.ndarray, 'Image was not a ndarray!'
    n_img = img.copy()
    _, n_img = cv.threshold(n_img,127,1,cv.THRESH_BINARY)
    
    # forward
    for i in range(1,n_img.shape[0]-1):
        for j in range(1,n_img.shape[1]-1):
            if n_img.item(i,j) == 1:
                if n_img.item(i-1,j) == 0 and n_img.item(i,j-1) == 0:
                    n_img.itemset(i,j,1)
                else:
                    value = np.min([n_img.item(i-1,j),n_img.item(i,j-1)]) + 1
                    n_img.itemset(i,j,value)

    #backward
    for i in range(1,n_img.shape[0]-1)[::-1]:
        for j in range(1,n_img.shape[1]-1)[::-1]:
            if n_img.item(i,j) >= 1:
                if n_img.item(i+1,j) == 0 and n_img.item(i,j+1) == 0:
                    n_img.itemset(i,j,1)
                else:
                    value = np.min([n_img.item(i+1,j),n_img.item(i,j+1)]) + 1
                    value = np.min([value,n_img.item(i,j)])
                    n_img.itemset(i,j,value)
    return n_img

if __name__ == "__main__":
    img = cv.imread('test.jpg')
    img = cv.cvtColor(img,cv.COLOR_BGR2GRAY)
    new_img = DistanceTransform(img)
    new_img *= 5 # 픽셀값이 1씩 차이나면 잘 안보이므로 5를 곱해줌
    cv.imshow('roi',img)
    cv.imshow('res',new_img)
    cv.waitKey(0)
    cv.destroyAllWindows()

Distance Transform을 구현한 프로그램이다.

Distance Transform은 Binary Image에서 픽셀이 배경에서 멀어질수록,

픽셀이 점점 더 큰 값을 지니게 바꾸는 것이다.

4-연결성과 8-연결성으로 방법이 나뉘는데, 여기서는 4-연결성을 구현하였다.

실행 결과는 다음과 같다.

import cv2 as cv
import numpy as np
import random
import math
import copy

roi = cv.imread('sunflower.png') # 이미지 불러오기

k = 6 # 분류될 군집의 갯수

Z = [] # 각 군집의 대표값
X = [] # 샘플 집합. 여기서는 이미지픽셀
Z_xlist = [] # 각 군집에 해당되는 샘플을 저장할 리스트
prev_list = [] # 리스트의 이전상태를 기록할 리스트

for i in range(roi.shape[0]):
    for j in range(roi.shape[1]):
        x = (roi.item(i,j,0),roi.item(i,j,1),roi.item(i,j,2),(i,j)) # 이미지의 각 픽셀의 rgb값+이미지 좌표로 저장
        X.append(x) # 샘플리스트에 저장

checked = [] # 좌표 중복을 방지하기 위한 리스트
for i in range(k): # K개의 군집 초기화
    while True: # 랜덤하게 한 좌표를 뽑아서 Z를 초기화
        iy = random.randint(0,roi.shape[0]-1)
        ix = random.randint(0,roi.shape[1]-1)
        if (iy,ix) not in checked: # 체크한 좌표가 아니면 기록후 무한반복 탈출
            checked.append((iy,ix))
            break
    pos = checked[-1] # 방금 찾은 좌표로 설정
    value = ((roi.item(pos[0],pos[1],0),roi.item(pos[0],pos[1],1),roi.item(pos[0],pos[1],2)),(0,0,0))
    # Z 값은 방금 찾은 좌표의 rgb값 + 각 rgb의 총합(초기에는 0)
    Z.append(value)
    Z_xlist.append([]) # 각 군집에 해당되는 x는 아직 없음

while True:
    for x in X: # 모든 샘플에 대해 검사
        z_list = [] # 각 군집 대표값과 샘플의 유사성을 저장할 리스트
        for z in Z: # 각 군집 대표값과 유사성 측정후 저장
            dist = math.sqrt((x[0] - z[0][0])**2 + (x[1] - z[0][1])**2 + (x[2] - z[0][2])**2)
            # 유클리드 거리로 색의 유사성을 측정했으므로 0에 가까울수록 유사함.
            z_list.append(dist)
        idx = z_list.index(min(z_list)) # 최소값이 가장 유사한 군집
        z_value, z_sum = Z[idx] # 군집 대표값, 총합 가져옴
        z_sum = (z_sum[0] + x[0],z_sum[1] + x[1],z_sum[2] + x[2]) # x의 픽셀값을 총합에 더함
        Z[idx] = (z_value,z_sum) # 군집 갱신. 총합만 달라짐
        Z_xlist[idx].append(x) # 샘플을 해당 군집에 저장
    if prev_list == Z_xlist: # 탈출조건; 군집리스트가 변화가 없으면 알고리즘을 중단.
        break
    prev_list = copy.deepcopy(Z_xlist) # 군집 리스트변화를 측정하기 위해 현재 리스트 기록
    for idx, z in enumerate(Z): # 각 Z값 갱신
        z_value, z_sum = z
        z_value = (z_sum[0] / len(Z_xlist[idx]),
        z_sum[1] / len(Z_xlist[idx]),
        z_sum[2] / len(Z_xlist[idx])
        ) # 대표값은 각 채널값의 평균.
        z = (z_value, (0,0,0)) # 다시 샘플들을 검사해야하므로 총합은 0이고 대표값만 수정
    Z_xlist.clear() # 샘플리스트 초기화
    for i in range(k):
        Z_xlist.append([])

result = np.zeros((roi.shape[0],roi.shape[1],roi.shape[2]),dtype=np.uint8) # 결과이미지

for idx, xlist in enumerate(Z_xlist):
    rand = random.Random()
    rand.seed(idx*10) # 일정한 색 출력을 위해 시드 고정. 시드값은 K의 인덱스 * 10
    b = rand.randint(0,255)
    g = rand.randint(0,255)
    r = rand.randint(0,255)
    for x in xlist: # 해당 군집의 샘플의 위치를 알아내서 군집색으로 표시
        i, j = x[3] 
        result.itemset(i,j,0,b)
        result.itemset(i,j,1,g)
        result.itemset(i,j,2,r)

cv.imshow('roi',roi) # 기존 이미지
cv.imshow('res',result) # 군집화된 이미지
cv.waitKey(0)
cv.destroyAllWindows()

K-Means 알고리즘을 적용하여 컬러영상을 분할하는 프로그램이다.

6개의 군집으로 이미지 화소들을 분할한다.

import cv2 as cv
import numpy as np
import math
import queue

SIGMA = 1.0
LOW_T = 0.25 * 255
HIGH_T = 0.1 * 255

def gauss(y,x,sigma):
    value = math.exp(-(x**2+y**2)/(2*sigma**2))
    return value/(2*math.pi*sigma**2)

SOBEL_Y = np.array([
    [-1,-2,-1],
    [0,0,0],
    [1,2,1]
])
SOBEL_X = np.array([
    [-1,0,1],
    [-2,0,2],
    [-1,0,1]
])

DIRECTION_LIST = [(-1,0,1,0),(-1,1,1,-1),(0,1,0,-1),(-1,-1,1,1)]
yx_list = [(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]

FILTER_SIZE = int(SIGMA*6)
if FILTER_SIZE % 2 == 0:
    FILTER_SIZE += 1
print('filtersize : ',FILTER_SIZE)
ROI = cv.imread('1.jpg')
ROI_GRAY = cv.cvtColor(ROI,cv.COLOR_BGR2GRAY)

map_dy = np.zeros((ROI_GRAY.shape[0],ROI_GRAY.shape[1]))
map_dx = np.zeros((ROI_GRAY.shape[0],ROI_GRAY.shape[1]))

mag_map = np.zeros((ROI_GRAY.shape[0],ROI_GRAY.shape[1]))
dir_map = np.zeros((ROI_GRAY.shape[0],ROI_GRAY.shape[1]),dtype=np.uint8)

gaussblurred = np.zeros((ROI_GRAY.shape[0],ROI_GRAY.shape[1]))

edge_map = np.zeros((ROI_GRAY.shape[0],ROI_GRAY.shape[1]))
visited = np.zeros((ROI_GRAY.shape[0],ROI_GRAY.shape[1]))

gauss_filter = np.zeros((FILTER_SIZE,FILTER_SIZE))
SIZE = int(FILTER_SIZE//2)

# 가우시안 필터를 구함
for x in range(FILTER_SIZE):
    for y in range(FILTER_SIZE):
        # a = math.exp(-(((y-(FILTER_SIZE//2))**2) + ((x-(FILTER_SIZE//2))**2))/2*SIGMA**2)
        # b = 1/(2* math.pi * SIGMA**2)
        gauss_value = gauss(x-SIZE,y-SIZE,SIGMA)
        gauss_filter.itemset(x,y,gauss_value)
print('gaussian filter has been created.')
# 가우시안 필터를 적용시켜 노이즈 제거
for i in range(SIZE,ROI_GRAY.shape[0]-SIZE):
    for j in range(SIZE,ROI_GRAY.shape[1]-SIZE):
        value = 0.0
        for r in range(-SIZE,SIZE+1):
            for c in range(-SIZE,SIZE+1):
                value += gauss_filter.item(r+SIZE,c+SIZE) * ROI_GRAY.item(i+r,j+c)
        gaussblurred.itemset(i,j,value)
print('blurred_img has been created.')
# 소벨 필터를 사용하여 엣지검출
for i in range(1,gaussblurred.shape[0]-1):
    for j in range(1,gaussblurred.shape[1]-1):
        value1 = 0.0
        value2 = 0.0
        for r in range(-1,2):
            for c in range(-1,2):
                value1 += SOBEL_X.item(r+1,c+1) * gaussblurred.item(i+r,j+c)
                value2 += SOBEL_Y.item(r+1,c+1) * gaussblurred.item(i+r,j+c)
        map_dx.itemset(i,j,value1)
        map_dy.itemset(i,j,value2)
print('edge has been created.')
# x축과 y축으로 검출된 엣지를 사용하여 각 픽셀에서의 그래디언트 크기와 방향을 구함
for i in range(gaussblurred.shape[0]):
    for j in range(gaussblurred.shape[1]):
        magnitude = math.sqrt(map_dx.item(i,j)**2 +map_dy.item(i,j)**2)
        direction = math.atan2(map_dy.item(i,j),map_dx.item(i,j)) + 90 # 엣지방향은 그래디언트 방향에 수직
        direction = (direction/360)*8
        mag_map.itemset(i,j,magnitude)
        dir_map.itemset(i,j,direction)
print('gradient has been computed.')
# 비최대억제를 통해 가짜 엣지를 제거함
'''
비최대 억제의 경우 자신 주변의 픽셀(엣지 방향에 따라 참조픽셀 위치가 다름)들 보다 
그래디언트 크기가 작으면 엣지에서 제외함.
'''
for i in range(1,gaussblurred.shape[0]-1):
    for j in range(1,gaussblurred.shape[1]-1):
        y1,x1,y2,x2 = DIRECTION_LIST[int(dir_map.item(i,j))%4]
        y1 += i
        x1 += j
        y2 += i
        x2 += j
        if mag_map.item(i,j) <= mag_map.item(y1,x1) or mag_map.item(i,j) <= mag_map.item(y2,x2):
            mag_map.itemset(i,j,0)
print('fake edges have been deleted.')

# def follow_edge(y,x):
#     visited.itemset(y,x,1)
#     edge_map.itemset(y,x,255)
#     for y1,x1 in yx_list:
#         if mag_map.item(y1+y,x1+x)>LOW_T and visited.item(y1+y,x1+x) == 0:
#             follow_edge(y1+y,x1+x)

# 이력임계값을 사용하여 엣지 추정
'''
이력임계값은 우선 엣지일 확률이 높은(임계값T_high보다 큰)곳에서 엣지추적을 시작함.
그 주변 엣지들을 대상으로 픽셀이 T_low보다 큰값을 가지면 엣지로 간주.
'''
Q = queue.Queue()
for i in range(1,edge_map.shape[0]-1):
    for j in range(1,edge_map.shape[1]-1):
        if mag_map.item(i,j) > HIGH_T and visited.item(i,j) == 0:
            # follow_edge(i,j)
            Q.put((i,j))
            while not Q.empty():
                y, x = Q.get()
                visited.itemset(y,x,1)
                edge_map.itemset(y,x,255)
                for y1,x1 in yx_list:
                    if mag_map.item(y1+y,x1+x)>LOW_T and visited.item(y1+y,x1+x) == 0:
                        visited.itemset(y1+y,x1+x,1)
                        edge_map.itemset(y1+y,x1+x,255)
                        Q.put((y+y1,x+x1))
print('found edges.')

cv.imshow('canny_edge',edge_map)
cv.waitKey(0)
cv.destroyAllWindows()

Canny Edge Detection 알고리즘을 사용하여 최대한 low level로 구현해본 파이썬 프로그램이다. 

이해가 완벽하지 않은 상태에서 구현한 것이기 때문에, 그럴싸한 결과가 출력되지만 완벽한지 검증하지는 못했다.

또한 참고한 책에서 재귀 호출로 알고리즘이 소개되어 있었는데, 이를 적용하니 Stack Overflow가 발생하여 Queue를 사용하는 방식으로 바꾸었다.

다만 최적화는 고려하지 않았기 때문에, 그 때문에 처리 속도가 매우 느리다.

import cv2 as cv
import numpy as np
import math

roi = cv.imread('picture6.jpg')

angle = 10.0

angle = angle* math.pi/180

normal_rotation = np.zeros((roi.shape[0],roi.shape[1],3),dtype=np.uint8)
normal_interpolation = np.zeros((roi.shape[0],roi.shape[1],3),dtype=np.uint8)
bilinear_interpolation = np.zeros((roi.shape[0],roi.shape[1],3),dtype=np.uint8)

for i in range(roi.shape[0]):
    for j in range(roi.shape[1]):
        for k in range(3):
            cy = roi.shape[0] // 2
            cx = roi.shape[1] // 2
            y = i - cy
            x = j - cx
            newY = y * math.cos(angle) - x * math.sin(angle) + cy
            newX = y * math.sin(angle) + x * math.cos(angle) + cx
            newY = round(newY)
            newX = round(newX)
            if newX >=0 and newX < roi.shape[1] and newY >=0 and newY < roi.shape[0]:
                normal_rotation.itemset(newY,newX,k,roi.item(i,j,k))

for i in range(roi.shape[0]):
    for j in range(roi.shape[1]):
        for k in range(3):
            cy = roi.shape[0] // 2
            cx = roi.shape[1] // 2
            y = i - cy
            x = j - cx
            newY = y * math.cos(angle) + x * math.sin(angle) + cy
            newX = y * -math.sin(angle) + x * math.cos(angle) + cx
            newY = round(newY)
            newX = round(newX)
            if newX >=0 and newX < roi.shape[1] and newY >=0 and newY < roi.shape[0]:
                normal_interpolation.itemset(i,j,k,roi.item(newY,newX,k))

for i in range(roi.shape[0]):
    for j in range(roi.shape[1]):
        for k in range(3):
            cy = roi.shape[0] // 2
            cx = roi.shape[1] // 2
            y = i - cy
            x = j - cx
            newY = y * math.cos(angle) + x * math.sin(angle) + cy
            newX = y * -math.sin(angle) + x * math.cos(angle) + cx
            alpha = 1 - (newX-math.floor(newX))
            beta = 1 - (newY-math.floor(newY))
            newX = round(newX)
            newY = round(newY)
            if newX >=0 and newX < roi.shape[1]-1 and newY >=0 and newY < roi.shape[0]-1:
                f1 = (1-alpha)*roi.item(newY,newX,k)+alpha*roi.item(newY,newX+1,k)
                f2 = (1-alpha)*roi.item(newY+1,newX,k)+alpha*roi.item(newY+1,newX+1,k)
                f3 = (1-beta)*f1+beta*f2
                bilinear_interpolation.itemset(i,j,k,int(f3))

cv.imshow('origin',roi)
cv.imshow('rotation_normal',normal_rotation)
cv.imshow('interpolation_normal',normal_interpolation)
cv.imshow('interpolation_bilinear',bilinear_interpolation)
cv.waitKey(0)
cv.destoryAllWindows()

파이썬 opencv라이브러리를 통해 구현한 이미지 회전 프로그램.

공부의 목적으로 직접 픽셀에 접근하여 회전하게 하였다.

출력되는 사진은 원본, 일반회전, 최근접이웃, 양선형보간법 순으로 되어있다.