Method for performing box filter

• US 5,822,232 A
• Filed: 03/01/1996
• Issued: 10/13/1998
• Est. Priority Date: 03/01/1996
• Status: Expired due to Term

• Current Assignee: Intel Corporation
• Original Assignee: Intel Corporation
• Inventors: Kelly, Mike, Mennemeier, Larry M., Dulong, Carole
• Primary Examiner(s): Mai, Tan V.
• Application Number:
  US08/609,601
• Time in Patent Office: 956 Days
• Field of Search: 364/724.05, 364/724.13, 364/736.03, 382/260-265, 382/308
• US Class Current: 708/308
• CPC Class Codes: G06F 17/10 Complex mathematical operations function generation by table look-up G06F1/03; evaluation of elementary functions by calculation G06F7/544

Abstract

A computer implemented method for box filtering an array of data. The method includes a first step of filtering the rows of an array. The rows are in packed data sequences, each sequence having a plurality of packed data elements. Each row is filtered by generating copies of the row, aligning the copies, and generating a sum of the copies. The sum is generated by simultaneously adding corresponding packed elements of two rows in response to executing a first instruction. The columns of the array are filtered by sequentially adding, in response to executing the first instruction, filtered rows to a preceding and succeeding filtered row.

Claims

1. In a computer system, a method for filtering an array of data, the method comprising the steps of:

a) filtering rows of an array, wherein the rows are in packed data sequences with each sequence having a plurality of packed data elements, by performing the following steps for each row;

a1) generating copies of a row of the array;

a2) aligning the copies;

a3) generating a sum of the copies, wherein corresponding packed elements of two copies are simultaneously added in response to executing a first instruction; and

b) filtering columns of the array by sequentially adding, in response to executing the first instruction, filtered rows to a preceding and succeeding filtered row.

2. The method of claim 1, wherein the following steps are performed prior to step a1) of claim 1:

a) unpacking four high packed-bytes of a row into four packed words of a first packed data sequence;

b) unpacking four low packed-bytes of the row into four packed words of a second packed data sequence; and

c) performing steps a1)-a3) and step b, of claim 1, on the first and second packed data sequences, separately.

3. The method of claim 2, wherein step b of claim 1 further includes the following steps:

b) filtering columns by performing the following steps for each filtered row, excluding a first and last filtered row;

b1) generating a sum, in response to executing the first instruction, by adding, X times, corresponding packed elements of filtered row_i-1 and row_i, where X represents a first coefficient of a column filter, and _i represents an integer;

b2) adding, Y times, in response to the first instruction, corresponding packed elements of row_i and said sum, where Y represents a second coefficient of the column filter;

b3) adding, Z times, in response to executing the first instruction, corresponding elements of row_i+1 and said sum, where Z represents a third coefficient of the column filter.

4. The method of claim 3, wherein step a1) of claim 1 further includes generating a number of copies equal to a sum of the row filter coefficients.

5. The method of claim 4, wherein the step of aligning includes the steps of:

a) shifting in a first direction, by at least one data element, a number of copies equal to a first coefficient of the row filter; and

b) shifting in a second direction, by at least one data element, a number of copies equal to a second coefficient of the row filter, wherein a number of copies left unshifted is equal to a third coefficient.

6. The method of claim 5 wherein in step a) of claim 1, a first and eighth data element of each filtered row is weighted by a factor equal to the sum of the row filter coefficients.

7. The method of claim 6, wherein each data element represents a separate pixel.

10. The machine-readable medium of claim 9, wherein the following steps are performed prior to step a1) of claim 9:

a) unpacking four high packed-bytes of a row into four packed words of a first packed data sequence;

b) unpacking four low packed-bytes of the row into four packed words of a second packed data sequence; and

c) performing steps a1)-a3) and step b, of claim 1, on the first and second packed data sequences, separately.

11. The machine-readable medium of claim 10, wherein step b of claim 9 further includes the following steps:

b) filtering columns by performing the following steps for each filtered row, excluding a first and last filtered row;

b1) generating a sum, in response to executing the first instruction, by adding, X times, corresponding packed elements of filtered row_i-1 and row_i, where X represents a first coefficient of a column filter, and _i represents an integer;

b2) adding, Y times, in response to the first instruction, corresponding packed elements of row_i and said sum, where Y represents a second coefficient of the column filter

b3) adding, Z times, in response to executing the first instruction, corresponding elements of row_i+1 and said sum, where Z represents a third coefficient of the column filter.

12. The machine-readable medium of claim 11, wherein step a1) of claim 9 further includes generating a number of copies equal to a sum of the row filter coefficients.

13. The machine-readable medium of claim 12, wherein the step of aligning includes the steps of:

a) shifting in a first direction, by at least one data element, a number of copies equal to a first coefficient of the row filter; and

b) shifting in a second direction, by at least one data element, a number of copies equal to a second coefficient of the row filter, wherein a number of copies left unshifted is equal to a third coefficient.

14. The machine-readable medium of claim 13 wherein in step a) of claim 9, a first and eighth data element of each filtered row is weighted by a factor equal to the sum of the row filter coefficients.

15. The machine-readable medium of claim 14, wherein each data element represents a separate pixel.

8. In a computer system a method for filtering of an array of data, the method comprising the steps of:

a) filtering rows by performing the following steps for each row;

a1) unpacking, in response to executing a PUNPCK instruction, four high packed-bytes of a row into four packed words of a first packed data sequence;

a2) unpacking, in response to executing a PUNPCK instruction, four low packed-bytes of the row into four packed words of a second packed data sequence;

a3) generating, in response to executing MOVQ instructions, copies of the row of the array;

a4) shifting right, in response to executing a PSRL instruction, by at least one data element, a number of copies equal to a first coefficient of a row filter;

a5) shifting left, in response to executing a PSLL, by at least one data element, a number of copies equal to a second coefficient of the row filter, wherein a number of the copies unshifted is equal to a third coefficient of the row filter;

a6) generating a sum of the copies, wherein corresponding packed elements of two copies are simultaneously added in response to executing a first instruction; and

b) filtering columns of the array by performing the following steps for each filtered row, excluding a first and last filtered row;

b1) generating a sum, in response to executing a PADD instruction, by adding, X times, corresponding packed elements of filtered row_i-1 and row_i, where X represents a first coefficient of a column filter, and _i represents an integer;

b2) adding, Y times, in response to executing a PADD instruction, filtered row_i to the sum, where Y represents a second coefficient of the column filter

b3) adding, Z times, in response to executing a PADD instruction, row_i+1 to the sum, where Z represents a third coefficient of the column filter.

9. A machine-readable medium having stored thereon data representing a sequence of instructions for filtering an array of data, the sequence of instructions which, when executed by a processor, cause the processor to perform the steps of:

a) filtering rows of an array, wherein the rows are in packed data sequences with each sequence having a plurality of packed data elements, by performing the following steps for each row;

a1) generating copies of a row of the array;

a2) aligning the copies;

a3) generating a sum of the copies, wherein corresponding packed elements of two copies are simultaneously added in response to executing a first instruction; and

b) filtering columns of the array by sequentially adding, in response to executing the first instruction, filtered rows to a preceding and succeeding filtered row.