米国特許情報 | 欧州特許情報 | 国際公開(PCT)情報 | Google の米国特許検索
 
     特許分類
A 農業
B 衣類
C 家具
D 医学
E スポ−ツ;娯楽
F 加工処理操作
G 机上付属具
H 装飾
I 車両
J 包装;運搬
L 化学;冶金
M 繊維;紙;印刷
N 固定構造物
O 機械工学
P 武器
Q 照明
R 測定; 光学
S 写真;映画
T 計算機;電気通信
U 核技術
V 電気素子
W 発電
X 楽器;音響


  ホーム -> 計算機;電気通信 -> キヤノン株式会社

発明の名称 正規乱数生成装置
発行国 日本国特許庁(JP)
公報種別 公開特許公報(A)
公開番号 特開2007−4358(P2007−4358A)
公開日 平成19年1月11日(2007.1.11)
出願番号 特願2005−181902(P2005−181902)
出願日 平成17年6月22日(2005.6.22)
代理人 【識別番号】100090538
【弁理士】
【氏名又は名称】西山 恵三
発明者 堤 隆之
要約 課題
ハードウェアの増大を抑えながら、良質な正規分布特性を有し、自己相関を軽減した正規乱数を発生させることができる。これにより近傍の自己相関による画質劣化を防ぐことができ、良質な画質を得ることができる。

解決手段
画像処理において、正規分布特性を有する乱数信号を生成する正規乱数生成装置であって、M系列生成手段より抽出したビット値をビット反転手段、ビット位置入れ替え手段、上記M系列生成手段の上位ビットの値より排他論理和を行う論理演算手段により複数の一様乱数を生成する一様乱数生成手段と、上記複数の一様乱数を用いて正規乱数を生成する正規乱数生成手段を備えた正規乱数生成装置。
特許請求の範囲
【請求項1】
画像処理において、正規分布特性を有する乱数信号を生成する正規乱数生成装置であって、
M系列生成手段より抽出したビット値をビット反転手段、ビット位置入れ替え手段、上記M系列生成手段の上位ビットの値より排他論理和を行う論理演算手段により複数の一様乱数を生成する一様乱数生成手段と、
上記複数の一様乱数を用いて正規乱数を生成する正規乱数生成手段を備えた正規乱数生成装置。
【請求項2】
上記排他論理和を行う論理演算手段によって生成されたビット値は上記一様乱数の上位ビットの値になることを特徴とする、請求項1記載の正規乱数生成装置。
【請求項3】
上記一様乱数生成手段は、所定の周期を有するM系列巡回符号乱数を生成するM系列生成手段により構成されている請求項1記載の正規乱数生成装置。
【請求項4】
上記一様乱数生成手段は、一つのM系列生成手段から複数の一様乱数を生成することを特徴とする、請求項1記載の正規乱数生成装置。
【請求項5】
上記M系列生成手段に設定された初期値は、夫々が異なる値であることを特徴とする、請求項1記載の正規乱数生成装置。
発明の詳細な説明
【技術分野】
【0001】
本発明は乱数生成装置に関し、特に、正規分布特性を有する正規乱数の生成装置に関する。
【背景技術】
【0002】
正規乱数生成手段として、主にボックスミューラ法、極座標法、中心極限定理を利用する手段がある。また、上記正規乱数生成手段のための要素となる一様乱数生成手段は、主に線形合同法、M系列巡回符号を利用した手段がある〔非特許文献1〕。正規乱数生成装置を実現する際には、回路のハードウェアの量を増大させないために、上記正規乱数生成手段として上記中心極限定理を利用する手段と、上記一様乱数生成手段としてM系列巡回符号を利用した手段がよく用いられる。
【非特許文献1】三上直樹、「アルゴリズム教科書-実用的なプログラミングで示すアルゴリズムの基礎と応用」1996/5 初版
【発明の開示】
【発明が解決しようとする課題】
【0003】
画像処理において、量子化雑音によるモアレを目立ちにくくするために、入力されたCMYK 4色の画像データに対して、意図的にノイズを加算することが行われる。
【0004】
しかし、従来技術のアルゴリズム、特に上記正規乱数生成手段として上記中心極限定理を利用する手段と、上記一様乱数生成手段としてM系列巡回符号を利用した手段のみを用いて正規乱数を生成し、上記正規乱数を上記ノイズとして使用するならば、正規乱数の自己相関が大きくなり、画質劣化が起きてしまう。周期相関による画質劣化を避けるために所望の画素数内で正規乱数の自己相関が出ないようなビット長のM系列巡回符号生成器を複数備え、上記M系列巡回符号生成器の一部から一様乱数を生成し、中心極限定理に従って、上記一様乱数を用いて正規乱数を生成したとしても近傍の自己相関による画質劣化が起きてしまう。例えば、一様乱数生成器を説明する図8に示すように、A3サイズで1インチ1200画素数について1画素おきに乱数を加算する場合、M系列巡回符号生成器の周期相関による画質劣化しないように一様乱数を生成に28ビット長のM系列巡回符号生成器102を用いる。ここで101は28ビット長のM系列巡回符号生成器102の初期値を設定するシードレジスタである。28ビット長のM系列巡回符号生成器102を用いて一様乱数103を生成する。そしてシードレジスタの値が違ったM系列巡回符号生成器から一様乱数を複数生成し、中心極限定理に従って、正規乱数を生成することができる。だが、近傍の正規乱数自己相関の影響により画質劣化が起きてしまう。28ビットのビット幅を持つ上記 M系列巡回符号生成器で生成した正規乱数の自己相関は図9になる。注目乱数の周辺10〜20個程度の乱数に関する自己相関が強くなっている。そして図10で示すような画像の主走査方向に細かい横線が生成されてしまうといった画質劣化が起こる。
【0005】
以上の画質劣化を防ぐために、〔特開平11-85474号〕に示されるように、一様乱数に使用するM系列巡回符号生成器とは別に、同じビット幅を持つ他のM系列巡回符号生成器を用意(以下、EXOR発生器と呼ぶ)し、これらの乱数列をそれぞれのビットごとの排他論理和を取る手法があるが、上記EXOR発生器の分だけ回路規模が増大してしまう。また上記EXOR発生器自体がM系列巡回符号であるため、同じ値が連続して出力されてしまうことがあり、必ずしも自己相関のない、良質な正規乱数を生成できるとは限らない。
【課題を解決するための手段】
【0006】
画像処理において、正規分布特性を有する乱数信号を生成する正規乱数生成装置であって、M系列生成手段より抽出したビット値をビット反転手段、ビット位置入れ替え手段、上記M系列生成手段の上位ビットの値より排他論理和を行う論理演算手段により複数の一様乱数を生成する一様乱数生成手段と、上記複数の一様乱数を用いて正規乱数を生成する正規乱数生成手段を備ることを特徴とする。
【0007】
また、上記排他論理和を行う論理演算手段によって生成されたビット値は上記一様乱数の上位ビットの値になることを特徴とする。
【0008】
また、上記一様乱数生成手段は、所定の周期を有するM系列巡回符号乱数を生成するM系列生成手段により構成されている事を特徴とする。
【0009】
また、上記一様乱数生成手段は、一つのM系列生成手段から複数の一様乱数を生成することを特徴とする。
【0010】
また、上記M系列生成手段に設定された初期値は、夫々が異なる値であることを特徴とする。
【発明の効果】
【0011】
本発明の正規乱数生成装置によれば、ハードウェアの増大を抑えながら、良質な正規分布特性を有し、自己相関を軽減した正規乱数を発生させることができる。これにより近傍の自己相関による画質劣化を防ぐことができ、良質な画質を得ることができる。
【発明を実施するための最良の形態】
【0012】
(第一の実施形態)
図1に本発明の正規乱数生成装置の一様乱数生成法の概略を示す。
【0013】
11は、28ビットのシード値を格納するシードレジスタ、
12は、28ビット長のM系列巡回符号生成器、
13、14は、12ビット一様乱数、
15は、並べ替え回路、
16は、排他処理回路、
17は、反転回路。
【0014】
以上の構成において、
11は28ビットのシード値を格納するシードレジスタである。12は28ビット長のM系列巡回符号生成器であり、シードレジスタ11に格納されたシード値を初期値として動作する。28ビット長M系列巡回符号生成器12は28ビットM系列巡回符号であり、数字はビット番号を示している。28ビット長M系列巡回符号生成器12からビットを抽出し、並べ替え回路15によって抽出したビットを不連続に並べ替えをし、排他処理回路16で28ビット長M系列巡回符号生成器12の上位ビットの値と、他の任意のビット値とをエクスクルーシブORをとり、生成する一様乱数13,14の上位2ビットとする。そして反転回路17で任意のビットを反転させ、一様乱数13,14を生成する。この時の一様乱数13と一様乱数14はお互いの相関を無くすために28ビット長M系列巡回符号生成器12から抽出するビット番号が重ならないようにしている。また、28ビット長M系列巡回符号生成器12から2つの一様乱数を生成することで、シードの設定し易くし、回路規模を削減している。
【0015】
次に図2に前述の一様乱数生成法を用いた一様乱数生成部の概略を示す。
【0016】
A21〜A26は、シードレジスタ、
B21〜B26は、28ビット長のM系列巡回符号生成器、
C21〜C26は、並べ替え回路、
D21〜D26は、排他処理回路、E21〜E26は、反転回路、
以上の構成において、
A21は、シードレジスタで各々値が異なる。シードレジスタA21を28ビット長のM系列巡回符号生成器B21の初期値とし、前述した手法により一様乱数u0 [11:0]及びu1 [11:0]を生成させる。この時の並べ替え回路C21の手法は図1の15と等しく、排他処理回路D21の手法は図16と等しく、反転回路の手法は図17と等しい。
【0017】
以下u0 [11:0]及びu1 [11:0]は(式1)、(式2)によって表される。
u0[11:0]=[22xor27,not(7xor 25),11,not(2),not(18),1,not(3),not(14),23,9,21,not(10)]
(式1)
u1[11:0]=[5xor26,not(20xor 24),not(8),not(16),not(19),0,not(12),not(17),4,not(6),13,not(15)]
(式2)
(式1)の右辺の表記は、数字が28ビット長M系列巡回符号生成器12のビット番号であり、notが上記ビット番号のビット値の反転処理を、xor が排他論理和を行う論理演算を行っていることを意味している。(式2)についても表記法は(式1)と同じである。
【0018】
一様乱数u2 [11:0] u4 [11:0] u6 [11:0] u10 [11:0]は(式1)と、u3 [11:0] u5 [11:0] u7 [11:0] u9 [11:0]u11 [11:0]は(式2)と、生成法が同じである。ただし、シードレジスタA21〜A26に設定されている値は各々異なる。
【0019】
図3に本発明の正規乱数生成装置の概略を示す。
【0020】
31は、CPU等からの設定を格納するレジスタ部、
32は、他のブロックの動作シーケンス制御を行う制御部、
33は、一様乱数を生成する一様乱数生成部、
34は、上記一様乱数部で生成された一様乱数を入力とし、正規乱数を生成する正規乱数生成部、
35は、上記正規乱数生成部から生成した正規乱数をスケーリングするスケーリング部、
36は、加算器、
37は、10ビット出力にするリミッタ。
【0021】
上記構成において、
本発明の第一の実施形態を図1のブロック図を用いて説明する。
【0022】
31はレジスタ部であり、CPU等からの設定値dataを格納し、他のブロックに供給する。32は制御部であり他のブロックの動作シーケンスの制御を行う。33は一様乱数生成部であり、前述図2を用いて説明した。28ビット長M系列巡回符号生成器6個備え、12ビットの一様乱数を12個抽出して出力する。ここで、一様乱数のビット長は、後述する加算器36における乱数加算値のビット長10ビット以上の値が必要であるため、後述するスケーリング部35での演算誤差等を考えて12ビットとしている。
【0023】
34は正規乱数生成部あり、中心極限定理に従って、一様乱数生成部33からの12個の一様乱数を加算して出力する。
【0024】
ここで、一様乱数生成部33から出力される一様乱数をuk(k=0〜11)とすると正規乱数xは(式3)で算出される。
【0025】
【数1】


【0026】
よってx=-24570〜24570(16 ビット)となる。35はスケーリング部であり、正規乱数生成部34から出力された16 ビットの正規乱数に対して、スケーリングを行い、10 ビットの乱数加算値を生成する。
【0027】
図4にスケーリングの一例を示す。図4では、3σの値を255にスケーリングすることにより、正規乱数の最大値の6σが510にスケーリングされる。よって符号ビットも含めて10 ビットの乱数加算値が生成される。
【0028】
36は加算器であり、スケーリング部35から出力された10ビットの乱数加算値と、明示していない前段のガンマ変換処理の10ビットの出力濃度値Din(正の数0〜1023)との加算を行う。37はリミッタであり、加算器36からの11ビットの濃度値に対して負の値と1023より大きい値に対して夫々、0、1023へのクリッピング処理を行う。リミッタ37の出力は10ビットの濃度値Doutとして、図示していない後段の誤差拡散処理に出力される。
【0029】
尚、本実施例では、28ビット長のM系列巡回符号生成器に関して説明したが、所望の画像領域での乱数の自己相関が問題にならないようなビット長を選択すれば、28ビット以外のビット長のものに対しても本発明が適用できることは言うまでも無い。
【0030】
図5を用いて、カラー複写機の処理を説明する。
【0031】
図5において51はカラー複写機のイメージリーダー部などのカラー画像入力手段である。52は対数変換部であり、入力されたRGB3色の画像データに対して濃度リニアな信号に変換する。53は色空間変換部であり、入力されたRGB3色の画像データに対して、CMYK 4色の画像データに変換する。54はカラーバランス補正部であり、入力されたCMYK 4色の画像データに対して夫々の濃度値のバランスを補正する。55は本発明の乱数加算処理部であり、後段の擬似中間調処理部において量子化雑音によるモアレを目立ちにくくするために、入力されたCMYK 4色の画像データに対して、意図的に一様乱数や正規乱数を小雑音として加算する。56は出力ガンマ補正部であり、入力されたCMYK 4色の画像データに対して、後述するカラー画像出力部の特性に合わせたガンマ補正を行う。57は擬似中間調処理部であり、入力されたCMYK 4色の画像データに対して、誤差拡散処理などの擬似中間調処理を行う。58は平滑化処理部であり、入力されたCMYK 4色の画像データに対して、ジャギーを軽減して滑らかにするスムージング処理を行う。59はプリンタなどの画像出力部であり、入力されたCMYK 4色の画像データの印刷を行う。
【0032】
次に、処理フローを説明する。カラー画像入力手段51により入力された画像データR1, G1, B1は対数変換部52において対数変換された後、画像データR2, G2, B2として色空間変換部53に入力される。そして、色空間変換部53で色空間変換された画像データC1, M1, Y1, K1はカラーバランス補正部54に入力される。その後、カラーバランス補正部54でカラーバランスが補正された画像データC2, M2, Y2, K2は乱数加算処理部55に入力される。そして、乱数加算処理部55で乱数が加算された画像データC3, M3, Y3, K3は出力ガンマ補正部56に入力される。その後、出力ガンマ補正部56にてガンマ補正が行われた画像データC4, M4, Y4, K4は平滑化処理部58に入力される。そして、平滑化処理部58にてスムージング処理が行われた画像データC5, M5, Y5, K5はカラー画像出力部59に入力され、印刷が行われる。
【0033】
本発明の正規乱数生成装置によれば、ハードウェアの増大を抑えながら、良質な正規分布特性を有し、自己相関を軽減した正規乱数を発生させることができる。これにより近傍の自己相関による画質劣化を防ぐことができ、良質な画質を得ることができる。正規乱数生成装置を利用した例を次に示す。図6は本発明による正規乱数生成装置の正規乱数自己相関を表した図である。図7は本発明の正規乱数発生装置による出力である。
【図面の簡単な説明】
【0034】
【図1】本発明の第一実施形態の一様乱数生成手法を説明する図である。
【図2】本発明の第一の実施形態の一様乱数生成部を説明する図である。
【図3】本発明の第一実施形態の本発明の正規乱数生成装置を説明する図である。
【図4】本発明のスケーリング部の動作を説明する図である。
【図5】カラー複写機の処理を説明する図である。
【図6】本発明の第一実施形態の正規乱数自己相関を表した図である。
【図7】本発明の第一実施形態の出力結果を表した画像の写真を示す図である。
【図8】従来技術を用いた一様乱数生成法を説明する図である。
【図9】従来技術を用いた実施形態の正規乱数自己相関を表した図である。
【図10】従来技術を用いた実施形態の出力結果を表した画像の写真を示す図である。




 

 


     NEWS
会社検索順位 特許の出願数の順位が発表

URL変更
平成6年
平成7年
平成8年
平成9年
平成10年
平成11年
平成12年
平成13年


 
   お問い合わせ info@patentjp.com patentjp.com   Copyright 2007-2013