doi: 10.7873/DATE.2015.0017

Clustering-Based Multi-Touch Algorithm Framework for the Tracking Problem with a Large Number of Points

Shih-Lun Huang1, Sheng-Yi Hung1 and Chung-Ping Chen2

1Graduate Institute of Electronics Engineering, National Taiwan University, Taipei, Taiwan

2Department of Electrical Engineering, National Taiwan University, Taipei, Taiwan


Microcontrollers (MCUs) are extensively used in consumer devices for specific purposes because they are tiny, cheap, and low-power. Any time-consuming algorithm and any large-size program are not suited for MCUs. Recently, we found that the conventional multi-touch algorithm becomes computationally expensive to handle the applications of large- sized touch panels. Although a more high-end MCU can obtain an improvement on speed, it would increase manu- facturing cost and operating power consumption as well. In the whole multi-touch algorithm flow, point tracking is the most computationally expensive part. Fortunately, touch point tracking is similar to the pin-assignment problem in EDA. To accelerate tracking, we employ EDA techniques, such as clustering, to speed up our multi-touch algorithm. Besides, we prove that the tracking problem would be solved in O(n) time for practical cases and without losing its ac- curacy after clustering. Furthermore, we apply computational geometry techniques to develop an effcient clustering method. Experimental results show that clustering is efficient and effective. For the necessary requirement of large- area touch panels having 20 touch points, we can reduce the runtime by up to 70%. Besides, our multi-touch algorithm may support up to 80 touch points accompanied by a low-cost MCU.

Full Text (PDF)