いつも通り negainoido チームにお邪魔して参戦した. いつも通り私は、バイナリ解析といった王道な問題は全然なので、ちょっと邪道な問題に手を付けていた.
SECCON TOWER
問題は次の動画を読み取って PNG 画像を得よ、ということらしい.
考えたこと
ロボット？ (よく見ると伏せた紙コップの中にラズパイを仕込んで作ってある) がどうも手旗信号みたいなのを振っている. 最初の 70秒程度は、チュートリアルである. ロボットの動きに対して人間がノートに "WELCOMETO..." とペンで書き込む. ロボットの一つのポーズが一つのアルファベットに対応してることが推測できる. だとしてもいくつかのアルファベットが欠けているので完璧な対応表をここだけで得ることはできない.
以降50分に渡って、ロボットがひたすらポーズを取っていくので、対応する文字を列にして、何かしらの方法でバイナリにデコードすると PNG 画像になるのだろう.
ポーズとポーズとの間隔はほぼ、1秒であった. おそらく、ぴったり1秒になるように調整されてるのだと願い、フレームを切り出して、機械的に振り分けることにした. はじめは画像をピクセルのベクトルに変換して、コサイン類似度を取って、高かったら2つの画像は同じポーズを示している、、、、で分類することにした. ココらへんに関しては後述.
結局大事だったのは、とりあえず、ロボットの一つのポーズを一つの文字だと思って (それが実際には何の英字や数字に対応してるかは気にせず) 最初の100文字程度を手でアノテートしてみたこと.
ロボットの腕の形は、中心が固定されてぐるぐる廻る長い棒と、その両端に関節がある小さい棒の三本で構成される. 長い棒は、地面に対して、0度、45度、90度、135度の四通り. 小さい棒は、長い棒に対して、90度未満程度、右、左、または長い棒と重なった状態の三通り. 以上から、 4x3x3 で 36 通りありえる. これをラーメン屋でチームの皆に話した所、BASE36というのがあるらしい. 英字+数字で表現するらしい. しかし自分は36通りの内、35通りしか切り出したフレーム (ロボットのポーズの瞬間を取った画像) から発見できなかった (これについても後述). BASE36 なら 36 文字全てが出てこないのは怪しい.
フレームの切り出し
ポーズは1秒間隔で、動画は50分なので、ポーズ、すなわち読むべき文字は3000文字. 機械的にポーズを読むのを初め、目指すは目指すが、最悪、人間の力技で3000文字読むことも考えられる. どちらにしても、ポーズ画像を動画から得るのが必要だ. 何番目のポーズの文字は何々、という情報を共有するのに、動画を初めから睨んで、そのポーズが何番目かなんてカウントしたくないので.
最初、自分は次のように単純な方法でポーズ画像を得ることにした. あ、動画は YouTube にあるが、どうにかこうにかして手元に input.mp4 としてあるものとする.
# 動画 -> ポーズ ffmpeg -ss 75.5 -i ./input.mp4 -f image2 -vcodec png -r 1 "./pose/%05d.png"
75.5秒を起点に、1秒に1枚、スクリーンショットを取って保存する. これはロボットがぴったり一秒ごとにポーズを取ってくれることを期待している. ついでに、画像全体だと無駄が多い. ほしいのはロボットの腕部分だけだし、ついでにいうとカラー画像である必要はない. HDD を圧迫するし.
for f in pose/*.png; do g=crop/${f#*/} convert -crop 400x400+520+20 -type GrayScale $f $g; done
こんな感じ. 最初の方はいいんだが、後半、なんだかロボットの動きが鈍くなってく気がする. 動きがたま〜に、遅いんだか、まだ腕を動かしてる途中のフレームを切り出してしまうことがある.
躍動感がある. ちょっと腕がブレてるぐらいならいいが、実際と違うポーズに見える瞬間を切り取ってしまったことがあった. 先程、35通りのポーズを確認したと言ったがそれは嘘で、これが原因だった.
ちゃんとロボットが動きを止めてることを確認して、フレームを切り出さなければならなかったのだ. ここはチームメイトにタスクを投げたので私はやってないが、次のようなことをやってもらった.
- 全フレームを切り出す (動画は12fps)
- 隣接する2フレームの cos 類似度を取る
i番目とi+1番目のそれをk[i]とする
- 変数
iに初期値を与える i+12の周辺 (そのプラスマイナス2程度) でk[j]が最大となるjを探すj番目のフレームをポーズとして出力iをjで更新 (i <- j)
+12 周辺を見るのは、やはり基本的にポーズの次のポーズは 1 秒後、すなわち 12 フレーム後であるはずというヒューリスティック.
これできれいなポーズ画像が 3000 枚手に入る.
自動識別
きれいなポーズ画像が 3000 枚、手に入り、それまでにやってたアノテーションは誤りを多く含むことがわかった. 先程、 36 種類の文字を表現できるのに 35 種類しか発見できなかったと述べたが、実は誤りで、35 どころか 32 種類しか無いことが発覚した. ここらへんで @autotaker1984 さんが chappe system なるものを見つけ、加えて BASE32 であることを推理したので話が一気に簡単になった.
- chappe system はなんかセマフォアライン？の 1 プロコトルSemaphore line - Wikipedia
- Base32 は英字と数字を使うが 0, 1, 8, 9 は使われない Base32 - Wikipedia
いくつかすぐ気づく例外として、chappe system の "&" (アンパサンド) が SECCON TOWER の "J" である. あとあと、動画の最初のチュートリアルでは、次のポーズ、
は "." (ピリオド) に対応しそうな雰囲気だったが、BASE32に "." などない. 本番のスタートもこのポーズからスタートしているが、途中で一切出てこないので、気にしない (存在しない) ことにした. ちなみに padding の "=" というつもりでもないらしい. 動画の最後は "A" で終わっているので.
で、さて、自動識別であるが、フレームの切り出しにも利用した画像のコサイン類似度は、まるで使い物にならないことは結構初めに気づいていたので (今回これがダメな理由は CTF SECCON TOWERに挑んでみました - WGGの活動log にある通りです. でももっと工夫すれば頑張りの余地はありそう)、MNIST と同じ要領で簡単なCNNで32に分類させることにした.
コード自体は全然なんということもなく、chainer でちゃちゃっと書いた.
import chainer import chainer.functions as F import chainer.links as L class SecconTowerClassifier(chainer.Chain): def __init__(self): super().__init__( bn0=L.BatchNormalization(3), bn1=L.BatchNormalization(8), c1=L.Convolution2D(3, 8, 3), c2=L.Convolution2D(8, 32, 5, stride=2), c3=L.Convolution2D(32, 64, 5, stride=2), out=L.Linear(None, 32) ) def forward(self, x, train=False): h = x h = F.average_pooling_2d(h, 3) h = self.bn0(h) h = F.dropout(h, 0.5, train=train) h = self.c1(h) h = self.bn1(h) h = self.c2(h) h = F.elu(h) h = self.c3(h) h = F.max_pooling_2d(h, 3) h = self.out(h) return h def __call__(self, x, t): h = self.forward(x, train=True) loss = F.softmax_cross_entropy(h, t) # Acc n = x.data.shape[0] _i = chainer.cuda.cupy.argmax(h.data, axis=1).reshape((n, )) acc = chainer.cuda.cupy.sum((_i == t.data)) / n chainer.report({'loss': loss, 'acc': acc}, self) return loss
学習も何十分も回していない. なにより学習データを自分一人で作っていたので、そんなに数が無くすぐに収束する. 学習を回しながら学習データを増やしてって、ちょっと溜まったら学習をリスタートさせるというサイクルを30分位？繰り返していた.
以下、作ったデータセット. 行の頭がラベル (chappe system ならぬ seccon tower におけるポーズが表すシンボル) で、続く数字の列が、何番目のポーズであるか. 例えば 1 番目のポーズは "R". 2 番目は "F".
A 12 14 15 17 18 27 28 29 30 33 34 35 36 40 53 54 55 56 57 58 61 67 68 69 70 1137 1388 B 9 40 47 50 1520 1512 2427 C 23 63 88 2311 2594 D 1017 1032 2485 2469 E 4 24 49 1351 1348 1452 1386 2474 2452 F 2 37 60 698 703 2450 2407 2312 G 19 1040 402 1521 1517 H 52 71 1020 1665 1587 1387 2463 2421 2408 I 3 10 26 65 1015 1022 403 1952 J 91 1012 456 373 2025 1779 K 25 1005 1352 590 617 2835 2697 2655 L 77 1009 1029 1044 822 651 589 2974 2905 2263 M 42 79 1353 2252 2120 2042 1975 1903 1855 920 N 8 11 1025 1028 219 1156 O 89 1019 1003 1350 2253 1940 1924 P 1031 1042 400 1045 1273 1357 1930 2722 Q 39 1018 1033 2231 2324 R 1 6 90 999 1002 1034 S 21 22 1382 968 1065 1141 1207 1382 T 51 62 1041 1354 856 1875 U 13 20 64 66 82 94 1026 1027 1030 1035 V 48 1004 1036 1379 1362 W 31 38 78 1014 404 1108 1181 1330 1413 1522 1660 1960 2102 2175 X 1000 1010 1319 1672 1971 2864 Y 7 1021 1364 2264 2131 684 603 543 Z 1001 1013 1125 2266 303 412 494 2 32 76 855 2817 2546 2270 2198 3 81 1043 1380 1349 278 279 1446 1696 4 5 93 1016 1023 1363 5 1006 1039 1361 1356 401 405 6 1024 1383 2219 1570 1857 2333 7 72 73 74 75 80 95 96 97 98 530 522 256 788 1072 1088
見たら分かるように、「ディープラーニング」をするにはあまりにも事例数が足りない. 一応訓練事例において正解率 97% を超えてたことにはなった時点で学習を終了した.
たった 10 の文字に分類する MNIST ですら、100% の精度を出したという報告はない. すなわち多少の誤りは諦めるしかない. @autotaker1984 のアドバイスにより、機械学習の識別でポーズ画像をディレクトリに分けて、あとは人間の目でチェックすることにした. 基本的に分類はほぼ成功しており、人間は、多くの同じポーズの中に、別なポーズが混じっていないかを確認するだけなので、そんなに難しくはなかったし、誤りは 3000 ポーズ中、10 程度しかなかった.
10程度と言った誤りは全て、UとV、QとM の取り違いであった. 次にそれぞれのポーズを示す.
U
V
Q
M
まあ、似てる. しょうがない. 人間の手でチェックしたあと、base32 列になおしてバイナリに直したところ、次の画像を得た.
Macのプレビューでは強引に開けるものの、いまブログにアップロードしようとすると「未対応のファイル形式です」と怒られたし、明らかに最後の方、壊れてる. でもカメラでは読み取ることが出来た. 読み取るとフラグ及びスペシャルサンクスを得る. よかった.