# [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
frame).

Example:
Let buffer size = 5
paths = P
paths = BP
paths = BPP
paths = PBBP
To compute paths, we try paths+BBBP vs paths+BBP vs paths+BP
vs paths+P.
Say the lowest cost is paths+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?

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
decided.
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

```