Below you will find an abstract of the single-constraint-at-a-time (SCAAT) approach to tracking, followed by a more detailed introduction, and finally a list of references. More complete descriptions can be found in Greg Welch's doctoral dissertation, and a 1997 SIGGRAPH paper on the subject.
The idea behind the SCAAT approach is to use of a Kalman filter to estimate a globally observable system using only measurements from locally unobservable systems. The Kalman filter has been similarly used in cases where observations were only available sequentially, e.g., to solve the bearings-only problem of tracking a target using only measurements from a single sensor [Lindgren78, Petridis81]. However, modern tracking systems do not normally face a similar single-sensor problem, they make use of multiple sensors (and sources) that together offer complete information about a target's position and orientation. Despite the availability of multiple sensors we present specific justification for recasting the tracking problem in terms of observing single sensors, i.e. incremental tracking with incomplete information, a single constraint at a time.
On February 19, 1997, Greg Welch presented a UNC COMP 205 guest lecture on the numerical and stability concerns of a Kalman filter in general, and a SCAAT implementation in particular.
Greg Welch and Gary Bishop have written an Introduction to the Kalman Filter which you can look at in PDF or HTML format.
The UNC-CS optoelectronic 3D tracking system utilizes user-mounted outward-looking optical sensors that sight infrared beacons mounted in special ceiling panels. Because single beacon sightings provide no distance information, a non-collinear group of three or more sightings must be obtained before a complete position estimate can be computed. In the context of control theory we would say that a single beacon sighting provides a measurement of a system that is unobservable, while a non-collinear group of three or more sightings forms a measurement of a system that is completely observable. But beacon sightings cannot be measured simultaneously. Instead they are measured sequentially and treated mathematically as if they had been measured simultaneously, even though the user is typically in motion throughout the sequence of measurements. We refer to this assumption as the simultaneity assumption.
The extended Kalman filter (EKF) provides a powerful mathematical framework within which a least-squares estimate of a user's position and orientation can be maintained using a sequence of single beacon sightings, as opposed to groups of sightings. We refer to this new approach as single-constraint-at-a-time or SCAAT tracking. In addition to avoiding the simultaneity assumption, this approach provides tracking estimates at a higher rate and with lower latency than our current system, and it provides a new opportunity to simultaneously perform beacon autocalibration.
The most significant aspect of our work is the introduction and exploration of the SCAAT approach to 3D tracking. This core research is supplemented with the introduction of a new method for performing beacon autocalibration, a method uniquely facilitated by SCAAT tracking. Finally, we also offer hope that this research may prove to be of interest to the larger scientific and engineering community in addressing a more general class of tracking and estimation problems.
The idea for one-LED-at-a-time tracking, was originally conceived of by Dr. Gary Bishop, and has been the subject of joint research with Greg Welch since August of 1994. The original hypothesis, that one might actually be able to build an inside-looking-out tracking system that functioned by only looking at one LED or beacon at a time, is a very interesting one. After all, each observation of a single beacon does not provide enough information to completely determine the target's position and orientation. However each observation does provide some information about a target's position and orientation, and that information can be used to improve an existing estimate. The more general description one-step-at-a-time was later suggested by Dr. Anselmo Lastra during discussions about how the approach might apply to a more general class of problems (e.g. GPS navigation). This extension of the idea is discussed briefly below, and in more detail in Greg Welch's recent dissertation. We later decided that the word "constraint" better described what was happening rather than "step", and Mark Mine then suggested the acronym SCAAT for single-constraint-at-a-time. Finally, Vernon Chi suggested the notion of "incremental tracking", and Fred Brooks suggested "incomplete information". Hence the final name for the work: "SCAAT: Incremental Tracking with Incomplete Information".
Our research is motivated by several factors. We will briefly discuss a few here. To begin with, sightings (observations) using our current ceiling tracker [Ward92] take as long as one millisecond. While [Azuma91] suggests the use of between 12 and 14 sightings to estimate the position and orientation of the target, in practice up to 20 observations are used [Gottscha93]. Thus the time required to offer a complete tracker estimate can exceed 20 milliseconds. In our current system this corresponds to an update rate of 50 estimates per second. In addition to the tracker latency, the time from motion to estimate, is typically on the order of 40 milliseconds [Mine93] which contributes to problems with head-mounted display registration [Holloway95] and with the motion prediction argued for by both Holloway and [Azuma94]. We would certainly like to be able to obtain updated tracking estimates at a higher rate and with lower latency than is possible with current schemes. Since the maximum beacon (LED) activation rate for our tracking system exceeds 5000 activations per second, a scheme that provides estimates based on a single beacon activation (and corresponding sighting) appears attractive. It is worthwhile to note that our tracking system is not alone in these respects: other (commercial) tracking systems make use of sequential sensor observations and might benefit from the SCAAT approach.
Second, the mathematics currently used to completely estimate position and orientation "assume" that the observations (the constraints on the unknowns) are related, i.e. that the observations occurred simultaneously [Azuma91][Gottscha95]. We refer to this assumption as the simultaneity assumption. However, because the time required to obtain the necessary multiple measurements is typically on the order of 20 milliseconds, the target can undergo significant motion during the sequence of observations. Not only is the simultaneity assumption physically violated, but it introduces error into the system by "pulling" estimates away from the truth.
Third, because under such a scheme the beacons are observed one at a time, it might be possible to devise a means to improve the estimates of the positions of individual beacons while concurrently tracking the main target, i.e. it might be possible to formulate a new approach to beacon autocalibration [Gottscha93]. Our new optoelectronic tracking system makes use of ceiling (LED) panels that are designed to be used in place of existing acoustical tiles. This flexibility comes at the expense of precise control over the positioning of the ceiling panels. Various independent environmental factors (e.g. slamming doors, HVAC operation) may cause the ceiling panels to move from time to time. As such we desire a tracking system that incorporates beacon autocalibration. However, such aspirations appear difficult with the current scheme. Not only does the simultaneity assumption introduce error when the target undergoes motion during calibration (indeed a necessity for autocalibration), but the mathematical grouping of beacon sightings seems to preclude ready access to information about individual beacons.
Finally, and possibly most exciting, it is possible that the central SCAAT idea may apply to a more general class of problems where repeated estimations of a process or linear system are performed. As far as we know, no one has yet proposed (much less demonstrated) the use of an extended Kalman filter to estimate the state of a globally observable system by incorporating only measurements of locally unobservable systems. Other tracking systems, e.g. the Polhemus cube [Raab79] from Polhemus Navigation Sciences estimate a user's position and orientation only after obtaining measurements of multiple sensors. Again, the reason is that the sensors individually provide insufficient tracking information, but collectively provide a complete picture. To generalize a bit further, we believe that the typical navigation systems (e.g. GPS, aircraft, spacecraft or robotic) probably share this "multiple inadequate sensor" characteristic, i.e. these systems too might benefit from the SCAAT approach. Finally we feel that some thought should be devoted to an even broader application of the idea. We believe that there exists some basic class of estimation problems that we can characterize as subject to improvement by incorporating observations one step at a time.
Azuma, Ronald and Mark Ward. 1991. "Space-Resection by Collinearity: Mathematics Behind the Optical Ceiling Head-Tracker," UNC Chapel Hill Department of Computer Science technical report TR 91-048 (November 1991), 23 pages.
Azuma, Ronald and Gary Bishop. 1994. "Improving Static and Dynamic Registration in an Optical See-Through HMD," Proceedings of ACM SIGGRAPH '94 (Orlando, FL, July 1994), Computer Graphics, Annual Conference Series.
Gottschalk, Stefan and John F. Hughes. 1993. "Autocalibration for Virtual Environments Tracking Hardware," Proceedings of ACM SIGGRAPH '93 (Anahiem, CA, July 1993), Computer Graphics, Annual Conference Series.
Gottschalk, Stefan and Vernon L. Chi. 1995. "Sensitivity of System Accuracy to Fabrication Tolerances in an Outward-looking Tracker," UNC Chapel Hill Computer Science Technical Report TR94-055. (94-055.ps.Z, approximately 460KB)
Holloway, Richard L. 1995. "Registration Errors in Augmented Reality Systems," Ph.D. dissertation, The University of North Carolina at Chapel Hill, TR95-016. (95-016.ps.Z, approximately 860KB)
Lindgren, Allen G., and Kai F. Gong. July 1978. "Position and Velocity Estimation Via Bearing Observations," IEEE Transactions on Aerospace and Electronic Systems, Vol. AES-14, No. 4.
Mine, Mark. 1993. "Characterization of End-to-End Delays in Head-Mounted Display Systems," UNC Chapel Hill Computer Science Technical Report TR93-001. (93-001.ps.Z, approximately 913KB)
Petridis, Vassilios. April 1981. "A Method for Bearings-Only Position and Velocity Estimation," IEEE Transactions on Automatic Control, Vol. AC-26, No. 2.
Raab, F. H., E. B. Blood, T. O. Steiner, and H. R. Jones. 1979. "Magnetic Position and Orientation Tracking System," IEEE Transactions on Aerospace and Electronic Systems, Vol. AES-15, 709-718
Ward, Mark, Ronald Azuma, Robert Bennett, Stefan Gottschalk, and Henry Fuchs. 1992. "A Demonstrated Optical Tracker With Scalable Work Area for Head-Mounted Display Systems," Proceedings of 1992 Symposium on Interactive 3D Graphics (Cambridge, MA, 29 March - 1 April1992), 43-52.
Return to Greg Welch's home page.
Last modified: