[알고리즘2] Seam Carving 구현 - 실습

복습하기 위해 학부 수업 내용을 필기한 내용입니다.
이해를 제대로 하지 못하고 정리한 경우 틀린 내용이 있을 수 있습니다.
그러한 부분에 대해서는 알려주시면 정말 감사하겠습니다.

2022.12.09 - [컴퓨터공학/알고리즘2] - [알고리즘2] Shortest Paths on Weighted Digraphs

[알고리즘2] Shortest Paths on Weighted Digraphs

▶Seam Carving

이미지의 크기 조절 시 중요한 부분 자동 인식해 최대한 보존하며 조절하는 방식이다.

(web browser, 휴대폰 등에서 활용한다.)

 

양옆을 밀어 1 pixel 축소한다.

너비 1 pixel인 위아래 연결선 중 중요도 합이 가장 낮은 선(seam)을 찾아 제거한다.(carve)

 

seam(중요도 합 가장 낮은 선) 찾는 방법

1. 각 픽셀을 정점으로 본다.

2. 각 픽셀이 아래 3개 정점으로 연결되었다고 본다.

3. 위아래 연결선 중 중요도 합이 최소인 연결선(seam)을 찾는다.

 

픽셀의 중요도(energy)

픽셀 주변 색깔 변화가 클수록 중요도가 커진다.

반대로, 색깔 변화가 거의 없는 곳이 중요도가 가장 낮다.

 

▶구현 API 정리

SeamCarver class

seam carving 수행하고 결과 저장하는 클래스

# 이 클래스는 실습 과제로 구현할 findVerticalSeam() 외의 기능은 모두 구현된 클래스로
# 각 함수의 의미 이해하고 사용하기
class SeamCarver:
	# 멤버 변수, 상수
	self.image: Image class 객체로 seam carve하는 이미지 나타냄. Seam carving할 때마다 변경된 이미지 저장
	self.MAX_ENERGY: Energy(중요도)의 최대값 1000을 나타냄

	# 멤버 함수
	def __init__(self, image): # SeamCarver 생성자
		# image는 그림을 나타내는 Image class 객체로
		# 복사본을 멤버 변수 self.image에 저장 (seam carving 후에도 원본 이미지 보존하기 위함)

def width(self): # self.image의 너비(가로 픽셀 수) 반환
def height(self): # self.image의 높이(세로 픽셀 수) 반환

def energy(self,x,y): # self.image에서 픽셀 (x,y)의 energy(중요도) 반환
	# **는 거듭제곱의 의미 (예: 4**2 == 16)
	# math.sqrt(x) 함수는 x의

 

findVerticalSeam() 함수로 찾은 seam을 입력으로 받는 함수

# 이 클래스는 실습 과제로 구현할 findVerticalSeam() 외의 기능은 모두 구현된 클래스로
# 각 함수의 의미 이해하고 사용하기
class SeamCarver:
	# 멤버 함수
	def removeVerticalSeam(self, seam): 
		# seam: findVerticalSeam() 함수로 찾은 vertical seam (위아래 방향으로 energy 합 최소인 경로)
		# self.image에서 seam을 제거 (그 결과 self.image에 저장된 이미지의 너비 1 감소)

	def isValidSeam(self, seam):
		# seam의 형식이 올바른지 검증하는 함수로
		# removeVerticalSeam() 등 seam을 입력으로 받는 함수 내부에서 입력 검증에 활용함
		# seam이 길이가 self.image의 높이와 같으며, 좌우로 1 pixel씩만 이동함 등을 검증

	def energySumOverVerticalSeam(self, seam):
		# seam이 나타내는 경로의 energy 합 구해 반환

 

debugging에 활용할 수 있는 함수(Text Debugging)

# 이 클래스는 실습 과제로 구현할 findVerticalSeam() 외의 기능은 모두 구현된 클래스로
# 각 함수의 의미 이해하고 사용하기
class SeamCarver:
	# 멤버 함수
	def energyMap(self):
		# self.image 각 픽셀의 에너지를 문자열 형태로 반환

	def energyMapWithVerticalSeam(self, seam):
		# self.image 각 픽셀의 에너지를 문자열 형태로 반환하되
		# seam으로 선택된 픽셀은 에너지 값 뒤에 ‘*’를 붙여 반환

 

debugging에 활용할 수 있는 함수(Graphical Debugging)

# 아래 함수는 SeamCarver 클래스 외부에 있는 함수로, 
# SeamCarver 클래스 객체를 생성해 seam carving을 수행함
#
def showBeforeAfterSeamCarving(fileName, numCarve):
	# fileName: seam carving을 수행할 이미지 파일 이름으로 (jpg, png 등 가능)
	# SeamCarver.py와 같은 디렉토리에 있는 파일이어야 함
	# numCarve: carving을 수행할 횟수
	#
	# fileName이 지정한 그림에 대해 numCarve만큼 seam carving을 수행해 결과를 좌우로 대비해 보여줌

 

▶코드

from pathlib import Path
from PIL import Image  # PIL (Python Image Library)
import math
import random
import timeit

class SeamCarver:
    MAX_ENERGY = 1000.0 # Static constant

    def __init__(self, image):
        assert(isinstance(image, Image.Image))
        self.image = image.copy() # Create a copy to not mutate the original image

    def width(self):
        return self.image.size[0]
    
    def height(self):
        return self.image.size[1]

    def energy(self,x,y):
        assert(x>=0 and x<self.width() and y>=0 and y<self.height())
        if x==0 or x==self.width()-1 or y==0 or y==self.height()-1: return self.MAX_ENERGY
        pixels = self.image.load()
        cl, cr = pixels[x-1,y], pixels[x+1,y]
        cu, cd = pixels[x,y-1], pixels[x,y+1]
        return int(math.sqrt((cl[0]-cr[0])**2 + (cl[1]-cr[1])**2 + (cl[2]-cr[2])**2 +\
            (cu[0]-cd[0])**2 + (cu[1]-cd[1])**2 + (cu[2]-cd[2])**2))

    def energeMap(self): # return all energe in string format
        rlist = []
        for row in range(self.height()):
            clist = []
            for col in range(self.width()):
                clist.append(f"{self.energy(col,row):4.0f}")
            rlist.append(' '.join(clist))
        return '\n'.join(rlist)

    def energyMapWithVerticalSeam(self, seam):
        assert(self.isValidSeam(seam))
        rlist = []
        energySum = 0.0
        for row in range(self.height()):
            clist = []
            for col in range(self.width()):
                if col == seam[row]: 
                    clist.append(f"{self.energy(col,row):3.0f}*")
                    energySum += self.energy(col,row)
                else: clist.append(f"{self.energy(col,row):4.0f}")
            rlist.append(' '.join(clist))
        rlist.append(f"energy sum over vertical seam: {energySum:4.0f}")
        return '\n'.join(rlist)

    def energySumOverVerticalSeam(self, seam):        
        assert(self.isValidSeam(seam))
        energySum = 0.0
        for row in range(self.height()):
            energySum += self.energy(seam[row],row)
        return energySum

    @staticmethod
    def isListOfIntegers(x):
        if isinstance(x, list):
            if all(isinstance(e, int) for e in x): return True
            else: return False
        else: return False

    def isValidSeam(self, seam):        
        if not SeamCarver.isListOfIntegers(seam): return False
        if len(seam) != self.height(): return False
        for i in range(self.height()):
            if seam[i]<0 or self.width()<=seam[i]: return False
            if i>0 and (seam[i] < seam[i-1]-1 or seam[i-1]+1 < seam[i]): return False
        return True

    def removeVerticalSeam(self, seam):
        # Sanity check
        assert(self.isValidSeam(seam))        
        assert(self.width() > 1)

        # Add codes below
        carvedImage = Image.new("RGB", (self.width()-1, self.height()), "white")
        pixelsInCarvedImage = carvedImage.load()
        pixelsInOriginalImage = self.image.load()
        for row in range(self.height()):
            colInCarvedImage = 0
            for col in range(self.width()):
                if col == seam[row]: continue
                pixelsInCarvedImage[colInCarvedImage,row] = pixelsInOriginalImage[col,row]
                colInCarvedImage += 1

        self.image = carvedImage

    def findVerticalSeam(self):
        # Add codes below
        height = self.height()
        width = self.width()
        distTo = [list(self.MAX_ENERGY for _ in range(width))]
        edgeTo = [list(None for _ in range(width))]
        for y in range(1, self.height()):
            distTo.append([0 for _ in range(width)])
            edgeTo.append([0 for _ in range(width)])
            for x in range(self.width()):
                if x == self.width() - 1:
                    Min = min(distTo[y - 1][x], distTo[y - 1][x - 1])
                elif x == 0:
                    Min = min(distTo[y - 1][x], distTo[y - 1][x + 1])
                else:
                    Min = min(distTo[y - 1][x], distTo[y - 1][x - 1], distTo[y - 1][x + 1])

                if Min == distTo[y - 1][x]:
                    xx = x
                elif Min == distTo[y - 1][x - 1]:
                    xx = x - 1
                else:
                    xx = x + 1
                distTo[y][x] = Min + self.energy(x, y)
                edgeTo[y][x] = xx

        result = [0] * height
        Min = 9999999
        x_min = 0
        for i in range(width):
            if distTo[height - 1][i] < Min:
                Min = distTo[height - 1][i]
                x_min = edgeTo[height - 1][i]
        for y in range(height - 1, -1, -1):
            result[y] = x_min
            x_min = edgeTo[y][x_min]

        return result


def showBeforeAfterSeamCarving(fileName, numCarve):
    image = Image.open(Path(__file__).with_name(fileName)) # Use the location of the current .py file
    assert(numCarve <= image.size[0])
    assert(image.size[0] <= 100 and image.size[1] <= 100)
    sc = SeamCarver(image)
    for i in range(numCarve): sc.removeVerticalSeam(sc.findVerticalSeam())                                  
    
    image = image.resize((image.size[0]*10, image.size[1]*10))    
    sc.image = sc.image.resize((sc.image.size[0]*10, sc.image.size[1]*10))

    # Concatenate two images side-by-side
    concat = Image.new("RGB", (image.size[0]+sc.image.size[0]+1, image.size[1]), "black")
    concat.paste(image, (0,0))
    concat.paste(sc.image, (image.size[0]+1, 0))
    concat.show()
    

'''
    Iterate over pixels and change colors to gray scale
'''
def convertToGrayScale(image):
    assert(isinstance(image, Image.Image))
    image2 = Image.new(mode="RGB", size=(image.size[0],image.size[1]), color='white') # Create a new white image of the same size
    pixels1 = image.load() # Get pixel map
    pixels2 = image2.load()
    for col in range(image.size[0]): # width
        for row in range(image.size[1]): # height
            r,g,b = pixels1[col,row]
            y = int(0.299*r + 0.587*g + 0.144*b) # Change color to gray scale
            pixels2[col,row] = (y,y,y)
    return image2


if __name__ == "__main__":        
    '''
    # Unit test for convertToGrayScale()    
    image_color = Image.open(Path(__file__).with_name("heart.jpg")) # Use the location of the current .py file    
    image_gray = convertToGrayScale(image_color)
    image_color.show()
    image_gray.show()
    '''
    # Unit test 1 for vertical seam

    image = Image.new("RGB", (10,10), "white")
    pixels = image.load()
    for row in range(image.size[0]):         
        pixels[4,row] = (255,0,0)
        pixels[5,row] = (255,0,0)
    sc = SeamCarver(image)           
    #print(sc.energeMap(), '\n')
    #sc.image.show()
    
    vs = sc.findVerticalSeam()
    print(sc.energyMapWithVerticalSeam(vs),'\n')
    if int(sc.energySumOverVerticalSeam(vs)) == 2000: print("pass")
    else: print("fail")
    sc.removeVerticalSeam(vs)
    # sc.width() == 9    
    
    vs = sc.findVerticalSeam()
    #print(sc.energyMapWithVerticalSeam(vs),'\n')  
    if int(sc.energySumOverVerticalSeam(vs)) == 2000: print("pass")
    else: print("fail")
    sc.removeVerticalSeam(vs)
    # sc.width() == 8

    vs = sc.findVerticalSeam()
    #print(sc.energyMapWithVerticalSeam(vs),'\n')
    if int(sc.energySumOverVerticalSeam(vs)) == 2000: print("pass")
    else: print("fail")
    sc.removeVerticalSeam(vs)
    # sc.width() == 7

    vs = sc.findVerticalSeam()
    #print(sc.energyMapWithVerticalSeam(vs),'\n')
    if int(sc.energySumOverVerticalSeam(vs)) == 2000: print("pass")
    else: print("fail")
    sc.removeVerticalSeam(vs)
    # sc.width() == 6

    vs = sc.findVerticalSeam()
    #print(sc.energyMapWithVerticalSeam(vs),'\n')
    if int(sc.energySumOverVerticalSeam(vs)) == 4880: print("pass")
    else: print("fail")
    sc.removeVerticalSeam(vs)
    # sc.width() == 5


    # Unit test 2 for vertical seam

    image2 = Image.new("RGB", (3,10), "white")
    sc2 = SeamCarver(image2)
    vs2 = sc2.findVerticalSeam()
    print(sc2.energyMapWithVerticalSeam(vs2))
    if all([vs2[i]==1 for i in range(1,image2.size[0]-1)]): print("pass")
    else: print("fail")
    sc2.removeVerticalSeam(vs2)

    # sc2.width() == 2

    image3 = Image.open(Path(__file__).with_name("heart.jpg")) # Use the location of the current .py file
    sc3 = SeamCarver(image3)
    vs3 = sc3.findVerticalSeam()
    if int(sc3.energySumOverVerticalSeam(vs3)) == 2000: print("pass")
    else: print("fail")

    '''
    image3 = Image.open(Path(__file__).with_name("heartR.jpg")) # Use the location of the current .py file
    sc3 = SeamCarver(image3)
    vs3 = sc3.findVerticalSeam()
    if int(sc3.energySumOverVerticalSeam(vs3)) == 2000: print("pass")
    else: print("fail")
    '''

    image3 = Image.open(Path(__file__).with_name("stars.jpg")) # Use the location of the current .py file
    sc3 = SeamCarver(image3)        
    vs3 = sc3.findVerticalSeam()      
    if int(sc3.energySumOverVerticalSeam(vs3)) == 2000: print("pass")
    else: print("fail")        

    image3 = Image.open(Path(__file__).with_name("piplub.jpg")) # Use the location of the current .py file
    sc3 = SeamCarver(image3)
    vs3 = sc3.findVerticalSeam()
    if int(sc3.energySumOverVerticalSeam(vs3)) == 2000: print("pass")
    else: print("fail")

    '''
    # Unit test 3: visual inpsection for seam carving
    showBeforeAfterSeamCarving("heart.jpg", 30)    # carving 후에 흰 부분만 삭제되고 하트 부분은 유지되어야 함    
    showBeforeAfterSeamCarving("stars.jpg", 20)    # 별 3개 모양 carving 전후에 유지되어야 함
    showBeforeAfterSeamCarving("piplub.jpg", 30)   # carving 후에 흰 부분만 삭제되고 piplub은 유지되어야 함
    '''
    
    # Speed test (effective only when you pass the accuracy test)
    image3 = Image.open(Path(__file__).with_name("piplub.jpg")) # Use the location of the current .py file
    sc3 = SeamCarver(image3)
    n=20
    tVerticalSeam = timeit.timeit(lambda: sc3.findVerticalSeam(), number=n)/n
    tGrayScale = timeit.timeit(lambda: convertToGrayScale(image3), number=n)/n
    print(f"Finding {n} vertical seams on a 100x100 image took {tVerticalSeam:.10f} sec on average")
    print(f"Creating {n} gray scale images on a 100x100 image took {tGrayScale:.10f} sec on average")    
    if (tVerticalSeam < 12 * tGrayScale): print("pass for speed test")
    else: print("fail for speed test")