Merge pull request #25991 from MaximSmolskiy:improve-corners-matching-in-ChessBoardDetector-NeighborsFinder-findCornerNeighbor

MaximSmolskiy · web-flow · commit 6ed603e91742 · 2024-08-05T13:28:07.000+03:00
Improve corners matching in ChessBoardDetector::NeighborsFinder::findCornerNeighbor #25991 ### Pull Request Readiness Checklist Idea was mentioned in `Section III-B. New Heuristic for Quadrangle Linking` of `Rufli, Martin & Scaramuzza, Davide & Siegwart, Roland. (2008). Automatic Detection of Checkerboards on Blurred and Distorted Images. 2008 IEEE/RSJ International Conference on Intelligent Robots and Systems, IROS. 3121-3126. 10.1109/IROS.2008.4650703` (https://rpg.ifi.uzh.ch/docs/IROS08_scaramuzza_b.pdf): ![Снимок экрана от 2024-08-05 09-51-27](https://github.com/user-attachments/assets/7a090ccc-c24c-4dfb-b0dd-259c8709eb72) ``` * For each candidate pair, focus on the quadrangles they belong to and draw two straight lines passing through the midsections of the respective quadrangle edges (see Fig. 6). * If the candidate corner and the source corner are on the same side of every of the four straight lines drawn this way (this corresponds to the yellow shaded area in Fig. 6), then the corners are successfully matched. ``` By improving corners matching, we can increase the search radius (`thresh_scale`). I tested this PR with benchmark ``` python3 objdetect_benchmark.py --configuration=generate_run --board_x=7 --path=res_chessboard --synthetic_object=chessboard ``` PR increases detected chessboards number by `3/7%`: ``` cell_img_size = 100 (default) before category detected chessboard total detected chessboard total chessboard average detected error chessboard all 0.910417 13110 14400 0.599746 Total detected time: 147.50906700000002 sec after category detected chessboard total detected chessboard total chessboard average detected error chessboard all 0.941667 13560 14400 0.596726 Total detected time: 136.68963200000007 sec ---------------------------------------------------------------------------------------------------------------------------------------------- cell_img_size = 10 before category detected chessboard total detected chessboard total chessboard average detected error chessboard all 0.539792 7773 14400 4.208237 Total detected time: 2.668964 sec after category detected chessboard total detected chessboard total chessboard average detected error chessboard all 0.579167 8340 14400 4.198448 Total detected time: 2.535998999999999 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 - [x] 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
@@ -222,7 +222,7 @@ class ChessBoardDetector
     int all_quads_count;
 
     struct NeighborsFinder {
-        const float thresh_scale = 1.f;
+        const float thresh_scale = sqrt(2.f);
         ChessBoardDetector& detector;
         std::vector<int> neighbors_indices;
         std::vector<float> neighbors_dists;
@@ -232,8 +232,9 @@ class ChessBoardDetector
         NeighborsFinder(ChessBoardDetector& detector);
 
         bool findCornerNeighbor(
-            const int idx,
-            const cv::Point2f& pt,
+            const int quad_idx,
+            const int corner_idx,
+            const cv::Point2f& corner_pt,
             float& min_dist,
             const float radius,
             int& closest_quad_idx,
@@ -514,9 +515,23 @@ ChessBoardDetector::NeighborsFinder::NeighborsFinder(ChessBoardDetector& _detect
     neighbors_dists.resize(all_corners_count);
 }
 
+static double pointSideFromLine(const Point2f& line_direction_vector, const Point2f& vector)
+{
+    return line_direction_vector.cross(vector);
+}
+
+static bool arePointsOnSameSideFromLine(const Point2f& line_pt1, const Point2f& line_pt2, const Point2f& pt1, const Point2f& pt2)
+{
+    const Point2f line_direction_vector = line_pt2 - line_pt1;
+    const Point2f vector1 = pt1 - line_pt1;
+    const Point2f vector2 = pt2 - line_pt1;
+    return pointSideFromLine(line_direction_vector, vector1) * pointSideFromLine(line_direction_vector, vector2) > 0.;
+}
+
 bool ChessBoardDetector::NeighborsFinder::findCornerNeighbor(
-    const int idx,
-    const cv::Point2f& pt,
+    const int quad_idx,
+    const int corner_idx,
+    const cv::Point2f& corner_pt,
     float& min_dist,
     const float radius,
     int& closest_quad_idx,
@@ -525,28 +540,29 @@ bool ChessBoardDetector::NeighborsFinder::findCornerNeighbor(
 {
     ChessBoardQuad* p_all_quads = detector.all_quads.data();
 
-    const ChessBoardQuad& cur_quad = (const ChessBoardQuad&)p_all_quads[idx];
+    const ChessBoardQuad& cur_quad = (const ChessBoardQuad&)p_all_quads[quad_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 std::vector<float> query = { corner_pt.x, corner_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)
+        if (k == quad_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]);
+        const Point2f neighbor_pt = all_quads_pts[neighbor_idx];
+        const float dist = normL2Sqr<float>(corner_pt - neighbor_pt);
         if (dist <= cur_quad.edge_len * thresh_scale &&
             dist <= q_k.edge_len * thresh_scale)
         {
@@ -560,6 +576,24 @@ bool ChessBoardDetector::NeighborsFinder::findCornerNeighbor(
                 DPRINTF("Incompatible edge lengths");
                 continue;
             }
+
+            const Point2f mid_pt1 = (cur_quad.corners[corner_idx]->pt + cur_quad.corners[(corner_idx + 1) & 3]->pt) / 2.f;
+            const Point2f mid_pt2 = (cur_quad.corners[(corner_idx + 2) & 3]->pt + cur_quad.corners[(corner_idx + 3) & 3]->pt) / 2.f;
+            if (!arePointsOnSameSideFromLine(mid_pt1, mid_pt2, corner_pt, neighbor_pt))
+                continue;
+
+            const Point2f mid_pt3 = (cur_quad.corners[(corner_idx + 1) & 3]->pt + cur_quad.corners[(corner_idx + 2) & 3]->pt) / 2.f;
+            const Point2f mid_pt4 = (cur_quad.corners[(corner_idx + 3) & 3]->pt + cur_quad.corners[corner_idx]->pt) / 2.f;
+            if (!arePointsOnSameSideFromLine(mid_pt3, mid_pt4, corner_pt, neighbor_pt))
+                continue;
+
+            const Point2f neighbor_pt_diagonal = q_k.corners[(j + 2) & 3]->pt;
+            if (!arePointsOnSameSideFromLine(mid_pt1, mid_pt2, corner_pt, neighbor_pt_diagonal))
+                continue;
+
+            if (!arePointsOnSameSideFromLine(mid_pt3, mid_pt4, neighbor_pt, neighbor_pt_diagonal))
+                continue;
+
             closest_neighbor_idx = neighbor_idx;
             closest_quad_idx = k;
             closest_corner_idx = j;
@@ -589,7 +623,7 @@ bool ChessBoardDetector::NeighborsFinder::findCornerNeighbor(
             if (cur_quad.neighbors[j] == closest_quad)
                 break;
 
-            if (normL2Sqr<float>(closest_corner_pt - all_quads_pts[(idx << 2) + j]) < min_dist)
+            if (normL2Sqr<float>(closest_corner_pt - all_quads_pts[(quad_idx << 2) + j]) < min_dist)
                 break;
         }
         if (j < 4)
@@ -1793,6 +1827,7 @@ void ChessBoardDetector::findQuadNeighbors()
 
             bool found = neighborsFinder.findCornerNeighbor(
                 idx,
+                i,
                 pt,
                 min_dist,
                 radius,
@@ -1813,6 +1848,7 @@ void ChessBoardDetector::findQuadNeighbors()
 
             found = neighborsFinder.findCornerNeighbor(
                 closest_quad_idx,
+                closest_corner_idx,
                 closest_corner_pt,
                 min_dist,
                 radius,
