(57)【要約】【課題】画像中の線分抽出処理の内容を改善することで、画像の傾き補正の実行速度を向上させ得る画像処理装置を提供する。【解決手段】画像の傾きを補正する画像処理装置において、画像データを入力する画像入力手段と、該画像内の線分群を抽出する線分抽出手段と、該線分と所定の基準方向との角度を検出する角度検出手段と、該角度検出手段の検出結果に基づいて前記画像を回転させる画像回転手段と、を有し、前記線分抽出手段は、前記画像のエッジ領域からなるエッジ領域群を抽出するエッジ領域抽出手段と、該エッジ領域群に基づいて、所定長さ以上のランレングスからなるランレングス群を抽出するランレングス抽出手段と、を有する画像処理装置とする。【選択図】  図３
2007295210.tif 000002
【特許請求の範囲】
【請求項１】
画像の傾きを補正する画像処理装置において、
画像データを入力する画像入力手段と、
該画像内の線分群を抽出する線分抽出手段と、
該線分と所定の基準方向との角度を検出する角度検出手段と、
該角度検出手段の検出結果に基づいて前記画像を回転させる画像回転手段と、を有し、
前記線分抽出手段は、
前記画像のエッジ領域からなるエッジ領域群を抽出するエッジ領域抽出手段と、
該エッジ領域群に基づいて、所定長さ以上のランレングスからなるランレングス群を抽出するランレングス抽出手段と、を有することを特徴とする画像処理装置。
【請求項２】
前記線分抽出手段は、
前記ランレングス群において、所定の連結関係にあるランレングス同士を統合する統合手段を有し、
該統合を行うことにより、前記線分を抽出することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記エッジ領域抽出手段は、
前記画像のエッジからなるエッジ群を抽出するエッジ抽出手段と、
画像を膨張させる膨張手段と、を備えたことを特徴とする請求項１または請求項２に記載の画像処理装置。
【請求項４】
前記エッジ領域抽出手段は、
前記画像のエッジからなるエッジ群を抽出するエッジ抽出手段を備え、
前記エッジの近傍の画素を抽出することにより、前記エッジ領域群を抽出することを特徴とする請求項１または請求項２に記載の画像処理装置。
【請求項５】
前記統合手段は、
一のランレングスと他のランレングスが、主走査方向または副走査方向において互いに接している場合に、これらのランレングスを統合させることを特徴とする請求項２から請求項４の何れかに記載の画像処理装置。
【請求項６】
前記線分抽出手段は、
前記ランレングスの副走査方向の座標に基づく参照範囲情報を用いて、前記統合を行うことを特徴とする請求項２から請求項５の何れかに記載の画像処理装置。
【請求項７】
前記線分抽出手段は、
前記ランレングス群における各ランレングスのうち副走査方向に隣り合うものを分類する処理を、前記ランレングス群における各ランレングスについて行い、
該分類結果に基づいて、前記統合を行うことを特徴とする請求項２から請求項６の何れかに記載の画像処理装置。
【請求項８】
画像の傾きを補正する画像処理装置において、
画像データを入力する画像入力手段と、
該画像内の線分を抽出する線分抽出手段と、
該線分と所定の基準方向との角度を検出する角度検出手段と、
該角度検出手段の検出結果に基づいて、前記画像を回転させる画像回転手段と、
を有することを特徴とする画像処理装置。
【請求項９】
画像の傾きを補正する画像処理方法であって、
画像データを入力する画像入力ステップと、
該画像内の線分群を抽出する線分抽出ステップと、
該線分と所定の基準方向との角度を検出する角度検出ステップと、
該検出結果に基づいて前記画像を回転させる画像回転ステップと、
を有することを特徴とする画像処理方法。
【請求項１０】
前記線分抽出ステップは、
前記画像のエッジからなるエッジ群を抽出するエッジ抽出ステップと、
該エッジの近傍の画素を抽出することにより、エッジ領域群を抽出するエッジ領域抽出ステップと、
該エッジ領域群に基づいて、所定長さ以上のランレングスからなるランレングス群を抽出するランレングス抽出ステップと、を含み、
前記ランレングス群において、所定の連結関係にあるランレングス同士を統合することにより、前記線分群を抽出することを特徴とする請求項９に記載の画像処理方法。
【請求項１１】
請求項１から請求項８の何れかに記載の画像処理装置を動作させる画像処理プログラムであって、コンピュータを上記の各手段として機能させるための画像処理プログラム。
【請求項１２】
請求項１１に記載の画像処理プログラムが記録されたことを特徴とするコンピュータ読取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像の傾き補正を高速に処理する画像処理装置、画像処理方法、画像処理プログラム、およびこの画像処理プログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
近年のハードウェアの進歩に伴い、ＰＣのみならず、ＰＤＡ、携帯電話などをターゲットとした各種情報の電子配信サービスが広がっている。
【０００３】
例えばマンガを電子配信する場合、コンテンツを画像データとして作成することとなる。この場合、既存の校正済み書籍を基に、（１）原稿のスキャナ入力、（２）画像の傾き補正、（３）各種画像処理による画像の整形、（４）コマ切り出し・エフェクト付与などの人手編集、（５）コンテンツ出力、までの作成過程を辿るのが一般的である。この過程の中で（４）の人手編集以外は、処理の自動化がなされ、ローコストでコンテンツが作成されている。
【０００４】
また上記の一連の過程において、（２）の画像の傾き補正処理は重要な処理の一つである。特に商用コンテンツの場合、その品質を保持するために、高精度に傾きを補正しておく必要がある。
【０００５】
このような要請に対し、入力画像の傾きを自動的に補正する従来技術は、電子ファイリングシステムや、ＯＣＲ［Optical Character Reader：光学式文字読取装置］の前処理機能として、既に各種方式で実現されている。また、マンガに特化したものとしては、例えば特許文献１に開示されているものが挙げられる。
【０００６】
特許文献１に開示されている従来技術は、画像のエッジ画素を抽出し、エッジ画素を連結し、連結したエッジ画素列に方向コードを付与し、方向コードを統合する処理を設けている。これにより、主にマンガのコマ線に該当する画像中の水平・垂直線分を抽出し、抽出した複数の線分の傾き角度から、原稿の傾きを決定し、傾きを補正するものである。
【特許文献１】特開２００２−９２６０６号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながらこの従来技術は、エッジ画素を連結する際に、注目エッジ画素の８近傍画素を所定の回転方向（従来技術では時計まわり）に見て最初にあたる未連結エッジ画素を連結する処理、すなわち「画素単位の処理」を繰り返すものである。そのため、比較的処理負担が大きく、実行速度が低下するという問題が発生していた。
【０００８】
そこで上記の問題点に鑑み、本発明は、画像中の線分抽出処理の内容を改善することで、画像の傾き補正の実行速度を向上させ得る画像処理装置の提供を目的とする。
【課題を解決するための手段】
【０００９】
上記目的を達成すべく、本発明に係る画像処理装置は、画像の傾きを補正する画像処理装置において、画像データを入力する画像入力手段と、該画像内の線分群を抽出する線分抽出手段と、該線分と所定の基準方向との角度を検出する角度検出手段と、該角度検出手段の検出結果に基づいて前記画像を回転させる画像回転手段と、を有し、前記線分抽出手段は、前記画像のエッジ領域からなるエッジ領域群を抽出するエッジ領域抽出手段と、該エッジ領域群に基づいて、所定長さ以上のランレングスからなるランレングス群を抽出するランレングス抽出手段と、を有する構成（第１の構成）とする。
【００１０】
本構成によれば、画像の傾き補正に用いられる線分群を、予め抽出されたランレングス群に基づいて抽出することができる。そのため上記した従来技術のように、１画素単位でエッジ画素を連結して線分を抽出するようなものに比べて、画像の傾き補正の実行速度を向上させることができる。また、エッジ領域群を抽出するエッジ領域抽出手段を有しているため、ランレングス群の抽出処理を容易に行うことが可能となっている。
【００１１】
なおここでの「線分」とは、画像中における画素の集合体であって、その集合状態によりある基準方向（例えば水平方向や垂直方向など）との角度が検出され得るものである。また「線分群」とは、線分の集合（単数である場合も含む）を指すものである。
【００１２】
また「エッジ」とは、異なる属性（例えば黒と白）の画素がある走査方向に隣り合うとき、その境界部に存在する画素を指し、「エッジ領域」とは、エッジの近傍をも含めた一定領域内の画素の集合を指し、「エッジ領域群」とは、エッジ領域の集合（単数の場合も含む）を指す。また「ランレングス」とは、ある走査方向に連続する画素の集合体である。また「ランレングス群」は、ランレングスの集合（単数の場合も含む）を指す。
【００１３】
また上記第１の構成において、前記線分抽出手段は、前記ランレングス群において、所定の連結関係にあるランレングス同士を統合する統合手段を有し、該統合を行うことにより、前記線分を抽出する構成（第２の構成）としてもよい。
【００１４】
本構成によれば、所定の連結関係にあるランレングス同士が統合されることによって線分が抽出されるため、該抽出処理を画一的かつ確実に実行することができる。なお「連結関係」は、線分を抽出するという目的に沿うものであれば、その内容は限定されない。
【００１５】
また上記第１または第２の構成において、前記エッジ領域抽出手段は、前記画像のエッジからなるエッジ群を抽出するエッジ抽出手段と、画像を膨張させる膨張手段と、を備えた構成（第３の構成）としてもよい。
【００１６】
本構成によれば、画像からエッジ群が抽出され、各エッジを膨張手段によって膨張させることができるから、エッジ領域群の抽出を適切に行うことができる。なおここでの「膨張」とは、ある属性を持つ画素に対し、その画素の近傍の画素（例えば接している４画素や、取り囲む８画素など）についても同じ属性と認識することである。
【００１７】
また上記第１または第２の構成において、前記エッジ領域抽出手段は、前記画像のエッジからなるエッジ群を抽出するエッジ抽出手段を備え、前記エッジの近傍の画素を抽出することにより、前記エッジ領域群を抽出する構成（第４の構成）としてもよい。
【００１８】
本構成によれば、画像からエッジ群が抽出され、エッジの近傍の画素を抽出することによりエッジ領域群が抽出されるから、該処理を適切に行うことができる。なおここでの「エッジの近傍の画素」とは、例えばエッジ画素に接している４画素やエッジ画素を取り囲む８画素などとしてもよく、後に適切な線分群を抽出するという趣旨に沿う限り、その内容は限定されない。
【００１９】
また上記第２から第４の何れかの構成において、前記統合手段は、一のランレングスと他のランレングスが、主走査方向または副走査方向において互いに接している場合に、これらのランレングスを統合させる構成（第５の構成）としてもよい。
【００２０】
本構成によれば、ランレングス同士が統合された結果、途切れの無い線分を抽出することが可能となる。そのため、該線分を用いた角度検出処理を容易に行うことができる。なおここでの「主走査方向」は、ランレングス抽出に係る走査方向のことである。また以下、画像平面上において「主走査方向」に直交する方向を「副走査方向」とする。
【００２１】
また上記第２から第５の何れかの構成において、前記線分抽出手段は、前記ランレングスの副走査方向の座標に基づく参照範囲情報を用いて、前記統合を行う構成（第６の構成）としてもよい。
【００２２】
本構成によれば、参照範囲情報（あるランレングスについて、前記連結関係の有無を調べる範囲を定める情報）を用いて統合処理がなされるから、該処理の効率向上が実現でき、ひいては画像の傾き補正をより高速に実行することができる。すなわち、線分を抽出するという目的から、あるランレングスに対する統合対象は、副走査方向において近接したランレングスに限定されることが多い。そこで参照範囲情報を用いて、例えば連結関係のないことが明らかなランレングスを予め調査対象から排除することにより、統合処理の効率向上がなされる。
【００２３】
また上記第２から第６の何れかの構成において、前記線分抽出手段は、前記ランレングス群における各ランレングスのうち副走査方向に隣り合うものを分類する処理を、前記ランレングス群における各ランレングスについて行い、該分類結果に基づいて、前記統合を行う構成（第７の構成）としてもよい。
【００２４】
本構成によれば、当該分類結果に基づいて、各ランレングスに隣り合うもののみを連結関係の調査対象とすることができるから、前記統合処理を極めて効率の良いものとすることができる。なおここでの「副走査方向」は、ランレングス抽出に係る副走査方向を指す。
【００２５】
また本発明に係る画像処理装置は、画像の傾きを補正する画像処理装置において、画像データを入力する画像入力手段と、該画像内の線分を抽出する線分抽出手段と、該線分と所定の基準方向との角度を検出する角度検出手段と、該角度検出手段の検出結果に基づいて、前記画像を回転させる画像回転手段と、を有する構成（第８の構成）とする。
【００２６】
また本発明に係る画像処理方法は、画像の傾きを補正する画像処理方法であって、画像データを入力する画像入力ステップと、該画像内の線分群を抽出する線分抽出ステップと、該線分と所定の基準方向との角度を検出する角度検出ステップと、該検出結果に基づいて前記画像を回転させる画像回転ステップと、を有する方法（第９の方法）とする。
【００２７】
また上記第９の方法において、前記線分抽出ステップは、前記画像のエッジからなるエッジ群を抽出するエッジ抽出ステップと、該エッジの近傍の画素を抽出することにより、エッジ領域群を抽出するエッジ領域抽出ステップと、該エッジ領域群に基づいて、所定長さ以上のランレングスからなるランレングス群を抽出するランレングス抽出ステップと、を含み、前記ランレングス群において、所定の連結関係にあるランレングス同士を統合することにより、前記線分群を抽出する方法（第１０の方法）であってもよい。
【００２８】
本方法によれば、線分抽出ステップにおいて、エッジ群の抽出、エッジ領域群の抽出、およびランレングス群の抽出を経ることで、所定の基準方向との角度を検出するための線分を適切に抽出させることが可能となる。
【００２９】
また、上記第１から第８の何れかの構成に係る画像処理装置を動作させる画像処理プログラムであって、コンピュータを上記の各手段として機能させるための画像処理プログラムであれば、上記した内容の画像処理を、適切なハードウェアを備えたコンピュータに実行させることができる。また、上記画像処理プログラムが記録されたコンピュータ読取り可能な記録媒体も有用である。
【発明の効果】
【００３０】
本発明の構成によれば、画像の傾き補正に用いられる線分群を、予め抽出されたランレングス群に基づいて抽出することができる。そのため上記した従来技術のように、１画素単位でエッジ画素を連結して線分を抽出するようなものに比べて、画像の傾き補正の実行速度を向上させることができる。また、エッジ領域群を抽出するエッジ領域抽出手段を有しているため、ランレングス群の抽出処理を容易に行うことが可能となっている。
【発明を実施するための最良の形態】
【００３１】
以下、図面を用いて本発明の実施の形態を説明する。
図１は、本発明にかかる画像処理装置のハードウェア構成を示すブロック図である。
図１を参照して、本発明にかかる画像処理装置は、画像処理装置全体を制御する制御部１０１と、データが格納されているメモリ部１０２と、入力処理部１０３と、入力装置１０４と、線分抽出部１０５と、角度検出部１０６と、回転処理部１０７で構成されており、各処理部はバス１０８で接続されている。
【００３２】
制御部１０１は、一般的にはＣＰＵ［Central Processing Unit］が該当するが、何らかのハードウェアで構成されていても良い。本願では、画像処理装置全体を制御するブロックを制御部と呼び、その構成は限定しない。
【００３３】
メモリ部１０２は、一般的にはＲＯＭ［Read Only Memory］とＲＡＭ［Random Access Memory］で構成されるが、例えばＲＡＭだけでも良い。本願では、画像処理装置の各種データを保持するブロックをメモリ部と呼び、その構成は限定しない。
【００３４】
入力処理部１０３は、入力装置１０４とつながっており、入力装置から入力された画像データを２値化し、バス１０８を介してメモリ部１０２へ格納する。入力装置１０４は、一般にはスキャナやカメラなどの画像入力装置である。本願では、画像データを入力する装置を入力装置と呼び、また、その入力データを処理するブロックを入力処理部と呼び、それらの構成は限定しない。
【００３５】
線分抽出部１０５は、入力された２値画像から線分を抽出するブロックであり、角度検出部１０６は、線分や画像の角度を検出するブロックであり、回転処理部１０７は、指定した角度に基づき画像を回転するブロックである。これら、線分抽出部１０５、角度検出部１０６、および回転処理部１０７は、ＣＰＵを用いてプログラムで実装する事も、何らかのハードウェアで実装する事も可能であり、その構成は限定しない。
【００３６】
図４は、本実施形態にかかる画像処理装置のメモリ部（図１の１０２）の構成図である。メモリ部１０２は、入力画像バッファ４０１、２値画像バッファ４０２、線分画像バッファ４０３、エッジ画像バッファ４０４、線分座標バッファ４０５、ランレングスバッファ４０６、候補線分バッファ４０７、高速検索テーブルバッファ４０８で構成される。
【００３７】
このうち、４０１〜４０４の画像バッファは、通常、ヘッダー部とデータ部で構成される画像データを格納するものである。通常、ヘッダー部には、少なくとも横画素数や縦画素数が格納される部分がある。一般的にこのような画像データ形式は多数存在し、ヘッダー部やデータ部の構成も様々であるが、本願ではその構成は限定しない。
【００３８】
図５は、本実施形態にかかる画像処理装置のメモリ部１０２における、線分座標バッファ（図４の４０５）の１つの線分データに対する構成図である。
【００３９】
線分データは線分抽出部（図１の１０５）により複数個抽出される。その線分データ１つに対して、線分方向フラグ５０１、開始Ｘ座標５０２、開始Ｙ座標５０３、終了Ｘ座標５０４、終了Ｙ座標５０５、および線分角度５０６で構成される。線分方向フラグ５０１には、線分の方向を示すフラグ値が格納され、本実施形態では、水平線分の場合には「１」が、垂直線分の場合には「０」が格納される。５０２〜５０５には線分の外接矩形座標が格納される。なお本願では水平方向をＸ、垂直方向をＹと表す。線分角度５０６には、その線分を対象として検出された基準方向（例えば水平方向）との角度が入る。
【００４０】
図６は、本実施形態にかかる画像処理装置のメモリ部（図１の１０２）における、ランレングスバッファ（図４の４０６）の１つのランレングスデータに対する構成図である。
【００４１】
ランレングスデータは線分抽出部（図１の１０５）により複数個抽出される。そのランレングスデータ１つに対して、統合ラベル６０１、ラン方向フラグ６０２、副走査方向座標６０３、主走査方向開始座標６０４、および主走査方向終了座標６０５で構成される。
【００４２】
統合ラベル６０１には、統合されたランレングスデータで同じラベル値が付与される。ラン方向フラグ６０２には、ラン方向を示すフラグ値が格納され、本実施形態では水平ランの場合には「１」が、垂直ランの場合には「０」が格納される。副走査方向座標６０３には、ラン方向を主走査方向とし、これに直交する副走査方向の座標が付与される。水平ランの場合には垂直方向の座標が、垂直ランの場合には水平方向座標が格納される。６０４と６０５には、ラン方向を主走査方向としたランの開始座標と終了座標が、各々格納される。
【００４３】
図７は、本実施形態にかかる画像処理装置のメモリ部（図１の１０２）の候補線分バッファ（図４の４０７）における、１つの候補線分データに対する構成図である。
【００４４】
候補線分データは線分抽出部（図１の１０５）により複数個抽出される。その候補線分データ１つに対して、統合ラベル７０１、線分方向フラグ７０２、開始Ｘ座標７０３、開始Ｙ座標７０４、終了Ｘ座標７０５、終了Ｙ座標７０５、評価値７０７、採用フラグ７０８で構成される。
【００４５】
統合ラベル７０１は、候補線分データ毎にユニークな値が付与される。７０２〜７０６は、図５の５０１〜５０５と同じ意味の情報となる。評価値７０７は、その候補線分データの評価値が格納される。採用フラグ７０８は、その候補線分データが採用されたかどうかを示すフラグであり、採用された場合には「１」が、不採用の場合には「０」が入る。なお、採用された候補線分データの７０２〜７０６が、５０１〜５０５にコピーされる。
【００４６】
図８は、本実施形態にかかる画像処理装置のメモリ部（図１の１０２）における、高速検索テーブルバッファ（図４の４０８）の１つの高速検索テーブルデータに対する構成図である。
【００４７】
副走査方向座標８０１には、ランレングスが存在する副走査方向座標が格納される。開始インデックス８０２には、ランレングスバッファ内で、８０１に格納されている副走査座標を有する始めてのランレングスデータインデックスが、終了インデックス８０３には、ランレングスバッファ内で、８０１に格納されている副走査座標を有する最後のランレングスデータインデックスが、それぞれ格納される。
【００４８】
以上が、本発明にかかるブロック図および各データ構造の説明である。以下では、フローチャートを基に本発明の実施例を説明する。図２は、本発明にかかる画像処理装置の全体フローチャートである。この図を基に本発明の全体処理を説明する。
【００４９】
入力処理部１０３により、入力装置１０４から画像データを入力する。入力した画像データは入力画像バッファ４０１に格納される（Ｓ２０１）。入力処理部１０３により、入力画像バッファ４０１の内容が読み込まれ２値化処理を行う（Ｓ２０２）。なお、２値化処理とは、モノクロデータ（１画素が例えば０〜２５５の値で、多諧調で表現されているデータ）に対して、ある閾値を定め、黒の場合は「１」、白の場合は「０」にする処理である。
【００５０】
一般的な入力画像データは、カラー、モノクロ、２値などそのデータ形式にバリエーションが考えられるが、カラーの場合は一旦モノクロ化して２値化すればよい。また、２値化には、判別分析など各種手法があるが、本発明ではその２値方式は限定しない。
【００５１】
２値画像データが２値画像バッファ４０２に格納される（Ｓ２０３）。線分抽出部１０５により、２値画像バッファ４０２に格納された２値画像データを基に線分抽出を行う。この結果は線分画像バッファ４０３と線分座標バッファ４０５に格納される（Ｓ２０４）。なお線分抽出処理の内容については、改めて詳述する。
【００５２】
角度検出部１０６により、線分画像バッファ４０３と線分座標バッファ４０５に格納された外接矩形座標（５０２〜５０５）を基に、線分毎の角度が検出される。検出された角度は線分角度５０６として格納される（Ｓ２０５）。
【００５３】
なお、線分を対象とした角度の検出方法は、例えば、線分画像を微小角度毎に回転させ、その主走査方向の周辺部分（黒画素のヒスグラム）を求め、その周辺分布の分散が最小となる角度を線分の角度として検出する方式などが考えられるが、本発明ではその方式は限定しない。
【００５４】
角度検出部１０６により、線分毎の線分角度５０６を基に画像全体の角度を決定する（２０６）。この画像角度決定方法は、例えば、特許文献１に記載されている式１の重み付き平均法などが考えられるが、本発明ではその方式は限定しない。
【００５５】
制御部１０１により、角度検出部１０６により決定された画像角度を基に、角度検出処理が収束したかどうかを判定する（Ｓ２０７）。収束した場合Ｓ２０９へ分岐し、収束していない場合はＳ２０８へ分岐する。角度検出処理が収束していない場合、決定された角度を基に２値画像を回転し、新たな２値画像データを作成しＳ２０３に戻る。
【００５６】
角度検出処理が収束した場合、決定された角度を基に入力画像バッファ４０１に格納されている入力画像データを回転し、傾き補正処理を終了する（２０９）。なお、画像の回転方法は、単純なアフィン変換、線形補間、３次補間などが考えられるが、本発明ではその方式は限定しない。以上が、本発明の全体処理の説明である。
【００５７】
図３は、本発明にかかる画像処理装置の線分抽出部のフローチャートであり、図２の全体フローチャートの線分抽出２０４を詳細化したものである。以下ではこの図３をもとに、本発明の特長となる線分抽出処理を説明する。また、図９は、本発明にかかる画像処理装置の線分抽出処理が対象とする、２値化後の入力画像データの一例である。図９を見て分かる通り、この入力画像は半時計方向に傾いている。
【００５８】
線分抽出部１０５により、入力画像図９に対して、エッジ画像抽出（Ｓ３０１）と膨張処理（Ｓ３０２）が行われてエッジ領域群が得られ、この情報がエッジ画像バッファ４０４に格納される。エッジ画像の抽出方法は、例えば、水平・垂直方向に走査し、白画素（本発明では、画素値が０の画素）から黒画素（本発明では、画素値が１の画素）に変化する箇所を求め、その画素をエッジとして黒画素とし、エッジ以外を白画素とする方法が考えられるが、本発明ではその方式は限定しない。
【００５９】
また、膨張処理の方法は、画像中の全画素を順に走査し、注目画素が黒（エッジ画素）の場合、その４近傍や８近傍画素を全て黒画素に変換する方法などが考えられるが、本発明ではその方式は限定しない。なお、図１０は、図９の入力画像に対して、エッジ画像抽出と膨張処理を行った結果の画像である。すなわち膨張処理は、エッジの近傍の画素を抽出し、この抽出した画素にエッジと同じ属性を与えることによって、エッジ領域群を生成する処理ともいえる。
【００６０】
線分抽出部１０５により、エッジ画像バッファ４０４を水平・垂直に走査し、長いランレングスだけを抽出し、結果がランレングスバッファ４０６に格納される（Ｓ３０３）。なおランレングスとは、主走査方向に連続する画素の集合体である。
【００６１】
１つのランレングス毎に図６で示されるデータが作成され、ランレングスバッファ４０６に格納される。また、長いランレングスとは、例えば、画像のサイズに応じて設定される閾値を用いる方法が考えられる。本願では特にその方式は限定しないが、本発明では、画像の縦もしくは横サイズを３０で割った値を閾値として、それよりも長いランレングスだけを抽出するものとする。
【００６２】
図１１は、図１０の画像に対して、水平・垂直の長いランレングスだけを抽出した結果を図示した図である。この段階で、抽出された１つのランレングスデータ毎に、図６で示すランレングスバッファ４０６のデータは下表１の通り設定される。
【００６３】
【表１】
2007295210.tif 000003
【００６４】
また、この段階でのランレングスとランレングスバッファ４０６の関係を、より具体的に図１４に示す。図１４の１４０１は画像を示す。なお原点は左上とする。水平方向には、ｘ０、ｘｓ、ｘｅの3つの座標があり、垂直方向には、ｙｓ、ｙｅ、ｙ０がある。１４０２は垂直方向のランレングスであり、１４０３は水平方向のランレングスを示す。
【００６５】
１４０２の垂直ランレングスの場合、その副走査方向座標はｘ０であり、その主走査（ラン）方向の開始座標はｙｓ、終了座標はｙｅとなっている。１０４３の水平ランレングスの場合、その副走査方向座標はｙ０であり、その主走査（ラン）方向の開始座標はｘｓ、終了座標はｘｅとなっている。この場合のランレングスバッファ４０６は、図１４の下表に示す内容となっている。
【００６６】
次に、線分抽出部１０５により、水平ランと垂直ランを分けて順に走査し、隣り合うラン（水平ランの場合は上下に存在するラン、垂直ランの場合は左右に存在するラン）で、連結関係が存在するものに同じ統合ラベルを付与する方式で、ラン同士を統合する（Ｓ３０４）。なお、連結関係を調べる際には、以下の条件を満足する場合に連結しないと判断する。
【００６７】
条件１：
（注目ランの主走査方向開始座標）−１≧（統合候補ランの主走査方向終了座標）
条件２：
（注目ランの主走査方向終了座標）＋１≦（統合候補ランの主走査方向開始座標）
【００６８】
上記判断により、ランレングス同士が、主走査方向または副走査方向において互いに接している場合（一角を共有する場合も含む）には、連結関係を有するものとされ、そうでない場合には、連結関係を有さないものとされる。なお、連結関係の判断に係る条件は、適切な線分を抽出する目的に沿うものであれば、他の内容であっても構わない。
【００６９】
条件１と条件２とも満足しない統合候補ランに、注目ランと同じ統合ラベルを付与する。この判断を、一切の新たな統合が発生しなくなるまで繰り返し、ランの統合を行う。統合処理の結果、連結関係が存在すると判断れたランには、ランレングスバッファ４０６の、統合ラベル６０１に、同じ統合ラベル値（１から始まる自然数）が付与される。
【００７０】
次に、線分抽出部１０５により、統合が完了したランレングスバッファ４０６を走査し、同じ統合ラベルが付与されているランレングスを対象に候補線分バッファ４０７が作成される（Ｓ３０４）。この段階で、抽出された１つの候補線分データ毎に、図７で示す候補線分バッファ４０７のデータは下表２の通り設定される。
【００７１】
【表２】
2007295210.tif 000004
【００７２】
次に、線分抽出部１０５により、候補線分バッファ４０７を走査し、次式１に基づき評価値を計算する（Ｓ３０５）。
【００７３】
式１：（評価値）＝（主走査方向の長さ）2÷（副走査方向の長さ）
【００７４】
この式１は、細長い線分程大きくなる評価値である。線分毎の評価値は対応する候補線分バッファ４０７の評価値７０７に格納される。次に、この評価値７０７を走査し、大きいものから順にある数（本発明では１０）だけを採用線分として抽出する。採用と決定したものは、対応する候補線分バッファ４０７の採用フラグ７０８に採用を示す「１」が格納される。
【００７５】
次に、線分抽出部１０５により、候補線分バッファ４０７を走査し、採用フラグ７０８が「１」になっている採用線分だけの線分画像が作成され、線分画像バッファ４０３に格納される（Ｓ３０６）。図１２は、図１１のランレングス抽出結果に基づき、線分統合、採用線分が決定された結果、線分画像バッファ４０３に格納された画像の図である。
【００７６】
次に、線分抽出部１０５により、候補線分バッファ４０７を走査し、採用フラグ７０８が「１」になっている採用線分だけを対象として、その情報を線分座標バッファ４０５にコピーする（Ｓ３０７）。この場合、線分方向フラグ７０２が５０１に、開始Ｘ座標７０３が５０２に、開始Ｙ座標７０４が５０３に、終了Ｘ座標７０５が５０４に、終了Ｙ座標７０６が５０５にそれぞれコピーされる。
【００７７】
以上が、本発明にかかる画像処理装置の線分抽出処理である。上述の通り、従来技術では１画素単位にエッジ画素を連結していたが、本発明では、ランレングスという複数の画素を統合した単位処理できるため、高速化が実現できる。また、ランレングスの抽出はハード化が容易であり、その場合、さらなる高速化も期待できる。
【００７８】
しかしながら、図３のフローチャートの線分抽出３０４では、注目ランレングスに対して連結関係の存在するランレングスを、ランレングスバッファ４０６内を全て走査して探すことになり、この部分に冗長な処理が含まれる。結局は、隣り合うラン（水平ランの場合は上下に存在するラン。垂直ランの場合は左右に存在するラン）に対して、条件１、条件２で連結関係を判断するため、注目ランレングスの副走査方向座標に対して、±１の副走査方向座標を有するランレングスだけを対象にすればよく、全走査することが冗長である。この問題を解決し、さらに高速化を図る手段を本発明は提供する。
【００７９】
図１５は、本発明にかかる線分抽出部１０５の線分抽出（水平・垂直ラン統合）３０４を詳細化したフローチャートである。また、図１６は、ランレングスとランレングスバッファ４０６の関連図である。まず、図１６を基に高速化の原理を説明する。
【００８０】
図１６は便宜上水平方向のランレングスだけを図示しているが原理は垂直方向のランレングスでも同様である。そのため、以降の説明では、水平・垂直を区別せず、ラン方向を主走査方向と、ラン方向に直行する方向を副走査方向と呼ぶ。
【００８１】
図１６の１６０１は画像を示し、１６０２はランレングスバッファを示す。ランレングスは副走査方向に１座標毎にずらし、１つの副走査方向座標に対して主走査方向にランを抽出する。そのため、ランレングスは大局的に見れば副走査方向の順に並んでいる。ただし、１つの副走査方向座標に対してランレングスが存在しない場合も、また、複数存在する場合もある。この関係を図１６では示しており、画像１６０１内のランレングスを着色矩形（注目ランレングスについては斜線矩形）で示し、それに対応するランレングスバッファ４０６内の格納場所を破線矢印で示している。
【００８２】
注目ランレングスに対して、全ランレングスバッファ要素である１６０２の全てを評価対象とする必要はなく、注目ランレングスの副走査方向座標に対して、±１の副走査方向座標を有するもの（副走査方向に隣り合うもの）だけを対象とすればよいことが分かる。具体的には、図１６ではこの範囲は、１６０３から１６０４の間だけとなる。
【００８３】
すなわち、ランレングス群における各ランレングスのうち、副走査方向に隣り合うものを分類する処理を、ランレングス群における各ランレングスについて行っておく。そしてこの分類結果に係る情報（ランレングスの副走査方向の座標に基づく参照範囲情報）を用いて、ランレングス同士の連結関係の有無の調査を行うこととする。本発明の線分抽出（水平・垂直ランレングスの統合）の高速化手法はこの内容に着目しており、以下、図１５を用いて説明する。
【００８４】
まず、高速検索テーブル４０８を作成する（Ｓ１５０１）。この高速検索テーブル４０８は１つのデータが図８で示されるデータであり、ランレングスバッファ４０６の全要素を走査し、同じラン方向フラグと同じ副走査方向座標を持つ２つ以上のランレングスに対して、ランレングスバッファ４０６内のインデックス番号の小さいものを開始インデックス８０２に、ランレングスバッファ４０６内のインデックス番号の大きいものを終了インデックス８０３に、順次格納することで作成する。
【００８５】
もし、ある副走査方向座標に対して、１つもランレングスが存在しない場合は、図８のデータは作成されず、また、１つだけランレングスが存在する場合は、開始インデックス８０２と終了インデックス８０３の値は、同じ値となる。（その１つのランレングスを示すランレングスバッファ４０６内のインデックス番号となる。）
【００８６】
次に、各種変数を０クリアする（Ｓ１５０２）。この変数はメモリ上の変数でもレジスタでも、ハードウェアのカウンターでもなんでも良い。本発明では「統合ラベル」と「統合フラグ」と「現統合ラベル」３変数を使用する。
【００８７】
次に、注目ランレングスを設定する（Ｓ１５０３）。これは、ランレングスバッファ４０６内のインデックス番号を１つずつインクリメントして、現在統合対象となるラン方向フラグ６０２を有しているものを探し、注目ランレングスに設定する。
【００８８】
注目ランレングスに既に統合ラベルが付与されている場合（統合ラベルが未統合を示す「−１」でない場合）、その値を「現統合ラベル」変数に設定する。「−１」の場合「統合ラベル」変数の値を「現統合ラベル」変数に設定し、「統合ラベル」変数の値をインクリメントする。また、注目ランレングスの統合ラベル６０１には、統合ラベルの値を設定する。
【００８９】
次に、走査開始/終了インデックスを取得する（Ｓ１５０４）。開始インデックスは、高速検索テーブル４０８を走査し、その副走査方向座標８０１が、注目ランレングスの副走査方向座標６０３の「−１」の座標値となるものの開始インデックス８０２とし、終了インデックスは、高速検索テーブル４０８を走査し、その副走査方向座標８０１が、注目ランレングスの副走査方向座標６０３の「＋１」の座標値となるものの終了インデックス８０２とすることで取得できる。
【００９０】
図１６で言えば、斜線矩形を注目ランレングスとした場合、開始インデックスが１６０３として、終了インデックスが１６０４として取得される。なお、開始インデックスが設定できない場合は、「（注目ランレングスの副走査方向座標）−１」に統合すべきランレングスが無いため、開始インデックスを「（注目ランレングスのインデックス番号）＋１」と設定し、終了インデックスが設定できない場合は、同様の理由で終了インデックスを「（注目ランレングスのインデックス番号）−１」と設定する。
【００９１】
次に、開始インデックスから終了インデックスで示されるランレングスバッファ４０６内の各ランレングスデータを順に走査し、注目ランレングスに対して、条件１、条件２で統合可能か判断し、統合できる場合は、そのランレングスの統合ラベル６０１に「現統合ラベル」変数の値を設定し、「統合フラグ」変数の値をインクリメントする（Ｓ１５０５）。
【００９２】
注目ランレングスが終了かどうか判断し、まだ、存在する場合はＳ１５０３へ分岐する。もうない場合はＳ１５０７へ分岐する（Ｓ１５０６）。「統合フラグ変数」が「０」であるかどうかを判断し、「０」でない場合はＳ１５０２へ分岐する。「０」の場合は統合処理が完了したとして終了する（Ｓ１５０７）。
【００９３】
以上のように、本発明にかかる画像処理装置は、傾き補正を高速に処理する手段を提供する。なお本発明にかかる画像処理装置が、図９の入力画像に対して傾きを補正した結果の画像を、図１３に示す。特に、高速処理が要求される複写機などの場合、本発明にかかる画像処理装置は有効に活用される。
【００９４】
さらに、上述した構成の画像処理装置を動作させる画像処理プログラムを提供することもできる。このようなプログラムであれば、適切なハードウェアを備えているコンピュータに、上述した利点を享受し得る画像処理を行わせることが可能となる。
【００９５】
またこのようなプログラムは、コンピュータに付属するフレキシブルディスク、ＣＤ−ＲＯＭ［Compact Disc _Read Only Memory］、ＲＯＭ［Read Only Memory］、ＲＡＭ［Random Access Memory］およびメモリカードなどのコンピュータ読み取り可能な記録媒体にて記録させて、プログラムを提供することもできる。また、ネットワークを介したダウンロードによって、プログラムを提供することもできる。
【００９６】
提供されるプログラム製品は、ハードディスクなどのプログラム格納部にインストールされて実行される。なお、プログラム製品は、プログラム自体とプログラムが記録された記録媒体とを含む。今回開示された実施の形態はすべての点で例示であって制限的なものではないと考えられるべきである。本発明の範囲は上記した説明ではなくて特許請求の範囲によって示され、特許請求の範囲と均等の意味および範囲内でのすべての変更が含まれることが意図される。
【産業上の利用可能性】
【００９７】
本発明の画像処理装置、画像処理方法、画像処理プログラム、記録媒体は、高速処理が要求される複写機などに適用可能である。
【図面の簡単な説明】
【００９８】
【図１】本発明にかかる画像処理装置のハードウェア構成を示すブロック図である。
【図２】本発明にかかる画像処理装置の全体フローチャートである。
【図３】本発明にかかる画像処理装置の線分抽出部のフローチャートである。
【図４】本発明にかかる画像処理装置のメモリ部（図１の１０２）の構成図である。
【図５】本発明にかかる画像処理装置のメモリ部（図１の１０２）の線分座標バッフ  ァ（図４の４０５）の、１つの線分データに対する構成図である。
【図６】本発明にかかる画像処理装置のメモリ部（図１の１０２）のランレングスバ  ッファ（図４の４０６）の、１つのランレングスデータに対する構成図である。
【図７】本発明にかかる画像処理装置のメモリ部（図１の１０２）の候補線分バッフ  ァ（図４の４０７）の、１つの候補線分データに対する構成図である。
【図８】本発明にかかる画像処理装置のメモリ部（図１の１０２）の高速検索テーブ  ルバッファ（図４の４０８）の、１つの高速検索テーブルデータに対する構成図である  。
【図９】本発明にかかる画像処理装置の線分抽出処理が対象とする、２値化後の入力  画像データの一例である。
【図１０】本発明にかかる画像処理装置が、図９の入力画像に対してエッジ画像抽出  と膨張処理を行った結果の画像である。
【図１１】本発明にかかる画像処理装置が、図１０の画像に対して水平・垂直の長い  ランレングスだけを抽出した結果を図示した図である。
【図１２】図１１のランレングス抽出結果に基づき、線分統合、採用線分が決定され  た結果、線分画像バッファ４０３に格納された画像の図である。
【図１３】本発明にかかる画像処理装置が、図９の入力画像に対して傾きを補正した  結果の画像である。
【図１４】水平・垂直ランレングスとランレングスバッファ４０６の関係を示した図  である。
【図１５】本発明にかかる線分抽出部１０５の線分抽出（水平・垂直ラン統合）３０  ４を詳細化したフローチャートである。
【図１６】ランレングスとランレングスバッファ４０６の関連図である。
【符号の説明】
【００９９】
１０１    制御部
１０２    メモリ部
１０３    入力処理部
１０４    入力装置
１０５    線分抽出部
１０６    角度検出部
１０７    回転処理部
１０８    バス
４０１    入力画像バッファ
４０２    ２値画像バッファ
４０３    線分画像バッファ
４０４    エッジ画像バッファ
４０５    線分座標バッファ
４０６    ランレングスバッファ
４０７    候補線分バッファ
４０８    高速検索テーブルバッファ
１４０１    画像
１４０２    垂直方向のランレングス
１４０３    水平方向のランレングス
１６０１    画像
１６０２    ランレングスバッファ
【図１】
2007295210.tif 000005
【図２】
2007295210.tif 000006
【図３】
2007295210.tif 000007
【図４】
2007295210.tif 000008
【図５】
2007295210.tif 000009
【図６】
2007295210.tif 000010
【図７】
2007295210.tif 000011
【図８】
2007295210.tif 000012
【図９】
2007295210.tif 000013
【図１０】
2007295210.tif 000014
【図１１】
2007295210.tif 000015
【図１２】
2007295210.tif 000016
【図１３】
2007295210.tif 000017
【図１４】
2007295210.tif 000018
【図１５】
2007295210.tif 000019
【図１６】
2007295210.tif 000020