主にプログラミングに関して。Python, .NET Framework(C#), JavaScript, その他いくらか。
記事にあるサンプルやコードは要検証。使用に際しては責任を負いかねます

スポンサーサイト

                
tags:
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

instagram engineering challengeをやってみる その後

                
tags:


instagram engineering challengeをやってみた

Demo

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

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

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

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

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


            

コメントの投稿

非公開コメント

プロフィール

hMatoba

Author:hMatoba
Github

最新記事
リンク
作ったものなど
月別アーカイブ
カテゴリ
タグリスト

検索フォーム
Amazon
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。