(57)【特許請求の範囲】
【請求項１】
入力画像から第１の輪郭画素の系列を、前記入力画像から検出された枠に関係する輪郭線毎に抽出する輪郭線抽出手段と、
前記抽出された第１の輪郭画素の系列毎に、当該第１の輪郭画素の系列の凸包を構成する第２の輪郭画素の系列を抽出する凸包抽出手段と、
前記抽出された第２の輪郭画素の系列を、前記入力画像から検出された枠に囲まれた領域の情報として取得する領域取得手段と
を具備する領域検出装置。
【請求項２】
マスク画像生成手段及び抽出画像生成手段を更に具備し、
前記凸包抽出手段は、前記輪郭線抽出手段によって抽出された前記第１の輪郭画素の系列毎に、当該第１の輪郭画素の系列の凸包の頂点に位置する輪郭画素が当該凸包の外輪上での順に並んだ系列を前記第２の輪郭画素の系列として抽出し、
前記マスク画像生成手段は、前記枠に囲まれた領域内の画素値が１で当該領域外の画素値が０のマスク画像を生成し、
前記抽出画像生成手段は、前記マスク画像上の画素値が１の座標における画素の画素値が前記入力画像の画素値と一致し、残りの画素の画素値が白を示す抽出画像を生成する
請求項１記載の領域検出装置。
【請求項３】
前記輪郭線抽出手段は、
前記入力画像内の隣接する画素間からエッジを検出するエッジ検出手段と、
前記エッジで区切られた画素の塊の輪郭線を追跡することにより前記輪郭線を構成する前記第１の輪郭画素の系列を前記輪郭線毎に抽出する輪郭線追跡手段と
を含む請求項１記載の領域検出装置。
【請求項４】
輪郭線抽出手段と、凸包抽出手段と、領域取得手段とを具備する領域検出装置において、入力画像から枠で囲まれた領域を検出する領域検出方法であって、
前記輪郭線抽出手段が、前記入力画像から第１の輪郭画素の系列を、前記入力画像から検出された枠に関係する輪郭線毎に抽出するステップと、
前記凸包抽出手段が、前記抽出された第１の輪郭画素の系列毎に、当該第１の輪郭画素の系列の凸包を構成する第２の輪郭画素の系列を抽出する凸包抽出ステップと、
前記領域取得手段が、前記抽出された第２の輪郭画素の系列を、前記入力画像から検出された枠に囲まれた領域の情報として取得するステップと
を具備する領域検出方法。
【請求項５】
前記凸包抽出ステップは、前記凸包抽出手段が、前記輪郭線抽出手段によって抽出された前記第１の輪郭画素の系列毎に、当該第１の輪郭画素の系列の凸包の頂点に位置する輪郭画素が当該凸包の外輪上での順に並んだ系列を前記第２の輪郭画素の系列として抽出するステップであり、
前記領域検出装置は、マスク画像生成手段及び抽出画像生成手段を更に具備し、
前記マスク画像生成手段が、前記枠に囲まれた領域内の画素値が１で当該領域外の画素値が０のマスク画像を生成するステップと、
前記抽出画像生成手段が、前記マスク画像上の画素値が１の座標における画素の画素値が前記入力画像の画素値と一致し、残りの画素の画素値が白を示す抽出画像を生成するステップと、
を更に具備する請求項４記載の領域検出方法。
【請求項６】
コンピュータを、
入力画像から第１の輪郭画素の系列を、前記入力画像から検出された枠に関係する輪郭線毎に抽出する輪郭線抽出手段と、
前記抽出された第１の輪郭画素の系列毎に、当該第１の輪郭画素の系列の凸包を構成する第２の輪郭画素の系列を抽出する凸包抽出手段と、
前記抽出された第２の輪郭画素の系列を、前記入力画像から検出された枠に囲まれた領域の情報として取得する領域取得手段と
して機能させるためのプログラム。
【請求項７】
前記コンピュータを、マスク画像生成手段及び抽出画像生成手段として更に機能させ、
前記凸包抽出手段は、前記輪郭線抽出手段によって抽出された前記第１の輪郭画素の系列毎に、当該第１の輪郭画素の系列の凸包の頂点に位置する輪郭画素が当該凸包の外輪上での順に並んだ系列を前記第２の輪郭画素の系列として抽出する手段であり、
前記マスク画像生成手段は、前記枠に囲まれた領域内の画素値が１で当該領域外の画素値が０のマスク画像を生成する手段であり、
前記抽出画像生成手段は、前記マスク画像上の画素値が１の座標における画素の画素値が前記入力画像の画素値と一致し、残りの画素の画素値が白を示す抽出画像を生成する手段である
請求項６記載のプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の実施形態は、画像から枠で囲まれた領域を検出する領域検出装置、領域検出方法及びプログラムに関する。
【背景技術】
【０００２】
画像から枠で囲まれた領域を検出する技術として、道路標識から赤枠を検出し、その中の標示を識別する技術（第１の技術）が従来から知られている。
【０００３】
また、帳票上の黒罫線に囲まれた白画素の連結領域を検出することにより、文字の抽出や認識を行う技術（第２の技術）も従来から知られている。
【先行技術文献】
【特許文献】
【０００４】
【特許文献１】特公平６−１０８３８号公報
【特許文献２】特開平６−１１９４９１号公報
【特許文献３】特開平６−６０２２０号公報
【発明の概要】
【発明が解決しようとする課題】
【０００５】
上述したような、道路標識から特定の色の枠を検出する第１の技術は、カラー画像を必要とする。このため、画像を取得する手段が例えばモノクロカメラである場合、色情報を利用できないことから、枠検出（領域検出）に第１の技術を適用することは難しい。
【０００６】
また、上第１及び第２の技術では、検出すべき領域を取り囲む枠の外側と内側を区別する必要がある。しかし、枠と枠内の文字等が接触している場合、前記区別の基準が不明確となる場合がある。
【０００７】
本発明が解決しようとする課題は、枠と枠内の文字等が接触している場合における枠の内側と外側の区別をより確実にし、枠に囲まれた領域の検出性能を向上できる領域検出装置、領域検出方法及びプログラムを提供することにある。
【課題を解決するための手段】
【０００８】
実施形態によれば、領域検出装置は、凸包抽出手段と、領域取得手段とを具備する。前記輪郭線抽出手段は、入力画像から第１の輪郭画素の系列を輪郭線毎に抽出する。前記凸包抽出手段は、前記抽出された第１の輪郭画素の系列毎に、当該第１の輪郭画素の系列の凸包を構成する第２の輪郭画素の系列を抽出する。前記領域取得手段は、前記抽出された第２の輪郭画素の系列を、前記入力画像から検出された領域の情報として取得する。
【図面の簡単な説明】
【０００９】
【図１】第１の実施形態に係る領域検出装置のハードウェア構成を示すブロック図。
【図２】第１の実施形態に係る領域検出装置の機能構成を示すブロック図。
【図３】第１の実施形態で適用される入力画像の例を示す図。
【図４】図３に示す入力画像内で隣接する２つの画素の対の群のうち、当該２つの画素間にエッジが検出されなかった画素同士を線分で結んだ様子を示す図。
【図５】第１の実施形態において輪郭線追跡手段によって実行される輪郭線抽出処理の手順を示すフローチャートの一部を示す図。
【図６】第１の実施形態において輪郭線追跡手段によって実行される輪郭線抽出処理の手順を示すフローチャートの残りを示す図。
【図７】第１の実施形態で適用される、輪郭線の群に関する情報のデータ構造の例を示す図。
【図８】図３に示した入力画像から輪郭線追跡手段によって抽出された輪郭画素の系列全てをまとめて示す図。
【図９】図８に示した輪郭画素の系列の群のうちの一部の輪郭画素の系列を個別に示す図。
【図１０】図８に示した輪郭画素の系列の群のうちの残りの輪郭画素の系列を個別に示す図。
【図１１】図９及び図１０に示した輪郭画素の系列の群から、予め定められた条件の下で選択手段により抽出された輪郭画素の系列の集合の例を示す図。
【図１２】第１の実施形態に係る領域検出装置に付加されている文字認識機構の機能構成を示すブロック図。
【図１３】図３に示した入力画像を２値化することによって生成される２値画像の例を示す図。
【図１４】図３に示した入力画像から最終的に抽出される輪郭画素の系列が図１１に示した輪郭画素の系列の集合である場合に、画像抽出手段により生成されるマスク画像及び抽出画像の例を示す図。
【図１５】第２の実施形態に係る領域検出装置の機能構成を示すブロック図。
【図１６】第２の実施形態で適用される入力画像の例を示す図。
【図１７】図１６に示した入力画像から輪郭線追跡手段によって抽出された輪郭画素の系列全てをまとめて示す図。
【図１８】図１７に示した輪郭画素の系列の群のうちの一部の輪郭画素の系列を個別に示す図。
【図１９】図１７に示した輪郭画素の系列の群のうちの残りの輪郭画素の系列を個別に示す図。
【図２０】図１７に示した輪郭画素の系列の群のうちの１つの系列から凸包抽出手段によって抽出された凸包を構成する輪郭画素の系列の例を示す図。
【図２１】図１６に示した入力画像の場合に、画像抽出手段によって生成されるマスク画像及び抽出画像の例を示す図。
【図２２】図１６に示した入力画像の場合に、第２の実施形態との比較のために、第１の実施形態において画像抽出手段によって生成されるマスク画像及び抽出画像の例を示す図。
【図２３】第３の実施形態に係る領域検出装置の機能構成を示すブロック図。
【図２４】第３の実施形態で適用される入力画像の例を示す図。
【図２５】図２４に示す入力画像内で隣接する２つの画素の対の群のうち、当該２つの画素間にエッジが検出されなかった画素同士を線分で結んだ様子を示す図。
【図２６】図２４に示した入力画像から輪郭線追跡手段によって抽出された輪郭画素の系列全てをまとめて示す図。
【図２７】図２４に示した輪郭画素の系列の群のうちの一部の輪郭画素の系列を個別に示す図。
【図２８】図２４に示した輪郭画素の系列の群のうちの残りの輪郭画素の系列を個別に示す図。
【図２９】明暗判定手段による明暗判定の対象となる画素と近傍の画素との位置関係の例を示す図。
【図３０】第３の実施形態において明暗判定手段によって実行される明暗判定処理の手順を示すフローチャート。
【図３１】明暗判定手段によって取得される、抽出された輪郭画素の系列の各画素が近傍の画素と比較して明るいか暗いかの判定結果を示す配列を含む、記憶装置に格納される輪郭線の群に関する情報のデータ構造の例を示す図。
【図３２】第３の実施形態において変化点検出手段によって実行される変化点検出処理の手順を示すフローチャート。
【図３３】変化点検出手段によって取得される、各輪郭線上の変化点の個数を表す配列及び当該変化点の輪郭画素の番号を表す配列を含む、記憶装置に格納される輪郭線の群に関する情報のデータ構造の例を示す図。
【図３４】輪郭線の断片を構成する輪郭画素の系列を含む、記憶装置１２に格納される輪郭線の群に関する情報のデータ構造の例を示す図。
【図３５】輪郭線切断手段によって実行される輪郭線切断処理の手順のフローチャートの一部を示す図。
【図３６】輪郭線切断手段によって実行される輪郭線切断処理の手順のフローチャートの他の一部を示す図。
【図３７】輪郭線切断手段によって実行される輪郭線切断処理の手順のフローチャートの残りを示す図。
【図３８】図２６に示した輪郭線が輪郭線切断手段によって切断された断片の輪郭画素の系列を含む全ての輪郭画素の系列をまとめて示す図。
【図３９】図３８に示した輪郭画素の系列の群のうちの一部の輪郭画素の系列を個別に示す図。
【図４０】図３８に示した輪郭画素の系列の群のうちの残りの輪郭画素の系列を個別に示す図。
【図４１】輪郭線再接続手段によって実行される接続断片決定処理の手順を示すフローチャートの一部を示す図。
【図４２】輪郭線再接続手段によって実行される接続断片決定処理の手順を示すフローチャートの残りを示す図。
【図４３】図３８に示した輪郭画素の系列の群に含まれている切断された断片の輪郭画素の系列の再接続後の全ての輪郭画素の系列をまとめて示す図。
【図４４】図４３に示した輪郭画素の系列の群のうちの一部の輪郭画素の系列を個別に示す図。
【図４５】図４３に示した輪郭画素の系列の群のうちの残りの輪郭画素の系列を個別に示す図。
【図４６】第４の実施形態に係る領域検出装置の機能構成を示すブロック図。
【発明を実施するための形態】
【００１０】
以下、実施の形態につき図面を参照して説明する。  
［第１の実施形態］
図１は第１の実施形態に係る領域検出装置のハードウェア構成を示すブロック図である。図１に示す領域検出装置は、コンピュータ（以下、ＰＣと称する）１０を用いて実現されるものとする。ＰＣ１０は、ＣＰＵ１１と、記憶装置１２と、入出力制御部１３とを備えている。ＣＰＵ１１、記憶装置１２及び入出力制御部１３は、バス１４によって相互接続されている。
【００１１】
記憶装置１２は、領域検出ソフトウェア１２１及び文字認識ソフトウェア１２２のようなソフトウェア群、入力画像、及び作業データ等を格納するのに用いられる。ＣＰＵ１１は、記憶装置１２から領域検出ソフトウェア１２１を読み取って実行することにより、入力画像から枠に囲まれた領域を検出する領域検出処理を行う。領域検出処理は、領域検出結果を記憶装置１２または外部デバイスに出力する処理を含む。ＣＰＵ１１はまた、記憶装置１２から文字認識ソフトウェア１２２を読み取って実行することにより、領域検出処理で検出された領域内の文字を認識する文字認識処理を行う。文字認識処理は、文字認識結果を記憶装置１２または外部デバイスに出力する処理を含む。
【００１２】
入出力制御部１３は、画像を撮像する画像取得手段としてのカメラ２１と接続されている。入出力制御部１３はまた、シリアルインタフェース２２と接続されている。入出力制御部１３は、カメラ２１からの画像の入力、及び外部デバイス（カメラ２１以外の外部デバイス）へのシリアルインタフェース２２を介してのシリアル出力を制御（つまり、外部の装置との間の入出力を制御）する。入出力制御部１３はまた、カメラ２１から入力した画像を、例えばダイレクトメモリアクセス（ＤＭＡ）により記憶装置１２へ転送する。入出力制御部１３は更に、ＣＰＵ１１による領域検出ソフトウェア１２１或いは文字認識ソフトウェア１２２の実行の結果（つまり、領域検出結果或いは文字認識結果）等を、シリアルインタフェース２２を介して外部デバイスにシリアル出力する、或いはバス１４を介して記憶装置１２に出力する。
【００１３】
図２は第１の実施形態に係る領域検出装置の機能構成を示すブロック図である。図２に示す領域検出装置の機能構成は、ＣＰＵ１１が領域検出ソフトウェア１２１を読み取って実行することによって実現される。
【００１４】
図２に示す領域検出装置は、輪郭線抽出手段２１０、選択手段２２０及び領域出力手段２３０を備えている。  
輪郭線抽出手段２１０は、カメラ２１から入力された画像（つまり、入力画像）から輪郭線毎に輪郭画素の系列を検出することにより、当該輪郭画素の系列の集合Ｓ１を抽出する。
【００１５】
選択手段２２０は、輪郭画素の系列の集合Ｓ１から１つまたは複数の輪郭画素の系列を選択することにより、当該選択した輪郭画素の系列の集合Ｓ４（つまり、集合Ｓ１の部分集合Ｓ４）を抽出する。  
領域出力手段２３０は、選択（抽出）された画素の系列の集合Ｓ４を、領域検出の結果として外部デバイスまたは記憶装置１２に出力する。
【００１６】
次に。図２に示す領域検出装置の動作について説明する。以下の説明では１次元の配列αの第ｉ番目の要素をα（ｉ）、２次元の配列βの横方向にｊ番目、縦方向にｉ番目の要素をβ（ｉ，ｊ）と表す。但し、記号αは任意の１次元配列変数、βは任意の２次元配列変数の、それぞれ変数名を表すものとする。また、以下では入力画像が原則モノクログレースケール画像（いわゆるものモノクロ画像）であるものとして説明する。
【００１７】
図３は入力画像の例を示す図である。図３に示す入力画像は、丸枠の中に文字列「１０」を含む。入力画像は横幅ｗ画素、高さｈ画素の画素値の配列であり、記憶装置１２に格納される。また、以下の説明では、入力画像の座標（ｘ，ｙ）の画素を画素（ｘ，ｙ）と表記する。画素（ｘ，ｙ）の画素値は２次元配列ｆ、つまりｆ（ｘ，ｙ）として読み書きできるものとする。但し、ｘは図３における矢印３１の方向（右方向）を正、ｙは図３における矢印３２の方向（下方向）を正とする。
【００１８】
輪郭線抽出手段２１０は、図３に示す入力画像から、輪郭線毎に輪郭画素の系列を検出することにより、当該輪郭画素の系列の集合Ｓ１を抽出する。この集合Ｓ１の抽出のために、輪郭線抽出手段２１０は、エッジ検出手段２１１及び輪郭線追跡手段２１２を備えている。
【００１９】
エッジ検出手段２１１は、入力画像内の隣接する画素間からエッジを検出する。より詳細には、エッジ検出手段２１１は、隣接する画素間の画素値の差に基づいてエッジを検出する。ここではエッジ検出手段２１１は、隣接する画素間の画素値の差の絶対値がしきい値Ｔｅ以上の場合にエッジを検出し、Ｔｅ未満の場合にエッジを検出しない。
【００２０】
輪郭線追跡手段２１２は、検出されたエッジで区切られた画素の塊毎に、当該画素の塊の輪郭線を追跡する。輪郭線追跡手段２１２は、輪郭線追跡により検出された輪郭線を構成する輪郭画素の系列を、上記画素の塊に対応する輪郭線毎に抽出する。
【００２１】
以下、エッジ検出手段２１１によるエッジ検出の詳細について説明する。ここで、横方向（ｘ方向）のエッジの有無を表す変数をｈ（ｘ，ｙ）と表記し、縦方向（ｙ方向）のエッジの有無を表す変数をｖ（ｘ，ｙ）と表記する。
【００２２】
エッジ検出手段２１１は、入力画像から、後述する方法で、変数ｈ（ｘ，ｙ）及び縦方向のエッジの有無を表す変数ｖ（ｘ，ｙ）を−１≦ｙ≦ｈ−１且つ１≦ｘ≦ｗ−１で規定される範囲の座標（ｘ，ｙ）全てについて算出する。
【００２３】
変数ｈ（ｘ，ｙ）は、入力画像の座標（ｘ，ｙ）の画素（ｘ，ｙ）と縦方向に隣接する画素（ｘ，ｙ＋１）とを結ぶ線分を横切る横エッジが検出されたか否かを表す。  
ｈ（ｘ，ｙ）には、横エッジが検出された場合は０、当該横エッジが検出されなかった場合は１が代入される。したがってｈ（ｘ，ｙ）は、
｜ｆ（ｘ，ｙ）−ｆ（ｘ，ｙ＋１）｜≧Ｔｅ
ならば０、
｜ｆ（ｘ，ｙ）−ｆ（ｘ，ｙ＋１）｜＜Ｔｅ
ならば１となる。
【００２４】
変数ｖ（ｘ，ｙ）は、入力画像の座標（ｘ，ｙ）の画素（ｘ，ｙ）と横方向に隣接する画素（ｘ＋１，ｙ）とを結ぶ線分を横切る縦エッジが検出されたか否かを表す。  
ｖ（ｘ，ｙ）には、縦エッジが検出された場合は０、当該縦エッジが検出されなかった場合は１が代入される。したがってｈ（ｘ，ｙ）は、
｜ｆ（ｘ，ｙ）−ｆ（ｘ＋１，ｙ）｜≧Ｔｅ
ならば０、
｜ｆ（ｘ，ｙ）−ｆ（ｘ＋１，ｙ）｜＜Ｔｅ
ならば１となる。
【００２５】
但しエッジ検出手段２１１は、入力画像の外側の画素、即ちｘ＜０またはｘ≧ｗまたはｙ＜０またはｙ≧ｈの画素については、画素値ｆ（ｘ，ｙ）が予め定められた値Ｃであるものとみなして、ｈ（ｘ，ｙ）及びｖ（ｘ，ｙ）を算出する。
【００２６】
図４は、図３に示す入力画像内で隣接する２つの画素の対の群のうち、エッジ検出手段２１１によって当該２つの画素間にエッジが検出されなかった画素同士を線分で結んだ様子を示す図である。
【００２７】
輪郭線追跡手段２１２は、検出されたエッジ（横方向のエッジまたは縦方向のエッジ）で区切られた画素の塊の輪郭線を追跡することにより、輪郭線毎に当該輪郭線を構成する輪郭画素の系列を検出する。輪郭線追跡手段２１２は、この輪郭線毎の輪郭画素の系列を検出することにより、検出された輪郭線の集合を表す、輪郭画素の系列の集合Ｓ１を抽出する。
【００２８】
以下、輪郭線追跡手段２１２による輪郭線検出の詳細について説明する。  
輪郭線追跡手段２１２は、輪郭線検出のために以下の変数群
（ａ１）入力画像と同様の、横幅ｗ画素、高さｈ画素の整数の配列ｇ
（ａ２）輪郭線の追跡開始画素（つまり追跡開始点）の座標を表す整数変数ｘ０，ｙ０
（ａ３）現在追跡中の画素（輪郭点）の座標を表す整数変数ｘ，ｙ
（ａ４）上下左右の方向を、値０で右方向、値１で上方向、値２で左方向、値３で下方向を表す整数変数ｄ０，ｄ１，ｄ２
（ａ５）追跡中の輪郭線の番号（且つ追跡が完了した輪郭線の個数）を表す整数変数Ｎ１
（ａ５）抽出（列挙）された輪郭画素の個数（輪郭画素数）を表す整数変数Ｍ１
（ａ６）抽出（列挙）された輪郭画素の２次元座標を格納する配列変数（配列）ｐ１
（ａ７）要素ｒ１（ｎ）が、第ｎ番目に追跡された輪郭線を構成する画素の系列の先頭画素（つまり始点）の配列ｐ１中での位置を表す整数の配列変数（配列）ｒ１
（ａ８）要素ｍ１（ｎ）が、第ｎ番目に追跡された輪郭線を構成する画素（つまり輪郭画素）の系列に含まれる輪郭画素の個数（輪郭画素数）を表す整数の配列変数（配列）ｍ１
を用いる。これらの変数群は、記憶装置１２に格納される。
【００２９】
次に、輪郭線追跡手段２１２によって実行される輪郭線抽出処理の手順について、図５及び図６のフローチャートを参照して説明する。この輪郭線抽出処理では、以下に述べるように、輪郭線を構成する輪郭画素が抽出（列挙）される。
【００３０】
まず輪郭線追跡手段２１２は、Ｎ１を０に、Ｍ１を０に、それぞれ初期化する（ステップ５０１）。また輪郭線追跡手段２１２は、配列ｇの要素を全て０に初期化する（ステップ５０２）。また輪郭線追跡手段２１２は、ｙ０を０に初期化する（ステップ５０３）。
【００３１】
次に輪郭線追跡手段２１２は、ｙ０がｈに達するまで以下のループＡの処理（ステップ５０４）を繰り返す。  
まず輪郭線追跡手段２１２は、ｘ０を０に初期化する（ステップ５０５）。次に輪郭線追跡手段２１２は、ｘ０がｗに達するまで以下のループＢの処理（ステップ５０６）を繰り返す。
【００３２】
まず輪郭線追跡手段２１２は、ｇ（ｘ０，ｙ０）＝０で且つｈ（ｘ０，ｙ０）＝０であるかを判定する（ステップ５０７）。もし、ステップ５０７の判定がＹｅｓであるならば、輪郭線追跡手段２１２は、ｍ１（Ｎ１）に０を、ｒ（Ｎ１）にＭ１を、それぞれ代入する（ステップ５０８）。また輪郭線追跡手段２１２は、ｘにｘ０を、ｙにｙ０を、それぞれ代入する（ステップ５０９）。また輪郭線追跡手段２１２は、ｄ０に２を代入する（ステップ５１０）。次に輪郭線追跡手段２１２は、ｄ１にｄ０を代入する（ステップ５１１）。
【００３３】
すると輪郭線追跡手段２１２は、ｘ＝ｘ０で且つｙ＝ｙ０で且つｄ１＝ｄ０となるまで以下のループＣの処理（ステップ６０１）を繰り返す。  
まず輪郭線追跡手段２１２は、ｐ１（Ｍ１）に座標（ｘ，ｙ）を代入する（ステップ６０２）。このステップ６０２が繰り返されることにより、座標（ｘ，ｙ）の画素（ｘ，ｙ）が輪郭画素として列挙（抽出）される。
【００３４】
次に輪郭線追跡手段２１２は、ｍ１（Ｎ１）にｍ１（Ｎ１）＋１を代入し（ステップ６０３）、Ｍ１にＭ１＋１を代入する（ステップ６０４）。
【００３５】
次に輪郭線追跡手段２１２は、座標（ｘ，ｙ）の画素（ｘ，ｙ）と、当該画素（ｘ，ｙ）からｄ２が指し示す方向に隣接した画素（隣接画素）との間にエッジが検出されているかを判定する（ステップ６０５）。このステップ６０５において輪郭線追跡手段２１２は、前記判定結果に基づき、隣接画素との間にエッジが検出されていない方向を指すようになるまで、ｄ２を以下の値
・（ｄ１＋３） ＭＯＤ ４
・  ｄ１
・（ｄ１＋１） ＭＯＤ ４
・（ｄ１＋２） ＭＯＤ ４
の順に変更する。但し、ｄ２の方向の画素が入力画像の範囲外ならば、輪郭線追跡手段２１２は、隣接画素の値は０であるとみなす。ここで、「ａ ＭＯＤ ｂ」はａをｂで割った余りを表す。
【００３６】
また輪郭線追跡手段２１２は、ｄ２が指し示す方向に隣接した画素との間にエッジが検出されているかを、ｄ２の値によって以下のように判定する。  
ｄ２＝０で且つｈ（ｘ，ｙ）＝０なら、エッジが検出されている。  
ｄ２＝１で且つｖ（ｘ，ｙ−１）＝０なら、エッジが検出されている。  
ｄ２＝２で且つｈ（ｘ−１，ｙ）＝０なら、エッジが検出されている。  
ｄ２＝３で且つｖ（ｘ，ｙ）＝０なら、エッジが検出されている。  
その他の場合は、エッジが検出されていない。
【００３７】
輪郭線追跡手段２１２は、ステップ６０５を実行し終えると、ｄ１にｄ２を代入し（ステップ６０６）、ｇ（ｘ，ｙ）に１を代入する（ステップ６０７）。  
次に輪郭線追跡手段２１２は、ｄ１の値に応じて、以下のいずれかの処理を行う（ステップ６０８）。  
ｄ１＝０なら、輪郭線追跡手段２１２はｘにｘ＋１を代入する。  
ｄ１＝１なら、輪郭線追跡手段２１２はｙにｙ−１を代入する。  
ｄ１＝２なら、輪郭線追跡手段２１２はｘにｘ−１を代入する。  
ｄ１＝３なら、輪郭線追跡手段２１２はｘにｙ＋１を代入する。
【００３８】
ステップ６０８の後、ｘ＝ｘ０で且つｙ＝ｙ０で且つｄ１＝ｄ０が成立していないならば、輪郭線追跡手段２１２はループＣ（ステップ６０１）を再び実行する。  
これに対し、ｘ＝ｘ０で且つｙ＝ｙ０で且つｄ１＝ｄ０が成立しているならば、輪郭線追跡手段２１２はループＣ（ステップ６０１）の繰り返しを終了する。
【００３９】
すると輪郭線追跡手段２１２は、Ｎ１にＮ１＋１を代入する（ステップ６０９）。  
次に輪郭線追跡手段２１２は、ｘ０を１増やす（ステップ６１０）。また、前記ステップ５０７の判定がＮｏの場合にも、輪郭線追跡手段２１２はｘ０を１増やす（ステップ６１０）。
【００４０】
ステップ６１０の後、ｘ０＝ｗが成立していないならば、輪郭線追跡手段２１２はループＢ（ステップ５０６）を再び実行する。  
これに対し、ｘ０＝ｗが成立しているならば、輪郭線追跡手段２１２はループＢ（ステップ５０６）の繰り返しを終了する。  
すると輪郭線追跡手段２１２は、ｙ０を１増やす（ステップ６１１）。
【００４１】
ステップ６１１の後、ｙ０＝ｈが成立していないならば、輪郭線追跡手段２１２はループＡ（ステップ５０４）を再び実行する。  
これに対し、ｙ０＝ｈが成立しているならば、輪郭線追跡手段２１２はループＡ（ステップ５０４）の繰り返しを終了する。
【００４２】
以上に述べた輪郭線追跡手段２１２の処理により、記憶装置１２には、抽出された輪郭線（を構成する輪郭画素の系列）の群に関する情報が格納される。図７は、この輪郭線の群に関する情報のデータ構造の例を示す図である。このデータ構造は、整数変数Ｎ１、整数変数Ｍ１、配列変数（配列）ｒ１、配列変数（配列）ｐ１及び配列変数（配列）ｍ１を含む。
【００４３】
図８は、図３に示した入力画像から輪郭線追跡手段２１２によって抽出された輪郭画素の系列全てをまとめて示す図である。図８には、１１の輪郭画素の系列８０１乃至８１１（より詳細には、１１の輪郭線を構成する輪郭画素の系列８０１乃至８１１）が示されている。系列８０１乃至８１１は、輪郭画素の系列の集合Ｓ１を構成する。
【００４４】
図９は、図８に示した輪郭画素の系列８０１乃至８１１のうちの系列８０１乃至８０６を個別に示す図であり、図１０は、当該輪郭画素の系列８０１乃至８１１のうちの系列８０７乃至８１１を個別に示す図である。
【００４５】
再び図２を参照すると、選択手段２２０は、輪郭線抽出手段２１０によって抽出されたた集合Ｓ１から、１つまたは複数の輪郭画素の系列を選択する。そして選択手段２２０は、選択された輪郭画素の系列を含む集合Ｓ４を、集合Ｓ１の部分集合Ｓ４として抽出する。選択手段２２０による輪郭画素の系列（つまり部分集合Ｓ４）の選択（抽出）の詳細について以下に説明する。
【００４６】
選択手段２２０は、ｎ＝０，…，Ｎ１−１の各々について、第ｎ番目に追跡された輪郭線を構成する輪郭画素の系列を選択するか否かを、次のような方法により判定する。  
（1-1）まず選択手段２２０は、第ｎ番目に追跡された輪郭線が取り囲む面積を算出する。算出された面積が負の場合、即ち第ｎ番目に追跡された輪郭線がエッジで区切られた画素の塊の外輪郭をなす場合には、選択手段２２０は、当該輪郭線を構成する画素の系列を選択しないと判定する。図８に示した輪郭画素の系列（輪郭線）の集合の場合、例えば、系列８０２及び８０３のうちの系列８０２、系列８０４び８０５のうちの系列８０４、系列８０６及び８０７のうちの系列８０６、系列８０８及び８０９のうちの系列８０８、そして系列８１０及び８１１のうちの系列８１０が、上記外輪郭をなすために選択されない。
【００４７】
第ｎ番目に追跡された輪郭線が取り囲む面積は、ｉ＝０，…，ｍ１（ｎ）−１の各々についての以下の値
（ｐ１（ｒ１（ｎ）＋ｉ）．ｘ
＋ｐ１（ｒ１（ｎ）＋ｉ＋１ ＭＯＤ ｍ１（ｎ））．ｘ）
×（ｐ１（ｒ１（ｎ）＋ｉ）．ｙ−ｐ１（ｒ１（ｎ）＋ｉ＋１）．ｙ）／２
を足し合わせることによって算出される。ここで、ｐ１（ｒ１（ｎ）＋ｉ）．ｘは、ｐ１（ｒ１（ｎ）＋ｉ）に格納された２次元座標のｘ成分を示し、ｐ１（ｒ１（ｎ）＋ｉ）．ｙは、ｐ１（ｒ１（ｎ）＋ｉ）に格納された２次元座標のｙ成分を示す。ｐ１（ｒ１（ｎ）＋ｉ＋１）．についても同様である。
【００４８】
（1-2）次に選択手段２２０は、ｉ＝０，…，ｍ１（ｎ）−１に関するｐ１（ｒ１（ｎ）＋ｉ）．ｘの、それぞれ最小値ｘｍｉｎ（ｎ）及び最大値ｘｍａｘ（ｎ）を算出する。そして選択手段２２０は、第ｎ番目に追跡された輪郭線の幅ｘｍａｘ（ｎ）−ｘｍｉｎ（ｎ）＋１を算出する。
【００４９】
算出された幅ｘｍａｘ（ｎ）−ｘｍｉｎ（ｎ）＋１が、予め定められたしきい値ｗｍｉｎ未満であるか、或いは予め定められたしきい値ｗｍａｘを超えるならば、選択手段２２０は、第ｎ番目に追跡された輪郭線を構成する輪郭画素の系列を選択しない。ｗｍｉｎが後述するように１６の場合、上述の外輪郭をなさない系列８０７，８０９及び８１１も選択されない。
【００５０】
（1-3）同様に選択手段２２０は、ｉ＝０，…，ｍ１（ｎ）−１に関するｐ１（ｒ１（ｎ）＋ｉ）．ｙの、それぞれ最小値ｙｍｉｎ（ｎ）及び最大値ｙｍａｘ（ｎ）を算出する。そして選択手段２２０は、第ｎ番目に追跡された輪郭線の高さｙｍａｘ（ｎ）−ｙｍｉｎ（ｎ）＋１を算出する。
【００５１】
算出された高さｘｍａｘ（ｎ）−ｘｍｉｎ（ｎ）＋１が、予め定められたしきい値ｈｍｉｎ未満であるか、或いは予め定められたしきい値ｈｍａｘを超えるならば、選択手段２２０は、第ｎ番目に追跡された輪郭線を構成する輪郭画素の系列を選択しない。
【００５２】
ｗｍａｘ及びｈｍａｘは、入力画像の周縁に対応する輪郭線の輪郭画素の系列８０１のように、枠とは無関係の輪郭線の輪郭画素の系列が選択されるのを防止するために設定される。一方、ｗｍｉｎ及びｈｍｉｎは、枠として用いられないような小領域の輪郭線の輪郭画素の系列が選択されるのを防止するために設定される。
【００５３】
（1-4）上記（1-2）、（1-3）のいずれにも該当しない場合、選択手段２２０は、第ｎ番目に追跡された輪郭線を構成する輪郭画素の系列を選択する。  
このようにして選択手段２２０は、集合Ｓ１から選択条件に合致する輪郭画素の系列を選択し、当該選択された輪郭画素の系列を集合（部分集合）Ｓ４に格納する。
【００５４】
集合Ｓ４の記憶装置１２におけるデータ構造は集合Ｓ１と同様である。つまり、集合Ｓ４のデータ構造は、変数Ｍ１、Ｎ１、ｒ１、ｐ１、ｍ１の代わりに、変数Ｍ４、Ｎ４、ｒ４、ｐ４、ｍ４を用いる点を除いてＳ１と同等である。後述する集合Ｓ２についても同様であり、変数Ｍ１、Ｎ１、ｒ１、ｐ１、ｍ１の代わりに、変数Ｍ２、Ｎ２、ｒ２、ｐ２、ｍ２が用いられる。また、後述する集合Ｓ３についても同様であり、変数Ｍ１、Ｎ１、ｒ１、ｐ１、ｍ１の代わりに、変数Ｍ３、Ｎ３、ｒ３、ｐ３、ｍ３が用いられる。
【００５５】
図１１は、図９及び図１０に示した輪郭画素の系列８０１乃至８１１から、上述の選択条件の下で選択手段２２０により抽出された輪郭画素の系列の集合Ｓ４の例を示す図である。選択条件は、例えばｗｍｉｎ＝１６、ｈｍｉｎ＝１６、ｗｍａｘ＝３４、ｈｍｉｎ＝３４を含む。図１１では、集合Ｓ４を構成する輪郭画素の系列（つまり選択された輪郭画素の系列）が実線で表され、選択されなかった輪郭画素の系列が破線で表されている。図１１の例では、集合Ｓ４は、２個の輪郭画素の系列８０３及び８０５から構成されており、領域検出装置によって検出された領域を表す。
【００５６】
なお、選択手段２２０が、前述の方法で抽出した集合のうちで面積が最大の系列だけを含む集合を集合Ｓ４として抽出してもよい。また選択手段２２０が、集合Ｓ１を構成する全ての輪郭画素の系列をＳ４に含めても良い。つまり、Ｓ４＝Ｓ１とすることにより、枠で囲まれた領域の輪郭画素の系列だけでなく、他の領域の輪郭画素の系列を抽出しても構わない。このように選択手段２２０において輪郭画素の系列を選択する方法は、後続の処理の負荷の大小や利用可能な計算機資源等の条件が許す限り、いかなる方法であっても良い。
【００５７】
領域出力手段２３０は、選択手段２２０によって輪郭画素の系列の集合Ｓ４が抽出されると領域取得手段として機能して、当該輪郭画素の系列の集合Ｓ４を、入力画像から検出された領域の情報（つまり、領域検出の結果）として取得する。領域出力手段２３０は、取得された領域検出の結果（つまり集合Ｓ４）を、領域検出装置の外部のデバイス（外部デバイス）または記憶装置１２に出力する。ここでは、領域出力手段２３０による集合Ｓ４の出力は、文字認識ソフトウェア１２２（より詳細には、文字認識ソフトウェア１２２に従って文字認識処理を実行するＣＰＵ１１）から参照可能な記憶装置１２の領域に変数Ｍ４、Ｎ４、ｒ４、ｐ４、ｍ４のコピーを作成することによって行われる。なお、領域出力手段２３０による集合Ｓ４の出力が、例えば入出力制御部１３及びシリアルインタフェース２２を介して、変数Ｍ４、Ｎ４、ｒ４、ｐ４、ｍ４の内容を外部デバイスに送信することで行われても構わない。つまり、領域出力手段２３０による集合Ｓ４の出力は、当該集合Ｓ４が何らかの形で情報処理の用に供される方法で行われるならば、他の方法で行われても構わない。
【００５８】
図１２は、第１の実施形態に係る領域検出装置に付加されている文字認識機構の機能構成を示すブロック図である。図１２に示す文字認識機構の機能構成は、ＣＰＵ１１が文字認識ソフトウェア１２２を読み取って実行することによって実現される。なお、文字認識機構が、外部デバイスに備えられていてもよい。この場合、領域出力手段２３０による集合Ｓ４の出力が、外部デバイスに対して行われればよい。
【００５９】
図１２に示す文字認識機構は、２値化手段２４０、画像抽出手段２５０、認識手段２６０及び認識結果出力手段２７０を備えている。  
２値化手段２４０は、入力画像を２値化して２値画像を生成する。
【００６０】
画像抽出手段２５０は、領域出力手段２３０によって出力された集合Ｓ４に含まれる輪郭画素の系列の各々について、上記２値画像から対応する画像を抽出する。つまり画像抽出手段２５０は、図２に示す領域検出装置によって検出された領域の画像を抽出する。
【００６１】
認識手段２６０は、画像抽出手段２５０によって抽出された画像上の文字（つまり領域検出装置で検出された領域内の文字）を認識する。認識結果出力手段２７０は、認識手段２６０によって認識された結果（認識結果）を、記憶装置１２または外部デバイスに出力する。
【００６２】
以下、図１２に示す文字認識機構の動作の詳細について説明する。  
２値化手段２４０は、入力画像を２値化して２値画像を生成する。この２値化には、例えば、周知のＮｉｂｌａｃｋのアルゴリズムが用いられるものとする。図１３は、図３に示した入力画像を２値化することによって生成される２値画像の例を示す図である。
【００６３】
画像抽出手段２５０は、集合Ｓ４に含まれる輪郭画素の系列で示される領域（つまり、領域検出装置によって検出された領域）の内部の画素を、上記２値画像から抽出する。そして画像抽出手段２５０は、検出された領域の外部の画素を白画素で埋めることにより、当該領域の外部の画素が白画素で埋められた抽出画像を生成する。この画像抽出手段２５０による抽出画像の生成について更に具体的に説明する。
【００６４】
まず画像抽出手段２５０は、周知のソリッド・スキャン・コンバージョンのアルゴリズムを用いて、集合Ｓ４に含まれる輪郭画素の系列に囲まれた領域（検出された領域）内の画素値が１で、当該領域外の画素値が０のマスク画像を生成する。そして画像抽出手段２５０は、マスク画像上の画素値が１の座標における画素値が入力画像のそれと一致し、残りの画素の画素値が白を示す抽出画像を生成する。
【００６５】
図１４は、図３に示した入力画像から最終的に抽出される輪郭画素の系列が図１１に示した系列８０３及び８０５である場合に、画像抽出手段２５０により生成されるマスク画像及び抽出画像の例を示す図である。ここでは、マスク画像は図１４（ａ）に示されており、画素値が１の画素が白で、画素値が０の画素が灰色で表されている。画素値が１の画素（つまり、白で表される画素）の領域は、図１１に示した系列８０５の示す輪郭線の内部の領域であり、図３に示した入力画像に含まれている丸枠内の領域に対応する。一方、抽出画像は図１４（ｂ）に示されている。図１４（ｂ）に示す抽出画像は、図３に示した入力画像に含まれている丸枠内の文字列「１０」を含む。
【００６６】
認識手段２６０は、周知の文字認識処理により文字列画像上の文字（文字列）を次のように認識する。まず認識手段２６０は、上記抽出画像からラベリングにより黒画素の連結成分を抽出した上で、当該連結成分の外接矩形内から部分画像を抽出する。次に認識手段２６０は、抽出された部分画像を部分空間法により認識して、認識結果に対応する文字コードを取得する。
【００６７】
認識結果出力手段２７０は、認識手段２６０によって取得された文字コードを記憶装置１２に出力する。もし、認識手段２６０によって複数の文字コードが取得されたならば、認識結果出力手段２７０は、当該複数の文字コードを外接矩形の中心座標の順にソートする。そして認識結果出力手段２７０は、ソートされた文字コードの列を、文字認識結果を表す文字列データとして、記憶装置１２に出力する。なお、認識結果出力手段２７０が、文字列データと改行コード（ＡＳＣＩＩコードならば０ｘ０ａ）とを文字認識結果として入出力制御部１３及びシリアルインタフェース２２を介して外部デバイスに出力してもよい。つまり、認識結果出力手段２７０による文字認識結果の出力は、当該文字認識結果が何らかの形で情報処理の用に供される方法で行われるならば、他の方法で行われても構わない。
【００６８】
第１の実施形態によれば、入力画像がモノクログレースケールでありながら、当該入力画像内の隣接する画素間からエッジを検出し、検出されたエッジで区切られた画素の塊毎に、当該画素の塊の輪郭線を追跡することにより、領域を形成する輪郭線を検出すること、つまり領域を検出することができる。
【００６９】
上記第１の実施形態では、入力画像がモノクログレースケールであることを想定している。しかしながら、入力画像がカラーであっても構わない。入力画像がカラーである場合、画素値の配列ｆの各要素に、カラーの画素値を表現する２次元以上のベクトル（以下、画素値ベクトルと称する）を適用するとよい。
【００７０】
画素値ベクトルを適用する場合、第１の実施形態において、しきい値Ｔｅとの比較のためエッジ検出手段２１１によって算出される、隣接する画素間の画素値の差の絶対値に代えて、当該隣接する画素間の画素値ベクトルの差分のノルムを用いるとよい。また、画素値ベクトルの成分を、赤、緑、青の色成分を表すＲＧＢ値としても、或いは赤、緑の色成分を表す２値としてもよい。要するに、画素値ベクトルの成分として、カメラ２１で撮像された画像の色を表現する値の組み合せならば、いずれを用いても構わない。
【００７１】
また、カメラ２１から入力された画素値の色成分の組み合せを、エッジ検出により一層適した別の色成分に変換する前処理が行われてもよい。この前処理として、例えばＲＧＢ表色系からＨＳＶ表色系への変換等が挙げられる。
【００７２】
［第２実施形態］
次に、第２の実施形態について説明する。  
第２の実施形態に係る領域検出装置のハードウェア構成は、第１の実施形態と同様である。但し、領域検出ソフトウェア１２１の構成は第１の実施形態と異なる。一方、文字認識ソフトウェア１２２の構成、つまり文字認識機構の構成は第１の実施形態と同様である。これらの点を考慮して、以下の説明では、便宜的に図１及び図１２を援用する。
【００７３】
図１５は第２の実施形態に係る領域検出装置の機能構成を示すブロック図である。図１５において図２と等価な構成要素には同一参照番号を付して、当該等価な構成要素についての詳細な説明は省略する。
【００７４】
図１５に示す領域検出装置は、図２に示した領域検出装置（第１の実施形態）と同様に、輪郭線抽出手段２１０及び領域出力手段２３０を備えている。この領域検出装置は更に、凸包抽出手段２８０及び選択手段２２１を備えている。
【００７５】
凸包抽出手段２８０は、輪郭線抽出手段２１０（より詳細には、輪郭線抽出手段２１０の輪郭線追跡手段２１２）によって抽出された輪郭画素の系列（以下、第１の輪郭画素の系列と称する）の集合Ｓ１に基づき、当該第１の輪郭画素の系列の各々の凸包を抽出する。具体的には、凸包抽出手段２８０は、集合Ｓ１に含まれる第１の輪郭画素の系列の各々について、ＧｒａｈａｍＳｃａｎのアルゴリズムを適用することで当該第１の輪郭画素の系列の凸包の頂点に位置する輪郭画素が当該凸包の外輪上での順に並んだ系列（以下、第２の輪郭画素の系列と称する）を抽出する。凸包抽出手段２８０は、抽出された第２の輪郭画素の系列を全て含む集合Ｓ３を取得する。つまり凸包抽出手段２８０は、集合Ｓ１に含まれる第１の輪郭画素の系列に対応して抽出された全ての第２の輪郭画素の系列を含む集合Ｓ３を取得する。集合Ｓ３を構成する第２の輪郭画素の系列の情報（変数Ｍ３、Ｎ３、ｒ３、ｐ３、ｍ３）は記憶装置１２に格納される。
【００７６】
選択手段２２１は、凸包抽出手段２８０によって取得された第２の輪郭画素の系列の集合Ｓ３から１つまたは複数の輪郭画素の系列を選択することにより、当該選択した輪郭画素の系列の集合Ｓ４（つまり、集合Ｓ３の部分集合Ｓ４）を抽出する。
【００７７】
次に、第２の実施形態の特徴について説明する。  
まず輪郭線抽出手段２１０が、入力画像から、第１の実施形態と同様に輪郭線毎に輪郭画素の系列を検出することにより、当該輪郭画素の系列の集合Ｓ１を抽出したものとする。図１６は、この入力画像の例を示す図である。図１６に示す入力画像では、図３に示した入力画像と異なり、丸枠内の文字列「１０」のうちの文字「０」の一部が、当該丸枠の内側と接触している。
【００７８】
図１７は、図１６に示した入力画像から輪郭線追跡手段２１２によって抽出された輪郭画素の系列全てをまとめて示す図である。図１７には、１０の輪郭画素の系列１７０１乃至１７１０（より詳細には、１０の輪郭線を構成する輪郭画素の系列１７０１乃至１７１０）が示されている。系列１７０１乃至１７１０は、輪郭画素の系列の集合Ｓ１を構成する。
【００７９】
ここで、系列１７０１乃至１７０４は、それぞれ図８の系列８０１乃至８０４に対応し、系列１７０６，１７０７，１７０８，１７０９及び１７１０は、それぞれ図８の系列８０６，８０７，８０９，８１０，及び８１１に対応する。これに対し、系列１７０５は、図８の２つの系列８０５及び８０８に対応する。その理由は、上述したように、図８の系列８０５に対応する丸枠の内側の輪郭線と文字「０」の外側の輪郭線とが接触しているためである。
【００８０】
図１８は、図１７に示した輪郭画素の系列１７０１乃至１７１０のうちの系列１７０１乃至１７０６を個別に示す図であり、図１９は、当該輪郭画素の系列１７０１乃至１７１０のうちの系列１７０７乃至１７１０を個別に示す図である。
【００８１】
図２０は、図１７に示した輪郭画素の系列１７０１乃至１７１０のうちの系列１７０５から凸包抽出手段２８０によって抽出された凸包を構成する輪郭画素の系列の例を示す図である。ここでは、第１の実施形態から類推されるように、輪郭画素の系列の集合Ｓ４は、系列１７０５から抽出された凸包を構成する輪郭画素の系列（図２０参照）と、系列１７０３から抽出された凸包を構成する輪郭画素の系列とから構成される。
【００８２】
図２１は、図１６に示した入力画像の場合に、画像抽出手段２５０によって生成されるマスク画像及び抽出画像の例を示す図である。ここでは、マスク画像は図２１（ａ）に示されており、画素値が１の画素が白で、画素値が０の画素が灰色で表されている。このマスク画像は、図１６に示した入力画像及び図２０に示した輪郭画素の系列（つまり、系列１７０５から抽出された凸包を構成する輪郭画素の系列）に基づいて画像抽出手段２５０によって生成されたものである。
【００８３】
一方、抽出画像は図２１（ｂ）に示されている。図２１（ｂ）は、図１６に示した入力画像及び図２１（ａ）に示したマスク画像に基づいて生成される抽出画像の例を示している。
【００８４】
図２２は第２の実施形態との比較のために、図１６に示した入力画像の場合に、第１の実施形態において画像抽出手段２５０によって生成されるマスク画像及び抽出画像の例を示す図である。ここでは、マスク画像は図２２（ａ）に示されており、抽出画像は図２２（ｂ）に示されている。図２２（ａ）に示すマスク画像は、図１６に示した入力画像と図１８（ｅ）に示した輪郭画素の系列に基づいて生成されたものであり、画素値が１の画素が白で、画素値が０の画素が灰色で表されている。
【００８５】
図２２（ａ）に示すマスク画像では、文字「０」を取り囲む輪郭線と枠の内側の輪郭線とが繋がっており、文字「０」を囲んでいない。したがって、図２２（ａ）に示すマスク画像と図１６に示した入力画像とに基づいて抽出画像を生成すると、図２２（ｂ）に示すように、文字「０」が消失し、文字列「１０」のうちの文字「１」のみが残ったものとなる。第２実施形態において、凸包を構成する輪郭画素の系列を適用しているのは、このような文字の消失（より詳細には、検出されるべき領域の輪郭線が枠に接触していることに起因して発生する文字の消失）を防止するためである。
【００８６】
第２の実施形態によれば、抽出された輪郭線を構成する輪郭画素の系列の各々の凸包を抽出することにより、たとえ枠と枠内の文字等が接触している場合でも、枠の内側と外側の区別をより確実にし、枠に囲まれた領域の検出性能を向上することができる。
【００８７】
［第３の実施形態］
次に、第３の実施形態について説明する。  
第３の実施形態に係る領域検出装置のハードウェア構成は、第１の実施形態と同様である。但し、領域検出ソフトウェア１２１の構成は第１の実施形態と異なる。一方、文字認識ソフトウェア１２２の構成、つまり文字認識機構の構成は第１の実施形態と同様である。これらの点を考慮して、以下の説明では、便宜的に図１及び図１２を援用する。
【００８８】
図２３は第３の実施形態に係る領域検出装置の機能構成を示すブロック図である。図２３において図２と等価な構成要素には同一参照番号を付して、当該等価な構成要素についての詳細な説明は省略する。
【００８９】
図２３に示す領域検出装置は、図２に示した領域検出装置（第１の実施形態）と同様に、輪郭線抽出手段２１０及び領域出力手段２３０を備えている。図２３に示す領域検出装置は更に、明暗判定手段２９０、変化点検出手段３００、輪郭線修正手段３１０及び選択手段２２２を備えている。
【００９０】
明暗判定手段２９０は、輪郭線抽出手段２１０（より詳細には、輪郭線抽出手段２１０の輪郭線追跡手段２１２）によって抽出された輪郭画素の系列の集合Ｓ１に基づき、当該輪郭画素の系列が近傍の画素と比較して明るいか暗いかを判定する。
【００９１】
変化点検出手段３００は、明暗判定手段２９０によって判定された明暗が対応する輪郭画素の系列で示される輪郭線上で変化する点（画素）の集合を当該輪郭画素の系列上で検出する。
【００９２】
輪郭線修正手段３１０は、変化点検出手段３００によって検出された点において輪郭線を繋ぎ直し、その繋ぎ直された輪郭線を構成する画素（輪郭画素）の系列の集合Ｓ２を取得する。
【００９３】
選択手段２２２は、輪郭線修正手段３１０によって取得された集合Ｓ２から１つまたは複数の輪郭画素の系列を選択することにより、当該選択した輪郭画素の系列の集合Ｓ４（つまり、集合Ｓ３の部分集合Ｓ４）を抽出する。
【００９４】
次に。図２３に示す領域検出装置の動作について説明する。  
ここでは、図２３に示す領域検出装置によって図２４に示す入力画像から枠で囲まれた領域が検出されるものとする。図２４に示す入力画像では、図３に示した入力画像と異なり、枠（丸枠）の一部に、いわゆる白飛びが発生している。つまり、本来黒画素として検出されるべき画素の系列が徐々に白画素に変化している。
【００９５】
輪郭線抽出手段２１０のエッジ検出手段２１１は、図２４に示す入力画像内の隣接する画素間からエッジを検出する。  
図２５は、図２４に示す入力画像内で隣接する２つの画素の対の群のうち、エッジ検出手段２１１によって当該２つの画素間にエッジが検出されなかった画素同士を線分で結んだ様子を示す図である。
【００９６】
輪郭線抽出手段２１０の輪郭線追跡手段２１２は、エッジ検出手段２１１によって検出されたエッジで区切られた画素の塊毎に、当該画素の塊の輪郭線を追跡する。輪郭線追跡手段２１２は、輪郭線追跡により検出された輪郭線を構成する輪郭画素の系列を、上記画素の塊に対応する輪郭線毎に抽出する。
【００９７】
図２６は、図２４に示した入力画像から輪郭線追跡手段２１２によって抽出された輪郭画素の系列全てをまとめて示す図である。図２６には、８つの輪郭画素の系列２６０１乃至２６０８（より詳細には、８つの輪郭線を構成する輪郭画素の系列２６０１乃至２６０８）が示されている。系列２６０１乃至２６０８は、輪郭画素の系列の集合Ｓ１を構成する。
【００９８】
ここで、系列２６０３乃至２６０８は、それぞれ図８の系列８０６乃至８１１に対応する。これに対し、系列２６０１は、図８の２つの系列８０２及び８０３に対応し、系列２６０２は、図８の２つの系列８０４及び８０５に対応する。その理由は、上述したように、図８の系列８０２及び８０３並びに８０４及び８０５に対応する丸枠の部分で白飛びが発生しているためである。なお、図２６には、図８の系列８０１に相当する輪郭画素の系列は省略されている。
【００９９】
図２７は、図２６に示した輪郭画素の系列２６０１乃至２６０８のうちの系列２６０１乃至２６０６を個別に示す図であり、図２８は、当該輪郭画素の系列２６０１乃至２６０８のうちの系列２６０７及び２６０８を個別に示す図である。
【０１００】
明暗判定手段２９０は、上記集合Ｓ１に含まれている輪郭画素の系列における輪郭画素の各々が近傍の画素と比較して明るいか暗いかを判定する。具体的には、明暗判定手段２９０は、輪郭画素が近傍の画素（予め定められた範囲内の画素）と比較して明るいか暗いかを、当該輪郭画素の画素値と、当該輪郭画素の上下左右にＤ画素を含む正方形（つまり、当該輪郭画素を中心とする縦横が２Ｄ＋１の領域）の内部の画素値の平均値とを比較することで判定する。図２９に明暗判定手段２９０による明暗判定の対象となる画素と近傍の画素との位置関係の例を示す。図２９において、判定の対象となる画素には記号×が付されている。
【０１０１】
明暗判定手段２９０による上述の明暗判定は、Ｍ１個の輪郭画素の各々について行われる。Ｍ１個の輪郭画素の各々の明暗判定結果は、要素数Ｍ１の整数配列ｓに格納される。この整数配列ｓは記憶装置１２に格納される。
【０１０２】
以下、明暗判定手段２９０によって実行される明暗判定処理の手順について図３０のフローチャートを参照して説明する。  
まず明暗判定手段２９０は、輪郭画素の番号を表す整数変数ｉを０に初期化する（ステップ３００１）。
【０１０３】
次に明暗判定手段２９０は、ｉがＭ１以上であるかを判定する（ステップ３００２）。もし、ｉ≧Ｍ１でないならば（ステップ３００２のＮｏ）、明暗判定手段２９０は、座標（ｐ１（ｉ）．ｘ，ｐ１（ｉ）．ｙ）の画素の画素値と、当該画素の上下左右にＤ画素を含む正方形の内部の画素値の平均値との差Δ（ｉ）を計算する（ステップ３００３）。
【０１０４】
次に明暗判定手段２９０は、Δ（ｉ）が正であるかを判定する（ステップ３００４）。明暗判定手段２９０は、Δ（ｉ）が正であるならば（ステップ３００４のＹｅｓ）、ｓ（ｉ）に「明」を示す１を代入し（ステップ３００５）、そうでないならば（ステップ３００４のＮｏ）、ｓ（ｉ）に「暗」を示す０を代入する（ステップ３００６）。ｓ（ｉ）は、図７に示した配列（配列変数）ｐ１の座標（ｐ１（ｉ）．ｘ、ｐ１（ｉ）．ｙ）に対応付けて記憶装置１２に格納される。
【０１０５】
次に明暗判定手段２９０は、ｉにｉ＋１を代入して（ステップ３００７）、ステップ３００２に戻る。以上の処理がＭ１回繰り返されて、ｉ≧Ｍ１となると（ステップ３００２のＹｅｓ）、明暗判定手段２９０は明暗判定処理を終了する。
【０１０６】
図３１は、明暗判定手段２９０によって取得される、配列ｐ１内の各画素（つまり抽出された輪郭画素の系列の各画素）が近傍の画素と比較して明るいか暗いかの判定結果を示す配列（配列変数）ｓ１を含む、記憶装置１２に格納される輪郭線の群に関する情報のデータ構造の例を示す図である。
【０１０７】
変化点検出手段３００は、明暗判定手段２９０によって判定された明暗が対応する輪郭画素の系列で示される輪郭線上で変化する点（以下、変化点と称する）を、当該輪郭画素の系列上で検出する。変化点検出手段３００は、検出された変化点を、対応する輪郭線の輪郭画素の系列上での当該変化点の順序数として、記憶装置１２に格納する。
【０１０８】
以下、変化点検出手段３００によって実行される変化点検出処理の手順について図３２のフローチャートを参照して説明する。  
まず変化点検出手段３００は、輪郭線の番号を表す整数変数ｊを０に初期化する（ステップ３２０１）。以下の説明では、ｊで示される輪郭線を輪郭線ｊと称することもある。
【０１０９】
次に変化点検出手段３００は、ｊがＮ１以上であるかを判定する（ステップ３２０２）。もし、ｊ≧Ｎ１でないならば（ステップ３２０２のＮｏ）、輪郭線ｊ上の変化点の個数を示す整数の配列変数ｅ（ｊ）に０を代入する（ステップ３２０３）。次に変化点検出手段３００は、ｓ（ｍ１（ｊ）−１）とｓ（０）とが異なるかを判定する（ステップ３２０４）。つまり変化点検出手段３００は、輪郭線ｊの終点（最後の画素）及び始点（最初の画素）の明暗が異なるかを判定する。
【０１１０】
もし、ｓ（ｍ１（ｊ）−１）≠ｓ（０）であるならば（ステップ３２０４のＹｅｓ）、変化点検出手段３００は、輪郭線ｊの始点は終点に対して変化点であると判定する。この場合、変化点検出手段３００は、変化点の輪郭線ｊ上における輪郭画素の番号を表す整数の配列変数ｃ（ｅ（ｊ）＋ｒ１（ｊ））に０を代入し（ステップ３２０５）、ｅ（ｊ）を１増やす（ステップ３２０６）。そして変化点検出手段３００は、輪郭線ｊ上の輪郭画素の番号を表す整数変数ｉを１に初期化する（ステップ３２０７）。以下の説明では、ｉで示される輪郭画素を輪郭画素ｉと称することもある。一方、ｓ（ｍ１（ｊ）−１）≠ｓ（０）でないならば（ステップ３２０４のＮｏ）、変化点検出手段３００はステップ３２０７にジャンプしてｉを１に初期化する。
【０１１１】
次に変化点検出手段３００は、前述のステップ３００２と同様にｉがＭ１以上であるかを判定する（ステップ３２０８）。もし、ｉ≧Ｍ１でないならば（ステップ３２０８のＮｏ）、変化点検出手段３００は、ｓ（ｉ−１）とｓ（ｉ）とが異なるかを判定する（ステップ３２０９）。つまり変化点検出手段３００は、輪郭線ｊ上のｉ−１番目の画素及びｉ番目の画素の明暗が異なるかを判定する。
【０１１２】
もし、ｓ（ｉ−１）≠ｓ（ｉ）であるならば（ステップ３２０９のＹｅｓ）、変化点検出手段３００は、ｉ番目の画素は変化点であると判定し、ｃ（ｅ（ｊ）＋ｒ１（ｊ））にｉを代入し（ステップ３２１０）、ｅ（ｊ）を１増やす（ステップ３２１１）。次に変化点検出手段３００はｉにｉ＋１を代入し（ステップ３２１２）、ステップ３２０８に戻る。これに対し、ｓ（ｉ−１）≠ｓ（ｉ）でないならば（ステップ３２０９のＮｏ）、つまりｓ（ｉ−１）＝ｓ（ｉ）であるならば、変化点検出手段３００はｉ番目の画素は変化点でないと判定する。この場合、変化点検出手段３００は、ステップ３２１２にジャンプしてｉにｉ＋１を代入し、ステップ３２０８に戻る。
【０１１３】
ステップ３２０８において変化点検出手段３００は、ｉ≧ｍ１（ｊ）であるかを判定する。もし、ｉ≧ｍ１（ｊ）であるならば（ステップ３２０８のＹｅｓ）、変化点検出手段３００はｊにｊ＋１を代入し（ステップ３２１３）、ステップ３２０２に戻る。ステップ３２０２において変化点検出手段３００は、ｊ≧Ｎ１であるかを判定する。もし、ｊ≧Ｎ１であるならば（ステップ３２０２のＹｅｓ）、変化点検出手段３００は変化点検出処理を終了する。
【０１１４】
図３３は、変化点検出手段３００によって取得される、各輪郭線上の変化点の個数を表す配列ｅ及び当該変化点の輪郭画素の番号を表す配列ｃを含む、記憶装置１２に格納される輪郭線の群に関する情報のデータ構造の例を示す図である。
【０１１５】
輪郭線修正手段３１０は、変化点検出手段３００によって検出された変化点において輪郭線を繋ぎ直す。そして輪郭線修正手段３１０は、繋ぎ直された輪郭線を構成する画素（輪郭画素）の系列の集合Ｓ２を取得する。輪郭線修正手段３１０は、上述の輪郭線の繋ぎ直し（つまり修正）のために、輪郭線切断手段３１１及び輪郭線再接続手段３１２を備えている。
【０１１６】
輪郭線切断手段３１１は、変化点検出手段３００によって検出された変化点において対応する輪郭画素の系列（つまり輪郭線）を切断する。輪郭線切断手段３１１は、この輪郭線の切断により、切断された輪郭線の断片を構成する輪郭画素の系列を取得する。取得された、輪郭線の断片を構成する輪郭画素の系列は、記憶装置１２に格納される。
【０１１７】
輪郭線再接続手段３１２は、輪郭線切断手段３１１によって取得された輪郭線の１つまたは複数の断片（つまり１つ以上の断片）を構成する輪郭画素の系列（１つ以上の系列）における端点を繋ぎ合わせる。この接続（つまり断片の接続）により、輪郭線再接続手段３１２は、接続（修正）された輪郭線を構成する画素の系列を取得する。
【０１１８】
第３の実施形態では、輪郭線の断片を構成する輪郭画素の系列に含まれる画素（輪郭画素）の座標が要素数Ｍ１の配列ｐ８に格納される。また、輪郭線の断片を構成する画素の系列に含まれる当該画素の数（輪郭画素数）が整数の配列ｍ８に、当該系列（つまり断片）の始点のｐ８中での位置（開始位置）が整数の配列ｒ８に格納される。図３４は、輪郭線の断片を構成する輪郭画素の系列を含む、記憶装置１２に格納される輪郭線の群に関する情報のデータ構造の例を示す図である。
【０１１９】
次に、輪郭線切断手段３１１によって実行される輪郭線切断処理の手順について、図３５乃至図３７のフローチャートを参照して説明する。  
まず輪郭線切断手段３１１は、切断中の輪郭線の番号を表す変数ｊを０に初期化する（ステップ３５０１）。このステップ３５０１において輪郭線切断手段３１１は、ｋを０に、Ｎ８を０に、それぞれ初期化する。ｋは輪郭線の切断された断片の始点の、当該輪郭線の輪郭画素の系列における位置（番号）を表す整数変数、Ｎ８は配列ｐ８の要素数を表す整数変数である。
【０１２０】
次に輪郭線切断手段３１１は、ｊがＮ１以上であるかを判定する（ステップ３５０２）。もし、ｊ≧Ｎ１でないならば（ステップ３５０２のＮｏ）、輪郭線切断手段３１１はｅ（ｊ）が０であるかを判定する（ステップ３５０３）。つまり輪郭線切断手段３１１は、輪郭線ｊ上の変化点の個数が０であるかを判定する。
【０１２１】
もし、ｅ（ｊ）＝０であるならば（ステップ３５０３のＹｅｓ）、輪郭線切断手段３１１はｍ８（Ｎ８）にｍ１（ｊ）を、ｒ８（Ｎ８）にｋを、ｉに０を、それぞれ代入する（ステップ３５０４，３５０５，３５０６）。
【０１２２】
次に輪郭線切断手段３１１は、ｉがｍ１（ｊ）以上であるかを判定する（ステップ３５０７）。もし、ｉ≧ｍ１（ｊ）でないならば、輪郭線切断手段３１１はｐ８（ｋ）．ｘにｐ１（ｋ）．ｘを、ｐ８（ｋ）．ｙにｐ１（ｋ）．ｙを、それぞれ代入する（ステップ３５０８，３５０９）。つまり輪郭線切断手段３１１は、輪郭線ｊ上のｋ番目の画素の座標を配列ｐ１から配列ｐ８にコピーする。次に輪郭線切断手段３１１は、ｉ及びｋを、それぞれ１増やす（ステップ３５１０）。
【０１２３】
すると輪郭線切断手段３１１はステップ３５０７に戻り、ｉがｍ１（ｊ）以上であるかを判定する。もし、ｉ≧ｍ１（ｊ）であるならば（ステップ３５０７のＹｅｓ）、輪郭線切断手段３１１はＮ８を１増やし（ステップ３５１１）、しかる後にｊを１増やす（ステップ３５１２）。そして輪郭線切断手段３１１はステップ３５０２に戻る。
【０１２４】
一方、ステップ３５０３で、ｅ（ｊ）＝０でないと判定されたならば、輪郭線切断手段３１１はステップ３６０１に進む。ステップ３６０１において輪郭線切断手段３１１は、ｃ（ｒ１（ｊ））が０であるかを判定する。もし、ｃ（ｒ１（ｊ））＝０であるならば（ステップ３６０１のＹｅｓ）、輪郭線切断手段３１１は、輪郭線上で最後に切り出す断片の直前の変化点の輪郭線上での番号を表す整数変数ｅａにｅ（ｊ）−１を代入する（ステップ３６０２）。そして輪郭線切断手段３１１は、後述するステップ３７０６に進む。
【０１２５】
これに対し、ｃ（ｒ１（ｊ））＝０でないならば（ステップ３６０１のＮｏ）、輪郭線切断手段３１１はｓｉ２にｃ（ｅ（ｊ）−１）を代入する（ステップ３６０３）。また輪郭線切断手段３１１は、ｅｉ３にｃ（０）−１を、ｅａにｅ（ｊ）−２をそれぞれ代入する（ステップ３６０４，３６０５）。
【０１２６】
輪郭線切断手段３１１は、ステップ３６０５を実行すると、ｍ８（Ｎ８）に０を代入し、ｉにｓｉ２を、それぞれ代入する（ステップ３６０６，３６０７）。次に輪郭線切断手段３１１は、ステップ３５０７と同様に、ｉがｍ１（ｊ）以上であるかを判定する（ステップ３６０８）。
【０１２７】
もし、ｉ≧ｍ１（ｊ）でないならば（ステップ３６０８のＮｏ）、輪郭線切断手段３１１は、ｐ８（ｋ）．ｘにｐ１（ｒ１（ｊ）＋ｉ）．ｘを、ｐ８（ｋ）．ｙにｐ１（ｒ１（ｊ）＋ｉ）．ｙを、それぞれ代入する（ステップ３６０９，３６１０）。また輪郭線切断手段３１１は、ｉ、ｋ及びｍ８（Ｎ８）を、それぞれ１増やす（ステップ３６１１）。
【０１２８】
すると輪郭線切断手段３１１はステップ３６０８に戻り、ｉがｍ１（ｊ）以上であるかを判定する。もし、ｉ≧ｍ１（ｊ）であるならば（ステップ３６０８のＹｅｓ）、輪郭線切断手段３１１はステップ３７０１に進む。ステップ３７０１において輪郭線切断手段３１１は、ｉに０を代入する。
【０１２９】
次に輪郭線切断手段３１１は、ｉがｅｉ３より大きいかを判定する（ステップ３７０２）。もし、ｉ＞ｅｉ３でないならば（ステップ３７０２のＮｏ）、輪郭線切断手段３１１は、ｐ８（ｋ）．ｘにｐ１（ｒ１（ｊ）＋ｉ）．ｘを、ｐ８（ｋ）．ｙにｐ１（ｒ１（ｊ）＋ｉ）．ｙを、それぞれ代入する（ステップ３７０３，３７０４）。次に輪郭線切断手段３１１は、ｉ、ｋ及びｍ８（Ｎ８）をそれぞれ１増やし（ステップ３７０５）、ステップ２７０２に戻る。これに対し、ｉ＞ｅｉ３であるならば（ステップ３７０２のＹｅｓ）、輪郭線切断手段３１１はステップ３７０６に進む。
【０１３０】
ステップ３７０６において輪郭線切断手段３１１は、新しく切り出す輪郭線の断片の直前の変化点の輪郭線上での番号を表す整数変数ａに０を代入する。次に輪郭線切断手段３１１は、ａがｅａより大きいかを判定する（ステップ３７０７）。もし、ａ＞ｅａであるならば（ステップ３７０７のＹｅｓ）、輪郭線切断手段３１１はステップ３５１２にジャンプする。すると輪郭線切断手段３１１は、ｊを１増やして（ステップ３５１２）、ステップ３５０２に戻る。
【０１３１】
一方、ａ＞ｅａでないならば（ステップ３７０７のＮｏ）、輪郭線切断手段３１１は、ｉにｃ（ａ）を、ｅｉ４にｃ（ａ）＋ｅ（ａ）−１を、それぞれ代入する（ステップ３７０８）。次に輪郭線切断手段３１１は、ｉがｅｉ４よりも大きいかを判定する（ステップ３７０９）。もし、ｉ＞ｅｉ４であるならば（ステップ３７０９のＹｅｓ）、輪郭線切断手段３１１は、ａ及びＮ８を、それぞれ１増やし（ステップ３７１０）、ステップ３７０７に戻る。
【０１３２】
これに対し、ｉ＞ｅｉ４でないならば（ステップ３７０９のＮｏ）、輪郭線切断手段３１１は、ｐ８（ｋ）．ｘにｐ１（ｒ１（ｊ）＋ｉ）．ｘを、ｐ８（ｋ）．ｙにｐ１（ｒ１（ｊ）＋ｉ）．ｙを、それぞれ代入する（ステップ３７１１，３７１２）。また輪郭線切断手段３１１は、ｉ、ｋ及びｍ８（Ｎ８）を、それぞれ１増やす（ステップ３７１３）。そして輪郭線切断手段３１１は、ステップ３７０９に戻る。
【０１３３】
前述したように輪郭線切断手段３１１は、ステップ３５１２においてｊを１増やすと、ステップ３５０２に戻る。もし、ｊを１増やした結果、ｉ≧Ｎ１となったならば（ステップ３５０２のＹｅｓ）、輪郭線切断手段３１１は輪郭線切断処理を終了する。
【０１３４】
以上に述べた輪郭線切断手段３１１の処理により，前記輪郭線抽出手段２１０で抽出された輪郭線の各々が前記変化点検出手段３００で検出した変化点の各々を境に切断した断片が生成され，配列変数ｐ８，ｍ８及びｒ８に格納される．
図３８は、図２６に示した輪郭線（つまり、図２４に示した入力画像から抽出された輪郭線）が輪郭線切断手段３１１によって切断された断片の輪郭画素の系列を含む全ての輪郭画素の系列をまとめて示す図である。なお、図３８において、図２６と同一の輪郭画素の系列には、同一参照番号を付してある。図３８には、図２６に示した輪郭画素の系列２６０１から構成される輪郭線が切断された２つの断片の輪郭画素の系列２６０１ａ及び２６０１ｂと、輪郭画素の系列２６０２から構成される輪郭線が切断された２つの断片の輪郭画素の系列２６０２ａ及び２６０２ｂとが示されている。また、図３８には、図２６に示した輪郭画素の系列２６０３乃至２６０８も示されている。
【０１３５】
図３９は、図３８に示した輪郭画素の系列のうちの系列２６０１ａ，２６０１ｂ，２６０２ａ，２６０２ｂ，２６０３及び２６０４を個別に示す図であり、図４０は、図３８に示した輪郭画素の系列のうちの系列２６０５乃至２６０８を個別に示す図である。
【０１３６】
輪郭線再接続手段３１２は、前述したように、輪郭線切断手段３１１によって取得された輪郭線の１つ以上の断片を構成する輪郭画素の系列の端点を繋ぎ合わせる（つまり接続する）ことにより、修正された輪郭線を構成する画素の系列を取得する。取得された輪郭線を構成する画素の系列の集合Ｓ２は記憶装置１２に格納される。
【０１３７】
輪郭線再接続手段３１２が輪郭線の断片同士を接続するためには、記憶装置１２に格納された順に各断片の後ろに接続すべき断片を決定する必要がある。以下、輪郭線再接続手段３１２によって実行される接続断片決定処理の手順について図４１及び図４２のフローチャートを参照して説明する。
【０１３８】
まず輪郭線再接続手段３１２は、ｊ＝０，…，Ｎ８−１のそれぞれについて、Ｆ（ｊ）に０を代入する（ステップ４１０１）。ここで、Ｆは要素数Ｎ８の整数の配列であり、Ｆ（ｊ）は配列Ｆのｊ番目の要素を示す。次に輪郭線再接続手段３１２は、整数変数ｋ及びｊを、それぞれ０を代入する（ステップ４１０２，４１０３）。
【０１３９】
次に輪郭線再接続手段３１２は、ｊがＮ８以上であるかを判定する（ステップ４１０４）。この例のようにｊ≧Ｎ８でないならば（ステップ４１０４のＮｏ）、輪郭線再接続手段３１２はＦ（ｊ）が０であるかを判定する（ステップ４１０５）。この例のようにＦ（ｊ）＝０であるならば（ステップ４１０５のＹｅｓ）、輪郭線再接続手段３１２は、ｒ８（ｊ）の示す画素を始点とするｊ番目の断片の隣接画素の系列をｐ８から取得し、当該ｊ番目の断片の隣接画素の系列を集合Ｓ２のｋ番目の系列として当該集合Ｓ２に格納する（ステップ４１０６）。ここで、ｊ番目の断片の隣接画素の系列を構成する隣接画素の個数は、ｍ８（ｊ）で示され、集合Ｓ２に格納される隣接画素の系列は、ｐ８（ｒ８（ｊ））の位置から始まるｍ８（ｊ）個の画素から構成される。
【０１４０】
次に輪郭線再接続手段３１２は、ｊ番目の断片の隣接画素の系列が集合Ｓ２に既に格納済みであることを示すために、Ｆ（ｊ）に１を代入する（ステップ４１０７）。次に輪郭線再接続手段３１２は、整数変数ｆｌａｇに０を代入する（ステップ４１０８）。一方、Ｆ（ｊ）＝０でないならば（ステップ４１０５のＮｏ）、つまりＦ（ｊ）＝１であるならば、輪郭線再接続手段３１２はｊ番目の断片の隣接画素の系列が集合Ｓ２に既に格納済みであると判断する。この場合、輪郭線再接続手段３１２は、整数変数ｆｌａｇに０を代入する（ステップ４１０８）。
【０１４１】
輪郭線再接続手段３１２は、整数変数ｆｌａｇに０を代入すると（ステップ４１０８）、ｊ２＝０，…，Ｎ８−１のそれぞれについて、ｓｃｏｒｅ（ｊ２）に０を代入する（ステップ４１０９）。ｓｃｏｒｅは要素数Ｎ８の実数の配列であり、ｓｃｏｒｅ＿（ｊ２）は、配列ｓｃｏｒｅのｊ２番目の要素を示す。
【０１４２】
次に輪郭線再接続手段３１２は、実数変数ｓｃｏｒｅ＿ｍａｘに−１を、整数変数ｊ２＿ｏｐｔに０を、それぞれ代入する（ステップ４１１０）。そして輪郭線再接続手段３１２は整数変数ｊ２に０を代入する（ステップ４１１１）。
【０１４３】
次に輪郭線再接続手段３１２は、ｊ２がＮ８以上であるかを判定する（ステップ４２０１）。この例のようにｊ２≧Ｎ８でないならば（ステップ４２０１のＮｏ）、輪郭線再接続手段３１２は、Ｆ（ｊ２）＝０で、且つｓ１（ｒ８（ｊ２））＝ｓ１（ｒ８（ｊ））で、且つｊ２番目の断片上の最初の輪郭画素とｊ番目の断片の最後の輪郭画素とのユークリッド距離ｕｄ（ｊ２，ｊ）が予め定められた正の定数εより小さいかを判定する（ステップ４２０２）。ここで、ｓ１（ｒ８（ｊ２））＝ｓ１（ｒ８（ｊ））であること、つまりｊ２番目の断片の始点の明暗がｊ番目の断片の始点の明暗と一致することは、ｊ２番目の断片上の輪郭画素を近傍の輪郭画素と比較した明暗がｊ番目の断片上のそれと一致することを示す。また、ｕｄ（ｊ２，ｊ）＜εは、ｊ２番目の断片上の端点（例えば始点）とｊ番目の断片の端点（例えば終点）の位置が予め定められた範囲（つまり、近傍として定義される範囲）にあることを示す。
【０１４４】
もし、ステップ４２０２の判定がＹｅｓであるならば、輪郭線再接続手段３１２は、ｊ番目の断片の最後の輪郭画素（つまり終点）から最後からδ番目の輪郭画素へのベクトルＶＡを算出する（ステップ４２０３）。δは予め定められた自然数である。また輪郭線再接続手段３１２は、ｊ２番目の断片の最初の輪郭画素（つまり始点）から最初からδ番目の輪郭画素へのベクトルＶＢを算出する（ステップ４２０４）。
【０１４５】
次に輪郭線再接続手段３１２は、ベクトルＶＡとベクトルＶＢとがなす角度θを余弦定理により算出する（ステップ４２０５）。ここでは、角度θの単位は「度」であるとする。次に輪郭線再接続手段３１２は、角度θがｓｃｏｒｅ＿ｍａｘよりも大きいかを判定する（ステップ４２０６）。
【０１４６】
ステップ４２０９の判定は、ベクトルＶＡとベクトルＶＢとがなす角度θが、ｊ２がそれぞれ０，…，Ｎ８−１番目の断片のうちｊ番目の断片に対して最も大きい（つまり１８０度に最も近い）断片を検出するために、ステップ４２０２の示す条件を満たす断片について繰り返し行われる。ｊ番目の断片に対してベクトルＶＡとベクトルＶＢとがなす角度θが最も大きい断片がｊ２＿ｏｐｔ番目の断片である場合、ｊ２＿ｏｐｔ番目の断片の端点（ここでは始点）が、０，…，Ｎ８−１番目の断片の端点の中で、ｊ番目の断片の端点（ここでは終点）に対して最も正対しているといえる。
【０１４７】
もし、θ＞ｓｃｏｒｅ＿ｍａｘであるならば（ステップ４２０６のＹｅｓ）、輪郭線再接続手段３１２は、ｓｃｏｒｅ＿ｍａｘにθを、整数変数ｊ２＿ｏｐｔにｊ２を代入する（ステップ４２０７）。次に輪郭線再接続手段３１２はｆｌａｇに１を代入し（ステップ４２０８）、しかる後にｊ２を１増やす（ステップ４２０９）。ｆｌａｇ＝１は、ｊ番目の断片に接続されるべき断片が存在することを示す。整数変数ｊ２＿ｏｐｔ＝ｊ２は、ｊ番目の断片に接続されるべき断片として、断片０，…，ｊ２のうちの断片ｊ２が最適であることを示す。
【０１４８】
一方、θ＞ｓｃｏｒｅ＿ｍａｘでないならば（ステップ４２０６のＮｏ）、輪郭線再接続手段３１２はステップ４２０９にジャンプしてｊ２を１増やす。また、ステップ４２０２の判定がＮｏの場合にも、輪郭線再接続手段３１２はステップ４２０９にジャンプしてｊ２を１増やす。
【０１４９】
輪郭線再接続手段３１２は、ｊ２を１増やすと（ステップ４２０９）、ステップ４２０１に戻り、ｊ２≧Ｎ８であるかを判定する。もし、ｊ２≧Ｎ８であるならば、輪郭線再接続手段３１２は、ｊ番目の断片に接続されるべき断片をｊ２＝０，…，Ｎ８−１についてチェックし終えたと判断する。
【０１５０】
そこで輪郭線再接続手段３１２は、ｆｌａｇが１であるかを判定する（ステップ４２１０）。もし、ｆｌａｇ＝１であるならば（ステップ４２１０のＹｅｓ）、輪郭線再接続手段３１２は、集合Ｓ２のｋ番目の輪郭画素の系列（の示す輪郭線の断片）の末尾にｊ２＿ｏｐｔ番目の断片の輪郭画素の系列を追加する（ステップ４２１１）。
【０１５１】
このように、ｋ番目の輪郭線の断片へのｊ２＿ｏｐｔ番目の断片の追加は、当該ｊ２＿ｏｐｔ番目の断片に含まれる輪郭画素の系列を当該輪郭線の輪郭画素の系列に追加することで行われる。これにより、ｋ番目の輪郭線の断片にｊ２＿ｏｐｔ番目の断片が繋ぎ合わされたことになる。ここで、ｊ２＿ｏｐｔ番目の断片の輪郭画素の系列は、ｐ８に格納されている断片の輪郭画素の系列のうち、輪郭画素ｒ８（ｊ２＿ｏｐｔ）の示す画素を始点とする断片の輪郭画素の系列であり、ｍ８（ｊ）で示される個数の輪郭画素から構成される。
【０１５２】
輪郭線再接続手段３１２は、ｋ番目の輪郭線の断片にｊ２＿ｏｐｔ番目の断片を追加すると（ステップ４２１１）、Ｆ（ｊ２＿ｏｐｔ）に１を代入する（ステップ４２１２）。次に輪郭線再接続手段３１２は、ｋを１増やし（ステップ４１１２）、ｊを１増やす（ステップ４１１３）。一方、ｆｌａｇ＝１でないならば（ステップ４２１０のＮｏ）、輪郭線再接続手段３１２はステップ４１１２にジャンプしてｋを１増やし、ｊを１増やす（ステップ４１１３）。輪郭線再接続手段３１２は、ｊを１増やすと（ステップ４１１３）、ステップ４１０４に戻り、ｊがＮ８以上であるかを判定する。もし、ｊ≧Ｎ８であるならば（ステップ４１０４のＹｅｓ）、輪郭線再接続手段３１２は輪郭線再接続処理を終了する。
【０１５３】
図４３は、図３８に示した輪郭画素の系列の群に含まれている切断された断片の輪郭画素の系列の再接続後の全ての輪郭画素の系列をまとめて示す図である。なお、図４３において、図３８と同一の輪郭画素の系列には、同一参照番号を付してある。図４３には、図３８に示した断片の輪郭画素の系列２６０１ａの始点及び終点が接続された輪郭線の輪郭画素の系列４３０１及び図３８に示した断片の輪郭画素の系列２６０１ｂの始点及び終点が接続された輪郭線の輪郭画素の系列４３０２が示されている。
【０１５４】
系列４３０１及び４３０２は、それぞれ断片の輪郭画素の系列２６０１ａ及び２６０１ｂを、上記ステップ４１０６で集合Ｓ２に格納することにより生成される。系列２６０１ａ及び２６０１ｂの末尾に別の断片の輪郭画素の系列が追加されない場合、つまりステップ４２１１が実行されない場合、系列２６０１ａ及び２６０１ｂが集合Ｓ２に格納されるだけで、系列２６０１ａの両端、及び系列２６０１ｂの両端が、それぞれ繋がれたことになる。
【０１５５】
図４３にはまた、図３８に示した断片の輪郭画素の系列２６０２ａの始点及び終点が接続された輪郭線の輪郭画素の系列４３０３及び図３８に示した断片の輪郭画素の系列２６０２ｂの始点及び終点が接続された輪郭線の輪郭画素の系列４３０４が示されている。系列４３０３及び４３０４は、それぞれ断片の輪郭画素の系列２６０２ａ及び２６０２ｂを、上記ステップ４１０６で集合Ｓ２に格納することにより生成される。図４３には更に、図３８に示した輪郭画素の系列２６０３乃至２６０８も示されている。
【０１５６】
図４４は、図４３に示した輪郭画素の系列のうちの系列４３０１乃至４３０４、２６０３及び２６０４を個別に示す図であり、図４５は、図４３に示した輪郭画素の系列のうちの系列２６０５乃至２６０８を個別に示す図である。
【０１５７】
なお、輪郭線の断片を構成する輪郭画素の系列におけるそれぞれ１つまたは複数の端点を繋ぎ合わせる手法は、近傍の画素と比較した明暗が一致しており、端点が最も正対している断片同士を繋ぎ合せる手法ならば、第３の実施形態で適用した方法に限らずいかなる方法で行ってもよい。
【０１５８】
また、輪郭線再接続手段３１２が、Ｍ２にＭ１を、Ｎ２にＮ８を、それぞれ代入し、ｊ＝１，…，Ｎ８について、ｒ２（ｊ）にｒ８（ｊ）を、ｍ１（ｊ）にｒ８（ｊ）を、それぞれ代入してもよい。つまり、輪郭線再接続手段３１２が、輪郭線切断手段３１１によって得られた断片の両端を単純に繋いだものを新しい輪郭線としてもよい。
【０１５９】
さて、輪郭線再接続手段３１２による輪郭線再接続処理が終了すると、選択手段２２２は、輪郭線修正手段３１０によって取得された集合Ｓ２から、第１の実施形態における選択手段２２０と同様に１つまたは複数の輪郭画素の系列を選択することにより、当該選択した輪郭画素の系列の集合Ｓ４を抽出する。
【０１６０】
第３の実施形態によれば、輪郭画素の系列で示される輪郭線上で変化する点（変化点）を検出して、当該変化点において輪郭線を繋ぎ直すことにより、光の反射などに起因する白飛びに頑健な領域検出を実現することができる。
【０１６１】
［第４実施形態］
次に、第４の実施形態について説明する。  
第４の実施形態に係る領域検出装置のハードウェア構成は、第１の実施形態と同様である。但し、領域検出ソフトウェア１２１の構成は第１の実施形態と異なる。
【０１６２】
図４６は第４の実施形態に係る領域検出装置の機能構成を示すブロック図である。図４６において、図２、図１５または図２３と等価な構成要素には同一参照番号を付して、当該等価な構成要素についての詳細な説明は省略する。
【０１６３】
図４６に示す領域検出装置は、図２、図１５及び図２３に示した領域検出装置と同様に、輪郭線抽出手段２１０及び領域出力手段２３０を備えている。図４６に示す領域検出装置はまた、図２３に示した領域検出装置と同様に、明暗判定手段２９０、変化点検出手段３００及び変化点検出手段３００を備えている。図４６に示す領域検出装置は更に、図１５に示した領域検出装置内の凸包抽出手段２８０に相当する凸包抽出手段２８１を備えると共に、図１５に示した領域検出装置と同様に選択手段２２１を備えている。
【０１６４】
凸包抽出手段２８１は、輪郭線修正手段３１０（輪郭線再接続手段３１２）によって取得された集合Ｓ２に含まれる輪郭画素の系列の各々の凸包を抽出し、当該凸包を構成する画素の系列の集合Ｓ３を取得する。凸包抽出手段２８１は、凸包抽出の対象となる輪郭画素の系列の集合が集合Ｓ１ではなくて集合Ｓ２である点を除き、第２の実施形態で適用される凸包抽出手段２８０と同様である。
【０１６５】
図４６に示す領域検出装置の特徴は、第３の実施形態で適用された図２３に示す領域検出装置の構成において、輪郭線修正手段３１０及び領域出力手段２３０の間に、第２の実施形態で適用された凸包抽出手段２８０及び選択手段２２１に対応する、凸包抽出手段２８１及び選択手段２２１を追加した点にある。
【０１６６】
第２の実施形態及び第３の実施形態から明らかなように、第４の実施形態によれば、白飛びに頑健な領域検出を実現すると共に、枠と枠内の文字等が接触している場合における枠に囲まれた領域の検出性能を向上することができる。
【０１６７】
以上説明した少なくとも１つの実施形態によれば、枠と枠内の文字等が接触している場合における枠の内側と外側の区別をより確実にし、枠に囲まれた領域の検出性能を向上できる領域検出装置、領域検出方法及びプログラムを提供することができる。
【０１６８】
本発明のいくつかの実施形態を説明したが、これらの実施形態は、例として提示したものであり、発明の範囲を限定することは意図していない。これら新規な実施形態は、その他の様々な形態で実施されることが可能であり、発明の要旨を逸脱しない範囲で、種々の省略、置き換え、変更を行うことができる。これら実施形態やその変形は、発明の範囲や要旨に含まれるとともに、特許請求の範囲に記載された発明とその均等の範囲に含まれる。
【符号の説明】
【０１６９】
１０…コンピュータ（ＰＣ）、１１…ＣＰＵ、１２…記憶装置、２１…カメラ、２１０…輪郭線抽出手段、２１１…エッジ検出手段、２１２…輪郭線追跡手段、２２０，２２１…選択手段、２３０…領域出力手段、２４０…２値化手段、２５０…画像抽出手段、２６０…認識手段、２７０…認識結果出力手段、２８０，２８１…凸包抽出手段、２９０…明暗判定手段、３００…変化点検出手段、３１０…輪郭線修正手段、３１１…輪郭線切断手段、３１２…輪郭線再接続手段。
【図１】
0005653308.tif 000002
【図２】
0005653308.tif 000003
【図３】
0005653308.tif 000004
【図４】
0005653308.tif 000005
【図５】
0005653308.tif 000006
【図６】
0005653308.tif 000007
【図７】
0005653308.tif 000008
【図８】
0005653308.tif 000009
【図９】
0005653308.tif 000010
【図１０】
0005653308.tif 000011
【図１１】
0005653308.tif 000012
【図１２】
0005653308.tif 000013
【図１３】
0005653308.tif 000014
【図１４】
0005653308.tif 000015
【図１５】
0005653308.tif 000016
【図１６】
0005653308.tif 000017
【図１７】
0005653308.tif 000018
【図１８】
0005653308.tif 000019
【図１９】
0005653308.tif 000020
【図２０】
0005653308.tif 000021
【図２１】
0005653308.tif 000022
【図２２】
0005653308.tif 000023
【図２３】
0005653308.tif 000024
【図２４】
0005653308.tif 000025
【図２５】
0005653308.tif 000026
【図２６】
0005653308.tif 000027
【図２７】
0005653308.tif 000028
【図２８】
0005653308.tif 000029
【図２９】
0005653308.tif 000030
【図３０】
0005653308.tif 000031
【図３１】
0005653308.tif 000032
【図３２】
0005653308.tif 000033
【図３３】
0005653308.tif 000034
【図３４】
0005653308.tif 000035
【図３５】
0005653308.tif 000036
【図３６】
0005653308.tif 000037
【図３７】
0005653308.tif 000038
【図３８】
0005653308.tif 000039
【図３９】
0005653308.tif 000040
【図４０】
0005653308.tif 000041
【図４１】
0005653308.tif 000042
【図４２】
0005653308.tif 000043
【図４３】
0005653308.tif 000044
【図４４】
0005653308.tif 000045
【図４５】
0005653308.tif 000046
【図４６】
0005653308.tif 000047