Skip to content

Instantly share code, notes, and snippets.

Created January 27, 2013 21:12
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save anonymous/4650518 to your computer and use it in GitHub Desktop.
Save anonymous/4650518 to your computer and use it in GitHub Desktop.
Restore scrambled profile pics in OkCupid's crazy blind date.
#!/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