(57)【特許請求の範囲】
【請求項１】
少なくとも文字画像を含む画像を受け付ける受付手段と、
前記受付手段によって受け付けられた画像に対して、該画像内の文字画像を分離する線分である分離経路を算出する経路算出手段と、
前記経路算出手段によって算出された複数方向の分離経路の特徴量を算出する特徴量算出手段と、
前記特徴量算出手段によって算出された特徴量に基づいて、画像の分離方向及び文字画像の状態を判別し、該判別の結果によって前記複数方向の分離経路のうちの分離経路を選択する選択手段と、
前記選択手段によって選択された分離経路により、前記画像を複数の部分画像へ分離する分離手段と、
前記分離手段によって分離された画像の前記文字画像の状態に基づいて、再帰的に処理を行うか否かを判断する再帰処理判断手段
を具備し、
前記経路算出手段は、前記再帰処理判断手段によって再帰的に処理を行うと判断された場合に、前記分離手段によって分離された画像に対して、該画像内の文字画像を分離する線分である分離経路を算出する
ことを特徴とする画像処理装置。
【請求項２】
再帰的処理を行わないで、画像を分離する第２の分離手段と、
前記受付手段が受け付けた画像又は前記分離手段によって分離された部分画像の縦方向の長さと横方向の長さの比率と予め定められた値との比較、又は前記再帰処理判断手段によって再帰的に処理を行うと判断された場合の再帰の深さに基づいて、該画像又は該部分画像を対象として、前記第２の分離手段又は前記経路算出手段に処理を行わせるか否かを判断する判断手段
をさらに具備することを特徴とする請求項１に記載の画像処理装置。
【請求項３】
前記選択手段は、前記文字画像の状態が多段落である場合は、前記経路算出手段によって算出された分離経路を間引く
ことを特徴とする請求項１又は２に記載の画像処理装置。
【請求項４】
コンピュータを、
少なくとも文字画像を含む画像を受け付ける受付手段と、
前記受付手段によって受け付けられた画像に対して、該画像内の文字画像を分離する線分である分離経路を算出する経路算出手段と、
前記経路算出手段によって算出された複数方向の分離経路の特徴量を算出する特徴量算出手段と、
前記特徴量算出手段によって算出された特徴量に基づいて、画像の分離方向及び文字画像の状態を判別し、該判別の結果によって前記複数方向の分離経路のうちの分離経路を選択する選択手段と、
前記選択手段によって選択された分離経路により、前記画像を複数の部分画像へ分離する分離手段と、
前記分離手段によって分離された画像の前記文字画像の状態に基づいて、再帰的に処理を行うか否かを判断する再帰処理判断手段
として機能させ、
前記経路算出手段は、前記再帰処理判断手段によって再帰的に処理を行うと判断された場合に、前記分離手段によって分離された画像に対して、該画像内の文字画像を分離する線分である分離経路を算出する
ことを特徴とする画像処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置及び画像処理プログラムに関する。
【背景技術】
【０００２】
画像内から対象とする領域を分離する技術がある。
これに関連する技術として、例えば、特許文献１には、文書画像の行と段の抽出機能を持つ文書画像認識装置に関し、横行と縦行が混在する文書画像の行・段の抽出を高速かつ高精度に行うことができるようにすることを目的とし、文書画像傾き検出部は、文書画像を参照して文字を構成する成分の集合を抽出し、これをもとに横及び縦の行候補を抽出し、それらの各々の行候補に対して信頼度を推定し、推定した行信頼度に基づいて確度の高い行の集合を抽出し、その結果をもとに確度の高い行の集合の文字成分の配置を用いて傾きを推定し、レイアウト解析部は、文書画像を構成する基礎要素の集合から行方向の確定した行集合を抽出し、行どうしの関連付けによる段抽出と段を制約とした行抽出とを相互に実行して行と段を抽出することが開示されている。
【０００３】
また、例えば、特許文献２には、文書画像の傾き検出及び行と段の抽出機能を持つ文書画像認識装置に関し、横行と縦行が混在する文書画像の傾き検出及び行・段の抽出を高速かつ高精度に行うことができるようにすることを目的とし、文書画像傾き検出部は、文書画像を参照して文字を構成する成分の集合を抽出し、これをもとに横及び縦の行候補を抽出し、それらの各々の行候補に対して信頼度を推定し、推定した行信頼度に基づいて確度の高い行の集合を抽出する。その結果をもとに確度の高い行の集合の文字成分の配置を用いて傾きを推定する。レイアウト解析部は、文書画像を構成する基礎要素の集合から行方向の確定した行集合を抽出し、行どうしの関連付けによる段抽出と段を制約とした行抽出とを相互に実行して行と段を抽出することが開示されている。
【０００４】
また、例えば、特許文献３には、複雑なレイアウトの文書画像から適切な行又はテキストブロックを抽出することを課題とし、文書画像における空白領域を仮想的なセパレータとして抽出し（ステップＳ１）、仮想的なセパレータを越えたテキスト要素の統合を禁止するもとで、複数のテキスト要素を統合して統合テキスト要素として抽出し（ステップＳ２）、これにより、文書画像レイアウトに応じた統合テキスト要素が抽出され、また、抽出した統合テキスト要素が行又はテキストブロックとして適合か不適合かを検証し（ステップＳ３）、その検証の結果不適合の場合には空白領域の大きさを制御パラメータにより変化させ、不適合とされた統合テキスト要素に対して変化させた空白領域に基づいた仮想的なセパレータを再抽出しステップＳ２の処理を行い、このような処理を再帰的に繰り返すことで、複雑なレイアウトの文書画像においても適切な行又はテキストブロックが抽出されることが開示されている。
【０００５】
また、例えば、特許文献４には、文書内における縦書き文章領域や横書き文章領域の段組構成、文章領域内の各文字サイズ等を考慮することなく、局所的な画素の配置情報に基づいて領域の抽出処理を行うと、結果として得られる領域情報は必ずしも文書の論理構造を反映するものとはならないことを課題とし、画像入力部から入力された文書画像を分割して文章領域を抽出する画像処理装置において、入力文書画像に含まれる文章が縦書きであるか又は横書きであるかを文章方向算定部で算定し、この文章方向算定部による算定結果を参照して分割境界設定部で入力文書画像を分割する境界を設定し、そして、領域分割部において、分割境界設定部で設定された境界にて入力文書画像を分割することが開示されている。
【０００６】
また、例えば、特許文献５には、文字行方向が不明で、文字の大きさやピッチ、文字行方向の異なる文字行や写真等の領域が混在する文書からの文字行抽出を可能にすることを課題とし、文字行候補生成部で、画像データより生成した画素連結矩形を接続し、文字行候補を生成し、文字矩形生成部で、生成された文字行候補を非分割領域として、主方向、副方向に適宜分割して、副方向の文字行を抽出するとともに、文字行候補内で基本矩形の統合を行うことにより文字矩形を生成し、文字行候補分割部で、文字矩形サイズの平均値、分散値から文字行候補の構成を判定し、構成に応じて文字行候補を分割し、文字矩形接続部で、分割された文字行候補の領域内において文字矩形を接続することにより文字行を抽出することが開示されている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００８−２１７８３３号公報
【特許文献２】特開平１１−２１９４０７号公報
【特許文献３】特開２００５−２５０８１６号公報
【特許文献４】特開２０００−０９０１９４号公報
【特許文献５】特開平１０−０３１７１６号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
本発明は、投影分布又は連結成分を用いた技術では、文字列どうしの境界が不明確となる画像であって複数の段落を含む画像を対象とした場合に、文字画像が分離できなくなってしまうことを抑制するようにした画像処理装置及び画像処理プログラムを提供することを目的としている。
【課題を解決するための手段】
【０００９】
かかる目的を達成するための本発明の要旨とするところは、次の各項の発明に存する。
請求項１の発明は、少なくとも文字画像を含む画像を受け付ける受付手段と、前記受付手段によって受け付けられた画像に対して、該画像内の文字画像を分離する線分である分離経路を算出する経路算出手段と、前記経路算出手段によって算出された複数方向の分離経路の特徴量を算出する特徴量算出手段と、前記特徴量算出手段によって算出された特徴量に基づいて、画像の分離方向及び文字画像の状態を判別し、該判別の結果によって前記複数方向の分離経路のうちの分離経路を選択する選択手段と、前記選択手段によって選択された分離経路により、前記画像を複数の部分画像へ分離する分離手段と、前記分離手段によって分離された画像の前記文字画像の状態に基づいて、再帰的に処理を行うか否かを判断する再帰処理判断手段を具備し、前記経路算出手段は、前記再帰処理判断手段によって再帰的に処理を行うと判断された場合に、前記分離手段によって分離された画像に対して、該画像内の文字画像を分離する線分である分離経路を算出することを特徴とする画像処理装置である。
【００１０】
請求項２の発明は、再帰的処理を行わないで、画像を分離する第２の分離手段と、前記受付手段が受け付けた画像又は前記分離手段によって分離された部分画像の縦方向の長さと横方向の長さの比率と予め定められた値との比較、又は前記再帰処理判断手段によって再帰的に処理を行うと判断された場合の再帰の深さに基づいて、該画像又は該部分画像を対象として、前記第２の分離手段又は前記経路算出手段に処理を行わせるか否かを判断する判断手段をさらに具備することを特徴とする請求項１に記載の画像処理装置である。
【００１１】
請求項３の発明は、前記選択手段は、前記文字画像の状態が多段落である場合は、前記経路算出手段によって算出された分離経路を間引くことを特徴とする請求項１又は２に記載の画像処理装置である。
【００１２】
請求項４の発明は、コンピュータを、少なくとも文字画像を含む画像を受け付ける受付手段と、前記受付手段によって受け付けられた画像に対して、該画像内の文字画像を分離する線分である分離経路を算出する経路算出手段と、前記経路算出手段によって算出された複数方向の分離経路の特徴量を算出する特徴量算出手段と、前記特徴量算出手段によって算出された特徴量に基づいて、画像の分離方向及び文字画像の状態を判別し、該判別の結果によって前記複数方向の分離経路のうちの分離経路を選択する選択手段と、前記選択手段によって選択された分離経路により、前記画像を複数の部分画像へ分離する分離手段と、前記分離手段によって分離された画像の前記文字画像の状態に基づいて、再帰的に処理を行うか否かを判断する再帰処理判断手段として機能させ、前記経路算出手段は、前記再帰処理判断手段によって再帰的に処理を行うと判断された場合に、前記分離手段によって分離された画像に対して、該画像内の文字画像を分離する線分である分離経路を算出することを特徴とする画像処理プログラムである。
【発明の効果】
【００１３】
請求項１の画像処理装置によれば、投影分布又は連結成分を用いた技術では、文字列どうしの境界が不明確となる画像であって複数の段落を含む画像を対象とした場合に、文字画像が分離できなくなってしまうことを抑制することができる。
【００１４】
請求項２の画像処理装置によれば、再帰的な処理を行う必要がない画像に対して、再帰的な処理をしてしまうことを抑制することができる。
【００１５】
請求項３の画像処理装置によれば、本構成を有していない場合に比較して、余分な分離経路に対する処理を減少させることができる。
【００１６】
請求項４の画像処理プログラムによれば、投影分布又は連結成分を用いた技術では、文字列どうしの境界が不明確となる画像であって複数の段落を含む画像を対象とした場合に、文字画像が分離できなくなってしまうことを抑制することができる。
【図面の簡単な説明】
【００１７】
【図１】画像を領域に分離する経路の例を示す説明図である。
【図２】異なる始点をもつ複数の経路が、同じ終点をもつ例を示す説明図である。
【図３】対象とする画像の例を示す説明図である。
【図４】上方向への最短経路の例を示す説明図である。
【図５】下方向への最短経路の例を示す説明図である。
【図６】１回の往復によって得られる最短経路の例を示す説明図である。
【図７】２回の往復によって得られる最短経路の例を示す説明図である。
【図８】３回の往復によって得られる最短経路の例を示す説明図である。
【図９】収束した場合の最短経路の例を示す説明図である。
【図１０】最短経路によって画像を領域に分離した例を示す説明図である。
【図１１】＜Ａ＞の実施の形態の基本構成例についての概念的なモジュール構成図である。
【図１２】第Ａ−１の実施の形態の構成例についての概念的なモジュール構成図である。
【図１３】第Ａ−２の実施の形態の構成例についての概念的なモジュール構成図である。
【図１４】第Ａ−３の実施の形態の構成例についての概念的なモジュール構成図である。
【図１５】第Ａ−４の実施の形態の構成例についての概念的なモジュール構成図である。
【図１６】第Ａ−５の実施の形態の構成例についての概念的なモジュール構成図である。
【図１７】経路抽出モジュールを組み込んだ画像処理装置の構成例についての概念的なモジュール構成図である。
【図１８】経路抽出モジュールを組み込んだ画像処理装置の構成例についての概念的なモジュール構成図である。
【図１９】経路抽出モジュールを組み込んだ画像処理装置の構成例についての概念的なモジュール構成図である。
【図２０】経路抽出モジュールを組み込んだ画像処理装置の構成例についての概念的なモジュール構成図である。
【図２１】経路情報の算出例を示す説明図である。
【図２２】経路情報の算出例を示す説明図である。
【図２３】経路情報を算出するために必要となる情報の例を示す説明図である。
【図２４】対象とする画像の例を示す説明図である。
【図２５】対象とする画像を分離した例を示す説明図である。
【図２６】対象とする画像の投影情報の例を示す説明図である。
【図２７】分離経路の算出処理の例を示す説明図である。
【図２８】分離経路の結合処理の例を示す説明図である。
【図２９】分離経路の結合処理の例を示す説明図である。
【図３０】特徴量の例を示す説明図である。
【図３１】第Ｂ−１の実施の形態の構成例についての概念的なモジュール構成図である。
【図３２】第Ｂ−２の実施の形態の構成例についての概念的なモジュール構成図である。
【図３３】方向判別の処理の例を示すフローチャートである。
【図３４】第Ｂ−３の実施の形態の構成例についての概念的なモジュール構成図である。
【図３５】投影分布の例を示す説明図である。
【図３６】水平、垂直方向の分離経路の例を示す説明図である。
【図３７】水平、垂直方向の分離経路の例を示す説明図である。
【図３８】水平、垂直方向の分離経路の例を示す説明図である。
【図３９】本実施の形態による処理例を示す説明図である。
【図４０】本実施の形態による処理例を示す説明図である。
【図４１】本実施の形態による処理例を示す説明図である。
【図４２】第Ｃ−１の実施の形態の構成例についての概念的なモジュール構成図である。
【図４３】特徴量の例を示す説明図である。
【図４４】第Ｃ−２の実施の形態の構成例についての概念的なモジュール構成図である。
【図４５】分離経路による画像分離モジュールの構成例についての概念的なモジュール構成図である。
【図４６】再帰処理モジュールによる処理例を示すフローチャートである。
【図４７】主分離方向判別モジュールによる処理例を示すフローチャートである。
【図４８】主分離経路選択モジュールによる処理例（１）を示すフローチャートである。
【図４９】主分離経路選択モジュールによる処理例（２）を示すフローチャートである。
【図５０】主分離経路選択モジュールによる処理例（３）を示すフローチャートである。
【図５１】主分離経路選択モジュールによる処理例（４）を示すフローチャートである。
【図５２】主分離経路選択モジュールによる処理例（５）を示すフローチャートである。
【図５３】主分離経路選択モジュールによる処理例（６）を示すフローチャートである。
【図５４】第Ｃ−３の実施の形態の構成例についての概念的なモジュール構成図である。
【図５５】解析器選択モジュールによる処理例を示すフローチャートである。
【図５６】再帰処理モジュールによる処理例を示すフローチャートである。
【図５７】解析器選択モジュールによる多段落判別の処理例（１）を示すフローチャートである。
【図５８】解析器選択モジュールによる多段落判別の処理例（２）を示すフローチャートである。
【図５９】第Ｃ−４の実施の形態の構成例についての概念的なモジュール構成図である。
【図６０】第Ｃ−５の実施の形態の構成例についての概念的なモジュール構成図である。
【図６１】多段落であるにもかかわらず単段落として処理してしまった場合の処理結果の例を示す説明図である。
【図６２】第Ｃ−１〜第Ｃ−５の実施の形態による処理結果の例を示す説明図である。
【図６３】本実施の形態を実現するコンピュータのハードウェア構成例を示すブロック図である。
【発明を実施するための形態】
【００１８】
＜Ａ＞、＜Ｂ＞、＜Ｃ＞に分けて説明する。＜Ａ＞に記載のものは、＜Ｂ＞に記載のものを実現するために前提となる技術の一部の説明である。＜Ａ＞、＜Ｂ＞に記載のものは、＜Ｃ＞に記載のものを実現するために前提となる技術の一部の説明である。
【００１９】
＜Ａ＞に記載のものは、文字列画像内から文字を分離するためのものであり、＜Ｂ＞に記載のものは、１つの段落の画像内から文字列を分離するためのものであり、＜Ｃ＞に記載のものは、複数の段落の画像内から文字列を分離するためのものである。
【００２０】
＜Ａ＞前提となる技術
まず、＜Ａ＞に示す実施の形態の概略を説明する。
本実施の形態は、画像内から領域を分離する（切り出す、抽出等ともいわれる）画像処理装置に関するものである。領域を分離するためには、その領域を囲む外郭を決定する必要がある。そこで、領域を囲む外郭として最短経路を採用する。この最短経路によって画像内から領域を分離しようとするものである。
ここで、最短経路とは、対象とする画像上のピクセル（の位置）の１次元配列である線パタンであり、経路上のピクセルの輝度値の累積値をコストとして、ある範囲においてコスト最小又はコスト最大の経路を指す。特に本実施の形態において最短経路とは、図１に例示するように、画像１００に対して領域を分割するための外郭にあたり、画像１００の下端のあるピクセルを始点１１１として、画像１００の上端にあるピクセルであって、終点候補のセットとしての予め定められた終点候補１２０内において、経路上のピクセルの輝度値の累積値が最小又は最大となるように定めたピクセルを終点１２１とした経路である。また、始点１１１と終点候補１２０が定まると、移動範囲１３０が定まることになる。
なお、コスト最小又はコスト最大の用語を用いるが、必ずしも最小、最大である必要はない。ここでのコスト最小又はコスト最大とは、その経路を抽出するための判断条件であり、その経路のコスト（経路上のピクセルの輝度値の累積値）が他の経路のコストよりも小さい又は大きいことであればよい。したがって、最短経路という場合は、特に明記する場合以外は、比較した範囲内で経路のコストが最小又は最大である経路であることの他に、画像を分割する経路を抽出するという目的を達成するための判断条件としてであれば、コストが最小又は最大から２番目等を選択した場合の経路であってもよいし、コストが最小又は最大から１番目、２番目等の複数を選択した場合の経路であってもよい。
【００２１】
次に、最短経路の収束を利用した分離経路の決定について説明する。
本実施の形態は、前述の最短経路について、始点の異なる複数の経路が同一の終点をもつ（以下、経路の収束、とよぶ）ことを利用する。この様子を図２の例に模式的に示す。図２は、異なる始点をもつ複数の経路が、同じ終点をもつ例を示す説明図である。つまり、画像２００を対象として、始点２１１〜２１３の３つの始点から出発した最短経路が１つの終点２２１に到達していることを示しており、始点２１４〜２１８の５つの始点から出発した最短経路が１つの終点２２２に到達していることを示している。
以下、複数の単文字を含む文字列画像を受け付けて、単文字どうしを分離することを主に例示して説明する。
本実施の形態は、最短経路の情報に基づいて、文字列画像について、単文字どうしを分離する経路を算出する。なお、前述の先行技術文献に記載されている技術において、この処理の役割をもつ処理は、投影情報又は連結成分に基づく分離領域候補の抽出処理にあたる。
【００２２】
以下、図３〜図１０に示す例を用いて、経路の収束を利用した分離経路の決定について説明する。
図３は、対象とする画像の例を示す説明図である。画像３００内には、「Ｓ」の文字画像３１０、「Ｔ」の文字画像３２０、「Ｕ」の文字画像３３０を含んでおり、これらは写像をとると互いに重なっているパタンである。セルはピクセルを表し、セルの値はピクセルの輝度値を表す。さらに、図３の例について、最短経路を算出したものを図４、図５の例に示す。セルの数値について、１は経路があることを、０は経路がないことを表している。図４の例は、下端のすべてのピクセルを始点として上端にあるピクセルを終点とする、上方向の最短経路を表す。図５の例は、上端のすべてのピクセルを始点として下端にあるピクセルを終点とする、下方向の最短経路を表す。それぞれ、経路が収束していることが分かる。つまり、始点の数よりも終点の数が少ないのであるから、始点の異なる複数の経路が同一の終点をもっている。
【００２３】
ここで、図４の例のすべての終点を始点とした場合に、下方向への最短経路を算出する処理を行う。この処理結果を図６の例に示す。このように、片方の方向のすべての経路の終点を、もう片方の方向の始点として経路を算出する作業（以下、往復、とする）により、さらに経路が収束する。つまり、図６は、１回の往復（上方向から下方向）によって得られる最短経路の例を示す説明図である。
以下、上方向を開始の方向として、２回の往復により得られた最短経路の例を図７に、３回の往復により得られた最短経路の例を図８に、往復により経路の始点終点に変化がなくなった状態で得られる最短経路の例を図９に示す。ここで、経路の始点終点に変化がなくなった状態とは、上方向の経路と下方向の経路が合致することをいい、合致とは、経路が一致することをいい、その方向は問わない。つまり、一方の始点は他方の終点となり、一方の終点は他方の始点となることである。
また、図９に例示する最短経路を分離経路として、図３に例示する画像を分離する様子を図１０の例に模式的に表す。つまり、画像３００は、分離経路１０１０、分離経路１０２０、分離経路１０３０、分離経路１０４０によって、文字画像３１０（文字「Ｓ」）と文字画像３２０（文字「Ｔ」）と文字画像３３０（文字「Ｕ」）との領域に分離されていることが分かる。
本実施の形態は、このように、経路の収束に基づき、分離経路の絞り込みを行うものである。
【００２４】
なお、本実施の形態において、往復の処理は、経路の始点と終点のペアのセットを利用することで、経路の始点と終点の中間のピクセルの位置等を記憶する必要がなくなり、処理対象とするデータ量も少なくなる。また、図９の例に示すような、完全に収束した経路は、経路の始点と終点のペアのセットだけを利用して、中間のピクセルの位置等がなくても算出され得るものである。
往復回数を指定する経路の算出（つまり、必ずしも完全な収束とはならない算出）は、往復回数に対して、分離経路数は単調減少であることを利用して、本実施の形態全体が要求に合わせて分離の度合いを調節するようにしてもよい。
【００２５】
以下、図面に基づき本発明を実現するにあたっての好適な各種の実施の形態の例を説明する。
＜本実施の形態の基本構成例＞
まず、図１１に、本実施の形態（画像処理装置である経路抽出装置）の基本構成例についての概念的なモジュール構成図を示す。この基本構成例は、以下の処理を行う。
（１）経路情報算出処理：経路要求を受け取ると、対象画像を解析し、経路情報を算出する処理である。この処理は、次の２種類がある。
（ア）順方向の経路情報算出（順方向経路情報算出モジュール１１１０による処理）
（イ）逆方向の経路情報算出（逆方向経路情報算出モジュール１１３０による処理）
（２）経路選択（経路選択モジュール１１２０による処理）：経路情報を参照し、経路の収束に基づいて経路を選択する処理である。
【００２６】
（１）経路情報算出処理は、順方向経路情報算出モジュール１１１０、逆方向経路情報算出モジュール１１３０によって行われる。順方向経路情報算出モジュール１１１０、逆方向経路情報算出モジュール１１３０は、経路選択モジュール１１２０と接続されており、画像１１０１を解析し、前述した最短経路の情報（経路情報１１１１、１１３１）を算出する処理を行う。ここで、順方向とは出力する経路の方向であり、逆方向とは順方向と逆の方向である。例えば、図９の例に示す経路は、上方向が順方向、下方向が逆方向となる。
【００２７】
（２）経路選択は、経路選択モジュール１１２０によって行われる。経路選択モジュール１１２０は、順方向経路情報算出モジュール１１１０、逆方向経路情報算出モジュール１１３０と接続されており、順方向経路情報算出モジュール１１１０、逆方向経路情報算出モジュール１１３０が出力する順方向、逆方向の経路情報（経路情報１１１１、１１３１）を得る。さらに、得られた経路情報について、経路の収束を利用した経路の選択を行い、分離経路１１９９を出力する。
図１１の例において、破線で示す情報（開始要求１１０２、経路要求１１２１、経路要求１１２２）は必ずしも存在しない処理を表す。具体的に、開始要求は、経路選択の往復回数、初期方向、初期始点を指定する情報である。また、経路要求は、順方向経路情報算出モジュール１１１０、逆方向経路情報算出モジュール１１３０が経路情報を算出するための経路の始点を指定する情報である。
【００２８】
なお、モジュールとは、一般的に論理的に分離可能なソフトウェア（コンピュータ・プログラム）、ハードウェア等の部品を指す。したがって、本実施の形態におけるモジュールはコンピュータ・プログラムにおけるモジュールのことだけでなく、ハードウェア構成におけるモジュールも指す。それゆえ、本実施の形態は、コンピュータ・プログラム、システム及び方法の説明をも兼ねている。ただし、説明の都合上、「記憶する」、「記憶させる」、これらと同等の文言を用いるが、これらの文言は、実施の形態がコンピュータ・プログラムの場合は、記憶装置に記憶させる、又は記憶装置に記憶させるように制御するの意である。また、モジュールは機能に一対一に対応していてもよいが、実装においては、１モジュールを１プログラムで構成してもよいし、複数モジュールを１プログラムで構成してもよく、逆に１モジュールを複数プログラムで構成してもよい。また、複数モジュールは１コンピュータによって実行されてもよいし、分散又は並列環境におけるコンピュータによって１モジュールが複数コンピュータで実行されてもよい。なお、１つのモジュールに他のモジュールが含まれていてもよい。また、以下、「接続」とは物理的な接続の他、論理的な接続（データの授受、指示、データ間の参照関係等）の場合にも用いる。
また、システム又は装置とは、複数のコンピュータ、ハードウェア、装置等がネットワーク（一対一対応の通信接続を含む）等の通信手段で接続されて構成されるほか、１つのコンピュータ、ハードウェア、装置等によって実現される場合も含まれる。「装置」と「システム」とは、互いに同義の用語として用いる。もちろんのことながら、「システム」には、人為的な取り決めである社会的な「仕組み」（社会システム）にすぎないものは含まない。「予め定められた」とは、対象としている処理の前に定まっていることをいい、本実施の形態による処理が始まる前はもちろんのこと、本実施の形態による処理が始まった後であっても、対象としている処理の前であれば、そのときの状況・状態に応じて、又はそれまでの状況・状態に応じて定まることの意を含めて用いる。
また、各モジュールによる処理毎に又はモジュール内で複数の処理を行う場合はその処理毎に、対象となる情報を記憶装置から読み込み、その処理を行った後に、処理結果を記憶装置に書き出すものである。したがって、処理前の記憶装置からの読み込み、処理後の記憶装置への書き出しについては、説明を省略する場合がある。なお、ここでの記憶装置としては、ハードディスク、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、外部記憶媒体、通信回線を介した記憶装置、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）内のレジスタ等を含んでいてもよい。
また、対象とする画像として、１行の横書きの複数文字の画像とした例を主に説明する。
【００２９】
＜実施の形態の分類＞
以降、実施の形態の例は、以下の項目によって分類している。
（１）往復回数
（２）経路情報の算出のタイミング
（３）絞り込む情報
（４）絞り込みの調節
つまり、表１の例に示すように分類している。
【表１】
0005577948.tif 000002
【００３０】
（１）往復回数は、前述した、往復を行う回数による分類である。往復を行う回数に対して、分離経路の数は単調減少である。第Ａ−１の実施の形態は、往復回数が１回（順方向、逆方向ともに１回）のものであり、他の実施の形態は、往復回数が複数の回数のものである。
（２）経路情報の算出のタイミングは、経路情報の算出について、予めすべての経路情報を算出するか（以下、予め一括して算出という）、又は、逐次必要な経路情報を算出する（以下、逐次算出という）か、による分類である。ワークメモリと、処理時間のトレードオフに関係する。第Ａ−２の実施の形態、第Ａ−３の実施の形態は、予め一括して算出するものであり、第Ａ−４の実施の形態、第Ａ−５の実施の形態は、逐次算出するものである。
【００３１】
（３）絞り込む情報は、最短経路の収束を利用した経路の絞り込みを行う際に、経路そのもの（始点、終点の位置の他にその中間にある経路上のピクセルの位置）を参照するか、又は、始点（若しくは、始点と終点のペア）を参照するか、による分類である。実装においては、ワークメモリ、処理時間の観から、主に後者が選択される。第Ａ−２の実施の形態、第Ａ−４の実施の形態は、経路そのものを参照するものであり、第Ａ−３の実施の形態、第Ａ−５の実施の形態は、始点を参照するものである。
（４）絞り込みの調節は、予め定められた往復回数による絞り込みの結果を分離経路とするか、又は、完全な収束の結果を分離経路とするか、による分類である。両者では、処理が異なる。また、予め一括して経路情報を算出する場合（第Ａ−２の実施の形態、第Ａ−３の実施の形態）において、完全な収束の結果を分離経路とする例を示す。なお、逐次算出によって、完全な収束の結果を得る実施の形態の例もあるが、これは、往復回数を無限大として、終了条件を付けるものであり、往復回数を指定するものと同等であるため、実施の形態を示さない。
【００３２】
＜第Ａ−１の実施の形態＞
図１２は、第Ａ−１の実施の形態の構成例についての概念的なモジュール構成図である。第Ａ−１の実施の形態の例は、１回の往復により、経路を絞り込むものであり、順方向経路算出モジュール１２１０、逆方向経路終点算出モジュール１２２０を有しており、順方向経路算出モジュール１２１０と逆方向経路終点算出モジュール１２２０は、接続されている。
【００３３】
第Ａ−１の実施の形態は、以下の処理を行う。
＜＜ｓｔｅｐ１．＞＞
逆方向経路算出モジュール１２２０は、画像１２０１と初期始点１２０２を受け付け、画像１２０１を解析することによって、初期始点１２０２に対応する最短経路の終点１２２１を算出し、順方向経路算出モジュール１２１０へ出力する。
＜＜ｓｔｅｐ２．＞＞
順方向経路算出モジュール１２１０は、画像１２０１を解析することによって、受け取った終点１２２１を始点として、その始点に対応する分離経路１２９９を算出し、出力し、終了する。
なお、順方向経路算出モジュール１２１０は、図１１の例に示した経路選択モジュール１１２０の役割も有していることになる。
【００３４】
＜第Ａ−２の実施の形態＞
第Ａ−２の実施の形態以降は、複数回の往復により、経路を絞り込む構成である。
図１３は、第Ａ−２の実施の形態の構成例についての概念的なモジュール構成図である。第Ａ−２の実施の形態の例は、予め一括して経路情報を算出し、これを絞り込むものであり、順方向経路算出モジュール１３１０、経路選択モジュール１３２０、逆方向経路始点終点表算出モジュール１３３０を有している。特に、予め一括してすべての経路情報を算出し、これを絞り込む場合について説明する。なお、すべての経路とは、対象とする画像の上端又は下端のすべてのピクセルを始点とする場合のすべての経路である。
また、第Ａ−２の実施の形態、第Ａ−３の実施の形態は、始めの１回のみ経路情報を算出するため、処理時間の削減を図る場合に用いられるものである。
【００３５】
第Ａ−２の実施の形態は、以下の処理を行う。
＜＜ｓｔｅｐ１．＞＞
逆方向経路始点終点表算出モジュール１３３０は、経路選択モジュール１３２０と接続されており、画像１３０１を解析することによって、始点終点表１３３１を算出し、経路選択モジュール１３２０へ出力する。
そして、順方向経路算出モジュール１３１０は、経路選択モジュール１３２０と接続されており、画像１３０１を解析することによって、すべての始点の経路１３１１を算出し、経路選択モジュール１３２０へ出力する。
＜＜ｓｔｅｐ２．＞＞
経路選択モジュール１３２０は、順方向経路算出モジュール１３１０、逆方向経路始点終点表算出モジュール１３３０と接続されており、順方向の経路１３１１と逆方向の始点終点表１３３１に基づいて、経路を絞り込み、分離経路１３９９として出力し、終了する。
なお、始点終点表については後述する。
【００３６】
＜第Ａ−３の実施の形態＞
図１４は、第Ａ−３の実施の形態の構成例についての概念的なモジュール構成図である。第Ａ−３の実施の形態の例は、始点終点表と経路作成情報のみを算出し、始点を絞り込んだのち、経路を算出するものであり、順方向経路始点終点表算出モジュール１４１０、始点選択モジュール１４２０、逆方向経路始点終点表算出モジュール１４３０、順方向経路作成モジュール１４４０を有している。
【００３７】
第Ａ−３の実施の形態は、以下の処理を行う。
＜＜ｓｔｅｐ１．＞＞
逆方向経路始点終点表算出モジュール１４３０は、始点選択モジュール１４２０と接続されており、画像１４０１を解析することによって、始点終点表１４３１を算出し、始点選択モジュール１４２０へ出力する。
そして、順方向経路始点終点表算出モジュール１４１０は、始点選択モジュール１４２０、順方向経路作成モジュール１４４０と接続されており、画像１４０１を解析することによって、始点終点表１４１１を算出し、始点選択モジュール１４２０へ出力する。さらに、経路作成情報１４１２を算出し、順方向経路作成モジュール１４４０へ出力する。
＜＜ｓｔｅｐ２．＞＞
始点選択モジュール１４２０は、順方向経路始点終点表算出モジュール１４１０、逆方向経路始点終点表算出モジュール１４３０、順方向経路作成モジュール１４４０と接続されており、順方向の経路の始点終点表１４１１と、逆方向の経路の始点終点表１４３１に基づいて、経路の始点１４２１の絞り込みを行い、順方向経路作成モジュール１４４０へ出力する。
＜＜ｓｔｅｐ３．＞＞
順方向経路作成モジュール１４４０は、順方向経路始点終点表算出モジュール１４１０、始点選択モジュール１４２０と接続されており、順方向経路始点終点表算出モジュール１４１０から受け取った経路作成情報１４１２に基づいて、始点選択モジュール１４２０から受け取った始点１４２１の経路を作成し、分離経路１４９９として出力する。
【００３８】
ここで、始点終点表について説明する。
始点終点表とは、経路の始点と終点のペアを保持した情報である。第Ａ−２の実施の形態（図１３）、第Ａ−３の実施の形態（図１４）における経路の絞り込み処理においては、経路の始点と終点のペアの情報を利用する。以下、この処理を説明する。
いま、順方向の始点終点表を数１とする。
【数１】
0005577948.tif 000003
また、逆方向の始点終点表をＴ’とする。数２は、位置ｘを始点とする経路の終点位置を表す。
【数２】
0005577948.tif 000004
始点終点表は、すべての始点の経路の始点と終点のペアの配列であり、ｗは対象とする画像の横幅（文字列方向の幅）である。
なお、第Ａ−２の実施の形態（図１３）の経路選択モジュール１３２０は、受け取った経路１３１１からＴを算出し、以下同様の処理を行うものとする。
【００３９】
ある経路を数３とする。
【数３】
0005577948.tif 000005
高さｙにおける経路の位置を数４とする。
【数４】
0005577948.tif 000006
例えば、上方向の経路の始点は数５であり、終点は数６である。
【数５】
0005577948.tif 000007
【数６】
0005577948.tif 000008
なお、ｈは対象とする画像の縦幅（文字列方向と垂直な方向の幅）である。順方向が上方向のとき、経路選択モジュール１３２０が受け付けた経路１３１１のセットを数７として、すべての数８について、数９とすることで、受け付けた経路からＴを算出する。また、順方向が下方向であれば、数１０とする。
【数７】
0005577948.tif 000009
【数８】
0005577948.tif 000010
【数９】
0005577948.tif 000011
【数１０】
0005577948.tif 000012
また、出力する経路の方向である順方向と、往復回数によって、初めに参照する始点終点表の方向（初期方向とする）が定まる。具体的には、往復回数が奇数であれば、初期方向は逆方向であり、往復回数が偶数であれば、初期方向は順方向である。
【００４０】
経路の絞り込み処理は、往復回数を指定する経路の絞り込みと、完全な収束による経路の絞り込みで、処理が異なる。以下、それぞれについて説明する。
まず、往復回数を指定する経路（始点）の絞り込み処理は、数１１にしたがう。
【数１１】
0005577948.tif 000013
【００４１】
次に、完全な収束による経路（始点）の絞り込み処理は、数１２にしたがう。
【数１２】
0005577948.tif 000014
以上のようにして、始点のセットＳを得る。なお、第Ａ−２の実施の形態（図１３）の経路選択モジュール１３２０は、数１２の処理の後に、数１３としてＰ’を出力する。
【数１３】
0005577948.tif 000015
なお、順方向が上方向であればｙ＝０であり、下方向であればｙ＝ｈ−１である。
数１２内の３行目の式は、ある方向の始点（Ａ）に対する終点（Ｂ）を、逆方向の始点（Ｂ）とした場合に、その結果である経路の終点が（Ａ）となることを示している。
【００４２】
＜第Ａ−４の実施の形態＞
複数回の往復により、経路を絞り込む構成のうち、逐次、必要な経路情報を算出する構成を第Ａ−４の実施の形態（図１５）、第Ａ−５の実施の形態（図１６）に示す。第Ａ−４の実施の形態は逐次経路を算出する構成であり、第Ａ−５の実施の形態は逐次始点を算出し、最後に経路を算出する構成である。
第Ａ−４の実施の形態、第Ａ−５の実施の形態に示す構成は、逐次、必要な経路情報を算出するため、ワークメモリの削減を図る場合に用いられるものである。
第Ａ−４の実施の形態は、順方向経路算出モジュール１５１０、逐次経路選択モジュール１５２０、逆方向経路終点算出モジュール１５３０を有している。
なお、開始要求（図１５の例に示す１５０２、図１６の例に示す１６０２）とは、初期の始点のセットである。
【００４３】
第Ａ−４の実施の形態は、以下の処理を行う。
＜＜ｓｔｅｐ１．＞＞
往復回数をＲとする。
逐次経路選択モジュール１５２０は、順方向経路算出モジュール１５１０、逆方向経路終点算出モジュール１５３０と接続されており、以下の処理を行う。
Ｒが偶数ならば、順方向経路算出モジュール１５１０に始点１５２１を出力し、ｓｔｅｐ２．へ進む。
そうでなければ、Ｒ←Ｒ−１として、逆方向経路終点算出モジュール１５３０に始点１５２２を出力し、ｓｔｅｐ４．へ進む。
＜＜ｓｔｅｐ２．＞＞
順方向経路算出モジュール１５１０は、逐次経路選択モジュール１５２０と接続されており、画像１５０１を解析することによって、受け付けたすべての始点１５２１の経路１５１１を算出し、逐次経路選択モジュール１５２０へ出力する。
【００４４】
＜＜ｓｔｅｐ３．＞＞
逐次経路選択モジュール１５２０は、Ｒ＝０であれば、受け付けた経路１５１１を分離経路１５９９として出力し、終了する。
そうでなければ、Ｒ←Ｒ−２として、受け付けた経路１５１１の始点を終点として、逆方向経路終点算出モジュール１５３０に始点１５２２を出力する。
＜＜ｓｔｅｐ４．＞＞
逆方向経路終点算出モジュール１５３０は、逐次経路選択モジュール１５２０と接続されており、画像１５０１を解析することによって、受け付けたすべての始点１５２２の経路の終点１５３１を算出し、逐次経路選択モジュール１５２０へ出力する。
＜＜ｓｔｅｐ５．＞＞
逐次経路選択モジュール１５２０は、受け付けた終点１５３１を始点として、順方向経路算出モジュール１５１０に出力し、ｓｔｅｐ２．へ進む。
【００４５】
＜第Ａ−５の実施の形態＞
図１６は、第Ａ−５の実施の形態の構成例についての概念的なモジュール構成図である。第Ａ−５の実施の形態は、順方向経路終点算出モジュール１６１０、逐次始点選択モジュール１６２０、逆方向経路終点算出モジュール１６３０、順方向経路算出モジュール１６４０を有している。
【００４６】
第Ａ−５の実施の形態は、以下の処理を行う。
＜＜ｓｔｅｐ１．＞＞
往復回数をＲとする。
逐次始点選択モジュール１６２０は順方向経路終点算出モジュール１６１０、逆方向経路終点算出モジュール１６３０、順方向経路算出モジュール１６４０と接続されており、以下の処理を行う。
Ｒが偶数ならば、順方向経路終点算出モジュール１６１０に始点１６２１を出力し、ｓｔｅｐ２．へ進む。
そうでなければ、Ｒ←Ｒ−１として、逆方向経路終点算出モジュール１６３０に始点１６２２を出力し、ｓｔｅｐ４．へ進む。
＜＜ｓｔｅｐ２．＞＞
順方向経路終点算出モジュール１６１０は、逐次始点選択モジュール１６２０と接続されており、画像１６０１を解析することによって、受け付けたすべての始点１６２１の経路の終点１６１１を算出し、逐次始点選択モジュール１６２０へ出力する。
【００４７】
＜＜ｓｔｅｐ３．＞＞
逐次始点選択モジュール１６２０は、Ｒ＝０であれば、受け付けた終点１６１１を始点１６２３として順方向経路算出モジュール１６４０へ出力し、ｓｔｅｐ６．へ進む。
そうでなければ、Ｒ←Ｒ−２として、受け付けた経路の終点１６１１を始点として、逆方向経路終点算出モジュール１６３０に始点１６２２を出力する。
＜＜ｓｔｅｐ４．＞＞
逆方向経路終点算出モジュール１６３０は、逐次始点選択モジュール１６２０と接続されており、画像１６０１を解析することによって、受け付けたすべての始点１６２２の経路の終点１６３１を算出し、逐次始点選択モジュール１６２０へ出力する。
＜＜ｓｔｅｐ５．＞＞
逐次始点選択モジュール１６２０は、受け付けた終点１６３１を始点１６２１として、順方向経路終点算出モジュール１６１０に出力し、ｓｔｅｐ２．へ進む。
＜＜ｓｔｅｐ６．＞＞
順方向経路算出モジュール１６４０は、逐次始点選択モジュール１６２０と接続されており、受け付けたすべての始点１６２３の経路を作成し、分離経路１６９９として出力し、終了する。
【００４８】
＜部分画像を出力する実施の形態＞
前述の実施の形態により算出した分離経路により、画像分離を行う構成を図１７、図１８、図１９、図２０の例に示す。これらの構成は、文字列画像から単文字どうしを分離し、単文字画像として出力しようとする構成である。図１７、図１８、図１９、図２０において、経路抽出モジュールとは、第Ａ−１の実施の形態（図１２）、第Ａ−２の実施の形態（図１３）、第Ａ−３の実施の形態（図１４）、第Ａ−４の実施の形態（図１５）、第Ａ−５の実施の形態（図１６）の構成である。そして、この出力した単文字画像を、例えば文字画像認識装置等によって処理させる。
【００４９】
図１７は、経路抽出モジュール１７２０を組み込んだ画像処理装置の構成例についての概念的なモジュール構成図である。この実施の形態は、分離経路によって、画像を分離し、部分画像を出力するものであり、画像分離モジュール１７１０、経路抽出モジュール１７２０を有している。
画像分離モジュール１７１０は、経路抽出モジュール１７２０と接続されており、文字列画像である画像１７０１を受け付け、その画像１７０１を経路抽出モジュール１７２０から受け取った分離経路１７２１にしたがって、単文字画像の領域に分離して、部分画像１７９９として出力する。
【００５０】
図１８は、経路抽出モジュール１８３０を組み込んだ画像処理装置の構成例についての概念的なモジュール構成図である。この実施の形態は、画像分離モジュール１８１０、画像分離モジュール１８２０、経路抽出モジュール１８３０を有している。
画像分離モジュール１８１０は、画像分離モジュール１８２０、経路抽出モジュール１８３０と接続されており、経路抽出モジュール１８３０の前処理として、分離候補領域抽出を行うものである。例えば、画像１８０１から文字画像だけを部分画像１８１１として取り出すものである。また、投影情報等を利用する従来技術で分離可能な単文字画像の分離を行い、分離できなかったもの（部分画像１８１１）を経路抽出モジュール１８３０に渡す。
画像分離モジュール１８２０は、画像分離モジュール１８１０、経路抽出モジュール１８３０と接続されており、画像分離モジュール１８１０から受け取った部分画像１８１１を経路抽出モジュール１８３０から受け取った分離経路１８３１にしたがって、単文字画像の領域に分離して、部分画像１８９９として出力する。なお、画像分離モジュール１８１０も単文字画像を分離する場合は、画像分離モジュール１８１０から画像分離モジュール１８２０へ渡す部分画像１８１１には、画像分離モジュール１８１０が分離した領域の単文字画像（経路抽出モジュール１８３０による処理の対象外の画像）も含まれ、それはそのまま部分画像１８９９として出力する。
【００５１】
図１９は、経路抽出モジュール１９３０を組み込んだ画像処理装置の構成例についての概念的なモジュール構成図である。この実施の形態は、画像分離モジュール１９１０、経路判定モジュール１９２０、経路抽出モジュール１９３０を有している。
経路判定モジュール１９２０は、画像分離モジュール１９１０、経路抽出モジュール１９３０と接続されており、経路抽出モジュール１９３０の出力する分離経路１９３１について、その経路によって正しい分離ができるか否かを判別する処理を行う。複数の分離経路間の出現間隔が他の分離経路間の出現間隔と比べて狭い場合（例えば、漢字構成としての偏、旁等）など、意味のない分離経路を棄却するものである。その判別の際に、画像１９０１を利用してもよい。
画像分離モジュール１９１０は、経路判定モジュール１９２０と接続されており、画像１９０１を経路判定モジュール１９２０から受け取った分離経路１９２１にしたがって、単文字画像の領域に分離して、部分画像１９９９として出力する。
【００５２】
図２０は、経路抽出モジュール２０４０を組み込んだ画像処理装置の構成例についての概念的なモジュール構成図である。この実施の形態は、画像分離モジュール２０１０、画像分離モジュール２０２０、経路判定モジュール２０３０、経路抽出モジュール２０４０を有している。これは、図１８、図１９の両者の例を組み合わせた構成である。
画像分離モジュール２０１０は、画像分離モジュール２０２０、経路判定モジュール２０３０、経路抽出モジュール２０４０と接続されており、図１８の例に示した画像分離モジュール１８１０と同等の処理を行う。
経路判定モジュール２０３０は、画像分離モジュール２０１０、画像分離モジュール２０２０、経路抽出モジュール２０４０と接続されており、図１９の例に示した経路判定モジュール１９２０と同等の処理を行う。
画像分離モジュール２０２０は、画像分離モジュール２０１０、経路判定モジュール２０３０と接続されており、図１９の例に示した画像分離モジュール１９１０と同等の処理を行う。ただし、対象とする画像は画像分離モジュール２０１０から受け取った部分画像２０１１である。
【００５３】
前述の実施の形態内で経路を算出する処理（例えば、第Ａ−１の実施の形態（図１２）内の順方向経路算出モジュール１２１０、逆方向経路終点算出モジュール１２２０等が行う処理）について、具体的に示した実施例を以下に説明する。
図１の例に示す最短経路について、図２１の例に示す最短経路を用いて、始点の異なる複数の最短経路情報を同時に算出する実施例を示す。なお、最短経路の算出法は、Ｄｉｊｋｓｔｒａ法など、いくつか選択肢がある。
図２１の例に示す最短経路について説明する。
あるピクセルを親として、終点方向（図２１では上方向）に隣り合うピクセル、及び、終点方向とは斜め４５度に存在するピクセルの３つのピクセルを子とする木構造を対象とする。この構造を繰り返し、図２１の例に示すように、画像２１００の端部のあるピクセル（始点２１１１）を根として、もう片方の端部（終点２１２１等）を葉として、画像高さが木の高さとなるような木を抽出する。
本実施の形態における最短経路とは、前述の木について、根から葉へ向かうすべての経路のうち経路上のピクセル（すなわち、節）の輝度値の累積値であるコストが最小又は最大である経路をさす。根が始点であり、また、葉が終点である。
【００５４】
まず、基本的な最短経路の算出処理例を数１４のアルゴリズムに示す。また、参考のため、図２２の例に処理対象の位置関係を示す。
この実施例は後方帰納的な処理であり、図２１の例に示す木の最短経路の探索法である。ただし、経路のコストは辺でなく節にある。＜ｓｔｅｐ２．画像解析＞と、＜ｓｔｅｐ３．経路作成＞とは、画像上の位置について処理を行う順序が逆であることに注意が必要である。この処理は、上方向の最短経路を算出する処理であるが、下方向はもちろんのこと、あらゆる方向に適用できることは明らかである。
なお、本処理は、「順方向経路算出」に相当する。また、ｓｔｅｐ３．以降が、「順方向経路作成」に相当する。
【数１４】
0005577948.tif 000016
【００５５】
また、経路の終点のみを出力する場合、ｐ（ｈ−１）を参照してもよいが、ワークメモリを省略するために、ｓｔｅｐ３．以降を数１５のアルゴリズムのようにしてもよい。なお、本処理は、「順方向経路終点算出」、「逆方向経路終点算出」に相当する。
【数１５】
0005577948.tif 000017
【００５６】
また、経路の始点終点表を算出する場合も、同様に数１６のアルゴリズムのようにしてもよい。なお、本処理は、「順方向経路始点終点表算出」、「逆方向経路始点終点表算出」に相当する。
【数１６】
0005577948.tif 000018
ただし、各符号等の意味は、数１７に示す通りである。
【数１７】
0005577948.tif 000019
【００５７】
また、前述の処理において、数１８、数１９の保持の方法に注意が必要である。
【数１８】
0005577948.tif 000020
【数１９】
0005577948.tif 000021
すなわち、数１８、数１９が保持する数値の個数は、画像サイズよりも小さな個数でよい。
具体的には、数１８は経路のコストに関する情報であり、ラインバッファである。処理においては、直前のラインのみ参照できればよく、数１８の保持部は２つのラインバッファでよい。また、数１９は経路の移動に関する情報であるが、処理において、経路が存在しない領域が逐次判明する。この領域分、保持する領域を逐次削減してもよい。
さらに、始点が指定された場合、図２３の例に示すように、前述の木構造を構成することから、最短経路を算出するために必要な情報は、画像サイズよりも小さいことがあり、数１８、数１９を保持する領域をさらに削減してもよい。なお、図２３の例は、画像２３００において、始点２３１１、始点２３１２とした場合、色付のピクセルは、解析において参照する必要があるピクセルであり、白色のピクセルは、解析において必ずしも参照する必要がないピクセルであることを示している。
【００５８】
＜実験結果Ａ＞
前述の実施の形態による実験結果を図２４、図２５、図２６を用いて説明する。
図２４は、対象とする画像（「Ｃｈａｒａｃｔｅｒ」の文字画像）の例を示す説明図である。図２５は、本実施の形態が対象とする画像を分離した例を示す説明図である。図２６は、対象とする画像の投影情報の例を示す説明図である。
【００５９】
これらについて、次の３つの観点から説明する。
（１）投影情報では分離できない文字画像間の間隙である領域であっても分離している。
対象画像内の“ｔｅｒ”の文字画像部分（図２４の例参照）については、図２６の例に示すように投影情報２６００では分離困難な文字画像間の間隙である。つまり、従来技術で投影情報を利用して分離しようとしても、図２６の例に示すように投影情報２６００には明確な谷がないため分離することは困難である。
このような画像に対して、本実施の形態は、図２５の例に示すように文字画像の周囲を通るような形状の分離経路を算出している。
（２）連結成分を分離している。
対象画像内の“ｈａｒ”、“ａｃｔ”及び“ｅｒ”の文字画像部分（図２４の例参照）について、隣り合う文字画像と連結している部分がある。
図２５の例に示すように、本実施の形態により、連結する文字画像をも分離している。前述したように最短経路による画像分離の仕組みにより、最短経路が移動可能な範囲内でコスト最小又はコスト最大の分離経路を算出しているからである。
（３）多値画像に対応している。
図２４の例に示す画像２４００は多値画像である。前述の実施の形態による処理は、２値画像を含む、多値画像に対応するものである。これにより、例えば、２値化に伴う、受け付けた画像毎の閾値設定を行う必要がなくなる。
【００６０】
なお、＜Ａ＞に記載の発明は、以下のように捉えることができる。
（Ａ１）  画像内から領域を分離するための第１の経路を示す情報である第１の経路情報を算出する第１の経路情報算出手段と、
前記第１の経路とは逆方向の経路であって、前記画像内から前記領域を分離するための第２の経路を示す情報である第２の経路情報を算出する第２の経路情報算出手段と、
前記第１の経路情報算出手段によって算出された第１の経路情報、前記第２の経路情報算出手段によって算出された第２の経路情報のいずれかを選択する経路選択手段
を具備することを特徴とする画像処理装置。
（Ａ２）  前記第１の経路及び前記第２の経路は、該経路上の画素の輝度値の累積値が予め定めた条件を満たす場合の経路である
ことを特徴とする（Ａ１）に記載の画像処理装置。
（Ａ３）  前記第２の経路情報算出手段は、前記第１の経路情報算出手段によって算出された第１の経路情報に基づいて、前記第２の経路情報を算出し、
前記第１の経路情報算出手段は、２回目以降の処理においては、前記第２の経路情報算出手段によって算出された第２の経路情報に基づいて、前記第１の経路情報を算出する
ことを特徴とする（Ａ１）又は（Ａ２）に記載の画像処理装置。
（Ａ４）  前記第１の経路情報算出手段による処理と前記第２の経路情報算出手段による処理は、該処理が予め定められた回数行われること、又は、前記第１の経路情報算出手段によって算出された第１の経路情報と前記第２の経路情報算出手段によって算出された第２の経路情報が合致すること、を終了の条件とする
ことを特徴とする（Ａ３）に記載の画像処理装置。
【００６１】
＜Ｂ＞
次に、＜Ａ＞に示した技術を前提とした実施の形態を説明する。ただし、分離経路の特徴として、「特開平０４−１００８９」に記載の技術に基づいて算出された分離経路を利用してもよい。
＜Ｂ＞の実施の形態の概要を説明する。本実施の形態では、投影分布又は連結成分を利用せず、分離経路を利用する。ここでの分離経路とは、前述した＜Ａ＞のものと同等である。なお、＜Ａ＞は、文字列の画像を受け付け、単文字又は準文字である部分画像を出力するための分離経路の算出に関するものであるが、＜Ｂ＞の実施の形態では、受け付けた文書の画像を、分離経路によって文字列である部分画像に分離して出力するものである。
【００６２】
＜Ｂ＞の実施の形態における分離経路は、経路上のコスト（すなわち、画素の輝度値の累積値）を最小又は最大とするように算出される。これに伴い、投影分布に現れない文字列どうしの分離境界を特定し、文字間に生じている連結を分離して、文字列どうしの分離境界を特定する。
また、段落を構成する文字列の方向は未知であるとき、これを判別する必要がある。＜Ｂ＞の実施の形態では、複数方向の分離経路を比較することで、文字列の方向を判別する。
文書の画像について、前述の分離経路を算出したとき、以下のような性質がある。
（１）正しい方向の分離経路は、誤った方向の分離経路に対して、歪曲が小さい。
（２）分離経路による分離が行われない（分離経路の数が２以下）場合、単文字又は単文字列である。
【００６３】
＜Ｂ＞に示す実施の形態は、画像内の文字の領域を分離する（以下、切り出しともいう）画像処理装置に関するものである。特に、文字認識技術の分野に利用される装置であり、対象とする文書の画像に含まれる文字列の方向を判別すること、文字列の画像を分離する装置に属する。
なお、以降の説明のため、文字認識の技術分野について補足する。文字認識における文字の分離技術を、便宜的に以下のように分類する。
（１）領域（文字領域、非文字領域）の属性判別及び分離
画像内の領域が文字領域であるか、文字ではない領域であるかを判別し、その領域を分離する。
（２）文字列領域の方向判別及び分離
画像（文字領域を含む）内から文字領域内の文字列の領域の方向（縦書き、横書き）を判別し、その文字列の領域を分離する。
（３）単文字領域の分離
画像（文字領域、文字列領域を含む）内から一文字ずつ分離する。
【００６４】
＜Ｂ＞に示す実施の形態は、特に前記（２）に属するものである。
さらに、前記（２）には２つの技術がある。すなわち、以下のことである。
Ａ）文字列の方向判別
Ｂ）文字列（領域）の分離
文字列の方向が未知の場合、前記（２）の性能は、すなわち、前記Ａ），Ｂ）の直列の性能である。＜Ｂ＞に示す実施の形態は、Ａ），Ｂ）を併合したものである。
また、分離経路を求める方向は、横方向（以下、水平方向ともいう。ただし、厳密な水平でなくてもよい）と縦方向（以下、垂直方向ともいう。ただし、厳密な垂直でなくてもよい）の２つとする。なお、分離経路とは、画像内の文字画像を分離する線分である。
【００６５】
本実施の形態は、分離経路の特徴量に基づいて、諸々の判別を行う。以下、分離経路の特徴量について説明する。
分離経路の特徴量は、その本数、個々の位置と形状、経路上の画素の輝度値（以下、画素の輝度値を画素値ともいう）から算出される。これらを表２に例示する。また、対応する記号を定義する。ここで、ｉは経路の本数に関係するインデックスである。
【表２】
0005577948.tif 000022
【００６６】
以下、表２に例示する特徴量についてそれぞれ説明する。
まず、特徴量「Ｎｕｍ」について、これは、分離経路の本数そのものを指す。
次に、特徴量「Ｃｕｒｌｉ」について、これは、分離経路ｉの形状の歪曲の度合いを表す値である。ただし、ｉ≦Ｎｕｍである。ここで、歪曲とは、分離経路ｉの始点と終点から導かれる直線と、分離経路ｉとの差分値である。前者（分離経路ｉの始点と終点から導かれる直線）をｆｉ（ｘ）、後者（分離経路ｉ）をｐｉ（ｘ）とすれば、歪曲とは、Σｘ｜ｆｉ（ｘ）−ｐｉ（ｘ）｜ｄｘ、Ｍａｘ（｜ｆｉ（ｘ）−ｐｉ（ｘ）｜）、又は、Σｘ（ｆｉ（ｘ）−ｐｉ（ｘ））２ｄｘ等となる。
次に、特徴量「Ｔｈｉｃｋｉ」について、これは、分離経路ｉの太さを表す。文字列分離の目的においては、隣接する文字列どうしの間隙に相当する。ただし、ｉ≦Ｎｕｍである。
次に、特徴量「Ｃｏｓｔｉ」について、これは、分離経路の算出により定義されるコストそのものである。又は、別途、分離経路ｉ上の画素値の累積値を求めてもよい。ただし、ｉ≦Ｎｕｍである。
さらに、前記の特徴量について、方向（水平、垂直）毎に分離経路の長さが異なるため、前記特徴量を分離経路の長さで正規化するようにしてもよい。
＜Ｂ＞に示す実施の形態では、「経路の特徴量算出処理」において、前記特徴量を算出するものとする。
【００６７】
＜Ｂ−１．１  分離経路の算出における、予め定められた区間の解析単位について＞
図２７を用いて説明する。図２７は、分離経路の算出処理の例を示す説明図である。
＜Ａ＞に示した分離経路の算出、又は「特開平０４−１００８９」に記載の分離経路の算出は、分離経路の移動範囲内において、Ｃｏｓｔｉが最小又は最大となる経路を算出するものである。このとき、分離経路の長さが長いほど、分離経路の移動範囲は広くなる。分離経路の移動範囲が必要以上に広い場合、図２７（ａ）に例示するように、局所の障害物パタン（障害物パタン２７３１〜障害物パタン２７４７、具体的な例として文字画像等がある）の存在が、分離経路の算出に大きな影響を与える。つまり、文字列の切り出しの目的から前記のことが分離の精度に消極的な影響を与えることがある。例えば、図２７（ａ）に例示するように、障害物パタン２７３６と障害物パタン２７４５は、ノイズ、書き込み等によって領域が接触してしまっているため、Ｃｏｓｔｉが最小又は最大となる経路は、始点２７１１から上側の経路を通って始点２７１１へとつながる。
【００６８】
そこで、分離経路の算出において、対象とする画像内の文字画像の一部を含む予め定められた範囲内において、経路上にある画素値の累積値が予め定められた条件を満たす分離経路を算出する。具体的には、図２７（ｂ）に例示するように、対象画像を予め定められた区間の解析単位に分割し、ある区間の分離経路の終点を隣接する次の区間の始点として（例えば、領域２７５１における終点である中間点２７６２を、領域２７５２における始点としている）、次の区間の分離経路を求めることを繰り返すことで、分離経路の移動範囲を狭め、局所の障害物パタンの存在が分離経路の算出に与える影響を低減する。したがって、領域２７５４では、障害物パタン２７３６と障害物パタン２７４５の接触を横切って分離経路が算出され、分離経路の直進性を調節する。なお、予め定められた範囲としての領域２７５１等の大きさは、等分としてもよいし、それぞれ異なる大きさとしてもよい。例えば、対象とする画像に存在する文字のサイズを計測し、その文字サイズの倍数に基づいて領域２７５１等の大きさを定めるようにしてもよいし、文字が予め定められた個数分含まれるように領域２７５１等の大きさを定めるようにしてもよい。
特に、＜Ａ＞に示した技術では、分離経路の算出過程において、Ｃｏｓｔｉに関するラインバッファを持つが、このとき、予め定められた長さ毎に前記ラインバッファを初期化するだけで、同等の処理が得られる。
【００６９】
＜Ｂ−１．２  複数の等価な分離経路の結合について＞
＜Ａ＞に記載した技術のように分離経路を算出した後、複数の等価な分離経路を結合する。
ここで、複数の等価な分離経路を結合するには、分離経路の算出において、隣り合う分離経路どうしの間隙の幅が予め定められた条件を満たす場合に、その間隙にある画素の輝度値によらず、その隣り合う分離経路は等価であると判断し、結合する。又は、分離経路の算出において、隣り合う分離経路どうしの間隙にある画素の輝度値の累積値が予め定められた条件を満たす場合に、その隣り合う分離経路は等価であると判断し、結合する。
【００７０】
図２８を用いて説明する。図２８は、分離経路の結合処理の例を示す説明図である。隣接する２つの分離経路どうしについて、その間隙の障害物パタンによって、隣り合う分離経路は、分離の目的から等価なものであり、これを単一の分離経路として結合する。図２８では、分離経路２８１１〜分離経路２８１５を結合して分離経路２８５１にし、分離経路２８１６〜分離経路２８１９を結合して分離経路２８５２にし、分離経路２８２０と分離経路２８２１を結合して分離経路２８５３にし、分離経路２８２２、分離経路２８２３には他に等価な分離経路がないので、他の分離経路とは結合していない。なお、結合された分離経路は、１［ｐｉｘｅｌ］以上の太さを持つ。障害物パタン２８３１〜障害物パタン２８３７のうち、障害物パタン２８３４はノイズである。
【００７１】
図２９を用いて説明する。図２９は、分離経路の結合処理の例を示す説明図である。結合後の分離経路をｐａｔｈｉとして、ｐａｔｈｉ  ＝  （ｔｏｐ＿ｐａｔｈｉ，ｂｏｔｔｏｍ＿ｐａｔｈｉ）と、分離経路の輪郭線である２つの分離経路で表す。このとき、結合前の分離経路をｓｒｃ＿ｐａｔｈｊとすると、ｔｏｐ＿ｐａｔｈｉ，ｂｏｔｔｏｍ＿ｐａｔｈｉは、ｓｒｃ＿ｐａｔｈｊを指すものとなる。３つ以上の分離経路の結合においては、端部でない分離経路（図２９の例では、分離経路２９１２であるｓｒｃ＿ｐａｔｈｊ−１）が消去される。結合され、太さを持つｐａｔｈｉは、「ｔｏｐ＿ｐａｔｈｉ  ≠  ｂｏｔｔｏｍ＿ｐａｔｈｉ」である。また、そうでないｐａｔｈｉは、「ｔｏｐ＿ｐａｔｈｉ  ＝  ｂｏｔｔｏｍ＿ｐａｔｈｉ」である。なお、横方向の分離経路であるので、上端（ｔｏｐ）、下端（ｂｏｔｔｏｍ）の分離経路で示したが、縦方向の分離経路の場合は右端、左端の分離経路となる。
図２９の上側の３本の分離経路（分離経路２９１１〜分離経路２９１３）を結合した分離経路２９５１は、（２０）式のように表現される。すなわち、分離経路の輪郭線の情報で表現される。
【数２０】
0005577948.tif 000023
また、図２９の下側の１本の分離経路（分離経路２９１４）は結合していないが、結合の表記に合わせると、（２１）式のように表現される。
【数２１】
0005577948.tif 000024
【００７２】
ここで、隣り合う分離経路の間隙の広さが予め定められた条件を満たす場合（例えば、予め定められた量以下）であれば、障害物パタンの有無に限らず、分離経路を結合するようにしてもよい。また同様に、隣り合う分離経路の間隙のコスト（画素値の累積値）が予め定められた条件を満たす場合（例えば、予め定められた量以下）であれば、分離経路を結合するようにしてもよい。
また、分離経路の結合と特徴量の算出とを併合してもよい。例えば、ｐａｔｈｉは、ｎ個のｓｒｃ＿ｐａｔｈｊを結合したものとすれば、後述する特徴量であるＴｈｉｃｋｉをｎとするようにしてもよい。
【００７３】
＜Ｂ−１．３  分離経路の特徴量について＞
前述の分離経路の定義に基づいて、表２に示す分離経路の特徴量の具体例を示す。
以下では、簡単のため、横方向の分離経路について説明する。縦方向の分離経路については、上端を右端、下端を左端と読み替えることによって対応できる。以下、経路の始点を（ｘｓ，  ｙｓ）、終点を（ｘｅ，  ｙｅ）とし、ｘｓ  ＜  ｘｅであるとする。なお、分離経路ｉについて、水平位置ｘにおける垂直位置ｙを「ｔｏｐ＿ｐａｔｈｉ（ｘ），  ｂｏｔｔｏｍ＿ｐａｔｈｉ（ｘ）」とする。また、水平位置ｘ、垂直位置ｙにおける、対象画像の画素値をｉｍｇ（ｘ，  ｙ）とする。ここでは、簡単のため、ｉｍｇ（ｘ，  ｙ）の値が大きいほど、障害物パタンであるとする。
【００７４】
まず、特徴量「Ｎｕｍ」は、結合後の分離経路の本数である。
次に、特徴量「Ｃｕｒｌｉ」は、（２２）式、（２３）式、（２４）式、（２５）式等を用いて抽出する。
【数２２】
0005577948.tif 000025
【数２３】
0005577948.tif 000026
【数２４】
0005577948.tif 000027
【数２５】
0005577948.tif 000028
次に、特徴量「Ｔｈｉｃｋｉ」は、（２６）式、（２７）式、（２８）式等を用いて抽出する。
【数２６】
0005577948.tif 000029
【数２７】
0005577948.tif 000030
【数２８】
0005577948.tif 000031
次に、特徴量「Ｃｏｓｔｉ」は、（２９）式、（３０）式、（３１）式等を用いて抽出する。
【数２９】
0005577948.tif 000032
【数３０】
0005577948.tif 000033
【数３１】
0005577948.tif 000034
【００７５】
前記の特徴量について、図３０を用いて説明する。図３０は、（２２）式、（２６）式の特徴量を主として説明している。つまり、図３０の例に示す分離経路３０１１の特徴量であるＴｈｉｃｋｉは、（２２）式を用いて抽出し、分離経路３０１２の特徴量であるＣｕｒｌｉ＋１は、（２６）式を用いて抽出している。分離経路３０１１は１以上の太さを持ち、分離経路３０１２は１の太さを持つ。
Ｃｕｒｌｉについて、分離経路３０１２を用いて説明する。図３０の例では実線の分離経路３０１２に対して、その始点と終点を通る直線ｆ（ｘ）（（３２）式）との差分（射線部の面積）を、分離経路３０１２の長さ（＝  ｘｅ−ｘｓ）で正規化したものである。
【数３２】
0005577948.tif 000035
【００７６】
Ｃｕｒｌｉについては、（２２）式、（２３）式、（２４）式のように、始点と終点を結ぶ直線との差分を評価するようにしてもよい。具体的には、（２２）式は太さを持たない経路と前記直線との差分の絶対値、（２３）式は太さを持たない経路と前記直線との差分の２乗誤差、（２４）式は太さを持つ経路について中心線を算出した場合の（２２）式と同様の差分の絶対値である。また、（２５）式のように、経路そのものの微分値を（微分距離ｄ［ｐｘ］）評価するようにしてもよい。
Ｔｈｉｃｋｉについては、（２６）式、（２７）式、（２８）式のように、最大値、最小値、又は、平均値を用いるようにしてもよい。
【００７７】
Ｃｏｓｔｉについては、（２９）式、（３０）式のように、経路上の画素値の累積値を評価するようにしてもよい。具体的には、（２９）式は、経路上の画素値の累積値を評価する例である。（３０）式は、経路の中心線上の画素値の累積値を評価する例である。さらに、（３１）式のように、経路の湾曲によって、重みづけをした経路上の画素値の累積値を評価するようにしてもよい。つまり、経路上にある画素の輝度値と経路の移動に基づく重み係数との積の累積値が予め定められた条件を満たす分離経路を算出するようにしてもよい。重み係数は、ｐｉ（ｘ）とｐｉ（ｘ＋１）との関係に基づいて定まる。具体的には、両方が同じ場合（つまり、直線の場合）は重み係数（ｃｉ）を１とし、異なる場合（つまり、斜線の場合）は重み係数（ｃｉ）ｃ（１より大きい値）とする。
【００７８】
＜Ｂ−２  実施の形態＞
ここでは、文書の画像を対象とし、文字列の分離、文字列の方向判別を行う実施の形態を説明する。
＜第Ｂ−１の実施の形態＞
文書の画像を受け付け、文字列の分離を行う実施の形態を説明する。
第Ｂ−１の実施の形では、受け付ける文書の画像の文字列の方向は既知であるものとする。
【００７９】
図３１は、第Ｂ−１の実施の形態の構成例についての概念的なモジュール構成図である。第Ｂ−１の実施の形態の例は、既知である文字列方向の分離経路を算出し、この分離経路に基づいて、画像を分離し、出力するものであって、画像受付モジュール３１１０、分離経路算出モジュール３１２０、画像分離モジュール３１３０を有している。
【００８０】
画像受付モジュール３１１０は、分離経路算出モジュール３１２０、画像分離モジュール３１３０と接続されている。画像３１００を受け付けて、その画像を分離経路算出モジュール３１２０、画像分離モジュール３１３０へ渡す。画像を受け付けるとは、例えば、スキャナ、カメラ等で画像を読み込むこと、ファックス等で通信回線を介して外部機器から画像を受信すること、ハードディスク（コンピュータに内蔵されているものの他に、ネットワークを介して接続されているもの等を含む）等に記憶されている画像を読み出すこと等が含まれる。画像は、２値画像、多値画像（カラー画像を含む）であってもよい。受け付ける画像は、１枚であってもよいし、複数枚であってもよい。また、画像の内容として、少なくとも文字画像が含まれていれば、ビジネスに用いられる文書、広告宣伝用のパンフレット等であってもよい。
【００８１】
分離経路算出モジュール３１２０は、画像受付モジュール３１１０、画像分離モジュール３１３０と接続されている。分離経路算出モジュール３１２０は、画像受付モジュール３１１０によって受け付けられた画像に対して、その画像内の文字画像を分離する分離経路を算出する。例えば、＜Ａ＞、＜Ｂ−１．１  分離経路の算出における、予め定められた区間の解析単位について＞、＜Ｂ−１．２  複数の等価な分離経路の結合について＞に示した技術を適用して実現される。なお、画像受付モジュール３１１０によって受け付けられた画像の文字列方向は既知であるので、その方向の分離経路を算出すればよい。
【００８２】
画像分離モジュール３１３０は、画像受付モジュール３１１０、分離経路算出モジュール３１２０と接続されている。画像分離モジュール３１３０は、分離経路算出モジュール３１２０によって算出された分離経路により、画像受付モジュール３１１０によって受け付けられた画像を複数の文字列の画像へ分離する。例えば、ｂｏｔｔｏｍ＿ｐａｔｈｉ−１とｔｏｐ＿ｐａｔｈｉの間隙の領域を分離する処理である。ここで、前記経路上に、障害物パタンが予め定められた量以上存在する場合、すなわち、Ｃｏｓｔｉ−１、又は、Ｃｏｓｔｉ−１が予め定められた量以上である場合、ｔｏｐ＿ｐａｔｈｉ−１とｔｏｐ＿ｐａｔｈｉ、ｂｏｔｔｏｍ＿ｐａｔｈｉ−１とｂｏｔｔｏｍ＿ｐａｔｈｉ、又は、ｔｏｐ＿ｐａｔｈｉ−１とｂｏｔｔｏｍ＿ｐａｔｈｉ  の間隙の領域を分離することで、出力される文字列の画像において、文字パタンの一部が失われないようにする。
【００８３】
＜第Ｂ−２の実施の形態＞
文書の画像を受け付け、文字列の方向判別を行う実施の形態を説明する。
図３２は、第Ｂ−２の実施の形態の構成例についての概念的なモジュール構成図である。第Ｂ−２の実施の形態の例は、水平方向、垂直方向の分離経路を算出し、それぞれの分離経路の特徴量を算出し、これらの特徴量を比較し、文字列の方向と状態を判別し、出力するものであって、画像受付モジュール３２１０、水平方向分離経路算出モジュール３２２０、垂直方向分離経路算出モジュール３２３０、経路特徴量算出モジュール３２４０、分離方向判別モジュール３２５０を有している。
【００８４】
画像受付モジュール３２１０は、水平方向分離経路算出モジュール３２２０、垂直方向分離経路算出モジュール３２３０と接続されており、第Ｂ−１の実施の形態における画像受付モジュール３１１０と同等の処理を行う。画像３２００を受け付け、水平方向分離経路算出モジュール３２２０、垂直方向分離経路算出モジュール３２３０に渡す。なお、画像３２００内の文字列の方向は既知ではない。したがって、複数方向（ここでは、水平方向と垂直方向）の分離経路を算出する必要がある。なお、ここでは、画像３２００は単段落の文書の画像であるとする。
【００８５】
水平方向分離経路算出モジュール３２２０は、画像受付モジュール３２１０、経路特徴量算出モジュール３２４０と接続されており、垂直方向分離経路算出モジュール３２３０は、画像受付モジュール３２１０、経路特徴量算出モジュール３２４０と接続されている。画像受付モジュール３２１０、水平方向分離経路算出モジュール３２２０は、第Ｂ−１の実施の形態における分離経路算出モジュール３１２０に該当し、複数方向の分離経路を算出し、その分離経路を経路特徴量算出モジュール３２４０へ渡す。
水平方向分離経路算出モジュール３２２０は、画像受付モジュール３２１０によって受け付けられた画像に対して、その画像内の文字画像を分離する横方向の線分である分離経路を算出する。例えば、＜Ａ＞、＜Ｂ−１．１  分離経路の算出における、予め定められた区間の解析単位について＞、＜Ｂ−１．２  複数の等価な分離経路の結合について＞に示した技術を適用して実現される。
垂直方向分離経路算出モジュール３２３０は、画像受付モジュール３２１０によって受け付けられた画像に対して、その画像内の文字画像を分離する縦方向の線分である分離経路を算出する。例えば、＜Ａ＞、＜Ｂ−１．１  分離経路の算出における、予め定められた区間の解析単位について＞、＜Ｂ−１．２  複数の等価な分離経路の結合について＞に示した技術を適用して実現される。
【００８６】
経路特徴量算出モジュール３２４０は、水平方向分離経路算出モジュール３２２０、垂直方向分離経路算出モジュール３２３０、分離方向判別モジュール３２５０と接続されている。水平方向分離経路算出モジュール３２２０、垂直方向分離経路算出モジュール３２３０によって算出された複数方向の分離経路の特徴量を算出し、その特徴量を分離方向判別モジュール３２５０へ渡す。例えば、経路特徴量算出モジュール３２４０は、前述した特徴量の算出、例えば、（２２）式、（２６）式、（２９）式と、これらの統計値の算出により、実現される。以下では、特徴量Ｆの最大値をＭａｘＦ、最小値をＭｉｎＦ、平均値をＡｖｇＦとする。例えば、歪曲の最大値であれば、ＭａｘＣｕｒｌとする。
【００８７】
分離方向判別モジュール３２５０は、経路特徴量算出モジュール３２４０と接続されている。経路特徴量算出モジュール３２４０によって算出された特徴量に基づいて、画像の分離方向及び文字画像の状態を判別し、その判別の結果によって複数方向の分離経路のうちの分離経路を選択する。具体的には、図３３に例示したフローチャートにしたがう。図３３は、分離方向判別モジュール３２５０が行う方向判別の処理の例を示すフローチャートである。
【００８８】
図３３に例示したフローチャートは、分離方向判別モジュール３２５０が表３、表４、表５、表６、表７を用いて判別を行う。以下、このことについて説明する。
【表３】
0005577948.tif 000036
【表４】
0005577948.tif 000037
【表５】
0005577948.tif 000038
【表６】
0005577948.tif 000039
【表７】
0005577948.tif 000040
【００８９】
分離方向判別モジュール３２５０では、水平方向分離経路算出モジュール３２２０、垂直方向分離経路算出モジュール３２３０から渡された横方向、縦方向の分離経路の特徴量を比較し、対象画像の分離方向（すなわち、出力する文字列の方向、以下、「方向」とする）と、対象画像の状態（以下、「状態」とする）を判別する。それぞれ、以下の値をとりうる変数である。
「方向」は、以下の３つの値をとりうる。
（１）Ｈ：水平
（２）Ｖ：垂直
（３）⊥：判別不能
また、「状態」は、以下の４つの値をとりうる。
（１）Ｐ：単段落
（２）Ｔ：単文字列
（３）Ｃ：単文字
（４）⊥：判別不能
【００９０】
図３３に例示するフローチャートにおける、表を用いた判別は、まず、表３を用いた判別により、対象画像が単文字か、単文字列か、それ以外かを判別する。これは、分離経路の本数Ｎｕｍによる判別により実現される。つまり、横方向の分離経路と縦方向の分離経路が２本であるならば、単文字（Ｃ）である。いずれか一方が２本であるならば、単文字列（Ｔ）であり、横方向の分離経路が２本であるならば、方向はは水平（Ｈ）であり、縦方向の分離経路が２本であるならば、方向は垂直（Ｖ）である。両方が２本でないならば、何もしない（状態は判別不能（⊥）のままである）。
表４、表５、表６、表７を用いた判別は、それぞれ、分離経路の特徴量によって、文字列の方向を判別するものである。
【００９１】
図３３に例示するフローチャートでは、順番として「Ｎｕｍによる判別」（表３）、「Ｃｕｒｌによる判別」（表４、表５）、「Ｔｈｉｃｋによる判別」（表６）、「Ｃｏｓｔによる判別」（表７）の順に判別を行う。以下、この順番について説明する。
まず、分離方向判別モジュール３２５０による方向判別は、分離経路の形状に基づいて文字列の方向を判別するものである。このため、形状の情報に基づく判別でない「Ｃｏｓｔによる判別」は、最も優先度の低い、最後段に設置する。
次に、形状の情報に基づく判別である「Ｃｕｒｌによる判別」、「Ｔｈｉｃｋによる判別」について、箇条書きのような配置に対応するためには、必ずしも、ＭａｘＴｈｉｃｋ又はＡｖｇＴｈｉｃｋが最大の方向が文字列の方向ではない場合があり得る。ゆえに、「Ｔｈｉｃｋによる判別」（表６）の前段に、「Ｃｕｒｌによる判別」（表４、表５）を設置する。
次に、「Ｃｕｒｌによる判別」について、対象となっている文書の画像によって、必ずしも、水平方向、垂直方向について、算出される分離経路の総数が同じであるとは限らない（すなわち、縦に長い横書き、又は、横に長い縦書き等があり得る）。ある方向の分離経路の平均値は、分離経路の総数に影響されるため、「ＡｖｇＣｕｒｌによる判別」（表５）の前段に、「ＭａｘＣｕｒｌによる判別」（表４）を設置する。
以上の設計は、複数の文字列によって構成されている文書の画像を想定した判別であるが、対象とする文書の画像は必ずしも複数の文字列によって構成されているとは限らない。このため、最前段に「Ｎｕｍによる判別」（表３）を設置し、対象となっている文書の画像が、単文字か、単文字列か、それ以外かを判別する。
【００９２】
ステップＳ３３０２では、「方向」変数に⊥（判別不能）を代入し、「状態」変数に⊥（判別不能）を代入する。
ステップＳ３３０４では、表３のＮｕｍによる判別を行う。
ステップＳ３３０６では、「状態」変数は判別不能（状態＝＝⊥）か否かを判断し、「状態」変数が判別不能の場合はステップＳ３３０８へ進み、それ以外の場合はステップＳ３３２２へ進む。
ステップＳ３３０８では、表４のＭａｘＣｕｒｌによる判別を行う。つまり、横方向のＭａｘＣｕｒｌが縦方向のＭａｘＣｕｒｌよりも小であるならば、方向は水平（Ｈ）であり、状態は単段落（Ｐ）である。横方向のＭａｘＣｕｒｌが縦方向のＭａｘＣｕｒｌよりも大であるならば、方向は垂直（Ｖ）であり、状態は単段落（Ｐ）である。それ以外（両方が同じ）ならば、何もしない（状態は判別不能（⊥）のままである）。
【００９３】
ステップＳ３３１０では、「状態」変数は判別不能（状態＝＝⊥）か否かを判断し、「状態」変数が判別不能の場合はステップＳ３３１２へ進み、それ以外の場合はステップＳ３３２２へ進む。
ステップＳ３３１２では、表５のＡｖｇＣｕｒｌによる判別を行う。つまり、横方向のＡｖｇＣｕｒｌが縦方向のＡｖｇＣｕｒｌよりも小であるならば、方向は水平（Ｈ）であり、状態は単段落（Ｐ）である。横方向のＡｖｇＣｕｒｌが縦方向のＡｖｇＣｕｒｌよりも大であるならば、方向は垂直（Ｖ）であり、状態は単段落（Ｐ）である。それ以外（両方が同じ）ならば、何もしない（状態は判別不能（⊥）のままである）。
【００９４】
ステップＳ３３１４では、「状態」変数は判別不能（状態＝＝⊥）か否かを判断し、「状態」変数が判別不能の場合はステップＳ３３１６へ進み、それ以外の場合はステップＳ３３２２へ進む。
ステップＳ３３１６では、表６のＡｖｇＴｈｉｃｋによる判別を行う。つまり、横方向のＡｖｇＴｈｉｃｋが縦方向のＡｖｇＴｈｉｃｋよりも大であるならば、方向は水平（Ｈ）であり、状態は単段落（Ｐ）である。横方向のＡｖｇＴｈｉｃｋが縦方向のＡｖｇＴｈｉｃｋよりも小であるならば、方向は垂直（Ｖ）であり、状態は単段落（Ｐ）である。それ以外（両方が同じ）ならば、何もしない（状態は判別不能（⊥）のままである）。
【００９５】
ステップＳ３３１８では、「状態」変数は判別不能（状態＝＝⊥）か否かを判断し、「状態」変数が判別不能の場合はステップＳ３３２０へ進み、それ以外の場合はステップＳ３３２２へ進む。
ステップＳ３３２０では、表７のＡｖｇＣｏｓｔによる判別を行う。つまり、横方向のＡｖｇＣｏｓｔが縦方向のＡｖｇＣｏｓｔよりも小であるならば、方向は水平（Ｈ）であり、状態は単段落（Ｐ）である。横方向のＡｖｇＣｏｓｔが縦方向のＡｖｇＣｏｓｔよりも大であるならば、方向は垂直（Ｖ）であり、状態は単段落（Ｐ）である。それ以外（両方が同じ）ならば、何もしない（状態は判別不能（⊥）のままである）。
ステップＳ３３２２では、「方向」変数と「状態」変数の組である（方向，状態）を出力する。
【００９６】
さらに、図３２に例示した構成に、画像分離モジュールを付加し、その画像分離モジュールは分離方向判別モジュール３２５０によって選択された分離経路により、画像受付モジュール３２１０によって受け付けられた画像を複数の部分画像へ分離するようにしてもよい。
【００９７】
＜第Ｂ−３の実施の形態＞
次に、文書の画像を受け付け、文字列の方向判別と、分離の処理を行う実施の形態を説明する。
図３４は、第Ｂ−３の実施の形態の構成例についての概念的なモジュール構成図である。第Ｂ−３の実施の形態は、水平方向、垂直方向の分離経路を算出し、これらを一旦保持し、それぞれの分離経路の特徴量を算出し、これらの特徴量を比較し、文字列の方向と状態を判別し、判別された方向の分離経路を選択し、これらに基づいて、画像分離を行うものであって、画像受付モジュール３２１０、水平方向分離経路算出モジュール３２２０、垂直方向分離経路算出モジュール３２３０、分離経路記憶モジュール３４３５、経路特徴量算出モジュール３２４０、分離方向判別モジュール３２５０、画像分離モジュール３４６０を有している。
【００９８】
なお、前述の実施の形態と同種の構成要素には同一符号を付し重複した説明を省略する。つまり、分離経路記憶モジュール３４３５と画像分離モジュール３４６０以外は、第Ｂ−２の実施の形態（図３２）の構成要素と同等である。
分離経路記憶モジュール３４３５は、水平方向分離経路算出モジュール３２２０、垂直方向分離経路算出モジュール３２３０、経路特徴量算出モジュール３２４０、画像分離モジュール３４６０と接続されており、水平方向分離経路算出モジュール３２２０、垂直方向分離経路算出モジュール３２３０によって算出された分離経路を記憶する。そして、その分離経路を経路特徴量算出モジュール３２４０又は画像分離モジュール３４６０へ渡す。
【００９９】
画像分離モジュール３４６０は、画像受付モジュール３２１０、分離経路記憶モジュール３４３５、分離方向判別モジュール３２５０と接続されている。
画像分離モジュール３４６０が行う判断、処理を表８に示す。
【表８】
0005577948.tif 000041
画像分離モジュール３４６０は、「方向」変数が判別不能（⊥）以外の場合であって、「状態」変数が単文字列（Ｔ）、単文字（Ｃ）、判別不納（⊥）以外の場合（つまり、単段落（Ｐ）の場合）、分離方向判別モジュール３２５０によって判別された方向の分離経路を分離経路記憶モジュール３４３５から選択し、画像受付モジュール３２１０が受け付けた画像を複数の部分画像に分離する。「方向」変数が判別不能（⊥）の場合、又は、「状態」変数が単文字列（Ｔ）、単文字（Ｃ）、判別不納（⊥）の場合（つまり、単段落（Ｐ）以外の場合）、分離経路を選択せず、画像を分離することはしないで、対象となっている文書の画像をそのまま出力する。
【０１００】
＜実験結果Ｂ＞
＜Ｂ＞に示した実施の形態による実験結果を、この実施の形態を用いないで行った場合と比較して説明する。
まず、本実施の形態を用いないで行った場合について説明する。本実施の形態を用いないで行った場合として背景技術で説明した技術がある。そのアプローチは、大きく２つに分類される。つまり、投影分布に基づくアプローチと、連結成分に基づくアプローチである。なお、連結成分の外接矩形の投影分布によるものは、投影分布に基づくアプローチに属するものとする。
それぞれ基本とする情報（すなわち、投影分布、連結成分）について、特徴量を算出し、複数方向の特徴量について、それぞれ比較することで、文字列の方向判別又は切り出しを行う。
投影分布による文字列の方向判別では、投影分布の値又はその形状（例えば、山、谷）の特徴を比較する。例えば、特開平０４−３１１２８３号公報記載の技術では、水平方向及び垂直方向の投影分布の最大値を特徴量として、方向判別を行う。
連結成分による文字列の方向判別では、連結成分どうしの位置関係の特徴を比較する。例えば、特開平０５−０７３７１８号公報記載の技術では、水平方向及び垂直方向について、最小距離が得られる連結成分の対の数を比較することで、方向判別を行う。一方、例えば、特開２０００−０９０１９４号公報記載の技術では、水平方向及び垂直方向について、連結成分の外接矩形どうしの平均間隔を比較することで、方向判別を行う。
投影分布による文字列の切り出しでは、文字列の方向の投影分布について、文字列の間隙に相当する投影分布の谷を特定し、分離境界とする。
連結成分による文字列の切り出しでは、隣接する連結成分を文字列として統合する。このとき、文字列の方向が既知であれば、この情報を有効に活用する。また、連結成分の統合により、方向判別と切り出しを併合して行うことのできる学術文献（ＬＯ’Ｇｏｒｍａｎ，  “Ｔｈｅ  Ｄｏｃｕｍｅｎｔ  Ｓｐｅｃｔｒｕｍ  ｆｏｒ  Ｐａｇｅ  Ｌａｙｏｕｔ  Ａｎａｌｙｓｉｓ，”  ＩＥＥＥ  ＴＰＡＭＩ，  Ｖｏｌ．１５，  Ｎｏ．１１，  Ｎｏｖ．１９９３，  ｐｐ１１６２−１１７３）のような方式もある。
図３５は、投影分布の例を示す説明図である。図３５（ａ）は水平・垂直方向の投影分布の例であり、図３５（ｂ）は連結成分の外接矩形の水平・垂直方向の投影分布の例である。図３５の例に示す文書の画像は、文字が密に配置されている。このような画像からは、文字列の切り出しを行うために有効な投影分布及び連結成分が得られないことがある。一般に、投影分布は文書画像のスキューの影響が大きく、連結成分は文書画像を構成する単文字のパタン（言語、装飾、等）、非文字のパタン（アンダーライン、ノイズ、等）による影響が大きい。特に、図３５の例に示すように、文字が密に配置された文書の画像では前述の影響が顕著となる。このような状況では、文字列どうしの分離境界の情報が現れないこと、水平方向及び垂直方向で十分な差異が現れないこととなる。
【０１０１】
次に、＜Ｂ＞の実施の形態で用いた分離経路について、図３６、図３７を用いて説明する。図３６、図３７は、水平、垂直方向の分離経路の例を示す説明図であり、対象とする画像である段落画像に対して、分離経路を、水平方向と垂直方向についてそれぞれ算出したものである。段落を構成する文字列の方向と同じ方向の分離経路は直線に近い形状であるのに対し、文字列と異なる方向の分離経路は歪曲している（図３６参照）。また、分離経路の歪曲の程度が同等であっても、太さが異なる（図３７参照）。＜Ｂ＞の実施の形態では、これらの特徴を定量的に評価し、特徴量として比較することで、文字列の方向判別を実現する。具体的には、分離経路の本数、個々の位置と形状及び経路上の画素値に基づいて特徴量を抽出する。
また、＜Ｂ＞の実施の形態では、分離経路の数により、対象としている画像が単段落であるか、単文字であるか、単文字列であるかを判別する。この様子を図３８の例に示す。すなわち、正しい方向と、誤った方向の分離経路とが、文字列の方向判別のために有効な差異をもつことを利用している。
【０１０２】
＜Ｂ＞の実施の形態による文字列切り出しの例を図３９、図４０、図４１に示す。
図３９の例は、第Ｂ−３の実施の形態による文字列切り出しの結果である。文書の画像を受け付け、状態＝Ｐ、すなわち、画像は単段落であると判別した。また、文字列の方向が水平であると判別した。この結果、分離経路によって、隣接（近接）する文字列が分離されていることが分かる（図３９（ｂ）、（ｃ）の拡大図参照）。
図４０（ａ）の例は＜Ｂ＞の実施の形態による切り出し結果であり、図４０（ｂ）の例は対象とした画像と投影分布であり、図４０（ｃ）の例は連結成分の外接矩形である。図４０の例から分かるように、＜Ｂ＞の実施の形態により、投影分布に現れない分離境界を特定すること、複数文字の連結を分離すること、単文字の誤分離を統合し、文字列の方向判別及び切り出しも行われている。
また、図４１の例から分かるように、図３９（ｂ）の例に示すような密に文字の配置された画像のみでなく、図３７の例に示すような文字列どうしの間隙の広い画像についても、＜Ｂ＞の実施の形態によって文字列の切り出しが行われている。
【０１０３】
なお、＜Ｂ＞に記載の発明は、以下のように捉えることができる。
（Ｂ１）  少なくとも文字画像を含む画像を受け付ける受付手段と、
前記受付手段によって受け付けられた画像に対して、該画像内の文字画像を分離する線分である分離経路を算出する経路算出手段と、
前記経路算出手段によって算出された分離経路により、前記受付手段によって受け付けられた画像を複数の文字画像へ分離する分離手段
を具備し、
前記経路算出手段は、該画像内の文字画像の一部を含む予め定められた範囲内において、経路上にある画素の輝度値の累積値が予め定められた条件を満たす分離経路を算出する
ことを特徴とする画像処理装置。
（Ｂ２）  前記経路算出手段は、複数方向の分離経路を算出し、
前記経路算出手段によって算出された複数方向の分離経路の特徴量を算出する特徴量算出手段と、
前記特徴量算出手段によって算出された特徴量に基づいて、画像の分離方向及び文字画像の状態を判別し、該判別の結果によって前記複数方向の分離経路のうちの分離経路を選択する選択手段
を具備し、
前記分離手段は、前記選択手段によって選択された分離経路により、前記受付手段によって受け付けられた画像を複数の部分画像へ分離する
ことを特徴とする（Ｂ１）に記載の画像処理装置。
（Ｂ３）  前記経路算出手段は、該画像内の文字画像の一部を含む予め定められた範囲内において、経路上にある画素の輝度値と経路の移動に基づく重み係数との積の累積値が予め定められた条件を満たす分離経路を算出する
ことを特徴とする（Ｂ１）又は（Ｂ２）に記載の画像処理装置。
（Ｂ４）  前記経路算出手段は、分離経路の算出において、隣り合う分離経路どうしの間隙の幅が予め定められた条件を満たす場合に、該間隙にある画素の輝度値によらず、該隣り合う分離経路は等価であると判断し、結合すること、
又は、
前記経路算出手段は、分離経路の算出において、隣り合う分離経路どうしの間隙にある画素の輝度値の累積値が予め定められた条件を満たす場合に、該隣り合う分離経路は等価であると判断し、結合すること
を特徴とする（Ｂ１）から（Ｂ３）のいずれか一項に記載の画像処理装置。
【０１０４】
＜Ｃ＞
次に、＜Ａ＞、＜Ｂ＞に示した技術を前提とした実施の形態を説明する。つまり、前述の＜Ｂ＞を採用し、主に＜Ａ＞による分離経路を応用し、この分離経路による画像分離を再帰的に行うことで、文字列の画像の分離を行うものである。なお、分離経路等の表記については、＜Ｂ＞と同じとする。
【０１０５】
＜第Ｃ−１の実施の形態＞
＜Ｃ＞の実施の形態の概要を説明する。
図４２は、第Ｃ−１の実施の形態の構成例についての概念的なモジュール構成図である。
第Ｃ−１の実施の形態は、画像受付モジュール４２１０、解析器選択モジュール４２２０、分離経路算出モジュール４２３０、分離経路特徴量算出モジュール４２４０、主分離方向判別モジュール４２５０、主分離経路選択モジュール４２６０、画像分離モジュール４２７０、再帰処理モジュール４２８０、再帰のない画像分離モジュール４２９０を有している。
【０１０６】
画像受付モジュール４２１０は、解析器選択モジュール４２２０と接続されている。画像４２００を受け付けて、その画像を解析器選択モジュール４２２０に渡す。画像受付モジュール４２１０は＜Ｂ＞に示した画像受付モジュール３１１０等に該当するものである。なお、画像４２００は、複数の段落を含む画像であってもよい。
【０１０７】
解析器選択モジュール４２２０は、画像受付モジュール４２１０、分離経路算出モジュール４２３０、再帰処理モジュール４２８０、再帰のない画像分離モジュール４２９０と接続されており、対象の画像を再帰のない画像分離モジュール４２９０又は分離経路算出モジュール４２３０のいずれか一方に渡す。画像受付モジュール４２１０が受け付けた画像４２００又は画像分離モジュール４２７０によって分離された部分画像（再帰的処理を行う場合に再帰処理モジュール４２８０から渡された部分画像）の縦方向の長さと横方向の長さの比率と予め定められた値との比較、又は再帰処理モジュール４２８０によって再帰的に処理を行うと判断された場合の再帰の深さに基づいて、画像受付モジュール４２１０が受け付けた画像４２００又は画像分離モジュール４２７０によって分離された部分画像を対象として、再帰のない画像分離モジュール４２９０又は分離経路算出モジュール４２３０に処理を行わせるか否かを判断する。詳細については、図５５、図５６を用いて後述する。
【０１０８】
分離経路算出モジュール４２３０は、解析器選択モジュール４２２０、分離経路特徴量算出モジュール４２４０と接続されており、分離経路を分離経路特徴量算出モジュール４２４０へ渡す。画像受付モジュール４２１０によって受け付けられた画像に対して、その画像内の文字画像を分離する線分である分離経路を算出する。分離経路算出モジュール４２３０は、＜Ｂ＞に示した水平方向分離経路算出モジュール３２２０、垂直方向分離経路算出モジュール３２３０、分離経路記憶モジュール３４３５に該当するものである。また、分離経路算出モジュール４２３０は、再帰処理モジュール４２８０によって再帰的に処理を行うと判断された場合に、画像分離モジュール４２７０によって分離された画像に対して、その画像内の文字画像を分離する線分である分離経路を算出する。
分離経路特徴量算出モジュール４２４０は、分離経路算出モジュール４２３０、主分離方向判別モジュール４２５０と接続されており、分離経路とその特徴量を主分離方向判別モジュール４２５０へ渡す。分離経路算出モジュール４２３０によって算出された複数方向の分離経路の特徴量を算出する。分離経路特徴量算出モジュール４２４０は、＜Ｂ＞に示した経路特徴量算出モジュール３２４０に該当するものである。
【０１０９】
主分離方向判別モジュール４２５０は、分離経路特徴量算出モジュール４２４０、主分離経路選択モジュール４２６０と接続されており、分離経路とその特徴量と文字画像の方向と状態を主分離経路選択モジュール４２６０へ渡す。分離経路特徴量算出モジュール４２４０によって算出された特徴量に基づいて、画像の分離方向及び文字画像の状態を判別する。主分離方向判別モジュール４２５０は、＜Ｂ＞に示した分離方向判別モジュール３２５０に該当するものである。
主分離経路選択モジュール４２６０は、主分離方向判別モジュール４２５０、画像分離モジュール４２７０と接続されており、分離経路とその特徴量と文字画像の方向と状態を画像分離モジュール４２７０へ渡す。主分離方向判別モジュール４２５０による判別の結果によって複数方向の分離経路のうちの分離経路を選択する。また、再帰処理モジュール４２８０による再帰的に処理を行うか否かの判断を行うため文字画像の状態を判別するようにしてもよい。また、主分離経路選択モジュール４２６０は、文字画像の状態が多段落である場合は、分離経路算出モジュール４２３０によって算出された分離経路の一部を間引くようにしてもよい。この間引き処理については、図５２、図５３を用いて後述する。
画像分離モジュール４２７０は、主分離経路選択モジュール４２６０、再帰処理モジュール４２８０と接続されており、部分画像とその部分画像の方向と状態を再帰処理モジュール４２８０へ渡す。主分離経路選択モジュール４２６０によって選択された分離経路により、画像を複数の部分画像へ分離する。画像分離モジュール４２７０は、＜Ｂ＞に示した画像分離モジュール３４６０に該当するものである。
【０１１０】
再帰処理モジュール４２８０は、解析器選択モジュール４２２０、画像分離モジュール４２７０と接続されており、再帰的処理を行う場合は部分画像を解析器選択モジュール４２２０へ渡し、再帰的処理の終了条件を満たしている場合は、文字列画像とその方向とその状態を出力する。画像分離モジュール４２７０によって分離された画像の文字画像の状態に基づいて、再帰的に処理を行うか否かを判断する。再帰的に処理を行うと判断した場合は、画像分離モジュール４２７０から受け取った部分画像を対象画像として解析器選択モジュール４２２０へ渡す。ここでの「文字画像の状態に基づいて、再帰的に処理を行う」とは、文字画像の状態が多段落ではないこと（判別する状態が、多段落、単段落、単文字列、単文字、判別不能の４つの場合は、単段落、単文字列、単文字、判別不能のうち、いずれかであること）を、再帰的処理の終了条件として、画像分離モジュール４２７０によって分離された部分画像に対して、解析器選択モジュール４２２０、分離経路算出モジュール４２３０、分離経路特徴量算出モジュール４２４０、主分離方向判別モジュール４２５０、主分離経路選択モジュール４２６０、画像分離モジュール４２７０による処理を繰り返し行うことをいう。
【０１１１】
再帰のない画像分離モジュール４２９０は、解析器選択モジュール４２２０と接続されており、文字列画像とその方向とその状態を出力する。再帰のない画像分離モジュール４２９０は、再帰的処理を行わないで、画像を分離する。分離経路算出モジュール４２３０〜再帰処理モジュール４２８０による処理を行わせるのでなければ、どのような画像分離の技術であってもよい。例えば、＜Ｂ＞に記載の技術を用いる。
【０１１２】
特徴量の具体例を表９に示す。
【表９】
0005577948.tif 000042
なお、表９に例示した通り、分離経路の本数Ｎｕｍは、分離経路の総数である。分離経路を求める各方向について（＜Ｃ＞に示す実施の形態では、水平方向と垂直方向）に１つずつ算出する。
図４３は、表９に例示した特徴量の例を示す説明図である。図４３の例は、図３０の例に分離経路の特徴として「分離経路どうしの間隙（Ｇａｐｉ）」を加えたものである。
表９に例示した特徴量のうち、Ｃｕｒｌｉ、Ｔｈｉｃｋｉ、Ｃｏｓｔｉは、ｐａｔｈｉについて１つずつ算出される。これに対して、Ｇａｐｉは、ｐａｔｈｉとｐａｔｈｉ＋１の間隙の特徴量であり、ｐａｔｈｉとｐａｔｈｉ＋１のペアについて１つずつ算出される。
【０１１３】
以下、各特徴量について、詳細に説明する。
「分経路の歪曲」について
Ｃｕｒｌｉの例を（３３）式、（３４）式、（３５）式、（３６）式に示す。
【数３３】
0005577948.tif 000043
【数３４】
0005577948.tif 000044
【数３５】
0005577948.tif 000045
【数３６】
0005577948.tif 000046
図４３に例示したように、Ｃｕｒｌｉはｐａｔｈｉの歪曲である。
Ｃｕｒｌｉについては、（３３）式、（３４）式、（３５）式のように、始点と終点を結ぶ直線ｆ（ｘ）（以下、理想直線とする）との差分を評価する例がある。具体的には、（３３）式は太さを持たない経路と理想直線との差分の絶対値、（３４）式は前記差分の２乗誤差、（３５）式は太さを持つ経路について算出した中心線について（３３）式と同様の差分を評価した例である。これらは、図４３の例において、ｐａｔｈｉ＋１の射線部分の面積の評価に相当する。
また、（３６）式のように、経路そのものの微分値を（微分距離ｄ［ｐｘ］）評価する例を用いてもよい。
【０１１４】
次に、「分経路の歪曲」の統計値である特徴量の例について説明する。
Ｃｕｒｌｉは各ｐａｔｈｉについて算出する。そこで、すべてのｐａｔｈｉのＣｕｒｌｉについて、統計値を特徴量とする例を（３７）式、（３８）式、（３９）式に示す。それぞれ、すべての分離経路のＣｕｒｌｉの最大値（ＭａｘＣｕｒｌ）、最小値（ＭｉｎＣｕｒｌ）、平均値（ＡｖｇＣｕｒｌ）に相当する。
【数３７】
0005577948.tif 000047
【数３８】
0005577948.tif 000048
【数３９】
0005577948.tif 000049
さらに、前記の統計値の特徴量は、端部の２つの分離経路（すなわち、ｐａｔｈ０とｐａｔｈＮｕｍ−１）のＣｕｒｌｉであるＣｕｒｌ０とＣｕｒｌＮｕｍ−１を除いた場合の統計値である特徴量として（４０）式、（４１）式、（４２）式の例がある。端部の２つの分離経路のＣｕｒｌｉは対象画像に大きく依存せず、諸々の判別で参照する特徴量として必ずしも適切でない。ゆえに、より正確な解析を行う場合に、各式の例のように、これらを除くことを行う。
【数４０】
0005577948.tif 000050
【数４１】
0005577948.tif 000051
【数４２】
0005577948.tif 000052
【０１１５】
「分離経路の太さ」について
Ｔｈｉｃｋｉの例を（４３）式、（４４）式、（４５）式に示す。
図４３に例示したように、Ｔｈｉｃｋｉはｐａｔｈｉの太さである。これは、図４３に例示したｔｏｐ＿ｐａｔｈｉとｂｏｔｔｏｍ＿ｐａｔｈｉとの距離の評価に相当する。
（４３）式は、ｐａｔｈｉについて太さの最大値を特徴量とする例である。
（４４）式は、ｐａｔｈｉについて太さの最小値を特徴量とする例である。
（４５）式は、ｐａｔｈｉについて太さの平均値を特徴量とする例である。
【数４３】
0005577948.tif 000053
【数４４】
0005577948.tif 000054
【数４５】
0005577948.tif 000055
【０１１６】
また、ＴｈｉｃｋｉについてもＣｕｒｌｉと同様に、（４６）式、（４７）式、（４８）式、（４９）式、（５０）式、（５１）式に示すような統計値である特徴量の例がある。
【数４６】
0005577948.tif 000056
【数４７】
0005577948.tif 000057
【数４８】
0005577948.tif 000058
【数４９】
0005577948.tif 000059
【数５０】
0005577948.tif 000060
【数５１】
0005577948.tif 000061
【０１１７】
「分離経路のコスト」について
Ｃｏｓｔｉの例を（５２）式、（５３）式、（５４）式に示す。
Ｃｏｓｔｉについては、（５２）式、（５３）式のように、単純な経路上の画素値の累積値を評価する例がある。具体的には、（５２）式は、経路上の画素値の累積値を評価する例である。（５３）式は、経路の中心線上の画素値の累積値を評価する例である。さらに、（５４）式のように、経路の歪曲によって、重みづけ（式中、係数ｃに相当する）を行った経路上の画素値の累積値を評価する例がある。
【数５２】
0005577948.tif 000062
【数５３】
0005577948.tif 000063
【数５４】
0005577948.tif 000064
また、ＣｏｓｔｉについてもＣｕｒｌｉと同様に、（５５）式、（５６）式、（５７）式、（５８）式、（５９）式、（６０）式に示すような統計値である特徴量の例がある。
【数５５】
0005577948.tif 000065
【数５６】
0005577948.tif 000066
【数５７】
0005577948.tif 000067
【数５８】
0005577948.tif 000068
【数５９】
0005577948.tif 000069
【数６０】
0005577948.tif 000070
【０１１８】
「分離経路どうしの間隙」について
Ｇａｐｉの例を（６１）式、（６２）式、（６３）式に示す。
図４３に例示したように、Ｇａｐｉはｐａｔｈｉとｐａｔｈｉ＋１の間隙の幅である。これは、図４３の例において、ｂｏｔｔｏｍ＿ｐａｔｈｉとｔｏｐ＿ｐａｔｈｉ＋１との距離の評価に相当する。
（６１）式は、ｐａｔｈｉとｐａｔｈｉ＋１のペアについて間隙幅の最大値を特徴量とする例である。
（６２）式は、ｐａｔｈｉとｐａｔｈｉ＋１のペアについて間隙幅の最小値を特徴量とする例である。
（６３）式は、ｐａｔｈｉとｐａｔｈｉ＋１のペアについて間隙幅の平均値を特徴量とする例である。
【数６１】
0005577948.tif 000071
【数６２】
0005577948.tif 000072
【数６３】
0005577948.tif 000073
また、ＧａｐｉについてもＣｕｒｌｉと同様に、（６４）式、（６５）式、（６６）式に示すような統計値である特徴量の例がある。ただし、Ｃｕｒｌｉと異なり、端部の間隙（すなわち、ｐａｔｈ０とｐａｔｈ１の間隙、及びｐａｔｈＮｕｍ−２とｐａｔｈＮｕｍ−１の間隙）の幅は、対象の画像に依存する。
【数６４】
0005577948.tif 000074
【数６５】
0005577948.tif 000075
【数６６】
0005577948.tif 000076
【０１１９】
＜第Ｃ−２の実施の形態＞
図４４は、第Ｃ−２の実施の形態の構成例についての概念的なモジュール構成図である。
第Ｃ−２の実施の形態は、画像受付モジュール４４１０、分離経路による画像分離モジュール４４２０、再帰処理モジュール４４３０を有している。
【０１２０】
画像受付モジュール４４１０は、分離経路による画像分離モジュール４４２０と接続されており、図４２に例示した画像受付モジュール４２１０に該当する。また、画像４４００も図４２に例示した画像４２００に該当する。
分離経路による画像分離モジュール４４２０は、画像受付モジュール４４１０、再帰処理モジュール４４３０と接続されている。分離経路による画像分離モジュール４４２０は、対象となる画像を部分画像へ分離し、出力する。また、対象となる画像の分離方向（以下、方向ともいう）、及び状態を判別し、出力する。分離経路による画像分離モジュール４４２０については、図４５を用いて後述する。
再帰処理モジュール４４３０は、分離経路による画像分離モジュール４４２０と接続されている。再帰処理モジュール４４３０は、対象となる画像の状態に基づいて、再帰処理を行うか否かを判別する。再帰処理を行う場合、各部分画像は分離経路による画像分離モジュール４４２０へ渡される。そうでなければ、文字列の画像である部分画像、方向、及び状態を出力し、処理を終了する。再帰処理モジュール４４３０については、図４６を用いて後述する。
【０１２１】
ここで、「方向」は、以下の３つの値をとりうる。
（１）Ｈ：水平
（２）Ｖ：垂直
（３）⊥：判別不能
また、「状態」は、以下の５つの値をとりうる。
（１）Ｍ：多段落        （再帰処理あり）
（２）Ｐ：単段落        （再帰処理の疑いあり）
（３）Ｔ：単文字列      （再帰処理なし）
（４）Ｃ：単文字        （再帰処理なし）
（５）⊥：判別不能      （再帰処理なし）
【０１２２】
図４５は、分離経路による画像分離モジュール４４２０の構成例についての概念的なモジュール構成図である。
分離経路による画像分離モジュール４４２０は、水平方向分離経路算出モジュール４５１０、垂直方向分離経路算出モジュール４５２０、経路特徴量算出モジュール４５３０、主分離方向判別モジュール４５４０、主分離経路選択モジュール４５５０、画像分離モジュール４５６０を有している。
【０１２３】
水平方向分離経路算出モジュール４５１０は、経路特徴量算出モジュール４５３０、主分離経路選択モジュール４５５０と接続されている。対象とする画像に対して、水平方向の分離経路を算出し、その分離経路を経路特徴量算出モジュール４５３０に渡す。＜Ａ＞、＜Ｂ＞に示した水平方向分離経路算出モジュール３２２０と同等のものである。
垂直方向分離経路算出モジュール４５２０は、経路特徴量算出モジュール４５３０、主分離経路選択モジュール４５５０と接続されている。対象とする画像に対して、垂直方向の分離経路を算出し、その分離経路を経路特徴量算出モジュール４５３０に渡す。＜Ａ＞、＜Ｂ＞に示した垂直方向分離経路算出モジュール３２３０と同等のものである。
経路特徴量算出モジュール４５３０は、水平方向分離経路算出モジュール４５１０、垂直方向分離経路算出モジュール４５２０、主分離方向判別モジュール４５４０、主分離経路選択モジュール４５５０と接続されている。前述の分離経路の特徴量を算出し、その特徴量を主分離方向判別モジュール４５４０、主分離経路選択モジュール４５５０に渡す。＜Ｂ＞に示した経路特徴量算出モジュール３２４０と同等のものである。
【０１２４】
主分離方向判別モジュール４５４０は、経路特徴量算出モジュール４５３０、主分離経路選択モジュール４５５０と接続されている。分離方向と状態を判別し、その分離方向と状態を主分離経路選択モジュール４５５０に渡す。ただし、状態は後段の処理で更新されうる。判別は、水平方向と垂直方向の分離経路の特徴量に基づいて行う。この処理フローを図４７の例に示すが、説明は後述する。
主分離経路選択モジュール４５５０は、水平方向分離経路算出モジュール４５１０、垂直方向分離経路算出モジュール４５２０、経路特徴量算出モジュール４５３０、主分離方向判別モジュール４５４０、画像分離モジュール４５６０と接続されている。分離方向の分離経路の一部を、主な分離経路として選択し、その分離経路と状態を画像分離モジュール４５６０へ渡す。また、分離経路を間引く。また、条件が満たされた場合、状態を更新する。判別された方向の分離経路を選択し、水平方向と垂直方向の分離経路の特徴量に基づいて、再帰の判別のため、対象となる画像の状態がＭであるか否かを判別する。また、このとき、分離経路を間引く。この処理フローを、図４８から図５３の例に示すが、説明は後述する。
画像分離モジュール４５６０は、主分離経路選択モジュール４５５０と接続されている。前述の画像分離モジュール４２７０と同等のものであり、部分画像、方向、状態を再帰処理モジュール４４３０に渡す。
【０１２５】
図４６は、再帰処理モジュール４４３０による処理例を示すフローチャートである。
再帰処理モジュール４４３０では、状態に基づいて、再帰処理を行うか否かを判断する。具体的には、分離する対象である画像が多段落と判別された場合、分離後の各部分画像を分離経路による画像分離モジュール４４２０に渡す（すなわち、再帰する）。そうでなければ、文字列画像である部分画像、方向、及び状態を出力し、処理を終了する。
フローチャートに沿って説明する。
ステップＳ４６０２では、「状態」変数が多段落（状態＝＝Ｍ）であるか否かを判断し、「状態」変数が多段落である場合はステップＳ４６０６へ進み、それ以外の場合はステップＳ４６０４へ進む。
ステップＳ４６０４では、部分画像を出力し、方向と状態を出力する。
ステップＳ４６０６では、部分画像を受け付け（再帰）、分離経路による画像分離モジュール４４２０へ受け付けた画像を渡す。
【０１２６】
次に、主分離方向判別モジュール４５４０の処理を説明する。図４７は、主分離方向判別モジュール４５４０による処理例を示すフローチャートである。主分離方向判別モジュール４２５０は、表１０、表１１、表１２、表１３、表１４、表１５を用いて判別を行う。これらは、前述の特徴量について、水平方向と垂直方向のものを比較することを示す表である。主分離方向判別モジュール４２５０は、判別し、方向と状態を更新し、出力する。
【表１０】
0005577948.tif 000077
【表１１】
0005577948.tif 000078
【表１２】
0005577948.tif 000079
【表１３】
0005577948.tif 000080
【表１４】
0005577948.tif 000081
【表１５】
0005577948.tif 000082
【０１２７】
図４７の例に示す判別のフローチャートは、逐次判別である。図４７における各判別の順番は、以下のことに基づく。
まず、本実施の形態における分離方向判別は、分離経路の形状に基づいて分離方向を判別するものである。このため、形状の情報に基づく判別でない「Ｃｏｓｔによる判別」は、最も優先度が低いので、最後段に行う。
続いて、対象とする画像は多段落の可能性があり、その画像から文字列を切り出す必要があることから、まずは、段落どうしを分離する必要がある。段落どうしの間隙は、段落を構成する文字列どうしの間隙よりも広いことが一般的である。そこで、まず、「ＭａｘＴｈｉｃｋによる判別」（表１１）を行う。
【０１２８】
次に、対象とする画像によって、必ずしも、水平方向、垂直方向について、算出される分離経路の総数が同じであるとは限らない（すなわち、縦に長い横書き、又は、横に長い縦書き等があり得る）。ある方向の分離経路の平均値は、分離経路の総数（すなわち、Ｎｕｍ）に影響されるため、「ＡｖｇＣｕｒｌによる判別」（表１３）の前段に、「ＭａｘＣｕｒｌによる判別」（表１２）を行う。
次に、文字列どうしの間隙が十分に広い場合、Ｃｕｒｌでは判別がつかないことがある。このため、「ＡｖｇＴｈｉｃｋによる判別」（表１４）を行う。
最後に、複数の文字列を含む画像を想定した判別であるが、対象とする画像は必ずしも複数の文字列があるとは限らない。このため、最前段に「Ｎｕｍによる判別」（表１０）を行い、対象とする画像が、単文字か、単文字列か、それ以外かを判別する。
【０１２９】
フローチャートに沿って説明する。
ステップＳ４７０２では、「方向」変数に⊥（判別不能）を代入し、「状態」変数に⊥（判別不能）を代入する。
ステップＳ４７０４では、表１０のＮｕｍによる判別を行う。つまり、横方向の分離経路と縦方向の分離経路が２本であるならば、単文字（Ｃ）である。いずれか一方が２本であるならば、単文字列（Ｔ）であり、横方向の分離経路が２本であるならば、方向は水平（Ｈ）であり、縦方向の分離経路が２本であるならば、方向は垂直（Ｖ）である。両方が２本でないならば、何もしない（状態は判別不能（⊥）のままである）。
ステップＳ４７０６では、「状態」変数は判別不能（状態＝＝⊥）か否かを判断し、「状態」変数が判別不能の場合はステップＳ４７０８へ進み、それ以外の場合はステップＳ４７２６へ進む。
【０１３０】
ステップＳ４７０８では、表１１のＭａｘＴｈｉｃｋによる判別を行う。つまり、縦方向のＭａｘＴｈｉｃｋが横方向のＭａｘＴｈｉｃｋよりも小であるならば、方向は水平（Ｈ）であり、状態は単段落（Ｐ）である。縦方向のＭａｘＴｈｉｃｋが横方向のＭａｘＴｈｉｃｋよりも大であるならば、方向は垂直（Ｖ）であり、状態は単段落（Ｐ）である。それ以外（両方が同じ）ならば、何もしない（状態は判別不能（⊥）のままである）。
ステップＳ４７１０では、「状態」変数は判別不能（状態＝＝⊥）か否かを判断し、「状態」変数が判別不能の場合はステップＳ４７１２へ進み、それ以外の場合はステップＳ４７２６へ進む。
【０１３１】
ステップＳ４７１２では、表１２のＭａｘＣｕｒｌによる判別を行う。つまり、横方向のＭａｘＣｕｒｌが縦方向のＭａｘＣｕｒｌよりも小であるならば、方向は水平（Ｈ）であり、状態は単段落（Ｐ）である。横方向のＭａｘＣｕｒｌが縦方向のＭａｘＣｕｒｌよりも大であるならば、方向は垂直（Ｖ）であり、状態は単段落（Ｐ）である。それ以外（両方が同じ）ならば、何もしない（状態は判別不能（⊥）のままである）。
ステップＳ４７１４では、「状態」変数は判別不能（状態＝＝⊥）か否かを判断し、「状態」変数が判別不能の場合はステップＳ４７１６へ進み、それ以外の場合はステップＳ４７２６へ進む。
【０１３２】
ステップＳ４７１６では、表１３のＡｖｇＣｕｒｌによる判別を行う。つまり、横方向のＡｖｇＣｕｒｌが縦方向のＡｖｇＣｕｒｌよりも小であるならば、方向は水平（Ｈ）であり、状態は単段落（Ｐ）である。横方向のＡｖｇＣｕｒｌが縦方向のＡｖｇＣｕｒｌよりも大であるならば、方向は垂直（Ｖ）であり、状態は単段落（Ｐ）である。それ以外（両方が同じ）ならば、何もしない（状態は判別不能（⊥）のままである）。
ステップＳ４７１８では、「状態」変数は判別不能（状態＝＝⊥）か否かを判断し、「状態」変数が判別不能の場合はステップＳ４７２０へ進み、それ以外の場合はステップＳ４７２６へ進む。
【０１３３】
ステップＳ４７２０では、表１４のＡｖｇＴｈｉｃｋによる判別を行う。つまり、横方向のＡｖｇＴｈｉｃｋが縦方向のＡｖｇＴｈｉｃｋよりも大であるならば、方向は水平（Ｈ）であり、状態は単段落（Ｐ）である。横方向のＡｖｇＴｈｉｃｋが縦方向のＡｖｇＴｈｉｃｋよりも小であるならば、方向は垂直（Ｖ）であり、状態は単段落（Ｐ）である。それ以外（両方が同じ）ならば、何もしない（状態は判別不能（⊥）のままである）。
ステップＳ４７２２では、「状態」変数は判別不能（状態＝＝⊥）か否かを判断し、「状態」変数が判別不能の場合はステップＳ４７２４へ進み、それ以外の場合はステップＳ４７２６へ進む。
【０１３４】
ステップＳ４７２４では、表１５のＡｖｇＣｏｓｔによる判別を行う。つまり、横方向のＡｖｇＣｏｓｔが縦方向のＡｖｇＣｏｓｔよりも小であるならば、方向は水平（Ｈ）であり、状態は単段落（Ｐ）である。横方向のＡｖｇＣｏｓｔが縦方向のＡｖｇＣｏｓｔよりも大であるならば、方向は垂直（Ｖ）であり、状態は単段落（Ｐ）である。それ以外（両方が同じ）ならば、何もしない（状態は判別不能（⊥）のままである）。
ステップＳ４７２６では、「方向」変数と「状態」変数の組である（方向，状態）を出力する。
【０１３５】
主分離方向判別モジュール４５４０は、図４７に例示したフローチャートの他にも、判別の順番を異ならせてもよい。例えば、「ＡｖｇＴｈｉｃｋによる判別」（表１４）を、「ＭａｘＴｈｉｃｋによる判別」（表１１）の直後に配置してもよい。また、図４７に例示するような逐次判別ではなく、各判別の総合を利用する総合判別を行ってもよい。つまり、表１０から表１５を用いた判別をそれぞれ行った後に、総合して判別するようにしてもよい。また、分離経路以外に、投影分布や、連結成分の特徴量による判別との総合判別もある。これらは、対象とする画像の性質によって、選択すればよい。
【０１３６】
次に、主分離経路選択モジュール４５５０の処理を説明する。この処理フローを、図４８から図５３の例に示す。主分離経路選択モジュール４５５０は、これらの処理フローのうち、いずれか一つの処理フロー又はこれらの組み合わせの処理フローにしたがった処理を行う。
この処理では、判別された方向の分離経路のうち、分離経路として適切な経路を選択し、出力する。また、再帰の判別のための状態の判別を行う。また、分離経路の間引きを行う。
【０１３７】
図４８は、主分離経路選択モジュール４５５０による処理例（１）を示すフローチャートである。
ステップＳ４８０２では、主分離方向判別モジュール４５４０によって判別された方向の分離経路を選択する。
ステップＳ４８０４では、「状態」変数は単段落でない（状態≠Ｐ）か否かを判断し、「状態」変数が単段落でない場合はステップＳ４８１０へ進み、それ以外の場合はステップＳ４８０６へ進む。つまり、状態がＰ（段落）でなければ、ステップＳ４８０２で選択された分離経路をそのまま選択し、これ以上の再帰処理を行わないよう、状態を更新しない。これは、対象とする画像が、Ｔ（単文字列）、Ｃ（単文字）、又は⊥（判別不能）であった場合、これ以上の画像分離を行わないためである。
【０１３８】
ステップＳ４８０６では、ＭａｘＴｈｉｃｋ＞ＭａｘＧａｐか否かを判断し、ＭａｘＴｈｉｃｋ＞ＭａｘＧａｐの場合はステップＳ４８０８へ進み、それ以外の場合はステップＳ４８１０へ進む。つまり、ＭａｘＴｈｉｃｋ（すなわち、分離経路の最大の太さ）が、対象とする画像に対して十分に大きいとき、対象とする画像は多段落（Ｍ）であると判別し、状態をＭに更新する（ステップＳ４８０８）。この十分に大きいことを、文字列どうしの間隙であるＭａｘＧａｐとの比較により判別することで、対象とする画像が多段落（Ｍ）であるか、単段落（Ｐ）であるかを判別する。
ステップＳ４８０８では、「状態」変数にＭ（多段落）を代入する。
ステップＳ４８１０では、（分離経路，状態）を出力する。
【０１３９】
図４９は、主分離経路選択モジュール４５５０による処理例（２）を示すフローチャートである。
ステップＳ４９０２では、主分離方向判別モジュール４５４０によって判別された方向の分離経路を選択する。
ステップＳ４９０４では、「状態」変数は単段落でない（状態≠Ｐ）か否かを判断し、「状態」変数が単段落でない場合はステップＳ４９１０へ進み、それ以外の場合はステップＳ４９０６へ進む。
【０１４０】
ステップＳ４９０６では、ＭａｘＣｕｒｌ＞θＣｕｒｌか否かを判断し、ＭａｘＣｕｒｌ＞θＣｕｒｌの場合はステップＳ４９０８へ進み、それ以外の場合はステップＳ４９１０へ進む。つまり、ＭａｘＣｕｒｌと予め定められた閾値（θＣｕｒｌ）とを比較して、状態が多段落（Ｍ）であるか否かの判別を行う。「ＭａｘＣｕｒｌ＞θＣｕｒｌ」による判別では、ステップＳ４９０２で選択された分離経路の歪曲が閾値θＣｕｒｌ以下であるとき、対象とする画像は多段落（Ｍ）以外の単段落（Ｐ）等であると判別し、ステップＳ４９０２で選択された分離経路をそのまま選択する。そうでなければ、状態をＭに更新する（ステップＳ４９０８）。
ステップＳ４９０８では、「状態」変数にＭ（多段落）を代入する。
ステップＳ４９１０では、（分離経路，状態）を出力する。
【０１４１】
図５０は、主分離経路選択モジュール４５５０による処理例（３）を示すフローチャートである。図４８、図４９と異なり、複数の判別（ステップＳ５００６、ステップＳ５００８、ステップＳ５０１０）がある処理例である。
ステップＳ５００２では、主分離方向判別モジュール４５４０によって判別された方向の分離経路を選択する。
ステップＳ５００４では、「状態」変数は単段落でない（状態≠Ｐ）か否かを判断し、「状態」変数が単段落でない場合はステップＳ５０１４へ進み、それ以外の場合はステップＳ５００６へ進む。
ステップＳ５００６では、ＭａｘＣｕｒｌ＝＝０か否かを判断し、ＭａｘＣｕｒｌ＝＝０の場合はステップＳ５０１４へ進み、それ以外の場合はステップＳ５００８へ進む。つまり、ステップＳ５００２で選択した分離経路に歪曲がないとき、対象とする画像は単段落であると判別し、ステップＳ５００２で選択された分離経路をそのまま選択する。
【０１４２】
ステップＳ５００８では、ＭａｘＴｈｉｃｋ＞ＭａｘＧａｐか否かを判断し、ＭａｘＴｈｉｃｋ＞ＭａｘＧａｐの場合はステップＳ５０１２へ進み、それ以外の場合はステップＳ５０１０へ進む。図４８に例示のフローチャート内のＳ４８０６に該当する。
ステップＳ５０１０では、ＭａｘＣｕｒｌ＞θＣｕｒｌか否かを判断し、ＭａｘＣｕｒｌ＞θＣｕｒｌの場合はステップＳ５０１２へ進み、それ以外の場合はステップＳ５０１４へ進む。図４９に例示のフローチャート内のＳ４９０６に該当する。
ステップＳ５０１２では、「状態」変数にＭ（多段落）を代入する。
ステップＳ５０１４では、（分離経路，状態）を出力する。
【０１４３】
図５１は、主分離経路選択モジュール４５５０による処理例（４）を示すフローチャートである。分離方向でない方向の分離経路の特徴量を参照して判別（ステップＳ５１１０）する処理例である。
ステップＳ５１０２では、主分離方向判別モジュール４５４０によって判別された方向の分離経路を選択する。
ステップＳ５１０４では、「状態」変数は単段落でない（状態≠Ｐ）か否かを判断し、「状態」変数が単段落でない場合はステップＳ５１１６へ進み、それ以外の場合はステップＳ５１０６へ進む。
ステップＳ５１０６では、ＭａｘＣｕｒｌ＝＝０か否かを判断し、ＭａｘＣｕｒｌ＝＝０の場合はステップＳ５１１６へ進み、それ以外の場合はステップＳ５１０８へ進む。図５０に例示のフローチャート内のＳ５００６に該当する。
ステップＳ５１０８では、ＭａｘＴｈｉｃｋ＞ＭａｘＧａｐか否かを判断し、ＭａｘＴｈｉｃｋ＞ＭａｘＧａｐの場合はステップＳ５１１４へ進み、それ以外の場合はステップＳ５１１０へ進む。図４８に例示のフローチャート内のＳ４８０６に該当する。
【０１４４】
ステップＳ５１１０では、ＡｖｇＴｈｉｃｋ＜ｓｕｂ＿ＭａｘＴｈｉｃｋか否かを判断し、ＡｖｇＴｈｉｃｋ＜ｓｕｂ＿ＭａｘＴｈｉｃｋの場合は、Ｓ５１１４へ進み、それ以外の場合はステップＳ５１１２へ進む。なお、「ｓｕｂ＿ＭａｘＴｈｉｃｋ」とは、分離方向でない方向の分離経路の最大太さである。「ｓｕｂ＿ＭａｘＴｈｉｃｋ」が、分離方向の分離経路の平均の太さである「ＡｖｇＴｈｉｃｋ」よりも大きいとき、対象とする画像は多段落（Ｍ）であると判別する。
ステップＳ５１１２では、ＭａｘＣｕｒｌ＞θＣｕｒｌか否かを判断し、ＭａｘＣｕｒｌ＞θＣｕｒｌの場合はステップＳ５１１４へ進み、それ以外の場合はステップＳ５１１６へ進む。図４９に例示のフローチャート内のＳ４９０６に該当する。
ステップＳ５１１４では、「状態」変数にＭ（多段落）を代入する。
ステップＳ５１１６では、（分離経路，状態）を出力する。
【０１４５】
図５２は、主分離経路選択モジュール４５５０による処理例（５）を示すフローチャートである。対象とする画像が多段落であると判別されたとき、分離経路の間引きのある処理例である。なお、Ｓ５２０２からＳ５２１４までの処理、Ｓ５２１８の処理は、それぞれ図５１のＳ５１０２からＳ５１１４までの処理、Ｓ５１１６の処理に該当する。
ステップＳ５２０２では、主分離方向判別モジュール４５４０によって判別された方向の分離経路を選択する。
ステップＳ５２０４では、「状態」変数は単段落でない（状態≠Ｐ）か否かを判断し、「状態」変数が単段落でない場合はステップＳ５２１８へ進み、それ以外の場合はステップＳ５２０６へ進む。
ステップＳ５２０６では、ＭａｘＣｕｒｌ＝＝０か否かを判断し、ＭａｘＣｕｒｌ＝＝０の場合はステップＳ５２１８へ進み、それ以外の場合はステップＳ５２０８へ進む。
ステップＳ５２０８では、ＭａｘＴｈｉｃｋ＞ＭａｘＧａｐか否かを判断し、ＭａｘＴｈｉｃｋ＞ＭａｘＧａｐの場合はステップＳ５２１４へ進み、それ以外の場合はステップＳ５２１０へ進む。
【０１４６】
ステップＳ５２１０では、ＡｖｇＴｈｉｃｋ＜ｓｕｂ＿ＭａｘＴｈｉｃｋか否かを判断し、ＡｖｇＴｈｉｃｋ＜ｓｕｂ＿ＭａｘＴｈｉｃｋの場合は、Ｓ５２１４へ進み、それ以外の場合はステップＳ５２１２へ進む。
ステップＳ５２１２では、ＭａｘＣｕｒｌ＞θＣｕｒｌか否かを判断し、ＭａｘＣｕｒｌ＞θＣｕｒｌの場合はステップＳ５２１４へ進み、それ以外の場合はステップＳ５２１８へ進む。
ステップＳ５２１４では、「状態」変数にＭ（多段落）を代入する。
ステップＳ５２１６では、分離経路の歪曲（Ｃｕｒｌｉ）が最も小さいもの、分離経路の太さ（Ｔｈｉｃｋｉ）が最も太いもの以外の分離経路を消去する。例えば、ＣｕｒｌｉとＭｉｎＣｕｒｌとの比較、ＴｈｉｃｋｉとＭａｘＴｈｉｃｋとの比較によって、条件を満たすｐａｔｈｉを消去するようにしてもよい。
ステップＳ５２１８では、（分離経路，状態）を出力する。
【０１４７】
図５３は、主分離経路選択モジュール４５５０による処理例（６）を示すフローチャートである。対象とする画像が多段落であると判別されたとき、分離経路の間引きのある処理例である。なお、Ｓ５３０２からＳ５３１４までの処理、Ｓ５３１８の処理は、それぞれ図５１のＳ５１０２からＳ５１１４までの処理、Ｓ５１１６の処理に該当する。
ステップＳ５３０２では、主分離方向判別モジュール４５４０によって判別された方向の分離経路を選択する。
ステップＳ５３０４では、「状態」変数は単段落でない（状態≠Ｐ）か否かを判断し、「状態」変数が単段落でない場合はステップＳ５３１８へ進み、それ以外の場合はステップＳ５３０６へ進む。
ステップＳ５３０６では、ＭａｘＣｕｒｌ＝＝０か否かを判断し、ＭａｘＣｕｒｌ＝＝０の場合はステップＳ５３１８へ進み、それ以外の場合はステップＳ５３０８へ進む。
ステップＳ５３０８では、ＭａｘＴｈｉｃｋ＞ＭａｘＧａｐか否かを判断し、ＭａｘＴｈｉｃｋ＞ＭａｘＧａｐの場合はステップＳ５３１４へ進み、それ以外の場合はステップＳ５３１０へ進む。
【０１４８】
ステップＳ５３１０では、ＡｖｇＴｈｉｃｋ＜ｓｕｂ＿ＭａｘＴｈｉｃｋか否かを判断し、ＡｖｇＴｈｉｃｋ＜ｓｕｂ＿ＭａｘＴｈｉｃｋの場合は、Ｓ５３１４へ進み、それ以外の場合はステップＳ５３１２へ進む。
ステップＳ５３１２では、ＭａｘＣｕｒｌ＞θＣｕｒｌか否かを判断し、ＭａｘＣｕｒｌ＞θＣｕｒｌの場合はステップＳ５３１４へ進み、それ以外の場合はステップＳ５３１８へ進む。
ステップＳ５３１４では、「状態」変数にＭ（多段落）を代入する。
ステップＳ５３１６では、｛ｐａｔｈｉ｜Ｃｕｒｌｉ＞θ’Ｃｕｒｌ｝を消去する。つまり、予め定められた閾値（θ’Ｃｕｒｌ）と比較することによって、分離経路の間引きを行う。歪曲が閾値θ’Ｃｕｒｌよりも小さなｐａｔｈｉを選択することで分離経路の間引きを実現している。
ステップＳ５３１８では、（分離経路，状態）を出力する。
【０１４９】
図４８から図５３までの処理は、逐次的に判別しているが、逐次判別ではなく、各判別の総合を利用する総合判別を行ってもよい。例えば、ステップＳ５３０８、ステップＳ５３１０、ステップＳ５３１２の処理をそれぞれ行った後に、総合して判別するようにしてもよい。また、分離経路以外に、投影分布や、連結成分の特徴量による判別と組み合わせるようにしてもよい。例えば、それぞれの投影分布の幅及び間隔が規則的である等の対象とする画像の性質に応じて、投影分布や、連結成分の特徴量による判別を行うようにしてもよい。
【０１５０】
＜第Ｃ−３の実施の形態＞
図５４は、第Ｃ−３の実施の形態の構成例についての概念的なモジュール構成図である。
第Ｃ−３の実施の形態は、画像から文字列を切り出すものであって、画像受付モジュール４４１０、解析器選択モジュール５４１５、分離経路による画像分離モジュール４４２０、再帰処理モジュール５４３０、再帰のない画像分離モジュール５４４０を有している。
【０１５１】
画像受付モジュール４４１０は、解析器選択モジュール５４１５と接続されており、図４２に例示した画像受付モジュール４２１０に該当する。また、画像４４００も図４２に例示した画像４２００に該当する。
【０１５２】
解析器選択モジュール５４１５は、画像受付モジュール４４１０、分離経路による画像分離モジュール４４２０、再帰のない画像分離モジュール５４４０と接続されている。解析器選択モジュール５４１５は、対象とする画像を分離経路による画像分離モジュール４４２０又は再帰のない画像分離モジュール５４４０のいずれか一方に振り分ける。この処理フローを図５５に示す。図５５は、解析器選択モジュール５４１５による処理例を示すフローチャートである。
ステップＳ５５０２では、多段落判別を行う。この処理については、図５７、図５８を用いて後述する。
ステップＳ５５０４では、状態が多段落（状態＝Ｍ）であるか否かを判断し、「状態」変数が多段落である場合はステップＳ５５０８へ進み、それ以外の場合はステップＳ５５０６へ進む。
ステップＳ５５０６では、再帰のない画像分離モジュール５４４０へ受け付けた画像を渡す。
ステップＳ５５０８では、分離経路による画像分離モジュール４４２０へ受け付けた画像を渡す。この後、再帰処理モジュール５４３０による再帰的な処理が行われる。
【０１５３】
また、このとき、対象とする画像の特徴によって、分離経路による画像分離モジュール４４２０、再帰のない画像分離モジュール５４４０の処理におけるパラメータを更新するようにしてもよい。例えば、具体的には、図４５に例示した水平方向分離経路算出モジュール４５１０、垂直方向分離経路算出モジュール４５２０の解析パラメータ、又は図４９から図５３に例示した閾値θＣｕｒｌ、閾値θ’Ｃｕｒｌ等、図５７、図５８を用いて後述する「多段落判別」における閾値（θａｓｐｅｃｔ）の更新を行うようにしてもよい。
【０１５４】
分離経路による画像分離モジュール４４２０は、解析器選択モジュール５４１５、再帰処理モジュール５４３０と接続されている。分離経路による画像分離モジュール４４２０は、図４５に例示した技術を用いて実現される。また、再帰処理モジュール５４３０によって再帰的に処理を行うこととなる。
再帰のない画像分離モジュール５４４０は、解析器選択モジュール５４１５と接続されている。再帰のない画像分離モジュール５４４０は、前述の＜Ｂ＞に記載の技術を用いて実現される。
【０１５５】
再帰処理モジュール５４３０は、分離経路による画像分離モジュール４４２０と接続されている。
図５６は、再帰処理モジュール５４３０による処理例を示すフローチャートである。状態に基づいて、再帰処理を行うか否かを判別する。
フローチャートに沿って説明する。
ステップＳ５６０２では、状態が多段落（状態＝＝Ｍ）であるか否かを判断し、「状態」変数が多段落である場合はステップＳ５６０６へ進み、それ以外の場合はステップＳ５６０４へ進む。
ステップＳ５６０４では、部分画像、方向、状態を出力する。
ステップＳ５６０６では、再帰的な処理を行うため、解析器選択モジュール５４１５へ受け付けた画像を渡す。
【０１５６】
単段落を再帰的に分離してしまうことを抑制するために、解析器選択モジュール５４１５は図５５に例示したフローチャート内のステップＳ５５０２では、以下の処理を行う。
図５７は、解析器選択モジュール５４１５による多段落判別の処理例（１）を示すフローチャートである。対象とする画像の縦横比を参照することで、多段落か否かを判別する例である。つまり、対象とする画像がθａｓｐｅｃｔ以上に細長いか否かで判別している。より具体的には、縦横比が予め定めた閾値（θａｓｐｅｃｔ）の範囲外であるとき、再帰のない画像分離モジュール５４４０へ画像を渡すため、状態をＰに更新する。なお、判別においては、ＷｉｄｔｈとＨｅｉｇｈｔの差分を利用してもよい。なお、図５７の例に示した変数は以下のことを表す。
対象とする画像の横幅  ：  Ｗｉｄｔｈ
対象とする画像の縦幅  ：  Ｈｅｉｇｈｔ
縦横比閾値  ：  θａｓｐｅｃｔ
【０１５７】
フローチャートに沿って説明する。
ステップＳ５７０２では、θａｓｐｅｃｔ−１＜Ｗｉｄｔｈ／Ｈｅｉｇｈｔ＜θａｓｐｅｃｔか否かを判断し、θａｓｐｅｃｔ−１＜Ｗｉｄｔｈ／Ｈｅｉｇｈｔ＜θａｓｐｅｃｔの場合はステップＳ５７０６へ進み、それ以外の場合はステップＳ５７０４へ進む。
ステップＳ５７０４では、状態が単段落（状態＝Ｐ）であることを出力し、画像を出力する。
ステップＳ５７０６では、状態が多段落（状態＝Ｍ）であることを出力し、画像を出力する。
【０１５８】
図５８は、解析器選択モジュール５４１５による多段落判別の処理例（２）を示すフローチャートである。対象とする画像がθｒｅｃｕｒｓｉｏｎ以上に複雑な文書構造を持たないことを利用している。つまり、再帰深さ（すなわち、対象とする画像はこれまで何回分離されているか）を保持・カウントし、予め定められた閾値（θｒｅｃｕｒｓｉｏｎ）との大小関係を比較することで、多段落か否かを判別する例である。再帰深さが閾値（θｒｅｃｕｒｓｉｏｎ）よりも大きくない場合、再帰のない画像分離モジュール５４４０へ画像を渡すため、状態をＰに更新する、なお、再帰深さのカウンタを部分画像と対として保持し、初期値は０として、これを再帰処理モジュール５４３０における処理で１つ加算すればよい。なお、図５８における変数は以下のことを表す。
再帰深さ  ：  θｒｅｃｕｒｓｉｏｎ
【０１５９】
フローチャートに沿って説明する。
ステップＳ５８０２では、再帰深さ＞θｒｅｃｕｒｓｉｏｎか否かを判断し、再帰深さ＞θｒｅｃｕｒｓｉｏｎの場合はステップＳ５８０６へ進み、それ以外の場合はステップＳ５８０４へ進む。
ステップＳ５８０４では、状態が単段落（状態＝Ｐ）であることを出力し、画像を出力する。
ステップＳ５８０６では、状態が多段落（状態＝Ｍ）であることを出力し、画像を出力する。
【０１６０】
なお、図５５に例示したステップＳ５５０２の多段落判別は、図５７、図５８に例示した処理フロー以外であってもよい。例えば、図５７、図５８に例示した処理フローを組み合わせてもよいし、さらに、投影分布、連結成分を利用するようにしてもよい。
【０１６１】
前述の実施の形態に前処理や後処理を付加した実施の形態を示す。ここでの実施の形態は、対象とする画像から、文字列切り出しを行うものである。
＜第Ｃ−４の実施の形態＞
図５９は、第Ｃ−４の実施の形態の構成例についての概念的なモジュール構成図である。
第Ｃ−４の実施の形態は、画像受付モジュール５９１０、前処理モジュール５９２０、文字切り出しモジュール５９３０を有している。
画像受付モジュール５９１０は、前処理モジュール５９２０と接続されており、図４２に例示した画像受付モジュール４２１０に該当する。また、画像５９００も図４２に例示した画像４２００に該当する。
前処理モジュール５９２０は、画像受付モジュール５９１０、文字切り出しモジュール５９３０と接続されており、画像受付モジュール５９１０が受け付けた画像５９００に対して、傾き補正、ノイズ除去、レイアウト解析等を行う。例えば、レイアウト解析で分離した部分画像を、文字切り出しモジュール５９３０へ渡す。
文字切り出しモジュール５９３０は、前処理モジュール５９２０と接続されており、前述の実施の形態（＜Ｂ＞の実施の形態を含む）で実現される。
【０１６２】
＜第Ｃ−５の実施の形態＞
図６０は、第Ｃ−５の実施の形態の構成例についての概念的なモジュール構成図である。
第Ｃ−５の実施の形態は、画像受付モジュール６０１０、文字切り出しモジュール６０２０、後処理モジュール６０３０を有している。
画像受付モジュール６０１０は、文字切り出しモジュール６０２０と接続されており、図４２に例示した画像受付モジュール４２１０に該当する。また、画像６０００も図４２に例示した画像４２００に該当する。
文字切り出しモジュール６０２０は、画像受付モジュール６０１０、後処理モジュール６０３０と接続されており、前述の実施の形態（＜Ｂ＞の実施の形態を含む）で実現される。
後処理モジュール６０３０は、文字切り出しモジュール６０２０と接続されており、文字切り出しモジュール６０２０によって分離された各文字列画像に対して、傾き補正、ノイズ除去、下線除去等を行う。
【０１６３】
＜実験結果Ｃ＞
＜Ｃ＞に示した実施の形態による実験結果を、この実施の形態を用いないで行った場合と比較して説明する。
まず、＜Ｃ＞に示した実施の形態を用いないで行った場合について説明する。
図６１は、多段落であるにもかかわらず単段落として処理してしまった場合の処理結果の例を示す説明図である。例えば、＜Ｂ＞に示した実施の形態による処理結果である。＜Ｂ＞に示した実施の形態は、単段落であることを前提として処理を行うものであるからである。したがって、方向の異なる複数の文字列を含む画像、又は複数の段落を含む画像に対して、文字列を正しく切り出せない場合がある。
図６１（ａ）に例示する画像は、タイトル部分の文字サイズの異なる文字列、横書きの段落、縦書きの段落が混在している多段落により構成されている文書の画像である。図６１（ｂ）に例示する画像は、図６１（ａ）に示す画像に対して、＜Ｂ＞に示した実施の形態の処理による文字列切り出し結果である。縦書きの段落は、文字列領域が正しく切り出されていない。
【０１６４】
図６２は、＜Ｃ＞に示した実施の形態による処理結果の例を示す説明図である。図６１（ａ）に例示した画像を対象としたものであり、タイトル部分の文字サイズの異なる文字列、横書きの段落、縦書きの段落の３つの領域に分離しており、タイトル部分は横書きの文字列として、横書きの段落内を横書きの文字列として、縦書きの段落内を縦書きの文字列として、それぞれ分離している。
【０１６５】
図６３を参照して、本実施の形態の画像処理装置のハードウェア構成例について説明する。図６３に示す構成は、例えばパーソナルコンピュータ（ＰＣ）などによって構成されるものであり、スキャナ等のデータ読み取り部６３１７と、プリンタなどのデータ出力部６３１８を備えたハードウェア構成例を示している。
【０１６６】
ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）６３０１は、前述の実施の形態において説明した各種のモジュール、すなわち、順方向経路情報算出モジュール１１１０、経路選択モジュール１１２０、逆方向経路情報算出モジュール１１３０、画像分離モジュール１７１０、分離経路算出モジュール３１２０、画像分離モジュール３１３０、水平方向分離経路算出モジュール３２２０、垂直方向分離経路算出モジュール３２３０、経路特徴量算出モジュール３２４０、分離方向判別モジュール３２５０、画像分離モジュール３４６０、解析器選択モジュール４２２０、分離経路算出モジュール４２３０、分離経路特徴量算出モジュール４２４０、主分離方向判別モジュール４２５０、主分離経路選択モジュール４２６０、画像分離モジュール４２７０、再帰処理モジュール４２８０、再帰のない画像分離モジュール４２９０等の各モジュールの実行シーケンスを記述したコンピュータ・プログラムにしたがった処理を実行する制御部である。
【０１６７】
ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）６３０２は、ＣＰＵ６３０１が使用するプログラムや演算パラメータ等を格納する。ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）６３０３は、ＣＰＵ６３０１の実行において使用するプログラムや、その実行において適宜変化するパラメータ等を格納する。これらはＣＰＵバスなどから構成されるホストバス６３０４により相互に接続されている。
【０１６８】
ホストバス６３０４は、ブリッジ６３０５を介して、ＰＣＩ（Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ／Ｉｎｔｅｒｆａｃｅ）バスなどの外部バス６３０６に接続されている。
【０１６９】
キーボード６３０８、マウス等のポインティングデバイス６３０９は、操作者により操作される入力デバイスである。ディスプレイ６３１０は、液晶表示装置又はＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）などがあり、各種情報をテキストやイメージ情報として表示する。
【０１７０】
ＨＤＤ（Ｈａｒｄ  Ｄｉｓｋ  Ｄｒｉｖｅ）６３１１は、ハードディスクを内蔵し、ハードディスクを駆動し、ＣＰＵ６３０１によって実行するプログラムや情報を記録又は再生させる。ハードディスクには、対象とする画像、経路情報、特徴量、文字列画像などが格納される。さらに、その他の各種のデータ処理プログラム等、各種コンピュータ・プログラムが格納される。
【０１７１】
ドライブ６３１２は、装着されている磁気ディスク、光ディスク、光磁気ディスク、又は半導体メモリ等のリムーバブル記録媒体６３１３に記録されているデータ又はプログラムを読み出して、そのデータ又はプログラムを、インタフェース６３０７、外部バス６３０６、ブリッジ６３０５、及びホストバス６３０４を介して接続されているＲＡＭ６３０３に供給する。リムーバブル記録媒体６３１３も、ハードディスクと同様のデータ記録領域として利用可能である。
【０１７２】
接続ポート６３１４は、外部接続機器６３１５を接続するポートであり、ＵＳＢ、ＩＥＥＥ１３９４等の接続部を持つ。接続ポート６３１４は、インタフェース６３０７、及び外部バス６３０６、ブリッジ６３０５、ホストバス６３０４等を介してＣＰＵ６３０１等に接続されている。通信部６３１６は、ネットワークに接続され、外部とのデータ通信処理を実行する。データ読み取り部６３１７は、例えばスキャナであり、ドキュメントの読み取り処理を実行する。データ出力部６３１８は、例えばプリンタであり、ドキュメントデータの出力処理を実行する。
【０１７３】
なお、図６３に示す画像処理装置のハードウェア構成は、１つの構成例を示すものであり、本実施の形態は、図６３に示す構成に限らず、本実施の形態において説明したモジュールを実行可能な構成であればよい。例えば、一部のモジュールを専用のハードウェア（例えば特定用途向け集積回路（Ａｐｐｌｉｃａｔｉｏｎ  Ｓｐｅｃｉｆｉｃ  Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ：ＡＳＩＣ）等）で構成してもよく、一部のモジュールは外部のシステム内にあり通信回線で接続しているような形態でもよく、さらに図６３に示すシステムが複数互いに通信回線によって接続されていて互いに協調動作するようにしてもよい。また、複写機、ファックス、スキャナ、プリンタ、複合機（スキャナ、プリンタ、複写機、ファックス等のいずれか２つ以上の機能を有している画像処理装置）などに組み込まれていてもよい。
【０１７４】
前述の実施の形態においては、対象とする画像として、１行の横書きの複数文字の画像とした例を用いて説明したが、もちろん縦書きの文字画像であってもよい。その場合、上方向、下方向とあるのは、右方向、左方向となる。また、文字画像の領域を分離する以外に、その他のオブジェクトの画像（例えば、写真内の人物画像、顔画像等）の領域を分離するのに用いてもよい。
前述の実施の形態においては、数式を用いて説明したが、数式には、その数式と同等のものが含まれる。同等のものとは、その数式そのものの他に、最終的な結果に影響を及ぼさない程度の数式の変形、又は数式をアルゴリズミックな解法で解くこと等が含まれる。
なお、前述の各種の実施の形態（実施例を含む）を組み合わせてもよく（例えば、ある実施の形態内のモジュールを他の実施の形態内に適用する、入れ替えする等も含む）、各モジュールの処理内容として背景技術で説明した技術を採用してもよい。
また、前述の各種の実施の形態の説明において、予め定められた値との比較において、「以上」、「以下」、「より大きい」、「より小さい（未満）」としたものは、その組み合わせに矛盾が生じない限り、それぞれ「より大きい」、「より小さい（未満）」、「以上」、「以下」としてもよい。
【０１７５】
なお、説明したプログラムについては、記録媒体に格納して提供してもよく、また、そのプログラムを通信手段によって提供してもよい。その場合、例えば、前記説明したプログラムについて、「プログラムを記録したコンピュータ読み取り可能な記録媒体」の発明として捉えてもよい。
「プログラムを記録したコンピュータ読み取り可能な記録媒体」とは、プログラムのインストール、実行、プログラムの流通などのために用いられる、プログラムが記録されたコンピュータで読み取り可能な記録媒体をいう。
なお、記録媒体としては、例えば、デジタル・バーサタイル・ディスク（ＤＶＤ）であって、ＤＶＤフォーラムで策定された規格である「ＤＶＤ−Ｒ、ＤＶＤ−ＲＷ、ＤＶＤ−ＲＡＭ等」、ＤＶＤ＋ＲＷで策定された規格である「ＤＶＤ＋Ｒ、ＤＶＤ＋ＲＷ等」、コンパクトディスク（ＣＤ）であって、読出し専用メモリ（ＣＤ−ＲＯＭ）、ＣＤレコーダブル（ＣＤ−Ｒ）、ＣＤリライタブル（ＣＤ−ＲＷ）等、ブルーレイ・ディスク（Ｂｌｕ−ｒａｙ  Ｄｉｓｃ（登録商標））、光磁気ディスク（ＭＯ）、フレキシブルディスク（ＦＤ）、磁気テープ、ハードディスク、読出し専用メモリ（ＲＯＭ）、電気的消去及び書換可能な読出し専用メモリ（ＥＥＰＲＯＭ）、フラッシュ・メモリ、ランダム・アクセス・メモリ（ＲＡＭ）等が含まれる。
そして、前記のプログラム又はその一部は、前記記録媒体に記録して保存や流通等させてもよい。また、通信によって、例えば、ローカル・エリア・ネットワーク（ＬＡＮ）、メトロポリタン・エリア・ネットワーク（ＭＡＮ）、ワイド・エリア・ネットワーク（ＷＡＮ）、インターネット、イントラネット、エクストラネット等に用いられる有線ネットワーク、あるいは無線通信ネットワーク、さらにこれらの組み合わせ等の伝送媒体を用いて伝送させてもよく、また、搬送波に乗せて搬送させてもよい。
さらに、前記のプログラムは、他のプログラムの一部分であってもよく、あるいは別個のプログラムと共に記録媒体に記録されていてもよい。また、複数の記録媒体に分割して
記録されていてもよい。また、圧縮や暗号化など、復元可能であればどのような態様で記録されていてもよい。
【符号の説明】
【０１７６】
４２１０…画像受付モジュール
４２２０…解析器選択モジュール
４２３０…分離経路算出モジュール
４２４０…分離経路特徴量算出モジュール
４２５０…主分離方向判別モジュール
４２６０…主分離経路選択モジュール
４２７０…画像分離モジュール
４２８０…再帰処理モジュール
４２９０…再帰のない画像分離モジュール
４４１０…画像受付モジュール
４４２０…分離経路による画像分離モジュール
４４３０…再帰処理モジュール
４５１０…水平方向分離経路算出モジュール
４５２０…垂直方向分離経路算出モジュール
４５３０…経路特徴量算出モジュール
４５４０…主分離方向判別モジュール
４５５０…主分離経路選択モジュール
４５６０…画像分離モジュール
５４１５…解析器選択モジュール
５４３０…再帰処理モジュール
５４４０…再帰のない画像分離モジュール
５９１０…画像受付モジュール
５９２０…前処理モジュール
５９３０…文字切り出しモジュール
６０１０…画像受付モジュール
６０２０…文字切り出しモジュール
６０３０…後処理モジュール
【図１】
0005577948.tif 000083
【図２】
0005577948.tif 000084
【図３】
0005577948.tif 000085
【図４】
0005577948.tif 000086
【図５】
0005577948.tif 000087
【図６】
0005577948.tif 000088
【図７】
0005577948.tif 000089
【図８】
0005577948.tif 000090
【図９】
0005577948.tif 000091
【図１０】
0005577948.tif 000092
【図１１】
0005577948.tif 000093
【図１２】
0005577948.tif 000094
【図１３】
0005577948.tif 000095
【図１４】
0005577948.tif 000096
【図１５】
0005577948.tif 000097
【図１６】
0005577948.tif 000098
【図１７】
0005577948.tif 000099
【図１８】
0005577948.tif 000100
【図１９】
0005577948.tif 000101
【図２０】
0005577948.tif 000102
【図２１】
0005577948.tif 000103
【図２２】
0005577948.tif 000104
【図２３】
0005577948.tif 000105
【図２４】
0005577948.tif 000106
【図２５】
0005577948.tif 000107
【図２６】
0005577948.tif 000108
【図２７】
0005577948.tif 000109
【図２８】
0005577948.tif 000110
【図２９】
0005577948.tif 000111
【図３０】
0005577948.tif 000112
【図３１】
0005577948.tif 000113
【図３２】
0005577948.tif 000114
【図３３】
0005577948.tif 000115
【図３４】
0005577948.tif 000116
【図３５】
0005577948.tif 000117
【図３６】
0005577948.tif 000118
【図３７】
0005577948.tif 000119
【図３８】
0005577948.tif 000120
【図３９】
0005577948.tif 000121
【図４０】
0005577948.tif 000122
【図４１】
0005577948.tif 000123
【図４２】
0005577948.tif 000124
【図４３】
0005577948.tif 000125
【図４４】
0005577948.tif 000126
【図４５】
0005577948.tif 000127
【図４６】
0005577948.tif 000128
【図４７】
0005577948.tif 000129
【図４８】
0005577948.tif 000130
【図４９】
0005577948.tif 000131
【図５０】
0005577948.tif 000132
【図５１】
0005577948.tif 000133
【図５２】
0005577948.tif 000134
【図５３】
0005577948.tif 000135
【図５４】
0005577948.tif 000136
【図５５】
0005577948.tif 000137
【図５６】
0005577948.tif 000138
【図５７】
0005577948.tif 000139
【図５８】
0005577948.tif 000140
【図５９】
0005577948.tif 000141
【図６０】
0005577948.tif 000142
【図６１】
0005577948.tif 000143
【図６２】
0005577948.tif 000144
【図６３】
0005577948.tif 000145