1 /*M/////////////////////////////////////////////////////////////////////////////////////// 2 // 3 // IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 4 // 5 // By downloading, copying, installing or using the software you agree to this license. 6 // If you do not agree to this license, do not download, install, 7 // copy or use the software. 8 // 9 // 10 // License Agreement 11 // For Open Source Computer Vision Library 12 // 13 // Copyright (C) 2000-2008, Intel Corporation, all rights reserved. 14 // Copyright (C) 2009, Willow Garage Inc., all rights reserved. 15 // Third party copyrights are property of their respective owners. 16 // 17 // Redistribution and use in source and binary forms, with or without modification, 18 // are permitted provided that the following conditions are met: 19 // 20 // * Redistribution's of source code must retain the above copyright notice, 21 // this list of conditions and the following disclaimer. 22 // 23 // * Redistribution's in binary form must reproduce the above copyright notice, 24 // this list of conditions and the following disclaimer in the documentation 25 // and/or other materials provided with the distribution. 26 // 27 // * The name of the copyright holders may not be used to endorse or promote products 28 // derived from this software without specific prior written permission. 29 // 30 // This software is provided by the copyright holders and contributors "as is" and 31 // any express or implied warranties, including, but not limited to, the implied 32 // warranties of merchantability and fitness for a particular purpose are disclaimed. 33 // In no event shall the Intel Corporation or contributors be liable for any direct, 34 // indirect, incidental, special, exemplary, or consequential damages 35 // (including, but not limited to, procurement of substitute goods or services; 36 // loss of use, data, or profits; or business interruption) however caused 37 // and on any theory of liability, whether in contract, strict liability, 38 // or tort (including negligence or otherwise) arising in any way out of 39 // the use of this software, even if advised of the possibility of such damage. 40 // 41 //M*/ 42 43 #ifndef CIRCLESGRID_HPP_ 44 #define CIRCLESGRID_HPP_ 45 46 #include <fstream> 47 #include <set> 48 #include <list> 49 #include <numeric> 50 #include <map> 51 52 #include "precomp.hpp" 53 54 class CirclesGridClusterFinder 55 { 56 CirclesGridClusterFinder& operator=(const CirclesGridClusterFinder&); 57 CirclesGridClusterFinder(const CirclesGridClusterFinder&); 58 public: CirclesGridClusterFinder(bool _isAsymmetricGrid)59 CirclesGridClusterFinder(bool _isAsymmetricGrid) 60 { 61 isAsymmetricGrid = _isAsymmetricGrid; 62 squareSize = 1.0f; 63 maxRectifiedDistance = (float)(squareSize / 2.0); 64 } 65 void findGrid(const std::vector<cv::Point2f> &points, cv::Size patternSize, std::vector<cv::Point2f>& centers); 66 67 //cluster 2d points by geometric coordinates 68 void hierarchicalClustering(const std::vector<cv::Point2f> &points, const cv::Size &patternSize, std::vector<cv::Point2f> &patternPoints); 69 private: 70 void findCorners(const std::vector<cv::Point2f> &hull2f, std::vector<cv::Point2f> &corners); 71 void findOutsideCorners(const std::vector<cv::Point2f> &corners, std::vector<cv::Point2f> &outsideCorners); 72 void getSortedCorners(const std::vector<cv::Point2f> &hull2f, const std::vector<cv::Point2f> &corners, const std::vector<cv::Point2f> &outsideCorners, std::vector<cv::Point2f> &sortedCorners); 73 void rectifyPatternPoints(const std::vector<cv::Point2f> &patternPoints, const std::vector<cv::Point2f> &sortedCorners, std::vector<cv::Point2f> &rectifiedPatternPoints); 74 void parsePatternPoints(const std::vector<cv::Point2f> &patternPoints, const std::vector<cv::Point2f> &rectifiedPatternPoints, std::vector<cv::Point2f> ¢ers); 75 76 float squareSize, maxRectifiedDistance; 77 bool isAsymmetricGrid; 78 79 cv::Size patternSize; 80 }; 81 82 class Graph 83 { 84 public: 85 typedef std::set<size_t> Neighbors; 86 struct Vertex 87 { 88 Neighbors neighbors; 89 }; 90 typedef std::map<size_t, Vertex> Vertices; 91 92 Graph(size_t n); 93 void addVertex(size_t id); 94 void addEdge(size_t id1, size_t id2); 95 void removeEdge(size_t id1, size_t id2); 96 bool doesVertexExist(size_t id) const; 97 bool areVerticesAdjacent(size_t id1, size_t id2) const; 98 size_t getVerticesCount() const; 99 size_t getDegree(size_t id) const; 100 const Neighbors& getNeighbors(size_t id) const; 101 void floydWarshall(cv::Mat &distanceMatrix, int infinity = -1) const; 102 private: 103 Vertices vertices; 104 }; 105 106 struct Path 107 { 108 int firstVertex; 109 int lastVertex; 110 int length; 111 112 std::vector<size_t> vertices; 113 PathPath114 Path(int first = -1, int last = -1, int len = -1) 115 { 116 firstVertex = first; 117 lastVertex = last; 118 length = len; 119 } 120 }; 121 122 struct CirclesGridFinderParameters 123 { 124 CirclesGridFinderParameters(); 125 cv::Size2f densityNeighborhoodSize; 126 float minDensity; 127 int kmeansAttempts; 128 int minDistanceToAddKeypoint; 129 int keypointScale; 130 float minGraphConfidence; 131 float vertexGain; 132 float vertexPenalty; 133 float existingVertexGain; 134 float edgeGain; 135 float edgePenalty; 136 float convexHullFactor; 137 float minRNGEdgeSwitchDist; 138 139 enum GridType 140 { 141 SYMMETRIC_GRID, ASYMMETRIC_GRID 142 }; 143 GridType gridType; 144 }; 145 146 class CirclesGridFinder 147 { 148 public: 149 CirclesGridFinder(cv::Size patternSize, const std::vector<cv::Point2f> &testKeypoints, 150 const CirclesGridFinderParameters ¶meters = CirclesGridFinderParameters()); 151 bool findHoles(); 152 static cv::Mat rectifyGrid(cv::Size detectedGridSize, const std::vector<cv::Point2f>& centers, const std::vector< 153 cv::Point2f> &keypoint, std::vector<cv::Point2f> &warpedKeypoints); 154 155 void getHoles(std::vector<cv::Point2f> &holes) const; 156 void getAsymmetricHoles(std::vector<cv::Point2f> &holes) const; 157 cv::Size getDetectedGridSize() const; 158 159 void drawBasis(const std::vector<cv::Point2f> &basis, cv::Point2f origin, cv::Mat &drawImg) const; 160 void drawBasisGraphs(const std::vector<Graph> &basisGraphs, cv::Mat &drawImg, bool drawEdges = true, 161 bool drawVertices = true) const; 162 void drawHoles(const cv::Mat &srcImage, cv::Mat &drawImage) const; 163 private: 164 void computeRNG(Graph &rng, std::vector<cv::Point2f> &vectors, cv::Mat *drawImage = 0) const; 165 void rng2gridGraph(Graph &rng, std::vector<cv::Point2f> &vectors) const; 166 void eraseUsedGraph(std::vector<Graph> &basisGraphs) const; 167 void filterOutliersByDensity(const std::vector<cv::Point2f> &samples, std::vector<cv::Point2f> &filteredSamples); 168 void findBasis(const std::vector<cv::Point2f> &samples, std::vector<cv::Point2f> &basis, 169 std::vector<Graph> &basisGraphs); 170 void findMCS(const std::vector<cv::Point2f> &basis, std::vector<Graph> &basisGraphs); 171 size_t findLongestPath(std::vector<Graph> &basisGraphs, Path &bestPath); 172 float computeGraphConfidence(const std::vector<Graph> &basisGraphs, bool addRow, const std::vector<size_t> &points, 173 const std::vector<size_t> &seeds); 174 void addHolesByGraph(const std::vector<Graph> &basisGraphs, bool addRow, cv::Point2f basisVec); 175 176 size_t findNearestKeypoint(cv::Point2f pt) const; 177 void addPoint(cv::Point2f pt, std::vector<size_t> &points); 178 void findCandidateLine(std::vector<size_t> &line, size_t seedLineIdx, bool addRow, cv::Point2f basisVec, std::vector< 179 size_t> &seeds); 180 void findCandidateHoles(std::vector<size_t> &above, std::vector<size_t> &below, bool addRow, cv::Point2f basisVec, 181 std::vector<size_t> &aboveSeeds, std::vector<size_t> &belowSeeds); 182 static bool areCentersNew(const std::vector<size_t> &newCenters, const std::vector<std::vector<size_t> > &holes); 183 bool isDetectionCorrect(); 184 185 static void insertWinner(float aboveConfidence, float belowConfidence, float minConfidence, bool addRow, 186 const std::vector<size_t> &above, const std::vector<size_t> &below, std::vector<std::vector< 187 size_t> > &holes); 188 189 struct Segment 190 { 191 cv::Point2f s; 192 cv::Point2f e; 193 Segment(cv::Point2f _s, cv::Point2f _e); 194 }; 195 196 //if endpoint is on a segment then function return false 197 static bool areSegmentsIntersecting(Segment seg1, Segment seg2); 198 static bool doesIntersectionExist(const std::vector<Segment> &corner, const std::vector<std::vector<Segment> > &segments); 199 void getCornerSegments(const std::vector<std::vector<size_t> > &points, std::vector<std::vector<Segment> > &segments, 200 std::vector<cv::Point> &cornerIndices, std::vector<cv::Point> &firstSteps, 201 std::vector<cv::Point> &secondSteps) const; 202 size_t getFirstCorner(std::vector<cv::Point> &largeCornerIndices, std::vector<cv::Point> &smallCornerIndices, 203 std::vector<cv::Point> &firstSteps, std::vector<cv::Point> &secondSteps) const; 204 static double getDirection(cv::Point2f p1, cv::Point2f p2, cv::Point2f p3); 205 206 std::vector<cv::Point2f> keypoints; 207 208 std::vector<std::vector<size_t> > holes; 209 std::vector<std::vector<size_t> > holes2; 210 std::vector<std::vector<size_t> > *largeHoles; 211 std::vector<std::vector<size_t> > *smallHoles; 212 213 const cv::Size_<size_t> patternSize; 214 CirclesGridFinderParameters parameters; 215 216 CirclesGridFinder& operator=(const CirclesGridFinder&); 217 CirclesGridFinder(const CirclesGridFinder&); 218 }; 219 220 #endif /* CIRCLESGRID_HPP_ */ 221