JPH0799545B2 - パイプラインヒストグラム算出回路 - Google Patents

Description

【発明の詳細な説明】 〔概要〕 算出結果をメモリに格納する濃度ヒストグラム算出処理
をパイプライン化する為、１つの入力濃度値に対しパイ
プライン処理中にそれまで入力された濃度値で前記入力
濃度値と同一濃度値の個数を検出して補正値を求め、前
記入力濃度値によって読み出されたメモリ内容と共にパ
イプライン演算手段に供給する。これにより入力濃度値
に対する濃度ヒストグラムをパイプライン加算処理で正
しく算出することが可能となり、高速な濃度ヒストグラ
ム算出処理を小規模回路で実現することが出来る。

〔産業上の利用分野〕 本発明は、パイプライン演算処理による高速な濃度ヒス
トグラムの算出回路、特に画像処理において、入力画素
の濃度ヒストグラムを高速に算出する場合に好適な高速
パイプラインヒストグラム算出回路に関する。

〔従来の技術〕

画像処理において濃度ヒストグラムは、コントラストの
修正や領域の抽出等、各種の画像処理に広く用いられて
いる。この濃度ヒストグラムは、画像中から濃度値毎に
その画素数を累積することにより求められる。

この画像の濃度ヒストグラムを算出する方式として、従
来算出された濃度ヒストグラムをメモリに格納し、あ
る入力画素の濃度値に対応するアドレスのメモリ内容を
読み出し、その内容に“1"を加えて再度メモリの同じア
ドレスに書き込みを行う方式、入力画素の濃度値毎に
対応するカウンタに格納する方式、が用いられていた。

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

前述の画像の濃度ヒストグラム算出方式において、の
濃度ヒストグラムをメモリに格納する方式は、安価で規
模の小さいメモリを使用出来る利点がある。しかしなが
ら１回の濃度ヒストグラム算出処理を行うのにメモリか
らの濃度ヒストグラムの読出し動作、加算動作及び算出
された濃度ヒストグラムの再書込み動作の三動作を必要
とする為、濃度ヒストグラム算出処理に時間が掛り算出
処理を高速化することが出来ないという問題があった。

一方、のカウンタに格納する方式は、高速なカウンタ
を用いることにより濃度ヒストグラムの算出処理を容易
に高速化することが可能である反面、濃度ヒストグラム
の最大値、例えば4096×4096の画像では最大2²⁴までの
カウンタを必要とする為、ハードウェアが大規模且つ高
価なものになるという問題があった。

本発明は、画像の濃度ヒストグラムをメモリに格納する
際の濃度ヒストグラム算出処理をパイプライン化するこ
とにより、高速処理が可能で且つ小規模で安価な濃度ヒ
ストグラム算出回路を提供することを目的とする。

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

画像の濃度ヒストグラムをメモリに格納する方式におい
ては、入力画素についてその濃度ヒストグラムを算出す
る場合、メモリの読出し時間をt_mr、演算（加算）時間
をt_ad、メモリへの再書込み時間をt_mwとすると、１回の
濃度ヒストグラム算出処理時間に、t_mr＋t_ad＋t_mw時間
を必要とする。

この様に複数動作からなる演算処理を高速化する為の一
般的な手法として、処理をパイプライン化する手法が知
られている。濃度ヒストグラム算出処理をパイプライン
化することが出来れば、メモリの読出し処理、演算処
理、メモリへの書込み処理を独立に行うことにより、あ
る入力画素についての演算時間はt_mr＋t_ad＋t_mwである
が、全体のスループットとしては（ｎ＋１）t_maxを得る
ことが可能となる。ここで、ｎは連続して入力される画
素の数であり、t_maxはt_mr,t_ad,t_mwの中の最大値であ
る。

然しながら、画像の濃度ヒストグラム算出処理において
は、メモリの読出し、演算、メモリへの書込みの各処理
は独立して行うことが出来ないので、これらの処理を直
ちにパイプライン化することは出来ない。

即ち、画像の濃度ヒストグラム算出処理をそのままパイ
プライン化すると、パイプライン処理中に同じ濃度値の
画素がｍ個連続して入力された場合、その濃度値につい
てメモリから読み出されたそれまでの累積値がＳであっ
たとすると、パイプライン処理結果は“Ｓ＋1"となっ
て、“Ｓ＋1"から“Ｓ＋ｍ＋1"に順次累積する正しい処
理結果が得られないからである。

本発明は、この問題を解決して、画像の濃度ヒストグラ
ム算出処理のパイプライン化を可能にしたものである。

以下、濃度ヒストグラムをメモリに格納する方式におけ
る前述の問題点を解決する為に本発明が講じた手段を、
第１図を参照して説明する。

第１図は、本発明の基本構成をブロック図で示したもの
である。

第１図において、110はメモリで、濃度ヒストグラムの
既算出結果が格納される。

120は入力レジスタ手段で、パイプライン演算手段の演
算段数に対応した数のレジスタ段を有し、濃度値を入力
データとし順次シフトして格納される。

130は補正値発生手段で、入力レジスタ手段120の各レジ
スタ段に格納されている濃度値に基づいて濃度ヒストグ
ラムを算出するための補正値を発生する。

140はパイプライン演算手段で、入力濃度値に基づいて
読み出されたメモリ110の内容と前記補正値を入力とし
てパイプライン処理により濃度ヒストグラムを算出す
る。

150はアドレス選択手段で、入力濃度値をメモリ110に対
する読出しアドレスとして選択し、入力レジスタ手段12
0から出力された濃度値を、パイプライン演算手段140の
処理結果をメモリ110に格納する書き込みアドレスとし
て選択する。

〔作用〕

１つの入力IPがあると、アドレス選択手段150で選択さ
れ、その入力濃度値より得られるアドレスでメモリ110
の内容が読み出されてパイプライン演算手段140に入力
される。

一方、前記入力IPは、レジスタ手段120に加えられる。

補正量発生手段130は、レジスタ段120内の各レジスタ段
間の濃度値に基づいて濃度ヒストグラムを算出するため
の補正値を発生する。即ち、いまパイプライン演算手段
140における演算処理中に前記入力IPと同じ濃度値の入
力がｍ個入力されていて、前記入力IPが加わった時点
で、それらｍ個を含むｎ個の入力に対する演算処理中で
あったとする。

入力IPの濃度値をアドレスとしてメモリ110より読み出
された濃度ヒストグラム値をＳとすると、このＳだけを
パイプライン演算手段140に入力した場合は、パイプラ
イン演算手段140によって“Ｓ＋1"の演算処理が行われ
て、正しい結果である“Ｓ＋ｍ＋1"が得られない。それ
は、入力IPが加わったときに読み出されたメモリ110の
濃度ヒストグラム値Ｓが、パイプライン演算手段140内
で演算処理中のｎ個の入力に関する累積処理が終ってい
ない濃度ヒストグラム値を示すものであることによる。

補正値発生手段130は、レジスタ手段120の各レジスタ段
（図示せず）にあるそれまでのｎ−１個の入力から前記
入力IPの濃度値と同じ濃度値を持ったｍ個の入力を検出
すると、その個数ｍを補正量ｍ＋１としてパイプライン
演算手段140に加える。

パイプライン演算手段140は、前記入力IPの濃度値に基
づいて読み出されたメモリ110の内容Ｓと補正値発生手
段130の発生した前記補正値ｍ＋１を入力としてパイプ
ライン演算処理を行い、正しい処理結果“Ｓ＋ｍ＋1"を
出力する。

アドレス選択手段150は、レジスタ手段120から前記入力
IPの濃度値が出力されたときそれを書き込みアドレスと
して選択し、そのときパイプライン演算手段140から出
力された入力IPの濃度値に対する前記処理結果“Ｓ＋ｍ
＋1"をメモリ110に格納する。

以上の様にして、濃度ヒストグラム算出処理をパイプラ
イン化し、パイプライン演算処理中に同じ濃度値の入力
が連続又は不連続に入力されても正しい濃度ヒストグラ
ムを高速に算出することが出来る。

〔実施例Ｉ〕

本発明の一実施例である実施例Ｉを、第２図を参照して
説明する。

第２図は、実施例Ｉの構成をブロック図で示したもので
ある。

（Ａ）実施例Ｉの構成 第２図において、メモリ110、入力レジスタ手段120、補
正値算出手段130、パイプライン演算手段140、アドレス
選択手段150については、第１図で説明した通りであ
る。

160はサンプリングレジスタで、フリップフロップFFで
構成され、回路外から一定時間間隔で供給される入力画
素濃度値を回路内部のクロックCKに同期した信号となる
様にクロックCKでサンプリングする。

170はメモリレジスタで、アドレス選択手段150を経由し
て加えられたサンプリングレジスタ160の画素濃度値を
アドレスとして読み出されたメモリ110の内容がサンプ
リングレジスタ160より１クロック後れて格納され、そ
の出力はバイプライン演算手段140に供給される。

入力レジスタ手段120において、120₀は入力レジスタ段
で、サンプリングレジスタ160の内容が、サンプリング
レジスタ160より１クロック遅れで格納される。又121₁
〜121_nはパイプライン処理手段140の演算段数ｎに対応
するｎ段のレジスタ段で、フリプフロップ（FF）で構成
され、各入力画素の濃度値がクロックCKに同期して順次
シフトされて格納される。

なお、入力レジスタ手段120のレジスタ段の段数ｎと後
述するパイプライン演算手段140の演算段の段数ｎは同
一であり、ｎはヒストグラム値を２進数で表現できる桁
数以上のｎで構成される。

補正値発生手段130において、131₁〜131_nは比較器で、
比較器131j（ｊ＝１〜ｎ）は、入力レジスタ手段内の対
応するレジスタ段121j（ｊ＝１〜ｎ）と入力レジスタ段
120₀の内容を比較し、等しければ“1"を出力し、等しく
なければ“0"を出力する。132は補正値テーブルで、比
較器131₁〜131_nからの入力に基づいて補正値を発生して
パイプライン演算手段140に加える。具体的には、比較
器131₁〜131_nから供給された“1"入力の加算値に１を加
えた値を発生する。

パイプライン演算手段140において、141₁〜141_nはｎ段
の演算段で、各加算段141j（ｊ＝１〜ｎ）は、パイプラ
イン化した加算器142j、加算結果が格納される演算レジ
スタ144j及び保留しているデータが格納される演算レジ
スタ143jを有している。各加算器142₁〜142_nの加算処理
は１クロック以内で終了する。

第２図のパイプライン演算手段140の具体例を第４図に
示す。なお第４図は演算段数ｎは４とした場合を示して
いる。

第４図において、メモリ170および補正値テーブル132よ
り、後で説明するように、それぞれ、入力レジスタ段12
1₀に記録されている濃度値をアドレスとしてメモリ110
より読出されたヒストグラム値Ｓおよび補正値ｍ＋１が
入力される。

加算器142₁はヒストグラム値Ｓと補正値ｍ＋１の最下位
のケタの加算が行なわれ、加算結果が演算レジスタ144₁
に、また加算結果のケタ上げと最下位ケタ以外のデータ
が演算レジスタ143₁に格納される。

また加算器142₂では最下位よりのケタ上げと第２ケタの
加算が行なわれ、加算結果が演算レジスタ144₂、第２ケ
タよりのケタ上げと第３ケタ以上のデータが演算レジス
タ143₂に格納される。

順次各ケタに対応したパイプライン加算演算を行ない、
最終の第４（ｎ）ケタにおいては演算レジスタ143_4(n)
に格納されているデータを最上位ケタデータとし、また
演算レジスタ144_4(n)に格納されているデータを下位に
続くデータとしてメモリ110に出力する。

（Ｂ）実施例Ｉの動作 回路外より一定時間間隔で入力された画素の濃度値はサ
ンプリングレジスタ160でクロックCKに同期してサンプ
リングされ、入力レジスタ段121₀及びアドレス選択手段
150に供給される。いま、その入力画素をIPとする。

アドレス選択手段150は、入力画素IPの濃度値を選択
し、これを読出してアドレスとしてメモリ110の内容Ｓ
を読み出してメモリレジスタ170に格納する。

入力レジスタ段121₀には、入力画素IPの濃度値がサンプ
リングレジスタ160より１クロック遅れで格納され、メ
モリレジスタ170には、前記メモリ110の内容Ｓが同じく
サンプリングレジスタ160より１クロック遅れで格納さ
れる。

補正値発生手段130内の各比較器131j（ｊ＝１〜０）
は、入力レジスタ手段内の対応するレジスタ段121j（ｊ
＝１〜ｎ）の画素濃度値を入力画0000濃度値と比較し、
一致した場合に“1"を出力し、一致しない場合は“0"を
出力して補正値テーブル132に供給する。

補正値テーブル132は、各比較器131₁〜131_nより供給さ
れた“1"入力の加算値に１を加えた値を発生する。これ
により、画素IPの入力時点にパイプライン演算手段140
内において処理中のｎ個の入力画素中に入力画素IPと同
一濃度値の入力画素がｍ個あったとすると、それが検出
され補正値ｍ＋１となってパイプライン演算手段140に
加えられる。

パイプライン演算手段140は、メモリレジスタ170より入
力されたメモリ内容Ｓ及び補正値テーブル132より入力
された補正値ｍ＋１に基づき“Ｓ＋ｍ＋1"を出力する演
算処理を、第４図で説明したパイプライン処理により実
行する。

これにより、正しい濃度ヒストグラム値“Ｓ＋ｍ＋1"が
算出されて、演算レジスタ143_n及び144_nに格納される。
その時、入力レジスタ手段120内のレジスタ手段121_nに
は、入力画像IPの濃度値が前段から順次シフトされて格
納されている。

アドレス選択手段150は、レジスタ手段121_nの画素IPの
濃度値を選択し、これを書き込みアドレスとして演算レ
ジスタ143_n及び144_nに格納された濃度ヒストグラム“Ｓ
＋ｍ＋1"を、メモリ110に格納する。

更に詳細に動作を説明すると、時間ｔ＝t₀にサンプリン
グレジスタ160に濃度値が入力されて保持され、次のク
ロック入力時であるｔ＝t₀＋１で入力レジスタ段121₀に
移される。

一方、ｔ＝t₀でアドレス選択手段150はサンプリングレ
ジスタ160を選択して、濃度値をアドレスとしてメモリ1
10の記録を読出し、ｔ＝t₀＋１でメモリレジスタ170に
格納される。

また一方、ｔ＝t₀＋１においてアドレス選択手段150
は、サンプリングレジスタ160の出力を選択してメモリ1
10より記録の読出が終了すると、アドレス選択手段150
はレジスタ段121_nを選択してメモリ110のアドレス（濃
度値）を出力し、出力されたアドレスに対するメモリに
加算段141_nで加算されたＳ＋ｍ＋１を格納する。

以上の処理はサンプリングレジスタ160に入力される濃
度値が最終になるまで繰返され、メモリ110にヒストグ
ラム結果が記録される。

また、パイプライン演算手段140では、まず、ｔ＝t₀＋
１ではレジスタ段120₀に記録されている濃度値をアドレ
スとしたメモリ110に格納されている現在までのヒスト
グラムＳが読出されてメモリレジスタ170に記録され
る。また、補正値テーブル132よりｍ＋１が出力される
（補正値ｍ＋１については後で説明する）。

時間ｔ＝t₀＋２では、第４図で説明しているように、メ
モリレジスタ170に記録されている現在までのヒストグ
ラム値Ｓと補正値テーブル132より出力される補正値ｍ
＋１が加算段141₁に移されて、Ｓとｍ＋１の最下位桁
（第１桁）に対する加算が行なわれる。また、レジスタ
段121₀に記録されている濃度値はレジスタ段121₁に移さ
れる。

時間ｔ＝ｔ＋３では、Ｓとｍ＋１の第２桁の加算が行な
われる。

以下、下位桁より順次加算が行なわれ、ｔ＝ｔ＋ｎ＋１
で最上位の桁の加算が終了し、Ｓ＋ｍ＋１の加算結果が
得られる。

したがって、加算段141_jではレジスタ段121_jに記録され
ている濃度値に対するＳとｍ＋１の第ｊ桁の加算が実行
されている。

補正値テーブル132よりｍ＋１を出力させる理由につい
ては、ｔ＝t₀＋１でメモリ110より読出されてメモリレ
ジスタ170に記録されているヒストグラム値Ｓには、レ
ジスタ段121₀と同じ濃度値のものがレジスタ段121₁〜12
1_nの中に存在していても、その濃度値に対するヒストグ
ラム加算はＳの中に加算されていない。

したがって、補正値テーブル132では、レジスタ段121₀
に記録されている濃度値と同じ濃度値がレジスタ段121₁
〜121_nの中に記録されている個数ｍと自濃度に対する１
個を加えたｍ＋１を出力させている。

以上のパイプライン演算処理による画素濃度ヒストグラ
ム算出処理が、サンプリングレジスタ160からクロックC
Kに同期して各クロック毎に順次入力される各画素濃度
値に対してそれぞれ実行される。

〔実施例II〕

パイプライン演算手段の演算段が１段の場合は、実施例
Ｉの場合よりも回路の構成を簡単化することが出来る。
実施例IIは、パイプライン演算手段の演算手段が１段の
場合の実施例で、第３図は、実施例IIの構成をブロック
図で示したものである。

第３図において、入力レジスタ手段120補正値発生手段1
30及びパイプライン演算手段140を除いた他の構成、即
ちメモリ110、アドレス選択手段150、サンプリングレジ
スタ160及びメモリレジスタ170は、第２図と同じであ
る。

入力レジスタ手段120は、入力レジスタ段121₀及び１段
のレジスタ段121₁で構成される。

補正値発生手段130は、１個の比較器131で構成される。
比較器131は、入力レジスタ手段120内の入力レジスタ段
121₀とレジスタ段121₁との濃度値を比較し、一致してい
る場合は補正値“1"を発生し、一致していない場合は補
正値“0"を発生する。比較器131の出力がそのまま補正
値として使用出来るので、実施例Ｉの様に補正値テーブ
ルを設ける必要はない。パイプライン演算手段140は、
加算器142及び演算レジスタ143を備えた１段の演算段14
1で構成される。演算段141内の加算器142は、メモリレ
ジスタ170から入力された濃度ヒストグラム値Ｓに“1"
を加算すると共に、比較器131から入力された補正値の
加算を行い、その結果を演算レジスタ143に格納する。

以上の構成により、入力レジスタ段121₀の濃度値と演算
レジスタ143の濃度値が等しい場合には、加算器142にお
いて“Ｓ＋2"の加算処理が行われて正しい濃度ヒストグ
ラが算出される。

その他の動作は、実施例Ｉと同じであるので、その詳細
な動作説明は省略する。

以上、画像の濃度ヒストグラムを算出する場合の各実施
例について説明したが、本発明は、これらの実施例に限
定されるものでなく、各種の入力の濃度ヒストグラムの
算出処理に用いることが出来るものである。

〔発明の効果〕

以上説明した様に、本発明によれば次の諸効果が得られ
る。

（イ）算出された濃度ヒストグラムをメモリに格納する
場合の濃度ヒストグラム算出処理をパイプライン化する
ことが出来る。

（ロ）従って、小規模且つ安価な構成で高速処理が可能
な濃度ヒストグラム算出回路を実現することが出来る。

【図面の簡単な説明】

第１図……本発明の基本構成の説明図、 第２図……本発明の実施例Ｉの構成の説明図、 第３図……本発明の実施例IIの構成の説明図、 第４図……本発明の実施例Ｉのパイプライン演算手段の
具体例。 第１図〜第４図において、 110……メモリ、120……入力レジスタ手段、130……補
正値発生手段、140……パイプライン演算手段、150……
アドレス選択手段、160……サンプリングレジスタ、170
……メモリレジスタ。

Claims (1)

【特許請求の範囲】
1. 【請求項１】濃度ヒストグラムの算出結果が格納される
   メモリと、 パイプライン演算手段の演算段数に対応した数のレジス
   タ段を有し、濃度値を入力データとし順次シフトして格
   納される入力レジスタ手段と、 入力レジスタ手段の各レジスタ段に格納されている濃度
   値に基づいて濃度ヒストグラムを算出するための補正値
   を発生する補正値発生手段と、 入力濃度値に基づいて読み出されたメモリの内容と前記
   補正値を入力としてパイプライン処理により濃度ヒスト
   グラムを算出するパイプライン演算手段と、 入力濃度値をメモリに対する読出しアドレスとして選択
   し、入力レジスタ手段から出力された濃度値をパイプラ
   イン演算手段の算出結果をメモリに格納する書込みアド
   レスとして選択するアドレス選択手段と、 を備えたことを特徴とするパイプラインヒストグラム算
   出回路。