Skip to content

Instantly share code, notes, and snippets.

@isagalaev
Forked from bobuk/img.py
Last active December 11, 2015 05:48
Show Gist options
  • Save isagalaev/4554182 to your computer and use it in GitHub Desktop.
Save isagalaev/4554182 to your computer and use it in GitHub Desktop.
#!/usr/bin/env python
# coding: utf-8
import os
import random
import glob
from PIL import Image
import numpy
BLOCK_SIZE = 20
THRESHOLD = 60
WIDTH = 200
MAX_DISTANCE = 220
def image_data(filename):
"""
Get data from image ready for comparison
"""
img = Image.open(filename).resize((BLOCK_SIZE, BLOCK_SIZE), Image.BILINEAR)
return numpy.array([sum(x) for x in img.getdata()])
def distance(data1, data2):
"""
Logical distance between two images on a scale 0..400
"""
return sum(1 for x in data1 - data2 if abs(x) > THRESHOLD)
def duplicates(dirname):
"""
Finds duplicate images in a directory.
All files must be *.jpg.
Returns an iterator of image groups ([], [], ... [])
"""
files = glob.glob(os.path.join(dirname, '*.jpg'))
images = [(f, image_data(f)) for f in files]
random.shuffle(images)
for filename, data in images:
distances = [(distance(data, d), f) for f, d in images]
yield sorted([(dist, f) for dist, f in distances if dist < MAX_DISTANCE])
def html_group(group):
return ''.join(
'<img src="%s" width="%s"/>%s' % (os.path.basename(f), WIDTH, dist)
for dist, f in group
)
def html(groups):
"""
Generates HTML from groups of image duplicates
"""
body = '<hr/>'.join(html_group(g) for g in groups)
return '<html><body>%s<hr/></body></html>' % body
if __name__ == '__main__':
print(html(duplicates('/home/maniac/Desktop/4554182')))
@reclosedev
Copy link

Хорошо получилось.

distance() можно и numpy доверить:

def distance(data1, data2):
     ...
     return (abs(data1 - data2) > THRESHOLD).sum()

@isagalaev
Copy link
Author

Да, так короче и лучше, спасибо. Хотя, @bobuk говорит, что он померил, и numpy там вообще выигрыша по скорости не даёт, большую часть времени съедает загрузка и уменьшение картинок.

@megabuz
Copy link

megabuz commented Jan 17, 2013

В 42 строке лучше вместо списка генерить итератор
В 43 строке в sorted тоже можно передать итератор

@refaim
Copy link

refaim commented Jan 17, 2013

Есть ещё один вариант реализации distance():

def distance(data1, data2):
    ...
    return sum(abs(x) > THRESHOLD for x in data1 - data2)

Впрочем, он аналогичен варианту @reclosedev, только без numpy.

@isagalaev
Copy link
Author

В 43 строке в sorted тоже можно передать итератор

Хм… Я всегда считал, что sorted требует объекта с длиной, а потому открытый генератор ему не подходит. Впрочем, может так и было в старых Питонах… Спасибо!

@isagalaev
Copy link
Author

В 42 строке лучше вместо списка генерить итератор

Там, в общем-то это совсем неважно, потому что список файлов вряд ли будет достаточно большим, чтобы это оправдать. Но можно, да.

@vslinko
Copy link

vslinko commented Jan 18, 2013

Первым делом я бы добавил argv

@anxieux
Copy link

anxieux commented Jan 18, 2013

В images можно избавиться от f (как вы и пытались в скринкасте), а в 42 строке вместо images итерировать по zip(files, images). Тогда переменная filename не нужна.
upd: пардон, не получится из-за random.shuffle(images)

@nnemkin
Copy link

nnemkin commented Jan 18, 2013

Как это numpy выигрыша не дает? Вот пара тестов на коленке ("загрузка" включает в себя ресайз):

      387 картинок, 272 МБ                860 картинок, 587 МБ              
numpy       |   нет    |  есть      numpy       |   нет    |  есть          
------------+----------+--------    ------------+----------+--------        
Загрузка    |  61.43 s | 60.63 s    Загрузка    | 131.14 s | 149.80 s      
Сравнение   | 121.11 s |  6.11 s    Сравнение   | 605.53 s |  38.49 s      
------------+----------+--------    ------------+----------+--------        
Итого       | 182.55 s | 66.74 s    Итого       | 736.67 s | 188.29 s   
Ускорение   |       x1 |    x2.7    Ускорение   |       x1 |     x3.9  

(Python 2.7.2 x86, Windows 7)

Оба этапа упираются в процессор, скорость диска особо не влияет.
Загрузка/ресайз идет за O(n), сравнение за O(n^2), можно легко оценить выигрыш от быстрого сравнения, подставив две константы...

@mgulyaev
Copy link

В 27й строчке наверно имеет смысл в комментарии сослаться не на число 400, а на BLOCK_SIZE^2. А то если вдруг поменяется значение BLOCK_SIZE, этот комментарий потеряет актуальность

@reclosedev
Copy link

@nnemkin
Интересные результаты. При большем BLOCK_SIZE разница была бы еще заметнее.

Можно еще загрузку немного ускорить:

def image_data(filename):
    """
    Get data from image ready for comparison
    """
    img = Image.open(filename).resize((BLOCK_SIZE, BLOCK_SIZE), Image.BILINEAR)
    return numpy.asarray(img).sum(axis=2).ravel()

@isagalaev
Copy link
Author

В 27й строчке наверно имеет смысл в комментарии сослаться не на число 400, а на BLOCK_SIZE^2.

Верно :-). Я о чём-то параллельно думал в тот момент, поэтому в итоге забыл исправить.

@nnemkin
Copy link

nnemkin commented Jan 19, 2013

@reclosedev именно так я и делаю (только c dtype=np.int16 и без ravel). Но на фоне Image.resize разница не заметна.
Кстати если еще переписать оба главных цикла с использованием parallel_map = multiprocessing.Pool().map (буквально), то на 4х ядерном процессоре ускорение на обоих этапах ~3.3.

@anton-ryzhov
Copy link

В 42 строке лучше вместо списка генерить итератор
В 43 строке в sorted тоже можно передать итератор

В 23 видимо тоже генераторное выражение к месту.

@glader
Copy link

glader commented Feb 23, 2013

Поддержу противников однобуквенных переменных :) При чтении кода строка 42

for f, d in images

совсем не понятна. Что такое f? Что такое d? ИМХО лучше было бы написать

for filename, data in images

так длиннее и многословнее, зато понятнее при просмотре.

@kataev
Copy link

kataev commented Oct 23, 2013

def html_group(group):
    return ''.join(
            '<img src="%s" width="%s"/>%s' % (os.path.basename(f), WIDTH, dist)
            for dist, f in group
        )

Я думаю можно заменить на

def html_group(group):
    tmpl = '<img src="%s" width="%s"/>%s' 
    return ''.join(tmpl % (os.path.basename(f), WIDTH, dist) for dist, f in group)

Что улучшит читаемость и сократит код на 2 строки.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment