My Technical Articles . . . ...

Optimization -05

2010-11-23T09:07:00.004+05:30

Tips for Optimizing C++ Code

12. Careful when declaring C++ object variables.

Use initialization instead of assignment (Color c(black); is faster than Color c; c = black;).

13. Make default class constructors as lightweight as possible.

Particularly for simple, frequently used classes (e.g., color, vector, point, etc.) that are manipulated frequently.

These default constructors are often called behind your back, where you are not expecting it.

Use constructor initializer lists. (Use Color::Color() : r(0), g(0), b(0) {} rather than Color::Color() { r = g = b = 0; } .)

16. For most classes, use the operators +=, -=, *=, and /=, instead of the operators +, -, *, and /.

The simple operations need to create an unnamed, temporary intermediate object.

For instance: Vector v = Vector(1,0,0) + Vector(0,1,0) + Vector(0,0,1); creates five unnamed, temporary Vectors: Vector(1,0,0), Vector(0,1,0), Vector(0,0,1), Vector(1,0,0) + Vector(0,1,0), and Vector(1,0,0) + Vector(0,1,0) + Vector(0,0,1).

The slightly more verbose code: Vector v(1,0,0); v+= Vector(0,1,0); v+= Vector(0,0,1); only creates two temporary Vectors: Vector(0,1,0) and Vector(0,0,1). This saves 6 functions calls (3 constructors and 3 destructors).

18. Delay declaring local variables.

Declaring object variable always involves a function call (to the constructor).

If a variable is only needed sometimes (e.g., inside an if statement) only declare when necessary, so the constructor is only called if the variable will be used.

19. For objects, use the prefix operator (++obj) instead of the postfix operator (obj++).

This probably will not be an issue in your ray tracer.

A copy of the object must be made with the postfix operator (which thus involves an extra call the the constructor and destructor), whereas the prefix operator does not need a temporary copy.

20. Careful using templates.

Optimizations for various instantiations may need to be different!

The standard template library is reasonably well optimized, but I would avoid using it if you plan to implement an interactive ray tracer.

Why? By implementing it yourself, you'll know the algorithms it uses, so you will know the most efficient way to use the code.

More importantly, my experience is that debug compiles of STL libraries are slow. Normally this isn't a problem, except you will be using debug versions for profiling. You'll find STL constructors, iterators, etc. use 15+% of your run time, which can make reading the profile output more confusing.

.

Optimization -04

2010-11-23T08:53:00.006+05:30

Tips for Optimizing C Code

1. Remember Ahmdal's Law:

Where func_cost is the percentage of the program runtime used by the function func, and func_speedup is the factor by which you speedup the function.

Thus, if you optimize the function func(), which is 40% of the runtime, so that it runs twice as fast, your program will run 25% faster .

This means infrequently used code (e.g., the scene loader) probably should be optimized little (if at all).

2. First Code for correctness, then optimize!

This does not mean write a fully functional ray tracer for 8 weeks, then optimize for 8 weeks!

Perform optimizations on your ray tracer in multiple steps.

Write for correctness, and then if you know the function will be called frequently, perform obvious optimizations.

Then profile to find bottlenecks, and remove the bottlenecks (by optimization or by improving the algorithm). Often improving the algorithm drastically changes the bottleneck – perhaps to a function you might not expect. This is a good reason to perform obvious optimizations on all functions you know will be frequently used.

3. People I know who write very efficient code say- they spend at least twice as long optimizing code as they spend writing code.

4. Jumps/branches are expensive. Minimize their use whenever possible.

Function calls require two jumps, in addition to stack memory manipulation.

Prefer iteration over recursion.

Use inline functions for short functions to eliminate function overhead.

Move loops inside function calls

e.g., change for(i=0;i<100;i++){ ... } DoSomething();

into DoSomething() { for(i=0;i<100;i++) { ... } } .

Long if...else if...else if...else if... chains require lots of jumps for cases near the end of the chain (in addition to testing each condition). If possible, convert to a switch statement, which the compiler sometimes optimizes into a table lookup with a single jump. If a switch statement is not possible, put the most common clauses at the beginning of the if chain.

5. Think about the order of array indices.

Two and higher dimensional arrays are still stored in one dimensional memory. This means (for C/C++ arrays) array[i][j] and array[i][j+1] are adjacent to each other, whereas array[i][j] and array[i+1][j] may be arbitrarily far apart.

Accessing data in a more-or-less sequential fashion, as stored in physical memory, can dramatically speed up your code (sometimes by an order of magnitude, or more)!

When modern CPUs load data from main memory into processor cache, they fetch more than a single value. Instead they fetch a block of memory containing the requested data and adjacent data (a cache line). This means after array[i][j] is in the CPU cache, array[i][j+1] has a good chance of already being in cache, whereas array[i+1][j] is likely to still be in main memory.

6. Think about instruction-level-parallelism.

Even though many applications still rely on single threaded execution, modern CPUs already have a significant amount of parallelism inside a single core. This means a single CPU might be simultaneously executing 4 floating point multiplies, waiting for 4 memory requests, and performing a comparison for an upcoming branch.

To make the most of this parallelism, blocks of code (i.e., between jumps) need to have enough independent instructions to allow the CPU to be fully utilized.

Think about unrolling loops to improve this.

This is also a good reason to use inline functions.

7. Avoid/reduce the number of local variables.

Local variables are normally stored on the stack. However if there are few enough, they can instead be stored in registers. In this case, the function not only gets the benefit of the faster memory access of data stored in registers, but the function avoids the overhead of setting up a stack frame.

(Do not, however, switch wholesale to global variables!)

8. Reduce the number of function parameters.

For the same reason as reducing local variables – they are also stored on the stack.

9. Pass structures by reference, not by value.

I know of no case in a ray tracer where structures should be passed by value (even simple ones like Vectors, Points, and Colors).

10. If you do not need a return value from a function, do not define one.

11. Try to avoid casting where possible.

Integer and floating point instructions often operate on different registers, so a cast requires a copy.

Shorter integer types (char and short) still require the use of a full-sized register, and they need to be padded to 32/64-bits and then converted back to the smaller size before storing back in memory. (However, this cost must be weighed against the additional memory cost of a larger data type.)

12. Careful when declaring C variables.

Use initialization instead of assignment (Color c = black); is faster than Color c; c = black ;).

14. Use shift operations >> and << instead of integer multiplication and division, where possible.

15. Careful using table-lookup functions.

Many people encourage using tables of precomputed values for complex functions (e.g., trigonometric functions). For ray tracing, this is often unnecessary. Memory lookups are exceedingly (and increasingly) expensive, and it is often as fast to recompute a trigonometric function as it is to retrieve the value from memory (especially when you consider the trig lookup pollutes the CPU cache).

In other instances, lookup tables may be quite useful. For GPU programming, table lookups are often preferred for complex functions.

17. For basic data types, use the operators +, -, *, and / instead of the operators +=, -=, *=, and /=.

21. Avoid dynamic memory allocation during computation.

Dynamic memory is great for storing the scene and other data that does not change during computation.

However, on many (most) systems dynamic memory allocation requires the use of locks to control an access to the allocator. For multi-threaded applications that use dynamic memory, you may actually get a slowdown by adding additional processors, due to the wait to allocate and free memory!

Even for single threaded applications, allocating memory on the heap is more expensive than adding it on the stack. The operating system needs to perform some computation to find a memory block of the requisite size.

22. Find and utilize information about your system's memory cache.

If a data structure fits in a single cache line, only a single fetch from main memory is required to process the entire class.

Make sure all data structures are aligned to cache line boundaries. (If both your data structure and a cache line are 128 bytes, you will still have poor performance if 1 byte of your structure is in once cache line and the other 127 bytes are in a second cache line).

23. Avoid unnecessary data initialization.

If you must initialize a large chunk of memory, consider using memset().

24. Try to early loop termination and early function returns.

Consider intersecting a ray and a triangle. The "common case" is that the ray will miss the triangle. Thus, this should be optimized for.

If you decide to intersect the ray with the triangle plane, you can immediately return if the t value ray-plane intersection is negative. This allows you to skip the barycentric coordinate computation in roughly half of the ray-triangle intersections. A big win! As soon as you know no intersection occurs, the intersection function should quit.

Similarly, some loops can be terminated early. For instance, when shooting shadow rays, the location of the nearest intersection is unnecessary. As soon as any occluding intersection is found, the intersection routine can return.

25. Simplify your equations on paper!

In many equations, terms cancel out... either always or in some special cases.

The compiler cannot find these simplifications, but you can. Eliminating a few expensive operations inside an inner loop can speed your program more than days working on other parts.

26. The difference between math on integers, fixed points, 32-bit floats, and 64-bit doubles is not as big as you might think.

On modern CPUs, floating-point operations have essentially the same throughput as integer operations. In compute-intensive programs like ray tracing, this leads to a negligible difference between integer and floating-point costs. This means, you should not go out of your way to use integer operations.

Double precision floating-point operations may not be slower than single precision floats, particularly on 64-bit machines. I have seen ray tracers run faster using all doubles than all floats on the same machine. I have also seen the reverse.

27. Consider ways of rephrasing your math to eliminate expensive operations.

sqrt() can often be avoided, especially in comparisons where comparing the value squared gives the same result.

If you repeatedly divide by x, consider computing 1/x and multiplying by the result. This used to be a big win for vector normalizations (3 divides), but I've recently found it's now a toss-up. However, it should still be beneficial if you do more than 3 divides.

If you perform a loop, make sure computations that do not change between iterations are pulled out of the loop.

Consider if you can compute values in a loop incrementally (instead of computing from scratch each iteration).

.

Socket Programming -01

2010-11-15T23:27:00.011+05:30

Socket Programming - Server (Rx)

#define WIN32_LEAN_AND_MEAN

#include <windows.h>

#include <winsock2.h>

#include <ws2tcpip.h>

#include <stdlib.h>

#include <stdio.h>

#include <conio.h>

// Need to link with Ws2_32.lib, Mswsock.lib, and Advapi32.lib

#pragma comment (lib, "Ws2_32.lib")

#pragma comment (lib, "Mswsock.lib")

#pragma comment (lib, "AdvApi32.lib")

#define DEFAULT_BUFLEN 1452

#define DEFAULT_PORT "27015"

int main (void)

{

WSADATA wsaData;

FILE *fp;

SOCKET ListenSocket = INVALID_SOCKET, ClientSocket = INVALID_SOCKET;

struct addrinfo *result = NULL, hints;

char recvbuf[DEFAULT_BUFLEN];

int iResult, iSendResult;

int recvbuflen = DEFAULT_BUFLEN;

fp = fopen("receive.dat","wb");

// Initialize Winsock

iResult = WSAStartup(MAKEWORD(2,2), &wsaData);

if (iResult != 0) {

printf("WSAStartup failed with error: %d\n", iResult);

return 1;

}

ZeroMemory(&hints, sizeof(hints));

hints.ai_family = AF_INET;

hints.ai_socktype = SOCK_STREAM;

hints.ai_protocol = IPPROTO_TCP;

hints.ai_flags = AI_PASSIVE;

// Resolve the server address and port

iResult = getaddrinfo(NULL, DEFAULT_PORT, &hints, &result);

if ( iResult != 0 ) {

printf("getaddrinfo failed with error: %d\n", iResult);

WSACleanup();

return 1;

}

// Create a SOCKET for connecting to server

ListenSocket = socket(result->ai_family, result->ai_socktype, result->ai_protocol);

if (ListenSocket == INVALID_SOCKET) {

printf("socket failed with error: %ld\n", WSAGetLastError());

freeaddrinfo(result);

WSACleanup();

return 1;

}

// Setup the TCP listening socket

iResult = bind( ListenSocket, result->ai_addr, (int)result->ai_addrlen);

if (iResult == SOCKET_ERROR) {

printf("bind failed with error: %d\n", WSAGetLastError());

closesocket(ListenSocket);

WSACleanup();

return 1;

}

freeaddrinfo(result);

iResult = listen(ListenSocket, SOMAXCONN);

if (iResult == SOCKET_ERROR) {

printf("listen failed with error: %d\n", WSAGetLastError());

closesocket(ListenSocket);

WSACleanup();

return 1;

}

// Accept a client socket

ClientSocket = accept(ListenSocket, NULL, NULL);

if (ClientSocket == INVALID_SOCKET) {

printf("accept failed with error: %d\n", WSAGetLastError());

closesocket(ListenSocket);

WSACleanup();

return 1;

}

// No longer need server socket

closesocket(ListenSocket);

// Receive until the peer shuts down the connection

do {

iResult = recv(ClientSocket, recvbuf, recvbuflen, 0);

if (iResult > 0) {

printf("Bytes received: %d\n", iResult);

// Echo the buffer back to the sender

iSendResult = send( ClientSocket, recvbuf, iResult, 0 );

if (iSendResult == SOCKET_ERROR) {

printf("send failed with error: %d\n", WSAGetLastError());

closesocket(ClientSocket);

WSACleanup();

return 1;

}

printf("Bytes sent: %d\n", iSendResult);

}

else
if (iResult == 0)

printf("Connection closing...\n");

else {

printf("recv failed with error: %d\n", WSAGetLastError());

closesocket(ClientSocket);

WSACleanup();

return 1;

}

} while (iResult > 0);

// shutdown the connection since we're done

iResult = shutdown(ClientSocket, SD_SEND);

if (iResult == SOCKET_ERROR) {

printf("shutdown failed with error: %d\n", WSAGetLastError());

closesocket(ClientSocket);

WSACleanup();

return 1;

}

// cleanup

closesocket(ClientSocket);

WSACleanup();

fclose(fp);

printf("Sucessfully Received Data...\n");

return 0;

}

Matlab - 01

2010-11-09T08:44:00.004+05:30

Working with Videos in MATLAB

MATLAB supports only "raw" (uncompressed) avi files on Linux and only some Indeo and Cinepack compressed versions on Windows. But mostly we get videos in MPEG. So we need to convert to raw or any supported format. For this, FFmpeg can be used.

AVI means Audio Video Interleave and is only a container format. AVI does not mean raw video. It is possible to have mpeg or many other compressed avi files. MATLAB cannot read such a compressed avi files. (See http://en.wikipedia.org/wiki/Audio_Video_Interleave).

1. Section: If we have raw video (or supported format)

If we have raw video, then handling in MATLAB is quite easy. We need to use functions mmreader, read, movie, mmfileinfo, frame2im, im2frame, aviread, avifile, aviinfo, addframe (avifile), close (avifile), movie2avi functions. Following code reads and plays back a given video. For further details and other functions see MATLAB help.

%Reads and plays back the movie file xylophone.mpg.

xyloObj = mmreader('xylophone.mpg');

nFrames = xyloObj.NumberOfFrames;

vidHeight = xyloObj.Height;

vidWidth = xyloObj.Width;

% Preallocate movie structure.

mov(1:nFrames) = struct('cdata', zeros(vidHeight, vidWidth, 3, 'uint8'),
'colormap', []);

% Read one frame at a time.

for k = 1 : nFrames

mov(k).cdata = read(xyloObj, k);

end

% Size a figure based on the video's width and height.

hf = figure;

set(hf, 'position', [150 150 vidWidth vidHeight])

% Play back the movie once at the video's frame rate.

movie(hf, mov, 1, xyloObj.FrameRate);

2. Section: If we have not supported video format

We can use any converter tool to convert compressed video to uncompressed avi format. One such tool is FFmpeg (http://ffmpeg.mplayerhq.hu/index.html). Mplayer, VLC and many other players are based on this codec.

If you are a Windows user, just download latest binary from http://ffdshow.faireal.net/mirror/ffmpeg/ (Any virus? I don't know. Download at your risk!). (You can use WinRAR to uncompress .7z - http://www.freedownloadscenter.com/Utilities/Compression_and_Zip_File_Utilities/WinRAR_Download.html )

Use this command to convert any compressed file (compressed.any) to uncompressed avi file (uncompressed.avi) (Note: pthreadGC2.dll file should be in the same directory as ffmpeg.exe).

ffmpeg.exe -i compressed.any -vcodec rawvideo uncompressed.avi

This should work most of the cases. However, sometimes it may not work (because, avi is a container format by Microsoft! :)). The converted video may have only blank frames or MATLAB may not be able to read it properly. In such a case, you can try steps explained in Section 3.

3. Section: If Section 2 does not work

Create a folder by name "images". Use this command to convert each frame of the compressed video to bmp (or ppm, jpg) images using ffmpeg or virtualDub and put it into the folder "images".

ffmpeg.exe -i compressed.any images/image_%d.bmp

Now you can use these images for processing. If you want uncompressed avi file, then use following MATLAB code to combine all raw images into a single uncompressed avi file.

%Script file to combine images to an uncompressed avi file

%Directory that contains images

in_dir = 'D:\temp\ffmpeg.rev11870\images\';

fout = 'D:\out.avi'; %Output file name

num_images = 341; %Number of images

%Set a suitable frame rate fps

aviobj = avifile(fout, 'compression', 'none', 'fps', 25);

for i = 1:num_images;

temp = sprintf('%d', i);

name = [in_dir, 'image_', temp, '.bmp']; %For ppm, change

img = imread(name);

frm = im2frame(img);

aviobj = addframe(aviobj,frm);

end;

aviobj = close(aviobj);

4. Useful Functions

mmreader, read, movie, mmfileinfo, frame2im, im2frame, aviread, avifile, aviinfo, addframe (avifile), close (avifile), movie2avi

5. Supported File Formats

Platform		Supported File Formats
Windows		AVI (.avi), MPEG-1 (.mpg), Motion JPEG 2000 (.mj2), Windows Media Video (.wmv, .asf, .asx), and any format supported by Microsoft DirectShow.
Macintosh		AVI (.avi), MPEG-1 (.mpg), MPEG-4 (.mp4, .m4v), Motion JPEG 2000 (.mj2), Apple QuickTime Movie (.mov), and any format supported by QuickTime as listed on http://www.apple.com/quicktime/player/specs.html.
Linux		Motion JPEG 2000 (.mj2), Any format supported by your installed plug-ins for GStreamer 0.10 or above, as listed on http://gstreamer.freedesktop.org/documentation/plugins.html, including AVI (.avi) and Ogg Theora (.ogg).

OpenCV – 02

2010-11-08T17:03:00.016+05:30

Working with Videos in OpenCV

#include <stdio.h>
#include <cv.h>
#include <highgui.h>

int main(void)

{
   /* Create an object that decodes the input video stream. */
   CvCapture *input_video = cvCaptureFromFile("VideoPlay_Demo.avi");
   if (input_video == NULL)
   {
   /* Either the video didn't exist OR codec doesn't support */
   fprintf(stderr, "Error: Can't open video.\n");
   return -1;
   }

   /* Read the video's frame size out of the AVI. */
   CvSize frame_size;
   frame_size.height = (int) cvGetCaptureProperty(input_video, CV_CAP_PROP_FRAME_HEIGHT);
   frame_size.width = (int) cvGetCaptureProperty(input_video, CV_CAP_PROP_FRAME_WIDTH);

   /* Determine the number of frames in the AVI. */
   long number_of_frames;
   number_of_frames = (int) cvGetCaptureProperty(input_video, CV_CAP_PROP_FRAME_COUNT);

   /* Create a windows called "VideoPlay_Demo" for output.
   * window automatically change its size to match the output. */
   cvNamedWindow("VideoPlay_Demo", CV_WINDOW_AUTOSIZE);

   long current_frame = 0;
   while(true)
   {
   static IplImage *frame = NULL;

   /* Go to the frame we want */
   cvSetCaptureProperty( input_video, CV_CAP_PROP_POS_FRAMES, current_frame );

   /* Get the next frame of the video */
   frame = cvQueryFrame( input_video );
   if (frame == NULL)
   {
   fprintf(stderr, "Error: Hmm. The end came sooner than we thought.\n");
   return -1;
   }

   /* Now display the image */
   cvShowImage("VideoPlay_Demo", frame);

   /* And wait for. If the argument is 0 then it waits forever otherwise it waits that number of milliseconds */
   cvWaitKey(60);
   current_frame++;
   if (current_frame < 0)
   current_frame = 0;
   if (current_frame >= number_of_frames - 1)
   current_frame = number_of_frames - 2;
   }
}

.

Audio Codec – MP3 –ID3v2.3

2010-10-25T20:05:00.003+05:30

MP3 Codec - ID3 tag version 2.3.0

ID3v2 Overview

The two biggest design goals were to be able to implement ID3v2 without disturbing old software too much and that ID3v2 should be as flexible and expandable as possible.

The first criterion is met by the simple fact that the MPEG decoding software uses a syncsignal, embedded in the audiostream, to 'lock on to' the audio. Since the ID3v2 tag doesn't contain a valid syncsignal, no software will attempt to play the tag. If, for any reason, coincidence make a syncsignal appear within the tag it will be taken care of by the 'unsynchronisation scheme'.

The second criterion has made a more noticeable impact on the design of the ID3v2 tag. It is constructed as a container for several information blocks, called frames, whose format need not be known to the software that encounters them. At the start of every frame there is an identifier that explains the frames' format and content, and a size descriptor that allows software to skip unknown frames.

If a total revision of the ID3v2 tag should be needed, there is a version number and a size descriptor in the ID3v2 header.

The ID3 tag described in this document is mainly targeted at files encoded with MPEG-1/2 layer I, MPEG-1/2 layer II, MPEG-1/2 layer III and MPEG-2.5, but may work with other types of encoded audio.

The bitorder in ID3v2 is most significant bit first (MSB). The byteorder in multibyte numbers is most significant byte first (e.g. $12345678 would be encoded $12 34 56 78).

It is permitted to include padding after all the final frame (at the end of the ID3 tag), making the size of all the frames together smaller than the size given in the head of the tag. A possible purpose of this padding is to allow for adding a few additional frames or enlarge existing frames within the tag without having to rewrite the entire file. The value of the padding bytes must be $00.

ID3v2 header

The ID3v2 tag header, which should be the first information in the file, is 10 bytes as follows:

ID3v2/file identifier	"ID3"
ID3v2 version	$03 00
ID3v2 flags	%abc00000
ID3v2 size	4 * %0xxxxxxx

The first three bytes of the tag are always "ID3" to indicate that this is an ID3v2 tag, directly followed by the two version bytes. The first byte of ID3v2 version is it's major version, while the second byte is its revision number. In this case this is ID3v2.3.0. All revisions are backwards compatible while major versions are not. If software with ID3v2.2.0 and below support should encounter version three or higher it should simply ignore the whole tag. Version and revision will never be $FF.

The version is followed by one the ID3v2 flags field, of which currently only three flags are used.

a	- Unsynchronisation
	Bit 7 in the 'ID3v2 flags' indicates whether or not unsynchronisation is used; a set bit indicates usage.
b	- Extended header
	The second bit (bit 6) indicates whether or not the header is followed by an extended header.
c	- Experimental indicator
	The third bit (bit 5) should be used as an 'experimental indicator'. This flag should always be set when the tag is in an experimental stage.

All the other flags should be cleared. If one of these undefined flags are set that might mean that the tag is not readable for a parser that does not know the flags function.

The ID3v2 tag size is encoded with four bytes where the most significant bit (bit 7) is set to zero in every byte, making a total of 28 bits. The zeroed bits are ignored, so a 257 bytes long tag is represented as $00 00 02 01.

The ID3v2 tag size is the size of the complete tag after unsychronisation, including padding, excluding the header but not excluding the extended header (total tag size - 10). Only 28 bits (representing up to 256MB) are used in the size description to avoid the introducuction of 'false syncsignals'.

An ID3v2 tag can be detected with the following pattern:

$49 44 33 yy yy xx zz zz zz zz

Where yy is less than $FF, xx is the 'flags' byte and zz is less than $80.

ID3v2 extended header

The extended header contains information that is not vital to the correct parsing of the tag information; hence the extended header is optional.

Extended header size	$xx xx xx xx
Extended Flags	$xx xx
Size of padding	$xx xx xx xx

Where the 'Extended header size', currently 6 or 10 bytes, excludes itself. The 'Size of padding' is simply the total tag size excluding the frames and the headers, in other words the padding. The extended header is considered separate from the header proper, and as such is subject to unsynchronisation.

The extended flags are a secondary flag set which describes further attributes of the tag. These attributes are currently defined as follows:

	%x0000000 00000000
	x	- CRC data present
		If this flag is set four bytes of CRC-32 data is appended to the extended header. The CRC should be calculated before unsynchronisation on the data between the extended header and the padding, i.e. the frames and only the frames.
		Total frame CRC $xx xx xx xx

ID3v2 frame overview

As the tag consists of a tag header and a tag body with one or more frames, all the frames consists of a frame header followed by one or more fields containing the actual information. The layout of the frame header:

	Frame ID	$xx xx xx xx (four characters)
	Size	$xx xx xx xx
	Flags	$xx xx

The frame ID made out of the characters capital A-Z and 0-9. Identifiers beginning with "X", "Y" and "Z" are for experimental use and free for everyone to use, without the need to set the experimental bit in the tag header. Have in mind that someone else might have used the same identifier as you. All other identifiers are either used or reserved for future use.

The frame ID is followed by a size descriptor, making a total header size of ten bytes in every frame. The size is calculated as frame size excluding frame header (frame size - 10).

In the frame header the size descriptor is followed by two flags bytes.

There is no fixed order of the frames' appearance in the tag, although it is desired that the frames are arranged in order of significance concerning the recognition of the file. An example of such order: UFID, TIT2, MCDI, TRCK ...

A tag must contain at least one frame. A frame must be at least 1 byte big, excluding the header.

If nothing else is said a string is represented as ISO-8859-1 characters in the range $20 - $FF. Such strings are represented as <text string>, or <full text string> if newlines are allowed, in the frame descriptions. All Unicode strings use 16-bit unicode 2.0 (ISO/IEC 10646-1:1993, UCS-2). Unicode strings must begin with the Unicode BOM ($FF FE or $FE FF) to identify the byte order.

All numeric strings and URLs are always encoded as ISO-8859-1. Terminated strings are terminated with $00 if encoded with ISO-8859-1 and $00 00 if encoded as unicode. If nothing else is said newline character is forbidden. In ISO-8859-1 a new line is represented, when allowed, with $0A only. Frames that allow different types of text encoding have a text encoding description byte directly after the frame size. If ISO-8859-1 is used this byte should be $00, if Unicode is used it should be $01. Strings dependent on encoding is represented as <text string according to encoding>, or <full text string according to encoding> if newlines are allowed. Any empty Unicode strings which are NULL-terminated may have the Unicode BOM followed by a Unicode NULL ($FF FE 00 00 or $FE FF 00 00).

The three byte language field is used to describe the language of the frame's content, according to ISO-639-2.

All URLs may be relative, e.g. "picture.png", "../doc.txt".

If a frame is longer than it should be, e.g. having more fields than specified in this

document, that indicates that additions to the frame have been made in a later version of the ID3v2 standard. This is reflected by the revision number in the header of the tag.

4.1

Frame header flags

In the frame header the size descriptor is followed by two flags bytes. All unused flags must be cleared. The first byte is for 'status messages' and the second byte is for encoding purposes. If an unknown flag is set in the first byte the frame may not be changed without the bit cleared. If an unknown flag is set in the second byte it is likely to not be readable. The flags field is defined as follows.

%abc00000 %ijk00000
a	- Tag alter preservation
	This flag tells the software what to do with this frame if it is unknown and the tag is altered in any way. This applies to all kinds of alterations, including adding more padding and reordering the frames.
		0		- Frame should be preserved.
		1		- Frame should be discarded.
b	- File alter preservation
	This flag tells the software what to do with this frame if it is unknown and the file, excluding the tag, is altered. This does not apply when the audio is completely replaced with other audio data.
		0	- Frame should be preserved.
		1	- Frame should be discarded.
c	- Read only
	This flag, if set, tells the software that the contents of this frame is intended to be read only. Changing the contents might break something, e.g. a signature. If the contents are changed, without knowledge in why the frame was flagged read only and without taking the proper means to compensate, e.g. recalculating the signature, the bit should be cleared.
i	- Compression
	This flag indicates whether or not the frame is compressed.
		0	Frame is not compressed.
		1	Frame is compressed using [#ZLIB zlib] with 4 bytes for 'decompressed size' appended to the frame header.
j	- Encryption
	This flag indicates wether or not the frame is enrypted. If set one byte indicating with which method it was encrypted will be appended to the frame header.
		0	- Frame is not encrypted.
		1	- Frame is encrypted.
k	- Grouping identity
	This flag indicates whether or not this frame belongs in a group with other frames. If set a group identifier byte is added to the frame header. Every frame with the same group identifier belongs to the same group.
		0	- Frame does not contain group information
		1	- Frame contains group information

Some flags indicates that the frame header is extended with additional information. This information will be added to the frame header in the same order as the flags indicating the additions. I.e. the four bytes of decompressed size will preceed the encryption method byte. These additions to the frame header, while not included in the frame header size but are included in the 'frame size' field, are not subject to encryption or compression.

Default flags

The default settings for the frames described in this document can be divided into the following classes. The flags may be set differently if found more suitable by the software.

	Discarded if tag is altered, discarded if file is altered.
		None.
	Discarded if tag is altered, preserved if file is altered.
		None.
	Preserved if tag is altered, discarded if file is altered.
		AENC, ETCO, EQUA, MLLT, POSS, SYLT, SYTC, RVAD, TENC, TLEN, TSIZ
	Preserved if tag is altered, preserved if file is altered.
		The rest of the frames.

Declared ID3v2 frames

The following frames are declared in this draft.

	AENC	Audio encryption
	APIC	Attached picture
	COMM	Comments
	COMR	Commercial frame
	ENCR	Encryption method registration
	EQUA	Equalization
	ETCO	Event timing codes
	GEOB	General encapsulated object
	GRID	Group identification registration
	IPLS	Involved people list
	LINK	Linked information
	MCDI	Music CD identifier
	MLLT	MPEG location lookup table
	OWNE	Ownership frame
	PRIV	Private frame
	PCNT	Play counter
	POPM	Popularimeter
	POSS	Position synchronisation frame
	RBUF	Recommended buffer size
	RVAD	Relative volume adjustment
	RVRB	Reverb
	SYLT	Synchronized lyric/text
	SYTC	Synchronized tempo codes
	TALB	Album/Movie/Show title
	TBPM	BPM (beats per minute)
	TCOM	Composer
	TCON	Content type
	TCOP	Copyright message
	TDAT	Date
	TDLY	Playlist delay
	TENC	Encoded by
	TEXT	Lyricist/Text writer
	TFLT	File type
	TIME	Time
	TIT1	Content group description
	TIT2	Title/songname/content description
	TIT3	Subtitle/Description refinement
	TKEY	Initial key
	TLAN	Language(s)
	TLEN	Length
	TMED	Media type
	TOAL	Original album/movie/show title
	TOFN	Original filename
	TOLY	Original lyricist(s)/text writer(s)
	TOPE	Original artist(s)/performer(s)
	TORY	Original release year
	TOWN	File owner/licensee
	TPE1	Lead performer(s)/Soloist(s)
	TPE2	Band/orchestra/accompaniment
	TPE3	Conductor/performer refinement
	TPE4	Interpreted, remixed, or otherwise modified by
	TPOS	Part of a set
	TPUB	Publisher
	TRCK	Track number/Position in set
	TRDA	Recording dates
	TRSN	Internet radio station name
	TRSO	Internet radio station owner
	TSIZ	Size
	TSRC	ISRC (international standard recording code)
	TSSE	Software/Hardware and settings used for encoding
	TYER	Year
	TXXX	User defined text information frame
	UFID	Unique file identifier
	USER	Terms of use
	USLT	Unsychronized lyric/text transcription
	WCOM	Commercial information
	WCOP	Copyright/Legal information
	WOAF	Official audio file webpage
	WOAR	Official artist/performer webpage
	WOAS	Official audio source webpage
	WORS	Official internet radio station homepage
	WPAY	Payment
	WPUB	Publishers official webpage
	WXXX	User defined URL link frame

The unsynchronisation scheme

The only purpose of the 'unsynchronisation scheme' is to make the ID3v2 tag as compatible as possible with existing software. There is no use in 'unsynchronising' tags if the file is only to be processed by new software. Unsynchronisation may only be made with MPEG 2 layer I, II and III and MPEG 2.5 files.

Whenever a false synchronisation is found within the tag, one zeroed byte is inserted after the first false synchronisation byte. The format of a correct sync that should be altered by ID3 encoders is as follows:

%11111111 111xxxxx

And should be replaced with:

%11111111 00000000 111xxxxx

This has the side effect that all $FF 00 combinations have to be altered, so they won't be affected by the decoding process. Therefore all the $FF 00 combinations have to be replaced with the $FF 00 00 combination during the unsynchronisation.

To indicate usage of the unsynchronisation, the first bit in 'ID3 flags' should be set. This bit should only be set if the tag contains a, now corrected, false synchronisation. The bit should only be clear if the tag does not contain any false synchronisations.

Do bear in mind, that if a compression scheme is used by the encoder, the unsynchronisation scheme should be applied *afterwards*. When decoding a compressed, 'unsynchronised' file, the 'unsynchronization scheme' should be parsed first, decompression afterwards.

If the last byte in the tag is $FF, and there is a need to eliminate false synchronizations in the tag, at least one byte of padding should be added.

In the next blog let us see the encoding method.

Audio Codec - MP3 -ID3V1

2010-10-20T09:28:00.008+05:30

Audio Codec -MPEG Audio Compression Basics

This is one of many methods to compress audio in digital form trying to consume as little space as possible but keep audio quality as good as possible. MPEG compression showed up as one of the best achievements in this area.

This is a lossy compression, which means, you will certainly lose some audio information when you use this compression methods. But, this lost can hardly be noticed because the compression method tries to control it. By using several quite complicate and demanding mathematical algorithms it will only loose those parts of sound that are hard to be heard even in the original form. This leaves more space for information that is important. This way you can compress audio up to 12 times (you may choose compression ratio) which is really significant. Due to its quality MPEG audio became very popular.

MPEG standards MPEG-1, MPEG-2 and MPEG-4 are known but this document covers first two of them. There is an unofficial MPEG-2.5 which is rarely used. It is also covered.

MPEG-1 audio (described in ISO/IEC 11172-3) describes three Layers of audio coding with the following properties:

one or two audio channels
sample rate 32kHz, 44.1kHz or 48kHz
bit rates from 32kbps up to 448kbps

Each layer has its merits.

MPEG-2 audio (described in ISO/IEC 13818-3) has two extensions to MPEG-1, usually referred as MPEG-2/LSF and MPEG-2/Multichannel.

MPEG-2/LSF has the following properties:

one or two audio channels
sample rates half those of MPEG-1
bit rates from 8 kbps up to 256kbps.

MPEG-2/Multichannel has the following properties:

up to 5 full range audio channels and an LFE-channel (Low Frequency Enhancement <> subwoofer!)
sample rates the same as those of MPEG-1
highest possible bitrate goes up to about 1Mbps for 5.1

MPEG Audio Frame Header

An MPEG audio file is built up from smaller parts called frames. Generally, frames are independent items. Each frame has its own header and audio information. There is no file header. Therefore, you can cut any part of MPEG file and play it correctly (this should be done on frame boundaries but most applications will handle incorrect headers). For Layer III, this is not 100% correct. Due to internal data organization in MPEG version 1 Layer III files (mp3), frames are often dependent of each other and they cannot be cut off just like that.

When you want to read info about an MPEG file, it is usually enough to find the first frame, read its header and assume that the other frames are the same, this may not be always the case. Variable bitrate MPEG files may use so called bitrate switching, which means that bitrate changes according to the content of each frame. This way lower bitrates may be used in frames where it will not reduce sound quality. This allows making better compression while keeping high quality of sound.

The frame header is constituted by the very first four bytes (32bits) in a frame. The first eleven bits (in the case of the MPEG 2.5 extension) (or first twelve bits, see below about frame sync) of a frame header are always set and they are called "frame sync". Therefore, you can search through the file for the first occurrence of frame sync (meaning that you have to find a byte with a value of 255, and followed by a byte with its three (or four) most significant bits set). Then you read the whole header and check if the values are correct. You will see in the following table the exact meaning of each bit in the header, and which values may be checked for validity. Each value that is specified as reserved, invalid, bad, or not allowed should indicate an invalid header. Remember, this is not enough, frame sync can be easily (and very frequently) found in any binary file. Also it is likely that MPEG file contains garbage on it's beginning which also may contain false sync. Thus, you have to check two or more frames in a row to assure you are really dealing with MPEG audio file.

Frames may have a CRC check. The CRC is 16 bits long and, if it exists, it follows the frame header. After the CRC comes the audio data. You may calculate the length of the frame and use it if you need to read other headers too or just want to calculate the CRC of the frame, to compare it with the one you read from the file. This is actually a very good method to check the MPEG header validity.

Here is "graphical" presentation of the 32 bit header content. Characters from A to M are used to indicate different fields. In the table, you can see details about the content of each field.

76543210 76543210 76543210 76543210

AAAAAAAA AAABBCCD EEEEFFGH IIJJKLMM

Sign

Length
(bits)

Position
(bits)

Description

(31-21)

Frame sync (all bits set)

(20,19)

MPEG Audio version ID
00 - MPEG Version 2.5
01 - reserved
10 - MPEG Version 2 (ISO/IEC 13818-3)
11 - MPEG Version 1 (ISO/IEC 11172-3)

Note: MPEG Version 2.5 is not official standard. Bit No 20 in frame header is used to indicate version 2.5. Applications that do not support this MPEG version expect this bit always to be set, meaning that frame sync (A) is twelve bits long, not eleve as stated here. Accordingly, B is one bit long (represents only bit No 19). I recommend using methodology presented here, since this allows you to distinguish all three versions and keep full compatibility.

(18,17)

Layer description
00 - reserved
01 - Layer III
10 - Layer II
11 - Layer I

(16)

Protection bit
0 - Protected by CRC (16bit crc follows header)
1 - Not protected

(15,12)

Bitrate index

bits	V1,L1	V1,L2	V1,L3	V2,L1	V2, L2 & L3
0000	free	free	free	free	free
0001	32	32	32	32	8
0010	64	48	40	48	16
0011	96	56	48	56	24
0100	128	64	56	64	32
0101	160	80	64	80	40
0110	192	96	80	96	48
0111	224	112	96	112	56
1000	256	128	112	128	64
1001	288	160	128	144	80
1010	320	192	160	160	96
1011	352	224	192	176	112
1100	384	256	224	192	128
1101	416	320	256	224	144
1110	448	384	320	256	160
1111	bad	bad	bad	bad	bad

NOTES: All values are in kbps
V1 - MPEG Version 1
V2 - MPEG Version 2 and Version 2.5
L1 - Layer I
L2 - Layer II
L3 - Layer III
"free" means free format. If the correct fixed bitrate (such files cannot use variable bitrate) is different than those presented in upper table it must be determined by the application. This may be implemented only for internal purposes since third party applications have no means to find out correct bitrate. Howewer, this is not impossible to do but demands lot's of efforts.
"bad" means that this is not an allowed value

MPEG files may have variable bitrate (VBR). This means that bitrate in the file may change. I have learned about two used methods:

 bitrate switching. Each frame may be created with different bitrate. It may be used in all layers. Layer III decoders must support this method. Layer I & II decoders may support it.

 bit reservoir. Bitrate may be borrowed (within limits) from previous frames in order to provide more bits to demanding parts of the input signal. This causes, however, that the frames are no longer independent, which means you should not cut this files. This is supported only in Layer III.

For Layer II there are some combinations of bitrate and mode which are not allowed. Here is a list of allowed combinations.

bitrate	allowed modes
free	all
32	single channel
48	single channel
56	single channel
64	all
80	single channel
96	all
112	all
128	all
160	all
192	all
224	stereo, intensity stereo, dual channel
256	stereo, intensity stereo, dual channel
320	stereo, intensity stereo, dual channel
384	stereo, intensity stereo, dual channel

(11,10)

Sampling rate frequency index (values are in Hz)

bits	MPEG1	MPEG2	MPEG2.5
00	44100	22050	11025
01	48000	24000	12000
10	32000	16000	8000
11	reserv.	reserv.	reserv.

(9)

Padding bit
0 - frame is not padded
1 - frame is padded with one extra slot
Padding is used to fit the bit rates exactly. For an example: 128k 44.1kHz layer II uses a lot of 418 bytes and some of 417 bytes long frames to get the exact 128k bitrate. For Layer I slot is 32 bits long, for Layer II and Layer III slot is 8 bits long.

(8)

Private bit. It may be freely used for specific needs of an application, i.e. if it has to trigger some application specific events.

(7,6)

Channel Mode
00 - Stereo
01 - Joint stereo (Stereo)
10 - Dual channel (Stereo)
11 - Single channel (Mono)

(5,4)

Mode extension (Only if Joint stereo)

Mode extension is used to join informations that are of no use for stereo effect, thus reducing needed resources. These bits are dynamically determined by an encoder in Joint stereo mode.

Complete frequency range of MPEG file is divided in subbands There are 32 subbands. For Layer I & II these two bits determine frequency range (bands) where intensity stereo is applied. For Layer III these two bits determine which type of joint stereo is used (intensity stereo or m/s stereo). Frequency range is determined within decompression algorythm.

Layer I and II

Layer III

value	Layer I & II
00	bands 4 to 31
01	bands 8 to 31
10	bands 12 to 31
11	bands 16 to 31

Intensity stereo	MS stereo
off	off
on	off
off	on
on	on

(3)

(2)

Original
0 - Copy of original media
1 - Original media

(1,0)

Emphasis
00 - none
01 - 50/15 ms
10 - reserved
11 - CCIT J.17

How to calculate frame length

First, let's distinguish two terms frame size and frame length. Frame size is the number of samples contained in a frame. It is constant and always 384 samples for Layer I and 1152 samples for Layer II and Layer III. Frame length is length of a frame when compressed. It is calculated in slots. One slot is 4 bytes long for Layer I, and one byte long for Layer II and Layer III. When you are reading MPEG file you must calculate this to be able to find each consecutive frame. Remember, frame length may change from frame to frame due to padding or bitrate switching.

Read the BitRate, SampleRate and Padding of the frame header.

For Layer I files us this formula:

FrameLengthInBytes = (12 * BitRate / SampleRate + Padding) * 4

For Layer II & III files use this formula:

FrameLengthInBytes = 144 * BitRate / SampleRate + Padding

Example:
Layer III, BitRate = 128000, SampleRate = 441000, Padding = 0
==> FrameSize=417 bytes

Frames per Second

Just as the movie industry has a standard that specifies the number of frames per second in a film in order to guarantee a constant rate of playback on any projector, the MP3 spec employs a similar standard. Regardless of the bitrate of the file, a frame in an MPEG-1 file lasts for 26ms (26/1000 of a second). This works out to around 38fps. If the bitrate is higher, the frame size is simply larger, and vice versa. In addition, the number of samples stored in an MP3 frame is constant, at 1,152 samples per frame.

The total size in bytes for any given frame can be calculated with the following formula: FrameSize = 144 * BitRate / (SampleRate + Padding).

Where the bitrate is measured in bits per second (remember to add the relevant number of zeros to convert from kbps to bps), SampleRate refers to the samplerate of the original input data, and padding refers to extra data added to the frame to fill it up completely in the event that the encoding process leaves unfilled space in the frame. For example, if you're encoding a file at 128 kbps, the original samplerate was 44.1kHz, and no padding bit has been set, the total size of each frame will be 417.96 bytes: 144 * 128000 / (44100 + 0) = 417.96 bytes .

Keeping in mind that each frame contains the header information described above, it would be easy to think that header data accounts for a lot of redundant information being stored and read back. However, keep in mind that each frame header is only 32 bits long. At 38fps, that means you get around 1,223 bits per second of header data, total. Since a file encoded at 128 kbps contains 128,000 bits every second; the total amount of header data is miniscule in comparison to the amount of audio data in the frame itself

ID3 Tag

Digital audio files can contain, in addition to the audio track, related text and/or graphical information, like Song title, Artist name, Album name, Year and Genre. This is the information displayed when you playback a digital audio file on your computer or portable device.

The process of including information other than sound into these digital audio files is commonly referred to as "tagging" in which you "tag" the audio file with additional information that describes the audio file. The original standard for tagging digital files was developed in 1996 by Eric Kemp and he coined the term ID3. At that time ID3 simply meant "IDentify an MP3".

ID3 tags were designed with the MP3 file format in mind. ID3v2 tags will break formats which are container-based such as Ogg Vorbis and WMA. Here is some information on specific formats:

ID3 tags work in MP3 and MP3pro files
WAV has no tags
WMA has its own tagging format, which is specified in the wma spec, available in the MSDN (which unfortunately, basically does not allow Open Source implementations)
Ogg Vorbis uses "Xiph Comments" (same as later versions of FLAC and Speex), which are embedded into the Ogg container. You can find information on these in the comment and container specs on www.xiph.org
AAC uses yet another tagging format, which does not at present have a published spec as of 3/1/2006.

The TagLib Audio Meta-Data Library supports MP3s (with ID3v1, ID3v2 or APE tags), Ogg Vorbis, FLAC (with Xiph Comments or ID3 tags), and MPC files (with APE tags).

MPEG Audio Tag ID3v1

The TAG is used to describe the MPEG Audio file. It contains information about artist, title, album, publishing year and genre. There is some extra space for comments. It is exactly 128 bytes long and is located at very end of the audio data. You can get it by reading the last 128 bytes of the MPEG audio file.

AAABBBBB BBBBBBBB BBBBBBBB BBBBBBBB
BCCCCCCC CCCCCCCC CCCCCCCC CCCCCCCD
DDDDDDDD DDDDDDDD DDDDDDDD DDDDDEEE
EFFFFFFF FFFFFFFF FFFFFFFF FFFFFFFG

Sign	Length (bytes)	Position (bytes)	Description
A	3	(0-2)	Tag identification. Must contain 'TAG' if tag exists and is correct.
B	30	(3-32)	Title
C	30	(33-62)	Artist
D	30	(63-92)	Album
E	4	(93-96)	Year
F	30	(97-126)	Comment
G	1	(127)	Genre

The specification asks for all fields to be padded with null character (ASCII 0). However, not all applications respect this (an example is WinAmp which pads fields with <space>, ASCII 32).

There is a small change proposed in ID3v1.1 structure. The last byte of the Comment field may be used to specify the track number of a song in an album. It should contain a null character (ASCII 0) if the information is unknown.

Genre is a numeric field which may have one of the following values:

0	'Blues'	20	'Alternative'	40	'AlternRock'	60	'Top 40'
1	'Classic Rock'	21	'Ska'	41	'Bass'	61	'Christian Rap'
2	'Country'	22	'Death Metal'	42	'Soul'	62	'Pop/Funk'
3	'Dance'	23	'Pranks'	43	'Punk'	63	'Jungle'
4	'Disco'	24	'Soundtrack'	44	'Space'	64	'Native American'
5	'Funk'	25	'Euro-Techno'	45	'Meditative'	65	'Cabaret'
6	'Grunge'	26	'Ambient'	46	'Instrumental Pop'	66	'New Wave'
7	'Hip-Hop'	27	'Trip-Hop'	47	'Instrumental Rock'	67	'Psychadelic'
8	'Jazz'	28	'Vocal'	48	'Ethnic'	68	'Rave'
9	'Metal'	29	'Jazz+Funk'	49	'Gothic'	69	'Showtunes'
10	'New Age'	30	'Fusion'	50	'Darkwave'	70	'Trailer'
11	'Oldies'	31	'Trance'	51	'Techno-Industrial'	71	'Lo-Fi'
12	'Other'	32	'Classical'	52	'Electronic'	72	'Tribal'
13	'Pop'	33	'Instrumental'	53	'Pop-Folk'	73	'Acid Punk'
14	'R&B'	34	'Acid'	54	'Eurodance'	74	'Acid Jazz'
15	'Rap'	35	'House'	55	'Dream'	75	'Polka'
16	'Reggae'	36	'Game'	56	'Southern Rock'	76	'Retro'
17	'Rock'	37	'Sound Clip'	57	'Comedy'	77	'Musical'
18	'Techno'	38	'Gospel'	58	'Cult'	78	'Rock & Roll'
19	'Industrial'	39	'Noise'	59	'Gangsta'	79	'Hard Rock'

WinAmp expanded this table with next codes:

80	'Folk'	92	'Progressive Rock'	104	'Chamber Music'	116	'Ballad'
81	'Folk-Rock'	93	'Psychedelic Rock'	105	'Sonata'	117	'Poweer Ballad'
82	'National Folk'	94	'Symphonic Rock'	106	'Symphony'	118	'Rhytmic Soul'
83	'Swing'	95	'Slow Rock'	107	'Booty Brass'	119	'Freestyle'
84	'Fast Fusion'	96	'Big Band'	108	'Primus'	120	'Duet'
85	'Bebob'	97	'Chorus'	109	'Porn Groove'	121	'Punk Rock'
86	'Latin'	98	'Easy Listening'	110	'Satire'	122	'Drum Solo'
87	'Revival'	99	'Acoustic'	111	'Slow Jam'	123	'A Capela'
88	'Celtic'	100	'Humour'	112	'Club'	124	'Euro-House'
89	'Bluegrass'	101	'Speech'	113	'Tango'	125	'Dance Hall'
90	'Avantgarde'	102	'Chanson'	114	'Samba'
91	'Gothic Rock'	103	'Opera'	115	'Folklore'
Any other value should be considered as 'Unknown'

MPEG Audio Tag ID3v2

This is new proposed TAG format which is different than ID3v1 and ID3v1.1. In the next blog, let us see in detail about ID3V2.

Navratri

2010-10-16T14:46:00.030+05:30

Wish you happy Navratri and Dussehra may Maa Durga bless all

Navratri, Navaratri, or Navarathri (Sanskrit, Hindi, Marathi, and Nepali: नवरात्रि, Bengali: নবরাত্রি, Gujarātī: નવરાત્રી, Kannada:ನವರಾತ್ರಿ,Telugu : దుర్గా నవరాత్రులు , Malayalam: നവരാത്രി, Tamil: நவராத்திரி) is a Hindu festival of worship of Shakti and dance & festivities. The word Navaratri literally means nine nights in Sanskrit, nava meaning nine and ratri meaning nights. It is celebrated during the period of Sarad Masi Aswin by Hindu lunar calendar, all eight days and nine nights have its importance and is divided into sets of three days to adore three different aspects of the supreme goddess or goddesses.

Nine Goddesses of Navratri are collectively known as Navdurga and are mentioned in the Devi Mahatmya and Durga Saptashati. The Nine Goddesses worshipped on each nine-day of Navaratri are incarnations of Goddess Shakti. The nine goddess worshipped are Shailaputri, Brahmacharini, Chandraghanta, Kushmanda, Skanda Mata, Katyayani, Kala Ratri (Kaalratri), Maha Gowri and Siddhidayini.

Maa Shailaputri – Goddess Worshipped on the first day of Navratri

'Shail' means mountains and 'Putri' means daughter. She is also known as Parvati or Hemavati

Shailaputri is believed to be the rebirth of Sati, the daughter of Daksha and the wife of Lord Shiva. In her second birth she is Parvati, the daughter of Himalaya and later she became the consort of Shiva. This is one of the very first forms of Shakti and is closely associated with Lord Shiva.

Maa Brahmacharini – Goddess Worshipped on the second day of Navratri

Here Brahma means 'one who constantly meditates on the Supreme Being'. Brahmacharini is highly pious and is a peaceful form or is in meditation. She is also known as Tapashcharini, Aparna and Uma.

This form of Durga is related to the severe penance undertaken by Sati and Parvati in their respective births to attain Lord Shiva as husband. Some of the most important Vratas observed in different parts of India by women is based on the strict austerities followed by Brahmacharini.

Maa Chandraghanta – Goddess Worshipped on the third day of Navratri

Her name Chandraghanta comes from the crescent moon worn by her on the head.

This is a terrible aspect of Goddess Shakti and is roaring in anger. This form of Durga is completely different from earlier forms and shows when provoked she can be the terrible or malevolent.

Maa Kushmanda – Goddess Worshipped on the fourth day of Navratri

The name Kushmanda consists of three words. 'Ku' means 'a little', 'Usma' means 'energy' and 'Anda' means 'the cosmic egg or universe.' She is also known as Ashtabhuja.

Goddess Shakti is very happy in this incarnation and it is believed that the eternal darkness ended when she smiled. And this led to the beginning of creation.

Maa Skanda Mata – Goddess Worshipped on the fifth day of Navratri

Skanda is one of the names of Subrahmanya or Lord Muruga or Kartik – the General of the Army of the Devas and the most handsome God. Skanda Mata is the mother of Kartik. She is also known as Padmasana.

This the motherly form of Durga and she is benevolent.

Maa Katyayani – Goddess Worshipped on the sixth day of Navratri

She is called Katyayani because she was born as the daughter of Sage Katya of Katya clan.

This is the daughter form of Durga. Here is she a loving daughter. She is epitome of love but won't hesitate to rise up in anger to defend righteousness and Dharma.

Maa Kalaratri – Goddess Worshipped on the seventh day of Navratri

Kalaratri is the one who destroys ignorance and removes darkness. She is also known as Shubhamkari.

In this form she is believed to have licked the blood of demon Rakta Beeja who had the capacity to bring out thousand demons from a drop of blood spilt from his body. This is the most violent form of Durga. This form primarily depicts that life also has dark side – the violent Mother Nature and creates havoc and removes all dirt.

Maa Mahagauri – Goddess Worshipped on the eighth day of Navratri

Mahagauri means one clean and bright like a ray of lightning.

This is the form of Mata Parvati when she did penance to get Shiva as her husband. It is believed that due to the intense Tapas performed by her without moving caused soil and dust to collect on her body. Lord Shiva cleaned her with water from Ganga. Purity is depicted in this form of Durga.

Maa Siddhidatri – Goddess Worshipped on the ninth day of Navratri

In this form Mother Goddess provides 'Siddhi' or knowledge.

In this form Durga removes ignorance and she provides the knowledge to realize That or Brahman. She is surrounded by Siddhas, Gandharvas, Yakshas, Demons and Gods who are worshipping her. The Siddhi that she provides is the realization that everything is Supreme Being or Brahman.

For the initial six the Pooja celebrations are limited to home. The celebrations acquire a festive form since the seventh day when the festivities of Navratri surround the atmosphere. The festivities culminate on the tenth day, called variously Vijayadashmi, Dushehra when people in most parts of the country burn effigies of Ravana, Meghanatha and Kumbhakarna.

Some people fast on all nine days, eating only fruit and milk dishes. Some fast only on the eighth or/and ninth day. As the festival is dear to the mother goddess, on the eighth or ninth day many people invite over nine young girls from the neighborhood. These girls are treated as the goddess herself. People ceremonially wash their feet, worship them and then offer food to the "girl-goddesses".

On the first day of the Navaratras, grains of barley are planted in the puja room of the house. A small bed of mud is prepared in which barley seeds are sown after a small puja has been performed. Every day some water is sprinkled on it. On the tenth day, the shoots are about 3 - 5 inches in length. After the puja, these seedlings are pulled out and given to devotees as a blessing from god. The seedlings are placed on their caps, behind their ears, and inside books to bring good luck. This custom suggests a link to harvesting. The sowing and reaping of barley is symbolic of the "first fruit". Soon after this festival, the sugarcane crop is harvested and the winter crops are sown.

History & Origin Of Navratri - The Legend

Mahishasura, the mighty demon, worshipped Lord Shiva and obtained the power of eternity. Soon, he started killing and harassing innocent people and set out to win all the three lokas. The gods in swargaloka appealed to Lord Shiva, to find a way to get rid of the demon. To protect the world from the atrocities of Mahishasura, the Trinity of Brahma, Vishnu and Shiva united their powers and created a divine female warrior, known as Goddess Durga. Mahishasura, when he saw the divine beauty of Goddess Durga, got mesmerized.

So fascinated was Mahishasura by Goddess Durga's beauty that he approached her with the intention of marriage. The goddess agreed to marry him, but put forth a condition - Mahishasura would have to win over her in a battle. Mahishasura, proud as he was, agreed immediately! The battle continued for 9 nights and at the end of the ninth night, Goddess Durga beheaded Mahishasura. The nine nights came to be known as Navratri, while the tenth day was called Vijayadashmi, the tenth day that brought the triumph of good over evil.

The origin of this custom can also be traced to the Ramayana. According to it, Rama had to pray to the nine different aspects of Devi to be able to kill Ravana. He then accumulated enough power to kill Ravana on the tenth day, which was called Vijayadashmi or Victory Day. Since then, the tradition of praying to Devi for nine days has continued and was especially pronounced amongst the Kshatriyas who believed that by doing so, they too would be able to defeat the most powerful enemy.

In different parts of India:

Today, it is celebrated more for its mythological significance and reaffirms the Hindu faith in the triumph of good. Even today, the nine different forms of the goddess are worshipped. Though several communities of Hindus are staunch vegetarians, Navaratri is one exception. On the eighth day, many communities, especially Gurkha and other hill tribes who are believers in the Devi cult sacrifice an animal. This blood sacrifice is a form of thanksgiving to the goddess for a wish that has been granted. People often sacrifice a buffalo symbolic of the killing of Mahishasura by Durga.

In Bengal, this period is celebrated as Durga Puja. Groups and residents' associations in towns and cities erect beautiful marquees, where they install the idol of the Mother Goddess.

In Calcutta, as also other places, there are competitions held and the most beautiful and creatively done marquee gets a prize. For all the nine days, the marquee becomes the center of all activity where cultural events and competitions are organized every day.

In Gujarat, this is the time for the joyous Garba and Dandia dances and people pour out at night to participate in this community festival. Women and girls in all their fineries dance around the garb a pot, clapping their hands in rhythmic movement. The pot is decorated with flowers, betel leaves, and has its mouth covered with a coconut.

In Tamil Nadu, the first three days of the festival are dedicated to Lakshmi, the next three to Durga and the last three to Sarasvati. The nine-day celebration is compartmentalized in certain parts of the country, dedicating three days each to a trinity of goddesses: to Durga the goddess of valor, to Lakshmi the goddess of wealth and to Saraswati the goddess of knowledge.

The one thing that remains constant in most parts of the country is that daytime is exclusively for prayers, fasting, and solemnity while the nights are spent in joy and revelry. Men, women, and children, who have fasted during the day, have a light repast of fruit or other non-cereals at night before going out to enjoy the festive season.

In Punjab, people organize Jagrans to sing devotional songs all night in praise of the Mother Goddess. Solemnity and piety mark these nine days as even those Punjabis who do not keep a fast, stop eating non-vegetarian and impure food items like onion and garlic.

Another part of the Navratri celebrations is the Ramlila. In places like Delhi and Uttar Pradesh, almost every locality has its own group of actors re-enacting episodes from the life of Lord Rama. This is probably because, the day after Navratri, i.e. on the tenth day of Ashvin called the Vijaya Dashami, it is said that Lord Rama killed Ravana and other demons to rid the earth of evil.

Mysore Palace during Dussehra

Rituals

The tempo of life changes perceptibly in every family, in markets, in Mata's temples, long before the festival commences. In homes, the corner or room reserved for puja becomes the scene of intense preparation. A coconut, saffron or sandalwood paste, a garba (perforated earthen pot), a kumbh (earthen pot), grains of wheat or barley, ghee (clarified butter) or mustard oil for a lamp that will burn incessantly all through the nine special nights, are placed in readiness for the ceremonial ritualistic initiation of the festival.

Housewives draw designs and emblems with rice flour, turmeric powder-and vermilion. Each of the motifs symbolizes abundance and represents hope for the future.

The eagerly awaited first day of the festival witnesses a flurry of ritualistic activity. On a small platform of fresh earth in front of the idol of the Mother Goddess, all the things collected for the puja are placed and the lamp is lit. As evening falls, people gather around the sacred flame that is constantly fed with ghee or oil, and soon, mellow voices singing bhajans can be heard from home after home.

On Lalita Panchami (the fifth day), children gather all the books in the house before a sacred lamp and invoke the blessings of Saraswati. It is also the occasion for all artisans to lay down their tools before the goddess and seek her benediction upon their trade.

On the eighth and ninth days of the festival, yagnas are performed as a final act of farewell that marks the termination of the ceremonies. Ghee or clarified butter, a sweet concoction of rice cooked in condensed milk (paayas or kheer) and sesame seeds are traditional items used in the yagna to the chanting of mantras conveying the theme'"This is my offering to God".

On the tenth day or Vijaya Dasami, more popularly known as Dussehra, enormous effigies of Ravana stuffed with firecrackers are torched with flaming arrows to the delight of throngs of revelers.

People read "The Devi Mahatmyam" (Glory of Divine Mother) having 700 Mantras on Shri Durga Mata.

Things you need to know about

"Nava-ratri" literally means "nine nights." This festival is observed twice a year, once in the beginning of summer and again at the onset of winter.

What's the Significance of Navratri?

During Navaratri, we invoke the energy aspect of God in the form of the universal mother, commonly referred to as "Durga," which literally means the remover of miseries of life. She is also referred to as "Devi" (goddess) or "Shakti" (energy or power). It is this energy, which helps God to proceed with the work of creation, preservation and destruction. In other words, we can say that God is motionless, absolutely changeless, and the Divine Mother Durga, does everything. Truly speaking, our worship of Shakti re-confirms the scientific theory that energy is imperishable. It cannot be created or destroyed. It is always there.

Why Worship the Mother Goddess?

We think this energy is only a form of the Divine Mother, who is the mother of all, and all of us are her children. "Why mother; why not father?" J Let me just say that we believe that God's glory, his cosmic energy, his greatness and supremacy can best be depicted as the motherhood aspect of God. Just as a child finds all these qualities in his or her mother, similarly, all of us look upon God as mother. In fact, Hinduism is the only religion in the world, which gives so much importance to the mother aspect of God because we believe that mother is the creative aspect of the absolute.

Why Twice a Year?

Every year the beginning of summer and the beginning of winter are two very important junctures of climatic change and solar influence. These two junctions have been chosen as the sacred opportunities for the worship of the divine power because:

We believe that it is the divine power that provides energy for the earth to move around the sun, causing the changes in the outer nature and that this divine power must be thanked for maintaining the correct balance of the universe.
Due to the changes in the nature, the bodies and minds of people undergo a considerable change, and hence, we worship the divine power to bestow upon all of us enough potent powers to maintain our physical and mental balance.

Why Nine Nights & Days?

Navaratri is divided into sets of three days to adore different aspects of the supreme goddess. On the first three days, the Mother is invoked as powerful force called Durga in order to destroy all our impurities, vices and defects. The next three days, the Mother is adored as a giver of spiritual wealth, Lakshmi, who is considered to have the power of bestowing on her devotees the inexhaustible wealth. The final set of three days is spent in worshipping the mother as the goddess of wisdom, Saraswati. In order have all-round success in life, we need the blessings of all three aspects of the divine mother; hence, the worship for nine nights.

Why Do We Need the Power?

J what I suggest that join your parents and friends in worshipping "Ma Durga", she will bestow on you wealth, auspiciousness, prosperity, knowledge, and other potent powers to cross every hurdle of life.

Let us all take a resolve, this Navaratri, to spread peace, harmony and knowledge in this world and strengthen our commitment to making this world a better place.

Karmaniye wadhikaraste

OpenCV - 01

2010-10-14T19:24:00.011+05:30

OpenCV Customization with VS2008

Installation

OpenCV is an open source library for computer vision development. There are some very interesting sample applications included with this library. Before we can start we need to be able to build the library.

Requirements

OpenCV Library

Visual Studio 2008 Express C++

Windows Platform SDK

Optional

Visual Studio 2008 Express C++ SP1

Procedure
1. Step 1 - Installing Visual C++ and Platform SDK

Visit http://msdn.microsoft.com/en-in/vstudio/default.aspx or http://www.microsoft.com/india/visualstudio/products/2008-editions/professional and follow Microsoft's Guide to setup Visual C++ and the Platform SDK.

When you get to Step 3, add this line to "Include Files" (assume default install location) C:\Program Files\Microsoft Platform SDK for Windows \Include\mfc this is because OpenCV requires some files that are inside that folder.

Step 2 - Update Visual C++ with Service Pack 1 (Optional)

Service Packs for the each of the Visual Studio products are available on one page from Microsoft. Visual Studio 2008 Express SP1.

Step 3 - Install OpenCV

Get OpenCV Library and download OpenCV 2.1 for Windows http://sourceforge.net/projects/opencvlibrary/files/opencv-win/2.1/ Installation is straight forward.

Step 4 - Customising Visual C++ for use with OpenCV

We need to setup the directories for Open Visual C++

Open Visual C++

Choose menu "Tools" and select "Options"

In "Projects and Solutions" and go to "VC++ Directories"

Show directories for "Library Files"

Add "C:\Program Files\OpenCV2.1\lib" to the list of directories

(The important library files are: cv.lib, cvaux.lib, cxcore.lib, cvcam.lib, highgui.lib)

Similarly,

Show directories for "Include Files"

Add "C:\Program Files\OpenCV2.1\include\opencv" to the list of directories

(The important include files are: cvaux.h, cxcore.h, cv.h, highgui.h, cvcam.h)

And,

Show directories for "Source Files"

Add "C:\Program Files\OpenCV2.1\src" to the list of directories

Finally,

Show directories for "Executable Files"

Add "C:\Program Files\OpenCV2.1\bin" to the list of directories

Step 5 - Open "OpenCV Workspace .NET 2008"

In the start menu a folder called "Open CV" was created when you installed OpenCV. Inside the folder "OpenCV" there is a shortcut called "OpenCV Workspace .NET 2008" Open "OpenCV Workspace .NET 2008" This will load OpenCV solution within Visual C++ There is one last thing you need to do, to be able to compile OpenCV.

Choose menu "Build" and Select "Configuration Manager"

Change "Active solution configuration" to either "Debug" or "Release"

Step 6 - Build

Now that everything is installed and setup; building OpenCV should be a breeze.

Choose menu "Build" and Select "Build Solution"

Creating Application at A Glance

Now, we will try to create application based on OpenCV at a glance. First, we will try to create console application (without Graphical User Interface / GUI)

Create new console project by following the picture below

Right click and add new file

OpenCV Application with Graphical User Interface

Click File >> New >> Project >> Visual C++ >> Windows Forms Application (don't forget to enter your application's name)

Set additional directories and libraries, as you do in creating console application (step 3 previous sections).

The main important thing set your general properties of Common Language Runtime Support. To do this, select your project at the left windows, right click >> Properties >> Configuration Properties >> General >> Common Language Runtime Support

Change from "No Common Language Runtime Support" to "Common Language Runtime Support" …….and happy coding!

Reference

http://opencv.willowgarage.com/wiki/FullOpenCVWiki

Optimization - 03

2010-10-12T19:06:00.010+05:30

Optimization - Inline Functions in C

Introduction

GNU C (and some other compilers) had inline functions long before standard C introduced them (in the 1999 standard). The point of making a function inline is to hint to the compiler that it is worth making some form of extra effort to call the function faster than it would otherwise - generally by substituting the code of the function into its caller. As well as eliminating the need for a call and return sequence, it might allow the compiler to perform certain optimizations between the bodies of both functions.

Sometimes it is necessary for the compiler to emit a stand-alone copy of the object code for a function even though it is an inline function - for instance if it is necessary to take the address of the function, or if it can't be inlined in some particular context, or (perhaps) if optimization has been turned off. (And of course, if you use a compiler that doesn't understand inline, you'll need a stand-alone copy of the object code so that all the calls actually work at all.)

There are various ways to define inline functions; any given kind of definition might definitely emit stand-alone object code, definitely not emit stand-alone object code, or only emit stand-alone object code if it is known to be needed. Sometimes this can lead to duplication of object code, which is a potential problem for following reasons:

It wastes space.
It can cause pointers to what is apparently the same function to compare not equal to one another.
It might reduce the effectiveness of the instruction cache. (Although inlining might do that in other ways too.)

Motivation

Inline expansion is used to eliminate the time overhead when a function is called. It is typically used for functions that execute frequently. It also has a space benefit for very small functions, and is an enabling transformation for other optimizations.

Without inline functions, however, the compiler decides which functions to inline. The programmer has little or no control over which functions are inlined and which are not. Giving this degree of control to the programmer allows her/him to use application-specific knowledge in choosing which functions to inline.

In some computer languages inline functions interact intimately with the compilation model. In C++, for example, it is necessary to define an inline function in every module that uses it, whereas an ordinary function must be defined in only a single module. This makes it possible to compile a single module independently of all other modules.

Microsoft Visual C++ Specific

Microsoft Visual C++ and few other compilers support non-standard constructs for defining inline functions, such as __inline and __forceinline specifiers.

__inline

The __inline keyword is equivalent to inline.

__forceinline

The __forceinline keyword allow the programmer to force the compiler to inline the function, but indiscriminate use of __forceinline can result in larger code (bloated executable file), minimum or none performance gain and in some cases even performance losses. The compiler cannot inline the function in all circumstances, even with the __forceinline keyword applied. If the compiler cannot inline a function declared with __forceinline, a warning of level 1 is generated.

cases when __forceinline will not take effect

The function or its caller is compiled with /Ob0 (the default option for debug builds).
The function and the caller use different types of exception handling (C++ exception handling in one, structured exception handling in the other).
The function has a variable argument list.
The function uses inline assembly, unless compiled with /Og, /Ox, /O1, or /O2.
The function is recursive and not accompanied by #pragma inline_recursion(on). With the pragma, recursive functions are inlined to a default depth of 16 calls. To reduce the inlining depth, use inline_depth pragma.
The function is virtual and is called virtually. Direct calls to virtual functions can be inlined.
The program takes the address of the function and the call is made via the pointer to the function. Direct calls to functions that have had their address taken can be inlined.
The function is also marked with the naked __declspec modifier.

__forceinline is useful if:

inline or __inline is not respected by the compiler (ignored by compiler cost/benefit analyzer)
code portability is not required
inlining results in a necessary performance boost

Example of portable code

#ifdef _MSC_VER

#define INLINE __forceinline // use __forceinline (VC++ specific)

#else

#define INLINE inline // use standard inline

#endif

INLINE void helloworld() { /* function body */ }

C99 Inline Rules

The specification for inline is section 6.7.4 of the C99 standard (ISO/IEC 9899:1999). Unfortunately this isn't freely available. The following possibilities exist:

A Standalone Function

A function where all the declarations (including the definition) mention inline and never extern. There must be a definition in the same translation unit. The standard refers to this as an inline definition. No stand-alone object code is emitted, so this definition can't be called from another translation unit.

You can have a separate (not inline) definition in another translation unit, and the compiler might choose either that or the inline definition.

Such functions may not contain modifiable static variables, and may not refer to static variables or functions elsewhere in the source file where they are declared.

In this example, all the declarations and definitions use inline but not extern:

// a declaration mentioning inline

inline int max(int a, int b);

// a definition mentioning inline

inline int max(int a, int b) {

return a > b ? a : b;

}

The function won't be callable from other files; if another file has a definition that might be used instead.

The standard is vague on this point. It says that the inline definition does not forbid an external definition elsewhere, but then that it provides an alternative to an external definition. Unfortunately this doesn't really make clear whether this external definition must actually exist.

In practice unless you are torture-testing your compiler it will exist: if you wanted to keep your inline function entirely private to one translation unit, you make it static inline.

A Function with extern

A function where at least one declaration mentions inline, but where some declaration doesn't mention inline or does mention extern. There must be a definition in the same translation unit. Stand-alone object code is emitted (just like a normal function) and can be called from other translation units in your program.

The same constraint about statics above applies here, too.

In this example all the declarations and definitions use inline but one adds extern:

// a declaration mentioning extern and inline

extern inline int max(int a, int b);

// a definition mentioning inline

inline int max(int a, int b) {

return a > b ? a : b;

}

In this example, one of the declarations does not mention inline:

// a declaration not mentioning inline

int max(int a, int b);

// a definition mentioning inline

inline int max(int a, int b) {

return a > b ? a : b;

}

In either example, the function will be callable from other files.

A Function with static

A function defined static inline. A local definition may be emitted if required. You can have multiple definitions in your program, in different translation units, and it will still work. Just dropping the inline reduces the program to a portable one (again, all other things being equal).

This is probably useful primarily for small functions that you might otherwise use macros for. If the function isn't always inlined then you get duplicate copies of the object code, with the problems described above.

A sensible approach would be to put the static inline functions in either a header file if they are to be widely used or just in the source files that use them if they are only ever used from one file.

In this example the function is defined static inline:

// a definition using static inline

static int max(int a, int b) {

return a > b ? a : b;

}

The first two possibilities go together naturally. You either write inline everywhere and extern in one place to request a stand-alone definition, or write inline almost everywhere but omit it exactly once to get the stand-alone definition.

main is not allowed to be an inline function.

(If you think I've misinterpreted these rules, please let me know!)

(C++ is stricter: a function which is inline anywhere must be inline everywhere and must be defined identically in all the translation units that use it.)

GNU C Inline Rules

The GNU C rules are described in the GNU C manual, which is included with the compiler. This is freely available if you follow links from e.g. http://gcc.gnu.org. The following possibilities exist:

A Standalone Function

A function defined with inline on its own. Stand-alone object code is always emitted. You can only write one definition like this in your entire program. If you want to use it from other translation units to the one where it is defined, you put a declaration in a header file; but it would not be inlined in those translation units.

This is of rather limited use: if you only want to use the function from one translation unit then static inline below makes more sense, if not the you probably want some form that allows the function to be inlined in more than one translation unit.

However it does have the advantage that by defining away the inline keyword, the program reduces to a portable program with the same meaning (provided no other non-portable constructions are used).

A Function with extern

A function defined with extern inline. Stand-alone object code is never emitted. You can have multiple such definitions and your program will still work. However, you should add a non-inline definition somewhere too, in case the function is not inlined everywhere. This provides sensible semantics (we can avoid duplicate copies of the functions' object code) but is a bit inconvenient to use.

One approach to using this would be to put the definitions in a header file, surrounded by a #if that expands to true either when using GNU C, or when the header has been included from the file that is contain the emitted definitions (whether or not using GNU C). In the latter case the extern is omitted (for instance writing EXTERN and #define-ing that to either extern or nothing). The #else branch would contain just declarations of the functions, for non-GNU compilers.

A Function with static

A function defined with static inline. Stand-alone object code may be emitted if required. We can have multiple definitions in our program, in different translation units, and it will still work. This is the same as the C99 rules.

As of release 4.3, GNU C supports the C99 inline rules mentioed above and defaults to them with the -std=c99 or -std=gnu99 options. The old rules can be requested in new compilers with the -gnu89-inline option or via the gnu_inline function attribute.

If the C99 rules are in force then GCC will define the __GNUC_STDC_INLINE__ macro. Since GCC 4.1.3, it will define __GNUC_GNU_INLINE__ if the GCC-only rules are in use, but older compilers use these rules without defining either macro. You could normalize the situation with a fragment like this:

#if defined __GNUC__ && !defined __GNUC_STDC_INLINE__ && !defined __GNUC_GNU_INLINE__

# define __GNUC_GNU_INLINE__ 1

#endif

Strategies For Using Inline Functions

These rules suggest several possible models for using inline functions in more or less portable ways.

A Simple Portable Model

Use static inline (either in a common header file or just in one file). If the compiler needs to emit a definition (e.g. to take its address, or because it doesn't want to inline some call) then you waste a bit of space; if you take the address of the function in two translation units then the result won't compare equal.

For instance, in a header file:

static inline int max(int a, int b) {

return a > b ? a : b;

}

You can support legacy compilers (i.e. anything without inline) via -Dinline="", although this may waste space if the compiler does not optimize out unused functions.

A GNU C Model

Use extern inline in a common header and provide a definition in a .c file somewhere, perhaps using macros to ensure that the same code is used in each case. For instance, in the header file:

#ifndef INLINE

# define INLINE extern inline

#endif

INLINE int max(int a, int b) {

return a > b ? a : b;

}

...and in exactly one source file:

#define INLINE

#include "header.h"

Supporting legacy compilers is awkward unless you don't mind wasting space and having multiple addresses for the same function; you need to restrict the definitions to a in single translation unit (with INLINE defined to the empty string) and add some external declarations in the header file.

A C99 Model

Use inline in a common header, and provide definitions in a .c file somewhere, via extern declarations. For instance, in the header file:

inline int max(int a, int b) {

return a > b ? a : b;

}

...and in exactly one source file:

#include "header.h"

extern int max(int a, int b);

To support legacy compilers, you have to swap the whole thing around so that the declarations are visible in the common header and the definitions are restricted to a single translation unit, with inline defined away.

A Complicated Portable Model

Use macros to choose either extern inline for GNU C, inline for C99, or neither for a definition. For instance, in the header:

#ifndef INLINE

# if __GNUC__ && !__GNUC_STDC_INLINE__

# define INLINE extern inline

# else

# define INLINE inline

# endif

#endif

INLINE int max(int a, int b) {

return a > b ? a : b;

}

...and in exactly one source file:

#define INLINE

#include "header.h"

Supporting legacy compilers has the same issues as the GNU C model.

Problems With Inline Functions

Besides the problems associated with inline expansion in general, inline functions as a language feature may not be as valuable as they appear, for a number of reasons:

Often, a compiler is in a better position than a human to decide whether a particular function should be inlined. Sometimes the compiler may not be able to inline as many functions as the programmer indicates.
An important point to note is that the code (of the inline function) gets exposed to the calling function.
As functions evolve, they may become suitable for inlining where they were not before, or no longer suitable for inlining where they were before. While inlining or un-inlining a function is easier than converting to and from macros, it still requires extra maintenance which typically yields relatively little benefit.
Inline functions used in proliferation in native C-based compilation systems can increase compilation time, since the intermediate representation of their bodies is copied into each call site where they are inlined. The potential increase in code size is mirrored by a potential increase in compilation time.
The specification of inline in C99 requires exactly one additional external definition of a function in another compilation unit, when the corresponding inline definition that can occur multiple times in different compilation units, if that function is used somewhere. That can easily lead to linker errors because such a definition wasn't provided by the programmer. In particular, the C++ specification of inline does not require an additional non-inline definition of such a function. For this reason, inline in C99 often is used together with static, which gives the function internal linkage.

Image Processing - 02

2010-10-11T19:32:00.005+05:30

Image Segmentation

In computer vision, segmentation refers to the process of partitioning a digital image into multiple segments (group of meaningful pixels). The goal of segmentation is to simplify and/or change the representation of an image into something that is more meaningful and easier to analyze. Image segmentation is typically used to locate objects and boundaries (lines, curves, etc.) in images. More precisely, image segmentation is the process of assigning a label to every pixel in an image such that pixels with the same label share certain visual characteristics. Each of the pixels in a region are similar with respect to some characteristic or computed property, such as color, intensity, or texture. Adjacent regions are significantly different with respect to the same characteristic(s). Some of the practical applications of image segmentation are:

Medical Imaging
- Locate tumors and other pathologies
- Measure tissue volumes
- Computer-guided surgery
- Diagnosis
- Treatment planning
- Study of anatomical structure
Locate objects in satellite images (roads, forests, etc.)
Face recognition
Fingerprint recognition
Traffic control systems
Brake light detection
Machine vision

Several general-purpose algorithms and techniques have been developed for image segmentation. Since there is no general solution to the image segmentation problem, these techniques often have to be combined with domain knowledge in order to effectively solve an image segmentation problem for a problem domain.

Algorithm	Description
Fixed circle (FC) (Eisen, 1999)	Circular mask with constant radius
Adaptive circle (AC) (Buhler et al., 2000)	Circular mask with independently estimated radius for each spot
Seeded region growing (SRG) (Yang et al., 2002)	Segmentation with seeded region growing segmentation algorithm
Mann–Whitney (MW) (Chen et al., 1997)	Computing segmentation threshold iteratively with Mann–Whitney test
k-means (KM) (Bozinov and Rahnenfu¨hrer, 2002)	k-means clustering of pixels
Hybrid k-means (HKM) (Rahnenfu¨hrer and Bozinov, 2004)	k-means clustering of pixels and removing outliers with mask matching
EM (Expectation Maximization)
Markov random field (MRF) (Demirkaya et al., 2005)	MRF modeling of pixels
Model-based segmentation (MBS) (Li et al., 2005)	Model-based clustering of pixels and extraction of connected components
Matarray (MA) (Wang et al., 2001)	Iterative modification of target mask based on spatial and intensity information

Clustering methods

The K-means algorithm is an iterative technique that is used to partition an image into K clusters. The k-means clustering was invented in 1956. The most common form of the algorithm uses an iterative refinement heuristic known as Lloyd's algorithm. The basic i.e., Lloyd's algorithm is:

Partition the input points into k initial sets, either randomly or based on some heuristic, then calculates the mean point, or centroid, of each set as K cluster centers
Assign each pixel in the image to the cluster that minimizes the distance between the pixel and the cluster center
Re-compute the cluster centers by averaging all of the pixels in the cluster
Repeat steps 2 and 3 until convergence is attained (e.g. no pixels change clusters)

In this case, distance is the squared or absolute difference between a pixel and a cluster center. The difference is typically based on pixel color, intensity, texture, and location, or a weighted combination of these factors.

This algorithm is guaranteed to converge, but it may not return the optimal solution. The quality of the solution depends on the initial set of clusters and the value of K.

In statistics and machine learning, the k-means algorithm is clustering algorithm to partition n objects into K clusters, where K < n. It is similar to the expectation-maximization algorithm for Gaussians mixtures in that both attempt to find the centers of natural clusters in the data. In terms of performance the algorithm is not guaranteed to return a global optimum. The quality of the final solution depends largely on the initial set of clusters. Since the algorithm is extremely fast, a common method is to run the algorithm several times and return the best clustering found. A drawback of the k-means algorithm is that the number of clusters K is an input parameter. An inappropriate choice of K may yield poor results. The algorithm also assumes that the variance is an appropriate measure of cluster scatter.

Histogram-based methods

Histogram-based methods are very efficient when compared to other image segmentation methods because they typically require only one pass through the pixels. In this technique, a histogram is computed from all of the pixels in the image, and the peaks and valleys in the histogram are used to locate the clusters in the image. Color or intensity can be used as the measure.

A refinement of this technique is to recursively apply the histogram-seeking method to clusters in the image in order to divide them into smaller clusters. This is repeated with smaller and smaller clusters until no more clusters are formed.

One disadvantage of the histogram-seeking method is that it may be difficult to identify significant peaks and valleys in the image. In this technique of image classification distance metric and integrated region matching are familiar.

Histogram-based approaches can also be quickly adapted to occur over multiple frames, while maintaining their single pass efficiency. The histogram can also be applied on a per pixel basis where the information result are used to determine the most frequent color for the pixel location. This approach segments based on active objects and a static environment, resulting in a different type of segmentation useful in Video tracking.

Edge detection

Edge detection is a well-developed field on its own within image processing. Region boundaries and edges are closely related, since there is often a sharp adjustment in intensity at the region boundaries. Edge detection techniques have therefore been used as the base of another segmentation technique.

The challenge is, the edges identified by edge detection are often disconnected. To segment an object from an image however, one needs closed region boundaries.

Region growing methods

The first region growing method was the seeded region growing method. This method takes a set of seeds as input along with the image. The seeds mark each of the objects to be segmented. The regions are iteratively grown by comparing all unallocated neighboring pixels to the regions. The difference between a pixel's intensity value and the region's mean, δ, is used as a measure of similarity. The pixel with the smallest difference measured this way is allocated to the respective region. This process continues until all pixels are allocated to a region.

Drawback is seeded region growing requires seeds as additional input. The segmentation results are dependent on the choice of seeds. Noise in the image can cause the seeds to be poorly placed.

Unseeded region growing is a modified algorithm that doesn't require explicit seeds. It starts off with a single region A₁ – the pixel chosen here does not significantly influence final segmentation. At each iteration it considers the neighboring pixels in the same way as seeded region growing. It differs from seeded region growing in that if the minimum δ is less than a predefined threshold T then it is added to the respective region A_j. If not, then the pixel is considered significantly different from all current regions A_i and a new region A_n_{+ 1} is created with this pixel.

Graph partitioning methods

Graph partitioning methods can effectively be used for image segmentation. In these methods, the image is modeled as a weighted, undirected graph. Usually a pixel or a group of pixels are associated with nodes and edge weights define the (dis)similarity between the neighborhood pixels. The graph (image) is then partitioned according to a criterion designed to model "good" clusters. Each partition of the nodes (pixels) output from these algorithms are considered an object segment in the image. Some popular algorithms of this category are normalized cuts, random walker, minimum cut, isoperimetric partitioning and minimum spanning tree-based segmentation.

Watershed transformation

The watershed transformation considers the gradient magnitude of an image as a topographic surface. Pixels having the highest gradient magnitude intensities (GMIs) correspond to watershed lines, which represent the region boundaries. Water placed on any pixel enclosed by a common watershed line flows downhill to a common local intensity minimum (LIM). Pixels draining to a common minimum form a catch basin, which represents a segment.

Model based segmentation

The central assumption of such an approach is that structures of interest/organs have a repetitive form of geometry. Therefore, one can seek for a probabilistic model towards explaining the variation of the shape of the organ and then when segmenting an image impose constraints using this model as prior. Such a task involves (i) registration of the training examples to a common pose, (ii) probabilistic representation of the variation of the registered samples, and (iii) statistical inference between the model and the image. State of the art methods in the literature for knowledge-based segmentation involve active shape and appearance models, active contours and deformable templates and level-set based methods.

Neural networks segmentation

Neural Network segmentation relies on processing small areas of an image using an artificial neural network or a set of neural networks. After such processing the decision-making mechanism marks the areas of an image accordingly to the category recognized by the neural network. A type of network designed especially for this is the Kohonen map.

Pulse-Coupled Neural Networks (PCNNs) are neural models proposed by modeling a cat's visual cortex and developed for high-performance biomimetic image processing. In 1989, Eckhorn introduced a neural model to emulate the mechanism of cat's visual cortex. The Eckhorn model provided a simple and effective tool for studying small mammal's visual cortex, and was soon recognized as having significant application potential in image processing. In 1994, the Eckhorn model was adapted to be an image processing algorithm by Johnson, who termed this algorithm as Pulse-Coupled Neural Network. Over the past decade, PCNNs have been utilized for a variety of image processing applications, including: image segmentation, feature generation, face extraction, motion detection, region growing, noise reduction, etc.

A PCNN is a two-dimensional neural network. Each neuron in the network corresponds to one pixel in an input image, receiving its corresponding pixel's color information (e.g. intensity) as an external stimulus. Each neuron also connects with its neighboring neurons, receiving local stimuli from them. The external and local stimuli are combined in an internal activation system, which accumulates the stimuli until it exceeds a dynamic threshold, resulting in a pulse output. Through iterative computation, PCNN neurons produce temporal series of pulse outputs. The temporal series of pulse outputs contain information of input images and can be utilized for various image processing applications, such as image segmentation and feature generation. Compared with conventional image processing means, PCNNs have several significant merits, including robustness against noise, independence of geometric variations in input patterns, capability of bridging minor intensity variations in input patterns, etc.

Open source software

Several open source software packages are available for performing image segmentation

ITK - Insight Segmentation and Registration Toolkit (Open Source)
ITK-SNAP is a GUI tool that combines manual and semi-automatic segmentation with level sets.
GIMP which includes among other tools SIOX (see Simple Interactive Object Extraction)
VXL
ImageMagick
3DSlicer
MITK has a program module for manual segmentation
OpenCV is a computer vision library originally developed by Intel.
GRASS GIS has the program module i.smap for image segmentation
Fiji - Fiji is just ImageJ, an image processing package which includes different segmentation plug-ins.
AForge.NET - an open source C# framework.

Multimedia over IP - 04

2010-10-07T20:38:00.003+05:30

RTCP -- Real-Time Control Protocol

The future Integrated Services Internet will provide means to transmit real-time multimedia data across networks. RSVP, RTP, RTCP and RTSP are the foundation of real-time services. RTCP is the control part of RTP that helps with quality of service and membership management. RTCP is the control protocol designed to work in conjunction with RTP. It is standardized in RFC 1889 and 1890. In an RTP session, participants periodically send RTCP packets to convey feedback on quality of data delivery and information of membership.

Protocol functions -

RTCP provides three basic functions expected to be implemented in all RTP sessions:

The primary function of RTCP is to gather statistics on quality aspects of the media distribution during a session and transmit this data to the session media source and other session participants. Such information may be used by the source for adaptive media encoding (codec) and detection of transmission faults. If the session is carried over a multicast network, this permits non-intrusive session quality monitoring.
RTCP provides canonical end-point identifiers (CNAME) to all session participants. Although a source identifier (SSRC) of an RTP stream is expected to be unique, the instantaneous binding of source identifiers to end-points may change during a session. The CNAME establishes unique identification of end-points across an application instance (multiple use of media tools) and for third-party monitoring.
RTCP reports are expected to be sent by all participants, even in a multicast session which may involve thousands of recipients. Such traffic will increase proportionally with the number of participants. Thus, to avoid network congestion, the protocol must include session bandwidth management. This is achieved by dynamically controlling the frequency of report transmissions. RTCP bandwidth usage should generally not exceed 5% of total session bandwidth. Furthermore, 25% of the RTCP bandwidth should be reserved to media sources at all times, so that in large conferences new participants can receive the CNAME identifiers of the senders without excessive delay.
A fourth, optional feature, is the provisioning of session control functions, because RTCP is a convenient means to reach all session participants, whereas RTP itself is not. RTP is only transmitted by a media source.

Message types

RTCP distinguishes several types of packets: sender report, receiver report, source description, and bye. In addition, the protocol is extensible and allows application-specific RTCP packets. A standards-based extension of RTCP is the Extended Report packet type introduced by RFC 3611 RFC 1889 defines five RTCP packet types to carry control information. These five types are:

RR: Receiver Report

Receiver reports are generated by participants that are not active senders. They contain reception quality feedback about data delivery, including the highest packets number received, the number of packets lost, inter-arrival jitter, and timestamps to calculate the round-trip delay between the sender and the receiver.

SR: Sender Report

Sender reports are generated by active senders. In addition to the reception quality feedback as in RR, they contain a sender information section, providing information on inter-media synchronization, cumulative packet counters, and number of bytes sent.

SDES: Source Description

The Source Description message is used to send the CNAME item to session participants. It may also be used to provide additional information such as the name, e-mail address, telephone number, and address of the owner or controller of the source. They contain information to describe the sources.

BYE: End of participation

A source sends a BYE message to shut down a stream. It allows an end-point to announce that it is leaving the conference. Although other sources can detect the absence of a source, this message is a direct announcement. It is also useful to a media mixer. It indicates end of participation.

APP: Application Specific Functions

The application-specific message provides a mechanism to design application-specific extensions to the RTCP protocol. It is now intended for experimental use as new applications and new features are developed.

Services

Through these control information packets, RTCP provides the following services:

QoS Monitoring And Congestion Control

This is the primary function of RTCP. RTCP provides feedback to an application about the quality of data distribution. The control information is useful to the senders, the receivers and third-party monitors. The sender can adjust its transmission based on the receiver report feedback. The receivers can determine whether congestion is local, regional or global. Network managers can evaluate the network performance for multicast distribution.

Source Identification

In RTP data packets, sources are identified by randomly generated 32-bit identifiers. These identifiers are not convenient for human users. RTCP SDES (source description) packets contain textual information called canonical names as globally unique identifiers of the session participants. It may include user's name, telephone number, email address and other information.

Inter-Media Synchronization

RTCP sender reports contain an indication of real time and the corresponding RTP timestamp. This can be used in inter-media synchronization like lip synchronization in video.

Control Information Scaling

RTCP packets are sent periodically among participants. When the number of participants increases, it is necessary to balance between getting up-to-date control information and limiting the control traffic. In order to scale up to large multicast groups, RTCP has to prevent the control traffic from overwhelming network resources. RTP limits the control traffic to at most 5% of the overall session traffic. This is enforced by adjusting the RTCP generating rate according to the number of participants.

Optimization - 02

2010-10-07T05:05:00.008+05:30

Code Optimization - Inline Functions

Inline function is the optimization technique used by the compilers. One can simply prepend inline keyword/specifier to function prototype to make a function inline. This does not change the behavior of a function itself, but instruct compiler to embed the complete body of the function wherever that function is called, instead of being inserted only once and perform a regular call to it. When we declare a function or member function as inline we are trying to avoid the overhead of a function. If done carefully, this can improve the application's performance in exchange for increased compile time and possibly (but not always) an increase in the size of the generated binary executables.

//The format for its declaration is:

inline type name ( arguments ... )

{

// instructions ...

}

and the call is just like the call to any other function. You do not have to include the inline keyword when calling the function, only in its declaration.

Most compilers already optimize code to generate inline functions when it is more convenient. This specifier only indicates the compiler that inline is preferred for this function.

Optimizations

C++ inline functions present a potential optimization to code: make a function inline and you save the overhead of a function call, Which is: loading parameters onto the stack, making a jump, popping parameters off the stack, and then it all in reverse when you return.

Modern CPUs have pipelines and attempt to optimize code execution on the fly. A function call can disrupt this pipeline when it is encountered, and again, when it returns. So that, not only we are avoiding the function call, but also we potentially allow the CPU to further improve execution.

Not only this, but a compiler may be able to optimize code which has been inlined in a way it cannot if there is a function call simply because the optimization becomes visible, e.g. optimizing register allocations. In the case of empty functions - fairly typical of constructors - making the function inline may allow the compiler to remove the call altogether.

Sometimes an inline function may save time and space. Making a function call requires instruction codes to make the call both on the part of the caller and callee. On occasions the number of bytes required for this may actually be greater than the number of bytes in the function body itself.

Comparison to Macros

Traditionally, in languages such as C, inline expansion was accomplished at the source level using parameterized macros. Use of true inline functions, as are available in C99, provides several benefits over this approach:

Macro invocations do not perform type checking, or even check that arguments are well-formed, whereas function calls usually do.
In C, a macro cannot use the return keyword with the same meaning as a function would do (it would make the function that asked the expansion terminate, rather than the macro). In other words, you cannot make the macro return something which is not the result of the last expression invoked inside it.
Since C macros use mere textual substitution, this may result in unintended side-effects and inefficiency due to re-evaluation of arguments and order of operations.
Compiler errors within macros are often difficult to understand, because they refer to the expanded code, rather than the code the programmer typed.
Many constructs are awkward or impossible to express using macros, or use a significantly different syntax. Inline functions use the same syntax as ordinary functions, and can be inlined and un-inlined at will with ease.
Debugging information for inlined code is usually more helpful than that of macro-expanded code.

Many compilers can also inline expand some recursive functions; recursive macros are typically illegal.

Bjarne Stroustrup, the designer of C++, likes to emphasize that macros should be avoided wherever possible, and advocates extensive use of inline functions.

Inline as a Better Macro

C programmers used to simulate inline functions with macros. C++ inline functions where in part, an attempt to encode this as a language feature rather than yet another use of the macro pre-processor. However, they are not an exact replacement.

If you use a macro the compiler has no desecration, the function will be inlined.
Scope rules are different.
Macros, particularly multi-line macros are much more difficult to understand and maintain.

In short, inline is an improvement on macro, but they are not a direct replacement.

Catches

With these kinds of optimizations available we might wonder why we don't just make all functions inline. Simply, there are downsides, and in my opinion they out weigh the advantages.

For starters inline is only a hint to the compiler, it is free to ignore it. It will typically ignore it if:

The member is a virtual: it's not really possible to have an inline virtual function as virtual implies an indirect function call - although compiler can sometimes do it if it has type information.
The function is recursive or mutually recursive with other functions.
The compiler will also ignore the inline if it considers the body of the function "too big." How big is too big depends on your compiler.

The Other Inline

C++ inline functions are not the only "inlines" supported by most compilers. It is also possible to place assembler code within C++ code and this is commonly referred to as "inline assembler". It's normally clear which type is being talked about, but it's more difficult when doing a keyword search in MSDN or a search engine to pin down what you want.

The days when most systems contained some inline assembler to improve speed are fast receding. Traditionally used to speed up performance critical sections of a program it's now doubtful that even this is possible. Increasingly, to get the best performance out of a CPU requires you to know a lot of things about memory layout, cache architecture, pipelining, out of order execution and so on. While these rules can be encoded in a good compiler it is hard for an individual to know and apply all these rules.

There are a few occasions where inline assembler is still useful though. Microsoft use a little bit in the ATL to "thunk" a function call, and sometimes hard coding a break point in your code (asm { int 03h; } in Intel speak) has it's uses.
Inline code will not be generated when using a variable number of arguments to a function call (e.g. printf would not be inlined) or a variable sized data type, e.g.

void foo(int n)

{

char str[n];

...

}

Compilers have a limit to the depth they will inline functions, e.g. if inline A calls inline B, which calls inline C and so on. This is often configurable through a pragma or command line switch.

Of course, every compiler will differ slightly and you or I can't guarantee that there isn't a compiler out that can inline some of these things. Conversely, there are more reasons why your compiler will not inline a function that those given here. These are clear-cut cases but there are several other reasons why I avoid using inline functions. The main culprit is: code bloat, inline functions usually make your code bigger because you have duplicated code for each invocation of the function. Apart from needing a bigger hard disc code bloat has several implications:

Increased number of CPU cache misses: a CPU may keep a frequently executed function entirely in it's cache, if you increase the function size with lots of inline functions it may be too big for the cache, and because your functions are bigger fewer may be held in cache at once.
Disc cache: if every function is inlined the OS may not load the entire program into memory and your disc will start to thrash.

So, don't be surprised if making methods inline actually makes your program slower!

In addition embedded systems are very sensitive to code bloat: a PC may have a big CPU cache, oodles of fast RAM and a big fast hard disc but an embedded system probably won't. In the extreme this may mean you need to fit your device with a bigger ROM, which means it costs more, which in a competitive market may make the difference between success and failure.

And some more catches...

There are catches which have to do less with an individual piece of code and more with how a system hangs together. These design issues mean you should think carefully before making a method inline:

Coupling between headers and implementation increases because a change is more likely to occur in the header file, which causes a bigger rebuild because other files depend on your header files. If the code is in the implementation file by contrast only that file needs to be recompiled. On large systems the difference can be hours.
Putting the implementation in the header file reduces the opportunity to forward declare classes, so you have to include another header file, increasing coupling; making the code less flexible and more prone to ripple effects - again increasing build times.

Perhaps a more significant point is what a lot of inline functions says about your design. Inlining is typically used forget and set functions. Classes with lots of such functions aren't really hiding anything, they are just containers for values which begs the question, just how object oriented is your design?

Some other points that are worth noting about inlined functions are:

Finding code in source files can be time consuming, if you have lots of inline functions you need to look in the .h files as well as the .cpp files. This may seem trivial but on a large system with several thousand files the time adds up.
If some of your code is compiled with inlining enabled and some with them disabled you will encounter link errors.
Some compilers have an auto-inline function that lets the compiler decide which functions to inline and which to leave as is. Of course, how aggressive this is, and hence how much difference it makes, is dependent on your compiler.
Inlining is usually only enabled when optimised code is being generated, so your debug builds won't have any inlined functions.
Although inline is commonly thought of as a C++ optimisation it is also available in C, and other languages, although these may need vendor specific extensions.
Theoretically each inline function should have one, and only one implementation body. However, it would be possible to provide different bodies in different files. Stroustrup points out in the Design & Evolution of C++ that most compilers don't check for this, we can hope that in the 7 years since he made his comments the situation has improved but I'm not sure. Before anyone think of a use for this "feature" consider the maintenance nightmare and please don't do it.

Seeing inline at work

The most reliable way to see if a function is being inlined or not is to look at the output from the compiler. Most compilers have a switch to output assembler code for your inspection. In Visual C++ there are several /FA which control this - the "listing file type" in the project C++ settings box.

The other switches worth playing with are the /Ob which control the aggressiveness of inline expansion - the "Inline function expansion" option in C++ settings.

It's interesting to experiment with these switches and the following example:

struct Widget {

int number_;

Widget();

int t() const;

};

Widget::Widget() : number_(99) { }

int Widget::t() const

{

return number_;

}

int main()

{

Widget w;

int i = w.t();

return i;

}

It's interesting to make the constructor and t function inline and look at the assembler code, or use the /Ob2 switch to force functions to be inline, at this point the compiler reduces the program to:

push 99

pop eax

The program still comes out at 19,968 bytes, which demonstrates the overhead that even the simplest programs may carry.

When to Use Inlines

Despite all this there are occasions when inlines make sense.

Templates based code is always inlined: this is one of the reasons people believe templates lead to bigger executables.
Sometimes making a function inline will improve performance for all the reasons given at the start.

The orthodox approach to performance today is to design a system for ease of maintenance, flexibility and extendibility, and only consider performance second. Usually, this means producing a working system and then performance profiling, improving the slowest bit and repeating until the system is fast enough.

When you profile your code you may find a hot spot in a function that could benefit from inlining. This is quite understandable, and at this point in the cycle your can afford to sacrifice some maintainability for speed if it is needed. However, after making the change repeat the performance test to ensure it actually does help.

One compromise is to avoid inlining other than for templates. Then as part of the QA or performance cycle use your compilers auto-inline feature. This compromise is not ducking the issue, or delivering code with sub-optimal performance. In fact, it's taking an engineering line, we build something, measure it, and if necessary improve it. (Stroustrup questions if letting the compiler decide is the best policy.)

Advantages

It does not require function calling overhead.
It also save overhead of variables push/pop on the stack, while function calling.
It also save overhead of return call from a function.
It increases locality of reference by utilizing instruction cache.
After in-lining compiler can also apply intraprocedural optmization if specified. This is the most important one, in this way compiler can now focus on dead code elimination, can give more stress on branch prediction, induction variable elimination etc..

Disadvantages

May increase function size so that it may not fit on the cache, causing lots of cahce miss.
After in-lining function if variables number which are going to use register increases than they may create overhead on register variable resource utilization.
It may cause compilation overhead as if some body changes code inside inline function than all calling location will also be compiled.
If used in header file, it will make your header file size large and may also make it unreadable.
If somebody used too many inline function resultant in a larger code size than it may cause thrashing in memory. More and more number of page fault bringing down your program performance.
Its not useful for embeded system where large binary size is not preferred at all due to memory size constraints.

Performance

Now covering the topic which most the people are interested in the "Performance".
In most of the cases Inline function boost performance if used cautiously as it saves lots of overhead as discussed in our Advantages section above but as we have also discussed its disadvantages one need to be very cautious while using them. Today's modern compiler inline functions automatically, so no need to specify explicitly in most of the cases. Although placing inline keyword only gives compiler a hint that this function can be optimized by doing in-lining, its ultimately compiler decision to make it inline. Though there are ways to instruct compiler too, for making a function call inline like one can use __forceinline to instruct compiler to inline a function while working with microsoft visual c++. I suggest not to use this keyword until you are very sure about performance gain. Making a function inline may or may not give you performance boost, it all depends on your code flows too. Don't expect a magical performance boost by prepending inline keyword before a function to your code as most of the compiler nowadays does that automatically.

As we have seen inline function serves in terms of performacen but one has to use it with extreme cautions.

Uses Guidelines

Always use inline function when your are sure it will give performance.
Always prefer inline function over macros.
Don't inline function with larger code size, one should always inline small code size function to get performance.
If you want to inline a function in class, then prefer to use inkine keyword outside the class with the function definition.
In c++, by default member function declared and defined within class get linlined. So no use to specify for such cases.
Your function will not be inlined in case there is differences between exception handling model. Like if caller function follows c++ structure handling and your inline function follows structured exception handling.
For recursive function most of the compiler would not do in-lining but microsoft visual c++ compiler provides a special pragma for it i.e. pragma inline_recursion(on) and once can also control its limit with pragma inline_depth.
If the function is virtual and its called virtually then it would not be inlined. So take care for such cases, same hold true for the use of function pointers.

Conclusion

While inline functions may improve performance seldom will you be able to radically change a program's performance by making a bunch of functions inline. Inlines are not free; they will usually increase your program size and may actually impair performance.

They may also increase your development cycle because they increase coupling between files and lead to longer build times and more ripple effects.

Heavy reliance on inline functions may indicate flaws in your design; either a lack of object-orientedness or failure to design a system with the required performance characteristics.

Optimization - 01

2010-10-07T04:48:00.003+05:30

Porting C Code to the CCS - C6416

Initial Modifications

The first set of modifications to the original base C code is to accommodate multi-channel environments and prevention of stack overflow.

Code Modifications for Multi-Channel Environments

To accommodate multi-channel systems, eliminate global variables and static data in each C module. For each file that contained static or global data, following steps are necessary:

Define a data structure containing the static data variables in header-file.
Add this generated data structure in header-file to the general encoder and decoder channel information.
Perform the former static data initialization explicitly in the encoder/decoder initialization function.
For each function in the original file that used static data:
- Add a pointer to the data structure to the parameter list.
- Replace all static variables referenced in the function body with the variables stored in the data structure whose addresses are received as parameters.
For each function that called any of the functions modified in step 4, add a pointer to the data structure to its parameter list. Repeat this process recursively up to the main encoder/decoder function.

Prevention of stack overflow:

Since default size of stack is fixed K bytes, the large arrays in the functions may cause stack overflow. That is because the local variables are also placed on the stack when the function is called. These are accessed indirectly, which makes processor slow. So add a scratch space for reducing the stack size, which is more efficient way of using the RAM space also.

To perform this, for each function that contained the large arrays, the following steps are necessary to follow:

Define a data structure containing the large arrays in the header-file.
Add this generated data structure in header-file to the general encoder and decoder channel information.
For each function in the original file with the large arrays:
- Add a pointer to the structure to the parameter list.
- Replace all large arrays referenced in the function body with variables stored in the data structure whose addresses are received as parameters.
For each function that called any of the functions modified in step 3, add a pointer to the structure in that to its parameter list. Repeat this process recursively up to the main encoder/decoder function.

In addition, the Word16, Word32, and Flag data types used in the base code should redefine in typedef.h to comply with processor architecture.

Intrinsic Functions

The basic math operations defined in basic_op.c were replaced by corresponding intrinsic functions of TMS320C6416. The compiler recognizes intrinsic operators which can be used like functions to produce assembly language statements otherwise it would not be expressible through standard ANSI C. This optimization allows a call to a DSP specific intrinsic function to be replaced by a copy of the body of that function which can be optimized at the assembly level. This optimization will speedup execution by eliminating function call & return overhead and substitute hand optimized and compiler optimized low level code for high level C intrinsic code. The set of functions defined in the compiler's gsm.h file is substantially richer than the set provided in basic_op.c.

So all basic math operations were easily replaced, with some minor modifications described below that were required to handle overflow and saturation. The basic math operations in basic_op.c simulate two processor flags, Overflow and Carry. The Carry flag is used only inside the basic math operations, so there was no problem in removing it. However, the Overflow flag is set in several functions, and tested in other functions, so it must remain. The Control Status Register is defined in compiler's c6x.h file. The CSR contains control and status bits. The SAT field in this register is set when there is overflow. Because the overflow flag was no longer available as a global variable, the SAT bit is cleared explicitly when the Overflow flag is assigned zero in the original file.

Project-Level Optimizations (Function Inlining)

In general, these techniques improve the performance of both C and assembly code. So apply function inlining to the entire project.

Function inlining (also referred to as 'inline expansion' or simply 'inlining'), is the process of replacing a function call with the body of the function itself. This optimization technique improves execution time by eliminating function call & return overhead at the expense of larger code size.

Profiler information is used to determine whether a function should be inlined or not. Small, frequently called functions are the best candidates for inlining. In general, functions that take fewer than 25 cycles offer the most speed savings by inlining. The overhead to call such a function is typically 20 percent or greater. Functions that take 25–35 cycles and pass several parameters are also worth inlining. Function inlining is done in one of three ways:

Implicitly, allowing the compiler to select the functions to be inlined. This is done by setting the –o3 compiler option.
Explicitly, using the #pragma inline C statement. To inline a function in several files, the function should be placed in a header file, and the static keyword should be used in each file to prevent the linker from generating duplicate global symbols.
Manually replacing a function call with the body of the function.

For example, manual inlining technique -

// Body of the function of L_Extract()is defined as –

void L_Extract(Word32 L_32, Word16 *hi, Word16 *lo)

{

*hi = extract_h(L_32);

*lo = extract_l( L_msu( L_shr(L_32, 1) , *hi, 16384));

return;

}

//Further, intrinsic functions of extract_l() and extract_h() are:

extract_l ( a ) ((a )& 0xffff); and extract_h ( a ) (unsigned(a) >>16);

// Original: L_Extract( ) calls were manually replaced with L_Extract( ) body

L_Extract(sum0, &r_h[i], &r_l[i]);

//Modified: STEP 1

r_h[i] = extract_h(sum0);

r_l[i] = extract_l(L_msu( L_shr(sum0, 1), r_h[i], 16384));

// extract_h( ) and extract_l( ) calls were manually replaced with intrinsic //functions

// Finally: STEP 2

r_h[i] = (unsigned (sum0) >> 16);

r_l[i] = (sum0 & 0xffff);

Implicit and explicit
inlining requires no knowledge of the code and is performed without examining code sections because the compiler automatically tries to interleave consecutive calls. These techniques are recommended when there is only one call to the inlined function.

Manual inlining is recommended when several identical calls are made in sequence, and enables the programmer to fully exploit potential parallelism. By replacing a function call with the C statements of the function, we can place in parallel, by hand, the actions in the function by allocating different variables and performing several consecutive identical calls on phases. This technique requires a working knowledge of the code to identify where a small function is repeatedly called and which actions are executed in parallel. Manual inlining is also used in assembly code.

Within Code Composer Studio, the Build Options are used to set the -o3, -pm op3, -mr1, -mt program-level options that affect all project files.

Collect profile data after the project-level optimizations, and use this as a baseline for further analysis.

Function Level Optimization

The general approach for optimizing each function includes:

Establishing the function interface and separating the function from the rest of the code to facilitate analysis.
Add test code that saves the function input and output values before and after each function call.
Optimize the function and verifying the output to ensure that it remains the same as the corresponding reference output.
Integrate the optimized function with the rest of the code and verify that it passes the test vectors.

Criterion for selecting functions:

The selection of functions for optimization is primarily based on profiling information after the project-level optimizations, focusing on the most time-critical functions. Information provided by the profiler includes: Number of calls per frame. Based on this information, the decision is made whether a small, frequently-called function should be inlined. This information is most useful during the global-level optimizations. Total number of cycles per frame, is the most useful information for selecting the functions to optimize.

Loop Unrolling

Loop unrolling explicitly repeats the body of a loop with corresponding indices. That is expanding the loops so that, each iteration of the loop appears in the code. This optimization technique increases the number of instructions available to execute in parallel. Loop unrolling can be used when the operations in a single iteration do not use all of the resources of the C6000 architecture. Loop unrolling proves quite rewarding in some cases where it gives up to 2% improvement in terms of total number of cycles for each of its applications.

Loop Merging

Combining two or more loops into a single loop loads the ALU more efficiently, as illustrated below. This technique yields up to 1% improvement in terms of total number of cycles for each of its applications. This avoids spending overhead on two separate loops. An example code from Corr_xy2() function is illustrated.

Loop Splitting

Loop splitting refers to the process of breaking a large loop with several variables or pointers into two or more shorter loops and saving the results of the partial computations in local vectors. This technique enables the compiler to allocate registers more efficiently, resulting in substantial performance improvement, especially when combined with other optimization techniques.

Simplifying the Test Conditions

The test conditions were simplified to reduce the amount of computation. e.g. the conditions which involved subtraction were replaced with direct comparisons. This saves a subtraction operation. For example -

/* original if construct */

if( sub(max1, max2) < 0 ){

}

/* modified if construct */

if(max1 < max2){

}

Declaring Local Variables

Variables are declared as close as possible, in the code hierarchy, to their area of use to help the compiler identify their life cycles. This improves register allocation but requires more stack memory. For example -

for(i= -pit_max; i< L_frame; i+=2) {

Word32 sum = 0;

sum = L_mac(sum, signal[i], signal[i]);

}

Replacing Functions by Arithmetic Operators

The right/left shift operator >> is used in a variable shift displacement to save a function call, if overflow or underflow does not occur after a shift operation. Similarly additions, subtractions can be replaced by addition operator +or subtraction operator - after analyzing the code. However, the C operators *, +, - were not applied to operations on fractional values that only employ intrinsic functions, because it is difficult to ascertain whether overflow, underflow or saturation would occur or not. For example -

// Original: subtraction

T0_min = sub(T_op, 3);

// Modified: subtraction

T0_min =T_op- 3;

Pointer Addressing

Accessing array elements using pointers rather than indexing improves the performance greatly. This reduces the overhead of calculating the address. For example, consider the case of a for loop, the overhead involved in calculating the address of y[i] for every element are

Loading the base address of the array
Loading 'i' into the memory
Going to an offset (i) * size (type of array).

// Original:

for (i=0; i<L_WINDOW; i++) {

sum = L_mac(sum, y[i], y[i]);

}

Instead, this overhead can be moved outside the loop, to make the compiler generate faster code as shown in the below example.

//Modified:

Word16 *ptr ;

ptr = &y[0];

for (i=0; i<L_WINDOW; i++) {

sum = _sadd(sum, _smpy(*ptr ++, *ptr++));

}

Function Implementation In Linear Assembly

In general, rewriting C functions in assembly increases speed and reduces code size. However, because of improvements in C compiler performance, the trend is to keep most code in C and optimized C and to implement fewer functions in assembly. The functions to be implemented in assembly were selected based on profiling data.

Usually the user can program a DSP in either C language or in assembly language. The C6000 allows to program in Linear Assembly. Linear Assembly uses exactly the same assembly instructions, but the difference is that it is easier than assembly language to program. This language is processed by the Assembly Optimizer instead of the assembler. The output of which is pure assembly language program. The Assembly Optimizer allows us to write assembly code without being concerned with pipelining structure of C6000 or with assigning of registers. It accepts Linear Assembly code which is assembly code that has not been register allocated and is unscheduled. The Assembly Optimizer assigns register and uses loop optimization to turn linear assembly into highly parallel assembly.

Advantages of Linear Assembly are:

Assembly optimizer is delay slot aware for different instructions. So, we need not write NOP's.
Register scheduling and functional unit specifications is also not required. The assembly optimizer takes care of this. This means that the programmer can use C like variable name in linear assembly instead using of C6000 registers.
Most importantly assembly optimizer takes care of pipelining and parallelism this is huge advantage in VLIW(Very Long Instruction Word) machines with deep pipelines make it a huge challenge for the programmer to write highly pipelined code. We can say that Linear Assembly is a slightly higher level language than pure assembly but retaining about 90% programming efficiency of the hand coded pure assembly.

Functions Selection Criteria:

The entire code is profiled, and the most time-critical functions are identified. The estimates of ideal execution times are compared with the C optimization results. Functions which are near-optimal are retained in the optimized C version and the remainders are candidates to be implemented in assembly.

Conclusion

Porting of C code to the TMS320C6416 and optimizing the code while maintaining the bit-exactness of the original code is important. The recommended approach follows the following key points:

C source optimizations for selected functions.
Linear Assembly implementation of selected time-critical functions.

Do the C optimization of selected functions at both the project and function level. Execution time profile, provided by the profiler, can be used for selecting functions for optimization. The project-level optimizations involve profiling the initially ported code, inlining frequently-called functions, and optimizing the C code so that the compiler produces code that is better adapted to the TMS320C6416 architecture. In the function-level optimization, several techniques including loop unrolling and loop merging are involved. Linear Assembly implementation is the final phase of development because it is very difficult to change the structure of an implementation in linear assembly. Functions targeted for linear assembly implementation are primarily those for which the simulator could not produce efficient code, and those which execute for large number of cycles. Particular emphasis is given to loops, where each cycle saved results in a significant reduction in execution time. The optimized C implementation is used to verify the bit-exactness for the linear assembly and it also provides a pseudo-code for the algorithm.

Sintel - Blender 2.5 Lguana Sculpting

2010-10-05T17:51:00.002+05:30

Sintel - Sintel's Face

2010-10-05T17:47:00.002+05:30

Multimedia over IP - 03

2010-10-03T14:29:00.010+05:30

RTP --- Real-time Transport Protocol

For the future Integrated Services Internet will provide means to transmit real-time multimedia data across networks. RSVP, RTP, RTCP and RTSP are the foundation of real-time services. RTP is the transport protocol for real-time data. It provides timestamp, sequence number and other means to handle the timing issues in real-time data transport. It relies on RVSP for resource reservation to provide quality of service.

Real-time transport protocol (RTP) is an IP-based protocol providing support for the transport of real-time data such as video and audio streams. The services provided by RTP include time reconstruction, loss detection, security and content identification. RTP is primarily designed for multicast of real-time data, but it can be also used in unicast. It can be used for one-way transport such as video-on-demand as well as interactive services such as Internet telephony.

RTP is designed to work in conjunction with the auxiliary control protocol RTCP to get feedback on quality of data transmission and information about participants in the on-going session.

Development

Attempts to send voice over networks began in early 70's. Several patents on packet transmission of speech, time stamp and sequence numbering were granted in 70's and 80's. In 1991, a series of voice experiments were completed on DARTnet. In August 1991, the Network Research Group of Lawrence Berkeley National Laboratory released an audio conference tool vat for DARTnet use. The protocol used was referred later as RTP version 0.

In December 1992 Henning Schulzrinne, GMD Berlin, published RTP version 1. It went through several states of Internet Drafts and was finally approved as an Proposed Standard on November 22, 1995 by the IEFT/IESG. This version was called RTP version 2 and was published as

RFC 1889, RTP: A Transport Protocol for Real-Time Applications
RFC 1890, RTP Profile for Audio and Video Conferences with Minimal Control

On January 31, 1996, Netscape announced "Netscape LiveMedia" based on RTP and other standards. Microsoft claims that their NetMeeting Conferencing Software supports RTP. The latest extensions have been made by an industry alliance around Netscape Inc., who uses RTP as the basis of the Real Time Streaming Protocol RTSP.

RFC References

RFC 4103, RTP Payload Format for Text Conversation
RFC 3984, RTP Payload Format for H.264 Video
RFC 3640, RTP Payload Format for Transport of MPEG-4 Elementary Streams
RFC 3267, Real-Time Transport Protocol (RTP) Payload Format and File Storage for the Adaptive Multi-Rate (AMR) and Adaptive Multi-Rate Wideband (AMR-WB) Audio Codec
RFC 3016, RTP Payload Format for MPEG-4 Audio/Visual Streams
RFC 3551, Standard 65, RTP Profile for Audio and Video Conferences with Minimal Control
RFC 3550, Standard 64, RTP: A Transport Protocol for Real-Time Applications
RFC 2250, Proposed Standard, RTP Payload Format for MPEG1/MPEG2 Video

How does RTP Work

As discussed in the first section, Internt is a shared datagram network. Packets sent on the Internet have unpredictable delay and jitter. But multimedia applications require appropriate timing in data transmission and playing back. RTP provides time stamping, sequence numbering, and other mechanisms to take care of the timing issues. Through these mechanisms, RTP provides end-to-end transport for real-time data over datagram network.

Timestamping is the most important information for real-time applications. The sender sets the timestamp according to the instant the first octet in the packet was sampled. Timestamps increase by the time covered by a packet. After receiving the data packets, the receiver uses the timestamp to reconstruct the original timing in order to play out the data in correct rate. Timestamp is also used to synchronize different streams with timing properties, such as audio and video data in MPEG. However, RTP itself is not responsible for the synchronization. This has to be done in the application level.

UDP does not deliver packets in timely order, so sequence numbers are used to place the incoming data packets in the correct order. They are also used for packet loss detection. Notice that in some video format, when a video frame is split into several RTP packets, all of them can have the same timestamp. So just timestamp is not enough to put the packets in order.

The payload type identifier specifies the payload format as well as the encoding/compression schemes. From this payload type identifier, the receiving application knows how to interpret and play out the payload data. Default payload types are defined in RFC 1890. Example specifications include PCM, MPEG1/MPEG2 audio and video, JPEG video, Sun CellB video, H.261 video streams, et al. More payload types can be added by providing a profile and payload format specification. At any given time of transmission, an RTP sender can only send one type of payload, although the payload type may change during transmission, for example, to adjust to network congestion.

Another function is source identification. It allows the receiving application to know where the data is coming from. For example, in an audio conference, from the source identifier a user could tell who is talking.

The above mechanisms are implemented through the RTP header. Figure 1 shows a RTP packet encapsulated in a UDP/IP packet.

Figure 1: RTP data in an IP packet

RTP is typically run on top of UDP to make use of its multiplexing and checksum functions. TCP and UDP are two most commonly used transport protocols on the Internet. TCP provides a connection-oriented and reliable flow between two hosts, while UDP provides a connectionless but unreliable datagram service over the network. UDP was chosen as the target transport protocol for RTP because of two reasons. First, RTP is primarily designed for multicast, the connection-oriented TCP does not scale well and therefore is not suitable. Second, for real-time data, reliability is not as important as timely delivery. Even more, reliable transmission provided by retransmission as in TCP is not desirable. For example, in network congestion, some packets might get lost and the application would result in lower but acceptable quality. If the protocol insists a reliable transmission, the retransmitted packets could possibly increase the delay, jam the network, and eventually starve the receiving application.

RTP and RTCP packets are usually transmitted using UDP/IP service. However, efforts have been made to make them transport-independent so they can be also run on CLNP(Connectionless Network Protocol), IPX (Internetwork Packet Exchange), AAL5/ATM or other protocols.

In practice, RTP is usually implemented within the application. Many issues, such as lost packet recovery and congestion control, have to be implemented in the application level. To set up an RTP session, the application defines a particular pair of destination transport addresses (one network address plus a pair of ports for RTP and RTCP). In a multimedia session, each medium is carried in a separate RTP session, with its own RTCP packets reporting the reception quality for that session. For example, audio and video would travel on separate RTP sessions, enabling a receiver to select whether or not to receive a particular medium.

An audio-conferencing scenario presented in RFC 1889 illustrates the use of RTP. Suppose each participant sends audio data in segments of 20 ms duration. Each segment of audio data is preceded by an RTP header, and then the resulting RTP message is placed in a UDP packet. The RTP header indicates the type of audio encoding that is used, e.g., PCM. Users can opt to change the encoding during a conference in reaction to network congestion or, for example, to accommodate low-bandwidth requirements of a new conference participant. Timing information and a sequence number in the RTP header are used by the receivers to reconstruct the timing produced by the source, so that in this example, audio segments are contiguously played out at the receiver every 20 ms.

RTP Fixed Header Fields

The RTP header has the following format:

Figure 2: RTP Packet Header

The RTP header has a minimum size of 12 bytes. After the header, optional header extensions may be present. This is followed by the RTP payload, the format of which is determined by the particular class of application. The fields in the header are as follows:

Version: (2 bits) Indicates the version of the protocol. Current version is 2.

P (Padding): (1 bit) Used to indicate if there are extra padding bytes at the end of the RTP packet. Padding might be used to fill up a block of certain size, for example as required by an encryption algorithm.

X (Extension): (1 bit) Indicates presence of an Extension header between standard header and payload data. This is application or profile specific.

CC (CSRC Count): (4 bits) Contains the number of CSRC identifiers (defined below) that follow the fixed header.

M (Marker): (1 bit) Used at the application level and defined by a profile. If it is set, it means that the current data has some special relevance for the application.

PT (Payload Type): (7 bits) Indicates the format of the payload and determines its interpretation by the application. This is specified by an RTP profile. For example, see RTP Profile for audio and video conferences with minimal control (RFC 3551).

Sequence Number: (16 bits) The sequence number is incremented by one for each RTP data packet sent and is to be used by the receiver to detect packet loss and to restore packet sequence. The RTP does not take any action when it sees a packet loss, but it is left to the application to take the desired action. For example, video applications may play the last known frame in place of the missing frame. According to RFC 3550, the initial value of the sequence number should be random to make known-plaintext attacks on encryption more difficult. RTP provides no guarantee of delivery, but the presence of sequence numbers makes it possible to detect missing packets.

Timestamp: (32 bits) Used to enable the receiver to play back the received samples at appropriate intervals. When several media streams are present, the timestamps are independent in each stream, and may not be relied upon for media synchronization. The granularity of the timing is application specific. For example, an audio application that samples data once every 125 µs (8 kHz, a common sample rate in digital telephony) could use that value as its clock resolution. The clock granularity is one of the details that is specified in the RTP profile or payload format for an application.

SSRC: (32 bits) Synchronization source identifier uniquely identifies the source of a stream. The synchronization sources within the same RTP session will be unique.

CSRC: Contributing source IDs enumerate contributing sources to a stream which has been generated from multiple sources.

Extension header: (optional) The first 32-bit word contains a profile-specific identifier (16 bits) and a length specifier (16 bits) that indicates the length of the extension (EHL=extension header length) in 32-bit units, excluding the 32 bits of the extension header.

Profiles and Payload formats

One of the design considerations of the RTP was to support a range of multimedia formats (such as H.264, MPEG-4, MJPEG, MPEG, etc.) and allow new formats to be added without revising the RTP standard. The design of RTP is based on the architectural principle known as Application Level Framing (ALF). The information required by a specific application needs are not present in the generic RTP header and are specified by RTP Profiles and Payload formats. For each class of application (e.g., audio, video), RTP defines a profile and one or more associated payload formats.

The Profile defines the codecs used to encode the payload data and their mapping to payload format codes in the Payload Type (PT) field of the RTP header (see below). Each profile is accompanied by several payload format specifications, each of which describes the transport of a particular encoded data. Some of the audio payload formats include: G.711, G.723, G.726, G.729, GSM, QCELP, MP3, DTMF etc., and some of the video payload formats include: H.261, H.263, H.264, MPEG etc.

Examples of RTP Profiles include:

The RTP profile for Audio and video conferences with minimal control (RFC 3551) defines a set of static payload type assignments, and a mechanism for mapping between a payload format, and a payload type identifier (in header) using Session Description Protocol (SDP).
The Secure Real-time Transport Protocol (SRTP) (RFC 3711) defines a profile of RTP that provides cryptographic services for the transfer of payload data.

A complete specification of RTP for a particular application usage will require a profile and/or payload format specification(s).

RTP-Based Systems

A complete network based system will include other protocols and standards in conjunction with RTP. Protocols like SIP, RTSP, H.225 and H.245 are used for session initiation, control and termination. Other standards like H.264, MPEG, H.263 etc., are used to encode the payload data (specified via RTP Profile).

An RTP sender captures the multimedia data, which are then encoded as frames and transmitted as RTP packets, with appropriate timestamps and increasing sequence numbers. Depending on the RTP Profile in use, the Payload Type field is set. The RTP receiver, captures the RTP packets, and may perform reordering of packets, which may have resulted because of the underlying IP network and the frames are decoded depending on the payload format and presented to the end user.

RTP Features

RTP provides end-to-end delivery services for data with real-time characteristics, such as interactive audio and video. But RTP itself does not provide any mechanism to ensure timely delivery. It needs support from lower layers that actually have control over resources in switches and routers. RTP depends on RSVP to reserve resources and to provide the requested quality of service.

RTP doesn't assume anything about the underlying network, except that it provides framing. RTP is typically run on the top of UDP to make use of its multiplexing and checksum service, but efforts have been made to make RTP compatible with other transport protocols, such as ATM AAL5 and IPv6.

Unlike usual data transmission, RTP does not offer any form of reliability or flow/congestion control. It provides timestamps, sequence numbers as hooks for adding reliability and flow/congestion control, but how to implement is totally left to the application.

RTP is a protocol framework that is deliberately not complete. It is open to new payload formats and new multimedia software. By adding new profile and payload format specifications, one can tailor RTP to new data formats and new applications.

RTP/RTCP provides functionality and control mechanisms necessary for carrying real-time content. But RTP/RTCP itself is not responsible for the higher-level tasks like assembly and synchronization. These have to be done at application level.

The flow and congestion control information of RTP is provided by RTCP sender and receiver reports.

RTP Implementation Resources

RTP is an open protocol that does not provide pre-implemented system calls. Implementation is tightly coupled to the application itself. Application developers have to add the complete functionality in the application layer by themselves. However, it is always more more efficient to share and reuse code rather than starting from scratch. The RFC 1889 specification itself contains numerous code segments that can be borrowed directly to the applications. There are some implementations with source code available on the web for evaluation and educational purposes. Many modules in the source code can be usable with minor modifications. The following is a list of useful resources:

vat (http://www-nrg.ee.lbl.gov/vat/)
rtptools(ftp://ftp.cs.columbia.edu/pub/schulzrinne/rtptools/)
NeVoT(http://www.cs.columbia.edu/~hgs/rtp/nevot.html)
RTP page (http://www/cs.columbia.edu/~hgs/rtp) maintained by Henning Schulzrinne is a very complete reference.
RTP Library (http://www.cs.columbia.edu/~jdrosen/rtp_api.html) provides a high level interface for developing applications that make use of the Real Time Transport Protocol (RTP).

FAQs: Transformation and Quantization

2010-10-02T23:06:00.011+05:30

FAQs: Transformation and Quantization

1) What type of transformation is used in H.264?

Ans: H.264 uses an adaptive transform of block size, 4 x 4 and 8 x 8 (High Profiles only), whereas previous video coding standards used the 8 x 8 DCT. The smaller block size leads to a significant reduction in ringing artifacts. And for improved compression efficiency, H.264 also employs a hierarchical transform structure, in which the DC coefficients of neighboring 4 x 4 transforms for the luma signals are grouped into 4 x 4 blocks and transformed again by the Hadamard transform.

2) Why Hardmard transform is neccesary and when this transform will apply?

Ans: For blocks with mostly flat pel values, there is significant correlation among transform DC coefficients of neighboring blocks. Therefore, the standard specifies the 4 x 4 Hadamard transform for luma DC coefficients for 16 x 16 Intra-mode only, and 2 x 2 Hadamard transform for chroma DC coefficients, in 4:2:0 format. For 4:2:2 and 4:4:4 formats, the Hadamard block size is increased to reflect the enlarged block.

3) what is the adentage of having transformation block size 4x4?

Ans: The size of H.264 transforms is mainly 4×4, in special cases 2×2 (8x8 in High Profile). This smaller block size of 4×4 instead of 8×8 enables the encoder to better adapt the prediction error coding to the boundaries of moving objects, to match the transform block size with the smallest block size of the motion compensation, and to generally better adapt the transform to the local prediction error signal.

4) How transformation and quantization procedure is modified to avoid complex

DCT multiplications?

Ans: For simple implementation, the exact transform process is modified to avoid the multiplications. Then the transform and quantization are combined by the modified forward integer transform, post-scaling, and quantization for the encoding; and inverse quantization, pre-scaling, and inverse integer transform for the decoding.

5) is this H.264 supports Perceptual-based quantization scaling matrices there any changes in the quantization procedure?

Ans: Yes, The High Profiles support the perceptual-based quantization scaling matrices as same concept used in MPEG-2. The encoder can specify a matrix for scaling factor according to the specific frequency associated with the transform coefficient for use in inverse quantization scaling by the decoder. This allows the optimization of the subjective quality according to the sensitivity of the human visual system, less sensitive to the coded error in high frequency transform coefficients. It typically does not improve objective fidelity as measured by mean-squared error (or, equivalently, PSNR), but it does improve subjective fidelity, which is really the more important criterion.

6) is there any default scaling matrix is defined in H.264?

Ans: Yes.

7)And any ways to develop dynamic matrices?

Ans: Yes, by defining 2 QPs and using logarithemic/laplacian or any other distributions, we can generate perceptual-based quantization scaling matrices.

8) How many transform are applied in H.264?

Ans: Three different types of transforms are used.

The first type is applied to all samples of all prediction error blocks of the luminance component Y and also for all blocks of both chrominance components Cb and Cr regardless of whether motion compensated prediction or intra prediction was used. The size of this transform is 4×4. Its transform matrix H1 is shown in Figure 1.

If the macroblock is predicted using the type INTRA_16×16, the second transform, a Hadamard transform with matrix H2 (see Figure 1), is applied in addition to the first one. It transforms all 16 DC coefficients of the already transformed blocks of the luminance signal. The size of this transform is also 4×4.

The third transform is also a Hadamard transform but of size 2×2. It is used for the transform of the 4 DC coefficients of each chrominance component. Its matrix H3 is shown in Figure 1.

Figure 1: Matrices of 3 Different transforms applied in H.264/AVC

9) What is the transmission order in H.264, in INTRA_16X16?

Ans: The transmission order of all coefficients is shown in Figure 2. If the macroblock is predicted using the intra prediction type INTRA_16×16 the block with the label "−1" is transmitted first. This block contains the DC coefficients of all blocks of the luminance component. Afterwards all blocks labeled "0"–"25" are transmitted whereas blocks "0"–"15" comprise all AC coefficients of the blocks of the luminance component. Finally, blocks "16" and "17" comprise the DC coefficients and blocks "18"–"25" the AC coefficients of the chrominance components.

Figure 2: The Transmission Order of all Coefficients

10) Compared to previous coding algorithm how H.264 transformation technique is really good?

Ans: Yes, Compared to a DCT, all applied integer transforms have only integer numbers ranging from −2 to 2 in the transform matrix (see eqns 6, 11, 12). This allows computing the transform and the inverse transform in 16-bit arithmetic using only low complex shift, add, and subtract operations.

In the case of a Hadamard transform, only add and subtract operations are necessary. Furthermore, due to the exclusive use of integer operations mismatches of the inverse transform are completely avoided which was not the case in former standards and caused problems.

H.264 - Transformation

2010-10-02T21:05:00.012+05:30

Transformation and Quantization

Both source pictures and prediction residuals have high spatial redundancies. H.264 Standard is based on the use of a block-based transform for spatial redundancy removal. After inter prediction from previously-decoded samples in other pictures or spatial-based prediction from previously-decoded samples within the current picture, the resulting prediction residual is split into 4 x 4 or 8 x 8 blocks. These are converted into the transform domain where they are quantized.

H.264 uses an adaptive transform block size, 4 x 4 and 8 x 8 (High Profiles only), whereas previous video coding standards used the 8 x 8 DCT. The smaller block size leads to a significant reduction in ringing artifacts. Also, the 4 x 4 transform has the additional benefit of removing the need for multiplications.

For improved compression efficiency, H.264 also employs a hierarchical transform structure, in which the DC coefficients of neighboring 4 x 4 transforms for the luma signals are grouped into 4 x 4 blocks and transformed again by the Hadamard transform.

For blocks with mostly flat pel values, there is significant correlation among transform DC coefficients of neighboring blocks. Therefore, the standard specifies the 4 x 4 Hadamard transform for luma DC coefficients for 16 x 16 Intra-mode only, and 2 x 2 Hadamard transform for chroma DC coefficients.

In some applications, it is desired to reduce the quantization step size to improve PSNR to levels that can be considered visually lossless. To achieve this, the H.264 extends the quantization step sizes QP by two additional octaves, redefining the tables and allowing QP to vary from 0 to 51.

In general transform and quantization require several multiplications resulting in high complexity for implementation. So, for simple implementation, the exact transform process is modified to avoid the multiplications. Then the transform and quantization are combined by the modified integer forward transform, quantization, scaling.

Described below are the steps for the forward integer transform, post-scaling, and quantization for the encoding; and inverse quantization, pre-scaling, and inverse integer transform for the decoding.

Encoding Process

Step 1: Forward Integer Transform

For DCT transform of a 4 x 4 input luma data F, the exact formula is as follows:

where, H is a matrix of

The variables a, b, c are as follows:

However, in order to simplify the implementation of the transform, c is approximated by 0.5. For ensuring orthogonality, b also needs to be modified so that:

Multiplication in the transform process is avoided by integrating it with the quantization. So, equation (1) is modified as

where

The symbol denotes the element by element multiplication of the corresponding matrices.

In step 1, only integer transform is implemented without multiplication term SF. The term SF is combined with quantization in step 2.

Step 2: Post-Scaling and Quantization

A transformed and quantized signal Y is obtained by SF ('post-scaling') and quantization with step size Qstep. H.264 defines a total of 52 values for Qstep.

Decoding Process

Step 1: Inverse Quantization and Pre-Scaling

A received signal Y in the decoder is scaled with Qstep and SF as the inverse quantization and a part of inverse transform.

Step 2: Inverse Integer Transform

where, inverse integer transform matrix is

Additionally, for luma (4 x 4) DC coefficients in 16 x 16 Intra-mode, 2D Hadamard transform is applied. This is a hierarchical transform.

Also, for chroma DC coefficients in 4:2:0 format, the transform matrix is as follows. For 4:2:2 and 4:4:4 formats, the Hadamard block size is increased to reflect the enlarged block.

The following integer DCT matrix is applied to 8 x 8 luma components, defined only in High Profiles.

Note that only 4x4 IntDCT is always applied to chroma components.

FRExtensions suggest default perceptual weighting matrices for (4x4) and (8x8) IntDCT coefficients. Scaling matrix reflecting visual perception is simply a multiplier applied during the inverse quantization. (This, itself is a multiplication) Weighting matrices can be customized separately for 4x4 Intra Y, 4x4 Intra Cb, Cr, 4x4 Inter Y, 4x4 Inter Cb, Cr, 8x8 Intra Y and 8x8 Inter Y. Besides these two new schemes, FRExt has added entropy-coded transform-bypass lossless macroblocks, residual color transform for efficient RGB coding without color format conversion loss or bit expansion and 9 intra 8x8 prediction modes.

Encoder can design and use customized perceptual scaling matrices. These are to be sent to the decoder at the sequence or picture level. Default scaling matrix for (8x8) IntDCT coefficients is shown below.

In FRExt, two scans similar to 4x4 transform switched for frame/field coding are shown. Coefficient scanning is based on the decreasing variances and to maximize number of zero-valued coefficients along the scan.

Figure 1: Coefficient scanning order in (a) Frame and (b) Field modes

If a macroblock is compressed using the 4x4 transform in the field mode, the scanning order of the coefficients is modified to be more efficient for field scanning as shown in Fig. 4b – reflecting the decreased correlation of the source data in the vertical dimension. For other block sizes (8x8 for luma, 2x2 for 4:2:0 chroma DC, and 2x4 for 4:2:2 chroma DC), the same basic concepts apply, with scan orders specified for each block size.

Quantization Scaling Matrices

The High Profiles support the perceptual-based quantization scaling matrices as same concept used in MPEG-2. The encoder can specify a matrix for scaling factor according to the specific frequency associated with the transform coefficient for use in inverse quantization scaling by the decoder. This allows the optimization of the subjective quality according to the sensitivity of the human visual system, less sensitive to the coded error in high frequency transform coefficients. It typically does not improve objective fidelity as measured by mean-squared error (or, equivalently, PSNR), but it does improve subjective fidelity, which is really the more important criterion. Default values for the quantization scaling matrices are specified in the standard, and the encoder can choose to instead use customized values by sending a representation of those values at the sequence or picture level.

For the quantization scaling, (8) and (9) are modified as follows.

where w_ij is a scaling factor.

Transform Coding

The transmission order of all coefficients is shown in Figure 1. If the macroblock is predicted using the intra prediction type INTRA_16×16 the block with the label "−1" is transmitted first. This block contains the DC coefficients of all blocks of the luminance component. Afterwards all blocks labeled "0"–"25" are transmitted whereas blocks "0"–"15" comprise all AC coefficients of the blocks of the luminance component. Finally, blocks "16" and "17" comprise the DC coefficients and blocks "18"–"25" the AC coefficients of the chrominance components.

Figure 2: Transmission order of all coefficients of a macroblock

Compared to a DCT, all applied integer transforms have only integer numbers ranging from −2 to 2 in the transform matrix (see eqns 6, 11, 12). This allows computing the transform and the inverse transform in 16-bit arithmetic using only low complex shift, add, and subtract operations.

All coefficients are quantized by a scalar quantizer. The quantization step size is chosen by a so called quantization parameter QP which supports 52 different quantization parameters, shown in figure 3. The step size doubles with each increment of 6 of QP. An increment of QP by 1 results in an increase of the required data rate of approximately 12.5%. The wide range of quantizer step sizes makes it possible for an encoder to accurately and flexibly control the trade-off between bit rate and quality. The values of QP may be different for luma (Y) and chroma (C); both parameters are in the range 0-51 but QP_Chroma is derived from QP_Y so that it QP_C is less that QP_Y for values of QP_Y above 30. A user-defined offset between QP_Y and QP_C may be signalled in a Picture Parameter Set.

Protect Worksheet, 2007

2010-10-02T03:32:00.014+05:30

How to lock cell, column or row in worksheet, 2007?

If You Want the Majority of Cells Locked

To lock the majority of the cells on the worksheet, follow these steps:

Select the cells that you want to remain unprotected. To select nonadjacent (noncontiguous) cells, hold down CTRL and click the cells that are to remain unprotected.
On the Home menu, click Format submenu, click Format Cells… option OR Right click on the selected cells click Format Cells… option
and then click the Protection tab.
Click to clear the Locked check box and click OK.
On the Home menu, click to Format submenu, and then click Protect Sheet…. Option, Type a password if you want one, and then click OK.

If You Want the Majority of Cells Unlocked

To leave the majority of the cells on the worksheet unlocked, follow these steps:

Select the entire worksheet by clicking the Select All button (the gray rectangle in the upper-left corner of the worksheet where the row 1 and column A headings meet), or by pressing CTRL+A or CTRL+SHIFT+SPACEBAR.
On the Home menu, click Format submenu, click Format Cells… option, and then click the Protection tab. Click to clear the Locked check box and click OK.
Select the cells that you want to protect. To select nonadjacent (noncontiguous) cells, hold down CTRL and click the cells that you want to protect.
On the Home menu, click Format submenu, click Format Cells… option, and then click the Protection tab. Click to select the Locked check box, and then click OK.
On the Home menu, click to Format submenu, and then click Protect Sheet…. Option, Type a password if you want one, and then click OK.

You will find that you can only type data in the cells that you selected.

Note: You can reach Protect Sheet... option from Review menu also, see the below figures.

Figure 1: Format Cells… option

Figure 2: Format Cells Window

Figure 3: Protect Sheet Window

Figure 4: Protect Sheet Submenu

Multimedia over IP - 01

2010-10-01T19:55:00.010+05:30

Multimedia over IP - Introduction

Internet will provide means to transmit real-time multimedia data across networks. RSVP, RTP, RTCP and RTSP are the foundation of real-time services.

Figure 1: Multimedia Communication Demand

Multimedia Networking: Goals and Challenges

Computer networks were designed to connect computers on different locations so that they can share data and communicate. In the old days, most of the data carried on networks was textual data. Today, with the rise of multimedia and network technologies, multimedia has become an indispensable feature on the Internet. Animation, voice and video clips become more and more popular on the Internet. Multimedia networking products like Internet telephony, Internet TV, video conferencing have appeared on the market. In the future, people would enjoy other multimedia products in distance learning, distributed simulation, distributed work groups and other areas.

For networkers, multimedia networking is to build the hardware and software infrastructure and application tools to support multimedia transport on networks so that users can communicate in multimedia. Multimedia networking will greatly boost the use of computer as a communication tool. We believe someday multimedia networks will replace telephone, television and other inventions that had dramatically changed our life.

The Real-time Challenge

However, multimedia networking is not a trivial task.

Figure 2: Mission Critical Applications

We can expect at least three difficulties.

1) First, compared with traditional textual applications, multimedia applications usually require much higher bandwidth. A typical piece of 25 second 320x240 QuickTime movie could take 2.3MB, which is equivalent to about 1000 screens of textual data.

2) Second, most multimedia applications require the real-time traffic. Audio and video data must be played back continuously at the rate they are sampled. If the data does not arrive in time, the playing back process will stop and human ears and eyes can easily pick up the artifact. In Internet telephony, human beings can tolerate a latency of about 250 milliseconds. If the latency exceeds this limit, the voice will sound like a call routed over a long satellite circuit and users will complain about the quality of the call. In addition to the delay, network congestion also has more serious effects on real-time traffic. If the network is congested, the only effect on non-real-time traffic is that the transfer takes longer to complete, but real-time data becomes obsolete and will be dropped if it doesn't arrive in time. If proper reaction is not taken, the retransmission of lost packets would aggravate the situation and jam the network.

3) Third, multimedia data stream is usually bursty. Just increasing the bandwidth will not solve the burstiness problem. For most multimedia applications, the receiver has a limited buffer. If no measure is taken to smooth the data stream, it may overflow or underflow the application buffer. When data arrives too fast, the buffer will overflow and the some data packets will be lost, resulting in poor quality. When data arrives too slowly, the buffer will underflow and the application will starve.

Contrary to the high bandwidth, real-time and bursty traffic of multimedia data, in real life, networks are shared by thousands and millions of users, and have limited bandwidth, unpredictable delay and availability. How to solve these conflicts is a challenge multimedia networking must face.

The possibility of answering this challenge comes from the existing network software architecture and fast developing hardware. The basis of Internet, TCP/IP and UDP/IP, provides a range of services that multimedia applications can use. Fast networks like Gigabit Ethernet, FDDI, and ATM provide high bandwidth required by digital audio and video.

So the design of real-time protocols for multimedia networking becomes imperative before the multimedia age comes.

Multimedia Over Internet

There are other ways to transmit multimedia data, like dedicated links, cables and ATM. However, the idea of running multimedia over Internet is extremely attractive.

Dedicated links and cables are not practical because they require special installation and new software. Without an existing technology like LAN, WAN, the software development will be extremely expensive. ATM was said to be the ultimate solution for multimedia because it supports very high bandwidth, is connection-oriented and can tailor different level of quality of service to different type of applications. But at this moment, very few users have ATM networks reaching their organization; even fewer have ATM connections to their desktops.

Figure 3: Media over ATM Access

On the other hand, the Internet is growing exponentially. The well established LAN and WAN technologies based on IP protocol suite connect bigger and bigger networks all over the world to the Internet. In fact, Internet has become the platform of most networking activities. This is the primary reason to develop multimedia protocols over Internet. Another benefit of running multimedia over IP is that users can have integrated data and multimedia service over one single network, without investing on network hardware and building the interface between two networks.

At current time, IP and Ethernet seem to be more favored in the desktops and LANs, with ATM in wide area networks. As a shared datagram network, Internet is not naturally suitable for real-time traffic. To run multimedia over Internet, several issues must be solved.

1) First, multimedia means extremely dense data and heavy traffic. The hardware has to provide enough bandwidth.

2) Second, multimedia applications are usually related to multicast, i.e., the same data stream, not multiple copies, is sent a group of receivers. For example, in video conference, the video data need to be sent to all participants at the same time. Live video can be sent to thousands of recipients. The protocols designed for multimedia applications must take into account multicast in order to reduce the traffic.

3) Third, the price tag attached shared network resources is unpredictable availability. But real-time applications require guaranteed bandwidth when the transmission takes place. So there must be some mechanisms for real-time applications to reserve resources along the transmission path.

4) Fourth, Internet is a packet-switching datagram network where packets are routed independently across shared networks. The current technologies cannot guarantee that real-time data will reach the destination without being jumbled and jerky. Some new transport protocols must be used to take care of the timing issues so that audio and video data can be played back continuously with correct timing and synchronization.

5) Fifth, there should be some standard operations for applications to manage the delivery and present the multimedia data.

The Solution

The Internet carries all types of traffic; each type has different characteristics and requirements. For example, a file transfer application requires that some quantity of data is transferred in an acceptable amount of time, while Internet telephony requires that most packets get to the receiver in less than 0.3 seconds. If enough bandwidth is available, best-effort service fulfills all of these requirements. When resources are scarce, however, real-time traffic will suffer from the congestion.

The solution for multimedia over IP is to classify all traffic, allocate priority for different applications and make reservations. The Integrated Services working group in the IETF (Internet Engineering Task Force) developed an enhanced Internet service model called Integrated Services that includes best-effort service and real-time service, see RFC 1633. The real-time service will enable IP networks to provide quality of service to multimedia applications. Resource ReServation Protocol (RSVP), together with Real-time Transport Protocol (RTP), Real-Time Control Protocol (RTCP), Real-Time Streaming Protocol (RTSP), provides a working foundation for real-time services. Integrated Services allows applications to configure and manage a single infrastructure for multimedia applications and traditional applications. It is a comprehensive approach to provide applications with the type of service they need and in the quality they choose.

Figure 4: Streaming Architecture

Figure 4 depicts a typical streaming session, in which a piece of media content is delivered from a server to a client on-demand. The client requests the media using RTSP, and receives a description of how to access and decode the media flows for this session. The media are transported using RTP/UDP, and RTCP may be used to feed reception statistics back to the server.

Let us see in depth details of these internet protocols in future articles.

Multiview Video Coding - 01

2010-09-30T13:34:00.022+05:30

Multiview Video Coding

Introduction:

The need for multiview video coding is driven by two recent technological developments: new 3D video/display technologies and the growing use of multi-camera arrays. A variety of companies are starting to produce 3D displays that do not require glasses and can be viewed by multiple people simultaneously. The immersive experience provided by these 3D displays are compelling and have the potential to create a growing market for 3D video and hence for multiview video compression. Furthermore, even with 2D displays, multi-camera arrays are increasingly being used to capture a scene from many angles. The resulting multiview data sets allow the viewer to observe a scene from any viewpoint and serve as another application of multiview video compression.

In July 2008, MPEG officially approved an amendment of the ITU-T Rec. H.264 & ISO/IEC 14996-10 Advanced Video Coding (AVC) standard on Multiview Video Coding. MVC is an extension of the AVC/H.264 standard that provides efficient encoding or compressed representation of sequences captured simultaneously from multiple cameras by exploiting correlation among neighboring camera views. MVC is intended for encoding stereoscopic (two-view) video, as well as free viewpoint television and multi-view 3D television applications. The Stereo High profile has been standardized in June 2009; the profile is based on MVC toolset and is used in stereoscopic Blu-ray 3D releases.

MVC stream is backward compatible with H.264/AVC, which allows older devices and software to decode stereoscopic video streams, ignoring additional information for the second view. 3D video (3DV) and free viewpoint video (FVV) are new types of visual media that expand the user's experience beyond what is offered by 2D video. 3DV offers a 3D depth impression of the observed scenery, while FVV allows for an interactive selection of viewpoint and direction within a certain operating range. A common element of 3DV and FVV systems is the use of multiple views of the same scene that are transmitted to the user.

The overall structure of MVC defining the interfaces is illustrated in the figure below. The encoder receives N temporally synchronized video streams and generates one bitstream. The decoder receives the bitstream, decodes and outputs the N video signals.

Fig 1: Multiview Video Coding (MVC)

Multiview video contains a large amount of inter-view statistical dependencies, since all cameras capture the same scene from different viewpoints. Therefore, combined temporal and inter-view prediction is the key for efficient MVC. As illustrated in the figure below a picture of a certain camera can not only be predicted from temporally related pictures of the same camera. Also pictures of neighboring cameras can be used for efficient prediction.

Fig 2: Temporal/inter-view prediction structure for MVC

Application Areas:

Stereo Scope Video
3D Video/Display
Free Viewpoint Video

Topics Related to MVC:

Multiview Coding Structures
Multiview Coding Tools
Inter-view Prediction
Illumination Compensation
Disparity, Depth and 3D Geometry Coding
View Interpolation Prediction
Scene Analysis and View Synthesis
Random Access Aspects in MVC
Multiview Communication Systems
Multiview Coding Applications
Performance and Complexity Issues in MVC

Post a Video to Blog from YouTube

2010-09-29T07:49:00.005+05:30

How do I post a video to my blog from YouTube?

If you've got your own videos on your computer that you want to share on your blog, Blogger now allows you to upload video directly!

If you'd like to share a video from YouTube, you can do that, too.

Embedding a YouTube Video

To embed a video from YouTube, just copy the code from the "Embed" box on the video's YouTube page. You can find the "Embed" box in the "About This Video" box when you're watching the video. You can also get the code from the "Embed HTML" box on the "Edit Video" page if the video belongs to your YouTube account. Or simply right click on the video and copy the "embedded html code".

To embed a YouTube video within a blog post, first click "Edit HTML" from within the post editor. Next, paste the video's code into the body of your post. That's it!

Set Up One-Click Video Sharing

If you post YouTube videos to your blog regularly, sharing directly from YouTube is even easier and you'll only have to set it up once.

Click the "Share" button on the YouTube video's page
Scroll down and click "Setup your blog for video posting."
Click "Add a Blog/Site"
Choose "Blogger" as your Blog Service and fill in your Google Account login information.
Choose which blogs you'd like to add to your YouTube account. You can choose more than one.
From now on, when you click "Share", you'll be given the option to post YouTube videos directly to your blogs!

Language Setting on youtube.com

2010-09-29T07:35:00.003+05:30

In the main of youtube page (www.youtube.com)
click the "भाषा" at the bottom of the page, this will show you available languages...

H.264 – Inter Prediction

2010-09-26T06:51:00.009+05:30

H.264 Video Codec - Inter Prediction

Inter prediction is to reduce the temporal correlation with help of motion estimation and compensation. In H.264, the current picture can be partitioned into the macroblocks or the Submacroblock. In addition to the intra macroblock coding types, various predictive or motion-compensated coding types are allowed in P slices. Each P-type macroblock is partitioned into fixed size blocks used for motion description. Partitionings with luma block sizes of 16 × 16, 16 × 8, 8 × 16, and 8 × 8 samples are supported by the syntax. When the macroblock is partitioned into four so-called sub-macroblocks each of size 8 × 8 luma samples, one additional syntax element is transmitted for each 8 × 8 sub-macroblock. This syntax element specifies whether the corresponding sub-macroblock is coded using motion-compensated prediction with luma block sizes of 8 × 8, 8 × 4, 4 × 8, or 4 × 4 samples. Figure 1 illustrates the partitioning. The prediction signal for each predictivecoded M × N luma block is obtained by displacing a corresponding area of a previously decoded reference picture, where the displacement is specified by a translational motion vector and a picture reference index. Thus, if the macroblock is coded using four 8 × 8 sub-macroblocks, and each sub-macroblock is coded using four 4 × 4 luma blocks, a maximum of 16 motion vectors may be transmitted for a single P-slice macroblock.A macroblock of 16X16 luma samples can be partitioned into smaller block sizes up to 4X4.

Figure 1: Portioning of Macroblock an Submacroblock for Inter Prediction

The smaller block size requires larger number of bits to signal the motion vectors and extra data of the type of partition, however the motion compensated residual data can be reduced. Therefore, the choice of partition size depends on the input video characteristics. In general, a large partition size is appropriate for homogeneous areas of the frame and a small partition size may be beneficial for detailed areas. In former standards as MPEG-4 or H.263, only blocks of the size 16×16 and 8×8 are supported. The inter prediction process can form segmentations for motion representation as small as 4X4 luma samples in size, using motion vector accuracy of one-quarter of the luma sample.

A displacement vector is estimated and transmitted for each block, refers to the corresponding position of its image signal in an already transmitted reference image. In former MPEG standards this reference image is the most recent preceding image. In H.264/AVC it is possible to refer to several preceding images. This technique is denoted as motion-compensated prediction with multiple reference frames. For multi-frame motion-compensated prediction, the encoder stores decoded reference pictures in a multi-picture buffer. The decoder replicates the multi-picture buffer of the encoder according to the reference picture buffering type and memory management control operations (MMCO) specified in the bitstream. Unless the size of the multi-picture buffer is set to one picture, the index at which the reference picture is located inside the multi-picture buffer has to be signaled. For this purpose, an additional picture reference index parameter has to be transmitted together with each motion vector of 16 × 16, 16 × 8, or 8 × 16 macroblock partition or 8 × 8 submacroblock.

The process for inter prediction of a sample block can also involve the selection of the pictures to be used as the reference pictures from a number of stored previously-decoded pictures. Reference pictures for motion compensation are stored in the picture buffer. With respect to the current picture, the pictures before and after the current picture, in the display order are stored into the picture buffer. These are classified as 'short-term' and 'long-term' reference pictures. Long-term reference pictures are introduced to extend the motion search range by using multiple decoded pictures, instead of using just one decoded short-term picture. Memory management is required to take care of marking some stored pictures as 'unused' and deciding which pictures to delete from the buffer for efficient memory management.

Sub-pixel Motion Vector:

The motion vector precision is at the granularity of one quarter of the distance between luma samples. If the motion vector points to an integer-sample position, the prediction signal is formed by the corresponding samples of the reference picture; otherwise, the prediction signal is obtained using interpolation between integer-sample positions. Sub-pel motion compensation can provide significantly better compression performance than integer-pel compensation, at the expense of increased complexity. Quarter-pel accuracy outperforms half-pel accuracy. Especially, sub-pel accuracy would increase the coding efficiency at high bitrates and high video resolutions. In the luma component, the sub-pel samples at half-pel positions are generated first and are interpolated from neighboring integer-pel samples using a one-dimensional 6-tap FIR filter with weights (1, -5, 20, 20, -5, 1)/32, horizontally and/or vertically, which was designed to reduce aliasing components that deteriorate the interpolation and the motion compensated prediction. Once all the half-pel samples are available, each quarter-pel sample is produced using bilinear interpolation (horizontally, vertically, or diagonally) between neighboring half- or integer-pel samples. For 4:2:0 video source sampling, 1/8 pel samples are required in the chroma components (depending on the chroma format, corresponding to 1/4 pel samples in the luma). These samples are interpolated (linear interpolation) between integer-pel chroma samples. Sub-pel motion vectors are encoded differentially with respect to predicted values formed from nearby encoded motion vectors. After interpolation, block-based motion compensation is applied. As noted, however, a variety of block sizes can be considered, and a motion estimation scheme that optimizes the trade-off between the number of bits necessary to represent the video and the fidelity of the result is desirable.

Figure 2: Example of Integer and Sub-Pel Prediction

Skipped Mode:

In addition to the macroblock modes described above, a P-slice macroblock can also be coded in the so-called skip mode. If a macroblock has motion characteristics that allow its motion to be effectively predicted from the motion of neighboring macroblocks, and it contains no non-zero quantized transform coefficients, then it is flagged as skipped. For this mode, neither a quantized prediction error signal nor a motion vector or reference index parameter are transmitted. The reconstructed signal is computed in a manner similar to the prediction of a macroblock with partition size 16 × 16 and fixed reference picture index equal to 0. In contrast to previous video coding standards, the motion vector used for reconstructing a skipped macroblock is inferred from motion properties of neighboring macroblocks rather than being inferred as zero (i.e., no motion).

Weighted Prediction:

In addition to the use of motion compensation and reference picture selection for prediction of the current picture content, weighted prediction can be used in P slices. When weighted prediction is used, customized weights can be applied as a scaling and offset to the motion-compensated prediction value prior to its use as a predictor for the current picture samples. Weighted prediction can be especially effective for such phenomena as "fade-in" and "fade-out" scenes.

Motion Vector Prediction:

After the temporal prediction, the steps of transform, quantization, scanning, and entropy coding are conceptually the same as those for I-slices for the coding of residual data (the original minus the predicted pixel values). The motion vectors and reference picture indexes representing the estimated motion are also compressed. Because, Encoding a motion vector for each partition can take a significant number of bits, especially if small partition sizes are chosen. Motion vectors for neighbouring partitions are often highly correlated and so each motion vector is predicted from vectors of nearby, previously coded partitions. A predicted vector, MVp, is formed based on previously calculated motion vectors. MVD, the difference between the current vector and the predicted vector, is encoded and transmitted. The method of forming the prediction MVp depends on the motion compensation partition size and on the availability of nearby vectors. The "basic" predictor is the median of the motion vectors of the macroblock partitions or subpartitions immediately above, diagonally above and to the right, and immediately left of the current partition or sub-partition. The predictor is modified if (a) 16x8 or 8x16 partitions are chosen and/or (b) if some of the neighbouring partitions are not available as predictors. If the current macroblock is skipped (not transmitted), a predicted vector is generated as if the MB was coded in 16x16 partition mode.

At the decoder, the predicted vector MVp is formed in the same way and added to the decoded vector difference MVD. In the case of a skipped macroblock, there is no decoded vector and so a motioncompensated macroblock is produced according to the magnitude of MVp.

Figure 3: Multiframe Motion Compensation, I addition to the motionvector picture reference parameter also transmit.