読者です 読者をやめる 読者になる 読者になる

CodeIQ Blog

自分の実力を知りたいITエンジニア向けの、実務スキル評価サービス「CodeIQ(コードアイキュー)」の公式ブログです。

「グラフから元のデータを復元!」問題解説~画像解析をpythonでやってみる #python #R

CodeIQ中の人、millionsmileです。

「もしデータがグラフの形でしか手に入らなかったら?」

データはないけど、グラフ画像だけある・・・

ありえなくもない状況ですね。あなたならどうしますか?
ここは、グラフ画像から元データを生成してみるなんてしてみてはいかがでしょう。

今回は、そんな問題をエール大学経済学部博士課程在学中の森 浩太さんに出題いただきました。
解説記事では、Pythonを使って画像からデータを作る方法をご紹介しています。

挑戦してくださった方の中には、100点(99.99点)と完全に近い状態までデータを読み取った解答もあったようです。スゴイですね。

ではでは、解説記事をお楽しみくださいませ。

https://codeiq.jp/ace/mori_kota/q385
f:id:codeiq:20130822144818j:plain

◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

グラフからデータを復元するという問題を出題させていただきました。

問題文

問題文は以下になります。

長年探してきた貴重なデータをついに見つけました!・・・ただし、グラフの形式で。
このデータ、他にはどこにも見つけることができないため、折れ線グラフの画像から元の数値を再現することとなりました。

グラフの数は100個です。
ありがたいことに、全てのグラフは以下のような形式で描かれています。

(1) 画像サイズは全て同じ(640x480)
(2) 横軸は全ファイルで共通(1月1日〜翌年1月1日)。ただしデータは1月1日〜12月31日まで。
(3) 縦軸は全ファイルで共通(0〜10)

【課題】
graph.zip:
https://dl.dropboxusercontent.com/u/110505645/CodeIQ/2013/07/graph.zip
ZIPファイルをダウンロードして、解凍してください。
なかには100個の折れ線グラフの画像ファイルが入っています。
各グラフについて、その元データを復元してください。

解答は、タブ区切りのテキストファイルにして提出してください(拡張子は.txt)。
変数名はなしで、1行目からデータです。
各行について、
第1要素が画像ファイルの名前(拡張子なし。001, 002, 003,..., 100)、
第2要素が日付(01-01, 01-02,..., 12-31というように月と日をハイフンで区切ってください)、
第3要素がデータの値です。
365日×100ファイルで、36500行のテキストファイルとなります。

解答に対する評価は、データの精度によります。
各行について、誤差5%以内を「正解」として、36500行のなかの正解の割合で評価します(0〜100%)。

完成した解答テキストファイルはファイルアップロードにて提出してください。

解説

問題のグラフはRで乱数を発生させて作りました。
「答え」のデータはこちら(data.zip)ですので、挑戦していただいた皆さんはぜひご確認ください。
評価の方法は途中で変更して、誤差0.2ポイント以内を「正解」として、その正答率をそのまま得点にしました。
中には100点(99.99点)を取る方もいて、驚かされました。

ここではPythonのpngパッケージを使用する方法を紹介します。
この方法ですと、93点くらいになるようです。

手順としてはまず画像を読み込み、そのグラフの線のy座標を取得し、またそれを値に変換します。
最後に、日付をマッチする。
おそらく、日付とマッチングする段階でズレが出やすかったのではないかと思います。

(1) ピクセルの色を読み込む

以下がサンプルコードです。png.reader()でPNGファイルを読み込むと、その第2要素にピクセルごとの色が入ります。
各行ごとに [ R1 G1 B1 R2 G2 B2 ... ] の順になっているので、ここでは行列の形に直しています。

    import png
    x = png.Reader(path).read()
    x = list(x[2])
    
    RGB = []
    for i in range(len(x)):
        R = list(x[i][0::3])
        G = list(x[i][1::3])
        B = list(x[i][2::3])
        RGB.append([(R[j], G[j], B[j]) for j in range(len(R))])
(2) グラフの線の座標と値を取得

今回は、グラフの色が黒、背景がほぼ白なので、色を見分けるのは難しくなかったと思います。準備として、画像編集ソフトなどでグラフの色を確認します。すると、背景の色は(255,255, 255)に近く、グラフの線の色が(0, 0, 0)に近いことが分かります。そこで、ここでは色の(0,0,0)が一番小さいところ(つまり最も黒に近い)を線の座標としています。最小値が複数ある場合にはそれらの平均を取っています。

    # 範囲
    LEFT = 90  # 左のJanの位置
    RIGHT = 585  # 右のJanの位置
    TOP = 72  # グラフの上端
    BOTTOM = 390  # グラフの下端
    
    # 各列ごとに点の位置を探す
    y = []
    for j in range(LEFT, RIGHT):
        col = [ RGB[i][j] for i in range(len(RGB)) ]
        
        # 色の「黒さ」を(0,0,0)からの距離で表現
        blackness = map(lambda cell: (float(cell[0]**2 + cell[1]**2 + cell[2]**2)/3)**0.5, col)
        
        # 最も黒に近い点
        MIN = min(blackness)
        ind = filter(lambda i: blackness[i]==MIN, range(len(blackness)))
        
        # インデックスの平均値
        if MIN < 120:
            y.append(float(sum(ind)) / len(ind))
        else:
            y.append(-999)
            # 十分に黒い点が見つからなかった

次に、上で計算したのは線の座標なので、これを値に変換します。10と1のy座標を別途調べて、1ピクセルあたりの幅を求めて計算します。

    # スケールを合わせる
    i1 = 82  # 10の位置
    i0 = 380  # 0の位置
    y_scaled = map(lambda p: (i0 - p) / (i0 - i1) * 10, y)
(3) 日付をマッチする

各点の日付を計算します。グラフを調べると、X座標90〜585で1年であることがわかるので、そこから1ピクセルあたりの時間幅は(365 ÷ 495)日と求まります。式の中の0.5は、ピクセルの真ん中を取るための補正です。datetimeパッケージを利用しています。

    from datetime import datetime
    from datetime import timedelta

    dt = map(lambda j: datetime(2011, 1, 1) + timedelta(float(j + 0.5 - LEFT) / (RIGHT - LEFT) * 365), range(LEFT, RIGHT))

最後に、1月1日から12月31までの値を計算する方法ですが、ここでは最も時間差の小さい点の値を取ることにしています。
昼の12時を指定することで、一日の真ん中の値となるように補正しています。

    out = []
    for k in range(365):
        d = datetime(2011, 1, 1, 12, 0, 0)  + timedelta(k)

        dif = map(lambda z: abs(z-d), dt)
        j, v = min(enumerate(dif), key=itemgetter(1))
        val = y_scaled[j]
        
        out.append([d.strftime("%m-%d"), val])


挑戦していただいた皆さん、どうもありがとうございました。

◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇◇

CodeIQ中の人後記:

どこかでマジで使えそうです。

エンジニアのための新しい転職活動!CodeIQのウチに来ない?の特集ページを見る