mirror of
https://github.com/opencv/opencv.git
synced 2026-07-25 21:33:04 +04:00
Ding zhehao
ffa38e1b74
imgproc: optimize EMD (Earth Mover's Distance) solver performance #29194 ### imgproc: optimize EMD solver performance using O(V) spanning tree traversal --- This PR significantly optimizes the performance of the Earth Mover's Distance (`cv::EMD`) solver in `modules/imgproc/src/emd_new.cpp`. Specifically, it refactors the dual-variable calculation in `EMDSolver::findBasicVars()` from a naive $O((N+M)^2)$ linked-list scanning approach to an optimized $O(N+M)$ BFS tree traversal utilizing existing adjacency lists, leading to a massive speedup. --- #### Technical Details & Core Bottleneck Fixed 1. **Algorithmic Complexity Reduction in `findBasicVars()`:** - **Before**: The original implementation solved the dual variables $u_i$ and $v_j$ by traversing the entire unmarked rows (`u0_head`) or columns (`v0_head`) linked-lists and invoking `getIsX(i, j)` inside nested loops to find connected basic variables. This resulted in an $O((N+M)^2)$ complexity per simplex iteration. For a scale of $2000 \times 2000$, this performed up to $16,000,000$ operations per iteration. - **After**: Since `EMDSolver` already maintains the adjacency lists of the basic variables tree (`rows_x` and `cols_x`), we can traverse the spanning tree in linear time. This PR implements a dual-queue BFS tree traversal. The complexity per iteration is drastically reduced to $O(N+M)$, performing at most $4000$ operations per iteration. 2. **Cache Locality & Pointer-Chasing Elimination:** - Replaced pointer-chasing on dynamically-allocated linked lists with contiguous, stack-allocated array queues (`cv::AutoBuffer`), significantly improving CPU L1/L2 cache hit rates and enabling hardware prefetching. --- #### Performance Benchmarks Below is the benchmark comparison evaluated on a standard CPU. #### Test 1: dims = 64 | Scale ($N, M$) | Original EMD (ms) | Optimized EMD (This PR) | Speedup | | :--- | :--- | :--- | :--- | | **100** | 5.473 | 3.419 | **1.60x** | | **500** | 381.871 | 244.355 | **1.56x** | | **1000** | 1893.053 | 1369.016 | **1.38x** | | **2000** | 11387.792 | 8331.221 | **1.37x** | #### Test 2: dims = 3 | Scale ($N, M$) | Original EMD (ms) | Optimized EMD (This PR) | Speedup | | :--- | :--- | :--- | :--- | | **100** | 4.433 | 3.042 | **1.46x** | | **500** | 365.762 | 259.735 | **1.41x** | | **1000** | 1989.400 | 1421.952 | **1.40x** | | **2000** | 12731.836 | 7952.210 | **1.60x** | *(Note: The exact performance figures may vary slightly depending on the compiler and test machine.)* --- #### Verification - All existing tests in `opencv_test_imgproc` (including EMD tests) pass successfully. No regressions were introduced. --- ### Pull Request Readiness Checklist See details at https://github.com/opencv/opencv/wiki/How_to_contribute#making-a-good-pull-request - [x] I agree to contribute to the project under Apache 2 License. - [x] To the best of my knowledge, the proposed patch is not based on a code under GPL or another license that is incompatible with OpenCV - [x] The PR is proposed to the proper branch - [ ] There is a reference to the original bug report and related work - [ ] There is accuracy test, performance test and test data in opencv_extra repository, if applicable Patch to opencv_extra has the same branch name. - [ ] The feature is well documented and sample code can be built with the project CMake
37 lines
913 B
C++
37 lines
913 B
C++
// This file is part of OpenCV project.
|
|
// It is subject to the license terms in the LICENSE file found in the top-level directory
|
|
// of this distribution and at http://opencv.org/license.html
|
|
|
|
#include "perf_precomp.hpp"
|
|
#include <cmath>
|
|
|
|
namespace opencv_test { namespace {
|
|
|
|
typedef tuple<int, int> EMD_Size_Dim_t;
|
|
typedef perf::TestBaseWithParam<EMD_Size_Dim_t> EMD_Fixture;
|
|
|
|
PERF_TEST_P(EMD_Fixture, L1_Distance, testing::Combine(
|
|
testing::Values(100, 500, 1000),
|
|
testing::Values(3, 64)
|
|
))
|
|
{
|
|
int size = get<0>(GetParam());
|
|
int dims = get<1>(GetParam());
|
|
|
|
Mat sign1(size, dims + 1, CV_32FC1);
|
|
Mat sign2(size, dims + 1, CV_32FC1);
|
|
|
|
theRNG().fill(sign1, RNG::UNIFORM, 0.1, 1.0);
|
|
theRNG().fill(sign2, RNG::UNIFORM, 0.1, 1.0);
|
|
|
|
declare.in(sign1, sign2);
|
|
|
|
TEST_CYCLE()
|
|
{
|
|
cv::EMD(sign1, sign2, cv::DIST_L1);
|
|
}
|
|
|
|
SANITY_CHECK_NOTHING();
|
|
}
|
|
|
|
}} |