Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Remarks
This Office Action is responsive to Applicants' Amendment filed on 09/12/2025, in which claims 1, 5, 8, 12, 14-16, 20, and 22 are amended. Claims 2-4, 6, 9-11, 13, 17-19, and 21 are newly cancelled. No new claims are added.
Claims 1, 5, 7, 8, 12, 14-16, 20, and 22 are currently pending.
Response to Arguments
With regards to the rejections of claims 1-22 under 35 U.S.C. 101 as directed to abstract ideas, Applicant’s arguments that the claims as amended overcome the rejections are persuasive. Any recited abstract ideas have been integrated into a practical application of efficiently processing convolution operations.
With regards to the rejections of claims 1-2 and 8-9 under 35 U.S.C 102(a), as anticipated by Ruff, Examiner finds Applicant’s arguments that the claims as amended overcome the rejections are persuasive, however the arguments are moot in view of a new grounds of rejection, as presented below.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1, 8, and 14 are rejected under 35 U.S.C. 103 as being unpatentable over Ruff, in view of Zlateski et al. “ZNNi: Maximizing the Inference Throughput of 3D Convolutional Networks on CPUs and GPUs”, hereinafter Zlateski.
Regarding claim 1,
Ruff teaches A method for neural network convolution, the method comprising: ((Ruff Abstract) “A computational device performs the operation of a bank of convolutional filters commonly used in a convolutional neural network”)
receiving, by a processing circuitry, a three dimensional (3D) data input that includes input data segments associated with different input data depth values; ((Ruff [0001]) “This input is typically treated as a 3D tensor with Y and X dimensions forming a 2D slice of the input and the depth dimension D indexes the different channels in the input”, 2D slices of input with depth indexes corresponds to input data segments with different input data depth values)
receiving, by the processing circuitry, a convolution kernel that is a 3D convolution kernel and comprises kernel segments associated with different kernel depth values; ((Ruff [0002]) “a 3D tensor is applied to the input tensor which in this sense is shared by all filters in the filter bank and to represent this plurality of filters as a single 4 dimensional (4D) tensor here referred to as W wherein each filter is indexed by f and the filter has a 3D kernel comprising coefficients indexed by subscripts (f,i,p,q) which in order represent the filter number f, the depth index i of the 2D slice of the kernel and also the input, and the 2D position (p,q) of the coefficient within the 2D depth slice of the kernel corresponding by convention to its Y position p and X position q of the point on a Cartesian grid”, a 3D kernel which has 2D slices indexed by depth corresponds to a 3D convolution kernel with kernel segments associated with different kernel depth values)
and performing multiple 3D convolution iterations, ((Ruff [0032]) “further sequencing control means is arranged that sequences these indices according to the order desired for processing each filter coefficient from the filter bank W and this order and range of values being dependant upon the particular choice for parallel computational processing implemented and naively for a single processor implementation this order could be for example by firstly indexing f that is the filter index, then i that is the depth slice index so that each filter is processed in turn by accessing each of its coefficients in turn by order of depth slice but noting that an efficient parallel implementation would likely access each 2D slice of the input data in tum and perform convolutional processing of the filter coefficients corresponding to this slice across all filters before moving on to the next slice of the input data”, sequentially performing convolutional processing for each 2D slice of a 3D input corresponds to performing multiple 3D convolution iterations)
wherein each iteration of the multiple 3D convolution iterations comprises: determining a convolution iteration type [based on whether a kernel segment is to be paired with a virtual padding segment], the convolution iteration type indicating whether a 3D convolution iteration of the multiple 3D convolutional iterations is of a first convolution iteration type or of a second convolution iteration type; ((Ruff [0042]) “The coefficient sequential processing of the device is not dependant on the order of processing the coefficients but if two or more in the sequence lie within the same slice of the filter kernel then the accumulator Af [25] tensor is the same for those coefficients, so in this case accordingly the accumulator does not need to be stored and fetched from A and a means is further provided to recirculate the previous addition result back to Af [25] and in particular the carry of each bit is separately recirculated to the next accumulation so that a bitwise single bit addition may be performed and thereby at a much higher rate than a synchronous adder with the benefit of simpler logic thereby”, determining if two or more filter kernel coefficients are within the same slice of the filter kernel and performing different operations based on this corresponds to determining a convolution iteration type that indicates whether a 3D convolution iteration is of a first convolution iteration type or of a second convolution iteration type, Ruff does not teach determining convolution iteration type based on presence of padding)
and executing the 3D convolution iteration based on the convolution iteration type; ((Ruff [0042]) “if two or more in the sequence lie within the same slice of the filter kernel then the accumulator Af [25] tensor is the same for those coefficients, so in this case accordingly the accumulator does not need to be stored and fetched from A and a means is further provided to recirculate the previous addition result back to Af”, executing processing of filter kernel coefficients based on if they are within the same slice of the 3D filter kernel corresponds to executing a 3D convolution iteration based on the convolution iteration type)
in at least one iteration of the multiple 3D convolution iterations, determining that the respective 3D convolution iteration is of the first convolution iteration type, ((Ruff [0042]) “if two or more in the sequence lie within the same slice of the filter kernel then the accumulator Af [25] tensor is the same for those coefficients, so in this case accordingly the accumulator does not need to be stored and fetched from A and a means is further provided to recirculate the previous addition result back to Af”, a case where the accumulator does not need to be stored and fetched from A is a first convolution iteration type that can occur)
and consequentially executing the 3D convolution iteration, including allocating each one of the kernel segments to a corresponding input data segment; ((Ruff Claim 24) “performing the convolutional operations within a convolutional neural net in which a real valued 4D tensor bank W of filters each 3D filter Wf of which is applied at all 2D (y,x) locations, i.e. spatial dimensions over which the convolution is performed, to a real valued 3D input tensor M that is split into identically sized tiles that are presented in sequence to the device in which each tile is a stack of depth D of 2D slices and which 2D slices are arranged to be presented to the device in turn so that it may be convolved with the corresponding slice of the filters each of kernel depth D in the bank in order to sequentially compose and accumulate the convolutional 3D output tile tensor”, a convolution operation with 3D kernel filters and inputs in which 2D slices of the input are presented to a device sequentially to be convolved with a corresponding slice of the kernel filters corresponds to allocating each one of the kernel segments to a corresponding input data segment)
Zlateski teaches the following further limitations that Ruff does not teach:
…determining a convolution iteration type based on whether a kernel segment is to be paired with a virtual padding segment,… ((Zlateski Pg. 3) “A 3D FFT is obtained by computing 1D FFTs along the three dimensions. Some of these 1D FFTs are of an array with all elements equal to 0. These are unnecessary to compute as the FFT of an all zeros signal is all zeros. We can reduce the amount of computation by computing only necessary 1D transforms. When computing the FFT of a trainable kernel of size k3 zero padded to size of n3, instead of naively computing n2 1D FFTs along each dimension, which takes Cn3 log n3 we could first only do k2 FFTs along one dimension, then k×x along then next, and finally n2 along the last dimension, as shown on Fig. 2”, changing the amount of FFTs per dimension of a kernel based on amount of zero padding corresponds to determining a convolution iteration type based on pairing with padding segments)
and in at least one other iteration of the multiple 3D convolution iterations, determining that the respective other 3D convolution iteration is of the second convolution iteration type, ((Zlateski Pg. 3) “A 3D FFT is obtained by computing 1D FFTs along the three dimensions. Some of these 1D FFTs are of an array with all elements equal to 0. These are unnecessary to compute as the FFT of an all zeros signal is all zeros. We can reduce the amount of computation by computing only necessary 1D transforms”, convolution with an array of all zeros is a second convolution iteration type)
and consequentially executing the 3D convolution iteration, including skipping a calculation of element-wise multiplication and addition operations between elements of a first kernel segment and elements of a virtual padding segment; ((Zlateski Pg. 3) “In FFT convolution the kernel and the image are zero-padded to a common size. Since the kernel is typically much smaller than the image, the padded kernel consists mostly of zeros. Ignoring the zeros is known as FFT pruning, and can provide speedup [22]…For 3D FFT-based convolution, the 3D images x and y are first zero-padded to the same size”, (Zlateski Pg. 5) “Multiply-add task computes the point-wise product of an input image and a kernel FFT accumulating the result to an appropriate image transform”, not computing an outcome of element-wise multiply-add operations between elements of a kernel and padding because it is already known that the outcome will be zero corresponds to skipping a calculation of element-wise multiplication and addition operations between elements of a kernel segment and a virtual padding segment, although the kernel is more likely to have more zero-padding, both the image and the kernel are zero-padded)
wherein the execution of the 3D convolution iteration comprises at least one of: a) performing element-wise multiplication and addition operations between elements of a second kernel segment to elements of a corresponding input data segment; ((Zlateski Pg. 3) “In FFT convolution the kernel and the image are zero-padded to a common size…A 3D FFT is obtained by computing 1D FFTs along the three dimensions. Some of these 1D FFTs are of an array with all elements equal to 0”, (Zlateski Pg. 5) “Multiply-add task computes the point-wise product of an input image and a kernel FFT accumulating the result to an appropriate image transform”, a 3D FFT that has 1D FFTs for each dimension has at least three kernel segments, FFT convolution includes multiply-add tasks between points or elements of the kernel and the input image)
replacing the elements of the first kernel segment by zero-valued elements; ((Zlateski Pg. 3) “In FFT convolution the kernel and the image are zero-padded to a common size. Since the kernel is typically much smaller than the image, the padded kernel consists mostly of zeros”, replacing most elements of a kernel with zeroes correspond to replacing the elements of at least one kernel segment by zero-valued elements)
and performing element-wise multiplication and addition operations between the zero-valued elements and elements of one of the corresponding input data segments; ((Zlateski Pg. 3) “In FFT convolution the kernel and the image are zero-padded to a common size…A 3D FFT is obtained by computing 1D FFTs along the three dimensions. Some of these 1D FFTs are of an array with all elements equal to 0”, (Zlateski Pg. 5) “Multiply-add task computes the point-wise product of an input image and a kernel FFT accumulating the result to an appropriate image transform”, a 3D FFT that has 1D FFTs for each dimension has at least three kernel segments, including kernel segments that can have all zeros, and the image will also have at least three dimensions and thus segments, FFT convolution includes multiply-add tasks between points or elements of the kernel and the input image)
and (b) performing: element-wise multiplication and addition operations between elements of the second kernel segment to elements of the corresponding input data segment; ((Zlateski Pg. 3) “In FFT convolution the kernel and the image are zero-padded to a common size…A 3D FFT is obtained by computing 1D FFTs along the three dimensions. Some of these 1D FFTs are of an array with all elements equal to 0”, (Zlateski Pg. 5) “Multiply-add task computes the point-wise product of an input image and a kernel FFT accumulating the result to an appropriate image transform”, a 3D FFT that has 1D FFTs for each dimension has at least three kernel segments, FFT convolution includes multiply-add tasks between points or elements of the kernel and the input image)
and setting a zero-value to an outcome of the calculation of element-wise multiplication and addition operations between elements of the first kernel segment and elements of the virtual padding segment ((Zlateski Pg. 3) “A 3D FFT is obtained by computing 1D FFTs along the three dimensions. Some of these 1D FFTs are of an array with all elements equal to 0. These are unnecessary to compute as the FFT of an all zeros signal is all zeros. We can reduce the amount of computation by computing only necessary 1D transforms. When computing the FFT of a trainable kernel of size k3 zero padded to size of n3, instead of naively computing n2 1D FFTs along each dimension, which takes Cn3 log n3 we could first only do k2 FFTs along one dimension, then k×x along then next, and finally n2 along the last dimension, as shown on Fig. 2”, Zlateski Pg. 3, Fig. 2 shows the elements, including padding, that are convolved, (Zlateski Pg. 5) “Multiply-add task computes the point-wise product of an input image and a kernel FFT accumulating the result to an appropriate image transform”, not computing an outcome of element-wise multiply-add operations between elements of a kernel and padding because it is already known that the outcome will be zero corresponds to setting a zero-value to the outcome of element-wise multiplication and addition operations between kernel segment and virtual padding segment elements)”, Zlateski Pg. 3, Fig. 2 shows the elements, including padding, that are convolved, (Zlateski Pg. 5) “Multiply-add task computes the point-wise product of an input image and a kernel FFT accumulating the result to an appropriate image transform”, not computing an outcome of element-wise multiply-add operations between elements of a kernel and padding because it is already known that the outcome will be zero corresponds to setting a zero-value to the outcome of element-wise multiplication and addition operations between kernel segment and virtual padding segment elements)
At the time of filing, one of ordinary skill in the art would have motivation to combine Ruff and Zlateski by taking the method for performing 3D neural network convolution with a 3D input, a 3D kernel, both split into segments, and iteratively doing convolutions of one type or another, taught by Ruff, and having the second convolution type involve skipping calculations with zero replacement between elements in a kernel segment and in a padding segment, taught by Zlateski, as Zlateski teaches (Zlateski Pg. 3) “Ignoring the zeros is known as FFT pruning, and can provide speedup”, and faster neural network convolution is a predicable benefit. Such a combination would be obvious.
Regarding claim 8,
Claim 8 recites a non-transitory machine-readable storage medium for performing the function of the method of claim 1. Specifically, claim 8 recites At least one non-transitory machine-readable storage medium, comprising a plurality of instructions that, responsive to being executed with processor circuitry of a computing device, cause the computing device to:. Ruff teaches: (Ruff [0008]) “where applicable a processing means that applies to a processor as just described implicitly refers to a configurable software means. For instance, with an ASIC implementation such software would likely be a combination of fixed register values and a microcode for moving data around and activating hardware components and is just a special case of a general-purpose CPU style processor”, with software for a general-purpose CPU style processor corresponding to a plurality of instructions to be executed with processor circuitry, and the software being fixed register values and microcode being a non-transitory machine-readable storage medium.
All other limitations in claim 8 are substantially the same as those in claim 1, therefore the same rationale for rejection applies.
Regarding claim 14,
Ruff and Zlateski jointly teach The at least one non-transitory machine-readable storage medium according to claim 8,
Zlateski further teaches:
wherein the execution of the 3D convolution iteration comprises allocating the first kernel segment to virtual padding segments and allocating the second kernel segment to the corresponding input data segment ((Zlateski Pg. 3) “A 3D FFT is obtained by computing 1D FFTs along the three dimensions. Some of these 1D FFTs are of an array with all elements equal to 0. These are unnecessary to compute as the FFT of an all zeros signal is all zeros”, if some of the arrays are all equal to 0 but others aren’t then some segments of the kernel will be allocated to virtual padding segments while others are allocated to input data, Zlateski Pg. 3, Fig. 2 shows that some of the kernel segment is allocated to virtual padding (of zeroes))
PNG
media_image1.png
785
1225
media_image1.png
Greyscale
At the time of filing, one of ordinary skill in the art would have motivation to combine the method jointly taught by Ruff and Zlateski for the parent claim of claim 14, claim 8. No new embodiments are introduced, so the reason to combine is the same as for the parent claim.
Claims 5 and 12 are rejected under 35 U.S.C. 103 as being unpatentable over Ruff, in view of Zlateski, further in view of Wang et al. (U.S. Patent Application Publication No. 2020/0302265), hereinafter Wang.
Regarding claim 5,
Ruff and Zlateski jointly teach The method according to claim 1,
Wang teaches the following further limitation that neither Ruff, nor Zlateski teaches:
wherein the replacing the elements of the first kernel segment comprises retrieving zero-valued elements from a memory unit instead of retrieving elements of the first kernel segment ((Wang [0025]-[0026]) “The zero matrix is a matrix in which all elements are 0. In this implementation, a secondary convolution kernel is obtained by setting, to a zero matrix, a two-dimensional matrix on at least one channel of a primary convolution kernel”, (Wang [0008]) “generate, by using the primary convolution kernels of the convolution layers, secondary convolution kernels required by the convolution layers. This can reduce memory occupied by the convolutional neural network”, a secondary convolution kernel of all zeros that is used to occupy less memory than elements of a primary convolution kernel with non-zero elements corresponds to retrieving zero-valued elements from memory instead of elements of a first kernel segment)
At the time of filing, one of ordinary skill in the art would have motivation to combine Ruff, Zlateski, and Wang by taking the method for performing 3D neural network convolution involving skipping calculations of kernel segments in a second convolution type with zero replacement, jointly taught by Ruff and Zlateski, and having the elements of the kernel segment replaced with zeroes be performed by retrieving zeroes from memory instead of the original elements, taught by Wang. Retrieving wanted values from memory is well-understood, routine, and conventional in the art, and provides the predictable benefit of being faster than retrieving the original values, as instead of accessing memory locations individually to yield the precise values needed, all memory locations can be assumed to be zero to start, reducing the amount of memory access operations needed. Such a combination would be obvious.
Regarding claim 12,
Claim 12 recites a non-transitory machine-readable storage medium for performing the function of the method of claim 5. All other limitations in claim 12 are substantially the same as those in claim 5, therefore the same rationale for rejection applies.
Claims 7 and 15 are rejected under 35 U.S.C. 103 as being unpatentable over Ruff, in view of Zlateski, further in view of Francini et al. (U.S. Patent Application Publication No. 2020/0042871), hereinafter Francini.
Regarding claim 7,
Ruff and Zlateski jointly teach The method according to claim 1,
Francini teaches the following further limitation that neither Ruff nor Zlateski teaches:
wherein the input data segments belong to a single channel ((Francini [0096]) “similar considerations apply if the input image 110(0)…comprises a different number of channels 110(0)(k(0)) (such as a single channel 110(0)(1) in case of a gray-scale input image 110(0))”)
At the time of filing, one of ordinary skill in the art would have motivation to combine Ruff, Zlateski, and Francini by taking the method for performing 3D neural network convolution with a 3D input of claim 1, jointly taught by Ruff and Zlateski, and having segments of the input data belong to a single channel, taught by Francini, as gray-scale images have a single channel, and use of gray-scale images provides the predicable benefit of using input that requires less memory to store, as there is no color information to store. Such a combination would be obvious.
Regarding claim 15,
Claim 15 recites a non-transitory machine-readable storage medium for performing the function of the method of claim 7. All other limitations in claim 15 are substantially the same as those in claim 7, therefore the same rationale for rejection applies.
Claim 16 is rejected under 35 U.S.C. 103 as being unpatentable over Ruff, in view of Zlateski, further in view of Avni et al. (International Patent Application Publication No. 2018/162933), hereinafter Avni.
Regarding claim 16,
Claim 16 recites a device for performing the function of the method of claim 1. Specifically, claim 16 recites A device for neural network convolution, the device comprising: processing circuitry configured to:. Ruff teaches (Ruff Abstract) “A computational device performs the operation of a bank of convolutional filters commonly used in a convolutional neural network”.
Additionally, claim 16 recites the additional further limitation not present in claim 1: receive a three dimensional (3D) data input from a depth image capture device. Avni teaches (Avni Pg. 18, lines 23-27) “The method comprises: (1) capturing depth information, using one or more optical measurement devices such as LiDAR; and then (2) adding the depth information to each captured image of a scene, captured using one or more image capture devices, such as cameras mounted on a vehicle, and identifying areas of the image of interest”, with optical measurement devices such as LiDAR corresponding to depth image capture devices.
At the time of filing, one of ordinary skill in the art would have motivation to combine Ruff, Zlateski, and Avni by taking the device for performing 3D neural network convolution with a 3D input, jointly taught by Ruff and Zlateski, and having the 3D input be captured by a depth image capture device, taught by Avni, as depth image capture devices are well-known means of acquiring 3D image inputs, and they provide the predictable benefit of providing more reliable depth information than what can be estimated from a 2D image capture device. Such a combination would be obvious.
All other limitations in claim 16 are substantially the same as those in claim 1, therefore the same rationale for rejection applies.
Claim 20 is rejected under 35 U.S.C. 103 as being unpatentable over Ruff, in view of Zlateski, further in view of Avni, further in view of Wang.
Regarding claim 20,
Claim 20 recites a device for performing the function of the method of claim 5. All other limitations in claim 20 are substantially the same as those in claims 5, therefore the same rationale for rejection applies.
Claim 22 is rejected under 35 U.S.C. 103 as being unpatentable over Ruff, in view of Zlateski, further in view of Avni, further in view of Francini.
Regarding claim 22,
Claim 22 recites a device for performing the function of the method of claim 7. All other limitations in claim 22 are substantially the same as those in claims 7, therefore the same rationale for rejection applies.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Zhang (U.S. Patent Application Publication No. 2020/0265306) teaches a method of convolution for a convolutional neural network, including slicing input data depth-wise into slices of variable depth thickness, in order to be able to use smaller convolution kernels to process the input data.
Son et al. (U.S. Patent Application Publication No. 2020/0372276) teaches a method of performing convolutions for a convolutional neural network in one of two operating modes, based on characteristics of the data used.
Mittal “A survey of accelerator architectures for 3D convolution neural networks” teaches an overview of hardware accelerators and optimizations for 3D convolutional neural networks.
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to VICTOR A NAULT whose telephone number is (703) 756-5745. The examiner can normally be reached M - F, 12 - 8.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Miranda Huang can be reached at (571) 270-7092. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/V.A.N./Examiner, Art Unit 2124
/Kevin W Figueroa/Primary Examiner, Art Unit 2124