# US 2014/0198076 A1 · Multi-dimensional multi-finger search using oversampling hill climbing and descent with range > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2014/0198076 A1 - Document ID: US20140198076A1 - Status: Published application - Kind: A1 - Application number: 14/156,087 - Filed: 2014-01-15 - Published: 2014-07-17 - Earliest claimed: 2013-01-15 - Assignees: Cirque Corporation - Applicants: Cirque Corporation - Inventors: Michael D. Layton - Web page: https://patentgrep.com/patent/US20140198076A1 ## CPC - G06F 3/04166: {Details of scanning methods, e.g. sampling time, grouping of sub areas or time sharing with display driving (Synchronisation with the driving of the display or the backlighting unit to avoid interferences generated internally G06F3/04184)} - G06F 2203/04104: Multi-touch detection in digitiser, i.e. details about the simultaneous detection of a plurality of touching locations, e.g. multiple fingers or pen and finger - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A method for detecting and tracking multiple fingers in a two dimensional set of results using oversampling hill climbing and descent with range. ## Claims ### Claim 1 A method for detecting and tracking multiple objects using a two dimensional set of measurements from a touch sensor, said method comprising: 1) scanning a two dimensional array of locations to identify a first finger location having a result which is greater than zero such that it indicates the presence of at least one finger; 2) performing a hill climbing procedure to determine if there is a location immediately adjacent to the first finger location that has a higher value; 3) repeating the hill climbing procedure until the highest first finger location is found; and 4) performing a hill descending algorithm to identify a boundary between the first finger location and a second finger. ### Claim 2 (depends on 1) The method as defined in claim 1 wherein the method further comprises oversampling the two dimensional array of locations when scanning to thereby make certain that at least one adjacent location to the first finger location also has a result to thereby confirm the presence of at least one finger. ### Claim 3 (depends on 1) The method as defined in claim 1 wherein the hill climbing procedure further comprises bypassing local minima caused by aliasing in order to find the first finger location with the highest value to create a new current first finger location. ### Claim 4 (depends on 3) The method as defined in claim 3 wherein the method of bypassing the local minima further comprises comparing a weighted sum of near cross axis results in order to determine the new current first finger location. ### Claim 5 (depends on 4) The method as defined in claim 4 wherein the hill climbing algorithm further comprises performing a 4-connected comparison of the four closest locations in order to determine the new current first finger location. ### Claim 6 (depends on 5) The method as defined in claim 5 wherein comparing a weighted sum of near cross axis results further comprises creating separate filtered data arrays for each climbing direction around the current first finger location. ### Claim 7 (depends on 6) The method as defined in claim 6 wherein the weighted sum further comprises applying a weighted pattern that gives more weight to some locations and less weight to other locations. ### Claim 8 (depends on 6) The method as defined in claim 6 wherein the hill climbing algorithm further comprises: 1) locating a repeating loop around an actual location of a finger that causes the hill climbing procedure to not identify a location with a maximum result; and 2) terminating the repeating loop when the hill climbing procedure repeats a location in a current measurement cycle. ### Claim 9 (depends on 6) The method as defined in claim 6 wherein the hill climbing algorithm further comprises: 1) locating a repeating loop around an actual location of a finger that causes the hill climbing procedure to not identify a location with a maximum result; and 2) terminating the repeating loop when the hill climbing procedure has moved the current first finger location N times. ### Claim 10 (depends on 1) The method as defined in claim 1 wherein the hill descending algorithm further comprises including a range of results which are then considered to be part of the same finger. ### Claim 11 (depends on 10) The method as defined in claim 10 wherein the hill descending algorithm further comprises identifying a boundary with an adjacent finger by comparison of adjacent results, with range. ### Claim 12 (depends on 11) The method as defined in claim 11 wherein the method further comprises repeating steps 1 through 4 while excluding any fingers that are already identified. ### Claim 13 A method for detecting and tracking a single object using a two dimensional set of measurements from a touch sensor, said method comprising: 1) scanning a two dimensional array of locations to identify a finger location having a result which is greater than zero such that it indicates the presence of the finger; 2) performing a hill climbing procedure to determine if there is a location immediately adjacent to the finger location that has a higher value; and 3) repeating the hill climbing procedure until the highest finger location is found. ### Claim 14 (depends on 13) The method as defined in claim 13 wherein the method further comprises oversampling the two dimensional array of locations when scanning to thereby make certain that at least one adjacent location to the finger location also has a result to thereby confirm the presence of the finger. ### Claim 15 (depends on 13) The method as defined in claim 13 wherein the hill climbing procedure further comprises bypassing local minima caused by aliasing in order to find the finger location with the highest value to create a new finger location. ### Claim 16 (depends on 15) The method as defined in claim 15 wherein the method of bypassing the local minima further comprises comparing a weighted sum of near cross axis results in order to determine the new current finger location. ### Claim 17 (depends on 16) The method as defined in claim 16 wherein the hill climbing algorithm further comprises performing a 4-connected comparison of the four closest locations in order to determine the new current finger location. ### Claim 18 (depends on 17) The method as defined in claim 17 wherein comparing a weighted sum of near cross axis results further comprises creating separate filtered data arrays for each climbing direction around the current finger location. ### Claim 19 (depends on 18) The method as defined in claim 18 wherein the weighted sum further comprises applying a weighted pattern that gives more weight to some locations and less weight to other locations. ### Claim 20 (depends on 18) The method as defined in claim 18 wherein the hill climbing algorithm further comprises: 1) locating a repeating loop around an actual location of a finger that causes the hill climbing procedure to not identify a location with a maximum result; and 3) terminating the repeating loop when the hill climbing procedure repeats a location in a current measurement cycle. ### Claim 21 (depends on 18) The method as defined in claim 18 wherein the hill climbing algorithm further comprises: 1) locating a repeating loop around an actual location of a finger that causes the hill climbing procedure to not identify a location with a maximum result; and 2) terminating the repeating loop when the hill climbing procedure has moved the current finger location N times. ### Claim 22 (depends on 13) The method as defined in claim 13 wherein the hill descending algorithm further comprises including a range of results which are then considered to be part of the finger.