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

スポンサーサイト

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

instagram engineering challengeをやってみる

                
tags:
コード改良後の記事
instagram engineering challengeをやってみる その後

 もう終わってしまったようだけど、Instagramがエンジニア向けに面白い企画を出していた。
http://instagram-engineering.tumblr.com/post/12651721845/instagram-engineering-challenge-the-unshredder
こういうのを見ると、つい手を出したくなってしまう。

 内容を読んでみるに、掲載されてれる画像を復元できればいいようだ。どんな画像にでも適用できるようには書かなくていいらしい。そんなことをしたら立派な研究だし、そんなアルゴリズムを数時間で開発したらおそろしいが...と思ったらいろんな画像でやってる人がいるのは恐ろしいところ。僕もいくつか画像を用意して試したけど、案の定、全部成功するわけではなかった。

 僕はPythonで書いたが、ヒストグラム作成のためnumpyを使った。使わなくても書けるけど。所要時間は、共通問題とボーナス問題を合わせて日中丸々かかった。Instagramとどっこいどっこいか、ぼくのほうが数時間かかっているということだろう。

サンプルとして、bingにあった画像を一つ置いておく。


import Image, numpy
import os
import glob

def gpv(im, x, y):
width, height = im.size
pixel = im.getdata()[y * width + x]
return pixel

def list_save_as_image(li):
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):
val = []
for x in range(1, width):
diff = [(abs(gray[x - 1, y] - gray[x, y])>25) * 255 for y in range(0, height)]
val.append(diff)
list_save_as_image(val)

def split_image(image):
cropped = []
for x in range(NUMBER_OF_COLUMNS):
source_region = image.crop((x1 * x, y1, x1 + x1 * x, y2))
cropped.append(source_region)
return cropped

def choose_leftend(cropped_gray):
li_diff = []
for a, im in enumerate(cropped_gray):
diff = []
for b, im in enumerate(cropped_gray):
if not (a == b):
diff.append(sum([abs(gpv(cropped_gray[a], 0, y) - gpv(cropped_gray[b], shred_width - 1, y)) for y in range(height)]))
else:
diff.append("ignore")
li_diff.append(diff)
li_min = [min(x) for x in li_diff]
min_index = li_min.index(max(li_min))
return min_index

def first_join2(cropped):
dest = [0, 0]
cropped_gray = [x.convert("L") for x in cropped]
left_im_index = choose_leftend(cropped_gray)
unshredded_gray = Image.new("L", image.size)
unshredded_gray.paste(cropped_gray.pop(left_im_index), tuple(dest))
unshredded = Image.new("RGBA", image.size)
unshredded.paste(cropped.pop(left_im_index), tuple(dest))
while cropped_gray:
li_diff = []
dest[0] += shred_width
for a, im in enumerate(cropped_gray):
diff = sum([1 for y in range(height)
if abs(gpv(unshredded_gray, dest[0] - 1, y) - gpv(im, 0, y)) > threshold])
li_diff.append(diff)

val_min = min(li_diff)
index_min = li_diff.index(val_min)
unshredded.paste(cropped.pop(index_min), tuple(dest))
unshredded_gray.paste(cropped_gray.pop(index_min), tuple(dest))
return unshredded

def finalize(unshredded):
final = Image.new("RGBA", image.size)
li_diff = []
unshredded_gray = unshredded.convert('L')
for x in range(1, 20):
diff = sum([1 for y in range(height-1) if abs(gpv(unshredded_gray, shred_width * x - 1, y) - gpv(unshredded_gray, shred_width * x, y)) > threshold])
li_diff.append(diff)
index_max = li_diff.index(max(li_diff))
diff2 = sum([1 for y in range(height-1) if abs(gpv(unshredded_gray, 0, y) - gpv(unshredded_gray, width - 1, y)) > threshold])
if max(li_diff) > diff2:
dst_x = index_max * shred_width + shred_width
cropped1 = unshredded.crop((dst_x, 0, width + dst_x, height))
final.paste(cropped1, (0, 0))
cropped2 = unshredded.crop((0, 0, dst_x, height))
final.paste(cropped2, (width - dst_x, 0))
return final
else:
return unshredded


def calculate_width(li):
li_diff1 = []
while li:
li_diff2 = [li[p] - li[0] for p in range(len(li) - 1)]
li.pop(0)
li_diff1 += li_diff2
hist_x, hist_y = numpy.histogram(li_diff1, range(10, width/2))
hist_x = hist_x.tolist()
hist_y = hist_y.tolist()
for p in range(len(hist_x)):
num_index = hist_x.index(max(hist_x))
sh_width = hist_y[num_index]
if not (width % sh_width):
return sh_width
else:
hist_x.pop(num_index), hist_y.pop(num_index)
return "width?"

def line_up_candidates(image):
gray = image.convert("L").load()
pos = []
li_sum_diff = []
for x in range(1, width):
diff = sum([1 for y in range(0, height, 1) if (abs(gray[x - 1, y] - gray[x, y])>threshold)])
pos.append([x, diff])
li_sum_diff.append(diff)

hist_x, hist_y = numpy.histogram(li_sum_diff, range(10, width/2))
num = 0
for x in range(len(hist_x)):
num += hist_x[-x]
if num > 40: break

threshold2 = int(hist_y[-x])
li_border = [x[0] for x in pos if (x[1]>threshold2)]
return li_border

def cropped_width(image):
li_border = line_up_candidates(image)
w = calculate_width(li_border)
return w


os.chdir('sample/shredded')
files = glob.glob('*.png')
for filename in files:
print "\n", filename
image = Image.open(filename)

# Access an arbitrary pixel. Data is stored as a 2d array where rows are
# sequential. Each element in the array is a RGBA tuple (red, green, blue,
# alpha).

##x, y = 20, 90

width, height = image.size
# Create a new image of the same size as the original
# and copy a region into the new image
NUMBER_OF_COLUMNS = 20
shred_width = width / NUMBER_OF_COLUMNS
##shred_number = 1
x1, y1 = shred_width, 0
x2, y2 = x1 + shred_width, height
threshold = 25 # 10% of 255

print cropped_width(image), "\n"
cropped = split_image(image)
unshredded = first_join2(cropped)
final = finalize(unshredded)
final.save("un_" + filename, "JPEG")
            

コメントの投稿

非公開コメント

プロフィール

hMatoba

Author:hMatoba
Github

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

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