# Patent

## Title
Apparatus and method for detecting a pointer relative to a touch surface

## Abstract

An apparatus for detecting a pointer relative to a touch surface includes at least two spaced imaging assemblies having overlapping fields of view encompassing the touch surface. The imaging assemblies see the touch surface in three-dimensions as a perspective view. The imaging assemblies acquire overlapping images from different locations. A processor receives and processes image data generated by at least one of the imaging assemblies to determine the location of the pointer relative to the touch surface.

## Background
FIELD OF THE INVENTION
The present invention relates generally to interactive input systems and in particular to an apparatus and method for detecting a pointer relative to a touch surface.
BACKGROUND OF THE INVENTION
Touch systems are well known in the art and typically include a touch screen having a touch surface on which contacts are made using a pointer in order to generate user input. Pointer contacts with the touch surface are detected and are used to generate corresponding output depending on areas of the touch surface where the pointer contacts are made. Common touch systems utilize analog resistive, electromagnetic, capacitive, acoustic or machine vision techniques to identify pointer contacts on the touch surface.
For example, International PCT Application No. PCT/CA01/00980 filed on Jul. 5, 2001 and published under No. WO 02/03316 on Jan. 10, 2002, assigned to SMART Technologies Inc., assignee of the present invention, discloses a camera-based touch system comprising a touch screen that includes a passive touch surface on which a computer-generated image is presented. A rectangular bezel or frame surrounds the touch surface and supports digital cameras at its corners. The digital cameras have overlapping fields of view that encompass and look generally across the plane of the touch surface. The digital cameras acquire images looking across the touch surface from different locations and generate image data. Image data acquired by the digital cameras is processed by digital signal processors to determine if a pointer exists in the captured image data. When it is determined that a pointer exists in the captured image data, the digital signal processors convey pointer characteristic data to a master controller, which in turn processes the pointer characteristic data to determine the location of the pointer in (x,y)-co-ordinates relative to the touch surface using triangulation. The pointer co-ordinate data is conveyed to a computer executing one or more applications programs. The computer uses the pointer co-ordinate data to update the computer-generated image that is presented on the touch surface. Pointer contacts on the touch surface can therefore be recorded as writing or drawing or used to control execution of applications programs executed by the computer.
Although the above touch system works extremely well, improvements in vision-based touch systems are continually being sought.
It is therefore an object of the present invention to provide a novel apparatus and method for detecting a pointer relative to a touch surface.
SUMMARY OF THE INVENTION
According to one aspect of the present invention there is provided an apparatus for detecting a pointer relative to a touch surface comprising at least two spaced imaging devices having overlapping fields of view encompassing the touch surface. The imaging devices see the touch surface in three-dimensions as a perspective view. The imaging devices acquire images from different locations. A processor receives and processes image data generated by at least one of the imaging devices to determine the location of the pointer relative to the touch surface.
Each imaging device is calibrated to establish the relationship between points (X,Y,Z) in its perspective view and points (x,y) in acquired images. Each imaging device generates pointer co-ordinate data when a pointer is captured in an acquired image. The processor triangulates the pointer co-ordinate data to determine the location of the pointer relative to the touch surface.
In one embodiment, the apparatus includes a pair of imaging devices with each imaging device being positioned adjacent a different corner of the touch surface. Each imaging device is spaced from and spaced in front of the touch surface. Each imaging device is positioned relative to the touch surface so that at a minimum the entire periphery of the touch surface is within its perspective view.
In one embodiment, during calibration, calibration points (X,Y,Z) on the touch surface and image points (x,y) corresponding to the calibration points are measured. Collinearity equations are solved using the measured calibration and image points to determine external and internal orientation parameters of the imaging devices. The collinearity equations are solved using a least-squares method. The calibrations points are at spaced location along the periphery of the touch surface such as at the corners and edge mid-points of the touch surface. In an alternative embodiment, the external orientation parameters of the imaging devices are determined using a vanishing point method. In yet another embodiment, the external and internal orientation parameters of the imaging devices are determined using planar homography. In still yet another embodiment, the external orientation parameters of the imaging devices are determined using a three-point method.
In one embodiment, each imaging device generates a certainty value representing the degree of certainty that the imaging device has positively identified the pointer of the acquired image. The certainty value is used by the processor to determine pointer co-ordinate data to be used to determine the position of the pointer relative to the touch surface. The processor ignores pointer co-ordinate data generated by the imaging device when the certainty value associated therewith is below a threshold level.
According to another aspect of the present invention there is provided a camera-based touch system comprising a generally rectangular passive touch surface on which contacts are made using a pointer. Camera devices are removably mounted adjacent at least two corners of the touch surface. Each of the camera devices has a field of view looking across and back towards the touch surface and is disposed in front of the plane of the touch surface. The fields of view of the camera devices overlap over the touch surface. The camera devices acquire images of the touch surface. A processor receives and processes the image data to determine the location of the pointer relative to the touch surface via triangulation.
According to yet another aspect of the present invention there is provided an apparatus for detecting a pointer relative to a generally rectangular touch surface comprising at least two spaced imaging devices having overlapping fields of view encompassing the touch surface. The imaging devices see the touch surface in three-dimensions as a perspective view with the perspective view at a minimum including the four corners of the touch surface. The imaging devices acquire overlapping images from different locations. A processor receives and processes image data generated by at least one of the imaging devices to determine the location of the pointer relative to the touch surface using triangulation.
The present invention provides advantages in that since the imaging devices see the touch surface in three-dimensions as a perspective view, the imaging devices see the entire touch surface as well as its surrounding area. As a result, during image processing it is not necessary to process the entire images captured by the imaging devices but rather only pixels corresponding to information within the boundaries of the touch surface. Noise and other aberrations occurring in areas outside of the touch surface can be disregarded. In addition, the three-dimensional perspective of the imaging devices allows the apparatus to be automatically calibrated and calibrated on a continuing basis without the need for user intervention. Furthermore, the three-dimensional perspective of the imaging devices allows (x,y,z) co-ordinates to be assigned to each pointer appearing within the fields of view of the imaging devices. Thus, the apparatus is able to disambiguate between multiple pointers contacting the touch surface.
The present invention also provides advantages in that since the imaging devices are portable, they can be used to turn basically any surface into a touch surface. The imaging devices simply need to extend forwardly of the surface a sufficient distance so that their fields of view looking back and across the touch surface see the corners of the surface and are not obstructed by any bezel or framing surrounding the surface. The use of portable imaging devices that see the touch surface in three-dimensions as a perspective view also supports arbitrarily large or curved touch surfaces.



BRIEF DESCRIPTION OF THE DRAWINGS
Embodiments of the present invention will now be described more fully with reference to the accompanying drawings in which:
FIG. 1 is a schematic illustration, partially in perspective, of an apparatus for detecting a pointer relative to a touch surface;
FIG. 2 is a schematic front plan view of the apparatus of FIG. 1;
FIG. 3 is a schematic side view of the apparatus of FIG. 1;
FIG. 4 is a perspective view of an imaging assembly forming part of the apparatus of FIG. 1;
FIG. 5 is a schematic block diagram of the imaging assembly of FIG. 4;
FIG. 6 is a flow chart showing the steps performed during calibration of the apparatus of FIG. 1;
FIG. 7 is a flow chart showing the steps performed during triangulation of pointer data extracted from acquired images to determine the location of a pointer contact on the touch surface;
FIG. 8a to 8d show the number of pixel rows in a captured image that must be processed for different spacings between an imaging assembly and the plane of the touch surface;
FIG. 9 is a perspective view of another embodiment of apparatus for detecting a pointer relative to a touch surface;
FIG. 10 is a front view of yet another embodiment of an apparatus for detecting a pointer relative to a touch surface;
FIG. 11 is still yet another embodiment of an apparatus for detecting a pointer relative to a touch surface; and
FIGS. 12a to 12c show different pointer contacts on the touch surface of the apparatus of FIG. 11.



DETAILED DESCRIPTION OF THE EMBODIMENTS
Turning now to FIGS. 1 to 3, an apparatus for detecting a pointer relative to a touch surface is shown and is generally identified by reference numeral 50. In this embodiment, apparatus 50 is in the form of a touch system and includes a touch screen 52 having a touch surface 54 on which pointer contacts are to be made. Touch screen 52 is a flat panel display such as for example, a plasma display, a high-definition television (HDTV), a liquid crystal display (LCD) or the like that presents an image on the touch surface 54. A bezel 56 surrounds the touch surface 54. A pair of imaging assemblies 58 is positioned adjacent the top corners of the touch screen 52. The imaging assemblies 58 communicate with each other as well as with a computer 60 executing one or more application programs. The computer 60 processes pointer co-ordinate data generated by the imaging assemblies 58 to determine the locations of pointer contacts made on the touch surface 54 and updates the image that is presented on the touch surface 54 in response to the pointer contacts. Pointer contacts on the touch surface 54 can therefore be recorded as writing or drawing or used to control execution of application programs executed by the computer 60.
Turning now to FIG. 4, one of the imaging assemblies 58 is better illustrated. As can be seen, the imaging assembly 58 includes a housing 72 shaped complimentary to the corner of the touch screen 52. Formations (not shown) on the housing 72 allow the imaging assembly 58 to be secured in position relative to the corner of the touch screen. The imaging assembly 58 can however be removed from the touch screen 52 making the imaging assembly 58 portable. A digital camera 74 is accommodated by the housing 72 and is positioned in front of the plane of the touch surface 54 by a distance equal to approximately 2.5 cm. This distance between the digital camera 74 and the plane of the touch surface 54 is selected so that the bezel 56 does not obstruct the field of view of the digital camera 74 allowing the digital camera to see the entire touch surface 54 while still permitting useful three-dimensional processing of image data. The digital camera 74 is also positioned above the touch surface 54 by a distance equal to approximately 10 cm. The digital camera 74 is aimed so that its field of view (FOV) looks back at and across the entire touch surface 54. Thus, the digital camera 74 sees the touch surface 54 including its four corners in three-dimensions as a perspective view. The optical axis of the digital camera 74 is in line with the top corner of the touch screen 52 and forms an angle equal to approximately 45 degrees with respect to the top edge of the touch screen 52.
Housing 72 also accommodates a circuit board on which the digital camera 74 and image processing circuitry 80 are mounted as shown in FIG. 5. As can be seen, the image processing circuitry 80 includes a digital signal processor (DSP) 82 coupled to the digital camera 74 and to static random access memory (SRAM) 84. The DSP 82 also communicates with the computer 60 over a data bus 86. The digital camera 74 is a high-resolution CMOS digital camera having a 640×480 pixel array such as that manufactured by National Semiconductor under model No. LM9618 and an associated lens 88. The DSP 82 is of the type manufactured by Analog Devices Inc. under model No. Blackfin BF 533 and includes a feature that allows image data to be moved from the digital camera 74 to the SRAM 84 quickly without interrupting DSP processing.
The general operation of the touch system 50 will firstly be described. When a pointer is brought into the fields of view of the digital cameras 74 and contacts the touch surface 54, each of the digital cameras 74 acquires an image including the pointer. The DSP 82 of each imaging assembly 58 moves the image data from the digital camera 74 to the SRAM 84 and then compares the image data with a mathematical model describing the boundary of the touch surface 54 as seen by the digital camera 74. This enables a pixel subset of the captured image including only relevant pixels to be processed. The DSP 82 of each imaging assembly 58 in turn processes the pixel subset to determine the (x,y) position of the pointer within the captured image. The imaging assemblies 58 in turn convey this pointer co-ordinate data to the computer 60, which uses the pointer co-ordinate data to calculate the (X,Y,Z) location of the pointer contact on the touch surface 54 using triangulation. The pointer location data is then either recorded by the computer 60 as writing or drawing or interpreted as a mouse or other event.
In order to enable pointer contacts relative to the touch surface 54 to be calculated accurately using triangulation, the touch system 50 needs to be calibrated so that either or both imaging assemblies 58 know how a particular point in a captured image relates to a physical three-dimensional location on the touch surface 54 (the “scene”). During calibration, a transformation that establishes the relationship between any point in the three-dimensional scene that each imaging assembly 58 observes and any point in a captured two-dimensional image is established. This step is necessary, since when the touch system 50 is set up, a priori information concerning the locations and orientations of the digital cameras 74 with respect to a touch surface 54 are not known.
The relationship between a point in a three-dimensional scene and its two-dimensional position in a captured image is summarized according to the collinearity equations as follows:



  
    x
    =
    
      
        x
        0
      
      -
      
        Δ
        x
      
      -
      
        
          fR
          1
        
        
          R
          3
        
      
    
  




  
    y
    =
    
      
        y
        0
      
      -
      
        Δ
        y
      
      -
      
        
          fR
          2
        
        
          R
          3
        
      
    
  



where:

(x,y) are the co-ordinates of a point in a captured image corresponding to a point (X,Y,Z) in the three-dimensional scene;
(x0, y0) are the co-ordinates of the principal point of the digital camera 74, the location at which the optical axis of the digital camera meets the focal plane of the digital camera with the optical axis being approximately normal to the focal plane;
(Δx,Δy) represent distortion terms introduced due to the imperfect nature of the lens 88;
f is the digital camera focal length; and
(R1,R2,R3) are terms depending on point (X,Y,Z), the spatial location of the optical center of the digital camera (X0,Y0,Z0) and the orientation angles (ω,φ,κ) of the digital camera optical axis with respect to the three-dimensional co-ordinate system of the touch surface 54.
The above collinearity equations represent a pinhole model. Thus, each digital camera 74 is idealized as a very small aperture at the location of the digital camera's optical center (focal point), which is taken to be the position of the digital camera in three-dimensional space. The three-dimensional nature of the digital cameras' view is important in that it allows the digital cameras to see over the bezels 56, if the touch surface 54 is assumed to be planar allows the plane of the touch surface to be determined, allows a determination to be made at any point as to whether a pointer is in contact with the touch surface 54 or hovering above the touch surface 54, and allows the position of the pointer relative to the touch surface 54 to be determined.
The above collinearity equations express that a point in a three-dimensional scene with co-ordinates (X,Y,Z) projects into a two-dimensional image at point (x,y). In order to establish the transformation using the collinearity equations, the external orientation parameters (X0,Y0,Z0) and ω,φ,κ and the internal orientation parameters f,x0,y0 and Δx,Δy of the digital cameras 74 need to be determined.
The distortion of each lens 88 can be represented by terms relating specifically to both radial distortion and decentering distortion. Due to the relativity low quality of each lens 88 and captured image data, in the present embodiment, only the first-order radial distortion term is recorded. As a result the lens distortion terms can be expressed as:

Δx=(x−x0)K1((x−x0)2+(y−y0)2)

Δy=(y−y0)K1((x1−x0)2+(y−y0)2)

Thus, lens distortion can be summarized through parameter K1.

As will be appreciated, ten (10) parameters for each digital camera 74 need to be determined from the collinearity equations to calibrate each digital camera, namely:

X0,Y0,Z0,ω,φ,κ,f,x0,y0,K1 

In the present embodiment, a self-calibration technique is used to calibrate the touch system 50. Self-calibration is based on the fact that if the three-dimensional positions of reference points on an object are known and the two-dimensional positions of the same points can be measured in one or more images of the object, these data completely specify the location of the imaging assembly capturing the image, the angular orientation of the imaging assembly and parameters relating to the lens of the imaging assembly.
The positions (X0,Y0,Z0)of the digital cameras 74 in three-dimensional space may be measured in absolute units (e.g., centimeters) or in relative terms by assuming a unit of length corresponding to a reference length such as for example the shorter dimension of the touch surface 54. Each digital camera's angular orientation is represented by the three angles ω, φ, κ allowing a rotation matrix R for each digital camera 74 to be defined. The rotation matrix R describes the transformation between the co-ordinate system of the three-dimensional scene and that of the digital camera. Calculating the focal length f, principal point (x0,y0), and lens distortion coefficient(s) for each digital camera 74 is not necessary if precise values for these digital camera parameters are known.
During self-calibration, it is assumed that the touch surface 54 corresponds to the X-Y plane, and that the Z axis is pointing outward from the touch surface 54 at an angle generally normal to the plane of the touch surface. If image positions (x,y) corresponding to a number of scene points (X,Y,Z) are measured from an image, and the positions of the scene points (X,Y,Z) are known (e.g., in centimeters), then the collinearity equations may be set up for each point and solved using a least-squares technique to enable the external and internal orientation parameters to be determined. The least-squares method is used due to the non-linear nature of the collinearity equation model.
In the present embodiment, eight (8) calibration points around the periphery of the touch surface 54 are chosen since by doing so yields sixteen (16) equations and ten (10) unknowns, which is sufficient for a good least-squares solution. In particular, the four corners and the mid-points along each side edge of the touch surface 54 are selected as the calibration points since the (X,Y) positions at these calibration points are easy to measure, provide reproducible calibration points, are easily located by users and at each of these (X,Y) positions Z=0 cm. The corresponding image points are defined by either measuring the positions of a pointer at the calibration points captured in an image, or by measuring the positions of markers at the calibration points in a captured image.
Turning now to FIG. 6, a flow chart illustrating the general steps performed during self-calibration is shown. Initially the (X,Y,Z) positions of the calibration points on the touch surface 54 are determined (step 100). Specifically, the positions of the calibration points on the touch surface 54 are determined by measuring the positions of the touch surface corners and the mid-points of its side edges relative to one of the touch surface corners that is designated to be at the co-ordinate origin. Alternatively, if the aspect ratio of the touch surface 54 is known, then the short dimension of the touch surface can be taken as a unit of length, allowing the relative positions of the corners and side edge mid-points to be determined. The (x,y) positions of the calibrations points in the images are then determined through image processing (step 102), with possible initial guess input from external image processing as will be described (step 104). A calibration solution is then computed, including the internal orientation parameters if desired (step 106). If the computed solution is based on initial guess input, a least-squares refinement is computed (step 108).
With the touch system 50 calibrated, the three-dimensional position of a pointer above or in contact with the touch surface 54 can be calculated via triangulation. During triangulation it is assumed that all of the camera orientation parameters are known and the pointer position (X,Y,Z) is to be determined given corresponding (x,y) measurements from the image captured either by one or both digital cameras 74. FIG. 7 is a flow chart illustrating the general steps performed during triangulation of pointer co-ordinate data to determine pointer contact locations relative to the touch surface. When images are captured by the imaging assemblies 58 including a pointer, the image data is processed by the DSPs 82 to determine the position of the pointer in each captured image in (x,y) co-ordinates. The DSPs 82 in turn output this pointer co-ordinate data to the computer 60 (step 120). Each DSP 82 also outputs a pointer position certainty estimate representing the degree of certainty that the DSP 82 has positively identified the actual pointer in the captured image. The computer 60, which receives pointer co-ordinate and certainty estimate data from the DSPs 82 of both imaging assemblies 58 (steps 122 and 124), makes a decision as to whether to use the pointer co-ordinate data returned by one or both imaging assemblies based on the certainty estimates (step 126). Generally, the pointer co-ordinate data generated by both DSPs 82 is used by the computer 60. If however, the certainty estimate associated on the pointer co-ordinate data generated by one of the DSPs 82 is below a threshold level, in this case 50%, representing a low degree of certainty that the pointer co-ordinate data is accurate, that pointer co-ordinate data is ignored and not used.
Triangulation is then performed using the collinearity equations referred earlier either using the pointer co-ordinate data from both imaging assemblies 58 (step 128) or using the pointer co-ordinate data from one imaging assembly 58 (step 130). Since the collinearity equations relate image position (x,y) to spatial position (X,Y,Z), two (x,y) positions, one from each digital camera 74, are necessary to compute a unique (X,Y,Z) spatial position for the pointer. This yields four equations and three unknowns. The collinearity equations are rearranged to produce a linear least-squares problem, making triangulation an efficient procedure. Since the results of the triangulation in this case yield an (X,Y,Z) spatial position for the pointer, multiple pointers appearing within the fields of view of the imaging assemblies 58 can be tracked separately thereby to provide pointer disambiguation.
When performing triangulation using pointer co-ordinate data from a single imaging assembly 58, it is assumed Z=0 (cm). In this case, one of the unknowns in the collinearity equations is eliminated. In other words, spatial position (X,Y) is determined from image position (x,y). Using images from a single imaging assembly 58 provides advantages in that the touch system 50 can still determine pointer contacts with the touch surface 54 even in instances where one of the imaging assemblies 58 is unable to see the pointer.
Once the triangulation results are available, the triangulation results can be refined using a non-linear least-squares technique if desired.
The use of imaging assemblies 58 that see the entire touch surface 54 in three-dimensions as a perspective view as well as its surrounding area provides advantages. For example, during image processing, pointers crossing the boundaries of the touch surface 54 can be recognized prior to contact on the touch surface. This information can be used by the DSPs 82 to limit image processing to pixels within the relevant pixel subset adjacent the boundary crossover points. The touch system 50 also provides shadow/object discrimination. Generally, as a pointer is brought towards the touch surface 54, one of the imaging assemblies 58 will see the pointer before the other. The imaging assembly seeing the pointer first can provide pointer information to the other imaging assembly identifying the region of its relevant pixel subset that should be examined to locate the pointer. This helps to increase the probability of locating the pointer accurately and quickly. Planar homography is used to relate the two digital camera focal planes to one another, allowing the pointer information to be effectively exchanged between the imaging assemblies 58.
Another approach is to make use of a different relationship between the views of the imaging assemblies, through an entity known as the fundamental matrix, or the closely-related essential matrix. Here, if the location of a point is known in one digital camera view, the fundamental matrix translates this point into a line in the other digital camera image. Thus, it is only necessary to search an image along this line (known as an epipolar line) to locate the corresponding point. This approach has an advantage in that it severely limits the search region in the second digital camera view and helps to eliminate false positives.
In the above-described embodiment, the imaging assemblies 58 are shown as being disposed in front of the plane of the touch surface 54 by a distance equal to approximately 2.5 cm. As mentioned, this distance ensures that the bezel 56 does not obstruct the imaging assemblies' views of the entire touch surface 54. The distances over which the imaging assemblies 58 are disposed in front of the plane of the touch surface 54 can of course vary depending on the environment although, the distances have an impact on the size of the relevant pixel subset corresponding to the boundary of the touch surface that must be processed. The imaging assemblies 58 are positioned so that, at a minimum, the four corners of the touch surface 54 are within their fields of view. FIGS. 8a to 8d show the number of pixel rows in a captured image that must be processed for different distances assuming a touch surface 54 having an 84′′ diagonal dimension and a 4:3 aspect ratio. As will be appreciated, as the distance increases so do the number of pixel rows that require processing in captured images.
Although a self-calibration technique has been described, other techniques can be used to calibrate the touch system 50. For example, the vanishing points for the touch surface 54 can be determined as described in the publication entitled “Geometric Computation for Machine Vison”, Oxford University Press, Oxford 1993, authored by Kanatani. Alternatively planar homography as described in the publication entitled “Multiple View Geometry in Computer Vision”, Cambridge University Press, Cambridge 2001, authored by Hartley et al. or the three-point method as described in the publication entitled “Minimum Solutions for Orientations in Calibration and Orientation of Cameras in Computer Vision”, Springer-Verlag, New York 2001, authored by Wrobel can be used to calibrate the touch system.
During the vanishing point method, advantage of the fact that the touch surface 54 is generally rectangular in shape is taken during computation of the external orientation parameters. In this case, by finding the peripheral edges of the touch surface 54 in a digital camera image, the vanishing points corresponding to the two sets of parallel peripheral side edges of the touch surface may be used to define the external orientation parameters completely. In the touch system, the vanishing points are finite, i.e., they lie within the bounds of a digital camera image and serve to define the rotation matrix R. If a unit of length is assumed, the digital camera positions can then be determined, completing the external orientation parameter determination. The vanishing points can also be used to define the digital camera's focal length and principal point as described in the publication entitled “On Estimating Rotations”, T.U. Munchen, 1999, authored by Foerstner. As will be appreciated, the two vanishing points define a three-dimensional co-ordinate system for the touch system, from which everything else follows. When using this approach it is preferred that the determined external orientation parameters be refined using a least-squares method.
The planar homography calibration approach relates points on the plane of the touch surface 54 to points on the image plane of the digital camera. By measuring the positions of a number of image points corresponding to certain scene points, it is possible to define the nine components of the homography matrix. Once this is done, the homography matrix can be decomposed into the rotation matrix R and a vector representing the digital camera's position in three-dimensional space. Using this calibration method requires some assumptions about the digital camera's internal orientation to be made. The need to make these assumptions can however be avoided by rewriting the homography matrix as another matrix entity known as the image of the absolute conic as described in the previously mentioned Hartley et al. publication. This matrix entity provides direct estimates of the focal length and principal point of the digital camera through its singular value decomposition.
The three-point calibration method makes use of basic trigonometry and the fact that three points define a plane. If the locations and distances between three points in a three-dimensional scene are known and form a triangle, then the image positions of these points may be used to define angles between the points. This information is sufficient to solve for the distances of the three points from the digital camera's optical center, thus giving the digital camera's position in space. Subsequent processing of the image points then provides an estimate of the rotation matrix R. As this method gives an orientation from a minimal data set, it can be used to initialize a least-squares method for refining the orientation, and hence to provide the initial guess input at step 104 during calibration.
Although the above-described calibration techniques make use of three angles to define the orientation of each digital camera 74 in space through a rotation matrix R, alternatives are available. For example rather than defining the rotation matrix R, the orientation of each digital camera in space can be determined based on an entity known as a “quaternion”. A quaternion is a four-element vector with certain properties as described in the previously mentioned Foerstner publication. Quaternion elements take on only values between −1 and 1, with one of the elements being constrained to be 1. This avoids problems associated with abrupt changes in value and assists greatly in the convergence using a least-squares approach. As will be appreciated, when measuring angles, some angle changes create difficulty such as for example when an angle changes from 359 degrees to 360 degrees, which is the same as 0 degrees.
FIG. 9 shows another embodiment of an apparatus for detecting a pointer relative to a touch surface 54. In this embodiment, both digital cameras 174 are accommodated within a single housing 172 adjacent its opposite ends. The housing 172 overlies the top edge of the bezel 56 and spans the touch screen 52 so that the digital cameras 174 are positioned adjacent the top corners of the touch screen.
Imaging assemblies that see the touch surface in three-dimensions as a perspective view can also be used in conjunction with large scale touch systems such as those described in U.S. patent application Ser. No. (not available) filed on Jan. 2, 2004 to Hill et al., assigned to SMART Technologies Inc., assignee of the present invention, the content of which is incorporated herein by reference. For example, FIG. 10 shows a digital camera arrangement for a large scale touch system. In this embodiment, digital cameras C1 to C8 are provided along the top of the touch surface 254 and look back at and across the touch surface. In particular, digital cameras C1 and C8 are located at the top left and top right corners of the touch surface 254. Intermediate pairs of digital cameras C2 and C3, C4 and C5 and C6 and C7 are located at spaced locations along the top of the touch surface 254. The fields of view of the digital cameras are shown by the dotted lines. As can be seen, the fields of view of the cameras overlap so that each location on the touch surface 254 falls within the fields of view of at least two digital cameras. This of course allows a pointer to be tracked across the entire touch surface 254 using triangulation in the same manner described above.
FIG. 11 shows yet another digital camera arrangement for a large scale touch system. In this embodiment, evenly spaced digital cameras C1 to C7 are positioned above the top edge of the touch surface 354 and look back at and across the touch surface. The fields of view of the digital cameras are shown by the dotted lines and as can be seen, the fields of view of the digital cameras overlap so that each location on the touch surface falls within the fields of view of at least two digital cameras. Again this allows a pointer to be tracked across the entire touch surface 354 using triangulation in the same manner described above. In this embodiment, most locations on the touch surface 354 fall within the fields of view of more than two digital cameras allowing multiple triangulation results to be generated for each pointer contact. Depending on the pointer contact locations, different logic can be used to select the triangulation results to be used to determine the pointer contact location.
For example, as shown in FIG. 12a, the position of pointer P on touch surface 354 can be calculated by triangulating pointer information derived from images captured by digital cameras C1 and C2 and possibly by triangulating pointer information derived from images captured by digital camera C3. In this latter case pointer information derived from images captured by digital cameras C1 and C3 and digital cameras C2 and C3 can be triangulated resulting in multiple triangulation results. The multiple triangulation results can be averaged or processed according to other logic to yield a single pointer position. If digital camera C3 is deemed to be too far from the pointer P, the result from the digital camera C3 can be ignored. Alternatively, pointer information derived from images captured by digital camera C3 can be used to track the pointer to determine when the pointer reaches a certain proximity to the digital camera C3. When the pointer reaches a certain proximity to the digital camera C3, the pointer information derived from images captured by digital camera C3 can be triangulated to determine the position of the pointer on the touch surface 354.
FIGS. 13b and 13c show other positions of pointers on the touch surface 354 and the various triangulation results that can be derived from images captured by the digital cameras.
By pairing the digital cameras, curved and non-planar touch surfaces can be supported since the various pairs of digital cameras need only be responsible for viewing a portion of the touch surface.
As will be appreciated, since the imaging assemblies are able to self-calibrate, the imaging assemblies can be affixed basically to any surface to convert that surface to a touch surface.
Although the touch system 50 is described as including a computer communicating with the DSPs of the imaging assemblies and processing the pointer co-ordinate data using triangulation to determine the position of the pointer relative to the touch surface, other processing architectures can of course be used. For example, the DSP of one of the imaging assemblies may serve as the processor responsible for triangulating the pointer co-ordinate data.
Although preferred embodiments of the present invention have been described, those of skill in the art will appreciate that variations and modifications may be made without departing from the spirit and scope thereof as defined by the appended claims.

## Claims

1. An apparatus for detecting a pointer relative to a touch surface comprising:
at least two spaced imaging devices having overlapping fields of view, each of said imaging devices having a field of view that looks back at the touch surface such that said imaging devices see said touch surface in three-dimensions as a perspective view including the boundaries of said touch surface, said imaging devices acquiring overlapping images from different viewpoints, each imaging device comparing acquired images with a model describing the boundaries of said touch surface thereby to determine a subset of pixels in each acquired image and processing each pixel subset to generate image data; and
processing structure processing image data generated by at least one of said imaging devices to determine the location of the pointer.

2. An apparatus according to claim 1 wherein each imaging device is calibrated to establish the relationship between points (X,Y,Z) in its perspective view and points (x,y) in acquired images, each imaging device generating pointer co-ordinate data when a pointer exists in an acquired image.

3. An apparatus according to claim 1 wherein said processing structure triangulates the image data to determine the location of the pointer relative to said touch surface.

4. An apparatus according to claim 3 including a pair of imaging devices.

5. An apparatus according to claim 4 wherein each imaging device is positioned adjacent a different corner of said touch surface.

6. An apparatus according to claim 5 wherein each imaging device is laterally spaced from and spaced in front of said touch surface.

7. An apparatus according to claim 6 wherein each imaging device is positioned relative to said touch surface so that at a minimum the entire periphery of the touch surface is within its field of view.

8. An apparatus according to claim 7 wherein each imaging device is spaced in front of said touch surface by a distance equal to at least 2.5 cm.

9. An apparatus according to claim 8 wherein said touch surface is bordered by a bezel.

10. An apparatus according to claim 7 wherein each imaging device is aimed so that the optical axis thereof bisects a corner of said touch surface.

11. An apparatus according to claim 2 wherein during calibration external orientation parameters (X0,Y0,Z0) and (ω,φ,κ) of each imaging device are determined where:
(X0,Y0,Z0) is the spatial location of the optical center of the imaging device; and
(ω,φ,κ) are the orientation angles of the optical axis of the imaging device with respect to the three-dimensional co-ordinate system of the touch surface.

12. An apparatus according to claim 11 wherein during calibration internal orientation parameters f,x0,y0 and Δx,Δy of each imaging device are also determined where:
(Δx,Δy)represent distortion terms introduced due to the imperfect nature of a lens of the imaging device;
f is the focal length of the imaging device; and
(x0,y0) are the co-ordinates of the principal point of the imaging device.

13. An apparatus according to claim 12 wherein said relationship is expressed using collinearity equations as:



  
    x
    =
    
      
        x
        0
      
      -
      
        Δ
        x
      
      -
      
        
          fR
          1
        
        
          R
          3
        
      
    
  




  
    y
    =
    
      
        y
        0
      
      -
      
        Δ
        y
      
      -
      
        
          fR
          2
        
        
          R
          3
        
      
    
  



where:
(x,y) are the co-ordinates of a point in a captured image corresponding to a point (X,Y,Z) in the three-dimensional perspective view; and
(R1,R2,R3) are terms depending on point (X,Y,Z), the spatial location (X0,Y0,Z0) and the orientation angles (ω,φ,κ).

14. An apparatus according to claim 13 wherein during calibration, calibration points (X,Y,Z) on said touch surface and image points (x,y) corresponding to said calibration points are measured, said collinearity equations being solved using said measured calibration and image points thereby to determine said external and internal orientation parameters.

15. An apparatus according to claim 14 wherein said collinearity equations are solved using a least-squares method.

16. An apparatus according to claim 14 wherein said calibration points are at spaced locations along the periphery of said touch surface.

17. An apparatus according to claim 16 wherein said calibration points are located at the corners and edge mid-points of said touch surface.

18. An apparatus according to claim 11 wherein said external orientation parameters are determined using a vanishing point method.

19. An apparatus according to claim 18 wherein the determined external orientation parameters are refined using a least-squares method.

20. An apparatus according to claim 18 wherein said external and internal orientation parameters are determined using planar homography.

21. An apparatus according to claim 18 wherein said external orientation parameters are determined using a three point method.

22. An apparatus according to claim 2 wherein each imaging device also generates a certainty value representing the degree of certainty that the imaging device has positively identified the pointer in the acquired image.

23. An apparatus according to claim 22 wherein said certainty value is used by said processing structure to determine pointer co- ordinate data to be used to determine the position of said pointer.

24. An apparatus according to claim 23 wherein said processing structure ignores pointer co-ordinate data generated by said imaging device when the certainty value associated therewith is below a threshold level.

25. An apparatus according to claim 24 including a pair of imaging devices.

26. An apparatus according to claim 25 wherein each imaging device is positioned adjacent a different corner of said touch surface.

27. An apparatus according to claim 26 wherein each imaging device is laterally spaced from and spaced in front of said touch surface.

28. An apparatus according to claim 27 wherein each imaging device is positioned relative to said touch surface so that at a minimum the entire periphery of the touch surface is within its field of view.

29. An apparatus according to claim 28 wherein each imaging device is aimed so that the optical axis thereof bisects the corner of said touch surface.

30. An apparatus according to claim 2 wherein said imaging devices communicate to assist in determining a pointer in acquired images.

31. An apparatus according to claim 30 wherein the imaging device that detects a pointer in its acquired image first communicates data to the other imaging device to assist that imaging device to detect the pointer in its acquired image.

32. An apparatus according to claim 31 wherein each imaging device also generates a certainty value representing the degree of certainty that the imaging device has positively identified the pointer in the acquired image.

33. An apparatus according to claim 32 wherein said certainty value is used by said processing structure to determine pointer co-ordinate data to be used to determine the position of said pointer.

34. An apparatus according to claim 33 wherein said processing structure ignores pointer co-ordinate data generated by said imaging device when the certainty value associated therewith is below a threshold level.

35. An apparatus according to claim 34 including a pair of imaging devices.

36. An apparatus according to claim 35 wherein each imaging device is positioned adjacent a different corner of said touch surface.

37. An apparatus according to claim 36 wherein each imaging device is laterally spaced from and spaced in front of said touch surface.

38. An apparatus according to claim 37 wherein each imaging device is positioned relative to said touch surface so that at a minimum the entire periphery of the touch surface is within its field of view.

39. An apparatus according to claim 38 wherein each imaging device is aimed so that the optical axis thereof bisects the corner of said touch surface.

40. An apparatus according to claim 14 wherein each imaging device also generates a certainty value representing the degree of certainty that the imaging device has positively identified the pointer in the acquired image.

41. An apparatus according to claim 40 wherein said certainty value is used by said processor to determine pointer co-ordinate data to be used to determine the position of said pointer.

42. An apparatus according to claim 41 wherein said processing structure ignores pointer co-ordinate data generated by said imaging device when the certainty value associated therewith is below a threshold level.

43. An apparatus according to claim 42 including a pair of imaging devices.

44. An apparatus according to claim 43 wherein each imaging device is positioned adjacent a different corner of said touch surface.

45. An apparatus according to claim 44 wherein each imaging device is laterally spaced from and spaced in front of said touch surface.

46. An apparatus according to claim 45 wherein each imaging device is positioned relative to said touch surface so that at a minimum the entire periphery of the touch surface is within its field of view.

47. An apparatus according to claim 46 wherein each imaging device is aimed so that the optical axis thereof bisects the corner of said touch surface.

48. An apparatus according to claim 2 wherein said imaging devices are portable.

49. An apparatus according to claim 48 wherein each imaging device includes a digital camera and a digital signal processor mounted within a housing, said digital signal processor processing image frames acquired by said digital camera to generate said pointer co-ordinate data.

50. An apparatus according to claim 48 wherein each imaging device includes a digital camera and a digital signal processor, both imaging devices being mounted within a single housing, said digital signal processor processing image data acquired by said digital camera to generate said pointer co-ordinate data.

51. An apparatus according to claim 3 including three or more imaging devices at spaced locations along said touch surface, each imaging device having a field of view encompassing a different portion of said touch surface.

52. An apparatus according to claim 51 wherein said imaging devices are arranged in pairs, with each pair of imaging devices viewing a different portion of said touch surface.

53. A camera-based touch system comprising:
a generally rectangular passive touch surface on which contacts are made using a pointer;
camera devices removably mounted adjacent at least two corners of said touch surface, each of said camera devices being disposed in front of the plane of the touch surface and having a field of view looking across and back towards said touch surface, the fields of view of said camera devices overlapping over said touch surface such that said camera devices see said touch surface and the boundaries thereof in perspective views, said camera devices acquiring images of said touch surface from different viewpoints, each camera device comparing each acquired image with a mathematical model describing the boundaries of said touch surface as seen by said camera device to determine a subset of relevant pixels of the acquired image corresponding generally to said touch surface and processing the subset of relevant pixels of each acquired image to generate image data; and
a processor receiving and processing said image data to determine the location of said pointer relative to said touch surface via triangulation.

54. A touch system according to claim 53 wherein each camera device is calibrated to establish the relationship between points (X,Y,Z) in its perspective view and points (x,y) in acquired images, each camera device generating pointer co-ordinate data when a pointer is captured in an acquired image.

55. A touch system according to claim 54 wherein each camera device is spaced in front of said touch surface a sufficient distance so that at a minimum each camera device sees the four corners and sides of said touch surface with its field of view.

56. A touch system according to claim 55 wherein each camera device also generates a certainty value representing the degree of certainty that the camera device has positively identified the pointer in the acquired image.

57. A touch system according to claim 56 wherein said certainty value is used by said processor to determine pointer co-ordinate data to be used to determine the position of said pointer relative to said touch surface.

58. A touch system according to claim 57 wherein said processor ignores pointer co-ordinate data generated by said camera device when the certainty value associated therewith is below a threshold level.

59. An apparatus for detecting a pointer relative to a generally rectangular touch surface comprising:
at least two spaced imaging devices having overlapping fields of view encompassing said touch surface, said imaging devices being spaced in front of said touch surface and looking back to see said touch surface in three-dimensions as a perspective view with the perspective view including at least the four corners and sides of said touch surface, said imaging devices acquiring overlapping images from different viewpoints, each imaging device comparing each captured image with a mathematical model describing the boundaries of the touch surface to determine a subset of relevant pixels within the captured image and processing the subset of relevant pixels in each captured image to generate image data, said relevant pixel subset encompassing said touch surface; and
a processor receiving and processing image data generated by at least one of said imaging devices to determine the location of the pointer relative to said touch surface using triangulation.

60. An apparatus according to claim 59 wherein each imaging device is calibrated to establish the relationship between points (X,Y,Z) in its perspective view and points (x,y) in acquired images, each imaging device outputting pointer co-ordinate data when a pointer is captured in an acquired image.

61. An apparatus according to claim 60 wherein each imaging device is spaced in front of said touch surface a sufficient distance to inhibit its view of the entire touch surface from being obstructed.

62. An apparatus according to claim 61 wherein each imaging device also generates a certainty value representing the degree of certainty that the imaging device has positively identified the pointer in the acquired image.

63. An apparatus according to claim 62 wherein said certainty value is used by said processor to determine pointer co-ordinate data to be used to determine the position of said pointer relative to said touch surface.

64. An apparatus according to claim 63 wherein said processor ignores pointer co-ordinate data generated by said imaging device when the certainty value associated therewith is below a threshold level.

65. An apparatus for detecting a pointer relative to a touch surface comprising:
at least two spaced imaging devices having overlapping fields of view, each of said imaging devices being in front of the touch surface and looking back at the touch surface such that said imaging devices see said touch surface in three-dimensions as a perspective view including the boundaries of said touch surface, said imaging devices acquiring overlapping images from different viewpoints; and
processing structure processing image data generated by at least one of said imaging devices to determine the location of the pointer, wherein each imaging device is calibrated to establish the relationship between points (X,Y,Z) in its perspective view and points (x,y) in acquired images, each imaging device generating pointer co-ordinate data when a pointer exists in an acquired image and wherein during calibration external orientation parameters (X0,Y0,Z0) and (ω,φ,κ) of each imaging device are determined where:
(X0,Y0,Z0) is the spatial location of the optical center of the imaging device; and
(ω,φ,κ) are the orientation angles of the optical axis of the imaging device with respect to the three-dimensional co-ordinate system of the touch surface.

66. An apparatus according to claim 65 wherein during calibration internal orientation parameters f,x0,y0 and Δx,Δy of each imaging device are also determined where:
(Δx,Δy) represent distortion terms introduced due to the imperfect nature of a lens of the imaging device;
f is the focal length of the imaging device; and
(x0,y0) are the co-ordinates of the principal point of the imaging device.

67. An apparatus according to claim 66 wherein said relationship is expressed using collinearity equations as:



  
    x
    =
    
      
        x
        0
      
      -
      
        Δ
        x
      
      -
      
        
          fR
          1
        
        
          R
          3
        
      
    
  




  
    y
    =
    
      
        y
        0
      
      -
      
        Δ
        y
      
      -
      
        
          fR
          2
        
        
          R
          3
        
      
    
  



where:
(x,y) are the co-ordinates of a point in a captured image corresponding to a point (X,Y,Z) in the three-dimensional perspective view; and
(R1,R3R3) are terms depending on point (X,Y,Z), the spatial location (X0,Y0,Z0)and the orientation angles (ω,φ,κ).

68. An apparatus according to claim 67 wherein during calibration, calibration points (X,Y,Z) on said touch surface and image points (x,y) corresponding to said calibration points are measured, said collinearity equations being solved using said measured calibration and image points thereby to determine said external and internal orientation parameters.

69. An apparatus according to claim 68 wherein said collinearity equations are solved using a least-squares method.

70. An apparatus according to claim 68 wherein said calibration points are at spaced locations along the periphery of said touch surface.

71. An apparatus according to claim 70 wherein said calibration points are located at the corners and edge mid-points of said touch surface.

72. An apparatus according to claim 65 wherein said external orientation parameters are determined using a vanishing point method.

73. An apparatus according to claim 72 wherein the determined external orientation parameters are refined using a least-squares method.

74. An apparatus according to claim 72 wherein said external and internal orientation parameters are determined using planar homography.

75. An apparatus according to claim 72 wherein said external orientation parameters are determined using a three point method.