diff options
| -rw-r--r-- | include/input/CoordinateFilter.h | 54 | ||||
| -rw-r--r-- | include/input/OneEuroFilter.h | 101 | ||||
| -rw-r--r-- | include/input/Resampler.h | 41 | ||||
| -rw-r--r-- | libs/input/Android.bp | 2 | ||||
| -rw-r--r-- | libs/input/CoordinateFilter.cpp | 31 | ||||
| -rw-r--r-- | libs/input/OneEuroFilter.cpp | 79 | ||||
| -rw-r--r-- | libs/input/Resampler.cpp | 30 | ||||
| -rw-r--r-- | libs/input/tests/Android.bp | 1 | ||||
| -rw-r--r-- | libs/input/tests/OneEuroFilter_test.cpp | 134 |
9 files changed, 473 insertions, 0 deletions
diff --git a/include/input/CoordinateFilter.h b/include/input/CoordinateFilter.h new file mode 100644 index 0000000000..f36472dc8c --- /dev/null +++ b/include/input/CoordinateFilter.h @@ -0,0 +1,54 @@ +/** + * Copyright 2024 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#pragma once + +#include <chrono> + +#include <input/Input.h> +#include <input/OneEuroFilter.h> + +namespace android { + +/** + * Pair of OneEuroFilters that independently filter X and Y coordinates. Both filters share the same + * constructor's parameters. The minimum cutoff frequency is the base cutoff frequency, that is, the + * resulting cutoff frequency in the absence of signal's speed. Likewise, beta is a scaling factor + * of the signal's speed that sets how much the signal's speed contributes to the resulting cutoff + * frequency. The adaptive cutoff frequency criterion is f_c = f_c_min + β|̇x_filtered| + */ +class CoordinateFilter { +public: + explicit CoordinateFilter(float minCutoffFreq, float beta); + + /** + * Filters in place only the AXIS_X and AXIS_Y fields from coords. Each call to filter must + * provide a timestamp strictly greater than the timestamp of the previous call. The first time + * this method is invoked no filtering takes place. Subsequent calls do overwrite `coords` with + * filtered data. + * + * @param timestamp The timestamps at which to filter. It must be greater than the one passed in + * the previous call. + * @param coords Coordinates to be overwritten by the corresponding filtered coordinates. + */ + void filter(std::chrono::duration<float> timestamp, PointerCoords& coords); + +private: + OneEuroFilter mXFilter; + OneEuroFilter mYFilter; +}; + +} // namespace android
\ No newline at end of file diff --git a/include/input/OneEuroFilter.h b/include/input/OneEuroFilter.h new file mode 100644 index 0000000000..a0168e4f91 --- /dev/null +++ b/include/input/OneEuroFilter.h @@ -0,0 +1,101 @@ +/** + * Copyright 2024 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#pragma once + +#include <chrono> +#include <optional> + +#include <input/Input.h> + +namespace android { + +/** + * Low pass filter with adaptive low pass frequency based on the signal's speed. The signal's cutoff + * frequency is determined by f_c = f_c_min + β|̇x_filtered|. Refer to + * https://dl.acm.org/doi/10.1145/2207676.2208639 for details on how the filter works and how to + * tune it. + */ +class OneEuroFilter { +public: + /** + * Default cutoff frequency of the filtered signal's speed. 1.0 Hz is the value in the filter's + * paper. + */ + static constexpr float kDefaultSpeedCutoffFreq = 1.0; + + OneEuroFilter() = delete; + + explicit OneEuroFilter(float minCutoffFreq, float beta, + float speedCutoffFreq = kDefaultSpeedCutoffFreq); + + OneEuroFilter(const OneEuroFilter&) = delete; + OneEuroFilter& operator=(const OneEuroFilter&) = delete; + OneEuroFilter(OneEuroFilter&&) = delete; + OneEuroFilter& operator=(OneEuroFilter&&) = delete; + + /** + * Returns the filtered value of rawPosition. Each call to filter must provide a timestamp + * strictly greater than the timestamp of the previous call. The first time the method is + * called, it returns the value of rawPosition. Any subsequent calls provide a filtered value. + * + * @param timestamp The timestamp at which to filter. It must be strictly greater than the one + * provided in the previous call. + * @param rawPosition Position to be filtered. + */ + float filter(std::chrono::duration<float> timestamp, float rawPosition); + +private: + /** + * Minimum cutoff frequency. This is the constant term in the adaptive cutoff frequency + * criterion. Units are Hertz. + */ + const float mMinCutoffFreq; + + /** + * Slope of the cutoff frequency criterion. This is the term scaling the absolute value of the + * filtered signal's speed. The data member is dimensionless, that is, it does not have units. + */ + const float mBeta; + + /** + * Cutoff frequency of the signal's speed. This is the cutoff frequency applied to the filtering + * of the signal's speed. Units are Hertz. + */ + const float mSpeedCutoffFreq; + + /** + * The timestamp from the previous call. Units are seconds. + */ + std::optional<std::chrono::duration<float>> mPrevTimestamp; + + /** + * The raw position from the previous call. + */ + std::optional<float> mPrevRawPosition; + + /** + * The filtered velocity from the previous call. Units are position per second. + */ + std::optional<float> mPrevFilteredVelocity; + + /** + * The filtered position from the previous call. + */ + std::optional<float> mPrevFilteredPosition; +}; + +} // namespace android diff --git a/include/input/Resampler.h b/include/input/Resampler.h index 6d95ca7e86..155097732c 100644 --- a/include/input/Resampler.h +++ b/include/input/Resampler.h @@ -19,11 +19,13 @@ #include <array> #include <chrono> #include <iterator> +#include <map> #include <optional> #include <vector> #include <android-base/logging.h> #include <ftl/mixins.h> +#include <input/CoordinateFilter.h> #include <input/Input.h> #include <input/InputTransport.h> #include <input/RingBuffer.h> @@ -293,4 +295,43 @@ private: inline static void addSampleToMotionEvent(const Sample& sample, MotionEvent& motionEvent); }; +/** + * Resampler that first applies the LegacyResampler resampling algorithm, then independently filters + * the X and Y coordinates with a pair of One Euro filters. + */ +class FilteredLegacyResampler final : public Resampler { +public: + /** + * Creates a resampler, using the given minCutoffFreq and beta to instantiate its One Euro + * filters. + */ + explicit FilteredLegacyResampler(float minCutoffFreq, float beta); + + void resampleMotionEvent(std::chrono::nanoseconds requestedFrameTime, MotionEvent& motionEvent, + const InputMessage* futureMessage) override; + + std::chrono::nanoseconds getResampleLatency() const override; + +private: + LegacyResampler mResampler; + + /** + * Minimum cutoff frequency of the value's low pass filter. Refer to OneEuroFilter class for a + * more detailed explanation. + */ + const float mMinCutoffFreq; + + /** + * Scaling factor of the adaptive cutoff frequency criterion. Refer to OneEuroFilter class for a + * more detailed explanation. + */ + const float mBeta; + + /* + * Note: an associative array with constant insertion and lookup times would be more efficient. + * When this was implemented, there was no container with these properties. + */ + std::map<int32_t /*pointerId*/, CoordinateFilter> mFilteredPointers; +}; + } // namespace android diff --git a/libs/input/Android.bp b/libs/input/Android.bp index e4e81adf58..a4ae54b351 100644 --- a/libs/input/Android.bp +++ b/libs/input/Android.bp @@ -217,6 +217,7 @@ cc_library { ], srcs: [ "AccelerationCurve.cpp", + "CoordinateFilter.cpp", "Input.cpp", "InputConsumer.cpp", "InputConsumerNoResampling.cpp", @@ -230,6 +231,7 @@ cc_library { "KeyLayoutMap.cpp", "MotionPredictor.cpp", "MotionPredictorMetricsManager.cpp", + "OneEuroFilter.cpp", "PrintTools.cpp", "PropertyMap.cpp", "Resampler.cpp", diff --git a/libs/input/CoordinateFilter.cpp b/libs/input/CoordinateFilter.cpp new file mode 100644 index 0000000000..d231474577 --- /dev/null +++ b/libs/input/CoordinateFilter.cpp @@ -0,0 +1,31 @@ +/** + * Copyright 2024 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#define LOG_TAG "CoordinateFilter" + +#include <input/CoordinateFilter.h> + +namespace android { + +CoordinateFilter::CoordinateFilter(float minCutoffFreq, float beta) + : mXFilter{minCutoffFreq, beta}, mYFilter{minCutoffFreq, beta} {} + +void CoordinateFilter::filter(std::chrono::duration<float> timestamp, PointerCoords& coords) { + coords.setAxisValue(AMOTION_EVENT_AXIS_X, mXFilter.filter(timestamp, coords.getX())); + coords.setAxisValue(AMOTION_EVENT_AXIS_Y, mYFilter.filter(timestamp, coords.getY())); +} + +} // namespace android diff --git a/libs/input/OneEuroFilter.cpp b/libs/input/OneEuroFilter.cpp new file mode 100644 index 0000000000..400d7c9ab0 --- /dev/null +++ b/libs/input/OneEuroFilter.cpp @@ -0,0 +1,79 @@ +/** + * Copyright 2024 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#define LOG_TAG "OneEuroFilter" + +#include <chrono> +#include <cmath> + +#include <android-base/logging.h> +#include <input/CoordinateFilter.h> + +namespace android { +namespace { + +inline float cutoffFreq(float minCutoffFreq, float beta, float filteredSpeed) { + return minCutoffFreq + beta * std::abs(filteredSpeed); +} + +inline float smoothingFactor(std::chrono::duration<float> samplingPeriod, float cutoffFreq) { + return samplingPeriod.count() / (samplingPeriod.count() + (1.0 / (2.0 * M_PI * cutoffFreq))); +} + +inline float lowPassFilter(float rawPosition, float prevFilteredPosition, float smoothingFactor) { + return smoothingFactor * rawPosition + (1 - smoothingFactor) * prevFilteredPosition; +} + +} // namespace + +OneEuroFilter::OneEuroFilter(float minCutoffFreq, float beta, float speedCutoffFreq) + : mMinCutoffFreq{minCutoffFreq}, mBeta{beta}, mSpeedCutoffFreq{speedCutoffFreq} {} + +float OneEuroFilter::filter(std::chrono::duration<float> timestamp, float rawPosition) { + LOG_IF(FATAL, mPrevFilteredPosition.has_value() && (timestamp <= *mPrevTimestamp)) + << "Timestamp must be greater than mPrevTimestamp"; + + const std::chrono::duration<float> samplingPeriod = (mPrevTimestamp.has_value()) + ? (timestamp - *mPrevTimestamp) + : std::chrono::duration<float>{1.0}; + + const float rawVelocity = (mPrevFilteredPosition.has_value()) + ? ((rawPosition - *mPrevFilteredPosition) / samplingPeriod.count()) + : 0.0; + + const float speedSmoothingFactor = smoothingFactor(samplingPeriod, mSpeedCutoffFreq); + + const float filteredVelocity = (mPrevFilteredVelocity.has_value()) + ? lowPassFilter(rawVelocity, *mPrevFilteredVelocity, speedSmoothingFactor) + : rawVelocity; + + const float positionCutoffFreq = cutoffFreq(mMinCutoffFreq, mBeta, filteredVelocity); + + const float positionSmoothingFactor = smoothingFactor(samplingPeriod, positionCutoffFreq); + + const float filteredPosition = (mPrevFilteredPosition.has_value()) + ? lowPassFilter(rawPosition, *mPrevFilteredPosition, positionSmoothingFactor) + : rawPosition; + + mPrevTimestamp = timestamp; + mPrevRawPosition = rawPosition; + mPrevFilteredVelocity = filteredVelocity; + mPrevFilteredPosition = filteredPosition; + + return filteredPosition; +} + +} // namespace android diff --git a/libs/input/Resampler.cpp b/libs/input/Resampler.cpp index 056db093d1..3ab132d550 100644 --- a/libs/input/Resampler.cpp +++ b/libs/input/Resampler.cpp @@ -389,4 +389,34 @@ void LegacyResampler::resampleMotionEvent(nanoseconds frameTime, MotionEvent& mo mLastRealSample = *(mLatestSamples.end() - 1); } +// --- FilteredLegacyResampler --- + +FilteredLegacyResampler::FilteredLegacyResampler(float minCutoffFreq, float beta) + : mResampler{}, mMinCutoffFreq{minCutoffFreq}, mBeta{beta} {} + +void FilteredLegacyResampler::resampleMotionEvent(std::chrono::nanoseconds requestedFrameTime, + MotionEvent& motionEvent, + const InputMessage* futureSample) { + mResampler.resampleMotionEvent(requestedFrameTime, motionEvent, futureSample); + const size_t numSamples = motionEvent.getHistorySize() + 1; + for (size_t sampleIndex = 0; sampleIndex < numSamples; ++sampleIndex) { + for (size_t pointerIndex = 0; pointerIndex < motionEvent.getPointerCount(); + ++pointerIndex) { + const int32_t pointerId = motionEvent.getPointerProperties(pointerIndex)->id; + const nanoseconds eventTime = + nanoseconds{motionEvent.getHistoricalEventTime(sampleIndex)}; + // Refer to the static function `setMotionEventPointerCoords` for a justification of + // casting away const. + PointerCoords& pointerCoords = const_cast<PointerCoords&>( + *(motionEvent.getHistoricalRawPointerCoords(pointerIndex, sampleIndex))); + const auto& [iter, _] = mFilteredPointers.try_emplace(pointerId, mMinCutoffFreq, mBeta); + iter->second.filter(eventTime, pointerCoords); + } + } +} + +std::chrono::nanoseconds FilteredLegacyResampler::getResampleLatency() const { + return mResampler.getResampleLatency(); +} + } // namespace android diff --git a/libs/input/tests/Android.bp b/libs/input/tests/Android.bp index 661c9f739f..46e819061f 100644 --- a/libs/input/tests/Android.bp +++ b/libs/input/tests/Android.bp @@ -25,6 +25,7 @@ cc_test { "InputVerifier_test.cpp", "MotionPredictor_test.cpp", "MotionPredictorMetricsManager_test.cpp", + "OneEuroFilter_test.cpp", "Resampler_test.cpp", "RingBuffer_test.cpp", "TestInputChannel.cpp", diff --git a/libs/input/tests/OneEuroFilter_test.cpp b/libs/input/tests/OneEuroFilter_test.cpp new file mode 100644 index 0000000000..270e789c84 --- /dev/null +++ b/libs/input/tests/OneEuroFilter_test.cpp @@ -0,0 +1,134 @@ +/** + * Copyright 2024 The Android Open Source Project + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +#include <input/OneEuroFilter.h> + +#include <algorithm> +#include <chrono> +#include <cmath> +#include <numeric> +#include <vector> + +#include <gtest/gtest.h> + +#include <input/Input.h> + +namespace android { +namespace { + +using namespace std::literals::chrono_literals; +using std::chrono::duration; + +struct Sample { + duration<double> timestamp{}; + double value{}; + + friend bool operator<(const Sample& lhs, const Sample& rhs) { return lhs.value < rhs.value; } +}; + +/** + * Generates a sinusoidal signal with the passed frequency and amplitude. + */ +std::vector<Sample> generateSinusoidalSignal(duration<double> signalDuration, + double samplingFrequency, double signalFrequency, + double amplitude) { + std::vector<Sample> signal; + const duration<double> samplingPeriod{1.0 / samplingFrequency}; + for (duration<double> timestamp{0.0}; timestamp < signalDuration; timestamp += samplingPeriod) { + signal.push_back( + Sample{timestamp, + amplitude * std::sin(2.0 * M_PI * signalFrequency * timestamp.count())}); + } + return signal; +} + +double meanAbsoluteError(const std::vector<Sample>& filteredSignal, + const std::vector<Sample>& signal) { + if (filteredSignal.size() != signal.size()) { + ADD_FAILURE() << "filteredSignal and signal do not have equal number of samples"; + return std::numeric_limits<double>::max(); + } + std::vector<double> absoluteError; + for (size_t sampleIndex = 0; sampleIndex < signal.size(); ++sampleIndex) { + absoluteError.push_back( + std::abs(filteredSignal[sampleIndex].value - signal[sampleIndex].value)); + } + if (absoluteError.empty()) { + ADD_FAILURE() << "Zero division. absoluteError is empty"; + return std::numeric_limits<double>::max(); + } + return std::accumulate(absoluteError.begin(), absoluteError.end(), 0.0) / absoluteError.size(); +} + +double maxAbsoluteAmplitude(const std::vector<Sample>& signal) { + if (signal.empty()) { + ADD_FAILURE() << "Max absolute value amplitude does not exist. Signal is empty"; + return std::numeric_limits<double>::max(); + } + std::vector<Sample> absoluteSignal; + for (const Sample& sample : signal) { + absoluteSignal.push_back(Sample{sample.timestamp, std::abs(sample.value)}); + } + return std::max_element(absoluteSignal.begin(), absoluteSignal.end())->value; +} + +} // namespace + +class OneEuroFilterTest : public ::testing::Test { +protected: + // The constructor's parameters are the ones that Chromium's using. The tuning was based on a 60 + // Hz sampling frequency. Refer to their one_euro_filter.h header for additional information + // about these parameters. + OneEuroFilterTest() : mFilter{/*minCutoffFreq=*/4.7, /*beta=*/0.01} {} + + std::vector<Sample> filterSignal(const std::vector<Sample>& signal) { + std::vector<Sample> filteredSignal; + for (const Sample& sample : signal) { + filteredSignal.push_back( + Sample{sample.timestamp, mFilter.filter(sample.timestamp, sample.value)}); + } + return filteredSignal; + } + + OneEuroFilter mFilter; +}; + +TEST_F(OneEuroFilterTest, PassLowFrequencySignal) { + const std::vector<Sample> signal = + generateSinusoidalSignal(1s, /*samplingFrequency=*/60, /*signalFrequency=*/1, + /*amplitude=*/1); + + const std::vector<Sample> filteredSignal = filterSignal(signal); + + // The reason behind using the mean absolute error as a metric is that, ideally, a low frequency + // filtered signal is expected to be almost identical to the raw one. Therefore, the error + // between them should be minimal. The constant is heuristically chosen. + EXPECT_LT(meanAbsoluteError(filteredSignal, signal), 0.25); +} + +TEST_F(OneEuroFilterTest, RejectHighFrequencySignal) { + const std::vector<Sample> signal = + generateSinusoidalSignal(1s, /*samplingFrequency=*/60, /*signalFrequency=*/22.5, + /*amplitude=*/1); + + const std::vector<Sample> filteredSignal = filterSignal(signal); + + // The filtered signal should consist of values that are much closer to zero. The comparison + // constant is heuristically chosen. + EXPECT_LT(maxAbsoluteAmplitude(filteredSignal), 0.25); +} + +} // namespace android |