The subject matter of the present disclosure relates to searching a large repository of 3D models (e.g., objects) to find models similar to a query model. More specification, the subject matter of the present disclosure relates to semi-structuring of the 3D model data and implementing of approximate similarity algorithms in the search. Such a search may detect potential intellectual property infringements, both physical and virtual.
Systems and methods described here provide comparative analysis results between 3D objects that may exhibit superficial and/or abstract similarities. The objective is to efficiently sort through large datasets (e.g., a library of 3D models) to detect not just duplicates to a query object but similar objects that may have been derived from the query object, and to provide quantitative descriptors of object similarities. Implementations include a novel method of consistently structuring 3D model data that represents a given model as a feature tree with varying levels of ‘abstraction’ in order to avoid skewed comparison results due to superficial model modifications. Because tree comparison algorithms are computationally expensive, this full structuring of 3D model data can be represented as a semi-structured histogram or signature accompanied metadata that relates the data in each bin to its level in the feature tree hierarchy in order to deliver quicker search and comparison results. These results can be achieved with a high degree of efficiency from very large datasets (such as an online marketplace or repository for CAD files) by using an approximate nearest or k-nearest neighbor algorithm (such as Locality-Sensitive Hashing) and an approximate Earth Mover’s Distance algorithm (e.g., Signature EMD or Wavelet EMD). Implementations draw high-level model similarity and low-level feature similarity conclusions with minimal computational expense (linear time runtime) and with any desired level of probability. Such conclusions, in combination with feature tree metadata, provide the necessary tools to perform extensive and accurate follow-up analysis on whether intellectual property infringement has occurred in one or more 3D objects.
Creative Commons License
This work is licensed under a Creative Commons Attribution 4.0 License.
Scott, Wallace P., "3D Object Search System", Technical Disclosure Commons, (September 02, 2016)