JP3470326B2

JP3470326B2 - 画像符号化方法

Info

Publication number: JP3470326B2
Application number: JP18241395A
Authority: JP
Inventors: 淳村山
Original assignee: Sony Corp
Current assignee: Sony Corp
Priority date: 1995-07-19
Filing date: 1995-07-19
Publication date: 2003-11-25
Anticipated expiration: 2015-07-19
Also published as: JPH0937247A

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、画像符号化方法に
関する。特に、画像の特徴点に関する情報を符号化して
得られる符号化データのデータ量を低減することができ
るようにした画像符号化方法に関する。

【０００２】

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

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

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

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

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

【０００７】

【発明が解決しようとする課題】ところで、２次元変化
点検出回路１０における特徴点の検出は、基本的に、画
像データに対して微分処理を施すオペレータ（微分オペ
レータ）を用いて行われるが、微分オペレータによれ
ば、画像中の少しの起伏でも特徴点として検出される。
このため、例えば図２９（Ａ）に示すような、僅かな起
伏の連続するようなテクスチャの領域（このような領域
を、以下、適宜、テクスチャ領域という）（図２９
（Ａ）（後述する図２４（Ａ）においても同様）では、
例えば色の濃いまたは淡い部分が、それぞれ輝度の高い
または低い部分を表している）において、同図（Ｂ）に
示すように、多数の点（画素）が、特徴点（図中、斜線
を付してある部分）として検出される課題があった。

【０００８】即ち、テクスチャ領域内部を構成する点
（画素）は、視覚的にはそれほど重要なものではないの
にも拘らず、このような点に関する情報が、チェーン符
号化データに含められるため、そのデータ量が増加する
課題があった。

【０００９】本発明は、このような状況に鑑みてなされ
たものであり、構造抽出符号化方式により画像を圧縮符
号化することにより発生するデータのデータ量を低減す
ることができるようにするものである。

【００１０】

【課題を解決するための手段】本発明の第１の画像符号
化方法は、画像の特徴点と、特徴点以外の点とからなる
２値画像のうち、特徴点の周囲の点を特徴点に変換した
２値画像である膨張２値画像を生成する生成ステップ
と、膨張２値画像の変化点を検出する変化点検出ステッ
プと、画像を構成する点が、変化点に近接する度合いを
表す近接度を算出する算出ステップと、画像の特徴点か
ら、近接度が所定の閾値以上のものを選択する選択ステ
ップと、選択ステップにおいて選択された特徴点に関す
る情報を符号化する符号化ステップとを備えることを特
徴とする。

【００１１】

【００１２】

【００１３】本発明の第２の画像符号化方法は、画像の
特徴点に関する情報を符号化し、符号化データを出力す
る符号化ステップと、画像の特徴点と、特徴点以外の点
とからなる２値画像のうち、特徴点の周囲の点を特徴点
に変換した２値画像である膨張２値画像を生成する生成
ステップと、膨張２値画像の変化点を検出する変化点検
出ステップと、符号化データに基づいて、画像の特徴点
を結ぶチェーンを検出するチェーン検出ステップと、チ
ェーンが、変化点に近接する度合いを表す近接度を算出
する算出ステップと、符号化データから、その符号化デ
ータに対応するチェーンの近接度が所定の閾値以上のも
のを選択して出力する選択ステップとを備えることを特
徴とする。

【００１４】

【００１５】

【００１６】本発明の第１の画像符号化方法において
は、画像の特徴点と、特徴点以外の点とからなる２値画
像のうち、特徴点の周囲の点を特徴点に変換した２値画
像である膨張２値画像が生成され、膨張２値画像の変化
点が検出される。さらに、画像を構成する点が、変化点
に近接する度合いを表す近接度が算出され、画像の特徴
点から、近接度が所定の閾値以上のものが選択される。
そして、その選択された特徴点に関する情報が符号化さ
れる。

【００１７】

【００１８】本発明の第２の画像符号化方法において
は、画像の特徴点に関する情報が符号化され、符号化デ
ータが出力される。さらに、画像の特徴点と、特徴点以
外の点とからなる２値画像のうち、特徴点の周囲の点を
特徴点に変換した２値画像である膨張２値画像が生成さ
れ、膨張２値画像の変化点が検出される。また、符号化
データに基づいて、画像の特徴点を結ぶチェーンが検出
され、チェーンが、変化点に近接する度合いを表す近接
度が算出される。そして、符号化データから、その符号
化データに対応するチェーンの近接度が所定の閾値以上
のものが選択されて出力される。

【００１９】

【００２０】

【発明の実施の形態】

【００２１】

【００２２】

【００２３】

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

【００２５】従って、この画像符号化装置においては、
２次元変化点検出回路１０からは、入力された画像デー
タ（その画像データを有する画素）が特徴点であるかど
うかに対応した特徴点データが出力される一方、量子化
器１１からは、画像データを量子化して得られる量子化
係数が出力される。

【００２６】特徴点データは、変化点スレッショルド回
路１３を介してチェーン符号化回路１２に供給され、量
子化係数は、そのままチェーン符号化回路１２に供給さ
れる。ここで、変化点スレッショルド回路１３では、特
徴点データのうち、視覚的な重要度の低い特徴点につい
ての特徴点データの値が１から０に変更され、これによ
り、値が１の特徴点データの数が少なくされる。

【００２７】チェーン符号化回路１２では、前述したよ
うに、特徴点データが１の点（画素）についての位置情
報がチェーン符号化され、さらに特徴点の量子化係数と
多重化されて、チェーン符号化データとされる。

【００２８】従って、変化点スレッショルド回路１３に
おいて、値が１の特徴点データの数が少なくされるの
で、チェーン符号化データのデータ量を低減することが
できる。

【００２９】図２は、図１の２次元変化点検出回路１０
の構成例を示している。画像データは、フレームバッフ
ァ４１に供給され、一旦記憶される。フレームバッファ
４１に、１フレーム分の画像データが記憶されると、そ
の画像データは、フレームバッファ４１から読み出さ
れ、フィルタ（ローパスフィルタ）４２に供給されて、
そこでフィルタリング（平滑化）される。その後、画像
データは、例えば、いわゆるラインスキャン順に、乗算
器４３、１サンプル遅延回路（Ｄ）４４、乗算器５３、
および１ライン遅延回路（ＬＤ）５４に供給される。

【００３０】乗算器４３では、画像データに、−１が乗
算され、加算器４５に出力され、１サンプル遅延回路４
４では、画像データが１サンプル分だけ遅延されて、加
算器４５に出力される。加算器４５では、乗算器４３の
出力と、１サンプル遅延回路４４の出力とが加算され
る。従って、第ｎサンプル目の画像データを現画像デー
タとし、ｘ（ｎ）と表すとすると、乗算器４３、１サン
プル遅延回路４４、および加算器４５では、１サンプル
前の画像データｘ（ｎ−１）（本実施例では、画像デー
タは、上述したように、ラインスキャン順にフィルタ４
２から出力されるから、１サンプル前の画像データｘ
（ｎ−１）は、現画像データｘ（ｎ）の画素の左に隣接
する画素の画像データということになる）と、現画像デ
ータｘ（ｎ）との差分ｘ（ｎ−１）−ｘ（ｎ）が演算さ
れる。

【００３１】ここで、以下、適宜、加算器４５の出力
を、横方向振幅傾度という。

【００３２】加算器４５から出力された横方向振幅傾度
は、２つに分けられて、いずれも乗算器４６に入力され
る。乗算器４６では、２つの横方向振幅傾度が乗算さ
れ、即ち、横方向振幅傾度が自乗され（以下、適宜、横
方向振幅傾度の自乗値を、横方向振幅傾度電力とい
う）、加算器４７および１サンプル遅延回路４８に供給
される。

【００３３】加算器４７には、横方向振幅傾度電力の
他、所定の閾値−Ｔ１が供給されるようになされてお
り、そこでは、横方向振幅傾度電力に閾値−Ｔ１が加算
される。即ち、加算器４７では、横方向振幅傾度電力と
閾値Ｔ１との差分がとられる。この差分値は、乗算器５
０に供給される。

【００３４】また、１サンプル遅延回路４８では、横方
向振幅傾度電力が１サンプル分だけ遅延され、加算器４
９に供給される（以下、適宜、１サンプル分だけ遅延さ
れた横方向振幅傾度電力を、遅延横方向振幅傾度電力と
いう）。加算器４９には、横方向振幅傾度電力の他、所
定の閾値−Ｔ１が供給されるようになされており、そこ
では、遅延横方向振幅傾度電力に閾値−Ｔ１が加算され
る。即ち、加算器４９では、加算器４７における場合と
同様に、遅延横方向振幅傾度電力と閾値Ｔ１との差分が
とられる。この差分値は、乗算器５０に供給される。

【００３５】乗算器５０では、加算器４７の出力と加算
器４９の出力とが乗算され、コンパレータ５１に出力さ
れる。コンパレータ５１では、乗算器５０の出力が０と
比較され、その出力が０以上のとき、または０未満のと
き、それぞれ０または１が、ＯＲゲート５２に出力され
る。

【００３６】ここで、加算器４７または４９からそれぞ
れ出力される横方向振幅傾度電力と閾値Ｔ１との差分
値、または遅延横方向振幅傾度電力と閾値Ｔ１との差分
値は、（ｘ（ｎ−１）−ｘ（ｎ））²−Ｔ１、または
（ｘ（ｎ−２）−ｘ（ｎ−１））²−Ｔ１と表すことが
できる。従って、コンパレータ５１からは、横方向振幅
傾度電力（ｘ（ｎ−１）−ｘ（ｎ））²および遅延横方
向振幅傾度電力（ｘ（ｎ−２）−ｘ（ｎ−１））²が、
ともに閾値Ｔ１より大きい場合か、閾値Ｔ１より小さい
場合、またはそのうちのいずれか一方が０の場合に、０
が出力され、一方が閾値Ｔ１より小さく、他方が閾値Ｔ
１より大きい場合に、１が出力されることになる。

【００３７】即ち、コンパレータ５１からは、画素を水
平方向（横方向）（ｘ軸方向）に見た場合において、画
素値の変化の割合（画素値の空間的な微分値）が大きく
変わるときに、１が出力される。

【００３８】一方、乗算器５３では、画像データに、−
１が乗算され、加算器５５に出力され、１ライン遅延回
路５４では、画像データが１ライン分だけ遅延されて、
加算器５５に出力される。加算器５５では、乗算器５３
の出力と、１ライン遅延回路５４の出力とが加算され
る。従って、１ラインの画素数を、ＬHとすると、乗算
器５３、１ライン遅延回路５４、および加算器５５で
は、１ライン前の画像データｘ（ｎ−ＬH）（本実施例
では、画像データは、上述したように、ラインスキャン
順にフィルタ４２から出力されるから、１ライン前の画
像データｘ（ｎ−ＬH）は、現画像データｘ（ｎ）の画
素の上に隣接する画素の画像データということになる）
と、現画像データｘ（ｎ）との差分ｘ（ｎ−ＬH）−ｘ
（ｎ）が演算される。

【００３９】ここで、以下、適宜、加算器５５の出力
を、縦方向振幅傾度という。

【００４０】加算器５５から出力された縦方向振幅傾度
は、２つに分けられて、いずれも乗算器５６に入力され
る。乗算器５６では、２つの縦方向振幅傾度が乗算さ
れ、即ち、縦方向振幅傾度が自乗され（以下、適宜、縦
方向振幅傾度の自乗値を、縦方向振幅傾度電力とい
う）、加算器５７および１ライン遅延回路５８に供給さ
れる。

【００４１】加算器５７には、縦方向振幅傾度電力の
他、所定の閾値−Ｔ１が供給されるようになされてお
り、そこでは、縦方向振幅傾度電力に閾値−Ｔ１が加算
され、乗算器６０に供給される。また、１ライン遅延回
路５８では、縦方向振幅傾度電力が１ライン分だけ遅延
され、加算器５９に供給される（以下、適宜、１ライン
分だけ遅延された縦方向振幅傾度電力を、遅延縦方向振
幅傾度電力という）。加算器５９には、縦方向振幅傾度
電力の他、所定の閾値−Ｔ１が供給されるようになされ
ており、そこでは、縦延横方向振幅傾度電力に閾値−Ｔ
１が加算され、乗算器６０に供給される。

【００４２】乗算器６０では、加算器５７の出力と加算
器５９の出力とが乗算され、コンパレータ６１に出力さ
れる。コンパレータ６１では、乗算器６０の出力が０と
比較され、その出力が０以上のとき、または０未満のと
き、それぞれ０または１が、ＯＲゲート５２に出力され
る。

【００４３】ここで、加算器５７または５９からそれぞ
れ出力される縦方向振幅傾度電力と閾値Ｔ１との差分値
（閾値−Ｔ１との加算値）、または遅延縦方向振幅傾度
電力と閾値Ｔ１との差分値（閾値−Ｔ１との加算値）
は、（ｘ（ｎ−ＬH）−ｘ（ｎ））²−Ｔ１、または（ｘ
（ｎ−２ＬH）−ｘ（ｎ−ＬH））²−Ｔ１と表すことが
できる。従って、コンパレータ６１からは、縦方向振幅
傾度電力（ｘ（ｎ−ＬH）−ｘ（ｎ））²および遅延縦方
向振幅傾度電力（ｘ（ｎ−２ＬH）−ｘ（ｎ−ＬH））²
が、ともに閾値Ｔ１より大きい場合か、閾値Ｔ１より小
さい場合、またはそのうちのいずれか一方が０の場合
に、０が出力され、一方が閾値Ｔ１より小さく、他方が
閾値Ｔ１より大きい場合に、１が出力されることにな
る。

【００４４】即ち、コンパレータ６１からは、画素を垂
直方向（縦方向）（ｙ軸方向）に見た場合において、画
素値の変化の割合が大きく変わるときに、１が出力され
る。

【００４５】ＯＲゲート５２では、コンパレータ５１の
出力と、コンパレータ６１の出力とのＯＲ（論理和）が
計算され、これが特徴点データとして出力される。従っ
て、水平方向または垂直方向の画素値の変化の割合が大
きく変わる画素については、値が１の特徴点データが出
力され、画素値の変化の割合が大きく変わらない画素に
ついては、値が０の特徴点データが出力されることにな
る。

【００４６】次に、図３は、図１の２次元変化点検出回
路１０の他の構成例を示している。この２次元変化点検
出回路１０は、２次元変化点強度／最大変化方向計算回
路７１および変化点検出回路７２で構成されている。２
次元変化点強度／最大変化方向計算回路７１では、画像
を構成する各画素について、画像データから、画素値が
最も大きく変化する方向（最大変化方向）と、その最大
変化方向への画素値の変化量に対応する値（変化強度）
とが計算され、変化点検出回路７２に出力される。変化
点検出回路７２では、最大変化方向および変化強度に基
づき、画像を構成する各画素について、その画素が特徴
点であるかどうかを判定し、特徴点であると判定した画
素については１を、特徴点でないと判定した画素につい
ては０を、それぞれ特徴点データとして出力する。

【００４７】図４は、図３の２次元変化点強度／最大変
化方向計算回路７１の構成例を示している。画像データ
は、フレームバッファ８１に供給され、一旦記憶され
る。フレームバッファ８１に、１フレーム分の画像デー
タが記憶されると、その画像データは、フレームバッフ
ァ８１から読み出され、フィルタ（ローパスフィルタ）
８２に供給されて、そこでフィルタリングされる。その
後、画像データは、例えば、いわゆるラインスキャン順
に、乗算器８３、１サンプル遅延回路（Ｄ）８４、乗算
器９３、および１ライン遅延回路（ＬＤ）９４に供給さ
れる。

【００４８】ここで、図４の乗算器８３、１サンプル遅
延回路８４、および加算器８５でなるブロックは、図２
に示した乗算器４３、１サンプル遅延回路４４、および
加算器４５でなるブロックと同様に構成されている。ま
た、図４の乗算器９３、１ライン遅延回路９４、および
加算器９５でなるブロックは、図２に示した乗算器５
３、１ライン遅延回路５４、および加算器５５でなるブ
ロックと同様に構成されている。

【００４９】従って、加算器８５または９５からは、図
２の加算器４５または５５における場合と同様に、横方
向振幅傾度または縦方向振幅傾度がそれぞれ出力され
る。

【００５０】この横方向振幅傾度および縦方向振幅傾度
は、最大変化方向計算回路８７に供給される。最大変化
方向計算回路８７では、横方向振幅傾度または縦方向振
幅傾度を、それぞれＡまたはＢと表すとすると、Ｃ＝ａ
ｒｃｔａｎ（Ｂ／Ａ）（ｔａｎ^-1（Ｂ／Ａ））が計算さ
れ、その計算結果（角度）（方向）Ｃに応じて、図５
（Ａ）に示すような値を、最大変化方向として出力す
る。

【００５１】ここで、図５（Ａ）から、最大変化方向
は、図５（Ｂ）に示すような方向を表す。即ち、値が０
の最大変化方向は、いま処理の対象としている画素（処
理対象の画素）（図５（Ｂ）において斜線を付してある
部分）の左および右方向を表し、値が１の最大変化方向
は、処理対象の画素の左下および右上方向を表す。さら
に、値が２の最大変化方向は、処理対象の画素の上およ
び下方向を表し、値が３の最大変化方向は、処理対象の
画素の右下および左上方向を表す。つまり、値が０の最
大変化方向は、左に隣接する画素Ｐ１および右に隣接す
る画素Ｐ６の方向を表し、値が１の最大変化方向は、左
下に隣接する画素Ｐ２および右上に隣接する画素Ｐ５の
方向を表す。さらに、値が２の最大変化方向は、上に隣
接する画素Ｐ３および下に隣接する画素Ｐ４の方向を表
し、値が３の最大変化方向は、右下に隣接する画素Ｐ７
および左上に隣接する画素Ｐ０の方向を表す。

【００５２】次に、図４において、乗算器８３、１サン
プル遅延回路８４、加算器８５、および乗算器８６でな
るブロックは、図２に示した乗算器４３、１サンプル遅
延回路４４、加算器４５、および乗算器４６でなるブロ
ックと同様に構成されている。また、図４の乗算器９
３、１ライン遅延回路９４、加算器９５、および乗算器
９６でなるブロックは、図２に示した乗算器５３、１ラ
イン遅延回路５４、加算器５５、および乗算器５６でな
るブロックと同様に構成されている。

【００５３】従って、乗算器８６または９６からは、図
２の乗算器４６または５６における場合と同様に、横方
向振幅傾度電力または縦方向振幅傾度電力がそれぞれ出
力される。

【００５４】この横方向振幅傾度電力および縦方向振幅
傾度電力は、加算器９７に供給される。加算器９７で
は、横方向振幅傾度電力と縦方向振幅傾度電力とが加算
され、その加算結果が、変化強度として出力される。

【００５５】以上のようにして求められた最大変化方向
および変化強度は、上述したように、変化点検出回路７
２（図３）に供給される。

【００５６】図６は、図３の変化点検出回路７２の構成
例を示している。変化強度または最大変化方向は、フレ
ームバッファ１０１または１０２にそれぞれ供給されて
記憶される。フレームバッファ１０１または１０２に、
１フレーム分の変化強度または最大変化方向が記憶され
ると、セレクタ１０３は、フレームバッファ１０２か
ら、最大変化方向を、例えばラインスキャン順に順次読
み出し、各最大変化方向について、次のような処理を行
う。

【００５７】即ち、セレクタ１０３は、処理対象の画素
についての最大変化方向を、フレームバッファ１０２か
ら読み出すと、その最大変化方向に基づいて、図７に示
すような画素を、第１および第２最大変化方向候補点と
する。即ち、最大変化方向が、処理対象画素の左および
右方向を表す０である場合、図５（Ｂ）に示したよう
に、その左に隣接する画素Ｐ１または右に隣接する画素
Ｐ６が、それぞれ第１または第２最大変化方向候補点と
される。また、最大変化方向が、処理対象画素の左下お
よび右上方向を表す１である場合、その左下に隣接する
画素Ｐ２または右上に隣接する画素Ｐ５が、それぞれ第
１または第２最大変化方向候補点とされる。さらに、最
大変化方向が、処理対象画素の上および下方向を表す２
である場合、その上に隣接する画素Ｐ３または下に隣接
する画素Ｐ４が、それぞれ第１または第２最大変化方向
候補点とされる。同様に、最大変化方向が、処理対象画
素の左上および右下方向を表す３である場合、その左上
に隣接する画素Ｐ０または右下に隣接する画素Ｐ７が、
それぞれ第１または第２最大変化方向候補点とされる。

【００５８】さらに、セレクタ１０３は、第１および第
２最大変化方向候補点である画素についての変化強度が
記憶されているアドレスをフレームバッファ１０１に出
力することで、それらの画素についての変化強度を、フ
レームバッファ１０１から読み出す。この第１または第
２最大変化方向候補点の変化強度は、加算器１０４また
は１０５にそれぞれ供給される。

【００５９】加算器１０４には、第１最大変化方向候補
点の変化強度の他、所定の閾値−Ｔ２が供給されるよう
になされており、そこでは、第１最大変化方向候補点の
変化強度に閾値−Ｔ２が加算される。即ち、加算器１０
４では、第１最大変化方向候補点の変化強度と閾値Ｔ２
との差分がとられる。この差分値は、乗算器１０６に供
給される。

【００６０】一方、加算器１０５にも、第２最大変化方
向候補点の変化強度の他、所定の閾値−Ｔ２が供給され
るようになされており、そこでは、第２最大変化方向候
補点の変化強度に閾値−Ｔ２が加算される。即ち、加算
器１０５においても、加算器１０４における場合と同様
に、第２最大変化方向候補点の変化強度と閾値Ｔ２との
差分がとられる。そして、この差分値も、乗算器１０６
に供給される。

【００６１】乗算器１０６では、加算器１０４の出力と
加算器１０５の出力とが乗算され、コンパレータ１０７
に出力される。コンパレータ１０７では、乗算器１０６
の出力が０と比較され、その出力が０以上のとき、また
は０未満のとき、それぞれ０または１が、特徴点データ
として出力される。

【００６２】従って、この場合、コンパレータ１０７か
らは、第１および第２最大変化方向候補点の変化強度
が、ともに閾値Ｔ２より大きい場合か、閾値Ｔ２より小
さい場合、またはそのうちのいずれか一方が０の場合
に、０が出力され、一方が閾値Ｔ２より小さく、他方が
閾値Ｔ２より大きい場合に、１が出力されることにな
る。即ち、最大変化方向の画素値の変化の割合が大きく
変わる画素については、値が１の特徴点データが出力さ
れ、最大変化方向の画素値の変化の割合が大きく変わら
ない画素については、値が０の特徴点データが出力され
ることになる。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【０１１０】次に、図２３は、図１の変化点スレッショ
ルド回路１３の構成例を示している。２次元変化点検出
回路１０（図１）からの特徴点データは、フレームバッ
ファ１１１に供給されて記憶される。なお、フレームバ
ッファ１１１では、図８のマスクフレームバッファ２２
（係数フレームバッファ２１）における場合と同様に、
各画素についての特徴点データが、その画素の座標に対
応したアドレスに記憶されるようになされている。

【０１１１】フレームバッファ１１１に１フレーム分の
特徴点データが記憶されると、膨張回路１１２は、フレ
ームバッファ１１１を参照して、画像の特徴点と、特徴
点以外の点とからなる２値画像のうち、特徴点の周囲の
点を特徴点に変換した２値画像である膨張２値画像を生
成する。即ち、膨張回路１１２は、フレームバッファ１
１１に記憶された特徴点データを、１および０の２値で
なる２値画像とみなし、その２値画像を構成する画素の
うち、値が１になっている画素（特徴点）を中心とする
Ｌ１×Ｌ２画素の範囲にある画素の画素値を１に変換す
ることで、値が１になっている画素を、いわば膨張させ
た膨張２値画像を生成する。

【０１１２】具体的には、膨張回路１１２は、フレーム
バッファ１１１から、例えばラインスキャン順に、特徴
点データを読み出し、フレームバッファ１１３に供給し
て、フレームバッファ１１１における場合と同様に、そ
の特徴点データに対応する画素の座標に対応したアドレ
スに記憶させる。この際、膨張回路１１２は、読み出し
た特徴点データが１である場合には、その特徴点データ
に対応する画素を中心とするＬ１×Ｌ２画素の範囲にあ
る画素の座標に対応するアドレスすべてに１を格納し、
特徴点データが０である場合には、そのまま、その特徴
点データに対応する画素の座標に対応する、フレームバ
ッファ１１３のアドレスに転送する（但し、この場合、
そのアドレスに、既に１が記憶されている場合、その１
を記憶させたままにする）。

【０１１３】これにより、画像データとして、テクスチ
ャ領域を含む、例えば図２４（Ａ）に示すようなものが
入力され、２次元変化点検出回路１０において、その画
像データに基づいて、例えば図２４（Ｂ）に示すよう
に、テクスチャ領域の外周部分からだけでなく、その内
部からも特徴点（図中、斜線を付してある部分）が検出
された場合には、各特徴点を中心とするＬ１×Ｌ２画素
の範囲（図中、点線で囲んである範囲）も特徴点とさ
れ、その結果、図２４（Ｃ）に示すような、テクスチャ
領域を膨張させ、かつその内部が特徴点で埋められたよ
うな膨張２値画像（図中、斜線を付してある部分が１
（特徴点）に、斜線を付していない部分が０に、それぞ
れ対応する）が構成される。なお、図２４においては、
Ｌ１＝Ｌ２＝３としてある。

【０１１４】フレームバッファ１１３に、以上のような
膨張２値画像が記憶されると、変化点検出回路１１４で
は、その膨張２値画像の変化点が検出される。即ち、例
えば、変化点検出回路１１４は、フレームバッファ１１
３を参照し、膨張２値画像を構成する各画素と、その画
素の右に隣接する画素または下に隣接する画素との画素
値が異なる場合、その画素を変化点として検出し、値が
１の変化点データを、近接度計算回路１１５に出力す
る。また、変化点検出回路１１４は、膨張２値画像を構
成する各画素と、その画素の右に隣接する画素または下
に隣接する画素との画素値が、いずれも異ならない場
合、値が０の変化点データを、近接度計算回路１１５に
出力する。

【０１１５】従って、図２５（Ａ）に示す、図２４
（Ｃ）と同様の膨張２値画像が得られた場合、変化点デ
ータで構成される２値画像は、図２５（Ｂ）に示すよう
な膨張２値画像の外周を囲むようなものとなる（図２５
（Ｂ）においては、斜線を付してある部分が値が１の変
化点データに、斜線を付していない部分が値が０の変化
点データに、それぞれ対応する）。

【０１１６】近接度計算回路１１５では、画像を構成す
る各画素について、その画素が、変化点検出回路１１４
で検出された変化点に近接する度合いを表す近接度が、
その画素の視覚的な重要度を表すものとして算出され
る。即ち、近接度計算回路１１５は、画像を構成する各
画素について、その画素を中心とするＬ１×Ｌ２画素の
範囲内に存在する変化点の数を、変化点検出回路１１４
からの変化点データに基づいてカウントし、そのカウン
ト値を、その画素の近接度とする。

【０１１７】そして、近接度計算回路１１５は、近接度
を所定の閾値Ｔと比較し、その近接度が、閾値Ｔ以上の
場合、値が、例えば１のセレクトデータを、また、近接
度が閾値Ｔ未満の場合、値が、例えば０のセレクトデー
タを、それぞれセレクタ１１６に出力する。

【０１１８】セレクタ１１６は、近接度計算回路１１５
から、所定の画素に対応するセレクトデータを受信する
と、その画素に対応する特徴点データを、フレームバッ
ファ１１１から読み出す。そして、セレクトデータが１
である場合、フレームバッファ１１１から読み出した特
徴点データを選択してそのまま出力し、セレクトデータ
が０である場合、セレクトデータ、即ち、０を選択し、
これを、特徴点データとして出力する。

【０１１９】従って、値が１の特徴点データであって
も、その画素の近接度（視覚的な重要度）が閾値Ｔ未満
である場合には、その値が０とされる。

【０１２０】以上から、チェーン符号化回路１２に供給
される、値が１の特徴点データの数が少なくされるの
で、チェーン符号化データのデータ量を低減することが
できる。さらに、この場合、値が１から０にされる特徴
点データに対応する画素は、視覚的な重要度の高いもの
ではないから、復号画像の画質の劣化もほとんどない。

【０１２１】即ち、例えば図２４（Ｂ）に示したような
テクスチャ領域の内部に存在する、視覚的重要度の高く
ない特徴点（このような特徴点は、ノイズ状のエッジに
相当すると考えられる）が、特徴点でないものとして
（スレッショルディングされ）、チェーン符号化が行わ
れるので、画質をほとんど劣化させることなく、チェー
ン符号化データのデータ量を低減することができる。

【０１２２】次に、図２６は、本発明を適用した画像符
号化装置の第２実施例の構成を示している。なお、図
中、図１の画像符号化装置における場合と対応する部分
については、同一の符号を付してある。即ち、この画像
符号化装置は、変化点スレッショルド回路１３が削除さ
れるとともに、テクスチャチェーン除去回路１５および
チェーンセレクト回路１６が新たに設けられている他
は、図１の画像符号化装置と同様に構成されている。

【０１２３】従って、この画像符号化装置においては、
２次元変化点検出回路１０より出力される特徴点データ
が、そのまま、チェーン符号化回路１２に供給され、そ
こでは、従来における場合と同様に、２次元変化点検出
回路１０で検出されたすべての特徴点について、チェー
ン符号化が行われる。そして、その結果得られたチェー
ン符号化データは、チェーンセレクト回路１６に出力さ
れる。

【０１２４】チェーンセレクト回路１６は、チェーン符
号化回路１２から出力されたチェーン符号化データに対
応する各チェーンについて、そのチェーンの視覚的な重
要度を、テクスチャチェーン除去回路１５に計算させ
る。テクスチャチェーン除去回路１５では、チェーンセ
レクト回路１６により指定されたチェーンの視覚的な重
要度が計算されるようになされており、その計算結果に
応じて、そのチェーンを出力するかどうかを決定するよ
うになされている。そして、チェーンセレクト回路１６
は、テクスチャチェーン除去回路１５の決定結果に応じ
て、チェーン符号化回路１２より出力されたチェーン符
号化データから、視覚的な重要度が高いものを選択して
出力する。

【０１２５】従って、この場合、チェーンセレクト回路
１６において、視覚的な重要度が高くないチェーンのチ
ェーン符号化データが、いわば除去されるので、画像符
号化装置から出力されるチェーン符号化データのデータ
量を低減することができる。

【０１２６】次に、図２７は、テクスチャチェーン除去
回路１５の構成例を示している。このテクスチャチェー
ン除去回路１５には、２次元変化点検出回路１０から出
力された特徴点データが供給され、その特徴点データ
は、フレームバッファ１２１に入力される。フレームバ
ッファ１２１、膨張回路１２２、フレームバッファ１２
３、または変化点検出回路１２４は、図２３に示したフ
レームバッファ１１１、膨張回路１１２、フレームバッ
ファ１１３、または変化点検出回路１１４とそれぞれ同
様に構成されるもので、従って、特徴点データは、フレ
ームバッファ１２１、膨張回路１２２、フレームバッフ
ァ１２３、および変化点検出回路１２４を介することに
より、変化点データとされ、近似度計算回路１２５に供
給される。

【０１２７】一方、チェーン検出回路１２６には、チェ
ーンセレクト回路１６（図２６）から、チェーン符号化
データが供給される。チェーン検出回路１２６は、チェ
ーンセレクト回路１６から、チェーン符号化データを受
信すると、そのチェーン符号化データに基づいて、即
ち、そこに含まれる開始点座標、方向データ、および方
向変化データ（図２２）を参照して、特徴点を結ぶチェ
ーンを検出する。検出されたチェーンは、近似度計算回
路１２５に供給される。

【０１２８】近接度計算回路１２５では、チェーン検出
回路１２６から供給されたチェーンが、変化点検出回路
１２４で検出された変化点に近接する度合いを表す近接
度が、そのチェーンの視覚的な重要度を表すものとして
算出される。即ち、近接度計算回路１２５は、チェーン
検出回路１２６からのチェーンを構成する画素（特徴
点）それぞれを中心とするＬ１×Ｌ２画素の範囲内に存
在する変化点の数を、変化点検出回路１２４からの変化
点データに基づいて求め、さらに、その平均値（チェー
ンを構成する各画素を中心とするＬ１×Ｌ２画素の範囲
に存在する変化点の数の総和を、チェーンを構成する画
素数で除算したもの）を求めて、これを、そのチェーン
の近接度とする。

【０１２９】なお、以上のようにして算出される近接度
は、チェーンを構成する各画素を中心とするＬ１×Ｌ２
画素の範囲に存在する変化点の密度ということができる
が、近接度としては、このような変化点の密度以外の量
を採用することが可能である。

【０１３０】即ち、例えば、チェーンを構成する画素の
うち、それを中心とするＬ１×Ｌ２画素の範囲に変化点
が存在するものの数を、チェーンを構成する画素数で除
算し、その結果得られる値を、そのチェーンの近接度と
することが可能である。

【０１３１】近接度計算回路１２５は、近接度の算出
後、その近接度を所定の閾値Ｔ４と比較し、その近接度
が、閾値Ｔ４以上の場合、値が、例えば１のセレクトデ
ータを、また、近接度が閾値Ｔ４未満の場合、値が、例
えば０のセレクトデータを、それぞれチェーンセレクト
回路１６（図２６）に出力する。

【０１３２】チェーンセレクト回路１６では、チェーン
符号化データを、テクスチャチェーン除去回路１５に出
力した後、テクスチャチェーン除去回路１５（近接度計
算回路１２５）から、セレクトデータを受信すると、セ
レクトデータが１である場合には、テクスチャチェーン
除去回路１５に出力したチェーン符号化データを選択し
てそのまま出力し、セレクトデータが０である場合、そ
のチェーン符号化データを削除する。従って、チェーン
セレクト回路１６からは、チェーン符号化回路１２から
のチェーン符号化データのうち、そのチェーンに対応す
るセレクトデータが１のもの、即ちチェーンの視覚的な
重要度が高いものだけが選択されて出力される。

【０１３３】以上のように、チェーン符号化回路１２か
ら出力されたチェーン符号化データが少なくされるの
で、画像符号化装置から出力されるチェーン符号化デー
タのデータ量を低減することができる。さらに、この場
合、セレクトデータが０であるチェーンは、視覚的な重
要度の高いものではないから、復号画像の画質の劣化も
ほとんどない。

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

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

【０１３６】また、本発明は、動画および静止画のいず
れにも適用可能である。

【０１３７】さらに、本明細書中において、「近接度が
所定の閾値以上である（より大きい）とき」というの
は、近接度の値が大きい場合に、近接度が高くなること
を前提としている。従って、近接度が、値が小さい方が
高くなるように定義した場合には、本明細書中における
「近接度が所定の閾値以上である（より大きい）とき」
というのは、「近接度が所定の閾値以下である（より小
さい）とき」ということを意味する。

【０１３８】

【発明の効果】本発明の第１の画像符号化方法によれ
ば、画像の特徴点と、特徴点以外の点とからなる２値画
像のうち、特徴点の周囲の点を特徴点に変換した２値画
像である膨張２値画像が生成され、その膨張２値画像の
変化点が検出される。さらに、画像を構成する点が、変
化点に近接する度合いを表す近接度が算出され、画像の
特徴点から、近接度が所定の閾値以上のものが選択され
る。そして、選択された画像の特徴点に関する情報が符
号化される。従って、符号化の結果生じるデータのデー
タ量を低減することができる。

【０１３９】本発明の第２の画像符号化方法によれば、
画像の特徴点と、特徴点以外の点とからなる２値画像の
うち、特徴点の周囲の点を特徴点に変換した２値画像で
ある膨張２値画像が生成され、その膨張２値画像の変化
点が検出される。一方、画像の特徴点に関する情報が符
号化され、その結果得られる符号化データに基づいて、
画像の特徴点を結ぶチェーンが検出される。さらに、そ
のチェーンが、変化点に近接する度合いを表す近接度が
算出され、その後、符号化データから、その符号化デー
タに対応するチェーンの近接度が所定の閾値以上のもの
が選択されて出力される。従って、符号化データのデー
タ量を低減することができる。

【図面の簡単な説明】

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

【図２】図１の２次元変化点検出回路１０の構成例を示
す図である。

【図３】図１の２次元変化点検出回路１０の他の構成例
を示すブロック図である。

【図４】図３の２次元変化点強度／最大変化方向計算回
路７１の構成例を示す図である。

【図５】図４の最大変化方向計算回路８７の動作を説明
するための図である。

【図６】図３の変化点検出回路７２の構成例を示す図で
ある。

【図７】図６のセレクタ１０３の動作を説明するための
図である。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

【図２３】図１の変化点スレッショルド回路１３の構成
例を示すブロック図である。

【図２４】図２３の膨張回路１１２の動作を説明するた
めの図である。

【図２５】図２３の変化点検出回路１１４の動作を説明
するための図である。

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

【図２７】図２６のテクスチャチェーン除去回路１５の
構成例を示すブロック図である。

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

【図２９】図２８の２次元変化点検出回路１０における
特徴点検出を説明するための図である。

【符号の説明】

１０２次元変化点検出回路１１量子化器１２チェーン符号化回路１３変化点スレッショルド回路１４バッファ１５テクスチャチェーン除去回路１６チェーンセレクト回路１１１フレームバッファ１１２膨張回路１１３フレームバッファ１１４変化点検出回路１１５近接度計算回路１１６セレクタ１２１フレームバッファ１２２膨張回路１２３フレームバッファ１２４変化点検出回路１２５近接度計算回路１２６チェーン検出回路

Claims

(57)【特許請求の範囲】

【請求項１】画像の特徴点を検出する特徴点検出ステ
ップと、前記画像の特徴点と、前記特徴点以外の点とからなる２
値画像のうち、前記特徴点の周囲の点を前記特徴点に変
換した２値画像である膨張２値画像を生成する生成ステ
ップと、前記膨張２値画像の変化点を検出する変化点検出ステッ
プと、前記画像を構成する点が、前記変化点に近接する度合い
を表す近接度を算出する算出ステップと、前記画像の特徴点から、前記近接度が所定の閾値以上の
ものを選択する選択ステップと、前記選択ステップにおいて選択された前記特徴点に関す
る情報を符号化する符号化ステップとを備えることを特
徴とする画像符号化方法。
【請求項２】画像の特徴点を検出する特徴点検出ステ
ップと、前記画像の特徴点に関する情報を符号化し、符号化デー
タを出力する符号化ステップと、前記画像の特徴点と、前記特徴点以外の点とからなる２
値画像のうち、前記特徴点の周囲の点を前記特徴点に変
換した２値画像である膨張２値画像を生成する生成ステ
ップと、前記膨張２値画像の変化点を検出する変化点検出ステッ
プと、前記符号化データに基づいて、前記画像の特徴点を結ぶ
チェーンを検出するチェーン検出ステップと、前記チェーンが、前記変化点に近接する度合いを表す近
接度を算出する算出ステップと、前記符号化データから、その符号化データに対応する前
記チェーンの近接度が所定の閾値以上のものを選択して
出力する選択ステップとを備えることを特徴とする画像
符号化方法。