Intra prediction mode selection in video coding

1. A method of encoding a digital video with a video encoder, comprising:

loading a picture comprising a plurality of pixels;

arranging said plurality of pixels into a plurality of intra prediction blocks and/or inter prediction blocks;

dividing the pixels of each intra prediction block into a first group, a second group, a third group, and a fourth group based on phases of the pixels;

for each intra prediction block, loading an initial list of intra prediction modes;

at a first stage for each intra prediction block, calculating a first stage cost value for each of the intra prediction modes on said initial list for said first group, calculating a first stage threshold maximum cost, and generating a first stage mode list by copying each intra prediction mode on said initial mode list that has a first stage cost value that is less than said first stage threshold maximum cost;

at a second stage for each intra prediction block, calculating a second stage cost value for each of the intra prediction modes on said first stage mode list for said second group, calculating a second stage threshold maximum cost, and generating a second stage mode list by copying each intra prediction mode on said first stage mode list that has a second stage cost value that is less than said second stage threshold maximum cost;

at a third stage for each intra prediction block, calculating a third stage cost value for each of the intra prediction modes on said second stage mode list for said third group, calculating a third stage threshold maximum cost, and generating a third stage mode list by copying each intra prediction mode on said second stage mode list that has a third stage cost value that is less than said third stage threshold maximum cost;

at a fourth stage for each intra prediction block, calculating a fourth stage cost value for each of the intra prediction modes on said third stage mode list for said fourth group;

for each intra prediction block, selecting the intra prediction mode on said third stage mode list with the lowest fourth stage cost value as a tentative intra prediction mode for the intra prediction block;

calculating a heterogeneity index for each group of contiguous intra prediction blocks in said picture, based on the tentative intra prediction mode selected for each intra prediction block after said fourth stage; and

finalizing the tentative intra prediction mode for each intra prediction block within each group of contiguous intra prediction blocks that has a heterogeneity index above a predetermined threshold value.

2. The method of claim 1 , wherein:

said first stage cost value for an intra prediction mode is calculated as the sum of the absolute transformed differences or the sum of absolute differences between the first group's original pixels and the predicted pixels using the intra prediction mode, plus a bitrate factor equaling a bitrate multiplied by a Lagrange multiplier based on a quantization parameter when the intra prediction mode is identified as a most probable mode, and

wherein said first stage threshold maximum cost is calculated as the minimum first stage cost value across all intra prediction modes on said initial mode list plus a first parameter that is less than one multiplied by the range of first stage cost values.

3. The method of claim 2 , wherein:

said second stage cost value, said third stage cost value, and said fourth stage cost value for an intra prediction mode are calculated as the sum of the absolute transformed differences or the sum of absolute differences between the associated group's original pixels and the predicted pixels using the intra prediction mode, plus a cost value for the preceding stage, plus said bitrate factor when the intra prediction mode is identified as a most probable mode,

wherein said second stage threshold maximum cost is calculated as the minimum second stage cost value across all intra prediction modes on said first stage mode list, plus a positive second parameter that is less than said first parameter multiplied by the range of first stage cost values, and

wherein said third stage threshold maximum cost is calculated as the minimum third stage cost value across all intra prediction modes on said second stage mode list, plus a positive third parameter that is less than said second parameter multiplied by the range of first stage cost values.

4. The method of claim 1 , wherein each group of contiguous intra prediction blocks is a region of four intra prediction blocks arranged two blocks wide and two blocks high, and the heterogeneity index for a group is calculated by summing the differences between the intra prediction modes of the top and bottom intra prediction blocks in the left column of the group, the differences between the intra prediction modes of the top and bottom intra prediction blocks in the right column of the group, the differences between the intra prediction modes of the left and right intra prediction blocks in the top row of the group, and the differences between the intra prediction modes of the left and right intra prediction blocks in the bottom row of the group.

5. The method of claim 4 , further comprising comparing the rate distortion costs of encoding the four intra prediction blocks within each group that had a heterogeneity index that was not above said predetermined threshold value against the costs of encoding the four intra prediction blocks as a unified region, and selecting the arrangement with the lower rate distortion cost.