(57)【要約】【課題】  ハフ変換により入力画像自体の性質から画像の傾斜角を検出すると共に、精密なハフ変換を高速で行えるようにする。【解決手段】  所定の角度範囲に対して所定の角度分解能でハフ変換値を求めて、第１投票テーブルに投票する。また第１ハフ変換手段よりも狭い角度範囲で、かつより高い角度分解能でハフ変換値を求めて、第２投票テーブルに投票する。第１投票テーブルのデータと第２投票テーブルのデータとに基づいて、各々画像の傾斜角を求め、求めた２つの傾斜角の整合性をチェックする。【選択図】    図６
2010244353.tif 000002
【特許請求の範囲】
【請求項１】
画像の傾斜角を決定する画像処理装置であって、
画像中の画素に対して、所定の角度範囲に対して所定の角度分解能でハフ変換値を求め、求めたハフ変換値を第１投票テーブルに投票するための第１ハフ変換手段と、
画像中の画素に対して、第１ハフ変換手段よりも狭い角度範囲で、かつより高い角度分解能でハフ変換値を求め、求めたハフ変換値を第２投票テーブルに投票するための、第２ハフ変換手段と、
第１投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第１傾斜角検出手段と、
第２投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第２傾斜角検出手段と、
第１傾斜角検出手段で求めた傾斜角と、第２傾斜角検出手段で求めた傾斜角との整合性をチェックするための整合性チェック手段、とを設けたことを特徴とする画像処理装置。
【請求項２】
前記第１投票テーブルへの投票と、前記第２投票テーブルへの投票とを、並行して実行するように構成したことを特徴とする、請求項１の画像処理装置。
【請求項３】
画像の傾斜角を決定する画像処理装置であって、
画像中の画素に対して、所定の角度範囲に対して所定の角度分解能でハフ変換値を求め、求めたハフ変換値を第１投票テーブルに投票するための第１ハフ変換手段と、
画像中の画素に対して、第１ハフ変換手段よりも狭い角度範囲で、かつより高い角度分解能でハフ変換値を求め、求めたハフ変換値を第２投票テーブルに投票するための、第２ハフ変換手段と、
第１投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第１傾斜角検出手段と、
第２投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第２傾斜角検出手段と、
第１傾斜角検出手段で求めた傾斜角により、第２ハフ変換手段での角度範囲を決定するための角度範囲決定手段、とを設けたことを特徴とする画像処理装置。
【請求項４】
前記第１投票テーブルと、前記第２投票テーブルとを、画像処理装置の同じメモリ領域を用いて設けて、前記第１投票テーブルのデータに基づいて、第２ハフ変換手段での角度範囲を決定した後に、前記第２投票テーブルへの投票を実行するように構成したことを特徴とする、請求項３の画像処理装置。
【請求項５】
画像処理装置により、画像の傾斜角を決定する方法であって、
画像中の画素に対して、所定の角度範囲に対して所定の角度分解能でハフ変換値を求め、求めたハフ変換値を第１投票テーブルに投票するステップと、
画像中の画素に対して、第１ハフ変換手段よりも狭い角度範囲で、かつより高い角度分解能でハフ変換値を求め、求めたハフ変換値を第２投票テーブルに投票するステップと、
第１投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるステップと、
第２投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるステップと、
第１投票テーブルのデータに基づいて求めた傾斜角と、第２投票テーブルのデータに基づいて求めた傾斜角との整合性をチェックするステップ、とを設けたことを特徴とする画像処理方法。
【請求項６】
画像処理装置により、画像の傾斜角を決定する方法であって、
画像中の画素に対して、所定の角度範囲に対して所定の角度分解能でハフ変換値を求め、求めたハフ変換値を第１投票テーブルに投票するステップと、
画像中の画素に対して、第１ハフ変換手段よりも狭い角度範囲で、かつより高い角度分解能でハフ変換値を求め、求めたハフ変換値を第２投票テーブルに投票するステップと、
第１投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるステップと、
第２投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるステップと、
第１投票テーブルのデータに基づいて求めた傾斜角により、第２投票テーブルへ投票する角度範囲を決定するステップ、とを設けたことを特徴とする画像処理方法。
【請求項７】
情報処理装置からなる画像処理装置により、画像の傾斜角を決定するために、
前記画処理装置を、
画像中の画素に対して、所定の角度範囲に対して所定の角度分解能でハフ変換値を求め、求めたハフ変換値を第１投票テーブルに投票するための第１ハフ変換手段と、
画像中の画素に対して、第１ハフ変換手段よりも狭い角度範囲で、かつより高い角度分解能でハフ変換値を求め、求めたハフ変換値を第２投票テーブルに投票するための、第２ハフ変換手段と、
第１投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第１傾斜角検出手段と、
第２投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第２傾斜角検出手段と、
第１傾斜角検出手段で求めた傾斜角と、第２傾斜角検出手段で求めた傾斜角との整合性をチェックする整合性チェック手段、として機能させるための画像処理プログラム。
【請求項８】
情報処理装置からなる画像処理装置により、画像の傾斜角を決定するために、
前記画処理装置を、
画像中の画素に対して、所定の角度範囲に対して所定の角度分解能でハフ変換値を求め、求めたハフ変換値を第１投票テーブルに投票するための第１ハフ変換手段と、
画像中の画素に対して、第１ハフ変換手段よりも狭い角度範囲で、かつより高い角度分解能でハフ変換値を求め、求めたハフ変換値を第２投票テーブルに投票するための、第２ハフ変換手段と、
第１投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第１傾斜角検出手段と、
第２投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第２傾斜角検出手段と、
第１傾斜角検出手段で求めた傾斜角により、第２ハフ変換手段での角度範囲を決定するための角度範囲決定手段、として機能させるための画像処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は入力画像の傾斜角の検出に関する。
【背景技術】
【０００２】
スキャナで画像を読み取ると、画像が僅かに傾斜した状態で読み取られることがある。これを補正するため、原稿用紙の辺の傾斜あるいは頂点の位置を検出することが行われている。原稿用紙が方形であれは、辺の向きは主走査方向あるいは副走査方向に平行で、これらの方向からのずれは原稿用紙の傾斜を表している。この手法で傾斜を検出できるのはスキャン時に限られるので、蓄積済みの画像及び外部から転送された画像の傾斜は検出できない。また原稿用紙の傾斜を検出するので、切り抜きのように用紙が定型でないものは、傾斜を検出できない。さらにハードカバーの書籍を見開きでスキャンすると、カバーは傾斜していないものの、見開いたページが傾斜していることがある。この場合も、傾斜の検出は難しい。これらの問題を解決するには、原稿用紙の傾斜を検出するのではなく、画像自体の傾斜を検出する必要がある。さらに傾斜の検出は、比較的小さなハードウエアで高速で行う必要がある。
【０００３】
ここで関連する先行技術を示すと、特許文献１：JPH10-283476Aは、画像中の直線をハフ変換により検出することを記載している。しかしながら特許文献１は、画像の傾斜をハフ変換により検出することを示していない。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】JPH10-283476A
【発明の概要】
【発明が解決しようとする課題】
【０００５】
この発明の課題は、ハフ変換により画像自体の性質を用いて画像の傾斜角を検出すると共に、精密なハフ変換を小さなハードウエアで高速で行えるようにすることにある。  
【課題を解決するための手段】
【０００６】
この発明は、画像の傾斜角を決定する画像処理装置であって、
画像中の画素に対して、所定の角度範囲に対して所定の角度分解能でハフ変換値を求め、求めたハフ変換値を第１投票テーブルに投票するための第１ハフ変換手段と、
画像中の画素に対して、第１ハフ変換手段よりも狭い角度範囲で、かつより高い角度分解能でハフ変換値を求め、求めたハフ変換値を第２投票テーブルに投票するための、第２ハフ変換手段と、
第１投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第１傾斜角検出手段と、
第２投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第２傾斜角検出手段と、
第１傾斜角検出手段で求めた傾斜角と、第２傾斜角検出手段で求めた傾斜角との整合性をチェックするための整合性チェック手段、とを設けたことを特徴とする。
【０００７】
またこの発明は、画像処理装置により、画像の傾斜角を決定する方法であって、
画像中の画素に対して、所定の角度範囲に対して所定の角度分解能でハフ変換値を求め、求めたハフ変換値を第１投票テーブルに投票するステップと、
画像中の画素に対して、第１ハフ変換手段よりも狭い角度範囲で、かつより高い角度分解能でハフ変換値を求め、求めたハフ変換値を第２投票テーブルに投票するステップと、
第１投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるステップと、
第２投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるステップと、
第１投票テーブルのデータに基づいて求めた傾斜角と、第２投票テーブルのデータに基づいて求めた傾斜角との整合性をチェックするステップ、とを設けたことを特徴とする。
【０００８】
この発明の画像処理プログラムでは、情報処理装置からなる画像処理装置により、画像の傾斜角を決定するために、
前記画処理装置を、
画像中の画素に対して、所定の角度範囲に対して所定の角度分解能でハフ変換値を求め、求めたハフ変換値を第１投票テーブルに投票するための第１ハフ変換手段と、
画像中の画素に対して、第１ハフ変換手段よりも狭い角度範囲で、かつより高い角度分解能でハフ変換値を求め、求めたハフ変換値を第２投票テーブルに投票するための、第２ハフ変換手段と、
第１投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第１傾斜角検出手段と、
第２投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第２傾斜角検出手段と、
第１傾斜角検出手段で求めた傾斜角と、第２傾斜角検出手段で求めた傾斜角との整合性をチェックする整合性チェック手段、として機能させる。
【０００９】
さらにこの発明は、画像の傾斜角を決定する画像処理装置であって、
画像中の画素に対して、所定の角度範囲に対して所定の角度分解能でハフ変換値を求め、求めたハフ変換値を第１投票テーブルに投票するための第１ハフ変換手段と、
画像中の画素に対して、第１ハフ変換手段よりも狭い角度範囲で、かつより高い角度分解能でハフ変換値を求め、求めたハフ変換値を第２投票テーブルに投票するための、第２ハフ変換手段と、
第１投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第１傾斜角検出手段と、
第２投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第２傾斜角検出手段と、
第１傾斜角検出手段で求めた傾斜角により、第２ハフ変換手段での角度範囲を決定するための角度範囲決定手段、とを設けたことを特徴とする。  
【００１０】
さらにこの発明は、画像処理装置により、画像の傾斜角を決定する方法であって、
画像中の画素に対して、所定の角度範囲に対して所定の角度分解能でハフ変換値を求め、求めたハフ変換値を第１投票テーブルに投票するステップと、
画像中の画素に対して、第１ハフ変換手段よりも狭い角度範囲で、かつより高い角度分解能でハフ変換値を求め、求めたハフ変換値を第２投票テーブルに投票するステップと、
第１投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるステップと、
第２投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるステップと、
第１投票テーブルのデータに基づいて求めた傾斜角により、第２投票テーブルへ投票する角度範囲を決定するステップ、とを設けたことを特徴とする。
【００１１】
さらにこの発明の画像処理プログラムでは、情報処理装置からなる画像処理装置により、画像の傾斜角を決定するために、
前記画処理装置を、
画像中の画素に対して、所定の角度範囲に対して所定の角度分解能でハフ変換値を求め、求めたハフ変換値を第１投票テーブルに投票するための第１ハフ変換手段と、
画像中の画素に対して、第１ハフ変換手段よりも狭い角度範囲で、かつより高い角度分解能でハフ変換値を求め、求めたハフ変換値を第２投票テーブルに投票するための、第２ハフ変換手段と、
第１投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第１傾斜角検出手段と、
第２投票テーブルのデータに基づいて、画像中の直線を抽出することにより、画像の傾斜角を求めるための第２傾斜角検出手段と、
第１傾斜角検出手段で求めた傾斜角により、第２ハフ変換手段での角度範囲を決定するための角度範囲決定手段、として機能させる。
【００１２】
この明細書において、画像処理装置に関する記載は画像処理方法及び画像処理プログラムにもそのまま当てはまり、逆に画像処理方法に関する記載は画像処理装置及び画像処理プログラムにもそのまま当てはまる。処理対象の画像は例えばスキャナで読み取った直後の画像であるが、ファクシミリ、ファイル転送、e-mailなどで受信した画像、あるいはメモリに蓄積済みの画像でも良い。また直線と線分とは同じ意味である。
【００１３】
この発明では、ハフ変換により、画像中の直線を抽出し、好ましくは画像中の文字の行あるいは罫線などからなる直線を抽出して、画像の傾斜角を決定するので、画像自体の性質に基づいて、傾斜角を決定できる。従ってスキャン時に限らず、任意の時点で傾斜角を決定でき、切り抜きあるいは見開きの画像などでも、傾斜角を決定できる。
ハフ変換を高精度で実行するための角度分解能を増すと、投票テーブルに大きなメモリが必要になり、また１画素当たりの投票数が増え、処理が低速になる。しかしこの発明では、第１ハフ変換手段と第１傾斜角検出手段とにより画像の傾斜角の概略値を求めて、第２ハフ変換手段と第２傾斜角検出手段により求めた傾斜角の詳細値をチェックするので、高い角度分解能でハフ変換する第２ハフ変換手段の規模を小さくできる。
あるいはまた、第１傾斜角検出手段で求めた傾斜角により、第２ハフ変換手段での角度範囲を決定しても、第２ハフ変換手段の規模を小さくできる。
このためこの発明では、比較的小さなハードウェアで、高速かつ精密に画像の傾斜角を決定できる。
【００１４】
好ましくは、前記第１投票テーブルへの投票と、前記第２投票テーブルへの投票とを、並行して実行するように構成する。このようにすると、２種類の投票を並行して実行できるので、より高速で傾斜角を決定できる。この手法は、スキャナで読み込んだ画像などのように、画像の傾斜角が所定の範囲にあることが確実な場合に、高速でかつ正確に傾斜角を決定するのに適している。
【００１５】
また好ましくは、前記第１投票テーブルと、前記第２投票テーブルとを、画像処理装置の同じメモリ領域を用いて設け、さらに、前記第１投票テーブルのデータに基づいて、第２ハフ変換手段での角度範囲を決定した後に、前記第２投票テーブルへの投票を実行する。
このようにすると、傾斜角の概略値により、精密な傾斜角を探索する範囲を決定するので、任意の傾斜角に対して、精密に傾斜角を決定できる。また同じメモリ領域を第１投票テーブルと第２投票テーブルに使い分けることができるので、メモリを節約できる。投票テーブルは、処理上は角度と距離とを見出しとする大規模な２次元のテーブルであり、例えば第１投票テーブルと第２投票テーブルとで角度の要素数が同じであれば、同じメモリ領域を兼用できる。ただし投票を２回別々に行うので、処理が低速になる。
【図面の簡単な説明】
【００１６】
【図１】実施例の複合機のブロック図
【図２】実施例での前処理部のブロック図
【図３】実施例での前処理アルゴリズムを示す図
【図４】実施例でのハフ変換部〜画像回転部の基本構成を示すブロック図
【図５】実施例での投票テーブルを模式的に示す図
【図６】実施例でのハフ変換部及び傾斜角検出部の構成を示すブロック図
【図７】実施例でのハフ変換アルゴリズムを示すフローチャート
【図８】変形例でのハフ変換部及び傾斜角検出部の構成を示すブロック図
【図９】第２の実施例でのハフ変換部及び傾斜角検出部の構成を示すブロック図
【図１０】第２の実施例での、三角関数演算を示すブロック図
【図１１】第２の実施例でのハフ変換アルゴリズムを示すフローチャート
【図１２】実施例での傾斜角の決定アルゴリズムを示す図
【図１３】実施例での傾斜角の決定原理を示す図
【図１４】入力画像を直接二値化した例を示す図
【図１５】実施例での入力画像の縮小画像を示す図
【図１６】実施例で、縮小画像からノイズを除去した画像を示す図
【図１７】実施例で、ノイズの除去後の画像から抽出したエッジを示す図
【図１８】実施例で用いた、エッジ抽出フィルタを示す図
【図１９】実施例で、エッジの画像を二値化した画像を示す図
【図２０】実施例で、二値化画像から孤立点を除いた画像を示す図
【図２１】実施例で、孤立点を除いた後に、縮退処理を施した画像を示す図
【図２２】偽の最大投票線を示す図
【図２３】投票テーブルでの近傍点が有効線として複数選択される状況を示す図
【図２４】実施例で、抽出済みの有効線の近傍をマスクした際の、有効線の抽出状況を示す図で、明度は投票テーブルでの投票数を示す
【図２５】実施例での抽出した有効線を模式的に示す図
【図２６】実施例での傾斜角の決定手法を模式的に示す図
【発明を実施するための形態】
【００１７】
以下に本発明を実施するための最適実施例を示す。
【実施例】
【００１８】
図１〜図２６に、複合機２を例に実施例を示す。図１において、４はＬＡＮ、６はパーソナルコンピュータで、情報処理装置の例であり、８はルータで、インターネット１０と複合機２及びパーソナルコンピュータ６等を接続する。実施例での傾斜角の検出及び補正は複合機２で行うが、パーソナルコンピュータ６などで行っても良く、例えば、複合機２のスキャナ２０で読み取った画像をパーソナルコンピュータ６へ転送して、パーソナルコンピュータ６で傾斜角を検出して補正しても良い。その場合、パーソナルコンピュータ６が実施例の画像処理プログラムを記憶し、実行する。
【００１９】
複合機２の構造を説明する。１２はＬＡＮインターフェースで、１４はバス、１６は画像メモリで、ページメモリとして画像データを記憶する。メモリ１８は汎用のメモリで、プログラム及び中間的なデータなどを記憶する。スキャナ２０は、原稿用紙から画像を、モノクロのグレイスケールあるいはフルカラーで読み取り、プリンタ２２は画像をプリントし、Ｇ３ファクシミリ部２４は画像のＧ３ファクシミリ送信と受信とを行う。e-mail部２６は、e-mailの添付ファイルとして画像の送受信を行い、ネットワークサーバ部２８は、文書管理サーバ及びリモートプリンタなどとして複合機２を動作させる。ユーザインターフェース３０はユーザのマニュアル入力などを受け付け、画像処理部３２は種々の画像処理を行う。
【００２０】
スキャンした画像、受信画像もしくは蓄積済みの画像の傾斜角を検出するため、前処理部４０とハフ変換部５０並びに傾斜角検出部６０を設ける。そして検出した傾斜角と反対向きに同じ角度だけ、画像回転部７０で画像を回転させ、傾斜を補正する。
【００２１】
図２に前処理部４０の構成を示す。画像メモリ１６から画像データが縮小処理部４１へ入力され、画像の解像度を１／ｎ(ｎは２以上の自然数で、好ましくは４〜８，特に４〜６)に縮小する。これによって画像データの量は１／ｎ2に減少し、縮小は例えばｎ×ｎ画素のブロック毎に、画素の値の平均値を求めればよい。またより単純に、縮小処理部４１では、ｎ×ｎ画素のブロックの内の代表点、例えばブロックの左上の頂点の、１画素のデータをそのまま出力しても良い。このためハフ変換はｎ2倍高速になる。
【００２２】
同じ画像データで、データの内容と解像度は一定でも、縮小処理部４１での縮小率が異なると、傾斜角の検出結果が異なることがあった。これに対して同じ原稿を４００dpi，６００dpi，８００dpiなどの異なる解像度で読み取り、これを一定の解像度、例えば１００dpiへ縮小すると、傾斜角の検出結果は共通であった。そこでスキャン時の解像度によらず、縮小処理部４１で一定の解像度まで解像度を低下させると、解像度の違いによる傾斜角の検出値の差を解消できる。
【００２３】
複合機２でスキャンした画像以外でも、ファクシミリの受信データなどのように、スキャン時の解像度が既知の場合、同様に一定の解像度に画像を縮小する。スキャン時の解像度は、通信のプロトコルあるいは画像ファイルのヘッダなどから判明することが多い。このため、スキャン時の解像度が異なれば縮小率は異なり、縮小画像の解像度を一定にする。なおjpeg画像のようにヘッダに解像度が記載されていない場合、１／４あるいは１／８などの一定の縮小率で、画像を縮小する。
【００２４】
スムージング部４２は、平滑化フィルタなどにより縮小画像からノイズを除去し、これによって画像中のランダムなデータを、ハフ変換によって直線として抽出しないようにする。次にエッジ抽出部４３は、スムージング済みの画像から、ラプラシアンフィルタあるいはソーベルフィルタなどのエッジ抽出用フィルタにより、エッジを抽出する。これによって地色の影響が解消し、また白抜きの文字などでも、文字の輪郭に対応するエッジを抽出できる。さらにエッジの抽出により画像のデータ量が小さくなり、ハフ変換が容易になる。
【００２５】
二値化部４４は抽出したエッジを二値化する。二値化の閾値は、一定でも良く、あるいは抽出したエッジでの明度もしくはカラー値の分布などから定めても良い。さらに全てのエッジを二値化する必要があるのではなく、例えば画像中の文字部分と、写真部分及び図形部分を判別できる場合、文字部分のみを二値化することが好ましい。
【００２６】
扱う画像データは実施例ではモノクロのグレイスケール画像とするが、ＲＧＢ画像などでもよい。この場合、ＲＧＢデータを、明度画像に変換して傾斜角を検出してもよく、またＲ，Ｇ，Ｂの各成分毎に傾斜角を検出し、その平均値などを用いてもよい。
【００２７】
孤立点除去部４５は二値化画像から孤立点を除去し、二値化前のエッジ画像に対して孤立点を除去しても良い。孤立点の除去によりデータ量が減り、かつ偽の傾斜角を検出する確率が減少する。なお孤立点は写真画像中に特に多く、画像本来の傾きとは無関係なデータである。
【００２８】
縮退処理部４６は、孤立点を除去した後の二値化画像に対し、縮退処理を行う。ここに縮退処理とは、上下，左右，斜めなどの方向に有効画素が連続して並んでいる場合に、有効画素をカットする処理のことである。なお有効画素とは二値化画像においてデータのある画素をいい、白であるか黒であるかは問題にしない。縮退処理により線分は例えば１点となる。円、方形、及び十字も１点となる。この結果、画像中の図形部分及び写真部分の斜線は、例えば１点に縮小される。これに対して、文字も縮退によって小さなデータになるが、文字の行がなす直線は失われない。縮退は罫線及び下線を１点に単純化するので、罫線及び下線を傾斜角検出に用いる場合には、縮退処理部４６は設けなくても良い。
【００２９】
図３は前処理部４０の制御アルゴリズムを示し、このアルゴリズムに従ってパーソナルコンピュータ６を動作させると、この発明を実施できる。ステップ１でスキャナ２０により画像を読み取り、ステップ２で一定の解像度へ画像を縮小し、これによってハフ変換の処理速度をｎ2倍に向上させる。ステップ３でスムージングによりノイズを減らし、ステップ４でエッジを抽出して地色の影響などを除き、また白抜き文字なども検出できるようにする。そしてステップ５で二値化し、ステップ６で孤立点を除く。これによって、写真画像中などの孤立点の傾斜角の検出への影響を小さくできる。なお孤立点の除去は二値化の前に行っても良い。そして好ましくはステップ７で縮退処理によりデータを単純化し、特に写真部分及び図形部分の直線を例えば１点まで単純化する。
【００３０】
ステップ２〜ステップ７の前処理は、画像のスキャンと同期して行い、またハフ変換部５０でのハフ変換、傾斜角検出部６０での傾斜角の検出、画像回転部７０での傾斜角の補正も、スキャンと同期して行えるようにする。ここに同期とは、これらの処理速度がスキャナ２０の読み込み速度以上であることを意味し、このようにすると画像のスキャンと同時にリアルタイムに画像の傾斜を補正できる。
【００３１】
図４はハフ変換部５０〜画像回転部７０の原理的構造を示し、ハフ変換部５０及び傾斜角検出部６０の実用的な構造は図６〜図１１に示す。ハフ変換部５０は複数の実行ユニット５１を備えて、ハフ変換を並列に実行する。実行ユニット５１はρ値計算部５２とsinθ及びcosθに対するテーブル５３とから成り。０°〜１８０°等の投票範囲を分割して、分割した投票範囲毎に複数の実行ユニット５１で並列に実行する。ρ値計算部５２はテーブル５３からsinθ及びcosθの値を読み出し、縮退処理部４６もしくは孤立点除去部４５から出力された有効画素の位置(ｘ，ｙ)に対し、ρ値を  ρ＝ｘcosθ＋ｙsinθ  として計算する。投票テーブル５４はθとρの２次元のテーブルで、管理部５５は複数の実行ユニット５１を管理する。
【００３２】
図５に、ρ値計算部５２と投票テーブル５４との関係を示す。テーブル５４の各点はρとθとの組み合わせ、即ち元の画像での線分を表している。テーブル５４の横軸はθを、縦軸はρを表し、所定の投票範囲をカバーする。なおρの分解能は、θの分解能よりも低くても良い。そして投票範囲を分割して、複数の実行ユニットに割り当てる。次ぎにｘ，ｙの値が入力されると、θ毎にρの値を計算し、表の該当する位置のデータを１加算する。その結果、例えば左から３つめのカラムに○で示すように、(ρ，θ)値が投票される。また５７はマスクで、テーブル５４から有効線(抽出する直線)として抽出済みの点の周囲をマスクし、マスク５７の外部から次の有効線が抽出されるようにする。
【００３３】
図４に戻り、有効線抽出部６１は投票テーブル５４から例えば上位ｍ位の点を抽出する。投票テーブル５４で投票数の多い点は、画像での有効線である可能性が高い。そして抽出済みの点の周囲にマスク５７を施し、マスク５７内からの他の点が抽出されないようにする。候補角抽出部６２は、抽出した有効線から傾斜角の候補(ｋ個で例えばｍ／２個以上)を抽出し、決定部６３はこれらの候補角に基づいて傾斜角θｄを決定する。決定した傾斜角θｄを座標計算部７１へ入力し、画像メモリ１６の記憶画像の各画素に対し、傾斜補正後の座標(アドレス)を計算する。アドレス生成部７２は、傾斜補正前の座標に基づいて、画像メモリ１６への読み出しアドレスを生成する。bicubic処理部７３は読み出したデータを補間し、傾斜補正後の座標に基づいて、補間後のデータを画像メモリ１６へ書き戻す。これらの処理によって、画像メモリ１６の画像は、傾斜を補正するように回転する。なお回転には単純なアフィン変換などを用いてもよい。
【００３４】
図５，図６の処理を±０.１°程度の精度で実行すると、
・  投票テーブル５４及びsinθとcosθのテーブル５３の規模が大きくなる、
・  元の画像の１点に対して１８００票の投票がなされ、処理量が大きくなる、
との問題がある。そこでこれらの点を解決するため、図６〜図８（第１の実施例とその変形）及び図９〜図１１（第２の実施例）を提案する。図６〜図１１の各例では、θを高精度に決定すべきエリアに対してのみ、精密な刻み（刻みは角度の分解能）で投票を行ない、他のエリアでは粗い刻みで投票を行なう。そのため図６の第１の実施例では、２つのハフ変換部１５０，１５２で同時に並行して投票を行い、図８の変形例では投票テーブルの刻みをエリアにより変更する。図９〜図１１の第２の実施例では、２回の投票を行い、１回目の投票で傾斜角の概略値を求め、２回目の投票で正確な傾斜角を求める。これらにより、図４のハフ変換を小規模なハードウエアで高速かつ精密に実行する。
【００３５】
図６において、１５０，１５２は新たなハフ変換部で、その構造は図４のハフ変換部５０と同一であるが、ハフ変換部１５０では例えば１°刻みで０°〜１８０°の投票範囲を処理し、ハフ変換部１５２では例えば０.１°刻みで０°〜５°，８５°〜９５°，及び１７５°〜１８０°の投票範囲（合計２０°、好ましくは１０〜３０°）を処理する。そして図４の傾斜角検出部６０と同様の傾斜角検出部１６０，１６２を設け、傾斜角検出部１６０はハフ変換部１５０，１５２からのデータで傾斜角を求め、傾斜角検出部１６２はハフ変換部１５０，１５２からのデータで傾斜角を求める。整合性チェック部１６６は、傾斜角検出部１６０，１６２で別々に求めた２つの傾斜角の整合性をチェックする。
【００３６】
画像処理プログラムとしては、図７のステップ１１で、１°刻みのハフ変換と０.１°刻みのハフ変換を行うように２回の投票を並行して行い、ステップ１２で２つの投票テーブルから各々傾斜角を求める。ハフ変換部１５０の１°刻みの粗い投票テーブルから求めた傾斜角が、０°〜５°，８５°〜９５°，あるいは１７５°〜１８０°の範囲にあれば、２つの傾斜角が整合するものとして、傾斜角検出部１６０で求めた傾斜角を有効とする。ハフ変換部１５０の投票テーブルから求めた傾斜角が、０°〜５°，８５°〜９５°，あるいは１７５°〜１８０°の範囲に無い場合は、
・  傾斜角の検出に失敗したものとして、傾斜の補正を行わない、  あるいは
・  ハフ変換部１５０の投票テーブルから求めた傾斜角を有効として、傾斜の補正を行う、
等の処理を行う。
【００３７】
図６，図７の処理は、スキャナで読み込んだ画像、受信した画像、及びＰＤＦ画像では、画像が走査方向から著しく、例えば５度以上傾いていることは少ないことを前提にしている。そこでハフ変換部１５２と傾斜角検出部１６２で、０°±５°及び９０°±５°の範囲に対して精密に傾斜角を求め、ハフ変換部１５０と傾斜角検出部１６０でその整合性をチェックする。例えば１８０°の全範囲に対し０.１°刻みで投票テーブルに投票すると、投票テーブルの規模はθに対して１８００レベルで、三角関数テーブルの規模はθが０°〜４５°をカバーするものとして、４５×１０（１°当たり１０レベル）×２（sinθとcosθ）の９００データとなる。また処理回数は元の画像の１点当たり、１８００回である。これに対して、図６，図７の実施例では、
・  投票テーブルの規模がθに対して１８０°÷１＋２０°÷０.１の３８０レベル、
・  三角関数テーブルの規模が９０レベル＋１０°÷０.１の１８０レベルで、
図４の機能ブロックをそのまま実装した場合の約１／５となる。ここでは距離ρの分解能が変わらないものとしているが、一般的にはθの分解能にρの分解能を比例させるので、図４の構造をそのまま実装すると、投票テーブルの規模は図６，図７の場合の約５０倍となる。また元の画像の１点当たりの処理回数は１８００回から３８０回に減少し、これも約１／５になる。従って小さなハードウェアで、高速かつ精密にハフ変換を実行できる。
【００３８】
図８のハフ変換部１５４では、０°〜５°，８５°〜９５°，及び１７５°〜１８０°の範囲を１／１６°刻みで処理し、他の角度に対しては１°刻みで処理する。傾斜角検出部１６４では、０°〜５°，８５°〜９５°，及び１７５°〜１８０°での投票数をｍ倍、例えば４〜１６倍し、他の角度では投票数をそのまま用いて、傾斜角を決定する。ｍ倍するのは、０°〜５°，８５°〜９５°，及び１７５°〜１８０°では、１°の範囲内の投票が１６レベルに分散するからである。またｍを４とするのは、０°〜５°，８５°〜９５°，及び１７５°〜１８０°では、１°の範囲内でのピークを検出し、他の角度では１°当たりの平均を検出しているからである。そしてｍの値を小さくすると整合性を厳しくチェックし、大きくするとチェックを緩めることになる。
【００３９】
図８の変形例は、整合性のチェックを緩めて処理を簡単にしたものであるが、処理を簡単にする効果よりも、整合性のチェックが曖昧になる不利益の方が大きい。即ち、図８での効果は、０°〜５°，８５°〜９５°，及び１７５°〜１８０°で２重に投票することを避けることができる点であるが、図６でのθの合計３８０レベルの処理中の２０レベルを省略できるに過ぎない。
【００４０】
図９〜図１１の第２の実施例では、最初に１８０°÷２５６レベルの０.７０３１２５°刻みでハフ変換部１５６へ投票し、傾斜角検出部６０で傾斜角θｄを仮に決定する。仮に決定した傾斜角θd及びその直交角φdの周囲の合計例えば２０°、好ましくは１０°〜３０°に対して、２０°÷２５６レベルの０.０７８１２５°刻みで、２回目の投票を行う。そして２回目の投票結果から、傾斜角検出部６０で傾斜角θｄを最終的に決定する。ここに直交角φdは、傾斜角θd＋π／２あるいはθd−π／２で、値が負にならない角度である。投票の範囲は、θd±α°及びφd±α°（αは例えば５°で、好ましくは２°〜１０°）である。
【００４１】
第１回の投票と第２回の投票で、投票テーブルに論理アドレスでの同じメモリ領域を用いると、メモリを節約できる。またsinθとcosθのテーブルに同じメモリ領域を用いて、データを書き換えると、１回目の投票も２回目の投票も、sinθとcosθのテーブルから連続したアドレスでデータを読み出せる。sinθとcosθのテーブルを書き換えるための三角関数データ計算部１７０を図１０に示し、１７１は粗テーブルで０°〜４５°の範囲に対して、sinθとcosθとを例えば０.７０３１２５°刻みで記憶する。細密テーブル１７２は、０°〜５°の範囲に対して、sinθとcosθとを例えば０.０７８１２５°刻みで記憶する。そして傾斜角θdが決定されると、θd±α°及びφd±α°内の角度に対するsinθとcosθを、加法定理計算部１７３により計算し、テーブルを書き換える。ただしsinθとcosθのテーブルを、第１回の投票用と第２回の投票用に、２種類記憶しても良い。
【００４２】
図９，図１０での処理を図１１に示し、ステップ２１でsinθとcosθのテーブルに、１８０°÷２５６レベルの刻みでデータを書き込み（ステップ２１）、投票テーブルでは０°〜１８０°を２５６レベルに分割して、第１回の投票を行う（ステップ２２）。そして傾斜角θdを仮に決定し（ステップ２３）、sinθとcosθのテーブルをθd±αとφd±αの範囲をカバーするように、４α°÷２５６レベルの刻みで上書きする（ステップ２４）。次ぎにθd±αとφd±αの範囲に対して、θの範囲及びρの範囲を絞った投票テーブルを、同じメモリ領域で実現し、第２回の投票を行う（ステップ２５）。そして第２回の投票結果から、傾斜角θdを最終的に決定する。
【００４３】
図９〜図１１の実施例では２回の投票を行い、傾斜角の決定精度を例えば９倍（αが５°の場合）にする。必要なハードウェア規模は粗い角度刻みで１回の投票を行う場合とほぼ同じで、データ処理量は約２倍である。図９〜図１１の実施例は２回の投票を別々に行うので、並列に投票する図６，図７の実施例よりも低速で、スキャナでの画像の読み取りと同期して処理することが難しい。しかし図９〜図１１の実施例では、画像の傾斜が大きい場合にも正確な傾斜角を決定できる。
【００４４】
図１２に傾斜角検出部６０のアルゴリズムを示し、投票テーブルから上位ｍ位、例えば１６位あるいは８位の(ρ，θ)からなる点を抽出する(ステップ３１)。そして抽出済みの点の近傍、例えば１辺が５〜４０レベルの正方形からなる近傍をマスクし(ステップ３２)、同じ近傍内から２点以上が抽出されないようにする。なお最大投票数の１／２以上の投票数のある(ρ，θ)のみを抽出する。従ってｍ位目の点の投票数が最大投票数の１／２未満の場合はエラーとし、傾斜角の検出を行わず、画像回転部７０は画像を回転させない(ステップ３３)。ステップ３２，３３はステップ３１を実行するための補助的な処理である。このようにして、他の点の近傍に入らず、かつ最大投票数の１／２以上の点をｍ個抽出する。１／２以上は例であり、例えば２／３以上あるいは０.４以上などとしても良い。ステップ３１〜３３が、有効線抽出部６１の処理に対応する。なお最大投票数の例えば１／２以上の投票数の点を最大投票数の点を含めて抽出し、所定個以上の点を抽出できないとエラーとしても良い。この場合は、抽出する点の数が一定ではなくなる。
【００４５】
次に傾斜角の候補を求めるための角度をθｘとし、その直交角をφｘとする。ここに  φｘは正または０で、かつ  φｘ＝θｘ＋π／２  もしくは  φｘ＝θｘ−π／２  である。δを許容範囲とし、例えばδは１°あるいは０.５°などであり、θｘ±δ及びφｘ±δの範囲に入る点(ρ，θ)の個数が最大となるように、θｘを決定する。そしてθｘ±δ及びφｘ±δの範囲に入る点を出力する(ステップ３４)。言い換えると、ｍ個の点に対し、角度θ成分が±δの範囲で一致する点の数が最大となる角度をθｘとする。なお単純にθ成分が±δの範囲で一致する点の数を問題とする代わりに、θｘ±δ及びφｘ±δの範囲に入る点に対する、投票数の和が最大となるようにしても良い。そしてこれらの点の数ｋが閾値未満の場合、例えばｍ／２未満もしくはｍ／３未満の場合、ステップ３５でエラーとする。エラーの場合、傾斜角の検出を行わず、画像回転部７０は画像を回転させない。ステップ３４，３５が、候補角抽出部６２の処理に対応する。
【００４６】
ステップ３６は決定部６３の処理に対応し、ステップ３４で求めたｋ個の点(ρ，θ)に対し、例えばθの単純平均値を傾斜角θｄとして出力する。あるいはｋ個の点でのθの加重平均を用い、重みには投票数ｖiを用いても良い。これらに代えて、ｋ個のθの候補θ1〜θkの中で、投票数ｖiが最大のθを傾斜角θｄとしてもよい。ステップ３６ではθｄを出力し、θｄがπ／２を越える場合、θｄ−π／２、即ちφｄを出力する。
【００４７】
図１３〜図２６に実施例の動作を示す。図１３の上部は原稿画像を示し、画像中の文字の列を直線と見なして、その傾斜を検出する。従って実施例の目的は、図１３の上部の画像を図１３の下部の画像に変換し、これに対するハフ変換を行うことにある。
【００４８】
図１４は入力画像(画像メモリ１６の画像)を、縮小もスムージングもエッジ抽出も行わずに、直接二値化した例を示し、円でマークしたように、文字以外の写真部分などの黒画素(この場合の有効画素)が多くなり、ハフ変換の負担が増すと共に、写真中の斜線などの影響が強くなり、検出精度が低下する。そこで入力画像をグレースケールで取り扱い、縮小、スムージング、エッジ抽出等の画像処理を施した後に、二値化する。ハフ変換を高速で行うため、入力画像を１／ｎに縮小し、これによって以降の計算時間を１／ｎ2に減少させる(図１５)。
【００４９】
次にスムージングによりノイズを除去し(図１６)、エッジを抽出すると図１７の画像が得られる。エッジの抽出により、地色の影響が無くなり、また白抜き文字にも対応でき、さらにデータを単純化して、ハフ変換を容易にする。
【００５０】
図１８に、エッジの抽出フィルタ８０を示す。被処理画像８１に対し、フィルタ８０を左上側から適用することにより、被処理画像８１の下側と右側のエッジ８２を抽出する。これによって被処理画像８１のエッジ全体を検出する場合に比べ、エッジの量を１／２にできる。以上のように、好ましくは、上下左右４種類のエッジの内で、下と右、下と左、上と右、上と左のように、２種類のエッジを抽出する。
【００５１】
エッジ抽出後の画像を二値化すると、図１９の画像が得られる。図１９の画像から孤立点を除去すると、図２０の画像が得られる。なお孤立点の除去は、図１７のエッジの画像に対して行っても良い。図１９，図２０のように、図形部分の線あるいは写真部分の線が残っていると、傾斜角の誤検出の原因となる。そこで縮退処理を行うと図２１の画像が得られ、写真や図形中の線は単なる点あるいは短い線分などに変換され、文字の列からなる行は基本的に保存される。
【００５２】
そこで縮退処理後の画像に対しハフ変換を行うことにより、文字の行から成る直線のみを検出できる。ただし罫線を伴う画像に対し、罫線の向きを傾斜の検出に用いたいことがある。この場合、縮退処理は不要である。
【００５３】
ハフ変換により投票テーブルにデータが蓄積され、投票テーブルから投票数が最大の点のみを単純に取り出すと、誤った検出が行われることがある。図２２はこのような例を示し、図２２では画像の一部のみを表示するので、「最大投票直線」がどこから抽出されたのか分かり難いが、画像中の写真部分等から抽出されたものである。このため投票数が上位の点を複数抽出する。ここで単純に上位ｍ位までの点を抽出すると、投票テーブル内での近傍の点が複数抽出されることが多い。そこで投票テーブル５４から最上位の点を抽出し、抽出した点の近傍をマスクして次の投票数の点を抽出することにより、抽出済みの点の近傍の点を抽出しないようにする。このようにして、上位ｍ位の点を抽出する。ここで抽出した上位ｍ位のうち、最下位の点が最上位の点の例えば１／２以上の投票数を持たない場合、検出をエラーとする。文字から成る行を抽出している場合、最大投票数の点と、上からｍ位の点とで、投票数に余り大きな差はないはずである。これにもかかわらず大きな差があるのは、最上位の点が図形中の直線部分などである可能性が高い。あるいはまた、上位ｍ位(例えば１６位)のうちから、最上位の点に対して所定の割合以上（例えば１／２以上）の投票数を持つ点を抽出し、抽出した点の数が所定値ｋ（例えば４）以下の場合は、エラーとして傾斜角を未検出としても良い。
【００５４】
図２４に投票テーブルの状況を模式的に示し、ここでは投票数を明度で表している。そして選択済みの点の近傍を、黒い四角形のマスクで覆っている。図２４では上位８点を抽出済みである。
【００５５】
抽出された上位ｍ位の点に対し、傾斜角を決定する。この手続を図２５，図２６に模式的に示し、ここではｍは例えば８とする。文字の行を検出している場合、文字ブロックの上下の列も同時に検出できるので、傾斜角θｄと、その直交角φｄとに意味がある。また候補を抽出する際の許容誤差をδ(０.５°あるいは１°程度)とし、角θｘ±δと      φｘ±δの範囲内に入る点の数ｋが最大となるように、θｘを決定する。ここでどの角度に対してもｋの値が閾値(例えばｍ／２)未満の場合、例えばエラーとする。閾値以上の点を含む角θｘが得られた場合、含まれる点の角度の単純加算平均、あるいは加重平均などにより、候補角を決定する。これは図１２のステップ３６の処理である。
【００５６】
以上のようにして傾斜角θｄを例えば±０.１°程度の精度で決定すると、画像回転部７０により画像を回転させて傾斜を補正する。画像の回転自身は単純な処理であり、例えばスキャンと同期して実行できる。
【００５７】
実施例では傾斜角の回転と補正とを複合機２の内部で行う例を示したが、パーソナルコンピュータ６などで行っても良い。その場合、実施例の画像処理プログラムをパーソナルコンピュータなどの情報処理装置で実行すると、情報処理装置はこの発明の画像処理装置となる。
本の見開きの傾斜を検出する場合、例えばスキャン前に原稿の種類が見開きであることを入力すると、左右別々の傾斜角を検出できる。あるいは入力画像を左右に分割して、傾斜角を求め、左右の傾斜角が異なると、見開きの画像であると推定しても良い。
【符号の説明】
【００５８】
２      複合機
４      ＬＡＮ
６      パーソナルコンピュータ
８      ルータ
１０    インターネット
１２    ＬＡＮインターフェース
１４    バス
１６    画像メモリ
１８    メモリ
２０    スキャナ
２２    プリンタ
２４    Ｇ３ファクシミリ部
２６    e-mail部
２８    ネットワークサーバ部
３０    ユーザインターフェース
３２    画像処理部
４０    前処理部
４１    縮小処理部
４２    スムージング部
４３    エッジ抽出部
４４    二値化部
４５    孤立点除去部
４６    縮退処理部
５０    ハフ変換部
５１    実行ユニット
５２    ρ値計算部
５３    テーブル
５４    投票テーブル
５５    管理部
５６    データ
５７    マスク
６０    傾斜角検出部
６１    有効線抽出部
６２    候補角抽出部
６３    決定部  
７０    画像回転部
７１    座標計算部
７２    アドレス生成部
７３    bicubic処理部
８０    フィルタ
８１    被処理画像
８２    エッジ
１５０〜１５６  ハフ変換部
１６０〜１６４  傾斜角検出部
１６６  整合性チェック部
１７０  三角関数データ計算部  
１７１  粗テーブル
１７２  細密テーブル
１７３  加法定理計算部  
【図１】
2010244353.tif 000003
【図２】
2010244353.tif 000004
【図３】
2010244353.tif 000005
【図４】
2010244353.tif 000006
【図５】
2010244353.tif 000007
【図６】
2010244353.tif 000008
【図７】
2010244353.tif 000009
【図８】
2010244353.tif 000010
【図９】
2010244353.tif 000011
【図１０】
2010244353.tif 000012
【図１１】
2010244353.tif 000013
【図１２】
2010244353.tif 000014
【図１７】
2010244353.tif 000015
【図１８】
2010244353.tif 000016
【図２１】
2010244353.tif 000017
【図２５】
2010244353.tif 000018
【図２６】
2010244353.tif 000019
【図１３】
2010244353.tif 000020
【図１４】
2010244353.tif 000021
【図１５】
2010244353.tif 000022
【図１６】
2010244353.tif 000023
【図１９】
2010244353.tif 000024
【図２０】
2010244353.tif 000025
【図２２】
2010244353.tif 000026
【図２３】
2010244353.tif 000027
【図２４】
2010244353.tif 000028