Patent Publication Number: US-2022221942-A1

Title: Method and apparatus for object tracking using objects with tracking marks

Description:
TECHNICAL FIELD 
     The present disclosure generally relates to the field of computer input and tracking devices and, more particularly, computer-assisted drawing devices such as a pen or a stylus which tracks user hand movements to create series of point coordinates that represent a drawing or hand writing. 
     BACKGROUND 
     This section describes approaches that could be employed, but are not necessarily approaches that have been previously conceived or employed. Hence, unless explicitly specified otherwise, any approaches described in this section are not prior art to the claims in this application, and any approaches described in this section are not admitted to be prior art by inclusion in this section. 
     Computer-assisted design and drawing applications often require an input device to track user hand movements and translate them to series of computer coordinates representing a drawing or hand writing. Examples of such input devices include digital pens and styluses such as the Apple Pencil™. A digital pen often requires a touch sensitive surface such as an Apple iPad™ to track the positions of the tip of the pen. The use of a touch sensitive surface limits the drawings to the area of the surface, and thus makes such digital pens unsuitable for large drawings when a large touch sensitive surface is expensive or not available. 
     This disclosure describes a new type of digital pen which allows users to draw on any surface, or even in the air without a hard surface. Users can use the new digital pens to draw not only two-dimensional drawings but also drawings in three-dimensional spaces. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
       To provide a more complete understanding of the present disclosure and advantages thereof, reference is made to the attached drawings, like reference numbers represent like parts, in which: 
         FIG. 1  illustrates an example embodiment of a new 3D input system consisting of a 3D pen, a tracking camera, and a computer that processes camera images to calculate the positions and movements of the 3D pen and generate drawing strokes. 
         FIG. 2  illustrates an example embodiment of a 3D pen with tracking marks. 
         FIG. 3  illustrates an example embodiment of the 3D algorithm. 
         FIG. 4  illustrates an example embodiment of a method to calculate the three-dimensional position of a 3D pen from a two-dimensional image of the tracking marks of the pen. 
     
    
    
     DESCRIPTION OF EXAMPLE EMBODIMENTS 
     Overview 
     A three-dimensional input device that allows computer users to draw on any surface or in three-dimensional space without the need of a touch sensitive drawing pad. The system consists of a pen, a digital video camera, and a computer that runs an algorithm to calculate the three-dimensional positions and orientations of the pen in real-time from the images of the pen. 
     The pen in this system is marked with three or more distinct tracking marks whose distances between each other are known. The digital video camera captures the images of the pen and sends the images to the computer in real-time. The computer runs a software algorithm that processes the images of the pen from the camera, detects the tracking marks, calculates the three-dimensional positions of the tracking marks, and determines the three-dimensional positions of the pen, in particular the positions of the drawing tip of the pen. 
     The three-dimensional positions of the tip of the pen are then sent to software applications such as a drawing app or a computer-aid design (CAD) app to create user drawings. 
     DETAILED DESCRIPTION 
       FIG. 1  illustrates an example embodiment of the new three-dimensional computer input system which has the following components: 
     1. A 3D Pen: a handheld device which has three or more distinct tracking marks. A tracking mark can be a small shape or symbol such as a dot, a cross, an asterisk, or a star. A tracking mark can also be a feature point in a geometric tracking pattern such as an intersection in a grid pattern or a corner in a checker board pattern. The position of a feature point in a tracking pattern is calculated using a large number of data points from the image of the tracking pattern to improve tracking accuracy and reduce errors caused by image noises. For example, in a grid pattern, a tracking mark can be the intersection of two straight lines, and a large number of image pixels can be used to calculate the positions and orientations of the lines and the position of their intersection in the image. The tracking marks and patterns can be painted on the surface of the pen or illuminated using small lights such as LED lights. There can be multiple groups of three or more tracking marks so that at least one group is visible when the pen is held at different positions and angles. The distances from each tracking mark to the other tracking marks in the group are known. The distances from some tracking marks to the drawing tip of the pen are also know. The groups of tracking marks and the tracking marks in a group can be distinguished by their relative positions, shapes, colors, or geometric properties.  FIG. 2  illustrates one embodiment of the 3D pen with a group of three tracking marks M 1 , M 2 , and M 3  that form a straight line to the tip T of the pen. The distances from M 1  to M 2 , from M 2  to M 3 , and from M 1  to T are known. M 3  can be distinguished from M 1  and M 2  by its distinct star shape. M 1  and M 2  can be distinguished by their distances to M 3  or T. The collinear property of M 1 , M 2 , and M 3  can be used to distinguish them from other groups. Other embodiments of the 3D pen can have groups with redundant tracking marks to improve accuracy and to ensure that if some marks are hidden or covered by the holding hand, at least three tracking marks are visible by the tracking camera. 
     2. A Tracking Camera: a digital high-definition video camera that continuously captures the images of the 3D pen. The focal length of the camera lens is known or assumed. The field of view of the camera is wide enough to capture at least three tracking marks on the 3D pen. The images of the 3D pen are streamed in real-time to the tracking computer. 
     3. A Tracking Computer: a computing device with an input port that receives images of the 3D pen from the tracking camera. The tracking computer runs the 3D Pen Algorithm which processes the images from the camera, detects the tracking marks from the images, and uses the positions of the detected tracking marks in the two-dimensional images to compute the position of the drawing tip of the 3D pen in three-dimensional space. The computer then sends the positions of the drawing tip of the 3D pen in real-time to the application that requires drawing or hand writing user inputs. 
     4. 3D Pen Algorithm: a method to process the images of the 3D pen, compute the three-dimensional positions of the drawing tip of the pen, and generate drawing strokes.  FIG. 3  illustrates an example embodiment of the 3D Pen Algorithm. 
     In the first step, an image of the 3D pen is processed using techniques such as image sharpening, smoothing, and noise reduction, and the tracking patterns and tracking marks are detected and extracted from the image using techniques such as dot detection, corner point detection, feature detection, edge detection, line detection, image segmentation, adaptive threshold, pattern recognition, machine learning, color filters, and other digital filters. The position of a tracking mark in the two-dimensional image is calculated using methods such as finding the center of gravity of a shape or calculating the intersection of two lines. 
     In the second step, the tracking marks and tracking mark groups are distinguished and identified using their colors, shapes, relative positions, geometric properties or patterns. For example, the tracking marks which are collinear can be distinguished and put in a group. In other embodiments, the tracking marks can be grouped by their colors or positions. 
     In the third step, the three-dimensional positions of a group of three or more tracking marks are calculated using the positions of the tracking marks in the two-dimensional images, the distances from the tracking marks to each other, and the focal length of the camera. 
       FIG. 4  illustrates an example embodiment of the calculations of the positions of the tracking marks and the tip of the pen. C is the position of the camera lens (convergence point). F is the central focal point of the camera on the image plane. Reference point T is the tip of the pen. M 1 , M 2 , and M 3  are the three-dimensional positions of the tracking marks, and d 0 , d 1  and d 2  are the distances from T to M 1 , M 1  to M 2 , and M 2  to M 3  respectively. P 1 , P 2 , and P 3  are the projections of the tracking marks M 1 , M 2 , and M 3  respectively on the two-dimensional camera image. The positions of P 1 , P 2 , and P 3  are determined in the first step above. Angle a 1  is the viewing angle between the tracking marks M 1  and M 2  as viewed from the camera. Angle a 2  is the viewing angle between the tracking marks M 2  and M 3  as viewed from the camera. The positions of the tracking marks can be calculated using the following sub-steps:
         3A. Calculate the viewing angles a 1  and a 2 : First, calculate the distances s 1  and s 2  between P 1  and P 2  and between P 2  and P 3  respectively. Calculate the distances r 1 , r 2 , and r 3  between the central focal point F to P 1 , P 2 , and P 3  respectively. Calculate the distance f 1  from C to P 1  using the two sides f and r 1  of the right triangle [C, F, P 1 ]. Similarly, calculate the distances f 2  and f 3  from C to P 2  and P 3  respectively. Calculate the viewing angle a 1  using the three sides f 1 , f 2 , and s 1  of the triangle [C, P 1 , P 2 ]. Similarly, calculate the viewing angle a 2  using f 2 , f 3 , and s 2 .   3B. Calculate the distances e 1 , e 2 , and e 3  from C to the tracking marks M 1 , M 2  and M 3  respectively: From the facts that the area of the triangle [C, M 1 , M 2 ] is e 1 ·e 2 ·sin(a 1 )/2, the area of triangle [C, M 2 , M 3 ] is e 2 ·e 3 ·sin(a 2 )/2, and the ratio of the two areas is d 1 /d 2 , calculate the angle a 3  in the triangle [M 1 , M 3 , C] using the formula:       

       tan( a 3)=( d 1/ d 2)sin( a 1+ a 2)/[sin( a 1)/sin( s 2)−cos( a 1+ a 2)]
         Calculate the angle a 4  in the triangle [M 1 , M 3 , C] using the formula:       

         a 4=180°−( a 1+ a 2+ a 3)
         Calculate e 1 , e 2 , and e 3  using the angles a 1 , a 2 , a 3 , a 4 , and the distances d 1 , d 2  according to the Law of Sines:       

         e 1=( d 1+ d 2)sin( a 3)/sin( a 1+ a 2) 
         e 2= d 1 sin( a 4)/sin( a 1) 
         e 3=( d 1+ d 2)sin( a 4)/sin( a 1+ a 2)         3C. Calculate the three-dimensional positions of the tracking marks: Let M 1 , M 2 , and M 3  be the positions of the tracking marks and P 1 , P 2 , and P 2  be the positions of their projections on the camera image plane in a three-dimensional Cartesian coordinate system whose origin is at the convergence point C of the camera lens. Calculate M 1 , M 2 , and M 3  using:       
         M 1=−( e 1/ f 1) P 1
 
         M 2=−( e 2/ f 2) P 2
 
         M 2=−( e 3/ f 3) P 3
 
     In a different embodiment, M 1 , M 2 , and M 3  are not collinear. The four points C, M 1 , M 2 , and M 3  form a tetrahedron. The three-dimensional positions of M 1 , M 2 , and M 3  can be calculated using the three distances between M 1  and M 2 , between M 2  and M 3 , and between M 3  and M 1 , and the three viewing angles from C to M 1  and M 2 , from C to M 2  and M 3 , and from C to M 3  and M 1 , which are equal to the angles from C to P 1  and P 2 , to P 2  and P 3 , and P 3  and P 1  respectively. 
     In the fourth step, the three-dimensional position of the reference point T, which refers to the tip of the pen, is calculated using the distances from T to the tracking marks and the three-dimensional positions of the tracking marks. For example, if T, M 1  and M 2  are collinear, the position of T can be calculated using linear extrapolation: 
         T =(( d 0+ d 1) M 1− d 0· M 2)/ d 1
 
     In the fifth step, the three-dimensional positions of the drawing tip T of the pen are processed in real-time to generate the drawing strokes. In one embodiment, there is a button or pressure sensor in the 3D pen for user to indicate the start and end of each drawing stroke. In another embodiment, the start and end of a stroke can be automatically detected by analyzing the positions and movements of the drawing tip of the 3D pen relative to the drawing surface. If the position of the tip of the pen moves away from the drawing surface, the drawing stroke ends, if the position of the tip of the pen moves back on to the drawing surface, a new stroke starts. If the drawing surface is a flat plane, the drawing surface can be detected by analyzing three or more previous positions of the tips of the 3D pen on the surface. 
     In another embodiment, a generic object can be tracked instead of a drawing pen. The generic object can have three or more tracking marks and multiple reference points such as tips, end points, corners, holes, the center of gravity, and other distinct points of the object. The three-dimensional positions of the reference points can be calculated using the distances from the reference points to the tracking marks and the three-dimensional positions of the tracking marks. The three-dimensional positions of the reference points then can be used to determine the dimensions, positions, orientations, and movements of the object in three-dimensional space. 
     In some embodiments, the distances from some reference points to the tracking marks are not known in advance. In these cases, the distances can be calculated using one or more calibration images. If a reference point and the tracking marks are collinear or coplanar, only a single calibration image is needed. For example, in  FIG. 4 , if the distance d 0  from the reference point T (the drawing tip of the pen) to the tracking mark M 1  is not known in advanced, and P 0  is the position of T in the two-dimensional camera image, then P 0  and P 1  can be used to calculate the viewing angle a 0  from C to P 0  and P 1  (and to T and M 1 ), similar to step 3A above. Since T, M 1 , and M 2  are collinear, angle a 5 =a 4 −a 0 , and d 0  can be calculated using the Law of Sines for triangle [C, T, M 1 ]: 
         d 0= e 1 sin( a 0)/sin( a 5) 
     If a reference point and the tracking marks are not coplanar, two calibration images of the object are taken from different perspectives by moving the object. The positions of the tracking marks in the two images are used to calculate the object displacement. Given the displacement, stereoscopic triangulation is then used to calculate the three-dimensional position of the reference point and subsequently its distances to the tracking marks. 
     Similar calibrations can be used to determine the three-dimensional positions of other tracking marks. Thus starting from a group of three tracking marks with known distances to each other, the distances between all tracking marks to each other can be calculated.