Method and system for image compression using block size heuristics

1. A method for motion searching each macroblock of a video frame, comprising iteratively decreasing block size until a rate-distortion (RD) has been minimized and selectively reducing the number of block sizes searched, wherein said motion searching each block of said video frame comprises:

performing a motion search on said video frame relative to a previous video frame using 16×16, 8×16 and 16×8 block sizes';

calculating a rate-distortion (RD) for each of said 16×16, 8×16 and 16×8 block sizes;

if said calculated RD is lowest for said 16×16 block size, motion search is complete, otherwise continue;

performing a motion search on said video frame relative to said previous video frame using an 8×8 block size;

calculating a RD for said ×8 block size;

if said calculated AD for said 8×8 block size is not lower than said calculated RD for said said 16×16, 8×16 and 16×8 block sizes then said motion search is complete, otherwise continue;

performing a motion search on said video frame relative to said previous video frame using 4×8 and 8×4 block sizes;

calculating a RD for said 4×8 and 8×4 block sizes;

if neither of said calculated RDs for said 4×8 and 8×4 block sizes is lower than said calculated RD for said 16×16, 8×16, 16×8 and 8×8 block sizes, then said motion search is complete, otherwise continue;

performing a motion search on said video frame relative to said previous video frame using a 4×4 block size; and

determining a block size with lowest calculated RD and motion search is complete.

2. The method of claim 1 , wherein said motion searching each block of said video frame comprises:

selecting a largest of a plurality of available block sizes to obtain a selected block size;

performing a motion search using said selected block size;

calculating and storing a rate-distortion (RD) for said selected block size;

comparing said RD for said selected block size with a RD for a larger block size if one exists;

if the RD for said selected block is larger than said RD for said larger block size then a lowest RD block size has been found, if not, continuing;

selecting a smaller block size if one exists; and

repeating above starting from performing a motion search using said selected block size.

3. The method of claim 1 , further comprising repeating all steps for a new video frame.

4. The method of claim 1 , wherein said RD comprises:

RD=n (rate)+ m (distortion)

where n and m are scalar values.

5. The method of claim 4 , wherein rate comprises a number of bits of storage required for macroblock overhead.

6. The method of claim 4 , wherein distortion comprises a sum of absolute differences.

7. A method for compressing motion video images comprising:

inputting a video frame;

performing a motion search on each macroblock of said video frame including iteratively decreasing block size until a rate-distortion (RD) has been minimized;

storing a motion vector for each block in said video frame; and

residual coding of motion compensated errors, wherein said performing said motion search on each macroblock of said video frame comprises:

performing a motion search on said video frame relative to a previous video frame using 16×16, 8×16 and 16×8 block sizes;

calculating a rate-distortion (.RD) for each of said16×16, 8×16 and 16×8 block sizes;

if said calculated RD is lowest for said 16×16 block size, motion search is complete, otherwise continue,

performing a motion search on said video frame relative to said previous video frame using an 8×8 block size;

calculating a RD for said 8×8 block size;

if said calculated RD for said 8×8 block size is not lower than said calculated RD for said said 16×16, 8×16 and 16×8 block sizes then said motion search is complete, otherwise continue;

performing a motion search on said video frame relative to said previous video frame using 4×8 and 8×4 block sizes;

calculating a RD for said 4×8 and 8×4 block sizes;

if neither of said calculated AI)s for said 4×8 and 8×4 block sizes is lower than said calculated RD for said 16×16, 8×16, 16×8 and 8×8 block sizes, then said motion search is complete, otherwise continue;

performing a motion search on said video frame relative to said previous video frame using a 4×4 block size; and

determining a block size with lowest calculated RD and motion search is complete.

8. The method of claim 7 , further comprising repeating all steps for a new video frame.

9. The method of claim 7 , wherein said performing said motion search on each macroblock of said video frame further comprises:

selecting a largest of a plurality of available block sizes to obtain a selected block size;

performing a motion search using said selected block size;

calculating and storing a rate-distortion (RD) for said selected block size;

comparing said RD for said selected block size with a RD for a larger block size if one exists;

if the RD for said selected block is larger than said RD for said larger block size then a lowest RD block size has been found, if not, continuing;

selecting a smaller block size if one exists; and

repeating above starting from performing a motion search using said selected block size.

10. The method of claim 7 , wherein said RD comprises:

RD=n (rate)+ m (distortion)

where n and m are scalar values.

11. The method of claim 10 , wherein rate comprises a number of bits of storage required for macroblock overhead.

12. The method of claim 10 , wherein distortion comprises a sum of absolute differences.

13. A system for transmitting and receiving video images, comprising:

a processor configured for processing computer instructions and a memory for storing said computer instructions; and

wherein said computer instructions implement a method for compressing motion video images, comprising:

inputting a video frame;

performing a motion search on each macroblock of said video frame including iteratively decreasing block size until a rate-distortion (RD) has been minimized;

storing a motion vector for each block in said video frame; and

residual coding of motion compensated errors, wherein said performing said motion search on each macroblock of said video frame further comprises:

performing a motion search on said video frame relative to a previous video frame using 16×16, 8×16 and 16×8 block sizes;

calculating a rate-distortion (#D) for each of said 16×16, 8×16 and 16×8 block sizes;

if said calculated .RD is lowest for said 16×16 block size, motion search is complete, othenvise continue;

performing a motion search on said video frame relative to said previous video frame using an 8×8 block size;

calculating a RD for said 8×8 block size;

if said calculated .RD for said 8×8 block size is not lower than said calculated RD for said said 16×16, 8×16 and 16×8 block sizes then said motion search is complete, othenvise continue;

performing a motion search on said video frame relative to said previous video frame using 4×8 and 8×4 block sizes',

calculating a SD for said 4×8 and 8×4 block sizes;

if neither of said calculated RD's for said 4×8 and 8×4 block sizes is lower than said calculated RD for said16×16, 8×16, 16×8 and 8×8 block sizes, then said motion search is complete, otherwise continue;

performing a motion search on said video frame relative to said previous video frame using a 4×4 block size; and

determining a block size with lowest calculated RD and motion search is complete.

14. The system of claim 13 , wherein said performing said motion search on each macroblock of said video frame further comprises:

selecting a largest of a plurality of available block sizes to obtain a selected block size;

performing a motion search using said selected block size;

calculating and storing a rate-distortion (RD) for said selected block size;

comparing said RD for said selected block size with a RD for a larger block size if one exists;

if the RD for said selected block is larger than said RD for said larger block size then a lowest RD block size has been found, if not, continuing;

selecting a smaller block size if one exists; and

repeating above starting from performing a motion search using said selected block size.

15. The system of claim 13 , wherein said RD comprises:

RD=n (rate)+ m (distortion)

where n and m are scalar values.

16. The system of claim 15 , wherein rate comprises a number of bits of storage required for macroblock overhead.

17. The system of claim 15 , wherein distortion comprises a sum of absolute differences.

18. The system of claim 13 , further comprising an input device in communication with said processor for capturing video images.

19. The system of claim 13 , wherein said system is further configured to communicate over a network.