Comments
Description
Transcript
画素の情報量を考慮した類似画像検索 Similar
DEWS2008 E10-1 画素の情報量を考慮した類似画像検索 光川 正弘† 鈴木 優†† 川越 恭二†† † 立命館大学大学院 理工学研究科 〒 525–8577 滋賀県草津市野路東 1–1–1 †† 立命館大学 情報理工学部 〒 525–8577 滋賀県草津市野路東 1–1–1 E-mail: †[email protected], ††{yusuzuki,kawagoe}@is.ritsumei.ac.jp あらまし 本研究では画素の出現頻度と画素の情報量を考慮した画像検索手法の提案を行う．現在，類似画像検索に 関する研究において，画像内に出現する画素の出現頻度から画像の特徴量を抽出する手法などが行われている．この 手法では，画像を特徴付ける画素は画像内で頻出する画素だけである．しかし，膨大な画像中で少数の画像でだけ出 現する画素は，画像を特定することが容易な画素と考えられるため，特定の画像でだけ出現する画素も画像を特徴付 けていると考えられる．ここで，画像は複数の画素によって構成されている点が，文書が複数の単語によって構成さ れる点に類似していることに着目した．画像と文書はある要素の集合によって構成されている点が類似する．画素の 出現頻度と，画素の情報量を考慮することは，文書検索における単語の出現頻度と単語の重要性を考慮することと考 えられる．そこで，画像の特徴量算出にベクトル空間モデルの重み付け手法である tfidf 法を利用し， Earth Mover’s Distance によって類似画像検索を行う． キーワード 類似画像検索，tfidf，Earth Mover’s Distance Similar Image Retrieval Considering Pixel Information Masahiro MITSUKAWA† , Yu SUZUKI†† , and Kyoji KAWAGOE†† † Graduate School of Science and Engineering, Ritsumeikan University Nojihigashi 1–1–1, Kusatsushi, Shiga, 525–8577 Japan †† College of Information Science and Engineering, Ritsumeikan University Nojihigashi 1–1–1, Kusatsushi, Shiga, 525–8577 Japan E-mail: †[email protected], ††{yusuzuki,kawagoe}@is.ritsumei.ac.jp Abstract In this paper, we propose a image retrieval method using pixel information. Recently, feature value of image in image retrieval system is frequency of pixel. However, pixel which appears in a few of images has a high feature value, because pixel which appears in a few of images is important to identify image. We aim at structure of image and document. The image is composed by pixels. The document is composed by words. We use vector space model to weight feature value for pixels, because structure of document is similar structure of image. So, we use tfidf to calculate feature value of image, and use Earth Mover’s Distance to retrieve similar image. Key words Similar Image Retrieval, tfidf, Earth Mover’s Distance 1. は じ め に 索の需要が高まっているといえる． 現在，デジタルカメラやデジタルカメラ機能が搭載された携 いる [1] [2]．従来の類似画像検索では，画像の特徴量として各 需要の高まりに伴い，様々な類似画像検索の研究が行われて 帯電話の普及によって，我々は気軽に写真を撮影することが可 色の画素出現頻度を用いることが一般的な手法の一つである． 能になり，我々の所持する画像数は増加している．そのため， 従来研究で色の特徴量に画素出現頻度を用いる理由に，画像内 膨大な画像の中から個人の要求する画像を検索することが困難 に頻出する色の画素は，画像を特徴付ける色であると考えてい となり，膨大な画像の中から個人の要求に適した画像を検索す るためである．しかし，画像を特徴付ける色は画像内に頻出す るために，類似画像検索の需要が高まっている．例えば，個人 る色だけではない．特定の画像でだけ出現する色も画像を特徴 がある画像に興味を持ったとする．その際に，興味のある画像 付ける色であると考えられる． と類似する画像を検索したいと考える．このため，類似画像検 例えば，風景画が膨大な枚数あり，画像は山や林の風景画と する．また，風景画の全てに空が写り，一部の画像には人，ま と，人間の感覚で類似する画像の検索が，本研究の類似する画 たは太陽が出現するとする．まず， 1 枚ずつ画像を閲覧するこ 像の検索という点に類似している．これは，本研究は画素の構 とによって，画像ごとに特徴的な色の画素を判断する．空の青 成の類似する画像を類似画像と定義している．この定義は，言 色と山や林の緑色が頻出することから，青色と緑色が特徴的な い換えると直感的に類似する画像と考えられる．直感的に類似 色であると考えられる．この考え方は，従来の類似画像検索で する画像は人間の感覚で類似する画像という点に類似している 用いられている特徴量の考え方である．次に，画像全てを閲覧 と考えた．しかし，研究の目的は類似しているが，本研究とは し，全画像中で特徴的な色の画素を判断する．この場合，全て 類似する画像を検索するために考慮した要素が異なる．本研究 の画像に空が写るため，青色は特徴的な色とは考えない．また， では類似する画像を検索するために，色相や彩度ではなく，色 山や林は緑色であるため，緑色も全ての画像に出現することか ごとに画素の出現頻度と特定性を考慮して画像を検索している． ら特徴的な色ではない．太陽や人は，画像内では空と山と比較 また，画像内の検索対象領域を限定することによって類似画 して画像内で占める画素の割合は低い．そのため，従来の手法 像検索を行うという研究が大森ら [5] によって行われている．こ で考えると，人の肌色，太陽の赤色は出現画素数が少ないため， の研究では，画像内の対象とする物体の領域を限定し，領域か 特徴量は小さいとされる．しかし，膨大な画像全体で考えると， ら色相，輝度のヒストグラムを用いることによって画像間類似 赤色や肌色の出現する画像数が少ないことから，赤色や肌色は 度を算出している．本研究では，クラスタリングによって画素 画像を特定しやすいと考えられる．つまり，特徴的な色である の色を限定し，この研究では画像内の物体領域に特徴量抽出対 と考えられる．本研究では，画像を特定するための特徴量を特 象を限定し，画素の特徴量を算出している．本研究とは，画像 定性と定義する． 中の画素の色を限定し，特徴量を算出する点が類似している． 本研究では色の出現頻度に色の特定性を考慮した特徴量によ しかし，画像の特徴量は対象領域内の画素だけのため，画像全 る類似画像検索を提案する．色の特徴量算出には，単語の重み 体の雰囲気を考慮して検索を行うことが困難になる．また，画 付けで用いられる tfidf 法の考え方を利用する．この考え方は 像の対象領域を限定するためには対象領域と背景となる画像 画像と文書間に類似関係があることに基づいている．画像は， の部分が明確に分離している必要があり，この手法が利用可能 色の組合せによって構成されている．そして，文書は単語の組 な環境が限定されている．しかし，本研究では画像の画素全体 合せによって構成されている．画像と文書は，ある要素の組合 から特徴量の算出を行っているため，使用環境は限定されてい せによって構成されている点が類似している．そのため，画像 ない． は文書，色は単語に相当すると考える．文書における一般的な 単語の特徴量は，文書中の単語出現頻度である．また，画像に おける一般的な色の特徴量は，画像内の画素出現頻度である． 3. 提 案 手 法 本研究の提案システムでは，検索問合せに画像を入力し，シ この画像と文書の類似関係から，画像に tfidf 法を適用可能で ステムによって検索された類似画像を出力する．提案手法によ あると考える．tfidf 法を画像検索に適用することによって，画 る類似画像検索の処理概要を図 1 に示す．まず，利用者は検索 像における色の特定性を考慮し，色自身の重要度に基づく，直 問合せとなる画像をシステムに入力する．そして， STEP1 で 感的な類似画像検索が可能になる．なお，本研究における画像 入力された問合せ画像から色情報の抽出を行う．問合せ画像の の類似とは，問合せ画像と比較画像に出現する画素と特徴量が 色情報を抽出後， STEP2 で検索対象画像の色情報を分類する 類似する状態と定義する． ことによって，画像全体で特徴的な色の画素を選出する．なお 2. 関 連 研 究 検索対象画像は，あらかじめ画像から色情報の抽出を行い，画 現在画像検索を行う手法には，画像の内容に基づいた CBIR ラスタ，問合せ画像と画像データベース内画像の色情報を用い (Content-Based Image Retrieval) の画像検索の以外に，画像と ることによって STEP3 では画像のクラスタごとにクラスタの 共に出現する文書などを用いて検索を行う TBIR (Text-Based 特徴量を算出する．そして STEP4 では STEP3 で算出した各 Image Retrieval) の画像検索 [3] などが挙げられる．CBIR に 画像の特徴量を用いることによって，問合せ画像と検索対象画 関する研究では，類似画像検索を行うために多数の特徴量抽出 像間の類似度を Earth Mover’s Distance によって算出し，類 手法が提案されている． 似度が高い画像順に利用者に表示する．以上が提案システムの まず，従来の Earth Mover’s Distance に彩度，色相を考慮 像データベースに格納している．STEP2 で選出した画素のク 処理概要である． した研究が藤田ら [4] によって行われている．この研究では， 3. 1 画像内の色情報抽出 従来の Earth Mover’s Distance による画像間類似度算出では 色ごとに画素の特徴量を抽出するために，画素の色情報を抽 人間の感覚で類似する画像でも，類似しない画像と判断され 出する必要がある．一般的な画素の色情報には RGB 表色系 る問題の解決を行っている．この問題は，画素の彩度，色相が の R 値，G 値，B 値などが挙げられる．しかし， RGB 表色 原因で起こる問題点であり，問題点を解決するために，従来の 系による画素の表現には問題があり，知覚できる色を完全に表 Earth Mover’s Distance 以外に，彩度，色相を問合せ画像と 現できない．本研究の類似画像とは直感的に類似すると感じる 比較画像の色ベクトル間距離の算出に考慮している．本研究と 画像である必要があるため，RGB 表色系による色情報の抽出 は， Earth Mover’s Distance による類似度算出手法が同じ点 は，人が知覚できる色を表現しきれないため適当ではない．そ データベース内画像の 色情報 画像データベース 入力 STEP1 画像の色情報 問合せ画像 色情報抽出 STEP2 色情報のクラスタリング 問合せ画像の 利用者 色情報 クラスタの座標 STEP3 色情報とクラスタを用いて 特徴量算出 各画像の特徴量 出力 STEP4 画像，画像間類似度 画像間類似度算出 図1 処理概要 idfi は以下の式 (8) によって算出される． idfi = log N n (8) 例えば，文書総数を 2 とし，idf を算出する単語 wi の出現文 書数は 1 とする．この場合，式 (8) により idf 値は 1 となる． しかし，画素の色情報に tfidf 法を適用すると， tf 値を適切 に算出することが困難な場合が考えられる．画素の色情報は， L 値と a 値， b 値によって構成されている．画素の出現頻度 は，画像内で L 値， a 値， b 値が全て一致する画素の出現頻 度であるが，この 3 値の組合せは膨大にあるため，3 値が完全 一致する画素が頻出することは少ないと考えられる．そのため， こで，国際照明委員会が定める CIEL*a*b* 表色系によって画 素の色情報を抽出する．この CIEL*a*b* 表色系は，人間の感 覚に近い色であると言われている．以上の利点から，本研究で は CIEL*a*b* 表色系による色情報の抽出を行う． RGB 表色系で表現された画素を，CIEL*a*b* 表色系に変換 する前処理として式 (1),(2),(3) によって XYZ 表色系に変換す る [3]．なお，式 (1),(2),(3) 中の R ，G ，B は画素の R 値，G 値，B 値である． 画素の tf 値に差が生じず，画素が他の画像に出現する頻度に も差が生じにくいため，適切な idf 値を算出することが困難と いった問題点が挙げられる． そこで， 3 値を利用して，従来研究と同様に画素の値域を 限定するために，画素の分類を行う．適切な分類を行うため に，分類開始時にクラスタの重心位置となる初期点を我々が自 由に決定可能な k-means 法を画素の分類に利用する．しかし， k-means 法には分類の結果が分類に用いる初期点に依存してし まうという問題点がある．そこで，この問題点を解決するため X = 0.489989R + 0.310008G + 0.2B (1) Y = 0.176962R + 0.81240G + 0.010B (2) Z = 0.0R + 0.01G + 0.99B (3) に，我々が求めるクラスタ数 c 以上の初期点を用いてクラスタ リングを行う．なお，クラスタリングの手法を図 2 に示す．ク ラスタリングの結果，各クラスタに含まれる画素数が算出され る．生成されたクラスタに多くの画素が含まれている場合，多 次に式 (4),(5),(6) を用いて， 算出した X 値，Y 値，Z 値を くの画像で用いられている色の画素が出現する位置にクラスタ CIEL*a*b* 表色系に変換する [6]．なお，式 (4)，(5)，(6) 中の が生成されていると考えられる．つまり，出現頻度が高い画素 Xn ，Yn ，Zn の値は，標準的に用いられている Xn = 98.072， のクラスタが生成されている．しかし，生成されたクラスタに Yn = 100，Xn = 118.225 とする． 含まれる画素数が少ない場合，少ない画像でだけ使われている ³ X L = 116 Xn ³ a = 500 ³ b = 200 ´ X Xn Y Yn 1 3 ´ 13 ¡ ¡ あるため， X Xn ³ − 500 ³ X Xn ¡ ¢ 13 X Xn − 16 Z Zn ¢ 13 ´ Yn Yn , (4) (5) (6) ¡ Y ¢ 13 ， Yn ¡ ， Z Zn ¢ 13 Z Zn ¡ ， ¢ 13 Z Zn ¢ 13 は式 (7) の条 の分岐条件は共通で を A と表現する． A (A > 0.008856) 7.787A3 + 16 (A < = 0.008856) 適当ではない． 本研究では，生成したクラスタに含まれる画素数が上位のク ラスタを必要な初期点数 c だけ取得し，クラスタの重心を初期 点として再度クラスタリングを実行する．通常の k-means 法 では，画素数の少ないクラスタを生成する場合が考えられるが， 本研究で行ったクラスタリングでは，画素数が少ないクラスタ を除去するため，適切なクラスタリングが可能となる． ( A= クラスタに含まれる画素数が少なすぎると，画像から判断する ことができない画素であると考えられるため，クラスタとして 1 3 ´ 13 ¡ Y ¢ 13 ， ¢ 13 ¡ Y ¢ 13 ¡ , 画素が出現する位置にクラスタが生成されている．この場合， Y Yn − 200 式 (4)，(5)，(6) 中の 件で分岐する． ´ 13 クラスタリングによって生成したクラスタを利用し画素の特 (7) 116 徴量を画像ごとに算出する．分類によって生成したクラスタ 数を m + 1 個とすると，画像 i (i = 0, 1, 2, · · · , n) のクラスタ 3. 2 画素の特徴量算出 j (j = 0, 1, 2, · · · , m) の特徴量を wij とし，画像 i のクラスタ j 3. 1 節で算出した画素の色情報に tfidf 法を適用することに に含まれる画素数を cij とし，クラスタ j が出現する画像数を よって，各画像から特徴量を算出する．tfidf 法は，情報検索 の分野で文書中から特徴的である単語を抽出する手法である． tfidf 法の tf とは，文書 D 中に出現する単語 wi の出現頻度を 表す．例えば，文書 D 中に単語 wi が 3 回出現した場合，単語 nj とする．tfidf 法を画像 i に適用すると式 (9) のようになる． wij = cij log n nj (9) 3. 3 画像間類似度算出 wi の tf は 3 となる．また， idf とは，単語が出現する文書頻 本節では， Earth Mover’s Distance(EMD) [7] による画像 度の逆数に対数をとったものである．文書数を N とし， idf を 間類似度算出手法について示す．EMD とは，ヒッチコック型 算出する単語 wi の出現文書数を n とすると，単語 wi の idf 値 輸送問題の解に基づく尺度である．ヒッチコック型輸送問題を a a fij > = 0 (1 < =i< = m, 1 < =j< = n) L L b n X (12) fij < = wpi (1 < =i< = m) (13) fij < = wqj (1 < =j< = n) (14) j=1 b m X 画素頻度上位のクラスタで 再クラスタリング i=1 図 2 k-means クラスタリング m n X X 例で示すと，複数の工場で製品を生産し，生産した製品を複数 の店舗に輸送する状況で，製品の輸送費を最小とする場合を算 出することである．EMD は，例における工場で生産される製 品の量と店舗に供給する製品の量，そして工場から店舗へ製品 を輸送する際に発生する輸送費を定義することが可能な問題で fij = min( i=1 j=1 間の感覚に近いことが知られているため， EMD を利用するこ n X wqj ) (15) j=1 以上の制約条件を満たす fij を算出し，輸送コストが最小となる fij を式 (16) に用いることによって画像間類似度 W (P, Q, F ) を算出する．式 (16) 中の F は輸送量の総和，P は画像 P の Color Signature，Q は画像 Q の Color Signature である． W (P, Q, F ) = 検索の分野でも 獅子掘ら [9] が EMD を利用してハミングによ る類似楽曲検索の研究を行っている．また， EMD の尺度は人 wpi , i=1 適用可能という特徴がある．このため，画像検索の研究では竹 内ら [8] の TBIR の画像検索に EMD を適用する研究や，楽曲 m X m n X X dij fij (16) i=1 j=1 式 (16) の dij は pi ，qj 間の距離であり，dij を算出するために ユークリッド距離を利用する．ユークリッド距離算出式は以下 とによって画像の雰囲気を検索結果に反映させることが可能で の式 (17) となる．式 (17) 中の L1i ，a1i ，b1i は問合せ画像の あると我々は考え，本研究の画像間類似度算出に利用した．な クラスタ i の L 値，a 値，b 値であり， L2j ，a2j ，b2j は比較 お，以後例における工場を需要地，店舗を供給地，製品の量を 画像のクラスタ j の L 値，a 値，b 値である． 重み，輸送費を輸送コストとして説明していく． 3. 2 節で算出した特徴量を用いた画像間類似度算出手法を示 す．EMD による画像間類似度を算出では，分布を画像，問合 せ画像のクラスタを需要地，比較画像のクラスタを供給地，ク ラスタの特徴量を重みとして考える．また，輸送コストは問合 せ画像と比較画像のクラスタ間距離と輸送する特徴量の積とす る．問合せ画像を P とし，比較画像を Q とし，これらの分布 を クラスタとクラスタの特徴量を Color Signature によって表 dij = p (L1i − L2j )2 + (a1i − a2j )2 + (b1i − b2j )2 このように画像間類似度を算出するが，画像ごとに特徴量の総 和は異なる．そのため，EMD では制約条件の式 (??) によって 正規化を行う．よって，画像間類似度算出は以下の式 (18) のよ うになる． Pm Pn d f i=1 j=1 ij ij EM D(P, Q) = Pm Pn 現する．なお， Color Signature は (ci , wi ) のように画素のク ラスタ i，そしてクラスタ i の特徴量 wi の組によって表現され (17) i=1 4. 実 j=1 fij (18) 験 る．問合せ画像 P と比較画像 Q の分布を Color Signature に よって表現すると，以下の (10)，(11) ように定義する．(10)， 4. 1 実 験 環 境 (11) 内の ppm は問合せ画像内のクラスタであり，qqn は比較画 本節では，提案手法による画像検索結果と，比較手法による 像内のクラスタである．また，wpm はクラスタ ppm の特徴量 画像検索結果の比較実験を行う．比較手法には，従来手法で用 であり，wqn はクラスタ qqn の特徴量である． いられている画素の出現頻度を特徴量とした EMD による類似 画像検索，提案手法の特徴量を用いたコサイン尺度による類似 P = {(p1 , wp1 ) , (p2 , wp2 ) , · · · , (pm , wpm )} (10) Q = {(q1 , wq1 ) , (q2 , wq2 ) , · · · , (qn , wqn )} (11) 画像検索，画素の出現頻度を特徴量としたコサイン尺度による 類似画像検索の 3 手法を用いる．以後は，画素の出現頻度を用 いた EMD を tf-EMD ，提案手法の特徴量を用いたコサイン 次に，画像 P ，Q の Color Signature (10)，(11) を用いるこ 尺度を tfidf-cosine ，画素の出現頻度を用いたコサイン尺度を とによって画像間類似度を算出する．まずクラスタ間の輸送量 tf-cosine とする．比較手法のコサイン尺度による類似画像検索 の定義を行う．クラスタ pi から qj への輸送量は fij と表す．こ は，本研究で用いている特徴量が文書検索で用いられている手 こで，fij を求めるためには以下の制約条件を満たす必要があ 法によって算出されているため比較手法として用いた．また， る．以下の制約条件内の wpi は問合せ画像 P のクラスタ i の 従来手法では画素の出現頻度だけを特徴量としているため，提 特徴量であり，wqj は問合せ画像 Q のクラスタ j の特徴量で 案手法の特徴量を用いたコサイン尺度と，画素の出現頻度によ ある． るコサイン尺度の 2 手法を比較手法として用いた． 本実験では， INEX2007（注 1） のテストコレクションを用いて 実験を行う．画像データベース内の比較画像は 176045 枚であ る．また，3. 2 節で行った画素の分類で生成するクラスタを 20 で実験を行った． 次に，比較手法で用いるコサイン尺度について説明する．コ サイン尺度は，問合せ画像の特徴ベクトル P と，比較画像の 特徴ベクトル Q 間の類似度を二つのベクトルがなす角度から 算出する．問合せ画像 P と比較画像 Q 間のコサイン尺度を 図 3 問合せ画像 1(ID:527) cos (P, Q) とすると，コサイン尺度は以下の式 (19) によって算 出される． P20 PQ = qP cos (P, Q) = ||P ||||Q|| 20 j=1 j=1 wpj wqj 2 wpj qP 20 j=1 (19) 2 wqj また，q と Ii は以下の (20)，(21) ように定義する． P = [wp1 , wp2 , · · · , wp20 ] (20) Q = [wq1 , wq2 , · · · , wq20 ] (21) 式 (19) の wpj ，wqj は j 番目のクラスタが持つ特徴量を表して (a) 提案手法 (b) tf-EMD いる． 4. 2 実 験 結 果 問合せ画像 1 の実験結果は図 4，問合せ画像 2 の実験結果は 図 6 のようになった．なお，図 4，図 6 中の画像は各手法で最 も類似度が高い画像である． 問合せ画像 1 の実験結果から，提案手法の結果 4(a) は画像 4(a) で出現するクラスタも類似しており，算出されたクラスタ ごとの特徴量も類似していた．本研究における画像の類似する とは，問合せ画像と比較画像に出現する画素と特徴量が類似す (c) tfidf-cosine (d) tf-cosine る状態と定義しているため，提案手法による類似画像検索は類 似画像を検索が行われたと考えられる．また， tf-cosine による 図 4 問合せ画像 1(ID:527) 検索結果 画像検索の結果も，出現するクラスタ，画像を構成するクラス タの特徴量が問合せ画像 1 と類似していた．しかし， tf-EMD タへ輸送することによって問合せ画像と比較画像間の類似度を と tfidf-cosine による実験結果では問合せ画像 1 と類似する部 算出する．ここで，問合せ画像と比較画像に同じクラスタの画 分は含まれている．しかし，tf-EMD と tfidf-cosine の検索結 素が存在する場合，輸送コストは発生しない．しかし，輸送コ 果は問合せ画像 1 で特徴量が高いクラスタだけが出現してい ストの量は 3. 3 節の制限条件 (13)，(14)，(15) から問合せ画像 て，特徴量が小さいクラスタの部分が考慮されていないため， か比較画像の特徴量までと制限される．そのため，問合せ画像 画像の雰囲気は類似するとは言えない． のクラスタと比較して比較画像のクラスタが小さい特徴量の場 問合せ画像 2 では， tfidf-cosine と tf-cosine の実験結果が 合，同一クラスタに輸送できない特徴量は，比較画像内の輸送 問合せ画像 2 に出現するクラスタが類似しており，特徴量も同 可能なクラスタに輸送される．この時，問合せ画像のクラスタ 程度であることから，tfidf-cosine と tf-cosine は類似画像を検 と異なるクラスタに輸送されるため，輸送コストが発生する． 索していると言える．しかし， EMD による検索結果では，問 つまり， EMD では輸送コストを類似度として算出する．画 合せ画像 2 と出現するクラスタは類似しているが，検索結果の 像間類似度が高くなるのは比較画像に問合せ画像と同じクラス 画像を閲覧すると，画像を構成している画素の色は類似してい タの画素が出現する画像と考えられる．しかし， tf-EMD では ない． 問合せ画像と同じクラスタの画素が出現しない画像が検索され 4. 3 考 察 問合せ画像 1 での実験で，提案手法は類似画像が検索され たが， tf-EMD では適当な画像が検索されていない．EMD で は，問合せ画像のクラスタ特徴量を比較画像の最も近いクラス た．これは，図 7 のように問合せ画像 A と比較画像 B が異な るクラスタの画素で構成されている場合，図 7 のクラスタ 4 の 輸送コストが画像間類似度となることがある． ここで，クラスタ 4 の特徴量が小さい場合，画像 A のクラ スタ 4 から画像 B の各クラスタへの輸送コストは非常に小さ （注 1）：http://inex.is.informatik.uni-duisburg.de/2007/ 画像A ①②③④⑤ ⑥ ・・・ 画像B ①②③④ ⑤ ⑥ ・・・ 類似度算出 図 5 問合せ画像 2(ID:530) 同じ番号の領域同士で類似度算出 全類似度の平均を画像間類似度に 図 8 EMD 改良手法 画像検索の結果が依存してしまうためである．そのため，問合 (a) 提案手法 (b) tf-EMD せ画像 1 で頻出するクラスタの画素で構成されている画像が検 索された． 提案手法では，問合せ画像 1 と同じクラスタの画素が出現 し，問合せ画像の特徴量と近似した値の画像が検索された．し かし，類似しているのは特徴量の点で評価した場合であり，実 際に画像を閲覧すると，問合せ画像 1 と類似している画像とは 言えない．問合せ画像と特徴量が類似する画像が，閲覧すると 類似していないのは，色の構成は類似するが，画像内での画素 (c) tfidf-cosine (d) tf-cosine 図 6 問合せ画像 2(ID:530) 検索結果 画像A 画像B クラスタ1 クラスタ1 クラスタ2 クラスタ2 の出現位置が考慮されていないためである． 問合せ画像 2 では，コサイン尺度を用いた手法は，問合せ画 像 2 と類似する画像が検索されている．しかし， EMD による 手法では類似画像が検索されず，コサイン尺度と EMD のどち らの場合でも画像内に問合せ画像にない画素が出現している． これは，図 7 の問題点の他に，画素のクラスタリングにも問題 点があると考えられる．本研究では，生成するクラスタを 20 クラスタ3 生 ト発 ト発生 コス コス 生 コスト発 クラスタ3 クラスタ4 として実験を行っている．しかし，画素が集中し過ぎている場 所にクラスタを生成すると，複数の色がクラスタに含まれてし まう．このため，問合せ画像と同じクラスタが用いられている 比較画像の場合でも，類似する色以外の画素が画像に含まれ， 画像間類似度が高くても，検索結果の画像が類似しない結果に 図 7 EMD の問題 くなる．そのため，問合せ画像と比較画像が同じクラスタの画 素で構成されている場合でも，輸送コストが図 7 のように，画 像 A と画像 B に出現するクラスタの画素が異なる場合より大 きくなることがある．このため， tf-EMD の検索結果のよう に，画素の構成が類似しない画像の類似度が最も高くなる．こ の問題は， EMD による類似度を算出する際に，複数のクラス タによって画像が構成されていることによってこの問題が発生 する．そのため，提案手法でも，この問題が発生することが考 えられる． また，コサイン尺度による類似度算出で tfidf-cosine では， 問合せ画像 1 と類似しない画像が検索されている．これは，コ サイン尺度による類似度算出は，出現頻度が大きいクラスタに なる． 4. 4 改 良 手 法 4. 3 節で挙げた問題点は，画像は複数のクラスタによって構 成されているため， EMD を算出する際に問題が発生するこ と，色の出現位置が考慮されていないため，視覚的に類似した 画像が検索できていない，クラスタリングでのクラスタの取り 方の三つである． EMD の問題点は図 8 を用いて改良手法の説明を行う．ま ず， EMD を算出する際の問題点である．この問題は画像に 複数のクラスタの画素が含まれているため，同じクラスタの画 素で構成されている画像と比較した場合より，異なるクラスタ の画素で構成された画像の類似度が高くなることが考えられ る．この問題を解決するためには，画像が一つのクラスタに含 まれる画素だけで構成されていれば，画像が類似する，類似し 5. お わ り に 本研究では，画素の特定性と出現頻度から画素の特徴量抽出 を行い，画素の特徴量を用いた類似画像検索を提案した．本提 案手法によって，問合せ画像と類似する画像が検索されるのを 従来手法 制約付きクラスタリング 確認した．提案手法の結果から，画像が含むクラスタの数によ る EMD の問題点，色の出演位置を考慮していない問題点，画 素のクラスタリングによる問題点が発見された．今後は 4. 4 節 図 9 制限付きクラスタリング の手法を用いて改良を行うことを検討している． ないという 2 値評価を行える．つまり，画像内のクラスタ数を 減少させることによって画像間類似度をシステムが誤認する問 題点を解決することが可能である．そこで改良手法として．画 像を複数の領域に分割し，領域ごとに EMD による類似度の 算出を行う．そして，全領域の類似度の平均値を画像間類似度 とする．改良手法では領域に画像を分割することによって，領 域に含まれるクラスタの種類が減少するため，EMD の問題点 を解決可能になる．また，問合せ画像と比較画像の同じ位置の 領域同士で類似度を算出するため，位置を考慮した画像検索を 行うことが可能になり，色の出現位置が考慮されていない問題 点も同時に解決することができる．ここで，各領域の類似度を Si (i = 0, 1, 2, · · · , m)，クラスタ数を m + 1 とすると，以下の 式 (22) によって EMD の類似度 S を算出可能になる． S= m 1 X Si m (22) i=0 次に，クラスタリングの際に生成するクラスタ数が少ないた め，一つのクラスタに複数色の画素が含まれてしまう問題点が ある．この問題点を解決する手法に，生成するクラスタ数を増 加させ，クラスタの範囲に制約を加える方法が考えられる．図 9 によって改良手法の説明を行う．まず，本研究で用いたクラ スタリングの手法では，複数の色がクラスタ内に含まれる問題 点がある．この問題点を解決するために，生成するクラスタ数 を増加させることが考えられる．しかし，クラスタ数を増加さ せても，クラスタの位置によっては複数の色が含まれるクラス タが出現する．そこで，生成するクラスタの大きさを制限する ことによって，適切なクラスタを生成する．この制限により， 初期点で生成したクラスタに含まれない画素が出現する．そこ で，クラスタに含まれない画素を用いてクラスタリングを再度 行うことによって，全画素が適切な色で分類される． また，色の特徴量にクラスタの tfidf を用いているが， idf のみを特徴量として用いることも考えられる．idf 値が高い色 を画像の特徴量が高い色と判断し， idf を深く分析することに よって類似画像を導き出せるのではないかと考える．提案手法 の tfidf 法を用いる場合，クラスタの数を変える必要がある．そ れは，クラスタの数が 20 ということは，文書中に出現する単 語が 20 個ということである．実際に文書ではこのように少な い単語ということはないため， tfidf 法を適用するためにはク ラスタの数の設定が課題になる． また，精度の評価を行っていないため，CLEF(Cross Lan- guage Evaluation Forum) による提案手法の評価を行いたいと 考えている． 文 献 [1] 横山, 渡辺, 菅原, 上野：“フラクタル符号に基づく構造的な類似 性抽出手法の提案”, 電子情報通信学会技術研究報告, 101, 713, pp. 105–112 (2002). [2] N. Vasconcelos: “From Pixels to Semantic Spaces:Advances in Content-Based Image Retrieval”, Computer, 40, 7, pp. 20–26 (2007). [3] 池田：“色彩工学の基礎”, 株式会社 朝倉書店 (1993). [4] 藤田, 野口, 石田, 平澤：“色情報に対する人間の感性を考慮した類 似画像検索”, FIT2007 第 6 回情報科学技術フォーラム (2007). [5] 大森, 川田, 清木：“対象領域限定型類似度計量系による画像メタ データ抽出方式”, DEWS2006 (2006). [6] 大田：“色彩工学”, 東京電機大学出版局 (1993). [7] Y. Rubner, C. Tomasi and L. J. Guibas: “The Earth Mover’s Distance as a Metric for Image Retrieval”, International Journal of Computer Vision, 40, 2, pp. 99–121 (2000). [8] 竹内, 黄瀬：“Eatrh Mover ’s Distance に基づく Text-Based Image Retrieval”, 情報処理学会研究報告, 自然言語処理研究会 報告, 2007, 7, pp. 33–38 (2007). [9] 獅々堀, 大西, 柘植, 北：“Earth Mover’s Distance を用いたハ ミングによる類似音楽検索手法”, 情報処理学会論文誌, 48, 1, pp. 300–311 (2007).