DCT and XviD

[Wbtz]

Hi,
I am new to dct. Read about it and the calculations with the 8x8 matrix. How exactly does Xvid do it?(I have read about 8x8 blocks/matrix, but not sure what it does). Is it based on P frames?

What does the quantization do? After quantization, can each calculation be written to a file?

Is this algo standard for all codecs that use dct?

Which part of the source code can i locate this algorithm?

Did a search in the forum. Results displayed were to deep for a newbie like me. Sorry for the ignorance!

[-h]

MPEG-based codecs all perform a DCT on the image data (both for I-frames and P-frames) and then quantize the result to reduce the number of bits needed to store the remaining values.

DCT (Discrete Cosine Transformation):
Transforms the 8x8 square of pixels into frequency coefficients. Think of it as a filter that picks out certain patterns in the 8x8 pixels and stores information about those patterns, instead of storing the values of the pixels individually. Here (http://www.cs.sfu.ca/CourseCentral/365/li/material/notes/Chap4/Chap4.2/DCT_basis.gif) is an image that shows how each of the 64 values created by the DCT describes the original 64 pixels. Notice that the top-left values are quite plain, getting progressively noisier until the bottom-right is reached. The useful part about performing this transformation is that with just a few of these values (namely those around the top-left), you can get a pretty good idea of what the original 64 pixels would have looked like. Thus you can throw away a lot of these values, and still have a pretty good image when you reverse the DCT.

Quantization:
Now performing the DCT doesn't actually save us any bits, it just converts the pixels into a different format which is more apt for compression. When we quantize, we actually divide the values that come from the DCT by a value called the quantizer to leave us with less information to store. An example:

The DCT outputs (I'm making these up) values like:

100, -50, 203, 8, -240, 1, 0, 500

Now those aren't really nice values to work with - they would take quite a few bits to store. However if we divide them all by 50:

2, -1, 4, 0, -5, 0, 0, 10

Now we have much smaller values, which will requre far fewer bits to actually store in our AVI file. The fact that we have thrown away so much information by division means that as a result, when we reverse the DCT we won't get exactly the same 8x8 block of pixels that we started with, but thanks to the DCT approximating a large number of pixels with each coefficient we still have something that resembles the original.

If you want to see how XviD performs these steps, locate the "mbtransquant.c" file in the xvidcore module, for every 16x16 macroblock it steps through performing the DCT, quantizing the output, dequantizing the output (i.e. multiplying it by the quantizer) and reversing the DCT (Inverse DCT). The actual forward DCT transformation is in "fdct.c", and quantization is in "quant_h263.c".

-h

[Wbtz]

Hey thanks!! Deeply enlightened!

After quantization will be mulitplexing? As in the arrays of quantized DCT outputs will be multiplexed together and then the video will be encoded? The reason I am asking this is because I would like to try and modify the code such that the quantized DCT outputs will be written to a file everytime it has been converted.

[-h]

After quantization will be mulitplexing? As in the arrays of quantized DCT outputs will be multiplexed together and then the video will be encoded? The reason I am asking this is because I would like to try and modify the code such that the quantized DCT outputs will be written to a file everytime it has been converted.

I'm not sure what you want to do.. the quantized DCT coefficients are always output (into the AVI of course). What is your final goal, once you have the quantized coefficients?

-h

[SirDavidGuy]

I think he's trying to make a lossless encoder, storing all the differences between a highly compressed version and the original, then recombining them.

[Wbtz]

Good guess but I think my knowledge is so limited I don't even know how to start on a loseless codec. I have a project in hand, requires me to sort of split the video into different "streams". Since each video only has 2 streams, this is not sufficient. The only other way I have in mind is to used the quantized DCT outputs.

Question: Instead of storing into the avi, is it possible to store into separate small files then transferred in parallel then recombined at the client?

I am not talking about splitting the avi in blocks of files but rather each frame of the avi into different blocks. This is to facilitate faster transfer of each frame to the client.

[-h]

Question: Instead of storing into the avi, is it possible to store into separate small files then transferred in parallel then recombined at the client?

I suppose, but they would take up quite a bit more space since you couldn't exploit RLE coding. Unless you want each macroblock written to a separate file? Again we're talking about a fair bit of overhead.

I am not talking about splitting the avi in blocks of files but rather each frame of the avi into different blocks. This is to facilitate faster transfer of each frame to the client.

I think I need an example of how this could speed things up..

-h

[serbersan]

-h I would like to learn about the mpeg-4 video compression, and If I could understand it a little then I'll try to contribute a little to XviD project. I'm really amazed with the explanations about XviD than you and other members do.

Do you recommend me (you or other person with important acknowledge) a book to buy, with a basic introduction to the video compression ?

Some link to Web would be usefull but, I'm very interested in a book, maybe it has been translated to spanish, now.

Thanks

[Wbtz]

I suppose, but they would take up quite a bit more space since you couldn't exploit RLE coding. Unless you want each macroblock written to a separate file? Again we're talking about a fair bit of overhead.


A macro block stores each 8 by 8 array of quantized dct outputs right? If I have not interpreted wrongly, each frame is divided into 16 by 16 macroblocks?

Run-length encoding is used after quantization? I suppose it would be better to write each macroblock to a file rather than each quantized dct output. A question is how to identify which macroblock belongs where.


I think I need an example of how this could speed things up..


My project suggest that if each quantized output or each macroblock is delivered to the client in parallel simultaneously, perhaps streaming could be faster. Not sure if feasible but it is to simulate and discover.

Currently I am looking at fdct.c file. Its very intriguing but my c programming is always only on a single file with the include of a single library. The source for XviD has so many files. The encoder.c file calls so many library and nothing to the fdct.c file so how does it calls the dct function? <-- Apologies for a super dumb question.

In fact my fundamentals are a little fuzzy. Let me have a go at it. A frame is divided into different 16 by 16 pixels of macroblocks. Each macroblock has 4 Y blocks and 1 U block and 1 V block? (How does dat make 16 x 16???) Each block is 8 by 8 pixels. DCT is carried out on the individual block. Hope I got this right!

Thanks -h. you are amazing!

[SirDavidGuy]

An overview:

1. A macroblock is 16x16 pixels
2. The DCT operates on a group of 8x8 pixels.
3. The Y component of each macroblock is split into 8x8 sections, which are all DCT'ed and quantitized.
4. The U and V components are all resized to a quarter (in 4:1:1) the resolution, since it's harder to detect loss of resolution in these.
5. These are then DCT'ed.


Do you recommend me (you or other person with important acknowledge) a book to buy, with a basic introduction to the video compression ?

"Video Compression Demystified" by Peter Symes is a great introduction, but costs about 50 bucks. :scared:

[-h]

A macro block stores each 8 by 8 array of quantized dct outputs right? If I have not interpreted wrongly, each frame is divided into 16 by 16 macroblocks?

A macroblock consists of 6 8x8 blocks which represent a 16x16 pixel region of the image. In those 6 8x8 blocks we have 4 blocks representing the Y component (luminance), and 2 representing U and V (colour). Since we have 2 colour blocks versus 4 luminance, there is less colour information stored.

Run-length encoding is used after quantization? I suppose it would be better to write each macroblock to a file rather than each quantized dct output. A question is how to identify which macroblock belongs where.

Yes, after quantization you have lots of 0's, so RLE is an effective way to reduce the number of bits needed. They could be identified by being in separate files, I imagine..

My project suggest that if each quantized output or each macroblock is delivered to the client in parallel simultaneously, perhaps streaming could be faster. Not sure if feasible but it is to simulate and discover.

I wouldn't think so. Ultimately the pipe to the client is what's slowing you down, and opening more transport sessions won't create more bandwidth. Should increase TCP/IP packet overhead though.

Currently I am looking at fdct.c file. Its very intriguing but my c programming is always only on a single file with the include of a single library. The source for XviD has so many files. The encoder.c file calls so many library and nothing to the fdct.c file so how does it calls the dct function? <-- Apologies for a super dumb question.

I wouldn't worry about fdct.c, all it does is transform the input into the DCT domain. The "important" part from your perspective would be mbtransquant.c, that is where each macroblock undergoes the dct and quantization. Also, mbcoding.c is where the blocks themselves are RLE-coded and output to the bitstream.

-h

[SirDavidGuy]

Try not to think of the DCT as a changing of numbers.

Think of it as a rotation in 64-D space, with the DCT determining where it is rotated to.

All the DCT does is change the information out of the spatial domain, and into the frequency domain, with the more important ones in the top left. Since you can set the bottom-right numbers to zero, and rotate it back to the spatial domain without much difference, all the zeroed coefficients aren't perceptible.

[Wbtz]

Thanks again. Understand the DCT part but still a little unclear about the macroblocks.

If a macroblock contains 6 8 by 8 pixels of blocks that makes more information than a 16 by 16 region? Mathematically 6x8x8 is greater than 16x16? Ok this is the only thing confusing me.

Will take a look at both mbtransquant and mbcoding.

Will also try to write each macroblock to a file and see if it actually will be faster. Frankly I doubt it too but heck, got to appease my supervisor!

Will try and use the RLE-coded macroblocks instead of non RLE ones.
My C programming is shallow though, still cant understand how the encoder works with so many .c files and functions.

[Nic]

LoL...-h should charge by the hour :)

Working with lots of .c files is done by having lots of .h files, one for each .c file. Then you #include the .h file into another .c file to use the functions from it.

Please try & look up as much as you can from the net before asking here too much though, we dont want to distract -h too much :)

Take Care & good luck! :)

Cheers,
-Nic

[bergi]

the picture is in yuv12 format

yy
yy
u
v

so 4xy + 1xu + 1xv = 6x

there is 1 color information (u&v) for 4 brightness informations (y), because the human eye sees more the difference of brightness, than the difference of color.

[Wbtz]

Whoops..sorry -h! Got it! Still dont really get the YUV part. I know the conversion and all but like what i said mathematically, it seems 6 times 8 times 8 is greater than 16 times 16! Haha..I must be missing something! Thanks!!

Think I make myself clearer
A macroblock is 16 x 16 pixels = 256 pixels

A macroblock is converted to YUV totally 6 blocks of 8 x 8 pixels and this total is 384 pixels. isnt this more than what perviously was?

I was also wondering if only -h understood the source code for xvid. Dun wanna bother him too much. I feel embarrassed about being such a weakling.

Also been looking at the code. Seems I have to refer back to encoder.c no matter what and the other c files for various functions so i guess i cannot bullet through and just understand the mbtransquant.c . Initially in the encoder.c there is a "fill members of encoder structure" Why is there a need for this line?

pEnc->mbParam.edged_width = 16 * pEnc->mbParam.mb_width + 2 * EDGE_SIZE;

mbParam.mb_width i have determined it to be the number of macroblocks to fit the width.
Edge_size is defined as 32

So what is edged_width for? Also what is "stride" for?

[-h]

Still dont really get the YUV part. I know the conversion and all but like what i said mathematically, it seems 6 times 8 times 8 is greater than 16 times 16! Haha..I must be missing something! Thanks!!

Well, think of it as in RGB colour - each pixel requires 3 bytes to store, 1 each for red, green and blue. Therefore, a 16x16 "region" of an RGB image would actually contain 12 8x8 blocks - 4 8x8 blocks for red, 4 for green and 4 for blue. Those 12 8x8 blocks do indeed represent 3 16x16 areas, but they are combined to give you the final full-colour image.

In YUV images, to create a 16x16-pixel area of the image, you need a 16x16 block of the Y component (luminance), but only 2 8x8 blocks for the colour components (U and V). Those 2 colour components are combined with the Y component to give you a final full-colour image. If you only had 256 values (as you are thinking), we'd have a black-and-white image with no colour - the extra bytes you're wondering about (384 pixels as opposed to 256) are used to convey colour information.

Also been looking at the code. Seems I have to refer back to encoder.c no matter what and the other c files for various functions so i guess i cannot bullet through and just understand the mbtransquant.c . Initially in the encoder.c there is a "fill members of encoder structure" Why is there a need for this line?

Encoder.c was supposed to be a rather brief abstraction of the entire MPEG-4 video process - a line here saying "estimate motion", a line there saying "code macroblock", etc. It just got a bit larger over time :)

pEnc->mbParam.edged_width = 16 * pEnc->mbParam.mb_width + 2 * EDGE_SIZE;

MPEG-4 requires the image to be padded out around the sides, so the codec has some breathing room for when it tries to approximate the motion of each block. Consider a video where the camera moves from left to right - on the left side, blocks are going to be disappearing out of the picture as they move out of the camera's scope, however on the right side, *new* blocks are going to be appearing. We don't want to restrict ourself to only using fully stored blocks for approximating motion, so we let ourselves look *outside* the area of the image that is visible and copy a partial block, just because it's better than storing the block without the benefit of motion compensation. Of course a block from outside the image doesn't contain real image data from the future, it contains repeated rows of the right-most visible pixel (as per the edging part of the mpeg-4 spec).

There are a great many such oddities you'll find, but most of them make sense when working from the spec. Have a look at the MPEG-4 video verification model (http://mpeg.telecomitalialab.com/working_documents/mpeg-04/visual/video_vm.zip) (400+ pages!) to see what we're working from.

Oh, and a stride is a value which describes (for XviD's purposes) how many bytes you have to go forward to get to the point in the next line that you want to work with. Because images have edging in XviD, the stride will be greater than the original image width because we have more data to skip over to go down a line. i.e. for an input image of width=320, edging will increase the internal width to 384, thus we need to skip 384 pixels to go down one line (stride=384).

-h

[duartix]

Well I was about to suggest:
http://www.cs.cf.ac.uk/Dave/Multimedia/node200.html
I found this very enlightening althoug it's about MPEG2.
The fundamentals concepts are similar though.

[Wbtz]

Learnt a new thing today. Perhaps not new to many of you but new to me. The difference between field and frame interlacing.

http://icsl.ee.washington.edu/~woobin/papers/General/img27.gif

One question about it is why do you need to multiply the "stride" by 2 after quantization since you have already convert frame2field by the MBFrametoField function in mbtransquant.c?
My impression is as in the picture with the line interchanged to form field interlacing shown. But why multiply by 2? Since the lines have been changed from 0123456789 etc to 12468101214 etc. If one multiplies the stride by 2, then you will be skipping lines?
All these i am talking about is in the function MBTransQuantIntra. Finally why do you need to do fdct then quantization and then dequantization and then idct all in the same function? Thought dequant and idct was in decoding while dct and quant was in encoding?

Also why do you need to do a MBTransQuantInter since you did it on the intra-frames? Does the inter-frames thing has to be dine due to motion compensation? the B-frames?

-h hope i m not annoying you with all these questions!

[-h]

-h hope i m not annoying you with all these questions!

Not at all, it's a good way to keep up with the source.

One question about it is why do you need to multiply the "stride" by 2 after quantization since you have already convert frame2field by the MBFrametoField function in mbtransquant.c?

That is a trick to copy lines in a field-based way back to the image (for future encoding use). If we didn't do that, we'd have to re-interlace the blocks manually, then perform some cbp checks when copying them back over. Remember, we want the reference frame to look the way it did when it was input, not the deinterlaced version of it you'd get if the stride trick wasn't there.

Finally why do you need to do fdct then quantization and then dequantization and then idct all in the same function? Thought dequant and idct was in decoding while dct and quant was in encoding?

The encoder must keep a copy of the image that would be seen at the decoder's end. Thus, after fdct and quantization (which alter the image), we reverse them and store the result so the encoder knows *exactly* what the image will look like when decoding. If this weren't performed, differences generated by fdct/quant would build up over time and look horrible when played back.

Also why do you need to do a MBTransQuantInter since you did it on the intra-frames? Does the inter-frames thing has to be dine due to motion compensation? the B-frames?

I'm not sure I follow you. MBTransQuantXxx functions are called depending on the type of the block we're encoding. If it's inter, MBTransQuantInter will be called. The intra/inter decision is made in motion estimation.

-h

[sysKin]

Also why do you need to do a MBTransQuantInter since you did it on the intra-frames? Does the inter-frames thing has to be dine due to motion compensation? the B-frames?

It's for intra-macroblocks which are in P-frames.

You've just found another person who can be annoyed with all the questions ;) so ask. I was in the same situation about 4 months ago - I didn't know anything about mpeg-4 and wanted to help. Now, my new motion estimation code was uploaded in development-cvs ^__^ (today if I'm not mistaken) so it's not very difficult to learn.

[Wbtz]

Wow sysKin, thats pretty encouraging!

I think I quite understand the DCT and Quantization now. Intra is for I-frames and inter for the P frames and B frames. However, are B frames introduced or do they exist already? It is quite ambigious in most tutorials, all I know is that they are insert between then I or P frames and have most compression as the macroblocks can choose to either be differentially coded from the previous or next frame.

I am now looking at how each macroblock is stored after quantization. It looks like it undergoes VLC but not sure how it is written. Looking at mbcoding.c now. This output to bitstream is where the macroblocks are written in order? How are they identified as being in the same frame?

[-h]

I am now looking at how each macroblock is stored after quantization. It looks like it undergoes VLC but not sure how it is written. Looking at mbcoding.c now. This output to bitstream is where the macroblocks are written in order? How are they identified as being in the same frame?

Yep, mbcoding.c writes the 64 DCT coefficients along with ancillary data such as motion vectors, block skipping flags, etc.

The macroblocks are written such that you can read from the bitstream continuously, and be certain that you are reading macroblocks for the current frame in the order top-left.. top-right.. bottom-left.. bottom-right. Due to this convention, there is no need for each macroblock to be written to the bitstream with an additional marker indicating such.

-h

[-h]

Oh and congrats on the ME sysKin :)

I only just found Alexis' paper on EPZS, I'd try finising up the implementation but it'd require quite a few changes in XviD to address the concerns Alexis mentioned on the forum a while back. There does seem to be quite a few nice features like predicting accelerated vectors, but still scant information on inter4v/bidirectional searching. What kind of method have you used to implement those, might I ask?

-h

[sysKin]

Originally posted by -h
Oh and congrats on the ME sysKin :)

I only just found Alexis' paper on EPZS, I'd try finising up the implementation but it'd require quite a few changes in XviD to address the concerns Alexis mentioned on the forum a while back. There does seem to be quite a few nice features like predicting accelerated vectors, but still scant information on inter4v/bidirectional searching. What kind of method have you used to implement those, might I ask?
First of all, 'my' motion estimation is basically normal PMV/EPZS. It was based on them and my main goal was to rewrite all the motion code simply because the old one became very ugly ;). I also made it because it was easier to implement some of my new ideas in new code than trying to 'bend' the old one. Just like with your EPZS.
The new ideas:
- skip-decision. The old code was substracting a bias from 0,0 motion vector's sad and that way, more macroblocks were encoded with 0,0 MV and - if we were lucky - were skipped. It wasn't effective imho. Some macroblocks couldn't be skipped for variuous reasons but they were still coded with not-effective 0,0 which was a waste of bits and quality. My code makes a simple check of 0,0's SAD and if it's low enough, does some extra checking and *makes* the macroblock skipped. No further ME/MC/DCT/etc ;) is done for it. Fast and efficient.
- new kind of inter4v search. For every check of 16x16 motion vector, four sads (of 8x8 blocks) are done and the data about smallest 8x8 sad are gathered. At the end of 16x16 search, we have full data about smallest 16x16 sad and MOST of the data needed for inter4v search. In fact, only a halfpel refinement of 8x8 blocks is needed - I also made the possibility of 'normal' diamond but the gain is as little as 0.005 (!) dB.
As a result, inter4v mode can be exactly as fast as non-inter4v or a bit (<2%) slower - with the same quality. Or 3% slower again with the same quality again ;) )
Overall, quality is a little bit higher at all motion precision levels while speed is faster with inter4v and a bit slower without inter4v. I'm still finding ways to optimize speed.

Some more info: The code size is 55kb with full B-frame and 'hinted me search' support. The old code (without the former thingy) was 107kb.
The resulting windows .dll is 331kb. The corresponding original library was 438kb.

As for bidirectional search modes, 3 different search procedures were created - one for direct mode (and also skip-check, working as before), one for forward/backward modes and one for interpolate. They all use the same diamond/advdiamond/square/halfpel-refinement 'infrastucture' as inter and inter4v, which simply made the code smaller and easier.
Direct search is a skip-check and a diamond starting in 0,0
Backward/Forward search is a 'lite' version of normal P-frame search, also using predictions from direct search.
Interpolate search is a 'special' diamond starting in the positions found by forward/backward search.

Dunno what else to say, just ask.
Oh, I just noticed how off-topic this mail is :p

Radek

[-h]

Oh, I just noticed how off-topic this mail is :p

Well the topic contains the word "XviD".. ah what the heck I'm a mod.

- skip-decision. The old code was substracting a bias from 0,0 motion vector's sad and that way, more macroblocks were encoded with 0,0 MV and - if we were lucky - were skipped. It wasn't effective imho. Some macroblocks couldn't be skipped for variuous reasons but they were still coded with not-effective 0,0 which was a waste of bits and quality. My code makes a simple check of 0,0's SAD and if it's low enough, does some extra checking and *makes* the macroblock skipped. No further ME/MC/DCT/etc ;) is done for it. Fast and efficient.

Have you considered storing the best non-0,0 MV in that case? It might be that some motion exists, but the 0,0 vector just happens to have a lower SAD on that occasion - the "true" motion vector would be a better spatial/temporal predictor. Ditto when a block is designated as intra - a vector over an intra-threshold is still a better spatial/temporal predictor than 0,0. This might cause some problems with variable usage though..

- new kind of inter4v search. For every check of 16x16 motion vector, four sads (of 8x8 blocks) are done and the data about smallest 8x8 sad are gathered. At the end of 16x16 search, we have full data about smallest 16x16 sad and MOST of the data needed for inter4v search. In fact, only a halfpel refinement of 8x8 blocks is needed - I also made the possibility of 'normal' diamond but the gain is as little as 0.005 (!) dB.

That is a nicer way, gathering inter4v stats during 16x16 SADs. How aggressive is the subsequent inter4v search? Could the 4 MVs differ from each other by > 8 or so pels, or do you only bother with those around the best 16x16? Heh I should just read the source ;)

I just recall Alexis mentioning some mammoth (>1.5 dB) gains when implementing a +-7 pel inter4v full search, though I'm not sure which vector that was around, or if it was around all candidates..

Some more info: The code size is 55kb with full B-frame and 'hinted me search' support. The old code (without the former thingy) was 107kb.

Yeah, that and the compiled size was one thing that concerned me about the old ME structure. It was getting to the stage where it'd be harmful to cache usage!

As for bidirectional search modes, 3 different search procedures were created - one for direct mode (and also skip-check, working as before), one for forward/backward modes and one for interpolate.

I was about to suggest something really stupid about a different P-frame search when B-frames are enabled, but luckily stopped myself.

I'll go check out the code & have a play.

-h

[sysKin]

Originally posted by -h

Have you considered storing the best non-0,0 MV in that case? It might be that some motion exists, but the 0,0 vector just happens to have a lower SAD on that occasion - the "true" motion vector would be a better spatial/temporal predictor. Ditto when a block is designated as intra - a vector over an intra-threshold is still a better spatial/temporal predictor than 0,0. This might cause some problems with variable usage though..

No, I don't store the real motion simply because I don't compute it. It's faster that way.
However, I already had a similar idea. I wanted to use it in hinted-me search, when I already have future macroblocks' motion vectors and modes. Can work. In the current hinted ME search, skip- and intra-decisions are copied from the first pass - and the quality is even higher then in full search, possibly because decisions are better with quant 2.
That is a nicer way, gathering inter4v stats during 16x16 SADs. How aggressive is the subsequent inter4v search? Could the 4 MVs differ from each other by > 8 or so pels, or do you only bother with those around the best 16x16?
Every check of 16x16 candidate - predictions, diamond, halfpel refinement, extsearch - is used for finding best sad8s of the 8x8 blocks. I don't limit anything. The only problem is that I only know a prediction of the first block, and only this block can have "+calc_delta_8" at this stage. It doesn't give me any problems, though.
The subsequent 8x8 search is 'by default' limited to halfpel refinement only. If one wants, the flag 'EXTSEARCH8' can be used to enable a diamond (advdiamond, square) starting in the best position found so far. However, the gain is absolutely minimal.
Heh I should just read the source ;)New version (newer then the one I posted in mailing list) is at http://users.bigpond.com/syskin/src3.zip .

I just recall Alexis mentioning some mammoth (>1.5 dB) gains when implementing a +-7 pel inter4v full search, though I'm not sure which vector that was around, or if it was around all candidates.. Really?? The gain of inter4v mode in xvid is about 0.2dB. Depends on the source movie of course (more for smaller resolution for instance) but 1.5dB?
However, inter/inter4v decision is still not perfect in xvid. Far from it.

[Defiler]

Thank you for this incredibly informative discussion. I learned a great deal.
For those reading the last five posts in the thread.. SAD stands for "Summation of Absolute Difference"
You can read about how it's used here:
MPEG-4 Motion Estimation (http://hellninjacommando.com/misc/docs/Motion%20Estimation.txt)
I yanked that from the MPEG-4 Overview PDF file.

[Wbtz]

Hi, need some advise. My sup's idea is to have prioritise the servers that are streaming the bits so that the low freq data from quantization (should be the DC value) are of higher priority and the AC ones are of lower priority. So in the event of lnefficiency most of the image are still restored. In case it slipped your mind, my project encompasses streaming of mpeg4 video from various servers. this, i hope, shld speed up streaming.

Some questions: other than after the both the DC and AC values that have been VLC-ed that are being written to the bitstream and motion vectors, what other info are written. Is there a standard way the stream is being written to? I think the difficult part would be to separate the DC values from the AC ones.:(

[-h]

Hi, need some advise. My sup's idea is to have prioritise the servers that are streaming the bits so that the low freq data from quantization (should be the DC value) are of higher priority and the AC ones are of lower priority. So in the event of lnefficiency most of the image are still restored. In case it slipped your mind, my project encompasses streaming of mpeg4 video from various servers. this, i hope, shld speed up streaming.

Ok. The biggest problem with this is that *every* frame after an I-frame depends on the previous frame. In the event that only DC coefficients were transmitted, yes you could re-create the *current* frame with some degree of efficacy, but every frame after that until the next I-frame would have extensive visual artifacts. Such is the nature of inter-frame compression.

I think you would be much more interested in MPEG-4's FGS profile for a thoroughly researched implementation of transmitting video information where some values may/must be discarded in transit. Unfortunately XviD does not implement this profile.

Some questions: other than after the both the DC and AC values that have been VLC-ed that are being written to the bitstream and motion vectors, what other info are written. Is there a standard way the stream is being written to? I think the difficult part would be to separate the DC values from the AC ones.:(

Quite a bit of ancillary data is written to the bitstream. For each macroblock, you have a single bit deciding whether or not the macroblock is stored at all (or just a copy of the previous frame), a code deciding what kind of macroblock it is (intra, inter, bidirectional, inter4v, etc.), how many of the 8x8 blocks are stored or skipped (cbp value), what the motion vector is in the case of an inter block, whether the macroblock utilizes interlacing tools such as the field-based DCT or field-based motion estimation, what form of AC prediction is used, which zig-zag scan direction is used, and some other values which I must have forgotten. Quite a bit, basically.

The biggest problem is that if *any* of the data is omitted, be it AC or cbp values, you will have extremely visible artifacts on *every frame* until you reach another I-frame. That is an unfortunate fact, but one that is partially addressed by the FGS system. You will have to turn to MoMuSys or MSFDAM for implementations of this, however.

-h

[Wbtz]

Oh no! This is bad news.... MoMuSys and the other is not GNU or open source right?

About FGS, are there any othere codecs that have implemented this? Does wavelet transform have anything to do with FGS? Is wavelet transform compliant with MPEG-4? Any reference I can look up for fgs? Been studying xvid so much, it would be a shame!

Unclear about why there will be artifacts. I know that the B and P frames will be dependent on other frames but doesnt motion estimation take this into account? Why would there still be artifacts?

[-h]

Oh no! This is bad news.... MoMuSys and the other is not GNU or open source right?

The software I mentioned are distributed with source code, and the only realy condition in their license is that whatever you modify the code into, it must be MPEG-4 compatible. Most commercial MPEG-4 implementations are most likely just modifications of MoMuSys.

About FGS, are there any othere codecs that have implemented this? Does wavelet transform have anything to do with FGS? Is wavelet transform compliant with MPEG-4? Any reference I can look up for fgs? Been studying xvid so much, it would be a shame!

None others that I know of. The MPEG-4 verification model is probably your best bet for information - http://mpeg.telecomitalialab.com/working_documents/mpeg-04/visual/video_vm.zip . It is a long read though.

Unclear about why there will be artifacts. I know that the B and P frames will be dependent on other frames but doesnt motion estimation take this into account? Why would there still be artifacts?

Well, motion estimation consists of copying a block from a reference frame to the current one, and storing the difference from what it should be. If the block you copy to the current frame happens to be corrupt (because we didn't transmit some values that were needed), it will look like garbage, and even after we apply the stored difference, it will still look like garbage. Then, if we copy that block to the next frame, even more will look like garbage, etc. The decoder won't know how to correct the garbage, because it doesn't have enough data.

-h

[Wbtz]

Once again thanks -h!

Do you have any idea if prioritizing is possible if i continue to look at xvid?

If not, seriously, would it be easy to modify the mbcoding such that i can write each frame individually to be streamed?

I have been to momusys website but cant really find the software package you mentioned. I suppose its there but its in a secured location...

Looks like I am stranded!

[-h]

Do you have any idea if prioritizing is possible if i continue to look at xvid?

I'm not sure what you mean.

If not, seriously, would it be easy to modify the mbcoding such that i can write each frame individually to be streamed?

Each frame is already written individually, they're returned 1 at a time through the API.

I have been to momusys website but cant really find the software package you mentioned. I suppose its there but its in a secured location...

Several versions of the software is available at http://megaera.ee.nctu.edu.tw/mpeg/ . I don't know much about the code itself, however.

I think you might be best off investigating B-frame usage. Since they are not needed during decoding (they can be skipped since no frame is allowed to reference a B-frame), if your bandwidth drops you can just not send the B-frames. Playback will be jerky, but fully functional. When bandwidth increases again, you can start sending some or all of the B-frames for smoother playback. Using 2 B-frames per P-frame could give you a stream where 2% of the bits are used by I-frames, 50% used by P-frames and 48% used by B-frames. Thus, if you have to you can send only half the bits to the client by skipping the B-frames.

-h

[standard]

- skip-decision. The old code was substracting a bias from 0,0 motion vector's sad and that way, more macroblocks were encoded with 0,0 MV and - if we were lucky - were skipped. It wasn't effective imho. Some macroblocks couldn't be skipped for variuous reasons but they were still coded with not-effective 0,0 which was a waste of bits and quality. My code makes a simple check of 0,0's SAD and if it's low enough, does some extra checking and *makes* the macroblock skipped. No further ME/MC/DCT/etc is done for it. Fast and efficient.

hi,
a question from a newbie:
is that the effect that we can see with Divx5 and even stronger with Nandub Divx3, when the camera pans over a scene and macroblocks are kept when the difference in brightness and/or color is very small?
if that is the case, it would give Xvid a real boost in my opinion, because i think it distributes (or even wastes) bits in some areas where is no change at all. in some cases it looks jerkily compared to the source.

sorry for my bad english.

[Wbtz]

Hey -h,

Think the skipping of the B-frames may be possible. Will have to explore more in this area. Lets say the B -frames are skipped. Will the original decoder still be able to decode the I and P frames without the B frames? Or does it need to modified to realise this skipping? In the encoder, where can i trap the writting of the frames and its auxilliary information to the bitstream? I think its time I did some "real" work!:p

[-h]

Lets say the B -frames are skipped. Will the original decoder still be able to decode the I and P frames without the B frames?

Yes, I and P-frames are all that are needed for decoding a stream, B-frames are really just "fill-in-the-blank" frames that can be skipped without breaking the decoding of any other frames.

Or does it need to modified to realise this skipping?

This may be a problem. I'm not sure what would happen if you just neglected to call the decoder altogether (i.e. if you haven't got a B-frame transferred soon enough, just don't bother calling xvid_decore()).. I dare say it would happily continue as normal when the next I or P-frame was delivered. This must be tested of course, I'm just guessing.

In the encoder, where can i trap the writting of the frames and its auxilliary information to the bitstream? I think its time I did some "real" work!:p

Which frames? The B-frames are the output of the encoder_encode_bframes() function in encoder.c, a rather large and slightly worrying function that manages the caching and timestamps involved in B-frame encoding. I have not studied XviD's method of re-ordering and encoding B-frames, so if you want to understand it, you'll have quite a bit of code to look through :)

Currently, the dev-api-3 branch of xvidcore contains sysKin's new variable B-frame insertion method which lets the codec decide when to use a P-frame, and when to use a string of 1, 2, 3 or even 12 consecutive B-frames. You would probably be interested in writing as many B-frames as possible, to decrease the amount of "critical" information that needs to get to the recipient (I and P-frames).

-h

[sysKin]

Originally posted by standard
is that the effect that we can see with Divx5 and even stronger with Nandub Divx3, when the camera pans over a scene and macroblocks are kept when the difference in brightness and/or color is very small?
Yes, that happens because the macroblocks are skipped.if that is the case, it would give Xvid a real boost in my opinion, because i think it distributes (or even wastes) bits in some areas where is no change at all. in some cases it looks jerkily compared to the source.You mean you actually LIKE the artifacts? I hate them. However, if you feel that XviD can skip more blocks, just compile your own xvid ;) My code is only available in development CVS. In motion_est.c file, there are two constants. First is INITIAL_SKIP_THRESH and it defines when macroblock is skipped outright (after first check). If you increase it, you'll get more macroblocks skipped and it will also make the encoding faster. Second constant is MAX_SAD00_FOR_SKIP and it defines a maximum error when skipping is still possible - but 'skipped' error will be compared to 'motion estimated' error and macroblock will only be skipped if motion estimation didn't really find anything better (much better).
Go on and play :)

As for possible gain - don't expect too much. Not-skipped macroblock which has it's motion vector equal to prediction and no other data will take 6 bits, skipped will take one. That's a lot if you think of disabling skip but not much if you want to skip more.

Radek

[Teegedeck]

Sorry for being OT, sysKin, but I find uManiac's builds dating past the 18th have an excessive appetite for physical memory - they won't run on my machine. Could it be the new ME? Or more likely uManiac's instant builds screwing up?

[-h]

Sorry for being OT, sysKin, but I find uManiac's builds dating past the 18th have an excessive appetite for physical memory - they won't run on my machine. Could it be the new ME? Or more likely uManiac's instant builds screwing up?

Do you know if uManiac is turning on BFRAMES in vfw? I had a similar problem until I did that. I think. Can't remember actually.

But yes I saw the memory skyrocket as well. It was probably the encoder busily allocating space for 2^31 B-frames :)

-h

[Teegedeck]

Hello -h,

it's been a long time. :)

According to the changelog, B-frames are defined by default. They are greyed-out in the config-tab, though, but I don't think that means a lot, does it?

BTW, it's so nice to see you guys hard at work again, thanks a lot!

[easyfab]

I think you can try b-frames with the debug version.
I don't test with the newer versions but in the past is was so.

[-h]

According to the changelog, B-frames are defined by default. They are greyed-out in the config-tab, though, but I don't think that means a lot, does it?

Yep, if they're greyed out then BFRAMES hasn't been defined in the project settings. That'd be the culprit.

BTW, it's so nice to see you guys hard at work again, thanks a lot!

There's a lot more coming :)

-h

[Wbtz]

Which frames? The B-frames are the output of the encoder_encode_bframes() function in encoder.c, a rather large and slightly worrying function that manages the caching and timestamps involved in B-frame encoding. I have not studied XviD's method of re-ordering and encoding B-frames, so if you want to understand it, you'll have quite a bit of code to look through :)


Yeah I suppose its inevitable. So all the writting of the I, P and B frames are done through encoder.c? I will first try and write each individual frame to a file first. Anything to look out for?

Oh a stupid question: Lets say I edited the code, how do I actually use the edited code to test and debug on a video file ie to actually see if it writes to the different files that i specified as in practically? Using tmpEnc and stuff?:confused: <--Sorry, I think its trivial but I really have no idea! (Perhaps its the same way as the original encoder is to be used?)

[-h]

Yeah I suppose its inevitable. So all the writting of the I, P and B frames are done through encoder.c? I will first try and write each individual frame to a file first. Anything to look out for?

Well you won't have to change too much actually. Or even look at much code.

What you want to do is just write the output of the encoder to one file per frame, instead of one file for all frames (like an AVI). This isn't too difficult if you build on the existing CVS example code. I could probably write a mock program that does this with B-frames in the correct order in 10 or so minutes. Of course eventually you would want all these frames to go into a single file that could be intelligently served up.

The hardest thing you are going to have to do is code something that intelligently skips B-frames that would normally be sent to the recipient, but won't due to network congestion / lack of speed. I have no real suggestions for that.

You might want to investigate ffmpeg - it too supports MPEG-4 with B-frames, but has been written from the ground up as a platform for encoding video on one machine and serving it on another - I'd be surprised if it didn't have some kind of governed network behaviour. You might want to drop an email to their mailing list (though responses seem rare).

Oh a stupid question: Lets say I edited the code, how do I actually use the edited code to test and debug on a video file ie to actually see if it writes to the different files that i specified as in practically? Using tmpEnc and stuff?:confused: <--Sorry, I think its trivial but I really have no idea! (Perhaps its the same way as the original encoder is to be used?)

You would be better off building a command-line program that calls xvidcore but reads/writes files that you specify at run-time. Just such a program is xvid_stat, which is in the examples directory on one of the cvs branches.

-h

[Wbtz]

What you want to do is just write the output of the encoder to one file per frame, instead of one file for all frames (like an AVI). This isn't too difficult if you build on the existing CVS example code. I could probably write a mock program that does this with B-frames in the correct order in 10 or so minutes.

10mins? Haha..I will probably take a month! To give me a headstart, will I be dealing with encoder.c only or must I modify the bitstream files too because I cant really understand where the writting takes place. Btw, are each frame identified with a number or some header info?

Of course eventually you would want all these frames to go into a single file that could be intelligently served up.


What is the reason for this? My idea was to have all the frames as different files and all the files on mirror servers. Each server will send each file whenever needed. Eg server1 send 1st frames, 2 sends second, 3 sends third etc. Not sure if its a theoretically feasible idea though

[sysKin]

Originally posted by Teegedeck
Sorry for being OT, sysKin, but I find uManiac's builds dating past the 18th have an excessive appetite for physical memory - they won't run on my machine. Could it be the new ME? Or more likely uManiac's instant builds screwing up?
No, that's not my code ;). My code was uploaded to CVS on 24th of September. It's only available in development (api version 3) branch and it's not supposed to be available by means of 'instant builds'.

If you download any new build, you can tell if it's new code by checking xvid.dll filesize - it's down to about 330kb with new ME.

[-h]

10mins? Haha..I will probably take a month! To give me a headstart, will I be dealing with encoder.c only or must I modify the bitstream files too because I cant really understand where the writting takes place. Btw, are each frame identified with a number or some header info?

Frames are written in the MBCoding() function, but only to memory. The core just fills an array passed by the calling application, which is then responsible for writing it to disk / whatever. You shouldn't have to alter anything.

Frames don't have any header info, but the encoder keeps track of the current frame number, which I guess you could write to a file if you wanted.

What is the reason for this? My idea was to have all the frames as different files and all the files on mirror servers. Each server will send each file whenever needed. Eg server1 send 1st frames, 2 sends second, 3 sends third etc. Not sure if its a theoretically feasible idea though

There will just be less overhead. Moving a single 100 MB file from one server to another will be faster than moving 100,000 thousand-byte files. There are other reasons but it is very early at the moment.

-h

[Wbtz]

Ok, so mbcoding.c does not do the writing. It is a calling program that does this. Is this calling program a program that I need to write or can i execute it from the xvid_stat thing because I am not familiar with this. This means I can leave the whole source code of xvid alone? I am getting confused(I just do not have the programming brains!)

[-h]

Ok, so mbcoding.c does not do the writing. It is a calling program that does this. Is this calling program a program that I need to write or can i execute it from the xvid_stat thing because I am not familiar with this. This means I can leave the whole source code of xvid alone? I am getting confused(I just do not have the programming brains!)

Xvid_stat will do this. I'm not sure whether it supports multiple input frames yet though, it's only an example of calling xvidcore and saving the output.

-h