線画像の原画検索方法
【課題】手書きなどの大幅な変換に対しても有効となる線画の複製検出手法を提供する。
【解決手段】検索質問の線画からその局所的な特徴を表す複数の局所領域を決定する領域決定工程、決定された各局所領域の特徴に応じた特徴ベクトル（クエリ特徴ベクトル）を抽出する特徴抽出工程、各検索質問特徴ベクトルを原画データーベースに登録された特徴ベクトル（原画特徴ベクトル）と照合し、各クエリ特徴ベクトルにつき近傍の原画特徴ベクトルをそれぞれ決定する照合工程、前記検索質問に近い特徴を持つ線画が前記原画データーベースに登録されているか否かを決定し、その線画を特定する工程を備え、前記領域決定工程は画像の明暗変化および濃淡変化に対する耐性を有し、かつ所定量の線成分を内包するような各局所領域を対象の線画からそれぞれ抽出し、前記特徴抽出工程は線画が幾何的変換を受けた場合に耐性を有するような各特徴ベクトルをそれぞれ抽出する。
【解決手段】検索質問の線画からその局所的な特徴を表す複数の局所領域を決定する領域決定工程、決定された各局所領域の特徴に応じた特徴ベクトル（クエリ特徴ベクトル）を抽出する特徴抽出工程、各検索質問特徴ベクトルを原画データーベースに登録された特徴ベクトル（原画特徴ベクトル）と照合し、各クエリ特徴ベクトルにつき近傍の原画特徴ベクトルをそれぞれ決定する照合工程、前記検索質問に近い特徴を持つ線画が前記原画データーベースに登録されているか否かを決定し、その線画を特定する工程を備え、前記領域決定工程は画像の明暗変化および濃淡変化に対する耐性を有し、かつ所定量の線成分を内包するような各局所領域を対象の線画からそれぞれ抽出し、前記特徴抽出工程は線画が幾何的変換を受けた場合に耐性を有するような各特徴ベクトルをそれぞれ抽出する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、線画像の原画検索方法に関し、より詳細には、局所特徴量の照合により線画の部分的複製を検出する手法に関する。
【背景技術】
【０００２】
近年、インターネットの普及に伴い、音声、画像、動画などの大容量のデータが大量に流通し、パソコンの高機能化により誰でも個人規模でデジタルコンテンツ を扱えるようになっている。しかし、技術の発展は便利な反面、新たな問題を生んでいる。その中でもコンテンツの不正コピーによる著作権の侵害が社会的な問題となっている。この問題を解決するため、不正コピーを自動的に検出する技術が求められている。
【０００３】
著作権を保護すべきコンテンツとしては様々なものが考えられるが、その中でも図面や漫画などの線画は重要なものの一つである。線画は、濃淡のない直線又は曲線だけで描く図形であり、単色が基本となる。線画の不正利用者は、オリジナルをそのまま使うことは希であり、オリジナルの一部分（部分的複製）を、自分の線画の一部として使うことが多い。また、漫画などで部分的複製を作成する場合には、オリジナルの切り抜きをそのまま使うのではなく、手書きで複製するなどの改変を伴う場合が考えられる。それ故に、印刷の複製だけではなく、手書きの複製も考えなければならない。
このような問題に対処するため、コンテンツの著作権保護の技術として、これまでにいくつかの技術が提案されている。
【０００４】
その一つは電子透かしという技術である。電子透かしは、対象とするコンテンツに著作権の情報を埋め込む技術である。カラー画像のような冗長性の高いコンテンツについては、人間に知覚できないように著作権情報を埋め込むことができる。この中には、幾何学的な変換に対する耐性を持つ手法もある。例えば、Basらは、画像の特徴点をマーカとして利用し、幾何学的な変換に対する不変な電子透かしを提案している（例えば、非特許文献１参照）。しかし、電子透かしの手法を線画に適用することは困難である。これは、画像に比べて線画は冗長性の少ないコンテンツであり、人間に知覚できないような埋め込みが困難なためである。
【０００５】
もう一つの技術は画像検索に基づく複製検出である。この技術では、著作権保護の対象となるコンテンツをデーターベースに保持しておき、疑わしい画像を検索質問（クエリ）として検索することにより、複製を検出する。特に画像については、各種変換や部分的複製に対して安定である局所特徴量と呼ばれるものがよく用いられる。この中で、SIFT(Scale-Invariant Feature Transform)は最も良く知られた局所特徴量であり、多くの研究者により画像検索への有効性が示されている（例えば、非特許文献２参照）。また、Keらは、SIFTを改良したPCA-SIFT(Principal Component Analysis SIFT)を用い、ある程度改変された画像を手がかりに、そのオリジナルが検出できることを示している（例えば、非特許文献３，４参照）。しかしながら、これらの方法が線画、特に手書きなどの変換を伴うものに対しても有効かどうかは検証されていない。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】P. Bas, J-M Chassery, and B. Macq, "Geometrically invariant watermarking using feature points", IEEE Trans. Antennas Propag., Vol.11, No.9, pp.1014-1028, 2002.
【非特許文献２】D. G. Lowe, "Distinctive image features from scale-invariant key-points", Int. J. Comput. Vis. 60(2), pp.91-110, 2004.
【非特許文献３】Y. Ke, R.Sukthankar, and L. Hustion, "Efficient near-duplicate detection and sub-image retrieval", MM, pp. 869-876, 2004.
【非特許文献４】Y. Ke and R. Sukthankar, "PCA-SIFT: A more distinctive representation for local image descriptors", Proc. CVPR, Vol. 2, pp.506-513, 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
そこでこの発明では、局所特徴量を用いるという方針のもと、印刷や画像スキャンなどの軽微な変換だけではなく、手書きなどの大幅な変換に対しても有効となる線画の複製検出手法を提供する。
【課題を解決するための手段】
【０００８】
この発明は、検索質問の線画に近い特徴を持つ線画が、複製から保護されるべき原画が登録されてなる原画データーベース中に登録されているか否かを決定すべく、前記検索質問の線画からその局所的な特徴を表す複数の局所領域を決定する領域決定工程と、決定された各局所領域の特徴に応じた特徴ベクトル（クエリ特徴ベクトル）をそれぞれ抽出する特徴抽出工程と、各検索質問特徴ベクトルを、前記原画データーベースに登録された各原画について予め抽出された複数の特徴ベクトル（原画特徴ベクトル）とそれぞれ照合し、各クエリ特徴ベクトルにつき近傍の原画特徴ベクトルをそれぞれ決定する照合工程と、近傍の各原画特徴ベクトルに基づいて、前記検索質問に近い特徴を持つ線画が前記原画データーベースに登録されているか否かを決定しかつ登録されている場合はその線画を特定する工程とを備え、前記領域決定工程は、画像の明暗の変化および濃淡の変化に対する耐性を有し、かつ、所定量の線成分を内包するような各局所領域を対象の線画からそれぞれ抽出し、前記特徴抽出工程は、線画が幾何的変換を受けた場合に耐性を有するような各特徴ベクトルをそれぞれ抽出し、各工程をコンピュータが実行することを特徴とする線画像の原画検索方法を提供する。
【発明の効果】
【０００９】
この発明による原画検索方法において、前記領域決定工程は、画像の明暗の変化および濃淡の変化に対する耐性を有し、かつ、所定量の線成分を内包するような各局所領域を対象の線画からそれぞれ抽出し、前記特徴抽出工程は、線画が幾何的変換を受けた場合に耐性を有するような各特徴ベクトルをそれぞれ抽出するので、印刷線画の印刷および手書きによる部分的複製を高い精度で検出できるばかりでなく、複雑な背景に埋め込まれた手書き線画も高精度の検出が可能である。
【００１０】
後述する実施形態では、局所領域の決定手法としてMSER (Maximally Stable Extremal Region)を、局所領域の記述子としてHOG (Histogram of Oriented Gradients)を用いた。なお、MSERの詳細については、次の文献、J. Matas, O. Chum, M. Urban and T. Pajdla,
"Robust Wide Baseline Stereo from Maximally Stable Extremal Regions", BMVC, pp.384-393, 2002.を参照されたい。また、HOGの詳細については、次の文献、N. Dalal and B. Triggs, "Histograms of Oriented Gradients for Human Detection", IEEE CVPR, vol.1, pp.88-893, 2005.を参照されたい。
【００１１】
MSERをはじめとするこれらの手法は、もともと線画の特徴抽出を対象として開発されたものでなく、むしろ、写真画像のように比較的なだらかなコントラストの画像を取り扱うことを念頭においたものである。HOGについても、本来は画像中の人を検出するための手法であり、線画を対象に開発されたものではない。結局、局所記述子を用いることにより線画の手書きによる部分的複製が検出できるという発想が一般的なものでなく、その試みが従来はあまり行われていなかった。
【００１２】
後述する実施形態では、漫画を対象とし、部分的複製を類似の漫画中に埋め込んだものから、オリジナルを検出できるかどうかについて実験を行い、
（１）印刷とスキャンを経た部分的複製については、SIFTを用い複製検出法が極めて有効であり、この発明も同程度に有効であること、
（２）手書きによる部分的複製については、SIFTでは殆ど検出できないが、この発明ではある程度検出できること、
（３）この発明では、回転や拡大縮小を受けた部分的複製であっても検出できること
を確認した。
【００１３】
ただし、局所領域を定義、決定する手法は、MSERに限定されるものでなく、その他にもSIFT、SURF、Harris-Affine、Hessian-AffineあるいはIBR(Intensity extrema based Regions)などの手法が適用できる可能性がある。
【００１４】
また、局所領域の特徴を抽出、記述する手法は、HOGに限定されるものでなく、その他にもSIFT、PCA-SIFT、SURF、Cross Correlation、Complex Filters、GLOH、Steerable Filters、Moments、PCA-SIFT、Shape Context、Spin Image、EHOG、Edgelet等の手法が適用できる可能性がある。
ただし、単にそれらの手法を組み合わせるだけに過ぎない手法では、良好な結果が得られないことは、後述する実験でSIFTの実験結果が示すとおりである。
【図面の簡単な説明】
【００１５】
【図１】この発明に係る線画の複製について、複製の種類を示す説明図である。
【図２】この発明に係る原画の印刷による部分的複製の一例および手書きによる部分的複製の一例をそれぞれ示す説明図である。(a)は、印刷による部分的複製の例を、(b)は、手書きによる部分的複製の一例である。
【図３】この実施形態の原画検索方法の処理手順の流れの例を示す説明図である。
【図４】この実施形態の領域決定工程により、複製された線画から決定された局所領域の一例を示す説明図である。
【図５】この実施形態の領域決定工程における、局所領域の処理過程の一例を示す説明図である。
【図６】この実施形態の特徴抽出工程の処理の一例を示す説明図である。
【図７】この実施形態の実験に用いたクエリ画像を示す説明図である。
【図８】この実施形態において、印刷による部分的複製の検出実験の結果を示すグラフである。
【図９】この実施形態において、手書きよる部分的複製の検出実験の結果を示すグラフである。
【図１０】この実施形態において、背景の影響により検出が失敗した例を示す説明図である。
【発明を実施するための形態】
【００１６】
以下、この発明の好ましい態様について説明する。
前記領域決定工程は、MSER（エムエスイーアール、Maximally Stable Extremal Regions）の手法を用いて対象の線画から候補となる複数の領域を抽出する工程と、抽出された候補のうち所定面積より広い領域を拡大し、拡大された領域を局所領域とする工程とを含んでいてもよい。
【００１７】
また、前記特徴抽出工程は、HOG（ホグ、Histgram of Oriented Gradients）の手法を用いて各局所領域から特徴ベクトルを抽出するようにしてもよい。
【００１８】
さらにまた、前記照合工程は、近似最近傍探索の手法を用いて各クエリ特徴ベクトルにつき近傍の原画特徴ベクトルをそれぞれ決定し、各原画特徴ベクトルは、各原画が前記原画データーベースに登録される際にその原画に対し前記領域決定工程および前記特徴抽出工程と同様の処理を行って各原画から複数個抽出され、前記原画データーベースは、各原画とそれから抽出された原画特徴ベクトルとが対応付けられて登録されていてもよい。
ここで示した種々の好ましい態様は、それら複数を組み合わせることもできる。
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。
【００１９】
１．概要
部分的複製とはオリジナル素材の一部を切り出すことによって作成される複製である。不正な利用者はこの手法を使って盗作を行うことが多い。その際には，部分的複製は他の素材の中に埋め込まれる形で使われる。加えて，部分的複製はそのままの形で埋め込まれるとは限らず、様々な処理によって改変されることも考えられる。その結果、不正利用の検出が困難となっている。
【００２０】
以下の実施形態では、このような場合にも対処可能な著作権保護の手法の一例を詳細に説明する。対象としては、漫画のような線画を取り上げる。線画の場合、改変の手法として手書き複製が考えられるが、これが問題をより困難なものとしている。この問題に対処するため、著作権保護対象の線画に対する局所特徴量の照合を考える。具体的には、局所領域の抽出手法としてMSERを、特徴量の記述子としてHOGを用いる。実験により、この手法が印刷線画の部分的複製ばかりでなく、複雑な背景に埋め込まれた手書き線画に対しても有効性があることを示す。
【００２１】
2. タスク定義
オリジナルの複製とその利用は、図1に示す5種類に分類できる。複製(Duplicate)とは、オリジナルを改変せず直接利用する場合を指す。オリジナル全体に対して改変処理を施した複製は、オリジナルに近い複製(Near Duplicate)と呼ばれる。オリジナル全体ではなく、その一部分を用いる場合は、partial copy(部分的複製)と呼ばれる。特に、部分的複製が殆ど改変を受けていない場合（ここでは intact partial copyと呼ぶ）と改変を受けている場合（ここでは near partial copyと呼ぶ）を区別する。なお、部分的複製の場合には、他の素材を背景とし、その中に埋め込まれて使われることが多く、より問題を複雑にしている。
【００２２】
複製の検出の難易度という観点から見ると、最も容易なのはDuplicateであり、図1の下に向かうに従ってより難しくなる。特に、漫画などの線画の場合には、手書きによるnear
partial copyの可能性がある。例を図2に示す。手書きの複製では、オリジナルにある台詞の吹き出しと花が略されているとともに、個々の線についてもオリジナルと微妙な差があり、スケールも違う。この発明では、こういった場合であっても複製を検出すること、特に漫画の中に漫画の部分的複製を埋め込むといったような、複雑な背景を伴うような場合であっても検出することを目標とする。なお、図２、７および１０に示す漫画は、実験のため著作者の了解を得て提供いただいたものである。
【００２３】
3. この発明の処理手順
上に述べたそれぞれのタイプの複製を検出するには、各々に適した手法を用いるべきかもしれない。しかし、実際に利用することを考えると、全種類の不正利用を統一的に検出できる手法が望まれる。この発明は、一番難しい問題である部分的複製を検出することを意図しているが、他の種類の複製であっても検出可能であることを目指す。
【００２４】
3.1. 処理の流れ
この発明は、局所特徴量を用いて部分的複製を検出する手法である。図3に示すように、処理過程は2つの部分からなる。
データーベース処理では、著作権を保護すべき画像１３（著作権保護画像と呼ぶ）を集めて局所特徴量を抽出し、データーベース１５を作る。局所特徴量の抽出は、region detectorによる局所領域の抽出と、feature descriptorによる特徴ベクトルとしての記述からなる。画像のサイズにもよるが、一般に抽出される特徴ベクトルの数は画像あたり数百から数万と膨大になる。
【００２５】
一方、クエリ処理では、著作権侵害の可能性のある画像（被疑画像と呼ぶ）をクエリ１１としてデーターベース１５に問い合わせ処理を行う。まず、データーベース処理で用いたものと同じdetectorとdescriptorを用いて、特徴ベクトルを抽出する。それから、近似最近傍探索によって、クエリ１１の特徴ベクトルとデーターベースの特徴ベクトルを照合し、対応する著作権保護に投票を行う。その結果、得票数が最大の画像から一定数を著作権侵害の可能性として報告する。
【００２６】
線画の部分的複製を検出するため、この実施形態では、MSERを領域検出器として、HOGを特徴量記述子として用いる。マッチングの時間を短縮するため、ANN(Approximate Nearest Neighbor search、詳細は、次の文献、S. Arya, D. Mount, R. Silverman and A. Y. Wu, "An optimal algorithm for approximate nearest neighbor searching", Journal of the ACM, 45, 6, pp.891-923, 1998.参照)を用いて、最近傍の特徴ベクトルを計算する。
【００２７】
3.2. MSER
Matasらは、wide-baseline マッチングのため、MSERと呼ばれる手法を提案している。多重解像度表現を用いることによって、違う視点から得られた画像を照合している。
【００２８】
概略を以下に述べる。極値領域(Extremal region)という領域を考える。この領域は、領域内の全部の画素の明暗度は周りの画素の明暗度より高い又は小さいとして定義された領域である。この極値領域の中で、安定な面積が一番大きい領域をMSERという。この領域の共分散行列を対角化して、MSERを楕円領域に変換する。図4に抽出された楕円領域の例を示す。
【００２９】
この楕円MSERはアフィン変換と輝度変化に耐性を持っている。手書きの複製では、原画像の線の明暗と濃淡が変化するので、MSERの特性は、手書き複製から安定な領域を抽出するために重要となる。さらに、手書き複製では画像の細かい部分に多くの改変がある。そして、細かい部分から抽出した楕円のサイズは小さく、複製の識別にはあまり役に立たないため、利用する楕円のサイズを一定の大きさを持つものに限定する。また、複製の識別のためには、楕円領域内に多くの線分が含まれていることが望ましい。そこでこの発明では、楕円のサイズを一定割合(実験では6倍)だけ拡大する。それから、楕円の長軸を画像のy軸に平行となるように回転し、局所特徴領域を得る。図5に、拡大、回転されたMSERの領域の例を示す。
【００３０】
3.3. HOG
HOG (Histogram of Oriented Gradients)は、人検出のため、Dalalらによって提案された特徴量である。基本的な考え方は、局所の勾配あるいはエッジの方向の分布で、物体の見えや形状をうまく表現できるというものである。提案方法では、MSERで定義された各々の局所領域に対してHOG特徴を抽出する。図6に示すように、まず、各ピクセルの輝度から勾配強度と勾配方向を計算する。このとき、勾配方向を9方向に離散化する。そして、局所領域をセルと呼ばれる一様な小領域に分割する。次に、各セル領域において、輝度の勾配方向ヒストグラムを作成して、9次元のベクトルを得る。それから、図6に示すように、
セル間で互いに重なりを持つブロックを構成し、セルのベクトルを結合、正規化して、ブロックを表すベクトルを得る。結果として得られる特徴ベクトルは、全てのブロックのベクトルから構成される多次元ベクトルである。1つのブロックは9個のセルを含み、局所領域からは6×6個のブロックが得られるため、特徴ベクトルの次元数は9×3×3×6×6 = 2916次元である。なお、HOG特徴は局所特徴領域を均一に分割するので、スケール変換に対して不変である。
【００３１】
3.4. 照合と投票による複製検出
上記のプロセスを経て得られる特徴ベクトルは多数となるため、その照合には効率化が必要である。この実施形態では、近似最近傍探索の一手法であるANN(Approximate Nearest Neighbor)を使って、照合の高速化を図る。ANNでは、k-d木を用いてデータを記録する。探索時には、クエリとなる特徴ベクトルqを用いてk-d木を根から葉に向かって辿ることにより、暫定的な最近傍となる特徴ベクトルpを得る。qとpのユークリッド距離をrとするとき、真の最近傍はqから半径rの超球中に存在するので、その空間を探索すればよい。ANNではこのとき、近似のパラメータεを用いて縮小した半径r/(1+ε)の超球内を探索することにより、高速化を図るものである。縮小のために真の最近傍が得られないというリスクを負うものの、処理は劇的に高速化される。
【００３２】
一般に、照合の結果として得られる対応関係の中には、誤ったものも多数含まれる。誤対応を除去する簡便な方法は、距離の比を用いるものである。いま、クエリの特徴ベクトルをq、その最近傍となるデーターベース中の特徴ベクトルをp1、第2位となる特徴ベクトルをp2とするとき、
【００３３】
【数１】
となる、すなわち2位との差が顕著である場合にのみ対応するとみなす。ここで、Tは閾値である。
【００３４】
以上の処理により、被疑画像から得た各特徴ベクトルについて、対応するデーターベース中の特徴ベクトルを得ることができる。データーベース中の特徴ベクトルに対しては、どの著作権保護画像から得たものであるかが分かっている。これをその画像に対する投票と考えることにより、最大得票数を得る画像として、対応する著作権保護画像を検出することができる。ユーザにとって少数の画像を検査することはそれほど苦にならないと考えられるため、この実施形態では、得票数第R位までの画像を出力する。
【００３５】
4. 実験
4.1. 実験条件
この発明の有効性を検証するため、漫画を対象として実験を行った。
まず、データーベースに格納する著作権保護画像としては、7種類の漫画から得た1002枚の単色画像を用いた。
クエリについては、次のような手順により作成した。まず、データーベースの画像から101枚の画像を選択した。次に、各々について、約1/5程度の面積を持つ部分領域を切り出した。部分画像には、人物や顔の一部、建物や花の一部が含まれている。
【００３６】
near partial copyとしては、この部分領域を用いて次のように2種類を作成した。一つは、部分領域の画像を印刷してからスキャンして、再度、画像化することにより得られる部分的複製(以後、印刷と呼ぶ)である。もう一つは、部分領域の線画をまねて手書きで複
製し、スキャンして画像化することにより得られる部分的複製(以後、手書きと呼ぶ)である。両者とも、元の部分領域画像の3/4の大きさとなるようにスケール変動を加えた。そしてこれらの画像を、データーベースには存在しない漫画（背景）に埋め込むことによって、クエリ画像とした。背景はデーターベースに登録していない漫画からランダムに選択した。
【００３７】
クエリ画像の例を図7に示す。クエリ画像としては、背景となる漫画を持たないものに加えて、部分的複製の面積を基準として、背景の面積を2, 4, 10の3通りに変化させ、合計4通りのクエリ画像を作成した。
画像の照合では、ANNのεを10に設定した。実験に用いた計算機は、CPUがOpteron 2.4GHz、メモリが128GBのものである。
【００３８】
4.2. 実験 1
まず、上記のクエリ画像を用いて複製検出実験を行った。本実験では、この発明による処理のほか、比較手法としてSIFTを用いた複製検出法も試した。比較手法では、局所特徴量としてSIFTを用いる以外は、基本的にはこの発明による処理と同じである。距離の比の閾値Tとしては、この発明による処理で0.95、SIFTを用いる手法で0.6という値を設定した。
【００３９】
実験の結果を図8と図9に示す。横軸は得票数の順位、縦軸は累積分類率を表す。図8を見ると、印刷の複製については、SIFTはこの発明による処理を多少上回る結果を得ていることが分かる。両者に共通して言えることは以下の2点である。下位の画像まで見ることにより、累積分類率はわずかではあるが改善する。また、背景がない場合の累積分類率が最も高く、背景の面積が大きくなるにつれて精度が少しずつではあるが低下する。
【００４０】
一方、図9を見ると、手書きの複製については、SIFTは全く有効に動作しないことが分かる。これはSIFT特徴が手書きのような微妙ではあるが複雑な変動に対して非常に脆いことを意味している。これに対して、この発明による処理は、印刷の場合に比べて低下はするものの一定の累積分類率を得た。具体的には、例えば、背景のない手書きの場合で5位の累積分類率が94%、10倍の背景を伴う場合で74%という結果であった。これは、MSERとHOGの組み合わせが手書きの変動に対して有効であることを示している。
この発明による処理で検出に失敗した原因は、次の2つであった。
【００４１】
一つは、違う漫画であっても似ている部分が多いことである。テクスチャとして似た領域からは類似の特徴ベクトルが得られる。また、文字を多く含む部分領域からも類似の特徴ベクトルを得ることが多く、これが原因となり誤投票が増加した。
【００４２】
もう一つの原因は、局所性の不足によるものである。図10に示すように、クエリ画像から得られた局所領域には、背景の一部分にまたがるものがある。このような場合、データーベース中の特徴ベクトルと類似しない特徴ベクトルが得られ、誤投票につながった。
【００４３】
処理時間については、この発明による処理はSIFTを用いた場合に比べてかなり劣る結果となった。この主な理由は、特徴ベクトルの次元数の差にある。SIFTが128次元であるのに対して、HOGにより得られる特徴ベクトルは2916次元と大きな開きがある。この結果、例えば背景がない場合の処理時間は、SIFTによる手法で425ms/queryであったのに対して、この発明による処理では6013ms/queryであった。
【００４４】
4.3. 実験2
次に、この発明による処理に対して、回転とスケール変換に対する耐性を検査した。クエリ画像としては、印刷、手書きの双方について、背景のない部分的複写を用いた。具体
的には、これらを30°、45°に回転したものや、大きさを2倍(原画像の3/2倍)にしたものを用いた。
【００４５】
5位までの累積分類率を表1と表2に示す。ここで、表1の0°、表2の3/4とは、実験1と同様のクエリ画像を表す。この結果より、この発明による処理は、スケール変化や回転についても一定の耐性を持つことが分かる。また、これらの表からは、回転やスケール変化に対する耐性は、手書きの場合により得にくいことも分かる。
【００４６】
【表１】
【表２】
5. まとめ
【００４７】
この発明では、局所特徴量の照合による線画の部分的複製の検出手法を提案した。この実施形態では、MSERで抽出した領域をHOGで記述することにより、複雑な背景を伴う場合でも、印刷した線画と手書きの不正コピーを一定の精度で検出可能である。SIFTを用いた手法との比較実験により、以下のことが分かった。(1)SIFTを用いる手法は、印刷した線画に対して高い有効性がある。(2)この実施形態では、印刷した線画の検出に対して、SIFTより数%低い分類率となる。(3)SIFTを用いる手法は、手書きの線画に対して20%程度の5位分類率しか得られずほぼ無力である。(4)この実施形態では、分類率は低下するものの5位分類率で74-94%を得、一定の有効性がある。(5)この実施形態には、ある程度の回転とスケール変換に対する耐性がある。
今後の課題は、この発明における処理時間の短縮などである。
【００４８】
前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
【符号の説明】
【００４９】
１１ クエリ、被疑画像
１３ 著作権保護画像
１５ データーベース
【技術分野】
【０００１】
この発明は、線画像の原画検索方法に関し、より詳細には、局所特徴量の照合により線画の部分的複製を検出する手法に関する。
【背景技術】
【０００２】
近年、インターネットの普及に伴い、音声、画像、動画などの大容量のデータが大量に流通し、パソコンの高機能化により誰でも個人規模でデジタルコンテンツ を扱えるようになっている。しかし、技術の発展は便利な反面、新たな問題を生んでいる。その中でもコンテンツの不正コピーによる著作権の侵害が社会的な問題となっている。この問題を解決するため、不正コピーを自動的に検出する技術が求められている。
【０００３】
著作権を保護すべきコンテンツとしては様々なものが考えられるが、その中でも図面や漫画などの線画は重要なものの一つである。線画は、濃淡のない直線又は曲線だけで描く図形であり、単色が基本となる。線画の不正利用者は、オリジナルをそのまま使うことは希であり、オリジナルの一部分（部分的複製）を、自分の線画の一部として使うことが多い。また、漫画などで部分的複製を作成する場合には、オリジナルの切り抜きをそのまま使うのではなく、手書きで複製するなどの改変を伴う場合が考えられる。それ故に、印刷の複製だけではなく、手書きの複製も考えなければならない。
このような問題に対処するため、コンテンツの著作権保護の技術として、これまでにいくつかの技術が提案されている。
【０００４】
その一つは電子透かしという技術である。電子透かしは、対象とするコンテンツに著作権の情報を埋め込む技術である。カラー画像のような冗長性の高いコンテンツについては、人間に知覚できないように著作権情報を埋め込むことができる。この中には、幾何学的な変換に対する耐性を持つ手法もある。例えば、Basらは、画像の特徴点をマーカとして利用し、幾何学的な変換に対する不変な電子透かしを提案している（例えば、非特許文献１参照）。しかし、電子透かしの手法を線画に適用することは困難である。これは、画像に比べて線画は冗長性の少ないコンテンツであり、人間に知覚できないような埋め込みが困難なためである。
【０００５】
もう一つの技術は画像検索に基づく複製検出である。この技術では、著作権保護の対象となるコンテンツをデーターベースに保持しておき、疑わしい画像を検索質問（クエリ）として検索することにより、複製を検出する。特に画像については、各種変換や部分的複製に対して安定である局所特徴量と呼ばれるものがよく用いられる。この中で、SIFT(Scale-Invariant Feature Transform)は最も良く知られた局所特徴量であり、多くの研究者により画像検索への有効性が示されている（例えば、非特許文献２参照）。また、Keらは、SIFTを改良したPCA-SIFT(Principal Component Analysis SIFT)を用い、ある程度改変された画像を手がかりに、そのオリジナルが検出できることを示している（例えば、非特許文献３，４参照）。しかしながら、これらの方法が線画、特に手書きなどの変換を伴うものに対しても有効かどうかは検証されていない。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】P. Bas, J-M Chassery, and B. Macq, "Geometrically invariant watermarking using feature points", IEEE Trans. Antennas Propag., Vol.11, No.9, pp.1014-1028, 2002.
【非特許文献２】D. G. Lowe, "Distinctive image features from scale-invariant key-points", Int. J. Comput. Vis. 60(2), pp.91-110, 2004.
【非特許文献３】Y. Ke, R.Sukthankar, and L. Hustion, "Efficient near-duplicate detection and sub-image retrieval", MM, pp. 869-876, 2004.
【非特許文献４】Y. Ke and R. Sukthankar, "PCA-SIFT: A more distinctive representation for local image descriptors", Proc. CVPR, Vol. 2, pp.506-513, 2004.
【発明の概要】
【発明が解決しようとする課題】
【０００７】
そこでこの発明では、局所特徴量を用いるという方針のもと、印刷や画像スキャンなどの軽微な変換だけではなく、手書きなどの大幅な変換に対しても有効となる線画の複製検出手法を提供する。
【課題を解決するための手段】
【０００８】
この発明は、検索質問の線画に近い特徴を持つ線画が、複製から保護されるべき原画が登録されてなる原画データーベース中に登録されているか否かを決定すべく、前記検索質問の線画からその局所的な特徴を表す複数の局所領域を決定する領域決定工程と、決定された各局所領域の特徴に応じた特徴ベクトル（クエリ特徴ベクトル）をそれぞれ抽出する特徴抽出工程と、各検索質問特徴ベクトルを、前記原画データーベースに登録された各原画について予め抽出された複数の特徴ベクトル（原画特徴ベクトル）とそれぞれ照合し、各クエリ特徴ベクトルにつき近傍の原画特徴ベクトルをそれぞれ決定する照合工程と、近傍の各原画特徴ベクトルに基づいて、前記検索質問に近い特徴を持つ線画が前記原画データーベースに登録されているか否かを決定しかつ登録されている場合はその線画を特定する工程とを備え、前記領域決定工程は、画像の明暗の変化および濃淡の変化に対する耐性を有し、かつ、所定量の線成分を内包するような各局所領域を対象の線画からそれぞれ抽出し、前記特徴抽出工程は、線画が幾何的変換を受けた場合に耐性を有するような各特徴ベクトルをそれぞれ抽出し、各工程をコンピュータが実行することを特徴とする線画像の原画検索方法を提供する。
【発明の効果】
【０００９】
この発明による原画検索方法において、前記領域決定工程は、画像の明暗の変化および濃淡の変化に対する耐性を有し、かつ、所定量の線成分を内包するような各局所領域を対象の線画からそれぞれ抽出し、前記特徴抽出工程は、線画が幾何的変換を受けた場合に耐性を有するような各特徴ベクトルをそれぞれ抽出するので、印刷線画の印刷および手書きによる部分的複製を高い精度で検出できるばかりでなく、複雑な背景に埋め込まれた手書き線画も高精度の検出が可能である。
【００１０】
後述する実施形態では、局所領域の決定手法としてMSER (Maximally Stable Extremal Region)を、局所領域の記述子としてHOG (Histogram of Oriented Gradients)を用いた。なお、MSERの詳細については、次の文献、J. Matas, O. Chum, M. Urban and T. Pajdla,
"Robust Wide Baseline Stereo from Maximally Stable Extremal Regions", BMVC, pp.384-393, 2002.を参照されたい。また、HOGの詳細については、次の文献、N. Dalal and B. Triggs, "Histograms of Oriented Gradients for Human Detection", IEEE CVPR, vol.1, pp.88-893, 2005.を参照されたい。
【００１１】
MSERをはじめとするこれらの手法は、もともと線画の特徴抽出を対象として開発されたものでなく、むしろ、写真画像のように比較的なだらかなコントラストの画像を取り扱うことを念頭においたものである。HOGについても、本来は画像中の人を検出するための手法であり、線画を対象に開発されたものではない。結局、局所記述子を用いることにより線画の手書きによる部分的複製が検出できるという発想が一般的なものでなく、その試みが従来はあまり行われていなかった。
【００１２】
後述する実施形態では、漫画を対象とし、部分的複製を類似の漫画中に埋め込んだものから、オリジナルを検出できるかどうかについて実験を行い、
（１）印刷とスキャンを経た部分的複製については、SIFTを用い複製検出法が極めて有効であり、この発明も同程度に有効であること、
（２）手書きによる部分的複製については、SIFTでは殆ど検出できないが、この発明ではある程度検出できること、
（３）この発明では、回転や拡大縮小を受けた部分的複製であっても検出できること
を確認した。
【００１３】
ただし、局所領域を定義、決定する手法は、MSERに限定されるものでなく、その他にもSIFT、SURF、Harris-Affine、Hessian-AffineあるいはIBR(Intensity extrema based Regions)などの手法が適用できる可能性がある。
【００１４】
また、局所領域の特徴を抽出、記述する手法は、HOGに限定されるものでなく、その他にもSIFT、PCA-SIFT、SURF、Cross Correlation、Complex Filters、GLOH、Steerable Filters、Moments、PCA-SIFT、Shape Context、Spin Image、EHOG、Edgelet等の手法が適用できる可能性がある。
ただし、単にそれらの手法を組み合わせるだけに過ぎない手法では、良好な結果が得られないことは、後述する実験でSIFTの実験結果が示すとおりである。
【図面の簡単な説明】
【００１５】
【図１】この発明に係る線画の複製について、複製の種類を示す説明図である。
【図２】この発明に係る原画の印刷による部分的複製の一例および手書きによる部分的複製の一例をそれぞれ示す説明図である。(a)は、印刷による部分的複製の例を、(b)は、手書きによる部分的複製の一例である。
【図３】この実施形態の原画検索方法の処理手順の流れの例を示す説明図である。
【図４】この実施形態の領域決定工程により、複製された線画から決定された局所領域の一例を示す説明図である。
【図５】この実施形態の領域決定工程における、局所領域の処理過程の一例を示す説明図である。
【図６】この実施形態の特徴抽出工程の処理の一例を示す説明図である。
【図７】この実施形態の実験に用いたクエリ画像を示す説明図である。
【図８】この実施形態において、印刷による部分的複製の検出実験の結果を示すグラフである。
【図９】この実施形態において、手書きよる部分的複製の検出実験の結果を示すグラフである。
【図１０】この実施形態において、背景の影響により検出が失敗した例を示す説明図である。
【発明を実施するための形態】
【００１６】
以下、この発明の好ましい態様について説明する。
前記領域決定工程は、MSER（エムエスイーアール、Maximally Stable Extremal Regions）の手法を用いて対象の線画から候補となる複数の領域を抽出する工程と、抽出された候補のうち所定面積より広い領域を拡大し、拡大された領域を局所領域とする工程とを含んでいてもよい。
【００１７】
また、前記特徴抽出工程は、HOG（ホグ、Histgram of Oriented Gradients）の手法を用いて各局所領域から特徴ベクトルを抽出するようにしてもよい。
【００１８】
さらにまた、前記照合工程は、近似最近傍探索の手法を用いて各クエリ特徴ベクトルにつき近傍の原画特徴ベクトルをそれぞれ決定し、各原画特徴ベクトルは、各原画が前記原画データーベースに登録される際にその原画に対し前記領域決定工程および前記特徴抽出工程と同様の処理を行って各原画から複数個抽出され、前記原画データーベースは、各原画とそれから抽出された原画特徴ベクトルとが対応付けられて登録されていてもよい。
ここで示した種々の好ましい態様は、それら複数を組み合わせることもできる。
以下、図面を用いてこの発明をさらに詳述する。なお、以下の説明は、すべての点で例示であって、この発明を限定するものと解されるべきではない。
【００１９】
１．概要
部分的複製とはオリジナル素材の一部を切り出すことによって作成される複製である。不正な利用者はこの手法を使って盗作を行うことが多い。その際には，部分的複製は他の素材の中に埋め込まれる形で使われる。加えて，部分的複製はそのままの形で埋め込まれるとは限らず、様々な処理によって改変されることも考えられる。その結果、不正利用の検出が困難となっている。
【００２０】
以下の実施形態では、このような場合にも対処可能な著作権保護の手法の一例を詳細に説明する。対象としては、漫画のような線画を取り上げる。線画の場合、改変の手法として手書き複製が考えられるが、これが問題をより困難なものとしている。この問題に対処するため、著作権保護対象の線画に対する局所特徴量の照合を考える。具体的には、局所領域の抽出手法としてMSERを、特徴量の記述子としてHOGを用いる。実験により、この手法が印刷線画の部分的複製ばかりでなく、複雑な背景に埋め込まれた手書き線画に対しても有効性があることを示す。
【００２１】
2. タスク定義
オリジナルの複製とその利用は、図1に示す5種類に分類できる。複製(Duplicate)とは、オリジナルを改変せず直接利用する場合を指す。オリジナル全体に対して改変処理を施した複製は、オリジナルに近い複製(Near Duplicate)と呼ばれる。オリジナル全体ではなく、その一部分を用いる場合は、partial copy(部分的複製)と呼ばれる。特に、部分的複製が殆ど改変を受けていない場合（ここでは intact partial copyと呼ぶ）と改変を受けている場合（ここでは near partial copyと呼ぶ）を区別する。なお、部分的複製の場合には、他の素材を背景とし、その中に埋め込まれて使われることが多く、より問題を複雑にしている。
【００２２】
複製の検出の難易度という観点から見ると、最も容易なのはDuplicateであり、図1の下に向かうに従ってより難しくなる。特に、漫画などの線画の場合には、手書きによるnear
partial copyの可能性がある。例を図2に示す。手書きの複製では、オリジナルにある台詞の吹き出しと花が略されているとともに、個々の線についてもオリジナルと微妙な差があり、スケールも違う。この発明では、こういった場合であっても複製を検出すること、特に漫画の中に漫画の部分的複製を埋め込むといったような、複雑な背景を伴うような場合であっても検出することを目標とする。なお、図２、７および１０に示す漫画は、実験のため著作者の了解を得て提供いただいたものである。
【００２３】
3. この発明の処理手順
上に述べたそれぞれのタイプの複製を検出するには、各々に適した手法を用いるべきかもしれない。しかし、実際に利用することを考えると、全種類の不正利用を統一的に検出できる手法が望まれる。この発明は、一番難しい問題である部分的複製を検出することを意図しているが、他の種類の複製であっても検出可能であることを目指す。
【００２４】
3.1. 処理の流れ
この発明は、局所特徴量を用いて部分的複製を検出する手法である。図3に示すように、処理過程は2つの部分からなる。
データーベース処理では、著作権を保護すべき画像１３（著作権保護画像と呼ぶ）を集めて局所特徴量を抽出し、データーベース１５を作る。局所特徴量の抽出は、region detectorによる局所領域の抽出と、feature descriptorによる特徴ベクトルとしての記述からなる。画像のサイズにもよるが、一般に抽出される特徴ベクトルの数は画像あたり数百から数万と膨大になる。
【００２５】
一方、クエリ処理では、著作権侵害の可能性のある画像（被疑画像と呼ぶ）をクエリ１１としてデーターベース１５に問い合わせ処理を行う。まず、データーベース処理で用いたものと同じdetectorとdescriptorを用いて、特徴ベクトルを抽出する。それから、近似最近傍探索によって、クエリ１１の特徴ベクトルとデーターベースの特徴ベクトルを照合し、対応する著作権保護に投票を行う。その結果、得票数が最大の画像から一定数を著作権侵害の可能性として報告する。
【００２６】
線画の部分的複製を検出するため、この実施形態では、MSERを領域検出器として、HOGを特徴量記述子として用いる。マッチングの時間を短縮するため、ANN(Approximate Nearest Neighbor search、詳細は、次の文献、S. Arya, D. Mount, R. Silverman and A. Y. Wu, "An optimal algorithm for approximate nearest neighbor searching", Journal of the ACM, 45, 6, pp.891-923, 1998.参照)を用いて、最近傍の特徴ベクトルを計算する。
【００２７】
3.2. MSER
Matasらは、wide-baseline マッチングのため、MSERと呼ばれる手法を提案している。多重解像度表現を用いることによって、違う視点から得られた画像を照合している。
【００２８】
概略を以下に述べる。極値領域(Extremal region)という領域を考える。この領域は、領域内の全部の画素の明暗度は周りの画素の明暗度より高い又は小さいとして定義された領域である。この極値領域の中で、安定な面積が一番大きい領域をMSERという。この領域の共分散行列を対角化して、MSERを楕円領域に変換する。図4に抽出された楕円領域の例を示す。
【００２９】
この楕円MSERはアフィン変換と輝度変化に耐性を持っている。手書きの複製では、原画像の線の明暗と濃淡が変化するので、MSERの特性は、手書き複製から安定な領域を抽出するために重要となる。さらに、手書き複製では画像の細かい部分に多くの改変がある。そして、細かい部分から抽出した楕円のサイズは小さく、複製の識別にはあまり役に立たないため、利用する楕円のサイズを一定の大きさを持つものに限定する。また、複製の識別のためには、楕円領域内に多くの線分が含まれていることが望ましい。そこでこの発明では、楕円のサイズを一定割合(実験では6倍)だけ拡大する。それから、楕円の長軸を画像のy軸に平行となるように回転し、局所特徴領域を得る。図5に、拡大、回転されたMSERの領域の例を示す。
【００３０】
3.3. HOG
HOG (Histogram of Oriented Gradients)は、人検出のため、Dalalらによって提案された特徴量である。基本的な考え方は、局所の勾配あるいはエッジの方向の分布で、物体の見えや形状をうまく表現できるというものである。提案方法では、MSERで定義された各々の局所領域に対してHOG特徴を抽出する。図6に示すように、まず、各ピクセルの輝度から勾配強度と勾配方向を計算する。このとき、勾配方向を9方向に離散化する。そして、局所領域をセルと呼ばれる一様な小領域に分割する。次に、各セル領域において、輝度の勾配方向ヒストグラムを作成して、9次元のベクトルを得る。それから、図6に示すように、
セル間で互いに重なりを持つブロックを構成し、セルのベクトルを結合、正規化して、ブロックを表すベクトルを得る。結果として得られる特徴ベクトルは、全てのブロックのベクトルから構成される多次元ベクトルである。1つのブロックは9個のセルを含み、局所領域からは6×6個のブロックが得られるため、特徴ベクトルの次元数は9×3×3×6×6 = 2916次元である。なお、HOG特徴は局所特徴領域を均一に分割するので、スケール変換に対して不変である。
【００３１】
3.4. 照合と投票による複製検出
上記のプロセスを経て得られる特徴ベクトルは多数となるため、その照合には効率化が必要である。この実施形態では、近似最近傍探索の一手法であるANN(Approximate Nearest Neighbor)を使って、照合の高速化を図る。ANNでは、k-d木を用いてデータを記録する。探索時には、クエリとなる特徴ベクトルqを用いてk-d木を根から葉に向かって辿ることにより、暫定的な最近傍となる特徴ベクトルpを得る。qとpのユークリッド距離をrとするとき、真の最近傍はqから半径rの超球中に存在するので、その空間を探索すればよい。ANNではこのとき、近似のパラメータεを用いて縮小した半径r/(1+ε)の超球内を探索することにより、高速化を図るものである。縮小のために真の最近傍が得られないというリスクを負うものの、処理は劇的に高速化される。
【００３２】
一般に、照合の結果として得られる対応関係の中には、誤ったものも多数含まれる。誤対応を除去する簡便な方法は、距離の比を用いるものである。いま、クエリの特徴ベクトルをq、その最近傍となるデーターベース中の特徴ベクトルをp1、第2位となる特徴ベクトルをp2とするとき、
【００３３】
【数１】
となる、すなわち2位との差が顕著である場合にのみ対応するとみなす。ここで、Tは閾値である。
【００３４】
以上の処理により、被疑画像から得た各特徴ベクトルについて、対応するデーターベース中の特徴ベクトルを得ることができる。データーベース中の特徴ベクトルに対しては、どの著作権保護画像から得たものであるかが分かっている。これをその画像に対する投票と考えることにより、最大得票数を得る画像として、対応する著作権保護画像を検出することができる。ユーザにとって少数の画像を検査することはそれほど苦にならないと考えられるため、この実施形態では、得票数第R位までの画像を出力する。
【００３５】
4. 実験
4.1. 実験条件
この発明の有効性を検証するため、漫画を対象として実験を行った。
まず、データーベースに格納する著作権保護画像としては、7種類の漫画から得た1002枚の単色画像を用いた。
クエリについては、次のような手順により作成した。まず、データーベースの画像から101枚の画像を選択した。次に、各々について、約1/5程度の面積を持つ部分領域を切り出した。部分画像には、人物や顔の一部、建物や花の一部が含まれている。
【００３６】
near partial copyとしては、この部分領域を用いて次のように2種類を作成した。一つは、部分領域の画像を印刷してからスキャンして、再度、画像化することにより得られる部分的複製(以後、印刷と呼ぶ)である。もう一つは、部分領域の線画をまねて手書きで複
製し、スキャンして画像化することにより得られる部分的複製(以後、手書きと呼ぶ)である。両者とも、元の部分領域画像の3/4の大きさとなるようにスケール変動を加えた。そしてこれらの画像を、データーベースには存在しない漫画（背景）に埋め込むことによって、クエリ画像とした。背景はデーターベースに登録していない漫画からランダムに選択した。
【００３７】
クエリ画像の例を図7に示す。クエリ画像としては、背景となる漫画を持たないものに加えて、部分的複製の面積を基準として、背景の面積を2, 4, 10の3通りに変化させ、合計4通りのクエリ画像を作成した。
画像の照合では、ANNのεを10に設定した。実験に用いた計算機は、CPUがOpteron 2.4GHz、メモリが128GBのものである。
【００３８】
4.2. 実験 1
まず、上記のクエリ画像を用いて複製検出実験を行った。本実験では、この発明による処理のほか、比較手法としてSIFTを用いた複製検出法も試した。比較手法では、局所特徴量としてSIFTを用いる以外は、基本的にはこの発明による処理と同じである。距離の比の閾値Tとしては、この発明による処理で0.95、SIFTを用いる手法で0.6という値を設定した。
【００３９】
実験の結果を図8と図9に示す。横軸は得票数の順位、縦軸は累積分類率を表す。図8を見ると、印刷の複製については、SIFTはこの発明による処理を多少上回る結果を得ていることが分かる。両者に共通して言えることは以下の2点である。下位の画像まで見ることにより、累積分類率はわずかではあるが改善する。また、背景がない場合の累積分類率が最も高く、背景の面積が大きくなるにつれて精度が少しずつではあるが低下する。
【００４０】
一方、図9を見ると、手書きの複製については、SIFTは全く有効に動作しないことが分かる。これはSIFT特徴が手書きのような微妙ではあるが複雑な変動に対して非常に脆いことを意味している。これに対して、この発明による処理は、印刷の場合に比べて低下はするものの一定の累積分類率を得た。具体的には、例えば、背景のない手書きの場合で5位の累積分類率が94%、10倍の背景を伴う場合で74%という結果であった。これは、MSERとHOGの組み合わせが手書きの変動に対して有効であることを示している。
この発明による処理で検出に失敗した原因は、次の2つであった。
【００４１】
一つは、違う漫画であっても似ている部分が多いことである。テクスチャとして似た領域からは類似の特徴ベクトルが得られる。また、文字を多く含む部分領域からも類似の特徴ベクトルを得ることが多く、これが原因となり誤投票が増加した。
【００４２】
もう一つの原因は、局所性の不足によるものである。図10に示すように、クエリ画像から得られた局所領域には、背景の一部分にまたがるものがある。このような場合、データーベース中の特徴ベクトルと類似しない特徴ベクトルが得られ、誤投票につながった。
【００４３】
処理時間については、この発明による処理はSIFTを用いた場合に比べてかなり劣る結果となった。この主な理由は、特徴ベクトルの次元数の差にある。SIFTが128次元であるのに対して、HOGにより得られる特徴ベクトルは2916次元と大きな開きがある。この結果、例えば背景がない場合の処理時間は、SIFTによる手法で425ms/queryであったのに対して、この発明による処理では6013ms/queryであった。
【００４４】
4.3. 実験2
次に、この発明による処理に対して、回転とスケール変換に対する耐性を検査した。クエリ画像としては、印刷、手書きの双方について、背景のない部分的複写を用いた。具体
的には、これらを30°、45°に回転したものや、大きさを2倍(原画像の3/2倍)にしたものを用いた。
【００４５】
5位までの累積分類率を表1と表2に示す。ここで、表1の0°、表2の3/4とは、実験1と同様のクエリ画像を表す。この結果より、この発明による処理は、スケール変化や回転についても一定の耐性を持つことが分かる。また、これらの表からは、回転やスケール変化に対する耐性は、手書きの場合により得にくいことも分かる。
【００４６】
【表１】
【表２】
5. まとめ
【００４７】
この発明では、局所特徴量の照合による線画の部分的複製の検出手法を提案した。この実施形態では、MSERで抽出した領域をHOGで記述することにより、複雑な背景を伴う場合でも、印刷した線画と手書きの不正コピーを一定の精度で検出可能である。SIFTを用いた手法との比較実験により、以下のことが分かった。(1)SIFTを用いる手法は、印刷した線画に対して高い有効性がある。(2)この実施形態では、印刷した線画の検出に対して、SIFTより数%低い分類率となる。(3)SIFTを用いる手法は、手書きの線画に対して20%程度の5位分類率しか得られずほぼ無力である。(4)この実施形態では、分類率は低下するものの5位分類率で74-94%を得、一定の有効性がある。(5)この実施形態には、ある程度の回転とスケール変換に対する耐性がある。
今後の課題は、この発明における処理時間の短縮などである。
【００４８】
前述した実施の形態の他にも、この発明について種々の変形例があり得る。それらの変形例は、この発明の範囲に属さないと解されるべきものではない。この発明には、請求の範囲と均等の意味および前記範囲内でのすべての変形とが含まれるべきである。
【符号の説明】
【００４９】
１１ クエリ、被疑画像
１３ 著作権保護画像
１５ データーベース
【特許請求の範囲】
【請求項１】
検索質問の線画に近い特徴を持つ線画が、複製から保護されるべき原画が登録されてなる原画データーベース中に登録されているか否かを決定すべく、前記検索質問の線画からその局所的な特徴を表す複数の局所領域を決定する領域決定工程と、
決定された各局所領域の特徴に応じた特徴ベクトル（クエリ特徴ベクトル）をそれぞれ抽出する特徴抽出工程と、
各検索質問特徴ベクトルを、前記原画データーベースに登録された各原画について予め抽出された複数の特徴ベクトル（原画特徴ベクトル）とそれぞれ照合し、各クエリ特徴ベクトルにつき近傍の原画特徴ベクトルをそれぞれ決定する照合工程と、
近傍の各原画特徴ベクトルに基づいて、前記検索質問に近い特徴を持つ線画が前記原画データーベースに登録されているか否かを決定しかつ登録されている場合はその線画を特定する工程とを備え、
前記領域決定工程は、画像の明暗の変化および濃淡の変化に対する耐性を有し、かつ、所定量の線成分を内包するような各局所領域を対象の線画からそれぞれ抽出し、
前記特徴抽出工程は、線画が幾何的変換を受けた場合に耐性を有するような各特徴ベクトルをそれぞれ抽出し、
各工程をコンピュータが実行することを特徴とする線画像の原画検索方法。
【請求項２】
前記領域決定工程は、MSER（エムエスイーアール、Maximally Stable Extremal Regions）の手法を用いて対象の線画から候補となる複数の領域を抽出する工程と、抽出された候補のうち所定面積より広い領域を拡大し、拡大された領域を局所領域とする工程とを含んでなる請求項１に記載の方法。
【請求項３】
前記特徴抽出工程は、HOG（ホグ、Histgram of Oriented Gradients）の手法を用いて各局所領域から特徴ベクトルを抽出する請求項１または２に記載の方法。
【請求項４】
前記照合工程は、近似最近傍探索の手法を用いて各クエリ特徴ベクトルにつき近傍の原画特徴ベクトルをそれぞれ決定し、
各原画特徴ベクトルは、各原画が前記原画データーベースに登録される際にその原画に対し前記領域決定工程および前記特徴抽出工程と同様の処理を行って各原画から複数個抽出され、
前記原画データーベースは、各原画とそれから抽出された原画特徴ベクトルとが対応付けられて登録されてなる請求項１〜３のいずれか一つに記載の方法。
【請求項１】
検索質問の線画に近い特徴を持つ線画が、複製から保護されるべき原画が登録されてなる原画データーベース中に登録されているか否かを決定すべく、前記検索質問の線画からその局所的な特徴を表す複数の局所領域を決定する領域決定工程と、
決定された各局所領域の特徴に応じた特徴ベクトル（クエリ特徴ベクトル）をそれぞれ抽出する特徴抽出工程と、
各検索質問特徴ベクトルを、前記原画データーベースに登録された各原画について予め抽出された複数の特徴ベクトル（原画特徴ベクトル）とそれぞれ照合し、各クエリ特徴ベクトルにつき近傍の原画特徴ベクトルをそれぞれ決定する照合工程と、
近傍の各原画特徴ベクトルに基づいて、前記検索質問に近い特徴を持つ線画が前記原画データーベースに登録されているか否かを決定しかつ登録されている場合はその線画を特定する工程とを備え、
前記領域決定工程は、画像の明暗の変化および濃淡の変化に対する耐性を有し、かつ、所定量の線成分を内包するような各局所領域を対象の線画からそれぞれ抽出し、
前記特徴抽出工程は、線画が幾何的変換を受けた場合に耐性を有するような各特徴ベクトルをそれぞれ抽出し、
各工程をコンピュータが実行することを特徴とする線画像の原画検索方法。
【請求項２】
前記領域決定工程は、MSER（エムエスイーアール、Maximally Stable Extremal Regions）の手法を用いて対象の線画から候補となる複数の領域を抽出する工程と、抽出された候補のうち所定面積より広い領域を拡大し、拡大された領域を局所領域とする工程とを含んでなる請求項１に記載の方法。
【請求項３】
前記特徴抽出工程は、HOG（ホグ、Histgram of Oriented Gradients）の手法を用いて各局所領域から特徴ベクトルを抽出する請求項１または２に記載の方法。
【請求項４】
前記照合工程は、近似最近傍探索の手法を用いて各クエリ特徴ベクトルにつき近傍の原画特徴ベクトルをそれぞれ決定し、
各原画特徴ベクトルは、各原画が前記原画データーベースに登録される際にその原画に対し前記領域決定工程および前記特徴抽出工程と同様の処理を行って各原画から複数個抽出され、
前記原画データーベースは、各原画とそれから抽出された原画特徴ベクトルとが対応付けられて登録されてなる請求項１〜３のいずれか一つに記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【公開番号】特開２０１０−１８６２６３（Ｐ２０１０−１８６２６３Ａ）
【公開日】平成２２年８月２６日（２０１０．８．２６）
【国際特許分類】
【出願番号】特願２００９−２９０１５（Ｐ２００９−２９０１５）
【出願日】平成２１年２月１０日（２００９．２．１０）
【出願人】（５０５１２７７２１）公立大学法人大阪府立大学 (688)
【Ｆターム（参考）】
【公開日】平成２２年８月２６日（２０１０．８．２６）
【国際特許分類】
【出願日】平成２１年２月１０日（２００９．２．１０）
【出願人】（５０５１２７７２１）公立大学法人大阪府立大学 (688)
【Ｆターム（参考）】
[ Back to top ]