Detecting duplicate images using Python - The Iconfinder Blog 의 내용을 정리합니다.

문제

Iconfinder는 매월 수천 개의 아이콘이 올라와 판매되는 마켓 플레이스 스타트업입니다. 문제는, 타인의 이미지를 다운받아 그대로 올리거나 약간 수정한 뒤 업로드해서 수익을 얻는 사용자가 생긴다는 점입니다. 이런 사용자를 자동으로 찾아야 했습니다. 처음에는 파일의 해시를 만들고, 그 해시를 look up 하는 방식으로 해결했습니다. 하지만 완전히 동일한 이미지는 이 알고리즘으로 찾을 수 있어도, 약간 변경해서 올린 이미지는 찾을 수 없었습니다.

대부분의 해시 알고리즘은 조금만 수정해도 해시값이 완전히 달라지는 문제가 있습니다. 아래 코드처럼 점 하나만 더해도 결과가 완전히 다릅니다.

# Original text.
>>> hashlib.md5('The quick brown fox jumps over the lazy dog').hexdigest()
'9e107d9d372bb6826bd81d3542a419d6'

# Slight modification of the text.
>>> hashlib.md5('The quick brown fox jumps over the lazy dog.').hexdigest()
'e4d909c290d0fb1ca068ffaddf22cbd0'

해결 (dHash 사용)

그래서 dHash(difference hash)를 구현했고, 아래 순서로 동작합니다.

이미지를 흑백(Grayscale)으로 만든다.

그러면 픽셀은 0~255 사이의 값을 가지게 됩니다.

이미지를 공통 크기로 줄인다.

예를 들어 9x8 로 줄이면 72개의 intensity(강도)만으로 판단할 수 있게 됩니다. 이렇게 하면 악의적인 사용자가 이미지를 확대하거나 축소해서 약간의 조작을 가했더라도 유사 이미지를 판별할 수 있습니다.

인접 픽셀 비교.

>>> from PIL import Image
>>> img = Image.open('data/cat_grumpy_orig_after_step_2.png')
>>> width, height = img.size
>>> pixels = list(img.getdata())
>>> for col in xrange(width):
... print pixels[col:col+width]
...
[254, 254, 255, 253, 248, 254, 255, 254, 255]
[254, 255, 253, 248, 254, 255, 254, 255, 255]
[253, 248, 254, 255, 254, 255, 255, 255, 222]
[248, 254, 255, 254, 255, 255, 255, 222, 184]
[254, 255, 254, 255, 255, 255, 222, 184, 177]
[255, 254, 255, 255, 255, 222, 184, 177, 184]
[254, 255, 255, 255, 222, 184, 177, 184, 225]
[255, 255, 255, 222, 184, 177, 184, 225, 255]

>>> difference = []
>>> for row in xrange(height):
... for col in xrange(width):
... if col != width:
... difference.append(pixels[col+row] > pixels[(col+row)+1])
...
>>> for col in xrange(width-1):
... print difference[col:col+(width-1)]
...
[False, False, True, True, False, False, True, False]
[False, True, True, False, False, True, False, False]
[True, True, False, False, True, False, False, False]
[True, False, False, True, False, False, False, True]
[False, False, True, False, False, False, True, True]
[False, True, False, False, False, True, True, False]
[True, False, False, False, True, True, False, False]
[False, False, False, True, True, False, False, True]

차이를 비트로 변환. Convert the difference into bits.

def dhash(image, hash_size = 8):
    # Grayscale and shrink the image in one step.
    image = image.convert('L').resize(
        (hash_size + 1, hash_size),
        Image.ANTIALIAS,
    )

    pixels = list(image.getdata())

    # Compare adjacent pixels.
    difference = []
    for row in xrange(hash_size):
        for col in xrange(hash_size):
            pixel_left = image.getpixel((col, row))
            pixel_right = image.getpixel((col + 1, row))
            difference.append(pixel_left > pixel_right)

    # Convert the binary array to a hexadecimal string.
    decimal_value = 0
    hex_string = []
    for index, value in enumerate(difference):
        if value:
            decimal_value += 2**(index % 8)
        if (index % 8) == 7:
            hex_string.append(hex(decimal_value)[2:].rjust(2, '0'))
            decimal_value = 0

    return ''.join(hex_string)
해시 비교

파이썬에서는 이렇게 비교합니다.

>>> from PIL import Image
>>> from utility import dhash, hamming_distance
>>> orig = Image.open('data/cat_grumpy_orig.png')
>>> modif = Image.open('data/cat_grumpy_modif.png')
>>> dhash(orig)
'4c8e3366c275650f'
>>> dhash(modif)
'4c8e3366c275650f'
>>> dhash(orig) == dhash(modif)
True

SQL로 비교하는 방법은 다음과 같습니다.

SELECT pk, hash, BIT_COUNT(
        CONV(hash, 16, 10) ^ CONV('4c8e3366c275650f', 16, 10)
    ) as hamming_distance
FROM image_hashes
HAVING hamming_distance < 4
ORDER BY hamming_distance ASC;

두 값의 binary XOR을 수행합니다. 즉, 두 값에서 서로 다른 비트의 개수를 세는 것입니다. BIT_COUNT 는 integer 에서만 동작하기 때문에 16진수를 10진수로 변환해서 넘깁니다. 해밍 거리를 기준으로 유사 이미지를 판별합니다. 해밍 거리 는 string 에서 오류가 난 값, 즉 서로 다른 값의 개수를 의미하는 용어인 듯합니다.

추가

Python Korea Facebook Group 댓글 에서 두 분이 다른 알고리즘을 알려 주셨습니다. 김태호님 은 pHash 도 있다고 알려 주셨습니다. 이재영님 은 x,y-axis 이동과 회전, 색깔 변경까지 감지할 수 있는 SURF 나 SIFT 도 괜찮다고 알려 주셨습니다. 결과물이 좀 커서 검색에 쓰기는 어려울 수도 있다는 단서를 달아 주셨습니다.