Apple Inc. v. Samsung Electronics Co. Ltd. et al

Filing 462

Declaration of DEOK KEUN Matthew Ahn IN SUPPORT OF #461 APPLES OPENING CLAIM CONSTRUCTION BRIEF PURSUANT TO PATENT L.R. 4-5 filed by Apple Inc.(a California corporation). (Attachments: #1 Exhibit A, #2 Exhibit B Part 1, #3 Exhibit B Part 2, #4 Exhibit C Part 1, #5 Exhibit C Part 2, #6 Exhibit D Part 1, #7 Exhibit D Part 2, #8 Exhibit D Part 3, #9 Exhibit D Part 4, #10 Exhibit E Part 1, #11 Exhibit E Part 2, #12 Exhibit F, #13 Exhibit G, #14 Exhibit H, #15 Exhibit I, #16 Exhibit J, #17 Exhibit K, #18 Exhibit L, #19 Exhibit M Part 1, #20 Exhibit M Part 2, #21 Exhibit N, #22 Exhibit O, #23 Exhibit P, #24 Exhibit Q)(Jacobs, Michael) (Filed on 12/8/2011) Modified on 12/9/2011 linking entry to document #461 (dhm, COURT STAFF).

U.S. Patent

Oct. 12, 2010

Sheet 43 of 45

US 7,812,828 B2

( START )

GET ANY PATH RECENTLY ,750
CREATED BY HAND PART
TOUCHDOWN

PATH
752
PROXIMITY
JUST CROSSED
KEYPRESS
HRESH

N

Y
N

y

PATH
754
IDENTIFIED
AS FINGER NOT
PALM7
Y

PATH'S
HAND SLIDINGI
WRITING 7

756
N

757

DEBOUNCE
OK ?

, 760
FIND CLOSEST
KEY REGION

Y

N
N
764

T 766

CREATE KEYPRESS

APPEND KEYPRESS

QUEUE ELEMENT TO ,
TAIL OF FIFO
KEYPRESS QUEUE

762

ANY KE
REGION
EARBY
y

'

QUEUE ELEMENT
CONTAINING PATH ID, e
CLOSEST KEY &
PRESS T1MESTAMP

FIG. 42

APLNDC00030375

N

U.S. Patent

e

N

Oct. 12, 2010

START )

H6

NN

Sheet 44 of 45

A

US 7,812,828 B2

DELETE CURRENT
ELEMENT EROM •
KEYPRESS QUEUE

PICK ELEMENT AT HEAD p-770
OF KEYPRESS QUEUE

B

778
Y

LEMEN
PATH STILL
IDENTIFIED AS
FINGER ?

y

PATH IN A
SYNCHRONIZED
SUBSET 7

772

N
774

782
B

780

N

i

FINGER SLID
TOO FAR 7

TIME

SINCE PRESS <
TAP TIMEOUT

Y

FINGER
Ll- -•· 7

N
784
APPEND PRECEDING
MODIFIERS &
ELEMENT'S KEY
REG10N SYMBOL TO

786
788
SKIP TO NEXT
ELEMENT IN
QUEUE

C

KEY REGION
A MODIFIER 7

HOST COMM QUEUE
792
Y

790
PATH
PROXIMITY
PROFILE

Y

IMPULSIVE
7

MOST
FINGERS

TOUCHING
?

FIG. 43A

sa-.... ---..:A-A km ISODTft tomaan ilma DIOC innersa Aminimman oft MË

APLNDC00030376

Y

U.S. Patent

805

800

Oct. 12, 2010

Y

802 ,

Sheet 45 of 45

NN

US 7,812,828 B2

D

D FOC 798N
lENT ?

REMCE

ANOTHER
ASYNCHRONOUS

Y

7

AP TI IIEOUT

FINGER
DOWN

HAND'S
OT ER FINGERS

Y
COMPUTE REPEAT
INTERVAL FROM
CURRENT
FINGERPROXIMITY

A

-.

C 806
INITIALIZE
TYPEMATIC
MODE FOR
ELEMENT

80
TIME
SINCE I &
SE

808
y
810

N
812

APPEND PRECEDING
O MODIFIERS & ELEMENT'S
KEY REGION SYMBOL TO

HOST COMM QUEUE

UPDATE vio i TYPEMATIC
SEND TIMESTAMP

FIG. 43B

t½nw nrnuidad hu URPTO from the PIRE Imane Datshame on ---11

APLNDC00030377

1

2

US 7,812,828 B2
ELLIPSE -· · · · G FOR MULTI-TOUCH
SURFACES

will always be a need in the art for multi-function manual
input devices which supplement voice input.
A generic manual input device which combines the typing,
CROSS-u a su -CE TO RELATED
pointing, scrolling, and handwriting capabilities of the stanAPPLICATIONS
s dard input device collectionmusthave ergonomic, economic,
andproductivityadvantages which outweighthe unavoidable
This application is a continuation of 11/015,434, entitled
sacrifices of abandoning device specialization. The generic
"Method and Apparatus for Integrating Manual Input," filed
device must tightly integrate yet clearly distinguish the difDec. 17, 2004 now U.S. Pat. No. 7,339,580, which is a conferent types of input. It should therefore appear modeless to
tinuation of 09/236,513 (now Pat. No. 6,323,846) filed Jan. 10 the user in the sense that the user should not need to provide
25, 1999 which claims the benefit of provisional application
explicit mode switch signals such as buttonpresses, arm relo60/072,509, filed Jan. 26, 1998, each of which is hereby
cations, or stylus pickups before switching from one mput
incorporated by reference in its entirety. This application is
activity to another. Epidemiological studies suggest that repalso related to Application Ser. No. 11/428,501, entitled
etition and force multiply m causmg repetitive strain injuries.
"Capacitive Sensing Arrangement," 11/428,503, entitled 15 Awkward postures, device activation force, wasted motion,
"Touch Surface," 11/428,506, entitled "User Interface Gesand repetition should be minimized to improve ergonomics.
tures," 11/428,515, entitled "User Interface Gestures",
Furthermore, the workload should be spread evenly over all
11/428,522, entitled "Identifying Contacts on a Touch Suravailable muscle groups to avoid repetitive strain.
face," 11/428,521, entitled "Identifying Contacts on a Touch
Repetition can be minimized by allocating to several
Surface", 11/559,736, entitled "Multi-Touch Contact Track- 20 graphical manipulation channels those tasks which require
ing Algorithm", 11/559,763, "Multi-Touch Contact Motion
complex mouse pointer motion sequences. Common graphiExtraction," 11/559,799, entitled "Multi-Touch Contact
cal userinterface operations such as fmding and manipulating
MotionExtraction,"11/559,822,entitled"Multi-TouchCona scroll bar or slider control are much less efficient than
tact Motion Extraction," 11/559,833, entitled Multi-Touch
specialized fmger motions which cause scrolling directly,
Hand Position Offset Computation, each of which is hereby 25 withoutthe step ofrepositioningthe cursor over an on-screen
incorporated by reference in its entirety,
control. Preferably the graphical manipulation channels
should be distributed amongst many finger and hand motion
- - GROUND OF THE INVENTION
combinations to spread the workload. Touchpads and mice
with auxilliary scrolling controls such as the Cirque®=
A. Field of the Invention
so Smartcat touchpad with edge scrolling, the IBM®= ScrollThe present invention relates generally to methods and
Pointm mouse with embedded pointing stick, and the Roller
apparatus for data input, and, more particularly, to a method
Mouse described in U.S. Pat. No. 5,530,455 to Gillick et al.
and apparatus for integrating manual input.
represent small improvements m this area, but still do not
B. Description of the Related Art
provide enough direct manipulation channels to eliminate
Many methods for manual input of data and commands to 35 manyoften-usedcursormotion sequences. Furthermore, as S.
computers are in use today, but each is most efficient and easy
Zhai et al. found in "Dual Stream Input for Pointing and
to use forparticulartypes ofdata input. For example, drawing
Scrolling," Proceedings of CHI '97 Extended Abstracts
tablets with pens or pucks excel at drafting, sketching, and
(1997), manipulationofmore than two degrees offreedom at
quick command gestures. Handwriting with a stylus is cona time is very difficult with these devices, preventing simulvenient for filling out forms which require signatures, special 40 taneous panning, zooming and rotating.
symbols, or small
of text, but handwriting is slow
Another common method for reducing excess motion and
compared to typing and voice input for long documents.
repetition is to automatically continue pointing or scrolling
Mice, finger-sticks and touchpads excel at cursor pointing
movement signals once the user has stopped moving or lifts
and graphical object manipulations such as drag and drop.
the finger. Related art methods can be distinguished by the
Rollers, thumbwheels and trackballs excel at panning and 45 conditions underwhich such motion continuation is enabled.
scrolling. The diversity of tasks that many computer users
In U.S. Pat. No. 4,734,685, Watanabe continues image panencounter in a single day call for all of these techniques, but
ningwhenthe distance and velocity ofpointing device movefew users will pay for a multitude of input devices, and the
ment exceed thresholds. Automatic panning is, stopped by
separate devices are often incompatible in a usability and an
moving the pointing device backin the opposite direction, so
ergonomic sense. For instance, drawingtablets are a must for so stopping requires additional precise movements. In U.S. Pat.
graphics professionals, but switching between drawing and
No. 5,543,591 to Gillespie et al., motion continuation occurs
typing is inconvenient because the pen must be put down or
when the fmger enters an edge border region around a small
held awkwardlybetweenthe fingers while typing. Thus, there
touchpad. Continued motion speed is fixed and the direction
is a long-felt need in the art for a manual input device which
correspondstothedirectionfromthecenterofthetouchpadto
is cheap yet offers --. Jent integration of---nmanual 55 the finger at the edge. Continuation mode ends when the
input techniques.
finger leaves the border region or lifts off the pad. DisadvanSpeech recognition is an exciting new technology which
tageously, users sometimes pause at the edge of the pad
promises to relieve some of the input burden on user hands.
without intending for cursor motion to continue, and the
However, voice is not appropriate for inputting all types of
unexpected motion continuation becomes annoymg. U.S.
data either. Currently, voice input is best-suited for dictation 60 Pat. No. 5,327,161 to Logan et al. describes motion continuof long text documents. Until natural language recognition
ation when the fmger enters a border area as well, but in an
matures sufficiently that very high level voice commands can
alternative trackball emulation mode, motion continuation
be understood by the computer, voice will have little advancanbeafonctionsolelyoflateralfingervelocity and direction
tage over keyboard hot-keys and mouse menus for command
at liftoff. Motion continuation decays due to a friction factor
and control. Furthermore, precise pointing, drawing, and 65 or can be stoppedby a subsequent touchdown on the surface.
manipulation ofgraphical objects is difficult with voice comDisadvantageously, touch velocity at liftoff is not a reliable
mands, no matter how well speech is understood. Thus, there
indicator of the user's desire for motion continuation since

I

a..... - ...:a-a a , ricanTra ham the DINA imana fantahnmaan 04/25/ŽÛ11

APLNDC00030378

US 7,812,828 B2
3

4

when approaching a large target on a display at high speeds
An ergonomic typing system should require minimal key
the user may not stop the pointer completely before liftoff.
tapping force, easily distinguish finger taps from resting
Thus it would be an advance in the art to provide a motion
hands, and cushion the fmgers from the jarring force of surcontinuation method which does not become activated unexface impact. Mechanical and membrane keyboards rely on
pectedly when the user really intended to stop pointer move- 5 the spring force in the keyswitches to prevent activation when
ment at a target but happens to be on a borderorhappens to be
the hands are resting on the keys. This causes an irreconcilmoving at significant speed during liftoff.
able tradeoff between the ergonomic desires to reduce the
Many attempts have been made to embed pointing devices
fatigue from key activating force and to relax the full weight
in a keyboard so thehands do not have to leavetypingposition
ofthehandsontothekeysduringrestperiods.Force---:--i to access the pointing device. These include the integrated 10 zation on touch surfaces is possible with capacitive or active
pointing key described in U.S. Pat. No. 5,189,403 to Franz et
optical sensing, which do not rely on fmger pressure, rather
al., the integrated pointing stick disclosed by J. Rutledge and
than resistive-membrane or surface-acoustic-wave sensing
T. Selker in "Force-to-Motion Functions for Pointing,"
techniques. The related art touch devices discussed below
Human-Computer Interaction- m i n run i '90, pp. 701-06
(1990), and the position sensing keys described in U.S. Pat. 15 will become confused if a whole hand including its four
fmgertips a thumb and possibly palm heels, rests on the surNo. 5,675,361 to Santilli. Nevertheless, the limited moveface. Thus, there exists a long felt need in the art for a multiment range and resolution of these devices, leads to poorer
touch surface typing system based on zero-force capacitive
pointing speed and accuracy than a mouse, and they add
sensing which can tolerate resting hands and a surface cushmechanical complexity to keyboard construction. Thus there
exists a need in the art for pointing methods with higher 20 Ion.
An ergonomic typing system should also adapt to indiresolution, larger movement range, and more degrees offreevidual hand sizes tolerate variations in typing style, and supdom yet which are easily --ble from typing hand posiport a range of healthy hand postures. Though many ergotions.
nomic keyboards have been proposed, mechanical
Touch .._ and touchpads often distinguish pointing
motions from emulated button clicks orkeypressesby assum- 25 keyswitches can only be repositioned at great cost. For
example, the keyboard with concave keywells described by
ing very little lateral fingertip motion will occur during taps
Hargreaves et al. in U.S. Pat. No. 5,689,253 fits most hands
on the touch surface which are intended as clicks. Inherent in
well but also tends to lock the arms in a single position. A
these methods is the assumption that tapping will usually be
touch surface key layout could easily be morphed, translated,
straightdownfromthe suspendedfingerposition, minimizing
those components of fmger motion tangential to the surface. 30 or arbitrarily reconfigured as long as the changes did not
confuse the user. However, touch surfaces may not provide as
This is a valid assumption if the surface is not fmely divided
much laterally orienting tactile feedback as the edges of
into distinct key areas or if the user does a slow, "hunt and
mechanical keyswitches. Thus, there exists a need in the art
peck"visual search for each key before striking. For example,
for a surface typing recognizer which can adapt a key layout
in U.S. Pat. No. 5,543,591 to Gillespie et al., a touchpadsends
all lateral motions to the host computer as cursor movements. 35 to fit individual hand postures and which can sustain typing
accuracy if the hands drift due to limited tactile feedback.
However, if the finger is lifted soon enough after touchdown
Handwriting on smooth touch surfaces using a stylus is
to count as a tap and ifthe accumulatedlateral motions are not
well-knownin the art, but it typically does not integrate well
---ve, any sent motions are undone and a mouse button
with typing andpointing becausethe stylus must be put down
click is sent instead. This method only works for mouse
comman<h such as pointing which can safely be undone, not 40 .u-where or held awkwardly during other input activities.
Also, it may be difficult to distinguish the handwriting activfor dragging or other manipulations. In U.S. Pat. No. 5,666,
ity of the stylus from pointing motions of a fingertip. Thus
113 to Logan, taps with less than about ½s" lateral motion
there exists a need in the art for a method to capture coarse
activate keys on a small keypadwhile lateral motion in excess
handwriting gestures without a stylus and without confusing
of ½6" activates cursor control mode. In both patents cursor
mode is invoked by default when a finger stays onthe surface 45 them with pointing motions.
a long time.
Many of the input differentiation needs cited above could
H......., fast touch typing on a surface divided into a large
be met witha touch sensing technology which distinguishes a
array ofkey regions tends to producemore tangential motions
variety of hand configurations and motions such as sliding
along the surface than related art filtering techniques can
fmger chords and grips. Many mechanical chord keyboards
tolerate. Such an array contains keys in multiple rows and so havebeen designedto detect simultaneous downwardactivity
columns which may not be directly under the fingers, so the
from multiple fmgers, but they do not detect lateral finger
user must reach with the hand or flex or extend fingers to
motionovera largerange. Related art shows several examples
touch many ofthe key regions. Quick reaching andextending
of capacitive touchpads which emulate a mouse or keyboard
imparts significant lateral finger motion while the finger is in
by tracking a single fmger. These typically measure the
the air whichmay still be present whenthe fingercontacts the ss capacitance ofor betweenelongated wires which are laid out
surface. Glancing taps with as much as ¼" lateral motion
in rows and columns. A thin dielectric is interposed between
measured at the surface can easily result. Attempting to filter

the row and column layers. Presence of a fmger perturbs the

or suppress this much motion would make the cursor seem
selfor mutual capacitance for nearby electrodes. Since most
sluggish and unæsponsive. Furthermore, it may be desirable
ofthese technologies use projective row and column sensors
to enter a typematic or automatic key repeat mode instead of so which integrate on one electrode the proximity of all objects
pointing mode when the finger is held in one place on the
ina particularrow or column, they cannot uniquely determine
surface. Any lateral shifting by the fingertip during a prothepositions oftwo ormore objects as discussed in S. Lee, "A
longed fmger press would also be picked up as cursor jitter

Fast Multiple-Touch-Sensitive Input Device," University of

without heavy filtering. Thus, there is a need in the art for a
Toronto Masters Thesis (1984). The best they can do is count
method to distinguish keying from pointing on the same 65 fingertips which happen to lie in a straight row, and even that
surface via more robust hand configuration cues than lateral
will fail ifa thumb or palm is introduced in the same column
motion of a single fmger.
as a fmgertip.

Copy provided by USPTO from the PIRS Image Database on 04/25/2011

APLNDC00030379

5

6

US 7,812,828 B2
In U.S. Pat. Nos. 5,565,658 and 5,305,017, Gerpheide et al.
those rows, andthentimingthe dischargeof selected columns
measure the mutual capacitance between row and column
to ground through a discharge resistor. Lee's design required
electrodes by driving one set of electrodes at some clock
only two diodes per electrode, but the principal disadvantage
frequency and sensing how much ofthat frequency is coupled
of Lee's design is that the column diode ...._ bias capacionto a second electrode set. Such synchronous measurements s tances allowed interference between electrodes in the same
are very prone to noise at the driving frequency, so to increase
column.
signal-to-noise ratio they form virtual electrodes comprised
Alloftherelatedcapacitancesensingartcitedaboveutilize
ofmultiple rows or multiple columns, instead ofa single row
interpolation between electrodes to achieve high pointing
and column, and scan through electrode combinations until
resolutionwith economical electrode density. Both Boie et al.
the various mutual capacitances are nulled or balanced. The to and Gillespie et al. discuss compultattion of a centroid from
coupled signal increases with the product of the rows and
all row and columnelectrodereadings. However, for multiple
columns in each virtual electrodes, but the noise only
finger detection, centroid calculation must be carefully limincreases with the sum, giving a net gain in signal-to-noise
ited around local
' to include only one fmger at a time.
ratio for virtual electrodes consisting of more than two rows
Lee utilizes a bisective search technique to find local maxuna
and two columns. However, to uniquely distinguish multiple is and then interpolates only onthe eight nearest neighbor elecobjects, virtual electrode sizes would have to be reduced so
trodes ofeach local maximum electrode. This may work fine
the intersection of the row and column virtual electrodes
for small fingertips, but thumb and pahn contacts may cover
would be no larger than a finger tip, i.e., about two rows and
more than nine electrodes. Thus there exists a need in the art
two columns, which will degrade the signal-to-noise ratio.
for improved means to group exactly those electrodes which
Also, the signal-to-noise ratio drops as row and column 2o are covered by each distinguishable hand contact and to comlengths ° .
to cover a large area.
pute a centroid from such potentially irregular groups.
In U.S. Pat. Nos. 5,543,591, 5,543,590, and 5,495,077,
To take maximum advantage of multi-touch surface sensGillespie et al measure the electrode-finger self-capacitance
ing, complex proximity image processmg 1s necessary to
for row and column electrodes independently. Total electrode
track and identify the parts ofthe hand contacting the surface
capacitance is estimated by measuring the electrode voltage 25 at any one time. Compared to passive optical, images, poxchange caused by injecting or removing a known amount of
imity images provide clear indications of where the body
charge in a known time. All electrodes can be measured
contacts the surface, uncluttered by luminosity variation and
simultaneously if each electrode has its own drivelsense cirextraneous objects in the background. Thus proximity image
cuit. The centroid calculated from all row and column elecfiltering and segmentation stages can be simpler and more
trodesignalsestablishesaninterpolatedverticalandhorizon- 30 reliable than in computer vision approaches to free-space
tal position for a single object. This method may in general
hand tracking such as S. Alimad, "A Usable Real-Time 3D
have higher signal-to-noise ratio than synchronous methods,
HandTracker," Proceedings ofthe 28* Asilomar Conference
but the signal-to-noise ratio is still degraded as row and colon Signals, Systems, and ComputeroPart 2, vol. 2, IEEE
umn lengths i_ __ Signal-to-noise ratio is especially
(1994) or Y. Cui and J. Wang, "Hand Segmentation Using
important for accurately locating objects which are floating a as Learning-Based Prediction and Verification for Hand Sign
few millimeters abovethe pad. Thoughthis method can detect
Recognition," Proceedings ofthe 1996 IEEE Computer Socisuch objects, it tends to report their position as being near the
ety Conference on ComputerVision and Pattern Recognition,
middle of the pad, or simply does not detect floating objects
pp. 88-93 (1996). However, parts of the hand such as internear the edges.
mediate fmgerjoints and the center ofthe palms do not show
Thusthereexistsaneedintheartforacapacitance-sensing 40 up in capacitive proximity images at all if the hand is not
apparatus which does not suffer from poor signal-to-noise
flattened on the surface. Without these intermediate linkages
ratio and the multiple finger indistinguishability problems of
between fingertips and palms the overall hand structure can
touchpads with long row and column electrodes.
only be guessed at, making hand contact identification very
U.S. Pat. No. 5,463,388 to Boie et al. has a capacitive
difficult. Hence the optical flow and contour tracking techsensing system applicable to either keyboard or mouse input, 45 niques whichhave been applied to free-space hand sign lanbut does not consider the problem of integrating both types of
guage recognition as in F. Quek, "Unencumbered Gestural
input simultaneously. Though they mention independent
Interaction," IEEE Multimedia, vol. 3, pp. 36-47 (1996), do
detection of arrayed unit-cell electrodes, their capacitance
not address the special challenges of proximity image tracktransduction circuitry appears too complex to be
mg.
cally reproduced at each electrode. Thus the long lead wires so Synaptics Corp. bas successfully fabricated their electrode
connecting electrodes to remote signal conditioning circuitry
array on flexiblemylarfilm ratherthan stiffcircuit board. This
can pickup noise and will have significant capacitance comis suitable for conforming to the contours of special products,
pared to the finger-electrode self-capacitance, again limiting
but does not provide significant finger cushioning for large
signal-to-noise ratio. Also, they do not recognize the imporsurfaces. Even ifa cushion was placed under the film, the lack
tance of independent electrodes for multiple finger tracking, 55 ofstretchability inthe film, leads, and electrodes would limit
or mention how to track multiple fingers on an independent
the compliance afforded by the compressible material. Boie
electrode array.

et al suggests that placing

-. sihle insulators ontop ofthe

Lee built an early multi-touch electrode array, with 7 mm
electrode arraycushions fmgerimpact. However, an insulator
by 4 mm metal electrodes arranged in 32 rows and 64 colmore thanabout one millimeterthick would seriously attenuumns. The "Fast Multiple-Touch-Sensitive Input Device 60 ate the measured fmger-electrode capacitances. Thus there
(FMTSID)" total active area measured 12" by 16", with a
exists a need in the art for a method to transfer finger capaci0.075 mm Mylar dielectric to insulate fingers from electance influences through an arbitrarily thick cushion.
trodes. Each electrode had one diode connected to a row

charging line and a second diode connected to a column
SUMMARY OF THE INVENTION
discharging line. Electrode capacitance changes were mea- 65
sured singly or in rectangular groups by raisingthevoltageon
It is a primary object of the present invention to provide a
one or more row lines, selectively charging the electrodes in
system and method for integratmg different types of manual

ram, nraumaa hv linpTO from the PlHS Imaae Database on 04/25/2011

APLNDC00030380

7

8

US 7,812,828 B2
input such as typing, multiple degree-of-freedom manipulameans connected in parallel across the integrating capacitor
tion, and handwriting on a multi-touch surface.
to deplete its residual charge; and a voltage-to-voltage transIt is also an object of the present invention to provide a
lation device connected to the output node of the seriessystem and method for distinguishing different types of
connected switching means which produces a voltage repremanual input such as typing, multiple degree-of-freedom s senting the magnitude of the self-capacitance of the sensing
manipulation, and handwriting on a multi-touch surface, via
device.Alternatively,the sensmg device comprises: two elecdifferent hand configurations which are easy for the user to
trical switching means connected together in series having a
learn and easy for the system to recognize.
common node, an input node, and an output node; a dielecIt is a further object of the present invention to provide an
tric-covered sensing electrode connected to the common
improved capacitance-transducing apparatus that is cheaply lo node between the two switching means; a power supply proimplemented near each electrode so that two-dimensional
viding an approximately constant voltage connected to the
sensor arrays of arbitrary size and resolution can be built
input node of the series-connected switching means; and an
without degradation in signal to noise,
integratingcurrent-to-voltagetranslation device connectedto
It is a further object of the present invention to provide an
the output node ofthe series connected switching means, the
electronic system which minimizes the number of sensing 15 current-to-voltagetranslationdeviceproducingavoltagerepelectrodes necessary to obtain proximity images with such
resentingthemagnitudeoftheself-capacitanceofthesensing
resolution that a variety of hand configurations can be distindevice.
shy
To further achieve the objects, the present invention comet another object of the present invention is to provide a
prises a multi-touch surface apparatus for detecting a spatial
multi-touch surface apparatus which is compliant and con- 2o arrangement ofmultiple touch devices on or near the surface
toured to be comfortable and ergonomic under extended use.
of the multi-touch apparatus, comprising: one of a rigid or
Yet another object of the present invention is to provide
flexible surface; a plurality oftwo-dimensional arrays of one
tactile key or hand position feedback without impeding hand
of the sensing devices (recited m the previous paragraph)
resting on the surface or smooth, accurate sliding across the
arrangedonthe surface in groups whereinthe sensing devices
surface
25 within a group have their output nodes connected together
It is a further object of the present invention to provide an
and share the same integrating capacitor, charge depletion
electonic system which can provide images offlesh proximswitch, and voltage-to-voltage translation circuitry; control
ity to an array of sensors with such resolutionthat a variety of
circuitry for enabling a single sensor device from each twohand configurations can be distinguished,
dimensional array; means for selecting the sensor voltage
It is another object of the present invention to provide an 30 data fromeach two-dimensional array; voltage measurement
improved method for invoking cursor motion continuation
circuitry to convert sensor voltage data to a digital code; and
only when the user wants it by not invoking it when significircuitry for communicating the digital code to another eleccant deceleration is detected.
tronic device. The sensor voltage data selecting means comAnother object of the present invention is to identify difprises one of a multiplexing circuitry and a plurality of voltferent hand parts as they contact the surface so that a variety as age measurement circuits.
of hand configurations can be recognized and used to distinTo still further achieve the objects, the present invention
guishdifferentkindsofinputactivity.
comprisesamulti-touchsurfaceapparatusforsensingdiverse
Yet another object of the present invention is to reliably
configurations and activities oftouch devices and generating
extract rotation and scaling as well as translation degrees of
integrated manual input to one of an electronic or electromefreedom from the motion oftwo or more hand contacts to aid 40 chanical device, the apparatus comprismg: an array of one of
in navigation and manipulation of two-dimensional electhe proximity sensing devices described above; a dielectric
tronic documents.
cover having symbols printed thereon that represent actionIt is a further object of the present invention to reliably
to-be-taken when engaged by the touch devices; scanmng
extract tilt and m11 degrees of freedom from hand pressure
means forforming digital proximity images from the array of
differences to aid in navigation and manipulation of three- 45 sensing devices; calibrating means for removing background
dimensional environments.
offsets from the proximity images; recognition means for
Additional objects and advantages of the invention will be
interpreting the configurations and activities of the touch
set forth in part in the description which follows, and in part
devicesthatmakeup theproximity1mages; processing means
will be obvious from the description, or may be learned by
for generating input signals in response to particular touch
practice of the invention. The objects and advantages of the so device configurations and motions; and co--cation
invention will be realized and attained by means of the elemeans for sending the input signals to the electronic or elecments and combinations particularly pointed out in the
tromechanical device.
appended claims.
To even further achieve the objects, the present invention
To achieve the objects and in accordance with the purpose
comprises amulti-touchsurfaceapparatus for sensmg diverse
of the invention, as embodied and broadly described herein, ss configurations and activities of fmgers and palms of one or
the invention comprises a sensing device that is sensitive to
morehands nearthesurfaceand generatingintegratedmanual
changes in self-capacitance brought about by changes in
input to one ofan electronic or electromechanical device, the
proximity ofa touch device to the sensing device, the sensing
apparatus comprising: an array of proximity sensing means
device comprising: two electrical switchingmeans connected
embedded in the surface; scanning means for forming digital
together in series having a w--nnode, an input node, and so proximity images from the proximities measuredby the sensan output node; a dielectric-covered sensing electrode coning means; image segmentation means for collecting into
nected to the common node between the two switching
groupsthoseproximityimagepixelsintensifiedbycontactof
means; a power supply providing an approximately constant
the same distinguishable part of a hand; contact tracking
voltage connected to the input node of the series-connected
means for parameterizing hand contact features and trajectoswitching means; an integrating capacitor to accumulate 65 ries as the contactsmove across successive proximity images,
charge transferred during multiple consecutive switchings of
contact identification means for determining which hand and
the series connected switching means; another switching
which part of the hand is causing each surface contact; syn-

r..« .w.wiana hu tinpTO from the PIRS Imaae Database on 04/25/2011

APLNDC00030381

prisespa method for tracking and identifying vi hord a in 25 ta 1sew oangaen ed ensurs a op o edsrse
m to e en ce
a
c
ouopeo p at o hand contacts
e
ty
1
and entation 30 0su co ee one
3s
e
e ec
u
e

tr o

US 7,812,828 B2
10
chronization detection means for identifying subsets ofidentified contacts which touchdown or liftoff the surface at
approximately the same time, and for generating command
signals in response to synchronous taps ofmultiplefmgers on
the surface; typing recognitionmeans for generatingintended
key symbols from asynchronous finger taps; motion component extraction means for compressing multiple degrees of
freedom ofmultiple fingers into degrees of freedom common
in two and three dimensional graphical manipulation; chord
motion recognition means for generating one of command
and cursor manipulation signals in response to motion m one
or more extracted degrees of freedom by a selected combination of fingers; pen grip detection means for recognizing
contactarrangementswhichresembletheconfigurationofthe
hand when gripping a pen, generating inking signals from
motions of the inner fingers, and generating cursor mampulation signals from motions of the palms while the inner
fingers are lifted; and communication means for sending the
sensed configurations and activities offinger andpalms to one
of the electronic and electromechanical device.
To further achieve the objects, the present invention com-

hanhdwri
ae

ao of a

the

enabling users to instantaneously switch between the input
activities by placing their hands in different configurations
comprising distinguishable combinations of relative hand
contact timing, proximity, shape, size, position, motion and/
5 or identity across a succession of surface proximity images,
the method comprising the steps of: tracking each touching
hand part across
.. proximity images; measuring the
times when each hand part touches down and lifts off the
surfàce; detecting when hand parts touch down or lift off
10 simultaneously; producing discrete key symbols when the
user asynchronously taps, holds, or slides a finger on key
regions defined on the surface; producing discrete mouse
button click commands, key commands, or no signals when
the user synchronously taps two or more fingers from the
15 same hand on the surface; producing gesture commands or
multiple degree-of-freedom manipulation signals when the
userslidestwoormorefingersacrossthesurface;andsending
the produced symbols, commands and manipulation signals
as input to an electronic or an electro-mechanical device.
20
To still even further achieve the objects, the present inven-

Ing a s de
e

n oces

peach o

ec t et oc

r u he

maned

c e

ff co

ing

coen

n the s

ace as either a

handpart touches downand lifts offthe surface; formmg a set
ofthose fingers whichtouchdown from the all fmger floating

fingeridentitiesintheset;generatinginputsignalsofthiskind

bias segmentations and identifications in future images.
occur and continuing to form new subsets, choose and genTo still further achieve the objects, the present invention
erate new kinds of input signals in response to liftoff and
comprises a method forintegrally extractingmultiple degrees
synchronous touchdowns until all fmgers lift off the surface.
of freedom of hand motion fmm sliding motions of two or
To further achieve the objects, the present invention commore fingers ofa hand across a multi-touch surface, one ofthe 45 prises a method for continuing generation of cursor movefmgers preferably being the opposable thumb, the method
ment or scrolling signals from a tangential motion of a touch
comprising the steps of: tracking across successive scans of
device over a touch-sensitive input device surface after touch
the proximity sensor array the trajectories of individual hand
device liftoff from the surface if the touch device operator
parts on the surface; finding an innermost and an outermost
indicates that cursor movement contmuation is desired by
finger contact from contacts identified as fingers onthe given so accelerating or failing to decelerate the tangential motion of
hand; computing a scaling velocity componentfrom a change
the touch device before the touch device is lifted, the method
in a distance between the i-.-st and outermost fmger
comprisingthefollowingsteps:measuring,storingandtranscontacts; computing a rotational velocity component from a
mitting to a computing device two or more representative
change in a vector angle between the innermost and outertangential velocities during touch device manipulation; commost fmger contacts; computing a translation weighting for 55 puting and storing a liftoff velocity from touch device posieach contactingfinger; computingtranslationalvelocity comtions immediatelypriorto the touch device liftoff; comparmg
ponents in two dimensions from a translation weighted averthe liftoff velocity with the representative tangential velociage of the finger velocities tangential to surface; suppresties, and entering a mode for continuously movmg the cursor
sively filtering components whose speeds are consistently
if a tangential liftoff direction approximately equals the replower than the fastest components; transmitting the filtered 60 resentativetangential directions and a tangential liftoff speed
velocity components as control signals to an electronic or
is greater than a predetermined fractional multiple of repreelectromechanical device.
sentative tangential speeds; continuously transmitting cursor
To even further achieve the objects, the present invention
movement signals after liftoffto a computing device suchthat
comprises a manual input integration method for supporting
the cursor movement velocity corresponds to one of the repdiverse hand input activities such as resting the hands, typing, 65 resentative tangential velocities; and ceasing transmission of
multiple degree-of-freedom manipulation, command gesturthe cursor movement signals when the touch device engages
ing and handwriting on a multi-touch surface, the method
the surface again, if comparing means detects significant

APLNDC00030382

US 7,812,828 B2
11
deceleration before liftoff, or if the computing device replies
that the cursor can move no farther or a window can scroll no
farther.

It is to be understood that both the foregoing general
description and the following detailed description are exemplary and explanatory only and are not restrictive ofthe invention as claimed.

BRIEF D- ·<··-· ·ON OF THE DRAWINGS
The accompanying drawings, which are incorporated in
and constitute a part of this specification, illustrate several
embodiments of the invention and together with the description, serve to explain the principles of the invention. In the
drawings:
FIG. 1 is a block diagram of the integrated manual input
apparatus;

12
FIG. 21 is a flow chart of segmentation edge testing;
FIG. 22 is a flow chart of persistent path tracking;
FIG. 23 is a flow chart of the hand part identification
algorithm;
5
FIG. 24 is aVoronoi cell diagram constructed around hand
part attractor pomts;
FIG. 25A is a plot of orientation weighting factor for right
thumb, right inner palm, and left outer palm versus contact
orientation;
10 FIG. 25B is a plot ofthumb size factor versus contact size;
FIG. 25C is a plot of palm size factor versus ratio of total
contact proximity to contact eccentricity;
FIG. 25D is a plot ofpalm separationfactorversus distance
between a contact and it nearest neighbor contact;
15 FIG. 26 is a flow chart of the thumb presence verification
algorithm;
FIG. 27 is a flow chart of an alternative hand part identification algorithm;
FIG. 28 is a flow chart of the pen grip detection process:
20 FIG. 29 is a flow chart ofthe hand identification algorithm:
FIGS. 30A-C show three different hand partition hypotheses for a fixed arrangement of surface contacts;
FIG. 31A is a plot of the hand clutching direction factor
versus horizontal hand velocity;
25
FIG. 31B is a plot ofthe handedness factor versus vertical
position ofoutermost finger relative to next outermost;
FIG. 31C is a plot of the palm cohesion factor versus
horizontal separation between palm contacts
within a hand;
30 FIG. 32 is a plot of the inner finger angle factor versus the
angle between the innermost and next L--.t finger con-

FIG. 2 is a schematic drawing ofthe proximity sensor with
voltage amplifier;
FIG. 3 is a schematic drawing ofthe proximity sensor with
integrating current amplifier;
FIG. 4 is a schematic drawing of the proximity sensor
implemented with field effect transistors;
FIG. 5 is a schematic drawing of the proximity sensor as
used to implement 2D arrays of proximity sensors;
FIG. 6 is a block diagram showinga typical architecture for
a 2D array of proximity sensors where all sensors share the
same amplifier;
FIG. 7 is a block diagram of circuitry used to convert
proximity sensor output to a digital code;
FIG.8 is a block diagram showing a typical architecture for
tacts;
a 2D array of proximity sensors where sensors within a row
FIG. 33 is a plot of the inter-hand separation factor versus
share the same amplifier;
the estimated distance between the right thumb and left
FIG. 9 is a schematic of a circuit useful for enabling the
output gates ofall proximity ..... withina group (arranged 35 thumb;
FIG. 34 is a flow chart ofhand motion component extracin columns);
FIG. 10 is a side view of a 2D proximity sensor array that
tion;
FIG. 35 is a diagram of typical finger trajectories when
is sensitive to the pressure exerted by non-conducting touch
hand is contracting;
objects;
FIG. 11 is a, side view of a 2D proximity sensor array that 40 FIG. 36 is a flow chart ofradial and angular hand velocity
extraction;
provides a compliant surface without loss of spatial sensitivFIG. 37 is a flow chart showing extraction of translational
ity;
FIG. 12 is a side view of a 2D proximity sensor array that
hand velocity components;
FIG. 38 is a flow chart of differential hand pressure extracis sensitive to both the proximity ofconducting touch objects
and to the pressure exerted by ___ nducting touch objects; 45 tion;
FIG. 39A is a flow chart of the fmger synchronization
FIG. 13 is an example proximity image ofa hand flattened
detection loop;
onto the surface with fingers outstretched;
FIG. 39B is a flow chart of chord tap detection;
FIG. 14 is an example proximity image of a band partially
FIG. 40A is a flow chart of the chord motion recognition
closed with fmgertips normal to surface;
FIG.15isanexampleproximityimageofahandinthepen so loop;
FIG. 40B is a flow chart ofchord motion event generation;
grip configuration with thumb and index fmgers pinched;
FIG. 41 is a flow chart ofkey layout morphing;
FIG. 16 is a data flow diagram of the hand tracking and
FIG. 42 is a flow chart of the keypress detection loop;
contact identification system;
FIG. 43A is a flow chart of the keypress acceptance and
FIG. 17 is a flow chart of hand position estimation:
FIG.18 is a data flow diagramofproximity image segmen- ss transmission loop; and
FIG. 43B is a flow chart of typematic emulation.
tation;
FIG. 19 is a diagram ofthe boundary search pattem during

Deat<n- t tONOF THE PREF ---·
construction of an electrode group;
EMBOD-- =
FIG. 20A is a diagram of the segmentation strictness
regions with both hands in their neutral, default position on so
Reference will now be made in detail to the present presurface;
ferred embodiments ofthe invention, examples of which are
FIG. 20B is a diagram of the segmentation strictness
illustrated in the accompanying drawings. Wherever possible
regions when the hands are in asymmetric positions on surthe same reference numbers will be used throughout the
face;
FIG. 20C is a diagram of the segmentation strictness 65 drawings to refer to the same or like parts.
regions when the right hand crosses to the left half of the

surface and the left hand is off the surface;

FIG. 1 is a system block diagram of the entire, integrated

manual input apparatus. Sensor embedded in the multi-touch

Copy provided by USPTO from the PIRS Image Database on 04/25/2011

APLNDC00030383

\
US 7,812,828 B2
13

14

surface 2 detect proximity ofentire flattened hands 4, fmgertips thumbs, palms, and other conductive touch devices to the
surface 2. In a preferred embodiment, the surface is large
enough to comfortably accommodate both hands 4 and is
arched to reduce forearm pronation.
In alternative embodiments the multi-touch surface 2 may
be large enoughto "e motion ofonehand, butmay
be flexible so it can be fitted to an armrest or clothing.
Electronic scanning hardware 6 controls and reads from
each proximity sensor of a sensor array. A calibration module
8 constructs a raw proximity image from a complete scan of
the sensor array and subtracts off any background sensor
offsets. The background sensor offsets can simply be a proximity image taken when nothing is touching the surface.
The offset-corrected proximity image is then passed on to
the contact tracking and identification module 10, which segments the image into distinguishable hand-surface contacts,
tracks and identifies them as they move through
images.
The paths of identified contacts are passed on to a typing
recognizermodule 12, finger synchronizationdetection module 14, motion component extractionmodule 16, andpen grip
detection module 17, which contain soihvare algorithms to
distinguishhand configurations and respond to detected hand

vary widely depending onthe function and processing power
of the host computer. In a preferred embodiment, the communication would take place over computer cables via industry standardprotocols such as Apple Desktop Bus, PS/2 keyboard and mouse protocol for PCs, or Universal Serial Bus
(USB). In alternative embodiments the software processing
of modules 10-18 would be performed within the host computer 22. The multi-touch surface apparatus would only contain enough hardware to scan the proximity sensor array 6,
form proximity images 8, and compæss and send them to the
host computer over a wireless network. The host co
i
cation interface 20 would then play the role of device driver
on the host computer, conveying results of the proximity
image recognition process as input to other applications
residing on the host computer system 22.
In a preferred embodiment the host computer system outputs to a visual display device 24 so that the hands and fingers
4 can manipulate graphical objects on the display screen.
However, in alternative embodiments the host computer
might output to an audio display or control a machine such as
a robot.
The term "proximity" will only be used in reference to the
distance or pressure between a touch device such as a fmger
and the surface 2, not in reference to the distance between
adjacent fingers. "Horizontal" and "vertical" refer to x and y
directional axes withinthe surface plane. Poximity
ments are then interpretedas pressure in a z axis normal to the
surface. The direction "inner" means toward the thumb of a
given hand, and the direction 'oukt means towards the
pinky finger ofa given hand. For the purposes ofthis description, the thumb is considered a fmger unless otherwise noted,
but it does not count as a fingertip. "Contact" is used as a
general term for a hand part when it touches the surface and
appears inthe currentproximity image, and for the group and

motions.

5

10

15

20

25

Thetyping recognizermodule 12 responds to quickpresses
and releases of fingers which are largely asynchronous with
respect to the activity of other fingers on the same hand. It
attempts to find the key region nearest to the location of each
finger tap and forwards the key symbols or commama associated with the nearest key region to the communication interface module 20.
The fmger synchronization detector 14 checks the finger
activity within a hand for simultaneous presses or releases of
a subset of fmgers. When such simultaneous activity is
detected it signals the typing recognizer to ignore or cancel
keystroke processing for fmgers contained in the synchronous subset. It also passes on the combination offinger identities in the synchronous subset to the chord motion recognizer 18.
The motion component extraction module 16 computes
multiple degrees of freedom ofcontrol from individual fmger
motions during easily performablehand manipulations onthe
surface 2, such as hand translations, hand rotation about the
wrist, hand scaling by grasping with the fingers, and differential hand tilting.
The chord motion recognizerproduces chord tap ormotion
events dependent upon both the synchronized finger subset
identifiedby the synchronizationdetector 14 andonthe direc-

so

hand is configuredas ifgripping a pen. Ifsuchan arrangement
is, detected, it forwards the -..... ts ofthe grippingfingers
as inking events to the host communication interface 20.

35 path data structures which represent it.
FIG. 2 is a schematic diagram of a device that outputs a
voltage 58 dependentonthe proximity ofa touch device 38 to
a conductive sense electrode 33. The proximity sensing
device includes two electrical switching means 30 and 31
40 connected together in series having a common node 48, an
input node 46, and an output node 45. A thin dielectric material 32 covers the sensing electrode 33 that is electrically
connected to the
node 48. A power supply 34 providing an approximately constant voltage is connected
45 between reference ground and the input node 46. The two
electrical switches 30 and 31 gate the flow ofcharge from the
power supply 34 to an integrating capacitor 37. The voltage
across the integrating capacitor 37 is translated to another
voltage 58 by a high-impedance voltage amplifier 35. The
50 plates of the integrating capacitor 37 can be discharged by
closing electrical switch 36 until the voltage across the integrating capacitor 37 is near zero. The electrical switches 30
and 31 are openedandclosedin sequence but are never closed
at the same time, although they may be opened at the same
ss time as shown in FIG. 2. Electrical switch 30 is referred to as
the input switch; electrical switch 31 is referred to as the

These inking events can either lay digital ink on the host

output switch; and, electrical switch 36 is referred to as the

tion and speed of motion extracted in 16. These events are
then posted to the host co-acation interface 20.

The pen grip detection module 17 checks for specific
arrangements of identified hand contacts which indicate the

computer display for drawing or signature capture purposes,
shorting switch.
or they can be further interpreted by handwriting recognition
The proximity sensing device shown in FIG. 2 is operated
software which is well known in the art. The detailed steps 60 by closing and opening the electrical switches 30, 31, and 36
within each of the above modules will be further described
in a particular sequence after which the voltage output from
later.
the amplifier 58, which is dependent on the proximity of a
The host communication interface keeps events from both
touch device 38, is recorded. Sensor operationbegins with all
the typing recognizer 12 and chord motion recognizer 18 in a
switches in the open state as shown in FIG. 2. The shorting
single temporally ordered queue and dispatches them to the 65 switch 36 is then closed for a suinciently long time to reduce

host computer system 22. The method of communication

the charge residing on the integrating capacitor 37 to a low

between the interface 20 and host computer system 22 can

level. The shorting switch 37 is then opened. The input switch

copy provided by USPTO from the PIRS Image Database on 04/25/2011

APLNDC00030384

US 7,812,828 B2

15

16

the desired voltage across integrating capacitor 37. In typical
30 is then closed thus allowing charge to flow between the
applications the number is between one and several hundred
power supply and the common node 48 until the voltage
pulse-pairs.
across the input switch 30 becomes zero. Charge Q will
FIG.5 shows theproximity sensor circuitry appropriate for
accumulate on the sensing electrode 33 according to
s use in a system comprising an array of proximity sensors 47
Q=V(e*AyD
(1)
as in a multi-touch surface system. The proximity sensor 47
consists ofthe input transistor30, the output transistor31, the
where V is the voltage of the power supply 34, e is the
sensing electrode 33, the dielectric cover 32 for the sensing
permittivity of the dielectric sensing electrode cover 32 and
electrode 33, and conductive traces 43, 44, 45, and 46. The
the air gap betweenthe cover and the touch device 38, D is the 10 conductive traces are arranged so as to allow the proximity

thickness ofthis dielectric region, and A is the overlap area of
47 compnsmg a 2D array to be closely packed and to
share the sameconductive traces, thus reducingthe number of
the touch device 38 and the sensing electrode 33. Therefore
wires needed in a system. FIG. 6 shows an example of such a
the amount of charge accumulating on the sensing electrode
system where the input nodes 46 of all proximity _ .. are
33 will depend, among other things, on the area ofoverlap of
the touch device 38 and the sensing electrode 33 and the 15 connected together and connected to a power supply 34. The
output nodes 45 of all proximity sensors are connected
distance between the touch device 38 and the sensing electogether and connectedto a single integrating capacitor 37, a
trode 33. The input switch 30 is opened after the voltage
single shorting transistor 36, and a single voltage-to-voltage
across it has become zero, or nearly so. Soon aûer input
amplifier 35. In this implementation, a single proximity senswitch 30 is opened the output switch 31 is closed until the
20 sor 47 is enabled at a time by applying a logic 1 signal first to
voltage across it is nearly zero. Closing the output switch 31
its input gate 43 and then to its output gate 44. This gating of
allows charge to flow between the sensing electrode 33 and
a singleproximitysensor47 one at atime is done by input gate
the integrating capacitor 37 resulting in a voltage change
controller 50 and output gate controller 51. For example, to
across the integrating capacitor 37 according to:
enable the proximity sensor 47 in the lower right corner the
deltaV=(V-Vc)/(1+C*D/e*A)
(2) 25 input gate controller 50 would output a logic one pulse on
conductive trace 43a. This is followed by a logic one pulse on
conductive trace 44h produced by output gate controller 51.
where Vc is the voltage across the integrating capacitor 37
Repetition of this pulse as shown in FIG. 4B would cause
before the output switch 31 was closed, C is the capacitance
charge to build up on integrating capacitor 37 and a correof the integrating capacitor 37, and A and D are equal to their
values when input switch 30 was closed as shown in Equation 3 sponding voltage to appear at the output of the amplifier 58.
The entire array of proximity sensors 47 is thus scanned by
1. Multiple switchings ofthe input 30 and output 31 switches
enabling a single sensor at a time and recording its output.
as described above produce a voltage on the integrating
FIG.7A is a schematic of typical circuitry useful for concapacitor 37 that reflects the proximity ofa touch device 38 to
verting theproximity sensoroutput 58 to a digital code approthe sensing electrode 33.
priate for processing by computer. The proximity sensor outFIG. 3A is a schematic diagram of the proximity sensor in
put 58 is typically non-zero even when there is no touch
which the shorting transistor 36 and the voltage-to-voltage
device (e.g., ref.no.38 inFIG.2)nearby.This non-zero signal
translation device 35 are replaced by a resistor 40 and a
is due to parasitic or stray capacitance present at the common
current-to-voltage translation device 41, respectively. The
node 48 of the proximity sensor and is of relatively constant
integrating function ofcapacitor 37 shown in FIG.2 is, in this 4e value. It is desirable to __ .. this non-zero background
variation ofthe proximity sensor, carried out by the capacitor
signal before convertingthe sensor output 58 to a digital code.
39 shown in FIG. 3A. Those skilled in the art will see that this
This is done by using a differential amplifier 64 to subtract a
variation of the proximity sensor produces a more linear
stored record of the background signal 68 from the sensor
output 58 from multiple switchings of the input and output
output 58. The resulting difference signal 65 is then converted
switches, depending on the relative value of the resistor 40. 4s to a digital code by an ADC (analog to digital converter) 60
Alternatively, the resistor 40 can be replaced by a shorting
producing a K-bit code 66. The stored background signal is
switch 69 (cf. FIG. 3B) to improve linearity. Although, the
first recorded by sampling the array of proximity ...w. 47
circuits shown in FIG. 3 provide a more linear output than the
(FIG. 6) with no touch devices nearby and storing a digital
circuit shown in FIG. 2 the circuits ofFIG. 3 generallyrequire
code specific for each proximity sensor 47 in a memory
dual power supplies while the circuit of FIG. 2 requires only so device 63. The particular code corresponding to the backgroundsignalofeachproximitysensoris selectedby anM-bit
one.
address input 70 to the memory device 63 and applied 69 to a
The electrical switches shown in, FIG. 2 can be impleDAC (digital to analog converter) 61.
mented with various transistor technologies: discrete, inteThe 2D array ofproximity sensors 47 shown in FIG. 6 can
grated, thin film, thick film, polymer, optical, etc. One such
implementation is shown in FIG. 4A where field effect tran- 55 be connected in groups so as to improve the rate at which the
entire array is scanned. This is illustrated in FIG. 8 where the
sistors (FETs) are used as the input 30, output 31, and shorting
36 switches. The FETs are switched on and off by voltages

groups are arranged as columns ofproximity sensors. In this

approach, the input nodes of the proximity sensors are connected together and connected to a power supply 34, as in
on when its gate voltage is logic 1 and switched off when its 60 FIG. 6. The output gates 44 are also connected in the same
way. However, the input gates 43 are now all connected
gate voltage is logic 0. A controller 42 is used to apply gate
together and the output nodes 45 are connected to only those
voltages as a function of time as shown in FIG. 4B. In this
proximity sensors 47 within a row and to a dedicated voltage
example, a sequence of three pairs of pulses (43 and 44) are
amplifier 35. With this connection method, all ofthe proximapplied to the input and output transistor gates. Each pair of
pulses 43 and 44 produces a voltage change across the inte- 65 ity sensors ina columnareenabledat a time, thus reducing the
time to scan the array by a factor N, where N is the number of
grating capacitor 37 as shown in Equation 2. The number of
proximity
in a group. The outputs 58a-h could conpulse pairs applied to input 43 and output 44 gates depends on

applied to their gate terminals (43, 44, and 55). For the pur-

pose of this description we will assume the FET is switched

Copy provided by USPTO from the PIRS Image Database on

APLNDC00030385

US 7,812,828 B2
17

18

To illustrate typical properties of hand contacts as they
nect to dedicated converter circuitry as shown in FIG. 7A or
appear in proximity images, FIGS. 13-15 contain sample
alternatively each output 58a-h could be converted one at a
images captured by a prototype array of parallelogramtime using the circuitry shown in FIG. 7B. In this figure, the
shaped electrodes. Shading ofeach electrode darkens to indioutput signals from each group 58a-h are selected one at a
time by multiplexer 62 and applied to the positive input ofthe 5 cate heightened proximity signals as flesh gets closer to the
surface, compresses against the surface due to hand pressure,
differential amplifier 64. With this later approach, it is
and overlaps the parallelogram more completely. Note that
assumed that the ADC 60 conversion time is much faster than
the resolution of these images is in no way intended to limit
the sensor enable time, thus providing the suggested speed up
the scope of the invention, since certain applications such as
m sensor array scannmg.
to handwriting recognition will clearly require finer electrode
FIG. 9 shows a typical circuit useful for the control of the
arrays than indicated by the electrode size in these sample
proximity sensor's output gate 44. It consists of three input
images. In the discussion that follows, the proximity data
signals 75, 76, 78 and two output signals 44, 77. The output
measured at one electrode during a particular scan cycle
gate signal 44 is logic 1 when both inputs to AND gate 79 are
constitutes one "pixel" of the proximity image captured in
logic 1. The AND input signal 77 becomes logic 1 if input
15 that scan cycle.
signa176 is logic 1 when input signal 78 transitions from logic
FIG.-13 shows a right hand flattened against the surface
0 to logic 1, otherwise it
° logic 0. A linear array of
with fingers outstretched. At the far left is the oblong thumb
these circuits 81 can be connected end-to-end to enable the
201 whichtends to point offat about 120-degrees. The columoutput gates of a single group of proximity sensors at a time
nar blobs arrangedinanare across the top ofthe image are the
as shown in FIG. 8.
20 index finger202, middle fmger203, ring finger 204 and pinky
FIG. 10 shows a cover for the multi-touch surface 89 that
finger 205. Flesh from the proximal fingerjoint, or proximal
permits the system to be sensitive to pressure exerted by
phalanges 209, will appear below each fingertip ifthe fingers
non-conducting touch objects (e.g., gloved fingers) contactare fully extended. The inner 207 and outer 206 palm heels
ing the multi-touch surface. This cover comprises a deformcause the pair ofvery large contacts across the bottom of the
able dielectric touch layer 85, a deformable conducting layer 25 image. Forepalm calluses 213 are visible at the center of the
86, and a compliant dielectric layer 87. The touch surface 85
hand if the palm is fully flattened. This image shows that all
would have a symbol set printed on it appropriate for a spethe hand contacts are roughly oval-shaped, but they differ in
cific application, and this surface could be removed and
pressure, size, orientation, eccentricity and spacing relative to
replaced with another one having a different symbol set. The
one another. This image includes all of the hand parts which
conducting layer 86 is electrically connected 88 to the refer- 30 cantouchthesurfacefromthebottomofonehandbut inmany
ence ground of the proximity sensor's power supply 34.
instances only a few of these parts will be touching the surWhen a touch object presses on the top surface 85 it causes the
face, and the fmgertips may roam widely in relation to the
conducting surface 86 under the touch device to move closer
palms as fingers are flexed and extended.
to the sensing electrode 33 of the pmximity sensor. This
FIG. 14 shows another extreme in which the hand is parresults in a change in the -,-t of charge stored on the 35 tially closed. The thumb 201is adductedtowardthe fingertips
sensing electrode 33 and thus the presence ofthe touch object
202-208 and the fingers are flexed so the fingertips come
can be detected. The amount of charge stored will depend on
down normal instead of tangential to the surface. The height
the pressure exerted by the touch object. More pressure
and intensity of fingertip contacts is lessened somewhat
results in more charge stored as indicated in Equation 1.
because the boney tip rather than fleshy pulp pad is actually
To obtain a softer touch surface on the multi-touch device 40 touching the surface, but fingertip width remains the same.
a thicker and more, compliant dielectric cover could be used.
Adjacent fingertips 202-205 and thumb 201 are so close
However, as the dielectric thickness :
the effeet ofthe
together as to be distinguishable only by slight proximity
touch device on the sensing electrodes 33 spreads out thus
valleys 210 between them. The proximal phalange finger
lowering spatial resolution. A compliant anisotropically-conjoints are suspendedwell above the surface and do not appear
ducting material can be used to counter this negative effect 45 in the image, nor do the forepalm calluses. The palm heels
while also providing a soft touch surface. FIG. 11 shows a
206, 207 are ---hat shortersince only the rear ofthe palm
cover in which a compliant anisotropically-conductingmatecan touch the surface when fmgers are flexed, but the separaria190 is set between a thin dielectric cover 85 and the sensing
tion between them is unchanged. Notice that the proximity
electrodes 33. Ifthe conductivity ofthe compliant material 90
images are unclutteredbybackground objects. Unlike optical
is oriented mostly in the vertical direction, the image formed so images, only conductive objects within a few millimeters of
by a touch device on the surface 85 will be translatedwithout
the surface show up at all.
significant spreading to the sensing electrodes 33, thus preFIG. 15 is a proximity image of a right hand in a pen grip
serving spatial resolution while providing a compliant touch
configuration. The thumb 201 and index fingertip 202 are
pinched togetheras ifthey were holding a pen but in this case
surface.
FIG. 12 shows a cross section ofa multi-touch surface that ss they are touching the surface instead. Actually the thumb and
index finger appearthe same here as in FIG. 14. However, the
senses both the proximity and pressure ofa touch device. The
middle 203, ring 204, and pinky 205 fingers are curled under
touch layer 85 is a thin dielectric that separates touch devices
as ifmaking a fist, so the knuckles from the top ofthe fingers
from the sensing electrodes 33. Proximity sensing is relative
actually touch the surface instead of the fmger tips. The curito this surface. The electrodes 33 and associated switches and
conductors are fabricated on a compliant material 89 which is so ing under of the knuckles actually places them behind the
pinched thumb 201 and index fmgertip 202 very close to the
attached to a rigid metal base 92. The metal base 92 is elecpalm heels 206, 207. The knuckles also appear larger than the
trically connected 88 to the reference ground oftheproximity
curled fingertips ofFIG. 14 but the same size as the flattened
sensor's power supply 34. Whena touch device presses onthe
fmgertips in FIG. 13. These differences in size and arrangetouch surface 85 it causes the sensing electrodes 33 directly
below to move closer to the rigid metal base 92. The distance 65 ment will be measured by the pen grip detector 17 to distinguish this pen grip configurationfromthe closed and flattened
moved depends on the pressure applied and thus the pressure
hand configurations.
exerted by a touch device can be detected as described before.

Cano nravidad hu USPTO from the PIRS Imaae Database on 04/25/2011

APLNDC00030386

US 7,812,828 B2
19

20

It is also convenient to maintain for each hand a set of
FIG. 16 represents the data flow withinthe contact tracking
bitfield data registers for which each bit represents touchand identification module 10. The image segmentation prodown, continued contact or liftofIof a particular finger. Bit
cess 241 takes the most recently scanned proximity image
positions within each bit field correspond to the hand part
data 240 and segments it into groups of electrodes 242 corresponding to the distinguishable hand parts of FIG. 13. The 5 indices above. Such registers can quickly be tested with a bit
mask to determine whether a particular subset of fingers has
filtering and segmentation rules applied in particular regions
touched down. Alternatively, they can be fed into a lookup
of the image are partially determined by feedback of the
table to find the input events associated with a particular
estimated hand offset data 252. The image segmentationprocess 241 outputs a set of electrode group data structures 242
finger chord (combination of fingers). Such finger identity
which are parameterized by fitting an ellipse to the positions 10 bitfields are neededprimarily by the synchronizationdetector
14 and chord motion recognizer 18.
and proximity measurements of the electrodes within each
The last process withinthetracking and identification subgroup.
The path tracking process 245 matches up the parametersystem is the hand position estimator 251, which as described
ized electrode groups 242 with the predictedcontinuations of
above provides biasing feedback to the identification and
contact path data structures 243 extracted from previous 15 segmentation processes. The hand position estimator is
images. Such path tracking ensures continuity of contact
intended to pmvide a conservative guess 252 of lateral hand
representation across proximity images. This makes it posposition under all conditions including when the hand is
sible to measure the velocity of individual hand contacts and
floating above the surface without touching. In this case the
determine when a hand part lifts offthe surface, disappearing
estimate represents a best guess ofwhere the hand will touch
from future images. The path tracking process 245 updates 20 down again. When parts of a hand are touching the surface,
the path positions, velocities, and contact geometry features
the estimate combines the current position mea
-ts of
from the parameters of the current groups 242 and passes
currently identified handparts withpast estimates which may
them on to the contact identification processes 247 and 248.
have been made from more or less reliable identifications.
Fornotational purposes, groups and unidentified paths will be
The simplest but inferior method of obtaining a hand posireferred to by data structure names of the form Gi and Pi 25 tion measurement would be to averagethe positions ofall the
respectively, where the indices i are arbitrary except for the
hand's contacts regardless of identity. If hand parts 201-207
null group GO and null path PO. Particular group and path
were all touching the surface as in FIG. 13 the resulting
parameters will be denoted by subscripts to these structure
centroid would be a decent estimate, lying somewhere under
names and image scan cycles will be denoted by bracketed
the center of the palm since the fmgers and palm heels typiindices, so that, for example, P22, [n] represents the horizon- 30 cally form a ring around the center of the palm. However,
tal position ofpath 2 in the current proximity image, and P2,
consider when only one hand contact is available for the
[n-1] representsthe position in theprevious proximity image.
average. The estimate would...-sthe hand center is at the
The contact identification system is hierarchically split into a
position ofthis lone contact, but ifthe contact is from the right
hand identification process 247 and within-hand finger and
thumb the hand center would actually be 4-8 cm to the right,
palm identification process 248. Given a hand identification 35 orifthe contact is from a palmheel the hand center is actually
for each contact, the finger and palm identification process
4-6 cm higher, or ifthe lone contact is from the middle finger
248 utilizes combinatorial optimization and fuzzy pattern
the hand center should actually be actually 4-6 cm lower.
recognitiontechniques to identify the part ofthehandeausing
FIG. 17 shows the detailed steps within the hand position
each surface contact. Feedback of the estimated hand offset
estimator 251. The steps must be repeated for each hand
helps identify hand contacts when so few contacts appear in
separately. Ina preferredembodiment, theprocess utilizes the
the image that the overall hand structure is not apparent.
within-hand contact identifications (250) to compute (step
The hand identification process 247 utilizes a separate
254) for each contact an offset between the measured contact
combinatorial optimization algorithm to find the assignment
position (Fi,[n],Fi,[n]) andthe default position ofthe particuof left or right hand identity to surface contacts which results 45 lar finger or palm heel (Fi Fig) with hand part identity i.
in the most biomechanically consistent within-hand identifiThe default positions preferably correspond to finger and
cations. It also receives feedback of the estimated hand and
palm positions when the hand is in a neutral posture with
finger offsets 252, primarily for the purpose of temporarily
fingers partially closed, as when resting on home row of a
storing the last measured hand position after fingers in a hand
keyboard. Step 255 averages the individual contact offsets to
lift off the surface. Then if the fingers soon touch back down
in the same region they will more likely receive theirprevious 50 obtain a measured hand offset, (H,,,[n],H..,[n])•
hand identifications.
The output of the identification processes 247 and 248 is
the set ofcontact paths with non-zero hand and finger indices
attached. For notational purposes identified paths will be
referred to as FO for the unidentified or null finger, F1 for the 55
I Fi.[n]
thumb 201, F2 for the index finger 202, F3 for the middle
i=1
finger 203, F4 for the ring finger 204, F5 for the pinky finger
(4)
205, F6 the outer palm heel 206. F7 for the inner palm heel
207, and F8 for the forepalm calluses 208. To denote a particular hand identity this notation can be prefixed with an L 60
I Fi.,,[n]
i=1
for left hand or R for right hand, so that, for example, RF2
denotes the right index finger path. When referring to a particular hand as a whole. LH denotes the left hand and RH
Preferably the weighting Fi,,,,,[n] of each finger and palm
denotes the right hand. In the actual algorithms left hand
identity is represented by a -1 and right hand by +1, so it is 65 heel is approximately its measuredtotal proximity, i.e., Fi,,,
[n]=Fi,[n).This---thatliftedfingers,whoseproximityis
easy to reverse the handedness ofmeasurements taken across
zero, have no influence on the average, and that contacts with
the vertical axis of symmetry.

P-,. .

.ridad hv USPTO from the PIRS Imane Database on 04/25/2011

APLNDC00030387

US 7,812,828 B2
21

22

lower than normal proximity, whose measured positions and
identities are less accurate, have low influence. Furthermore,
if palm heels are touching, their large total proximities will
dominate the average. This is beneficial because the palm
heels, being immobile relative to the hand center comparedto '
i=1
the highly flexible fingers, supply a more reliable indication
of overall hand position. When a hand is not touching the
i 7
(6)
surface, i.e., when all proximities are zero, the measured
offsets are set to zero. This will cause the filtered hand posi- 10
tionestimate below to decay towardthe default handposition.
As long as the contact identifications are correct, this hand
position measurement method eliminates the large errors
causedby assuming lone contacts originatefrom the center of 15 The current contact velocities. (Fi,[n],F,[n]), are
retrievedfrom the path tracking process 245, which ---the hand. Flexing of fingers from their default positions will
them independent of fmger identity. Step 258 updates the
not perturb the measured centroid more than a couple centiestimated hand offsets (H,,,[n],H,,,[n]) using the complete
meters. However, this scheme is susceptible to contact misifilter equations:
dentification, which can cause centroid measurement errors
H,[n]=H,[n]H [n]+(1-H,[n])(HQn-1]+H
of up to 8 cm if only one hand part is touching. Therefore, the 20
current measured offsets are not used directly, but are averH,,,[n]=H,[n]H.,,,[n]+(1-H.Jn])(H,,,[n-1]+H.
aged with previous offset estimates (H,,,[n-1],HQn-1])
[njar)
(8)
using a simple first-order autoregressive filter, forming curFinally, to provide a similarly conservative estimate of the
rent offset estimates (H,,,[n],H,,[n]).
25 positions of particular fingers step 259 computes individual
Step 256 adjusts the filter pole Hoa[n] according to confifinger offsets (Fi,,,[n],Fign]) from the distance between
dence in the current contact identifications. Since finger idenidentified contacts and their corresponding default finger
tifications accumulate reliability as more parts of the hand
positions less the estimatedhandoffsets. For each identifiable
contact the surface one simple measure of identification concontact i, the offsets are computed as:
fidence: is the number of fingers which have touched down 3o
B..xM=H-f=KH.[n]+Fi,N-Fd¢)+(1-H.,[n])
from the hand since the hand last left the surface. Contacts
(R..Jn-1]+R,,[n]At)
(9)
with large total proximities also improve identification reli-

FI ,,M=H,,[n](H.., +R,[n]-Fidefyy 1-H., nD
abilitybecause theyhave strong disambiguating features such
(Fi,,,[n-1]+Fi,,[n]At)
(10)
as size and orientation. "-*ore Hoa[n] is set roughly proThese fmger offsets reflect deviations of finger flexion and
portional to the maximum finger count plus the sumofcontact 35
extension from the neutral posture. If the user places the
proximitiesforthehand.Hoa[n]mustofcoursebenormalized
fingers in an extreme configuration such as the flattened hand
to be between zero and one or the filter will be unstable. Thus
configuration, the collective magnitudes of these finger offwhen confidence in contact identifications is high, i.e., when
sets can be used as an indication of user hand size and finger
many parts of the hand firmly touch the surface, the autorelength compared to the average adult.
gressive filter favors the current ofset measurements. How- *
The parameters (H,,,[n],H,,,[n]) and (Fi,,,[n],Fi, ,[n])
ever, when only one or two contacts have reappeared since
for each hand and finger constitute the estimated hand and
hand liftof, the filter emphasizes previous offset estimates in
finger offset data 252, which is fed back to the segrnentation
the hope that they were based upon more reliable identificaand identification processes during analysis ofthe next proxtions.
45
imity image. If the other processes need the estimate in absoThe filtered offsets must also maintain a conservative estilute coordinates, they can simply add (step 260 ) the supplied
mate of hand position while the hand is floating above the
offsets to the default finger positions, but in many cases the

surface for optimal segmentation and identification as the

relative offset representation is actually more convenient.

It should be clear to those skilled in the art that many
hand touches back down. If a band lifts of the surface in the
middle of a complex sequence of operations and must, so improvements can be made to the above hand position estimation procedure which,-Lwell within the scope ofthis
quickly touch down again, it will probably touch down close
invention, especially inthe.........- ofguessing the position of
to where it lifted off. However, ifthe operation sequence has
lifted hands. One improvement is to make the estimated hand
ended, the hand is likely to eventually return to the neutral
offsets decay toward zero at a constant speed when a hand is
posture, or default position, to rest. Therefore, while a hand is
nottouching the surface, Hoa[n] is made small enoughthat the 65 lifted rather than decay exponentially. Also, the offset computations for each hand have been independent as described
estimated offsets gradually decay to zero at about the same
so far. It is actually advantageous to impose a
rate as a hand lazily returns to default position.
horizontal separation between the estimated left hand posiWhen Hoa[n] is made small due to low identification contion and estimated right hand position such that when a hand
fidence, the filter tracking delay becomes large enough to lag
such as the right hand slides to the opposite side of the board
while the other hand is lifted, the estimated position of the
behind a pair of quickly moving fingers by several centimeters. The purpose ofthe filter is to react slowly to questionable
other hand is displaced. In this case the estimated position of
the lifted left hand wouldbe forced from default to the far left
changes in contact identity, not to smooth contact motion.
ofthe surface, possiblyoffthe surface completely. Ifthe right
This motion tracking delay can be safely eliminated by add-

ing the contact motion measured between images to the old as handis lifted andthe lefI is not, an equationlike the following
canbeappliedtoforcetheestimatedrightbandpositionoutof
offset estimate. Step 257 obtains motion from the average,

(H

[n],H,,,[n]) of the current contact velocities:

the way:

APLNDC00030388

US 7,812,828 B2
23
Rh.[n]:=min(RH.[n],(LF1¿,p-RF1¿,p)+Lh.[n]+
minjurd_sep)

24
the strict segmentation region 282, where proximity saddle
(11)

points must serve as contact boundaries. As a preferred

where (LF14-RF14) is the default separation between

left and right thumbs, is theminimum horizontal separationto
be imposed, andI H_[n]isthecurrentestimatedoffsetofthe
left hand.
FIG. 18 represents the data flow within the proximity
image segmentation process 241. Step 262 makes a spatially
smoothed copy 263 of the current proximity image 240 by
passing a two-dimensional diffusion operator or Gaussian
kernel over it. Step 264 searches the smoothed image 263 for
local
° um pixels 265 whose filtered proximity exceeds
a significance threshold and exceeds the filtered proximities
ofnearest neighborpixels. The smoothing reduces the chance
that an isolated noise spike on a single electrode will result in
a local --- ---------which exceeds the significance threshold,
and consolidates local
° to about one per distinguishable fleshy contact.
Process 268 then constructs a group of electrodes or pixels
which register significant proximity around each local maximum pixel by searching outward from each local
for contact edges. Each electrode encountered before reaching a contact boundary is added to the local maximum's
group. FIG. 19 shows the basic boundary electrode search
pattern for an example contact boundary 274.Inthis diagram,
an electrode or image pixel lies at the tip of each arrow. The

s

10

15

20

embodiment the sloppy regions are rectangular, their inner
boundaries 285 are placed just inside of the columns where
the index fingers 202 are expected to lie, and the upperboundaries 287 are placed at the estimated vertical levels of their
respective thumbs 201. The outerand lowerboundaries ofthe
sloppy regions are determined by the outside edges of the
surface.Duetothedecayinestimatedhandolfsets afterhands
leave the surface, the sloppy segmentation regions return to
thepositionsshownafterthehandshavestayedoffthesurface
a few seconds, regardless ofhandposition at liftoff. FIG. 20B
shows how the sloppy regions follow the estimated hand
positions 252 as the right hand moves toward the upper left
and the left hand moves toward the lower left. This --that the palms and only the palms fall in the sloppy regions as
long as the hand position estimates are correct.
FIG. 20C shows that the left sloppy region 284 is moved
left offthe surface entirelywhenthe left hand is lifted offthe
surface and the right hand slides to the left side ofthe surface.
This prevents the fingers ofonehand from entering the sloppy
segmentation region of the opposite hand. This effect is
implemented by imposing a .L.l...- horizontal separation
between the sloppy regions and, should the regions get too

25 close to one another, letting the hand with the most surface
contacts override the estimated position of the hand with
fewer contacts. FIG. 21 is a detailed flow chart of the edge
search starts at the local maximum pixel 276, proceeds to the
tests which are applied at each searched electrode depending
left pixels 277 until the boundary 274 is detected. The last
on whether the electrode is in a strict or sloppy segmentation
pixel before the boundary 278 is marked as an edge pixel, and 30 region. Decision diamond 290 checks whether the
the search resumes to the right 279 of the local maximum
unsmoothed proximity of the electrode is greater than the
pixel 276. Once the left and right edges of the local maxibackground proximity levels. If not, the electrode is labeled
mum's row have been found, the search -- to the rows
an edge electrode in step 304 regardless of the segmentation
above and below, always starting 281 in the column of the
region or search direction, and in step 305 the search returns
to recurse in another direction. If the
pixel in the previous row whichhadthe greatestproximity.As 35 to the row
the example illustrates, the resulting set of pixels or elecunsmoothed proximity is significant farther tests are applied
trodes is connected in the mathematical sense but need not be
to the smoothedproximity ofneighboring electrodes dependrectangular. This allows groups to closely fit the typical ovaling on whether decision diamond 292 decides the search
shape of flesh contacts without leaving electrodes out or
electrode is in a sloppy or strict region.
including those from adjacent contacts.
40 If a strict region search is advancing horizontally within a
If contacts were small and always well separated, edges
row, decision diamond 306 passes to decision diamond 308
whichtests whetherthe electrode lies in a horimntal or diagocould simply be established wherever proximity readings fell
nal partial minimum with respect to its nearest neighborelecto the background level. But sometimes fmgertips are only
trodes. If so, a proximity valley between adjacent fingers has
separated by a slight valley or shallow saddle point 210. To
segment adjacent fingertips the partial
of these val- 45 probably been detected, the electrode is labeled as an edge
314 and search
in other directions 305. If not, the
leys must be detected and used as group boundaries. Large
seamh continues on the next electrode in the row 302. If a
palm heel contacts, on the other hand, may exhibit partial
strict region search is advancing vertically to the next row,
minima due to minor nonuniformities in flesh proximity
decision diamond 306 passes to decision diamond 310 which
across the contact. Ifall electrodes under the contact are to be
collected in a single group, such partial
must be so tests whether the electrode lies in a vertical partial minimum
withrespectto the smoothedpmximity ofits nearestneighbor
ignored. Given a hand position estimate the segmentation
electrodes. If so, a proximity valley between a finger and the
system can apply strict edge detection rules in regions of the
thumb has probably been detected, the electrode is labeled as
image where fingertips and thumb are expected to appearbut
anedge312 and searchresumesinotherdirections 305.Ifnot,
apply sloppy edge detection rules in regions of the image
where palms are expected to, appean This ensures that adja- ss the search continues into the next row 302. If decision diamond 294 determinesthat a sloppy region search is advancing
cent fingertips are notjoined into a single group and that each
horizontallywithin a row, stringenthorizontal minimum tests
palm heel is not broken into multiple groups.
are performed to check for the crease or proximity valley
Step 266 of FIG.18 defines the positions ofthese segmenbetween the inner and outer palm heels. To qualify, the electation regions using the hand position estimates 252 derived
from analyses ofprevious images. FIG. 20A shows the extent 60 trode must be more than about 2 cm horizontal distance from
the originating local maximum, as checked by decision diaofthe strict and sloppy segmentation regions while the hands
mond 296. Also the electrode must be part of a tall valley or
are in their default positions, making estimated offsets for
partial horizontal i i
which extends to the rows above
both hands zero. Plus signs in the diagram 252 indicate the
and below and the next-nearest neighbors within the row, as
estimated position ofeach finger and palm heel in each hand.
Rectangular outlines in the lower -,-- represent the left 65 checked by decision diamond 298. If so, the electrode is
labeled as an edge 300 and search recurses in other directions
284 and right 286 sloppy segmentation regions where partial
305. All other partial mint== within the sloppy regions are
22- are largely ignored. The T-shaped region remaining is

APLNDC00030389

US 7,812,828 B2
25

26

ignored, so the search continues 302 until a background level
edge is reached on an upcoming electrode.

o, = 2 e,

In sloppy segmentation regions it is possible for groups to
overlap significantly because partial i
between local 5

(12)

réGg

exex
(13)
maxima do not act as boundaries. Typically when this happens the overlapping groups are part of a large fleshy contact
such as a palm which, even after smoothing, has multiple
G, =
(14)
local
. Two groups are defined to be overlappingifthe 10
EEÜE
search originating local
electrode of one group is
also an element of the other group. In the interest ofpresenting only one group per distinguishable fleshy contact to the
Note that since the total group proximity G, integrates
rest ofthe system, step 270 of FIG. 18 combines overlapping
proximity over each pixel in the group, it depends upon both
ofthe size of a hand part, since large hand parts tend to cause
groups into single supergroups before parameter extraction.
Those skilled in the art will realize that feedback from high- 15 groups with more pixels, and of the proximity to or pressure
on the surface of a hand part.
level analysis of previous images can be applied in various
Since most groups are ---, their shape is well approxialternativeways to improve the seginentationprocess and still
mated by ellipse parameters. The ellipse fitting procedure
lie well within the scope of this invention. For example,
requires a unitary transformation of the group --i-additional image smoothing in sloppy segmentation regions 20 matrix G,,, of second moments L, g, G,:

could consolidate each palm heel contact into a single local

ma °
which would pass strict segmentation region
boundary tests. Care must be taken with this approach however, because too much smoothing can cause finger pairs
which unexpectedly enter sloppy palm regions to be joined
into one group. Once a finger pair is joined the finger identification process 248 bas no way to tell that the fingertips are
actually not a single palm heel, so the finger identification
process will be unable to correct the hand position estimate or
adjust the sloppy regions for proper segmentation of future
unages.
More detailed forms of feedback than the hand position
estimate can be utilized as well. For example, the proximal
phalanges(209 in FIG. 13) are actually part of the fmger but
tend to be segmented into separate groups than the fingertips
by the vertical minimum test 310. The vertical minimum test
is necessary to separate the thumb group from index fmgertip
group in the partially closed FIG. 14 and pen grip FIG. 15
hand configurations. However, the proximal phalanges of
flattened fingers can be distinguished from a thumb behind a
curled fingertip by the fact that it is very difficult to flatten one
long finger without flattening the other long fingers. To take,
advantage of this constraint, a flattened finger flag 267 is set
whenever two or more of the contacts identified as index
through pinky in previous images are larger than normal,
reliably indicating that fmgertips are flattening. Then decision
diamond 310 is modified during processing of the current
image to ignore the first vertical =*ni==== encountered during search of rows below the originating local minimum 276.
This allows the proximal phalanges to be included in the
fingertip group but prevents fingertip groups from merging
with thumbs or forepalms. The last step 272 of the segmen-

G, G,,
G.,=

25

(15)

G, G,

30

©

The eigenvalues & and 4 of the covariance matrix G,
determine the ellipse axis lengths and orientation Ga.

Ge =

Ao - G.

(21)

G,,

45

where Ge is uniquely wrapped into the range (0,180°).
For convenience while distinguishing fmgertips from
palms at higher system levels, the major and minor axis
so lengths are converted via their ratio into an eccentricity GE

tation process is to extract shape, size, and position param- 55

eters from each electrode group. Group position reflects hand
contact position and is necessary to determine fmger velocity.

Note that since the major axis length is always greater than

or equal to the minor axis length, the eccentricity will always
The total group proximity, eccentricity, and orientation are
be greater than or equal to one. Finally, the total group proxusedby higher level modules to help distinguish fmger, palm, æ imity is empirically renormalized so that the typical curled
and thumb contacts.
fingertip will have a total proximity around one:
Provided GE iS ÍÏle set of electrodes in group G, e, is tlie
unsmoothedproximity ofan electrode orpixel e, ande, and e,

are the coordinates on the surface of the electrode center in
centimeters, to give a basic indicator of group position, the es

G,

(23)

proximity-weighted center, or centroid, is computed from

positions and proximities of the group's electrodes:

r

rielasi ha, I IODTt3 fram the DIRA imana a un ---a an O&I98/9011

APLNDC00030390

US 7,812,828 B2
27

28

On low resolution electrode arrays, the total group proximity G, is a more reliable indicator ofcontact size as well as
finger pressurethan the fitted ellipse parameters. Therefore, if
proximity images have low resolution, the orientation and
eccentricity of small contacts are set to default values rather
than their measured values, and total group proximity G, is
used as the primary measure of contact size instead ofmajor
and minor axis lengths.
FIG. 22 shows the steps ofthe path tracking process, which
chains together those groups from successive proximity
images which correspond to the same physical hand contact.
To determine where each hand part has moved since the last
proximity image, the tracking process must decide which
current groups should be matched with which existing contact paths. As a general rule, a group and path arising from the
same contact will be closerto one anotherthanto othergroups
and paths. Also, biomechanical constraints on lateral fmger
velocity and acceleration limit how far a finger can travel
between images. Therefore a group and path should not be
matched unless they are within a distance known as the tracking radius of one another. Since the typical lateral separation
between fingers is greaterthan the tracking radius forreasonable image scan rates touchdown and liftoff are easily
detected by the fact that touchdown usually causes a new
group to appear outside the tracking radii of existing paths,
and liftoffwill leave an active path without a group within its
tracking radius. To prevent improperbreaking ofpaths at high
finger speeds each path's tracking radius Paa can be made
dependent on its existing speed and proximity.
The first step 320 predicts the current locations of surface
contacts along existing trajectories using path positions and
velocities measured from p
images. Applying previous velocity to the location prediction improves the prediction except when a finger suddenly starts or stops or changes
direction. Since such high accelerationevents occur less often
than zero acceleration events, the benefits of velocity-based
prediction outweigh the potentially bad predictions during
finger acceleration. Letting P,[n-1],P,[n-1] be the position
of path P from time step n-1 and PJn-1]. P,[n-1] the last
known velocity, the velocity-predicted path continuation is
then:

between them is less than the tracking radius. All of the
following conditions must hold:
oks.,,,,PI
5

(31)

PI

(32)

,,gk

(33)

To aid in detection of repetitive taps of the same finger, it

may be useful to preserve continuity of path assignment
10 between taps over the same location. This is accomplished in
step Via - = = EFS 334 by repeating steps 322-326 using
only groups which were left unpaired above and paths which
were deactivated within the last second or so due to finger
liftoff.
15
In step 336, any group whichhas still not be paired with an
active or recently deactivated path is allocated a new path,
representing touchdown of a new finger onto the surface. In
step 344, any active path which cannot be so paired with a

group is deactivated, representing hand part liftoff from the
20 SUrface.

Step 346 incorporates the extracted parameters of each
group into its assigned path via standard filtering techniques.
The equations shown below apply simple autoregressive filters to update the path position (P,[n],P,[n],P,[n]), velocity
25 g,[n],P,[n]), and shape (Pe[n], P,[n]) parameters from corresponding group parameters, but Kalman or finite impulse
response filters would also be appropriate.
Ifa path P has just been started by group G at time step n,

i.e., a hand part has just touched down, its parameters are
30 initialized as follows:
PJulm,
y,[n]=o,

(35)

PágG

(30

P,[n]<

(39)

w[n)=O

35

(34)

(40)

40

P,a[n]=PA-1]+stP.[n-1]

(24)

P,4[n]=P,[n-1]+AtP,,[n-1]

(25) 45

Letting the set ofpaths active in the previous image be PA,
and let the set electrode groups constructed in the current
image be G, step 322 finds for each group Gk the closest
active path and records the distance to it:

P,[n]=G/At

(41)

else ifgroup G is a continuation ofactive path P[n-1] to time
step n:
PËI=G.0,+(1-G)(P,gn-1])
(42)

mm

90 '°

P,[n]=G.a,+(1-G.XPy[n-1])

(43)

Gk closestPdist 2-min Pl PA d 2(Gk,PI) Gk G

(27)

22[n]=GaGr+(1-G.XPy[n-1])

(44)

where the squared Euclidean distance is an easily computed gy

Pe[nf=G.Ge+(1-G.XPe[n-1])

(45)

distance metric:

p¿nj=o.oE

(46)

a2(Gk,Pl)=(Gk,-PI

)24Gg-PI

)2

28)

a)(Pgn-1])

PJn]=(Pjn)-P¿n-1]yAt

(47)

Pgn]=(P,[n]-P,[n-1]yAt

(48)

P,[n]=(P/n]-P,{n-1]yAt

(49)

Step 324 then finds for each active path Pl, the closest

active group and records the distance to it:
9 P1 closestG-arg min Gk Gd 2(Gk,PI) Pl PA
Pl closestGdist 2=min Gk Gd 2(Gk,P1) Pl PA

60
(29)
(30)

It is also useful to compute the P.). Since thŠHabilityof
and angle
P,from the velocity vector (P. magnitude P

In step 326, an active group Gk and path Pl are only paired 65 position measurements Lconsiderably with total
with one another if they are closest to one another, i.e.,
proximity P,, the low-pass filter pole Geis decreased for
Gk
- and Pletosesto refer to one another, and the distance
groups with total proximities lower than normal. Thus when

Conv Drovided bv USPTO from the PIRS Image Database on 04/25/2011

APLNDC00030391

US 7,812,828 B2
29

30

hand's estimated position offset. The final attractor positions
signals are weak, the system relies heavily on the previously
established path velocity, but when the finger firmly touches
(Aj,[n],Aj,[n]) are therefore given by:
the surface causing a strong, reliable signal, the system relies
AÀxh]=H.RJ+Fja,p
(50)
entirely on the current group centroid measurement.
The next process within the tracking module is contact 5
AÍ,h]=H,,,þJ+Fjg
(51)
identification. On surfaces large enough for multiple hands,
In alternative embodiments the attractor ring can also be
the contacts of each hand tend to form a circular cluster, and
the clusters tendto.._ _ separatebecauseusers like to avoid

mtated or scaled by estimates ofhand rotation and size such

Alternative embodiments can include additional attractors

approaches the default value of 1 at 0°, 90°, and 180° where

as the estimated finger offsets, but care must be taken that
entangling the fingers of opposite hands. Because the
arrangement offingers within a band clusteris independentof 10 wrong finger offset estimates and identification errors do not
reinforce one another by severely warping the attractor ring.
the location of and arrangement within the other hand's clusOnce the attractor template is in place, step 354 constructs
ter, the contact identification system is hierarchically split.
a square matrix [dy] ofthe distances in the surface plane from
The hand identification process 247 first decides to which
each active contact path Pi to each attractor point Aj. If there
cluster each contact belongs. Then a within-cluster identification process 248 analyzes for each hand the arrangement of 15 are fewer surface contacts than attractors, the null path PO,
which has zero distance to each attractor, takes place of the
contacts within the hand's cluster, independent of the other
missing contacts. Thoughanydistance metric can be used, the
hand's cluster. Because within-clusteror finger identification
squared Euclidean distance,
works the same for each hand regardless ofhow many hands
dy¯(4.Al-PGA1)2+(Aj,[n]-Pi,[n])
(52)
can fit on the surface, it will be described first. The description
below is for identification within the right hand. Mirror sym- 20
is preferred because it specially favors assignments wherein
metry must be applied to some parameters before identifying
the angle between any pair of contacts is close to the angle
left hand contacts.
betweenthe pair ofattractors assigned to those contacts. This
FIG. 23 shows the preferred embodiment of the finger
corresponds to the biomechanical constraint that fingertips
identification process 248. For the contacts assigned to each
hand this embodiment attempts to match contacts to a tem- 25 avoid crossing over one another, especially while touching a
surface.
plate ofhand part attractor points, each attractorpoint having
In step 356, the distances from each contact to selected
an identity which corresponds to a particular finger or palm
attractors are weighted according to whether the geometrical
heel. This matching between contact paths and attractors
features of the given contact match those expected from the
should be basically one to one but in the case that some hand
parts are not touching the surface, some attractors will be left 30 hand part that the attractor represents. Since the thumb and
palm heels exhibit the most distinguishing geometrical feaunfilled, i.e., assigned to the null path or dummy paths.
tures, weighting functions are computed for the thumb and
Step 350 initializes the locations of the attractor points to
palm heel attractors, and distances to fingertip attractors are
the app-ite positions of the corresponding fingers and
unchanged. In a preferredembodiment, each weighting funcpalms when the hand is in a neutral posture with fingers
partially curled. Preferably these are the same default finger 35 tion is composed ofseveral factorversus feature relationships
such as those plotted approximatelyin FIG. 25. Each factor is
locations (Fig,Fig) employed in hand offset estimation.
designed to take on a default value of I when its feature
Setting the distances and angles between attractorpoints from
measurementprovides no distinguishinginformation, take on
a half-closed hand posture allows the matching algorithm to
larger values if the measured contact feature uniquely
perform well for a wide variety of finger flexions and extensions.
40 resembles the given thumb or palm hand part, and take on
smallervalues ifthe measuredfeature is Lw stent with the
The resulting attractor points tend to lie in a ring as disgiven attractor's hand part. The factor relationships can be
played by the cosses in FIG. 24. The identities of attractor
variously stored and computed as lookup tables, piecewise
points 371-377 correspond to the identities of hand parts
linear functions, polynomials, trigonometric functions, ratio201-207. If the given hand is a left hand, the attractor ring
must be mirrored about the vertical axis from that shown. 45 nal functions, or any combination ofthese. Since assignment
between a contact and an attractor whose features match is
FIG. 24 also includes line segments 380 forming theVoronoi
favored as the weighted distance between becomes smaller,
cell around each attractor point. Every point within an attracthe distances are actually weighted (multiplied) with the
tor's Voronoi cell is closer to that attractor than any other
reciprocals of the factor relationships shown.
attractor. When there is only one contact in the cluster and its
features are not distinguishing, the assignment algorithm so
FIG. 25A shows the right thumb and right inner palm heel
orientation factor versus orientation of a contact's fitted
effectively assigns the contact to the attractor point of the
ellipse. Orientationofthesehandparts tends to be about 120°,
Voronoi cell which the contact lies within. When there are
whereas fingertip and outer palm heel contacts are usually
multiple surface contacts in a hand cluster, they couldall liein
very close to vertical (90°), and orientation ofthe left thumb
the same Voronoi cell, so the assignment algorithm must
perform a global optimization which takes into account all of ss and left inner palm heel averages 60°. The right orientation
the contact positions at once.
factor therefore approaches a ----- -------- at 120°. It

orientation is inconclusive of identity, and reaches a minifor other hand part or alternative attractor arrangements for
mum at 60°, the favored orientation ofthe opposite thumb or
atypical hand configurations. For example, attractorsfor forepalm contacts can be placed at the center ofthe ring, but since 60 palm heel. The corresponding relationship for the left thumb
the forepalms typicallydo not touch the surface unless therest
and inner palm heel orientation factor is flipped about 90°.
FIG. 25B approximately plots the thumb size factor. Since
of the hand is flattened onto the surface as well, forepalm
attractors should be weighted such that contacts are assigned

thumb sizeas indicatedby total proximity tends to peak at two

to them only when no regular attractors are left unassigned.
or three times the size of the typical curled fingertip, the
For optimal matching accuracy the ring should be kept 65 thumb size factor peaks at these sizes. Unlike palm heels,
roughly centered on the hand cluster. Therefore step 352
thumb contacts can not be muchlargerthan two or three times
translates all of the attractor points for a given hand by the
thedefault fingertip size, so the thumb factor drops back down

Copy provided by USPTO from the PIRS Image Database on 04/25/2011

APLNDC00030392

US 7,812,828 B2
31

32

for larger sizes. Since any hand part can appear small when

ized combinatorial search, the Hungarian method, or network
flow solvers. Those skilled in the art will recognize that this
type ofcombinatorial optimizationproblem has a mathematically equivalentdual representation inwhich the optimization

touching the surface very lightly or just starting to touchdown, small size is not distinguishing, so the size factor
defaults to 1 for very small contacts.

FIG. 25C approximatelyplots the palm heel size factor. As 5 is reformulated as a maximization of a sum of dual param-

eters. Such reformulation of the above hand part identificamore pressure is applied to the palms, the palm heel contacts
tion method as the dual ofattractor-contact distance
can grow quite large, remaining fairly round as they do so.
zation remains well within the scope of this invention.
Thus the palm heel size factor is much like the thumb size
factor except the palm factor is free to L..._ indefmitely.
To avoid -----sary computation, decision diamond 360
However, fingertip contacts can grow by becoming taller as 10 ends the fmger identification process at this stage if the hand
assignment of the given contact cluster is only a tentative
the fingers are flattened. But since fmgerwidth is constant, the
eccentricity of an ellipse fitted to a growing fmgertip contact
hypothesis being evaluated bythe hand identification module
1..._.. in proportion to the height. To prevent flattened
247. However, if the given hand assignments are the fmal
preferred hypothesis, further processes verify finger identifingers from having a large palm factor, has little effect for
palms, whose eccentricity
° near 1, but cancels the is ties and compile identity statistics such as finger counts.
highproximities offlattened fingertips. Thoughdirectlyusing
The identifications produced by this attractor assignment
fitted ellipse width would be less accurate for low resolution
method are highly reliable when all five fingers are touching
electrode arrays, the above ratio basically captures contact
the surface or when thumb and palm features are unambiguwidth.
ous. Checking that the horizontal coordinates for identified
Another important distinguishingfeature ofthe palm heels 20 fingertip contacts are m mcreasmg order easily verifies that
is that wrist anatomy keeps the centroids of their contacts
fingertip identities are not __..sly swapped. However,

when-only two to four fmgers are touching, yet no finger
strongly exhibits thumb size or orientation features, the
assignment ofthe
st finger contact may wronglyindiflexible joints. The inter-palm separation feature is measured 25 cate whether the contact is the thumb. In this case, decision
by searching for the nearest neighbor contact ofa given condiamond 362 employs a thumb verification process 368 to
separated from one other and from the fingers by several

centimeters. This is not true of the thumb and fingertips,
which can be moved within a centimeter of one another via

tact and measuring the distance to the neighbor. As plotted

take furthermeasurements betweentheinnermost finger con-

tact and the other fingers. If these further measurements
approximately in FIG. 25D, the palm separation factor
quickly decreases as the separation between the contact and
strongly suggest the innermost finger contact identity is
its nearest neighbor falls below a few centimeters, indicating 30 wrong, the thumb verification process changes the assignment ofthe innermost fmger contact. Once the finger assignthat the given contact (and its nearest neighbor) are not palm
heels. Unlike the size and orientation factors which only

ments are verified, step 364 compiles statistics about the

become reliable as the weight of the hands fully compresses

assignments withineachhand suchas the number oftouching

the palms, the palm separation factor is especially helpful in

fingertips and bitfields of touching finger identities. These

distinguishing the palm heels from pairs ofadjacent fingertips 35 statistics provide convenient summaries of identification
because it applies equally well to light, small contacts.
results for other modules.
Once the thumb and palm weightings have been applied to
FIG. 26 shows the steps within the thumb verification
module. The first 400 is to compute several velocity, separathe distance matrix, step 358 finds the one-to-one assignment
between attractors and contacts which minimizes the sum of
tion, and angle factors for the °
'st contact identified as
weighted; distances between each attractor and it's assigned 4° a finger relative to the other contacts identified as fingers.
contact. For notational purposes, let a new matrix [cy] hold
Since these inter-path measurements presuppose a contact
the weighted distances:
identity ordering, they could not have easily been included as
attractor distance weightings because contact identities are
not known until the attractor distance minimization is comdy/(Pim.ne_sirefactPixiempt) if j=1
(53) 45 plete. For the factor descriptions below, let FI be the innermost finger contact, FN be the next
st finger contact,
du
if25js5
cg=

FO be the outermost finger contact.

du/(Pimon_siw>aPipappa) if j=6
du / (Pimen_sizejaPimam_seppa) if Ì = 7
50

inner separationfactorinner_separation_fact is definedas the
ratio of the distance between the ......... st and next inner-

Mathematically the optimization can then be stated as finding
the permutation {ni, . . . , x,} of integer hand part identities

{1, . . . , 7} which
7

The separation between thumb and index finger is often
larger than the separations between fingertips, but all separationstendtogrowasthefingersareoutstretched.Thereforean
most finger contacts to the average of the distances between

55

other adjacent fingertip contacts, avg_separation: 12
innerseparationfact min

(54)

c;

FI - FNJ2 + (FI - FN)2

60

umerseparationfacta mit 1,

(55)

avgseparation

where ey is the weighted distance from contact i to attractorj,

and contact i and attractor j are considered assigned to one
The factor is clipped to be greater than one since an inneranotherwhennpj. This combinatorial optimizationproblem,
most separation less than the average can occur regardless of
known more specifically in mathematics as an assignment 65 whether thumb or index fmger is the innermost touching
problem, can be efficiently solved by a variety ofwell-known

finger. In case there are only two finger contacts, a default

mathematical techniques, such as branch and bound, local-

average separation of 2-3 cm is used. The factor tends to

Copy provided by USPTO from the PIRS Image Database on 04/25/2011

APLNDC00030393