TOP > 国内特許検索 > 最適平滑化スプラインによる極値検出方法及び極値検出プログラム > 明細書

明細書 :最適平滑化スプラインによる極値検出方法及び極値検出プログラム

発行国 日本国特許庁(JP)
公報種別 特許公報(B2)
特許番号 特許第4669993号 (P4669993)
公開番号 特開2007-128237 (P2007-128237A)
登録日 平成23年1月28日(2011.1.28)
発行日 平成23年4月13日(2011.4.13)
公開日 平成19年5月24日(2007.5.24)
発明の名称または考案の名称 最適平滑化スプラインによる極値検出方法及び極値検出プログラム
国際特許分類 G06T   7/60        (2006.01)
FI G06T 7/60 250C
請求項の数または発明の数 20
全頁数 44
出願番号 特願2005-319646 (P2005-319646)
出願日 平成17年11月2日(2005.11.2)
新規性喪失の例外の表示 特許法第30条第1項適用 2005年5月19日 システム制御情報学会主催の「第49回 システム制御情報学会研究発表講演会」において文書をもって発表
審査請求日 平成20年10月30日(2008.10.30)
特許権者または実用新案権者 【識別番号】800000068
【氏名又は名称】学校法人東京電機大学
発明者または考案者 【氏名】狩野 弘之
【氏名】藤岡 寛之
個別代理人の代理人 【識別番号】100067541、【弁理士】、【氏名又は名称】岸田 正行
【識別番号】100087398、【弁理士】、【氏名又は名称】水野 勝文
【識別番号】100126147、【弁理士】、【氏名又は名称】川上 成年
審査官 【審査官】松永 稔
参考文献・文献 特開平10-262941(JP,A)
特開2005-326977(JP,A)
特表2003-509748(JP,A)
森川博由、坪川直宏、柳雄一郎,平滑化スプライン関数による音声ピッチパターンのモデル化と分析,電子情報通信学会技術研究報告. SP, 音声,日本,社団法人電子情報通信学会 ,2000年 7月20日,100(239),pp.17-24
調査した分野 G06T 7/60
特許請求の範囲 【請求項1】
データが入力される入力手段と、プログラムを格納する記憶手段と、前記プログラムを実行し前記データを処理する演算手段と、前記演算手段の処理結果を出力する出力手段とを備える処理装置で実行される極値検出方法であって、
前記入力手段から入力された平面における離散データ群又は関数から、前記演算手段が複数の節点を有する最適平滑化スプライン曲線を生成するステップと、
前記演算手段が、前記最適平滑化スプライン曲線又はその導関数隣接する前記節点により区分された一区間である各節点区間の各々について各々極値を求めることにより、前記最適平滑化スプライン曲線又はその導関数の極値のすべてを求め、該極値を前記出力手段へ出力するステップと、
を有することを特徴とする最適平滑化スプライン曲線による極値検出方法。
【請求項2】
前記最適平滑化スプライン曲線又はその導関数の極値のすべてを求め、該極値を前記出力手段へ出力するステップは、
前記演算手段が、前記最適平滑化スプライン曲線又はその導関数の各節点区間について各々正規化して、単位区間における正規化された多項式関数又はその導関数を生成するステップと、
前記演算手段が、前記単位区間における正規化された多項式関数又はその導関数について極値を求めることにより、前記最適平滑化スプライン曲線又はその導関数の極値のすべてを求めるステップと、
を有することを特徴とする請求項1に記載の最適平滑化スプライン曲線による極値検出方法。
【請求項3】
前記演算手段が前記最適平滑化スプライン曲線を生成するステップは、
前記演算手段が前記平面における離散データ群又は関数から節点ごとの最適重み係数を求めるステップと、
前記演算手段が前記節点ごとの正規化された一様なBスプライン関数を、前記節点ごとの最適重み係数により重みづけして加え合わせて構成することにより、最適平滑化スプライン曲線を生成するステップと、
を有することを特徴とする請求項1または2に記載の最適平滑化スプライン曲線による極値検出方法。
【請求項4】
前記スプライン関数は、3次のスプライン関数であることを特徴とする請求項3に記載の最適平滑化スプライン曲線による極値検出方法。
【請求項5】
データが入力される入力手段と、プログラムを格納する記憶手段と、前記プログラムを実行し前記データを処理する演算手段と、前記演算手段の処理結果を出力する出力手段とを備える処理装置で実行される極値検出方法であって、
前記入力手段から入力された空間における離散データ群又は関数から前記演算手段が複数の節点を有する最適平滑化スプライン曲面を生成するステップと、
前記演算手段が前記最適平滑化スプライン曲面又はその偏導関数前記節点により格子上に区画された一領域である各節点領域の各々について各々極値を求めることにより、前記最適平滑化スプライン曲面又はその偏導関数の極値のすべてを求め、該極値を前記出力手段へ出力するステップと、
を有することを特徴とする最適平滑化スプライン曲面による極値検出方法。
【請求項6】
前記最適平滑化スプライン曲面又はその偏導関数の極値のすべてを求め、該極値を前記出力手段へ出力するステップは、
前記演算手段が前記最適平滑化スプライン曲面又はその偏導関数の各節点領域について各々正規化して、単位領域における正規化された多項式関数又はその偏導関数を生成するステップと、
前記演算手段が前記単位領域における正規化された多項式関数又はその偏導関数について極値を求めることにより、前記最適平滑化スプライン曲面又はその偏導関数の極値のすべてを求めるステップと、
を有することを特徴とする請求項5に記載の最適平滑化スプライン曲面による極値検出方法。
【請求項7】
前記演算手段が前記最適平滑化スプライン曲面を生成するステップは、
前記演算手段が前記空間における離散データ群又は関数から節点ごとの最適重み係数を求めるステップと、
前記演算手段が前記節点ごとの正規化された一様なBスプライン関数を、前記節点ごとの最適重み係数により重みづけして加え合わせて構成することにより、最適平滑化スプライン曲面を生成するステップと、
を有することを特徴とする請求項5または6に記載の最適平滑化スプライン曲面による極値検出方法。
【請求項8】
ピクセルデータが入力される入力手段と、プログラムを格納する記憶手段と、前記プログラムを実行し前記ピクセルデータを処理する演算手段と、前記演算手段の処理結果を出力する出力手段とを備える画像処理装置で実行されるデジタル画像のエッジ検出方法であって、
前記入力手段から入力されたピクセルの座標及び輝度値からなるピクセルデータから、前記演算手段が複数の節点を有する最適平滑化スプライン曲面を生成するステップと、
前記演算手段が前記最適平滑化スプライン曲面を第1の座標軸上の複数の座標で固定した複数の曲線からなる第1の曲線群を生成し、該第1の曲線群を構成する複数の曲線の1次導関数隣接する前記節点により区分された一区間である各節点区間の各々について各々極値を求めることにより、前記第1の曲線群の1次導関数の極値のすべてを求めるステップと、
前記演算手段が前記最適平滑化スプライン曲面を第2の座標軸上の複数の座標で固定した複数の曲線からなる第2の曲線群を生成し、該第2の曲線群を構成する複数の曲線の1次導関数隣接する前記節点により区分された一区間である各節点区間の各々について各々極値を求めることにより、前記第2の曲線群の1次導関数の極値のすべてを求めるステップと、
前記演算手段が前記第1の曲線群の1次導関数の極値又は前記第2の曲線群の1次導関数の極値の絶対値が所定のしきい値より大きい箇所を、デジタル画像のエッジ部分と判定し、該判定結果を前記出力手段へ出力するステップと、
を有することを特徴とするデジタル画像のエッジ検出方法。
【請求項9】
前記第1の曲線群の1次導関数の極値のすべてを求めるステップは、
前記演算手段が前記第1の曲線群を構成する複数の曲線の1次導関数の各節点区間について各々正規化して、単位区間における正規化された第1の曲線群を構成する複数の曲線の1次導関数の極値を求めることにより、前記第1の曲線群の1次導関数の極値のすべてを求めるステップと、を有し、
前記第2の曲線群の1次導関数の極値のすべてを求めるステップは、
前記演算手段が前記第2の曲線群を構成する複数の曲線の1次導関数の各節点区間について各々正規化して、単位区間における正規化された第2の曲線群を構成する複数の曲線の1次導関数の極値を求めることにより、前記第2の曲線群の1次導関数の極値のすべてを求めるステップと、
を有することを特徴とする請求項8に記載のデジタル画像のエッジ検出方法。
【請求項10】
前記演算手段が前記最適平滑化スプライン曲面を生成するステップは、
前記演算手段が前記ピクセルの座標及び輝度値からなるピクセルデータから節点ごとの最適重み係数を求めるステップと、
前記演算手段が前記節点ごとの正規化された一様なBスプライン関数を、前記節点ごとの最適重み係数により重みづけして加え合わせて構成することにより、最適平滑化スプライン曲面を生成するステップと、
を有することを特徴とする請求項8または9に記載のデジタル画像のエッジ検出方法。
【請求項11】
データが入力される入力手段と、プログラムを格納する記憶手段と、前記プログラムを実行し前記データを処理する演算手段と、前記演算手段の処理結果を出力する出力手段とを備える処理装置に、
前記入力手段から入力された平面における離散データ群又は関数から、前記演算手段が複数の節点を有する最適平滑化スプライン曲線を生成するステップと、
前記演算手段が前記最適平滑化スプライン曲線又はその導関数隣接する前記節点により区分された一区間である各節点区間の各々について各々極値を求めることにより、前記最適平滑化スプライン曲線又はその導関数の極値のすべてを求め、該極値を前記出力手段に出力するステップと、
を実行させるための最適平滑化スプライン曲線による極値検出プログラム。
【請求項12】
前記最適平滑化スプライン曲線又はその導関数の極値のすべてを求め、該極値を前記出力手段に出力するステップは、
前記演算手段が前記最適平滑化スプライン曲線又はその導関数の各節点区間について各々正規化して、単位区間における正規化された多項式関数又はその導関数を生成するステップと、
前記演算手段が前記単位区間における正規化された多項式関数又はその導関数について極値を求めることにより、前記最適平滑化スプライン曲線又はその導関数の極値のすべてを求めるステップと、
を有することを特徴とする請求項11に記載の最適平滑化スプライン曲線による極値検出プログラム。
【請求項13】
前記演算手段が前記最適平滑化スプライン曲線を生成するステップは、
前記演算手段が前記平面における離散データ群又は関数から節点ごとの最適重み係数を求めるステップと、
前記演算手段が前記節点ごとの正規化された一様なBスプライン関数を、前記節点ごとの最適重み係数により重みづけして加え合わせて構成することにより、最適平滑化スプライン曲線を生成するステップと、
を有することを特徴とする請求項11または12に記載の最適平滑化スプライン曲線による極値検出プログラム。
【請求項14】
前記スプライン関数は、3次のスプラインであることを特徴とする請求項13に記載の最適平滑化スプライン曲線による極値検出プログラム。
【請求項15】
データが入力される入力手段と、プログラムを格納する記憶手段と、前記プログラムを実行し前記データを処理する演算手段と、前記演算手段の処理結果を出力する出力手段とを備える処理装置に、
前記入力手段から入力された空間における離散データ群又は関数から、前記演算手段が複数の節点を有する最適平滑化スプライン曲面を生成するステップと、
前記演算手段が前記最適平滑化スプライン曲面又はその偏導関数前記節点により格子上に区画された一領域である各節点領域の各々について各々極値を求めることにより、前記最適平滑化スプライン曲面又はその偏導関数の極値のすべてを求め、該極値を前記出力手段に出力するステップと、
を実行させるための最適平滑化スプライン曲面による極値検出プログラム。
【請求項16】
前記最適平滑化スプライン曲面又はその偏導関数の極値のすべてを求め、該極値を前記出力手段に出力するステップは、
前記演算装置が前記最適平滑化スプライン曲面又はその偏導関数の各節点領域について各々正規化して、単位領域における正規化された多項式関数又はその導関数を生成するステップと、
前記演算装置が前記単位領域における正規化された多項式関数又はその偏導関数について極値を求めることにより、前記最適平滑化スプライン曲面又はその偏導関数の極値のすべてを求めるステップと、
を有することを特徴とする請求項15に記載の最適平滑化スプライン曲面による極値検出プログラム。
【請求項17】
前記演算手段が前記最適平滑化スプライン曲面を生成するステップは、
前記演算手段が空間における離散データ群又は関数から節点ごとの最適重み係数を求めるステップと、
前記演算手段が前記節点ごとの正規化された一様なBスプライン関数を、前記節点ごとの最適重み係数により重みづけして加え合わせて構成することにより、最適平滑化スプライン曲面を生成するステップと、
を有することを特徴とする請求項15または16に記載の最適平滑化スプライン曲面による極値検出プログラム。
【請求項18】
ピクセルデータが入力される入力手段と、プログラムを格納する記憶手段と、前記プログラムを実行し前記ピクセルデータを処理する演算手段と、前記演算手段の処理結果を出力する出力手段とを備える画像処理装置に、
前記入力手段から入力されたピクセルの座標及び輝度値からなるピクセルデータから前記演算手段が複数の節点を有する最適平滑化スプライン曲面を生成するステップと、
前記演算手段が前記最適平滑化スプライン曲面を第1の座標軸上の複数の座標で固定した複数の曲線からなる第1の曲線群を生成し、該第1の曲線群を構成する複数の曲線の1次導関数隣接する前記節点により区分された一区間である各節点区間の各々について各々極値を求めることにより、前記第1の曲線群の1次導関数の極値のすべてを求めるステップと、
前記演算手段が前記最適平滑化スプライン曲面を第2の座標軸上の複数の座標で固定した複数の曲線からなる第2の曲線群を生成し、該第2の曲線群を構成する複数の曲線の1次導関数隣接する前記節点により区分された一区間である各節点区間の各々について各々極値を求めることにより、前記第2の曲線群の1次導関数の極値のすべてを求めるステップと、
前記演算手段が前記第1の曲線群の1次導関数の極値又は前記第2の曲線群の1次導関数の極値の絶対値が所定のしきい値より大きい箇所を、デジタル画像のエッジ部分と判定し、該判定結果を前記出力手段へ出力するステップと、
を実行させるためのデジタル画像のエッジ検出プログラム。
【請求項19】
前記第1の曲線群の1次導関数の極値のすべてを求めるステップは、
前記演算手段が前記第1の曲線群を構成する複数の曲線の1次導関数の各節点区間について各々正規化して、単位区間における正規化された前記第1の曲線群を構成する複数の曲線の1次導関数の極値を求めることにより、前記第1の曲線群の1次導関数の極値のすべてを求めるステップと、を有し、
前記第2の曲線群の1次導関数の極値のすべてを求めるステップは、
前記演算手段が前記第2の曲線群を構成する複数の曲線の1次導関数の各節点区間について各々正規化して、単位区間における正規化された前記第2の曲線群を構成する複数の曲線の1次導関数の極値を求めることにより、前記第2の曲線群の1次導関数の極値のすべてを求めるステップと、
を有することを特徴とする請求項18に記載のデジタル画像のエッジ検出プログラム。
【請求項20】
前記演算手段が前記最適平滑化スプライン曲面を生成するステップは、
前記演算手段が前記ピクセルの座標及び輝度値からなるピクセルデータから節点ごとの最適重み係数を求めるステップと、
前記演算手段が前記節点ごとの正規化された一様なBスプライン関数を、前記節点ごとの最適重み係数により重みづけして加え合わせて構成することにより、最適平滑化スプライン曲面を生成するステップと、
を有することを特徴とする請求項18または19に記載のデジタル画像のエッジ検出プログラム。
発明の詳細な説明 【技術分野】
【0001】
本発明は、離散データ点や関数に関する極値検出方法及び極値検出プログラムに関し、特に、離散データ点や関数に関する最適平滑化スプラインを設計することにより、すべての極値を検出する極値検出方法及び極値検出プログラム、およびその極値検出方法及び極値検出プログラムを利用したデジタル画像のエッジ検出方法及びエッジ検出プログラムに関する。
【背景技術】
【0002】
離散データ点や関数に関する極値検出の問題は、工学を始めとする様々な分野で現れ、いわゆる「数理計画法」あるいは「最適化法」という分野の中で重要な問題として知られている。離散データ点や関数に関する極値検出の方法は、山登り法(山下り法)に代表されるような数値的な極値探索法が一般的であり、従って局所的な方法である。
【0003】
しかしながら、このような局所的な方法による極値探索は、離散データ点の局部のノイズの影響を受けやすく、極値を精度良く安定的に検出することが困難である。したがって、離散データ点に関して大域的に評価することが可能な極値検出方法が求められている。
【0004】
離散データ点に関して大域的に評価することが可能な極値検出方法に関しては、例えば、特許文献1に記載の方法がある。この方法によれば、1組のデータ点について大域的にサンプリングを行い、この1組のデータ点に基づいて単一のポリラインを生成し、このポリラインの極値を求める方法が開示されている。

【特許文献1】特開2005-222554号公報
【発明の開示】
【発明が解決しようとする課題】
【0005】
特許文献1に記載の方法においては、曲線を作成する際に使用する「特定の点」や「分割点」の選択に、曲率(2次導関数)が用いられている。特に「特定の点」は,曲率が極値(極小値,極大値)をとる点あるいは0になる点として選ばれている。一方、「分割点」は曲率の積分値に基づいて選択されている。
【0006】
しかしながら、曲率の極値や,曲率が0になる点の計算法は何ら具体的に示されていない。曲率の値を幾つかの点で計算し,得られた値から極大や極小,さらに0になる点を選んでいるのではないかと推測されるが、定かではない。
【0007】
また、特許文献1に記載の方法は、曲線設計に関する高い技術を有していないユーザを対象として、ユーザの希望する曲線を描き、それを修正することを支援するものに過ぎず、離散データ点に関して大域的に評価することが可能ではない。
【0008】
本発明は、このような極値に関する従来の問題も解決するもので、離散データ点や関数に関する最適平滑化スプラインを設計することにより、最適平滑化スプラインに対する極値を精度良く安定的に検出する方法を提供しようとするものである。また、すべての極値が求まることから、最大値や最小値も得られる方法を提供しようとするものである。
【課題を解決するための手段】
【0009】
本発明は、データが入力される入力手段と、プログラムを格納する記憶手段と、プログラムを実行しデータを処理する演算手段と、演算手段の処理結果を出力する出力手段とを備える処理装置で実行される極値検出方法であって、入力手段から入力された平面における離散データ群又は関数から、演算手段が複数の節点を有する最適平滑化スプライン曲線を生成するステップと、演算手段が、前記最適平滑化スプライン曲線又はその導関数隣接する前記節点により区分された一区間である各節点区間の各々について各々極値を求めることにより、最適平滑化スプライン曲線又はその導関数の極値のすべてを求め、極値を出力手段へ出力するステップとを有することを特徴とする最適平滑化スプライン曲線による極値検出方法である。

【0010】
また、本発明は、データが入力される入力手段と、プログラムを格納する記憶手段と、プログラムを実行しデータを処理する演算手段と、演算手段の処理結果を出力する出力手段とを備える処理装置で実行される極値検出方法であって、入力手段から入力された空間における離散データ群又は関数から演算手段が複数の節点を有する最適平滑化スプライン曲面を生成するステップと、演算手段が最適平滑化スプライン曲面又はその偏導関数前記節点により格子上に区画された一領域である各節点領域の各々について各々極値を求めることにより、最適平滑化スプライン曲面又はその偏導関数の極値のすべてを求め、極値を前記出力手段へ出力するステップとを有することを特徴とする最適平滑化スプライン曲面による極値検出方法である。

【0011】
また、本発明は、ピクセルデータが入力される入力手段と、プログラムを格納する記憶手段と、プログラムを実行しピクセルデータを処理する演算手段と、演算手段の処理結果を出力する出力手段とを備える画像処理装置で実行されるデジタル画像のエッジ検出方法であって、入力手段から入力されたピクセルの座標及び輝度値からなるピクセルデータから、演算手段が複数の節点を有する最適平滑化スプライン曲面を生成するステップと、演算手段が最適平滑化スプライン曲面を第1の座標軸上の複数の座標で固定した複数の曲線からなる第1の曲線群を生成し、該第1の曲線群を構成する複数の曲線の1次導関数隣接する前記節点により区分された一区間である各節点区間の各々について各々極値を求めることにより、第1の曲線群の1次導関数の極値のすべてを求めるステップと、演算手段が最適平滑化スプライン曲面を第2の座標軸上の複数の座標で固定した複数の曲線からなる第2の曲線群を生成し、第2の曲線群を構成する複数の曲線の1次導関数隣接する前記節点により区分された一区間である各節点区間の各々について各々極値を求めることにより、第2の曲線群の1次導関数の極値のすべてを求めるステップと、演算手段が第1の曲線群の1次導関数の極値又は第2の曲線群の1次導関数の極値の絶対値が所定のしきい値より大きい箇所を、デジタル画像のエッジ部分と判定し、判定結果を出力手段へ出力するステップとを有することを特徴とするデジタル画像のエッジ検出方法である。

【0012】
また、本発明は、データが入力される入力手段と、プログラムを格納する記憶手段と、プログラムを実行しデータを処理する演算手段と、演算手段の処理結果を出力する出力手段とを備える処理装置に、入力手段から入力された平面における離散データ群又は関数から、演算手段が複数の節点を有する最適平滑化スプライン曲線を生成するステップと、演算手段が最適平滑化スプライン曲線又はその導関数隣接する前記節点により区分された一区間である各節点区間の各々について各々極値を求めることにより、最適平滑化スプライン曲線又はその導関数の極値のすべてを求め、極値を出力手段に出力するステップとを実行させるための最適平滑化スプライン曲線による極値検出プログラムである。

【0013】
また、本発明は、データが入力される入力手段と、プログラムを格納する記憶手段と、プログラムを実行しデータを処理する演算手段と、演算手段の処理結果を出力する出力手段とを備える処理装置に、入力手段から入力された空間における離散データ群又は関数から、演算手段が複数の節点を有する最適平滑化スプライン曲面を生成するステップと、演算手段が最適平滑化スプライン曲面又はその偏導関数前記節点により格子上に区画された一領域である各節点領域の各々について各々極値を求めることにより、最適平滑化スプライン曲面又はその偏導関数の極値のすべてを求め、極値を出力手段に出力するステップとを実行させるための最適平滑化スプライン曲面による極値検出プログラムである。

【0014】
また、本発明は、ピクセルデータが入力される入力手段と、プログラムを格納する記憶手段と、プログラムを実行しピクセルデータを処理する演算手段と、演算手段の処理結果を出力する出力手段とを備える画像処理装置に、入力手段から入力されたピクセルの座標及び輝度値からなるピクセルデータから演算手段が複数の節点を有する最適平滑化スプライン曲面を生成するステップと、演算手段が最適平滑化スプライン曲面を第1の座標軸上の複数の座標で固定した複数の曲線からなる第1の曲線群を生成し、第1の曲線群を構成する複数の曲線の1次導関数隣接する前記節点により区分された一区間である各節点区間の各々について各々極値を求めることにより、第1の曲線群の1次導関数の極値のすべてを求めるステップと、演算手段が最適平滑化スプライン曲面を第2の座標軸上の複数の座標で固定した複数の曲線からなる第2の曲線群を生成し、第2の曲線群を構成する複数の曲線の1次導関数隣接する前記節点により区分された一区間である各節点区間の各々について各々極値を求めることにより、第2の曲線群の1次導関数の極値のすべてを求めるステップと、演算手段が第1の曲線群の1次導関数の極値又は第2の曲線群の1次導関数の極値の絶対値が所定のしきい値より大きい箇所を、デジタル画像のエッジ部分と判定し、判定結果を出力手段へ出力するステップとを実行させるためのデジタル画像のエッジ検出プログラムである。
【発明の効果】
【0015】
本発明の最適平滑化スプラインによる極値検出方法によれば、設計されたスプラインを対象とするため、各節点ごとに定義された多項式の極値(極小値、極大値)を求めれば良い。これによりすべての極値が求まり、最小値や最大値を求めることが可能となる。
【発明を実施するための最良の形態】
【0016】
(第1実施形態)
以下、本発明の第1実施形態である最適平滑化スプライン曲線による極値検出方法及び極値検出プログラムについて、図を参照して詳細に説明をする。
【0017】
よく知られるように、スプライン関数は様々な工学分野で用いられており、これまで幅広い研究がなされてきている。特に、最適制御理論に基づいた「動的スプライン」の理論が提案されており、そのようなアプローチは、Bスプライン関数の解析や、最適平滑化曲線の設計に利用されている。さらには、最適内挿および平滑化スプラインの枠組みが日本の書道で見られるような文字や文字列の設計および再設計を行うために利用されている。
【0018】
本実施形態では、まず、与えられた離散データの集合に対して最適平滑化スプライン曲線の設計を行う。そのような曲線の設計には、正規化された一様なBスプライン関数を基底関数として用いる。まず、最適平滑化曲線の設計について、簡潔な計算手順が得られる基本的な結果を示す。次に、最適曲線のすべての極値、すなわち極小値、極大値を計算するためのアルゴリズムを示す。その際、スプラインが区分的多項式であり、連続かつ微分可能であるということを利用するものである。スプライン曲線は、区分的多項式であり制御点によって表すことができるので、その極値を検出し計算するアルゴリズムは簡潔かつ数値計算に対しても利用しやすいものとなっている。
【0019】
Bk(・)を、整数値の節点をもつk次の正規化された一様なBスプライン関数とし、一定間隔でシフトし重みづけしたBスプライン関数の和としてスプライン曲線x(t)を生成する。すなわち、k次スプライン曲線x(t)は、
【0020】
【数1】
JP0004669993B2_000002t.gif

【0021】
のように表現される。
【0022】
ここで、mは、整数であって、予め定めうる設計パラメータである。τi∈Rは制御点と呼ばれる重み係数である。α(>0)は、予め定めうる設計パラメータであり、等間隔に配置された節点tiの間隔(節点区間)を、ti+1-ti=1/αに従って調整するための定数である。
【0023】
数式1によってスプライン曲線x(t)が構成される様子を図1に示す。各つり鐘状の波形は適宜シフトされたk次BスプラインBk(・)に対応する制御点τi(「×」印で示す)によって重み付けされた関数を表し,スプライン曲線x(t)はこれらをすべて加え合わせて構成されている。制御点τi∈Rを適切に選ぶことによって,任意のk次スプライン曲線x(t)を区間[t0,tm]で設計することができる。
【0024】
k次B-スプライン関数Bk(t)は、次式
【0025】
【数2】
JP0004669993B2_000003t.gif

【0026】
で定義されている。Bk(t)は整数値の節点をもち,j=0,…,kに対する各節点区間[j,j+1]で基底関数Nj,k(t-j)によって指定され,[0,k+1]以外の区間では恒等的に0である。
【0027】
ここで基底関数Nj,k(t)は、
【0028】
【数3】
JP0004669993B2_000004t.gif

【0029】
によって,初期関数N0,0(t)=1から順次生成することができる。
【0030】
実際上、k=3、すなわち3次のスプライン関数を選定した場合、基底関数Nj,3(t)は次式
【0031】
【数4】
JP0004669993B2_000005t.gif

【0032】
のように、4つ(すなわちk+1個)の関数を含むことになる。
【0033】
このことは、各tにおけるk次スプライン関数の値は、tが含まれる区間におけるk+1個の基底関数(従って対応するk+1個の制御点)の影響を受けるだけで、その範囲外の基底関数(従って対応する制御点)の影響を受けないことを意味している。
【0034】
(最適化過程)
次に、離散データDの集合が
【0035】
【数5】
JP0004669993B2_000006t.gif

【0036】
によって与えられているとし、また、τ∈RM(M=m+k)を以下のように定義される制御点ベクトルとする。
【0037】
【数6】
JP0004669993B2_000007t.gif

【0038】
そのとき、最適平滑化スプライン曲線の設計の基本問題は、評価関数
【0039】
【数7】
JP0004669993B2_000008t.gif

【0040】
を最小にするスプライン曲線x(t)もしくは等価的に制御点ベクトルτ∈RMを見つける問題となる。ただし、λ>0、wi∈(0,1]∀iである。
【0041】
この問題に対する最適解τは以下の線形方程式の解として得られる。
【0042】
【数8】
JP0004669993B2_000009t.gif

【0043】
ここで、Q∈RM×M
【0044】
【数9】
JP0004669993B2_000010t.gif

【0045】
によって定義されるグラミアンで、与えられる離散データDとは無関係に予め計算しておくことができる。
【0046】
またW∈RN×N、d∈RNおよびB∈RM×N
【0047】
【数10】
JP0004669993B2_000011t.gif

【0048】
【数11】
JP0004669993B2_000012t.gif

【0049】
【数12】
JP0004669993B2_000013t.gif

【0050】
である。
【0051】
ただし数式9,12におけるb(t)∈RMは、
【0052】
【数13】
JP0004669993B2_000014t.gif

【0053】
なるベクトルである。
【0054】
数式8は可解であり、従って解τは常に存在する。もちろんλQ+BWBT>0のときに限り唯一となる。この解τを数式1に用いることによって、区間[t0,tm]におけるk次の最適平滑化スプラインx(t)が設計される。
【0055】
このように、制御点ベクトルτに関する最適化解を求め、数式1を用いることによって、k次最適平滑化スプライン曲線x(t)が生成される。
【0056】
(スプライン曲線の極値)
次に、最適平滑化スプライン曲線x(t)の極値を検出する方法を説明する。具体的には、x(1)(t)=0とx(2)(t)>0もしくはx(2)(t)<0を満たしている点t∈(t,tm)を見つければ良い。
【0057】
区間[t0,tm]で設計されたk次最適平滑化スプラインx(t)は、各区間[tj,tj+1)(k=0,1,2,・・・,m-1)で各々k次多項式である。従って、区間毎に極値を検出することによって、x(t)の最大値、最小値を含むすべての極値が求まる。
【0058】
x(t)は区間[tj,tj+1)において、
【0059】
【数14】
JP0004669993B2_000015t.gif

【0060】
となり、k+1個の制御点τj-k、τj-k+1、・・・、τjによって決まるk次多項式である。
【0061】
tからδへの変数変換を次のように行う。
【0062】
【数15】
JP0004669993B2_000016t.gif

【0063】
このとき変数tの区間[tj,tj+1)は変数δに対する単位区間[0,1)に正規化され、関数x(t)はδの関数
【0064】
【数16】
JP0004669993B2_000017t.gif

【0065】
に変換される。x(δ)はδに関するk次多項式であり、これを
【0066】
【数17】
JP0004669993B2_000018t.gif

【0067】
とする。
【0068】
なお、以下に使用される数式に関して、δを変数とする関数xには、すべて‘ハット(^)’がつくものであるが、明細書本文中では省略するものとする。
【0069】
明らかにx(t)=x(δ)、またx(1)(t)=αx (1)(δ)、x(2)(t)=α2x(2)(δ)かつα>0より、x(t)の区間[tj,tj+1)における極値はx(δ)の単位区間[0,1)における極値として得ることができる。x(δ)がδ=δ(0≦δ<1)で極値x(δ)を持てばx(t)はt=(1/α)δ+tで極値x(t)=x(δ)を持つ。
【0070】
x(δ)の単位区間[0,1)における極値の求め方は、後述する図3のステップ103~ステップ105の通りである。その際、1次導関数x(1)(δ)の根の計算は、既存の多項式の根の計算プログラムを用いることができる。
【0071】
(3次スプライン)
実際に良く用いられている3次スプライン(すなわちk=3)の場合には、以下の仮定1を置くことによって、上のステップはより詳細なアルゴリズムとして書くことができる。これはx(1)(δ)が2次多項式となり、その根が陽的に表現できるからである。
【0072】
ここでは、実用的な目的上、次の仮定を導入する。
【0073】
(仮定1)各節点区間[tj,tj+1)のx(t)の極値の個数は、多くても1つである。ただし、j=0, 1,2,・・・,m-1
【0074】
x(t)が、最適平滑化スプライン曲線であることに注意すると、節点区間[tj,tj+1)が小さければ仮定1は妥当なものである。
【0075】
3次スプライン(すなわちk=3)の場合には、多項式x(δ)は4つの重み係数τj-3,τj-2,τj-1,τjだけに依存し、δの変域[0,1)に対して次式のように表現することができる。
【0076】
【数18】
JP0004669993B2_000019t.gif

【0077】
すなわち、係数pj、qj、rj、sjは、上記最適化過程ですでに得られている重み係数(ベクトル)τのうち、τj-3、τj-2、τj-1、τjの4つから唯一に決定される。
【0078】
前述のように、x(δ)がδ=δe∈[0,1)で極値をもつことがわかれば、そのときx(t)は、te=tje(1/α)∈[tj,tj+1)で極値をもち、その値は、x(te)= x(δe)により得られることとなる。
【0079】
δeを得るためには、数式18のx(δ)の1次導関数、すなわち
【数19】
JP0004669993B2_000020t.gif
が重要な役割をはたす。pj≠0である場合には、x(1)(δ)の2つの根は、
【0080】
【数20】
JP0004669993B2_000021t.gif
のように表すことができる。そのとき、x(1)(0)=rj/2およびx(1)(1)=rj+1/2となるので、極値が存在するかどうかはrjとrj+1の符号により調べることができる。具体的には、仮定1のもとでの幾何学的な観察により、以下の3つの場合が得られる。
【0081】
(P1) rj・rj+1<0であれば、極値は[0,1)に存在する。(P2) rj・rj+1=0であれば、極値はいくつかの付加的な条件のもとで[0,1)に存在する。
【0083】
(P3) rj・rj+1>0であれば、極値は[0,1)には存在しない。
【0084】
(P1)と(P2)の場合について、以下の結果が得られる。
【0085】
(命題1)rj・rj+1<0と仮定する。そのとき、r>0かつrj+1<0(r<0かつr>0)ならば、関数x(δ)はδ=δe∈(0,1)で極大(極小)をもつ。ただし、
【0086】
【数21】
JP0004669993B2_000022t.gif

【0087】
(命題2)rj・rj+1=0と仮定するとき、以下の2つの場合が生じる。
【0088】
(i)rj=0の場合: qj<0 (q>0)であれば、そのときx(δ)はδ=0で極大(極小)をもつ。qj=0である場合には、極値は存在しない。
【0089】
(ii)rj≠0かつrj+1=0の場合: rj>0かつqj+1>0(rj<0かつq<0)であれば、そのときx(δ)はδ=r/pj∈(0,1)で極大(極小)をもつ。また、rj・qj+1≦0であれば極値は存在しない。
【0090】
したがって、3次最適平滑化スプライン関数x(t)の極値を検出し計算するアルゴリズムは、以下のようにまとめることができる。
【0091】
重み係数τ-3,τ-2,τ-1,・・・,τm-1が与えられ、rjとrj+1を、j=0, 1,2,・・・,m-1に対して計算し、そのときrj・rj+1<0およびr・rj+1=0の場合には、それぞれ命題1および2を使う。δ=δeで極値x(δ)が見つかれば、te=tj+(1/α)δeで極値x(te)を計算する。
【0092】
図2は、本実施形態のk次最適平滑化スプライン曲線による極値検出方法及び極値検出プログラムに用いられる処理装置を示すブロック図である。本実施形態の最適平滑化スプラインによる極値検出方法に用いられる処理装置1は、CPU5(演算手段)とメモリ装置4(RAMやROM等:記憶手段)を有し、このメモリ装置4に格納されたプログラムを実行し、図3、4のフローチャートに記載した動作を実行することにより、図2のブロック図に示すように、CPU5と、メモリ装置4とマウス、キーボード、スキャナ、データロガー等の入力装置6(入力手段)とバス3と、ディスプレイ装置7(出力手段)と、プリンタ装置8(出力手段)と、外部ネットワーク10と接続するネットワーク装置9(入力手段・出力手段)を備えた処理装置として機能する。
【0093】
図3は、本実施形態の一般のk次最適平滑化スプラインによる極値検出方法の処理の流れを示すフローチャートである。
【0094】
ステップ101(図ではステップをSと略す)は、離散データDについて重み係数τiを求め入力する工程である。すなわち、CPU5は、入力した離散データD(ui,di),i=1,・・・,Nについて、最適な重み係数τi,i=-k, -k+1,・・・,m-1を決定し、最適平滑化スプライン曲線x(t)を設計する。
【0095】
ステップ102では、CPU5は、節点区間[tj,tj+1)での最適平滑化スプライン曲線x(t)を正規化して得られる、単位区間[0,1 )でのk次多項式x(δ)を生成する。すなわち、x(δ)の各係数a0,・・・,akの計算を行う。
【0096】
x(δ)は、数式16で定義されている。ここで、基底関数(多項式)N0,k(δ)、N1,k(δ)、・・・、Nh,k(δ)は、数式3の逐次式から計算機を用いて予め求めておくことができ、いずれもk次多項式である。いま、
【0097】
【数22】
JP0004669993B2_000023t.gif

【0098】
とし、求めるx(δ)の多項式表現を数式17とすると、その係数a0,・・・,akは数式17、数式22によって次式から求められる。
【0099】
【数23】
JP0004669993B2_000024t.gif

【0100】
ステップ103では、CPU5は、ステップ102で求めた多項式x(δ)の1次導関数x(1)(δ)の根を求める。
【0101】
ステップ104では、CPU5は、多項式x(δ)が単位区間[0,1)で実根を有するか否か判定する。実根を有する場合にはステップ105へ進み、実根を有しない場合にはステップ106へ進む。
【0102】
ステップ105では、CPU5は、x(δ)の2次導関数x (2)(δ)へ、ステップ103で求めた多項式x(δ)の実根δeを代入し、x(2)e)>0の場合には、te=tj+(1/α)δeで極小値x(δe)をもつものとし、x(2)e)<0の場合には、te=tj+(1/α)δeで極大値x(δe)をもつものとする。これにより、最適平滑化スプライン関数x(t)の所定の節点区間[tj,tj+1)における、極大値または極小値が求まることとなる。
【0103】
ステップ106では、jが、m-1より小さい場合にはステップ102へ戻り、jが、m-1の場合にはステップ107へ進み、区間[t0,tm]のすべての節点区間[tj,tj+1)についての極値検出手続きが終了するまで、ステップ102からステップ105を繰り返す。
【0104】
ステップ107では、CPU5は、最適平滑化スプライン関数x(t)の全区間[t0,tm]に存在するすべての極値から、すべての極値の大小を判別することにより、最適平滑化スプライン関数x(t)の最大値及び最小値を求める。そして、最適平滑化スプライン関数x(t)の極大値、極小値、最大値及び最小値を、ディスプレイ装置7やプリンタ装置8に出力する。
【0105】
図4は、本実施形態の最適平滑化スプラインによる極値検出方法の処理の流れにおいて、3次スプライン(k=3)を用いた場合を示すフローチャートである。なお、図3のフローチャートとはステップ102~104のみ相違するため、対応する部分を、ステップ102a及び103aとして記載している。
【0106】
ステップ102aは、図3のフローチャートのステップ102に対応する部分である。ステップ102aでは、CPU5は、3次多項式であるx(δ)について、各係数pj、qj、rj、sjを算出する。上述したように、各係数pj、qj、rj、sjは、τj-3、τj-2、τj-1、τjの4つから唯一に決定される。
【0107】
ステップ103aは、図3のフローチャートのステップ103及び104に対応する部分である。ステップ103aでは、CPU5は、ステップ102aで求めた多項式x(δ)の1次導関数x(1)(δ)の根を求める。qj2-pjrj≧0の場合には図3のステップ105ヘ進み、qj2-pjrj<0の場合には図3のステップ106へ進む。
【0108】
なお、本実施形態においては、離散データDが与えられた場合について極値をもとめたが、関数f(t),t0≦t≦tmが入力データとして与えられた場合についても、同様な方法で極値を求めることが可能である。この場合にも、まずf(t)を近似する最適スプラインを以下のように設計する。
【0109】
関数f(t)が与えられたとき、評価関数は、数式7の代わりに
【0110】
【数24】
JP0004669993B2_000025t.gif

【0111】
を用いる。この最適解τは線形方程式
【0112】
【数25】
JP0004669993B2_000026t.gif

【0113】
の解として得られる。ここで、Qは、数式9で定義される行列、Q
【0114】
【数26】
JP0004669993B2_000027t.gif

【0115】
で定義される行列で、いずれもf(t)とは無関係に予め計算しておくことができる。右辺は、f(t)が与えられると適当な数値積分法を用いて計算できる。
【0116】
一旦、最適なベクトルτが決まると、極値の検出等、後の扱いは離散データの場合と同様である。ただし、既存の最適化アルゴリズムとの併用によって以下のような有効性がある。一般に関数f(t)が与えられたとき、ある区間(一般性を失わずに[t0,tm]と考えてよい)での最大値や最小値を求める方法は繰り返しによる数値的探索法によるのが通常である。
【0117】
その際、繰り返し式の初期値の取り方が問題となり、それによって多峰性関数の場合は到達する極値が異なる。最大値や最小値が得られる保証は全くない。本方法によれば、f(t)を近似する最適スプラインが得られ、その最大値や最小値が得られる。さらに対応するtの値を初期値として数値的探索法を適用すればf(t)の最大値や最小値をより正確に求めることができる。
【0118】
(数値実験例)
図5は、本発明の第1実施形態の最適平滑化スプライン曲線とその極値を示す図である。図5は、最適平滑化スプライン曲線x(t)(図中の実線で示された関数)から極値を抽出する性能を示す図である。図5は、k=3,α=1, t0=1およびtm=m=50の場合での結果を示している。ただし、三角形と逆三角形はそれぞれ検出された極大値および極小値を示す。ここで、データdi(図中の*印)は、関数f(t)= ea(t-1)cos(b(t-1))+1(図中の点線で示された関数)をサンプリングすることにより生成されている。ただし、a=1/(m-1) log1/4, b=2π×3/(m-1)である。 データの個数はN=30とし、uiは区間[t0,tm]=(1,50)においてランダムに配置されたデータ点であり、またデータに加えるノイズの大きさはσ=0.02とする。さらに、平滑化パラメータλを推定するためにいわゆるcross-validation手法を採用し、その最適値はλ=0.1585のように得られた。
【0119】
図からわかるように、データノイズがかなり大きいにもかかわらず、元の関数であるf(t)のすべての極値がかなり精度よく検出されていることがわかる。特に極値を与えるtの値はほぼ正確に得られていることがわかる。
【0120】
なお、上記実施形態では、最適平滑化スプライン関数x(t)の極値を求めたが、同様な方法で、x(t)の第i導関数x(i)(t)の極値を求めることが可能である。
【0121】
区間[t1,tm]で設計された最適スプラインx(t)の第i導関数x(i)(t)(i=1,2,・・・,k)も各節点区間[tj,tj+1) (k=0, 1,・・・,m-1)毎に考えれば良い。すなわち、節点区間[tj,tj+1 )においては数式14と数式15の変数変換によって、x(i)(t)=αix(i)(δ)の関係が成立する。またα>0よりx(i)(t)の節点区間[tj,tj+1 ) における極値は、x (i)(δ)の単位区間[0,1 )における極値となる。この第i導関数x (i)(δ)は、数式17と数式23の結果を用いて、
【0122】
【数27】
JP0004669993B2_000028t.gif

【0123】
によって計算できる。
【0124】
x(i)(δ)(ただしi≦k-2)の極値の検出は、図3のステップ102における多項式x(δ)をx(i)(δ)に置き換え、これに伴いx(1)(δ), x(2)(δ)をそれぞれx(i+i)(δ)、x(i+2)(δ) に置き換えて、ステップ103以降に同様な方法を適用すれば良い。ここで、i≦k-2に限定されるのは、k-(i+2)次の多項式であるi+2次導関数が必要であるからで、k-(i+2)≧0が必要なためである。
【0125】
以上説明したように、本実施形態の最適平滑化スプラインによる極値検出方法によれば、設計されたスプラインを対象とするため、各節点区間ごとに定義された多項式の極値(極小値、極大値)を求めれば良い。これによりすべての極値が求まり、最小値や最大値を求めることが可能となる。
【0126】
また、基底関数としてBスプライン関数を用いているため、設計されたスプラインの表現が簡潔であり、その導関数も容易に求めることができる。
【0127】
そして、極値計算の対象は、離散データでも関数でも良い。いずれの場合にも最適平滑化スプラインが設計でき、その際、節点の間隔やBスプラインの次数を調整することによって十分な精度で近似でき、ノイズの影響を受けにくい数値的に非常に安定した方法といえる。もちろん、この極値検出法は最適平滑化スプライン曲線に限らず、数式1で表現されるスプライン曲線であれば適用できるものである。
【0128】
特に、3次Bスプライン関数を用いた場合には、各区間毎に3次多項式となり、極値は解析的に得ることができる。
【0129】
(第2実施形態)
以下、本発明の第2実施形態である最適平滑化スプライン曲面による極値検出方法及び極値検出プログラムについて、図を参照して詳細に説明をする。
【0130】
(最適平滑化スプライン曲面)
本発明の第1実施形態では、平面における離散データについて最適平滑化スプライン曲線を生成し極値の検出を行ったが、本実施形態は、空間における離散データを近似する最適平滑化スプライン曲面を生成し極値の検出を行うものである。また、本実施形態は、本発明の第1実施形態の最適平滑化スプライン曲線の極値検出方法を最適平滑化スプライン曲面に素直に拡張した方法を提供するものである。
【0131】
図6は、本実施形態の最適平滑化スプライン曲面を概略的に示す図である。図6Aは、空間における離散データから求められた最適な制御点(重み係数)の分布を示す図であり、図6Bは、空間における離散データに基づいて生成された最適平滑化スプライン曲面x(s,t)を示す図である。
【0132】
(曲面の生成)
本実施形態の最適平滑化スプライン曲面x(s,t)は、k次Bスプライン関数Bk(・)を用いて、数式1の自然な拡張である以下の数式28で表すことが可能である。
【0133】
【数28】
JP0004669993B2_000029t.gif

【0134】
ここで、α、β(>0)は定数、m、m(>2)は整数、si、tjは以下のように等間隔に配置された節点を表す。
【0135】
【数29】
JP0004669993B2_000030t.gif

【0136】
このとき、制御点τi,jを適切に選ぶことによって、任意のk次スプライン曲面を(s,t)の領域
【0137】
【数30】
JP0004669993B2_000031t.gif

【0138】
上で設計することができる。この制御点をまとめて行列τ∈RM1×M2(ただしM1=m1+k、M2=m2+k)で表すことにする。
【0139】
【数31】
JP0004669993B2_000032t.gif

【0140】
いま、空間内に離散データが
【0141】
【数32】
JP0004669993B2_000033t.gif

【0142】
のように与えられたとする。このとき最適平滑化スプライン曲面を、下記の評価関数J(τ)が最小となるように設計する。
【0143】
【数33】
JP0004669993B2_000034t.gif

【0144】
この問題に対する解、すなわち最適な制御点は次の線形方程式の解として得られる。
【0145】
【数34】
JP0004669993B2_000035t.gif

【0146】
以下で数式34において現れる各行列、ベクトルを示す。まず、Qは次式で与えられる M1M2×M1M2の行列である。
【0147】
【数35】
JP0004669993B2_000036t.gif

【0148】
ここで、Ql(ij)∈RM1×M2
【0149】
【数36】
JP0004669993B2_000037t.gif


【0150】
によって定義される。ただし、ベクトルb1(t)∈RM1、b2(t)∈RM2 は、Bスプライン関数から構成されている。
【0151】
【数37】
JP0004669993B2_000038t.gif

【0152】
数式36に示す各行列、従ってQは与えられるデータとは独立にBスプラインから予め計算しておくことができる。
【0153】
行列W∈RN×Nは、数式33に示す評価関数における重みから構成される対角行列である
【0154】
【数38】
JP0004669993B2_000039t.gif

【0155】
行列B∈RM1M2×N、 およびベクトルd∈RNは与えられるデータによって以下のように定められる。
【0156】
【数39】
JP0004669993B2_000040t.gif

【0157】
以上によって、数式34に現れる各行列、ベクトルが定まる。この方程式を解くことによって最適なτ、従って最適な制御点行列τが求められ、最適平滑化曲面x(s,t)が数式28によって構成できる。
【0158】
(曲面の極値)
次に、上記の方法により求めた最適平滑化曲面x(s,t)の極値を求める方法について説明する。
【0159】
(対象とする曲面)
数式28のk次スプライン曲面の極値を求める。ここでパラメータk、α、β、m、mは設定済みで,制御点τi,jは前述の方法等によってすでに与えられているとする。なお、(s,t) の定義域はS=[s0,sm1]×[t0,tm2]⊂R2である。
【0160】
(極値)
曲面x(s,t)の極値は
【0161】
【数40】
JP0004669993B2_000041t.gif

【0162】
をみたす点(s,t)∈Sとして得られる。
【0163】
曲面x(s,t)のヘッセ行列が正定値となる場合が極小値、曲面x(s,t)のヘッセ行列が負定値となる場合が極大値を与える。x(s,t)の領域Sでの極値を求める問題は、節点間の部分領域Sκ,μ=[sκ,sκ+1)×[tκ,tκ+1 )における極値を求める問題を全領域κ=0,1,・・・,m1-1;μ=0,1,・・・,m2-1に渡って繰り返せば良い。
【0164】
(部分領域の正規化)
領域Sκ,μに注目し、u=α(s-sκ),v=β(t-tμ)なる変数変換を行うと、u,vの変域はいずれも[0,1)と正規化される。すなわち、(s,t)の領域Sκ,μは、κ、μにかかわらず、(u,v)の単位領域ε=[0,1)×[0,1)になる。このとき、Sκ,μにおける関数x(s,t)は、
【0165】
【数41】
JP0004669993B2_000042t.gif

【0166】
と表すことができる。なお、以下に使用される数式に関して、u、vを変数とする関数xには、すべて‘ハット(^)’がつくものであるが、明細書本文中では省略するものとする。
【0167】
さらにx(s,t)の偏導関数とx(u,v)の偏導関数の間の関係は
【0168】
【数42】
JP0004669993B2_000043t.gif

【0169】
となる。α、β>0より、x(s,t)の領域Sκ,μ上での極値はx(u,v)の領域ε上での極値と一致する。
【0170】
(部分領域での極値)
数式40に示す、曲面x(s,t)の勾配ベクトルが0、かつ、曲面x(s,t)のヘッセ行列が正定値となるか、又は、曲面x(s,t)のヘッセ行列が負定値となる点(u,v)∈εを検出すればよい。このときx(s,t)は、点(s,t)=((1/α) u+sκ,(1/β) v+tμ)で極値x(s,t)=x(u,v)をもつ。
【0171】
(x(u,v)の極値の求め方)
(関数x(u,v)の表現)
x(u,v)はu,vについてそれぞれk次の2変数多項式であり、以下のように簡潔に表すことができる。
【0172】
【数43】
JP0004669993B2_000044t.gif

【0173】
(k+1)×(k+1)行列Aは
【0174】
【数44】
JP0004669993B2_000045t.gif

【0175】
で定義される。また、S,Tκ,μは次のようにして得られる(k+1)×(k+1)行列である。
【0176】
行列Sは、その各行がBスプラインの基底関数Ni,k(t),i=0,1,・・・,kの各係数から構成される行列である。すなわち、
【0177】
【数45】
JP0004669993B2_000046t.gif

【0178】
としたとき、Nk(t)=Shk+1(t)となる行列Sであり、例えばk=3の場合、数式4よりSはつぎのようになる。
【0179】
【数46】
JP0004669993B2_000047t.gif

【0180】
行列Tκ,μは、曲面x(u,v)の定義式に現れる(k+1)2個の制御点から次のように構成される。
【0181】
【数47】
JP0004669993B2_000048t.gif

【0182】
すなわち、曲面x(s,t)を構成する全体の制御点行列τ(数式31)のうちの、要素Tκ,μから左上の(k+1)×(k+1)のブロックとして得られるτの部分行列である。
【0183】
(勾配ベクトルとヘッセ行列)
x(u,v)の勾配ベクトルおよびヘッセ行列は以下のように表現される。
【0184】
【数48】
JP0004669993B2_000049t.gif

【0185】
【数49】
JP0004669993B2_000050t.gif

【0186】
ただしCkは次のように定義される(k+1)×k行列である。
【0187】
【数50】
JP0004669993B2_000051t.gif

【0188】
(極値の候補点)
曲面x(u,v)の勾配ベクトルが0となる点(u,v)∈εを求める。曲面x(u,v)の勾配ベクトルの各要素は、次のように与えられる。
【0189】
【数51】
JP0004669993B2_000052t.gif

【0190】
ただし、
【0191】
【数52】
JP0004669993B2_000053t.gif

【0192】
は次式で定義されている。
【0193】
【数53】
JP0004669993B2_000054t.gif

【0194】
xu(u,v)=0、xv(u,v)=0が同時に成り立つためには、これらをuに関する多項式とみなしたときの終結式が0となる必要がある。すなわち、
【0195】
【数54】
JP0004669993B2_000055t.gif

【0196】
ただしR(v)は以下の(2k-1)×(2k-1)行列である。
【0197】
【数55】
JP0004669993B2_000056t.gif

【0198】
|R(v)|はvに関する多項式であり、この多項式の根を求め、0≦v<1をみたす根をv=vとする。なお、このような根がない場合にはx(u,v)は、単位領域εに極値をもたない。このvに対応するuは、uに関する連立方程式xu(u,v)=0、xv(u,v)=0の解として求められる。具体的には、qi(バー)=qi(v)、ri(バー)=ri(v)として得られる2つの多項式
【0199】
【数56】
JP0004669993B2_000057t.gif

【0200】
の共通因子f0(u)を求める。その際、例えばユークリッド互助法を適用することができる。なお、f1(u)、f2(u)が共通因子をもつことは保証されており、もちろん、f0(u)はuに関する次数1以上の多項式である。f0(u)の根uが0≦u<1をみたすとき、u=uとおく。みたさないときはx(u,v)は領域εに極値をもたない。
【0201】
(極値の判定)
得られた点(u,v)∈εが関数x(u,v)の極値の候補となる点であり、この点に対するヘッセ行列が正定(極小)あるいは負定(極大)の極値条件をみたすかどうか判定すればよい。なお、ヘッセ行列の計算の際、次のように定義される多項式
【0202】
【数57】
JP0004669993B2_000058t.gif

【0203】
【数58】
JP0004669993B2_000059t.gif

【0204】
を導入し、さらにq(v)、r(v)を用いることによって得られる次式を用いるのがよい。
【0205】
【数59】
JP0004669993B2_000060t.gif

【0206】
図7は、本実施形態の最適平滑化スプラインによる極値検出方法及び極値検出プログラムに用いられる処理装置を示すブロック図である。本実施形態の極値検出処理装置11は、CPU15(演算手段)とメモリ装置14(RAMやROM等:記憶手段)を有し、このメモリ装置14に格納されたプログラムを実行し、図8~11のフローチャートに記載した動作を実行することにより、図7のブロック図に示すように、CPU15(演算手段)と、メモリ装置14(記憶手段)と、マウス、キーボード、スキャナ、データロガー等の入力装置16(入力手段)と、バス13と、ディスプレイ装置17(出力手段)と、プリンタ装置18(出力手段)と、外部ネットワーク20と接続するネットワーク装置19(入力手段・出力手段)を備えた処理装置として機能する。
【0207】
図8は、本実施形態の最適平滑化スプラインによる極値検出方法及び極値検出プログラムの処理の概要を示すフローチャートである。図9は、図8のフローチャートのステップ203の処理の詳細を示すフローチャートであり、図10は、図8のフローチャートのステップ206の処理の詳細を示すフローチャートであり、図11は、図8のフローチャートのステップ211の処理の詳細を示すフローチャートである。
【0208】
ステップ201では、極値検出処理装置11に曲面の最適設計に用いられたパラメータκ、α、β、m、mおよび得られた最適制御点τi,j、i=-k,-k+1,・・・,m1-1、j=-k,-k+1,・・・,m2-1を入力する。
【0209】
ステップ202では、CPU15は、(k+1)×(k+1)行列S、(k+1)×k行列Ckおよびk×(k-1)行列Ck-1を準備する。
【0210】
以下、すべての(κ,μ)、κ=1,2,・・・,m1-1、μ=1,2,・・・,m2-1、の組み合わせに対して、以下の手順に従って領域Sκ,μでのx(s,t)の極値の検出、計算を行う。
【0211】
CPU15は、(k+1)×(k+1)行列A(ステップ203a)、多項式qi(v),i=1,2,・・・,k、 多項式ri(v),i=1,2,・・・,k+1(ステップ203b)、および終結式|R(v)|を求め(ステップ203c)、vの多項式である終結式の根を求める(ステップ203)。この終結式|R(v)|の計算には、数式処理を援用することができる。0≦v<1をみたす根vが存在しない場合には、次の(κ,μ)の組に移る(ステップ204)。
【0212】
CPU15は、得られたv(0≦v<1)をvとおき(ステップ205)、さらに、qi(バー)=qi(v),i=1,2,・・・,k、およびri(バー)=ri(v),i=1,2,・・・,k+1を計算する。それぞれqi(バー)、ri(バー)を係数とするuの多項式f1(u)、f2(u)を定め(ステップ206a)、例えば、ユークリッド互助法を適用するなどして、f1(u)とf2(u)の共通因子f0(u)を求める(ステップ206b)。f0(u)の根u(ステップ206c)が、0≦u<1をみたすとき(ステップ207)、u=uとおく(ステップ208)。そのような根uが存在しない場合には、次の(κ,μ)の組に移る。
【0213】
CPU15は、点(u,v)におけるヘッセ行列を計算し(ステップ209)、点(u,v)におけるヘッセ行列が正定となる場合には極小、点(u,v)におけるヘッセ行列が負定となる場合には極大と判断し(ステップ210)、対応する極値x(u,v)を計算する(ステップ211a)。これら両ケース以外の場合は、次の(κ,μ)の組に移る。
【0214】
CPU15は、x(s,t)の極値をとる点(s,t)を、(s,t)=((1/α)u+sκ,(1/β)v+tμ)で計算し(ステップ211b)、その値x(s,t)=x(u,v)とともに出力する(ステップ211c)。
【0215】
(2変数関数に対する最適曲面の設計)
なお、本実施形態においては、離散データDが与えられた場合について極値をもとめたが、関数f(s,t)が入力データとして与えられた場合についても、同様な方法で極値を求めることが可能である。関数f(s,t)が与えられたときのk次最適スプライン曲面x(s,t)の設計方法は以下の通りである。評価関数は、数式33の代わりに次式を用いる。
【0216】
【数60】
JP0004669993B2_000061t.gif

【0217】
この評価関数を最小にするτ(=vecτ)は、数式34の代わりに線形方程式
【0218】
【数61】
JP0004669993B2_000062t.gif

【0219】
を解けばよい。この右辺のベクトルは、数値積分を用いて求めることができる。なお、行列Q,Q1(00),Q2(00)は数式35、ベクトルb1(s)、b2(t)は数式37で定義されている。
【0220】
(数値実験例)
極値検出の数値例を示す。極値検出の対象となる最適平滑化スプライン曲面x(s,t)は、次式をサンプルして得られたデータに対して設計した。
【0221】
【数62】
JP0004669993B2_000063t.gif

【0222】
ここでのパラメータの値を次の表に示す。
【0223】
【表1】
JP0004669993B2_000064t.gif





















【0224】
曲面の設計の際に用いた各パラメータは、k=3、α=β=1、 s0=t0=0、m1=m2=10 である。従って、3次スプライン曲面を領域S=[0,10]×[0,10]で設計した。設計に用いたデータは、上記d(s,t)をs,t方向とも0.5間隔の格子点でサンプリングして生成した。設計された曲面x(s,t)に上述の極値検出法を適用して得られた結果を図12に示す。図では、検出された極大値(△印)と極小値(▽印)を、曲面x(s,t)の3次元表示に重ねて示した。また、st平面上には曲面の等高線表示と極値点とを示した。いずれの図からもすべての極値が検出されていることが確認できる。
【0225】
以上説明したように、本実施形態の最適平滑化スプライン曲面による極値検出方法及び極値検出プログラムによれば、与えられたk次スプライン曲面x(s,t)のすべての極値(極小値、極大値)を求めることが可能となる。従って、最小値や最大値も求まったことになる。曲面x(s,t)の設計は、与えられた離散空間データD(数式32)に基づく既述の方法でも良いし、あるいは与えられた関数f(s,t)を近似する曲面の設計によっても良い。後者の場合、設計されたスプライン曲面x(s,t)の最大値や最小値を求め、これらを与える点を初期値として、関数f(s,t)にさらに山登り法等の数値的探索法を適用することによって、f(s,t)の最大値や最小値がより正確、かつ系統だった方法で求められることになる。
【0226】
なお、上記実施形態では、最適平滑化スプライン関数x(s,t)の極値を求めたが、同様な方法で、x(s,t) の任意の偏導関数の極値を求めることが可能である。
【0227】
(偏導関数の極値)
いま記号の簡単化のためにx(s,t)とx(u,v)の偏導関数を以下のようにおく。
【0228】
【数63】
JP0004669993B2_000065t.gif

【0229】
また、問題が意味をもつためにi,j≦k-2とする。このとき、数式42の関係は、xi,j(s,t)=αiβjxi,j(u,v)となり、偏導関数xi,j(s,t)の極値は、xi,j(u,v)の極値から求めることができる。すなわち、xi,j(u,v)が点(u,v)∈εで極値をとれば、xi,j(s,t)は点(s,t)=((1/α)u+sκ,(1/β)v+tμ)で、極値xi,j(s,t)=αiβjxi,j(u,v)をもつことが分かる。
【0230】
(関数xi,j(u,v)の表現)
xi,j(u,v)は,数式43から
【0231】
【数64】
JP0004669993B2_000066t.gif

【0232】
と表される。ここで、
【0233】
【数65】
JP0004669993B2_000067t.gif

【0234】
である。このxi,j(u,v)は、数式43のx(u,v)と同形式であることから、その極値もx(u,v)の極値の検出、計算の場合と同様な手順に従って求めることができる。もちろん、偏導関数xi,j(s,t)のすべての極値(極小値、極大値)を求めることができ、従って、その最小値や最大値も求まったことになる。
【0235】
(第3実施形態)
以下、本発明の第3実施形態である最適平滑化スプラインによる極値検出方法及び極値検出プログラムについて、図を参照して詳細に説明をする。
【0236】
本発明の第2実施形態では、空間における離散データを近似する最適平滑化スプライン曲面を生成し極値の検出を行ったが、本実施形態では、離散データとしてデジタル画像の各ピクセルの輝度値データについて極値の検出を行う。さらに、ここでは、最適平滑化スプライン曲面x(s,t)のs方向およびt方向の1次偏導関数の極値を検出することにより、デジタル画像のエッジ検出を行う。
【0237】
(曲面の生成)
デジタル画像のエッジ検出に上記の極値検出法を適用した。対象としたのは256×256(pixel)のモノクロ画像であり、各ピクセルの輝度値をデータとして、まず、最適平滑化スプライン曲面x(s,t)を設計し、画像のエッジは、輝度値の変化率が急激に変化する部分(つまり、最適平滑化スプライン曲面x(s,t)のs方向およびt方向の1次偏導関数の極値が存在する部分)に存在するとの考えに基づき検出する。
【0238】
本実施形態では、最適平滑化スプライン曲面x(s,t)をライン毎に(たとえばsをs=pに固定し)処理している。その場合、エッジは変数tに関するスプライン曲線x(p,t)の1次導関数の極値として求めればよい。
【0239】
図6は、本実施形態の最適平滑化スプライン曲面を概略的に示す図である。図6Aは、各ピクセルの位置(座標)及びその輝度の分布から求められた最適な制御点(重み係数)の分布を示す図であり、図6Bは、各ピクセルの空間における離散データに基づいて生成された最適平滑化スプライン曲面x(s,t)及びライン毎に生成された関数x(s,q)、x(p,t)を示す図である。
【0240】
図13は、本実施形態の最適平滑化スプラインによる極値検出方法及び極値検出プログラムを用いたデジタル画像のエッジ検出処理装置を示すブロック図である。
【0241】
本実施形態の画像のエッジ検出処理装置21は、CPU25(演算手段)とメモリ装置24(RAMやROM等:記憶手段)を有し、このメモリ装置24に格納されたプログラムを実行し、図14~16のフローチャートに記載した動作を実行することにより、図13のブロック図に示すように、CPU25(演算手段)と、メモリ装置24(記憶手段)と、マウス、キーボード、スキャナ、データロガー等の入力装置26(入力手段)と、バス23と、ディスプレイ装置27(出力手段)と、プリンタ装置28(出力手段)と、外部ネットワーク30と接続するネットワーク装置29(入力手段・出力手段)を備えた処理装置として機能する。
【0242】
図14は、本実施形態の最適平滑化スプラインによるデジタル画像のエッジ検出方法の処理の概要を示すフローチャートである。
【0243】
ステップ301では、ピクセルデータ(i,j,fi,j)、i= 1,2,・・・,I、j= 1,2,・・・,J、を、画像のエッジ検出処理装置21に入力する工程である。ここで、fi,jは、ピクセルの座標(i,j)におけるピクセルの輝度値を示す。ピクセルデータは、例えば、不図示の光学的読取手段にてデータとして取得されうるものである。また、ピクセルデータは、ネットワーク装置29を介して不図示の外部装置から取得してもよい。そして、しきい値ρをメモリ装置24に格納する。しきい値ρは、極値がエッジ部分かどうか判別するためのパラメータである。x(1)(s,t)の極値(極大、極小)の絶対値がある程度以上の大きさの箇所をエッジとみなす。その程度は、画像の状態やエッジ検出条件により異なるため、エッジ検出においてしきい値ρを設定する。しきい値ρよりも極値の絶対値が大きければ、その箇所をエッジ部分としてみなし、それ以外の場合は、極値であってもエッジ部分とはみなさない。
【0244】
ステップ302では、CPU25は、上記入力ピクセルデータ(i,j,fi,j)に基づいて、最適平滑化スプライン曲面を生成する。具体的には、CPU25は、最適な重み係数τij(i=-k, -k+1,・・・,I-1、j=-k, -k+1,・・・,J-1)を求め、数式28に示す最適平滑化スプライン曲面を生成する。最適平滑化スプライン曲面を生成する方法については、本発明の第2実施形態で説明した通りである。その際のパラメータはα=β=1,s0=t0=1、m1=I-1,m2=J-1とする。
【0245】
最適平滑化スプライン曲面を生成したのち、その曲面をライン毎に(たとえばsをs=qに固定し)処理する。図6のs軸方向に対する処理をするために、ステップ303へ進み、図6のt軸方向の処理をするためにステップ304へ進む。
【0246】
ステップ303では、CPU25は、ステップ302で生成された最適平滑化スプライン曲面x(s,t)について、t座標をq(q=1,2,・・・,J)で固定した複数の曲線x(s,q)(図6B参照)を生成し、曲線x(s,q)の1次導関数x(1)(s,q)について極値を検出する(ステップ303a)。そして、CPU25は、この極値に基づいて、各々エッジの判定の処理を行う(ステップ303b)。
【0247】
ステップ304では、CPU25は、ステップ302で生成された最適平滑化スプライン曲面x(s,t)について、s座標をp(p=1,2,・・・,I)で固定した複数の曲線x(p,t)(図6B参照)を生成し、曲線x(p,t)の1次導関数x(1)(p,t)について極値を検出する(ステップ304a)。そして、CPU25は、この極値に基づいて、各々エッジの判定の処理を行う(ステップ304b)。
【0248】
ステップ305では、CPU25は、ステップ303とステップ304で得られた判定により検出されたエッジ箇所を総和としてまとめる。すなわちs方向、t方向のうち少なくとも一方でエッジと判定された箇所をエッジと判定する。
【0249】
ステップ306では、CPU25は、ステップ305の結果に基づいて、入力画像に対するエッジ検出結果を画像に変換し、ディスプレイ装置27やプリンタ装置28に出力する。
【0250】
図15は、ステップ303における処理の詳細を示すフローチャートである。ステップ401~403が、図14のステップ303aに相当し、ステップ404~407が、図14のステップ303bに相当する。
【0251】
ステップ401は、CPU25に、図14のステップ301で求めたピクセルデータ(i,j,fi,j)について重み係数τi,j(i=-k, -k+1,・・・,I-1、j= -k, -k+1,・・・,J-1)を入力する工程である。
【0252】
なお、以下に使用される数式に関して、δを変数とする関数xには、すべて‘ハット(^)’がつくものであるが、明細書本文中では省略するものとする。
【0253】
ステップ402では、CPU25は、ステップ302で生成された最適平滑化スプライン曲面x(s,t)を、t座標をq(q= 1,2,・・・,J)で固定して生成された複数の曲線x(s,q)について、節点区間[sj,sj+1)において正規化を行う。そして、単位区間[0,1)における正規化された曲線x(δs,q)を生成し、1次導関数x(1)s,q)を求め、多項式であるx(1)s,q)について、各係数a0,・・・,ak-1の計算を行う。
【0254】
ステップ403では、CPU25は、多項式x(1)s,q)の極値点δs1、δs2、・・・、δsm (m≦k-1)の検出を行う。多項式x(1)s,q)の極値点δs1、δs2、・・・、δsmは、x(2)s,q)の根のうち、単位区間[0,1)にある実根を検出して求めることができる。
【0255】
ステップ404、405では、CPU25は、すべての各極値点δs1、δs2、・・・、δsmについて、x(1)sl,q)・x(3)sl,q)<0、かつ、|x(1)sl,q)|>ρ(0≦l≦m)か否かを判断する。x(1)sl,q)・x(3)sl,q)<0、かつ、|x(1)sl,q)|>ρ(0≦l≦m)の場合には、ステップ406へ進む。そうでない場合には、ステップ404に戻る。
【0256】
ステップ406では、CPU25は、x(1)sl,q)・x(3)sl,q)<0、かつ、|x(1)sl,q)|>ρ(0≦l≦m)の場合には、点(p+(1/α)δsl ,q)においてエッジがあるものと判断する。これは、x(1)(t,q)の極値の箇所が必ずしもエッジの位置に対応しないことがあり、x(1)sl,q)・x(3)sl,q)<0を満たす箇所が、実際のエッジに対応するからである。
【0257】
ステップ407では、CPU25は、p<I-1の場合には、ステップ402~ステップ406の各工程を繰り返し、ステップ408では、q<Jの場合には、ステップ402~ステップ407の各工程を繰り返し、ステップ302で生成された最適平滑化スプライン曲面x(s,t)のt座標をq(q=1,2,・・・,J)で固定して生成された複数の曲線x(s,q)のすべてについてエッジを判断する。
【0258】
図16は、ステップ304における処理の詳細を示すフローチャートである。
【0259】
ステップ501は、CPU25に、図14のステップ301で求めたピクセルデータ(i,j,fi,j)について重み係数τi,j(i=-k, -k+1,・・・,I-1、j=-k, -k+1,・・・,J-1)を入力する工程である。
【0260】
ステップ502では、CPU25は、ステップ302で生成された最適平滑化スプライン曲面x(s,t)を、s座標をp(p=1,2,・・・,I)で固定して生成された複数の曲線x(p,t)について、区間[tj,tj+1)において正規化を行う。そして、単位区間[0,1)における正規化された曲線x(p,δt)を生成し、1次導関数x(1)(p,δt)を求め、多項式であるx(1)(p,δt)について、各係数b0,・・・,bk-1の計算を行う。
【0261】
ステップ503では、CPU25は、多項式x(1)(p,δt)の極値点δt1、δt2、・・・、δtn (n≦k-1)の検出を行う。多項式x(1)(p,δt)の極値点δt1、δt2、・・・、δtnは、x(2)(p, δt)の根のうち、単位区間[0,1)にある実根を検出して求めることができる。
【0262】
ステップ504、505では、CPU25は、すべての各極値点δt1、δt2、・・・、δtnについて、x(1)(p,δtl)・x(3)(p,δtl)<0、かつ、|x(1)(p,δtl)|>ρ(0≦l≦n)か否かを判断する。x(1)(p,δtl)・x(3)(p,δtl)<0、かつ、|x(1)(p,δtl)|>ρ(0≦l≦n)の場合には、ステップ506へ進む。そうでない場合には、ステップ504に戻る。
【0263】
ステップ506では、CPU25は、x(1)(p,δtl)・x(3)(p,δtl)<0、かつ、|x(1)(p,δtl)|>ρ(0≦l≦n)の場合には、点(p,q+(1/α)δtl)においてエッジがあるものと判断する。
【0264】
ステップ507では、q<J-1の場合には、CPU25は、ステップ502~ステップ506の各工程を繰り返し、ステップ508では、p<Iの場合には、ステップ502~ステップ507の各工程を繰り返し、ステップ302で生成された最適平滑化スプライン曲面x(s,t)を、s座標をp(p=1,2,・・・,I)で固定して生成された複数の曲線x(p,t)のすべてについてエッジを検出する。
【0265】
(デジタル画像のエッジ検出例)
図17及び図18は、本発明の第3実施形態の最適平滑化スプラインによる極値検出方法に用いたデジタル画像のエッジ検出方法を用いて、実際にエッジ検出を行った例を示す図である。図17は、原画像(a)にノイズが含まれない例を示し、図18は、原画像(a)にノイズが含まれる例を示す。
【0266】
図17(b)と図18(b)は、本実施形態のエッジ検出法を適用して生成した画像である。また、比較例として、cannyフィルタ及びsobelフィルタを用いてエッジ検出した画像を、図17(c)と図18(c)(cannyフィルタ)及び図17(d)と図18(d)(sobelフィルタ)に示した。
【0267】
図からもわかるように、特に、原画像(a)にノイズが含まれる場合において、他のフィルタと比較して、精度良くエッジの検出ができることがわかる。よって、本発明の最適平滑化スプラインによる極値検出方法に用いたデジタル画像のエッジ検出方法の有効性が証明された。
【0268】
以上説明したように、本実施形態の最適平滑化スプラインによる極値検出方法によれば、スプライン曲面の設計が画像情報全体の情報に基づいた曲面近似となるため、デジタル画像のエッジ検出は大域的な方法となる。従来の局所的な(画像の一部の情報に基づいた)方法とはまったく異なる方法であるといえ、本実施形態の最適平滑化スプラインによる極値検出方法は、結果的に画像のノイズの影響を受けにくい。
【0269】
なお、上記各実施形態においては、スプライン曲線(1次元)の場合、スプライン曲面(2次元)の場合について説明をしたが、本発明はこれに限られず、さらなる高次元の場合に拡張して適用することが可能である。
【図面の簡単な説明】
【0270】
【図1】最適平滑化スプライン曲線を概略的に示す図である。
【図2】本発明の第1実施形態の最適平滑化スプラインによる極値検出方法に用いられる処理装置を示すブロック図である。
【図3】本発明の第1実施形態の最適平滑化スプラインによる極値検出方法の処理の流れを示すフローチャートである。
【図4】本発明の第1実施形態の最適平滑化スプラインによる極値検出方法の処理の流れにおいて、最適平滑化スプラインが3次である場合を示すフローチャートである。
【図5】本発明の第1実施形態の最適平滑化スプライン曲線とその極値を示す図である。
【図6A】空間における離散データから求められた最適な制御点(重み係数)の分布を示す図である。
【図6B】最適平滑化スプライン曲面を概略的に示す図である。
【図7】本発明の第2実施形態の最適平滑化スプラインによる極値検出方法に用いたデジタル画像のエッジ検出処理装置を示すブロック図である。
【図8】本発明の第2実施形態の最適平滑化スプラインによる極値検出方法及び極値検出プログラムの処理の概要を示すフローチャートである。
【図9】図8のフローチャートのステップ203における処理の詳細を示すフローチャートである。
【図10】図8のフローチャートのステップ206における処理の詳細を示すフローチャートである。
【図11】図8のフローチャートのステップ211における処理の詳細を示すフローチャートである。
【図12】本発明の第2実施形態の最適平滑化スプラインによる極値検出方法及び極値検出プログラムを用いて、実際に極値検出を行った例を示す図である。
【図13】本発明の第3実施形態の最適平滑化スプラインによる極値検出方法及び極値検出プログラムを用いたデジタル画像のエッジ検出処理装置を示すブロック図である。
【図14】本発明の第3実施形態の最適平滑化スプラインによるデジタル画像のエッジ検出方法の処理の概要を示すフローチャートである。
【図15】図14のフローチャートのステップ303における処理の詳細を示すフローチャートである。
【図16】図14のフローチャートのステップ304における処理の詳細を示すフローチャートである。
【図17】本発明の第3実施形態の最適平滑化スプラインによる極値検出方法を用いたデジタル画像のエッジ検出方法を用いて、実際にエッジ検出を行った例を示す図である。
【図18】本発明の第3実施形態の最適平滑化スプラインによる極値検出方法を用いたデジタル画像のエッジ検出方法を用いて、実際にエッジ検出を行った例を示す図である。
【符号の説明】
【0271】
1:最適平滑化スプラインによる極値検出処理装置
3:バス
4:メモリ装置
5:CPU
6:入力装置
7:ディスプレイ装置
8:プリンタ装置
9:ネットワーク装置
図面
【図1】
0
【図2】
1
【図3】
2
【図4】
3
【図5】
4
【図6A】
5
【図6B】
6
【図7】
7
【図8】
8
【図9】
9
【図10】
10
【図11】
11
【図12】
12
【図13】
13
【図14】
14
【図15】
15
【図16】
16
【図17】
17
【図18】
18