電気工学科石川聖二電気工学科加藤清史

九州工業大学研究報告（工学）No．63 1991年9月       15        、

コンシステントラベリングを用いたパターンの階層的認識

（平成3年5月31日 原稿受付）

電気工学科（大学院）村野  ^隆

電気工学科石川聖二 電気工学科加藤清史

Hierarchical Pattern Recognition by Consisteht Labeling

by Takashi MURANO   Seiji ISHIKAWA   Kiyoshi KATO

Abstract

  In the present paper， we propose a technique for recognizing patterns in a hierarchical way by consistent labeling． The procedure of pattern recognition as well as pattern association can be lre−

garded as a labeling problem which is given、 formalization as a consistent labeling problem Although we have already proposed a method of recognizing and associating pattems in a consis−

tent labeling manner， it does not have a very effective matching procedure， since this model．based recognition technique needs matching an input object to each model in the memory． It is also in−

sufficient in the ability of recognizing distorted or noisy images． To solve these problems， an approach is studied employing hierarchical consistent labeling．

       ついて未知の画素に濃度値を割り付けたり，入力画像の 1・はじめに

@       ある領域に，モデルのある部分を対応させるというよう

 コンピュータは，数値計算などの処理において，高速   なラベル付け問題であるとの立場から，人間の視覚情報 性や高い信頼性を持つ。しかし，データがあいまいであ  処理過程においても同様のことが行われているとの想定 るとその効率は極端に悪くなる。これに対し，人間の脳   のもとに，コンシステントラベリング3）の概念を用いて は神経細胞から構成された巨大なシステムで，その特徴   パターン連想4）や物体認識5）を行う手法を提案した。し には自己組織系，並列処理方式，構造的安定，優れた記   かしながらこの手法は，〉人間の情報処理の特徴の1つで 憶方式などがあり，あいまいなデータを扱うことには慣  ある階層性6）を考慮していないため，連想・認識の柔軟 れている。もし，コンピュータが人間の脳のような情報  性や効率の面で問題があった。この点の改善をはかるた 処理能力を持てば，様々な作業の自動化や，人間との自  め，本稿では，コンシステントラベリングを用いたパタ 然なインターフェイスの達成に貢献することが期待され   一ン認識（以後連想も含める）の階層化について検討す

る。コンピュータに人間の脳と同様な情報処理を行わせ   る。

ようとする観点から，知識工学1）やニューラルネットワ ーク2）といった分野の研究が近年活発に行われている。

 人間の情報処理機能のうち，視覚情報処理について考 える。我々は，視覚パターンの連想や認識は，知識に基

      識では同図（b）のように，パターンの局所的特徴の相対位  2．コンシステントラベリングによるパターン

      置をユニット，その局所的特徴をラベルとしたモデルで

   認識方式       表現される・・。

 2．1コンシステントラベリング問題      このように，モデルとなるパターンはユニット拘束集

 コンシステント・ラベリング問題3）とは，ネットワー   合τニ｛（μγ1，μγ2， ◆ ・〃γ苑）｝，およびユニット・ラベル ク拘束解析問題を抽象化した概念であり，対象間の拘束   拘束集合R＝｛（μγ1，1γ1，μ72，172，…，μγ ，1γ ）｝によってメ

集合σ，ユニット％に付けることのできるラベル1の   X＝｛（μエ、山、，μエ、，1⇔…，ぬ。，Lπ）

集合L，互いに拘束しあう〃個のユニットの組を要素      k晦、，晦、，…，晦。）εT｝

とするユニット拘束集合丁（τ⊆ση），及び互いに拘束   のように，ユニット・ラベル拘束集合を用いて表現され しあう〃個のユニット・ラベルのペアの組を要素とする   る。ただしム＝痂1（不明）も含むが，1エ、＝ZΩ＝…ニL．

ユニット・ラベル集合R（1〜⊆（σ×L）η）からなるコン   ＝η〃なる組は除く。Xが与えられると，1〜の要素はX パチビリティモデル（σ，L，τ，1〜）によって与え   によって拘束を受ける。 Xに矛盾する要素をRから除

られる。コンパチビリティモデルの概念を図1に示す。   いた集合を1〜＊，すなわち，

コンシステントラベリング問題とは，Rが与える拘束    R＊＝｛rlrεR， r〜∀鋲X｝

、と矛盾しないような，σの各々のユニットへのラベル   で表す。ここで， 〜 は無矛盾を表す。R＊を生成する の対応付けを求めることである。これは普通，Rに対   アルゴリズムREMOVALは，次のような手続きである。

して縦型探索を行うことにより求められる。        ただし，8＝（μS1，1S、，μ、、，1。、，…，μ、。， S。）のとき，81T・＝

 2．2 パターン認識方式      （κs、，μs2，…，μs ）と定義する。

 コンシステントラベリングによるパターン認識では，   REMOVAL 記憶されている認識対象パターンのモデルを構成するユ    如g仇

ニット・ラベル拘束集合Rがどのようなユニットとラベ    、ωヵRz。R㌧

ルによって表現されているかが重要である。我々がすで    ㌧ノbτα〃rε1〜＊∂o

に実現しているパターン認識に多面体認識と文字認識が       ノbrα〃⑳εX 40        ある。多面体認識では図2（a）のように，多面体上の面を        ぴrIT＝∋T

ユニット，その2次元の見え方をラベルとし5），文字認         功εησノbrαcθ噺仇ゴ（1，、≠1エ、

       αη4 エ，≠ηの       仇εηπ御ouεr∫わo沈R＊

   ユニットu．       ラベル1．

         ＿．．＿。。N  こ竺きパターンxの認識問題は，コンパチビリテ，モ

    ゜1三＿。b。 デル（σ，LT，蜘・対するコンシステントラベ

     2      リング問題に帰着し，その解が，パターン認識の結果を

   ・4（ぜ゜一…｛〕c□  与える・パターン認識の手続きを以下に示す・

         へ

     ○  〜〜一一｛1 ロ  REC°GNITI°N l

       bεgiη

ロ   ロ 仇力砿ραzzεグηX∫

ρεプb耽REMOVALω励Xαη4 R Zo o伽仇R＊；

ρεη危τ〃2εoηsisZεηZψ6ε存η9脚 仇

Tの要素（4−t・pl・） Rの要素（4−t・pl・）         （σ， L，τ， R・）

（1， 2， 3， 4）     （1， a， 2， b， 3， c， 4， d）

θηd

図1 コンパチビリティモデルの概要

コンシステントラベリングを用いたパターンの階層的認識       17

6＼   1   ／5

         ↑          7

 1       2

（［コ，＜つ，口，〈〉）

（口〈〉・口・∠ン）   （1，〈，，，片）

（［コ，∠7，口，∠コ3    4）  （・，ん・，／）

（口・口・〔コ・〔才  （1・〈…へ）

：；：1：日：目： 1：：sl：㍉

       ●       ●        ●       ●

       ●

  多面体認識における       文字認識における

  ユニット・ラベル拘束集合の要素       ユニット・ラベル拘束集合の要素        （a）      （b）

図2 ユニット・ラベル拘束集合の要素

       る。第勿層（卿＝1，2，・…，、M）における特徴パ  3．コンシステントラベリングによるパターン

      ターンの集合をP㈲＝｛ρ1ω，ρ2㈲，…・，ρM幼㈲｝とし，

   認識方式の階層化

       パターンρ ㈲は第初一1層の特徴パターン如（先D（〃

 コンシステントラベリングによるパターン認識はモデ   ＝1，2，・…，M卿、）からなるものとする。また，第m層 ルベースの認識方式であり，記憶されているすべてのモ   において特徴パターンを抽出する画像上の領域をαゴ㈲

デルに対して入力パターンとのマッチングを行う。その  で表す。このとき，パターンρが画像上の領域αに存 ため，処理の効率が悪い。また，1層の認識方式である  在することを（α，ρ）で表せば，ρ（づは，

ことから・パターン識アルゴリズムが備えているべき・   州一叉輌（αゴ此（初），ρゴ、（鋤）

ひずみやノイズ，欠落等を含む不完全なパターンの処理       此一1

に対する強靱さが十分でない。そこでそれらの問題の解   と表現できる。ただし砺㈲はパターンρ，㈲上の領域，

決へのアプローチとして，階層化を行って本認識法を多   またくは論理積である。このことから，パターンρ，㈲

層の認識方式に拡張する。各層の認識方式をそれぞれコ  の認識はρ，㈲を構成するローカルなパターンとその位 ンシステントラベリング問題として記述すれば，処理手   置のペアをすべて求める問題となるが，これは，コンシ 続きの統一的記述が可能になり，アルゴリズムも構造的   ステントラベリング問題として記述できる。これを階層 に明確になる。      化したパターン認識は，次のように定式化される。

 ある画像パターンの認識は，そのローカルな特徴パタ   第初層におけるコンパチビリティモデルを（ぴ鋤，

一ンの認識が階層的に積み重ねられて行われるものとす  L㈲，7 ㈲，R㈲）で表せば，

σ（卿）｛    （卿）24．｝：ρ・（ D・P（  句相対的位置の集合  磁  L（柳＝｛1．㈲｝：集合（P（牛1り

 τ吻）⊆ぴ鋤：第勉層において構造的拘束関係を検討    4．文字認識の階層化     する％組の位置の集合

       64×64画素の2値画像の文字パターンを対象として，

R吻）⊆（σ㈱×L呼：輪層において認識される特 階層的パターン認識の手続きの概要を述べる。

    徴パターンの構造的拘束を与える醐のユニ ここでは，階層を微小線分検出層橋成線分検出層，

    ・ト ラベルペアの集合     局所的特徴検出層，文字誠層（特徴統合層）の4層と

である。ただし，ディジタル画像f（2，ノ）＠＝1，2，…，  する。認識の手順として，．はじめに微小線分検出層にお 1；ブ＝1，2，…，ノ）は，画素（ゴ，力とグレィレベル   いて，入力パターンから角度の異なった微小線分を検出 f＠，∫）のペアの集合とみなすことができるため，第1   し，検出された微小線分を使って入力パターンを表現す 層では，      る。次に構成線分検出層において，微小線分で表現され       たパターンから入力パターンを構成する線分を検出し，

  σω∋ぽD ：画素     入力パターン1、対する構成線分モデルを繊紛とその

  Lω≡P（°）∋f（i・∫）：グレイレベル    結合関係から形成する．続いて局所的特徴検出層にお、、

と定義される。      て，構成線分モデルから入力パターンを構成する局所的  このように，特徴パターンP㈲はユニット拘束関係   特徴を検出し，検出された局所的特徴とその結合関係か τ㈲とユニット・ラベル拘束関係R㈲で表現され，メ   ら特徴モデルを形成して，これを文字認識層の入力とす モリに記銘される。認識のために各層に提示されるパタ   る。最後に，この特徴モデルから文字を認識する（図3 一ンX㈲も，次のように，ユニット・ラベル拘束関係   参照）。

を用いて表現される。       4．1微小線分検出層

       微小線分検出層では，角度の異なった微小線分ρ、ω

X㈲ニ｛（隆・㌦・㈲・〃・・（吻 ・1・・（沈㌧    （。・，22．5・，4，・，67．5・，9。・，、、2．，・，135・，、571，・）

      ・…，μエ。㈱，1エ。㈲）    ∈PωG＝1，2，・…，8）を検出して，入力画像パタ        ーンを32×32のパターンに再構成する。微小線分の検出         1（μ。、（幼）魂、（鋤，…・，妬。㈲）∈τ（沈｝｝      一        は，入力パターン上で2画素×2画素の小領域ごとに行 R㈲とX吻）からREMOVAL処理によって生成し，   う。微小線分検出層は階層的パターン認識モデルにおい

（σ㈲，L㈲，τ㈲，R㈲＊）に対するコンシステントラベ   て最下位層であり，入力パターンが2値画像パターンで リング問題を解く，第勿層におけるすべての領域α．㈲   あるため，3章の定義に従ってユニットを画素μ ω∈

においてこの手段を行うことにより，第吻層の認識が   σ（1）（i＝1，2，3，4），ラベルをグレイレベルL（D＝

終了する。最終層における解が第1層に提示された入力 パターンの認識結果となる。階層的パターン認識アルゴ

リズムRECOGNITION 2は次のようになる。

RECOGNITION 2

b69ゴη

 ノbrη2：＝1Zo M40

  プbγα〃α．（幼）∂o    bε9ゼη

A

 沈αんαη勿ρ砿1りα舵「ηX（初㌧      入力   微小線分構成線分構成特徴文字 認識結果

         ω効rε5ρε 〃ox吻）αη41〜（鋤

εηめ      図3 文字パターン認識における階層

コンシステントラベリングを用いたパターンの階層的認識       19

ニ｛0，1｝とする。図4（a）に，コンパチビリティモデ    4．3局所的特徴検出層

ルによる微小線分検出層の表現を示す。入力文字パター    局所的特徴検出層では，構成線分モデルから局所的特 ンを微小線分で再構成した例を図4（b）に示す。      徴ρ，（3）∈P（3）＠＝1，2，…・）を検出し特徴モデルを  4．2 構成線分検出層       形成する。この層において検出される特徴は，構成線分  構成線分検出層では，微小線分検出層において再構成   の結合点上に存在する。そこで，ユニットを結合点の回 されたパターンから入力パターンを構成する線分ρ輌（2）  りの8近傍画素μ （3）∈σ（3）（i＝1，2，・…，8），ラ

（0°，22．5°，45°，67．5°，90°，112．5°，135°，157．5°）  ベルを構成線分1輌（3）＝ρ輌（2）∈L（3）とする。局所的検出層

∈P（2）（ゴ＝1，2・…，8）を検出し，構成線分モデ   の表現は図6（a）のようになる。特徴モデルは，局所的特 ルを構成線分とその結合関係から形成する。この層に対   徴間の結合関係と結合を行っている構成線分によって形 する入力は，微小線分検出層で再構成された，8種の角   成される （図6（b）参照）。この層で行う処理は，多面体 度を持った微小線分で構成される32×32のパターンであ   認識における画像上での各面の内角の角度検出に相当す

る。その微小線分の追跡を行い，数本の構成線分を検出   る。

する。追跡の際，微小線分を5本つつ追跡しその都度微    4．4 文字認識

小線分とその位置関係のペアに対して認識を行い，統合    文字認識では，局所特徴と構成線分で形成された特徴 するには不適当な微小線分もしくは特徴点が存在するよ   モデルから入力パターンに対する最終的な認識を行う。

うな場所が現れるまで，微小線分を統合し構成線分を検   ユニットを，正規化された文字の与えられる画像上の領 出する。そのため微小線分を格納する5×5のマスクを  域α，∈A≡σω，ラベルを前層で抽出された局所的特徴

用意する。そこでユニットをマスクの構成要素μ‡（2）∈   と構成線分1輌ω＝カ （2）またはρ∫（3）∈L（4）≡P（2）UP（3）と

す。この処理によって入力パターンは，図5（b）のように   ターンモデルの構成要素と特徴モデルの構成要素間に1 角度を持った構成線分の結合関係と位置関係からなる構   対1の対応付けを持つような文字パターンがコンパチビ 成線分モデルで表される。この層における処理は，多面   リティモデル上で探索される。その結果，認識に成功す 体認識における辺検出に相当する。なお現在は曲線部の   ると，図7（b）のような出力が得られる。

表現は行っていない。

2×2の小領域

ぴll＝｛μ1（1），μ2ω，μ3ω，μ4（1）｝

L（D＝｛0，1｝

Tω＝｛（1，2，3，4）｝

R・・一 o（12340011），（｝治1），、ぴの微撒分

   （12340110），  、4⑰微撒分

…   ｝  入力パターン 灘貧鷺

（a）コンパチビリティモデルによる       （b）微小線分検出層における入力パターンの再構成   微小線分検出層の表現

図4 微小線分検出層の表現と微小線分による再構成

1 2 3 4 5 6 7

8

12

16 17 18

20

22 23 24 25

   5×5の小領域      微小線分による     ；  し    1

       輔成パターン 田丁百図1図

：ll：㌫にil：1ご㌃       日出日団

丁（2）＝｛（3，8，13，18，23），       入力パターンに対する構成線分モデル

（4，8，13，18，23），

・    ………・｝     0   1

      ｛Gぷ瀞｝ 局所ζ領域：

      億蒜㌶），  ヲ ・

       面          ………・   ｝

 1     2

       、        へ

，   3    、

      、

    オ

14 1 51

1 2 3 4  5 0 1 1 1 0

1 0  1 0  1

構成線分      構成線分の隣接関係

（a）コンパチビリティモデルによる         （b）構成線分検出層における構造線分による    構成線分検出層の表現       入力パターンの表現

図5 構成線分検出層の表現と構成線分モデル

1

4 6

2

7 3 5

8

       1皿u．一＿    ／一一一｛亙

       1、一．1．．癒㌧二＼こて一』

       素構誓蝶 斑眉

       4 5＼、図・ 6  イ 5−□

σ③一｛・・1ゴー1………｝        ｛コ；二〔     i

L（3）ニ｛♪（2）li＝1・2・ ・8｝ 入力パター。に対する繊線分モデル入力パター。特徴モデル、

τ（3）＝｛（6，8），（6，7），・… ｝

結舗のR叶（6  8ρ3（2）ρ1（2）），（あD 1

局所的領域

      ，…・……  ｝  1

       ：

1 2 3 4  5

0  1 1 1 0      1 1 0  1 0  1       2

1 0  1 0  0      4 0  1 1 0  0      5

1 2 3 4 5 0 4 8 0 0

4  0  3  4／ 0 8  3  0 

0 

0 4  0 0 0

0 0  1  0 0       構成線分の隣接関係       局所的特徴と構成線分        の隣接関係

（a）コンパチビリティモデルによる      （b）局所的特徴検出層における局所的特徴と

  局所的特徴の表現       構成線分による入力パターンの表現

コンシステントラベリングを用いたパターンの階層的認識．         21

       皿1ニー一   ！一一一囚  皿一〜    ／一一囚

       日；2パ 1・」，』   1聴．』

      田4 一田  ［刀    一［罰

      1  囚冒、−2遼』 ＼、一▲趨』

       図・・6 、 5−□   A、 A，一囚        ・・    因一一     ：  ［団一！

α3       8       ●

  イメージ画面      入力パターンの特徴モデル    文字パターンAの特徴モデル

ぴ4 ＝｛α1｝       1

Lω＝｛ρ・ 2 ，がlliニ1，2，…㍉8；∫ニ1・2，…・｝  2

  ＝P（2 UP③       3

Tω＝｛（α山・・2，・ ・）1α・・∈A；元＝1，2，3｝     4

o㌫㌶；）・・…・文字A   

1 2 3 4  5

0  4  8／ 0  0       1 4  0  3， 41 0       2 8／ 3／ 0  0  r      3

0 4  0 0 0      4 0 0  1  0 0      5

AIA2A3A4A5

1 0 0 0 0 0  1 0 0 0 0 0 1 0 0 0 0 0  1 0

0  0 0  0  1

ド…・文字・｝      の麟関係    繊への文寸応付け

（a）コンパチビリティモデルによる      （b）局所的特徴検出層における局所的特徴と   文字認識層の表現       構成線分による入力パターンの表現

図7 特徴モデルによる文字パターンの表現

       参 考 文 献  5．まとめ

       1）大須賀節雄：知識情報処理，オーム社（1986）．

 コンシステントラベリングを利用したパターンの階層   2）合原一幸：ニューラルコンピュータ，東京電気大学 的認識の手法を提案した。視覚パターンの認識問題をラ     出版局（1988）．

ベル付け問題と見れば，認識はコンシステントラベリン   3）Haralick， R． M．， Shapiro， L． G．： The consistent

コンシステントラベリングによるパターン認識法の階層     Aη己Mα訪．∫ηzθ1Z， PAMI−1，2，173−184（1979）．

化によって認識手法の構造に一層の明確性を与えたが，   4）石川聖二，郷原幸一，加藤清史： ネックワーク拘 さらにラベル付け（認識）処理の効率化や，歪やノイズ     束解析を用いた多面体認識 ，電子情報通信学会技 を含むパターンの処理能力の一層の向上が可能である。     術研究報告，PRU 90−77，61−68（1990）．

 今後の課題として，処理問題の高速化のために，各層   5）黒川 清，石川聖二，加藤清史： コンシステント における処理の並列化の実現が必要である。また層間の     ラベリングを用いたパターン連想 ，情報処理学会 結合の態様についてもさらに検討の余地がある。       論文誌，31，3，511−515（1990）．

 また，パターンの連想がコンシステントラベリング問   6）Lindsay， P． H．， Norman， D． A．：Human Information

した階層的パターン認識法は連想の機能を含んでいる。   7）村野 隆： コンシステント・ラベリングの文字認 従ってパターン連想問題についても，本法はより効果的     識への応用 ，平成元年度九州工業大学工学部情報

なアルゴリズムを提供するものと思われる。         工学科卒業論文（1990）．