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 .
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claim(s) 1-12, 14-17, and 20 is/are rejected under 35 U.S.C. 103 as being unpatentable over Zhao et al. (U.S. PGPUB 20190370989) in view of Halen et al. (U.S. PGPUB 20210343089).
With respect to claim 1, Zhao et al. one or more processors (paragraph 86, processor 520 configured to execute the instructions stored in the memory 510), comprising: circuitry (paragraph 86, The apparatus 500 of FIG. 5 includes a memory 510 configured to store instructions and a processor 520 configured to execute the instructions stored in the memory 510, such hardware implies circuitry) to: generate a data structure comprising one or more mappings of one or more voxel coordinates to points of one or more point clouds (paragraph 45, paragraph 48, paragraph 51, step 242 may include searching for a storage space of the first voxel in the target storage space according to the first voxel and pre-stored mapping relationship information, where the mapping relationship information can be used for indicating correspondences between stored voxels and storage spaces of the stored voxels); and
generate one or more voxel representations of the one or more point clouds based, at least in part, on use of the data structure to identify features of the corresponding points of the one or more point clouds (paragraph 20, the embodiments of the present disclosure provide a 3D point cloud reconstruction method based on voxels to generate a dense 3D point cloud, paragraph 29, voxels may be used as points in a 3D point cloud, and a high accuracy dense 3D point cloud may be reconstructed). However, Zhao et al. do not expressly disclose the data structure comprises one or more mappings of one or more keys corresponding to one or more voxel offsets calculated from point locations of one or more point clouds to one or more values indicating one or more memory locations storing voxel identifiers corresponding to points of the one or more point clouds.
Halen et al., who also deal with 3D data, disclose a method for generating a data structure comprising one or more mappings of one or more keys corresponding to one or more voxel offsets calculated from point locations of one or more point clouds (paragraph 85, for each entity to be inserted into the acceleration structure, a processor determines a position of the entity in the 3D scene. In a 3D space, the position is parameterized by x-, y-, and z-coordinate components relative to a location of a camera [i.e., a point], paragraph 88, Given that the entity falls within the central grid structure, a first offset value in memory is identified corresponding to the central grid structure. Then, once the 3D voxel grid coordinate within the central grid structure is determined at step 1206, a second offset value is identified corresponding to the voxel within the central grid structure corresponding to the determined 3D voxel grid coordinate within the central grid structure) to one or more values indicating one or more memory locations storing voxel identifiers corresponding to points of the one or more point clouds (paragraph 71, each of the separate memory regions 701-707 is associated with a first offset value 701A-707A, respectively, that provides a memory offset (e.g., a pointer) to the given memory region, paragraph 72, To access a particular location within a given memory region (e.g., within memory region 701), the first offset value for that region is first identified (e.g., first offset value 701A for memory region 701). Then, a second offset value identifies a particular location within the given memory region (e.g., for region 701, second offset value 701B)).
Zhao et al. and Halen et al. are in the same field of endeavor, namely computer graphics.
Before the effective filing date of the claimed invention, it would have been obvious to apply the method wherein the data structure comprises one or more mappings of one or more keys corresponding to one or more voxel offsets calculated from point locations of one or more point clouds to one or more values indicating one or more memory locations storing voxel identifiers corresponding to points of the one or more point clouds, as taught by Halen et al., to the Zhao et al. system, because the location in memory for the look-up can be deterministically identified based on the position of the entity. There is no iterative or recursive process needed to identify the memory location (paragraph 99 of Halen et al.).
With respect to claim 2, Zhao et al. as modified by Halen et al. disclose the one or more processors of claim 1, wherein the circuitry is to generate the data structure to comprise one or more hash tables (Zhao et al.: paragraph 59, The hash table in the embodiments of the present disclosure may be designed in order to quickly and efficiently find a voxel block in an array). Halen et al. disclose storing the one or more voxel offsets as keys and one or more values as corresponding values, wherein the one or more values comprise one or more voxel index values (paragraph 93, the processor causes data associated with the position of the entity to be inserted into memory based on the 3D voxel grid coordinate (i.e., identified at either step 1206 or 1212). As described, a first offset value identifies the memory region of the corresponding grid structure (i.e., either the central grid structure or one of the six additional grid structures). Then, a second offset value identifies a particular voxel within the corresponding grid structure). It would have been obvious to store the data in one or more hash tables because hash tables are well known in the art for lookup and retrieval of data values.
With respect to claim 3, Zhao et al. as modified by Halen et al. disclose the one or more processors of claim 1, wherein the circuitry is to generate the one or more data structures using an amount of memory based, at least in part, on a number of point locations in the one or more point clouds (Zhao et al.: paragraph 62, The target storage spaces may be located in a memory of a graphics processing unit (GPU), or may be located in a memory of a central processing unit (CPU), or may even be located in an external storage device, paragraph 66, in a 3D point cloud map reconstruction, the embodiments of the present disclosure may include using the CPU memory to store a reconstructed global map, using the GPU memory to store a local map).
With respect to claim 4, Zhao et al. as modified by Halen et al. disclose the one or more processors of claim 1, wherein the circuitry is to use the data structure to access one or more data values, and to generate one or more feature values of one or more voxels of the one or more voxel representations based, at least in part, on the one or more data values (Zhao et al.: paragraph 79, the hash table may record the correspondence between the position information of the stored voxel block and the storage space of the stored voxel block. A voxel block may include a plurality of spatially adjacent voxels, and position information of the stored voxel block may be used to indicate a spatial position of the stored voxel block in a 3D scene).
With respect to claim 5, Zhao et al. as modified by Halen et al. disclose the one or more processors of claim 1, wherein the circuitry is to store one or more data values indicative of features associated with the points within the one or more memory locations to be accessed based, at least in part, on data stored in the data structure (Zhao et al.: paragraph 24, The memory 190 may store all or portions of the input feature data associated with each 3D point in the 3D pointcloud data set 110. The compute engine may store in memory 190 the intermediate results 194 from processing the pointcloud data (e.g. on a tile or level basis), which may be used in subsequent data fetches for other levels, tiles, etc.).
With respect to claim 6, Zhao et al. as modified by Halen et al. disclose the one or more processors of claim 1, wherein the circuitry is to iterate over the one or more keys to generate, using the data structure, one or more feature values of one or more voxels of the one or more voxel representations (Halen et al.: paragraph 95, the method of FIG. 12 can be repeated for other entities. In one embodiment, all entities in a scene are processed to insert them into the acceleration structure). It would have been obvious to iterate over the one or more keys to account for rendering the entire scene.
With respect to claim 7, Zhao et al. as modified by Halen et al. disclose the one or more processors of claim 1, wherein the circuitry is to input one or more indications of the one or voxel offsets into a hash function (Zhao et al.: paragraph 56, The above-described searching for the storage space of the first voxel in the target storage space through the hash algorithm, according to the first voxel and the hash table, may include determining position information of a target voxel block that the first voxel belongs to; searching for a storage space of the target voxel block through the hash algorithm, according to the position information of the target voxel block and the hash table; and according to a position of the first voxel in the target voxel block, searching for the storage space of the first voxel in the storage space of the target voxel block) to output one or more indications of one or more memory locations storing voxel identifiers corresponding to one or more voxels of the one or more voxel representations (Halen et al.: paragraph 75, For lookups, once a 3D position of an entity is determined (e.g., relative to a position of the camera), the first offset value and the second offset value can be determined directly from the 3D position to identify where in memory to look for the data corresponding to that entity). It would have been obvious to input data using a hash function because hash functions are well known in the art for lookup and retrieval of data values.
With respect to claim 8, Zhao et al. as modified by Halen et al. disclose a system (Zhao et al.: paragraph 86, FIG. 5 is a schematic structural diagram of an apparatus for 3D point cloud reconstruction), comprising: one or more processors (Zhao et al.: paragraph 86, The apparatus 500 of FIG. 5 includes a memory 510 configured to store instructions and a processor 520) as in claim 1; see rationale for rejection of claim 1.
With respect to claim 9, Zhao et al. as modified by Halen et al. disclose the system of claim 8, wherein the one or more processors are to generate the data structure to comprise one or more hash tables based, at least in part, on one or more arrays of the one or more voxel offsets and one or more arrays of the one or more values (Zhao et al.: paragraph 59, The hash table in the embodiments of the present disclosure may be designed in order to quickly and efficiently find a voxel block in an array. A hash table entry can contain a position of the voxel block, a pointer pointing to an array that stores the voxel block, an offset, or another member variable). Halen et al. disclose generating the data structure comprising voxel offsets and the one or more values (paragraph 88, Given that the entity falls within the central grid structure, a first offset value in memory is identified corresponding to the central grid structure. Then, once the 3D voxel grid coordinate within the central grid structure is determined at step 1206, a second offset value is identified corresponding to the voxel within the central grid structure corresponding to the determined 3D voxel grid coordinate within the central grid structure, paragraph 72, To access a particular location within a given memory region (e.g., within memory region 701), the first offset value for that region is first identified (e.g., first offset value 701A for memory region 701). Then, a second offset value identifies a particular location within the given memory region (e.g., for region 701, second offset value 701B)).
With respect to claim 10, Zhao et al. as modified by Halen et al. disclose the system of claim 8, wherein the one or more processors are to generate the data structure by allocating, in one or more storage devices, an amount of memory that is at least twice a number of points in the one or more point clouds to store each voxel offset and the one or more values (Zhao et al.: paragraph 60, the hash table may record the above-described mapping relationship information using the following data structure: where pos[3] can represent world coordinates (x, y, z) of the voxel block in the 3D space, pointer can point to a starting address of an array storing the voxel block, offset can be used to indicate an offset between a starting address of a storage position of the voxel block and the starting address of the array storing the voxel block). The data structure comprises twice the data (point and offset) to a voxel location. Halen et al. disclose generating the data structure comprising voxel offsets (paragraph 88, Given that the entity falls within the central grid structure, a first offset value in memory is identified corresponding to the central grid structure. Then, once the 3D voxel grid coordinate within the central grid structure is determined at step 1206, a second offset value is identified corresponding to the voxel within the central grid structure corresponding to the determined 3D voxel grid coordinate within the central grid structure).
With respect to claim 11, Zhao et al. as modified by Halen et al. disclose the system of claim 8, wherein the one or more processors are to generate the data structure to comprise one or more tables to index one or more voxels of the one or more voxel representations as a function of the one or more voxel offsets (Zhao et al.: paragraph 56, The above-described searching for the storage space of the first voxel in the target storage space through the hash algorithm, according to the first voxel and the hash table, may include determining position information of a target voxel block that the first voxel belongs to; searching for a storage space of the target voxel block through the hash algorithm, according to the position information of the target voxel block and the hash table; and according to a position of the first voxel in the target voxel block, searching for the storage space of the first voxel in the storage space of the target voxel block). The hash algorithm corresponds to a function. Halen et al. disclose generating the data structure comprising voxel offsets (paragraph 88, Given that the entity falls within the central grid structure, a first offset value in memory is identified corresponding to the central grid structure. Then, once the 3D voxel grid coordinate within the central grid structure is determined at step 1206, a second offset value is identified corresponding to the voxel within the central grid structure corresponding to the determined 3D voxel grid coordinate within the central grid structure).
With respect to claim 12, Zhao et al. as modified by Halen et al. disclose the system of claim 8, wherein the one or more processors are to access one or more memory locations indicated by the one or more values to identify one or more voxels of the one or more voxel representations (Halen et al.: paragraph 75, For lookups, once a 3D position of an entity is determined (e.g., relative to a position of the camera), the first offset value and the second offset value can be determined directly from the 3D position to identify where in memory to look for the data corresponding to that entity).
With respect to claim 14, Zhao et al. as modified by Halen et al. disclose the system of claim 8, wherein the one or more processors are to input one or more indications of the one or more voxel offsets into a hash function (Zhao et al.: paragraph 56, The above-described searching for the storage space of the first voxel in the target storage space through the hash algorithm, according to the first voxel and the hash table, may include determining position information of a target voxel block that the first voxel belongs to; searching for a storage space of the target voxel block through the hash algorithm, according to the position information of the target voxel block and the hash table; and according to a position of the first voxel in the target voxel block, searching for the storage space of the first voxel in the storage space of the target voxel block) to output the one or more values corresponding to individual voxels of a voxel grid used to represent the point cloud (Halen et al.: paragraph 75, For lookups, once a 3D position of an entity is determined (e.g., relative to a position of the camera), the first offset value and the second offset value can be determined directly from the 3D position to identify where in memory to look for the data corresponding to that entity). It would have been obvious to input data using a hash function because hash functions are well known in the art for lookup and retrieval of data values.
With respect to claim 15, Zhao et al. as modified by Halen et al. disclose a method as executed by the system of claim 1; see rationale for rejection of claim 1.
With respect to claim 16, Zhao et al. as modified by Halen et al. disclose the method of claim 15, further comprising generating the data structure to comprise one or more hash tables (Zhao et al.: paragraph 59, The hash table in the embodiments of the present disclosure may be designed in order to quickly and efficiently find a voxel block in an array). Halen et al. disclose storing the one or more voxel offsets as keys to indicate one or more voxels of the one or more voxel representations to be generated (paragraph 93, the processor causes data associated with the position of the entity to be inserted into memory based on the 3D voxel grid coordinate (i.e., identified at either step 1206 or 1212). As described, a first offset value identifies the memory region of the corresponding grid structure (i.e., either the central grid structure or one of the six additional grid structures). Then, a second offset value identifies a particular voxel within the corresponding grid structure). It would have been obvious to store the data in one or more hash tables because hash tables are well known in the art for lookup and retrieval of data values.
With respect to claim 17, Zhao et al. as modified by Halen et al. disclose the method of claim 15, further comprising generating the data structure to use an amount of memory based, at least in part, on a number of points in the one or more point clouds (Zhao et al.: paragraph 62, The target storage spaces may be located in a memory of a graphics processing unit (GPU), or may be located in a memory of a central processing unit (CPU), or may even be located in an external storage device, paragraph 66, in a 3D point cloud map reconstruction, the embodiments of the present disclosure may include using the CPU memory to store a reconstructed global map, using the GPU memory to store a local map).
With respect to claim 20, Zhao et al. as modified by Halen et al. disclose the method of claim 15, further comprising using the data structure to access one or more data values, and to generate one or more voxels based, at least in part, on the one or more data values (Zhao et al.: paragraph 79, the hash table may record the correspondence between the position information of the stored voxel block and the storage space of the stored voxel block. A voxel block may include a plurality of spatially adjacent voxels, and position information of the stored voxel block may be used to indicate a spatial position of the stored voxel block in a 3D scene).
Claim(s) 13 and 19 is/are rejected under 35 U.S.C. 103 as being unpatentable over Zhao et al. (U.S. PGPUB 20190370989) in view of Halen et al. (U.S. PGPUB 20210343089) and further in view of Oh et al. (U.S. PGPUB 20220159312).
With respect to claim 13, Zhao et al. as modified by Halen et al. disclose the system of claim 8, wherein the one or more processors are to iterate over the one or more keys to: identify, using the data structure, a number of corresponding points mapped to a voxel corresponding to a voxel offset (Halen et al.: paragraph 88, Given that the entity falls within the central grid structure, a first offset value in memory is identified corresponding to the central grid structure. Then, once the 3D voxel grid coordinate within the central grid structure is determined at step 1206, a second offset value is identified corresponding to the voxel within the central grid structure corresponding to the determined 3D voxel grid coordinate within the central grid structure). However, Zhao et al. as modified by Halen et al. do not expressly disclose generating, using the identified number of corresponding points, one or more mean feature values of a voxel of the one or more voxel representations, the voxel corresponding to the voxel offset.
Oh et al., who also deal with 3D data, disclose a method for generating, using the identified number of corresponding points, one or more mean feature values of a voxel of the one or more voxel representations, the voxel corresponding to the voxel offset. (paragraph 299, the attribute transformation unit 40007 according to the embodiments performs attribute transformation related thereto. In one embodiment, the attribute transformation unit 40007 may adjust the attribute value of the voxel to the average value of the color or reflectance of points included in the voxel or the average value of the color or reflectance of neighboring points within a specific radius from the position value of the center point of the voxel).
Zhao et al., Halen et al., and Oh et al. are in the same field of endeavor, namely computer graphics.
Before the effective filing date of the claimed invention, it would have been obvious to apply the method of generating, using the identified number of corresponding points, one or more mean feature values of a voxel of the one or more voxel representations, the voxel corresponding to the voxel offset, as taught by Oh et al., to the Zhao et al. as modified by Halen et al. system, because redundant information between the pieces of attribute information may be reduced (paragraph 305 of Oh et al.).
With respect to claim 19, Zhao et al. as modified by Halen et al. and Oh et al. disclose the method of claim 15, further comprising iterating over the one or more voxel offsets to generate, using the data structure, one or more sum feature values of one or more voxels of the one or more voxel representations (Oh et al.: paragraph 362, the geometry reconstruction unit 11003 directly invokes and adds the position information value of the point). It would have been obvious to perform iterating over the one or more voxel offsets to generate, using the data structure, one or more sum feature values of one or more voxels of the one or more voxel representations because this would implement positions decoded and output by the geometry decoder and point cloud content including attribute information decoded and output by the attribute decoder are output to the renderer 10007 paragraph 376 of Oh et al.).
Claim(s) 18 is/are rejected under 35 U.S.C. 103 as being unpatentable over Zhao et al. (U.S. PGPUB 20190370989) in view of Halen et al. (U.S. PGPUB 20210343089) and further in view of O’Connell et al. (U.S. PGPUB 20130222382).
With respect to claim 18, Zhao et al. as modified by Halen et al. disclose the method of claim 15. However, Zhao et al. as modified by Halen et al. do not expressly disclose accessing one or more of the voxel identifiers corresponding to the one or more voxel offsets in parallel using the data structure.
O’Connell et al., who also deal with 3D data, disclose a method for accessing one or more of the voxel identifiers corresponding to the one or more voxel offsets in parallel using the data structure (paragraph 38, Nodes 225, 230, . . . , and 235 are configured to each access, in parallel, the voxel data from voxel data memory 220).
Zhao et al., Halen et al., and O’Connell et al. are in the same field of endeavor, namely computer graphics.
Before the effective filing date of the claimed invention, it would have been obvious to apply the method of accessing one or more of the voxel identifiers corresponding to the one or more voxel offsets in parallel using the data structure, as taught by O’Connell et al., to the Zhao et al. as modified by Halen et al. system for accessing one or more voxel identifiers, because individual storage units for each node may not be required as each node may access the voxel data in parallel with the other nodes from shared voxel data memory 220 (paragraph 39 of O’Connell et al.).
Response to Arguments
Applicant’s arguments with respect to claim(s) 1, 8, and 15 have been considered but are moot in view of the new ground(s) of rejection.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
U.S. PGPUB 20240193788 to Tang et al. for a method of accessing a central coordinate of a 3D voxel grid cell.
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to ANDREW GUS YANG whose telephone number is (571)272-5514. The examiner can normally be reached M-F 9 AM - 5:30 PM.
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, Kent Chang can be reached at (571)272-7667. 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.
/ANDREW G YANG/Primary Examiner, Art Unit 2614
10/3/26
