Note: Descriptions are shown in the official language in which they were submitted.
~lqs~o~
BACKGROUND OF THE INVENTION:
This invention relates to computer input devices and more particularly to a hand-held
means for accurately digitizing the X Y coordinates which define graphical features
appearing on printed documents.
Much of the world's information still exists on printed media, either in the form of textual
information or as graphical features appearing on maps, drawings, photographs and the
like. If the information contained on these historical documents is digitized into a
computer, it's value can be enhanced using a wide variety of computerized applications
which transform, organize and distribute the data. It is therefore desirable to devise
efflcient means to digitize textual and graphical information from printed documents into
a computer readable format.
Text based documents can be transformed into computer readable ASCII codes simply by
means of a manual keyboarding however this approach is too labor intensive for large text
digitizing tasks. A more automated method of digitizing large volumes of text is to first
raster-scan the typewritten pages so as to create a bit-mapped image of each alpha-
numeric character. These bit-mapped images can then be analyzed using an OpticalCharacter Recognition program which first creates a vector graphic for each character.
Each vector graphic contains only the X-Y coordinates of the key points and lines which
geometrically describe the shape of each character's scanned image. Once vectorized, an
OCR algorithm can more easily match these compact mathematical descriptions of each
scanned character to its corresponding ASCII character code.
The purpose of the present invention is to digitize graphical documents such as maps,
drawings or photographs into a computer readable format. The prior art reveals various
means for accomplishing this task which are somewhat analogous to the methods used for
digitizing textual documents. One approach is to simply raster-scan the entire document
thereby creating a bit-map image of the various graphical elements appearing on the
21 95807
printed document. This scanned image can be displayed on a col--puler monitor however
the large bit-map file consumes a large amount of computer storage space. More
importantly, the individual graphical elements in the raster image cannot be spatially
distinguished by the computer thereby severely limiting the level of useful dataprocessing that can take place.
Vectorizing the document' s graphical elements into a spatially referenced set of points,
lines, curves and polygons is therefore desirable since it creates a data file of graphical
objects which is more compact than a simple raster scan and far more amenable tocomputer analysis and manipulation. Once a document has been scanned into a bit-map
file, sophisticated raster to vector algorithms can then be used to try to break down the
bit-mapped image into its separate geometrically defined entities. Automated
vectorization is however not nearly as effective on graphical documents it is on text based
documents. The relatively unpredictable placement of graphical elements which make up
maps and drawings often causes unreliable vectorization performance. Significantoperator intervention and editing is often required to insure that only the desired graphical
elements are extracted from the image. Furthermore, since many graphical documents
such as engineering drawings or nautical charts are much larger than the page size of text
based documents, the raster scanning ha dwar~ required to create the bit-mapped source
images is prohibitively expensive.
For many graphical digitization tasks, it is therefore advantageous for the operator to
visually select, then manually digitize the vectors which make up the desired graphical
elements. Direct vectorization is typically accomplished by means of a specially built
digitization table comprised of a dense grid of electrical sensing elements embedded in
the surface of the table. Each grid node sensor is electrically energized by a hand-held
cursor as it passes into its close proximity, thereby sending a message to the host
computer containing X-Y coordinates of the cursor. To use such a system, the document
being vectorized is first affixed and registered to the table, then the operator uses the
hand-held cursor to visually select and digitize the coordinates of the points which define
the document's important graphical features.
Direct vectorization using a conventional X-Y digitization table elimin~tPs some of the
drawbacks inherent to first sc~nning a graphical document and then using software to
vectorize the bit-mapped features. However, the large size and complexity of dedicated
digitization tables together with their attendant high capital cost are factors which have
limited their widespread use. The prior art reveals several attempts to devise a more
compact and inexpensive means of vectorizing document coordinates using a hand-held
vectorizing cursor. This prior art is based on adaptations to the conventional hand-held
cu---~u~r pointing device commonly referred to as a "mouse". Typically, a computer
mouse is comprised of a hand-held housing, a freely rotateable trackball protruding from
the lower surface of the device, two orthogonally mounted mechanical or optical encoders
which digitize the rotational movement of the trackball and a reference surface over
which the operator rolls the trackball to induce pulses from the X-Y motion sensing
encoders. This conventional mouse configuration permits the user to continuouslydigitize the approximate horizontal trajectory of the operator's hand movements over the
reference surface which the computer can use to ~nim:~te a pointing icon on the
computer's display screen. Due to its low cost and ease of use, trackball mice have found
very wide acceptance in co~ uler systems as a means of controlling the computer's
2t 55807
Graphical User Interface. Since trackball mice have become very inexpensive, devising a
means of using trackball technology to vectorize graphical documents is an economically
attractive alternative to the digitization table.
One approach to realizing a trackball based digitizer is to simply attach a sighting cursor
to the housing of a conventional mouse. In theory, the ch~nging XY coordinates of the
cursor's location can then be computed directly from the trackball's ch~nging XYcoordinates as it rolls over the document. However in practice this approach does not
work accurately enough to satisfy even the least stringent user requirements. The reason
for the inaccurate mouse coordinate computations is that the axes of the trackball's
rotational encoders are not kept in perfect alignment with the orthogonal coordinate
system used by the document being digitized. A good example of a document's
orthogonal coordinate system are the parallel and meridian lines printed onto navigational
charts. However; not all documents have visible coordinates systems, photographs for
example might have an orthogonal reference system defined simply by the four corners of
the paper or the camera's fiducial marks which appear on the image. In fact, anydocument image can have a gridded reference system ~,upefilllposed on it which spatially
references all of its graphical features.
As a hand-held mouse is moved about over a document, slight rotations of the mouse
housing around the center of its track ball (called "yaw") are inevitably induced by the
operator's natural hand movements. These fluctuating miss-alignments between theencoders and the document's orthogonal coordinate system induce geometric distortions
into the XY coordinates that are trigonometrically related to the changing angle of yaw
miss-alignment. The fluctuating geometric distortions are not seen as a random noise in
the cursor coordinates but rather as an accumulating error. The accumulating positional
error often grows proportionally to the distance traveled, thereby preventing the
conventional trackball mouse from being used to accurately vectorize graphical
documents.
The prior art reveals several attempts to rectify the problem posed by yaw induced mouse
coordinate errors. Marvin Shores reveals a device (4,561,183) which physically
constrains the yaw angle of the mouse housing with respect to the document' s reference
surface. The yaw constraint is accomplished by means of a parallelogram arm structure,
similar to a draftsman's "drafting machine". The device is affixed to the mouse at one
end and to the document's supporting table at the other end. As the operator moves the
mouse about over the document, mechanical constraint is applied by the parallelogram
arm to prevent the mouse from changing its yaw angle, thereby maintaining constant
alignment between the mouse' s trackball encoders and the XY frame of reference on the
document. William Bryant reveals a device (4,831,736) of similar intent which
constrains yaw rotation by means of a mouse carriage which is frictionally constrained to
the document by means of orthogonal roller elements. The prior art reveals various other
hand-held mechanical devices which rely on friction between rollers and the document to
prevent yaw rotations from distorting the digital encoder readings. All of this prior art
has significant drawbacks in terms of the cost to manufacture a suitable mechanical
apparatus. Furthermore, these yaw constraint devices are cumbersome to use since they
demand an unnatural hand motion from the operator.
SUMMARY OF THE INVENTION:
21 95807
-
It is therefore the object of the present invention to provide a digitizing mouse which
elimin~tes the aforelllellLioned drawbacks inherent to the prior art. The most significant
distinguishing characteristic of the present invention with respect to the prior art is that
the user is free to move the digitizing mouse over the document without regard to any
yaw rotations that may be imparted to the apparatus by natural hand movements. Instead
of mechanically constraining yaw rotations, all natural variations in yaw angle are
permitte~ The present invention has adaptations which permit the mouse's' yaw
variations to be measured and their distorting effect to be elimin~ted by a geometrical
algoli~hlll which rectifies the device's computed XY position coordinates. The
mechanism used to measure the yaw fluctuations together with the algorithm used to
compute accurate document coordinates for the sighting cursor's location constitute the
innovative content of the present invention.
The present invention builds upon the basic configuration of a conventional computer
mouse pointing device. The basic mouse configuration consists of; a hand-held housing,
a freely rotateable trackball element protruding from the lower surface of said housing,
suspension elements for said rotateable trackball consisting of a triad of roller elements
disposed tangentially to the sphere, two orthogonally mounted digital pulse encoders and
a static graphical surface over which the operator rolls the trackball to induce X-Y motion
sensing output from the two orthogonal encoders. The orthogonal digital pulse encoders
are typically frictional rollers which also serve as two elements of the trackball
suspension however independent optical encoders can also be used. This typical mouse
configuration also includes electrical switches on the upper surface of the housing which
the operator can activate to send control signals to the host computer thereby causing it to
enter into different digitization modes. Appropriate encoder processing circuitry is also
generally included in the conventional mouse configuration which serves to condition and
format the electrical output from the trackball' s pulse encoders and then carry the stream
of signals to the host computer.
The present invention adds three new elements to the conventional mouse configuration,
thereby enabling the mouse to digitize accurate document coordinates regardless of any
yaw fluctuations imparted by the operator's hand movements. The three additionalelements are:
Element #1:
A second, "auxiliary" trackball assembly, said assembly being comprised of: a trackball,
trackball suspension mechanism and trackball encoder mech~ni~m. The auxiliary
trackball assembly is the means by which the present invention measures fluctuations in
the mouse structure's yaw angle. The auxiliary trackball assembly is suspended against
the triad of suspension rollers such that it protrudes from the mouse housing's lower
surface at a precisely known distance from the first, "primary" trackball.
In a pl~fell~d embodiment, the auxiliary trackball assembly differs from the primary
trackball assembly in that it has only one rotational encoder. In this preferredembodiment, the single rotational encoder is affixed within the mouse housing such that
its axis of rotation is coaxial with one of the two rotational encoders located within the
primary trackball assembly. Instantaneous differences between the motion detected by the
-1
21 95807
two coaxially disposed encoders located in the primary and auxiliary trackball assemblies
is used to measure changes in the subtended yaw angle at which the mouse is being held
with respect to the document being digitized.
In another preferred embodiment, the auxiliary trackball assembly is identical to the
primary trackball assembly It therefore incorporates a fourth (redundant) rotational
encoder orthogonally disposed with respect to the one used to measure subtended yaw
angle. The additional rotational encoder on the auxiliary trackball provides redundant
spatial information that can be exploited during computation of the rectified document
coordinates. Using a "least-squares" position computation algorithm, the redundant
trackball movement readings are used to statistically detect when slippage of one of the
trackballs or one of their rotational encoders occurs. This real-time Quality Control
information is used to trigger an alert to the operator that the apparatus needs to be re-
calibrated with respect to the document's coordinate system.
Element#2:
A transparent sighting cursor incorporated into the mouse housing such that the operator
can aim the cursor's cross-hairs onto the graphical document features being digitized.
The cursor' s lower surface contacts the document being digitized thereby, forming a
stable, 3 point support (with the mouse's two trackball contact points) for the device as it
is displaced across the document being digitized. The center of the cursor's cross-hair is
located on the mouse assembly at a precisely known distance from the rotational center of
both trackball mech~ni~ms. The center of the cross-hair is the location on the mouse
structure for which the device's yaw rectified coordinate output is computed. A small
hole at the center of the cursor' s cross-hair permits the user to insert a pencil point
through the sighting cursor to mark the document at the exact location from which a
document coordinate has been digitized. In a preferred embodiment, the sighting cursor
is easily detachable from the mouse's main housing so that, when not being used as a
document digitizer, the device can better serve as a conventional computer pointing
device.
Element #3:
A microprocessor executing a co~ u~er algorithm which receives and processes themotion sensing signals generated by the rotational encoders located on both trackballs. In
a preferred embodiment, the microprocessor is located within the mouse housing where it
computes yaw corrected coordinates and uploads them directly to the host computer via a
serial data cable. In an alternate embodiment, the raw trackball encoder pulses are simply
transmitted over the data cable to its host computer where the raw data is transformed
into geometrically rectified cursor coordinates.
The computer algorithm running on the microprocessor transforms the stream of data
from the 2 trackball's rotational encoders into a stream of geometrically correct cursor
coordinates expressed within the document's orthogonal reference frame. Each pulse
received from any of the trackball motion encoders initiates a computation cycle. Each
computational cycle models the geometrically rectified XY movement measured by the
latest encoder pulse and uses it to update the record of cursor's trajectory over the
document since the start of the whole calibration and digitization process.
21 95807
-
The computer algorithm uses 4 data inputs to compute rectified cursor coordinates:
Input #1:
The known, constant angles and distances that exist between the sighting cursor and the
two trackballs. These are fixed calibration parameters determined during manufacture of
the apparatus.
Input #2:
The misalignment angle and XY offset distance between the orthogonal reference system
of the document being digitized and the orthogonal reference system of the mouse at the
initial epoch of digitization. These are temporary calibration parameters that are
determined by the user at the start of each digitization session. Any slippage of the
trackballs with respect to the document destroys the accuracy of these calibration
parameters and demands that they be re-determined by the operator. The misalignment of
the two reference system axes and the XY translation between them is computed from
XY encoder reading observed by pointing the cursor onto reference marks appearing on
the document while the algorithm is in the calibration mode described below.
Input #3:
The computed change in the apparatus' subtended yaw angle with respect to the
document since the last con~ul~lion cycle. This change in yaw angle is computed from
the difference in readings observed by the two coaxial encoders (one in each trackball
assembly).
Input #4:
The unrectified X and Y displacement of the apparatus within its local, orthogonal frame
of reference that has occurred since the last colll~ul~lional cycle. Since this local frame
of reference is coincident with the orthogonal axes of the two orthogonal encoders on the
primary trackball, these are read directly from the primary trackball' s two encoders. In
the case of the preferred embodiment which incorporates two identical trackball
assemblies to over-determine the rectified cursor coordinates, all 4 encoder readings are
input to the algorithm.
In order to transform these 4 inputs into geometrically rectified cursor coordinates
expressed within the documents frame of reference, the algorithm first computes the
change in subtended yaw angle corresponding to the relative movement of the two
trackballs with respect to the baseline between their centers. This difference between the
two coaxial encoders must be observed and updated for each and every impulse generated
by either encoder. Using readily available mouse components, the angular resolution of
the measured change in yaw would be approximately 5 arc seconds (based on using 300
pulse per inch encoders and a 3 inch subtended baseline between the two trackballs).
Such encoders typically output +l values in one direction of rotation and -1 values in the
opposite direction of rotation, thereby enabling the algorithm to differentiate the sign of
the measured angular movement. The actual implementation of pulse counting and
differencing may involve hardware accumulation circuitry which buffers the encoder
differences and thereby permits the colllpul~tion cycle to take place less often than once
every pulse epoch.
21 95807
The orthogonal reference frame for the cursor's trajectory is initially defined as having its
zero origin coincident with the center of the primary trackball and having its X and Y
axes coincident with the rotational axes of the primary trackball' s X and Y encoders. The
cursor's initial XY coordinates within this reference frame are therefore fixed and easily
determined by the known geometry of the cursor and the two trackballs. Each of the
sequential changes in cursor coordinates is therefore computed with respect to the
arbitrary local reference frame of the mouse when it is first placed on the document to be
digitized and the XY encoders start to feed the algorithm.
The rectification algorithm computes absolute cursor positions by continually
accumulating each local position change to form a record of the cursor's trajectory within
the document's frame of reference. Each successive local change in cursor position is
rotated by the latest yaw change, and translated by the principal trackball' s latest X-Y
position change. This successive updating of the cursor' s frame of reference results in a
geometrically correct record of the cursor' s trajectory with respect to the local reference
frame that was defined by the location and orientation of the mouse at the first epoch of
digitizing the trajectory. To m~int~in the accuracy of this digital record, it is essential that
the user m~int~in continuous tracking of both trackball elements as the mouse travels
over the document (since during any mechanical jump in encoder tracking, the lack of
updates to the mouse centered frame of reference results in erroneous modeling of the
mouse's true trajectory).
The digitized trajectory is a series of yaw corrected XY coordinates referenced within the
orthogonal frame of coordinates defined by the axes of the primary trackball's X and Y
encoders at the instant the mouse begins to move along the digitized trajectory. As the
mouse' s trajectory is digitized with respect to the local reference frame, these observed
coordinates must also be transformed into the absolute coordinate system printed on the
map or document being digitized in order to be of any benefit to users. This is
accomplished by applying a rotation, translation and scale factor to the yaw corrected
trajectory. The rotation, translation and scaling has the effect of bringing the mouse
trajectory's local coordinates system into coincidence with the document's coordinate
system. The correction factors for rotation, translation and scale are determined by the
operator pointing the cursor at a minimum of three non-collinear points on the document
with known position coordinates.
The angular offset between the coordinate frame of reference used by the digitized
trajectory and the frame of reference used by the document is equal to the angular offset
between the mouse's local frame of reference and the document's frame of reference at
the beginning of the trajectory. This angle is trigonometrically deduced by initiating the
calibration procedure after the mouse has been placed at any arbitrary location on the
document. The cursor is then moved to point onto 3 or more known points on the
document's reference axes thereby building a yaw corrected trajectory referenced to the
mouse' s frame of reference at the initial epoch of digitization. Typically the 3 points on
the document would be the lower left hand corner of the document and at one other point
along the X and Y axes respectively however any 3 non-collinear points will suffice.
Knowing the document coordinates of these 3 points as well as their coordinates relative
21 95807
to the initial epoch of the calibration trajectory provides sufficient data to solve for the
desired angular calibration value.
The X and Y offsets between any point on the cursor's modeled trajectory and itscorresponding trajectory expressed in true document coordinates is equal to the X and Y
offsets of the mouse's coordinate origin with respect to the origin of the document' s
coordinate system at the start of the digitized cursor trajectory. These two distances can
be solved for using the same coordinate data collected during the calibration procedure
described above.
The X and Y scale factors used to bring the mouse trajectory's coordinates into the
document's frame of reference are simply the ratios of the actual distance traveled by the
cursor along the X and Y axis of the document to the scaled distance traveled on the
document being digitized. These two scale factors (one for X and one for Y) can be
solved for using the same coordinate data collected during the calibration procedure
described above.
Once the rotation, translation and scale factors calibration factors for the digitization
session have been computed, the operator can then roll the mouse about over the
document to guide the pointing cursor over the document's points and lines. A
continuous stream of yaw rectified document coordinates are thereby computed by the
algorithm described above. While guiding the mouse over the document, the operator
activates function keys on the mouse (or on the host computer's keyboard) which signal
the computer to enter into various digitization modes (e.g. logging on, logging off, point
entry mode, line entry mode and textual attribute entry mode). The computed document
coordinates can be graphically displayed by other application programs running on the
host computer or permanently logged for later use.
In the manner described above, the present invention digitizes accurate coordinates from
graphical documents thereby providing a lower cost and more compact alternative to the
prior art. Although the invention has been described with reference to a particular
illustrative example, it is recognized that various minor mechanical modifications are
possible when implementing this inventive concept.
ADDITIONAL EMBODIMENTS OF THE INVENTION:
In addition to the four principal elements which comprise a preferred embodiment of the
present invention (described above), several additional elements can be added to produce
alternate preferred embodiments:
1) An embodiment of the invention in which a small hole is drilled through the center of
the cursor's cross-hair thereby pe~ g a pencil to be inserted through the cursor to
mark the document at the computed coordinates displayed on the host computer.
2) An embodiment of the invention in which the cursor is removable so that the mouse
can be easily converted from an accurate digitizing device into a standard pointing
device.
21 95807
3) An embodiment of the invention which uses a microprocessor embedded within the
mouse housing to perform all of the geometric rectification (rather than uploading the
raw encoder data to the host computer for processing). This embodiment would
prevent occupying two of the host computer's serial ports and also permit using the
invention in conjunction with small hand-held computers which typically lack
computing resources.
4) An embodiment of the invention in which a switch on the mouse housing permits the
operator to selectively triggers the on-board microprocessor to output rectified XY
coordinates in various data formats which emulate the output format of popular
digitizing tables (such as the "Calcomp", "Kurta" or "Sumigraphics") as well as the
output format of conventional pointing devices (such as the "Microsoft", "Mouse
Systems" or "Logitech").
5) An embodiment of the invention which uses two conventional desktop mice
detachably mounted to a carriage such that they are held in a fixed relationship with
respect to each other as the carriage is moved about over the document. A sighting
cursor is affixed to the carriage such that the two mice and cursor form a triangle very
similar to embodiment described above and the data from the two mice can be
processed by the same algorithm described above. A conventional desktop mouse
normally used simply as a pointing device uses a sprung ball rather than the rigidly
suspended ball used in trackballs. The sprung ball suspension is considerably more
prone to slippage than the rigid suspension however the hardware is less expensive.
With suitably sophisticated QC software, this embodiment might prove to be a cost
effective alternative to the embodiment described above.
6) A programmed function or application running on the host computer which operates
in conjunction with the dual trackball mouse and permits the user to manually move
the mouse's cursor to the coordinates of any desired location on the document. One
implementation of this function would be a "bull's eye" graphic displayed on the host
co~ u~er whose center corresponds to the true present position of a ship or other
vehicle (this position data being input in real-time from a Global Positioning System
receiver). The computer's screen would also display an icon at the current document
coordinates of the mouse' s cursor (expressed in the document' s latitude/longitude
frame of reference). The navigator could plot the ships current position onto the
navigational chart by moving the mouse until the icon is centered in the bull's eye and
then using a pencil to mark the chart through the cursor.
7) A programmed function or application running on the host computer which operates
- in conjunction with the dual trackball mouse and permits the user to digitize planned
routes from a map or chart and then upload the course waypoints into the waypoint
memory of a hand-held GPS receiver. The user can thereby do route planning with
respect to the detailed graphical information on the printed map or chart and then
follow that planned route using the very rudimentary "go left / go right" computer
display typical of hand-held GPS receivers.
8) A programmed function or application running on the host computer which operates
in conjunction with the dual trackball mouse enabling the operator to digitize various
related documents (including maps within the same area but at different scales) into
an integrated whole. Each geo-referenced document is successively vectorized by the
2! 95807
dual trackball mouse into the host co~ ulel-. The limits of larger scale data sets are
displayed as icons within the images of smaller scale documents. Users can access
larger scale information by pointing within the icons, thereby causing the more
detailed vector data to be displayed. Documents other than maps and charts can be
incorporated provided they have a spatial component which can be localized with a
graphical document. For example: a vectorized city street map might show an icon at
the location of an office building. Clicking on that icon might display a large scale
vectorized floor plan of the building with icons at the location of various workers
desks. Clicking on any of these "worker" icons might display a photograph of theworker at that location or textual information of the persons function within the
org~ni7:~tion. In this manner, the vectorizing mouse can be used to integrate the
information contained in various media.
9) A programmed function or application running on the host computer which
implements a verification/correction strategy to insure that the accuracy of thedigitized coordinates do not degrade as the mouse moves about over the document.The algofllhm uses XY misclosures observed at the known location of the document's
grid intersections. The operator can verify the accuracy of digitization at these
locations and, if necessary, choose to have the computer proportionally adjust the XY
coordinate errors that have been digitized since the last verification.
DRAWINGS AND DETAILED DESCRIPTION:
In drawings illustrating an embodiment of the invention:
FIG. 1 is a plan view of the geometry of the 3 encoder hand-held vectorizing digitizer
constructed in accordance with and embodying the present invention.
FIG. 2 is a plan view of the geometry of the 4 encoder hand-held vectorizing digitizer
constructed in accordance with and embodying the present invention.
FIG. 3 is an elevational view of a hand-held vectorizing digitizer constructed in
accordance with and embodying the present invention.
FIG. 4 shows two alternate plan views of a hand-held vectorizing digitizer in useage
scenarios and constructed in accordance with and embodying the present invention.
- lo
