JPH022193B2 - - Google Patents

Description

【発明の詳細な説明】 (1) 発明の技術分野 本発明は複数の文字が近接して書かれた文字列
に対して個々の文字を分離抽出することができる
文字分離抽出方式に関するものである。

(2) 従来技術と問題点 従来の文字列の分離抽出方式としては、一定の
形状たとえば矩形のウインドウを文字列上に走査
させ、個々の文字を抽出する方式があるが、複数
の文字が互いに近接して書かれている文字列の場
合、これらの文字を正確に分離抽出することは不
可能であつた。これに対し、本出願人は特願昭57
―157237号「文字分離抽出方式」を提案した。こ
の方式は近接した文字の分離抽出でも非常に効果
があるが、最短径路を求める際の前処理としての
ラベル付与の処理速度に時間がかかることが問題
であつた。

(3) 発明の目的 本発明の目的は複数の文字が近接して書かれて
いる場合でも各文字を正確に分離することができ
るとともに、最短径路を求めるためのラベル付与
処理を高速化しうる文字分離抽出方式を提供する
ことである。

(4) 発明の構成 前記目的を達成するため、本発明の文字分離抽
出方式は単一または複数の文字から構成される文
字列をその外接矩形よりも各方向にそれぞれ１画
素分大きい矩形によつて切出された画像に対し、
文字列方向に垂直で長さが矩形幅に等しい１画素
幅のウインドウを矩形領域の一端より走査し、最
初に該ウインドウ内に黒画素が出現する位置を検
出してその位置での該ウインドウの両端に存在す
る画素間の最短径路の探索領域を該ウインドウ位
置から走査方向側に該探索領域の画素にラベルを
付与し該ラベルから限定して最短径路を見出し、
該ウインドウと前記最短径路によつて囲まれた領
域を１文字の存在する領域とみなし、その領域を
逐次分離抽出することにより、近接して書かれた
文字列から個々の文字の存在する領域を抽出する
文字分離抽出方式において、水平・垂直の一次元
走査で前記探索領域の画素にラベルを付与する手
段を具えたことを特徴とするものである。

(5) 発明の実施例 第１図〜第１４図は本発明を具体例により説明
する手順説明図である。

ここでは文字列として第１図に示す「V_2B」の
ようにそのままでは分離困難な場合の処理手順を
示す。

第１図は文字列１１₁〜１１₃をその外接矩形よ
りも各方向にそれぞれ１画素分大きい矩形枠１２
により切出した画像を示す。この画像に対して同
図に示すウインドウ１３、すなわち文字列方向に
垂直で長さが矩形枠１２の縦幅に等しく、１画素
幅のウインドウを矩形枠内領域の１端より走査さ
せ、最初にウインドウ１３内に黒画素１４が出現
する位置を検出する。

第２図は第１図の文字列１１₁〜１１₃に対しウ
インドウ１３により黒画素１４を検出した位置を
示す。次に、この位置におけるウインドウ１３の
両端位置“Ｓ”，“Ｅ”の白画素間の最短径路を見
出すのであるが、その探索領域をウインドウ１３
の位置から文字列の走査方向に限定する。第２図
の“＋”印で示す文字端位置１５は探索領域の限
定を表わすラベルである。すなわち、“＋”印の
右側の領域が探索領域である。最短径路の抽出ア
ルゴリズムとしては、従来各種のものが提案され
ているが、ここではリー（Lee）のアルゴリズム
を用いて説明する。

前述の処理によつて決定された２点“Ｓ”，
“Ｅ”のうち、まずどちらか一方、たとえば“Ｓ”
を出発点として選ぶ。最初に、第３図ａに示すウ
インドウを水平方向に一次元的に走査させ、次の
論理条件によつて白画素の領域に“１”→“２”
→“３”→“１”→“２”→……のラベルを与え
る。

この場合のラベル付与の論理条件は次のとおり
である。

（） A₀が白画素でなければスキツプ（走査
を進める）する。

（） A₀が白画素で、かつ A₁がラベル“１”，“２”，“３”のいずれ
かである時はA₁のラベルの次のラベルをA₀
に与える。たとえば、A₁のラベルが“１”
ならばA₀にラベル“２”を与える。A₁のラ
ベル“３”ならばA₀にラベル“１”を与え
る。

A₁がラベル“１”，“２”，“３”以外の時
で、かつA₂がラベル“１”，“２”，“３”の
いずれかである時はA₂のラベルの次のラベ
ルをA₀に与える。A₂がラベル“１”，“２”，
“３”以外の時はスキツプ（走査を進める）
する。

なお、初期条件としてA₁が出発点“Ｓ”の時、
A₀にラベル“１”を与える。

第４図は第３図に示した論理条件を水平走査に
よるラベル付与に適用した途中結果を示したもの
であり、第５図に最終結果を示す。

すなわち、第４図に示すように、“Ｓ”から始
まり第１行目に対し“１”，“２”，“３”，…の順
にラベルを付してゆく。第２行目は“１”，“２”
で黒画素１４にぶつかるからこれをスキツプし、
黒画素の終つたところで縦列の次のラベル“２”
を付し以下“３”，“１”，“２”…の順にラベルを
付す。以下同様に黒画素にぶつかつたらスキツプ
し縦列を見てラベルを付すことを繰返し第４図か
ら第５図を完了する。

次に第３図(b)に示すウインドウを垂直方向に一
次元的に走査させ、水平方向と同様の論理条件に
よつてラベル付与を実行する。この際、垂直方向
の走査の出発点は文字列の外接矩形１２の１端で
探索領域の限定位置１５と反対の側１２′とする。

第６図は垂直走査によるラベル付与の途中結果
を、第７図は終点“Ｅ”まで到達した最終結果を
示す。

このようにして、水平方向、垂直方向の一次元
走査を各１回ずつ実行することによつて、必ずラ
ベル付与処理は完結するので、高速度の処理が実
現できる。

次に切出しの段階に入る。終点“Ｅ”から
“３”→“２”→“１”の順番に逆追跡し、始点
“Ｓ”に到達する径路を見出す。

この径路は最短径路であるが、必ずしも一意的
に定まることは限らない。ここでは第８図に示す
ように、逆追跡の方向に優先順位を設け、最短径
路を一意に定めている。

第９図に逆追跡によつて検出された最短径路を
示し、逆追跡の際に径路上の画素１６にラベル
“＋”を与えたものである。

以上の処理によつて、文字列中の１文字の存在
する領域が“＋”で囲まれた領域として識別され
る。そこでこの領域内の黒画素を切出すことによ
つて、１文字の画像が分離抽出される。

第１０図は１文字を分離抽出した後の矩形枠１
２の領域内の文字列１１₂，１１₃の画像を示す。

以上の処理を、１文字分離抽出する毎に白画素、
黒画素以外のラベルが付与された画素を白画素に
変換した後、矩形領域内の黒画素が検出されなく
なるまで繰返すことにより、文字列の個々の文字
が１文字ずつ分離抽出できる。

すなわち、次の文字１１₂に対しウインドウを
設定し、次の文字の探索領域の限定を表わすラベ
ルを決定し、第４図〜第９図の手順を繰返す。

第１１図は本発明の実施例の構成説明図であ
る。同図において、２１は入力文字列画像の外接
矩形を検出する外接矩形検出回路、２２は文字列
画像を格納しておく画像メモリ、２３は分離され
た文字を切出す文字切出し回路、２４は文字端位
置を検出するためのウインドウを走査するウイン
ドウ走査回路、２５は文字端位置へのラベル付け
や最短径路探索のためのラベルを付与するラベリ
ング回路、２６は付与されたラベルを基に逆追跡
を行なう逆追跡回路、２７は分離抽出された文字
の消去及びラベルの消去を行なうクリア回路、２
８は文字列画像の外接矩形のアドレスやラベリン
グの始点、終点のアドレスを保持しておくアドレ
ステーブルである。

この構成において、第１図〜第１０図の例を引
用して説明する。

まず、入力文字列画像１１₁〜１１₃を外接矩形
検出回路２１を介して画像メモリ２２に格納す
る。このとき外接矩形検出回路２１によつて検出
された入力文字列１１₁〜１１₃の外接矩形より各
方向にそれぞれ１画素分大きい矩形枠１２のアド
レスをアドレステーブル２８に書込む。

ウインドウ走査回路２４は、アドレステーブル
２８に保持されている矩形アドレスを基に、矩形
領域の一端よりウインドウ１３を走査し、文字端
位置１５、すなわちウインドウ内に最初の黒画素
が現われる位置を検出する。そしてその位置１５
でのウインドウ１３の両端の一方を始点（Ｓ）、
他方を終点（Ｅ）としてそのアドレスをアドレス
テーブル２８に書込む。

ラベリング回路２５は始点アドレスを基に、ま
ず最短径路探索領域を限定するためのラベル、後
の処理では文字の切出しに利用されるラベルを、
文字端位置１５に付与する。

これは第２図中に“＋”印で示されるラベルで
あり、実際には他のラベルと区別される特別のコ
ードである。

その後、ラベリング回路２５は始点（Ｓ）から
前述の第４図〜第７図に示す手順の如く、水平・
垂直の一次元走査を各一回実行し、終点（Ｅ）ま
でラベルを付与していく。

ラベル付けが終点（Ｅ）に達すると、逆追跡回
路２６は終点（Ｅ）からラベル付けの逆の順番で
ラベルを逆追跡し、始点（Ｓ）に到達する径路１
６を見出す。これと同時に見出した径路１６には
文字端位置１５に付与したものと同じラベル
“＋”を付与する。

文字切出し回路２３は文字端位置１５のラベル
“＋”と、始点（Ｓ）、終点（Ｅ）間の最短径路１
６のラベル“＋”で囲まれる領域内の黒画素１４
を切出し、この画像１１₁を出力に接続される文
字認識装置等に送出する。

クリア回路２７は前記ラベル“＋”で囲まれる
文字領域およびこの切出しのために用いた各ラベ
ルを消去し、第１０図の次の文字列１１₂，１１₃
のみが得られ、次に形成する文字端位置で限定さ
れる領域につき前述の手順が再び繰返えされる。

(6) 発明の効果 以上説明したように、本発明によれば、文字列
の中から１文字毎の画像を分離抽出する際のラベ
ル付与の処理を水平、垂直の一次元走査を各１回
ずつ実行するのみで、非常に高速度の文字分離抽
出が実現できる。従つてフリーフオーマツトの手
書き文字でも個々の文字を確実にかつ高速度で分
離抽出することができるので、手書文字に対する
文字認識等に適用して大きな効果を発揮するもの
である。

【図面の簡単な説明】

第１図〜第１０図は本発明の手順説明図、第１
１図は本発明の実施例の構成説明図であり、図中
１１₁〜１１₃は文字列、１２，１２′は矩形枠、
１３はウインドウ、１４は黒画素、１５は文字端
位置、１６は最短径路、２１は外接矩形検出回
路、２２は画像メモリ、２３は文字切出し回路、
２４はウインドウ走査回路、２５はラベリング回
路、２６は逆追跡回路、２７はクリア回路、２８
はアドレステーブルを示す。

Claims (1)

【特許請求の範囲】
1. １ 単一または複数の文字から構成される文字列
   をその外接矩形よりも各方向にそれぞれ１画素分
   大きい矩形によつて切出された画像に対し、文字
   列方向に垂直で長さが矩形幅に等しい１画素幅の
   ウインドウを矩形領域の一端より走査し、最初に
   該ウインドウ内に黒画素が出現する位置を検出し
   てその位置での該ウインドウの両端に存在する画
   素間の最短径路の探索領域を該ウインドウ位置か
   ら走査方向側に限定して該探索領域の画素にラベ
   ルを付与し該ラベルから最短径路を見出し、該ウ
   インドウと前記最短径路によつて囲まれた領域を
   １文字の存在する領域とみなし、その領域を逐次
   分離抽出することにより、近接して書かれた文字
   列から個々の文字の存在する領域を抽出する文字
   分離抽出方式において、水平・垂直の一次元走査
   で前記探索領域の画素にラベルを付与する手段を
   具えたことを特徴とする文字分離抽出方式。