[Xvid-devel] PSNR, Bitrate of Full Search and other algorithms

[Chien Tran]

That's what makes me worry. I only implement the full pel motion estimation
and disable sub-pel on other algorithms. Not only the PSNR is higher, but
the bit rate is also significantly smaller (Ex: 520kbit/s with UMHexagon
and 430kbit/s with new algorithm). Actually, I implement this algorithm on
JM Reference Software, and the PSNR and the ME time are calculated
automatically when encoding the video. Therefore I think the PSNR and
bitrate are correct. Moreover, the search method is not complex because it
only need you to set the motion vector and return the cost when using that
motion vector.

The new algorithm I implemented is based on algorithm presented in this
paper:
http://ihome.ust.hk/~tkt/PaperReading-EESM5547/paper%20list/motion%20estimation(16)/Novel%20Directional%20Gradient%20Descent%20Searches%20for%20Fast%20Block.pdf
And the experiments result when implementing it on my computer is totally
different with the result in that paper (PSNR higher and Bit rate lower)
Regards,

Chien Tran

2012/6/15 Michael Militzer <michael at xvid.org>

> Hi,
>
> 20% smaller bitrate at higher PSNR only from using a new ME algorithm
> doesn't sound right. Are you sure you've measured your PSNR right? Or
> that you're not comparing apples with oranges (like: your new algorithm
> does subpel refinement but the full search / hexagon search you compare
> it to is limited to fullpel precision only)?
>
> Best regards,
> Michael
>
>
> Quoting Chien Tran <chien.study at gmail.com>:
>
> > Thank you for your answer. The Rate-Distortion Optimization is turned off
> > completely. I was surprised at the result because in many scientific
> papers
> > about motion estimation, they often compare the PSNR and the bit rate
> with
> > Full Search algorithm to evaluate the performance of new algorithm. And
> in
> > my experiment result with the new algorithm, the UM Hexagon algorithm
> that
> > is used in H.264 (and I personally think that this is an quite advanced
> > algorithm)  also gives quite similar PSNR and bit rate compared with Full
> > Search, that make me feel unsure about my algorithm because mine is very
> > simple and much more simpler than the UMHexagon algorithm, but the
> bitrate
> > is so different (ex. the Full Search is 526.6 kbits/s, UMhexagon is
> > 526.61kbits/s, and my algorithm is 426.68 kbits/s).
> >
> > Regards,
> >
> > 2012/6/14 Michael Militzer <michael at xvid.org>
> >
> >> Hi,
> >>
> >> it depends on how your full search is implemented and how you determined
> >> your test points on the R-D curve (rate-controlled, at constant QP?).
> You
> >> didn't mention about this.
> >>
> >> In general though, it is not unusual at all that an advanced motion
> >> estimation algorithm beats a full search strategy. It is well known that
> >> a naive full search (so simply selecting the match that minimizes a
> >> simple distortion metric like SAD or SSE) produces highly irregular and
> >> erratic motion vector fields. A more advanced motion estimation
> algorithm
> >> like a predictive search strategy usually produces much smoother motion
> >> vector fields that better correlate with the underlaying "true" motion,
> >> can be more effectively predicted and are therefore cheaper to code.
> >>
> >> The savings in coding the motion vectors can be so large that an
> advanced
> >> motion estimation algorithm produces a lower overall rate than a full
> >> search approach (like you observed). As to PSNR: Note that PSNR
> typically
> >> measures the distortion of the reconstructed pictures. In contrast, SAD
> or
> >> SSE that you use during your full search capture the absolute difference
> >> between the current block and its match in the reference frame (so
> before
> >> any reconstruction). The motion vectors that minimize SAD/SSE during
> motion
> >> estimation do not necessarily produce reconstructed frames with best
> PSNR.
> >>
> >> Best regards,
> >> Michael
> >>
> >>
> >> Quoting Chien Tran <chien.study at gmail.com>:
> >>
> >> > Hi guys,
> >> > Sorry if this question make you feel uncomfortable because it is not
> >> > related to XVID, but more related to Motion Estimation algorithm in
> video
> >> > compression. I am implementing new search algorithm that is used in
> >> motion
> >> > estimation. The interesting point is that the new algorithm give the
> >> bigger
> >> > PSNR and lower bit rate in comparison with Full Search algorithm. I
> >> tested
> >> > this new algorithm on different video sequences here
> >> > http://trace.eas.asu.edu/yuv/ and I still got the same results
> (bigger
> >> PSNR
> >> > and lower bit rate than Full Search). What do you think about this?
> Is it
> >> > normal or just a bugs in my algorithm? and do you guys think it is
> >> possible
> >> > that sometimes new algorithm can give bigger PSNR and lower bit rate
> than
> >> > Full Search algorithm? Has any of you experienced this kind of strange
> >> > result before?
> >> > Thanks in advance!
> >> >
> >> > --
> >> > Best wishes,
> >> >
> >> > Tran Xuan Chien
> >> > University of Information Technology
> >> > Phone: (+84) 1692 468 154
> >> > _______________________________________________
> >> > Xvid-devel mailing list
> >> > Xvid-devel at xvid.org
> >> > http://list.xvid.org/mailman/listinfo/xvid-devel
> >> >
> >> >
> >>
> >>
> >>
> >> _______________________________________________
> >> Xvid-devel mailing list
> >> Xvid-devel at xvid.org
> >> http://list.xvid.org/mailman/listinfo/xvid-devel
> >>
> >
> >
> >
> > --
> > Best wishes,
> >
> > Tran Xuan Chien
> > University of Information Technology
> > Phone: (+84) 1692 468 154
> > _______________________________________________
> > Xvid-devel mailing list
> > Xvid-devel at xvid.org
> > http://list.xvid.org/mailman/listinfo/xvid-devel
> >
> >
>
>
>
> _______________________________________________
> Xvid-devel mailing list
> Xvid-devel at xvid.org
> http://list.xvid.org/mailman/listinfo/xvid-devel
>



-- 
Best wishes,

Tran Xuan Chien
University of Information Technology
Phone: (+84) 1692 468 154