JPH03201866A - 圧縮形態のデータを含むデータから画像スキュー角度を決定する方法 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 本発明は、概して、走査画像に存在するスキューを検出
する方法に関し、より詳しくは、画像のある特徴のカウ
ントに基づいた、また圧縮された形態で存在する画像の
スキューを検出する方法に関するものである。

人間の目は、直角からごく僅かな偏位を検出することが
でき、エリアシング（ａｌｉａｓｉｎｇ）エラーに起因
する不連続性がこれらの偏位に注意を引きつける簡単な
構造のディジタル画像においては特にそうである。テキ
ストや複雑なグラフィック画像のスキューに対する人間
の感覚に関する有効な情報はほとんどない。明確な特徴
のある座標フレーム中に情報が現れる場合、スキュー角
度は一貫してかつ相当に過大評価される。スキューがあ
るということは、審美学上喜ばしいことではなく、かつ
実用的効果もない。スキューの存在は、一つ或いはそれ
以上のコーナーが、スキューのためにスキャナの視野か
ら外方に外れることにより、画像の全てのソース域の捕
獲が失敗することになる。

スキューした画像は、ページ座標系に正確に記録されて
いるのと同じくらいには、迅速に或いはコンパクトに圧
縮されない。スキューされたフィールドは、例えば刈り
込み（ｃｒｏｐｐｉｎｇ）や仲人のような標準のページ
レイアウトや合成操作に用いるのはより困難である。

スキューは、ディジタル化の時か或いはとりわけフォト
コピー時におけるディジタル化の前のいずれかにおいて
、紙を供給するに際しての困難さを含むいくつかの場合
に生してくる。再生か、ディジタル走査と、これにより
得られるビットマツプのプリントによってもたらされる
電子写真複写環境においては、スキュー角度の早くて正
確な検出が、スキュー画像の修正と記録するための資源
の必要性を充分に縮小することが可能である。

スキュー角度検出は、伝統的に２工程で行われる。まず
第１に、アライメントの質が基本となっている特徴が決
定され、次いで企てられたアライメントが前のサンプル
アライメント或いは他の基準に関して優れているかどう
かを決定するために種々のテストが課せられる。ここで
いう「アライメント」とは画像の要素の方向付けのこと
である。

現在に至るまで、スキュー角度の決定は、圧縮状態での
画像データで達成されてきた。ここで「画像」とはパタ
ーン或いは識別可能域の集合を意味し、画像、表示か或
いはこのどちらでもないか、典型的であるが、排他的で
はなしに、プリントされたページに見いだされるもので
ある。「画像データ」とは、適当なシステムによって画
像の再生に用いられる、典型的であるが、排他的ではな
いフォーマット中のディジタルな画像のことをいう。「
圧縮された」フォーマット中のデータとは、ここでは「
圧縮されていない」フォーマット中のデータから、デー
タを記憶する必要のある例えばビットによるメモリスペ
ースの大きさに縮小されることを意味する。この場合、
データを圧縮するのに用いられる方法は問わない。圧縮
された画像データからのスキュー角度の決定は、現在ま
で考察されてきていない。或いはもし考察されてきてい
るとしても、圧縮された画像データ上からスキューを決
定する操作には必要以上のことであり、かつ、決定的に
画像を圧縮されたデータフォーマットに変換するのは不
必要な工程であるという一般的な考えの下にかたずけら
れてきている。

圧縮されていない画像のスキュー角度を決定する技術と
しては、ヘンリー・ニス・ベアード（Ｈｅｎｒｙ　Ｓ、
　Ｂａ１ｒｄ）による「印刷物のスキュー角度」と題す
るハイブリッド画像システムに関する５ＰＳＥシンポジ
ウム議事録、ｐｐ２１〜２４．１９８７　（以後、ベア
ードという）に開示されているものを参照する。まず最
初に、ベアードは、マーク或いはテキストである関連要
素とテキストでない要素と識別をしなければならない。

この点に関し、この明細書の目的としての「テキスト」
マークすなわち関連要素は、文字、数字、句読点及び関
連する符号からなる。この「テキスト」マークは「非テ
キストＪマーク或いはテキストではない典型的にはグラ
フィックス、シンボル或いは画像の描写のような部分で
あるＰＡ連要素と識別されている。基準点を位置決めに
用いる方法として、ベアード技術はテキスト画像にとっ
て意味のある結果を生しるのみである。テキストとして
のこの分類は、テキストマークの最大寸法が予め定めら
れた最大フォントサイズ、例えば２４ポイント中のｒｅ
ｍＪ以下、ないしこれと同等であることに基づいてベア
ードによって作られたものである。

ベアード技術のアライメントアルゴリズムは、各マーク
或いは関連する要素に関係した選ばれた特徴のアライメ
ントに基づいて作用する。「マーク」は、関連する要素
として用いるものとする。

「関連する要素」は、本願明細書の目的として、一連の
カラー付きユニット、典型的には互いに関連する同様の
色の画素（「ビクセルＪ）に定義される。この目的で普
通用いられる特徴は「基準点」である。ここで用いる「
基準点」は予め定められた一連のルール（各マークにつ
き同じルール）によって位置決めされ、かつマークの特
徴を表現する選ばれた目的のために用いられるマークの
ポイント或いは関連するマークのポイントである。例え
ば、ベアードは基準点として各マークのまわりに境界と
なるボックス（枠）の下方中心に用いている。ベアード
の基準点１０は第１Ａ図のマーク１４のまわりの境界線
１２上の十字線として示される。

英語のテキストの完全に一直線上にある水平線において
、例えば各基準点は文字のベース（ベースラインと呼ぶ
）で同じ水平線１６上に位置する。

ただし、例えば第１Ａ図の文字「ｉ」、ある種の句読点
及びたれ下り文字、つまりマークの一部がベースライン
より下に下かっている、例えば文字ｒｇ」　ｒｐＪ等は
別である。基準点が各関連要素に指定されているので、
ドツト付き文字「ｉＪと「ｊ」及び多くの句読点マーク
（：？：”）は−文字当たり一つ以上の基準点か生じる
ことになり、これら基準点のうちの少なくとも一つがベ
ースラインに対して大きくずれてしまう。たれ下がりを
有する文字は基準点から離れて形成されるが、ベースラ
インの近くにはある。たれ下がり文字は統計的にはそう
普通ではなく、ベアードの方法（及び本発明は発明にお
いても）は真のベースラインを決定する効果を認識し、
補正するための手段を提供する。注目したいのは、画像
中の一つの関連要素当たりの基準点は正確には一つであ
るということである。

本質的には、ベアードは、交換するアライメントに変化
のために一つの「ライン」当たりの基準点の数を決定す
ることによってスキューを計算した。ここで用いるライ
ンは例えばドキュメント（書類）を横切る走査線及び例
えばマージン或いはページエツジのような選択された特
徴に垂直に方向付けられた想像上の複数の走査線の一つ
を意味する。回転アライメントは、基準点の三角法によ
って計算される。

１１Ｂ図、第１Ｃ図を参照して、１本のライン当たりの
基準点の数の数え方は、矢印ｐで示される投影方向と鉛
直なアキュムレータライン１８上に基準点ＩＯの位置を
投影することによって達成される。

アキュムレータライン１８は、例えば６点文字の高さの
１／３に等しい均一の予め定められたｈの「ビンＪ　２
０に区分される。高さｈは適当に変えることができる。

高さｈは２ビクセルと同しくらいに小さくすることもで
きる。しかし、ｈが小さくなるにつれて、計算時間が長
くなる。重要なのはｈが文字の高さに近づくとスキュー
角度決定性能が劣化することである。ビンについて説明
すると、１本のライン当たり正確に一つのビンである。

選択されたラインのための基準点の数は、そのラインに
対応するビンに投影される基準点の数と等しくなる。

この方法は、比較的少ない基準点（画像の性質によって
決まる）となるので、アライメントはｌよりも大きい正
の累乗の和、例えば回転してアラインされたビン中に現
れる基準点のカウントの２（二乗の和）に基づいたアラ
イメントの計算によって効果的になされる。分布の変動
は、スキュー角度が決定されるアライメントの「累乗」
指数となるカウントの二乗の和を最大にすることによっ
て最大にされる。ｑＩＢ図は、基準点１０の位置及びビ
ンがスキューされたテキストと一致していないスキュー
されたテキストサンプル上の各ビン２０の相対的な大き
さを示す。第１Ｃ図は第１Ｂ図の同じスキューされた画
像の基準点の一致したビンへの分布を示す。

アライメントの各変動の累乗の計算には、各基準点の位
置がわかっていることが必要である。すなわち基準点の
座標は、原点からの角度と偏位によって基準点を新しい
一連の座標に数学的に変換するのに用いられる。この工
程は基準点を完全に収集するために行われ、この変換の
前後におけるアライメントの累乗が比較される。各々の
比較から最大の累乗を有するアライメントに対応する角
度が保持される。選ばれた範囲内の全ての角度上にアラ
イメントがこの方法によって比較された後、スキュー角
度が最大の累乗を有するアライメントに対応する角度と
みなされる。しかし、アライメントが弱いか或いは多重
アライメントの場合、この仮定は別の方法で証明する必
要がある。

本発明は、従来技術の種々の問題点や欠点を解消する新
規なスキュー角度決定方法を提供する。

本発明の一つの観点は、スキュー角度が大きくなるに従
って、マークの底部と境界枠の底部との間の距離が大き
くなるという、ベアードのスキュー角度決定方法におけ
る問題を見つけることにある。この距離の差は、スキュ
ーの角度の正弦の関数として大きくなる。この点が基準
点のカウント中の誤差となり、この誤差の二乗としてス
キュー角度の決定に影響を与える。

この観点は、さらにベアード法の問題は、マーク自身の
上に位置される基準点に基づいたスキュー角度を決定す
ることによって解決できることを見つけることに基づい
ている。

本発明のこの観点に関連した点としては、ラインの端が
スキュー決定の基準となる有効な一連の特徴を形成する
ことを発見することである。特に有効な一連の特徴は、
水平方向に向けられた画像のためのベースラインに、或
いはこれの近くに配置されたラインの端々或いは垂直な
或いは円柱方向に付けられた画像のための垂直ラインで
ある。

包括的な画像中のライン端の検出は困難な仕事であるこ
とが立証されている。しかし、一つの方法が発見され、
かつ一連のライン端を含む一連の特徴を検出する本発明
の他の観点が形成された。

連の特徴は、使用するライン端の有効性が少なくなるよ
うな大きさに限定される。一つの走査線を続く走査線と
比較することによって、ピクセルカラー変化が位置決め
される。ピクセルカラー変化の適切な選択が、スキュー
角度を決定する非常に有効に使用できるライン端を含む
一連の特徴を作り出すことができる。

本発明の他の観点は、スキュー角度を決定する従来法の
他の問題が、特徴（基準点）位置のコンピュータによる
決定法を含んでいることを認識することである。ベアー
ド法によれば、マークをそれと認めなければならないだ
けでなく、境界枠かマークのまわりに作られ、かつ、境
界枠の下方中心が位置決めされなければならない。

この観点は、さらに上述の問題が第１ラインの走査と次
に続くラインの走査との比較から基準点を決定すること
によって解決できることの発見に基づいていることであ
る。基準点の位置は、次の走査線上の対応する地形的な
特徴なしに、或いはそうでなければ前の走査線上に位置
する対応する地形的な特徴なしに、第１走査線上に位置
決めされた選ばれた地形的特徴の位置に対応する。この
点に関し、この明細書の説明の目的として、「地形的」
とは、マークの特徴を意味し、その画像或いはその部分
が例えば形状、大きさ、湾曲度、オーバーラツプ等のよ
うなその幾何学的形状特徴に基づいている。この点は、
マークの特徴、その画像或いは部分がその幾何学的形状
に基づいてはおらず、例えばカラー陰影等のようなある
他の属性に基づいている「非地形的Ｊ特徴から識別され
る。

本発明のさらに他の観点は、スキュー角度決定の従来法
が、テキスト画像のためのみ意味のある結果をもたらす
という認識にある。この点は基準点の位置を決定するの
に用いられる方法となる。

境界枠がマークのまわりに作られ、境界枠の下方中心が
基準点として用いられる。ベアードは、境界枠をテキス
トマークのまわりのみに作るのに選んだ。この選択はテ
キストマークの位置が一致されていること、及び非テキ
ストマークが一致していないことを推測することに基づ
いてなされる。

境界枠が非テキストマークのまわりに作られた場合、マ
ークから生じた基準点はノイズとして現れ、スキュー角
度を決定するのに必要とする重要なデータからそれてし
まう。この点から、本発明の観点が、スキュー角度決定
がテキスト或いは非テキスト画像に、或いは、テキスト
と非テキストの組み合わせたものに実行できることにあ
ることになる。マーク自身の上に位置された基準点にス
キューの決定の基準を置くことによって、境界枠を作る
必要がなくなる。この観点から非テキストマークから生
じる基準点にはその結果に正確性が大きく加えられる。

このようにして、従来技術のテキストの制限が克服され
る。

本発明のさらなる観点は、いかなる方法も圧縮されたフ
ォーマット中の画像データをスキュー角度を決定するの
に用いていないという問題を認識することにある。この
観点は、本発明の他の観点に関係する。すなわち、マー
ク、画像或いは圧縮されたフォーマット中のデータによ
って代表されるその画像或いはその一部におけるスキュ
ー角度決定を実行することが、多くの状況と多くの目的
に関して大変有利である。もし、それが排他的でなけれ
ば、多くの最近のシステムが圧縮されたフォーマット中
で大きな比率でデータを処理すると仮定すると、現時点
では画像データを圧縮されたフォーマットに用いるスキ
ュー決定法のための技術か必要である。

したがって、本発明のさらに池の観点は、圧縮されたフ
ォーマット中の画像データに基づいたスキュー角度決定
方法を提供することである。この点は、圧縮されたデー
タフォーマット中に検出可能な特徴を用いることを含意
している。すなわち、実質上全てのバイナリ画像圧縮シ
ステムか圧縮（例えばピクセルカラー変化）のために走
査された画像の物理的な特徴に用いる。データを用いる
ことによって、これらの特徴を有することになり、画像
データを完全に圧縮することなしにスキュー角度を決定
することができる。

ＣＣＩＴＴグループ４圧縮フォーマット（以後グループ
４という）は、ファクシミリの画像の伝送、ワークステ
ーションとサーバ間の画像の中間伝送、光学媒体及び磁
気媒体上の記憶フォーマット及び他の適用のための規格
となっている。圧縮アルゴリズムのソフトウェア実行は
、ある特定目的のＶＬＳ　Ｉハードウェア実行としても
利用できる。例えば、アドバンスドマイクロデバイシズ
（Ａｄｖａｎｃｅｄ　Ｍｉｃｒｏ　Ｄｅｖｉｃｅｓ）７
９７１Ａプロセツサは、ＣＣＩＴＴフォーマットに関す
るデータ圧縮／伸長のための専用回路である。したがっ
て、本発明の他の観点は、グループ４規格によって圧縮
された画像を使用するスキュー決定方法を提供すること
である。

本発明のこの観点に関連して、非常に有効な結果が、基
準点の位置がスキュー決定に基づいたグループ４圧縮に
よってもたらされる、いわゆる「バスコード」の位置を
用いることによって達成される。二つのタイプのバス、
すなわち白ビクセルのバスと黒ピクセルのバスが認識さ
れている。

ＣＣＩＴＴグループ４の圧縮規格では、これらの二つの
間に差異はないが、本発明はさらに二つの観点がある。

第１に白ビクセルを表示するバスコードを選択すること
によって、スキュー角度決定の正確度が大きく改善され
ることを発見し、第２にスキュー角度決定によって二つ
のタイプのバスコード間を区別するための方法を実行す
ることである。

本発明の範囲及び従来のスキュー決定方法に関連する問
題に接近する方法は、付随する図面及び特許請求の範囲
と同時に見られるとき、以下の詳細な説明からより容易
に明らかになる。

第１Ａ図は、従来技術の一つの方法によるスキューして
いない画像上の基準点の位置を示す。

第１Ｂ図は、前記従来技術の方法によるスキューした画
像上の基準点の位置を、整列していないビンへの基準屯
の分布のプロットとともに示す。

第１Ｃ図は、第１Ｂ図に示される同じスキューした画像
上の基準点の位置を、整列したビンへの基準点の分布の
プロットとともに示す。

第２図は、本発明のスキュー角度決定方法による動作が
可能なコンピュータシステムの一部を示す。

第３Ａ図から第３Ｃ図は、ＣＣＴＴＴグループ４圧縮規
格の三つのエンコードモードを示す。

第４Ａ図及び第４Ｂ図は、それぞれスキューしていない
及びスキューしたテキストでのＣＣＴＴＴグループ４圧
縮規格のバスコードに基づいた基準点の位置を示す。

第５Ａ図及び第５Ｂ図は、それぞれスキューしていない
及びスキューしたテキストでのＣＣＩＴＴグループ４圧
縮規格のバスコードからの白バスコードに基ついた基準
点の位置を示す。

第６図は、本発明の一つの観点の流れ図を示す。

第７図は、本発明の他の観点の流れ図を示す。

第８図は、本発明の一つの観点の例として使用されたス
キューしたテキストの一部を示す。

第９図は、本発明によるアライメント決定に使用された
第８図のサンプルテキストに対応した白バスコードの位
置を示す。

第１Ｏ図は、第８図のサンプルのスキューしたテキスト
に対応したアライメントの累乗のプロットを示す。

第１１図は、多重スキュー角度を有するテキストに対応
したアライメントの累乗のプロットを示す。

以下、図示実施例を詳細に説明する。

これまでに述べた観点及び他の諸観点を用いた新規なス
キュー決定方法を説明する。本発明の方法は、特に走査
された画像中のスキューの決定に適用可能である。本明
細書において、画像データは、はっきりしたユニットに
、好ましくは画像のラインに分割されると仮定している
。この分割は、例えば画像を走査し、かつ、各走査ライ
ンの始めと終りに或いはライン全長に指示を挿入するこ
とによって達成される。この方法は、当該技術としては
公知である。便宜上、このユニットは以後走査線と呼ぶ
。

普及の度合いが増してくると、走査された画像は圧縮さ
れたフォーマットで処理される。例えば、ファクシミリ
装置は、実質上完全に圧縮されたフォーマットで走査さ
れた画像で動作する。このため、本発明は画像データは
、圧縮された形態（ここでは圧縮されたデータドキュメ
ントとも呼ぶ）を仮定して説明する。

しかし、一つの技術として明白なのは、本発明が圧縮さ
れていない画像中の画像データにも同様に適用可能であ
ることである。

第２図は、本発明が適用される環境のブロックフォーマ
ットを示す。特に第２図は、本発明の種々の観点に基づ
いて動作するように組まれたコンピュータシステム５０
の一部を示す。このコンピュータシステム５０にはスキ
ャナ５２が含まれるか、或いはシステムがスキャナから
の出力信号を受けるようにこれに接続されている。この
スキャナは画像を走査し、かつ、その画像を表すディジ
タルデータはプロセッサ５４に連絡されている。このプ
ロセッサは入力及び出力動作を制御ｌするとともに、バ
ス６０を介してプログラムメモリ５６とデータメモリ５
８に連結されている。

プログラムメモリ５６は、特にスキャナ６２によって画
像の走査を制御するためのルーチン６２と、画像を表す
ディジタルデータを圧縮されたデータフォーマットに変
換するためのルーチン６４と、この圧縮されたデータか
らスキュー角度を決定するためのルーチン６６を含んで
いる。したがって、このプログラムメモリ５６は、デー
タメモリ５８と関連しており、特に記憶場所６８におい
て走査制御ルーチン６２の制御下でディジタルデータ構
造かスキャナ５２によって作られ、記憶場所７０におい
て走査画像の圧縮された描写のデータ構造が圧縮ルーチ
ン６４によって作られ、記憶場所７２において例えば基
準点の位置のような選択されたポイントデータを含むデ
ータ構造がスキュー角度決定ルーチン６６によって作ら
れる。プログラムメモリ５６とデータメモリ５８間の連
結を容易にするために、入力と出力動作がなされるよう
にして両者か互いにバス６０によって接続されている。

メモリ５６及び５８に関して一つ付は加ええる点は、こ
れら両者を明確にする目的で別々に描かれているが、実
際には、本発明に影響を与えることなしに、コンピュー
タシステムの単一のメモリブロックの一部としてもよい
。

プロセッサの制御下でスキュー検出ルーチン６６かデー
タメモリ５８の種々の部分にアクセスしてスキュー角度
の計算に必要なデータを得る。−度この計算がなされる
と、スキュー角度が出力部７４に出力される。この出力
部は、ＣＲＴ表示器のような結果を表示する手段と、ハ
ードコピープリンタ等からなるか、或いは結果をさらに
別の操作をするのに、例えば画像データの補正をスキュ
ー等の補正に用いるための手段からなる。

画像データは、グループ４基準に基づいて圧縮されてき
たと仮定されるが、適当な修正のなされた本発明は、他
の圧縮体系、例えばＣＣＩＴＴ２次元グループ３フォー
マット等を用いて同様の結果を作る。グループ４のコー
ド体系は、対をなす続いている走査線に見られるピクセ
ルカラーの変わり目の存在とその相対的間隔に依存して
いる。

グループ４において、次いで各ラインがコード化される
と「コーディングライン」となり、かつその前の「基準
線」に関してコード化される。最初のラインが人工的に
規定された全白基準線に関してコード化される。グルー
プ４圧縮規格についてのより詳しい説明については、ハ
ンター（Ｈｕｎｔｅｒ）他による「国際ディジタルファ
クシミリコーディング規格ＪＩＥＥＥｆｊｌ事Ｒ，Ｖｏ
ｌ、　６８．に７．１９８０年７月、　ｐｐ８５４−８
６７及び国際電気通信連合、ＣＣＩＴＴ（国際電信電話
諮問委員会）レッドブック、ジュネーブ１９８５　（Ｉ
　Ｓ　Ｂ　Ｎ　９２−６ｌ−０２２９１−Ｘ）ヲ参照ス
るものとする。

グループ４フオーマツト中のエンコーディングは、三つ
のモード、すなわち垂直、水平、及びパスがある。これ
ら三つのモードは第３Ａ図、第３Ｂ図及び第３Ｃ図に基
づいて次に説明する。近接する走査線が、例えば黒から
白への基準線上で第１ピクセルカラー変化があるかどう
か、コーディングライン上に対応するピクセルカラー変
化（すなわちこちらも黒から白）が存在するどうかを決
定するのに比較される。基準線上の変化からコーディン
グライン上の変化の存在と相対的間隔がモードの決定に
用いられる。

第３Ａ図を参照して、垂直モードは近接する走査線上で
黒から白或いは白から黒への移り変わり何時が水平方向
に近接（≦３ピクセル）しているとき、従って少ないビ
ット数でエンコードされる場合に用いられる。水平モー
ドは、移り変わり位置が第３Ｂ図に示すように３ピクセ
ルよりも離れている場合に用いられる。バスモードは、
基準線上の移り変わりが第３Ｃ図に示すように、コーデ
ィングライン上に対応するものがない場合に用いられる
。

圧縮されたデータは、特にコーディングラインとは反対
に基準線上で測定され偏位を意味する偏位と一緒にモー
ドコードを含んでいる。

第４Ａ図、第４Ｂ図を参照して、ベアードが用いたマー
クのまわりの境界線上に配置された基準点の代わりに、
本発明はマークの地形的特徴の位置に基ついて基準点を
位置決めする。これら地形的特徴は、単にマーク自身の
上に位置される。特に、スキューは、画像のグループ４
圧縮表現中のパスコードの位置から決定される。スキュ
ーされていないテキスト及びスキューされたテキスト上
のノくスコード基準点７ｂの位置は、それぞれ第４Ａ図
。

第４Ｂ図においてｒＸＪ印で示される。

全てのバスコードは、マーク上のポイント（１点）に図
して規定されるので、スキューの範囲に拘わらず、全て
の基準点はマーク上のある点で位置決められる。さらに
、一つ以上のバスコードがマークを表す圧縮されたデー
タ中にあるので、１つのマークより一つ以上の基準点が
あることになる。例えば、典型的なフォントスタイルに
とってはパスは上下のケースｒＡＪ、　　ｒＨＪ、　　
ｒＫ」等ヲ含む多くの文字のベースラインに沿って二つ
の位置に生じる。また上下のケース「Ｍ」のベースライ
ンに沿って三つの位置に生しる。

パスはエリアシングエラーとしても発生し、例えば第４
図に示すようにスキューされていない「Ｇ」のクロスバ
−〇下側及びスキューされていない「Ｋ」の右脚に見ら
れる。このようなエリアシングエラーを区別することは
本発明の範囲外である。しかし、ある状況のエリアシン
グエラーは有効で意味のある結果に結びつく。例えば、
長い水平方向の構造がディジタル化されると、エリアシ
ングエラーがしばしば発生する。このエリアシングエラ
ーの存在によって、黒から白への移り変わりを表すバス
コードを生ぜしめる結果となるので、長い水平線は、そ
のコードが表出するアライメント中に全くあいまいさを
含まずに多数のバスコードを提供する。従って、水平方
向に整列された図形的構造が、それがエリアシングエラ
ーを生じる傾向にあるために、スキュー角度の決定を大
きく改善する。ここで、つけ加えておかなければならな
いのは、大きい非水平方向構造は、本発明の特性を大き
く低下させることはないということである。なぜなら、
この構造は一般的にバスコードを生じるエリアシングエ
ラーに従属していないからであり、エリアシングエラー
がグループ４垂直モードを用いてエンコードされるため
である。

二つのタイプのパス即ち白ピクセルのパスによる白パス
と、黒ビクセルによる黒パスがある。白パスは黒構造の
底部を表すものであるから、たとえばライン端のような
処理されていないビットマツプ中の関連要素の底部に見
られるものと幾分類似している。実際に、各関連要素の
底部において少なくとも一つのパスが保証される。従っ
て、白パスは基準点として用いるのは有利であるが、当
該技術においては、本発明に基づいて適当な状況におい
て黒パスもスキュー角度を決定するのに用いることがで
きることは明白である。スキューされていないテキスト
及びスキューされたテキスト上の白バスコード基準点７
８の位置をそれぞれ第５Ａ図、第５Ｂ図に矢印で示す。

パスのグループ４エンコードは、白パスと黒パスを区別
していない。パスのどのカラーがエンコードされたかを
知るために、状態を維持しなければならない。本発明に
よれば、状態は架空の完全な白の最初のラインに対応し
て設定されたバイナリ状態ビットによって維持される。

パスコードが生じるために、状態ビットが反転され、こ
れによってバスコードの状態（すなわちカラー）のラン
ニングトラックが維持される。

第４Ａ図、第４Ｂ図と第５Ａ図、第５Ｂ図を比較すると
、第５図のテキストのベースラインに生じた基準点の数
は、第４図の基準点よりも少なくなっているのがわかる
。たとえば、第４Ａ図、第４Ｂ図において文字ｒＯＪ８
０では二つの基準点すなわち上方ポイント８Ｊ２と下方
ポイント８４があることが分かる。下方ポイント８４は
ベースライン８６上にあるが、上方ポイント８２はベー
スライン上にない。第５Ａ図、第５Ｂ図において、同じ
文字「Ｏ」８０ではベースライン９０上に位置する単一
の基準点８８があるだけである。これは図形的な表示で
、白パスはアライメントによるスキュー測定を基準とす
る基準点を提供するために有利である。しかし、ある種
の「ノイズ」が白バスを用いることで発生する。すなわ
ち発生したいくつかの基準点は、ベースライン上には直
接位置せず、ベースライン情報に加えられる。

例えば文字「Ｃ」は二つの自パスを生じることがあり、
その一つはマークの底部にもう一つは文字「Ｃ」の右側
の開口部の上方限界を形成するストロークの底部に生じ
る。同様にして、バスコードのもとになる文字「Ｍ」の
中心の底部がある種のフォントでベースライン上にてな
いことかある。

この種のノイズ信号を区別することは本発明の範囲外で
ある。しかし、このノイズ信号の発生は統計上そうしば
しば生じるものではなく、スキュー角度決定の精度を大
きく落とすものでもなく、また計算時間が相当長くなる
わけでもない。

第６図は第２図のプログラムメモリ５６の実施例のブロ
ックダイヤグラムを示す。ルーチン６６の出発点につき
、画像が走査されると仮定すると、ディジタルデータが
走査された画像に対応して発生され、このディジタルデ
ータがグループ４圧縮データを生じるような選択された
データ圧縮方法に基づいて圧縮の処理が課せられる。

まず、例えばデータメモリ５８の記憶場所７２に記憶さ
れた圧縮された画像データのデータ構造中の白バスコー
ドが位置決めされる。これを第６図のボックス９２で示
す。−度目バスコードが位置決めされると、適当な座標
系の位置が決定される。これをボックス９４で示す。横
軸ｘ１縦軸ｙを有する直角座標の座標対が一般的にこの
目的として便利であるが、本発明の範囲内で、例えば極
座標のような他の座標系もそれが適当な場合に用いるこ
ともできる。座標対アレイ９６をコンピユーテイングア
ライメントで使用するために形成できる。これについて
は次に詳しく説明する。白バスコードの位置の座標対を
記憶した後、走査されたページの終端が達したかどうか
を決定するためにテストが９８で行われる。もし到達し
ておれば、次に詳しく説明するようにスキュー角度の決
定が行われる。

もし到達していなければ、ページ上にもし白バスコード
があれば次操作のためにサーチが行われる。

前述の四つの工程９２〜９８は、座標決定ルーチン１０
０として集合的に表される。走査決定ルーチン６６はサ
ブルーチンとなり、次に走査決定ルーチン６６はサブル
ーチンとなり、次に第７図に基づいてさらに説明する。

ブロック　１０１はグループ４圧縮フオーマツト中のデ
ータの入力を表す。ｘ−ｙ座標対を用いて、Ｘとｙをま
ずページのスタートを表す０におく。この様子を工程１
０２で示し、各々の新しい走査されたページのスタート
において行う。

ブロック　１０３は、グループ４コードの検出を表す。

これまでに説明したように、三つのタイプのグループ４
コード、すなわち水平、垂直及びバスのコードがある。

前述したＣＣＩＴＴレッドブックを参照する。検出グル
ープ４コードがキャラクタ列認識によって実行できる。

当該技術範囲内のこれ以外の種々の方法でもコード検出
できる。

度グループ４コードか検出されると、そのタイプを決定
する必要がある。すなわち、三つのグループ４タイプの
うちのとれであるか、つまりバスコードか白バスコード
か或いは黒バスコードであるか決定しなければならない
。この工程は一連のテストによって行われ、その結果で
Ｘ座標がどのように決定されたかが決定される。Ｘ座標
がＸの前回値に相当すると、座標決定ルーチン１００を
通る直前のバス中の工程１０３によって位置決めされた
コードと関連し、新しいＸ値に相当すると、座標決定ル
ーチン１００を通る今回のバス中の工程１０３によって
位置決めされたコードと関連する。

コードが位置決めされると、そのコードが水平コードで
あるかどうかを決定するためにテストが課される。もし
そうであれば、Ｘの新しい値はＸの古い値に、水平コー
ドに関する偏位値を加えたものとなる。すなわち、グル
ープ４の水平モードはモードを示すコードと、基準ピク
セルカラーの移り目と今回ピクセルカラーの移り目との
間のビクセル数を示す偏位を含んでいる。水平コードの
場合、この偏位は特定ライン上ピクセルカラーの移り目
と同じライン上の次のピクセルカラーの移り目との間の
ビクセル数になる。この状態を１０６で示す。

注目したい重要な点は、Ｘのこの新しい値はアライメン
トを決定するのに用いる横座標値にはならないことであ
る。というよりはむしろこの値は走査線上の第１ビクセ
ル位置から偏位したランニング値である。自バスコード
に関係するＸ値のみがアライメント決定に用いられる。

水平コードが検出されたと仮定された時期を求めるため
に２進ピクセルカラー状態ビツトが１２２でインクリメ
ントされる。この操作を行う方法と目的を次に詳しく説
明する。−度Ｘの新しい値が計算されると、Ｘは１０８
でチエツクされ、ライン端が到達されたかどうかが決定
される。この操作はビクセル中でＸを走査線の公知の長
さと比較することによって好適に行うことができ、Ｘが
この値に達するとライン端が検出されたことになる。

ライン端が到達していなければ、このラインにつきコー
ド検出が１０３にて続行される。ライン端が到達すると
、Ｘは次のラインの始まりに対応して１１０にて０に設
定され、ライン数のランニングカウントを保持している
ｙが１だけインクリメントされ、１１１でチエツクされ
てページ端が到達したかどうかが決定される。この決定
は、Ｘについてはｙをページ当たりの公知のライン数と
の比較により行い、ｙがこの値に達すれば、ページ端が
検出されたことになる。ページ端に到達すると、多数の
アライメント角度を通過した種々のアライメントのため
の累乗か＋２６で決定される。これについては、次に詳
しく説明する。ページ端に到達していなければ、コード
検出が１０３で再開される。

コードが水平でないと決定されると、垂直コートである
かどうかを１１２でテストする必要がある。

垂直モード中の基準線上の値として用いるために種々の
ラインからなる移り変わり位置を記憶する必要がある。

この操作は（ｘｉ、、ｘ２．、　　・・・ｘｎ、）形式
の配列で行われる。ここにｒは基準線（前の走査線）上
の値を示し、ｎは基準線上の全コード数である。前のラ
インにつきＸ値を保持すればよいだけであるから、新し
いＸ値は一度決定された古い値に上書きてきる。この操
作は１１４で示される。

垂直コードが検出されたと仮定すると、Ｘに対する値が
次のようにして１１６で計算される。垂直モードは基準
線とのビクセルｂ１におけるビクセル移り目との間の偏
位からコード化される。この偏位の計　にはＸ値のみ関
係するので、この屁には単に　　ｘｂ、−ｘａ、　　で
簡単に計算できる。

ここにｘ　ｂ　＋及びＸａ、は各々ビクセルｂ、とａに
おけるＸ値である。新しいＸ値は古いＸ値にこの偏位を
加えたものである。再度、２進のピクセルカラー状態ビ
ットが１２２でインクリメントされ、新しいＸ値が１０
８でテストされラインの終端が達したかどうかが決定さ
れ、ページの終端が到達していれば＋１２で決定される
ようにして次々実行される。

検出されたコードが１０４．１１２でのテストに失敗す
ると、コードは消去工程によってバスコードになる。す
でに説明したように、白バスコードと黒バスコードを区
別するのは重要である。白バスコードはアライメントの
決定に用いられるか、黒バスコードはこれに用いられな
い。グループ４は白バスコードと黒バスコードを区別し
ないので、２進ピクセ１ルのトラックを保持して、１１
８におけるカラー状態ビットの状態を決定する。まず最
初に、状態ビットが１１２においてＯに設定される。任
意に、０が自バスコードに対応して運ばれる。コードが
検出される毎に状態ビットがチエツクされる。

状態ビットが０でない、すなわち、バスコードが白バス
コードでない場合、Ｘの新しい値が１２０においてＸの
古い値と等しく設定される。次に現れるコードがバスコ
ードでないと仮定すると、次のコードは、次のＸを正し
く計算するのに必要な必要情報を連想できる。次に現れ
るコードがバスコード、であれば、コードがバスコード
でないものが現れるまで処理が繰り返される。この工程
はグループ４バスコードの最も重要な部分である。引き
続いて、Ｘの新しい値が１２０で設定され、状態ビット
が次に現れるバスコードのために１２２で増幅される。

状態ビットがＯに等しいと決定されると、自バスコード
が現れたことになる。この白バスコードの位置は、アラ
イメントの累乗を計算する目的と、いくつかのアライメ
ント角度の両端を掃引する次に説明する転換工程のため
に保持しなけらばならない。この工程は、第２図のデー
タメモリ５８の選択されたポイントデータ記憶場所７２
で行われる。

白バスコードの記憶場所の保持は１２４で行われる。

次いで、Ｘが設定され、前述したように状態ビットがイ
ンクリメントされ、ライン端とページ端がチエツクされ
る。

第６図に戻り、この説明はライン端が達したと仮定して
続けられる。もしそのような場合、累乗は参照番号１２
６で示した部所で異なるアライメント角度を有、する複
数のアライメントにつき決定しなければならない。まず
最初にアライメント角度が１２８にて０に設定される。

このアライメントはその画像が走査されたアライメント
に対応している。このアライメント角度につきアライメ
ントの累乗が概して上述したようにして計算される。こ
の場合、一つのコールがデータメモリ５８の記憶場所７
２でなされ、そこに記憶されたＸ値の数値が各ラインに
つき決定される。この様子が各ラインごとのビンのサイ
ズを表している。各ラインにおけるＸ値の数の２乗か、
１３０て配列に累計され、現在のアライメント角度での
アライメントの累乗が表される。２乗の配列が、１３２
て、現在のアライメント角度と共に、データメモリ５８
の一部に記憶される。

次いで、アライメント角度が１３４にて例えば１度のよ
うな選択された大きさだけインクリメントされる。アラ
イメントの累乗は、アライメント角度の範囲内のアライ
メントにつき決定される。アライメント角度の範囲の選
択は、たとえばアライメント角度の予想される範囲、ア
ライメントの予想される強さ、アライメントの予想され
る数等の多数の要素に依存している。アライメント角度
の値が大きくなればなるほど、任意の角度の増大のため
の計算時間が長くなる。いずれにしても、スキュー角度
の範囲の一例は−４０から＋４０度となる。

したがって、−度インクリメントされると現在のアライ
メント角度か、選択された範囲外にあるかとうかを決定
するテストをする必要がある。これが１３６で行われる
。現在のアライメント角度が選択された範囲外になけれ
ば、白バスコードの位置が１３８で翻訳される。翻訳の
いくつかの方法として、バスコードの記憶場所の有無、
その適用可能性が使用された座標系に依存しているか、
メモリの大きさが利用可能か、要求されている計算速度
か等々がある。−例を挙げると、 Ｘ、　　：ＸＣＯ５α　−ｙＳｉｎ　　Ｃ１ｙ１＝ＸＳ
ｌｎα−ｙＣＯ８α 現在のアライメント角度が選択範囲外にある場合には、
次いで、前もって格納された種々のアライメントの累乗
と比較されることにより最大出力が決定される。この最
大累乗は、次いで、種々の形式で、たとえば、絶対角度
、それらの累乗を伴った角度のスペクトルで１４２に出
力される。出力の形式は、前述したように結果の使用意
図に依存する。以下、本発明の特定の例について説明す
る。

例 第８図に示されているのは、本発明の方法をテストする
ために使用されたサンプルテキストである。ビンサイズ
は、ディジタル画像（すなわち、画像の幅を横切って垂
直位置にｌピクセル分だけ相違して）における最小検知
可能スキューを反映して、二つのピクセルに設定される
。同じ理由により、角度増分サイズは、このスレショル
ド以下にスキュー角度を分解するための試みがなされな
いように、制限される。アライメントは、＋／−８０度
の範囲にわたって測定される。

第８図のサンプルのスキューしたテキストのための白バ
スコード位置が第９図に示されている。

これらの白バスコードは、種々の回転アライメントを計
算するために使用される。第１Ｏ図は、第８図のこれら
の自パス基準用のアライメント関係の関数としての累乗
を示す。スキュー角度は、角度が水平の０度指示から相
違する累乗ピークに比例しているので、第１Ｏ図のプロ
ットから図式的に決定される。

第１０図の三つの破線で示された円弧に注目する。

最も内側の円弧は、基準点が整列されなかった場合に予
測される累乗レベルを示す。次の円弧は、８０度にわた
って走査した場合の平均累乗レベルを示す。最も外側の
円弧は、ピーク累乗レベルを示す。これらの円弧は、累
乗計算アルゴリズムにより決定されるように、ピーク累
乗の統計的な特徴を表している。

ベアードのようなアライメント方法が、画像の圧縮され
た表現であるグループ４の白バスの位置に対応している
基準点に適用された場合、基礎になる画像においてスキ
ュー角度を決定する効率的で正確な手段が得られる。

テスト ＣＣＩＴＴテストデータによる本システムのテストによ
れば、本発明は、殆どの場合にスキュー角度検出特性に
おいて顕著な改善を示している。

幾つかのＣＣＩＴＴテストファイル（ＣＣ１からＣＣ８
）は、付ｍｌに示されており、ベアードの方法と本方法
との間のスキュー角度検出特性の比較が、第１表に示さ
れている。各個においては、両方のスキュー角度検出ア
ルゴリズムは生のビットマツプに適用され、仮想のスキ
ューしていない画像におけるアルゴリズムにより検出さ
れたスキューの量を決定する。次いて、ビットマツプは
、ディジタル的に、−３，０度から＋５．０度まで回転
され、スキュー角度決定が再度実行される。

第１表 上記テストの注目すべき結果は、テキストであれ非テキ
ストであれ、マークを分類するステップが取り除かれる
ことである。実際、本発明によれば、主に非テキスト的
であるＣＣ２のような画像に対して非常に適切で正確な
結果が得られる。この結果は、スキュー角度が決定され
ている構造に明白に結びついている基準点から出る高い
スキュー角度において特に重要である。

ハーフトーン領域はグループ４勧告の非圧縮モードを使
用してエンコードされるべきであり、また、バスコード
の使用に関わりがないので、非直交スクリーン角度での
ハーフトーンの存在は、本発明のアルゴリズムの特性を
劣化させることがない。それにも拘わらず、本技術にお
けるノ）−フトーン材料の存在の効果は未だテストされ
たことがない。

累乗分布の形状の特徴記述は、ページ画像における単純
なスキュー角度の支配に関して有効な一般化を導くこと
ができる。第１１図を参照すれば、多重井戸で規定され
たピークは、ソース画像における多重井戸で表されたア
ライメントの指示である。このような多重アライメント
を決定する方法は、単一のアライメントを有する画像の
スキューを決定する方法から実質的に相違がない。

本発明は、全ページ画像にわたる主要なスキュー角度に
関して一般化するように設計されている。

しかし、多重スキュー角度は、広告コピーや不適正に糊
つけされた加工品において生じ得る。このような場合、
依然この技術は全画像について一般化することができ、
この−膜化は、画像の特徴記述において有用であったり
そうでなかったりする。

相対的なスキュー角度が、広告コピーにおけるように大
きなところでは、ページ画像に対する単一スキュー角度
特性の指定は意味がないけれども、糊つけエラーの場合
には、単一スキュー角度決定は、単なる単純な利用可能
な手段と同様に、画像を表すのには十分である。

このように、本発明は、スキュー角度を決定する目的の
ために、画像の特徴、特に地形的な特徴を、位置決めし
、選択して利用するための方法を開示している。本発明
は、従来技術で詳細に述べられた方法よりもずっと計算
が簡単になる。本発明はまた、安価なデータ圧縮パッケ
ージの広い範囲の利用及びこれらのパッケージを一つの
システムに統合する簡単さの点で有利である。

一般に、本発明に関連する当業者にとって、本発明の構
造上の種々の変更、種々に異なった実施態様及び応用が
、本発明の精神及び範囲から離れることなくなしつる。

このように、ここでの開示及び記述は、例を挙げて説明
されたが、これに限定する意図はないものである。

【図面の簡単な説明】

第１Ａ図は、従来技術の一つの方法によるスキューして
いない画像上の基準点の位置を示す。 第１Ｂ図は、前記従来技術の方法によるスキューした画
像上の基準点の位置を、整列していないビンへの基準点
の分布のプロットとともに示す。 第１Ｃ図は、第１Ｂ図に示される同じスキューした画像
上の基準点の位置を、整列したビンへの基準点の分布の
プロットとともに示す。 第２図は、本発明のスキュー角度決定方法による動作が
可能なコンピュータシステムの一部を示す。 第３Ａ図から第３Ｃ図は、ＣＣＩＴＴグループ４圧縮規
格の三つのエンコードモードを示す。 第４Ａ図及び第４Ｂ図は、それぞれスキューしていない
及びスキューしたテキストでのＣＣＩＴＴグループ４圧
縮規格のバスコードに基づいた基準点の位置を示す。 第５Ａ図及び第５Ｂ図は、それぞれスキューしていない
及びスキューしたテキストでのＣＣＩＴＴグループ４圧
縮規格のバスコードからの白バスコードに基づいた基準
点の位置を示す。 第６図は、本発明の一つの観点の流れ図を示す。 第７図は、本発明の他の観点の流れ図を示す。 第８図は、本発明の一つの観点の例として使用されたス
キューしたテキストの一部を示す。 第９図は、本発明によるアライメント決定に使用された
第８図のサンプルテキストに対応した白バスコードの位
置を示す。 第１０図は、第８図のサンプルのスキューしたテキスト
に対応したアライメントの累乗のプロットを示す。 第１１図は、多重スキュー角度を有するテキストに対応
したアライメントの累乗のプロットを示す。 ５０：コンピュータシステム

Claims (1)

1. 【特許請求の範囲】 １、スキュー角度が一連のアライメントの選択された一
   つに対応する角度として決定され、各アライメントが選
   択に基づいた関連する累乗を有し、各アライメントの累
   乗がそのアライメント毎に選択された特徴のライン当た
   りのカウントから計算され、画像データがピクセルカラ
   ー変化のポイントの表示を含んでいる、画像のスキュー
   角度を決定する方法であって、 ピクセルカラー変化の前記ポイントの選択されたポイン
   トを前記選択された特徴として選択する工程と； アライメントを選択する工程と； 前記アライメント毎にピクセルカラー変化の前記選択さ
   れたポイントの位置を決定する工程ピクセルカラー変化
   の前記選択されたポイントの位置から前記アライメント
   の累乗を計算する工程と； を含む方法。