基于Groebner基方法的射影不變曲線的構造

付澤豪 李耀輝 胡超棋

摘? 要： 提出利用Groebner基方法對射影不變曲線的構造方程進行求解。首先構造出二次曲線的一般方程且其系數用參數表示；然后，利用拉格朗日乘子法得到滿足最優擬合曲線時的條件，該問題由7個三次方程構成，其一般形式的解最多可以達到2187個。利用多項式環字典序下的Groebner基具有消元的性質將原問題轉化為三角型方程組，進而求解。討論了兩組點集通過該類方法擬合出的不變曲線，并用實例分析了曲線在射影變換時具有拓撲結構和次數不變性。

關鍵詞： 射影不變性； 擬合曲線； 拉格朗日函數； Groebner基

中圖分類號：TP301.6? ? ? ? ? 文獻標識碼：A? ? ?文章編號：1006-8228（2023）06-01-06

Construction of projective invariant curve based on Groebner basis method

Fu Zehao， Li Yaohui， Hu Chaoqi

（School of Information Technology Engineering， Tianjin University of Technology and Education， Tianjin 300222， China）

Abstract： In this paper， the Groebner basis method is proposed to solve the construction equations of projective invariant curves. First， the general equation of conic is constructed and its coefficients are expressed by parameters. Then， using the Lagrange multiplier method， the conditions for satisfying the optimal fitting curve are obtained. The problem consists of seven cubic equations， and the general form of the solution can reach 2187 at most. The original problem is transformed into a trigonometric system of equations by using the elimination property of Groebner basis under the dictionary order of polynomial rings. The invariant curves fitted by two point sets using this method are discussed， and the topological structure and degree invariance of curves in projective transformation are analyzed with examples.

Key words： projective invariance; fitting curve; Lagrange function; Groebner basis

0 引言

計算機視覺中，邊界曲線擬合是一個經典的問題，它在人臉識別，物體形狀匹配等領域都有重要的應用[1-4]。常用的邊界曲線的擬合方法有：直接最小二乘法、最小平方中值法和卡爾曼濾波擬合法[5-7]。但是在模式識別中，擬合的曲線必須具有射影不變性，即射影點集的擬合曲線恰好是原始點集擬合曲線的射影，我們稱這類曲線為射影不變曲線[8]。射影不變曲線能夠避免攝像機視點的變化以及物體運動對目標識別產生的影響。而上述方法擬合的曲線均不具備射影不變性這一特征而不被模式識別所采用。因此，構造出射影不變曲線有其現實需要。

目前射影不變曲線的擬合方法大多采用代數距離作為擬合誤差的測度，對最小代數距離進行逼近來實現擬合過程。文獻[9]提出將給定變換的絕對不變量的函數作為約束，通過計算最小代數距離下的參數得到擬合曲線。該方法雖然可以獲得符合要求的曲線，但是有些變換下不存在絕對不變量，方法不具備普適性。文獻[10]給出了用相對不變量作為約束條件的定理，同樣可以通過計算最小代數距離下的參數得到擬合曲線。該方法解決了擬合曲線普適性問題，但在后續參數的計算問題上，無法避免高次非線性方程組的求解，計算量較為龐大。

本文將曲線的系數矩陣作為約束條件，在給定變換群下，對系數矢量規格化，將曲線擬合問題轉化為最優化問題，并且利用多項式環字典序下Groebner基具有的消元性質，將問題轉化成三角型方程組進行求解，計算出擬合曲線的參數，最終對實驗結果擬合曲線的射影不變性進行驗證與分析。

1 Groebner基方法

當給出一系列點擬合邊界曲線時，一方面期望保留原圖形或圖像的主要特征，另一方面期望曲線的計算簡單且能夠良好的逼近。因此，擬合時采用二次曲線進行擬合。我們主要研究當給定一組點集時，滿足上述要求的曲線有多少條且它們滿足什么樣的性質。該問題最終轉化為非線性方程組的求解問題。為了解決該問題采用Groebner基方法實現。

Groebner基理論屬于計算代數幾何理論。該理論于1964年由Hirona-ka H首先引入并稱其為標準基。1965年Buchberger首次提出多項式理想的Groebner基算法，在隨后的幾十年里，不斷地改進優化，其理論在研究過程中一般將問題轉化為非線性多項式問題，然后利用Groebner基理論對所轉化的數學問題進行求解。下面給出Groebner基的定義：

定義1 在多項式環[k[x1，…，xn]]，一個有限子集[G={g1，…，gn}]的理想[I?k[x1，…，xn]]，若[LT（g1），…，LT（gt）]

[=LT（I）]，則[G]是一個Groebner基，其中[LTg1]表示按照某種排序（多為字典序）的多項式[g1]的首項。[LTg1，…，LTgt]表示以[LTg1，…，LTgt]為元素所生成的理想，[LTI]表示[I]中所有元素的首項組成的集合。

直觀來說，Groebner基是理想的代表元素，若計算出理想的一組Groebner基，那么理想的一些好的性質可以更為方便的研究。

多項式理想保持了系統零點的不變性，即：最后得到多項式系統的解就是原多項式系統的解。具體來說，假設有一個多項式方程組：

[a11xp111+a12xp122+…+a1nxp1nn=0a21xp211+a22xp222+…+a2nxp2nn=0……an1xpn11+an2xpn22+…+annxpnnn=0]? ⑴

通過利用Groebner基可以對部分元素進行消元處理，可以將原多項式系統轉化為：

[a'11xp'111+a'12xp'122+…+a'1nxp'1nn=0a'21xp'211+…+a'2n-1xp'2n-1n-1=0? ………? ? ? ? ? ? ? ?a'n1xp'n11+m=0? ? ? ? ? ? ? ? ?]? ?⑵

通過計算式⑴的Groebner基，并能保證這兩個方程組的解相同，且稱式⑵為三角型方程組。在對于復雜的多元多項式方程的求解過程中，可以先確定字典序，然后求得其多項式理想的Groebner基，最后計算Groebner基中多項式的根，即為原本多元多項式方程的解。

在構造平面二次曲線的過程中，需要建立拉格朗日方程求解曲線的多個參數值，即要解決高次多變元方程組的求解。這類問題在參數以及約束過多的情況下難以計算。引入Groenber基方法，其理論在研究過程中將問題轉化為非線性多項式問題，利用Groebner基理論消元的性質求解擬合方程的系數，該方法不需要迭代，直接可以求出非線性方程組的解。

2 射影不變性曲線的構造

對于邊界曲線的擬合，首先給定平面上的點集S，它是由[xi，yi1iN]的集合，然后利用點集的數據擬合出可以代表點集的閉合曲線，并且保證其具有射影不變性。良好的擬合曲線，需要滿足兩個性質：①曲線良好逼近，數據小的變化只會導致擬合曲線小的變化；②射影不變性，即射影點集的擬合曲線恰好是原始點集擬合曲線的射影。

2.1 二次不變曲線擬合理論

設所要求的二次曲線為：

[Q2x，y=Ax2+Bxy+Cy2+Dx+Ey+F=0] ⑶

該曲線也可以表示為矩陣及矢量相乘的形式，即[Q2x，y=v'Pv]，其中[v]表示變元向量，[v]是[v]的轉置且[v=[x，y，1]]；[P]是系數矩陣，為：

[P=AB2D2B2CE2D2E2F]? ? ⑷

為了擬合曲線，將任一點[xi，yi]到曲線[Q2x，y]的距離定義為[Q22xi，yi]，點集到該曲線的距離為[1Ni=1NQ22xi，yi]。若要擬合出性質良好的二次曲線需要保證射影不變性及其對原曲線的良好逼近兩點性質。為了滿足第二個性質需要使點集到給定曲線的距離盡可能??；雖然[Q2x，y]與k[Q2x，y]表示同一條曲線，但是曲線外一點[xi，yi]到曲線的代數距離會隨著k值的不同而不同。為了保證點集上任一點到曲線代數距離的惟一性，構造不變射影曲線時增加約束條件即要求擬合時二次曲線系數矩陣的行列式[|P|=1]。最終，將二次曲線的不變性擬合轉化為帶有約束條件的優化問題，若給定點集S，就可以得到：

[mini=1NQ22xi，yis.t. P=1]? ? ⑸

利用拉格朗日乘子法，將帶有約束條件的優化問題進一步轉為無約束條件的優化問題：

[L=i=1NQ22xi，yi+λ（P-1）]? ?⑹

其中，[λ]為拉格朗日乘子，可得到一個七元三次非線性方程組：

[?L?A=2i=1Nx2i*Q2xi，yi+λCF-E24=0?L?B=2i=1Nxiyi*Q2xi，yi+λDE4-BF2=0?L?C=2i=1Ny2i*Q2xi，yi+λAF-D24=0?L?D=2i=1Nxi*Q2xi，yi+λBE4-CD2=0?L?E=2i=1Nyi*Q2xi，yi+λBD4-AE2=0?L?F=2i=1NQ2xi，yi+λAC-B22=0P=ACF+BDE4-CD24-AE24-B2F4-1=0] ⑺

由于上述方程組是非線性的，直接消元非常困難，采用數值法求解不能保證得到滿足上述方程的所有解，根據前述的Groebner基理論得知其具有消元的性質，若計算非線性方程組生成理想在變元字典序下的Groebner基會得到另一個非線性方程組且是一個三角型方程組，這樣我們就容易求出其中的單變元方程的解，然后將該變元的解代入含有兩個變元的方程求出另一個變元的解，最后，計算出所有變元的解。具體計算時，首先將式⑺中的變元按字典序排序為[{λ，A，B，C，D，E，F}]，再將式⑺中方程組左側的各項構建系統的理想，然后計算該理想的Groebner基，可得到如下一般形式的方程組：

[k=0Na1kFk=0k=0Na2kFk+b2E=0k=0Na3kFk+b3D=0k=0Na4kFk+b4C=0k=0Na5kFk+b5B=0k=0Na6kFk+b6A=0k=0Na7kFk+b7λ=0]? ? ? ?⑻

該方程組第一個方程只含有變元F，因此求解過程只需要先求出F，再將F的值代入第二個方程求解出E的解，這樣逐一得到其他所有變元的值。實際上，有時在計算Groebner基時并非得到的方程數和變元一樣多，后面具體實例中可以看到，有時我們得到的方程組中方程的個數并不是七個而是八個，但是變元個數仍然只有七個。這種情況，必有一個方程和其他方程的變元個數一樣多，計算時，取這兩個方程的任一個計算新增加變元的解，用另外一個方程進行驗證，去掉不滿足這兩個方程的解。這樣，可以排除非擬合曲線的解，在計算后面其他變元的解時可以大大降低非線性方程組的求解復雜度。這是一種特殊的形式，相比一般形式可以節約一定的算力。

根據代數方程組的一般定理可知七元三次方程組在復數域上最多可以有2187個解，其中很多解可能是復數解并且對于實際擬合曲線無意義，因此，討論一般情況下的射影曲線的形式與參數之間的關系也會非常復雜。在實際的邊界擬合問題上，并非要計算出方程組的全部解，我們只需要在全部實數解中得到與點集距離最近的那一條曲線。而且在求解變元的過程中，變元[λ]也并非是曲線所需要的參數，因此可以不作計算，來達到減輕工作量的目的，下面通過實例來討論點集曲線擬合所得到的解。

2.2 不變曲線擬合的實例討論

為了計算具體的不變擬合曲線，假設目標邊界過點[q1：5，0，q2：0，5，q3：-5，0，][q4：0，-5，q5：3，4，q6：-3，-3]。采用前述計算二次曲線的理論擬合該目標邊界曲線，使其滿足射影不變性。

將點集坐標代入式⑺可以得到如下非線性方程組：

[2824A+ 378B + 450C + 18E+ 136F+λCF -E24=0378A + 450B+546C+18D+42E+42F + λDE4-BF2=0450A+545B+3174C+42D+74E+150F + λAF-D24=018B+42C+136D+42E+λBE4-CD2=018A+42B+74C+42D+150E+2F+λBD4-AE2=0136A+42B+150C+2 E+12F+λAC-B22=0ACF+BDE4-CD24-AE24-B2F4-1=0] ⑼

將式⑼方程組左側的各多項式作為集合，構造多項式理想，確定變元的字典序為[[λ， A， B， C， D， E， F]]，計算該序下的Groebner基。為了構造二次曲線，當選定6個點構成點集，通過計算Groebner基，恰能生成七個變元的三角型方程組。我們先得到多項式系統生成理想，然后計算該理想在字典序[{λ，A，B，C，D，E，F}]下的Groebner基，得到消元理想，其中含有七個多項式，其形式如下：

[G1=f1FG2=f2E，FG3=f3D，FG4=f4C，FG5=f5B，FG6=f6A，FG7=f7λ，F]? ⑽

由式⑽可以看出新得到的多項式系統自上至下每個多項式新增一個變元，令系統等于0得到三角型方程組，其中第一個多項式[G1]只含有單變元F且各項的次數如下：

[G1=a69F69+a66F66+…+a3F3+a0=0]? ⑾

其中，[a0，a3，…，a69]是各此項的系數且均為常數，因其為單變元方程故易得到F的解。根據代數基本定理，其最多有69個解（重根以重數計）。在這69個解中只有五個實數解。再將F的實數解分別代入[G2，G3，G4，G5，G6]，在這些多項式中同樣包含了關于F的高次項以及其他單一變元的單次項，因此，每一個F的解都可以對應其他變元的惟一解，由于其他方程過于冗長不再一一列舉。最終，可以得到5組實數解。而[G7]中的變元[λ]由于不屬于曲線的參數，因此不作計算。5組實數解結果如表1所示。

將上述參數代入⑶式中，得到五個方程，分別對應以下五條擬合曲線，如圖1所示。

這五條曲線包含了兩條橢圓，三條拋物線。說明通過點集擬合出的曲線具有不惟一性。并且根據二次不變曲線擬合理論，這五條擬合曲線均滿足射影不變性的條件。不過，并非所有不變曲線都可以做到良好逼近，上述例子中所給出的點集分布可以看出，該點集更加適合通過橢圓來擬合曲線，通過比較點集到曲線的代數距離[1Ni=1NQ22xi，yi]可以驗證出這一點，得到4條曲線中最佳逼近的那一條擬合曲線。4條擬合曲線到[q1， q2，q3，q4，q5，q6]的距離如表2所示。

根據結果可以明顯比較出曲線5具有更加良好的逼近條件，因此擬合該點集的最佳曲線方程應當為：[-0.347x2+0.105xy-0.343y2+0.089x+0.101y+8.586=0]。

上例中得到的Groebner基只是一般情況，并非所有擬合點集過程都可以得到規整的三角型方程，不過其方程仍然可以轉化為非線性方程組來計算。下面將點集中[q6：-3，-3]改為[q7：-3，-4]，進行計算，可以發現這一現象。

將點[q1，q2，q3，q4，q5，q7]的坐標代入式⑺可以得到如下非線性方程組：

[2824A+ 432B + 576C + 136F+λCF -E24=0432A + 576B+768C+48F + λDE4-BF2=0576A+768B+3524C+164F + λAF-D24=0136D+48E+λBE4-CD2=048D+164E+λBD4-AE2=0136A+48B+164C+12F+λAC-B22=0ACF+BDE4-CD24-AE24-B2F4-1=0] ⑿

將式⑿方程組左側的各多項式作為集合，按照相同字典序排列后求出Groebner基含有八個多項式，其具體形式如下：

[G1=f1FG2=f2E，FG3=f3E，FG4=f4D，E，FG5=f5C，FG6=f6B，FG7=f7A，FG8=f8λ，F] ⒀

其中，[G2]和[G3]都是包含了變元E和F的多項式，且[G4]含有三個參數，但這仍然是非線性方程組，可以先舍棄[G2]的方程組，計算得到69組解，其中11組為實數解。再將這11組解帶入方程[G2=0]進行驗證，可以發現均滿足等式，因此這11組解就是式⑿的實數解，具體結果如表3所示。

通過比較曲線與點集的代數距離可以發現，點集的所有點均落在擬合曲線[-0.342x2-0.343y2+8.550=0]上，且曲線符合射影不變性特征。

上文兩例可以說明該方法對于擬合不變曲線具有普適性，通過Groebner基理論轉化的非線性方程組都可以更加簡單得求出原本方程組的解，得到的最優解即為最佳擬合曲線的參數。

2.3 曲線射影不變性分析

上節所求得曲線應當保持射影不變性的特征，即射影點集的擬合曲線恰好是原始點集擬合曲線的射影。假設點集[（xi，yi）（1iN）]的擬合曲線為[Q2x，y=Ax2+Bxy+Cy2+Dx+Ey+F=0]，在經過射影矩陣[τ=a11a12a13a21a22a23a31a32a33]的射影變換后，點集中的點坐標改變得：

[x'i=a11xi+a12yi+a13a31xi+a32yi+a33y'i=a21xi+a22yi+a23a31xi+a32yi+a33]? ⒁

點集[（x'i，y'i）（1iN）]即為射影變換后的點集，曲線[Q2x，y]經過τ的射影變換后，得：

[Q'2x，y=A'（x'）2+B'x'y'+C'（y'）2+D'x'+C'y'+F'=0] ⒂

其中[x'=a11x+a12y+a13a31x+a32y+a33y'=a21x+a22y+a23a31x+a32y+a33]，可以解出式⒂的參數[A'，B'，C'，D'，E'，F']，若式⒂可以擬合出點集[（x'i，y'i）（1iN）]，則說明擬合曲線[Q2x，y]具有射影不變性的特征，反之則沒有。

根據此判據，可以通過一次射影變換對上節中兩條曲線的射影不變性進行如下驗證。

設邊界點[q1，q2，q3，q4，q5，q6]，[q7]經過變換矩陣τ后變為[q'1，q'2，q'3，q'4，q'5，q'6]，[q'7]，射影變換矩陣τ為：

[τ=122212001]

則邊界點的坐標變換根據⒁式可得：

射影變換后的擬合曲線如圖2所示。

可以看出，射影變換后的曲線可以很好的擬合出影射變換后的點集，其拓撲結構仍是橢圓，其方程仍是二次方程，故曲線[-0.347x2+0.105xy-0.343y2+0.089x+0.101y+8.586=0]和[-0.342x2-0.343y2+8.550=0]擬合邊界點，不僅滿足曲線的良好逼近，而且具有射影不變曲線的性質。證明了本文方法可以高效、準確地進行曲線擬合。

3 總結

本文構造出平面曲線的二次曲線射影不變性擬合一般方法。該方法將擬合過程中的一般非線性方程通過計算變元字典序的Groebner基消元得到三角型方程組，然后進行求解。該方法克服了Gauss-Seidel迭代只能求解線性方程組，而Newton迭代只能求解單變元非線性方程組的問題。在計算機視覺領域，對運動與模糊物體的識別的底層算法進行了優化。將來隨著算力的提升，可以利用該方法對四次曲線的擬合對這類曲線進行更精確的擬合。

參考文獻（References）：

[1] Yang F， Tan X. Establishment and Analysis of Face

Recognition Model Based on Least Square Method[C]// 2018 International Conference on Mathematics， Modelling， Simulation and Algorithms （MMSA 2018），2018：67-70

[2] Wu W， Qian C， Yang S， et al. Look at Boundary： A

Boundary-Aware Face Alignment Algorithm[C]// 2018 IEEE/CVF Conference on Computer Vision and Pattern Recognition.IEEE，2018：2129-2138

[3] MerkerL， Will C， Steigenberger J， et al. Object Shape

Recognition and Reconstruction Using Pivoted Tactile Sensors[J]. Mathematical Problems in Engineering，2018（1）：1-11

[4] Fan Y N， Lang B. An Object Shape-matching Method

Using Contour Orientation Feature[J].Computer Technology and Development，2018，28（1）：88-92

[5] Fitzgibbon A， Pilu M， Fisher R B. Direct least square fitting

of ellipses[J]. IEEE Trans.patt.anal.mach.intell，1999，21（5）：476-480

[6] Roth G， M.D. Levine. Extracting Geometric Primitives[J].

Academic Press， Inc，1993，58（1）：1-22

[7] PorrillJ. Fitting ellipses and predicting confidence

envelopes using a bias corrected Kalman filter[J]. Image & Vision Computing，1990，8（1）：37-41

[8] 孫即祥.模式識別中的特征提取與計算機視覺不變量[M].

北京：國防工業出版社，2001

[9] Reiss Thomas H. Recognizing Planar Objects Using

Invariant Image Features[M]. Springer-Verlag，1993

[10] Forsyth D， Mundy J L， Zisserman A， et al. Projectively

invariant representations using implicit algebraic curves[J]. Image and Vision Computing，1991，9（2）：130-136

[12] 徐正偉，吳成柯.二維形狀的透視不變性識別[J].自動化

學報，1995，21（4）：431-438

[11] Rajashekhar， Chaudhuri S， Namboodiri V P. Image

retrieval based on projective invariance[C]. Image Processing， 2004. ICIP '04. 2004 International Conference on. IEEE，2004：405-408

[13] DavidCox， JohnLittle， DonalO'shea. Ideals， varieties， and

algorithms：anintroductional algebraic geometry and commutative algebra[M]. 世界圖書出版公司北京公司，2013

[14] 齊紫微.應用Groebner基方法求解代數方程組的解[J].

裝甲兵工程學院學報，2007，21（4）：90-91

[15] 張政武.空間二次曲線代數不變量的幾何解釋[J].機械

科學與技術，2008，27（12）：1670-1672

[16] 袁立行，鄭南寧.一種新的空間透視不變量計算方法[J].

西安交通大學學報，1997，31（1）：84-89

[17] 趙臨龍.二階線性微分方程不變量解法的新類型[J].西南

民族大學學報（自然科學版），2018，44（4）：402-405

[18] 張文哲.參數Groebner系統在偏微分代數方程中的應用[J].

數學的實踐與認識，2021，51（24）：171-180

[19] Baik， Hyungryul， Samperton， et al. Spaces of invariant

circular orders of groups[J]. Groups Geometry & Dynamics，2018，12（2）：721-763

[20] 嚴飛，張銘倫，張立強.基于邊界值不變量的對抗樣本檢測

方法[J].網絡與信息安全學報，2020，6（1）：38-45