Instagramがエンジニアを見つけるために出題した独創的な課題をやってみた

面白そうなのでやってみた。

あなたは解ける？ Instagramがエンジニアを見つけるために出題した独創的な課題:Don't be lame
http://kenichinishimura.blogspot.com/2011/11/instagram.html

縦に分割された画像をゴチョゴチョやって元に戻す。

これを

こうする

以下、コードの中にコメントで書いた。
ぜんぜんエレガントじゃない。。

2011/11/16 追記
ぜんぜんエレガントじゃないどころか、解けていなかった。。
最後に画像のつながりを推測する段階で、いちばんつながっていない箇所が画像の端っこになるはずだけど、下のコードでは最後から2番目を端っこにしている（ズルしている）

2011/11/16 さらに追記
色をRGBからHSVに変換して、閾値をいじったら解けるようになった。
ただし、他の画像でも同じように出来るかは分からない。たぶん良い閾値を発見できればいけると思うけど。

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import time
import math
import Image


def RGBtoHSV(r, g, b):
    """RGBをHSVに変換"""
    maxValue = max(r, max(g, b))
    minValue = min(r, min(g, b))
                   
    if maxValue == minValue:
        h = 0;
    elif maxValue == r:
        h = (60 * (g - b) / (maxValue - minValue) + 360) % 360;
    elif maxValue == g:
        h = (60 * (b - r) / (maxValue - minValue)) + 120;
    elif maxValue == b:
        h = (60 * (r - g) / (maxValue - minValue)) + 240;   
        
    if maxValue == 0:
        s = 0;
    else:
        s = (255 * ((maxValue - minValue) / maxValue));
        
    v = maxValue;

    return h, s, v;
	


def calcLinesDistance(d1, d2):
    """(行単位で)色の距離を求める"""
    calcDistance = lambda c1,c2: math.sqrt((c1[0]-c2[0])**2 + (c1[1]-c2[1])**2 + (c1[2]-c2[2])**2)
    return sum(calcDistance(d1[x], d2[x]) for x in xrange(len(d1))) / len(d1)


def guessSplitHeight(im, nlist=(2,4,6), thlist=(1.5,1.7)):
    """何ピクセルで分割されているか推測する"""
    
    width, height = im.size
    
    # 画像を行ごとのHSV値に変換
    data = tuple(RGBtoHSV(*c[:3]) for c in im.getdata())
    data = tuple(data[i*width:(i+1)*width] for i in xrange(height))
    
    # 各行ごとに次の行との差(距離)を計算する
    lis = tuple(calcLinesDistance(data[y-1], data[y]) for y in xrange(1, height))

    candidates = {}
    for n in nlist: # n は移動平均の数
        for th in thlist: # th は閾値
            prev = -1
            for i in xrange(n, len(lis)-n):
                # 周りに比べて距離が大きい？？
                x = lis[i] / (sum(lis[i-n:n+i+1]) / (2 * n + 1))
                if x > th:
                    # 閾値を超えたら、前回の閾値を超えたときとの間隔をカウント
                    key = (i-prev)
                    if key not in candidates:
                        candidates[key] = 0
                    candidates[key] += 1
                    prev = i

    # いちばん良く出てくる間隔があやしい
    return sorted(candidates.items(), key=lambda a:-a[1])[0][0]



def guessConnect(im, n):
    """画像のつながりっぷりを推測する"""

    width, height = im.size
    h = height/n
    
    # 画像を分割サイズで切り抜く、
    # ついでに半分のサイズに(計算量を減らすのとある程度平均値で調査するため)
    cropper = lambda i: im.crop((0, i * h, width, (i+1)*h)).resize((width/2, h/2), Image.CUBIC)

    # 画像の端っこのデータだけ取る
    lis = []
    for i in xrange(n):
        data = tuple(RGBtoHSV(*c[:3]) for c in cropper(i).getdata())
        data = tuple(data[i*width/2:(i+1)*width/2] for i in xrange(h/2))
        lis.append(dict(L=data[0], R=data[-1]))
        
    # 分割したそれぞれの距離を求める (距離が小さい=自然にくっつきそう)
    distanceList = {}
    for i in xrange(n):
        for j in xrange(n):
            if i == j: continue
            d = calcLinesDistance(lis[i]["R"], lis[j]["L"])
            distanceList[(i, j)] = d

    # 距離が小さい順番につながりを確定させていく
    right, left = range(n), range(n)
    lis = []
    while len(left) > 0:
        mind = float("inf")
        pair = None
        for i in xrange(n):
            if i not in left: continue
            for j in xrange(n):
                if i == j: continue
                if j not in right: continue
                d = distanceList[(i, j)]
                if d < mind:
                    pair = (i, j, d)
                    mind = d
        left.remove(pair[0])
        right.remove(pair[1])
        lis.append(pair)
        
    # 順番にならべる
    map = dict(x[:2] for x in lis)
    head = key = lis[-1][1]
    result = [head]
    for i in xrange(n):
        result.append(map[key])
        key = map[key]
    return result


def main():
    begin = time.time()
    
    imgpath = "./instagram_shuttered.png"

    im1 = Image.open(imgpath)
    width, height = im1.size
    
    # 縦に捜査するの気持ち悪いので回転させる
    im2 = im1.rotate(-90)

    # 分割の間隔を推測する
    h = guessSplitHeight(im2.resize((height/4, width)))
    
    # つながりを推測する
    l = guessConnect(im2, width/h)

    # 張り合わせる
    im2 = Image.new(im1.mode, im1.size)
    for i1, i2 in enumerate(l):
        cpi = im1.crop((i2 * h, 0, (i2+1) * h, height))
        im2.paste(cpi, (i1 * h, 0, (i1+1) * h, height))
    im2.save("./result.png")
    
    print time.time() - begin, "sec"

if __name__ == "__main__":
    main()