Input Device With Data Targeting to Determine an Entry Field for a Block of Stroke Data

1. Field of the Invention

The present invention relates to the field of data entry in computer systems.

2. Background Art

A typical computer system consists of a central processing unit (CPU), main memory such as random access memory (RAM), a data entry device, including a positioning device, a mass storage device such as one or more disk drives, a display and/or a printer. In the prior art, the data entry device often consists of a keyboard, on which a user enters data by typing. The positioning device of a prior art computer system may consist of a "mouse" or other cursor positioning device.

Computer systems have also been developed that are directed to handwritten data entry rather than keyboard data entry. These systems are often characterized by the use of a pen, stylus, or other writing device, to enter handwritten data directly on the display of the computer system. Alternatively, these systems may provide for a user to enter data on a digitizing tablet or other input device, with the image of the written input displayed on a separate computer display output device. The writing device for entering handwritten or freestyle stroke input information is not limited to a pen or stylus, but may be any input device such as a mouse, trackball, pointer, or even a person's fingers. Such systems are not necessarily limited to receiving data generated by human users; for example, machine generated data may also be inputted and accepted to such systems.

One class of this handwriting entry computer system that receives handwritten data input is referred to as "pen based" computers. In a pen based computer system, a writer can input information on a display by "writing" directly on the display. A writing device, such as a pen or stylus, is used to enter information on the display. In a typical pen-based computer system, a user touches the stylus to the display and writes as he would on a piece of paper, by making a series of pen strokes to form letters and words. A line appears on the display that follows the path of travel of the pen point, so that the pen strokes appear on the display as ink would appear on a handwritten page. Thus, the user can enter information into the computer by writing on the display. In addition to handwriting, special functions based on input strokes are supported on pen based computer systems. For example, a writer may strike certain previously entered handwritten input by making the strokes of an "X" over the entry. These special functional strokes or actions are referred to herein as "gestures". Pen based computers typically have a display surface that serves as both an input receiving device and as an output display device.

One problem in a handwriting entry computer system is determining the beginning and ends of characters and words. This process is referred to as "splitting." Some prior art systems rely on the proximity of a pen or stylus to the display or entry means as a cue to indicate the beginning and ends of characters and/or words. However, users may not always lift the pen out of proximity from the display or entry means when writing a new character or new word. Incorrect splitting decisions can lead to errors in display of handwritten or translated text since separations between words and characters may not be recognized.

The display of a pen-based entry or other handwriting entry computer system may have bordered regions called "fields" that define locations or areas where data is to be entered, or that are associated with particular actions. For example, if the software application provides a data entry display that is an information form with fields for "First Name", "Last Name", "Age", "Occupation", etc., certain information is generally associated with each field. These locations are referred to here as "objects" or "fields". Each object has a boundary associated with it. When data is entered, the computer must determine which object is to be associated with the writing or gesture. The object intended to be associated with the data input is called the target object. The process of identifying the target object is referred to here as targeting. The method and apparatus that performs the function of targeting is referred to here as a targeting system.

It is the nature of handwriting that the writer often will write strokes or characters outside of defined boundaries of objects or fields. Where the target object is relatively small compared to typical handwriting paper guidelines, for example, the writer will typically find it difficult to stay within the lines when writing into that object. Resultant writing strokes may fall partly within the boundaries of the target object and partly in areas of the display that are outside of the boundaries of the target object and/or in areas that do not contain any objects. In addition, writing strokes may fall partly within the boundaries of objects adjacent to the target object.

There are a number of prior art schemes for targeting. These prior art targeting schemes will typically provide incorrect targeting decisions when applied to handwritten input. A common characteristic of these prior art schemes is that targeting decisions about the target field are made at the beginning of the writing operation, for example, at the time of initial contact of the writing entry device with the display or input device. These prior art schemes typically result in a substantially degraded targeting decision.

In the following description, the prior art schemes will be described in connection with a handwriting data entry computer system that uses a pen or stylus as the data entry device and where data is entered by writing directly on the display. This is for purposes of example only, and is not intended to limit the description.

In one prior art targeting scheme, the target is defined as the object touched by the pen upon initial contact. Thus, in this prior art scheme, the target object is the object, (if any), that is associated with the point of initial contact of the stylus, pen or analogous input device. This scheme is described in connection with the examples of FIGS. 1 and 2.

FIG. 1 illustrates an example of a writing entry computer system that includes a housing 101, a display 102 and a writing tool, or "pen" 103. The display 102, for example, shows as display output, the outline of a form for data entry. This form can be generated, for example, by an application program running on the pen based computer system. The form may include a number of objects or fields. For example, in the example of FIG. 1, the form includes the "First Name" field 104, the "Last Name" field 105, the "Company" field 106 and the "Date" field 107.

In this example, fields 104-107 are arranged such that the lower boundary of one field is coincident with the upper boundary of the adjacent field. As a result, if a user entering data in one field writes outside the boundaries of that field, the stray writing may fall within the boundaries of another adjacent field. Consider the example of entering the name "Tom" in the "First Name" field 104, the name "Jones" in the "Last Name" field 105, and the name "International" in the "Company" field 106. When an entry begins with a capital letter such as "T", "J", or "I", it has been found that a user is likely to begin the pen stroke that defines the letter "J" near the top of the target field. The first stroke of the letter will be entered by the user beginning in the field above the target field, or by beginning the first stroke entirely outside any field, as shown in the examples of FIG. 1.

For example, in FIG. 1, the top stroke of the letter "T" of the name "Tom" in field 104 extends outside of the boundaries of field 104 and a portion of the top stroke of the letter "T" is not located within the boundaries of any field. The letter "J" of the name "Jones" in field 105 has a portion of its top stroke that is not within the boundaries of any field. The top stroke of the letter "J" crosses a corner of field 104 before extending into field 105. The "I" of the name "International" is found partially within the boundaries of field 105 and extends within the boundaries of field 106.

It has been found that the letter "T" is typically written with two strokes, a horizontal "cap" stroke, and a vertical stroke. The letter "J" is also typically written with two strokes, namely a horizontal stroke for the top or cap of the "J", and a curved stroke for the bottom hook of the letter "J". The letter "I" is can be written with a single vertical stroke, or, alternatively, with horizontal top and bottom strokes connected by a single vertical stroke. In the examples of FIGS. 1 and 2, the "I" is written as a single vertical stroke.

The first letters of each of the words in fields 104-106 respectively are illustrated in detail in FIG. 2. Referring to FIG. 2, an enlarged view of handwritten strokes 201 and 202 that together represent the letter "T" is illustrated. The beginning point of top stroke 201, that is, the point where the stylus first makes contact with the display, is at point 206. The end point of stroke 201, that is, the point where the stylus is lifted from the display, is at point 207. The beginning point of bottom stroke 202 is at point 208. The end point of stroke 202 is at point 209. Note that the beginning point of bottom stroke 202 lies on stroke 201.

Still referring to FIG. 2, the letter "J" is shown formed by top stroke 203 and bottom stroke 204. The beginning of top stroke 203 is at location 211. The end point of top stroke 203 of the "J" is at location 212. The beginning of bottom stroke 204 is at point 213 (which also lies on stroke 203). The end point of bottom stroke 204 is at point 214.

The letter "I" is formed by a single stroke 205 with a beginning point at location 215. The end point of stroke 205 is at location 216.

The intended target fields for the names "Tom", "Jones", and "International" are fields 104-106 respectively. The application of the prior art scheme that defines the target field as the first point of contact of the stylus results in incorrect targeting assignments for each name. Referring to the letter "T", the first point of pen contact with the display, namely point 206, does not lie in any field at all. Therefore, using the prior art scheme describing a target field cannot be properly determined, resulting in an error. Similarly, the first point of contact of the top stroke 203 of the letter "J", namely point 211, does not fall within the boundaries of any field. Therefore, no target field is defined by this prior art scheme, also resulting in error.

Referring to the stroke 205 that defines the letter "I" of the name "International", the first point of contact of the stylus is at point 215, located within the boundaries of field 105. Thus, the prior art scheme defines the target object as field 105. However, the intended target field is field 106. Thus, there is a targeting error.

Another prior art targeting scheme defines the target object as the first object touched by a pen stroke of the writer, regardless of where the first point of contact of the stylus may occur. That is, after the pen touches the display and the writer begins to make a stroke, the very first object or field touched by the stroke is considered to be the target. The operation of this scheme is also illustrated by referring to the characters of FIG. 2.

Referring to the "T" of the name "Tom", the first point of contact of the stylus on the display is at point 206. The first field contacted by the stroke 201 is field 104. Therefore, the second prior art scheme makes the correct targeting decision for this character, namely field 104. However, the second prior art scheme renders incorrect decisions for the other characters of FIG. 2.

Referring to the letter "J" of the name "Jones", the first point of contact of stroke 203 is at point 211, outside the boundaries of any field. The first field contacted by stroke 203 is field 104. Therefore, the second prior are scheme incorrectly identifies the target field as field 104, instead of field 105. This is an incorrect decision.

Referring to the letter "I" of the name "International", the first point of contact of stroke 205 is at point 215, within the boundaries of field 105. Therefore, using the prior art targeting scheme, the target field is incorrectly identified as field 105, when the intended target field is field 106.

Thus, it is a disadvantage of prior art targeting schemes that they do not make accurate targeting decisions when data is entered outside the boundaries of the intended target field.

There are a number of patents that are directed to or relate to computer systems that operate on handwritten data.

Fox, U.S. Pat. No. 4,727,588, provides a system to create and edit handwritten images of documents on an all points addressable digitalizing tablet. The device of Fox stores pen stroke coordinates in order to form word extremities. By comparing a current pen stroke with the preceding pen stroke and the associated word extremity, a new word can be detected. Since each word has an extremity associated with it, the system is able to format a handwritten document. In Fox, a word extremity consists of a rectangular area and a zone of proximity extending from each side of the rectangle. Each new pen stroke is compared with the current zone of proximity of the current word. If any part of the current pen stroke falls within the zone, it is part of the current word. If the current stroke is outside the zone of proximity, the beginning of a new word is detected. Thus, Fox employs a rectangle to help indicate the beginning of a new word. Fox does not teach a rectangle/area overlap technique to provide targeting

Ward, U.S. Pat. No. 4,562,304, is directed to emulating keyboard input using a hand-print terminal that includes a digitizing tablet. In Ward, characters are written with a pen in boxes of a grid paper that is disposed upon the digitizing tablet. The characters are converted to ASCII and stored in a line buffer memory at their respective column positions. The contents of the line buffer is serially output to the computer just as a keyboard supplies serial data to a computer. The system of Ward allows only one row of data to be "worked on" at a time. Therefore, the beginning of a new row is determined by comparing the current character row position on the grid with that of the previous character. If the row values differ, the line buffer memory is cleared and a new row can be entered and edited. Ward teaches writing characters within a specified box to allow for character recognition. As such, Ward does not teach a targeting scheme for characters written in adjacent boxes or written only partially in one box.

Tsugei, U.S. Pat. No. 4,656,317, is directed to an apparatus for providing handwritten data to computer memory by categories. The invention uses a format paper with predefined "write areas" disposed upon a digitalizing tablet wherein each "write area" is a category of information to be processed. After information is written within the "write areas" with a pen, it is stored in RAM by category. The invention of Tsugei uses a computer program to recognize when information has been written within a specified area on a digitizing tablet. Tsugei does not disclose a targeting technique in the case where information is written outside the designated areas.

A system that allows for pen input for different application programs such as a word processor or database is described in Sklarew, U.S. Pat. No. 4,972,496. The input pen is used to designate a location to enter data. An input box or line appears on the screen and the pen is used to input text. The invention of Sklarew provides a "learning" feature in which handwritten characters are matched to a database to determine the characters. A character not found in the database is appended. Thus, the invention is adaptable to all handwriting styles. Sklarew provides for handwritten data input within a rectangular input box and does not utilize a targeting scheme.

The invention in Hardin, U.S. Pat. No. 4,817,034, is directed to a system for replicating handwritten signatures. A pen is used to input a signature that is stored in computer memory for future use. The signature data can be provided to a plotter to replicate the handwritten signature. To enter a signature, an input rectangle and signature line is provided by software. Hardin utilizes a rectangular input area for pen input. The system of Hardin does not disclose a method for targeting a signature that exceeds an input area bounds.

A device for editing text is disclosed in van Raamsdonk, U.S. Pat. No. 4,475,239. As the user enters text via a keyboard, a printing head prints the characters on a record carrier which is disposed upon a digitalizing panel. As the characters are entered, they are also stored in computer memory. After a page is stored in memory and printed, a pen is used to assist in editing. For example, the user places alignment marks on the record carrier to allow the system to align the printed text with the corresponding text in memory. Next, using the pen, the user marks the location on the record carrier to perform an operation, such as insert text. After the location is marked, the keyboard is used to enter new characters. The keyed-in characters are inserted into the computer's memory and do not appear on the record carrier. Van Raamsdonk teaches the use of alignment marks to define an edit area. However, van Raamsdonk does not disclose a targeting scheme for marks written outside the edit area.

Sato, U.S. Pat. No. 4,947,156, discloses a handwritten character input device that includes a means to correct deviations on a display due to variations in angles of the input pen. The invention accounts for and corrects LCD dots that are inadvertently lit because of the angle that the input pen makes with the display screen. Sato relates generally to the field of pen based computer systems and does not disclose a targeting scheme.

The following is a patent teaching a scheme that uses a rectangle overlap scheme in a conventional keyboard based computer system.

Ikegami, U.S. Pat. No. 4,677,585 teaches a system in which information having a predetermined format is stored as a card image within a data processing system. The user defines a card by providing coordinates to indicate the size of fields and the desired location on the card. In the case of character data, the fields may be more than one row, thus forming a rectangle. The invention disclosed in Ikegami allows the user to define rectangular areas in which to input character data. The user also defines the location on a card that the rectangular input area will occupy on the display screen. The invention allows for more than one character field may be placed on a card. Therefore, the system utilizes a rectangle overlap technique to determine whether any adjacent character fields intersect. However, the scheme of Ikegami is carried out before any character data entry is performed. That is, the rectangle areas are defined prior to any data input.

The present invention provides an improved method for targeting and splitting in a computer system. A block of data (such as a character or word) is identified by analyzing strokes of writing to determine if a current stroke is to be associated with the strokes of an existing block of data or with a new block of data. Displacement in the X direction and Y direction between a prior stroke and a current stroke is generated and analyzed to determine if a new block of data has been created. After a block of data has been identified, a targeting operation for that block is performed. The bounds of the smallest rectangle that contains all of the strokes in the block is determined. The area overlap between the bounded rectangle and every object or field touched by the rectangle is calculated. If a preselected threshold percentage of the bounded rectangle overlaps a single field or object, that field or object is identified as the target. If no one field or object is overlapped by at least the preselected percentage area of the bounded rectangle, bounding rectangles are defined for each character or stroke in the block of data. The amount of overlap of the bounded characters is determined, and the field having the greatest area of overlap is identified as the target field.

In an alternate embodiment, a bounded rectangle is generated for the data block and the center of the rectangle is determined. The object overlapped by the center of the writing rectangle is identified as the target object.

FIG. 1 is a diagram of an entry form on the display of a computer system.

FIG. 2 is an enlarged view of fields 104, 105, and 106 of FIG. 1.

FIG. 3 is a block diagram of the present invention.

FIG. 4 is a diagram illustrating X displacement in the present invention.

FIG. 5 is a diagram illustrating the bounding of individual characters in the present invention.

FIG. 6 is an expanded view of the boundary of fields 403 and 404 of FIG. 4.

FIG. 7 is a flow diagram illustrating the X displacement algorithm of the present invention.

FIGS. 8A-8C are examples illustrating Y displacement in the present invention.

FIG. 9 is a flow diagram illustrating the operation of the Y displacement algorithm of the present invention.

FIG. 10 is a diagram illustrating targeting in the present invention.

FIGS. 11A and 11B are diagrams illustrating the second step of the targeting process of the present invention.

FIG. 12 is a flow diagram illustrating the targeting algorithm of the present invention.

FIG. 13 illustrates diagrams of gestures for use in the present invention.

FIG. 14 is a flow diagram illustrating the gesture targeting algorithm of the present invention.

A targeting system for use in a computer system is described. In the following description, numerous specific details, such as processor type, processor speed, operating system type, etc. are set forth in detail to provide a more thorough description of the present invention. It will be apparent, however, to one skilled in the art, that the present invention may be practiced without these specific details. In other instances, well known features have not been described in detail so as not to unnecessarily obscure the present invention.

The invention provides a splitting and targeting system for use in handwriting entry computer systems. The targeting decision of the present invention is not made until a block of data has been entered. This is in contrast to the prior art, in which targeting decisions are made at the initial stages of the entry of the data to be targeted. The present invention uses a boundary analysis scheme to determine the intended target field of the data.

The preferred embodiment of the invention is incorporated in computer software for use, for example, with the PenPoint.TM. operating system for pen-based computers, such as those manufactured by GO.TM. Corporation of Foster City, Calif. However, the invention can be used with a wide variety of other operating systems and other computers and computer systems.

FIG. 1 shows an example of a handwriting entry computer of a type that may be used with the present invention. It consists of a pen sensitive display 102 disposed in a housing 101. The front of the housing features an on/off button 110. Input/output ports for a disk drive, communications, and a printer, a power supply socket, and a contrast control (not visible) are located along the top 111 of housing 101.

The pen-sensitive display senses the position of a special stylus 103 when the tip of the stylus is near to, or contacts the display.

Internally, the computer of FIG. 1 uses at least an Intel 80286 microprocessor chip running at 16 Mhz or more. Preferably, at least four megabytes of random access memory (RAM) is included.

The items on the display are accessed with hand held stylus 103. The stylus may be used to write characters, "gestures", words or illustrations on the display. Except for certain standard "gestures", the way that such handwritten input is handled generally depends on the specific software application being used.

"Gestures" are simple types of pen movements that invoke certain specified commands. The present invention utilizes approximately a dozen standard "gestures" that form part of its user interface. Examples of these "gestures" are left and right brackets ("[" and "]"), often used for selecting words or a section of text, an up-caret (" "), for accessing an editing pad that can be used for data entry, single strokes or "flicks" right, left, up or down, which are used for scrolling, and "taps" or "presses" which are used to invoke commands.

The operating system of the preferred embodiment of the present invention also provides data to an application about any writing that is done on the display with the stylus. The operating system records events such as "pen down", "pen up", pen position, and pen movement, and makes the record of such events available to applications running on the computer system.

The present invention implements a targeting scheme that makes targeting decisions based on the entire block of data that is intended to be entered in a target field or object. Using the present invention a block of data is identified and the boundaries of the smallest rectangle that contains the data is determined. If more than a preselected percentage of the area of the rectangle defined by the boundaries of the data is within the boundaries of a particular field, that field is defined to be the target field. If that threshold condition is not met, a boundary is defined for each stroke in the block of data. The areas of the rectangles defined by the boundaries of each stroke are then examined. The total overlap between each field and all stroke boundary boxes is calculated. The target that has the greatest total stroke overlap area is selected.

The present invention is described in connection with the entry of handwritten data consisting of one or more pen strokes. This is by way of example only, as any type of data may be used in connection with this invention.

Using this invention, a splitting decision to identify a block of data is made as strokes are entered. A targeting decision is made only after the entry of a block of data has been completed. Blocks of data may consist of strokes, words, numerals, symbols, gestures, or combinations thereof. Blocks of data are identified by detecting and analyzing the displacement in the X and Y directions of an XY coordinate system between a current stroke and a previous stroke. The completion of entry of a block of data is identified when entry of a new block of data begins. The entry of a new block of data begins when a current stroke is displaced from a previous stroke by a certain amount. When these conditions are satisfied, the current stroke is said to be "split" from the previous stroke.

Splitting in the X direction

In the following descriptions of splitting in the X direction and the Y direction, examples are provided of displacements used in the preferred embodiment of the invention. These are given by way of example only. Other displacement may be used without departing from the spirit and scope of the present invention.

The operation of the present invention in making decisions concerning splitting in the X direction is illustrated in FIG. 4. Referring to FIG. 4, an enlarged view of four fields 401-404, arranged in a two-by-two array, is shown. The present invention identifies a stroke as being separate from prior strokes if the new stroke is displaced in the X direction by a predetermined distance. In the preferred embodiment, this distance is greater than 0.5 inches.

Referring to FIG. 4, the words "Tom" 405A and "Jones" 406A have been written in fields 401 and 402. Word 405A is written entirely in field 401, while word 406A begins in field 401 and extends into field 402.

An algorithm (described in detail below) is performed comparing the location of each stroke with the previous stroke to determine if the current stroke is to be grouped with prior strokes or to be treated as a separate stroke or group of strokes. When this comparison is done for each of the strokes that make up the letters "T," "o" and "m" in the word "Tom," the X displacement is less than 0.50 inches in each case so those letters are grouped as a single block of data 405A. However, the X displacement 407A between the "m" in Tom and the first stroke, (the "hook"), of the letter "J" in Jones is greater than 0.50 inches. Therefore, that stroke, (and consequently the letter "J"), is a candidate for a "split" from the "m" at the end of the word "Tom". However, it is not actually split from the prior block of strokes because the first stroke (the hook of the J), is not less than 49% in target field 401. The remaining strokes of the letters that make up the word Jones are all within the appropriate X distance, and so are not candidates for splitting.

The X displacement calculation is performed by accessing certain information that is provided about each stroke of data entered into the computer of the present invention. When a stroke is entered in a computer, the "bounds" of the stroke are determined. For example, the bounds of the letter m are shown as dashed rectangle 501 in FIG. 5. The bounds are defined by the points of intersections of horizontal lines drawn at the uppermost and lowermost points of the stroke, as well as vertical lines drawn at the leftmost and right-most points of the stroke. Thus, the bounds or rectangles include each point of this stroke under consideration. The bounds are defined by an origin point X.sub.P, a width w.sub.P representing the X displacement from the origin X.sub.P and a height h.sub.P representing the vertical displacement from the origin X.sub.P. In the present invention, the ".sub.P " indicates that the information is for the previous stroke that has been entered. Similarly, the current stroke (for example, the hook of the letter "J") of FIG. 5, is defined by a rectangular bounds 502. The current stroke has an origin X.sub.C (where the ".sub.C " indicates the current stroke), a width w.sub.C and a height h.sub.C. The X displacement is determined by the following equation:

To determine if a subsequent stroke or block is to be targeted to a different field, the present invention reviews every stroke as it is generated to determine if it begins a new block of data. Refer now to the data in fields 403 and 404. Again, the word Tom 405B is written entirely within field 403. The X displacement 407B between the "m" of Tom and the hook of the letter "J" of Jones is greater than 0.50 inches. Therefore, the first stroke of the letter "J" of the word Jones is a candidate for splitting from the block of data that ends with the stroke "m". An analysis of the first stroke of the block Jones 406B is undertaken to determine if a split does occur. Referring now to FIG. 6, an enlarged view of the first stroke of the letter "J" is illustrated. In the present invention, if the first stroke of a new word is more than 50 percent in a different field than the preceding stroke, a split occurs.

In the example of FIG. 6, the bounds of the stroke are drawn, and the ratio of the areas overlying fields 403 and 404 is determined. A rectangle formed by the line 601, 602, 603 (the boundary between fields 403 and 404 between lines 602 and 604) and line 604 defines the area of the bounds of the stroke that lies within the boundaries of field 403. Similarly, a rectangle 603, 605, 606, 607 define the area of the boundaries of the stroke that lies within the boundaries of field 404. In the example shown, the area of the rectangle 603, 605, 606, 607 is greater than the area of the rectangle 601, 602, 603, 604. Therefore, the stroke, and by extension, all strokes following it, are split from the block "Tom".

A flow diagram of the operation of the X displacement algorithm of the present invention is illustrated in FIG. 7. At step 701, a stroke is written by the user. At decision block 702, the argument "first stroke?" is made. If the argument is true, there is no prior stroke to compare the stroke with so the stroke is stored at step 703 and the system returns to decision block 702. If the argument is false, the system proceeds to step 704 and the X.sub.C, Y.sub.C, h.sub.C and w.sub.C values for the stroke bounds are generated.

After these values are generated, the system determines whether "ABS((X.sub.P +w.sub.P)-Xc)>0.50 inches?". is made. If the argument is false, the system proceeds to step 707. If the argument is true, the system proceeds to decision block 705 and the argument "New stroke <50% in old target?" is made. If the argument at decision block 705 is false, the system proceeds to step 707. If the argument at decision block 705 is true, the system proceeds to step 706 and the conditions for splitting a stroke are met. At step 706, the stroke is split from the prior stroke. At step 707, the stroke is stored as the previous stroke and the process ends at step 708.

Splitting in the Y Direction

The present invention identifies a block of data as a candidate for splitting if the block satisfies a three-part test for displacement in the Y direction. The first test looks for the Y displacement between the end of a previous stroke and the beginning of a stroke. If the Y displacement is greater than 0.15 inches, the first part of the test is satisfied and the current stroke is a candidate to be split from the prior stroke.

The second test determines if the current stroke is located between the upper and lower bounds of the prior stroke. If the current stroke is not within the upper and lower bounds of the prior stroke, the second part of the test is satisfied. This test is to identify small strokes that may be written after large strokes that make up capital letters and are entirely within the upper and lower bounds of the prior large stroke. Although the distance between the vertical distance of the large stroke and the small stroke may be greater than 0.15 inches, because the small stroke is with the bounds of the large stroke, no splitting will occur.

The third part of the test compares the centers of the bounded areas of a prior stroke and a current stroke. If the centers are at least 0.25 inches apart in the Y direction, then the third part of the test is satisfied and the current stroke is a candidate to be split from the prior stroke. If a stroke that is a candidate for splitting also has more than 50% of its bounded area in a different target than the previous stroke, it is split from the previous stroke.

A number of examples of the application of the Y displacement tests are illustrated in FIGS. 8A-8C. Referring first to FIG. 8A, two strokes "S" and "o" are shown. The stroke S is bounded and has an origin at a point X.sub.P, Y.sub.P with the width w.sub.P and a height h.sub.P. The stroke "o" is a small o and has an origin at point X.sub.C, Y.sub.C with a width w.sub.C and a height h.sub.C. In the first test, it is determined if the Y displacement between the previous stroke "S" and the current stroke "o" is greater than 0.15 inches. This is accomplished by the equation:

In the example shown, this distance is greater than 0.15 inches. In the preferred embodiment of the present invention, the Y displacement between the lower bounds is also compared to determine if the stroke is a candidate for splitting based on Y displacement. This is accomplished by the equation:

In the example of FIG. 8A, this distance is also >0.15 inches so the stroke o is still a candidate for splitting. Applying the second tests to the example of FIG. 8A, it is determined if the current stroke is completely contained within the upper and lower bounds of the first stroke. This is accomplished by the following equation:

Implementing this equation, it is seen that the current stroke "o" is completely contained within the upper and lower boundaries of the prior stroke "S". Therefore, these strokes should not be split based on Y displacement.

Referring now to FIG. 8B, the same two strokes "S" and "o" are illustrated, but in a different orientation than in FIG. 8A. Applying the first test, and applying equation 2 it is determined that there is at least 0.15 inches between Y.sub.P and Y.sub.C. Similarly, applying Equation 3 yields a displacement greater than 0.15 inches, as well. Therefore, the first part of the test is met. Applying the second test, it is shown that the stroke o is not contained within the upper and lower boundaries of the previous stroke. Therefore, the second test is met and the stroke remains a candidate for splitting based on Y displacement. Next, the third test is applied and the centers of the bounds of the current and previous character strokes are examined. This is accomplished by the equation:

The third test fails in the example of FIG. 8B because the centers of the current stroke "o" and the previous stroke "S" are less than 0.25 inches apart.

FIG. 8C illustrates an example where all three tests are met and a splitting of strokes based on Y displacement is proper, if the current stroke is also greater than 50% in a different target than the previous stroke. The first test is met because the difference based on Equation 2 is >0.15 inches. Similarly, Equation 3 is satisfied because it also results in a distance of >0.15 inches.

The second test is met because the current stroke is not contained entirely within the upper and lower bounds of the prior character. Finally, the third test is met because the centers of the bounds of the current and prior strokes are more than 0.25 inches apart.

The present invention also handles special cases, such as the top stroke of an "F", "J", "T" as well as the dot on a small "i". For letters having a top, horizontal stroke, often a user does not actually touch the top stroke to the remainder of the strokes of the character. In these circumstances, the top stroke may be incorrectly identified as a stroke that is to be split based on Y displacement. The present invention applies the test that if a stroke has a slope of less than one-third, it is assumed to be the top of a capital letter and the Y displacement test is not executed. For the dot of an "i", (which may often satisfy the conditions for splitting based on Y displacement), if the height plus the width of the stroke (the dot of an i) is less than 8 points, the stroke is identified as the dot of an i and no Y displacement test is implemented.

The dot on an i may also create problems because one thing that should be permitted is for a user to tap on two different fields and have the taps split appropriately. The present invention also implements the convention that if the last stroke was also a tap (a potential dot of an i) then the "dot of the i test" is not applied to the current stroke and splitting is allowed on the second tap.

As with the splitting decision in the X direction, if a new stroke satisfies the splitting decision based on the Y displacement tests, a decision is then made as to the targeting of the new stroke. If the new stroke falls more than 50 percent inside a separate target field than the previous stroke, then the new stroke is split from the old stroke. If the new stroke is more than 50 percent in the original target field, then that stroke and strokes associated with that stroke are not split from the prior stroke.

A flow diagram illustrating the operation of the present invention in determining splitting the Y direction is illustrated in FIG. 9. The system begins at step 901 where a stroke is written by a user. At decision block 902, the argument "first stroke?" is made. If the argument is true, meaning there have been no prior strokes, the system proceeds to step 903 where the stroke is stored. After step 903, the system returns to decision block 902.

If the argument at decision block 902 is false, the system proceeds to step 904 and the values X.sub.C, Y.sub.C, h.sub.C and w.sub.C are generated for the current stroke.

At decision block 905, the argument "ABS(Y.sub.P -Y.sub.C)>0.15?" is made. If the argument is false, no splitting occurs and the system proceeds to step 914. If the argument is true, the system proceeds to decision block 906. At decision block 906, the argument "ABS((Y.sub.P +h.sub.P)-(Y.sub.C +h.sub.C))>0.15?" is made. If this argument is false, the system moves to step 914. If the argument is true, the first part of the Y displacement test is met and the system proceeds to decision block 907.

At decision block 907, the argument "(Y.sub.C >Y.sub.P) AND (Y.sub.C +h.sub.C)<(Y.sub.P +h.sub.P))?" is made. If the argument is false, the system proceeds to step 914. If the argument is true, the second part of the Y displacement test is met and the system proceeds to decision block 908.

At decision block 908, the argument "ABS(Y.sub.P +(h.sub.P /2))-(Y.sub.C +(h.sub.C /2))>0.25 inches" is made. If the argument is false, the system moves to step 914. If the argument is true, the third part of the Y displacement test is met and the system proceeds to decision blocks 909-911. These decision blocks are used to determine if any of the exceptions (double tap, dot of an i, top of a capital letter) are met. At decision block 909 the argument "previous stroke a tap?" is made. That is, was the prior stroke a tap itself. If the argument is true, the system proceeds to step 913. If the argument is false, the system proceeds to decision block 910. At decision block 910, the argument "dot of i?" is made. If the argument is true, that is, the mark is the dot of an i, the system proceeds to step 914 and no splitting of the strokes is performed. If the argument is false, the system proceeds to decision block 911. At decision block 911, the argument "cap of letter?" is made. If the argument is true, no splitting is performed and the system proceeds to step 914. If the argument is false, none of the exceptions have been met and the system proceeds to step 912. At decision block 912, the argument "New stroke greater than 50% in new target?" is made. If the argument at decision block 912 is false, the system proceeds to step 914. If the argument at decision block 912 is true, the system proceeds to step 913. At step 913, the current stroke is split from the prior stroke. At step 914, the current stroke is then stored as the previous stroke and the process ends at step 915.

Targeting

After identifying a block of data by using the splitting algorithms described above, the present invention employs a targeting algorithm to determine the intended target field of the block of data. The present invention uses a two-part test for the targeting algorithm. In the first part of the test, the bounds of the data block are determined and the percentages of the bounded area that lie over possible target fields is determined. If a preselected percentage of the bounded area of the block of data falls within the boundaries of a single field, that field is identified as the target field. In the preferred embodiment of this invention, the preselected percentage is 70%. However, other preselected percentages can be utilized as a threshold without departing from the scope of the invention.

An example of an application of the threshold test is illustrated in FIG. 10. In FIG. 10, there are two adjacent fields, 1001 and 1002. The word "Tom" is written with the intended target field being field 1001. After the word Tom is written and identified as a block of data, the bounds of the block of data are determined and the values X.sub.C, Y.sub.C, h.sub.C and w.sub.C are generated. Next, comparison of the areas of the bounded block of data that overlap fields 1001 and 1002 are compared. The boundary between fields 1001 and 1002 intersects the bounds of the word Tom at point n, intersecting the vertical bounds of the word Tom between the origin Y.sub.C and the bottom edge at Y.sub.C +h.sub.C. The area of the portion overlaying field 1001 is generated by multiplying the length of the line segment between points Y.sub.C and n by the width w.sub.C. This area is Area.sub.1001 and is shaded in FIG. 10. This area is compared to the overall area of the bounds of the block of data, namely h.sub.C .times.w.sub.C to come up with Area.sub.Total. If Area.sub.1001 /Area.sub.Total is greater than 0.7, the target field is field 1001.

There are some circumstances where the first test is not met because less than 70 percent of the bounded area of the block of data overlaps the intended target field. This is particularly true if the block of data includes one or more "descenders," that is, letters with "tails" that extend below the line of writing, such as g, y, j, etc. Such an example is illustrated in FIGS. 11A and 11B. In FIG. 11A, the word "gary" is identified as a block of data. The bounds of the word gary are determined and the values X.sub.C, Y.sub.C, h.sub.C and w.sub.C are determined. The total area of the bounds of the block of data gary, w.sub.C .times.h.sub.C are calculated. Then the areas overlapping fields 1101 and 1102, respectively, are calculated and compared to the overall area. The area overlapping field 1101 is determined by multiplying w.sub.C by the length of the line segment between points Y.sub.C and n. This area, Area.sub.1101 (not shaded) is compared to the total area and is found to be less than 70 percent of the total area. Therefore, the threshold test is not met. Similarly, the shaded area overlying field 1102 is calculated by subtracting the length of the line segment between points Y.sub.C and n from the height h.sub.C and multiplying the result by w.sub.C. This area is compared to the total area and is again found to be less than 70 percent, so the threshold test is not met.

At this point, the present invention determines the target field by determining the bounds of the individual strokes of the block of data and adding the areas overlapping one field and comparing that sum to the sum of the areas overlapping any other fields. The field with the largest area overlapped is the target field. This is illustrated in FIG. 11B. The bounds for the individual strokes are calculated and origins, widths and heights are calculated for each stroke. For example, bounds are determined for the letter g, and origin X.sub.g, Y.sub.g, width w.sub.g and height h.sub.g are determined. By summing the areas overlapping field 1101 and comparing that to the sum of the areas overlapping field 1102, it is dear that the target field is field 1101.

A flow diagram illustrating the operation of the target scheme of the present invention is illustrated in FIG. 12. At step 1201, strokes are collected into a block of data. This is accomplished by executing the Y displacement and X displacement algorithms described previously. At step 1202, the bounds of the block are determined and values X.sub.C, Y.sub.C, w.sub.C and h.sub.C are calculated.

At step 1203, the percentage of the bounded data block that overlaps any one field is compared to the overall area of the data block. The system then proceeds to decision block 1204. At decision block 1204, the argument "> than 70 percent of area overlapping one field?" is made. If the argument is true, the system proceeds to step 1205 and that field is identified as the target field. If the argument at decision block 1204 is false, the system proceeds to step 1206. At step 1206, a stroke by stroke analysis is performed. The analysis is performed by generating bounds for the individual strokes of the data block and comparing the sum of the areas overlapping one field with the sum of the areas overlapping other fields. At step 1207, the field with the largest overlap is identified. The system then proceeds to step 1205 and that field is identified as the target field.

In an alternate embodiment of the invention, the center of the bounded area of a block of data is determined. The field that is overlapped by the center point is then identified. This field is made the target field. The center point of a bounded area is determined by the following equation:

After the center point X.sub.center, Y.sub.center is determined, its coordinates are compared to the coordinates of fields and objects on the display. If the coordinates found within the boundaries of a field or object match the coordinates of the center point, that field or object is the target.

Targeting Gestures

The present invention also implements a scheme for targeting gestures. As noted above, gestures are command strokes that direct certain operations, such as deleting a stroke or word, selecting text, etc. An example of several gestures is illustrated in FIG. 13. These gestures include an "X" often used for deleting text, and a ".check mark.". In the present invention, gestures may have "hot points". A hot point is an area of action of the gesture. Typically, the hot point of a gesture is positioned over the object or field to be acted upon. For example, the "X" has a hot point 1301 at the intersection of the X. The .check mark. has a hot point 1302 at the beginning of the checkpoint.

A flow diagram illustrating the targeting of the present invention with respect to gestures is illustrated in FIG. 14. At step 1401, a user makes a gesture on a computer system, the number of strokes on the gesture are determined and the argument "fewer than predetermined number of strokes?" is made at derision block 1401. In the preferred embodiment of the present invention, a gesture is three strokes or fewer. This is for purposes of example only, and other numbers of strokes can be used to describe gestures. If the argument at derision block 1401 is false, the system proceeds to block 1402 and the strokes are identified as something other than a gesture. If the argument at decision block 1401 is true, the system proceeds to step 1403. At step 1403, strokes are translated as a gesture. At decision block 1404, the argument "did it translate to a meaningful gesture?" is made. If the argument is false, that is, if the attempt of the translation of the gesture did not result in a known or understandable gesture, the system proceeds to step 1402 and the strokes are identified as not being a gesture.

If the argument at decision block 1404 is true, the system proceeds to step 1405 and all the overlapping fields of the strokes of the gesture are determined. At decision block 1406, the argument "how many overlapping fields?" is made. If the result of the argument is one field, then the gesture is targeted to that field at step 1408. If there are no overlapping fields, the system proceeds to step 1407 and the gesture is treated as a form gesture. If there is more than one overlapping field, the system proceeds to step 1409. At step 1409, the preferred direction for the particular gesture is determined. There is a preferred direction of operation for each gesture. This direction is stored in a table. For example, for a checkmark, this direction may be down and to the right. At step 1410, a test rectangle skewed in the preferred direction of the gesture is generated. At step 1411, the field overlap is calculated with the test rectangle. At decision block 1412, the argument "does one field have greater overlap?" is made. If the argument at decision block 1412 is true, the system proceeds to step 1413 and that field is defined as the target of the gesture. If the argument at derision block 1412 is false, the system proceeds to step 1414. At step 1414, a test rectangle skewed in the non-preferred direction is built. At step 1415, the overlap of the field of the gesture boundaries with the underlying fields is recalculated. At decision block 1416, the argument "does one field have greater overlap?" is made. If the argument is true, the system proceeds to step 1417 and the gesture is targeted to that field. If the argument at decision block 1416 is false, the gesture is ignored because of indeterminate targeting at step 1418.

A block diagram of the present invention is illustrated in FIG. 3. A writing instrument 103 is used to write data on the display 102 of computer 101. Information about the strokes of data are provided to identifying means 1501 on line 1500. The identifying means 1501 is used to determine blocks of data using the X displacement and Y displacement tests described previously. When a block of data is identified, it is provided on line 1502 to boundary generating means 1503. Boundary generating means 1503 is used to generate a rectangular boundary around the block of data.

The boundary information is provided to comparing means 1505 on line 1504. The comparing means compares the relative overlap of the boundaries of the block of data with the boundaries of potential target fields. The results of the comparison are provided to the target identifying means 1507 on line 1506. The target identifying means 1507 determines the target field based on the results of the comparison.

In the preferred embodiment of the present invention, the blocks within dashed line 1508 of FIG. 15 are implemented as a series of instructions on a microprocessor based computer system. An example of code that can be used to implement the present invention is illustrated in Tables 1, 2 and 3.

Table 1 illustrates code for use in implementing the splitting and targeting schemes of the present invention. Table 2 illustrates code for use in implementing gesture targeting and directional preferences. Table 3 illustrates code for determining whether to append strokes to prior strokes.

Thus, a method and apparatus for implementing a targeting scheme is described. ##SPC1##