JPH0426151B2

JPH0426151B2 -

Info

Publication number: JPH0426151B2
Application number: JP59207239A
Authority: JP
Inventors: Kooru Mintsuaa Furederitsuku; Ruisu Andaason Karen; Rauaan Mitsucheru Joon
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1983-12-30
Filing date: 1984-10-04
Publication date: 1992-05-06
Also published as: DE3484195D1; US4569081A; EP0149120A2; JPS60146368A; EP0149120A3; EP0149120B1; CA1220581A

Description

【発明の詳細な説明】〔産業上の利用分野〕本発明はデイジタル・イメージ処理方法、更に
詳細に説明すれば、イメージの引伸し方法に関す
る。

〔従来技術〕

イメージを引伸す方法はこれまでに数多くある
が、本発明の方法は開示されたことがないばかり
か、示唆されたことすらない。

〔発明が解決しようとする問題点〕

従来のイメージ引伸し方法は手間と時間が掛り
すぎる点で不満足であつたので、本発明は２進イ
メージを高速で引伸す方法を提供することを目的
とする。

〔問題点を解決するための手段〕

本発明が解決しようとする問題点は次のステツ
プを含む方法によつて解決される：２進イメージをビツト・シーケンスで記憶し；該イメージの第１の軸に沿つたｎビツトのスト
リングごとに少なくとも１つの引伸しビツトを挿
入し、前記ｎビツトのストリングの各々を、ｎビ
ツトよりも多いｍビツトのストリングに変換し；前記引伸しビツトの各々の値を一定のアルゴリ
ズムによつて指定し；該イメージの第２の軸に沿つたｉビツトのロー
（横列row）ごとに少なくとも１つの引伸しビツ
トのローを挿入し、前記ｉビツトのローの各々
を、ｉビツトよりも多いｊビツトのローに変換
し；前記引伸しビツトの各々の値を一定のアルゴリ
ズムによつて指定し；前記ステツプによつて引伸されたイメージを記
憶する。

〔作用〕

本発明の良好な実施例では、２進イメージは、
該イメージのビツト・シーケンスを記憶し、該イメージの第１の軸に沿つた５ビツトのスト
リングごとに少なくとも１つの引伸しビツトを挿
入し、前記５ビツトのストリングの各々を６ビツ
トのストリングに変換し、前記引伸しビツトの値を一定のアルゴリズムに
よつて指定し、イメージの第２の軸に沿つた５ビツトのローご
とに少なくとも１つの引伸しビツトのローを挿入
し、前記５ビツトのローを第２の軸に沿う６ビツ
トのローに変換し、前記引伸しビツトの値を一定のアルゴリズムに
よつて指定し、前記ステツプによつて引伸されたイメージを記
憶することにより引伸される。

〔実施例〕

本発明の良好な実施例として、２進イメージを
水平、垂直両方向にそれぞれ５：６に引伸す場合
の例を説明する。イメージは、ローを左から右
へ、イメージの上部から下部へ読取つて記憶する
ものとする。引伸しは元の場所で実行することが
ある。あるいは、出力は、元のイメージの最初の
部分を含まない記憶領域に置かれることもある
（従つて出力イメージのデータを元のイメージの
データに重ね書きすることは、元のデータを使用
してからでないと出来ないことがある）。

本実施例では、前述のように、水平、垂直それ
ぞれの方向で２進イメージを５：６に引伸すこと
になつている。提案された引伸し方法は、牽引表
によつて速度で５バイト・ローを引伸すアルゴリ
ズム、および、２進イメージは一般に、０の値
（白の画素）しか含まない大きな領域を有するこ
とを利用した新しいアルゴリズムを含む斬新な手
法の組合せを用い、必要な処理量を大幅に削減す
るので、従来の方法よりもかなり速い引伸し動作
が行なわれる。

イメージを構成するビツトは、８ビツトを１バ
イトとして記憶し、各ロー（横列）およびカラム
（縦行）はバイト境界から始まるものでする。イ
メージの引伸しは元の場所で行なわれる。計算機
によるビツト操作は割高であるので、IBMシス
テム／370では、（32ビツト）ワード操作により、
１回に多くのビツトを処理する。

次に、本発明の方法の詳細について説明する。
最初に、元のイメージの各ローの５ビツトごと
に、後に１ビツトを挿入する。挿入されるビツト
の値は、周りのビツトの値の相互関係によつて決
められる。挿入されたビツトをｘ、ｘに接するビ
ツトをａ、ｂ、ｃ、ｄ、ｅ、ｆとし、これらのビ
ツトの位置関係を第２図ａに示す。この場合、空
白になつている部分のビツト（ｘの上下）はｘの
値の決定とは無関係である。新しいビツト（以
下、引伸しビツトという）ｘは次のアルゴリズム
によつて決められる： (a) 若し、ｃ＝ｄなら、ｘはｃと同じ値（１また
は０）にセツトされ、さもなければ、 (b) 若し、ａ＝ｆ＝１またはｅ＝ｂ＝１なら、ｘ
＝１にセツトされ、さもなければ、 (c) ｘ＝０にセツトされる。

ａ、ｂ、ｃ、ｄ、ｅおよびｆの値のすべての可
能な組合わせのそれぞれの場合のｘの値を第２図
ｃに示す。

水平方向の引伸しに続いて、イメージの５ロー
ごとに新しいローが挿入され、前記と同じアルゴ
リズムを用いて決められた引伸しビツトの値が書
込まれるが、ｘと周りのビツトの関係を示すビツ
ト・マスクは90度回転され、第２図ｂに示すよう
になる。

最初に挿入されたカラムとローのビツトが、出
力イメージの第３のカラムと第３のローに位置す
るビツトになるように、ビツトを挿入するカラム
とローを選択する。このような位置にビツトを挿
入して５：６に引伸し、挿入したビツトの値を決
める方法は、それぞれが６ビツトのカラムとロー
から第３のビツトと第３のローのビツトを取除い
て６：５に縮小する方法を逆にしたものに等し
い。

従つて、元のイメージを５：６に引伸してから
６：５に縮小することにより、元のイメージが復
元される。また、最初にイメージを６：５に縮小
してから、何段階かにわたつて５：６の引伸しを
行ない、その後更に６：５の縮小を行なつて最終
的に元のイメージの大きさに復元する場合、減成
（ビツト損失）は最初の縮小によつて生じるのみ
である。

次に、引伸し方法について詳細に説明する。

イメージの引伸しは、イメージ・データの最後
から始めてイメージ・データの最初に進む。引伸
しプロセスを開始する前に、元のイメージの最初
の２つのカラムを一時記憶領域にコピーする。こ
れは、イメージが元の場所で引伸された場合に、
前記データが、それが使用される前に、無効にな
らないようにするためである。若し、元のイメー
ジと引伸されたイメージとが記憶領域の同じ場所
で始まれば、引伸されたイメージの第４のカラム
（元のイメージの第３のカラムのデータを含む）
の先頭は、元のイメージの第３のカラムの末尾を
越えているので、元のイメージの第３のカラムで
始まるすべてのカラムは、記憶領域の、元のイメ
ージのカラムとオーバラツプしない場所に置かれ
る。若し、元のイメージと引伸されたイメージが
記憶領域の同じ場所で初まらないなら、両者はオ
ーバラツプしない−この場合は問題はない−か、
または入力イメージは出力イメージ以前に始ま
る。この場合も、引伸されたイメージの第４カラ
ムの先頭は元のイメージの第３カラムの末尾を過
ぎているので、最初の２つのカラムをコピーする
だけでよい。

引伸しの方法は、次の４つの基本的動作から成
る： (a) 引伸しビツトをカラムに挿入し、引伸しビツ
トのローの隣接ビツトがどちらも０の場合に
は、引伸しビツトに０の値を付与する（以下、
“ロー引伸し”という）。

(b) 引伸しビツトをセツトするのに用いる残りの
動作（以下、“カラム書込み”という）。

(c) 空白ローの挿入（以下、“ロー挿入”という） (d) 挿入されたローの書込み（以下、“ロー書込
み”という）。

ロー引伸しは、若し、水平方向の隣接ビツトが
どちらも１なら、引伸しビツトを１にセツトす
る。カラム書込みの詳細は既に説明したので省略
する（第２図参照）。イメージは２パスで処理さ
れる。第１のパスは、ロー引伸し、カラム書込
み、およびロー挿入である。第２のパスは、ロー
書込みを実行する。

第１のパスは、元のイメージの１つのローと引
伸されたイメージの３つのローで同時に動作す
る。ローを引伸す前に、出力データの最新の２つ
の引伸しローが得られる。これらのローのうちの
古い部分では、ロー引伸しとカラム書込みは終つ
ており、新しい部分のロー引伸しのみが終つてい
る。入力されたローは、新たに新伸されたローを
含む出力イメージの記憶領域を０にしてから、入
力されたローの１つの５バイト単位でロー引伸し
を同時に実行することにより引伸される。５バイ
トの入力ごとに６バイトの出力が生じる。ローを
処理するループが始まる前に、最後の（恐らく部
分的な）５バイト単位の最初のバイトが記憶領域
に保管され、非０の値だけが置換えられる。ルー
プは同時に５バイトの入力を観察する。若し、５
バイトが全０なら、対応する出力イメージ領域は
既に０になつているので、処理する必要はない。
ローの最後の単位が確実に非０データを含むよう
にすることにより、ループのその部分において明
白なロー終了検査をしなくても、ローの末尾で、
ループの、０データを処理する部分から、ループ
の出口が与えられる。

ロー引伸し動作は５バイト単位で行なわれる。
若し、５バイト単位が非０データを含むことが分
れば、最初に、ロー末尾に達したかどうかを決め
る検査が行なわれる。若し、ロー末尾に達してい
れば、ループは終了し、元のバイトは入力に復元
され、入力は引伸され、元のイメージの次のロー
のバイトが提供したデータを取除くマスクと
ANDされ、かつ、既に出力イメージにあるデー
タとORされ、次の出力ローのデータを無効にし
ないようにする。若し、ローの末尾に達していな
ければ、入力データは引伸され、それによつて生
じた６バイトは出力イメージに記憶され、ループ
は引続き動作する。

第３図は、５バイトの入力データを引伸すロー
引伸し方法を示す。データはそれぞれが10ビツト
の４単位（Ａ〜Ｄ）に分割され、牽引表により引
伸しビツトを挿入する。第３図で、データ単位を
示す枠の縦の点線はバイト境界を示し、Ａ〜Ｄは
それぞれ10ビツト単位、A′〜D′はそれぞれ12ビ
ツト単位、０は０ビツト領域を示す。

引伸しビツトは次のように配列される： XXOXXXXXOXXX ただし、Ｘは元のイメージのビツト、Ｏは引伸
しビツトである。引伸しビツトは、前述のアルゴ
リズムによつて周りのビツトの値の組合せから１
または０にセツトされる。10ビツトのグループを
レジスタに取込み、牽引表を索引するため、入力
データを、２つの（４バイト）レジスタにロード
し、一方のレジスタには入力データの第１バイト
から第４バイトまで、他方のレジスタには第２バ
イトから第５バイトまでを取り込む。レジスタで
は、データは、第３図に示すようにシフトまたは
コピーされ、それぞれの必要な10ビツト以外の他
のすべてのビツトは、それぞれのレジスタで、デ
ータとマスク000007FE（16進表示）とをANDす
ることにより０にセツトされ、Ａ〜Ｄのそれぞれ
の10ビツト単位は、１ビツト左シフトされた位置
に置かれる。入力データの各々の10ビツト単位
は、２バイトの牽引表データによつて牽引され、
その結果は、図示のように、シフトまたはORさ
れ、２回の記憶動作によつて出力を記憶装置に記
憶する。すなわち、３出力バイトA′，B′および
“０”バイトを保管した後、残りの３出力バイト
C′，D′を付加し、最終的に、48ビツトの引伸され
た出力データA′〜D′を得る。

入力ローが引伸されている間に、前に引伸され
たローはカラム書込みアルゴリズムによつて処理
される。カラム書込みは同時に３バイトずつ行な
う。３バイト単位の引伸しビツトは次の配列を有
する： XXOXXXXX OXXXXXOX XXXXOXXX ただし、“０”は引伸しビツト、Ｘは元のイメ
ージのビツトである。

このアルゴリズムによつて変更できるのは引伸
しビツトだけであるので、１つの３バイト単位と
次の３バイト単位の間で相互に影響を及ぼすこと
はない。すべての３バイト単位は同じ位置に引伸
しビツトを有する。５バイトの入力ロー（従つ
て、６バイトの出力ロー）ごとに、２つの３バイ
ト単位が処理される。若し、５入力バイトが全０
なら、前のローの変更はないはずである。その理
由は、変更は斜め方法の両ビツトが１の場合にし
かありえず、入力が全０の場合は、各斜め方向の
ビツトの１つは必ず０であるからである。従つ
て、５入力バイトが全０の場合は、入力の引伸し
を省略できるとともに、前のローの処理も省略で
きる。若し、入力が非０データを含むならば、引
伸されたデータはマスクされ、斜め方向のビツト
の中に非０のものがあるかどうかを判断する。若
し、非０のビツトがあれば、前のローのすべての
引伸しビツトは、使用可能な３出力ローからのデ
ータを用いて計算される。

カラム書込みアルゴリズムは第４図に示されて
いる。第４図で、“＊”はビツトを１桁右シフト
することを表わし、縦棒“｜”はOR、“＆”印
はAND動作は表わす。また、ロー１、ロー２お
よびロー３は、第２図ａに示したビツト配置の
“ａｂ”、“cxd”および“ｃｆ”のローにそ
れぞれ対応し、データは各レジスタの上位３バイ
トに記憶されるとともに、結果は上位３バイトし
か使用されない。カラム書込みでは、新しいロ
ー、前のローおよび前のローの直前のローのデー
タが使用される。各々のローの３バイトは、レジ
スタの上位３バイトに読込まれる。斜方向の２つ
のビツト対のそれぞれの対のビツトがANDされ、
２つのビツト対の結果はORされる。ORの結果
は、書込もうとしているローの隣接する２つのビ
ツトをORした結果とANDされ、若し、どちらか
の斜め方向の２つのビツトがともに１つで、かつ
少なくとも水平方向の隣接ビツトの１つが１な
ら、ビツトは１にセツトされる。この計算の大部
分は、データをその正規の位置から２桁右シフト
して実行される。その理由は、２つのレジスタの
内容をそれぞれ１桁シフトするよりも、１つのレ
ジスタの内容を２桁シフトする方が速い上に、命
令数が少なくて済むからである。前記ビツトは、
マスク20820800（16進表示）とANDされ、引伸し
ビツト以外の全ビツトを０にし、引伸しビツトし
か変更できないようにする。マスクした結果は、
書込もうとしているローのデータとORされてか
ら記憶される。非引伸しビツトのセツトアツプに
加えて、引伸しビツトのローの隣接ビツトはロー
引伸し動作でセツトされているので、これらの隣
接ビツトがどちらも１の場合は、OR動作により
引伸しビツトは１にセツトされる。

カラム書込み動作は、３つのローのデータを必
要とするので、処理される元のイメージの最初の
２つのロー（すなわち、イメージの最後の２つの
ロー）の処理中は、実行されない。これらの２つ
のローには、カラム書込みの省略以外は前述のル
ープに似た別個のループが使用される。カラム書
込み方法はロー引伸し方法よりもロー１つ分遅れ
て実行されるので、イメージの最初と最後のロー
では、カラム書込みは実行されず、これは、元の
イメージの前と後に０のローを置くと仮定した場
合の通常の処理と同じである。

ロー引伸し方法の第１のパスで、メイン・ルー
プは、５つのローを引伸し、次いで０のローを挿
入して書込む。ループの出口で、元のイメージの
２つのローの処理が残されるように、十分な量の
ローを処理してから、メイン・ループを開始す
る。これらのローは、コピーされていない一時記
憶領域から読込まれる。この場合、入力ローの数
が０、１、２または３の４つのケースがあり、別
個に処理される。この処理は、より大きいイメー
ジの処理に似ているが、元のデータは正しい位置
から読込まれなければならない。

第１のパスがイメージ全体を処理した後、出力
イメージに挿入された空白の水平ローは、隣接ロ
ーからのデータを用いて書込まれなければならな
い。これがロー書込み動作である。隣接ローは、
ローの最初の部分の前の１バイトから始まり、同
時に４バイトが読込まれる。各４バイトの入力
は、入力の中央の２バイトに対応する２バイトの
出力を生じ、次いで、次の入力ワードを読込むよ
うに、指標を２増加する。

若し、入力ワードの１つのローの中央の18ビツ
トが全０なら、対応する２つの出力バイトも０で
ある。というのは、縦の線（カラム）の１ビツ
ト、および中央の16ビツトの各々を通る斜め方向
の１ビツトも０であるからである。挿入されるロ
ーは、生成されたときには０であるから、処理は
必要としない。挿入されたローに書込むためのル
ープは、この事実を利用して、次のようなプロセ
スを実行する。すなわち、書込まれるローに先行
するローは、前述のように、同時に４バイト読込
まれ（書込まれるローの次のローを代りに用いる
ことがあるが、その選択は任意である）、最初の
２つの入力ワードは、レジスタに取込まれてOR
され、その結果は２番目の入力ワードと置換えら
れる。若し、ORの結果が非０なら、新しいロー
に書込まれるビツトは、（まだレジスタ内にある）
最初の入力ワードと、書込み中のローの次のロー
からのワードとを用いて計算され、ループは反復
される。若し、OR動作の結果が０なら、入力ワ
ードはどちらも０であつたことを表わし、次の６
出力バイトも０であるに違いない。追加０入力ワ
ードの各々は、さらに４つの０出力バイトを意味
する。非０入力ワードがある場合、これは16ビツ
ト右シフトし、あたかも、ループの先頭で書込ま
れたかのように、レジストに挿入され、非０入力
の処理が実行され、ループは反復する。この手順
は、（入力の中央の18ビツトが０のすべての場合
を省略しないので）不必要な計算も実行するが、
もつと慎重な検査を行なう場合よりも効率的に、
大きな空白領域を省略することが可能になる。

第５図は、３バイトの挿入ローのロー書込み動
作を実行するのに用いる手順を示す。第５図で、
ロー１、ロー２およびロー３は、第２図ｂに示し
たロー“bdf”、“ｘ”および“ace”に、それぞ
れ対応する。ｘは書込まれる引伸しビツトであ
り、“＊”印は、ビツトを１桁右シフトすること
を表わす。また、端のビツトは正しくないので、
結果は中央の２バイトしか使用しない。尚、記号
“｜”はOR、“＆”はAND動作を表わす。

実際には、16ビツトの出力を生じるのに18ビツ
トしか必要としないが、書込まれるローの前のロ
ー、および書込まれるローの次のローの両方から
32ビツトのデータが使用される。ロー引伸しの２
番目のステージのように、計算の大部分は、デー
タを、正規の位置より２桁右シフトして実行す
る。書込まれる各ビツトに隣接する斜め方向と縦
方向の３つのビツト対は、それぞれANDされ、
その結果はANDされ、これらの対の、少なくと
も１つが１の場合に、ビツトは１にセツトされ
る。この結果と、縦に隣接するビツトをORした
結果とがANDされ、縦の隣接ビツトがどちらも
０の場合には、ビツトを０にする。最終結果を含
むレジスタの中央の２バイトが記憶される。他の
２バイトは、端のビツトが必ずしも正しくはない
から使用できない。

〔発明の効果〕

本発明によつて、２進イメージを高速で引伸す
ことができる。

【図面の簡単な説明】

第１Ａ図は本発明の方法を示す概要図、第１Ｂ
図は本発明の方法に従つてイメージを引伸すプロ
セスを示す図、第２図は本発明によつて挿入され
たビツトの値を指定する方法を示す図、第３図は
本発明によるロー引伸し方法の部分の流れ図、第
４図は本発明に従つてイメージに挿入されたビツ
トの値を指定する方法の流れ図、第５図は本発明
に従つて新しいローに挿入されたビツトの値を指
定する方法の流れ図である。１００……イメージ記憶ステツプ、１１０……
第１の軸の引伸しビツトの挿入・変換ステツプ、
１３０……引伸しビツトの値指定ステツプ、１４
０……第２の軸の引伸しビツトの挿入・変換ステ
ツプ、１５０……引伸しビツトの値の指定ステツ
プ、１６０……引伸されたイメージの記憶ステツ
プ。

Claims

【特許請求の範囲】１２進イメージを引伸ばす方法であつて、 (a) 上記２進イメージをビツト・シーケンスで記
憶する段階と、 (b) 上記２進イメージのｎビツトのストリングを
ｍビツト（ｍは、ｎよりも大きい整数）のスト
リングに変換するように、上記２進イメージの
第１の軸に沿うｎビツトのストリング毎に、１
つまたはそれ以上の拡張ビツトを挿入し、その
際該拡張ビツトは、上記イメージの列を形成す
るように配置されるようにする段階と、 (c) 上記段階ｂによつて生成される各々の拡張ビ
ツトの値を、次の段階（c1）乃至（c2）に従い
割り当てる段階と、 (c1) もし、上記各拡張ビツトを跨ぐ水平方向の
隣り合うイメージ・ビツトの対がどちらも１
であるか、水平方向に隣り合うイメージ・ビ
ツトの１つが１であり、上記各拡張ビツトを
斜め方向に跨ぐ隣り合う２つのイメージ・ビ
ツトの対のどちらかがともに１であるなら値
１を上記各拡張ビツトを１にセツトし、 (c2) さもなければ、上記拡張ビツト０にセツト
する段階、 (d) 上記２進イメージの、上記第１の軸に直交す
る第２の軸に沿つて配列されたｉ行を、該第２
の軸に沿つて配列されたビツトのｊ行（ｊは、
ｉよりも大きい整数）に変換するように、該第
２の軸に沿つて配列されたｉ行のビツト毎に、
１つまたはそれ以上の拡張ビツトの行を挿入す
る段階と、 (e) 上記段階(d)によつて生成される各々の拡張ビ
ツトの値を、次の段階（e1）乃至（e2）に従い
割り当てる段階と、 (e1) もし、上記各拡張ビツトを跨ぐ垂直方向の
隣り合うイメージ・ビツトの対がどちらも１
であるか、垂直方向に隣り合うイメージ・ビ
ツトの１つが１であり、上記各拡張ビツトを
斜め方向に跨ぐ隣り合う２つのイメージ・ビ
ツトの対のどちらかがともに１であるなら値
１を上記各拡張ビツトを１にセツトし、 (e2) さもなければ、上記拡張ビツトを０にセツ
トする段階、 (f) 上記段階で拡張されたイメージを記憶する段
階とを有する、２進イメージ引伸し方法。