[Python] 사천성 알고리즘 - 거상 사천성 적용

1. 개요

 사천성 게임을 사진으로 가져와 분석하고 사천성을 해결하는 프로그램입니다. 사천성 이미지는 거상의 작업장 이미지를 사용하였으며 이후 거상 작업장 메크로 프로젝트에 사용할 예정입니다.

개인적인 요청인해 사천성 입력 사진 파일도 올립니다.

이미지 추출 및 데이터화 소스 코드 : get_Sichuan_Data.py

입력 데이터 : img_sichuan.zip

사천성 알고리즘 통합 소스 코드 : Sichuan.py

2. 이미지 추출

 우선 기존 사천성 이미지 입니다.

 해당 프로젝트에서 이미지를 다루기 위해 opencv를 사용하였습니다.  그런데 openve로 불러온 이미지 파일을 출력해보면 파란 빛을 띱니다. 이 부분은 정확인 이유를 잘 모르겠습니다. 아마 제가 잘못한 것이 있을 것이라 생각합니다.

import cv2 import cv2 import numpy as np import matplotlib.pyplot as plt import math img = cv2.imread("./four.png") plt.figure(figsize=(15,12)) plt.imshow(img);

 

크기를 자르고 색상을 반전시켜줍니다.

img = img[241:578, 288:737] img = ~img plt.figure(figsize=(10,10)) plt.imshow(img);

 흑백화와 GaussianBlur 필터를 씨워줍니다. GaussianBlur을 적용하는 이유는 책과 색의 경계선을 찾기 위해서 입니다. 정확한 원리와 사용 이유에 대해선 저도 모르겠습니다. 아마 포토샵을 사용하실 줄 아시는 분은 잘 알고 계실거라고 생각합니다.

img_gray = cv2.cvtColor(img, cv2.COLOR_BGR2GRAY) #Gray imgae img_blur = cv2.GaussianBlur(img_gray, (5, 5), 0) # GaussianBlur image plt.figure(figsize=(7,7)) plt.imshow(img_gray)

 다음은 픽셀에 대한 값을 비교하여 입력한 threshold값보다 작을 경우 색을 모두 죽여버립니다. 

# cv2.threshold(img, threshold_value, value, flag) # img: Grayscale 이미지 # threshold_value: 픽셀 문턱값 # value: 픽셀 문턱값보다 클 때 적용되는 최대값(적용되는 플래그에 따라 픽셀 문턱값보다 작을 때 적용되는 최대값) # flag: 문턱값 적용 방법 또는 스타일 ret, img_th = cv2.threshold(img_blur, 70,255, cv2.THRESH_BINARY_INV) plt.figure(figsize=(7,7)) plt.imshow(img_th);

 살아 남은 픽셀들의 집합에 사각형 틀을 입혀 줍니다... 예상으로는 6 * 4, 총 24개가 나와야 하지만 더 많이 출력이 됩니다.

image, contours, hierachy= cv2.findContours(img_th.copy(), cv2.RETR_EXTERNAL, cv2.CHAIN_APPROX_SIMPLE) rects = [cv2.boundingRect(each) for each in contours] print(rects)

 시각적으로 확인하기 위해 원본 사진에 그려봅니다. 확인 후에는 주석 처리 합니다.

for rect in rects: # Draw the rectangles cv2.rectangle(img, (rect[0], rect[1]),(rect[0] + rect[2], rect[1] + rect[3]), (0, 255, 0), 1) plt.figure(figsize=(17,12)) plt.imshow(img)

 닭에게 먼가 이상한게 있네요... 사과 역시 무언가가 잡힙니다. 저것들을 제거해야하는데 저는 사각형의 넓이를 이용하여 제거하겠습니다. sort는 데이터의 순서를 찾기위해 하였고 x좌표를 기준으로 정렬하였습니다.

rects = [(x,y,w,h) for (x,y,w,h) in rects if ((w*h>500)and(w*h<600))] rects.sort() print(rects)

이쁘게 잘됬네요. ㅎㅎ

  다음은 그림들이 나타내고 있는 배열의 크기를 구하고 각각의 그림들을 배열에 집어 넣는 코드입니다. 그림과 종류를 나타내기 node라는 클레스를 정의 하였습니다.

def Relative_error(a, b): return abs(a-b) * 100 / a start = rects[1][0] nodeRaw = 0 for rect in rects: if(Relative_error(start,rect[0]) < 3): nodeRaw = nodeRaw + 1 nodeNum = len(rects); nodeColum = int(nodeNum / nodeRaw) print("%d = %d * %d" % (nodeNum, nodeRaw,nodeColum)) class node: def __init__(self, img): self.img = img self.num =-1 img_arr = [] for rect in rects: newimg = img[rect[1]:rect[1]+rect[3],rect[0]:rect[0]+rect[2]] img_arr.append(node(img=newimg))

 마지막으로 이미지끼리 비교하여 같은 이미지에게는 같은 번호를 주고 이미지가 나타내고 있는 2차원 배열을 구하는 부분입니다.

def mse(imageA, imageB): err = np.sum((imageA.astype("float") - imageB.astype("float")) ** 2) err /= float(imageA.shape[0] * imageA.shape[1]) return err count = 0; for subimg_i in img_arr: if(subimg_i.num == -1): subimg_i.num = count count = count + 1 for subimg_j in img_arr: if(mse(subimg_i.img,subimg_j.img)<1000): subimg_j.num = subimg_i.num Matrix = [[0]*nodeColum for i in range(nodeRaw)] for j in range(nodeColum): for i in range(nodeRaw): Matrix[i][j] = img_arr[j*nodeRaw+i].num for subimg_i in Matrix: print(subimg_i)

 맨 위의 첨부 파일의 소스코드는 아래 사진과 같이 숫자가 아닌 문자, 그리고 '*'로 테투리까지 표현하도록 하였습니다.

3. 사천성 알고리즘

 빠르게 구현한다고 최적화는 되어 있지 않습니다. C++로 알고리즘 구현하다가 파이썬으로 구현하려고 하니 많이 어렵더라구요. 우선 결과를 보겠습니다. 

  

왼쪽 사진은 입력이며 오른쪽은 사진을 출력입니다. 사천성을 푸는 많은 해답 중 먼저 발견된 해답이며 (1,2), (3,4)....(79,80)이 짝입니다.

소스코드는 3개의 함수로 구현되어 있으며 설명은 아래와 같습니다.

checkContent 함수 : 컨텐츠 같은 컨텐츠를 찾는 함수입니다. 2번까지 방향을 꺽을 수 있도록 구현하였습니다.

checkLoop 함수 : 주어진 시작 좌표부터 문제를 해결해 나갑니다. 만약 성능 개선을 해야한다면 이 함수를 수정하시면 됩니다.

getSichuanOrder 함수 : 알고리즘 시작 지점을 다르게 하여 순서를 찾을 수 있도록 합니다. 중간에 해답을 찾으면 멈춥니다.

import copy def _checkContent(target_xy,next_x,next_y,direction,trun_num, matrix, order, orderNum): if (trun_num >2): return orderNum else: if((0 <= next_x and next_x < len(matrix)) and (0 <= next_y and next_y < len(matrix[0]))): if(direction == 0): # 처음 new_orderNum = self._checkContent(target_xy, next_x, next_y + 1, 1, trun_num, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum new_orderNum = self._checkContent(target_xy, next_x, next_y - 1, 2, trun_num, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum new_orderNum = self._checkContent(target_xy, next_x + 1, next_y, 3, trun_num, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum new_orderNum = self._checkContent(target_xy, next_x - 1, next_y, 4, trun_num, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum return orderNum elif(direction == 1): if(matrix[next_x][next_y] == '*'): new_orderNum = self._checkContent(target_xy, next_x, next_y + 1, 1, trun_num, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum new_orderNum = self._checkContent(target_xy, next_x + 1, next_y, 3, trun_num + 1, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum new_orderNum = self._checkContent(target_xy, next_x - 1, next_y, 4, trun_num + 1, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum return orderNum elif(matrix[target_xy[0]][target_xy[1]] == matrix[next_x][next_y]): order[target_xy[0]][target_xy[1]] = orderNum order[next_x][next_y] = orderNum + 1 matrix[target_xy[0]][target_xy[1]] = '*' matrix[next_x][next_y] = '*' return orderNum + 2 else: return orderNum elif(direction == 2): if(matrix[next_x][next_y] == '*'): new_orderNum = self._checkContent(target_xy, next_x, next_y - 1, 2, trun_num, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum new_orderNum = self._checkContent(target_xy, next_x + 1, next_y, 3, trun_num + 1, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum new_orderNum = self._checkContent(target_xy, next_x - 1, next_y, 4, trun_num + 1, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum return orderNum elif(matrix[target_xy[0]][target_xy[1]] == matrix[next_x][next_y]): order[target_xy[0]][target_xy[1]] = orderNum order[next_x][next_y] = orderNum + 1 matrix[target_xy[0]][target_xy[1]] = '*' matrix[next_x][next_y] = '*' return orderNum + 2 else: return orderNum elif(direction == 3): if(matrix[next_x][next_y] == '*'): new_orderNum = self._checkContent(target_xy, next_x, next_y + 1, 1, trun_num + 1, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum new_orderNum = self._checkContent(target_xy, next_x, next_y - 1, 2, trun_num + 1, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum new_orderNum = self._checkContent(target_xy, next_x + 1, next_y, 3, trun_num, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum return orderNum elif(matrix[target_xy[0]][target_xy[1]] == matrix[next_x][next_y]): order[target_xy[0]][target_xy[1]] = orderNum order[next_x][next_y] = orderNum + 1 matrix[target_xy[0]][target_xy[1]] = '*' matrix[next_x][next_y] = '*' return orderNum + 2 else: return orderNum elif(direction == 4): if(matrix[next_x][next_y] == '*'): new_orderNum = self._checkContent(target_xy, next_x, next_y + 1, 1, trun_num + 1, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum new_orderNum = self._checkContent(target_xy, next_x, next_y - 1, 2, trun_num + 1, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum new_orderNum = self._checkContent(target_xy, next_x - 1, next_y, 4, trun_num, matrix, order, orderNum) if(new_orderNum != orderNum): return new_orderNum return orderNum elif(matrix[target_xy[0]][target_xy[1]] == matrix[next_x][next_y]): order[target_xy[0]][target_xy[1]] = orderNum order[next_x][next_y] = orderNum + 1 matrix[target_xy[0]][target_xy[1]] = '*' matrix[next_x][next_y] = '*' return orderNum + 2 else: return orderNum else: return orderNum def _checkLoop(start_x,start_y,matrix,order,num): new_num = num target_num = (len(matrix[0])-2)*(len(matrix)-2) for i in (list(range(start_x,len(matrix))) + list(range(0,start_x))): for j in (list(range(start_y,len(matrix[0]))) + list(range(0,start_y))) : if(matrix[i][j] == '*'): continue else: new_num = self._checkContent((i,j),i,j,0,0,matrix,order,new_num) if(new_num-1 == (target_num)): break if(new_num-1 == (target_num)): break while(True): if(new_num != num): if(new_num-1 == (target_num)): return new_num else: num = new_num new_num = self._checkLoop(start_x,start_y,matrix,order,new_num) else: return new_num def getSichuanOrder(matrix): result = None targetNum = (len(matrix[0])-2)*(len(matrix)-2) for i in range(len(matrix)): for j in range(len(matrix[0])): order = [[0] * len(matrix[0]) for i in range(len(matrix))] copyMetrix = copy.deepcopy(matrix) result = self._checkLoop(i,j,copyMetrix,order,1) if( result== targetNum): break; if( result== targetNum): break; return order