遺伝的アルゴリズムを用いた特徴選択 によるパターン認識 同志社大学 三木 光範 同志社大学 廣安 知之 同志社大学大学院 永松 秀人 ○

研究背景 商品管理システムの現状 タグの不要なシステム バーコードが主流 タグ自体にコストがかかる 特殊な商品(多品種少量)を扱うのが困難 販売時に商品を撮影しデータベース上の 商品画像と比較する 画像認識により商品管理を行う

画像認識による商品管理システム アクセサリの商品管理 撮影時の置き方によって同一物体が異なる 見え方をする際の画像認識

画像認識のための処理 前処理部 特徴量抽出部 識別部 2値化 特徴量データの抽出 特徴量データベースとの マッチングにより識別 まず、一般的に計算機上で画像認識を行うにはこちらに示す処理の流れをとります。 識別対象となる画像が入力されると、前処理部で2値化などの操作が行われます。 そして特徴抽出部において、識別のために必要となる特徴量の抽出が行われます。 最後に識別部において、あらかじめ抽出している特徴量データと入力画像の特徴量の比較を行うことによって マッチングが行われ、入力画像の候補が出力されます。 では、最も単純な特徴量を用いた識別では、

特徴量を用いた識別 最も単純な識別 すべてのデータが識別に用いられるとは 限らない すべての特徴量データを用いた識別 特徴量は撮影条件，対象物体に依存 同一物体が異なる見え方を示す場合もある すべてのデータが識別に用いられるとは 限らない 入力データの全特徴量をデータベース上の各候補の全特徴量と比較することで行われます。 しかし、特徴量データは撮影条件、対象物体に依存すると考えられ、 同一物体が異なる見え方を示す場合などがあり、 全てのデータが識別のためのマッチングにもちいることができるとは限りません。

特徴量 幾何学的特徴量→形状に関する特徴量 統計的特徴量 →色に関する特徴量 統計的特徴量　→色に関する特徴量 実際に画像から得ることのできる特徴量データは大別すると幾何学的特徴量と統計的特徴量の 2種類に分けることができます。 幾何学的特徴量は面積、最大長、周囲長等の形状に関する特徴量であり、 統計的特徴量はRGB成分の平均値や分散等の色に関する特徴量です。 ここで、実際に画像より抽出した特徴量の具体例を示します。

特徴量抽出例(変化なし) 例：指輪 撮影例1 誤差：撮影例1を基準としたときの 撮影例2の変化量 撮影例2 特徴量 撮影例 1 撮影例 2 誤差(%) 面積 2437 2787 1.8 モーメント 0.6548 0.6352 3 外周囲長 342.9 344.4 0.4 全周囲長 605.2 607.6 撮影例1 こちらの例は，認識対象として指輪を用いた場合です。 撮影例１，撮影例2は商品の置き方を変えて撮影したものです． 撮影例1と撮影例2のそれぞれの特徴量データを比較するとこちらの表のようになります。 また，誤差とは，撮影例1の時の特徴量データを基準としたときの撮影例2の特徴量データの誤差を％表示したものです． こちらの表が示すように，撮影例1と撮影例2の特徴量データの誤差はわずかなものです． 誤差：撮影例1を基準としたときの 　　　撮影例2の変化量 撮影例2

特徴量抽出例(変化あり) 例：ネックレス 撮影例1 誤差：撮影例1を基準としたときの 撮影例2の変化量 撮影例2 特徴量 撮影例 1 撮影例 2 誤差(%) 面積 16110 17237 7 モーメント 0.3895 0.5219 34 外周囲長 1369.8 2035.5 48 全周囲長 3775.8 4490.2 19 撮影例1 一方，ネックレスを認識対象とした場合の例を示します． 撮影例１，撮影例2は商品の置き方を変えて撮影したものです． 撮影例1と撮影例2のそれぞれの特徴量データを比較するとこちらの表のようになります。 また，表中に示す誤差とは， 撮影例1の時の特徴量データを基準としたときの撮影例2の特徴量データの誤差を％表示したものです． こちらの表を見ればわかるように，面積に関する特徴量データの変動は7%と少ないものですが， その他の特徴量の変化量は34%,48%,19%と変動は大きいものとなっています． このように，特徴量データについてまとめますと， 誤差：撮影例1を基準としたときの 　　　撮影例2の変化量 撮影例2

特徴量データ ある対象物体，ある特徴量で 変動が大きくなるものが存在 信頼性の高いデータと 信頼性の低いデータに分別される 信頼性を考慮したマッチングが必要 重み係数wを定義 面積 周囲長 安定 不安定 画像より得ることのできる特徴量データには，ある対象，ある特徴量で変動が大きくなるものが存在します． つまり，特徴量データは信頼性の高いデータと信頼性の低いデータに分別されます． そのため，特徴量データの信頼性を考慮したマッチングが必要になります． そこで，信頼性を表す尺度として重み係数ｗを定義しました． 対象ごとに特徴量データに関して最適な重み係数が存在し，これを決定することにより精度の高い マッチングが行われると考えられます． つまり，最適な重み係数を決定する最適化問題であるといえます。 では、特徴量の使用、不使用を定める重み係数について説明します。 最適な重み係数を決定する 最適化問題

重み係数 例： 候補数1000個 特徴量数30個 重み係数の組み合わせは2の30乗 加えて1000候補に対して決定する 特徴量1 特徴量2 特徴量3 ･･･ 特徴量j Item 1 1 Item 2 ： Item i w(i,1) w(i,2) w(i,3) w(i,j) 例： 候補数1000個　特徴量数30個 重み係数の組み合わせは2の30乗 加えて1000候補に対して決定する 決定しなければならない重み係数はこちらの表に示すようにそれぞれの候補、特徴量ごとに存在し W(I,j)と表すことができます。 例えば，候補が1000個，抽出される特徴量数が30個あった場合， 商品1つにつき重み係数の組み合わせは2の30乗となります． 加えて1000商品に対して一つ一つ決定しなければならないため， 探索空間が膨大な数となり、全数探索的に求めるのは現実的ではありません。そこで本研究では、 最適な重み係数の決定に最適化手法の一つである遺伝的アルゴリズムを用います． 遺伝的アルゴリズム(GA)を用いる

遺伝的アルゴリズム(GA) 生物の進化を模倣した最適化アルゴリズム 母集団に対して，遺伝的操作を繰り返し適用 多点探索により，大域的な探索に優れている 遺伝的アルゴリズムとは、～～ 強力な最適化手法です。 個体 母集団

GAを用いた特徴選択 識別に最適な重み係数の組み合わせを GAで決定する を決定します。

画像認識問題の定式化 重み係数wの最適な組み合わせを決定する wの値を並べてNビットの2進記号列を遺伝子型 適合度により候補が決定 では，GAを用いた画像認識問題の定式化について説明します． まず，決定しなければならないものは，重み係数ｗの最適な組み合わせであります． そこで，ｗの値を並べてNビット，ここでは，特徴量の数になりますが，の2進記号列を遺伝子型としました． 適合度関数はここに示すようなものとなります．最適な重み係数を決定すると同時に，適合度により商品候補が決定します． 式中，Xiは特徴量データベース上のそれぞれの候補であり，Yは入力画像となります． また，Zは入力と比較されるデータベース上の候補であり，sizeは識別に使用する特徴量の数となります。 こちらの適合度関数は、GAで選択された特徴量空間におけるそれぞれの画像間の距離を 比較していることになります。 具体的にGAで行われるマッチングとしては， ：入力と比較される 　データベース上の候補 ：データベース上の候補 ：入力画像 ：使用する特徴量の数

実験 実画像を2種類用意 特徴量データベース，入力画像 対象画像内訳 特徴量データ 幾何学的 特徴量 統計的 特徴量 分類 個数(個) 指輪 10 ピン 9 ネックレス 6 その他 合計 31 幾何学的 特徴量 2値画像 では、本手法の有効性を検討するため、一般的に市販されているアクセサリの実画像を用いた実験を行いました。 実験に際して実画像は2種類用意し、一つはデータベースに格納するためのもの、もう一つは入力となるものです。 入力画像の内訳としてはこちらの表に示すようなものであり、特徴量データに関しては、 2値画像より幾何学的特徴量を抽出し、オリジナル画像より統計的特徴量を抽出しました。 また、特徴量データベースには入力には用いなかった他のアクセサリのデータも入っており データベース上には45種類の候補が存在します。 統計的 特徴量 オリジナル画像

画像例 こちらに、対象としたアクセサリの画像を示します。

特徴量一覧 幾何学的特徴量 統計的特徴量 面積 2次モーメント 絶対最大長 パターン幅 円相当径 外周囲長 全周囲長 包絡周囲長 丸さの度合い 円形度 尖状度 最大弦長 フェレ長 投影長 等分径 切片長 フラクタル次元 こちらに特徴量の一覧を示します。本実験では39種類の特徴量データを用いました。 平均値 分散 標準偏差 歪度 尖度

GAパラメータ 個体数 100 設計変数(特徴量数) 39 染色体長 交叉率 0.6 交叉法 2点交叉 選択法 トーナメント選択 トーナメントサイズ 4 突然変異率 0.025(=1/39) GAに用いたパラメータはこちらに示すようなものです。これは経験的に良いとされている値を用いました。

評価方法 実験結果の評価法 入力画像が候補の何番目に提示されたか？ 適合度 入力画像 第一候補 第一候補 第二候補 18.889119 6.812660 本実験では、入力の候補が何種類か提示されます。 そこで、評価方法として、入力画像と同一の対象物体が写っている画像が候補の何番目に出力された のかを用いることとします。 第二候補

実験結果 87%の確率で一意に識別可能 全ての特徴量を使用した識別と比較して 約20%の性能向上 こちらの円グラフは入力が，提示された候補の何番目に正しく提示されたのかを割合で示したものです． 円グラフは、提示される各候補が正解を含む割合を示したもの 棒グラフGAを用いた場合と用いない場合の識別結果（第一候補が正解を含む割合を示したもの） 87%の確率で一意に識別可能 全ての特徴量を使用した識別と比較して 約20%の性能向上

識別例 こちらに具体的な認識例を示します． 指輪に関しては正しく第一候補に同一商品を示しました． ネックレスに関しては，第二候補に同一商品を示しました．

特徴量の使用度合い 面積 周囲長 識別に有効な特徴量を自動的に決定 比較的どのような 対象においても安定 形が変化する 対象では不安定 指輪 100%(8/8) ピン 100%(9/9) ネックレス 66%(4/6) その他 100%(4/4) 指輪 87%(7/8) ピン 77%(7/9) ネックレス 16%(1/6) その他 100%(4/4) 入力を第一候補と正しく識別したものを対象に、そのときの特徴量の使用度合いについて見てみます。 面積は比較的どのような対象においても安定である特徴量のため、全ての対象物体においてよく用いられている ことがわかります。 一方、周囲長は形が変化する対象では、撮影条件によって特徴量データが大きく変動するため、 形が変化しやすいネックレスでは、あまり用いられていないことがわかります。 識別に有効な特徴量を自動的に決定

まとめ GAを用いた特徴選択による画像認識の提案 アクセサリを用いた実験 87%の確率で一意に識別可能 特徴量を選択しない場合と比較して 20%の性能向上 同一物体が異なる見え方を示す場合 (特徴量が変動する条件下)において有効 人の顔認識等への応用

質疑応答

パターン認識 パターン認識問題 画像認識 音声認識 優れた認識技術の開発 観測されたパターンを，あらかじめ定められた 複数の概念のうちの一つに対応させる処理 画像認識 指紋認証,etc 音声認識 音声ワープロ,etc 優れた認識技術の開発 パターン認識とは、観測されたパターンをあらかじめ定められた複数の概念のうちの一つに対応させる処理である。 その代表的な研究課題として、画像認識や音声認識がある。 これらの技術は指紋認証機能つきの携帯電話や音声ワープロに応用され、我々の生活の身近なものとなりつつある。 そのため優れた認識技術の開発は、より便利な製品の開発に欠かせないものであり、高度な認識技術を開発する ことは重要な研究課題である。 本研究では、種々のパターン認識問題の中でも画像認識を取り上げ、その認識技術の性能向上を目指す。

特徴選択 人間は優れた画像認識機能を有する 特徴選択 特徴を選択的に抽出し，統合する 与えられた特徴量の中から，識別に有用な 特徴量の組み合わせを選択する 識別処理における計算コストの低減 識別能力の向上

マッチングのフローチャート 商品ごとに最適な 重み係数が存在 商品一つ一つに 対してGAを適用 入力画像Yと データベース上の 各候補　 を順に 比較する

マッチング方法 周囲長 面積 平均値 ･･･ 分散 商品B 商品A 周囲長 面積 平均値 ･･･ 分散 マッチング方法としては，入力商品の特徴量データを特徴量データベースに格納されている各商品の特徴量データと比較します． この際，GAによりマッチングに最適な重み係数が適応的に決定されます． この重み係数を用いてマッチングを行います． 具体的には，重み係数が1である特徴量データはマッチングに使用されことになり， 0である特徴量データはマッチングに使用されません． この場合だと，入力データの商品Aとのマッチングでは周囲長と分散が用いられ， 商品Bとのマッチングでは面積と平均値が用いられます． 周囲長 面積 平均値 ･･･ 分散 商品B 商品A 周囲長 面積 平均値 ･･･ 分散

入力画像と前処理 撮影条件 前処理 バックライト上に配置 カメラ位置は固定 商品の置き方は自由 2値化 まず，認識対象となる画像については，こちらに示す条件のもと撮影を行いました． バックライト上に商品を置いて撮影します．これは，商品自体の影などを除き，形がはっきり現れるようにするためです． デジタルカメラと対象商品との距離は固定し，商品の置き方は自由であり，商品をどのような向きにおいてもいいこととしています． そのため，画像中の商品は撮り方を変えるたびに変化することとなります． 次に前処理として，特徴抽出が容易にできるよう2値化を行っています． 特徴量抽出に関しては，オリジナル画像，2値画像両方を用いて行いました．

商品例（指輪）

商品例（ネックレス）

商品例（ピン）

商品例（その他）

認識例 その他 ピン

識別部におけるマッチング手法 テンプレートマッチング 特徴量を用いたマッチング 基準となる画像と入力画像との重ね合わせ 特徴量データの比較によるマッチング

マッチングの概念 誤差が大きすぎるのは変動の激しい特徴量 ＤＢデータ１ １１０１００ ＤＢデータ２ ０１１０１１ 似通ったデータのみを用いてマッチングを行う

人間によるマッチング結果 特徴量データだけによるマッチング 人間・GAともに認識できる それぞれの商品の特徴量 データに違いが存在 pin-01を入力 人間 GA 第一候補 pin-01 第二候補 pin-02 etc-02 pin-02を入力 人間 GA 第一候補 pin-02 第二候補 Necklace-02 Necklace-01 ring-04を入力 人間 GA 第一候補 ring-03 第二候補 ring-01

フラクタル次元 次元の概念 元の図形をn分割し，できた相似な図形をm，次元をDとする 直線： 正方形： 1辺の長さ1の直線，正方形の辺をそれぞれ5等分したとき，直線では5個の線分，正方形では25個の正方形ができる． 次元は元の図形を分割しn個になったとき，できた相似な図形をm，次元をDとすると式のように一般化される． 直線では5個に等分割すると5個の相似な直線，正方形では5個に等分割したとき25個の相似な図形ができる．

フラクタル次元 次元の概念を非整数まで拡張したもの 直線は1次元 正方形は2次元 立方体は3次元 コッホ図形は1.262次元 コッホ図形

円形度，尖状度，丸さの度合い 円形度 尖状度 丸さの度合い 真円で1となり，複雑なほど0に近づく 正方形，真円で1となり，とがっているほど小さくなる 丸さの度合い 真円で1となり，複雑なほど大きくなる

歪度，尖度 歪度 尖度 濃度ヒストグラムの形状が対称な形からどれだけずれているかを表したもの 濃度ヒストグラムの分布がどれだけ平均値の回りに集中しているかを表したもの ：濃度ヒストグラム ：標準偏差 ：平均値

評価関数 未知の入力 item X 特徴量 w1,w2,w3 候補 A,B,C 適合度

評価関数 未知の入力 item X 特徴量 w1,w2,w4 候補 A,B,C 適合度 入力をBとしたとき，他の候補(B,C)と比べて どれだけ離れているか?