(57)【要約】【課題】画像変換用の座標変換テーブルに対して効率的な圧縮を行い、必要なメモリのコストダウンを図る。【解決手段】データ入力部２１０により画像変換用の座標変換テーブルを元配列データＲとして入力し、ブロック分割部２２０において複数のブロックに分割する。１ブロックを構成するＭ行Ｎ列の配列データは作業用メモリ２３１に格納される。当該配列データを構成する個々のセル内の数値に対して、横方向第１置換部２３２によって横方向の差分値に置換する処理が行われ、続いて、縦方向第２置換部２３４によって縦方向の差分値に置換する処理が行われる。ブロック間差分演算部２４０では、更に、ブロック間についての差分演算が行われ、最終的な圧縮配列データＷがデータ出力部２５０から出力される。画像変換装置では、こうして圧縮された座標変換テーブルをメモリに格納し、必要に応じてこれを伸張して参照しながら画像変換を実行する。【選択図】図２７
2014082660.tif 000002
【特許請求の範囲】
【請求項１】
複数の行および複数の列を有する配列データを圧縮する方法であって、
コンピュータが、行列状に並んだ各セルについての数値の集合体からなる圧縮対象配列データを入力するデータ入力段階と、
コンピュータが、少なくとも所定の基準列に属するセルを除いて、前記圧縮対象配列データの個々のセル内の数値を、左もしくは右に隣接するセル内の数値との差分値に置き換える作業を含む置換処理を実行することにより、第１差分配列データを作成する第１差分演算段階と、
コンピュータが、少なくとも所定の基準行に属するセルを除いて、前記第１差分配列データの個々のセル内の数値を、上もしくは下に隣接するセル内の数値との差分値に置き換える作業を含む置換処理を実行することにより、第２差分配列データを作成する第２差分演算段階と、
を有することを特徴とする配列データの圧縮方法。
【請求項２】
請求項１に記載の圧縮方法において、
第１差分演算段階で、少なくとも所定の基準列に属するセルを除いて、個々のセル内の数値を、左もしくは右に隣接するセル内の数値との差分値に置換した後、更に、前記基準列に属するセルのうち少なくとも所定の基準セルを除いて、個々のセル内の数値を、上もしくは下に隣接するセル内の数値との差分値に置換することにより、第１差分配列データを作成することを特徴とする配列データの圧縮方法。
【請求項３】
請求項１または２に記載の圧縮方法において、
第２差分演算段階で、少なくとも所定の基準行に属するセルを除いて、個々のセル内の数値を、上もしくは下に隣接するセル内の数値との差分値に置換した後、更に、前記基準行に属するセルのうち少なくとも所定の基準セルを除いて、個々のセル内の数値を、右もしくは左に隣接するセル内の数値との差分値に置換することにより、第２差分配列データを作成することを特徴とする配列データの圧縮方法。
【請求項４】
請求項１〜３のいずれかに記載の圧縮方法を用いて圧縮された配列データを伸張する方法であって、
コンピュータが、伸張対象となる圧縮配列データを入力するデータ入力段階と、
コンピュータが、第２差分演算段階で置換された値を置換前の値に復元する段階と、
コンピュータが、第１差分演算段階で置換された値を置換前の値に復元する段階と、
を有することを特徴とする配列データの伸張方法。
【請求項５】
ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像を、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる変換画像に変換する画像変換方法であって、
コンピュータが、原画像と変換画像との間の幾何学的な関係に基づいて、変換画像を構成する各画素について、原画像上の対応点の座標値（ｘ，ｙ）を求める対応点演算段階と、
コンピュータが、変換画像を構成する各画素について前記対応点演算段階で求められた座標値ｘを並べたＸ座標変換テーブルと、変換画像を構成する各画素について前記対応点演算段階で求められた座標値ｙを並べたＹ座標変換テーブルと、をメモリに格納する変換テーブル格納段階と、
コンピュータが、原画像を構成する各画素の画素値を入力する原画像入力段階と、
コンピュータが、変換画像を構成する各画素について、前記Ｘ座標変換テーブルおよびＹ座標変換テーブルを参照し、原画像上の対応点の座標値（ｘ，ｙ）を認識する対応座標認識段階と、
コンピュータが、認識した座標値（ｘ，ｙ）の近傍に位置する原画像上の画素の画素値に基づいて、変換画像を構成する画素の画素値を決定する画素値決定段階と、
を有し、
前記変換テーブル格納段階において、Ｘ座標変換テーブルおよびＹ座標変換テーブルを、請求項１〜３のいずれかに記載の配列データ圧縮方法を利用して圧縮した状態でメモリに格納し、
前記対応座標認識段階において、請求項４に記載の配列データ伸張方法を利用して伸張したＸ座標変換テーブルおよびＹ座標変換テーブルを参照することにより、対応点の座標値（ｘ，ｙ）を認識することを特徴とする画像変換方法。
【請求項６】
複数Ｍ行および複数Ｎ列を有する配列データを圧縮する方法であって、
コンピュータが、Ｍ行Ｎ列の行列状に並んだセル群について、第ｉ行第ｊ列目のセル内の数値ｘ（ｉ，ｊ）の集合体（但し、１≦ｉ≦Ｍ，１≦ｊ≦Ｎ）からなる圧縮対象配列データを入力するデータ入力段階と、
コンピュータが、Ｄ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ＋１）−ｘ（ｉ，ｊ）なる演算式もしくはＤ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ）−ｘ（ｉ，ｊ＋１）なる演算式に基づいて、前記圧縮対象配列データの第ｉ行第（ｊ＋１）列目のセル内の数値ｘ（ｉ，ｊ＋１）を差分値Ｄ（ｉ，ｊ＋１）に置換する処理を、ｉ＝１〜Ｍおよびｊ＝１〜Ｎ−１の各組み合わせについて実行する横方向第１置換段階と、
コンピュータが、Ｄ（ｉ＋１，１）＝ｘ（ｉ＋１，１）−ｘ（ｉ，１）なる演算式もしくはＤ（ｉ＋１，１）＝ｘ（ｉ，１）−ｘ（ｉ＋１，１）なる演算式に基づいて、前記横方向第１置換段階後の配列データの第（ｉ＋１）行第１列目のセル内の数値ｘ（ｉ＋１，１）を差分値Ｄ（ｉ＋１，１）に置換する処理を、ｉ＝１〜Ｍ−１について実行することにより、第１差分配列データを作成する縦方向第１置換段階と、
コンピュータが、Ｅ（ｉ＋１，ｊ）＝Ｄ（ｉ＋１，ｊ）−Ｄ（ｉ，ｊ）なる演算式もしくはＥ（ｉ＋１，ｊ）＝Ｄ（ｉ，ｊ）−Ｄ（ｉ＋１，ｊ）なる演算式に基づいて、前記第１差分配列データの第（ｉ＋１）行第ｊ列目のセル内の数値Ｄ（ｉ＋１，ｊ）を差分値Ｅ（ｉ＋１，ｊ）に置換する処理を、ｉ＝１〜Ｍ−１およびｊ＝１〜Ｎの各組み合わせ（但し、ｉ＝１，ｊ＝１の組み合わせは除く）について実行する縦方向第２置換段階と、
コンピュータが、Ｅ（１，ｊ＋１）＝Ｄ（１，ｊ＋１）−Ｄ（１，ｊ）なる演算式もしくはＥ（１，ｊ＋１）＝Ｄ（１，ｊ）−Ｄ（１，ｊ＋１）なる演算式に基づいて、前記縦方向第２置換段階後の配列データの第１行第（ｊ＋１）列目のセル内の数値Ｄ（１，ｊ＋１）を差分値Ｅ（１，ｊ＋１）に置換する処理を、ｊ＝２〜Ｎ−１について実行することにより、第２差分配列データを作成する横方向第２置換段階と、
を有することを特徴とする配列データの圧縮方法。
【請求項７】
請求項６に記載の圧縮方法において、
コンピュータが、複数μ行および複数ν列を有する元配列データ（但し、μ＞Ｍ，ν＞Ｎ）を、複数Ｍ行および複数Ｎ列を有する配列データからなる複数Ｋ個のブロックに分割するブロック分割段階を更に有し、
個々のブロックを構成する配列データをそれぞれ圧縮対象配列データとして、横方向第１置換段階、縦方向第１置換段階、縦方向第２置換段階、横方向第２置換段階を行って第２差分配列データを作成し、
少なくとも所定の基準ブロックを除いて、個々のブロックを構成する第２差分配列データの第１行第１列目のセル、第１行第２列目のセル、第２行第１列目のセル内の数値を、隣接するブロック内の対応位置のセル内の数値との差分値に置換して、第３差分配列データを作成するブロック間差分演算段階を更に有することを特徴とする配列データの圧縮方法。
【請求項８】
請求項６または７に記載の圧縮方法において、
コンピュータが、第２差分配列データもしくは第３差分配列データを、１行目の配列データ、２行目の配列データ、３行目以降の配列データについて、それぞれ異なるフォーマットで符号化するデータ符号化段階を更に有することを特徴とする配列データの圧縮方法。
【請求項９】
請求項８に記載の圧縮方法において、
１行目の配列データについては、１列目のセル内の数値と、２列目のセル内の数値と、３列目以降のセル内の数値と、について、それぞれ異なるフォーマットで符号化し、
２行目の配列データについては、１列目のセル内の数値と、２列目以降のセル内の数値と、について、それぞれ異なるフォーマットで符号化し、
３行目以降の配列データについては、各セル内の数値を同一のフォーマットで符号化することを特徴とする配列データの圧縮方法。
【請求項１０】
請求項６に記載の圧縮方法を用いて圧縮された配列データを伸張する方法であって、
コンピュータが、第２差分配列データについて、横方向第２置換段階において置換されていた差分値Ｅを元の数値Ｄに復元する横方向第２置換復元段階と、
コンピュータが、前記横方向第２置換復元段階で復元されたデータについて、縦方向第２置換段階において置換されていた差分値Ｅを元の数値Ｄに復元して第１差分配列データを得る縦方向第２置換復元段階と、
コンピュータが、第１差分配列データについて、縦方向第１置換段階において置換されていた差分値Ｄを元の数値ｘに復元する縦方向第１置換復元段階と、
コンピュータが、前記縦方向第１置換復元段階で復元されたデータについて、横方向第１置換段階において置換されていた差分値Ｄを元の数値ｘに復元して圧縮対象配列データを得る横方向第１置換復元段階と、
を有することを特徴とする配列データの伸張方法。
【請求項１１】
請求項７に記載の圧縮方法を用いて圧縮された配列データを伸張する方法であって、
コンピュータが、第３差分配列データについて、ブロック間差分演算段階において置換されていた差分値を元の数値に復元して第２差分配列データを得るブロック復元演算段階と、
コンピュータが、個々のブロックの第２差分配列データについて、請求項１０に記載の横方向第２置換復元段階および縦方向第２置換復元段階を実行して、第１差分配列データを得る第２差分復元段階と、
コンピュータが、個々のブロックの第１差分配列データについて、請求項１０に記載の縦方向第１置換復元段階および横方向第１置換復元段階を実行して、圧縮対象配列データを得る第１差分復元段階と、
コンピュータが、個々のブロックの前記圧縮対象配列データを合成して元配列データを得るブロック合成段階と、
を有することを特徴とする配列データの伸張方法。
【請求項１２】
ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像を、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる変換画像に変換する画像変換方法であって、
コンピュータが、原画像と変換画像との間の幾何学的な関係に基づいて、変換画像を構成する各画素について、原画像上の対応点の座標値（ｘ，ｙ）を求める対応点演算段階と、
コンピュータが、変換画像を構成する各画素について前記対応点演算段階で求められた座標値ｘを並べたＸ座標変換テーブルと、変換画像を構成する各画素について前記対応点演算段階で求められた座標値ｙを並べたＹ座標変換テーブルと、をメモリに格納する変換テーブル格納段階と、
コンピュータが、原画像を構成する各画素の画素値を入力する原画像入力段階と、
コンピュータが、変換画像を構成する各画素について、前記Ｘ座標変換テーブルおよびＹ座標変換テーブルを参照し、原画像上の対応点の座標値（ｘ，ｙ）を認識する対応座標認識段階と、
コンピュータが、認識した座標値（ｘ，ｙ）の近傍に位置する原画像上の画素の画素値に基づいて、変換画像を構成する画素の画素値を決定する画素値決定段階と、
を有し、
前記変換テーブル格納段階において、Ｘ座標変換テーブルおよびＹ座標変換テーブルを、請求項６に記載の配列データ圧縮方法を利用して圧縮した状態でメモリに格納し、
前記対応座標認識段階において、請求項１０に記載の配列データ伸張方法を利用して伸張したＸ座標変換テーブルおよびＹ座標変換テーブルを参照することにより、対応点の座標値（ｘ，ｙ）を認識することを特徴とする画像変換方法。
【請求項１３】
ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像を、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる変換画像に変換する画像変換方法であって、
コンピュータが、原画像と変換画像との間の幾何学的な関係に基づいて、変換画像を構成する各画素について、原画像上の対応点の座標値（ｘ，ｙ）を求める対応点演算段階と、
コンピュータが、変換画像を構成する各画素について前記対応点演算段階で求められた座標値ｘを並べたＸ座標変換テーブルと、変換画像を構成する各画素について前記対応点演算段階で求められた座標値ｙを並べたＹ座標変換テーブルと、をメモリに格納する変換テーブル格納段階と、
コンピュータが、原画像を構成する各画素の画素値を入力する原画像入力段階と、
コンピュータが、変換画像を構成する各画素について、前記Ｘ座標変換テーブルおよびＹ座標変換テーブルを参照し、原画像上の対応点の座標値（ｘ，ｙ）を認識する対応座標認識段階と、
コンピュータが、認識した座標値（ｘ，ｙ）の近傍に位置する原画像上の画素の画素値に基づいて、変換画像を構成する画素の画素値を決定する画素値決定段階と、
を有し、
前記変換テーブル格納段階において、Ｘ座標変換テーブルおよびＹ座標変換テーブルを、請求項７に記載の配列データ圧縮方法を利用して圧縮した状態でメモリに格納し、
前記対応座標認識段階において、請求項１１に記載の配列データ伸張方法のうちのブロック合成段階を除く部分を利用して、必要なブロックごとに伸張したＸ座標変換テーブルおよびＹ座標変換テーブルを参照することにより、対応点の座標値（ｘ，ｙ）を認識することを特徴とする画像変換方法。
【請求項１４】
請求項１〜１３のいずれかに記載の配列データの圧縮方法、配列データの伸張方法、もしくは画像変換方法をコンピュータに実行させるプログラム。
【請求項１５】
請求項１〜１３のいずれかに記載の配列データの圧縮方法、配列データの伸張方法、もしくは画像変換方法を実行するプログラムが組み込まれたコンピュータとして機能する集積回路。
【請求項１６】
複数の行および複数の列を有する配列データを圧縮する装置であって、
行列状に並んだ各セルについての数値の集合体からなる圧縮対象配列データを格納する作業用メモリと、
少なくとも所定の基準列に属するセルを除いて、前記圧縮対象配列データの個々のセル内の数値を、左もしくは右に隣接するセル内の数値との差分値に置き換える作業を含む置換処理を実行することにより、第１差分配列データを作成する第１差分演算部と、
少なくとも所定の基準行に属するセルを除いて、前記第１差分配列データの個々のセル内の数値を、上もしくは下に隣接するセル内の数値との差分値に置き換える作業を含む置換処理を実行することにより、第２差分配列データを作成する第２差分演算部と、
を備えることを特徴とする配列データの圧縮装置。
【請求項１７】
請求項１６に記載の圧縮装置を用いて圧縮された圧縮配列データを伸張する装置であって、
第２差分配列データを格納する作業用メモリと、
第２差分配列データについて、第２差分演算部で置換された値を置換前の値に戻すことにより第１差分配列データを復元する第２差分復元部と、
前記第１差分配列データについて、第１差分演算部で置換された値を置換前の値に戻すことにより圧縮対象配列データを復元する第１差分復元部と、
を備えることを特徴とする配列データの伸張装置。
【請求項１８】
ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像を、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる変換画像に変換する画像変換装置であって、
変換処理用メモリと、
前記変換処理用メモリに原画像を入力する原画像入力部と、
前記変換処理用メモリに得られた変換画像を出力する変換画像出力部と、
前記変換処理用メモリに、変換に用いるＸ座標変換テーブルおよびＹ座標変換テーブルを設定する変換テーブル設定部と、
変換画像を構成する各画素について、前記Ｘ座標変換テーブルおよびＹ座標変換テーブルを参照することにより原画像上の対応点の座標値（ｘ，ｙ）を認識し、認識した座標値（ｘ，ｙ）の近傍に位置する原画像上の画素の画素値に基づいて画素値を決定し、前記変換処理用メモリ上に変換画像を生成する変換処理部と、
を備え、
前記変換テーブル設定部内には、請求項１６に記載の配列データの圧縮装置が組み込まれており、前記変換テーブル設定部は、当該圧縮装置を利用してＸ座標変換テーブルおよびＹ座標変換テーブルを圧縮して前記変換処理用メモリに設定し、
前記変換処理部内には、請求項１７に記載の配列データの伸張装置が組み込まれており、前記変換処理部は、当該伸張装置を利用して伸張したＸ座標変換テーブルおよびＹ座標変換テーブルを参照することにより、対応点の座標値（ｘ，ｙ）を認識することを特徴とする画像変換装置。
【請求項１９】
複数Ｍ行および複数Ｎ列を有する配列データを圧縮する装置であって、
Ｍ行Ｎ列の行列状に並んだセル群について、第ｉ行第ｊ列目のセル内の数値ｘ（ｉ，ｊ）の集合体（但し、１≦ｉ≦Ｍ，１≦ｊ≦Ｎ）からなる圧縮対象配列データを格納する作業用メモリと、
Ｄ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ＋１）−ｘ（ｉ，ｊ）なる演算式もしくはＤ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ）−ｘ（ｉ，ｊ＋１）なる演算式に基づいて、前記圧縮対象配列データの第ｉ行第（ｊ＋１）列目のセル内の数値ｘ（ｉ，ｊ＋１）を差分値Ｄ（ｉ，ｊ＋１）に置換する置換処理を、ｉ＝１〜Ｍおよびｊ＝１〜Ｎ−１の各組み合わせについて実行する横方向第１置換部と、
Ｄ（ｉ＋１，１）＝ｘ（ｉ＋１，１）−ｘ（ｉ，１）なる演算式もしくはＤ（ｉ＋１，１）＝ｘ（ｉ，１）−ｘ（ｉ＋１，１）なる演算式に基づいて、前記横方向第１置換部による置換処理後の配列データの第（ｉ＋１）行第１列目のセル内の数値ｘ（ｉ＋１，１）を差分値Ｄ（ｉ＋１，１）に置換する置換処理を、ｉ＝１〜Ｍ−１について実行することにより、第１差分配列データを作成する縦方向第１置換部と、
Ｅ（ｉ＋１，ｊ）＝Ｄ（ｉ＋１，ｊ）−Ｄ（ｉ，ｊ）なる演算式もしくはＥ（ｉ＋１，ｊ）＝Ｄ（ｉ，ｊ）−Ｄ（ｉ＋１，ｊ）なる演算式に基づいて、前記第１差分配列データの第（ｉ＋１）行第ｊ列目のセル内の数値Ｄ（ｉ＋１，ｊ）を差分値Ｅ（ｉ＋１，ｊ）に置換する置換処理を、ｉ＝１〜Ｍ−１およびｊ＝１〜Ｎの各組み合わせ（但し、ｉ＝１，ｊ＝１の組み合わせは除く）について実行する縦方向第２置換部と、
Ｅ（１，ｊ＋１）＝Ｄ（１，ｊ＋１）−Ｄ（１，ｊ）なる演算式もしくはＥ（１，ｊ＋１）＝Ｄ（１，ｊ）−Ｄ（１，ｊ＋１）なる演算式に基づいて、前記縦方向第２置換部による置換処理後の配列データの第１行第（ｊ＋１）列目のセル内の数値Ｄ（１，ｊ＋１）を差分値Ｅ（１，ｊ＋１）に置換する置換処理を、ｊ＝２〜Ｎ−１について実行することにより、第２差分配列データを作成する横方向第２置換部と、
を備えることを特徴とする配列データの圧縮装置。
【請求項２０】
請求項１９に記載の圧縮装置を用いて圧縮された圧縮配列データを伸張する装置であって、
第２差分配列データを格納する作業用メモリと、
第２差分配列データについて、横方向第２置換部において置換された差分値Ｅを元の数値Ｄに復元する横方向第２置換復元部と、
前記横方向第２置換復元部で復元されたデータについて、縦方向第２置換部において置換された差分値Ｅを元の数値Ｄに復元して第１差分配列データを得る縦方向第２置換復元部と、
前記第１差分配列データについて、縦方向第１置換部において置換された差分値Ｄを元の数値ｘに復元する縦方向第１置換復元部と、
前記縦方向第１置換復元部で復元されたデータについて、横方向第１置換部において置換された差分値Ｄを元の数値ｘに復元して圧縮対象配列データを得る横方向第１置換復元部と、
を備えることを特徴とする配列データの伸張装置。
【請求項２１】
ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像を、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる変換画像に変換する画像変換装置であって、
変換処理用メモリと、
前記変換処理用メモリに原画像を入力する原画像入力部と、
前記変換処理用メモリに得られた変換画像を出力する変換画像出力部と、
前記変換処理用メモリに、変換に用いるＸ座標変換テーブルおよびＹ座標変換テーブルを設定する変換テーブル設定部と、
変換画像を構成する各画素について、前記Ｘ座標変換テーブルおよびＹ座標変換テーブルを参照することにより原画像上の対応点の座標値（ｘ，ｙ）を認識し、認識した座標値（ｘ，ｙ）の近傍に位置する原画像上の画素の画素値に基づいて画素値を決定し、前記変換処理用メモリ上に変換画像を生成する変換処理部と、
を備え、
前記変換テーブル設定部内には、請求項１９に記載の配列データの圧縮装置が組み込まれており、前記変換テーブル設定部は、当該圧縮装置を利用してＸ座標変換テーブルおよびＹ座標変換テーブルを圧縮して前記変換処理用メモリに設定し、
前記変換処理部内には、請求項２０に記載の配列データの伸張装置が組み込まれており、前記変換処理部は、当該伸張装置を利用して伸張したＸ座標変換テーブルおよびＹ座標変換テーブルを参照することにより、対応点の座標値（ｘ，ｙ）を認識することを特徴とする画像変換装置。
【請求項２２】
複数μ行および複数ν列を有する元配列データを圧縮する装置であって、
元配列データを入力する元配列データ入力部と、
入力した元配列データを、それぞれが複数Ｍ行および複数Ｎ列を有する配列データ（但し、μ＞Ｍ，ν＞Ｎ）からなる複数Ｋ個のブロックに分割するブロック分割部と、
個々のブロックのＭ行Ｎ列の行列状に並んだセル群について、第ｉ行第ｊ列目のセル内の数値ｘ（ｉ，ｊ）の集合体（但し、１≦ｉ≦Ｍ，１≦ｊ≦Ｎ）からなる圧縮対象配列データを格納する作業用メモリと、
Ｄ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ＋１）−ｘ（ｉ，ｊ）なる演算式もしくはＤ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ）−ｘ（ｉ，ｊ＋１）なる演算式に基づいて、前記圧縮対象配列データの第ｉ行第（ｊ＋１）列目のセル内の数値ｘ（ｉ，ｊ＋１）を差分値Ｄ（ｉ，ｊ＋１）に置換する置換処理を、ｉ＝１〜Ｍおよびｊ＝１〜Ｎ−１の各組み合わせについて実行する横方向第１置換部と、
Ｄ（ｉ＋１，１）＝ｘ（ｉ＋１，１）−ｘ（ｉ，１）なる演算式もしくはＤ（ｉ＋１，１）＝ｘ（ｉ，１）−ｘ（ｉ＋１，１）なる演算式に基づいて、前記横方向第１置換部による置換処理後の配列データの第（ｉ＋１）行第１列目のセル内の数値ｘ（ｉ＋１，１）を差分値Ｄ（ｉ＋１，１）に置換する置換処理を、ｉ＝１〜Ｍ−１について実行することにより、第１差分配列データを作成する縦方向第１置換部と、
Ｅ（ｉ＋１，ｊ）＝Ｄ（ｉ＋１，ｊ）−Ｄ（ｉ，ｊ）なる演算式もしくはＥ（ｉ＋１，ｊ）＝Ｄ（ｉ，ｊ）−Ｄ（ｉ＋１，ｊ）なる演算式に基づいて、前記第１差分配列データの第（ｉ＋１）行第ｊ列目のセル内の数値Ｄ（ｉ＋１，ｊ）を差分値Ｅ（ｉ＋１，ｊ）に置換する置換処理を、ｉ＝１〜Ｍ−１およびｊ＝１〜Ｎの各組み合わせ（但し、ｉ＝１，ｊ＝１の組み合わせは除く）について実行する縦方向第２置換部と、
Ｅ（１，ｊ＋１）＝Ｄ（１，ｊ＋１）−Ｄ（１，ｊ）なる演算式もしくはＥ（１，ｊ＋１）＝Ｄ（１，ｊ）−Ｄ（１，ｊ＋１）なる演算式に基づいて、前記縦方向第２置換部による置換処理後の配列データの第１行第（ｊ＋１）列目のセル内の数値Ｄ（１，ｊ＋１）を差分値Ｅ（１，ｊ＋１）に置換する置換処理を、ｊ＝２〜Ｎ−１について実行することにより、第２差分配列データを作成する横方向第２置換部と、
少なくとも所定の基準ブロックを除いて、個々のブロックを構成する第２差分配列データの第１行第１列目のセル、第１行第２列目のセル、第２行第１列目のセル内の数値を、隣接するブロック内の対応位置のセル内の数値との差分値に置換して、第３差分配列データを作成するブロック間差分演算部と、
個々のブロックについての第２差分配列データもしくは第３差分配列データを、圧縮配列データとして出力する圧縮配列データ出力部と、
を備えることを特徴とする配列データの圧縮装置。
【請求項２３】
請求項２２に記載の圧縮装置を用いて圧縮された配列データを伸張する装置であって、
圧縮配列データを入力する圧縮配列データ入力部と、
入力した圧縮配列データのうちの第３差分配列データについて、ブロック間差分演算部において置換された差分値を元の数値に復元して第２差分配列データを得るブロック復元演算部と、
各ブロックの第２差分配列データを格納する作業用メモリと、
第２差分配列データについて、横方向第２置換部において置換された差分値Ｅを元の数値Ｄに復元する横方向第２置換復元部と、
前記横方向第２置換復元部で復元されたデータについて、縦方向第２置換部において置換された差分値Ｅを元の数値Ｄに復元して第１差分配列データを得る縦方向第２置換復元部と、
前記第１差分配列データについて、縦方向第１置換部において置換された差分値Ｄを元の数値ｘに復元する縦方向第１置換復元部と、
前記縦方向第１置換復元部で復元されたデータについて、横方向第１置換部において置換された差分値Ｄを元の数値ｘに復元して圧縮対象配列データを得る横方向第１置換復元部と、
個々のブロックの前記圧縮対象配列データを合成して元配列データを得るブロック合成部と、
を備えることを特徴とする配列データの伸張装置。
【請求項２４】
ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像を、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる変換画像に変換する画像変換装置であって、
変換処理用メモリと、
前記変換処理用メモリに原画像を入力する原画像入力部と、
前記変換処理用メモリに得られた変換画像を出力する変換画像出力部と、
前記変換処理用メモリに、変換に用いるＸ座標変換テーブルおよびＹ座標変換テーブルを設定する変換テーブル設定部と、
変換画像を構成する各画素について、前記Ｘ座標変換テーブルおよびＹ座標変換テーブルを参照することにより原画像上の対応点の座標値（ｘ，ｙ）を認識し、認識した座標値（ｘ，ｙ）の近傍に位置する原画像上の画素の画素値に基づいて画素値を決定し、前記変換処理用メモリ上に変換画像を生成する変換処理部と、
を備え、
前記変換テーブル設定部内には、請求項２２に記載の配列データの圧縮装置が組み込まれており、前記変換テーブル設定部は、当該圧縮装置を利用してＸ座標変換テーブルおよびＹ座標変換テーブルを圧縮して前記変換処理用メモリに設定し、
前記変換処理部内には、請求項２３に記載の配列データの伸張装置もしくは当該配列データの伸張装置のうちのブロック合成部を除く部分が組み込まれており、前記変換処理部は、当該組込装置を利用して必要なブロックごとに伸張したＸ座標変換テーブルおよびＹ座標変換テーブルを参照することにより、対応点の座標値（ｘ，ｙ）を認識することを特徴とする画像変換装置。
【請求項２５】
請求項１６〜２４のいずれかに記載の配列データの圧縮装置、配列データの伸張装置、もしくは画像変換装置としてコンピュータを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、複数の行および複数の列を有する配列データを圧縮したり伸張したりする技術に関し、特に、幾何学的な画像変換処理の用途に利用される座標変換テーブルの圧縮や伸張に適した圧縮／伸張方法に関する。
【背景技術】
【０００２】
光学系を用いて画像を撮影したり投影したりする場合、光学的な原因で画像に歪みが生じざるを得ない場合がある。このような場合、画像を表示する際に、歪みを補正するための処理が必要になる。たとえば、魚眼レンズが組み込まれた全方位カメラを用いると、半球状の極めて広い視界をもった画像を撮影することができるが、得られる撮影画像は歪曲した円形画像になる。このため、平面上に撮影画像を表示する際には、歪曲した円形画像を歪みのない正則矩形画像に変換する画像変換処理が必要になる。また、一般的なプロジェクタでは、スクリーン面に対して斜め方向から矩形画像の投影を行った場合に、投影画像が台形にならないように補正するための画像変換処理が行われる。
【０００３】
このように、光学的な原因で生じる画像の歪みを補正するための画像変換処理は、画像間の幾何学的な位置関係で定義される変換演算式を利用して行うことができる。たとえば、ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像を、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる変換画像に変換する場合、座標値（ｘ，ｙ）と座標値（ｕ，ｖ）との間の対応関係を一義的に定義した変換演算式を求めることができる。画像変換処理は、この変換演算式を利用した演算により、変換後の画像を構成する個々の画素に対応する原画像上の位置を認識し、変換画像を構成する個々の画素の画素値を決定する処理ということになる。
【０００４】
たとえば、下記の特許文献１には、プロジェクタの投影画像に対する台形補正を効率的に行うことができる画像変換処理が開示されており、特許文献２には、魚眼レンズを用いた撮影により得られた歪曲円形画像を歪みのない正則矩形画像に変換する画像変換処理が開示されている。また、特許文献３には、広角レンズや全方位ミラーを用いた撮影により得られた歪曲円形画像を歪みのない正則矩形画像に変換する際に、画像をブロック単位でキャッシュメモリに保存し、メモリアクセスに要する時間を短縮する技術が開示されている。
【０００５】
画像変換処理に利用される変換演算式は、原画像と変換画像との間の幾何学的な位置関係に基づいて得られる。したがって、両者間の幾何学的な位置関係が複雑になればなるほど、変換演算式も複雑にならざるを得ない。特に、魚眼レンズを用いて撮影された歪曲円形画像を正則矩形画像に変換する場合に用いる変換演算式は、三角関数を含む複雑な式になるため、原画像上の対応位置を求める演算負担は大きい。そのため、魚眼レンズを用いた監視システムにおいて、リアルタイムで監視画像を表示する必要がある場合、処理能力の高いプロセッサが必要になり、製造コストを高騰させる要因になっていた。また、演算負担の増加は消費電力の増大につながるため、運用コストを高騰させる要因にもなる。
【０００６】
このような問題に対処するため、原画像上の座標値（ｘ，ｙ）と変換画像上の座標値（ｕ，ｖ）との間の対応関係を、画素値決定に必要な離散的な座標ごとに予め演算しておき、その結果を座標変換テーブルという形でメモリに格納しておく手法が提案されている。たとえば、前掲の特許文献１には、台形補正に必要な座標変換テーブルを予め用意しておき、この変換テーブルを参照することにより、変換に必要な座標値を得る方法が開示されている。
【０００７】
原画像と変換画像との間の幾何学的な位置関係が一定であれば、変換に利用する変換演算式も同一になる。したがって、１フレームごとの原画像が与えられるたびに変換演算式を用いた演算を行って座標値を得る代わりに、予め算出しておいた演算結果を収録した座標変換テーブルを参照して座標値を得る方が効率的である。予め投影方向が定まっているプロジェクタや、予め監視エリアが定まっている魚眼監視システムなどでは、原画像と変換画像との間の幾何学的な位置関係は一定であり、変換に利用する変換演算式も一定であるので、上述した座標変換テーブルを参照する方法は非常に効率的である。
【先行技術文献】
【特許文献】
【０００８】
【特許文献１】特開２００２−２７８５０７号公報
【特許文献２】特開２０１０−０６２７９０号公報
【特許文献３】特開２０１０−１７６５４７号公報
【発明の概要】
【発明が解決しようとする課題】
【０００９】
上述した座標変換テーブルは、変換画像上に得られる各画素のそれぞれについて、原画像上の対応点の座標値を示すものであり、変換画像を構成する画素に対応した配列を有する配列データである。このため、画像のサイズが大きければ大きいほど、座標変換テーブルの配列サイズも大きくせざるを得ない。その一方で、座標変換テーブルを参照した変換処理を高速に行うためには、高速読出が可能なメモリに座標変換テーブルを格納しておく必要があるので、座標変換テーブルの配列サイズが大きくなればなるほど、高速読出が可能な高価なメモリの容量を増やす必要があり、ハードウエアのコストが高騰せざるを得ない。
【００１０】
このような問題に対処するために、たとえば、前掲の特許文献１には、座標変換テーブルとして、１つ前のデータとの差分値を収録した配列データを用意することにより、全体の情報量を圧縮する手法が提案されているが、必ずしも十分な圧縮効率が得られていないのが現状である。特に、魚眼レンズを用いた撮影により得られた歪曲円形画像を正則矩形画像に変換するために用いられる座標変換テーブルの場合、１つ前のデータとの差分値を収録するだけでは、十分な圧縮効果を得ることはできない。
【００１１】
変換画像が縦横に画素を配列した画像の場合、座標変換テーブルも、座標値を縦横に並べた配列データになるので、原理的には、一般的な画像データに対する圧縮方法を利用した圧縮プロセスを適用することが可能である。しかしながら、一般的な画像データと座標変換テーブルとは、いずれも何らかの数値を縦横に並べた配列データという点では共通するものの、個々の数値の意味合いが異なるため、一般的な画像データに対する圧縮方法を座標変換テーブルに適用しても、十分な圧縮効果を得ることはできない。
【００１２】
そこで本発明は、画像変換用の座標変換テーブルからなる配列データに対して、効率的な圧縮を行うことが可能な配列データの圧縮方法およびこれに応じた配列データの伸張方法を提供することを目的とする。更に、これらの方法を実行するのに適した装置を提供することを目的とする。また、そのような圧縮／伸張方法を利用した画像変換方法を採用することにより、画像変換装置のコストダウンを図ることを目的とする。
【課題を解決するための手段】
【００１３】
(1)   本発明の第１の態様は、複数の行および複数の列を有する配列データを圧縮する配列データの圧縮方法において、
コンピュータが、行列状に並んだ各セルについての数値の集合体からなる圧縮対象配列データを入力するデータ入力段階と、
コンピュータが、少なくとも所定の基準列に属するセルを除いて、圧縮対象配列データの個々のセル内の数値を、左もしくは右に隣接するセル内の数値との差分値に置き換える作業を含む置換処理を実行することにより、第１差分配列データを作成する第１差分演算段階と、
コンピュータが、少なくとも所定の基準行に属するセルを除いて、第１差分配列データの個々のセル内の数値を、上もしくは下に隣接するセル内の数値との差分値に置き換える作業を含む置換処理を実行することにより、第２差分配列データを作成する第２差分演算段階と、
を行うようにしたものである。
【００１４】
(2)   本発明の第２の態様は、上述した第１の態様に係る配列データの圧縮方法において、
第１差分演算段階で、少なくとも所定の基準列に属するセルを除いて、個々のセル内の数値を、左もしくは右に隣接するセル内の数値との差分値に置換した後、更に、基準列に属するセルのうち少なくとも所定の基準セルを除いて、個々のセル内の数値を、上もしくは下に隣接するセル内の数値との差分値に置換することにより、第１差分配列データを作成するようにしたものである。
【００１５】
(3)   本発明の第３の態様は、上述した第１または第２の態様に係る配列データの圧縮方法において、
第２差分演算段階で、少なくとも所定の基準行に属するセルを除いて、個々のセル内の数値を、上もしくは下に隣接するセル内の数値との差分値に置換した後、更に、基準行に属するセルのうち少なくとも所定の基準セルを除いて、個々のセル内の数値を、右もしくは左に隣接するセル内の数値との差分値に置換することにより、第２差分配列データを作成するようにしたものである。
【００１６】
(4)   本発明の第４の態様は、上述した第１〜第３の態様に係る配列データの圧縮方法を用いて圧縮された配列データを伸張する方法であって、
コンピュータが、伸張対象となる圧縮配列データを入力するデータ入力段階と、
コンピュータが、第２差分演算段階で置換された値を置換前の値に復元する段階と、
コンピュータが、第１差分演算段階で置換された値を置換前の値に復元する段階と、
を行うようにしたものである。
【００１７】
(5)   本発明の第５の態様は、ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像を、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる変換画像に変換する画像変換方法において、
コンピュータが、原画像と変換画像との間の幾何学的な関係に基づいて、変換画像を構成する各画素について、原画像上の対応点の座標値（ｘ，ｙ）を求める対応点演算段階と、
コンピュータが、変換画像を構成する各画素について対応点演算段階で求められた座標値ｘを並べたＸ座標変換テーブルと、変換画像を構成する各画素について対応点演算段階で求められた座標値ｙを並べたＹ座標変換テーブルと、をメモリに格納する変換テーブル格納段階と、
コンピュータが、原画像を構成する各画素の画素値を入力する原画像入力段階と、
コンピュータが、変換画像を構成する各画素について、Ｘ座標変換テーブルおよびＹ座標変換テーブルを参照し、原画像上の対応点の座標値（ｘ，ｙ）を認識する対応座標認識段階と、
コンピュータが、認識した座標値（ｘ，ｙ）の近傍に位置する原画像上の画素の画素値に基づいて、変換画像を構成する画素の画素値を決定する画素値決定段階と、
を行い、
変換テーブル格納段階において、Ｘ座標変換テーブルおよびＹ座標変換テーブルを、上述した第１〜３の態様に係る配列データ圧縮方法を利用して圧縮した状態でメモリに格納し、
対応座標認識段階において、上述した第４の態様に係る配列データ伸張方法を利用して伸張したＸ座標変換テーブルおよびＹ座標変換テーブルを参照することにより、対応点の座標値（ｘ，ｙ）を認識するようにしたものである。
【００１８】
(6)   本発明の第６の態様は、複数Ｍ行および複数Ｎ列を有する配列データを圧縮する配列データの圧縮方法において、
コンピュータが、Ｍ行Ｎ列の行列状に並んだセル群について、第ｉ行第ｊ列目のセル内の数値ｘ（ｉ，ｊ）の集合体（但し、１≦ｉ≦Ｍ，１≦ｊ≦Ｎ）からなる圧縮対象配列データを入力するデータ入力段階と、
コンピュータが、Ｄ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ＋１）−ｘ（ｉ，ｊ）なる演算式もしくはＤ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ）−ｘ（ｉ，ｊ＋１）なる演算式に基づいて、圧縮対象配列データの第ｉ行第（ｊ＋１）列目のセル内の数値ｘ（ｉ，ｊ＋１）を差分値Ｄ（ｉ，ｊ＋１）に置換する処理を、ｉ＝１〜Ｍおよびｊ＝１〜Ｎ−１の各組み合わせについて実行する横方向第１置換段階と、
コンピュータが、Ｄ（ｉ＋１，１）＝ｘ（ｉ＋１，１）−ｘ（ｉ，１）なる演算式もしくはＤ（ｉ＋１，１）＝ｘ（ｉ，１）−ｘ（ｉ＋１，１）なる演算式に基づいて、横方向第１置換段階後の配列データの第（ｉ＋１）行第１列目のセル内の数値ｘ（ｉ＋１，１）を差分値Ｄ（ｉ＋１，１）に置換する処理を、ｉ＝１〜Ｍ−１について実行することにより、第１差分配列データを作成する縦方向第１置換段階と、
コンピュータが、Ｅ（ｉ＋１，ｊ）＝Ｄ（ｉ＋１，ｊ）−Ｄ（ｉ，ｊ）なる演算式もしくはＥ（ｉ＋１，ｊ）＝Ｄ（ｉ，ｊ）−Ｄ（ｉ＋１，ｊ）なる演算式に基づいて、第１差分配列データの第（ｉ＋１）行第ｊ列目のセル内の数値Ｄ（ｉ＋１，ｊ）を差分値Ｅ（ｉ＋１，ｊ）に置換する処理を、ｉ＝１〜Ｍ−１およびｊ＝１〜Ｎの各組み合わせ（但し、ｉ＝１，ｊ＝１の組み合わせは除く）について実行する縦方向第２置換段階と、
コンピュータが、Ｅ（１，ｊ＋１）＝Ｄ（１，ｊ＋１）−Ｄ（１，ｊ）なる演算式もしくはＥ（１，ｊ＋１）＝Ｄ（１，ｊ）−Ｄ（１，ｊ＋１）なる演算式に基づいて、縦方向第２置換段階後の配列データの第１行第（ｊ＋１）列目のセル内の数値Ｄ（１，ｊ＋１）を差分値Ｅ（１，ｊ＋１）に置換する処理を、ｊ＝２〜Ｎ−１について実行することにより、第２差分配列データを作成する横方向第２置換段階と、
を行うようにしたものである。
【００１９】
(7)   本発明の第７の態様は、上述した第６の態様に係る配列データの圧縮方法において、
コンピュータが、複数μ行および複数ν列を有する元配列データ（但し、μ＞Ｍ，ν＞Ｎ）を、複数Ｍ行および複数Ｎ列を有する配列データからなる複数Ｋ個のブロックに分割するブロック分割段階を更に行い、
個々のブロックを構成する配列データをそれぞれ圧縮対象配列データとして、横方向第１置換段階、縦方向第１置換段階、縦方向第２置換段階、横方向第２置換段階を行って第２差分配列データを作成し、
少なくとも所定の基準ブロックを除いて、個々のブロックを構成する第２差分配列データの第１行第１列目のセル、第１行第２列目のセル、第２行第１列目のセル内の数値を、隣接するブロック内の対応位置のセル内の数値との差分値に置換して、第３差分配列データを作成するブロック間差分演算段階を更に行うようにしたものである。
【００２０】
(8)   本発明の第８の態様は、上述した第６または第７の態様に係る配列データの圧縮方法において、
コンピュータが、第２差分配列データもしくは第３差分配列データを、１行目の配列データ、２行目の配列データ、３行目以降の配列データについて、それぞれ異なるフォーマットで符号化するデータ符号化段階を更に行うようにしたものである。
【００２１】
(9)   本発明の第９の態様は、上述した第８の態様に係る配列データの圧縮方法において、
１行目の配列データについては、１列目のセル内の数値と、２列目のセル内の数値と、３列目以降のセル内の数値と、について、それぞれ異なるフォーマットで符号化し、
２行目の配列データについては、１列目のセル内の数値と、２列目以降のセル内の数値と、について、それぞれ異なるフォーマットで符号化し、
３行目以降の配列データについては、各セル内の数値を同一のフォーマットで符号化するようにしたものである。
【００２２】
(10)  本発明の第１０の態様は、上述した第６の態様に係る配列データの圧縮方法を用いて圧縮された配列データを伸張する配列データの伸張方法において、
コンピュータが、第２差分配列データについて、横方向第２置換段階において置換されていた差分値Ｅを元の数値Ｄに復元する横方向第２置換復元段階と、
コンピュータが、横方向第２置換復元段階で復元されたデータについて、縦方向第２置換段階において置換されていた差分値Ｅを元の数値Ｄに復元して第１差分配列データを得る縦方向第２置換復元段階と、
コンピュータが、第１差分配列データについて、縦方向第１置換段階において置換されていた差分値Ｄを元の数値ｘに復元する縦方向第１置換復元段階と、
コンピュータが、縦方向第１置換復元段階で復元されたデータについて、横方向第１置換段階において置換されていた差分値Ｄを元の数値ｘに復元して圧縮対象配列データを得る横方向第１置換復元段階と、
を行うようにしたものである。
【００２３】
(11)  本発明の第１１の態様は、上述した第７の態様に係る配列データの圧縮方法を用いて圧縮された配列データを伸張する配列データの伸張方法において、
コンピュータが、第３差分配列データについて、ブロック間差分演算段階において置換されていた差分値を元の数値に復元して第２差分配列データを得るブロック復元演算段階と、
コンピュータが、個々のブロックの第２差分配列データについて、請求項１０に記載の横方向第２置換復元段階および縦方向第２置換復元段階を実行して、第１差分配列データを得る第２差分復元段階と、
コンピュータが、個々のブロックの第１差分配列データについて、請求項１０に記載の縦方向第１置換復元段階および横方向第１置換復元段階を実行して、圧縮対象配列データを得る第１差分復元段階と、
コンピュータが、個々のブロックの圧縮対象配列データを合成して元配列データを得るブロック合成段階と、
を行うようにしたものである。
【００２４】
(12)  本発明の第１２の態様は、ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像を、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる変換画像に変換する画像変換方法において、
コンピュータが、原画像と変換画像との間の幾何学的な関係に基づいて、変換画像を構成する各画素について、原画像上の対応点の座標値（ｘ，ｙ）を求める対応点演算段階と、
コンピュータが、変換画像を構成する各画素について対応点演算段階で求められた座標値ｘを並べたＸ座標変換テーブルと、変換画像を構成する各画素について対応点演算段階で求められた座標値ｙを並べたＹ座標変換テーブルと、をメモリに格納する変換テーブル格納段階と、
コンピュータが、原画像を構成する各画素の画素値を入力する原画像入力段階と、
コンピュータが、変換画像を構成する各画素について、Ｘ座標変換テーブルおよびＹ座標変換テーブルを参照し、原画像上の対応点の座標値（ｘ，ｙ）を認識する対応座標認識段階と、
コンピュータが、認識した座標値（ｘ，ｙ）の近傍に位置する原画像上の画素の画素値に基づいて、変換画像を構成する画素の画素値を決定する画素値決定段階と、
を行い、
変換テーブル格納段階において、Ｘ座標変換テーブルおよびＹ座標変換テーブルを、上述した第６の態様に係る配列データ圧縮方法を利用して圧縮した状態でメモリに格納し、
対応座標認識段階において、上述した第１０の態様に係る配列データ伸張方法を利用して伸張したＸ座標変換テーブルおよびＹ座標変換テーブルを参照することにより、対応点の座標値（ｘ，ｙ）を認識するようにしたものである。
【００２５】
(13)  本発明の第１３の態様は、ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像を、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる変換画像に変換する画像変換方法において、
コンピュータが、原画像と変換画像との間の幾何学的な関係に基づいて、変換画像を構成する各画素について、原画像上の対応点の座標値（ｘ，ｙ）を求める対応点演算段階と、
コンピュータが、変換画像を構成する各画素について対応点演算段階で求められた座標値ｘを並べたＸ座標変換テーブルと、変換画像を構成する各画素について対応点演算段階で求められた座標値ｙを並べたＹ座標変換テーブルと、をメモリに格納する変換テーブル格納段階と、
コンピュータが、原画像を構成する各画素の画素値を入力する原画像入力段階と、
コンピュータが、変換画像を構成する各画素について、Ｘ座標変換テーブルおよびＹ座標変換テーブルを参照し、原画像上の対応点の座標値（ｘ，ｙ）を認識する対応座標認識段階と、
コンピュータが、認識した座標値（ｘ，ｙ）の近傍に位置する原画像上の画素の画素値に基づいて、変換画像を構成する画素の画素値を決定する画素値決定段階と、
を行い、
変換テーブル格納段階において、Ｘ座標変換テーブルおよびＹ座標変換テーブルを、上述した第７の態様に係る配列データ圧縮方法を利用して圧縮した状態でメモリに格納し、
対応座標認識段階において、上述した第１１の態様に係る配列データ伸張方法のうちのブロック合成段階を除く部分を利用して、必要なブロックごとに伸張したＸ座標変換テーブルおよびＹ座標変換テーブルを参照することにより、対応点の座標値（ｘ，ｙ）を認識するようにしたものである。
【００２６】
(14)  本発明の第１４の態様は、上述した第１〜第１３の態様に係る配列データの圧縮方法、配列データの伸張方法、もしくは画像変換方法を、コンピュータにプログラムを組み込むことにより実行させるようにしたものである。
【００２７】
(15)  本発明の第１５の態様は、上述した第１〜第１３の態様に係る配列データの圧縮方法、配列データの伸張方法、もしくは画像変換方法を、プログラムを組み込んだコンピュータとして機能する集積回路により実行させるようにしたものである。
【００２８】
(16)  本発明の第１６の態様は、複数の行および複数の列を有する配列データを圧縮する配列データの圧縮装置において、
行列状に並んだ各セルについての数値の集合体からなる圧縮対象配列データを格納する作業用メモリと、
少なくとも所定の基準列に属するセルを除いて、圧縮対象配列データの個々のセル内の数値を、左もしくは右に隣接するセル内の数値との差分値に置き換える作業を含む置換処理を実行することにより、第１差分配列データを作成する第１差分演算部と、
少なくとも所定の基準行に属するセルを除いて、第１差分配列データの個々のセル内の数値を、上もしくは下に隣接するセル内の数値との差分値に置き換える作業を含む置換処理を実行することにより、第２差分配列データを作成する第２差分演算部と、
を設けるようにしたものである。
【００２９】
(17)  本発明の第１７の態様は、上述した第１６の態様に係る配列データの圧縮装置を用いて圧縮された圧縮配列データを伸張する配列データの伸張装置において、
第２差分配列データを格納する作業用メモリと、
第２差分配列データについて、第２差分演算部で置換された値を置換前の値に戻すことにより第１差分配列データを復元する第２差分復元部と、
第１差分配列データについて、第１差分演算部で置換された値を置換前の値に戻すことにより圧縮対象配列データを復元する第１差分復元部と、
を設けるようにしたものである。
【００３０】
(18)  本発明の第１８の態様は、ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像を、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる変換画像に変換する画像変換装置において、
変換処理用メモリと、
変換処理用メモリに原画像を入力する原画像入力部と、
変換処理用メモリに得られた変換画像を出力する変換画像出力部と、
変換処理用メモリに、変換に用いるＸ座標変換テーブルおよびＹ座標変換テーブルを設定する変換テーブル設定部と、
変換画像を構成する各画素について、Ｘ座標変換テーブルおよびＹ座標変換テーブルを参照することにより原画像上の対応点の座標値（ｘ，ｙ）を認識し、認識した座標値（ｘ，ｙ）の近傍に位置する原画像上の画素の画素値に基づいて画素値を決定し、変換処理用メモリ上に変換画像を生成する変換処理部と、
を設け、
変換テーブル設定部内には、上述した第１６の態様に係る配列データの圧縮装置を組み込み、変換テーブル設定部が、当該圧縮装置を利用してＸ座標変換テーブルおよびＹ座標変換テーブルを圧縮して変換処理用メモリに設定し、
変換処理部内には、上述した第１７の態様に係る配列データの伸張装置を組み込み、変換処理部が、当該伸張装置を利用して伸張したＸ座標変換テーブルおよびＹ座標変換テーブルを参照することにより、対応点の座標値（ｘ，ｙ）を認識するようにしたものである。
【００３１】
(19)  本発明の第１９の態様は、複数Ｍ行および複数Ｎ列を有する配列データを圧縮する配列データの圧縮装置において、
Ｍ行Ｎ列の行列状に並んだセル群について、第ｉ行第ｊ列目のセル内の数値ｘ（ｉ，ｊ）の集合体（但し、１≦ｉ≦Ｍ，１≦ｊ≦Ｎ）からなる圧縮対象配列データを格納する作業用メモリと、
Ｄ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ＋１）−ｘ（ｉ，ｊ）なる演算式もしくはＤ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ）−ｘ（ｉ，ｊ＋１）なる演算式に基づいて、圧縮対象配列データの第ｉ行第（ｊ＋１）列目のセル内の数値ｘ（ｉ，ｊ＋１）を差分値Ｄ（ｉ，ｊ＋１）に置換する置換処理を、ｉ＝１〜Ｍおよびｊ＝１〜Ｎ−１の各組み合わせについて実行する横方向第１置換部と、
Ｄ（ｉ＋１，１）＝ｘ（ｉ＋１，１）−ｘ（ｉ，１）なる演算式もしくはＤ（ｉ＋１，１）＝ｘ（ｉ，１）−ｘ（ｉ＋１，１）なる演算式に基づいて、横方向第１置換部による置換処理後の配列データの第（ｉ＋１）行第１列目のセル内の数値ｘ（ｉ＋１，１）を差分値Ｄ（ｉ＋１，１）に置換する置換処理を、ｉ＝１〜Ｍ−１について実行することにより、第１差分配列データを作成する縦方向第１置換部と、
Ｅ（ｉ＋１，ｊ）＝Ｄ（ｉ＋１，ｊ）−Ｄ（ｉ，ｊ）なる演算式もしくはＥ（ｉ＋１，ｊ）＝Ｄ（ｉ，ｊ）−Ｄ（ｉ＋１，ｊ）なる演算式に基づいて、第１差分配列データの第（ｉ＋１）行第ｊ列目のセル内の数値Ｄ（ｉ＋１，ｊ）を差分値Ｅ（ｉ＋１，ｊ）に置換する置換処理を、ｉ＝１〜Ｍ−１およびｊ＝１〜Ｎの各組み合わせ（但し、ｉ＝１，ｊ＝１の組み合わせは除く）について実行する縦方向第２置換部と、
Ｅ（１，ｊ＋１）＝Ｄ（１，ｊ＋１）−Ｄ（１，ｊ）なる演算式もしくはＥ（１，ｊ＋１）＝Ｄ（１，ｊ）−Ｄ（１，ｊ＋１）なる演算式に基づいて、縦方向第２置換部による置換処理後の配列データの第１行第（ｊ＋１）列目のセル内の数値Ｄ（１，ｊ＋１）を差分値Ｅ（１，ｊ＋１）に置換する置換処理を、ｊ＝２〜Ｎ−１について実行することにより、第２差分配列データを作成する横方向第２置換部と、
を設けるようにしたものである。
【００３２】
(20)  本発明の第２０の態様は、上述した第１９の態様に係る配列データの圧縮装置を用いて圧縮された圧縮配列データを伸張する配列データの伸張装置において、
第２差分配列データを格納する作業用メモリと、
第２差分配列データについて、横方向第２置換部において置換された差分値Ｅを元の数値Ｄに復元する横方向第２置換復元部と、
横方向第２置換復元部で復元されたデータについて、縦方向第２置換部において置換された差分値Ｅを元の数値Ｄに復元して第１差分配列データを得る縦方向第２置換復元部と、
第１差分配列データについて、縦方向第１置換部において置換された差分値Ｄを元の数値ｘに復元する縦方向第１置換復元部と、
縦方向第１置換復元部で復元されたデータについて、横方向第１置換部において置換された差分値Ｄを元の数値ｘに復元して圧縮対象配列データを得る横方向第１置換復元部と、
を設けるようにしたものである。
【００３３】
(21)  本発明の第２１の態様は、ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像を、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる変換画像に変換する画像変換装置において、
変換処理用メモリと、
変換処理用メモリに原画像を入力する原画像入力部と、
変換処理用メモリに得られた変換画像を出力する変換画像出力部と、
変換処理用メモリに、変換に用いるＸ座標変換テーブルおよびＹ座標変換テーブルを設定する変換テーブル設定部と、
変換画像を構成する各画素について、Ｘ座標変換テーブルおよびＹ座標変換テーブルを参照することにより原画像上の対応点の座標値（ｘ，ｙ）を認識し、認識した座標値（ｘ，ｙ）の近傍に位置する原画像上の画素の画素値に基づいて画素値を決定し、変換処理用メモリ上に変換画像を生成する変換処理部と、
を設け、
変換テーブル設定部内には、上述した第１９の態様に係る配列データの圧縮装置を組み込み、変換テーブル設定部が、当該圧縮装置を利用してＸ座標変換テーブルおよびＹ座標変換テーブルを圧縮して変換処理用メモリに設定し、
変換処理部内には、上述した第２０の態様に係る配列データの伸張装置を組み込み、変換処理部が、当該伸張装置を利用して伸張したＸ座標変換テーブルおよびＹ座標変換テーブルを参照することにより、対応点の座標値（ｘ，ｙ）を認識するようにしたものである。
【００３４】
(22)  本発明の第２２の態様は、複数μ行および複数ν列を有する元配列データを圧縮する配列データの圧縮装置において、
元配列データを入力する元配列データ入力部と、
入力した元配列データを、それぞれが複数Ｍ行および複数Ｎ列を有する配列データ（但し、μ＞Ｍ，ν＞Ｎ）からなる複数Ｋ個のブロックに分割するブロック分割部と、
個々のブロックのＭ行Ｎ列の行列状に並んだセル群について、第ｉ行第ｊ列目のセル内の数値ｘ（ｉ，ｊ）の集合体（但し、１≦ｉ≦Ｍ，１≦ｊ≦Ｎ）からなる圧縮対象配列データを格納する作業用メモリと、
Ｄ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ＋１）−ｘ（ｉ，ｊ）なる演算式もしくはＤ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ）−ｘ（ｉ，ｊ＋１）なる演算式に基づいて、圧縮対象配列データの第ｉ行第（ｊ＋１）列目のセル内の数値ｘ（ｉ，ｊ＋１）を差分値Ｄ（ｉ，ｊ＋１）に置換する置換処理を、ｉ＝１〜Ｍおよびｊ＝１〜Ｎ−１の各組み合わせについて実行する横方向第１置換部と、
Ｄ（ｉ＋１，１）＝ｘ（ｉ＋１，１）−ｘ（ｉ，１）なる演算式もしくはＤ（ｉ＋１，１）＝ｘ（ｉ，１）−ｘ（ｉ＋１，１）なる演算式に基づいて、横方向第１置換部による置換処理後の配列データの第（ｉ＋１）行第１列目のセル内の数値ｘ（ｉ＋１，１）を差分値Ｄ（ｉ＋１，１）に置換する置換処理を、ｉ＝１〜Ｍ−１について実行することにより、第１差分配列データを作成する縦方向第１置換部と、
Ｅ（ｉ＋１，ｊ）＝Ｄ（ｉ＋１，ｊ）−Ｄ（ｉ，ｊ）なる演算式もしくはＥ（ｉ＋１，ｊ）＝Ｄ（ｉ，ｊ）−Ｄ（ｉ＋１，ｊ）なる演算式に基づいて、第１差分配列データの第（ｉ＋１）行第ｊ列目のセル内の数値Ｄ（ｉ＋１，ｊ）を差分値Ｅ（ｉ＋１，ｊ）に置換する置換処理を、ｉ＝１〜Ｍ−１およびｊ＝１〜Ｎの各組み合わせ（但し、ｉ＝１，ｊ＝１の組み合わせは除く）について実行する縦方向第２置換部と、
Ｅ（１，ｊ＋１）＝Ｄ（１，ｊ＋１）−Ｄ（１，ｊ）なる演算式もしくはＥ（１，ｊ＋１）＝Ｄ（１，ｊ）−Ｄ（１，ｊ＋１）なる演算式に基づいて、縦方向第２置換部による置換処理後の配列データの第１行第（ｊ＋１）列目のセル内の数値Ｄ（１，ｊ＋１）を差分値Ｅ（１，ｊ＋１）に置換する置換処理を、ｊ＝２〜Ｎ−１について実行することにより、第２差分配列データを作成する横方向第２置換部と、
少なくとも所定の基準ブロックを除いて、個々のブロックを構成する第２差分配列データの第１行第１列目のセル、第１行第２列目のセル、第２行第１列目のセル内の数値を、隣接するブロック内の対応位置のセル内の数値との差分値に置換して、第３差分配列データを作成するブロック間差分演算部と、
個々のブロックについての第２差分配列データもしくは第３差分配列データを、圧縮配列データとして出力する圧縮配列データ出力部と、
を設けるようにしたものである。
【００３５】
(23)  本発明の第２３の態様は、上述した第２２の態様に係る配列データの圧縮装置を用いて圧縮された圧縮配列データを伸張する配列データの伸張装置において、
圧縮配列データを入力する圧縮配列データ入力部と、
入力した圧縮配列データのうちの第３差分配列データについて、ブロック間差分演算部において置換された差分値を元の数値に復元して第２差分配列データを得るブロック復元演算部と、
各ブロックの第２差分配列データを格納する作業用メモリと、
第２差分配列データについて、横方向第２置換部において置換された差分値Ｅを元の数値Ｄに復元する横方向第２置換復元部と、
横方向第２置換復元部で復元されたデータについて、縦方向第２置換部において置換された差分値Ｅを元の数値Ｄに復元して第１差分配列データを得る縦方向第２置換復元部と、
第１差分配列データについて、縦方向第１置換部において置換された差分値Ｄを元の数値ｘに復元する縦方向第１置換復元部と、
縦方向第１置換復元部で復元されたデータについて、横方向第１置換部において置換された差分値Ｄを元の数値ｘに復元して圧縮対象配列データを得る横方向第１置換復元部と、
個々のブロックの圧縮対象配列データを合成して元配列データを得るブロック合成部と、
を設けるようにしたものである。
【００３６】
(24)  本発明の第２４の態様は、ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像を、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる変換画像に変換する画像変換装置において、
変換処理用メモリと、
変換処理用メモリに原画像を入力する原画像入力部と、
変換処理用メモリに得られた変換画像を出力する変換画像出力部と、
変換処理用メモリに、変換に用いるＸ座標変換テーブルおよびＹ座標変換テーブルを設定する変換テーブル設定部と、
変換画像を構成する各画素について、Ｘ座標変換テーブルおよびＹ座標変換テーブルを参照することにより原画像上の対応点の座標値（ｘ，ｙ）を認識し、認識した座標値（ｘ，ｙ）の近傍に位置する原画像上の画素の画素値に基づいて画素値を決定し、変換処理用メモリ上に変換画像を生成する変換処理部と、
を設け、
変換テーブル設定部内には、上述した第２２の態様に係る配列データの圧縮装置を組み込み、変換テーブル設定部が、当該圧縮装置を利用してＸ座標変換テーブルおよびＹ座標変換テーブルを圧縮して変換処理用メモリに設定し、
変換処理部内には、上述した第２３の態様に係る配列データの伸張装置もしくは当該配列データの伸張装置のうちのブロック合成部を除く部分が組み込み、変換処理部が、当該組込装置を利用して必要なブロックごとに伸張したＸ座標変換テーブルおよびＹ座標変換テーブルを参照することにより、対応点の座標値（ｘ，ｙ）を認識するようにしたものである。
【００３７】
(25)  本発明の第２５の態様は、上述した第１６〜第２４の態様に係る配列データの圧縮装置、配列データの伸張装置、もしくは画像変換装置を、コンピュータにプログラムを組み込むことにより構成したものである。
【発明の効果】
【００３８】
本発明に係る配列データの圧縮方法および圧縮装置によれば、縦横マトリックス状に数値が並べられた圧縮対象配列データに対して、横方向に差分をとる演算と縦方向に差分をとる演算とが実行され、２回の差分演算が施された配列データが得られることになる。したがって、画像変換用の座標変換テーブルからなる配列データに対して、効率的な圧縮を行うことが可能になる。また、本発明に係る配列データの伸張方法および伸張装置によれば、上記圧縮プロセスとは逆のプロセスに基づく可逆的な伸張処理が行われるため、圧縮された配列データから元の配列データを正確に復元することが可能になる。一方、本発明に係る画像変換方法および画像変換装置では、上記プロセスを採用して座標変換テーブルの圧縮／伸張を行うため、座標変換テーブルの格納に必要なメモリ容量を節約することができるようになり、ハードウエアのコストダウンを図ることができるようになる。
【図面の簡単な説明】
【００３９】
【図１】魚眼レンズが組み込まれた全方位カメラによって撮影された歪曲円形画像とこれを変換して得られた正則矩形画像を示す平面図である。
【図２】プロジェクタによる投影用原画像とこれを変換して得られた台形補正画像を示す平面図である。
【図３】原画像Ａを変換画像Ｂに変換する画像変換処理の具体的な処理手順を示す平面図である。
【図４】変換画像Ｂを構成する各画素Ｐ（ｕ，ｖ）の位置に対応する原画像Ａ上の対応点Ａ（ｘ，ｙ）を、座標変換テーブルＴｘ，Ｔｙを用いて求める原理を示す平面図である。
【図５】座標変換テーブルを用いて変換を行う画像変換装置の基本構成を示すブロック図である。
【図６】図５に示すＸ座標変換テーブルＴｘの構成例を示す平面図である。
【図７】本発明の圧縮方法による圧縮対象となる配列データＸの構成例を示す平面図である。
【図８】図７に示す圧縮対象配列データＸの第１行目のセル内の数値に対して、横方向の差分値による置換を行った状態を示す平面図である。
【図９】図７に示す圧縮対象配列データＸに対して、横方向第１置換段階の処理を施した結果を示す平面図である。
【図１０】図９に示す横方向第１置換段階の処理後の配列データに対して、縦方向第１置換段階の処理を施した結果を示す平面図である。
【図１１】図１０に示す縦方向第１置換段階の処理の結果として得られる第１差分配列データＤを示す平面図である。
【図１２】図７に示す圧縮対象配列データＸの具体的な実例を示す平面図である。
【図１３】図１２に示す圧縮対象配列データＸに対して、横方向第１置換段階の処理を施した結果を示す平面図である。
【図１４】図１３に示す横方向第１置換段階の処理後の配列データに対して、縦方向第１置換段階の処理を施すことにより得られる第１差分配列データＤを示す平面図である。
【図１５】図１１に示す第１差分配列データＤに対して、縦方向第２置換段階の処理を施した結果を示す平面図である。
【図１６】図１５に示す縦方向第２置換段階の処理後の配列データに対して、横方向第２置換段階の処理を施した結果を示す平面図である。
【図１７】図１６に示す横方向第２置換段階の処理の結果として得られる第２差分配列データＥを示す平面図である。
【図１８】図１７に示す第２差分配列データＥの具体的な実例を示す平面図である。
【図１９】図１７および図１８に示す第２差分配列データＥの特徴を示す平面図である。
【図２０】元配列データを複数のブロックに分割した状態を示す平面図である。
【図２１】本発明に係る配列データの圧縮方法の基本手順を示す流れ図である。
【図２２】本発明に係る配列データの伸張方法の基本手順を示す流れ図である。
【図２３】本発明に係る配列データの圧縮方法により得られた圧縮配列データを記述するのに適したフォーマットの一例を示す第１の図である。
【図２４】本発明に係る配列データの圧縮方法により得られた圧縮配列データを記述するのに適したフォーマットの一例を示す第２の図である。
【図２５】本発明に係る配列データの圧縮方法により得られた圧縮配列データを記述するのに適したフォーマットの一例を示す第３の図である。
【図２６】本発明に係る画像変換方法の具体的な手順を示す流れ図である。
【図２７】本発明に係る配列データの圧縮装置の具体的な構成例を示すブロック図である。
【図２８】本発明に係る配列データの伸張装置の具体的な構成例を示すブロック図である。
【図２９】本発明に係る画像変換装置の具体的な構成例を示すブロック図である。
【発明を実施するための形態】
【００４０】
以下、本発明を図示する実施形態に基づいて説明する。
【００４１】
＜＜＜  §１．  一般的な幾何学的画像変換処理  ＞＞＞
本発明は、幾何学的な画像変換処理を行う際に、座標変換テーブルを構成する配列データに対して最適な圧縮方法を提供することができる技術である。そこで、ここでは、本発明を利用するのに適した幾何学的な画像変換処理を簡単に説明しておく。
【００４２】
図１(a) は、魚眼レンズが組み込まれた全方位カメラによって撮影された歪曲円形画像Ａの一例を示す平面図である。図示の例は、撮像面を水平にし、魚眼レンズが上方に向くように配置した全方位カメラによって、撮像面より上方の半球視界を撮影した例であり、カメラの周囲３６０°の全方位画像が歪んだ状態で記録されている。したがって、モニタ画面に表示する際には、この歪曲円形画像Ａに対して幾何学的な画像変換処理を施す必要がある。図１(b) は、画像変換処理によって得られた正則矩形画像Ｂの一例を示す平面図である。もちろん、３６０°の全方位画像全体をパノラマ画像に変換することも可能であるが、一般的には、歪曲円形画像Ａの一部分を正則矩形画像Ｂに変換して表示する方法が採られる。図示の例は、歪曲円形画像Ａから女性の画像部分のみを切り出して変換処理を施すことにより、正則矩形画像Ｂを作成した例である。
【００４３】
ここでは、説明の便宜上、歪曲円形画像ＡがＸＹ二次元直交座標系上に定義され、正則矩形画像ＢがＵＶ二次元直交座標系上に定義されているものとする。また、図示のとおり、ＸＹ二次元座標系の原点Ｏは歪曲円形画像Ａの中心点に位置し、ＵＶ二次元座標系の原点Ｏは、正則矩形画像Ｂの左下隅点に位置するものとする。このように、歪曲円形画像Ａの一部分を切り出して変換し、正則矩形画像Ｂを得るためには、両者間の位置関係を示す幾何学的な条件を設定する必要がある。
【００４４】
具体的には、歪曲円形画像Ａ上のどの点を切出中心点として（切出位置）、どのような向きに（切出向き）、どのような大きさの領域（切出倍率）を切り出して正則矩形画像Ｂに変換するか、という条件を示すパラメータを設定する必要がある。このようなパラメータが定まれば、両者間の位置関係を示す式を定義することができ、この式を用いた演算により、歪曲円形画像Ａから正則矩形画像Ｂへの変換処理を行うことができる。たとえば、図１に示す例の場合、歪曲円形画像Ａ上の１点Ａ（ｘ，ｙ）と、正則矩形画像Ｂ上の１点Ｂ（ｕ，ｖ）とは、互いに対応する点になる。
【００４５】
結局、両画像Ａ，Ｂ間の位置関係を示す式とは、ＸＹ二次元座標系上の任意の点Ａ（ｘ，ｙ）の座標値ｘ，ｙと、ＵＶ二次元座標系上の対応点Ｂ（ｕ，ｖ）の座標値ｕ，ｖとの対応関係を示す式ということになる。この対応関係式には、上述した条件を示すパラメータが変数として含まれている。具体的な対応関係式は、たとえば、前掲の特許文献２などに開示されている公知の式であるため、ここでは詳しい説明は省略する。
【００４６】
一方、図２は、プロジェクタによる投影用原画像Ａとこれを変換して得られた台形補正画像Ｂを示す平面図である。図２(a) に示すとおり、投影用原画像Ａは、本来表示すべき矩形状の正則画像であるのに対して、図２(b) に示すとおり、台形補正画像Ｂは、台形補正処理を施すことによって得られる歪んだ画像である。前述した図１に示す例では、歪曲画像を正則画像に変換する処理が行われるのに対して、この図２に示す例では、正則画像を歪曲画像に変換する処理が行われることになる。ただ、台形補正処理は、プロジェクタからスクリーン面に対して斜め方向から投影を行った場合に、投影画像が台形にならないように補正するための処理であり、図示の例の場合、台形補正画像Ｂをプロジェクタからスクリーン面に投影すると、スクリーン上には、投影用原画像Ａに対応する正則矩形画像が得られることになる。
【００４７】
図示の例は、プロジェクタからスクリーンに向けて、斜め上方に投影を行う場合に適切な正則画像が表示されるように台形補正を施した例であり、画像の上方部分ほど横方向に密になるような補正が行われている。この例でも、投影用原画像ＡはＸＹ二次元座標系上に定義され、台形補正画像ＢはＵＶ二次元座標系上に定義されており、投影用原画像Ａから台形補正画像Ｂへの変換処理は、ＸＹ二次元座標系上の任意の点Ａ（ｘ，ｙ）の座標値ｘ，ｙと、ＵＶ二次元座標系上の対応点Ｂ（ｕ，ｖ）の座標値ｕ，ｖとの対応関係式に基づいて行われる。
【００４８】
台形補正を行うための対応関係式には、スクリーンとプロジェクタとの位置関係（相互の向きや距離）、プロジェクタに内蔵された投影光学系の特性などがパラメータとして含まれることになるが、これらのパラメータが定まれば、投影用原画像Ａと台形補正画像Ｂとの間の位置関係を示す対応関係式を一義的に定義することができ、この対応関係式を用いた演算により、投影用原画像Ａから台形補正画像Ｂへの変換処理を行うことができる。台形補正を行うための具体的な対応関係式は、たとえば、前掲の特許文献１などに開示されている公知の式であるため、ここでは詳しい説明は省略する。
【００４９】
以上、魚眼レンズ式の全方位カメラを用いた撮影によって得られた歪曲円形画像に対する変換例や、プロジェクタにおける台形補正の例を述べたが、この他にも、光学的な原因で生じる歪みを修正するための画像変換処理は、様々な状況で行われている。以下、変換前の画像を原画像Ａ、変換後の画像を変換画像Ｂと呼ぶことにし、原画像Ａが、ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる画像であり、変換画像Ｂが、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる画像である場合についての一般的な説明を行うことにする。
【００５０】
原画像Ａに基づいて変換画像Ｂを得るためには、変換画像Ｂ上の任意の点Ｂ（ｕ，ｖ）に位置する画素に対して、原画像Ａ上の対応点Ａ（ｘ，ｙ）に位置する対応画素の画素値を与えればよい。ただ、実際の画像上の画素は、所定の解像度に応じたピッチで離散的に配列されているため、一般的には、原画像Ａ上の画素と変換画像Ｂ上の画素とは１対１に対応するものではない。そこで、実際には、変換画像Ｂを構成する個々の画素の代表点Ｂ（ｕ，ｖ）について、原画像Ａ上の対応点Ａ（ｘ，ｙ）を求め、この対応点Ａ（ｘ，ｙ）の近傍に位置する原画像Ａ上の画素の画素値に基づいて、変換画像Ｂを構成する画素の画素値を決定する処理が行われる。
【００５１】
図３は、原画像Ａを変換画像Ｂに変換する画像変換処理の具体的な処理手順を示す平面図である。ここに示す例は、原画像Ａと変換画像Ｂの解像度が異なる例であり、原画像Ａを構成する画素と変換画像Ｂを構成する画素とは、互いに異なる大きさで描かれている。変換画像Ｂの解像度は、画像変換処理のパラメータとして、所望の値が設定される。
【００５２】
概念的には、この画像変換処理は、図３(a) に示す原画像Ａを図３(b) に示す変換画像Ｂに変換する処理ということになるが、実際に行うべき処理は、変換画像Ｂを構成する各画素Ｐ（ｕ，ｖ）の画素値を、原画像Ａを構成する画素の画素値に基づいて決定する処理であり、ＵＶ二次元座標系上の座標値（ｕ，ｖ）をＸＹ二次元座標系上の座標値（ｘ，ｙ）に変換する座標変換処理が必要になる。このような座標変換は、前述したように、両画像Ａ，Ｂ間の幾何学的な位置関係に基づいて一義的に定まる対応関係式に基づいて行われる。
【００５３】
ここでは、図３(b) に示す変換画像Ｂを構成する任意の画素Ｐ（ｕ，ｖ）の画素値を決定するプロセスを簡単に説明しよう。点Ｂ（ｕ，ｖ）は、この画素Ｐ（ｕ，ｖ）の代表点（この例では、画素の中心点）であり、画素Ｐ（ｕ，ｖ）の位置を代表する点ということになる。点Ｂ（ｕ，ｖ）は、ＵＶ二次元座標系上で座標値（ｕ，ｖ）をもつ点であり、画素Ｐ（ｕ，ｖ）は、座標値（ｕ，ｖ）で示される位置に配置された画素ということになる。
【００５４】
画素Ｐ（ｕ，ｖ）の画素値を決定するには、まず、図３(a) に示す原画像Ａ上において、点Ｂ（ｕ，ｖ）の対応点Ａ（ｘ，ｙ）を求める必要がある。２点Ａ（ｘ，ｙ）とＢ（ｕ，ｖ）との対応関係は、前述したように、両画像Ａ，Ｂ間の幾何学的な位置関係に基づいて一義的に定まる対応関係式によって定義される。この対応関係式は、点Ｂ（ｕ，ｖ）の座標値ｕ，ｖに基づいて、対応点Ａ（ｘ，ｙ）の座標値ｘ，ｙを導出する幾何学変換関数Ｇによって与えられ、前述したとおり、両画像Ａ，Ｂ間の幾何学的な位置関係を示すパラメータを含んだ式になる。いずれにしても、この幾何学変換関数Ｇを用いれば、任意の座標値（ｕ，ｖ）の組み合わせに対して、対応する座標値（ｘ，ｙ）の組み合わせが一義的に導出される。
【００５５】
続いて、原画像Ａ上において、対応点Ａ（ｘ，ｙ）の近傍に位置する画素を参照画素として抽出し、これら参照画素の画素値に基づいて、変換画像Ｂ上の画素Ｐ（ｕ，ｖ）の画素値を決定する。図示の例では、対応点Ａ（ｘ，ｙ）の近傍に位置する参照画素として、４つの画素Ｑ１〜Ｑ４が抽出された例が示されている。画素Ｐ（ｕ，ｖ）の画素値は、これら４つの参照画素Ｑ１〜Ｑ４の画素値に基づいて決定されることになる。
【００５６】
具体的には、たとえば、参照画素Ｑ１〜Ｑ４の各画素値の単純平均を画素Ｐ（ｕ，ｖ）の画素値とすることもできるが、通常は、対応点Ａ（ｘ，ｙ）と各参照画素Ｑ１〜Ｑ４の代表点（たとえば、中心点）との距離を考慮した補間処理（たとえば、距離が小さいほど大きな重みづけをした加重平均を求める処理）を行うことにより、画素Ｐ（ｕ，ｖ）の画素値を決定する方法がとられる。
【００５７】
図３に示す例は、対応点Ａ（ｘ，ｙ）からの距離が所定範囲内の画素を参照画素とする、という基準に基づいて参照画素の抽出を行ったため、合計４個の参照画素Ｑ１〜Ｑ４が抽出されているが、参照画素の抽出基準は任意に定めることができる。たとえば、対応点Ａ（ｘ，ｙ）を含む画素を中心とした３行３列の合計９個の画素を参照画素として抽出することもできるし、５行５列の合計２５個の画素を参照画素として抽出することもできる。また、補間処理も、加重平均をとる単純な方法だけでなく、スプライン補間法などの高度な補間方法をとることもできる。なお、カラー画像に対して変換処理を行う場合には、たとえば、Ｒ，Ｇ，Ｂという原色プレーンごとに同様の処理を行い、画素Ｐ（ｕ，ｖ）の原色ごとの画素値を決定すればよい。
【００５８】
いずれにしても、このような画像変換処理を行うためには、変換画像Ｂ上の１点Ｂ（ｕ，ｖ）に対応する原画像Ａ上の対応点Ａ（ｘ，ｙ）を求める処理が不可欠である。この処理は、幾何学変換関数Ｇを用いた演算によって行うことができるが、両画像Ａ，Ｂの幾何学的な位置関係が複雑になればなるほど、幾何学変換関数Ｇを用いた演算も複雑になる。特に、全方位カメラで撮影した歪曲円形画像を正則矩形画像に変換するための幾何学変換関数Ｇは、三角関数を含む複雑な関数になるため、画像変換装置の演算負担は大きなものになる。したがって、魚眼レンズを用いた監視システムにおいて、リアルタイムで監視画像を表示する必要がある場合、処理能力の高いプロセッサが必要になる。これは、画像変換装置の製造コストを高騰させるとともに、装置の消費電力を増加させる要因にもなる。
【００５９】
このような問題に対処するため、原画像上の座標値（ｘ，ｙ）と変換画像上の座標値（ｕ，ｖ）との間の対応関係を、画素値決定に必要な離散的な座標ごとに予め演算しておき、その結果を座標変換テーブルという形でメモリに格納しておく手法が用いられる。すなわち、画像変換に利用される幾何学変換関数Ｇは、変換に係る光学的な条件が同一である限り同一であり、光学的な条件に変更が生じない限り、変換画像Ｂ上の所定の座標値（ｕ，ｖ）に対応する原画像Ａ上の座標値（ｘ，ｙ）は同じになる。そこで、必要な座標値（ｕ，ｖ）の組み合わせに対応する座標値（ｘ，ｙ）を予め計算しておき、座標変換テーブルという形で用意しておけば、幾何学変換関数Ｇに基づく演算を行う代わりに、この座標変換テーブルを参照することにより、必要な対応座標値（ｘ，ｙ）を得ることができ、演算負担を大幅に軽減できる。
【００６０】
たとえば、図１に例示した全方位カメラを、現在、女性が立っている付近の状況を常時監視するための定点監視カメラとして利用する場合を考えてみよう。この場合、図示の女性が立ち去り、別な男性が近づいてきたとすると、フレーム単位で撮影される画像の内容は変化することになり、正則矩形画像Ｂ上には男性の画像が表示されることになる。それでも、歪曲円形画像Ａ上の点Ａ（ｘ，ｙ）と正則矩形画像Ｂ上の点Ｂ（ｕ，ｖ）との対応関係に変わりはない。すなわち、歪曲円形画像Ａに対する切出位置、切出向き、切出倍率といったパラメータが固定されている限り、点Ａ（ｘ，ｙ）と点Ｂ（ｕ，ｖ）との対応関係は一定であり、変換に利用される幾何学変換関数Ｇも一定になる。
【００６１】
したがって、図１に示す例の場合は、監視対象領域の切出条件を設定した段階で、当該条件に合致する幾何学変換関数Ｇを定め、必要な座標値（ｕ，ｖ）の組み合わせに対応する座標値（ｘ，ｙ）を予め計算しておき、座標変換テーブルという形で用意しておけば、切出条件が変更にならない限り、当該座標変換テーブルをそのまま利用することができる。
【００６２】
また、図２に示すプロジェクタの例においても、動画を投影する場合、投影用原画像Ａの内容自体はフレーム単位で逐次変化してゆくことになるが、プロジェクタおよびスクリーンの位置が不変である限り、投影用原画像Ａ上の点Ａ（ｘ，ｙ）と台形補正画像Ｂ上の点Ｂ（ｕ，ｖ）との対応関係に変わりはないので、変換に利用される幾何学変換関数Ｇも一定になる。
【００６３】
したがって、図２に示す例の場合は、プロジェクタとスクリーンとを所定の投影条件で設置した段階で、当該条件に合致する幾何学変換関数Ｇを定め、必要な座標値（ｕ，ｖ）の組み合わせに対応する座標値（ｘ，ｙ）を予め計算しておき、座標変換テーブルという形で用意しておけば、切出条件が変更にならない限り、当該座標変換テーブルをそのまま利用することができる。
【００６４】
図４は、変換画像Ｂを構成する各画素Ｐ（ｕ，ｖ）の位置に対応する原画像Ａ上の対応点Ａ（ｘ，ｙ）を、座標変換テーブルＴｘ，Ｔｙを用いて求める原理を示す平面図である。図の上段に示すように、ＵＶ二次元座標系上には、所望の解像度に応じた画素配列が定義される。ここでは、そのうちの任意の１画素を画素Ｐ（ｕ，ｖ）と呼ぶことにする。図の中段には、縦横にセルを配列してなる２つの座標変換テーブルが示されている。ここで、Ｘ座標変換テーブルＴｘは、個々のセルＸ（ｕ，ｖ）内にＸ座標値ｘを収容したテーブルであり、対応点Ａ（ｘ，ｙ）のＸ座標値ｘを得るために用いられる。一方、Ｙ座標変換テーブルＴｙは、個々のセルＹ（ｕ，ｖ）内にＹ座標値ｙを収容したテーブルであり、対応点Ａ（ｘ，ｙ）のＹ座標値ｙを得るために用いられる。
【００６５】
Ｘ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙのセル配列は、変換画像Ｂの画素配列に対応しており、変換画像Ｂ上の１画素Ｐ（ｕ，ｖ）に対して、Ｘ座標変換テーブルＴｘ上の１セルＸ（ｕ，ｖ）とＹ座標変換テーブルＴｙ上の１セルＹ（ｕ，ｖ）とが対応する。したがって、図の上段に示すように、特定の画素Ｐ（ｕ，ｖ）が選択されると、図の中段に示すように、これに対応したセルＸ（ｕ，ｖ）およびＹ（ｕ，ｖ）から座標値ｘおよびｙを抽出することができる。こうして抽出された座標値（ｘ，ｙ）は、図の下段に示すように、原画像Ａ上での対応点Ａ（ｘ，ｙ）の位置を示している。結局、図の上段に示す変換画像Ｂ上の選択画素Ｐ（ｕ，ｖ）に対して、図の中段に示す座標変換テーブルＴｘ，Ｔｙを参照することにより、図の下段に示す原画像Ａ上の対応点Ａ（ｘ，ｙ）が求まる。こうして、対応点Ａ（ｘ，ｙ）が求まれば、その近傍に位置する原画像Ａ上の画素の画素値に基づいて、選択画素Ｐ（ｕ，ｖ）の画素値が決定できることは、既に述べたとおりである。
【００６６】
ＵＶ二次元座標系上の任意の画素Ｐ（ｕ，ｖ）の位置座標（たとえば、中心点Ｂ（ｕ，ｖ）の位置座標）とＸＹ二次元座標系上の対応点Ａ（ｘ，ｙ）の位置座標との関係は、原画像Ａと変換画像Ｂとの位置関係に基づいて幾何学変換関数Ｇによって定義され、両画像Ａ，Ｂの位置関係が一定であれば、幾何学変換関数Ｇも一定である。したがって、両画像Ａ，Ｂの位置関係が固定されていれば、Ｘ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙの内容は不変になる。
【００６７】
このため、幾何学変換関数Ｇを用いて、必要な座標値（ｕ，ｖ）の組み合わせ（すなわち、変換画像Ｂを構成する個々の画素についての（ｕ，ｖ））について、予め対応する（ｘ，ｙ）の組み合わせを演算しておき、Ｘ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙを作成しておけば、両画像Ａ，Ｂの位置関係が変化しない限り、幾何学変換関数Ｇを用いた演算を行う代わりに、これらテーブルＴｘ，Ｔｙを参照するだけで、各画素Ｐ（ｕ，ｖ）についての対応点Ａ（ｘ，ｙ）を得ることができる。このように、座標変換テーブルを利用した画像変換処理を行うと、演算負担を大幅に軽減するメリットが得られる。
【００６８】
図５は、座標変換テーブルを用いて変換を行う画像変換装置１００の基本構成を示すブロック図である。図示のとおり、この画像変換装置１００は、変換テーブル設定部１１０、変換処理用メモリ１２０、原画像入力部１３０、変換処理部１４０、変換画像出力部１５０を備えており、原画像Ａを変換画像Ｂに変換する画像変換処理を行う機能を有している。
【００６９】
変換処理用メモリ１２０には、図示のとおり、原画像Ａおよび変換画像Ｂの他、Ｘ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙが格納されている。原画像入力部１３０は、ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像Ａを画像データとして変換処理用メモリ１２０に格納する処理を行う。変換処理部１４０は、この原画像Ａに基づいて、変換処理用メモリ１２０内に変換画像Ｂとなる画像データを作成する処理を行う。作成された変換画像Ｂは、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる画像になる。変換画像出力部１５０は、こうして作成された変換画像Ｂを出力する処理を行う。
【００７０】
一方、変換テーブル設定部１１０は、変換に用いるＸ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙを変換処理用メモリ１２０内に格納する処理を行う。変換処理部１４０は、図４で説明した原理に基づいて、これらのテーブルＴｘ，Ｔｙを参照しながら変換画像Ｂを構成する個々の画素Ｐ（ｕ，ｖ）の画素値を決定する処理を行うことになる。上述したとおり、原画像Ａと変換画像Ｂとの間の幾何学的な位置関係が固定されている限り、同一の座標変換テーブルＴｘ，Ｔｙを利用して変換処理を行うことができる。したがって、変換テーブル設定部１１０は、原画像Ａと変換画像Ｂとの間の幾何学的な位置関係が変更された時に、新たな座標変換テーブルＴｘ，Ｔｙを変換処理用メモリ１２０内に設定する処理を行えばよい。
【００７１】
たとえば、図１に例示した全方位カメラを、特定の場所を常時監視するための定点監視カメラとして利用する場合、監視場所や表示倍率などを新たに設定しなおす場合に、変換テーブル設定部１１０によって新たな座標変換テーブルＴｘ，Ｔｙを変換処理用メモリ１２０内に設定する処理を行えばよい。同様に、図２に示すプロジェクタの例では、スクリーンとプロジェクタとの位置関係や投影倍率などを新たに設定しなおす場合に、変換テーブル設定部１１０によって新たな座標変換テーブルＴｘ，Ｔｙを変換処理用メモリ１２０内に設定する処理を行えばよい。
【００７２】
ところで、図５に示す画像変換装置１００を構成する上で、変換処理用メモリ１２０としては、高速なアクセスが可能なメモリを用いるのが好ましい。一般的な動画には、１秒間に３０フレーム程度の静止画の情報が含まれているため、このような動画を構成する原画像Ａをリアルタイムで変換画像Ｂに変換する処理を行うためには、変換処理部１４０には、それなりの処理速度が要求される。ところが、変換処理用メモリ１２０のアクセス速度が不十分であると、変換処理部１４０は十分な速度で変換処理を行うことができなくなる。このような事情から、変換処理用メモリ１２０としては、通常、高速な読み書きが可能なＲＡＭが用いられるが、その容量が増えれば増えるほど、ハードウエアのコストは高騰せざるを得ない。
【００７３】
その一方で、Ｘ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙは、図４に示すとおり、作成する変換画像Ｂの画素配列と同じ配列をもった配列データになるため、変換画像Ｂのサイズが大きければ大きいほど、座標変換テーブルＴｘ，Ｔｙの配列サイズも大きくなる。しかも、これらのテーブルの各セルＸ（ｕ，ｖ），Ｙ（ｕ，ｖ）に収容される座標値ｘ，ｙは、幾何学変換関数Ｇに基づく演算によって得られる値であるため、一般的には画素配列の行や列に応じた整数にはならない。したがって、ある程度の変換精度を維持するためには、各座標変換テーブルＴｘ，Ｔｙには、ある程度の有効桁数を有する座標値ｘ，ｙを収容しておく必要がある。
【００７４】
このような事情を考慮すると、変換テーブル設定部１１０が、Ｘ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙを変換処理用メモリ１２０内に格納する際に、これらのテーブルに対して圧縮処理を施し、メモリの占有容量をできるだけ低減するようにし、変換処理部１４０が、Ｘ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙから必要な座標値ｘ，ｙを読み出す際には、圧縮処理に対応した伸張処理を施すようにするのが好ましい。本発明は、このような座標変換テーブルを構成する配列データに対して最適な圧縮方法を提案するものである。
【００７５】
＜＜＜  §２．  本発明に係る圧縮プロセスの実例  ＞＞＞
＜２−１：  座標変換テーブルに固有の特徴＞
上述したとおり、本発明は、幾何学的な画像変換処理を行う際に、座標変換テーブルを構成する配列データに対して効率的な圧縮を行う方法を提供するものである。そこで、ここでは、まず、このような座標変換テーブルに固有の特徴を検討してみよう。
【００７６】
図６は、図５に示すＸ座標変換テーブルＴｘの構成例を示す平面図である。図示のとおり、Ｘ座標変換テーブルＴｘを構成する個々のセル内には、それぞれ所定のｘ座標値が収容されている。ここで、左右に隣接する２つのセル内のｘ座標値に着目すると、相互に近似した値になっているはずであり、また、上下に隣接する２つのセル内のｘ座標値に着目すると、やはり相互に近似した値になっているはずである。たとえば、図６に示す例の場合、セルα内の座標値ｘαとセルβ内の座標値ｘβとは互いに近似した値になり、セルγ内の座標値ｘγとセルδ内の座標値ｘδとは互いに近似した値になる。
【００７７】
このような現象が生じることは、たとえば、図１に示す例において、正則矩形画像Ｂ上の点Ｂ（ｕ，ｖ）に隣接する点Ｂ′（ｕ′，ｖ′）をプロットし、これらについて、それぞれ歪曲円形画像Ａ上の対応点Ａ（ｘ，ｙ）およびＡ′（ｘ′，ｙ′）の位置を考えれば理解できよう。正則矩形画像Ｂ上の点Ｂ′（ｕ′，ｖ′）が、点Ｂ（ｕ，ｖ）の右隣、左隣、上隣、下隣のいずれの点であったとしても、歪曲円形画像Ａ上での対応点Ａ′（ｘ′，ｙ′）の位置は対応点Ａ（ｘ，ｙ）に隣接した位置になるので、座標値ｘと座標値ｘ′とは互いに近似した値になり、座標値ｙと座標値ｙ′とは互いに近似した値になる。
【００７８】
したがって、Ｘ座標変換テーブルＴｘやＹ座標変換テーブルＴｙの隣接するセル内の座標値は互いに近似した値になるので、個々のセル内の座標値について、横方向の差分値や縦方向の差分値をとると、当該差分値自身は比較的小さな値になることが予想される。
【００７９】
たとえば、図６に示す例において、左右に隣接するセルα，β内の座標値ｘα，ｘβは互いに近似した値になるので、両者の差Ｄβ＝ｘβ−ｘαを求め、セルβ内の座標値ｘβを差分値Ｄβに置換すれば、セルβ内の情報量を圧縮することができる。もちろん、セルβ内の本来の座標値ｘβが必要な場合には、ｘβ＝ｘα＋Ｄβなる伸張演算を行えばよい。同様に、上下に隣接するセルγ，δ内の座標値ｘγ，ｘδも互いに近似した値になるので、両者の差Ｄδ＝ｘδ−ｘγを求め、セルδ内の座標値ｘδを差分値Ｄδに置換すれば、セルδ内の情報量を圧縮することができる。もちろん、セルδ内の本来の座標値ｘδが必要な場合には、ｘδ＝ｘγ＋Ｄδなる伸張演算を行えばよい。
【００８０】
＜２−２：  第１差分演算段階＞
以下、上述した基本原理に基づいて、Ｘ座標変換テーブルＴｘを構成する配列データを圧縮する具体的なプロセスを説明する。このプロセスは、前半段階（第１差分演算段階）と後半段階（第２差分演算段階）とによって構成される。まず、§２−２では、前半段階（第１差分演算段階）のプロセスを説明する。
【００８１】
いま、図７に示すような配列データＸが、圧縮対象となる配列データとして与えられた場合を考えてみる。ここでは、説明の便宜上、８行８列の小規模な行列状に並んだ６４個のセル内に、それぞれｘ１１〜ｘ８８なる数値が収容された配列データの例を示しているが、本発明に係る圧縮方法は、一般に、複数Ｍ行、複数Ｎ列からなる行列状に配置されたセル内に数値が収容された配列データに対して適用可能である。
【００８２】
なお、以下の説明において、図では各セル内の数値をｘ１１，ｘ１２，ｘ１３，...，ｘ８８のように、符号ｘに続けてセルの行番号および列番号を並べて表記することにするが、数式では、セルの行番号をパラメータｉ、セルの列番号をパラメータｊで表し、各セル内の数値をｘ（ｉ，ｊ）のように表記することにする。また、２つの数の差として得られる差分値については、数値ｘと直観的に区別しやすいように大文字のＤもしくはＥを用い、個々のセル内では、Ｄ１２，Ｄ１３，Ｄ１４，... 、あるいは、Ｅ１２，Ｅ１３，Ｅ１４，... のように表記し、数式では、Ｄ（ｉ，ｊ）やＥ（ｉ，ｊ）のように表記することにする。
【００８３】
さて、はじめに、図７に示す圧縮対象配列データＸの第１行目のセル内の数値について、横方向に差分をとって、各セル内の数値ｘを差分値Ｄに置換してみよう。但し、第１行第１列目の数値ｘ１１は基準値として、そのまま残すことにする。図８は、このようにして、第１行目のセル内の数値に対して、横方向の差分値による置換を行った状態を示す平面図である。数値ｘ１１は元のままであるが、２列目〜８列目までの数値ｘ１２〜ｘ１８は、差分値Ｄ１２〜Ｄ１８に置き換えられている。図では、こうして置換が行われたセルを太枠で示してある。
【００８４】
より具体的には、Ｄ１２は、Ｄ１２＝ｘ１２−ｘ１１で与えられる差分値、Ｄ１３は、Ｄ１３＝ｘ１３−ｘ１２で与えられる差分値、Ｄ１４は、Ｄ１４＝ｘ１４−ｘ１３で与えられる差分値、,,, 、Ｄ１８は、Ｄ１８＝ｘ１８−ｘ１７で与えられる差分値になっている。一般式で示すと、第１行第（ｊ＋１）列目のセルを置換する差分値Ｄ（１，ｊ＋１）は、Ｄ（１，ｊ＋１）＝ｘ（１，ｊ＋１）−ｘ（１，ｊ）なる演算式で与えられる数値になる（但し、ｊ＝１〜７）。結局、太枠内のセルの数値は、元の数値と左に隣接するセル内の数値との差に相当する差分値によって置き換えられたことになる。
【００８５】
図９は、同様の置換処理を、第２行目〜第８行目についても行った結果を示す。すなわち、Ｄ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ＋１）−ｘ（ｉ，ｊ）なる演算式に基づいて、図７に示す圧縮対象配列データＸの第ｉ行第（ｊ＋１）列目のセル内の数値ｘ（ｉ，ｊ＋１）を差分値Ｄ（ｉ，ｊ＋１）に置換する処理を、ｉ＝１〜８およびｊ＝１〜７の各組み合わせについて実行した結果である。図では、こうして置換が行われたセルを太枠で示してある。第１列目の８個のセルを除いて、他のすべてのセルについて置換が行われたことになる。本願では、このような処理段階を横方向第１置換段階と呼ぶことにする。図９は、図７に示す圧縮対象配列データＸに対して、横方向第１置換段階の処理を施した結果ということになる。
【００８６】
上述した横方向第１置換段階の処理において、第１列目は基準列として機能し、この基準列に属する８個のセル内の数値ｘ１１〜ｘ８１は、第２〜８列目のセルを置換した差分値に対する基準値としての役割を果たす。別言すれば、各セルを置換した差分値は、基準値を利用することにより、元の数値に復元することが可能である。たとえば、図９に示す第１行第２列目の差分値Ｄ１２は、基準値ｘ１１を利用して、ｘ１２＝Ｄ１２＋ｘ１１なる演算を行うことにより、置換前の元の数値ｘ１２に戻すことができる。こうして、数値ｘ１２が得られれば、第１行第３列目の差分値Ｄ１３は、ｘ１３＝Ｄ１３＋ｘ１２なる演算を行うことにより、置換前の元の数値ｘ１３に戻すことができる。
【００８７】
このように、各行の第１列目（基準列）の数値は基準値としての役割を果たすために必要な数値であるが、これら基準列の数値に対して、今度は、縦方向に差分をとる処理を行えば、第１行第１列目のセル（基準セル）を除いて、差分値に置換することが可能である。本願では、このような処理段階を縦方向第１置換段階と呼ぶことにする。図１０は、図９に示す横方向第１置換段階後の配列データに対して、更に、縦方向第１置換段階の処理を施した結果を示す。ここでも、置換が行われたセルを太枠で示してある。
【００８８】
具体的には、図１０に示すＤ２１は、Ｄ２１＝ｘ２１−ｘ１１で与えられる差分値、Ｄ３１は、Ｄ３１＝ｘ３１−ｘ２１で与えられる差分値、Ｄ４１は、Ｄ４１＝ｘ４１−ｘ３１で与えられる差分値、,,, 、Ｄ８１は、Ｄ８１＝ｘ８１−ｘ７１で与えられる差分値になっている。結局、太枠内のセルの数値は、元の数値と上に隣接するセル内の数値との差に相当する差分値によって置き換えられたことになる。この縦方向第１置換段階の処理を一般式で示すと、Ｄ（ｉ＋１，１）＝ｘ（ｉ＋１，１）−ｘ（ｉ，１）なる演算式に基づいて、図９に示す横方向第１置換段階後の配列データの第（ｉ＋１）行第１列目のセル内の数値ｘ（ｉ＋１，１）を差分値Ｄ（ｉ＋１，１）に置換する処理を、ｉ＝１〜７について実行する処理ということになる。
【００８９】
本願では、この図１０に示す縦方向第１置換段階の処理の結果として得られる配列データを、第１差分配列データＤと呼ぶことにする。図１１は、この第１差分配列データＤを示す平面図である（各セルの内容は、図１０と同じ）。図１１に示す第１差分配列データＤを、図７に示す圧縮対象配列データＸと比べてみると、二重枠で示す第１行第１列目のセル（基準セル）の値ｘ１１は元のままであるが、その他のセルの値はすべて差分値Ｄに置換されていることがわかる。各差分値Ｄは、左もしくは上に隣接するセル内の数値との差であるため、圧縮対象配列データＸが、幾何学的な画像変換処理を行う際に用いる座標変換テーブルである場合には、比較的小さな値になり、個々のセル内の情報量の低減が図られたことになる。
【００９０】
もちろん、基準セル内の値ｘ１１は、元の数値のままであるので、上述した差分値を求める圧縮プロセスと逆の伸長プロセスを行うことにより、図１１に示す第１差分配列データＤを図７に示す圧縮対象配列データＸに戻すことが可能である。たとえば、図７に示す第２行第１列目の差分値Ｄ２１は、基準値ｘ１１を利用して、ｘ２１＝Ｄ２１＋ｘ１１なる演算を行うことにより、置換前の元の数値ｘ２１に戻すことができる。こうして、数値ｘ２１が得られれば、第３行第１列目の差分値Ｄ３１は、ｘ３１＝Ｄ３１＋ｘ２１なる演算を行うことにより、置換前の元の数値ｘ３１に戻すことができる。こうして、図９に示すように、基準列となる第１列目の数値ｘ１１〜ｘ８１が復元できたら、前述したように、各基準列の数値に基づいて横方向の復元を行えば、圧縮対象配列データＸを復元することができる。
【００９１】
続いて、上述した横方向第１置換段階（図９）および縦方向第１置換段階（図１０）を実行した場合の圧縮効果を、具体的な数値を用いた実例で示しておく。図１２は、図７に示す圧縮対象配列データＸの具体的な実例を示す平面図である。この例では、各セルに、１０進表示で「２３０００」前後の数値が収容された配列データが示されている。いずれの数値も１０進表示では５桁を要する値であるが、２進数として取り扱うためには、より多くの桁数を必要とし、このような配列データをメモリ上に格納するためには、多数のメモリビットが必要になる。
【００９２】
図１３は、図１２に示す圧縮対象配列データＸに対して、横方向第１置換段階の処理を実行した結果を示す。図示のとおり、基準列（第１列目）を除いて、各セル内の値は、２８〜３０の差分値に置き換えられており、この段階でも十分な圧縮効果が得られていることがわかる。
【００９３】
図１４は、図１３に示す配列データに対して、更に、縦方向第１置換段階の処理を実行することにより得られる第１差分配列データＤを示す。図示のとおり、基準列（第１列目）についても、縦方向に差分をとる処理が行われたため、基準セル（第１行第１列目のセル）を除いて、基準列内の各セル内の値は、−３または−４の差分値に置き換えられており、圧縮効果が更に高まっていることがわかる。
【００９４】
以上述べた横方向第１置換段階の処理および縦方向第１置換段階の処理を、本願では、第１差分演算段階と呼ぶことにする。この第１差分演算段階は、本発明に係る圧縮プロセスの前半段階の処理であり、第１差分演算段階によって得られる第１差分配列データＤ（図１１，図１４）は、本発明における中途段階の圧縮データということになる。
【００９５】
＜２−３：  第２差分演算段階＞
続いて、本発明に係る圧縮プロセスの後半段階となる第２差分演算段階の処理を説明する。この第２差分演算段階では、図１１に示す第１差分配列データＤに対して、更なるデータ圧縮処理が行われる。これは、図１４の実例を見ればわかるとおり、第１差分配列データＤにおいても、上下左右に隣接するセル内の数値が互いに近似する特徴が見られ、更なる圧縮が可能なためである。はじめに、各セルについて縦方向に差分をとって、各セル内の数値Ｄを差分値Ｅに置換する縦方向第２置換段階を実行する。このとき、第１行目を基準行とし、この基準行のセルは置換処理の対象から除外されるようにする。また、ここに示す実施形態では、第２行第１列目のセルも置換処理の対象から除外している。
【００９６】
図１５は、このようにして、縦方向第２置換段階を実行した結果として得られる配列データを示している。太枠で示すセルは、置換が行われたセルである。具体的には、Ｅ２２は、Ｅ２２＝Ｄ２２−Ｄ１２で与えられる差分値、Ｅ２３は、Ｅ２３＝Ｄ２３−Ｄ１３で与えられる差分値、,,, 、Ｅ２８は、Ｅ２８＝Ｄ２８−Ｄ１８で与えられる差分値である。同様に、Ｅ３１は、Ｅ３１＝Ｄ３１−Ｄ２１で与えられる差分値、Ｅ３２は、Ｅ３２＝Ｄ３２−Ｄ２２で与えられる差分値、Ｅ３３は、Ｅ３３＝Ｄ３３−Ｄ２３で与えられる差分値、,,, 、Ｅ３８は、Ｅ３８＝Ｄ３８−Ｄ２８で与えられる差分値である。
【００９７】
結局、この縦方向第２置換段階の処理は、Ｅ（ｉ＋１，ｊ）＝Ｄ（ｉ＋１，ｊ）−Ｄ（ｉ，ｊ）なる演算式に基づいて、図１１に示す第１差分配列データＤの第（ｉ＋１）行第ｊ列目のセル内の数値Ｄ（ｉ＋１，ｊ）を差分値Ｅ（ｉ＋１，ｊ）に置換する処理を、ｉ＝１〜７およびｊ＝１〜８の各組み合わせ（但し、ｉ＝１，ｊ＝１の組み合わせは除く）について実行する処理ということになる。
【００９８】
上述したとおり、第１行目は基準行として機能し、この基準行に属する７個のセル内の差分値Ｄ１２〜Ｄ１８は、第２行目の第２〜８列目のセルを置換した差分値Ｅ２２〜Ｅ２８に対する基準値としての役割を果たす。したがって、差分値Ｅ２２〜Ｅ２８は、各基準値を利用することにより、元の差分値Ｄ２２〜Ｄ２８に戻すことができる。たとえば、差分値Ｅ２２は、上に隣接するセル内の基準値Ｄ１２を利用して、Ｄ２２＝Ｅ２２＋Ｄ１２なる演算を行うことにより、置換前の元の差分値Ｄ２２に戻すことができる。こうして、差分値Ｄ２２が得られれば、その下に隣接するセルの差分値Ｅ３２は、Ｄ３２＝Ｅ３２＋Ｄ２２なる演算を行うことにより、置換前の元の差分値Ｄ３２に戻すことができる。
【００９９】
このように、第１行目は基準行としての機能を果たすため、第１行目の各セルは、縦方向第２置換段階における置換処理の対象からは除外される。一方、図示の実施形態では、第２行第１列目のセルも置換処理の対象から除外しており、当該セル内の差分値Ｄ２１は、差分値Ｅ２１に置換されることなく、元の差分値Ｄ２１のまま維持されている。この差分値Ｄ２１は、基準値としての役割を果たす必要はないので（縦方向の基準値としての役割は、第１行第１列目の数値ｘ１１が果たしている）、理論的には、Ｅ２１＝Ｄ２１−ｘ１１なる演算によって得られる差分値Ｅ２１に置換してもかまわない。それにもかかわらず、差分値Ｄ２１を置換処理の対象から除外している理由は、置換処理を行うと、データの桁数がかえって増加してしまい、データ圧縮の効果を損なう結果となってしまうためである。
【０１００】
これは、図１４に実例として示す第１差分配列データＤに対して、縦方向第２置換段階を実行する例を考えてみれば容易に理解できる。すなわち、図１４に示す例において、第２行第１列目のセル内の値「−３」について、上に隣接するセル内の値「２２９２２」との差分値Ｅ２１を求めると、差分値Ｅ２１＝（−３）−（２２９２２）＝−２２９２５となるため、置換前の値「−３」よりも置換後の値「−２２９２５」の方が桁数が増加してしまう結果となる。したがって、実用上は、縦方向第２置換段階を実行する際には、基準行となる第１行目のセルだけでなく、第２行第１列目のセルも置換処理の対象から除外するのが好ましい。もちろん、第２行第１列目のセルを除外する処理が煩雑である場合は、除外しない実施形態を採用してもかまわない。この場合、データ圧縮の効果は若干損なわれることになるが、第１行目のセルだけを置換処理の対象から除外すればよいので、除外処理は単純化される。
【０１０１】
さて、続いて、基準行としての機能を果たした第１行目のセルについて、横方向に差分をとる処理を行い、圧縮効率を更に高める処理を行う。本願では、このような処理段階を横方向第２置換段階と呼んでいる。図１６は、図１５に示す縦方向第２置換段階後の配列データに対して、更に、横方向第２置換段階の処理を施した結果を示す。置換が行われたセルは太枠で示されているとおり、第１行目の第３〜８列目のセルである。
【０１０２】
具体的には、図１６に示すＥ１３は、Ｅ１３＝Ｄ１３−Ｄ１２で与えられる差分値、Ｅ１４は、Ｅ１４＝Ｄ１４−Ｄ１３で与えられる差分値、,,, 、Ｅ１８は、Ｅ１８＝Ｄ１８−Ｄ１７で与えられる差分値になっている。要するに、太枠内のセルの数値は、元の数値と左に隣接するセル内の数値との差に相当する差分値によって置き換えられたことになる。
【０１０３】
なお、第１行第１列目のセルが置換対象から除外されているのは、当該セルが、基準値ｘ１１を収容する基準セルとして機能するためである。また、第１行第２列目のセルが置換対象から除外されているのは、当該セルを置換対象とすると、置換前の値よりも置換後の値の方が桁数が増加してしまう結果となるためである。
【０１０４】
結局、この横方向第２置換段階の処理を一般式で示すと、Ｅ（１，ｊ＋１）＝Ｄ（１，ｊ＋１）−Ｄ（１，ｊ）なる演算式に基づいて、縦方向第２置換段階後の配列データの第１行第（ｊ＋１）列目のセル内の数値Ｄ（１，ｊ＋１）を差分値Ｅ（１，ｊ＋１）に置換する処理を、ｊ＝２〜７について実行する処理ということになる。
【０１０５】
本願では、この図１６に示す横方向第２置換段階の処理の結果として得られる配列データを、第２差分配列データＥと呼ぶことにする。図１７は、この第２差分配列データＥを示す平面図である（各セルの内容は、図１６と同じ）。図１７に示す第２差分配列データＥを、図１１に示す第１差分配列データＤと比べてみると、二重枠で示す第１行第１列目のセルの値ｘ１１、第１行第２列目のセルの値Ｄ１２、第２行第１列目のセルの値Ｄ２１は元のままであるが、その他のセルの値はすべて差分値Ｅに置換されていることがわかる。ここでもやはり、上述した差分値を求める圧縮プロセスと逆の伸長プロセスを行うことにより、図１７に示す第２差分配列データＥを図１１に示す第１差分配列データＤに戻すことが可能であり、更に、図７に示す圧縮対象配列データＸに戻すことも可能である。
【０１０６】
続いて、上述した縦方向第２置換段階（図１５）および横方向第２置換段階（図１６）を実行した場合の圧縮効果を、具体的な数値を用いた実例で示しておく。既に、§２−２において、図１２に示すような圧縮対象配列データＸに対して横方向第１置換段階を行うことにより図１３に示すような配列データが得られ、更に、縦方向第１置換段階を行うことにより図１４に示すような第１差分配列データＤが得られることを示した。図１８は、この図１４に示す第１差分配列データＤに対して、更に、縦方向第２置換段階（図１５）および横方向第２置換段階（図１６）を実行した場合に得られる第２差分配列データＥを示すものである。
【０１０７】
図１８に示す第２差分配列データＥを見ると、第１行第１列の「２２９２２」、第１行第２列の「２９」、第２行第１列の「−３」という３つのセル内の数値を除いて、他のすべてのセル内の数値が、−２〜＋２の範囲内の数値に収まっていることがわかる。これは、図１４に示す第１差分配列データＤに比べて、更なるデータ圧縮が行われていることを示している。もちろん、図１８に示す第２差分配列データＥを、図１２に示す圧縮対象配列データＸに比べれば、本発明に係る圧縮プロセスにより、極めて高い圧縮効果が得られることが理解できよう。
【０１０８】
しかも、これまで述べてきた圧縮プロセスと逆の伸長プロセスを行うことにより、図１８に示す第２差分配列データＥを、図１４に示す第１差分配列データＤに復元することができ、更に、これを図１２に示す圧縮対象配列データＸに復元することができる。このように、本発明に係る圧縮プロセスは、極めて高い圧縮効果が得られるものの、完全な可逆圧縮方式を採用するものであるため、座標変換テーブルの圧縮に利用したとしても、テーブル自身の情報量が損なわれることはない。
【０１０９】
また、本発明に係る圧縮プロセスや伸張プロセスは、隣接するセル間における単なる差分演算もしくはその逆演算であり、必要な演算は、減算もしくは加算だけである。このため、圧縮プロセスや伸張プロセスの演算負担は極めて軽いものになり、画像変換処理に利用したとしても、圧縮処理や伸張処理の演算負担が支障を及ぼすことはない。
【０１１０】
図１９は、図１７および図１８に示す第２差分配列データＥの特徴を示す平面図である。左上隅において「ＤＣ」，「ＲＣ」，「ＢＣ」と記された３つのセルは、図１７に二重枠で示されているセルであり、他のセルとは若干異なる取り扱いがなされている。すなわち、他の一般セルは、第１差分演算段階と第２差分演算段階の双方において、それぞれ差分値に置換される処理が施されており、合計２回の置換処理が行われている。より具体的に説明すれば、第１行目に所属する第３〜８列目の斜線ハッチングを施したセルは、横方向に差分をとる処理が２回繰り返されたセルであり、第１列目に所属する第３〜８行目の斜線ハッチングを施したセルは、縦方向に差分をとる処理が２回繰り返されたセルである。そして、ドットによるハッチングを施した残りの一般セルは、縦方向と横方向にそれぞれ１回ずつ差分をとる処理が施されたセルである。
【０１１１】
このように、図１９に斜線もしくはドットによるハッチングを施して示す一般セルは、いずれも差分値による置換処理が合計２回行われている。図１８に示す実例において、これら一般セル内の数値が−２〜＋２という極めて小さな値に収まっているのは、合計２回の置換処理の成果である。特に、ドットによるハッチングを施して示すセルは、縦方向と横方向との双方向に関して差分がとられているため、圧縮効率は非常に高くなる。
【０１１２】
これに対して、第１行第１列目のセル内の値「ＤＣ」は、この配列データ全体の基準値を示すものであり、差分値による置換処理の対象にはなっていない。ここで「ＤＣ」は「Direct Current」の略であり、いわば各セルの数値の直流成分を示している。一方、第１行第２列目のセル内の値「ＲＣ」は、「Right Coefficient」の略であり、「ＤＣ」の右隣のセルとして、１回だけ横方向の差分値による置換処理が行われた数値ということになる。また、第２行第１列目のセル内の値「ＢＣ」は、「Bottom Coefficient」の略であり、「ＤＣ」の下隣のセルとして、１回だけ縦方向の差分値による置換処理が行われた数値ということになる。
【０１１３】
数値「ＲＣ」，「ＢＣ」について、２回目の置換処理を行わない理由は、既に述べたとおり、数値「ＤＣ」との間の２回目の差分値をとると、１回目の置換処理で得られた差分値よりも桁数が増えてしまうためである。このような理由から、第２差分配列データＥにおいて、左上隅の３つのセル内の数値「ＤＣ」，「ＲＣ」，「ＢＣ」は、他の一般セル内の数値とは若干異なる値になる。
【０１１４】
＜２−４：  配列データのブロック分割＞
これまで、本発明に係るデータ圧縮方法を、８行８列の配列データを例にとって説明したが、この方法は、実際にはより大きなサイズの配列データに対して実施することが可能であり、一般論としては、Ｍ行Ｎ列の配列データに対して行うことができる。ここで、行の総数Ｍや列の総数Ｎは、理論的には、２以上の整数であれば、どのような数であってもよい。
【０１１５】
ただ、圧縮対象となる元の配列データが、あまり大きなサイズの配列である場合には、この元配列データをいくつかのブロックに分割し、個々のブロックをそれぞれ圧縮対象配列データＸとして、これまで述べてきたデータ圧縮方法を個別に適用するのが好ましい。これは、複数のブロックに分割することにより、個々のブロック単位で伸張処理を行うことができるためである。
【０１１６】
図２０は、μ行ν列からなる元配列データを、複数のブロックに分割した状態を示す平面図である。図示のとおり、元配列データは、合計１２個のブロックＢ（１，１），Ｂ（１，２），ブロックＢ（１，３），... ，ブロックＢ（３，４）に分割されている。個々のブロックは、いずれもＭ行Ｎ列からなる配列データであり、それぞれに対して、これまで述べてきた圧縮プロセスを適用することができ、また、その逆の伸張プロセスにより元の配列データに戻すことができる。なお、μがＭの整数倍でない場合や、νがＮの整数倍でない場合は、一部のブロックの配列データのサイズをＭ行Ｎ列よりも小さくするようにしてもよいし、ダミーとなるデータ（たとえば、隣接するセル内の数値と同一の数値）を追加して、Ｍ行Ｎ列の配列データとして取り扱うようにしてもよい。
【０１１７】
このようなブロック分割を行うと、個々のブロック単位で圧縮プロセスが行われるため、個々のブロックについて、図１９に示すような特徴をもった第２差分配列データが得られることになる。図２０には、個々のブロックごとに得られた「ＤＣ」，「ＲＣ」，「ＢＣ」がそれぞれ示されている。たとえば、ブロックＢ（１，１）内に示されたＤＣ（１，１），ＲＣ（１，１），ＢＣ（１，１）は、ブロックＢ（１，１）に対して圧縮プロセスを実施することにより得られた「ＤＣ」，「ＲＣ」，「ＢＣ」の値である。
【０１１８】
ブロック単位で圧縮プロセスを行うと、伸張プロセスもブロック単位で行うことが可能になる。たとえば、図２０に示すブロックＢ（１，３）内の一部のセルについて、圧縮前の本来の値を取り出したい場合、ＤＣ（１，３）を基準値として当該ブロックＢ（１，３）内のみに対して伸張プロセスを実行すればよい。ブロック分割を行わずに圧縮した場合、ＤＣ（１，１）が唯一の基準値となるため、ＤＣ（１，１）のセルから順に元の数値を復元してゆく伸張プロセスが必要になるが、ブロック分割を行っておけば、必要なブロックについてのみ伸張プロセスを行えば足りる。
【０１１９】
もっとも、ブロック分割を行うと、個々のブロックごとに「ＤＣ」，「ＲＣ」，「ＢＣ」が得られることになり、全体的な圧縮効率が低下することは否めない（前述したとおり、「ＤＣ」，「ＲＣ」，「ＢＣ」は、他の一般セルに比べて圧縮効率が低い）。ブロック分割した場合に圧縮効率を改善するには、第２差分配列データＥ内の「ＤＣ」，「ＲＣ」，「ＢＣ」の３つの値に関してブロック間で差分をとり、差分値による置換処理を行い、第３差分配列データＦを得るようにすればよい。
【０１２０】
たとえば、図２０に示す例の場合、ブロックＢ（１，１）を基準ブロックとして、各値ＤＣ（１，１），ＲＣ（１，１），ＢＣ（１，１）をそのまま維持し、それ以外のブロックの「ＤＣ」，「ＲＣ」，「ＢＣ」については、隣接するブロックの「ＤＣ」，「ＲＣ」，「ＢＣ」との間の差分値に置換する処理を行い、第３差分配列データＦを得るようにすればよい。
【０１２１】
具体的には、ブロックＢ（１，２）に関しては、ＤＣ（１，２），ＲＣ（１，２），ＢＣ（１，２）の各値を、それぞれＤＣ（１，２）−ＤＣ（１，１），ＲＣ（１，２）−ＲＣ（１，１），ＢＣ（１，２）−ＢＣ（１，１）なる差分値（左隣のブロックＢ（１，１）内の「ＤＣ」，「ＲＣ」，「ＢＣ」との差分値）に置換する処理を行い、ブロックＢ（１，３）に関しては、ＤＣ（１，３），ＲＣ（１，３），ＢＣ（１，３）の各値を、それぞれＤＣ（１，３）−ＤＣ（１，２），ＲＣ（１，３）−ＲＣ（１，２），ＢＣ（１，３）−ＢＣ（１，２）なる差分値（左隣のブロックＢ（１，２）内の「ＤＣ」，「ＲＣ」，「ＢＣ」との差分値）に置換する処理を行えばよい。
【０１２２】
また、２行目のブロックに関しては、ブロックＢ（２，１）内の「ＤＣ」，「ＲＣ」，「ＢＣ」については、上隣のブロックＢ（１，１）（基準ブロック）内の「ＤＣ」，「ＲＣ」，「ＢＣ」との差分値による置換を行い、以下、ブロックＢ（２，２）以降については、左隣のブロック内の「ＤＣ」，「ＲＣ」，「ＢＣ」との差分値による置換を行うようにすればよい。
【０１２３】
結局、基準ブロックＢ（１，１）は、第２差分配列データＥのままの状態になるが、それ以外のブロックは、上述した置換処理を施すことにより、第３差分配列データＦに置き換えられることになり、「ＤＣ」，「ＲＣ」，「ＢＣ」について、更なるデータ圧縮が行われることになる。
【０１２４】
＜＜＜  §３．  本発明に係る圧縮／伸張方法  ＞＞＞
＜３−１：  本発明に係る圧縮／伸張方法の基本概念＞
§２では、本発明に係る圧縮方法の具体的な手順を実例を挙げながら説明した。そこで、ここでは、本発明に係る圧縮方法および伸張方法の基本概念を一般論として述べる。
【０１２５】
本発明に係る圧縮方法は、複数の行および複数の列を有する配列データを圧縮する方法であり、実際には、コンピュータによって実行される。そのため、まず、コンピュータが、図７に示すような行列状に並んだ各セルについての数値の集合体からなる圧縮対象配列データＸを入力するデータ入力段階が行われる。
【０１２６】
続いて、コンピュータが、少なくとも所定の基準列に属するセルを除いて、圧縮対象配列データＸの個々のセル内の数値を、左もしくは右に隣接するセル内の数値との差分値に置き換える作業を含む置換処理を実行することにより、第１差分配列データＤを作成する第１差分演算段階を実行する。§２−２では、図７に示す圧縮対象配列データＸに対して第１差分演算段階を実行することにより、図１１に示す第１差分配列データＤが得られる実施例を説明した。
【０１２７】
この実施例の場合、第１列目を基準列として、この基準列に属するセルを除いて、圧縮対象配列データＸの個々のセル内の数値を、左に隣接するセル内の数値との差分値に置き換える置換処理（横方向第１置換段階）を行い、図９に示す配列データを生成している。もちろん、基準列は必ずしも第１列目に設定する必要はない。たとえば、第８列目を基準列に設定し、この基準列に属するセルを除いて、圧縮対象配列データＸの個々のセル内の数値を、右に隣接するセル内の数値との差分値に置き換える置換処理を行うようにしてもよい。すなわち、第７列目のセルの数値を、第８列目のセルとの差分値に置き換え、第６列目のセルの数値を、第７列目のセルとの差分値に置き換え、... 、という処理を行えばよい。
【０１２８】
また、基準列は必ずしも端の列に設定する必要はなく、任意の列を基準列にすることも可能である。たとえば、第４列目を基準列として設定した場合は、第１〜３列目のセルについては、右に隣接するセル内の数値との差分値に置き換える置換処理を行い、第５〜８列目のセルについては、左に隣接するセル内の数値との差分値に置き換える置換処理を行えばよい。
【０１２９】
なお、§２−２で述べた実施例では、横方向第１置換段階後に得られた図９に示す配列データに対して、更に、図１０に示す縦方向第１置換段階を行うことにより、図１１に示す第１差分配列データＤを得ているが、この縦方向第１置換段階は必ずしも必須の処理ではなく、省略してもかまわない。省略した場合は、図９に示す配列データが第１差分配列データＤとして取り扱われることになる。もっとも、圧縮効率を高める上では、縦方向第１置換段階を実施するのが好ましい。
【０１３０】
図１０に示す縦方向第１置換段階は、一般論で述べると、図９に示す横方向第１置換段階を実行した後に、更に、基準列に属するセルのうち少なくとも所定の基準セルを除いて、個々のセル内の数値を、上もしくは下に隣接するセル内の数値との差分値に置換することにより、第１差分配列データＤを作成する処理と言うことができる。図１０に示す実施例は、第１行第１列目のセル（数値ｘ１１を収容したセル）を基準セルとして、この基準セルを除いた第１列目のセルについて、上に隣接するセル内の数値との差分値に置換する処理を行っているが、第８行第１列目のセル（数値ｘ８１を収容したセル）を基準セルとして、この基準セルを除いた第１列目のセルについて、下に隣接するセル内の数値との差分値に置換する処理を行ってもかまわない。もちろん、基準セルは、基準行の上端や下端のセルに限定されるものではなく、基準行内の任意のセルを基準セルに設定してもかまわない。
【０１３１】
こうして、第１差分演算段階によって、第１差分配列データＤが得られたら、続いて、コンピュータにより第２差分演算段階が実行される。この第２差分演算段階は、少なくとも所定の基準行に属するセルを除いて、第１差分配列データＤの個々のセル内の数値を、上もしくは下に隣接するセル内の数値との差分値に置き換える作業を含む置換処理を実行することにより、第２差分配列データＥを作成する処理である。§２−３では、図１１に示す第１差分配列データＤに対して第２差分演算段階を実行することにより、図１７に示す第２差分配列データＥが得られる実施例を説明した。
【０１３２】
この実施例の場合、第１行目を基準行として、この基準行に属するセルを除いて、第１差分配列データＤの個々のセル内の数値を、上に隣接するセル内の数値との差分値に置き換える置換処理（縦方向第２置換段階）を行い、図１５に示す配列データを生成している。なお、このとき、第２行第１列目のセル（図１５のＤ２１のセル）も置換処理の対象から除外するようにしている。もちろん、基準行は必ずしも第１行目に設定する必要はない。たとえば、図１０に示す縦方向第１置換段階において、第８行第１列目のセルを基準セルに設定した場合は、縦方向第２置換段階では、第８行目を基準行に設定し、この基準行に属するセルを除いて、第１差分配列データＤの個々のセル内の数値を、下に隣接するセル内の数値との差分値に置き換える置換処理を行うようにするのが好ましい。
【０１３３】
また、§２−３で述べた実施例では、縦方向第２置換段階後に得られた図１５に示す配列データに対して、更に、図１６に示す横方向第２置換段階を行うことにより、図１７に示す第２差分配列データＥを得ているが、この横方向第２置換段階は必ずしも必須の処理ではなく、省略してもかまわない。省略した場合は、図１５に示す配列データが第２差分配列データＥとして取り扱われることになる。もっとも、圧縮効率を高める上では、横方向第２置換段階を実施するのが好ましい。
【０１３４】
図１６に示す横方向第２置換段階は、一般論で述べると、図１５に示す縦方向第２置換段階を実行した後に、更に、基準行に属するセルのうち少なくとも所定の基準セルを除いて、個々のセル内の数値を、右もしくは左に隣接するセル内の数値との差分値に置換することにより、第２差分配列データＥを作成する処理と言うことができる。図１６に示す実施例は、第１行第１列目のセル（数値ｘ１１を収容したセル）を基準セルとして、この基準セルと、第１行第２列目のセル（差分値Ｄ１２を収容したセル）とを除いた第１行目のセルについて、左に隣接するセル内の数値との差分値に置換する処理を行っている。もちろん、第１行目の別なセルを基準セルに設定してもかまわない。
【０１３５】
以上、本発明に係る圧縮方法の基本概念を説明したが、本発明に係る伸張方法の基本概念は、圧縮方法で実行したプロセスと全く逆のプロセスを実行することにより、第２差分配列データＥから圧縮対象配列データＸを復元することにある。具体的には、コンピュータが、伸張対象となる圧縮配列データを入力するデータ入力段階と、第２差分演算段階で置換された値を置換前の値に復元する段階と、第１差分演算段階で置換された値を置換前の値に復元する段階と、を実行すればよい。
【０１３６】
＜３−２：  本発明に係る圧縮方法の基本手順＞
ここでは、本発明に係る圧縮方法の基本手順を、図２１の流れ図を参照しながら説明する。この流れ図の手順は、いずれもコンピュータによって実施される手順である。
【０１３７】
まず、ステップＳ１の元配列データ入力段階において、コンピュータが、元配列データを入力する処理が行われ、続くステップＳ２のブロック分割段階において、入力した元配列データをＫ個のブロックに分割する処理が行われる。たとえば、図２０に例示したように、複数μ行および複数ν列を有する元配列データが、複数Ｍ行および複数Ｎ列を有する配列データからなる複数Ｋ個のブロックに分割される（但し、μ＞Ｍ，ν＞Ｎ）。
【０１３８】
§２−４で述べたとおり、個々のブロックを構成する配列データのサイズ（Ｍ，Ｎの値）は、ブロックごとに異なっていてもかまわないが、実用上は、全ブロックのサイズが同一となるようにした方が、全ブロックに対して同一のハードウエアを用いて同一の処理を行うことができるので好ましい。μがＭの整数倍でない場合や、νがＮの整数倍でない場合は、ダミーとなるデータ（たとえば、隣接するセル内の数値と同一の数値）を追加して、Ｍ行Ｎ列の配列データとして取り扱うようにすればよい。
【０１３９】
こうして、Ｍ行Ｎ列の配列データからなるＫ個のブロックが得られたら、個々のブロックに対して、次のような手順で圧縮処理を行う。まず、ステップＳ３において、ブロックを示すパラメータｋを初期値１に設定し、第ｋ番目のブロックについて、ステップＳ４〜Ｓ８の手順を実行する。そして、ステップＳ９においてｋ＝Ｋと判断されるまで（すなわち、Ｋ個のブロックのすべてについての圧縮処理が完了するまで）、ステップＳ１０でｋを１ずつ更新して、ステップＳ４〜Ｓ８の圧縮処理を繰り返し実行する。
【０１４０】
具体的には、まず、ステップＳ４において、第ｋ番目のブロック内の配列データを、圧縮対象配列データＸとして抽出し、この抽出した配列データに対して、ステップＳ５の横方向第１置換段階、ステップＳ６の縦方向第１置換段階、ステップＳ７の縦方向第２置換段階、ステップＳ８の横方向第２置換段階が行われる。ここで、ステップＳ４の処理は、前述した基本概念におけるデータ入力段階に相当する処理であり、ステップＳ５，Ｓ６の処理は、前述した基本概念における第１差分演算段階に相当する処理であり、ステップＳ７，Ｓ８の処理は、前述した基本概念における第２差分演算段階に相当する処理である。これら各ステップの処理を具体的に説明すれば、次のとおりである。
【０１４１】
まず、ステップＳ４のデータ入力段階では、Ｍ行Ｎ列の行列状に並んだセル群について、第ｉ行第ｊ列目のセル内の数値ｘ（ｉ，ｊ）の集合体（但し、１≦ｉ≦Ｍ，１≦ｊ≦Ｎ）からなる圧縮対象配列データが入力される。具体的には、たとえば、図７に例示するような圧縮対象配列データＸを構成する個々の数値ｘ１１〜ｘ８８が配列として入力されることになる。
【０１４２】
続くステップＳ５の横方向第１置換段階では、Ｄ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ＋１）−ｘ（ｉ，ｊ）なる演算式に基づいて、圧縮対象配列データＸの第ｉ行第（ｊ＋１）列目のセル内の数値ｘ（ｉ，ｊ＋１）を差分値Ｄ（ｉ，ｊ＋１）に置換する処理を、ｉ＝１〜Ｍおよびｊ＝１〜Ｎ−１の各組み合わせについて実行する処理が行われる。具体的には、図９に示すような配列データが得られることになる。なお、差分値を求める演算式として、Ｄ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ＋１）−ｘ（ｉ，ｊ）なる演算式の代わりに、Ｄ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ）−ｘ（ｉ，ｊ＋１）なる演算式を用いてもかまわない（符号が反転するだけである）。
【０１４３】
次のステップＳ６の縦方向第１置換段階では、Ｄ（ｉ＋１，１）＝ｘ（ｉ＋１，１）−ｘ（ｉ，１）なる演算式に基づいて、横方向第１置換段階後の配列データの第（ｉ＋１）行第１列目のセル内の数値ｘ（ｉ＋１，１）を差分値Ｄ（ｉ＋１，１）に置換する処理を、ｉ＝１〜Ｍ−１について実行することにより、第１差分配列データＤを作成する処理が行われる。具体的には、図１０に示すような第１差分配列データＤが得られることになる。なお、差分値を求める演算式として、Ｄ（ｉ＋１，１）＝ｘ（ｉ＋１，１）−ｘ（ｉ，１）なる演算式の代わりに、Ｄ（ｉ＋１，１）＝ｘ（ｉ，１）−ｘ（ｉ＋１，１）なる演算式を用いてもかまわない（符号が反転するだけである）。
【０１４４】
続くステップＳ７の縦方向第２置換段階では、Ｅ（ｉ＋１，ｊ）＝Ｄ（ｉ＋１，ｊ）−Ｄ（ｉ，ｊ）なる演算式に基づいて、第１差分配列データＤの第（ｉ＋１）行第ｊ列目のセル内の数値Ｄ（ｉ＋１，ｊ）を差分値Ｅ（ｉ＋１，ｊ）に置換する処理を、ｉ＝１〜Ｍ−１およびｊ＝１〜Ｎの各組み合わせ（但し、ｉ＝１，ｊ＝１の組み合わせは除く）について実行する処理が行われる。具体的には、図１５に示すような配列データが得られることになる。なお、差分値を求める演算式として、Ｅ（ｉ＋１，ｊ）＝Ｄ（ｉ＋１，ｊ）−Ｄ（ｉ，ｊ）なる演算式の代わりに、Ｅ（ｉ＋１，ｊ）＝Ｄ（ｉ，ｊ）−Ｄ（ｉ＋１，ｊ）なる演算式を用いてもかまわない（符号が反転するだけである）。
【０１４５】
そしてステップＳ８の横方向第２置換段階では、Ｅ（１，ｊ＋１）＝Ｄ（１，ｊ＋１）−Ｄ（１，ｊ）なる演算式に基づいて、縦方向第２置換段階後の配列データの第１行第（ｊ＋１）列目のセル内の数値Ｄ（１，ｊ＋１）を差分値Ｅ（１，ｊ＋１）に置換する処理を、ｊ＝２〜Ｎ−１について実行することにより、第２差分配列データを作成する処理が行われる。具体的には、図１６に示すような第２差分配列データＥが得られることになる。なお、差分値を求める演算式として、Ｅ（１，ｊ＋１）＝Ｄ（１，ｊ＋１）−Ｄ（１，ｊ）なる演算式の代わりに、Ｅ（１，ｊ＋１）＝Ｄ（１，ｊ）−Ｄ（１，ｊ＋１）なる演算式を用いてもかまわない（符号が反転するだけである）。
【０１４６】
こうして、全Ｋ個のブロックについて、それぞれ図１６に示すような第２差分配列データＥが得られたら、ステップＳ９からステップＳ１１へと進み、ブロック間差分演算段階が行われる。これは、図２０を参照しながら§２−４で説明したとおり、各ブロック内の「ＤＣ」，「ＲＣ」，「ＢＣ」の３つの値に関してブロック間で差分をとり、差分値による置換処理を行い、第３差分配列データＦを得る処理である。すなわち、所定の基準ブロックを除いて、個々のブロックを構成する第２差分配列データＥの第１行第１列目のセル（「ＤＣ」のセル）、第１行第２列目のセル（「ＲＣ」のセル）、第２行第１列目のセル（「ＢＣ」のセル）の数値を、隣接するブロック内の対応位置のセルの数値との差分値に置換して、第３差分配列データＦを作成する処理が行われる。
【０１４７】
以上で、ステップＳ１で入力した元配列データに対する圧縮処理は完了である。最後に、ステップＳ１２のデータ符号化段階では、各ブロックについて得られた第２差分配列データＥもしくは第３差分配列データＦを、それぞれ所定のフォーマットで符号化する処理が行われる。具体的な符号化処理の内容は、§４で詳述する。
【０１４８】
なお、入力した元配列データに対してブロック分割を行わない場合は、ステップＳ２およびステップＳ１１の処理は不要であり、ステップＳ４〜Ｓ８の処理を１回だけ実行し、ステップＳ１２のデータ符号化段階を実行すれば足りる。
【０１４９】
＜３−３：  本発明に係る伸張方法の基本手順＞
続いて、本発明に係る伸張方法の基本手順を、図２２の流れ図を参照しながら説明する。この流れ図の手順も、コンピュータによって実施される手順である。ここで述べる伸張方法の基本は、§３−２で説明した圧縮方法で実行したプロセスと全く逆のプロセスを実行することにより、圧縮された配列データからもとの配列データを復元することにある。したがって、図２２の流れ図に示す各ステップは、図２１の流れ図に示す各ステップに対応する逆のプロセスになっている。
【０１５０】
まず、ステップＳ２１の符号化データ入力段階において、コンピュータが、符号化データを入力する処理が行われる。すなわち、図２１のステップＳ１２で符号化されたデータがコンピュータに取り込まれることになる。
【０１５１】
続くステップＳ２２のブロック復元演算段階では、符号化データとして取り込まれた各ブロック内の第３差分配列データＦについて、ブロック間差分演算段階（図２１のステップＳ１１）において置換されていた差分値を元の数値に復元して第２差分配列データＥを得る処理が行われる。すなわち、各ブロック内の「ＤＣ」，「ＲＣ」，「ＢＣ」の３つの値が、差分値から本来の値に復元されることになる。
【０１５２】
次に、第２差分配列データＥを構成する個々のブロックに対して、次のような手順で伸張処理を行う。まず、ステップＳ２３において、ブロックを示すパラメータｋを初期値１に設定し、第ｋ番目のブロックについて、ステップＳ２４〜Ｓ２８の手順を実行する。そして、ステップＳ２９においてｋ＝Ｋと判断されるまで（すなわち、Ｋ個のブロックのすべてについての伸張処理が完了するまで）、ステップＳ３０でｋを１ずつ更新して、ステップＳ２４〜Ｓ２８の伸張処理を繰り返し実行する。
【０１５３】
具体的には、まず、ステップＳ２４において、第ｋ番目のブロック内の圧縮配列データを抽出し、この抽出した配列データに対して、ステップＳ２５の横方向第２置換復元段階、ステップＳ２６の縦方向第２置換復元段階、ステップＳ２７の縦方向第１置換復元段階、ステップＳ２８の横方向第１置換復元段階が行われる。
【０１５４】
ここで、ステップＳ２４の処理は、前述した基本概念におけるデータ入力段階に相当する処理である。一方、ステップＳ２５，Ｓ２６の処理は、前述した基本概念における第２差分復元段階に相当する処理であり、個々のブロックの第２差分配列データＥについて、横方向第２置換復元段階および縦方向第２置換復元段階を実行して、第１差分配列データＤを得る処理である。また、ステップＳ２７，Ｓ２８の処理は、前述した基本概念における第１差分復元段階に相当する処理であり、個々のブロックの第１差分配列データＤについて、縦方向第１置換復元段階および横方向第１置換復元段階を実行して、もとの圧縮対象配列データＸを得る処理である。これら各ステップの処理を具体的に説明すれば、次のとおりである。
【０１５５】
まず、ステップＳ２４のデータ入力段階では、第ｋ番目のブロック内の圧縮配列データ、すなわち、図１７に示すような第２差分配列データＥが伸張対象となる配列データとして抽出される。
【０１５６】
そして、ステップＳ２５の横方向第２置換復元段階では、第２差分配列データＥについて、横方向第２置換段階（図２１のステップＳ８）において置換されていた差分値Ｅを元の数値Ｄに復元する処理が行われる。たとえば、図１６に示す例の場合、置換処理と逆のプロセスを実行することにより、差分値Ｅ１３〜Ｅ１８が差分値Ｄ１３〜Ｄ１８に戻される。
【０１５７】
続いて、ステップＳ２６の縦方向第２置換復元段階では、ステップＳ２５の横方向第２置換復元段階で復元されたデータについて、縦方向第２置換段階（図２１のステップＳ７）において置換されていた差分値Ｅを元の数値Ｄに復元して第１差分配列データＤを得る処理が行われる。たとえば、図１５に示す例の場合、置換処理と逆のプロセスを実行することにより、差分値Ｅ２２〜Ｅ８８が差分値Ｄ２２〜Ｄ８８に戻される。
【０１５８】
次に、ステップＳ２７の縦方向第１置換復元段階では、ステップＳ２６の処理で得られた第１差分配列データＤについて、縦方向第１置換段階（図２１のステップＳ６）において置換されていた差分値Ｄを元の数値ｘに復元する処理が行われる。たとえば、図１０に示す例の場合、置換処理と逆のプロセスを実行することにより、差分値Ｄ２１，Ｄ３１，Ｄ４１，... ，Ｄ８１がもとの数値ｘ２１，ｘ３１，ｘ４１，... ，ｘ８１に戻される。
【０１５９】
続くステップＳ２８の横方向第１置換復元段階では、ステップＳ２７の縦方向第１置換復元段階で復元されたデータについて、横方向第１置換段階（図２１のステップＳ５）において置換されていた差分値Ｄを元の数値ｘに復元して圧縮対象配列データＸを得る処理が行われる。たとえば、図９に示す例の場合、置換処理と逆のプロセスを実行することにより、差分値Ｄ１２〜Ｄ８８がもとの数値ｘ１２〜ｘ８８に戻され、図７に示すもとの圧縮対象配列データＸが復元される。
【０１６０】
こうして、全Ｋ個のブロックについて、それぞれ図７に示すようなもとの圧縮対象配列データＸが復元できたら、ステップＳ２９からステップＳ３１へと進み、ブロック合成段階が行われる。これは、図２１のステップＳ２のブロック分割段階と逆のプロセスであり、個々のブロックの圧縮対象配列データＸを合成して元配列データを得るプロセスということになる。こうして、元配列データが復元できたら、ステップＳ３２における元配列データ出力段階が実行され、復元された元配列データが外部に出力される。
【０１６１】
なお、圧縮処理の段階で、元配列データに対してブロック分割が行われていない場合は、図２２に示すステップＳ２２およびステップＳ３１の処理は不要であり、ステップＳ２４〜Ｓ２８の処理を１回だけ実行すれば足りる。
【０１６２】
＜＜＜  §４．  圧縮データの実用的なフォーマット  ＞＞＞
図２１の流れ図の最後のステップＳ１２は、個々のブロックを構成する配列データを符号化する段階であり、図２０に示すようなブロック単位の配列データを、所定の規則で符号化してビット列で表現する処理が行われる。符号化によるデータ圧縮の効率を高めるためには、無駄なビットを省くことができる可変長符号方式を用いるのが好ましい。以下、本発明に適した可変長符号方式の具体的な符号化方法の一例を説明する。
【０１６３】
ステップＳ１２における符号化の対象となる配列データは、図１９に示すような第２差分配列データＥ（基準ブロックの場合）、もしくはこれに対してステップＳ１１におけるブロック間差分演算を施した第３差分配列データＦ（基準ブロック以外のブロックの場合）ということになる。第２差分配列データＥは、図１９に示すように、「ＤＣ」，「ＲＣ」，「ＢＣ」という３つの特殊値と、それ以外の一般値によって構成されている。
【０１６４】
図１８の実例を見ればわかるように、これら３つの特殊値は、他の一般セル値に比べて比較的大きな値をとり、特に、ＤＣ値は、格段に大きな値をとるケースが多い。そこで、実用上は、「ＤＣ値」，「ＲＣ値およびＢＣ値」，「一般セル値」という３種類の値について、それぞれ最適な別個独立したフォーマットを採用して符号化を行うのが好ましい。以下に述べるフォーマットは、このような観点に基づいて設計した、本発明に適した圧縮データのフォーマットの一例である。
【０１６５】
まず、図２３に、ＤＣ値を記述するためのフォーマットの一例を示す。図には、図１８の実例におけるＤＣ値、すなわち、「＋２２９２２」なる具体的な数値についての記述例が示されている。このフォーマットでは、ＤＣ値は、ａ，ｂ，ｃの３つの区画のデータによって記述される。ここで、区画ａは固定長４ビットのデータ、区画ｂは可変長の任意ビットのデータ、区画ｃは固定長１ビットのデータによって構成されている。区画ａのデータは、可変長の区画ｂのビット長を示す役割を担い、「区画ｂのビット長−１」なるデータになる。区画ｂには、ＤＣ値の絶対値が収容され、区画ｃには、ＤＣ値の符号（０なら正、１なら負）が収容される。
【０１６６】
図示の例の場合、ＤＣ値の絶対値「２２９２２」を２進表記すると、「１０１１００１１０００１０１０」なる１５ビットのビット列が必要になるので、区画ｂには１５ビットのビット長が確保される。一方、区画ａには、区画ｂのビット長１５から１を減じた１０進数の「１４」を示すビット「１１１０」が収容され、区画ｃには、符号が正であることを示すビット「０」が収容される。区画ｂが可変長ビットであるため、ＤＣ値の絶対値にかかわらず、効率良い符号化が可能になる。
【０１６７】
続いて、図２４に、ＲＣ値を記述するためのフォーマットの一例を示す。図には、図１８の実例におけるＲＣ値、すなわち、「＋２９」なる具体的な数値についての記述例が示されている。このフォーマットでは、ＲＣ値は、ｄ，ｅ，ｆ，ｇの４つの区画のデータによって記述される。ここで、区画ｄは固定長１ビットのデータ、区画ｅは５ビットまたは２ビットのいずれかの選択固定長のデータ、区画ｆは可変長の任意ビットのデータ、区画ｇは固定長１ビットのデータによって構成されている。区画ｄの１ビットのデータは、区画ｅの選択固定長がいずれの選択状態にあるかを示す役割を担い、ビット「１」の場合は、区画ｅが５ビットの固定長であることを示し、ビット「０」の場合は、区画ｅが２ビットの固定長であることを示す。区画ｅのデータは、可変長の区画ｆのビット長を示す役割を担い、「区画ｆのビット長−１」なるデータになる。区画ｆには、ＲＣ値の絶対値が収容され、区画ｇには、ＲＣ値の符号（０なら正、１なら負）が収容される。
【０１６８】
図示の例の場合、ＲＣ値の絶対値「２９」を２進表記すると、「１１１０１」なる５ビットのビット列が必要になるので、区画ｆには５ビットのビット長が確保される。一方、区画ｅには、区画ｆのビット長５から１を減じた１０進数の「４」を示すビット「１００」を収容することになるが、区画ｅは、５ビットか２ビットかのいずれかを選択する選択固定長であるため、この場合は、ビット「１００」を収容可能な５ビット固定長を選択することになり、「００１００」なる５ビットのデータが区画ｅに収容される。そして、区画ｄには、区画ｅの選択固定長として５ビットを選択したことを示すビット「１」が収容され、区画ｇには、符号が正であることを示すビット「０」が収容される。
【０１６９】
このように、区画ｆを可変長ビットとし、区画ｅを選択固定長にしたため、ＲＣ値の絶対値にかかわらず、効率良い符号化が可能になる。以上、ＲＣ値の記述フォーマットを説明したが、ＢＣ値を記述する場合も同じフォーマットを用いればよい。
【０１７０】
最後に、図２５に、一般セル値（ＤＣ値，ＲＣ値，ＢＣ値以外のセル値）を記述するためのフォーマットの一例を示す。図には、図１８の実例における第１行第３〜８列目の６つのセルに収容された値、すなわち、「０」，「−１」，「２」，「−２」，「１」，「−１」という具体的な数値についての記述例が示されている。このフォーマットでは、これらの数値を絶対値と符号とに分け、絶対値をそれぞれ２進表記して羅列した２進ビット列「０００１１０１００１０１」を作成する。このとき、個々の絶対値の２進表記に必要な最長ビット長に合わせたビット表記を行うようにする。
【０１７１】
この例の場合、絶対値の最大値は「２」であり、２ビットのデータ「１０」によって表記することが可能なので、６つの数値の絶対値をいずれも２ビットのデータで表記し、これを羅列することにより２進ビット列「０００１１０１００１０１」が作成されることになる。
【０１７２】
一方、個々の数値の符号については、図示のような符号ビット列を作成する。ここで、０は正、１は負を示している。但し、絶対値がゼロの数値については、符号を定義する必要はないので、符号ビットは作成しない。図示の例の場合、６つの数値の先頭はゼロであり、符号を定義する必要はないので、符号ビット列の先頭の升には×印が記されている。
【０１７３】
図２５の下段には、具体的なフォーマット例が示されている。このフォーマット例では、「０」，「−１」，「２」，「−２」，「１」，「−１」という６つの数値が、ｈ，ｉ，ｊという３つの区画のデータによって記述されている。ここで、区画ｈは可変長の指標ビット列を構成するデータ、区画ｉは可変長の２進ビット列データ、区画ｊは可変長の符号ビット列データである。区画ｉに収容される２進ビット列データは、図２５の上段に示す絶対値を示す２進ビット列であり、図示の例の場合、６つの数値の絶対値を示す「０００１１０１００１０１」なるビット列が収容されている。
【０１７４】
一方、区画ｊに収容される符号ビット列データは、図２５の上段に示す符号ビット列のデータであり、×印の升（絶対値がゼロの数値に対応する升）を除いて、符号を示す０または１を羅列したビット列になる。図示の例の場合、６つの数値のうち、先頭の数値はゼロであるため符号ビット列の升は×印となっており、残りの５つの数値の符号を示すビット列「１０１０１」が区画ｊに収容されている。区画ｉに収容されているデータに基づいて、６つの数値のうちの先頭がゼロであることが認識できるので、区画ｊに収容されている５つの符号ビットが、先頭を除く５つの数値の符号を示していることが把握できる。
【０１７５】
区画ｈの指標ビット列は、区画ｉに羅列されたビット列のビット単位を示す役割を担う。たとえば、図示の例の場合、区画ｈの指標ビット列は「０１０００」となっているが、これは区画ｉの２進ビット列を２ビット単位で区切って把握すべきことを示している。具体的には、区画ｉの２進ビット列「０００１１０１００１０１」を、２ビット単位で区切ると、「００」「０１」「１０」「１０」「０１」「０１」となり、６つの１０進数「０」「１」「２」「２」「１」「１」を認識することができる。これに、区画ｊの符号ビット列に基づいて符号を付加すれば、「０」「−１」「２」「−２」「１」「−１」なるもとのセル値を得ることができる。
【０１７６】
図示の例の場合、もとのセル値の絶対値は、いずれも２ビットで表記することが可能であるため、区画ｉには、２ビット単位で６つの数値の絶対値を羅列したが、セル値の絶対値は、必ずしも２ビットで表記できるとは限らない。たとえば、もとのセル値が「０」「−１」「４」「−２」「１」「−１」であった場合、絶対値「４」の２進表記「１００」には３ビット必要になるので、区画ｉは３ビット単位で各絶対値を表記して羅列する必要がある。この場合、区画ｈの指標ビット列には、「０１００１」なるビット列が収容されることになる。逆に、もとのセル値が「０」「１」「−１」のいずれかであった場合、その絶対値は「０」または「１」になるので、区画ｉは１ビット単位のビット列で表現できる。この場合、区画ｈの指標ビット列には、「００」なるビット列を収容し、区画ｉが１ビット単位のビット列であることを示すようにする。
【０１７７】
すなわち、区画ｈの指標ビット列は、「００」であった場合には区画ｉが１ビット単位のビット列であることを示し、「０１０００」であった場合には区画ｉが２ビット単位のビット列であることを示し、「０１００１」であった場合には区画ｉが３ビット単位のビット列であることを示し、「０１０１０」であった場合には区画ｉが４ビット単位のビット列であることを示し、「０１０１１」であった場合には区画ｉが５ビット単位のビット列であることを示している。
【０１７８】
また、特殊なケースとして、区画ｈの指標ビット列が「０１１０」であった場合には、セル値がすべてゼロであることを示しており、この場合には、区画ｉ，ｊは不要になる。更に、稀なケースとして、区画ｉが６ビット単位以上のビット列である場合には、区画ｈの指標ビット列を「０１１１ｚｚｚｚｚｚｚｚ」なる形式の１２ビットのビット列によって構成し（ｚは０または１の１ビットデータ）、「ｚｚｚｚｚｚｚｚ」の部分によって具体的なビット単位を示すようにする。たとえば、「ｚｚｚｚｚｚｚｚ」の部分が「００００００００」なら６ビット単位、「０００００００１」なら７ビット単位、「００００００１０」なら８ビット単位という具合である。
【０１７９】
このように、区画ｈの指標ビット列は可変長になるが、先頭の２ビットが「００」であれば、全ビット長は必ず２ビットになり、先頭の３ビットが「０１０」であれば、全ビット長は必ず５ビットになり、先頭の４ビットが「０１１０」であれば、全ビット長は必ず４ビットになり、先頭の４ビットが「０１１１」であれば、全ビット長は必ず１２ビットになるため、混同が生じることはない。
【０１８０】
以上、基本ブロック内の圧縮データ（第２差分配列データＥ）について具体的なデータフォーマットの一例を示したが、他のブロック内の圧縮データ（「ＤＣ」，「ＲＣ」，「ＢＣ」についてブロック間差分演算を施した第３差分配列データＦ）についても、ほぼ同様のフォーマットを利用することができる。
【０１８１】
図１９に示すとおり、本発明によって圧縮された第２差分配列データＥや、これに対してブロック間差分演算を施した第３差分配列データＦは、１行目の配列データ、２行目の配列データ、３行目以降の配列データがそれぞれ異なる特性を有している。すなわち、１行目の配列データには、ＤＣ値およびＲＣ値や、そのブロック間置換値が含まれ、２行目の配列データには、ＢＣ値やそのブロック間置換値が含まれ、３行目以降の配列データには、一般セル値のみが含まれている。
【０１８２】
したがって、本発明において、第２差分配列データＥもしくは第３差分配列データＦを符号化する際には、１行目の配列データ、２行目の配列データ、３行目以降の配列データについて、それぞれ異なるフォーマットで符号化するデータ符号化方式を採用するのが好ましい。
【０１８３】
より具体的には、１行目の配列データについては、１列目のセル内の数値と、２列目のセル内の数値と、３列目以降のセル内の数値と、について、それぞれ異なるフォーマットで符号化し、２行目の配列データについては、１列目のセル内の数値と、２列目以降のセル内の数値と、について、それぞれ異なるフォーマットで符号化し、３行目以降の配列データについては、各セル内の数値を同一のフォーマットで符号化するようにすればよい。
【０１８４】
＜＜＜  §５．  画像変換方法への適用  ＞＞＞
既に§１で述べたように、本発明は、魚眼レンズが組み込まれた全方位カメラによって撮影された歪曲円形画像Ａを正則矩形画像Ｂに変換したり、プロジェクタによる投影用原画像Ａを台形補正画像Ｂに変換したりする幾何学的な画像変換処理を行う際に、変換処理に用いる座標変換テーブルを圧縮するのに適したデータ圧縮方法およびこれを伸張するデータ伸張方法を提供するものである。そこで、以下、本発明に係るデータ圧縮／伸張方法を画像変換方法に適用した例を述べる。
【０１８５】
この画像変換方法は、図１や図２に示すように、ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像Ａを、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる変換画像Ｂに変換する方法であり、図２６の流れ図に示す各段階によって構成される。これらの段階には、これまで述べてきた配列データの圧縮方法や配列データの伸張方法の手順も含まれている。
【０１８６】
なお、この図２６の流れ図に示す各段階の処理は、いずれもコンピュータによって実行され、コンピュータ用のプログラムとして記述されることになる。もちろん、これらのプログラムを組み込んだコンピュータとして機能する集積回路を用意すれば、図２６の手順を実行する機能をもったハードウエア装置を提供することも可能である。
【０１８７】
まず、ステップＳ４１では、原画像Ａと変換画像Ｂとの間の幾何学的な関係に基づいて、変換画像Ｂを構成する各画素について、原画像Ａ上の対応点の座標値（ｘ，ｙ）を求める対応点演算段階が実行される。
【０１８８】
§１で述べたとおり、変換画像Ｂ上の任意の点Ｂ（ｕ，ｖ）の座標値ｕ，ｖと、原画像Ａ上の対応点Ａ（ｘ，ｙ）の座標値ｘ，ｙとの関係は、幾何学変換関数Ｇによって一義的に定められ、この幾何学変換関数Ｇには、両画像Ａ，Ｂ間の幾何学的な位置関係を示すパラメータが含まれている。ステップＳ４１の対応点演算段階は、この幾何学変換関数Ｇに基づいて、変換画像Ｂを構成する個々の画素の代表点Ｂ（ｕ，ｖ）（たとえば、画素の中心点）の座標値ｕ，ｖに対して、それぞれ原画像Ａ上の対応点Ａ（ｘ，ｙ）の座標値ｘ，ｙを算出する処理ということになる。
【０１８９】
続くステップＳ４２では、変換画像Ｂを構成する各画素について、ステップＳ４１の対応点演算段階で求められた座標値ｘを並べたＸ座標変換テーブルＴｘと、座標値ｙを並べたＹ座標変換テーブルＴｙと、を作成し、これをメモリに格納する変換テーブル格納段階が実行される。但し、このとき、Ｘ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙを構成する配列データに対して、§３で述べた本発明に係る圧縮方法を利用した圧縮処理を施し、各テーブルＴｘ，Ｔｙを圧縮した状態でメモリに格納するようにする。
【０１９０】
Ｘ座標変換テーブルＴｘは、たとえば、図７に示すような配列データＸであるが、圧縮処理により図１７に示すような第２差分配列データＥの形に変換され（ブロック分割を行った場合は、更に、第３差分配列データＦの形に変換され）、図２３〜図２５に例示したようなフォーマットでメモリに格納されることになる。図７に示す圧縮対象配列データＸ（Ｘ座標変換テーブルＴｘ）は、変換画像Ｂ上の個々の画素について、対応点Ａ（ｘ，ｙ）の座標値ｘを配列したものであるため、上下左右に隣接するセル内の数値は比較的近似した値になるという特徴を有している。本発明に係る配列データの圧縮方法では、横方向の差分値と縦方向の差分値との双方がとられるため、圧縮後に得られる第２差分配列データＥの各セルの数値の桁数は大幅に減少し、極めて高い圧縮効果が得られる。このため、Ｘ座標変換テーブルＴｘを格納するためのメモリの容量を大幅に低減できる。Ｙ座標変換テーブルＴｙについても同様である。
【０１９１】
以上述べたステップＳ４１，Ｓ４２の処理は、いわば画像変換処理の準備段階というべき処理であり、変換に用いるＸ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙを、圧縮した状態でメモリに準備する処理ということになる。続いて実行されるステップＳ４３以降の処理は、これらのテーブルＴｘ，Ｔｙを利用して、実際に原画像Ａを変換画像Ｂに変換する処理である。
【０１９２】
まず、ステップＳ４３では、原画像を構成する各画素の画素値を入力する原画像入力段階が行われる。たとえば、図１(a) に示す歪曲円形画像Ａや図２(a) に示す投影用原画像Ａが原画像としてコンピュータに入力されることになる。これらの原画像Ａは、ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合から構成され、コンピュータに入力される原画像のデータは、これら個々の画素についての画素値を示すデータということになる。
【０１９３】
続くステップＳ４４では、変換画像Ｂを構成する各画素について、メモリ上に準備されたＸ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙを参照して、原画像Ａ上の対応点の座標値（ｘ，ｙ）を認識する対応座標認識段階が実行される。前述したとおり、Ｘ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙは、変換画像Ｂを構成する個々の画素に対応するセル内に座標値ｘおよび座標値ｙを格納したものであるから、ステップＳ４４の処理は、単に、これらのテーブルＴｘ，Ｔｙを参照して、対応点の座標値（ｘ，ｙ）を取得する処理になる。
【０１９４】
但し、テーブルＴｘ，Ｔｙは、メモリ上に圧縮された状態で格納されているため、この対応座標認識段階を実行する際には、§３で述べた本発明に係る配列データ伸張方法を利用して各テーブルＴｘ，Ｔｙを伸張し、伸張した各テーブルＴｘ，Ｔｙを参照することにより、対応点の座標値（ｘ，ｙ）を取得する処理が行われることになる。
【０１９５】
そして、ステップＳ４５では、ステップＳ４４で認識した座標値（ｘ，ｙ）の近傍に位置する原画像Ａ上の画素の画素値に基づいて、変換画像Ｂを構成する画素の画素値を決定する画素値決定段階が実行される。たとえば、図３に示す例の場合、変換画像Ｂ上の画素Ｐ（ｕ，ｖ）の画素値は、原画像Ａ上の対応点Ａ（ｘ，ｙ）の近傍に位置する参照画素Ｑ１〜Ｑ４の画素値に基づいて決定されることになる。参照画素Ｑ１〜Ｑ４の画素値に基づいて画素Ｐ（ｕ，ｖ）の画素値を決定する方法としては、距離に応じた加重平均をとる方法や、スプライン補間法などの高度な補間を行う方法など、公知の補間方法を採用すればよい。
【０１９６】
こうして、ステップＳ４５において、変換画像Ｂを構成する全画素についての画素値が決定されれば、原画像Ａから変換画像Ｂへの画像変換処理は完了である。そこで、画像変換の変換条件が同一であれば、ステップＳ４６からステップＳ４３へと戻り、新たな原画像を入力し、これを変換する処理が繰り返されることになる。一方、変換条件に変更があった場合には、ステップＳ４６からステップＳ４１へと戻り、新たな変換テーブルＴｘ，Ｔｙを準備する段階からの処理が実行される。
【０１９７】
たとえば、図１に例示した全方位カメラを定点監視カメラとして利用する場合、歪曲円形画像Ａに対する切出位置、切出向き、切出倍率といったパラメータが固定されている限り、原画像Ａから変換画像Ｂへの変換条件は同一であり、変換に利用される幾何学変換関数Ｇは一定である。したがって、全方位カメラによる撮影画像を構成する個々のフレーム画像（原画像Ａ）に対して、ステップＳ４２で準備した変換テーブルＴｘ，Ｔｙを繰り返し利用することができる。このような場合は、ステップＳ４６からステップＳ４３へと戻り、個々のフレーム画像に対して、同一の変換テーブルＴｘ，Ｔｙを利用した画像変換処理を行えばよい。
【０１９８】
一方、歪曲円形画像Ａに対する切出位置、切出向き、切出倍率といったパラメータを変更した場合は、変換に利用される幾何学変換関数Ｇが変わるため（実際には、関数Ｇに含まれるパラメータ値が変わることになる）、新たな変換テーブルＴｘ，Ｔｙを用意する必要が生じる。このような場合は、ステップＳ４６からステップＳ４１へと戻り、新たな変換テーブルＴｘ，Ｔｙを準備する段階から処理を繰り返すようにすればよい。
【０１９９】
図２に示すプロジェクタの例も同様である。すなわち、プロジェクタおよびスクリーンを所定位置に設定して投影条件を固定した状態では、変換に利用される幾何学変換関数Ｇは一定になるので、個々のフレーム画像に対して、同一の変換テーブルＴｘ，Ｔｙを用いてステップＳ４３〜Ｓ４５の処理を繰り返して変換画像を得るようにすればよい。これに対して、プロジェクタとスクリーンとの相対位置を変更したり、投影倍率を変えたりした場合には、新たな変換テーブルＴｘ，Ｔｙを用意する必要が生じる。このような場合は、ステップＳ４６からステップＳ４１へと戻り、新たな変換テーブルＴｘ，Ｔｙを準備する段階から処理を繰り返すようにすればよい。
【０２００】
なお、変換テーブルＴｘ，Ｔｙを元配列データとして、図２０に示すようなブロック分割の手法を採用する場合には、ステップＳ４２の変換テーブル格納段階において、各変換テーブルＴｘ，Ｔｙを、§２−４で説明した方法によって複数Ｋ個のブロックに分割してから圧縮を行うようにすればよい。各変換テーブルＴｘ，Ｔｙは、ブロック単位で圧縮された状態でメモリに格納されることになる。
【０２０１】
もちろん、この場合は、ステップＳ４４の対応座標認識段階において、ブロック単位で圧縮されている各変換テーブルＴｘ，Ｔｙを伸張して、テーブル内の必要なセルを参照する必要がある。したがって、必要に応じて、ブロック間差分演算段階で置換されたブロック間の差分値を元に戻す処理（図２２のステップＳ２２：ブロック復元演算段階）を行う必要がある。
【０２０２】
なお、ステップＳ４４の対応座標認識段階では、各変換テーブルＴｘ，Ｔｙの必要なセル内の数値を参照することができればよいので、全ブロックの配列データを一括して伸張する必要はなく、参照に必要なブロックごとに伸張処理を行い、必要なブロックごとに伸張した変換テーブルＴｘ，Ｔｙを参照することにより、対応点の座標値（ｘ，ｙ）を認識すれば足りる。別言すれば、ステップＳ４４の対応座標認識段階では、本来の変換テーブルＴｘやＴｙのテーブル全体を復元する必要はないので、図２２のステップＳ３１のブロック合成段階は実行する必要はない。
【０２０３】
＜＜＜  §６．  圧縮装置／伸張装置／画像変換装置  ＞＞＞
これまで、本発明を、配列データの圧縮方法および配列データの伸張方法、ならびにこれらの方法を利用した画像変換方法として捉え、その処理手順を詳細に説明してきた。そこで、§６では、本発明を、配列データの圧縮装置および配列データの伸張装置、ならびにこれらの装置を組み込んだ画像変換装置として捉え、これら各装置の構成を説明する。実用上は、これらの各装置は、コンピュータに専用のプログラムを組み込むことにより構成することができる。
【０２０４】
＜６−１：  配列データの圧縮装置＞
図２７は、本発明に係る配列データの圧縮装置２００の具体的な構成例を示すブロック図である。この圧縮装置２００は、入力した元配列データＲを圧縮して、圧縮配列データＷとして出力する機能を有しており、図示のとおり、元配列データ入力部２１０、ブロック分割部２２０、圧縮装置本体部２３０、ブロック間差分演算部２４０、圧縮配列データ出力部２５０によって構成される。
【０２０５】
元配列データ入力部２１０は、複数μ行および複数ν列を有する元配列データＲを入力して格納する機能をもった構成要素であり、メモリをはじめとする様々な記憶装置によって構成することができる。元配列データＲの実体は、μ行ν列からなる行列を構成するデータの集合体である。
【０２０６】
ブロック分割部２２０は、元配列データ入力部２１０が入力した元配列データＲを、それぞれが複数Ｍ行および複数Ｎ列を有する配列データ（但し、μ＞Ｍ，ν＞Ｎ）からなる複数Ｋ個のブロックに分割する処理を行う。μがＭの整数倍でない場合や、νがＮの整数倍でない場合は、一部のブロックの配列データのサイズをＭ行Ｎ列よりも小さくするようにしてもよいが、実用上は、ダミーとなるデータ（たとえば、隣接するセル内の数値と同一の数値）を追加して、Ｍ行Ｎ列の配列データとして取り扱うようにするのが好ましい。分割された個々のブロックを構成するＭ行Ｎ列の配列データは、順次、圧縮装置本体部２３０へと引き渡される。
【０２０７】
圧縮装置本体部２３０は、こうして引き渡された個々のブロック内のＭ行Ｎ列の配列データに対して圧縮処理を行う構成要素であり、図示のとおり、作業用メモリ２３１、横方向第１置換部２３２、縦方向第１置換部２３３、縦方向第２置換部２３４、横方向第２置換部２３５を有している。
【０２０８】
作業用メモリ２３１は、ＲＡＭなどの書換可能なメモリによって構成され、個々のブロックのＭ行Ｎ列の行列状に並んだセル群について、第ｉ行第ｊ列目のセル内の数値ｘ（ｉ，ｊ）の集合体（但し、１≦ｉ≦Ｍ，１≦ｊ≦Ｎ）からなる圧縮対象配列データＸ（たとえば、図７に示すような配列データ）を格納する役割を果たす。
【０２０９】
なお、この作業用メモリ２３１上に格納された配列データの各セル内の数値は、各置換部２３２〜２３５による置換処理の対象になる。したがって、実用上は、作業用メモリ２３１内には、置換前のＭ行Ｎ列の配列データを格納する第１の領域と、置換後のＭ行Ｎ列の配列データを格納する第２の領域と、の双方を設けておき、各置換部２３２〜２３５が、第１の領域から読み出した置換前の数値を参照しながら、置換後の数値を第２の領域に書き込む処理ができるようにしておくのが好ましい。あるいは、置換後のＭ行Ｎ列の配列データを格納する領域と、後の演算に必要な一部のセル内の置換前の数値を一時的に格納するレジスタ領域と、を設けるようにしてもよい。
【０２１０】
横方向第１置換部２３２は、作業用メモリ２３１に格納されている圧縮対象配列データＸの第ｉ行第（ｊ＋１）列目のセル内の数値ｘ（ｉ，ｊ＋１）を差分値Ｄ（ｉ，ｊ＋１）に置換する置換処理を、ｉ＝１〜Ｍおよびｊ＝１〜Ｎ−１の各組み合わせについて実行する構成要素である。ここで、差分値Ｄ（ｉ，ｊ＋１）は、Ｄ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ＋１）−ｘ（ｉ，ｊ）なる演算式もしくはＤ（ｉ，ｊ＋１）＝ｘ（ｉ，ｊ）−ｘ（ｉ，ｊ＋１）なる演算式に基づいて求められる。図７に例示する圧縮対象配列データＸに対して、横方向第１置換部２３２による置換処理が行われると、図９に示すような配列データが得られることになる。
【０２１１】
縦方向第１置換部２３３は、作業用メモリ２３１に格納されている、横方向第１置換部２３２による置換処理後の配列データの第（ｉ＋１）行第１列目のセル内の数値ｘ（ｉ＋１，１）を差分値Ｄ（ｉ＋１，１）に置換する置換処理を、ｉ＝１〜Ｍ−１について実行することにより、第１差分配列データＤを作成する構成要素である。ここで、差分値Ｄ（ｉ＋１，１）は、Ｄ（ｉ＋１，１）＝ｘ（ｉ＋１，１）−ｘ（ｉ，１）なる演算式もしくはＤ（ｉ＋１，１）＝ｘ（ｉ，１）−ｘ（ｉ＋１，１）なる演算式に基づいて求められる。図９に例示する配列データに対して、縦方向第１置換部２３３による置換処理が行われると、図１０に示すような第１差分配列データＤが得られることになる。
【０２１２】
縦方向第２置換部２３４は、作業用メモリ２３１に格納されている、縦方向第１置換部２３３による置換処理後に得られた第１差分配列データＤの第（ｉ＋１）行第ｊ列目のセル内の数値Ｄ（ｉ＋１，ｊ）を差分値Ｅ（ｉ＋１，ｊ）に置換する置換処理を、ｉ＝１〜Ｍ−１およびｊ＝１〜Ｎの各組み合わせ（但し、ｉ＝１，ｊ＝１の組み合わせは除く）について実行する構成要素である。ここで、差分値Ｅ（ｉ＋１，ｊ）は、Ｅ（ｉ＋１，ｊ）＝Ｄ（ｉ＋１，ｊ）−Ｄ（ｉ，ｊ）なる演算式もしくはＥ（ｉ＋１，ｊ）＝Ｄ（ｉ，ｊ）−Ｄ（ｉ＋１，ｊ）なる演算式に基づいて求められる。図１１に例示する第１差分配列データＤに対して、縦方向第２置換部２３４による置換処理が行われると、図１５に示すような配列データが得られることになる。
【０２１３】
縦方向第２置換部２３５は、作業用メモリ２３１に格納されている、縦方向第２置換部２３４による置換処理後の配列データの第１行第（ｊ＋１）列目のセル内の数値Ｄ（１，ｊ＋１）を差分値Ｅ（１，ｊ＋１）に置換する置換処理を、ｊ＝２〜Ｎ−１について実行することにより、第２差分配列データを作成する構成要素である。ここで、差分値Ｅ（１，ｊ＋１）は、Ｅ（１，ｊ＋１）＝Ｄ（１，ｊ＋１）−Ｄ（１，ｊ）なる演算式もしくはＥ（１，ｊ＋１）＝Ｄ（１，ｊ）−Ｄ（１，ｊ＋１）なる演算式に基づいて求められる。図１５に例示する配列データに対して、横方向第２置換部２３５による置換処理が行われると、図１６に示すような第２差分配列データＥが得られることになる。
【０２１４】
こうして、圧縮装置本体部２３０は、ブロック分割部２２０によって分割された個々のブロックを、Ｍ行Ｎ列の圧縮対象配列データＸとして入力し、これに対して圧縮処理を施して第２差分配列データＥとして出力する機能を果たす。
【０２１５】
一方、ブロック間差分演算部２４０は、こうしてブロック単位の圧縮データとして出力された個々の第２差分配列データＥに対して、§２−４で述べたブロック間差分演算処理を実行する。すなわち、所定の基準ブロックを除いて、個々のブロックを構成する第２差分配列データＥの第１行第１列目のセル（ＤＣ値を収容したセル）、第１行第２列目のセル（ＲＣ値を収容したセル）、第２行第１列目のセル（ＢＣ値を収容したセル）の数値を、隣接するブロック内の対応位置のセル内の数値との差分値に置換して、第３差分配列データＦを作成する処理を実行する。
【０２１６】
圧縮配列データ出力部２５０は、個々のブロックについての第２差分配列データＥ（基準ブロックの場合）もしくは第３差分配列データＦ（基準ブロック以外のブロックの場合）を、圧縮配列データＷとして外部に出力する。
【０２１７】
なお、元配列データＲが、Ｍ行Ｎ列の配列サイズもしくはそれより小さい場合には、ブロック分割を行う必要はない。この場合は、元配列データＲとして、Ｍ行Ｎ列もしくはそれ以下のサイズの圧縮対象配列データＸを圧縮装置本体部２３０に直接入力し、圧縮装置本体部２３０から出力される第２差分配列データＥを、そのまま圧縮配列データＷとして取り扱えばよいので、ブロック分割部２２０およびブロック間差分演算部２４０を設ける必要はない。
【０２１８】
図示の実施例において、横方向第１置換部２３２および縦方向第１置換部２３３を第１差分演算部と呼び、縦方向第２置換部２３４および横方向第２置換部２３５を第２差分演算部と呼ぶことにすると、実質的な圧縮処理を実行する圧縮装置本体部２３０は、作業用メモリ２３１と、第１差分演算部と、第２差分演算部とによって構成される装置ということになる。
【０２１９】
ここで、第１差分演算部の主たる役割は、作業用メモリ２３１内の配列データに対して、横方向に差分をとる演算を行うことであり、当該役割は横方向第１置換部２３２によって果たされる。縦方向第１置換部２３３は、基準列に対して縦方向の差分をとる役割を果たすが、当該役割は従たる役割であるため、コストダウンを図る上では、縦方向第１置換部２３３を省略してもかまわない（もちろん、省略すると、圧縮効率は若干低下する）。
【０２２０】
一方、第２差分演算部の主たる役割は、作業用メモリ２３１内の配列データに対して、縦方向に差分をとる演算を行うことであり、当該役割は縦方向第２置換部２３４によって果たされる。横方向第２置換部２３５は、基準行に対して横方向の差分をとる役割を果たすが、当該役割は従たる役割であるため、コストダウンを図る上では、横方向第２置換部２３５を省略してもかまわない（もちろん、省略すると、圧縮効率は若干低下する）。
【０２２１】
このように、縦方向第１置換部２３３および横方向第２置換部２３５を省略した場合は、圧縮装置本体部２３０は、行列状に並んだ各セルについての数値の集合体からなる圧縮対象配列データＸを格納する作業用メモリ２３１と、所定の基準列に属するセルを除いて、圧縮対象配列データＸの個々のセル内の数値を、左もしくは右に隣接するセル内の数値との差分値に置き換える置換処理を実行することにより、第１差分配列データＤを作成する第１差分演算部と、所定の基準行に属するセルを除いて、第１差分配列データＤの個々のセル内の数値を、上もしくは下に隣接するセル内の数値との差分値に置き換える置換処理を実行することにより、第２差分配列データＥを作成する第２差分演算部と、によって構成することができる。
【０２２２】
＜６−２：  配列データの伸張装置＞
図２８は、本発明に係る配列データの伸張装置の具体的な構成例を示すブロック図である。この伸張装置３００は、図２７に示す圧縮装置２００によって圧縮された圧縮配列データＷを伸張して、元配列データＲを復元する機能を有しており、図示のとおり、圧縮配列データ入力部３１０、ブロック復元演算部３２０、伸張装置本体部３３０、ブロック合成部３４０、元配列データ出力部３５０によって構成される。
【０２２３】
圧縮配列データ入力部３１０は、図２７に示す圧縮装置２００によって圧縮された圧縮配列データＷを入力して格納する機能をもった構成要素であり、メモリをはじめとする様々な記憶装置によって構成することができる。圧縮配列データＷは、個々のブロックについての第２差分配列データＥ（基準ブロックの場合）もしくは第３差分配列データＦ（基準ブロック以外のブロックの場合）からなるデータである。
【０２２４】
ブロック復元演算部３２０は、入力した圧縮配列データＷのうちの第３差分配列データについて、ブロック間差分演算部２４０において置換された差分値を元の数値に復元して第２差分配列データＥを得る処理を行う。これにより、すべてのブロックについての圧縮配列データが、図１９に示す第２差分配列データＥになり、個々のブロック単独で伸張処理が可能になる。個々のブロックの第２差分配列データＥは、Ｍ行Ｎ列の配列データであり、順次、伸張装置本体部３３０へと引き渡される。
【０２２５】
伸張装置本体部３３０は、こうして引き渡された個々のブロック内のＭ行Ｎ列の配列データに対して伸張処理を行う構成要素であり、図示のとおり、作業用メモリ３３１、横方向第２置換復元部３３２、縦方向第２置換復元部３３３、縦方向第１置換復元部３３４、横方向第１置換復元部３３５を有している。
【０２２６】
作業用メモリ３３１は、ＲＡＭなどの書換可能なメモリによって構成され、個々のブロックのＭ行Ｎ列の行列状に並んだセル群について、第ｉ行第ｊ列目のセル内の数値ｘ（ｉ，ｊ）の集合体（但し、１≦ｉ≦Ｍ，１≦ｊ≦Ｎ）からなる配列データを格納する役割を果たす。
【０２２７】
なお、この作業用メモリ３３１上に格納された配列データの各セル内の数値は、各置換復元部３３２〜３３５による置換復元処理の対象になる。したがって、実用上は、作業用メモリ３３１内には、置換復元前のＭ行Ｎ列の配列データを格納する第１の領域と、置換復元後のＭ行Ｎ列の配列データを格納する第２の領域と、の双方を設けておき、各置換復元部３３２〜３３５が、第１の領域から読み出した置換復元前の数値を参照しながら、置換復元後の数値を第２の領域に書き込む処理ができるようにしておくのが好ましい。あるいは、置換復元後のＭ行Ｎ列の配列データを格納する領域と、後の演算に必要な一部のセル内の置換復元前の数値を一時的に格納するレジスタ領域と、を設けるようにしてもよい。
【０２２８】
横方向第２置換復元部３３２、縦方向第２置換復元部３３３、縦方向第１置換復元部３３４、横方向第１置換復元部３３５は、この作業用メモリ３３１上の配列データに対して、それぞれ、図２７に示す横方向第２置換部２３５、縦方向第２置換部２３４、縦方向第１置換部２３３、横方向第１置換部２３２が行った置換処理と逆の置換復元プロセスを実行する構成要素である。
【０２２９】
すなわち、横方向第２置換復元部３３２は、作業用メモリ３３１に格納されている第２差分配列データＥについて、横方向第２置換部２３５において置換された差分値Ｅを元の数値Ｄに復元する処理を行い、縦方向第２置換復元部３３３は、横方向第２置換復元部３３２で復元されたデータについて、縦方向第２置換部２３４において置換された差分値Ｅを元の数値Ｄに復元して第１差分配列データＤを得る処理を行う。
【０２３０】
更に、縦方向第１置換復元部３３４は、復元された第１差分配列データＤについて、縦方向第１置換部２３３において置換された差分値Ｄを元の数値ｘに復元する処理を行い、横方向第１置換復元部３３５は、縦方向第１置換復元部３３４で復元されたデータについて、横方向第１置換部２３２において置換された差分値Ｄを元の数値ｘに復元して圧縮対象配列データＸを得る処理を行う。
【０２３１】
結局、伸張装置本体部３３０は、ブロック復元演算部３２０から順次与えられる個々のブロックを、Ｍ行Ｎ列の伸張対象配列データ（第２差分配列データＥ）として入力し、これに対して伸張処理を施して、もとの圧縮対象配列データＸとして出力する機能を果たす。
【０２３２】
一方、ブロック合成部３４０は、こうしてブロック単位の配列データとして出力された個々の圧縮対象配列データＸを合成して元配列データＲを得る処理を行う。すなわち、ブロック分割部２２０が行った分割処理と逆のプロセスにより、個々のブロックを合成して元配列データＲを生成する処理が行われる。こうして合成された元配列データＲは、元配列データ出力部３５０から外部へと出力される。
【０２３３】
なお、元配列データＲを分割せずに圧縮が行われた圧縮配列データＷを伸張する場合には、ブロック単位の処理を行う必要はないので、ブロック復元演算部３２０およびブロック合成部３４０を設ける必要はない。
【０２３４】
図示の実施例において、横方向第２置換復元部３３２および縦方向第２置換復元部３３３を第２差分復元部と呼び、縦方向第１置換復元部３３４および横方向第１置換復元部３３５を第１差分復元部と呼ぶことにすると、実質的な伸張処理を実行する伸張装置本体部３３０は、作業用メモリ３３１と、第２差分復元部と、第１差分復元部とによって構成される装置ということになる。
【０２３５】
ここで、第２差分復元部の役割は、第２差分配列データＥについて、第２差分演算部で置換された値を置換前の値に戻すことにより第１差分配列データＤを復元することであり、第１差分復元部の役割は、第１差分配列データＤについて、第１差分演算部で置換された値を置換前の値に戻すことにより圧縮対象配列データＸを復元することである。
【０２３６】
§６−１で述べたとおり、図２７に示す圧縮装置の構成において、コストダウンを図るために、縦方向第１置換部２３３や横方向第２置換部２３５を省略することが可能であるが、これらを省略した圧縮装置を用いて得られた圧縮配列データＷを伸張する場合には、図２８に示す伸張装置の構成において、縦方向第２置換復元部３３３や横方向第１置換復元部３３５を省略すればよい。
【０２３７】
＜６−３：  画像変換装置＞
図２９は、本発明に係る画像変換装置の具体的な構成例を示すブロック図である。§１では、従来の一般的な画像変換装置１００の基本構成を、図５のブロック図を参照しながら説明した。図２９に示す本発明に係る画像変換装置１００Ａは、図５に示す従来の画像変換装置１００における変換テーブル設定部１１０の代わりに、配列データの圧縮装置を組み込んだ変換テーブル設定部１１０Ａを用い、変換処理部１４０の代わりに、配列データの伸張装置を組み込んだ変換処理部１４０Ａを用いるようにしたものである。
【０２３８】
すなわち、この画像変換装置１００Ａは、ＸＹ二次元座標系上の座標値（ｘ，ｙ）で示される位置に配置された画素の集合からなる原画像Ａを、ＵＶ二次元座標系上の座標値（ｕ，ｖ）で示される位置に配置された画素の集合からなる変換画像Ｂに変換する機能をもった装置であって、図示のとおり、変換テーブル設定部１１０Ａ、変換処理用メモリ１２０、原画像入力部１３０、変換処理部１４０Ａ、変換画像出力部１５０を備えている。
【０２３９】
原画像入力部１３０は、変換処理用メモリ１２０に原画像Ａを入力する機能を果たす構成要素であり、入力された原画像Ａは、変換処理用メモリ１２０内の一領域に格納される。変換処理部１４０Ａは、この原画像Ａに基づいて変換画像Ｂを生成し、変換処理用メモリ１２０内の別な一領域に格納する画像変換処理を実行する。変換画像出力部１５０は、こうして変換処理用メモリ１２０に得られた変換画像Ｂを外部に出力する機能を果たす。
【０２４０】
変換処理用メモリ１２０は、原画像Ａおよび変換画像Ｂを格納するとともに、変換処理に用いられるＸ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙを格納する機能を果たす。これらの座標変換テーブルＴｘ，Ｔｙは、変換テーブル設定部１１０Ａによって変換処理用メモリ１２０に書き込まれ、変換処理部１４０Ａが変換処理を行う際に読み出されて参照される。実用上、この変換処理用メモリ１２０は、書込処理や読出処理を高速で行うことが可能なＲＡＭによってを構成するのが好ましい。
【０２４１】
変換処理部１４０Ａは、変換画像Ｂを構成する各画素Ｐ（ｕ，ｖ）について、Ｘ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙを参照することにより原画像Ａ上の対応点Ａ（ｘ，ｙ）の座標値（ｘ，ｙ）を認識し、認識した座標値（ｘ，ｙ）の近傍に位置する原画像Ａ上の画素の画素値に基づいて画素値を決定し、決定した画素値を変換処理用メモリ１２０内の所定アドレスに書き込むことにより、変換処理用メモリ１２０上に変換画像Ｂを生成する処理を行う。このような画像変換処理の詳細については、既に§１で述べたとおりである。
【０２４２】
この画像変換処理に利用されるＸ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙの内容は、画像変換の変換条件が同一であれば一定である。たとえば、図１に例示した全方位カメラを定点監視カメラとして利用する場合、歪曲円形画像Ａに対する切出位置、切出向き、切出倍率といったパラメータが一定であれば、原画像入力部１３０が時系列的に複数の異なるフレーム画像をそれぞれ原画像Ａとして取り込んだとしても、変換処理用メモリ１２０内に格納されているテーブルＴｘ，Ｔｙは同じ内容のテーブルをそのまま利用することができる。図２に示すプロジェクタの場合も、プロジェクタおよびスクリーンの位置関係や投影倍率が一定であれば、同じテーブルＴｘ，Ｔｙをそのまま利用して台形補正のための画像変換処理が可能である。
【０２４３】
しかしながら、図１に示す例において切出条件に変更が生じた場合や、図２に示す例において投影条件に変更が生じた場合には、変換に利用される幾何学変換関数Ｇ内のパラメータが変化するため、新たな変換テーブルＴｘ，Ｔｙを用意する必要が生じる。変換テーブル設定部１１０Ａは、このように新たな変換条件を設定する必要が生じた場合に、当該新たな変換条件に対応する幾何学変換関数Ｇに基づく演算によって新たな変換テーブルＴｘ，Ｔｙを生成し、これを変換処理用メモリ１２０に設定する処理を行う。新たな変換条件は、たとえば、変換テーブル設定部１１０Ａに対して、オペレータが所定のパラメータ値を入力することにより設定することができる。
【０２４４】
本発明に係る画像変換装置１００Ａの特徴は、変換テーブル設定部１１０Ａ内に、§６−１で述べた配列データの圧縮装置２００（圧縮装置本体部２３０の部分だけからなる実施例や、その他の変形例を含む）が組み込まれており、変換テーブル設定部１１０Ａは、この圧縮装置を利用してＸ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙを圧縮して変換処理用メモリ１２０に設定する点である。したがって、変換処理用メモリ１２０内に格納されているＸ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙは圧縮された状態となっており、格納に必要なメモリ容量は大幅に節約されることになる。その結果、画像変換装置１００Ａ全体のコストダウンを図ることが可能になる。
【０２４５】
このように、各テーブルＴｘ，Ｔｙが圧縮された状態で格納されているため、変換処理部１４０Ａがこれらのテーブルを参照する際には、伸張処理を行う必要がある。そのため、変換処理部１４０Ａ内には、§６−２で述べた配列データの伸張装置３００（伸張装置本体部３３０の部分だけからなる実施例や、その他の変形例を含む）が組み込まれており、変換処理部１４０Ａは、この伸張装置を利用して伸張したＸ座標変換テーブルＴｘおよびＹ座標変換テーブルＴｙを参照することにより、対応点の座標値（ｘ，ｙ）を認識することになる。
【０２４６】
なお、変換処理部１４０Ａは、変換画像Ｂを構成する特定の画素の画素値を決定する処理を行う際に、各変換テーブルＴｘ，Ｔｙの必要なセル（当該特定の画素に対応するセル）内の数値を参照することができればよい。したがって、各座標変換テーブルＴｘ，Ｔｙがブロック分割された後に圧縮されていた場合は、全ブロックの配列データを一括して伸張する必要はなく、参照に必要なブロックごとに伸張処理を行い、必要なブロックごとに伸張した変換テーブルＴｘ，Ｔｙを参照することにより、対応点の座標値（ｘ，ｙ）を認識すれば足りる。したがって、変換処理部１４０Ａに組み込む配列データの伸張装置３００には、図２８に示すブロック合成部３４０を除く部分が組み込まれていれば十分である。
【０２４７】
結局、本発明に係る画像変換装置１００Ａでは、変換テーブル設定部１１０Ａが各変換テーブルＴｘ，Ｔｙを生成して変換処理用メモリ１２０に格納する際に圧縮処理を行う必要が生じ、変換処理部１４０Ａが各変換テーブルＴｘ，Ｔｙを参照する際に伸張処理を行う必要が生じるため、図５に示す従来の画像変換装置１００に比べて、圧縮処理および伸張処理のプロセスが余分に必要になる。しかしながら、圧縮処理および伸張処理のプロセスは、§２，§３で述べたとおり、２つのセル値の差分値を求める減算演算もしくは当該差分値に基づいて元の値を復元する加算演算によって行うことができるため、これらの処理プロセスの演算負担は極めて小さく、実用上、大きな支障が生じることはない。
【０２４８】
＜＜＜  §７．  本発明の変形例  ＞＞＞
これまで、本発明を具体的な配列データを用いた具体的な処理例を挙げながら説明してきたが、もちろん、本発明はこれらの具体的な実施例に限定されるものではない。特に、本願における「縦」および「横」という文言は、行列状の配列データにおいて、互いに直交する配列方向をそれぞれ区別するための便宜に用いたものであり、本発明を実施する上では、「縦」と「横」は相互に可換性を有するものである。
【０２４９】
また、本願において、配列データの各セルについての「左右」や「上下」の位置関係も相互に可換性を有するものである。たとえば、各セルについて、左に隣接するセルとの差分値を求める代わりに、右に隣接するセルとの差分値を求めてもかまわないし、上に隣接するセルとの差分値を求める代わりに、下に隣接するセルとの差分値を求めてもかまわない。
【０２５０】
また、これまで述べてきた実施例は、配列データの圧縮効率をできるだけ高めたり、ハードウエアコストをできるだけ低減させたりするために、発明者が最良と思われるいくつかの形態を示したものである。本発明の作用効果を得る上では、必ずしもこれまでの実施例で示した置換処理をすべて行う必要はなく、一部の置換処理を省略してもかまわない。もちろん、一部のセルについての置換処理を省略すると、一般的には、そのセルについての圧縮効率が低下する可能性が高いが、それでも他の一部のセルについての置換処理が行われている限り、圧縮処理を全く行わない場合に比べれば発明の効果は得られていることになる。
【０２５１】
本発明に係る圧縮処理を行う上では、基準列、基準行、基準セル（ＤＣ値を収容したセル）といった所定の基準値を収容するセルについては、置換処理を行わずに、基準となる元の数値をそのまま残しておく必要がある。これらの基準値を収容するセルについても置換処理を行ってしまうと、基準となる数値の情報が失われ、伸張処理により元の数値を復元することができなくなってしまう。しかしながら、これら基準値を収容するセル以外のセルについては、置換処理を行っても、元の数値を支障なく復元することが可能である。
【０２５２】
もちろん、ＲＣ値やＢＣ値などでは、置換処理を実行すると逆に圧縮効率が低下してしまうことになるが、それでも元の数値を復元する上では何ら支障は生じない。また、それ以外の一般のセルの場合は、置換処理を行わないと、圧縮効率が低下することになるが、元の数値を復元する上では何ら支障は生じない。したがって、最良の結果を得る必要がないのであれば、ＲＣ値やＢＣ値に対しても置換処理を実行してしまってかまわないし、その他の一般のセルのうちのいくつかに対しては置換処理を省略してもかまわない。
【０２５３】
要するに、本発明では、少なくとも、基準列、基準行、基準セルといった所定の基準値を収容するセルを置換対象から除外して、残りのセルのうちのいくつかに対して置換処理を実行すれば、最良の効果ではないにしても、従来技術に対する何らかの効果を得ることができる。これは、ブロック間差分処理についても同様であり、少なくとも所定の基準ブロックを除いて、いくつかのブロックについてブロック間の差分演算が行われるようにすればよい。
【符号の説明】
【０２５４】
１００，１００Ａ：画像変換装置
１１０，１１０Ａ：変換テーブル設定部
１２０：変換処理用メモリ
１３０：原画像入力部
１４０，１４０Ａ：変換処理部
１５０：変換画像出力部
２００：配列データの圧縮装置
２１０：元配列データ入力部
２２０：ブロック分割部
２３０：圧縮装置本体部
２３１：作業用メモリ
２３２：横方向第１置換部
２３３：縦方向第１置換部
２３４：縦方向第２置換部
２３５：横方向第２置換部
２４０：ブロック間差分演算部
２５０：圧縮配列データ出力部
３１０：圧縮配列データ入力部
３２０：ブロック復元演算部
３３０：伸張装置本体部
３３１：作業用メモリ
３３２：横方向第２置換復元部
３３３：縦方向第２置換復元部
３３４：縦方向第１置換復元部
３３５：横方向第１置換復元部
３４０：ブロック合成部
３５０：元配列データ出力部
Ａ：原画像（歪曲円形画像／投影用原画像）
Ａ（ｘ，ｙ）：原画像Ａ上の１点
Ｂ：変換画像（正則矩形画像／台形補正画像）
Ｂ（ｕ，ｖ）：変換画像Ｂ上の１点
Ｂ（１，１）〜Ｂ（３，４）：ブロック
ＢＣ：１ブロックを構成する配列データの第２行第１列目のセル内の数値（Bottom Coefficientの略）
Ｄ：第１差分配列データ
Ｄ１１〜Ｄ８８：配列データを構成するセル内の差分値
ＤＣ：１ブロックを構成する配列データの第１行第１列目のセル内の数値（Direct Currentの略）
Ｅ：第２差分配列データ
Ｅ１１〜Ｅ８８：配列データを構成するセル内の差分値
Ｆ：第３差分配列データ
Ｇ：幾何学変換関数
ｉ：配列データにおける行を示すパラメータ
ｊ：配列データにおける列を示すパラメータ
ｋ：ブロックを示すパラメータ
Ｋ：総ブロック数
Ｍ：配列データの行数
Ｎ：配列データの列数
Ｏ：二次元座標系の原点
Ｐ（ｕ，ｖ）：変換画像Ｂ上の１画素
Ｑ１〜Ｑ４：点Ａ（ｘ，ｙ）の近傍に位置する参照画素
Ｒ：元配列データ
ＲＣ：１ブロックを構成する配列データの第１行第２列目のセル内の数値（Right Coefficientの略）
Ｓ１〜Ｓ４６：流れ図の各ステップ
Ｔｘ：Ｘ座標変換テーブル（配列データ）
Ｔｙ：Ｙ座標変換テーブル（配列データ）
Ｕ：変換画像Ｂが定義されたＸＹ二次元座標系の横座標軸
Ｖ：変換画像Ｂが定義されたＸＹ二次元座標系の縦座標軸
Ｗ：圧縮配列データ
Ｘ：圧縮対象配列データ（Ｘ座標変換テーブルＴｘを構成する配列データ）
Ｘ：原画像Ａが定義されたＸＹ二次元座標系の横座標軸
Ｘ（ｕ，ｖ）：Ｘ座標変換テーブルＴｘを構成するセル
ｘ：座標軸Ｘ上の座標値
ｘ１１〜ｘ８８：配列データを構成するセル内の数値
ｘα，ｘβ，ｘγ，ｘδ：ｘ座標値
Ｙ：原画像Ａが定義されたＸＹ二次元座標系の縦座標軸
Ｙ（ｕ，ｖ）：Ｙ座標変換テーブルＴｙを構成するセル
ｙ：座標軸Ｙ上の座標値
α，β，γ，δ：Ｘ座標変換テーブルＴｘを構成するセル
【図１】
2014082660.tif 000003
【図２】
2014082660.tif 000004
【図３】
2014082660.tif 000005
【図４】
2014082660.tif 000006
【図５】
2014082660.tif 000007
【図６】
2014082660.tif 000008
【図７】
2014082660.tif 000009
【図８】
2014082660.tif 000010
【図９】
2014082660.tif 000011
【図１０】
2014082660.tif 000012
【図１１】
2014082660.tif 000013
【図１２】
2014082660.tif 000014
【図１３】
2014082660.tif 000015
【図１４】
2014082660.tif 000016
【図１５】
2014082660.tif 000017
【図１６】
2014082660.tif 000018
【図１７】
2014082660.tif 000019
【図１８】
2014082660.tif 000020
【図１９】
2014082660.tif 000021
【図２０】
2014082660.tif 000022
【図２１】
2014082660.tif 000023
【図２２】
2014082660.tif 000024
【図２３】
2014082660.tif 000025
【図２４】
2014082660.tif 000026
【図２５】
2014082660.tif 000027
【図２６】
2014082660.tif 000028
【図２７】
2014082660.tif 000029
【図２８】
2014082660.tif 000030
【図２９】
2014082660.tif 000031