Method and system for tracking attitude

CROSS REFERENCE TO RELATED APPLICATION(S)

0001This is a continuation of copending application Ser. No. 09/022,097 filed on Feb. 11, 1998 now Pat. No. <b>6,175,357 which is a divisional application of Ser. No. 08/540,355 filed Oct. 6, 1995, now U.S. Pat. No. 5,786,804</b>.

TECHNICAL FIELD

0002The invention relates generally to methods and systems for tracking attitude of a device and more particularly to tracking the attitude of a device in order to control a device or process, such as a cursor of a video display.

BACKGROUND ART

0003A device may be used to control the cursor of a video display.

0004There are applications in which video systems require that a person interact with information presented on a display screen. At times, the interaction is to occur while the person is situated at a distance from the display screen. As will be described more fully below, the interaction may be accomplished by remotely controlling a screen cursor in one of a variety of manners. The interactions may include selecting from a variety of choices presented as a screen menu, or “typing” text using an on-screen keyboard. Examples of remote interactive video systems (RIVS) include interactive television (ITV), TV-style Internet browsers, and conference-room video projectors.

0005One key component of a RIVS is the “pointing” device for controlling the on-screen cursor. The pointing device fulfills a function analogous to that which mice, trackballs, and graphic tablets perform for computers. However, the environment for RIVS presents difficulties that are typically not encountered in operation of a computer. For example, an operator of a RIVS is typically further away from the controlled device than is the operator of a computer. As another example, the operator of a RIVS is more likely to be in an unstructured immediate environment, e.g., an ITV operator seated across a living room from a television set. In many situations, the environment precludes use of conventional computer pointing devices, such as mice. Moreover, a RIVS is rarely equipped with a keyboard, so that the pointing device may have to accommodate the extra burden of providing a text entry.

0006There are a number of known pointing devices for a RIVS. Most of the known pointing devices implement some variation of a four-key cursor pad on a hand-held controller. The four-key cursor pad is manipulated to step the screen cursor up, down, left or right among various menu choices. Such interfaces emulate the computer keyboard cursor keys used with old-style textural interfaces. However, these interfaces are typically much slower and less intuitive to use than computer mice and other pointing devices developed for modern graphical software interfaces.

0007In an effort to improve upon cursor control within the RIVS environment, more advanced computer pointing devices of mice and trackballs have been adapted. In one adaptation, a miniature trackball is mounted atop a controller, with the trackball being operated by the person's thumb. The trackball controller is faster than the use of cursor keys and facilitates diagonal moves. Unfortunately, the trackball may require repeated strokes to accomplish large cursor movements and, in general, thumb control taxes the user's thumb dexterity. For example, it is difficult to trace the cursor in a circle on the display screen.

0008The use of a mouse for ITV cursor control has been demonstrated. The advantage of the mouse is that it provides excellent and intuitive cursor control. The concern is that there may not be a suitable planar operating surface that is convenient to the operator.

0009A further refinement in the RIVS pointing art is the use of devices that enable control of a cursory by merely gesturing with a controller. These devices may measure the attitude, i.e. pitch, yaw, and possibly roll, of the controller. A first category of such an approach employs light beams to measure attitude. PCT International Publication Number WO 95/19031 describes a system for determining the pointing orientation of a remote unit relative to a fixed base unit. The fixed base unit includes one or more light sources for emitting a light beam. The emitted light is polarized in at least one predetermined orientation. The movable remote unit includes a photodetector for detecting the polarized emitted light. The attitude of the movable remote unit may be determined by measuring the intensity of received light from various directions.

0010Another implementation of the emitted-light category of measuring attitude is one in which an infrared (IR) signal is beamed from the area of the video display. The IR signal is defocused and is imaged onto a quad photodiode array in the controller. The relative signal amplitudes from the four photodiodes may be used to determine the relative orientation of the controller to a line drawn from the display. One concern is that the system may undesirably flood the room with intense IR, rendering other nearby IR-coupled appliances (e.g., a VCR controller) inoperative. A second concern is that the limited range of transmission of defocused IR signals may render this system of measuring attitude unreliable when the controller is more than a relatively short distance from the video display.

0011A second category of devices that measure attitude of the controller is one in which inertial navigation principles are employed. Gyroscopes or encoded gimballed masses establish inertial frames in the controllers, against which attitude changes can be measured. The attitude information may then be transmitted to the video display via a radio-frequency link to a small dipole antenna affixed atop the video display.

0012The third category is related to the first category. A hand-held object that provides cursor control has a number of light sources mounted on one surface. A single electronic camera is directed to capture images of the light sources mounted on a hand-held object. Locations of the images of the light sources are detected in each camera image, and a computer is used to determine the attitude of the light-emitting hand-held object. Such a device is described in U.S. Pat. No. 5,338,059 to DeMenphon.

0013A closely related need exists in the field of virtual reality. In games, simulations, and other visualization situations, it is often necessary to encode the attitude of a user's head, or other body part. In many cases, systems for encoding head pitch and yaw may be applied to RIVS controllers, and vice versa. One known virtual reality system encodes pitch and yaw by means of instrumented compasses and gravimeters.

0014While the known cursor control devices and attitude-determining systems operate adequately for their intended purposes, each is associated with a concern or a problem. Operation may be slow or tedious, or may require use of a specific operating surface. Devices and systems that include IR radiation may adversely affect operation of other devices. Attitude-sensing devices that are based on gravity may have difficulty in distinguishing tilting from traverse acceleration, thereby rendering control erratic. This last problem conceivably could be solved by gyro stabilization, but the cost and power consumption make this solution unattractive. Known systems that utilize light detection require adding a second contrivance at the display, again adding additional cost.

0015What is needed is a method and a system for reliably tracking attitude of a device. What is further needed is such a method and system that is cost efficient when used in controlling a screen cursor or when used in other remote interactive video applications.

SUMMARY OF THE INVENTION

0016An arrangement of a sensor and optics includes an array of photosensors, and a lens system for providing a focus for imaging by said array, said lens system having a characteristic of introducing curvilinear distortion of an image to the array, the array having a shape to achieve compensation of the curvilinear distortion, including having arcuate edges to establish said compensation, wherein the photosensors are disposed in a plurality of columns and a plurality of rows and wherein the photosensors combine to define an optical axis for the array, adjacent columns being spaced apart by an arcuate boundary, with curvatures of the arcuate boundaries increasing with departure from the optical axis.

0017<i>An arrangement of a sensor and optics includes a two</i>-<i>dimensional array of photosensors and a lens system for providing a focus for imaging by the array, the lens system having a characteristic of optically introducing curvilinear distortion of an image to the array, the array having a curvilinear shape to achieve compensation of the curvilinear distortion, including having a plurality of arcuate outer edges to establish the compensation, the photosensors being varied dimensionally to define the curvilinear shape, the curvilinear shape being aligned relative to the curvilinear distortion to introduce a physical distortion that offsets the optically introduced curvilinear distortion, wherein the photosensors are disposed in a plurality of columns and a plurality of rows and wherein the photosensors combine to define an optical axis for the array, adjacent columns being spaced apart by an arcuate boundary, with curvatures of the arcuate boundaries increasing with departure from the optical axis. </i>

0018<i>A movable device includes a housing, a lens system in the housing and an array of photosensors in the housing for acquiring images in light applied to the array by the lens system, the array disposed in a plurality of rows and columns defining an optical axis, adjacent columns being spaced apart by boundaries having curvatures increasing with departure from the optical axis sufficient to compensate for curvilinear distortion introduced in the images by characteristics of the lens system, the array comparing data from the images to indicate motion of features of the images relative to the housing.</i>

0019Correlation of successive images acquired by means of a two-dimensional array of photosensors is used as a basis for tracking attitude of a device to which the array is affixed. In the preferred embodiment, the device is a hand-holdable member, such as a controller for maneuvering a cursor on a display screen of a video set. Based upon the step of correlating images to detect differences in location of imaged features that are common to a succession of images, the system generates an attitudinal signal indicative of any changes in angular orientation during the time period of acquiring the images. That is, the attitudinal signal is determined by the pitch and yaw, and optionally the roll, of the device that bears the array of photosensors. Since the acquired images need not be related to that which is being controlled, e.g. a screen cursor, the device can face in any direction during the control process. Moreover, it is not necessary to provide a dimensional one-to-one correspondence of angular displacement of the device and travel of that which is being controlled. Within cursor control, for example, the controller may be directed arbitrarily and relationships of degrees of pitch and yaw to lengths of cursor movement may be user-adjustable.

0020The two-dimensional array of photosensors is used to acquire a reference frame for tracking the attitude of the device. The reference frame is stored and a second image of features within a field of view of the array is acquired. The second image may be considered to be a sample image, and the fields of view of the two images should be largely overlapping, so that the reference and sample frames include a number of common features. While not critical, the device includes optics which provide a focus nominally at infinity, intentionally presenting an off-sharp image to the array of photosensors. In the application of the device for controlling a screen cursor, the representative imaged features will typically include windows, lamps, furniture and the display screen itself. In any application of the invention, one or more stationary sources of light may be specifically added within the environment to be imaged, so that successive images of the fixed light are used for the purpose of correlation. In one implementation of such an embodiment, the source of light is an IR emitter and the imaging array on the device is provided with IR filtering to permit tracking of the attitude of the device.

0021Conceptually, the step of correlating the reference frame with a sample frame is one in which one of the frames is fixed in position and the other frame is repeatedly shifted to determine which shifted position best approximates an alignment of the imaged features that are common to the two frames, thereby allowing the determination of the pitch and yaw of the imaging array during the interval between acquiring the two frames. In practice, the shifts are performed computationally and are shifts of pixel values in which each pixel value is indicative of light energy received at a particular photosensor at a specific time. The correlations may be limited to computational shifts of only one pixel for nearest-neighbor correlations, or may be multi-pixel computational shifts. The nearest-neighbor correlation process if often preferred, since it is less computationally complex, with only the original position and eight computational shifts being necessary. Interpolations are then performed to determine angular displacements that are less than a full pixel. Angular displacement of the device about a horizontal axis, i.e. pitch, will result in the arrangement of pixel values of the reference frame being moved upwardly or downwardly. Angular displacement of the device about a vertical axis, i.e. yaw, will result in the pixel value arrangement being moved to the left or to the right. The system detects pitch, yaw and combinations of pitch and yaw. The attitudinal signal that is generated by the system is responsive to the detection of such angular displacements. Optionally, roll may also be considered.

0022In the application in which the attitudinal signal is generated in order to control a screen cursor, the device preferably includes a transmitter for wireless transmission of a cursor-control signal. For example, the signal may be transmitted via an infrared beam. Changes in the pitch of the hand-holdable device are then translated into vertical movements of the screen cursor, while changes in device yaw will move the screen cursor laterally. In this embodiment, translational movement of the device may also be detected and utilized, so that vertical or horizontal movement of the device translates to a corresponding vertical or horizontal movement of the screen cursor.

0023One concern in the implementation of the method and system is the effect of the phenomena known in the lens design as curvilinear distortions. Curvilinear distortions are also referred to as pin-cushion, barrel, and perspective distortions. Rectilinear detail is compressed at the outer edges of the field by such distortion. Curvilinear distortion is particularly pronounced in simple lenses with wide fields of view, such as the lens contemplated for use with the present invention. In the invention, the field of view is preferably approximately 64°, so that curvilinear distortions will inevitably occur.

0024In the preferred embodiment, the photosensors of the array vary dimensionally in order to define an array that is curvilinear, i.e., includes an arcuate outer edge. The curvilinear array is dimensioned to compensate for the curvilinear distortion introduced by the lens system. The imaging by the optics is evaluated to characterize the curvilinear distortion, with the array then being patterned to offset the distortion. In this manner, the arrangement of the photosensor array and the optics greatly reduces adverse effects of curvilinear distortion.

0025An advantage of the invention is that device attitude may be tracked in a reliable and cost-efficient manner. For those applications in which the array-bearing device is a hand-holdable device, control of a screen cursor or the like is economically achieved without a premium on dexterity. Moreover, the device does not require operation on a suitable surface.

BRIEF DESCRIPTION OF THE DRAWINGS

0026FIG. 1 is a perspective view of a hand-holdable device that enables attitude tracking of the device, in accordance with the invention.

0027FIG. 2 is a block diagram of components for controlling a screen cursor in accordance with the invention.

0028FIG. 3 is a block diagram of an array of photosensors and transfer amplifiers of the correlator of FIG. 2.

0029FIG. 4 is an operation view of the steps for correlating successive images in accordance with the invention.

0030FIG. 5 is a conceptual view of the steps of FIG. 4.

0031FIG. 6 is an embodiment of a computation cell of an array of cells for carrying out the steps of FIG. 4.

0032FIGS. <b>7-11 </b>illustrate arrays of photosensors and computation cells for demonstrating and then reducing curvilinear distortions.

id="DEL-S-00020" date="20080701"

BEST MODE FOR CARRYING OUT THE INVENTION

id="DEL-S-00020"

id="INS-S-00005" date="20080701"

DETAILED DESCRIPTION OF PREFERRED EMBODIMENT(

S

)

0033<i>Correlation of successive images acquired by means of a two</i>-<i>dimensional array of photosensors is used as a basis for tracking attitude of a device to which the array is affixed. In the preferred embodiment, the device is a hand</i>-<i>holdable member, such as a controller for maneuvering a cursor on a display screen of a video set. Based upon the step of correlating images to detect differences in location of imaged features that are common to a succession of images, the system generates an attitudinal signal indicative of any changes in angular orientation during the time period of acquiring the images. That is, the attitudinal signal is determined by the pitch and yaw, and optionally the roll, of the device that bears the array of photosensors. Since the acquired images need not be related to that which is being controlled, e.g. a screen cursor, the device can face in any direction during the control process. Moreover, it is not necessary to provide a dimensional one</i>-<i>to</i>-<i>one correspondence of angular displacement of the device and travel of that which is being controlled. Within cursor control, for example, the controller may be directed arbitrarily and relationships of degrees of pitch and yaw to lengths of cursor movement may be user</i>-<i>adjustable. </i>

0034<i>The two</i>-<i>dimensional array of photosensors is used to acquire a reference frame for tracking the attitude of the device. The reference frame is stored and a second image of features within a field of view of the array is acquired. The second image may be considered to be a sample image, and the fields of view of the two images should be largely overlapping, so that the reference and sample frames include a number of common features. While not critical, the device includes optics which provide a focus nominally at infinity, intentionally presenting an off</i>-<i>sharp image to the array of photosensors. In the application of the device for controlling a screen cursor, the representative imaged features will typically include windows, lamps, furniture and the display screen itself. In any application of the invention, one or more stationary sources of light may be specifically added within the environment to be imaged, so that successive images of the fixed light are used for the purpose of correlation. In one implementation of such an embodiment, the source of light is an IR emitter and the imaging array on the device is provided with IR filtering to permit tracking of the attitude of the device. </i>

0035<i>Conceptually, the step of correlating the reference frame with a sample frame is one in which one of the frames is fixed in position and the other frame is repeatedly shifted to determine which shifted position best approximates an alignment of the imaged features that are common to the two frames, thereby allowing the determination of the pitch and yaw of the imaging array during the interval between acquiring the two frames. In practice, the shifts are performed computationally and are shifts of pixel values in which each pixel value is indicative of light energy received at a particular photosensor at a specific time. The correlations may be limited to computational shifts of only one pixel for nearest</i>-<i>neighbor correlations, or may be multi</i>-<i>pixel computational shifts. The nearest</i>-<i>neighbor correlation process is often preferred, since it is less computationally complex, with only the original position and eight computational shifts being necessary. Interpolations are then performed to determine angular displacements that are less than a full pixel. Angular displacement of the device about a horizontal axis, i.e. pitch, will result in the arrangement of pixel values of the reference frame being moved upwardly or downwardly. Angular displacement of the device about a vertical axis, i.e. yaw, will result in the pixel value arrangement being moved to the left or to the right. The system detects pitch, yaw and combinations of pitch and yaw. The attitudinal signal that is generated by the system is responsive to the detection of such angular displacements. Optionally, roll may also be considered. </i>

0036<i>In the application in which the attitudinal signal is generated in order to control a screen cursor, the device preferably includes a transmitter for wireless transmission of a cursor</i>-<i>control signal. For example, the signal may be transmitted via an infrared beam. Changes in the pitch of the hand</i>-<i>holdable device are then translated into vertical movements of the screen cursor, while changes in device yaw will move the screen cursor laterally. In this embodiment, translational movement of the device may also be detected and utilized, so that vertical or horizontal movement of the device translates to a corresponding vertical or horizontal movement of the screen cursor. </i>

0037<i>One concern in the implementation of the method and system is the effect of the phenomena known in the lens design as curvilinear distortions. Curvilinear distortions are also referred to as pin</i>-<i>cushion, barrel, and perspective distortions. Rectilinear detail is compressed at the outer edges of the field by such distortion. Curvilinear distortion is particularly pronounced in simple lenses with wide fields of view, such as the lens contemplated for use with the present invention. In the invention, the field of view is preferably approximately <b>64</b>°, so that curvilinear distortions will inevitably occur. </i>

0038<i>In the preferred embodiment, the photosensors of the array vary dimensionally in order to define an array that is curvilinear, i.e., includes an arcuate outer edge. The curvilinear array is dimensioned to compensate for the curvilinear distortion introduced by the lens system. The imaging by the optics is evaluated to characterize the curvilinear distortion, with the array then being patterned to offset the distortion. In this manner, the arrangement of the photosensor array and the optics greatly reduce adverse effects of curvilinear distortion. </i>

0039<i>An advantage of the invention is that device attitude may be tracked in a reliable and cost</i>-<i>efficient manner. For those applications in which the array</i>-<i>bearing device is a hand</i>-<i>holdable device, control of a screen cursor or the like is economically achieved without a premium on dexterity. Moreover, the device does not require operation on a suitable surface.</i>

0040With reference to FIG. 1, a hand-holdable controller device <b>10</b> is shown as including an integrated circuit package <b>12</b> for acquiring and processing image data. On the surface of the package is an optoelectric integrated circuit chip <b>14</b> having a two-dimensional array <b>16</b> of photosensors and having processing circuitry <b>18</b>. The array and processing circuitry are used to acquire successive frames of image data, permitting the attitude of the device to be tracked. Thus, angular displacement about a horizontal axis <b>20</b>, i.e. pitch, and angular displacement about a vertical axis <b>22</b>, i.e. yaw, can be determined. Optionally, roll about the longitudinal axis <b>24</b> of the device <b>10</b> can also be monitored.

0041The invention will be described primarily with reference to providing control of a remote element, such as controlling a screen cursor of a video display. However, it is understood that the approach of a tracking attitude by means of correlating images formed by a photosensor array attached to the device has applications beyond that of controlling a screen cursor or the like.

0042The sensor array <b>16</b> and the processing circuitry <b>18</b> are mounted on the front of the controller device <b>10</b> with the array facing outwardly. A lens <b>26</b> is shown in FIG. 1 as being partially cutaway in order to expose the array and circuitry. The lens may be an inexpensive plastic lens that is molded to the integrated circuit package <b>12</b>. The focus of the lens is set nominally at infinity. The lens provides an image of a region of the surrounding environment to the sensor array <b>16</b>. A short focal-length lens is preferred, since a greater number of features within the environment will be imaged and used for the purpose of tracking attitude. The image quality demands are sufficiently lax, such that the demands on the optical arrangement are not stringent. In fact, a slight blurring is desirable, so that the spatial frequencies of the image are coarser than the size of the array elements.

0043The width of the field of view for imaging the environment is a matter of balancing the desire of capturing as much visible detail as possible with the requirement of avoiding excessive distortion. A 64° field of view provides a reasonable compromise between these two concerns. The dashed lines <b>28</b> in FIG. 1 represent the field of view for the sensor array <b>16</b>. The arrangement of the optics and the sensor array may be selected to reduce any adverse effects of curvilinear distortion on the attitude-tracking approach of the invention. The optic/sensor arrangement will be described in greater detail below.

0044On the top surface of the controller device <b>10</b> are a cursor control key <b>30</b> and a return key <b>32</b>. In operation, the screen cursor of a video display may be captured by depression of the control key <b>30</b>. With the control key in a depressed position, the angular displacement of the device <b>10</b> will be translated into movement of the cursor along the display screen. For example, in selecting a particular movie from a menu of movies presented by an interactive television system, key <b>30</b> is depressed and pitch and/or yaw of the device <b>10</b> is employed to drag the screen cursor to the desired movie. The control key <b>30</b> is then released to release control of the screen cursor. With the cursor indicating the desired menu choice, the return key <b>32</b> is depressed to activate the selection. Alternatively, a single selection key similar in operation to that of a computer mouse may be utilized, so that cursor control is continuously enabled.

0045Remote communication is provided by infrared transmission via an emitter <b>34</b>. Infrared emission is well known in the art. For cursor control, signal vectors are generated and transmitted. The vectors are sent as increments in order to reduce the burden of the IR communications channel by keeping the data bytes shorter. The rate at which vectors are transmitted should be sufficiently fast to achieve the necessary cursor responsiveness, but not so fast as to tax the limited bandwidths of the IR link to the controlled set. As will be explained more fully below, in one embodiment the transmission is a 10-bit word that is emitted every 40 ms, as needed. When neither of the keys <b>30</b> and <b>32</b> is depressed, no transmission occurs. This frees the IR emitter for other functions during non-cursor events. Thus, the controller device <b>10</b> may include keys to control other events, such as the changing of a television channel.

0046Referring now to FIGS. 1 and 2, a control clock <b>36</b> determines the timing of operations for the controller device <b>10</b>. The image-capture rate is at least partially determined by the features that are to be imaged. Where the field of view <b>28</b> is a living room of a person engaged in operation of an ITV system, the image capture rate must be sufficiently great to ensure that the image data is sufficiently intelligible to permit correlation between successive images. The circuitry of FIG. 2 includes an exposure control <b>38</b> which shows a minimum exposure of 5 μs and a maximum exposure of 5 ms. Electronically, the “exposure time” is the interval during which charge generated by the individual photosensors is allowed to integrate during the 5 ms period between successive image captures. While the exposure control may be manually adjusted, the preferred embodiment is one in which there is a feedback line <b>40</b> from image correlator circuitry <b>42</b> to establish automatic gain control. Thus, if the image data is consistently off-scale for performing correlation processing, the exposure control <b>38</b> increases the interval for integrating charge by the photosensors.

0047As previously noted, the field of view <b>28</b> is contemplated to be approximately 64°. In a sensor array of 32×32 photosensors, a single pixel will have an approximately 2° field of view (64°/32 pixels). In the preferred embodiment to be described below, correlations are limited to nearest-neighbor pixel cells. This establishes a maximum velocity for movement of the controller device <b>12</b>. In the preferred embodiment, the maximum velocity should not exceed one pixel length between successive image captures. If a frame of image data is to be acquired at the correlator <b>42</b> every 5 ms, the maximum velocity will be 200 pixels per second. Since the field of view of each pixel is 2°, the maximum velocity is 400° per second.

0048The operation of the correlator <b>42</b> will be explained in detail below. Its basic function is to compare the arrangement of pixel values in a first frame of image data to the location of a similar arrangement in a subsequent frame. The sensor array <b>16</b> is used to acquire a frame of 32×32 pixel values. The first captured frame is referred to as a reference frame. The first reference frame is captured upon depression of the cursor control key <b>30</b> of FIG. 1. A subsequently captured frame of pixel values, referred to as a sample frame, is compared with the reference frame to detect changes in attitude of the controller device <b>10</b>. A new reference frame is then acquired. The reference frame may be replaced by the sample frame after each correlation. Alternatively, the reference frame may be replaced with a sample frame each time a threshold is reached, such as a time threshold or a threshold based upon movement of the device.

0049Correlation will be described in detail below. Conceptually, the process may be considered as fixing the two-dimensional reference frame in position and shifting a transparency of the two-dimensional sample frame to various positions atop the reference frame in order to detect alignment of common features of the two frames. This conceptual view is shown in FIG. 5 and is computationally carried out by an array of cells such as the pixel cell shown in FIG. 6.

0050The correlation processing generates an attitudinal signal indicative of any changes in angular orientation of the controller device <b>10</b>. In FIG. 2, the correlator <b>42</b> is shown as generating a signal in which change along the X axis is +0.75 pixels, while the change along the Y axis is −0.31 pixels. In FIG. 1, positive movement along the X axis may be indicated as a result of angular displacement of the device <b>10</b> such that the field of view <b>28</b> is moved in the direction of arrow <b>44</b>, while a negative movement along the X axis is one in which a component of displacement of the field of view <b>28</b> is in the direction indicated by arrow <b>46</b>. Regarding the Y axis, a positive value at the attitudinal signal indicates manipulation of the device <b>10</b> to rotate the field of view as shown by arrow <b>48</b>, while a negative value of ΔY indicates displacement in the direction shown by arrow <b>50</b>.

0051The preferred approach for operation of the correlator <b>42</b> is one in which nearest-neighbor pixel shifts are executed in order to track changes in attitude of the controller device. This approach will be detailed when referring to FIGS. 4, 5 and 6. However, the attitude tracking alternatively may be carried out using correlations requiring shifts of greater than a single pixel. For either approach, interpolations are computationally performed to identify fractional pixel values. Such image correlating interpolating is well understood by persons skilled in the art.

0052The output from the correlator <b>42</b> is received at a multiplier <b>52</b> that increases the sensitivity of the cursor control. In the embodiment of FIG. 2, the multiplier doubles the ΔX and ΔY values from the correlator. The signal is then conducted to an accumulator <b>54</b>. A divide-by-eight circuit <b>56</b> dictates operation of the accumulator <b>54</b>. Eight samples will be received from the multiplier <b>52</b> before the accumulator outputs a sample to a modulo function block <b>58</b>. The output of the modulo block will be the integer portion of the accumulation of the eight samples from the multiplier <b>52</b>. As previously noted, the controller device transmits a cursor control signal by means of an IR emitter <b>34</b>. IR transmission links have limited bandwidth. The use of the accumulator <b>54</b> reduces the demands on the communications link.

0053The exemplary sample from the accumulator <b>54</b> in FIG. 2 is shown to be one in which ΔX=+15.2 pixels and ΔY=−3.3 pixels. The modulo block <b>58</b> passes only the whole numbers to a pulse code modulator <b>60</b>. Each of the ΔX and ΔY values is contained within 5 bits, with 4 bits relating to the numerical value and the remaining bit relating to whether the numerical value is positive or negative.

0054The values output from the modulo block <b>58</b> to the modulator <b>60</b> are whole number values, while the remainder of the sample from the accumulator <b>54</b> is conducted to a residue circuit <b>62</b>. The residue values are saved at the residue circuit and added to subsequent values from the accumulator.

0055The remaining arrangement of components is well known in the art. A 10-bit word is output from the pulse code modulator <b>60</b> to an amplifier <b>64</b> every 40 ms. Thus, the IR transmission from the emitter <b>34</b> is only 25 words per second. The IR transmission is received by a sensor <b>66</b> of a display system, such as a RIVS. The signal from the IR sensor <b>66</b> is decoded at a demodulator <b>68</b> and transmitted to a cursor control circuit <b>70</b> for manipulating a screen cursor of a video screen <b>72</b>. Merely for example, the screen may have 64×64 cursor addresses and the screen cursor may move 15×25=375 address states/second. In the example given above in which the field of view <b>28</b> of FIG. 1 is 64°, the screen can be traversed in 0.17 second (64/375).

0056The arrangement and interaction of the components of FIG. 2 permit cursor control based upon tracking of the attitude of the controller device <b>10</b> of FIG. 1. The controller encodes the device pitch, yaw and optionally roll by tracking the apparent motion of an image of the environment in which the device resides. It is not necessary to point the controller-in any one direction, other than to establish the IR link between the emitter <b>34</b> and the sensor <b>66</b>. With the possible exception of the correlator <b>42</b>, the individual components of FIG. 2 are readily understood by persons skilled in the art and need not be explained in detail. However, the preferred embodiment of the correlator <b>42</b> will be set forth below. The preferred arrangement of the two-dimensional sensor array <b>16</b> and the optics <b>26</b> will also be set forth.

Column Transfers of Photosensor Signals

0057As previously noted, the embodiment of FIGS. 1 and 2 includes a sensor array <b>16</b> having thirty-two columns and thirty-two rows of photosensors. Referring now to FIG. 3, five columns <b>74</b>, <b>75</b>, <b>76</b>, <b>77</b> and <b>78</b> of the thirty-two columns of photosensors are shown. Also shown are six of the thirty-two rows <b>79</b>, <b>80</b>, <b>81</b>, <b>82</b>, <b>83</b> and <b>84</b>. Each column is operatively associated with a separate transfer amplifier <b>85</b>. A photosensor in a column is connected to the operatively associated transfer amplifier for closing a read switch <b>86</b>. In the operation of the circuitry of FIG. 3, no two photosensors are connected to the same transfer amplifier simultaneously.

0058Each transfer amplifier <b>85</b> includes an input <b>87</b> that is connected to a source of a fixed voltage. A second input <b>85</b> is capacitively connected to the output <b>90</b> of the transfer amplifier by a transfer capacitor <b>89</b>.

0059In the operation of the circuit of FIG. 3, the read switches <b>86</b> of the first row <b>79</b> of photosensors may be closed, so that each transfer capacitor <b>89</b> receives a charge corresponding to the light energy at the associated photosensor in the first row. Thus, the transfer amplifiers <b>85</b> and the transfer capacitors <b>89</b> function as integrators. The received charge is transferred to subsequent processing circuitry via the output lines <b>90</b>. Following the readout of the first row, the read switches of the first row are opened and the transfer amplifiers are reset. The read switches of the second row <b>80</b> are then closed in order to transfer the signals from the photosensors of the second row. The process is repeated until each row of photosensors is read. By the operation of the transfer amplifiers <b>85</b>, photosensor signals are transferred in a row-by-row fashion to subsequent circuitry.

Correlation Processing

0060FIG. 4 illustrates steps for carrying out the correlation processing for tracking attitude of a device. In effect, the correlations compare the positions of imaged features in successive frames to provide information related to changes in angular orientation during time intervals between frames. In a first step <b>200</b>, a reference frame is acquired. As noted above, the capture of the reference frame may be initiated by depression of the cursor control key <b>30</b> on the upper surface of the device <b>10</b> of FIG. 1. The row-by-row transfer of signals from the photosensors continues until each photosensor in the array <b>16</b> has been read. The reference frame is a frame of 1,024 pixel values (32×32=1,024).

0061While the tracking of the attitude of the controller device <b>10</b> is performed computationally, the concepts of the correlation may be described with reference to FIGS. 4 and 5. A reference frame <b>202</b> is shown as having an image of a T-shaped feature <b>204</b>. The image feature may be a window in a room of a person operating an ITV system. At a later time (dt) the sensor array <b>16</b> of FIGS. <b>1-3 </b>is used to acquire a sample frame <b>206</b> as shown in FIG. 5. The field of view <b>28</b> of the controller device during acquisition of the sample frame largely overlaps the field of view at the time of acquiring the reference frame <b>202</b>. As a result, the imaged feature <b>204</b>, e.g. a window, is included within both of the frames. The duration dt and the velocity of the movement of the device preferably are such that the common features <b>204</b> will move less than one pixel from the reference frame to the sample frame. The schematic representation of FIG. 5 shows the feature as having shifted upwardly and to the right by one full pixel. The full-pixel shift is assumed only to simplify the representation.

0062FIG. 4 shows the step <b>208</b> of acquiring the sample frame after the step <b>200</b> of acquiring the reference frame. A computation step <b>210</b> is then executed. The correlation step is a shifting of the arrangement of the pixel values of the sample frame <b>204</b> and two nearest-neighbor pixel cells. The shifting is performed sequentially for each of eight nearest-neighbor pixel cells, as represented by member <b>212</b> in FIG. 5. Referring to the member <b>212</b>, step “0” does not include a shift of the pixel values in the sample frame <b>206</b>, step “1” is a diagonal shift upwardly and to the left, step “2” is an upward shift of the pixel values of the sample frame, etc. Eight shifts of the reference frame represented by member <b>212</b> occur one at a time, but all pixel values are shifted uniformly. In this manner, the eight pixel-shifted sample frames can be combined with the reference frame <b>202</b> to produce the frame array <b>214</b> of position frames. The position frame designated as “Position 0” does not include a shift, so that the result is merely a combination of frames <b>202</b> and <b>206</b>.

0063Within the frame array <b>214</b>, “Position 7” has the highest correlation. Based upon the correlation results, the position of the T-shaped feature <b>204</b> in the sample frame <b>206</b> is determined to be an upward and right-ward shift relative to the position of the same feature in the earlier-acquired reference frame <b>202</b>. The movement of the features is a result of a combination of pitch and yaw of the controller device <b>10</b> of FIG. 1, with components indicated by the leftward arrow <b>44</b> and the downward arrow <b>50</b>.

0064While other correlation approaches may be employed, an acceptable approach is a “sum of the squared differences” correlation. For the embodiment of FIGS. 4 and 5, there are nine correlation coefficients (C_k=C₀, C₁. . . C₈) formed from the nine offsets of <b>212</b>.

0065Correlations are used to find the locations of common features <b>204</b> of successive frames <b>202</b> and <b>206</b> in order to track the angular orientation of the controller device <b>10</b>. Summing or integrating angular displacements from frame-to-frame allows an attitudinal signal to be generated for controlling a screen cursor.

0066After the correlation step <b>210</b> has been executed for the sample frame acquired at step <b>208</b>, a determination is made at step <b>216</b> as to whether to maintain or replace the reference frame. In some embodiments, the reference frame is not replaced. If the same reference frame is to be used for subsequent correlation computation, the process returns to step <b>208</b> and a new sample frame is acquired. On the other hand, for applications in which there is a substitution of reference frames, step <b>218</b> shows the use of the previously acquired sample frame as a new reference frame prior to returning to step <b>208</b> of acquiring a new sample frame.

0067If the same reference frame is to be used throughout a process of dragging a cursor along a screen, the reference frame can be shifted upon detection that common features have traveled more than one pixel length since the acquisition of the reference frame. Thus, the reference frame is “walked” by detection of pitch, yaw and/or roll of the device. This process provides a high degree of correlation match, but errors that do occur will accumulate if the reference frame is not periodically replaced. Thus, in the preferred embodiment step <b>218</b> is included so as to place a restriction on the growth rate of this “random walk” error.

Computation Cell

0068FIG. 6 is a schematic diagram of an individual pixel cell, or computation cell <b>94</b>, for implementing the nearest-neighbor shifts of member <b>212</b> in FIG. 5 and for carrying out the various steps of FIG. 4. However, as will be understood by persons skilled in the art, other circuits may be used to carry out the process steps described and illustrated with reference to FIGS. 4 and 5.

0069The computation cell <b>94</b> of FIG. 6 is one of an array of computation cells. If there is a one-to-one correspondence of computation cells and photosensors, the embodiment of FIGS. <b>1-3 </b>will have 1,024 computation cells. For the reference frame, the pixel value from the photosensor that corresponds to the particular cell <b>94</b> will be stored at the REFDATA node <b>148</b>, while pixel values of the sample frame will be stored at NN(<b>0</b>) node <b>108</b>. The shifted sample frames for forming the frame array <b>214</b> of FIG. 5 are provided by changing the signal connections to NNINPUT input <b>150</b> of a square-of-the-difference circuit <b>146</b>. The output <b>150</b> of the circuit <b>146</b> is combined with the outputs of the other 1,023 computation cells to track the attitude of the controller device <b>10</b>.

0070Image data WDATA(i) is received from the photosensor that corresponds to the computation cell <b>94</b> at line <b>96</b>, by means of a charge compensate transistor switch <b>98</b> under the control of a WR(j) signal. After the WR(j) signal is deasserted, the new data is held at capacitor <b>100</b> and is buffered by an amplifier <b>102</b>. In the entire array of 1,024 computation cells, the array of CDATA nodes <b>104</b> is collectively referred to as the “reference frame” or the “sample frame,” depending upon the timing of the process. Control input CDOUT <b>106</b> selects signal CDATA, comparison data, or selects REFOUT for the nearest-neighbor output node NN(<b>0</b>) <b>108</b>.

0071The nearest-neighbor inputs NN(<b>0</b>)-NN(<b>8</b>) <b>110</b>, <b>112</b>, <b>114</b>, <b>116</b>, <b>118</b>, <b>120</b>, <b>122</b>, <b>124</b> and <b>126</b> are separately selected by means of switch control signals S(<b>0</b>)-S(<b>8</b>) on lines <b>128</b>. The NN(<b>0</b>)-NN(<b>8</b>) inputs <b>110</b>-<b>126</b> are the outputs of the nearest-neighbor cells according to the data cell map <b>212</b> of FIG. 5. The switch control signals are generated by a 4-9 encoder, not shown, that is external to the computational array. The 4-bit input to the encoder is referred to as the nearest-neighbor address and takes on binary values from 0000(0) to 1000(8).

0072The nearest-neighbor input (NNINPUT) node <b>130</b> is sampled by pulsing REFLD <b>132</b>, thereby storing the NNINPUT on node REFH <b>134</b>. Similarly, REFDATA <b>136</b> can be sampled and held on REFSH <b>138</b> by pulsing REFSFT <b>140</b>.

0073For testing, ROWTSTB <b>142</b> can be asserted, allowing the NN(<b>0</b>) signal to propagate to the TEST output <b>144</b>. The TEST signals from each cell in a row of cells connect to common vertical buses in each column of the computational array and are multiplexed at the bottom of the array and driven off-chip. A standard row decoder along the left edge of the array allows selection of a particular row for test. However, the test feature is not critical to the invention.

0074Each computational cell <b>94</b> has a circuit <b>146</b> that determines correlation values. A first input <b>148</b> receives the reference data from REFDATA node <b>136</b>. A second input <b>150</b> provides the nearest-neighbor input NNINPUT selected by the appropriate switch control signal at lines <b>128</b>. The output <b>152</b> of the correlation cell is a current. All of the correlation outputs in the computational array are summed together in a single off-chip summing resistor of a tracking circuit <b>154</b>. The voltage developed across the summing resistor is referred to as the correlation values in FIG. 4.

0075In the embodiment of FIG. 6, the circuit <b>146</b> is based on a squared-difference calculation. The cell <b>94</b> may be modified to provide product-based correlations without modifying the basic architecture of the array. Control inputs S(<b>0</b>)-S(<b>8</b>), REFLD, REFSFT and CDOUT are global to the entire array, so that the sample frame is manipulated and shifted uniformly within the computation cell array.

0076It is important to understand the relationship between the nearest-neighbor map represented by <b>214</b> in FIG. 5 for a single cell and for the array as a whole. Location <b>0</b> of an image refers to the present location of the image. When referring to the movement of an image from location <b>0</b> to location <b>1</b>, the representation is that the image data in all of the cells of the array are moved to the neighbor cell that is to the left and upward. That is, the movement is relevant to a single cell in the array and is relevant to every cell in the array.

0077The computational array functionality can be best described in terms of four basic operations: image acquisition, reference image load, correlation computation, and reference image translation. The image acquisition refers to the loading of new image data via the WDATA line <b>96</b> of each computation cell <b>94</b>. In the present implementation, every 50 ms a new frame of pixel values is acquired from the sensor array via the column transfer amplifiers. The process of loading a new reference image is referred to as a “frame transfer.” The operations of the computation array described below are coordinated with the frame transfer process by observing and synchronizing with a frame transfer (FTB) signal. The validity of a new sample image is signaled by the falling edge of the FTB signal. The operations described below are only appropriate when FTB is not asserted.

0078Loading a reference frame of pixel values is required before any image correlations can be calculated. To load the reference frame, all of the voltages at the CDATA nodes <b>104</b> in the computational array must be transferred to the REFH nodes <b>134</b>. This is accomplished by setting CDOUT <b>106</b> and S(<b>0</b>) high, and pulsing the REFLD signal on line <b>132</b>. The reference frame can also be loaded from another nearest-neighbor location by asserting one of the S(<b>1</b>)-S(<b>8</b>) inputs instead of S(<b>0</b>). Amplifier <b>156</b> buffers the REFH node <b>134</b> from the REFDATA nodes <b>136</b>. The two-dimensional array of REFDATA nodes <b>136</b> within the computational array are collectively known as the reference frame.

0079After a reference frame has been loaded, the computational array is ready to compute correlations. Correlations between the reference frame of pixel values and the subsequent sample frame are computed by setting the nearest-neighbor address to the desired value and recording the resulting voltage developed across the summing resistor of the attitude tracking circuit <b>154</b>. When the sensor array has moved a single pixel distance from the location at which the reference frame was acquired, a strong correlation will be detected at one of the nearest-neighbor locations. In FIG. 5, the correlation is detected to be at POSITION <b>7</b> in the array <b>214</b>. Sub-pixel movements can be determined by interpolating in two-dimensional correlation space.

0080It should be noted that correlations between the reference frame and itself can be computed by setting CDOUT <b>106</b> low and pulsing REFSFT <b>140</b>. This causes the nearest-neighbor inputs to come from the reference frame, rather than from the sample frame.

0081FIG. 4 referred to the step <b>218</b> of replacing the reference frame. However, the same reference frame may be used for multiple pixel movements by allowing the reference to “reach” beyond the nearest-neighbor cells, upon detection that changes in the angular orientation of the device have caused the field of view to shift by more than one pixel distance, the reference frame is shifted to the new location within the computational array. The shift to the new location is dictated by the change in angular orientation of the device. With the reference frame in the new location, nearest-neighbor correlations become correlations between the translated reference frame and a newly acquired sample frame. By translating the pixel values of the reference frame to new locations, inter-cell connectivity is kept to a minimum without compromising the accuracy of the attitude tracking.

0082The translation of the reference frame is accomplished within the individual computation cells of the computational array. Referring to the computation cell <b>94</b> of FIG. 6, a first step is to pulse REFSFT <b>140</b> high to sample-and-hold the REFDATA signal <b>136</b> at REFSH <b>138</b>. A third buffer amplifier <b>158</b> drives REFOUT <b>160</b> with the REFSH signal. CDOUT <b>106</b> is driven low, allowing REFOUT <b>160</b> to be the output of the computation cell <b>94</b> at the NN(<b>0</b>) node <b>108</b>.

0083The nearest-neighbor address is then set to select the appropriate S(<b>0</b>)-S(<b>8</b>) input from the switch control signal lines <b>128</b>. For example, if the T-shaped feature <b>204</b> in FIG. 5 is detected to have moved to the right and upwardly from the time at which the reference frame <b>202</b> is acquired to the time at which the sample frame <b>204</b> is acquired, the pixel values that comprise the reference frame must be shifted from cell-to-cell to the right and upwardly. Since S(<b>0</b>)-S(<b>8</b>) signals switch the address of the cell input NNINPUT <b>130</b>, S(<b>7</b>) must be driven high to enable movement of the pixel value from location <b>7</b> to <b>212</b> in FIG. 5 to location <b>0</b>. This takes place in each computation cell of the computational array. After REFOUT <b>160</b> has settled on the NNINPUT <b>130</b> of the appropriate neighbor cell, REFLD <b>132</b> is pulsed high to sample-and-hold the translated reference values at REFH <b>134</b>. After this operation has occurred in each of the computation cells of the array, the computational array is again ready to compute correlations.

Sensor/optics Arrangement

0084Another aspect of the invention is the arrangement for significantly reducing the adverse effects of what is known in lens design as “curvilinear distortions.” These distortions are also referred to as pincushion, barrel, and perspective distortions. The distortions compress rectilinear detail at the outer edges of a field of view.

0085The curvilinear distortions are particularly pronounced in simple lenses with wide fields of view. Such a lens may be used as the lens <b>26</b> in FIG. 1. The distortions are problematic, since they will cause the apparent shape of a feature to change as the feature drifts across the field of view. A change in the apparent shape of a feature will adversely affect the correlation process described with reference to FIGS. <b>4-6</b>.

0086FIG. 7 shows images of a T-shaped feature, imaged with distortion-free optics onto a 32×32 pixel array <b>220</b>. With such optics, the shape of the feature does not change with travel across the array, allowing high quality correlations and accurate tracking of pitch and yaw.

0087On the other hand, FIG. 8 illustrates the same feature imaged onto a pixel array <b>222</b> using a simple lens. It can be seen that the distortion increases as the feature is moved further from the optical axis of the lens. FIG. 9 shows in a stylized manner the way in which the feature is interpreted by the computational array for performing the correlation processing of FIG. 5. Each pixel in the array <b>224</b> of FIG. 9 represents a computational cell <b>94</b>, such as the one shown in FIG. 6. It is evident that the feature is “viewed” differently as it changes position within the computational array. This reduces the quality of the correlation, and the accuracy of the tracking of device attitude. Equally undesirable, the apparent motion of the feature changes with position, further degrading the accuracy of attitude tracking. For example, a strong off-axis moving detail will be measured as moving less than if the identical move were made on-axis. The result is a degradation of the attitude-tracking accuracy of the system. The adverse effects may be made smaller by not carrying the reference image across as many pixels, but this option of more frequently “zeroing” the reference frame increases the number of incremental errors, thereby adding its own contribution to tracking inaccuracy.

0088FIG. 10 illustrates a two-dimensional array <b>226</b> of photosensors configured to match the distortion of the lens. That is, the characteristics of the lens system with regard to introducing curvilinear distortions are determined and the array is configured to compensate for the distortion. Projected onto the curvilinear array of

0089FIG. 10 is the T-shaped feature in three different positions. It can be noted that although the images of the feature are still distorted, the distortion causes the images to fit within the pixels. Thus, each feature will be viewed as being rectilinear at the computation array level. That is, the corner image <b>228</b> will be distorted at the sensor level, as shown in FIG. 10, but the corner image <b>230</b> will be “viewed” as being an undistorted “T” at the computational array <b>232</b> of FIG. 11.

0090FIG. 10 illustrates a two-dimensional array <b>226</b> of photosensors configured to match the distortion of the lens. That is, the characteristics of the lens, system with regard to introducing curvilinear distortions are determined and the array is configured to compensate for the distortions. Projected onto the curvilinear array of FIG. 10 is the T-<i>shaped feature in three different positions. It can be noted that although the images of the feature are still distorted, the distortion causes the images to fit within the pixels. Thus, each feature will be viewed as being rectilinear at the computation array level. That is, the corner image <b>228</b> will be distorted at the sensor level, as shown in FIG. </i>10, but the corner image <b>230</b> will be “viewed” as being an undistorted “T” at the computational array <b>232</b> of FIG. 11.

0091The method of ascertaining the curvilinear geometry of the photosensor array elements may now be described. Conceptually, it consists of starting with an enlarged object plot of a 32×32 array of rectilinear (not curvilinear) cells, perhaps a foot square. The lens of choice is next used to produce an image of this array. This small and curvilinear image captures the distortions of the lens, and represents a reasonable approximation to an ideal array geometry.

0092This process produces accurate imaging with lenses of any field of view, and has many applications such as in positional navigation. However, in the present pointing device, it is a goal to transduce angles and not distances. For lenses of narrow fields of view, angles tend to become increasingly compressed as one moves further off of the optical axis.

0093This undesirable angular compression is avoided by changing the design process such that a segment of a sphere is substituted for the aforementioned flat array. The center of the spherical segment is overlaid approximately with the nodal point of the lens. The segment is lined at intervals of perhaps 2° in latitude and longitude. Each cell formed on the spherical segment, once imaged and reduced, is taken to be the outline of an array cell.

0094In practice, this method of generating the geometry of the curvilinear array is best accomplished using computer ray tracing. Many commercial optical design programs are available and familiar to those skilled in the art.

0095One advantage of the curvilinear array is that it provides more accurate autocorrelations, regardless of how far the images move from the axis of the sensor array. A second benefit is that distances are true and not compressed, so that attitude tracking is accurate over larger pixel moves without regard to where the move is imaged on the sensor array. Each benefit of the curvilinear array in itself contributes to more accurate tracking. Since the correlation is stronger and less noisy, the accuracy of measuring the end point of each move segment is higher. Moreover, since the image can be tracked in longer segments, the frequency of zeroing the reference frame is reduced, so that the cumulative re-zeroing error becomes less. Finally, because the curvilinear array does not compress off-axis moves, the accuracy of distance measurement is greater.