(57)【特許請求の範囲】
【請求項１】
画像要素を分類する方法であって、
前記画像要素の開区間長と前記画像要素の閉区間長との比に基づき、前記画像要素を前景層および背景層からなるカテゴリのうち１つとして分類するステップであって、該開区間長が、他の要素によって閉じられていない該画像要素の１以上の部分についての周囲セグメントの長さであり、該閉区間長が該他の要素によって閉じられた要素形状部分を除去した後の該画像要素の可視部分の周囲長である、ステップ、及び
前記カテゴリのうち前記１つと関連する符号化スキームに従って前記画像要素を符号化するステップ
を含む方法。
【請求項２】
前記開区間長が、
【数１】
0004351411.tif 000005
として計算され、ここで、Ｐｏｒｉｇｉｎａｌは画像要素の元の周囲長であって閉塞がないときに画像要素が見せることになる画像要素の元の形状の周囲長であり、Ｐｏｃｃｌｕｄｅｄは前記閉区間長であり、かつＰｏｃｃｌｕｓｉｏｎは前記他の要素によって閉じられる前記画像要素の部分の周囲長である請求項１に記載の方法。
【請求項３】
前記閉区間長が、
Ｒ−２Ｌ
として計算され、ここで、Ｒは画像要素の各水平走査線の周囲長の合計であり、かつＬは各水平走査線と前記画像要素の次の水平走査線との間における接触セグメントの長さの合計である請求項１に記載の方法。
【請求項４】
前記比が、
【数２】
0004351411.tif 000006
として計算され、ここで、δは画像要素と少なくとも１つの連接する画像要素の間の色差であり、Ｐｕｎｏｃｃｌｕｄｅｄは前記開区間長であり、かつＰｏｃｃｌｕｄｅｄは前記閉区間長である請求項１に記載の方法。
【請求項５】
前記色差が、前記画像要素と前記少なくとも１つの隣接する画像要素の間における色差のうち最大のものとして計算される請求項４に記載の方法。
【請求項６】
前記色差が、所定の数の前記少なくとも１つの隣接する画像要素と前記画像要素の間における色差の平均として計算される請求項４に記載の方法。
【請求項７】
前記比が所定のしきい値を超える場合、画像要素が複数のカテゴリのうち１つとして分類され、そうでなければ、前記画像要素が前記複数のカテゴリのうち別の１つとして分類される請求項１に記載の方法。
【請求項８】
画像要素を分類する方法であって、
前景層と背景層が交差する前記画像要素の部分を特定するステップ、
前記交差する部分を前記画像要素の閉じられた部分として識別するステップ、
前記閉じられた部分を除去して前記画像要素の形状を決めるステップ、
前記画像要素の開区間長と閉区間長を計算するステップ、
前記画像要素の開区間長と前記画像要素の閉区間長との比に基づき、前記画像要素を前景層及び背景層からなるカテゴリのうち１つとして分類するステップであって、該開区間長が他の要素によって閉じられていない該画像要素の１以上の部分についての周囲セグメントの長さであり、該閉区間長が該他の要素によって閉じられた要素形状部分を除去した後の該画像要素の可視部分の周囲長である、ステップ、及び
前記カテゴリのうち前記１つと関連する符号化スキームに従って前記画像要素を符号化するステップ
を含む方法。
【請求項９】
前記開区間長が、
【数３】
0004351411.tif 000007
として計算され、ここで、Ｐｏｒｉｇｉｎａｌは画像要素の元の周囲長であって閉塞がないときに画像要素が見せることになる画像要素の元の形状の周囲長であり、Ｐｏｃｃｌｕｄｅｄは前記閉区間長であり、かつＰｏｃｃｌｕｓｉｏｎは前記他の要素によって閉じられる前記画像要素の部分の周囲長である請求項８に記載の方法。
【請求項１０】
前記閉区間長が、
Ｒ−２Ｌ
として計算され、ここで、Ｒは画像要素の各水平走査線の周囲長の合計であり、かつＬは各水平走査線と前記画像要素の次の水平走査線との間における接触セグメントの長さの合計である請求項８に記載の方法。
【請求項１１】
各画像要素が周囲長を有する電子画像から生成された画像要素を分類する方法であって、
前景層および背景層のそれぞれを空であるように初期設定するステップと、
前記画像要素を前記前景層と前記背景層のうち１つとして反復して分類するステップとを含み、
第ｉ番の画像要素に関して、
前記前景層および前記背景層に属するものとして以前に分類された他の画像要素によって閉じられない画像要素の量を判定するステップと、
前記画像要素の開区間長の閉区間長に対する比が所定のしきい値を超えたとき、前記画像要素を前記前景層に属するものとして分類し、そうでなければ、前記背景層として分類するステップであって、該開区間長は他の要素によって閉じられていない該画像要素の１以上の部分についての周囲セグメントの長さであり、該閉区間長は該他の要素によって閉じられた要素形状部分を除去した後の該画像要素の可視部分の周囲長である、ステップと
を含む方法。
【請求項１２】
複数のカテゴリのうち１つと関連する符号化スキームに従って画像要素を符号化するステップをさらに含む請求項１１に記載の方法。
【請求項１３】
複数のカテゴリと関連する符号化スキームがそれぞれ画像圧縮スキームである方法であって、背景層の前記圧縮スキームが、前景層の前記圧縮スキームよりも比較的高い圧縮比と画像損失で符号化された出力を実現する請求項１２に記載の方法。
【請求項１４】
前記開区間長が、
【数４】
0004351411.tif 000008
として計算され、ここで、Ｐｏｒｉｇｉｎａｌは画像要素の元の周囲長であって閉塞がないときに画像要素が見せることになる画像要素の元の形状の周囲長であり、Ｐｏｃｃｌｕｄｅｄは前記閉区間長であり、かつＰｏｃｃｌｕｓｉｏｎは前記他の要素によって閉じられる前記画像要素の部分の周囲長である請求項１３に記載の方法。
【請求項１５】
前記閉区間長が、
Ｒ−２Ｌ
として計算され、ここで、Ｒは画像要素の各水平走査線の周囲長の合計であり、かつＬは各水平走査線と前記画像要素の次の水平走査線との間における接触セグメントの長さの合計である請求項１３に記載の方法。
【請求項１６】
画像要素を符号化する方法であって、
前記画像要素の開区間長と前記画像要素の閉区間長との比が、しきい値を超えているかどうか判定するステップ、
前記比が前記しきい値を超えている場合、前記画像要素を前景層に属するものとして分類するステップであって、該開区間長が他の要素によって閉じられていない該画像要素の１以上の部分についての周囲セグメントの長さであり、該閉区間長が該他の要素によって閉じられた要素形状部分を除去した後の該画像要素の可視部分の周囲長である、ステップ、
前記比が前記しきい値を下回る、または前記しきい値に等しい場合、前記画像要素を背景層に属するものとして分類するステップ、及び
前記画像要素が前記前景層に属するものとして分類されているか、または前記背景層に属するものとして分類されているかに基づき、前記画像要素を符号化するステップ
を含む方法。
【請求項１７】
前記開区間長が、
【数５】
0004351411.tif 000009
として計算され、ここで、Ｐｏｒｉｇｉｎａｌは画像要素の元の周囲長であって閉塞がないときに画像要素が見せることになる画像要素の元の形状の周囲長であり、Ｐｏｃｃｌｕｄｅｄは前記閉区間長であり、かつＰｏｃｃｌｕｓｉｏｎは前記他の要素によって閉じられる前記画像要素の部分の周囲長である請求項１６に記載の方法。
【請求項１８】
前記閉区間長が、
Ｒ−２Ｌ
として計算され、ここで、Ｒは画像要素の各水平走査線の周囲長の合計であり、かつＬは各水平走査線と前記画像要素の次の水平走査線との間における接触セグメントの長さの合計である請求項１６に記載の方法。
【請求項１９】
プロセッサによる実行のためのプログラム命令を含む機械可読記憶媒体であって、前記命令は、前記プロセッサによって実行されたとき、開区間長を他の要素によって閉じられていない該画像要素の１以上の部分についての周囲セグメントの長さと定義し、閉区間長を該他の要素によって閉じられた要素形状部分を除去した後の該画像要素の可視部分の周囲長と定義した場合に、前記画像要素の開区間長と前記画像要素の閉区間長との比に基づいて画像要素を前景層及び背景層からなるカテゴリのうち１つに割り当てることを前記プロセッサが行うようにさせる機械可読記憶媒体。
【請求項２０】
前記プロセッサが、前記カテゴリのうち１つと関連する符号化スキームに従って前記画像要素を符号化するようにさらに構成された請求項１９に記載の機械可読記憶媒体。
【請求項２１】
前記カテゴリと関連する符号化スキームがそれぞれ画像圧縮スキームである機械可読記憶媒体であって、前記背景層の前記圧縮スキームが、前記前景層の前記圧縮スキームよりも比較的高い圧縮比と画像損失で符号化された出力を実現する請求項２０に記載の機械可読記憶媒体。
【請求項２２】
前記開区間長が、
【数６】
0004351411.tif 000010
として計算され、ここで、Ｐｏｒｉｇｉｎａｌは画像要素の元の周囲長であって閉塞がないときに画像要素が見せることになる画像要素の元の形状の周囲長であり、Ｐｏｃｃｌｕｄｅｄは前記閉区間長であり、かつＰｏｃｃｌｕｓｉｏｎは前記他の要素によって閉じられる前記画像要素の部分の周囲長である請求項１９に記載の機械可読記憶媒体。
【請求項２３】
前記閉区間長が、
Ｒ−２Ｌ
として計算され、ここで、Ｒは画像要素の各水平走査線の周囲長の合計であり、かつＬは各水平走査線と前記画像要素の次の水平走査線との間における接触セグメントの長さの合計である請求項１９に記載の機械可読記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、一般に画像処理に関し、より詳細には、画像要素を分類するための方法、システム、および機械可読媒体に関する。
【０００２】
【従来の技術】
多くの画像が、画像のピクセルに基づく表現を利用しないコンピュータ化された方法を使用して生成されている。例えば、テキスト処理ソフトウェアは、テキスト、フォント、カラー、組込み画像などの画像の高レベル要素を記述する構造化されたページ情報を使用して画像を表す。この構造化されたページ情報には、ＭＳＷｏｒｄ（商標）ｄｏｃファイル、Ａｄｏｂｅ（商標）ＰＤＦファイル、またはＰｏｓｔＳｃｒｉｐｔ（商標）ファイルなどの多種多様なファイル形式がある。情報は、印刷される、または他の仕方でレンダリングされる際、画像を増分式に構成する一連のオーバーレーされる画像要素に変換される可能性がある。
【０００３】
しばしば、これらの画像を圧縮、すなわち、符号化する必要が存在する。一般に、画像要素は、まず、何らかの分類基準に基づいて前景または背景に分類される。分類の後、前景がより高い解像度で符号化される。というのは、それが関心の要素を含むからである。他方、背景は、通常、より低い解像度で符号化される。というのは、それがより関心の低い要素を含むからである。そのような符号化戦略は、当技術分野では周知のものであり、例えば、ＭＰＥＧ、ＪＰＥＧ等である。したがって、要素分類の品質が、これらの画像の圧縮比およびビデオ品質に大きく影響することになる。このため、分類を効果的に行うことが重要である。
【０００４】
構造化されたページ情報からレンダリングされる画像に関する現行の要素分類手法は、画像内のすべてのテキストを前景として、また他のすべての詳細を背景として分類するステップと、すべての単色要素を前景として、また他のすべての要素を背景として分類するステップと、および描かれる第１の要素を背景として、またすべての他の要素を前景として分類するステップとを含む。ただし、これらの手法のすべてが効果的ではなく、特に地理的な地図に関してはそうである。とうのは、関心の要素が、ときとして、実際には前景要素であるにも関わらず、背景分類のための基準を満たすようにレンダリングされるからである。この結果、これらの関心の要素が、誤ってより低い解像度で符号化される。このため、これらの要素の圧縮効率およびビデオ品質が相当に低下する。
【０００５】
したがって、当技術分野において、一般に、画像要素を分類する、また特に、構造化されたページ情報、例えば、電子文書からレンダリングされる画像要素を分類する効果的な方策の必要性が存在する。
【０００６】
【発明が解決しようとする課題】
本発明は、複数のカテゴリのうち１つとして画像要素を分類するための方法を提供する。この方法は、画像要素の閉じられない周囲長と、他の画像要素によって閉じられた画像要素の周囲長との比に基づいて画像要素を分類するステップを含む。その後、画像要素は、その画像要素がそこに分類されたカテゴリと関連する符号化スキームに従って符号化されることが可能である。
【０００７】
【課題を解決するための手段】
本発明の実施形態は、要素の閉じられない周囲長（開区間長、以下同じ）と、要素の閉じられた周囲長（閉区間長、以下同じ）との比に基づき、複数のカテゴリのうち１つとして画像要素を分類するための技法を提供する。画像要素の閉じられた周囲長は、通常、他の画像要素がその要素の上にオーバーレーされているとき、その要素の閉じられない周囲長とは異なる。したがって、この比は、どれだけ画像要素が他の画像要素によってブロックされているかという量の良好な見積りを提供することができる。符号化の誤りを高い度合いで閉じられた画像要素に「プッシュする」ことにより、高い度合いで圧縮された画像の知覚される品質を効果的に向上させることができる。
【０００８】
【発明の実施の形態】
本発明は、画像要素が前景層と背景層のうち１つに属するものとして分類されることが可能な画像圧縮に適用することができる。図１Ａは、本発明を実現する画像圧縮システムのブロック図である。このシステムは、レンダリング・エンジン１０と、分類器２０と、前景コーダ３０と、背景コーダ４０とを含む。レンダリング・エンジン１０は、圧縮されるべき画像を生成する。レンダリング・エンジン１０は、印刷ドライバまたはテキスト処理ソフトウェアであることが可能であるが、それらには限定されない。分類器２０は、画像要素を前景要素または背景要素として分類することによって画像を処理する。前景として分類された要素は、任意の符号化技法に従って前景コーダ３０によって符号化されることが可能である。同様に、背景として分類された要素は、任意の符号化技法に従って背景コーダ４０によって符号化されることが可能である。例としての符号化技法は、当技術分野では周知のものである。そのような技法は、独立に使用すること、または、例えば、Ｌ．Ｂｏｔｔｏｕ他による「Ｊｏｕｒｎａｌ  ｏｆ  Ｅｌｅｃｔｒｏｎｉｃ  Ｉｍａｇｉｎｇ，７（３）：４１０−４２５，１９９８」掲載の「Ｈｉｇｈ  Ｑｕａｌｉｔｙ  Ｄｏｃｕｍｅｎｔ  Ｉｍａｇｅ  Ｃｏｍｐｒｅｓｓｉｏｎ  ｗｉｔｈ  ＤｊＶｕ」に記載される符号化技法と併せて使用することが可能である。通常、前景符号化技法および背景符号化技法は、画像品質の損失がより少なく前景画像要素が圧縮されるように選択することになる。他方、背景画像要素は、より高い圧縮で符号化され、画像品質の損失が比較的高くなることになる。
【０００９】
画像圧縮の用途は、単に、実施例としてのものであり、画像要素分類が行われるようなどの用途でも本発明を使用できることを理解されたい。さらに、カテゴリの数は２つに限られないことも理解されたい。
【００１０】
実施例としての画像圧縮では、画像要素の閉じられない周囲長と閉じられた周囲長との比が低いことは、その要素が背景層に属するものとして分類されている場合、その要素の境界に関するどのような符号化の誤りも、他の閉塞を行う要素によって前景層から覆い隠される可能性が高いのを示している可能性がある。したがって、その符号化の誤りは、気が付かれる可能性が低い。これとは対照的に、画像要素の閉じられない周囲長と閉じられた周囲長との比が高いことは、その境界に関する符号化の誤りが認識される可能性が高いのを示している可能性がある。というのは、それらの誤りが他の要素によって覆い隠されないからである。この場合、その要素を前景層に符号化することが適切である可能性がある。したがって、本発明は、圧縮画像のより高い圧縮比と向上した視覚的品質を提供する。
【００１１】
前景要素を符号化するためのビット数は、その要素の可視部分（すなわち、他の要素によって閉じられた要素形状部分を除去した後の）の周囲長Ｐｏｃｃｌｕｄｅｄに正比例することが可能である。前景要素による閉塞から生じる背景要素の縁は、閉塞を行う前景要素の境界によって規定される可能性がある。したがって、背景要素を符号化するためのビット数は、前景要素の一部として既に符号化されている可能性がある背景要素の閉じられた部分を除外することによって減少させることができる。したがって、背景要素を符号化するためのビット数は、前景要素による閉塞から生じたものではない周囲セグメントの長さＰｕｎｏｃｃｌｕｄｅｄに正比例することが可能である。さらに、比例係数は、要素の境界上の色差に依存する。
【００１２】
図１Ｂは、本発明の実施形態による方法の流れ図である。本発明によれば、画像分類システムは、画像要素の閉じられない周囲長Ｐｕｎｏｃｃｌｕｄｅｄ（１００）、および他の画像要素によって閉じられたときのその画像要素の周囲長Ｐｏｃｃｌｕｄｅｄ（１１０）を計算する。システムは、これらの計算した値の比を所定のしきい値Ｔ（１２０）と比較する。
0004351411.tif 000002
ＰｕｎｏｃｃｌｕｄｅｄのＰｏｃｃｌｕｄｅｄに対する比がこのしきい値を超える場合には、システムは、その画像要素を前景要素（１４０）に属するものとして分類する。そうでなければ、システムは、その画像要素を背景要素（１３０）に属するものとして分類する。実施例としてのしきい値Ｔは、８０％である。次に、システムは、要素分類（１５０）に基づき、前景符号化スキームまたは背景符号化スキームを使用して画像要素を符号化する。
【００１３】
オプションとして、システムは、何らかの所定タイプの画像要素を前景層または背景層に割り当てる。例えば、システムは、前景層にテキストまたは記号を事前割当てすることができる。前景はより高い解像度で符号化することができるので、テキストおよび記号を前景として符号化することにより、それらの可読性が向上する。
【００１４】
本発明のすべてまたはその部分は、いくつかの態様がオプションであるため、画像要素を分類するための他の方法と関連して使用することができる。例えば、テキストが前景層に自動的に割り当てられることが可能な場合、本方法をテキスト画像要素に適用する必要はない。
【００１５】
本発明によって処理される画像要素は、画像要素の構成要素および画像内のその座標を記述する構造化されたページ情報として最初に表現されることが可能である。これらの構成要素のほとんどは、「長方形を塗りつぶす」、「線を描く」、または「テキストを描く」などの簡単な動作である。これらの動作は、単に、要素形状と呼ばれる一組の指定された部分に単一カラーを割り当てる。後の動作が、前の動作によって生成された画像データに上書きする可能性がある。印刷動作により、それが完了したとき、完成した印刷出力（しばしば、ページである）がレンダリングされる。
【００１６】
本発明において、システムは、その構造化されたページ情報から画像要素を処理し、画像要素座標が読み取られ、前景層および背景層と比較されるようにする。この比較から、システムは、画像要素の閉じられた部分を判定する。次に、システムは、画像要素を前景層または背景層にレンダリングする。
【００１７】
図２は、画像要素周囲長を計算するための実施例としての方法の流れ図である。本方法は、前景層および背景層と画像要素形状の間でいくつかのブール演算を行う。この実施形態では、これらの層および形状は、ランレングス符号化を使用して表現することができる。ランレングス符号化では、層および画像要素の各走査線（または行）が、黒のビットと白のビットの連続するランを記述する一連の長さによって表される。ランは、走査線の左から右への走査において遭遇する隣接する一群の０（白のビット）または１（黒のビット）である。実施例として、黒のビットは画像要素を表し、また白のビットは非要素空間を表す。したがって、システムは、「黒のビット」のランに対して単一回のパスを行い、層または要素形状の各走査線を左から右に走査することにより、ランレングス符号化された層または要素形状の周囲長を計算する（２００）。
【００１８】
各「黒のビット」のランごとに、システムは、ランの長さの２倍、すなわち、ビット数および幅の２倍を加算することによってランの周囲長ｒを計算する（２０５）。長さの値および幅の値は、それぞれ、頂部の長さおよび底部の長さ、ならびに端部の幅を計算に入れるため、２倍にする。次に、システムは、ランと次の走査線内の隣接するラン、すなわち、ランに隣接し、同一の層または同一の要素形状の一部である次の走査線内のラン・ビットの間の各接触セグメントの長さｌを計算する（２１０）。
【００１９】
すべてのランを処理した後、システムは、すべての周囲長ｒを合計してＲを生成し、またすべての接触の長さｌを合計してＬを生成する（２２０）。隣接するランの周囲長は、同じ接触の長さを含むので、システムは、合計Ｌを２倍にして、重複する包含を計算に入れる。システムは、層または要素形状の周囲長をＰ＝Ｒ−２Ｌとして計算する（２３０）。
【００２０】
図３は、実施例としての画像要素に関する図２の周囲長の計算を示している。この実施例では、画像要素３００は、５つの走査線から構成されている。各走査線は、第３の走査線を例外として、単一の「黒のビット」のランを有している。第３の走査線は、「白のビット」のランによって隔てられた２つの「黒のビット」のランを有している。システムは、各「黒のビット」のラン３１０の周囲長ｒを判定する。次に、システムは、ラン３１０の周囲長ｒの合計Ｒを計算する。システムは、隣接するランの間における接触セグメント３２０を検出し、それらすべての長さｌを合計し、その合計を２倍にして２Ｌを生成する。画像要素３００の周囲長Ｐは、Ｒ−２Ｌに等しい。
【００２１】
他の技法によって計算された周囲長も本発明によって使用されることが可能であるので、この周囲長計算は、単に、実施例としてのものであることを理解されたい。そのような技法には、輪郭マッピング法および領域成長法が含まれるが、それらには限定されない。
【００２２】
図４は、画像要素の閉じられない部分と閉じられた部分を検出するための実施例としての方法を示し、これらの部分に関してシステムが、例えば、図２の方法を使用して周囲長を計算して、画像要素を前景層または背景層に属するものとして分類するようにする。第１に、システムは、２つの空の層ＦおよびＢを作成して、前景または背景として分類されるべき画像要素を表す。次に、システムは、一番上の要素から開始して一番下の要素に向って進み、すべての画像要素に対して以下のことを行う。
【００２３】
システムは、画像要素の周囲長Ｐｏｒｉｇｉｎａｌを計算する（４００）。これは、閉塞がないときに画像要素が見せることになる画像要素の元の形状の周囲長である。次に、システムは、現在の画像要素上に描かれた背景画像要素によって閉じられた画像要素形状の部分を判定する（４０５）。これは、画像要素形状と現在の背景Ｂの交差を計算することによって達せられる。例えば、所与の画像要素部分ｉに関して、現在の背景部分Ｂ（ｉ）がある値を有する場合には、その画像要素部分ｉは、閉じられたものとして指定され、除去される。
【００２４】
処理される第１の画像要素に関しては、すなわち、一番上の要素に関しては、背景Ｂは空であり、したがって、除去すべき閉じられた部分は全く存在しない。後続の要素に関しては、背景が前に処理された閉塞を行う要素を含む場合、システムが閉じられた部分を画像要素形状から除去する（４１０）。
【００２５】
次に、システムは、現在の画像要素上に描かれる前景画像要素によって閉じられる合成要素形状の部分を判定する（４２０）。これは、画像要素形状と現在の前景Ｆの交差を計算することによって達せられる。例えば、所与の画像要素部分ｉに関して、現在の前景部分Ｆ（ｉ）がある値を有する場合には、その画像要素部分ｉは、閉じられたものとして指定され、除去される。
【００２６】
処理される第１の画像要素に関しては、すなわち、一番上の要素に関しては、前景Ｆは空であり、したがって、除去すべき閉じられた部分は全く存在しない。後続の要素に関しては、前景が前に処理された閉塞を行う要素を含む場合、システムが閉じられた部分を画像要素形状から除去する（４２５）。次に、システムは、前景要素および背景要素によって閉じられる部分の周囲長Ｐｏｃｃｌｕｓｉｏｎを計算する（４３０）。
【００２７】
合成画像要素形状は、画像要素の可視部分だけを含む。次に、システムは、その要素の閉じられた周囲長Ｐｏｃｃｌｕｄｅｄおよびその要素の閉じられない周囲長Ｐｕｎｏｃｃｌｕｄｅｄを計算し（４４０）、ただし、
Ｐｏｃｃｌｕｄｅｄ＝Ｒ−２Ｌ    （２）
前述したとおり、可視部分の周囲長。そして、
0004351411.tif 000003
可視境界の周囲長、ただし、閉じられた周囲長と元の周囲長の合計は、画像要素の閉じられない周囲長を２倍にしたものに、除去された閉じられた部分の周囲長を足したものに等しい。
【００２８】
図５Ａ−５Ｃは、本発明の方法に従って検出された画像要素の例としての閉じられた部分と閉じられない部分を示している。図５Ａは、「ａｂ」画像要素７１０によって閉じられた多角形画像要素７００を示している。多角形７００の閉じられた周囲長Ｐｏｃｃｌｕｄｅｄ、すなわち、その閉じられた部分が除去されている可視部分の周囲長を図５Ｂに示している。多角形７００の閉じられない周囲長Ｐｕｎｏｃｃｌｕｄｅｄ、すなわち、非連続の可視境界（実線で示す）を図５Ｃに示している。
【００２９】
図６は、多角形７００の閉じられない周囲長を判定するのに使用する数式（３）を示している。元の周囲長Ｐｏｒｉｇｉｎａｌと閉じられた周囲長Ｐｏｃｃｌｕｄｅｄの合計は、閉じられない周囲長Ｐｕｎｏｃｃｌｕｄｅｄを２倍にしたものに、閉じられた部分の周囲長Ｐｏｃｃｌｕｓｉｏｎを足したものに等しい。
【００３０】
画像要素の閉じられない部分と閉じられた部分を検出するためのこの方法は、この方法の多くの変形形態が本発明によって使用されることが可能であるため、単に実施例としてのものであることを理解されたい。
【００３１】
オプションとして、その比に色差δを含めることができる。
0004351411.tif 000004
【００３２】
色差を使用して、画像要素のカラーが背景のカラーとどれほどよく一致するかを判定することができる。それらのカラーがよく一致する場合には、その画像要素の縁はあまり明確ではなく、したがって、その要素が背景に属している可能性が高い。
【００３３】
一般に、画像要素上における複数回のパスを使用して、その要素が前景に属するか、または背景に属するかを判定する。これを行うのは、現在の要素の下に位置する要素が、背景要素ではなく、前景要素であると判明する可能性があり、これにより、現在の要素の周囲長に影響を与える可能性があるからである。本発明では、色差の計算により、現在の要素が背景に割り当てられている可能性を推定することができ、これにより、画像要素上における単一回のパスで、その要素が前景であるべきか、背景であるべきかを判定することができるようになる。
【００３４】
色差の計算は非常に高価であるので、２つの実施例としての単純化を使用することができる。図７Ａが、第１の実施例の流れ図である。システムは、要素境界と隣接する背景要素のそれぞれとの間の色差を計算する（５００）。次に、システムは、これらの色差のうち最大のものをδとして選択する（５１０）
【００３５】
図７Ｂは、第２の実施例を示している。システムは、所定の数の背景要素を選択する（５５０）。システムは、背景要素の全体のサイズおよび形状に応じて画像要素上における予備パス中に、これらの背景要素をヒューリスティックに判定する。つまり、そのバウンディング・ボックス（すなわち、要素のまわりの想像上の境界）に比べて大きい面積を有し、また現在の画像要素と重なり合う面積が大きい、ソリッド長方形などの画像要素は、背景である可能性がある要素である。このため、色差を計算するのに、その画像要素を使用することができる。反対に、バウンディング・ボックスに比べて小さい面積を有し、また現在の画像要素と重なり合う面積が小さい、長く薄い曲線などの画像要素は、背景である可能性がある要素ではない。このため、色差を計算するのに、その画像要素を使用することはできない。
【００３６】
システムは、背景要素を選択した後、選択した隣接する背景要素のそれぞれと要素境界との間の色差を計算する（５６０）。次に、システムは、それらの色差をδとして平均する（５７０）。
【００３７】
色差を計算するための説明した方法は、色差を計算する多くの技法を本発明において使用することができるため、単に実施例としてのものであることを留意されたい。そのような技法には、階調度測定が含まれるが、それには限定されない。
【００３８】
図８は、本発明の別の実施形態による方法の流れ図である。本発明によれば、画像分類システムが、前景層Ｆおよび背景層Ｂを空に初期設定する（５８０）。次に、システムは、各画像要素を反復して分類する（５８２）。
【００３９】
各画像要素ごとに、システムは以下のことを行う。システムは、前景層および背景層と交差する画像要素の部分を判定し（５８３）、次に、その交差する部分をその画像要素の閉じられた部分として識別して、それらの部分を除去する（５８４）。次に、システムは、画像要素の閉じられない周囲長Ｐｕｎｏｃｃｌｕｄｅｄを計算し（５８５）、また画像要素の閉じられた周囲長Ｐｏｃｃｌｕｄｅｄを計算する（５８６）。システムは、数式（１）のとおり、これらの計算した周囲長の比を所定のしきい値Ｔに対して比較する（５８７）。ＰｕｎｏｃｃｌｕｄｅｄのＰｏｃｃｌｕｄｅｄに対する比がこのしきい値を超える場合には、システムは、その画像要素を前景層に属するものとして分類する（５８９）。そうでなければ、システムは、その画像要素を背景層に属するものとして分類する（５８８）。実施例としてのしきい値Ｔは、８０％である。オプションとして、システムは、数式（４）のとおり、この比に色差を含める。
【００４０】
すべての画像要素を分類した後、システムは、次に、前景層および背景層をそのそれぞれの符号化スキームを使用して符号化する（５９０）。
【００４１】
図９は、本発明に従ってセグメント化することができる実施例としての電子的に生成された画像を示している。システムは、画像６００を互いに重なって描かれた一連の基本画像要素６１０ないし６５５に分解し、ここで、この順序列の前６１０と後ろ６５５は、この順序列内の一番上の画像要素および一番下の画像要素をそれぞれ示す。つまり、システムは、前の画像要素を最後に、また後ろの画像要素を初めに印刷する。システムは、所与の画像形式を処理する印刷ソフトウェアを使用して、図９に示すとおり、基本画像要素６１０ないし６５５を別々に印刷することができる。
【００４２】
本発明によれば、システムは、最初に、前景および背景として分類される画像要素を表す空の前景層Ｆおよび空の背景層Ｂを準備する。次に、システムは、本発明の方法に従って第１の要素６１０を処理する。つまり、システムは、例えば、図２の周囲長計算を使用して第１の要素の元の形状の周囲長Ｐｏｒｉｇｉｎａｌを計算する。次に、システムは、例えば、図４のとおり、現在の画像要素の上に描かれる背景画像要素および前景画像要素によって閉じられる第１の要素形状の部分を判定する。層ＦおよびＢは、この時点では、空であるので、第１の要素のどこも閉じられず、その部分のどれも除去されない。したがって、これらの存在しない閉じられた部分の周囲長Ｐｏｃｃｌｕｓｉｏｎはゼロである。
【００４３】
次に、システムは、数式（２）および（３）から第１の要素の周囲長Ｐｏｃｃｌｕｄｅｄおよび周囲長Ｐｕｎｏｃｃｌｕｄｅｄを計算する。オプションとして、システムは、例えば、図７Ａまたは７Ｂのどちらかの方法に従って、第１の要素と背景の間の色差を計算することができる。次に、システムは、閉じられた周囲長と閉じられない周囲長の比を計算する。この比に基づき、システムは、例えば、図１Ｂに示すとおり、前景層または背景層に属するものとして第１の要素を分類する。第１の要素は閉じられないので、閉じられた周囲長と閉じられない周囲長は同じである。したがって、第１の要素は、１という比、または色差があれば、それより高い比を有する。しきい値が８０％に設定される場合（すなわち、０．８）には、第１の要素は前景に割り当てられる。次に、システムは、第１の要素を含めるように前景層Ｆを更新する。
【００４４】
要素６１０、６１５、６２０、６３０、および６３５によって閉じられる閉じられた画像要素６５０のケースでは、層ＦおよびＢは、空ではない可能性がある。というのは、要素６１０ないし６４５が、要素６５０に先立って処理され、分類されていることになるからである。したがって、システムは要素６５０の閉じられた部分を判定し、除去する。要素６５０の閉じられた周囲長Ｐｏｃｃｌｕｄｅｄは、閉じられない周囲長Ｐｕｎｏｃｃｌｕｄｅｄより大きい可能性がある。このため、これらの周囲長の間の比は、しきい値よりも低い可能性がある。その場合、システムは要素６５０を背景として分類する。
【００４５】
システムは、画像要素６１０ないし６５５に対して本発明の方法を繰り返し、これにより、分類された画像要素がもたらされ、次に、これらの要素をシステムが効率的に符号化する。
【００４６】
本発明の機構および方法は、本発明の教示に従ってプログラミングされた汎用マイクロプロセッサを使用して実施することができる。したがって、本発明は、本発明による方法を行うためにプロセッサによって実行されることが可能な命令を含む機械可読媒体も含む。この媒体には、フロッピー・ディスク、光ディスク、ＣＤ−ＲＯＭを含む任意の型のディスク、または電子命令を記憶するのに適した任意の型の媒体が含まれるが、それらには限定されない。
【００４７】
図１０は、本発明を実施することができるコンピュータ・システムの一実施形態のブロック図である。システム７００は、本発明の実施形態により、プロセッサ７２０と通信するバス７１０と、システム・メモリ・モジュール７３０と、記憶装置７４０とを含むことができるが、それらには限定されない。
【００４８】
本発明を実施するのに使用するソフトウェアの構造は、任意の所望の形態をとるのが可能なことを理解されたい。例えば、説明した方法は、単一のプログラム内または複数のプログラム内で実装することができる。
【００４９】
前述した教示に照らして、本発明の多くの変更形態および変形形態が可能である。したがって、添付の特許請求の範囲内で、本明細書に具体的に記載したのとは異なる仕方で方法を実施することが可能であることを理解されたい。
【図面の簡単な説明】
【図１Ａ】本発明を実現するシステムを示すブロック図である。
【図１Ｂ】本発明の方法の実施形態を示す流れ図である。
【図２】画像要素周囲長を計算するための実施例としてのステップを示す流れ図である。
【図３】図２の方法に従って計算された周囲長の例を示す図である。
【図４】閉じられた周囲長および閉じられない周囲長を計算するための実施例としてのステップを示す流れ図である。
【図５Ａ】図４の方法に従って計算された閉じられた周囲長および閉じられない周囲長の例を示す図である。
【図５Ｂ】図４の方法に従って計算された閉じられた周囲長および閉じられない周囲長の例を示す図である。
【図５Ｃ】図４の方法に従って計算された閉じられた周囲長および閉じられない周囲長の例を示す図である。
【図６】閉じられない周囲長の計算を示す図である。
【図７Ａ】画像要素の色差を計算するための実施例としてのステップを示す流れ図である。
【図７Ｂ】画像要素の色差を計算するための実施例としてのステップを示す流れ図である。
【図８】本発明の方法の別の実施形態を示す図である。
【図９】図１Ｂまたは８の方法をそれに適用することができる、互いに重なって描かれる一連の基本画像要素として分解された電子的に生成される画像の例を示す図である。
【図１０】本発明を実施することができるコンピュータ・システムの一実施形態を示すブロック図である。
【図１Ａ】
0004351411.tif 000011
【図１Ｂ】
0004351411.tif 000012
【図２】
0004351411.tif 000013
【図３】
0004351411.tif 000014
【図４】
0004351411.tif 000015
【図５Ａ】
0004351411.tif 000016
【図５Ｂ】
0004351411.tif 000017
【図５Ｃ】
0004351411.tif 000018
【図６】
0004351411.tif 000019
【図７Ａ】
0004351411.tif 000020
【図７Ｂ】
0004351411.tif 000021
【図８】
0004351411.tif 000022
【図９】
0004351411.tif 000023
【図１０】
0004351411.tif 000024