(57)【要約】【課題】ある基準データの複数の参照データにおける類似度を、高速でかつ並列に演算することができるマッチング演算回路を提供する。【解決手段】参照画像メモリの各行を折り畳む形でデータをメモリ内に格納することにより、読み出しデータ幅を稼ぎ、並列マッチング演算に必要な複数の参照データを同時に読み出すことを可能にする。さらに、その読み出し結果をシフトレジスタに格納し、シフト演算によって類似度を計算するＰＥに参照データ１行分のデータを与え、メモリへのアクセス回数を減らしてデータの読み出しに必要な待ち時間を減らすことにより、全体の処理時間の高速化を行う。【選択図】図１
2004145476.tif 000002
【特許請求の範囲】
【請求項１】
複数の画像データのうち１つを基準画像として、その他を参照画像として、基準画像の一部（ブロックという）を選択して基準データとし、参照画像から対応位置を求める範囲内（対応点探索範囲という）に存在する全ての参照画像のブロック（参照データ）を選択し、基準データと各参照データを１画素ずつずらした複数の対応付けを求めさせ、各対応について類似度を演算してもっとも類似する基準データと参照データの対応を求めるブロックマッチング演算回路において、参照画像の各行を折り畳んでメモリに記憶することにより読み出しデータ幅を折り畳んだデータ幅に等しくすることで、ひとつの基準画像に対するマッチング演算を並列に行うことを特徴とするマッチング演算回路。
【請求項２】
請求項１に記載の画像処理装置において、参照画像メモリの各行を２のべき乗になる数で折り畳むことにより、読み出すデータのアドレス制御を容易にすることを特徴とするマッチング回路。
【請求項３】
請求項１に記載の画像処理装置において、参照画像メモリから読み出されたデータをシフトレジスタに格納してシフト動作を行うことにより、メモリアクセスの回数を低減することを特徴とするマッチング演算回路。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は画像処理装置におけるマッチング演算装置に関するものである。
【０００２】
【従来の技術】
現在、特にロボットビジョンや画像検査システムにおいて高速・高性能なマッチング演算装置が強く望まれており、開発が盛んに行われている。マッチング演算装置は、ある画像データともっとも似通った画像データを検出する装置で、検査システムや物体検出および認識などに用いられている。マッチング演算を用いた物体検出手法であるステレオビジョンや動きベクトル検出では、マッチング演算結果をもとに、空間中に存在する物体の位置や動きを求めることができる。検査システムや物体検出および認識装置では処理の高速化が強く求められている。
【０００３】
一般に、マッチング演算は演算量が大きく、リアルタイムで処理することが実用化への課題となっている。それを達成するため、マッチング演算を並列化する手法がよく用いられており、マッチング演算装置において、並列化を行うためには同時に複数のデータをメモリから読み出す必要があり、通常のメモリではこれを実現することができない。そのため、一般にマルチポートメモリと呼ばれる、複数の読み出し書き込みポートをもつメモリが並列マッチング演算装置では用いられている。
並列読み出しできるものとして、マルチポートメモリがある。しかし、一般のマルチポートメモリは、複数のポートが独立にメモリ領域全てにアクセスすることが可能であるため、ポート数が増えるに従って読み出し制御が複雑となりその回路規模が大きくなるという問題点がある。
また、マッチング演算の際には必要な各データをメモリから読み出す必要があるが、メモリからのデータ読み出しでは一般にデータを読み出すまでの待ち時間が長く、処理の高速化の妨げとなっている。
【０００４】
【発明が解決しようとする課題】
本発明の第１の目的は、マッチング演算を並列に行うためにマルチポートメモリを利用するのではなく、データの格納方法を変更することにより読み出しデータ幅を拡大し、同時に大量のデータを読み出せるデータ格納方法を提供することである。
また、第２の目的は、メモリから読み出したデータをシフトレジスタに格納して類似度演算部に与えることにより、メモリアクセスの回数を低減することでデータ読み出し時の待ち時間を減らし、処理の高速化を図ることができるマッチング演算回路を提供することである。
【０００５】
【発明が解決するための手段】
本発明のマッチング演算装置は、基準画像を格納するための基準画像メモリと、参照画像を格納するための参照画像メモリと、基準画像メモリおよび参照画像メモリの読み出しを制御するための制御回路と、読み出された基準データとそれに対する参照データから類似度演算を行ってもっとも類似度の高い対応を検出するための類似度演算部を具備することを特徴とする。
また、１つの基準データに対して複数の参照データを割り当てて、参照データと同数の類似度演算部を配置することにより、複数の対応における類似度を並列に演算する構成を特徴とする。
さらに、参照データメモリ１行を折り畳んだ形でデータを格納することにより、並列マッチング演算において必要となるデータの同時読み出しを可能とする構成を特徴とする。
また、参照データメモリから読み出されたデータをシフトレジスタに格納して、循環シフトを行うことにより、各対応における類似度演算回路に参照データブロック１行分のデータを与える構成を特徴とする。
【０００６】
【発明の実施の形態】
以下，本発明の実施例について図面を参照しながら説明する。
本発明の第１の特徴は、従来のマルチポートメモリを用いた並列マッチング演算装置では各ポートが独立したアドレスによって格納されているデータの全てにアクセス可能としているためにポート数を増やすに従ってアクセス制御回路が複雑になり回路規模が増大していたことに対して、本発明のマッチング演算装置では参照画像データの各行を折り畳む形でメモリ内に格納することにより、読み出しデータ幅を拡大し、かつ、メモリへのアクセス制御を簡略化した点である。
本発明の第２の特徴は、従来はマッチングブロック内に含まれる各画素のデータをそれぞれ独立にアドレスを与えて読み出していたのに対して、並列読みだしした連続範囲のデータをシフトレジスタに格納してシフト動作を行うことにより、マッチングブロック１行分のデータを類似度演算部に与え、メモリアクセスの回数を削減した点にある。
【０００７】
図１は本発明の画像処理装置の第１の実施形態を示す図である。
本発明の画像処理装置は、基準画像を格納するための基準データメモリ２と、参照画像を格納するための参照データメモリ３と、基準画像メモリと参照画像メモリの読み出しを制御するための制御回路１と、読み出された基準データと参照データの各対応について類似度を演算し、もっとも類似度の高い点を検出するための類似度演算部４からなる。
【０００８】
図２は図１中の参照画像メモリ２におけるデータ格納方法を示す図である。
各行を折り畳む形でデータを記憶して読み出しデータ幅を折り畳みデータ幅に等しくし、１つの基準データに対する複数の対応についての類似度演算を並列に行うために必要なデータを一度に読み出すことを可能とする。
通常のメモリでは、各データに対してアドレスをそれぞれ生成し、対応するデータを読み出す。しかし、マッチング演算では、一般に対応点探索範囲は画像中で連続領域であり、マッチング演算を行う画素のアドレスとその探索範囲から対応点探索範囲の全てのアドレスを求めることができ、それは連続したアドレスとなる。対応点探索範囲で参照画像メモリの各行を折り畳んでデータを格納すると、折り畳みデータ幅分のデータを常に読み出すことにより、並列演算に必要なデータを読み出すことが可能となり、かつ、データの読み出しに必要なアドレスは折り畳み行アドレスのみだけになるため、読み出し制御用のアドレスが圧縮される。これにより、読み出し制御回路が簡単化され、回路規模の増大をおさえることが可能となる。
【０００９】
また、折り畳みデータ幅を２のべき乗とすることによりアドレス変換が不要となるため、回路規模の増大無しに並列読み出しを可能にすることができる。
１行にｗｉｄｔｈピクセルのデータをもっているとし、ｆｏｌｄ＿ｗｉｄｔｈ＝２ｎピクセルでメモリを折り畳んだとき、折り畳みの回数がｍ回であったとする。このとき、
ｗｉｄｔｈ＝ｍ×ｆｌｏｄ＿ｗｉｄｔｈ＝ｍ×２ｎ
であり、各画素の列アドレスは
ｌｏｇ２（ｗｉｄｔｈ）＝ｌｏｇ２（ｍ×２ｎ）＝ｌｏｇ２ｍ＋ｎ
ビットで表現され、列アドレスを２進数表記したとき、列アドレスの上位ｌｏｇ２ｍビットが折り畳み行アドレスを、下位ｎビットが折り畳みデータ幅中でのアドレスを表す。探索範囲でメモリを折り畳んだ場合、下位ｎビットは無視され、上位ｌｏｇ２ｍビットのみで読み出し位置を指定することが可能となる。
また、このとき、画像の分解能をＲとすると、読み出しデータ幅は、
Ｒ×ｆｏｌｄ＿ｎｕｍ＝Ｒ×２ｎ
ビットとなる。
【００１０】
図３は図１中の類似度演算部４の第１の内部構造例を示す図である。
類似度演算部４は、参照画像メモリ３から読み出されたデータを格納するためのシフトレジスタ５と各対応における類似度を演算するための複数のＰＥ（ｐｒｏｃｅｓｓｏｒ　ｅｌｌｅｍｅｎｔ）６から構成される。このブロックは、基準画像メモリ２から読み出された基準データと参照画像メモリ３から読み出された参照データの類似度をＰＥ６において計算し、もっとも類似度の高い位置とその位置における類似度を求める。
読み出すデータ幅が（Ｒ×ｆｏｌｄ＿ｎｕｍ）ビットであるとき、ｆｌｏｄ＿ｎｕｍ個のＰＥ６を配置することにより、１つの基準データに対する複数（ｆｏｌｄ＿ｎｕｍ個）の参照画像データとの各対応における類似度演算を並列に行うことを可能とする。
また、通常の構成では読み出しに行く各画素のアドレスを生成してメモリに与え、読み出されてきた値を用いて演算を行う。このとき、ブロック内に含まれる画素数回メモリへのアクセスを行う。それに対し、本発明ではｆｏｌｄ＿ｎｕｍビットの長さをもつシフトレジスタ５をＲ個配置することにより、メモリの出力（Ｒ×ｆｏｌｄ＿ｎｕｍビット）を一度シフトレジスタに格納し、その後シフト動作をマッチングブロックの列数分行うことで参照データ１行分のデータを各ＰＥ６に与え、メモリアクセス回数をマッチングブロックの行数分に低減する。これにより、メモリ読みだし時に発生する待ち時間を短縮することが可能となる。
この発明は対応する画素同士の値を用いて演算する場合に適用されるものであり、類似度演算内容をブロックマッチング法に限るものではない。また、図３に示すＰＥの構造は一例であり、これに限るものではない。
【００１１】
図４は図１中の類似度演算部４の第２の内部構造例を示す図である。
図３に示す類似度演算部と異なるのは、シフトレジスタの内部構造が、１つ前に読み出した参照データと現在の参照データを保持するために２段構成となる点と、基準画像を保持するためのシフトレジスタが追加される点である。
対応点探索範囲が参照データメモリの折り畳み幅よりも大きい場合、折り畳みの幅の中でマッチング演算を行ったあとに折り畳み行アドレスを１つかえて続きの探索範囲となる参照データアドレスを読み出し、類似度演算を行う必要がある。このとき、図３に示すシフトレジスタの構成では、循環シフトにより参照画像データを各ＰＥ４６に与えるため、探索範囲の端になるＰＥでは、不連続な参照データが与えられることになり、正しい類似度演算を行うことができないという問題がある。その問題点を解決するため、１つ前に読み出した参照データを保持するシフトレジスタと現在の参照データをもつようにシフトレジスタ４５を２段で構成し、読み出し範囲の端が不連続になることを防ぎ、正しい参照データを与え、連続な対応点探索範囲でのマッチング演算を実現する。また、基準データをシフトレジスタに蓄え、循環シフトを行いながら、類似度演算を行うことにより、一度読み出した基準データを複数回にわけて読み出される参照データに対して利用することが可能となり、基準画像メモリへのアクセス数を低減できる。
以上により、対応点探索範囲を列方向に拡大することが容易に可能となる。
【００１２】
本発明は連続したアドレスをもつ参照データを用いてマッチング演算を行う場合であれば、対象をブロックマッチング法によるマッチング演算に限らず、適用することができる。
【００１３】
【発明の効果】
以上、実施の形態に基づいて説明したように、本発明では、参照画像データの各行を折り畳んでデータを格納することにより、ひとつの基準画像について複数の参照画像との類似度演算を並列に行うために必要なデータ幅を取得可能となる。
また、参照画像メモリからの読み出しデータをシフトレジスタに格納することにより、各対応における類似度演算を行うＰＥにそれぞれマッチングブロック１行分のデータを与えることを可能とし、メモリアクセス回数を低減できる。
【図面の簡単な説明】
【図１】本発明の実施例１を示すブロック図
【図２】参照画像メモリの構成図
【図３】類似度演算部の構成例１
【図４】類似度演算部の構成例２
【符号の説明】
１　制御回路
２　基準画像メモリ
３　参照画像メモリ
４　類似度演算部
３５，４５　シフトレジスタ（参照データ）
３６，４６　ＰＥ
３７，４７　最小値検出回路
４８　シフトレジスタ（基準データ）
【図１】
2004145476.tif 000003
【図２】
2004145476.tif 000004
【図３】
2004145476.tif 000005
【図４】
2004145476.tif 000006