斜めに写った画像をCanvasで矩形に補正する

将棋駒画像分類の話の続きのような、あんまり関係もないような。

memo.sugyan.com

memo.sugyan.com

結局、素材を組み合わせて自動で生成しただけの駒画像ではやはりデータが足りていないようで、「やはりもっと様々な画像から人力でラベル付けしてデータセットを作っていく必要がありそう」ということになった。

とはいえ、インターネットから画像を拾ってこようと思うと、例えば以下のような感じで

f:id:sugyan:20180903172533j:plain

f:id:sugyan:20180903172543j:plain

f:id:sugyan:20180903172555j:plain

(引用元: フリー写真素材ぱくたそ)

多少ならともかく 斜めの角度から写っているものは、そのまま矩形に切り出して学習用画像データに利用するのは難しそう。 これらはうまいこと変形して使いたい。 いわゆるperspective projectionの逆変換のような操作が必要になる。

JavaScriptを使ったCanvas APIでの変換では簡単な拡大・縮小などの変換は可能だけど こういったperspectiveなtransformationは無理っぽい。OpenCVなどの画像処理ライブラリを使えば可能そうだけど、できればやっぱりJSでグリグリ動かしながら出来ると嬉しいな、と思って探してみた。

OpenCVEmscriptenを使ってビルドすればJSで利用できるのだけど、

今回みたいなちょっとした変換だけのためにわざわざこれをやるのも過剰だよね…

ということで探し当てたのが、glfx.js

WebGLなどを上手いこと使って様々な画像変換処理をしてくれるライブラリ、のようだ。 perspective というAPIが含まれていて、デモもある。

よーし これを使うぞ!と思ったものの 最終更新が5年前とかで TypeScriptで利用するためのdefinitionsも無い。 仕方ないので見様見真似で自分が使いたいAPIの部分だけ書いてみた。

declare module 'glfx' {
    function canvas(): Canvas;

    export class Canvas extends HTMLCanvasElement {
        draw: (texture: Texture, width?: number, height?: number) => Canvas;
        perspective: (before: number[], after: number[]) => Canvas;
        update: () => Canvas;
        getPixelArray: () => Uint8Array;
        texture: (image: HTMLImageElement) => Texture;
    }
    export class Texture {
    }
}

これで、TypeScriptからでも

import * as fx from "glfx";

...

const canvas: fx.Canvas = fx.canvas();
const texture: fx.Texture = canvas.texture(img);
canvas
    .draw(texture)
    .perspective(src, dst)
    .update()

のような形で Image elementからtextureを読み込み、変形させた結果を描画できる。 getPixelArray()Uint8Array を取り出し new ImageData(new Uint8ClampedArray(data), size, size)ImageData オブジェクトを作ってやれば その内容を別のcanvas内にコピーするようなこともできる。

こうして最初の例の画像は以下のように矩形に補正された盤面画像を得ることが出来るし、

f:id:sugyan:20180903205513p:plain

マウス操作でグリグリ動かしながら変形パラメータを調整することが出来る。 パフォーマンス的にも不満は無い。

f:id:sugyan:20180903210714g:plain

あとは指定した数で分割すればマスごとの画像を取得できるので、

f:id:sugyan:20180903211908p:plain

(↑の右下部分が分割結果)

こうして得た一つ一つのマスの画像にラベルを付けていけばデータセットが作りやすいんじゃないだろうか(まだそこまでは出来ていない)。

実際に動かして試せるデモはこちら

TOKYO IDOL FESTIVAL のタイムテーブル画像化ツール 2018

2年前に作り始めたのがきっかけで、今年もTIFのタイムテーブルが公開されたので作ってみた。

memo.sugyan.com

2016年は画像を生成するだけであとはそれを自分で保存して勝手に使ってくれ、くらいの感じだったけど、

2017年では生成した画像と生成後のURLをTwitterでシェアできる機能を追加し、わりと多くの方々に使っていただけた。 出演者さんがブログで紹介してくれたりしたのも良い思い出。

今年も自分はTIF行かないし 作るモチベーションもあまり無かったけど、多少は需要ありそうだし一応作るか… と

データの取得とUIの細かい部分だけ変更すれば昨年の使い回しでも良かったのだけど、折角だから色々アップデートしておくか、とほぼイチから作り直してみた。

  • Rails 5.1 → 5.2
  • Webpack 3.2 → 4.16
  • Bootstrap 3.3 → 4.1
  • JS → TypeScript化

バックエンドはほぼ変更なしで問題なかったけど、フロントエンドをTS化するのは思った以上に大変だった。 元々の.jsx.tsxにリネームして : any とかつけていけば何とかなるやろ〜 と気軽に始めてみたら全然うまく動かなかったり やっぱりちゃんと型を書かないと気が済まなくなったりして、 結局8割くらい書き直した感じになった気がする。3日ほどかかってしまった。 でもおかげで幾らか?見通しも良くなったし、スッキリした、と思う。

フロントエンドは相変わらず色々と変化はあるけど以前より使いやすくなって整理されてきているとは思うし TypeScriptも大変だけど「ちゃんとcompile通るように書けばちゃんと動く」という感覚はあって嫌いじゃない。 Bootstarp 4もほぼ始めて触ったけど割と融通ききやすくなっていて悪くない印象だった。

将棋駒画像分類をMobileNetV2で最初から学習させる

前回の将棋駒画像分類の話の続き。

memo.sugyan.com

TensorFlow Hubの学習済みモデルを利用して 最終層にあたる部分だけ(?)を再学習させることで簡単に特定ドメインの画像分類のモデルを作成した。 …が、結果としてあまり精度が良くなくて、特に未学習の画像に対してかなりの高確率で誤分類してまっていた。

やはりもっと色々なバリエーションの駒画像を用意して学習させる必要があるか… と思ったが、その前にもう一つ試しておきたかったのでやってみた。

「学習済みモデルは本当にこのドメインの分類に適した特徴を学習できているのか?」

TensorFlow Hub で公開されている学習済みモデルは ILSVRC-2012-CLS 用のデータセットを用いて1000クラス分類のために学習してある。 けど、これが必ずしも自分がやろうとしている将棋駒画像の分類に適した特徴を抽出できるようになっているとは限らない。 もしかしたら、自分の用意したデータに適するよう全層を最初から学習させたら 学習済みモデルをretrainしたものより良くなることもあるのでは…?

というもの。

MobileNet V2

TensorFlow Models のrepositoryを見てみると、MobileNetV2モデルについてのコードや説明が載っている。

V1やV2の違いはよく分かっていないけど、とりあえず読んでみると tensorflow.contrib.slim を使ってモデルの構造が記述されていて、簡単に利用できるようになっているようだ。

from nets.mobilenet import mobilenet_v2

with tf.contrib.slim.arg_scope(mobilenet_v2.training_scope()):
    logits, endpoints = mobilenet_v2.mobilenet(input_tensor)

という形で training_scope() の中で呼ぶことで学習モードとしてモデルを定義できるらしい。 なのでこれに合わせて入力と学習手続きを定義していけば良さそう。

Inputs

とりあえず前回の記事で使った retrain.py に倣って学習用画像データを保存したディレクトリから 一定の割合で "training" と "validation" で別々のデータに分かれるようにしてリストを取得。

def create_image_lists(image_dir, validation_percentage):
    result = collections.OrderedDict()
    sub_dirs = [d for d in tf.gfile.ListDirectory(image_dir) if tf.gfile.IsDirectory(os.path.join(image_dir, d))]
    for sub_dir in sub_dirs:
        file_list = []
        dir_name = os.path.basename(sub_dir)
        file_glob = os.path.join(image_dir, dir_name, '*.jpg')
        file_list.extend(tf.gfile.Glob(file_glob))
        training_images = []
        validation_images = []
        for file_name in file_list:
            base_name = os.path.basename(file_name)
            # https://github.com/tensorflow/hub/blob/master/examples/image_retraining/retrain.py
            hashed = hashlib.sha1(tf.compat.as_bytes(file_name)).hexdigest()
            percentage_hash = int(hashed, 16) % 100
            if percentage_hash < validation_percentage:
                validation_images.append(base_name)
            else:
                training_images.append(base_name)
        result[dir_name] = {
            'training': training_images,
            'validation': validation_images,
        }
    return result

Datasets

取得した画像のリストを使って、入力データを作成する。 今回はせっかくなので tf.data APIを利用してみることにした。

基本的には、 tf.data.Datasetfrom_...Dataset instanceを作り、そこからiteratorを取得、その tf.data.Iterator instanceから get_next() を呼ぶことで入力Tensorを作ることができる、というものらしい。 画像分類のためのデータセットを作る場合は、対応するimages, labelsのセットを用意して使えば良い。 画像のファイルパスから内容を展開するなどの中間処理をする必要がある場合は Dataset.map で処理を書く。

def parser(file_path, label_index):
    image = tf.image.decode_jpeg(tf.read_file(file_path), channels=3)
    image = tf.image.convert_image_dtype(image, tf.float32)
    image = tf.image.resize_images(image, [96, 96])
    return image, tf.to_int64(label_index)

image_files, labels = [...], [...]
dataset = tf.data.Dataset.from_tensor_slices((image_files, labels))
dataset = dataset.map(parser)
dataset = dataset.repeat()
dataset = dataset.batch(FLAGS.batch_size)

iterator = dataset.make_initializable_iterator()
inputs, labels = iterator.get_next()

このようにして入力のbatchを作成できる。

今回は traing用のデータセットと validation用のデータセットを明示的に分けようと思って、 retrain.py と同様に一定の割合で振り分け、それぞれのデータを元に別々の Dataset, Iterator を返すようにした。

中身が違うだけで同shapeの入力を扱う場合には "reinitializable iterator" というのがあって、単一のiteratorから各Dataset用にinitializerを作ってそれを実行することで get_next() で得られる値を切り換える、という仕組みもあるようなのだけど、trainingとvalidationの切り替えを頻繁に行う場合はそのたびにinitializeすることになり、そうなるとshuffleする際に大きめの buffer_size を確保する必要がありそうで、そうすると学習開始時にかなり大きくメモリ確保してバッファリング処理をするようになって ちょっと微妙だなーと思って 結局ここでは "reinitializable iterator" は使わず 別々の Dataset として処理するようにした。 shuffleの重要度、validationの頻度などによっては普通に便利に使用できるのかもしれない。ちょっとよく分からない。

def shogi_inputs(image_lists):
    class_count = len(image_lists.keys())
    t_count, v_count = 0, 0
    for l in image_lists.values():
        t_count += len(l['training'])
        v_count += len(l['validation'])

    def generate_dataset(category):
        images = []
        labels = []
        label_names = []
        for label_index in range(class_count):
            label_name = list(image_lists.keys())[label_index]
            label_names.append(label_name)
            category_list = image_lists[label_name][category]
            for basename in category_list:
                images.append(os.path.join(FLAGS.image_dir, label_name, basename))
                labels.append(label_index)
        zipped = list(zip(images, labels))
        random.shuffle(zipped)
        return tf.data.Dataset.from_tensor_slices((
            [e[0] for e in zipped],
            [e[1] for e in zipped]))

    def parser(file_path, label_index):
        image = tf.image.decode_jpeg(tf.read_file(file_path), channels=3)
        image = tf.image.convert_image_dtype(image, tf.float32)
        image = tf.image.resize_images(image, [96, 96])
        return image, tf.to_int64(label_index)

    t_dataset = generate_dataset('training')
    t_dataset = t_dataset.map(parser)
    t_dataset = t_dataset.repeat()
    t_dataset = t_dataset.shuffle(FLAGS.batch_size * 10)
    t_dataset = t_dataset.batch(FLAGS.batch_size)

    v_dataset = generate_dataset('validation')
    v_dataset = v_dataset.map(parser)
    v_dataset = v_dataset.repeat()
    v_dataset = v_dataset.batch(FLAGS.batch_size * 5)

    return [
        t_dataset.make_initializable_iterator(),
        v_dataset.make_initializable_iterator(),
        t_count,
    ]

Training and Validation

それぞれの Dataset を使って入力画像とラベルのTensorを得られるので、実際にモデルに入力して得た結果を使って training operation と validation accuracy を作る。 trainingのあたりは models/research/slim/nets/mobilenet_v1_train.py という MobileNetV1用のスクリプトがあったのでそれを真似している。

t_iter, v_iter, training_count = shogi_inputs(image_lists)
t_inputs, t_labels = t_iter.get_next()
v_inputs, v_labels = v_iter.get_next()
with slim.arg_scope(mobilenet_v2.training_scope()):
    t_logits, _ = mobilenet_v2.mobilenet(t_inputs, num_classes=class_count)
    v_logits, _ = mobilenet_v2.mobilenet(v_inputs, num_classes=class_count, reuse=True)

# training
tf.losses.sparse_softmax_cross_entropy(t_labels, t_logits)
total_loss = tf.losses.get_total_loss(name='total_loss')
num_epochs_per_decay = 2.5
decay_steps = int(training_count / FLAGS.batch_size * um_epochs_per_decay)
learning_rate = tf.train.exponential_decay(
    0.045,
    tf.train.get_or_create_global_step(),
    decay_steps,
    _LEARNING_RATE_DECAY_FACTOR,
    staircase=True)
update_ops = tf.get_collection(tf.GraphKeys.UPDATE_OPS)
with tf.control_dependencies(update_ops):
    train_tensor = slim.learning.create_train_op(
        total_loss,
        optimizer=tf.train.GradientDescentOptimizer(learning_rate))

# validation accuracy
indices = tf.argmax(v_logits, axis=1)
correct = tf.equal(indices, v_labels)
accuracy = tf.reduce_mean(tf.to_float(correct))

これが出来たら、あとは学習を回すだけ。 ここも mobilenet_v1_train.py では slim.learning.train というのを使っていたので、それを真似してみた。

slim.learning.train はどうやらtrain tensorを渡すと定期的に記録しながら指定したstep数の学習を回してくれるようなのだけど、例えば50 stepごとにvalidationを回して記録したい、とか思うと train_step_fn で各stepで何をするかを定義してやる必要があるようだ。 正直ここまでやるんだったら slim.learning.train は使わずに普通にfor loop回すだけでも良いような気もする…。

# train step function
def train_step(sess, train_op, global_step, train_step_kwargs):
    start_time = time.time()
    total_loss, np_global_step = sess.run([train_op, global_step])
    time_elapsed = time.time() - start_time
    # validation
    if np_global_step % 50 == 0:
        logging.info('validation accuracy: %.4f', sess.run(accuracy))

    if 'should_log' in train_step_kwargs:
        if sess.run(train_step_kwargs['should_log']):
            logging.info('global step %d: loss = %.4f (%.3f sec/step)',
                         np_global_step, total_loss, time_elapsed)
    if 'should_stop' in train_step_kwargs:
        should_stop = sess.run(train_step_kwargs['should_stop'])
    else:
        should_stop = False
    return total_loss, should_stop

# start training
g = tf.Graph()
with g.as_default():
    init_op = tf.group(t_init, v_init, tf.global_variables_initializer())
    slim.learning.train(
        train_tensor,
        FLAGS.checkpoint_dir,
        graph=g,
        number_of_steps=FLAGS.number_of_steps,
        save_summaries_secs=FLAGS.save_summaries_secs,
        save_interval_secs=FLAGS.save_interval_secs,
        local_init_op=init_op,
        train_step_fn=train_step,
        global_step=tf.train.get_global_step())

Results

実際このスクリプトを回して学習開始してみると、最初は当然3%くらいの正答率で そこから徐々にlossが減少し正答率が上昇していくのが観測できる。 1,000 step前後で正答率98%〜 と、十分に高い精度まで上がるようだった。

f:id:sugyan:20180707000650p:plain

f:id:sugyan:20180707000700p:plain

さすがにCPUだと1 stepにも数秒かかるくらいのスピードでそれなりに時間がかかる。 EC2 P3 instanceを使って回してみたところ、1,000 step程度ならものの数分で終了するようだった。

Evaluation

この学習済みモデルを使って、実際に前回記事と同じ画像を与えてどう識別されるかを確認してみる。

1200 stepほど学習した後のcheckpointファイルからモデルを復元し、局面図の画像を分割してそれぞれ識別してみる。

1. 学習データに使った素材で作ったもの

f:id:sugyan:20180501012958p:plain

前回の結果:

-KI * +TO * -OU * +TO+TO+NY
 * -FU *  *  * +FU *  *  * 
+RY-TO *  * -FU-FU * -FU-KY
 * +KE+KE-GI-KI-TO *  * +RY
-UM-NK+KY+TO * -TO *  *  * 
 * +FU *  *  * -GI-GI+FU * 
 *  * +FU * +TO-GI *  * +KE
 *  *  *  * +TO * +FU * +KY
+UM *  *  *  *  * +KI * -KI

今回の結果:

-KI * +TO * -OU * +TO+TO+NY
 * -FU *  *  * +FU *  *  * 
+RY-TO *  * -FU-FU * -FU-KY
 * +KE+KE-GI-KI-TO *  * +RY
-UM-NK+KY+TO * -TO *  *  * 
 * +FU *  *  * -GI-GI+FU * 
 *  * +FU * +TO-GI *  * +KE
 *  *  *  * +TO * +FU * +KY
+UM *  *  *  *  * +KI * -KI

さすがにこれは全部正解するようだ。

2. Shogipicで生成された局面図

f:id:sugyan:20180501013010p:plain

前回の結果:

-KI * +TO * -OU * +TO+TO+NY
 * -UM *  *  * +FU *  *  * 
+RY-TO+UM+UM-UM-FU ? -UM-KY
 * +KE+KE-KA-KI-TO ?  * +RY
-UM-KA+KY+TO * -TO *  *  * 
 * +FU ?  ?  * -KE-KE+FU * 
 *  * +FU ? +TO-KE ?  * +KE
 *  *  *  * +TO * +FU * +KY
+UM *  *  *  *  * +KI * -KI

今回の結果:

-KI * +TO * -OU * +NK+NK-NG
 * -FU *  *  * +FU *  *  * 
+RY-TO *  * -FU-FU * -FU-KY
 * +KE+KE-GI-KI-TO *  * +RY
-UM-NK+KY+TO * -TO *  *  * 
 * +FU *  *  * -GI-GI+FU * 
 *  * +FU * +TO-GI *  * +KE
 *  *  *  * +TO * +FU * +KY
+UM *  *  *  *  * +KI * -KI

何故か1段目の「と金」が「成桂」になっていたりといった誤答はあるが、前回のように駒の無いはずのところで駒があると判別してしまうような間違いは無くなっているようだ。

3. 激指 14の局面スクリーンショット

f:id:sugyan:20180501013026p:plain

前回の結果:

-KI * +TO * -OU * +TO+TO+NY
 * -FU *  *  * +FU *  *  * 
+RY-TO *  * -FU-FU * -FU-KY
 * +HI+HI-GI-KI-TO *  * +RY
-UM-NG+KY+TO * -TO *  *  * 
 * +FU *  *  * -GI-GI+FU * 
 *  * +OU * +TO-GI *  * +HI
 *  *  *  * +TO * +FU * +KY
+RY *  *  *  *  * +KI * -KI

今回の結果:

-KI *  *  * -OU *  *  * +NK
 * -FU *  *  * +FU *  *  * 
+RY-TO *  * -FU-FU * -FU-KY
 * +KE+KE-GI-KI-TO *  * +RY
-UM-NK+KY *  * -TO *  *  * 
 * +FU *  *  * -GI-GI+KY * 
 *  * +FU * +TO-GI *  * +KE
 *  *  *  *  *  * +KY * +KY
+RY *  *  *  *  * +KI * -KI

攻方の「と金」が空白として識別されて消えてしまっていたり、「歩兵」が「香車」と認識されていたり、間違いが多い…

4. Shogi.ioの局面スクリーンショット

f:id:sugyan:20180501013041p:plain

前回の結果:

-NG * +TO * -FU * +TO+TO+UM
 * -FU *  *  * +NK *  *  * 
-UM-TO ?  * -FU-FU * -FU-NG
 * +KE+OU-GI-NG-TO *  * +KE
-NG-UM+NG+TO * -TO *  *  * 
 * +NK ?  *  * -GI-GI-UM * 
 *  * +NK * +TO-GI *  * +KE
 *  *  *  * +TO * -UM * +NG
-UM *  *  *  *  * +NG * -NG

今回の結果:

-NG *  *  * +OU *  *  * -TO
 * -NK *  *  * +NY *  *  * 
-UM-TO *  * -NK-NK * -NK-NG
 * +KE+KE-NG-NG-TO *  * +GI
-UM-NG-UM *  * -TO *  *  * 
 * +NY *  *  * +RY-HI+NY * 
 *  * +NG *  * +RY *  * +KE
 *  *  *  *  *  * +NY * +FU
-KE *  *  *  *  * +FU * -NG

前回のも全然合ってなくてひどかったが、今回のはもっとひどい…

まとめ

TensorFlowでMobileNetV2を最初から学習させることができた、けど別にそれが出来たからといって性能が改善するわけでもない。

ラクして生成したものだけを使って…ではなく、ちゃんと様々な学習用データセットを用意して 学習させていくしかなさそう。

Repository

interface要素を持つstructへのJSON Unmarshal

ちょっとやり方が分からなくて調べたのでメモ。

例題

type hoge struct {
    Foo int `json:"foo"`
    Bar baz `json:"bar"`
}

type baz interface {
    hoge()
}

type fuga struct {
    Fuga string `json:"fuga"`
}

func (*fuga) hoge() {}

という感じで "foo"int に固定されているけど "bar"baz interface というのだけ定義されている hoge struct がある。

baz interface を正しく実装している fuga structを使ってその要素を持つJSONhoge structにunmarshalしたい。とする。

func main() {
    str := `{"foo":3,"bar":{"fuga":"fuga"}}`

    var h hoge
    if err := json.Unmarshal([]byte(str), &h); err != nil {
        log.Fatal(err)
    }
}

これは失敗する。

2018/06/23 22:42:58 json: cannot unmarshal object into Go struct field hoge.bar of type main.baz
exit status 1

"bar" 要素のunmarshalの方法が分からん。ということなので明示的に教えてやる必要がある。

hoge struct に UnmarshalJSON([]byte) error 関数を実装してやる。

mapを使う方法

直感的に分かりやすい? かも知れない方法

func (h *hoge) UnmarshalJSON(b []byte) error {
    m := map[string]json.RawMessage{}
    if err := json.Unmarshal(b, &m); err != nil {
        return err
    }
    for k, v := range m {
        switch k {
        case "foo":
            var i int
            if err := json.Unmarshal(v, &i); err != nil {
                return err
            }
            h.Foo = i
        case "bar":
            var f fuga
            if err := json.Unmarshal(v, &f); err != nil {
                return err
            }
            h.Bar = &f
        }
    }
    return nil
}

一旦 map[string]json.RawMessage{}マッピングしてunmarshalしてから、各要素をfor loopで回して それぞれの値を改めてunmarshalする。 他のfieldにunmarshalすべきtypeの情報が入っていればここで取り出してから分岐させたりして処理すれば良い。

func main() {
    str := `{"foo":3,"bar":{"fuga":"fuga"}}`

    var h hoge
    if err := json.Unmarshal([]byte(str), &h); err != nil {
        log.Fatal(err)
    }
    log.Printf("%#v, (bar: %+v)", h, h.Bar)
}
$ go run main.go
2018/06/23 22:52:12 main.hoge{Foo:3, Bar:(*main.fuga)(0xc42000e2c0)}, (bar: &{Fuga:fuga})

alias typeを使う

上記の方法だと Foo 要素とか interface 以外のものもいちいち分岐の中でunmarshal処理を書かなければならず、めんどい。

そこで、aliasなtypeを使って処理する方法があるようだ。

func (h *hoge) UnmarshalJSON(b []byte) error {
    type alias hoge
    a := struct {
        Bar json.RawMessage `json:"bar"`
        *alias
    }{
        alias: (*alias)(h),
    }
    if err := json.Unmarshal(b, &a); err != nil {
        return err
    }

    var f fuga
    if err := json.Unmarshal(a.Bar, &f); err != nil {
        return err
    }
    h.Bar = &f

    return nil
}

このようにalias typeを使って そこに突っ込むようにunmarshalすると、Bar だけ json.RawMessageで受け取り それ以外はそのままunmarshalしてくれる、ようだ。 なので Bar要素の部分だけ明示的に処理を書けば良いらしい。

スッキリ書けて良さそう。

複数のtype候補がある場合

例えば上記の fuga struct 以外にも 似たような piyo struct が同様に baz interface を実装していたとする。

type hoge struct {
    Foo int `json:"foo"`
    Bar baz `json:"bar"`
}

type baz interface {
    hoge()
}

// こっちのFugaはstring
type fuga struct {
    Fuga string `json:"fuga"`
}

func (*fuga) hoge() {}

// こっちのFugaはbool
type piyo struct {
    Fuga bool `json:"fuga"`
}

func (*piyo) hoge() {}

同名のフィールドを持っているが型が違うので、

{"foo":3,"bar":{"fuga":"true"}}

というJSON"fuga" は文字列なので fuga structで、

{"foo":3,"bar":{"fuga":true}}

というJSONの場合は "fuga" がbooleanを受け取るので piyo struct にしたい。

どっちか分からない、という場合は 「上手くunmarshalできるかどうかとにかく試してみる」という感じになりそう

func (h *hoge) UnmarshalJSON(b []byte) error {
    type alias hoge
    a := struct {
        Bar json.RawMessage `json:"bar"`
        *alias
    }{
        alias: (*alias)(h),
    }
    if err := json.Unmarshal(b, &a); err != nil {
        return err
    }

    var (
        f fuga
        p piyo
    )
    for _, c := range []baz{&f, &p} {
        err := json.Unmarshal(a.Bar, c)
        if err != nil {
            if _, ok := err.(*json.UnmarshalTypeError); ok {
                continue
            }
            return err
        }
        h.Bar = c
        break
    }
    return nil
}

とにかくfugapiyoもどっちも使ってjson.Unmarshalを試みる。文字列なのにboolとしてunmarshalしようとしたりその逆だったりした場合 json.UnmarshalTypeError が返ってくるので、その場合は別のtypeで再挑戦、みたいな感じ。

func main() {
    str1 := `{"foo":3,"bar":{"fuga":"true"}}`
    str2 := `{"foo":3,"bar":{"fuga":true}}`

    var h hoge
    if err := json.Unmarshal([]byte(str1), &h); err != nil {
        log.Fatal(err)
    }
    log.Printf("%#v, (bar: %+v)", h, h.Bar)

    if err := json.Unmarshal([]byte(str2), &h); err != nil {
        log.Fatal(err)
    }
    log.Printf("%#v, (bar: %+v)", h, h.Bar)
}
$ go run main.go
2018/06/23 23:16:47 main.hoge{Foo:3, Bar:(*main.fuga)(0xc42000e2a0)}, (bar: &{Fuga:true})
2018/06/23 23:16:47 main.hoge{Foo:3, Bar:(*main.piyo)(0xc420014288)}, (bar: &{Fuga:true})

ちゃんと1つ目はfugaとしてunmarshalされ 2つ目はpiyoとしてunmarshalされた。

まぁこんなのが必要になる場合はそもそものデータ設計が間違ってると思うけど。

参照

Google Code Jam 2018: Round 1C

Google Code Jam の第1ラウンド。

・予選のときの記事はこちら memo.sugyan.com

Round 1は時間制限が2時間半、3回行われてどこか1つで上位1,500人に入れば次に進める、というもの。 多分毎回ここで脱落していた

1Aは土曜日の早朝で起きられなくて断念、1Bは挑戦してみたものの全然正解できずに撃沈、最後の望みをかけて1Cに挑戦。

A Whole New Word

文字の並び換えで新しい単語を作る、もしくはもうすべて網羅されているか、を出力する。

どうやって解けばいいんだろう…とすごく悩んでしまった。 例えば最後の文字が3種類あったら 最後から2番目の文字は各種類 × 3回あらわれるはずで、それが2種類×3あったらさらに前の文字は各種類6回… となるはず、それより少なければそれは入力に含まれていない語がある、ということでそれを出力すればいい! という感じで、それを愚直に書いた。

def solve(w, l):
    n = 1
    p = []
    for i in range(l):
        d = {}
        for c in [s[l - i - 1] for s in w]:
            d[c] = d.get(c, 0) + 1
        if i > 0:
            for k in d.keys():
                if d[k] < n:
                    for e in p:
                        a = set(p) - set([s[l - i:] for s in w if s[l - i - 1] == k])
                        a = k + list(a)[0]
                        if len(a) < l:
                            a = w[0][0:l - len(a)] + a
                        return a
        if i == 0:
            p = [x for x in d.keys()]
        else:
            p = [x + e for x in d.keys() for e in p]
        n *= len(set(d.keys()))
    if len(w) == n:
        return '-'


t = int(input())
for i in range(1, t + 1):
    n, l = [int(e) for e in input().split(' ')]
    words = []
    for _ in range(n):
        words.append(input().strip())
    ans = solve(words, l)
    print('Case #{:d}: {}'.format(i, ans))

これで1時間くらい使ってしまった…。でも一応これで両方とも通っていたようだ

Lollipop Shop

飴を買いに来る人に最適なものをオススメしてたくさん販売できるようインタラクティブに。

この種のものにまず挑戦したことがなかったので とりあえずtesting_tool.py を使って動かしてみて、適当に出力を返すようにして通るのを確認、提出してみるとWrong answerに。 適当に販売してたらダメかそりゃそうか、で改めて問題を読み直して 買われる傾向が決まっているっぽい、ということが分かる。 じゃあ売れやすいものはまた注文が来るかもしれないし、売れにくいものを優先で売るようにすればいいのか? 候補を全部記録して、出現回数が少ないものを優先的に返すように変更。

終了2分前にギリギリで通った。

t = int(input())
for i in range(1, t + 1):
    n = int(input())
    f = set(range(n))
    s = {}
    for _ in range(n):
        c = []
        d = [int(x) for x in input().strip().split(' ')]
        for j in d[1:]:
            s[j] = s.get(j, 0) + 1
            if j in f:
                c.append(j)
        if len(c) > 0:
            m = min([s[j] for j in c])
            j = 0
            for k, v in s.items():
                if v == m and k in c:
                    j = k
                    break
            print(j)
            f.remove(j)
        else:
            print('-1')

Ant Stack

耐久重量が決まっている各蟻が前の蟻を乗せていって、最大幾つ積めるかを求める。

どういう形で積むのが最大になるかがなかなかイメージできなくて 幾つかテストケースを追加して考えてみる。 結局 途中n匹目までのところで「m段詰むと最軽量のものはw_mになる」というのを順番に計算していって 求められるかな…?と思って書いてみた。

def solve(w):
    d = {1: w[0]}
    for i in range(1, len(w)):
        dd = {1: set([w[i]])}
        for k, v in d.items():
            dd[k] = dd.get(k, set())
            dd[k].add(v)
            if v <= w[i] * 6:
                dd[k + 1] = dd.get(k + 1, set())
                dd[k + 1].add(v + w[i])
        d = {}
        for k, v in dd.items():
            d[k] = min(v)
    return max(d.keys())


t = int(input())
for i in range(1, t + 1):
    n = int(input())
    w = [int(x) for x in input().strip().split(' ', n)]
    ans = solve(w)
    print('Case #{}: {}'.format(i, ans))

Test set 1で通って安心してそのまま提出したけど、Test set 2ではTIME LIMIT EXCEEDEDになってしまっていた。 考慮が足りていなかったようだ…

結果

奇跡的に73ptで871位で通過できた、っぽい。嬉しい

将棋駒画像の分類器をラクして作る

ちょっと将棋関連の画像認識をやってみたいな、と思って。

理想的には、将棋の盤面の写真や盤面図の画像から認識を行い 盤面の状態をデータとして取得できるようにしたい。

となると、

  1. 入力画像から盤面の部分を検出し、切り出す
  2. 切り出した盤面をさらに、9x9の各マスに分割する
  3. 分割した各マスに対し どの駒が置かれているか(もしくは何も置かれていないか)を分類する
  4. さらに持駒の部分も画像内から検出し、同様に分類

といった処理が必要になりそう。 1, 2, や 4, の処理はともかくとして、3, の分類はアイドル顔認識と同じようなimage classifierで出来るはずなので、まずはこれを作ってみることに。

目標

将棋盤における駒の状態として有り得るのは「歩兵」「桂馬」「香車」「銀将」「金将」「角行」「飛車」「王将」の8種類、それに成駒である「と金」「成香」「成桂」「成銀」「竜馬」「竜王」を加えた14種類、それぞれ先手側と後手側があるので倍の28種類。そして何も駒が置かれていないマス、も分類対象に加える必要があるので合計で29 classの分類taskとなる。

また さらに、「将棋盤のマスでも何でもない、まったく関係ない画像である」というclassも含めても良さそう。このへんは用途によるかもしれない。

とにかく、この 29 or 30 classの分類を高精度・高速度でできるImage classifierを簡単に作りたい。

データセットを「生成」する

普通の画像分類には大量の「画像」と「正解ラベル」のセットが学習データとして必要になるが、それを用意するのがとにかく大変。 将棋駒のラベル付きデータセットがどこかに公開されていれば良いけど、少し探してみた限りではやはり存在してないようだ。

アイドル顔画像のときのようにやろうとすると、様々な将棋盤の画像を収集して 盤面を切り抜いて 各マスに分割して ラベル付けて… を繰り返すことになる。 極力それは避けたい。

ということで、画像データを自動的に「生成」して用意することを考えてみる。

有り難いことに、将棋盤画像を生成するのに使える良い素材を無料で公開してくださっている方々がいる。

kifulog.ko31.com

こちらの記事で紹介されている素材データは、それぞれ盤の画像と 透過pngの駒画像が個別に用意してあり(「しんえれ外部駒」は背景色固定の駒画像のみ)、これらを貼り合わせることで任意の盤面画像を作ることができる。

例えば以前の記事で載せている

f:id:sugyan:20171119215709p:plain

のような画像は、すべて「CC Resources for Shogi Applications」に含まれている盤・枠・駒それぞれの素材画像を使って貼り合わせることで生成している。

任意の盤面を自由に生成できるということは、当然どの位置にどの駒が置かれているかを分かっているということなので、生成した盤面画像から対象の駒の置いてあるマスの位置を切り抜いて、それと正解ラベルを関連づけることができる。 例えば上記の画像を生成した上で 2三 の位置のマスの部分を切り抜けば、それを「歩兵」としてラベル付けしたデータとして扱うことができる。

f:id:sugyan:20180427120917p:plain

必要な画像処理は

  • 画像の任意の位置に別の透過画像を貼り付ける
  • 任意の位置を切り抜く
  • 任意の大きさにリサイズする

くらい。これらは Pillow でもあれば簡単に実現できる。

また、素材画像の組み合わせではなくすべて自分で描画して生成することも出来る。 よく書籍などで使われる局面図は、漢字一文字(もしくは二文字)で表現される。

f:id:sugyan:20180427123119p:plain

(上図はShogipicより)

こういうものも、枠線を引いて任意のマス位置に文字を描画(後手側の場合は180°回転をする)することで生成することができる。 OSに入っているヒラギノ*.ttcなどのフォントを使って複数の種類のものを生成できる。

これらの方法で画像を生成し、自動でラベル付けする というより「ラベルに合う画像を生成する」という手法でデータセットを作ってみた。 素材の組み合わせを変えたり 画像の質を変えたりして少しずつ違う画像が生成されるよう調整し、各駒300〜400点が全自動で生成できた。

f:id:sugyan:20180427124355p:plain f:id:sugyan:20180427124404p:plain

TensorFlow Hubのモデルを使って学習

データセットがある程度用意できたら、いよいよこれらを識別する分類器を作る…ところだけど、これも既存のものを再利用できるならそれがラクで良い。

3月末に行われたTensorFlow Dev Summit 2018で、「TensorFlow Hub」が発表された。 ここで様々な学習済みモデルが公開され、独自データセットでの利用のための再学習の仕組みも整備されているようだ。

この中にある examples/image_retraining/retrain.py を使うことで、TensorFlow Hub のモジュールを使用して独自データに対する学習ができる。

今回は mobilenet_v2_100_96/classification/1 というMobileNet V2のものを使ってみた。

python retrain.py \
    --image_dir ${IMAGEDIR} \
    --tfhub_module https://tfhub.dev/google/imagenet/mobilenet_v2_100_96/classification/1 \
    --how_many_training_steps 10000

これで、指定したモジュールをダウンロードし そのモデルを使って指定ディレクトリ以下の画像データに対する分類のための再学習を行ってくれる。 distortionを行わない場合は最初に全データに対するbottleneckを計算してそれを使っていくだけのようなので、手元のMacBookProのCPUでも10,000 stepsくらいなら十数分程度で学習が完了する。

f:id:sugyan:20180428013442p:plain

順調にcross entropyが減少し、train dataset に対してはほぼ100%、validation datasetに対しても97〜98%くらいの正答率になっている。

結果と考察

学習が終わると output_graph.pb ファイルが書き出されるので、これを使って実際に幾つかの画像を入力して試してみる。

入力データは (?, 96, 96, 3) のshapeを持つTensorで、値は[0, 1]の範囲にscalingされたものとして学習されているので、それに合わせてやる必要がある。

盤面の部分だけを切り抜いた画像を用意し、縦横それぞれ9分割して81マスすべてに対して学習済みの分類器にかけて 最も高スコアになったラベルを表示してみる。

1. 学習データに使った素材で作ったもの

f:id:sugyan:20180501012958p:plain

-KI * +TO * -OU * +TO+TO+NY
 * -FU *  *  * +FU *  *  * 
+RY-TO *  * -FU-FU * -FU-KY
 * +KE+KE-GI-KI-TO *  * +RY
-UM-NK+KY+TO * -TO *  *  * 
 * +FU *  *  * -GI-GI+FU * 
 *  * +FU * +TO-GI *  * +KE
 *  *  *  * +TO * +FU * +KY
+UM *  *  *  *  * +KI * -KI

学習データそのままなのだから、当然と言えば当然なんだけど、すべて正解。

そのままとはいえ少し縦長のものを96 x 96にリサイズしているので縦横比など少しずれているとは思うのだけど、そのへんは上手く吸収してくれているようだ。

2. Shogipicで生成された局面図

f:id:sugyan:20180501013010p:plain

漢字のみで表現するタイプのもの。 これは…何というフォントを使って生成されているんだろう? ヒラギノ丸ゴ?であれば学習データにも含まれている。

-KI * +TO * -OU * +TO+TO+NY
 * -UM *  *  * +FU *  *  * 
+RY-TO+UM+UM-UM-FU ? -UM-KY
 * +KE+KE-KA-KI-TO ?  * +RY
-UM-KA+KY+TO * -TO *  *  * 
 * +FU ?  ?  * -KE-KE+FU * 
 *  * +FU ? +TO-KE ?  * +KE
 *  *  *  * +TO * +FU * +KY
+UM *  *  *  *  * +KI * -KI

不思議なことに 2三5三8二 などの後手側の「歩兵」が「竜馬」として認識されてしまっている。 4三 の位置のものは正しく「歩兵」になっているのに…。

それぞれ切り抜いて認識結果の上位3つとscoreを出してみる。

4三

f:id:sugyan:20180502174326p:plain

W_FU: 0.6095971
W_UM: 0.25771713
W_TO: 0.095992066

5三

f:id:sugyan:20180502174343p:plain

W_UM: 0.69194067
W_FU: 0.10603738
W_TO: 0.07219603

8二

f:id:sugyan:20180502174357p:plain

W_UM: 0.62901
W_TO: 0.24588391
W_NY: 0.05405906

うーん、真ん中部分は大きく違わないはずなのに結果は随分バラバラになる…。枠線部分の影響を強く受けてしまっているのだろうか…

その他にも、「銀将」が「桂馬」になってしまっていたり、「成桂」が「角行」になってしまっていたり、誤判定が目立つ。

3. 激指 14の局面スクリーンショット

f:id:sugyan:20180501013026p:plain

こちらは学習データの素材とはまったく関連がない画像、のはず。同じ駒でも微妙に模様が違っていたりする。とはいえ最もメジャーな菱湖書体、のものなのかな?

-KI * +TO * -OU * +TO+TO+NY
 * -FU *  *  * +FU *  *  * 
+RY-TO *  * -FU-FU * -FU-KY
 * +HI+HI-GI-KI-TO *  * +RY
-UM-NG+KY+TO * -TO *  *  * 
 * +FU *  *  * -GI-GI+FU * 
 *  * +OU * +TO-GI *  * +HI
 *  *  *  * +TO * +FU * +KY
+RY *  *  *  *  * +KI * -KI

2. のものよりは正答率が高いようだ。

8五 の「成桂」が「成銀」になってしまっているのは似ているから仕方無いかな、という感じはするけど、 7七 の「歩兵」が「王将」になってしまっているのはヒドい。その他にも 1七 の「桂馬」が「飛車」になってしまっていたり、やっぱりちょっと理解できない誤答がある…。

4. Shogi.ioの局面スクリーンショット

f:id:sugyan:20180501013041p:plain

-NG * +TO * -FU * +TO+TO+UM
 * -FU *  *  * +NK *  *  * 
-UM-TO ?  * -FU-FU * -FU-NG
 * +KE+OU-GI-NG-TO *  * +KE
-NG-UM+NG+TO * -TO *  *  * 
 * +NK ?  *  * -GI-GI-UM * 
 *  * +NK * +TO-GI *  * +KE
 *  *  *  * +TO * -UM * +NG
-UM *  *  *  *  * +NG * -NG

なんと、ビックリするくらい当たらない。めちゃくちゃだ。正解しているのは「と金」と後手の「歩兵」くらいか…? 駒の向きさえ正しくない場合がある。

そういえば今回作成したデータセットにはこのような形の「一字駒」を使用していなかった。 まったく学習していないタイプの駒画像なので正解しないのは当然と言えるかもしれない。「と金」だけは普通の書体の駒でも一字のものになるから似ていて正答できているのかもしれない。

この一字駒系はあまりフリー素材としては公開されていないのかな? しかしこうした局面図も正しく認識できるようにするためにはこうした一字駒も学習データに加える必要がありそうだ。

まとめ

一応それっぽく簡単に学習データを作って学習させて分類モデルを作ることは出来た。 が、使えるかどうかというと全然まだまだダメそう。

枠線の影響を受けずにもっとロバストに駒部分を正しく分類できるように、また一字駒などに対しても正しく分類できるよう より良い学習データを作る必要がありそうだ。

分類モデルの再利用については MobileNet V2のもので問題ないか、他のモデルを使った方が良いかどうか? もう少し良質な学習データが揃ってから検証したいところ。

参照

Repository

Google Code Jam 2018: Qualification Round

Google Code Jamに今年もチャレンジ。

(昨年の: Google Code Jam 2017: Qualification Round - すぎゃーんメモ)

今年もRubyで、と思って最初の問題を解いてコード提出してみたのだけど、Runtime Errorになって上手くいかなくて、なんで??と思ってPython3に変更して(結局Runtime Errorは単純なバグだったんだけど) そのまま他の問題もPython3で提出した。

Saving The Universe Again

C (charge) と S (shoot) からなる文字列が与えられ、倍々になって蓄積されるダメージを一定量まで減らすための最低操作回数を求める。

文字列を1つずつ読んでいけばダメージ総量はすぐに求められる。あとはこれをどのように減らしていけるか。 効率的に減らすためには最大ダメージのもの つまり最後方にあるSを直前のCと交換することで つまり1回の操作は「ダメージ最大のものを半分に減らすこと」と考えられる。 初期値のダメージ総量は1回だけ計算すればよくて、あとはshootによるダメージと回数の辞書を作って 最大ダメージのものから選択してその回数を減らし 半分の値の辞書エントリの回数の方に加える。減少させた総量 > ダメージ初期値 - 防御力になるまでそれを繰り返せばよさそう。 足し算引き算を繰り返しても良かったけど、掛け算的に一気に処理もできるな、と思ってそうしてみた

t = int(input())
for i in range(1, t + 1):
    d, p = input().split(' ')
    d = int(d)
    dam = {}
    s = 1
    for c in list(p):
        if c == 'C':
            s *= 2
        if c == 'S':
            dam[s] = dam.get(s, 0) + 1
    s = sum([k * v for k, v in dam.items()])
    a = 0
    while s > d:
        m = max(dam.keys())
        if m == 1:
            a = 'IMPOSSIBLE'
            break
        r = m / 2 * dam[m]
        if s - r > d:
            s -= r
            a += dam[m]
            dam[int(m / 2)] = dam.get(int(m / 2), 0) + dam[m]
            del(dam[m])
        else:
            a += int((s - d) / (m / 2))
            if (s - d) % (m / 2) != 0:
                a += 1
            break
    print('Case #{}: {}'.format(i, a))

Trouble Sort

数値の列が与えられたときに「順番に連続の3つの数字並びを見て 左端より右端の数値の方が大きくなるようswapする」という操作を繰り返すsortingを行ったときに、正しくsortされない箇所を求める。

実際にこれを実行するとそれなりに実行時間がかかるはずなのでシミュレーションして求める、のはダメそう。 とはいえどうすれば良いか分からなかったので最初は実際にそれを実装してランダムな初期値を与えて実行結果を観察してみた。 先頭に来るべき最小値が0番目じゃなくて1番目に来ることがある… 2番目に小さな値が先頭に来たり… → はっ これは初期状態の位置が偶数番目か奇数番目かによるな → そういえばn番目の要素はn+2番目の要素としか交換しないのか →つまり奇数番目の要素による数値列と偶数番目の要素による数値列が別々にsortされる、と考えれば良いのか、とようやく気付いた。

あとは普通に分けてsortしたものを先頭から比較して見ていって 昇順でなくなるところを検出する。

t = int(input())
for i in range(1, t + 1):
    n = int(input())
    v = [int(e) for e in input().split(' ', n)]
    a = 'OK'
    e, o = [], []
    for j, val in enumerate(v):
        if j % 2 == 0:
            e.append(val)
        else:
            o.append(val)
    e.sort()
    o.sort()
    for j in range(len(o)):
        if e[j] > o[j]:
            a = j * 2
            break
        if j < len(e) - 1 and o[j] > e[j + 1]:
            a = j * 2 + 1
            break
    print('Case #{}: {}'.format(i, a))

Test set 2 では 3 <= N <= 10 ** 5 とのことで10万要素あると普通のsortも結構時間かかってダメかも…?と思ったけど それ以上の方法が思い付かなかったのでこのまま提出。

Go, Gopher!

なんか問題が複雑そうで読むのもつらかったので捨て…

Cubic UFO

立方体による影の面積が指定された値になるよう回転させたときの各面の座標を求めよ、というもの

すごい難しそう、とは思ったものの、Test set 1は 1.000000 ≤ A ≤ 1.414213という制約があったので、0°から45°までのz軸固定の回転のみで考えても良さそう。 Aの面積は cos(回転角 - 45°) * sqrt(2)で算出できるのは単純な計算で分かるので、それを解いて必要な回転角度を出して、それをもとに座標を出す。

import math

t = int(input())
for i in range(1, t + 1):
    a = float(input())
    r = 45.0 * math.pi / 180.0 - math.acos(a / math.sqrt(2))
    print('Case #{}:'.format(i))
    print('{:.8f} {:.8f} 0.0'.format(0.5 * math.cos(r), 0.5 * math.sin(r)))
    print('{:.8f} {:.8f} 0.0'.format(-0.5 * math.sin(r), 0.5 * math.cos(r)))
    print('0.0 0.0 0.5')

明らかにTest set 1のみのための解法でTest set 2には絶対通らないけど、これで提出

結果

"Saving The Universe Again", "Trouble Sort" は無事にどちらも正解だったようで、"Cubic UFO"のTest set 1の正解もあわせて合計49ptで通過した模様。

次のRoundはもう全然通過できる気がしないけど頑張ろう…