mirror of
https://github.com/opencv/opencv.git
synced 2026-07-21 19:33:03 +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