(57)【要約】      （修正有）【課題】画像のピクセルリストを格納、圧縮及び送信する符号化及び復号する方法と装置を提供する。【解決手段】画像のピクセルは少なくとも１つの関係に従ってクラスタ化される。クラスタはピクセルリストとして格納される。画像と同じサイズの整数行列が生成される。第１のインデックスにある画像のピクセルは１つのリストに属する。リスト中の次のピクセルは第２のインデックスを有する。２つのインデックスにより整数が計算され、行列中の第１のインデックスに格納される。行列はロスレス圧縮法により圧縮される。復号時、画像中の第１のインデックスにあるピクセルがピクセルリストと関連付けられる。画像中の第１のインデックスにある整数により第２のインデックスが計算され、画像中の第２のインデックスにあるピクセルがリストに追加される。【選択図】図６
2018110390.tif 000002
【特許請求の範囲】
【請求項１】
画像のピクセルリストを整数行列に符号化する方法であって、前記行列のサイズは前記画像のサイズと同じであり、本方法は、前記画像中の第１のインデックスにある、前記ピクセルリストのリストに属する第１のピクセルに対して、
前記画像中の第２のインデックスにある、前記リスト中の前記第１のピクセルの次の第２のピクセルを取得することと、
前記第１のインデックス及び／又は前記第２のインデックスに関する整数を前記行列の第１のインデックスに符号化することとを含む、
方法。
【請求項２】
前記ピクセルリストは、前記ピクセルリストのピクセルインデックスの昇順または降順でソートされる、
請求項１に記載の方法。
【請求項３】
符号化される整数は第２のインデックスである、
請求項１または２に記載の方法。
【請求項４】
符号化される整数は第２のインデックスと第１のインデックスとの間の差分である、
請求項１または２に記載の方法。
【請求項５】
画像ロスレス圧縮法で前記行列を圧縮することをさらに含む、
請求項１ないし４いずれか一項に記載の方法。
【請求項６】
前記行列に関連する画像を宛先媒体に送信することをさらに含む、
請求項１ないし５いずれか一項に記載の方法。
【請求項７】
整数行列から画像のピクセルリストを復号する方法であって、前記行列のサイズは前記画像のサイズと同じであり、本方法は、前記画像中の第１のインデックスにある、前記ピクセルリストのリストに属する第１のピクセルに対して、
前記第１のインデックス及び／又は前記画像中の前記第１のインデックスにある整数に従って第２のインデックスを計算することと、
前記画像中の前記第２のインデックスにある第２のピクセルを、前記リスト中の第１のピクセルに次ぐピクセルとして設定することとを含む、
方法。
【請求項８】
前記第２のインデックスは前記行列中の第１のインデックスにある整数である、
請求項７に記載の方法。
【請求項９】
前記第２のインデックスは、前記第１のインデックスと、前記行列中の前記第１のインデックスにある整数との和である、
請求項７に記載の方法。
【請求項１０】
前記リストは生成され、前記第１のピクセルで初期化される、
請求項７に記載の方法。
【請求項１１】
画像ロスレス圧縮法で前記行列を解凍することを最初に含む、
請求項７ないし１０いずれか一項に記載の方法。
【請求項１２】
前記行列に関連する画像を宛先媒体から受信することを最初に含む、
請求項７ないし１１いずれか一項に記載の方法。
【請求項１３】
画像のピクセルリストを整数行列に符号化する装置であって、前記行列のサイズは前記画像のサイズと同じであり、本装置は、少なくとも１つのプロセッサに付随するメモリを有し、該プロセッサは、前記画像中の第１のインデックスにある、前記ピクセルリストのリストに属する第１のピクセルに対して、
前記画像中の第２のインデックスにある、前記リスト中の前記第１のピクセルの次の第２のピクセルを取得し、
前記第１のインデックス及び／又は前記第２のインデックスに関する整数を前記行列の第１のインデックスに符号化するように構成される、
装置。
【請求項１４】
前記プロセッサは、前記ピクセルリストを、前記ピクセルリストのピクセルインデックスの昇順または降順でソートするように構成される、
請求項１３に記載の装置。
【請求項１５】
符号化される整数は第２のインデックスである、
請求項１３または１４に記載の装置。
【請求項１６】
符号化される整数は第２のインデックスと第１のインデックスとの間の差分である、
請求項１３または１４に記載の装置。
【請求項１７】
前記プロセッサは、前記行列を、画像ロスレス圧縮法で圧縮するよう構成される、
請求項１３ないし１６いずれか一項に記載の装置。
【請求項１８】
整数行列から画像のピクセルリストを復号する装置であって、前記行列のサイズは前記画像のサイズと同じであり、本装置は、少なくとも１つのプロセッサに付随するメモリを有し、該プロセッサは、前記画像中の第１のインデックスにある、前記ピクセルリストのリストに属する第１のピクセルに対して、
前記第１のインデックス及び／又は前記画像中の前記第１のインデックスにある整数に従って第２のインデックスを計算し、
前記画像中の前記第２のインデックスにある第２のピクセルを、前記リスト中の第１のピクセルに次ぐピクセルとして設定するように構成される、
装置。
【請求項１９】
前記第２のインデックスは前記行列中の第１のインデックスにある整数である、
請求項１８に記載の装置。
【請求項２０】
前記第２のインデックスは、前記第１のインデックスと、前記行列中の前記第１のインデックスにある整数との和である、
請求項１８に記載の装置。
【請求項２１】
前記プロセッサは、前記リストを生成し、前記第１のピクセルで初期化するように構成される、
請求項１８に記載の装置。
【請求項２２】
画像ロスレス圧縮法で前記行列を解凍することをさらに含む、
請求項１８ないし２１いずれか一項に記載の装置。
【請求項２３】
前記行列に関連する画像を宛先媒体から受信することを最初に含む、
請求項１８ないし２２いずれか一項に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本開示は、例えば画像のピクセルのクラスタリングが画像またはビデオの処理パイプラインの異なる段階で使用される場合、画像のピクセル間の関係を符号化および復号する領域に関する。
【背景技術】
【０００２】
ピクセルクラスタリングは、幅広い画像およびビデオの処理パイプラインのセットにおける必須のステップである。画像の（およびビデオシーケンスならなおさら各画像の）ピクセルをクラスタに集めることは、広範囲の計算のための準備動作である。例えば、コンピュータビジョンでは、画像セグメンテーションは、デジタル画像を複数のセグメント（ピクセルのセットであり、スーパーピクセルとしても知られる）に分割するプロセスである。他の例は多視点画像またはプレノプティック画像により与えられる。かかる画像は異なる視点からキャプチャされた同じビューの画像の配列である。これらの画像は、一般的に、多数の再構成法（リフォーカシング、３次元再構成または写真測量法など）に用いられる。
【０００３】
このような動作は、ピクセル間および画像のサイズおよび数に従って検出または推定する関係に応じて、非常に時間およびリソースを消費する可能性がある。例えば、多視点画像では、３次元空間内の共通点に関連するピクセルのクラスタを読み出すことは、非常に複雑なプロセスである。
【０００４】
画像処理パイプラインは、ネットワークの異なるノードで異なるデバイスによって実行される、接続された画像処理アプリケーションから構成される。同じピクセルクラスタリングは、異なる処理段階に対して有用であり得る。パイプラインのいくつかのノードで数回クラスタリングを計算する必要を避けるために、ピクセルのこのようなクラスタを効率的に符号化し、復号し、スキャンすることが必要である。ピクセルクラスタを符号化する第１の方法は、整数リストのリストを構築すること、すなわち各クラスタについて、ピクセルのインデックスをリストすることである。別の方法は、画像と同じサイズの整数の行列を符号化し、画像の各ピクセルに対して、そのピクセルが属するクラスタの識別子を格納することからなる。これらのアプローチには主に２つの欠点がある。それらが生成する最初のデータは、可逆圧縮に対する準備がされておらず、その結果、圧縮率が低い。第２に、それらは、画像とクラスタの迅速な同時の高速スキャンに適応されていない。これらの欠点を克服する符号化方法および復号方法は無い。
【発明の概要】
【０００５】
本開示の目的は、画像のピクセルリストを格納、圧縮及び送信する符号化及び復号の方法が無いことを解消することである。
【０００６】
本開示の目的は、画像のピクセルリストを格納、圧縮及び送信する符号化及び復号の方法が無いことを解消することである。
【０００７】
本開示は、画像のピクセルリストを整数行列に符号化する方法に関する。この行列は画像と同じサイズで生成される。本方法は、画像中の第１のインデックスにある第１のピクセルに対して、このピクセルはピクセルリストのリストに属し、
−  前記画像中の第２のインデックスにある、前記リスト中の前記第１のピクセルの次の第２のピクセルを取得することと、
−  前記第１のインデックス及び／又は前記第２のインデックスに関する整数を前記行列の第１のインデックスに符号化することとを含む。
【０００８】
本方法の利点は、特に、ピクセルリストがそのピクセルインデックスの昇順または降順でソートされているとき、画像ロスレス圧縮法を用いて高い圧縮レベルで圧縮し易い行列を生成することである。
【０００９】
一実施形態では、符号化される整数は第２のインデックスに等しい。例えば、多視点画像またはコンピュータビジョンの場合、行列は境界がはっきりした整数勾配を含む。このような低周波数行列は、画像ロスレス圧縮アルゴリズムにより非常に高い圧縮レベルで圧縮される。
【００１０】
他の一実施形態では、符号化される整数は、第２のインデックスと第１のインデックスとの間の差分である。例えば、多視点画像またはコンピュータビジョンの場合、行列は同じ整数の大きな領域を含む。ここで再度、このタイプの行列は、画像ロスレス圧縮法により非常に高い圧縮レベルで圧縮される。
【００１１】
具体的な特徴によれば、本方法はさらに、行列に付随する画像を宛先媒体に送信することを含む。宛先媒体はローカルまたはリモートのモジュールまたはデバイスである。
【００１２】
本開示は、整数行列から画像のピクセルリストを復号する方法に関する。行列のサイズは画像のサイズと同じである。本方法は、画像中の第１のインデックスにある、ピクセルリストに属する第１のピクセルに対して、
−  前記第１のインデックス及び／又は前記画像中の前記第１のインデックスにある整数に従って第２のインデックスを計算することと、
−  前記画像中の前記第２のインデックスにある第２のピクセルを、前記リスト中の第１のピクセルに次ぐピクセルとして設定することとを含む。
【００１３】
この方法によれば、各ピクセルリストは同時に復号され、スキャンされる。ピクセル間のかかる関係表現により、画像処理パイプラインの計算ノードが円形のピクセルリストにアクセスできる。
【００１４】
具体的な特徴により、リストが生成され、第１のピクセルで初期化される。
【００１５】
本開示は次の装置にも関する。すなわち、画像のピクセルリストを整数行列に符号化する装置であって、前記行列のサイズは前記画像のサイズと同じであり、本装置は、少なくとも１つのプロセッサに付随するメモリを有し、該プロセッサは、前記画像中の第１のインデックスにある、前記ピクセルリストのリストに属する第１のピクセルに対して、
−  前記画像中の第２のインデックスにある、前記リスト中の前記第１のピクセルの次の第２のピクセルを取得し、
−  前記第１のインデックス及び／又は前記第２のインデックスに関する整数を前記行列の第１のインデックスに符号化するように構成される。
【００１６】
本開示は次の装置にも関する。すなわち、整数行列から画像のピクセルリストを復号する装置であって、前記行列のサイズは前記画像のサイズと同じであり、本装置は、少なくとも１つのプロセッサに付随するメモリを有し、該プロセッサは、前記画像中の第１のインデックスにある、前記ピクセルリストのリストに属する第１のピクセルに対して、
−  前記第１のインデックス及び／又は前記画像中の前記第１のインデックスにある整数に従って第２のインデックスを計算し、
−  前記画像中の前記第２のインデックスにある第２のピクセルを、前記リスト中の第１のピクセルに次ぐピクセルとして設定するように構成される。
【図面の簡単な説明】
【００１７】
添付図面を参照した以下の説明を読めば、本開示をよく理解でき、その他の具体的な特徴と利点がはっきりするであろう。
【図１】本原理の具体的な実施形態による、ピクセルクラスタリングプロセスが適用された画像を示す図である。
【図２】本原理の具体的な実施形態による、ピクセル間の関係が計算された多視点画像を示す図である。
【図３Ａ】本原理の具体的な実施形態による、行ベーススキャンに従って指標付けされた６×４行列のピクセルとしてクラスタ化されたピクセルを有する、図１の画像と比較し得る画像を示す。
【図３Ｂ】本原理の具体的な実施形態による、図３Ａの画像のピクセルのリストを符号化する実施形態を示す図である。
【図３Ｃ】本原理の具体的な実施形態による、図３Ａの画像のピクセルのリストを符号化する他の実施形態を示す図である。
【図４Ａ】本原理の具体的な実施形態による、行ベーススキャンに従って指標付けされた５×４行列のピクセルとしてクラスタ化されたピクセルを有する、図２の画像と比較し得る画像を示す。
【図４Ｂ】本原理の具体的な実施形態による、図４Ａの画像のピクセルのリストを符号化する方法を示す図である。
【図４Ｃ】本原理の具体的な実施形態による、図４Ａの画像のピクセルのリストを符号化する方法を示す図である。
【図５】本原理の具体的な実施形態による、ピクセルのリストを符号化または復号するように構成された装置のハードウェア実施形態を示す図である。
【図６】本原理の具体的な実施形態による、図５の処理デバイスに実装されたピクセルのリストを符号化する方法の実施形態を図式的に示す図である。
【図７】本原理の具体的な実施形態による、図５の処理デバイスに実装されたピクセルのリストを復号する方法の実施形態を図式的に示す図である。
【発明を実施するための形態】
【００１８】
図面を参照して主題を説明する。図面では、同じ参照数字を用いて同じ要素を示す。以下の説明では、説明を目的として、本主題をよく理解できるよう、多数の具体的な詳細事項を記載する。言うまでもなく、主題の実施形態は、これらの具体的な詳細事項が無くても実施できる。
【００１９】
画像処理の分野では、ピクセルの座標を整数インデックスとして符号化することが通常である。インデックスは、行ベース（式［１］による）または列ベース（式［２］による）上で画像をスキャンするときのピクセル数として計算される。この符号化にはいくつかの利点がある。最初の座標は２つではなく１つの整数で表され、インデックスはスキャン操作を反映するように順序付けられる。２つのインデックスの比較は、あるスキャンでピクセルが別のピクセルの前か後にあるかを示す簡単な計算である。この文書ではピクセルインデックスはピクセル座標に相当する。画像の幅と高さおよび選択されたスキャン方法が分かれば、インデックスを座標に変換すること、及びその逆は簡単かつ一般的だからである。
［１］  ｎ＝ｘ＋ｗ＊ｙ    ｛ｘ＝ｎ％ｗ；ｙ＝（ｎ−ｘ）／ｗ｝
［２］  ｎ＝ｙ＋ｈ＊ｘ    ｛ｙ＝ｎ％ｈ；ｘ＝（ｎ−ｙ）／ｈ｝
「ｎ」は座標（ｘ，ｙ）のピクセルのインデックスであり、ｗは画像のピクセル単位の幅であり、ｈは画像のピクセル単位の高さであり、
ｘは［０．．ｗ−１］に属し、ｙは［０．．ｈ−１］に属する。
【００２０】
言うまでもなく、当業者は、ここには明示的に説明や図示はしていないが、本開示の原理を化体する様々な構成を工夫することができる。
【００２１】
本原理の非限定的な実施形態によれば、画像のピクセルのリストを符号化する方法及びデバイスが開示される。画像のピクセルは少なくとも１つの関係に従ってクラスタ化される。通常、コンピュータのメモリの技術的な性質のため、一般的にクラスタまたはセットをアイテムリストとして格納する。リストは、例えばピクセルのリストは、ある順序で、例えば画像中のピクセルのインデックスの昇順または降順で格納されることがある。本原理によれば、画像と同じサイズ（ｗ×ｈ）の整数の行列が生成される。画像のインデックスＮ１にあるピクセルＰ１は１つのリストＬに属する。リストＬ中の次のピクセルは、その画像におけるインデックスＮ２を有するピクセルＰ２である。Ｎ１及び／又はＮ２により整数が計算され、行列中のインデックスＮ１のところに格納される。整数は少なくともその２つのインデックスＮ１とＮ２に応じて計算される。行列に符号化する整数は、インデックスＰ１とインデックスＰ２の少なくとも１つを含むインデックスのグループに対して取得される。例えば、この整数はＮ２である。変形例では、この整数はＮ２−Ｎ１である。この方法をさらに計算例と特殊事例に監視詳細に説明する。生成される行列は、ロスレス圧縮法により圧縮されてもよく、（圧縮されてもよい）画像に関連付けられてもよい。行列と画像は、画像又はビデオの処理パイプラインの次の段階に送られる。
【００２２】
本原理の他の非限定的な実施形態によれば、画像のピクセルのリストを復号する方法及びデバイスが開示される。サイズ（ｗ×ｈ）の画像と同じサイズ（ｗ×ｈ）の整数の行列が入力として受け取られる。これらのデータは潜在的に圧縮され、そうであれば、適切な解凍方法を用いて解凍される。インデックスＮ１を有する画像のピクセルＰ１は、ピクセルのリストＬと関連付けられる。この最初の関連付けの異なる実施形態は、この説明でさらに詳しく説明する。行列中のインデックスＮ１の整数Ｉにより、インデックスＮ２を計算し、画像中のインデックスＮ２のピクセルＰ２をリストＬ中のＰ１の次のピクセルとして設定する。例えば、Ｎ２はＩである。変形例では、Ｎ２＝Ｎ１＋Ｉである。この方法により、リストＬのピクセルを高速にスキャンできる。換言すると、本方法により、リストＬ中のＰ１に関連付けられた画像のすべてのピクセルを高速スキャンすることができる。インデックスＮ２は、インデックスＮ１と整数Ｉとの値の少なくとも一方に従って計算される。インデックスＮ２は、Ｐ１のインデックスと、インデックスＮ１における行列中で読まれる整数Ｉのうち少なくとも１つを含む値のグループに対して取得される。
【００２３】
図１は、ピクセルクラスタ化処理が適用された画像１０を示す。画像１０のピクセルは、例えばコンピュータビジョンアルゴリズムまたはその他の認識アルゴリズムにより、クラスタ化されている。この画像例では、ピクセルは４つのクラスタに集められている。クラスタ１１は象のピクセルを集め、クラスタ１２は空のピクセルを集め、クラスタ１３はブッシュのピクセルを集め、クラスタ１４は樹木のピクセルを集めている。クラスタ１１と１２は連結したピクセルグループであるが、クラスタ１３と１４は複数の区別できる画像領域により構成されている。クラスタは画像ピクセル間の関係に従ってアルゴリズムにより形成されている。図１の例では、ピクセルは、同種のオブジェクトに属するものがグループ分けされている。メモリ中では、ピクセルクラスタはピクセルのリストとして符号化される。これら４つのリストは、行ベーススキャンにより、例えば、ピクセルインデックスの昇順でソートされてもよい。
【００２４】
図２は、ピクセル間の関係が計算された多視点画像２０を示す。画像２０は４×４カメラ配列によりキャプチャされた１６個の部分画像（ｓｕｂ−ｉｍａｇｅｓ）よりなる。カメラによりキャプチャされた３次元（３Ｄ）空間の点が、多視点画像２０上で１６回まである。換言すると、多視点画像の幾つかのピクセルは３Ｄ空間の同じ点を表す。例えば、キャラクタの右眼上のポイントは画像２０上で１２回現れる（実際、画像サンプリングは離散的なので、投影されたピクセルがまったく同じ３Ｄポイントから来るわけではなく、アルゴリズムはコロケーション（ｃｏｌｌｏｃａｔｉｏｎ）を仮定する）。キャラクタの左の靴上のポイント２２は、多視点画像２０上に４回現れる。３Ｄ空間の同じ点から来る多視点（またはプレノプティック）画像ピクセルのクラスタ化は、画像処理パイプラインにおける有用な処理である。しかし、そのようなアルゴリズムには、時間とメモリがかかる。かかるアルゴリズムの結果（すなわち、計算されたピクセル間関係）をパイプラインの別のノードに送るためにそれを符号化することは、それを再び計算しなくてもよくするために重要である。図１のクラスタについて、図２のクラスタはピクセルのリストとして符号化される。これら多数のリストは、行ベーススキャンにより、例えば、ピクセルインデックスの昇順でソートされてもよい。
【００２５】
図３Ａは、行ベーススキャンに従ってインデックスされたピクセルの６×４行列としてクラスタ化されたピクセルを有する画像を示す。ピクセルのインデックスは０から２３までである。２つのクラスタ（白ピクセルとグレーピクセル）を示した。これらは図１に示したアルゴリズムなどから得られる。この例では、２つのクラスタはピクセルのインデックスに従ってソートされたリストにより符号化される。「白」クラスタはピクセル｛０，１，４，５，６，９，１０，１１，１２，１７，１８，１９，２０，２１，２２，２３｝をリストし、「グレー」クラスタはピクセル｛２，３，７，８，１３，１４，１５，１６｝をリストする。かかるクラスタの特殊性は、画像の接続領域を占めることである。
【００２６】
図３Ｂは、図３Ａの画像のピクセルのリストの符号化の一実施形態を示す。リストは、画像と同じサイズの整数行列に符号化される。画像のピクセルに対して、それのインデックスと、それが属するリスト中の次のピクセルのインデックスとに従って整数が計算される。計算された整数は、行列中に、考慮されたピクセルの位置に格納される。この実施形態では、計算された整数はリスト中の次のピクセルのインデックスである。例えば、ピクセル０の場合、白リスト中の次のピクセルはピクセル１であり、ピクセル１の場合、白リスト中の次のピクセルはピクセル４である。整数１は行列中のピクセル０の位置に（すなわち、インデックス０に）格納され、整数４は行列中のピクセル１の位置に（すなわち、インデックス１に）格納される。リストの最後のピクセルの次のピクセルは、そのリストの最初のピクセルである。図３Ａの例では、ピクセル２３の次のピクセルはピクセル０であり、ピクセル１６の次のピクセルはピクセル２である。この例では、符号化するピクセルのリストは、ピクセルのインデックスの昇順に格納される。リストは、画像の接続領域を占めるクラスタを表すので、本原理のこの実施形態は、顕著な境界線を有する行に整数勾配を有する行列を生成するという利点を有する。これは、例えば、図３Ｂの行列の第３行に示されている。整数勾配を有するかかる行列は、画像ロスレス圧縮アルゴリズムで効率的に圧縮できる。行列は非常に軽く送信できるものとなる。
【００２７】
本原理にしたがって、整数行列の復号により、デコーダはピクセルリストを読み出すことができる。そのため、ピクセル間の関係を再計算する必要はない。行列は、圧縮されていれば、適切な解凍アルゴリズムを用いて最初に解凍される。方法は、行列中のデコードされていない位置の整数を考慮することにより始まる。まず初めのステップで、例えば、インデックス０の整数が考慮される。新しいリストが生成され、ピクセル０で始まる：Ｌａ＝｛０｝。行列中のインデックス０の整数が読まれ、この例では１である整数と、この例では０である実際に考慮されるインデックスとに従って、リスト中の次のピクセルのインデックスが計算される。図３Ｂに示す実施形態では、整数は次のピクセルのインデックスである。そのため、リストＬａ＝｛０，１｝にピクセル１が追加される。次いで、計算されたインデックスの整数が読まれ、新しいインデックスが計算される。この例では、ピクセル４がリストに追加される。この操作は、次に計算されるインデックスがリスト中の最初のインデックスになるまで、繰り返される。この時、リストは完成する。リストはデコードされ、効率的にスキャンされている。この方法は、行列中のどのピクセルからでも開始できる。リストが完成すると、前のリストでは考慮されていない整数が考慮され、新しいリストが生成される。例えば、リストＬｂは、リストＬａに属していないピクセル１６で開始される。位置１６における整数が読み取られ、リスト中の次のピクセルが計算される。この例では、ピクセル２がリストＬｂに追加される。この操作は、ピクセル１６がリスト中の次のピクセルとして決定されるまで、繰り返される。すべてのインデックスを考慮した（すべてのピクセルがリストに追加された）とき、各リストは再構成されている。
【００２８】
変形例では、各リストについて、リストの１つのピクセルのインデックスをそのリストに関する情報とペアリングするデータが生成される。これらのデータのセットは行列に付随して送信される。この変形例では、復号方法は、そのデータにより記述されるリストを生成し、ペアリングされたインデックスでそれをデコードし始める。
【００２９】
図３Ｃは、図３Ａの画像のピクセルのリストの符号化の他の一実施形態を示す。この実施形態では、整数はリスト中の次のピクセルのインデックスと、実際に考慮されるインデックスとの間の差分である。例えば、グレーリスト中のピクセル１３を考慮するとき、行列中のインデックス１３に格納された整数は、ピクセルのインデックス１４からインデックス１３を引いた１４−１３＝１である。整数は負であってもよい。例えば、インデックス１６を考えると、リスト中の次のピクセルはインデックス２なので、行列中のインデックス１６に格納される整数は、２−１６＝−１４である。変形例では、図３Ｃに示すように、差分は行列サイズを法として（ｍｏｄｕｌｏ  ｔｈｅ  ｓｉｚｅ  ｏｆ  ｔｈｅ  ｍａｔｒｉｘ）計算される。図３Ｂの例では、行列のインデックス１６に格納された整数は（２−１６）％２４＝１０である。リストがピクセルのインデックスの昇順でソートされているとき、クラスタは画像の接続領域を表すので、行列は１の広い領域を含む（リスト中の次のピクセルが次のインデックスを有することが多いため）。このような行列は、画像ロスレス圧縮アルゴリズムにより高いレベルの圧縮ができる。
【００３０】
復号において、リストは、図３Ｂを参照して説明した実施形態と同様に圧縮された行列を構成する。図３Ｃの実施形態では、考慮中のリスト中の次のピクセルのインデックスは、実際に考慮されているインデックスを行列中のこのインデックスで読み取った整数に加えることによって計算される。例えば、インデックス１２を考えると、行列中のインデックス１２で読み出された整数は５であり、考慮中のリスト中の（ここでは、白リスト中の）次のピクセルはピクセル１２＋５＝１７である。インデックス１６を考えると、読み出される整数は−１４であり、次のピクセルはピクセル２である。図３Ｃに示す変形例では、読み取られた整数は１０であり、リスト中の次のピクセルのインデックスは行列サイズを法として計算され、グレーリスト中の次のピクセルはピクセル（１６＋１０）％２４＝２である。
【００３１】
図４Ａは、行ベーススキャンに従ってインデックスされたピクセルの５×４行列としてクラスタ化されたピクセルを有する画像を示す。ピクセルのインデックスは０から１９までである。２つのクラスタだけが表され、「薄いグレー」のクラスタはピクセル｛０，１１，１７｝をリストし、「濃いグレー」のクラスタはピクセル｛１，１２，１８｝をリストする。各リストにおいて、ピクセルはそのインデックスルの昇順でソートされている。これらは図２に示したアルゴリズムなどから得られる。かかるクラスタの特殊性はピクセルが互いに離れていることである。しかし、２つの隣接するピクセルＰ１１とＰ２１は２つのクラスタＣ１とＣ２に属し、Ｃ１の他のピクセルＰ１２はＣ２の他のピクセルＰ２２に隣接することが多い。ピクセルが、例えば、そのインデックスの昇順で、そのクラスタのリストでソートされている場合、このプロパティはリストに沿って繰り返されることが多い。
【００３２】
図４Ｂは、図３Ｂで説明した実施形態による、図４Ａの画像のピクセルリストを符号化する方法を示す図である。画像と同じサイズの整数行列中の１つの位置において、格納された整数はリスト中の次のピクセルのインデックスである。リストの最後のピクセルの次のピクセルは、そのリストの最初のピクセルである。この種の画像の隣接性のために、リストがソートされているとき、例えばそれらが含むピクセルの昇順にリストがソートされるとき、得られた行列は、整数の勾配を含み、これは画像ロスレス圧縮法によって高レベルの圧縮で圧縮することができる。
【００３３】
図４Ｃは、図３Ｃで説明した実施形態による、図４Ａの画像のピクセルリストを符号化する方法を示す図である。画像と同じサイズの整数行列中の１つの位置において、格納される整数は、リスト中の次のピクセルのインデックスと、その行列中の考慮されている位置のインデックスとの間の差分である。変形例では、この差分は行列のサイズを法として計算される。この種の画像の隣接性のために、リストがソートされているとき、例えばそれらが含むピクセルの昇順にリストがソートされるとき、得られた行列は、同じ整数の広い領域を含み、これは画像ロスレス圧縮法によって高レベルの圧縮で圧縮することができる。
【００３４】
図５は、ピクセルリストを符号化または復号するように構成された装置５０のハードウェア実施形態を示す。この例では、デバイス５０は、アドレスとデータのバス５２（クロック信号も運ぶ）により互いに接続された次の要素を有する：
−  少なくとも１つのマイクロプロセッサ（またはＣＰＵ）５１、
−  ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）タイプの不揮発性メモリ５３、
−  ランダムアクセスメモリすなわちＲＡＭ５４。
【００３５】
また、このデバイスは、
−  グラフィックカード（ＧＰＵ）５５、これはランダムアクセスメモリのレジスタを化体してもよい、
−  一  例えば、マウス、ジョイスティック、ウェブカメラなどである、Ｉ／Ｏ（入出力）デバイスのセット５７、及び
−  電源５６。
【００３６】
有利にも、デバイス５０は、ディスプレイ画面タイプの一以上のディスプレイデバイス（図示せず）に接続され、グラフィックカード５５に直接接続され、グラフィックカードで計算された画像を表示する。変形例では、一以上のディスプレイデバイスは、バス５２を介してグラフィックカード５５に接続されている。
【００３７】
メモリ５３、５４、及び５５の説明で用いる用語「レジスタ」は、上記の各メモリにおける、小容量（少量のバイナリデータ）のメモリ領域、及び（プログラム全体を格納できる、または計算したデータや表示するデータを表すデータのすべて、またはその一部を格納できる）大容量のメモリ領域を言う。
【００３８】
スイッチオンされると、マイクロプロセッサ５１は、ＲＯＭ５３中のプログラムに従って、ＲＡＭ５４中のプログラムの命令をロードして実行する。
具体的な一実施形態によると、本開示及び後で説明する方法のステップを実施するアルゴリズムは、有利にも、これらのステップを実施するデバイス５０に付随するグラフィックカード５５のメモリＧＲＡＭ６２１に格納される。
【００３９】
一変形例では、電源５６は装置５０の外部にある。
【００４０】
図６は、非限定的な有利な実施形態による、デバイス５０などの処理デバイスにおいて実施され、ピクセルリストを符号化する方法６０の一実施形態を模式的に示す。
【００４１】
初期化ステップ６１と６２において、画像のピクセルリストを取得する。本明細書では、ピクセルリストなどのデータの取得は、情報源からのデータの受信として理解すべきである。例えば、情報源は次を含むセットに属する：
−  ローカルメモリであって、例えばビデオメモリまたはＲＡＭ（すなわちランダムアクセスメモリ）、フラッシュメモリ、ＲＯＭ（すなわちリードオンリメモリ）、ハードディスク；
−  ストレージインターフェースであって、例えば大容量記憶装置、ＲＡＭ、フラッシュメモリ、ＲＯＭ、光ディスク、または磁気支持体とのインターフェース；及び
−  通信インターフェースであって、例えば有線インターフェース（例えば、バスインターフェース、広域ネットワークインターフェース、ローカルエリアネットワークインターフェース）または無線インターフェース（例えば、ＩＥＥＥ８０２．１１インターフェースまたはＢｌｕｅｔｏｏｔｈ（登録商標）インターフェース）。
【００４２】
ステップ６１において、画像のサイズを取得し、画像自体が取得されてもよい。有利にもピクセルのリストが、例えば、ピクセルインデックスの昇順でソートされる。ステップ６２において、画像と同じサイズの整数行列を、デバイス５０のＲＡＭ５４に生成する。デフォルト整数値、例えばゼロで初期化されてもよい。変形例では、行列はグラフィックカード５５のメモリに生成され、リストはＧＰＵにより処理される。
【００４３】
ステップ６３において、リストＬのピクセルＰ１を考慮する。それは例えば第１のリストの第１のピクセルである。このピクセルは、画像のスキャニングモードに応じてインデックスＩ１の位置に配置される。本方法はリストＬ中のＰ１の次のピクセルＰ２を選択する。Ｐ２は画像中のインデックスＩ２の位置に配置される。ステップ６４において、整数値ＶはＩ１とＩ２に応じて計算される。例えば、Ｖ＝Ｉ２。変形例では、Ｖ＝Ｉ２−Ｉ１である。他の一変形例では、Ｖ＝（Ｉ２−Ｉ１）％（Ｗ×Ｈ）、ここでＷは画像（または行列）の幅であり、Ｈは画像（または行列）の高さである。所与のＶのＩ２とＩ１を読み出す関数がデコーダに知られている（または送信されている）限り、Ｉ１とＩ２の任意の関数を用いても良い。ステップ６５において、値Ｖは行列中のインデックスＩ１の位置に格納される。有利にも、まだ考慮されていない新しいピクセルがＰ１と選択され、本方法はステップ６３において繰り替えされる。この新しいピクセルは実際のＰ２であってもよい。新しいピクセルがリストの最後のピクセルであるとき、リスト中の次のピクセルはリストの第１のピクセルである。リストのすべてのピクセルが考慮されたら、本方法は他のリストのピクセルに対して繰り返され得る。この操作は有利にも、すべてのリストのすべてのピクセルが考慮されるまで繰り返される。
【００４４】
ステップ６６において、行列は、画像ロスレス圧縮方法により圧縮されてもよく、画像処理パイプラインの他のモジュールに送信される画像に関連付けられてもよい。例えば行列を計算するのに用いる関数を表すパラメータなどの他のデータを、同じ手段で送信しても異なる手段で送信してもよい。
【００４５】
図７は、非限定的な有利な実施形態による、デバイス５０などの処理デバイスにおいて実施される、ピクセルリストをデコードする方法７０の一実施形態を模式的に示す。
【００４６】
初期化ステップ７１において、整数行列が情報尾源から取得される。任意的に、行列は圧縮形式であり、適切な画像ロスレス解凍方法を用いて最初に解凍される。変形例では、付加データが行列と同時に又は別に取得される。例えば、行列と同じサイズの画像を取得してもよい。リストの説明をリストのピクセルとペアリングするデータが取得されてもよい。例えば、ピクセルのリストを符号化するのに用いる関数を表すパラメータも、同じ又は異なる情報源から取得されてもよい。
【００４７】
ステップ７２において、画像中のインデックスＩ１のピクセルＰ１を検討する。このピクセルはリストＬに属することが分かっている。必要であれば、新しいピクセルリストが生成され、ピクセルＰ１で初期化される。行列中のインデックスＩ１において整数値Ｖが読み出される。行列は画像と同じサイズなので、このインデックスは常に存在する。ステップ７３において、Ｉ１とＶにより、第２のインデックスＩ２、例えば、Ｉ２＝Ｖが計算される。変形例では、Ｉ２＝Ｖ＋Ｉ１である。他の一変形例では、Ｉ２＝（Ｖ＋Ｉ１）％（Ｗ×Ｈ）、ここでＷは画像（または行列）の幅であり、Ｈは画像（または行列）の高さである。ステップ７４において、画像中のインデックスＩ２のピクセルＰ２が、リスト中のＰ１に次ぐピクセルとして、リストＬに追加される。有利にも、まだ考慮されていない新しいピクセルがＰ１と選択され、本方法はステップ７２において繰り替えされる。この新しいピクセルは実際のＰ２であってもよい。新しいピクセルがリストの最初のピクセルである場合、リストは完全に復号されスキャンされている。本方法は、まだ考慮されていない画像のピクセルを選択する。画像のすべてのピクセルが考慮された場合、すべてのリストが復号され、スキャンされる。
【００４８】
当然、本開示は上記の実施形態に限定されない。特に、本開示は、ピクセルリストの符号化方法と復号方法に限定されず、整数行列として符号化されたピクセルリストを送信及びスキャンする任意の方法に拡張することもできる。ピクセルリストの符号化と復号に必要な計算の実装は、ｓｈａｄｅｒタイプのマイクロプログラムにおける実装に限定されず、任意のプログラムタイプ、例えばＣＰＵタイプのマイクロプロセッサにより実行できるプログラムにおける実装にも拡張される。本開示の方法の使用は、手順上の実装に限定されず、いくつかのマイクロプロセッサを使用して並行実装にも及ぶ。
【００４９】
ここで説明した実施形態は、方法またはプロセス、装置、またはソフトウェアプログラム、データストリーム、又は信号として実施できる。１つの形式の実施形態の場合で説明した（例えば、方法または装置としてのみ説明した）場合であっても、説明した機能の実施形態は他の形式（例えば、プログラム）でも実施できる。装置は例えば適切なハードウェア、ソフトウェア、及びファームウェアで実施可能である。上記の方法は、例えばプロセッサ等の装置で実施可能である。プロセッサとは、処理装置一般を指し、例えばコンピュータ、マイクロプロセッサ、集積回路、プログラマブル論理デバイスなどを指す。プロセッサは、デバイス及び／又はエンドユーザ間での情報通信を行うスマートフォン、タブレット、コンピュータ、携帯電話、ポータブル／パーソナル・デジタル・アシスタント（ＰＤＡ）などのデバイス、及びその他の通信デバイスも含む。
【００５０】
ここに説明した様々なプロセスやフィーチャの実装は、異なる様々な機器やアプリケーションで実施してもよい。具体的には、例えば、データ符号化、データ復号、ビュー生成、テクスチャ処理、その他の画像処理、及び関係テクスチャ情報及び／又は奥行き情報に関連する機器やアプリケーションで実施してもよい。かかる装置の例には、エンコーダ、デコーダ、デコーダからの出力を処理するポストプロセッサ、エンコーダに入力を供給するプリプロセッサ、ビデオコーダ、ビデオデコーダ、ビデオコーデック、ウェブサーバ、セットトップボックス、ラップトップ、パーソナルコンピュータ、セルラー電話、ＰＤＡ、その他の通信デバイスが含まれる。言うまでもなく、上記の機器は可動なものであってもよいし、移動体に組み込まれていてもよい。
【００５１】
また、上記の方法は、プロセッサによって実行される命令で実施することができる。かかる命令（及び／又は、一実施形態で生成されるデータ値）は、例えば集積回路、ソフトウェア担体その他の記憶デバイス、例えば、ハードディスク、コンパクトディスク（ＣＤ）、光ディスク（例えば、デジタルバーサタイルディスクやデジタルビデオディスクと呼ばれることが多いＤＶＤなど）、ランダムアクセスメモリ（ＲＡＭ）、リードオンリーメモリ（ＲＯＭ）に記憶できる。上記の命令は、プロセッサ読み取り可能媒体上に化体されたアプリケーションプログラムであってもよい。命令は、例えば、ハードウェア、ファームウェア、ソフトウェア、又はこれらの組み合わせであってもよい。命令は、例えば、オペレーティングシステム、アプリケーション、又はこれらの組み合わせに見いだすことができる。それゆえ、プロセッサは、プロセスを実行するように構成されたデバイス、及びプロセスを実行する命令を記憶したプロセッサ読み取り可能媒体（記憶デバイスなど）を含むデバイスの両方として特徴付けられる。さらに、プロセッサ読み取り可能媒体は、命令に加えて、又は命令の替わりに、実施形態により生成されたデータ値を記憶することができる。
【００５２】
当業者には言うまでもないが、実施形態は、例えば記憶または送信され得る情報を担うようフォーマットされた種々の信号を生成することもできる。情報には、例えば、方法を実行する命令や、説明した実施形態により生成されるデータが含まれ得る。例えば、信号は、データとして、説明した実施形態のシンタックスを書き込み又は読み出しする規則を担うようにフォーマットされてもよいし、又はデータとして、説明した実施形態により書き込まれた実際のシンタックス値を担うようにフォーマットされてもよい。かかる信号は、（例えば、無線周波数のスペクトルを用いた）電磁波やベースバンド信号などとしてフォーマットし得る。フォーマット化には、例えば、データストリームの符号化、符号化したデータストリームによるキャリアの変調が含まれる。信号が担う情報は例えばアナログ情報やデジタル情報であってもよい。知られているように、信号は様々な異なる有線リンクまたは無線リンクで送信できる。信号はプロセッサ読み取り可能媒体に記憶してもよい。
【００５３】
実施形態を説明した。しかし、言うまでもなく様々な修正を行うことができる。例えば、別の実施形態の要素を組み合わせ、補充し、修正し、または削除して、他の実施形態を形成してもよい。また、当業者には言うまでもないが、開示した構成やプロセスを他の構成やプロセスで置き換えてもよく、その結果の実施形態が少なくとも実質的に同じ機能を果たし、少なくとも実質的に同じように、開示した実施形態と実質的に同じ結果を達成する。したがって、本願ではこれらの実施形態及びその他の実施形態を想定している。
【図１】
2018110390.tif 000003
【図２】
2018110390.tif 000004
【図３Ａ】
2018110390.tif 000005
【図３Ｂ】
2018110390.tif 000006
【図３Ｃ】
2018110390.tif 000007
【図４Ａ】
2018110390.tif 000008
【図４Ｂ】
2018110390.tif 000009
【図４Ｃ】
2018110390.tif 000010
【図５】
2018110390.tif 000011
【図６】
2018110390.tif 000012
【図７】
2018110390.tif 000013
【外国語明細書】
2018110390000001.pdf