随着人们对视频信息需求的日益增长，H.26X、MPEG系列视频国际标准不断被推出，我国也积极推动自己的音视频编解码标准(AVS)的制定，AVS的视频部分己于2006年3月1日开始实施。其中，由MPEG组织制定的MPEG-4标准是一种基于“内容”的可交互性的第二代视频压缩标准，该标准在视频检索、视频监控和IPTV等方面都具有良好的发展前景。本论文对MPEG-4的高级应用前提——视频分割和运动估计算法进行了分析和改进。尽管MPEG-4定义了视频对象的概念，但是却没有定义视频分割算法，因此本论文对视频分割算法进行了研究和设计。首先，介绍了现有的几种视频分割算法，并对其进行了分析。其中的对称差分法能准确快速地检测到运动物体，在实时性要求较高的视频压缩中具有一定的优越性；但是该方法存在有时会提取不全或提取不出物体的缺陷。然后，本论文在对称差分法的基础上提出了一种视频分割算法，加入运动估计，还在对称差分法的中间处理过程——二值图像的预处理中加入了双阈值法作去噪去空洞处理。实验表明，本论文的算法解决了对称差分的缺陷，在运动信息不够明显的情况下依然能够提取出整个物体，从而增强了对称差分法的健壮性。运动估计算法不仅对本论文的视频分割有着很重要的意义，在整个的视频压缩算法中也具有举足轻重的作用，是视频压缩中占用计算量最大的一部分。本论文接下来介绍了运动估计算法原理，随后对几种经典的运动估计算法进行了描述和分析。本论文在对标准视频序列进行深入分析之后，发现运动矢量的分布除具有中心偏移性这一特点外，还具有另一重要特点，即在中心点水平和垂直方向上的分布较其他方向的分布更为密集，据此本论文提出了一种符合该特点的运动估计算法——新十字形搜索算法(NCS)，将搜索模板改进为大小十字形。实验表明该算法较之前的钻石搜索算法在图像质量和搜索点数方面均具优越性。运动估计中除了运动搜索算法，起点的预测也是不可或缺的，本论文设计了一种与NCS相匹配的运动预测算法，首先将预测器的数量减少为两个，并采用比较精确的比较法，然后根据自适应的阈值法来决定预测后采取的动作：是直接中止还是进入不同的十字模板进行搜索。这一系列的改进进一步加强了NCS算法的优势。