JPH0422392B2

JPH0422392B2 -

Info

Publication number: JPH0422392B2
Application number: JP59222292A
Authority: JP
Inventors: Hideo Asano; Eisuke Kanzaki; Yutaka Shimizu
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1984-10-24
Filing date: 1984-10-24
Publication date: 1992-04-16
Also published as: JPS61102872A; EP0179291A2; US4757552A; CA1262279A; DE3575510D1; EP0179291B1; EP0179291A3

Description

【発明の詳細な説明】

［産業上の利用分野］本発明は、例えばイメージ走査装置の如きイメ
ージ・データ供給装置から供給された２レベルの
イメージ・データを、これをデータ圧縦装置に送
る前に処理する方法に関する。［従来技術］日経エレクトロニクス1975年11月３日号第30〜
34ページは、ラン・レングス符号化に適したイメ
ージ・データの前処理を示している。この文献に
おいては、参照走査線及び符号化走査線（現走査
線）の黒のイメージ・データ及び白のイメージ・
データは、黒のイメージ・データ（黒ビツト）を
新走査線の左半分にそして白のイメージ・データ
（白ビツト）を新走査線の右半分にグループ分け
するように再配列される。左半分をA1シーケン
スと呼びそして右半分をA2シーケンスと呼ぶ。
そしてA1及びA2シーケンスに適応する新たな符
号化方式が必要とされる。この分献はイメージ・
データの前処理に関するものであるが、これのイ
メージ・データ再配列のプロセスの詳細は本発明
のものと異なつている。［発明が解決しようとする問題点］従来のプロセスは前記文献の如くにイメージ・
データの複雑な再配列を必要とした。２次元符号
化方式に適し且つ圧縮比を改善するようなイメー
ジ・データの前処理は提案されていなかつた。［問題点を解決するための手段］例えばイメージ走査装置の如きイメージ供給手
段から送られる２レベル・イメージ・データが本
発明により前処理され、そしてこの前処理された
イメージ・データは、例えばCCITTの提案T.4の
如き２次元符号化方式のもとにイメージ・データ
を圧縮する手段に送られる。本発明の方法は次の工程を含む。第１走査線の変化画素及び第２走査線の変化画
素を検出する工程。上記第１走査線の変化画素及び第２走査線の変
化画素の間の距離が予定の範囲内にあるか否かを
調べる工程。上記距離が上記予定の範囲内にある時に上記距
離を予定の距離に減少するように、上記イメー
ジ・データを再配列する工程。上記再配列されたイメージ・データを圧縦手段
に供給する工程。更に具体的に言うならば、本発明は次の工程を
含む。第１走査線の変化画素、第２走査線の変化画素
及び第３走査線の変化画素を検出する工程。上記第１走査線の変化画素及び上記第２走査線
の変化画素の間の第１の距離並びに上記第２走査
線の変化画素及び上記第３走査線の変化画素の間
の第２の距離を検出する工程。上記第１の距離及び第２の距離に従つて該第１
の距離若しくは第２の距離を選択的に減少するよ
うに上記２レベル・イメージ・データを再配列す
る工程。上記２次元コーデイングによる圧縮を行う手段
に上記再配列された２レベル・イメージ・データ
を供給する工程。［第１の実施例の説明］本発明は、例えばCCITTの提案T.4の如き２次
元符号化方式のもとで圧縮された圧縮データの量
を減少するように２レベル・イメージ・データを
前処理する。本発明の第１の実施例を説明する前に、代表的
な符号化方式として上記CCITTの提案T.4の２次
元符号化方式を次に説明する。次の表１は上記提案T.4の２次元符号化テーブ
ルを示す。

【表】

【表】第２図を参照するに、上記符号化方式を説明す
るための例示的パターンを示す。ここで、“a₀”
は符号化走査線における参照変化画素あるいは開
始変化画素を表わし、“a₁”は、符号化走査線の
a₀の右にある次の変化画素を表わし、“b₁”は、
参照走査線にあつてa₀の右にある変化画素であつ
てa₁と同じ色の画素を表わす。表１から明らかな
如く、｜a₁b₁｜≦３に対する符号語は比較的短か
い。本発明の基本的概念を第３Ａ図乃至第６Ｄ図を
参照して説明すると、本発明は、第１走査線の変
化画素C₁、第２走査線の変化画素C₂及び第３走
査線の変化画素C₃を検出する。ここで以下の点に注目されたい。 −第３Ａ，４Ａ，４Ｃ，５Ａ，５Ｃ，６Ａ及び６
Ｃ図の第１走査線及び第２走査線を、第２図の
参照走査線及び符号化走査線に夫々対応すづけ
る場合には、変化画素C₁及びC₂は夫々画素
“b₁”及び“a₁”に対応する。 −第３Ａ，４Ａ，４Ｃ，５Ａ，５Ｃ，６Ａ及び６
Ｃ図の第２走査線及び第３走査線を、第２図の
参照走査線及び符号化走査線に夫々対応づける
場合には、変化画素C₂及びC₃は画素“b₁”及
び“a₁”に夫々対応する。次に本発明は、第１走査線の変化画素C₁及び
第２走査線の変化画素C₂の間の第１の距離Δ12並
びに第２走査線の変化画素C₂及び第３走査線の
変化画素C₃の間の第２の距離Δ23を検出する。
尚、この動作は第１図のブロツク１乃至５に示さ
れている。動作はブロツク１で開始する。ブロツ
ク２は３本走査線を３走査線バツフア（図示せ
ず）に記憶する。ブロツク３は、変化画素C₁及
びこれの次の白画素の間の境界３１を検出する。
ブロツク４は変化画素C₂及びこれの次の白画素
の間の境界を検出する。境界３１に関連するのは
境界３２である。そして又、ブロツク４は距離
Δ12を検出する。ブロツク５は境界３２に関連す
る境界３３を検出する。又、ブロツク５は距離
Δ23を検出する。そして動作はブロツク６に進む。ブロツク６
は、式３＜｜Δ12｜＜ｘ又は３＜｜Δ23｜＜ｘが
満足されたか否かを調べる。第４Ａ，４Ｃ，５
Ａ，５Ｃ，６Ａおよび６Ｃ図のように、もしも｜
Δ12｜≦３又は｜Δ23｜≦３であれば、ブロツク
６の答はノーであり、そして動作はブロツク８に
進む。第４Ａ，４Ｃ，５Ａ，５Ｃ，６Ａおよび６Ｃ図
の距離｜Δ12｜又は｜Δ23｜は、表１に示した｜
a₁b₁｜＝１、｜a₁b₁｜＝２及び｜a₁b₁｜＝３のい
づれかの場合に対応する。もし距離｜Δ12｜又は
｜Δ23｜が上記３つの場合の１つに対応するなら
ば、本発明は、第４Ａ，４Ｃ，５Ａ，５Ｃ，６Ａ
および６Ｃ図のイメージ・データのオリジナル・
ビツト・パターンを、第４Ｂ，４Ｄ，５Ｂ，５
Ｄ，６Ｂ及び６Ｄ図のビツト・パターンに夫々変
換するように再配列を行う。次の表２はブロツク８で行なわれるビツト変換
を表わす。

【表】上記の変換を行う理由は次の通りである。 (a) a₁b₁＝０及びa₁b₁＝１の場合に対する符号語
のビツト数は表１に示すように夫々“１ビツ
ト”及び“３ビツト”であり、一方、a₁b₁＝２
及びa₁b₁＝３に対する符号語のビツト数は夫々
“６ビツト”及び“７ビツト”である。そして (b) 上記本発明に従う距離の変換は、例えば８画
素／mmの解像度のオリジナル・イメージ・デー
タのイメージ忠実度に著しい影響を及ぼさな
い。言い代えるならば、オリジナル・イメージ
は、たとえ距離を変換したとしても維持され
る。尚、第４Ａ乃至６Ｄ図については後に詳細
する。もしも式３＜｜Δ12｜＜ｘまたは３＜｜Δ23｜
＜ｘを満足するならば、動作はイエス通路を介し
てブロツク７に進む。ｘの値は、所望のイメージ
忠実度に従つて選択される。言い代えると、値ｘ
は、オリジナル・イメージの情報を、変換後のイ
メージ・データ内に維持するための上限の値であ
る。説明中の実施例では、ｘの値は６に選択され
ている。第４Ａ図は、ブロツク６がイエス出力を
生じる１つの場合を示し、ここでΔ12の値は４で
ありそしてΔ23の値は５である。そしてブロツク
７は｜Δ12｜が｜Δ23｜よりも大きいか否かを調
べる。第３Ａ図のビツト・パターンの場合には、
ブロツク７はノー出力を生じ、そして動作はブロ
ツク10に進む。そして第３Ａ図のオリジナル・イ
メージ・データは、距離Δ12を値３に減少するよ
うに再配列される。第３Ｂ図はこの再配列したイ
メージ・データを示す。オリジナル・イメージ・
データのΔ12及びΔ23の総計距離はイメージの忠
実性を保つために変換後も維持されねばならな
い。｜Δ12｜が｜Δ23｜よりも大きい場合、イエス
出力が発生され、そして動作はブロツク９に進
む。このブロツク９を含むたプロセスの例は図示
していない。ブロツク９において、元のバイ・レ
ベル・イメージ・データの｜Δ23｜は“３”に減
少されるが、このオリジナル・イメージ・データ
における｜Δ12｜及び｜Δ23｜の総訂距離は再配
列後のイメージ・データにおいても維持されねば
ならない。上の説明から明らかな如く、ブロツク８、９及
び10は、ブロツク６及び７の結果に従つて距離
Δ12若いくはΔ23を所定の距離に迄選択的に減少
するように元のイメージ・データを再配列する。本発明に従つて再配列即ち前処理されたイメー
ジ・データは圧縮装置に送られて圧縮される（ブ
ロツク11）。この圧縮装置は、例えば表１の２次
元符号化方式のもとにデータを圧縮する。そして
動作はブロツク12において終了する。さて第４Ａ乃至６Ｄ図について説明すると、第
４Ａ及び４Ｃ図、第５Ａ及び５Ｃ図、並びに第６
Ａ図及び６Ｃ図は、文書又はイメージ走査装置の
CCD走査アレイからのオリジナルの２レベル・
イメージ・データを示す。第４Ａ及び４Ｃ図は
Δ12＝１そしてΔ23＝１の場合を示し。第５Ａ及
び５Ｃ図はΔ12＝２そしてΔ23＝２の場合を示
し、そして第６Ａ図及び６Ｃ図はΔ12＝３そして
Δ23＝３の場合を示す。第４Ａ図のイメージ・デ
ータ即ちビツト・パターンは前述のブロツク８の
動作により第４Ｂ図のパターンに変換され、そし
て以下同様に第４Ｃ図のパターンは第４Ｄ図のパ
ターンに、第５Ａ図のパターンは第５Ｂ図のパタ
ーンに、第５Ｃ図のパターンは第５Ｄ図のパター
ンに、第６Ａ図のパターンは第６Ｂ図のパターン
にそして第６Ｃ図のパターンは第６Ｄ図のパター
ンに変換される。第７図は、第３Ａ乃至６Ｄ図に関して第１図に
示した動作を行う回路ブロツクを示す。３ペル×３ペルのウインドウ７１は、文書イメ
ージの３×３イメージ・ビツトをサンプル即ちピ
ツク・アツプする。例示的な解像度は、水平方向
で８ペル／mmである。第３Ａ乃至６Ｄ図に示した如き本発明に従うオ
リジナル・イメージ・データについてのビツト変
換即ち前処理は変換テーブル７３によつて行なわ
れる。３×３ウインドウ毎のビツト・パターンは
パターン・レジスタ７２を介して変換テーブル７
３にアドレスとして印加され、所望の出力ビツ
ト・パターンを出力線７４に又は制御信号“パタ
ーン・セイブ”を制御線７７にとり出す。パター
ン・レジスタ７２は、３×３ウインドウ７１、１
つ分のビツト・パターンを記憶し、又は変換テー
ブル７３からのパターン・セイブ信号に応答して
３×３ウインドウ７１複数個分のビツト・パター
ンを記憶する。変換テーブル７３のアドレス及び記憶されてい
るビツト・パターンの例を次の表３に示す。

【表】

【表】３×３ウインドウ７１が例えば第４Ａ図に示す
ビツト・パターンをサンプルしたと仮定する。第
１走査線のビツト・パターン“100”、第２走査線
のビツト・パターン“110”及び第３走査線のビ
ツト・パターン“100”は直列に接続されて
“100110100”となり、そしてこの直列ビツト・パ
ターンはパターン・レジスタ７２に記憶され、次
いで変換テーブル７３に供給される。表３を参照
するに、エントリイNo.１において、変換テーブル
７３は上述のアドレスを有しそして、出力パター
ン“100100100”を発生する。この出力パターン
“100100100”は出力線７３及びゲート７５を経て
３ライン・バツフア７６に供給される。ゲート７
５は、直列な出力ビツト・パターン“100100100”
を第４Ｂ図に示す３ラインのパターンに組立て
る。かくして、第４Ａ図の入力ビツト・パターン
は第４Ｂ図のビツト・パターンに変換され終え
た。表３の残りのエントリイ２乃至７は第４Ｃ乃至
６Ｄ図並びに第３Ａ及び３Ｂ図に対するアドレス
及び出力ビツト・パターンを示す。第４Ａ，５Ａ，５Ｃ，６Ａおよび６Ｃ図の場合
には、２つ分のウインドウ７１により囲まれたビ
ツト・パターンが単一アドレスとして使用され、
そして第３Ａ図の場合には、４つ分のウインドウ
７１により囲まれたビツト・パターンが単一アド
レスとして使用されている点に注目されたい。こ
のように単一アドレスを生じるために複数個のウ
インドウを用いる理由を以下に説明する。最初第
４Ａ図を参照するに、これの第３番目の列の全ビ
ツトは“０”である。言い代えると、全走査線に
対する“黒から白への境界”はこの単一ウインド
ウ内に見られる。これとは対照的に、第４Ｃ図の
第１番目の３×３ウインドウは、全走査線に対す
る黒から白への境界を含まず、従つて、黒ペルが
後続ウインドウに迄連続するのか否かを調べるこ
とができない。従つて、第１番目のウインドウに
第２番目のウインドウが接続される。そしてこの
第２番目のウインドウは第３番目の列のビツトが
全て“０”であり、従つて、全走査線に対して黒
から凡への境界がこれら第１及び第２番目のウイ
ンドウ内に存在する。先行ウインドウに対する後続ウインドウの接続
を制御するために、変換テーブル７３は、全走査
線に対する黒白境界を有しないパターンが印加さ
れた時に制御線７７上に制御信号パターン・セイ
ブを発生する。パターン・セイブ信号は例えば
“111111111”のパターンを有する。このパターン
は表３のエントリイｎ−６乃至ｎにおいて示され
ているように出力ビツト・パターンと区別できる
ようなものである。例えば、第３Ａ図のビツト・パターンの処理に
ついて考えると、第１目の３×３ウインドウのビ
ツト・パターンを変換テーブル７３に印加すると
（エントリイｎ−２）、制御線７７にパターン・セ
イブ信号“111111111”を生じ、そして出力線７
４には出力パターンが発生されない。このパター
ン・セイブ信号がパターン・レジスタ７２に印加
さ胆ると、第２番目のウインドウのビツト・パタ
ーンが第１番目のウインドウのビツト・パターン
につづいて記憶される。そして、これら第１番目
及び第２番目のウインドウの組合わされたビツ
ト・パターンはエントリイｎ−１で示すように単
一アドレスとして変換テーブル７３に印加され、
そして再びパターン・セイブ信号が線７７に発生
される。そしてパターン・レジスタ７２は、この
パターン・セイブ信号に応答して、第３番目のウ
インドウのビツト・パターンを前記第１及び第２
番目のウインドウのビツト・パターンと共に記憶
する。この組合されたビツト・パターンは変換テ
ーブル７３に印加されそしてこのテーブルは線７
７にパターン・セイブ信号を発生する（表３のエ
ントリイｎ）。次いで、パターン・レジスタは第
４番目のウインドウのビツト・パターンを記憶
し、そして第１乃至第４番目迄のウインドウのビ
ツト・パターンを組合わせたパターンが変換テー
ブル７３にアドレスとして印加され（表３のエン
トリイ７）、そして変換テーブル７３は第３Ｂ図
のビツト・パターンを出力線７４に発生する。ゲ
ート７５を介して３ライン・バツフア７６に記憶
された出力ビツト・パターンは、第３Ｂ図のビツ
ト・パターンを表わす。３ライン・バツフア７６のビツト・パターン即
ち本発明に従つて前処理されたビツト・パターン
は圧縮装置７８に送られる。この圧縮装置は、３
ライン・バツフア７６からのビツト・パターンを
例えばCCITTの提案T.4の２次元符号化方式のも
とに圧縮を行う。［第２実施例の説明］第８図乃至第１０図は本発明の第２の実施例を
示す。この実施例において、第８図の２ペル×４
ペルのウインドウ８１が、文書イメージ８２の２
×４ペル・ウインドウ開始位置は文書イメージ８
２の左上の角即ち、ペルＬ１Ｃ１〜Ｌ１Ｃ４及び
Ｌ２Ｃ１〜Ｌ２Ｃ４である。２×４ペルのウイン
ドウ８１は最も右のベル位置Cnに向つて逐次的
に移動即ちシフトする。上記の左上角の位置即ちＬ１Ｃ１〜Ｌ１Ｃ４及
びＬ２Ｃ１〜Ｌ２Ｃ４から出発した２×４ペル・
ウインドウ８１が走査線Ｌ１及びＬ２の右端に到
着すると、この２×４のウインドウ８１は次の開
始位置即ちＬ２Ｌ１〜Ｌ２Ｃ４及びＬ３Ｃ１〜Ｌ
３Ｃ４に戻り、そしてこの走査線Ｌ２及びＬ３を
走査する。２×４のウインドウ８１が文書イメー
ジ８２を走査するにつれて、第９図に示すペル変
換が行なわれる。この変換の一例を第８図及び第
１０図に示す。第１０図のＡは走査線Ｌ１及びＬ
２の２レベル・イメージ・データが入力バツフア
（図示せず）にとり出され）第１スイツプを示す。
そして、２×４ペル・ウインドウ８１は、第１ペ
ルＣ１から最終ペルCnに向つて逐次移動される。
逐次移動の夫々の間、２×４ペル・ウインドウ８
１内の８画素（ペル）は、これがパターン１乃至
４のうちの１つに一致するか否かについて調べら
れる。もしもイエスならば、これらの８画素は、
パターン11乃至14のうちの１つと取替えられる。
もしもノーであれば、取替即ち変換は行なわれ
ず、元の画素は変化を受けない。３×４個のペル
の取り出し及びこれら２×８個のペルを第９図の
パターン１〜４に比較することは、第７図のパタ
ーン・レジスタ７２及び変換テーブル７３と同様
の回路配列により達成されることができる。パターン１に対する一致がペルＬ１Ｃ３〜Ｌ１
Ｃ６及びＬ２Ｃ３〜Ｌ２Ｃ６で見い出され、そし
てこれら８つのペルがパターン11に代えられる。
この取替えられたパターン11は第１０図Ｂの太い
実線１０１により示されている。次の一致は、ペ
ルＬ１Ｃ９〜Ｌ１〜Ｃ１２及びＬ２Ｃ９〜Ｌ２Ｃ
１２において見出され、ここでこれら８個のペル
は第９図のパターン３と一致する。そして、８個
のペルは第９図のパターン13と代えられる。この
取替は太い実線１０２により示されている。かく
して、走査線Ｌ１及びＬ２の前処理が第１０図Ｂ
に示すように完了し、そしてこれの第１走査線Ｌ
１′は出力バツフア（第１０図Ｅ）の第１走査線
Ｌ１′に記載される。第１０図Ｃに示す次のステ
ツプにおいて、第１０図Ｂの第２走査線Ｌ２′及
び第８図のオリジナル・イメージ・データの第３
走査線Ｌ３が入力バツフアにつめ込まれる。２×
４ペル・ウインドウは再び左端Ｃ１から右端Cn
に移動する。この２×４ペル・ウインドウ８１が
ベルＬ２′Ｃ９〜Ｌ２′Ｃ１２及びＬ３Ｃ９〜Ｌ３
Ｃ１２に到着した時に、これらの８個のペルに第
９図のパターン４と一致し、従つてこれら８個の
ペルは第９図のパターン14と取替えられる。この
変換は太い実線１０３により示されている。そし
て第１０図Ｃの走査線Ｌ２′及びＬ３の前処理が
終り、そしてこのうち走査線Ｌ２″が第１０図Ｅ
の出力バツフアの走査線Ｌ２″に記載される。次
の工程は、第１０図Ｄの走査線Ｌ３′及び第８図
の走査線Ｌ４を入力バツフアにつめ込む。再び、
２×４のペル・グループがパターン１乃至４と逐
次比較され、そしてもしも一致が見出されると、
８ペル・グループはパターン11乃至14のうちの１
つと取替えられ、そして第１０図Ｅに示す如く走
査線Ｌ３″が出力バツフアに記憶される。出力バツフアのビツト・パターンは圧縮装置に
供給され、この圧縮装置は、例えばCCITTの提
案T.4の如き２次元符号化方式に従つて、出力バ
ツフアのビツト・パターンを圧縮する。本明細書において、水平方向の前処理を説明し
た。しかしながら、本発明に従う前処理は垂直方
向において２−レベル・イメージ・データを前処
理するのに用いられることができる。垂直方向の
前処理において、垂直方向の各列の変化画素が続
出され、そして第１列の変化画素及び第２列の変
化画素の間の距離が予定の範囲にあるか否かを調
べるステツプが行なわれる。更に、前述の実施例
のステツプと同様の動作ステツプが２−レベル・
イメージ・データを垂直方向で前処理するために
行なわれる。実施例ではデータのうちの黒画素を前処理し
た。しかしながら、本発明は第４Ａ，４Ｃ，５
Ａ，５Ｃ，６Ａ，６Ｃ図のパターン及び第９図の
パターン１〜４を反転したイメージ・パターンを
前処理するのにも使用され得る。この場合、白画
素は前景画素として処理され、そして黒画素は背
含画素として処理される。［発明の効果］本発明はデータ圧縮効率を改善するイメージ・
データの前処理方法を与える。言い代えると、本
発明は圧縮データのデータ量を減少する。

【図面の簡単な説明】

第１図は本発明に従う前処理の動作を示すフロ
ーチヤート、第２図は２次元符号化方式の一例を
示す図、第３Ａ図、第３Ｂ図、第４Ａ図、第４Ｂ
図、第４Ｃ図、第４Ｄ図、第５Ａ図、第５Ｂ図、
第５Ｃ図、第５Ｄ図、第６Ａ図、第６Ｂ図、第６
Ｃ図及び第６Ｄ図は本発明に従う前処理の例を示
す図、第７図は本発明に従う前処理を行う概略的
な回路ブロツクを示す図、第８図は本発明の第２
の実施例の説明のために用いたオリジナル・イメ
ージの一例を示す図、第９図は本発明の第２の実
施例において前処理されるパターンを示す図、第
１０図は本発明の第２の実施例における前処理動
作を示す図である。７１……３×３ウインドウ、７２……パター
ン・レジスタ、７３……変換テーブル、７５……
ゲート、７６……３ライン・バツフア、７８……
圧縮装置。

Claims

【特許請求の範囲】１イメージ供給手段から供給された２レベル・
イメージ・データを、２次元コーデイングによる
圧縮前に処理する方法において、第１走査線の変化画素及び第２走査線の変化画
素を検出し、上記第１走査線の変化画素及び第２走査線の変
化画素の間の距離が予定の範囲内にあるか否かを
調べ、上記距離が上記予定の範囲内にある時に上記距
離を予定の距離に減少するように上記イメージ・
データを再配列し、上記再配列されたイメージ・データを圧縮手段
に供給することを特徴とする上記処理方法。２イメージ供給手段から供給された２レベル・
イメージ・データを、２次元コーデイングによる
圧縮前に処理する方法において、第１走査線の変化画素、第２走査線の変化画素
及び第３走査線の変化画素を検出し、上記第１走査線の変化画素及び上記第２走査線
の変化画素の間の第１の距離並びに上記第２走査
線の変化画素及び上記第３走査線の変化画素の間
の第２の距離を検出し、上記第１の距離及び第２の距離に従つて該第１
の距離若しくは第２の距離を選択的に減少するよ
うに上記２レベル・イメージ・データを再配列
し、上記２次元コーデイングによる圧縮を行う手段
に上記再配列された２レベル・イメージ・データ
を供給することを特徴とする上記２レベル・イメ
ージ・データの処理方法。