マエカワの備忘録的な何か

思い立ったが吉日

ソフトウェア工学 其の八 20171214

構造化分析(続き)

 前回出てきた図は「業務をモデリング」していることをもう一回書いておく。このように、モデリングを図にして表したものをDFD(Data Flow Diagram)と呼ぶ。構造化分析以外のことをするにしても、このDFDをキチっと理解していないとダメらしい。何かを理解するときに、この図を頭の中にイメージできるといいエンジニアになるとも。ちゃんと理解しよう。
 DFDはフローチャートと似ているが、異なるものだということを頭に置いておかなければならない。フローチャートは「プロセスの実行順番・制御」について記述したもの。DFDは「データの流れ」を記述したもの*1

DFDの書き方

 具体的なDFDの書き方を以下に書いていく。

構文解析

 仕様書を構文解析することによって、作りたいシステムに必要なことを抜き出す。具体的には名詞と動詞を抜き出していく。どのような機能が必要で、そこでは何をするのかを明確にする。

レベル0DFDを書く

 そのシステムがどのようなものなのかだけを書いておく(どんな入力を受けて何をするのか)。なので、プロセスの数は1個。仕様書の文脈だけを図にしているとも表現できるので、レベル0DFDのことをcontext diagramと呼んだりもする。

DFDを再帰的に詳述する(水平・垂直分割する)

 分割していくたびにDFDのレベルが上がっていく。
 分割する際の注意点は、ちょっとだけ分割するということ。分割していくほど、各プロセスの仕様書を書くことができる。この仕様書のことをPSPECと呼ぶ。PSPECを構文解析、詳細分割していくことで、下位のPSPECが手に入る。この処理を繰り返し繰り返し、分割不可能なところ(具体的なアルゴリズムが想像できる)まで行っていく。このことを段階的詳細化と呼ぶ。
 一般的にはレベル7DFDまで書くのだが、1回で5個に分割できるとすると、レベル7DFDは7万8千くらいのプロセス。とんでもない量になる。仕様書が膨大になるわけだ。

データディクショナリ

 設計段階で出てくる用語をまとめたもの。誰でも理解できるように書く必要がある。


 上に示したDFDという考え方など、ソフトウェア工学に出てくる概念はとても簡単なものが多い。その理由は、大規模で複雑なシステムを良く作るための学問だから。現実社会でも、問題にぶち当たったとき、どのように簡単にシンプルに問題を変換して解決するのかが重要になってくる。そういうところにも使える基礎的な知識だ。

 さて、ここまでやってきたのが構造化分析。DFDでシステムの業務をモデリングすることはできたが、ここからどのようにプログラムに落とし込むのか。これが残りの内容で、構造化設計という。

構造化設計

STS分割

 全てのDFDに共通する特徴は、

  • 前半でデータの整理
  • 真ん中ででデータの処理
  • 後半でデータの整理

ということ。つまり、DFDは上の特徴に従って3つに分割して考えることができるということだ。この分割方法をSTS分割と呼ぶ。

モジュール構造図

 STS分割されたDFDはいったい何を表しているのだろうか。それは、関数の呼び出し関係だ。例として、プロセス ASTS分割によって、 a, b, cという部分(モジュール)に分割されたとする。これは、 a, b, cという関数を順番に呼び出しなさいという表現に読み替えられる。さらに、各関数の中身(モジュール)はDFDに具体的にきっちり書かれている(そうなるようにDFDは記述されているはずだ)。これを図にしたものをモジュール構造図と呼ぶ。
 気が付いたら、コーディングすべきことが分かっている。DFDをモジュール構造図に落とし込むことこそが、構造化設計

モジュール構造図の形について

 構造化設計では、分割するほど末広がりな形になるのだろうか。
 答えはNoだ。下の方ので共通するモジュール(例えば、画面に文字列を表示するとか)が出てくるので、そんなに広がらない。一番理想的な形は、ひし形。モジュールを増やすので途中までは広がるが、ある時点で共通モジュールの関係でしぼんでいく。

良い設計とは

 良い設計の特徴をいかに箇条書きにする。

  • 縦に分割→各サブツリーの機能が分かる
  • 横に分割→上の方はドメイン(機能・分野)の言葉、下の方は実行環境の言葉で書かれている
  • ファンアウト・ファンイン・幅・深さのバランスがいい

こんな感じ。
 小々節「モジュール構造図の形について」で、出てきた「ある時点」とは、ドメインの言葉と実行環境の言葉が入れ替わるあたり

ファンアウト・ファンイン

 新しい言葉が出てきたのでここで補足。
 ファンアウトとは、一つのモジュールから伸びている線の数。ファンインとは、一つのモジュールへ伸びている線の数。この二つの値が近い方が、モジュール構造図の理想形に近い構造になっている

*1:http://www.dab.hi-ho.ne.jp/sasa/hyoryuki/dfd/に、フローチャートとDFDの違いについて書いてあるので参考に。

物体認識論の課題を解くために

はじめに

 こんにちは。マエカワと申します。
 自分も取っている「物体認識論」という講義。MATLABを使って画像認識をしていく講義なのですが、その途中で出てくる、そして最終課題でも必要になってくるBag of Featureという考え方がとても分かりにくい。講義は毎回聞いてはいるのですが、とにかく分かりにくい。演習中にどんどん説明しちゃうもんだから、「聞く」と「プログラムを書く」を同時にできない人にとってはとても厳しいものがあります。
 なので、今回BoF周りの考え方を一気に備忘録として書いていきたいと思います。難しいプログラムはなるべく書きません。概念だけ、理解の仕方だけふわっと書いていくつもりです。
 それでは、お付き合いのほどよろしくお願いします。

 以下、今回の目次です。順番に理解できるように書いていきますが、「こんなのもうわかってんだよ!」という方は目次のコンテンツをクリックして該当箇所に飛んでください。

CodeBook

 BoFが何なのかを書く前に、まずはすべての根幹であるCodeBookについてです。これが理解できてないと、始まらない。
 CodeBookですが、簡単に言ってしまえば「辞書」です。CodeBookの各列ベクトルが一つのカテゴリ(単語)を表していて、中に入っている値がそのカテゴリの特徴量(意味)を表しています。絵で描きましょう。

f:id:maekawa_yoshimiki_1119:20180201020224j:plain:w700

講義ページに書いてあるサンプルコードの最後でK-meansを適用しているのも、画像から得られたSIFT特徴量をカテゴライズするためだと考えれば自然です。
 では、CodeBookのサイズ(列サイズ)とは何なのか。ここまで理解できれば、「単語の数」だということが理解できます。得られた大量の情報を何個の単語に分けるのか。このサイズが大きいほど、より正確なCodeBookが出来上がります。計算時間は半端ないですが。
 ちなみに、CodeBookの行サイズは128です。これは、SIFT特徴量が一つにつき128次元のベクトルで出てきたことが関係しています。ただ、ここでは「単語一つにつき128個のパラメータがあるんだな」くらいに思っておいてください。
 ここまでで覚えておくことは、

  • CodeBookは辞書
  • 列のサイズは「単語の数」
  • 行のサイズは128

ということくらいです。

Bag of Feature

 大本命のBoFです*1。まず最初に、一つの画像についてのBoFベクトルを手に入れるためのフローチャートを書いてみましょう。

  1. 「1×CodeBookのサイズ」の零ベクトルFを作る
  2. 画像ImgのSIFT特徴量を手に入れる
  3. SIFT特徴量一つとCodeBookを比べて、一番似ているところのインデックスidxを手に入れる
  4. F[idx]の値を1増やす
  5. 3. 4. を画像のSIFT特徴の数だけ繰り返す

最終的に手に入るのは「1×CodeBookのサイズ」のベクトルです。絵に描いてみましょう。

f:id:maekawa_yoshimiki_1119:20180201020246j:plain:w700

3番目の処理で列ベクトルどうしを比べることができるのは、CodeBookの行サイズとSIFT特徴量の行サイズがともに128だからですね。
 課題ではこれを100枚、200枚の画像を使い、得られたBoFベクトルを転置して結合しました。その結果「CodeBookのサイズ×画像の数」のBoFベクトルを作り上げたわけです。

f:id:maekawa_yoshimiki_1119:20180201020307j:plain:w700

 ここまで理解できれば、NN法、NB法の理解も速いはずです。

NN法、NB法に進む前に

 これからNN法やNB法で未知の画像を分類していくわけですが、未知画像の何をもって比較していくのかという話をここで書いていきます。上で、「一つの画像についてのBoFベクトル」を手に入れるための方法を書きました。まさにこのフローチャートを未知画像に適用してあげればいいんです(2つ前の画像のフローチャートを未知画像にやっていきます)。
 手に入った「1×CodeBookのサイズ」のベクトルと、BoFベクトルをNN法、NB法それぞれの方法で評価して、適応度の高い画像を選ぶという感じです。
 講義課題では「簡単のため」と称して、学習に使った画像データを再分類しているのでわかりにくくなったのかもしれません。

Nearest Neighbor 法

 NN法は、あらかじめ手に入れてあるBoFベクトルのうち、最も未知画像のBoFベクトル(1行のやつ)と似ているものを一つ選ぶという処理をしています。絵で描きましょう。

f:id:maekawa_yoshimiki_1119:20180201205335j:plain:w700

Naive Bayes 法

 NB法は、迷惑メールを分類するところなどで使われています。確率計算が入ってくるので少し手間取るかもしれませんが、本質は簡単です。まずは、学習データの取得について順を追って書いていきます。

  1. ポジティブ・ネガティブ画像ごとにBoFベクトルを手に入れる
  2. 各要素に1を加える
  3. ポジティブ・ネガティブごとにBoFベクトルの行ベクトルの値をすべて足し合わせ、「CodeBookのサイズ×1」のベクトルを手に入れる
  4. 得られたベクトルの総和でもって各値を割る(これで、各要素の合計値が1になります/正規化)
  5. 全ての要素にlogをはかせる

ここまでで、学習は終了です。得られた二つのベクトルには、各カテゴリ(これはCodeBookのとき出てきたカテゴリです)に属する確率がlogをはいた状態で入っています。今度は、未知画像の処理です。

  1. 未知画像からBoFベクトル(1行のもの)を手に入れる
  2. 転置する
  3. 値が0以上の要素のインデックスを手に入れる
  4. 得られたインデックスと対応する、ポジティブ・ネガティブ各学習ベクトルの要素を足し合わせる(logをはいてるからできること)
  5. ポジティブ・ネガティブから出てきた値を比べる
  6. 大きいほうのカテゴリに分類

これで、未知画像を分類することができました。文字だけだとつらいので、絵に描いてみましょう。

f:id:maekawa_yoshimiki_1119:20180201205336j:plain:w700

こんな感じ。講義での方法では未知画像のBoFベクトルに少しでも値が入っていたら、学習データの確立を足し合わせています。未知画像のBoFベクトルについても正規化をして、頻度に関して分類していくともう少し高い精度が出るかもしれませんね。
 メールの分類では、このポジティブネガティブが「スパム」「大学」「就活」などいろいろなカテゴリに分かれています。ですが、カテゴリが増えてもやることは同じなので何も怖くありません。学習ベクトルを出して、未知画像のBoFベクトルに応じて足し合わせていく。最終的に大きい値が出たものに分類。この流れがNB法です。

最後に

 ここまで見ていただいてありがとうございます。自分なりに解釈して書いてみたので、専門の方が見たら「何だこいつ、ふざけているのか」とおしかりを受けてしまいそうです。自分も理解が追い付かず、右往左往していたのでご容赦いただきたいものです。コメントに「ここはこうじゃね?」とか書いていただくと、自分へのフィードバックになりとてもありがたいです。
 MATLABでコードを書くにしても、仕組みが分かっていなければ何も始まりません。詰まっている人がコードを書く上での助けになってくれれば幸いです。それではこの辺で。



読んでいただいた方に感謝を
マエカワ

*1:課題ではいきなりBoFWという新しい知識が出てきて、思わずIEDのパソコンをたたきたくなりました。