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(const cv::CirclesGridFinderParameters2 & parameters)59 CirclesGridClusterFinder(const cv::CirclesGridFinderParameters2 ¶meters) 60 { 61 isAsymmetricGrid = parameters.gridType == cv::CirclesGridFinderParameters::ASYMMETRIC_GRID; 62 squareSize = parameters.squareSize; 63 maxRectifiedDistance = parameters.maxRectifiedDistance; 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> &patternPoints, 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 class CirclesGridFinder 123 { 124 public: 125 CirclesGridFinder(cv::Size patternSize, const std::vector<cv::Point2f> &testKeypoints, 126 const cv::CirclesGridFinderParameters ¶meters = cv::CirclesGridFinderParameters()); 127 bool findHoles(); 128 static cv::Mat rectifyGrid(cv::Size detectedGridSize, const std::vector<cv::Point2f>& centers, const std::vector< 129 cv::Point2f> &keypoint, std::vector<cv::Point2f> &warpedKeypoints); 130 131 void getHoles(std::vector<cv::Point2f> &holes) const; 132 void getAsymmetricHoles(std::vector<cv::Point2f> &holes) const; 133 cv::Size getDetectedGridSize() const; 134 135 void drawBasis(const std::vector<cv::Point2f> &basis, cv::Point2f origin, cv::Mat &drawImg) const; 136 void drawBasisGraphs(const std::vector<Graph> &basisGraphs, cv::Mat &drawImg, bool drawEdges = true, 137 bool drawVertices = true) const; 138 void drawHoles(const cv::Mat &srcImage, cv::Mat &drawImage) const; 139 private: 140 void computeRNG(Graph &rng, std::vector<cv::Point2f> &vectors, cv::Mat *drawImage = 0) const; 141 void rng2gridGraph(Graph &rng, std::vector<cv::Point2f> &vectors) const; 142 void eraseUsedGraph(std::vector<Graph> &basisGraphs) const; 143 void filterOutliersByDensity(const std::vector<cv::Point2f> &samples, std::vector<cv::Point2f> &filteredSamples); 144 void findBasis(const std::vector<cv::Point2f> &samples, std::vector<cv::Point2f> &basis, 145 std::vector<Graph> &basisGraphs); 146 void findMCS(const std::vector<cv::Point2f> &basis, std::vector<Graph> &basisGraphs); 147 size_t findLongestPath(std::vector<Graph> &basisGraphs, Path &bestPath); 148 float computeGraphConfidence(const std::vector<Graph> &basisGraphs, bool addRow, const std::vector<size_t> &points, 149 const std::vector<size_t> &seeds); 150 void addHolesByGraph(const std::vector<Graph> &basisGraphs, bool addRow, cv::Point2f basisVec); 151 152 size_t findNearestKeypoint(cv::Point2f pt) const; 153 void addPoint(cv::Point2f pt, std::vector<size_t> &points); 154 void findCandidateLine(std::vector<size_t> &line, size_t seedLineIdx, bool addRow, cv::Point2f basisVec, std::vector< 155 size_t> &seeds); 156 void findCandidateHoles(std::vector<size_t> &above, std::vector<size_t> &below, bool addRow, cv::Point2f basisVec, 157 std::vector<size_t> &aboveSeeds, std::vector<size_t> &belowSeeds); 158 static bool areCentersNew(const std::vector<size_t> &newCenters, const std::vector<std::vector<size_t> > &holes); 159 bool isDetectionCorrect(); 160 161 static void insertWinner(float aboveConfidence, float belowConfidence, float minConfidence, bool addRow, 162 const std::vector<size_t> &above, const std::vector<size_t> &below, std::vector<std::vector< 163 size_t> > &holes); 164 165 struct Segment 166 { 167 cv::Point2f s; 168 cv::Point2f e; 169 Segment(cv::Point2f _s, cv::Point2f _e); 170 }; 171 172 //if endpoint is on a segment then function return false 173 static bool areSegmentsIntersecting(Segment seg1, Segment seg2); 174 static bool doesIntersectionExist(const std::vector<Segment> &corner, const std::vector<std::vector<Segment> > &segments); 175 void getCornerSegments(const std::vector<std::vector<size_t> > &points, std::vector<std::vector<Segment> > &segments, 176 std::vector<cv::Point> &cornerIndices, std::vector<cv::Point> &firstSteps, 177 std::vector<cv::Point> &secondSteps) const; 178 size_t getFirstCorner(std::vector<cv::Point> &largeCornerIndices, std::vector<cv::Point> &smallCornerIndices, 179 std::vector<cv::Point> &firstSteps, std::vector<cv::Point> &secondSteps) const; 180 static double getDirection(cv::Point2f p1, cv::Point2f p2, cv::Point2f p3); 181 182 std::vector<cv::Point2f> keypoints; 183 184 std::vector<std::vector<size_t> > holes; 185 std::vector<std::vector<size_t> > holes2; 186 std::vector<std::vector<size_t> > *largeHoles; 187 std::vector<std::vector<size_t> > *smallHoles; 188 189 const cv::Size_<size_t> patternSize; 190 cv::CirclesGridFinderParameters parameters; 191 192 CirclesGridFinder& operator=(const CirclesGridFinder&); 193 CirclesGridFinder(const CirclesGridFinder&); 194 }; 195 196 #endif /* CIRCLESGRID_HPP_ */ 197