Abstract:
A method is provided for the automated identification of real world objects. The invention, implementable via various means such as a processing system, method, or data structure in a recording medium such as memory or as a self-contained electronic circuit, has wide ranging applicability to numerous fields such as in a user interface for gaming systems, like Kinect, or immersive environments such as remote surgical operations, and other medical diagnostic applications. Similarly, our method can be utilized in artificial intelligence application for automated robotic identification of targets, such as drone assisted search and rescue missions, and the enablement of patent protection against unlawful replication on 3D printers. The method of the invention includes the steps of creating a 3D representation for the real world object to be identified, segmenting the newly created 3D representation according to potential identities, alignment of minimal, unique representations for said potential identities to the corresponding segments of the newly created 3D representation, and then the analysis of said alignments to determine which potential identity correctly identifies the real world object to be identified.

Description:
REFERENCES CITED 
     U.S. Patent Documents  
       [0001]      
         [0000]    
       
         
               
               
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 8,325,984 
                 A 
                 December 2012 
                 Lee et al. 
               
               
                   
                 7,974,443 
                 A 
                 July 2011 
                 Kipman et al. 
               
               
                   
                 8,295,546 
                 A 
                 October 2012 
                 Craig et al. 
               
               
                   
                 8,213,680 
                 A 
                 July 2012 
                 Fitzgibbon et al. 
               
               
                   
                 8,267,781 
                 A 
                 September 2012 
                 Geiss et al. 
               
               
                   
                   
               
             
          
         
       
     
       Other Publications 
       [0002]    I. Baran and J. Popovic, “Automatic Rigging and Animation of 3D Characters,” ACM Transactions on Graphics, vol. 26, July 2007. 
         [0003]    S. Schaefer and C. Yuksel, “Example-based skeleton extraction,” in Symposium on Geometry Processing, 2007. 
         [0004]    N. Hasler, T. Thormahlen, B. Rosenhahn and H. -P. Seidel, “Learning skeletons for shape and pose,” in ACM Symposium on interactive 3D graphics, 2010. 
         [0005]    W. Chang and M. Zwicker, “Global registration of dynamic range scans for articulated model reconstruction,” ACM Transactions on Graphics, vol. 30, pp. 15-26, 2011. 
         [0006]    N. D. Cornea, D. Silver and P. Min, “Curve-Skeleton Properties, Applicaitons, and Algorithms,” IEEE Transactions on Visualization and Computer Graphics, vol. 13, pp. 530-548, 2007. 
       AUTOMATED OBJECT IDENTIFIER 
       [0007]    1. Technical Field 
         [0008]    This invention relates to the automatic identification and classification of real world objects via an analysis of virtual representation of said objects; where said representation is composed of any electronic, optical, or other medium for representing, storing, transmitting, or analyzing information about the original real world object. A component of this invention relates to the automatic rigging of 3D computer graphics. 
         [0009]    2. Background of the Invention 
         [0010]    There has been a great deal of research into methods for the automatic identification of digital representations. These methods are as diverse as the digital representations that are to be identified. For example, text recognition software utilizes methods involving the computation of discrete local symmetries; Microsoft&#39;s Kinect utilizes probabilistic tracking in metric spaces; and there is an entire plethora of skeletonization methodologies that utilize everything from voxelization of 3D spaces to Reb graphs. 
         [0011]    The method utilized by Microsoft&#39;s Kinect device is by far the most widely used and impressive to date. However, Microsoft&#39;s probabilistic tracking method requires a large amount of training data in order to produce a predictive model, and each new predictive model requires substantial, even international, efforts to construct. This will not work for many industries that wish to dynamically and automatically identify real world objects because they require a method that can completely recognize an object after one scan, and then be able to match said identity to any other instances of the object. Other industries that can benefit from our technology are not even interested in recognizing objects, but are instead interested in being able to completely analyze the object based off of a single representation, such as a CAD design, and then be able to draw conclusions from said analysis. 
         [0012]    Voxelization, Reb graphs, and energy gradient methods do retain this ability to perform analysis or identification based off of a single frame, or data set; however, they are known to be highly error prone and pose specific. This means that it is difficult to ensure that an object will be accurately and uniquely identified from instance to instance. Similarly, if an object is identified in one instance, and then repositioned, then the voxelization, Reb graph, and energy gradient methods may not recognize the re-positioned real world object as the same object from the initial data acquisition. 
       SUMMARY OF INVENTION 
       [0013]    This Summary is not intended to limit the scope of the claimed subject matter or identify key or essential features of the claimed subject matter. This Summary is only provided, in an abridged form, a selection of concepts that are further described in the Detailed Description. 
         [0014]    With the previous paragraph in mind, this disclosure details a novel method for the identification of real world objects via the identification of a minimal representation for the real world object. The identification of said minimal representation is frequently, and generically, referred to as skeletonization; however, here we emphasize the goal of obtaining a minimal representation for the real world object. This is in contrast to many previous definitions of a skeletal representation that often involve the identification of excess information that can lead to the obfuscation of the identity of the real world object to be identified. As a side product of this method, we have also devised a novel automatic rigging method. This automatic rigging method resides at the core of our automatic object identification method. 
         [0015]    The scope of this claim is not in any way intended to be limited to the identification of real world objects and includes, but is not limited to, the identification of virtual objects. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0016]    Similarly numbered elements in the attached drawings correspond to one another. 
           [0017]      FIG. 1  depicts an example environment for an object identification system 
           [0018]      FIG. 2   a  depicts example components for a minimal representation. 
           [0019]      FIG. 2   b  depicts two example minimal representations, as indicated by the projection of object data onto the surfaces of said minimal representations. 
           [0020]      FIG. 3  depicts more examples of computed minimal representations. 
           [0021]      FIG. 4  compares a graphical skeleton with a minimal representation. 
           [0022]      FIG. 5  depicts a high level view of the process of automatically identifying an object. 
           [0023]      FIG. 6  depicts a method for deriving a minimal representation form object data. 
           [0024]      FIG. 7  depicts a method for reducing an object skeleton 
           [0025]      FIG. 8  depicts a method for the verification of a computed minimal representation. 
           [0026]      FIG. 9  depicts an algorithm for the conversion of a cyclic graph into an acyclic graph. 
           [0027]      FIG. 10  presents more detail about the automatic rigging process that is performed during the automatic object identification (step  44  in  FIG. 5 ). 
           [0028]      FIG. 11  presents a more detailed image of the method utilized for automatic object identification (step  44  in  FIG. 5 ). 
           [0029]      FIG. 12  presents a detailed image of a concurrent method for the automatic identification of objects (step  44  in  FIG. 5 ). 
       
    
    
     DETAILED DESCRIPTION 
       [0030]    The presented disclosure is directed at object identification and analysis. In particular, the use of an acquisition device such as a computed axial tomography (CT scan), radar, sonar, depth sensors, atomic force microscopy, or 3D scanning devices to acquire data representative of a real world object, where said representative data can then be analyzed to determine the identity of the said real world object. Similarly, the presented disclosure includes the use of the disclosed method to identify unknown virtual objects, such as a virtual cup, chair, or avatar, which represent potential real world objects, and to identify key components or sub-components of said virtual objects. 
         [0031]      FIG. 1  shows a non-limiting example of an object identification system for real world objects. In particular,  FIG. 1  shows a recording device  12  that may or may not be a camera, depth sensor, radar or sonar based system, or any other device utilized to detect, quantify, and or measure real world objects, a square on top of a peg  14  as a generic example of an object that may exist in the real world, and a computational device  10 , such as but not limited to a computer, that implements that object identification method. For identifying virtual objects and virtual object components and/or attributes the virtual object could be present on the computational device that is implementing the object identification method, or a replica of said virtual object could be sent to the computational device implementing the automated object identification method. An object identification system, such as the one shown in  FIG. 1  may be utilized to identify one or more objects, such as the square on top of a peg  10  in  FIG. 1 , at a time. 
         [0032]      FIG. 2   a  shows a non-limiting set of examples for components of a minimal representation. The first example  16  is a simple line segment bound by two points. The second example  18  is an unrestricted plane, the third example  20  is a spheroid, and the fourth example  22  is a rectangular box. 
         [0033]      FIG. 2   b  shows two examples of minimal representations defined over four components.  24  shows a point cloud projection onto a minimal representation defined over line segments.  26  shows an equivalent point cloud projection of the same point cloud onto spindle shaped components similar to that utilized during bone representation in computer graphics. See  FIG. 7  for further details. The yellow lines in  24  and  26  for  FIG. 2   b  are the boundaries of the Voronoi diagram induced by the minimal representations partitioning of real space. 
         [0034]      FIG. 3  shows examples of minimal representations for a sphere  28 , a cylinder  30 , and a human  32 : where said minimal representation is the minimal amount of information required to identify an object. The concept of a minimal representation is similar to the computer graphics concept of a skeleton; however, a minimal representation seeks to only include the minimal amount of information necessary to accurately and faithfully represent the object in question within a scale S :=[l 1 , l 2 ] of representation: where said scale S is only able to detect attributes larger than l 1  and smaller than l 2 . For more details on the difference between a skeleton and a minimal representation see  FIG. 4 . In particular,  28  shows a sphere that could be, but is not limited to, a ball or a bearing;  30  depicts a cylinder that could be, but not limited to, a can of food or a child&#39;s building block; and  32  depicts a point cloud representation of a human male; where the minimal representation in  32  includes a range [l 1 , l 2 ] that is unable to detect lower scale attributes such as fingers, toes, or facial features, but is large enough to detect arms, legs, torso, and the head. The scale S is in no way to imply a limit on the ability of the presented method to detect attributes or features of objects; virtual or real. On the contrary, if information about attributes and features at a lower/higher scale then all the user has to do is specify a new scale S′ :=[l 1 ′, l 2 ′] such that S′ is above, bellow, or overlaps S; depending on the newly desired scale. Similarly, said scale S is not intended to imply a required limit on the amount of information that is detectible. If a limit on the amount of information that is detectible is not desired then S can be defined as S=[0∞]. 
         [0035]    For the sphere in  28 , this minimal representation is a single point at the center of the sphere. For the cylinder in  30 , this minimal representation is the line that represents the principle component that determines the height of the cylinder. For the human point cloud in  32 , the minimal representation is a 15-node tree. 
         [0036]      FIG. 4  depicts a non-limiting example of the difference between a skeleton  34  and a minimal representation  36 . Both  34  and  36  depict a representation of a human form.  34  depicts a skeleton of a human form.  36  depicts a minimal representation for a human form. 
         [0037]    The concept of a minimal representation is related to the concept of a skeletal model or skeleton; where a skeletal model is a virtual specification of joints and other points of interest for a virtual model; and where said joints generally define the relative origin for a sub-graph, or component, of the overall virtual model. Different models may or may not require different skeletons in that not every model is defined over the same number or variety of sub-graphs or components. 
         [0038]    There are two major differences between a skeleton  34  and a minimal representation  36 . The first is that a minimal representation contains a scale that defines the lower bound and the upper bound for the size or significance of the attributes that are allowed to participate in or influence the minimal representation. The scale S is a dimensional specification, such as but not limited to length, height, and width. As a non-limiting example,  FIG. 3  depicts a cylinder  30  of length and width 5 units and of height 10 units. As such, the minimal representation for the object in  30  must utilize a scale S=[5, 10], or any scale that incorporates dimensional lengths in the range 5 to 10 units. Similarly, the feet and hands are missing in  36  while not in  34  because said feet and hands are below the scale that is detected for the minimal representation in  36 . 
         [0039]    The second difference is that a skeleton typically includes any information that was detectable to the algorithm utilized to generate said skeleton whereas a minimal representation only includes the minimal amount of information necessary to identify an object. In  34  we can see that a lot more information, in the form of joint information, is utilized to represent the same shape as the minimal representation in  36 . 
         [0040]      FIG. 5  depicts a high level view of a non-limiting example of a method for automatically determining the identity of an object, real or virtual. Step  40  involves the acquisition of a known library of potential minimal representations or templates. See  FIG. 6  for more details. Such a library can be obtained via methods such as, but not limited to, automatically via the use of various known skeletonization methodologies, followed by appropriate minimization and generalization methodologies, or via explicit definitions constructed by exports. Step  42  involves the acquisition of object data, such as but not limited to that depicted in  32 . This object data can be, but is not limited to, data representative of virtual objects or real world objects that have been recorded or scanned into a computational or processing device. This object data is generally, but not necessarily, a 3D representation of some virtual or real object. Step  44  involves the computation of a minimal representation from the object data. See  FIG. 10  for more details. 
         [0041]      FIG. 6  shows a non-limiting example of a method for deriving a minimal representation. The purpose for the derivation of a minimal representation in  FIG. 6  is for, but not limited to, the automatic construction of an object library defined over a set of minimal representations. In general, the method presented in  FIG. 6  is slower than the method presented in  FIG. 10 , and therefore less desirable for circumstances in which the method in  FIG. 10  is applicable. 
         [0042]    Step  50  involves the acquisition of the data or information that is utilized to convey the characteristics of the object. This data is generally in the form of, but not limited to the form of, 3D information about the virtual or real object to be utilized for the computation of a minimal representation. 
         [0043]    Step 52  involves the computation of a skeletal representation for, or skeletonization of, the object represented by the data passed to this method in step  50 . This skeletonization process can be performed utilizing any standard skeletonization methodology; for example, we could utilize, but are not limited to, thinning and boundary propagation methods, distance field methods, geometric methods, or general-field functions. 
         [0044]    The final step in  FIG. 6  is step  54 . Step  54  involves the reduction of the skeleton computed in step  52  to a minimal representation. For more details see  FIG. 7 . 
         [0045]      FIG. 7  provides further details on the reduction of a skeletal model K to a minimal representation. Step  62  involves the conversion of the skeleton K computed in  52  to a graph G. Here, a graph is meant to indicate the mathematical construction that is composed of vertices, or points in space, and edges that connect said vertices to each other, where if the vertices u and v are in a graph G then u and v are connected to each other if and only if there exists an edge e(u, v) that connects the vertex u to the vertex v, and vise versa. This conversion involves the replacement of every point in the computed skeleton from  52  to a vertex in G, and the creation of an edge e(u, v) for every pair of points u,v∈K such that u is immediately adjacent to v and e is added to G. 
         [0046]    Step  64  involves the reduction of G to an acyclic graph, or tree. An acyclic graph, or tree, G is meant to indicate the mathematical construct of a graph that does not contain a cycle; where a cycle is a path, or series of vertices, p in G such that the first and last vertex in p are the same vertex. Here, a path p is meant to indicate the mathematical construct that is defined over a series of vertices for a graph G, and such that if a vertex u immediately proceeds a vertex vin p then there exists an edge e(u, v) in G. One methodology for such a reduction is detailed in  FIG. 9 . 
         [0047]    Step  66  involves the creation of a joint for the minimal representation for every vertex of degree greater than two. As a non-limiting example, we can create joints by sequentially querying each vertex v in G to determine v&#39;s degree. If v&#39;s degree is greater than two then we can set a flag that designates v as a joint in the minimal representation. 
         [0048]    Step  68  involves the creation of a joint for the minimal representation for every vertex of degree equal one. As in  66 , a non-limiting example for such a process would be to query the degree for every vertex v in G. If the degree of said vertex v in G is equal to one then we can set a flag that designates v as a joint for the minimal representation. 
         [0049]    Steps  70  and step  72  together implement a search for a significant change in the direction d of the overall skeleton.  72  begins this search by computing the direction of the lines defined over each edge in G. As a non-limiting example, if u and v are joints in G, and p is the path in G from u to v, then the direction of every edge e(x 1 , x 2 ), where x 1  is closer to u than x 2 , then the direction of e is computed as the vector subtraction x 2 - x 1 , for all pairs of vertices (x 1 , x 2 ) in the path p from u to v. The change in direction ΔT is then computed as the angular difference between the direction of two neighboring, edges, or ΔT=cos −1 (((x 2 -x 1 )·(x 3 -x 2 ))/(|x 2 -x 1 ||x 3 -x 2 |)). Alternatively, ΔT could be computed as ΔT=Σ i   i+r−2  cos −1  (((x i+1 -x i )·(x i+2 -x i+1 ))/(|x i+1 -x i ||x i+2 -x i+1 |))for some range r of edges: where 2≦r≦i+r≦|p| r is even and where i≧1. The computed value for ΔT is then assigned to the vertex at location i+└r/L┘. 
         [0050]    Step  72  implements the second half of the search for significant changes in the direction of the overall skeletal model structure. Significant changes in the skeletal model structure can be detected by scanning the value of ΔT for each vertex v 1 . If a value ΔT i &gt;θ is detected then the index i of the vertex v i  with said value for ΔT i  is temporarily stored. The values of ΔT for the subsequent vertex v i+1  is then read. If ΔT i+1 ≧ΔT i  then the value of ΔT i+1  is stored in the place of ΔT i . The process in step  72  continues in this manner until a value for ΔT i+1  is found such that ΔT i+1 &lt;ΔT i . Once a value for ΔT i+1  is found such that ΔT i+1 &lt;ΔT i  the values d 1 =|v i -v 1 | and d 2 =|v |p| - v i | are computed. If d 1 &gt;          and d 2 &gt;          then the vertex v i  associated with ΔT i  is converted to a joint for the minimal representation, as in  36 . 
         [0051]    Step  74  involves the removal of all of the remaining vertices. This is performed by visiting each remaining non-joint vertex v, where v participates in the two edges e(u, v) and e(v, w), removing v and the two edges e(u, v) and e(v, w) from G, and then adding the bi-undirected edge e(u, w) to G until only joints vertices remain in G. 
         [0052]      FIG. 7  is only provided as an illustrative example of the method for the reduction of a generic skeleton to a minimal representation.  FIG. 7  is in no way meant to be interpreted as limiting, or to be the singular means for the derivation of a minimal representation. 
         [0053]      FIG. 8  details a non-limiting example of a method for the verification of a minimal representation for a given object data set. Step  80  involves obtaining object data, such as in  FIG. 1 . Step  82  involves the computation of a minimal representation from the object data and data stored in an object library. For more details see  FIG. 11 . Step  84  involves the derivation of a new minimal representation as detailed in  FIG. 6 . 
         [0054]    Step  86  involves the computation of the deviation from the computed minimal representation in  82  and the derived minimal representation in  84 . The deviation in  86  is performed by aligning the minimal representation form  82  with the minimal representation from  84  and then computing the pair-wise deviation in location from the joints in the minimal representation from  82  with the joints in the minimal representation from  84 . If the minimal representation from  82  has more or less joints than the minimal representation in  84  then a penalty will be applied for each join in the minimal representation from  82  but not found in  84 , and vice versa. 
         [0055]    Step  88  decides if the deviation between the two minimal representations is high or low. If the deviation is low then the method in  FIG. 8  returns “TRUE” to indicate that the computed minimal representation is a valid representation for the object data. If the deviation is high then 92 returns “FALSE” to indicate that the computed minimal representation is an invalid representation for the object data 
         [0056]      FIG. 9  provides further details on the algorithm for reducing a graph G to an acyclic graph or tree. The method presented in  FIG. 9  takes as input an undirected graph G that may or may not be cyclic, a maximal cycle length l max  and a cycle detection function φ. The cycle detection function φ could be any of a number of widely known methods for the detection of cycles in a graph, including but not limited to breath-first-search and depth-fust-search. 
         [0057]    The algorithm in  FIG. 9  begins by using the cycle detection function φ to compute and return a set of cycles from G. This computed set of cycles is then stored in a queue Q. Each cycle C in Q is then investigated to determine if its length is less than l max . If the length of C is less than l max  then a new vertex v′ is created, and a new undirected edge e(v′, u) is created for each vertex u that is connected to some vertex v∈C but that u∉C. After e(v′, u) is created, e(v, u) is deleted form G. 
         [0058]    Once the adjacency list for v′ is constructed, all of the edges e(v, u) that participated in C are deleted form G. Similarly, every vertex V∈C is subsequently deleted from G. Finally, v′ is added to G. 
         [0059]    The algorithm in  FIG. 9  serves as a non-limiting illustrative example for the elimination of cyclical components of general graphs in a manner that maintains the overall geometrical properties of the original graph.  FIG. 9  is meant to imply an exclusively available approach. For example, we could easily modify the algorithm presented in  FIG. 9  such that the deletions in lines  15  and  18  are performed after line  11 . Many other such permutations of the algorithm presented in  FIG. 9  are possible while maintaining the original concept of the proposed method. 
         [0060]      FIG. 10  goes into further details about the core components of the object identification method presented in this claim. The core components are divided up into three main steps: library based segmentation  100 , computation of joint polytopes  110 , and alignment of minimal representation with object data  130 . The first major step involves the clustering of components, such as points, according to the geometrical properties of the minimal representation retrieved from the object library in  40 . 
         [0061]    Step  100  is broken up into four sub-steps  102 ,  104 ,  106 , and  108 . The first sub step  102  involves the alignment of the minimal representation from the library with the object data. This is done by computing the mean-deviation form for the object data and then aligning the origin of the object data with the origin of the minimal representation retrieved form the object library. 
         [0062]    Sub-Step  104  involves aligning the principle components of the minimal representation with the principal components of the object data. This is performed by computing the principle components associated with the object data, and then aligning the principle components of the minimal representation with the principle components of the object data, or vice versa, or both can be aligned with a pre-defined orientation for the principle components. For example, the first principle component can be aligned with the y-axis, the second principle component can be aligned with the x-axis, and the third principle component can be aligned with the z-axis. The number of principle components to be aligned is directly proportional to the dimensionality of the data passed in at  42 . 
         [0063]    Sub-Step  106  involves adjusting the size of the minimal representation retrieved from the library to have the same size and proportions as the object data. This can be performed via simple scaling methodologies over multidimensional space. 
         [0064]    Sub-step  108  involves the clustering of the primary components, such as points, of the object data according to the components, such as line segments, of the minimal representation from the object library. This can be done by any number of methods, but the two most efficient are general least squares methods and Voronoi diagram methods. 
         [0065]    As a non-limiting example, the least squares method for clustering can be formulated as follows. Let S :={s 1 , s 2 , . . . , s n } be the set of components for the minimal representation retrieved from the object library in  40 . Let P :={p 1 , p 2 , . . . , p k } be the set of components for the object data in  42 . Let {circumflex over (p)} j,i =proj sj p i  be the projection of component p i  from P onto a component s j  from S, and r j,i =|{circumflex over (p)} j,i −p i | be the residual after p i  has been projected onto s j . Then we can define the least squares equation 
         [0000]      minimize Σ j=3   n Σ i=3   k φ( s,r   j,i   ,p   i ) r   j,i   2 .
 
         [0000]    where φ(S, r j,i , p i ) is the function 
         [0000]    
       
         
           
             
               φ 
                
               
                 ( 
                 
                   S 
                   , 
                   
                     r 
                     
                       j 
                       , 
                       i 
                     
                   
                   , 
                   
                     p 
                     i 
                   
                 
                 ) 
               
             
             = 
             
               { 
               
                 
                   
                     
                       1 
                     
                     
                       
                         
                           if 
                            
                           
                               
                           
                            
                           
                             r 
                             
                               j 
                               , 
                               i 
                             
                           
                         
                         = 
                         
                           min 
                            
                           
                             { 
                             
                               
                                 
                                   r 
                                   | 
                                   r 
                                 
                                 = 
                                 
                                    
                                   
                                     
                                       
                                         proj 
                                         
                                           s 
                                           j 
                                         
                                       
                                        
                                       
                                         p 
                                         i 
                                       
                                     
                                     - 
                                     
                                       p 
                                       i 
                                     
                                   
                                    
                                 
                               
                               , 
                               
                                 1 
                                 ≤ 
                                 j 
                                 ≤ 
                                 n 
                               
                             
                             } 
                           
                         
                       
                     
                   
                   
                     
                       0 
                     
                     
                       
                         
                           if 
                            
                           
                               
                           
                            
                           
                             r 
                             
                               j 
                               , 
                               i 
                             
                           
                         
                         ≠ 
                         
                           min 
                            
                           
                             { 
                             
                               
                                 
                                   r 
                                   | 
                                   r 
                                 
                                 = 
                                 
                                    
                                   
                                     
                                       
                                         proj 
                                         
                                           s 
                                           j 
                                         
                                       
                                        
                                       
                                         p 
                                         i 
                                       
                                     
                                     - 
                                     
                                       p 
                                       i 
                                     
                                   
                                    
                                 
                               
                               , 
                               
                                 1 
                                 ≤ 
                                 j 
                                 ≤ 
                                 n 
                               
                             
                             } 
                           
                         
                       
                     
                   
                 
                 . 
               
             
           
         
       
     
         [0066]    Using the above least squares method the object data can be clustered according to the geometric properties of the minimal representation retrieved from the object library. 
         [0067]    Step  110  involves the computation of the bisecting polytope for each joint.  110  is divide up into two sub-steps. These bisecting polytopes can be utilized to align the components of the minimal representation retrieved from the object library. A bisecting polytope is defined as the set B of components from P that are within λ of the plane that bisects a joint φ in the minimal representation obtained in  40 . The joint φ is the intersection of two components s i ,s j ∈S. As such, the plane that bisects φ is a hyperplane. This means that λ is the distance of a component p i ∈P to the hyperplane that bisects φ, and all components p i ∈P within λ distance to said bisecting plane belong to the bisecting polytope B k  associated with the joint φ k . 
         [0068]    Sub-Step  112  involves the retrieval of the bisecting polytope information for each joint. This can be done during step  100 , or as a separate search after the completion of  100 . 
         [0069]    Sub-Step.  114  involves the computation of the centroid for each bisecting polytope B k ; where a centroid is the geometric center of mass for the bisecting polytope. The computation of the centroid can be done in the usual way. Since the object data P is regarded as a set of uncorrelated data points, the centroid for B k ={p i , p i+1 , . . . , p i+k } can be computed as 
         [0000]      centroid k =( p   i   ,p   i+1   , . . . , p   i+h )/h. 
         [0070]    The computation of the centroid in  114  is only a non-limiting example of one way to compute the centroid for B k ; for there are many other equivalent methods for computing the centroid for B k . Similarly, we could utilize the Euclidian in  114  center instead of the geometric center of mass. 
         [0071]    Step.  120  only has one sub-step, and involves the actual alignment of the minimal representation retrieved from the object library to the object data. This step involves updating the joint information for each intersection of a non-empty set of components from S in  40  with the corresponding centroid computed in  122 . 
         [0072]      FIG. 11  details a method for the computation of an aligned minimal representation for a provided set of object data. The fast computation of such an aligned, minimal representation is critically important for the rapid identification of objects. While the method detailed in  FIG. 11  specifically indicates a use in the identification of real world objects,  FIG. 11  is only meant to serve as a non-limiting example of an implementation of the proposed method. The example detailed in  FIG. 11  is for a serial implementation of the overall object identification method. To see information on a concurrent implementation see details in  FIG. 12 . 
         [0073]      140  depicts a library of previously computed minimal representations that can serve as a reference to be used in the acceleration of the computation of a minimal representation for the currently unidentified object. 
         [0074]    Step  142  indicates the acquisition of object data from a data source; specified in  14  as data representing a real world object. This object data acquisition can be performed as detailed in  FIG. 1  and  FIG. 5 . 
         [0075]    Step  144  involves a conditional that keeps track of the number of times that the main body of the method in  FIG. 11  has been entered, or the number of example minimal representations from the object library  140  that have been used by the method in  FIG. 11 . If this is the first time to enter the main method body then the iteration counter i is initialized to 1. If this is not the first time to enter the main method body then the iteration counter i is incremented by 1. 
         [0076]    Step  150  involves the retrieval of a previously identified minimal representation from the object library according to the value of the iterator i. This previously identified minimal representation is then utilized by Step  152  to segment the provided object data. The segmentation performed in  152  is according to a least square analysis such that each point p in the provided data is assigned to the closest segment of the minimal representation passed from  140 ; where said segmentation is performed after the minimal representation from  140  has been scaled to the same size as the representation in the raw object data, and has been aligned with the representation in the raw object data. 
         [0077]    Let S={p 1 , p 1 , . . . , p k } be the set of raw object data captured in  142 , and T={s 1 , s 1 , s 1 } be the set of components to the minimal representation retrieved from the object library in  150 . Then the segmentation performed in  1152  is done by assigning a value p i  from S to a component s j  in T according to the equation min d  {d(p i , s j )|p i ∈S n s j ∈T}; where d(p i , s j ) is the minimum Euclidean distance from a value p i  to a component s j . 
         [0078]    Step  154  involves the computation of the joint polytopes associated with the intersection of the minimal representation and the raw object data. A polytope is a geometric figure defined over a set of vertices. For the object identification method presented here, the raw data set S is mapped to a set of vertices to be utilized in the joint polytope. For each joint j i  specified by the minimal representation retrieved from the object library, a polytope is computed around said joint as the subset S i    ⊂ S that is within a distance ç within the bisecting plane, or bisecting planes, of the components that intersect at the joint j i . 
         [0079]    Step  156  aligns the joints of the minimal representation retrieved from the object library with the center of mass for the associated polytopes computed in step  154 . This alignment can be done, but is not limited to, by computing the mean-deviation form of the polytopes computed in step  154  and then updating the joint values to reflect the shift of the joint polytope from the origin. Step  158  involves the verification of the validity of the computed minimal representation in  154  and  156 . For further information, see  FIG. 8 . At the end of the verification process in  158  the method in  FIG. 11  adds the object data and the computed, aligned minimal representation to an alignment queue  162  and then checks in  160  to see if the current iteration of the loop used the Nth minimal representation from the object library. If it is not the Nth minimal representation then the process will loop back to  144 . If it is the Nth minimal representation then the process will go to  164 . 
         [0080]    Step  164  involves the selection of the best computed minimal representation. This selection is done by retrieving the computed minimal representation that has the least amount of total deviation from the derived minimal representation from  156 . This best computed minimal representation is then returned in  166 . 
         [0081]      FIG. 12  details a concurrent version of the method presented in  FIG. 11 . Both the serial method presented in  FIG. 11  and the concurrent method presented in  FIG. 12 . are equivalent except that the serial method presented in  FIG. 11  investigates the optimality of each object in the object library one at a time whereas the method presented in  FIG. 12  has multiple, concurrent paths that simultaneously take unique minimal representations from the object library to determine the fit of the chosen minimal representation with the object data.  FIG. 11  and  FIG. 12  present two, non-limiting implementations for the object identification method presented here. There are many other possible implementations. For example, we could also utilize a tree structure to organize the object library, and then utilized a combination of n, iterative and concurrent calls to gradually increase the accuracy of the identification process. 
         [0082]      FIG. 13  shows a series of steps in computing the identity of a virtual object via a single minimal representation.  210  is a point cloud representing the object data for a virtual object.  212  is a skeleton representing a single minimal representation.  214  is a segmented point cloud, based on  212  and as computed in  FIG. 11. 216  is the collection of bisecting polytopes associated with  214 .  218  is the minimal representation form  212  rigged to the point cloud from  210 . Note that if only a single minimal representation is paired with a single point cloud, or mesh, then the process described above is the same as a novel, fast automatic rigging method for a virtual object. 
         [0083]    The preceding detailed description of the methodologies and technologies herein is meant for illustrative purposes and descriptive purposes. This description is not meant to be exhaustive or limiting of technologies disclosed with respect to the exact form presented in the detailed description. Many possible variations and alterations are possible in light of the material covered above. The examples detailed above were chosen in an effort to best explain the concepts and principles of the technologies discussed herein. It is intended that the scope of the technologies presented herein be defined and delineated by the claims appended hereto.