DETAILED ACTION
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 .
Priority
Receipt is acknowledged of certified copies of papers required by 37 CFR 1.55.
Information Disclosure Statement
The reference listed in paragraphs 11-12 of the specification is not a proper information disclosure statement. 37 CFR 1.98(b) requires a list of all patents, publications, or other information submitted for consideration by the Office, and MPEP § 609.04(a) states, "the list may not be incorporated into the specification but must be submitted in a separate paper." Therefore, unless the references have been cited by the examiner on form PTO-892, they have not been considered.
Drawings
The following is a quotation of 37 CFR 1.84(p)(5) and 37 CFR 1.84(u)(1):
(p)(5) Reference characters not mentioned in the description shall not appear in the drawings. Reference characters mentioned in the description must appear in the drawings.
(u)(1) The different views must be numbered in consecutive Arabic numerals, starting with 1, independent of the numbering of the sheets and, if possible, in the order in which they appear on the drawing sheet(s). Partial views intended to form one complete view, on one or several sheets, must be identified by the same number followed by a capital letter. View numbers must be preceded by the abbreviation "FIG." Where only a single view is used in an application to illustrate the claimed invention, it must not be numbered and the abbreviation "FIG." must not appear.
The drawings are objected to as failing to comply with 37 CFR 1.84(p)(5) because they do not include the following reference signs mentioned in the description: “(1)” or “(2)”. See, e.g., paragraphs 10, 40, 41, 51, 71, 81 and 91-93. These are reference characters mentioned in the description and therefore must appear in the drawings. The Examiner suggests amending the description to replace “method (1)” and “method (2)” with “first extraction method” and “second extraction method” or the like.
The drawings are objected to as failing to comply with 37 CFR 1.84(p)(u)(1) because view numbers are preceded by “Fig.” instead of “FIG.” The Examiner suggests filing replacement drawings that use “FIG.” to designate each view.
Figure 5 is objected to because of the following informalities: reference character “10” is used to designate the “transformer processing unit”, but the description refers to a “sparse transformer unit” in relation to the reference character “10”. See, e.g., paragraphs 29-34. The Examiner suggests filing a replacement sheet for Figure 5 that replaces “transformer processing unit” with “sparse transformer processing unit”.
Figure 12 is objected to because of the following informalities: the language “, ETC.” should be removed because neither the drawings nor the description explain what is encompassed by “ETC”. The description at paragraph 127 describes the “communication interface 117” as meditating “data transmission between the CPU 111 and another computer”. The Examiner suggests filing a replacement sheet for Figure 12 that replaces “OTHER COMPUTER, ETC.” with “OTHER COMPUTER”.
Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. The figure or figure number of an amended drawing should not be labeled as “amended.” If a drawing figure is to be canceled, the appropriate figure must be removed from the replacement sheet, and where necessary, the remaining figures must be renumbered and appropriate changes made to the brief description of the several views of the drawings for consistency. Additional replacement sheets may be necessary to show the renumbering of the remaining figures. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
Specification
The title of the invention is not descriptive. A new title is required that is clearly indicative of the invention to which the claims are directed.
The current title is “IMAGE PROCESSING APPARATUS, IMAGE PROCESSING METHOD, AND COMPUTER-READABLE RECORDING MEDIUM”. The terms “apparatus”, “method” and “computer-readable recording medium” are generic and “image processing” refers to every conceivable image processing method. The application is concerned with a sparse attention mechanism for Vision Transformers, not a general image processing technique.
Appropriate correction is required.
Claim Objections
Claims 1, 9 and 10 are objected to because of the following informalities: “a plurality of sparse transformer units, wherein the sparse transformer units each comprise” in claim 1, “a plurality of sparse transformer processes, wherein the sparse transformer processes each execute” in claim 9 and “a plurality of sparse transformer processes, and the sparse transformer processes each execute” in claim 10 should be clarified to change “the sparse transformer units” and “the sparse transformer processes” to refer to the plurality and not just the units/processes to avoid confusion as to whether all or a subset of the plurality is being referenced.
Claims 1-3, 9 and 10 are objected to because of the following informalities: each instance of “the first feature vectors” and “the second feature vectors” should be changed to “the plurality of first feature vectors” and “the plurality of second feature vectors” to clarify which vectors amongst each “plurality” of vectors is being referenced.
Appropriate correction is required.
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f):
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f). The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f). The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) except as otherwise indicated in an Office action.
This application includes claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) because the claim limitations use a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitations are:
“a plurality of sparse transformer units, wherein the sparse transformer units each comprise: an extraction unit that: uses a matrix formed such that a plurality of first feature vectors at a first time point constitute rows and a matrix formed such that a plurality of second feature vectors at a second time point that is earlier than the first time point constitute rows to calculate, for each of the first feature vectors, the difference between the first feature vector and a second feature vector corresponding to the first feature vector; and, based on the difference, extracts a feature vector that is a computation target from among the first feature vectors; and a transformer processing unit that includes a plurality of matrix multipliers that execute matrix multiplication computation using the plurality of first feature vectors, wherein each of the matrix multipliers: executes matrix multiplication computation for the feature vector that is a computation target; and does not execute matrix multiplication computation and uses a result of the matrix multiplication computation at the second time point for a feature vector that is not a computation target among the first feature vectors” in claims 1-8.
“a feature-vector generation unit that sequentially acquires images, splits each of the acquired images into a preset number of images, and generates a feature vector for each split image obtained by the splitting” in claims 2, 3, 7 and 8.
“the transformer processing unit includes a first computation unit, and each of a plurality of matrix multipliers included in the first computation unit executes matrix multiplication computation using a matrix formed by the feature vector that is a computation target and a matrix formed using weight parameters obtained in advance by learning” in claim 4.
“an attention processing unit, and a matrix multiplier included in the attention processing unit, upon executing matrix multiplication computation: uses elements included in a column and a row indicated by the row number of the feature vector that is a computation target as elements that are computation targets in the matrix multiplication computation; executes matrix multiplication computation only for the elements that are computation targets; and does not execute the matrix multiplication computation and uses a result of the matrix multiplication computation at the second time point for elements that are not the computation targets” in claim 6.
“an attention processing unit, and a matrix multiplier included in the attention processing unit, upon executing matrix multiplication computation: uses an element corresponding to the position of the selected element as an element that is a computation target in the matrix multiplication computation; executes matrix multiplication computation only for the element that is a configuration target; and does not execute the matrix multiplication computation and uses a result of the matrix multiplication computation at the second time point for an element that is not the computation target” in claim 8.
Because these claim limitations are being interpreted under 35 U.S.C. 112(f), they are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
If applicant does not intend to have these limitations interpreted under 35 U.S.C. 112(f), applicant may: (1) amend the claim limitations to avoid them being interpreted under 35 U.S.C. 112(f) (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitations recite sufficient structure to perform the claimed function so as to avoid them being interpreted under 35 U.S.C. 112(f).
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
Claims 1-10 are rejected under 35 U.S.C. 112(b) as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
The phrase “such that” in claims 1, 9 and 10 creates confusion as to whether the subject matter it describes is included or merely serves as an example. The broadest reasonable interpretation (BRI) of the phrase “such that” is: to express purpose or result.1 As a representative example, claim 1 recites, “wherein the sparse transformer units each comprise: an extraction unit that: uses a matrix formed such that a plurality of first feature vectors at a first time point constitute rows and a matrix formed such that a plurality of second feature vectors at a second time point that is earlier than the first time point constitute rows to calculate, for each of the first feature vectors, the difference between the first feature vector and a second feature vector corresponding to the first feature vector; and, based on the difference”. According to the BRI, the above subject matter specifies two matrices, where the matrices are formed (i) for the purpose of having or (ii) resulting in the various feature vectors at certain time points. It is thus unclear from the language presented whether Applicant intended for the claims to require a first matrix that includes a plurality of first feature vectors at a first time point constitute rows and a second matrix that includes a plurality of second feature vectors at a second time point that is earlier than the first time point constitute rows, or first and second matrices formed with such vectors as an intended purpose or result but do not ultimately contain such vectors at the moment of use by the apparatus of claim 1, the method of claim 9 or the recorded program of claim 10. The phrase “such that” is akin to the phrase “for example”, which renders the claims indefinite because it is unclear whether the limitation(s) following the phrase are part of the claimed invention. See MPEP § 2173.05(d). For purposes of applying prior art, the phrase “formed such that” is interpreted as “including” or “that includes” or the like. Dependent claims 2-8 are rejected for inheriting and not curing the deficiencies of claim 1.
Claims 1, 9 and 10 recite “the difference between the first feature vector and a second feature vector corresponding to the first feature vector”. The limitation of “the difference” is ambiguous because feature vectors can have any number of differences and the claims do not provide sufficient context to describe only one such difference. For example, a difference between two vectors can be a difference in value of only one parameter of each vector or any number of parameters. A “difference” could be a mathematical difference or a semantic difference, for example. Accordingly, “the difference” lacks a proper antecedent basis. For purposes of applying prior art, the first instance of “the difference” is interpreted as “a [[the]] distance”. Dependent claims 2 and 4-8 are rejected for inheriting and not curing the deficiencies of claim 1. Dependent claim 3 does not inherit the same deficiencies because the antecedent basis of “the difference” is clarified: “calculate, as the difference for each of the first feature vectors, an absolute value of a difference value between the first feature vector and the second feature vector corresponding to the second split image at the same position as the first split image corresponding to the first feature vector” (emphasis added).
Claims 1, 9 and 10 recite claim limitations that are confusing and contradictory. As a representative example, claim 1 recites “a transformer processing unit that includes a plurality of matrix multipliers that execute matrix multiplication computation using the plurality of first feature vectors, wherein each of the matrix multipliers: executes matrix multiplication computation for the feature vector that is a computation target; and does not execute matrix multiplication computation and uses a result of the matrix multiplication computation at the second time point for a feature vector that is not a computation target among the first feature vectors” (emphasis added). On its face, this language requires the transformer processing unit to both execute and not execute matrix multiplication, which creates confusion as to when the multiplication occurs and when it does not occur and whether either processing pathway is optional. From the description, e.g., paragraphs 30-32 and 90-92, it appears that Applicant intended to convey the concept that matrix multiplication, i.e., dot product or kernel, is executed for computation targets in patches at a current time t and is skipped for elements that do not correspond to a computation target at the current time t, where instead of executing matrix multiplication for elements that are not the computation target, a result of matrix multiplication executed in the prior time step t -1 is used for the non-targets at the current time t. However, even in that case, matrix multiplication is still executed. The claims do not specify that “does not execute matrix multiplication computation” applies only to the elements that are not the computation target at the current time. Accordingly, for purposes of applying prior art, “does not execute matrix multiplication computation and uses a result” is interpreted as forgoing matrix multiplication in the current time, where the current time t is the “first time point” and the “second time point” is t – 1. Dependent claims 2-8 are rejected for inheriting and not curing the deficiencies of claim 1.
Claim 4 recites “a matrix formed by the feature vector that is a computation target and a matrix formed using weight parameters obtained in advance by learning” (emphasis added). It is unclear whether the image processing apparatus of claim 4 or some other device(s) performing the learning of the “weight parameters obtained in advance”. If the apparatus of claim 4 performs the learning process, the scope of claim 4 is substantively different than if the apparatus is interpreted as merely retrieving stored weights. The component or program responsible for performing the obtaining and/or the learning is unspecified. The description does not provide sufficient clarification. It thus remains ambiguous as to whether Applicant intended the apparatus to retrieve stored weight parameters or learn them in advance for later retrieval. For purposes of applying prior art, “a matrix formed by the feature vector that is a computation target and a matrix formed using weight parameters obtained in advance by learning” is interpreted as “a matrix formed by the feature vector that is a computation target and a matrix formed using learned weight parameters
Claim 8 recites “uses an element corresponding to the position of the selected element as an element that is a computation target in the matrix multiplication computation; executes matrix multiplication computation only for the element that is a configuration target; and does not execute the matrix multiplication computation and uses a result of the matrix multiplication computation at the second time point for an element that is not the computation target” (emphasis added). However, claim 1 recites “extracts a feature vector that is a computation target from among the first feature vectors; and a transformer processing unit that includes a plurality of matrix multipliers that execute matrix multiplication computation using the plurality of first feature vectors, wherein each of the matrix multipliers: executes matrix multiplication computation for the feature vector that is a computation target; and does not execute matrix multiplication computation and uses a result of the matrix multiplication computation at the second time point for a feature vector that is not a computation target among the first feature vectors” (emphasis added). While the target in the phrase “the element that is a configuration target” is assumed to refer to the same as the target in the phrase “an element that is a computation target”, it is unclear which target corresponds to “an element that is not the computation target” given there are numerous instances of “a computation target”. For purposes of applying prior art, each “computation target” is assumed to be the same target amongst each of the image “splits”, i.e., image patches.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 1, 2, 4-6, 9 and 10 are rejected under 35 U.S.C. 103 as being unpatentable over Eventful Transformers: Leveraging Temporal Redundancy in Vision Transformers (published 25 August 2023) to Dutson et al. (hereinafter “Dutson”) in view of WIPO Pat. Appl. Pub. No. 2023049726 (published 30 March 2023) to Li et al. (hereinafter “Li”).
Regarding claim 1, Dutson teaches an image processing apparatus (Dutson, section 1, “We demonstrate wall-time speedups on both the CPU and GPU. … Perhaps unsurprisingly, reusing computation from previous time steps requires maintaining some tensors in memory. These memory overheads are relatively modest; see Section 6 for further discussion”) comprising a plurality of sparse transformer units (Dutson, Figure 1, “each Transformer block”), wherein the sparse transformer units each comprise:
an extraction unit that (Dutson, section 5.3, “a CPU (Xeon Silver 4214, 2.2 GHz) and a GPU (NVIDIA RTX 3090)”. The gate module receives N input tokens, determines which of the N tokens should be updated, and extracts the selected tokens using a gather operation. See Dutson at section 4.1, steps 1-3): uses a matrix (N x D matrix where each of the N token/feature vectors constitutes a row of the matrix. See Dutson at sections 3, 4.1) formed such that a plurality of first feature vectors at a first time point constitute rows and a matrix formed such that a plurality of second feature vectors at a second time point constitute rows to calculate, for each of the first feature vectors, the difference between the first feature vector and a second feature vector corresponding to the first feature vector (For each current token/feature vector row, Dutson computes the difference from its corresponding stored reference-token row. At each time step, the current tokens are compared against their references. See Dutson at section 4.1); and, based on the difference, extracts a feature vector that is a computation target from among the first feature vectors (Dutson applies a selection policy to the calculated error (difference) which returns a binary mask or a list of token indices, identifying the feature vectors that are to be updated. See Dutson at sections 4.1 and 4.3); and
a transformer processing unit (Dutson, section 5.3, “a CPU (Xeon Silver 4214, 2.2 GHz) and a GPU (NVIDIA RTX 3090)”) that includes a plurality of matrix multipliers that execute matrix multiplication computation using the plurality of first feature vectors (The Q, K and V matrix transforms of the Transform block. See Dutson, equations (3)-(5) and sections 3 and 4.2), wherein each of the matrix multipliers: executes matrix multiplication computation for the feature vector that is a computation target (The selected tokens are passed through the transform by the gate while the others are skipped. See Dutson at section 4.2, Figures 3-6); and does not execute matrix multiplication computation and uses a result of the matrix multiplication computation at the second time point for a feature vector that is not a computation target among the first feature vectors (Computation for tokens not selected by the gate is skipped and their earlier computed values are retained/reused. See Dutson at section 4.2).
Dutson does not teach that which is explicitly taught by Li.
Li teaches a second time point that is earlier than the first time point (A set of tokens having features to be reused from an earlier frame and a set of features to be recomputed from a later frame are identified. A binary gate determines whether to use a previously computed feature from the earlier segment or generate a new current feature, where the gate may block re-computation where the prior feature is reused. See Li at pars. 58-60, 60-64 and 72).
Dutson discloses an event-based sparse Transformer architecture that performs Transformer matrix computations as necessary for selected tokens and retains or reuses earlier computed results for the remaining tokens. Thus, Dutson shows that it was known in the art before the effective filing date of the claimed invention to skip matrix multiplication and re-use computed values from prior frames (but does not necessarily guarantee that the reused tokens are from an earlier frame because they can be retained over multiple frames), which is analogous to the claimed invention in that it is pertinent to the problem being solved by the claimed invention, reducing computations of a vision Transformer. Li discloses a Transformer architecture that groups corresponding tokens from two video frames at respective earlier and later times, identifies changed current-frame tokens for computation, and reuses previously computed features of the earlier frame for the unchanged tokens. Thus, Li shows that it was known in the art before the effective filing date of the claimed invention to reuse previous computations from an earlier frame, which is analogous to the claimed invention in that it is pertinent to the problem being solved by the claimed invention, reducing computations of a vision Transformer.
A person of ordinary skill in the art would have been motivated to modify the update policy disclosed by Dutson to reuse computed values from the preceding frame as disclosed by Li, to thereby reuse values from the prior frame instead of any prior value. Based on the foregoing, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have made such modification according to known methods to yield the predictable results to have the benefit of reducing Transformer computations.
Regarding claim 2, Dutson in view of Li teaches the image processing apparatus according to claim 1 further comprising a feature-vector generation unit (Dutson, section 5.3, “a CPU (Xeon Silver 4214, 2.2 GHz) and a GPU (NVIDIA RTX 3090)”) that sequentially acquires images, splits each of the acquired images into a preset number of images (number of patches), and generates a feature vector for each split image obtained by the splitting (Dutson, section 5.1, “Before the backbone, the model maps each 16×16 image patch to a token vector using a linear transform. The model expects fixed-size inputs (due to resolution-specific position embeddings).”).
Regarding claim 4, Dutson in view of Li teaches the image processing apparatus according to claim 1, wherein the transformer processing unit includes a first computation unit (Dutson, section 5.3, “a CPU (Xeon Silver 4214, 2.2 GHz) and a GPU (NVIDIA RTX 3090)”), and
each of a plurality of matrix multipliers (Dutson, section 3, “The self-attention operator first applies three linear transforms Wq, Wk, Wv”, equation (3)) included in the first computation unit executes matrix multiplication computation using a matrix formed by the feature vector that is a computation target (The matrix containing the selected token vectors, i.e., “
PNG
media_image1.png
19
20
media_image1.png
Greyscale
”. See Dutson at section 4.1) and a matrix formed using weight parameters (Dutson, section 3, “Wq, Wk, Wv”) obtained in advance by learning (Dutson, section 5.1, “we fine-tune before we add temporal redundancy awareness to the model.” Original emphasis.).
Regarding claim 5, Dutson in view of Li teaches the image processing apparatus according to claim 1,
wherein the extraction unit further
generates computation-target identification information that includes information indicating a row number of the feature vector that is a computation target (The gate applies a selection policy that produces binary mask or list of token indices identifying the selected tokens for re-computation, which are then gathered along the first axis of the token matrix. See Dutson at section 4.1. Because the token vectors are the rows of that matrix, the selected token indices identify the row numbers of the feature vectors that are computation targets.).
Regarding claim 6, Dutson in view of Li teaches the image processing apparatus according to claim 5,
wherein the transformer processing unit includes an attention processing unit (Dutson, section 5.3, “a CPU (Xeon Silver 4214, 2.2 GHz) and a GPU (NVIDIA RTX 3090)”), and
a matrix multiplier included in the attention processing unit, upon executing matrix multiplication computation: uses elements included in a column and a row indicated by the row number of the feature vector that is a computation target as elements that are computation targets in the matrix multiplication computation (An element needs updating when the ith row of q changes or the jth column of kT. See Dutson at section 4.2, Figure 5); executes matrix multiplication computation only for the elements that are computation targets (Dutson, Fig. 5, “We reduce the cost of computing B = q kT by only updating a subset of its elements”); and does not execute the matrix multiplication computation and uses a result of the matrix multiplication computation at the second time point for elements that are not the computation targets (Matrix multiplication is performed for the affected row/column elements while the previous timestep results remain in place for elements that are not computation targets. See Dutson at Figure 5).
Claim 9 substantially corresponds to claim 1 by reciting a method corresponding to the functions of the apparatus of claim 1 (Dutson, section 5.3, “a CPU (Xeon Silver 4214, 2.2 GHz) and a GPU (NVIDIA RTX 3090)”).
Claim 9 is rejected for the same reasons of obviousness as provided for claim 1.
Claim 10 substantially corresponds to claim 1 by reciting a non-transitory computer readable recording medium (Dutson, section 6, “memory”) that includes a program recorded thereon, wherein the program causes a computer (Dutson, section 5.3, “a CPU (Xeon Silver 4214, 2.2 GHz) and a GPU (NVIDIA RTX 3090)”) to execute the method of claim 1.
Claim 10 is rejected for the same reasons of obviousness as provided for claim 1.
Claim 3 is rejected under 35 U.S.C. 103 as being unpatentable over Dutson in view of Li and in further view of U.S. Pat. Appl. Pub. No. 20090083228 to Shatz et al. (hereinafter “Shatz”).
Regarding claim 3, Dutson in view of Li teaches the image processing apparatus according to claim 2,
wherein the extraction unit:
uses the first feature vectors corresponding to first split images generated by splitting a first image acquired at the first time point and the second feature vectors corresponding to second split images generated by splitting a second image acquired at the second time point (A set of tokens having features to be reused from an earlier frame and a set of features to be recomputed from a later frame are identified. A binary gate determines whether to use a previously computed feature from the earlier segment or generate a new current feature, where the gate may block re-computation where the prior feature is reused. See Li at pars. 58-60, 60-64 and 72) to calculate, as the difference for each of the first feature vectors, a value of a difference value between the first feature vector and the second feature vector corresponding to the second split image at the same position as the first split image corresponding to the first feature vector (The error is the difference. See Dutson at section 4.1); and
for each of the first feature vectors, calculates a total sum of feature amounts included in the first feature vector (Dutson, Figure 2, “total error”), and, if a calculated total sum is greater than or equal to a preset first threshold, extracts the first feature vector corresponding to the total sum that is greater than or equal to the first threshold as a feature vector that is a computation target (The L2 norm is used to select the tokens with the largest norm. See Dutson at section 4.3).
The rationale for obviousness is the same as provided for claim 2.
Dutson in view of Li does not teach that which is explicitly taught by Shatz.
Shatz teaches an absolute value of a difference value between the first feature vector and the second feature vector and calculating a total sum of feature amounts (Shatz, par. 101, “the content tracker may determine the similarity between feature vectors using the sum of absolute differences (SAD)”. SAD is the L1 norm of the difference between two vectors.). Dutson and Li are analogous to the claimed invention for the reasons above. Shatz discloses multi-frame feature matching that computes the SAD to determine the difference between feature vectors. Thus, Shatz shows that it was known in the art before the effective filing date of the claimed invention to use the L1 norm to determine the sum of absolute differences between feature vectors, which is analogous to the claimed invention in that it is pertinent to the problem being solved by the claimed invention, reducing computations of a vision Transformer.
A person of ordinary skill in the art would have been motivated to replace the L2 norm disclosed by Dutson in view of Li with the L1 norm/SAD disclosed by Shatz, to thereby use the L1 norm/SAD as the difference measure employed by the temporal gating. Based on the foregoing, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have made such modification according to known methods to yield the predictable results to have the benefit of preventing or mitigating overfitting.
Claims 7 and 8 are rejected under 35 U.S.C. 103 as being unpatentable over Dutson in view of Li, in view of Shatz and in further view of Sparsifiner: Learning Sparse Instance-Dependent Attention for Efficient Vision Transformers to Wei et al. (hereinafter “Wei”).
Regarding claim 7, Dutson in view of Li and in further view of Shatz teaches the image processing apparatus according to claim 3 (Current tokens for re-computation are selected based on temporal error. See Dutson at section 4.1), but does not teach that which is explicitly taught by Wei.
Wei teaches wherein the extraction unit further:
generates a computation-target extraction matrix by executing accumulative computation using the feature vector that is a computation target (Generating token features, forming query and key representations, and computing a matrix from the matrix product. See Wei at section 3, equations (1) and (2).); and, if an element in the computation-target extraction matrix is greater than or equal to a preset second threshold, selects the element that is greater than or equal to the second threshold (Wei, section 3, equation (2)) and generates computation-target identification information that includes information indicating the position of the selected element in the computation-target extraction matrix (Generating a sparse connectivity mask, where non-zero elements identify the token connectivity positions for computation. Individual connectivity is pruned rather than complete rows or columns. See Wei at section 3, equations (2) AND (3)).
Dutson, Li and Shatz are analogous to the claimed invention for the reasons provided above. Wei discloses learning sparse attention for vision Transformers and an element-level connectivity mask predictor to identify which individual attention computations associated with the selected target tokens should be performed. Thus, Wei shows that it was known in the art before the effective filing date of the claimed invention to use an element-level connectivity mask to identify computation targets, which is analogous to the claimed invention in that it is pertinent to the problem being solved by the claimed invention, reducing computations of a vision Transformer.
A person of ordinary skill in the art would have been motivated to combine the temporal sparse Transformer disclosed by Dutson in view of Li and in further view of Shatz with the element-level connectivity mask predictor disclosed by Wei, to thereby identify which individual attention computations associated with already-selected computation targets should be performed, i.e., identifies the position of the selected element. Based on the foregoing, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have made such modification according to known methods to yield the predictable results to have the benefit of finer-grained sparsity.
Regarding claim 8, Dutson in view of Li, in further view of Shatz and in further view of Wei teaches the image processing apparatus according to claim 7,
wherein the transformer processing unit includes an attention processing unit (Dutson, section 5.3, “a CPU (Xeon Silver 4214, 2.2 GHz) and a GPU (NVIDIA RTX 3090)”. ), and
a matrix multiplier included in the attention processing unit, upon executing matrix multiplication computation (Attention processing performs query-key matrix multiplication to calculate B. See Dutson at section 4.2); and does not execute the matrix multiplication computation and uses a result of the matrix multiplication computation at the second time point for an element that is not the computation target (Recomputing selected portions of B and scattering the newly computed values into the old B. See Dutson at section 4.2), but does not teach that which is explicitly further taught by Wei.
We further teaches uses an element corresponding to the position of the selected element as an element that is a computation target in the matrix multiplication computation (Generating a sparse connectivity mask with nonzero positions that identify the individual attention matrix elements selected for computation. See Wei at section 3, equations (2)-(5)); executes matrix multiplication computation only for the element that is a configuration target (Generating a sparse connectivity mask to compute only the nonzero elements of the sparse attention matrix such that the individual matrix identified by the mask are computed while the unselected elements are omitted. See Wei at section 3, equations (4) and (5)).
Dutson, Li, Shatz and Wei are analogous to the claimed invention for the reasons provided above.
A person of ordinary skill in the art would have been motivated to modify the temporal sparse attention of Dutson in view of Li, in further view of Shatz and in further view of Wei by using the identified matrix position(s) to restrict the attention computation to the corresponding attention matrix elements while retaining/reusing previously computed values for the remaining unchanged elements as further disclosed by Wei, to thereby use the identified matrix positions as computation targets in the matrix multiplication. Based on the foregoing, it would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have made such modification according to known methods to yield the predictable results to have the benefit of further reducing unnecessary computation by re-computing only the selected matrix elements while retaining the prior timestep’s results for the remaining elements.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to RYAN P POTTS whose telephone number is (571)272-6351. The examiner can normally be reached M-F, 9am-5pm EST.
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, Sumati Lefkowitz can be reached at 571-272-3638. 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.
/RYAN P POTTS/Examiner, Art Unit 2672
1 See https://web.archive.org/web/20160313184601/https://www.collinsdictionary.com/dictionary/english/such-that.
Prosecution Insights