JPH0157830B2

JPH0157830B2 -

Info

Publication number: JPH0157830B2
Application number: JP59130040A
Authority: JP
Inventors: Tadashi Iwase; Takashi Suga; Hiroyuki Myata
Original assignee: Agency of Industrial Science and Technology
Current assignee: National Institute of Advanced Industrial Science and Technology AIST
Priority date: 1984-06-26
Filing date: 1984-06-26
Publication date: 1989-12-07
Also published as: JPS619763A

Description

【発明の詳細な説明】〔発明の技術分野〕この発明は、デイジタル画像処理を行う画像処
理方式に関するものである。

〔従来技術〕

従来、この種の画像処理方式において、デイジ
タル画像に対してアフイン変換を施す処理では、
アフイン変換をＡ、デイジタル画像の格子点の座
標値をＰ、座標値ｑに対応する変換前及び変換後
の画素値をそれぞれｄ（ｑ）及びd′（ｑ）とする
と、 d′（ｑ）←ｄ｛ｆ（A^-1P）｝ ……(1) と記述することができる。ただし、矢印は、矢印
の左辺に矢印の右辺を代入することを示し、A^-1
はＡの逆変換を示し、ｆ（ｑ）はｑに対して四拾
五入や切り拾てなどのデイジタル化操作を施した
結果を示す。また、実際の画像処理においては、
処理の対象となる画像の座標値の上限及び下限が
存在する。ｘ及びｙ座標の上限及び下限をそれぞ
れx_nax，x_nio，y_nax，y_nioとし、座標値ｑのｘ及び
ｙ座標をそれぞれqx，qyとすると、上記ｄ（ｑ）
は、下記(2)式の条件を満足する必要がある。

x_nio≦qx≦x_nax y_nio≦qy≦y_nax ……(2) したがつて、上記(2)式の条件が成立しない場合
は定義されないので、値が定義されないことを示
す特殊な値（例えば０）であると定義することが
できる。

さて、従来の画像処理方式においては、上記(1)
式に示す処理を画像の全格子点に対して遂次的に
行つていた。第１図は従来の画像処理方式の一例
を示すフローチヤート図である。第１図において
は、説明を簡単にするために、x_nio＝y_nio＝０，
x_nax＝y_nax＝Ｎ−１，ｘ，ｙのきざみを１として
いる。図に示す様に、Ｓ１及びＳ２では格子点を
表わす変数であるｘ及びｙに初期値０を代入して
いる。Ｓ３では、ｘ及びｙにアフイン変換を定め
る行列Ａの逆行列A^-1を乗ずることにより、ｘ及
びｙで指定される格子点が保持するデータｄ（ｘ，
ｙ）を格納すべき格子点の座標であるｘ１及びｙ
１を求めている。Ｓ４及びＳ５ではｘ１及びｙ１
が座標値の上限及び下限である０とＮ―１の間に
あるか否かを判定している。判定の結果が真であ
れば、Ｓ６においてｄ（ｘ，ｙ）をｄ（ｘ１，ｙ
１）に代入し、偽りであれば、Ｓ７において未定
義値を示す値である０をｄ（ｘ１，ｙ１）に代入
する。Ｓ８では、次の格子点に対する処理を行う
ために、ｙを１だけ増している。Ｓ９では、ｙが
上限Ｎ―１を超えたか否かを判定し、超えていな
ければＳ３にもどる。超えていれば、Ｓ１０にお
いてｘを１だけ増し、Ｓ１１においてｘが上限Ｎ
―１を超えたか否かを判定する。ｘが上限Ｎ―１
を超えていなければＳ２にもどり、超えていれば
処理を終了する。以上の説明から明らかな様に、
Ｓ３，Ｓ４，Ｓ８及びＳ９の各ステツプはN²回
だけ実行される。また、Ｓ４で真又は偽りである
と判定される回数をk₄t及びk₄f，Ｓ５で真又は偽
りであると判定される回数をk₅t及びk₅fとする
と、Ｓ５，Ｓ６及びＳ７が実行される回数k₅，k₆
及びk₇に対して以下に示す関係式が成り立つ。

｛k₅＝k₄t＝N²−k₄f k₆＝k₅t＝N²−k₄f−k₅f k₇＝k₄f＋k₅f｝したがつて、k₅，k₆，k₇の総和は、 k₅＋k₆＋k₇＝2N²−k₄f≧N² となる。それゆえ、第１図に示す様な画像処理に
は、格子点の総数、すなわちN²に比例した処理
時間を消費することが明らかであり、高速なアフ
イン変換を実行し得ないという欠点があつた。

〔発明の概要〕

この発明は、上記の様な従来のものの欠点を改
善する目的でなされたもので、２次元座標平面上
の格子点に対応する単位プロセツサ群から成るプ
ロセツサ・アレイを用いて、このプロセツサ・ア
レイの各単位プロセツサが、該当単位プロセツサ
に対応する格子点の原座標にアフイン変換の逆変
換を施して目的座標を得て、この目的座標に対応
する単位プロセツサに原座標を転送し、この原座
標を受け取つた目的座標に対応する単位プロセツ
サが、その画素値を原座標に対応する単位プロセ
ツサに転送する処理を、各格子点ごとに並列に行
うことにより、高速なアフイン変換の処理を実現
できる様にした画像処理方式を提供するものであ
る。

〔発明の実施例〕

以下、この発明の実施例を図について説明す
る。第２図はこの発明の一実施例である画像処理
方式を示すブロツク構成図である。図において、
１は単位プロセツサであり、デイジタル画像の格
子点に対応して、Ｎ×Ｎ個配置されている。な
お、図中の左下の単位プロセツサ１がｘ＝x_nio，
ｙ＝y_nioに、右上の単位プロセツサ１がｘ＝x_nax，
ｙ＝y_naxにそれぞれ対応する。２と３は各単位プ
ロセツサ１間を接続する信号線であり、それぞれ
ｘ及びｙ方向に隣接する単位プロセツサ１を接続
している。また、ｘ及びｙ座標の上限及び下限に
相当する単位プロセツサ１も、各信号線２又は３
を介して相互に接続されている。４は制御プロセ
ツサであり、単位プロセツサ１の集合から成るプ
ロセツサ・アレイにデータを入力したり、プロセ
ツサ・アレイからデータを受け取ることができる
ものである。制御プロセツサ４からデータをプロ
セツサ・アレイに入力する場合は、信号線５及び
セレクタ６を介してｘ＝x_nio，ｙ＝y_nioに相当す
る単位プロセツサ１にデータを入力する。セレク
タ６は、ｘ＝x_nax，ｙ＝y_naxに相当する単位プロ
セツサ１から信号線２を介して送られるデータ
と、制御プロセツサ４から信号線５を介して送ら
れるデータを、制御プロセツサ４から供給される
信号線７によつて選択される。なお、制御プロセ
ツサ４とセレクタ６の構成は、この発明には直接
的な関係を持たないので、その詳細な説明は省略
する。

第３図は、第２図の画像処理方式において、各
単位プロセツサ間を接続する信号線の構成を示す
図で、第２図と同一符号は同一、又は相当の構成
要素であるので、その説明は省略する。また、信
号の伝播方向は、各信号線に対して図の矢印の方
向で示してある。図において、２ａ及び３ａはデ
ータを転送する信号線であり、ｘ及びｙ座標の小
さい単位プロセツサ１から大きい単位プロセツサ
１にデータが転送される。また、ｘ＝x_nio，ｙ＝
y_nioの単位プロセツサ１及びｘ＝x_nax，ｙ＝y_nax
の単位プロセツサ１は、前述した様に、制御プロ
セツサ４との間でデータの転送を行うことができ
る。この様に各信号線２ａ及び３ａを介して転送
されるデータには、デイジタル画像の画素値，座
標値，アフイン変換を定める行列，単位プロセツ
サ１に与える命令及び制御情報等がある。２ｂ及
び３ｂはデータの転送を要求する１ビツトの信号
線（REQX及びREQYという）であり、信号線
の値が「１」の時、ｘ及びｙ座標の小さい単位プ
ロセツサ１から大きい単位プロセツサ１へデータ
が転送される。２ｃ及び３ｃはデータの転送を許
可する１ビツトの信号線（RPLYX及びRPLYY
という）であり、ｘ及びｙ座標の大きい単位プロ
セツサ１から小さい単位プロセツサ１へデータが
転送される。各RPLYX２ｃ及びRPLYY３ｃが
「１」の時、各REQX２ｂ及びREQY３ｂをそれ
ぞれ「１」にすることができる。２ｄ及び３１ｄ
は、その値が「１」の時、処理が完了したことを
示す１ビツトの信号線（CMPLX及びCMPLYと
いう）であり、ｘ及びｙ座標の小さい単位プロセ
ツサ１から大きい単位プロセツサ１へデータが転
送される。制御プロセツサ４は、ｘ＝x_nax，ｙ＝
y_naxに相当する単位プロセツサ１のCMPLX２ｄ
を受け取ることにより、プロセツサ・アレイ全体
の処理の完了を知ることができる。

第４図ａ及びｂは、それぞれ第２図の画像処理
方式において、信号線２ａ及び３ａを介して転送
されるデータの一般的な形式を示す図、及び各デ
ータの種類とその内容を示す図である。第４図ａ
において、８はデータの種類を示す部分（TAG
という）であり、９はデータの値を示す部分
（BODYという）である。第４図ｂに示す様に、
TAG８が「MTX」という値の時、BODY９は
アフイン変換を定める行列の値であり、この場合
のデータはすべての単位プロセツサ１に伝達され
る。TAG８が「PRD」という値の時、BODY９
は単位プロセツサ１の座標（原座標という）にア
フイン変換の逆変換を施した座標（目的座標とい
う）であり、この場合のデータは隣接した単位プ
ロセツサ１に伝達される。TAG８が「FWD」と
いう値の時、BODY９は目的座標及び原座標で
あり、この場合のデータは目的座標に相当する単
位プロセツサ１に送られる。TAG８が「BWD」
という値の時、BODY９は原座標及び目的座標
の画素値であり、この場合のデータは原座標に相
当する単位プロセツサ１に送られる。TAG８が
「CMP」という値の時、BODY９は目的座標の画
素値であり、この場合のデータは原座標に相当す
る単位プロセツサ１に送られる。

第５図は、第２図の画像処理方式において、１
つの単位プロセツサの内部構成の一例を示すブロ
ツク構成図で、第２図及び第３図と同一符号は同
一、又は相当の構成要素であるので、その説明は
省略する。図において、１０ａ及び１０ｂは各信
号線２ａ及び３ａを介して隣接する単位プロセツ
サ１から転送されたデータを格納するレジスタ
（IBX及びIBYという）である。１１ａ及び１１
ｂは各信号線２ａ及び３ａを介して隣接する単位
プロセツサ１へ転送すべきデータを格納するレジ
スタ（OBX及びOBYという）である。１２は原
座標を格納するレジスタ（Ｐという）である。１
３はアフイン変換を施す前の単位プロセツサ１の
座標の画素値を格納するレジスタ（DSという）
である。１４はアフイン変換を施した後の単位プ
ロセツサ１の座標の画素値を格納するレジスタ
（DDという）である。１５はデータの転送を制
御するスイツチ回路（SWという）であり、この
SW１５は各IBX１０ａ，IBY１０ｂ，OBX１１
ａ，OBY１１ｂ，Ｐ１２，DS１３及びDD１４
との間で、各信号線１６ａ，１６ｂ，１７ａ，１
７ｂ及び１８〜２０を介してデータを転送する。
２１は単位プロセツサ１の動作を制御する回路
（CNTという）であり、このCNT２１は各信号
線２ｂ〜２ｄ及び３ｂ〜３ｄを介した各単位プロ
セツサ１間のデータの転送の制御と、各IBX１０
ａ，IBY１０ｂ，OBX１１ａ，OBY１１ｂ，Ｐ
１２，DS１３，DD１４及びSW１５の構成要素
の制御を行う。なお、説明を簡単にするため、
CNT２１と各IBX１０ａ，IBY１０ｂ，OBX１
１ａ，OBY１１ｂ，Ｐ１２，DS１３，DD１４
及びSW１５の間の制御用信号線は省略してあ
る。

次に、上記したこの発明の一実施例である画像
処理方式の動作について説明する。この画像処理
方式による全体の処理は、以下に示す方式で行わ
れる。

ステツプＡ１：制御プロセツサ４からTAG８
が「MTX」のデータを入力する。このデータは
順次にすべての単位プロセツサ１に伝達される。

ステツプＡ２：各単位プロセツサ１は
「MTX」のデータと単位プロセツサ１の原座標
から目的座標を計算する。

ステツプＡ３：ステツプＡ２で計算した目的座
標がｘ又はｙ座標の上限又は下限を超えた単位プ
ロセツサ１はステツプＡ７に行く。

ステツプＡ４：ステツプＡ２で計算した目的座
標にTAG８の「PRD」を付して、隣接する単位
プロセツサ１に転送する。

ステツプＡ５：ステツプＡ４で転送された目的
座標と単位プロセツサ１自身の目的座標が一致し
た単位プロセツサ１は、ステツプＡ７に行く。

ステツプＡ６：目的座標と原座標にTAG８の
「FWD」を付して送出する。

ステツプＡ７：「FWD」のデータを順次に目的
座標に相当する単位プロセツサ１に転送する。

ステツプＡ８：「FWD」のデータの目的座標と
単位プロセツサ１自身の座標が一致した単位プロ
セツサ１は、「FWD」のデータの原座標と単位プ
ロセツサ１が保持している画素値に、TAG８の
「BWD」を付して送出する。

ステツプＡ９：「BWD」のデータを順次に原
座標に相当する単位プロセツサ１に転送する。

ステツプＡ１０：「BWD」のデータの原座標
と単位プロセツサ１自身の原座標が一致した単位
プロセツサ１は、「BWD」のデータの画素値を
取り込む。また、画素値にTAG８の「CMP」を
付して隣接する単位プロセツサ１に転送する。

ステツプＡ１１：「CMP」のデータを受け取つ
た単位プロセツサ１が、ステツプＡ５の条件を満
たした単位プロセツサ１であれば、「CMP」のデ
ータの画素値を取り込み、隣接する単位プロセツ
サ１に送出する。

ステツプＡ１２：各ステツプＡ３，ステツプＡ
１０又はステツプＡ１１の条件を満たした単位プ
ロセツサ１は、隣接する単位プロセツサ１から転
送される各CMPLX２ｄ及びCMPLY３ｄの値が
共に「１」であれば、各CMPLX２ｄ及び
CMPLY３ｄを「１」にして送出する。

ステツプＡ１３：ｘ＝x_nax，ｙ＝y_naxの単位プ
ロセツサ１から送出されるCMPLX２ｄが、「１」
になつたことを制御プロセツサ４が検知して処理
の完了を知る。なお、上述した処理の内、各プロ
セツサＡ４，Ａ５，Ａ１０及びＡ１１は、デイジ
タル化の影響によつて多くの単位プロセツサ１が
同一の目的座標を有した場合に発生する。これ
は、目的座標に相当する単位プロセツサ１の周辺
でのデータの混雑を避けるための処理である。ま
た、上述した処理は各単位プロセツサ１において
並列に実行される。

次に、各単位プロセツサ１におけるデータの転
送の方式を説明する。説明を簡単にするために、
データは信号線２ａを経由してｘ方向から転送さ
れるものとする。また、データのTAG８は
「FWD」であり、データの目的座標は単位プロセ
ツサ１の座標と一致しないものとする。データの
転送は以下に示す方式で行われる。

ステツプＢ１：隣接する単位プロセツサ１から
の信号線２ａにデータがセツトされ、REQX２
ｂが「１」にセツトされる。

ステツプＢ２：データをIBX１０ａにセツトす
る。

ステツプＢ３：データの目的座標のｘ成分が単
位プロセツサ１の座標のｘ成分に一致する場合
は、ステツプＢ６に行く。

ステツプＢ４：隣接する単位プロセツサ１から
のRPLYX２ｃが「１」であれば、データを
OBX１１ａにセツトし、REQX２ｂを「１」に
セツトする。また、RPLYX2cを「１」にセツト
して転送を終了する。

ステツプＢ５：隣接する単位プロセツサ１から
のRPLYX２ｃが「０」であれば、RPLYX２ｃ
を「０」にセツトしてステツプＢ４にもどる。

ステツプＢ６：RPLYY３ｃとREQY３ｂ及び
OBY１１ｂについて、各ステツプＢ４及びＢ５
の処理を行う。

次に、上述したステツプＡ１〜Ａ１３の処理
を、各単位プロセツサ１がどの様に行うかを説明
する。各単位プロセツサ１は、以下に示す８つの
状態を取ることができる。

ステート１：初期状態に「MTX」のデータが
入力されると、それにしたがつて、目的座標を計
算する。その結果がｘ又はｙ座標の上限又は下限
を超えた場合は、DD１４に適当な値（例えば
「０」）をセツトし、ステート８に行く。そうでな
ければ、目的座標にTAG８の「PRD」を付し
て、ｘ及びｙ方向の隣接する単位プロセツサ１に
出力する。単位プロセツサ１の座標がｘ＝x_nio又
はｙ＝y_nioであれば、ステート３へ、そうでなけ
ればステート２へそれぞれ行く。

ステート２：ｘ又はｙ方向の隣接する単位プロ
セツサ１から「PRD」のデータが入力されると、
その目的座標と単位プロセツサ１の目的座標を比
較する。ｘ方向から入力された目的座標と単位プ
ロセツサ１の目的座標が一致すればステート５
へ、ｙ方向から入力された目的座標と単位プロセ
ツサ１の目的座標が一致すればステート６へ、そ
うでなければステータ３へそれぞれ行く。

ステータ３：単位プロセツサ１の目的座標と原
座標にTAG８の「FWD」を付して出力し、ステ
ート４へ行く。

ステート４：「BWD」のデータが入力され、
その目的座標と単位プロセツサ１の原座標が一致
すれば、その画素値をDD１４にセツトし、ステ
ート７に行く。

ステート５：ｘ方向の単位プロセツサ１から
「CMP」のデータが入力されると、その画素値を
DD１４にセツトし、ステート７に行く。

ステート６：ｙ方向の単位プロセツサ１から
「CMP」のデータが入力されると、その画素値を
DD１４にセツトし、ステート７に行く。

ステート７：DD１４の値にTAG８の「CMP」
を付して出力し、ステート８に行く。

ステート８：CMPLX２ｄ及びCMPLY３ｄか
ら「１」が入力されると、CMPLX２ｄ及び
CMPLY３ｄに「１」を出力する。

なお、上記したいずれの状態においても、
「FWD」又は「BWD」のデータが入力され、そ
の目的座標と単位プロセツサ１の原座標が一致し
なければ、上述したステツプＢ１〜Ｂ６にしたが
つてそのデータを転送する。また、「FWD」のデ
ータが入力され、その目的座標と単位プロセツサ
１の原座標が一致すれば、「FWD」のデータの原
座標と、DS１３に保持している画素値に、TAG
８の「BWD」を付して出力する。

上述した様に、この発明による画像処理方式に
したがえば、上記ステート３において「FWD」
のデータが出力され、そのデータが目的座標に相
当する単位プロセツサ１を経由して、再び原座標
に相当する単位プロセツサ１に到達するまでに経
由する単位プロセツサ１の数は、たかだか２×Ｎ
個である。また、「MTX」のデータの転送及び
CMPLX２ｄ及びCMPLY３ｄを用いた処理完了
の検出のために経由する単位プロセツサ１の数は
Ｎ個である。したがつて、データの転送の過程に
おいて、各信号線２ａ及び３ａを同時に複数のデ
ータが共有し様とした場合に発生する待ち時間を
除外すれば、アフイン変換の処理時間はＮに比例
したものとなる。そして、この発明による画像処
理方式においては、上述の様に多数の単位プロセ
ツサ１が同一の目的座標を有した場合に、実際
に、「FWD」のデータを出力する単位プロセツサ
１の数を減少させる処理方式を採用している。し
たがつて、各信号線２ａ及び３ａの共有による待
ちの発生の可能性が大幅に削除されるために、Ｎ
に比例した処理時間に非常に近い処理時間でアフ
イン変換を行うことができる。

なお、上記実施例においては、特定の装置構成
例について説明したが、この発明では、上記した
装置構成例には限定されるものではないことは云
うまでもない。

〔発明の効果〕

この発明は以上説明した様に、画像処理方式に
おいて、２次元座標平面上の格子点に対応する単
位プロセツサ群から成るプロセツサ・アレイを用
いて、このプロセツサ・アレイの各単位プロセツ
サが、該当単位プロセツサに対応する格子点の原
座標にアフイン変換の逆変換を施して目的座標を
得て、この目的座標に対応する単位プロセツサに
原座標を転送し、この原座標を受け取つた目的座
標に対応する単位プロセツサが、その画素値を原
座標に対応する単位プロセツサに転送する処理
を、各格子点ごとに並列に行う様にしたので、こ
の種の従来例のものと比べて、画像処理における
アフイン変換を極めて高速に行うことができると
いう優れた効果を奏するものである。

【図面の簡単な説明】

第１図は従来の画像処理方式の一例を示すフロ
ーチヤート図、第２図はこの発明の一実施例であ
る画像処理方式を示すブロツク構成図、第３図
は、第２図の画像処理方式において、各単位プロ
セツサ間を接続する信号線の構成を示す図、第４
図ａ及びｂは、それぞれ第２図の画像処理方式に
おいて、信号線を介して転送されるデータの一般
的な形式を示す図、第５図は、第２図の画像処理
方式において、１つの単位プロセツサの内部構成
の一例を示すブロツク構成図である。図において、１……単位プロセツサ、２，２ａ
〜２ｄ，３，３ａ〜３ｄ，５，７，１６ａ，１６
ｂ，１７ａ，１７ｂ，１８〜２０……信号線、４
……制御プロセツサ、６……セレクタ、８……デ
ータの種類を示す部分（TAG）、９……データの
値を示す部す部分（BODY）、１０ａ，１０ｂ，
１１ａ，１１ｂ，１２〜１４……レジスタ、１５
……スイツチ回路（SW）、２１……単位プロセ
ツサ１の動作を制御する回路（CNT）である。
なお、各図中、同一符号は同一、又は相当部分を
示す。

Claims

【特許請求の範囲】

１２次元座標平面上の格子点にデイジタル化さ
れた画素値を対応させたデイジタル画像に対して
アフイン変換を施す処理において、この処理を、
前記２次元座標平面上の格子点に対応する単位プ
ロセツサ群から成るプロセツサ・アレイを用いて
行う手段と、前記処理において、前記プロセツ
サ・アレイの各単位プロセツサが、該当単位プロ
セツサに対応する格子点の原座標に前記アフイン
変換の逆変換を施して目的座標を得て、この目的
座標に対応する単位プロセツサに前記原座標を転
送し、この原座標を受け取つた前記目的座標に対
応する単位プロセツサが、その画素値を前記原座
標に対応する単位プロセツサに転送を行う手段
と、前記原座標及び画素値の転送を、前記各単位
プロセツサを経由して並列に行う手段とから成る
ことを特徴とする画像処理方式。