(57)【特許請求の範囲】
【請求項１】
画像から矩形領域を検出する画像処理方法であって、
原画像を２値化した画像において、その水平及び垂直方向の黒画素数のヒストグラムを作成するヒストグラム作成工程と、
該ヒストグラムを台形近似することによって、前記２値画像における矩形領域の存在範囲を検出する矩形範囲検出工程と、
前記存在範囲内における、前記矩形領域の傾き方向を検出する傾き方向検出工程とを有し、
前記矩形範囲検出工程においては、前記矩形領域が長方形であると仮定して、前記ヒストグラムの形状が、左右の斜辺が対称となる台形を呈するように、該左右の斜辺について回帰分析による直線近似の精度を比較して、誤差の少ない一方の斜辺から得られるデータに合わせて、他方の斜辺のデータを修正することを特徴とする画像処理方法。
【請求項２】
前記矩形範囲検出工程においては、
前記２値画像の水平及び垂直方向における前記ヒストグラムのそれぞれについて台形近似を行い、
前記２値画像の水平及び垂直方向のそれぞれついて、矩形領域の存在範囲を検出することを特徴とする請求項１記載の画像処理方法。
【請求項３】
前記矩形範囲検出工程においては、前記矩形領域に対する複数の頂点座標候補を検出することを特徴とする請求項２記載の画像処理方法。
【請求項４】
前記矩形範囲検出工程においては、前記近似された台形の頂点座標を、前記矩形領域に対する複数の頂点座標候補として検出することを特徴とする請求項３記載の画像処理方法。
【請求項５】
前記傾き方向検出工程においては、前記矩形領域の複数の頂点座標候補から４頂点の座標を特定することを特徴とする請求項４記載の画像処理方法。
【請求項６】
前記傾き方向検出工程においては、
前記矩形領域に対する複数の頂点座標候補に基づいて、該矩形領域の複数の傾き方向を仮定し、
該複数の傾き方向のそれぞれで示される矩形領域について、その外部に存在する黒画素数を計数し、
それぞれの計数結果に基づいて１つの傾き方向を特定することによって、前記４頂点の座標を特定することを特徴とする請求項５記載の画像処理方法。
【請求項７】
前記傾き方向検出工程においては、
前記矩形領域に対する複数の頂点座標候補に基づいて、該矩形領域の複数の傾き方向を仮定し、
該複数の傾き方向のそれぞれで示される矩形領域について、その内部に存在する黒画素を計数し、
それぞれの計数結果に基づいて１つの傾き方向を特定することによって、前記４頂点の座標を特定することを特徴とする請求項５記載の画像処理方法。
【請求項８】
さらに、前記傾き方向検出工程において検出された４頂点の座標によって決定される矩形領域に対して、斜行補正を施す斜行補正工程を備えることを特徴とする請求項５記載の画像処理方法。
【請求項９】
前記斜行補正工程においては、バイリニア法による補間を行うことを特徴とする請求項８記載の画像処理方法。
【請求項１０】
前記斜行補正工程においては、ニアレストネイバ法による補間を行うことを特徴とする請求項８記載の画像処理方法。
【請求項１１】
前記台形近似は、台形を構成する左右の斜辺について、回帰分析による直線近似の精度を比較して、誤差の少ない斜辺から得られるデータにあわせて行われることを特徴とする請求項１記載の画像処理方法。
【請求項１２】
前記矩形領域は、写真画像を示す領域であることを特徴とする請求項１１記載の画像処理方法。
【請求項１３】
さらに、多値の原画像を２値化して前記２値画像を得る２値化工程を有することを特徴とする請求項１記載の画像処理方法。
【請求項１４】
前記原画像は、１枚の写真画像が配置された画像であることを特徴とする請求項１３記載の画像処理方法。
【請求項１５】
前記原画像が、複数枚の写真画像が主走査方向に離れた位置に配置された画像である場合、
前記ヒストグラム作成工程においては、前記２値画像を前記写真画像毎に主走査方向で分割し、該分割した２値画像毎に、前記ヒストグラムを作成することを特徴とする請求項１３記載の画像処理方法。
【請求項１６】
前記原画像が、複数枚の写真画像が副走査方向に離れた位置に配置された画像である場合、
前記ヒストグラム作成工程においては、前記２値画像を前記写真画像毎に副走査方向で分割し、該分割した２値画像毎に、前記ヒストグラムを作成することを特徴とする請求項１３記載の画像処理方法。
【請求項１７】
さらに、前記２値画像に対してラベル付けを行うラベリング工程を有し、
前記ヒストグラム作成工程においては、前記ラベル付けされた画素数のヒストグラムを作成することを特徴とする請求項１記載の画像処理方法。
【請求項１８】
前記ラベリング工程は、
前記２値画像において、その内部における黒画素数が所定割合以上であるような所定サイズのブロックを、黒ブロックとして検出する黒ブロック検出工程と、
検出された黒ブロック内および該黒ブロックに連結している黒画素について、所定のラベル値で置き換えるラベル付け工程と、を有することを特徴とする請求項１７記載の画像処理方法。
【請求項１９】
前記黒ブロック検出工程においては、その内部が全て黒画素からなるブロックを、前記黒ブロックとして検出することを特徴とする請求項１８記載の画像処理方法。
【請求項２０】
前記黒ブロック検出工程は、
前記２値画像全体を前記所定サイズのブロックに分割する分割工程と、
前記ブロックごとに黒ブロックであるか否かを判定する判定工程と、を有することを特徴とする請求項１８記載の画像処理方法。
【請求項２１】
前記黒ブロック検出工程においては、
前記２値画像において前記所定サイズのブロック位置を順次ずらすことによって、黒ブロックを検出することを特徴とする請求項１８記載の画像処理方法。
【請求項２２】
前記黒ブロック検出工程においては、前記２値画像において前記所定サイズの黒ブックが検出されなかった場合に、該所定サイズよりも小さなサイズの黒ブロックを検出することを特徴とする請求項１８記載の画像処理方法。
【請求項２３】
前記ラベル付け工程は、
前記黒ブロック内の基準ラインを前記ラベル値で置き換える基準ラベル付け工程と、
前記前記基準ラインよりも上部に連結している黒画素を前記ラベル値で置き換える上部ラベル付け工程と、
前記前記基準ラインよりも下部に連結している黒画素を前記ラベル値で置き換える下部ラベル付け工程と、を有することを特徴とする請求項１８記載の画像処理方法。
【請求項２４】
上記黒ブロックは矩形であることを特徴とする請求項１８記載の画像処理方法。
【請求項２５】
上記黒ブロックは多角形であることを特徴とする請求項１８記載の画像処理方法。
【請求項２６】
上記黒ブロックは円形であることを特徴とする請求項１８記載の画像処理方法。
【請求項２７】
画像から矩形領域を検出する画像処理装置であって、
原画像を２値化した画像において、その水平及び垂直方向の黒画素数のヒストグラムを作成するヒストグラム作成手段と、
該ヒストグラムを台形近似することによって、前記２値画像における矩形領域の存在範囲を検出する矩形範囲検出手段と、
前記存在範囲内における、前記矩形領域の傾き方向を検出する傾き方向検出手段とを有し、
前記矩形範囲検出手段においては、前記矩形領域が長方形であると仮定して、前記ヒストグラムの形状が、左右の斜辺が対称となる台形を呈するように、該左右の斜辺について回帰分析による直線近似の精度を比較して、誤差の少ない一方の斜辺から得られるデータに合わせて、他方の斜辺のデータを修正することを特徴とする画像処理装置。
【請求項２８】
画像から矩形領域を検出する画像処理プログラムであって、
コンピュータが実行することによって、
原画像を２値化した画像において、その水平及び垂直方向の黒画素数のヒストグラムを作成するヒストグラム作成工程と、
該ヒストグラムを台形近似することによって、前記２値画像における矩形領域の存在範囲を検出する矩形範囲検出工程と、
前記存在範囲内における、前記矩形領域の傾き方向を検出する傾き方向検出工程とを実現し、
前記矩形範囲検出工程においては、前記矩形領域が長方形であると仮定して、前記ヒストグラムの形状が、左右の斜辺が対称となる台形を呈するように、該左右の斜辺について回帰分析による直線近似の精度を比較して、誤差の少ない一方の斜辺から得られるデータに合わせて、他方の斜辺のデータを修正することを特徴とするコンピュータが読取可能な画像処理プログラム。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像処理方法及び画像処理装置に関し、特に矩形画像の検出を行う画像処理方法及び画像処理装置に関する。
【０００２】
【従来の技術】
従来より、原画像から矩形領域を検出し、切り出すためのアルゴリズムが種々提案されている。例えば、特開平8-237537号においては、まず輪郭抽出を行い、輪郭が直線を成す部分を探すことによって矩形領域の探索を行なう技術が記載されている。
【０００３】
【発明が解決しようとする課題】
しかしながら従来の矩形切り出しのアルゴリズムによれば、ノイズの多い環境下においては、矩形輪郭の直線部分を検出すること、さらに、4つの直線を関連付けて1個の矩形を検出することは困難であった。従って、正確な切り出しを行うことは困難であり、切り出し結果の精度は十分とはいえなかった。
【０００４】
本発明は上述した問題を解決するためになされたものであり、ノイズの多い環境下でも矩形領域を高精度に検出可能とする画像処理方法及び画像処理装置を提供することを目的とする。
【０００５】
【課題を解決するための手段】
上記目的を達成するための一手法として、本発明の画像処理方法は以下の工程を備える。
【０００６】
すなわち、画像から矩形領域を検出する画像処理方法であって、原画像を２値化した画像において、その水平及び垂直方向の黒画素数のヒストグラムを作成するヒストグラム作成工程と、該ヒストグラムを台形近似することによって、前記２値画像における矩形領域の存在範囲を検出する矩形範囲検出工程と、前記存在範囲内における、前記矩形領域の傾き方向を検出する傾き方向検出工程とを有し、前記矩形範囲検出工程においては、前記矩形領域が長方形であると仮定して、前記ヒストグラムの形状が、左右の斜辺が対称となる台形を呈するように、該左右の斜辺について回帰分析による直線近似の精度を比較して、誤差の少ない一方の斜辺から得られるデータに合わせて、他方の斜辺のデータを修正することを特徴とする。
【０００７】
さらに、前記２値画像に対してラベル付けを行うラベリング工程を有し、前記ヒストグラム作成工程においては、前記ラベル付けされた画素数のヒストグラムを作成することを特徴とする。
【０００８】
【発明の実施の形態】
以下、本発明に係る一実施形態について、図面を参照して詳細に説明する。
【０００９】
＜第１実施形態＞
●システム構成
図１は、本発明が実行されるコンピュータシステムの構成を示すブロック図である。101はCPUであり、システム全体の制御を行なう。102はキーボードであり、102aのマウスとともにシステムへのデータ入力に使用される。103は表示装置であり、CRTや液晶等で構成されている。104はROM、105はRAMであり、システムの記憶装置を構成し、システムが実行するプログラムやシステムが利用するデータを記憶する。106はハードディスク装置(HDD)、107はフロッピディスク装置(FDD)であり、システムのファイルシステムに使用される外部記憶装置を構成している。108はプリンタである。
【００１０】
109はネットワークI/Fであり、LANまたはWANに接続している。I/F109を介して、コンピュータプログラムやデジタル画像等のデータファイルを他のコンピュータシステムとやりとりすることができる。プログラムやデータはハードディスク106に記録されたり、直接RAM105に展開されて実行される。
【００１１】
110はイメージスキャナであり、原稿台上の写真や印刷物を読み込んで、多値のデジタル画像データとしてRAM105上に取り込むことができる。
【００１２】
●矩形画像概要
図２に、イメージスキャナ110から取り込んで2値化された画像の一例を示す。図中の矩形は、写真等の矩形の原稿画像（以下、矩形画像と称する）を示し、3つの楕円はノイズを示している。なお、同図においては説明のためノイズを簡略化して示したが、実際のノイズ分はサイズも形状も不定であり、その数も数百から数千個程度になることが多い。また、画像の2値化は所定の閾値との比較による周知の単純二値化法を用いるとし、ここでは詳細な説明を省略する。
【００１３】
図２に示す画像は、RAM105上で幅W画素、高さH画素のビットマップとして保持されている。各画素は1バイトの深さを持ち、黒画素は値255、白画素は値0で示されるとする。また、RAM105上のビットマップは2次元配列としてアクセスできるものとし、該ビットマップの左上を起点として水平方向にi番目、垂直方向にj番目の画素をbuf(i,j)と表記する。本実施形態ではこのビットマップから、以下に示す方法によって矩形画像の存在領域の座標を特定する。
【００１４】
●ヒストグラム作成
図３は、図２に示す2値画像においてノイズが存在しない理想的な状態を想定した場合に、水平方向に黒画素を計数したヒストグラムの様子を示す図であり、同図上部が2値画像、下部がヒストグラム例を示す。同図によれば、2値画像の矩形の4頂点に対応して、ヒストグラムが概ね台形をなすことがわかる。なお、実際の2値画像はノイズを含むため、ヒストグラムが完全な台形となることはないが、水平方向における頂点の位置を特定するのに十分な情報を、このヒストグラムの台形形状から得ることができる。
【００１５】
図４は、図３に示したヒストグラムの作成処理を示すフローチャートである。以下、ヒストグラムデータを格納する配列をhist()で示す。
【００１６】
先ずステップS401，S402において、変数x，y及びのそれぞれに値0を代入し、ステップS403で変数hist(x)に値0を代入する。
【００１７】
そしてステップS404において、ビットマップ上の画素buf(x,y)と値255を比較し、異なればステップS406へ進むが、等しければステップS405へ進んでhist(x)を値1だけインクリメントした後、ステップS406へ進む。
【００１８】
ステップS406では変数yを値1だけインクリメントし、次にステップS407においてyとビットマップの高さHを比較する。yとHが異なればステップS404へ戻るが、等しければステップS408へ進んで変数xを値1だけインクリメントし、ステップS409でxとビットマップ幅Wを比較する。xとWが異なればステップS402へ戻るが、等しければ処理を終了する。
【００１９】
●頂点検出処理
以上の処理によって、黒画素を計数したヒストグラムの配列hist()が得られる。このヒストグラムは図３に示したように、X軸及び3つの直線で囲まれた台形をなしている。本実施形態ではこの台形において、左辺がX軸と交わる位置をa、左辺と上底が交わる位置をb、右辺と上底が交わる位置をｃ、右辺がX軸と交わる位置をdとする。
【００２０】
ここで図５のフローチャートを用いて、ヒストグラムが呈する台形の左辺を解析して、上記位置a，bを求める方法について説明する。
【００２１】
まずステップS501において、hist(x)が最大になるピーク点Pを検出する。図３に示すヒストグラムにおいては、X=400前後の位置に高さ800のピークがある。次にステップS502において、点Pの前方向に、ピークの半分の高さになる点Fを検出する。図３に示すヒストグラムにおいては、X=100前後の位置が点Fに相当する。そしてステップS503で、点Fの前方向にピークの1/4の高さになる点F0を検出し、さらにステップS504で、点Fの後方向にピークの3/4の高さになる点F1を検出する。
【００２２】
次にステップS505において、F0≦X≦F1の全ての点について、周知の回帰分析を用いて直線近似を行うことによって、図３に示すような直線Lを得る。そしてステップS506において直線LがX軸と交わる点を算出し、この点をaとして得る。そしてステップS507において、直線LがピークPの高さの98％になる点を算出し、この点をbとして得る。これは、ピークPはノイズ分を含んでいるため実際のピークよりも多めに出ていることを考慮して、これを98％分に補正するためである。
以上、図５に示すフローチャートにより、ピークPの前方向への探索を行って点a，bを得る例について説明したが、同様にピークPの後方向に探索を行うことにより、点c、dを得ることができる。
【００２３】
また、以上は水平方向の頂点位置検出についての説明であるが、上記説明における縦軸と横軸を反転して全く同様の方法を適用することにより、垂直方向における頂点位置検出を行うことが可能である。これにより図６に示すように、矩形を囲む縦横それぞれ4個の座標値、すなわち8個の変数（ax，bx，cx，dx，ay，by，cy，dy）を、頂点候補として得ることができる。
【００２４】
ここで、矩形から上記8つの変数は一意に決定されるが、逆に、8つの変数から矩形を決定することはできない。すなわち図７に示すように、8つの変数に基づく矩形としては、その斜行方向（以下、斜行モード）によって4通りの頂点座標が考えられるが、そのいずれであるかを決定することができない。なお図７においては、矩形が完全に水平である特別な場合（不図示）をモード0として、4つの斜行モードをそれぞれ、モード1,2,-1,-2とする。これら各モードで示される画像からは同じ形状のヒストグラムが生成されるため、ヒストグラム以外の他の方法によって、斜行モードを判定する必要がある。
【００２５】
●斜行モード判定
以下、本実施形態における斜行モード判定処理について、詳細に説明する。
【００２６】
上述した図６は、図７に示すモード1の状態に相当するが、図６において斜線で示した2つの三角領域の内側に存在する黒画素を計数すると、理想的には黒画素（図中網点部分）が含まれないため、黒画素の計数結果は0になると考えられる。以下、この図６に示す斜線領域を、モード1のテンプレートと呼ぶ。なお、図７に示す他のモードについても同様に、矩形上部に存在する2つの三角領域を、各モードのテンプレートとする。
【００２７】
ここで図８に示すように、実際にはモード1である矩形画像（図中網点部分）に対してモード2のテンプレート（図中斜線部分）を当てはめると、テンプレートの内側に矩形部分がはみ出してしまうため、黒画素数の計数結果は0にならない。本実施形態ではこの特性を利用して、矩形の斜行モードを判定する。
【００２８】
具体的には、判定対象となる矩形画像に対して4つのモードのテンプレートを適用した場合の黒画素数をそれぞれ計数し、計数結果が最少であるテンプレートを、その画像の斜行モードとして決定する。すなわち、テンプレートへの入り込みの度合いが最も少ない場合が、該矩形画像が最も近似する斜行度合いであるとする。もちろん、テンプレート外に存在する黒画素を計数し、計数結果が最大であるテンプレートによって斜行モードを決定することも可能である。
【００２９】
以上の処理により、2値画像中の矩形領域の4つの頂点座標を特定することができる。従ってこの情報に基づき、原画像に対して周知の斜行補正及び画像切り出し処理を施すことによって、例えばイメージスキャナ110上に配置した矩形の写真画像を切り出すことができる。
【００３０】
なお、上記周知の斜行補正処理としては、単純補間法（ニアレストネイバ法）または線形補間法（バイリニア法）を用いることが望ましく、前者は速度に優れ、後者は画質に優れるので、用途に応じて使い分ければ良い。
【００３１】
以上説明したように本実施形態によれば、ノイズの多い環境下であっても、矩形領域を正確に検出することができる。
【００３２】
なお、矩形領域が完全な長方形であれば、理想的なヒストグラムとして、左右の斜辺が対称となる理想的な台形を呈するはずであるが、ノイズの影響により左右の斜辺が対称とはならず、すなわち、図３に示すa-b間の距離が、c-d間の距離と等しくならないことがある。そのような場合には、ノイズの影響が少ないと考えられる方の斜辺から得られるデータにあわせて、台形近似を行う。具体的には左右の斜辺について、回帰分析による直線近似の精度（直線と実データの間の２乗誤差）を比較して、誤差の少ないほうを採用すれば良い。
【００３３】
同様に、矩形検出の結果として得られた4つの頂点を結んだ矩形が、ノイズの影響で必ずしも長方形にならず、隣り合う辺が直交しないことも考えられる。このような場合も、ノイズの影響が少ないと考えられる方のデータに基づいて、矩形が長方形になるように修正を施すことで、矩形検出の精度を向上することができる。
【００３４】
＜第２実施形態＞
以下、本発明に係る第２実施形態について説明する。なお、第２実施形態におけるシステム構成は上述した第１実施形態と同様であるため、説明を省略する。
【００３５】
上述した第１実施形態においては、画像内に1つの矩形領域が存在する場合について説明した。このような状況としては例えば、イメージスキャナ110の原稿台上に1枚の写真を必ずしも水平ではなく載置した状態でスキャンを行い、その後自動的に斜行補正、画像切り出しを行うことで、写真画像を抽出する処理が想定される。
【００３６】
しかしながら、一般的なフラットヘッドスキャナの原稿台はA4サイズ程度の原稿の載置を可能とするため、一般的な写真（所謂L版サイズ）の複数枚を一度に載置することができる。従って、このような複数枚の写真画像を一回のスキャンによって読み取り、得られた画像から写真画像を示す矩形領域だけを切り出すことができれば、スキャン作業の効率化が図れる。
【００３７】
そこで第２実施形態においては、一枚の画像から、複数の矩形画像を検出することを特徴とする。
【００３８】
以下、図９を参照して、第２実施形態における複数の矩形画像の検出処理について説明する。図９の左部は、原稿台の副走査方向（図中長手方向）に2枚の写真を離して配置した際の2値化画像を示し、図９の右部は該2値化画像の副走査方向におけるヒストグラムの様子を示す。同図から分かるように、複数枚の写真が離れて配置されている場合、ヒストグラムに複数個の台形が現れる。従って第２実施形態においてはこのヒストグラムを参照することによって、これら複数の台形の間、すなわち図９において1点鎖線Lで示した位置で、画像を二つに切り分ける。すると、以降は上述した第１実施形態で示した方法によって、該切り分けられた各々の領域において、矩形画像をそれぞれ検出することができる。
【００３９】
なお、図９においては複数枚の写真を副走査方向に離して配置した場合について説明したが、これを主走査方向（図中短手方向）に離して配置した場合も同様に、主走査方向についてのヒストグラムを作成することによって、画像を主走査方向で切り分け、それぞれの矩形画像を抽出することができる。
【００４０】
以上説明したように第２実施形態によれば、一枚の画像から複数の矩形画像を検出することができる。
【００４１】
＜第３実施形態＞
以下、本発明に係る第３実施形態について説明する。なお、第３実施形態におけるシステム構成は上述した第１実施形態と同様であるため、説明を省略する。
【００４２】
第３実施形態においては、図２に示すような2値画像に対して理想的なラベリング処理を施すことによってノイズの影響を排除し、矩形画像の検出をより高精度に行うことを特徴とする。
【００４３】
ここで、図２に示す2値画像における理想的なラベリング処理とは、黒画素同士の連結に基づき、例えば上方の矩形オブジェクトに含まれる全ての画素に対して画素値1を与え、下方の矩形オブジェクトに含まれる全画素に対しては画素値2を与えることである。すなわち、微小なノイズ分にはラベルを与えず、画素値255のままにしておく。
【００４４】
●ラベリング処理概要
以下、上記理想的なラベリングを実現するためのラベリング方法について、詳細に説明する。
【００４５】
図１０は、図２における上方の矩形オブジェクトを含む左上部分に対応し、第３実施形態における塗りつぶし処理の起点となるブロックの探索方法を説明するための図である。
【００４６】
まず図１０に示すように、図２に示したW画素×H画素のビットマップ全体を、w画素×h画素のブロックに分け、その内部が全て値255の黒画素で占められるようなブロック（以下、「黒ブロック」と称する）を図中矢印方向に探索する。図３において黒矩形で示したブロックが、見つかった黒ブロックである。
【００４７】
第３実施形態では、見つかった黒ブロックと黒画素が連結している領域を塗りつぶすことによって、高速なラベリングを実現する。図１１に、第３実施形態におけるラベリング処理全体のフローチャートを示し、説明する。
【００４８】
まずステップS1401で、変数cに値1を代入し、ステップS1402で黒ブロック探索を行う。この黒ブロック探索処理の詳細については後述する。
【００４９】
次にステップS1403において黒ブロックが見つかったか否かを判断し、見つかったらステップS1404へ進むが、見つからなければ処理を終了する。
【００５０】
ステップS1404では、見つかった黒ブロックを起点にして、黒画素連結領域をラベルcで塗りつぶす。この塗りつぶし処理の詳細については後述する。
【００５１】
そしてステップS1405で変数cを1だけインクリメントしてステップS1402に戻り、以上の処理を繰り返す。
【００５２】
この処理の結果、所定以上の大きさを持つオブジェクトのみに対して、ラベル1,2,…,cを与えることができる。
【００５３】
●黒ブロック探索処理
以下、図１１のステップS1402に示した黒ブロック探索処理の詳細を図１２のフローチャートに示し、説明する。
【００５４】
まずステップS1501〜S1504において、変数y，x，j，iをそれぞれ値0で初期化する。そしてステップS1505でbuf(x+i,y+j)が黒画素を示す255であるか否かを判断し、255であればステップS1506へ、255でなければステップS1510へ進む。
【００５５】
ステップS1506では変数iを値1だけインクリメントし、ステップS1507でiがブロック幅を示すwに等しければステップS1508へ進み、異なればステップS1505へ進む。
【００５６】
ステップS1508では変数jを値1だけインクリメントし、ステップS1509でjがブロック高さを示すhに等しければ処理を終了し、このとき、(x,y)を左上起点とするw×h画素ブロックが黒ブロックであるとして検出される。jがhと異なるときはステップS1504へ戻る。
【００５７】
ステップS1510ではxにwを加え、ステップS1511でxが画像幅を示すW以上であればステップS1512へ進み、そうでなければステップS1503へ戻る。
【００５８】
ステップS1512ではyにhを加え、ステップS1513でyが画像高さを示すH以上であれば処理を終了し、このとき、黒ブロックは存在しないと判定される。yがH未満であればステップS1502へ戻る。
【００５９】
以上の処理によって、W画素×H画素の2値画像からw画素×h画素の黒ブロックが検出される。
【００６０】
●連結領域の塗りつぶし処理
以下、図１１のステップS1404に示した連結領域の塗りつぶし処理の詳細を図１３のフローチャートに示し、説明する。
【００６１】
なお、オブジェクトの塗りつぶし処理としては種々の方法が知られており、第３実施形態ではどのような塗りつぶし方法を用いても良い。したがって、ここでは基本的な方法について説明することとし、説明の簡略化のためオブジェクトは外に凸である単純な形状であると仮定する。
【００６２】
上述した黒ブロック探索処理の結果、図１４に示すように(x,y)を左上起点とするブロックが黒ブロックとして検出されている。そこで第３実施形態の塗りつぶし処理においては、この黒ブロックの中心点である（(x+w)/2，(y+h)/2）を起点として、黒画素で連結している領域をラベルcで塗りつぶす。すなわち、値255である画素値を値cで置き換える。
【００６３】
具体的にはまずステップS601において、黒ブロックの中心点（(x+w)/2，(y+h)/2）を含む走査線について、該走査線上の黒連結部分をラベルcで塗りつぶす。すなわち、図１４に示す黒ブロックを含むオブジェクトにおける上記走査線の左端（x0，y+h/2）と右端（x1，y+h/2）を結ぶ線分（図１４においてオブジェクトを水平方向に切断する線分）がラベルcで塗りつぶされる。なお、上記（x0，y+h/2）と（x1，y+h/2）を結ぶ線分を以下では連結線分と称し、その塗りつぶし処理の詳細については後述する。
【００６４】
そして、ステップS602で連結線分から下にある黒連結部分を塗りつぶし、ステップS603で連結線分から上にある黒連結部分を塗りつぶす。なお、ステップS602，S603における塗りつぶし処理の詳細については後述する。
【００６５】
この処理の結果、黒ブロックと黒画素で連結した領域を、ラベルcで塗りつぶすことができる。
【００６６】
●連結線分の塗りつぶし処理
以下、図１３のステップS601に示した連結線分の塗りつぶし処理の詳細を図１５のフローチャートに示し、説明する。なお、説明の簡略化のために、処理の起点となる黒ブロックの中心点（(x+w)/2，(y+h)/2）を、座標（X，Y）で示すとする。すなわち、X=(x+w)/2，Y=(y+h)/2とする。
【００６７】
まず、ステップS801で変数iにXを代入し、ステップS802でiを値1だけデクリメントする。そして、ステップS803でbuf(i,Y)が値255に等しいか否かを判定し、異なればステップS804へ進むが、等しければステップS802へ戻ってiをさらにデクリメントする。
【００６８】
ステップS804では変数x0に値i+1を格納し、ステップS805では変数iにXを代入する。そしてステップS806でiを値1だけインクリメントし、ステップS807でbuf(i,Y)が値255に等しいか否かを判定し、等しければステップS808へ進むが、異なればステップS806へ戻ってiをさらにインクリメントする。
【００６９】
ステップS808では、変数x1に値i-1を格納し、ステップS809では変数iに値x0を代入し、ステップS810ではbuf(i,Y)にcを代入する。そしてステップS811でiを値1だけインクリメントし、ステップS812でiがx1よりも大きければ処理を終了するが、そうでなければステップS810に戻る。
【００７０】
この処理により、変数x0，x1に連結線分の両端におけるx座標を格納し、該連結線分をラベルcで塗りつぶすことができる。
【００７１】
●連結線分から下（上）の塗りつぶし処理
以下、図１３のステップS602に示した連結線分から下にある黒連結部分の塗りつぶし処理の詳細を図１６のフローチャートに示し、説明する。なお、ここでもY=y+h/2とし、したがって、(x0,Y)と(x1,Y)を結ぶ連結線分より下の黒連結部分をラベルcで塗りつぶす。
【００７２】
まず、ステップS901で変数Yを値1だけインクリメントし、ステップS902で変数iにx0を代入する。そしてステップS903でbuf(i,Y)が値255に等しいか否かを判定し、異なればステップS904へ、等しければステップS906へ進む。
【００７３】
ステップS904ではiを値1だけインクリメントし、ステップS905でiがx1よりも大きければ処理を終了するが、そうでなければステップS903に戻る。
【００７４】
ステップS906ではXにiを代入し、ステップS907で（X,Y）を起点として、横方向、すなわち走査線上の連結線分を塗りつぶす。なお、この走査線上の塗りつぶし処理については図１５のフローチャートで示したため、ここではその詳細な説明を省略する。
【００７５】
なお、図１３のステップS603に示した連結線分から上にある黒連結部分の塗りつぶし処理については、基本的に上述した図１６のフローチャートに示す、下方向への塗りつぶし処理と同様であり、ステップS901においてYをインクリメントする代わりにデクリメントすれば良く、他のステップについては同様の処理を行えば良い。
【００７６】
以上説明したようなラベリング処理によれば、所定サイズの黒ブロックを含むオブジェクト、すなわち所定サイズ以上の面積をもつオブジェクトについてのみ、ラベル付けを行うことができる。したがって、微小なノイズ領域に対してラベルを付けてしまうことがなく、高速なラベリングが可能になる。
【００７７】
●ラベリング後の矩形検出
以上のラベリング処理により、図２に示すbuf()の2次元配列においては、同図上方の矩形オブジェクトに含まれる全ての画素に対してラベル1としての画素値1が、下方の矩形オブジェクトに含まれる全画素に対してはラベル2としての画素値2が、それ以外の微小ノイズ部分の黒画素には画素値255が、背景の白画素には値0が、それぞれ格納される。
【００７８】
第３実施形態においては、各ラベル領域毎に矩形オブジェクトの位置（頂点座標）を判定する。すなわち、ラベリング後の画像に対して、上述した第１及び第２実施形態において説明した矩形検出処理を施す。具体的には、上述した図４に示すヒストグラムの作成フローチャートにおいて、ステップS404に示すbuf()の比較対象を、黒画素を示す値255から、ラベル値（この場合、1または2）に変更すれば良い。これにより、ラベル1及びラベル2の領域が、矩形として検出される。
【００７９】
なお、ここでは2個の矩形を含む場合を例として説明したが、任意個数の矩形を含む2値画像に対して上記ラベリング処理を施し、各ラベル毎に、矩形検出処理を行うことが可能であることは言うまでもない。
【００８０】
以上説明したように第３実施形態によれば、2値画像に対して理想的なラベリング処理を施すことによってノイズの影響を排除し、矩形画像の検出をより高精度に行うことができる。
【００８１】
＜第４実施形態＞
以下、本発明に係る第４実施形態について説明する。なお、第４実施形態におけるシステム構成は上述した第１実施形態と同様であるため、説明を省略する。
【００８２】
上述した第３実施形態においては、2値画像から黒ブロックの探索を行なう際にまず2値画像全体をブロックに分割した後に、各ブロックの内部が全て黒画素であるか否かをチェックした。しかしながら黒ブロックの探索方法としては他の方法も適用可能であり、例えば第４実施形態においては、2値画像内におけるブロックの左上座標を連続的に変化させていく方法について説明する。この方法によれば演算負荷は高くなるものの、黒ブロックの検出性能を向上することができる。
【００８３】
図１７は、第４実施形態において矩形オブジェクト内の黒ブロックを探索する様子を示す図である。同図によれば第４実施形態における探索の起点(x,y)は、第３実施形態で図１０に示したブロック境界からは外れた位置にあることが分かる。
【００８４】
図１８に、第４実施形態における黒ブロックの探索処理のフローチャートを示し、詳細に説明する。
【００８５】
まずステップS1101〜S1104において、変数y，x，j，iをそれぞれ値0で初期化する。そしてステップS1105でbuf(x+i,y+j)が黒画素を示す255であるか否かを判断し、255であればステップS1106へ、255でなければステップS1110へ進む。
【００８６】
ステップS1106では変数iを値1だけインクリメントし、ステップS1107でiがブロック幅を示すwに等しければステップS1108へ進み、異なればステップS1105へ進む。
【００８７】
ステップS1108では変数jを値1だけインクリメントし、ステップS1109でjがブロック高さを示すhに等しければ処理を終了し、このとき、(x,y)を左上起点とするw×h画素ブロックが黒ブロックであるとして検出される。jがhと異なるときはステップS1104へ戻る。
【００８８】
ステップS1110ではxにi+1を加える。なお、ここでxを単に値1だけインクリメントしても、最終的には全く同様の結果が得られるが、i+1を加えることで探索の無駄を省き、処理を高速化できる。
【００８９】
そして、ステップS1111でxが画像幅を示すW以上であればステップS1112へ進み、そうでなければステップS1103へ戻る。
【００９０】
ステップS1112ではyを値1だけインクリメントし、ステップS1113でyが画像高さを示すHに等しければ処理を終了し、このとき、黒ブロックは存在しないと判定される。yがHに等しくなければステップS1102へ戻る。
【００９１】
以上の処理によって、W画素×H画素の2値画像からw画素×h画素の黒ブロックが検出される。そして、以降は上述した第３実施形態と同様に、黒画素連結領域の塗りつぶし及び矩形検出処理を行うことができる。
【００９２】
以上説明したように第４実施形態によれば、所定サイズの黒ブロックをより高精度に検出することができる。したがって、有効なオブジェクトのみについてのラベリングを、より高精度に行うことができ、ひいては、より高精度な矩形検出が可能となる。
【００９３】
なお、上述した第３及び第４実施形態によれば、ブロック内の全画素が黒画素であることを黒ブロックの判定条件としたが、例えばノイズの状態によっては、黒領域の内部に白画素が多数混入することがある。そこで本発明においては例えば、ブロック内部の黒画素数をカウントし、これが所定の閾値を超えた場合に黒ブロックであると判定しても良い。
【００９４】
また、探索すべき黒ブロックは必ずしも矩形である必要はなく、例えば六角形等の多角形や、円形もしくは楕円形であってもよいし、想定されるオブジェクトの形状に応じて選択可能なようにしてもよい。
【００９５】
また、探索ブロックのサイズも1つの所定サイズに限らず、例えば大きなブロックサイズから探索をはじめ、オブジェクトが見つからなければ徐々にサイズを小さくして探索を繰り返すようにしても良い。これにより、想定されたよりも小さなオブジェクトをノイズと誤認し、無視してしまう危険性を回避できる。
【００９６】
【他の実施形態】
なお、本発明は、複数の機器(例えばホストコンピュータ、インタフェイス機器、リーダ、プリンタなど)から構成されるシステムに適用しても、一つの機器からなる装置(例えば、複写機、ファクシミリ装置など)に適用しても良い。
【００９７】
また、本発明の目的は、前述した実施形態の機能を実現するソフトウェアのプログラムコードを記録した記憶媒体を、システムあるいは装置に供給し、そのシステムあるいは装置のコンピュータ(またはCPUまたはMPU)が記憶媒体に格納されたプログラムコードを読み出し実行することによっても達成されることは言うまでもない。
【００９８】
この場合、記憶媒体から読み出されたプログラムコード自体が前述した実施形態の機能を実現することになり、そのプログラムコードを記憶した記憶媒体は本発明を構成することになる。
【００９９】
プログラムコードを供給するための記憶媒体としては、例えば、フロッピーディスク、ハードディスク、光ディスク、光磁気ディスク、CD-ROM、CD-R、磁気テープ、不揮発性のメモリカード、ROMなどを用いることが出来る。
【０１００】
また、コンピュータが読み出したプログラムコードを実行することにより、前述した実施形態の機能が実現されるだけでなく、そのプログラムコードの指示に基づき、コンピュータ上で稼動しているOS(オペレーティングシステム)などが実際の処理の一部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１０１】
さらに、記憶媒体から読み出されたプログラムコードが、コンピュータに挿入された機能拡張ボードやコンピュータに接続された機能拡張ユニットに備わるメモリに書き込まれた後、そのプログラムコードの指示に基づき、その機能拡張ボードや機能拡張ユニットに備わるCPUなどが実際の処理の一部または全部を行い、その処理によって前述した実施形態の機能が実現される場合も含まれることは言うまでもない。
【０１０２】
【発明の効果】
以上説明したように本発明によれば、ノイズの多い環境下でも矩形領域を高精度に検出することができる。
【図面の簡単な説明】
【図１】本発明に係る一実施形態における画像処理システムの概要構成を示すブロック図である。
【図２】本実施形態において検出対象となる2値画像例を示す図である。
【図３】本実施形態における黒画素数の水平方向ヒストグラム例を示す図である。
【図４】本実施形態におけるヒストグラム算出処理を示すフローチャートである。
【図５】本実施形態におけるヒストグラムの台形近似方法を示すフローチャートである。
【図６】本実施形態における矩形画像の検出座標例を示す図である。
【図７】本実施形態における4つの斜行モードを示す図である。
【図８】本実施形態における斜行モード判定の原理を説明するための図である。
【図９】第２実施形態において、複数枚の写真を配置した際のヒストグラムの様子を示す図である。
【図１０】第３実施形態における黒ブロック探索方法を説明するための図である。
【図１１】第３実施形態におけるラベリング処理の概要を示すフローチャートである。
【図１２】第３実施形態における黒ブロック探索処理を示すフローチャートである。
【図１３】第３実施形態における塗りつぶし処理を示すフローチャートである。
【図１４】第３実施形態における連結線分塗りつぶし方法を説明するための図である。
【図１５】第３実施形態における連結線分塗りつぶし処理を示すフローチャートである。
【図１６】第３実施形態における連結線分下領域の塗りつぶし処理を示すフローチャートである。
【図１７】第４実施形態における黒ブロック探索方法を説明するための図である。
【図１８】第４実施形態における黒ブロック探索処理を示すフローチャートである。
【符号の説明】
101  CPU
102  キーボード
102a  マウス
103  表示部
104  ROM
105  RAM
106  ハードディスク
107  フロッピーディスク
108  プリンタ
109  ネットワークI/F
110  イメージスキャナ
【図１】
0003885001.tif 000002
【図２】
0003885001.tif 000003
【図３】
0003885001.tif 000004
【図４】
0003885001.tif 000005
【図５】
0003885001.tif 000006
【図６】
0003885001.tif 000007
【図７】
0003885001.tif 000008
【図８】
0003885001.tif 000009
【図９】
0003885001.tif 000010
【図１０】
0003885001.tif 000011
【図１１】
0003885001.tif 000012
【図１２】
0003885001.tif 000013
【図１３】
0003885001.tif 000014
【図１４】
0003885001.tif 000015
【図１５】
0003885001.tif 000016
【図１６】
0003885001.tif 000017
【図１７】
0003885001.tif 000018
【図１８】
0003885001.tif 000019