Merge pull request #25427 from MaximSmolskiy:make-finding-corner-neighbor-symmetrical-in-ChessBoardDetector-findQuadNeighbors

MaximSmolskiy · web-flow · commit cc6f85e1bab6 · 2024-06-10T09:42:56.000+03:00
Make finding corner neighbor symmetrical in ChessBoardDetector::findQuadNeighbors #25427 ### Pull Request Readiness Checklist The basic idea of finding pair of corners neighbors is to find best candidate for first corner and check if first corner quite good candidate for its best candidate. And we test first corner for its best candidate less than best candidate for first corner. Idea of changes is to make finding corner neighbor symmetrical - find best candidate for first corner, find best candidate for second corner and match them as pair iff they are both best candidates for each other. Additional advantage - it simplifies code and removes some code duplication. I tested this PR with benchmark ``` python3 objdetect_benchmark.py --configuration=generate_run --board_x=7 --path=res_chessboard --synthetic_object=chessboard ``` There are minor changes in results ``` cell_img_size = 100 (default) before category detected chessboard total detected chessboard total chessboard average detected error chessboard _none_none_blur 1.000000 360 360 0.630345 _none_none_gaussNoise 0.833333 300 360 0.623405 _none_none_none 1.000000 360 360 0.631517 _none_none_strongBlur 1.000000 360 360 0.630316 _none_undistorted_blur 1.000000 360 360 0.671232 _none_undistorted_gaussNoise 1.000000 360 360 0.672619 _none_undistorted_none 1.000000 360 360 0.673669 _none_undistorted_strongBlur 1.000000 360 360 0.671257 _perspective_none_blur 1.000000 1080 1080 0.588694 _perspective_none_gaussNoise 0.805556 870 1080 0.599312 _perspective_none_none 1.000000 1080 1080 0.591063 _perspective_none_strongBlur 1.000000 1080 1080 0.588604 _perspective_undistorted_blur 1.000000 1080 1080 0.622081 _perspective_undistorted_gaussNoise 1.000000 1080 1080 0.625704 _perspective_undistorted_none 1.000000 1080 1080 0.624191 _perspective_undistorted_strongBlur 1.000000 1080 1080 0.621618 _strongPerspective_none_blur 1.000000 360 360 0.482934 _strongPerspective_none_gaussNoise 0.166667 60 360 0.391551 _strongPerspective_none_none 1.000000 360 360 0.480290 _strongPerspective_none_strongBlur 0.333333 120 360 0.469080 _strongPerspective_undistorted_blur 1.000000 360 360 0.503458 _strongPerspective_undistorted_gaussNoise 0.250000 90 360 0.448713 _strongPerspective_undistorted_none 1.000000 360 360 0.504412 _strongPerspective_undistorted_strongBlur 0.166667 60 360 0.473791 all 0.904167 13020 14400 0.600512 Total detected time: 139.65614900000008 sec after category detected chessboard total detected chessboard total chessboard average detected error chessboard _none_none_blur 1.000000 360 360 0.630345 _none_none_gaussNoise 0.750000 270 360 0.636279 _none_none_none 1.000000 360 360 0.631517 _none_none_strongBlur 1.000000 360 360 0.630316 _none_undistorted_blur 1.000000 360 360 0.671232 _none_undistorted_gaussNoise 1.000000 360 360 0.672619 _none_undistorted_none 1.000000 360 360 0.673669 _none_undistorted_strongBlur 1.000000 360 360 0.671257 _perspective_none_blur 1.000000 1080 1080 0.588694 _perspective_none_gaussNoise 0.888889 960 1080 0.594106 _perspective_none_none 1.000000 1080 1080 0.591064 _perspective_none_strongBlur 1.000000 1080 1080 0.588604 _perspective_undistorted_blur 1.000000 1080 1080 0.622081 _perspective_undistorted_gaussNoise 1.000000 1080 1080 0.625703 _perspective_undistorted_none 1.000000 1080 1080 0.624191 _perspective_undistorted_strongBlur 1.000000 1080 1080 0.621618 _strongPerspective_none_blur 1.000000 360 360 0.482934 _strongPerspective_none_gaussNoise 0.166667 60 360 0.391551 _strongPerspective_none_none 1.000000 360 360 0.480290 _strongPerspective_none_strongBlur 0.333333 120 360 0.469080 _strongPerspective_undistorted_blur 1.000000 360 360 0.503458 _strongPerspective_undistorted_gaussNoise 0.333333 120 360 0.422259 _strongPerspective_undistorted_none 1.000000 360 360 0.504412 _strongPerspective_undistorted_strongBlur 0.166667 60 360 0.473791 all 0.910417 13110 14400 0.599746 Total detected time: 142.40333700000005 sec ---------------------------------------------------------------------------------------------------------------------------------------------- cell_img_size = 10 before category detected chessboard total detected chessboard total chessboard average detected error chessboard _none_none_blur 0.991667 357 360 4.905091 _none_none_gaussNoise 0.750000 270 360 5.215633 _none_none_none 1.000000 360 360 4.943304 _none_none_strongBlur 0.916667 330 360 3.806217 _none_undistorted_blur 0.994444 358 360 5.220915 _none_undistorted_gaussNoise 0.997222 359 360 4.542443 _none_undistorted_none 0.997222 359 360 4.340208 _none_undistorted_strongBlur 0.161111 58 360 5.024331 _perspective_none_blur 0.629630 680 1080 4.825401 _perspective_none_gaussNoise 0.966667 1044 1080 3.895425 _perspective_none_none 0.971296 1049 1080 3.920378 _perspective_none_strongBlur 0.000000 0 1080 NaN _perspective_undistorted_blur 0.583333 630 1080 4.594335 _perspective_undistorted_gaussNoise 0.999074 1079 1080 3.553195 _perspective_undistorted_none 0.750000 810 1080 3.604110 _perspective_undistorted_strongBlur 0.000000 0 1080 NaN _strongPerspective_none_blur 0.000000 0 360 NaN _strongPerspective_none_gaussNoise 0.000000 0 360 NaN _strongPerspective_none_none 0.083333 30 360 2.382460 _strongPerspective_none_strongBlur 0.000000 0 360 NaN _strongPerspective_undistorted_blur 0.000000 0 360 NaN _strongPerspective_undistorted_gaussNoise 0.000000 0 360 NaN _strongPerspective_undistorted_none 0.000000 0 360 NaN _strongPerspective_undistorted_strongBlur 0.000000 0 360 NaN all 0.539792 7773 14400 4.209964 Total detected time: 2.6968930000000015 sec after category detected chessboard total detected chessboard total chessboard average detected error chessboard _none_none_blur 0.991667 357 360 4.905091 _none_none_gaussNoise 0.750000 270 360 5.215633 _none_none_none 1.000000 360 360 4.943304 _none_none_strongBlur 0.916667 330 360 3.806217 _none_undistorted_blur 0.994444 358 360 5.220915 _none_undistorted_gaussNoise 0.997222 359 360 4.542443 _none_undistorted_none 0.997222 359 360 4.340208 _none_undistorted_strongBlur 0.161111 58 360 5.024331 _perspective_none_blur 0.629630 680 1080 4.825401 _perspective_none_gaussNoise 0.966667 1044 1080 3.895425 _perspective_none_none 0.999074 1079 1080 3.865684 _perspective_none_strongBlur 0.000000 0 1080 NaN _perspective_undistorted_blur 0.583333 630 1080 4.594335 _perspective_undistorted_gaussNoise 0.999074 1079 1080 3.553195 _perspective_undistorted_none 0.750000 810 1080 3.604110 _perspective_undistorted_strongBlur 0.000000 0 1080 NaN _strongPerspective_none_blur 0.000000 0 360 NaN _strongPerspective_none_gaussNoise 0.000000 0 360 NaN _strongPerspective_none_none 0.000000 0 360 NaN _strongPerspective_none_strongBlur 0.000000 0 360 NaN _strongPerspective_undistorted_blur 0.000000 0 360 NaN _strongPerspective_undistorted_gaussNoise 0.000000 0 360 NaN _strongPerspective_undistorted_none 0.000000 0 360 NaN _strongPerspective_undistorted_strongBlur 0.000000 0 360 NaN all 0.539792 7773 14400 4.208308 Total detected time: 2.7706419999999983 sec ``` 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
diff --git a/modules/calib3d/src/calibinit.cpp b/modules/calib3d/src/calibinit.cpp
@@ -221,6 +221,26 @@ class ChessBoardDetector
 
     int all_quads_count;
 
+    struct NeighborsFinder {
+        const float thresh_scale = 1.f;
+        ChessBoardDetector& detector;
+        std::vector<int> neighbors_indices;
+        std::vector<float> neighbors_dists;
+        std::vector<Point2f> all_quads_pts;
+        flann::GenericIndex<flann::L2_Simple<float>> all_quads_pts_index;
+
+        NeighborsFinder(ChessBoardDetector& detector);
+
+        bool findCornerNeighbor(
+            const int idx,
+            const cv::Point2f& pt,
+            float& min_dist,
+            const float radius,
+            int& closest_quad_idx,
+            int& closest_corner_idx,
+            cv::Point2f& closest_corner_pt);
+    };
+
     ChessBoardDetector(const Size& pattern_size_) :
         pattern_size(pattern_size_),
         all_quads_count(0)
@@ -471,6 +491,125 @@ static void icvBinarizationHistogramBased(Mat & img)
     }
 }
 
+static std::vector<Point2f> getCornersFromQuads(ChessBoardQuad* p_all_quads, const int all_quads_count)
+{
+    std::vector<Point2f> all_quads_pts;
+    all_quads_pts.reserve(all_quads_count * 4);
+    for (int idx = 0; idx < all_quads_count; idx++)
+    {
+        const ChessBoardQuad& cur_quad = (const ChessBoardQuad&)p_all_quads[idx];
+        for (int i = 0; i < 4; i++)
+            all_quads_pts.push_back(cur_quad.corners[i]->pt);
+    }
+    return all_quads_pts;
+}
+
+ChessBoardDetector::NeighborsFinder::NeighborsFinder(ChessBoardDetector& _detector) :
+    detector(_detector),
+    all_quads_pts(getCornersFromQuads(detector.all_quads.data(), detector.all_quads_count)),
+    all_quads_pts_index(Mat(all_quads_pts).reshape(1, detector.all_quads_count * 4), cvflann::KDTreeSingleIndexParams())
+{
+    const int all_corners_count = detector.all_quads_count * 4;
+    neighbors_indices.resize(all_corners_count);
+    neighbors_dists.resize(all_corners_count);
+}
+
+bool ChessBoardDetector::NeighborsFinder::findCornerNeighbor(
+    const int idx,
+    const cv::Point2f& pt,
+    float& min_dist,
+    const float radius,
+    int& closest_quad_idx,
+    int& closest_corner_idx,
+    cv::Point2f& closest_corner_pt)
+{
+    ChessBoardQuad* p_all_quads = detector.all_quads.data();
+
+    const ChessBoardQuad& cur_quad = (const ChessBoardQuad&)p_all_quads[idx];
+    int closest_neighbor_idx = -1;
+    ChessBoardQuad *closest_quad = 0;
+
+    // find the closest corner in all other quadrangles
+    const std::vector<float> query = { pt.x, pt.y };
+    const cvflann::SearchParams search_params(-1);
+    const int neighbors_count = all_quads_pts_index.radiusSearch(query, neighbors_indices, neighbors_dists, radius, search_params);
+
+    for (int neighbor_idx_idx = 0; neighbor_idx_idx < neighbors_count; neighbor_idx_idx++)
+    {
+        const int neighbor_idx = neighbors_indices[neighbor_idx_idx];
+        const int k = neighbor_idx >> 2;
+        if (k == idx)
+            continue;
+
+        ChessBoardQuad& q_k = p_all_quads[k];
+        const int j = neighbor_idx & 3;
+        if (q_k.neighbors[j])
+            continue;
+
+        const float dist = normL2Sqr<float>(pt - all_quads_pts[neighbor_idx]);
+        if (dist <= cur_quad.edge_len * thresh_scale &&
+            dist <= q_k.edge_len * thresh_scale)
+        {
+            // check edge lengths, make sure they're compatible
+            // edges that are different by more than 1:4 are rejected.
+            // edge_len is squared edge length, so we compare them
+            // with squared constant 16 = 4^2
+            if (q_k.edge_len > 16 * cur_quad.edge_len ||
+                cur_quad.edge_len > 16 * q_k.edge_len)
+            {
+                DPRINTF("Incompatible edge lengths");
+                continue;
+            }
+            closest_neighbor_idx = neighbor_idx;
+            closest_quad_idx = k;
+            closest_corner_idx = j;
+            closest_quad = &q_k;
+            min_dist = dist;
+            break;
+        }
+    }
+
+    // we found a matching corner point?
+    if (closest_neighbor_idx >= 0 && closest_quad_idx >= 0 && closest_corner_idx >= 0 && min_dist < FLT_MAX)
+    {
+        CV_Assert(closest_quad);
+
+        if (cur_quad.count >= 4 || closest_quad->count >= 4)
+            return false;
+
+        // If another point from our current quad is closer to the found corner
+        // than the current one, then we don't count this one after all.
+        // This is necessary to support small squares where otherwise the wrong
+        // corner will get matched to closest_quad;
+        closest_corner_pt = all_quads_pts[closest_neighbor_idx];
+
+        int j = 0;
+        for (; j < 4; j++)
+        {
+            if (cur_quad.neighbors[j] == closest_quad)
+                break;
+
+            if (normL2Sqr<float>(closest_corner_pt - all_quads_pts[(idx << 2) + j]) < min_dist)
+                break;
+        }
+        if (j < 4)
+            return false;
+
+        // Check that each corner is a neighbor of different quads
+        for(j = 0; j < 4; j++ )
+        {
+            if (closest_quad->neighbors[j] == &cur_quad)
+                break;
+        }
+        if (j < 4)
+            return false;
+
+        return true;
+    }
+
+    return false;
+}
+
 bool findChessboardCorners(InputArray image_, Size pattern_size,
                            OutputArray corners_, int flags)
 {
@@ -1607,25 +1746,7 @@ int ChessBoardDetector::checkQuadGroup(const std::vector<ChessBoardQuad*>& quad_
 
 void ChessBoardDetector::findQuadNeighbors()
 {
-    const float thresh_scale = 1.f;
-
-    const int all_corners_count = all_quads_count * 4;
-
-    std::vector<Point2f> all_quads_pts;
-    all_quads_pts.reserve(all_corners_count);
-    for (int idx = 0; idx < all_quads_count; idx++)
-    {
-        const ChessBoardQuad& cur_quad = (const ChessBoardQuad&)all_quads[idx];
-        for (int i = 0; i < 4; i++)
-            all_quads_pts.push_back(cur_quad.corners[i]->pt);
-    }
-
-    const cvflann::KDTreeSingleIndexParams index_params;
-    flann::GenericIndex<flann::L2_Simple<float>> all_quads_pts_index(Mat(all_quads_pts).reshape(1, all_corners_count), index_params);
-
-    // find quad neighbors
-    std::vector<int> neighbors_indices(all_corners_count);
-    std::vector<float> neighbors_dists(all_corners_count);
+    NeighborsFinder neighborsFinder(*this);
     for (int idx = 0; idx < all_quads_count; idx++)
     {
         ChessBoardQuad& cur_quad = (ChessBoardQuad&)all_quads[idx];
@@ -1641,125 +1762,65 @@ void ChessBoardDetector::findQuadNeighbors()
             if (cur_quad.neighbors[i])
                 continue;
 
-            float min_dist = FLT_MAX;
-            int closest_neighbor_idx = -1;
-            int closest_corner_idx = -1;
-            ChessBoardQuad *closest_quad = 0;
+            const cv::Point2f pt = neighborsFinder.all_quads_pts[(idx << 2) + i];
 
-            cv::Point2f pt = all_quads_pts[(idx << 2) + i];
-
-            // find the closest corner in all other quadrangles
-            std::vector<float> query = Mat(pt);
-            float radius = cur_quad.edge_len * thresh_scale + 1;
-            const cvflann::SearchParams search_params(-1);
-            int neighbors_count = all_quads_pts_index.radiusSearch(query, neighbors_indices, neighbors_dists, radius, search_params);
+            float min_dist = FLT_MAX;
 
-            for (int neighbor_idx_idx = 0; neighbor_idx_idx < neighbors_count; neighbor_idx_idx++)
-            {
-                const int neighbor_idx = neighbors_indices[neighbor_idx_idx];
-                const int k = neighbor_idx >> 2;
-                if (k == idx)
-                    continue;
-
-                ChessBoardQuad& q_k = all_quads[k];
-                const int j = neighbor_idx & 3;
-                if (q_k.neighbors[j])
-                    continue;
-
-                const float dist = normL2Sqr<float>(pt - all_quads_pts[neighbor_idx]);
-                if (dist <= cur_quad.edge_len * thresh_scale &&
-                    dist <= q_k.edge_len * thresh_scale)
-                {
-                    // check edge lengths, make sure they're compatible
-                    // edges that are different by more than 1:4 are rejected.
-                    // edge_len is squared edge length, so we compare them
-                    // with squared constant 16 = 4^2
-                    if (q_k.edge_len > 16 * cur_quad.edge_len ||
-                        cur_quad.edge_len > 16 * q_k.edge_len)
-                    {
-                        DPRINTF("Incompatible edge lengths");
-                        continue;
-                    }
-                    closest_neighbor_idx = neighbor_idx;
-                    closest_corner_idx = j;
-                    closest_quad = &q_k;
-                    min_dist = dist;
-                    break;
-                }
-            }
+            int closest_quad_idx = -1;
+            int closest_corner_idx = -1;
 
-            // we found a matching corner point?
-            if (closest_neighbor_idx >= 0 && closest_corner_idx >= 0 && min_dist < FLT_MAX)
-            {
-                CV_Assert(closest_quad);
+            float radius = cur_quad.edge_len * neighborsFinder.thresh_scale + 1;
 
-                if (cur_quad.count >= 4 || closest_quad->count >= 4)
-                    continue;
+            cv::Point2f closest_corner_pt;
 
-                // If another point from our current quad is closer to the found corner
-                // than the current one, then we don't count this one after all.
-                // This is necessary to support small squares where otherwise the wrong
-                // corner will get matched to closest_quad;
-                ChessBoardCorner& closest_corner = *closest_quad->corners[closest_corner_idx];
-                cv::Point2f closest_corner_pt = all_quads_pts[closest_neighbor_idx];
+            bool found = neighborsFinder.findCornerNeighbor(
+                idx,
+                pt,
+                min_dist,
+                radius,
+                closest_quad_idx,
+                closest_corner_idx,
+                closest_corner_pt);
 
-                int j = 0;
-                for (; j < 4; j++)
-                {
-                    if (cur_quad.neighbors[j] == closest_quad)
-                        break;
+            if (!found)
+                continue;
 
-                    if (normL2Sqr<float>(closest_corner_pt - all_quads_pts[(idx << 2) + j]) < min_dist)
-                        break;
-                }
-                if (j < 4)
-                    continue;
+            radius = min_dist + 1;
+            min_dist = FLT_MAX;
 
-                // Check that each corner is a neighbor of different quads
-                for(j = 0; j < 4; j++ )
-                {
-                    if (closest_quad->neighbors[j] == &cur_quad)
-                        break;
-                }
-                if (j < 4)
-                    continue;
+            int closest_closest_quad_idx = -1;
+            int closest_closest_corner_idx = -1;
 
-                // check whether the closest corner to closest_corner is different from pt
-                query = Mat(closest_corner_pt);
-                radius = min_dist + 1;
-                neighbors_count = all_quads_pts_index.radiusSearch(query, neighbors_indices, neighbors_dists, radius, search_params);
+            cv::Point2f closest_closest_corner_pt;
 
-                int neighbor_idx_idx = 0;
-                for (; neighbor_idx_idx < neighbors_count; neighbor_idx_idx++)
-                {
-                    const int neighbor_idx = neighbors_indices[neighbor_idx_idx];
-                    j = neighbor_idx >> 2;
+            found = neighborsFinder.findCornerNeighbor(
+                closest_quad_idx,
+                closest_corner_pt,
+                min_dist,
+                radius,
+                closest_closest_quad_idx,
+                closest_closest_corner_idx,
+                closest_closest_corner_pt);
 
-                    ChessBoardQuad* q = &const_cast<ChessBoardQuad&>(all_quads[j]);
-                    if (j == idx || q == closest_quad)
-                        continue;
+            if (!found)
+                continue;
 
-                    const int k = neighbor_idx & 3;
-                    CV_DbgAssert(q);
-                    if (!q->neighbors[k])
-                    {
-                        if (normL2Sqr<float>(closest_corner_pt - all_quads_pts[neighbor_idx]) < min_dist)
-                            break;
-                    }
-                }
-                if (neighbor_idx_idx < neighbors_count)
-                    continue;
+            if (closest_closest_quad_idx != idx ||
+                closest_closest_corner_idx != i ||
+                closest_closest_corner_pt != pt)
+                continue;
 
-                closest_corner.pt = (pt + closest_corner_pt) * 0.5f;
+            ChessBoardQuad* closest_quad = &all_quads[closest_quad_idx];
+            ChessBoardCorner& closest_corner = *closest_quad->corners[closest_corner_idx];
+            closest_corner.pt = (pt + closest_corner_pt) * 0.5f;
 
-                // We've found one more corner - remember it
-                cur_quad.count++;
-                cur_quad.neighbors[i] = closest_quad;
-                cur_quad.corners[i] = &closest_corner;
+            // We've found one more corner - remember it
+            cur_quad.count++;
+            cur_quad.neighbors[i] = closest_quad;
+            cur_quad.corners[i] = &closest_corner;
 
-                closest_quad->count++;
-                closest_quad->neighbors[closest_corner_idx] = &cur_quad;
-            }
+            closest_quad->count++;
+            closest_quad->neighbors[closest_corner_idx] = &cur_quad;
         }
     }
 }
