[M4IF Technotes] Problem : Half Pixel ME

[Christoph Lampert]

Hi,
I can answer you something, not as an expert but with some 
experience from the Simple Profile Open Source MPEG-4 Codec XviD
(www.xvid.org): 
On Thu, 8 Aug 2002, Sachin Patil wrote:
> Hello all,
>      I have an integer pel search Motion Estimation algorithm 
> implemented  for my MPEG4 video encoder. Now I am trying to refine the 
> search using half pixel resolution. I find that there is an increase in 
> file size with half pel refined search.
> 
> Can anyone tell me the advantages of using Half Pel search with respect to 
> the following --
> 1. I want to know if there can be an increase in the output file size.

It is (of course) possible that the Half Pel motion vectors need more
space in VLC than the Full Pel ones, and that the gain in prediction 
accuracy does not compensate for this. However, if you just
"refine" motion vectors from a Full Pel search by a small amount, I
consider this effect rather unlikely for "normal" input material. You
might want to check if your implementation is correct. 
> 2. Is half pel refinement used only for an improvement in quality ( quality 
> measure used : PSNR ) ?

For us it has both effects: Smaller bitrate at fixed quantization
parameter, _and_ improvement in quality (more than 1dB gain in PSNR,
often much more). 
> 3. What is the increased computational complexity?

That depends only on your implementation. 
In our codec on i386 with SIMD optimization, speed with Half Pel usage is
about two thirds of speed without (always remember it's Simple Profile). 
This is mostly because we interpolate the whole image, then perform ME
without distriminating between Full Pel and Half Pel positions, and after
that there is a simple +-1 refinement check in x and y of the so far best
motion vector. 
Hope that helps,
Christoph
-- 
Christoph H. Lampert chl   math,uni-bonn,de | Diese Signature wurde maschi-     
Beringstr. 6, Raum 14 Tel. (0228) 73-2948 | nell erstellt und bedarf
Sprechstunden: keine, aber meistens da    | keiner Unterschrift. AZ 27B-6