Abstract:
A system for computer vision comprises a source of digitized video signals and a frame encoder circuit connected to the source of digitized video signals. The frame encoder encodes threshold crossing events at at least two threshold levels and stores encoded data for a two-dimensional area within the frame in a cache memory. The threshold levels are programmable. A computer is in communication with the encoder circuit at least via its data bus and address bus for programming the threshold levels and controlling the encoder and accessing the data in said cache memory. The computer has an associated main memory with a stored task for reading the cache memory and interactively controlling the frame encoder circuit and interpreting the data gathered thereby. Data is encoded by event type and pixel address wherein the event type is indicative of threshold crossed and direction of crossing. The task stored in main memory has an algorithm for continuously changing the threshold levels and analyzing the data in successive frames until the desired threshold levels are achieved.

Description:
BACKGROUND OF THE INVENTION 
     Eye-trackers are instruments for measuring the movements of an eye. An eye-tracker communication system allows a physically handicapped person to use eye movements to communicate. There are several varieties as explained in &#34;Survey of Eye Movement Recording Methods&#34; by Young and Sheena, Behavorial Research Methods Instrumentation, 175, Vol. 7 (5), pages 397-429. A number of eye-tracking devices have been explained in the patent literature including U.S. Pat. Nos. 2,288,430; 2,445,787; 3,462,604; 3,514,193; 3,534,273; 3,583,794; 3,806,725; 3,864,030; 3,992,087; 4,003,642; 4,034,401; 4,075,657; 4,102,564; 4,145,122; 4,169,663; and 4,303,394. 
     One technique, the theory of which is explained in the Young and Sheena article, is the corneal reflection technique. The corneal reflection technique can be implemented in a number of ways. See, Laboratory Oculometer, NASA CR-1422 by John Merchant and &#34;Eye Fixations Recorded on Changing Visual Sense by the Television Eye Marker&#34; by Mackworth and Mackworth in Journal of Optical Society of America, Vol. 48, No. 7, July 1958. 
     While the prior art discloses eye-tracking devices, the applicants found that there was no relatively inexpensive eye-tracking system and technique which could be used by individuals on a more or less continual basis. Prior systems have been large and expensive, if adequate. 
     While it has been possible to use a digitized image processed by computer to implement the corneal reflection eye-tracking technique, it has required a very large, very fast computer to do so. Consider that a television frame divided into 240 lines by 256 pixels (picture elements) requires nearly 62,000 bytes of memory if one byte is stored for each pixel. Moreover, the time to load and compare and analyze 62,000 bytes of memory in a typical eight bit microprocessor would be no less than several seconds--too long for any value in a real time eye-tracking device. 
     Some form of digital preprocessing is essential if eight bit or even sixteen bit microprocessors clocked at typical rates are to be used in a practical eye-tracker. A preprocessing frame grabber is disclosed in &#34;Video Signal Input&#34; Robotics Age, March/April 1981, pages 2-11 and 19. The article describes a circuit for comparing video signals to an analog threshold (programmable at 256 levels) to establish one bit of data for each pixel and then packing the data (eight pixels to the byte) before dispatching each data byte one at a time to the associated computer memory. Eight thousand (8K) bytes of computer memory are required for one frame. Since only one bit of data for each pixel is gathered, a simple binary image is gathered which is insufficient for most computer vision applications. It is clearly insufficient for eye-tracking by the corneal reflection technique where it is necessary to locate the corneal reflection (the brightest location on the frame) and the pupil (either very dark or less bright than the corneal reflection). Moreover, eight thousand bytes (8K) of data is still a large quantity for real time processing. Consider that eye movements can take only fractions of a second. 
     SUMMARY OF THE INVENTION 
     Briefly, according to this invention, there is provided a system for computer vision comprising a television camera, a frame encoder circuit, and a computer having an associated main memory with a stored task. The television camera produces a video signal including synchronization signals. The frame encoder connected to the video signal from the camera encodes the signal at at least two threshold levels. The encoded data for a two-dimensional area within the frame, i.e., a window, is stored in a cache memory. The encoder circuit is provided with programmable threshold levels. The computer is in communication with the encoder circuit at least via its data bus and address bus. The task stored in the main memory of the computer reads the cache memory and interactively controls the frame encoder and interprets the data gathered thereby. According to a preferred embodiment, the frame encoder stores the data in the cache memory after first encoding the data by event type and pixel address. With two thresholds, four event types may be selected for recordation; namely, rising across or dropping across the upper threshold level and dropping across or rising across the lower threshold level. It is further preferable that the frame digitizer has a programmable data collection window within the frame such that the frame area within which data is gathered may be reduced by, say, one-twentieth. It is yet another preferred embodiment according to this invention that the frame digitizer have a programmable data collection rate wherein at least the precision of the horizontal pixel position may be doubled. 
     The task stored in main memory has an algorithm for continuously changing the threshold levels and analyzing the data in successive frames until desired threshold levels are established. The task stored in main memory may also have an algorithm for establishing the size and position of the data collection window based upon analysis of the data for the entire frame; for example, the frame might be positioned about the brightest spot on the frame. Preferably, the task stored in main memory has an algorithm for changing the data collection rate when the increased precision is feasible and useful. 
     One special embodiment of this invention comprises an eye-tracker system including a display, a light source, a television camera, a frame encoder, and a computer, said computer having an associated main memory stored with the task for establishing the vector from the center of the corneal reflection to the center of the pupil upon which the television camera is focussed. The television camera produces a video signal. The frame encoder is connected to the video signal output of the camera and encodes the signal at at least two threshold levels and stores the encoded data for the entire frame in a cache memory. The threshold levels are programmable. The computer is in communication with the encoder circuit at least via its data bus and address bus. The task stored in the main memory reads the cache memory and interactively controls the frame encoder. The task comprises a subtask for finding the corneal reflection of an eye upon which the camera is focussed by lowering the upper threshold until the brightest spot on the frame is detected. The task comprises a subtask for finding the pupil by raising the lower threshold until the border between the pupil and the iris is defined. The task has a third subtask for finding the center of the corneal reflection and the center of the pupil and establishing the vector (azimuth and length) from the center of the corneal reflection to the center of the pupil. 
     A specific embodiment according to this invention comprises an eye-typer. The apparatus for the eye-typer comprises the above described eye-tracker apparatus and a display board bearing indica, for example, the characters of the alphabet plus punctuation and control characters. The display is arranged with the light source and television camera facing through it and away from it. The computer then has another task stored in main memory which calls upon the tasks already described. This additional task associates vectors of the corneal reflection with the character on the display board which is being looked upon by the user of the eye-typer. Characters can, thereby, be selected and sent to the output device, for example, a typewriter. 
    
    
     THE DRAWINGS 
     Further features and other objects and advantages of this invention will be clear from the followng detailed description made with reference to the drawings in which 
     FIG. 1 is an overall schematic of an eye-tracker system; 
     FIG. 2 is a view of a display which might be used with an eye-typer system; 
     FIG. 3 is a function level circuit diagram of a frame encoder useful with the system of this invention; 
     FIG. 4 is similar to FIG. 3 and illustrates an embodiment wherein the data collection rate is programmable; 
     FIG. 5 is a flow diagram showing the task for detecting the azimuth direction of the gaze of the eye upon which the system is focussed; and 
     FIG. 6 is a flow diagram showing a task for associating corneal reflection vectors with characters and outputting characters to a display device. 
    
    
     DESCRIPTION OF THE PREFERRED EMBODIMENTS 
     Referring now to FIG. 1, the overall system for an eye-tracker according to this invention is set forth. The system includes a light source 10 (which may be an infrared light source) and a television camera 11 (which must, of course, be an infrared sensitive television camera if the light source is infrared). The light from the light source 10 is beamed through an opening in the display board 12 before which the user sits. The sight of the camera 11 is also through the opening in the display board. A display board suitable for use with the eye-tracker as an eye-tracker is shown in FIG. 2. The user, sitting before the eye-typer can select a letter by looking at it for a predefined period of time. The remainder of the system analyzes the video image of the eye to determine at what letter the eye is gazing and signals a typewriter or printer or the like to type that letter. Other applications of the eye-tracker are contemplated by this disclosure, for example, telephone dialers, machine controls, speech generators and the like. 
     The display has about 30 characters spaced about the center of the display. The number of characters that can be placed upon the display is directly related to the precision with which the corneal reflection vector is established. For a given data rate (say 256 pixels 240 lines) the precision is dependent upon the extent to which the pupil falls within the frame and the precision with which the centers of the pupil and the corneal reflection can be determined. The extent to which the pupil falls within the frame involves a trade-off. Head movement (side-to-side or up-and-down) can only be tolerated by having the pupil fall within the frame no matter the head position. Allowing for greater head movement requires giving up corneal vector precision. (The image of the pupil on the frame must be smaller for increased head movement). Applicants have chosen to provide head movement in the range of two to three inches and a display of about 30 characters as a satisfactory compromise. This compromise can only be made because of the accuracy with which the edges of the corneal reflection and pupil are obtained by the entire system discloed herein. Thus, the quality of the data gathered by the eye-tracker is critical. The quantity available from solid-state cameras having a digitized output has not to data been found satisfactory. 
     Referring now to FIG. 3, the encoder circuit comprises a number of programmable registers for configuring the circuit and at least one readable register for providing status information. Two eight-bit registers 21 are provided to hold the upper and lower threshold values. (In the embodiment described only six bits of these registers are actually used as the analog signal is only digitized at sixty-four levels.) Four more eight-bit registers 22 are required to hold the X and Y counts (frame addresses) of two corners (upper left and lower right) of the window within which the data is collected. The entire frame may fall within this window. Several one-bit registers (latches) hold control data. Register 24 holds the select high flag and register 25 holds the select low flag. These are applied respectively to select the high valid gate 26 and the low valid gate 27; which gates control flow of information to the event logic 31. A one-bit control register 28 holds the &#34;active&#34; flag which places the encoder circuit in the data collection mode. The output of a decoder 29 presents the &#34;write to window register&#34; flag which is set true during the time data is being written to the window registers. The system decode logic 20 generates a board select signal (&#34;decode&#34;) from the signals on the address bus of the associated computer and specifically points to the control registers 21, 24, 25, 28, and 30. It is also used to generate the output of decoder 29. 
     One status register 30 may be read and contains at least two bits of status of information; namely, and end of field (&#34;eof&#34;) flag and a memory overflow (&#34;mem ov&#34;) flag. The output of the control register 28 holding the active flag is applied to the end of file (EOF) generator 32 which also has applied thereto the vertical sync (VS) signal of the video signal. The EOF generator 32 looks for the negative edge of the vertical sync signal next following the change of the active flag to start the &#34;enable&#34; signal. The enable signal remains high or true during the whole field. The &#34;EOF&#34; output of the EOF generator goes active at the end of the frame just captured. These signals are used to control the data gathering process. 
     The video input to the encoder circuit is continually digitized by a six-bit analog to digital (A/D) converter 35 which is clocked by an element rate clock (ERC) 36. (With a digital camera of sufficient quality, should one become available, the television camera output signal would not be analog and the analog-to-digital apparatus on the encoder board would be eliminated. The output of the digital camera would then be applied to the dual digital comparator circuit 38.) 
     The clock 36 is free running and is gated to the converter 35 by the vertical sync and horizontal sync signals. The element rate clock outputs a clock pulse at about five megahertz under typical conditions. This permits the gathering of approximately 256 pixels per line. The output of the A/D converter is continually applied to a dual digital comparator circuit 38 comprising two comparators. To one side of the first comparator is applied the upper threshold level; to one side of the other comparator is applied lower threshold level. The output from the upper comparator is an equal to or greater than signal. The output from the lower comparator is an equal to or less than signal. These signals are applied via the high valid and low valid gates 26, 27 to the event logic 31. 
     The encoding scheme for the digitized data will now be explained. Run length encoding is a data collection scheme in which only the time between events is stored. Applicants&#39; encoding scheme is a significant departure from run length encoding. The X address of a pixel for which an event is detected is stored with the data descriptive of that event. The twelve-bit word which is stored for such an event comprises eight bits of X address data and four bits of type data. At the end of every line in which an event takes place, the Y address of the entire line is stored. The bit length of each data word including event and event type must, of course, exceed eight, where the address count is 256 or more. The particular implementation described herein stores six types of events and could thus be encoded in three bits, but as a practical matter stores the information about the six event types in four bits. The six types of events encoded, according to the specific embodiment disclosed, are 
     (1) rising oven (begin) high threshold; 
     (2) dropping through (end) high threshold; 
     (3) dropping through (begin) low threshold; 
     (4) rising through (end) low threshold; 
     (5) end of line (Y address follows); and 
     (6) end of frame. 
     The applicants have found that the encoded data required for properly tracking an eye can be stored in a 1K (1024) by twelve-bit word cache memory 45. Note that the exact amount of memory required depends upon the number of events encountered. The data so summarized can be easily analyzed by the task stored in the main memory of the associated computer during real time processing. 
     The event logic 31 outputs an &#34;event&#34; signal every time the upper or lower threshold is crossed unless the &#34;in window&#34; input disables all outputs of the event logic. The event logic signal is applied to clock the DMA counter 40 for the cache memory 45 and is also applied to the R/W input of the cache memory to permit the contents of the event buffer 46 and the X or Y counter bus 47 to be written to the cache memory. Two other outputs of the event logic are the low event (LoEv) and high event (HiEv) lines which encode the event type relating to threshold crossings. 
     The event buffer 46 is a four-bit buffer which writes to the high order bits in the cache memory. Two bits are binary coded to indicate one of four types of events and two other bits are flags, one to note horizontal sync (HS) (end of line) and the other to indicate end of the frame (EOF). 
     The X and Y counters 50 and 51 are eight bit counters. The X counter (pixel counter) is clocked by the inverted output of the element rate clock (ERC) and is reset by the fall of the horizontal sync signal (HS). The Y counter (line counter) is clocked by the horizontal sync signal (HS) and is reset by the rising edge of the vertical sync signal (VS). An eight-bit, two bus input multiplexer 53 multiplexes the outputs of the X counter and Y counter to the eight-bit X or Y counter bus 47. The multiplexing signal is the horizontal sync signal (HS) which causes the Y counter data to flow to the bus 47 at the end of a line. Otherwise, the X counter data flows to the bus 47. 
     The &#34;active&#34; signal, that is, the output of register 28 is not only applied to the EOF generator. It is inverted and applied to the X-Y address multiplexer 53 and the event buffer 46 to place them in the high impedance state such that they are isolated from the buses 47 and 48 and the cache memory 45. This enables the use of these buses for reading the contents of the cache memory to the computer. The active signal also selects the cache memory address multiplexer 54 to pass the event address generated by the DMA counter 40. Otherwise, the address bus of the computer has access to the cache memory. 
     The cache memory 45 is written to at the time of an event. At that time the next free address in the cache memory is placed upon the memory address bus by the DMA counter 40 and the cache memory address multiplexer 54. The event signal out from the event logic clocks the DMA counter and sets the R/W of the cache memory to the write condition. The event signal also strobes the chip select (CS) input to the cache memory through NOR gate 57. Each word of the cache memory must be read in two steps when the computer data bus is only eight bits wide. The four bits of type data must be multiplexed by memory output multiplexer 55 which is selected by line SA10 of the computer address bus in the embodiment disclosed. The multiplexed output of the cache memory is buffered from the computer data bus by the buffer driver 56 which is activated to pass the cache memory data upon application of the decode signal. The decode signal is also NORed at 57 with the event signal to strobe the chip select (CS) input to the cache memory during a memory read. 
     The window logic comprises a state machine 60, digital comparator 61, and the four window address registers 22. One of the four address registers is placed on one side of the comparator 61 according to the following selecting inputs: 
     
         ______________________________________Register          Input   Input______________________________________Vertical Begin    Begin   HS Vertical End              ##STR1##                      HS Horizontal Begin  Begin                      ##STR2## Horizontal End              ##STR3##                      ##STR4##______________________________________ 
    
     The data bus 47 places the current X or Y count upon the other side of the comparator 61 depending upon whether the HS or HS is applied to the X-Y address multiplexer 53. The output of the comparator is a true or &#34;matched&#34; signal when a match is found. 
     The inputs to the state machine are the HS/HS, ERC, VS, and &#34;matched&#34; signals. The outputs are the &#34;in window&#34; and &#34;begin&#34; signals. The state machine has flags &#34;vertical in&#34; and &#34;horizontal in&#34; which, when both set true put the &#34;in window&#34; in the true state. (State to enable the event logic 31.) 
     At the time of the horizontal sync preceding the first line, the vertical in and horizontal in flags are set false and the begin address flag which controls the begin output, is set true. When a match is found for the vertical begin, the vertical end flag is set true and the begin address flag remains true. Now the state machine looks for a begin X address and when found, sets the horizontal in flag true and therefore the window in output true. The begin flag is set false. The state machine now looks for the next end address (the begin flag being set false). If an end address match is found (either X or Y count) the flags are set accordingly. If an X end match is found, the begin flag is not set false but left to look for the Y end match during the next horizontal retrace. At the start of every line, the begin flag is set true so that the state machine can find the begin X address match for that line. 
     According to a preferred embodiment shown in FIG. 4, the element rate clock is programmable by a one-bit register 65 so that it either clocks at five megahertz (the normal situation) or ten megahertz. According to this embodiment, the X counter must be enlarged to count an additional bit. The connection between the data bus 47 and the comparator circuit 61 is rewired to shift the input down so that the high order seven bits on the bus 47 are applied to the low order seven bits of the comparator input. (This shift has the effect of dividing the count by two prior to applying to the comparator.) The output of the ninth bit in the counter is applied directly to the high order bit of the comparator input. It will be zero during the HS pulse so as not to disturb the divided Y-count applied to the comparator. The frame addresses are stored in the window register after first dividing by two except the X count during the ten megahertz rate. 
     Referring now to FIG. 5, there is shown a flow diagram of the portion of the software or task in the computer main memory which most directly interfaces with the encoder circuit. The entry point at 71 leads to 72 in which the encoder circuit is instructed to grab a field. Thereafter at 73 the data in the cache memory is reviewed looking for a corneal reflection; that is, the very brightest spot on the frame. If, at 74, a bright spot is found control moves to 76 at which the window size is set about the corneal reflection. However, if no corneal reflection is found, the upper threshold is lowered at 75 and an additional field is grabbed. After the window is set at 76 the data for the window is grabbed at 77 and thereafter the computer looks at the data in the cache memory to find a pupil at 78; that is, a dark round spot near the corneal reflection. If no pupil is found, at 79 then the lower threshold is raised at 80 and an additional window is grabbed until a pupil is found. When a pupil is found, control passes to 81 where an algorithm finds the centers of the pupil and center of the corneal reflection and then control is passed to 82 where the vector between the centers is calculated. Exit to the main program is at block 83 where the vector is correlated with a particular indicia upon the display and an output indicative of the indicia selected is made. 
     The pattern recognition techniques used for establishing that either the corneal reflection or the pupil has been found are variations of standard pattern recognition techniques. If, during the procedure at 73, the first byte of information stored in the cache memory is an end of field indication, then no corneal reflection has been found and the upper threshold must be lowered. (During this time, the lower threshold is set so that it will not produce any event.) When event data first appears in the cache memory following frame grab, a test is made to determine that all event data is related to substantially contiguous pixels on successive lines indicative of only one bright spot. If more than one bright spot is detected, the shape of the spots are considered and the spot that is closest to round is taken as the corneal reflection. 
     The pattern recognition technique used for finding the pupil during the procedure at 78 is somewhat more complex. As the lower threshold is raised, events begin to appear in the cache memory. A test is made to determine that they are in substantially continguous pixels in adjacent lines which is indicative of one dark object being detected. If more than one dark object is detected (for example, the eyebrow is also detected) the most circular object is taken as the pupil. The lower level is raised even after the pupil is first detected. With successive increases in the lower threshold level the size of the detected pupil will increase until a &#34;dead zone&#34; is reached in which increase in the lower threshold level produces very little increase in the size of the pupil. At this time, raising of the lower threshold is stopped and the pupil is considered found. 
     The procedure for detecting the center of the corneal reflection and the pupil are variations of standard techniques. An obvious difficulty with detecting the center of the pupil is that the corneal reflection often has removed a portion thereof. 
     Assembly language source code for the procedures set forth in FIG. 5 is provided at the end of this specification. 
     Referring to FIG. 6, there is shown a flow diagram of a task for associating corneal vectors with characters. The corneal vectors are previously associated with each character position on the display by a trial and error procedure and are stored in a look-up table. By and large, the curvature of the corneas of most human eyes are sufficiently similar so that only one table need be established. Of course, the table associates ranges of X differences (differences in the X address of the centers of the corneal reflection and the pupil) and ranges of Y differences with each character positioned. Storing ranges provides the ability to work with the eye of more than one individual under differing conditions. 
     It should be understood tht any number of equivalent tasks could be developed within the scope of this invention to correlate the corneal vectors and the desired outputs. From the start 90 (FIG. 6), the task moves to a call for a vector at 91 which is a call to the task described with reference to FIG. 5, for example. The vector returned by the call (in terms of X and Y differences) is then compared to the predefined look-up table at 92. At 93, a test is made to determine if the vector corresponds to a character in the look-up table. If not, control is returned to 91 and another vector is sought. If the vector corresponds to a character, it is considered initially selected. After a delay at 94, another vector is obtained and compared to the look-up table at 95 and 96. If the same character is not selected as was initially selected, the process starts over. If the same character is selected at 97 it is considered firmly selected and will be output if not deselected. At 98, a test for the deselect character is made. If the deselect character has not been chosen, the last firmly selected character is output at 99 and the just selected character is saved at 100. Preferably, a feedback signal indicating selection, for example, a beep is output at 101. If the deselected character has been chosen, the last selected character is dropped. Following either save of a firmly selected character or deselect, the task starts all over again looking for the next selection. ##SPC1##