JP2018081674A

JP2018081674A - 手書きテキスト画像に対する行及び単語切り出し方法

Info

Publication number: JP2018081674A
Application number: JP2017159043A
Authority: JP
Inventors: ドゥアンドゥアンヤン，; Duanduan Yang
Original assignee: Konica Minolta Laboratory USA Inc
Current assignee: Konica Minolta Laboratory USA Inc
Priority date: 2016-09-29
Filing date: 2017-08-22
Publication date: 2018-05-24
Anticipated expiration: 2037-08-22
Also published as: US10062001B2; US10643094B2; US20180330181A1; JP6951905B2; US20180089525A1

Abstract

【課題】手書きテキストを含む画像を行単位及び単語単位に切り出す方法を提供する。【解決手段】画像を、第１の比で水平方向にダウンサンプリングする。ダウンサンプリングされた画像中の接続領域を検出する。水平方向に隣接する接続領域同士を結合して行を形成し、元の画像を行画像に切り出す。各行画像を、第１の比よりも小さな第２の比で、水平方向にダウンサンプリングする。ダウンサンプリングされた行画像中の接続領域を検出して、可能な単語切り出し位置を取得する。パスは、可能な単語切り出し位置の一部又は全てで行を複数のパス切り出しに分割する態様である。全ての可能なパスのそれぞれについて、各パス切り出しに単語認識をかけて単語認識スコアを算出し、そのパスに対する平均単語認識スコアを算出する。最もスコアが高いパスから、最終的な単語単位が得られる。【選択図】図１

Description

本発明は、手書きテキストを認識する方法に関し、より詳細には、手書きテキスト画像から行及び単語を切り出す方法に関する。

手書き文字認識は、人工知能の分野で重要な役割を担っている。手書き文字認識は、コンピューターが紙文書、写真、タッチスクリーン、及び他の機器などの情報源から理解可能な手書きの入力を受け取り解釈する能力を意味している。テキストを含む画像の処理には、例えば、テキスト認識にかける前に、画像からテキスト領域を抽出すること、その領域からテキストの行を抽出すること（行切り出し）、次いで、行からテキストの単語を抽出すること（単語切り出し）が含まれることがある。

手書きテキストの場合、手書き文字には多くのばらつきがあるので、行及び単語の切り出しは、しばしば困難を伴う。この課題に対して、幾つかの方法が提案されてきた。例えば、「Post-OCR image segmentation into spatially separated text zones（空間的に分離されたテキスト区域へのＯＣＲ後の画像の切り出し）」と題された米国特許出願公開第２００７／００４１６４２号明細書は、「文書画像から光学式文字読取装置（ＯＣＲ）によって認識されたテキストを区域にグループ分けするための認識後の手順」について記載している。「認識されたテキスト、及びテキストの各単語の対応する単語境界ボックスを一旦受け取ると、記載された手順は、ある倍率だけこれらの単語境界ボックスを拡張し、交差する単語境界ボックスを記録する。２つの単語境界ボックスは、対応する単語同士が元の文書で互いに非常に近接している場合には、拡張時に交差することになる。次いで、２つの単語は、それらの単語境界ボックスが拡張時に交差する場合には同一の区域に属するというルールを用いて、テキストを区域にグループ分けする。このように識別されたテキスト区域は、並べ替えられて、戻される。」（要約）

「Language-independent and segmentation-free optical character recognition system and method（言語に依存せずかつ切り出しのない光学式文字認識システム及び方法）」と題された米国特許第５９３３５２５号明細書は、「独自の特徴抽出手法を含む言語に依存せずかつ切り出しのないＯＣＲシステム及び方法」について記載しており、「この手法は、ＯＣＲに関する２次元データを１つの独立変数（具体的には、行方向のテキストの行内での位置）として表わし、その結果、ＨＭＭに基づく同一のＣＳＲ技術を直接的に適合して光学文字を認識することができるようになる。行の発見段階の後に、単純な特徴抽出段階が続き、システムは市販のＣＳＲシステムを僅かに変更して又は全く変更せずに利用して、システムによるテキストの認識及びシステムのトレーニングを行うことができる。特徴抽出、トレーニング、及び認識のコンポーネントを含むシステム全体が、認識されるテキストの原稿又は言語からは独立しているように設計される。システムの言語に依存する部分は、辞書及びトレーニングデータに限定される。更に、この認識方法は、トレーニングのためにも又は認識のためにも、文字レベル及び／又は単語レベルでのデータの事前切り出しを必要としない。加えて、例えば、スペルチェックで一般的に行われるように後処理としてではなく、認識処理の不可欠な一部として言語モデルを使用して、システムの性能を向上させることができる。」（要約）

「Picture words segmentation method（画像化された単語の切り出し方法）」と題された中国特許出願公開第ＣＮ１００５２７１５６Ｃ号明細書は、「テキスト画像を検出する方法」について記載しており、「この方法は、（１）各色成分のエッジマップに関して合成されたピクチャが累積エッジマップを取得する工程と、（２）累積エッジマップのクラスタリングが数枚のサブエッジマップシートに分割され、各サブエッジマップが類似の色エッジポイントを含んだ状態で、色ポイントエッジに応じて、それぞれの色のピクチャ内でエッジポイントに対して累積エッジマップが設定される工程と、（３）画像領域中でテキストを位置決めしながら、垂直方向での局所的投影及び水平方向の切り出しに従って、各サブエッジマップにおいて、複数回の水平投影及び垂直投影を行う工程と、を含む。本発明では、累積エッジマップの色を数枚のサブエッジマップに分割することに基づいたクラスタリング手法を用いて、元の累積エッジマップを取得した後で、サブエッジのエッジマップは単純化され、その結果、検出領域は比較的に単純なテキストピクチャになり、また正確になる。」（要約）

本発明は、手書きテキストを切り出すための、行切り出し及び単語切り出し方法に関する。

本発明の目的は、精度と効率とのつり合いが取れた、テキスト行及び単語を切り出すための方法を提供することである。

上記の目的に鑑みて本発明は、テキストを含む２値画像である入力画像を行単位及び単語単位に切り出す、コンピューター上で実行される方法であって、（ａ）第１のダウンサンプリング比を用いて前記入力画像を水平方向にダウンサンプリングする工程と、（ｂ）工程（ａ）で取得された前記ダウンサンプリングされた画像中の接続領域を検出する工程と、（ｃ）同一の行に属する水平方向に隣接する接続領域を特定して、そのような水平方向に隣接する接続領域を含む行リストを形成する工程と、（ｄ）前記入力画像を複数の行単位に切り出す工程であって、各行単位は工程（ｃ）で取得された対応する行リスト内の全ての接続領域を含む前記ダウンサンプリングされた画像中の境界ボックスに対応する前記入力画像の領域である、工程と、工程（ｄ）で取得された前記行単位のそれぞれについて、（ｅ）第２のダウンサンプリング比を用いて前記行単位を水平方向にダウンサンプリングする工程と、（ｆ）工程（ｅ）で取得された前記ダウンサンプリングされた行単位内の接続領域を検出する工程と、（ｇ）工程（ｄ）から取得された前記行単位を、工程（ｆ）で取得された前記接続領域を用いて単語単位に切り出す工程と、を含み、前記第２のダウンサンプリング比は前記第１のダウンサンプリング比よりも小さい、方法を提供する。

本発明のその他の側面によれば、本発明はコンピューターと一以上のプリンターを含むデータ処理システムを制御するコンピューターに上記の方法を実行させるコンピュータープログラムを提供する。

本発明のその他の側面によれば、本発明は上記の方法を実行するＣＰＵを備えるデータ処理装置を提供する。

本発明の更なる特徴及び利点が、以降に続く明細書の中で記載され、その一部が明細書の記載から明らかになるか、又は、本発明を実施することにより学ぶことができる。本発明の目的及び他の利点が、添付の図面並びに明細書及び特許請求の範囲の記載の中で特に示された構造によって実現され、達成される。

なお、前述の全般的な説明及び以降の詳細な説明は両方とも例示的かつ説明的なものであり、特許請求される本発明の更なる説明を提供するように意図されている。

本発明の一実施形態による行切り出し及び単語切り出しを含む手書きテキスト切り出し方法を概略的に示すフローチャートである。本発明の一実施形態による行切り出し及び単語切り出しを含む手書きテキスト切り出し方法を概略的に示すフローチャートである。本発明の実施形態における例示的なテキスト画像の水平方向のダウンサンプリングを概略的に示す図である。図３のテキスト画像の例示的な行切り出しを概略的に示す図である。図３のテキスト画像の例示的な水平方向のダウンサンプリングを概略的に示す図である。本発明の一実施形態による単語切り出しで使用されるパスの例を概略的に示す図である。本発明の一実施形態による単語切り出しで使用されるパスの例を概略的に示す図である。本発明の実施形態を実施することができるコンピューターシステムのブロック図である。

本発明の実施形態による手書きテキスト切り出し方法は、まず行切り出しを実施して入力テキスト画像を行に切り出し、次いで、単語切り出しを実施して各行を単語に切り出す。行切り出しを実施するために、入力画像は第１のダウンサンプリング比を用いて水平方向にダウンサンプリングされ、その結果、ダウンサンプリングされた画像の同一行内のテキストは、図３の例に示すように、互いにぴたりとくっつく傾向がある。ダウンサンプリングされた画像内の接続領域が検出され、この接続領域を使用して元の画像中で行が検出されて行が切り出される。次いで、元の入力画像の切り出された行のそれぞれが、第２のダウンサンプリング比を用いて水平方向にダウンサンプリングされ、この第２のダウンサンプリング比は第１のダウンサンプリング比よりも小さく、かつ異なる行に対して異なっていてもよく、その結果、ダウンサンプリングされた行画像中の単一の単語のそれぞれからのテキスト文字は、互いにぴたりとくっつく傾向がある。ダウンサンプリングされた行単位中の接続領域が検出され、これを使用して単語が検出され、行単位が単語単位に切り出される。

本発明の実施形態による手書きテキスト切り出し方法を、図１及び図２のフローチャートを参照して、更に詳細に説明する。入力画像を取得する工程（工程Ｓ１０１）は、元の画像がカラー画像か又はグレースケール画像である場合には、元の画像を２値化することを含むことができる。以下の説明では、入力画像は２値画像である。入力画像は純粋なテキスト画像であり、即ち、入力画像はテキストを含んでいるが、写真又は図形などの他のオブジェクトは含まず、また、テキストは表、フローチャート、又は他の種類の図中に分散していないことを意味する。以下の説明では、テキスト行は、水平方向又はほぼ水平の方向にあることが想定されている。当業者は、この方法を、垂直方向又はほぼ垂直の方向にあるテキスト行を扱うように容易に修正することができることを理解しうるであろう。

まず、第１のダウンサンプリング比Ｎを算出し（工程Ｓ１０２）、この第１のダウンサンプリング比を用いて、入力画像を水平方向にダウンサンプリングする（工程Ｓ１０３）。言い換えると、入力画像中の画素のＮ番目毎の垂直列を、水平方向にダウンサンプリングされた画像を形成するのに用いる。第１のダウンサンプリング比Ｎは、以下のように算出される（工程Ｓ１０２）。

入力画像中の接続領域を検出する。２値画像では、接続領域（時には接続コンポーネントとも呼ばれる）は、互いに接続された前景画素（例えば、白色の背景画像上の黒色テキストに対する黒色画素）のグループである。接続領域を検出するために、任意の適切な方法を使用することができる。水平に隣接する接続領域の各対の間の水平距離を決定する。そのような距離の全ての平均値を算出し、算出した平均距離に基づいて、第１のダウンサンプリング比Ｎを設定する。好ましい実施形態では、第１のダウンサンプリング比Ｎは、平均距離の３倍に等しい。

上記の計算では、２つの接続領域は、垂直位置が所定の閾値以下だけ互いに異なっており、かつ、他の接続領域によって分離されていない場合には、水平に隣接しているものとみなされる。水平に隣接した２つの接続領域間の距離は、この２つの接続領域の２つのそれぞれの境界ボックス間の距離として規定することができる。接続領域の境界ボックスとは、その接続領域を完全に包含する最小の矩形のボックスである。

工程Ｓ１０３では、入力画像を水平にのみダウンサンプリングすることが好ましいが、垂直方向に対するダウンサンプリング比が水平方向に対するダウンサンプリング比よりもはるかに小さい場合には、水平方向のダウンサンプリングに加えて垂直方向のダウンサンプリングを実行してもよい。

水平方向のダウンサンプリング（工程Ｓ１０３）の後、水平方向にダウンサンプリングされた画像中の全ての接続領域を検出し（工程Ｓ１０４）、それらの対応する境界ボックスを生成し、１つの集合（集合Ａ）に記憶する。

検出された接続領域を、水平方向に互いに結合する（工程Ｓ１０５）。同一の行に属する水平方向に隣接する接続領域を特定して、そのような水平方向の隣同士のリストを作成することにより、水平方向の結合を行う。

より具体的には、特定の接続領域について、別の接続領域が、（１）所定の閾値未満の量だけ、この特定の接続領域の垂直位置からオフセットされた垂直位置を有し、（２）基準（１）を満たす接続領域の全ての中で、この特定の接続領域の左又は右に最も近い位置にある場合、この他の接続領域を、特定の接続領域と同じ行に位置する水平方向の隣の接続領域であるとみなす。この結合工程を実施するために、集合Ａからランダムに選択される接続領域であり得る接続領域Ｃから開始して、探索を実行して、上述の基準を満たす水平方向の隣の接続領域を見つける（そのような隣の接続領域は、ゼロ、１つ、又は２つ存在することがある）。そのようにして発見された水平方向の隣の接続領域を、接続領域Ｃを含む行リストに追加する。既に発見された水平方向の隣の接続領域のそれぞれを現在の接続領域として使用して探索を再び実行し、同じ行の追加の接続領域を見つける。上記の基準を満たす接続領域が見つからなくなるまで、探索を続ける。既に発見された接続領域を、集合Ａから削除する。そのような探索は、グラフを探索するための幅優先探索アルゴリズムの概念と類似している。結果として、１つの行リストが生成され、このリストは、接続領域Ｃ、及び探索で発見された他の接続領域を含む。次いで、集合Ａの残りの接続領域から別の接続領域をランダムに選択し、上述の探索を実行して別の行リストを生成する。これを、集合Ａが空になるまで続ける。結果として、いくつかの行リストを生成する。

入力画像を、水平方向に結合された接続領域の行リストを用いて行に切り出す（工程Ｓ１０６）。より具体的には、各行リストについて、その行リスト内の全ての接続領域を囲む境界ボックスを、ダウンサンプリングされた画像中に生成する。ダウンサンプリングされた画像中のそのような境界ボックスの例を、図４の左側に示す。元の（ダウンサンプリングする前の）画像中に、対応する境界ボックスを生成する。この境界ボックスは、元の画像の行単位を構成する。元の画像中のそのような境界ボックスの例を、図４の右側に示す。結果として、複数の行単位を生成する。

単語切り出しを実施するために、個々の行単位のそれぞれ（即ち、１つの行の境界ボックス内に含まれる画像パッチ）を、第２のダウンサンプリング比Ｍｉを使用して水平方向にダウンサンプリングする。ここで、ｉは、行のインデックスである（工程Ｓ１０７〜Ｓ１０９）。より具体的には、各行単位に対して（工程Ｓ１０７）、第２のダウンサンプリング比Ｍｉを決定し（工程Ｓ１０８）、この第２のダウンサンプリング比Ｍｉを用いて、その行画像を水平方向にダウンサンプリングする（工程Ｓ１０９）。言い換えると、行単位中の画素のＭｉ番目毎の垂直列を、水平方向にダウンサンプリングされた行単位を形成するために用いる。図５は、テキスト行のダウンサンプリングの一例を示す。

一実施形態では、工程Ｓ１０８で、第２のダウンサンプリング比Ｍｉを以下のようにして決定する。行単位内の接続領域を検出し、水平方向に隣接する接続領域の各対の間の水平距離を決定し、そのような距離の全てについて平均値を算出し、算出された平均距離に基づいて第２のダウンサンプリング比Ｍｉを設定する。好ましい実施形態では、第２のダウンサンプリング比Ｍｉは、平均距離に等しい。

工程Ｓ１０９では、行画像を水平にのみダウンサンプリングすることが好ましいが、垂直方向に対するダウンサンプリング比が水平方向に対するダウンサンプリング比よりもはるかに小さい場合には、水平方向のダウンサンプリングに加えて垂直方向のダウンサンプリングを実行してもよい。

次いで、処理Ｓ１１０を実施して、各行を単語単位に切り出す。この処理について、図２を参照して以下で説明する。

まず、ダウンサンプリングされた行単位における接続領域を検出し、それらの接続領域を使用して、元の（ダウンサンプリングする前の）行単位における可能な単語切り出し位置を決定する（工程Ｓ２０１）。元の行単位における可能な単語切り出し位置は、ダウンサンプリングされた行単位における接続領域同士の間の間隙の位置に対応する位置に設定する。言い換えると、可能な単語切り出し位置同士の間のテキスト内容は、ダウンサンプリングされた行単位において検出された接続領域に対応する。

次いで、以下でより詳細に説明するパススコア比較手法を用いて、元の行単位に関して単語切り出しを行う。

パスとは、行を複数の切り出し（便宜上「パス切り出し」と呼ばれる）に分割するために、行単位を、可能な単語切り出し位置の全て又は一部で分割する態様である。例えば、図６Ａに示す例では、テキスト行単位は９つの可能な単語切り出し位置を有する。図６Ｂの各例は、パスを概略的に示している。例示的なパス（ｌ）では、行単位は、９つの可能な単語切り出し位置の全てで分割されている。例示的なパス（ｎ）では、行単位は１番目を除く全ての可能な単語切り出し位置で分割されている（そのため、１番目及び２番目の接続領域が１つのパス切り出しになっている）。例示的なパス（ｍ）では、行単位は、５番目を除く全ての可能な単語切り出し位置で分割されている（そのため、５番目と６番目の接続領域は１つのパス切り出しになっている）、等である。

パスはまた、隣接する接続領域の一部又は全てを結合する態様としても捉えることができる。従って、例示的なパス（ｌ）は、各接続領域がパス切り出しである（結合がない）パスである。例示的なパス（ｎ）は、１番目と２番目の接続領域が結合されて１つのパス切り出しになるパスである。例示的なパス（ｍ）は、５番目と６番目の接続領域が結合されて１つのパス切り出しになるパスである、等である。

より広い意味では、画像の「パス」は、画像の全ての画素をカバーする一連の画像切り出しからなり、各切り出しは、入力画像において異なっており重複しない複数の画素を含む。

パススコア比較は、可能な単語切り出し位置に基づいて、行に形成され得る全ての可能なパスを評価する。各パスについて（工程Ｓ２０２及び工程Ｓ２０６）、各パス切り出しに単語認識をかけて単語認識スコアを算出し（工程Ｓ２０３）、全てのパス切り出しに対するスコアを平均して、そのパスに対する平均単語認識スコアを算出する（工程Ｓ２０４）。単語認識とは、画像切り出しが単語である可能性を表すスコアを決定するために、画像パッチをサンプルの集合と比較する処理である。この工程のために、任意の適切な単語認識アルゴリズムを使用することができる。全ての可能なパスについて、平均単語認識スコアを算出する（工程Ｓ２０５）。全ての可能なパスの中で平均単語認識スコアが最も高いパスを、その行に対する最終的な単語単位であると決定し（工程Ｓ２０７）、これに応じて、その行画像を単語画像に切り出す（工程Ｓ２０８）。

例えば、図６Ｂの例では、パス切り出し「that many」は単語ではなく、「nvolve」も単語ではないので、パス（ｎ）はパス（ｌ）よりもスコアが低くなり、パス（ｌ）はパス（ｍ）よりもスコアが低くなる。パス（ｍ）が、全ての可能なパスの中でスコアが最も高いパスでありそうである。

パススコア法を使用する目的は、入力画像中のどの単語が最も高い精度で認識され得るかに基づいて最適なパスを見つけ、それによって手書き文字認識の精度を高めることである。

図１に戻って、工程Ｓ１０７からＳ１１０を、各行単位に対して繰り返す（工程Ｓ１１１）。

図７は、本発明の実施形態を実施することができる例示的なコンピューターのブロック図である。図７に示すように、このコンピューター１０は、中央演算処理装置（ＣＰＵ）１０１、メモリー１０２、キーボード又はタブレットスタイラスペンなどの入力部１０３、コンピューターのモニター又はタッチスクリーンディスプレイなどの表示部１０４、及びネットワークインターフェース１０５を備えており、（図示していないものを含めて）これらの構成要素の全ては、バス１０６を介して互いに内部的に通信している。コンピューター１０は、ネットワークインターフェース１０５を介して、ＬＡＮ又はＷＡＮなどのネットワーク２０に接続され、ネットワークに接続された他の機器と通信する。

通常、メモリー１０２は、ＣＰＵ１０１にとってアクセス可能なコンピューター実行可能命令又はソフトウェアプログラムを記憶し、ＣＰＵ１０１は、動作時に必要に応じてこれらのソフトウェアプログラムを実行するように構成される。そのようなソフトウェアプログラムは、Windows OS、Macintosh OS、Unix X Windows、又は、ディスプレイモニターと結合された、タッチスクリーン並びに／若しくはマウス及びキーボードなどのＧＵＩ（グラフィカルユーザインターフェース）を実装する他の一般に普及しているコンピューターオペレーティングシステム上で実行されるように設計されていることが好ましい。一実施形態では、メモリー１０２内のそのようなソフトウェアはプログラム１０８を含み、このプログラム１０８は、ＣＰＵ１０１によって実行されると、上述の行及び単語切り出し方法を実行する。認識プログラム１０８に加えて、ＣＰＵ１０１は、他の種類のソフトウェア（例えば、管理ソフトウェア）、アプリケーション（例えば、ネットワーク通信アプリケーション）、オペレーティングシステム等を実行するようにも構成される。

手書きテキスト画像を処理する上述の行及び単語切り出し方法において、並びに本発明の関連する装置及びシステムにおいて、様々な修正及び変形を、本発明の趣旨又は範囲から逸脱することなく加え得ることが、当業者には明らかであろう。従って、本発明は、添付の特許請求の範囲及びそれらの均等物の範囲内にある修正及び変形を包含することが意図されている。

Claims

テキストを含む２値画像である入力画像を行単位及び単語単位に切り出す、コンピューター上で実行される方法であって、
（ａ）第１のダウンサンプリング比を用いて前記入力画像を水平方向にダウンサンプリングする工程と、
（ｂ）工程（ａ）で取得された前記ダウンサンプリングされた画像中の接続領域を検出する工程と、
（ｃ）同一の行に属する水平方向に隣接する接続領域を特定して、そのような水平方向に隣接する接続領域を含む行リストを形成する工程と、
（ｄ）前記入力画像を複数の行単位に切り出す工程であって、各行単位は工程（ｃ）で取得された対応する行リスト内の全ての接続領域を含む前記ダウンサンプリングされた画像中の境界ボックスに対応する前記入力画像の領域である、工程と、
工程（ｄ）で取得された前記行単位のそれぞれについて、
（ｅ）第２のダウンサンプリング比を用いて前記行単位を水平方向にダウンサンプリングする工程と、
（ｆ）工程（ｅ）で取得された前記ダウンサンプリングされた行単位内の接続領域を検出する工程と、
（ｇ）工程（ｄ）から取得された前記行単位を、工程（ｆ）で取得された前記接続領域を用いて単語単位に切り出す工程と、を含み、
前記第２のダウンサンプリング比は前記第１のダウンサンプリング比よりも小さい、方法。
前記第１のダウンサンプリング比は前記入力画像から算出され、各行単位に対する前記第２のダウンサンプリング比は前記行単位から算出される、請求項１に記載の方法。
工程（ａ）の前に、前記第１のダウンサンプリング比を算出する工程を更に含み、この工程は、
（ｈ１）前記入力画像中の接続領域を検出する工程と、
（ｈ２）工程（ｈ１）で検出された水平に隣接する接続領域の各対の間の水平距離を算出する工程と、
（ｈ３）工程（ｈ２）で算出された水平距離の全てについての平均である第１の平均水平距離を算出する工程と、
（ｈ４）工程（ｈ３）で算出された前記第１の平均水平距離に基づいて、前記第１のダウンサンプリング比を設定する工程と、を含む、請求項１又は２に記載の方法。
工程（ｈ４）で、前記第１のダウンサンプリング比は、前記第１の平均水平距離の３倍に等しい、請求項３に記載の方法。
工程（ｅ）の前に、前記第２のダウンサンプリング比を算出する工程を更に含み、この工程は、
（ｉ１）工程（ｄ）で取得された前記行単位内の接続領域を検出する工程と、
（ｉ２）工程（ｉ１）で取得された水平に隣接する接続領域の各対の間の水平距離を算出する工程と、
（ｉ３）工程（ｉ２）で算出された水平距離の全てについての平均である第２の平均水平距離を算出する工程と、
（ｉ４）工程（ｉ３）で算出された前記第２の平均水平距離に基づいて、前記第２のダウンサンプリング比を設定する工程と、を含む、請求項１〜４のいずれか一項に記載の方法。
工程（ｉ４）で、前記第２のダウンサンプリング比は、前記第２の平均水平距離に等しい、請求項５に記載の方法。
工程（ｃ）は、
（ｃ１）工程（ｂ）で検出された全ての接続領域を集合にまとめる工程と、
（ｃ２）前記集合から前記接続領域のうちの１つを選択する工程と、
（ｃ３）前記選択された接続領域の水平方向の隣の接続領域を探索する工程であって、水平方向の隣の接続領域は、（１）所定の閾値未満の量だけ前記選択された接続領域の垂直位置からオフセットされた垂直位置を有し、（２）基準（１）を満たす前記接続領域の全ての中で、前記選択された接続領域に対して水平方向に最も近い位置にある、接続領域である工程と、
（ｃ４）前記選択された接続領域を含む行リストに、工程（ｃ３）の前記探索で検出された任意の水平方向の隣の接続領域を追加し、前記水平方向の隣の接続領域を前記集合から削除する工程と、
（ｃ５）工程（ｃ３）で検出された前記水平方向の隣の接続領域について、前記探索する工程（ｃ３）及び前記追加し削除する工程（ｃ４）を、探索で水平方向の隣の接続領域が見つからなくなるまで繰り返し、それによって行リストを生成する工程と、
（ｃ６）前記集合から別の接続領域を選択し、前記集合が空になるまで、工程（ｃ３）、（ｃ４）、及び（ｃ５）を繰り返して別の行リストを生成する工程と、を含み、
これによって、複数の行リストを生成する、請求項１〜６のいずれか一項に記載の方法。
工程（ｇ）は、
工程（ｆ）で検出された前記接続領域に基づいて、前記行単位に対して複数の可能な単語切り出し位置を決定する工程であって、各可能な単語切り出し位置は、前記ダウンサンプリングされた行単位内の接続領域同士の間の間隙の位置に対応する工程と、
前記行単位に対して、全ての可能なパスを規定する工程であって、各パスは、前記行単位を複数のパス切り出しに分割する前記可能な単語切り出し位置の全て又は一部で前記行単位を分割したものである工程と、
各パスについて、各パス切り出しに単語認識をかけて前記パス切り出しに対する単語認識スコアを算出し、全ての前記パス切り出しに対する単語認識スコアを平均して、前記パスに対する平均単語認識スコアを算出する工程と、
前記行単位に対する全ての可能なパスの中で、平均単語認識スコアが最も高いパスを判定する工程と、
前記判定されたパスに従って、前記行単位を単語単位に切り出す工程と、を含む、請求項１〜７のいずれか一項に記載の方法。
データ処理装置を制御するコンピューターに、テキストを含む２値画像である入力画像を行単位及び単語単位に切り出す処理を実行させるコンピュータープログラムであって、前記処理は、
（ａ）第１のダウンサンプリング比を用いて前記入力画像を水平方向にダウンサンプリングする工程と、
（ｂ）工程（ａ）で取得された前記ダウンサンプリングされた画像中の接続領域を検出する工程と、
（ｃ）同一の行に属する水平方向に隣接する接続領域を特定して、そのような水平方向に隣接する接続領域を含む行リストを形成する工程と、
（ｄ）前記入力画像を複数の行単位に切り出す工程であって、各行単位は、工程（ｃ）で取得された対応する行リスト内の全ての接続領域を含む前記ダウンサンプリングされた画像中の境界ボックスに対応する、前記入力画像の領域である、工程と、
工程（ｄ）で取得された前記行単位のそれぞれについて、
（ｅ）第２のダウンサンプリング比を用いて前記行単位を水平方向にダウンサンプリングする工程と、
（ｆ）工程（ｅ）で取得された前記ダウンサンプリングされた行単位内の接続領域を検出する工程と、
（ｇ）工程（ｄ）から取得された前記行単位を、工程（ｆ）で取得された前記接続領域を用いて単語単位に切り出す工程と、を含み、
前記第２のダウンサンプリング比は前記第１のダウンサンプリング比よりも小さい、コンピュータープログラム。
前記第１のダウンサンプリング比は前記入力画像から算出され、各行単位に対する前記第２のダウンサンプリング比は前記行単位から算出される、請求項９に記載のコンピュータープログラム。
前記処理は、工程（ａ）の前に、前記第１のダウンサンプリング比を算出する工程を更に含み、この工程は、
（ｈ１）前記入力画像中の接続領域を検出する工程と、
（ｈ２）工程（ｈ１）で検出された水平に隣接する接続領域の各対の間の水平距離を算出する工程と、
（ｈ３）工程（ｈ２）で算出された水平距離の全てについての平均である第１の平均水平距離を算出する工程と、
（ｈ４）工程（ｈ３）で算出された前記第１の平均水平距離に基づいて、前記第１のダウンサンプリング比を設定する工程と、を含む、請求項９又は１０に記載のコンピュータープログラム。
工程（ｈ４）で、前記第１のダウンサンプリング比は、前記第１の平均水平距離の３倍に等しい、請求項１１に記載のコンピュータープログラム。
前記処理は、工程（ｅ）の前に、前記第２のダウンサンプリング比を算出する工程を更に含み、この工程は、
（ｉ１）工程（ｄ）で取得された前記行単位内の接続領域を検出する工程と、
（ｉ２）工程（ｉ１）で取得された水平に隣接する接続領域の各対の間の水平距離を算出する工程と、
（ｉ３）工程（ｉ２）で算出された水平距離の全てについての平均である第２の平均水平距離を算出する工程と、
（ｉ４）工程（ｉ３）で算出された前記第２の平均水平距離に基づいて、前記第２のダウンサンプリング比を設定する工程と、を含む、請求項９〜１２のいずれか一項に記載のコンピュータープログラム。
工程（ｉ４）で、前記第２のダウンサンプリング比は、前記第２の平均水平距離に等しい、請求項１３に記載のコンピュータープログラム。
工程（ｃ）は、
（ｃ１）工程（ｂ）で検出された全ての接続領域を集合にまとめる工程と、
（ｃ２）前記集合から前記接続領域のうちの１つを選択する工程と、
（ｃ３）前記選択された接続領域の水平方向の隣の接続領域を探索する工程であって、水平方向の隣の接続領域は、（１）所定の閾値未満の量だけ前記選択された接続領域の垂直位置からオフセットされた垂直位置を有し、（２）基準（１）を満たす前記接続領域の全ての中で、前記選択された接続領域に対して水平方向に最も近い位置にある、接続領域である工程と、
（ｃ４）前記選択された接続領域を含む行リストに、工程（ｃ３）の前記探索で検出された任意の水平方向の隣の接続領域を追加し、前記水平方向の隣の接続領域を前記集合から削除する工程と、
（ｃ５）工程（ｃ３）で検出された前記水平方向の隣の接続領域について、前記探索する工程（ｃ３）及び前記追加し削除する工程（ｃ４）を、探索で水平方向の隣の接続領域が見つからなくなるまで繰り返し、それによって行リストを生成する工程と、
（ｃ６）前記集合から別の接続領域を選択し、前記集合が空になるまで、工程（ｃ３）、（ｃ４）、及び（ｃ５）を繰り返して別の行リストを生成する工程と、を含み、
これによって、複数の行リストを生成する、請求項９〜１４のいずれか一項に記載のコンピュータープログラム。
工程（ｇ）は、
工程（ｆ）で検出された前記接続領域に基づいて、前記行単位に対して複数の可能な単語切り出し位置を決定する工程であって、各可能な単語切り出し位置は、前記ダウンサンプリングされた行単位内の接続領域同士の間の間隙の位置に対応する工程と、
前記行単位に対して、全ての可能なパスを規定する工程であって、各パスは、前記行単位を複数のパス切り出しに分割する前記可能な単語切り出し位置の全て又は一部で前記行単位を分割したものである工程と、
各パスについて、各パス切り出しに単語認識をかけて前記パス切り出しに対する単語認識スコアを算出し、全ての前記パス切り出しに対する単語認識スコアを平均して、前記パスに対する平均単語認識スコアを算出する工程と、
前記行単位に対する全ての可能なパスの中で、平均単語認識スコアが最も高いパスを判定する工程と、
前記判定されたパスに従って、前記行単位を単語単位に切り出す工程と、を含む、請求項９〜１５のいずれか一項に記載のコンピュータープログラム。
データ処理装置であって、
入力画像を行単位及び単語単位に切り出す処理を実行するＣＰＵを備え、前記処理は、
（ａ）第１のダウンサンプリング比を用いて前記入力画像を水平方向にダウンサンプリングする工程と、
（ｂ）工程（ａ）で取得された前記ダウンサンプリングされた画像中の接続領域を検出する工程と、
（ｃ）同一の行に属する水平方向に隣接する接続領域を特定して、そのような水平方向に隣接する接続領域を含む行リストを形成する工程と、
（ｄ）前記入力画像を複数の行単位に切り出す工程であって、各行単位は、工程（ｃ）で取得された対応する行リスト内の全ての接続領域を含む前記ダウンサンプリングされた画像中の境界ボックスに対応する、前記入力画像の領域である、工程と、
工程（ｄ）で取得された前記行単位のそれぞれについて、
（ｅ）第２のダウンサンプリング比を用いて前記行単位を水平方向にダウンサンプリングする工程と、
（ｆ）工程（ｅ）で取得された前記ダウンサンプリングされた行単位内の接続領域を検出する工程と、
（ｇ）工程（ｄ）から取得された前記行単位を、工程（ｆ）で取得された前記接続領域を用いて単語単位に切り出す工程と、を含み、
前記第２のダウンサンプリング比は前記第１のダウンサンプリング比よりも小さい、データ処理装置。
前記第１のダウンサンプリング比は前記入力画像から算出され、各行単位に対する前記第２のダウンサンプリング比は前記行単位から算出される、請求項１７に記載のデータ処理装置。
前記処理は、工程（ａ）の前に、前記第１のダウンサンプリング比を算出する工程を更に含み、この工程は、
（ｈ１）前記入力画像中の接続領域を検出する工程と、
（ｈ２）工程（ｈ１）で検出された水平に隣接する接続領域の各対の間の水平距離を算出する工程と、
（ｈ３）工程（ｈ２）で算出された水平距離の全てについての平均である第１の平均水平距離を算出する工程と、
（ｈ４）工程（ｈ３）で算出された前記第１の平均水平距離に基づいて、前記第１のダウンサンプリング比を設定する工程と、を含む、請求項１７又は１８に記載のデータ処理装置。
工程（ｈ４）で、前記第１のダウンサンプリング比は、前記第１の平均水平距離の３倍に等しい、請求項１９に記載のデータ処理装置。