Camera-based touch system

IS 2 340 945 T3

DESCRIPTION

Procedure for a camera-based touch system.

Technical field

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

Previous technique

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 prompts. The contacts of the pointer with the touch surface are detected and used to generate corresponding outputs, according to 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 broadly classified as "active" touch systems and "passive" touch systems.

Active touch systems allow the user to generate user prompts by contacting the touch surface with a special pointer, which usually requires some form of an on-board power source, usually batteries. The special pointer emits signals, such as infrared light, visible light, ultrasonic frequencies, electromagnetic frequencies, etc., which activate the touch surface.

Passive touch systems allow the user to generate user prompts by contacting the touch surface with a passive pointer, and do not require the use of a special pointer in order 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 contact some predetermined area of ​​interest on the touch surface.

Passive touch systems provide advantages over active touch systems in that any suitable pointing device, including a user's finger, can be used as a pointer to contact the touch surface. C sa result, can easily generate a user indication. Also, since special active pointers are not needed in passive touch systems, battery power levels and / or damage, theft, or loss of the pointer are not of concern to users.

Passive touch systems have a number of applications that relate to the operation of the computer and the video viewer. 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 display is displayed on the screen. touch screen touch surface. The coordinates representing the specific locations on the touch surface are associated with the computer's display. When a user makes contact with the touch surface, the coordinates of the contact position are fed back to the computer and associated with the computer's viewer, thus allowing the user to operate the computer in a manner similar to using a computer mouse. simply by making contact with the touch surface. Additionally, the coordinates fed back to the computer can be saved in an application and redeployed at a later time. The recording of the contact coordinates is usually done when it is desired to record the information written or drawn on the touch surface by the user.

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 selecting areas on the touch screen associated with regions on the computer or video viewer, in order to manipulate computer or video viewer. 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.

Low resolution passive touchscreens have just enough DPI to detect the contacts on the touch surface in a large group of pixels displayed by the computer or video viewer. Therefore, these low resolution passive touchscreens are only useful for manipulating the computer or video viewer.

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 viewer. However, a requirement for 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 pulses would not be possible, thus making manipulation of the computer screen virtually impossible. A secondary requirement is the ability to detect when the pointer is "hovering" above the touch surface. Although not required for writing or drawing, today's computer operating systems are increasingly using glide information to manipulate the computer or video displays, or pop-up information boxes.

IS 2 340 945 T3

Passive touchscreens are typically either the analog resistive type, the surface acoustic wave (SAW) type, or the capacitive type. Unfortunately, these touchscreens suffer from a number of problems or drawbacks, as will be described.

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 more. Analog resistive touchscreens are constructed using two flexible sheets that are coated with a resistive material, and arranged like a sandwich. The sheets do not come into contact with each other until a contact has been made. The sheets are typically kept separated by insulating microdots or by insulating airspace. The sheets are constructed of ITO (Indium Tin Oxide), which is highly transparent. Thus, the touch screen introduces some image distortion but very little parallax.

During operation of an analog resistive passive touch screen, a uniform voltage gradient is applied in one direction along the first of the foils. The second sheet measures the voltage across the first sheet when the two sheets make contact with each other as a result of a contact made on the touch surface. Since the voltage gradient of the first sheet can be distanced along the first sheet, the measured voltage is proportional to the position of the contact on the touch surface. When a contact coordinate is acquired on the first sheet, the uniform voltage gradient is then applied to the second sheet, and the first sheet measures the voltage across the second sheet. The voltage gradient of the second sheet is proportional to the distance along the second sheet. These two contact coordinates represent the XY position of the contact 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 pick up when a pointer is hovering over the touch surface. Therefore, in the case of analog resistive touchscreens, contact events and positions can only be detected when actual contacts are made with the touch surface.

Surface acoustic wave (SAW) touchscreens typically provide medium resolution, and are not suitable for recording good quality handwriting. SAW touchscreens employ transducers on the edges of a glass surface to vibrate the glass and produce acoustic waves that wave across the glass surface. When a contact is made on the glass surface, the acoustic waves are retroreflected and the contact position is determined from the signature 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. Furthermore, events and contact positions can only be detected when effective contacts are made with the glass surface. Additionally, SAW touchscreens do not support adjustments beyond a few feet diagonally.

Capacitive touchscreens provide low resolution because contacts can only be determined over large areas (approximately 12.7mm x 12.7mm (1/2 inch x 1/2 inch)). As a result, capacitive touch screens cannot be used to record writing or drawings, but are suitable for selecting areas on the touch screen, corresponding to computer generated buttons displayed on the video or computer screen. Capacitive touchscreens also suffer from disadvantages in that they are sensitive to temperature and humidity. Similar to analog resistive touchscreens and SAW touchscreens, capacitive touchscreens can also only detect events and contact positions when effective contact is made with the touch surface.

The scalability of passive touchscreens is important as the demand for larger electronic digitizers is increasing. Where digitizers were once small desktop gadgets, 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 maximum size where they are still functional.

Document WO 99/40562 relates to a video camera computer touch screen system, wherein a method and system for inputting data to a computer via the 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 immediately below the video camera, causes two images on the front screen to be recorded by the camera simultaneously, viewed from different angles.

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 occlusion objects, which tend to obstruct a portion of the light normally received by the optical sensors.

DE 19810452 relates to an optical digitizer for determining a position of a pointer object that projects a light and which is arranged on a coordinate plane. In the optical digitizer, a

ES 2 340 945 T3 detector on the periphery of the coordinate plane, and has a field of view that covers the coordinate plane to receive the light projected from the pointing object, and to convert the received light into an electrical signal.

As will be appreciated, improvements are desired for passive touch systems. 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 claim 1.

The present invention provides advantages in that the passive touch system is of high resolution and allows effective contacts of the pointer with the touch surface, as well as that the hovering of the pointer above the touch surface is detected and the corresponding output is generated. . Furthermore, the present passive touch system provides advantages in that it does not suffer from parallax, image distortion, pointer position restrictions, or image projection and scalability problems that are associated with prior art passive touch systems. .

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

Brief description of the drawings

The embodiments of the present invention will now be described in more detail 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 system 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 flow chart showing the steps performed during the execution of a processFrame routine;

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

Figure 8 is a flow chart showing the steps performed during the execution of a findPointer 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 pixel subset of Figure 9;

Figure 11 shows a 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 a pointer end and its median line;

Figure 13 shows a pointer contact and a hovering pointer, for different pointer orientations;

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

Figures 15 and 16 show the results of a Matlab simulation of the pointer tracking, using a Kalman filter; Y

Figures 17a to 17d show the results of another Matlab simulation of pointer tracking, using a Kalman filter.

IS 2 340 945 T3

Best mode 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, the touch system 50 includes a touch screen 52 coupled to a master controller 54 based on a digital signal processor (DSP). Master controller 54 is also coupled to computer 56. Computer 56 executes one or more application programs and supplies screen output that is displayed on touch screen 52 via projector 58. Touch screen 52, master controller 54, computer 56, and projector 58 form a closed loop. such that the user's contacts with the touch screen 52 can be recorded as writing or drawing, or used to control the execution of application programs executed by the computer 56.

Figures 2-4 better illustrate touch screen 52. Touch screen 52 includes touch surface 60 bounded by rectangular structure 62. Touch surface 60 is in the form of a flat rectangular sheet of passive material. DSP-based CMOS digital cameras 63 are associated with each corner of 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 digital camera 63 is mounted. Support frame elements 70 and 72 are mounted on plate 66 via posts 74, and secure plate 66 to frame 62 .

Each digital camera 63 includes a two-dimensional CMOS image sensor and associated lens mount 80, a "first in, first out" (FIFO) buffer 82 coupled to the image sensor and lens mount 80 via of a data bus and a digital signal processor (DSP) 84 coupled to the FIFO element 82 via a data bus, and to the image sensor and lens mount 80 via a control bus. A bootable EPROM 86 and a power supply subsystem 88 are also included.

In the present embodiment, the CMOS camera image sensor is a Photobit PB300 image sensor configured for a 20x640 sub-array of pixels, which can be operated to capture image frames at speeds greater than 200 frames per second, since they can arbitrary pixel rows be selected. In addition, since the rows of pixels can be arbitrarily selected, the pixel subformation can be exposed for a longer duration for a given frame rate of the digital camera, which allows good operation in dark rooms as well as in well rooms. illuminated. The FIFO 82 buffer is made by Cypress under part number CY7C4211V and DSP 84 is made by Analog Devices under part number ADSP2185M.

The DSP 84 supplies control information to the image sensor and lens mount 80 via the control bus. The control information allows the DSP 84 to control parameters of the image sensor and lens mount 80, such as exposure, gain, formation setup, reset, and initialization. The DSP 84 also supplies clock signals to the image sensor and lens mount 80 to control the frame rate of the image sensor and lens mount 80.

The angle of plate 66 is selected such that the field of view (FOV) of each digital camera 63 extends beyond a designated peripheral edge of touch pad 60, as shown in Figure 11. 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. DSP 90 communicates with DSP 84 of digital cameras 63 over a data bus, through serial port 96, and communicates with computer 56 over data bus through serial port 98, and controller 94 serial line. In this embodiment, the DSP 90 is also manufactured by Analog Devices under the part number ADSP2185M. The serial line controller 94 is manufactured by Analog Devices under part number ADM222.

The master controller 54 and each digital camera 63 follow a communication protocol that enables bidirectional communication over a common serial cable, similar to a universal serial bus (USB). Broadband transmission 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 not used. Master controller 54 monitors the twenty-four (24) channels assigned to DSPs 84, while DSPs 84 monitor the six (6) channels assigned to DSP 90 of master controller 54. Communications between master controller 54 and digital cameras 63 they develop as background processes in response to interruptions.

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

IS 2 340 945 T3

Master controller 54 polls digital cameras 63 for PIPs. If the PIPs include pointer characteristic 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 rectangular Cartesian coordinates. Master controller 54, in turn, transmits calculated pointer position data, status, and / or diagnostic information, to 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 run by the computer 56. The computer 56 also updates the output. of screen transported to projector 58 such that information displayed on touch surface 60 reflects pointer activity.

Master controller 54 also receives commands from personal computer 56 and responds accordingly, as well as generates and transports command PIPs to digital cameras 63.

Specific data regarding the processing of the acquired images and the triangulation of the pointer features in the PIPs will now be described with particular reference to Figures 6 to 8.

Initially, a camera offset angle calibration routine is run to determine the offset angle δ of each digital camera 63 (see Figure 11) such that the contact or glide position of a pointer relative to touch surface 60 can be accurately determined. Details of camera offset angle calibration are described in applicants' co-pending US application entitled "Calibrating Camera Offsets to Facilitate Object Position Determination Using Triangulation." Determination of the Position of Objects Using Triangulation ”], filed on June 1, 2001, the content of which is incorporated into this document by reference.

Following the camera offset angle calibration routine, a surface detection routine is run to improve the determination as to whether the pointer is in contact with touch surface 60 at a given point, or hovering above it. the touch pad.

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

The z-coordinate of the pointer can be measured from a digital camera image and thus the z-coordinates can be determined for the pointer positions on the touch pad 60. This vertical calibration becomes a matter of adjusting the data. of the z coordinate for the given x and y rectangular coordinates. Vertical calibration can be described as a surface of the form:

<img file="ES2340945T3_D0001.tif" />

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

<td> *1</td><td>TO</td><td></td><td>Y?</td><td></td><td>F</td><td>Ά ' B</td><td></td><td> “ -</td>

<td></td><td>and Z</td><td> £</td><td></td><td></td><td> 1</td><td>C</td><td> —</td><td>^Z2</td>

<td></td><td> •</td><td> •</td><td></td><td></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></td>

In order to fit the rectangular coordinates x and y to equation (0.1), to determine the coefficients A to E, the Moore-Penrose pseudo-inverse procedure, which is based on singular value decomposition (SVD), is used to determine the least norm and least squares solution.

IS 2 340 945 T3

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

A = USV^T (0.2)

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

<img file="ES2340945T3_D0002.tif" />

The diagonal matrix S is composed entirely 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 with it, The inverse of matrix A can always be computed. Furthermore, it is possible to control this inversion when a poorly determined problem is encountered. Let's consider the system of linear equations:

<img file="ES2340945T3_D0003.tif" />

Whose solution would be:

<img file="ES2340945T3_D0004.tif" />

The SVD allows the inverse of matrix A to be written as:

TO'¹ = VS¹OR^T (0.3) since both matrices U and V are orthogonal. In a loosely determined situation, some of the singular values ​​will be very small, such that when the matrix S is formed^-1, 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 procedure of normal equations for least squares problems is based on solving:

<img file="ES2340945T3_D0005.tif" />

in the ultra-determined case, and in solving

<img file="ES2340945T3_D0006.tif" />

in the ultra-determined case. As will be appreciated, during the adjustment of the system of equations to equation (0.1), the same method is used that was used during the determination of the camera phase shift angles δ. Since the same procedure is used, memory usage and processing speed are kept at the desired levels.

IS 2 340 945 T3

With the known coefficients A through E, the z-coordinate can be calculated for any given point (x, y) on the touch pad, and in this way a determination can be made as to whether or not a pointer is making contact with the touch pad 60 or hovering over it.

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

During the processing of an image acquired by a digital camera 63, the DSP 84 executes a processFrame routine, as shown in Figure 6. When an image is available for processing (step 120), a check is made to determine whether the image has been captured for the purpose of adjusting digital camera 63 (step 122). If the image has been acquired for the purpose of exposure adjustment, an exposureControl routine (step 124) is called to adjust the exposure of digital camera 63. The DSP 84 then waits for the receipt of the next available image for its 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 background image (step 126). . If the image has been acquired for the purpose of replacing the background image, a captureBackground routine is called (step 128) and the acquired image is used as the background image. This is done if a digital camera acquires an image and sends a PIP to the master controller indicating that a pointer is on the image, when the image is, in fact, noise. Replacing the background image effectively inhibits the digital camera from falsely identifying a pointer in future PIPs. The DSP 84 then waits for receipt of the next image available for processing.

In step 126, if the image has not been captured for the purpose of background image replacement, a copyICur routine is called by DSP 84 (step 130). During this routine, the current acquired image is copied into memory and used to update the background image, as well as to form a difference image representing the differences between the current acquired image and the background image.

After the completion of the copyICur routine, a segmentPointer routine is called (step 132) to determine whether a pointer is in the acquired image and, if so, to determine the location of the pointer relative to the touch surface 60, and whether the pointer it is in contact with or hovering over the touch surface 60. The segmentPointer routine 132 also allows you to detect changing light conditions. Following the segmentPointer routine 132, the DSP 84 calls a fillPIP routine (step 134) to place the pointer and the light condition information in a PIP, for transmission to the master controller 54. Subsequently, the DSP 84 awaits receipt of the next image available for processing.

Figure 7 illustrates the steps performed by the DSP 84 during the execution of the segmentPointer 132 routine. As you can see, when the DSP 84 executes the segmentPointer routine, the DSP 84 calls a findPointer routine to determine if a pointer is in the acquired image and, if so, the position of the pointer in the current acquired image (step 140). After completing the findPointer routine 140, the DSP 84 calls an updateBackground routine to update the background image to deal with changes in lighting conditions (step 142).

During the execution of the updateBackground routine, the DSP 84 continuously updates the background image using the equation:

B_{n + 1}(i, j) = (1-a) B_n(i, j) + al (i, j) (.6) in which:

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

B_n is the current background image;

I is the current acquired image;

i, j are the row and column coordinates of the background image pixels that are 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 background image is updated.

IS 2 340 945 T3

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

Figure 8 illustrates the steps executed by the DSP 84 during the execution of the findPointer 140 routine. As can be seen, when the DSP 84 executes the findPointer 140 routine, the DSP 84 initializes the location of the pointer and the xyz parameters of the tip. of the pointer, respectively (step 150). Subsequently, a vertical intensity histogram is constructed (step 152). During this stage, the difference image representing the differences between the current image and the background image is formed, and the pixel intensities in the difference image are added by columns. 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 specific details of this process can be found in the article entitled “A smart camera application: DSP-based people detection and tracking”, authored by V. Cheng et al, and published in the SPIE Journal of Electronic Imaging in July 2000.

Following creation of the vertical intensity histogram in step 152, the pointer location parameter x is determined by finding the column in the vertical intensity histogram with the highest intensity above a 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 no pointers are within the acquired image.

When a pointer location parameter x is determined, the DSP 84 analyzes the ROI to determine the row of pixels where the pointer tip is located, and to determine whether that row represents touch surface contact or glide (step 156). Specifically, the DSP 84 creates a binary mask on the ROI, such that the white pixels represent the pointer and the black pixels represent the background, as shown in Figure 12. From the mask, the midline of the pointer and the z-location of the pointer tip can be easily calculated.

During the fillPIP routine 134, the DSP 84 uses the pointer and light condition information, acquired during the execution of the segmentPointer routine 132, and creates a PIP to reduce the acquired image to a small data set to provide, of this way, bandwidth economy. 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 source / determination field, a data type field, an image frame number field, a sequence number field, and a number field. of package. The destination / source field identifies the recipient of the PIP and the source of the PIP. If the PIP is generated by the master controller 54, the recipient 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 such 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. The package number field stores a number that identifies the package.

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 field, and a contact state field. pointer quality. The pointer identifier field stores an identifier for the pointer, to allow tracking of multiple pointers. The pointer location parameter field stores the value of x calculated by the DSP 84. The pointer tip parameter field stores the value of z computed by DSP 84. The contact status field stores a value that indicates whether the pointer is in contact, out of contact, or possibly in contact with the touch surface 60. The pointer quality field stores a statistical value about the probability that a detected pointer is real.

The checksum portion of the PIP is used to ensure the transmission integrity of the PIP. If PIP checksum errors are infrequent, PIPs exhibiting checksum errors are ignored by the target device.

IS 2 340 945 T3

Status PIPs that do not refer to pointer information have a different form than the previously identified PIPs described. For PIPs of this nature, the data portion 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 current instruction or status request identifier. 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.

A frame header PIP typically includes the number of pointer PIPs that follow for a current acquired image, with statistics for the current image such as the intensity variance between the current acquired image and a previous image. A command PIP issued by master controller 54 may instruct a digital camera to adjust one or more of its set values, such as exposure, or to capture an image to be used as a new background 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. PIPs created by DSPs 84 are only sent to master controller 54 when digital cameras 63 are polled by the master controller 54.

When the master controller 54 polls 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 receiving a frame sync pulse, each DSP 84 transmits the PIP to the master controller 54 over the data bus. PIPs transmitted to master controller 54 are received via serial port 96 and temporarily self-stored in DSP 90.

After the DSP 90 has polled the digital cameras 63 and received the PIPs from each of the digital cameras 63, which include the pointer information, the DSP 90 processes the PIPs using triangulation to determine the location of the pointer with respect to touch surface 60 at coordinates (x, y). Specifically, the PIPs of the pairs of digital cameras 63 are processed using triangulation.

Figure 11 shows that two angles are needed &lt;/_tíllll Y /_cam2 to triangulate the position (x₀, Y₀) 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 the angle ^_cam using the equation:

<img file="ES2340945T3_D0007.tif" />

in which:

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

The angle /_cim calculated is equal to the angle formed between the extremity of the field of view that extends beyond the designated peripheral edge 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 intersects 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 tactical surface 60 within the field of view by a known amount. However, in almost all cases the range d_cam angular phase shift of each digital camera 63 is different and unknown.

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

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

IS 2 340 945 T3

In order to determine a pointer position using the 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 the upper and lower digital cameras:

<img file="ES2340945T3_D0008.tif" />

in which:

h is the height of the touch screen 52, that is, the vertical distance between the focus point and the digital camera focus point;

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

For digital cameras 63 along the right 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="ES2340945T3_D0009.tif" />

The similarity between equations (0.8) and (0.10), that is, equation (0.10) = 1 - equation (0.8), once the angles φ have been substituted₂ and φ₃ in equation (0.8) instead of the angles φ₁ and φ₂ respectively, it should be obvious. Equations (0.9) and (0.11) are related in a similar way.

In order to determine a pointer position using digital camera 63 along the bottom of touch screen 52, the following equations are used to determine the coordinates (x0, y0) of the pointer position, given the angles φ0 and φ3 for the lower left and lower right digital cameras:

<img file="ES2340945T3_D0010.tif" />

IS 2 340 945 T3

In order 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:

<img file="ES2340945T3_D0011.tif" />

The similarity between equations (0.12) and (0.14), that is, equation (0.14) = equation (0.12), once the angles φι and φ have been substituted₂ in equation (0.12) instead of the angles φ₀ and φ₃, it should go without saying. Equations (0.13) and (0.15) have the following relationship: equation (0.15) = 1 - equation (0.13), once the angles φι and φ have been substituted₂ in equation (0.13) instead of the angles φ₀ and φ₃, respectively.

In order to determine a pointer position using 63 digital cameras on the diagonal from the lower left to the upper right corner, the following equations are used to determine the coordinates (x0, y0) of the pointer position, given the angles φ0 and φ2 for the lower left and upper right digital cameras:

<img file="ES2340945T3_D0012.tif" />

In order to determine a pointer position using 63 digital cameras on the lower right to upper left diagonal, the following equations are used to determine the coordinates (x₀, Y₀) of the pointer position, given the angles φι and φ₃ for the lower right and upper left digital cameras:

<img file="ES2340945T3_D0013.tif" />

The similarity between equations (0.16) and (0.18) that is, equation (0.18) = equation (0.16), once the angles φι and φ have been substituted₃ in equation (0.16) instead of the angles φ₀ and φ₂, it should go without saying. Equations (0.17) and (0.19) have the following relationship: equation (0.19) = 1 - equation (0.17), once the angles φι and φ have been substituted₃ in equation (0.17) instead of the angles φ₀ and φ₂, respectively.

IS 2 340 945 T3

As will be appreciated, the above equations generate the coordinates x₀ hey₀ on a scale of [0,1]. Therefore, any suitable coordinate scale can be used by multiplying x₀ hey₀ by the maximum X and maximum Y values, 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. The resulting pointer positions are then averaged, and the resulting pointer position coordinates are queued for transmission to personal computer 56 via serial port 90 and serial line controller 94.

With the position (x, y) of a pointer known by triangulation, using the coefficients A to E calculated during the surface detection calibration, the z coordinate corresponding to the position (x, y) can be determined, using the equation ( 0.1). Calculating the z coordinate and comparing the z coordinate with the z parameter in the PIP provides an indication as to whether the pointer is hovering over the touch surface 60 or is in effective contact with the touch surface.

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

The angle of the pointer can be determined due to the fact that the PIP includes the x-intercept at 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 necessary to calculate the angle of the pointer is available.

If desired, a Kalman filter (essentially a recursive least squares procedure) can be used to effectively "track" the pointer when it is within a certain distance of the touch surface 60. To do this, 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 the pointer position z and velocity v, the following description can be used:

z = z₀ + vt

V = V

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

<img file="ES2340945T3_D0014.tif" />

To relate the state of the system at two successive moments n and n + 1, let us write the equations of the system as a matrix difference equation:

<td>z</td><td></td><td>Ί</td><td>dt</td><td></td><td>₊</td><td></td>

<td>Y.</td><td></td><td> 0</td><td> 1.</td><td></td><td></td><td>σ,</td>

or, in matrix notation,

<img file="ES2340945T3_D0015.tif" />

IS 2 340 945 T3

Here, dt denotes the time interval between successive time steps. The term "process noise" is also introduced here on the right hand side. This is merely formal, but part of the Kalman filter procedure. You also need to specify how a measurement is entered into the procedure. This is done using the matrix equation:

z_n = Hx_n + w where z_n is a measurement of position and velocity, H is a “measurement matrix” that is taken as an identity matrix, x_n is the state vector and w is the measurement noise. 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="ES2340945T3_D0016.tif" />

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

M-) = A (+) = / i / t) (⁺M^r+6»-)

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

<img file="ES2340945T3_D0017.tif" />

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

A (+) = ί * (-) + ^ [^ - ^ Λ &lt;-) 1 p_k(+) = k '(-) + ^' ^ F

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

The results of the Matlab simulation of a Kalman filter, carried out using a set of measurements representing a pointer approaching touch surface 60 at a constant speed. Figures 15 and 16 illustrate the simulation, with a time step dt of 0.1 sec and a measurement precision of 0.5 pixels. The open symbols represent the data, and the lines the estimate of the state of the Kalman filter. Clearly, the state estimate tracks the data quite well.

IS 2 340 945 T3

A second Matlab simulation was carried out to take into account the vertical (z) and horizontal (x) movement of a pointer. This simulation is basically of two similar Kalman filters working together in a "parallel" way. The formulation is exactly the same, except that you need to consider twice the number of variables. Figures 17a to 17d show the simulation results and depict movement of a pointer toward touch surface 60 at constant speed and at a slowly varying x position (ie, the person's hand is not steady).

Although the touch system 50 has been described as including a projector for displaying 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 can be placed on a display unit such that the screen displayed on the display unit is visible through the touch screen. Also, the touch screen does not need to be a rectangular sheet of material bordered by a frame. The touch screen, in fact, can be virtually any surface within the overlapping fields of view of two or more digital cameras.

Furthermore, 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 set up to function as a camera and as a master controller, and poll the other digital cameras. looking for the PIPs. In this case, it is preferred that the digital camera acting as the master controller includes a DSP 84 faster than the other digital cameras.

Additionally, although the surface detection routine is described as determining the coefficients A to E to be used with equation (0.1), to calculate the z-coordinates of the pointer at a given point (x, y) in relation to the touch screen During the surface detection routine, the master controller 54 may be programmed to calculate a z coordinate for unique regions (x, y) of the touch surface and store the z coordinates in a lookup 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 pad is determined, a decision can be made as to whether or not the pointer is in contact with the touch pad , comparing the z coordinate in the corresponding LUT with the region (x, y) in which the pointer is located, and with the row of pixels of the image sensor and the lens assembly in which the tip of the pointer is located.

As described above, the master controller 54 calculates or searches the touch surface z coordinates for each digital camera, and compares the z coordinates with the z location of the pointer tip, to determine if the pointer is in effective contact with the touch pad. However, those skilled in the art will appreciate that the DSP 84 in digital cameras can include image processing software to determine if the pointer is in effective contact with the touch surface. This image processing can be performed in conjunction with, or instead of, the pointer contact determination of the master controller.