Field of the Invention

[0001] The present invention relates to the field of interactive image display, and more specifically to apparatus and methods relating to the real-time tagging, positioning, and tracking of objects for interactive image display applications such as interactive television.

Background Information

[0002] Object identification and hyperlink tagging in video media allows a viewer to learn more about displayed objects by selecting an object and being linked to a website with additional information about the object. This provides sponsors of a television program or a movie production with a means to effectively embed advertising in a program or to display advertisements that will allow interested viewers to learn more about products or services displayed therein. [0003] Currently, no object tagging or tracking procedures are considered at the time of filming. The object identification and tagging in the video medium is done at the post-editing stage. This task is typically done by a human manually entering the object information in a database. A more automated approach has been to use image recognition technology to track the object of interest in the captured video stream. This, however, is more error-prone even with current state-of-the-art image processing algorithms.

Summary of the Invention

[0004] The present invention is directed to apparatus and methods that track the location of an object within a video image at the time of capture of the video image. The location of the object within each frame can be recorded as meta-data for the video image so that when the video image is played back, a viewer can select the object using suitable interaction means and be linked through to a source of additional information about the object, such as a product website or the like. Preferably, the present invention allows multiple objects in an image to be individually tracked and identified.

[0005] In accordance with an exemplary embodiment of the present invention, a device emitting radio frequency (RF) signals is attached to an object that is to be identified and tracked within a video image. Using an RF receiver with multiple antennas and applying trilateration techniques, the object's location within the video image is determined in real time and recorded as the video image is recorded. Where multiple objects are to be tracked, each object is provided with a radio device having a unique ID and the location of each device within the video image is recorded. [0006] Using a projection algorithm, positions of the objects in the 3-D field can be mapped to a set of pixels on the 2-D screen on which the image is displayed. The coordinate information, the frame number of the filmed video, the ID of the radio device, and other relevant or useful information can be stored in a database, as metadata, or in any appropriate form, at the time of recording.

[0007] In a further exemplary embodiment, a camera capturing an image containing the tagged object is also provided with RF emitting devices which allow for the determination of the camera position and orientation using trilateration techniques. Using additional camera information such as focal length and field of vision, the 2-D virtual screen representing the captured image can be derived.

[0008] The aforementioned and other features and aspects of the present invention are described in greater detail below.

Brief Description of the Drawings

[0009] FIG. 1 is a high-level block diagram of an exemplary embodiment of an object tagging system in accordance with the present invention.

[00010] FIG. 2 is a high-level flow chart illustrating the operation of the system of

FIG. 1.

[00011] FIG. 3 is a schematic representation of a trilateration technique used in an exemplary embodiment of the present invention. [00012] FIGs. 4A through 4D diagrams for illustrating an exemplary technique of mapping the three-dimensional location of an object onto a virtual, two-dimensional screen representative of an image captured by a camera.

Detailed Description

[00013] FIG. 1 is a block diagram of an exemplary embodiment of an object tagging system 100 in accordance with the present invention. The system 100 comprises a positioning block 110, a computing block 120, and media storage 130. The positioning block 110 tracks and determines positional information relating to a camera 140 and one or more objects 150.

[00014] As contemplated in the exemplary system 100, each object 150 is provided with a radio device or tag 155 that allows the positioning block 110 to locate the object and track its position in real time using trilateration techniques, described below in greater detail. Any of a variety of suitable radio technologies, including, for example, RFID, Bluetooth, or UWB, can be exploited for this purpose. The tag 155 may be an active device which emits a signal under its own power, or it may be a passive device which emits a signal derived from a signal with which it is illuminated. Where multiple objects 150 are to be tagged, each tag 155 preferably emits a unique ID to allow individual tracking of the multiple objects.

[00015] As the camera 140 captures images of a scene including the tagged object 150, the object's location in three dimensions is determined by the positioning block 110. For determining the location of the object 150 with trilateration, the positioning block 110 uses multiple antennas for receiving signals from the tag 155. (An additional, emitting antenna may be included for implementations using passive tags.) In addition, the location, shooting angle, focal length, and/or field-of-view of the camera 140 is provided to the positioning block 110. The camera information can be provided to the positioning block 110 over a dedicated interface (wireless or hardwired) or, like the object 150, the camera 140 may have one or more tags attached thereto, with the tags providing the camera information. An exemplary trilateration arrangement in which the camera is provided with multiple tags is described below. In a further exemplary embodiment, the relevant camera information can be determined by the camera itself or by data collection apparatus associated with the camera and sent therefrom to the positioning block.

[00016] The camera information and object location information are provided in real time to the computing block 120. Using a projection algorithm described in greater detail below, the computing block maps the three-dimensional object location information onto a two-dimensional field representing the viewing screen of the captured video image. The location of the tagged object 150 within a scene can be represented in terms of pixel locations in the captured image.

[00017] The 2D location information of the tagged object 150 within each frame of a captured video stream is provided and recorded in the media storage 130. For multiple tagged objects, the location information for each object is associated with the object's ID. Each tagged object is associated with a hyperlink so that when the viewer of the video stream points to and selects the object (with a suitable interaction device such as, for example, a mouse or a television remote control), the user can navigate to a website with additional information about the object. [00018] FIG. 2 is a high-level flow chart illustrating an exemplary method in accordance with the present invention. As mentioned above, the location of the tagged object in three-dimensional space is first determined, at step 201. At step 202, the 3D location of the object is mapped onto a two-dimensional virtual screen representative of the image captured by a camera viewing a scene containing the object. The processing of the object location takes place while the image is captured, as represented by step 203. The location information and the image are recorded at step 204. Additional information may also be recorded, including, for example, object ID, time, and frame number, among others. The data and image recording are preferably done simultaneously.

[00019] Exemplary techniques for carrying out the steps illustrated in FIG. 2 will now be described in greater detail.

[00020] An exemplary arrangement for determining the coordinates in three- dimensional space of an object will now be described with reference to FIG. 3. The points R ₀ , R ₁ , R ₂ , and R^ are stationary, known reference points from which distances to any RF transmission point, P, can be measured. In the exemplary system described above, the points R ₀ , R ₁ , R ₂ , and R ₃ represent the locations of antennas receiving emissions from an RF tag located at point P. The receiving antennas are used in a time difference of arrival (TDOA) scheme in which the differences in the times of arrival at the antennas of a signal emitted from the tag are used to determine the distances from each antenna to the tag. [00021] i? _o is treated as the origin of the Cartesian coordinate system and the line

R ₀ R^ is in the yz-plane. The line R ₀ R ₂ is on the z-axis. ^ ₁ andi? ₃ can be placed anywhere in the domain except on the z-axis. In an exemplary embodiment, the points R ₁ , R ₂ , and R ₃ are on the y, z, and x axes, equidistant from the origin R ₀ of the 3 dimensional Cartesian coordinate system. [00022] For an arbitrary transmission point P = (x,y,z) , r _Q , r, , r ₂ , and r ₃ are the distances between point P and points R ₀ , R _x , R ₂ , and R ₃ , respectively, and are determined using the aforementioned TDOA technique. The RF signal receiving points and the transmission points can be arranged so as to have non-negative coordinates by proper placement of R ₀ , R _x , R ₂ , and R ₃ .

[00023] The coordinates of the reference points can be represented by d _x , d ₂ , d ₃ , d _A , d ₅ and d ₆ , the distances between the reference points. These distances are fixed and known. The angles among the line segments connecting reference points can be obtained from basic trigonometric relationships, as follows:

[00024] Then, the coordinates R ₁ (0, y _x ,z _x ) and R ₂ (0,0, z ₂ ) are given by:

y _x = d _x cos(— - α) z _x = d _x sin(— - α) (2) z ₂ = d ₂ .

[00025] The coordinates of R ₃ (x ₃ ,y ₃ ,z ₃ ) can be obtained by solving the following equations: _J ² 2 , 2 , 2

«3 = *3 +^3 ^{+ Z} 3

^ ₅ ² =X ₃ ² ₊ ^ ₃ ² +(^ ₃ -Z ₂ ) ² (3)

These equations yield the following solutions:

z ² +J ₃ ² -J ₅ ²

^Z 3 =

2z,

(4) [00026] Once the coordinates of the reference points R _x , R ₂ and R ₃ are determined, the coordinates of point P = (x,y,z) can be obtained by solving the following system of equations:

r ₃ ² =(x-x ₃ ) ² +(^-^ ₃ ) ² +(z-z ₃ ) ²

This system of equation yields the following solution:

₌ ^r o ^{2 ~r} \ +y? + ^z ϊ -( ^r o ^2z i ^~ r ₂ ^{2 Z} _x )Iz ₂ ^{~ z} ^2 ₍₆₎

_ _ ^0 ² -^ ^{2 + Z} 2 ²

2z ₂

The sign of x should be positive due to the assumptions made above. [00027] As such, using the exemplary trilateration technique described, the 3D coordinates of the tagged object (at point P), can be determined from the distances between the receiving antennas ( J ₁ , J ₂ , J ₃ , J ₄ , J ₅ and J ₆ ) and the distances between the receiving antennas and the tagged object ( r ₀ , r, , r ₂ , and r ₃ ). [00028] Ultimately, the object appears on a two-dimensional screen, thus, the object coordinates in three-dimensional space should be mapped on a virtual planar surface which represents the screen to be viewed. An exemplary procedure for performing such a mapping will now be described with reference to FIGs. 4A-4D which show a camera 310, a tagged object 320, and a two-dimensional plane or virtual screen 350 representative of the image (still or moving) captured by the camera. FIG. 4A shows a plan view, FIG. 4B an elevation view and FIG. 4C an isometric view of the aforementioned elements. The screen 350 extends horizontally and vertically by dimensions h and v, respectively, about a center point C ₀ .

[00029] Three points are shown on the camera 310, C _a , C _b , and C _c , at which emitters, such as the tag used for the object 320 are located, in accordance with an exemplary embodiment of the invention. The coordinates of each of these points, ^c a = (x _a ,y _a > ^z a) > ^c b = (x _b >yb> ^z b) > ^c c = ( ^x c>yo ^z c) > ^{can be} determined from the distances between these points and the reference points R ₀ , i?, , R ₂ , and R ₃ , using a similar procedure and arrangement as described above for the coordinates of the object 320, P = (x _p ,y _p , z _p ) . With reference to FIG. 1, the same positioning block

1 10 and receiving antennas used to locate the tagged device(s) 150 can be used for determining the location and orientation of the camera 140. As shown in FIG. 4A, the points C _b , and C _c are arranged in a line that is substantially perpendicular to a line L _c which includes the point C _a and is substantially at the center of the field of view of the camera 310. The line L _c is also perpendicular to the two-dimensional plane 350 of the scene, which is defined, as shown in FIG. 4C, by the lines L _x andZ _y .

[00030] Ideally, the point C _a is at the center of the lens of the camera but because of the physical limitations of placing an emitting device there, it is preferably as close as possible, such as centered directly above the lens. In this embodiment, the points C _b , and C _c are equidistant from the center of the camera lens, in which case, the line L _c includes the midpoint between the points C _b , and C _c , namely, C _1n = {x _m ,y _m ,z _m ) , where x _m = (x _b + x _e )/2 , y _m = (y _b + y _e )/2 , z _m = (z _b + z _e )/2 . The line, L _c , through C ₀ and the midpoint C _n , = (x _m ,y _m ,z _m ) of C _b and C _c , can be expressed as follows: A- ~ ^X a y- y _a z-

(7)

^X _m ~ ^X n y _m - -y _n z _m [00031] Let /, m, n be the directional cosine of the line L _c , then they become:

x~ -x.

I = -

J( ^χ _m - ^χ _a ) ² +(y _m -y _a ) ² +(z _m -z _a γ z_ -z. n =

V ⁽ *.-*. ⁾² + ⁽ x.->'. ⁾² + ⁽ *..-O ²

[00032] The image of the object point P on the screen 350 is designated as point P ₁ =(X^y ₁ , Z ₁ ). A line L _p from the point C ₀ to the object image point P ₁ =(x _l ,y _l ,z _l ) is:

Because the line L _c is perpendicular to the plane 350 and the point C ₀ - (x ₀ , y _o ,z _o ) is in the plane 350, the equation of the plane 350 becomes l(x-x _o ) + m(y-y _o ) + n(z-z _o ) = 0. (10)

[00033] The center point of the screen plane 350 can be used as the origin of a two- dimensional coordinate system for the screen plane 350. Since the center point C ₀ = (x ₀ ,y _o ,z ₀ ) is on the line L _c , it satisfies the following:

[00034] Another equation is needed to close the system and to determine the coordinates of the point C ₀ . The focal length/of the camera is the distance from the lens of the camera C ₀ to the focal point of the camera, which corresponds to the center point C ₀ . As such:

f = J( ^χ _a - ^χ ₀ Y+(y _a -y ₀ ) ² +(Z ₀ -Z ₀ ) ² . (12) [00035] Let k _o be a constant which satisfies: in which case the focal length/and k ₀ have the following relationship:

K = ^ ■ (14)

V(*m - ^X af +(y _m -y _a f+( ^Z _m -Z of

The coordinates of point C ₀ are:

^X o= ^X _a + ^k _O ( ^X _m - ^χ a) y _o =y _o + K(y _m -y _a )- O ⁵ )

[00036] The coordinates of the object image point P ₁ can be obtained from the following system of equations:

l(x,-x _o ) + m(y _ι -y _o ) + n(z,-z _o ) = 0 (16)

AzΞ±. ₌ ^y .-y _° =Λz^ _{=k (17)}

^X p ^~X a y _p ^~ y _a ^Z p ^~Z a

[00037] Eq.17 follows from the fact the point P ₁ is on screen 350. The second part of the above equations is valid since the point P ₁ is on a line connecting point C ₀ and the object point P = (x _p , y _p , z _p ) . k _p is a constant which satisfies the line equation. The coordinate of the point P ₁ becomes:

x ,= ^{xa +k} p( ^x P ^~x °) y,= y _a +k _p [y _p -y _a ), (18)

where k = ^ι { ^χ o- ^χ M ^m {yo-y<.) ⁺ⁿ { ^z o- ^z a) ₍₁₉₎

^P ι{ ^χ _P - ^χ _a y™{ ^y _P - ^y _a YA ^z p - ^z _° ) [00038] Now, we have all the coordinate information for the center point C ₀ and the object image point P ₁ . A line through these two points is: x — x v— y z — z

(20) m.. where x. -*„ l. =

J(χ,-χ.) ² + (y.-y ₀ ?+(z,-z ₀ ? m = ^■ yy,,--yy _oo (21)

J( ^χ ,- ^χ _o ) ² +Cy _l -y _o ?+(z,-z _o ?

Z -Z _n

",„= ^•

J( ^X ₁ - ^X ₀ ) ² + (y,-y _o ) ² +( ^Z ₁ - ^Z ₀ ) ²

[00039] The line equations for L _x and L _y will give the values of the angles θ and φ shown in FIGs.4A and 4B. Suppose that the equations of L _x and L _y are:

x-x _~ y-y _o Z-Z _n and (22) nι

X ~ ^x . y -y ₀ Z -Zo (23) h Yl ₁

[00040] The directional cosine of line L _x should be proportional to the directional cosine of a line passing through points C _b and C _c since they are parallel. More precisely the directional cosine, (l _bc ,m _bc ,n _bc ), of a line through points C ₄ and C _c becomes

/ ^X b - ^X c lbc -

J( ^χ _b - ^χ _c ) ² +(y _b -y _c ) ² + (z _b -z _c ) ² m _bc = , * ^Λ . ■ (24)

Ji?6- ^X c) ^{2 +} Cy ₀ -Vc? +(z.-*c?

J( ^χ _b - ^χ _c ) ² +(y _b -y _c ) ² +(z ₀ -z _c Ϋ [00041] We then have/, =kl _bc ,m^ =km _bc , and «, =kn _bc for a certain constant k The equation of line L _x can be rewritten as:

^X - ^X ₀ y-y _o ^z~z o (25) lbc m be n be

[00042] To obtain the directional cosine of L _y we have two equations: hhc + ^m 2 ^m bc + ⁿ 2 ⁿ bc = 0 » (26) since Z, _L L _y , and

I ₂ I + m ₂ m + n ₂ n = 0, (27)

since Z^ is on the plane 350. This system of equations yields the following solution for the directional cosine of L _y : I ₂ =h m ₂ =h. ⁿ - ^l *- ^l - ⁿ * (28) m-n _bc -m _bc -n

m - "bc ~ ^m bc ^{■ n} for a constant h. The equation of line L _v becomes x- x ~ y-y ₀ z-z,.

(29) m-n _bc -n-m _bc ⁿ - ^l bc - ^l - ⁿ bc l-m _bQ -m-l _bc

[00043] The directional cosine of L can be rewritten as:

_ m n _bc -n-m _bc

V( ^{w • n} bc - ^{n ■ m} bcf + ( ⁿ - ^l bc ^~l - ⁿ bc) ² + V ^{■ m} bc -m-hcΫ

τj(m ■n _bc -n-m _bc γ ^■ ¥{n-l _bc -l-n _bc ) ² +{l-m _bc -m-l _bc f [00044] Let line Z ₇₀ be defined by the two points C ₀ and P ₁ . Then, the angles between L _x and L ₁₀ becomes φ = arccos(/,/, ₀ + m _} m _ι0 + n.nj . (31) The angle θ, between L _y and L ₁₀ is

θ = arccos(/ ₂ /, ₀ + m ₂ m, ₀ + n ₂ n _ι0 ) . (32)

[00045] Since /, h, and v are readily available, the angles δ _h and δ _v can be derived as:

δ _h = arctan — , and (33)

δ _v = arctan ( —A . (34)

[00046] The ratios θ/δ _v and φ/δ _h are sufficient to determine, respectively, the relative vertical and horizontal positions of the object image point P ₁ on the screen

350. This is shown in FIG. 4D.

[00047] Once the coordinates of the object within the camera image have been determined, as described above, this information along with any other relevant information that may be desired, is recorded, as discussed above with reference to FIG. 2.

[00048] The present invention can be used in a variety of applications. Consider an illustrative application of the present invention in which a movie studio is filming a scene in Central Park in which the main actor and actress are sitting on a bench. A sponsor of the movie is a well-known fashion company that wants to advertise a new handbag held by the actress on her lap. The fashion company wants to provide a direct link to their online shop if a viewer moves the pointer, available with an interactive TV set, to the proximity of the handbag. At the time of filming, a Bluetooth radio device, or the like, is placed inside the handbag. Four radio antennas placed around the bench receive the radio signals from the Bluetooth device and send it to a laptop computer. Simultaneously, the video camera sends frame numbers to the laptop computer where the concurrently generated object position and frame numbers are associated and stored in a database. The present invention allows the producer to build a database of all the necessary information regarding the location of the object (i.e., handbag) in the video screen, its identity, and the frame number. Advantageously, this can be done without human intervention or error-prone image recognition technologies. The trilateration positioning device, video camera, and computer can communicate over wired or wireless connections. [00049] The present invention provides accurate means of object tracking and tagging in real time for interactive TV applications, streaming video, or the like. This eliminates time consuming and/or error-prone post processing steps involved in locating objects in the video. It is a useful tool for a variety of applications such as advertising and marketing in interactive video. Additionally, the present invention can help advertisers track the amount of time that their products are seen on the screen, and provide other useful information.

[00050] Note that while the apparatus and methods of the present invention are most advantageously used in conjunction with video or moving images, the present invention can just as readily be applied to still imaging as well, where individual images are captured.

[00051] It is understood that the above-described embodiments are illustrative of only a few of the possible specific embodiments which can represent applications of the invention. Numerous and varied other arrangements can be made by those skilled in the art without departing from the spirit and scope of the invention.