応募結果

---

２２件の応募があり，２８アルゴリズム審査を行った．

• アルゴリズム A3 応募クラス３ 色情報に基づく領域分割後、２つの領域の配置関係による探索の絞り込み
• アルゴリズム B3 応募クラス３ 色情報に基づく領域分割後、２つの領域の配置関係による探索の絞り込み
• アルゴリズム C２ 応募クラス２ 背景部を削除したテンプレートの粗密マッチング。拡大縮小マッチング
• アルゴリズム D1 応募クラス１ 横１行分の画素列を新たなテンプレートとしたマッチング処理の簡略化
• アルゴリズム E3 応募クラス3 色領域を特徴とした一般化Hough変換を利用
• アルゴリズム F2 応募クラス2 ピラミッド（３解像度）画像を用いた疎密探索、クラス１とクラス２の自動判別
• アルゴリズム G1 応募クラス１ ガボール関数（ウェイブレット）を用いた２段階粗密探索
• アルゴリズム H1 応募クラス１ カラーヒストグラムと RGB 差分絶対値和を基準にした粗密探索
• アルゴリズム I2 応募クラス2 テンプレートの特徴（色頻度、色の相対的配置、エッジ頻度）を予め学習
• アルゴリズム J2 応募クラス2 特徴色の水平、垂直射影と、平滑化した射影パターンの重畳により位置を特定
• アルゴリズム K1 応募クラス１ ２段階の粗密探索．第１段階のではＲＧＢの各値が最も大きい９点だけを使用
• アルゴリズム L3 応募クラス３ テンプレートマッチング：粗密探索のオーソドックスな手法、途中打ち切りあり。
• アルゴリズム M1 応募クラス１ テンプレートマッチングの簡略化による効率化
• アルゴリズムNシリーズ
  • アルゴリズム N1-1応募クラス1 テンプレート中の最多頻度の色を用いた粗密探索
  • アルゴリズム N1-2 応募クラス１ テンプレート中の最多頻度の色を用いた粗密探索＋色ヒストグラムの利用
  • アルゴリズム N1-3 応募クラス１テンプレート中の最多頻度の色を持つ領域の重心計算による高速サーチ
  • アルゴリズム N1-４ 最多頻度の色を持つ領域の重心計算による探索＋誤差絶対値和による密探索
  • アルゴリズム N2 応募クラス2 テンプレート中の最多頻度の色を用いた粗密探索＋固有空間法によるスケール推定
  • アルゴリズム N3-1 応募クラス３ テンプレート中の最多頻度の色を用いた粗密探索＋固有空間法
  • アルゴリズム N3-2 応募クラス３ テンプレート中の最多頻度の色を用いた粗密探索＋領域モーメント計算
• アルゴリズム O3 応募クラス３ 均等色空間での領域分割。代表領域と従属領域の対応関係による探索
• アルゴリズム P3 応募クラス３ テンプレートを円で表現される部分領域で表現。　部分領域の対応から探索（ハフ変換）
• アルゴリズム Q1 応募クラス１ メッシュに切った小領域の高次自己相関特徴の利用
• アルゴリズム R2 応募クラス２ テンプレートマッチングによる粗密探索
• アルゴリズム S3 応募クラス３ テンプレートマッチングによる粗密探索
• アルゴリズム T1 応募クラス１ テンプレートマッチングの簡略化による効率化
• アルゴリズム U2 応募クラス２ 色ヒストグラムによる粗密探索。　上限値で候補を絞り高速化。
• アルゴリズム V3 応募クラス３ 色による領域分割。各領域のニ項関係を探索

評価手順と結果

---

１．評価方法

評価環境

• OS　：　Linux　（kernel 2.0.34）
• CPU ：　Pentium　2　（350MHz）
• メモリ　：　　64MB

評価手順

評価の方法として異なる背景二つを用い、１１のテンプレートと３ノイズレベル
（雑音なし、ガウス雑音・非線形雑音を２段階で加える）について計６６回のテンプレート探索の結果を評価する。
　移動±５画素以内、回転±５°以内、スケール±１０％以内を正解として計数する。　
また正解のものについては、２乗誤差平均を求める。

1. コンパイルオプションをサンプルプログラムと同様に編集（-O２を削除、-gを削除など）し、コンパイルする。
2. 背景２種類、キャラクタパターン２種類、ノイズレベル３種類で評価。（計算時間評価には、gprofを用いる。）

２．評価画像

• クラス　1

  　　　　 　　　　　　　　　　　

  　　評価背景１（キャラクタパターン１）　　　　　　　　　評価背景１（キャラクタパターン２）
  ノイズレベル0　class1_b1_n0_1.ppm　 　　　　　　　　　ノイズレベル0　class1_b1_n0_2.ppm　　　　　　　　　　　　　　　　　　

  ノイズレベル50　class1_b1_n50_1.ppm　　　　　　　　　　ノイズレベル50　class1_b1_n50_2.ppm

  ノイズレベル100　class1_b1_n100_1.ppm　　　　　　　　　ノイズレベル100　class1_b1_n100_2.ppm

  　　　
  　　　　　
  　　　 　　　　　　　　　　　　　　　　　

  　評価背景２（キャラクタパターン１）　　　　　　　　　　評価背景２（キャラクタパターン２）
  ノイズレベル0　class1_b2_n0_1.ppm　　　　　　　　　　ノイズレベル0　class1_b2_n0_2.ppm　　　　　　　　　　　　　　　　　　

  ノイズレベル50　class1_b2_n50_1.ppm　　　　　　　　　ノイズレベル50　class1_b2_n50_2.ppm

  ノイズレベル100　class1_b2_n100_1.ppm　　　　　　　　ノイズレベル100　class1_b2_n100_2.ppm

  クラス１　正解

  キャラクターパターン１	キャラクターパターン２
  usagi.ppm x = 50 , y = 170　 inu.ppm　 x = 140 , y = 175　　　　　　 reoinu.ppm x = 300 , y = 65　　　　　　 tamago.ppm x = 260 , y = 175　　 yuurei.ppm x = 100 , y = 60	pengin.ppm x = 50 , y = 170　　　　　 neko.ppm x = 145 , y = 175　　　　　 saru.ppm x = 300 , y = 65　　　　 saboten.ppm x = 260 , y = 175　　 usamimi.ppm x = 70 , y = 60　　 usamimi2.ppm x = 200 , y = 80

• クラス　2

　　評価背景１（キャラクタパターン１）　　　　　　　　　　評価背景１（キャラクタパターン２）
ノイズレベル０　class2_b1_n0_1.ppm　　　　　　　　　　ノイズレベル０　　class2_b1_n0_2.ppm　　　　　　　　　　　　　　　　　

ノイズレベル１　class2_b1_n50_1.ppm　　　　　　　　　ノイズレベル１ 　class2_b1_n50_2.ppm

ノイズレベル２　class2_b1_n100_1.ppm　　　　　　　　ノイズレベル２　 class2_b2_n100_2.ppm

　　　
　　　　 　　　　　　　　　　　　　　　

　 　　評価背景２（キャラクタパターン１）　　　　　　　　　評価背景２（キャラクタパターン２）
ノイズレベル０　class2_b2_n0_1.ppm　　　　　　　　　　ノイズレベル０　　class2_b2_n0_2.ppm　　　　　　　　　　　　　　　　　

ノイズレベル１　class2_b1_n50_1.ppm　　　　　　　　　ノイズレベル１　　class2_b2_n50_2.ppm

ノイズレベル２　class2_b2_n100_1.ppm　　　　　　　　ノイズレベル２　　class2_b2_n100_2.ppm

クラス２　正解

キャラクターパターン１	キャラクターパターン２
reoinu.ppm x = 50 , y = 180 , scale = 0.9　 inu.ppm x = 80 , y = 60 , scale = 1.1 usagi.ppm x = 150 , y = 170 , scale = 0.8 usamimi.ppm x = 260 , y = 150 , y = 1.3 usamimi2.ppm x = 200 , y = 50 , scale = 0.7	tamago.ppm x = 55 , y = 170 , scale = 0.9 pengin.ppm x = 80 , y = 50 , scale = 1.1 saboten.ppm x = 140 , y = 200 , scale = 0.8 neko.ppm x = 275 , y = 160 , scale = 1.3 saru.ppm x = 285 , y = 50 , scale = 0.7 yuurei.ppm x = 175 , y = 85 , scale = 1.0

• クラス　３

　　評価背景１（キャラクタパターン１）　　　　　　　　評価背景１（キャラクタパターン２）
ノイズレベル０　class3_b1_n0_1.ppm　　　　　　　　　　ノイズレベル０　　class3_b1_n0_2.ppm　　　　　　　　　　　　　　　　　

ノイズレベル１　class3_b1_n50_1.ppm　　　　　　　　　ノイズレベル１ 　class3_b1_n50_2.ppm

ノイズレベル２　class3_b1_n100_1.ppm　　　　　　　　ノイズレベル２　 class3_b1_n100_2.ppm

　　　
　　　　　　　　　　　　　　　　　　

　 　　評価背景２（キャラクタパターン１）　　　　　　評価背景２（キャラクタパターン２）
ノイズレベル０　class3_b2_n0_1.ppm　　　　　　　　　ノイズレベル０　　class3_b2_n0_2.ppm　　　　　　　　　　　　　　　　　

ノイズレベル１　class3_b2_n50_1.ppm　　　　　　　　ノイズレベル１　　class3_b2_n50_2.ppm

ノイズレベル２　　class3_b2_n100_1.ppm　　　　　　　ノイズレベル２　　class3_b2_n100_2.ppm

クラス３　正解

キャラクターパターン１	キャラクターパターン２
usagi.ppm x = 65 , y = 121, scale = 0.8 , rotation = 11 neko.ppm x = 246, y = 143, scale = 1.1, rotation = 17 reoinu.ppm x = 175, y = 145, scale = 1.4, rotation = -12 tamago.ppm x = 200, y = 67, scale = 0.6, rotation = -25 usamimi2.ppm x = 70, y = 65, scale = 1.2, rotation = 16	pengin.ppm x = 292, y = 153, scale = 0.9, rotation = -18 saru.ppm x = 111, y = 91,scale = 1.6, rotation = -25 inu.ppm x = 65 , y = 151, scale = 0.8, rotation = 11 usamimi.ppm x = 250, y = 92 ,scale = 1.0, rotation = -6 yuurei.ppm x = 111,y = 170, scale = 1.3, rotation = -5 saboten.ppm x = 171, y = 162, scale = 0.8, rotation = 14

３．実験結果（Excelファイル）

４．入賞アルゴリズム

速度に関して５段階評価，アルゴリズムの新規性・有用性（汎用性，ロバスト性）１０段階で評価し
これを正解率（正答数/66）でを乗じたスコアで評価した． まずクラス３で上位３アルゴリズムを選択し，
入賞とした．そして，入賞アルゴリズムを除外して，クラス２の上位アルゴリズム３を選び，
最後にクラス１から上位２アルゴリズムを選択した．Best Score Awardは 各クラスの入賞の次点であったが，
クラス２で全問正解，クラス１でも正解５６とトップの正解率を評価し，特別に賞を設けた．

• Class 3
  • アルゴリズム A3 応募クラス３ 色情報に基づく領域分割後、２つの領域の配置関係による探索の絞り込み
  • アルゴリズム B3 応募クラス３ 色情報に基づく領域分割後、２つの領域の配置関係による探索の絞り込み
  • アルゴリズム P3 応募クラス３ テンプレートを円で表現される部分領域で表現。　部分領域の対応から探索（ハフ変換）
• Class 2
  • アルゴリズム F2 応募クラス2 ピラミッド（３解像度）画像を用いた疎密探索、クラス１とクラス２の自動判別
  • アルゴリズム U2 応募クラス２ 色ヒストグラムによる粗密探索。　上限値で候補を絞り高速化。
  • アルゴリズム V3 応募クラス３ 色による領域分割。各領域のニ項関係を探索
• Class 1
  • アルゴリズム L3 応募クラス３ テンプレートマッチング：粗密探索のオーソドックスな手法、途中打ち切りあり。
  • アルゴリズム H1 応募クラス１ カラーヒストグラムと RGB 差分絶対値和を基準にした粗密探索
• 審査員特別賞 "Best Score Award"
  • アルゴリズム S3 応募クラス３ テンプレートマッチングによる粗密探索

5.講評

クラス１（平行移動の探索）では， 間引きや代表点を用いたテンプレートマッチングの簡略化が功を奏し，
アルゴリズムK1, M1, D1は好成績をあげました．しかし，アルゴリズムの新規性，汎用性の評価が低く入選と
することができませんでした． クラス１，２では全体的に，オーソドックスなテンプレートの階層的な探索や
色ヒストグラムを用いた手法が好成績を上げました． この中で，アルゴリズム改良に進歩性のあるものを入賞として
選んでいます．全般的に，これまで歴史のある標準的な手法が上位を占める中で，クラス３では，入賞者全員が
色情報に基づく領域分割と部分領域の配置関係による探索の絞り込み（パラメータ推定）という共通した手法で
応募されていました． いずれも独創的であり，標準的な手法よりも優れた性能を示したことは特筆すべき事です．

冒頭に応募アルゴリズムを照会したように，色による領域分割と部分領域間の対応から探索（ハフ変換），
多重解像度を利用したテンプレートのCoarse-To-fine探索，ガボールウェーブレットによる階層表現，
色ヒストグラムインターセクション，射影特徴の重畳による位置推定，固有空間での照合，領域のモーメント演算，
小領域の高次自己相関特徴の利用 など 非常に盛りだくさんで審査委員一同 応募者の熱意，創意工夫に感心しました．
この中で，不幸にして選に漏れた応募者は，高度な内容のアルゴリズムを提案されているにもかかわらず，
評価実験で 性能が認められなかった ことをご理解ください．
コンテスト募集のこれまでに寄せられた質問コーナーに  「モデルの画像（テンプレート）には
 このホームページデータ置き場にある11のキャラクタのみを用います．ただし，背景については データ置き場にある 背景
以外の画像でも評価します．したがって，『テンプレートにしかない物体の色を使って場所を特定する戦略』
が必ず成功する保証はありません．」とあります．
また「探索結果の正確さ，雑音への頑健さ，異なる背景への適応力」を評価する
とも述べています． 是非 出題者の意図を汲み取っていただき， 多くのテンプレート，雑音状態で 行い，
 頑健な手法へと絞り込んでいただきたたかったと思います． 

最後に，このアルゴリズムコンテストに応募してくれた２２人の皆さんに感謝します． 夏の時間を
プログラミングに費やした努力はいつか報われるでしょう． このコンテストが皆さんの， パターンを
探索することはどういことか， 頑健なアルゴリズムとは何か， 汎用的なアルゴリズムとはどうあるべきか，
良いアルゴリズムとはどういことなのか， を考える一助になってくれることを，コンテスト実行委員一同
希望しております．

１９９８年電子情報通信学会ソサイエティ大会

アルゴリズムコンテスト発表会

---

ソサイエティ大会については，http://www.ieice.or.jp/jpn/societytaikai.htmlをご照会ください．

日時：１９９８年９月３０日　13：00 〜 17:05
会　場：山梨大学〔甲府市武田４−３−１１〕
　Ｎ号館N-114講義室　（西側のキャンパス）
地図： http://www.yamanashi.ac.jp/
交通：　ＪＲ中央本線、甲府駅下車。バス：甲府駅北口バス停から武田神社行き、または積翠寺行きに乗車、山梨大学前下車(約10分)。
徒歩：甲府駅北口から武田通りを武田神社方向へ徒歩 20分
式次第
司 会：栄藤 稔（松下電器）．
コンテスト実行委員長挨拶 ：末永康仁（名大）
入賞者の発表講演 25分×8件　（入賞者へは　旅費を支給）
特別講演「形状整合技術と産業応用（仮題）」 講 師：鷲見和彦（三菱電機）．
入賞者表彰 ：原 信太郎（原総合知的通信システム基金 理事長）
閉会の挨拶：大田友一（筑波大）．