NAIST-IS-MT0951124

修士論文

テクスチャの幾何学的変換と類似パターン位置を考慮した画像修復

宮本 龍

2011 年 2 月 3 日

奈良先端科学技術大学院大学
情報科学研究科 情報システム学専攻

本論文は奈良先端科学技術大学院大学情報科学研究科に修士 (工学) 授与の要件として提出した修士論文である。
宮本 龍

審査委員：
横矢 直和 教授

(主指導教員)千原 國広 教授

(副指導教員)山澤 一誠 准教授

(副指導教員)テクスチャの幾何学的変換と類似パターン位置を考慮した画像修復∗
宮本 龍

内容梗概
画像内の不要な部分を取り除き，その欠損領域を自動的に修復する画像修復に関する研究が近年盛んに行われている．従来，欠損領域の修復に関しては，パターン類似度 SSD (Sum of Squared Diﬀerences) を用いて欠損領域全体の尤もらしさに基づくエネルギー関数を定義し，それを最小化することで画像を修復する手法が提案されている．また，明度変化を許容したパターン類似度 SSD を用いること
で，明度の不自然な変化を抑止する手法も提案されている．しかし，画像内のテクスチャパターンに限りがあるため，違和感のない修復に必要なパターンが画像内に存在しないことが多い．また，パターンの変形に比較的弱い SSD による評価尺度を用いて画像全体に対して類似パターンの探索を行うため，計算コストが大きく，かつ不適切なパターンの対応を招き，修復画像がぼけてしまうという問題がある．そこで，本論文ではテクスチャの明度変化だけでなく幾何学的な変換も許容したパターン類似度によるエネルギー関数を新たに定義し，画像内で近接するパターン間の位置関係を利用した効率的な探索を用いてこれを最小化すること
で，高品位に欠損領域を修復する手法を提案する．これにより，修復に必要なパターンの不足によるテクスチャの明度と幾何学的な構造の不自然な変化を抑止す
る．また，画像内で近接するパターン間の位置関係を利用した探索範囲の限定により，計算コストを削減し，かつ不適切なパターンの対応付けによるぼけの発生∗

奈良先端科学技術大学院大学 情報科学研究科 情報システム学専攻 修士論文, NAIST-ISMT0951124, 2011 年 2 月 3 日.

i

を抑制する．実験では，様々な画像に対して欠損領域の修復を行い，主観的評価
実験により従来手法と比較することで提案手法の有効性を示す．

キーワード
画像修復，画像補間，エネルギー最小化，幾何学的変換iiImage Inpainting
Considering Geometric Transformand Similar Pattern Position of Textures∗
Ryo Miyamoto

Abstract
Image inpainting techniques have been widely used to remove undesired objects
in images such as damaged portions of photographs and people who have accidentally entered pictures. Conventionally, the missing or undesired parts of an image
are completed by minimizing an energy function which is deﬁned based on pattern similarity SSD (Sum of Squared Diﬀerences). Moreover, the SSD has been
extended by considering brightness changes of textures. However, the conventional method still may generate unnatural textures due to the limited available
samples in an image. In addition, exhaustive search for similar patterns using
the SSD criterion which is sensitive to pattern changes causes high computational cost and inappropriate pattern correspondences which result in generating
blurs for missing regions. In this thesis, in order to improve the image qualityof the completed texture, the conventional energy function is newly extended byconsidering not only brightness changes but also geometric transform of textures
to increase available samples. Moreover, in searching for similar patterns, thepositional relationship between adjacent texture patterns in an image is used todecrease the computational cost and prevent the inappropriate correspondences.
∗

Master’s Thesis, Department of Information Systems, Graduate School of Information
Science, Nara Institute of Science and Technology, NAIST-IS-MT0951124, February 3, 2011.

iii

In experiments, the eﬀectiveness of the proposed method is successfully demonstrated by applying our method to various images and comparing the results withthose obtained by the conventional methods.

Keywords:
image inpainting, image completion, energy minimization, geometric transformiv

目次
1. はじめに

1

2. 画像修復に関する従来研究および本研究の位置付けと方針

4

2.1

2.2

画像修復に関する従来研究 . . . . . . . . . . . . . . . . . . . . . .

4

2.1.1

欠損領域周辺の画素の輝度値を利用する画像修復 . . . . .

4

2.1.2

データ領域全体の情報を利用する画像修復 . . . . . . . . .

6

本研究の位置付けと方針 . . . . . . . . . . . . . . . . . . . . . . .

12

3. テクスチャの幾何学的変換と類似パターン位置を考慮したエネルギー最小化による画像修復

14

3.1

画像修復手法の概要. . . . . . . . . . . . . . . . . . . . . . . . .

14

3.2

パターン類似度 SSD によるエネルギー関数の定義 . . . . . . . . .

14

3.3

テクスチャの幾何学的変換を許容したエネルギー関数の拡張 . . .

17

3.4

エネルギー最小化 . . . . . . . . . . . . . . . . . . . . . . . . . . .

18

3.4.1

欠損領域外の画素に対する類似パターン位置の探索 . . . .

19

3.4.2

欠損領域内の各画素に対する類似パターン位置の探索 . . .

20

3.4.3

欠損領域内の画素値に対する並列的な更新 . . . . . . . . .

21

粗密法による局所解の回避と処理の高速化 . . . . . . . . . . . . .

23

3.5
4. 実験

25

4.1

提案手法による画像修復の具体例 . . . . . . . . . . . . . . . . . .

29

4.2

被験者による主観的評価実験と考察 . . . . . . . . . . . . . . . . .

32

4.2.1

評価方法 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

4.2.2

評価結果と考察 . . . . . . . . . . . . . . . . . . . . . . . .

32

提案手法と従来手法の間に有意差がある画像に対する考察 . . . .

38

4.3

5. まとめ

44

謝辞

45

v

参考文献

46

vi

図目次
1

Telea ら [10] の手法を用いた画像修復の例 . . . . . . . . . . . . .

62

天野ら [25] の手法を用いた画像修復の例 . . . . . . . . . . . . . .

83

Xu ら [36] の手法を用いた画像修復の例 . . . . . . . . . . . . . . .

94Kawai ら [43] の手法を用いた画像修復の例 . . . . . . . . . . . . .

10

5Orii ら [44] の手法を用いた画像修復の例 . . . . . . . . . . . . . .

116

画像修復の処理の流れ . . . . . . . . . . . . . . . . . . . . . . . .

157

画像上の各領域 . . . . . . . . . . . . . . . . . . . . . . . . . . . .

16

8

領域 Ψ 内の画素に対する類似パターン位置の探索 . . . . . . . . .

199

欠損領域内の各画素に対する類似パターン位置の探索方法 . . . .

20

10エネルギー算出における画素の関係 . . . . . . . . . . . . . . . . .

21

11

粗密法による画像修復の反復処理 . . . . . . . . . . . . . . . . . .

2412

実験で用いた入力画像 (1/3) . . . . . . . . . . . . . . . . . . . . .

26

13

実験で用いた入力画像 (2/3) . . . . . . . . . . . . . . . . . . . . .

2714

実験で用いた入力画像 (3/3) . . . . . . . . . . . . . . . . . . . . .

28

15

提案手法による修復におけるエネルギーと反復回数の関係 (画像番号:99) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1629

粗密法の各段階における初期画像とエネルギー収束後の画像 (画像番号 99) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

30

17エネルギーの推移と画像修復過程 (画像番号 99) . . . . . . . . . .

31

18

アンケート評価のための事前説明ページ . . . . . . . . . . . . . .

33

19

修復結果の採点ページ . . . . . . . . . . . . . . . . . . . . . . . .

34

20

Criminisi ら [32] の手法が他手法よりも平均点が高く有意差がある
画像 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

36

21

Wexler ら [42] の手法が他手法よりも平均点が高く有意差がある画像 36

22

Kawai ら [43] の手法が他手法よりも平均点が高く有意差がある画像 3723

提案手法が他手法よりも平均点が高く有意差がある画像 . . . . . .

24

提案手法が従来手法に対して有意差があると認められた画像 A(94)の比較 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

37
40

25

提案手法が従来手法に対して有意差があると認められた画像 B(99)の比較 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2641

従来手法が提案手法に対して有意差があると認められた画像 C(07)の比較 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

42

表目次
1

本実験での各種パラメータの設定 . . . . . . . . . . . . . . . . . .

25

2

100 枚の画像に対する点数の平均点 . . . . . . . . . . . . . . . . .

35

3

各手法が他の 3 手法より平均点が高くかつ有意差が認められた画像の枚数 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

35

4

画像 A〜C の平均点 . . . . . . . . . . . . . . . . . . . . . . . . . .

385

従来手法と提案手法による処理時間の比較 . . . . . . . . . . . . .

39

viii

1. はじめにインターネットの普及に伴い，個人が日常的に撮影した写真や映像をホームページやブログに掲載することが一般的に行われている．このような目的で，過去に撮影済みのアナログ写真をスキャナなどで電子化する際，アナログ写真の物
理的な損傷（キズ，よごれ等）によりそのままでの利用が難しい場合がある．また，デジタル写真や映像においては，利用意図に沿わない物体などが写っている
ため，そのままでは利用しづらい場合も起こりうる．このような問題に対して，
写真についた傷や意図せず写りこんでしまった物体などの画像内の不要部分を取り除き，取り除かれた領域（以下，欠損領域）を自動的に違和感なく修復することで画像の利用価値を高める画像修復に関する研究が盛んに行われている．
これら画像修復の手法は，欠損領域周辺の画素の輝度値を利用する手法と欠損領域以外の領域全体 (以下，データ領域) の情報を利用する手法に大別できる．前者のアプローチとして，輝度値の連続性を考慮して欠損領域の周りから輝度値を滑らかに補間する手法が古くから用いられてきた [1–21]．これらの手法は，画素の輝度値を欠損領域の境界から内側へ徐々に伝播させることで，写真に付いた引っかき傷のような細い領域に対しては良好な修復画像を得ることができる．しかし，大きな領域を修復した場合には細かいテクスチャが表現できず，不鮮明な画像が生成されるという問題がある．このような問題を解決するために，近年では，後者のアプローチを用いた以下のような手法が多数提案されている．

• 特徴空間を用いる手法 [22–26]• テクスチャを逐次合成する手法 [27–39]• テクスチャを全体で最適化する手法 [40–44]
これらデータ領域の情報を用いる手法は，欠損領域とデータ領域のパターン類似度に基づいてデータ領域のテクスチャを欠損領域内に再現することで画像修復を行うため，細かいテクスチャを表現することが可能である．
特徴空間を用いる手法では，欠損領域を含む一つのウインドウ内に必ずデータ領域を含まなければならないという原理的な制約から，一つのウインドウに収ま1

らないような大きな欠損領域を持つ画像に対しては適用が難しい．これに対して，
テクスチャの輝度値を用いる手法では，欠損領域が比較的大きい場合にも，細かいテクスチャを欠損領域内部に再現できる．しかし，テクスチャを逐次合成する
手法では，テクスチャを欠損領域の境界から内側に逐次的に合成するというアプ
ローチを採るため，最終的に生成される画像の品質がテクスチャの合成順に大きく依存し，不連続なテクスチャが生じやすいという問題がある．これに対して，
テクスチャを欠損領域全体で最適化し修復する手法は，結果がテクスチャの合成
順に依存せずに，欠損領域全体に対して最適な画像を生成できる．しかし，画像
内に存在するテクスチャパターンに限りがあるため，違和感のない修復に必要なパターンが画像内に存在しないことが多い．また，パターンの変形に比較的弱い

SSD による評価尺度を用いて画像全体に対して類似パターンの探索を行うため，計算コストが大きく，かつ不適切なパターンの対応を招き，修復画像がぼけてしまうという問題がある．
本論文では，このような問題を解決するために，テクスチャの全体最適化による手法 [42, 43] を基礎とし，データ領域と欠損領域の間の明度変化と幾何学的な変換を許容したパターン類似度によるエネルギー関数を新たに定義する．しかし，この明度変化と幾何学的な変換を許容する際には，探索空間のパラメータ追加に
より計算量が大きく増加する．この計算量を抑えるために，エネルギー関数の最小化において，画像内で近接するパターン間の位置関係を利用した探索を用いる
ことで，高速かつ高品位に画像修復を行うアプローチを採る．明度変化と幾何学的な変換を許容したパターン類似度を用いることで，修復に必要なパターンの不足により生じるテクスチャの明度と幾何学的な構造の不自然な変化を抑止する．
また，画像内で近接するパターン間の位置関係を利用した探索範囲の限定により，計算コストを削減し，かつ不適切なパターンの対応付けによるぼけの発生を抑制
する．
以降，2 章では，画像修復に関する従来研究と本研究の位置づけについて述べる．3 章では，明度変化と幾何学的な変換を考慮したエネルギー関数を，画像内で類似しているパターン間の位置関係を利用して最小化することで画像修復を行う手法を提案する．4 章では，様々な特徴を持つ画像に対して欠損領域の修復を2

行い，従来手法との比較および主観的評価実験を行うことで，提案手法の有効性を示す．最後に 5 章で，本論文のまとめと今後の課題について述べる．

3

2. 画像修復に関する従来研究および本研究の位置付けと方針
現在，キズやよごれ等が入ってしまった写真，映画のフィルム，壁画等の修復
は，主に専門の技師によって手作業で行われている．しかし，大量の写真や映像の修復を行うためには多くの労力がかかってしまうため，専門の技師によって行われてきた画像修復を自動化するための手法の開発が近年盛んになりつつある．本章では，このような画像修復の自動化に関する従来研究を概観し，最後に本研究の位置づけについて述べる．なお，修復領域の自動的な検出に関する研究 [45–48]も近年盛んに行われているが，本研究では欠損領域の修復にのみ着目し，修復領
域はあらかじめ与えられるものとする．

2.1 画像修復に関する従来研究
画像修復に関する従来手法は，欠損領域周辺の画素の輝度値を利用する手法とデータ領域全体の情報を利用する手法に大別できる．また，後者の手法は，欠損領域とデータ領域のパターン間での類似度の指標として，テクスチャの輝度値を用いる手法と特徴空間上の距離を用いる手法に大別できる．どの手法も現在までに多くの研究がなされているが，どのような画像に対しても良好な結果を出力する手法は無いと言える．そこで，以下では，欠損領域周辺の画素の輝度値を利用する手法とデータ領域全体の情報を利用する手法についてそれぞれ順に特徴と問題点を述べる．

2.1.1 欠損領域周辺の画素の輝度値を利用する画像修復
欠損領域周辺の画素の輝度値を利用する画像修復は，欠損領域内に欠損領域の境界部分の輝度値が滑らかに続くことで違和感のない画像が生成されるという考
え方に基づき，欠損領域内の画素値を周辺から補間することで欠損領域の修復を行う [1–21]．このようなアプローチにおいて，多くの手法はエッジを保存することに着目し修復を行っている．

4前田ら [1] は，欠損領域の境界部にエッジが存在する場合には，エッジの方向を保つよう連続的に欠損領域内部へエッジを延ばし，エッジがない場合には周りの画素値の平均値をとることで欠損領域の修復を行う手法を提案した．この手法
では欠損領域の境界部分から内側へ逐次的に画素を埋めていくため比較的大きな
欠損領域ではエッジがつながらないという問題がある．また，Masnou ら [2] は，欠損領域に到達する複数のエッジをあらかじめ自動的に対応させ，エッジを直線的に結ぶことで修復を行っているが，欠損領域境界でのエッジが複雑な場合にはエッジを正しく対応付けることが難しく，また直線的に結ぶため曲線的なエッジが欠損領域に続く画像では違和感が生じる．また，Oliveira ら [3] は，欠損領域の画素を適切な重み付けをした近傍の画素の加重平均値で補間するという処理を繰り返すことで修復を行う手法を提案した．Hadhoud ら [4] はこの手法を改良し，加重平均値で補間する画素の位置を変えることにより高速で，かつエッジを保存できる修復手法を提案した．しかし，これらの手法はエッジがぼけやすいという問題がある．これらの手法に対して，以下のような基準を用いて反復処理でエッジを滑らかに接続することで画像修復する手法が提案されている．

• 偏微分方程式 (Partial Diﬀerential Equation) を用いる手法 [5–12]• 総変動 (Total Variation) を用いる手法 [13–15]• 弾性方程式を用いる手法 [16]• マンフォード・シャー関数を用いる手法 [17]• 確率モデルを用いる手法 [18–20]• オプティカルフローを用いる手法 [21]これらの手法を用いることで，輝度値の連続性とエッジのつながりを考慮することができ，引っかき傷やテロップのような小さな欠損領域に対しては図 1 に示す
ように良好な修復画像を得ることができる．しかし，原理的に細かいテクスチャを表現することができず，大きな領域を修復した場合には不鮮明な画像が生成されるという問題がある．

5

(a) 原画像(b) 黒い線を取り除いた修復画像

図 1 Telea ら [10] の手法を用いた画像修復の例

2.1.2 データ領域全体の情報を利用する画像修復
データ領域全体の情報を利用する画像修復は，欠損領域とデータ領域間のパターン類似度に基づいてデータ領域のテクスチャを欠損領域に合成することで画像修復を行う．このような手法にはフーリエ空間，ウェーブレット空間，固有空間等の特徴空間上の距離を類似度の指標として用いる手法と，テクスチャの輝度値をパターン類似度の指標として用いる手法がある．

[特徴空間上の距離を類似度の指標として用いる手法]
特徴空間上の距離を類似度の指標として用いる手法は，欠損領域を含む一定範囲の領域に対して特徴量を算出し，その領域での特徴量と最も近いデータ領域上の特徴ベクトルを利用することで欠損領域を補間する手法である．このような手法では，特徴量として周波数ベクトルや，画像から得られる固有ベクトルが従来用いられてきた．
周波数ベクトルを用いる手法として，東海林 [22] は，データ領域のフーリエ振幅ベクトル情報を利用することで欠損領域を修復する手法を提案した．この手法
は，テクスチャ画像のフーリエ振幅スペクトルの位置不変性を仮定することで欠損領域を修復するため，周期的なテクスチャパターンを持つ画像では良好な結果を得られるが，そうでない場合は良好な結果を得ることが難しい．また，Hirani

6

ら [23] は，空間領域と周波数領域の両方を用いて欠損領域を修復する手法を提案している．この手法ではユーザが修復に用いる領域を手動で指定する必要があり，欠損領域の周りで多様なテクスチャを持つ場合には修復が難しい．
これらの手法に対して，一般的な周波数ベクトルよりも画像特有の特徴量を用いた方が良好な結果を得られるとの考えから，画像から得られる固有ベクトルを用いる修復手法が提案されている．天野らは，データ領域から学習サンプルとして複数のウインドウを切り出すことにより固有ベクトル群を生成し，生成された固有ベクトルを結合することで欠損領域の補間を行う BPLP 法 [24] および BPLP法を改良した kBPLP 法 [25] を提案している．これらの手法では，自己相関性の高い画像に対して，図 2 に示すように欠損領域内に細かいテクスチャを再現し違
和感の少ない修復を行うことができる．また，文献 [24] ではフーリエ基底を用いた結果との比較を行い，固有ベクトルを用いることの有効性を示している．井添ら [26] は，画像のフラクタル性と局所性に着目し，画像から生成した固有ベクトルを用いて修復を行う FID 法を提案している．この手法も，天野らの手法と同様にデータ領域のテクスチャを用いて生成した固有ベクトルから修復を行うため，欠損領域内の細かいテクスチャを再現することが可能である．
このように，特徴空間での補間による修復手法は欠損領域内に細かいテクス
チャを再現することが可能である．しかし，修復には欠損領域周辺の特徴量を用いるため，画像中に欠損領域を含むウインドウをあてはめた時，そのウインドウ
内に必ずデータ領域を含まなければならないという原理的な制約がある．そのため，一つのウインドウに収まらないような大きな欠損領域を持つ画像に対しては適用が難しい．

[テクスチャの輝度値を類似度の指標として用いる手法]
テクスチャの輝度値を類似度の指標として用いる手法は，テクスチャを逐次的に合成する手法とテクスチャを欠損領域全体で最適化する手法に大別できる．

• テクスチャの逐次的合成による画像修復
テクスチャの逐次的合成による手法は，データ領域から欠損領域の境界のテクスチャパターンと類似する部分を探索し，最も類似したテクスチャ

7

(a) 原画像(b) テロップを取り除いた修復画像

図 2 天野ら [25] の手法を用いた画像修復の例を逐次的に合成する手法であり，図 3 に示すように，大きな欠損領域に対しても細かいテクスチャを表現した修復が可能である．
このアプローチによる画像修復は，一枚の小さなテクスチャから大きな
新しいテクスチャを生成するというテクスチャ合成に関する研究に関連が深い．Efros ら [27] は，テクスチャ合成の分野で用いられてきたテクスチャの合成手法を画像修復に対して適用した．また，Bertalmio ら [28] は，この手法を応用し，輝度値を滑らかに補間する手法 [5] とテクスチャ合成の手法 [27] を組み合わせた手法を提案している．これらの手法は，欠損領域の境界部分から欠損領域内部へと逐次的に合成を行い，一度合成された画素
値は書き換えないという方針から，短時間で修復が完了する反面，生成される画像の品質が画像の合成順序に大きく依存し，テクスチャの不連続が起こりやすい．そのため，より違和感の少ない画像を生成可能なテクスチャの合成順の決定方法に関して，以下のような様々な基準を用いた手法が提案されてきた [29–36]．

– テクスチャの類似度 [29]– inverse matte [30]
– 決定済みの画素数 [31]8(a) 原画像(b) 前景 (象) を取り除いた修復画像

図 3 Xu ら [36] の手法を用いた画像修復の例– 決定済みの画素数とエッジの強さ [32–34]– 決定済みの画素数とエッジの強さと類似度 [35]– テクスチャの希少度 [36]しかし，これらの手法においても，やはり欠損領域の外部で複雑なパターン構造を持つ画像に対しては，不連続なテクスチャが生じやすいという問
題がある．
これに対して，エッジ部分のつながりをあらかじめ自動的または手動で指定し，優先的にテクスチャを合成することでこの問題を回避する手法 [37–39]も提案されている．しかし，テクスチャが複雑な場合には，修復に有効なエッジを正しく推定することが難しい．

• テクスチャの全体最適化による画像修復
テクスチャを逐次的に合成する手法は，不連続なテクスチャが生じやすいという問題があるため，テクスチャを欠損領域全体で最適化することでこれを解決する手法 [40–44] が提案されている．画像全体で最適化を行う手法では，修復結果がテクスチャの合成順に依存せず，不連続なテクスチャが生成されにくい特徴がある．

Komodakis ら [40] は，Belief Propagation を応用した Priority-BP を用い
9

(a) 原画像(b) 前景 (人物・バイク) を取り除いた修復画像

図 4 Kawai ら [43] の手法を用いた画像修復の例て目的関数を最適化し，欠損領域にラベル付けをすることで不連続なテク
スチャを生じさせないような最適なテクスチャの合成順を決定する手法を提案した．また，Allene ら [41] は，欠損領域を様々な形の断片に分割し，最適となるテクスチャの組み合わせで合成を行う手法を提案した．この手法
では，定義した目的関数が最適となるようデータ領域のテクスチャを張り合わせることで，欠損領域全体で不連続なテクスチャの少ない最適な画像を生成できる．また，Wexler ら [42] は，欠損領域と欠損領域以外のパター
ン類似度 SSD を用いて画像の尤もらしさを表すエネルギー関数を定義し，これを欠損領域全体に対して最適となるよう各画素の値を求めることで画像を修復する手法を提案した．しかし，これまで挙げた手法は，データ領
域のテクスチャをそのまま用いて修復するため，欠損領域に適した類似物
体がデータ領域に存在したとしても類似物体の明度や見え方の変化がある
場合はその変化に対応できず，不自然なテクスチャが生成される場合がある． そのため，近年，データ領域のテクスチャを光学的，幾何学的に拡張し，修復に利用できるテクスチャパターンの種類を増やすことで，より多くの画像に対して違和感のない修復が試みられている．Kawai ら [43] は，テ10

(a) 欠損 (赤い領域) を与えた画像(b) 欠損部の修復画像

図 5 Orii ら [44] の手法を用いた画像修復の例
クスチャの明度変化を考慮したエネルギー関数を用いることで，図 4 に示
すように欠損領域の周辺で同一物体の明度に差がある場合でも，自然な明度変化を持つテクスチャを生成する手法を提案した．また，Orii ら [44] は，テクスチャの回転を考慮したエネルギー関数を用いることで，図 5 に示す
ように円状の物体の一部が欠損している場合でも，自然な幾何学的構造を持つテクスチャを生成する手法を提案した．しかし，これまで同一画像内
におけるテクスチャパターンの明度変化と幾何学的な変換の両方を考慮した手法は存在しておらず，また幾何学的な変換にも限りがあった．そのため，修復に必要なパターンの不足により，修復画像において明度や幾何学的な構造の不自然な変化が表れ違和感が生じる場合がある．また，これらの手法では画像全体に対して類似パターンの探索を行うため，計算コストが大きく，かつ不適切なパターンの対応を招くことがあり，修復画像がぼけてしまう場合がある．
このように，テクスチャの輝度値を類似度の指標として用いる手法は，大きな欠損領域に対しても細かいテクスチャを表現でき，特定の画像に対しては違和感の少ない修復が可能である．しかし，テクスチャの拡張が限定されているため，
画像によっては違和感が生じることがある．

11

2.2 本研究の位置付けと方針
前節までに概観したように，画像修復手法として既に多くの手法が提案されている．欠損領域周辺の画素の輝度値を利用する手法では，小さな欠損領域に対しては良好な結果を得られるが，細かいテクスチャを再現できない特徴から，大きな欠損領域では不鮮明な画像が生成されやすく，適用できる画像が限られる．
データ領域全体の情報を利用する手法の中で，特徴空間での補間による手法は，画像の自己相関性が強くなければならないことや，一つのウインドウにデータ領
域と欠損領域の両方を含まなければならない制約のため，適用可能な画像が比較的限定される．また，テクスチャを用いる手法において，逐次的に合成を行うア
プローチは，どのような画像に対しても良好な結果が得られるような合成順を求めることが困難である．これに対して，テクスチャを欠損領域全体で最適化するアプローチでは，細かいテクスチャを持ち，かつ不連続なテクスチャがない画像を得ることができ，現時点で最も高品位な修復画像を得ることができる．しかし，一般的に画像内には，対称性を持つ物体が多く存在し，また，カメラと物体の位置関係により類似物体のスケール等の幾何学的な構造が異なる場合がある．さらに，照明条件や汚れ等によって画像内での類似物体の明度が異なる場合がある．
そのため，欠損領域の周りで幾何学的な構造の変化や明度の変化が大きい画像に対して修復を行った際には，そのままのテクスチャを用いて修復をすると，明度や幾何学的な構造の不自然な変化が見られ違和感が生じる．また，従来手法では画像全体で欠損領域とデータ領域間の類似パターンを探索しているため，計算コ
ストが大きく，かつ不適切なパターンの対応を招き，修復画像がぼけてしまうという問題が残っている．
本論文では，テクスチャの全体最適化による画像修復手法における上記の問題
に対して，テクスチャの明度変化と幾何学的変換の両方を考慮することで，不連
続・不明瞭なテクスチャの生じにくい画像修復を実現する手法を提案する．本研
究では，テクスチャを欠損領域全体で最適化する Wexler らの手法 [42] を基礎に，明度変化と幾何学的変換を許容したパターン類似度を用いることで，明度と幾何学的な構造の不自然な変化を抑止し，違和感を軽減する．しかし，この明度変化と幾何学的な変換を許容する際には，探索空間のパラメータ追加により計算量が12大きく増加する．この計算量を抑えるために，類似パターンの探索において，画像内で近接するパターン間の相対的な位置関係を利用し，探索範囲を限定する．
これによって，計算コストを削減しつつ，不適切なパターンの対応付けによるぼけの発生を抑制する．

13

3. テクスチャの幾何学的変換と類似パターン位置を考慮したエネルギー最小化による画像修復
3.1 画像修復手法の概要
本論文では，従来からあるパターン類似度 SSD によるエネルギー関数を，明度変化と幾何学的な変換を考慮することで拡張し，そのエネルギー関数を画像内で近接するパターン間の位置関係を利用して最小化することで画像修復を行う．提案手法の流れを図 6 に示す．本研究では，まず写真上の傷や不要な物といった修
復したい領域を画像上で手動により指定し (a)，指定した領域外の画素に対する類似パターンの位置を探索する (b)．次に，何らかの方法を用いて欠損領域に初期値となる画素値を与え (c)，欠損領域内の各画素に対する類似パターン位置の探索 (d-I) と画素値の更新 (d-II) を繰り返し行いエネルギー関数を最小化することで，欠損領域の修復を行う．
以下，3.2 節で従来から用いられてきたパターン類似度 SSD によるエネルギー関数の定義について概説し，3.3 節で今回新たに用いるエネルギー関数を定義する．また，3.4 節で提案するエネルギー関数の最小化手法について述べ，最後に，

3.5 節で処理全体で用いる粗密法による局所解の回避と処理の高速化について述
べる．

3.2 パターン類似度 SSD によるエネルギー関数の定義
本節では，Wexler ら [42] が提案したパターン類似度 SSD によるエネルギー関数について概説する．パターン類似度を用いた画像修復手法では，図 7 に示すよ
うに，画像をユーザが指定した欠損領域 Ω を含む領域 Ω′ と，画像内の Ω′ 以外のデータ領域 Φ に分け，領域 Ω′ 内の画像の尤もらしさをデータ領域 Φ 内の画像パ
ターンを用いて定義する．ここでは，画像内において一定サイズの正方ウインド
ウ W 内に一部でも Ω が含まれるウインドウの中心画素の集合を Ω′ とし，欠損領域の尤もらしさに基づくエネルギーを，領域 Ω′ 内の画素 xi とデータ領域 Φ 内の14

1枚の画像を入力(a)対象領域（欠損領域）の指定(b)欠損領域外の画素に対する類似パターン位置の探索(c)欠損領域の初期値の設定(d-I)欠損領域内の各画素に対する類似パターン位置の探索(d-II)欠損領域内の画素値の更新
エネルギーが収束したか
はい
1枚の画像を出力

図 6 画像修復の処理の流れ

15

いいえ

データ領域

ウインドウ

ウインドウ
欠損領域

図 7 画像上の各領域
画素 xj 周辺のパターン類似度 SSD の重み付き総和として以下のように定義する．

Eorg =∑

wxi SSD(xi , xj )(1)

xi ∈Ω′

ただし，SSD(xi , xj ) は以下のように表される．

SSD(xi , xj ) =∑{I(xi + p) − I(xj + p)}2

(2)

p∈W

ここで，I(xi ) は画素 xi の画素値を表す．また，ここでは重み wxi として，領域Ω′ ∩ Ω では各画素の値が固定値となるため wxi = 1 を，領域 Ω では境界に近いほど画素値の信頼度が高くなるため wxi = c−d (d は Ω の境界から画素 xi までの距離，c は定数) を用いる．Wexler らの手法 [42] では，定義したエネルギー関数

Eorg を最小化する欠損領域内の画素値 I(xi ) とそれに対応する類似パターン位置
xj を算出することで，欠損領域を修復する．

16

3.3 テクスチャの幾何学的変換を許容したエネルギー関数の拡張
本研究では，式 (1) による欠損領域の尤もらしさに基づくエネルギー関数 Eorg
を，明度変化と幾何学的変換を考慮して拡張する．具体的には，画像パターンの幾何学的な変換を許容するために座標変換行列を導入する．また，明度変化を許容するために文献 [43] で提案された輝度補正係数を利用することで，エネルギーを新たに次のように定義する．

E=∑

wxi SSD′ (xi , xj , Txi xj )(3)xi ∈Ω′

ここで，SSD′ (xi , xj , Txi xj ) は明度変化と幾何学的な変換を許容したパターン類
似度であり，以下のように定義する．

SSD′ (xi , xj , Txi xj ) =∑{}2
I(xi + p) − αxi xj I(xj + Txi xj p)

(4)

p∈W

ただし，αxi xj はデータ領域のテクスチャの明度変化を許容するための輝度補正係数，Txi xj はデータ領域のテクスチャの幾何学的変換を許容するための座標変換行列を表す．以下，輝度補正係数 αxi xj と座標変換行列 Txi xj について詳述する．
輝度補正係数 αxi xj は，xi , xj それぞれの画素の周辺の平均輝度値の比を用いて算出する．これにより，データ領域のテクスチャの明度を欠損領域のテクスチャの明度に合わせる．ただし，実際の画像において比較的大きな明度変化を定数倍の変化として近似すると，違和感のある画像が生成されやすいことから，式 (5)に示す一定範囲内 (1 − D ≤ αxi xj ≤ 1 + D，ただし D は 0 < D < 1 の定数) に限
定する．

ただし，




1 − D
αxi xj = βxi xj1 + D(βxi xj < 1 − D のとき)
(1 − D ≤ βxi xj ≤ 1 + D のとき)

(5)(βxi xj > 1 + D のとき)√∑

βxi xj = √∑2q∈W I(xi + q)

2q∈W I(xj + q)

17

(6)

幾何学的な変換として，被写体の対称性を利用するためにミラーリングを，カメラでの撮影時における透視投影効果等により生じるスケールの変化に対応するためにスケーリングを許容する．具体的には，座標変換行列 Txi xj を以下のように定義する．

(Txi xj =

aij

0

0

bij

)
(7)

ただし，|aij | = |bij | とする．
提案するエネルギー関数のパラメータは，欠損領域 Ω 内の画素値 I(xi )，領域′

Ω の画素に対応するデータ領域内の画素の位置 xj ，及びテクスチャの幾何学的変換パラメータ aij , bij である．

3.4 エネルギー最小化
本研究では，Greedy Algorithm の枠組みを用いて式 (3) で定義したエネルギー

E を最小化する．具体的には，類似パターンの位置を固定した時，輝度補正係数
α の変化が欠損領域内の画素値の変化に対して微小であると仮定すると，エネル
ギー E を欠損領域 Ω 内の各画素で独立に扱えることに着目し，(d-I) 領域 Ω′ 内の各画素に対する類似パターン位置の探索 (画素値を固定)(d-II) 欠損領域 Ω 内の画素値の並列的な更新 (類似パターンの位置を固定)
をエネルギーが収束するまで繰り返すことで，画像全体のエネルギーを最小化す
る．しかし，テクスチャの幾何学的変換を許容した類似パターンの探索は計算コ
ストが大きく，また様々な幾何学的変換を施したテクスチャの組み合わせにより，不自然なテクスチャが生成される場合が起こりうる．そこで，本研究では，欠損領域の周辺に存在するパターンに類似したデータ領域内のパターンと，その近傍に存在するパターンの相対的な位置関係を，欠損領域内に再現するよう，類似パ
ターンの探索範囲およびテクスチャの変換パラメータを限定することで，高速化及び不自然なテクスチャの生成の抑制を図る．具体的には，処理 (d-I)，(d-II) の前処理として，処理 (b) で，図 8 におけるデータ領域 Φ のうち領域 Ω′ と接する画

18

最類似
ウインドウ

図 8 領域 Ψ 内の画素に対する類似パターン位置の探索

素の集合領域を Ψ とし，領域 Ψ 内の画素に対する類似パターン位置の探索と幾何学的な変換のパラメータの算出を行い，かつ領域 Ω′ 内の画素と領域 Ψ 内の画
素との対応関係を決めておき，これらの情報を処理 (d-I) で利用する．以下では，
処理 (b)，(d-I)，(d-II) の詳細について順に述べる．

3.4.1 欠損領域外の画素に対する類似パターン位置の探索
処理 (b) では，処理 (d-I) における領域 Ω′ 内の各画素に対する類似パターン位
置の探索範囲と幾何学的変換パラメータを限定するための前処理を行う．ここでは，図 8 に示すように，領域 Ω′ 内の xi と画像上の距離が最も近い領域 Ψ 内の画
素を x̃i として対応付ける．次に，画素 x̃i に対して SSD′ (x̃i , xj , Tx̃i xj ) が最小となるパターン位置 f (x̃i ) = xj ，及び座標変換行列 g(Tx̃i f (x̃i ) ) = Tx̃i xj を算出する．
具体的には，データ領域 Φ 内の全画素を対象に，幾何学的変換パラメータ aij , bij
を離散的に変えながら SSD′ を算出し，SSD′ が最小となる位置および幾何学的

19

最類似
ウインドウ

図 9 欠損領域内の各画素に対する類似パターン位置の探索方法

変換パラメータを f (x̃i )，g(Tx̃i f (x̃i ) ) とする．

3.4.2 欠損領域内の各画素に対する類似パターン位置の探索
処理 (d-I) では，欠損領域内の全画素値を固定し，領域 Ω′ 内の画素 xi に対応する類似パターン位置を，処理 (b) において求めた領域 Ψ 内の画素に対する類似パ
ターン位置とテクスチャの変換パラメータを利用して探索する．ここでは，図 9に示すように，xi と x̃i の位置関係，算出された x̃i の類似パターン位置 f (x̃i ) と座標変換行列 g(Tx̃i f (x̃i ) ) をそれぞれ利用し，位置 f (x̃i ) − g(Tx̃i f (x̃i ) )(x̃i − xi ) を中心とし，一辺が A |xi − x̃i | の正方形 (A は正の定数) を画素 xi に対する類似パ
ターン位置の探索範囲とする．この範囲内において，座標変換行列 g(Tx̃i f (x̃i ) ) を用いた SSD′ (xi , xj , g(Tx̃i f (x̃i ) )) が最小となる f (xi ) = xj を求める．このように，予め求めた領域 Ψ 内の画素に対する類似パターン位置と座標変換行列を利用する
ことにより，欠損領域内の画素に対する類似パターン探索時の座標変換行列と探

20

最類似
ウインドウ

図 10 エネルギー算出における画素の関係

索範囲を限定することで，幾何学的変換を行ったテクスチャの連続性を保存し，かつ計算コストを削減する．

3.4.3 欠損領域内の画素値に対する並列的な更新
処理 (d-II) では，処理 (d-I) で更新された類似パターンの位置を利用し，式 (3)で定義したエネルギー E を最小化するよう，欠損領域 Ω 内の画素値 I(xi ) を画素並列に更新する．以下では，パターンの組を固定した場合の画素値 I(xi ) の算出
手法について詳述する．ここではまず，エネルギー E を，欠損領域内の各画素での要素エネルギー E(xi ) に分解する．図 10 に示すように，更新対象となる画素の位置を xi ，xi を中心とするウインドウ W 内の任意の点を xi + p (p ∈ W ) とする．このとき，画素 xi + p を中心とするパターンに対する類似パターンの位
置は f (xi + p) であり，この類似パターン上において xi と対応する画素の位置は

f (xi + p) − g(T(xi +p)f (xi +p) )p となる．ここで，注目画素 xi に関係する E の要素

21

エネルギー E(xi ) は，xi と f (xi + p) − g(T(xi +p)f (xi +p) )p の画素値の関係，それぞれの画素の周りの平均輝度値，xi と f (xi ) 位置の関係から算出でき，以下のよ
うに表すことができる．

E(xi ) =∑w(xi +p) {I(xi )−α(xi +p)f (xi +p) I(f (xi +p)−g(T(xi +p)f (xi +p) )p)}2 (8)p∈W

このとき，欠損領域全体のエネルギー E と各画素での要素エネルギー E(xi ) の関
係は，以下のように表せる．

E=∑

E(xi ) + C

(9)

xi ∈Ω

C は，領域 Ω′ ∩ Ω 内にある画素に関するエネルギーであり，処理 (d-II) では類似
パターン位置が固定されているため定数として扱える．ここで，要素エネルギーE(xi ) の変数は I(xi ) であるため，E を欠損領域内のある画素の画素値 I(xi ) で偏微分すれば，エネルギー E を最小化する I(xi ) の必要条件は次式で表せる．

∑ ∂E(xk )∂E==0∂I(xi ) x ∈Ω ∂I(xi )

(10)

k

このとき，画素値 I(xi ) の変化に対する輝度値補正係数 α の変化は微小であると仮定し，∂αxk f (xk )= 0(∀xk ∈ Ω′ )∂I(xi )

(11)とおけば，∂E(xk )/∂I(xi ) = 0(i ̸= k) となり，式 (10) は以下のように表せる．

∂E∂E(xi )==0
∂I(xi )
∂I(xi )

(12)

従って，式 (8)，(12) より，E を最小化する画素 I(xi ) は以下のように算出できる．
∑
p∈W w(xi +p) α(xi +p)f (xi +p) I(f (xi + p) − g(T(xi +p)f (xi +p) )p)∑I(xi ) =(13)p∈W w(xi +p)
なお，式 (13) は式 (11) を前提とした近似解であるが，I(xi ) が収束するに従って輝度値の補正係数 α の値も収束するため，エネルギーが収束するにつれて良い近似解となる．

22

3.5 粗密法による局所解の回避と処理の高速化
本研究では，Greedy Algorithm の枠組みを用いているため，局所解問題が存在する．ここでは効率的に大域最適解に近い解を得るために，図 11 左に示すように，初めは原画像を縮小した画像に対してエネルギー最小化処理を行い，その結果を初期値として順次解像度を高くしながらエネルギーを最小化する多重スケー
ル処理を採用する．具体的には，一定スケールまで画像サイズを 2 分の 1 ずつ縮小した画像ピラミッドを作成しておき，まず最小となるスケールで 3.4 節で述べた手法によりエネルギー最小化処理を行う．あるスケールでエネルギーが収束すると，上位層での最類似パターン位置の結果を下位層での初期値として投影する．
これらの処理を元の画像サイズになるまで同じ大きさのウインドウを用いて繰り返す．このような処理を行うことで大域最適解に近い解を得ることができ，また，
各スケールでの初期値があらかじめエネルギーの低いテクスチャを用いることができるため処理の高速化にもつながる．
また，本研究では細部までテクスチャを再現するために，図 11 右に示すように，元のサイズの画像に対しては，ウインドウサイズを順次小さくしながらエネ
ルギー最小化処理を行う．このような処理を行うことで，データ領域のテクスチャのサンプル数が増えるため，より細かいテクスチャも再現することができ，ぼけの発生を防ぐことができる．

23

・・・

大

スケール1/4
ウ
イ
ン
ド
ウ
サ
イ
ズ

スケール1/2

小図 11 粗密法による画像修復の反復処理

24

4. 実験
本章では，図 12∼14 に示す様々な特徴を持つ 100 枚の画像 (200×200 画素) を対象とした画像修復実験を通じて，提案手法の有効性を明らかにする．ここではまず，提案手法による画像修復の具体例を示し，提案手法のふるまいと効果を説明する．また，100 枚全ての修復結果に対するアンケート評価に基づく被験者実
験を行うことで，提案手法の有効性を判定する．アンケート評価の結果をもとに，提案手法による修復結果と従来手法による修復結果を比較し，統計的に有意差があると認められた画像について考察する．なお，本実験では，PC (CPU:Xeon

3.2GHz メモリ:8GB) を用いて修復処理を行い，エネルギー関数の各種パラメー
タは表 1 に示すように設定した．また，欠損領域は，原画像の一部を塗りつぶすことにより手動で与え (図 12∼14 中の赤い領域)，欠損領域の初期値は欠損領域の境界画素の輝度値の平均値とした．粗密法による処理では，データ領域のサンプ
ル数が全画素数の 1%以上となる最小のスケールから開始し，元のサイズの画像に対してはウインドウサイズを 9×9 から 7×7 までウインドウの辺の長さを 2 画
素ずつ減少させた．また，収束判定は，1 反復におけるエネルギーの減少幅がエ
ネルギーの大きさの 0.01%以下となる場合とした．なお，提案手法における幾何学的変換は，水平方向と垂直方向のミラーリングと，アスペクト比固定のスケーリングとした．ただし，スケーリングについては，処理中のウインドウの辺の長さを ±4 画素ずつ増減させたパターンを処理中のウインドウサイズにスケーリン
グして (例：ウインドウサイズが 9×9 の時は，5×5，13×13 のパターンを 9×9 にスケーリングして) 対応した．

表 1 本実験での各種パラメータの設定
ウインドウサイズW

9×9

輝度補正係数 α に関する範囲

D

0.1

提案手法における探索範囲に用いる係数

A2

画素の重み wxi に用いる定数

c

1.3

25

00

01

02

03

04

05

06

07

08

09

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

図 12 実験で用いた入力画像 (1/3)

26

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

図 13 実験で用いた入力画像 (2/3)

27

70

71

72

73

74

75

76

77

78

79

80

81

82

83

84

85

86

87

88

89

90

91

92

93

94

95

96

97

98

99

図 14 実験で用いた入力画像 (3/3)

28

1

エネルギー

0.9
スケール1/8, W 9x9

0.8

スケール1/4, W 9x9
スケール1/2, W 9x9

0.7

スケール1, W 9x9
スケール1, W 7x7

0.6
0.5
0

2

4

6

8

10 12 14 16 18 20

反復回数
図 15 提案手法による修復におけるエネルギーと反復回数の関係 (画像番号:99)

4.1 提案手法による画像修復の具体例
本節では，提案手法による画像修復の具体例として，対称性を持つ建物を含む
画像 (画像番号:99) の修復過程を示す．図 15 に各スケール，ウインドウサイズにおける画像処理時のエネルギーの変化と反復回数の関係を示す．なお，各スケー
ル，ウインドウサイズでの初期エネルギーを 1 に正規化している．図 15 から，式(11) による近似を用いてもエネルギーは単調に減少していることが確認できる．
また，各スケール，ウインドウサイズにおける初期画像とエネルギー収束後の画像を図 16 に，原寸スケールでウインドウサイズが 9×9 のときの，エネルギーの推移と画像修復過程を図 17 に示す．図 16 から，上位層での結果を下位層での初期値として利用することで，あらかじめエネルギーの低いテクスチャを用いることができていることが確認できる．また，提案手法において新たに考慮した水平方向のミラーリングによる対応付けにより，建物の対称性を利用し，違和感の少ない画像が生成できている．図 17 から，初期画像の左上部に違和感のあるテクスチャが存在していたが反復処理により，空が再現され違和感の少ない画像が生成されていることが確認できる．

29

スケール

ウインドウ
サイズ

1/8

9x9

1/4

9x9

1/2

9x9

1

9x9

1

7x7

初期画像

エネルギー
収束後の画像図 16 粗密法の各段階における初期画像とエネルギー収束後の画像 (画像番号 99)

30

1.05

エネルギー

1
0.95
0.9
0.85
0.8
0.75
0

2

4

6

8

10

12

反復回数

図 17 エネルギーの推移と画像修復過程 (画像番号 99)

31

4.2 被験者による主観的評価実験と考察
本節では，テクスチャの逐次的合成による代表的な修復手法である Criminisi
らの手法 [32]，全体最適化による修復手法である Wexler らの手法 [42]，Wexler
らの手法を明度変化を考慮して拡張した Kawai らの手法 [43] を実装し，提案手
法と従来手法を用いた修復画像に対して 31 名 (本学の学生) の被験者による評価実験を行った．本実験は，被験者により修復画像を主観的に評価してもらうこと
で，提案手法の有効性を客観的に示すことを目的とする．

4.2.1 評価方法
被験者には，アンケート評価のためのウェブページにアクセスしてもらい，図18 に示す事前説明を読んでもらった後，図 19 に示すようなレイアウトで並べられた 100 枚の入力画像に対する 400 枚の修復画像に対して 5 段階の点数評価を行ってもらった．なお，本実験で画像修復に用いた手法は，テクスチャの逐次的合成
による手法 [32]，テクスチャの全体最適化による手法 [42]，明度変化を考慮したテクスチャの全体最適化による手法 [43]，提案手法を用いた場合の 4 つであり，修復結果の採点ページ上では，4 つの手法により修復した結果画像をランダムな順序で並べた．また，本実験では，修復画像を個人のホームページや書籍・雑誌等の写真として利用することを前提として，使えない画像を 1 点，十分使える画像を 5 点という解答基準で採点してもらった．

4.2.2 評価結果と考察
各手法により出力された各々100 枚の修復結果につけられた点数の平均値を表2 に示す．評価結果に対して，有意水準を 5%と設定した t 検定により，提案手法と Criminisi らの手法 [32]，Wexler らの手法 [42]，Kawai らの手法 [43] のそれぞれ比較を行った結果，Criminisi らの手法に対しては有意差が認められ，Wexler
らの手法と Kawai らの手法に対しては有意傾向が認められたことから，平均的に提案手法が最も違和感が少ない画像を生成できる手法だと言える．また，各手法が他の 3 手法よりも平均点が高くかつ有意差が認められた画像の枚数の比較を表32

図 18 アンケート評価のための事前説明ページ

33

図 19 修復結果の採点ページ34

3 に示し，それらの画像を手法ごとに分類したものを図 20〜図 23 に示す．結果
から，類似したテクスチャを逐次的に合成する Criminisi らの手法は，川原の画
像 (画像番号:98) のように欠損領域周辺において高周波なパターンを持つ画像に対して有効であるといえる．これに対して，テクスチャの全体最適化を利用した

Wexler らの手法，Kawai らの手法，提案手法は，高周波なパターンを持つ画像においては様々な箇所のテクスチャが混ざりぼけやすいが，合成順序に依存しない
ため平均的には違和感の少ない画像を生成できるといえる．Wexler らの手法に対して，Kawai らの手法では明度変化を，提案手法では明度変化と幾何学的変換を許容しているため，それぞれ欠損領域付近で明るさの変化や幾何学的な構造の変化がある場合に有効であるといえる結果であった．しかし，欠損領域付近で幾何学的な構造の変化がある場合においても 3 つの従来手法がすべて提案手法よりも平均点が高くかつ有意差があると認められた画像もあるため，次節では，提案手法と 3 つの従来手法すべての間に有意差がある画像に対する考察をする．
表 2 100 枚の画像に対する点数の平均点
手法

平均点

テクスチャの逐次的合成による手法 [32]2.17

テクスチャの全体最適化による手法 [42]3.08

明度変化を考慮した手法 [43]

3.09

提案手法

3.19

表 3 各手法が他の 3 手法より平均点が高くかつ有意差が認められた画像の枚数
手法

枚数

テクスチャの逐次的合成による手法 [32]9

テクスチャの全体最適化による手法 [42]12

明度変化を考慮した手法 [43]

9

提案手法

13

35

07

23

66

33

85

53

89

55

98

図 20 Criminisi ら [32] の手法が他手法よりも平均点が高く有意差がある画像

06

16

22

25

26

34

36

43

59

68

78

88

図 21 Wexler ら [42] の手法が他手法よりも平均点が高く有意差がある画像

36

24

29

61

32

70

47

73

56

87

図 22 Kawai ら [43] の手法が他手法よりも平均点が高く有意差がある画像

00

04

09

11

13

65

71

72

77

80

90

94

99

図 23 提案手法が他手法よりも平均点が高く有意差がある画像

37

4.3 提案手法と従来手法の間に有意差がある画像に対する考察
本節では，欠損領域付近で幾何学的な構造の変化があり，また 4.2 節のアンケー
ト評価において，提案手法と 3 つの従来手法すべての間に有意差があると認められた図 24(a) から図 26(a) に示す 3 枚の画像について実験結果を示し，考察する．
図 24(a)，25(a) に示す画像 A(画像番号 94)，画像 B(画像番号 99) については，提案手法がどの従来手法よりも平均点が高く有意差があると認められ，図 26(a) に示す画像 C(画像番号 07) については，3 つの従来手法すべてが提案手法よりも平均点が高く有意差があると認められた画像である．画像 A〜C に対しての各手法の平均点を表 4 に示す．また，各図 (a) に欠損領域を指定した画像，(b) にテクス
チャを逐次的に合成する Criminisi らの手法 [32] による修復画像，(c) に 3.2 節で述べたパターン類似度 SSD をエネルギーとした Wexler らの手法 [42] による修復
画像，(d) に明度変化を考慮したパターン類似度をエネルギーとした Kawai らの手法 [43] による修復画像，(e) に提案手法を適用した修復画像を示す．以下，画
像 A〜C に関して考察する．
画像 A(図 24) は，提案手法が従来手法に対して有意差があると認められ，透視投影効果により画像上部に向かってパターンが徐々に小さくなっている構造をもつ画像である．Criminisi らの手法では，合成順序の影響からテクスチャの構造が極端に変化しており違和感が生じている．また，Wexler らの手法と Kawai らの手法では，適切な大きさのテクスチャと対応付けられないためぼけが生じる，あ
るいはテクスチャの大きさが極端に変化している．これに対して，提案手法では

表 4 画像 A〜C の平均点
手法

画像 A

画像 B

画像 C

テクスチャの逐次的合成による手法 [32]

2.23

1.06

3.22

テクスチャの全体最適化による手法 [42]

2.16

1.32

2.38

明度変化を考慮した手法 [43]

2.13

1.45

2.41

提案手法

2.65

3.77

1.84

38

テクスチャパターンのスケーリングを許容しているので，テクスチャのスケールの大きさが極端に変化することなく欠損領域が修復されているため，評価が高くなったと考えられる．
画像 B(図 25) は，提案手法が従来手法に対して有意差があると認められ，対称性を持つ物体を含む画像である．従来手法では，画像中のテクスチャをそのまま利用するため，修復に適切な構造を持つテクスチャが存在せず違和感が生じている．これに対して，提案手法ではテクスチャパターンのミラーリングを許容しているので，水平方向のミラーリングを利用したテクスチャにより，比較的違和感の少ない画像が生成できているため，評価が高くなったと考えられる．
画像 C(図 26) は，どの従来手法も提案手法に対して有意差があると認められた画像である．Criminisi らの手法では，欠損していた窓のエッジを再現できている．Wexler らの手法と，Kawai らの手法では，窓の部分においてはぼけが生じているが，画像の左中央部付近に存在する水平な白い線状のテクスチャの連続性が保たれている．これらに対して，提案手法では窓の部分と画像の左中央部付近の水平な白い線状のテクスチャどちらも途中で途切れている．これは提案手法の特徴から，欠損領域の内部になるほど様々な箇所のテクスチャが混ざりやすく，そのため適切なテクスチャが再現されずぼけが生じてしまい，評価が低くなったと考えられる．
次に，処理時間の比較を行った．従来手法 [42, 43] と提案手法による処理時間
を表 5 に示す．表 5 から提案手法では Wexler らの手法に対して 3〜7 倍程度の処理時間が必要であることが分かる．また，Kawai らの手法に対しては 0.6〜1.6 倍程度の処理時間が必要である．これは，提案手法において幾何学的な変換として

表 5 従来手法と提案手法による処理時間の比較

Wexler ら [42]Kawai ら [43]

提案手法 (処理 (b)+処理 (d))

画像 A

8分2秒

41 分 46 秒

23 分 15 秒 (7 分 45 秒+15 分 30 秒)

画像 B

9 分 48 秒

28 分 17 秒

44 分 24 秒 (14 分 4 秒+30 分 20 秒)

画像 C

1 分 54 秒

12 分 31 秒

9 分 58 秒 (4 分 1 秒+5 分 57 秒)

39

(a) 欠損領域を指定した画像(b) Criminisi らの手法 [32] による結果画像(c) Wexler らの手法 [42] による結果画像(d) Kawai らの手法 [43] による結果画像(e) 提案手法による結果画像

図 24 提案手法が従来手法に対して有意差があると認められた画像 A(94) の比較

40

(a) 欠損領域を指定した画像(b) Criminisi らの手法 [32] による結果画像(c) Wexler らの手法 [42] による結果画像(d) Kawai らの手法 [43] による結果画像(e) 提案手法による結果画像

図 25 提案手法が従来手法に対して有意差があると認められた画像 B(99) の比較

41

(a) 欠損領域を指定した画像(b) Criminisi らの手法 [32] による結果画像(c) Wexler らの手法 [42] による結果画像(d) Kawai らの手法 [43] による結果画像(e) 提案手法による結果画像

図 26 従来手法が提案手法に対して有意差があると認められた画像 C(07) の比較

42

ミラーリングとスケーリングを考慮したことで，計算コストが増えたことによる．
ただし，提案手法の処理時間は，処理 (b) と処理 (d) に分けることができ，処理(d) だけに注目すれば Kawai らの手法とほぼ同等，あるいはそれ以下の処理時間となることが分かる．処理 (b) では，欠損領域内の画素と対応付けられた欠損領域の境界付近の画素のみの探索を行っているにも関わらず処理時間の三分の一程度を占めている．これは，幾何学的変換パラメータを離散的に変えながらデータ
領域全体を探索していることが原因となっているため，処理 (b) における探索を改良することで，さらなる計算コストの削減が可能になると考えられる．

43

5. まとめ
本論文では，従来から提案されているパターン類似度 SSD による画像修復手法を基礎に，テクスチャの明度変化と幾何学的な変換を考慮したエネルギー関数
を新たに定義し，これを画像内で近接するパターン間の位置関係を利用した探索を用いて最小化することで，高品位に修復画像を生成する手法を提案した．

31 名の被験者による主観評価実験の結果，透視投影効果や対称性のある画像に対して，提案手法が従来手法より有効であることを示した．また，画像内で近接するパターン間の位置関係を利用した探索により，幾何学的変換による計算コストの増加を抑止し，かつ不適切なパターンの対応によるぼけの発生を抑制できることを示した．しかし，ウインドウサイズやエネルギー関数中での重みなど，経験的に決定したパラメータが多く，パラメータの変化により結果画像が大きく異なる場合がある．
今後，更に多くの画像に対して良好な結果を得るためには，画像の特徴から良好な結果画像を得るための最適なパラメータの決定手法や局所解を回避するための初期値の設定手法を確立する必要がある．また，回転や水平方向と垂直方向で異なる比率のスケーリング等より多くの幾何学的な変換を考慮する場合は，特徴量を用いた探索を利用することで，幾何学的な変換のパラメータの取り得る範囲の限定が可能となり，より効率的な探索ができると考えられる．また，繰り返し処理の中でエネルギーが収束してくる段階になると，類似パターン位置が固定されてくるため，それらの画素の再探索を省くことでさらなる高速化が期待できる．

44

謝辞
本研究の全過程を通して，懇切なる御指導，御鞭撻を賜りました視覚情報メディア講座 横矢直和 教授に心より感謝致します．また，本研究の遂行にあたり，有益な御助言，御鞭撻を頂いた像情報処理学講座 千原國宏 教授に厚く御礼申し上げます．そして，本研究を進めるにあたり，始終暖かい御指導をして頂いた視覚
情報メディア講座 山澤一誠 准教授に深く感謝致します．さらに，本研究を通じて，的確な御助言，御鞭撻を頂いた環境知能学講座 神原誠之 准教授に深く御礼申し上げます．また，本研究を行うにあたり，多大なる御助言，御鞭撻を賜った
視覚情報メディア講座 佐藤智和 助教に心より感謝致します．特に，山澤一誠 准教授には本研究のテーマ設定から本論文の執筆，その他の発表論文の添削，発表
練習に至るまで細やかな御指導を頂きました．さらに，本研究の遂行にあたり，貴重な御助言や御指摘を頂きましたカリフォルニア大学バークレー校 河合紀彦
氏に深く感謝いたします．また，研究室での生活を支えていただいた視覚情報メディア講座事務補佐員 中村美奈 女史に厚く御礼申し上げます．最後に，研究活
動だけでなく日々の生活においても大変お世話になった視覚情報メディア講座の諸氏に心より感謝致します．

45

参考文献
[1] 前田, 高橋, 太田: “欠損画像の修復処理の一方式”, 電子情報通信学会論文誌
D, Vol. J69-D, No. 1, pp. 91–97, 1986.
[2] S. Masnou and J. Morel: “Level lines based disocclusion,” Proc. IEEE Int.
Conf. on Image Processing, pp. 259–263, 1998.
[3] M. Oliveira, B. Bowen, R. McKenna and Y. Chang: “Fast digital image inpainting,” Proc. Int. Conf. on Visualization, Imaging and Image Processing,pp. 261–266, 2001.
[4] M. Hadhoud, K. Moustafa and S. Shenoda: “Digital images inpainting using modiﬁed convolution based method,” Int. Journal of Signal Processing,Image Processing and Pattern recognition, Vol. 1, No. 1, pp. 1–10, 2008.
[5] M. Bertalmio, G. Sapiro, V. Caselles and C. Ballester: “Image inpainting,”
Proc. ACM SIGGRAPH2000, pp. 417–424, 2000.
[6] M. Bertalmio, A. Bertozzi and G. Sapiro: “Navier-stokes, ﬂuid dynamics,
and image and video inpainting,” Proc. IEEE Conf. on Computer Vision
and Pattern Recognition, pp. 355–362, 2001.
[7] C. Ballester, M. Bertalmio, V. Sapiro and J. Verdera: “Filling-in by joint
interpolation of vector ﬁelds and gray levels,” IEEE Trans. on Image Processing, Vol. 10, No. 8, pp. 1200–1211, 2001.
[8] C. Ballester, V. Caselles, J. Verdera, M. Bertalmio and G. Sapiro: “A variational model for ﬁlling-in gray level and color images,” Proc. IEEE Int. Conf.
on Computer Vision, pp. 10–16, 2001.
[9] C. Barcelos, M. Batista, A. Martins and A. Nogueira: “Level lines continuation based digital inpainting,” Proc. IEEE Brazilian Symposium on
Computer Graphics and Image Processing, pp. 50–57, 2004.
46

[10] A. Telea: “An image inpainting technique based on the fast marching
method,” Journal of Graphics Tools, Vol. 9, No. 1, pp. 25–36, 2004.
[11] D. Tschumperlé: “Curvature-preserving regularization of multi-valued images usingpde’s,” Proc. European Conf. on Computer Vision, pp. 295–307,
2006.
[12] F. Bornemann and T. Marz: “Fast image inpainting based on coherencetransport,” Journal of Math Imaging and Vision, pp. 259–278, 2007.
[13] T. Chan and J. Shen: “Mathematical models for local non-texture inpaintings,” SIAM Journal of Applied Mathematics, Vol. 62, No. 3, pp. 1019–1043,
2001.
[14] T. Chan and J. Shen: “Non-texture inpainting by curvature-driven diﬀusions(CDD),” Journal of Visual Communication and Image Representation, Vol.
12, No. 4, pp. 436–449, 2001.
[15] C. Fei, W. Mei-qing and L. Choi-Hong: “An algorithm for total variation
inpainting based on nonlinear multi-grid methods,” Journal of Algorithms
and Computational Technology, Vol. 2, No. 1, pp. 15–33, 2007.
[16] T. Chan, S. Kang, J. Shen and S. Osher: “Euler’s elastica and curvature
based inpaintings,” SIAM Journal of Applied Mathematics, Vol. 63, No. 2,
pp. 564–592, 2002.
[17] S. Esedoglu and J. Shen: “Digital inpainting based on the mumford-shaheuler image model,” SIAM Journal of Applied Mathematics, Vol. 13, pp. 353–
370, 2003.
[18] A. Levin, A. Zomet and Y. Weiss: “Learning how to inpaint from global
image statistics,” Proc. IEEE Int. Conf. on Computer Vision, pp. 305–312,
2003.

47

[19] E. Villéger, G. Aubert and L. Blanc-Féraud: “Image disocclusion using aprobabilistic gradient orientation,” Proc. IAPR Int. Conf. on Pattern Recognition, pp. 52–55, 2004.
[20] 安田, 大久保, 田中: “ガウシアングラフィカルモデルを用いた画像補修アルゴ
リズム”, 情報科学技術フォーラム (FIT) 情報技術レターズ, Vol. 5, pp. 225–

228, 2006.
[21] 小川, 長谷山, 北島: “オプティカルフローを用いた静止画像における失われた輝度値の復元”, 電子情報通信学会論文誌 D-II, Vol. J87-D-II, No. 9, pp. 1786–

1795, 2004.
[22] 東海林: “テクスチャ画像における欠損部修復の一手法”, 電子情報通信学会
論文誌 D, Vol. J71-D, No. 9, pp. 1701–1708, 1988.

[23] A. Hirani and T. Totsuka: “Combining frequency and spatial domain
information for fast interactive image noise removal,” Proc. ACM SIGGRAPH1996, pp. 269–276, 1996.
[24] 天野, 佐藤: “固有空間法を用いた BPLP による画像補間”, 電子情報通信学
会誌 D-II, Vol. J85-D-II, No. 3, pp. 457–465, 2002.

[25] 天野, 佐藤: “kBPLP 法を用いた高次元非線形射影による画像補間”, 電子情報通信学会誌 D-II, Vol. J86-D-II, No. 4, pp. 525–534, 2003.

[26] 井添, 剣持, 小谷: “画像のフラクタル性に基づいたカーネル主成分分析による遮へい領域の原画像推定”, 電子情報通信学会 技術研究報告, PRMU2001-106,

pp. 55–62, 2001.
[27] A. Efros and T. Leung: “Texture synthesis by non-parametric sampling,”
Proc. IEEE Int. Conf. on Computer Vision, pp. 1033–1038, 1999.
[28] M. Bertalmio, L. Vese, G. Sapiro and S. Osher: “Simultaneous structure andtexture image inpainting,” IEEE Trans. on Image Processing, Vol. 12, No.
8, pp. 882–889, 2003.
48

[29] P. Harrison: “A non-hierarchical procedure for re-synthesis of complex textures,” Proc. Int. Conf. in Central Europe Computer Graphics, Visualization
and Computer Vision, pp. 190–197, 2001.
[30] I. Drori, D. Cohen-Or and H. Yeshurun: “Fragment-based image completion,” Proc. ACM SIGGRAPH2003, pp. 303–312, 2003.
[31] R. Bornard, E. Lecan, L. Laborelli and J. Chenot: “Missing data correction
in still images and image sequences,” Proc. ACM Int. Conf. on Multimedia,
pp. 355–361, 2002.
[32] A. Criminisi, P. Pérez and K. Toyama: “Region ﬁlling and object removal by
exemplar-based image inpainting,” IEEE Trans. on Image Processing, Vol.
13, No. 9, pp. 1200–1212, 2004.
[33] W.-H. Cheng, C.-W. Hsieh, S.-K. Lin, C.-W. Wang and J.-L. Wu: “Robustalgorithm for exemplar-based image inpainting,” Proc. Int. Conf. Computer
Graphics, Imaging and Visualization, pp. 64–69, 2005.
[34] S. Vetter, M. Grzegorzek and D. Paulus: “Wavelet-based inpainting for object removal from image series,” Annual Symposium of the German Association for Pattern Recognition, pp. 343–352, 2010.
[35] B. Li, Y. Qi and X. Shen: “An image inpainting method,” Proc. IEEE Int.
Conf. on Computer Aided Design and Computer Graphics, pp. 531–536,
2005.
[36] Z. Xu and J. Sun: “Image inpainting by patch propagation using patch
sparsity,” IEEE Trans. on Image Processing, Vol. 19, No. 5, pp. 1153–1165,
2010.
[37] J. Jia and C. Tang: “Image repairing: Robust image synthesis by adaptive nd tensor voting,” Proc. IEEE Conf. on Computer Vision and Patern
Recognition, pp. 643–650, 2003.
49

[38] J. Sun, L. Yuan, J. Jia and H. Shum: “Image completion with structure
propagation,” Proc. ACM SIGGRAPH2005, pp. 861–868, 2005.
[39] 柴田, 池谷, 仙田: “確率的構造予測に基づく高速な画像修復”, 画像の認識・理解シンポジウム, pp. 754–761, 2010.

[40] N. Komodakis and G. Tziritas: “Image completion using global optimization,” Proc. IEEE Conf. on Computer Vision and Pattern Recognition,
pp. 442–452, 2006.
[41] C. Allène and N. Paragios: “Image renaissance using discrete optimization,”
Proc. IAPR Int. Conf. on Pattern Recognition, pp. 631–634, 2006.
[42] Y. Wexler, E. Shechtman and M. Irani: “Space-time completion of video,”
IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol. 29, No. 3,
pp. 463–476, 2007.
[43] N. Kawai, T. Sato and N. Yokoya: “Image inpainting considering brightnesschange and spatial locality of textures and its evaluation,” Proc. Paciﬁc-Rim
Symp. on Image and Video Technology, pp. 271–282, 2009.
[44] H. Orii, H. Kawano, H. Maeda and N. Ikoma: “Image completion with generation of rotated patterns and eﬃcient matching,” Proc. IEEE Int. Symposium on Circuits and Systems, pp. 3190–3193, 2009.
[45] 鈴木, 玉木, 山本: “画像復元のための周期的な遮へい物体の抽出”, 電子情報通信学会誌 D-II, Vol. J87-D-II, No. 5, pp. 1189–1192, 2004.

[46] R. Chang, Y. Sie, S. Chou and T. Shih: “Photo defect detection for image
inpainting,” Proc. IEEE Int. Symposium on Multimedia, pp. 403–407, 2005.
[47] T. Amano: “Correlation based image defect detection,” Proc. IAPR Int.
Conf. on Pattern Recognition, pp. 163–166, 2006.

50

[48] T. Tamaki and H. Suzuki: “String-like occluding region extraction for background restoration,” Proc. IAPR Int. Conf. on Pattern Recognition, pp. 615–
618, 2006.

51