JPH0221632B2 - - Google Patents

Description

【発明の詳細な説明】 産業上の利用分野 本発明は各種の圧縮、とりわけ画像情報の高速
な圧縮を行なうことのできる情報圧縮方法および
その回路に関するものである。

従来例の構成とその問題点 近年、大型コンピユータや高価な専用システム
で行なわれていた画像の拡大や縮小などの編集処
理が、安価なパーソナルコンピユータの分野でも
必要とされるようになつてきた。

以下に従来の画像の圧縮について説明する。

圧縮とは、第１図に示すように長さｎの原画像
Ｘからマスクパターンｐの要素で“１”に対応す
る要素を抽出してXaを生成し、これを圧縮して
圧縮画像Ｙを得るものである。

上記操作を行なうために第２図に示すような画
像圧縮回路が考えられる。

第２図において、１は原画像Ｘを格納するシフ
トレジスタで、クロツク信号ａが印加されると、
左へ１要素だけシフトされ、そのシフトにより最
左端の値は出力信号ｃとして送出される。２はマ
スクパターンｐを格納するシフトレジスタで、ク
ロツク信号ａが印加されると、左へ１要素だけシ
フトされ、そのシフトにより最左端の値は出力信
号ｄとして送出される。３は圧縮結果が格納され
るシフトレジスタで、後述するANDゲートの出
力信号ｆが印加されると、各要素を１つ左へシフ
トする。４は１ビツトのレジスタで、クロツク信
号ｂに同期して信号ｄを取り込むとともに信号ｅ
を出力する。５は論理積をとるANDゲートであ
る。なお、クロツク信号ａ，ｂは周波数が同じで
位相差をもつた信号である。

以上のような構成の画像圧縮回路について、そ
の動作を以下に説明する。

シフトレジスタ１，２にはそれぞれ第１図に示
す原画像Ｘとマスクパターンｐの各要素が左から
順に格納されているものとする。まず、クロツク
信号ｂに同期してシフトレジスタ２の出力信号ｄ
（この時点では“１”）がレジスタ４に取り込まれ
信号ｅとなる。次にシフトレジスタ１，２がクロ
ツク信号ａに同期してシフトされる。この時、シ
フトされる直前の信号ｅが“１”であればAND
ゲート５の出力も“１”となりシフトレジスタ３
へクロツク信号ｆが供給されシフトレジスタ１の
出力信号ｃがシフトレジスタ３に取り込まれる。
一方シフトされる直前の出力信号ｌが“０”であ
れば、シフトレジスタ３へはクロツク信号ｆが供
給されず、シフト動作は行なわれないため、シフ
トレジスタ１から出力されていた出力信号ｃは消
減する。このような動作が、クロツク信号ａ，ｂ
に同期してシフトレジスタ１の要素の数だけ行な
われることにより圧縮画像をシフトレジスタ３に
生成することができる。

しかしながら以上のような方法は、各クロツク
信号に同期して行なわれるため、高速な動作をさ
せようとすると、それに応じて高速なクロツクが
必要となりLSI化が困難であり更に表のような画
像を圧縮する場合、抽出されない要素に表の枠情
報があると、その枠情報が消減してしまうという
欠点を有していた。

発明の目的 本発明は、上記従来の問題点を解消するもの
で、LSI化に適し、高速な情報の圧縮を行ないか
つ、表のような画像を圧縮する場合でも枠情報の
消滅しない情報圧縮方法およびその回路を提供す
ることを目的とする。

発明の構成 本発明の情報圧縮方法は、圧縮すべき情報x₁，
x₂，……，x_o（但し、ｎはｎ≧２の整数）に対し
てすくなくとも２値情報からなる参照用マスクパ
ターンp₁，p₂，……，p_oを有し、前記圧縮すべき
情報x₁，x₂，……，x_oをｎ行ｎ列からなるマトリ
ツクスＡ内における第ｎ行から第１行の方向に移
動させる際に、前記参照用マスクパターンp_i（但
し、ｉは１≦ｉ≦ｎの整数）が第１の情報であれ
ばマトリツクスＡのa_i,iに位置する情報x_iと、a_i,i-1
に位置する情報ｘとで論理和演算を行ない、結果
をマトリツクスＡのa_i-1,i-1に移動するとともに、
マトリツクスＡのa_i,j（但し、ｊは（ｉ＋１）≦ｊ
≦ｎ）およびa_i,u（但し、ｕは１≦ｕ≦ｉ−２の整
数）に位置する情報ｘをマトリツクスＡのa_i-1,j-1
およびa_i-1,uにそれぞれ移動させ、一方前記参照
用マスクパターンp_iが第２の情報であればマトリ
ツクスＡのa_i,v（但し、ｖは１≦ｖ≦ｎの整数）に
位置する情報ｘをマトリツクスＡのa_i-1,vの位置
に移動させることにより、上記目的を達するもの
である。

一方本発明の情報圧縮回路は、ｎ行ｎ列（但
し、ｎはｎ≧２の整数）のマトリツクスＡのa_k,l
（但し、ｋ，ｌは３≦ｋ≦ｎ、１≦ｌ≦ｋ−２の
整数）の位置に情報伝達手段を設けるとともに、
前記マトリツクスＡのa_n,q（但し、ｍ，ｑは１≦
ｍ≦ｎ、０＜ｍ−１≦ｑ≦ｎの整数）の位置に情
報選択手段を設け、圧縮すべき情報x₁，x₂，…
…，x_oを第ｎ行から第１行の方向に移動させてい
く場合に、第ｎ行に設けられた前記情報伝達手段
は第ｎ−１行に設けられている前記情報伝達手
段、あるいは情報選択手段が情報ｘを入力できる
ように送出するとともに、第ｒ行（但し、ｒは３
≦ｒ≦ｎ−１の整数）に設けられた前記情報伝達
手段は第ｒ−１行に設けられている前記情報手
段、あるいは情報選択手段が情報ｘを入力できる
よう送出し、一方第ｎ列に設けられた前記情報選
択手段は参照用マスクパターンに対応する制御信
号に応じて前記圧縮すべき情報x_oを切り捨てるか
否かを決定するとともに、前記マトリツクスＡの
a_n-1,qの位置に設けられた前記情報選択手段は参
照用マスクパターンに対応する制御信号に応じて
前記マトリツクスＡのa_n,q+1の位置に設けられて
いる前記情報選択手段の出力情報ｘを入力する
か、前記マトリツクスＡのa_n,qの位置に設けられ
ている前記情報伝達手段、あるいは情報選択手段
の出力情報ｘを入力するかを選択し、更に前記マ
トリツクスＡのa_n-1,n-2およびa_o,o-1の位置に設け
られた前記情報選択手段は、前記マトリツクスＡ
のa_n-1,qの位置に設けられた前記選択手段に、前
記マトリツクスＡのa_n,n-1の位置に設けられた前
記情報選択手段の出力情報と、前記マトリツクス
Ａのa_n,n-2の位置に設けられた前記情報伝達手段
の出力情報との間および情報x_oとx_o-1との間で演
算を行なう演算手段を付加し、前記情報選択手段
は、参照用マスクパターンに対応する制御信号に
応じて前記マトリツクスＡのa_n,n-2の位置に設け
られている前記情報伝達手段の出力情報を入力す
るか前記情報選択手段内の前記演算手段の出力情
報を入力するかおよび情報x_o-1を入力するか情報
x_oとx_o-1との演算手段の出力情報を入力とするか
を選択することにより上記目的を達するものであ
る。

実施例の説明 以下、本発明の一実施例における情報圧縮方法
について説明する。説明の都合によりここでは８
行８列のマトリツクスとし、添字の値は０〜７で
表わす。

まず原画像Ｘをx₀，x₁，x₂，x₃，x₄，x₅，x₆，
x₇、または参照用マスクパターンｐを１、０、
１、０、０、０、１、０とした場合を考える。

第３図に示すように縦方向をｉ、横方向をｊな
る添字でマトリツクスの各要素をM_i,jで指示す
る。原画像Ｘが初めｉ＝７の行に存在し、ｉ行目
からｉ−１行目の方向にマトリツクス内を移動
し、圧縮画像Ｙ＝x₀₁，x₂₃₄₅，x₆₇を得るものであ
る。ｉ行目からｉ−１行目への移動に際し、参照
マスクパターンp_iが０であればｉ＝ｊの要素M_ij
より右の全ての要素が左へ１要素分シフトされ
る。この時、ｉ＝ｊの要素M_ijとM_ij-1の要素との
間で論理和がとられる。一方参照マスクパターン
p_iが１であれば、その時のｉ行目の全要素がｉ−
１行目に移動させる。この動作がｉ＝０の行の各
要素に対して行なわれ、マトリツクスからの出力
として圧縮画像Ｙを得る。

上記の原理に従つて実際の値をあてはめて圧縮
される様子をおつてみると、次のようになる。

(1) ｉ＝７の行ではp₇＝０であるから、x₇はx₆と
論理和がとられ、その結果M_6,6はx₆＋x₇とな
る。この例ではM_7,7より右の要素M_7,8は存在し
ないため、M_6,7は空になる。従つてｉ＝６の行
は、x₀，x₁，x₂，x₃，x₄，x₅，x₆＋x₇となる。

(2) ｉ＝６の行ではp₆＝１であるからこの行の全
要素がｉ＝５の行へ移され、従つてｉ＝５の行
はx₀，x₁，x₂，x₃，x₄，x₅，x₆＋x₇となる。

(3) ｉ＝５の行ではp₅＝０であるからx₅はx₄と論
理和がとられ、ｊ＝５より右の全要素が左へシ
フトされる。従つてｉ＝４の行は、x₀，x₁，
x₂，x₃，x₄，x₅，x₆＋x₇となる。

以下、同様にｉ＝４〜０の行に対して処理する
ことにより、マトリツクスからの出力はＹ＝x₀＋
x₁，x₂＋x₃＋x₄＋x₅＋x₆＋x₇となる。

ｊ＝８の列に０なる要素があるものとして考え
ることにより、マトリツクスの空となつた部分に
０をセツトすることができる。

次に、本発明の一実施例における情報圧縮回路
について説明する。

第４図は本発明の一実施例における情報圧縮回
路の結線を示すものである。

第４図において、１０₀〜１０₇は圧縮すべき画
像情報x₀〜x₇を印加する情報入力端子、１１₀〜
１１₇は参照用マスクパターンp₀〜p₇に応じた２
値制御信号が印加される制御信号入力端子、１２
_０〜１２₇はインバータである。１３は８行８列の
マトリツクスの要素M_j,k（但し、ｊ，ｋはともに
整数で２≦ｊ≦７、Ｏ≦ｋ≦ｊ≦−２）の位置に
設けられているとともに、上方から送出されてく
る情報を下方に送出する情報伝達手段で、単に信
号線であつてもよい。１４はマトリツクスの要素
M_s,t（但し、ｓ，ｔはともに整数で０≦ｓ≦７、
ｓ≦ｔ≦７）の位置に設けられているとともに、
制御信号入力端子１１_Sを介して送出されてくる
参照用マスクパターンp_sに対応する制御信号a_s，
b_sに応じてマトリツクスの要素M_s+1,t+1に位置す
る情報か、マトリツクスの要素M_s+1,tに位置する
情報の一方を選択する情報選択手段で、第５図ａ
に示すような論理素子１４ａ，１４ｂ，１４ｃ，
１４ｄにより構成されている。但し、マトリツク
スＭのｊ＝７の列に位置する情報選択手段につい
ては画像情報x₇を切り捨てるか否かを選択するの
みに設けられている。１６はマトリツクスの要素
M_i,i-1の位置に設けられているとともに制御信号
入力端子１１_iを介して送出されてくる参照用マ
スクパターンp_iに対応する制御信号a_i，b_iに応じ
てマトリツクスの要素M_i+1,iとM_i+1,i-1に位置する
情報との論理和の結果かマトリツクスの要素
M_i+1,i-1に位置する情報の一方を選択する情報選
択手段で、第５図ｂに示すような論理素子１６
ａ，１６ｂ，１６ｃ，１６ｄ，１６ｅにより構成
されている。情報選択手段１６は、情報選択手段
１４への情報ｃの代りに情報ｄとｃとの論理和を
入力したものである。１５₀〜１５₇は圧縮された
画像情報Ｙを得る出力端子である。

以下、第６図を参照しながら情報選択手段１４
の構成についてさらに詳細に説明する。

第６図に示すように、制御信号入力端子１１_s
を介して送出されてくる制御信号a_sが“０”制御
信号b_sが“１”の際すなわち（a_s，b_s）＝（０、
１）の際には情報選択手段１４はマトリツクスの
M_s+1,t+1に位置する情報ｃを情報選択手段１６は
M_s+1,tとM_s+1,t-1に位置する情報ｅとｆの論理和
を入力し、一方制御信号a_sが“１”、制御信号b_s
が“０”の際すなわち（a_s，b_s）＝（１、０）の際
には情報選択手段１４はマトリツクスのM_s+1,tに
位置する情報ｄを情報選択手段１６はマトリツク
スM_s+1,t-1に位置する情報ｆを選択的に入力す
る。

上記構成において、以下その動作を説明する。

なお参照マスクパターンｐは１、０、１、０、
０、０、１、０とし、最終的に圧縮情報x₀＋x₁，
x₂＋x₃＋x₄＋x₅，x₆＋x₇を得るものとする。

まず第７図ａに示すように、情報入力端子１０
_０〜１０₇を介して情報伝達手段１３₀〜１３₅及び
情報選択手段１６₀，１４₀に原画像情報x₀〜x₇を
送出する。その際、制御信号として制御信号入力
端子１１₇を介して（a₇，b₇）＝（０、１）が印加
されていることにより、情報選択手段１４₀は入
力信号として線Ｃ側の情報を、情報選択手段１６
_０はＥとＦの信号の論理和x₆₇＝x₆＋x₇を選択す
る。（以下情報x₁，x₂，……，x_iの論理和の結果
をx₁₂……ｉと記す） 次に第７図ｂに示すように、情報伝達手段１３
_０〜１３₄までの原画像情報x₀〜x₄は、情報伝達手
段１６₆〜１３₁₀に送出される。一方情報選択手
段１４₁，１６₁は制御信号として制御信号入力端
子１１₆を介して（a₆，b₆）＝（１、０）が印加さ
れていることにより、情報選択手段１４₁は線Ｄ
側の情報を選択するので原画像情報x₆₇を情報選
択手段１６₁は線Ｆ側の情報x₅を入力する。

次に第７図ｃに示すように、情報伝達手段１３
_６〜１３₉までの原画像情報x₀〜x₃は、情報伝達手
段１３₁₁〜１３₁₄に送出される。一方情報選択手
段１４₂，１６₂は制御信号として制御信号入力端
子１１₅を介して（a₅，b₅）＝（０、１）が印加さ
れていることにより情報選択手段１４₂は線Ｃ側
の情報を選択するので原画像情報x₆₇を入力し、
情報選択手段１６₂は線ＥとＦの情報の論理和x₄₅
を選択する。

次に第７図ｄに示すように、情報伝達手段１３
₁₁〜１３₁₃までの原画像情報x₀〜x₂は、情報伝達
手段１３₁₅〜１３₁₇に送出される。一方情報選択
手段１４₃，１６₃は、制御信号として制御信号入
力端子１１₄を介して（a₄，b₄）＝（０、１）が印
加されていることにより、情報選択手段１４₃は
線Ｃ側の情報を選択するので原画像情報x₆₇を入
力し、情報選択手段１６₃は線ＥとＦの論理和
x₃₄₅を選択する。

次に第７図ｅに示すように、情報伝達手段１３
₁₅と１３₁₆の原画像情報x₀，x₁は、情報伝達手段
１３₁₈，１３₁₉に送出される。一方情報選択手段
１４₄，１６₄は制御信号として制御信号入力端子
１１₃を介して（a₃，b₃）＝（０、１）が印加され
ていることにより、情報選択手段１４₄は線Ｃ側
の情報を選択するので原画像情報x₆₇を入力し、
情報選択手段１６₄は線ＥとＦの論理和x₂₃₄₅を選
択する。

次に第７図ｆに示すように、情報伝達手段１３
₁₈の原画像情報x₀は、情報伝達手段１３₂₀に送出
される。一方情報選択手段１４₅，１４₆，１６₅
は制御信号として制御信号入力端子１１₂を介し
て（a₂，b₂）＝（１、０）が印加されていることに
より、情報選択手段１４₅，１４₆はそれぞれ線
D₁，D₂側の情報を選択するので原画像情報x₂₃₄₅，
x₆₇をそれぞれ入力し、情報選択手段１６₅は線Ｆ
側の情報を選択するので原画像情報x₁を入力す
る。

次に第７図ｇに示すように、情報選択手段１４
_７，１４₈，１６₆は制御信号として制御信号入力
端子１１₁を介して（a₁，b₁）＝（０、１）が印加
されていることにより、情報選択手段１４₇，１
４₈はそれぞれ線C₁，C₂側の情報を選択するので
原画像情報x₂₃₄₅，x₆₇をそれぞれ入力し、情報選
択手段１６₆は線ＥとＦの情報の論理和x₀₁を選択
する。

そして最終的に第７図ｈに示すように、情報選
択手段１４₉，１４₁₀，１４₁₁は制御信号として制
御信号入力端子１１₀を介して（a₀，b₀）＝（１、
０）が印加されていることによりそれぞれD₁，
D₂，D₃側の情報を選択するので、原画像情報
x₀₁，x₂₃₄₅，x₆₇を入力する。そして情報選択手段
１４₉，１４₁₀，１４₁₁を最終出力として取り出す
ことにより、圧縮情報Ｙを得ることができる。

以上のように本実施例によれば、情報伝達手段
１３及び情報選択手段１４，１６をマトリツクス
状に配置した回路構成とすることにより、高速な
圧縮が必要な場合であつてもクロツクを必要とせ
ず、また、規則的な回路構成であるためLSI化に
適している。また、原画像情報の圧縮を行なう
際、隣り合つた情報の論理和をとることにより論
理“１”の情報は消減することなく従つて論理
“１”で作成された表の枠は圧縮によつて消える
ことはない。また制御信号入力端子１１に印加す
る制御信号を変えるだけで、容易に他の圧縮情報
Ｙを得ることができる。

なお本実施例では説明の都合上、情報伝達手段
１３を設けたが、前述したように情報伝達手段１
３は単なる配線でもよい為、第４図の回路は第８
図のようなものとしてもよい。

また、本実施例では圧縮の際の演算として論理
和を用いたが他の演算にすることも容易にでき
る。さらに本実施例では画像情報についてのみ説
明したが、本発明に適用される情報は他のもので
もよく、情報のサンプリング等にも利用できる。

発明の効果 以上本発明は、圧縮すべき情報をマトリツクス
を用いて処理することにより、クロツクを用いず
に高速に情報の圧縮を行なうことができまた、原
画像情報の圧縮を行なう際、隣り合つた情報の論
理和をとることにより論理“１”の情報は消減す
ることなく従つて、論理“１”で作成された表の
枠は圧縮によつて消えることはない。またその回
路は規則的なものであるためLSI化にも適してお
り、その価値は大なるものがある。

【図面の簡単な説明】

第１図は画像の圧縮を示す図、第２図は従来考
えられる画像圧縮回路のブロツク結線図、第３図
は本発明の一実施例における情報圧縮方法を説明
する図、第４図は本発明の一実施例における情報
圧縮回路の結線図、第５図は情報選択手段の回路
図、第６図は同手段の結線図、第７図は同情報圧
縮回路の動作を示す結線図、第８図は本発明の他
の実施例における情報圧縮回路の結線図である。 １３…情報伝達手段、１４…情報選択手段。

Claims (1)

1. 【特許請求の範囲】 １ 圧縮すべき情報x₁，x₂，……，x_o（但し、ｎ
   はｎ≧２の整数）に対して少なくとも２値情報か
   ら成る参照用マスクパターンp₁，p₂，……，p_oを
   有し、前記圧縮すべき情報x₁，x₂，……，x_oをｎ
   行ｎ列からなるマトリツクスＡ内における第ｎ行
   から第１行の方向に移動させる際に、前記参照用
   マスクパターンp_i（但し、ｉは１≦ｉ≦ｎの整数）
   が第１の情報であればマトリツクスＡのa_i,iに位
   置する情報x_iとa_i,i-1に位置する情報ｘとで演算を
   行ない、結果をマトリツクスＡのa_i-1,i-1に移動す
   るとともに、マトリツクスＡのa_i,j（但し、ｊは
   （ｉ＋１）≦ｊ≦ｎ）およびa_i,u（但し、ｕは１≦ｕ
   ≦ｉ−２の整数）に位置する情報ｘをマトリツク
   スＡのa_i-1,j-1およびa_i-1,uにそれぞれ移動させ、
   一方前記参照用マスクパターンp_iが第２の情報で
   あればマトリツクスＡのa_i,v（但し、ｖは１≦ｖ≦
   ｎの整数）に位置する情報ｘをマトリツクスＡの
   a_i-1,vの位置に移動させることを特徴とする情報
   圧縮方法。 ２ ｎ行ｎ列（但し、ｎはｎ≧２の整数）のマト
   リツクスＡのa_k,l（但し、ｋ，ｌは３≦ｋ≦ｎ、１
   ≦ｌ≦ｋ−２の整数）の位置に情報伝達手段を設
   けるとともに、前記マトリツクスＡのa_n,q（但し、
   ｍ，ｑは１≦ｍ≦ｎ、０＜ｍ−１≦ｑ≦ｎの整
   数）の位置に情報選択手段を設け、圧縮すべき情
   報x₁，x₂，……，x_oを第ｎ行から第１行の方向に
   移動させていく場合に、第ｎ行に設けられた前記
   情報伝達手段は第ｎ−１行に設けられている前記
   情報伝達手段、あるいは情報選択手段が情報ｘを
   入力できるよう送出するとともに、第ｒ行（但
   し、ｒは３≦ｒ≦ｎ−１の整数）に設けられた前
   記情報伝達手段は第ｒ−１行に設けられている前
   記情報伝達手段、あるいは情報選択手段が情報ｘ
   を入力できるよう送出し、一方第ｎ列に設けられ
   た前記情報選択手段は参照用マスクパターンに対
   応する制御信号に応じて前記圧縮すべき情報x_oを
   切り捨てるか否かを決定するとともに、前記マト
   リツクスＡのa_n-1,qの位置に設けられた前記情報
   選択手段は参照用マスクパターンに対応する制御
   信号に応じて前記マトリツクスＡのa_n,q+1の位置
   に設けられている前記情報選択手段の出力情報ｘ
   を入力するか、前記マトリツクスＡのa_n,qの位置
   に設けられている前記情報伝達手段、あるいは情
   報選択手段の出力情報ｘを入力するかを選択し、
   更に前記マトリツクスＡのa_n-1,n-2およびa_o,o-1の
   位置に設けられた前記情報選択手段は、前記マト
   リツクスＡのa_n-1,qの位置に設けられた前記情報
   選択手段に、前記マトリツクスＡのa_n,n-1の位置
   に設けられた前記情報選択手段の出力情報と、前
   記マトリツクスＡのa_n,n-2の位置に設けられた前
   記情報伝達手段の出力情報との間および情報x_oと
   x_o-1との間で演算を行なう演算手段を付加し、前
   記情報選択手段は、参照用マスクパターンに対応
   する制御信号に応じて前記マトリツクスＡの
   a_n,n-2の位置に設けられている前記情報伝達手段
   の出力情報を入力するか、前記情報選択手段内の
   前記演算手段の出力情報を入力するかおよび情報
   x_o-1を入力するか情報x_oとx_o-1との演算手段の出
   力情報を入力するかを選択することを特徴とする
   情報圧縮回路。 ３ 情報伝達手段は配線であることを特徴とする
   特許請求の範囲第２項記載の情報圧縮回路。