q_recognizer/point_cloud_recognizer.rs
1/**
2 * The $P Point-Cloud Recognizer (rust version)
3 *
4 * Translated to rust from the original authors' C# code with an AI tool.
5 * The translated code has been reviewed by Ferran Pujol Camins.
6 *
7 * Original authors:
8 *
9 * Radu-Daniel Vatavu, Ph.D.
10 * University Stefan cel Mare of Suceava
11 * Suceava 720229, Romania
12 * vatavu@eed.usv.ro
13 *
14 * Lisa Anthony, Ph.D.
15 * UMBC
16 * Information Systems Department
17 * 1000 Hilltop Circle
18 * Baltimore, MD 21250
19 * lanthony@umbc.edu
20 *
21 * Jacob O. Wobbrock, Ph.D.
22 * The Information School
23 * University of Washington
24 * Seattle, WA 98195-2840
25 * wobbrock@uw.edu
26 *
27 * The academic publication for the $P recognizer, and what should be
28 * used to cite it, is:
29 *
30 * Vatavu, R.-D., Anthony, L. and Wobbrock, J.O. (2012).
31 * Gestures as point clouds: A $P recognizer for user interface
32 * prototypes. Proceedings of the ACM Int'l Conference on
33 * Multimodal Interfaces (ICMI '12). Santa Monica, California
34 * (October 22-26, 2012). New York: ACM Press, pp. 273-280.
35 *
36 * This software is distributed under the "New BSD License" agreement:
37 *
38 * Copyright (c) 2012, Radu-Daniel Vatavu, Lisa Anthony, and
39 * Jacob O. Wobbrock. All rights reserved.
40 *
41 * Redistribution and use in source and binary forms, with or without
42 * modification, are permitted provided that the following conditions are met:
43 * * Redistributions of source code must retain the above copyright
44 * notice, this list of conditions and the following disclaimer.
45 * * Redistributions in binary form must reproduce the above copyright
46 * notice, this list of conditions and the following disclaimer in the
47 * documentation and/or other materials provided with the distribution.
48 * * Neither the names of the University Stefan cel Mare of Suceava,
49 * University of Washington, nor UMBC, nor the names of its contributors
50 * may be used to endorse or promote products derived from this software
51 * without specific prior written permission.
52 *
53 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
54 * IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
55 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
56 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL Radu-Daniel Vatavu OR Lisa Anthony
57 * OR Jacob O. Wobbrock OR Ferran Pujol Camins BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
58 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
59 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
60 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
61 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
62 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
63 * SUCH DAMAGE.
64**/
65
66use crate::{geometry, gesture::Gesture, point::Point};
67
68/// Main function of the $P recognizer.
69/// Classifies a candidate gesture against a set of training samples.
70/// Returns the class of the closest neighbor in the training set.
71pub fn classify(candidate: &Gesture, training_set: &[Gesture]) -> String {
72 let mut min_distance = f32::MAX;
73 let mut gesture_class = String::new();
74 for template in training_set {
75 let dist = greedy_cloud_match(&candidate.points, &template.points);
76 if dist < min_distance {
77 min_distance = dist;
78 gesture_class = template.name.clone();
79 }
80 }
81 gesture_class
82}
83
84/// Implements greedy search for a minimum-distance matching between two point clouds
85fn greedy_cloud_match(points1: &[Point], points2: &[Point]) -> f32 {
86 // the two clouds should have the same number of points by now
87 let n = points1.len();
88
89 // controls the number of greedy search trials (eps is in [0..1])
90 let eps = 0.5;
91
92 let step = (n as f32).powf(1.0 - eps).floor() as usize;
93 let mut min_distance = f32::MAX;
94 for i in (0..n).step_by(step) {
95 // match points1 --> points2 starting with index point i
96 let dist1 = cloud_distance(points1, points2, i);
97 // match points2 --> points1 starting with index point i
98 let dist2 = cloud_distance(points2, points1, i);
99 min_distance = min_distance.min(dist1).min(dist2);
100 }
101 min_distance
102}
103
104/// Computes the distance between two point clouds by performing a minimum-distance greedy matching
105/// starting with point startIndex
106fn cloud_distance(points1: &[Point], points2: &[Point], start_index: usize) -> f32 {
107 // the two clouds should have the same number of points by now
108 let n = points1.len();
109 // matched[i] signals whether point i from the 2nd cloud has been already matched
110 let mut matched = vec![false; n];
111 // computes the sum of distances between matched points (i.e., the distance between the two clouds)
112 let mut sum = 0.0;
113 let mut i = start_index;
114 loop {
115 let mut index = 0;
116 let mut min_dist = f32::MAX;
117 for j in 0..n {
118 if !matched[j] {
119 let dist = geometry::euclidean_distance(&points1[i], &points2[j]);
120 if dist < min_dist {
121 min_dist = dist;
122 index = j;
123 }
124 }
125 }
126 // point index from the 2nd cloud is matched to point i from the 1st cloud
127 matched[index] = true;
128 let weight = 1.0 - (((i - start_index + n) % n) as f32 / n as f32);
129 // weight each distance with a confidence coefficient that decreases from 1 to 0
130 sum += weight * min_dist;
131 i = (i + 1) % n;
132 if i == start_index {
133 break;
134 }
135 }
136 sum
137}