Computer architecture for video data processing and method thereof

• US 6,104,836 A
• Filed: 11/21/1997
• Issued: 08/15/2000
• Est. Priority Date: 02/19/1992
• Status: Expired due to Fees

• Current Assignee: 8X8, Inc.
• Original Assignee: 8X8, Inc.
• Inventors: Buckley, Ian John, Martin, Bryan R.
• Primary Examiner(s): Au, Amelia
• Assistant Examiner(s): Miller, Martin E
• Application Number:
  US08/975,768
• Time in Patent Office: 998 Days
• Field of Search: 382/236, 382/238, 358/430, 345/505
• US Class Current: 382/236
• CPC Class Codes: G06T 2207/10016 Video; Image sequence
• CPC Class Codes: G06T 7/223 using block-matching
• CPC Class Codes: H04N 19/43 Hardware specially adapted for motion estimation or compensation
• CPC Class Codes: H04N 19/433 characterised by techniques for memory access
• CPC Class Codes: H04N 19/51 Motion estimation or motion compensation
• CPC Class Codes: H04N 5/145 Movement estimation for video coding H04N19/51

Abstract

A system and method for video data processing for searching a region of overlapping candidate blocks to locate the best match to a comparably sized reference block comprising plurality of tree adder computational structures which each calculate the sum of absolute difference values for the corresponding data pixels in the comparison. The system further comprises a memory and addressing configuration comprising a dual part RAM, a funnel shifter, and control logic to supply the necessary data pixel values to allow the plurality of tree adders to compute the sum of absolute difference values for adjacent locations concurrently. Another aspect of the system and method for video processing is accumulating two values representing mathematical comparisons of two multi-dimensional images performed in a pixel-wise manner to determine which of the comparison produces less of a difference between the compared images.

Claims

1. A method of comparing first and second two-dimensional images to identify a desired match location for the first image within a search area of the second image, wherein each image represented by pixel values and one of the dimensions has at least N pixel values, comprising the steps of:

reading 2N pixel values corresponding to a line of the first image from a memory into a funnel shifter;

shifting the pixel values within the funnel shifter to align the pixel values on a desired pixel boundary;

receiving N+1 pixel values corresponding to a line within the search area of the second image;

accumulating a first pixel-wise sum of absolute difference (SAD) values within a first tree adder using a first set of pixels output from the funnel shifter and a selected set of pixels from the lines of the second image;

accumulating a second pixel-wise sum of absolute difference (SAD) values within a second tree adder using a second set of pixels output from the funnel shifter and the selected set of pixels from the lines of the second image; and

finding a minimum accumulated SAD value which corresponds to the desired match location for the first image within the second image.

2. The method according to claim 1, wherein the first set of pixel values from the funnel shifter correspond to bits [N-1:

0] and the second set of pixel values correspond to bits [N;

1] from the funnel shifter.

3. A method of comparing first and second two-dimensional images to identify a desired match location for the first image with a search area of the second image, wherein each image is represented by pixel values and one of the dimensions has at least N pixel values, comprising the steps of:

reading N pixel values corresponding to a line of the first image from a memory into a delay register;

receiving N pixel values corresponding to a line within the search area of the second image;

accumulating a first pixel-wise sum of absolute difference (SAD) values within a first tree adder using the pixels output from the memory and the received pixels from the lines of the second image;

accumulating a second pixel-wise sum of absolute difference (SAD) values within a first tree adder using the pixels output from the delay register and the pixels from the lines of the second image; and

finding a minimum accumulated SAD value which corresponds to the desired match location for the first image within the second image.

4. For use in locating a match location for a two-dimensional reference image within a search area of a two-dimensional candidate image, wherein the reference image and the candidate image are characterized as being comprised of a set of pixel values, and one of the dimensions is defined by at least N pixel values, a method of comparing the reference image and the search area of the candidate image, comprising the steps of:

reading 2N pixel values corresponding to a line of the sample image from a memory into a funnel shifter;

shifting the pixel values within the funnel shifter to align the pixel values on a desired pixel boundary;

receiving N+1 pixel values corresponding to a line within the search area of the reference image;

accumulating a first pixel-wise sum of absolute difference (SAD) value within a first tree adder using pixels [N-1;

0] from the output of the funnel shifter with pixels [N-1;

0] each line of the candidate image;

accumulating a second pixel-wise SAD value within a second tree adder using pixels [N;

1] from the output of the funnel shifter with pixels [N-1;

0] each line of the candidate image; and

determining which of the first accumulated pixel-wise SAD and second accumulated pixel-wise SAD is less.

5. For use in locating a match location for a two-dimensional reference image within a search area of a two-dimensional candidate image, wherein the reference image and the candidate image are characterized as being comprised of a set of pixel values, and one of the dimensions is defined by at least N pixel values, a method of comparing the reference image with the search area of the candidate image, comprising the steps of:

reading N pixel values corresponding to a line of the reference image into a delay register;

receiving N pixel values corresponding to a line of pixel values within the search area of the candidate image;

accumulating a first pixel-wise sum of absolute difference (SAD) within a first tree adder using the line of the reference image read from memory with the lines of the received search area;

accumulating a second pixel-wise SAD within a second tree adder using a prior line of N pixel values stored within the delay register with the lines of the received search area; and

determining which of the first and second accumulated pixel-wise SAD is less.

6. A method for locating a match location for an 8×

8 reference image within a search area of a candidate image, comprising the steps of;

(1) setting a memory address to the first location within the search area;

(2) setting a memory address to the first line within an 8×

8 reference image;

(3) resetting a first and a second accumulator register to zero;

(4) simultaneously reading 16 bytes of pixel data from the reference memory into a funnel shifter;

(5) simultaneously receiving 8 bytes of a reference line of pixel data;

(6) simultaneously computing a byte-wise sum of absolute difference (SAD) within a first tree adder using bytes [7;

0] from the shifter with bytes [7;

0] from the reference line of pixels;

(7) accumulating the first SAD value within the first accumulator register;

(8) simultaneously computing a byte-wise sum of absolute difference (SAD) within a second tree adder using bytes [8;

1] from the shifter with bytes [7;

0] from the reference line pixels;

(9) accumulating the second SAD value within the second accumulator register;

(10) repeating steps (3) through (8) for each of the 8 lines of the 8×

8 image;

(11) saving the accumulated first and second SAD values;

(12) setting the memory address to the next location within the search area;

(13) repeating steps (3) through (12) for each location within the search area to be directed; and

(14) finding the location with the minimum SAD value.

7. A method for locating a match location for an 8×

8 reference image within a search area of a candidate image comprising the steps of;

(1) setting a memory address to the first location within the search area to be checked;

(2) setting a memory address to the first line of an 8×

8 reference image;

(3) resetting a first accumulator register to zero; and

one cycle later, resetting a second accumulator to zero;

(4) simultaneously reading 8 bytes of data from the reference memory into a delay register;

(5) simultaneously receiving 8 bytes of a candidate line of pixel values;

(6) simultaneously computing a byte-wise sum of absolute differences (SAD) using bytes [7;

0] from the candidate line of pixels;

(7) accumulate the first SAD value within the first accumulator register;

(8) simultaneously computing a byte-wise sum of absolute difference value (SAD) within a second tree adder using bytes [7;

0] from the output of the delay register within bytes [7;

0] of the candidate line;

(9) accumulating the second SAD value within the second accumulator register;

(10) repeating steps (3) through (8) for each of the eight lines of the 8×

8 image;

(11) saving the accumulated first and second SAD values;

(12) setting the memory address for the next location within the search area to be checked; and

(12) repeating steps (3) through (12) for each locator within the search area to be checked; and

then finding the location with the minimum SAD value.

8. An apparatus for of comparing first and second two-dimensional images, each represented by pixel values and one of the dimensions has at least N pixel values, comprising:

means for reading 2N pixel values corresponding to a line of the first image from a memory into a funnel shifter;

means for shifting the pixel values within the funnel shifter to align the pixel values on a desired pixel boundary;

means for receiving N+1 pixel values corresponding to a line within the search area of the second image;

means for accumulating a first pixel-wise sum of absolute difference (SAD) values within a first tree adder using a first set of pixels output from the funnel shifter and a selected set of pixels from the lines of the second image;

means for accumulating a second pixel-wise sum of absolute difference (SAD) values within a second tree adder using a second set of pixels output from the funnel shifter and the selected set of pixels from the lines of the second image; and

means for determining which of the first and second accumulated pixel-wise SAD is less.

9. The apparatus according to claim 8, wherein the first set of pixel values from the funnel shifter correspond to bits [N-1:

0] and the second set of pixel values correspond to bits [N;

1] from the funnel shifter.

10. An apparatus for comparing first and second two-dimensional images, each represented by pixel values and one of the dimensions has at least N pixel values, comprising:

means for reading N pixel values corresponding to a line of the first image from a memory into a delay register;

means for receiving N pixel values corresponding to a line within the search area of the second image;

means for accumulating a first pixel-wise sum of absolute difference (SAD) values within a first tree adder using the pixels output from the memory and the received pixels from the lines of the second image;

means for accumulating a second pixel-wise sum of absolute difference (SAD) values within a second tree adder using the pixels output from the delay register and the received pixels from the lines of the second image; and

means for determining which of the first and second accumulated pixel-wise SAD is less.

11. An apparatus for of comparing first and second two-dimensional images, each represented by pixel values and one of the dimensions has at least N pixel values, comprising:

a first memory for providing 2N pixel values corresponding to a line of the first image to a funnel shifter;

the funnel shifter for shifting the pixel values within the funnel shifter to align the pixel values on a desired pixel boundary;

a second memory for providing N+1 pixel values corresponding to a line within the search area of the second image;

a first tree adder for accumulating a first pixel-wise sum of absolute difference (SAD) values using a first set of pixels output from the funnel shifter and a selected set of pixels from the lines of the second image;

a second tree adder for accumulating a second pixel-wise sum of absolute difference (SAD) values using a second set of pixels output from the funnel shifter and the selected set of pixels from the lines of the second image; and

means for determining which of the first and second accumulated pixel-wise SAD is less.

12. The apparatus according to claim 11, wherein the first set of pixel values from the funnel shifter correspond to bits [N-1:

0] and the second set of pixel values correspond to bits [N;

1] from the funnel shifter.

13. An apparatus for comparing first and second two-dimensional images, each represented by pixel values and one of the dimensions has at least N pixel values, comprising:

a first memory for providing N pixel values corresponding to a line of the first image from a memory into a delay register;

a second memory for producing N pixel values corresponding to a line within the search area of the second image;

a first tree adder for accumulating a first pixel-wise sum of absolute difference (SAD) values using the pixels output from the memory and the received pixels from the lines of the second image;

a second tree adder for accumulating a second pixel-wise sum of absolute difference (SAD) values using the pixels output from the delay register and the received pixels from the lines of the second image; and

means for determining which of the first computer pixel-wise SAD and second computed pixel-wise SAD is less.

14. A method of comparing first and second two-dimensional images, each represented by pixel values and one of the dimensions has at least N pixel values, comprising the steps of:

shifting 2N pixel values corresponding to a line of the first image within a funnel shifter to align the pixel values on a desired pixel boundary;

receiving N+1 pixel values corresponding to a line within the search area of the second image;

accumulating first pixel-wise values representing a mathematical comparison of a first set of pixels output from the funnel shifter and a selected set of pixels from the lines of the second image;

accumulating second pixel-wise values representing a mathematical comparison a second set of pixels output from the funnel shifter and the selected set of pixels from the lines of the second image; and

determining which of the first and second accumulated pixel-wise values is less.

15. The method according to claim 14, wherein the first set of pixel values from the funnel shifter correspond to bits [N-1:

0] and the second set of pixel values correspond to bits [N;

1] from the funnel shifter, and further including a step of;

finding a minimum accumulated pixel-wise value which corresponds to a desired match location for the first image within the second image.

16. A method of comparing first and second two-dimensional images, each represented by pixel values and one of the dimensions has at least N pixel values, comprising the steps of:

transferring N pixel values corresponding to a line of the first image into a delay register;

receiving N pixel values corresponding to a line within the search area of the second image;

accumulating a first pixel-wise value representing a mathematical comparison of the transferred pixels from the lines of the first image pixel and the received pixel values from the lines of the second image;

accumulating a second pixel-wise value representing a mathematical comparison of the pixel values contained in the delay register and the received pixel values from the line of the second image; and

determining which of the first and second accumulated pixel-wise values is less.

17. The method according to claim 16, wherein the method further includes the step of:

finding a minimum accumulated pixel-wise value which corresponds to a desired match location for the first image within the second image.