METHOD AND APPARATUS FOR EDITING ELECTRONIC INK
BACKGROUND OF THE INVENTION
1. Field of the Invention This invention relates to computers, and more particular, to a method and apparatus for editing electronic ink for pen-based computers.
2. Description of Related Art As computers have become increasingly popular for various applications, portable computers have been developed for a wide variety of uses. While many such portable computers use a traditional keyboard for input, for smaller computers, particularly including hand-held computers, the use of "pens" as an interface has been introduced as a way of making a small computer easier to use. With a pen interface, a user can place a pen or stylus directly on a touch-sensitive screen of the computer to control the software running on the computer and to input information. For many people, writing with a pen is a more natural way of inputing information than using a keyboard.
An example of a prior art pen-based hand-held computer is shown in FIGURE 1. The illustrated hand-held computer 1 is typically about 4 inches by 6.5 inches, with a substantial part of one surface comprising a touch-sensitive display screen 2. The display screen 2 is typically a liquid crystal display (LCD) having a resolution of 240x320 pixels or greater (although larger or smaller pixel arrays could be used) . Various technologies can be used to sense and digitize the location of a pen or stylus 3 touched against the surface of the LCD screen 2 to indicate to the compu- ter's operating system the X-Y coordinates of the touch. Various hardware buttons 4 may be provided to control different functions, and/or to turn power on or off to the unit. In addition, a variety of software buttons or icons 5 may be provided, in known fashion, to indicate such functions as, for example, word processing or a calendar.
An inherent characteristic of such pen-based computers is the use of electronic "ink" to depict input by a user on the touch-sensitive display screen 2. "Ink" comprises a series of pixels changed (e.g., darkened or lightened) as a pen 3 is moved across the touch- sensitive display screen 2 by a user, thus mimicking the application of real ink to paper. The ink input is typically represented internally as one or more "strokes", each comprising a set of points which can be connected on the display screen 2 to give the illusion of continuous lines.
In many systems, characters drawn in electronic ink can be recognized and converted to ASCII text. One such character recognition system is described in U.S. Patent No. 5,125,039, entitled "Object Recognition System", by the inventor of the present invention. In such systems, as a user inputs each ink character, or after several ink characters have been input, the computer applies algorithms to recognize each character as an ASCII character, and replaces the ink representation of the character drawn by the user with a standardized ASCII representation of that character. In other cases, it is desirable to leave the electronic ink unrecognized.
Editing ink input has proven difficult. Two prior methods have generally been used for editing electronic ink input. The first and most common method is to use the pen 3 as an electronic "eraser". In this method, the user touches an eraser icon to enter an erasing mode. Thereafter, any pixel of the display screen 2 that contains electronic ink input is erased if the pen 3 passes over that pixel. This method works very much like a real eraser, and has several similar problems. It is difficult to accurately erase only desired portions of a figure, and nothing else. Thus, it is common to accidentally erase part of a figure that was intended to be kept, requiring the user to go back and redraw the partially erased line after changing back to a drawing mode. The problem is exacerbated by the inaccuracies of the digitizer, and inaccuracies and parallax caused by the spacing of the pen 3 from the actual display screen 2 by the glass covering of the display screen 2, both of which makes it difficult to both erase accurately and to fix any inadvertently erased lines.
Another problem with the eraser method is that it leads to a drawing made up of many small strokes, some of which may be difficult to see. Further, what originally appeared to be smooth curves as drawn fre¬ quently end up as uneven curves made up of multiple line segments after erasing and then fixing parts of the original curve.
The second method for editing electronic ink is to have the user select a block of ink, designated by means of a selection rectangle, "lasso" feature, or other means. The user can then move, copy, or delete the selected portion of the ink figure. The biggest problem with this method is accurately selecting only the ink to be erased. The user may often select lines or parts of lines that the user did not intend to change, requiring that the user fix the erased portions.
In addition to the above drawbacks of the prior art, both methods of editing electronic ink make it unlikely that edited ink can be later recognized as ASCII text. Most handwriting recognition algorithms become confused when strokes are moved, partially erased, or consist of many small segments. All of these defects are likely to occur with existing methods of editing electronic ink.
Accordingly, it would be desirable to have an improved method for editing electronic ink, which permits easy and accurate selection of only those portions of a drawing that a user desires to erase and the ability to erase a selected portion without affecting other portions of a displayed figure. The present invention provides such a solution.
SUMMARY OF THE INVENTION
The invention comprises a method and apparatus for editing electronic ink for pen-based computers in which the ink is represented in stroke form. The invention implements a "backspace" ink function, similar to the backspace key on a keyboard. In the preferred embodiment of the invention, selecting a "backspace" ink icon with the pen of a pen-based computer, or pressing a hardware button on the computer, erases the last stroke, or segment of a stroke, drawn by the user. Erasure is accomplished by deleting the last stroke, or segment of a stroke, in a sequential list of strokes representing the user's input. Again selecting the icon or pressing the button erases the previous line stroke or stroke segment, and so on. This method allows the user to accurately erase any amount of electronic ink represented in stroke form without disrupting nearby or overlapping lines.
In an alternative embodiment of the invention, any dis- played line segment of a drawing can be selected as the starting point for erasing, and erasing can be done on a stroke-by-stroke or segment-by-segment basis, either "forward" or "backward" from the selected stroke.
The details of the preferred embodiment of the present invention are set forth in the accompanying drawings and the description below. Once the details of the invention are known, numerous additional innovations and changes will become obvious to one skilled in the art.
BRIEF DESCRIPTION OF THE DRAWINGS
FIGURE 1 is a front left-side perspective drawing showing a prior art pen-based computer.
FIGURE 2 is a diagrammatic example of electronic ink strokes made on a digitizer/display grid of a pen-based computer, showing a single-stroke curved line and a double-stroke character.
FIGURE 3 is a representation of the stroke data for the single-stroke curved line and the double-stroke charac¬ ter of FIGURE 2.
FIGURE 4 is a diagrammatic example of FIGURE 2, showing the single-stroke curved line after erasure of one stroke of the double-stroke character.
FIGURE 5 is a diagrammatic example of FIGURE 2, showing the single-stroke curved line after erasure of both strokes of the double-stroke character.
FIGURE 6 is a flow-chart of the preferred embodiment of the inventive method.
Like reference numbers and designations in the various drawings refer to like elements. DETAILED DESCRIPTION OF THE INVENTION
Throughout this description, the preferred embodiment and examples shown should be considered as exemplars, rather than limitations on the present invention.
FIGURE 2 is a diagrammatic example of electronic ink strokes made on a digitizer/display grid of a pen-based computer, showing a single-stroke curved line 10 and a character "D" 12 comprising two strokes 14, 16. FIGURE 3 is a representation of the stroke data for the single-stroke curved line 10 and the double-stroke character 12 of FIGURE 2. As can be seen from FIGURE 3, each stroke is represented by a set of paired numbers, each pair comprising the Cartesian coordinates of a pixel. Adjacent pairs of numbers define a segment of the stroke. (A typical input from a digitizer would contain more points than shown; FIGURE 2 is simplified for clarity) .
A numeric representation of a stroke requires at least two pairs of coordinates. As FIGURE 3 shows, the single-stroke curved line 10 can be described as comprising six pairs of pixel coordinates (i.e., five segments) . In the illustrated embodiment, the coordi- nate value "0,0" is used as a delimiter to designate the end of a series of coordinate pairs defining a single stroke; however, other values or means for delimiting strokes may be used.
Alternative ways can be used to represent strokes. For example, the origin for the grid need not be in the "lower left" corner, as is typical of a standard mathematical representation of a Cartesian grid, but may be in the "upper left", which is more typical of the addressing used for a pixel array. As another example, the coordinate points representing a stroke can be compressed, or the strokes can be represented as mathematical equations (such as the equation for a line or a curve) , or in any other desired form. The invention will work with any representation of strokes, such that each stroke can be distinguished from each other stroke. Thus, the term "stroke", as used herein, should be understood to mean any non-bitmapped representation of lines or figures input by a user as electronic ink.
The stroke data may be stored in a computer memory as simply a list of stroke entries in order of creation, each separated by a delimiter. Alternatively, the stroke data may be stored in random order in a computer memory as a linked list, in known fashion. As another alternative, the stroke data may be stored in random order in a computer memory with a list of sequential or linked pointers being used to indirectly define an entry order for the stroke data. Any data structure that permits input strokes to be accessed at least in order (or reverse order) of entry can be used to store the stroke data. Because the strokes comprising each drawing are accessible in the sequential order of input, it is easy to determine the "last" stroke drawn by the user. Hence, the term "stroke list" should be interpreted to cover any format from which the sequential order of input of strokes can be determined.
To display the input strokes, the list of strokes is read from the computer memory. For each stroke, the intensity of the pixels comprising each consecutive pair of coordinate pairs is changed, along with all interpolated pixels in between, in known fashion.
Thus, in accordance with these definitions, the data structure sequence shown in FIGURE 3 shows that the stroke for the curved line 10 in FIGURE 2 was drawn before the vertical line stroke 14 for the character "D" 12, which in turn was drawn before the curved line stroke 16 of the character "D" 12. When the strokes are read from the stroke list, the display of the computer will appear as in FIGURE 2 (without the grid lines) .
To accomplish the "backspace" ink function of the present invention, the computer detects the touch of a pen on a "backspace" ink icon, or the press of a "backspace" hardware button on the computer, by the user. The list of strokes stored in the computer is then examined to determine the last entered stroke. Since the strokes are accessible in sequential order, the last stroke can easily be determined by sequen- tially examining the entire list of strokes until the last "0,0" delimiter is accessed, or by keeping track (e.g., by means of a pointer) of the beginning address of the last stroke entered. Of course, other methods for determining the last entered stroke could also be used.
Once the last entered stroke is located, that stroke entry is simply deleted from the stroke list in the computer memory so that the next prior entry becomes the "last" stroke. Thus, referring to FIGURE 4, when the "backspace" ink function is selected, the stroke for the curved line portion 16 of the character "D" is deleted. Thereafter, the display screen is redrawn to show only the remaining strokes, comprising the single- stroke curved line 10 and the vertical line portion 14 of the character "D" 12. Since the displayed lines are re-drawn based upon the current contents of the stroke list, any pixels in common between a deleted stroke and other strokes are also redrawn. Thus, deletion of a stroke has no effect on the appearance of the remaining strokes. Again selecting the icon or pressing the "backspace" ink button erases the previous stroke in the stroke list, and so on. Thus, in FIGURE 5, pressing the "backspace" ink function again causes the vertical line stroke 14 to be deleted in the manner described above.
If desired, after the "backspace" ink function is selected, the last stroke may be highlighted, in known fashion (e.g., by holding or blinking the stroke), and the user prompted for approval of the deletion of that stroke. Also, if the user is prompted for a deletion, but reselects the "backspace" ink function, the prior stroke in the stroke list can be highlighted, and the user prompted for approval of the deletion of that stroke. In like manner, further reselection of the "backspace" ink function highlights the next prior stroke in the stroke list for prompted deletion.
FIGURE 6 is a flow-chart of the preferred embodiment of the inventive method. The flow chart shows the following steps in abbreviated form:
1. Test if the pen 3 is in a "backspace ink" icon, or a backspace button has been pressed (Step 60) .
2. If no, loop back to start (Step 61). 3. If yes, then:
3.1 Find the last entry in the list of strokes (Step 62) .
3.2 Delete the found entry (Step 63).
3.3 Redisplay the remaining strokes (Step 64). 4. Go back to start (Step 65).
Of course, other step sequences may be used to accom¬ plish the same function.
In an alternative embodiment of the invention, any dis- played stroke of a drawing can be selected as the starting point for erasing, and erasing can be done on a stroke-by-stroke basis, either "forward" or "back- ward" from the selected stroke. This is most easily accomplished by permitting a user to select with the pen 3 any desired displayed stroke, and setting a pointer to the sequential position of that stroke in the stroke list. If the "backspace ink" function is then selected, the entry of the selected stroke is deleted from the stroke list. The pointer is then set to point to the entry just prior in sequence to the deleted entry. If the "backspace ink" function is selected again, the entry pointed to by the pointer is deleted, and the pointer reset to the prior entry in the stroke list. To delete in a "forward direction", the user selects a different icon or button, and the entry in the stroke list just after the pointer is deleted. In an alternative embodiment, after a deletion, the pointer is set to point to the entry just after the deleted entry, and deletions in either direction are based upon that position as a reference point. In either case, the stroke indicated by the pointer may be highlighted and the user prompted for further deletions.
In another alternative embodiment of the invention, ink is erased segment-by-segment instead of stroke-by- stroke. In this method, pressing a "backspace ink" icon causes ink to be erased one segment at a time in either a forward or backward direction, starting either from the end of the last stroke or from a user-selected point. For example, referring to FIGURE 3, if the last stroke (the curved line portion 16 of the character "D" shown in FIGURE 2) is selected for erasure, the last segment (defined by coordinates 11,2 and 9,1) would be deleted by deleting the last coordinate pair (i.e., 9,1) and moving up the stroke delimiter (i.e., 0,0). This method allows even finer control of exactly which ink input is erased, while maintaining the benefit of not erasing nearby or adjacent strokes. Because the lines of a drawing are erased on a stroke- by-stroke or segment-by-segment basis, the inventive apparatus and method allows the user to accurately erase any amount of electronic ink represented in stroke form without disrupting nearby or overlapping strokes. The invention provides a means for editing electronic ink which permits accurate selection of only those portions of a drawing that a user desires to erase and the ability to erase a selected portion without affecting other portions of a displayed figure.
A number of embodiments of the present invention have been described. Nevertheless, it will be understood that various modifications may be made without departing from the spirit and scope of the invention. Accordingly, it is to be understood that the invention is not to be limited by the specific illustrated embodiment, but only by the scope of the appended claims.