Camera-based touch system

ES 2 396 587 T3

CAMERA-BASED METHOD AND TOUCH DEVICE

DESCRIPTION

TECHNICAL FIELD

[0001] The present invention relates in general to touch systems and in particular to a camera-based touch system.

BACKGROUND TECHNIQUE

[0002] 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 to generate user input. The pointer contacts with the touch surface are detected and used to generate the corresponding output depending on the areas of the touch surface where the contacts are made. There are basically two general types of touch systems available and they can be globally classified as "active" touch systems and "passive" touch systems.

[0003] Active touch systems allow the user to generate user input by contacting the touch surface with a special pointer that typically requires some form of integrated power source, typically batteries. The special pointer emits signals such as infrared light, visible light, ultrasonic frequencies, electromagnetic frequencies, etc. that activate the touch pad.

[0004] Passive touch systems allow the user to generate user input by contacting the touch surface with a passive pointer and do not require the use of a special pointer to activate the touch surface. A passive pointer can be a finger, a cylinder of some material, or any suitable object that can be used to make contact with some predetermined area of ​​interest on the touch surface.

[0005] Passive touch systems provide advantages over active touch systems in that any pointing device, including a user's finger, can be used as a pointer to make contact with the touch surface. As a result, user input can be easily generated. Also, since special active pointers are not required in passive touch systems, there is no concern for users about battery charge levels and / or pointer damage, theft or loss of the pointer.

[0006] Passive touch systems have a number of applications relating to the operation of computer and video displays. For example, in an interactive application as disclosed in US Patent No. 5,448,263 to Martin, assigned to the assignee of the present invention, a passive touch system is coupled to a computer and the computer screen is displayed on the screen. touch surface

ES 2 396 587 T3 of the touch screen. Coordinates representing specific locations on the touch pad are mapped onto the computer screen. When a user makes contact with the touch surface, the contact position coordinates are fed back to the computer and mapped onto the computer screen thus allowing the user to operate the computer in a manner similar to simply using a computer mouse. by contacting the touch surface. Additionally, the coordinates fed back to the computer can be recorded in an application and re-represented at a later time. Registration of contact coordinates is typically performed when it is desired to record information written or drawn by the user on the touch surface.

[0007] The resolution of a passive touch screen determines whether the touch system is suitable for recording information written or drawn on the touch screen or only useful for the selection of areas on the touch screen mapped to regions on the computer screen or video to manipulate the computer or video screen. Resolution is typically measured in dots per inch (DPI). DPIs are related to the size of the touch screen and the sampling ability of the touch system hardware and software used to detect contacts on the touch surface. [0008] Low resolution passive touchscreens only have enough DPI to detect contacts on the touch surface within a large group of pixels displayed by the computer or video screen. Therefore, these low resolution passive touchscreens are only useful for computer screen or video manipulation.

[0009] On the other hand, high resolution passive touchscreens have enough DPI to detect contacts that are proportional to a small number of pixels or sub-pixels of the computer or video screen. However, a requirement of high-resolution touchscreens is the ability to detect when the pointer is in contact with the touch surface. This is necessary for writing, drawing, mouse click operations, etc. Without the ability to detect pointer contact with the touch screen, writing and drawing would be a continuous operation and mouse clicks would not be possible making manipulation of the computer screen virtually impossible. A secondary requirement is the ability to detect when the pointer is “hovering over” the touch surface. Although not required for writing or drawing, current computer operating systems are increasingly using overhead motion information to manipulate computer or video screens or pop-up information boxes.

[0010] Passive touchscreens are typically either of the analog resistive type,

ES 2 396 587 T3 of the surface acoustic wave (SAW) type or of the capacitive type. Unfortunately, these touchscreens suffer from a number of problems or drawbacks as will be described.

[0011] Analog resistive touchscreens typically have a high resolution. Depending on the complexity of the touch system, the resolution of the touch screen can produce 4096x4096 DPI or higher. Analog resistive touchscreens are constructed using two flexible sheets that are coated with a resistive material and arranged as a sandwich. The sheets do not come into contact with each other until a contact is made. The sheets are typically kept separated by micro isolation points or by an isolation air gap. The sheets are constructed of ITO, which is primarily transparent. Therefore, the touch screen introduces some image distortion although very little parallax.

[0012] During the operation of an analog resistive passive touch screen, a uniform voltage gradient is applied in one direction along a first of the sheets. The second sheet measures the tension along the first sheet when the two sheets contact each other as a result of a contact made on the touch surface. Since the stress gradient in the first sheet can be translated into a distance along the first sheet, the measured stress is proportional to the position of the contact on the touch surface. When a contact coordinate is acquired on the first sheet, the uniform stress gradient is then applied to the second sheet and the first sheet measures the stress along the second sheet. The second sheet stress gradient is proportional to the distance along the second sheet. These two contact coordinates represent the contact XY position on the touch surface in a Cartesian coordinate system.

Unfortunately, since mechanical pressure is required to bring both sheets into contact, analog resistive touchscreens can only detect contact when there is enough pressure to bring the two sheets together. Analog resistive passive touchscreens also cannot detect when a pointer is moving over the touch surface. Thus, in the case of analog resistive touchscreens, contact events and positions can only be detected when actual contact is made with the touch surface.

[0014] Surface acoustic wave (SAW) touchscreens typically provide medium resolution and are not suitable for recording good writing quality. SAW touchscreens employ transducers on the edges of a glass surface to vibrate the glass and produce acoustic waves that ripple across the glass surface. When contacts are made

ES 2 396 587 T3 on the glass surface, the acoustic waves are reflected back and the contact position is determined from the mark of the reflected acoustic waves.

Unfortunately, SAW touchscreens exhibit remarkable parallax due to the thickness of the vibrating glass that is placed on the surface of the video or computer screen. Also, contact events and positions can only be detected when actual contact is made with the glass surface. Additionally, SAW touchscreens don't go beyond a few feet diagonally.

[0016] Capacitive touchscreens provide low resolution because contacts can only be determined over large areas (approximately 12.7mm x 12.7mm (½ x ¹Λ ”)). As a result, capacitive touch screens cannot be used for writing or drawing registration but are suitable for selecting areas on the touch screen that correspond to buttons generated by the computer and displayed on the video or computer screen. Capacitive touchscreens also suffer disadvantages in that they are sensitive to temperature and humidity. Similar to analog resistive touchscreens and SAW touchscreens, capacitive touchscreens can only detect contact events and positions when actual contact is made with the touch surface.

[0017] The scalability of passive touchscreens is important as the demand for large electronic digitizers is increasing. Where digitizers were once small desktop applications, today they have found their way into electronic whiteboard applications. The need to build a passive touch sensitive "wall" has become a requirement for new touch screen applications. Existing passive touchscreens of the types discussed above are all limited in their maximum size as long as they must remain functional.

[0018] WO 99/40562 relates to a computer video camera touch screen system in which a method and system for inputting data into a computer through a computer monitor screen is disclosed. A standard PC video camera mounted above the computer screen monitors the area immediately in front of the screen. An optical system similar to a periscope located behind the video camera causes two images to be recorded in the foreground of the screen by the camera viewed simultaneously from a different angle. This prior art is recognized in the preamble of claims 1 and 6.

ES 2 396 587 T3

[0019] US 4,746,770 relates to a method and apparatus for isolating and manipulating graphic objects on a computer video monitor. A frame member cooperates with a plurality of optical sensors and a plurality of light-blocking objects that tend to obstruct a portion of the light normally received by optical sensors.

[0020] DE 19810452 relates to an optical digitizer for determining the position of a pointer object that projects a light and that is arranged on a coordinate plane. In the optical digitizer, a detector is arranged on a periphery of the coordinate plane and has a field of view that covers the coordinate plane for receiving the light projected from the pointer object and for converting the received light into an electrical signal. .

As will be appreciated, improvements in passive touch systems are desired. It is therefore an object of the present invention to provide a novel camera-based touch system.

DISCLOSURE OF THE INVENTION

The invention is defined in claims 1 and 6.

Preferably, the at least two cameras are digital cameras that have fields of view that look generally along the plane of the touch surface. The image data generated by each digital camera includes a midline of the x-pointer and a location of the z-tip. Each of the digital cameras includes an array of pixels that have rows of selectable pixels. The pixel intensities of the pixels in the selectable pixel rows are used during the generation of the image data. Preferably, the pixel intensities of the pixels in a region of interest within the rows of selectable pixels are used during the generation of the image data.

[0024] In a preferred embodiment, each of the digital cameras includes a CMOS image sensor and a digital signal processor. The digital signal processor receives images output from the image sensor and executes a pointer search routine to determine if there is a pointer in each image acquired by the digital camera and, if so, the midline of the pointer. It is also preferred that the digital signal processor of each digital camera executes a base image update routine to update the base image after each image is acquired. Preferably, the digital signal processor of each digital camera determines the differences between each acquired image and the base image to detect the change in light conditions.

The present invention provides advantages for the passive touch system

ES 2 396 587 T3 is of high resolution and allows real pointer contacts with the touch surface as well as that movements of the pointer above the touch surface are detected and the corresponding output is generated. Also, the present passive touch system provides advantages in that it does not suffer from parallax, image distortion, pointer position restrictions, imaging, or the scalability problems associated with prior art passive touch systems.

[0026] Additionally, the present invention provides advantages in that due to the use of CMOS digital cameras, arbitrary pixel rows can be selected in the pixel arrays of the digital camera. This allows the frame rates of digital cameras to be increased significantly. Furthermore, since the rows of pixels can be arbitrarily selected, the pixel arrays can be exposed to longer durations for given digital camera frame rates allowing good operation in dark rooms as well as bright rooms.

BRIEF DESCRIPTION OF THE DRAWINGS

The embodiment of the present invention will now be more fully described with reference to the accompanying drawings in which:

Figure 1 is a schematic diagram of a camera-based touch system in accordance with the present invention;

Figure 2 is an isometric view of a touch screen that is part of the touch screen of Figure 1, Figure 3 is an isometric view of a corner portion of the touch screen of Figure 2;

Figure 4 is a schematic diagram of a digital camera that forms part of the touch screen of Figure 2;

Figure 5 is a schematic diagram of a master controller that is part of the touch system of Figure 1;

Figure 6 is a flowchart showing the steps performed during the execution of a Process Box routine;

Figure 7 is a flow chart showing the steps performed during the execution of a Pointer segment routine;

Figure 8 is a flow chart showing the steps performed during the execution of a pointer routine;

Figure 9 shows an image acquired by a digital camera and a pixel subset of the image being processed;

Figure 10 shows a region of interest (ROI) within the subset of

ES 2 396 587 T3 pixels of Figure 9;

Figure 11 shows the triangulation geometry used to calculate a contact position of the pointer on the touch surface of the touch screen illustrated in Figure 2;

Figure 12 shows an image acquired by a digital camera including the tip of the pointer and its midline;

Figure 13 shows pointer contact and movement above the pointer with different pointer orientations;

Figure 14 is an image of the touch screen of the touch screen as viewed by a digital camera;

Figures 15 and 16 show the results of a Matlab simulation of pointer tracking using a Kalman filter; and Figures 17a to 17d show the results of another Matlab simulation of pointer tracking using a Kalman filter.

BEST WAY TO CARRY OUT THE INVENTION

Turning now to Figure 1, a camera-based touch system in accordance with the present invention is shown and is generally identified by reference numeral 50. As can be seen, touch system 50 includes a screen touch 52 connected to a master controller 54 based on a digital signal processor (DSP). The master controller 54 is also connected to a computer 56. Computer 56 executes one or more application programs and provides screen output that is displayed on touch screen 52 by means of projector 58. Touch screen 52, master controller 54, computer 56 and projector 58 form a closed loop so that user contacts with touch screen 52 can be recorded as writing or drawing or used to control the execution of application programs run by computer 56.

[0029] Figures 2 through 4 better illustrate touch screen 52. Touch screen 52 includes a touch surface 60 surrounded by a rectangular frame 62. Touch surface 60 is in the form of a flat rectangular sheet of passive material. . The DSP-based CMOS 63 digital cameras are associated with each corner of the touch screen 52. Each digital camera 63 is mounted on a frame assembly 64. Each frame assembly 64 includes an angled support plate 66 on which the digital camera 63 is mounted. The support frame elements 70 and 72 are mounted on the plate 66 via posts 74 and secure the plate 66 to the frame. 62.

[0030] Each digital camera 63 includes a two-dimensional CMOS image sensor and associated lens assembly 80, a first-in-first-in buffer.

ES 2 396 587 T3 exit (FIFO) 82 connected to the image sensor and a set of lenses 80 via a data bus and a digital signal processor (DSP) 84 connected to the FIFO 82 via a data bus and the sensor image and lens assembly 80 via a control bus. Also included are a bootable EPROM 86 and a power supply subsystem 88.

[0031] In the present embodiment, the image sensor of the CMOS camera is a Photobit PB300 image sensor configured for a 20x640 sub-array of pixels that can be operated to capture image frames at rates above 200 frames per given second. that rows of pixels can be arbitrarily selected. Furthermore, since the rows of pixels can be arbitrarily selected, the pixel sub-array can be exposed to a longer duration for a given digital camera frame rate allowing good performance in dark rooms as well as in bright rooms. The FIFO 82 buffer is manufactured by Cypress under catalog number CY7C4211V and the DSP 84 is manufactured by Analog Devices under catalog number ADSP2185M.

The DSP 84 provides control information to the image sensor and lens assembly 80 via the control bus. The control information allows DSP 84 to control image sensor and lens assembly 80 parameters as well as exposure, gain, array setting, reset, and initialization. The DSP 84 also provides clock signals to the image sensor and lens assembly 80 to control the frame rate of the image sensor and lens assembly 80.

[0033] The angle of plate 66 is selected so that the field of view (FOV) of each digital camera 63 extends beyond a peripheral design edge of touch surface 60 as shown in Figure 11. From In this way, the entire touch surface 60 is within the fields of view of digital cameras 63.

The master controller 54 is best illustrated in Figure 5 and includes a DSP 90, a boot EPROM 92, a serial line controller 94, and a power supply subsystem 95. The DSP 90 communicates with the DSPs 84 of the digital cameras 63 via data bus via serial port 96 and communicates with computer 56 via data bus via serial port 98 and serial line controller 94. In the present embodiment the DSP 90 is also manufactured by Analog Devices under the catalog number ADSP2185M. The 94 series line controller is manufactured by Analog Devices under catalog number ADM222.

The master controller 54 and each digital camera 63 follow a communication protocol that allows two-way communications over a cable.

ES 2 396 587 T3 common serial similar to a universal serial bus (USB). The transmission bandwidth is divided into thirty-two (32) 16-bit channels. Of the thirty-two channels, six (6) channels are assigned to each of the DSPs 84 in digital cameras 63 and DSP 90 in the master controller 54 and the remaining two (2) channels are left unused. The master controller 54 supervises the twenty-four (24) channels assigned to the DSPs 84 while the DSPs 84 supervise the six (6) channels assigned to the DSP 90 of the master controller 54. Communications between the master controller 54 and the digital cameras 63 are They perform as background processes in response to interrupts.

The general operation of touch system 50 will now be described. Each digital camera 63 acquires images from touch surface 60 within the field of view of its image sensor and lens array 80 at a desired frame rate and processes each image. acquired to determine if there is a pointer in the acquired image. If there is a pointer in the acquired image, the image is further processed to determine the characteristics of the pointer contact or movement above the touch surface 60. The pointer information packets (PIPS) are then generated by the digital cameras 63 They include pointer characteristics, status, and / or diagnostic information and the PIPs are queued for transmission to the master controller 54. Digital cameras 63 also receive and respond to PIP commands generated by master controller 54.

[0037] The master controller 54 queries the PIPs of the digital cameras 63. If the PIPs include pointer characteristics information, the master controller 54 triangulates the pointer characteristics in the PIPs to determine the position of the pointer relative to the touch surface. 60 in Cartesian rectangular coordinates. The master controller 54 in turn transmits the calculated pointer position data, status and / or diagnostic information to the personal computer 56. In this way, the pointer position data transmitted to the personal computer 56 can be recorded as writing. or drawing or can be used to control the execution of application programs executed by the computer 56. Computer 56 also updates screen output transferred to projector 58 so that information displayed on touch surface 60 reflects pointer activity.

The master controller 54 also receives commands from the personal computer 56 and responds accordingly and also generates and transfers PIP commands to the digital cameras 63.

[0039] Details concerning the processing of the acquired images and the triangulation of the pointer characteristics in the PIPs will now be described.

ES 2 396 587 T3 with reference in particular to Figures 6 to 8.

Initially, a camera deflection angle calibration routine is performed to determine the deflection angle δ of each digital camera 63 (see Figure 11) so that the contact or contact position can be accurately determined. movement above a pointer relative to touch surface 60. Details of the camera offset angle calibration are described in Applicants' United States Application, pending together with this present, entitled "Calibrating Camera Offsets to Facilitate Object Position Determination Using Triangulation, filed June 1, 2001. .

Following the camera deflection angle calibration routine, a surface detection routine is performed to improve the determination of when a pointer is in contact with touch surface 60 at a given point or moving above the touch pad.

[0042] With the rectangular coordinates of a pointer in the plane of the touch surface 60 precisely known from the calibration of the offset angle of the camera, the orientation of the touch surface 60 can be determined as seen by each digital camera 63. This is necessary due to the fact that digital cameras not only see along the plane of the touch surface 60 but also in a direction perpendicular to it. To some degree, each digital camera 63 looks down into touch surface 60. Figure 14 generally shows the shape of touch surface 60 as seen by digital camera 63. Because of this, it is desired to define a coordinate "Vertical" z describing the location of the touch pad as a function of rectangular x and y coordinates.

[0043] The z-coordinate of the pointer can be measured from a digital camera image, and from there, the z-coordinates for the pointer positions on the surface can be determined and the z-coordinate for given rectangular x and y coordinates. Vertical calibration can be described as a surface of the form:

2 (x, y) = Ax + By + Cx²+ Dy¹+ E ^ + F (0-1)

Note that if the coefficients C, D, and E are zero, it becomes a plane. The fit is easily calculated since equation (0,1) represents a linear least squares problem. The corresponding matrix will take the form:

ES 2 396 587 T3

<td></td><td></td><td></td><td></td><td></td><td></td><td>Ύ</td><td colspan="2"></td>

<td> ’*&gt;</td><td>X</td><td></td><td></td><td> *1/</td><td> 1'</td><td>B</td><td></td><td> *1</td>

<td></td><td>Λ</td><td>χϊ</td><td></td><td></td><td> 1</td><td>C</td><td>₌</td><td>^zí</td>

<td>^:·</td><td></td><td></td><td></td><td>i</td><td>^:·</td><td>D</td><td></td><td></td>

<td>Λ</td><td>Y"</td><td></td><td>Y"</td><td></td><td> 1</td><td>AND</td><td></td><td> -²&gt; r,</td>

[0044] To adjust the rectangular coordinates xe and to equation (0,1) to determine the coefficients from A to E, the Moore-Penrose pseudo inverse procedure is used which is based on singular value decomposition (SVD ) to determine a least squares solution with normal least.

As will be appreciated, a matrix can always be decomposed as follows:

<img file="ES2396587T3_D0001.tif" />

[0046] Matrix A can have any shape. The matrices U and V are orthogonal matrices, which means that:

<img file="ES2396587T3_D0002.tif" />

The diagonal matrix S is completely composed of the singular values ​​of matrix A, which are related to the squares of the eigenvalues ​​of matrix A. The importance of singular value decomposition (SVD) rests on the fact that that with it, the inverse of matrix A can always be calculated. Furthermore, it is possible to control this inversion when a poorly determined problem is encountered. Consider the system of linear equations:

<img file="ES2396587T3_D0003.tif" />

whose solution would be:

<img file="ES2396587T3_D0004.tif" />

[0048] The SVD allows to write the inverse of the matrix A as:

A ~ '= VS-'U^r (03) since both matrices U and V are orthogonal. In a situation poorly

ES 2 396 587 T3 determined, some of the singular values ​​will be very small, so when the matrix S is formed¹, large values ​​will be produced, which is not desirable. In this case, the inverses of the smallest singular values ​​are set to zero. This has the effect of removing the poorly determined part of the solution. For least squares problems, this is a powerful tool. The usual normal equation procedure for least squares problems is based on solving:

<img file="ES2396587T3_D0005.tif" />

(0.4) in the overdetermined case, and solve:

(0.5) in the case below determined. As will be appreciated, during the fitting of the system of equations to equation (0,1), the same procedure is used that was used during the determination of the camera deflection angles δ. Since the same procedure is used, memory usage and processing speed are kept at desired levels.

[0049] With the known coefficients A to E, the z-coordinate can be calculated for any given point (x, y) on the touch surface and thus, a determination can be made as to whether a pointer is in contact with touch pad 60 or by moving over it.

With the touch system 50 calibrated, during operation each digital camera 63 acquires images of the touch surface 60 within its field of view. Images are acquired by the image and lens assembly 80 at intervals in response to clock signals received from the DSP 84. Each image acquired by the image and lens assembly 80 is sent to the FIFO buffer 82. The DSP 84 in turn reads each image from FIFO buffer 82 and processes the image. To avoid processing significant numbers of pixels that do not contain useful information, only a subset of the pixels in the acquired image is processed as shown in Figure 9.

[0051] During the processing of an image acquired by a digital camera 63, the DSP 84 executes a frame processing routine as shown in Figure 6. When an image is available for processing (step 120), a check is made for determine if the image was captured for the purpose of adjusting the

ES 2 396 587 T3 digital camera 63 (step 122). If the image was acquired for the purpose of exposure adjustment, an Exposure control routine (step 124) is called to adjust the exposure of the digital camera 63. Following this, the DSP 84 waits for the reception of the next image available for processing.

In step 122, if the image has not been captured for the purpose of adjusting the exposure of the digital camera 63, a check is made to determine whether the image has been captured for the purpose of replacing the base image ( step 126). If the image has been acquired for the purpose of replacing the base image, a base capture routine is called (step 128) and the acquired image is used as the base image. This is done if the digital camera acquires an image and sends a PIP to the master controller indicating that there is a pointer in the image when it is actually noise. Replacing the base image effectively inhibits the digital camera from falsely identifying a pointer in future PIPs. Following this, the DSP 84 waits for the reception of the next available image for processing.

[0053] In step 126, if the image has not been captured in order to replace the base image, a current copy I routine is called by the DSP 84 (step 130). During this routine, the current acquired image is copied into memory and used to update the base image as well as to form a difference image representing the differences between the current acquired image and the base image.

[0054] After completing the current copyI routine, a Pointer segment routine is called (step 132) to determine if there is a pointer in the acquired image and if so to determine the location of the pointer relative to touch surface 60 and if the pointer is in contact with or moving over the touch surface 60. The Pointer segment routine 132 also allows detection of the change in light conditions. Following the Pointer segment routine 132, the DSP 84 calls the PIP fill routine (step 134) to place the pointer information and light conditions in a PIP for transmission to the master controller 54. Subsequently, the DSP 84 waits for reception. of the following image available for processing.

[0055] Figure 7 illustrates the steps performed by the DSP 84 during the execution of the Pointer segment routine 132. As can be seen, when the DSP 84 executes the Pointer segment routine 132, the DSP 84 calls the Pointer search routine to determine if there is a pointer in the acquired image and if so, the position of the pointer in the current acquired image (step 140). Upon completion of the pointer search routine 140, the DSP 84 calls the updateBase routine to update the base image and thereby manage changes in lighting conditions (step 142).

[0056] During the execution of the updateBase routine, the DSP 84 updates

ES 2 396 587 T3 continuously the base image using the equation:

<img file="ES2396587T3_D0006.tif" />

in which:

B_{n + 1} it is the new base image;

B_n is the current base image;

I is the current acquired image;

i, j are the row and column coordinates of the base image pixels being updated; ya is a number between 0 and 1 that indicates the degree of learning that should be taken from the current acquired image I. The higher the value of a, the faster the base image is updated.

[0057] After the updateBase routine 142 has been executed, the intensity difference between the current acquired image and the base image is calculated by the DSP 84. This information is sent to the master controller 54 to allow the master controller to determine if the digital camera 63 needs to be re-exposed. This would be required if there is a drastic change in lighting conditions (i.e. ambient light was turned on or off). When re-exposure of digital camera 63 is required, master controller 54 sends a PIP command to digital camera 63 instructing the digital camera to acquire an image for exposure adjustment.

[0058] Figure 8 illustrates the steps performed by the DSP 84 during the execution of the pointer routine 140. As can be seen, when the DSP 84 executes the pointer routine 140, the DSP 84 clears the location of the pointer and the parameters of the pointer tip x and z respectively (step 150). A vertical intensity histogram is subsequently constructed (step 152). During this stage, the difference image representing the differences between the current image and the base image is formed and the intensities of the pixels in the difference image are summed per column. In this way, a 640 x 1 vector is formed that represents the sum of each column in the 640 x 20 difference image. Thus, the first element in the 640 x 1 vector represents the sum of the 20 pixels in the first column of the 640 x 20 difference image, the second element in the 640 x 1 vector represents the sum of the 20 pixels in the second column of the 640 x 20 difference image and so on. Additional details of this process can be found in the article entitled A smart camera application: DSP - based people detection and tracking by V. Cheng et al. and published in the SPIE Journal of Electronic Imaging, July

ES 2 396 587 T3 of 2000.

After the creation of the vertical intensity histogram in step 152, the pointer location parameter x is determined by searching for the column in the vertical intensity histogram with the highest intensity above the noise threshold (step 154). The column is used as the center of a region of interest (ROI) to be processed, the width of the ROI being equal to the base of the peak formed by the vertical intensity histogram (see Figure 10). If neither column has an intensity above the noise threshold, it is assumed that there is no pointer within the acquired image.

[0060] When determining a pointer location parameter x, the DSP 84 analyzes the ROI to determine the row of pixels where the pointer tip is located and determine whether that row represents touch surface contact or movement by above (step 156). Specifically, the DSP 84 creates a binary mask on the ROI so that the white pixels represent the pointer and the black pixels represent the base as shown in Figure 12. From the mask, the location of the midline of the pointer and the tip of the z pointer can be easily calculated.

[0061] During the PIP fill routine 134, the DSP 84 uses the pointer and light condition information acquired during the execution of the Pointer segment routine 132 and creates a PIP to reduce the acquired image to a small data set to provide input. thus an economy in bandwidth. The PIP is in the form of a six (6) word packet, each word in the packet being sixteen (16) bits. The PIP typically takes the form:

<td>Headboard</td><td>Data</td><td>Checksum</td>

The header portion of the PIP is typically sixteen (16) bits and includes a destination / source field, a data type field, an image frame number field, a sequence number field and a package number field. The destination / source field identifies the destination of the PIP and the source of the PIP. If the PIP is generated by the master controller 54, the destination may be a single digital camera 63 or all digital cameras. The data type indicates whether the PIP refers to pointer information or to other information such as status and diagnostic information. The image frame number field stores a number so that the images from each digital camera 63 are processed by the master controller 54 in sequence. The sequence number field stores a number that relates the PIP to other PIPs.

ES 2 396 587 T3

The package number field stores a number that identifies the package.

[0063] The data portion of the PIP is typically sixty-four (64) bits and includes a pointer ID field, a pointer location parameter field, a pointer tip parameter field, a contact status and a pointer kindness field. The pointer ID field stores a pointer identifier to allow tracking of multiple pointers. The pointer location parameter field stores the value x calculated by the DSP 84. The pointer tip parameter field stores the z-value calculated by the DSP 84. The contact status field stores a value that indicates whether the pointer is in contact, not in contact, or possibly in contact with the touch surface 60. pointer goodness field stores a statistical value about the probability that the detected pointer is real.

The checksum part of the PIP is used to ensure integrity in the transmission of the PIP. If PIP checksum errors are rare, the checksum errors displayed by PIPs are ignored by the target device.

[0065] Status PIPs that do not refer to pointer information have a different shape than the identified PIPs described above. For PIPs of this nature, the data part includes an instruction type field, an instruction code field, and a data field. The instruction type field identifies whether the instruction type is an instruction to be executed or a status request. The instruction code field stores the actual instruction or identifier of the request status. The data field stores data that varies depending on the type of instruction. Examples of status PIPs include frame header PIPs, command PIPs, and error message PIPs.

[0066] A frame header PIP typically includes the number of pointer PIPs to follow for a current acquired image with statistics for the current image such as intensity variation between the current acquired image and a previous image. A command PIP sent by master controller 54 can instruct a digital camera to adjust one or more of its settings such as exposure or image capture to be used as a new base image. An error PIP can pass an error condition from a digital camera 63 to the master controller 54 for storage in an error log.

Each digital camera 63 processes each image it acquires in the manner described above in response to each clock signal generated by its DSP 84. The PIPs created by the DSPs 84 are only sent to the master controller 54 when the cameras

ES 2 396 587 T3 digitals 63 are queried by the master controller 54.

[0068] When the master controller 54 queries the digital cameras 63, frame sync pulses are sent to the digital cameras 63 to initiate transmission of the PIPs created by the DSPs 84. Upon receipt of a frame sync pulse , each DSP 84 transmits the PIP to the master controller 54 via the data bus. PIPs transmitted to master controller 54 are received via serial port 96 and automatically stored in DSP 90.

[0069] After the DSP 90 has queried the digital cameras 63 and received the PIPs from each of the digital cameras 63 that include pointer information, the DSP 90 processes the PIPs using triangulation to determine the location of the pointer. relative to touch surface 60 in (x, y) coordinates. Specifically, PIPs from pairs of digital cameras 63 are processed using triangulation.

[0070] Figure 11 shows that two angles are needed f_cam1 and f_cam2 to triangulate the position (x0, y0) of a pointer relative to the touch screen 60. The PIPs generated by each digital camera 63 include a number Θ (see Figure 12) that identifies the midline or tip of the pointer. When the master controller 54 receives a PIP from a digital camera 63, the master controller uses the number representing the midline or tip of the pointer and the digital camera's field of view to calculate an angle f_camusing the equation:

<img file="ES2396587T3_D0007.tif" />

(0.7) in which:

x is the number that represents the middle line or tip of the pointer; and at that full length enclosed by the digital camera's field of view (FOV) at a distance from the camera.

The calculated angle is equal to the angle formed between the extremity of the field of view that extends beyond the edge of the design periphery of the touch surface 60 of the digital camera 63 that generated the PIP and a line that extends from the optical axis of the digital camera that crosses the pointer within the acquired image. Preferably, the extremity of the field of view extends beyond the designated peripheral edge (ie in this case the x-axis) of touch surface 60 within the field of view by a known amount. However, in almost all cases the

ES 2 396 587 T3 angular deviation d_cam Scanning of each digital camera 63 is different and unknown.

[0072] Once the master controller 54 calculates the angle f_cam, master controller 54 uses camera offset angle 5_cam determined during camera offset calibration to adjust angle f_cam. With the two available angles and with the angles f_cam adjusted, the master controller 54 uses the angles f_cam to determine the position of the pointer relative to the touch surface 60 using triangulation.

In the present embodiment, since the touch screen 52 includes four digital cameras 63, six pairs of digital cameras can be used for triangulation. The following explanation describes how the position of a pointer is determined by triangulating each pair of 63 digital cameras.

[0074] To determine a pointer position using PIPs received from digital cameras 63 along the left side of touch screen 52, the following equations are used to determine the coordinates (x₀, Y₀) of the pointer position, given the angles φ₀ and φ₁ for upper and lower digital cameras:

<img file="ES2396587T3_D0008.tif" />

so{₀) + tan (?) (0.9) in which:

h is the height of the touch screen 52, that is the vertical distance from focal point to focal point of digital camera;

w is the width of the touch screen 52, that is the horizontal distance from focal point to focal point of digital camera; and φ, is the angle with respect to the horizontal, measured using digital camera i and equation (0.7).

[0075] For digital cameras 63 along the right side of touch screen 52, the following equations are used to determine the coordinates (x0, y0) of the pointer position, given the angles φ2 and φ3 for digital cameras upper and lower:

ES 2 396 587 T3 ¹ w * tan (^) + tan (^)) ^⁰¹⁰^ so (&amp;) ^Y° tan ^ J + tan ^ j) ^⁰¹¹^

[0076] The similarity between equations (0.8) and (0.10) should be evident, that is equation (0.10) = 1 - equation (0.8) once the angles φ have been substituted₂ and φ₃ in equation (0,8) by the angles φ₀ and φ₁ respectively. Equations (0.9) and (0.11) are related in a similar way.

[0077] To determine a pointer position using digital cameras 63 along the bottom of touch screen 52, the following equations are used to determine the coordinates (x₀, Y₀) of the pointer position, given the angles φ₀ and φ3 for the lower left and lower right digital cameras:

<img file="ES2396587T3_D0009.tif" />

<img file="ES2396587T3_D0010.tif" />

[0078] To determine a pointer position using digital cameras 63 along the top of touch screen 52, the following equations are used to determine the coordinates (x₀, Y₀) of the pointer position, given the angles φ₁ and φ₂for the upper left and upper right digital cameras:

(014) ₌ tanfo) tan (^) + tan (&amp;)

<img file="ES2396587T3_D0011.tif" />

[0079] The similarity between equations (0.12) and (0.14) should be evident, ie equation (0.14) = equation (0.12) once the angles φ have been substituted₁ and φ₂ in equation (0,12) by the angles φ₀ and φ₃. Equations (0,13) and (0,15) have the following

ES 2 396 587 T3 relation: equation (0,15) = 1 - equation (0,13) after the angles φ have been substituted₁ and φ₂ in equation (0,13) by the angles φ₀ and φ₃ respectively.

[0080] To determine a pointer position using digital cameras 63 across the diagonal from the lower left to the upper right, the following equations are used to determine the coordinates (x₀, Y₀) of the pointer position, given the angles φ0, any φ2 for the lower left and upper right digital cameras:

<img file="ES2396587T3_D0012.tif" />

<img file="ES2396587T3_D0013.tif" />

[0081] To determine a pointer position using digital cameras 63 across the diagonal from the lower right to the upper left, the following equations are used to determine the coordinates (x₀, Y₀) of the pointer position, given the angles φ1 and φ3 for the lower right and upper left digital cameras:

<img file="ES2396587T3_D0014.tif" />

<img file="ES2396587T3_D0015.tif" />

[0082] The similarity between equations (0.16) and (0.18) should be evident, ie equation (0.18) = equation (0.16) once the angles φ have been substituted₁ and φ₃ in equation (0,16) by the angles φ₀ and φ₂. Equations (0,17) and (0,19) have the following relationship: equation (0,19) = 1 - equation (0,17) after the angles φ have been substituted₁ and φ₃ in equation (0,17) by the angles φ₀ and φ₂ respectively.

[0083] As will be appreciated, the above equations generate the x-coordinates₀ hey₀ on a scale of [0, 1]. Therefore, any appropriate coordinate scale can be reported by multiplying x₀ hey₀ by the maximum value of X and the maximum of Y respectively.

In the present embodiment, the DSP 90 calculates the position of the pointer using triangulation for each pair of digital cameras excluding diagonal pairs. I know

ES 2 396 587 T3 then averages the resulting pointer positions and the resulting pointer position coordinates are queued for transmission to personal computer 56 via serial port 98 and serial line controller 94.

[0085] With the position (x, y) of a pointer known by triangulation, using the coefficients from A to E calculated during the calibration of the surface detection, the z-coordinate corresponding to the position (x, y ) using equation (0,1). Calculating the z coordinate and comparing the z coordinate with the z parameter in the PIP provide an indication of whether the pointer is moving above touch surface 60 or in actual contact with the touch surface.

[0086] If desired, a velocity v and an angle of the pointer can be calculated by the DSP 90 as shown in Figure 13. The velocity of the pointer is calculated by examining changes in the z-position (or x-intercept) of the pointer in successive PIP and knowing the frame rate of the camera. For example, if the camera's frame rate is 200 frames per second and the z-position changes by 1 row of pixels per frame, the pointer speed is 200 pixels per second.

[0087] The angle of the pointer can be determined due to the fact that the PIP includes the x-intercepts in the pixel rows 0 and 19 of the midline. Since the distance x (the difference between x-intercepts) and the distance y (the number of rows of pixels) are known, all the information needed to calculate the pointer angle is available.

[0088] If desired, a Kalman filter (essentially a recursive least squares procedure) can be used to effectively "follow" the pointer when it is within a certain distance of the touch surface 60. To do this, it is It is necessary to define a system of equations or model to use in the filter. Since the master controller 54 is capable of providing both the z-position and the pointer velocity v, the following description can be used:

<img file="ES2396587T3_D0016.tif" />

<img file="ES2396587T3_D0017.tif" />

The second of these equations is required since the filter must know what to do with the velocity, and also since both z and v are measurable. Define the state vector as:

[zv]^T

To relate the state of the system in two successive times n and n + 1, we write the

ES 2 396 587 T3 system of equations as a matrix difference equation:

<img file="ES2396587T3_D0018.tif" />

or, in matrix notation,

<img file="ES2396587T3_D0019.tif" />

Here, dt denotes the time interval between successive time stages. The term “process noise” is also introduced here on the RHS. It is purely formal, but part of the Kalman filter procedure. It is also necessary to specify how a measurement is entered into the procedure. This is done by means of a matrix equation:

<img file="ES2396587T3_D0020.tif" />

where z_n is a measurement of position and velocity, H is a "measurement matrix" which is taken to be the identity matrix, x_n is the state vector and w is the noise measurement. Essentially, the measurements are assumed to be noisy versions of the state vector. It is also necessary to define a covariance matrix associated with w. If the measurement error in z is 0.5 pixels, then the covariance matrix is:

<img file="ES2396587T3_D0021.tif" />

A similar matrix Q is required for the process noise introduced above, but since it is somewhat arbitrary, it can be treated as a tuning parameter for the filter. In this example, the matrix Q is taken to be the identity matrix multiplied by a factor of unit order or less. With the above stated, there is enough information to begin the filter process. The first stage (prediction) is:

Here, the notation (-) implies that the measurement has not been performed yet while (+) implies it (but in this case the (+) refers to the previous stage). Also, the matrix equation for the matrix P predicts a covariance matrix. The next stage is the

ES 2 396 587 T3 filter gain calculation:

<img file="ES2396587T3_D0022.tif" />

Once a measurement is made, the state estimate and its covariance can be updated:

(+) = í * (-) + κ&gt; h - a (-)] Λ (+) =&gt;;^ι(-) + ^ * Μ '

It is this estimate of state x that is used to determine whether or not touch-surface contact has occurred. Note that the matrices H and R are both constant with time and that only the matrices K and P change (in fact, P approximates a constant matrix). A further simplification takes place as there is no control process involved.

[0089] The results of a Matlab simulation of a Kalman filter were performed using a set of measurements representing a pointer approaching a touch surface 60 at a constant speed. Figures 15 and 16 illustrate the simulation, with a time step dt of 0.1 seconds and a measurement precision of 0.5 pixels. The open symbols represent the data, and the lines the state estimates from the Kalman filter. Clearly, the state estimate follows the data completely well.

[0090] A second simulation was performed in Matlab to take into account both vertical (z) and horizontal (x) pointer movement. This simulation is basically of two similar Kalman filters working together in a "parallel" fashion. The formulation is exactly the same, except that the double number of variables needs to be considered. Figures 17a to 17d show the simulation results and depict the movement of a pointer towards the touch surface 60 at a constant speed and with a slowly varying x-position (ie the person's hand is unstable).

[0091] Although the touch system 50 has been described as including a projector for presenting the images on the touch screen, those skilled in the art will appreciate that this is not required. The touch screen 52 can be transparent or translucent and placed on a display unit so that the image displayed on the display unit is viewable through the touch screen. Also, the touch screen does not need to be a rectangular sheet of material bordered by a frame. The touchscreen

ES 2 396 587 T3 can in fact be virtually any surface within the overlapping fields of view of two or more digital cameras.

Also, although the touch system 50 is described as including a separate master controller from the digital cameras, if desired, one of the digital cameras can be conditioned to function as both a camera and a master controller and query the PIPs. from the other digital cameras. In this case, it is preferred that the digital camera serving as the master controller includes a DSP 84 faster than the other digital cameras.

Furthermore, although the surface detection routine is described as determining the coefficients from A to E to be used with equation (0,1) for the calculation of the z-coordinates of the pointer at a given point ( x, y) relative to the touch screen, during the surface detection routine, the master controller 54 can be programmed to calculate the z coordinate for regions (x, y) unique to the touch surface and store the z coordinates in a look-up table (LUT). In this case; When a pointer appears in images captured by digital cameras and the position (x, y) of the pointer relative to the touch surface is determined, a decision can be made as to whether or not the pointer is in contact with the touch surface by comparing the z-coordinate on the LUT that corresponds to the region (x, y) in which the pointer is located, with the row of pixels in the image sensor and lens array in which the tip of the pointer is located.

[0094] As described above, master controller 54 calculates or looks up the touch screen z coordinates for each digital camera and compares the z coordinates with the z pointer tip location to determine if the pointer is in actual contact. with the touch pad. However, those skilled in the art will appreciate that DSPs 84 in digital cameras may include image processing software to determine if the pointer is in actual contact with the touch surface. This image processing can be done in conjunction with or in place of the pointer contact determination by the master controller.

[0095] Although a preferred embodiment of the present invention has been described, those skilled in the art will appreciate that variations and modifications can be made without departing from the scope of the invention as defined by the appended claims.