（计算数学专业论文）吴方法在pnp问题中的应用.pdf

国防科学技术大学研究生院学位论文 摘要 n 点透视问题( p e r s p e c t i v e n - p o i n t ，简称p n p ) 起源于摄影测量学中的古老问题，近2 0 年 来又在图像分析和自动制图学、计算机视觉、机器视觉与机器人学及摄影测量学等领域中 广为关注的摄像机定位问题中重新提出，例如单目测距、位置估计及基于模型的视觉系统 等。1 9 8 1 年f i s h i e r 和b o l l e s 把根据控制点定位的l d p 问题改写为数学形式，称为n 点透 视问题。随后，引发了一系列的讨论，总体上可分为数值解法和解析解法两大类。 然而，在现有的各种解法中，一个另大家都很头痛的问题就是p n p 问题的多解性。 在实时系统中或在动画合成领域控制点的增加会导致费用的增加。而且，控制点越多，算 法就越复杂，计算速度就越慢，因此多年以来p n p 问题研究的重点就是采用尽可能少的点 设计出一个简单、使用、有效的算法，这使得p 3 p 和p 4 p 成为首选。本文主要是使用解析 的方法，从而得到p n p 问题多解的判定条件。 本文第二章河先用吴消元法对p 3 p 问题的多元多项式方程组进行了零点分解，从而 得到了p 3 p 方程组的特征列。然后根据特征列中的多项式的次数把特征列分组，分别对每 一组进行分析，从而得到了p 3 p 问题的解的完全分类。 第三章对于p 4 p 问题所产生的超约束方程组，采取巧妙的分组分解的方法，化解了 冈过多约束所带来的分解时的困难。在得到了每一组的特征列以后，再对其综合分析，从 而得到了一系列的p 4 p 问题存在多解时的充分条件。而且本文证明了文献 2 中的结论是水 文所得结论的特例。基于上面的判定条件，在实时系统中，可以很好地避开不稳定点，或 者为实时决策提供条件，从而提高了系统的稳定性和准确性。 关键词：吴方法p n p 问题摄影测量计算机视觉机器人视觉图像分析 第1 页 a b s t r a c t t h e p e r s p e c t i v e n - p o i n t ( p n p lp r o b l e m p h o t o g r a m m e t r y b u ti n r e c e n tt w od e c a d e s ， o r i g i n a t e d f r o mt h e a n c i e n t p r o b l e m o f i th a sb e e nr e i n t r o d u c e di nt h ef o t - f i to ft h e d e t e r m i n a t i o no ft h el o c a t i o no ft h ec a m e r ai nm a n yf i e l d s ，s u c ha si m a g ea n a l y s i s ，a u t o m a t e d c a r t o g r a p h y , c o m p u t e rv i s i o n ，m a c h i n ev i s i o n ，r o b o t i c sa n dp h o t o g r a m m e t r y i n1 9 8 1 ，f i s h i e ra n d b o l l e st r a n s f o r m e dt h el d p p r o b l e mw h i c hr e l i e s o nt h ef e a t u r ep o i n t si n t ot h em a t h e m a t i c a l f o r m ，w h i c hi st h es o c a l l e dp n pp r o b l e ma n ds u b s e q u e n t l y , as e r i e so fd i s c u s s i o na b o u tt h e p r o b l e mw e r ei g n i t e d a l lt h ed i s c u s s i o nc a nb ec a t e g o r i z e di n t ot w og r o u p s ：n u m e r i c a ls o l u t i o n a n da n a l y t i cs o l u t i o n h o w e v e r ，t h em o s tt r o n b l e s o m ed i f f i c u l t yi st h em u l t i s o l u t i o no ft h ep n pp r o b l e m i n r e a l t i m es y s t e mo ri nt h ef i e l do fc a r t o o n s y n t h e s i z i n g ，t h ei m p r o v e m e n to ft h ef e a t u r ep o i n t s w i l la l s o1 e n dt ot h ei m p r o v e m e n to ft h ee x p e n d i t u r e ，i na d d i t i o n t h em o r ef e a t u r ep o i n t sw e c h o o s e ，t h em o r ec o m p l e x i t yt h e a r i t h m e t i cw i l l h a v e s i m u l t a n e o u s l y t h e s p e e d o ft h e c o m p u t a t i o nw i l la l s od e c l i n ea n ds o ，f o rm a n yy e a r s ，o n eo f t h ee m p h a s i s s e so nt h er e s e a r c ho f t h ep n pp r o b l e mi st of i n das i m p l e ，p r a c t i c a la n de f f e c t i v ea r i t h m e t i cw h i c hb a s e do na sl e s s f e a t u r ep o i n t sa sp o s s i b l et h u st h ep 3 p p r o b l e ma n d t h ep 4 p p r o b l e mi st h ef i r s tc h o i c e i nt h i s p a p e r ，t h ea n a l y t i cm e t h o d i sm a i n l yu s e dt og e tt h em e t h o do f d i s c r i m i n a t i o n i nc h a p t e r2 ，t h ew u r i t t sd e c o m p o s i t i o nm e t h o di su s e dt od e c o m p o s et h ee q u a t i o n st h e p 3 pp r o b l e ma tf i r s ta n ds o m ec h a r a c t e r - s e t sa r eo b t a i n e d a c c o r d i n gt o t h ed e g r e eo ft h e p o l y n o m i a l s ，t h ec h a r a c t e r - s e t sa r ec a t e g o r i z e d ，a n dt h e nt h ec o m p l e t ec l a s s i f i c a t i o no f t h ep 3 p p r o b l e m i so b t a i n e d i nc h a p t e r3 ，as m a r tm e t h o do fg r o u p i n gd e c o m p o s i t i o n ，b a s e do nw h i c ht h ed i f f i c u l t y t h a tt o o m a n yr e s t r i c t i o n l e a dt oi s c o n q u e r e d ，i su s e d t o d e c o m p o s et h es u p e r r e s 打i c t l o n e q u a t i o n so ft h ep 4 pp r o b l e m a f t e rg e t t i n gt h e c h a r a c t e r s e to fe a c hg r o u p ，a n i n t e g r a t i v e a n a l y s ei sp e r f o r m e da n das e r i e so f s k i f f i c i e n tc o n d i t i o nt od e c i d et h es u mo ft h es o l u t i o no ft h e p 4 pp r o b l e ma r eo b t a i n e d a n dm o r e o v e r , i ti s p r o v e d t h a tt h ec o n c l u s i o n i n 【2 】i s t h e s p e c i f i c a t i o no ft h ef o r e g o i n gc o n c l u s i o ni n t h i s p a p e r b a s e do i l t h ep r e s e n t e dc o n d i t i o no f d i s c r i m i n a t i o ni nt h i sp a p e r , t h o s eu n r e l i a b l ep o s i t i o n sc a nb ee a s i l ya v o i d e d ，o fs o m ed e c i s i o n s c a nb eq u i c k l ym a d et h e r e f o r e ，t h es t a b i l i t ya n d a c c u r a c yo f t h es y s t e m a r ei m p r o v e d k e y w o r d s ： w u r i t t s d e c o m p o s i t i o nm e t h o d ，p n pp r o b l e m ，p h o t o g r a m m e t r y , c o m p u t e rv i s i o n ，r o b o t i cv i s i o n ，i m a g ea n a l y s i s 第1 i 页 独创性声明 本人声明所呈交的学位论文是我本人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含 其他人已经发表和撰写过的研究成果，也不包含为获得国防科学技术大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示谢意。 学位论文题目：芸友鎏查! 业囵基主曲廑屈 学位论文作者签名：二班2 埠日期：似埘；年三月7 日 学位论文版权使用授权书 本人完全了解国防科学技术大学有关保留、使用学位论文的规定。本人授权 国防科学技术大学可以保留并向国家有关部门或机构送交论文的复印件和电子 文档，允许论文被查阅和借阅；可以将学位论文的全部或部分内容编入有关数据 库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论文。 ( 保密学位论文在解密后适用本授权书。) 学位论文题目： 芸友洼查塑闰壁生的座围 学位论文作者签名 作者指导教师签名 日期：叫年亿月夕日 日期：勿净，之月9 日 国防科学技术大学研究生院学位论文 图i 图2 图3 图4 图5 图6 三点透视图 p 3 p 两组解 p 4 p 几何形式 四点透视图 图表目录 2 - - 5 组解的几何形式 三棱锥 i i第页 7 1 9 2 0 2 2 2 8 2 9 第一章绪论 1 ip n p 问题的由来及其发展现状 n 点透视问题是起源于摄影测量学中的一个古老问题【1 1 ，它是根据物体上n 个相应点 来确定照相机的位置和方向。匕关系到许多重要的领域，例如计算机直观显示 】、计算机 视觉【6 1 、自动化、图像分析、自动作图川、摄影测量叫】、机器人学【5 j 和基于模型的机器视 觉系统m 1 ，等等。f i s h i e r 和b o l l e s t l l 把这个问题总结如下： “绘定空问1 2 个控制点的相互位置关系，弗且给定每对控制点与另外一个被称为透射 中心的点的连线的夹角，计算每个控制点到透射中心的线段的长度。” p n p 问题的研究主要包括以下两个方面： 1 设计出能够t h j 来找出p n p 问题所有或者部分解的稳定且快速的算法。 2 给出p n p 问题的解的分类，也就是说给出p n p 问题存在，个，两个，三个或更多 解时的条件。 对于第个问题，目前己经有了许多结果，然而，第二个问题仍然有待进步深入的 探讨。基于对算法要求简单，使用，高效的考虑，主要的研究大都是针对p 3 p 和p 4 p 问题 的。多年以来研究者们作出了大量有益的探索，p 3 p 问题主要进展主要集中于以下几个力 面： ( 1 ) r a n s a c 算法。1 9 8 1 年文献 1 】列出p 3 p 方程组并通过其次代换把p 3 p 问题转化 为求解一个双丸一次方程。他们注意到每一组正解，商一组负解与之对应，因 而实际上最多只有四组正解，并举山了等边三角形时存在四组正解情形的实例， 他们通过计算观察出p 3 p 问题般有l 一2 组正解，少数情况f 有3 4 组正解。 文献 1 还提出了一种迭代算法，思路是让其中一点沿着一边滑动，据此确定其他 点的位置。文献f 1 1 还对l d p 给出了r a n s a x l d 算法。 ( 2 ) 新的化简算法。1 9 8 8 年l i n n a i n m a a 等人在文献【3 1 中指出如果有很多三角形 被提取出来或有其他几何限制，就可以通过三个控制点求解，并对p 3 p 方程 组设计了一个简单的化简方程。1 9 9 t 年文献【1 9 1 还总结了国际上已有的6 种 主要解法。包括g r u n e r t ( 1 8 4 1 ) ，m e r r i t ( 1 9 4 9 ) ，s m i t h ( 1 9 6 5 ) ，g r a f a r e n d ，l o h s e 和s c h a f f r i m ( 1 9 8 8 ) ，l o h s e ( 1 9 8 9 ) 和文献 1 9 中的方法。 ( 3 ) 三角函数方法。1 9 9 2 年d e m e n t h o n 等人脚j 总结了对p 3 p 问题的研究进展。文献 2 0 中采用了种新的使用三角函数的解法，但仍归于双二次一元八次方程。文 献 2 0 】中评价已有乃。法的共同缺点是需要较多的浮点操作，并指出采用平行投影 和透视可减少运算量。 ( 4 ) 利用同一平面内三角的方法 7 , 3 2 。1 9 8 9 年d h o m e t 7j 等人指出，已知三个控制点也 就确定了三边，故可用此法求解。并总结了对多解的主要处理方法：负解舍去， 保持三边可见及物体整体可见等。1 9 9 6 年王建刚等人m 给出了基于神经网络匹配 1第页 国防科学技术大学研究生院学位论文 的方法。 ( 5 ) 对多解对象的深入研究 t7 , 2 1 1 。文献 1 认为p 3 p 方程组最多有四组解并可达到。1 9 8 6 年w o l f e 等人【1 l 】提出了一种通过对不等边三角形反射形成多解的方法，并指出使 用三个控制点的四组正解最多可形成2 4 个摄像机位置，并指出p 3 p 算法的难点 之一是处理靠得很近的解。1 9 8 8 年文献f 3 1 1 认为一般有1 2 组正解，少数情况有 3 4 组正解。1 9 9 1 年w o l f e 等人m 1 采用一种“t h e c a n o n i c a l v i e w ”的假 设为p 3 p 问题1 4 解的不确定集合作出了一种几何解释，并由产生的解图像证 实了文献1 1 的结论。文献 1 7 中还注意到了一种特殊形式的多解现象“r o t a t e dl e g ”，并指出这种形式多解的几何条件，还指出其他多解现象可由 “r o t a t e d c i r c l e ”和“s w e e p r o t a t e d c i r c l e ”的方法产生。 ( 6 ) 涉及p 3 p 问题应用的其他1 ：作1 3 6 , 3 7 1 。由于p 3 p 阀题的多解现象，一部分工作转向 了p 4 p 问题。1 9 8 1 年文献 1 】认为通常四个控制点共面可唯一确定摄像机位置。 1 9 8 9 年文献 1 9 断言4 i 能从p 3 p 确定摄像机位置转向求解p 4 p 并给出了p 4 p 的一 般解法。1 9 9 5 年a b i d i l 5 1 等人建立了种利用四个共面的控制点的p 4 p 算法，并 总结到：现有的p 3 p 解法中，有的是补充其他几何特征建立了算法 i , 2 0 3 1 i ，有的提 出一种方法来研究正解的个数及各解之间的位置关系 17 , 2 1 1 ，通过对一元四次方程 的根进行估计的方法没能给人令人信服的几何条件，很长一段时间一直停留在“对 p 3 p 问题l 一4 解的_ ；确定集合作出了一种几何解释”的水平。1 9 9 8 年，文献f 1 2 1 根据p 3 p 存在多解时的几何图形，给出了特殊情形下的充要条件，并且对于一般 情形，把p 3 p 方程组化简，得到双一元四次方程，然后根据s t u r m 定理来判定这 两个一元四次方程组的数f 【，并且给出了判定条件，分析了多解的几何分布情况。 2 0 0 1 年，x s g a o 等人文献 3 3 】给出用吴方法给出问题的解的分类。 ( 7 ) 对于彳i 共面p 4 p 问题多解现象的研究。z y h u 和f c w u 在文献 2 e e 分别给出了 存在2 4 组正解时荐控制点所满足的几何关系。但是遗憾的是，该文给出的结果 只能解释多解现象，而1 i 能应用于实际计算过程。 ( 8 ) 五个及更多控制点多解的研究。基于对实际问题的考虑，即在要求速度和精度方 面都要高的情况下，迫使问题一般只能局限于三个控制点和四个控制点的情形。 而对于五个控制点的情形，极少情况下出现多解，则很少有人研究，至于六个发 更多控制点，文献 1 中已经证明只有唯解。 本文给出了利用吴方法分析p 3 p ，p 4 p 问题多解的途径，并且给出了分别存在2 - - 5 个 解时的判别式，实现起来相当简单，完全可以达到实时系统的需要。 1 2 吴方法简介 吴文俊先生的数学机械化思想是在七t 。年代逐步形成的，其后的l 余年里不断获得发 展和丰富。长期以来，数学界形成一种共识：线性数学与非线性数学是两个截然不同的领 域，有着天壤之别。数学中的种种线性问题，从理论到方法都已相当成熟，数学家们运用 自如。然而即便是相当简单的非线性数学问题，却往往令数学家们束手无策。大家知道， 第2 页 = ：一皇堡垒鲨塑堇兰些型垄兰垒垒垒：一 数学上从线性到非线性的第一步跨越，恰恰是由一次多项式到高次多项式予以实现的。高 次代数方程组求解是数学家们面对的非线性数学问题中的首要问题。这一问题是如此基 本，如此重要，如此困难，吸引了大量数学家前赴后继地为之奋斗。这一问题的探索，理 论上引发了代数几何学的建立和蓬勃发展，但方程组求解步履维艰。数百年来，仅出现少 数几种算法，且这几种算法，在理论或实效上存在着种种欠缺，有待进一步研究改进。吴 文俊消元法的建立，为代数方程组求解给出了完整的理论，提供了有效的算法。吴消元法 的建立是近代非线性数学研究中取得的重大实质f 生进展。下面就吴文俊消元法即吴方法给 予简要的介绍。 1 2 1多项式方程组的零点集 设k 是特征为零的域。k 上以。，x ：，。为变元的多项式环k i x ，x ：，x 。】，简记为 k 【x 环k x 中多项式的有理分式域k ( xi ，x ：，x 。) ，简记为板x ) 仔多项武 p ( x ) = p ( x ，x ：，x 。) ek 嗍，我们约定：存p 0 ) 中实际山现的变元中下标最大者称作p ( x ) 的 主变元。若x 是p ( x ) 的主变元，则p ( x ) 口7 - 写为 p 0 ) = ，+ j ? + t 的低次幂 d 。是p ( x ) 雨j t 变元的最高幂次，记为d e g 。( 尸( x ) ) ，首项系数1 通常是j 。x ：，x 一、的多项式 称为p ( x ) 的初式。 以k “表示k 卜的 维线性空间。给定一组多项式p s = 只( x ) ，b ( x ) ，只( 曲) ，其中 只( x ) 研x ，i = 1 , 2 ，。域k 中的i 1 重数组x o = o ? ，x ? ，x ：) 若满足p ( x ) = 0 ，i = 1 , 2 ，m ， 则称一是多项式方程组p s = o 的一个解。冈数组x o 可视作 维线性空间k ”中的一个点， 故又称x o 为多项组p s - - 0 的一个零点。记i 是数域的一个扩域( 代数扩域或超越扩域) 。 多项式组p s 在空间i “叶1 的零点称为扩充零点。如无特别说明，将不加区分统称多项组的 零点。多项式组p i s 的全体零点记为z e r o ( p s ) 。设，= 州) ，( ) ，( x ) 是另一组给定的 多项式。z e r o ( p s ) 。p 的零点使每一，( x ) ，j = 1 , 2 ，r 都不为零着，其全体记为z e r o ( p s 1 ) 求 解代数方程组p s = o ，无非是确定多项式组尸s 的零点集z e r o ( p s ) 。 回顾线性方程组的消去法，其结果是导致方程组的三角化。类t v a - ：线性的情形，我们 称多项式组是三角化的，如果变元是依次在多项式中出现的。三角化的多项式组义如下形 式： 五( x ，) ， t 2 ( u ，x 1 ，x 2 ) 其中多项式i k u i ，“：，l f d ，x 。，x i ，i = 1 2 。而h ，i = 1 , 2 ，d 可视为参变元。 可以认为，三角化的多项式组其零点集是能够完好确定的。这有两重意义：其，理 诊卜讲，多项式t ( u ，x 。，t ) ，i = l 2 ，确定了主变元x ，是“，“。，x 。的代数函数。 其二，数值计算上，当参数“= ( “，“：，u d ) 给定具体数值，利用单变元多项式的数值解法 第3 页 国防科学技术大学研究生院学位论文 可由z 求出x 1 的数值，将其代入瓦又可求得x ：的数值，依次下去，直到求出x r 的数值，这 样可求得三角化多项式组的数值解。所以我们的l q 标是：应用适当的三角化的多项式组， 准确地刻画给定的多项式组的零点集。 1 2 2余式公式 多项式问的求余运算式消元法中经常使用的基本运算。任给二多项式f 0 ) ，g ( x ) k x 可做g ( x ) g 。i 目的求余运算。若竹) 的主变元为t ，初式为l ( x 。，z ：，x 。) ，则一般有 + g ( 工) = ，l ( 工) 4 f ( x ) 十r ( x ) ，d e g ，( 只) j ，a ，对a ，经约化，即d e g 。( 一，) d e g ，( 4 ，) 。 余式公式是消元法中的基本公式。现给定一升列a s = a 。，a ) ，其中 a = a ，( 2 7 ，x ，x a i = 1 , 2 ，r ，考虑任一多项式p ( u ，z ，x2 ，x ，) 对升列爿s 求余。首先 p ( u ，x i ，x 2 ，工，) 对a ，( “，z l ，x2 ，x ，) 求余，得余式r h ( ，x 】，x 2 ，x ，) 。接着， r h ( “，z 2 r ，工，) 对a ( “，x 1 ，x 2 ，x ) 求得余式r ，一2 ( ， ，j 2 ”，工，) 。依此下去， 月 ( 2 ，x l ，工2 ，工，) 对爿i ( “，石l ，z 2 ，“) 求余，得余式r 川( “，工i ，x 2 ，x ，) ，k = ，- 一2 ，1 具体计 算过程可写为 ，；7 ( “，x 1 ，z ，一i ) + p ( u ，x ) = 五，( ，z ) 4 a ( “，x l ，x r ) + r ，一1 ( ，j ) 一：些塾兰鳖望耋里垒塑些垒垒坠：一 ，2 i ，( “，x l ，x ，2 ) + r , - 1 ( z f ，x ) = 五，( “，x ) + a ，一1 ( “，x i ，x r _ 1 ) 十r ，一2 ( “，x ) ， ，；2 ( “，x i ) + r 2 ( z f ，x ) = 2 ( “，x ) + a 2 ( ，x j ，x 2 ) + r l ( “，x ) ， ，? ( “) 4 r 1 ( “，x ) = 五l ( t 2 , x ) + aj ( “，x 1 ) 十r o ( “，x ) ， 其中z 一( z “：，。0 ) ，x = ( x ，x ：，x ，) 然后从最后一个式子倒推回去，可阱得到如下得公式 ，? ，i z ，j r p = ? 爿，十g 一，a ，一+ + q l 爿。+ r o ( 1 4 ) 其中，( “，x ；，x ：，x 。) 为多项式爿，( z ，x ，x 。x ，) 的初式，幂次s ，为非负整数， q ，( i f x l ，x 2 ，x ，) 是研“，x 】，x 2 ，x ， 中的多项式，i = l ，2 ， 公式( 1 4 ) 称为多项式户( z f ，x ；，x ：，_ ) 对升列a s 求余的余式公式。r 。( 玑t ) 称为多项 武p ( u ，x ) 对升到a s 的余式，记为r e m ( p a s ) ，g 女, r e m ( p ， 爿s ) ) 余式r o ( 1 f ，曲一般仍是 k u ， 中的多项式，满足 d e g 。( 尺o ) d e g ，( 爿，) ，i = l 2 ，r ( 1 5 ) 从余式公式可以看出，把余式r ( x ) 添加到多项式组 p ( x ) ，a 。( x ) ，爿：( x ) ，爿，( x ) 中得到 的多项式组 尸( z ) ，a ，( x ) ，a ：( x ) ，爿，( x ) ，r ( ) ) 其零点集没有变化， 即 z e r o ( p ，a ，a ) = z e r o ( p ，a ，a ，尺) 。从余式公式还可以看出，如果可以判定各初式都f i 能为零，则在条件r o ，j ，0 之下，有下武成立 z e r o ( p ，a ，a ，) 2 z e r o ( a ，a ，r j ) 即在备初式j o ，j ，0 _ i 为零的情况下，可在多项式组中以r 替换f ，而保持零点小变。 1 2 3多项式组的特征列 特征列是吴消元法中最重要的概念。特征歹0 的具体计算就是消元的过程。特扯列的机 械化算法是吴消元法的主体。 给定多项式组p s = 只( 上) ，p 2 ( 工) ，只( ) ) ，其中p a x 。，x 2 ”，。) s k x 。，如，一。 ，i = l ，2 ，m p s 中的多项式可依其主变元进行分类，记为类( x ，)c l ，。约定常数的类为零。显然，h 要多项式组尸- ，一经给定，这些类的个数有限。并且，每一类中包括的多项式的个数有限。 多项式组的基列。对给定的多项式组p s ，其中的多项式按其主变元分类后，在每 类中( x ，) 选取一个x ，的幂次最低的多项式b ，( 一，x ：，x i ) ，则多项式组b 5 = b ，b ，c l ， 是三角化的。如果b s 是一升列，即多项式b ，之间已经约化，则称b s 为多项式组尸s 的一 个基列，有时称为p s 的极小升列。 基列的选取可如下进行。在诸类( x ，) 中，变元的下标的大小可以排一个序，c l 。，c l ” c l i ，c l ，c l k ，其中i 。 i 2 0 ，z 0 ，订 0 ，6 0 ，c 0 ，a + b c ，订+ c 6 b + c 0 口，y 丌，0 卢，卢+ ， 。 ( 22 ) ，o = p 十g + ，一p q t 1 0 ( 点p ，a ，b ，c 不共而) 为了简化方程系统，令x = x z ，】，= y z ，1 4 占l = 屁，i b c l = 现，i a c l ；_ z 由于 z = | p c i 0 ，我们得到下面的方程系统： y + l 一炉一口v = 0 x 2 + 1 一x q b v = 0 ( 2 3 ) z 2 + y2 一x y r v = 0 第7 页 。 ：= 娑垒兰望圣兰些彗些些垒鳖坠一 由于i r l o ，那么z 能够唯一地由z = i a b i 石决定。从( 2 - 3 ) 中约去v 可得 加= ( 1 - a ) y 2 2 一怕r x y + l _ o ( e s l 【p2 = ( 1 一b ) x 2 砂2 一私+ b r x y + 1 = 0 上式与式( 21 ) 有相同数目的解。现在p 3 p 问题被化为寻找这两个二次方程的物理解。 2 , 2p 3 p 方程系统的零点集结构 w u r i t t 零点分解方法是解代数方程组的一般方法。它可以以卜面三角化的形式来表示 多项式组的零点集 z ( z ，1 ) = o ， ( “，x l ，z 2 ) = o ，兀( “，x ，x p ) = 0 其中“表示一个参数集合，x 表示有待确定的变元。对于一个多项式组p s 和一个多项式i z e r o ( p s ，) = z e r o ( p s ) 一z e r o ( ) 。 对于上节的问题的条f l 一，我们考虑z e r o ( e s i o ) ，利用w u - r i t t 零点分解方法对其进行 分解，可以得到1 0 个组成部分： z e r o ( e s l o ) = u c ( d e ) 其中c i = z e r o ( t s ，t ) ，i = l ，9 ，c j 。= z e r o ( t s , 。五。) u z e r o ( t s ，l 正。) ，三角化多项式组t s ，和 多项式r 的值见附录a 在这卜个组成部分里边，z e r o ( t s t , ) 被认为是p 3 p 方程组的土要成分，它具有如下 7 髟式： j f = o + o i x 3 + 0 2 x 2 + 0 3 x + a 4 一( t s ，) l g = b o y b l 1 其中系数qb ，见附录a 。很多文献中都得到过这种形式的结果。所有其他的组成部分可以 认为是一些蜕化情形。因为这些情形卑边，参数d ，b ，p ，q ，r 必须满足一定的代数关系。也 就是说这是些特殊情形。 与主要成分相比，蜕化情形发生概率要小的多，但是由于下而的原因，它们仍然十分 重要。事实上，当控制点a ，b ，c 来自诸如建筑物这类人造结构时，退化条件( 比如 d + b 一1 = 0 ( t s 。巾) 意味着z a c b 是直角) 被满足的情形就会经常发生。一般情况下，蜕化 情形( 如t s ：) 可能比较复杂，没有明确的几何意义，因此很难判断它什么时候发牛。 下表给出了符个组成部分所能取得最多解的数e j 。 lc ，= l234 567891 0 i 解的数目 4322 11l243 国防科学技术大学研究生院学位论文 由于c ，和c ，互不相容，所以对于给定的一组参数p ，q ，r ，d ，b z e r o ( p s l ) = z e r o ( t s , 丁 ) 如果k 满足1sk59 且瓦( p ，q ，r ，a ，b ) 0 ，或者 z e r o ( p s i o ) = z e r o ( t s l o 五o ) u z e r o ( t s l l r , 1 ) 如果五。( p ，g ，日，6 ) = 正，( p ，q ，- a ，b ) 0 。由于弼，中多项式的次数小于等于4 ，从而p 3 p 问题被化为三角形式的方程组的求解问题，也就是转化为次数小于等于4 的一元方程的求 解。 基于上面的分解，从而可以得到下面的结论。 1 由于每个三角型的解集合能够很好的确定，所以这个分解给出了p 3 p 问题的全 部解析解集合。 2 从表i 及其以下的分析很容易看出在实条t ：( 2 2 ) t ，原方程组最多有四组物理 解。这个结果以前的文献中已经给出。 2 3 1概述 2 3 p 3 p 方程组的解的完全分类 刺于多项式，( x ) 和g ( ) ，令炭示，( ) 实根的数目，矿，( g o ) 表示满足g 0 的实 根的数目。如果厂( x ) 有n 个文根，那么令掣“表示满足g on 使，( x ) 有j 个实根的条件。 下面的引理将在本节中用到。 引理2 1 ( d e s c a n e s 符号法则m “1 ) 若实系数方程式= ：。q = o ，( q 吼o ) 的正 根的数目是，而v 是系数序列 吼，d 。 的符号变号数，则v ，且v 一是一个偶数。 引理2 2 ”4 1 设，( x ) ，g ( j ) 是两多项式，f 的次数为”。令 r ( r ) = r e s u l t a n t ( f ，g 一7 1 ，x ) = c 丌( g ( ) 一7 _ ) = l 这里，i = l 一一? 是( ，) = o 的根。如果_ 厂( ) = 0 的所有根都是实根，那么v f ( g o ) ：一( r o ) 。 假设：( z ) ，g ，( z ，y ) 是t s 中的前两个多项式。 在组成部分巧，i = 5 , 6 ，7 ，1 0 中，z ( ) 和g ，( x ，y ) 分别关于z 和y 线性的。在这些情形下， 每个组成部分可能只有唯一的正解，而且很容易给出这些解存在的条件。 在组成部分嬲。，f 3 ，4 ，8 ，9 ，1 1 中，( z ) 和虽( y ) 分别关于。和，要么是线性的，要么 是二次的。本文将在下面的( 2 ，3 2 ) 节中讨论。 在组成部分t s ：中，z ( x ) 是三次方程，g ：( x ，) 关于y 足线性的。本文将在下面的 ( 23 3 ) 袖中时论。 9第! r 在组成部分界，中，( x ) 是一个四次方程，g l ( x ，y ) 关于y 是线性的。下面将在( 2 3 4 ) 关于四次的情形。 2 3 2二次情形 二次情形可能有三种形式：( 1 ) ，( j ) 是二次的，g l ( x ，y ) 关于y 是线性的；( 2 ) ( x ) 是线性的，g l ( j ，y ) 关于y 是二次的；( 3 ) ，( ) 和g i ( x ，y ) 分别关于x 和j ，都是二次的a 所 有这些情形都可以用相似的方法处理。下面以t s 。为例进行处理。方程如下： j = ( d + b - 1 ) x 2 + ( q q a ) x 一1 + d b = 0 9 9 = ( n + b 一1 ) _ y2 一l d 十q a x + 6 = 0 l p = 0 ，r = 0 ，x 0 ，y 0 ，口+ b 一1 0 卜而方程组正解的数目于如下方程组干目l 司： i i ，；= ( 口+ b 一1 ) x2 + ( g q a ) x 一1 + n b = 0 g = ( o + b 1 ) ( 1 + o q a x b ) 0 l p = 0 ，= 0 ，d + b 一1 0 ，工 0 ( 2 4 ) ( 2 5 ) 首先假设结式r e s u l t a n t ( f 9 ，g ，) 0 ，r e s u l t a n t ( f q ，x ，j ) = a b 一1 0 ，并且 r e s u t t a n t ( g ，x ，x ) = ( a + b - 1 ) 扣- b + 1 ) o 令 l ( 7 ) = r e s u l t a n t ( f 。，g 一7 1 ，上) = l o7 1 2 + 1 l7 1 + 1 l2 ， 2 ( r ) = r e s u l t a n t ( f 9 ，姆一丁，x ) = l j 2 0 t 2 + 2 i7 1 + 1 2 通过计算可以得到( ，d i f f ( f q ，x ) ) 的s y l v e s t e r - h a b i c h t 序列1 1 4 1 ，它们分别j ； j d ，d 。d l3 表 示。因此，当且仅当d ， 0 时 有两个实根，当且仅当d l ，= 0 时 有一个实根。由于 r e s u l t a n t ：l _ ，g ，的0 , r e s u l t a n t ( 矗，x ，砷= “一b l o 和r e s u l t a n t ( g ，x ) = ( a + b 1 ) ( 盘一b + 1 ) o 从而卜 列式子成立： _ ，= ( x o ) + ( x o ) ； 乡“! 2 o ，g 0 ) + ( j o ) ； 巧。( g o ) 2 巧。( x o ，g o ) + f 【x o ) = 音( ( x 0 ) + ( g o ) + ( x g o ) 一) ( 2 7 ) 根据引理2 1 和引理2 2 ，可以得到下面的结果： o o ) = ( x ) 的系数序列的符号的变号数， y ( g 0 ) = ，( t ) 的系数序列的符号的变号数， 吒，( x g 0 ) = ：( ，) 的系数序列的符号的变号数。 ：一= 垦些坠望垒婆兰垒型垄兰竺鳖坠一 如果r e s u l t a n t ( f q ，g ，x ) = 0 ，那么( 2 5 ) 式变为 f = 一a q ( a + b 一1 ) x q 2 十q 2 d 2 2 b 一日2 + 1 + b 20 ， g 。( 十6 1 ) ( 1 + 。一g “一6 ) o ，( 28 ) p = 0 ，r = 0 ， l + b l o ，x 0 关于上面的方程组，容易看出它可能有一组正解，并且存在一组正解的条件很容易得到。 对于结式r e s u l t a m ( 工，x ，z ) = 口一b 一1 = 0 和结式r e s u i t a n t ( g ，z ，x ) = ( a + b - 1 ) ( a - b + 1 ) = 0 ，可以使 用与上面相似的方法处理。 定理2 1 1 下面是判定零点集z e r o ( t s 9 瓦) 中满足条件x 0 ，g 0 的物理解数科的 判定条件： 1 当且仅当下面任一条件成立时，方程组( 2 4 ) 有2 组物理解 1 1 ) p = ，= 0 ，a + b l o ，q 0 ，d l3 0 ，a i o ，2 0 ，j o ，a 1 o ，2 0 2当r 仅当下面任一条件成立时，方程组( 2 4 ) 有1 组物理解 21 ) p = r = 0 ，口= 1 ，q 十b 一2 0 ，q 2 “ 0 ，d i3 = 0 ，l o ，! = 0 ，a l 0 ，订一b 一1 0 ，d l3 o ，a l 0 ，a3 0 21 0 ) p = ，= 0 ，