(57)【要約】【課題】走査線番号に関する始点と終点とに基づき符号化した第１及び第２画像データを論理演算処理する際の処理を高速化し、演算処理の時間の短縮化を可能にする画像処理方法を提供する。【解決手段】２つのランレングス符号１１２，１２２について、それぞれのランの集合に外接する外接図形１１９，１２９を算出し、それら外接図形の重なり部分を判定する。また、２つのランレングス符号１１２，１２２について、重なり部分に位置するランと、それ以外のランとに分割する。重なり部分がある場合、重なり部分に位置するそれぞれのランについて論理和で演算処理して各始点と各終点とを求め、それ以外のランについてはそのまま各始点と各終点とを用い、ランレングス符号１１２，１２２の論理和を演算処理する。これにより、重なり部分の判定回数を減少でき、処理を高速化できて、演算処理の時間の短縮化を可能とする。【選択図】図３
2015029172.tif 000002
【特許請求の範囲】
【請求項１】
走査線番号を付与した第１及び第２画像における各ランを、前記走査線番号に関する始点と終点とに基づき符号化した第１及び第２画像データを、演算部により論理和で演算処理する画像処理方法において、
前記演算部が、前記第１及び第２画像データについて、それぞれの前記ランの集合に外接する第１及び第２外接図形を算出する外接図形算出工程と、
前記演算部が、前記第１及び第２外接図形の重なり部分を判定する重なり判定工程と、
前記演算部が、前記第１及び第２画像データについて、前記重なり部分に位置するランと、それ以外のランと、に分割する分割工程と、
前記演算部が、前記重なり部分がある場合、前記第１及び第２画像データにおける前記重なり部分に位置するそれぞれのランについて論理和で演算処理して各始点と各終点とを求め、前記それ以外のランについてはそのまま各始点と各終点とを用い、前記第１及び第２画像データの論理和を演算処理する論理和演算工程と、を備えた、
ことを特徴とする画像処理方法。
【請求項２】
前記論理和演算工程において、前記重なり部分がない場合、全ての前記ランについて、そのまま各始点と各終点とを用い、前記第１及び第２画像データの論理和を演算処理する、
ことを特徴とする請求項１に記載の画像処理方法。
【請求項３】
走査線番号を付与した第１及び第２画像における各ランを、前記走査線番号に関する始点と終点とに基づき符号化した第１及び第２画像データを、演算部により論理積で演算処理する画像処理方法において、
前記演算部が、前記第１及び第２画像データについて、それぞれの前記ランの集合に外接する第１及び第２外接図形を算出する外接図形算出工程と、
前記演算部が、前記第１及び第２外接図形の重なり部分を判定する重なり判定工程と、
前記演算部が、前記第１及び第２画像データについて、前記重なり部分に位置するランと、それ以外のランと、に分割する分割工程と、
前記演算部が、前記重なり部分がある場合、前記第１及び第２画像データにおける前記重なり部分に位置するランについて論理積で演算処理して各始点と各終点とを求め、前記それ以外のランについては空とし、前記第１及び第２画像データの論理積を演算処理する論理積演算工程と、を備えた、
ことを特徴とする画像処理方法。
【請求項４】
前記論理積演算工程において、前記重なり部分がない場合、全ての前記ランについて空とし、前記第１及び第２画像データの論理積の演算処理を不実行とする、
ことを特徴とする請求項３に記載の画像処理方法。
【請求項５】
前記外接図形算出工程において、前記第１及び第２外接図形を、前記走査線番号の方向、及び前記始点と前記終点との方向に関する矩形状として算出する、
ことを特徴とする請求項１ないし４のいずれか１項に記載の画像処理方法。
【請求項６】
請求項１ないし５のいずれか１項に記載の画像処理方法の各工程をコンピュータに実行させるための画像処理プログラム。
【請求項７】
請求項６に記載の画像処理プログラムを記録した、コンピュータで読み取り可能な記録媒体。
【請求項８】
前記符号化した第１及び第２画像データを記憶可能な記憶部と、
請求項１ないし５のいずれか１項に記載の画像処理方法を実行可能な前記演算部と、を備えた、
ことを特徴とする画像処理装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、走査線番号に関する始点と終点とに基づき符号化した第１及び第２画像データを、演算部により論理演算処理する画像処理方法に関する。
【背景技術】
【０００２】
一般に、０及び１、もしくは白及び黒などのように、２つの値だけで構成された２値画像は、各画素の値を保存する２値マトリクスのデータで構成されるが、これをランレングス符号化で圧縮処理した画像データに構成することが行われている。ランレングス符号化とは、画像の走査線方向（水平又は行方向）の黒（又は白）画素の連続する並びを、走査線番号に関する始点と終点とを結ぶランで表現し、各ランの走査線番号と始点及び終点とを用いて２値画像を圧縮画像データにする符号化方法である。２値マトリクスのデータと比較して、ランレングス符号化した画像データは、メモリ使用量が小さくなるという特徴をもっている。
【０００３】
また、ランレングス符号化は、２値画像の圧縮処理だけでなく、画像上の領域を指定する方法としても使用されることがある。画像全域に対して画像処理を行うと演算処理の時間がかかるため、画像上で関心のある領域だけに限定して画像処理を行うことがある。このような領域のことを一般に、関心領域(ROI:Region  Of  Interest)という。ランレングス符号化は、任意形状の領域を表現することが可能であるため、この関心領域の表現方法としても使用されることがある。
【０００４】
ところで、画像処理として、例えば２つの２値画像同士を合成したり、２値画像の関心領域の範囲をさらに限定したりすることがある。この場合、ランレングス符号化された画像データ間で論理積や論理和といった論理演算を行う必要がある。具体的な演算方法として、ランレングス符号化された画像データを２値マトリクスに戻す変換を行い、２値マトリクス間で論理演算を行い、その結果を再度ランレングス符号化するという方法が考えられる。しかし、２値マトリクスへの変換が必要になるため、メモリ使用量が大きく、演算処理の時間も増大するという問題がある。
【０００５】
そこで、ランレングス符号化された画像データを２値マトリクスに戻す変換をせずに、ランレングス符号化された画像データのままで論理演算を行う方法が提案されている（特許文献１参照）。この特許文献１のものは、ランレングス符号化された２つの画像データ間の論理演算として、まず、２つのランレングス符号化された画像データにおける各ラン間の重なりを判定する。そして、重なりがあれば、それらの各ランの始点と終点との大小関係に基づいて、論理演算後のランの始点と終点とを求めている。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特公平３−７６０６５号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
しかし、上記特許文献１におけるランレングス符号化された画像データのままで論理演算を行う方法では、それぞれの画像データにおけるランの個数が増加するにつれて、重なりの判定回数が増加してしまい、つまり演算処理の時間が長くなるという問題がある。
【０００８】
そこで本発明は、走査線番号に関する始点と終点とに基づき符号化した第１及び第２画像データを論理演算処理する際の処理を高速化し、演算処理の時間の短縮化を可能にする画像処理方法を提供することを目的とするものである。
【課題を解決するための手段】
【０００９】
本発明は、走査線番号を付与した第１及び第２画像における各ランを、前記走査線番号に関する始点と終点とに基づき符号化した第１及び第２画像データを、演算部により論理和で演算処理する画像処理方法において、前記演算部が、前記第１及び第２画像データについて、それぞれの前記ランの集合に外接する第１及び第２外接図形を算出する外接図形算出工程と、前記演算部が、前記第１及び第２外接図形の重なり部分を判定する重なり判定工程と、前記演算部が、前記第１及び第２画像データについて、前記重なり部分に位置するランと、それ以外のランと、に分割する分割工程と、前記演算部が、前記重なり部分がある場合、前記第１及び第２画像データにおける前記重なり部分に位置するそれぞれのランについて論理和で演算処理して各始点と各終点とを求め、前記それ以外のランについてはそのまま各始点と各終点とを用い、前記第１及び第２画像データの論理和を演算処理する論理和演算工程と、を備えたことを特徴とする。
【００１０】
また、本発明は、走査線番号を付与した第１及び第２画像における各ランを、前記走査線番号に関する始点と終点とに基づき符号化した第１及び第２画像データを、演算部により論理積で演算処理する画像処理方法において、前記演算部が、前記第１及び第２画像データについて、それぞれの前記ランの集合に外接する第１及び第２外接図形を算出する外接図形算出工程と、前記演算部が、前記第１及び第２外接図形の重なり部分を判定する重なり判定工程と、前記演算部が、前記第１及び第２画像データについて、前記重なり部分に位置するランと、それ以外のランと、に分割する分割工程と、前記演算部が、前記重なり部分がある場合、前記第１及び第２画像データにおける前記重なり部分に位置するランについて論理積で演算処理して各始点と各終点とを求め、前記それ以外のランについては空とし、前記第１及び第２画像データの論理積を演算処理する論理積演算工程と、を備えたことを特徴とする。
【発明の効果】
【００１１】
本発明によると、符号化した第１及び第２画像データについて、それぞれのランの集合に外接する第１及び第２外接図形を算出し、それら第１及び第２外接図形の重なり部分を判定して、重なり部分に位置するランとそれ以外のランとに分割する。
【００１２】
そして、論理和で演算処理する際は、重なり部分に位置するそれぞれのランについて論理和で演算処理して各始点と各終点とを求め、それ以外のランについてはそのまま各始点と各終点とを用い、第１及び第２画像データの論理和を演算処理する。これにより、重なり部分の判定回数を減少でき、かつ重なり部分以外の論理和を簡易な和演算とすることができ、第１及び第２画像データの論理和を演算処理する際の処理を高速化することができて、演算処理の時間の短縮化を可能とすることができる。
【００１３】
また、論理積で演算処理する際は、重なり部分に位置するそれぞれのランについて論理積で演算処理して各始点と各終点とを求め、それ以外のランについては空とし、第１及び第２画像データの論理積を演算処理する。これにより、重なり部分の判定回数を減少でき、かつ重なり部分以外の論理積の演算を省略することができ、第１及び第２画像データの論理積を演算処理する際の処理を高速化することができて、演算処理の時間の短縮化を可能とすることができる。
【図面の簡単な説明】
【００１４】
【図１】本発明の実施の形態に係る画像処理装置を示すブロック図。
【図２】第１の実施の形態に係る論理和演算の画像処理制御を示すフローチャート。
【図３】第１の実施の形態に係るランレングス符号の論理和演算の一例を示す説明図。
【図４】ランレングス符号の一例を示す説明図。
【図５】ランの集合の外接矩形の一例を示す説明図。
【図６】第２の実施の形態に係る論理積演算の画像処理制御を示すフローチャート。
【図７】第２の実施の形態に係るランレングス符号の論理積演算の一例を示す説明図。
【発明を実施するための形態】
【００１５】
＜第１の実施の形態＞
以下、本発明に係る第１の実施の形態を図１乃至図５に沿って説明する。まず、第１の実施の形態に係るランレングス符号化された画像の論理和演算を実行可能な画像処理装置について図１に沿って説明する。
【００１６】
図１に示すように、画像処理装置（コンピュータ）２００は、ＣＰＵ（演算部）２４０、メモリ（記憶部、記録媒体）２１０、Ｉ／Ｆユニット２５０、通信ユニット２２０、制御ユニット２３０、バス２６０等で構成されている。ＣＰＵ２４０は、メモリ２１０に格納されている各種プログラムを読み出して、それらプログラムに基づく各種処理を実行する。メモリ２１０は、ＨＤＤやＲＡＭ、ＲＯＭ等を総称するものであり、上記ＣＰＵ２４０が処理するために必要な各種プログラムや画像（例えば２値化画像、ランレングス符号化された画像等）のデータを記憶可能である。
【００１７】
詳細には、メモリ２１０には、画像処理プログラムとして、外接図形算出プログラム２１１、重なり判定プログラム２１２、ラン分割プログラム２１３、論理演算プログラム２１４が記録格納されている。ＣＰＵ２４０は、詳しくは後述するように、これらの各種プログラムによる各工程として、外接図形（外接矩形）の算出、外接図形の重なり判定、重なり部分とそれ以外とにランを分割、２つのランレングス符号の論理演算、を実行する。なお、本明細書中において、「ランレングス符号」とは、２値画像をランレングス符号化した圧縮画像データのことを意味するものとする。
【００１８】
Ｉ／Ｆユニット２５０は、ディスプレイやスキャナ等の各種入出力デバイスと接続可能であり、それら各種入出力デバイスと信号をやりとりする。通信ユニット２２０は、画像等のデータを、ネットワーク２７０を経由して通信可能である。制御ユニット２３０は、画像処理装置２００全体を制御可能なユニットであり、バス２６０は各ユニット、ＣＰＵ、メモリ等を接続する。
【００１９】
なお、本実施の形態における画像処理の対象の画像データは、ネットワーク２７０を経由して受信したり、またはＩ／Ｆユニット２５０を経由してスキャナから読み取ったりして、メモリ２１０に格納されるものとする。
【００２０】
続いて、本第１の実施の形態に係る画像処理方法について、図２乃至図５に沿って説明する。まず、ランレングス符号について図４を用いて簡単に説明する。ランレングス符号とは、２値画像１００の一走査線上の連続する黒画素の並びを、２値画像１００の画素に関して付与した走査線番号(Row)、及び走査線上の始点(Start)と終点(End)との３組の値で表現したものである。この３組の値をラン（黒ラン）とよび、このランの集合がランレングス符号１０１である。即ち、ランレングス符号１０１では、２値画像１００における各黒画素が、図４に示すように、ランＲ１００ａ，Ｒ１００ｂ，Ｒ１００ｃ，Ｒ１００ｄ，Ｒ１００ｅ，Ｒ１００ｆの集合で表現されることになる。
【００２１】
次に、本第１の実施の形態に係る２つのランレングス符号１１２，１２２の論理和を演算する画像処理方法を説明する。なお、図３に示す説明図においては、発明の理解を容易にするため、ランレングス符号１１２，１２２に対応する、ランレングス符号化する前の２値画像（第１及び第２画像）１１１，１２１を示している。しかしながら、本実施の形態における演算では、ランレングス符号（符号化された第１及び第２画像データ）１１２，１２２を２値画像１１１，１２１に戻すことなく、そのまま論理和を演算するものである。
【００２２】
例えば上記画像処理装置２００により、２つのランレングス符号１１２，１２２の論理和を演算する画像処理を開始する。すると、ＣＰＵ２４０は、外接図形算出プログラム２１１によって、図２に示すように、２つのランレングス符号１１２，１２２のランの集合に外接する外接図形、本実施の形態では矩形状の外接矩形をそれぞれ算出する（外接図形算出工程）（Ｓ１−１）。
【００２３】
外接矩形を使用する利点としては、外接矩形そのものの計算が容易である点と、２つの外接矩形の重なり部分の計算が容易である点が挙げられる。外接矩形は、例えば左上隅の座標(Left,Top)と右下隅の座標(Right,Bottom)の４つのパラメータで表現することができる。各パラメータは、
Top=min{Row1,Row2,…,RowN}
Bottom=max{Row1,Row2,…,RowN}
Left=min{Start1,Start2,…,StartN}
Right=max{End1,End2,…,EndN}
で計算することができる。ただしRowi、Starti、Endiはそれぞれi番目のランの走査線番号及び走査線上の始点と終点との値である。
【００２４】
図５にランレングス符号（第１画像データ）１１２の外接矩形（第１外接図形、第１外接矩形）１１９を２値画像（第１画像）１１１に置き換えて示す。２値画像１１１において、横方向の走査線上に各ランＲ１１１ａ，Ｒ１１１ｂ，Ｒ１１１ｃ，Ｒ１１１ｄ，Ｒ１１１ｅがあるとする。これらランの集合に外接する外接矩形１１９は、最上部にあるランＲ１１１ａの上端(top)が「２」、最左部にあるランＲ１１１ｂ，Ｒ１１１ｃ，Ｒ１１１ｄの左端が「２」である。さらに、最下部にあるランＲ１１１ｅの下端(Bottom)が「６」、最右部にあるランＲ１１１ｂ，Ｒ１１１ｃ，Ｒ１１１ｄの右端が「６」である。従って、外接矩形１１９は、ランの集合における上端(top)の最小値「２」、下端(Bottom)の最大値「６」、左端の最小値「２」、右端の最大値「６」を取得することで矩形状となる。
【００２５】
同様に、図３に示すように、２値画像（第２画像）１２１においては、横方向の走査線上に各ランＲ１２１ａ，Ｒ１２１ｂ，Ｒ１２１ｃ，Ｒ１２１ｄがある。するとＣＰＵ２４０は、ランレングス符号（第２画像データ）１２２の外接矩形（第２外接図形、第２外接矩形）１２９を算出する。つまり、ランの集合における上端(top)の最小値「４」、下端(Bottom)の最大値「７」、左端の最小値「４」、右端の最大値「７」を取得することで外接矩形１２９を算出する。
【００２６】
つまり２つの外接図形として、走査線番号の方向、及び始点と終点との方向に関する矩形状で、それぞれ２つの矩形図形として算出する、そして、この外接矩形１１９，１２９の情報をランレングス符号１１２，１２２と一体としてメモリ２１０に保存しておく。
【００２７】
続いて、図２に示すように、ＣＰＵ２４０は、重なり判定プログラム２１２により、外接矩形１１９，１２９の重なり部分を求める（重なり判定工程）（Ｓ１−２）。外接矩形の重なりの判定は、
矩形の重なり条件１：Top1>Bottom2
矩形の重なり条件２：Bottom1<Top2
矩形の重なり条件３：Left1>Right2
矩形の重なり条件４：Right1<Left2
のいずれか一つの条件でも満足する場合に重なりなしと判定する。また、いずれか一つの条件でも満足する場合には重なりありと判定する。ただし、Top1、Bottom1、Left1、Right1は一方の外接矩形の上端、下端、左端、右端を、Top2、Bottom2、Left2、Right2は他方の外接矩形の上端、下端、左端、右端を表す。
【００２８】
２つの外接矩形の重なり部分がある場合は、その重なり部分は矩形となり、
Topoverlap=max{Top1,Top2}
Bottomoverlap=min{Bottom1,Bottom2}
Leftoverlap=max{Left1,Left2}
Rightoverlap=min{Right1,Right2}
で計算することができる。図３の例では、外接矩形１１９と外接矩形１２９の重なりがあり、その重なり部分は矩形１３１として表すことができる。このように、ステップＳ１−１で外接矩形１１９，１２９を算出しておくことで、ランレングス符号１１２，１２２の重なりの判定を高速に行うことが可能となる。
【００２９】
ステップＳ１−３において、仮に２つの外接矩形で重なりがないと判定されれば（Ｓ１−３のＮｏ）、つまり２つのランレングス符号の重なりがないことが分かる。その場合にはステップＳ１−６に進み、２つのランレングス符号におけるランどうしを比較することなく、２つのランレングス符号のランをまとめた（合成した）ランレングス符号が論理和の演算結果となる。つまり、全てのランについて、そのまま各始点と各終点とを用い、２つのランレングス符号の論理和を演算処理することになる。
【００３０】
一方、ステップＳ１−３において、図３に示す例のように２つの外接矩形１１９，１２９で重なりがあると判定されれば（Ｓ１−３のＹｅｓ）、ステップＳ１−４に進む。すると、ラン分割プログラム２１３により、ランレングス符号１１２，１２２の重なり部分とそれ以外の部分とに分割を行う（分割工程）。実際の分割方法としては、ランレングス符号の各ランが重なり部分の矩形に含まれるかを条件：
Bottomoverlap≦Row≦Topoverlap
AND
Start≦Rightoverlap
AND
End≧Leftoverlap
で順に判定すればよい。
【００３１】
即ち、ランレングス符号は、この条件を満足するランの集合である交差ランレングス符号と、満足しないランの集合である非交差ランレングス符号に分割される。図３に示すように、ランレングス符号１１２は、重なり部分の矩形１３１に含まれるランの集合である交差ランレングス符号１１４と、含まれないランの集合である非交差ランレングス符号１１５に分割される。同様にランレングス符号１２２は、重なり部分の矩形１３１に含まれるランの集合である交差ランレングス符号１２４と、含まれないランの集合である非交差ランレングス符号１２５に分割される。要するに、ランレングス符号１１２，１２２の各ランは、重なり部分の矩形１３１に位置するランＲ１１１ｃ，Ｒ１１１ｄ，Ｒ１１１ｅ，Ｒ１２１ａ，Ｒ１２１ｂ，Ｒ１２１ｃと、それ以外のランＲ１１１ａ，Ｒ１１１ｂ，Ｒ１２１ｄとに分割される。
【００３２】
そして、ステップＳ１−５では、論理演算プログラム２１４により、交差ランレングス符号１１４，１２４と非交差ランレングス符号１１５，１２５とに分けて論理和を計算する（論理和演算工程）。まず、２つの非交差ランレングス符号１１５，１２５は、それらのランレングス符号で重なりがないことが分かっているランの集合であるため、そのまま各ランの始点と終点とを走査線番号ごとに論理和演算後のランレングス符号として追加すればよい。
【００３３】
２つの交差ランレングス符号１１４，１２４については、それらのランレングス符号で重なりを確認した上で、論理和演算後のランの始点と終点とを計算する。実際には、交差ランレングス符号１１４と交差ランレングス符号１２４とで同一の走査線番号の重なり（Rowoverlap）をもつランをそれぞれ抽出し、各ランの始点と終点との大小関係を比較することで論理演算後のランの始点と終点とを
Startsum=min{Start1,Start2}
Endsum=max{End1,End2}
で計算する。
【００３４】
ここで図３に示す例で具体的な計算を説明する。交差ランレングス符号１１４と交差ランレングス符号１２４とで共通の走査線番号Rowoverlap=5をもつランに注目すると、それらの和は
Rowsum=5
Startsum=min{2,4}=2
Endsum=max{6,7}=7
で計算でき、これが論理和演算後のランになる。
【００３５】
同様に、走査線番号Rowoverlap=4及び走査線番号Rowoverlap=6の場合も計算することで、交差ランレングス符号１１４と交差ランレングス符号１２４との論理和が得られる。この交差ランレングス符号１１４，１２４の論理和結果と、非交差ランレングス符号１１５，１２５とをまとめることで、ランレングス符号１１２，１２２の論理和の演算結果を得ることができる。
【００３６】
以上のように本第１の実施の形態では、ランレングス符号１１２，１２２について、それぞれのランの集合に外接する外接矩形１１９，１２９を算出し、それらの重なり部分を判定して、重なり部分に位置するランとそれ以外のランとに分割する。そして、重なり部分に位置するそれぞれのランについて論理和で演算処理して各始点と各終点とを求め、それ以外のランについてはそのまま各始点と各終点とを用い、ランレングス符号１１２，１２２の論理和を演算処理する。これにより、重なり部分の判定回数を減少でき、かつ重なり部分以外の論理和を簡易な和演算とすることができ、ランレングス符号１１２，１２２の論理和を演算処理する際の処理を高速化することができて、演算処理の時間の短縮化を可能とすることができる。
【００３７】
＜第２の実施の形態＞
ついで、上記第１の実施の形態を一部変更した第２の実施の形態について主に図６及び図７に沿って説明する。なお、画像処理装置２００の構造、外接図形算出工程、重なり判定工程、ラン分割工程等は、第１の実施の形態と同様であるので、その詳細説明を省略する。上記第１の実施の形態においては、２つのランレングス符号の論理和を論理演算するものを説明したが、本第２の実施の形態では、２つのランレングス符号の論理積を論理演算するものを説明する。以下、論理積の論理演算について、詳細に説明する。
【００３８】
例えば上記画像処理装置２００により、２つのランレングス符号１１２，１２２の論理積を演算する画像処理を開始する。すると、図６及び図７に示すように、第１の実施の形態と同様に（Ｓ１−１参照）、ランレングス符号１１２，１２２におけるランの集合のそれぞれの外接矩形１１９，１２９を計算する（外接図形算出工程）（Ｓ２−１）。また同様に（Ｓ１−２参照）、２つの外接矩形１１９，１２９の重なり部分を求める（重なり判定工程）（Ｓ２−２）。更に同様に（Ｓ１−３参照）、２つの外接矩形１１９，１２９の重なり部分があるか否かを判定する（Ｓ２−３）。
【００３９】
ステップＳ２−３において、２つの外接矩形に重なりがないと判定した場合は（Ｓ２−３のＮｏ）、ステップＳ２−６に進む。ステップＳ２−６では、本第２の実施の形態では論理積の演算であり、２つのランレングス符号で重なるランが無いということになるので、２つのランレングス符号の各ランを比較することなく、２つのランレングス符号の論理積は空という結果を出力する。つまり、重なり部分がない場合、全てのランについて空とし、２つのランレングス符号の論理積の演算処理を不実行とする。これにより、重なり部分がない場合は、論理演算処理を省略でき、演算処理が高速化される。
【００４０】
ステップＳ２−３において、２つの外接矩形に重なりがあると判定した場合は（Ｓ２−３のＹｅｓ）、ステップＳ２−４に進む。ステップＳ２−４においては、第１の実施の形態と同様に（Ｓ１−４参照）、ランレングス符号１１２，１２２を重なり部分とそれ以外とに分割する（分割工程）。
【００４１】
そして、ステップＳ２−５においては、交差ランレングス符号１１４と交差ランレングス符号１２４との論理積を計算する。実際には、交差ランレングス符号１１４と交差ランレングス符号１２４とで同一の走査線番号Rowoverlapをもつランをそれぞれ抽出し、各ランの始点と終点との大小関係を比較することで論理積演算後のランの始点と終点とを
Startprod=max{Start1,Start2}
Endprod=min{End1,End2}
で計算する。
【００４２】
ここで図７に示す例で具体的な計算を説明する。交差ランレングス符号１１４と交差ランレングス符号１２４で共通のRowoverlap=5をもつランに注目すると、それらの重なり部分は
Rowprod=5
Startprod=max{2,4}=4
Endprod=min{6,7}=6
で計算でき、これが論理積演算後のランになる。
【００４３】
同様に、走査線番号Rowoverlap=4及びRowoverlap=6の場合も計算することで、交差ランレングス符号１１４と交差ランレングス符号１２４との論理積が得られる。そして、非交差ランレングス符号１１５，１２５の論理積は空であるので、この交差ランレングス符号１１４，１２４の論理積結果を、ランレングス符号１１２，１２２の論理積の演算結果として得ることができる。
【００４４】
以上のように本第２の実施の形態では、ランレングス符号１１２，１２２について、それぞれのランの集合に外接する外接矩形１１９，１２９を算出し、それらの重なり部分を判定して、重なり部分に位置するランとそれ以外のランとに分割する。そして、重なり部分に位置するそれぞれのランについて論理積で演算処理して各始点と各終点とを求め、それ以外のランについては空とし、ランレングス符号１１２，１２２の論理積を演算処理する。これにより、重なり部分の判定回数を減少でき、かつ重なり部分以外の論理積の演算を省略することができ、ランレングス符号１１２，１２２の論理積を演算処理する際の処理を高速化することができて、演算処理の時間の短縮化を可能とすることができる。
【００４５】
なお、以上説明した第１及び第２の実施の形態では、外接図形が矩形状の外接矩形である場合について説明したが、必ずしも矩形状に限定するものではなく、例えば外接円のような図形であっても構わない。
【符号の説明】
【００４６】
１１１…第１画像（２値画像）：１１２…第１画像データ（ランレングス符号）：１１９…第１外接図形（外接矩形）：１２１…第２画像（２値画像）：１２２…第２画像データ（ランレングス符号）：１２９…第２外接図形（外接矩形）：２００…コンピュータ、画像処理装置：２１０…記録媒体、記憶部（メモリ）：２１１，２１２，２１３，２１４…画像処理プログラム（外接図形算出プログラム、重なり判定プログラム、ラン分割プログラム、論理演算プログラム）：２４０…演算部（ＣＰＵ）：Ｒｏｗ…走査線番号：Ｓｔａｒｔ…始点：Ｅｎｄ…終点：Ｒ１１１ａ〜Ｒ１１１ｅ，Ｒ１２１ａ〜Ｒ１２１ｄ…ラン
【図１】
2015029172.tif 000003
【図２】
2015029172.tif 000004
【図３】
2015029172.tif 000005
【図４】
2015029172.tif 000006
【図５】
2015029172.tif 000007
【図６】
2015029172.tif 000008
【図７】
2015029172.tif 000009