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에서 오류가 난 값(또는 다른 값)의 수를 의미하는 용어인 듯.

추가