(57)【要約】【課題】ノイズの多い環境下では、矩形切り出し処理を高精度に行うことは困難であった。【解決手段】原画像を２値化した画像において、その水平及び垂直方向の黒画素数のヒストグラムを作成し、該ヒストグラムを台形近似することによって、前記２値画像における矩形領域の存在範囲を示す頂点座標を検出する。そして、該存在範囲内における矩形領域の傾き方向を検出することによって、２値画像から矩形領域を高精度に検出することができる。【選択図】　　図３
2004030430.tif 000002
【特許請求の範囲】
【請求項１】
画像から矩形領域を検出する画像処理方法であって、
原画像を２値化した画像において、その水平及び垂直方向の黒画素数のヒストグラムを作成するヒストグラム作成工程と、
該ヒストグラムを台形近似することによって、前記２値画像における矩形領域の存在範囲を検出する矩形範囲検出工程と、
前記存在範囲内における、前記矩形領域の傾き方向を検出する傾き方向検出工程と、
を有することを特徴とする画像処理方法。
【請求項２】
前記矩形範囲検出工程においては、
前記２値画像の水平及び垂直方向における前記ヒストグラムのそれぞれについて台形近似を行い、
前記２値画像の水平及び垂直方向のそれぞれついて、矩形領域の存在範囲を検出する
ことを特徴とする請求項１記載の画像処理方法。
【請求項３】
前記矩形範囲検出工程においては、前記矩形領域に対する複数の頂点座標候補を検出することを特徴とする請求項２記載の画像処理方法。
【請求項４】
前記矩形範囲検出工程においては、前記近似された台形の頂点座標を、前記矩形領域に対する複数の頂点座標候補として検出することを特徴とする請求項３記載の画像処理方法。
【請求項５】
前記傾き方向検出工程においては、前記矩形領域の複数の頂点座標候補から４頂点の座標を特定することを特徴とする請求項４記載の画像処理方法。
【請求項６】
前記傾き方向検出工程においては、
前記矩形領域に対する複数の頂点座標候補に基づいて、該矩形領域の複数の傾き方向を仮定し、
該複数の傾き方向のそれぞれで示される矩形領域について、その外部に存在する黒画素数を計数し、
それぞれの計数結果に基づいて１つの傾き方向を特定することによって、
前記４頂点の座標を特定することを特徴とする請求項５記載の画像処理方法。
【請求項７】
前記傾き方向検出工程においては、
前記矩形領域に対する複数の頂点座標候補に基づいて、該矩形領域の複数の傾き方向を仮定し、
該複数の傾き方向のそれぞれで示される矩形領域について、その内部に存在する黒画素を計数し、
それぞれの計数結果に基づいて１つの傾き方向を特定することによって、
前記４頂点の座標を特定することを特徴とする請求項５記載の画像処理方法。
【請求項８】
さらに、前記傾き方向検出工程において検出された４頂点の座標によって決定される矩形領域に対して、斜行補正を施す斜行補正工程を備えることを特徴とする請求項５記載の画像処理方法。
【請求項９】
前記斜行補正工程においては、バイリニア法による補間を行うことを特徴とする請求項８記載の画像処理方法。
【請求項１０】
前記斜行補正工程においては、ニアレストネイバ法による補間を行うことを特徴とする請求項８記載の画像処理方法。
【請求項１１】
前記矩形範囲検出工程においては、前記矩形領域が長方形であると仮定して、前記ヒストグラムを台形近似することを特徴とする請求項１記載の画像処理方法。
【請求項１２】
前記矩形領域は、写真画像を示す領域であることを特徴とする請求項１１記載の画像処理方法。
【請求項１３】
さらに、多値の原画像を２値化して前記２値画像を得る２値化工程を有することを特徴とする請求項１記載の画像処理方法。
【請求項１４】
前記原画像は、１枚の写真画像が配置された画像であることを特徴とする請求項１３記載の画像処理方法。
【請求項１５】
前記原画像が、複数枚の写真画像が主走査方向に離れた位置に配置された画像である場合、
前記ヒストグラム作成工程においては、前記２値画像を前記写真画像毎に主走査方向で分割し、該分割した２値画像毎に、前記ヒストグラムを作成することを特徴とする請求項１３記載の画像処理方法。
【請求項１６】
前記原画像が、複数枚の写真画像が副走査方向に離れた位置に配置された画像である場合、
前記ヒストグラム作成工程においては、前記２値画像を前記写真画像毎に副走査方向で分割し、該分割した２値画像毎に、前記ヒストグラムを作成することを特徴とする請求項１３記載の画像処理方法。
【請求項１７】
さらに、前記２値画像に対してラベル付けを行うラベリング工程を有し、
前記ヒストグラム作成工程においては、前記ラベル付けされた画素数のヒストグラムを作成することを特徴とする請求項１記載の画像処理方法。
【請求項１８】
前記ラベリング工程は、
前記２値画像において、その内部における黒画素数が所定割合以上であるような所定サイズのブロックを、黒ブロックとして検出する黒ブロック検出工程と、検出された黒ブロック内および該黒ブロックに連結している黒画素について、所定のラベル値で置き換えるラベル付け工程と、
を有することを特徴とする請求項１７記載の画像処理方法。
【請求項１９】
前記黒ブロック検出工程においては、その内部が全て黒画素からなるブロックを、前記黒ブロックとして検出することを特徴とする請求項１８記載の画像処理方法。
【請求項２０】
前記黒ブロック検出工程は、
前記２値画像全体を前記所定サイズのブロックに分割する分割工程と、
前記ブロックごとに黒ブロックであるか否かを判定する判定工程と、
を有することを特徴とする請求項１８記載の画像処理方法。
【請求項２１】
前記黒ブロック検出工程においては、
前記２値画像において前記所定サイズのブロック位置を順次ずらすことによって、黒ブロックを検出することを特徴とする請求項１８記載の画像処理方法。
【請求項２２】
前記黒ブロック検出工程においては、前記２値画像において前記所定サイズの黒ブックが検出されなかった場合に、該所定サイズよりも小さなサイズの黒ブロックを検出することを特徴とする請求項１８記載の画像処理方法。
【請求項２３】
前記ラベル付け工程は、
前記黒ブロック内の基準ラインを前記ラベル値で置き換える基準ラベル付け工程と、
前記前記基準ラインよりも上部に連結している黒画素を前記ラベル値で置き換える上部ラベル付け工程と、
前記前記基準ラインよりも下部に連結している黒画素を前記ラベル値で置き換える下部ラベル付け工程と、
を有することを特徴とする請求項１８記載の画像処理方法。
【請求項２４】
上記黒ブロックは矩形であることを特徴とする請求項１８記載の画像処理方法。
【請求項２５】
上記黒ブロックは多角形であることを特徴とする請求項１８記載の画像処理方法。
【請求項２６】
上記黒ブロックは円形であることを特徴とする請求項１８記載の画像処理方法。
【請求項２７】
画像から矩形領域を検出する画像処理装置であって、
原画像を２値化した画像において、その水平及び垂直方向の黒画素数のヒストグラムを作成するヒストグラム作成手段と、
該ヒストグラムを台形近似することによって、前記２値画像における矩形領域の存在範囲を検出する矩形範囲検出手段と、
前記存在範囲内における、前記矩形領域の傾き方向を検出する傾き方向検出手段と、
を有することを特徴とする画像処理装置。
【請求項２８】
画像から矩形領域を検出する画像処理プログラムであって、
原画像を２値化した画像において、その水平及び垂直方向の黒画素数のヒストグラムを作成するヒストグラム作成工程のコードと、
該ヒストグラムを台形近似することによって、前記２値画像における矩形領域の存在範囲を検出する矩形範囲検出工程のコードと、
前記存在範囲内における、前記矩形領域の傾き方向を検出する傾き方向検出工程のコードと、
を有することを特徴とするコンピュータ可読なプログラム。
【請求項２９】
請求項２８記載のプログラムを記録した記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像処理方法及び画像処理装置に関し、特に矩形画像の検出を行う画像処理方法及び画像処理装置に関する。
【０００２】
【従来の技術】
従来より、原画像から矩形領域を検出し、切り出すためのアルゴリズムが種々提案されている。例えば、特開平８−２３７５３７号においては、まず輪郭抽出を行い、輪郭が直線を成す部分を探すことによって矩形領域の探索を行なう技術が記載されている。
【０００３】
【発明が解決しようとする課題】
しかしながら従来の矩形切り出しのアルゴリズムによれば、ノイズの多い環境下においては、矩形輪郭の直線部分を検出すること、さらに、４つの直線を関連付けて１個の矩形を検出することは困難であった。従って、正確な切り出しを行うことは困難であり、切り出し結果の精度は十分とはいえなかった。
【０００４】
本発明は上述した問題を解決するためになされたものであり、ノイズの多い環境下でも矩形領域を高精度に検出可能とする画像処理方法及び画像処理装置を提供することを目的とする。
【０００５】
【課題を解決するための手段】
上記目的を達成するための一手法として、本発明の画像処理方法は以下の工程を備える。
【０００６】
すなわち、画像から矩形領域を検出する画像処理方法であって、原画像を２値化した画像において、その水平及び垂直方向の黒画素数のヒストグラムを作成するヒストグラム作成工程と、該ヒストグラムを台形近似することによって、前記２値画像における矩形領域の存在範囲を検出する矩形範囲検出工程と、前記存在範囲内における、前記矩形領域の傾き方向を検出する傾き方向検出工程と、を有することを特徴とする。
【０００７】
さらに、前記２値画像に対してラベル付けを行うラベリング工程を有し、前記ヒストグラム作成工程においては、前記ラベル付けされた画素数のヒストグラムを作成することを特徴とする。
【０００８】
【発明の実施の形態】
以下、本発明に係る一実施形態について、図面を参照して詳細に説明する。
【０００９】
＜第１実施形態＞
●システム構成
図１は、本発明が実行されるコンピュータシステムの構成を示すブロック図である。１０１はＣＰＵであり、システム全体の制御を行なう。１０２はキーボードであり、１０２ａのマウスとともにシステムへのデータ入力に使用される。１０３は表示装置であり、ＣＲＴや液晶等で構成されている。１０４はＲＯＭ、１０５はＲＡＭであり、システムの記憶装置を構成し、システムが実行するプログラムやシステムが利用するデータを記憶する。１０６はハードディスク装置（ＨＤＤ）、１０７はフロッピディスク装置（ＦＤＤ）であり、システムのファイルシステムに使用される外部記憶装置を構成している。１０８はプリンタである。
【００１０】
１０９はネットワークＩ／Ｆであり、ＬＡＮまたはＷＡＮに接続している。Ｉ／Ｆ１０９を介して、コンピュータプログラムやデジタル画像等のデータファイルを他のコンピュータシステムとやりとりすることができる。プログラムやデータはハードディスク１０６に記録されたり、直接ＲＡＭ１０５に展開されて実行される。
【００１１】
１１０はイメージスキャナであり、原稿台上の写真や印刷物を読み込んで、多値のデジタル画像データとしてＲＡＭ１０５上に取り込むことができる。
【００１２】
●矩形画像概要
図２に、イメージスキャナ１１０から取り込んで２値化された画像の一例を示す。図中の矩形は、写真等の矩形の原稿画像（以下、矩形画像と称する）を示し、３つの楕円はノイズを示している。なお、同図においては説明のためノイズを簡略化して示したが、実際のノイズ分はサイズも形状も不定であり、その数も数百から数千個程度になることが多い。また、画像の２値化は所定の閾値との比較による周知の単純二値化法を用いるとし、ここでは詳細な説明を省略する。
【００１３】
図２に示す画像は、ＲＡＭ１０５上で幅Ｗ画素、高さＨ画素のビットマップとして保持されている。各画素は１バイトの深さを持ち、黒画素は値２５５、白画素は値０で示されるとする。また、ＲＡＭ１０５上のビットマップは２次元配列としてアクセスできるものとし、該ビットマップの左上を起点として水平方向にｉ番目、垂直方向にｊ番目の画素をｂｕｆ（ｉ，ｊ）と表記する。本実施形態ではこのビットマップから、以下に示す方法によって矩形画像の存在領域の座標を特定する。
【００１４】
●ヒストグラム作成
図３は、図２に示す２値画像においてノイズが存在しない理想的な状態を想定した場合に、水平方向に黒画素を計数したヒストグラムの様子を示す図であり、同図上部が２値画像、下部がヒストグラム例を示す。同図によれば、２値画像の矩形の４頂点に対応して、ヒストグラムが概ね台形をなすことがわかる。なお、実際の２値画像はノイズを含むため、ヒストグラムが完全な台形となることはないが、水平方向における頂点の位置を特定するのに十分な情報を、このヒストグラムの台形形状から得ることができる。
【００１５】
図４は、図３に示したヒストグラムの作成処理を示すフローチャートである。以下、ヒストグラムデータを格納する配列をｈｉｓｔ（）で示す。
【００１６】
先ずステップＳ４０１，Ｓ４０２において、変数ｘ，ｙ及びのそれぞれに値０を代入し、ステップＳ４０３で変数ｈｉｓｔ（ｘ）に値０を代入する。
【００１７】
そしてステップＳ４０４において、ビットマップ上の画素ｂｕｆ（ｘ，ｙ）と値２５５を比較し、異なればステップＳ４０６へ進むが、等しければステップＳ４０５へ進んでｈｉｓｔ（ｘ）を値１だけインクリメントした後、ステップＳ４０６へ進む。
【００１８】
ステップＳ４０６では変数ｙを値１だけインクリメントし、次にステップＳ４０７においてｙとビットマップの高さＨを比較する。ｙとＨが異なればステップＳ４０４へ戻るが、等しければステップＳ４０８へ進んで変数ｘを値１だけインクリメントし、ステップＳ４０９でｘとビットマップ幅Ｗを比較する。ｘとＷが異なればステップＳ４０２へ戻るが、等しければ処理を終了する。
【００１９】
●頂点検出処理
以上の処理によって、黒画素を計数したヒストグラムの配列ｈｉｓｔ（）が得られる。このヒストグラムは図３に示したように、Ｘ軸及び３つの直線で囲まれた台形をなしている。本実施形態ではこの台形において、左辺がＸ軸と交わる位置をａ、左辺と上底が交わる位置をｂ、右辺と上底が交わる位置をｃ、右辺がＸ軸と交わる位置をｄとする。
【００２０】
ここで図５のフローチャートを用いて、ヒストグラムが呈する台形の左辺を解析して、上記位置ａ，ｂを求める方法について説明する。
【００２１】
まずステップＳ５０１において、ｈｉｓｔ（ｘ）が最大になるピーク点Ｐを検出する。図３に示すヒストグラムにおいては、Ｘ＝４００前後の位置に高さ８００のピークがある。次にステップＳ５０２において、点Ｐの前方向に、ピークの半分の高さになる点Ｆを検出する。図３に示すヒストグラムにおいては、Ｘ＝１００前後の位置が点Ｆに相当する。そしてステップＳ５０３で、点Ｆの前方向にピークの１／４の高さになる点Ｆ０を検出し、さらにステップＳ５０４で、点Ｆの後方向にピークの３／４の高さになる点Ｆ１を検出する。
【００２２】
次にステップＳ５０５において、Ｆ０≦Ｘ≦Ｆ１の全ての点について、周知の回帰分析を用いて直線近似を行うことによって、図３に示すような直線Ｌを得る。そしてステップＳ５０６において直線ＬがＸ軸と交わる点を算出し、この点をａとして得る。そしてステップＳ５０７において、直線ＬがピークＰの高さの９８％になる点を算出し、この点をｂとして得る。これは、ピークＰはノイズ分を含んでいるため実際のピークよりも多めに出ていることを考慮して、これを９８％分に補正するためである。以上、図５に示すフローチャートにより、ピークＰの前方向への探索を行って点ａ，ｂを得る例について説明したが、同様にピークＰの後方向に探索を行うことにより、点ｃ、ｄを得ることができる。
【００２３】
また、以上は水平方向の頂点位置検出についての説明であるが、上記説明における縦軸と横軸を反転して全く同様の方法を適用することにより、垂直方向における頂点位置検出を行うことが可能である。これにより図６に示すように、矩形を囲む縦横それぞれ４個の座標値、すなわち８個の変数（ａｘ，ｂｘ，ｃｘ，ｄｘ，ａｙ，ｂｙ，ｃｙ，ｄｙ）を、頂点候補として得ることができる。
【００２４】
ここで、矩形から上記８つの変数は一意に決定されるが、逆に、８つの変数から矩形を決定することはできない。すなわち図７に示すように、８つの変数に基づく矩形としては、その斜行方向（以下、斜行モード）によって４通りの頂点座標が考えられるが、そのいずれであるかを決定することができない。なお図７においては、矩形が完全に水平である特別な場合（不図示）をモード０として、４つの斜行モードをそれぞれ、モード１，２，−１，−２とする。これら各モードで示される画像からは同じ形状のヒストグラムが生成されるため、ヒストグラム以外の他の方法によって、斜行モードを判定する必要がある。
【００２５】
●斜行モード判定
以下、本実施形態における斜行モード判定処理について、詳細に説明する。
【００２６】
上述した図６は、図７に示すモード１の状態に相当するが、図６において斜線で示した２つの三角領域の内側に存在する黒画素を計数すると、理想的には黒画素（図中網点部分）が含まれないため、黒画素の計数結果は０になると考えられる。以下、この図６に示す斜線領域を、モード１のテンプレートと呼ぶ。なお、図７に示す他のモードについても同様に、矩形上部に存在する２つの三角領域を、各モードのテンプレートとする。
【００２７】
ここで図８に示すように、実際にはモード１である矩形画像（図中網点部分）に対してモード２のテンプレート（図中斜線部分）を当てはめると、テンプレートの内側に矩形部分がはみ出してしまうため、黒画素数の計数結果は０にならない。本実施形態ではこの特性を利用して、矩形の斜行モードを判定する。
【００２８】
具体的には、判定対象となる矩形画像に対して４つのモードのテンプレートを適用した場合の黒画素数をそれぞれ計数し、計数結果が最少であるテンプレートを、その画像の斜行モードとして決定する。すなわち、テンプレートへの入り込みの度合いが最も少ない場合が、該矩形画像が最も近似する斜行度合いであるとする。もちろん、テンプレート外に存在する黒画素を計数し、計数結果が最大であるテンプレートによって斜行モードを決定することも可能である。
【００２９】
以上の処理により、２値画像中の矩形領域の４つの頂点座標を特定することができる。従ってこの情報に基づき、原画像に対して周知の斜行補正及び画像切り出し処理を施すことによって、例えばイメージスキャナ１１０上に配置した矩形の写真画像を切り出すことができる。
【００３０】
なお、上記周知の斜行補正処理としては、単純補間法（ニアレストネイバ法）または線形補間法（バイリニア法）を用いることが望ましく、前者は速度に優れ、後者は画質に優れるので、用途に応じて使い分ければ良い。
【００３１】
以上説明したように本実施形態によれば、ノイズの多い環境下であっても、矩形領域を正確に検出することができる。
【００３２】
なお、矩形領域が完全な長方形であれば、理想的なヒストグラムとして、左右の斜辺が対称となる理想的な台形を呈するはずであるが、ノイズの影響により左右の斜辺が対称とはならず、すなわち、図３に示すａ−ｂ間の距離が、ｃ−ｄ間の距離と等しくならないことがある。そのような場合には、ノイズの影響が少ないと考えられる方の斜辺から得られるデータにあわせて、台形近似を行う。具体的には左右の斜辺について、回帰分析による直線近似の精度（直線と実データの間の２乗誤差）を比較して、誤差の少ないほうを採用すれば良い。
【００３３】
同様に、矩形検出の結果として得られた４つの頂点を結んだ矩形が、ノイズの影響で必ずしも長方形にならず、隣り合う辺が直交しないことも考えられる。このような場合も、ノイズの影響が少ないと考えられる方のデータに基づいて、矩形が長方形になるように修正を施すことで、矩形検出の精度を向上することができる。
【００３４】
＜第２実施形態＞
以下、本発明に係る第２実施形態について説明する。なお、第２実施形態におけるシステム構成は上述した第１実施形態と同様であるため、説明を省略する。
【００３５】
上述した第１実施形態においては、画像内に１つの矩形領域が存在する場合について説明した。このような状況としては例えば、イメージスキャナ１１０の原稿台上に１枚の写真を必ずしも水平ではなく載置した状態でスキャンを行い、その後自動的に斜行補正、画像切り出しを行うことで、写真画像を抽出する処理が想定される。
【００３６】
しかしながら、一般的なフラットヘッドスキャナの原稿台はＡ４サイズ程度の原稿の載置を可能とするため、一般的な写真（所謂Ｌ版サイズ）の複数枚を一度に載置することができる。従って、このような複数枚の写真画像を一回のスキャンによって読み取り、得られた画像から写真画像を示す矩形領域だけを切り出すことができれば、スキャン作業の効率化が図れる。
【００３７】
そこで第２実施形態においては、一枚の画像から、複数の矩形画像を検出することを特徴とする。
【００３８】
以下、図９を参照して、第２実施形態における複数の矩形画像の検出処理について説明する。図９の左部は、原稿台の副走査方向（図中長手方向）に２枚の写真を離して配置した際の２値化画像を示し、図９の右部は該２値化画像の副走査方向におけるヒストグラムの様子を示す。同図から分かるように、複数枚の写真が離れて配置されている場合、ヒストグラムに複数個の台形が現れる。従って第２実施形態においてはこのヒストグラムを参照することによって、これら複数の台形の間、すなわち図９において１点鎖線Ｌで示した位置で、画像を二つに切り分ける。すると、以降は上述した第１実施形態で示した方法によって、該切り分けられた各々の領域において、矩形画像をそれぞれ検出することができる。
【００３９】
なお、図９においては複数枚の写真を副走査方向に離して配置した場合について説明したが、これを主走査方向（図中短手方向）に離して配置した場合も同様に、主走査方向についてのヒストグラムを作成することによって、画像を主走査方向で切り分け、それぞれの矩形画像を抽出することができる。
【００４０】
以上説明したように第２実施形態によれば、一枚の画像から複数の矩形画像を検出することができる。
【００４１】
＜第３実施形態＞
以下、本発明に係る第３実施形態について説明する。なお、第３実施形態におけるシステム構成は上述した第１実施形態と同様であるため、説明を省略する。
【００４２】
第３実施形態においては、図２に示すような２値画像に対して理想的なラベリング処理を施すことによってノイズの影響を排除し、矩形画像の検出をより高精度に行うことを特徴とする。
【００４３】
ここで、図２に示す２値画像における理想的なラベリング処理とは、黒画素同士の連結に基づき、例えば上方の矩形オブジェクトに含まれる全ての画素に対して画素値１を与え、下方の矩形オブジェクトに含まれる全画素に対しては画素値２を与えることである。すなわち、微小なノイズ分にはラベルを与えず、画素値２５５のままにしておく。
【００４４】
●ラベリング処理概要
以下、上記理想的なラベリングを実現するためのラベリング方法について、詳細に説明する。
【００４５】
図１０は、図２における上方の矩形オブジェクトを含む左上部分に対応し、第３実施形態における塗りつぶし処理の起点となるブロックの探索方法を説明するための図である。
【００４６】
まず図１０に示すように、図２に示したＷ画素×Ｈ画素のビットマップ全体を、ｗ画素×ｈ画素のブロックに分け、その内部が全て値２５５の黒画素で占められるようなブロック（以下、「黒ブロック」と称する）を図中矢印方向に探索する。図３において黒矩形で示したブロックが、見つかった黒ブロックである。
【００４７】
第３実施形態では、見つかった黒ブロックと黒画素が連結している領域を塗りつぶすことによって、高速なラベリングを実現する。図１１に、第３実施形態におけるラベリング処理全体のフローチャートを示し、説明する。
【００４８】
まずステップＳ１４０１で、変数ｃに値１を代入し、ステップＳ１４０２で黒ブロック探索を行う。この黒ブロック探索処理の詳細については後述する。
【００４９】
次にステップＳ１４０３において黒ブロックが見つかったか否かを判断し、見つかったらステップＳ１４０４へ進むが、見つからなければ処理を終了する。
【００５０】
ステップＳ１４０４では、見つかった黒ブロックを起点にして、黒画素連結領域をラベルｃで塗りつぶす。この塗りつぶし処理の詳細については後述する。
【００５１】
そしてステップＳ１４０５で変数ｃを１だけインクリメントしてステップＳ１４０２に戻り、以上の処理を繰り返す。
【００５２】
この処理の結果、所定以上の大きさを持つオブジェクトのみに対して、ラベル１，２，…，ｃを与えることができる。
【００５３】
●黒ブロック探索処理
以下、図１１のステップＳ１４０２に示した黒ブロック探索処理の詳細を図１２のフローチャートに示し、説明する。
【００５４】
まずステップＳ１５０１〜Ｓ１５０４において、変数ｙ，ｘ，ｊ，ｉをそれぞれ値０で初期化する。そしてステップＳ１５０５でｂｕｆ（ｘ＋ｉ，ｙ＋ｊ）が黒画素を示す２５５であるか否かを判断し、２５５であればステップＳ１５０６へ、２５５でなければステップＳ１５１０へ進む。
【００５５】
ステップＳ１５０６では変数ｉを値１だけインクリメントし、ステップＳ１５０７でｉがブロック幅を示すｗに等しければステップＳ１５０８へ進み、異なればステップＳ１５０５へ進む。
【００５６】
ステップＳ１５０８では変数ｊを値１だけインクリメントし、ステップＳ１５０９でｊがブロック高さを示すｈに等しければ処理を終了し、このとき、（ｘ，ｙ）を左上起点とするｗ×ｈ画素ブロックが黒ブロックであるとして検出される。ｊがｈと異なるときはステップＳ１５０４へ戻る。
【００５７】
ステップＳ１５１０ではｘにｗを加え、ステップＳ１５１１でｘが画像幅を示すＷ以上であればステップＳ１５１２へ進み、そうでなければステップＳ１５０３へ戻る。
【００５８】
ステップＳ１５１２ではｙにｈを加え、ステップＳ１５１３でｙが画像高さを示すＨ以上であれば処理を終了し、このとき、黒ブロックは存在しないと判定される。ｙがＨ未満であればステップＳ１５０２へ戻る。
【００５９】
以上の処理によって、Ｗ画素×Ｈ画素の２値画像からｗ画素×ｈ画素の黒ブロックが検出される。
【００６０】
●連結領域の塗りつぶし処理
以下、図１１のステップＳ１４０４に示した連結領域の塗りつぶし処理の詳細を図１３のフローチャートに示し、説明する。
【００６１】
なお、オブジェクトの塗りつぶし処理としては種々の方法が知られており、第３実施形態ではどのような塗りつぶし方法を用いても良い。したがって、ここでは基本的な方法について説明することとし、説明の簡略化のためオブジェクトは外に凸である単純な形状であると仮定する。
【００６２】
上述した黒ブロック探索処理の結果、図１４に示すように（ｘ，ｙ）を左上起点とするブロックが黒ブロックとして検出されている。そこで第３実施形態の塗りつぶし処理においては、この黒ブロックの中心点である（（ｘ＋ｗ）／２，（ｙ＋ｈ）／２）を起点として、黒画素で連結している領域をラベルｃで塗りつぶす。すなわち、値２５５である画素値を値ｃで置き換える。
【００６３】
具体的にはまずステップＳ６０１において、黒ブロックの中心点（（ｘ＋ｗ）／２，（ｙ＋ｈ）／２）を含む走査線について、該走査線上の黒連結部分をラベルｃで塗りつぶす。すなわち、図１４に示す黒ブロックを含むオブジェクトにおける上記走査線の左端（ｘ０，ｙ＋ｈ／２）と右端（ｘ１，ｙ＋ｈ／２）を結ぶ線分（図１４においてオブジェクトを水平方向に切断する線分）がラベルｃで塗りつぶされる。なお、上記（ｘ０，ｙ＋ｈ／２）と（ｘ１，ｙ＋ｈ／２）を結ぶ線分を以下では連結線分と称し、その塗りつぶし処理の詳細については後述する。
【００６４】
そして、ステップＳ６０２で連結線分から下にある黒連結部分を塗りつぶし、ステップＳ６０３で連結線分から上にある黒連結部分を塗りつぶす。なお、ステップＳ６０２，Ｓ６０３における塗りつぶし処理の詳細については後述する。
【００６５】
この処理の結果、黒ブロックと黒画素で連結した領域を、ラベルｃで塗りつぶすことができる。
【００６６】
●連結線分の塗りつぶし処理
以下、図１３のステップＳ６０１に示した連結線分の塗りつぶし処理の詳細を図１５のフローチャートに示し、説明する。なお、説明の簡略化のために、処理の起点となる黒ブロックの中心点（（ｘ＋ｗ）／２，（ｙ＋ｈ）／２）を、座標（Ｘ，Ｙ）で示すとする。すなわち、Ｘ＝（ｘ＋ｗ）／２，Ｙ＝（ｙ＋ｈ）／２とする。
【００６７】
まず、ステップＳ８０１で変数ｉにＸを代入し、ステップＳ８０２でｉを値１だけデクリメントする。そして、ステップＳ８０３でｂｕｆ（ｉ，Ｙ）が値２５５に等しいか否かを判定し、異なればステップＳ８０４へ進むが、等しければステップＳ８０２へ戻ってｉをさらにデクリメントする。
【００６８】
ステップＳ８０４では変数ｘ０に値ｉ＋１を格納し、ステップＳ８０５では変数ｉにＸを代入する。そしてステップＳ８０６でｉを値１だけインクリメントし、ステップＳ８０７でｂｕｆ（ｉ，Ｙ）が値２５５に等しいか否かを判定し、等しければステップＳ８０８へ進むが、異なればステップＳ８０６へ戻ってｉをさらにインクリメントする。
【００６９】
ステップＳ８０８では、変数ｘ１に値ｉ−１を格納し、ステップＳ８０９では変数ｉに値ｘ０を代入し、ステップＳ８１０ではｂｕｆ（ｉ，Ｙ）にｃを代入する。そしてステップＳ８１１でｉを値１だけインクリメントし、ステップＳ８１２でｉがｘ１よりも大きければ処理を終了するが、そうでなければステップＳ８１０に戻る。
【００７０】
この処理により、変数ｘ０，ｘ１に連結線分の両端におけるｘ座標を格納し、該連結線分をラベルｃで塗りつぶすことができる。
【００７１】
●連結線分から下（上）の塗りつぶし処理
以下、図１３のステップＳ６０２に示した連結線分から下にある黒連結部分の塗りつぶし処理の詳細を図１６のフローチャートに示し、説明する。なお、ここでもＹ＝ｙ＋ｈ／２とし、したがって、（ｘ０，Ｙ）と（ｘ１，Ｙ）を結ぶ連結線分より下の黒連結部分をラベルｃで塗りつぶす。
【００７２】
まず、ステップＳ９０１で変数Ｙを値１だけインクリメントし、ステップＳ９０２で変数ｉにｘ０を代入する。そしてステップＳ９０３でｂｕｆ（ｉ，Ｙ）が値２５５に等しいか否かを判定し、異なればステップＳ９０４へ、等しければステップＳ９０６へ進む。
【００７３】
ステップＳ９０４ではｉを値１だけインクリメントし、ステップＳ９０５でｉがｘ１よりも大きければ処理を終了するが、そうでなければステップＳ９０３に戻る。
【００７４】
ステップＳ９０６ではＸにｉを代入し、ステップＳ９０７で（Ｘ，Ｙ）を起点として、横方向、すなわち走査線上の連結線分を塗りつぶす。なお、この走査線上の塗りつぶし処理については図１５のフローチャートで示したため、ここではその詳細な説明を省略する。
【００７５】
なお、図１３のステップＳ６０３に示した連結線分から上にある黒連結部分の塗りつぶし処理については、基本的に上述した図１６のフローチャートに示す、下方向への塗りつぶし処理と同様であり、ステップＳ９０１においてＹをインクリメントする代わりにデクリメントすれば良く、他のステップについては同様の処理を行えば良い。
【００７６】
以上説明したようなラベリング処理によれば、所定サイズの黒ブロックを含むオブジェクト、すなわち所定サイズ以上の面積をもつオブジェクトについてのみ、ラベル付けを行うことができる。したがって、微小なノイズ領域に対してラベルを付けてしまうことがなく、高速なラベリングが可能になる。
【００７７】
●ラベリング後の矩形検出
以上のラベリング処理により、図２に示すｂｕｆ（）の２次元配列においては、同図上方の矩形オブジェクトに含まれる全ての画素に対してラベル１としての画素値１が、下方の矩形オブジェクトに含まれる全画素に対してはラベル２としての画素値２が、それ以外の微小ノイズ部分の黒画素には画素値２５５が、背景の白画素には値０が、それぞれ格納される。
【００７８】
第３実施形態においては、各ラベル領域毎に矩形オブジェクトの位置（頂点座標）を判定する。すなわち、ラベリング後の画像に対して、上述した第１及び第２実施形態において説明した矩形検出処理を施す。具体的には、上述した図４に示すヒストグラムの作成フローチャートにおいて、ステップＳ４０４に示すｂｕｆ（）の比較対象を、黒画素を示す値２５５から、ラベル値（この場合、１または２）に変更すれば良い。これにより、ラベル１及びラベル２の領域が、矩形として検出される。
【００７９】
なお、ここでは２個の矩形を含む場合を例として説明したが、任意個数の矩形を含む２値画像に対して上記ラベリング処理を施し、各ラベル毎に、矩形検出処理を行うことが可能であることは言うまでもない。
【００８０】
以上説明したように第３実施形態によれば、２値画像に対して理想的なラベリング処理を施すことによってノイズの影響を排除し、矩形画像の検出をより高精度に行うことができる。
【００８１】
＜第４実施形態＞
以下、本発明に係る第４実施形態について説明する。なお、第４実施形態におけるシステム構成は上述した第１実施形態と同様であるため、説明を省略する。
【００８２】
上述した第３実施形態においては、２値画像から黒ブロックの探索を行なう際にまず２値画像全体をブロックに分割した後に、各ブロックの内部が全て黒画素であるか否かをチェックした。しかしながら黒ブロックの探索方法としては他の方法も適用可能であり、例えば第４実施形態においては、２値画像内におけるブロックの左上座標を連続的に変化させていく方法について説明する。この方法によれば演算負荷は高くなるものの、黒ブロックの検出性能を向上することができる。
【００８３】
図１７は、第４実施形態において矩形オブジェクト内の黒ブロックを探索する様子を示す図である。同図によれば第４実施形態における探索の起点（ｘ，ｙ）は、第３実施形態で図１０に示したブロック境界からは外れた位置にあることが分かる。
【００８４】
図１８に、第４実施形態における黒ブロックの探索処理のフローチャートを示し、詳細に説明する。
【００８５】
まずステップＳ１１０１〜Ｓ１１０４において、変数ｙ，ｘ，ｊ，ｉをそれぞれ値０で初期化する。そしてステップＳ１１０５でｂｕｆ（ｘ＋ｉ，ｙ＋ｊ）が黒画素を示す２５５であるか否かを判断し、２５５であればステップＳ１１０６へ、２５５でなければステップＳ１１１０へ進む。
【００８６】
ステップＳ１１０６では変数ｉを値１だけインクリメントし、ステップＳ１１０７でｉがブロック幅を示すｗに等しければステップＳ１１０８へ進み、異なればステップＳ１１０５へ進む。
【００８７】
ステップＳ１１０８では変数ｊを値１だけインクリメントし、ステップＳ１１０９でｊがブロック高さを示すｈに等しければ処理を終了し、このとき、（ｘ，ｙ）を左上起点とするｗ×ｈ画素ブロックが黒ブロックであるとして検出される。ｊがｈと異なるときはステップＳ１１０４へ戻る。
【００８８】
ステップＳ１１１０ではｘにｉ＋１を加える。なお、ここでｘを単に値１だけインクリメントしても、最終的には全く同様の結果が得られるが、ｉ＋１を加えることで探索の無駄を省き、処理を高速化できる。
【００８９】
そして、ステップＳ１１１１でｘが画像幅を示すＷ以上であればステップＳ１１１２へ進み、そうでなければステップＳ１１０３へ戻る。
【００９０】
ステップＳ１１１２ではｙを値１だけインクリメントし、ステップＳ１１１３でｙが画像高さを示すＨに等しければ処理を終了し、このとき、黒ブロックは存在しないと判定される。ｙがＨに等しくなければステップＳ１１０２へ戻る。
【００９１】
以上の処理によって、Ｗ画素×Ｈ画素の２値画像からｗ画素×ｈ画素の黒ブロックが検出される。そして、以降は上述した第３実施形態と同様に、黒画素連結領域の塗りつぶし及び矩形検出処理を行うことができる。
【００９２】
以上説明したように第４実施形態によれば、所定サイズの黒ブロックをより高精度に検出することができる。したがって、有効なオブジェクトのみについてのラベリングを、より高精度に行うことができ、ひいては、より高精度な矩形検出が可能となる。
【００９３】
なお、上述した第３及び第４実施形態によれば、ブロック内の全画素が黒画素であることを黒ブロックの判定条件としたが、例えばノイズの状態によっては、黒領域の内部に白画素が多数混入することがある。そこで本発明においては例えば、ブロック内部の黒画素数をカウントし、これが所定の閾値を超えた場合に黒ブロックであると判定しても良い。
【００９４】
また、探索すべき黒ブロックは必ずしも矩形である必要はなく、例えば六角形等の多角形や、円形もしくは楕円形であってもよいし、想定されるオブジェクトの形状に応じて選択可能なようにしてもよい。
【００９５】
また、探索ブロックのサイズも１つの所定サイズに限らず、例えば大きなブロックサイズから探索をはじめ、オブジェクトが見つからなければ徐々にサイズを小さくして探索を繰り返すようにしても良い。これにより、想定されたよりも小さなオブジェクトをノイズと誤認し、無視してしまう危険性を回避できる。
【００９６】
【他の実施形態】
なお、本発明は、複数の機器（例えばホストコンピュータ、インタフェイス機器、リーダ、プリンタなど）から構成されるシステムに適用しても、一つの機器からなる装置（例えば、複写機、ファクシミリ装置など）に適用しても良い。
【００９７】
また、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ（またはＣＰＵまたはＭＰＵ）が記憶媒体に格納されたプログラムコードを読み出し実行することによっても達成されることは言うまでもない。
【００９８】
この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【００９９】
プログラムコードを供給するための記憶媒体としては、例えば、フロッピーディスク、ハードディスク、光ディスク、光磁気ディスク、ＣＤ−ＲＯＭ、ＣＤ−Ｒ、磁気テープ、不揮発性のメモリカード、ＲＯＭなどを用いることが出来る。
【０１００】
また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているＯＳ（オペレーティングシステム）などが実際の処理の一部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１０１】
さらに、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるＣＰＵなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１０２】
【発明の効果】
以上説明したように本発明によれば、ノイズの多い環境下でも矩形領域を高精度に検出することができる。
【図面の簡単な説明】
【図１】本発明に係る一実施形態における画像処理システムの概要構成を示すブロック図である。
【図２】本実施形態において検出対象となる２値画像例を示す図である。
【図３】本実施形態における黒画素数の水平方向ヒストグラム例を示す図である。
【図４】本実施形態におけるヒストグラム算出処理を示すフローチャートである。
【図５】本実施形態におけるヒストグラムの台形近似方法を示すフローチャートである。
【図６】本実施形態における矩形画像の検出座標例を示す図である。
【図７】本実施形態における４つの斜行モードを示す図である。
【図８】本実施形態における斜行モード判定の原理を説明するための図である。
【図９】第２実施形態において、複数枚の写真を配置した際のヒストグラムの様子を示す図である。
【図１０】第３実施形態における黒ブロック探索方法を説明するための図である。
【図１１】第３実施形態におけるラベリング処理の概要を示すフローチャートである。
【図１２】第３実施形態における黒ブロック探索処理を示すフローチャートである。
【図１３】第３実施形態における塗りつぶし処理を示すフローチャートである。
【図１４】第３実施形態における連結線分塗りつぶし方法を説明するための図である。
【図１５】第３実施形態における連結線分塗りつぶし処理を示すフローチャートである。
【図１６】第３実施形態における連結線分下領域の塗りつぶし処理を示すフローチャートである。
【図１７】第４実施形態における黒ブロック探索方法を説明するための図である。
【図１８】第４実施形態における黒ブロック探索処理を示すフローチャートである。
【符号の説明】
１０１　ＣＰＵ
１０２　キーボード
１０２ａ　マウス
１０３　表示部
１０４　ＲＯＭ
１０５　ＲＡＭ
１０６　ハードディスク
１０７　フロッピーディスク
１０８　プリンタ
１０９　ネットワークＩ／Ｆ
１１０　イメージスキャナ
【図１】
2004030430.tif 000003
【図２】
2004030430.tif 000004
【図３】
2004030430.tif 000005
【図４】
2004030430.tif 000006
【図５】
2004030430.tif 000007
【図６】
2004030430.tif 000008
【図７】
2004030430.tif 000009
【図８】
2004030430.tif 000010
【図９】
2004030430.tif 000011
【図１０】
2004030430.tif 000012
【図１１】
2004030430.tif 000013
【図１２】
2004030430.tif 000014
【図１３】
2004030430.tif 000015
【図１４】
2004030430.tif 000016
【図１５】
2004030430.tif 000017
【図１６】
2004030430.tif 000018
【図１７】
2004030430.tif 000019
【図１８】
2004030430.tif 000020