JPH0594533A

JPH0594533A - ラン抽出装置

Info

Publication number: JPH0594533A
Application number: JP3290789A
Authority: JP
Inventors: Shinsuke Teramura; 信介寺村
Original assignee: Ricoh Co Ltd
Current assignee: Ricoh Co Ltd
Priority date: 1991-04-09
Filing date: 1991-10-09
Publication date: 1993-04-16

Abstract

(57)【要約】【目的】画像データ中の黒ランを高速に抽出すること
ができ、集積化も容易なラン抽出装置を実現する。【構成】複数画素単位の入力画像データをそれに含ま
れる白ランの個数に着目して変換する第１変換テーブル
１０３と、その変換データを黒ランの抽出のためのデー
タに変換する第２変換テーブル１０４と、その変換デー
タを用いて黒ランの始点座標及び終点座標を求める回路
手段１０５〜１０９を有し、第２変換テーブルを、１単
位の画像データに含まれる白ランの個数によって分類さ
れたタイプ別に複数のテーブルに分割し、それぞれに対
応タイプによって決まる必要な情報のみを記憶する。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、文字認識などの画像処
理に係り、特に２値画像データよりランを高速に抽出す
るためのラン抽出装置に関する。

【０００２】

【従来の技術】従来、２値の画像データよりラン（黒画
素または白画素の連続部分）を抽出する場合は、画像を
１ラインずつラスタースキャンして黒ラン（黒画素の連
続部分）の始点と終点を検出するという方法が一般的で
あった。より具体的には、画像データはメモリや二次記
憶、あるいはスキャナなどの外部デバイスから取り込む
が、いずれにしてもデータの転送単位は１画素ではなく
複数画素が普通である。例えば、１画素を１ビットで表
現し、１バイトすなわち８画素を単位としてデータを取
り込む。そして、このような複数画素単位で取り込んだ
画像データについて、ラスタースキャン方向に１ビット
ずつ画素の白黒を判定し、白画素から黒画素への変化点
と黒画素から白画素への変化点を検出するという処理を
繰り返して黒ランを抽出している。

【０００３】

【発明が解決しようとする課題】しかし、１画素単位の
白黒判定を行なうために処理時間が長く、また前後画素
の白黒変化の判定を行なうために処理フローが複雑にな
ることから、ラン抽出の高速化が困難であるとともに装
置構成もしくはソフトウエアが複雑化するという問題が
あった。

【０００４】本発明の目的は、上記問題点を解決するた
め、ラン抽出処理をテーブル引きを主体とした単純な処
理とすることにより、複数画素単位で画像データを取り
込みラン抽出を高速に実行することが可能であり、か
つ、ラン抽出のためのテーブルを含む処理回路の集積化
が容易なラン抽出装置を提供するにある。

【０００５】

【課題を解決するための手段】請求項１の発明によれ
ば、ラン抽出装置は、複数画素を単位とした入力画像デ
ータを、それに含まれる白ランの個数に着目して変換す
る第１変換テーブルと、該第１変換テーブルによる変換
データを黒ランの抽出のためのデータに変換する第２変
換テーブルと、該第２変換テーブルによる変換データを
用いて黒ランの始点座標及び終点座標を求める回路手段
とを有し、該第２変換テーブルは、１単位の画像データ
に含まれる白ランの個数によって分類されたタイプ別に
複数のテーブルに分割され、該分割テーブルは対応タイ
プによって決まる必要な情報のみを記憶する構成とされ
る。

【０００６】請求項２の発明によれば、請求項１の発明
において、第１変換テーブルによる変換データは、入力
画像データをそれに含まれる白ランの個数により分類し
たタイプの情報と該入力画像データのパターンに対応し
たアドレス情報とを含むものとされ、第２変換テーブル
による変換データは、入力画像データの開始位置にある
黒ラン及び終了位置にある黒ランのそれぞれの長さの情
報、該入力画像データ中の前後を白ランで挟まれた黒ラ
ンの始点及び終点の位置の情報を含むものとされる。

【０００７】請求項３の発明によれば、請求項２の発明
において、第２変換テーブルは第１変換テーブルの変換
データ中のタイプ情報に従って前記複数の分割テーブル
を選択的に作動させるデコーダを含み、該複数の分割テ
ーブルを重複したアドレスを割り当てた構成とされる。

【０００８】請求項４の発明によれば、請求項２の発明
において、第１変換テーブルの変換データ中の黒ランの
始点位置及び終点位置の情報は入力画像データの開始位
置座標を基準としたオフセットであり、回路手段は、黒
ランの長さ情報を保持するためのランレングスカウン
タ、入力画像データの開始位置座標を保持するための座
標保持カウンタ、及び演算回路を含み、該各カウンタの
値及び第２変換テーブルの変換データを用いた演算を該
演算回路により行なうことによって黒ランの始点及び終
点の座標を求める構成とされる。

【０００９】請求項５の発明によれば、請求項４の発明
において、回路手段は、入力画像データのタイプに無関
係に該入力画像データの開始位置にある黒ランの長さの
情報を前記ランレングスカウンタの値に加算する第１の
処理を行ない、該入力画像データが白ランを含まないタ
イプのときは該第１処理の後に該入力画像データに対す
る処理を終了し、該入力画像データが１個以上の白ラン
を含むタイプのときは該ランレングスカウンタの値が０
以外であれば、一つの黒ランの始点及び終点の座標を求
めて出力する第２の処理を行ない、該入力画像データが
白ランを１個のみ含むタイプのときは該第２処理の後に
該入力画像データの終了位置にある黒ランの長さの情報
を該ランレングスカウンタに設定する第３の処理段階を
行ない該入力画像データに対する処理を終了し、該入力
画像データが２個以上の白ランを含むタイプのときは、
該入力画像中の前後を白ランで挟まれた黒ランの始点及
び終点の座標を求める第４の処理を該入力画像データの
タイプによって決まる回数返した後、該第３処理を行な
って該入力画像データに対する処理を終了する構成とさ
れる。

【００１０】請求項６の発明によれば、ラン抽出装置
は、画像データを記憶するイメージメモリと、該イメー
ジメモリより各ラインの画像データを読み出し最初の黒
画素の位置を検出する黒画素検索部と、該黒画素検索部
により検索された位置を記憶するワークメモリと、請求
項１ないし５のいずれか１項の発明による構成のラン抽
出部とを有し、該ラン抽出部において、処理しようとす
る現在ラインのラン抽出処理を、該ワークメモリに記憶
されている該現在ラインに対する位置を含む画像データ
より開始する構成とされる。

【００１１】

【作用】前述のように請求項１ないし５に記載された発
明は、画像データを複数画素を単位として取り込み、こ
れを第１変換テーブルによって入力画像データ中の白ラ
ンの個数に着目して変換し、さらに第２変換テーブルに
より黒ラン抽出のためのデータに変換し、この変換デー
タを用いて黒ランの始終点座標を求める構成であるた
め、黒ラン抽出の高速化が容易となり、請求項５の記載
より最も明らかなように処理のアルゴリズムを単純化す
ることができ、また請求項４の記載によって最も明らか
になるに装置構成も単純なものとすることができる。

【００１２】実施例に関連して詳細に説明するように、
入力画像データをそれに含まれる白ランの個数によって
タイプ分けすると、入力画像データに対して第２変換テ
ーブルの変換データとして提供する必要のある情報が増
減する。したがって、請求項１に示されるように分類さ
れたタイプ別に第２変換テーブルを複数のテーブルに分
割し、各分割テーブルに対応したタイプによって決まる
必要な情報だけを記憶させるならば、第２変換テーブル
を実現するために必要なＲＯＭのサイズを小さくするこ
とができ、これは第２変換テーブルを回路手段と一緒に
集積化することを容易にする。また、請求項２の記載か
らも明かなように第１変換テーブルの変換データのビッ
ト数は、第２変換テーブルの変換データのビット数より
遥かに少なくできる。特に請求項３に記載された構成と
することにより、第１変換テーブルの各分割テーブルに
別個のアドレスを割り当てる場合に比べ、第２変換テー
ブルの変換データ中のアドレス情報のビット数を最少に
することができる。これは、第１変換テーブルと回路手
段を一つのＬＳＩとして集積化し、第２変換テーブルを
外付け回路とした場合に、第２変換テーブルとＬＳＩと
の接続のために必要な入力ピンの本数を少なくできると
いうことである。このピン本数の増加はＬＳＩの大型化
・コスト上昇の大きな原因である。このように、画像デ
ータの変換テーブルを一つのテーブルにする構成に比
べ、本発明によればラン抽出装置の集積化が容易にな
る。

【００１３】文書画像等においては、白画素の比率が極
めて大きく、画像データを１バイト単位で処理する場
合、全ビットが白画素のバイトの割合が９０％を超える
ことも稀ではなく、このような画像ではラインの先頭か
ら最初の黒画素が出現するまでのバイト数が非常に多い
場合も少なくない。請求項６の発明によれば、各ライン
の先頭の黒画素の位置の検索とラン抽出処理とを並列に
行ない、各ラインの先頭の黒画素が含まれるバイト以降
の画像データについてラン抽出処理を開始することによ
って、先頭より白画素が連続するようなラインに対する
処理時間を短縮し、ラン抽出処理の一層の高速化が可能
である。

【００１４】

【実施例】以下、本発明の一実施例を説明するが、ここ
では画像データを１ビット／画素とし、１バイト（８ビ
ット）を処理単位としてラン抽出を行なうものとする。

【００１５】このラン抽出装置の全体的構成は図１に示
す通りであり、その構成要素のうちで例えば破線枠１０
０の内部のものが一つのＬＳＩパッケージとして集積化
される。メモリ１１１を、その必要メモリ量にもよるが
一緒に集積化することも可能であり、逆にメモリアドレ
ス管理部１１０を外部回路とすることも可能である。た
だし、本発明の利点を活かすために、画像データインタ
ーフェイス部１０２と第１変換テーブル１０３は外部回
路とされるべきである。

【００１６】処理の概略は次の通りである。画像データ
のソース１０１（メモリ、二次記憶、スキャナなど）か
ら、画像データ・インターフェイス部１０２によって画
像データが１バイトずつ読み込まれて第１変換テーブル
１０３に入力され、この第１変換テーブル１０３から３
ビットのタイプ情報と７ビットのアドレス情報が出力さ
れる。このタイプ情報及びアドレス情報を入力として第
２変換テーブル１０４から、pre-len（４ビット）、pos
t-len（３ビット）、run1 ,run2,run3 （それぞれの始
点座標３ビット、終点座標３ビットの計６ビット）の各
情報が出力される。シーケンスコントローラ１０５は、
第２変換テーブル１０４の出力情報及び第１変換テーブ
ル１０３からのタイプ情報などに基づき加算器１０８，
１０９、ランレングスカウンタ１０７、座標保持カウン
タ１０６の制御と処理全体のシーケンスを制御し、抽出
されたランの始終点情報をメモリ１１１へ出力させる。
ランレングスカウンタ１０７は黒ランの長さを保持する
ためのもので、座標保持カウンタ１０６は現在処理して
いる画像データの先頭位置の座標を保持するためのもの
である。メモリアドレス管理部１１０は、シーケンスコ
ントローラ１０５からの書き込み指令に従って、メモリ
１１１へのラン始終点情報の書き込みの制御とアドレス
管理を行なう。以下、処理内容及び第２変換テーブル１
０４の構成について詳細に説明する。

【００１７】本実施例においては、処理単位の１バイト
すなわち８画素の画像データをランのパターンとして考
える。このパターンは２５６（＝２⁸）通りのものがあ
るが、これを出現した白ランの個数によって（表１）に
示す５種類のタイプに分類する。すなわち、第１変換テ
ーブル１０３は、入力した画像データのビットパターン
をアドレス情報として、この分類に従ったタイプ情報を
出力するわけである。

【表１】

【００１８】ここで、白ランがあるというは、そこで黒
ランが途切れているということである。注目している画
像データ中の黒ランの前及び後に白ランがあれば、その
黒ランは黒ランとして確定し登録してよい。このような
黒ランを確定ランと呼ぶことにする。１バイトのデータ
中の確定ランの出現個数は最大３個であるので、画像デ
ータの先頭側より出現順にrun1,run2,run3 と表わすも
のとする。

【００１９】１バイト画像データのランパターン種類数
は２５６であるが、タイプ別に整理すると、ランパター
ン数と確定ラン数は（表２）の通りである。

【表２】

【００２０】また、１バイト単位で画像データを処理す
るため、前後のバイトの画像データとのランの連続関係
を考慮する必要がある。すなわち図４に示すように、注
目している現在の画像データ（実線で囲まれたデータ）
が黒ラン（斜線部）で始まっている場合、この黒ランは
直前に処理した画像データ（破線で囲まれたデータ）の
黒ランの続きである可能性がある。同様に現在の画像デ
ータが黒ランで終わっている場合、次に処理される画像
データの黒ランと連続している可能性がある。このよう
な前後の画像データ中の黒ランと連続した黒ランについ
ては、その連続範囲を確認した段階で、前後の連続した
黒ランを一つの黒ランとして確定し登録する必要があ
る。そこで、図４に示すように画像データの先頭位置に
ある黒ランの長さ及び画像データの終了位置にある黒ラ
ンの長さをそれぞ表わすためのpre-lenとpost-lenとい
う情報を定義する。ただし画像データが白ランで始まる
ときは pre-len ＝０、画像データが白ランで終わると
きはpost-len ＝０とする。

【００２１】第２変換テーブル２は図２に示す構成であ
る。２０１はタイプ０及びタイプ１のための変換テーブ
ルを記憶したＲＯＭ、２０２はタイプ２のための変換テ
ーブルを記憶したＲＯＭ、２０３はタイプ３のための変
換テーブルを記憶したＲＯＭ、２０４はタイプ４のため
の変換テーブルを記憶したＲＯＭである。これら各ＲＯ
Ｍに、第１変換テーブル１０３からのアドレス情報が入
力する。２０５は第１変換テーブル１０３から入力する
タイプ情報をデコードして、ＲＯＭ２０１，２０２，２
０３，２０４に対するイネーブル信号を発生するデコー
ダである。

【００２２】１バイトの画像データのランパターン種類
数は２５６であるから、第２変換テーブルの総エントリ
ー数は２５６となり、そのアクセスのためには基本的に
８ビットのアドレス情報が必要とされる。しかし、タイ
プによってＲＯＭ２０１，２０２，２０３，２０４を選
択するので同一のアドレスを各ＲＯＭに重複させて割り
当て、第１変換テーブル１０３はタイプ別に画像データ
のランパターンに対応した７ビットのアドレス情報を出
力するようにテーブル内容が作成されている。ただし、
タイプ０とタイプ１は扱いが同じであるため、区別しな
いで０から３６の値のアドレス情報を出力する。このよ
うな第１変換テーブルはＲＯＭを用いて容易に実現され
る。

【００２３】前記（表２）に見られるように、タイプ０
のランパターン数は１、タイプ１のランパターン数は３
６であるが、いずれも確定ランの個数が０でラン抽出処
理上では一緒に扱うことができるため、その変換テーブ
ルはＲＯＭ２０１上の一つのテーブルにまとめられ、０
から３６のアドレスを割り当てられる。この変換テーブ
ル（２０１）の各エントリーは、４ビットのpre-lenと
３ビットの post-lenの計７ビットの情報のフィールド
からなる。

【００２４】タイプ２のランパターン数は１２６である
ので、その変換テーブルのエントリー数は１２６であ
る。この変換テーブルはＲＯＭ２０２に置かれ、０から
１２５のアドレスを割り当てられる。確定ラン個数は１
であるから、各エントリーはpre-lenとpost-lenのフィ
ールドと run1 の始終点情報６ビットのフィールドから
なる。なお、run 1 の始終点情報はその始点座標と終点
座標であるが、これらは図５に示すように画像データの
先頭からのオフセットとして、それぞれ３ビットで表わ
される。これはrun2, run3 についても同様である。

【００２５】タイプ３のランパターン数は８４であるの
で、その変換テーブルはエントリー数が８４のテーブル
としてＲＯＭ２０３に置かれ、０から８３のアドレスを
割り当てられる。確定ラン個数は２であるので、各エン
トリーはrun2 の始終点情報６ビットのフィールドが追
加される。同様に、タイプ４のための変換テーブルはエ
ントリー数が９でＲＯＭ２０４に置かれ、０から８のア
ドレスを割り当てられる。各エントリーは、さらにrun3
の始終点情報６ビットのフィールドが追加され最も長
くなっている。

【００２６】このように確定ランの個数が異なるタイプ
別に第２変換テーブルを分割し、それぞれの各エントリ
ーから不要な確定ランのためのフィールドを削除するこ
とにより、必要なＲＯＭのサイズを減らすことができ
る。タイプを区別せず第２変換テーブル１０４の２５６
エントリーのフィールド構成を同一にした場合に必要な
ＲＯＭサイズに比べ、必要なＲＯＭサイズは２６８２ビ
ット（＝(1+36)*6*2 + 126*6*2 + 84*6*1 ）だけ少ない
３７１８ビットとなる。第１変換テーブル１０３に必要
なＲＯＭサイズ２５６０ビット（＝10*256 ）を加えた
ＲＯＭサイズも６２７８ビットとなり、第１変換テーブ
ル１０３と第２変換テーブル１０４を一つのテーブルと
して実現した場合に必要なＲＯＭサイズ７１６８ビット
（＝(3+4+3+((3*2)*3))*256 ）よりもＲＯＭサイズを減
らすことができる。

【００２７】このように変換テーブルを第１変換テーブ
ル１０３と第２変換テーブル１０４に分け、かつ第２変
換テーブル１０４に必要なＲＯＭサイズの削減を図った
ため、第１変換テーブル１０３を外付け回路とし、第２
変換テーブル１０４を他の処理回路とともに同一のＬＳ
Ｉとして集積化することが容易になる。さらに集積化す
る場合には入出力ピン数の増加を抑えることが極めて重
要であるが、第１変換テーブル１０３から第２変換テー
ブル１０４への入力情報ビット数は１０ビットと少な
い。第２変換テーブルの分割したテーブルに重複したア
ドレスを割り当てることも、このビット数の１ビット削
減に寄与している。したがって、第１変換テーブル１０
３を外付けしても、ＬＳＩのピン数の問題を避けられ
る。

【００２８】因みに、第１変換テーブル１０３と第２変
換テーブル１０４を同一テーブルとすると、他の処理回
路と同一のＬＳＩとして集積化することがＲＯＭサイズ
の面から難しい場合がある。しかし、そうだからといっ
て同テーブルを外付けにすると、同テーブルから他の処
理回路のＬＳＩへ２８ビットもの情報を入力しなければ
ならず、ＬＳＩの入力ピン数が極めて多くなってしま
い、ＬＳＩの大型化やコスト上昇を伴い好ましくない。
これと対比すれば明かなように、本発明によるラン抽出
処理装置は集積化が遥かに容易である。

【００２９】次にラン抽出処理を順を追って説明する
が、その処理の概略フローは図３に示す通りである。ラ
スタースキャン方向の１ラインについての処理を開始す
る前に、ランレングスカウンタ１０７と座標保持カウン
タ１０６をリセットし（処理３０１）、この後に画像デ
ータ・インターフェイス部１０２より１バイトの画像デ
ータを取り込む（処理３０２）。

【００３０】この画像データ（現在データと呼ぶ）によ
るテーブル引きが行なわれる（処理３０３）。すなわ
ち、現在データが入力された第１変換テーブル１０３よ
り、現在データのタイプ情報と第２変換テーブル１０５
を引くためのアドレス情報が出力される。第２変換テー
ブル１０４において、タイプ情報により示されたタイプ
に対応したテーブルのＲＯＭ２０１，２０２，２０３ま
たは２０４の一つに対するイネーブル信号がアクティブ
となり、そのＲＯＭのみが有効となって、アドレス情報
で指定されたエントリーの情報を出力する。

【００３１】シーケンスコントローラ１０５は、第２変
換テーブル１０４より出力されたpre-len の値とランレ
ングスカウンタ１０７の値との加算を加算器１０８によ
り行なわせ、結果値をランレングスカウンタ１０７に保
持させる（処理３０４）。現在データのタイプが０であ
れば、ランの登録は行なわず直ちに処理３０９に進み座
標保持カウンタを８だけインクリメントしてから、処理
３０２に戻り次の画像データの処理を開始する。

【００３２】なお、現在データが白ランで始まる場合、
pre-len の値は０であるから加算後もランレングスカウ
ンタ１０７の値は変わらないが、直前データが黒ランで
終わっているときには、その黒ランの長さ（直前データ
に対するpost-len の値）がランレングスカウンタ１０
７の値となっており、これは０以外である。他方、直前
データが白ランで終わっているときは、加算後のランレ
ングスカウンタ値は０である。

【００３３】また、処理３０４において、現在データの
タイプが０以外であれば、pre-len値のランレングスカ
ウンタ１０７への加算の後に処理３０５に進む。

【００３４】処理３０５において、シーケンスコントロ
ーラ１０５は、ランレングスカウンタ１０７の値が０で
あれば、何もせず、現在データのタイプが１のときは処
理３１０に進む。

【００３５】他方、ランレングスカウンタ１０７の値が
０でない場合、ランレングスカウンタ値をpre-len 値か
ら差し引く減算（補数加算）を加算器１０８に行なわ
せ、その結果値と座標保持レジスタ１０６の値との加算
を加算器１０９に行なわせることによって、一つの黒ラ
ン（これは前データから続いている場合もある）の始点
座標を求め、これをメモリ１１１に登録（格納）させ、
また座標保持カウンタ１０６の値とpre-len 値を加算器
１０９によって加算させることによって同黒ランの終点
座標を求め、これをメモリ１１１に登録させる。この
際、メモリアドレス管理部１１０に一つのランの登録を
指示することにより、始終点座標情報の登録アドレスを
適切に制御させる。そして、現在データのタイプが１で
あれば処理３１０に進み、タイプが２，３または４であ
れば処理３０６に進む。

【００３６】処理３０６において、シーケンスコントロ
ーラ１０５は、第２変換テーブル１０４より入力したru
n1 の始点座標値及び終点座標値（いずれも現在データ
の開始位置すなわち座標保持カウンタ１０６の値に対す
るオフセット）と、座標保持カウンタ１０６の値との加
算を加算器１０９で行なわせ、現在データ中の１番目の
確定ランの始点及び終点の座標を求め、これをメモリ１
１１に登録する。そして、現在データがタイプ２であれ
ば他に確定ランはないので処理３１０に進むが、タイプ
が３または４であれば処理３０６に進む。

【００３７】現在データのタイプが３の場合、処理３０
７においてrun2 の始終点座標値と座標保持カウンタ１
０６の値の加算を行なって現在データ中の２番目の確定
ランの始終点座標を計算し、これをメモリ１１１に登録
し、処理３１０に進む。現在データのタイプが４の場
合、処理３０７で２番目の確定ランを登録した後に処理
３０８に進み、run3 の始終点座標値と座標保持カウン
タ１０６の値との加算により３番目の確定ランの始終点
座標を計算し、これをメモリ１１１に登録し、この後に
処理３１０に進む。

【００３８】処理３１０において、現在データのpost-l
en の値を加算器１０８経由でランレングスカウンタ３
１０にロードする。そして、処理３０９に戻り座標保持
カウンタ１０６のインクリメントを行なってから次の画
像データの処理に以降することになる。

【００３９】図６に示す画像データを例にしてラン抽出
を説明する。データＤ１が現在データとなった時は、タ
イプ１であるので処理３０５に進むが、pre-lenは０で
あるので処理３１０，３０９を経由して処理３０２に戻
る。次のデータＤ２が現在データとなった時も同様であ
るが、 post-len の値がランレングスカウンタ１０７に
残る。次のデータＤ３が現在データとなった時は、処理
３０５において直前データＤ２から続いた黒ランＲ１が
抽出され登録され、また終わりまで続く黒ランの長さす
なわちpost-len の値がランレングスカウンタ１０７に
残る。次のデータＤ４が現在データとなった時は、タイ
プ０であるので処理３０４でpre-len の値がランレング
スカウンタ１０７の値に加算されるだけである。次のデ
ータＤ５が現在データとなった時は、処理３０５でデー
タＤ３から続いた黒ランＲ２が登録され、続いて処理３
０６で確定ランＲ３が登録されることになる。

【００４０】ここまでの説明から明かなように、画像デ
ータを白ランの出現個数によってタイプ分けすること
は、変換テーブルのＲＯＭサイズ削減などの利益をもた
らすが、さらに処理の効率化及びアルゴリズムの単純化
の面でも利益がある。すなわち、白ランが出現したとい
うことは、そこで黒ランが途切れているということであ
り、ラン登録処理が必要になるということであって、白
ラン出現回数により分類したタイプによって必要なラン
登録処理の回数をほぼ決定できる。これには例外、すな
わち注目している画像データが白ランで始まり、かつ直
前の画像データが白ランで終わっている場合、あるいは
注目している画像データが黒ランで終わっている場合が
ある。このような例外があるとしても、画像データのタ
イプに応じて不要なラン登録処理のスキップ制御を行な
うことにより、様々なランパターンを統一的に扱った効
率的なラン抽出処理を容易に実現できる。

【００４１】なお、本実施例におけるように、第２変換
テーブルのタイプ別テーブルに同一アドレスを割り当て
ると第２変換テーブルをＬＳＩ化した場合の入出力ピン
を減少できる利点があり好ましいが、それぞれのテーブ
ルに別々のアドレスを割り当てることも許される。

【００４２】図７は本発明の他の実施例を示すブロック
図である。イメージメモリ４０１はスキャナ等から取り
込んだ画像データを蓄積するメモリであり、黒画素検索
部４０２はイメージメモリ４０１から画像データを読み
出し、各ライン毎に先頭の黒画素を検索し、その黒画素
の先頭位置（ｘ，ｙ）を出力する。ワークメモリ４０３
は、この黒画素先頭位置と黒画素検索が終了した最後の
ラインのｙ座標を記憶するメモリであり、ラン抽出部４
０４からもアクセスされる。ラン抽出部４０４は、図１
に示された装置からソース１０１とメモリ１１１を除い
た如き構成の回路である（したがって、以下の説明にお
いては、図１中の符号を適宜用いる）。ただし、後述の
ようにシーケンスコントローラ１０５の制御に僅かに違
いがある。４０５は抽出されたランデータをバッファリ
ングするためのランデータバッファである。このランデ
ータバッファ４０５は２ライン分あり、一方が現在処理
中のラインのランデータのバッファリングに用いられる
期間に、他方から前ラインのランデータが出力されると
いうように、交互に切り替えて使用される。なお、この
ランデータバッファ４０５は図１中のメモリ１１１に対
応する。

【００４３】次に動作を説明する。黒画素検索部４０２
は、イメージメモリ４０１から画像データを読み出し、
各ライン毎に先頭の黒画素の位置を検索し、先頭の黒画
素の先頭位置（ｘ，ｙ）をワークメモリ４０３に書き込
む。なお、イメージメモリ４０１のイメージデータは、
Ｘ×Ｙ画素の原画像を左から右へ主走査し、上から下へ
副走査した２値データである。また、黒画素先頭位置
（ｘ，ｙ）は、画像の左上を原点とし、右方向へｘ座標
が増加し、下方向へｙ座標が増加するような座標を指
す。１ライン（Ｘ／８バイト）調べて黒画素が見つから
ない場合は、そのラインについては黒画素先頭位置の書
き込みを行なわない。また、１ラインの処理が済んだ時
に、処理し終えたラインのｙ座標をワークメモリ４０３
の固定領域に書き込む。

【００４４】ラン抽出部４０４は黒画素検索部４０２と
同時に動作する。ラン抽出部４０４のシーケンスコント
ローラ１０５は、ワークメモリ４０３の前記固定領域に
書き込まれたｙ座標を読み、これから処理を開始しよう
としているラインに対する黒画素検索が終了しているか
調べる。黒画素検索が終了している場合、シーケンスコ
ートローラ１０５は、その現在ラインに対するラン抽出
を開始させる。ただし、ワークメモリ４０３より現在ラ
インの黒画素先頭位置のｘ座標を読み込み、この位置を
超えない最大の８の倍数のアドレスから、現在ラインの
画像データの読み込みを開始させる。また、処理開始時
に座標保持カウンタ１０６に、この最初に読み込むデー
タの先頭位置（ｘ）を初期設定する。すなわち、図３の
処理３０１において、座標保持カウンタ１０６をリセッ
トする代わりに、現在ラインの先頭の黒画素が含まれる
１バイトの先頭位置を初期設定する。この後の処理内容
は図３に示される通りである。なお、現在ラインの黒画
素先頭位置がクリアされている場合、つまり黒画素が検
索されなかった場合は、現在ラインは処理せず、次のラ
インに移行する。

【００４５】画像データの大部分は８ビットすべてが白
画素であり、その比率は９０％を超えることも少なくな
い。また、ラン抽出部４０４では、画像データの読み込
み、テーブル引きによるデータ変換、ランレングスカウ
ンタ１０７とpre-lenの加算、座標保持カウンタ１０６
のインクリメントの作業を繰り返すが、このような作業
が実際に必要となるのは各ラインの先頭の画素から後の
データであり、各ラインの先頭から処理を開始した場合
は、先頭黒画素より前の区間ではただ座標保持カウンタ
１０６をインクリメントするだけである。したがって、
本実施例のように、ライン上の先頭黒画素検索処理とラ
ン抽出処理を並列に行ない、ラン抽出処理を先頭の黒画
素が含まれるバイトより開始すれば、各ラインの先頭か
ら処理する場合に比べラン抽出時間が大幅に短縮するこ
とは明らかである。

【００４６】

【発明の効果】以上、詳細に説明した如く、請求項１な
いし５に記載の本発明によれば、画像データを複数画素
を単位として取り込み、これをテーブル引きを中心とし
た単純な処理によって、また単純な装置構成によって黒
ラン抽出を高速に行なうことができる。また、変換テー
ブルを第１変換テーブルと第２変換テーブルに分け、入
力画像データ中の白ランの個数により分類されたタイプ
別に第２変換テーブルを複数のテーブルに分割し、各分
割テーブルに対応したタイプによって決まる必要な情報
だけを記憶させることによって、さらには第２変換テー
ブルの複数の分割テーブルに重複したアドレスを割り当
てることによって、第２変換テーブルを他の回路手段と
一体的に集積化し、第１変換テーブルを外付け回路とす
ることが容易となる。また請求項６記載の発明によれ
ば、各ラインの先頭から最初の黒画素がある部分まで
は、バイト単位のラン抽出処理を行なわないため、ラン
抽出を一層高速化できる。よって画像データ中の黒ラン
の高速抽出が可能で、その構成も単純で、かつ集積化が
容易なラン抽出装置を実現できるという効果を達成でき
るものである。

【図面の簡単な説明】

【図１】本発明によるラン抽出装置の全体的構成を示す
ブロック図である。

【図２】第２変換テーブルの構成を示すブロック図であ
る。

【図３】ラン抽出処理の概略を示すフロー図である。

【図４】入力画像データの開始位置または終了位置にあ
る黒ランの長さ情報の説明図である。

【図５】入力画像中の確定ランの始終点位置情報の説明
図である。

【図６】黒ラン抽出処理の説明のための画像データ列の
一例の説明図である。

【図７】本発明の他の実施例の構成を示すブロック図で
ある。

【符号の説明】

１０１画像データのソース１０２画像データインターフェイス部１０３第１変換テーブル１０４第２変換テーブル１０５シーケンスコントローラ１０６座標保持カウンタ１０７ランレングスカウンタ１０８加算器１０９加算器１１０メモリアドレス管理部１１１メモリ４０１イメージメモリ４０２黒画素検索部４０３ワークメモリ４０４ラン抽出部４０５ランデータバッファ

Claims

【特許請求の範囲】

【請求項１】複数画素を単位として画像データを入力
し、黒ランを抽出しその始点座標及び終点座標を出力す
るラン抽出装置において、入力画像データをそれに含ま
れる白ランの個数に着目して変換する第１変換テーブル
と、該第１変換テーブルによる変換データを黒ランの抽
出のためのデータに変換する第２変換テーブルと、該第
２変換テーブルによる変換データを用いて黒ランの始点
座標及び終点座標を求める回路手段とを有し、該第２変
換テーブルは、１単位の画像データに含まれる白ランの
個数によって分類されたタイプ別に複数のテーブルに分
割され、該分割テーブルは対応タイプによって決まる必
要な情報のみを記憶する構成とされることを特徴とする
ラン抽出装置。
【請求項２】前記第１変換テーブルによる変換データ
は、入力画像データをそれに含まれる白ランの個数によ
り分類したタイプの情報と該入力画像データのパターン
に対応したアドレス情報とを含み、該第２変換テーブル
による変換データは、該入力画像データの開始位置にあ
る黒ラン及び終了位置にある黒ランのそれぞれの長さの
情報、該入力画像データ中の前後を白ランで挟まれた黒
ランの始点及び終点の位置の情報を含むことを特徴とす
る請求項１記載のラン抽出装置。
【請求項３】前記第２変換テーブルは、前記第１変換
テーブルの変換データ中のタイプ情報に従って前記複数
の分割テーブルを選択的に作動させるデコーダを含み、
該複数の分割テーブルは重複したアドレスを割り当てら
れることを特徴とする請求項２記載のラン抽出装置。
【請求項４】前記第１変換テーブルの変換データ中の
黒ランの始点位置及び終点位置の情報は入力画像データ
の開始位置座標を基準としたオフセットであり、前記回
路手段は、黒ランの長さ情報を保持するためのランレン
グスカウンタ、入力画像データの開始位置座標を保持す
るための座標保持カウンタ、及び演算回路を含み、該各
カウンタの値及び該第２変換テーブルの変換データを用
いた演算を該演算回路により行なうことによって黒ラン
の始点及び終点の座標を求めることを特徴とする請求項
２記載のラン抽出装置。
【請求項５】前記回路手段は、入力画像データのタイ
プに無関係に該入力画像データの開始位置にある黒ラン
の長さの情報を前記ランレングスカウンタの値に加算す
る第１の処理を行ない、該入力画像データが白ランを含
まないタイプのときは該第１処理の後に該入力画像デー
タに対する処理を終了し、該入力画像データが１個以上
の白ランを含むタイプのときは該ランレングスカウンタ
の値が０以外であれば、一つの黒ランの始点及び終点の
座標を求めて出力する第２の処理を行ない、該入力画像
データが白ランを１個のみ含むタイプのときは該第２処
理の後に該入力画像データの終了位置にある黒ランの長
さの情報を該ランレングスカウンタに設定する第３の処
理段階を行ない該入力画像データに対する処理を終了
し、該入力画像データが２個以上の白ランを含むタイプ
のときは、該入力画像中の前後を白ランで挟まれた黒ラ
ンの始点及び終点の座標を求める第４の処理を該入力画
像データのタイプによって決まる回数返した後、該第３
処理を行なって該入力画像データに対する処理を終了す
ることを特徴とする請求項４記載のラン抽出装置。
【請求項６】画像データを記憶するイメージメモリ
と、該イメージメモリより各ラインの画像データを読み
出し最初の黒画素の位置を検出する黒画素検索部と、該
黒画素検索部により検索された位置を記憶するワークメ
モリと、請求項１ないし５のいずれか１項に記載された
構成のラン抽出部とを有し、該ラン抽出部は、処理しよ
うとする現在ラインのラン抽出処理を、該ワークメモリ
に記憶されている該現在ラインに対する位置を含む画像
データより開始することを特徴とするラン抽出装置。