Created
January 27, 2013 21:12
-
-
Save anonymous/4650518 to your computer and use it in GitHub Desktop.
Restore scrambled profile pics in OkCupid's crazy blind date.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env python | |
# This program trys to restore the original user photos from OkCupid's | |
# tile-shuffled pictures used in "crazy blind date". The algorithm used | |
# here is not super clever, but sufficient to restore human face in most | |
# of the cases. | |
# requires python2.5+ and PIL. | |
import Image | |
from collections import defaultdict | |
size = 60 | |
seam = 1 | |
# Four different edges for a size * size image. | |
edges = [(0, 0, seam, size), # top | |
(0, size-seam, size, size), # right | |
(0, 0, size, seam), # left | |
(size-seam, 0, size, size), #bottom | |
] | |
neighbors = [(-1, 0), (0, 1), (0, -1), (1, 0)] | |
EMPTY = -1 | |
def RGB_distance(edge1, edge2): | |
distance = 0 | |
for i in xrange(len(edge1)): | |
for j in xrange(3): # RGB | |
# I use L2 distance here, L1 is also fine. Not much differences. | |
distance += (edge1[i][j] - edge2[i][j]) * (edge1[i][j] - edge2[i][j]) | |
return distance | |
# Cut image into 16 tiles. | |
def PrepareTiles(fname): | |
img=Image.open(fname) | |
tiles = [] | |
for i in xrange(4): | |
for j in xrange(4): | |
box = (i * size, j * size, i * size + size, j * size + size) | |
newimg = img.crop(box) | |
tiles.append(newimg) | |
return tiles | |
# Determine how likely two tiles are adjancent to each other by comparing their | |
# edges. This function returns a dictionary with (i, j) pairs as keys, and a list | |
# of four numbers as values. These four numbers are the likely scores for two tiles | |
# to be adjanceny in four ways (top, right, left, and bottom). | |
def PairMatchingScores(tiles): | |
result = defaultdict(list) | |
for i in xrange(16): | |
for j in xrange(16): | |
for direction in xrange(4): # four directions. | |
l1 = list(tiles[i].crop(edges[direction]).getdata()) | |
l2 = list(tiles[j].crop(edges[(3-direction)]).getdata()) | |
result[(i, j)].append(RGB_distance(l1, l2)) | |
return result | |
# This function tries to put a tile on board that is adjencent to existing | |
# tiles on board, and calculate the score of the placement. | |
def BestPositionAndScore(board, tile, score): | |
fitness = {} | |
for row in xrange(7): | |
for col in xrange(7): | |
if board[row][col] == EMPTY: | |
# put the tile in row, col | |
direction_score = [] | |
for direction in xrange(4): | |
new_row = row + neighbors[direction][0] | |
new_col = col + neighbors[direction][1] | |
if 0 <= new_row < 7 and 0 <= new_col < 7 and board[new_row][new_col] != EMPTY: | |
direction_score.append(score[(tile, board[new_row][new_col])][direction]) | |
if len(direction_score) > 0: | |
# fitness can be defined as average, min or max of edging scores. There is no | |
# clear winner in terms of what kind of algorithm is better. | |
# fitness[(row, col)] = sum(direction_score) / float(len(direction_score)) | |
# fitness[(row, col)] = min(direction_score) | |
fitness[(row, col)] = min(direction_score) | |
# sensitive to the fitness calculation, min or average. | |
position = min(fitness, key=fitness.get) | |
return position, fitness[position] | |
def FindNextPiece(board, candidates, scores): | |
candidate_score = {} | |
for i in candidates: | |
position, score = BestPositionAndScore(board, i, scores) | |
candidate_score[(i, position)] = score | |
return min(candidate_score, key=candidate_score.get) | |
def RenderImage(tiles, board): | |
new_img = Image.new('RGBA', (420, 420)) | |
for i in xrange(7): | |
for j in xrange(7): | |
index = board[i][j] | |
if index!=-1: | |
new_img.paste(tiles[index], (i * size, j*size, i *size + size, j*size + size)) | |
return new_img | |
if __name__ == "__main__": | |
import sys | |
tiles = PrepareTiles(sys.argv[1]) | |
pairwise_scores = PairMatchingScores(tiles) | |
# 7x7 grid for tiles. | |
board = [[EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY], | |
[EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY], | |
[EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY], | |
[EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY], | |
[EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY], | |
[EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY], | |
[EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY, EMPTY]] | |
best_pair = min(pairwise_scores, key=pairwise_scores.get) | |
board[3][3] = best_pair[1] # sensative to starting point. | |
candidates = set(range(16)) | |
candidates.remove(board[3][3]) | |
while candidates: | |
candidate, position = FindNextPiece(board, candidates, pairwise_scores) | |
print "Put tile ", candidate, "into ", position | |
board[position[0]][position[1]] = candidate | |
candidates.remove(candidate) | |
result = RenderImage(tiles, board) | |
result.show() |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment