(57)【特許請求の範囲】
【請求項１】
処理装置を作動させる方法であって、
前記処理装置は算術演算を実行する処理回路を有し、前記処理回路は４桁以上の処理桁を有し、それぞれの処理桁は１ビットに対する演算を実行するためのものであり、前記処理回路は処理桁のアレイを形成するために処理桁を接続する桁接続回路を含み、
前記方法が、
前記処理回路に第１及び第２の複合オペランドを提供する段階であって、前記第１及び第２の複合オペランドはそれぞれが１ビット以上を含む２つ以上の要素データ項目を含み、それぞれの要素データ項目は前記アレイにおける処理桁のそれぞれのサブアレイに提供されるものであり、前記第１及び第２の複合オペランドの要素データ項目は一列に揃えられてフラグビット桁によって分割されるようにサブアレイ内に位置し、これによってそれぞれのサブアレイが隣接するフラグビット桁を有するようにする段階と、
前記第１及び第２の複合オペランドに対して算術演算を並列して実行するために前記処理装置を作動させる段階であって、前記算術演算は、それぞれのサブアレイにおいてそれぞれが１ビット以上を含む複数の要素データ項目を含むそれぞれの結果データ項目を取得し、かつ、サブアレイに隣接するそれぞれのフラグビット桁において前記要素データ項目についての２進出力演算の結果を表わすフラグビットを取得する段階とを含む処理装置を作動させる方法。
【発明の詳細な説明】
【０００１】
本発明は複数のデータ項目に対して演算を実行する技術に関する。
【０００２】
多くの従来技術では複数データ項目に対して演算を実行している。その幾つかの例はそれぞれのデータ項目が画像内の画素に関連し得るような画像処理の分野でみられる。
【０００３】
マホーニー（Mahoney ）のヨーロッパ特許第４６０，９７０号では画素値に適用可能な階層的データ分析技術を開示している。図７では２進化画像ジャングル（ＢＩＪ）をシミュレーションすることにより画像処理を実行するコネクション・マシン・システムを図示している。コネクション・マシン内の処理ユニットに算術および論理演算を実行させるための呼び出しをフロントエンドプロセッサ（ＦＥＰ）が行なっている。図８ではコネクション・マシン内の処理ユニットのアレイの一部が図示してあり、１つの処理ユニットが１つの画素値を保存するようになっている。
【０００４】
ブルームバーグら（Bloomberg et al.）のヨーロッパ特許第４３１，９６１号では画像の縮小拡大技術を開示している。第２ページ１８行目から第３ページ１８行目までと第５ページ５０行目から第６ページ３１行目まででビット間の論理演算を実行することにより２進化画像を縮小する方法を開示している。第３ページ３６行目から５８行目では画素ワードをシフトした後で画素ワードとシフトしたそれ自身の変形を論理的に統合することを含む非常に広範囲な画素ワードに対する演算のための技術を開示している。
【０００５】
本発明はグレースケールやカラー画素値など多ビットデータ項目を処理する上での問題を取り扱う。
【０００６】
多ビットデータ項目に対する演算は条件式であることが多い。たとえば、データ項目はこれが閾値を越えている場合には１つの方法で操作しそうでない場合には別の方法で操作することが有り得る。またはデータ項目が所定の値に等しい場合またはある範囲内に収まる場合にのみ操作することがある。つまり、本明細書で２進出力演算と称するような、データ項目が条件に合致するかを決定するための２進値を生成する演算を実行することが必要な場合が多い。
【０００７】
２進出力演算はまたその他の目的にも有用である。たとえば、条件に適合するデータ項目をデータ項目のアレイについての２進論理結果の積算により計数することが可能である。
【０００８】
従来技術はデータ項目について２進出力演算を実行するために使用可能である。たとえば、マイクロプロセッサは２つのデータ項目を比較する演算を実行してこれらが等価かを決定するまたは一方が他方を越えているかを決定することが出来る。
【０００９】
しかし従来技術において、単一の処理装置(processor) は一度に１つの多ビットデータ項目に対してのみ演算が可能である。従来は、処理装置よりそれぞれが狭い幾つかの多ビットデータ項目に対して処理装置が２進出力演算を平行に実行できない。
【００１０】
本発明は複数の多ビット要素データ項目を含む複合(composite) オペランドに対して並列に２進出力演算を実行するための技術の発見に基づいている。要素データ項目は、たとえばグレースケールまたはカラー画素値であり得る。本技術では算術演算を用いてそれぞれの要素について２進出力を表わすデータを生成する。算術演算はたとえば加算または減算が可能である。
【００１１】
本技術は処理装置を作動させて複数の多ビット要素データ項目を含む複合オペランドに対して算術演算を実行させることにより実施可能である。算術演算でそれぞれの要素についての結果データ項目が生成される。フラグビットもそれぞれの要素について得られる。それぞれのフラグビットはその要素についての２進出力を表わす。
【００１２】
図１は２進出力演算の結果を表わすフラグビットを得るためにどのように並列に算術演算を実行することが出来るかの実施例を示す概略流れ図である。
【００１３】
図２は並列に算術演算を実行することによりフラグビットを得るためソフトウェア製品からの命令を処理装置が実行し得るようなシステムの部材を表わす概略ブロック図である。
【００１４】
図３は並列に算術演算を実行することによりフラグビットを得る上での一般的動作を表わす流れ図である。
【００１５】
図４は複合データ項目と定数の比較を行なう符号フラグビットを得るために図３での動作を実施する演算を表わす流れ図である。
【００１６】
図５は２つの要素データ項目の比較を行なう符号フラグビットを得るために図３での動作を実施する演算を表わす流れ図である。
【００１７】
図６は部分抽出演算で０フラグビットを得るために図３の動作を実施する演算を表わす概略流れ図である。
【００１８】
図７は算術および論理演算で０フラグビットを得るために図３の動作を実施する演算を表わす概略流れ図である。
【００１９】
図８は範囲フラグビットを得るために図３の動作を実施する演算を表わす流れ図である。
【００２０】
図９は範囲フラグビットを得るために図３の動作を実施する演算を表わす別の流れ図である。
【００２１】
図１から図３では本発明の一般的特徴を示す。図１では複数の多ビット要素データ項目を含む複合オペランドを模式的に示す。それぞれの要素について、算術演算でその要素に対する２進出力演算の結果を表わすフラグビットを得られる。図２では図１に示したような技術にしたがって処理装置が実行可能な命令を表わす命令データを有するソフトウェア製品を示す。図３では処理装置を作動させて２進出力演算の結果を表わすフラグビットを取得する際に算術演算を実行させる方法における一般的動作を示す。
【００２２】
図１において、複合オペランド１０はそれぞれが２ビットを含む要素データ項目１２、１４、１６を含む。要素１２は値「１０」を有し、要素１４は値「０１」、また要素１６は値「００」を有する。オペランド１０において、それぞれの要素はその最上位ビットに隣接してクリアしたビットを有している。
【００２３】
定数オペランド２０は値「１１」の繰り返しよりなり、一回の反復が複合オペランド１０内のそれぞれの要素データ項目と位置が揃えてあり、その最上位ビットに隣接してクリアしたビットを有している。値「１１」を２ビット値に加算して２ビットの結果を得るのは、（２2 −１）＝３であるから、２ビット値から値「０１」を減算するのと等価である。しかし２ビットの値に「１１」を加算すると２ビット値が「０１」またはそれ以上の場合に上位側ビットから桁上げビットも生成される。
【００２４】
オペランド２０をオペランド１０に加算すると、２種類の有用な形式の結果が得られる。これはオペランド３０として図示してある。ビット３２、３４、３６はそれぞれ要素１２、１４、１６が少なくとも値「０１」と同じ大きさかどうかを表わしている。結果データ項目３８は要素１４が値「０１」に等しいことを表わす値「００」を有している。
【００２５】
つまりビット３２、３４、３６はそれぞれが要素１２、１４、１６のそれぞれ１つについての２進出力演算の結果を表わすフラグビットである。２進出力演算はそれぞれの要素を閾値「０１」と比較する。要素１２は「０１」より大きいので、ビット３２は値「１」を有する。要素１４は「０１」に等しいので、ビット３４も値「１」を有する。しかし要素１６は「０１」以下なので、ビット３６は値「０」となる。
【００２６】
結果データ項目３８は２ビットを含むため、これからフラグビットを得るにはさらなる動作を行なわなくてはならない。オペランド３０を左向きに１ビット桁だけシフトして得られたオペランド４０は結果データ項目３８と同じ値を有するシフトしたデータ項目４２を含むが、これの最下位ビットは結果データ項目３８の最上位ビットと位置が揃えてある。
【００２７】
オペランド３０とオペランド４０の論理和でオペランド５０が生成される。これのビット２２は要素１４に対する２進出力演算の結果を表わすフラグビットである。２進出力演算は要素１４を値０１と等価性の点で比較し、ビット５２の値「０」は等価であることを表わしている。同様に、ビット５４とビット５６は要素１２および１６が値「０１」とは等しくないことを表わす値「１」を有するフラグビットである。
【００２８】
図２はソフトウェア製品６０を示し、これは図２に図示したのと同様な部材を含むシステム内で使用することが出来る製造物である。ソフトウェア製品６０は保存媒体アクセス装置６４からアクセス可能なデータ保存媒体６２を含む。データ保存媒体６２はたとえば１つまたはそれ以上のフロッピーディスクの組などの磁気媒体、１つまたはそれ以上のＣＤ−ＲＯＭの組などの光学媒体、半導体メモリ、またはデータを保存するために適切な何らかのほかの媒体であってよい。
【００２９】
データ保存媒体６２は保存媒体アクセス装置６４がたとえばマイクロプロセッサなどで有り得る処理装置６６に提供可能なデータを保存する。処理装置６６は入力回路７０からデータを受信するために接続してある。データは何らかの適切な供給源、たとえばファクシミリ（ファックス）装置や、デジタル複写機のスキャナまたはコンピュータの入出力装置で有り得るようなスキャナ、キーボードとマウスまたはペン型または鉄筆型入力装置などのユーザ入力装置で制御するフォームエディタまたはその他の対話型画像エディタであり得るようなエディタ、またはデータ転送能力を有するローカルエリアネットワークまたはその他のネットワークであり得るようなネットワークなどから取得することが出来る。データは画像に関連したものであり得る。
【００３０】
処理装置６６はまた出力回路８０へデータを提供するためにも接続してある。データはこのあとファクシミリ装置、印刷装置、表示装置、またはネットワークへ提供可能である。印刷装置はデジタル複写機の印刷装置またはコンピュータの入出力装置のことがある。
【００３１】
データ保存媒体６２に加えて、ソフトウェア製品６０は保存媒体６２に保存されるデータを含む。保存されたデータは算術演算命令８０とフラグビット命令８２を表わすデータを含んでいる。処理装置６６は命令８０を実行して複合オペランド中の複数の要素データ項目のそれぞれについての結果データ項目を得ることが出来る。処理装置６６は命令８２を実行してそれぞれの要素についての２進出力演算の結果を表わすそれぞれの結果データ項目からフラグビットを得ることが出来る。
【００３２】
処理装置６６はメモリ８４にアクセスすることにより算術演算を実行する要素データ項目を取得することが出来る。それぞれのデータ項目はたとえば画像の画素に関連し得るものである。データ項目はそれぞれ１ビット以上を含むことが出来る。保存媒体６２に保存されたデータには、入力回路７０から受信したデータ項目をメモリ８４内に保存し、演算のためにメモリ８４からデータ項目を取り込み、または出力回路７２へ提供し、または演算により得られたデータ項目をメモリ８４に保存するため処理装置６６が実行しうる命令を表わすデータも含むことが可能である。
【００３３】
処理装置６６は複数の処理桁(processing position) ９２を有する処理回路９０を含む。処理装置６６は、たとえば従来のマイクロプロセッサであってもよい。それぞれの処理桁９２では１ビットについての演算を実行することが出来る。処理回路９０はアレイを構成させるように処理桁９２を対にして接続する桁接続回路９４を含む。対の１つの処理桁からの信号は桁接続回路(position connectiong circuitry)９４によって別の処理ユニットへ転送することが可能である。
【００３４】
演算を実行している複合オペランド中のそれぞれの要素データ項目は処理桁９２のそれぞれの部分行列内に存在することが出来る。処理装置６６は算術演算命令８０を実行してそれぞれの要素の部分行列内にマスクデータ項目を取得できる。処理装置はフラグビット命令８２を実行してそれぞれの結果データ項目からフラグビットを取得することが出来る。
【００３５】
図３は図２の処理回路９０などの処理回路を有する処理装置を作動させる方法における一般的動作を示す。囲み１１０の動作は複合オペランドを処理回路９０に提供するもので、それぞれの要素データ項目が処理桁９２のそれぞれの部分行列に提供される。囲み１１２の動作では処理回路９０を作動させて複合オペランドに対し並列に算術演算を実行してそれぞれの部分行列内に結果データ項目を取得している。囲み１１４の動作ではそれぞれの要素に対して要素についての２進出力演算の結果を表わすフラグビットを得ている。囲み１１２と１１４の動作は単一周期で発生し得るもので、これはフラグビットが算術演算により直接生成し得るためである。
【００３６】
図１から図３に関して上記で説明した一般的特徴は広範な部材を用いまた各種の演算を用い多様な方法で実施することが出来る。たとえば、上述の一般的特徴の幾つかは従来の処理装置を用いて実施可能であるが、その他の特徴は特別設計の処理装置を用いて実施できるものである。
【００３７】
図４から図８では１つ以上のデータ項目に対して並列に演算可能な処理ユニットに応用可能な図３に図示した一般的段階の実施を図示したものである。並列に演算するこのような多数の処理ユニットをこれらの間の桁接続回路を設けまたは設けずに使用することが出来る。
【００３８】
図４および図５は算術演算の結果の符号を表わすフラグビットを得るような図３に関連して説明した一般的動作の実施を表わしている。図４において、このようなフラグビットは要素データ項目を閾値と比較する算術演算の結果も表わしている。図５において、このようなフラグビットは２つの要素を比較する算術演算の結果も表わしている。
【００３９】
図４において、囲み１５０の動作ではデータ項目を取得する。それぞれのデータ項目は、たとえば画像の画素に関連することが有り得る。囲み１５２の動作は囲み１５０で得られた要素データ項目およびそれぞれの要素データ項目の最上位ビットに隣接するバッファビットを含む複合オペランドを構成する。要素データ項目が直前の画像処理演算から得られたものの場合、囲み１５０ですでにこの様式を有する複合オペランド内に得られる。囲み１５２の動作はまた定数値を含み複合オペランド中のそれぞれの要素データ項目に一回づつ発生する定数オペランドも取得している。定数値のそれぞれの所在は複合オペランド中のそれぞれの要素データ項目と位置が揃っておりまた同じ長さを有している。つまり、定数オペランドを複合オペランドから減算する算術演算は複合オペランド中のそれぞれの要素データ項目から閾値Ｔを減算している。定数オペランドはまた定数値のそれぞれの所在の最上位ビットに隣接してバッファビットも含んでおり、複合オペランド中のそれぞれの要素データ項目に隣接するバッファビットと位置が揃っている。
【００４０】
複合オペランドと定数オペランド中のバッファビットはこれについて実行した算術演算の結果が有用となるような値を有するはずである。たとえば、複合オペランド中のすべてのバッファビットは値「１」を有しまた定数オペランド中のすべてのバッファビットは値「０」を有して、結果を無効にすることのある要素間信号を生成することなく複合オペランドから定数オペランドを減算し得るようにしている。
【００４１】
囲み１５４の動作は複合オペランドから定数オペランドを減算しそれぞれの要素データ項目からＴが減じられるような算術演算を実行する。したがって囲み１５４の動作は少なくともＴと同じ大きさのそれぞれの要素データ項目について値「１」を有する隣接バッファビットを有する結果データ項目、またＴより小さいそれぞれの要素データ項目について借り信号の結果として値「０」を有する隣接バッファビットのある結果データ項目を生成することになる。
【００４２】
囲み１５４の動作は定数を複合オペランドに加算する算術演算に置き換えることが可能である。たとえば、Ｋビットの要素に（２K −Ｋ）を加算すると要素からＴを減算して得られた差分と同じ和が得られる。しかしこの場合、両方のオペランドのバッファビットは演算前に値「０」を有するべきである。これは、少なくともＴと同じ大きさのそれぞれの要素データ項目について桁上げ信号の結果として値「１」を有する隣接バッファビットを有する結果データ項目、またＴより小さいそれぞれの要素データ項目について値「０」を有する隣接バッファビットを有する結果データ項目を生成することになる。
【００４３】
囲み１５６の動作ではフラグビットとして囲み１５４で生成した結果データ項目に隣接するバッファビットを用いる。この動作は多数の方法で実施可能である。
【００４４】
バッファビットだけを含む結果を得るには、縮小などの部分抽出演算を結果データ項目に対して実行する。バッファビットを有するそれぞれの要素データ項目がＫビットを含む場合、（Ｋ＋１）：１の縮小を実行するかまたはlog2（Ｋ＋１）２：１の縮小を実行し、それぞれのビット対の最上位ビットにそれぞれを保存する。これによりバッファビットは要素データ項目が少なくともＴと同じ大きさだった画素に関するそれぞれのビットでは１をまた要素データ項目がＴより小さかったそれぞれのビットでは０を有するビットマップを構成することになる。
【００４５】
多ビット要素データ項目の処理をさらに制御するために使用可能な結果を得るには、バッファビットを用いてマスクを生成することが出来る。
【００４６】
図５において、囲み１７０の動作ではデータ項目の対を得ている。たとえば、２つのデータ項目の両方が画像の同じ画素に関係していることからこれらを対に出来、またはこれらの関連する画素が２枚の異なる画像に由来しているが画像処理の間に一方の画像が他方の上に重ねあわされる際に位置が揃えられていることからこれらを対にすることが出来る。
【００４７】
囲み１７２の動作は第１と第２の複合オペランドを構成しており、これらは囲み１７０で得られたそれぞれのデータ項目の対の一方を第１の複合オペランドにまた他方を第２のオペランドに分割している。それぞれの複合オペランドは要素データ項目とそれぞれの要素データ項目の最上位ビットに隣接するバッファビットを含む。要素データ項目が直前の画像処理演算から得られた場合には、この様式を有する複合オペランドに囲み１７０で受信してもよい。対の要素データ項目は相互に位置が揃えてありまた同じ長さで、第２のオペランドを第１のオペランドから減算する算術演算において第２のオペランド内のそれぞれの要素データ項目を第１のオペランド内の対になった要素データ項目から減算する。バッファビットも同様に位置が揃えてあり第１のオペランドには値「１」また第２のオペランドには値「０」を有している。図４に関して述べたように、等価な加算を実行する場合、すべてのバッファビットは値「０」を有しているべきである。
【００４８】
囲み１７４の動作では、第１のオペランドから第２のオペランドを減算する算術演算を実行して、第２のオペランド内のそれぞれの要素データ項目が第１のオペランド内の対になった要素データ項目から減算されるようにする。つまり囲み１７４の動作では、少なくとも対になった要素データ項目と同じ大きさの第１のオペランド内のそれぞれの要素データ項目について値「１」を有する隣接バッファビットを有する結果データ項目、また対になった要素データ項目より小さい第１のオペランド内のそれぞれの要素データ項目について値「０」を有する隣接バッファビットを有する結果データ項目を借り信号の結果として生成することになる。
【００４９】
囲み１７６の動作では囲み１７４で生成した結果データ項目に隣接するバッファビットをフラグビットとして用いる。この動作は図４の囲み１５６に関連して前述したように実施することが出来る。特に、要素データ項目のそれぞれの対の極大を求めるには、第１のマスクをバッファビットから生成し、第２のオペランド内の要素データ項目がこれと対になる要素データ項目と等しいかまたはこれより大きいような桁に「０」を、また第１のオペランド内の要素データ項目のほうが大きい桁では「１」をマスクが含むようにする。第１のマスクと第１のオペランドの論理積から第１のオペランドのマスク版を生成する。第１のマスクを反転させて第２のオペランドとの論理積をとる第２のマスクを生成し、第２のオペランドのマスク板を生成することが出来る。第１と第２のオペランドのマスク版の論理和によってそれぞれの桁で極大の結果を得ることが出来る。逆に、第１のマスクと第２のオペランドの論理積をとり、さらに第２のマスクと第１のオペランドの論理積をとってマスク版を生成し、これの論理和からそれぞれの桁で極小の結果を得ることが出来る。
【００５０】
図６および図７は算術演算の結果が０かどうかを示すフラグビットを取得する図３に関連して説明した一般動作の２種類の実施例を示したものである。図６ではこのフラグビットを縮小により取得し、図７ではこのようなフラグビットを並列のさらなる演算で取得している。
【００５１】
図６および図７の両方とも図４の囲み１５４の動作から得られた結果で始めることが出来る。言い換えれば、両方の実施例で、定数オペランドを複合オペランドから減算して結果を得ている。結果は要素データ項目が定数に等しい桁でのみすべて「０」の値を有しそれ以外ではすべて「１」または「１」と「０」の混ざった値を有する。隣接バッファビットは要素データ項目が少なくとも定数と同じ大きさだった場合には「１」それ以外では「０」を有する。結果は図６および図７で図示したようにフラグビットを得るために使用することが出来る。
【００５２】
図６において、オペランド１８０は結果データ項目１８２、１８４、１８６とそれぞれのバッファビット１９２、１９４、１９６を含む。図示したように、データ項目１８２は定数値をそれより大きい要素データ項目から減算して得られ、データ項目１８２で「０」に等しくない差分を表わしまたバッファビット１９２で正の結果を表わす。同様に、データ項目１８４は定数値を等しい大きさの要素データ項目から減算して得られ、データ項目１８４で「０」に等しい差分を表わしまたバッファビット１９４で正の結果を表わす。また、データ項目１８６は定数値をそれより小さい要素データ項目から減算して得られ、データ項目１８６で「０」に等しくない差分を表わしまたバッファビット１９６で負の結果を表わす。
【００５３】
バッファビットを反転させるには、ＸＯＲ（排他的論理和）演算をオペランド１８０とオペランド２００に対して行ない、ビット２０２、２０４、２０６およびバッファビットと位置の揃っているその他のすべてのビットがＡＴＡ異音を有しまたバッファビットと位置の揃っていないすべてのビットが値オフを有するようにする。つまり排他的論理和演算でオペランド２１０を生成し、データ項目２１２、２１４、２１６はそれぞれオペランド１８０のデータ項目１８２、１８４、１８６と同じ値を有するがバッファビット２２２、２２４、２２６はバッファビット１９２、１９４、１９６の逆になるようにする。
【００５４】
図６の実施例ではオペランド２１０に対して部分抽出演算を実行してオペランド２３０を得ている。部分抽出演算は、オペランド２１０を１ビット左向きにシフトした後、図１に関連して上述したようにオペランド２１０とそのシフトした版の論理和をとりさらにそれぞれの対の最上位ビットを選択する２：１縮小で結果を部分抽出してオペランド２３０を取得することを含むことが出来る。部分抽出はオペランド２３０を含むテーブルへのインデックスとしてオペランド２１０を用いて実行することも可能である。
【００５５】
ビット２３２はバッファビット２２２と要素２１２の最上位ビットの論理和で得られる。ビット２３４は要素２１２の２つの最下位ビットの論理和で得られる。ビット２３６はバッファビット２２４と要素２１４の最上位ビットの論理和で得られる。ビット２３７は要素２１４の２つの最下位ビットの論理和で得られる。ビット２３８はバッファビット２２６と要素２１６の最上位ビットの論理和で得られる。ビット２３９は要素２１６の２つの最下位ビットの論理和で得られる。
【００５６】
次に、図６の実施ではオペランド２３０に対して別の部分抽出演算を実行してオペランド２４０を得ている。ビット２４２はビット２３２と２３４の論理和、ビット２４４はビット２３６と２３７の論理和、ビット２４６はビット２３８と２３９の論理和でそれぞれ得られる。ビット２４２、２４４、２４６は結果データ項目１８４が０結果を表わしまたデータ項目１８２と１８６が「０」に等しくない結果を表わしていることを示すフラグビットである。
【００５７】
図７のオペランド２５０は図６のオペランド２１０と同一のもので、データ項目２５２、２５４、２５６とバッファビット２６２、２６４、２６６を有する。オペランド２５０はバッファビットをクリアするためのオフの値２７２とそれ以外でオンの値２７４を有するマスク２７０と第１に論理和をとる。つまりオペランド２８０はバッファビット２８２、２８４、２８６をクリアしたことになる。
【００５８】
次にオペランド２８０をクリアしたバッファビット２９２とすべての桁で「１」を含む定数値２９４を有する定数オペランド２９０に加算する。オペランド３００は結果データ項目と、図６のビット２３２、２３４、２３６とそれぞれ同じ値を有するフラグビットのバッファビット３０２、３０４、３０６を含む。これらのフラグビットを図４の囲み１５６との関連で上述したように使用することが出来る。
【００５９】
フラグビットを得るためにバッファビットからの情報は必要ではなくまたバッファビットをフラグビットとして使用しないので、図６の実施はバッファビットのない結果データ項目にも応用することが可能である。図７の実施はバッファ人からの情報を必要としないが、バッファビットをフラグビットとして使用しているので、結果データ項目がバッファビットを有していない場合、バッファビットを挿入する必要がある。
【００６０】
それぞれの結果データ値とバッファビットの和にＫビット含む場合、バッファビットフラグに対して一連の（Ｋ−１）シフトと図１に関連して前述の形式の論理和演算を行なうことにより得ることが可能となる。比較すると、図６の実施はlog2Ｋシフトと論理和演算およびlog2Ｋ部分抽出演算で実施でき、これは高速な部分抽出演算が利用可能であれば大きなＫの値に対して有利である。図７の実施はオペランド２７０と２９０が利用可能であれば図示したように２回の演算で実行できる。したがって「０」フラグビットを得る演算をどのように実施するかの選択は処理装置の能力と効率を含んだ勘案に基づいて行なうことが出来る。
【００６１】
図８および図９では、要素データ項目のそれぞれが範囲内であるかを表わす範囲フラグビットをそれぞれに取得する２種類の実施を図示する。
【００６２】
図８において、囲み３２０の動作では、図４に関連して前述の複合オペランドに対する２種類の演算を実行してそれぞれの要素データ項目について第１と第２の符号フラグビットを得ている。１つの演算では定数値（Ｔ1 ＋１）をまた他方では定数値Ｔ2 を使用する。ここでＴ2 ＞Ｔ1 である。その結果、要素の第１のフラグビットは要素が（Ｔ1 ＋１）と同じ大きさかを表わし、第２のフラグビットは要素がＴ2 と同じ大きさかを表わしている。複合オペランド中の要素の第１のフラグビットは第１のオペランド内にまた第２のフラグビットは第２のオペランド内にある。
【００６３】
囲み３２２の動作は第２のオペランドを反転させる。反転した第２のフラグビットが値「１」を有する要素はＴ2 より小さく、一方第１のフラグビットが値「１」を有する要素はＴ1 より大きい。
【００６４】
囲み３２４の動作では第１のオペランドと反転した第２のオペランドの論理積をとって、それぞれ要素がＴ1 とＴ2 の範囲内にあるかを表わす範囲フラグビットを生成する。要素の範囲フラグビットは要素が範囲内にある場合は値「１」を有しそうではない場合は値「０」を有する。
【００６５】
定数値（Ｔ1 ＋１）とＴ2 を図８の実施において用い、Ｔ1 とＴ2 で区切られた開放範囲、（Ｔ1 ＋１）と（Ｔ2 −１）で区切られた閉鎖範囲、または一端では開放し他端では閉じている範囲についての範囲フラグビットを取得することが出来る。
【００６６】
図９において、囲み３４０の動作では図４に関連して前述したように複合オペランドに対する演算を実行してそれぞれの要素データ項目に符号フラグビットを有する第１のオペランドを得ている。演算には定数値Ｔ1 を用い、これをそれぞれの要素データ項目から減算する。その結果、第１のオペランド内の要素のフラグビットは要素がＴ1 と同じ大きさかを表わす。さらに、第１のオペランド内のそれぞれの要素の結果データ項目はＴ1 で下向きにシフトした値を有し、Ｔ1 より小さかった要素は２K と（２K −Ｔ1 ）の間の値にシフトされる。
【００６７】
囲み３４２の動作では第１のオペランドに対して演算を行ない全てのバッファビットを値「１」に設定している。これは減算演算の準備である。
【００６８】
囲み３４４の動作では、図４に関連して述べたように別の演算を実行してそれぞれの要素データ項目について符号フラグビットを有する第２のオペランドを取得する。この演算は、囲み３４２で変更したように、定数値（Ｔ2 −Ｔ1 ）を第１のオペランド内のそれぞれの要素の結果データ項目から減算するものである。その結果、第２のオペランド内の要素のフラグビットはその要素がＴ1 とＴ2 の間の範囲にあるかを示す。ここでＴ2 ＞Ｔ1 である。要素が範囲内の場合、第２のオペランド中のこれの符号フラグビットは借り信号のために値「０」を有する。要素が範囲以上または以下の場合、第２のオペランド中のこれの符号フラグビットは値「１」を有する。
【００６９】
図８におけるように、図９の実施でも開放または閉鎖範囲を使用することが可能である。
【００７０】
上述の一般的実施の特徴は広範なデータ処理用途に使用可能である。しかしある種の画像処理においてはそれぞれの要素データ項目について順次実行するよりも迅速に実行しうることで特に有用であると推測される。特に、上述の特徴をセラ（Serra, J. ）の「画像分析と数学的変換（Image Analysis and Mathematical Morphology）」、アカデミックプレス刊、１９８２年、およびセラ（Serra, J. ）の「画像分析と数学的変換第２巻：理論的な進歩（Image Analysis and Mathematical Morphology, Volume 2:  Theoretical Advances ）」、アカデミックプレス刊、１９８８年、に解説されているのと同様の技術を実施するために使用することが出来る。このような技術はたとえば雑音の除去またはその他の情報を含まない特徴の除去、歪曲補正、データ符号化、自動フォーム作成または制御シート作成のための部分の抽出、印刷装置特有の補正などの文書サービスを提供するために使用することが出来る。このような文書サービスは、ファクシミリ装置および複写装置を含むデジタル複写装置において、印刷装置またはその他の画像出力装置用の画像を定義するデータを生成する装置において、スキャナまたはその他の画像入力装置から受信した画像を定義するデータについて演算するまた画像処理を行なうその他の装置において、使用することが出来る。
【００７１】
上述の特徴は広範な画像処理演算の間にグレースケールまたはカラー画素値に対してフラグビットを取得するために使用できる。
【００７２】
上述の一般的実施の特徴はまた、各種のその他の用途において、たとえば特定の特徴の組み合わせを含む画像について画像データベースの検索や、封筒の住所の走査、高速スキャナからのフォームの解釈、人工視覚、および処理に特有の印刷画像の補正および確認などにおいても有用であろう。
【００７３】
本発明は各種のその他の画像処理演算、たとえば画素の計数、グレースケールの形態変更、グレースケールの回転、エラー分散画像の生成および歪曲検出などを実行するために応用することも可能である。
【００７４】
本発明は画像に関連しないデータに使用することも可能である。本発明はたとえば有限微分解析または物理現象のシミュレーションを実行するために使用することが出来る。
【００７５】
本発明は幾つかの実施に関連して説明した。本発明は２つまたはそれ以上の実施を組合せて用いることで、または２つまたはそれ以上の実施から得られたフラグビットに対して論理演算を行なうことによって、組み合わせフラグビットを取得するために実施することも可能である。
【００７６】
本発明は複合オペランド中の要素データ項目が単一のバッファビットで分離されているような実施に関連して説明した。本発明は要素間に複数のバッファビットを有するように実施することも出来る。
【００７７】
本発明は加算と減算を用いてフラグビットを取得する実施に関連して説明した。その他の算術演算を用いてフラグビットを取得することも可能である。
【００７８】
本発明は画像に関連するデータについて演算する実施に関連して説明したが、画像に関連しないデータに対して演算を行なうために実施してもよい。
【００７９】
本発明は従来のマイクロプロセッサを用いた実施に関連して説明したが、本発明は縮小命令セット計算機（ＲＩＳＣ）チップを用いてまたはメインフレーム・コンピュータ、ミニコンピュータ、スーパーコンピュータ、または何らかのその他の計算機の処理装置を含む何らかのその他の処理装置を用いて実施してもよい。
【００８０】
本発明は処理装置とメモリを含むシステム内で使用するためのメモリからのデータに対して演算を実行するために処理装置が実行できる命令を表わすデータを含むようなソフトウェア製品に関連して説明した。システムのメモリは当然のことながらシステム内で使用する際にソフトウェア製品を含み、命令ならびにデータは一般に処理装置からアクセス可能な何らかのメモリ装置内に任意に保存することが出来る。たとえば、本発明はソフトウェア製品内にではなくメモリ内に保存された命令を表わすデータを用いて容易に実施することが可能である。
【００８１】
本発明は単純な構造の複合オペランドに関連して説明した。上述の実施例において、全ての要素データ項目はおなじ長さであり複合オペランド内部の要素は相互に関連していなくとも良い。本発明は処理装置の幅の制約内で、さらなる構造を有する複合オペランドで実施することも可能である。たとえば、複合オペランドは、他のオペランドが同じ位置にある同じ幅の要素と位置が揃っているならば、異なる幅の要素データ項目を含んでいてもよい。また、要素データ項目は２つまたはそれ以上のグループに構成され、それぞれのグループの要素が関連していてもよい。それぞれのグループの要素が同じ画素に関連している場合、それぞれの要素はそれぞれの閾値減少のための値を保持することが可能である。より一般的には、それぞれのグループ内の要素が物理的シミュレーション空間内の同じ位置に関連している場合、１つの要素がその位置での値を保持しまた別の位置がその位置での導関数を保持することが可能である。
【図面の簡単な説明】
【図１】  ２進出力演算の結果を表わすフラグビットを得るためにどのように並列に算術演算を実行することが出来るかの実施例を示す概略流れ図である。
【図２】  並列に算術演算を実行することによりフラグビットを得るためソフトウェア製品からの命令を処理装置が実行し得るようなシステムの部材を表わす概略ブロック図である。
【図３】  並列に算術演算を実行することによりフラグビットを得る上での一般的動作を表わす流れ図である。
【図４】  複合データ項目と定数の比較を行なう符号フラグビットを得るために図３での動作を実施する演算を表わす流れ図である。
【図５】  ２つの要素データ項目の比較を行なう符号フラグビットを得るために図３での動作を実施する演算を表わす流れ図である。
【図６】  部分抽出演算で０フラグビットを得るために図３の動作を実施する演算を表わす概略流れ図である。
【図７】  算術および論理演算で０フラグビットを得るために図３の動作を実施する演算を表わす概略流れ図である。
【図８】  範囲フラグビットを得るために図３の動作を実施する演算を表わす流れ図である。
【図９】  範囲フラグビットを得るために図３の動作を実施する演算を表わす別の流れ図である。
【符号の説明】
１０  複合オペランド、１２，１４，１６  要素データ項目、２０  定数オペランド、３０  オペランド、３２，３４，３６  要素、３８  結果データ項目、４０  オペランド、４２  シフトしたデータ項目、５０  オペランド、６０  ソフトウェア、６２  データ保存媒体、６６  処理装置、８０  算術演算命令、８２フラグビット命令、８４  メモリ、９０  処理回路、９２  処理桁、１８０オペランド、１８２，１８４，１８６  要素データ項目、１９０  オペランド、１９２，１９４，１９６  バッファビット、２００  オペランド、２０２，２０４，２０６  ビット、２１０  オペランド、２１２，２１４，２１６  データ項目、２２０  オペランド、２２２，２２４，２２６  バッファビット、２３０オペランド、２３２，２３４，２３６，２３７，２３８，２３９  ビット、２４０  オペランド、２４２，２４４，２４６  ビット、２５０  オペランド、２５２，２５４，２５６  データ項目、２６２，２６４，２６６  バッファビット、２７０  マスク、２８０  オペランド、２８２，２８４，２８６  バッファビット、２９０  定数オペランド、２９２  バッファビット、２９４  定数、３００オペランド、３０２，３０４，３０６  バッファビット
【図１】
0003637923.tif 000002
【図２】
0003637923.tif 000003
【図３】
0003637923.tif 000004
【図４】
0003637923.tif 000005
【図５】
0003637923.tif 000006
【図６】
0003637923.tif 000007
【図７】
0003637923.tif 000008
【図８】
0003637923.tif 000009
【図９】
0003637923.tif 000010