(57)【要約】最適ビデオ処理システム設計を得る方法及び装置は、（ａ）（i）パフォーマンスについての最良の染色体及び関連する適応度を有するビデオサンプル候補を見つけるのに遺伝的アルゴリズムを用いる段階と、（ii）局所探索スキームで段階（ａ）（i）からの適応度に基づいて局所最適値を見つけるよう確率的方法を用いる段階とを含む。確率的方法の結果は、速度を高めるために遺伝的アルゴリズムに挿入され、遺伝的アルゴリズムのみが使用された場合よりも処理要件を減少させる。確率的方法によって見つかった局所最適値を用いて遺伝的アルゴリズムから得られる結果は、ビデオ処理システム及びビデオモジュールのうちの１つへ出力されうる。これを行うための装置及びシステム用のハードウエアは、ビデオ源入力、プロセッサ、遺伝的アルゴリズムモジュール、確率的探索モジュール、メモリ、及び少なくとも１つのビデオモジュールを含む。【特許請求の範囲】
【請求項１】
（ａ）（i）パフォーマンスについての最良の染色体及び関連する適応度を有するビデオサンプル候補を見つけるのに遺伝的アルゴリズムを用いる段階と、
（ii）局所探索スキームで前記段階（ａ）（i）からの前記適応度に基づいて局所最適値を見つけるよう確率的方法を用いる段階とを有する、
ハイブリッド法を実行する段階と、
（ｂ）遺伝的アルゴリズムによる更なる処理のために前記段階（ａ）（ii）で得られた結果を与える段階と、
（ｃ）前記段階（ｂ）で得られた結果をビデオ処理システム及びビデオモジュールのうちの一方へ与える段階とを有する、
最適ビデオ処理システム設計を得る方法。
【請求項２】
（ａ）パフォーマンスについての最良の染色体を有するビデオサンプル候補を見つけるのに遺伝的アルゴリズムを用いる段階と、
（ｂ）前記ステップ（ａ）において見つかった最良の染色体及び関連する適応度をメモリに記憶する段階と、
（ｃ）（i）所定の回数、及び、（ii）所定の適応度のうちの一方の間、複数の染色体を得るよう前記段階（ａ）及び（ｂ）を繰り返す段階と、
（ｄ）前記段階（ｂ）においてメモリに記憶された前記適応度に基づいて局所最適値を見つけるよう確率的方法を用いる段階と、
（ｅ）前記メモリに局所最適値を挿入する段階と、
（ｆ）前記段階（ｅ）で得られた前記局所最適値を用いて遺伝的アルゴリズムを実行する段階とを有する、
最適ビデオ処理システム設計を得る方法。
【請求項３】
前記ステップ（ｅ）において得られた値をビデオモジュール及びビデオ処理モジュールのうちの一方へ与える段階を更に有する、請求項２記載の方法。
【請求項４】
前記確率的方法は、以下の式に従って確率ベクトルを作り、即ち、
【数１】
2005533307.tif 000005
但し（０＜ｌ＜Ｋ＋１、ｌは整数）であり、且つ、
【数２】
2005533307.tif 000006
であり、
（外１）
2005533307.tif 000007
は、確率のベクトルであり、その次数はｋであり、任意のビットｌの値が局所最良染色体において１に等しくなる確率を示し、任意のビットｌ（０＜ｌ＜ｋ＋１、ｌは整数）が時間ｔ＋ｎにおいてｌに等しい確率はＰl（ｔ＋ｎ）であり、前記任意のビットの値（１又は０）と過去ｎ世代の染色体適応度の加重積の正規化された和として定義される、請求項２記載の方法。
【請求項５】
前記確率ベクトルは、最も高い適応度を有する所定数の最近のビデオ処理解の値を含む、請求項４記載の方法。
【請求項６】
ビデオ源入力と、
前記ビデオ源入力と通信するプロセッサと、
遺伝的アルゴリズムと確率的探索を夫々行う遺伝的アルゴリズムモジュール及び確率的探索モジュールと、
染色体及び関連する適応度の夫々の値を記憶するよう前記プロセッサ並びに前記遺伝的アルゴリズムモジュール及び確率的探索モジュールと通信するメモリとを有し、
前記確率的探索モジュールは前記遺伝的アルゴリズムモジュールによって記憶されたデータを前記メモリから取り出し、局所最適値を得るよう探索を行い、その結果は前記遺伝的アルゴリズムモジュールによる更なる処理のために前記メモリに記憶される、
最適ビデオ処理システム設計を得る装置。
【請求項７】
前記プロセッサは、最適パラメータを少なくとも１つのビデオモジュールへ与える出力手段を更に有する、請求項６記載の装置。
【請求項８】
前記確率的探索モジュールは、以下の式に従って探索を行い、即ち、
【数３】
2005533307.tif 000008
但し（０＜ｌ＜Ｋ＋１、ｌは整数）であり、且つ、
【数４】
2005533307.tif 000009
であり、
（外２）
2005533307.tif 000010
は、確率のベクトルであり、その次数はｋであり、任意のビットｌの値が局所最良染色体において１に等しくなる確率を示し、任意のビットｌ（０＜ｌ＜ｋ＋１、ｌは整数）が時間ｔ＋ｎにおいてｌに等しい確率はＰl（ｔ＋ｎ）であり、前記任意のビットの値（１又は０）と過去ｎ世代の染色体適応度の加重積の正規化された和として定義される、請求項６記載の装置。
【請求項９】
（i）パフォーマンスについての最良の染色体及び関連する適応度を有するビデオサンプル候補を見つけるのに遺伝的アルゴリズムを用いること、及び、
（ii）局所探索スキームで前記段階（i）からの前記適応度に基づいて局所最適値を見つけるよう確率的方法を用いることにより、
最適化のためにハイブリッド法を実行する手段と、
（ｂ）遺伝的アルゴリズムによる更なる処理のために前記段階（ａ）（ii）で得られた結果を与える手段と、
（ｃ）前記段階（ｂ）で得られた結果をビデオ処理システム及びビデオモジュールのうちの一方へ与える手段とを有する、
最適ビデオ処理設計を得るシステム。
【請求項１０】
パフォーマンスについての最良の染色体を有するビデオサンプル候補を見つける遺伝的アルゴリズム手段と、
前記遺伝的アルゴリズム手段によって見つかった最良の染色体を記憶し、関連する適応度をメモリに記憶する記憶手段と、
前記記憶手段メモリに記憶された前記適応度に基づいて局所最適値を見つけるよう確率的探索を与える手段と、
前記メモリに局所最適値を挿入する手段とを有し、
前記遺伝的アルゴリズム手段は、前記確率的探索を与える手段によって得られる値を用いる、
最適ビデオ処理システム設計を得るシステム。
【請求項１１】
前記遺伝的アルゴリズム手段は、前記確率的探索手段によって得られる前記局所最適値を用いて得られる値をビデオモジュール及びビデオ処理モジュールのうちの一方へ与える、請求項１０記載のシステム。
【請求項１２】
前記確率的探索を与える手段は、以下の式に従って確率ベクトルを作り、即ち、
【数５】
2005533307.tif 000011
但し（０＜ｌ＜Ｋ＋１、ｌは整数）であり、且つ、
【数６】
2005533307.tif 000012
であり、
（外３）
2005533307.tif 000013
は、確率のベクトルであり、その次数はｋであり、任意のビットｌの値が局所最良染色体において１に等しくなる確率を示し、任意のビットｌ（０＜ｌ＜ｋ＋１、ｌは整数）が時間ｔ＋ｎにおいてｌに等しい確率はＰl（ｔ＋ｎ）であり、前記任意のビットの値（１又は０）と過去ｎ世代の染色体適応度の加重積の正規化された和として定義される、請求項１０記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ビデオ処理システム設計及びかかるシステムを得る方法を最適化することに関連する。より特定的には、本発明は確率的方法を用いたかかるシステムの設計に関連する。
【背景技術】
【０００２】
ビデオ処理システムは、最良の画質に達するよう互いに影響し合う多数のビデオモジュールから構成される。各モジュールについての最良の設定について決定するにはかなりの困難性がある。実際には、モジュール設定の正しさを確認するための形式の決まった方法はない。むしろ、システム設計者は、ビデオモジュールを適合させるために特別な技術と自分たちの経験を用いてきた。より最近のハードウエアパラダイムは、多くの異なったアーキテクチャ構造を許すため、連結性について、より多くの可能性がある。従って、最良連結性スキームについて決定するうえで、より高い自由度がある。
【０００３】
形式の決まった方法でのビデオモジュールの設定に関する課題を解決するために、ビデオ処理システムを最適化する進化した枠組みとして遺伝的アルゴリズム（ＧＡ）を用いる方法が提案されている。ビデオの質を評価するのに使用されえ、ビデオの質が向上されるフィードバックシステムの一部であってもなくともよい遺伝的アルゴリズムは、ここに背景技術として参照として組み入れられる、本願発明者による２つの文献、即ち、「A  General  Scheme  for  Diffusing  Different  Implementations  of  a  Number  of  Video  Algorithms  in  an  Optimum  Way  for  Best  Objective  Video  Quality」なる名称の米国特許出願第０９／８１７，８９１号明細書（２００１年３月２７日出願）、及び、「A  Scalable  Dynamic  Metric  for  Automatic  Evaluation  of  Video  Quality」なる名称の米国特許出願第０９／７３４，８２３号明細書（２０００年１２月１２日出願）で提案されている。
【０００４】
遺伝的アルゴリズムは、遺伝子プールの多様性は変化する環境下での個体群（population）の生存を確実とするのに役立つ、という概念に基づく。ＧＡ手順は反復的であり、候補解の個体群を染色体配列（chromosome  string）の形で維持する。初期個体群は、ランダムに又はヒューリスティックに選択されうる。各世代において、候補は、評価され、続いて適応度（fitness  value）が割り当てられ、適応度に基づき後の世代における複製のために選択される。
【０００５】
従って、ＧＡは、かなりの処理パワー能力を必要とする計算的に貪欲な方法である。結果として、ＧＡのハイブリッド探索エンジン及びあまり複雑でない探索エンジンを用いる試みがされてきた。
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、この技術分野では、依然として、現在の状態よりもビデオ処理システム設計を改善することが要請されている。
【課題を解決するための手段】
【０００７】
本発明は、システムの調整（tuning）が使用されうる様々な状態を探索空間としてモデリングするビデオ処理システム設計を与える方法及び装置を提供する。探索空間は網羅的に調べるには大きすぎるため、本発明の面は、探索空間の局所近傍における最良のサンプルの確率パターンに基づいて、局所探索法をより速く局所最適値に合わせて調整するために確率的な方法を用いることを含む。確率パターンからの最良のサンプルは、続いて交叉（crossover）及び突然変異（mutation）のために遺伝的アルゴリズムに続いて再び挿入される。従って、新しい方法は、ＧＡの最も良い特徴（例えば局所最適値に陥らないこと）及び確率的な局所探索法の特徴（最良の局所最適値を見つける）を引き出すためのハイブリッド形成である。
【発明の効果】
【０００８】
従って、本発明は、遺伝的アルゴリズムのみを用いた場合よりも高速に局所最適値を見つける。
【発明を実施するための最良の形態】
【０００９】
当業者によれば、ＧＡの使用により、交叉及び突然変異によって個体群内で得られた最適解の「良さ（goodness）」（又は、適応性（fitness））を保ちつつ、解に変動性が与えられることが理解されるべきである。解は、染色体（chromosome）と称される２値パターンによって表わされる。例えば、問題の解はｋビットからなる染色体によって表わされる。ＧＡは１つの世代（個体群）内のサンプルの全体集合をテストすることにより改善されるため、サンプルの個体群はパフォーマンスの順にソートされうる。
【００１０】
図１Ａ及び図１Ｂは、本発明の概観を示すフローチャートである。ステップ１００において、遺伝的アルゴリズムは、パフォーマンスに対する最良の染色体を有するビデオサンプル候補を見つけるのに用いられる。ステップ１０５において、最良の染色体はメモリ装置に記憶される。関連する適応度ｆもまた各染色体に対して記憶される。ステップ１１０は、所定の回数、世代、及び／又は、適応度スコア規準に達するまでステップ１００及び１０５を繰り返す。１回目が時間＝ｔにおけるものであり、次の世代はｔ＋１であるとすると、閾値はｔ＋ｎであり、ｆ0、ｆ1、及びｆnの適応度を有しうる。
【００１１】
図２は、ステップ１００乃至１１０からの情報が表わされうる１つの表し方を示す表である。各世代（ｔ）の染色体は、長さがｋビットからのものである。関連する適応度もまた図示されている。
【００１２】
ステップ１１５において、ステップ１０５でメモリに記憶された値に基づき局所最適値を見つけるよう確率的な方法が使用される。このステップは、第１のステップにおいて用いられるＧＡのより「貪欲な」計算方法から離れ、最良の局所最適解を迅速に得るためのより高速な局所直接探索法に近づく、ハイブリッド生成（hybridization）の一種である。ベクトルは、ＧＡが最適解へ向かって進化するという仮定を用いて作られ、即ち、
【００１３】
【数７】
2005533307.tif 000002
但し（０＜ｌ＜Ｋ＋１、ｌ（英字のエル）は整数）（式１）であり、且つ、
【００１４】
【数８】
2005533307.tif 000003
である。
【００１５】
（外４）
2005533307.tif 000004
は、確率のベクトルであり、その次数はｋであり、任意のビットｌ（エル）の値が局所最良染色体において１に等しくなる確率を示す。任意のビットｌ（０＜ｌ＜ｋ＋１、ｌ（エル）は整数）が時間ｔ＋ｎにおいてｌ（エル）に等しい確率はＰl（ｔ＋ｎ）であり、このビットの値（１又は０）と過去ｎ世代の染色体適応度の加重積の正規化された和として定義される。
【００１６】
従って、時間ｔ＋ｎにおいて、確率ベクトルＰt+nがあり、任意のビット（ビットｌ、０＜ｌ＜ｋ＋ｌ、ｌは整数）の確率で２値染色体を引き出すことができ、式１は、ベクトルＰt+nで示されるようにこのビットの確率によって決定される。
【００１７】
ステップ１２０において、上述のような確率的方法からの局所最適値を交叉及び突然変異を行う遺伝的アルゴリズムへ挿入する。
【００１８】
最後に、ステップ１２５において、方法から得られる値は、設計を最適化するよう、ビデオ処理システム及び／又はビデオモジュールのうちのいずれかに与えられる。
【００１９】
図３は、本発明による最適なビデオ処理設計を得るための装置及び／システムを示す図である。ビデオ源３０２は、プロセッサ３０５によって受け取られる。遺伝的アルゴリズムは遺伝的アルゴリズムモジュール３１０によって実行されえ、局所最適値は確率的探索モジュール３２０によって与えられうる。Ｇ．Ａ．モジュール３１０と確率的探索モジュールは単一モジュールであることも可能である。ｔ乃至ｔ＋ｎの染色体は、適応度ｆと共にメモリ３１５に記憶される。確率的探索モジュール３２０が局所最適値を与えた後、これらの値はＧ．Ａ．モジュール３１０へ戻される。更なる処理（即ち、交叉及び突然変異）の後、ビデオモジュール３２５、３３０は、最適化されたパラメータを受け取ることができる。当業者によれば、ビデオモジュールの数は２つよりも多くとも少なくともよいことが理解されるべきである。
【００２０】
当業者により、本発明の趣旨又は添付の特許請求の範囲の範囲を逸脱することなく、様々な変更がなされうる。
【図面の簡単な説明】
【００２１】
【図１Ａ】本発明による方法の概観を示すフローチャートである。
【図１Ｂ】本発明による方法の概観を示すフローチャートである。
【図２】最近の最良のサンプル染色体を示す表である。
【図３】本発明による装置の１つの実施例を示すブロック図である。
2005533307.tif 000014
【図２】
2005533307.tif 000015
【図３】
2005533307.tif 000016
【手続補正書】
【提出日】平成17年2月3日(2005.2.3)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項４
【補正方法】変更
【補正の内容】
【請求項４】
前記確率的方法は、以下の式に従って確率ベクトルを作り、即ち、
【数１】
2005533307.tif 000017
但し（０＜ｌ＜Ｋ＋１、ｌは整数）であり、且つ、
【数２】
2005533307.tif 000018
であり、
（外１）
2005533307.tif 000019
は、確率のベクトルであり、その次数はｋであり、任意のビットｌの値が局所最良染色体において１に等しくなる確率を示し、任意のビットｌ（０＜ｌ＜ｋ＋１、ｌは整数）が時間ｔ＋ｎにおいてｌに等しい確率はＰl（ｔ＋ｎ）であり、前記任意のビットの値（１又は０）と過去ｎ世代の染色体適応度の加重積の正規化された和として定義される、請求項２記載の方法。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項８
【補正方法】変更
【補正の内容】
【請求項８】
前記確率的探索モジュールは、以下の式に従って探索を行い、即ち、
【数３】
2005533307.tif 000020
但し（０＜ｌ＜Ｋ＋１、ｌは整数）であり、且つ、
【数４】
2005533307.tif 000021
であり、
（外２）
2005533307.tif 000022
は、確率のベクトルであり、その次数はｋであり、任意のビットｌの値が局所最良染色体において１に等しくなる確率を示し、任意のビットｌ（０＜ｌ＜ｋ＋１、ｌは整数）が時間ｔ＋ｎにおいてｌに等しい確率はＰl（ｔ＋ｎ）であり、前記任意のビットの値（１又は０）と過去ｎ世代の染色体適応度の加重積の正規化された和として定義される、請求項６記載の装置。
【手続補正３】
【補正対象書類名】特許請求の範囲
【補正対象項目名】請求項１２
【補正方法】変更
【補正の内容】
【請求項１２】
前記確率的探索を与える手段は、以下の式に従って確率ベクトルを作り、即ち、
【数５】
2005533307.tif 000023
但し（０＜ｌ＜Ｋ＋１、ｌは整数）であり、且つ、
【数６】
2005533307.tif 000024
であり、
（外３）
2005533307.tif 000025
は、確率のベクトルであり、その次数はｋであり、任意のビットｌの値が局所最良染色体において１に等しくなる確率を示し、任意のビットｌ（０＜ｌ＜ｋ＋１、ｌは整数）が時間ｔ＋ｎにおいてｌに等しい確率はＰl（ｔ＋ｎ）であり、前記任意のビットの値（１又は０）と過去ｎ世代の染色体適応度の加重積の正規化された和として定義される、請求項１０記載のシステム。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
【数８】
2005533307.tif 000026
である。
【国際調査報告】
2005533307.tif 000027
2005533307.tif 000028
2005533307.tif 000029