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).

Download PDF
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., 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

Disclaimer: Justia Dockets & Filings provides public litigation records from the federal appellate and district courts. These filings and docket sheets should not be considered findings of fact or liability, nor do they necessarily reflect the view of Justia.

Why Is My Information Online?