JPH06223169A

JPH06223169A - 算術装置

Info

Publication number: JPH06223169A
Application number: JP5293229A
Authority: JP
Inventors: James L Hafner; ジェームズ・エル・ハフナー; Jr Wilfred E Plouffe; ウィルフレッド・エドムンド・プルッフェ・ジュニア
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1992-11-25
Filing date: 1993-11-24
Publication date: 1994-08-12
Anticipated expiration: 2012-07-23
Also published as: US5432892A; JP2634136B2

Abstract

(57)【要約】【目的】連続多変数関数の値を効率よく近似する方法
を提供する。【構成】連続関数を効率よく近似する方法は、３次元
線形補間法を使用し、算術装置中で補間法を実施して、
下記の式４に従って関数の値ｖを計算する。【数１】上式で、ｕ_iは関数のｎ次元定義域空間中の特定の既知
の点ｐ_iに対応するスケーリング係数、ｖ_iは関数のｍ次
元値域空間内の特定の既知の点、ｋ＋１は特定の既知の
点の数である。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は一般的に多数の変数の関
数の評価に関し、より詳細には連続多変数関数の値を近
似するための３次元線形補間法に関する。

【０００２】

【従来の技術】現代の多くのプロセスでは、１つまたは
多数の関数の評価が必要である。こうした関数は、比較
的複雑な数学式で相互に関連付けられる多数の変数を含
むことがしばしばである。しばしば、プロセスの全体的
効率が、関数評価の相対的難易度によって決まる。たと
えば、カラー画像処理の分野では、カラー画像を第１の
色空間から第２の色空間に変換することがしばしば望ま
れる。第１の色空間は、たとえばコンピュータ・ファイ
ルに記憶された画像表現用のものであり、第２の色空間
は、印刷インクによって紙の上に作成されるカラーの指
定用のものである。

【０００３】プロセスの実施中には、一般に、精度が最
大になるように最適化された関数評価技法を提供するよ
りも、効率のよい関数評価技法を提供する方が重要であ
る。たとえば、カラー画像変換の過程で、カラー画像関
数の迅速で巧妙な評価の方が、変換されたカラー画像の
完全に正確な表現よりもはるかに重要である。多くの画
像処理システムの一般的な設計上の目標は、リアルタイ
ム処理能力を提供することなので、この状況では効率が
最重要である。人間の目は小さな画像誤差を補償できる
ので、正確さは絶対に必要な設計パラメータではない。
人間の視覚の特性は、一般に画像レンダリングにおいて
既知の有界限誤差の存在を許容するものである。カラー
画像システムについては正確さよりも効率が重要なこと
は今までにも述べられているが、他の広範囲のプロセス
応用例でも同様の状況が存在する。

【０００４】ある種のプロセス応用例では、関数の出力
はサンプリングできても、関数自体は未知である。たと
えば、コンピュータ・ファイルの色空間から新聞の紙面
への画像の変換を考えられたい。紙と相互作用する印刷
インクによって生成される実際の色は、正確に定量化す
ることが困難または不可能である。紙の上に所与のカラ
ーの外観をもたらす諸因子は未知の関数で表される。も
っとも、その関数の値は様々な間隔でサンプリングでき
る。この状況では、画像情報の正確な表現は全く重要で
はなく、その代りにデータ処理速度に重点を置くことが
できる。

【０００５】既存の多くのプロセスは、広い定義域をも
つ関数を含んでいる。可能なすべてのサンプル値で関数
の出力をサンプリングすることは一般に非実際的であ
る。たとえば、図１は、カラー画像処理システムの環境
において物体の色を表す関数の定義域を示す。現在のカ
ラー画像システムは、カラー画像を、一般に画素と呼ば
れる規則的なスポットの配列として表す。各画素に、３
次元空間における色の座標によって表される色が割り当
てられる。加法色環境（すなわち、陰極線管表示装置）
では、どの色も赤、緑、青の３原色の所与の組合せによ
って表現ができる。図１に関して、赤の値はＸ軸１２に
沿って表され、緑はＹ軸１４に沿って、青はＺ軸１６に
沿って表される。各座標は任意の精度のものでよいが、
座標は一般に８ビット値を使って表現される。このよう
にして、各画素に２²⁴種の異なる色のうちの１つが割り
当てられる。したがって、画素の色を表す関数の定義域
はかなり広い。

【０００６】関数は、関数の定義域内の入力値を受諾
し、入力値に対応する出力値を生成する。関数によって
実施される演算の順序は、実施されるプロセスによって
決まる。陰極線管上に表示されたカラー画像を印刷する
には、画像を減法形から減法形に変換しなければならな
い。前述のように陰極線管画像は、赤、緑、青の特定の
量を指定する画素ごとの表現として記憶される。印刷な
どの減法色応用例では、３原色はマジェンタ、黄色、シ
アン（青緑色）であり、密度（暗さ）を増すため、また
はインクの総使用量を減らすために黒が追加または任意
選択の色として使用される。したがって、画素のカラー
表現を着色印刷インクの既知の量に変換する目的で、通
常はシアン、黄色、マジェンタ、黒のそれぞれについて
その量を０ないし２５５の範囲の整数で表して、関数を
決定しなければならない。この関数は、変数赤、緑、青
の入力値を受け入れ、マジェンダ、黄色、シアン、黒の
量を表す出力値を生成する。入力空間または出力空間と
して使用される他の色空間として、国際照明委員会（Ｃ
ＩＥ）によって定義される標準観測者を表す三刺激値に
基づいて色を表す測色空間がある。ＣＩＥＬ^*ａ
^*ｂ^*、ＣＩＥＬ^*ｕ^*ｖ^*、ＣＩＥＸＹＺがこのよう
な３つの空間である。

【０００７】多くのプロセスでは、関数を解析形で定義
するのは極めて非実際的である。カラー画像変換の環境
では、陰極線管画像表現を新聞紙媒体上でのカラー印刷
に適した形に変換する目的で、作業用解析モデルを開発
するのは非常に難しいと思われる。印刷インクが完全に
線形の応答を示し、紙が完全に白色であるなら、カラー
画像の変換用関数を解析的に指定できることになる。し
かし、実際にはインクは非線形応答を有し、紙は真白で
はない。したがって、印刷関数は、複数の印刷サンプル
について累計された測定値を使用すると最もよく表せ
る。サンプリング可能な関数定義域には２²⁴個の点があ
るので、これらの値をすべて測定し記憶するには、莫大
な時間と記憶域を要する。それよりも、より小さな１組
の測定値（サンプル点）を使用し、補間法によって他の
すべての定義域値の近似値を計算することにより、関数
を近似することができる。

【０００８】１つの有利な補間法は、３次元線形補間法
（volumetric linear interpolation）と呼ばれるもの
である。３次元空間の環境では、通常は２つの技法のど
ちらかを使って３次元線形補間を実施している。第一の
技法は３線形補間法（trilinear interpolation）であ
り、第二の技法は四面体補間法（tetrahedral interpol
ation）である。四面体補間法は、近似値の計算に必要
な算術演算の数が少ないので、３線形補間法など他の関
数近似法よりも好んで選択されることが多い。四面体補
間法の実行に必要なステップ数が少ないことは、それだ
け必要なハードウェアが少なくてすみ、計算ステップの
実施の速度と効率が高まるという、実用上重要な結果を
もたらす。

【０００９】３次元線形補間法は、関数の定義域から複
数のサンプル点を選択することによって実施する。これ
らのサンプル点は図１に示すように規則的な間隔で選択
する。図１に示した関数の定義域は３次元であり、その
結果、選択されるサンプル点は幾何立体のアレイを形成
する。サンプルは、点１８、２０、２２、２４、２６、
２８、３０、３２、３４、３６、３８、４０、４２、４
４、４６、４８で取る。このようにして、サンプル点は
関数の定義域内で直角格子を形成する。この直角格子
は、複数の直方体１０から構成される。

【００１０】四面体補間法の場合、関数の定義域を複数
の四面体に分割する。関数定義域をこのように分割する
プロセスは、しばしば２段階手法（two-step procedur
e）と呼ばれる。通常、定義域をまず図１に示すような
直方体に分割し、こうして得られた各直方体を複数の四
面体に再分割する。

【００１１】図２は、関数定義域の一部分を四面体に再
分割する例を示す。図の直方体１０は、図１のどれか１
つの直方体に対応する。直方体１０は５個の四面体２０
０、２０２、２０４、２０６、２０８に再分割される。
図２の幾何形状は、直方体を５個の四面体に分割する例
であるが、直方体を別の数の四面体構造に分割すること
も可能である。たとえば、直方体はしばしば６個または
１２個の四面体に分割される。直方体を再分割する技法
の１つは、６個の四面体がすべて直方体の頂点に共通の
基点をもつように、直方体内に６個の四面体を配置する
ものである。このようにして、すべての四面体が直方体
の対角線に沿って共通の稜を共有する。上記のような関
数の定義域を幾何立体に分割する方法は、当業者にはよ
く知られている。

【００１２】図３は、図２に対した四面体の幾何構造を
示す透視図である。四面体２００は、４つの平面３０
２、３０４、３０６、３０８、６個の稜ａ−ａ'、ｂ−
ｂ'、ｃ−ｃ'、ｄ−ｄ'、ｅ−ｅ'、ｆ−ｆ'、及び４個
の頂点３１０、３１２、３１４、３１６をもつ幾何立体
である。

【００１３】これ以降の記載において、「ｖ」は「ベク
トルｖ」を表すものとして記載し、「ｐ」は「ベクトル
ｐ」を表すものとして表記する。関数の定義域に沿って
任意に選択した点ｐでの関数の値ｖを近似するには、選
択した点を含む四面体を決定しなければならない。選択
した四面体の４つの頂点３１０、３１２、３１４、３１
６での関数の値ｖをサンプリングし、関数値ｖに標準の
３次元線形補間手順を適用して、点ｐにおける関数値ｖ
の近似値を計算する。頂点の座標など線形補間手順を実
施するのに必要な数値定数及びそれに対応する関数値
は、通常、１つまたは複数の補間表に記憶されている。
このようにすると、関数定義域に沿ったすべての点での
関数値ｖのサンプル値を得る必要はなくなる。

【００１４】ｋ＋１≧ｎ＋１個の点でｎ個の変数の関数
がｍ個の成分をもつ場合、標準の線形補間手順では、関
数Ｆのｍ個の成分のそれぞれについて、ｋ＋１回の乗算
ステップとｋ回の加算ステップの実行が必要である。し
たがって合計では（ｋ＋１）ｍ回の乗算とｋｍ回の加算
となる。これらの数字演算のそれぞれの実行で、貴重な
ハードウェア資源を消費し、近似値の計算に要する時間
が増大する。したがって、３次元線形補間を実施するの
に必要な演算の合計数を減らすことが非常に望ましい。
乗算ステップは加算よりも実施コストがずっと高いの
で、できる限り避けるべきである。したがって、必要な
乗算の回数を減らすことが特に望ましい。

【００１５】既存の３次元補間法が使用している補間表
は、ランダム・アクセス・メモリ（ＲＡＭ）などの記憶
装置に記憶しなければならない。これらの表は、しばし
ばメモリ空間の大きなブロックを占める。したがって、
貴重なメモリ空間を節約するために、必要な補間表のサ
イズを減らすことが望ましい。

【００１６】四面体補間関数を計算する方法は、Katsuh
iro Kanamori及びKiroaki Koteraの論文"Color Correct
ion Technique for Hard Copies by 4-Neighbors Inter
polation Method"、Journal of Imaging Science and T
echnology、Vol.36、No.1（１９９２年１〜２月）に記
載されている。この方法は、関数値［ｃ，ｍ，ｙ］の近
似値を計算するための下記の式１を開示している。な
お、ｃ，ｍ，ｙはそれぞれシアン、マジェンタ、黄色に
対応する。

【数１】

【００１７】

【発明が解決しようとする課題】上記の式は、３次元入
力と３次元出力を有する関数の場合にしか適用されな
い。しかし、標準の赤緑青（ＲＧＢ）ビデオ画像をシア
ン・マジェンタ・黄色・黒（ＣＭＹＫ）の印刷画像に変
換するのが望ましいことが極めて多い。あるいは、それ
ぞれが電磁スペクトル中の異なる周波数範囲に応答する
複数の電磁センサから受け取った画像情報を処理するの
が望ましいこともある。各センサの出力が所与の次元を
表すものとして概念化されている場合、そのような画像
システムでは、３次元よりも大きな次元で計算の実行が
必要となることがある。定義域入力、値域出力またはそ
の両方が３次元以上の次元を表す多次元関数と共に利用
できる関数近似法が求められている。

【００１８】

【課題を解決するための手段】本発明は、Ｋ＋１≧ｎ＋
１個の点を使ってｎ個の変数のｍベクトル値の関数Ｆの
値ｖを近似する、改良された方法を提供する。点は１組
のベクトルｐ₀，ｐ₁，．．．ｐ_kで表される。この関数
はｖ_i＝Ｆ（ｐ_i）の形であり、ｉは０ないしｋの範囲で
ある。このような関数はカラー画像処理システムの分野
でしばしば使用されている。値ｖは、関数の定義域内に
ある任意に選択した点ｐにおける関数の補間出力値を表
す。ｐは関数Ｆへの入力として機能する目標評価点を表
す。ｐは、１つまたは複数のベクトルｐ_iの和で表され
る総和ベクトルとして概念化され、ｖは、１つまたは複
数のベクトルｖ_iの和を含む総和ベクトルとして概念化
されている。

【００１９】本発明の３次元線形補間法は、３次元線形
補間スケーリング定数ｕ_iを定義することによって動作
する。下記の式２が成り立つような１組のスケーリング
係数ｕ_iを使用する。各スケーリング係数ｕ_iは、特定の
点ｐ_i及び特定の関数値ｖ_iに対応する。それぞれのｐ_i
は対応するｕ_iを掛けると、すべての（ｕ_i）＊（ｐ_i）
の和がベクトルｐに等しくなる。ただし、ｉは０ないし
ｋの範囲にある。それぞれのｖ_iに対応するｕ_iを掛ける
と、すべての（ｕ_i）＊（ｖ_i）の和がベクトルｖに等し
くなる。

【数２】

【００２０】ｖの方程式にｕ₀の方程式である下記の式
３を代入する。こうすると、関数の値ｖの方程式が下記
の数式４として得られる。この式４を使って、関数Ｆの
近似値を計算する。Ｆが線形関数である場合、上記の手
順によって得られる値ｖは正確である。

【数３】

【数４】

【００２１】上記の式を使った補間計算では、総和記号
の後のかっこ内の項を計算するのに関数Ｆのｍ個の成分
のそれぞれについてｋ回の加算と、総和過程を完了する
ためにｋ回の乗算とそれに続くＫ−１回の加算と、最後
に１回の加算が必要である。関数Ｆのｍ個の成分を考慮
に入れると、本発明の第１の実施例による３次元線形補
間法を実施するのに、合計でｋｍ回の乗算と２ｋｍ回の
加算が必要である。本発明の第２の実施例では、値（ｖ
_i−ｖ_o）を記憶することによって加算の回数をｋｍ回減
らし、合計でｋｍ回の乗算とｋｍ回の加算となる。

【００２２】従来技術の方法と比べて、第２の実施例で
は加算の回数は同じであり、第１の実施例では多くなる
が、必要な記憶域の量は、問題となる多くのケースで大
幅に少なくなる。

【００２３】たとえば、前掲のKanamoriとKoteraの方法
では、１２^*２^*５^*２^3bバイトが必要であり、直方体１
個当り５個の四面体のそれぞれについて１２個の２バイ
ト値ｖ_iが記憶され、関数定義域を完全に充填するため
に２^3b個の直方体が必要である。ただし、ｂは点ｐを含
む直方体を決定するために使用される点ｐのｎ個の成分
それぞれのビット数（０＜ｂ＜８）である。

【００２４】これとは対照的に、第１の実施例では、２
^*２^3*(b+1)＋２^3*(8-b)バイトが必要である。ただし、
第１項は単一の直方体の値ｖ_iの記憶のみを表し、第２
項は値ｕ_iの記憶を表す。この実施例では、ｂ＞２のと
き、KanamoriとKoteraの方法よりも必要な記憶域が少な
くなる。

【００２５】第２の実施例では、４^*２^*５^*２^3b＋２
^3*(8-b)バイトが必要である。ただし、第１項は直方体
ごとに５個の四面体のそれぞれについて２バイト値ｖ_i
−ｖ_o（１≦ｉ≦ｋ）とｖ_oの記憶を表し、第２項は単一
の直方体の値ｕ_iの記憶を表す。この実施例でも、ｂ＞
２のとき、必要な記憶域が少なくなる。

【００２６】

【実施例】図４は、本発明の好ましい実施例の全体的動
作環境を示す構成図である。本発明の３次元線形補間法
実行部４１８は、中央演算処理装置４１６と、恐らくは
他の内部装置または外部装置とを含む、コンピュータ４
２０によって実行される。コンピュータ４２０は、たと
えば簡単な卓上型パーソナル・コンピュータでも、大型
で複雑なメインフレーム・コンピュータでもよい。中央
演算処理装置４１６は、本発明の３次元線形補間法を実
施するのに必要な命令を実行する手段を備えている。

【００２７】コンピュータ４２０は、図形インターフェ
ース４１０に結合される。図形インターフェース４１０
は、図の例ではビデオ・カメラ４００に結合される。ビ
デオ・カメラ４００は、赤出力４０２、緑出力４０４、
青出力４０６を提供する。これらの出力は、図形インタ
ーフェース４１０に接続され、図形インターフェース４
１０はこれらの出力を、赤、緑、青の入力変数を有する
多変数関数に変換する。この関数が中央演算処理装置４
１６に供給され、そこで本発明の線形補間法４１８が関
数に適用される。この例の線形補間法４１８の出力は、
シアン、マジェンダ、黄色、黒の量を表す出力を有する
関数である。これらの出力はプリンタ・ドライバ回路４
２２に供給される。これらの回路は、黄色、マジェン
タ、シアン、黒のインク・ディスペンサ４２４、４２
６、４２８、４３０によって配量されるインクの量を制
御する。

【００２８】図４は、ビデオ・カメラ４００とインク・
ディスペンサ４２４、４２６、４２８、４３０の環境で
使用される本発明を例示的に示す。たとえば、ビデオ・
カメラ４００の代りに蛍光ビデオ表示画面を使用するこ
ともできる。さらに、本発明は、多変数関数の値を近似
することが望まれる、カラー画像処理以外の環境でも使
用できる。

【００２９】図５は、関数Ｆの定義域から任意に選択さ
れた点ｐ５１５を示す３次元のグラフである。ｘ軸５１
２は赤色の輝度、ｙ軸５１４は緑色の輝度、ｚ軸５１６
は青色の輝度を表す。ｘ、ｙ、ｚの許容される値は０な
いし１００の範囲にあり、この範囲が関数の定義域を定
義する。色の表現にはしばしば８ビット値を使用する
が、この例では例示のために関数定義域を単純化してあ
る。点ｐ５１５は、加法的原色の形で指定された所与の
ビデオ・イメージ内の１画素の色を表す。

【００３０】この例では、点ｐ５１５はビデオ・カメラ
が受け取るカラー画像の１画素を表す。ビデオ・カメラ
の狙いが海にあると仮定すると、その結果、位置ｘ＝１
０、ｙ＝５０、ｚ＝８０にある青ないしシアンの範囲の
色に対応する点ｐ５１５が得られる。ビデオ画像を新聞
紙の印刷に適した形に変換することが望まれる。画素の
加法的原色表現を減法色を表す形に変換しなければなら
ない。この変換過程は、赤、緑、青の入力変数及びシア
ン、マジェンタ、黄色、黒の出力値を伴う関数として表
現することができる。

【００３１】カラー変換の関数は比較的複雑なので、す
ぐに分析的指定に役立つものではない。関数定義域中の
代表点で関数の値をサンプリングし、これらの値を将来
の参照用に作表する方がずっと効率がよい。したがっ
て、関数の定義域を図１ないし３に示すように分割し、
関数のサンプル値を各四面体の頂点にとる。次いで、関
数定義域内の任意に選択した点ｐ５１５での関数の値を
知りたい場合、最も近いサンプル点での既知の関数値を
参照することにより、関数の値を補間することができ
る。これは、まず選択した点ｐ５１５を含む直方体５１
０を位置指定し、次いで点ｐを含む立体内部の四面体５
１２を決定することによって実施する。選択された四面
体の頂点５３０、５３２、５３４、５３６での関数のサ
ンプルされた値を補間プロセスで利用して、選択された
点ｐ５１５での関数の近似値を計算する。

【００３２】座標（１０，５０，８０）における点ｐ５
１５は、頂点５３０、５３２、５３４、５３６を有する
四面体の内部にある。加法的原色と減法的原色の関係
は、四面体の各頂点５３０、５３２、５３４、５３６で
特徴付けられている。たとえば、頂点５３０が、それぞ
れ赤、緑、青の量を表す（１２，５６，８４）の座標を
有するものとする。関数サンプリング・プロセスであら
かじめ、これら赤、緑、青の量が、シアンの値７８、マ
ジェンダの値３４、黄色の値６、黒の値１０に対応する
ことが決定された。頂点５３２、５３４、５３６でも同
様のサンプルを取った。これらの頂点５３０、５３２、
５３４、５３６での関数入力（赤、緑、青）と出力（シ
アン、マジェンダ、黄色、黒）の既知の関係を線形補間
手順で利用して、関数入力と出力の間の厳密な関係がわ
かっていない点での関数入力と出力の関係を近似する。
関数近似の相対的な難易度によって、カラー画像プロセ
スの全体的効率が決まることが多い。したがって、迅速
で有効な線形補間法を開発することが極めて望ましい。

【００３３】本発明は、ｋ＋１≧ｎ＋１個の点でｎ個の
変数のｍベクトル値をもつ関数Ｆの値ｖを近似する改良
された方法を提供する。本発明の第１の実施例に従って
関数近似を実施するのに必要なステップを図６に示す。
ブロック６０２で、関数パラメータを定義する。この関
数は、Ｖ＝Ｆ（ｐ_i）の形であり、ｉは０〜ｋの範囲に
あり、ｋ＋１は補間プロセスで使用するサンプル点の数
を示す。この関数はｎ個の変数を使って書くことができ
る。関数の入力点は、１組のベクトルｐ₀，ｐ_1...ｐ _kで
表される。このような関数はカラー画像処理システムで
しばしば使用される。

【００３４】プロセスの出力は値ｖとなる。これは、関
数の定義域内にある任意に選択した点Ｐにおける関数の
補間出力値を表す。特定のターゲット評価点Ｐについ
て、ｋ＋１個のベクトルＰ_iの組が補間プロセスへの入
力である（ブロック６０２）。

【００３５】ブロック６０４に進んで、３次元線形補間
スケーリング定数ｕ_iを決定する。これらの３次元線形
補間スケーリング定数は、式５が成り立つように算出す
る。

【数５】

【００３６】大きな画像内の各点ｐごとにスケーリング
定数を計算するのは、時間がかかり非効率的なので、本
発明では、ブロック６０４でスケーリング定数の格納と
適当な定数の検索を行う。各スケーリング係数ｕ_iは、
特定の点ｐ_i及び特定の関数値ｖ_i＝Ｆ（ｐ_i）に対応す
る。

【００３７】次にブロック６０６で、式６を使って関数
の値ｖを近似する。Ｆが線形関数である場合、上記の手
順で得られる値ｖは正確なものとなる。

【数６】

【００３８】前述の諸方程式を使った補間計算では、関
数Ｆのｍ個の成分のそれぞれについて、括弧内の頂を計
算するためにｋ回の加算と、総和プロセスを完了するた
めにＫ回の乗算及びそれに続くｋ−１回の加算と、最後
に１回の加算が必要である。関数Ｆがｍ個の成分を有す
ることを考慮すると、本発明の方法による３次元線形補
間を実施するには、合計でｋｍ回の乗算と２ｋｍ回の加
算が必要である。これとは対象的に、従来技術の方法で
は、関数のｍ個の成分のそれぞれについて、ｋ回の乗算
とｋ回の加算が必要である。

【００３９】したがって、従来技術の方法では合計でｋ
ｍ回の乗算とｋｍ回の加算を行う。しかし、本発明の変
形１よりもより多くの定数の記憶が必要である。

【００４０】本発明の３次元線形補間手順の第２の好ま
しい実施例を実施するためのプロセスを図７及び８の流
れ図に示す。この手順は、３変数のスカラー関数の文脈
中で機能する。関数の各入力成分と出力成分を８ビット
値で表す（図７のブロック７０２）。以下で説明するよ
うに、８ビット値と共にビット・アドレス方式を採用す
る。入力値の計算される範囲を関数の定義域として定義
する（ブロック７０４）。従来技術の補間手順と同様
に、関数の定義域を、直方体の格子を構成する諸点につ
いてサンプリングする。次に、後でより詳しく説明する
ように、これらの点のいくつかを実際の関数近似手順用
に選択する。

【００４１】関数の定義域内部にあるサンプル点を選ば
なければならない。図７及び８の方法によれば、各入力
成分ごとに１６個の間隔があり、合計１７個の値が得ら
れるようにサンプル点を選ぶ（図７のブロック７０
６）。これによって、関数定義域が４０９６（１６×１
６×１６）個の直方体に分割され、サンプル値は直方体
のかどにある。

【００４２】ブロック７０８で、関数定義域の外部にあ
る３つの極値において関数を評価する。この評価は、こ
の関数が当該の定義域の外部でも連続しており、かつ、
ビット表現（Ｘ，Ｙ，Ｚ）＝（１００００００００，
＊，＊），（Ｘ，Ｙ，Ｚ）＝（＊，１０００００００
０，＊）及び（Ｘ，Ｙ，Ｚ）＝（＊，＊，１０００００
０００）をもつ点で関数が評価できるとの仮定に基づい
ている（ブロック７０８）。定義により、これらの点は
当該定義域の外部にあるが、定義域内部にあるいくつか
の点の近似値を算出するために必要である。

【００４３】次にブロック７１０で、直方体のかどを構
成するサンプル点における関数値を計算して、４９１３
（１７×１７×１７）個のエントリを有する３次元アレ
イＦにセーブする。アレイＦは、ランダム・アクセス・
メモリなど標準のメモリ装置に記憶する。このアレイの
各エントリには、メモリから有利なアドレス指定技法を
用いてアクセスする。関数が連続である限り、均一なア
ドレス指定値を使ってメモリ装置からサンプル点にアク
セスすることができる。連続関数の仮定が有効でない場
合は、任意の成分の４つの上位ビットがすべて等しい間
隔を特殊ケースとして扱わなければならない。しかし、
連続関数と仮定すると、各サンプル点の各アドレス成分
は４つの下位ビットが０となる。

【００４４】サンプル点と共に使用するアドレス方式
は、次のように機能する。点（ｘ，ｙ，ｚ）を囲む直方
体の下側のかどは、Ｆ（ｘ_h、ｙ_h、ｚ_h）を使ってアド
レスされる。ただし、指標ｘ_h、ｙ_h、ｚ_hはそれぞれ０
〜１６の範囲にあり、ｘ＝１６ｘ_h＋ｘ₁、ｙ＝１６ｙ_h
＋ｙ₁、ｚ＝１６ｚ_h＋ｚ₁であり、ｘ_hはｘの上位４ビッ
トによって形成される数、ｘ₁はｘの下位４ビットによ
って形成される数であり、ｙとｚについても同様であ
る。

【００４５】ブロック７１２で、各直方体をさらに複数
の四面体に分割する（図８）。ブロック７１４で、直方
体のかど（頂点）にあるサンプル点に対するアレイＦか
らの値を使用し、直方体内部の四面体頂点にある点に対
するサンプル点値を計算することにより、Ｔアレイ８０
０（図９）を作成する。図９を参照すると、Ｔアレイ８
００は４次元であり、最大サイズが９８３０４（１６×
１６×１６×２４）要素である（参照８１６）。Ｔアレ
イ８００は、各エントリ８０２がそれぞれ２４個のアレ
イ要素からなる４０９６（１６×１６×１６）個のエン
トリの３次元アレイとして概念化することができる（参
照８０２）。アレイ・エントリ８０２は、ｘ軸８０６、
ｙ軸８０８、ｚ軸８１０に沿ってインデックスすること
によってアクセスされる。各アレイ・エントリ８０２
は、２４個の要素８１６が４×６表に配列された２次元
要素表８０４を含む。ｔ軸８１４は、各直方体の６個の
四面体に対応する６単位の次元を有する。ｖ軸８１２
は、四面体の４個の頂点に対応する４単位の次元を有す
る。たとえばアレイ・エントリ８０２が、直方体の下側
のかどを表すｘ，ｙ，ｚの値を有する場合、このアレイ
・エントリの要素表８０４は、最大２４個の要素８１６
を含むことになる。この多次元アレイは、変数ｘ，ｙ，
ｚのメモリ位置と１〜２４の要素番号をインデックスす
ることにより、従来型のランダム・アクセス・メモリ装
置に記憶することができる。

【００４６】各要素表８０４が２４個のエントリをもつ
のは、各直方体を６個の四面体に分割したことに基づい
ている。この表は、各固有のルート点即ち各基点ｖ₀に
ついての関数値を含む対する要素８１６と、直方体の１
四面体内部での各固有の差ｖ_i−ｖ₀のエントリを含む。
いくつかの四面体が隣接する直方体を横切ってルート及
び面を共有する場合は、要素表８０４中の値を、他の直
方体を表すエントリ８０２中で複製することができる。
これらの値の共有によって、必要な記憶空間が削減され
る。

【００４７】直方体を四面体に分割する特殊技法を利用
すると、Ｔアレイに必要な記憶空間を、前段で記載した
よりも著しく削減することができる。各直方体を、６個
の四面体がすべて直方体のかどで共通の基点をもち、各
四面体がその直方体の対角線に沿って共通のエッジ
（稜）をもつように、６個の四面体に分割する。このよ
うにすると、アレイＴは、４０９６個の直方体のそれぞ
れごとに８個のエントリ、合計３２７６７（１６×１６
×１６×８）個のエントリを含むことになる。この８個
のエントリの１つが、６個の四面体すべてに共通の基点
における関数値を表す。８個のエントリのうち残りの７
個は、直方体の他の７個の頂点の１つにおける関数値と
基点における関数値の差を表す。このようにすると、必
要なランダム・アクセス・メモリの記憶空間が９８３０
４エントリから３２７６７エントリに減少する。しか
し、直方体が異なると基点も違ってくるときは、上記の
四面体の共通基点構成を使って隣接する直方体を横切る
位置にある四面体のエントリを共有することにより、記
憶空間をさらに節約することは、不可能である。

【００４８】ここで図８に戻ると、１つの追加アレイ、
すなわち重み・頂点（ＷａｎｄＶ）アレイが、関数の定
義域中の４０９６個の直方体のそれぞれごとに基礎とな
る構造をメモリに記憶する目的で作成される（ブロック
７１６）。ＷａｎｄＶアレイ９００のデータ構造を図１
０に示す。ＷａｎｄＶアレイ９００は、１６×１６×１
６の３次元構成として論理的に配列された４０９６個の
エントリ（参照９０２）の表である。ＷａｎｄＶアレイ
９００は、ＷａｎｄＶ（ｘ₁，ｙ₁，ｚ₁）を使ってアド
レス指定される。ただし、ＷａｎｄＶの各インデックス
ｘ₁，ｙ₁，ｚ₁は１ないし１６（または０ないし１５）
の範囲にある。エントリ９０２は、変数ｘ₁，ｙ₁，ｚ₁
をインデックスすることによって通常のランダム・アク
セス・メモリに格納できる。許容範囲（０ないし１５ま
たは１ないし１６）内にあるｘ₁，ｙ₁，ｚ₁の特定の１
組の値が、ＷａｎｄＶアレイ９００内で所与のエントリ
９０２を一義的に指定する。図１０を参照すると、イン
デックスｘ₁でｘ軸９０４に沿って所与の位置にある１
群のエントリ９０２が選択され、インデックスｙ₁でｙ
軸９０６に沿って所与の位置にある１群のエントリ９０
２が選択され、インデックスｚ₁でｚ軸９０８に沿って
所与の位置にある１群のエントリ９０２が選択される。
こうした各エントリ９０２は、ランダム・アクセス・メ
モリ内の１つまたは複数の論理メモリ位置に対応する。

【００４９】ＷａｎｄＶアレイ９００中の各エントリ９
０２は、直方体内部でオフセットｘ₁，ｙ₁，ｚ₁を有す
るサンプル点に関する情報を格納する。格納される情報
のタイプについては下段でより詳しく述べる。オフセッ
トｘ₁，ｙ₁，ｚ₁は、直方体のかどに対して決定され
る。ＷａｎｄＶアレイ９００の目的は、アレイを一回だ
け計算すればよく、その後は必要に応じて多くの近似を
実施するために何回も使用できるように、所与のオフセ
ットのサンプル点に関する情報を記憶しておくことでも
ある。

【００５０】図１０に示したＷａｎｄＶアレイ９００の
各エントリには以下の情報が記憶される。各エントリは
７つの項目を含む。

【００５１】（１）増分０₁、これを値（ｘ_h，ｙ_h，
ｚ_h，０）に加えると、その四面体の第１の差値（ｖ₁−
ｖ₀）のＴ内のインデックスが得られる。この値は、４
−タプルを表す。

【００５２】（２）増分０₂、これを値（ｘ_h，ｙ_h，
ｚ_h，０）に加えると、その四面体の第２の差値（ｖ₂−
ｖ₀）のＴ内のインデックスが得られる。この値は、４
−タプルを表す。

【００５３】（３）増分０₃、これを値（ｘ_h，ｙ_h，
ｚ_h，０）に加えると、その四面体の第３の差値（ｖ₃−
ｖ₀）のＴ内のインデックスが得られる。この値は、４
−タプルを表す。

【００５４】（４）増分０₄、これを値（ｘ_h，ｙ_h，
ｚ_h，０）に加えると、その四面体の基点値（ｖ₀）のＴ
内のインデックスが得られる。この値は、４−タプルを
表す。

【００５５】（５）重みＷ₁、これに第１の差Ｔ
（（ｘ_h，ｙ_h，ｚ_h，０）＋０₁）を掛けると、最終近似
部が得られる。この値は、ターゲット・オフセットと、
０₁による点を排除した後に残る３つのサンプル点とを
使って形成される四面体の体積を、抽出された四面体の
体積で割った商に等しい。

【００５６】（６）重みＷ₂、これに第１の差Ｔ
（（ｘ_h，ｙ_h，ｚ_h，０）＋０₂）を掛けると、最終近似
部が得られる。この値は、ターゲット・オフセットと、
０₂による点を排除した後に残る３つのサンプル点とを
使って形成される四面体の体積を、抽出された四面体の
体積で割った商に等しい。

【００５７】（７）重みＷ₃、これに第１の差Ｔ
（（ｘ_h，ｙ_h，ｚ_h，０）＋０₃）を掛けると、最終近似
部が得られる。この値は、ターゲット・オフセットと、
０₃による点を排除した後に残る３つのサンプル点とを
使って形成される四面体の体積を、抽出された四面体の
体積で割った商に等しい。

【００５８】最終近似は、ＷａｎｄＶアレイ９００（図
１０）と関数値アレイＴ８００（図９）から次のように
して算出される（図８のブロック７１８）。Ｆ(ｘ,ｙ,
ｚ)＝ＷａｎｄＶ(ｘ₁,ｙ₁,ｚ₁).Ｗ₁ ^*Ｔ((ｘ_h,ｙ_h,ｚ_h,
０)＋ＷａｎｄＶ(ｘ₁,ｙ₁,ｚ₁).０₁)＋ＷａｎｄＶ(ｘ₁,
ｙ₁,ｚ₁).Ｗ₂ ^*Ｔ((ｘ_h,ｙ_h,ｚ_h,０)＋ＷａｎｄＶ(ｘ₁,
ｙ₁,ｚ₁).０₂)＋ＷａｎｄＶ(ｘ₁,ｙ₁,ｚ₁).Ｗ₃ ^*Ｔ
((ｘ_h,ｙ_h,ｚ_h,０)＋ＷａｎｄＶ(ｘ₁,ｙ₁,ｚ₁).０₃)＋
Ｔ((ｘ_h,ｙ_h,ｚ_h,０)＋ＷａｎｄＶ(ｘ₁,ｙ₁,ｚ₁).０₄).

【００５９】上式を使って、関数定義域内部の任意に選
択した点ｐ５１５（図５）での関数の値ｖを近似する。
図７及び８の手順は、選択した点を含む直方体を決定
し、また選択した点を含む立体内部の特定の四面体を突
き止めることによって機能する。適当な四面体頂点での
関数のサンプル値がＷａｎｄＶアレイ９００とＴアレイ
８００から得られ、これを使って、任意に選択した点ｐ
での関数値ｖの近似を計算する。

【００６０】Ｆ（ｘ，ｙ，ｚ）に関する上式で、ｖ₀と
してどのベクトルを使用するかの選択は任意である。上
式を適宜修正すれば、ｖ_iベクトルのどれをｖ₀として使
うこともできる。たとえば中心立法四面体構造では、ベ
クトルｖ₀として中心点を選択するのが自然であるが、
中心点以外の点をｖ₀として選択することもできる。四
面体が直方体の共通対角線を共有するという上記の方法
では、基本ベクトルとして直方体の基点または主共有対
角線の１隅を選択するのが論理的である。サンプル点の
立方体格子を使用する方法では、立方体中にアドレスす
るために使用される立方体のかどによって基本ベクトル
を決定することができる。

【００６１】既存の従来技術の最良の技法と比較して、
本発明の方法では、近似を計算するのに使用する演算の
数は同じである。しかし実際の多くの状況では、記憶の
量を大幅に減らすことができる。

【００６２】図１１は、本発明の第１の実施例による関
数値を近似するための算術装置１０００の構成図であ
る。装置１０００は、入力ポート１００２で、Ｒ、Ｇ、
Ｂの各成分について８ビット値の形の入力を受け入れ
る。この３つの８ビット値は、赤、緑、青の３次元色空
間定義域内部の任意に選択した点の座標を表す。この点
は、シアン、マジェンタ、黄色の３次元色空間領域内で
出力を生成する関数の定義域入力となる。

【００６３】入力ポート１００２で受け取った入力は、
デマルチプレクサ回路１００４に供給される。このデマ
ルチプレクサ回路１００４はこの２４ビットを、Ｒ_L、
Ｇ_L、Ｂ_Lと名付ける４つの低位ビットからなる３つのグ
ループと、Ｒ_H、Ｇ_H、Ｂ_Hと名付ける４つの高位ビット
からなる３つのグループに分離する。これらのビットＲ
_L、Ｇ_L、Ｂ_L、Ｒ_H、Ｇ_H、Ｂ_Hはそれぞれ、図８及び９に
関して論じたビットｘ_L、ｙ_L、ｚ_L、ｘ_H、ｙ_H、ｚ_Hに対
応する。

【００６４】これらの低位ビットは線１００６を横切
り、ＷａｎｄＶアレイ・メモリ１０１０をインデックス
するのに使用される。Ｒ_L、Ｇ_L、Ｂ_Lの各入力値ごと
に、ＷａｎｄＶアレイ・メモリ１０１０は４個の加算定
数０₁、０₂、０₃、０₄と３個の乗算定数Ｗ₁、Ｗ₂、Ｗ₃
を出力する。加算定数０₁は線１０１２を介して合算器
１０２０の第１入力に供給される。合算器１０２０の第
２入力は、デマルチプレクサ回路１００４から線１００
８を介して、Ｒ_H、Ｇ_H、Ｂ_Hのそれぞれからの４つの高
位ビットを受け取る。同様に、加算定数０₂は線１０１
４を介して合算器１０２２に供給され、０₃は線１０１
６を介して合算器１０２４に供給され、０₄は線１０１
８を介して合算器１０２６に供給される。各合算器１０
２２、１０２４、１０２６はそれぞれ加算定数０₂、
０₃、０₄をＲ_H、Ｇ_H、Ｂ_Hのそれぞれからの４つの高位
ビットに加える。１２の高位ビットがすべて、各合算器
１０２０、１０２２、１０２４、１０２６の１つの入力
に伝播される。

【００６５】ＷａｎｄＶアレイ・メモリ１０１０の内容
は、図７及び８に関して述べた手順を使って生成され
る。ＷａｎｄＶアレイのデータ構造は図１０に示されて
いる。この例では、図１０のＸ_L軸９０４は赤色を表
し、デマルチプレクサ１００４の出力におけるＲ_Lの当
該の値によってインデックスされる。同様に、Ｙ_L軸９
０６は緑を表し、Ｚ_L軸９０８は青を表す。

【００６６】合算器１０２０、１０２２、１０２４、１
０２６からの出力は、Ｔアレイ・メモリ１０２８のイン
デックス入力を提供するために使用される。第１の合算
器１０２０の出力はＴアレイ・メモリ１０２８からの第
１の関数値ｖ₁をインデックスし、第２の合算器１０２
２の出力は第２の関数値ｖ₂をインデックスし、第３の
合算器１０２４の出力は第３の関数値ｖ₃をインデック
スする。第４の合算器１０２６の出力は、ポート１００
２における（Ｒ，Ｇ，Ｂ）入力の高位ビットＲ_H、Ｇ_H、
Ｂ_Hで指定される直方体の基点におけるこの関数の関数
値ｖ₀をインデックスする。

【００６７】Ｔアレイ・メモリ１０２８の内容は、関数
Ｆの範囲空間を分割する立体領域の頂点における既知の
関数値ｖ₁を含んでいる。これらの値は、ＷａｎｄＶア
レイ１０１０により図６のブロック６０６に示す公式に
従って生成される乗算定数と組み合わされる。すなわ
ち、項（ｖ_i−ｖ₀）中の第１、第２、第３の関数値
ｖ₁、ｖ₂、ｖ₃がそれぞれ第４の関数値ｖ₀と共に当該の
減算器１０２９、１０３０、１０３１に供給される。こ
れらの減算器は、差を計算する。この差に、ステップ６
０６の方程式中で与えられる当該の乗算定数を個別に掛
けなければならない。減算器１０３１で計算された差値
（ｖ₁−ｖ₀）は、乗算器１０３４に供給され、そこでそ
の差に第１の乗算定数Ｗ₁を掛ける。同様に、減算器１
０３０及び１０２９で生成された差には、それぞれ乗算
器１０３３及び１０３２中で加重定数Ｗ₂及びＷ₃が掛け
られる。

【００６８】第１、第２、第３の乗算器１０３４、１０
３３、１０３２の出力はそれぞれＴアレイ・メモリ１０
２８から線１０５２を介して受け取った関数値ｖ₀と共
に合算器１０３６に入力される。合算器１０３６の出力
は、算術装置１０００の出力を表す。この出力は、ＣＭ
Ｙ色空間におけるシアン、マジェンタ、黄色の各色の特
定の量を表す関数値域の値の形を取る。関数値域値は、
算術装置１０００により、赤緑青色空間中の１つまたは
複数の定義域入力に、図６に示した３次元線形補間法を
適用することによって近似される。

【００６９】図１２は、図７、８、９、１０に示した３
次元線形補間法を適用することによって関数値域値を近
似する本発明の第２の実施例を示す。この装置は、下記
の例外を除き、本質的に図１１に示し上記で論じたもの
と同等である。すなわち、減算器１０２９、１０３０、
１０３１が省略されており、Ｔアレイ・メモリ１０２８
の内容に、省略した減算器で計算されていた差値が含ま
れている。

【００７０】図１２のＴアレイ・メモリ１０２８の内容
は、図７及び８に示した手順に従って生成されている。
Ｔアレイ・メモリ１０２８のデータ構造は図９に示され
ている。この例では、図９のＸ軸８０６は赤を表し、Ｙ
軸８０８は緑を表し、Ｚ軸８１０は青を表す。差値
Δ₁、Δ₂、Δ₃及びｖ₀の値はすべて１アレイ・エントリ
８０２の４要素縦列内に格納される。この縦列は、エン
トリ８０２内の、Ｔ軸８１６に沿ったＴの所与の値に対
応するアレイ要素８１６を示す。一方、Ｔの所与の値
は、直方体内部の、入力ポート１００２におけるＲ、
Ｇ、Ｂの値で指定される所与の四面体に対応する。

【００７１】このとき、合算器１０２０、１０２２、１
０２４、１０２６からの出力は、それぞれ、高位ビット
Ｒ_H、Ｇ_H、Ｂ_Hで指定される直方体の基点における関数
の第１関数値Δ₁、第２関数値Δ₂、第３の差値Δ₃、及
び第４の値ｖ₀をインデックスする。３つの差値はそれ
ぞれ乗算器１０３４、１０３３、１０３２に直接供給さ
れるが、関数値ｖ₀は、これらの乗算器によって生成さ
れる積と共に加算器１０３６に供給される。このとき、
合算器１０３６の出力は、図７、８、９、１０に示す線
形補間法による関数値域値の近似を表す。

【００７２】図７、８、９、１０、１１に示した補間技
法の利点は、補間表の格納に必要な全体のメモリ空間
が、従来技術の技法で利用していた量に比べて減少した
ことである。本発明ではＴアレイとＷａｎｄＶアレイの
２つの表を使用するが、これらの表で消費するメモリ空
間の合計量は、従来技術の各種システムで必要な量より
もかなり少ない。単一の補間定数表を使用する従来技術
のシステムでは、必要な表のサイズが、本発明の２つの
表の合計サイズよりもずっと大きい。

【００７３】以上、本発明のいくつかの具体的実施例に
ついて述べた。しかし、本発明の趣旨及び範囲から逸脱
せずに様々な修正及び変更が行えることを理解された
い。たとえば、関数定義域を不均等に分割または再分割
してもよい。不均等分割は、当技術分野で周知の自動メ
ッシング技法を使って実施できる。こうしたメッシング
技法は、当技術分野で周知の有限要素数学解析法を使用
する解析用のデータを用意するために使用される。本発
明の方法は、カラー・イメージ処理に適用することがで
き、また、多変数関数の値を計算することが望まれる他
の分野にも有利に適用できる。

【図面の簡単な説明】

【図１】多変数関数の定義域の直方体への分割を示す透
視図である。

【図２】直方体の複数の四面体構造への再分割を示す透
視図である。

【図３】四面体の幾何的特徴を示す透視図である。

【図４】カラー画像処理システムの文脈における本発明
の好ましい実施例の全体的動作環境を示す構成図であ
る。

【図５】図１に示した関数の定義域内部で任意に選択し
た点を示す３次元グラフである。

【図６】本発明の３次元線形補間法の第１の実施例を記
述する流れ図である。

【図７】本発明の３次元線形補間法の第２の実施例を記
述する流れ図である。

【図８】本発明の３次元線形補間法の第２の実施例を記
述する流れ図である。

【図９】図７及び８の方法で使用するＴアレイのデータ
構造を示す３次元メモリ・マップである。

【図１０】図７及び８の方法で使用するＷａｎｄＶアレ
イのデータ構造を示す３次元メモリ・マップである。

【図１１】本発明の第１の実施例に従って関数値を近似
する算術装置の構成図である。

【図１２】本発明の第２の実施例に従って関数値を近似
する算術装置の構成図である。

【符号の説明】

４００ビデオ・カメラ４１０図形インターフェース４２０コンピュータ４２２プリンタ・ドライバ回路４２４黄色インク・ディスペンサ４２６マジェンダ・インク・ディスペンサ４２８シアン・インク・ディスペンサ４３０黒インク・ディスペンサ

───────────────────────────────────────────────────── フロントページの続き (72)発明者ウィルフレッド・エドムンド・プルッフェ・ジュニアアメリカ合衆国95120、カリフォルニア州サンノゼ、ポート・アレグレ・ドライブ 5817

Claims

【特許請求の範囲】

【請求項１】第１のｎ次元色空間内に定義域入力を有
し、第２のｍ次元色空間内に値域出力を有し、該定義域
入力が、ｋ＋１（ｋ≧ｎ）個の頂点を有する複数個のｎ
次元立体に分割され、各頂点がサンプル定義域入力点ベ
クトルｐを含み、各サンプル定義域入力点ベクトルｐが
第１色空間内に１組の座標を有する、関数Ｆの値ベクト
ルｖを近似するための算術装置であって、（ａ）第１色
空間内にある任意に選択した定義域入力点ベクトルｐに
対する１組の座標を表す複数のビットを入力する入力ポ
ート手段であって、該ベクトルｐが座標ｘ₁，
ｘ₂，．．．，ｘ_n（ただし、ｘ₁が第１色空間内の第１
色成分を表し、ｘ₂が第１色空間内の第２色成分を表
し、以下同様にして、ｘ_nが第１色空間内の第ｎ色成分
を表す）を有し、該複数のビットが高位ビットと低位ビ
ットを含む、入力ポート手段と、（ｂ）上記入力ポート
手段に結合され、上記複数のビットを高位ビットと低位
ビットに分離し、低位ビットを第１出力端子に、高位ビ
ットを第２出力端子に運ぶデマルチプレクサ手段と、
（ｃ）上記デマルチプレクサ手段の第１出力端子に結合
され、該デマルチプレクサ手段からの低位ビットの受信
に応答して、ｋ＋１個の加算定数とｋ個の乗算定数とを
含む出力を生成する、重み・頂点アレイ手段と、（ｄ）
上記重み・頂点アレイ手段及びデマルチプレクサ手段の
第２出力端子に結合され、それぞれが対応する上記の加
算定数と高位ビットの算術和として計算されるｋ＋１個
のインデックス値を計算する、第１合算手段と、（ｅ）
上記第１合算手段に結合され、ｋ＋１個のインデックス
値の受信に応答して、ｋ個の関数値と１つの基点関数値
とからなる出力を生成する、３次元アレイ手段と、
（ｆ）上記３次元アレイ手段に結合され、それぞれが対
応する上記の関数値と基点関数値の差として計算される
ｋ個の第１の差値を計算する、減算手段と、（ｇ）上記
重み・頂点アレイ手段及び減算手段に結合され、それぞ
れが対応する上記差値と乗算定数の積として計算される
ｋ個の積を計算する、乗算手段と、（ｈ）上記３次元ア
レイ手段及び乗算手段に結合され、第２色空間内の関数
の値域出力値Ｖの近似を表す出力和を、ｋ個の積と基点
関数値の算術和として計算する、第２合算手段とを備え
る算術装置。
【請求項２】第１のｎ次元色空間内に定義域入力を有
し、第２のｍ次元色空間内に値域出力を有し、該定義域
入力が、ｋ＋１（ｋ≧ｎ）個の頂点を有する複数個のｎ
次元立体に分割され、各頂点がサンプル定義域入力点ベ
クトルｐを含み、各サンプル定義域入力点ベクトルｐが
第１色空間内に１組の座標を有する、関数Ｆの値ベクト
ルｖを近似するための算術装置であって、（ａ）第１色
空間内にある任意に選択した定義域入力点ベクトルｐに
対する１組の座標を表す複数のビットを入力する入力ポ
ート手段であって、該ベクトルｐが座標ｘ₁，
ｘ₂，．．．，ｘ_n（ただし、ｘ₁が第１色空間内の第１
色成分を表し、ｘ₂が第１色空間内の第２色成分を表
し、以下同様にして、ｘ_nが第１色空間内の第ｎ色成分
を表す）を有し、該複数のビットが高位ビットと低位ビ
ットを含む、入力ポート手段と、（ｂ）上記入力ポート
手段に結合され、上記複数のビットを高位ビットと低位
ビットに分離し、低位ビットを第１出力端子に、高位ビ
ットを第２出力端子に運ぶデマルチプレクサ手段と、
（ｃ）上記デマルチプレクサ手段の第１出力端子に結合
され、該デマルチプレクサ手段からの低位ビットの受信
に応答して、ｋ＋１個の加算定数とｋ個の乗算定数とを
含む出力を生成する、重み・頂点アレイ手段と、（ｄ）
上記重み・頂点アレイ手段及びデマルチプレクサ手段の
第２出力端子に結合され、それぞれが対応する上記の加
算定数と高位ビットの算術和として計算されるｋ＋１個
のインデックス値を計算する、第１合算手段と、（ｅ）
上記第１合算手段に結合され、ｋ＋１個のインデックス
値の受信に応答して、ｋ個の差値と１つの基点関数値と
からなる出力を生成する、３次元アレイ手段と、（ｆ）
上記重み・頂点アレイ手段及び減算手段に結合され、そ
れぞれが対応する上記差値と乗算定数の積として計算さ
れるｋ個の積を計算する、乗算手段と、（ｇ）上記３次
元アレイ手段及び乗算手段に結合され、第２色空間内の
関数の値域出力値Ｖの近似を表す出力和を、ｋ個の積と
基点関数値の算術和として計算する、第２合算手段とを
備える算術装置。
【請求項３】定義域入力が複数の直方体に分割され、各
直方体が２ⁿ個の頂点を含み、それらの頂点のうち１個
が基点関数値を持つ基点である、請求項１または２に記
載の算術装置。
【請求項４】定義域入力が複数の直方体に分割され、各
直方体が１個の基点と（２ⁿ−１）個の他の頂点とを含
む２ⁿ個の項を有するとともに、各直方体がさらに複数
の最小単体（ｋ＝ｎ）に分割され、該最小単体が直方体
内で、各単体の１つの頂点が、単体の到達距離の基点関
数値である該基点によって形成されるように配列され
る、請求項１または２に記載の算術装置。
【請求項５】定義域入力が複数の直方体に分割され、各
直方体がさらに複数の単体に再分割され、該単体が直方
体内で、各単体の１つの頂点が各単体の基点関数値であ
る直方体内部の１点によって形成されるように配列され
る、請求項１または２に記載の算術装置。
【請求項６】複数のビットが、第１色空間内にある任意
に選択した定義域入力点ベクトルｐに対する１組の座標
を表すｎ個の８ビット値を含み、各８ビット値が低位４
ビットと高位４ビット、または低位３ビットと高位５ビ
ット、または低位５ビットと高位３ビットを有する、請
求項５に記載の算術装置。
【請求項７】第１色空間が複数のｎ次元直方体に分割さ
れ、上記重み・頂点アレイ手段が、直方体のうち低位ビ
ットで指定される１つの直方体内にオフセットを有する
選択された定義域点に関連する重み・頂点情報セットを
含む、請求項６に記載の算術装置。