第2章 二维运动估计

二维位姿估计的定义二维位姿估计是指通过使用传感器数据和算法来推断或估计目标物体在二维平面上的位置和姿态。

在机器人技术、计算机视觉和自动驾驶等领域，二维位姿估计起着至关重要的作用。

它为机器人和计算机系统提供了实时感知和定位的能力，从而使它们能够快速准确地与周围环境进行交互和导航。

位姿估计主要分为两个方面：位置估计和姿态估计。

位置估计是指确定目标物体在平面上的位置坐标，通常使用二维坐标系表示。

姿态估计是指确定目标物体的旋转方向或朝向，常用欧拉角或四元数表示。

通过综合位置和姿态信息，能够得到目标物体的完整位姿。

在二维位姿估计中，常用的传感器包括摄像头、激光雷达、惯性测量单元（IMU）等。

摄像头可以通过图像处理技术来提取目标物体在图像中的特征点或者轮廓线，进而计算出其位置和姿态。

激光雷达可以通过发射激光束并测量其反射时间来获取目标物体的距离信息，从而实现三角定位或者点云匹配来估计位姿。

IMU则可以通过测量物体的加速度和角速度来推断其位置和姿态变化。

在位姿估计的算法中，常用的方法有：1. 特征点匹配方法：通过提取图像中的特征点，并通过计算特征点间的相对位置关系来估计位姿。

常用的特征点描述算法包括SIFT、ORB、SURF等。

2. 预测-校正方法：通过先验模型对目标物体的位置和姿态进行预测，然后根据实际观测数据进行校正。

预测模型可以基于上一时刻的位姿信息和运动模型，校正可以使用卡尔曼滤波、扩展卡尔曼滤波等方法。

3. 点云匹配方法：通过将激光雷达获取的点云数据与地图或者模型进行匹配，来估计位姿。

常用的点云匹配算法有ICP（Iterative Closest Point）算法和NDT（Normal Distributions Transform）算法等。

4. 深度学习方法：近年来，随着深度学习的发展，一些基于神经网络的方法也被应用到位姿估计中。

这些方法通过训练网络来学习从传感器数据到位姿的映射关系。

二维位姿估计在各个领域都有广泛的应用。

二维动量守恒公式好嘞，以下是为您生成的关于二维动量守恒公式的文章：在咱们学习物理的这个奇妙旅程中，二维动量守恒公式就像是一把神奇的钥匙，能帮咱们打开好多知识的大门。

先来说说啥是二维动量守恒公式。

其实啊，它就是描述在一个平面内，物体之间相互作用时动量总和保持不变的规律。

比如说，咱们想象一下打台球的场景。

台球桌上，球A 以一定的速度和方向撞击球B，在这个碰撞过程中，如果没有外力的干扰，那球 A 和球 B 的动量之和在碰撞前后是不会改变的。

我记得有一次在物理实验室里，老师让我们做一个有关二维动量守恒的实验。

那是一组简单但又很能说明问题的装置。

一个小滑块在光滑的平面上滑动，另一个滑块从侧面撞过来。

我们得通过测量它们碰撞前后的速度和质量，来验证二维动量守恒公式是不是真的那么灵。

当时我特别紧张，手都有点抖，就怕自己测的数据不准。

我小心翼翼地调整着测量工具，眼睛紧紧盯着滑块的运动，心里默默念叨着：“可千万别出错啊！”当我把最后一组数据记录下来，开始计算的时候，心都提到嗓子眼了。

结果发现，计算出来的数据和二维动量守恒公式的预测几乎一模一样，那种兴奋和成就感，真的没法形容。

那二维动量守恒公式到底怎么用呢？假设一个物体在 x 方向上的速度是 vx，质量是 m，在 y 方向上的速度是 vy，那它在 x 方向上的动量就是 m*vx，y 方向上的动量就是 m*vy。

如果有两个物体相互作用，那在这两个方向上，它们的动量之和在作用前后都是相等的。

比如说，一个小球以 3m/s 的速度水平向右运动，质量是 2kg，同时以 2m/s 的速度竖直向上运动。

那它在水平方向上的动量就是 2×3 = 6 kg·m/s，竖直方向上的动量就是 2×2 = 4 kg·m/s。

在实际生活中，二维动量守恒公式也有好多用处呢。

像火箭发射，燃料燃烧产生的气体向后喷射，给火箭一个向前的反作用力，这就可以用二维动量守恒来解释。

J.Korean Math.Soc.48(2011),No.5,pp.985–999/10.4134/JKMS.2011.48.5.985A FILLED FUNCTION METHOD FOR BOX CONSTRAINEDNONLINEAR INTEGER PROGRAMMINGYoujiang Lin and Yongjian YangAbstract.A newfilled function method is presented in this paper tosolve box-constrained nonlinear integer programming problems.It isshown that for a given non-global local minimizer,a better local min-imizer can be obtained by local search starting from an improved initialpoint which is obtained by locally solving a box-constrained integer pro-gramming problem.Several illustrative numerical examples are reportedto show the efficiency of the present method.1.IntroductionIn[13],Zhu showed that over unbounded domain,the integer programming is undecidable;i.e.,there cannot be any algorithm for the problem.So we consider the following box-constrained discrete global optimization problem: (1.1)min{f(x):x∈X⊂Z n},where f:Z n→R,and Z n is the set of integer points in R n,and X is box;i.e., X={x∈Z n:a≤x≤b,a,b∈Z n}.Like the continuous global optimization problems,the existence of multiple local minima of a general nonconvex objective function makes discrete global optimization a great challenge.For continuous global optimization problems, many deterministic methods(see[1],[7],[8],[10])have been proposed to search for a globally optimal solution of a function of several variables.Thefilled function algorithm(see[2],[4])is an effective and practical method among determinate algorithms.The primaryfilled function was proposed by Ge in paper[2].The definition of thefilled function is as follows:Definition1.1.Assume that x∗1is a current minimizer of f(x).A continuous function P(x)is said to be afilled function of f(x)at x∗1if it satisfies the following properties:Received March8,2010;Revised July26,2010.2010Mathematics Subject Classification.52A10,52A40.Key words and phrases.global optimization,filled function method,nonlinear integer programming,local minimizer,global minimizer.The authors would like to acknowledge the support from the National Natural Science Foundation of China(10971128),Shanghai Leading Academic Discipline Project(S30104).c⃝2011The Korean Mathematical Society985986YOUJIANG LIN AND YONGJIAN YANG(1)x∗1is a maximizer of P(x)and the whole basin B∗1of f(x)at x∗1becomesa part of a hill of P(x);(2)P(x)has no minimizers or saddle points in any higher basin of f(x)than B∗1;(3)If f(x)has a lower basin than B∗1,then there is a point x′in such abasin that minimizes P(x)on the line through x and x∗1.For the definitions of basin and hill,refer to Ge(1990),paper[2].Thefilled function given at x∗1in the paper[2]has the following form:(1.2)P(x,x∗1,r,ρ)=1r+f(x)exp(−∥x−x∗1∥2ρ2),where the parameters r andρneed to be chosen appropriately.The main idea of thefilled function method is to construct an auxiliary func-tion calledfilled function via the current local minimizer of the original opti-mization problem,with the property that the current local minimizer is a local maximizer of the constructedfilled function and a better initial point of the primal optimization problem can be obtained by minimizing the constructed filled function locally.By the same idea as that of solving continuous global optimization problems,We try to solve discrete global optimization problem (1.1).In[3],Ge adapted thefilled function method by Ge[2]for continuous global optimization to the discrete case.However,thefilled function algorithm de-scribed in the paper[2]still has some unexpected features:(i)The efficiency of thefilled function algorithm strongly depend on two parameters r and q.They are not so easy to be adjusted to make them satisfy the needed conditions;(ii)Thefilled function includes exponential terms.If the value of1/ρbe-comes large as iterations proceed,as required to preserve thefilling property, numerical illness may result in failure of computation;(iii)The termination criteria is not good because it requires a large amount of computation before a global minimizer has been found.In this paper,we provide a new definition of the discretefilled function,and a discretefilled function satisfying the definition is presented.An algorithm is developed from the newfilled function.The newfilled function algorithm overcomes the disadvantages mentioned above in a certain extent.Specifically, it has the following several advantages:(i)The newfilled function includes neither exponential terms nor logarithmic terms.Elementary functionϕ(t)=arctan t is used in thefilled function,which possesses many good properties and is efficient in numerical implementations.(ii)The parameters q and r in the newfilled function are easier to be ap-propriately chosen than those of the originalfilled function(1.2).(iii)The new algorithm has a simple termination criteria and the compu-tational results show that this algorithm is more efficient than the original algorithm.A FILLED FUNCTION METHOD987The rest of this paper is organized as follows.In Section2,wefirst re-call some definitions in discrete analysis and discrete optimization.In Section 3,a definition of discretefilled function is given,a discretefilled function is presented,and we investigate its properties.An algorithm is developed and numerical experiments are presented in Section4.Finally,some conclusions are drawn in Section5.2.PreliminaryFirst,we recall some definitions in discrete analysis and discrete optimization (see[11],[12]).Definition2.1.A sequence{x i}u i=−1is called a discrete path in X between two distinct point x∗and x∗∗in X if x−1=x∗,x u=x∗∗,x i∈X for all i; x i=x j for i=j;and∥x0−x∗∥=∥x i+1−x i∥=∥x∗∗−x u−1∥=1for all i.If such a discrete path exists,then x∗and x∗∗are said to be pathwise connected in X.Furthermore,if every two distinct points in X are pathwise connected in X,then X is called a pathwise connected set.Definition2.2.The set of all axial directions in Z n is defined by D={±e i: i=1,2,...,n},where e i is the i th unit vector;The set of all feasible directions at x∈X is defined by D x={d∈D:x+d∈X},where D is the set of axial directions.Definition2.3.For any x∈Z n,the discrete neighborhood of x is defined by N(x)={x,x±e i:i=1,2,...,n};The discrete interior of X is defined by int X={x∈X:N(x)⊆X}.While,the discrete boundary of X is denoted by∂X=X/int X.Definition2.4.A point x∗∈X is called a discrete local minimizer of f over X if f(x∗)≤f(x)for all x∈X∩N(x∗).If,in addition,f(x∗)<f(x)for all x∈X∩N(x∗)/{x∗},then x∗is called a strict discrete local minimizer of over X;A point x∗∈X is called a discrete global minimizer of f over X if f(x∗)≤f(x)for all x∈X.If,in addition,f(x∗)<f(x)for all x∈X,then x∗is called a strict discrete global minimizer of f over X.Definition2.5.For any x∈X,d∈D is said to be a discrete descent direction of f at x over X if x+d∈X and f(x+d)<f(x);beside,d∗∈D is called a discrete steepest descent direction of f at x over X if f(x+d∗)≤f(x+d)for all d∈D∗,where D∗is the set of all descent direction of f at x over X. Algorithm2.6.(Discrete steepest descent method).1.Start from the initial point x∈X.2.If x is a local minimizer of f over X,then stop.Otherwise,a discrete steepest descent direction d∗of f at x over X can be found.3.Let x:=x+λd∗,whereλ∈Z+is the step length such that f has maximum reduction in direction d∗,and go to Step2.988YOUJIANG LIN AND YONGJIAN YANGAlgorithm 2.7.(Modified discrete descent method).1.Start from the initial point x ∈X .2.If x is a local minimizer of f over X ,then stop.Otherwise,letd ∗=argmin {f (x +d i ):d i ∈D x ,f (x +d i )<f (x )},where D x denotes the set of feasible directions at x .3.Let x :=x +d ∗,and go to Step 2.Obviously,by Algorithms 2.6and 2.7,we can only find a discrete local minimizer.Finally,for the discrete global optimization problem (1.1),we make the following assumptions in this paper:Assumption 2.8.X ⊆Z n is a bounded set which contains more than one point.This implies that there exists a constant K >0such that1≤K =max x,y ∈X∥x −y ∥≤∞,where ∥·∥is the usual Euclidean norm.Assumption 2.9.f :∪x ∈X N (x )→R satisfies the following Lipschiz condi-tion for every x,y ∈∪x ∈X N (x ):|f (x )−f (y )|≤L ∥x −y ∥,where 0<L <∞is a constant,N (x )is the discrete neighborhood of x .3.A filled function and its propertiesIn this section,we propose a filled function of f (x )at a current local mini-mizer and discuss its properties.LetS 1={x :|f (x )≥f (x ∗1),x ∈X \{x ∗1}},S 2={x |f (x )<f (x ∗1),x ∈X }.Definition 3.1.P (x,x ∗1)is called a discrete filled function of f (x )at a discrete local minimizer x ∗1if P (x,x ∗1)has the following properties:(1)x ∗1is a strict discrete local maximizer of P (x,x ∗1)on X ;(2)P (x,x ∗1)has no discrete local minimizers in the region S 1;(3)If x ∗1is not a discrete global minimizer of f (x ),then P (x,x ∗1)does havea discrete minimizer in the region S 2.Now,we give a discrete filled function for problem (1.1)at a local minimizer x ∗1as follows:F (x,x ∗1,q,r )=1q +∥x −x ∗1∥ϕq (max {f (x )−f (x ∗1)+r,0}),(3.1)whereϕq (t )={arctan (−qt )+π2,if t =0,0,if t =0.(3.2)r=0.2q>0and r satisfies0<r<maxx∗,x∗1∈L(P)f(x∗)<f(x∗1)(f(x∗1)−f(x∗))where L(P)stand for the set of discrete local minimizers of f(x).A simple example is given in Figure1.Next we will show that the function F(x,x∗1,q,r)is a discretefilled function satisfying Definition3.1under certain conditions on the parameters q and r. Theorem3.2.Suppose that X holds Assumption2.8.Further suppose that x∗1 is a discrete local minimizer of f(x).For any r>0,when q>0is satisfactorily small,x∗1is a strict discrete local maximizer of F(x,x∗1,q,r).Proof.Since x∗1is a discrete local minimizer of f(x)for any x∈N(x∗1)∩X, f(x)≥f(x∗1)and∥x−x∗1∥=1.Hence,we haveF(x,x∗1,q,r)=1q+1(arctan(−qf(x)−f(x∗1)+r)+π2)andF(x∗1,x∗1,q,r)=1q(arctan(−qr)+π2),990YOUJIANG LIN AND YONGJIAN YANGwhen x ≥y ,arctan(x )−arctan(y )≤x −y ;let q <r ,we haveF (x,x ∗1,q,r )−F (x ∗1,x ∗1,q,r )=1q +1(arctan(−q f (x )−f (x ∗1)+r )+π2)−1q (arctan(−q r )+π2)=1q +1arctan(−q f (x )−f (x ∗1)+r )−1q arctan(−q r )+−1q (q +1)π2=1q +1×(arctan(q r )−arctan(q f (x )−f (x ∗1)+r ))+1q ×(q +1)(arctan(q r )−π2)<1q ×(q +1)×(q ×(q r −q f (x )−f (x ∗1)+r )+(arctan 1−π2))=1q ×(q +1)×(q 2×f (x )−f (x ∗1)r ×(f (x )−f (x ∗1)+r )−π4)≤1q ×(q +1)×(q 2×L ∥x −x ∗1∥r 2−π4)=1q ×(q +1)×(q 2×L r 2−π4)≤1q ×(q +1)×(q ×L r −π4).Therefore,when 0<q <min {r,πr 4L },we have F (x,x ∗1,q,r )−F (x ∗1,x ∗1,q,r )<0for any x ∈N (x ∗1)∩X ,x ∗1is a strict discrete local maximizer of F (x,x ∗1,q,r ).□Lemma 3.3.For every x ,x ∗∈X ,if there exits i ∈{1,2,...,n }such that x ±e i ∈X ,then there exists d ∈D such that∥x +d −x ∗∥>∥x −x ∗∥.Proof.If there is an i ∈{1,2,...,n }such that x ±e i ∈X ,then either ∥x +e i −x ∗∥>∥x −x ∗∥or ∥x −e i −x ∗∥>∥x −x ∗∥,therefore we let d =e i or d =−e i ,this completes the proof.□Theorem 3.4.Suppose that Assumptions 2.8-2.9are satisfied.If x ∗1is a discrete local minimizer of f (x ),then the function F (x,x ∗1,q,r )has no discrete local minimizers in the region S 1={x |f (x )≥f (x ∗1),x ∈X/{x ∗1}}when r >0and q >0are satisfactorily small.Proof.Let ˜X =∪x ∈X N (x ),obviously,˜X holds Assumptions 2.8-2.9,and wehave S 1⊆X ⊆int ˜X.For every x ∈S 1,by Lemma 3.3,there must exists a direction d ∈D such that x +d ∈X and∥x +d −x ∗1∥>∥x −x ∗1∥.A FILLED FUNCTION METHOD991 Consider the following two cases:(1)f(x+d)≥f(x∗1):Since f(x+d)≥f(x∗1),we haveF(x+d,x∗1,q,r)−F(x,x∗1,q,r)=1q+∥x+d−x∗1∥(arctan(−qf(x+d)−f(x∗1)+r)+π2)−1q+∥x−x∗1∥(arctan(−qf(x)−f(x∗1)+r)+π2)=1q+∥x+d−x∗1∥arctan(−qf(x+d)−f(x∗1)+r)−1q+∥x−x∗1∥arctan(−qf(x)−f(x∗1)+r)+∥x−x∗1∥−∥x+d−x∗1∥(q+∥x+d−x∗1∥)(q+∥x−x∗1∥)π2=1q+∥x+d−x∗1∥×(arctan(q∗1)−arctan(q∗1))+∥x+d−x∗1∥−∥x−x∗1∥(q+∥x+d−x∗1∥)(q+∥x−x∗1∥)(arctan(qf(x)−f(x∗1)+r)−π2).If f(x)>f(x+d),thenarctan(qf(x)−f(x∗1)+r)−arctan(qf(x+d)−f(x∗1)+r)<0therefore when q<r,we have arctan(qf(x)−f(x∗1)+r)−π2<0,henceF(x+d,x∗1,q,r)−F(x,x∗1,q,r)<0.If f(x)≤f(x+d)for any x,y∈R,when x≤y,we have arctan y−arctan x≤y−x,let q<r and q<1,we haveF(x+d,x∗1,q,r)−F(x,x∗1,q,r)≤1q+∥x+d−x∗1∥×(qf(x)−f(x∗1)+r−qf(x+d)−f(x∗1)+r)+∥x+d−x∗1∥−∥x−x∗1∥(q+∥x+d−x∗1∥)(q+∥x−x∗1∥)(arctan1−π2)≤qq+∥x+d−x∗1∥×(f(x+d)−f(x)(f(x)−f(x∗1)+r)(f(x+d)−f(x∗1)+r))+∥x+d−x∗1∥−∥x−x∗1∥(q+∥x+d−x∗1∥)(2∥x−x∗1∥)(arctan1−π2)≤1(q+∥x+d−x∗1∥)(2∥x−x∗1∥)992YOUJIANG LIN AND YONGJIAN YANG×(2qL∥d∥∥x−x∗1∥r2−π4(∥x+d−x∗1∥−∥x−x∗1∥)).Hence,for any given x∈S1and d,when q is satisfactorily small thatq<πr2(∥x+d−x∗1∥−∥x−x∗1∥)8L∥x−x∗1∥,we haveF(x+d,x∗1,q,r)<F(x,x∗1,q,r).(2)f(x+d)<f(x∗1):In this case,it is clear that f(x+d)<f(x),sincefunction f(t)=arctan(−qt )+π2is increasing about t,hence,we haveF(x+d,x∗1,q,r)<F(x,x∗1,q,r).The above two cases imply that any x∈S1is not the discrete local minimizer of F(x,x∗1,q,r)when q is satisfactorily small.□Theorem3.5.If x∗1is not a discrete global minimizer of f(x)in X,then there exists a discrete minimizer¯x1∗of F(x,x∗1,q,r)in the region S2={x|f(x)< f(x∗1),x∈X}.Proof.Since x∗1is not a discrete global minimizer and F(x,x∗1,q,r)≥0,there exist a point¯x1∗∈S2and r such that f(¯x1∗)<f(x∗1)−r.Hence,F(¯x1∗,x∗1,q,r) =0,it implies that¯x∗1∈S2is a discrete minimizer of F(x,x∗1,q,r).□Theorem3.2,Theorem3.4,and Theorem3.5show that the function F(x, x∗1,q,r)at point x∗1is a discretefilled function satisfying Definition3.1with satisfactorily small q and r.The following theorems further show that the proposedfilled function has some good properties which classical functions have.Theorem3.6.Suppose that Assumption2.9is satisfied.If x1,x2∈X and satisfy the following conditions:(1)f(x1)≥f(x∗1)and f(x2)≥f(x∗1),(2)∥x2−x∗1∥>∥x1−x∗1∥.Then,when r>0and q>0are satisfactorily small,F(x2,x∗1,q,r)<F(x1,x∗1,q,r).Proof.Consider the following two cases:(1)If f(x∗1)≤f(x2)≤f(x1),then it is obvious that the result follows.(2)If f(x∗1)≤f(x1)<f(x2),the result also holds(see the proof process in Theorem3.4).□Theorem3.7.If x1,x2∈X and satisfy the following conditions:(1)∥x2−x∗∥>∥x1−x∗∥,(2)f(x1)≥f(x∗1)>f(x2),and f(x2)−f(x∗1)+r>0.Then,we have F(x2,x∗1,r,q)<F(x1,x∗1,r,q).A FILLED FUNCTION METHOD993 Proof.By Conditions1and2,we have1q+∥x2−x∗1∥<1q+∥x1−x∗1∥and0<f(x2)−f(x∗1)+r<f(x1)−f(x∗1)+r.Hence F(x2,x∗1,r,q)<F(x1,x∗1,r,q).□Now we make some remarks.Firstly,in the phase of minimizing the new discretefilled function,Theorems3.6and3.7guarantee that the current dis-crete local minimizer x∗1of the objective function is escaped and the minimum of the new discretefilled function will be always achieved at a point where the objective function value is less than the current discrete minimum.Secondly, the parameters q and r are easier to be appropriately chosen.In the next section,a new discretefilled function algorithm is given.4.Algorithm and numerical resultsBased on the theoretical results in the previous section,a global optimization algorithm over X is proposed as follows:AlgorithmInitialization:(1)Choose any x0∈X as an initial point.(2)Letε=10−5and q0=0.01.(3)Let D0={±e i:i=1,2,...,n}.Main Program:(1)Starting from initial point x0,minimize f(x)(x∈X)by the discretesteepest descent method(see Algorithm2.1),we can obtain the discretelocal minimizer x∗1.Let r=1,q=q0and D=D0.(2)Construct the discretefilled function:F(x,x∗1,q,r)=1q+∥x−x∗∥ϕq(max{f(x)−f(x∗1)+r,0}),whereϕq(t)={arctan(−qt)+π2,if t=0, 0,if t=0.(3)If r≤ε,then terminate the iteration,the x∗k is the global minimizer off(x),otherwise,the next step.(4)If D=∅,then goto(6),otherwise the next step.(5)If q<ε×10−2,then let r=r/10,q=q0/10and D=D0,goto(2);otherwise let q=q/10,goto(2).(6)Take a direction d∈D,and D←D/{d},turn to Inner Loop.994YOUJIANG LIN AND YONGJIAN YANGInner Loop:(1)k=0.(2)Let y k=x∗1+d.(3)Minimize F(x,x∗1,q,r),starting from the point y k,by implementing themodified discrete descent method(see Algorithm2.2).y k+1denotes thenext iterative point.(4)If y k+1/∈X,then return Main Program(4),otherwise next step.(5)If f(y k+1)≤f(x∗1),then let x0=y m+1and return Main program(1),otherwise let k=k+1and goto Inner Loop(3).In the following part,several test problems are given and results of the algorithm in solving these problems are reported.Through out the tests,we use the modified discrete descent method as shown in Algorithm2.7to perform local searches,in the initialization of the algorithm we let q=0.01and r=1. The algorithm in Fortran95is successfully used tofind the global minimizers of these test problems.The main iterative results are summarized in tables for each function.The symbols used are shown as follows:k:The iteration number infinding the k th local minimizer.x0 k or y0k:The k th initial point.f(x0k )or f(y0k):The function value of the k th initial point.x∗k or y∗k:The k th local minimizer.f(x∗k )or f(y∗k):The function value of the k th local minimizer.Problem4.1.min f(x)=100(x2−x21)2+(1−x1)2+90(x4−x23)2+(1−x3)2,+10.1[(x2−1)2+(x4−1)2]+19.8(x2−1)(x4−1), s.t.10≤x i≤10,i=1,2,3,4.This problem is a discrete counterpart of the problem38in[6].It is a box constrained nonlinear integer programming problem.It has214≈1.94×105 feasible points where41of them are discrete local minimizers but only one of those discrete local minimizers is the discrete global minimum solution:x∗global =(1,1,1,1)with f(x∗global)=0.Let x01=(9,6,5,6)and x01=(9,−9,−9,9),a summary of the computational results are displayed in Tables 1and2.Problem4.2.min f(x)=g(x)h(x),s.t.x i=0.001y i,−2000<y i<2000,i=1,2,where y i(i=1,2)is integer,andg(x)=1+(x1+x2+1)2(19−14x1+3x21−14x2+6x1x2+3x2),h(x)=30+(2x1−3x2)2(18−32x1+12x21+48x2−36x1x2+27x22).A FILLED FUNCTION METHOD995 Table1.Problem4.1initial point is(9,6,5,6)k x0k f(x0k)x∗kf(x∗k)1(9,6,5,6)596070.0(3,8,3,8)2158.0000 2(3,10,2,5)1887.5000(3,8,2,3)1007.5000 3(3,10,1,1)922.1000(3,8,0,−1)453.1000 4(2,5,0,−1)235.6000(2,4,0,0)43.6000 5(1,1,0,0)11.1000(1,1,1,1)0.0000 Table2.Problem4.1initial point is(9,−9,−9,9)k x0k f(x0k)x∗kf(x∗k)1(9,−9,−9,9)1276796.40(3,8,−3,8)2170.0000 2(3,10,−2,5)1895.5000(3,8,−2,3)1015.5000 3(3,10,−1,1)926.1000(3,8,0,−1)453.1000 4(2,5,0,−1)235.6000(2,4,0,0)43.6000 5(1,1,0,0)11.1000(1,1,1,1)0.0000Table3.Problem4.2k y0k f(y0k)y∗kf(y∗k)1(1000,1000)1876.000(1280,890)954.13822(2000,632)951.2482(1609,71)92.34253(1379,2000)19.4895(85,2000)−210795.62531(−1000,−1000)1890.000(0,−1000) 3.0000002(0,1740)−256.5294(85,2000)−210795.62531(2000,2000)35028.000(1280,890)954.13822(2000,632)951.2482(1609,71)92.34263(1379,2000)19.4895(85,2000)−210795.62531(−2000,−2000)20811.9999(0,−1000) 3.0000002(0,1740)−256.5294(85,2000)−210795.6253 This problem is a discrete counterpart of the Goldstein and Price’s function in[5].It is a box constrained nonlinear integer programming problem.It has 40012≈1.60×107feasible points.More precisely,it has207and2discrete local minimizers in the interior and the boundary of box−2.00≤x i≤2.00,i=1,2, respectively.Nevertheless,it has only one discrete global minimum solution:y∗global =(85,2000)with f(y∗global)=−210795.6253.We used four initial pointsin our experiment:(1000,1000),(−1000,−1000),(2000,2000),(−2000,−2000), a summary of the computational results are displayed in Table3.Problem4.3(Beale’s function).min f(x)=[1.5−x1(1−x2)]2+[2.25−x1(1−x22)]2+[2.625−x1(1−x32)]2,996YOUJIANG LIN AND YONGJIAN YANGTable4.Problem4.3k y0k f(y0k)y∗kf(y∗k)1(3000,5000)146039.2031(−3,9735) 6.06732(10000,963) 6.0183(3015,504)3.7589×10−5 1(−3000,−5000)150120.7031(11,−5964)9.02302(10000,788)8.9179(3015,504)3.7589×10−5 1(8000,8000)16992808.2031(−3,9735) 6.06732(10000,963) 6.0183(3015,504)3.7589×10−5 1(−8000,−8000)17121524.2031(5,−7842)8.67812(10000,790)8.6132(3015,504)3.7589×10−5Table5.Problem4.4k y0k f(y0k)y∗kf(y∗k)1(−5000,−5000,−5000,−5000)3650.0000(−116,12,55,−56)3.7213×10−4 2(−78,8,38,−38)7.9387×10−5(−79,8,38,−38)7.9045×10−5 3(11,−1,11,11)1.2798×10−6(10,−1,11,11)2.7985×10−7 4(0,0,3,3)2.1060×10−9(0,0,1,1)2.6000×10−11 1(5000,5000,5000,5000)3650.0000(116,−12,56,57)3.7859×10−4 2(78,−8,38,38)7.9387×10−5(79,−8,38,38)7.9045×10−5 3(−11,1,−11,−11)1.2798×10−6(−10,1,11,−11)2.7985×10−7 4(0,0,3,−3)2.1060×10−9(0,0,1,−1)2.6000×10−11Table6P N DN IN T I F N1450.236049532230.070732317673220.05216224364444278.245675801758525247.49104950368555021147.47298451600510024406.341276667658625242.6725336724326502249.264535436658610023087.764275437056s.t.x i=0.001y i,−104≤y i≤104,i=1,2,where y i(i=1,2)is integer.This problem is discrete counterpart if the problem203in[9].It is a box constrained nonlinear integer programming problem.It has200012≈4.00×108 feasible points and many discrete local minimizers,but it has only one discreteA FILLED FUNCTION METHOD 997Table parison of the resultsGe’s algorithm New algorithm PN DN IN TI F N RA IN TI F N RA 1.41073.667707461.22−4638.564466530.47−5321837.5366175644.73−311328.102295761.78−512657.0751126852.03−38375.807522360.38−435866.2673855076.12−418406.542453513.80−618659.5161008410.24−415315.345500551.67−62.21157.36723520.10−4648.0512303.15−613168.74265900.67−56123.0985675.03−71389.52763501.25−4631.9165850.72−63.263454.3553674598.07−412982.440134223.90−567098.6216532109.12−4101752.812179839.92−64.42012873.31053243183.19−3162577.1205453901.10−5205952.54630876415.00−416214.3423166343.00−65.253228750.21783421091.05−6181524.7083452972.13−7326532.0972*******.09−618352.761965312.20−7316098.73230678124.56−619213.450882064.12−76.25181105.5503680560.06−525428.650309874.31−818963.2712987675.01−525320.710756183.00−8182544.3268021142.10−523484.56289457.00−7183245.71123547700.38−525145.3542345528.29−8global minimum solution y ∗global =(3000,500)with f (y ∗global )=0.We used four initial points in our experiment:(3000,5000),(−3000,−5000),(8000,8000),(−8000,−8000),a summary of the computational results are displayed in Table 4.Problem 4.4(Powell’s singular function).min f (x )=(x 1+10x 2)2+5(x 3−x 4)2+(x 2−2x 3)4+10(x 1−x 4)4,s .t .x i =0.001y i ,−104≤y i ≤104,i =1,2,3,4,where y i (i =1,2,3,4)is integer.It is a box constrained nonlinear integer programming problem.It has 200014≈1.60×1017feasible points and many local minimizers,but it hasonly one global minimum solution:y ∗global =(0,0,0,0)with f (y ∗global )=0.We used two initial points in our experiment:(−5000,−5000,−5000,−5000),(5000,5000,5000,5000),a summary of the computational results are displayed in Table 5.Problem 4.5.min f (x )=(x 1−1)2+5(x n −1)2+n −1∑i =1(n −i )(x 2i −x i +1)2,s .t .−5≤y i ≤5,i =1,2,...,n.998YOUJIANG LIN AND YONGJIAN YANGThis problem is a generalization of the problem282in[9].It is a box con-strained nonlinear integer programming problem.It has11n feasible points andmany local minimizers,but it has only one global minimum solution:x∗global =(1,...,1)with f(x∗global )=0.For all problem with different size,we used fourinitial points in our experiment:(5,...,5),(−5,...,−5),(−5,...,−5,5,...,5), (5,...,5,−5,...,−5).For every experiment,the proposed algorithm succeeded in identifying the discrete global minimum.Let x01=(5,...,5),for n= 25,50,100,respectively,the summary of the computational results are dis-played in Table6.Problem4.6(Rosenbrock’s function).min f(x)=n−1∑i=1[100(x i+1−x2i)2+(1−x i)2],s.t.−5≤y i≤5,i=1,2,...,n.It is a box constrained/unconstrained nonlinear integer programming prob-lem.It has11n feasible points and many local minimizers,but it has onlyone global minimum solution:x∗global =(1,1,...,1)with f(x∗global)=0.Forall problems with different sizes,we used four initial points in our experiment: (5,...,5),(−5,...,−5),(−5,...,−5,5,...,5),(5,...,5,−5,...,−5).For ev-ery experiment,the proposed algorithm succeeded in identifying the discrete global minimum.Let x01=(5,...,5),for n=25,50,100,respectively,the summary of the computational results are displayed in Table6.In Table6,we give the experiment results for Problems4.1-4.6.In Table7, Problems4.1-4.6.with2to25variables are tested and the table shows that in most cases the newfilled function algorithm works better than Ge’sfilled function algorithm.The symbols used in Tables6-7are shown as follows: P N:The N th problem.DN:The dimension of objective function of a problem.IN:The number of iteration cycles.T I:The CPU time in seconds for the algorithm to stop.F N:The number of objective function evaluations for algorithm to stop.RA:The ratio of the number of function evaluations to the number of feasible points.5.ConclusionsThis paper gives a definition of thefilled function for the nonlinear integer programming problem,and presents a newfilled function.Afilled function algorithm based on this givenfilled function is designed.The implementation of the algorithm on several test problems is reported with satisfactory numerical results.A FILLED FUNCTION METHOD999 Acknowledgment.The authors are most grateful to the referee for his many excellent suggestions for improving the original manuscript.References[1] B.C.Cetin,J.Barhen,and J.W.Burdick,Terminal repeller unconstrained subenergytunneling(TRUST)for fast global optimization,J.Optim.Theory Appl.77(1993),no.1,97–126.[2]R.P.Ge,Afilled function method forfinding a global minimizer of a function of severalvariables,Math.Programming46(1990),no.2,(Ser.A),191–204.[3]R.P.Ge and C.B.Huang,A continuous approach to nonlinear integer programming,put.34(1989),no.1,part I,39–60.[4]R.P.Ge and Y.F.Qin,The globally convexizedfilled functions for global optimization,put.35(1990),no.2,part II,131–158.[5] A.A.Goldstein and J.F.Price,On descent from local minima,p.25(1971),569–574.[6]W.Hock and K.Schittkowski,Test Examples for Nonlinear Programming Codes,Springer,NewYork,1981.[7]R.Horst,P.M.Pardalos,and N.V.Thoai,Introduction to Global Optimization,seconded.,Kluwer Academic Publishers,Dordrecht,2000.[8] A.V.Levy and A.Montalvo,The tunneling algorithm for the global minimization offunctions,SIAM put.6(1985),no.1,15–29.[9]K.Schittkowski,More Test Examples for Nonlinear Programming Codes,Springer,NewYork,1987.[10]Y.Yao,Dynamic tunneling algorithm for global optimization,IEEE Trans.SystemsMan Cybernet.19(1989),no.5,1222–1230.[11]L.S.Zhang,F.Gao,and W.X.Zhu,Nonlinear integer programming and global opti-mization,put.Math.17(1999),no.2,179–190.[12]W.X.Zhu,An approximate algorithm for nonlinear integer programming,Appl.Math.Comput.93(1998),no.2-3,183–193.[13],Unsolvability of some optimization problems,put.174(2006),no.2,921–926.Youjiang LinDepartment of MathematicsShanghai UniversityShanghai200444,P.R.ChinaE-mail address:linyoujiang@Yongjian YangDepartment of MathematicsShanghai UniversityShanghai200444,P.R.ChinaE-mail address:yjyang@。

运动估计综述1.定义这里指基于块的运动估计，基本思想是将图像序列的每一帧分成许多互不重叠的块，并认为块内所有像素的位移量都相同，然后对每个宏块到参考帧某一给定特定搜索范围内根据一定的块匹配准则找出与当前块最相似的块，即匹配块，匹配块与当前块的相对位移即为运动矢量。

2.运动估计算法2.1全搜索每一点都要比较，需计算（2*d+1）*(2*d+1)次（d是搜索范围）。

对分辨率360x288，帧率30fps的视频，设d=21，每秒要计算1.09E10次，计算量太大，需要研究相应的快速算法。

2.2早期的快速算法（固定模式法）这些算法假设匹配误差随着离全局误差最小点的距离增加而单调增加。

一般从原点开始，采用固定的搜索模板和搜索策略得到最佳匹配块。

常见的有：三步法（TSS）、四步法（FSS）、菱形法（DS）、六边形法(HEXBS)等。

三步法（TSS）四步法（FSS ）菱形法（DS ）：六边形法（HEXBS ）：早期算法的不足：∙ 没有利用图像本身的相关信息，不能根据物体运动的剧烈程度自适应的改变搜索起点和搜索半径；∙ 以菱形法为例，对背景图像，也要经历从大模板到小模板的转换过程，至少需要13个搜索点，搜索速度还有待改进；∙ 对于运动剧烈的图像，从原点开始搜索时，要经过多次搜索才能找到匹配点，搜索点过多，且容易陷入局部最优点。

2.3近年来提出的新算法针对以上不足，近几年来，针对序列图像的时空相关性和人眼视觉特性，提出了许多改进算法，主要从以下几个方面着手：∙预测搜索起点利用相邻块之间的运动相关性选择一个反映当前块运动趋势的预测点作为初始搜索点，这个预测点一般比原点更靠近全局最小点。

从预测点开始搜索可以在一定程度上提高搜索速度和搜索精度。

∙中止判别条件利用相邻块的相关性自适应的调整终止阀值，当搜索值小于该值时，则认为满足条件，跳出后面的搜索过程。

∙搜索模板的选择在序列图像中，大多数的运动矢量都位于水平或垂直方向，因此可以设计相应的搜索模板（非对称搜索模板）来加快搜索速度。

二维光流运动估计的方法嘿，咱今儿个就来唠唠二维光流运动估计的方法。

你说这光流运动估计啊，就像是给运动的物体安上了一双眼睛，能让我们清楚地知道它是咋动的。

先来说说基于梯度的方法吧。

这就好比是在一个迷宫里找路，通过观察周围的变化来确定方向。

这种方法呢，简单直接，能快速地算出个大概来。

但是呢，它也有它的局限性，就像走迷宫有时候也会碰到死胡同一样，可能会不太准确。

然后呢，还有基于区域匹配的方法。

这就像是拼图游戏，把相似的部分找出来拼在一起，从而了解物体的运动情况。

这种方法呢，相对来说更准确一些，就好像拼图拼对了就能看到完整的画面。

可它也不是完美的呀，有时候找那些相似的部分也挺费劲儿的呢。

再有就是基于相位的方法啦。

这个就有点像听音乐的节奏，通过节奏的变化来感知运动。

它有它的独特之处，能在一些复杂的情况下发挥作用，就像音乐的节奏能带动人的情绪一样。

还有基于特征的方法呢，这就像是抓住物体的一些关键特点，然后根据这些特点的变化来估计运动。

就好比你记住了一个人的独特之处，下次再见到就能认出来一样。

咱说了这么多种方法，每种都有它的长处和短处。

就像人一样，没有一个人是完美无缺的，每种方法也都有它适用的场景和不适用的情况。

那咱在实际应用的时候可得好好琢磨琢磨，到底哪种方法更适合当下的情况呢。

你想想啊，要是在一个很复杂的环境里，那是不是就得选一个更能应对复杂情况的方法呢？要是在一个简单的场景下，也许就不需要那么复杂的方法啦，简单直接的说不定更好用呢。

总之呢，二维光流运动估计的方法有很多，咱得根据具体情况来选择，可不能瞎用一通啊。

这就好比你去爬山，总不能穿着高跟鞋去吧，得选对鞋子才能爬得稳当呀！咱对待这些方法也得这样，选对了，才能让我们更好地了解物体的运动，为我们的研究或者应用提供有力的支持。

你说是不是这个理儿呀？。

第三讲光流分析法3. 1二维运动与视在运动1- 三维场景 —— >二维的时变图像 —— > 数学上3D 2D 投影而我们所能得到的是时变图像的某种采样点阵(或采样栅格)的图像序列, 问题是：2. 可控与可观测问题一 >即真实二维位移场与速度是否可观测? 三维运动可由物体像素的三维瞬时速度或三维位移来描述，但三维瞬时速度 及三维位移正是我们要估计的，这是一个逆问题。

而我们可观测到的是视在运动。

(1) 假定投影中心在原点t '时刻投影pp —二维成像平面上的二维位移矢量成像平面，投影平面 光学上3.二维运动——也称投影运动:透视、正交投影t 时刻 P '投影PP —三维位移矢量二维位移场 二维速度场(2) 假定投影中心在O i 点 由于投影作用，从P 点出发，终点在O i P /虚线上的三维位移矢 量均有相同的二维投影位移矢量。

所以说，投影的结果只是三维真实 运动的部分信息。

(3) 设(X,t) R 3, t t l t 由像素的运动S c(X ，t) d c(X,t,t ')对应于点阵A 3 ，则有d p (X,t ; l t) d c (X,t ; l t)，假定三维瞬时速度为(X i ,X 2,X 3)，则V p (X,t) V c ( n,k)4. 光流场与对应场(1) pp 定义为对应矢量光流矢量定义为某点(X,t) R 3上的图像平面坐标的瞬时变化率， 为一个导数。

V (V i ,V 2 )T (dx i /dt,dx 2/dt)T表征了时空变化，而且是连续的变化。

(2) 当t t t 0时，则光流矢量与对应矢量等价。

如果在某个点阵A 3可 观测到这种变化，则就意义对应场 <——像素的二维位移矢量场 光流场 <――像素的二维速度矢量场 也分别称为二维视在对应场与速度场。

一般而言，对应矢量 工位移场光流矢量工速度场二维位移矢量函数(x ，t ) A 3d (n,k ； I) d p (X,t ; l t)(n ，k )Z 3k 表达了 t ‘- t 的时间离散n (n i , n 2)T光照变化—— ＞将防碍二维运动场的估计。

平面运动图象解析步骤打开程序：双击simi motion/creat a new project/create and save—选择你要保存的位置-save平面图像解析的步骤：一、建模（creating a sepcification）二、坐标换算（calibrating the camera）三、打点（获取象坐标,capturing the image coordinates）四、数值计算（calculating the scaled 2-D coordinates）五、数据输出（presenting the data）一、建模（creating a sepcification）建模的目的就是把人体简化为多刚体模型，通过选择相应的关节点并对关节点进行连线，从而形成人体棍图模型。

建模块包括2项内容：A．编辑坐标点(edit points)；B．连接坐标点(connections)A．编辑坐标点：操作：Specification-points-(左键按住拖拽至右边黑色区域，或者在上单击右键-edit)a.把左侧的predefined栏中已设置的点拖拽到右边的uesed points栏中b.对选择后的坐标点的名称和颜色进行编辑：在所选坐标点上右击-property,进行编辑c.编辑软件中未设置的关节点：在uesed points栏里的空隙处点击右键，选择add添加新的关节点，并编辑坐标点B．连接坐标点：两个坐标点连接就会形成一个人体的环节，程序有默认的常规的环节的连线，如大腿是髋关节点与膝关节点的连线。

出于分析的需要，需要在某些关节点之间建立连线，此时需要我们添加新的连接，方法如下：操作：将左键按住拖拽到右边的灰色区域（或者在其上右击后选择edit）New connections—编辑连接名(例如头-脚跟)—选择起始点（starting point）--line to –结束点/apply如果需要在单个点的周围划圈，则只需要选circle with radius，确定圆圈大小即可。

天津大学《数字媒体信息技术》课程教学大纲课程编号：课程名称：数字媒体信息技术学 时： 40 学 分： 2学时分配： 授课：24 上机：16 实验： 实践： 实践（周）：授课学院： 计算机科学与技术学院适用专业： 计算机科学与技术先修课程： 计算机图形学，图像处理一．课程的性质与目的《数字媒体信息技术》是计算机应用专业数字媒体方向的一门重要的专业课。

介绍数字媒体的概念、历史、发展技术和新应用领域，如图形设计、绘制、文字、声音、色彩、图形图像、音频视频等媒体的数字化技术和应用情况。

陪养学生从事数字媒体相关工作的基本能力，为后续的各专业骨干课程奠定基础，使学生成为具有数字媒体综合能力的技能型人才。

二．教学基本要求课程内容实务，理论与实践并重，深入浅出。

对每节课的授课内容进行精心设计。

教学方式上采用多媒体和启发式、互动式、案例式、课堂辩论等教学方法。

引导学生深入思考，扩大信息量，调动学生学习自主学习的积极性，学会理论联系实际。

本课程课时为40学时，其中讲授时间约24学时，上机时间约16学时。

本课程讲授内容分为十章，分别是数字媒体基本概念；数字媒体发展史；媒体信息的采集与表示；音频信息及处理；图像与视频的压缩；运动估计；视频检索；交互式媒体技术；立体视觉；网络与数字媒体等。

三．教学内容第一章 数字媒体概念介绍数字媒体的概念。

第二章 数字媒体发展史介绍从计算器到多媒体的发展历史。

第三章 媒体信息的采集与表示音频采集与数字化表示表示。

数字视频的格式，视觉原理、时空采样、传感器与采集卡。

第四章 音频信息及处理音频信号的时频域分析，音频信号的编码技术。

第五章 图像与视频的压缩介绍H.261、H.263、MPEG-1、MPEG-2、MPEG-4等压缩方法。

视频的压缩编码、压缩评价、变换编码等。

第六章 运动估计二维运动估计及三维运动估计的常见方法，包括基于光流场估计、基于块估计、基于像素估计、全局估计，基于特征估计法、点对应估计法、直接运动估计法等。