(57)【特許請求の範囲】
【請求項１】
画像の色空間上での画素値の分布であるデータ分布をクラスタリングして得られるクラスタ代表点と、色域境界表わす複数の点とを制御点として設定する手段と、
設定された制御点を母点として色空間を四面体からなる単体に単体分割する手段と、
前記色空間を複数のブロックにブロック分割する手段と、
単体分割された各単体を包含する直方体をそれぞれ発生させる直方体発生手段と、
ブロック分割された各ブロックについて、それぞれ接触する前記直方体が存在するか否かの粗い判定を行う手段と、
接触する直方体が存在すると判定されたブロックに、該直方体の元の単体が接触するか否かの正確な判定を行う手段と、
データ分布中の各点から順次選択される注目点が属するブロックを判定する手段と、
該ブロックに接触すると判定された前記単体の中から該注目点が属する単体を決定する単体決定手段と、
空間座標で記述されている各点を、それぞれが属する単体で規定される単体内部座標に変換する手段と、
任意の制御点を色空間上で移動させる手段と、
単体内部座標に変換された各点を元の空間座標に逆変換する手段と、を備えていることを特徴とする画像処理装置。
【請求項２】
請求項１において、
前記直方体発生手段が、単体に外接する直方体を発生する機能を有していることを特徴とする画像処理装置。
【請求項３】
請求項１において、
前記単体決定手段が、単体を規定するｎ次元の空間座標軸の全てに垂直な軸を有する（ｎ＋１）次元の空間上に、該ｎ次元空間に向かって凸形状の放物面を発生させ、該放物面上に各単体を持ち上げ変換して、各単体に対応する超平面を発生させ、且つ、注目点を通り、前記垂直軸に平行な補助線を発生させ、該補助線と、前記各単体に対応する超平面又はその延長面との交点を算出し、前記ｎ次元空間からの距離が最大の交点を有する超平面に対応する単体に、注目点が属すると決定する機能を有することを特徴とする画像処理装置。
【請求項４】
請求項１において、
前記単体決定手段が、単体を規定するｎ次元の空間座標系の全てに垂直な軸を有する（ｎ＋１）次元の空間上に、該ｎ次元空間に向かって凸形状の放物面を発生させ、該放物面上に各単体を持ち上げ変換して、各単体に対応する超平面を発生させ、且つ、注目点を通り、前記垂直軸に平行な補助線を発生させ、該補助線と、前記各単体に対応する超平面又はその延長面との交点を算出するとと共に、前記放物面の上に存在すると判定された交点を有する超平面に対応する単体に、注目点が属すると決定する機能を有することを特徴とする画像処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像処理装置、特にカラー画像の色調修正に適用して好適な画像処理装置に関する。
【０００２】
【従来の技術】
画像の特徴空間上で特徴的な分布を持つ点データ群を移動させることにより、その画像を処理することが行われている。その１つに、カラースキャナ等の色調修正装置で（ハイライト／シャドウ）・ポイント、グラデーション・カーブ、カラー・コレクション等のパラメータを用いて行う色調修正がある。以下、この色調修正の場合を中心に説明する。
【０００３】
カラー画像の入出力機器の普及に伴い、異なるメディア間の色のマッチングが取れない、色の修正が簡単にできない等の問題が指摘されるようになり、画像の色再現・色修正が重要な技術的課題として広く認識されるようになってきた。このような課題を解決するために、近年、印刷機用のＣＭＹＫやディスプレイ用のＲＧＢ等の特定のデバイスに依存した色空間ではなく、測色的に定義されたＣＩＥＬＡＢ（ＣＩＥ（国際照明委員会）により１９７６年に勧告されたＬ＊ａ＊ｂ＊均等色空間）のようなデバイス・インディペンデントな色空間に変換した上で、色相・明度・彩度を制御することにより色調修正を行う手法が種々提案されている。
【０００４】
【発明が解決しようとする課題】
しかしながら、形状等を表現する３次元空間を含む画像の特徴空間上でデータ分布を移動させて行う画像処理は、演算量が膨大で難しいという問題がある。とりわけ、特徴空間として色空間を用いてカラー画像の色調修正を行う従来の色調修正装置には以下の問題がある。
【０００５】
色調修正を行う場合、画素毎に修正演算が必要であることから演算量が膨大であるために、複雑なアルゴリズムの実装は難しい。又、画像データをデバイス・インデベンデントな色空間に一旦変換して色調整を行う場合でも、画像の色調に関する特徴をオペレータが目で見て判断し、色空間の制御を行っているために熟練が必要である。更に、印刷製版現場等で行う色調修正作業では、特定領域のみの色を変えたいという要求があるが、このような領域選択的な色調修正を行う場合には、領域指定を効率的に実行できない。
【０００６】
本出願人は、前記従来の問題点を解決するべく鋭意研究することにより、色空間上の画素値の分布を初めとして、画像データを記述する特徴空間上のデータの分布を移動させることにより、色調修正等の画像処理を少ない演算量で実行できるようにすると共に、色調修正の場合は熟練したオペレータでなくとも、領域選択的な色調修正をも容易に行うことができる技術として、画像の特徴空間上でのデータ分布の特徴を表わす点を含む複数の点を制御点として設定する手段と、設定された制御点を母点として単体分割する手段と、データ分布中の各点が、単体分割された単体のいずれに属するか判定する判定手段と、空間座標で記述されている各点を、それぞれが属する単体で規定される単体内部座標に変換する手段と、任意の制御点を特徴空間上で移動させる手段と、単体内部座標に変換された各点を元の空間座標に逆変換する手段と、を備えた画像処理装置を、特願平８−９２２７２において提案している。
【０００７】
この技術においては、例えば特徴空間が色空間である場合、画像データの色空間上での分布特徴に依存した表現に画像を一旦変換し、その分布の特徴を表わす制御点を元に単体分割を行い、画像データをこの分割により作成された単体で規定される単体内部座標に変換することにより、演算量を大幅に低減できると共に、オペレータは制御点を移動させるだけで、容易に色調修正ができるようになるため、熟練を要することなく、領域選択的な色調修正も簡単にできるようになる。
【０００８】
以下、図面を参照して、本出願人が提案している既出願の画像処理装置について、具体例をあげて詳細に説明する。
【０００９】
図１は、上記具体例の一つである色調修正装置の概略構成を示すブロック図である。この色調修正装置（画像処理装置）は、カラー写真等の原画からカラー画像を入力するためのスキャナ等の画像入力装置１０、該画像入力装置１０で入力した画像データを保持する画像保持用メモリ１２、入力した上記カラー画像を表示するディスプレイ等の画像表示装置１４、最終的に修正されたカラー画像を出力するための画像出力装置１６を備えている。
【００１０】
又、この色調修正装置は、上記画像保持用メモリ１２に保持されている画像データを読み出し、以下に詳述するカラー画像に対する色調修正を実行するために、色空間座標で記述されている画像データをドローネ網表現データに変換する変換部２０と、該変換部２０で作成したデータを保持するドローネ網表現データ保持部３０と、該データ保持部３０に保持されているドローネ網表現データを元の色空間座標データに逆変換するための画素値データ逆変換部４０と、後述する色域境界を表わす点列データ保持用メモリ４２と、色を修正する際の指示を入力するための修正指示部４４とを備えている。
【００１１】
又、上記変換部２０には、各機能については後に詳述するが、制御点リスト作成部２２、四面体リスト作成部２４、画素値データ変換部２６が含まれている。又、上記データ保持部３０には、画像特徴量データ保持用メモリ３２、画素値データ保持用メモリ３４が含まれている。
【００１２】
更に、要部詳細を図２に示すように、制御点リスト作成部２２は、クラスタリング処理部２２Ａと、点列データ組合せ部２２Ｂを、四面体リスト作成部２４は、ドローネ網構成部２４Ａと、四面体抽出部２４Ｂを、画像特徴量データ保持用メモリ３２は、制御点リスト３２Ａと、四面体リスト３２Ｂを、それぞれ有している。
【００１３】
この色調修正装置では、上記変換部２０、保持部３０、逆変換部４０で、以下に詳述する画像の色調修正が実行され、修正後の画像データが前記メモリ１２に出力され、保存されると共に、必要に応じて前記出力装置１６に出力されるようになっている。
【００１４】
この例では、カラー画像上の、例えば１つの物体である対象領域に存在する画素について、図３に示すような色空間上におけるバナナ形状の分布を求め、該分布を利用して色調修正を行う。
【００１５】
即ち、通常、画像は３次元的な広がりを持った物体に照明光を当て、その反射光を適切なレンズ系を通し、２次元平面にマッピングすることによって撮影が行われる。その際、ある１つの物体は同一の分光反射率、つまり同一の色を持っていて、照明光と物体表面の角度と視点の位置の関係により、その色には様々なグラデーションが生じている。
【００１６】
従って、カラー画像中で１つの物体に注目すると、その物体に対応する画像領域に属する画素値の色空間上における分布には、ある特徴的な傾向があることが知られている。即ち、物体が同一でも、影になり照明光が届かない部分は黒くなり、物体の表面に対して照明光が入射したときの入射角で決まる出射角に視線が近い物体表面の領域では、鏡面反射に近い状態となるため、照明光と同じ白になり、その中間の部分は物体表面が拡散反射をし、視線角度に対し反射率が分布を持つので、同一領域（同一物体）の画素は、上記図３に色空間がＬ＊ａ＊ｂ＊空間の場合を示すように、黒（シャドウ）から物体固有の色（物体色）を通り、白（ハイライト）へ至る曲線に沿った弧状のグラデーションで分布する傾向がある。ここで、Ｌ＊は明度、ａ＊ｂ＊平面内で、Ｌ＊軸からの距離は彩度、回転角は色相を表わす。
【００１７】
この例では、同一物体を表わす画素値の色空間上における分布のこのような特徴を利用し、該分布を色空間上で移動（変形）させることにより、その物体の色調を修正できるようにし、容易にカラー画像の色調修正を行えるようにした。
【００１８】
この例では、図４に、複数の物体が描写されているカラー画像について求めた色空間上の画素値の分布を示したように、各分布についてその特徴を表わす複数の点（●で示す）を制御点として、これを矢印で示す方向に移動させることにより、色調修正を行う。その際、制御点以外のデータについては適当な補間演算が必要であるが、補間を効率的に実行するためには、ランダムにばらまかれた点を何等かの手法により構造化する必要がある。そのために、制御点を母点として空間を単体に分割する単体分割を行う。ここで言う単体とは、空間がｎ次元の場合、ｎ＋１個のアフィン独立な点の凸包である。
【００１９】
ここでは、この単体分割の具体的な方法としてドローネ網の作成を採用する。このドローネ網は、計算幾何学における重要な概念であるが、これについて簡単に説明しておく。
【００２０】
平面上にｎ個の、（母点）Ｐi （ｘi ，ｙi ）（ｉ＝０，・・・，ｎ−１）が与えられたとき、点Ｐi の勢力圏：Ｖ（Ｐi ）を、次の（１）式で定義し、これを点Ｐi に対するボロノイ（Ｖoronoi）領域、又は、これに基づいた領域分割をボロノイ分割と呼ぶ。
【００２１】
【数１】
0003934206.tif 000002
ここで、ｄ（Ｐ，Ｑ）は点Ｐと点Ｑのユークリッド距離
【００２２】
点Ｐi と点Ｐj に対応するボロノイ領域が共有する境界を持つ、即ち隣接しているとき、それらの点を線分で結ぶことによってあるグラフを作ることができる。このグラフは平面の三角形（単体）分割になっており、ドローネ三角形分割あるいはドローネ網と呼ばれている。即ち、ドローネ網とは、各点の集まり（母点）に対してボロノイ分割したとき、隣接したボロノイ領域の母点同士を線で結んでできるグラフである。このドローネ網は、最小角最大の意味で最適な単体分割であり、しかも一意に決まるという特徴を有している。
【００２３】
図５に２次元表記したドローネ網の例を概念的に示したが、以上のことは３次元以上の空間においても同様に定義でき、ここで扱う色空間は３次元であるので、ドローネ単体分割は四面体分割となり、ドローネ網の構成単位（単体）は四面体となる。なお、このドローネ網については、伊理：“ｂｉｔ別冊計算幾何学と地理情報処理”共立出版（１９８６）、今井：“計算幾何学”，共立出版（１９９４）に詳説されている。
【００２４】
ここでは、データを適切に表現するために、図６（Ａ）及び（Ｂ）にそれぞれ示すようなクラスタ代表点及び色域境界を表わす点列データを母点（これは制御点となる）として、同図（Ｃ）に示すドローネ網を構成する。
【００２５】
即ち、この色調修正装置では、まず入力されたカラー画像データが画像保持用メモリ１２から前記図４に示したような色空間上での画素値の分布データとして制御点リスト作成部２２に入力される。この作成部２２では、クラスタリング処理部２２Ａで、分布の特徴を表わす点列データを、例えばＫ平均クラスタリング等の通常のクラスタリングによって得られる各クラスタの代表点（例えば、クラスタの重心）として選択する。このクラスタリング処理部２２Ａで選択された上記点列データは、点列データ組合せ部２２Ｂに入力され、ここで色域境界を表わす点列データ保持用メモリ４２から別途入力される色域境界を表わす点列データと組合わされ、実際の修正に使用する制御点として四面体リスト作成部２４に出力される。
【００２６】
上記点列データ保持用メモリ４２に保持されている色域境界を表わす点列データは、実データから予め抽出して作成されている。この点列データは、入力もしくは出力に想定しているデバイスの信号値（ＲＧＢ、ＣＭＹＫ等）と、Ｌ＊ａ＊ｂ＊色空間との対応を記述するＬＵＴ（ルック・アップ・テーブル）を作成しておくことにより、次のようにして抽出することができる。
【００２７】
上記ＬＵＴに登録されている各値をＬ＊ａ＊ｂ＊色空間上にプロットしてみると、図７に示すような点の集合が得られる。但し、実際には３次元空間であるが、ここでは便宜上２次元で表わしてある。この点の集合から、凸包を形成し、且つ凸包内部の点以外の白丸○で示す点だけを抽出すれば、それが色域境界を表わす点の集合（点列）となる。
【００２８】
具体例としては、ＣＭＹＫで表現されている原画像を使用して、ＣＭＹＫからＬ＊ａ＊ｂ＊への変換用ＬＵＴとして、ＣＭＹＫの各値が０、２５、５０、７５、１００（％）の２５％毎に等分割した５4 個の点のデータからなるＬＵＴを使用することができる。このＬＵＴに登録されているＬ＊ａ＊ｂ＊値は、印刷されたカラー・パッチを実際に測色した値である。
【００２９】
なお、上記のような実測に基づくＬＵＴでなくとも、解析的な式により両者の変換が定義されている場合であれば、その変換式に基づいてＬＵＴを作成しておくことで、同様に色域境界を表わす点列データを抽出できる。
【００３０】
前記点列データ組合せ部２２Ｂで点列データを組合せて作成した制御点は、四面体リスト作成部２４のドローネ網構成部２４Ａに入力され、該制御点に基づきドローネ網が作成される。これを概念的に示したのが前記図６（Ｃ）である。
【００３１】
上記のようにして抽出された点列データとクラスタ代表点とを合わせたものに対して、この図６（Ｃ）のようなドローネ網を構成することにより、色域境界の外には原理的に画素値は存在しないため、全ての画素をドローネ網の内側として表現できるようになる。
【００３２】
この図６（Ｃ）にも、便宜上２次元的に表記してあるが、実際の色空間は３次元であるため、ドローネ網により分割される単体は前記の如く四面体である。このように構成部２４Ａで作成されたドローネ網は、四面体抽出部２４Ｂに入力され、ここで該ドローネ網から四面体リストを抽出する。抽出された四面体リストは、前記点列データ組合せ部２２Ｂで作成された全制御点を特定した制御点リストと共に、画像の分布特徴を表わすデータ（以下、両者の組合せを画像特徴量データと呼ぶ）として、画像特徴量データ保持用メモリ３２に保持される。
【００３３】
更に、この画像特徴量データは、画素値データ変換部２６に入力され、ここで各画素の画素値を該画像特徴量データに基づく画素値データに変換し、それを画素値データ保持用メモリ３４に保持する。この画素値データは、四面体ＩＤと四面体内部座標として表現される。
【００３４】
このようにしてドローネ網による表現（以下、ドローネ網表現と呼ぶ）の画像データが得られる。図８は、このようなドローネ網表現された画像データを概念的に示したものである。このデータ構成について詳述すると、前述した如く、図８（Ａ）に示すようなドローネ網（前記図６（Ｃ）に当る）は、四面体の集まりとみなせることから、四面体のみを抽出し、同図（Ｂ）に示すように、［四面体リスト］＋［制御点リスト］としてこれを表現する。
【００３５】
図８（Ｃ）に、このデータ構造を示すように、制御点を表わすデータの内部構造はＬ＊ａ＊ｂ＊の座標値であり、これは３つの実数値からなる。制御点リストはドローネ網を構成する元となった制御点［０］〜［Ｎ−１］の集合からなるリストで、リストの要素は上記制御点データ（色空間座標値）である。一方、四面体を表わすデータの内部構造は各頂点に対応した制御点の制御点番号（制御点リスト中のアドレス）であり、これは０〜Ｎ−１の中の４つの整数値からなる。四面体リストはドローネ網を構成する四面体［０］〜［Ｍ−１］の集合からなるリストで、リストの要素は上記四面体データ（制御点番号）である。以上のようなデータ構造でドローネ網は完全に表現できる。
【００３６】
次に、各画素に対応した画素値の表現方法について説明する。図８（Ａ）に×印で示した画素値が含まれる四面体を同図（Ｄ）に２次元的に拡大して示したように、該画素値を表現するために、同図（Ｅ）に示すように、まず、その画素値の属している四面体の四面体番号（四面体リスト中のアドレス。以下四面体ＩＤと表記する）を各画素毎に記述しておく。更に、その画素値が四面体内部でどのような位置にあるかを四面体内部座標で記述する。これには、四面体の任意の頂点を原点とし、原点から延びる３本の辺の方向に基底ベクトルを取り、各辺の長さを１に正規化した斜交座標系での座標値として表現する。従って、×印の座標値は、（ｐ1 ，ｐ2 ，ｐ3 ）の四面体内部座標値で記述できる。
【００３７】
上記図８（Ｄ）には、この四面体座標値を便宜上２次元で表現してあり、底辺左頂点を原点とする座標で、×印は（ｐ1 ，ｐ2 ）で規定できることを表わしている。即ち、四面体内部にある任意の点の座標を、各頂点にある制御点の座標値で補間できることを意味する。
【００３８】
実際の演算では、この四面体内部座標値を実数データとして保持しておくのはデータ量の観点から、現実的ではないので、適当に量子化する必要がある。又、四面体ＩＤも、四面体の個数に応じた適切なビット数で記述するようにしなければならない。四面体ＩＤのビット数についてはドローネ網に含まれる四面体の数から、その対数をとることで簡単に計算することができる。四面体内部座標の量子化については、単純な線形量子化を基本とし、ｐ1 、ｐ2 、ｐ3 に存在する拘束条件を利用して、若干圧縮する方式を導入する。
【００３９】
具体的には以下のようにする。ｐ1 、ｐ2 、ｐ3 は０以上１以下の実数なので、次の（２）式により、それぞれの数値を（２s −１）倍し、それを四捨五入することでｓビットに量子化する。なお、（２）式右辺の左右端に記したＬ及び逆Ｌ字状の記号はその内側の計算値の小数点以下を切捨てることを意味する。
【００４０】
【数２】
0003934206.tif 000003
【００４１】
これで四面体内部座標は３s ビットで表される。ｐ1 、ｐ2 、ｐ3 は四面体内部の点の位置を決めるパラメータなので、次の（３）式のような拘束条件が存在する。
【００４２】
ｐ1 ＋ｐ2 ＋ｐ3 ≦１        …（３）
【００４３】
この条件から、量子化されたＰ1 、Ｐ2 、Ｐ3 では、それぞれの値の最上位ビットに含まれる１の個数は２以上にならない。２以上になると、Ｐ1 、Ｐ2 、Ｐ3 を足し合わせた結果の桁が一つ上がってしまうため条件を満たさなくなる。従って、最上位ビットに関する可能な状態は、（１）Ｐ1 の最上位ビットのみ１、（２）Ｐ2 の最上位ビットのみ１、（３）Ｐ3 の最上位ビットのみ１、（４）最上位ビットに１がない、の４通りしかなく、これは２ビットで表現できる。結局図９のように、最上位ビット情報Ｑ（２ｂｉｔ）とＰi （ｉ＝１，２，３）から最上位ビットを除いたものＰi ′（ｉ＝１，２，３）（各（s-1 ）ｂｉｔ）で、四面体内部座標は表現することができ、合計３s-1 ビットとなり、１ビット分節約できる。
【００４４】
ところで、四面体内部座標を記述する基底ベクトルが直交していないことから、一つ問題が発生する。（２）式で量子化すれば、直交座標系では、ユークリッド距離最小という意味で最適な量子化ができる。しかし、斜交座標系の座標値でデータの値が設定されている場合、（２）式で最適な量子化はできない。正確には四面体内部に存在する量子化による格子点全てに対して、距離計算をして判定すればよいのだが、実際にはそこまで必要ない。対象となる画素の回りの格子点６４（＝４3 ）点程度の距離計算で距離最小となる格子点を決めるようにすれば十分である。
【００４５】
実際に作成され、前記データ保持部３０に保持されている全体のデータ構造は、図１０に示されるように、大きく分けてドローネ網自体を記述する画像特徴量データと、各画素を記述する画素値マップの２つの部分からなる。画像特徴量データの部分は、制御点リストと四面体リストからなり、画像の色空間上での分布特徴を記述し、画素値マップは、四面体内部座標と四面体ＩＤからなる画素値データの集まりで、画像データの本体を形成する。
【００４６】
なお、図１０では、制御点リストが複数記載されているが、これは、色調修正が制御点を移動させることに当るため、色調修正した場合、その結果を制御点リストの異なるバージョンとして順次登録することもできるということを示している。保存の必要がなければ、元の制御点リストに上書きすればよい。
【００４７】
色空間座標で記述された画素値を上述したドローネ網表現へ変換するまでの順変換の処理手順を、図１１のフローチャートに示した。まず、色空間上でのクラスタリング（Ｋ平均クラスタリング）により、クラスタ代表点を抽出する（ステップＳ１）。次いで、このクラスタ代表点と色域境界を表わす点列データを合わせて制御点リストを作成する（ステップＳ２）。作成した制御点リストを元に、ドローネ網を構成する（ステップＳ３）。そのドローネ網から、四面体リストを作成する（ステップＳ４）。その後、各画素がどの四面体に属するか判定し、四面体内部座標と四面体ＩＤを得る（ステップＳ５）。こうして前記画素値マップが作成される。
【００４８】
上記ステップＳ５の最終ステップは、各画素がどの四面体に属するか判定しなければならないため、この判定処理は全画素が終了するまで繰り返し実行される。従って、上記順変換処理で問題になるのは、この判定に全ての四面体について内外判定をする全探索法を採用したのでは、探索すべき四面体の数が大となり、非常に演算コストがかかる。因みに、例えば制御点が２００点で四面体数は１０００個程度になり、これに対する帰属を１０２４×１０２４画素の画像について探索することになり膨大な処理時間がかかる。
【００４９】
そこで、前記画素値データ変換部２６で行う上記判定には、図１２のフローチャートに示す手順で行う、次に示すブロック分割による高速探索法を新たに導入する。この高速探索法では、図１３に便宜上２次元で示すように、例えば色空間を１６のブロック（実際の色空間では４3 個の立方体ブロック）に分割し、各ブロックに少なくとも一部が含まれる関係（接触関係）にある四面体のリスト（以下、ブロック接触四面体リストと呼ぶ）を作成し、それを予め登録しておく。各画素に対して、それがどのブロックに存在しているかは簡単な計算で分かるので、そのブロックに関係あるとして登録されている四面体のみを探索し、内外判定を行えばよいことになる。これにより、全探索法での処理時間を１０分の１程度に短縮することができた。
【００５０】
このように変換されたデータに対して色調修正を行う際、ポインティングデバイス等の修正指示部４４で制御点を変更するだけで、修正処理は終了する。即ち、制御点が変更された後のデータは、画素値データ逆変換部４０に入力され、ここで元の色空間の表現に逆変換され、画像保持用メモリ１２に出力される。
【００５１】
ここで実行される逆変換について以下に説明する。逆変換には、まず、量子化された四面体内部座標値から、次の（４）式のように元の実数値ｐi バーを得る。
【００５２】
【数３】
0003934206.tif 000004
【００５３】
次に、四面体ＩＤから四面体リスト及び制御点リストを参照し、今注目している画素が属している、四面体の頂点の座標値：ベクトルＶi （ｉ＝０、１、２、３、）を得る。これにより、元の画素値：ベクトルＸは、次の（５）式のように計算することができる。これを全画素に対して実行する。ここでは、Ｖ0 が四面体の原点であるとしている。
【００５４】
【数４】
0003934206.tif 000005
【００５５】
この逆変換は各画素毎に９回の乗算で実行できるため高速である。ディスプレイ上で修正結果を表示しながらのオペレーションを考えると、逆変換が高速であることは、ほとんど必須条件であるが、この演算方法で実現できる。
【００５６】
ここで実行される上記逆変換を、前記図８（Ｄ）に相当する２次元表記した四面体内部座標を示す図１４に示す概念図を元に、より具体的に説明する。
【００５７】
いま、上記内部座標が頂点Ａを原点とする三角形ＡＢＣで表わされ、×印で示した注目画素の修正前の内部座標値が（ｐ1 ，ｐ2 ）であったとする。色調修正の計算を容易にするために、色空間Ｌ＊ａ＊ｂ＊における各頂点（制御点）Ａ、Ｂ、Ｃの座標値をベクトル表記する。図中矢印はベクトルを表わしている。
【００５８】
点Ａ、Ｂ、Ｃの位置ベクトルを、それぞれベクトルａ、ｂ、ｃとすると、×印の座標を表わすベクトルｘは、次の（６）式で与えられる。×印の座標値は、四面体を規定する４つの制御点の座標値で簡単に補間演算できる。但し、図示しない頂点Ｄの位置ベクトルをｄとし、辺ＡＤに関する内部座標値をｐ3 として３次元表記してある。
【００５９】
【数５】
0003934206.tif 000006
【００６０】
そして、色調修正を行う際に制御点を変更し、Ｂ点をＢ′に、Ｃ点をＣ′に移動させたとすると、変更後の×印の座標であるベクトルｘ′は、次の（７）式で与えられる。但し、Ａ点もＡ′点（図示せず）に変更した場合も想定し、ベクトルａ′として一般化してある。
【００６１】
【数６】
0003934206.tif 000007
この式は、前記（５）式に相当し、各項は次の関係にある。
【００６２】
【数７】
0003934206.tif 000008
上記（７）式から分かるように色調修正時には、四面体内部座標値ｐ1 、ｐ2 、ｐ3 は変更する必要がない。又、ベクトルｕ′、ｖ′、ｗ′は、前記（６）式と同様に、Ｌ＊ａ＊ｂ＊で記述された変更後の制御点Ｂ′、Ｃ′、Ｄ′の各座標値から原点に当る制御点Ａ′の座標値を引くだけで簡単に求めることができる。
【００６３】
前記逆変換部４０で実行される逆変換は、画素毎の四面体ＩＤと四面体内部座標値から、四面体リスト及び制御点リストを参照しながら、上記（７）式で、ベクトルａ′、ｕ′、ｖ′、ｗ′にＬ＊ａ＊ｂ＊の具体的な値を入れることにより実行されるが、前記（５）式のところで説明した如く、この処理は１画素当り数回の積和演算のみで済むので、十分高速で実行できる。
【００６４】
従って、色調修正を行う場合は、制御点リストを変更するだけで、上記（７）式により、任意画素についての画素値の補間演算が実行できるため、四面体リストも、画素値データも全く変える必要はない。従来のほとんどの色調修正アルゴリズムは、画素データそのものを変えるような処理を行っていたため、複雑な色の処理を実行しようとすると、処理が遅くなるという欠点があったが、この色調修正装置によれば、どんな複雑な色の処理でも、制御点の移動だけで済むため、幅の広い処理が高速でできるという利点がある。
【００６５】
以上詳述したこの色調修正装置では、オペレータは、次のようにして色調修正の作業を行うことができる。図１５には、この作業の特徴を概念的に示した。
【００６６】
（１）色修正に先立ち、画像データをドローネ網表現に変換しておく。
（２）ドローネ網表現のデータをロードし、ディスプレイ上に表示する。
（３）特定色領域のみを修正したい場合は、適当なユーザ・インターフェイスにより領域指定を行う。即ち、移動させたい制御点を選択する。全体を修正したい場合は、全制御点を選択しておく。
（４）選択された各制御点に対して、それぞれどれだけ移動させるかを指定し、移動させる。
（５）新しい制御点を元にディスプレイ上に修正結果を表示する。結果が良ければ次のステップへ進む。
（６）新しい制御点リストを新しいバージョンとして付け加え、セーブする。
（７）必要があれば、通常の画像表現へ逆変換する。
【００６７】
以上のように、この色調修正装置によれば、色修正を実行することで、ドローネ網表現での画素値データを全く変えることなく、制御点の移動と通常の画像表現への逆変換だけで色調修正ができるようになる。
【００６８】
そのため、複雑な色調修正を行いたい場合でも、複雑な処理を画素数分繰り返す必要はなく、制御点に対してのみ複雑な処理を実行するだけでよい。又、修正結果を制御点リストの異なるバージョンとして記述しておくことで、修正の履歴を保存しておくことができる。更に、画素毎にどの四面体に属しているかの情報が四面体ＩＤとして記述されているので、これを利用して領域指定の処理を効率的に実行できる。
【００６９】
以上、本出願人が特願平８−９２２７２に既に提案してあるドローネ網を利用した画像処理技術について具体的に詳述したとおり、上述したドローネ網を用いた色調修正法では、どんな複雑な処理でも制御点の移動だけで済むため、幅の広い色の修正が高速でできるというメリットがある。
【００７０】
しかしながら、本発明者は、更なる高速処理を実現するべく鋭意検討した結果、前記図１１に示したフローチャートのステップ５で、各画素（注目画素）がどの四面体に属するかの判定を行う、前述したブロック分割による高速探索法には、ドローネ網を用いた表現に画像を変換する演算が、未だ十分に高速でないという問題がある。
【００７１】
本発明は、前記新たな問題点を解決するべくなされたもので、前記ブロック分割による高速探索法の更なる高速化を図ることにより、画像処理を一段と高速に行うことができる技術を提供することを課題とする。
【００７２】
【課題を解決するための手段】
本発明は、画像処理装置を、画像の色空間上での画素値の分布であるデータ分布をクラスタリングして得られるクラスタ代表点と、色域境界表わす複数の点とを制御点として設定する手段と、設定された制御点を母点として色空間を四面体からなる単体に単体分割する手段と、前記色空間を複数のブロックにブロック分割する手段と、単体分割された各単体を包含する直方体をそれぞれ発生させる直方体発生手段と、ブロック分割された各ブロックについて、それぞれ接触する前記直方体が存在するか否かの粗い判定を行う手段と、接触する直方体が存在すると判定されたブロックに、該直方体の元の単体が接触するか否かの正確な判定を行う手段と、データ分布中の各点から順次選択される注目点が属するブロックを判定する手段と、該ブロックに接触すると判定された前記単体の中から該注目点が属する単体を決定する単体決定手段と、空間座標で記述されている各点を、それぞれが属する単体で規定される単体内部座標に変換する手段と、任意の制御点を色空間上で移動させる手段と、単体内部座標に変換された各点を元の空間座標に逆変換する手段と、を備えた構成とすることにより、前記課題を解決したものである。
【００７３】
【発明の実施の形態】
以下、図面を参照して、本発明の実施の形態について詳細に説明する。
【００７４】
本発明に係る第１実施形態の色調修正装置（画像処理装置）は、前記ドローネ網表現データ変換部２０において、前記図１２のフローチャートに示したステップ１１のブロック接触四面体リストの作成と、ステップ１２の四面体ＩＤの取得の処理を、以下のような手順で実行できるようにした以外は、その基本的な構成は前記図１に示したものと実質的に同一であり、又、処理機能も前述したものと実質的に同一である。
【００７５】
本実施形態では、前記変換部２０が、前記ステップ１１の処理を実行するために、単体（四面体）分割された各単体を包含する直方体をそれぞれ発生させる直方体発生手段と、ブロック分割された各ブロックについて、それぞれ接触する前記直方体が存在するか否かの粗い判定を行う手段と、接触する直方体が存在すると判定されたブロックに、該直方体の元の単体が接触するか否かの正確な判定を行う手段と、データ分布中の各点から順次選択される注目点が属するブロックを判定する手段と、該ブロックに接触すると判定された前記単体の中から該注目点が属する単体を決定する単体決定手段と、を備え、それぞれが機能するようになっている。
【００７６】
即ち、ここでは、既出願のように、四面体の少なくとも一部がブロックに含まれるという正確な接触判定を、処理対象となる全ての四面体と直方体ブロックとの間で行うのではなく、まず粗い接触判定により、対象ブロックに接触する可能性のある四面体の候補を絞り、候補として残ったものについてのみ、正確な接触判定を行うようにして、各ブロックに接触する四面体リストの作成の高速化を図るようにしている。
【００７７】
今、この粗い接触判定について、図１６を用いて概念的に説明する。この図においては、理解を容易にするために便宜上二次元表記してあり、四角形は直方体を、三角形は四面体を意味し、直方体（あ）は分割されたブロックを、直方体（う）は、前記直方体発生手段によって発生される四面体（い）に外接する（四面体（い）を包含する）直方体を表わしている。但し、実際の対象が２次元である場合は、上記直方体は長方形となる。
【００７８】
粗い接触判定を行うに当たっては、直方体（あ）と四面体（い）の接触判定を行う代わりに、四面体に外接し、且つ、その辺や面が直方体の各面や辺に平行になるような直方体（う）を考え、直方体同士の接触判定を行う。このように、各直方体の辺や面が空間の各軸に平行になっている場合、条件判断を数回（三次元の場合６回）施すことにより判定できる。
【００７９】
このようにすることにより、極端に離れている四面体と直方体（ブロック）に対しては、四面体を簡単な演算により接触候補から落とすことができる。
【００８０】
その後、外接直方体が接触して候補に残った四面体に対し、直方体との正確な接触判定を行うことにより、該判定処理を高速化することができる。この正確な接触判定は以下のように行う。
【００８１】
図１７（前記図１６に示したような直方体が外接する前の状態に相当する）に示すような直方体（あ）と四面体（い）において、直方体と四面体のそれぞれを構成する面全てに対し、その面が両者を分離する面になっているかどうかを判定する。一つでも分離する面があれば、直方体と四面体は分離しており、そうでない場合は接触していると判定できる（図では面Ａが両者を分離する面となっている）。
【００８２】
分離しているかどうかは、点と面との位置関係を判定するための基本的な演算である上下判定演算を繰り返すことで判定することができる。この上下判定演算は以下のように行う。
【００８３】
面の法線ベクトルを矢印付ｎとすると、面の式は、該面を規定する位置ベクトルを矢印付ｘとして、
【００８４】
【数８】
0003934206.tif 000009
のように内積で表わされる。このとき、法線ベクトルｎの方向を、この面の上方向と定義しておき、ある点の位置ベクトルを矢印付ｐとすると、
【数９】
0003934206.tif 000010
を満たすとき、点ｐは上記面よりも上にあり、その逆の場合、下にあると判定することができる。
【００８５】
以上の上下判定演算は、１つの面について乗算３回、加算２回、条件判断１回の演算で実行できる。従って、直方体と四面体の正確な接触判定は６面×４点＋４面×８点＝５６で、最大５６回の上下判定が必要となる。
【００８６】
以上の判定原理に基づいて、図１８、１９のフローチャートに従って処理することにより、全ての四面体に対して、ブロック接触四面体リストを作成することができる。
【００８７】
即ち、全ての四面体について外接直方体を作成し、そのデータをリストとして登録する（ステップ２１〜２３）。
【００８８】
次に、最初の対象とする初期ブロックを設定し（ステップ２５）、最初に判定する四面体を設定し（ステップ２６）、該四面体が上記初期ブロックに接触しているか否か判定する（ステップ２７）。
【００８９】
この判定処理は、図１９のフローチャートに従い、対象のブロックと四面体に対応した外接直方体との接触判定を行い、接触している場合には（ステップ２８、２９）、該ブロックと四面体との正確な接触判定を行い、接触している場合には（ステップ３０、３１）、その四面体のＩＤをブロック接触四面体リストとして登録する（ステップ３２）。
【００９０】
以上の処理を、全四面体について行う（ステップ３３、３４）。更に、以上の処理を、全ブロックについて行う（ステップ３５、３６）。このようにすることにより、全ブロックについて、それぞれ接触している四面体を高速に決定することができる。
【００９１】
又、本実施形態では、前記図１２のステップ１２で実行する、各画素がどの四面体に属しているかの判定（四面体ＩＤの取得）の処理を、前記図１の変換部２０が備えている前記単体決定手段が有する、単体を規定するｎ次元の空間座標軸の全てに垂直な軸を有する（ｎ＋１）次元の空間上に、該ｎ次元空間に向かって凸形状の放物面（超放物面）を発生させ、該放物面上に各単体を持ち上げ変換して、各単体に対応する超平面を発生させ、且つ、注目点を通り、前記垂直軸に平行な補助線を発生させ、該補助線と、前記各単体に対応する超平面又はその延長面との交点を算出し、前記ｎ次元空間からの距離が最大の交点を有する超平面に対応する単体に注目点が属すると決定する機能を用いて行うようになっている。
【００９２】
即ち、ここでは、既出願のように、ある画素に対応した点が四面体の内にあるか外にあるかを、単純な内外判定により行うのではなく、ドローネ網のある性質を利用し高速に点位置決定問題を解くようにしている。
【００９３】
単純な内外判定では、四面体を構成する４つの面のそれぞれに対し、注目点（画素）について上下判定演算を行い、該点の内外を判定するため、乗算１２回、加算９回、条件判断４回の演算が必要であったが、本発明では、ドローネ網の性質を利用し、この演算量を削減するようにしている。
【００９４】
以下にその方法について詳細に説明するが、その前に、本発明で利用しているドローネ網の性質について説明しておく。今、簡単のため、平面上のドローネ網について考える（三次元以上の場合についても以下の議論はそのまま成り立つ）。
【００９５】
図２０に示したように、ｘｙ平面上に点（●印）の集まり（Ｐn （ｎ＝０，１，…））があったとする。この平面に垂直な軸ｚを新たに考え、同図に示すような放物面に、該表面上の●印の点を持ち上げて張り付けることにより、（Ｑn （ｎ＝０，１，…））に変換する。このような変換（以下、持ち上げ変換ともいう）によってできた点の集まりに対して凸包を構成する。この凸包の下側境界（ｘｙ平面から（つまり下から）凸包を見上げたときに見える凸包の部分）のみに注目して、それをもう一度、ｘｙ平面に射影したものが、丁度ｘｙ平面上での●印の点に対するドローネ網となっている。以上のことは、三次元以上の空間にも容易に拡張することができる。
【００９６】
このように、ｎ次元空間上でのドローネ網と（ｎ＋１）次元空間上での凸包には、点の持ち上げ変換を通して密接な関係が存在している。即ち、ｎ次元空間上でのドローネ網は、（ｎ＋１）次元空間上での凸包（の一部）のｎ次元空間への射影に等しい。
【００９７】
この性質をうまく利用し、領域がドローネ網によって分割されている場合の点位置決定問題を高速に解くことができる。これを、図２１を用いて詳しく説明する。
【００９８】
今、簡単のため、三次元空間（ｘ，ｙ，ｚ軸によって張られる）を１次元として表わし、それに垂直な軸ｗを考え、
ｗ＝ｘ2 ＋ｙ2 ＋ｚ2         …（１０）
なる放物面（正確には超放物面）を考える。これは、丁度上記図２０を横から見ていることに相当する。そして、ｘｙｚ空間上の点は持ち上げ変換によってこの放物面に張り付けられ、凸包が構成されているものとする。
【００９９】
このｘｙｚ空間には、四面体Ａ、Ｂ、Ｃという３つの四面体が存在している。今、×印で示されている注目点ｖがどの四面体に属するかという問題を考える。
【０１００】
これを解くために、上記注目点ｖからｗ軸に平行な補助線ｘを引いてみる。この補助線ｘと凸包を構成する各四面体Ａ、Ｂ、Ｃに対応する超平面Ａ、Ｂ、Ｃ又はその延長面は一点で交わり、ａ、ｂ、ｃで表わすそれぞれの交点が得られる。
【０１０１】
上記図２１から分かるように、この交点の中でｘ、ｙ、ｚ軸で規定される３次元空間を規準にして最も高い、即ち交点のｗ座標値が最大の点に対応した四面体に、×印の注目点は存在している。つまり、どの四面体に属しているかという問題は、注目点と四面体の関係で決まるある値（交点のｗ座標値）の最大値問題を解くことに等しい。
【０１０２】
交点のｗ座標値の具体的な計算法について、以下に説明する。上記図２１の放物面上の凸包を構成する各面の四次元空間上での法線ベクトルをｎとする。三次元空間上の二次元平面の法線ベクトルは、ベクトルの外積により容易に求めることができるが、四次元空間上の超平面の法線ベクトルの求め方は、それ程簡単でないので、便宜上後述する。
【０１０３】
このようにして求まった法線ベクトルｎを用いると、超平面の式は、
【数１０】
0003934206.tif 000011
となる。
【０１０４】
上式では法線ベクトルの絶対値が１に正規化されているが、後の都合のため、第４成分の値（図２１ではｗ軸成分に相当）が１になるように正規化しておく。このように正規化されたベクトルを矢印付ａとすると、超平面の式は、
【数１１】
0003934206.tif 000012
となる。ここで、ベクトルａ＝（ａx ，ａy ，ａz ，１）である。
【０１０５】
この超平面と前記図２１で引いた補助線ｘとの交点のｗ座標値は、注目点ｖのｘｙｚ空間上での座標値を（ｖx ，ｖy ，ｖz ）とすると、
ａx ｖx ＋ａy ｖy ＋ａz ｖz ＋ｗ＝β
ｗ＝β−ａx ｖx −ａy ｖy −ａz ｖz       …（１３）
のように、３回の乗算と３回の加算（減算）によって求めることができる。この演算を四面体の数分繰り返し、ｗの最大値を求める。そして、注目点が属するものとして、ｗが最大となる超平面に対応した四面体を求めればよい。
【０１０６】
ここで、前記四次元空間上の超平面の法線ベクトルの求め方について説明する。
【０１０７】
まず、簡単な三次元の場合について考えてみる。今、三次元空間上に位置ベクトルで表わされた点、矢印付ｐ0 ，矢印付ｐ1 ，矢印付ｐ2 があるとする。これらを通る平面の法線ベクトル矢印付ｎは、
【数１２】
0003934206.tif 000013
とし、
【数１３】
0003934206.tif 000014
のようにして求まる。ここで、×はベクトルの外積を表わす。
【０１０８】
四次元への拡張は、このベクトルの外積を四次元に拡張すればよい。それを容易にするため、三次元の外積がテンソル代数の記法を用いてどのように表わされるか見てみる。外積の定義は、次のようである。
【０１０９】
【数１４】
0003934206.tif 000015
これをテンソル代数的な記法で表わしてみると、
Ｃi ＝εijk Ａj Ｂk （i,j,k ＝０，１，２）      …（１７）
となる。ここで、εijk は３階の完全反対称テンソルと呼ばれ、
ε012 ＝１
εjik ＝−εijk 
εikj ＝−εijk               …（１８）
で定義される。四次元のベクトルの外積は、これの拡張として、
Ｄi ＝εijklＡj Ｂk Ｃl （i,j,k,l ＝０，１，２，３）  …（１９）
と定義される。ここで、εijklは４階の完全反対称テンソルと呼ばれ、上記（１８）式と同様に定義される。
【０１１０】
即ち、全ての要素は、０，１，−１のいずれかで、２つの添字の任意の互換により符号が逆転する４階のテンソルである。このとき、ベクトルＤはベクトルＡ、Ｂ、Ｃのどれとも直交していることは、簡単に証明できる。
【０１１１】
さて、四次元空間上の三次元超平面の法線ベクトルは、今、四次元空間上に点、矢印付ｐ0 ，矢印付ｐ1 ，矢印付ｐ2 ，矢印付ｐ3 があったとする。この点を通る超平面の法線ベクトルｎは、
【数１５】
0003934206.tif 000016
とすると、
Ｎi ＝εijklv1 j v2 k v3 l
【数１６】
0003934206.tif 000017
と求められる。
【０１１２】
本実施形態では、注目点が属する四面体を決定する具体的なアルゴリズムとして、前記（１３）式を用いてその最大値を求める考え方をそのまま実現している。その処理手順を、図２２フローチャートに示す。これは、対象となる全四面体について、ｗ座標値を計算し最大値を求める手法で、上述のような考え方をそのまま適用させた方式である。
【０１１３】
先ず、全ての四面体について、「持ち上げ」変換による四面体に対応した超平面の法線ベクトルと定数データを作成し、リストとして保持する（ステップ４１〜４５）。
【０１１４】
次いで、画素（注目点）が属するブロックを選択し、該ブロックに接触している全ての四面体について、該画素の色空間上での位置から決まる補助直線ｘと、四面体に対応した超平面（又はその延長面）との交点のｗ座標値を計算する（ステップ４６〜５１）。
【０１１５】
次いで、ｗ座標値が最大の四面体のＩＤを前記画素の四面体ＩＤとし、その四面体内部座標を計算する（ステップ５１、５２）。以上のステップ４６〜５２の処理を全ての画素について実行する（ステップ５３、５４）。
【０１１６】
前述した既出願の方法では、１回の判定に従来では１２回の乗算が必要であったのに対し、本実施形態では１回のｗ座標値の計算に３回の乗算で済むため高速になる。実際に、既出願法よりも高速になることが確認されている。但し、既出願法と比較し、一つ無駄な演算をしている部分があり、これを削減することで更に高速化することが可能となる。
【０１１７】
次に、第２実施形態について説明する。
【０１１８】
前記第１実施形態では、全四面体について計算した後でなければ答えが求まらないが、既出願のブロック分割法の内外判定では、「内」と判定されればそこでループを抜けるようにできるため、全四面体について必ずしも計算する必要はない。
【０１１９】
そこで、この第２実施形態では、既出願の良い点と第１実施形態の手法をうまく組み合わせて、更に高速化できるようにした。その処理手順を図２３のフローチャートに示す。
【０１２０】
本実施形態では、前記図２１に示したように、超平面と補助線との交点のｗ座標値の最大値は、「持上げ」変換により生成された仮想的な超放物面よりも上に存在する、という性質を利用する。
【０１２１】
前記第１実施形態との違いを、ステップ６７〜７３に従って説明する。まず、補助線ｘが与えられたとき、それと交わる放物面上の点のｗ座標値を求めておく。次に、補助線と四面体に対応した超平面との交点のｗ座標値を求めていき、それが放物面よりも上にある場合のみ、内外判定を行い、内にあればループを抜け、答えを返すようにする。このようにすることにより、第１実施形態の場合と比べ、更に高速化することができる。
【０１２２】
以上の説明では、画像の特徴空間がＬ＊ａ＊ｂ＊色空間である場合について説明したが、これに限られない。
【０１２３】
例えば、ＲＧＢ色空間であってもよく、これを採用した場合について説明する。
【０１２４】
前記図１１の第２ステップで、「色域境界を表わす点」は、処理開始前に予め求めておくが、この求め方がＬ＊ａ＊ｂ＊のようなデバイスに依存しない色空間と、ＲＧＢのようなデバイスに依存する色空間とでは異なる。
【０１２５】
Ｌ＊ａ＊ｂ＊の場合には、ＣＭＹＫ−Ｌ＊ａ＊ｂ＊の変換を記述するＬＵＴに登録されている。各Ｌ＊ａ＊ｂ＊値の系列を三次元の色空間上にプロットし、その点を元に作成された凸包を構成する点のみを抽出することで得るようにしていた。
【０１２６】
しかし、ＲＧＢのようなデバイスに依存した色空間では、この処理は単純化される。Ｒ、Ｇ、Ｂの各チャネルからの信号には最小値、最大値が存在していて、その範囲での信号の組がそのまま色を表わすので、この色空間上での色域は、ちょうど図２４に示すような立方体（あるいは直方体）となる。従って、色域の境界を表わす点列データは、立方体（あるいは直方体）を構成する各面上の点を適当にサンプリングすることで、図２４の●印の点のように得られる。その他の処理は、Ｌ＊ａ＊ｂ＊で表わされている部分をそのままＲＧＢの値に置き換えればよい。
【０１２７】
前記Ｌ＊ａ＊ｂ＊色空間を採用する場合は、
・制御点の移動と人間の色知覚との対応をつけ易い、
・デバイスに依存しない色修正が可能である、
という利点が挙げられるが、上記ＲＧＢ色空間を採用する場合は、
・色域境界の計算が単純である、
・色変換の必要がない
という利点が挙げられる。
【０１２８】
以上、本発明を具体的に説明したが、本発明は、前記実施の形態に示したものに限られるものでなく、その要旨を逸脱しない範囲で種々変更可能である。
【０１３１】
例えば、デバイスに依存しない色空間もＬ＊ａ＊ｂ＊に限定されない。又、デバイスに依存する色空間もＲＧＢに限定されない。更に、単体分割もドローネ網の作成に限定されない。
【０１３２】
【発明の効果】
以上説明したとおり、本発明によれば、色空間上の画素値の分布を移動させることにより、色調修正等の画像処理を少ない演算量で実行することができる。又、カラー画像の色調修正は、熟練したオペレータでなくとも、しかも領域選択的な色調修正をも容易且つ迅速に行うことができる。
【図面の簡単な説明】
【図１】本発明に係る色調修正装置の概略構成を示すブロック図
【図２】上記色調修正装置の要部詳細を示すブロック図
【図３】色空間上の画素値の分布特徴を示す説明図
【図４】複数の物体に関する色空間上の画素値の分布特徴を示す説明図
【図５】ドローネ網を概念的に示す線図
【図６】色域境界を表わす点列データの抽出を示す線図
【図７】色空間上で構成するドローネ網を概念的に示す説明図
【図８】ドローネ網表現された画像データを概念的に示す説明図
【図９】四面体内部座標のデータ圧縮を示す説明図
【図１０】ドローネ網表現された画像データの構造を概念的に示す説明図
【図１１】色空間上の画素値をドローネ網表現に変換する手順を示すフローチャート
【図１２】画素が属している四面体の判定手順を示すフローチャート
【図１３】画素値の属する四面体の高速探索法を説明する線図
【図１４】ドローネ網表現から色空間座標への逆変換の演算を説明する線図
【図１５】色修正を概念的に示した説明図
【図１６】粗い接触判定を概念的に示した説明図
【図１７】正確な接触判定を概念的に示した説明図
【図１８】ブロック接触四面体リストの作成手順を示すフローチャート
【図１９】ブロック接触四面体リスト作成手順の一部詳細を示すフローチャート
【図２０】ドローネ網と凸包との関係を概念的に示した説明図
【図２１】ドローネ網の性質を利用した点位置決定法を示す説明図
【図２２】第１実施形態による点位置決定手順を示すフローチャート
【図２３】第２実施形態による点位置決定手順を示すフローチャート
【図２４】ＲＧＢ色空間での色域の境界を表わす点列の例を示す線図
【符号の説明】
１０…画像入力装置
１２…画像保持用メモリ
１４…画像表示装置
１６…画像出力装置
２０…ドローネ網表現データへの変換部
２２…制御点リスト作成部
２２Ａ…クラスタリング処理部
２２Ｂ…点列データ組合せ部
２４…四面体リスト作成部
２４Ａ…ドローネ網構成部
２４Ｂ…四面体抽出部
２６…画素値データ変換部
３０…ドローネ網表現データ保持部
３２…画像特徴量データ保持用メモリ
３２Ａ…制御点リスト
３２Ｂ…四面体リスト
３４…画素値データ保持用メモリ
４０…画素値データ逆変換部
４２…色域境界を表わす点列データ保持用メモリ
４４…修正指示部
【図１】
0003934206.tif 000018
【図２】
0003934206.tif 000019
【図３】
0003934206.tif 000020
【図４】
0003934206.tif 000021
【図５】
0003934206.tif 000022
【図６】
0003934206.tif 000023
【図７】
0003934206.tif 000024
【図８】
0003934206.tif 000025
【図９】
0003934206.tif 000026
【図１０】
0003934206.tif 000027
【図１１】
0003934206.tif 000028
【図１２】
0003934206.tif 000029
【図１３】
0003934206.tif 000030
【図１４】
0003934206.tif 000031
【図１５】
0003934206.tif 000032
【図１６】
0003934206.tif 000033
【図１７】
0003934206.tif 000034
【図１８】
0003934206.tif 000035
【図１９】
0003934206.tif 000036
【図２０】
0003934206.tif 000037
【図２１】
0003934206.tif 000038
【図２２】
0003934206.tif 000039
【図２３】
0003934206.tif 000040
【図２４】
0003934206.tif 000041