(57)【要約】  Example-based超解像を用いるビデオ圧縮のためのデータプルーニングの方法及び装置を提供する。入力ビデオからビデオのパッチを抽出し、クラスタリング方法を用いてグループ分けし、代表的パッチをパッチフレームにパッケージングする、符号化する方法と装置を提供する。元のビデオをダウンサイズし、パッチフレームと共に、又はパッチフレームに加えて送信する。デコーダにおいて、パッチフレームからパッチを抽出し、パッチライブラリを生成する方法と装置を提供する。通常のビデオフレームはアップサイズされ、低解像度パッチは、復号された通常フレームのパッチをキーワードとして用いてライブラリをサーチして、パッチライブラリからのパッチで置き換えられる。適当なパッチが無ければ、置き換えはしない。後処理手順を用いて、回復されたビデオの時間的・空間的に滑らかにする。
2013518464.tif 000002
【特許請求の範囲】
【請求項１】
ビデオ処理の方法であって、
受信したビデオ信号からビデオのパッチを抽出するステップと、
前記パッチをグループにクラスタ化するステップと、
元のビデオをダウンサイズするステップと、
前記グループの代表的パッチをパッチフレームにパッケージングするステップと、
前記ダウンサイズした元のビデオを、前記パッチフレームと共に、デコーダに送信するステップとを有する、方法。
【請求項２】
前記パッチフレームのデータを、前記受信したビデオ信号に連結するステップをさらに有する、請求項１に記載の方法。
【請求項３】
前記連結するステップは、通常フレームのデータを前記パッチフレームのデータに組み入れることにより行う、請求項２に記載の方法。
【請求項４】
抽出するステップを前記ビデオの特徴に基づき行う、請求項１に記載の方法。
【請求項５】
クラスタ化するステップを修正ｋ−ｍｅａｎｓアルゴリズムに基づき行う、
請求項１に記載の方法。
【請求項６】
クラスタかするステップをインクリメンタルクラスタ化を用いて行う、請求項１に記載の方法。
【請求項７】
前記パッチフレームはブロックに分割することによりダウンサイズされる、
請求項１に記載の方法。
【請求項８】
前記パッチフレームはスタガリングサンプリングを用いることによりダウンサイズされる、
請求項１に記載の方法。
【請求項９】
前記パッチフレームにおけるパッチの位置を、空間的及び時間的に平滑化するように、最適化する、請求項２に記載の方法。
【請求項１０】
フレームがパッチフレームか、前記受信したビデオ信号のフレームかを示すフラグを用いる、請求項２に記載の方法。
【請求項１１】
ビデオ処理装置であって、
受信したビデオ信号からビデオのパッチを抽出して、前記パッチをグループにクラスタ化する手段と、
前記受信したビデオ信号のサイズを小さくするダウンサイズ器と、
前記グループの代表的パッチをパッチフレームにパッケージングする回路と、
前記パッチフレームとダウンサイズされたビデオ信号とをデコーダに送信する回路とを有する、装置。
【請求項１２】
前記回路は、前記パッチフレームのデータを、前記受信したビデオ信号に連結する、請求項１１に記載の装置。
【請求項１３】
前記回路は、前記受信したビデオ信号のデータを、パッチフレームのデータに組み込む、請求項１１に記載の方法。
【請求項１４】
受信したビデオ信号からビデオのパッチを抽出して、前記パッチをグループにクラスタ化する手段は、前記ビデオの特徴に基づいて抽出を行う、請求項１１に記載の装置。
【請求項１５】
前記クラスタ化手段は、修正ｋ−ｍｅａｎｓアルゴリズムに基づきクラスタ化を行う、
請求項１１に記載の装置。
【請求項１６】
前記クラスタ化手段は、インクリメンタルクラスタ化を用いてクラスタ化を行う、
請求項１１に記載の装置。
【請求項１７】
前記回路は、パッチフレームをブロックに分割することによりダウンサイズする、
請求項１１に記載の装置。
【請求項１８】
前記パッチフレームはスタガリングサンプリングを用いることによりダウンサイズされる、
請求項１１に記載の装置。
【請求項１９】
前記パッチフレームにおけるパッチの位置を、空間的及び時間的に平滑化するように、最適化する、請求項１２に記載の装置。
【請求項２０】
フレームがパッチフレームか、前記受信したビデオ信号のフレームかを示すフラグを用いる、請求項１２に記載の装置。
【請求項２１】
ビデオ信号処理の方法であって、
パッチフレームからビデオのパッチを抽出するステップと、
抽出したパッチからパッチライブラリを生成するステップと、
ビデオの通常フレームのサイズを大きくするステップと、
サイズを大きくした通常ビデオフレームの低解像度のビデオ部分を、前記低解像度部分をキーワードとして用いて前記パッチライブラリからサーチしたパッチで置き換えるステップと、
その結果得られたビデオに後処理を行うステップと、を有する方法。
【請求項２２】
抽出はブロックベースで行われる、請求項２１に記載の方法。
【請求項２３】
生成するステップは、さらに、対応するパッチ中の高周波の詳細のレベルを示すフラグを、前記抽出されたパッチに付加するステップを有する、
請求項２１に記載の方法。
【請求項２４】
パッチライブラリを生成するステップは、さらに、前記抽出されたパッチのサイズを小さくするステップを有する、請求項２１に記載の方法。
【請求項２５】
サイズが小さいパッチをアップサンプリング及び補間して、リサイズされたパッチとそれに対応する元のパッチとの間の距離を、所定の閾値と比較することにより、前記フラグを生成する、請求項２３に記載の方法。
【請求項２６】
前記抽出するステップはブロックベースで行われる、
請求項２１に記載の方法。
【請求項２７】
前記置き換えるステップにおけるサーチは、バイナリツリーサーチを用いて行われる、
請求項２１に記載の方法。
【請求項２８】
前記置き換えるステップで前記フラグを用いて、パッチを前記パッチライブラリのものと置き換えるか決定する、請求項２３に記載の方法。
【請求項２９】
前記置き換えるステップは、コスト関数の最小化に基づく、
請求項２１に記載の方法。
【請求項３０】
前記コスト関数は空間的及び時間的な平滑性に基づく、
請求項２９に記載の方法。
【請求項３１】
ビデオ処理装置であって、
パッチフレームからビデオのパッチを抽出し、抽出したパッチからパッチライブラリを生成する手段と、
通常のビデオフレームのサイズを大きくするリサイズ回路と、
通常のビデオフレームの低解像のビデオ部分をキーワードとして用いて、前記パッチライブラリをサーチするパッチサーチ回路と、
サイズを大きくした通常ビデオフレームの低解像度のビデオ部分を、前記パッチライブラリからサーチしたパッチで置き換えるパッチ置き換え回路と、
前記パッチ置き換え回路からのビデオに後処理を行うポストプロセッサとを有する、装置。
【請求項３２】
前記手段はパッチ抽出プロセッサである、
請求項３１に記載の装置。
【請求項３３】
前記パッチ抽出器は、さらに、対応するパッチ中の高周波の詳細のレベルを示すフラグを、前記抽出されたパッチに付加する回路を有する、
請求項３１に記載の装置。
【請求項３４】
前記パッチ抽出手段は、さらに、前記抽出されたパッチのサイズを小さくする回路を有する、請求項３１に記載の装置。
【請求項３５】
前記パッチ抽出手段は、さらに、サイズが小さいパッチをアップサンプリング及び補間して、リサイズされたパッチとそれに対応する元のパッチとの間の距離を、所定の閾値と比較することにより、フラグを生成する回路を有する、
請求項３３に記載の装置。
【請求項３６】
前記パッチ置き換え回路はブロックベースで動作する、
請求項３１に記載の装置。
【請求項３７】
前記パッチサーチ回路はバイナリツリーサーチを行う、
請求項３１に記載の装置。
【請求項３８】
前記パッチ置き換え回路は、前記フラグから、前記サイズを大きくした通常のビデオフレームの低解像度のパッチを、前記パッチライブラリからのパッチで置き換えるか決定する、請求項３３に記載の装置。
【請求項３９】
前記パッチ置き換え回路は、コスト関数の最小化によりパッチを置き換える、
請求項３１に記載の装置。
【請求項４０】
前記コスト関数は、空間的及び時間的な平滑性を測るコスト関数を最小化する、請求項３９に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本原理は、データプルーニングをビデオ処理方法として用いて、入力ビデオデータの一部をそれが符号化される前に削除してビデオの符号化効率を上げることにより効率的にビデオ圧縮をする装置と方法とに関する。
【背景技術】
【０００２】
［関連出願との相互参照］
この出願は米国仮出願第６１／３３６５１６号（２０１０年１月２２日出願、発明の名称「Example-based超解像を用いたビデオ圧縮のためのデータプルーニング」の利益を主張するものであり、その出願全体をここに参照援用する。
［背景技術］
ビデオ圧縮のためのデータプルーニングは、ビデオ圧縮の分野における新しい技術である。データプルーニングに関する先行する業績には、ビデオの符号化効率を向上するものがある。
【０００３】
１つのアプローチは、非特許文献１に記載された垂直及び水平ライン削除である。このアプローチでは、ビデオフレーム中の垂直及び水平のラインを符号化前に削除し、このラインを復号後に非線形補間により回復する。ラインの位置は回復エラーを最小化するように最適化される。このアプローチには欠点がある。第１に、インの位置をサイドチャネルで送り、ロスレスに符号化しなければならず、全体的な符号化効率が低下してしまう。第２に、ラインの削除により情報が失われ、回復時にエイリアシングアーティファクトが生じる。例えば、ビデオフレームに１ピクセルの水平ラインがあると、それはライン削除により失われ、デコーダ側では回復できない。第３に、ビデオショットでは、そのショット中のすべてのフレームで、ライン位置が同じでなければならない。ショット中に速い動きがあると、重要な情報を含むラインを間違って削除する結果となる。ショット中のオブジェクトの動きに適合するようにラインの削除をデザインすることもできるが、ショット中のフレームごとに異なるラインを削除すると、見かけ上の動きが生じてしまい、動き推定と動き補償を含むビデオ符号化プロセスには悪影響がある。
【０００４】
他のカテゴリーの１つのアプローチは、非特許文献２、３、及び４に記載されたブロック又は領域の削除に基づく。これらのアプローチは、ライン削除と似ており、ラインではなくブロックや領域を削除する点が違うだけである。削除されたブロックや領域はデコーダ側で補間または修復（inpainting）により回復される。これらのアプローチの欠点はライン削除と同様である。しかし、ラインではなくブロックを用いることにより、データプルーニングの点では柔軟性が高く、情報損失の問題を緩和する。しかし、その他の問題については、ライン削除アプローチと同様である。
【０００５】
非特許文献５、６に記載された画像又はビデオエピトミ（epitome）は圧縮のためのデータプルーニングに使えるかも知れない他の一方法である。エピトミによるアプローチは、画像（又はビデオ）をパッチに分割し、代表的なパッチと、その画像中のパッチをエピトミミニチュア中のパッチにマッピングする全射マップ（surjective map）とを含む小さいミニチュアとして画像を表す。小型のミニチュア（すなわち、エピトミ）は元の画像又はビデオを圧縮したものとみなせるので、潜在的にはエピトミを圧縮目的に用いることができる。しかし、エピトミをデータプルーニングに適用する時の問題は、全射マップ（surjective map）もサイド情報としてデコーダに送信しなければならないことである。さらに、全射マップは、対応エラーとアーティファクトとを避けるため、ロスレス（losslessly）で符号化しなければならない。対応エラーとアーティファクトが生じると、符号化効率が大幅に下がってしまう。
【先行技術文献】
【非特許文献】
【０００６】
【非特許文献１】D. T. Vo、J. Sole、P.Yin、C. Gomila、及びT. Nguyen著「Data Pruning-Based Compression Using High Order Edge-DirectedInterpolation」IEEE International Conference onAcoustics, Speech, and Signal Processing (ICASSP), ２００９で提出されたThomson Research technical report
【非特許文献２】P. Ndjiki-Nya, T. Hinz, A. Smolic, and T. Wiegand,「A generic and automatic content-based approach for improved H.２６４/MPEG４-AVC video coding」、IEEE International Conference on Image Processing {ICIP), ２００５
【非特許文献３】Chunbo Zhu, Xiaoyan Sun, Feng Wu, and Houqiang Li,「Video Coding with Spatio-Temporal Texture Synthesis」、IEEE International Conference on Multimedia and Expo (ICME), ２００７
【非特許文献４】Chunbo Zhu, Xiaoyan Sun, Feng Wu, and Houqiang Li,「Video coding with spatio-temporal texture synthesis and edge-basedinpainting」、IEEE International Conference on Multimediaand Expo (ICME), ２００８
【非特許文献５】N. Jojic, B. Frey, and A. Kannan,「Epitomicanalysis of appearance and shape」、IEEE InternationalConference on Computer Vision (ICCV), ２００３
【非特許文献６】V. Cheung, B. Frey, and N. Jojic,「Videoepitomes」、IEEE Computer Society Conference on ComputerVision and Pattern Recognition (CVPR), ２００５
【発明の概要】
【課題を解決するための手段】
【０００７】
本原理は、Example-based超解像を用いたビデオ圧縮のためのデータプルーニングをする方法と装置とに関する。
【０００８】
本原理の一態様により、ビデオ圧縮のためにデータプルーニングを用いてビデオ処理する方法が提供される。前記方法は、受信したビデオ信号からビデオのパッチ又は一部分を抽出するステップと、前記パッチをグループにクラスタ化するステップと、前記グループの代表的パッチをパッチフレームにパッケージングするステップと、デコーダに送信するステップとを有する。
【０００９】
本原理の他の一態様により、ビデオ圧縮のためにデータプルーニングを用いてビデオ処理する装置が提供される。前記装置は、ビデオ信号からビデオのパッチを抽出して、前記パッチをグループにクラスタ化する手段と、前記グループの代表的パッチをパッチフレームにパッケージングする回路と、前記データをエンコーダに送信する回路とを有する。
【００１０】
本原理の他の一態様により、ビデオ圧縮のためにデータプルーニングを用いてビデオ処理する装置が提供される。前記装置は、ビデオ信号からビデオのパッチを抽出して、前記パッチをグループにクラスタ化するパッチ抽出及びクラスタ化手段と、前記グループの代表的パッチをパッチフレームにパッケージングする回路と、前記データをエンコーダに送信する回路とを有する。
【００１１】
本原理の他の一態様により、ビデオ処理方法が提供される。該方法は、パッチフレームからビデオのパッチを抽出するステップと、パッチからパッチライブラリを生成するステップと、通常のビデオフレームのサイズを大きくするステップと、通常ビデオフレームの低解像度のビデオ部分を、前記低解像度部分をキーワードとして用いて前記パッチライブラリからサーチしたパッチで置き換えるステップと、その結果得られたビデオに後処理を行うステップと、を有する。
【００１２】
本原理の他の一態様により、ビデオ処理装置が提供される。該装置は、前記パッチフレームからパッチを抽出し、パッチライブラリを生成する手段と、通常のビデオフレームのサイズを大きくするリサイズ回路と、通常のビデオフレームの低解像度のビデオ部分をキーワードとして用いて、前記パッチライブラリをサーチするパッチサーチ回路と、前記低解像度部分を、前記パッチライブラリからサーチしたパッチで置き換えるパッチ置き換え回路と、前記パッチ置き換え回路からのビデオに後処理を行うポストプロセッサとを有する。
【００１３】
本原理の他の一態様により、ビデオ処理装置が提供される。該装置は、前記パッチフレームからパッチを抽出し、パッチライブラリを生成するパッチ抽出プロセッサと、通常のビデオフレームのサイズを大きくするリサイズ回路と、通常のビデオフレームの低解像度のビデオ部分をキーワードとして用いて、前記パッチライブラリをサーチするパッチサーチ回路と、前記低解像度部分を、前記パッチライブラリからサーチしたパッチで置き換えるパッチ置き換え回路と、前記パッチ置き換え回路からのビデオに後処理を行うポストプロセッサとを有する。
【００１４】
本原理の上記その他の態様、特徴、及び有利性は、添付した図面を参照して読むと、実施形態の詳細な説明から明らかとなるであろう。
【図面の簡単な説明】
【００１５】
【図１Ａ】本原理におけるExample-based超解像アプローチを示すシステム図である。
【図１Ｂ】本原理におけるExample-based超解像アプローチを示すシステム図である。
【図１Ｃ】本原理におけるExample-based超解像アプローチを示すシステム図である。
【図２】本原理を用いるパッチクラスタリングアルゴリズムを示す図である。
【図３】本原理を用いる２レベルクラスタリングアルゴリズムを示す図である。
【図４】スタガリングサンプリングプロセスを示す図である。
【図５】パッチ位置最適化及びパッチ配布を示す図である。
【図６】本原理によるパッチのパッチフレームへのパッキングの一例を示す図である。
【図７】本原理によるサーチアンドリプレースメントプロセスの一実施形態を示す図である。
【図８】本原理を用いる符号化方法の一実施形態を示す図である。
【図９】本原理を用いる符号化装置の一実施形態を示す図である。
【図１０】本原理を用いる復号方法の一実施形態を示す図である。
【図１１】本原理を用いる復号装置の一実施形態を示す図である。
【発明を実施するための形態】
【００１６】
ここに記載する原理は、Example-based超解像を用いた新規のデータプルーニングフレームワークを提供する。データプルーニング（data pruning）は、符号化前に、入力ビデオデータの一部を削除することにより、ビデオ符号化効率をよくするビデオ前処理技術である。削除されたビデオデータは、デコーダサイドで、復号されたデータから推論することにより回復される。データプルーニングの一例は画像ライン削除である。これは入力ビデオ中の水平又は垂直のスキャンラインを削除するものである。
【００１７】
Example-based超解像は、入力画像中の低解像度パッチを検索キーワードとして用いてパッチライブラリ中の高解像度パッチを探し、低解像度入力画像中の低解像度パッチを、読み出した高解像度パッチで置き換えることにより、低解像度画像を高解像度画像に変換する、超解像技術である。言い換えると、低解像度パッチがパッチライブラリへのインデックスのように機能して、対応する高解像度パッチを読み出す。Example-based超解像は、最初に、William T. Freeman,
Thouis R. Jones, and Egon C. Pasztor著「Example-based
super-resolution」（IEEE Computer Graphics and
Applications, March/April, ２００２）で提案され、低解像度画像を高解像度画像に変換するのに用いられた。ここに説明された原理は、Example-based超解像技術に基づくデータプルーニング法を表す。説明されたフレームワークでは、トランスミッタサイドにおいて、高解像度パッチをグループ化し、代表的な高解像度パッチを入力ビデオから抽出する。代表的な高解像度パッチは、一連の合成フレーム（パッチフレーム）にパッキングされる。元のビデオの解像度を下げ、パッチフレームと共にレシーバに送る。レシーバサイドでは、パッチフレームから高解像度パッチを読み出し、パッチライブラリを作る。受信され拡大されたビデオ中の低解像度パッチは、それをキーワードとして用いて、ライブラリ中の対応する高解像度パッチを検索することにより、パッチライブラリ中の高解像度パッチと置き換えられる。
【００１８】
Example-based超解像方法をデータプルーニングに適用するため、パッチの抽出、クラスタリング、パッチのフレームへのパッキング、及びロバストリカバリ（robust recovery）などを含む、さらに別の問題を解決しなければならない。上記の通り、データプルーニングの既存のアプローチと比較して、本方法には多くの利点がある。第１に、入力ビデオは、ビデオ中のすべてのフレームが単純に、一様に小さいサイズにリサイズされるため、アダプティブラインアプローチやブロックリムーバルアプローチのような偽の動きの問題がない。第２に、高解像度情報は、パッチフレームで代表的なパッチを送信することにより、保存されるので、情報損失の問題は大幅に緩和される。第３に、ライン／ブロック位置や全射マップなどのメタデータをサイドチャネルにより追加的に送信する必要がほとんど又はまったく無い。
【００１９】
ここに説明される原理は、符号化して送信する前に、入力ビデオデータをプルーニングし、復号後に、プルーニングされたビデオデータを回復する方法を提供する。データプルーニングの目的は、符号化効率を高め、所定のビデオビットレートの要求を満たすことである。
【００２０】
本システムの一実施形態を図１に示す。エンコーダサイドでは、入力ビデオからパッチを抽出（extracted）して、クラスタリングアルゴリズムを用いてグループ化する。代表的なパッチを選択し、パッチフレームにパッキングする。他の経路において、アプリケーションの要請に応じて、元のビデオをあるサイズにダウンサイズする。パッチフレームは、ダウンサイズされたレギュラーフレームに付加してデコーダに送信でき、又は別のビデオとして送信できる。
【００２１】
デコーダサイドでは、パッチはパッチフレームから抽出され、サーチアンドリプレースプロセスを最適化するように処理される。プロセスは、検索と置換のためにパッチライブラリを生成する。復号されたレギュラーフレーム（regular frames）は、まずアップサンプリングと補間（例えば、双三次補間）を用いて、元のサイズにアップサイズされる。アップサイズされたフレームの低解像度パッチは、復号されたレギュラーフレーム中のパッチをキーワードとして用いて、対応する高解像度パッチを検索することにより、パッチライブラリ中のパッチと置き換えられる。ライブラリ中に高解像度パッチが見つからなければ、アップサイズされたフレーム中のパッチは置き換えられない。最後に、後処理手順を行い、回復されたビデオの時間的・空間的に滑らかにする。後処理手順は、最適化ベースの方法を用いて、サーチアンドリプレースプロセスと一体化することもできる。
【００２２】
１．パッチ抽出とクラスタリング
パッチ抽出は、ビデオフレームを一組のブロックに分割して行う。本原理の一実施形態では、パッチは１６×１６ピクセル又は８×８ピクセルなどの四角形のブロックと定義される。各パッチは、対応するブロック画像（ＲＧＢやＹＵＶなどフォーマットは異なってもよい）をベクトルに変換、すなわち平坦化（flattening）することにより、パッチベクトルとして表される。それゆえ、パッチベクトルに対応するブロック画像は、パッチベクトルを行列に変形することにより回復できる。ブロック画像を平坦化（flattening）する他に、パッチベクトルは、ブロック画像から特徴（例えば、カラーヒストグラム）を抽出することによっても、抽出できる。パッチは一連のフレームから抽出される。長いビデオの場合には、ビデオをグループオブピクチャ（ＧＯＰ）に分割する。各ＧＯＰでクラスタリングアルゴリズムを実行できる。
【００２３】
パッチクラスタリングの目的は、同じに見える、又は視覚的特性が類似しているパッチをグループ化することである。クラスタの代表的なパッチのみをパッチフレームにパッキングするので、クラスタ内のパッチ間の冗長性を除去できる。一実施形態では、各クラスタの代表的なパッチは、そのクラスタのパッチの平均である。クラスタリングアルゴリズムの入力は、ブロック画像の平坦化により、又は特徴抽出により抽出されたパッチベクトルである（本実施例では、ブロック画像平坦化を用いる）。
【００２４】
１．１  パッチクラスタリングアルゴリズム
ｋ−meansアルゴリズム（Ｌｌｏｙｄ’ｓアルゴリズムとも呼ばれる）や階層化クラスタリングアルゴリズムなどの既存の多くのクラスタリングアルゴリズムをパッチクラスタリングに用いられる。我々のパッチクラスタリングアルゴリズムの要件は、クラスタ内のパッチの外観的バリエーションが大き過ぎないということである。しかし、ｋ−ｍｅａｎｓアルゴリズムなどの通常のクラスタリングアルゴリズムは、このような要件を保証できない。そのため、本実施形態では、上記の要件を満たす（strictly enforces）修正ｋ−ｍｅａｎｓアルゴリズムを用いる。
【００２５】
通常のｋ−ｍｅａｎｓアルゴリズムは、収束するまで次の２つのステップを反復する：
１．各データポイントに対して、それとクラスタ中心との間の距離が最も近いクラスタを見つける。そのデータポイントをその最も近いクラスタに割り当てる。
２．すべてのデータポイントを割り当ててから、そのクラスタに割り当てられたデータポイントの平均を再計算することにより、各クラスタの中心をアップデートする。
【００２６】
我々の修正ｋ−ｍｅａｎｓアルゴリズムはこれと同様であるが、アウトライアーリジェクションプロセスを含む：
１．各データポイントに対して、それとクラスタ中心との間の距離が最も近いクラスタを見つける。距離が指定閾値βより大きいとき、そのデータポイントはリジェクトされる。そうでなければ、そのデータポイントはそのクラスタに割り当てられる。
２．すべてのデータポイントを割り当ててから、そのクラスタに割り当てられたデータポイントの平均を再計算することにより、各クラスタの中心をアップデートする。
【００２７】
修正ｋ−ｍｅａｎｓアルゴリズムは、クラスタ中の任意のデータポイントと、そのクラスタの中心との間の距離が、常に指定閾値βより小さいことを保証する。閾値βは、クラスタリング結果を見て値をマニュアル的に調整することにより、経験的に決定できる。
【００２８】
従来のｋ−ｍｅａｎｓアルゴリズムの他の問題は、クラスタ数ｋをアプリオリに決定しなければならないことである。本システムでは、すべてのデータポイントが最小数のクラスタでカバーされることを要求するので、クラスタリングプロセスの前には、ｋは未知である。この問題を解くため、我々のクラスタリングアルゴリズムは、１つのクラスタから始めて、収束するまで修正ｋ−ｍｅａｎｓアルゴリズムを実行し、他のクラスを加え、すべてのデータポイントがクラスタに割り当てられるまでこのプロセスを繰り返す。新しく加えられる各クラスタの中心は、既存のクラスタのどれにも割り当てられていない（ランダムに選択された）データポイントで初期化される。
【００２９】
このクラスタリングアルゴリズムの全体を図２のフローチャートに示した。
【００３０】
１．２  より効率的なパッチクラスタリング
クラスタリングプロセスは一度に一つのクラスタを加え、各クラスタに対して修正ｋ−ｍｅａｎｓアルゴリズムを実行しなければならないので、クラスタリングプロセスは遅くなりがちである。クラスタリングプロセスを速くするため、２つの方式を開発した。第１の方式は２レベルクラスタリングであり、第２の方式はインクリメンタルクラスタリングである。
【００３１】
２レベルクラスタリングプロセス（図３）は、最初に、大きい閾値βを用いてクラスタリングプロセスを実行する。そのクラスタリングプロセスが完了してから、小さい閾値を用いて、第１のクラスタリングプロセスで得られた各クラスタにおいて、クラスタリングアルゴリズムを実行する。このような階層的クラスタリング方式により、速くなるが、トレードオフ（trade-off）としてクラスタリング結果の精度が低下する。
【００３２】
インクリメンタルクラスタリング方式は、最初のフレームに対してだけ、２レベルクラスタリングプロセスを実行する。その後のフレームに対しては、クラスタを再利用して、各フレームのクラスタリングプロセスを、前のフレームから受け継いだクラスタ中心で初期化する。残りのプロセスは、図２に示した基本的なクラスタリングアルゴリズムと同じである。各フレームのクラスタリングプロセスを完了してから、そのフレームのパッチを破棄してメモリ空間を節約する。また、本クラスタリングプロセスでは、クラスタ中心と、そのクラスタ中のデータポイント数のみを保持する。クラスタを更新するため、Ｍ個のデータポイントがクラスタに割り当てられているとすると、クラスタ中心は次の式を用いて更新される：
【００３３】
【数１】
2013518464.tif 000003
ここで、Ｃｉは更新前のｉ番目のクラスタ中心であり、Ｃｉ＋は更新されたクラスタ中心であり、Ｄｊはクラスタに割り当てられたデータポイント（パッチベクトル）である。Ｎｉは更新前のクラスタ中のデータポイント数である。
【００３４】
インクリメンタルクラスタリングの利点は、クラスタリングプロセスの計算時間とメモリ空間とを両方とも節約できることである。長いビデオの場合、非インクリメンタルクラスタリングを使うと、必要な計算時間と記憶容量が非常に大きくなる。
【００３５】
１．３  グループオブピクチャ（Group of Pictures）
パッチが多くなればなるほどクラスタも多くなる。パッチ数が大きすぎるとき、計算が遅くなりすぎ現実的ではない。そのため、長いビデオの場合、それをグループオブピクチャ（ＧＯＰ）に分割し、クラスタリングアルゴリズムが各ＧＯＰ内で実行されるようにする必要がある。ＧＯＰ中のフレーム数は可変でも固定でもよい。フレキシブルＧＯＰを求める一方法は、ショット検出アルゴリズムを用いて、ビデオを複数のショットに切り分け、各ショットをＧＯＰとすることである。
【００３６】
ＧＯＰの長さを決定してから、パッチフレームを各ＧＯＰに連結する。ＧＯＰの長さやパッチフレーム数が可変であるとき、サイドチャネルを用いて、フレームが通常のフレーム（regular frame）かパッチフレームかを示すメタデータ（例えば、バイナリフラグ）を送信しなければならない。
【００３７】
１．４  クラスタ選択
クラスタ選択プロセスを実行して、デコーダ側に送信するクラスタの一部を破棄するが、これはデコーダ側ではすべてのクラスタは必要ないからである。
【００３８】
例えば、クラスタに細かいことのパッチのみが含まれる場合、そのクラスタは必要ない。高解像度のフラットパッチ（flat patches）と低解像度のものとはほとんど同じだからである。
【００３９】
一実施形態では、すべてのクラスタが保持される。その理由は、フラットパッチに追加情報が含まれていなくても、フラットパッチを破棄すると、サーチアンドリプレースプロセス中に、フラットパッチの一部が他のクラスタに引き寄せられて、目に見えるアーティファクトが生じるからである。そのため、フラットパッチクラスタを「ダミークラスタ」として保持すれば、アーティファクトの低減という利益になる。
【００４０】
２．パッチのパッチフレームへのパッキング
ＧＯＰにおけるクラスタリングプロセスが完了してから、クラスタ中心を、各クラスタの代表的パッチとして求める。代表的なパッチをパッチフレームにパッキングする。パッチフレームとダウンサイズされた通常フレームとを連結して、デコーダ側に送信する。
【００４１】
２．１  パッチフレームの生成
一実施形態では、最初に、元のビデオシーケンス中のビデオフレームと同じサイズのフレームにパッチをパッキングする。その後、大きなパッチフレームは、ダウンサイズされたビデオと同じサイズのフレームに分割される。これはいろいろな方法で実現することができる：一方法は、単に、フレームをブロックに分割することである。他の方法は、スタガリングサンプリングプロセス（staggering sampling process）を用いて、サイズリダクション後、フレームがダウンサイズされた通常ビデオのように見えるようにすることである。こうすることの利益は、符号化効率が高くなることである。サンプリングされたフレームは連結された通常フレームと同じように見え、時間的・空間的な平滑性が保存されるからである。
【００４２】
スタガリングサンプリングプロセス（staggering sampling process）は、画像をサンプリングして、ロケーションが異なる入力画像のサンプルを出力画像にコピーすることにより、複数の画像にする。例えば、ファクタ２のダウンサンプリングの場合、座標（１，１）、（１，３）、（３，１）・・・のピクセルを第１の出力画像にコピーし、座標（１，２）、（１，４）、（３，２）・・・のピクセルを第２の出力画像にコピーし、以下同様である（図４に示した）。留意点として、スタガリングサンプリングは、ピクセルに加えて、ブロックを基本的単位として実行することもできる。
【００４３】
２．２  パッチの位置の最適化
異なる多くの方法でパッチをフレームにパッキングできる。しかし、エンコーダによりパッチフレームが効率的に圧縮できるような方法で、パッチをパッキングすべきである。これには、パッチフレームが空間的及び時間的に平滑であることを要する。パッチフレームの空間的な及び時間的な平滑性（smoothness）を調整するトータルコスト関数を定義できる。しかし、かかるコスト関数を最適化するのは非常に困難である。コスト関数の入力空間はパッチの全順列だからである。
【００４４】
それゆえ、本システムでは異なるアプローチを用いる。本システムのアプローチの背後にある根拠は、すべてのパッチは元と同じ位置にあるべきだということである。これにより、パッチフレームが元のフレームに類似し、そのため元のフレームの空間的構造が保存されることになる。これを実現するため、クラスタリングプロセス中に、各クラスタ内のパッチのフレームＩＤと位置とが保持される。この情報はパッチパッキングプロセス中に使われる。
【００４５】
クラスタリングプロセスが終わると、各クラスタには、そのクラスタ内のすべてのパッチの位置情報が付加される。クラスタの代表的パッチをパッチフレーム中の対応する位置に配布する。例えば、座標（１，２）、（２，２）のタグを有する２つのパッチがクラスタに含まれているとき、そのクラスタの代表的パッチをパッチフレームの（１，２）ブロックと（２，２）ブロックに割り当てる。このプロセスを図５に示した。結果として、パッチフレームの各ブロックに複数の候補パッチを割り当ててもよい（各パッチがクラスタを表す）。最適化プロセスにより、ある基準（例えば、空間的平滑性）により、候補パッチから１つのパッチを選択する。一実施形態では、パッチフレームの各ブロック位置に対して、パッチ候補のどのブロック位置にも割り当てられていない第１のパッチを選択する。しかし、割り当てしても、ブロック位置にはまだカラ（empty）のものがあり、パッチにはまだ割り当てられていないものがある。すでにパッチに割り当てられた隣接ブロックとのパッチの互換性を表す尺度により、まだ割り当てられていないパッチをカラ（empty）のブロックに割り当てる。互換性の尺度は、隣接ブロックとのパッチの平均距離と定義される。フィルインプロセスは、隣接ブロックとの互換性の尺度が最もよいカラ（empty）のブロックを選択する。パッチフレーム中のカラ（empty）のブロックが完全には満たされていない場合、そのブロックは一定のカラーで満たされる。この一定のカラーは、一実施形態では、隣接するブロックの平均カラーである。カラのブロックがすべて満たされているが、まだ割り当てられていないパッチが残っている場合、他のパッチフレームを生成し、同じプロセスを繰り返し、まだ割り当てられていないパッチを受け入れる（accommodate）。このプロセスを図６に示した。ここで説明したデータプルーニング方法は、他のビデオ符号化方法とは独立して、又は共に用いることができる。
【００４６】
３．パッチフレームからパッチの抽出と処理
パッチフレームがデコーダ側で受信されると、そのパッチフレーム中の高解像度パッチがブロック分割により抽出される。データが送信前に何らかの符号化方法で符号化されている場合、実行しなければならない復号に加えて、この抽出を行う。抽出されたパッチは、サーチテーブル（すなわち、パッチライブラリ）を生成するのに使われ、「フラットパッチ」又は「非フラットパッチ」のラベルやフラグを付加される。
【００４７】
高解像度パッチのサイズをより小さくすることにより、サーチテーブルを生成する。そのリサイズ比はビデオフレームのリサイズ比と等しい。ダウンサイズしたパッチは、サーチアンドリプレースプロセスにおける高解像度パッチの「キーワード」とみなされる。
【００４８】
タギングプロセスを行い、パッチに「フラットパッチ」又は「非フラットパッチ」のマーク付けをする。フラットパッチは高周波の細部がほとんど又はまったく無いパッチである。サーチアンドリプレースプロセスはフラットパッチをスキップして、置き換えない。フラットパッチは視覚的なアーティファクトを低減するのに有用である。そのようなメカニズムを用いない場合、回復する細部をほとんど含まないパッチは、パッチライブラリ中の他のパッチに引き寄せられ、パッチの置き換えを間違ったり、視覚的なアーティファクトを生じることになるだろう。「フラットパッチ」の分類は、最初に、アップサンプリングと補間（例えば、双三次補間）により、「キーワード」が小さいパッチを高解像度パッチと同じサイズにリサイズすることにより行う。その後、リサイズされたパッチと高解像度パッチとの間の距離を計算する。その距離が所定閾値より小さいとき、高解像度パッチに「フラットパッチ」とマーク付けする。
【００４９】
４．パッチサーチアンドリプレースメント
パッチサーチテーブルを生成してから、パッチサーチアンドリプレースメントプロセスを実行し、低解像度入力フレームを高解像度フレームに変換する。
【００５０】
ダウンサイズされた入力フレームは、最初にアップサンプリングと（例えば、双三次補間を用いた）補間とをされる。次に、サーチアンドリプレースメントプロセスを、ブロックごとに実行する。サーチアンドリプレースメントプロセスにおいて、アップサイズされたフレーム中のブロックではなく、ダウンサイズされた入力フレーム中の対応するブロックをクエリーパッチとして用いることができる。アップサイズされたものは、アップサンプリングと補間のプロセスにより歪んでおり、サーチに小さいパッチを用いる方がいくらか効率的だからである。サーチプロセスはリニアサーチ手順として実行できるが、より高度な、高速なサーチアルゴリズム（例えば、バイナリツリーサーチ）を用いることもできる。サーチテーブル中に最も近いキーワードパッチが見つかると、アルゴリズムはそのパッチの「フラットパッチ」タグを見る。テーブル中のパッチが「フラットパッチ」である場合、アップサイズされたフレーム中の対応する低解像度パッチには失われた部分がないままである。さもなければ、低解像度パッチは、特定されたキーワードパッチに対応する高解像度パッチにより置き換えられる。このプロセスを図７に示した。
【００５１】
５．サーチアンドリプレースメントプロセスの最適化
サーチアンドリプレースプロセスの一問題は、空間的な及び時間的な平滑性を考慮していないことである。結果として、低解像度フレーム中のパッチがパッチテーブル中の間違ったパッチで置き換えられると、視覚的なアーティファクトが生じるおそれがある。この問題を解決する一アプローチは、後処理の利用である。一アプローチは、システムに潜在的なパッチ置き換えエラーを検出させ、そのパッチを平滑化して隣接するパッチと一貫性をもたせることである。しかし、パッチ置き換えエラーを正しく検出するのは困難であり、平滑化によりビデオフレームがぼける可能性がある。
【００５２】
他の一アプローチは、先行技術で用いられる方法、すなわちサーチアンドリプレースメントプロセスを空間的な及び時間的な平滑性を考慮したコスト関数最小化問題として定式化する方法と同様の方法を用いることである。
【００５３】
Ｎ個のパッチがサーチテーブルにあり、Ｍ個のパッチが高解像度パッチと置き換える必要がある低解像度フレームにあると仮定すると、低解像度フレームの各ブロック一には、７通りのパッチ置き換え方法がある。そのため、コスト関数は次の通り定義できる：
【００５４】
【数２】
2013518464.tif 000004
ここで、Ｐｉはパッチテーブル中のパッチの選択であり、１からＮまでの範囲である。λは重み付け係数である。Ｃ１は、クエリーパッチと、パッチテーブル中のＰｉに対応するキーワードパッチとの間の距離を測るコスト関数である。例えば、置き換える低解像度パッチに対応するダウンサイズされたパッチがＩｉであり、インデックスＰｉに対応するパッチテーブル中のキーワードパッチがＧＰｉであるとすると、
＜外１＞
2013518464.tif 000005
を定義することができる。Ｃ２は隣接するパッチの平滑性（smoothness）を測るコスト関数であり、
＜外２＞
2013518464.tif 000006
と定義できる。Ｃ２は、事前に計算してＮ×Ｎ行列として保存しておいてもよい。
【００５５】
上記の定式化は空間的な平滑性のみに適応したものである。時間的平滑性は、他の項を加えることにより容易に組み込むことができる。例えば、
＜外３＞
2013518464.tif 000007
ここで、Ｃ３は時間的一貫性を強制するコスト関数である。
【００５６】
【数３】
2013518464.tif 000008
ここで、Ｊｉは、カレントフレーム中のパッチＩｉに対応する、前のフレーム中のパッチである。動きを考えなければ、Ｊｉは、単にＩｉと同じロケーションにある、前のフレーム中のパッチである。動きを考慮し、かつ前のフレーム中のｋ番目のパッチがＩｉに対応することが動き推定アルゴリズムにより示された場合、ＪｉをＪｋに変更すべきである。μはキーワード一致コストと時間的平滑性コストとの間をバランスさせる重み付け係数である。
【００５７】
式（２）の最適化を解くことは、コンピュータビジョンにおける標準的な問題である。また、例えば、Belief Propagationアルゴリズム、Graph Cutsアルゴリズム、又はモンテカルロシミュレーションなどの、異なる方法で解くこともできる。
【００５８】
図８は、ビデオ圧縮用のデータプルーニングを用いてビデオ符号化する方法８００の一実施形態を示す図である。ビデオシーケンスがプロセスに入力される。このプロセスは、ステップ８１０のパッチ抽出とクラスタリングで始まる。並行して、ステップ８３０でビデオがダウンサイズされる。ステップ８１０でビデオから抽出されたパッチは、ステップ８２０でパッチフレームにパッケージングされる。パッチフレームと、ダウンサイズされたビデオの通常フレームとは、ステップ８４０で、別々に、又は結合されて、デコーダに送信される。
【００５９】
図９は、ビデオ圧縮用のデータプルーニングを用いてビデオ符号化する装置９００の一実施形態を示す図である。ビデオシーケンスは、パッチ抽出・クラスタ化器９１０に入力される。これは、ビデオからパッチを抽出して、クラスタにグループ分けする。パッチ抽出・クラスタ化器９１０の出力は、パッチフレーム・ビデオパッケージング回路９２０と信号通信している。これは、代表的なパッチを見つけてパッチフレームにパッケージングする。入力ビデオシーケンスは、小さいフレームを生成するダウンサイザ９３０にも入力される。パッチフレーム・ビデオパッケージング回路９２０の出力は、送信回路９４０に入力される。送信回路９４０は、ダウンサイザ９３０の出力も入力される。
【００６０】
図１０は、ビデオを復号する方法１０００の一実施形態を示す図である。本方法は、ステップ１０１０で、受信したビデオからパッチを抽出するパッチ抽出及び処理で始まる。受信したビデオは通常のビデオフレームとパッチフレームとから構成されている。ステップ１０１０と並行して、入力された通常のビデオは、ステップ１０２０でアップサンプリングと補間とがなされる。ステップ１０１でパッチが抽出されると、ステップ１０３０でパッチライブラリにオーガナイズされる。アップサンプリングする前のビデオの通常フレームビデオの部分、すなわち低解像度部分を用いて、ステップ１０４０で、ライブラリをサーチする。キーワードはパッチライブラリへのインデックス又はアドレスとして機能する。パッチ置き換えはステップ１０５０で行われる。ステップ１０４０のサーチで見つかったパッチを用いて、アップサンプリングされた通常のビデオフレームのうちの対応するビデオパッチを置き換える。次に、ステップ１０６０で後処理を行い、回復したビデオの空間的・時間的平滑性を改善する。
【００６１】
図１１は、ビデオを復号する装置１１００の一実施形態を示す図である。本装置は、受信ビデオ信号からパッチを抽出し、パッチライブラリを生成するパッチ抽出プロセッサ１１１０を有する。エンコーダからの入力ビデオは、入力ビデオ信号の一部として、又は入力ビデオ信号と共に受信したビデオの通常フレームをアップサンプリング及び補間するリサイジング回路１１２５の入力にも送られる。パッチ抽出プロセッサ１１１０の出力は、パッチサーチ回路１１２０の入力と信号通信している。このパッチサーチ回路１１２０は、アップサンプリング前の通常フレームの、キーワードと呼ばれるビデオの一部分を用いて、パッチライブラリをサーチして、好適な置き換えパッチを探す。パッチサーチ回路１１２０の出力は、パッチ置き換え回路１１３０の第１の入力と信号通信している。このパッチ置き換え回路１１３０は、リサイジング回路１１２０の出力も、第２の入力として受け取る。パッチ置き換え回路１１３０は、ビデオのアップサンプリングされた通常フレーム中のビデオの低解像度部分を、パッチサーチ回路１１２０により見つけられたパッチライブラリからのパッチで置き換える。パッチ置き換え回路１１３０の出力は、ポストプロセッサ１１４０の入力と信号通信している。このポストプロセッサ１１４０は、回復されたビデオの空間的及び時間的平滑性を改善する。
【００６２】
このように、具体的な特徴と態様を有する１つ以上の実施形態を提供する。しかし、説明した実施形態の特徴と態様は、他の実施形態にも適合できる。
【００６３】
例えば、これらの実施形態と特徴をビデオ及び／又はその他のタイプのデータの符号化のコンテクストで用いることができる。また、これらの実施形態と特徴は、標準のコンテクストで用いても、標準のコンテクストで用いるように構成してもよい。かかる標準には、ＡＶＣ、マルチビューコーディング（ＭＶＣ）用のＡＶＣの拡張、スケーラブルビデオコーディング（ＳＶＣ）用のＡＶＣの拡張、提案されている３Ｄビデオコーディング（３ＤＶ）とハイパフォーマンスビデオコーディング（ＨＶＣ）用のＰＥＧ／ＪＶＴ標準、その他の標準（既存のもの又は将来のもの）を用いることができる。もちろん、実施形態と特徴は、必ずしも標準で用いる必要はない。
【００６４】
明細書において、本原理の「一実施形態」等と言う場合、本発明の少なくとも１つの実施形態に含まれるその実施形態に関して説明する具体的な特徴、構造、特性などを意味する。それゆえ、本明細書を通していろいろなところに記載した「一実施形態において」等と言った場合、必ずしもすべてが同じ実施形態を参照するものではない。
【００６５】
ここで説明した実施形態は、方法またはプロセス、装置、またはソフトウェアプログラム、データストリーム、又は信号として実施できる。１つの形式の実施形態の場合で説明した（例えば、方法としてのみ説明した）場合であっても、説明した機能の実施形態は他の形式（例えば、装置やプログラム）でも実施できる。装置は例えば適切なハードウェア、ソフトウェア、及びファームウェアで実施可能である。上記の方法は、例えばプロセッサ等の装置で実施可能である。プロセッサとは、処理装置一般を指し、例えばコンピュータ、マイクロプロセッサ、集積回路、プログラマブル論理デバイスなどを指す。プロセッサは、エンドユーザ間での情報通信を行う、コンピュータ、セルラー電話、ポータブル／パーソナル・デジタル・アシスタント（ＰＤＡ）などのデバイス、及びその他の通信デバイスも含む。
【００６６】
ここに説明した様々なプロセスや機能の実施形態は、様々な機器やアプリケーションに化体でき、特にデータの符号化と復号に関連する機器やアプリケーションに化体できる。かかる装置の例には、エンコーダ、デコーダ、デコーダからの出力を処理するポストプロセッサ、エンコーダに入力を供給するプリプロセッサ、ビデオコーダ、ビデオデコーダ、ビデオコーデック、ウェブサーバ、セットトップボックス、ラップトップ、パーソナルコンピュータ、セルラー電話、ＰＤＡ、その他の通信デバイスが含まれる。言うまでもなく、上記の機器は可動なものであってもよいし、移動体に組み込まれていてもよい。
【００６７】
また、上記の方法は、プロセッサによって実行される命令で実施することができる。かかる命令（及び／又は、一実施形態で生成されるデータ値）は、例えば集積回路、ソフトウェア担体その他の記憶デバイス、例えば、ハードディスク、コンパクトディスク、ランダムアクセスメモリ（ＲＡＭ）、リードオンリーメモリ（ＲＯＭ）に記憶できる。上記の命令は、プロセッサ読み取り可能媒体上に化体されたアプリケーションプログラムであってもよい。命令は、例えば、ハードウェア、ファームウェア、ソフトウェア、又はこれらの組み合わせであってもよい。命令は、例えば、オペレーティングシステム、アプリケーション、又はこれらの組み合わせに見いだすことができる。それゆえ、プロセッサは、プロセスを実行するように構成されたデバイス、及びプロセスを実行する命令を記憶したプロセッサ読み取り可能媒体（記憶デバイスなど）を含むデバイスの両方として特徴付けられる。さらに、プロセッサ読み取り可能媒体は、命令に加えて、又は命令の替わりに、実施形態により生成されたデータ値を記憶することができる。
【００６８】
当業者には言うまでもないが、実施形態は、例えば記憶または送信され得る情報を担うようフォーマットされた種々の信号を生成することもできる。情報には、例えば、方法を実行する命令や、説明した実施形態により生成されるデータが含まれ得る。かかる信号は、（例えば、無線周波数のスペクトルを用いた）電磁波やベースバンド信号などとしてフォーマットし得る。フォーマット化には、例えば、データストリームの符号化、符号化したデータストリームによるキャリアの変調が含まれる。信号が担う情報は例えばアナログ情報やデジタル情報であってもよい。知られているように、信号は様々な異なる有線リンクまたは無線リンクで送信できる。信号はプロセッサ読み取り可能媒体に記憶してもよい。
【００６９】
ここで、本原理に付随する多くの有利性／特徴の一部を説明する。一部は上ですでに述べたことである。例えば、本原理の一利点は、すべてのフレームにおいて、入力ビデオがより小さいサイズに一様にリサイズされており、偽の動きアーティファクトが生じないことである。
【００７０】
他の一利点は、パッチフレームで代表的なパッチを送信することにより、高解像度情報が保存されるので、情報損失が最小化されることである。
【００７１】
さらに別の一利点は、本原理により、ライン又はブロック位置や全射マップなどの追加的メタデータを、サイドチャネルにより送信する必要が無いことである。
【００７２】
実施形態を説明した。しかし、言うまでもなく様々な修正を行うことができる。例えば、別の実施形態の要素を組み合わせ、補充し、修正し、または削除して、他の実施形態を形成してもよい。また、当業者には言うまでもないが、開示した構成やプロセスを他の構成やプロセスで置き換えてもよく、その結果の実施形態が少なくとも実質的に同じ機能を果たし、少なくとも実質的に同じように、開示した実施形態と実質的に同じ結果を達成する。したがって、これらの実施形態やその他の実施形態が本開示では想定されており、本開示の範囲に入る。
【図１Ａ】
2013518464.tif 000009
【図１Ｂ】
2013518464.tif 000010
【図１Ｃ】
2013518464.tif 000011
【図２】
2013518464.tif 000012
【図３】
2013518464.tif 000013
【図４】
2013518464.tif 000014
【図５】
2013518464.tif 000015
【図６】
2013518464.tif 000016
【図７】
2013518464.tif 000017
【図８】
2013518464.tif 000018
【図９】
2013518464.tif 000019
【図１０】
2013518464.tif 000020
【図１１】
2013518464.tif 000021
【国際調査報告】
2013518464.tif 000022
2013518464.tif 000023
2013518464.tif 000024