成麗美，袁偉，姚若俠

陜西師范大學計算機科學學院，西安 710062

活動標架的構(gòu)造及其在模式識別中的應用研究

成麗美，袁偉，姚若俠

陜西師范大學計算機科學學院，西安 710062

1 引言

活動標架的現(xiàn)代方法是由法國數(shù)學家Cartan[1-2]發(fā)展起來的，他把前人Cotton、Darboux、Frenet和Serret的工作改造融合，將活動標架發(fā)展成為用以研究子流形及其不變量在變換群作用下的幾何性質(zhì)的一種有效工具。到了20世紀70年代，Griffiths[3]、Green[4]、Jensen[5]試圖將Cartan的直觀構(gòu)造方法歸約為堅實的理論基礎(chǔ)。問題是該方法始終無法從狹窄的歐幾里德幾何或歐幾里德空間流形上的等仿射作用下脫離出來。直到一個概念性的跳躍，那就是“將活動標架理論從對任何形式標架叢或聯(lián)絡(luò)的依賴中分離出來，定義活動標架為一個從子流形或者Jet叢（射流叢）到群變換的一個等變映射?！被诖烁拍?，顯然活動標架不等同于標架(Moving Frames≠Frames!)，這一概念層面的跳躍成為新方法形成的關(guān)鍵。近幾年來，F(xiàn)els和Olver[6-7]建立了活動標架理論的一種新方法，其核心思想是將活標架定義為變換群的一個等變映射。該方法可以被系統(tǒng)地應用于一般的變換群，且所有經(jīng)典的活動標架都可以用這種方法重新詮釋。它通過選擇一個恰當?shù)娜很壍赖臋M截面（cross-section），并對其進行規(guī)范化來構(gòu)造活動標架，進而求解出微分不變量、微分不變算子和不變微分方程等。這種等變的活動標架方法最重要的貢獻就是給出了遞歸構(gòu)造算法，它將規(guī)范化的和差別化的微分不變量與不變微分形式聯(lián)系起來。這是一種基于Maurer-Cartan方程和相應結(jié)構(gòu)理論的新的、直接的代數(shù)構(gòu)造方法。正是因為構(gòu)造的代數(shù)性，所以算法可以在符號計算系統(tǒng)Maple或Mathematica上得以實現(xiàn)。這種方法產(chǎn)生的結(jié)果可以應用到許多新的領(lǐng)域，如共形不變量以及共形微分不變量[8]，不變數(shù)值方法[9]，計算機視覺，模式識別和對稱約化在圖像中的處理[10]，經(jīng)典不變理論[11]，不變微分問題[12]，不變子流形方法[13]，Poisson幾何和可積系統(tǒng)[14]，拉普拉斯微分不變算子[15]，相對論中的基林張量不變量和協(xié)變量[16-17]，李代數(shù)不變量，量子力學中的經(jīng)典子代數(shù)[18]等。大家知道，歐幾里德群、仿射群以及射影（變換）群作用下的不變量能廣泛地應用于圖像處理和計算機視覺[10，19-21]。其中，微分不變量的應用是最經(jīng)典的，例如空間曲線的歐氏曲率和撓率。在進行模型識別時，人們希望在數(shù)據(jù)庫中存儲一個圖片，然后，不從圖像上的離散點的觀點出發(fā)，而是從不變量的觀點去進行比較匹配，以此發(fā)現(xiàn)相似的圖片。也就是說，對于一個給定的曲線，人們可以選取一些關(guān)鍵點并在其上構(gòu)造其不變量，以便來獲得曲線的局部不變的簽名曲線，繼而可以得到歐幾里德不變簽名曲線。然后，通過比較不變簽名曲線而不是比較曲線本身來獲知曲線是否匹配。

本文將以一個一般的變換群為例來演示新的等變方法，也就是用遞歸算法構(gòu)造它的活動標架和微分不變量。為了演示該算法的高效性，文中同時給出了活動標架和微分不變量的經(jīng)典構(gòu)造方法。

2 活動標架

文中用G表示一個r維的李群，M表示一個m維的流形[6-7]，Jn=Jn(M，p)，1≤p≤m表示n階的Jet叢。此外，由于群變換G會保持相切等價關(guān)系，由此可得到在Jet空間Jn上的n階延拓變換群G(n)?；谶@些符號，下面給出一些定義：

定義1給定作用在流形M上的變換群G，一個活動標架是一個光滑的，G等變映射

定義2變換群G有兩個自然的作用作用于本身，若其滿足關(guān)系ρ(g·z)→g·ρ(z)，則ρ是左活動標架；若滿足關(guān)系ρ(g·z)→ρ(z)·g-1，則ρ是右活動標架。

引理1如果ρ~(z)是一個作用在流M上的左活動標架，則ρ(z)=ρ~(z)-1是一個右活動標架，反之亦然。

定理1如果變換群G作用在流形M上，當且僅當G在z∈M點附近的作用是自由和正則的，那么活動標架在點z的一個鄰域內(nèi)存在。

定義3對所有的z∈M，若Gz={g∈G|g·z=z}，則Gz為迷向子群。

定義4設(shè)G是一個作用于M上的局部變換群：

（1）若所有的軌道作為M的子流形都有相同的維數(shù)，則稱群G的作用是半正則的。

（2）若群G的作用是半正則的，且對于任意一點，存在任意小的鄰域，它與G的任意一條軌道相交于一個連通的子集合，則稱群G的作用是正則的[20]。

定義5如果對于所有的z∈M，都有Gz={e}，則稱該作用是自由的。

2.1 活動標架的基本構(gòu)造方法

活動標架的基本構(gòu)造方法是基于Cartan的規(guī)范化[1，22]，而規(guī)范化的實質(zhì)和關(guān)鍵則是要選擇軌道的一個恰當?shù)臋M截面κ。

定理2設(shè)G自由、正則地作用在M上，κ是一個截面，給定點z∈M，設(shè)g=ρ(z)是唯一的一個將z映射到截面κ上的群元素，即，g·z=ρ(z)·z∈κ。則ρ:M→G是群作用G的一個右活動標架。

給定M上的局部坐標z=(z1，z2，…，zm)，設(shè)ω(g·z)是群作用的顯式公式，則伴隨于一個坐標截面κ={z1=c1，z2=c2，…，zr=cr}，r=dimG≤m=dimM，ci是恰當選擇的常數(shù)。右活動標架g=ρ(z)可由以下步驟得到：

步驟1選取常數(shù)c1，c2，…，cr∈?，令變換后的坐標等于這些常數(shù)，從而給出規(guī)范化方程組：

步驟2求解規(guī)范化方程組（2），將群元素的參數(shù)g=(g1，g2，…，gr)解出，即用z=(z1，z2，…，zm)坐標來表示(g1，g2，…，gr)，由此可得活動標架g=ρ(z)。

步驟3將求得的活動標架g=ρ(z)代入剩下的未被規(guī)范的變換式ω(g·z)中，會獲得群作用的不變量的一個完全系統(tǒng)，也稱其基本不變量。

注若ω(g·z)=g·z，則可以獲得相應的右活動標架；若ω(g·z)=g-1·z，則可以獲得相應的左活動標架。

定理3如果g=ρ(z)是規(guī)范化方程組（2）的活動標架解，則函數(shù)

構(gòu)成了一組函數(shù)無關(guān)的完全的不變量系統(tǒng)，即其基本不變量。

定理4任意一個不變量I(z)可以被唯一地（局部）表示為基本不變量的函數(shù)：

定義6假定群G作用在流形M上，那么一個不變量是一個（局部）定義的標量函數(shù)F:M→R，它在群G的作用下是不變的，即F(g，z)=F(z)，對于使該方程有定義的所有的g∈G，z∈M都是成立的。

定理5一個標量函數(shù)I:M→R關(guān)于右活動標架ρ的不變性是指不變函數(shù)I=ι(F)，它滿足I(z)=F(ρ(z)·z)。

證明由活動標架的右等價性知：ρ(g·z)→ρ(z)·g-1，因而

大家知道，大部分的群作用不是自由的，因此按照定義，活動標架不存在。不過，有兩種方法可以將非自由的群作用轉(zhuǎn)化為自由的。一種是檢查群G在流形M的幾個副本上的笛卡爾乘積作用，即G×n:M×…×M→M×…×M，由此可獲得共形不變量。一種是將群作用延拓到導數(shù)空間，即Jet空間[23-24]，即G(n):Jn(M，p)→Jn(M，p)，由此會導致微分不變量。兩種方法的結(jié)合則會導致共形微分不變量。

定義9在平面上，如果G不變的曲率κ和它關(guān)于G弧長的導數(shù)κS被定義，同時在C上是解析的，則曲線C是G規(guī)則的；在空間中，如果G不變曲率κ，它關(guān)于G弧長的導數(shù)κS，G不變率τ和它關(guān)于G弧長的導數(shù)τS被定義，同時在C上是解析的，則曲線C是G規(guī)則的。

定義10非退化G不變平面曲線的G不變簽名曲線是由κ和κS參數(shù)化的曲線：

非退化G不變空間曲線的G不變簽名曲線是由κ、κS、τ和τS參數(shù)化的曲線：

因此，簽名曲線對于圖像識別[4]來說是一個有力的工具，這來源于下面這個定理：

定理6一般的r維變換群G作用于?2，在群G作用下，當且僅當兩個G規(guī)則的非退化解析曲線C和的簽名曲線是相同的，則它們是等價的。

2.2 群作用的延拓

為了給出遞歸算法的實現(xiàn)，此處對無窮小生成子的延拓做以簡要介紹。

定義11設(shè)G是一個作用于流形M上的局部變換群，向量場為：

例如，對于平面上的旋轉(zhuǎn)群：

3 遞歸算法

將r維的李群G作用在m維的流形M上，平凡主叢B=G×M繼承了廣義群的結(jié)構(gòu)，則有σ(g，z)=z是原映射σ:G×M→M。

Z(n)=g(n)·z(n)，z(n)∈J(n)，g(n)∈G是群G的n階延拓。ν1，ν2，…，νr是群G作用在流形M上的無窮小生成子，它形成李代數(shù)g的一個基。μ1，μ2，…，μr是基本的Maurer-Cartan一次形式。

笛卡爾積作用在余切叢T*B?T*G⊕T*M上，將其分為群和流形兩個組成部分，其中群組成部分是由Maurer-Cartan方程的μk展開來表示的，流形組成部分是將局部坐標z=(z1，z2，…，zm)的微分形式dzi代回到流形M上展開來表示的。因此，它導致微分d作用在B上可以將其分成對應的群組成部分和流形組成部分，即d=dM+dG。

通過提升函數(shù)f:M→R將其切映射代回到B中，所以λ(f) (g，x)=τ*f(g，z)=f?τ(g，z)=f(g·z)。此提升函數(shù)的原坐標與相應的切坐標的關(guān)系Z=g·z可以寫成關(guān)于群元素和原坐標的函數(shù)為Zα=λ(zα)，α=1，2，…，m。特別地，提升的微分形式僅僅是由流形組成部分來定義的，即：λ(dω)=dMλ(ω)。

定理8設(shè)ω是流形M上的微分形式，則有：

其中，#J是相切形的階。

注因為在確定活動標架和微分不變量的過程中相切形不扮演任何角色，所以從此處開始，都將它忽略。此外，文中將用“≡”來表示相等的切向模，例如是ω-?一個相切形，則ω≡?[25]。

對給定的李群G作用在流形M上，提升水平標架是由因變量的切向量水平微分形式組成的。即

4 例子

構(gòu)造活動標架有兩種方法，一種是用經(jīng)典的方法即基于Cartan的規(guī)范化，另外一種是就是本文的遞歸算法。通過對通常的微分算子進行不變性處理，可以得到p個互不相關(guān)的不變微分算子D1=ι(D1)，D2=ι(D2)，…，Dp=ι(Dp)，它們被迭代地應用到低價微分不變量上，則可以得到高階微分不變量。下面通過一個例子來演示如何用兩種方法來構(gòu)造活動標架和微分不變量。

4.1 用遞歸算法構(gòu)造活動標架和微分不變量

考慮一個作用在流形M=?2上的李群G=?4

它的延拓無窮小生成子，見表1。

表1 延拓無窮小生成子

由于前述原因，此處不考慮其相切形，那么0階遞推公式為：

下面開始逐步迭代計算活動標架和微分不變量。

（1）選擇0階橫截面κ0={x=1，u=0}。就是說，對于流形M上的點(x，u)，要尋找群參數(shù)a、b、c、q使得點(X，U)∈κ0。那么其0階規(guī)范化方程組為X=1，U=0，由其解即可得0階活動標架：

比較等式（20）兩邊，并利用變換（12）中的X=ax可得2階延拓：

顯然，式（21）中還包含待定群參數(shù)c、q，因而它不是微分不變量的最終形式，需要進行第（3）步迭代計算。由2階規(guī)范化方程的隱喻條件dUXX=0可得2階遞推公式：

比較等式（25）兩邊，并利用變換（12）中的X=ax可得3階延拓：顯然，式（26）中還包含待定群參數(shù)q，因而它依然不是微分不變量的最終形式，需要進行第（4）步迭代計算。將式（27）代入到方程（22）、（16）可獲得活動標架，即

繼而，將式（28）代入到方程（14）中可獲得最終的Maurer-Cartan形：

同理，基本微分不變量UXXXX可以通過計算dUXXX=UXXXXω+6μ4來獲得。由3階規(guī)范化方程UXXX=0，則存在隱喻條件dUXXX=0，由此得提升不變量為：

4.2用經(jīng)典方法構(gòu)造活動標架及微分不變量

考慮一個作用在流形M=?2上的李群G=?4

從方程（33）中可以看出該群含有a、b、c、q四個群參數(shù)，用經(jīng)典方法構(gòu)造活動標架的實質(zhì)就是選擇一個較好的橫截面κ={x=1，ux=uxx=uxxx=0}，即，X=1，UX=UXX=UXXX=0。顯然，需要由鏈式法則來分別計算UX，UXX，UXXX：

它和前述方法所得結(jié)果式（30）完全相同。此處不再計算其他高階微分不變量。

5 結(jié)束語

本文分別用經(jīng)典的Maurer-Cartan方法和改進的遞歸算法構(gòu)造活動標架和微分不變量。由文中的例子可以看到，用經(jīng)典的Maurer-Cartan方法構(gòu)造活動標架和微分不變量時，如果想獲得高階微分不變量，需要用隱式微分逐次迭代來計算高階微分不變量，且微分階數(shù)越高，尤其是變換越復雜，計算就越困難。而用遞歸算法構(gòu)造活動標架和微分不變量，只需要在逐個選擇恰當?shù)臋M截面的同時利用遞推公式，即在進行逐步規(guī)范化的同時，不但將群參數(shù)一個一個確定，也獲得了Maurer-Cartan形和微分不變量，從而避免了經(jīng)典算法所必須的復雜計算。該文用到的遞歸算法與Kogan[26-28]遞歸算法相比較，不需要存在一個切片（slice），而且這種遞歸算法還可以推廣應用到無限維李偽群的情形。這些微分不變量的獲得可用來構(gòu)造曲線的局部不變簽名曲線，繼而可以得到歐幾里德不變簽名曲線；然后，通過比較不變簽名曲線而不是比較曲線本身來獲知曲線是否匹配。

[1]Cartan é.La méthode du repére mobile，la théorie des groupes continus，et les espaces généralisés[J].Exposés de Géométrie，1935（5）.

[2]Cartan é.La théorie des groupes finis et continus et la géométrie différentielle traitées par la méthode du repére mobile[J]. Cahiers Scientifiques，1937，18.

[3]Griffiths P A.On Cartan method of Lie groups as applied to uniqueness and existence questions in differential geometry[J]. Duke Math Journal，1974，41：775-814.

[4]Green M L.The moving frame，differential invariants and rigiditytheoremsforcurvesinhomogeneousspaces[J]. Duke Math Journal，1978，45：735-779.

[5]Jensen G R.Higher order contact of submanifolds of homogeneous spaces[M].New York：Springer-Verlag，1977.

[6]Fels M，Olver P J.Moving coframes.I.a practical algorithm[J]. Acta Appl Math，1998，51：161-213.

[7]Fels M，Olver P J.Moving coframes.II.regularization and theoretical foundations[J].Acta Appl Math，1999，51：127-208.

[8]Olver P J.Joint invariant signatures[J].Found Comput Math，2001（1）：3-67.

[9]Kim P，Olver P J.Geometric integration via multi-space[J]. Regular and Chaotic Dynamics，2004，9：213-226.

[10]Calabi E，Olver P J，Shakiban C，et al.Differential and numerically invariant signature curves applied to object recognition[J].Int J Computer Vision，1998，26：107-135.

[11]Olver P J.Classical invariant theory[M].Cambridge：Cambridge University Press，1995.

[12]Kogan I A，Olver P J.Invariant Euler-Lagrange equations and the invariant variational bicomplex[J].Acta Appl Math，2003，76：137-193.

[13]Olver P J.Invariant submanifold flows[J].J Phys A，2008， 41：344-361.

[14]Marí Beffa G，Olver P J.Poisson structures for geometric curve flows on semi-simple homogeneous spaces[J].Regular and Chaotic Dynamics，2010，15：532-550.

[15]Shemyakova E，Mansfield E L.Moving frames for Laplace invariants[C]//Proceedings of ISSAC 2008.New York：ACM，2008：295-302.

[16]McLenaghan R G，Smirnov R G.An extension of the classical theory of algebraic invariants to pseudo-Riemannian geometry and Hamiltonian mechanics[J].J Math Phys，2004，45：1079-1120.

[17]Deeley R J，Horwood J T，McLenaghan R G，et al.Theory of algebraic invariants of vector spaces of killing tensors：methodsforcomputingthefundamentainvariants[J].Proc Inst Math NAS Ukraine，2004，50：1079-1086.

[18]Boyko V，Patera J，Popovych R.Computation of invariants of Lie algebras by means of moving frames[J].J Phys A，2006，39：5749-5762.

[19]Mundy J L，Zisserman A.Geometric invariance in computer vision[M]//Artificial Intelligence.Cambridge：MIT Press，1992.

[20]Weiss I.Geometric invariants and object recognition[J].Acta Applicandae Mathematicae，1993，10：207-231.

[21]Faugeras O.Cartan’s moving frame method and its application to the geometry and evolution of curves in the Euclidean affine and projective planes[M]//Applications of Invariance in Computer Vision.[S.l.]：Springer-Verlag，1994：11-46.

[22]Killing W.Erweiterung der begriffes der invarianten von transformation gruppen[J].Math Ann，1890，35：423-432.

[23]Mansfield E L.A practical guide to the incariant calculus[M]. Cambridge：Cambridge University Press，2010.

[24]Olver P J.Applications of Lie groups to differential equations6[M].2nd ed.New York：Springer-Verlag，1993.

[25]Olver P J.Recursive moving frames[J].Results Math，2011，60：423-452.

[26]Kogan I A.Inductive approach to Cartan moving frame method with applications to classical invariant theory[D].University of Minnesota，2000.

[27]Kogan I A.Inductive construction of moving frames[J].Contemp Math，2001，285：157-170.

[28]Kogan I A.Two algorithms for a moving frame construction[J].Cannad J Math，2003，55：266-291.

CHENG Limei,YUAN Wei,YAO Ruoxia

School of Computer Science,Shaanxi Normal University,Xi’an 710062,China

This paper presents a classical algorithm and an improved recursive method to construct moving frames and differential invariants based on the moving frame theory developed by Peter J.Olver and Mark Fels.It takes an example to demonstrate the constructive processes of two methods respectively for a Lie transformation group.The results indicate that the recursive algorithm has more advantages than the classical Maurer-Cartan approach,which can be applied to arbitrary group actions systematically. More importantly,it does not need the existing of a slice.Especially for multi-parameter transformation group,this recursive method is more convenient while constructing the corresponding moving frames and differential invariants.It is important that the corresponding Maurer-Cartan forms can be obtained as by-products step by step.The results presented here not only are new, but also provide a fundamental theory tool to the application study of signature curve for differential invariants.

recursive algorithm;classical Maurer-Cartan approach;moving frame;differential invariant

基于Mark Fels和Peter J.Olver的活動標架理論，給出了用經(jīng)典算法和改進的遞歸算法來構(gòu)造活動標架和微分不變量的代數(shù)構(gòu)造算法，并以一個李變換群為例演示了兩種方法的構(gòu)造過程。結(jié)果證明遞歸構(gòu)造方法與經(jīng)典的Maurer-Cartan方法相比較，不僅能夠系統(tǒng)地應用于任意的變換群作用，也不要求一個slice的存在，且對于多參數(shù)的變換群來說，其遞歸構(gòu)造方式使得相應的活動標架和微分不變量的構(gòu)造過程更便捷，也容易實現(xiàn)。重要的是，相應的Maurer-Cartan形也被一步步地構(gòu)造獲得。所獲得結(jié)果不僅是新的，且為微分不變量在簽名曲線中的應用研究提供了基礎(chǔ)理論支撐。

遞歸算法；經(jīng)典Maurer-Cartan算法；活動標架；微分不變量

A

TP301

10.3778/j.issn.1002-8331.1112-0527

CHENG Limei,YUAN Wei,YAO Ruoxia.Constructing moving frames and differential invariants and its applications in pattern recognition.Computer Engineering and Applications,2013,49（19）：147-152.

國家自然科學基金面上項目（No.11071278）。

成麗美（1986—），女，碩士研究生，主要研究方向：符號計算；袁偉（1984—），碩士研究生，主要研究方向：符號計算；姚若俠（1968—），通訊作者，女，博士/博士后，教授，研究生導師，主要研究領(lǐng)域：計算復雜性與符號計算，機器證明，孤子理論，可積系統(tǒng)。E-mail：rxyao2@hotmail.com

2012-01-02

2012-03-01

1002-8331（2013）19-0147-06

CNKI出版日期：2012-05-21http://www.cnki.net/kcms/detail/11.2127.TP.20120521.1139.018.html