WISS2007

ちらしアンテナ: 画像探索を用いた安売り情報お知らせシステム
CHIRASHI ANTENNA: Bargain Sale Information Antenna Using Visual Search

高地 利幸

林 貴宏

尾内 理紀夫∗

Summary. チラシ画像を Web に掲載している店舗の Web ページと，欲しい商品の画像を登録しておくと，登録した商品の載っているチラシ画像が更新された際に，通知するシステムを開発した．本システム
では，画像探索の技術を利用して，登録した店舗の Web ページから自動で収集したチラシ画像に，ユーザによって登録された商品が載っているかどうかを判定する．探索の結果を 5 段階でスコアリングする手法を提案し，スコアに基づいて結果を表示するインタフェースを実装した．評価実験の結果から，スコアが 2以上の場合に再現率 82.5%，精度 97.1%，スコアが 3 以上の場合には，再現率 67.5%，精度が 100%になることを確認し，提案手法の有効性を示した．

1

はじめに

近年インターネットの普及に伴い，スーパーなどの多くの店舗が Web ページを持ち，様々な情報を消費者に提供している．その中の 1 つに，安売り・特売情報としてのチラシ画像がある．消費者は，自分の行く店舗の Web ページにアクセスしてチラシ情報の更新を確認し，更新されていれば，そのチラシ画像の中から欲しい商品があるかどうかを探し出す．
チラシ情報は，短期間に有効な情報であり，掲載のタイミングは店舗によって定期であったり，不定期であったりする．したがって，複数の店舗の Webページに頻繁にアクセスし，チラシ情報の更新を見逃さないようにチェックすることは消費者にとって大きな負担となる．また，更新されていた際に，その中から自分の欲しい商品を探し出すことも，チラシ画像の枚数が多ければ負担となる．
そこで本研究では，「不定期に出るチラシを見逃したくない」，「自分の欲しい商品が載っているチラシのみ知りたい」といった消費者の要求に応えるためのシステムとして「ちらしアンテナ」を開発した．
ちらしアンテナは，ユーザが店舗の Web ページと欲しい商品画像を登録しておくと，自動でその店舗の Web ページからチラシ画像を収集し，欲しい商品の載っているチラシ画像があった際に，ユーザに通知するシステムである．これにより，消費者自身が複数の店舗の Web ページにアクセスし，チラシ画像を確認するという手間を省くことができる．本システムが対象とするチラシ情報は画像であり，テキスト情報は使用しない．これは，画像のみでチラシ情報を更新する店舗が多数存在するためである．
本システムでは，あるチラシ画像にユーザの欲しい商品が載っているかどうかを判定する商品検出に，∗

Copyright is held by the author(s).
Toshiyuki Takachi, Takahiro Hayashi and Rikio Onai,
電気通信大学図 1. システム構成図

画像探索の技術を利用している．
以下，2 章で本システムの概要について述べ，3章でインタフェース部，4 章で商品検出部について説明する．5 章で評価実験について述べ，本システムの有効性を議論する．6 章で関連研究について述
べ，7 章で本論文をまとめる．

2

システム概要本システムの構成を図 1 に示す．本システムは，
大きく分けてフロントエンドであるインタフェース部 (3 章) とバックエンドであるクローラ部，商品検出部 (4 章) の 3 つのモジュールから構成される．
インタフェース部では，システムへの入力としてチラシをチェックしたい店舗と欲しい商品の画像をユーザに登録してもらう．また，出力として商品検出の結果である，欲しい商品が載っているとシステ
ムが判定したチラシ画像とそのスコアを表示する．
クローラ部では，インタフェース部で登録された店舗の Web ページに定期的にアクセスし，チラシ画像の更新をチェックして，更新されていれば収集する．

WISS 2007

図 2. アンテナリストの管理画面
図 3. 領域指定画面

商品検出部では，クローラ部で収集されたチラシ画像からインタフェース部で登録された商品の検出を行ない，さらにその検出結果をスコアリングしてデータベースに保存する．

3
3.1

インタフェース部
チェックする店舗の登録

ユーザはまず，チェックしたいチラシを掲載している店舗を登録する．登録は，予めシステムに登録されている店舗をプルダウンメニューから選択する
インタフェースと，システムに登録されていない店
舗の Web ページの URL を入力して登録するイン
タフェースの 2 つが用意されている．
登録済みの店舗はアンテナリストとして管理され，図 2 に示すインタフェースにより登録内容の確認や，登録の削除を行なうことができる．

3.2

欲しい商品画像の登録

次に，欲しい商品の画像を登録する．商品画像の登録は 3 通りの方法が選択できる．ローカルにある画像をアップロードして登録する方法，Web 上にある画像の URL を入力し，さらに画像内の商品部分の領域を指定して登録する方法，本システムに保存されているデータベースから過去のチラシ画像を選び，そのチラシ画像から商品部分の領域を指定して登録する方法の 3 通りである．
商品画像の領域を指定する理由は，商品検出において邪魔になる背景などを除去するためである．
領域指定のインタフェースは図 3 のようになっている．このインタフェースでは，画像上でドラッグすると線を引くことができ，線で囲まれた領域は塗りつぶされる．塗りつぶされている領域を指定領域として登録することができる．ただし，商品の輪郭をマウスで正確になぞる作業はユーザにとって負担となりうる．そのため Lazy Snapping[1] を利用したインタフェースも選択可能としている．このインタフェースでは，ユーザは商品領域内と商品領域外にそれぞれ線分を引くだけで，商品領域が自動的に抽出される．

3.3

結果の確認

商品検出によって，ユーザが登録した商品画像とマッチする部分のあったチラシ画像のサムネイル画像は図 4 に示すインタフェースで確認できる．サム
ネイル画像は，価格を表示させるため，マッチした部分の周辺を切り出して作成している．さらに，そのチラシの店舗名と実際のチラシへのリンク，チラシを収集した日付とスコア (4.2.4 節) を表示する．

4

商品検出部

4.1

商品検出での精度低下の要因と対策

チラシ画像から商品を検出する際に，検出精度を落とす要因が 2 つあることが判明している．その要因と対策について説明する．

4.1.1

商品画像内における不要領域の混入

ユーザが登録する商品画像内に背景などの不要な領域が混入していることがある．背景の色などはチラシごとに変わる可能性があるので，不要な領域の混入した画像を用いて商品検出を行なうと，検出精度を下げる要因になる．
この要因に対しては，商品領域を指定することで不要領域を除去するという対策を取る．この領域指定のために実装したインタフェースは，3.2 節で説明したものである．ただし，領域指定された複雑な図形のままで商品検出を行なうと処理時間がかかるため，ユーザによる領域指定の後，システムがさらCHIRASHI ANTENNA: Bargain Sale Information Antenna Using Visual Search

図 6. 内接四角形の分割

4.2

商品検出の処理手順

商品検出は，前処理 (4.2.1 節)，画像探索 (4.2.2節)，類似判定 (4.2.3 節)，スコアリング (4.2.4 節)の 4 つの処理で構成されている．
図 4. 結果表示画面

4.2.1

前節で述べた 2 つの検出精度低下の要因に対処するために，商品検出の前処理として，商品画像のユーザによる指定領域内から内接四角形を切り出し，5 分割する．以降この分割した商品画像のことを，単に部分画像と呼ぶ．また，部分画像をそれぞれ識別するために，左上を R0 ，右上を R1 ，左下を R2 ，右下を R3 ，中央を R4 と表記する．

4.2.2

図 5. 指定領域内からの内接四角形の切り出しに図 5 のように指定領域内で内接四角形を切り出し，切り出し後の画像で商品検出を行なう．

4.1.2

チラシ画像内での商品領域の遮へい

チラシ画像に載っている対象商品の一部が，値段表示などによって遮へいされていることがある．チ
ラシ画像内の対象商品の一部が遮へいされていると，検出精度を下げる要因となる．
この要因に対しては，商品画像をいくつかの部分画像に分割し，部分画像ごとに検出を行なうという対策を取る．これにより，遮へいされている部分に対応する部分画像では検出ミスをしても，他の遮へいされていない部分の部分画像では正しい結果を得ることができる．本システムで現在用いている画像
分割は，図 6 に示すように，左上，右上，左下，右下，中央の 5 等分割という単純なものである．

商品画像の部分画像への分割 (前処理)

画像探索

部分画像 R0 〜R4 に対し，チラシ画像内を探索する前に，各部分画像の色の分散値を求める．このとき分散値が小さい部分画像は以後の探索処理を行なわない．この色の分散値によるフィルタリングの目的と効果については 4.3.4 節で説明する．
部分画像を，チラシ画像内で拡大・縮小させ，位置をずらしながら，最も類似するチラシ画像内の位置を検出する．本システムでは画像探索を 2 段階で行なっており，1 段階目にアクティブ探索法 [2](4.3.1節)，2 段階目にテンプレートマッチング法 [3](4.3.2節) を用いている．アクティブ探索法は，処理は高速だが正確さがやや低く，一方，テンプレートマッチング法は，処理は遅いが正確な位置を得ることができるという特徴がある．そこで，アクティブ探索法で大体の位置を検出し，その周辺領域でテンプレートマッチング法を用いることで，効率よく正確な結果を得ることができる．また，チラシ画像は店舗によって，画像サイズが 1 辺 2000(px) 以上の大きな画像も珍しくなく，探索は画像サイズに比例して処理時間が増大するので，この 2 段階の手順を踏むことは，処理時間の観点からも必要なことである．

4.2.3

類似判定

探索で検出されたチラシ画像上の部分領域 (以降，検出領域) が，検出に使われた部分画像と本当に類WISS 2007

いる．

4.3 システムで使用している要素技術
4.3.1 アクティブ探索法

図 7. 類似と判定された部分領域似しているかどうかを DCT 照合法 (4.3.3 節) により最終的に判定する．ただし，その判定を行なう前に検出領域に対し，色の分散値によるフィルタリン
グ (4.3.4 節) と検出領域のサイズによるフィルタリ
ング (4.3.5 節) を行なう．判定の結果，類似と判定されれば商品が検出できたとし，類似していないと判定されれば商品は検出できなかったとする．また，検出できた際には，探索での検出領域がそのまま商品検出における検出領域となる．
以上の画像探索 (4.2.2 節) と類似判定は，部分画像 R0 〜R4 の順で行なわれるが，最初に類似と判定された部分画像で処理を終了し，残りの部分画像での探索は行なわない．

4.2.4 スコアリング
図 6 の商品画像に対し，あるチラシ画像で商品検出した結果，図 6 に示した部分画像 R0 で商品が検出され，その検出位置は図 7 で示す実線の四角の位置であったとする．ここで，他の部分画像 R1 〜R4に対応するチラシ画像上の位置は一意に決まる．その R1 〜R4 に対応するチラシ画像上の部分領域と，実際の R1 〜R4 (図 6 右) とで，類似判定 (後述) を行なう．その結果，類似していると判定された R1 ，R2 ，R4 に対応する部分領域を図 7 において破線の四角で示している．図 7 で，R3 に対応する右下の部分は，値段表示による遮へいがあるため類似と判定されなかった．スコアは，類似と判定された部分領域の数とし，図 7 に示した例では，スコアは 4 である．また，現在の商品画像の分割数は 5 より，スコアの最大は 5 である．
部分画像と対応する部分領域との類似判定には，
DCT 照合法 (4.3.3 節) と，アクティブ探索法 (4.3.1節) の中で用いている色ヒストグラムでの照合，テンプレートマッチング法 (4.3.2 節) で用いている色の距離での照合を用いており，すべての照合で類似していると判定された場合のみ類似と判定する．
結果表示インタフェース (3.3 節) では，商品検出の結果をここで求めたスコアでソートして表示してアクティブ探索法とは，色ヒストグラム間類似度を用いてテンプレートを大きくスキップさせながら高速にマッチングを行ない，参照画像 (本システムにおける部分画像) と類似度が最大となる入力画像(本システムにおけるチラシ画像) 内の位置を検出する手法である．
本システムでは，同じ商品であってもチラシ画像ごとの色の輝度や，多少の色の変化に対応するために，色ヒストグラムの分割は粗くしている．具体的には，RGB 色空間の RGB 各軸を 3 分割することで，27(=33 ) 分割した色空間をヒストグラム化して，類似度計算を行なっている．また，アクティブ探索法による探索の結果である類似度が最大の位置でも，その値が閾値を越えなかった場合は，チラシ画像内に部分画像と類似する部分はないと判定して終了し，その後の処理は行なわない．

4.3.2

テンプレートマッチング法

テンプレートマッチング法とは，参照画像と入力画像上から切り出した部分領域との類似性を距離計算により算出し，距離が最小となる部分領域の位置を最も参照画像に類似した位置として検出する手法である．距離計算は，対応する画素間の画素値を用いて計算し，距離は差の絶対値の和 (Sum of AbsoluteDifference: SAD) や，差の 2 乗 (Sum of SquaredDifference: SSD) など様々な手法で求められるが，本システムでは SSD を用いている．
テンプレートマッチング法をそのまま使用すると計算時間が膨大になるので，適応的ウィンドウスキップ法 (Adaptive Window-Skipping Method:AWS) と残差逐次検定法 (Sequential Similarity Detection Algorithm: SSDA)[4] を組み合わせた高速テンプレートマッチング法 [5] を本システムでは利用している．さらに，アクティブ探索法によって予め入力画像の探索領域を狭めることでも時間の短縮を図っている．
また，アクティブ探索法同様，探索の結果である距離が最小の位置であっても，その値が閾値を超えなかった場合には，チラシ画像内に部分画像と類似する部分はないと判定して終了し，その後の処理は行なわない．

4.3.3 DCT 照合法
DCT 照合法はまず，照合する 2 つの画像をそれぞれ 2 次元離散コサイン変換 (DCT) し，DCT 係数ベクトルを求める．そして正規化した DCT 係数ベクトルを比較して距離を求め，その距離が閾値より小さければ 2 つの画像は類似していると判定し，CHIRASHI ANTENNA: Bargain Sale Information Antenna Using Visual Search

大きければ類似していないと判定する．なお，DCT係数はすべて使用するのではなく，低周波成分のみを使用している．
本システムにおいて，部分画像と探索で得た検出領域が類似しているかどうかの最終的な判定としてDCT 照合法を利用しているのは，画像探索は主に色情報を用いて類似度最大の部分領域を検出しており，形状情報が考慮されていないからである．そこで，形状情報である DCT 係数ベクトルを用いた照合を行なうことによって，より正しい類似判定が期待できる．

4.3.4

色の分散値によるフィルタリング

画像内の色の分散値が小さい画像とは，ほぼ単色で平坦な画像であると言える．そのような画像を探索や類似判定に用いると，チラシ画像の背景や値段表示などの単色で平坦な部分領域において類似度が高くなりやすく，誤検出率が高くなることが判明している．そのため，画像探索前の部分画像 R0 〜R4に対してと，類似判定を行なう前の，探索で得た検出領域に対して色の分散値を求め，その値が閾値より小さければ，それ以降の処理を行なわないというフィルタリングを行なっている．

4.3.5

実験

商品画像とチラシ画像で商品検出実験を行ない，対象商品の載っているチラシ画像をどの程度正しく検出できるか調査し，本手法の有効性を確認した．

5.1

実験データと評価方法

商品画像，チラシ画像共に，1 つのスーパー (西友 ) のデータを用いて実験を行なった．商品画像には，パッケージ商品を使用した．使用した商品画像の一部を図 8 に示す．
データ数は，商品画像 29 枚と，チラシ画像 21 枚で行なった．画像サイズは，実際のチラシ画像をそのまま使用したため統一されていない．領域指定さ
1

1れた商品画像から切り出した内接四角形の大きさは，商品画像 29 枚のうち最大 149 × 149(px)，最小 38× 39(px)，平均 95 × 95(px) であり，チラシ画像の大きさは，22 枚のうち最大 631 × 2743(px)，最小656 × 287(px)，平均 690 × 1284(px) である．
各商品画像を，21 枚のチラシ画像に対して商品検出を行なうので，商品検出の組合せは 609(=29 ×21) 通りである．そのうち，実際に対象商品がチラシに載っている組合せ (以降，検出されるべき組合せ) は 40 通りである．29 枚の商品画像には，21 枚のチラシ画像のうち複数のチラシに載っている商品もあれば，どのチラシにも載っていない商品もある．
物体検出の結果は，次式で定義される再現率，精度，F 値で評価した．

検出領域のサイズによるフィルタリング

本システムでは現在，チラシ画像内における 1 商品のサイズは 500 × 500(px) より小さく，30 × 30(px)よりも大きいと実験的に確認しており，画像探索における商品画像の拡大・縮小は，そのサイズの範囲内で行なっている．実際には，商品画像を分割した部分画像で探索を行なうため，250 × 250(px)〜15× 15(px) の範囲で部分画像を拡大・縮小して探索を行なっている．ここで，テンプレートマッチング法の探索結果である検出領域のサイズが最小の 15× 15(px) の場合には，部分画像はチラシ画像内になかったと判定してフィルタリングしている．

5

図 8. 商品画像

西友， http://www.seiyu.co.jp/

再現率 (R) =正検出
正検出 + 検出漏れ

(1)

精度 (P) =正検出
正検出 + 誤検出

(2)

F値=

2RP
R+P

(3)

ここで正検出とは，検出されるべき商品画像とチラシ画像の組合せ (40 通り) に対して，システムが実際に正しく商品検出できた数である．検出漏れとは，検出されるべき組合せに対して，システムが検出できなかった数である．誤検出とは，検出されるべきでない組合せ (569 通り) に対して，システムが検出してしまった数である．再現率は，検出されるべき組合せを，システムが実際にどれだけ検出できたか示す値であり，精度は，システムが実際に検出した組合せの中で，検出されるべき組合せがどれだ
け含まれていたかを示す値である．また，F 値とは精度と再現率の調和平均であり，システムの性能を総合的に判断するための一指標である．

5.2

結果

商品検出の結果は表 1 のようになった．精度は42%とあまり良い値とは言えないが，アンテナの機能としては，再現率が高いことが重要なことであり，その再現率は 92.5%と高い値であることが確認できる．
この結果をさらにスコアによりフィルタリングした場合の再現率や精度を求めると表 2 のようになっWISS 2007

6.2

表 1. 商品検出の結果登録したページの更新をチェックするサービスとして，はてなアンテナ6 や@links7 などのサービスがある．また，キーワードやトピックなどを登録しておくと，その情報が更新された際に通知してくれるサービスとして，Google アラート8 や Yahoo!アラー
ト9 などがある．しかし，これらはどれもテキスト情報でのチェックである．本システムのように画像の内容情報をチェックするサービスは見当たらない．

商品検出の結果

37
3510.925
0.4200.578

正検出
検出漏れ
誤検出
再現率
精度
F値

7
表 2. スコアによる検出結果のフィルタリング
スコア
正検出
検出漏れ
誤検出
再現率
精度
F値

1 以上
373510.925
0.420
0.578

2 以上
33710.825
0.971
0.892

3 以上
271300.675
1.0000.806

4 以上
202000.500
1.000
0.667

5
13
2700.325
1.0000.491

た．表から，スコア 2 以上の場合に再現率 82.5%，精度 97.1%，スコア 3 以上では再現率 67.5%，精度100%ということが確認できた．この結果から，スコア順に結果をソートすることで，正検出を結果の上位に表示することが可能であると言え，ユーザは上位の結果を見れば欲しい商品を容易に見つけることができる．

66.1

関連研究
チラシ情報を扱っている既存サービス

複数の店舗のチラシ画像を見ることができるサービスとして，「Shufoo！(しゅふー)2 」や「オリコミーオ！3 」などがある．どちらも自分の居住エリアを選択することで，その近くにある店舗のチラシ画像を見ることができるサービスである．また，他にも「毎日特売4 」や「情報楽園5 」などがある．これらはチラシ画像をそのまま掲載するのではなく，テキスト情報に直して掲載しているサービスである．それにより，商品ごとに他店と比較することができる．
しかし，どのサービスも登録されている店舗のチラシしか調べることができず，欲しい商品に対してアンテナを張る機能はない．

2

shufoo！， http://www.shufoo.net/
オリコミーオ！， http://www.dnp-orikomio.com/
4
毎日特売， http://www.navit-tokubai.jp/
5
情報楽園， http://club.e-topia.co.jp/
3

既存のアンテナサービス

おわりに画像探索の技術を用いて商品検出し，欲しい商品のチラシ情報を自動でチェックするシステム「ちらしアンテナ」を開発した．さらに，検出の結果に対し，5 段階でスコアリングをする手法を提案した．
その評価実験で，スコアが 2 以上の場合に再現率82.5%，精度 97.1%，スコアが 3 以上の場合には，再現率 67.5%，精度 100%になることを確認し，提案手法の有効性を示した．
今後の課題として，複数店舗のチラシ画像を使用した実験を行ない，本手法の汎用性を確認する必要がある．また，商品画像とチラシ画像が別の店舗の画像だった場合にも，ロバストに商品検出を行なう手法を検討する．検出の前処理である指定領域からの内接四角形の切り出し法や，その分割法についてもより効率的な方法を検討する予定である．システムの評価として，システムを使用した感想や満足度などを被験者実験により確認し，その結果を踏まえてユーザビリティをさらに向上させたいと考えている．

参考文献[1] Y.Li, J.Sun, C.K.Tang, H.Y.Shum. Lazy Snapping. ACM Transaction on Graphics (TOG),
23(3):303–308, 2004.
[2] 村瀬 洋, V.V.Vinod. 局所色情報を用いた高速物体探索–アクティブ探索法–. 電子情報通信学会論文誌, J81-D2(9):2035–2042, 1998.
[3] 尾上 守夫（編）. 画像処理ハンドブック. 昭晃堂,1987.
[4] D.I.Barnea and H.F.Silverman. A class of algorithms for fast digital image registration. IEEE
Trans. Comput., C-21(2):179–186, 1972.
[5] 川西 隆仁, 久野 和樹, 木村 昭悟, 黒住 隆行, 柏野邦夫, 高木 茂. サブテンプレート間距離を用いた適応的ウィンドウスキップによる高速テンプレー
トマッチング法. 電子情報通信学会論文誌, J88D2(8):1389–1397, 2005.
6

はてなアンテナ， http://a.hatena.ne.jp/@links，http://atlinks.jp/
8Google アラート， http://www.google.co.jp/alerts
9Yahoo!アラート， http://alerts.yahoo.co.jp/
7