Document

Semantic Based Image
Retrieval:
A Probabilistic Approach
Proc. of ACM Multimedia 2000,
pp 167-176, 2000
Ben Bradshaw
論文紹介者：久保正明
Contents
Content-based Image Retrieval
 Overview
 Extracting Feature Vector

• Colour extraction
• Texture Extraction
Probabilistic Labelling
 Results

• Natural/Man-made
• Inside/Outside
Image Retrieval Application
 SUMMARY

Content-based Image Retrieval

Low-Level Features (First generation)
• QBIC（M.Flickner et al,”Intelligent Multimedia Information Retrieval, chapter Query by image and video
content: The QBIC system”,pp 8-22.AAAI Press, 1977）
• Virage(A.Gupta et al,”Visual information retrieval”,Communication of the ACM, 40(5):71-79,1997)
• VisualSEEK(J.Smith et al,”Intelligent Multimedia Information Retrieval, chapter Querying by
colour regions using the VisualSEEK content-based visual query system”,pp 23-41, AAAI Press, 1997)
• ユーザが検索したい特徴量を指定できる
• 現在はユーザがクエリーを考案する助けにはならないと認識されて
いる


どの特徴量を使えばよいか決定することが困難
Query by Example (Second generation)
• Texture of texture(J.S.DeBonet,”Novel statistical multiresolution techniques for image
synthesis, discrimnation and recognition”. Master’s thesis, M.I.T. Learning and Vision Group, AI Lab,1997
• MARS(Y.Rui et al,”A relevance feedback architecture in content-based multimedia information
)
retrieval system”In Proc. of IEEE Workshop on Content-based Access of Image and Video Libraries, 1977.
)
• ユーザは例示画像を与えるだけ
• クエリをはじめる前に最適な画像を持っている必要がある
In conjunction with CVPR’97
Third generation of image retrieval

Second generationの低レベル特徴をハイレベ
ル意味空間に置き換える
• システムは低レベルな特徴を使って検索を行うがユー
ザは意味に基づいてクエリを作成

クエリを高レベルな意味で作るためユーザにとっ
ては低レベル特徴よりも理解しやすい
• 低レベル特徴：赤色が多い写真 etc
• 高レベルな意味：Walesでの休暇の写真 etc
従来手法と本手法の違い

局所的な領域を意味付けする
• 従来(参考文献参照)は画像に対して値を出していた

確率による局所領域の意味付け
• 画像全体ではなく画像中の小さい領域に対して意味付け
・M.M.Grkani et al,”Texture orientation for sorting photos ‘at a grance ’”,
In Porc. Of the IEEE int. Conf. On Pattern Recognition ,1994
・E.C. Yiu,”Image classification using colour cues and texture orientation”
Master’s thesis,Dept EECS, MIT, 1996
・M.Szummer et al,”Indoor-outdoor image classification”
In IEEE Int. Work. On Content-based Access of Image and Vid.
Databases ,1998
・A.B.Torralba et al,”Semantic organisation of scenes using discriminant
structural templates”,In ICCV’99,1999
・A.Vailaya,”Content-based hierarchical classification of vacation images”,
In IEEE Conf on Multimedia Computing and Systems,
vol1 pp518-523,1999
自然領域
人工物領域
Overview：ラベリング
ラベリング：領域に意味付けをすること
 確率を用いた画像の局所的ラベリング

• 多くの異なったブロックサイズからデータを収集
• 収集したデータを組み合わせて知識獲得
• 一定のブロックを用いるアルゴリズムよりもロバスト

意味ラベル
• Natural or Man-made (自然、人工)

Local sampling procedure
• Inside or Outside (屋内、屋外)

Global sampling procedure
Overview:局所サンプリング

サンプリングポイントを中心とした異なったサイズ
のブロックからデータを抽出
• ブロックを階層構造にレベル分けする
Natural/Man-madeのラベリングではサンプル
“グリッド”を16x16に設定（次ページ）
 画像サイズ 256x384,384x256

Local sampling
Sample Grid
16
16
Nature
Man-made
Overview:確率による分類
Nature
Man-made
特徴ベクトル特徴ベクトル
Images
特徴ベクトル
Dimension
Dimension
Dimension
Reduction
Reduction
Reduction
Nature
確率密度推定確率密度推定
事後確率
Man-made
Colour extraction
値の間でできるだけ相関がない色モデルがよい
 よく利用されるモデル

• Ohta colour model
• HSV colour model
• 両者ほぼ同じ結果が出るので変換が容易なOhtaモデ
ルを利用する

Ohta colour model
• 輝度（luminance） I o1 、色差情報（chrominance） I o 2 , I o 3
C1 ( Bl )   I o 2 ( r )d r
Bl
C2 ( Bl )   I o 3 ( r )d r
Bl
r : particular pixel pisition in the image
Bl : Image block at level l
Texture extraction

Complex wavelet transform (CWT)
• 方向に沿ったテクスチャ

N.G.Kingsbury,”The dual-tree complex wavelet transform:
Gabor wavelet
A new efficient tool for image restoration and enhancement”
,In EUSIPCO’98, vol1 pp319-322, EURASIP, 1998
• 従来良く利用された手法
• Gaborは2次元、CWTは1次元の畳込み（Convolution）
• CWTの方が負荷が少ない A.K.Jain et al.”Unsupervised texutre segmentation using Gabor filters”,
Pattern Recognition, vol. 24,pp 1167-1186,1991
  {15 ,45 ,75 ,75 ,45 ,15 }
I s  I o1 *  s
where  s is the wavelet function at scale s
I o1 is intensity of the image
s ( Bl )   ( I s ( r )) 2 d r
Bl
Complex Wavelet Transform:CWT
h0 f ( 2n )  f ( n )
Pre-filter
Filter
f  [  j,5, j ] / 5
 : const
h0  [1  j,4  j,4  j,1  j ] / 10
h1  [1  2 j,5  2 j,5  2 j,1  2 j ] / 14
低周波成分A
高周波成分D（３）
を2つ出す。
テクスチャー特徴の次元数

ウェーブレットのスケール（変換回数）
• 1-4

方向
• 6

  {15 ,45 ,75 ,75 ,45 ,15}
24次元ベクトル
TBl  [11 ( Bl ), 12 ( Bl ), , 46 ( Bl )]
T41 ( Bl )
T12 ( Bl )
Sample grid
T13 ( Bl )
T11 ( Bl )
T14 ( Bl )
T16 ( Bl )
T15 ( Bl )
Feature Vector
26次元
色：2次元（色差）
テクスチャ：24次元（スケール1-4,6方向）
色、テクスチャ特徴を一緒に扱う
X Bl  [11 ( Bl ), 12 ( Bl ), , 46 ( Bl ), C1 ( Bl ), C2 ( Bl )]
“Best” vectors for classification
クラス間が大きく分かれている
クラス内の距離が小さい
Bad vectors
Good vectors
Fisher’s linear discriminant
最適な分類となる直線を探す
多次元
一次元
射影（projection）
X Bl  pTl X Bl
Fisher’s Discriminant １
n個のd次元サンプルx1…xnをとりこのうちn1個が集合
Χ1に属しω1とラベル付け、n2個が集合X2に属しω2
とラベル付けされるとする。Xの各要素の線形結合y→
y  w Tx
これに対しn個のサンプルy1…ynが与えられそれぞれ
X1、X2に対応する集合Y1、Y2が得られる。このときwは
Y1,Y2がうまく分離できるものを選ぶ必要がある。
クラス間の分離殿尺度としては標本平均の差を取る。
標本平均をmiとすると、射影後のサンプルの標本平均
~  1
m
y
i
は次式で与えられる。
ni yYi

1
ni
w
xXi
T
x  w T mi
分離度を向上させるためには、標本平均の差が各クラスの
標準偏差の表価値に対して大きくする必要がある。射影後の
サンプルの分散は
~
~ )2
si 2   ( y  m
i
yY
mi 
1
ni
x
X X 1
i
Fisher’s Discriminant 2
1 ~2 ~2
( s1  s2 )は蓄積されたデータの分散の推定値
n
~
s12  ~
s22は射影されたサンプルのクラス内分散
と呼ばれる。 Fisher' s linear discrimina nt は以下の評価関数
~ m
~ |2
|m
J( w )  ~12 ~22
s s
1
2
を最大とする wを用いた線形関数 w T xとして
定義される
Classification flow
Images
Feature vector extraction
Construction of
Dimension reduction
probability density
using Fisher’s discriminant
using Maximum Likelihood Approach
Posterior conditioned
Class1
probability
Class2
予備知識：確率分布
確率分布
コインを2回投げたとき、表が出る回数の確率分布
予備知識：確率密度関数
Xを連続確率変数、f(x)を確率密度関数と呼ぶ
定義域が a  x  b であれば
b
P(a  x  b)   f ( x )dx  1
a
このときPを確率分布と呼ぶ
予備知識：正規分布
発生確率が完全に独立かつランダムであれば
確率密度関数は正規分布に従うことが知られている
最尤法（Maximum likelihood
approach）
最尤法：いくつかのサンプルから尤もらしい確率
密度分布を決定する手法
 正規分布に従うと仮定

各レベルにおける確率密度分布
X1,X2,X3：投影後の一次元データ
予備知識：同時確率と条件付確率
同時確率と条件付確率
Male(M)
Blue(B)
3,000
Female(F
)
1,000
4,000
Green(G) 2,000
4,000
6,000
5,000
5,000
10,000
同時確率：
条件付確率：
青い目の男性
男性という条件のもと青い目の人
P ( B, M ) 
3000
3

10000 10
P( B | M ) 
3000 3

5000 5
確率推定
仮定：それぞれのレベルでの尤度は互いに独立
 ブロックを１～Lとするときの事後条件付確率

Ck where k 1,2 : 2つのクラス
P() : 確率
p() : 確率密度
P ( X 1 ,  , X L | Ck )
P ( Ck | X 1 ,  , X L ) 
P ( Ck )
P ( X 1 ,, X L )


L
l 1
P ( X l | Ck )
P ( X 1 ,, X L )
P ( Ck )
ただし P ( X 1 ,, X L )
 P( X L | X L1 ,, X 1 )  P ( X 2 | X 1 ) P( X 1 )
実験：Natural/Man-made
NaturalとMan-madeの分類
 学習用画像

• Natural 120枚
• Man-made 120枚
レベル１～４（128x128～16x16）
 １次元ベクトルの作成（Fisher’s linear
discriminant）
 確率密度推定

X n : Projected data
実験：Natural/Man-made

実験1
• 自然のみ 120枚、人工物のみ 120枚

実験2
• 自然、人工物が両方写ったもの 125枚
確率密度生成時に利用した画像は用いない
 事後確率が0.5以上であればクラスに属する

実験結果

自然と人工物の両方を含む画像ではレベルをを
追加したほうが精度が高い
• レベル4のみでは29.8%だが1,2,3,4を使うと21.6%に
減少

一方のみしか写っていない画像は精度が高い
• エラー率約10%程度
人工物の割合の結果
ρ：人工物の割合
人工物が入っている割合（レベル1,2,3,4を利用）
上段：オリジナル画像
下段：人工物を明るく表現
実験：Outside/Inside
Outside/Inside（屋内・屋外）の分類
 Natural/Man-madeの分類とは違い、局所的でなく全
体的な特徴を取るようにする
 屋内 120枚、屋外 120枚
 レベル０～４（画像全体～16x16）

• 全体的な特徴を取り入れるため
1次元ベクトルの作成（Fisher’s linear discriminant）
 全体的な特徴量を抽出するため32x32のグリッドを用
いた

• Natural/Man-madeでは16x16
実験結果：Outside/Inside
3レベルあれば分類精度は86.3%
 Natural/Man-made分類と同様複数のレベルを
用いたほうが精度が高い

• ただし、画像全体（Level 0）を用いると精度低下
Outside/Insideの分類例
屋内･屋外の例、ρ：屋外と判断される領域の比率
レベル2,3,4のみで作成
分類誤り
ビルのペイント
周りの木から
プールと窓を
屋内と
が自然扱い
の影で建物が
屋外と判断
誤認識
自然扱い
画像検索アプリケーションのプロトタイプ
提案した分類方法がアプリケーション上で有効に
働くかを評価する
 著者がデジカメで撮影した800枚の画像 12か
月分
 撮影日時の情報を追加
 Daytime/Night-time（昼/夜)の分類を
Inside/Outsideと同様の手法で追加
 従来手法との違い

• 従来：実際の特徴ベクトルを保持
• 本手法：3つの確率の値（自然、屋外、昼）,日付
検索方法

写真がとられた日時を指定
• 検索対象の数を大幅に削減

屋外で撮られたか屋内で撮られたかを指定
• 屋外の場合次を指定
NaturalとMan-madeのどちらが多いか
 昼と夜どちらに撮られたものか

クエリー１
「My Holiday in Wales」
著者は同じ時期にBostonとWalesに行っていた。
日時のデータにより800枚から171枚へ。
風景が主に写っていた
P(Outside)xP(Natural)の降順
本当の適合画像は71枚
24枚中17枚が
適切な画像
クエリー２
「The evening spent with friends in a bar in Boston」
著者は同じ時期にBostonとWalesに行っていた。
日時のデータにより800枚から171枚へ。
屋内で撮った
P(Inside)で降順にソート。
本当の適合画像は16枚
24枚中9枚が
適合画像。
プロトタイプから得られたこと

Semantic-based Image retrieval systemの可
能性
• 日付のメタデータ＋少ないカテゴリ分類でさえユーザ
に対して迅速かつ容易な画像検索を提供できる

意味での画像検索の前提
• ユーザがクエリをシステムが抽出した意味に置き換え

例：クエリ「Holiday in Wales」→屋外＋自然
• クエリを低レベルな画像特徴に置き換えるよりも直観
的
SUMMARY

確率、多重階層を用いた画像の意味分類
• 多重階層により事後確率の精度を向上

意味分類
• Natural/Man-made、Inside/Outside
• 86-91%の精度
• 学習画像200枚程度

従来研究との比較
• 定量的な比較は困難
不変的な画像がない
 実験で用いた画像が少ない


日付を追加
• 検索結果の向上
• 画像検索にとって有効な手法
問題点


線形的に分類できるときしか適用できない
分類アルゴリズムは階層レベル間に統計的な独立性が
あるという仮定が正しいという前提が必要
• 分類の公式が当てはまらない


改善について
より洗練された確率密度推定を利用する
• Kernel method, Bayesian Belief Networks
• これらの手法は本手法に比べ精度向上、上記
制限の解消が見込める

他の分類カテゴリ
• People/No peopleなど

妥当性のフィードバックと例示画像による検索機能の追
加

Download Report