付 波，胡 什，趙熙臨，徐光輝

范數(shù)度量下的三項遞歸式數(shù)值穩(wěn)定性判據(jù)

付 波，胡 什，趙熙臨，徐光輝

（湖北工業(yè)大學(xué)電氣與電子工程學(xué)院，湖北武漢430068）

正交矩的數(shù)值穩(wěn)定性分析是近年來圖像處理中研究的熱點。研究對象是正交矩解析式中最為常用的三項遞歸公式，介紹正交矩的三項遞歸公式及數(shù)值穩(wěn)定性的概念；然后以歐幾里得范數(shù)作為恒量其穩(wěn)定性的標(biāo)準(zhǔn)提出一種基于其計算系數(shù)極限存在與否判斷其數(shù)值穩(wěn)定性的判據(jù)，并給予詳盡證明；最后運用兩個實例證明此判據(jù)的可行性。

正交矩三項遞歸式；歐幾里得范數(shù)；計算系數(shù)極限；數(shù)值穩(wěn)定性

作為正交矩計算基礎(chǔ)的三項遞歸公式在進(jìn)行高階計算時存在數(shù)值不穩(wěn)定的問題。R.Mukundan在研究Tchebichef矩時提出了隨著正交矩分析的圖像越來越大，高階矩的計算過程中各種誤差會造成矩數(shù)值計算不穩(wěn)定［1］，最終導(dǎo)致圖像重構(gòu)時模糊。G.R.Amayeh等［2］試圖采用提高正交矩計算精度的方法來抑制其傳遞誤差，但僅僅只是對其作出了抑制，無法從根源上解決問題。郭［3］指出其誤差根源在于計算機系統(tǒng)本身產(chǎn)生的截斷誤差和舍入誤差，所提出的一種將三項遞歸式轉(zhuǎn)化為離散狀態(tài)方程來研究其穩(wěn)定性的方法，是目前較令人信服的方法，然而其隨后提出來的利用李亞普洛夫方法解決系統(tǒng)穩(wěn)定性的方法適用范圍過窄，只能判斷Legendre矩以及Tchebichef矩等少量矩的穩(wěn)定性。

筆者在總結(jié)上述學(xué)者工作的同時，也對常見的幾種正交矩三項遞歸式進(jìn)行了細(xì)致的研究，得出了一個規(guī)律：系數(shù)極限存在的正交矩基函數(shù)一般具有數(shù)值穩(wěn)定性，而系數(shù)極限為無窮的正交矩基函數(shù)則不具有數(shù)值穩(wěn)定性。立足于上述規(guī)律，筆者提出了判斷正交矩三項遞歸公式穩(wěn)定性的一個充分條件和判斷其不穩(wěn)定性的一個充分條件，并從歐幾里得范數(shù)和距離空間的角度對其進(jìn)行了嚴(yán)謹(jǐn)?shù)淖C明。最后利用此判據(jù)分別驗證了極限存在的Legendre矩的數(shù)值穩(wěn)定性以及極限為無窮的Tchebichef矩的不穩(wěn)定性，證明了其可行性。

1 正交矩三項遞歸公式

在正交矩的解析方法中，利用三項遞歸公式進(jìn)行解析是最常使用的方法：

若需要計算較高階數(shù)上述公式的數(shù)值，則需要計算機等手段的幫助。然而在計算機的計算過程中，系統(tǒng)本身產(chǎn)生的計算誤差會使觀測值異于實際值。上述計算誤差有可能會在計算過程中被放大，最終影響計算所得的終值。因此分析計算誤差的傳遞過程和三項遞歸算法的數(shù)值穩(wěn)定性勢在必行。在這里采用郭［3］的做法將其化為狀態(tài)方程來進(jìn)行研究，設(shè)三相遞歸公式的觀測值為Pk，其真實值為P＊k，計算誤差為ek，起始二項為P0和P1，P0和P1的誤差為e0和e1，可以將式（1）變?yōu)椋?/p>

易得，計算真值滿足：

將上式化為矩陣形式，即：

計算誤差滿足：

將上式化為矩陣形式，即：

在實際計算過程中，三項遞歸算法的數(shù)值穩(wěn)定性涉及兩個方面：1）真值計算系統(tǒng)（即式（4））本身的穩(wěn)定性；2）觀測誤差系統(tǒng)（即式（6））的穩(wěn)定性。當(dāng)且僅當(dāng)式（4）和式（6）所代表的系統(tǒng)均收斂，即代表觀測值的系統(tǒng)與代表遞歸誤差的系統(tǒng)均收斂時，整個三項算法才具有數(shù)值穩(wěn)定性。而上述兩個系統(tǒng)的傳遞函數(shù)均為：，是一類系統(tǒng)，因此只需研究上述任一系統(tǒng)的穩(wěn)定性即可。由此將算法數(shù)值穩(wěn)定性本質(zhì)轉(zhuǎn)化為研究基于式（6）的二階系統(tǒng)的穩(wěn)定性。若式（6）所代表的系統(tǒng)是穩(wěn)定的，則說明遞歸誤差不會在計算中被逐步放大，仍然是可以抑制的，它代表的遞歸算法具有數(shù)值穩(wěn)定性；反之則是發(fā)散的，其遞歸算法不具有數(shù)值穩(wěn)定性。因此只需判斷系統(tǒng)（6）的穩(wěn)定性即可判斷遞歸算法的數(shù)值穩(wěn)定性。

正交矩三項遞歸公式的計算系數(shù)A與B會隨階數(shù)的增加而變化，故其形成的系統(tǒng)（6）為離散線性時變系統(tǒng)，該類系統(tǒng)的穩(wěn)定性較難判斷，目前學(xué)術(shù)界仍無一定論。在這里文獻(xiàn)［4］的方法是利用較為常見的李雅普洛夫第二法［4］來判斷，然而值得注意的是：李亞普洛夫定義下的穩(wěn)定性與三相遞歸式的數(shù)值穩(wěn)定性還是有細(xì)微區(qū)別的，無法一概而論；且李雅普洛夫方法過于復(fù)雜，對于每一個不同的正交矩多項式需尋求不同的李雅普洛夫函數(shù)來進(jìn)行對應(yīng)，大大增加了判斷的難度。筆者在下節(jié)中的研究將回歸誤差傳遞的本質(zhì)，直接從系統(tǒng)（6）的傳遞函數(shù)矩陣入手，以歐幾里得范數(shù)作為恒量其三項遞歸式數(shù)值穩(wěn)定性的標(biāo)準(zhǔn)，提出兩個較為簡潔的穩(wěn)定性判據(jù)，并佐以詳細(xì)的證明。

2 范數(shù)度量下數(shù)值穩(wěn)定性判據(jù)

判據(jù)1：正交矩三項遞歸公式（1）數(shù)值穩(wěn)定的充分條件是：其計算系數(shù)A或B極限都存在且不為無窮。

判據(jù)2：正交矩三項遞歸公式（1）數(shù)值不穩(wěn)定的充分條件是：其計算系數(shù)A或B至少有一者極限為無窮。

證明：由上文分析得，三項遞歸公式（1）的數(shù)值穩(wěn)定性大致等價于二階系統(tǒng)（6）的穩(wěn)定性，系統(tǒng)（6）的傳遞函數(shù)矩陣為：

設(shè)M2×2（C）是數(shù)域C上的方陣，按照通常矩陣的加法與數(shù)乘構(gòu)成的2×2維線性空間［5］，對于冪級數(shù)常項矩陣G（k）＝（a（k）ij）2×2∈M2×2（C），定義以下范數(shù)：

則（Mn×n（C），‖.‖2）是賦范線性空間。在此賦范線性空間下G（k）的范數(shù)為：

當(dāng)計算系數(shù)A（k）與B（k）均極限都存在且不為無窮時，上述范數(shù)G（k）的極限‖G（k）‖存在且不為無窮。這表明代表的遞歸誤差不會在進(jìn)行高階計算時放大，即使在計算至無窮階時誤差仍然是有界的，根據(jù)上文的推論可以判斷此種計算系數(shù)下的三項遞歸公式具有數(shù)值穩(wěn)定性，判據(jù)1充分性得證。

當(dāng)計算系數(shù)A（k）與B（k）至少有一為無窮時，上述范數(shù)的極限‖G（k）‖為無窮，此時其代表的遞歸誤差會在進(jìn)行高階計算時被無限放大，最終會使計算值大幅度偏離真值。由上文的討論可知：此種計算系數(shù)下的三項遞歸公式不具有數(shù)值穩(wěn)定性，判據(jù)2充分性得證。

3 實例驗證

本章將利用上文的判據(jù)分別對Legendre矩三項遞歸公式和Krawtchouk矩三項遞歸公式進(jìn)行數(shù)值穩(wěn)定性判斷。

3.1 Legendre矩三項遞歸公式

Legendre矩三項遞歸公式為：得到其計算系數(shù)為：

取L（0）＝1，L（1）＝0.5；x∈［－1，1］，在c＋＋大數(shù)庫中計算0至400階的Legendre矩三項遞歸公式的誤差。圖1代表計算誤差隨計算階數(shù)的增加的變化情況，其中圖1a代表絕對誤差的變化，圖1b代表相對誤差的變化情況，單位用Arbitrary Precision Arithmetic［6，7］對數(shù)形式表示。由圖1可知：在0至400階的計算過程中其絕對誤差L（k）逐漸趨于穩(wěn)定，相對誤差E（k）除了在150階和220階左右較大之外其余均小于e－12，說明整個傳遞誤差的遞歸過程是收斂［8］的，Legendre矩三項遞歸公式具有數(shù)值穩(wěn)定性，這與筆者利用判據(jù)1得出來的結(jié)論一致，說明了判據(jù)1的有效性。

圖1 Legendre多項式迭代計算誤差隨階數(shù)k變化圖

3.2 Krawtchouk三項遞歸公式

Krawtchouk矩三項遞歸公式為：

其計算系數(shù)為：此時，由于系數(shù)N，p的數(shù)值不確定性，求得：由判據(jù)2可知：Krawtchouk矩三項遞歸公式在相對意義上不具有數(shù)值穩(wěn)定性。

與Legendre矩不同的是，Krawtchouk多項式計算系數(shù)中含有變量參數(shù)p。因此取x＝398時，p＝0.1，p＝0.3，p＝0.5，p＝0.7，p＝0.9五組數(shù)據(jù)對Krawtchouk多項式進(jìn)行迭代計算測試。其相對誤差如圖2a所示，絕對誤差如圖2b所示。

圖2 Krawtchouk多項式迭代計算誤差隨階數(shù)k變化圖

由圖2可知：當(dāng)p取以上五個數(shù)據(jù)時其絕對誤差和相對誤差均是發(fā)散的，其遞歸誤差在一定范圍內(nèi)無法得到抑制，因此Krawtchouk矩三項遞歸公式不具有數(shù)值穩(wěn)定性，這與判據(jù)2所得出的結(jié)論完全相同，證明了判據(jù)2的可行性。

4 結(jié)論

本文從一個新的角度對正交矩三相遞歸式的穩(wěn)定性做出了分析，給出了一種根據(jù)極限判斷其數(shù)值穩(wěn)定性的判據(jù)。對比文獻(xiàn)［3］所提出的判據(jù)，該判據(jù)僅需判斷三相遞歸式的計算系數(shù)極限存在與否即可判斷其數(shù)值穩(wěn)定性，因此可以更為靈活快捷地應(yīng)用于正交矩穩(wěn)定性分析中。目前僅有一類極限不存在但是不為無窮的三項多項式無法利用該判據(jù)判斷穩(wěn)定性，如何判斷這一類三項多項式的穩(wěn)定性也是筆者下一步研究的焦點問題。

［1］ Mukundan R，Ramakrishnan K R.Fast computation of legendre and zernike moments［J］.Pattern Recognition，1995，28（9）：1433－1442.

［2］ Amayeh G，Erol A，Bebis G，et al.Accurate and efficient computation of high order zernike moments［C］.ISVC 2005：462－469.

［3］ 郭浩，范秀香，付波，等.三項遞歸公式的數(shù)值穩(wěn)定性分析［J］.湖北工業(yè)大學(xué)學(xué)報，2016（2）：58－61.

［4］ Mukundan R，Ong S H，Lee P A.Image analysis by tchebichef moments［J］.IEEE Transactions on Image Processing.2001，10（9）：1357－1364.

［5］ 程曹宗.應(yīng)用泛函分析［M］.北京：機械工業(yè)出版社，2008.

［6］ Xiao B，Ma J F，Wang X.Image analysis by bessel–fourier moments［J］.Pattern Recognition，2010，43（8）：2620－2629.

［7］ Ziliang P，Rigeng W，Yunlong S.Image description with chebyshev－fourier moments.［J］.Journal of the Optical Society of America A Optics Image Science ＆Vision，2002，19（9）：1748－54.

［8］ Zhu H Q，Shu H Z，Liang L，et al.Image analysis by discrete orthogonal dual－h(huán)ahn moments［J］.Pattern Recognition Letters.2007，28：1688－1794.

Numerical Stability Criterion of the Three Recursion Relations Based on Norm Measurement

FU Bo，HU Shi，ZHAO Xilin，，XU Guanghui
（School of Electrical and Electronic Engineering，Hubei Univ.of Tech.，Wuhan 430068，China）

Numerical stability analysis of orthogonal moments is one of the hot topics in the field of image analysis in recent years.This paper studies the most commonly used three recursive formulas among the orthogonal moments analytic ones.First，the concepts of three recursion formulas and numerical stability of orthogonal moments were introduced；Then a new stability criterion was proposed to judge the stability of three recursion relations based on Euclidean norm standard，which was proofed in detail；Finally，two examples were used to demonstrate the feasibility of this criterion.

three recursion relations of orthogonal moments；euclidean norm；limit of calculation factors；numerical stability

TP13

A

［責(zé)任編校：張巖芳］

1003－4684（2017）04－0035－04

2016－06－27

國家自然科學(xué)基金（61072130；51109088）；武漢市科技攻關(guān)計劃項目（2013012401010845）；湖北工業(yè)大學(xué)科研基金項目（BSQD12107）；廣東省工業(yè)攻關(guān)項目（2011B010100037）

付 波（1975－），男，湖北武漢人，工學(xué)博士，湖北工業(yè)大學(xué)教授，研究方向為圖像處理