Instagram Engineering Challengeを解いてみた

何時かは解いてみようと思っていたInstagram Engineering Challenge、バラバラに切断された画像を元に戻す、と言う問題。糞コードでもいいから週末にチャレンジしてみた。

前書き：完全糞コードなのであらかじめご了承下さい

スキル

HTML苦手、SVG、Canvasなど画像処理経験皆無、見ての通り無謀なスタートですが、色々なツールに出会って楽しくやり遂げました。

ツール

全部初体験ですが大いに役に立ちました。

• D3：SVGによるデータ可視化ツール、ギャラリーがかっこいい。
• jCanvas：canvas操作が楽に出来るjQueryプラグイン。
• i-color：カラースペースの変換ツール。

アプローチ

1. 切断された画像をcanvasに読み込み、行ごとに隣同士と色の相違度を求める。切断なら画像が繋がらないので相違度が高い。
2. n行ずつ相違度を求め、nが切断幅と重なると相違度が一層高くなる。ラジオのチューニング的なイメージ？？
3. ２の結果に基づいて画像を切断。
4. 左端の断片を見つけ、切断面が近い物を隣り合わせに配列。

コード

長いのでgistでどうぞ。長文注意、糞コード注意!!

結果

アドバンテージ

• カラースペースはRGBでは無くLabを使用する事で、色違い判定が人の目から見たそれに近くなる。

L*、a*、b* の非線形な関係は人間の目の非線形な反応を擬似しようとしたものである。--ウィキペディア

• 色違い判定の結果をD3により可視化。デバッグや、データ解析の時に役立つ。

ディスアドバンテージ

• 殴り書きな糞コード。
• カラースペース変換や色違い判定が非常に重い、Chromeのプロファイリングによると半分近い処理時間を消費している。
• Chromeでは正常だが、Safariでは計算結果が微妙に違い、壊れるケースがある。
• 時間があればnode.jsでマルチスレッドに書き換えた方がいいかも。