Big Sky

自宅で動かしている物体認識サーバは TensorFlow を使って Go で書かれていたのだけど、CPU 負荷が高いので以前 go-tflite で書き換えた。その後 Raspberry Pi Zero W でそのまま使えるだろうと思っていたら結構リソースが厳しかったので C++ なウェブサーバの実装である crow と TensorFlow Lite を使って書き換える事にした。

GitHub - ipkn/crow: Crow is very fast and easy to use C++ micro web framework (inspired by Python Flask)

How to Build If you just want to use crow, copy amalgamate/crow_all.h and include it. Requirements C...

https://github.com/ipkn/crow/

ただし問題があって、crow は最新の boost を使ってビルドするとエラーが発生する。issue に書いたら親切な人がパッチを貼ってくれたのでローカルの amalgamate コードに適用した。

Cannot build on boost 1.70 · Issue #340 · ipkn/crow · GitHub

g++ -std=c++14 -c -I../include -I. helloworld.cpp -o helloworld.o In file included from ../include/c...

https://github.com/ipkn/crow/issues/340

これで実装できるだろうと思っていたら、なんと crow はマルチパートアップロードをサポートしていない事に気付く。他のウェブサーバ実装を探しても良かったのだけど、どうせ家で動かすウェブサーバだしアタックを受ける事もないので若干雑な実装ながらマルチパートアップロードを実装した。

typedef struct {
  std::map<std::string, std::string> header;
  std::string body;
} part;

static void
trim_string(std::string& s, const char* cutsel = " \t\v\r\n") {
  auto left = s.find_first_not_of(cutsel);
  if (left != std::string::npos) {
    auto right = s.find_last_not_of(cutsel);
    s = s.substr(left, right - left + 1);
  }
}

static std::vector<std::string>
split_string(std::string& s, const std::string& sep, int n = -1) {
  std::vector<std::string> result;
  auto pos = std::string::size_type(0);
  while (n != 0) {
    auto next = s.find(sep, pos);
    if (next == std::string::npos) {
      result.push_back(s.substr(pos));
      break;
    }
    result.push_back(s.substr(pos, next - pos));
    pos = next + sep.length();
    --n;
  }
  return result;
}

static std::map<std::string, std::string>
parse_header(std::string& lines) {
  std::map<std::string, std::string> result;
  std::string::size_type pos;
  for (auto& line : split_string(lines, "\r\n")) {
    auto token = split_string(line, ":", 2);
    if (token.size() != 2)
      break;
    trim_string(token[0]);
    std::transform(token[0].begin(), token[0].end(), token[0].begin(), ::tolower);
    trim_string(token[1]);
    result[token[0]] = token[1];
  }
  return result;
}

static std::vector<part>
parse_multipart(const crow::request& req, crow::response& res) {
  auto ct = req.get_header_value("content-type");
  auto pos = ct.find("boundary=");

  std::vector<part> result;
  if (pos != std::string::npos) {
    auto boundary = "\n--" + ct.substr(pos + 9);
    pos = boundary.find(";");
    if (pos != std::string::npos)
      boundary = boundary.substr(0, pos);
    pos = 0;
    auto& body = req.body;
    while (true) {
      auto next = body.find(boundary, pos);
      if (next == std::string::npos)
        break;
      auto data = body.substr(pos + boundary.size() + 2, next);
      auto eos = data.find("\r\n\r\n");
      if (eos == std::string::npos)
        break;
      auto lines = data.substr(0, eos);
      part p = {
        .header = parse_header(lines),
        .body = data = data.substr(eos + 4)
      };
      result.push_back(p);
      pos = next + boundary.size() + 1;
      if (body.at(pos) == '-' && body.at(pos + 1) == '-'
          && body.at(pos + 2) == '\n')
        break;
      else if (body.at(pos) != '\n')
        break;
    }
  }
  return result;
}


API 部分しか実装していないので使う場合は以下の様に curl コマンドを使う。

$ curl -X POST http://localhost:8888/upload -F "file=@grace_hopper.png;type=image/png"
[{"label":"bow tie","index":458,"probability":0.996078}]


OpenCV を使ってるので OpenCV がサポートしている画像フォーマットであれば使えるはず。適当なレベルではあるけど、こういうの欲しいと思ってる人もいるんじゃないかなと思ったので GitHub に置いておいた。

GitHub - mattn/crow-tflite-object-detect: Object detection API server using crow webserver and TensorFlow Lite.

crow-tflite-object-detect Object detection API server using crow webserver. Usage -1 curl -X POST htt...

https://github.com/mattn/crow-tflite-object-detect

以前 TensorFlow Lite の Go バインディングを書いたのだけど

Big Sky :: TensorFlow Lite の Go binding を書いた。

Google launches TensorFlow Lite 1.0 for mobile and embedded devices | VentureBeat Google today intro...

https://mattn.kaoriya.net/software/lang/go/20190307190947.htm

これの mruby 版を作ってみました。

GitHub - mattn/mruby-tflite

model = TfLite :: Model .from_file " xor_model.tflite " interpreter = TfLite :: Interpreter . new (m...

https://github.com/mattn/mruby-tflite

TensorFlow Lite がライブラリ単体として配布されていないので、ビルドは少し難しいですが頑張って下さい。使い方は簡単です。以下 XOR (排他的論理和) なモデルの作り方と、そのモデルを使って推論する Ruby スクリプトを紹介します。keras で XOR... は説明が長くなるので省略します。知りたい方は調べて下さい。

import numpy as np 
from keras.models import Sequential
from keras.layers import Dense, Activation
from keras.optimizers import SGD

model = Sequential()
model.add(Dense(8, input_dim=2))
model.add(Activation('tanh'))
model.add(Dense(1))
model.add(Activation('sigmoid'))

sgd = SGD(lr=0.1)
model.compile(loss='binary_crossentropy', optimizer=sgd)
X = np.array([[0,0],[0,1],[1,0],[1,1]])
y = np.array([[0],[1],[1],[0]])
model.fit(X, y, verbose=True, batch_size=1, nb_epoch=1000)
model.save('xor_model.h5')


HDF5 なファイルを吐けば TFLiteConverter を使って TensorFlow Lite のモデルファイルが生成出来ます。

import tensorflow as tf
import tensorflow.contrib.lite as lite

converter = lite.TFLiteConverter.from_keras_model_file("xor_model.h5")
tflite_model = converter.convert()
open("xor_model.tflite", "wb").write(tflite_model)


TensorFlow Lite の C API を wrap する形にしてあるので、API を知ってる人なら使いやすいと思います。以下は生成されたモデルファイルを使って XOR を推論するサンプルです。

model = TfLite::Model.from_file "xor_model.tflite"
interpreter = TfLite::Interpreter.new(model)
interpreter.allocate_tensors
input = interpreter.input_tensor(0)
output = interpreter.output_tensor(0)
[[0,0], [1,0], [0,1], [1,1]].each do |x|
  input.data = x
  interpreter.invoke
  puts "#{x[0]} ^ #{x[1]} = #{output.data[0].round}"
end


リポジトリには FizzBuzz を扱う例も置いてあるので Ruby で TensorFlow Lite やりたかった人(いるのか)には嬉しいかもしれません。ただ残念ながら現状 MRuby の gems には画像を描画できる物が無かったので顔認識の様な物を簡単に作る事が出来ませんでした。これは別途 gem が出来れば実現できるはずです。

先日、mopp さんが Vim に flatten() を追加するプルリクエストを追加してくれたのだけど、その時の記憶を整理する為に書く自分の為の記事。

add flatten() to flatten list by mopp - Pull Request #3676 - vim/vim - GitHub

I'm a bit confused by the maxdepth argument. I would expect it to specify the maximum depth of the r...

https://github.com/vim/vim/pull/3676

Vim script のリストは以下の様に、異なる型が混在できる。Ruby や他のスクリプト言語でも一般的。そしてスクリプト言語には一般的にリストを平坦化する為の flatten という関数ないしはメソッドが用意されている。

let foo = [1, 2, ["bar"], 3]


Vim本体に組み込み関数を追加するパッチを投げた - Qiita

Vim本体に手を加える 次に本体への修正ですが、大体1週間くらいで出来ました。 しかし、これは私一人の力ではなく、7割りくらい vim-jp のおかげです。 vim-jpは日本のVim開発者(Plug...

https://qiita.com/mopp/items/084abe28681202bda30e

mopp さんが Advent Calendar でその時の様子を書いてくれているんだけど、flatten() ははじめ再帰を使って書かれていた。途中で僕が「ループに直したらこうなる」という感じにコードを貼ってしまったので、後でループに直す実装を楽しみにしていた mopp さんには悪い事をしてしまった。申し訳ない。ぜひ次は flat_map() を実装して下さい。その時考えていたのだけど、flatten() の様な関数を再帰でなくループにするには本来ならばスタックに相当する何かが必要になるはずだろうと踏んでいた。なぜならリストを再帰降下するという事は戻り場所を知っておく必要があり、ループに直すのであればそれ相当のスタック配列が必要だと考えていたからだ。そして一般的にはこのスタック配列の実装がめんどくさいので皆再帰を使ってお茶を濁そうとする。僕もよくやる。

例えば以下の様な簡単なリスト構造を作ってみたとする。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef enum _type_t {
  INT_T,
  STRING_T,
  LIST_T,
} type_t;

typedef struct _value_t {
  int ref;
  type_t type;
  union {
    int n;
    char *s;
    struct _list_t *l;
  } val;
} value_t;

typedef struct _item_t {
  struct _item_t *next;
  value_t *value;
} item_t;

typedef struct _list_t {
  item_t *first;
} list_t;

static void
free_value(value_t *v) {
  item_t *i;

  if (v->ref-- > 0) return;

  switch (v->type) {
  case INT_T:
    break;
  case STRING_T:
    free((void*)v->val.s);
    break;
  case LIST_T:
    i = v->val.l->first;
    while (i != NULL) {
      item_t *next = i->next;
      free_value(i->value);
      free(i);
      i = next;
    }
    free((void*)v->val.l);
    break;
  }
  free((void*)v);
}

static value_t*
new_list_value() {
  value_t *v = malloc(sizeof(value_t));
  v->type = LIST_T;
  v->val.l = malloc(sizeof(list_t));
  v->val.l->first = NULL;
  v->ref = 0;
  return v;
}

item_t*
new_item(value_t *v) {
  item_t *item = malloc(sizeof(item_t));
  item->value = v;
  item->next = NULL;
  ++v->ref;
  return item;
}

static void
list_add_value(list_t *list, value_t *rhs) {
  item_t *i = list->first;

  if (i == NULL) {
    list->first= new_item(rhs);
    return;
  }

  while (i->next != NULL) {
    i = i->next;
  }

  i->next= new_item(rhs);
}

static void
list_insert_value(list_t *list, item_t *before, value_t *value) {
  item_t *next;
  
  if (before == NULL) {
    list->first= new_item(value);
    return;
  }

  next = before->next;

  before->next= new_item(value);
  before->next->next = next;
}

static void
list_remove_item(list_t *list, item_t *item) {
  item_t *i, *before = NULL;
  
  for (i = list->first; i != NULL; i = i->next) {
    if (i == item) {
      if (before == NULL)
        list->first = i->next;
      else
        before->next = i->next;

      free_value(item->value);
      free(item);
      return;
    }
    before = i;
  }
}

static value_t*
new_int_value(int n) {
  value_t *v = malloc(sizeof(value_t));
  v->type = INT_T;
  v->val.n = n;
  v->ref = 0;
  return v;
}

static value_t*
new_string_value(const char* s) {
  value_t *v = malloc(sizeof(value_t));
  v->type = STRING_T;
  v->val.s = strdup(s);
  v->ref = 0;
  return v;
}

static void
print_value(value_t *v) {
  item_t *i;

  switch (v->type) {
  case INT_T:
    printf("%d", v->val.n);
    break;
  case STRING_T:
    /* TODO: escape non-printable */
    printf("\"%s\"", v->val.s);
    break;
  case LIST_T:
    printf("[");
    for (i = v->val.l->first; i != NULL; i = i->next) {
      print_value(i->value);
      if (i->next) printf(", ");
    }
    printf("]");
    break;
  }
}

int
main(int argc, char* argv[]) {
  value_t *list, *sub;

  list = new_list_value();  
  list_add_value(list->val.l, new_int_value(1));
  list_add_value(list->val.l, new_string_value("foo"));

  sub = new_list_value();  
  list_add_value(sub->val.l, new_string_value("bar"));
  list_add_value(list->val.l, sub);

  list_add_value(list->val.l, new_int_value(3));

  print_value(list);
  free_value(list);
  return 0;
}


数値と文字列とリストが扱える物。リストの中にはそのいずれかを混入できる。お気持ち程度の参照カウンタを入れてあるが動くかどうか確認してないし本題はそこじゃない。これを実行すると以下の様に表示される。

[1, "foo", ["bar"], 3]


このリスト関数を使って flatten() を実装する場合、簡単に思い付くのが再帰を使った以下の方法。vital.vim でも再帰を使ってる。

function! s:flatten(list, ...) abort
  let limit = a:0 > 0 ? a:1 : -1
  let memo = []
  if limit == 0
    return a:list
  endif
  let limit -= 1
  for Value in a:list
    let memo +=
          \ type(Value) == type([]) ?
          \   s:flatten(Value, limit) :
          \   [Value]
    unlet! Value
  endfor
  return memo
endfunction


上記のリスト関数を使った場合だと以下の様になる。

static void
flatten_list(item_t *before, list_t *list) {
  item_t *i, *j, *prev = NULL;

  for (i = list->first; i != NULL; i = i->next) {
    if (i->value->type == LIST_T) {
      flatten_list(i, i->value->val.l);
      list_remove_item(list, i);
      return;
    }
    if (before != NULL) {
      list_insert_value(list, before, i->value);
      before = before->next;
    }
  }
}


リストを舐めながら要素がリストだったら挿入位置とそのリストを引数に要素を追加する関数(自身)を呼び出す。呼び出したあと元々リストがあった箇所を削除する。この flatten() は再帰を使ってるのでメモリを多く消費するしスタックオーバーフローで突然死してしまう可能性がある。でも良く考えると flatten() は、現在いる要素の子要素がリストの場合、そのリストの中身をすべて現在いる場所に移動し、自身を削除し、そして今と同じ箇所で再検査すればいいだけなのだ。スタックとして覚えておく必要もない。なので実装は以下の様になる。

static void
flatten_list(list_t *list) {
  item_t *i, *j, *prev = NULL;

  for (i = list->first; i != NULL; i = i->next) {
    if (i->value->type == LIST_T) {
      item_t *before = i;
      for (j = i->value->val.l->first; j != NULL; j = j->next) {
        list_insert_value(list, before, j->value);
        before = before->next;
      }

      if (prev == NULL)
        list->first = i->next;

      prev->next = i->next;
      i = prev;
    }
    prev = i;
  }
}


言ってみるならば、自分がネストに降下するんじゃなく、flat にする事でネストがこっちに上がってくるという事。実行すると以下が表示される。

[1, "foo", "bar", 3]


再帰は消え、スタックオーバーフローの心配もなくなり、メモリの消費量も減り、良い事づくめだ。逆に、今まで何度か flatten() は書いた事があるけどなぜ自分はこれまで flatten() を再帰で作ろうと考えてしまったのかと思い起こしたくもなった。

追記 この最適化方は自身のリストが破壊されるから出来る方法なので、flatten 済みのリストをを返す場合には使えないので注意。