JPH04370881A

JPH04370881A - カラー画像領域管理装置及びカラー画像領域管理方法並びにカラー画像領域検索方法

Info

Publication number: JPH04370881A
Application number: JP3174749A
Authority: JP
Inventors: Jung Kuk Hong; 洪　政国; Hiroyasu Takahashi; 高橋　弘晏; Machiko Sato; 真知子佐藤
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1991-06-20
Filing date: 1991-06-20
Publication date: 1992-12-24
Anticipated expiration: 2009-11-30
Also published as: JPH0697459B2

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は一般には画像処理システ
ムに関し、さらに詳しく言えば、カラー画像を管理する
ための方法及びシステム並びにこのようにして管理され
たカラー画像の領域を検索するための方法及びシステム
に関する。

【０００２】

【従来の技術】カラー画像処理の分野においては、対象
物の切り出しや色変更など、ある対象領域のみに処理を
施したい場合がある。こうした要求は、特に、パーソナ
ルコンピュータやワークステーションなどで急速に製品
化が進んでいるカラー画像編集システムやペインティン
グシステムで顕著である。これらは、必要とする部分の
みを処理すればよいという点で、主として画像全体を処
理の対象としているリモートセンシングや医療システム
における画像処理とは大きく異なる。このような部分的
処理においては、必要な領域を迅速に検出できること及
びその領域について出来る限り無駄なく読み書きできる
ことが処理効率やメモリ効率の面から肝要となる。した
がって、データ構造もこのような部分的処理に適したも
のであることが必要である。これは、特に、静止画像中
に対象領域が多数点在する場合や動画像のように多数の
連続したフレームを処理する場合などにおいてシステム
を実用化する際に必須となる。

【０００３】カラー画像データは、通常、二次元配列に
おける画素ごとの三原色データとして記憶される。この
場合、画素の値は基本的には位置の関数として記述され
るため、処理の対象領域を検出するためには、画像全体
を読みだし、画素ごとに条件を満たすかどうかを調べる
必要がある。

【０００４】ところで、図形情報や画像データを扱う有
効な方法として、木構造やピラミッド構造がある。例え
ば、二値画像のデータを木構造で表現すると、情報が密
に存在するところほど領域が細かく分割されるため、画
像データを効率よく管理することが可能となり、指定さ
れた位置に白画素があるか黒画素あるかを高速に検索す
ることができる。しかしながら、逆に、目的となる領域
、例えば白画素の領域を検索したいという場合は、結局
、最下位レベルのノードをすべて調べなければならない
。情報が非常に密であれば、場合によっては、最下位レ
ベルが画素レベルになることもある。いずれにしても、
最下位レベルのノードをすべて調べなければならないと
いう点で、検索の効率が落ちる。木構造は多値画像デー
タにも応用できるが、この点では同様である。

【０００５】一方、ピラミッド構造は、解像度の低い画
像に対して処理を行い次に解像度の高い画像を処理する
場合には有効である。しかしながら、解像度の低い画像
では当然漏れている情報があるため、例えば白画素の領
域をすべて検索したいという処理には不向きである。

【０００６】色画像データの色の処理に関する従来技術
として、特定された対象領域におけるエッジの判定に関
する技術を開示する特開昭６３−１８２７８６号、対象
領域において分割を行うため代表色を選ぶ技術を開示す
る特開昭６３−１８４４７５号、色変換や明度変換さら
にデータの圧縮率を上げるためにＲＧＢ表色系以外の表
色系を利用する技術を開示する特開昭６３−１８５１６
３号がある。しかしながら、これらの従来技術は、指定
された色を有する領域を検索するのに適したものではな
く、また、そのためのデータ管理方法を開示するもので
もない。

【０００７】

【本発明が解決しようとする課題】以上説明したように
、カラー画像において指定された色を有する領域を高速
に検索出来るようにすることが従来技術の課題である。したがって、本発明の目的は、指定された色を有する領
域を検索するのに適したカラー画像の領域管理方法を提
供すること及びこれを用いて指定された色を有する領域
を高速に検索するための検索方法を提供することである
。

【０００８】

【課題を解決するための手段】

【０００９】上記目的を達成するため、本発明のカラー
画像領域管理装置は、各画素の色データが三色表色系に
より表わされた画像データの各画素についてその画素の
色が知覚色系に基づいて分類される複数の色クラスのい
ずれに属するかを決定する色クラス決定手段と、それぞ
れ少なくとも一つの画素を含むブロックを葉ノードとし
て根ノードに至る木構造データを構成するとともに、該
木構造データにおけるノードごとに、そのノードに含ま
れる画素について色クラスごとにその色クラスに属する
色を有する画素の頻度を計算し各色クラスごとに計算さ
れた画素の頻度を色指標として記憶する色指標記憶手段
と、を有することを特徴としている。

【００１０】上記目的を達成するため、本発明のカラー
画像領域管理方法は、画像データの各画素の色データを
三色表色系から知覚色系に変換するステップと、知覚色
系に基づく色空間を複数の色クラスに分割するステップ
と、画素の色が上記複数の色クラスのうちのいずれの色
クラスに属するかを決定するステップと、それぞれ少な
くとも一つの画素を含むブロックを葉ノードとして根ノ
ードに至る木構造データを構成するとともに、該木構造
データにおけるノードごとに、そのノードに含まれる画
素について色クラスごとにその色クラスに属する色を有
する画素の頻度を計算し各色クラスごとに計算された画
素の頻度を色指標として記憶するステップと、を有する
ことを特徴としている。

【００１１】上記目的を達成するため、本発明のカラー
画像領域管理システムは、原画像を三色表色系により表
される画像データとして取り込むの画像入力装置と、こ
の画像入力装置から出力される三色表色系により表され
る画像データを記憶する記憶手段と、各画素の色データ
が三色表色系により表わされた画像データの各画素につ
いてその画素の色が知覚色系に基づいて分類される複数
の色クラスのいずれに属するかを決定する色クラス決定
手段と、それぞれ少なくとも一つの画素を含むブロック
を葉ノードとして根ノードに至る木構造データを構成す
るとともに、該木構造データにおけるノードごとに、そ
のノードに含まれる画素について色クラスごとにその色
クラスに属する色を有する画素の頻度を計算し各色クラ
スごとに計算された画素の頻度を色指標として記憶する
色指標記憶手段と、を有することを特徴としている。

【００１２】上記目的を達成するため、上記カラー画像
領域管理装置によって構成された木構造データを用いて
カラー画像の領域を検索する本発明のカラー画像領域検
索方法は、指定された色に基づいて検索すべき色クラス
を決定するステップと、決定された色クラスについて木
構造データを探索するステップと、葉ノード以外の各ノ
ードにおいて、決定された色クラスに属する画素の頻度
がゼロの場合は自己より下位のノードの探索を打ち切り
、そうでない場合は探索を続行するステップと、葉ノー
ドにおいて、決定された色クラスの画素の頻度が所定の
値より大きい場合にその葉ノードに対応するブロックを
検出すべき色の領域として記録するステップと、を有す
ることを特徴としている。

【００１３】

【実施例】はじめに、本発明を適用することのできる画
像処理システムの一般的な構成について説明する。本発
明は図２に示されるような画像処理システムにおいて適
用することができる。このシステムは画像入力装置８、
主メモリ１０、補助メモリ１２、画像処理プロセッサ６
、デイスプレイ装置１４、キーボード装置１８、ポイン
テイングデバイス１４で構成されているが、もちろん本
発明はこの構成に限定されるものではない。原カラー画
像（図示せず）はカラースキャナなどのような画像入力
装置８によって三色表色系のＲＧＢデータに変換されて
補助メモリ１２に記憶される。このＲＧＢデータは本発
明を適用する画像処理プロセッサ６によって色指標を与
えられた木構造データに変換されて再び補助メモリ１２
に記憶される。色指標の与え方については後で詳しく説
明する。ＲＧＢデータと木構造データはそれぞれ別々の
メモリに記憶するようにしてもよい。たとえばＲＧＢデ
ータを補助メモリ１２に記憶し、木構造データを画像処
理プロセッサ６における主メモリ１０に記憶することが
できる。このようにすれば、木構造データのデータ量は
ＲＧＢデータのデータ量に比べてずっと少ないので、画
像検索の処理を高速に行うことができる。画像処理プロ
セッサ６は本発明に基づく木構造データ生成ユニット２
を有している。

【００１４】図２に木構造データ生成ユニット２の構成
が示されている。木構造データ生成ユニット２は表色系
変換装置２０、色クラス決定装置２２及び木構造データ
変換装置２４を有する。なお、図２のメモリ２６は図１
の主メモリ１０及び補助メモリ１２をまとめて表したも
のである。以下、順に表色系変換装置２０、色クラス決
定装置２２及び木構造データ変換装置２４の機能につい
てそれぞれ説明する。

【００１５】表色系変換装置２０は各画素の色データを
、三つの原刺激ないしは原色で表される三色表色系の色
データから三つの属性（色相、明度及び彩度）で表され
る知覚色系の色データに変換する。この表色系の変換は
以下のようにして行われる。

【００１６】本実施例では、三色表色系の一つであるＲ
ＧＢ表色系と、知覚色系の一つであるＣＩＥ１９７６（
Ｌ＊，ａ＊，ｂ＊）均等知覚色空間との間の変換を例に
とって説明する。Ｒ、Ｇ、ＢからＬ＊、ａ＊、ｂ＊への
変換は以下の式に従って行われる。Ｌ＊＝１１６（Ｙ／Ｙ０）１／３−１６ａ＊＝５００［
（Ｘ／Ｘ０）１／３−（Ｙ／Ｙ０）１／３］ｂ＊＝２０
０［（Ｙ／Ｙ０）１／３−（Ｚ／Ｚ０）１／３］Ｘ＝Ｘ
ｒＲ＋ＸｇＧ＋ＸｂＢＹ＝ＹｒＲ＋ＹｇＧ＋ＹｂＢＺ＝ＺｒＲ＋ＺｇＧ＋ＺｂＢここでＸ，Ｙ，ＺはＸＹＺ表色系の三刺激値、Ｘ０、Ｙ
０、Ｚ０は標準光の三刺激値、ＸｒないしＸｂ、Ｙｒな
いしＹｂ、ＺｒないしＺｂはＲＧＢ表色系からＸＹＺ表
色系への変換の係数を表す。

【００１７】１９７５年のＣＩＥ会議で、ｍｅｔｒｉｃ
　　ｈｕｅ−ａｎｇｌｅ（記号Ｈ）、ｍｅｔｒｉｃ　　
ｌｉｇｈｔｎｅｓｓ（記号Ｌ＊）、ｍｅｔｒｉｃ　　ｃ
ｈｒｏｍａ（記号Ｃ＊）という用語が提案された。Ｈ及
びＣ＊はそれぞれ色相及び彩度に相当するもので、以下
の式で与えられる。Ｈ＝ｔａｎ−１（ｂ＊／ａ＊）Ｃ＝（ａ＊２＋ｂ＊２）
１／２本実施例では、これらのＨ、Ｌ＊及びＣ＊を使用
している。なお、説明の都合上、これらのＨ、Ｌ＊及び
Ｃ＊のことを本明細書ではそれぞれ色相（記号Ｈ）、明
度（記号Ｌ）及び彩度（記号Ｓ）と呼ぶことにする。

【００１８】三色表色系及び知覚色系は上記以外にもそ
れぞれさまざまな種類があるが、上記の変換は例示にす
ぎず、本発明はどの三色表色系及びどの知覚色系の間に
も適用することができる。このような変換を行う表色系
変換装置２０は変換テーブルで構成することも可能であ
る。また、必要であれば、表色系変換装置２０に知覚色
系から三色表色系への逆変換を行う手段をさらに設けて
もよい。なお、知覚色系の選び方によっては彩度（ｓａ
ｔｕｒａｔｉｏｎ）の代わりにクロマ（ｃｈｒｏｍａ）
が用いられることもあるので、本明細書では彩度という
用語は彩度（ｓａｔｕｒａｔｉｏｎ）及びクロマ（ｃｈ
ｒｏｍａ）の両方を含んだ概念として用いることにする
。また、知覚色系の選び方によっては色相と彩度とを同
時考慮した知覚色度（ｃｈｒｏｍａｔｉｃｎｅｓｓ）が
用いられることもあるが、本発明はそのような知覚色系
の場合にも適用することができる。

【００１９】次に、色クラス決定装置２２による各画素
の色クラスの決定方法について説明する。色クラス決定
装置２２は色相Ｈ、明度Ｌ、及び彩度Ｓの三要素で表さ
れる知覚色系の色空間を複数の領域（すなわち、色クラ
ス）に分割する色空間分割手段（図示せず）と、各画素
の色がどの分割領域（色クラス）に属するのかを判別す
る色クラス判別手段（図示せず）とを有する。色空間分
割手段による分割のしかたはいろいろ考えられるが、本
実施例では実用的な見地から、次のように分割している
。Ｈ方向及びＬ方向に関してはそれぞれ等分割とする。Ｓ方向に関しては、所定のレベル以下の彩度のものは無
彩色として取り扱うこととした。彩度の低いものを有彩
色として扱うと、わずかなノイズによって全く異なる色
相に分類される可能性があるためである。このように、
所定のレベル以下の彩度のものは無彩色として扱うと、
色領域検索の信頼性を高めることができる。

【００２０】以上のようにして複数の領域に分割された
色空間の例が、図３に示されている。図３において紙面
に対して垂直な方向がＬの軸である。中央の小さな円が
、所定レベル以下の彩度を無彩色として分類した領域で
ある。図３の例では、Ｈ方向は１０個に分割され、Ｓ方
向は無彩色の部分を含めて５個に分割され（有彩色の部
分は４個に分割されている）、Ｌ方向は４個に分割され
ている（但し、Ｌ方向は図示せず）。Ｈ、Ｌ及びＳの各
方向の分割数ｉ、ｊ及びｋは、それぞれ自由に設定する
ことができる。本実施例ではＨ方向、Ｌ方向及びＳ方向
（但し、有彩色の部分）の分割は等分としたが、必ずし
も等分でなくともよい。

【００２１】色クラス決定装置２２の色クラス判別手段
は表色系変換装置２０によってＲ、Ｇ、Ｂから変換され
たＨ、Ｌ、Ｓによって表される各画素の色が上記色空間
のどの領域（すなわち、色クラス）に属するを次のよう
にして判別する。今、或る画素のＨ、Ｌ及びＳの値がそ
れぞれｈ、ｌ及びｓであるとする。ｈがＨ方向のｉ番目
の領域Ｈｉに属しｌがＬ方向のｊ番目の領域Ｌｊに属し
ｓがＳ方向のｋ番目の領域Ｓｋに属するときは、その画
素の色クラスはＨｉ、ＬｊおよびＳｋで決まる色クラス
Ｃ（Ｈｉ，Ｌｊ，Ｓｋ）に属するとされる。なお、原画
像の色の存在する領域だけに色クラスを割りふるように
してもよい。例えば、色空間の分割された領域の数が２
００だとして、そのうちの５０の領域に原画像の画素の
色が存在するときは、色クラスの数を５０とする。もち
ろん、原画像の一部の領域を原画像にない色で塗りつぶ
そうという場合は、原画像に存在しない色の分割領域が
必要となるので、このような場合には、原画像の色の存
在不存在にかかわりなく、色クラスの数を分割領域の総
数とする。

【００２２】図４のステップ１００ないしステップ１１
２は以上に説明した表色系変換装置２０による表色系の
変換及び色クラス決定装置２２による色空間の分割（色
クラスの定義）を簡単な流れ図で表したものである。

【００２３】各画素の色クラスＣ（Ｈｉ，Ｌｊ，Ｓｋ）
を決めるに際し、その画素の近傍の画素のＨ、Ｌ及びＳ
の値を考慮すれば、色領域検索の信頼性をより高めるこ
とができる。

【００２４】近傍の画素の考慮のしかたは、いろいろ考
えられる。たとえば、対象となっている画素Ｐｘ、ｙに
対し、図５に示すごとく、８つの近傍の画素を考えて、
対象となっている画素Ｐｘ、ｙを含めて全部で９個の画
素でＨ、Ｌ及びＳの値のそれぞれの平均ｈ、ｌ及びｓを
とり、このようにして求められた平均のｈ、ｌ及びｓが
それぞれＨ方向、Ｌ方向及びＳ方向のどの分割領域に属
するかで対象となっている画素Ｐｘ、ｙの色クラスを決
めることができる。

【００２５】三色表色系による原画像のＲＧＢデータ２
８と、表色系変換装置２０によって変換された知覚色系
によるＨＬＳデータ３０と、色クラス決定装置２２によ
って決定された色クラスデータ３２はメモリ２６（すな
わち、主メモリ１０または補助メモリ１２）に記憶され
るが、ＨＬＳデータ３０もしくは色クラスデータ３２ま
たはその双方は、必要な場合にそのつど原画像のＲＧＢ
データ２８を用いて表色系変換装置２０及び色クラス決
定装置２２から直接に取得するようにしてもよい。

【００２６】次に、色クラス決定装置２２によって決定
された色クラスを用いて木構造データ３０を生成する木
構造データ変換装置２４の機能について説明する。生成
された木構造データ３０は図１のメモリ２６（すなわち
、主メモリ１０または補助メモリ１２）に記憶される。説明の簡単のため、本実施例では、木構造として４分木
を用いた場合について説明するが、本発明は４分木に限
定されるものではない。

【００２７】木構造として４分木を用いる場合、補助メ
モリ１２に記憶されたＲＧＢデータ２８は（２のｎ乗）
Ｘ（２のｎ乗）個である複数個のブロックに分割される
。説明の簡単のため、木構造のレベルとしてｎ＝３、す
なわち、ｎ＝０ないし３の４レベルの場合を考えること
にしよう。図６ないし図９には、木構造の各レベルにお
けるノードＮＢと画像のブロックＢとの関係が概念的に
示されている。最上位レベル（ｎ＝０）のノードＮＢを
根ノード、最下位レベル（ｎ＝３）のノードＮＢｘｘｘ
を葉ノード、それら以外のレベル（ｎ＝１または２）の
ノードＮＢｘ及びＮＢｘｘを中間ノードという。一般的
には葉ノードに対応する最小のブロックＢｘｘｘは、そ
れぞれ、２個以上の画素で構成される。もちろん、１つ
の最小ブロックを１個の画素で構成することも可能であ
る。最小ブロックを２個以上の多数の画素で構成しておけば
、木構造データを記憶するのに必要なメモリの量を少な
くすることができ、色領域の検索をより高速で行うこと
が可能となる。一つの最小ブロックを構成する画素の数
は原画像の性質及び画像入力装置８の画素密度などを考
慮して決定することができる。

【００２８】ここで、最小ブロックＢｘｘｘは２Ｘ２＝
４個の画素で構成され、色クラスＣｍは色クラスＣ１か
ら色クラスＣ６４まで全部で６４個（ｍ＝６４）あると
仮定しよう。色指標Ｉは色クラスＣ１から色クラスＣ６
４のおのおのに対応する色指標の要素ｉ１ないしｉ６４
を並べたものとして表される。各要素はその要素に対応
する色クラスを有する画素が対象となるブロックに含ま
れているかどうか（又はどの程度含まれているか）を表
す。もっとも簡単な表現方法は各要素を２値表示にする
ことである。たとえば、対象となるブロック中に各要素
に対応する色クラスを有する画素が含まれていればその
要素を１とし、含まれていなければゼロとする。そこで
まず、各要素を２値表示とした色指標について説明する
。

【００２９】たとえば、ブロックＢ１１１の４つの画素
がすべて同じ色クラスＣ２であるときは、色クラスＣ２
に対応する色指標の要素ｉ２だけが１なのでブロックＢ
１１１の色指標ＩＢ１１１はＩＢ１１１＝（０，１，０
，・・・，０）と定義される。同様に４つの画素の色ク
ラスがすべて同じ色クラスＣ３であるときは、ブロック
Ｂ１１１の色指標ＩＢ１１１はＩＢ１１１＝（０，０，
１，０，・・・，０）と定義される。また、４つの画素
の色クラスがそれぞれ色クラスＣ１，色クラスＣ２，色
クラスＣ３及び色クラスＣ４であるときは、ブロックＢ
１１１の色指標ＩＢ１１１はＩＢ１１１＝（１，１，１
，１，０，・・・，０）と定義される。次に、最下位レ
ベルのノードの直ぐ上位のレベルのノードについての色
指標の求め方について説明する。たとえば、４つの最小
ブロックＢ１１０、Ｂ１１１、Ｂ１１２及びＢ１１３で
構成されるブロックＢ１１の色指標ＩＢ１１を例にとっ
て説明する。

【００３０】ブロックＢ１１０、Ｂ１１１、Ｂ１１２及
びＢ１１３の色指標がすべて同じであれば、ブロックＢ
１１の色指標もこれと同じになる。ブロックＢ１１０、
Ｂ１１１、Ｂ１１２及びＢ１１３の色指標ＩＢ１１０、
ＩＢ１１１、ＩＢ１１２及びＩＢ１１３が、それぞれ、
ＩＢ１１０＝（１，０，・・・，０）、ＩＢ１１１＝（
Ｏ，１，０，・・・，０）、ＩＢ１１２＝（０，０，１
，０，・・・，０）及びＩＢ１１３＝（０，０，０，１
，０，・・・，０）であれば、ブロックＢ１１の色指標
ＩＢ１１は、ＩＢ１１＝（１，１，１，１，０，・・・
，０）と定義される。このように、４つのブロックの直
ぐ上位のブロックの色指標は自己の直ぐ下位の４つのブ
ロックの色指標のＯＲをとったものとなる。

【００３１】ブロックＢｘｘの上位のブロックＢｘ、ブ
ロックＢｘの上位のブロックＢについても、これと同よ
うな操作を繰り返すことにより、それぞれの色指標ＩＢ
ｘ及びＩＢが得られる。このようにして定義された色指
標を各ノードごとに記憶することにより、色指標の付与
された木構造データが生成される。

【００３２】以上に説明した色指標の与え方は、要する
に、そのブロックにどんな色クラスの画素が含まれてい
るかを指標するというもっとも単純な方法である。

【００３３】次に、色領域の検索の信頼性をより高める
ための色指標の与え方について説明する。

【００３４】上記の色指標の与え方によれば、そのブロ
ックにどんな色クラスの画素が含まれているかが指標さ
れるが、次に説明する第二の方法では、そのブロックに
どんな色クラスの画素がどれくらい含まれているかを指
標するように色指標が定義される。

【００３５】この第二の方法では、ブロックに含まれる
画素の色クラスについての頻度が計算される。この頻度
は、もっとも簡単な例では、同一色クラスの個数をカウ
ントすることにより計算される。たとえば、ブロックＢ
１１１を構成する４つの画素がすべて同じ色クラスＣ１
であるときは、色クラスＣ１の画素が全部で４つなので
、ブロックＢ１１１の色指標ＩＢ１１１はＩＢ１１１＝
（４，０，・・・，０）と定義される。同様に４つの画
素の色クラスがすべて同じ色クラスＣ２であるときは、
ブロックＢ１１１の色指標ＩＢ１１１はＩＢ１１１＝（
０，４，０，・・・，０）と定義される。また、これら
４つの画素のうち、１つが色クラスＣ３で、残りの３つ
が色クラスＣ４であるときは、ブロックＢ１１１の色指
標ＩＢ１１１はＩＢ１１１＝（０，０，１，３，０，・
・・，０）と定義される。

【００３６】次に、最下位レベルのノードの直ぐ上位の
レベルのノードについての色指標の求め方について説明
する。たとえば、４つの最小ブロックＢ１１０、Ｂ１１
１、Ｂ１１２及びＢ１１３で構成されるブロックＢ１１
の色指標ＩＢ１１を例にとって説明する。

【００３７】ブロックＢ１１０、Ｂ１１１、Ｂ１１２及
びＢ１１３の色指標が、ＩＢ１１０＝ＩＢ１１１＝ＩＢ
１１２＝ＩＢ１１３＝（４，０，・・・，０）であると
きは、ブロックＢ１１の色指標ＩＢ１１は、ＩＢ１１＝
（１６，０，・・・，０）と定義される。また、ＩＢ１
１０＝（４，０，・・・，０）、ＩＢ１１１＝（０，４
，０，・・・，０）、ＩＢ１１２＝（０，０，４，０，
・・・，０）、ＩＢ１１３＝（０，０，０，４，０，・
・・，０）であるときは、ブロックＢ１１の色指標ＩＢ
１１は、ＩＢ１１＝（４，４，４，４，０，・・・，０
）と定義される。また、ＩＢ１１０＝（１，２，１，０
，・・・，０）、ＩＢ１１１＝（０，１，２，１，０，
・・・，０）、ＩＢ１１２＝（０，０，１，２，１，０
，・・・，０）、ＩＢ１１３＝（０，０，０，１，２，
１，０，・・・，０）であるときは、ブロックＢ１１の
色指標ＩＢ１１は、ＩＢ１１＝（１，３，４，４，３，
１，０，・・・，０）と定義される。これらの例からわ
かるように、ＩＢｘｘは自己の直ぐ下位の４つのブロッ
クＩＢｘｘｘの対応する要素の値の総和を自己のそれぞ
れの要素として持つように構成される。ＩＢｘ及びＩＢ
についても同様である。すなわち、４つのブロックの直
ぐ上位のブロックの色指標は自己の直ぐ下位の４つのブ
ロックの色指標の対応する要素の値の総和を自己のそれ
ぞれの要素として持つように構成される。

【００３８】上述の例では、ブロックに含まれる画素の
色クラスについての頻度は、もっとも簡単な例として、
同一色クラスの個数をカウントしそのカウント値をその
まま用いているが、そのブロックに含まれる画素の総数
を量子化し、考えている色クラスの画素の総数がどの量
子化レベルに属するかをその色クラスについての頻度と
して与えるようにしてもよい。たとえば、あるブロック
（任意のレベルのブロックでよい）について、そのブロ
ックが１００個の画素で構成されているとする。これを
、０個、１個から１０個、１１個から２０個、２１個か
ら３０個，・・・，９１個から１００個のそれぞれの範
囲に分ける。今、たとえば或る色クラスについて着目し
、その色クラスの画素の個数が０個であれば頻度は０、
１個から１０個までの範囲にあれば頻度は１、１１個か
ら２０個までの範囲にあれば頻度は２、２１個から３０
個までの範囲にあれば頻度は３（以下、同よう）と定義
される。量子化の程度及び方法はこの例に限定されるも
のではない。

【００３９】ブロックに含まれる画素の総数を量子化し
、考えている色クラスの画素の総数がどの量子化レベル
に属するかをその色クラスについての頻度として与える
ようにした場合の木構造データ生成の流れ図を図１０及
び図１１のステップ２００ないしステップ２３６に示し
た。

【００４０】次に、木構造データ生成ユニット２によっ
て色指標を与えられた木構造データ３０を用いた色領域
の検索について説明する。色領域の検索は図２に示す検
索ユニット４によって行われる。色領域の検索は、たと
えば、オペレータが或る色の領域を別の色に変更したい
という場合などに必要となる。この場合、まず、その色
の領域のブロックを過不足なく検出する必要がある。オ
ペレータによる色の指定には種々のやり方が考えられる
。たとえば、マウスなどのポインテイングデバイスを用
いてデイスプレイ画面上で所望の色を有する領域内の任
意の位置にカーソルを移動させそのカーソルにより画素
を特定することでその色を指定するやり方が考えられる
。前述のごとく、画素の色に関する情報はＲＧＢデータ
２８、ＨＬＳデータ３０または色クラスデータ３２のい
ずれの形でも記憶することができる。画素の色データが
色クラスデータの形で記憶されている場合は、カーソル
により画素が特定されることにより、その画素の色クラ
スＣ（Ｈｉ，Ｌｊ，Ｓｋ）が直接特定される。画素の色
データがＨＬＳデータの形で記憶されている場合は、色
クラス決定装置２２を用いてそのＨＬＳデータを色クラ
スデータに変換することにより、その画素の色クラスが
特定される。画素の色データがＲＧＢデータの形で記憶
されている場合は、表色系変換装置２０を用いてＲＧＢ
データをＨＬＳデータに変換し、さらにこのＨＬＳデー
タを色クラス決定装置２２で色クラスデータに変換する
ことにより、その画素の色クラスが特定される。

【００４１】また別のやり方として、所望の色を有する
領域内で複数の画素を指定して、そのうちでもっとも多
い色クラスをその領域の色クラスとしてもよいし、ある
いは、複数の画素のの平均をとってその領域の色クラス
としてもよい。この平均のとり方は、前述の色クラス決
定の場合と同ように、色相、明度及び彩度のそれぞれの
平均をとるようにする。たとえば、画素の色データがＨ
ＬＳデータの形で記憶されている場合は、これらの複数
の画素の各画素のＨＬＳデータを用いて、Ｈ、Ｌ及びＳ
の値のそれぞれの平均ｈ、ｌ及びｓをとり、これらのｈ
、ｌ及びｓによって決まる色クラスをその領域の色クラ
スとする。

【００４２】さらに別のやり方として、表示画面におい
て画像のほかに色クラスに基づく色のサンプルを表示し
ておき、このサンプルをオペレータが直接指定すること
により色クラスを特定するようにしてもよい。

【００４３】さらに別のやり方として、Ｈ、Ｌ及びＳの
値または色クラスの番号をキーボード装置１８などから
直接入力することにより色クラスを特定するようにして
もよい。

【００４４】このようにして特定された色クラスＣ（Ｈ
ｉ，Ｌｊ，Ｓｋ）について色指標をノードごとに持つ木
構造データを探索する。特定された色クラスＣ（Ｈｉ，
Ｌｊ，Ｓｋ）だけでなくその近傍の色クラスＣ’につい
ても木構造データを探索すれば、色領域検索の信頼性を
より高めることができる。色クラスＣ（Ｈｉ，Ｌｊ，Ｓ
ｋ）に対して、近傍の色クラスＣ’はＨ方向、Ｌ方向及
びＳ方向の各方向に存在する。すなわち、近傍の色クラ
スＣ’は色空間において色クラスＣに対して三次元的に
近接して存在する。どの程度の近傍の色クラスＣ’まで
検索の対象とするかは、原画像の性質及び色クラスの分
割数などの諸条件に応じて自由に設定することができる
。

【００４５】どの程度の近傍の色クラスＣ’まで検索の
対象とするかはＨ方向、Ｌ方向及びＳ方向のどの方向で
も考え方は同じなので、たとえば、図１５に示すように
、Ｈ方向について考えると、特定された色クラスＣ（Ｈ
ｉ，Ｌｊ，Ｓｋ）の色相Ｈｉがわずかに異なるＨｉ−１
及びＨｉ＋１が色クラスＣ（Ｈｉ，Ｌｊ，Ｓｋ）に色相
Ｈの観点からもっとも近い色クラスとなる。図に示すよ
うに、色クラスＣ（Ｈｉ，Ｌｊ，Ｓｋ）の近傍の色クラ
スＣ’（Ｈｉ−１，Ｌｊ，Ｓｋ）及び色クラスＣ’（Ｈ
ｉ＋１，Ｌｊ，Ｓｋ）は色クラスＣ（Ｈｉ，Ｌｊ，Ｓｋ
）の重みを１とするとそれに対して相対的に小さい重み
Ｗ（Ｗ＜１）を持つようにしておく。近傍の色クラスの
範囲をＨｉ−２及びＨｉ＋２、Ｈｉ−３及びＨｉ＋３、
・・・のようにさらに広げる場合はＨｉから離れるに従
って順次小さい重みを持たせるようにしておけばよい。近傍の色クラスの重みはＨ方向、Ｌ方向及びＳ方向の各
方向の分割数及び原画像の性質などを考慮してＨ方向、
Ｌ方向及びＳ方向の各方向で異なった値を用いることが
できる。

【００４６】簡単な例として、対象となっている色クラ
スＣ（Ｈｉ，Ｌｊ，Ｓｋ）についてＨ方向、Ｌ方向及び
Ｓ方向の各方向の両隣のみが近傍の色クラスであり、そ
れらの重みが色クラスＣの重みを１としてそれぞれＷｈ
、Ｗｌ及びＷｓである場合を考える。そうすると、近傍
の色クラスは色クラスＣ（Ｈｉ，Ｌｊ，Ｓｋ）を含めて
全部で２７（＝３ｘ３ｘ３）個となる。これらの近傍の
色クラスのそれぞれの重みは、色クラスごとに、Ｈ方向
、Ｌ方向及びＳ方向の各方向の重みを加えたものとなる
。たとえば、近傍の色クラスＣ’（Ｈｉ−１，Ｌｊ−１
，Ｓｋ−１）の重みＷはＷ＝Ｗｈ＋Ｗｌ＋Ｗｓであり、
近傍の色クラスＣ’（Ｈｉ−１，Ｌｊ，Ｓｋ−１）の重
みＷはＷ＝Ｗｈ＋１＋Ｗｓであり、色クラスＣ（Ｈｉ，
Ｌｊ，Ｓｋ）の重みＷはＷ＝１＋１＋１（＝３）である
。これらの色クラスの重みを、対象となっている色クラ
スＣの重みを１として規格化すれば、たとえば近傍の色
クラスＣ’（Ｈｉ−１，Ｌｊ−１，Ｓｋ−１）の重みＷ
はＷ＝１／３（Ｗｈ＋Ｗｌ＋Ｗｓ）であり、近傍の色ク
ラスＣ’（Ｈｉ−１，Ｌｊ，Ｓｋ−１）の重みＷはＷ＝
１／３（Ｗｈ＋１＋Ｗｓ）となる。対象となっている色
クラスに対し重みＷがゼロでない色クラスを近傍色クラ
スと呼ぶことにする。なお、単に近傍色クラスを定義す
るだけなら、近傍色クラスの重みはすべて１にしておけ
ば足りる。上述のような重みの定め方をすることは、後
で説明する、葉ノードにおけるブロック検出の際に非常
に有益である。この点については後で詳しく説明する。

【００４７】以上のようにして定義された近傍色クラス
の色は対象となっている色クラスの色に知覚色的に近い
色になるので、色領域検索の信頼性を高めることができ
る。したがって指定された色を含むブロックを検出する
ためには、色指標の４分木を上からたどり指定された色
の色クラスの色指標及びその色クラスの近傍色クラスに
ついての色指標を調べればよい。中間ノードにおいて、
指定された色の色クラス及びその近傍色クラスの色指標
がゼロであれば、その色指標についてはそれより下位の
ノードでは必ずゼロであるから、探索を打ち切る。これ
らの色指標がゼロでない限り、順に下位のノードが調べ
られ、最下位のノード、すなわち、葉ノードに至った場
合は、次のようにしてその葉ノードに対応するブロック
（最小ブロック）が検出すべきブロックであるかどうか
を決定する。なお、探索のやり方は深さ優先探索又は幅
優先探索のいずれを用いてもよい。好適には、探索のア
ルゴリズムが簡単になるように再帰的な手法が用いられ
る。

【００４８】今、色クラスＣ（Ｈｉ，Ｌｊ，Ｓｋ）の色
指標がゼロでないことにより、その色クラスの画素を有
する最小ブロックに対応する１つの葉ノードに至ったと
仮定する。色指標がゼロか１かの２値で表される場合（
以下、２値表示ともいう）は、このブロックを検出すべ
きブロックとして記録する。色指標が頻度で表される場
合（以下、頻度表示ともいう）は、そのブロックが所定
のしきい値を越える頻度を有するときに、そのブロック
を検出すべきブロックとして記録する。ところで、色ク
ラスＣ（Ｈｉ，Ｌｊ，Ｓｋ）の色指標がゼロでないこと
により探索された葉ノードに対応するブロックは、色ク
ラスＣの画素のほかに近傍色クラスＣ’の画素を含んで
いる場合もあるので、色クラスＣの画素の頻度を調べた
だけでは所定のしきい値に達せず、そのブロックがうま
く検出されないという可能性もある。そこで、好適な実
施例では、前述の近傍色クラスＣ’の重みを考慮して色
クラスＣの画素の頻度及び近傍色クラスＣ’の画素の頻
度の加重和をとり、重みを考慮した加重和として計算さ
れた画素の頻度を所定のしきい値と比較すべき画素の頻
度とすることにより、この問題を解決する。このしきい
値は場合に応じて自由に設定することができ、動的に変
えられるようにしておけばさらに便利である。近傍色ク
ラスＣ’の色指標がゼロでないことにより探索が葉ノー
ドに至った場合も、同ようにして近傍色クラスＣ’の重
みを考慮して色クラスＣの画素の頻度及び近傍色クラス
Ｃ’の画素の頻度の加重和をとり、重みを考慮した加重
和として計算された画素の頻度を所定のしきい値と比較
すべき画素の頻度とし、これが所定のしきい値を越える
ときに、そのブロックを検出すべきブロックとして記録
する。なお、色指標がゼロか１かの２値で表される場合
は、近傍色クラスの重みＷは１にしておく必要がある。色指標がゼロか１かの２値で表される場合は、複数個の
画素で構成される１つの最小ブロックの中に指定された
色クラスに属する色の画素が１個しかないときでもその
ブロックが検出すべきブロックとして記録されてしまう
ので、検出漏れがないという点ではよいが、逆に検出す
べきでないブロックを検出してしまう可能性もある。し
たがって、できるだけ過不足なく指定した色を有するブ
ロックを検出したい場合は、上述のように色指標を色ク
ラスの頻度で表して所定のしきい値を越える頻度を有す
るブロックを検出すべきブロックとして記録するとよい
。なお、色指標がゼロか１かの２値で表される場合（２
値表示）も所定のしきい値を１と考えれば、広い意味で
は頻度表示である。

【００４９】一方、木構造データを記憶するのに必要な
メモリの量は２値表示の場合の方が頻度表示の場合より
も少なくて済む。そこで、好適な実施例においては葉ノ
ードのみ色指標を頻度表示とし葉ノード以外のノードで
は色指標を２値表示として木構造データを構成する。こ
のようにすれば、木構造データを記憶するのに必要なメ
モリの量を抑えつつ（したがって色領域の検索をより高
速で行うことが可能となる）過不足なく指定した色を有
するブロックを検出することができる。

【００５０】ところで、オペレータが指定した色は、色
クラスを直接に指定する場合は別として、Ｈ方向、Ｌ方
向及びＳ方向の各方向の分割領域Ｈｉ、Ｌｊ及びＳｋの
各々のちょうど中心に来るとは限らない。そこで、指定
された色が分割領域の中心に来ない場合は、中心からの
ずれに応じて近傍色クラスの重みを変えることにより、
そのずれを反映させる。

【００５１】図１６に示すように、指定された色がＨ方
向のある分割領域Ｈｉにおいて中心からずれている場合
は（この例では中心からＨｉ＋１の方向にずれている）
、簡単な例として指定された色を中心として１の重みを
持つ範囲が１クラス分の幅で存在し、その両隣にＷの重
みを持つ範囲がそれぞれ１クラス分の幅で存在すると仮
定して、分割領域Ｈｉ−１、Ｈｉ、Ｈｉ＋１及びＨｉ＋
２の各領域における面積がそれぞれ等しくなるように各
分割領域Ｈｉ−１、Ｈｉ、Ｈｉ＋１及びＨｉ＋２の重み
を定める。たとえば、分割領域Ｈｉ−１を例にとると、
分割領域Ｈｉ−１の重みＷｉ−１は四角形ａｂｃｄの面
積Ｓ１と四角形ｅｆｃｇの面積Ｓ２が等しくなるように
定められる。Ｈ方向の重みのほか、Ｌ方向及びＳ方向の
各方向の重みも同ようにして定められ、このようにして
定められたＨ方向、Ｌ方向及びＳ方向の各方向の重みを
色クラスごとに加えることによって近傍色クラスを定義
する。各方向の重みの加え方は前述の場合と同ようであ
る。以上のようにして中心からのずれに応じて近傍色ク
ラスの重みを変えることにより、そのずれを反映させる
と、近傍色クラスの範囲は指定された色の色クラスの中
心からのずれを考慮しない場合に比べて若干広めに設定
されることになる。

【００５２】図１２ないし図１４に以上に説明した色領
域の検索の流れ図を例示した。図１２は色領域検索の全
体の流れ図、図１３は図１２のステップ３０６において
葉ノード以外で実行されるブロック探索の流れ図、図１
４は図１２のステップ３０６において葉ノードで実行さ
れるブロック探索の流れ図をそれぞれ表している。図１
４のステップ５０２において計算される色指標の加重和
が、上述の近傍色クラスＣ’の重みを考慮して計算され
る色クラスの頻度である。

【００５３】

【発明の効果】以上説明したように本発明によれば、知
覚色系に基づく色指標をノードごとに与えた木構造デー
タを構成することにより、カラー画像における色領域の
検索を高速かつ確実に行うことが可能となる。

【図面の簡単な説明】

【図１】本発明に基づく実施例の木構造データ生成ユニ
ット２の構成を示す図である。

【図２】本発明を適用した画像処理システムの実施例の
構成を示すである。

【図３】本発明に基づいて複数の領域に分割された色空
間の例を示す図である。

【図４】本発明に基づく実施例よる色クラスの定義の流
れ図である。

【図５】画素の色クラスを決めるに際し考慮される近傍
の画素を示す図である。

【図６】木構造の根ノードにおけるノードとブロックと
の関係を概念的に示す図である。

【図７】木構造の中間ノードにおけるノードとブロック
との関係を概念的に示す図である。

【図８】木構造の中間ノードにおけるノードとブロック
との関係を概念的に示す図である。

【図９】木構造の葉ノードにおけるノードとブロックと
の関係を概念的に示す図である。

【図１０】本発明に基づく実施例の木構造データ生成の
流れ図である。

【図１１】本発明に基づく実施例の木構造データ生成の
流れ図である。

【図１２】本発明に基づく実施例の色領域検索の全体の
流れ図である。

【図１３】図１２のステップ３０６において葉ノード以
外で実行されるブロック探索の流れ図

【図１４】図１２のステップ３０６において葉ノードで
実行されるブロック探索の流れ図

【図１５】近傍の色クラスの重みの与え方を説明する図
である。

【図１６】指定された色が色クラスの中心からのずれて
いる場合の近傍の色クラスの重みの与え方を説明する図
である。

【符号の説明】

２　　　　　　木構造データ生成ユニット４　　　　　
　検索ユニット６　　　　　　画像処理プロセッサ８　　　　　　画像入力装置１０　　　　主メモリ１２　　　　補助メモリ２０　　　　表色系変換装置２２　　　　色クラス決定装置２４　　　　木構造データ変換装置

Claims

【特許請求の範囲】

【請求項１】各画素の色データが三色表色系により表わ
された画像データの各画素についてその画素の色が知覚
色系に基づいて分類される複数の色クラスのいずれに属
するかを決定する色クラス決定手段と、それぞれ少なく
とも一つの画素を含むブロックを葉ノードとして根ノー
ドに至る木構造データを構成するとともに、該木構造デ
ータにおけるノードごとに、そのノードに含まれる画素
について色クラスごとにその色クラスに属する色を有す
る画素の頻度を計算し各色クラスごとに計算された画素
の頻度を色指標として記憶する色指標記憶手段と、を有
するカラー画像領域管理装置。
【請求項２】上記画素の頻度は、上記木構造データにお
けるノードごとに、そのノードに含まれる画素について
色クラスごとにその色クラスに属する色を有する画素が
存在する場合には一方の論理値でありその色クラスに属
する色を有する画素が存在しない場合には他方の論理値
である二進数として計算される請求項１に記載のカラー
画像領域管理装置。
【請求項３】上記画素の頻度は、上記木構造データにお
けるノードごとに、そのノードに含まれる画素について
色クラスごとにその色クラスに属する色を有する画素の
個数のカウント値として計算される請求項１に記載のカ
ラー画像領域管理装置。
【請求項４】上記画素の頻度は、上記木構造データにお
けるノードが葉ノードであるときは、そのノードに含ま
れる画素について色クラスごとにその色クラスに属する
色を有する画素が存在する場合には一方の論理値であり
その色クラスに属する色を有する画素が存在しない場合
には他方の論理値である二進数として計算され、上記木
構造データにおけるノードが葉ノードでないときは、そ
のノードに含まれる画素について色クラスごとにその色
クラスに属する色を有する画素の個数のカウント値とし
て計算される請求項１に記載のカラー画像領域管理装置
。
【請求項５】上記画素のカウント値を量子化した請求項
３または４に記載のカラー画像領域管理装置。
【請求項６】上記葉ノードに対応するブロックに含まれ
る画素の数が２個以上である請求項１ないし５のいずれ
か一つに記載のカラー画像領域管理装置。
【請求項７】上記葉ノードに対応するブロックに含まれ
る画素の数が１個である請求項１ないし５のいずれか一
つに記載のカラー画像領域管理装置。
【請求項８】上記色クラス決定手段は画像データの各画
素の色データを三色表色系から知覚色系に変換する変換
手段と、上記知覚色系に基づく色空間を複数の色クラス
に分割し上記変換手段により知覚色系に変換された色が
いずれの色クラスに属するかを判別する手段と、を有す
る請求項１ないし７のいずれか一つに記載のカラー画像
領域管理装置。
【請求項９】上記色クラス決定手段は画素の色の彩度が
所定の値より小さいときはその画素の色を無彩色の色ク
ラスとして判別する請求項８に記載のカラー画像領域管
理装置。
【請求項１０】画像データの各画素の色データを三色表
色系から知覚色系に変換するステップと、知覚色系に基
づく色空間を複数の色クラスに分割するステップと、画
素の色が上記複数の色クラスのうちのいずれの色クラス
に属するかを決定するステップと、それぞれ少なくとも
一つの画素を含むブロックを葉ノードとして根ノードに
至る木構造データを構成するとともに、該木構造データ
におけるノードごとに、そのノードに含まれる画素につ
いて色クラスごとにその色クラスに属する色を有する画
素の頻度を計算し各色クラスごとに計算された画素の頻
度を色指標として記憶するステップと、を有するカラー
画像領域管理方法。
【請求項１１】原画像を三色表色系により表される画像
データとして取り込むの画像入力装置と、上記画像入力
装置から出力される三色表色系により表される画像デー
タを記憶する記憶手段と、各画素の色データが三色表色
系により表わされた画像データの各画素についてその画
素の色が知覚色系に基づいて分類される複数の色クラス
のいずれに属するかを決定する色クラス決定手段と、そ
れぞれ少なくとも一つの画素を含むブロックを葉ノード
として根ノードに至る木構造データを構成するとともに
、該木構造データにおけるノードごとに、そのノードに
含まれる画素について色クラスごとにその色クラスに属
する色を有する画素の頻度を計算し各色クラスごとに計
算された画素の頻度を色指標として記憶する色指標記憶
手段と、を有するカラー画像領域管理システム。
【請求項１２】請求項１に記載のカラー画像領域管理装
置によって構成された木構造データを用いてカラー画像
の領域を検索するカラー画像領域検索方法であって、指
定された色に基づいて検索すべき色クラスを決定するス
テップと、決定された色クラスについて木構造データを
探索するステップと、葉ノード以外の各ノードにおいて
、決定された色クラスに属する画素の頻度がゼロの場合
は自己より下位のノードの探索を打ち切り、そうでない
場合は探索を続行するステップと、葉ノードにおいて、
決定された色クラスの画素の頻度が所定の値より大きい
場合にその葉ノードに対応するブロックを検出すべき色
の領域として記録するステップと、有するカラー画像領
域検索方法。
【請求項１３】上記検索すべき色クラスは指定された色
の属する色クラス及び指定された色の属する色クラスに
知覚色的に近い色クラスである請求項１２に記載のカラ
ー画像領域検索方法。