本論文以合成/分割的程序實現可變區塊大小動態搜尋，減少決定區塊大小時所需花費的計算量。我們先選定一區塊大小進行動態搜尋，再以動態搜尋所得的資訊，動態得更新臨界值，再經由臨界值得比對，判斷各相鄰區塊是否可合成較大的區塊，若這些相鄰區塊均不可合成，則對這些區塊進行邊緣的判斷，再根據各區塊所包含之邊緣資訊，將之分割成適當的區塊大小。最後，我們將合成/分割演算法在視訊標準H.264中實現，實驗結果顯示，合成/分割演算法的效能相當接近H.264中使用完全搜尋及驅動16x16，16x8，8x16和8x8四種模式的情況。

A merging/splitting procedure for variable-size block motion estimation is proposed to reduce the computation for block-size decision. A smaller block-size is initially used for motion estimation. An adaptive threshold, which depends on the information obtained from the motion estimation, quantization parameter, and rate distortion cost function is used to determine if the motion vectors of the neighboring blocks should be merged or not. If those blocks in a macroblock can not be merged, we then start edge classification. If the block contains edge, we split it into smaller sub-blocks according to edge information. The proposed merging/splitting procedure is applied to H.264 video encoders. Simulations show that the performance of the proposed method is close to that of H.264 JM2.0 when 16x16, 16x8, 8x16 and 8x8 block modes are enabled and the exhaustive search method is used to determine the block-sizes.

[1]M. Chan, Y. Yu, and A. Constantinides, “Variable size block matching
motion compensation with applications to video coding,” Proc. Inst.Elect.
Eng., pt. I, vol. 137, no. 4, pp. 205–212, Aug. 1990.
[2]H. Jelveh and A. Nandi, “Improved variable size block matching motion
compensation for video conferencing applications,” in Digital Signal
Processing, A. Cappellini and A. Constantinides, Eds. Berlin, Germany :
Springer-Verlag, 1991, pp. 391–396.
[3]A. Puri, H. Hang, and D. Schilling, “Interframe coding with variable block
size motion compensation,” in Proc. GLOBECOM'87, pp. 65–69.
[4]Y. Shoham and A. Gersho, “Efficient bit allocation for an arbitrary set of
quantizers,” IEEE Trans. Acoust., Speech, Signal Processing, vol. 36, pp.
1445– 1453, Sept. 1988.
[5]G. Sullivan and R. Baker, “Efficient quadtree coding of images and video,”
IEEE Trans. Image Processing, vol. 3, pp. 327–331, 1994.
[6]H. Bi and W. Chan, “Rate-constrained hierarchical motion estimation using
BFOS tree pruning,” in Proc. ICASSP, 1996, pp. 2315–2317.
[7]P. Chou, T. Lookabaugh, and R. Gray, “Optimal pruning with applications to
tree-structured source coding and modeling,” IEEE Trans. Inform. Theory, vol.
35, pp. 299–315, Mar. 1989.
[8]S. Kiang, R. Baker, G. Sullivan, and C. Chiu, “Recursive optimal pruning with
applications to tree structured vector quantizers,” IEEE Trans. Image
Processing, vol. 1, pp. 162–169, Apr. 1992.
[9]Injong Rhee, Graham R. Martin, S. Muthukrishnan, and Roger A. Packwood,
“Quadtree-structured variable-size block-matching motion estimation with
minimal error,” IEEE Trans. Circuits Syst. Video Technol., vol. 10, Feb.
2000.
[10]“MPEG-4 Video Verification Model version 18.0”, ISO/SC29/WG11 N3908,
January 2001
[11]International Telecommunication Union, “Video coding for low bit-rate
communication,” ITU-T Recommendation H.263, July. 1995.
[12]Joint Video Team (JVT) of ISO/IEC MPEG and ITU-T VCEG, “Editor’s Proposed
Draft Text Modifications for Joint Video Specification (ITU-T Rec. H.264 |
ISO/IEC 14496-10 AVC), Draft 7,” 5-th Meeting : Geneva, Switzerland, 9-17
October, 2002.
[13]X. Li and C. Gonzales, “A locally quadratic model of the motion estimation
error criterion function and its application to subpixel interpolation,”
IEEE Trans. Circuits Syst. Video Technol., vol. 6, pp. 118–122, Feb. 1996.
[14]Dimitrios Tzovaras and Michael G. Strintzis, “Motion and disparity field
estimation using rate-distortion optimization,” IEEE Trans. Circuits Syst.
Video Technol., vol. 8, pp. 171–180, April. 1998.
[15]Lee, M. H., and Crebbin. G, “Classified vector quantization with variable
block-size DCT models,” IEE Proc. Vis. Image Signal Process., 1994, 141,
(1), pp, 39-48
[16]A. M. Peacock, D. Renshaw and J. Hannah, “Motion direction estimates from
differenced DCT images,” Electronic Letters, vol.37, 1st Feb 2001.
[17]Yu-Kuang Tu , “Computation reduction for lower-frequency DCT coefficients,”
Department of Electrical Engineering, National Cheng Kung University, Tainan,
Taiwan, thesis for master of science, June, 2001.
[18]Chin-Yun Chen, “Computation reduction algorithms for motion estimation in
low rate video coders,” Department of Electrical Engineering, National Cheng
Kung University, Tainan, Taiwan, thesis for master of science, June, 2000.
[19]A. Hallapuro and M. Karczewicz, “Low complexity transform and quantization
– Part 1: Basic Implementation”, JVT document JVT-B038, February 2001.
[20]Thomas Wiegand, Gary J. Sullivan, Gisle Bjontegaard, and Ajay Luthra,
“Overview of the H.264 / AVC Video Coding Standard”, IEEE Trans. Circuits
Syst. Video Technol. , JULY. 2003.
[21] Thomas Wiegand, Heiko Schwarz, Anthony Joch, Faouzi Kossentini, and Gary J.
Sullivan, “Rate-Constrained Coder Control and Comparison of Video
Coding Standards”, IEEE Trans. Circuits Syst. Video Technol. , JULY. 2003.
[22] Xiang Li, Guowei Wu, “Fast Integer Pixel Motion Estimation”, JVT document
JVT-F011, December 2002.
[23] Zhibo Chen, Peng Zhou, Yun He, Yidong Chen, “Fast Integer Pel and
Fractional Pel Motion Estimation for JVT”, JVT document JVT-F017, December
2002.