Алгоритм классификации для мультисенсорного экрана

Question

Какой алгоритм можно использовать для решения следующей задачи классификации? У нас есть мультисенсорный экран, пользователь, который может касаться его двумя или тремя пальцами одновременно.

1. После того, как пользователь коснулся экрана, мы запоминаем начальные положения его пальцев. Каждый палец получает группу координат от устройства.
2. Когда пользователь двигает пальцами, мы должны отслеживать движения его пальцев.

Проблема в том, что когда пальцы приближаются друг к другу. Как определить, к каким точкам принадлежит какой палец?

Я знаю, что это какая-то проблема классификации. Какой алгоритм можно использовать для решения этой проблемы?

Answer 1

Одна проблема состоит в том, чтобы начать с отчетов о N местах в момент времени t и отчетов о N местах в момент времени t + 1 и выяснить, что позиция 1 в момент времени t совпадает с позицией 3 в момент времени t + 1.Военные много смотрели на подобные вещи, часто под именем объединения данных.Один из подходов состоит в том, чтобы записать стоимость связывания позиции i в момент времени t с позицией j в момент времени t + 1, а затем найти перестановку с минимальными общими затратами - это пример http://en.wikipedia.org/wiki/Assignment_problem.

Если устройство на самом деле сообщает, что два пальца очень близко друг к другу, как один, у вас есть более сложная проблема - но вы, конечно, не имеете много разных позиций для рассмотрения, поэтому вы должны иметь возможность, например, попробовать различные способы обработки одного отчета о позициив виде двух разных отчетов, а затем выбрать наиболее высокую оценку.

Answer 2

Решение проблемы с назначением является излишним, учитывая, что вы пытаетесь назначить три точки на три пальца.Даже если вы пытаетесь назначить пять точек пяти пальцам, вам лучше использовать метод грубой силы, чтобы определить оптимальную конфигурацию точек для пальцев.Обратите внимание, что для трех пальцев и трех точек существует только шесть возможных уникальных назначений пальцев точкам.Поэтому лучше всего рассчитать стоимость каждой конфигурации назначения и выбрать ту, которая будет стоить с наименьшей стоимостью.

Тем не менее, я думаю, что это не соответствует сути вашего вопроса.Сложной частью является не сам процесс назначения, а выбор подходящей функции «затрат» для каждого возможного назначения.Если функция стоимости не учитывает предыдущие назначения точек пальца, то при назначении любого пальца любой точке есть равные затраты, и поэтому вам не хватает «непрерывности», когда пальцы назначаются одной и той же точке перемещения.

Таким образом, ваша цель состоит в том, чтобы ваши модели назначения были «реальными».Подход, который я предлагаю, таков:

Определите физическую модель для движения пальцев.Очень простой моделью будет модель импульса, в которой каждый палец не зависит друг от друга и предполагается, что он обладает некоторой инерцией.Если палец перемещает dx, dy в одном кадре, можно ожидать, что он будет перемещать dx, dy во втором кадре.Это дает вам ожидаемое значение того, где вы ожидаете, что палец будет следующим.Теперь вы можете определить стоимость присвоения пальца точке как некоторую функцию расстояния между местоположением фактической зарегистрированной точки и тем, где вы ожидали, что это будет.

Суммируйте затраты по каждому назначению с указанием точки и найдите конфигурацию с наименьшими затратами.

Теперь, если вы хотите быть более сложным, все, что вам нужно сделать, это использовать более сложную модель.Возможно, вы не хотите предполагать, что пальцы двигаются независимо.Вы можете ожидать некоторой корреляции между движениями пальцев.В этом случае уточните модель, рассчитайте новые точечные ожидания и рассчитайте стоимость назначения, как и раньше.