Abstract:
A computer implemented method for tracking a marker on a deformable surface in augmented reality (AR) applications, comprising: detecting image-key-points in a currently processed video frame of a video-captured scene; performing key-point-correspondence searching and matching the image-key-points with model-key-points are identified from an original image of the marker, comprising: calculating an key-point matching score for each image-key-point; applying a key-point matching score filter on the key-point matching scores; restricting the searching of the image-key-points in the currently processed video frame to within same mesh block determined in a previously processed video frame of the captured video frames; 
     and applying adaptive thresholds on the key-point matching scores in determining successful matches of the image-key-points; performing motion detection of the marker in the video-captured scene and halting the application of the key-point matching score filter and suspending the restriction on the image-key-point searching if the marker is in significant movement.

Description:
COPYRIGHT NOTICE 
       [0001]    A portion of the disclosure of this patent document contains material, which is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the Patent and Trademark Office patent file or records, but otherwise reserves all copyright rights whatsoever. 
       FIELD OF THE INVENTION 
       [0002]    The present invention relates generally to the tracking of a marker in augmented reality (AR) applications. In particular, the present invention relates to the tracking of a flexible or deformable marker in real life AR applications. 
       BACKGROUND 
       [0003]    Augmented reality (AR) is a technology combining virtual objects and/or information with perceptions of the physical real-world environment through the use of sensors, computer-generated data, and/or multimedia playback devices in order to enhance the users&#39; perception of the physical real-world environment. For example, a camera can be used to video-capture a scene and a display unit such as video display glasses or goggles is used to project a computer-processed view of the scene to the viewer. Different from virtual reality where the viewer is presented a total artificial computer-generated viewing experience, only certain computer-generated imagery or virtual object is superimposed into the computer-processed view of the scene. The computer-generated imagery or virtual object can be viewer-interactive or driven by real-time user control or pre-configured settings and instructions. 
         [0004]    One key measure of the AR technique is how realistic the resulting augmented video as perceived, or how well the integration of the computer-generated imageries or virtual objects with the view of the scene. This requires the correct association of the computer-generated imageries or virtual objects and their placement locations within the scene throughout a motion sequence or consecutive video frames of the scene. One common issue among existing AR techniques is the tracking of three-dimensional coordinates and orientations of two-dimensional planar markers for placements of virtual objects within a video-captured scene. The tracking of markers allows the virtual objects to be superimposed into the scene at the marker locations and orientations through the motion sequence of the scene. 
         [0005]    However, the current state of the art does not have a satisfactory technique for addressing the situation in which a tracking marker for virtual object is placed on a deformable surface in a video-captured scene. A deformable surface can be found on a soft article such as a shirt on a person in motion, a flying flag, or moving water surface. A virtual object superimposed on a deformable surface not only need to properly appear at the right position in the right orientation during a motion sequence, its texture and shape must change along with the distortions of the deformable surface. 
       SUMMARY 
       [0006]    It is an objective of the presently claimed invention to provide a method of marker tracking in augmented reality (AR) applications, wherein the marker is placed on a deformable surface. It is a further objective of the presently claimed invention to provide such marker tracking method characterized by improved marker tracking stability, marker key-point matching accuracy, reduced marker texture stickiness, and better marker key-point matching under background lighting and video noise fluctuations. 
         [0007]    In accordance to various embodiments of the presently claimed invention, to track a marker placed on a deformable surface, polygon meshes are generated for the marker in a video-captured scene. The polygon meshes are for tracking the markers&#39; three-dimensional positions and orientations, and three-dimensional deformations throughout the motion sequence (or video frames) of the video-captured scene. 
         [0008]    In the generation of the polygon meshes of the marker in the video-captured scene, original key-points of the marker image are first identified. A key-point can be a sharp pictorial feature such as a corner, an edge, or an interest point of an object in the marker image. In various embodiments, key-points are detected using existing edge/corner/interest point detection or feature detection techniques in the art. Then in each of the subsequent video frames of the video-captured scene, the same key-points are to be searched and matched with the original key-points in a key-point-corresponding matching process. 
         [0009]    In the key-point-corresponding matching process, key-point matching scores are calculated, indicating how closely matched of the candidate key-points found in the subsequent video frames to the original key-points of the marker image. A match is considered successful only if the matching score of a candidate key-point found in a currently processed video frame is above a pre-determined matching threshold. Finally, the information of the successfully matched key-points in the currently processed video frame and the polygon mesh of the original image of the marker or the image of the marker in the first video frame are used to generate the recovered polygon mesh of the marker in the currently processed video frame. As such, the recovered polygon mesh reflects the changes in the three-dimensional position and orientation, and three-dimensional deformation of the marker in the currently processed video frame from the previous video frame in the video-captured scene. A marker placed on a deformable surface, therefore, is tracked by a series of recovered polygon meshes generated for a series of video frames. 
         [0010]    In accordance to one embodiment of the presently claimed invention, the aforementioned generation of the polygon meshes for the marker is enhanced in terms of key-point matching accuracy and marker tracking stability by incorporating an application of a key-point matching score filter; a restriction on candidate key-point searches in the currently processed video frame to within the same mesh block as in the previously processed video frame; an application of an adaptive threshold in determining successful matches of candidate key-points; and a motion detection of the marker in video-captured scene. 
         [0011]    The application of a key-point matching score filter is to reduce video-noise induced jitters in key-point matching score calculation. When the key-point matching scores of a particular key-point are calculated for across multiple video frames, occasionally sharp negative spikes are found. Experiments reveal that these negative spikes in the inter-frame key-point matching scores are likely caused by video noise rather than actual mismatching or poor matching of candidate key-points. A key-point matching score filter is applied to smoothen the inter-frame key-point matching scores. In one embodiment, the negative spikes are replaced by a weighted average or a moving average of inter-frame key-point matching scores. In another embodiment, the negative spikes are replaced by their preceding scores. 
         [0012]    The block of pixels in the video frame where the recovered polygon mesh is located is called the mesh block. Sometimes, false key-points are found outside of the mesh block due to video noise or other video effects, which cannot possibly be valid key-points of the marker. The mesh block key-point search restriction on candidate key-point searches is to limit key-point searching and matching in the currently processed video frame to within the same mesh block as in the previously processed video frame. As such, performance and accuracy are improved. 
         [0013]    Fluctuation in background lighting and video noise throughout the motion sequence of the video-captured scene can cause pixel characteristics, such as color and intensity gradient, to change from one video frame to another. In turn the same key-point that is found and correctly matched in different video frames with different background lighting and/or video noise can have significantly different key-point matching scores for the different video frames. A fixed threshold used in determining successful matches for all video frames will inevitably cause incorrect determination of failed matches of valid key-points. As such, an embodiment of the presently claimed invention uses an adaptive threshold in determining successful matches of found key-points throughout the video frames to accommodate the changing background lighting and/or video noise. In one embodiment, the adaptive threshold is a discounted moving average of the inter-frame key-point matching scores or a moving average of inter-frame key-point matching scores less a buffer value. 
         [0014]    As the marker&#39;s position changes through a motion sequence, the mesh block key-point search restriction could cause missed finding valid key-points that are located outside of the mesh block in the currently processed video frame when the marker has moved substantially from the previously processed video frame. At the same time, the key-point matching score calculation must also be more sensitive to found key-points that do not match with the original key-points of the marker image. Therefore, when the marker is moving substantially, the mesh block key-point search restriction is suspended temporarily and the application of key-point matching score filter is also halted temporarily. 
         [0015]    In one embodiment, motion vectors are computed by using vertices of the recovered polygon mesh from the previously processed video frame and vertices of the recovered polygon mesh from the currently processed video frame. If the motion vectors are greater than a pre-determined marker movement threshold, the mesh block key-point search restriction is suspended and the application of key-point matching score filter is also halted for the next video frame to be processed until the motion vectors, that are continuously being computed, are no longer greater than the pre-determined marker movement threshold. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0016]    Embodiments of the invention are described in more detail hereinafter with reference to the drawings, in which 
           [0017]      FIG. 1  shows an operation flow diagram of a method of tracking markers on deformable surface used in augmented reality (AR) application in accordance to one embodiment of the presently claimed invention; 
           [0018]      FIG. 2  shows a chart of exemplary inter-frame key-point matching scores and another chart of the same inter-frame key-point matching scores after the application of a key-point matching score filter in accordance to one embodiment of the presently claimed invention; 
           [0019]      FIG. 3  shows an exemplary mesh block of a marker in one video frame where key-points are found inside and outside of the mesh block; and 
           [0020]      FIG. 4  shows a chart of exemplary inter-frame key-point matching scores and an adaptive threshold in accordance to one embodiment of the presently claimed invention. 
       
    
    
     DETAILED DESCRIPTION 
       [0021]    In the following description, methods and systems of tracking markers on deformable surface used in augmented reality (AR) applications and the likes are set forth as preferred examples. It will be apparent to those skilled in the art that modifications, including additions and/or substitutions may be made without departing from the scope and spirit of the invention. Specific details may be omitted so as not to obscure the invention; however, the disclosure is written to enable one skilled in the art to practice the teachings herein without undue experimentation. 
         [0022]    Referring to  FIG. 1 . In accordance to various embodiments of the presently claimed invention, to track a marker placed on a deformable surface, polygon meshes are generated for the marker in a video-captured scene. The polygon meshes are for tracking the markers&#39; three-dimensional positions, two-dimensional orientations, and three-dimensional deformations throughout the motion sequence (or video frames) of the video-captured scene. 
         [0023]    In the generation of the polygon meshes of the marker in the video-captured scene, original key-points (referred to as model-key-points hereinafter) ( 113 ) of the marker image ( 111 ), which can be an original image of the marker are first identified. A key-point can be a sharp pictorial feature such as a corner, an edge, or an interest point of an object in the marker image. In various embodiments, model-key-points are detected using existing edge/corner/interest point detection or feature detection techniques in the art ( 112 ). Then in each of the subsequent video frames of the video-captured scene, the same key-points are to be searched and matched with the model-key-points in a key-point-correspondence matching process ( 131 ). 
         [0024]    In the key-point-correspondence matching process ( 131 ), key-point matching scores are calculated, indicating how closely matched of the candidate key-points (referred to as image-key-points hereinafter) ( 123 ) found in the subsequent video frames to the model-key-points. A match is considered successful only if the matching score of an image-key-point found in a currently processed video frame ( 121 ) is above a pre-determined matching threshold. Finally, information of the successfully matched image-key-points (also referred to as key-point correspondence) ( 132 ) in the currently processed video frame and the original marker polygon mesh ( 115 ) of the original image of the marker or the image of the marker in the first video frame are used to generate the recovered polygon mesh ( 134 ) of the marker in the currently processed video frame. As such, the recovered polygon mesh ( 134 ) reflects the changes in the three-dimensional position and orientation, and three-dimensional deformation of the marker in the currently processed video frame from the previous video frame in the video-captured scene. A marker placed on a deformable surface, therefore, is tracked by a series of recovered polygon meshes generated for a series of video frames. 
         [0025]    Still referring to  FIG. 1 . In accordance to one embodiment of the presently claimed invention, the aforementioned generation of the polygon meshes for the marker is enhanced in terms of key-point matching accuracy and marker tracking stability by incorporating an application of a key-point matching score filter (also referred to as spike removal) ( 101 ); a restriction on image-key-point searches in the currently processed video frame to within the same mesh block as in the previously processed video frame (also referred to as block search and matching) ( 102 ); an application of an adaptive threshold ( 104 ) in determining successful matches of image-key-points; and a motion detection ( 103 ) of the marker in video-captured scene. 
         [0026]    The application of a key-point matching score filter ( 101 ) is to reduce video-noise induced jitters in key-point matching score calculation. When the key-point matching scores of a particular image-key-point are calculated for across multiple video frames, occasionally sharp negative spikes are found.  FIG. 2  shows on the left half a chart of exemplary inter-frame key-point matching scores for multiple video frames, which exhibits sharp negative spikes. Experiments reveal that these negative spikes in the inter-frame key-point matching scores are likely caused by video noise rather than actual mismatching or poor matching of candidate key-points. A key-point matching score filter is applied to smoothen the inter-frame key-point matching scores. In one embodiment, the negative spikes are replaced by a weighted average or a moving average of inter-frame key-point matching scores. In another embodiment, the negative spikes are replaced by their preceding scores.  FIG. 2  shows on the right half a chart of the same inter-frame key-point matching scores after the application of the key-point matching score filter. 
         [0027]    The block of pixels in the video frame where the recovered polygon mesh is located is called the mesh block. Sometimes, image-key-points are found outside of the mesh block due to video noise or other video effects, which cannot possibly be valid image-key-points of the marker.  FIG. 3  shows an exemplary mesh block of a marker in one video frame where image-key-points are found inside and outside of the mesh block. The mesh block key-point search restriction on image-key-point searches is to limit key-point searching and matching in the currently processed video frame to within the same mesh block as in the previously processed video frame. As such, performance and accuracy are improved. 
         [0028]    Fluctuation in background lighting and video noise throughout the motion sequence of the video-captured scene can cause pixel characteristics, such as color and intensity gradient, to change from one video frame to another. In turn the same image-key-point that is found and correctly matched in different video frames with different background lighting and/or video noise can have significantly different key-point matching scores for the different video frames. A fixed threshold used in determining successful matches for all video frames will inevitably cause incorrect determination of failed matches of valid image-key-points. Thus, one embodiment of the presently claimed invention uses an adaptive threshold in determining successful matches of found key-points throughout the video frames to accommodate the changing background lighting and/or video noise. In one embodiment, the adaptive threshold is a discounted moving average of the inter-frame key-point matching scores or a moving average of inter-frame key-point matching scores less a buffer value.  FIG. 4  shows a chart of exemplary inter-frame key-point matching scores and an adaptive threshold. 
         [0029]    As the marker&#39;s position changes through a motion sequence, the mesh block key-point search restriction could cause missed finding valid image-key-points that are located outside of the mesh block in the currently processed video frame when the marker has moved substantially from the previously processed video frame. At the same time, the key-point matching score calculation must also be more sensitive to found image-key-points that do not match with the model-key-points. Therefore, when the marker is moving substantially, the mesh block key-point search restriction is suspended temporarily and the application of key-point matching score filter is also halted temporarily. 
         [0030]    In one embodiment, motion vectors are computed by using vertices of the recovered polygon mesh from the previously processed video frame and vertices of the recovered polygon mesh from the currently processed video frame. If the motion vectors are greater than a pre-determined marker movement threshold, the mesh block key-point search restriction is suspended and the application of key-point matching score filter is also halted for the next video frame to be processed until the motion vectors, that are continuously being computed, are no longer greater than the pre-determined marker movement threshold. This way the texture stickiness of the marker is reduced substantially. 
         [0031]    In accordance to various embodiments of the presently claimed invention, the key-point-correspondence matching process can be enhanced by all or any combination of the abovementioned process modules of application of key-point matching score filter; restriction on image-key-point searches in the currently processed video frame to within the same mesh block as in the previously processed video frame; application of adaptive threshold in determining successful matches of image-key-points; and motion detection of the marker in video-captured scene being executed concurrently and in serial manner. 
         [0032]    The embodiments disclosed herein may be implemented using general purpose or specialized computing devices, computer processors, or electronic circuitries including but not limited to digital signal processors (DSP), application specific integrated circuits (ASIC), field programmable gate arrays (FPGA), and other programmable logic devices configured or programmed according to the teachings of the present disclosure. Computer instructions or software codes running in the general purpose or specialized computing devices, computer processors, or programmable logic devices can readily be prepared by practitioners skilled in the software or electronic art based on the teachings of the present disclosure. 
         [0033]    In some embodiments, the present invention includes computer storage media having computer instructions or software codes stored therein which can be used to program computers or microprocessors to perform any of the processes of the present invention. The storage media can include, but are not limited to, floppy disks, optical discs, Blu-ray Disc, DVD, CD-ROMs, and magneto-optical disks, ROMs, RAMs, flash memory devices, or any type of media or devices suitable for storing instructions, codes, and/or data. 
         [0034]    The foregoing description of the present invention has been provided for the purposes of illustration and description. It is not intended to be exhaustive or to limit the invention to the precise forms disclosed. Many modifications and variations will be apparent to the practitioner skilled in the art. 
         [0035]    The embodiments were chosen and described in order to best explain the principles of the invention and its practical application, thereby enabling others skilled in the art to understand the invention for various embodiments and with various modifications that are suited to the particular use contemplated. It is intended that the scope of the invention be defined by the following claims and their equivalence.