US5926580A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Convolution algorithm for efficient hardware implementation
Assignee: Hewlett Packard Development Co LP
•
Filing: 1997-01-30
•
Granted: 1999-07-20
•
Expires: 2017-01-30
Abstract
Abstract A system and method for performing a discrete image convolution using convolution masks that are symmetric in both cardinal directions. The method is used in an image processor. The advantage of the convolution processing in accordance with the invention is the reduction in the number of multiply operations. With the convolution having symmetry in both m and n, the convolution processing minimizes the number of multiple operations in the following manner: ##EQU1## where c(x,y) is the convolved image array, f(m,n) is the convolution mask, and g(x,y) is the image array to be processed. The invention reduces the number of multiply operations to convolve g(x,y) with f(m,n) by up to a factor of four, to (m+1)(n+1)/4, in relation to conventional image convolution processing.
Inventors
- 👤 J. Scott McCoy
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-11-06 20:23
CPC Classifications
G; G06; G06F; G06F17/00; G06F17/10; G06F17/15; G06T; G06T5/00; G06T5/20
Claims Analysis
Total Claims: 15
Claim 1
Independent Claim
278 words
A method for convolving an image frame comprising a two-dimensional array of pixel values by a desired linear convolution mask that is symmetric in both cardinal directions, while reducing the number of multiply operations employed in the convolution, the array comprising R rows and C columns of pixels, the method comprising the following steps: reading input image data including an image pixel value for an image pixel to be convolved and a set of image pixel values corresponding to a set of pixels surrounding the image pixel to be convolved; forming respective first and second sets of boundary columns for the left and right edges of the image frame, wherein each column of said first set is a duplicate of the first column of the image frame, and each column of said second set is a duplicate of the last column of the image frame; convolving said image pixel by applying a set of mask coefficients to the image pixel values for the pixel to be convolved and the set of surrounding pixels, said convolving step exploiting said symmetry in said convolution mask to employ only a reduced number of multiplication operations required by said convolving step to perform said convolution, wherein said boundary columns are employed to furnish pixel values for the set of surrounding pixels for convolving pixels located on or near the first and last columns of image pixels; and repeating the steps of reading input image data and convolving the image pixel for each pixel in a set of image pixels comprising the image frame to provide a convolved image frame, wherein a highly efficient convolution is obtained with efficient utilization of multiply operations.
Claim 2
Independent Claim
278 words
A method for convolving an image frame comprising a two-dimensional array of pixel values by a desired linear convolution mask that is symmetric in both cardinal directions, while reducing the number of multiply operations employed in the convolution, the array comprising R rows and C columns of pixels, the method comprising the following steps: reading input image data including an image pixel value for an image pixel to be convolved and a set of image pixel values corresponding to a set of pixels surrounding the image pixel to be convolved; forming respective first and second sets of boundary columns for the left and right edges of the image frame, wherein each column of said first set is a duplicate of the first column of the image frame, and each column of said second set is a duplicate of the last column of the image frame; convolving said image pixel by applying a set of mask coefficients to the image pixel values for the pixel to be convolved and the set of surrounding pixels, said convolving step exploiting said symmetry in said convolution mask to employ only a reduced number of multiplication operations required by said convolving step to perform said convolution, wherein said boundary columns are employed to furnish pixel values for the set of surrounding pixels for convolving pixels located on or near the first and last columns of image pixels; and repeating the steps of reading input image data and convolving the image pixel for each pixel in a set of image pixels comprising the image frame to provide a convolved image frame, wherein a highly efficient convolution is obtained with efficient utilization of multiply operations.
Claim 3
Dependent Claim
204 words
A method for convolving an image frame according to claim 12, wherein said convolving step includes: (i) selecting a first subset of said set of surrounding image pixels consisting of four corresponding image pixels from each quadrant disposed equidistantly from the image pixel to be convolved; (ii) summing the pixel values of said subset of surrounding image pixels to form a summed value; (iii) multiplying the summed value by a filter mask value corresponding to said subset to form a first product value; (iv) selecting a subsequent subset of said set of surrounding image pixels consisting of four corresponding image pixels from each quadrant disposed equidistantly from the image pixel to be convolved and which have not already been selected to form a subset; (v) summing the pixel values of said subsequent subset of surrounding image pixels to form a subsequent summed value; (vi) multiplying the subsequent summed value by a filter mask value corresponding to said subsequent subset to form a second product value; (vii) forming an accumulated value comprising the sum of the product values formed for each multiplication process; and (viii) repeating steps (iv) through (vii) to obtain an accumulated value formed from all pixels in the set of surrounding pixels.
Claim 4
Dependent Claim
26 words
The method of claim 2 wherein said convolving step further comprises applying a division factor to said accumulated value to obtain a convolved image pixel value.
Claim 5
Dependent Claim
15 words
The method of claim 3 wherein said division factor is an integer multiple of 2.
Claim 6
Dependent Claim
26 words
The method of claim 2 wherein in general the number of multiply operations is (m+1)(n+1)/4, where the pixel mask is m by n pixels in size.
Claim 7
Dependent Claim
115 words
The method of claim 2 wherein said image frame comprises R rows and C columns of pixels, the method further comprising the step of forming respective first and second sets of boundary columns for the left and right edges of the image frame, wherein each column of said first set is a duplicate of the first column of the image frame, and each column of said second set is a duplicate of the last column of the image frame, and wherein said boundary columns are employed during the convolving step to furnish pixel values for the set of surrounding pixels for convolving pixels located on or near the first and last columns of image pixels.
Claim 8
Dependent Claim
17 words
The method of claim 2 wherein the convolution mask is formed by mask coefficients f(m,n), where f(m,n)=f(-m,n)=f(m,-n)=f(-m,-n).
Claim 9
Dependent Claim
278 words
An image processor for processing a two-dimensional image array of pixel values, including apparatus for convolving said pixel values by a desired linear convolution mask that is symmetric in both cardinal directions, the processor comprising: circuity for reading a block of input image data comprising the image frame, including an image pixel value for an image pixel to be convolved and a set of image pixel values corresponding to a set of pixels surrounding the image pixel to be convolved; a first apparatus forming respective first and second sets of boundary columns for the left and right edges of the image frame, wherein each column of said first set is a duplicate of the first column of the image frame, and each column of said second set is a duplicate of the last column of the image frame; second apparatus for applying a set of mask coefficients to the image pixel values for the pixel to be convolved and the set of surrounding pixels, said apparatus employing said boundary columns to furnish pixel values for the set of surrounding pixels for convolving pixels located on or near the first and last columns of image pixels, said apparatus adapted to exploit said symmetry in said convolution mask to employ only a reduced number of multiplication operation required by said convolving step to perform said convolution; and controller apparatus for controlling the reading circuitry, the first apparatus and the second apparatus for applying a set of mask coefficients to read successive blocks of input image data and convolve successive image pixels for each pixel in a set of image pixels comprising the image frame to provide a convolved image frame.
Claim 10
Dependent Claim
278 words
An image processor for processing a two-dimensional image array of pixel values, including apparatus for convolving said pixel values by a desired linear convolution mask that is symmetric in both cardinal directions, the processor comprising: circuity for reading a block of input image data comprising the image frame, including an image pixel value for an image pixel to be convolved and a set of image pixel values corresponding to a set of pixels surrounding the image pixel to be convolved; a first apparatus forming respective first and second sets of boundary columns for the left and right edges of the image frame, wherein each column of said first set is a duplicate of the first column of the image frame, and each column of said second set is a duplicate of the last column of the image frame; second apparatus for applying a set of mask coefficients to the image pixel values for the pixel to be convolved and the set of surrounding pixels, said apparatus employing said boundary columns to furnish pixel values for the set of surrounding pixels for convolving pixels located on or near the first and last columns of image pixels, said apparatus adapted to exploit said symmetry in said convolution mask to employ only a reduced number of multiplication operation required by said convolving step to perform said convolution; and controller apparatus for controlling the reading circuitry, the first apparatus and the second apparatus for applying a set of mask coefficients to read successive blocks of input image data and convolve successive image pixels for each pixel in a set of image pixels comprising the image frame to provide a convolved image frame.
Claim 11
Dependent Claim
142 words
An image processor according to claim 13, wherein said set of surrounding image pixels includes pixels disposed in each quadrant of a two-dimensional mask set surrounding said image pixel to be convolved; and wherein said second apparatus includes: (i) multiplexing circuitry for selecting a first subset of said set of surrounding image pixels consisting of four corresponding image pixels from each quadrant disposed equidistantly from the image pixel to be convolved; (ii) digital adder circuitry for summing the pixel values of said subset of surrounding image pixels to form a summed value; (iii) digital multiplier circuitry for multiplying the summed value by a filter mask value corresponding to said subset to form a product value; and (iv) an accumulator for summing the pixel values of said product values formed over the different subsets of surrounding image pixels to form a summed value.
Claim 12
Dependent Claim
31 words
The image processor of claim 9, wherein said second apparatus further comprises a digital circuit for applying a division factor to said accumulated value to obtain a convolved image pixel value.
Claim 13
Dependent Claim
16 words
The image processor of claim 10 wherein said division factor is an integer multiple of 2.
Claim 14
Independent Claim
505 words
A method for convolving an image frame comprising a two-dimensional array of pixel values by a desired linear convolution mask that is symmetric in both cardinal directions, while reducing the number of multiply operations employed in the convolution, the method comprising the following steps: reading input image data including an image pixel value for an image pixel to be convolved and a set of image pixel values corresponding to a set of pixels surrounding the image pixel to be convolved, wherein said set of surrounding image pixels includes pixels disposed in each quadrant of a two-dimensional mask set surrounding said image pixel to be convolved; convolving said image pixel by applying a set of mask coefficients to the image pixel values for the pixel to be convolved and the set of surrounding pixels, said convolving step exploiting said symmetry in said convolution mask to employ only a reduced number of multiplication operations required by said convolving step to perform said convolution, said convolving step comprising: (i) selecting a first subset of said set of surrounding image pixels consisting of four corresponding image pixels from each quadrant disposed equidistantly from the image pixel to be convolved; (ii) summing the pixel values of said subset of surrounding image pixels to form a summed value; (iii) multiplying the summed value by a filter mask value corresponding to said subset to form a first product value; (iv) selecting a subsequent subset of said set of surrounding image pixels consisting of four corresponding image pixels from each quadrant disposed equidistantly from the image pixel to be convolved and which have not already been selected to form a subset; (v) summing the pixel values of said subsequent subset of surrounding image pixels to form a subsequent summed value; (vi) multiplying the subsequent summed value by a filter mask value corresponding to said subsequent subset to form a second product value; (vii) forming an accumulated value comprising the sum of the product values formed for each multiplication process; and (viii) repeating steps (iv) through (vii) to obtain an accumulated value formed from all pixels in the set of surrounding pixels; repeating the steps of reading input image data and convolving the image pixel for each pixel in a set of image pixels comprising the image frame to provide a convolved image frame, wherein a highly efficient convolution is obtained with efficient utilization of multiply operations; wherein said image frame comprises R rows and C columns of pixels; and further comprising: forming respective first and second sets of boundary columns for the left and right edges of the image frame; wherein each column of said first set is a duplicate of the first column of the image frame; and wherein each column of said second set is a duplicate of the last column of the image frame; and wherein said boundary columns are employed during the convolving step to furnish pixel values for the set of surrounding pixels for convolving pixels located on or near the first and last columns of image pixels.
Claim 15
Independent Claim
505 words
A method for convolving an image frame comprising a two-dimensional array of pixel values by a desired linear convolution mask that is symmetric in both cardinal directions, while reducing the number of multiply operations employed in the convolution, the method comprising the following steps: reading input image data including an image pixel value for an image pixel to be convolved and a set of image pixel values corresponding to a set of pixels surrounding the image pixel to be convolved, wherein said set of surrounding image pixels includes pixels disposed in each quadrant of a two-dimensional mask set surrounding said image pixel to be convolved; convolving said image pixel by applying a set of mask coefficients to the image pixel values for the pixel to be convolved and the set of surrounding pixels, said convolving step exploiting said symmetry in said convolution mask to employ only a reduced number of multiplication operations required by said convolving step to perform said convolution, said convolving step comprising: (i) selecting a first subset of said set of surrounding image pixels consisting of four corresponding image pixels from each quadrant disposed equidistantly from the image pixel to be convolved; (ii) summing the pixel values of said subset of surrounding image pixels to form a summed value; (iii) multiplying the summed value by a filter mask value corresponding to said subset to form a first product value; (iv) selecting a subsequent subset of said set of surrounding image pixels consisting of four corresponding image pixels from each quadrant disposed equidistantly from the image pixel to be convolved and which have not already been selected to form a subset; (v) summing the pixel values of said subsequent subset of surrounding image pixels to form a subsequent summed value; (vi) multiplying the subsequent summed value by a filter mask value corresponding to said subsequent subset to form a second product value; (vii) forming an accumulated value comprising the sum of the product values formed for each multiplication process; and (viii) repeating steps (iv) through (vii) to obtain an accumulated value formed from all pixels in the set of surrounding pixels; repeating the steps of reading input image data and convolving the image pixel for each pixel in a set of image pixels comprising the image frame to provide a convolved image frame, wherein a highly efficient convolution is obtained with efficient utilization of multiply operations; wherein said image frame comprises R rows and C columns of pixels; and further comprising: forming respective first and second sets of boundary columns for the left and right edges of the image frame; wherein each column of said first set is a duplicate of the first column of the image frame; and wherein each column of said second set is a duplicate of the last column of the image frame; and wherein said boundary columns are employed during the convolving step to furnish pixel values for the set of surrounding pixels for convolving pixels located on or near the first and last columns of image pixels.
References Cited (Backward Citations)
US3980873A
Cited
US4328425A
Cited
US4328426A
Cited
US4821108A
Cited
US4866648A
Cited
US4918742A
Cited
US4984286A
Cited
US5031132A
Cited
US5258771A
Cited
US5661822A
Cited
US5500811A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2002-07-19 | 2003-01-18 | 2003-07-20 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2006-07-19 | 2007-01-18 | 2007-07-20 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2010-07-19 | 2011-01-18 | 2011-07-20 | $7700.00 | Window Closed / Lapsed |