JPH0937264A - 画像符号化装置および画像符号化方法、画像復号化装置および画像復号化方法、並びに記録媒体 - Google Patents

Abstract

(57)【要約】 【課題】 画像の圧縮率を向上させる。 【解決手段】 チェーン符号化回路１２において、動画
像がチェーン符号化され、その結果得られるチェーン符
号化データが、ＲＡＭ１４に出力されて記憶される。類
似チェーン検出回路１５では、ＲＡＭ１４の記憶値を参
照して、画像上の特徴点を結ぶチェーンが検出され、複
数フレームにわたって存在する、同一の輪郭を構成する
チェーンが接続される。さらに、類似チェーン検出回路
１５では、接続されたチェーンの間の動きベクトルが検
出され、セレクト多重化回路１６に出力される。セレク
ト多重化回路１６では、類似チェーン検出回路１５で接
続されたチェーンのうちの、あるチェーンについてのチ
ェーン符号化データと、類似チェーン検出回路１５より
出力された動きベクトルとが多重化されて出力される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、画像符号化装置お
よび画像符号化方法、画像復号化装置および画像復号化
方法、並びに記録媒体に関する。特に、動画像の特徴点
に関する画像データを符号化したデータと、その特徴点
を結ぶチェーンの動きベクトルとを多重化するようにす
ることにより、発生符号量を低減することができるよう
にした画像符号化装置および画像符号化方法、画像復号
化装置および画像復号化方法、並びに記録媒体に関す
る。

【０００２】

【従来の技術】従来より、画像を、限られた伝送帯域下
で伝送する装置や、限られた蓄積容量を持つ記録媒体
（メディア）への記録を行う装置などにおいては、画像
データをより少ない符号語で効率的に圧縮するための高
能率符号化方式が採用されている。画像の高能率符号化
方式としては、例えば入力画像をＤＣＴ（離散コサイン
変換）によって直交変換し、各周波数帯域ごとに、人間
の視覚特性にしたがった適応量子化を行う方式や、ウエ
ーブレット基底（ウエーブレット変換）により画像をサ
ブバンドに分割し、それぞれのバンドごとに重み付けを
して符号化する方式などが知られている。これらの符号
化方式によれば、視覚的に歪みが目立ちにくく、また、
高圧縮率を実現することができる。

【０００３】しかしながら、これらの符号化方式におい
ては、さらに圧縮率を向上させようとすると、いわゆる
ブロック歪みなどの、視覚上好ましくない影響が顕著に
なる。

【０００４】そこで、高圧縮率下でも視覚上有害な歪み
が生じない符号化方式として、例えば画像の構造の特徴
的な点（特徴点）（例えば、エッジを構成する点（画
素）など）を抽出し、その特徴点における画像データを
効率的に符号化する、画像の特徴点検出による構造抽出
符号化方式がなどが知られている。

【０００５】図５６は、構造抽出符号化方式により画像
を圧縮符号化する、従来の画像符号化装置の一例の構成
を示している。画像データは、量子化器１１および２次
元変化点検出回路１０に入力される。量子化器１１で
は、画像データが量子化され、これにより量子化係数と
される。この量子化係数は、チェーン（チェイン）符号
化回路１２に供給される。また、２次元変化点検出回路
１０では、入力された画像データが特徴点かどうかが検
出され、入力された画像データが、特徴点である場合に
は、例えば値が１の特徴点データが、特徴点でない場合
には、例えば値が０の特徴点データが、チェーン符号化
回路１２にそれぞれ出力される。

【０００６】そして、量子化器１１における量子化処理
と、２次元変化点検出回路１０における特徴点の検出処
理とが、１フレームの画像データについて終了すると、
チェーン符号化回路１２において、特徴点データが１の
点（画素）についての位置情報（特徴点の位置（座
標））がチェーン符号化され、さらに特徴点の量子化係
数（特徴点として検出された画素における画像データの
量子化係数）と多重化されて、チェーン符号化データと
される。このチェーン符号化データは、バッファ（バッ
ファメモリ）１７に供給されて、一旦記憶された後、図
示せぬ記録媒体に記録され、あるいは伝送路に出力され
る。なお、チェーン符号化データは、バッファ１７に一
旦記憶されることで、そのデータ量の平滑化がなされ、
これにより、記録媒体または伝送路には、ほぼ一定のデ
ータレートで、チェーン符号化データが出力される。

【０００７】

【発明が解決しようとする課題】ところで、上述したよ
うな、特徴点の検出により符号化を行う、従来の画像符
号化装置では、符号化の対象が静止画であったため、動
画像を対象に符号化を行った場合、時間方向の冗長成分
を取り除くための、例えば動き補償処理およびＤＣＴ処
理などを含む変換符号化方式に比較して、圧縮率が悪い
課題があった。

【０００８】本発明は、このような状況に鑑みてなされ
たものであり、構造抽出符号化方式により画像を圧縮符
号化する際の圧縮率を向上させることができるようにす
るものである。

【０００９】

【課題を解決するための手段】本発明の画像符号化装置
は、動画像の特徴点に関する情報を符号化し、符号化デ
ータを出力する特徴点符号化手段と、特徴点を結ぶチェ
ーンを検出するチェーン検出手段と、チェーン検出手段
により検出されたチェーンの動きベクトルを検出する動
きベクトル検出手段と、特徴点符号化手段より出力され
た符号化データと、動きベクトル検出手段により検出さ
れた動きベクトルとを多重化する多重化手段とを備える
ことを特徴とする。

【００１０】この画像符号化装置は、異なるフレームに
存在するチェーンどうしを接続し、その接続結果に基づ
いて、多重化手段に多重化させる符号化データおよび動
きベクトルを決定する決定手段をさらに備えることがで
きる。決定手段には、隣接するフレームに存在するチェ
ーンどうしの類似度を算出させ、その類似度に基づい
て、チェーンどうしを接続させることができる。また、
決定手段には、複数フレームにわたって接続されたチェ
ーンのうちの所定のものに対応する符号化データと、複
数フレームのうちの、隣接するフレームの間の動きベク
トルとを、多重化手段に多重化させるようにすることが
できる。さらに、決定手段には、所定のフレームに存在
する、あるチェーンＡの、その所定のフレームに隣接す
る隣接フレームに存在する他のチェーンＢに対する類似
度を、所定のフレームから隣接フレームへの動きベクト
ルにしたがって、チェーンＡを移動させ、その移動後の
チェーンＡを構成する画素のうち、隣接フレームに存在
するチェーンの中でチェーンＢとの距離が最も近いもの
の数に基づいて算出させることができる。また、決定手
段には、チェーンＡの、チェーンＢに対する類似度ＳＡ
と、チェーンＢの、チェーンＡに対する類似度ＳＢとを
算出させ、類似度ＳＡおよびＳＢがいずれも所定の閾値
以上であるとき、チェーンＡおよびＢを接続させること
ができる。

【００１１】隣接するフレームのうちの一方のフレーム
に、チェーンＣが存在し、他方のフレームに、複数のチ
ェーンＤ１，Ｄ２，Ｄ３，・・・が存在する場合におい
ては、決定手段には、チェーンＣの、複数のチェーンＤ
１，Ｄ２，Ｄ３，・・・それぞれに対する類似度ＳＣ
１，ＳＣ２，ＳＣ３，・・・と、複数のチェーンＤ１，
Ｄ２，Ｄ３，・・・それぞれの、チェーンＣに対する類
似度ＳＤ１，ＳＤ２，ＳＤ３，・・・とを算出させ、類
似度ＳＤ１，ＳＤ２，ＳＤ３，・・・がいずれも所定の
閾値以上であり、かつ類似度ＳＣ１，ＳＣ２，ＳＣ３，
・・・の総和も所定の閾値以上であるとき、チェーンＣ
と、チェーンＤ１，Ｄ２，Ｄ３，・・・それぞれとを接
続させることができる。

【００１２】また、本発明の画像符号化装置は、所定の
フレームに存在する、あるチェーンＡを、その所定のフ
レームから、それに隣接する隣接フレームへの動きベク
トルにしたがって移動し、その移動後のチェーンＡの、
隣接フレームにおける視覚的な重要性を表す重要度を算
出する重要度算出手段と、重要度算出手段により算出さ
れた重要度が所定の閾値以上であるとき、隣接フレーム
に存在するチェーンのうち、移動後のチェーンＡの周囲
にあるものを、その移動後のチェーンＡに置き換える置
換手段とをさらに備えることができ、この場合、多重化
手段には、チェーンＡに対応する符号化データと、置換
手段によるチェーンの置き換えがなされた隣接フレーム
への動きベクトルとを多重化させることができる。

【００１３】重要度算出手段には、隣接フレームにおけ
る、移動後のチェーンＡの周囲に存在する特徴点に基づ
いて、重要度を算出させることができる。また、重要度
算出手段には、隣接フレームにおける、移動後のチェー
ンＡ上のエッジ強度に基づいて、重要度を算出させるこ
とができる。

【００１４】本発明の画像符号化方法は、動画像の特徴
点に関するデータを符号化するとともに、特徴点を結ぶ
チェーンの動きベクトルを検出し、符号化されたデータ
と、動きベクトルとを多重化することを特徴とする。

【００１５】本発明の画像復号化装置は、伝送データか
ら、動画像の特徴点に関するデータを符号化した符号化
データと、特徴点を結ぶチェーンの動きベクトルとを抽
出する抽出手段と、符号化データを復号する復号化手段
と、復号化手段の出力を、動きベクトルにしたがって動
き補償する動き補償手段とを備えることを特徴とする。

【００１６】本発明の画像復号化方法は、伝送データか
ら、動画像の特徴点に関するデータを符号化した符号化
データと、特徴点を結ぶチェーンの動きベクトルとを抽
出し、符号化データを復号して、復号化データとし、復
号化データを、動きベクトルにしたがって動き補償する
ことを特徴とする。

【００１７】本発明の記録媒体は、そこに記録されてい
るデータが、動画像の特徴点に関するデータを符号化し
た符号化データと、特徴点を結ぶチェーンの動きベクト
ルとを含むことを特徴とする。

【００１８】本発明の画像符号化装置においては、特徴
点符号化手段は、動画像の特徴点に関する情報を符号化
し、符号化データを出力するようになされている。チェ
ーン検出手段は、特徴点を結ぶチェーンを検出し、動き
ベクトル検出手段は、チェーン検出手段により検出され
たチェーンの動きベクトルを検出するようになされてい
る。多重化手段は、特徴点符号化手段より出力された符
号化データと、動きベクトル検出手段により検出された
動きベクトルとを多重化するようになされている。

【００１９】本発明の画像符号化方法においては、動画
像の特徴点に関するデータを符号化するとともに、特徴
点を結ぶチェーンの動きベクトルを検出し、符号化され
たデータと、動きベクトルとを多重化するようになされ
ている。

【００２０】本発明の画像復号化装置においては、抽出
手段は、伝送データから、動画像の特徴点に関するデー
タを符号化した符号化データと、特徴点を結ぶチェーン
の動きベクトルとを抽出し、復号化手段は、符号化デー
タを復号するようになされている。動き補償手段は、復
号化手段の出力を、動きベクトルにしたがって動き補償
するようになされている。

【００２１】本発明の画像復号化方法においては、伝送
データから、動画像の特徴点に関するデータを符号化し
た符号化データと、特徴点を結ぶチェーンの動きベクト
ルとを抽出し、符号化データを復号して、復号化データ
とし、復号化データを、動きベクトルにしたがって動き
補償するようになされている。

【００２２】本発明の記録媒体においては、そこに記録
されているデータが、動画像の特徴点に関するデータを
符号化した符号化データと、特徴点を結ぶチェーンの動
きベクトルとを含んでいる。

【００２３】

【発明の実施の形態】以下に、本発明の実施例を説明す
るが、その前に、特許請求の範囲に記載の発明の各手段
と以下の実施例との対応関係を明らかにするために、各
手段の後の括弧内に、対応する実施例（但し、一例）を
付加して、本発明の特徴を記述すると、次のようにな
る。

【００２４】即ち、請求項１に記載の画像符号化装置
は、動画像を符号化する画像符号化装置であって、動画
像の特徴点に関する情報を符号化し、符号化データを出
力する特徴点符号化手段（例えば、図１に示すチェーン
符号化回路１２など）と、特徴点を結ぶチェーンを検出
するチェーン検出手段（例えば、図１８に示すチェーン
マップ回路５１など）と、チェーン検出手段により検出
されたチェーンの動きベクトルを検出する動きベクトル
検出手段（例えば、図１８に示す動きベクトル算出回路
５４など）と、特徴点符号化手段より出力された符号化
データと、動きベクトル検出手段により検出された動き
ベクトルとを多重化する多重化手段（例えば、図１に示
すセレクト多重化回路１６など）とを備えることを特徴
とする。

【００２５】請求項２に記載の画像符号化装置は、異な
るフレームに存在するチェーンどうしを接続し、その接
続結果に基づいて、多重化手段に多重化させる符号化デ
ータおよび動きベクトルを決定する決定手段（例えば、
図１７に示すチェーン接続回路４３など）をさらに備え
ることを特徴とする。

【００２６】請求項８に記載の画像符号化装置は、所定
のフレームに存在する、あるチェーンＡを、その所定の
フレームから、それに隣接する隣接フレームへの動きベ
クトルにしたがって移動し、その移動後のチェーンＡ
の、隣接フレームにおける視覚的な重要性を表す重要度
を算出する重要度算出手段（例えば、図５２に示すプロ
グラムの処理ステップＳ１４４など）と、重要度算出手
段により算出された重要度が所定の閾値以上であると
き、隣接フレームに存在するチェーンのうち、移動後の
チェーンＡの周囲にあるものを、その移動後のチェーン
Ａに置き換える置換手段（例えば、図５２に示すプログ
ラムの処理ステップＳ１４６など）とをさらに備え、多
重化手段が、チェーンＡに対応する符号化データと、置
換手段によるチェーンの置き換えがなされた隣接フレー
ムへの動きベクトルとを多重化することを特徴とする。

【００２７】請求項１２に記載の画像復号化装置は、動
画像を復号する画像復号化装置であって、伝送データか
ら、動画像の特徴点に関するデータを符号化した符号化
データと、特徴点を結ぶチェーンの動きベクトルとを抽
出する抽出手段（例えば、図３９に示す分離回路７２な
ど）と、符号化データを復号する復号化手段（例えば、
図３９に示すチェーン復号化回路７３など）と、復号化
手段の出力を、動きベクトルにしたがって動き補償する
動き補償手段（例えば、図３９に示す動き補償回路７７
など）とを備えることを特徴とする。

【００２８】なお、勿論この記載は、各手段を上記した
ものに限定することを意味するものではない。

【００２９】図１は、本発明を適用した画像符号化装置
の第１実施例の構成を示すブロック図である。なお、図
中、図５６における場合と対応する部分については、同
一の符号を付してある。

【００３０】この画像符号化装置は、動画像を、構造抽
出符号化方式により圧縮符号化するようになされてい
る。即ち、例えば動画の画像信号をディジタル化した入
力画像データは、図５６で説明したように、２次元変化
点検出回路１０または量子化器１１をそれぞれ介して、
チェーン符号化回路１２に供給されることで、チェーン
符号化データとされる。このチェーン符号化データは、
セレクタ１３に供給される。セレクタ１３は、チェーン
符号化データを、フレーム単位で、ＲＡＭ（Chain Code
RAM）１４₁乃至１４_Nに記憶させる。

【００３１】即ち、後段の類似チェーン検出回路１５お
よびセレクト多重化回路１６は、Ｎフレーム単位（例え
ば、１５フレーム単位など）で処理を行うようになされ
ており、ＲＡＭ１４₁には、そのＮフレーム単位のチェ
ーン符号化データのうちの先頭フレーム（第１フレー
ム）のものが記憶され、また、ＲＡＭ１４₂には、第２
フレームのチェーン符号化データが記憶され、以下、同
様にして、ＲＡＭ１４_nには、第ｎフレームのチェーン
符号化データが記憶される（但し、ｎ＝１，２，・・
・，Ｎ）。

【００３２】ＲＡＭ１４₁乃至１４_Nに、Ｎフレーム分の
チェーン符号化データが記憶されると、類似チェーン検
出回路１５では、ＲＡＭ１４_nに記憶されたチェーン符
号化データが読み出され、それを参照して、第１フレー
ム乃至第Ｎフレームそれぞれに存在する、連続する特徴
点の系列であるチェーンが検出される。さらに、類似チ
ェーン検出回路１５は、各フレーム間のチェーンで類似
度の高いチェーンを検出し、それらを接続する（同一の
物体の輪郭を表すものとして対応付ける）とともに、接
続したチェーンの間の動きベクトルを検出する。

【００３３】そして、類似チェーン検出回路１５は、接
続したチェーンの中から、いわば基本とすべきチェーン
（以下、適宜、基本チェーンという）を決定し、その基
本チェーンが存在するフレームのフレーム番号（本実施
例では、そのチェーンが存在するフレームが、第ｎフレ
ームであった場合には、例えばｎをフレーム番号す
る）、基本チェーンのチェーン番号（後述するように、
各フレームに存在するチェーンそれぞれには、他のチェ
ーンと区別するためのユニークな番号が付されるように
なされており、本実施例では、例えばこの番号を、チェ
ーン番号とする）、基本チェーンから、それと接続され
た、他のフレームに存在するチェーンへの動きベクトル
を、セレクト多重化回路１６に出力する。

【００３４】セレクト多重化回路１６は、類似チェーン
検出回路１５からフレーム番号、チェーン番号、および
動きベクトルを受信すると、フレーム番号に対応するフ
レームに存在するチェーンのうち、チェーン番号に対応
するチェーンについてのチェーン符号化データを、ＲＡ
Ｍ１４1乃至１４Nのいずれかから読み出し、そのチェー
ン符号化データと、類似チェーン検出回路１５からの動
きベクトルとを多重化し、多重化チェーン符号化データ
として出力する。この多重化チェーン符号化データは、
バッファ１７を介して、伝送路に出力される。あるい
は、例えば磁気テープや、光ディスク、光磁気ディスク
などの記録媒体１８に供給されて記録される。

【００３５】図２は、図１のチェーン符号化回路１２の
構成例を示している。量子化器１１からの量子化係数
は、係数フレームバッファ２１に供給されて記憶され
る。なお、係数フレームバッファ２１では、画像上の点
（ｉ，ｊ）における画像データの量子化係数Ｑijが、例
えば図３に示すように、上位アドレスまたは下位アドレ
スが、それぞれｉまたはｊで表されるアドレスに記憶さ
れるようになされている（但し、ｉまたはｊそれぞれ
は、例えば画像を構成する画素（点）の水平方向（ｘ軸
方向）または水平方向（ｙ軸方向）の座標を表す）。

【００３６】また、２次元変化点検出回路１０からの特
徴点データは、マスクフレームバッファ２２に供給され
て記憶される。なお、マスクフレームバッファ２２にお
いても、上述の係数フレームバッファ２１における場合
と同様にして、特徴点データが記憶される。

【００３７】係数フレームバッファ２１またはマスクフ
レームバッファ２２に、１フレーム分の量子化係数また
は特徴点データが、それぞれ記憶されると、方向探索器
２３において、図４に示すフローチャートにしたがった
処理が行われる。

【００３８】即ち、まず最初に、ステップＳ１におい
て、状態レジスタ２４，Ｘ座標レジスタ２５、およびＹ
座標レジスタ２６が、０に初期化され、ステップＳ２に
進み、状態レジスタ２４の記憶値が０であるか否かが判
定される。ステップＳ２において、状態レジスタ２４の
記憶値が０であると判定された場合、ステップＳ３に進
み、未処理の座標があるかどうかが判定される。即ち、
方向探索器２３は、後述するステップＳ４において、Ｘ
座標レジスタ２５またはＹ座標レジスタ２６それぞれ
に、１フレームの画像を構成する画素のｘまたはｙ座標
を、例えばいわゆるラインスキャン順（左から右、そし
て上から下方向）にセットするようになされており、ス
テップＳ３では、Ｘ座標レジスタ２５またはＹ座標レジ
スタ２６それぞれに、画像をラインスキャン順に見た場
合に、最後に位置する画素のｘまたはｙ座標がセットさ
れているかどうかが判定される（例えば、１フレームの
画像が６４０×４００画素でなる場合は、Ｘ座標レジス
タ２５またはＹ座標レジスタ２６それぞれに、６４０ま
たは４００がセットされているかどうかが判定され
る）。

【００３９】ステップＳ３において、未処理の座標があ
ると判定された場合、ステップＳ４に進み、画像をライ
ンスキャン順に見て最初に現れる未処理の座標（ｘ，ｙ
座標）が、Ｘ座標レジスタ２５，Ｙ座標レジスタ２６に
セットされる。従って、係数フレームバッファ２１また
はマスクフレームバッファ２２に、１フレーム分の量子
化係数または特徴点データがそれぞれ記憶された直後
は、Ｘ座標レジスタ２５およびＹ座標レジスタ２６に
は、いずれも０がセットされる。

【００４０】ここで、チェーン符号化回路１２では、Ｘ
座標レジスタ２５およびＹ座標レジスタ２６の記憶値に
対応する座標の画素が、最初に処理の対象となるが、こ
のように処理の対象となる（なっている）画素を、以
下、適宜、注目画素という。

【００４１】その後、ステップＳ５に進み、注目画素に
対応する特徴点データが、マスクフレームバッファ２２
から読み出され（注目画素のｘ座標またはｙ座標をそれ
ぞれ上位アドレスまたは下位アドレスとするアドレスか
ら、特徴点データが読み出され）、それが１であるかど
うかが判定される。ステップＳ５において、特徴点デー
タが１でないと判定された場合（０であると判定された
場合）、即ち、注目画素が特徴点ではない場合、ステッ
プＳ２に戻る。また、ステップＳ５において、特徴点デ
ータが１であると判定された場合、即ち、注目画素が特
徴点である場合、ステップＳ６に進み、探索Ｘ座標レジ
スタ２７または探索Ｙ座標レジスタ２８に、Ｘ座標レジ
スタ２５またはＹ座標レジスタ２６に記憶されている値
がセットされる。さらに、ステップＳ６では、３ビット
カウンタ２９が０に初期化される。なお、３ビットカウ
ンタ２９は、３ビットで表すことのできる数、即ち、例
えば０乃至７（２³−１）をカウントすることができる
ようになされている。

【００４２】そして、方向探索器２３では、ステップＳ
７において、値が１（Ｈレベル）の有効データ選択信号
が出力される。なお、有効データ選択信号は、通常は、
０（Ｌレベル）とされている。また、有効データ選択信
号は、ラッチ回路３４、セレクタ３６、およびマルチプ
レクサ３７に供給されるようになされている。さらに、
有効データ選択信号は、０から１にされた後、１クロッ
ク分の時間が経過すると、再び０にされるようになされ
ている。

【００４３】さらに、ステップＳ７では、探索Ｘ座標レ
ジスタ２７および探索Ｙ座標レジスタ２８に記憶されて
いる座標が読み出され、開始点座標として、セレクタ３
６に出力される。また、ステップＳ７では、状態レジス
タ２４に１がセットされるとともに、マスクフレームバ
ッファ２２に記憶されている、注目画素に対応する、値
が１の特徴点データが０に書き換えられて、ステップＳ
２に戻る。

【００４４】ここで、セレクタ３６には、方向探索器２
３から有効データ選択信号および開始点座標が供給され
る他、状態レジスタ２４の記憶値、ＲＯＭ（Direction
ROM）３３の出力、および方向変化信号発生器３５の出
力が供給されるようになされている。そして、セレクタ
３６は、値が１の有効データ選択信号を受信すると、状
態レジスタ２４の記憶値を参照し、それが０である場合
には、方向探索器２３からの開始点座標、ＲＯＭ３３の
出力、または方向変化信号発生器３５の出力のうちの方
向探索器２３からの開始点座標を選択して、マルチプレ
クサ３７に出力するようになされている。

【００４５】また、マルチプレクサ３７は、値が１の有
効データ選択信号を受信すると、注目画素の量子化係数
を、係数フレームバッファ２１から読み出し、セレクタ
３６の出力と多重化して出力するようになされている。

【００４６】従って、ステップＳ７において、状態レジ
スタ２４の記憶値が０の場合において、有効データ選択
信号が１となったとき（注目画素が特徴点であるとき）
には、チェーン符号化回路１２（マルチプレクサ３７）
からは、特徴点となっている注目画素の座標（開始点座
標）と、その特徴点における量子化係数とを多重化した
チェーン符号化データが出力される。

【００４７】なお、状態レジスタ２４の記憶値が０の場
合（以下、適宜、状態０の場合という）において、有効
データ選択信号が１となったときというのは、チェーン
を構成する特徴点であって、その始点となるものが見つ
かったときである。そして、この場合、上述したよう
に、ステップＳ７において、状態レジスタ２４の記憶値
は１とされる。

【００４８】一方、ステップＳ２において、状態レジス
タ２４の記憶値が０でないと判定された場合、ステップ
Ｓ８に進み、その記憶値が１であるかどうかが判定され
る。ステップＳ８において、状態レジスタ２４の記憶値
が１であると判定された場合、図５のステップＳ１１に
進み、アドレス発生器３２が発生しているアドレスに記
憶されている特徴点データが、マスクフレームバッファ
２２から読み出される。

【００４９】ここで、アドレス発生器３２は、加算器３
８または３９よりそれぞれ出力される値を、上位アドレ
スまたは下位アドレスとするアドレスを出力するように
なされている。加算器３８には、探索Ｘ座標レジスタ２
７に記憶されているＸ座標とＲＯＭ（Search X-ROM）３
０の出力値とが供給されるようになされており、そこで
は両者が加算されて出力されるようになされている。ま
た、加算器３９には、探索Ｙ座標レジスタ２８に記憶さ
れているＹ座標とＲＯＭ（Search Y-ROM）３１の出力値
とが供給されるようになされており、そこでは、加算器
３８における場合と同様に、やはり両者が加算されて出
力されるようになされている。

【００５０】ＲＯＭ３０および３１は、３ビットのアド
レス空間を有し、そこには、図６に示すような値が記憶
されている。そして、ＲＯＭ３０および３１は、３ビッ
トカウンタ２９の出力値をアドレスとし、そのアドレス
に記憶されている記憶値を出力するようになされてい
る。

【００５１】従って、加算器３８および３９の出力を、
（加算器３８の出力，加算器３９の出力）というように
表すとともに、探索Ｘ座標レジスタ２７または探索Ｙ座
標レジスタ２８に記憶されている値を、それぞれｘまた
はｙと表すとすると、３ビットカウンタ２９の出力値が
０乃至７であるとき、加算器３８および３９の出力は、
それぞれ（ｘ−１，ｙ−１），（ｘ−１，ｙ），（ｘ−
１，ｙ＋１），（ｘ，ｙ−１），（ｘ，ｙ＋１），（ｘ
＋１，ｙ−１），（ｘ＋１，ｙ），（ｘ＋１，ｙ＋１）
となる。

【００５２】よって、３ビットカウンタ２９の出力値が
０乃至７に変化することで、アドレス発生器３２は、図
７に示すように、探索Ｘ座標レジスタ２７および探索Ｙ
座標レジスタ２８の記憶値で表される座標の画素（図
中、斜線を付してある部分）に隣接する８個の画素Ｐ０
乃至Ｐ７の座標に対応するアドレスを出力することにな
る。

【００５３】以上から、ステップＳ１１では、探索Ｘ座
標レジスタ２７および探索Ｙ座標レジスタ２８の記憶値
で表される座標の画素に隣接する画素（３ビットカウン
タ２９が出力するカウント値に対応する画素）Ｐ０乃至
Ｐ７のいずれかにおける特徴点データが、マスクフレー
ムバッファ２２から読み出されることになる。ここで、
後述する処理は、探索Ｘ座標レジスタ２７および探索Ｙ
座標レジスタ２８の記憶値で表される座標の画素を元
に、それに隣接する画素を、いわば探索して（順次、注
目画素にして）行われるので、探索Ｘ座標レジスタ２７
および探索Ｙ座標レジスタ２８の記憶値で表される座標
の画素を、以下、適宜、探索中心画素という。

【００５４】特徴点データが読み出されると、ステップ
Ｓ１２に進み、その値が１であるか否かが判定される。
ステップＳ１２において、特徴点データが１でないと判
定された場合、即ち、注目画素が特徴点でない場合、ス
テップＳ１３に進み、３ビットカウンタ２９のカウント
値（出力値）が７であるかどうかが判定される。ステッ
プＳ１３において、３ビットカウンタ２９のカウント値
が７でないと判定された場合、即ち、探索中心画素に隣
接する画素すべてについて処理を行っていない場合、ス
テップＳ１４に進み、３ビットカウンタ２９のカウント
値が１だけインクリメントされ、図４のステップＳ２に
戻る。なお、この場合、状態レジスタ２４の記憶値は１
のままであるから、ステップＳ２およびステップＳ８を
介して、再度ステップＳ１１以下の処理が行われること
になる。

【００５５】また、ステップＳ１３において、３ビット
カウンタ２９のカウント値が７であると判定された場
合、即ち、探索中心画素に隣接する画素すべてについて
処理を行い、その結果、探索中心画素に隣接する画素に
特徴点がないことが判明した場合、ステップＳ１５に進
み、状態レジスタ２４に０がセットされ、ステップＳ２
に戻る。

【００５６】一方、ステップＳ１２において、特徴点デ
ータが１であると判定された場合、即ち、注目画素が特
徴点である場合、ステップＳ１６に進み、その注目画素
が、新たに探索中心画素とされる。即ち、探索Ｘ座標レ
ジスタ２７または探索Ｙ座標レジスタ２８の記憶値が、
それぞれ注目画素のｘまたはｙ座標に更新される。その
後、ステップＳ１７に進み、有効データ選択信号が１に
され、状態レジスタ２４の記憶値が２にされる。さら
に、ステップＳ１７では、３ビットカウンタ２９が０に
初期化されるとともに、マスクフレームバッファ２２に
記憶されている、注目画素に対応する、値が１の特徴点
データが０に書き換えられて、ステップＳ２に戻る。

【００５７】ここで、セレクタ３６は、値が１の有効デ
ータ選択信号を受信すると、状態レジスタ２４の記憶値
を参照し、それが１である場合には、方向探索器２３か
らの開始点座標、ＲＯＭ３３の出力、または方向変化信
号発生器３５の出力のうちのＲＯＭ３３の出力を選択し
て、マルチプレクサ３７に出力するようになされてい
る。

【００５８】ＲＯＭ３３は、上述したＲＯＭ３０および
３１と同様に、３ビットのアドレス空間を有し、そこに
は、図８に示すような値が記憶されている。そして、Ｒ
ＯＭ３３は、やはり、ＲＯＭ３０および３１と同様に、
３ビットカウンタ２９の出力値をアドレスとし、そのア
ドレスに記憶されている記憶値（以下、適宜、この記憶
値を、方向データという）を出力するようになされてい
る。

【００５９】従って、３ビットカウンタ２９の出力値が
０乃至７であるとき、ＲＯＭ３３からは、方向データＣ
０乃至Ｃ７がそれぞれ出力される。この方向データＣ０
乃至Ｃ７は、探索中心画素からの、それに隣接する画素
が位置する８つの方向を表すようになされており、即
ち、例えば図９に示すように、左上、左、左下、上、
下、右上、右、または右下方向を表すようになされてお
り、従って、方向データＣ０乃至Ｃ７は、探索中心画素
に対し、それに隣接する画素Ｐ０乃至Ｐ７が位置する方
向をそれぞれ表す。

【００６０】よって、ＲＯＭ３３からは、探索中心画素
に対する注目画素の方向を表す方向データが出力される
ことになる。なお、方向データは、セレクタ３６の他、
ラッチ回路３４および方向変化信号発生器３５にも供給
されるようになされている。

【００６１】以上から、ステップＳ１７において、状態
レジスタ２４の記憶値が１の場合において、有効データ
選択信号が１となったとき（注目画素が特徴点であると
き）には、チェーン符号化回路１２（マルチプレクサ３
７）からは、探索中心画素（開始点座標に位置する画
素）に隣接する注目画素であって特徴点となっているも
のが位置する方向を表す方向データと、その注目画素に
おける量子化係数とを多重化したチェーン符号化データ
が出力される。

【００６２】なお、状態レジスタ２４の記憶値が１の場
合（以下、適宜、状態１の場合という）において、有効
データ選択信号が１となったときというのは、チェーン
を構成する特徴点であって、その始点に隣接するものが
見つかったときである。そして、この場合、上述したよ
うに、ステップＳ１７において、状態レジスタ２４の記
憶値は２とされる。

【００６３】図４に戻り、ステップＳ８において、状態
レジスタ２４の記憶値が１でないと判定された場合、図
１０のステップＳ２１に進む。ここで、状態レジスタ２
４には、０乃至２のいずれかの整数が記憶されるように
なされている。従って、状態レジスタ２４の記憶値が、
図４のステップＳ２で０でないと判定され、同じく図４
のステップＳ８で１でもないと判定されたということ
は、その値は２になっているということになる。

【００６４】図１０のステップＳ２１では、図５のステ
ップＳ１１における場合と同様に、探索中心画素に隣接
するいずれかの画素（３ビットカウンタ２９が出力する
カウント値に対応する画素）における特徴点データが、
マスクフレームバッファ２２から読み出され、ステップ
Ｓ２２に進み、その値が１であるか否かが判定される。
ステップＳ２２において、特徴点データが１でないと判
定された場合、即ち、注目画素が特徴点でない場合、ス
テップＳ２３に進み、３ビットカウンタ２９のカウント
値が７であるかどうかが判定される。ステップＳ２３に
おいて、３ビットカウンタ２９のカウント値が７でない
と判定された場合、即ち、探索中心画素に隣接する画素
すべてについて処理を行っていない場合、ステップＳ２
４に進み、３ビットカウンタ２９のカウント値が１だけ
インクリメントされ、図４のステップＳ２に戻る。な
お、この場合、状態レジスタ２４の記憶値は２のままで
あるから、ステップＳ２およびステップＳ８を介して、
再度ステップＳ２１以下の処理が行われることになる。

【００６５】また、ステップＳ２３において、３ビット
カウンタ２９のカウント値が７であると判定された場
合、即ち、探索中心画素に隣接する画素すべてについて
処理を行い、その結果、探索中心画素に隣接する画素に
特徴点がないことが判明した場合、ステップＳ２５に進
み、状態レジスタ２４に０がセットされ、ステップＳ２
に戻る。

【００６６】一方、ステップＳ２２において、特徴点デ
ータが１であると判定された場合、即ち、注目画素が特
徴点である場合、ステップＳ２６に進み、探索Ｘ座標レ
ジスタ２７または探索Ｙ座標レジスタ２８の記憶値が、
それぞれ注目画素のｘまたはｙ座標に更新されることに
よって、その注目画素が、新たに探索中心画素とされ
る。その後、ステップＳ２７に進み、有効データ選択信
号が１にされる。さらに、ステップＳ２７では、３ビッ
トカウンタ２９が０に初期化されるとともに、マスクフ
レームバッファ２２に記憶されている、注目画素に対応
する、値が１の特徴点データが０に書き換えられて、ス
テップＳ２に戻る。なお、この場合、状態レジスタ２４
の記憶値は２のままであるから、ステップＳ２およびス
テップＳ８を介して、再度ステップＳ２１以下の処理が
行われることになる。但し、この場合、ステップＳ２６
において、前回の処理の対象とされていた注目画素が、
新たに探索中心画素とされたため、その新たな探索中心
画素に隣接する画素を注目画素として処理が行われる。

【００６７】ここで、セレクタ３６は、値が１の有効デ
ータ選択信号を受信すると、状態レジスタ２４の記憶値
を参照し、それが２である場合には、方向探索器２３か
らの開始点座標、ＲＯＭ３３の出力、または方向変化信
号発生器３５の出力のうちの方向変化信号発生器３５の
出力を選択して、マルチプレクサ３７に出力するように
なされている。

【００６８】方向変化信号発生器３５には、ＲＯＭ３３
から出力される方向データと、ラッチ回路３４の出力が
供給されるようになされており、そこでは、これらの入
力に基づいて、後述するような方向変化データが生成さ
れるようになされている。

【００６９】即ち、図１１（Ａ）に示すように、有効デ
ータ選択信号が１になると、ラッチ回路３４は、ＲＯＭ
３３が出力する方向データ（図１１（Ｂ））をラッチ
し、１クロック分遅延した後、次に、有効データ選択信
号が１になるまでの間、その方向データを、方向変化信
号発生器３５に出力し続ける（図１１（Ｃ））。即ち、
特徴点が見つかると（有効データ選択信号が１になる
と）、ラッチ回路３４からは、その特徴点への、探索中
心画素からの方向を表す方向データが、次の特徴点が見
つかるまで出力され続ける。ここで、ラッチ回路３４が
出力する方向データを、以下、適宜、前方向データとい
う。

【００７０】方向変化信号発生器３５は、有効データ選
択信号が１になると、即ち特徴点が見つかると、ラッチ
回路３４が出力している前方向データが示す方向と、Ｒ
ＯＭ３３から出力される方向データが示す方向を比較
し、その比較結果に対応して、前方向データが示す方向
に対する、方向データが示す方向の変化を表す方向変化
データを出力するようになされている。

【００７１】即ち、方向変化信号発生器３５は、例えば
図１２（Ａ）に示すように、前方向データが示す方向と
方向データが示す方向とが同一である場合、方向変化デ
ータとしてＤ０を出力する。また、方向変化信号発生器
３５は、例えば図１２（Ｂ）乃至（Ｄ）に示すように、
方向データが示す方向が、前方向データが示す方向と反
時計回りに４５度、９０度、または１３５度だけ異なる
場合、方向変化データとしてＤ１乃至Ｄ３をそれぞれ出
力する。さらに、方向変化信号発生器３５は、図１２
（Ｅ）乃至（Ｇ）に示すように、方向データが示す方向
が、前方向データが示す方向と時計回りに４５度、９０
度、または１３５度だけ異なる場合、方向変化データと
してＤ４乃至Ｄ６をそれぞれ出力する。

【００７２】なお、方向データが示す方向と前方向デー
タが示す方向との関係としては、上述の場合の他、図１
２（Ｈ）に示すように、両者の方向が１８０度異なる場
合があるが、図２のチェーン符号化回路１２では、上述
したように、特徴点が一度処理の対象となると、それに
対応する特徴点データは０に書き換えられるので、方向
データが示す方向と前方向データが示す方向とが１８０
度異なるような場合が生じることはない。このため、図
１２（Ｈ）に示したように、方向データが示す方向と前
方向データが示す方向とが１８０度異なる場合について
は、方向変化データとして、コードは与えられていない
（与える必要がない）。

【００７３】実際には、方向変化信号発生器３５は、例
えば図１３および図１４に示すような前方向データおよ
び方向データと、方向変化データとの対応表を記憶して
おり、ラッチ回路３４が出力している前方向データと、
ＲＯＭ３３から出力された方向データとの組み合わせと
一致する行を、対応表から検索し、その行の右欄に記述
されている方向変化データを出力する。なお、方向変化
データＤ０乃至Ｄ６には、例えば図１５に示すような符
号語が割り当てられており、実際には、この符号語が出
力される。

【００７４】以上から、ステップＳ２７において、状態
レジスタ２４の記憶値が２の場合において、有効データ
選択信号が１となったとき（注目画素が特徴点であると
き）には、チェーン符号化回路１２（マルチプレクサ３
７）からは、前回見つかった特徴点についての方向（前
々回見つかった特徴点から、前回見つかった特徴点への
方向）と、今回見つかった特徴点についての方向（前回
見つかった特徴点から、今回見つかった特徴点への方
向）との違いを表す方向変化データと、今回見つかった
特徴点（注目画素）における量子化係数とを多重化した
チェーン符号化データが出力される。

【００７５】なお、状態レジスタ２４の記憶値が２の場
合（以下、適宜、状態２の場合という）において、有効
データ選択信号が１となったときというのは、３以上の
連続する特徴点からなるチェーンを構成する特徴点であ
って、その始点およびそれに隣接するもの以外のもの
（３番目以降の特徴点）が見つかったときである。そし
て、この場合、状態レジスタ２４の記憶値は２のままと
される。

【００７６】図４に戻り、ステップＳ３において、未処
理の座標がないと判定された場合、処理を終了する。そ
して、次のフレームについての量子化係数または特徴点
データが係数フレームバッファ２１またはマスクフレー
ムバッファ２２に記憶されるのを待って、再び、ステッ
プＳ１からの処理が行われる。

【００７７】次に、図１６を参照して、セレクタ３６の
出力について、さらに説明する。いま、例えば図１６に
示したように、５個の連続する特徴点（図中、斜線を付
してある部分）からなるチェーンが存在する場合、ライ
ンスキャン順に見ていくと、座標（ｉ，ｊ）に位置する
特徴点が最初に現れる。特徴点が最初に見つかった場合
の状態は、状態０であるから、セレクタ３６からは、方
向探索器２３が出力する、その特徴点の座標（ｉ，ｊ）
が開始点座標として出力される。その後、状態は状態１
とされ、座標（ｉ，ｊ）に位置する特徴点（以下、適
宜、特徴点（ｉ，ｊ）と記述する）に隣接する特徴点
（ｉ＋１，ｊ）が検出される。この特徴点（ｉ＋１，
ｊ）は、前回見つかった特徴点（ｉ，ｊ）の右方向に位
置し、また、状態は状態１であるから、セレクタ３６か
らは、ＲＯＭ３３が出力する、右方向を表す方向データ
Ｃ６（図９）が出力される。そして、この場合、状態は
状態２にされる。

【００７８】次に、特徴点（ｉ＋１，ｊ）に隣接する特
徴点（ｉ＋２，ｊ＋１）が検出される。この場合、状態
は状態２であるから、前回見つかった特徴点ついての方
向と、今回見つかった特徴点についての方向との違いを
表す方向変化データが、セレクタ３６から出力される。
即ち、前回見つかった特徴点（ｉ＋１，ｊ）についての
方向は、上述したように方向データＣ６で表される右方
向であり、また、今回見つかった特徴点（ｉ＋２，ｊ＋
１）についての方向は、この特徴点（ｉ＋２，ｊ＋１）
は、特徴点（ｉ＋１，ｊ）の右下方向に位置するから、
方向データＣ７で表される。従って、図１４に示した対
応表の、前方向データまたは方向データがそれぞれＣ６
またはＣ７となっている行の右欄に記述されている方向
変化データＤ４が、セレクタ３６から出力される。

【００７９】さらに、特徴点（ｉ＋２，ｊ＋１）には、
特徴点（ｉ＋３，ｊ＋２）が隣接しているから、この特
徴点（ｉ＋３，ｊ＋２）が検出される。そして、この特
徴点（ｉ＋３，ｊ＋２）が位置する方向は、前回見つか
った特徴点（ｉ＋２，ｊ＋１）についての方向データＣ
７が表す方向と同一の右下方向であり、従って、今回見
つかった特徴点（ｉ＋３，ｊ＋２）についての方向は、
方向データＣ７で表される。また、状態は状態２のまま
であるから、この場合、セレクタ３６からは、図１３に
示した対応表の、前方向データおよび方向データがいず
れもＣ７となっている行の右欄に記述されている方向変
化データＤ０が出力される。

【００８０】そして、特徴点（ｉ＋３，ｊ＋２）に隣接
する特徴点（ｉ＋２，ｊ＋３）についても、特徴点（ｉ
＋３，ｊ＋２）と同様に処理され、その結果、セレクタ
３６からは、方向変化データＤ６が出力される。

【００８１】従って、画像上にチェーンが存在する場
合、チェーン符号化回路１２からは、まず最初に、その
チェーンの始点となる特徴点の座標と、その特徴点にお
ける量子化係数とを多重化したものが出力される。その
後、その始点に隣接する特徴点についての方向データ
と、その特徴点における量子化係数とを多重化したもの
が出力される。そして、その特徴点に隣接する特徴点
（始点を除く）が存在する場合には、即ち、３番目以降
の特徴点が存在する場合には、その特徴点についての方
向変化データと、その特徴点における量子化係数とを多
重化したものが順次出力される。

【００８２】以上のようにして、チェーン符号化回路１
２から出力されたチェーン符号化データは、上述したよ
うに、セレクタ１３（図１）を介して、ＲＡＭ１４₁乃
至１４_Nに供給されることで、ＲＡＭ１４_nには、第ｎフ
レームのチェーン符号化データが記憶される。そして、
ＲＡＭ１４₁乃至１４_Nすべてにチェーン符号化データが
記憶されると、即ち、Ｎフレーム分のチェーン符号化デ
ータが記憶されると、類似チェーン検出回路１５に読み
出され、以下に詳述するような処理が施される。

【００８３】図１７は、図１の類似チェーン検出回路１
５の構成例を示している。類似度検知回路４１は、ＲＡ
Ｍ１４₁乃至１４_Nすべてにチェーン符号化データが記憶
されると、即ち、Ｎフレーム分のチェーン符号化データ
が記憶されると、ＲＡＭ１４₁乃至１４_Nそれぞれから、
各フレームのチェーン符号化データを読み出し、隣接す
るフレーム間で、類似度の高いチェーンに関する情報
を、ＲＡＭ４２₁乃至４２_Nに供給して記憶させる。な
お、第ｎフレームのチェーンに関する情報は、ＲＡＭ４
２_nに記憶されるようになされている。

【００８４】ＲＡＭ４２₁乃至４２_Nそれぞれに、第１乃
至第Ｎフレームそれぞれについてのチェーンに関する情
報が記憶されると、チェーン接続回路４３は、その情報
を読み出し、さらに、その情報に基づいて、チェーンの
動きベクトルを検出しながら、隣接するフレームに存在
するチェーンどうしを接続する。そして、チェーン接続
回路４３は、接続したチェーンに関する情報を、ＲＡＭ
（Connection RAM）４４に順次記憶させ、１つのチェー
ンについての処理を終了すると、接続したチェーンのう
ち、所定のチェーンのチェーン番号、そのチェーンが存
在するフレームのフレーム番号、および検出した動きベ
クトルを出力する。

【００８５】図１８は、図１７の類似度検知回路４１の
構成例を示している。ＲＡＭ１４₁乃至１４_Nに記憶され
た各フレームのチェーン符号化データは、チェーンマッ
プ回路５１および類似度計算回路５３に供給されるよう
になされている。チェーンマップ回路５１は、各フレー
ムのチェーン符号化データを受信すると、そこに含まれ
る開始点座標、方向データ、および方向変化データ（以
下、適宜、これらをまとめて、チェーンの方向成分とい
う）を参照して、各フレームに存在するチェーンを、各
チェーンにユニークな番号としてのチェーン番号を付し
て、ＲＡＭ（Map RAM）５２₁乃至５２_N上に展開する。

【００８６】即ち、例えば図１９に示すように、第ｎフ
レームに、チェーンＣＨ１乃至ＣＨ５が存在する場合、
チェーンマップ回路５１は、チェーンＣＨ１乃至ＣＨ５
それぞれにユニークなチェーン番号を付加する。そし
て、図２０に示すように、チェーンＣＨ１乃至ＣＨ５そ
れぞれが存在する位置に対応する、ＲＡＭ５２_nのアド
レスに、それぞれに付されたチェーン番号を記憶させ
る。図２０の実施例では、チェーンＣＨ１乃至ＣＨ５
に、それぞれチェーン番号０，１０，１４，４３，１２
３が付されている。また、チェーンマップ回路５１は、
チェーンが存在しない位置に対応する、ＲＡＭ５２_nの
アドレスには、チェーン番号として使用されない値（図
２０の実施例においては、−１）を記憶させる。

【００８７】以上のようにして、チェーンマップ回路５
１は、第ｎフレームに存在するチェーンを、ＲＡＭ５２
_nに、いわばチェーン番号によるビットマップとして展
開する。

【００８８】なお、チェーン番号は、各フレームに存在
するチェーンについてユニークなものとなっていれば良
い。但し、チェーン番号は、類似チェーン検出回路１５
の処理単位であるＮフレームに存在するすべてのチェー
ンについてユニークなものとなるようにしても良い。

【００８９】ＲＡＭ５２₁乃至５２_Nそれぞれに、第１乃
至第Ｎフレームのチェーンが展開されると、類似度計算
回路５３は、ＲＡＭ５２₁乃至５２_Nにそれぞれ記憶され
た、各フレームのチェーンについて、図２１に示すフロ
ーチャートにしたがった処理を行う。

【００９０】即ち、まず最初に、ステップＳ３１におい
て、いま処理の対象となっているフレーム（以下、適
宜、注目フレームという）に、未処理のチェーン（後述
する注目チェーンとされていないチェーン）が存在する
かどうかが判定される。ステップＳ３１において、未処
理のチェーンが存在すると判定された場合、そのチェー
ン（未処理のチェーンが複数存在する場合には、そのう
ちのいずれか１つのチェーン）を処理対象として（以
下、適宜、処理対象としたチェーンを注目チェーンとい
う）、ステップＳ３２以下の処理が行われる。なお、こ
こでは、特に断らない限り、第ｎフレームが注目フレー
ムとされているものとする。

【００９１】即ち、ステップＳ３２では、注目チェーン
についての、その注目チェーンが存在するフレームの１
フレーム前のフレーム（以下、適宜、前フレームとい
う）（ここでは、第ｎ−１フレーム）への動きベクトル
を、動きベクトル算出回路５４に検出（算出）させる。
なお、ステップＳ３２では、類似度計算回路５３は、Ｒ
ＡＭ１４_nから供給される第ｎフレームのチェーン符号
化データに基づいて、注目チェーンを認識するととも
に、前フレームである第ｎ−１フレームについてのチェ
ーンのビットマップを、ＲＡＭ５２_n-1から読み出し、
これらを動きベクトル算出回路５４に供給することで、
動きベクトル検出回路５４に、注目チェーンの、前フレ
ームへの動きベクトルを検出させるようになされてい
る。

【００９２】注目チェーンの、前フレームへの動きベク
トルが算出されると、その動きベクトルは、注目チェー
ンのチェーン番号と対応付けられ、ＲＡＭ４２_n（図１
７）に出力されて記憶される。その後、ステップＳ３３
に進み、ステップＳ３２で算出された動きベクトルにし
たがって、注目チェーンが動き補償される。そして、ス
テップＳ３４に進み、動き補償後の注目チェーンを用い
て、前フレームに存在するチェーンのうち、注目チェー
ンとの類似度を最も高くするものが検出される。

【００９３】ここで、類似度計算回路５３では、ステッ
プＳ３４において、注目チェーンの、前フレームに存在
する、あるチェーンＣＨに対する類似度が、次のように
して算出される。即ち、類似度計算回路５３は、動き補
償後の注目チェーンを構成する画素（特徴点）のうち、
前フレームである第ｎ−１フレームに存在するチェーン
の中でチェーンＣＨとの距離が最も短いものを、ＲＡＭ
５２_n-1を参照して検出し、その数をカウントする。そ
して、そのカウント数を、注目チェーンを構成する画素
数で除算し、その除算結果を、チェーンＣＨに対する注
目チェーンの類似度とする。

【００９４】従って、ステップＳ３４では、ＲＡＭ５２
n-1に記憶されているチェーンの中で、動き補償後の注
目チェーンを構成する画素それぞれについて、その画素
から最も近い位置にあるものが選択され、その選択回数
が最も多いチェーンが、注目チェーンとの類似度を最も
高くするものとして検出される。なお、このとき、類似
度は、選択回数を、注目チェーンを構成する画素数で除
算することによって得られる。

【００９５】注目チェーンの類似度を最も高くする、前
フレームに存在するチェーン（以下、適宜、高類似度チ
ェーンという）が検出されると、ステップＳ３５に進
み、その類似度が所定の閾値Ｔ以上であるか否かが判定
される。ステップＳ３５において、注目チェーンの高類
似度チェーンに対する類似度が所定の閾値Ｔ以上である
と判定された場合、ステップＳ３６に進み、その高類似
度チェーンのチェーン番号が、注目チェーンのチェーン
番号と対応付けられる。そして、ＲＡＭ４２_nに出力さ
れて記憶され、ステップＳ３８に進む。なお、注目チェ
ーンのチェーン番号は、上述したステップＳ３２におい
て、動きベクトル（注目チェーンの、前フレームへの動
きベクトル）と対応付けられて、ＲＡＭ４２_nに既に記
憶されているので、ステップＳ３６では、これらに、高
類似度チェーンのチェーン番号が対応付けられて、ＲＡ
Ｍ４２_nに記憶される。

【００９６】一方、ステップＳ３５において、注目チェ
ーンの高類似度チェーンに対する類似度が所定の閾値Ｔ
以上でないと判定された場合、ステップＳ３６に進み、
前フレームには、注目チェーンに接続される可能性のあ
るチェーンがない（注目チェーンと同一の（物体の）輪
郭を表すチェーンがない）として、その旨を示す未対応
コード（本実施例では、後述する図２３に示すように、
例えば−１）が、注目チェーンのチェーン番号と対応付
けられ、ＲＡＭ４２_nに記憶されて、ステップＳ３８に
進む。

【００９７】ステップＳ３８では、注目チェーンについ
ての、その注目チェーンが存在するフレームの１フレー
ム後のフレーム（以下、適宜、後フレームという）（こ
こでは、第ｎ＋１フレーム）への動きベクトルを、動き
ベクトル算出回路５４に、上述したステップＳ３２にお
ける場合と同様にして検出（算出）させる。さらに、ス
テップＳ３８では、注目チェーンの、後フレームへの動
きベクトルが、注目チェーンのチェーン番号と対応付け
られ、ＲＡＭ４２_nに出力されて記憶される。その後、
ステップＳ３９に進み、ステップＳ３８で算出された動
きベクトルにしたがって、注目チェーンが動き補償され
る。そして、ステップＳ４０に進み、動き補償後の注目
チェーンを用いて、後フレームに存在するチェーンのう
ち、注目チェーンとの類似度を最も高くするもの（これ
も、以下、適宜、高類似度チェーンという）が、上述し
たステップＳ３４における場合と同様にして検出され
る。

【００９８】その後、ステップＳ４１に進み、注目チェ
ーンの高類似度チェーンに対する類似度が所定の閾値Ｔ
以上であるか否かが判定される。ステップＳ４１におい
て、その類似度が所定の閾値Ｔ以上であると判定された
場合、ステップＳ４２に進み、その高類似度チェーンの
チェーン番号が、注目チェーンのチェーン番号と対応付
けられ、ＲＡＭ４２_nに出力されて記憶される。また、
ステップＳ４１において、注目チェーンの高類似度チェ
ーンに対する類似度が所定の閾値Ｔ以上でないと判定さ
れた場合、ステップＳ４３に進み、後フレームには、注
目チェーンに接続される可能性のあるチェーンがないと
して、上述したステップＳ３７における場合と同様に、
その旨を示す未対応コードが、注目チェーンのチェーン
番号と対応付けられ、ＲＡＭ４２_nに記憶される。

【００９９】ステップＳ４２およびＳ４３の処理後は、
いずれも、ステップＳ３１に戻り、ステップＳ３１にお
いて、未処理のチェーンがないと判定されるまで、ステ
ップＳ３１乃至Ｓ４３の処理を繰り返す。そして、ステ
ップＳ３１において、未処理のチェーンがないと判定さ
れた場合、処理を終了する。なお、その後は、いま注目
フレームとされていた第ｎフレームに代えて、第ｎ＋１
フレームを、新たに注目フレームとして、図２１に示し
た処理が繰り返される。即ち、以上の処理が、ＲＡＭ１
４₁乃至１４_Nに記憶されたＮフレーム分のチェーン符号
化データについて行われる。

【０１００】以上の処理により、ＲＡＭ４２_nには、次
のようなチェーンに関する情報が記憶される。即ち、例
えば、いま、図２２に示すように、第ｎフレームに、チ
ェーン＃０（＃の後の数字は、チェーン番号を表す）が
存在し、このチェーン＃０の類似度を、閾値Ｔ以上とす
る高類似度チェーン＃１２または＃３４が、それぞれ前
または後フレームに存在する場合であって、注目チェー
ンの、前フレームまたは後フレームへの動きベクトル
が、それぞれ（１，２）または（０，−８）であると
き、ＲＡＭ４２_nには、図２３（図２３の先頭行）に示
すように、チェーン＃０のチェーン番号０に、後フレー
ムへの動きベクトル（０，−８）、前フレームへの動き
ベクトル（１，２）、前フレームに存在する高類似度チ
ェーン＃１２のチェーン番号（「前フレームで類似度が
最も高いチェーンの番号」）１２、および後フレームに
存在する高類似度チェーン＃３４のチェーン番号（「後
フレームで類似度が最も高いチェーンの番号」）３４が
対応付けられて記憶される。

【０１０１】以下、同様に、ＲＡＭ４２_nには、第ｎフ
レームに存在するチェーンすべてに関する情報が、チェ
ーンごとに記憶される。なお、前フレームに存在する高
類似度チェーンのチェーン番号（「前フレームで類似度
が最も高いチェーンの番号」）、または後フレームに存
在する高類似度チェーンのチェーン番号（「後フレーム
で類似度が最も高いチェーンの番号」）の欄が−１、即
ち未対応コードとなっているのは、その行のチェーン番
号に対応するチェーンには、上述したように、前フレー
ムまたは後フレームに、そのチェーンに接続される可能
性のあるチェーンが存在しないことを示している。

【０１０２】次に、図２４は、図１７のチェーン接続回
路４３の処理を説明するフローチャートである。チェー
ン接続回路４３では、ＲＡＭ４２₁乃至４２_Nに、第１乃
至第Ｎフレームのチェーンに関する情報がそれぞれ記憶
されると、ステップＳ５１において、ＲＡＭ４４が初期
化され、ステップＳ５２に進み、未処理のチェーンが、
ＲＡＭ４２₁乃至４２_Nに記憶されているか否かが判定さ
れる。なお、この判定は、例えばチェーン番号順および
フレーム番号順に、未処理のチェーンが検索されること
によって行われる。

【０１０３】ステップＳ５２において、未処理のチェー
ンが存在すると判定された場合、そのチェーンが注目チ
ェーンとされ、ステップＳ５３に進み、注目チェーンの
チェーン番号、そのチェーン番号と対応付けられている
前フレームへの動きベクトル、および後フレームへの動
きベクトルが、ＲＡＭ４２（ＲＡＭ４２₁乃至４２_Nのい
ずれか）から読み出される。さらに、ステップＳ５３で
は、これらが、注目チェーンが存在するフレームのフレ
ーム番号（これは、注目チェーンが記憶されていたＲＡ
Ｍ４２nのサフィックスｎに等しい）と対応付けられ、
ＲＡＭ４４に出力されて記憶される。

【０１０４】そして、ステップＳ５４に進み、前フレー
ムに、注目チェーンとの所定の接続条件を満足するチェ
ーンが存在するか否かが判定される。即ち、ステップＳ
５４では、例えば前フレームに、注目チェーンに対する
高類似度チェーンが存在し、その高類似度チェーンが、
まだ注目チェーンとされたことがなく、かつ、その高類
似度チェーンについての後フレーム（前フレームに存在
する高類似度チェーンから見た後フレーム（従って、注
目フレーム））に存在する高類似度チェーンが、注目チ
ェーンであるかどうかが、ＲＡＭ４２を参照することに
よって判定される。

【０１０５】以上のような注目チェーンとの接続条件を
満たすチェーンが、前フレームに存在する場合、ステッ
プＳ５５に進み、そのチェーンが、新たに注目チェーン
とされ、ステップＳ５３に戻る。従って、この場合、新
たな注目チェーンのチェーン番号、そのチェーン番号と
対応付けられている前フレームへの動きベクトル、およ
び後フレームへの動きベクトルが、ＲＡＭ４２から読み
出され、さらに、その新たな注目チェーンが存在するフ
レームのフレーム番号と対応付けられ、ＲＡＭ４４に出
力されて記憶される。これにより、前回注目チェーンで
あったチェーンと、新たな注目チェーンとが接続され
る。即ち、前回注目チェーンであったチェーンと、新た
な注目チェーンとは、同一の輪郭を表すものとして対応
付けられる。

【０１０６】なお、ＲＡＭ４２に記憶されているチェー
ン（高類似度チェーン）は、図２１で説明したように、
注目チェーンに対する類似度が閾値Ｔ以上のものである
から、以上の処理によれば、あるフレームに存在するチ
ェーンＡと、その前フレームに存在するチェーンＢと
は、チェーンＢに対するチェーンＡの類似度ＳＡ、およ
びチェーンＡに対するチェーンＢの類似度ＳＢがいずれ
も所定の閾値Ｔ以上であるときに接続されることにな
る。

【０１０７】一方、ステップＳ５４において、注目チェ
ーンとの接続条件を満たすチェーンが、前フレームに存
在しないと判定された場合、ステップＳ５６に進み、ス
テップＳ５２で未処理のチェーンが存在すると判定され
た直後に、注目チェーンとされたチェーンが、再び注目
チェーンとされ、ステップＳ５７に進む。ステップＳ５
７では、後フレームに、注目チェーンとの所定の接続条
件を満足するチェーンが存在するか否かが判定される。
即ち、ステップＳ５７では、例えば後フレームに、注目
チェーンに対する高類似度チェーンが存在し、その高類
似度チェーンが、まだ注目チェーンとされたことがな
く、かつ、その高類似度チェーンについての前フレーム
（後フレームに存在する高類似度チェーンから見た前フ
レーム（従って、注目フレーム））に存在する高類似度
チェーンが、注目チェーンであるかどうかが、ＲＡＭ４
２を参照することによって判定される。

【０１０８】以上のような注目チェーンとの接続条件を
満たすチェーンが、後フレームに存在する場合、ステッ
プＳ５８に進み、そのチェーンが、新たに注目チェーン
とされ、ステップＳ５９に進む。ステップＳ５９では、
新たな注目チェーンのチェーン番号、そのチェーン番号
と対応付けられている前フレームへの動きベクトル、お
よび後フレームへの動きベクトルが、ＲＡＭ４２から読
み出され、さらに、その新たな注目チェーンが存在する
フレームのフレーム番号と対応付けられ、ＲＡＭ４４に
出力されて記憶される。これにより、前回注目チェーン
であったチェーンと、新たな注目チェーンとが接続され
る。

【０１０９】一方、ステップＳ５７において、注目チェ
ーンとの接続条件を満たすチェーンが、後フレームに存
在しないと判定された場合、ステップＳ６０に進み、Ｒ
ＡＭ４４に記憶されたフレーム番号のうち、例えば最小
のもの（以下、適宜、最小フレーム番号という）、その
最小フレーム番号に対応付けられているチェーン番号
（以下、適宜、最小チェーン番号という）、および後フ
レームへの動きベクトルすべてが、セレクト多重化回路
１６（図１）に出力される。

【０１１０】即ち、フレーム番号が最小のフレームに対
応付けられたチェーンが基本チェーンに決定されるとと
もに、後フレームへの動きベクトルすべてが多重化すべ
き動きベクトルに決定され、基本チェーンが存在するフ
レーム番号、そのチェーン番号、および後フレームへの
動きベクトルすべてが、セレクト多重化回路１６に出力
される。

【０１１１】以上の処理により、ＲＡＭ４２_nの記憶内
容が、例えば図２５（Ａ）に示すようなものであった場
合、ＲＡＭ４４には、図２５（Ｂ）に示すような情報が
記憶され、さらに、チェーン接続回路４３からは、図２
５（Ｃ）に示すような情報が出力される。即ち、例え
ば、いま、図２５（Ａ）に示した第６フレームに存在す
るチェーン＃５６（チェーン番号が５６のチェーン）
が、ステップＳ５２において注目チェーンとされたとす
ると、ステップＳ５３において、そのフレーム番号６、
チェーン番号５６、後フレームへの動きベクトル（−
３，−６）、および前フレームへの動きベクトル（０，
２）が、ＲＡＭ４４に記憶される（図２５（Ｂ））。

【０１１２】そして、チェーン＃５６についての「前フ
レームで類似度が最も高いチェーンの番号」の欄には、
チェーン番号２７３が記述されているから、第６フレー
ムの前フレームである第５フレームには、チェーン＃５
６に対する高類似度チェーンであるチェーン＃２７３が
存在する。さらに、このチェーン＃２７３についての後
フレームで類似度が最も高いチェーンの番号」の欄に
は、チェーン番号＃５６が記述されており（図２５
（Ａ））、従って、このチェーン＃２７３が注目チェー
ンとされたことがないとすれば、チェーン＃２７３は、
ステップＳ５４で判定される接続条件を満たすことにな
る。よって、この場合、このチェーン＃２７３のフレー
ム番号５、チェーン番号２７３、後フレームへの動きベ
クトル（−１，３）、および前フレームの動きベクトル
（３，６）は、ＲＡＭ４４に記憶される（図２５
（Ｂ））。

【０１１３】接続条件を満たすチェーン＃２７３は、ス
テップＳ５５において新たな注目チェーンとされるが、
このチェーン＃２７３についての「前フレームで類似度
が最も高いチェーンの番号」の欄には、未対応コード
（−１）が記述されているから、前フレームには、チェ
ーン＃２７３との接続条件を満たすチェーンは存在しな
い。

【０１１４】このため、ステップＳ５６で、チェーン＃
５６が再び注目チェーンとされる。そして、チェーン＃
５６についての「後フレームで類似度が最も高いチェー
ンの番号」の欄には、チェーン番号＃２４が記述されて
いるから、第６フレームの後フレームである第７フレー
ムには、チェーン＃５６に対する高類似度チェーンであ
るチェーン＃２４が存在する。さらに、このチェーン＃
２４についての「前フレームで類似度が最も高いチェー
ンの番号」の欄には、チェーン番号＃５６が記述されて
おり（図２５（Ａ））、従って、このチェーン＃２４が
注目チェーンとされたことがないとすれば、チェーン＃
２４は、ステップＳ５７で判定される接続条件を満たす
ことになる。よって、この場合、このチェーン＃２４の
フレーム番号７、チェーン番号２４、後フレームへの動
きベクトル（０，−２）、および前フレームの動きベク
トル（３，９）は、ＲＡＭ４４に記憶される（図２５
（Ｂ））。

【０１１５】接続条件を満たすチェーン＃２４は、ステ
ップＳ５８において新たな注目チェーンとされるが、こ
のチェーン＃２４についての「後フレームで類似度が最
も高いチェーンの番号」の欄には、未対応コード（−
１）が記述されているから、後フレームには、チェーン
＃２４との接続条件を満たすチェーンは存在しない。

【０１１６】従って、いままで、ＲＡＭ４４に記憶され
た情報のうち、最小フレーム番号、最小チェーン番号、
および後フレームへの動きベクトルすべてが、ステップ
Ｓ６０において読み出されて出力される。

【０１１７】即ち、ＲＡＭ４４の記憶内容が、図２５
（Ｂ）に示すようなものであった場合、図２５（Ｃ）に
示すように、最小のフレーム番号である５、そのフレー
ム番号に対応付けられているチェーン番号である２７
３、および後フレームへの動きベクトル（−１，−
３），（−３，−６），（０，２）が、類似チェーン検
出回路１５（チェーン接続回路４３）からセレクト多重
化回路１６に出力される。

【０１１８】そして、セレクト多重化回路１６では、上
述したように、最小フレーム番号ｎのフレームに存在す
る最小チェーン番号のチェーンについてのチェーン符号
化データが、ＲＡＭ１４_nから読み出され、そのチェー
ン符号化データと、類似チェーン検出回路１５からの動
きベクトルすべてとが多重化されることにより、多重化
チェーン符号化データとされて出力される。

【０１１９】即ち、例えば、いま、図２６に示すよう
に、第ｎ乃至第Ｎフレームにそれぞれ存在するチェーン
ＣＨ_n乃至ＣＨ_Nが接続されたとすると、セレクト多重化
回路１６からは、チェーンＣＨ_nについてのチェーン符
号化データと、チェーンＣＨ_nからチェーンＣＨ_N-1まで
の後フレームへの動きベクトルすべてとを多重化したも
のが出力される。

【０１２０】従って、複数フレーム間にわたって接続さ
れたチェーン（時間方向に見た場合に、類似しているチ
ェーン）は、ある１つのチェーン（基本チェーン）につ
いてのチェーン符号化データと、そのチェーンを移動
（動き補償）して他のチェーンを復元するための動きベ
クトルとにされて出力されるので、即ち、複数フレーム
間にわたって類似するチェーンどうしを接続すること
で、そのようなチェーンを節点とする木構造を構成し、
そのうちの一つ節点となっているチェーンに関しては、
そのチェーンについてのチェーン符号化データを、その
他のチェーンに関しては、動きベクトルを出力するよう
にしたので、従来のように、各フレームに存在するチェ
ーンをそれぞれチェーン符号化データとして出力する場
合に比較して、時間方向の冗長度を低下させることがで
き、その結果、画像の圧縮効率を向上させることができ
る。

【０１２１】また、これにより、動画を、限られた伝送
帯域の伝送路で伝送したり、容量の少ない記録媒体に記
録したりすることが可能となる。

【０１２２】なお、基本チェーンは、接続されたチェー
ンのうち、フレーム番号が最小のフレームに存在するチ
ェーンとする他、例えばフレーム番号が最大のフレーム
に存在するチェーンや、その他の任意のチェーンとする
ことが可能である。基本チェーンを、例えばフレーム番
号が最大のフレームに存在するチェーンとした場合、類
似チェーン検出回路１５（チェーン接続回路４３）から
出力させる動きベクトルは、前フレームへの動きベクト
ルすべてとすれば良い。

【０１２３】次に、図２７は、図１の類似チェーン検出
回路１５の他の構成例を示している。多チェーン類似度
検知回路６１は、図１７の類似度検知回路４１と同様に
して、ＲＡＭ１４₁乃至１４_Nすべてにチェーン符号化デ
ータが記憶されると、ＲＡＭ１４₁乃至１４_Nそれぞれか
ら、各フレームのチェーン符号化データを読み出し、隣
接するフレームに存在するチェーンに関する情報を、Ｒ
ＡＭ６２に供給して記憶させる。

【０１２４】但し、類似度検知回路４１では、注目チェ
ーンの類似度を最も高くし、かつその類似度が所定の閾
値Ｔ以上となるチェーン（高類似度チェーン）が、隣接
フレーム（前フレームおよび後フレーム）に存在する場
合に、注目チェーンのチェーン番号に、後フレームへの
動きベクトル、前フレームへの動きベクトル、前フレー
ムに存在する高類似度チェーンのチェーン番号、および
後フレームに存在する高類似度チェーンのチェーン番号
が対応付けられ、ＲＡＭ４２に記憶されるようになされ
ていたが（図２３）、多チェーン類似度検知回路６１で
は、注目チェーンの類似度を０より大きくするチェーン
（注目チェーンが類似度を有するチェーン（以下、適
宜、有類似度チェーンという）が、隣接フレームに存在
すれば、注目チェーンのチェーン番号に、後フレームへ
の動きベクトル、前フレームへの動きベクトル、前フレ
ームに存在する有類似度チェーンすべてのチェーン番
号、および後フレームに存在する有類似度チェーンすべ
てのチェーン番号が対応付けられ、ＲＡＭ６２に記憶さ
れるようになされている。さらに、ＲＡＭ６２には、有
類似度チェーンのチェーン番号に、そのチェーンに対す
る注目チェーンの類似度が対応付けられて記憶されるよ
うにもなされている。

【０１２５】図２８は、ＲＡＭ６２nの記憶内容を表し
ている。この図２８の実施例のチェーン番号＃０の行
は、第ｎフレームに存在するチェーン＃０の、後フレー
ムへの動きベクトルまたは前フレームへの動きベクトル
が、それぞれ（０，−８）または（１，２）であり、前
フレームに有類似度チェーン＃１２，＃８，＃４４が存
在するとともに、後フレームに有類似度チェーン＃１０
９，＃６９が存在することを表している。また、前フレ
ームに存在する有類似度チェーン＃１２，＃８，＃４４
に対する注目チェーンの類似度は、それぞれ０．７，
０．２３，０．０６であり、後フレームに存在する有類
似度チェーン＃１０９，＃６９に対する注目チェーンの
類似度は、それぞれ０．７，０．１であることを表して
いる。

【０１２６】なお、前フレームまたは後フレームに、有
類似度チェーンが存在しない場合には、前フレームのチ
ェーン番号または後フレームのチェーン番号の欄および
その類似度の欄には、その旨を表す、例えば−１が記述
される。

【０１２７】チェーン番号＃１の行は、第ｎフレームに
存在するチェーン＃１の、後フレームへの動きベクトル
または前フレームへの動きベクトルが、それぞれ（７，
７）または（２，１）であり、前フレームに、類似度を
０．９２とする有類似度チェーン＃１２１が存在すると
ともに、後フレームに、類似度を０．９７とする有類似
度チェーン＃３９が存在することを表している。また、
チェーン番号＃Ｎ２の行は、第ｎフレームに存在するチ
ェーン＃Ｎ２の、後フレームへの動きベクトルまたは前
フレームへの動きベクトルが、それぞれ（−５，−５）
または（０，−１）であり、前フレームに、類似度を
０．２とする有類似度チェーン＃２が存在し、後フレー
ムには、有類似度チェーンが存在しないことを表してい
る。

【０１２８】ＲＡＭ６２₁乃至６２_Nに、以上のような第
１乃至第Ｎフレームのチェーンに関する情報がそれぞれ
記憶されると、多チェーン接続回路６３では、図２９に
示すフローチャートにしたがった処理が行われる。即
ち、多チェーン接続回路６３では、まず最初に、ステッ
プＳ６１において、ＲＡＭ（Connection RAM）６４が初
期化され、ステップＳ６２に進み、未処理のチェーン
が、ＲＡＭ６２1乃至６２Nに記憶されているか否かが判
定される。なお、この判定は、図２４のステップＳ５２
における場合と同様に、例えばチェーン番号順およびフ
レーム番号順に、未処理のチェーンが検索されることに
よって行われる。

【０１２９】ステップＳ６２において、未処理のチェー
ンが存在すると判定された場合、そのチェーンが注目チ
ェーンとされ、ステップＳ６３に進み、注目チェーンの
チェーン番号、そのチェーン番号と対応付けられている
前フレームへの動きベクトル、および後フレームへの動
きベクトルが、ＲＡＭ６２から読み出される。さらに、
ステップＳ６３では、これらが、注目チェーンが存在す
るフレームのフレーム番号と対応付けられ、ＲＡＭ６４
に出力されて記憶される。

【０１３０】その後、ステップＳ６４に進み、前フレー
ムに存在するチェーンへの接続処理が行われる。即ち、
ステップＳ６４では、前フレームに存在するチェーンで
あって、注目チェーンと接続すべきものが検出され、注
目チェーンと接続される。

【０１３１】具体的には、図３０に示すように、まず最
初に、ステップＳ７１において、注目チェーンが類似度
を有する、前フレームに存在するチェーン（有類似度チ
ェーン）のうち、後フレーム（前フレームから見た後フ
レーム（従って、注目フレーム））のチェーンに対する
類似度が最も高いチェーンが注目チェーンとなっている
ものがあるかどうかが判定される。ステップＳ７１にお
いて、前フレームの有類似度チェーンのうち、後フレー
ムのチェーンに対する類似度が最も高いチェーンが注目
チェーンとなっているものがないと判定された場合、ス
テップＳ７２乃至Ｓ７４をスキップして、ステップＳ７
５に進む。

【０１３２】また、ステップＳ７１において、前フレー
ムの有類似度チェーンのうち、後フレームのチェーンに
対する類似度が最も高いチェーンが注目チェーンとなっ
ているものがあると判定された場合、ステップＳ７２に
進み、そのチェーン（有類似度チェーン）の、注目チェ
ーンに対する類似度が所定の閾値Ｔ以上となっているも
のが、注目チェーンと接続される可能性のあるチェーン
としての接続候補チェーンとされる。なお、注目チェー
ンに対する類似度が所定の閾値Ｔ以上となっているチェ
ーンが、前フレームに複数存在する場合は、そのすべて
が接続候補チェーンとされる。また、注目チェーンに対
する類似度が所定の閾値Ｔ以上となっているチェーン
が、前フレームに存在しない場合、図３０には図示して
いないが、ステップＳ７３およびＳ７４をスキップし
て、ステップＳ７５に進む。

【０１３３】接続候補チェーンを得た後、ステップＳ７
３において、接続候補チェーンが、注目チェーンに対す
る接続条件を満足するかどうかが判定される。即ち、ス
テップＳ７３では、例えば注目チェーンの接続候補チェ
ーンに対する類似度（接続候補チェーンが複数存在する
場合には、それらの接続候補チェーンに対する類似度の
合計）が所定の閾値Ｔ以上である場合、接続候補チェー
ンが、注目チェーンに対する接続条件を満足すると判定
される。

【０１３４】ステップＳ７３において、接続候補チェー
ンが、上述のような注目チェーンに対する接続条件を満
足しないと判定された場合、ステップＳ７４をスキップ
して、ステップＳ７５に進む。また、ステップＳ７３に
おいて、接続候補チェーンが、上述のような注目チェー
ンに対する接続条件を満足すると判定された場合（以
下、適宜、接続条件を満足する接続候補チェーンを、接
続チェーンという）、ステップＳ７４に進み、ＲＡＭ６
２を参照しながら、接続チェーンが存在するフレーム番
号に、その接続チェーンのチェーン番号、前フレームへ
の動きベクトル、および後フレームへの動きベクトルが
対応付けられ、ＲＡＭ６４に出力されて記憶される。な
お、接続チェーンが複数ある場合には、すべての接続チ
ェーンに関する情報が、ＲＡＭ６４に記憶される。これ
により、注目チェーンと、接続チェーンとが接続され
る。即ち、注目チェーンと、接続チェーンとは、同一の
輪郭を表すものとして対応付けられる。

【０１３５】以上のステップＳ７１乃至Ｓ７４の処理に
よれば、例えば図３１に示すように、前フレームに、注
目チェーンＣを、いわば分割したような３つのチェーン
Ｄ１，Ｄ２，Ｄ３が存在する場合において、注目チェー
ンＣの、チェーンＤ１，Ｄ２，Ｄ３それぞれに対する類
似度ＳＣ１，ＳＣ２，ＳＣ３の総和が閾値Ｔ以上であ
り、かつ、チェーンＤ１，Ｄ２，Ｄ３それぞれの、チェ
ーンＣに対する類似度ＳＤ１，ＳＤ２，ＳＤ３がいずれ
も閾値Ｔ以上であるときには、注目チェーンＣと、チェ
ーンＤ１，Ｄ２，Ｄ３それぞれとが接続されることにな
る。

【０１３６】図３０に戻り、ステップＳ７５では、注目
チェーンに対する類似度が閾値Ｔ以上のチェーンＺが、
前フレームに存在するかどうかが判定される。ステップ
Ｓ７５において、注目チェーンに対する類似度が閾値Ｔ
以上のチェーンＺが、前フレームに存在しないと判定さ
れた場合、ステップＳ７６乃至Ｓ７９をスキップして、
ステップＳ８０に進む。また、ステップＳ７５におい
て、注目チェーンに対する類似度が閾値Ｔ以上のチェー
ンＺが、前フレームに存在すると判定された場合、ステ
ップＳ７６に進み、そのチェーンＺに対する類似度を有
する、後フレーム（チェーンＺから見た後フレーム（従
って、注目フレーム））に存在するチェーンのうち、前
フレームのチェーンに対する類似度が最も高いチェーン
がチェーンＺとなっているものがあるかどうかが、ＲＡ
Ｍ６２を参照して判定される。

【０１３７】ステップＳ７６において、チェーンＺから
見て後フレームに存在するチェーンのうち、前フレーム
のチェーンに対する類似度が最も高いチェーンがチェー
ンＺとなっているものがないと判定された場合、ステッ
プＳ７７乃至Ｓ７９をスキップして、ステップＳ８０に
進む。

【０１３８】また、ステップＳ７６において、チェーン
Ｚから見て後フレームに存在するチェーンのうち、前フ
レームのチェーンに対する類似度が最も高いチェーンが
チェーンＺとなっているものがあると判定された場合、
ステップＳ７７に進み、そのチェーンのうちの、チェー
ンＺに対する類似度が所定の閾値Ｔ以上となっているも
のが、チェーンＺと接続される可能性のあるチェーンと
しての接続候補チェーンとされる。なお、チェーンＺに
対する類似度が所定の閾値Ｔ以上となっているチェーン
が、後フレームに複数存在する場合は、そのすべてが接
続候補チェーンとされる。また、チェーンＺに対する類
似度が所定の閾値Ｔ以上となっているチェーンが、後フ
レームに存在しない場合、図３０には図示していない
が、ステップＳ７８およびＳ７９をスキップして、ステ
ップＳ８０に進む。

【０１３９】そして、ステップＳ７８に進み、接続候補
チェーンが、チェーンＺに対する接続条件を満足するか
どうかが判定される。即ち、ステップＳ７８では、例え
ばチェーンＺの接続候補チェーンに対する類似度（接続
候補チェーンが複数存在する場合には、それらの接続候
補チェーンに対する類似度の合計）が所定の閾値Ｔ以上
である場合、接続候補チェーンが、チェーンＺに対する
接続条件を満足すると判定される。

【０１４０】ステップＳ７８において、接続候補チェー
ンが、上述のようなチェーンＺに対する接続条件を満足
しないと判定された場合、ステップＳ７９をスキップし
て、ステップＳ８０に進む。また、ステップＳ７８にお
いて、接続候補チェーンが、上述のようなチェーンＺに
対する接続条件を満足すると判定された場合（以下、適
宜、この接続条件を満足する接続候補チェーンも、接続
チェーンという）、ステップＳ７９に進み、ＲＡＭ６２
を参照しながら、接続チェーンが存在するフレーム番号
に、その接続チェーンのチェーン番号、前フレームへの
動きベクトル、および後フレームへの動きベクトルが対
応付けられ、ＲＡＭ６４に出力されて記憶される。

【０１４１】なお、接続チェーンが複数ある場合には、
すべての接続チェーンに関する情報が、ＲＡＭ６４に記
憶される。また、接続チェーンには、注目チェーンが含
まれるが、注目チェーンに関する情報ついては、図２９
のステップＳ２９で、既にＲＡＭ６４に書き込まれてい
るので、ステップＳ７９では、その書き込みは行われな
い。

【０１４２】さらに、ステップＳ７９では、ＲＡＭ６２
を参照しながら、チェーンＺが存在するフレーム番号
に、そのチェーンＺのチェーン番号、前フレームへの動
きベクトル、および後フレームへの動きベクトルが対応
付けられ、ＲＡＭ６４に出力されて記憶される。

【０１４３】これにより、チェーンＺと、接続チェーン
とが接続される。即ち、チェーンＺと、接続チェーンと
は、同一の輪郭を表すものとして対応付けられる。

【０１４４】以上のステップＳ７５乃至Ｓ７９の処理に
よれば、例えば図３２に示すように、注目チェーンＤ１
が、前フレームに存在するチェーンＺを分割したような
複数のチェーンＤ１，Ｄ２，Ｄ３のうちの１つである場
合において、チェーンＺの、チェーンＤ１，Ｄ２，Ｄ３
それぞれに対する類似度ＳＺ１，ＳＺ２，ＳＺ３の総和
が閾値Ｔ以上であり、かつ、注目チェーン（図３２の実
施例では、チェーンＤ１）を含むチェーンＤ１，Ｄ２，
Ｄ３それぞれの、チェーンＺに対する類似度ＳＤ１，Ｓ
Ｄ２，ＳＤ３がいずれも閾値Ｔ以上であるときには、チ
ェーンＺと、注目チェーンを含むチェーンＤ１，Ｄ２，
Ｄ３それぞれとが接続されることになる。

【０１４５】ステップＳ７９の処理後は、ステップＳ８
０に進み、ＲＡＭ６４に記憶されたチェーン（注目フレ
ームに存在するチェーンを除く）のうち、後述するステ
ップＳ８１で、まだ、注目チェーンとされていないもの
が存在するかどうかが判定される。ステップＳ８０にお
いて、ＲＡＭ６４に記憶されたチェーンのうち、まだ、
注目チェーンとされていないものが存在すると判定され
た場合、ステップＳ８１に進み、まだ、注目チェーンと
されていないものが新たな注目チェーンとされ、ステッ
プＳ７１に戻る。従って、この場合、新たな注目チェー
ンについて、ステップＳ７１以降の処理が繰り返され、
これにより、上述したような木構造が、図２９のステッ
プＳ６２で注目チェーンとされたチェーンのフレームよ
り前（時間的に前）のフレームに存在するチェーンを対
象として構成されていく。

【０１４６】また、ステップＳ８０において、ＲＡＭ６
４に記憶されたチェーンのうち、まだ、注目チェーンと
されていないものが存在しないと判定された場合、即
ち、ＲＡＭ６４に記憶されたチェーンがすべて注目チェ
ーンとされた場合、ステップＳ８２に進み、この前フレ
ームに存在するチェーンへの接続処理が開始されたとき
に、注目チェーンとされていたチェーンが、再度、注目
チェーンとされる。そして、前フレームに存在するチェ
ーンへの接続処理を終了し、図２９のステップＳ６５に
進む。

【０１４７】ステップＳ６５では、後フレームに存在す
るチェーンへの接続処理が行われる。即ち、ステップＳ
６５では、後フレームに存在するチェーンであって、注
目チェーンと接続すべきものが検出され、注目チェーン
と接続される。

【０１４８】ここで、図３３のフローチャートは、後フ
レームに存在するチェーンへの接続処理の詳細を示して
いる。同図に示すように、後フレームに存在するチェー
ンへの接続処理では、ステップＳ９１乃至Ｓ１０２にお
いて、図３０のステップＳ７１乃至Ｓ８２における場合
とそれぞれ同様の処理が行われる。但し、図３０のステ
ップＳ７１乃至Ｓ８２では、前フレームに存在するチェ
ーンを対象として、注目チェーンとの接続が行われる
が、図３３では、後フレームに存在するチェーンを対象
として、注目チェーンとの接続が行われるようになされ
ている。

【０１４９】従って、ステップＳ９１乃至Ｓ９４の処理
によれば、例えば図３４に示すように、後フレームに、
注目チェーンＣを、いわば分割したような３つのチェー
ンＤ１，Ｄ２，Ｄ３が存在する場合において、注目チェ
ーンＣの、チェーンＤ１，Ｄ２，Ｄ３それぞれに対する
類似度ＳＣ１，ＳＣ２，ＳＣ３の総和が閾値Ｔ以上であ
り、かつ、チェーンＤ１，Ｄ２，Ｄ３それぞれの、チェ
ーンＣに対する類似度ＳＤ１，ＳＤ２，ＳＤ３がいずれ
も閾値Ｔ以上であるときには、注目チェーンＣと、チェ
ーンＤ１，Ｄ２，Ｄ３それぞれとが接続される。

【０１５０】また、ステップＳ９５乃至Ｓ９９の処理に
よれば、例えば図３５に示すように、注目チェーンＤ１
が、後フレームに存在するチェーンＺを分割したような
複数のチェーンＤ１，Ｄ２，Ｄ３のうちの１つである場
合において、チェーンＺの、チェーンＤ１，Ｄ２，Ｄ３
それぞれに対する類似度ＳＺ１，ＳＺ２，ＳＺ３の総和
が閾値Ｔ以上であり、かつ、注目チェーン（図３５の実
施例では、チェーンＤ１）を含むチェーンＤ１，Ｄ２，
Ｄ３それぞれの、チェーンＺに対する類似度ＳＤ１，Ｓ
Ｄ２，ＳＤ３がいずれも閾値Ｔ以上であるときには、チ
ェーンＺと、注目チェーンを含むチェーンＤ１，Ｄ２，
Ｄ３それぞれとが接続される。

【０１５１】これにより、類似するチェーンを節点とす
る木構造が、図２９のステップＳ６２で注目チェーンと
されたチェーンのフレームより後（時間的に後）のフレ
ームに存在するチェーンを対象として構成される。

【０１５２】図２９に戻り、ステップＳ６５における後
フレームに存在するチェーンへの接続処理が終了する
と、ステップＳ６６に進み、ＲＡＭ６４に記憶されたチ
ェーンのうち、注目チェーンの存在するフレーム、即
ち、注目フレームに存在するチェーン（但し、注目チェ
ーンを除く）であって、まだ、注目チェーンとされてい
ないものがあるかどうかが判定される。ステップＳ６６
において、ＲＡＭ６４に記憶されたチェーンのうち、注
目フレームに存在するチェーンであって、注目チェーン
とされていないものがないと判定された場合、ステップ
Ｓ６７をスキップして、ステップＳ６８に進む。また、
ステップＳ６６において、ＲＡＭ６４に記憶されたチェ
ーンのうち、注目フレームに存在するチェーンであっ
て、まだ、注目チェーンとされていないものがあると判
定された場合、ステップＳ６７に進み、そのチェーンを
注目チェーンとして、図３３の後フレームに存在するチ
ェーンへの接続処理が行われる。

【０１５３】なお、ＲＡＭ６４に記憶されたチェーンの
うち、注目フレームに存在するチェーンであって、ま
だ、注目チェーンとされていないものが、複数存在する
場合、ステップＳ６７では、その複数のチェーンを、注
目チェーンに順次変えて、後フレームに存在するチェー
ンへの接続処理が行われる。

【０１５４】その後、ステップＳ６８に進み、ステップ
Ｓ６６における場合と同様に、ＲＡＭ６４に記憶された
チェーンのうち、注目チェーンの存在するフレーム、即
ち、注目フレームに存在するチェーン（但し、注目チェ
ーンを除く）であって、まだ、注目チェーンとされてい
ないものがあるかどうかが判定される。

【０１５５】ステップＳ６８において、ＲＡＭ６４に記
憶されたチェーンのうち、注目フレームに存在するチェ
ーンであって、注目チェーンとされていないものがない
と判定された場合、ステップＳ６９をスキップして、ス
テップＳ７０に進む。また、ステップＳ６８において、
ＲＡＭ６４に記憶されたチェーンのうち、注目フレーム
に存在するチェーンであって、まだ、注目チェーンとさ
れていないものがあると判定された場合、ステップＳ６
９に進み、そのチェーンを注目チェーンとして、図３０
の前フレームに存在するチェーンへの接続処理を行うこ
とで、ＲＡＭ６４に記憶されるチェーンが存在するかど
うかが判定される。

【０１５６】ステップＳ６９において、ＲＡＭ６４に記
憶されたチェーンのうち、注目フレームに存在するチェ
ーンであって、まだ、注目チェーンとされていないもの
を注目チェーンとして、前フレームに存在するチェーン
への接続処理を行うことで、ＲＡＭ６４に記憶されるチ
ェーンが存在すると判定された場合、そのチェーン（Ｒ
ＡＭ６４に記憶されたチェーンのうち、注目フレームに
存在するチェーンであって、まだ、注目チェーンとされ
ていないもの）が注目チェーンとされ、ステップＳ６４
に戻る。なお、そのようなチェーンが複数ある場合に
は、そのうちのいずれかが注目チェーンとされる。

【０１５７】一方、ステップＳ６９において、ＲＡＭ６
４に記憶されたチェーンのうち、注目フレームに存在す
るチェーンであって、まだ、注目チェーンとされていな
いものを注目チェーンとして、前フレームに存在するチ
ェーンへの接続処理を行うことで、ＲＡＭ６４に記憶さ
れるチェーンが存在しないと判定された場合、ステップ
Ｓ７０に進み、ＲＡＭ６４に記憶された情報が、セレク
ト多重化回路１６（図１）に出力される。

【０１５８】即ち、ステップＳ７０では、例えば、ＲＡ
Ｍ６４に記憶された情報のうち、チェーンの数の最も少
ないフレーム（以下、適宜、最少フレームという）に存
在するチェーンを基本チェーンとすることが決定され、
最少フレームのフレーム番号、そのフレーム番号と対応
付けられているチェーン番号、最少フレームから最も小
さいフレーム番号のフレームまでのフレーム数、そのフ
レーム間の前フレームへの動きベクトルすべて、最少フ
レームから最も大きいフレーム番号のフレームまでのフ
レーム数、そのフレーム間の後フレームへの動きベクト
ルが、ＲＡＭ６４から読み出されて（但し、上述のフレ
ーム数は、動きベクトルの数に等しいので、その動きベ
クトルの数をカウントすることで認識される）、セレク
ト多重化回路１６（図１）に出力される。

【０１５９】なお、最少フレームから最も小さいフレー
ム番号のフレームまでのフレーム数、そのフレーム間の
前フレームへの動きベクトルすべて、最少フレームから
最も大きいフレーム番号のフレームまでのフレーム数、
そのフレーム間の後フレームへの動きベクトルは、多重
化されて出力される。

【０１６０】以上の処理により、ＲＡＭ６２_nの記憶内
容が、例えば図３６に示すようなものであった場合、Ｒ
ＡＭ６４には、図３７（Ａ）に示すような情報が記憶さ
れ、さらに、多チェーン接続回路６３からは、図３７
（Ｂ）に示すような情報が出力される。即ち、例えば、
いま、図３７に示した第８フレームに存在するチェーン
＃５６が、ステップＳ６２において注目チェーンとされ
たとすると、ステップＳ６３において、そのフレーム番
号８、チェーン番号５６、後フレームへの動きベクトル
（５，３）、および前フレームへの動きベクトル（−
２，０）が、ＲＡＭ４４に記憶される（図３７
（Ａ））。

【０１６１】そして、チェーン＃５６が類似度を有する
前フレーム（第７フレーム）のチェーン＃３６および＃
１５１については、いずれも、後フレームのチェーンに
対する類似度が最も高いチェーンが、注目チェーンであ
るチェーン＃５６になっている（図３６）。いま、閾値
Ｔを、例えば０．８とすると、チェーン＃３６または＃
１５１の、チェーン＃５６に対する類似度は、それぞれ
０．９７または０．９１であり、また、チェーン＃５６
の、チェーン＃３６または＃１５１に対する類似度は、
それぞれ０．９６または０．９１であるから、チェーン
＃３６および＃１５１の、チェーン＃５６に対する類似
度は、いずれも閾値Ｔ以上であり、さらに、チェーン＃
５６の、チェーン＃３６または＃１５１それぞれに対す
る類似度の合計も所定の閾値Ｔ以上である。

【０１６２】従って、第７フレームのチェーン＃３６，
＃１５１のフレーム番号７、チェーン番号３６，１５
１、後フレームへの動きベクトル（０，−２）、および
前フレームの動きベクトル（３，９），（３，１）は、
ステップＳ７９においてＲＡＭ６４に記憶される（図３
７（Ａ））。

【０１６３】ＲＡＭ６４に記憶されたチェーン＃３６お
よび＃１５１は、ステップＳ８１において新たな注目チ
ェーンとされるが、このチェーン＃３６または＃１５１
が類似度を有する前フレーム（第６フレーム）のチェー
ンは存在しないから（図３６）、ステップ８２で、チェ
ーン＃５６が再び注目チェーンとされる。

【０１６４】そして、チェーン＃５６が類似度を有する
後フレーム（第９フレーム）のチェーン＃２４および＃
２５については、いずれも、前フレームのチェーンに対
する類似度が最も高いチェーンが、注目チェーンである
チェーン＃５６になっている（図３６）。さらに、この
場合、チェーン＃２４または＃２５の、チェーン＃５６
に対する類似度は、それぞれ０．９５または０．９０で
あり、また、チェーン＃５６の、チェーン＃２４または
＃２５に対する類似度は、それぞれ０．９９または０．
９２であるから、チェーン＃２４および＃２５の、チェ
ーン＃５６に対する類似度は、いずれも閾値Ｔ以上であ
り、さらに、チェーン＃５６の、チェーン＃２４または
＃２５それぞれに対する類似度の合計も所定の閾値Ｔ以
上である。

【０１６５】従って、第９フレームのチェーン＃２４，
＃２５のフレーム番号９、チェーン番号２４，２５、後
フレームへの動きベクトル（１，−１）、および前フレ
ームの動きベクトル（４，０），（４，２）は、ステッ
プＳ９９においてＲＡＭ６４に記憶される（図３７
（Ａ））。

【０１６６】ＲＡＭ６４に記憶されたチェーン＃２４お
よび＃２５は、ステップＳ１０１において新たな注目チ
ェーンとされるが、このチェーン＃２４または＃２５が
類似度を有する後フレーム（第１０フレーム）のチェー
ンは存在しないから（図３６）、ステップＳ１０２で、
チェーン＃５６が再び注目チェーンとされる。

【０１６７】そして、この段階で、ＲＡＭ６４に記憶さ
れたチェーンのうち、注目フレームである第８フレーム
には、注目チェーンとされていないチェーンが存在しな
いから、いままで、ＲＡＭ６４に記憶された情報のう
ち、最少フレームに存在するチェーンを基本チェーンと
して、その基本チェーンを、いわば中心とする情報が、
ステップＳ７０において読み出されて出力される。即
ち、最少フレームのフレーム番号、基本チェーンのチェ
ーン番号、最少フレームから最も小さいフレーム番号の
フレームまでのフレーム数、そのフレーム間の前フレー
ムへの動きベクトルすべて、最少フレームから最も大き
いフレーム番号のフレームまでのフレーム数、そのフレ
ーム間の後フレームへの動きベクトルすべてが、ステッ
プＳ７０において読み出されて出力される。

【０１６８】具体的には、例えばＲＡＭ６４の記憶内容
が、図３７（Ａ）に示すようなものであった場合、チェ
ーンの数の最も少ないフレームは、第８フレームである
から、これが最少フレームとなり、従って、図３７
（Ｂ）に示すように、最少フレームのフレーム番号であ
る８、そのフレーム番号に対応付けられているチェーン
番号である５６、最少フレームから最も小さいフレーム
番号７のフレームまでのフレーム数である１、そのフレ
ーム間の前フレームへの動きベクトルである（−２，
０）、最少フレームから最も大きいフレーム番号９のフ
レームまでのフレーム数である１、そのフレーム間の後
フレームへの動きベクトルである（５，３）が、類似チ
ェーン検出回路１５（多チェーン接続回路６３）からセ
レクト多重化回路１６に出力される。

【０１６９】そして、セレクト多重化回路１６では、上
述したように、類似チェーン検出回路１５から受信した
フレーム番号ｎのフレームに存在するチェーンについて
のチェーン符号化データが、チェーン番号を参照するこ
とによりＲＡＭ１４_nから読み出され、そのチェーン符
号化データと、類似チェーン検出回路１５からのフレー
ム数および動きベクトルすべてとが多重化されることに
より、多重化チェーン符号化データとされて出力され
る。

【０１７０】即ち、例えば、いま、図３８に示すよう
に、第ｎ−３フレームに存在する１つのチェーン、第ｎ
−２フレームに存在する２つのチェーン、第ｎ−１に存
在する３つのチェーン、第ｎフレームに存在する１つの
チェーン、第ｎ＋１フレームに存在する１つのチェー
ン、第ｎ＋２フレームに存在する２つのチェーンが、第
ｎフレームに存在するチェーンを基本チェーンとして接
続されたとすると、セレクト多重化回路１６からは、第
ｎフレームの基本チェーンについてのチェーン符号化デ
ータ、第ｎフレームから第ｎ−３フレームまでのフレー
ム数とその間の前フレームへの動きベクトル、および第
ｎフレームから第ｎ＋２フレームまでのフレーム数とそ
の間の後フレームへの動きベクトルを多重化したものが
出力される。

【０１７１】従って、図２７の類似チェーン検出回路１
５を用いた場合も、図１７の類似チェーン検出回路１５
を用いた場合と同様に、複数フレーム間にわたって接続
されたチェーン（時間方向に見た場合に、類似している
チェーン）は、あるチェーン（基本チェーン）について
のチェーン符号化データと、そのチェーンを移動（動き
補償）して他のチェーンを復元するための動きベクトル
とにされて出力されるので、時間方向の冗長度を低下さ
せることができ、その結果、画像の圧縮効率を向上させ
ることができる。

【０１７２】さらに、図２７の類似チェーン検出回路１
５によれば、図３１、図３２、図３４、および図３５に
示したように、あるフレームでは、１つのチェーンとな
っているが、他のフレームにおいて、何らかの原因で、
複数に分割されているチェーンとが接続されるので、図
１７における場合に比較して、さらなる圧縮率の向上を
図ることが可能となる。

【０１７３】なお、上述の場合においては、ＲＡＭ６４
に記憶されたチェーンの数の最も少ないフレームに存在
するチェーンを、基本チェーンとするようにしたが、そ
の他のフレームのチェーンを基本チェーンとすることも
可能である。但し、基本チェーンについては、上述のよ
うに、チェーン符号化データが出力されるため、圧縮率
向上の観点からは、チェーン符号化データが少ない方が
好ましい。従って、上述したように、チェーンの数の最
も少ないフレームに存在するチェーンを、基本チェーン
とするのが好ましい。

【０１７４】また、図３８に示した実施例では、例えば
第ｎ−１フレームには、３つのチェーンが存在するが、
このような場合、この３つのチェーンそれぞれから、そ
の前フレーム（第ｎ−２フレーム）または後フレームへ
の動きベクトルが異なることがある。このような場合、
第ｎ−１フレームに存在する３つのチェーンそれぞれか
ら、前フレームへの動きベクトル、即ち、３つの動きベ
クトルを出力するようにしても良いが、圧縮率向上の観
点からは、第ｎ−１フレームに存在する３つのチェーン
それぞれから、前フレームへの動きベクトルの、例えば
平均値やそのうちの１つを、第ｎ−１フレームに存在す
る３つのチェーンそれぞれから、前フレームへの動きベ
クトルの、いわば代表値として出力するようにするのが
好ましい。

【０１７５】次に、図３９は、図１の画像符号化装置か
ら出力される多重化チェーン符号化データを、元の動画
像に復号する画像復号化装置の一実施例の構成を示して
いる。図１の画像符号化装置より出力された多重化チェ
ーン符号化データは、伝送路を介して、あるいは、記録
媒体１８から再生されてバッファ７１に供給されるよう
になされており、バッファ７１では、その多重化チェー
ン符号化データが一旦記憶されるようになされている。
分離回路７２は、バッファ７１に記憶された多重化チェ
ーン符号化データを読み出し、それから、チェーン符号
化データと、動きベクトルとを抽出するようになされて
いる。なお、チェーン符号化データまたは動きベクトル
は、チェーン復号化回路７３または動き補償回路７７に
それぞれ出力されるようになされている。

【０１７６】チェーン復号化回路７３は、チェーン符号
化データをチェーン復号化することにより、特徴点と、
その特徴点における量子化係数とにし、画像構成回路７
４に出力するようになされている。画像構成回路７５
は、チェーン復号化回路７３からの特徴点および量子化
係数から元の画像を構成（再構成）するようになされて
いる。即ち、画像構成回路７５は、量子化係数を逆量子
化することで画像データを求め、その画像データを、特
徴点に配置することで、基本チェーンを構成する画像デ
ータ（以下、適宜、基本チェーンデータという）を生成
するようになされている。この基本チェーンデータは、
セレクタ７５および動き補償回路７７に出力されるよう
になされている。

【０１７７】セレクタ７５は、画像構成回路７４から出
力される基本チェーンデータを、フレームメモリとして
構成されているＲＡＭ７６₁乃至７６_Nのうちのいずれか
に出力して記憶させるようになされている。さらに、セ
レクタ７５は、動き補償回路７７から出力される画像デ
ータについても同様に、ＲＡＭ７６₁乃至７６_Nのうちの
いずれかに出力して記憶させるようになされている。こ
れにより、ＲＡＭ７６_nには、図１の類似チェーン検出
回路１５の処理単位であるＮフレームの画像データのう
ち、第ｎフレームのものが記憶されるようになされてい
る。動き補償回路７７は、画像構成回路７４から出力さ
れる基本チェーンデータに対し、分離回路７２より出力
される動きベクトルにしたがった動き補償を施し、セレ
クタ７５に出力するようになされている。読み出し回路
７８は、ＲＡＭ７６₁乃至７６_NにＮフレーム分の画像デ
ータが記憶されると、その画像データを、ＲＡＭ７６₁
乃至７６_Nの順番で読み出し、図示せぬモニタに出力し
て表示させるようになされている。

【０１７８】次に、図４０のフローチャートを参照し
て、その動作について説明する。バッファ７１に入力さ
れた多重化チェーン符号化データは、そこに一旦記憶さ
れる。すると、分離回路７２では、バッファ７１に記憶
された多重化チェーン符号化データが読み出され、ステ
ップＳ１１１においてチェーン符号化データと動きベク
トルとに分離される。そして、チェーン符号化データは
チェーン復号化回路７３に、動きベクトルは動き補償回
路７７にそれぞれ出力される。

【０１７９】チェーン復号化回路７３では、ステップＳ
１１２において、チェーン符号化データがチェーン復号
化され、これにより特徴点と量子化係数とにされ、画像
構成回路７４に出力される。画像構成回路７４では、ス
テップＳ１１３において、チェーン復号化回路７３から
の特徴点および量子化係数（復号データ）に基づいて、
上述したようにして基本チェーンデータ（基本チェーン
を構成する画像データ）が生成される。この基本チェー
ンデータは、セレクタ７５に供給される。

【０１８０】ここで、画像符号化装置の類似チェーン検
出回路１５が、図１７に示したように構成される場合、
上述したように、チェーン符号化データは、最小フレー
ムに存在するチェーンについてのものである。そこで、
この場合、セレクタ７５は、画像構成回路７４から基本
チェーンデータを受信した場合、その基本チェーンデー
タを、最小フレームのフレーム番号ｎをサフィックスと
して有するＲＡＭ７６_nに出力して記憶させる。なお、
図１のセレクト多重化回路１６では、多重化チェーン符
号化データに、最小フレームのフレーム番号が含められ
るようになされており、図３９には、図示していない
が、この最小フレームのフレーム番号は、分離回路７２
において、多重化チェーン符号化データから分離され、
セレクタ７５に供給されるようになされている。そし
て、セレクタ７５では、分離回路７２からのフレーム番
号に基づいて、基本チェーンデータを、ＲＡＭ７６（Ｒ
ＡＭ７６₁乃至７６_Nのいずれか）に記憶させるようにな
されている。

【０１８１】また、画像構成回路７４より出力された基
本チェーンデータは、セレクタ７５だけでなく、動き補
償回路７７にも供給される。動き補償回路７７では、画
像構成回路７４より基本チェーンデータを受信すると、
ステップＳ１１４において、その基本チェーンデータに
対し、分離回路７２より出力される動きベクトルにした
がった動き補償が施される。

【０１８２】即ち、分離回路７２より出力される動きベ
クトルは、基本チェーンと接続されたチェーンが存在す
るフレームの間の、後フレームへの動きベクトルである
から、動き補償回路７７では、基本チェーンデータが、
分離回路７２からの最初の動きベクトルにしたがって動
き補償されることで、基本チェーンが存在するフレーム
の次のフレーム（後フレーム）に存在するチェーンの画
像データ（以下、適宜、第１のチェーンデータという）
が生成される。さらに、動き補償回路７７では、分離回
路７２からの２番目の動きベクトルにしたがって、第１
のチェーンデータが動き補償されることで、基本チェー
ンが存在するフレームの次のフレームの、さらに次のフ
レーム（従って、第１のチェーンデータが存在するフレ
ームの後フレーム）に存在するチェーンの画像データ
（以下、適宜、第２のチェーンデータという）が生成さ
れる。

【０１８３】以下、同様にして、動き補償回路７７で
は、分離回路７２から出力される動きベクトルすべてを
用いて動き補償処理が行われる。従って、分離回路７２
から出力された動きベクトルの数がＭ個であった場合
（但し、Ｍ＜Ｎ）、動き補償回路７７では、第１乃至第
Ｍのチェーンデータが生成されることになる。

【０１８４】動き補償回路７７で生成された第１乃至第
Ｍのチェーンデータは、セレクタ７５に順次出力され
る。セレクタ７５は、第１乃至第Ｍのチェーンデータを
受信すると、それを、基本チェーンデータを記憶させた
ＲＡＭ７６_n以降のＲＡＭ７６に順次記憶させる。即
ち、セレクタ７５は、第１乃至第Ｍのチェーンデータ
を、ＲＡＭ７６_n+1乃至７６_n+Mに順次記憶させる。

【０１８５】以上のようにして、Ｎフレームに存在する
チェーンすべてについてのデータが、ＲＡＭ７６₁乃至
７６_Nに記憶されると、読み出し回路７８は、ＲＡＭ７
６₁乃至７６_Nからデータを順次読み出し、モニタに出力
して表示させる。

【０１８６】なお、ＲＡＭ７６₁乃至７６_Nは、例えば１
フレーム分の画像データを記憶することのできる２つの
バンクから構成されている。そして、あるＮフレーム分
の画像データについて、一方のバンクに、その画像デー
タが記憶され、その読み出しが行われている場合には、
次のＮフレーム分の画像データについては、他方のバン
クに、その画像データが記憶され、一方のバンクに記憶
された画像データの読み出しが終了すると、他方のバン
クに記憶された画像データの読み出しが開始されるとと
もに、一方のバンクに、さらに次のＮフレーム分の画像
データが記憶されるようになされている。以上のような
バンク切り換えにより、モニタには、画像が途切れるこ
となく、連続して表示されるようになされている。

【０１８７】図４１は、図２６で説明したようにして、
第ｎフレームに存在するチェーンＣＨ_nを基本チェーン
として得られた多重化チェーン符号化データを復号して
得られる復号画像を示している。基本チェーンである第
ｎフレームのチェーンＣＨ_nは、多重化チェーン符号化
データに含まれるチェーン符号化データをチェーン復号
化することで得ることができる。また、第ｎ＋１フレー
ムのチェーンＣＨ_n+1は、復号されたチェーンＣＨ_nを、
多重化チェーン符号化データに含まれる、チェーンＣＨ
_nから後フレームへの動きベクトルにしたがって動き補
償することで得ることができる。さらに、第ｎ＋２フレ
ームのチェーンＣＨ_n+2は、チェーンＣＨ_nを動き補償す
ることで得られたチェーンＣＨ_n+1を、多重化チェーン
符号化データに含まれる、チェーンＣＨ_n+1から後フレ
ームへの動きベクトルにしたがって動き補償することで
得ることができる。以下、同様にして、基本チェーンＣ
Ｈ_nと接続された第ＮフレームのチェーンＣＨ_Nまでを得
ることができる。

【０１８８】次に、画像符号化装置の類似チェーン検出
回路１５が、図２７に示したように構成される場合、上
述したように、チェーン符号化データは、最少フレーム
に存在するチェーンについてのものである。そこで、こ
の場合、セレクタ７５は、画像構成回路７４から基本チ
ェーンデータを受信した場合、その基本チェーンデータ
を、最少フレームのフレーム番号ｎをサフィックスとし
て有するＲＡＭ７６_nに出力して記憶させる。なお、図
１のセレクト多重化回路１６では、多重化チェーン符号
化データに、最少フレームのフレーム番号が含められる
ようになされており、図３９には、図示していないが、
この最少フレームのフレーム番号は、分離回路７２にお
いて、多重化チェーン符号化データから分離され、セレ
クタ７５に供給されるようになされている。そして、セ
レクタ７５では、分離回路７２からのフレーム番号に基
づいて、基本チェーンデータを、ＲＡＭ７６（ＲＡＭ７
６₁乃至７６_Nのいずれか）に記憶させるようになされて
いる。

【０１８９】また、画像構成回路７４より出力された基
本チェーンデータは、セレクタ７５だけでなく、動き補
償回路７７にも供給される。動き補償回路７７では、画
像構成回路７４より基本チェーンデータを受信すると、
ステップＳ１１４において、その基本チェーンデータに
対し、分離回路７２より出力される動きベクトルにした
がった動き補償が施される。

【０１９０】即ち、分離回路７２からは、基本チェーン
と接続されたチェーンが存在する、時間的に最も前のフ
レームまでの間の、前フレームへの動きベクトル（以
下、適宜、前方向動きベクトルという）、および基本チ
ェーンと接続されたチェーンが存在する、時間的に最も
後のフレームまでの間の、後フレームへの動きベクトル
（以下、適宜、後方向動きベクトルという）が出力され
る。そこで、動き補償回路７７では、基本チェーンデー
タが、分離回路７２からの最初の前方向動きベクトルに
したがって動き補償されることで、基本チェーンが存在
するフレームの前フレームに存在するチェーンの画像デ
ータ（以下、適宜、第１の前フレームチェーンデータと
いう）が生成される。さらに、動き補償回路７７では、
分離回路７２からの２番目の前方向動きベクトルにした
がって、第１の前フレームチェーンデータが動き補償さ
れることで、基本チェーンが存在するフレームの前のフ
レームの、さらに前のフレーム（従って、第１の前フレ
ームチェーンデータが存在するフレームの前フレーム）
に存在するチェーンの画像データ（以下、適宜、第２の
前フレームチェーンデータという）が生成される。

【０１９１】以下、同様にして、動き補償回路７７で
は、分離回路７２から出力される前方向動きベクトルす
べてを用いて動き補償処理が行われる。従って、分離回
路７２から出力された前方向動きベクトルの数がＭ１個
であった場合（但し、Ｍ１＜Ｎ）、動き補償回路７７で
は、第１乃至第Ｍ１の前フレームチェーンデータが生成
されることになる。

【０１９２】さらに、動き補償回路７７では、基本チェ
ーンデータが、分離回路７２からの最初の後方向動きベ
クトルにしたがって動き補償されることで、基本チェー
ンが存在するフレームの後フレームに存在するチェーン
の画像データ（以下、適宜、第１の後フレームチェーン
データという）が生成される。さらに、動き補償回路７
７では、分離回路７２からの２番目の後方向動きベクト
ルにしたがって、第１の後フレームチェーンデータが動
き補償されることで、基本チェーンが存在するフレーム
の後のフレームの、さらに後のフレーム（従って、第１
の後フレームチェーンデータが存在するフレームの後フ
レーム）に存在するチェーンの画像データ（以下、適
宜、第２の後フレームチェーンデータという）が生成さ
れる。

【０１９３】以下、同様にして、動き補償回路７７で
は、分離回路７２から出力される後方向動きベクトルす
べてを用いて動き補償処理が行われる。従って、分離回
路７２から出力された後方向動きベクトルの数がＭ２個
であった場合（但し、Ｍ２＜Ｎ）、動き補償回路７７で
は、第１乃至第Ｍ２の後フレームチェーンデータが生成
されることになる。

【０１９４】なお、画像符号化装置の類似チェーン検出
回路１５が、図２７に示したように構成される場合、図
３７（Ｂ）および図３８で説明したことから、多重化チ
ェーン符号化データには、前方向動きベクトルの数Ｍ１
および後方向動きベクトルの数Ｍ２が含まれる。この数
Ｍ１およびＭ２は、分離回路７２において、多重化チェ
ーン符号化データから分離され、動き補償回路７７に供
給されるようになされており、これにより、動き補償回
路７７では、前方向動きベクトルによる動き補償処理が
Ｍ１回だけ行われ、さらに、後方向動きベクトルによる
動き補償処理がＭ２回だけ行われるようになされてい
る。

【０１９５】動き補償回路７７で生成された第１乃至第
Ｍ１の前フレームチェーンデータおよび第１乃至第Ｍ２
の後フレームチェーンデータは、セレクタ７５に出力さ
れる。セレクタ７５は、第１乃至第Ｍ１の前フレームチ
ェーンデータおよび第１乃至第Ｍ２の後フレームのチェ
ーンデータを受信すると、第１乃至第Ｍ１の前フレーム
チェーンデータを、ＲＡＭ７６_n-1乃至７６_n-M1にそれ
ぞれ記憶させるとともに、第１乃至第Ｍ２の後フレーム
のチェーンデータを、ＲＡＭ７６_n+1乃至７６_{n +M2}にそ
れぞれ記憶させる。

【０１９６】これにより、ＲＡＭ７６_n-M1乃至７６_n+M2
には、連続するＭ１＋Ｍ２＋１フレームのチェーンデー
タ（第ｎ−Ｍ１フレーム乃至第ｎ＋Ｍ２フレームのチェ
ーンデータそれぞれ）が記憶されることになる。

【０１９７】以上のようにして、Ｎフレームに存在する
チェーンすべてについてのデータが、ＲＡＭ７６₁乃至
７６_Nに記憶されると、上述したように、読み出し回路
７８によって、ＲＡＭ７６₁乃至７６_Nからデータが順次
読み出され、モニタに出力されて表示される。

【０１９８】図４２は、図３８で説明したようにして、
第ｎフレームに存在するチェーンＣＨ_nを基本チェーン
として得られた多重化チェーン符号化データを復号して
得られる復号画像を示している。基本チェーンである第
ｎフレームのチェーンＣＨ_nは、多重化チェーン符号化
データに含まれるチェーン符号化データをチェーン復号
化することで得ることができる。また、第ｎ−１１フレ
ームのチェーンＣＨ_{n- 1}は、復号されたチェーンＣＨ
_nを、多重化チェーン符号化データに含まれる、チェー
ンＣＨ_nから前フレームへの動きベクトルにしたがって
動き補償することで得ることができる。さらに、第ｎ−
２フレームのチェーンＣＨ_n-2は、チェーンＣＨ_nを動き
補償することで得られたチェーンＣＨ_n-1を、多重化チ
ェーン符号化データに含まれる、チェーンＣＨ_n-1から
前フレームへの動きベクトルにしたがって動き補償する
ことで得ることができる。同様に、第ｎ−３フレームの
チェーンＣＨ_n-3は、チェーンＣＨ_n-1を動き補償するこ
とで得られたチェーンＣＨ_n-2を、多重化チェーン符号
化データに含まれる、チェーンＣＨ_n-2から前フレーム
への動きベクトルにしたがって動き補償することで得る
ことができる。

【０１９９】また、第ｎ＋１フレームのチェーンＣＨ
_n+1は、復号されたチェーンＣＨ_nを、多重化チェーン符
号化データに含まれる、チェーンＣＨ_nから後フレーム
への動きベクトルにしたがって動き補償することで得る
ことができる。さらに、第ｎ＋２フレームのチェーンＣ
Ｈ_n+2は、チェーンＣＨ_nを動き補償することで得られた
チェーンＣＨ_n+1を、多重化チェーン符号化データに含
まれる、チェーンＣＨ_n+1から後フレームへの動きベク
トルにしたがって動き補償することで得ることができ
る。

【０２００】なお、元の画像に含まれるチェーンは、図
３８に示したように、第ｎ−２フレームについては２つ
に、第ｎ−１フレームについては３つに、第ｎ＋２フレ
ームについては２つに、それぞれ分割されているが、図
３９の画像復号化装置によれば、基本チェーンを基にし
た動き補償処理が行われるので、図４２に示したよう
に、第ｎ−２フレームの２つのチェーン、第ｎ−１フレ
ームの３つのチェーン、および第ｎ＋２フレームの２つ
のチェーンは、いずれも１つのチェーンに復号されるこ
とになる。しかしながら、このように復号化されるチェ
ーンは、同一の輪郭を構成するものとして、画像符号化
装置において接続されたものであるから、１つのチェー
ンとして復号化されても、視覚上問題が生じることはな
く、むしろ、この場合、何らかの原因で、２以上に分割
されてしまったチェーンが、１つのチェーンとして表示
されることになるので、画像の輪郭を明確にすることが
できる。

【０２０１】次に、図４３は、本発明を適用した画像符
号化装置の第２実施例の構成を示している。なお、図
中、図１における場合と対応する部分については、同一
の符号を付してある。即ち、この画像符号化装置は、類
似チェーン検出回路１５またはセレクト多重化回路１６
に代えて、チェーン置換回路１１５またはセレクト多重
化回路１１６が設けられている他は、図１の画像符号化
装置と同様に構成されている。

【０２０２】チェーン置換回路１１５では、第１フレー
ムに存在する、あるチェーン（従って、ＲＡＭ１４₁に
記憶された、あるチェーン）が、そのチェーンから後フ
レームへの動きベクトルにしたがって移動され、その移
動後のチェーン（以下、適宜、移動チェーンという）
の、後フレームにおける視覚的な重要性を表す重要度
（Visual Significant）が算出される。さらに、チェー
ン置換回路１１５は、重要度が所定の閾値Ｔ１以上であ
るとき、後フレームに存在するチェーンのうち、移動チ
ェーンの周囲にあるものを、その移動チェーンに置き換
え、置き換え後のチェーンを用い、その後フレームを対
象にして同様の処理を行うことを、重要度が閾値Ｔ１以
上とならなくなるまで、または第Ｎフレームついてまで
行う。そして、その後、チェーン置換回路１１５は、最
初に用いた第１フレームのチェーンに対応するチェーン
符号化データ、および第１フレームからチェーンの置き
換えを行った最後のフレームまでの間の後フレームへの
動きベクトルを、セレクト多重化回路１１６に多重化さ
せるものとして決定し、最初に用いた第１フレームのチ
ェーンのチェーン番号、チェーンの置き換えを行ったフ
レーム数（これは、次に述べる後フレームへの動きベク
トルの数に等しい）、および第１フレームからチェーン
の置き換えを行った最後のフレームまでの間の後フレー
ムへの動きベクトルを、セレクト多重化回路１１６に出
力する。

【０２０３】セレクト多重化回路１１６は、チェーン置
換回路１１５からのチェーン番号に対応するチェーンに
ついてのチェーン符号化データを、ＲＡＭ１４₁から読
み出し、そのチェーン符号化データ、並びにチェーン置
換回路１１５からの動きベクトルおよびその数を多重化
することで、多重化チェーン符号化データとし、バッフ
ァ１７に出力する。

【０２０４】図４４は、図４３のチェーン置換回路１１
５の構成例を示している。チェーンマップ回路１２１
は、ＲＡＭ１４₁乃至１４_Nに、Ｎフレーム分のチェーン
符号化データが記憶されると、ＲＡＭ１４₁から第１フ
レームのチェーン符号化データを読み出し、ＲＡＭ（Ch
ain RAM）１２２に供給して記憶させる。さらに、チェ
ーンマップ回路１２１は、図１８のチェーンマップ回路
５１における場合と同様にして、第２乃至第Ｎフレーム
に存在するチェーンについてのビットマップを、ＲＡＭ
（Map RAM）１２３₁乃至１２３_N-1に、それぞれ展開す
る。

【０２０５】なお、図１８のチェーンマップ回路５１で
は、図２０を参照して説明したように、チェーンを、チ
ェーン番号によるビットマップとして展開し、さらにチ
ェーンが存在しない位置（画素）に対応するアドレスに
は−１を格納するようにしたが、図４４のチェーンマッ
プ回路１２１では、チェーンが存在する位置に対応する
アドレスには、例えば１が格納され、チェーンが存在し
ない位置に対応するアドレスには、例えば０が格納され
るようになされている。即ち、第ｎフレームに（但し、
この場合、ｎ≠１）、例えば図１９に示したように、チ
ェーンＣＨ１乃至ＣＨ５が存在する場合、ＲＡＭ１２３
_n-1には、図４５に示すようなビットマップが展開され
る。

【０２０６】ＲＡＭ１２２に、第１フレームのチェーン
符号化データが記憶され、ＲＡＭ１２３₁乃至１２３_N-1
に、第２乃至第Ｎフレームのチェーンについてのビット
マップがそれぞれ展開されると、置換回路１２４では、
ＲＡＭ１２２に記憶された第１フレームに存在するチェ
ーンそれぞれについて、図４６のフローチャートにした
がった処理が行われる。

【０２０７】即ち、まず最初に、ステップＳ１２１にお
いて、ＲＡＭ（動きベクトルＲＡＭ）１２６が初期化さ
れ、ステップＳ１２２に進み、第１フレーム（先頭フレ
ーム）が注目フレームとされて、ステップＳ１２３に進
む。ステップＳ１２３では、注目フレーム、即ち第１フ
レームに存在する、あるチェーン（注目チェーン）から
後フレームへの動きベクトルが計算される。なお、ステ
ップＳ１２３における動きベクトルの計算は、置換回路
１２４が、その動きベクトルの計算に必要なデータを、
ＲＡＭ１２２，１２３（ＲＡＭ１２３₁乃至１２３_Nのい
ずれか）から読み出し、動きベクトル算出回路１２５に
出力することによって、動きベクトル算出回路１２５に
行わせるようになされている。

【０２０８】動きベクトルの計算後、ステップＳ１２４
に進み、注目チェーンの、後フレームでの重要度（視覚
的重要度）が算出される。即ち、ステップＳ１２４で
は、例えば図４７（Ａ）に示すように、注目チェーン
が、ステップＳ１２３で求められた動きベクトルにした
がって移動され、後フレームにおいて、同図（Ｂ）に示
すように、その移動後の注目チェーン（移動チェーン）
を構成する画素（図中、斜線を付してある部分）それぞ
れを中心とするＬ１×Ｌ２画素の範囲（図中、点線で囲
んである範囲）に存在する特徴点の数が求められる。さ
らに、ステップＳ１２４では、後フレームにおいて、移
動チェーンを構成する各画素を中心とするＬ１×Ｌ２画
素の範囲に存在する特徴点の数が算出された後、その平
均値（移動チェーンを構成する各画素を中心とするＬ１
×Ｌ２画素の範囲に存在する特徴点の数の総和を、移動
チェーンを構成する画素数で除算したもの）が求めら
れ、これが、重要度とされる。

【０２０９】ここで、ＲＡＭ１２３_nにおいては、図４
５で説明したように、第ｎ＋１フレームに存在するチェ
ーンを構成する画素（特徴点）に対応するアドレスに１
が格納され、それ以外のアドレスには０が格納されてい
るから、いま注目フレームとなっているフレームを、第
ｎフレームとすると、ステップＳ１２４では、ＲＡＭ１
２３_nに記憶されているビットマップを参照し、そのう
ちの、移動チェーンを構成する各画素を中心とするＬ１
×Ｌ２画素（例えば、Ｌ１＝Ｌ２＝３）の範囲に対応す
るアドレスの格納値の総和を計算することで、後フレー
ム（この場合、第ｎ＋１フレーム）において、移動チェ
ーンを構成する各画素を中心とするＬ１×Ｌ２画素の範
囲に存在する特徴点の数が算出される。

【０２１０】なお、以上のようにして算出される重要度
は、後フレームにおいて、移動チェーンを構成する各画
素を中心とするＬ１×Ｌ２画素の範囲に存在する特徴点
の密度ということができるが、重要度としては、このよ
うな特徴点の密度以外の量を採用することが可能であ
る。

【０２１１】即ち、例えば、後フレームにおいて、移動
チェーンを構成する画素のうち、それを中心とするＬ１
×Ｌ２画素の範囲に特徴点が存在するものの数を、移動
チェーンを構成する画素数で除算し、その結果得られる
値を、重要度とすることが可能である。また、例えば、
ＲＡＭ１２３₁乃至１２３_N-1に、第２乃至第Ｎフレーム
の画像データを記憶させるようにし、それを参照して、
後フレームにおいて、移動チェーンを構成する各画素に
対応する画素それぞれのエッジ強度（後フレームにおけ
る移動チェーン上に存在する画素それぞれのエッジ強
度）を求め、そのエッジ強度の平均値を、重要度とする
ことなども可能である。

【０２１２】重要度の算出後は、ステップＳ１２５に進
み、その重要度が所定の閾値Ｔ１以上であるかどうかが
判定される。ステップＳ１２５において、重要度が所定
の閾値Ｔ１以上でないと判定された場合、後フレームに
は、注目チェーンに接続されるチェーン（移動後の注目
チェーンと（ほぼ）重なるチェーン）が存在しないとし
て、ステップＳ１２６乃至Ｓ１２８をスキップして、ス
テップＳ１２９に進む。また、ステップＳ１２５におい
て、重要度が所定の閾値Ｔ１以上であると判定された場
合、即ち、後フレームに、注目チェーンと接続されるチ
ェーンが存在する場合、ステップＳ１２６に進み、その
後フレームのチェーンが、移動チェーンに置き換えられ
る（この置き換えというのは、置換回路１２４におい
て、注目チェーンと接続されるべき後フレームのチェー
ンが、移動チェーンに置き換えて認識されるようになる
ということである）。

【０２１３】さらに、ステップＳ１２６では、ステップ
Ｓ１２３で算出された後フレームへの動きベクトルが、
ＲＡＭ１２６に記憶され、ステップＳ１２７に進む。な
お、ステップＳ１２６では、ＲＡＭ１２３の更新処理も
行われる。即ち、後フレームに、注目チェーンと接続さ
れるべきチェーンが存在するとして、そのチェーンが、
移動チェーンに置き換えられた場合、以後、そのチェー
ンを処理対象とする必要はない。そこで、ステップＳ１
２６では、例えば、いま、注目フレームが第ｎフレーム
であるとすると、ＲＡＭ１２３_nに記憶された第ｎ＋１
フレームのビットマップのうち、移動チェーンを構成す
る各画素を中心とするＬ１×Ｌ２画素の範囲に対応する
アドレスの格納値が、すべて０にされる。これにより、
第ｎ＋１フレームにおいて、移動チェーンを構成する各
画素を中心とするＬ１×Ｌ２画素の範囲にある特徴点
は、いわば消去される。

【０２１４】その後、ステップＳ１２７において、後フ
レームが新たに注目フレームとされ、ステップＳ１２８
に進み、注目フレームが第Ｎフレーム（最終フレーム）
であるかどうかが判定される。ステップＳ１２８におい
て、注目フレームが第Ｎフレームでないと判定された場
合、ステップＳ１２３に戻り、ステップＳ１２７で新た
に注目フレームとされたフレームに存在し、ステップＳ
１２６で置き換えられたチェーン（移動チェーン）を注
目チェーンとして、ステップＳ１２３以下の処理が行わ
れる。

【０２１５】また、ステップＳ１２８において、新たな
注目フレームが第Ｎフレームであると判定された場合、
ステップＳ１２９に進み、ステップＳ１２２で注目フレ
ームとされたフレーム（従って、第１フレーム）のチェ
ーンであって、最初に注目チェーンとされたチェーンが
基本チェーンとされ、そのチェーン番号（これは、チェ
ーン符号化データが、ＲＡＭ１２２に記憶されるとき
に、各チェーンに対して付されるようになされてい
る）、ＲＡＭ１２６に記憶された動きベクトル（後フレ
ームへの動きベクトル）、およびその動きベクトルの数
が、セレクト多重化回路１１６に出力され、処理を終了
する。

【０２１６】なお、上述したように、図４６に示した処
理は、第１フレームに存在するチェーンすべてについて
行われる。

【０２１７】セレクト多重化回路１１６では、上述した
ように、第１フレームに存在する基本チェーンについて
のチェーン符号化データが、ＲＡＭ１４₁から読み出さ
れ、そのチェーン符号化データと、チェーン置換回路１
１５からの動きベクトルおよびその数とが多重化される
ことにより、多重化チェーン符号化データとされて出力
される。

【０２１８】即ち、例えば、いま、図４８に示すよう
に、第１乃至第Ｎフレームにそれぞれ存在するチェーン
ＣＨ₁乃至ＣＨ_Nが接続されたとすると、セレクト多重化
回路１１６からは、チェーンＣＨ₁についてのチェーン
符号化データと、チェーンＣＨ₁からチェーンＣＨ_N-1ま
での後フレームへの動きベクトルおよびその数Ｎ−１と
を多重化したものが出力される。

【０２１９】従って、第１フレームの注目チェーンと置
き換え（接続）可能なチェーンは、その注目チェーン
（基本チェーン）についてのチェーン符号化データと、
そのチェーンを移動（動き補償）して他のチェーンを復
元するための動きベクトルとにされて出力されるので、
やはり、時間方向の冗長度を低下させることができ、そ
の結果、画像の圧縮効率を向上させることができる。

【０２２０】なお、図４４のＲＡＭ１２２にも、ＲＡＭ
１２３₁乃至１２３_N-1における場合と同様に、第１フレ
ームのビットマップを展開するようにすることが可能で
ある。但し、この場合、ＲＡＭ１２２は、１フレーム分
のビットマップを記憶することのできるフレームメモリ
とする必要があり、従って、記憶容量の大きなものとす
る必要がある。これに対し、上述したように、ＲＡＭ１
２２に、第１フレームに存在するチェーン符号化データ
を記憶させるようにした場合には、通常、１フレーム分
のチェーン符号化データは、１フレーム分のビットマッ
プよりデータ量の少ないものであるから、ＲＡＭ１２２
も記憶容量の小さいものを用いることが可能となる。

【０２２１】ところで、図４３の画像符号化装置によれ
ば、上述したように、画像データの圧縮効率の向上を図
ることができるが、第１フレームに存在するチェーンに
ついてのみ、図４６に示した処理が行われるため、第２
フレーム以降のフレームで、初めてチェーンが現れた場
合（例えば、第２フレーム以降のフレームでシーンが変
わった場合など）には、そのチェーンについての情報
は、セレクト多重化回路１１６から出力されず、従っ
て、復号側において、そのチェーンを復号することが困
難となる。

【０２２２】そこで、図４９は、本発明を適用した画像
符号化装置の第３実施例の構成を示している。なお、図
中、図４３における場合と対応する部分については、同
一の符号を付してある。即ち、この画像符号化装置は、
チェーン置換回路１１５またはセレクト多重化回路１１
６に代えて、チェーン置換回路２１５またはセレクト多
重化回路２１６がそれぞれ設けられている他は、図４３
の画像符号化装置と同様に構成されている。

【０２２３】チェーン置換回路２１５は、図４３のチェ
ーン置換回路１１５と同様の処理を、第１フレームに存
在するチェーンだけでなく、第２フレーム以降のフレー
ムに存在するチェーンも対象として行い、後述するよう
に、フレーム番号、チェーン番号、動きベクトル、およ
びその動きベクトルの数を、セレクト多重化回路２１６
に出力する。

【０２２４】セレクト多重化回路２１６は、チェーン置
換回路２１５からのチェーン番号に対応するチェーンに
ついてのチェーン符号化データを、同じくチェーン置換
回路２１５からのフレーム番号ｎをサフィックスとする
ＲＡＭ１４_nから読み出し、そのチェーン符号化デー
タ、並びにチェーン置換回路２１５からの動きベクトル
およびその数を多重化することで、多重化チェーン符号
化データとし、バッファ１７に出力する。

【０２２５】図５０は、図４９のチェーン置換回路２１
５の構成例を示している。なお、図中、図４４のチェー
ン置換回路１１５における場合と対応する部分について
は、同一の符号を付してある。即ち、このチェーン置換
回路２１５は、置換回路１２４に代えて、置換回路１３
２が設けられ、さらに、新規チェーン符号化回路１３１
₁乃至１３１_N-1およびチェーン復号化回路１３３₁乃至
１３３_N-1が新たに設けられている他は、図４４のチェ
ーン置換回路１１５と同様に構成されている。

【０２２６】以上のように構成されるチェーン置換回路
２１５では、図４４における場合と同様にして、ＲＡＭ
１２２に、第１フレームのチェーン符号化データが記憶
され、ＲＡＭ１２３₁乃至１２３_N-1に、第２乃至第Ｎフ
レームのチェーンについてのビットマップがそれぞれ展
開されると、置換回路１３２において、図５１のフロー
チャートにしたがった処理が行われる。

【０２２７】即ち、まず最初に、ステップＳ１３１にお
いて、フレーム数をカウントするための変数ｎに初期値
としての１がセットされ、ステップＳ１３２に進み、後
述するような第ｎフレームに基づく置換処理が行われ
る。そして、その第ｎフレームに基づく置換処理が終了
すると、ステップＳ１３３において、変数ｎが１だけイ
ンクリメントされ、ステップＳ１３４に進み、変数ｎ
が、処理単位のフレーム数であるＮ以下であるかどうか
が判定される。ステップＳ１３４において、変数ｎがＮ
以下であると判定された場合、ステップＳ１３２に戻
り、再度、第ｎフレームに基づく置換処理が行われる。
また、ステップＳ１３４において、変数ｎがＮ以下でな
いと判定された場合、処理を終了する。

【０２２８】次に、図５２は、図５１の第ｎフレームに
基づく置換処理の詳細を示すフローチャートである。こ
の第ｎフレームに基づく置換処理では、ステップＳ１４
１乃至Ｓ１４８において、ステップＳ１４２で、第１フ
レームではなく、第ｎフレームが注目フレームとされる
ことを除き、図４６のステップＳ１２１乃至Ｓ１２８に
おける場合とそれぞれ同様の処理が行われる。

【０２２９】ここで、第１フレームに存在するチェーン
についてのチェーン符号化データは、ＲＡＭ１２２に記
憶されているので、第１フレームに存在するチェーンに
ついては、ＲＡＭ１２２に記憶されているチェーン符号
化データにより、第１フレームに存在するチェーンそれ
ぞれを認識し、例えばステップＳ１４３において、その
チェーンからの後フレームへの動きベクトルを算出する
ことができるが、第２フレーム以降のフレームに存在す
るチェーンについては、チェーンを構成する特徴点の位
置に対応するアドレスの格納値を１としたビットマップ
が、ＲＡＭ１２３1乃至１２３N-1に記憶されているだけ
なので、第２フレーム以降のフレームに存在するチェー
ンを認識するには、置換回路１３２において、注目フレ
ームのビットマップが展開されているＲＡＭ１２３の記
憶内容をスキャンして、１が連続する部分をチェーンと
して再構成する必要があり、処理に時間を要することに
なる。

【０２３０】さらに、ＲＡＭ１２３₁乃至１２３_N-1に記
憶されているビットマップは、ステップＳ１４６におい
て、図４６で説明したステップＳ１２６における場合と
同様に更新されるが、置換回路１３２では、その更新後
のチェーンを認識する必要がある。

【０２３１】そこで、ステップＳ１４２において、第２
フレーム以降のフレームが注目フレームとされた場合、
置換回路１３２は、次のようにして、その注目フレーム
とされたフレームに存在するチェーンを認識するように
なされている。

【０２３２】即ち、例えば、いま、ステップＳ１４２に
おいて、第ｎフレームが注目フレームとされたとすると
（但し、ここでは、ｎは２以上Ｎ以下の整数とする）、
図２で説明したチェーン符号化回路１２と同様に構成さ
れる新規チェーン符号化回路１３１_n-1に制御信号を出
力する。チェーン符号化回路１３１_n-1は、置換回路１
３２から制御信号を受信すると、チェーン復号化回路１
３３_n-1を制御し、これにより、ＲＡＭ１４_nから第ｎフ
レームのチェーン符号化データを読み出させ、チェーン
復号化させる。チェーン復号化回路１３３_n-1によって
チェーン復号化されることにより得られた第ｎフレーム
の画像データは、新規チェーン符号化回路１３１_n-1に
供給され、そこで、ＲＡＭ１２３_n-1の記憶内容を参照
しながら、再度チェーン符号化される。

【０２３３】即ち、チェーン復号化回路１３３_n-1から
は、第ｎフレームの画像データの他、第ｎフレームのチ
ェーン符号化データを復号することにより得られる第ｎ
フレームの特徴点も、新規チェーン符号化回路１３１
_n-1に供給されるようになされており、新規チェーン符
号化回路１３１_n-1では、チェーン復号化回路１３３_n-1
からの第ｎフレームの特徴点であって、その特徴点に対
応するＲＡＭ１２３_n-1のアドレスの格納値が１になっ
ている点（画素）を、いわば真の特徴点として、チェー
ン復号化回路１３３_n-1から供給される第ｎフレームの
画像データがチェーン符号化され、その結果得られるチ
ェーン符号化データが、置換回路１３２に出力される。

【０２３４】従って、新規チェーン符号化回路１３１
_n-1より出力される第ｎフレームのチェーン符号化デー
タは、ＲＡＭ１３１_n-1の更新内容を反映したものとな
る。

【０２３５】置換回路１３２では、以上のようにして、
新規チェーン符号化回路１３１_n-1から供給される、Ｒ
ＡＭ１３１_n-1の更新内容を反映した第ｎフレームのチ
ェーン符号化データに基づいて、第ｎフレームに存在す
るチェーンが認識される。

【０２３６】なお、置換回路１３２では、第ｎフレーム
に存在するチェーンを認識する際に、そのチェーンに対
し、ユニークなチェーン番号を付すようになされてい
る。

【０２３７】そして、置換回路１３２では、ステップＳ
１４９において、図４６のステップＳ１２９における場
合と同様に、最初に注目チェーンとされたチェーンのチ
ェーン番号、ＲＡＭ１２６に記憶された動きベクトル
（後フレームへの動きベクトル）、およびその動きベク
トルの数が、セレクト多重化回路２１６に出力され、さ
らに、最初に注目チェーンとされたチェーンが存在する
フレーム（ステップＳ１４２で注目フレームとされたフ
レーム）のフレーム番号も、セレクト多重化回路２１６
に出力される。

【０２３８】なお、図５２に示した処理は、ステップＳ
１４２で注目フレームとされる第ｎフレームに存在する
チェーンすべてについて行われる。

【０２３９】セレクト多重化回路２１６では、上述した
ように、チェーン置換回路２１５から出力されるフレー
ム番号ｎをサフィックスとするＲＡＭ１４nから、同じ
くチェーン置換回路２１５から出力されるチェーン番号
に対応するチェーン（基本チェーン）についてのチェー
ン符号化データが読み出され、そのチェーン符号化デー
タと、チェーン置換回路２１５からの動きベクトルおよ
びその数とが多重化されることにより、多重化チェーン
符号化データとされて出力される。

【０２４０】即ち、例えば、いま、図５３に示すよう
に、第１乃至第Ｎフレームにそれぞれ存在するチェーン
ＣＨ₁乃至ＣＨ_Nが接続されたとすると、セレクト多重化
回路２１６からは、図４８における場合と同様に、チェ
ーンＣＨ₁についてのチェーン符号化データと、チェー
ンＣＨ₁からチェーンＣＨ_N-1までの後フレームへの動き
ベクトルおよびその数Ｎ−１とを多重化したものが出力
される。さらに、同図に示すように、第２フレームで、
初めてチェーンＣＨ₂’が現れた場合でも、図５１のス
テップＳ１３２において「第２フレームに基づく置換処
理」が行われることによって、チェーンＣＨ₂’は、そ
れと接続されるべきチェーン（図５３の実施例において
は、第３フレームのチェーンＣＨ₃’）と接続され、そ
の結果、セレクト多重化回路２１６からは、チェーンＣ
Ｈ₂’についてのチェーン符号化データと、チェーンＣ
Ｈ₂’の後フレームへの動きベクトルおよびその数１と
を多重化したものも出力される。

【０２４１】従って、この場合、第２フレーム以降のフ
レームで、初めてチェーンが現れたとしても、復号側に
おいて、そのチェーンを復号することが可能となる。

【０２４２】なお、図４３および図４９の画像符号化装
置から出力された多重化チェーン符号化データは、図３
９で説明した画像復号化装置によって、上述した場合と
同様にして復号することができる。

【０２４３】但し、その復号画像は、図５４および図５
５に示すようなものとなる。即ち、例えば、図５４
（Ａ）に示すように、元の画像において、第ｎフレーム
に、ある１つのチェーンが存在し、後フレームに、その
チェーンを分割したような３つのチェーンが存在する場
合に、第ｎフレームのチェーンが基本チェーンとされ、
後フレームの３つのチェーンと接続された（置き換えら
れた）とき、画像復号化装置では、基本チェーンを動き
補償することで、後フレームのチェーンが復号されるた
め、後フレームの３つのチェーンは、同図（Ｂ）に示す
ように、１つのチェーンとして復号される。

【０２４４】また、例えば、図５５（Ａ）に示すよう
に、元の画像において、第ｎフレームに、３つのチェー
ンが存在し、後フレームに、そのチェーンをつなぎ合わ
せたような１つのチェーンが存在する場合に、第ｎフレ
ームの３つのチェーンそれぞれが基本チェーンとされ、
後フレームの１のチェーンと接続された（置き換えられ
た）とき、画像復号化装置では、基本チェーンを動き補
償することで、後フレームのチェーンが復号されるた
め、後フレームの１つのチェーンは、同図（Ｂ）に示す
ように、３つのチェーンとして復号される。

【０２４５】以上、本発明を適用した画像符号化装置お
よび画像復号化装置について説明したが、このような画
像符号化装置および画像復号化装置は、例えばビデオテ
ープレコーダや、テレビ会議システムなどに組み込むこ
とが可能である。

【０２４６】なお、本実施例においては、画像データを
チェーン符号化するようにしたが、本発明は、その他、
画像データを、チェーン符号化以外の構造抽出符号化す
る場合に適用可能である。

【０２４７】

【発明の効果】以上の如く、本発明の画像符号化装置お
よび画像符号化方法によれば、動画像の特徴点に関する
データが符号化され、その結果得られるデータと、特徴
点を結ぶチェーンの動きベクトルとが多重化されるの
で、発生符号量を低減することが可能となる。

【０２４８】本発明の画像復号化装置および画像復号化
方法によれば、伝送データから、動画像の特徴点に関す
るデータを符号化した符号化データと、特徴点を結ぶチ
ェーンの動きベクトルとが抽出され、符号化データが復
号される。そして、その結果得られる復号化データが、
動きベクトルにしたがって動き補償される。従って、動
画像の特徴点に関するデータを符号化した符号化データ
と、特徴点を結ぶチェーンの動きベクトルとを含む伝送
データから、復号画像を得ることが可能となる。

【０２４９】本発明の記録媒体によれば、そこに、動画
像の特徴点に関するデータを符号化した符号化データ
と、特徴点を結ぶチェーンの動きベクトルとを含んたデ
ータが記録されているので、長時間の動画を記録するこ
とが可能となる。

【図面の簡単な説明】

【図１】本発明を適用した画像符号化装置の第１実施例
の構成を示すブロック図である。

【図２】図１のチェーン符号化回路１２の構成例を示す
ブロック図である。

【図３】図２の係数フレームバッファ２１の記憶内容を
説明するための図である。

【図４】図２の方向探索器２３の動作を説明するフロー
チャートである。

【図５】図４のフローチャートに続くフローチャートで
ある。

【図６】図２のＲＯＭ３０および３１の記憶内容を示す
図である。

【図７】図２のアドレス発生器３２が出力するアドレス
を説明するための図である。

【図８】図２のＲＯＭ３３の記憶内容を示す図である。

【図９】図２のＲＯＭ３３から出力される方向データが
表す方向を示す図である。

【図１０】図４のフローチャートに続くフローチャート
である。

【図１１】図２の方向探索器２３からの有効データ選択
信号、ＲＯＭ３３からの方向データ、およびラッチ回路
３４からの前方向データの出力タイミングを示すタイミ
ングチャートである。

【図１２】図２の方向変化信号発生器３５から出力され
る方向変化データを説明するための図である。

【図１３】図２の方向変化信号発生器３５が記憶してい
る前方向データおよび方向データと、方向変化データと
の対応表を示す図である。

【図１４】図２の方向変化信号発生器３５が記憶してい
る前方向データおよび方向データと、方向変化データと
の対応表を示す図である。

【図１５】図２の方向変化信号が出力する方向変化デー
タに割り当てられている符号語を示す図である。

【図１６】図２のセレクタ３６から出力されるデータを
説明するための図である。

【図１７】図１の類似チェーン検出回路１５の構成例を
示すブロック図である。

【図１８】図１７の類似度検知回路４１の構成例を示す
ブロック図である。

【図１９】画像上に存在するチェーンの例を示す図であ
る。

【図２０】第ｎフレームの画像上に、図１９に示すよう
なチェーンが存在する場合の、図１８のＲＡＭ５２_nの
記憶内容を示す図である。

【図２１】図１８の類似度計算回路５３の動作を説明す
るフローチャートである。

【図２２】図２１のフローチャートに示す処理を説明す
るための図である。

【図２３】図１７のＲＡＭ４２_nの記憶内容を示す図で
ある。

【図２４】図１７のチェーン接続回路４３の動作を説明
するフローチャートである。

【図２５】図２４のフローチャートに示す処理を説明す
るための図である。

【図２６】図１のセレクト多重化回路１６より出力され
る多重化チェーン符号化データを説明するための図であ
る。

【図２７】図１の類似チェーン検出回路１５の他の構成
例を示すブロック図である。

【図２８】図２７のＲＡＭ６２_nの記憶内容を示す図で
ある。

【図２９】図２７のチェーン接続回路６３の動作を説明
するフローチャートである。

【図３０】図２９のステップＳ６４の処理の詳細を説明
するフローチャートである。

【図３１】図３０のステップＳ７１乃至Ｓ７４の処理を
説明するための図である。

【図３２】図３０のステップＳ７５乃至Ｓ７９の処理を
説明するための図である。

【図３３】図２９のステップＳ６５の処理の詳細を説明
するフローチャートである。

【図３４】図３３のステップＳ９１乃至Ｓ９４の処理を
説明するための図である。

【図３５】図３３のステップＳ９５乃至Ｓ９９の処理を
説明するための図である。

【図３６】図２９のフローチャートに示す処理を説明す
るための図である。

【図３７】図２９のフローチャートに示す処理を説明す
るための図である。

【図３８】図１のセレクト多重化回路１６より出力され
る多重化チェーン符号化データを説明するための図であ
る。

【図３９】本発明を適用した画像復号化装置の一実施例
の構成を示すブロック図である。

【図４０】図３９の画像復号化装置の動作を説明するた
めのフローチャートである。

【図４１】図３９の画像復号化装置より出力される復号
画像を説明するための図である。

【図４２】図３９の画像復号化装置より出力される復号
画像を説明するための図である。

【図４３】本発明を適用した画像符号化装置の第２実施
例の構成を示すブロック図である。

【図４４】図４３のチェーン置換回路１１５の構成例を
示すブロック図である。

【図４５】図４４のＲＡＭ１２３_nの記憶内容を示す図
である。

【図４６】図４４の置換回路１２４の動作を説明するフ
ローチャートである。

【図４７】図４６のステップＳ１２４の処理を説明する
ための図である。

【図４８】図４３のセレクト多重化回路１１６より出力
される多重化チェーン符号化データを説明するための図
である。

【図４９】本発明を適用した画像符号化装置の第３実施
例の構成を示すブロック図である。

【図５０】図４９のチェーン置換回路２１５の構成例を
示すブロック図である。

【図５１】図５０の置換回路１３２の動作を説明するフ
ローチャートである。

【図５２】図５１のステップＳ１３２の処理の詳細を説
明するフローチャートである。

【図５３】図４９のセレクト多重化回路２１６より出力
される多重化チェーン符号化データを説明するための図
である。

【図５４】図４３（図４９）の画像符号化装置より出力
された多重化チェーン符号化データを復号して得られる
復号画像を説明するための図である。

【図５５】図４３（図４９）の画像符号化装置より出力
された多重化チェーン符号化データを復号して得られる
復号画像を説明するための図である。

【図５６】従来の画像符号化装置の一例の構成を示すブ
ロック図である。

【符号の説明】

１０ ２次元変化点検出回路 １１ 量子化器 １２ チェーン符号化回路 １３ セレクタ １４₁乃至１４_N ＲＡＭ １５ 類似チェーン検出回路 １６ セレクト多重化回路 １７ バッファ ４１ 類似度検知回路 ４２₁乃至４２_N ＲＡＭ ４３ チェーン接続回路 ４４ ＲＡＭ ５１ チェーンマップ回路 ５２₁乃至５２_N ＲＡＭ ５３ 類似度計算回路 ５４ 動きベクトル算出回路 ６１ 多チェーン類似度検知回路 ６２₁乃至６２_N ＲＡＭ ６３ 多チェーン接続回路 ６４ ＲＡＭ ７１ バッファ ７２ 分離回路 ７３ チェーン復号化回路 ７４ 画像構成回路 ７５ セレクタ ７６₁乃至７６_N ＲＡＭ ７７ 動き補償回路 ７８ 読み出し回路 １１５ チェーン置換回路 １１６ セレクト多重化回路 １２１ チェーンマップ回路 １２２，１２３₁乃至１２３_N ＲＡＭ １２４ 置換回路 １２５ 動きベクトル算出回路 １２６ ＲＡＭ １３１₁乃至１３１_N-1 新規チェーン符号化回路 １３２ 置換回路 １３３₁乃至１３３_N-1 チェーン復号化回路 ２１５ チェーン置換回路 ２１６ セレクト多重化回路

Claims (14)

【特許請求の範囲】
1. 【請求項１】 動画像を符号化する画像符号化装置であ
   って、 前記動画像の特徴点に関する情報を符号化し、符号化デ
   ータを出力する特徴点符号化手段と、 前記特徴点を結ぶチェーンを検出するチェーン検出手段
   と、 前記チェーン検出手段により検出された前記チェーンの
   動きベクトルを検出する動きベクトル検出手段と、 前記特徴点符号化手段より出力された符号化データと、
   前記動きベクトル検出手段により検出された前記動きベ
   クトルとを多重化する多重化手段とを備えることを特徴
   とする画像符号化装置。
2. 【請求項２】 異なるフレームに存在する前記チェーン
   どうしを接続し、その接続結果に基づいて、前記多重化
   手段に多重化させる前記符号化データおよび動きベクト
   ルを決定する決定手段をさらに備えることを特徴とする
   請求項１に記載の画像符号化装置。
3. 【請求項３】 前記決定手段は、隣接するフレームに存
   在する前記チェーンどうしの類似度を算出し、その類似
   度に基づいて、前記チェーンどうしを接続することを特
   徴とする請求項２に記載の画像符号化装置。
4. 【請求項４】 前記決定手段は、複数フレームにわたっ
   て接続された前記チェーンのうちの所定のものに対応す
   る前記符号化データと、前記複数フレームのうちの、隣
   接するフレームの間の前記動きベクトルとを、前記多重
   化手段に多重化させることを特徴とする請求項２に記載
   の画像符号化装置。
5. 【請求項５】 前記決定手段は、所定のフレームに存在
   する、あるチェーンＡの、その所定のフレームに隣接す
   る隣接フレームに存在する他のチェーンＢに対する前記
   類似度を、前記所定のフレームから前記隣接フレームへ
   の前記動きベクトルにしたがって、前記チェーンＡを移
   動し、その移動後の前記チェーンＡを構成する画素のう
   ち、前記隣接フレームに存在する前記チェーンの中で前
   記チェーンＢとの距離が最も近いものの数に基づいて算
   出することを特徴とする請求項３に記載の画像符号化装
   置。
6. 【請求項６】 前記決定手段は、前記チェーンＡの、前
   記チェーンＢに対する前記類似度ＳＡと、前記チェーン
   Ｂの、前記チェーンＡに対する前記類似度ＳＢとを算出
   し、前記類似度ＳＡおよびＳＢがいずれも所定の閾値以
   上であるとき、前記チェーンＡおよびＢを接続すること
   を特徴とする請求項５に記載の画像符号化装置。
7. 【請求項７】 隣接するフレームのうちの一方のフレー
   ムに、チェーンＣが存在し、他方のフレームに、複数の
   チェーンＤ１，Ｄ２，Ｄ３，・・・が存在する場合にお
   いて、 前記決定手段は、前記チェーンＣの、前記複数のチェー
   ンＤ１，Ｄ２，Ｄ３，・・・それぞれに対する前記類似
   度ＳＣ１，ＳＣ２，ＳＣ３，・・・と、前記複数のチェ
   ーンＤ１，Ｄ２，Ｄ３，・・・それぞれの、前記チェー
   ンＣに対する前記類似度ＳＤ１，ＳＤ２，ＳＤ３，・・
   ・とを算出し、前記類似度ＳＤ１，ＳＤ２，ＳＤ３，・
   ・・がいずれも所定の閾値以上であり、かつ前記類似度
   ＳＣ１，ＳＣ２，ＳＣ３，・・・の総和も所定の閾値以
   上であるとき、前記チェーンＣと、前記チェーンＤ１，
   Ｄ２，Ｄ３，・・・それぞれとを接続することを特徴と
   する請求項５に記載の画像符号化装置。
8. 【請求項８】 所定のフレームに存在する、あるチェー
   ンＡを、その所定のフレームから、それに隣接する隣接
   フレームへの前記動きベクトルにしたがって移動し、そ
   の移動後の前記チェーンＡの、前記隣接フレームにおけ
   る視覚的な重要性を表す重要度を算出する重要度算出手
   段と、 前記重要度算出手段により算出された前記重要度が所定
   の閾値以上であるとき、前記隣接フレームに存在する前
   記チェーンのうち、前記移動後のチェーンＡの周囲にあ
   るものを、その移動後のチェーンＡに置き換える置換手
   段とをさらに備え、 前記多重化手段は、前記チェーンＡに対応する前記符号
   化データと、前記置換手段による前記チェーンの置き換
   えがなされた前記隣接フレームへの前記動きベクトルと
   を多重化することを特徴とする請求項１に記載の画像符
   号化装置。
9. 【請求項９】 前記重要度算出手段は、前記隣接フレー
   ムにおける、前記移動後のチェーンＡの周囲に存在する
   前記特徴点に基づいて、前記重要度を算出することを特
   徴とする請求項８に記載の画像符号化装置。
10. 【請求項１０】 前記重要度算出手段は、前記隣接フレ
    ームにおける、前記移動後のチェーンＡ上のエッジ強度
    に基づいて、前記重要度を算出することを特徴とする請
    求項８に記載の画像符号化装置。
11. 【請求項１１】 動画像を符号化する画像符号化方法で
    あって、 前記動画像の特徴点に関するデータを符号化するととも
    に、前記特徴点を結ぶチェーンの動きベクトルを検出
    し、 符号化された前記データと、前記動きベクトルとを多重
    化することを特徴とする画像符号化方法。
12. 【請求項１２】 動画像を復号する画像復号化装置であ
    って、 伝送データから、前記動画像の特徴点に関するデータを
    符号化した符号化データと、前記特徴点を結ぶチェーン
    の動きベクトルとを抽出する抽出手段と、 前記符号化データを復号する復号化手段と、 前記復号化手段の出力を、前記動きベクトルにしたがっ
    て動き補償する動き補償手段とを備えることを特徴とす
    る画像復号化装置。
13. 【請求項１３】 動画像を復号する画像復号化方法であ
    って、 伝送データから、前記動画像の特徴点に関するデータを
    符号化した符号化データと、前記特徴点を結ぶチェーン
    の動きベクトルとを抽出し、 前記符号化データを復号して、復号化データとし、 前記復号化データを、前記動きベクトルにしたがって動
    き補償することを特徴とする画像復号化方法。
14. 【請求項１４】 動画像を符号化したデータが記録され
    ている記録媒体であって、 前記データは、前記動画像の特徴点に関するデータを符
    号化した符号化データと、前記特徴点を結ぶチェーンの
    動きベクトルとを含むことを特徴とする記録媒体。