[x264-devel] Re: How b_adapt works?

Loren Merritt lorenm at u.washington.edu
Fri Jul 1 18:08:37 CEST 2005

On Fri, 1 Jul 2005, Tuukka Toivonen wrote:

> I'm trying to understand b_adapt algorithm from the latest
> svn, but it's hard to make sense of it.
> It looks like it encodes a lowres version of some frames
> using different frame types (P/B), computes a score using
> SATD and the lowres frame, and does a decision based on
> that.
> There seems to be two algorithms, first disabled (#if 0).
> What means "BFS"?
> What is this "path" thing?

"BFS" = breadth first search
The idea of the disabled algo is: Given some set of future frames (more 
than max_b_frames), try all possible combinations of frame types, and use 
the one with minimum total SATD. As stated that would take exponential 
time, but that's where BFS comes in: Since I use only 1 past reference 
frame and I'm not actually encoding the frames, to calculate the cost of 
frame N I don't need to care about the types before the previous P-frame. 
A "path" here is a list of frame types. paths[i] is the lowest cost path 
that ends on frame i (where i is counted starting from the last encoded 

Let buffer size = 5
     paths[1] = P
     paths[2] = BP
     paths[3] = BPP
     paths[4] = PBBP
To compute paths[5], we try paths[1]+BBBP vs paths[2]+BBP vs paths[3]+BP 
vs paths[4]+P.
Say the lowest cost is paths[2]+BBP = BPBBP. We have no more frames to 
consider, so this is the best estimate of optimal frametypes. So we encode 
the first bunch (BP), read in the next two input frames, and call 
x264_slicetype_analyse again. It can then calculate the new paths[1..3] 
for free, since the frame costs are cached.

> What the indices are in frame->i_cost_est[16][16]?

The 1st index is the distance from the current frame to list0ref0. The 2nd 
index is 0 for P-frames or distance to list1ref0 for B-frames.

> What are the last three parameters p0,p1,b in x264_slicetype_frame_cost?

p0 is the frame number of list0ref0, where counting starts with #0 = the 
last frame coded so far, and 1+ are the frames whose types are to be 
b is the frame number of the frame currently being analysed.
p1 is the frame number of list1ref0, or equal to b for P-frames.

--Loren Merritt

This is the x264-devel mailing-list
To unsubscribe, go to: http://developers.videolan.org/lists.html

More information about the x264-devel mailing list