Hello Absurd World!

instagram engineering challengeをやってみた

Demo

デモに使うサンプル詰め合わせ(リンク先のsamples.zip)

　instagram engineering challengeのコードを書き終えてみて、ほかの人の書いたコードを探してみた。HTML5を使ってブラウザにドラッグ＆ドロップでできるようになってるものもあって、面白いことを考え付くもんだなと感じた。

　ぼくもオリジナル要素を追加したくなったので、ちょっと考えて書いてみた。

　シュレッダーというのは前回のゴミを処理していないこともあるもので、断片が他の画像のものと混ざってしまうことがある。そこで前回の仕様に加えて、2つの画像が混ざっていると判断された場合、画像を２つに分けて出力する（混ざっていないと判断されれば１枚で出力される）。結果は↑にあるデモムービーの2:18で見られる。

　画像が混ざっているかを判断するには、RGBを極座標変換した値を使った。初めにシュレッドされた断片ごとに、RGBそれぞれの平均値を出した。そしてR,G,Bそれぞれの平均値のヒストグラムを見た。要素がまんべんなく分散していて、ピークが２つあるヒストグラムが欲しかったがそれは望めなかった。もしかしたら極座標ならと、それぞれのシュレッドされた断片ごとに、RGBの値をそれぞれの平均値を使って極座標にしてみた。２つの偏角それぞれでヒストグラムを作ったとき、どちらのヒストグラムにも２つのピークが現れた。なので画像が混ざっているかの判定には、RGBの極座標値を使った。

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

import os
import glob
import math
from collections import defaultdict

try:
    from PIL import Image
except:
    import Image
##import numpy


#汎用関数
def gpv(im, x, y):
    u"""指定された座標の画素値を返す"""
    width, height = im.size
    pixel = sum(im.getdata()[y * width + x][0:3]) / 3
    return pixel

def split_image(image, NUMBER_OF_COLUMNS):
    u"""与えられた画像を切ってリストで返す"""
    width, height = image.size
    shred_width = width / NUMBER_OF_COLUMNS
    cropped = []
    for x in range(NUMBER_OF_COLUMNS):
        source_region = image.crop((shred_width * x, 0, shred_width + shred_width * x, height))
        cropped.append(source_region)
    return cropped

def synthesize(cropped):
    u"""リストで与えられた断片をつなぎ、一枚の画像で返す"""
    width = sum([im.size[0] for im in cropped])
    height = im.size[1]
    dst_x = 0
    unshredded = Image.new("RGBA", (width, height))
    for im in cropped:
        unshredded.paste(im, (dst_x, 0))
        dst_x += im.size[0]
    return unshredded

def std_score(a, ave, std):
    u"""偏差値を返す"""
    return int(50 + 10 * (a - ave) / std)


#デバッグ用関数（main関数では不使用）
def list_save_as_image(li):
    u"""数値からリストを作って画像として保存。デバッグに使用"""
    array = numpy.array(li, numpy.uint8)
    image = Image.fromarray(array)
    image.rotate(270).transpose(Image.FLIP_LEFT_RIGHT).save('list.jpg', 'JPEG')

def decide_threshold(gray):
    u"""画素間の差分を出す時のスレッショルド値の判断に使用。デバッグに使用"""
    val = []
    width, height = gray.size
    for x in range(1, width):
        diff = [(abs(gray[x - 1, y] - gray[x, y]) > threshold) * 255 for y in range(0, height)]
        val.append(diff)
    list_save_as_image(val)


#並び替え
def order(cropped):
    u"""リストで与えられた断片の並び替え"""
    width = cropped[0].size[0] * len(cropped)
    height = cropped[0].size[1]
##    num = 0
    unshredded = cropped.pop()
    while cropped:
        left_diff = []
        for im in cropped:
            diff = sum([1 for y in range(height)
                                if abs(gpv(unshredded, 0, y) - gpv(im, im.size[0] - 1, y)) > threshold])
            left_diff.append(diff)

        right_diff = []
        for im in cropped:
            diff = sum([1 for y in range(height)
                                if abs(gpv(unshredded, unshredded.size[0] - 1, y) - gpv(im, 0, y)) > threshold])
            right_diff.append(diff)

        left_min = min(left_diff)
        right_min = min(right_diff)
        if left_min < right_min:
            index = left_diff.index(left_min)
            danpen = cropped.pop(index)
            unshredded = synthesize((danpen, unshredded))
        else:
            index = right_diff.index(right_min)
            danpen = cropped.pop(index)
            unshredded = synthesize((unshredded, danpen))
##        unshredded.save("un" + filename.replace(".png", "") + "danpen%02d" %(num) + ".png")
##        num += 1
    return unshredded


#断片幅の推定
def cropped_width(image):
    u"""断片幅を計算し、返す"""
    width, height = image.size
    gray = image.convert("L").load()
    pos = []
    li_sum_diff = []
    for x in range(1, width):
        diff = sum([abs(gray[x - 1, y] - gray[x, y]) for y in range(0, height, 1)])
        pos.append([x, diff])
        li_sum_diff.append(diff)
    ave = sum([float(num) for num in li_sum_diff]) / len(li_sum_diff)
    std = (sum([(num - ave)**2 for num in li_sum_diff]) / (len(li_sum_diff) - 1)) ** 0.5
    max_std_score = max([std_score(diff, ave, std) for diff in li_sum_diff])
    borders = [x + 1 for x, diff in enumerate(li_sum_diff) if std_score(diff, ave, std) > 75]
    widths = [borders[a + 1] - borders[a] for a in range(len(borders) - 1)
                                          if (borders[a + 1] - borders[a] > 1)]
    d = defaultdict(int)
    for x in widths: d[x] += 1
    if d:
        cropped_by = max(d, key = d.get)
        while (width % cropped_by):
            d.pop(cropped_by)
            if not d:
                cropped_by = False
                break
            cropped_by = max(d, key = d.get)
        return cropped_by
    else:
        return False


#画像が2枚混合しているか推定する。混合していれば分割したリストで返す
##def check_mixed(cropped):
##    u"""シュレッドされた画像が1枚から作られたか、2枚から作られたか判断"""
##    means = [get_mean(im) for im in cropped]
##    polar = [get_polar_coordinates(mean) for mean in means]
##    sd_theta = numpy.std([x[1] for x in polar])
##    sd_fai = numpy.std([x[2] for x in polar])
##    if sd_theta > 0.1:
##        li_theta = [x[1] for x in polar]
##        mean_theta = numpy.average(li_theta)
##        indexes_to_split = [numpy.where(li_theta > mean_theta)[0],
##                            numpy.where(li_theta <= mean_theta)[0]
##                            ]
##    elif sd_fai > 1:
##        li_fai = [x[2] for x in polar]
##        mean_fai = numpy.average(li_fai)
##        indexes_to_split = [numpy.where(li_fai > mean_fai)[0],
##                            numpy.where(li_fai <= mean_fai)[0]
##                            ]
##    else:
##        return [cropped]
##
##    cropped_split = [[cropped[x] for x in indexes_to_split[0]]]
##    cropped_split.append([cropped[x] for x in indexes_to_split[1]])
##    return cropped_split
##
##def get_mean(image):
##    u""""画像のRGBそれぞれの平均値を返す　ex.[R_mean, G_mean, B_mean]"""
##    width, height = image.size
##    r_mean = sum([image.getdata()[x][0]
##                for x in range(width * height)]) / (width * height)
##    g_mean = sum([image.getdata()[x][1]
##                for x in range(width * height)]) / (width * height)
##    b_mean = sum([image.getdata()[x][2]
##                for x in range(width * height)]) / (width * height)
##    return [r_mean, g_mean, b_mean]
##
##def get_polar_coordinates(li):
##    u"""RGB値を極座標形式に変換する　ex.[radius, theta, fai]"""
##    red, green, blue = li
##    if red == 0 and green == 0:
##        green = 0.1
##    radius = (red ** 2 + green ** 2 + blue ** 2) ** 0.5
##    theta = math.acos(blue / radius)
##    fai = math.acos(red / ((red **2 + green ** 2)) ** 0.5)
##    return [radius, theta, fai]


#メイン関数
def main(filename):
    print "\n", filename
    image = Image.open(filename)
    SHRED = cropped_width(image)
    if SHRED < 10: return False
    width, height = image.size[0], image.size[1]
    NUMBER_OF_COLUMNS = width / SHRED

    cropped = split_image(image, NUMBER_OF_COLUMNS)
    unshredded = order(cropped)
    new_filename ="un_" + filename
    unshredded.save(new_filename, "JPEG")



threshold = 25 # 10% of 255
os.chdir('sample/shredded')
files = glob.glob('sh*.png')
for filename in files:
    main(filename)