DETAILED ACTION
Notice of Pre-AIA or AIA Status
1. The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Notice to Applicants
2. This communication is in response to the application filed on 01/22/2025.
3. Claims 1-20 are pending.
4. Limitations appearing inside {} are intended to indicate the limitations not taught by said prior art(s)/combinations.
Information Disclosure Statement
5. The information disclosure statement (IDS) submitted on 01/22/2025 has been considered by the examiner.
Claim Rejections - 35 USC § 101
6. 35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
7. Claim 17-20 are rejected under 35 U.S.C. 101 because the claimed invention is directed to non-statutory subject matter. The claims do not fall within at least one of the four categories of patent eligible subject matter because they are directed toward a software per se (see MPEP 2106.03). The examiner specifically notes that the BRI of the computer readable storage mediums fails to specifically provide the program product with a physical or tangible form. The examiner encourages the applicant to amend “…one or more non-transitory computer readable storage mediums…”, which would obviate the rejection by clearly stating the computer-readable storage medium is of a non-transitory nature.
Claim Rejections - 35 USC § 103
8. 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.
9. Claims 1-7, 9-15, and 17-20 are rejected under 35 U.S.C. 103 as being unpatentable over “Fast and Simple Agglomerative LBVH Construction” to Apetrei (hereinafter Apetrei), and further in view of “Optimized LBVH-Construction and Hierarchy-Traversal to accelerate kNN queries on Point Clouds using the GPU” to Jakob et al. (hereinafter Jakob).
10. Regarding Claim 1, Apetrei discloses a method comprising ([pg. 1, Abstract, par. 1, ln. 1-8] “This paper continues the long-standing tradition of gradually improving the construction speed of spatial acceleration structures using sorted Morton codes. Previous work on this topic forms a clear sequence where each new paper sheds more light on the nature of the problem and improves the hierarchy generation phase in terms of performance, simplicity, parallelism and generality. Previous approaches constructed the tree by firstly generating the hierarchy and then calculating the bounding boxes of each node by using a bottom-up traversal. Continuing the work, we present an improvement by providing a bottom-up method that finds each node’s parent while assigning bounding boxes, thus constructing the tree in linear time in a single kernel launch. Also, our method allows clustering the sorted points using an user-defined distance metric function”):
mapping, by a hardware processor ([pg. 3, col. 2, 5. Results, par. 1, ln. 1-6] “To explore the performance of our algorithms, we have implemented them in CUDA 6.0 along with the method proposed by Karras [Kar12] and benchmarked their performance on a NVIDIA GeForce 745M installed in a laptop with 2.60 GHz Intel Core i5 CPU running Windows 8.1.”), 2-dimensional locations of a plurality of bounding boxes of a digital image to 1-dimensional locations ([pg. 1, col. 2, 2. Background, par. 1, ln. 7 to par. 2, ln. 12] “The first parallel linear BVH construction method was introduced by Lauterbach et al. [LGS*09]. The method starts by assigning a Morton code to each primitive’s barycenter or centroid, sorting them according to the Morton codes and then constructing the hierarchy by splitting where the highest bit differs between two Morton codes. A Morton code can be computed by mapping each coordinates to unit cube [0,1]3 relative to the scene and interleaving each of the binary digits. The algorithm consists of several dependent processing steps, requires large temporary buffers, and is an order of magnitude slower than e.g. sorting the Morton codes… In 2012, Karras [Kar12] presented a fast method for constructing BVHs, k-d trees and octrees on the GPU that would be completely pointless on a single-core processor, but leads to substantial gains in a parallel setting. The algorithms generates all nodes of the tree simultaneously in a fully data-parallel fashion, requires no temporary storage, consists of a single fully parallelizable loop, and executes roughly two orders of magnitude faster than [LGS*09]. After construction, he used a parallel bottom up reduction algorithm to calculate the bounding boxes. We aim to improve the method by using only the bottom up algorithm.”, [pg. 4, col. 1, par. 1, ln. 1-16] “Table 1 shows a breakdown of hierarchy construction time for a set of test scenes. We have used the thrust library to sort the keys for all methods and used 30-bit Morton codes. The method presented by Karras has two values, one representing the hierarchy construction and the other one the bounding box calculation. Our radix tree construction algorithm is implemented in a single kernel launch. The last column is a variant of our hierarchy building method which uses the squared distance between centroids as the d function. We first used a kernel launch to precompute the squared distances and then another kernel launch to create the hierarchy. The difference in construction time between the method proposed by Karras (Previous) and ours gradually increases with the number of triangles. Both methods amount to less than 50% of the time required to sort the keys.”);
calculating distances between bounding box pairs sorted based on the 1-dimensional locations ([pg. 1, col. 2, 2. Background, par. 1, ln. 7 to par. 2, ln. 12], [pg. 2, Figure 1], [pg. 2, col. 1, 3. Binary Radix Tree Construction, par. 1, ln. 1 to par. 3, ln. 7] “A radix tree (also known as Patricia tree or radix trie or compact prefix tree) is a binary tree which is built based on the common prefixes of each key. In our case, keys are represented as bit strings. Each leaf node contains a single key and each internal node corresponds to the longest common prefix of all the keys it covers. Splitting a sequence of keys into two subsets summarizes to finding the highest differing bit. A naive construction algorithm would start partitioning the tree from the root by finding the first differing bit and then creating the child nodes and processing each child recursively. Karras [Kar12] introduced a novel binary radix tree construction algorithm and used it as a building block for other types of trees. In order to generate the hierarchy in fully parallel fashion, the algorithm processes each node independently and performs one binary search to find the range of keys that each internal node covers and another binary search to find the split point for every internal node in the hierarchy. Then it uses a bottom-up traversal algorithm for bounding box calculation where each thread starts from a single leaf and advances toward the root and every node calculates its bounding box by looking at the bounding box of the children. To avoid duplicate work, each internal node has an atomic flag which prevents the first thread to enter and lets the second one through. A binary radix tree is a compact tree in the sense every node either has two children or none. Therefore, a binary radix tree with n leaf nodes has n-1 internal nodes corresponding to a split point between two keys. In our approach we consider only ordered trees, where the keys are sorted and each internal node covers a linear range of keys.”, [pg. 2, col. 1, Algorithm, par. 1, ln. 1 to col. 2, par. 5, ln. 9] “In order to further optimize the construction algorithm, what we want is to do both hierarchy generation and bounding box calculation in a single kernel launch. To achieve this, we must construct the tree in a bottom-up fashion. What this means is that we start from each key and progressively group them together into larger and larger clusters until the root cluster containing all the keys is formed. Similar to [Kar12], the basic idea is to utilize a specific node layout to establish a connection between the indices of internal nodes and the ranges of keys that they cover. In the case of BVHs, [Kar12] uses the connection to determine the children of each internal node in a separate processing step, followed by a custom bottom-up reduction algorithm to calculate the per-node AABBs. Our approach combines the two steps by tracking the ranges of keys as a part of the bottom-up reduction and using them to deduce the index of the parent node at each step. Every leaf node covers a range of one key, and every internal node merges the ranges of its children. We choose a node layout where each internal node i will split the hierarchy between keys i and i+1. The split point of an internal node is defined by the last key of its left child and the first key of its right child. What this implies is that the highest differing bit between the keys covered by an internal node i will always be between keys i and i+1. In contrast to the method proposed by [Kar12], where for each node he uses a binary search to find the highest differing bit, in our layout this isn’t necessary as we already know it. From a bottom-up construction point of view, for a given node that covers keys [a,b], the node layout implies that indices a-1 and b will correspond to ancestors of the node and one of these ancestors will be its parent. The general idea of our method is that we can analyze a split position of a given internal node to measure the dissimilarity between two subtrees. Being a bottom-up hierarchy construction, we start from each individual key and use the split point as an indicator for which node to choose as parent. To choose the parent, we define a function d(i) as the index of the highest differing bit between the keys covered by node i. Because of the way a radix tree is defined, d(x) > d(y) must be true if x is the ancestor of y. Thus, we can conclude that the index of the parent node is a-1 if d(a-1) < d(b), and b otherwise. Because we already know where the highest differing bit is for each internal node, the d function basically represents a distance metric between two keys. Unlike the d used by [Kar12], we are interested in the index of the highest differing bit and not the length of the common prefix. In practice, logical xor can be used instead of finding the index of the highest differing bit as we can compare the numbers. The higher the index of the differing bit, the larger the number.”, [pg. 3, col. 2, Bonding Box Hierarchy, par. 1, ln. 1-14] “The particularly interesting aspect about this algorithm is that it allows one to use an arbitrary distance metric for d. This can be advantageous because the LBVH construction method can now be made independent of how we sort the points by choosing an appropriate metric. For example, for each internal node i, d(i) could compute the surface area of the two keys where the node splits the hierarchy. We can then choose the parent in the same mode by comparing the values returned by the d function. Alternatively, we can use the squared distance to compute the distance between two centroids. In these cases, it proved better to do a separate kernel launch where we compute the value of d corresponding to each internal node.”, [pg. 4, col. 1, par. 1, ln. 1-16]);
storing, by the hardware processor, {entries in a priority queue, wherein each entry specifies} a bounding box pair and a distance between the bounding box pair ([pg. 1, col. 2, 2. Background, par. 1, ln. 7 to par. 2, ln. 12], [pg. 2, Figure 1], [pg. 2, col. 1, 3. Binary Radix Tree Construction, par. 1, ln. 1 to par. 3, ln. 7], [pg. 2, col. 1, Algorithm, par. 1, ln. 1 to col. 2, par. 5, ln. 9], [pg. 3, col. 2, Bonding Box Hierarchy, par. 1, ln. 1-14], [pg. 4, col. 1, par. 1, ln. 1-16]);
representing, by the hardware processor, the plurality of bounding boxes as a binary search tree based on the 1-dimensional locations ([pg. 1, col. 2, 2. Background, par. 1, ln. 7 to par. 2, ln. 12], [pg. 2, Figure 1], [pg. 2, col. 1, 3. Binary Radix Tree Construction, par. 1, ln. 1 to par. 3, ln. 7], [pg. 2, col. 1, Algorithm, par. 1, ln. 1 to col. 2, par. 5, ln. 9], [pg. 3, col. 2, Bonding Box Hierarchy, par. 1, ln. 1-14], [pg. 4, col. 1, par. 1, ln. 1-16]); and
reducing, by the hardware processor, a number of the plurality of bounding boxes by merging a selected bounding box pair selected {from the priority queue} based on distance, wherein the merging creates a new bounding box ([pg. 1, col. 2, 2. Background, par. 1, ln. 7 to par. 2, ln. 12], [pg. 2, Figure 1], [pg. 2, col. 1, 3. Binary Radix Tree Construction, par. 1, ln. 1 to par. 3, ln. 7], [pg. 2, col. 1, Algorithm, par. 1, ln. 1 to col. 2, par. 5, ln. 9], [pg. 2, col. 2, par. 6, ln. 1 to pg. 3, col. 1, par. 1, ln. 18] “Let us assume that the leaf nodes and internal nodes are stored in two separate arrays, L and I, the same way as proposed by [Kar12]. Each leaf node stores exactly one key. The hierarchy construction starts from each leaf node and walks towards the root by finding the parent at each step. We process an internal node only after it has both its children set. To find the parent of each node we have to look at the nodes that split the hierarchy at the left and right ends of the keys covered by the respective node. We initially know that each leaf node Li covers the range of keys [i,i]. As we described earlier, we look at the internal nodes with the index i-1 and i and compare the values returned by the d function. The one with the lowest value will be the parent because it splits the hierarchy between two more similar clusters (subtrees) than the other node. Because each parent merges the ranges of its children, the current node will pass to the parent the opposite range of the keys it covers. When we reach an internal node the algorithm works in the same way as we only need to know the range of keys it covers in order to find the parent.”, [pg. 3, col. 1, 4. Overview, par. 1, ln. 1-18] “The algorithm for hierarchy construction can be summarized in 3 steps: (1) The first step consists of sorting the keys. (2) (Optional) We do a separate kernel launch in order to calculate the d function for each internal node beforehand. We can choose what the d function will compute depending on the application requirements. (3) We use a node layout where we associate each internal node to a split point between two keys. Then, we construct the hierarchy by starting from each leaf node. Because we know that leafs covers a single key, we can find the parent by choosing between the two ancestors at the left and right of the key it covers. We choose the parent according to the d function that indicates a distance metric between the two keys where each internal node splits the hierarchy, the one with the lower value is the parent. Each parent then merges the ranges of its children and uses it in the same manner to advance towards the root.”, [pg. 3, col. 2, Bonding Box Hierarchy, par. 1, ln. 1-14], [pg. 4, col. 1, par. 1, ln. 1-16]).
One of ordinary skill in the art, before the effective filing date of the claimed invention, would recognize the keys of Apetrei represent bounding boxes, and thus Apetrei reduces a number of the plurality of bounding boxes by merging a selected bounding box pair based on distance, and wherein the merging creates a new bounding box containing the previous boxes. Apetrei does not specifically disclose wherein the distance pairs are stored as entries in a priority queue, or are selected/popped from the priority queue during the merging of the boxes.
However, Jacob specifically teaches storing bounding box pairs as entries into a priority queue, and wherein merging is performed by selection of a bounding box pair from the priority queue ([pg. 127, Fig. 3], [pg. 127, col. 1, 4.2. Tree optimization, par. 1, ln. 1 to pg. 128, col. 1, par. 1, ln. 2] “By using Morton codes for fast hierarchy generation, however, the space is discretized into a grid. Depending on the data set size and Morton code resolution, the point density and distribution within the data set, it may occur that many points share the same Morton key and are thus placed in the same leaf node, while the majority of the remaining leaves contain only one or very few data points. In terms of data-parallel processing this effect is adverse as it causes diverging threads during a tree traversal and thus a performance drop. In order to alleviate this problem, we try to create a more shallow hierarchy with leaf nodes of ideally equal data density, as outlined in Figure 2. This is achieved by a second bottom-up traversal of the initial LBVH. At each inner node we decide whether to reduce it into a leaf node (depending on the data density of the left and right children) and continue upwards, or to do nothing and stop the traversal. Merged nodes, that are no longer needed are flagged accordingly. To prevent race conditions between two threads coming from a left and right subtree, only one thread is allowed to collapse and continue (see line 6 in Algorithm 3). The procedure is outlined in Algorithm 3. This way we incrementally fuse spatially related parts of the dataset without destroying the underlying tree and at the same time can reuse the pre-calculated bounding volumes, which results in extremely fast processing. A visual example of this procedure applied to the tree in Figure 1 is shown in Figure 3. During the bottom-up traversal a heuristic ϕ decides whether an internal node becomes a leaf node. The necessary pointer adjustments are then performed by the MAKELEAF(...)-method. In the following both are described in detail: Collapse heuristic. The heuristic ϕ(node) decides whether the cur-rent node becomes a leaf node or not. We use a very simple point count limit: we compare the sum of the number of stored points in the left and right node with a user specified threshold and return true if this node should become a leaf node:
φ
v
=
t
r
u
e
i
f
∑
A
A
B
B
(
v
)
≤
Θ
f
a
l
s
e
e
l
s
e
with
∑
=
#
p
o
i
n
t
s
i
n
c
u
r
r
e
n
t
v
o
l
u
m
e
(
A
A
B
B
)
Θ
=
t
h
r
e
s
h
o
l
d
p
o
i
n
t
s
i
n
v
o
l
u
m
e
. This is trivial as we computed and stored the number of total contained points in each node during initial hierarchy buildup. MakeLeaf. The key to an efficient hierarchy adjustment is in two aspects: First, during hierarchy construction we temporarily store the number of contained points in each internal node by adding the primitive number of left and right children during bottom up traversal. Second, the data set items are sorted according to their Morton code in memory. An internal node is thus easily turned into a leaf node by simply replacing it with the leftmost leaf node of its subtree. Since we start the bottom up traversal at the tree leaves, each thread needs to remember the leaf-id it came from. The MAKELEAF(...) method then just adjusts pointers, the bounding box and the primitive count, as outlined in Algorithm 4 and visualized on the right. In this example, the depicted leaf with number 5 will contain all stored primitives of the leaves 5 and 6 of the initial tree.”, [pg. 128, Algorithm 3 and Algorithm 4], [pg. 128, col. 2, 4.4.2 Register based priority queue, par. 1, ln. 1 to pg. 129, col. 1, 4.4.3. Radius search, par. 1, ln. 9] “To keep track of the currently found nearest neighbours usually a second (maximum-) heap is used. For small k, a CPU can usually keep the entire heap in L1 cache, which enables extremely low latency and high bandwidth. However, as mentioned above, heaps generally do not show good data parallelism on GPUs. We were inspired by the idea of utilizing registers for sorting net-work primitives on the GPU as proposed by Johnson et al. [JDJ17]. Our approach differs in that we use a simple array in device register memory for our currently found neighbours and keep it sorted using insertion sort. For different kNN sizes we use a compile-time unrolled insertion sort as shown in Algorithm 5. Consequently the compiler can create the code directly and we do not have to provide complex sorting networks for every possible array size and also emit less instructions. Each time, before inserting a new point, we test whether its distance is smaller than the current largest in the heap and insert it only if this is the case. Therefore it can safely be over-written. With this approach we benefit from vector parallelism, extremely low memory latency and easy implementation. To enable the CUDA compiler into keeping a sorted list in register only, everything must be known at compile time and enough device registers must be avail-able. During runtime we then choose the appropriate kernel. Closely related to the kNN search is the radius search, which re-turns all nearest neighbours within a specified search radius. Our approach can be easily modified to use this radius as the abort criterion during traversal. The only change to the backtracking algorithm is, that elements which are smaller than or equal to the current search radius are always inserted. The traversal is aborted if no sub-tree within the search radius is available. This is only limited by the fact, that the size of the kNN heap must be set in advance and remains fixed during the query.”). One of ordinary skill in the art, before the effective filing date of the claimed invention, would recognize Apetrei and Jakob as within the same field of bounding box hierarchy construction, and as analogous to the claimed invention. The motivation to combine is disclosed in Jakob, wherein using a priority queue allows for better parallelism on GPU’s and lower memory latency ([pg. 128, col. 2, 4.4.2 Register based priority queue, par. 1, ln. 1 to pg. 129, col. 1, 4.4.3. Radius search, par. 1, ln. 9]). One ordinary skill in the art, before the effective filing date of the claimed invention, would have combined the method of Apetrei with the priority queueing of Jakob through know means, with no change to their respective function, and the combination would have yielded nothing more than predicable results. Specifically, one of ordinary skill in the art would have combined the method of Apetrei with the priority queueing of Jakob such that the bounding box pairs of Apetrei were pushed onto a priority queue during tree construction and popped during merger analogous to the priority queueing disclosed in Jakob.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the method of Apetrei with the priority queueing of Jakob to obtain the invention as specified in claim 1.
11. Regarding Claim 2, a combination of Apetrei and Jakob teaches the method of claim 1. Apetrei further discloses wherein the reducing comprises updating the binary search tree by: {removing each bounding box of the selected bounding box pair form the binary search tree}; mapping a 2-dimensional location of the new bounding box to a 1-dimensional location ([pg. 2, Figure 1], [pg. 2, col. 1, 3. Binary Radix Tree Construction, par. 1, ln. 1 to par. 3, ln. 7], [pg. 2, col. 1, Algorithm, par. 1, ln. 1 to col. 2, par. 5, ln. 9]); and adding the new bounding box to the binary search tree based on the 1-dimensional location ([pg. 2, Figure 1], [pg. 2, col. 1, 3. Binary Radix Tree Construction, par. 1, ln. 1 to par. 3, ln. 7], [pg. 2, col. 1, Algorithm, par. 1, ln. 1 to col. 2, par. 5, ln. 9]). The examiner specifically notes that the internal nodes effectively map locations of the bounding boxes of the child nodes to a 1-dimensional location that encompasses both the children into a single new bounding box, since they comprise the longest prefix of the child nodes when merging. As such, the 2-dimensional location of the new bounding box is represented by the 1-dimensionl code mapped during the merging of the children nodes, and thus Apetrei discloses mapping a 2-dimensional location of the new bounding box to a 1-dimensionl location. Apetrei does not specifically disclose removing each bounding box of the selected bounding box pair form the binary search tree.
However, Jakob specifically discloses removing each bounding box of the selected bounding box pair form the binary search tree ([pg. 126, col. 2, 4.1. LBVH construction, par. 1, ln. 1 to pg. 127, col. 1, par. 1, ln. 5] “For the initial spatial acceleration structure we use the fast LBVH construction of Apetrei et al. [Ape14], which is based on ordering primitives along a space-filling curve. Compared to previous methods, this bottom-up construction algorithm is able to generate both tree-hierarchy and enclosing bounding boxes in one single and simple kernel launch as shown in Algorithm 2. We first compute a Morton code for each item in the data set and sort all points accordingly using a parallel radix-sort. Subsequently, after creating the leaf nodes, an initial LBVH is built in a single bottom-up traversal by choosing the parent and simultaneously computing the bounding box at each step. The resulting tree is shown in Figure 1. Our implementation of the kernel proposed by Apetrei et al. differs only in that we store explicit parent pointers per node, the sum of all points in the current subtree (used during optimization), and force an explicit synchronization of the global memory write accesses as outlined in line 10 of Algorithm 2. This is required as Nvidia GPUs use a weakly-ordered memory model. The order in which a thread writes data to global (or shared) memory is not necessarily the order in which the data written by another thread is observed. Depending on the graphics card used (memory read/write ordering is different in different architectures), this leads to nondeterministic behaviour and invalid hierarchies since the pointers and keys set by the find-Parent method in line 9 are read directly in the next iteration during bottom up traversal.”, [pg. 127, col. 2, Algorithm 2] “…Pseudocode of our optimization kernel. As each leaf/node can be identified with a global index, we just flag only the deleted ones. This simplifies computing new memory positions for all nodes in the subsequent compaction step...”, [pg. 127, col. 1, 4.2. Tree optimization, par. 1, ln. 1 to pg. 128, col. 1, par. 1, ln. 2] “…Merged nodes, that are no longer needed are flagged accordingly...”). The motivation to combine is disclosed in Jakob, wherein it simplifies memory positions for subsequent compaction ([pg. 126, col. 2, 4.1. LBVH construction, par. 1, ln. 1 to pg. 127, col. 1, par. 1, ln. 5], [pg. 127, col. 2, Algorithm 2]). One ordinary skill in the art, before the effective filing date of the claimed invention, would have combined the method of Apetrei with the priority queueing and removal of unneeded bounding box pairs of Jakob through know means, with no change to their respective function, and the combination would have yielded nothing more than predicable results. Specifically, one of ordinary skill in the art would have combined the method of Apetrei with the priority queueing and removal of unneeded bounding box pairs of Jakob such that the bounding box pairs of Apetrei were pushed onto a priority queue during tree construction and popped during merger analogous to the priority queueing disclosed in Jakob, and further deleted analogous to Jacob when they are no longer needed.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the method of Apetrei with the priority queueing and removal of unneeded bounding box pairs of Jakob to obtain the invention as specified in claim 2.
12. Regarding Claim 3, a combination of Apetrei and Jakob teaches the method of claim 2. Apetrei specifically discloses wherein calculating a distance for each of one or more bounding box pairs that include the new bounding box and a neighbor bounding box as ordered based on the 1-dimensional locations ([pg. 1, col. 2, 2. Background, par. 1, ln. 7 to par. 2, ln. 12], [pg. 2, Figure 1], [pg. 2, col. 1, 3. Binary Radix Tree Construction, par. 1, ln. 1 to par. 3, ln. 7], [pg. 2, col. 1, Algorithm, par. 1, ln. 1 to col. 2, par. 5, ln. 9], [pg. 3, col. 2, Bonding Box Hierarchy, par. 1, ln. 1-14], [pg. 4, col. 1, par. 1, ln. 1-16]); and {pushing an entry} specifying a distance and a bounding box pair {onto the priority queue} for each of the one or more bounding box pairs including the new bounding box ([pg. 1, col. 2, 2. Background, par. 1, ln. 7 to par. 2, ln. 12], [pg. 2, Figure 1], [pg. 2, col. 1, 3. Binary Radix Tree Construction, par. 1, ln. 1 to par. 3, ln. 7], [pg. 2, col. 1, Algorithm, par. 1, ln. 1 to col. 2, par. 5, ln. 9], [pg. 3, col. 2, Bonding Box Hierarchy, par. 1, ln. 1-14], [pg. 4, col. 1, par. 1, ln. 1-16]). The examiner specifically notes that the process used for the leaf nodes as mapped is likewise applied to the internal nodes after merging, and thus Apetrei disclosed analogous operations between a new bounding box and its neighbor bounding boxes ([pg. 2, Figure 1], [pg. 3 Figure 2]). Apetrei does not specifically disclose pushing an entry onto the priority queue.
However, Jakob specifically discloses pushing bounding box pairs as entries onto a priority queue ([pg. 127, Fig. 3], [pg. 127, col. 1, 4.2. Tree optimization, par. 1, ln. 1 to pg. 128, col. 1, par. 1, ln. 2], [pg. 128, Algorithm 3 and Algorithm 4], [pg. 128, col. 2, 4.4.2 Register based priority queue, par. 1, ln. 1 to pg. 129, col. 1, 4.4.3. Radius search, par. 1, ln. 9]). The motivation to combine remains analogous to claim 1. One ordinary skill in the art, before the effective filing date of the claimed invention, would have combined the method of Apetrei with the priority queueing of Jakob through know means, with no change to their respective function, and the combination would have yielded nothing more than predicable results. Specifically, one of ordinary skill in the art would have combined the method of Apetrei with the priority queueing of Jakob such that the new bounding box pairs of Apetrei were pushed onto a priority queue during tree construction and popped during merger analogous to the priority queueing disclosed in Jakob.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to combine the method of Apetrei with the priority queueing of Jakob to obtain the invention as specified in claim 3.
13. Regarding Claim 4, a combination of Apetrei and Jakob teaches the method of claim 3. Apetrei specifically discloses iteratively reducing the number of the plurality of bounding boxes ([pg. 2, Figure 1] see root node 3, [pg. 2, col. 1, 3. Binary Radix Tree Construction, par. 1, ln. 1 to par. 3, ln. 7] see “…Then it uses a bottom-up traversal algorithm for bounding box calculation where each thread starts from a single leaf and advances toward the root and every node calculates its bounding box by looking at the bounding box of the children…To achieve this, we must construct the tree in a bottom-up fashion. What this means is that we start from each key and progressively group them together into larger and larger clusters until the root cluster containing all the keys is formed…”). Specifically, one of ordinary skill in the art, before the effective filing date of the claimed invention, would recognize the keys of Apetrei represent bounding boxes, and thus Apetrei iteratively reduces a number of the plurality of bounding boxes since it is repeated for each leaf and internal node till the root node (e.g. 3 in Figure 1) is obtained. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to combine the method of Apetrei with the priority queueing of Jakob to obtain the invention as specified in claim 4.
14. Regarding Claim 5, a combination of Apetrei and Jakob teaches the method of claim 1. Apetrei further discloses wherein the mapping 2-dimensional locations of the plurality of bounding boxes to 1-dimensional locations is based on a Morton code ([pg. 1, Abstract, par. 1, ln. 1-8], [pg. 1, col. 2, 2. Background, par. 1, ln. 7 to par. 2, ln. 12], [pg. 2, Figure 1], [pg. 4, col. 1, par. 1, ln. 1-16]). Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the method of Apetrei with the priority queueing of Jakob to obtain the invention as specified in claim 5.
15. Regarding Claim 6, a combination of Apetrei and Jakob teaches the method of claim 1. Apetrei discloses prioritizing entries specifying smaller distances over entries specifying larger distances ([pg. 3, col. 1, par. 2, ln. 1-9] “In the figure, the only possible parent for L0 is I0. In the case of L1, we compare d(0) and d(1) and find that d(0) has the smaller value and that means the parent is I0. After finding at which end of the range of keys is the parent, each node passes to their parent the opposite end. So, L0 will pass 0 and L1 will pass 1. Now that we have set the parent child relationship, the algorithm proceeds to process internal node I0 where we know that it covers the keys [0,1].”), but does not specifically disclose a priority queue.
However, Jakob specifically teaches wherein the priority queue further prioritizes entries specifying a smaller distance over entries specifying larger distances ([pg. 128, col. 2, 4.4.2 Register based priority queue, par. 1, ln. 1 to pg. 129, col. 1, 4.4.3. Radius search, par. 1, ln. 9]). The motivation to combine remains analogous to claim 1. One ordinary skill in the art, before the effective filing date of the claimed invention, would have combined the method of Apetrei with the priority queueing of Jakob through know means, with no change to their respective function, and the combination would have yielded nothing more than predicable results. Specifically, one of ordinary skill in the art would have combined the method of Apetrei with the priority queueing of Jakob such that the bounding box pairs of Apetrei were pushed onto a priority queue prioritizing the smallest distance during tree construction and popped during merger analogous to the priority queueing disclosed in Jakob.
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the method of Apetrei with the priority queueing of Jakob to obtain the invention as specified in claim 6.
16. Regarding Claim 7, a combination of Apetrei and Jacob teaches the method of claim 1. Rejections analogous to claim 6 are further applicable to claim 7. Specifically, one of ordinary skill in the art would recognize that a priority queue that prioritizes smaller distances over larger distances as taught by a combination of Apetrei and Jacob would necessarily pop an entry specifying a minimum distance from the priority queue. This is because a priority queue, by definition, prioritizes a property of its entries such that the entry with the highest (or lowest) property value is given the highest priority and will be dequeued and/or popped before elements with a lower property value. Given that a combination of Apetrei and Jacob teaches to prioritize smaller distances over larger distances, which is further substantiated by the nearest neighbor nature of the bounding box hierarchy as taught in Jacob ([pg. 128, col. 2, 4.4.2 Register based priority queue, par. 1, ln. 1 to pg. 129, col. 1, 4.4.3. Radius search, par. 1, ln. 9]), one of ordinary skill in the art, before the effective filling date of the claimed invention, would recognize that the priority of the queue would be places on the minimum distance, and thus when an entry of the queue is popped, it would be the entry specifying a minimum distance from the priority queue. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filing date of the claimed invention, to combine the method of Apetrei with the priority queueing of Jakob to obtain the invention as specified in claim 7.
17. Regarding Claim 9, the claim is analogous to claim 1 with the exception of “An apparatus, comprising: a hardware processor configured to perform operations including”, wherein the remainder of the claim is analogous to claim 1. Apetrei specifically discloses an apparatus comprising a hardware processor configured to perform operations of their method ([pg. 3, col. 2, 5. Results, par. 1, ln. 1-6]). Regarding the remainder of claim 9, rejections analogous to claim 1 are further applicable to claim 9 in view of the analogous claim language. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to combine the apparatus of Apetrei with the priority queue of Jakob to obtain the invention as specified in claim 9.
18. Regarding Claims 10-15, a combination of Apetrei and Jakob teaches the apparatus of claim 9. The claim language of claims 10-15 is analogous to claims 2-7 respectively. Rejections analogous to claims 2-7 are further applicable to claims 10-15 in view of the analogous claim language and the apparatus of Apetrei. Specifically, a combination of Apetrei and Jakob teaches the apparatus of claim 10 with arguments analogous to claim 2, arguments analogous to claims 3-4 are further applicable to claims 11-12 in view of analogous dependency, and the remainder of the claims 13-15 are rejected in view of the combination of Apetrei and Jakob teaching claim 10 with analogous rejections to those provided for claims 5-7. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to combine the apparatus of Apetrei with the priority queue and removal of unneeded bounding box pairs of Jakob to obtain the invention as specified in claims 10-15.
19. Regarding Claim 17, the claim is analogous to claim 1 with the exception of “A computer program product, comprising: one or more computer readable storage mediums, and program instructions collectively stored on the one or more computer readable storage mediums, wherein the program instructions are executable by computer hardware to initiate operations including:”, wherein the remainder of the claim is analogous to claim 1. Apetrei further discloses a computer program product, comprising: one or more computer readable storage mediums, and program instructions collectively stored on the one or more computer readable storage mediums, wherein the program instructions are executable by computer hardware to initiate operations of their method ([pg. 3, col. 2, 5. Results, par. 1, ln. 1-6], [pg. 3, Figure 2] see Pseudocode for program instructions). Specifically, one of ordinary skill in the art, before the effective filling date of the claimed invention, would recognize the GPU and CPU of Apetrei both include storage mediums on which the program and parameters are stored while being performed (e.g., VRAM for GPU, SRAM for CPU cache, etc.). Likewise, the examiner notes Jakob discloses an analogous program and storage mediums ([pg. 126-128, Algorithms 1-4], [pg. 129, col. 2, par. 1, ln. 1-5] “All measurements were performed on an AMD RyzenTM 7 2700XCPU @ 3.7 GHz, 32 GB RAM with a NVIDIA GeForceTM GTX2080TI, running under Linux 5.4.14 with NVIDIA driver version440.44. We implemented and compiled our hierarchy construction and traversal algorithm with CUDA 10.2.”). Regarding the remainder of claim 17, rejections analogous to claim 1 are further applicable to claim 17 in view of the analogous claim language. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to combine the program product and storage medium of Apetrei with the priority queue of Jakob to obtain the invention as specified in claim 17.
20. Regarding Claims 18-20, a combination of Apetrei and Jakob teaches the program product of claim 17. The claim language of claims 18-20 is analogous to claims 2-3 and 5 respectively. Rejections analogous to claims 2-3 and 5 are further applicable to claims 18-20 in view of the analogous claim language and the program product and storage medium of Apetrei. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to combine the program product and storage medium of Apetrei with the priority queue of Jakob to obtain the invention as specified in claim 18-20.
21. Claim 8 and 16 are rejected under 35 U.S.C. 103 as being unpatentable over “Fast and Simple Agglomerative LBVH Construction” to Apetrei, and further in view of “Optimized LBVH-Construction and Hierarchy-Traversal to accelerate kNN queries on Point Clouds using the GPU” to Jakob, and further in view of “Context-Aware Region-Dependent Scale Proposals for Scale-Optimized Object Detection Using Super-Resolution” to Akita et al. (hereinafter Akita).
22. Regarding Claim 8, a combination of Apetrei and Jacob teaches the method of claim 1. Apetrei and Jacob do not specifically teach upscaling the digital image based on a resulting number of bounding boxes remaining subsequent to the reducing the number of the plurality of bounding boxes.
However, Akita specifically teaches upscaling the digital image based on a resulting number of bounding boxes remaining subsequent to the reducing the number of the plurality of bounding boxes ([pg. 4, Figure 3, see x1 x2 and x4 branch], [pg. 4, col. 1, A. Region-Dependent SR-Scale Proposals, par. 1, ln. 1-16] “The RDSP network is required to roughly but robustly detect regions in each of which there might be any object. This region is called a Possible Object Region(POR).In particular, even PORs of tiny objects must also be detected by the RDSP network. Such PORs of tiny objects are upscaled using SR by large scaling factors (e.g., the factor of 4). However, this scheme seems to be a chicken-and-egg problem because the RDSP network must detect PORs of tiny objects to support the following object detection network. Therefore, the goal of the RDSP network is not to precisely detect objects without excess or deficiency but to roughly detect PORs with no false negatives. While the POR is similar to a general region proposal for object detection, RDSP also estimates the appropriate scaling factor of each POR for improving the performance of scale-specific object detection…”, [pg. 6, Figure 6, see different factors (b), (c), and (d) and corresponding bounding boxes of (a)], [pg. 6, col. 1, C. Scale-Proposal Ground-Truth For RDSP Training, par. 1, ln. 1 to col. 2, par. 4, ln. 4] “As described in Sec. III-B, the RDSP network is trained with the ground-truth heatmaps. Although the RDSP networks are required to estimate the regions that are suitable for the corresponding scale factor, it is difficult to learn to satisfy such requirements from end-to-end training with object detection alone. Therefore, to support the training, we create ground-truth heatmaps that satisfy the requirements. For producing the ground-truth data for this training, a standard training dataset for object detection is reprocessed as follows: 1) The bounding boxes of objects for detection are divided into height-dependent groups. In our experiments, the bounding boxes are divided into three groups, namely bounding boxes whose appropriate scaling factors are 1, 2, and 4. More specifically, in our experiments, the groups of scaling factors of 1, 2, and 4 include the following ranges depending on the height of the bounding box (denoted by hb): (1) if hb ≥ 64, factor of 1, (2) if 32 ≤ hb < 64, factor of 2, and (3) if hb < 32, factor of 4. In the training images, the groups of factors 1, 2, and 4 have 7,156, 6,348, and 6,297 bounding boxes, respectively. 2) Each RDSP network produces a heatmap-like image in which higher values are given in pixels where any target object is likely to be observed. The ground-truth image of the heatmap for the factor of S ∈ 1,2,4 contains only the bounding boxes included in factor S’s group, as illustrated in Figure 6. In each ground-truth image, all bounding boxes are filled by 1, while all other pixels are 0. 3) For robust detection, all bounding boxes filled by 1 are blurred by Gaussian. This blurred image is used as the ground truth of the output of the RDSP network for training.”). Specifically, one of ordinary skill in the art, before the effective filling date of the claimed invention, would recognize that Akita teaches applying different super-resolution to size varied objects based on a hierarchy of bounding boxes analogous to those used in Apetrei and Jacob. The motivation to combine would have been obvious to one or ordinary skill in the art, before the effective filling date of the claimed invention, and is disclosed in Akita, in that by incorporating an object hierarchy in tandem with an upscaler you can effectively improve detection performance of objects that would contain smaller bounding boxes and can further improve object detection ([pg. 8, col. 1, par. 1, ln. 9-15] “The quantitative results of various detectors on CityScapes are shown in Table 1. Table 1 shows that the use of SR improves the detection performance of small objects, but sometimes has negative impacts on the performance of medium or large object detections. With our proposed RDSP networks, the detection performances are further improved in most cases.”, [pg. 11, col. 2, V. Concluding Remarks, par. 1, ln. 1-5] “This paper proposed a method for estimating object-scale proposals for scale-optimized object detection using SR. With images that are rescaled by the appropriate SR scaling factor, an object detector can work better than in the original size image...”). One ordinary skill in the art, before the effective filing date of the claimed invention, would have combined the method of Apetrei with the priority queueing of Jakob, and further combined the method of the combination of Apetrei and Jakob with the upscaler of Akita through know means, with no change to their respective function, and the combination would have yielded nothing more than predicable results. Specifically, in combining the combination of the method of Apetrei and Jakob with the upscaler of Akita, one of ordinary skill in the art, before the effective filling date of the claimed invention, would have incorporated an analogous upscaler to Akita to perform upscaling on the hierarchal bounding boxes (e.g., by training a scaler on each level of the tree of the bounding box hierarchy).
Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to combine the method of Apetrei with the priority queueing of Jakob and the upscaler of Akita to obtain the invention as specified in claim 8.
22. Regarding Claim 16, a combination of Apetrei and Jakob teaches the apparatus of claim 10. Rejections analogous to claim 8 are further applicable to claim 10 in view of the analogous claim language. Therefore, it would have been obvious to one of ordinary skill in the art, before the effective filling date of the claimed invention, to combine the method of Apetrei with the priority queueing and removal of unneeded bounding box pairs of Jakob and the upscaler of Akita to obtain the invention as specified in claim 16.
Conclusion
23. The prior art made of record and not relied upon is considered pertinent to applicant’s disclosure. See PTO-892.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to PAULO ANDRES GARCIA whose telephone number is (703)756-5493. The examiner can normally be reached Mon-Fri, 8-4:30PM ET.
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, Chan Park can be reached on (571)272-7409. 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.
/PAULO ANDRES GARCIA/Examiner, Art Unit 2669 /CHAN S PARK/Supervisory Patent Examiner, Art Unit 2669
Prosecution Insights