Bottom up watershed dataflow method and region-specific segmentation based on historic data

• US 20080309629A1
• Filed: 06/13/2007
• Published: 12/18/2008
• Est. Priority Date: 06/13/2007
• Status: Active Grant

• Current Assignee: Apple Inc.
• Original Assignee: Apple Inc.
• Inventors: Strickon, Joshua, Westerman, Wayne Carl
• Granted Patent: US 7,916,126 B2
• Time in Patent Office: Days
• US Class Current: 345/173
• CPC Class Codes: G06F 3/038 Control and interface arrangements therefor, e.g. drivers or device-embedded control circuitry
• CPC Class Codes: 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
• CPC Class Codes: G06F 3/0488 using a touch-screen or digitiser, e.g. input of commands through traced gestures
• CPC Class Codes: G06T 7/11 Region-based segmentation
• CPC Class Codes: G06T 7/155 involving morphological operators

Abstract

The application of a watershed algorithm to pixels and their touch values obtained from a scan of a touch sensor panel to determine patches corresponding to images of touch is disclosed. Prior to applying the watershed algorithm, background pixels having little or no touch values can be eliminated. A primary merge algorithm can then merge adjacent patches together when the saddle point between them is shallow as compared to the peak represented by the patches. However, if two candidate patches for merging have a total number of pixels below a certain threshold, these two patches may not be merged under the assumption that the patches might have been caused by different fingertips. Conversely, if two candidate patches for merging have a total number of pixels above a certain threshold, these two patches can be merged under the assumption that the patches were caused by a single thumb or palm.

Claims

1. A method for identifying and processing patches indicative of touch events from a plurality of pixels having touch values captured during a scan of a touch sensor panel, comprising:

eliminating pixels having touch values indicative of no touch events prior to performing a watershed algorithm; and

performing the watershed algorithm on non-eliminated pixels to identify the patches, wherein the watershed algorithm traces paths of unlabeled pixels of increasing touch values until a pixel labeled with a patch number is found, at which time all pixels in the path are labeled with the same patch number as the labeled pixel, or a peak is found, at which time the peak is assigned a unique patch number and all pixels in the path are labeled with the unique patch number.

2. The method of claim 1, further comprising deleting those identified patches whose pixels are substantially linear, or patches that include a predetermined small number of pixels, prior to performing the watershed algorithm.

3. The method of claim 1, further comprising spatially smoothing the touch values of the pixels prior to performing the watershed algorithm.

4. The method of claim 1, further comprising performing a post-watershed merge of two patches having a saddle point between them that is shallow as compared to the peaks represented by the patches.

5. The method of claim 4, further comprising overruling the post-watershed merge if the two patches have a total number of pixels below a threshold.

6. The method of claim 1, further comprising performing a post-watershed merge of two patches if the two patches have a total number of pixels above a threshold.

7. The method of claim 1, further comprising performing a post-watershed merge of two patches if the two patches were part of a single large patch in a previous panel scan.

8. The method of claim 1, further comprising performing a post-watershed merge of a first larger patch and a second smaller patch if the second patch is located substantially directly below the first patch.

9. The method of claim 4, further comprising altering criteria to increase the likelihood of performing a post-watershed merge if a large object was expected to cause the touch events.

10. The method of claim 1, further comprising:

determining centroids for one or more of the patches;

estimating an orientation of a hand from locations of the centroids; and

performing a post-watershed merge of two patches if the centroids of the two patches are consistent with a single finger and the orientation of the hand.

11. The method of claim 1, further comprising computing a bounding box around a patch to assist in limiting a number of pixels to be considered in post-watershed processing of the patch.

12. The method of claim 1, further comprising computing a centroid for each patch located at an edge of the touch sensor panel and generated by a finger partially off the touch sensor panel by adding a phantom line of pixels outside the touch sensor panel to the computation of the centroid.

13. The method of claim 1, further comprising tracking the pixels in the paths formed during the performance of the watershed algorithm by storing only coordinates of the pixels in the paths.

14. A method for identifying and processing patches indicative of touch events from a plurality of pixels having touch values captured during a scan of a touch sensor panel, comprising:

performing a watershed algorithm to identify the patches, wherein the watershed algorithm traces paths of unlabeled pixels of increasing touch values until a pixel labeled with a patch number is found, at which time all pixels in the path are labeled with the same patch number as the labeled pixel, or a peak is found, at which time the peak is assigned a unique patch number and all pixels in the path are labeled with the unique patch number; and

performing a post-watershed merge of two patches having a saddle point between them that is shallow as compared to the peaks represented by the patches.

15. The method of claim 14, further comprising eliminating pixels having touch values indicative of no touch events prior to performing the watershed algorithm.

16. The method of claim 14, further comprising deleting those identified patches whose pixels are substantially linear, or patches that include a predetermined small number of pixels.

17. The method of claim 14, further comprising spatially smoothing the touch values of the pixels prior to performing the watershed algorithm.

18. The method of claim 14, further comprising overruling the post-watershed merge if the two patches have a total number of pixels below a threshold.

19. The method of claim 14, further comprising performing a post-watershed merge of two patches if the two patches have a total number of pixels above a threshold.

20. The method of claim 14, further comprising performing a post-watershed merge of two patches if the two patches were part of a single large patch in a previous panel scan.

21. The method of claim 14, further comprising performing a post-watershed merge of a first larger patch and a second smaller patch if the second patch is located substantially directly below the first patch.

22. The method of claim 14, further comprising altering criteria to increase the likelihood of performing a post-watershed merge if a large object was expected to cause the touch events.

23. The method of claim 14, further comprising:

determining centroids for one or more of the patches;

estimating an orientation of a hand from locations of the centroids; and

performing a post-watershed merge of two patches if the centroids of the two patches are consistent with a single finger and the orientation of the hand.

24. The method of claim 14, further comprising computing a bounding box around a patch to assist in limiting a number of pixels to be considered in post-watershed processing of the patch.

25. The method of claim 14, further comprising computing a centroid for each patch located at an edge of the touch sensor panel and generated by a finger partially off the touch sensor panel by adding a phantom line of pixels outside the touch sensor panel to the computation of the centroid.

26. A computer-readable medium comprising program code for identifying and processing patches indicative of touch events from a plurality of pixels having touch values captured during a scan of a touch sensor panel, the program code for causing performance of a method comprising:

eliminating pixels having touch values indicative of no touch events prior to performing a watershed algorithm; and

performing the watershed algorithm on non-eliminated pixels to identify the patches, wherein the watershed algorithm traces paths of unlabeled pixels of increasing touch values until a pixel labeled with a patch number is found, at which time all pixels in the path are labeled with the same patch number as the labeled pixel, or a peak is found, at which time the peak is assigned a unique patch number and all pixels in the path are labeled with the unique patch number.

27. The computer-readable medium of claim 26, the program code further for causing performance of a method comprising deleting those identified patches whose pixels are substantially linear, or patches that include a predetermined small number of pixels, prior to performing the watershed algorithm.

28. The computer-readable medium of claim 26, the program code further for causing performance of a method comprising spatially smoothing the touch values of the pixels prior to performing the watershed algorithm.

29. The computer-readable medium of claim 26, the program code further for causing performance of a method comprising performing a post-watershed merge of two patches having a saddle point between them that is shallow as compared to the peaks represented by the patches.

30. The computer-readable medium of claim 29, the program code further for causing performance of a method comprising overruling the post-watershed merge if the two patches have a total number of pixels below a threshold.

31. The computer-readable medium of claim 26, the program code further for causing performance of a method comprising performing a post-watershed merge of two patches if the two patches have a total number of pixels above a threshold.

32. The computer-readable medium of claim 26, the program code further for causing performance of a method comprising performing a post-watershed merge of two patches if the two patches were part of a single large patch in a previous panel scan.

33. The computer-readable medium of claim 26, the program code further for causing performance of a method comprising performing a post-watershed merge of a first larger patch and a second smaller patch if the second patch is located substantially directly below the first patch.

34. The computer-readable medium of claim 29, the program code further for causing performance of a method comprising altering criteria to increase the likelihood of performing a post-watershed merge if a large object was expected to cause the touch events.

35. The computer-readable medium of claim 26, the program code further for causing performance of a method comprising:

determining centroids for one or more of the patches;

estimating an orientation of a hand from locations of the centroids; and

performing a post-watershed merge of two patches if the centroids of the two patches are consistent with a single finger and the orientation of the hand.

36. The computer-readable medium of claim 26, the program code further for causing performance of a method comprising computing a bounding box around a patch to assist in limiting a number of pixels to be considered in post-watershed processing of the patch.

37. The computer-readable medium of claim 26, the program code further for causing performance of a method comprising computing a centroid for each patch located at an edge of the touch sensor panel and generated by a finger partially off the touch sensor panel by adding a phantom line of pixels outside the touch sensor panel to the computation of the centroid.

38. The computer-readable medium of claim 26, the program code further for causing performance of a method comprising tracking the pixels in the paths formed during the performance of the watershed algorithm by storing only coordinates of the pixels in the paths.

39. A computer-readable medium comprising program code for identifying and processing patches indicative of touch events from a plurality of pixels having touch values captured during a scan of a touch sensor panel, the program code for causing performance of a method comprising:

performing a watershed algorithm to identify the patches, wherein the watershed algorithm traces paths of unlabeled pixels of increasing touch values until a pixel labeled with a patch number is found, at which time all pixels in the path are labeled with the same patch number as the labeled pixel, or a peak is found, at which time the peak is assigned a unique patch number and all pixels in the path are labeled with the unique patch number; and

performing a post-watershed merge of two patches having a saddle point between them that is shallow as compared to the peaks represented by the patches.

40. The computer-readable medium of claim 39, the program code further for causing performance of a method comprising eliminating pixels having touch values indicative of no touch events prior to performing the watershed algorithm.

41. The computer-readable medium of claim 39, the program code further for causing performance of a method comprising deleting those identified patches whose pixels are substantially linear, or patches that include a predetermined small number of pixels.

42. The computer-readable medium of claim 39, the program code further for causing performance of a method comprising spatially smoothing the touch values of the pixels prior to performing the watershed algorithm.

43. The computer-readable medium of claim 39, the program code further for causing performance of a method comprising overruling the post-watershed merge if the two patches have a total number of pixels below a threshold.

44. The computer-readable medium of claim 39, the program code further for causing performance of a method comprising performing a post-watershed merge of two patches if the two patches have a total number of pixels above a threshold.

45. The computer-readable medium of claim 39, the program code further for causing performance of a method comprising performing a post-watershed merge of two patches if the two patches were part of a single large patch in a previous panel scan.

46. The computer-readable medium of claim 39, the program code further for causing performance of a method comprising performing a post-watershed merge of a first larger patch and a second smaller patch if the second patch is located substantially directly below the first patch.

47. The computer-readable medium of claim 39, the program code further for causing performance of a method comprising altering criteria to increase the likelihood of performing a post-watershed merge if a large object was expected to cause the touch events.

48. The computer-readable medium of claim 39, the program code further for causing performance of a method comprising:

determining centroids for one or more of the patches;

estimating an orientation of a hand from locations of the centroids; and

performing a post-watershed merge of two patches if the centroids of the two patches are consistent with a single finger and the orientation of the hand.

49. The computer-readable medium of claim 39, the program code further for causing performance of a method comprising computing a bounding box around a patch to assist in limiting a number of pixels to be considered in post-watershed processing of the patch.

50. The computer-readable medium of claim 39, the program code further for causing performance of a method comprising computing a centroid for each patch located at an edge of the touch sensor panel and generated by a finger partially off the touch sensor panel by adding a phantom line of pixels outside the touch sensor panel to the computation of the centroid.

51. A computing system comprising the computer-readable medium of claim 39.

52. A mobile telephone comprising the computing system of claim 51.

53. A digital audio player comprising the computing system of claim 51.

54. A mobile telephone including a computer-readable medium comprising program code for identifying and processing patches indicative of touch events from a plurality of pixels having touch values captured during a scan of a touch sensor panel, the program code for causing performance of a method comprising:

performing a watershed algorithm to identify the patches, wherein the watershed algorithm traces paths of unlabeled pixels of increasing touch values until a pixel labeled with a patch number is found, at which time all pixels in the path are labeled with the same patch number as the labeled pixel, or a peak is found, at which time the peak is assigned a unique patch number and all pixels in the path are labeled with the unique patch number; and

performing a post-watershed merge of two patches having a saddle point between them that is shallow as compared to the peaks represented by the patches.

55. A digital audio player including a computer-readable medium comprising program code for identifying and processing patches indicative of touch events from a plurality of pixels having touch values captured during a scan of a touch sensor panel, the program code for causing performance of a method comprising:

performing a watershed algorithm to identify the patches, wherein the watershed algorithm traces paths of unlabeled pixels of increasing touch values until a pixel labeled with a patch number is found, at which time all pixels in the path are labeled with the same patch number as the labeled pixel, or a peak is found, at which time the peak is assigned a unique patch number and all pixels in the path are labeled with the unique patch number; and

performing a post-watershed merge of two patches having a saddle point between them that is shallow as compared to the peaks represented by the patches.

56. An apparatus for identifying and processing patches indicative of touch events from a plurality of pixels having touch values captured during a scan of a touch sensor panel, comprising:

means for performing a watershed algorithm to identify the patches, wherein the watershed algorithm traces paths of unlabeled pixels of increasing touch values until a pixel labeled with a patch number is found, at which time all pixels in the path are labeled with the same patch number as the labeled pixel, or a peak is found, at which time the peak is assigned a unique patch number and all pixels in the path are labeled with the unique patch number; and

means for performing a post-watershed merge of two patches having a saddle point between them that is shallow as compared to the peaks represented by the patches.