[Computer Vision] Trapped-ball Segmentation

👀 본 예제는 Window10의 VSCode, Python3.11.0로 작성되었습니다.

 

Trapped-ball Segmentation은 주로 만화 프레임과 같은 이미지에서 의미 있는 영역을 추출하는데 효과적인 비지도 이미지 분할 기법이다.

 

이 방법은 이미지의 경계선에 의해 정의된 닫힌 지역을 식별하고 이를 통해 이미지 내에서 분할을 수행한다.

 

이 알고리즘은 형태학적 연산을 사용하여 큰 폐쇄된 지역을 식별하고, 각 지역에 대해 고유한 값을 채우는 방식으로 작동한다.

 

동작 순서

1. 흑백 또는 색상이 없는 스케치 이미지를 타깃으로 준비한다.
2. 형태학적 연산(Morphological Operations)을 수행(침식(Erosion), 팽창(Dilation)하여 각 영역의 경계를 잘 드러내도록 한다.
3. 비교적 넓은 영역을 찾고, 특정 크기 또는 모양에 기반하여 영역을 필터링한다.
4. 찾아낸 영역은 고유한 값으로 채워지고, 이 과정을 통해 큰 지역들이 명확하게 시각화 된다.
5. 큰 영역들이 전부 채워지고, 더 작은 영역으로 세분화하면서 채우기를 반복한다. (이 작업은 초기 단계에 설정한 기준에 따라 반복하고, 모든 영역이 다 채워질 때까지 반복한다.)
6. 최종적으로 세분화된 이미지를 출력한다.

 

동작을 하나하나 따라가보자.

 

먼저 타깃 이미지를 Threshold로 흑백 이미지로 변경한다.

img = cv2.imread("./test.jpg",cv2.IMREAD_GRAYSCALE)
ret, binary = cv2.threshold(image, 220, 255, cv2.THRESH_BINARY)
unfilled = binary

 

형태학적 연산으로 경계를 잘 드러나게 처리한다.

def get_unfilled_point(image: np.ndarray)->np.ndarray:
    """값이 255인 영역(빈 영역)에 해당하는 포인트를 가져온다.

    # 인자
        image: 처리할 이미지.

    # 반환 값
        빈 영역(선화가 없는 영역)에 대한 포인트 배열.
    """
    y, x = np.where(image == 255) # 이미지에서 값이 255인 픽셀의 x,y 좌표를 찾는다.

    return np.stack((x.astype(int), y.astype(int)), axis=-1) # x,y 좌표를 결합하여 포인트 배열을 생성한다.

def exclude_area(image:np.ndarray, radius)->np.ndarray:
    """이미지에서 경계에 가까운 포인트를 제외하기 위해 침식을 수행한다.
    팽창 후 시드 포인트를 사용하여 영역을 채우고자 한다.
    시드 포인트가 경계 근처에 있을 경우, 채우기 결과에 포함되지 않을 수 있으며,
    다음 채우기 작업을 위한 유효한 포인트가 되지 않을 수 있다. 따라서,
    이러한 포인트는 침식을 통해 무시한다.

    # Arguments
        image: 이미지
        radius: 구형 구조 요소의 반지름

    # Returns
        침식된 이미지
    """
    return cv2.morphologyEx(image, cv2.MORPH_ERODE, get_ball_structuring_element(radius), anchor=(-1, -1), iterations=1)

 

그리고 큰영역을 찾기 위해 구형 구조 요소를 만들고 영역을 탐색한다.

def get_ball_structuring_element(radius:int)->np.ndarray:
    """특정 반지름을 가진 구형 구조 요소를 가져오는 함수.
    이 구조 요소는 형태학적 작업(morphology operation)에서 사용된다.
    구의 반지름은 일반적으로 (leaking_gap_size / 2)와 같다.

    # Arguments
        radius: 구형 구조 요소의 반지름 
             
    # Returns
        구형 구조 요소의 배열
    """
    return cv2.getStructuringElement(cv2.MORPH_ELLIPSE, (2 * radius + 1, 2 * radius + 1))

def trapped_ball_fill_single(image:np.ndarray, seed_point:tuple[int,int], radius:int)->np.ndarray:
    """단일 Trapped-ball 채우기 작업을 수행하는 함수
    
    Flood Fill : 다차원 배열의 어떤 칸과 연결된 영역을 찾는 알고리즘.

    # Arguments
        image: 흰색(빈 영역) 배경의 검은(채워진) 선화를 가진 이미지
        seed_point: 갇힌 공 채우기용 시드 포인트, 튜플 형식(int,int)
        radius: 구형 구조 요소의 반지름
    # Returns
        채운 이미지
    """
    ball = get_ball_structuring_element(radius) # radius로 구형 구조 요소 생성

    pass1 = np.full(image.shape, 255, np.uint8) # 전체가 흰색인 배열
    pass2 = np.full(image.shape, 255, np.uint8) # 전체가 흰색인 배열

    im_inv = cv2.bitwise_not(image) # 이미지 색상 반전

    # Flood fill 수행
    mask1 = cv2.copyMakeBorder(im_inv, 1, 1, 1, 1, cv2.BORDER_CONSTANT, 0) # 경계 추가
    _, pass1, _, _ = cv2.floodFill(pass1, mask1, seed_point, 0, 0, 0, 4) # flood fill

    # 이미지 팽창(dilation) 수행, 갭 사이의 영역이 분리됨.
    pass1 = cv2.morphologyEx(pass1, cv2.MORPH_DILATE, ball, anchor=(-1, -1), iterations=1)
    mask2 = cv2.copyMakeBorder(pass1, 1, 1, 1, 1, cv2.BORDER_CONSTANT, 0) # 경계 추가

    # 다시 시드 포인트로 Flood fill 수행하여 하나의 채움 영역 선택
    _, pass2, _, rect = cv2.floodFill(pass2, mask2, seed_point, 0, 0, 0, 4)
    # 채움 결과에 대하 침식(erosion) 수행하여 누수 방지 채움
    pass2 = cv2.morphologyEx(pass2, cv2.MORPH_ERODE, ball, anchor=(-1, -1), iterations=1)

    return pass2
    
def trapped_ball_fill_multi(image:np.ndarray, radius:int, method:str='mean', max_iter:int=1000)->np.ndarray:
    """여러번의 갇힌 공 채우기(Trapped-Ball Fill) 작업을 수행하여 모든 유효한 영역을 채운다.

    # Arguments
        image: 흰색(빈 영역) 배경의 검은(채워진) 선화를 가진 이미지
        radius: 구형 구조 요소의 반지름
        method: 채우기 결과 필터링 방법 
               'max' 는 일반적으로 큰 반지름을 사용하여 같은 큰 영역을 선택
        max_iter: 최대 반복 횟수
    # Returns
        채운 포인트 배열
    """

    unfill_area = image # 채우지 않은 영역을 우너본 이미지로 초기화
    filled_area, filled_area_size, result = [], [], []

    for _ in range(max_iter):
        # 경계에 가까운 포인트를 제외한 후 빈 영역의 포인트를 가졍옴
        points = get_unfilled_point(exclude_area(unfill_area, radius)) 

        # 빈 포인트가 없으면 종료
        if not len(points) > 0:
            break
        # 첫 번째 포인트를 기준으로 Trapped-Ball Fill 수행
        fill = trapped_ball_fill_single(unfill_area, (points[0][0], points[0][1]), radius)
        # 채운 영역과 원본 이미지의 비트 AND 연산 수행
        unfill_area = cv2.bitwise_and(unfill_area, fill)
        # 채운 영역의 포인트를 저장
        filled_area.append(np.where(fill == 0))
        filled_area_size.append(len(np.where(fill == 0)[0]))

    filled_area_size = np.asarray(filled_area_size) # 채운 영역의 크기를 배열로 받음


    # 필터링
    """
    ## max
    - 채운 영역의 크기 중 최대값을 기준으로 필터링, 가장 큰영역을 선택하여 결과에 포함, 그보다 작은 영역은 제외
    - 일반적으로 큰 반지름을 사용할 때 유용하며, 배경 같은 큰 영역을 선택할 때 적합
    - 이 방법은 노이즈가 작은 채움 결과를 무시하고, 주요 채운 영역만을 추출하고자 할 때 사용

    ## median
    - 채운 영역의 크기 중 중앙값을 기준으로 필터링, 중앙값은 배열을 정렬했을 때, 중간값에 위치한 값
    - 극단적인 값에 덜 영향을 받기 때문에, 이상치가 있는 경우에도 안정적인 결과를 제공
    - 다양한 크기의 채운 영역이 존재할 때, 중간 정도의 크기를 가진 영역을 선택하고자 할 때 사용
    - 크기가 매우 작은 영역과 매우 큰 영역이 혼재할 때, 중간 규모의 채운 영역을 선택하는 데 유용

    ## mean
    - 채운 영역의 크기 평균값을 기준으로 필터링
    - 모든 채운영역의 크기를 더한 후, 채운 영역의 개수로 나눈 값을 사용하여 필터링 기준을 설정
    - 평균적인 크기를 가진 채운 영역을 선택하고자 할 때 사용
    - 전체적인 채운 결과의 크기가 비슷할 때 적합하며, 크기가 크게 차이나지 않는 경우에 유용
    
    """
    if method == 'max':
        area_size_filter = np.max(filled_area_size)
    elif method == 'median':
        area_size_filter = np.median(filled_area_size)
    elif method == 'mean':
        area_size_filter = np.mean(filled_area_size)
    else:
        area_size_filter = 0

    # 필터링된 영역의 인덱스를 찾는다.
    result_idx = np.where(filled_area_size >= area_size_filter)[0]

    # 필터링 결과 리스트에 추가
    for i in result_idx:
        result.append(filled_area[i])

    return result # 채운 포인트의 배열 반환

 

더 작은 영역을 세분화 하면서 작업한다.

 

import cv2
import numpy as np


img = cv2.imread("./test.jpg",cv2.IMREAD_GRAYSCALE)
ret, binary = cv2.threshold(image, 220, 255, cv2.THRESH_BINARY)
unfilled = binary
radius = radius

fills = []
for idx, method in enumerate(methods):
   fill = trapped_ball_fill_multi(image=unfilled,radius=3,method=method)
   fills+=fill
   unfilled = mark_fill(unfilled,fills)

   fill = flood_fill_multi(unfilled)
   fills += fill

   fillmap = build_fill_map(unfilled, fills)
   fillmap = merge_fill(fillmap)
   cv2.imshow(str(idx),unfilled)

 

이렇게 채운 영역 맵을 id를 줘서 분할 한다.

이렇게 하면 영역별로 구분이 된다.

def build_fill_map(image: np.ndarray, fills: list) -> np.ndarray:
    """각 픽셀을 채운 영역의 ID로 표시하는 배열을 생성하는 함수.

    # Arguments
        image: 처리할 이미지.
        fills: 채운 영역의 포인트 배열. 각 포인트는 (y, x) 형태의 좌표를 포함해야 함.
    
    # Returns
        각 픽셀에 채운 영역의 ID가 표시된 배열.
    """
    result = np.zeros(image.shape[:2], np.int_)  # 결과 배열 초기화, 모든 값은 0

    for index, fill in enumerate(fills):
        result[fill] = index + 1  # 채운 영역의 ID로 표시

    return result  # 결과 배열 반환

 

그리고 이 채움 맵을 영역 병합을 하면서 영역 세분화를 반복한다.

def get_bounding_rect(points:np.ndarray)->tuple:
    """주어진 포인트 집합의 최소 및 최대 x,y 좌표를 기반으로 경계 사각형을 계산

    # Arguments
        points: (y,x) 형태의 배열
    # Returns
        사각형 형태의 경계 사각형 좌표
    """
    x1, y1, x2, y2 = np.min(points[1]), np.min(points[0]), np.max(points[1]), np.max(points[0])
    return (x1, y1, x2, y2)

def get_border_bounding_rect(h:int, w:int, p1:tuple, p2:tuple, r:int)->tuple:
    """ 주어진 경계 사각형에 특정 크기의 여백을 추가하여 유효한 경계 사각형을 계산 
    경계가 이미지의 크기를 초과하지 않도록 조정

    # Arguments
        h: 이미지의 최대 높이
        w: 이미지의 최대 너비
        p1: 경계 사각형의 시작 점
        p2: 경계 사각형의 끝 점
        r: 여백의 반경
    # Returns
        여백이 추가된 경계 사각형의 좌표를 반환
    """
    x1, y1, x2, y2 = p1[0], p1[1], p2[0], p2[1]

    x1 = x1 - r if 0 < x1 - r else 0
    y1 = y1 - r if 0 < y1 - r else 0
    x2 = x2 + r + 1 if x2 + r + 1 < w else w
    y2 = y2 + r + 1 if y2 + r + 1 < h else h

    return (x1, y1, x2, y2)

def get_border_point(points:list, rect:tuple, max_height:int, max_width:int)->tuple:
    """주어진 포인트의 경계 포인트와 그 형태를 계산 
    경계 사각형에 여백을 추가하고, 해당 영역에서 경계 픽셀을 추출

    # Arguments
        points: 채운 영역의 포인트
        rect: 채운 영역의 경계 사각형
        max_height: 이미지 최대 높이
        max_width: 이미지 최대 너비
    # Returns
        경계 픽셀 좌표와 포인트의 다각형 형태를 반환
    """
    # Get a local bounding rect.
    border_rect = get_border_bounding_rect(max_height, max_width, rect[:2], rect[2:], 2)

    # Get fill in rect.
    fill = np.zeros((border_rect[3] - border_rect[1], border_rect[2] - border_rect[0]), np.uint8)
    # Move points to the rect.
    fill[(points[0] - border_rect[1], points[1] - border_rect[0])] = 255

    # Get shape.
    contours, _ = cv2.findContours(fill, cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE)
    approx_shape = cv2.approxPolyDP(contours[0], 0.02 * cv2.arcLength(contours[0], True), True)

    # Get border pixel.
    cross = cv2.getStructuringElement(cv2.MORPH_CROSS, (3, 3))
    border_pixel_mask = cv2.morphologyEx(fill, cv2.MORPH_DILATE, cross, anchor=(-1, -1), iterations=1) - fill
    border_pixel_points = np.where(border_pixel_mask == 255)

    # Transform points back to fillmap.
    border_pixel_points = (border_pixel_points[0] + border_rect[1], border_pixel_points[1] + border_rect[0])

    return border_pixel_points, approx_shape

def merge_fill(fillmap: np.ndarray, max_iter: int = 10) -> np.ndarray:
    """채운 영역 병합 함수.

    # Arguments
        fillmap: 채운 영역 ID가 표시된 이미지.
        max_iter: 최대 반복 횟수.
    
    # Returns
        병합된 채운 영역 이미지.
    """
    max_height, max_width = fillmap.shape[:2]
    result = fillmap.copy()  # 결과 배열 초기화

    for i in range(max_iter):

        result[np.where(fillmap == 0)] = 0  # 빈 영역은 0으로 설정

        fill_id = np.unique(result.flatten())  # 현재 채운 영역 ID 추출
        fills = []

        for j in fill_id:
            point = np.where(result == j)
            fills.append({
                'id': j,
                'point': point,
                'area': len(point[0]),
                'rect': get_bounding_rect(point)
            })

        for j, f in enumerate(fills):
            # 라인 ID는 무시
            if f['id'] == 0:
                continue

            border_points, approx_shape = get_border_point(f['point'], f['rect'], max_height, max_width)
            border_pixels = result[border_points]
            pixel_ids, counts = np.unique(border_pixels, return_counts=True)

            ids = pixel_ids[np.nonzero(pixel_ids)]
            new_id = f['id']
            if len(ids) == 0:
                # 주변에 색상이 변경된 라인으로 둘러싸인 경우
                if f['area'] < 5:
                    new_id = 0
            else:
                # 가장 접촉이 많은 영역의 ID로 설정
                new_id = ids[0]

            # 조건에 따라 ID 업데이트
            if len(approx_shape) == 1 or f['area'] == 1:
                result[f['point']] = new_id

            if len(approx_shape) in [2, 3, 4, 5] and f['area'] < 500:
                result[f['point']] = new_id

            if f['area'] < 250 and len(ids) == 1:
                result[f['point']] = new_id

            if f['area'] < 50:
                result[f['point']] = new_id

        # 변화가 없으면 종료
        if len(fill_id) == len(np.unique(result.flatten())):
            break

    return result  # 병합된 결과 반환

 

최종적으로 기존 선화 이미지에서 선화를 지우고 영역별로 다른 색으로 칠하여 밑색을 반환 한다.

def thinning(fillmap: np.ndarray, max_iter: int = 100) -> np.ndarray:
    """선 영역을 주변 채운 색상으로 채우는 함수.

    # Arguments
        fillmap: 채운 영역 ID가 표시된 이미지.
        max_iter: 최대 반복 횟수.

    # Returns
        채운 후의 이미지.
    """
    line_id = 0  # 기본 선 ID
    h, w = fillmap.shape[:2]  # 이미지 높이와 너비
    result = fillmap.copy()  # 결과를 저장할 배열 초기화

    for iterNum in range(max_iter):
        # 선의 포인트를 찾기. 포인트가 없으면 종료.
        line_points = np.where(result == line_id)
        if not len(line_points[0]) > 0:
            break

        # 선과 채운 영역 사이의 포인트를 찾기.
        line_mask = np.full((h, w), 255, np.uint8)  # 선 마스크 초기화
        line_mask[line_points] = 0  # 선의 포인트를 0으로 설정
        line_border_mask = cv2.morphologyEx(line_mask, cv2.MORPH_DILATE,
                                             cv2.getStructuringElement(cv2.MORPH_CROSS, (3, 3)), anchor=(-1, -1),
                                             iterations=1) - line_mask  # 선의 경계 포인트 찾기
        line_border_points = np.where(line_border_mask == 255)  # 경계 포인트 찾기

        result_tmp = result.copy()  # 임시 결과 배열 생성
        # 각 경계 포인트를 주변 채운 영역의 ID로 채움
        for i, _ in enumerate(line_border_points[0]):
            x, y = line_border_points[1][i], line_border_points[0][i]

            # 주변 픽셀을 확인하여 채움
            if x - 1 > 0 and result[y][x - 1] != line_id:
                result_tmp[y][x] = result[y][x - 1]
                continue

            if x - 1 > 0 and y - 1 > 0 and result[y - 1][x - 1] != line_id:
                result_tmp[y][x] = result[y - 1][x - 1]
                continue

            if y - 1 > 0 and result[y - 1][x] != line_id:
                result_tmp[y][x] = result[y - 1][x]
                continue

            if y - 1 > 0 and x + 1 < w and result[y - 1][x + 1] != line_id:
                result_tmp[y][x] = result[y - 1][x + 1]
                continue

            if x + 1 < w and result[y][x + 1] != line_id:
                result_tmp[y][x] = result[y][x + 1]
                continue

            if x + 1 < w and y + 1 < h and result[y + 1][x + 1] != line_id:
                result_tmp[y][x] = result[y + 1][x + 1]
                continue

            if y + 1 < h and result[y + 1][x] != line_id:
                result_tmp[y][x] = result[y + 1][x]
                continue

            if y + 1 < h and x - 1 > 0 and result[y + 1][x - 1] != line_id:
                result_tmp[y][x] = result[y + 1][x - 1]
                continue

        result = result_tmp.copy()  # 최종 결과 업데이트

    return result  # 채운 후의 이미지 반환

def show_fill_map(fillmap: np.ndarray) -> np.ndarray:
    """채운 영역을 색상으로 표시하여 시각화하는 함수.

    # Arguments
        fillmap: 채운 영역 ID가 포함된 이미지 배열.

    # Returns
        색상이 적용된 이미지 배열.
    """
    # 각 채운 영역에 대해 랜덤 색상 생성
    colors = np.random.randint(0, 255, (np.max(fillmap) + 1, 3))
    # 선의 ID는 0이며, 그 색상은 검정색으로 설정
    colors[0] = [0, 0, 0]

    return colors[fillmap]  # 색상이 적용된 이미지 반환

fill = show_fill_map(thinning(fillmap))
cv2.imshow("fill",cv2.convertScaleAbs(fill))

 

 

GitHub - pupba/Trapped-Ball-Segmentation: Trapped-Ball-Segmentation

여기서 모든 코드를 확인할 수 있다.