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
54class CirclesGridClusterFinder
55{
56    CirclesGridClusterFinder& operator=(const CirclesGridClusterFinder&);
57    CirclesGridClusterFinder(const CirclesGridClusterFinder&);
58public:
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);
69private:
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> &centers);
75
76  float squareSize, maxRectifiedDistance;
77  bool isAsymmetricGrid;
78
79  cv::Size patternSize;
80};
81
82class Graph
83{
84public:
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;
102private:
103  Vertices vertices;
104};
105
106struct Path
107{
108  int firstVertex;
109  int lastVertex;
110  int length;
111
112  std::vector<size_t> vertices;
113
114  Path(int first = -1, int last = -1, int len = -1)
115  {
116    firstVertex = first;
117    lastVertex = last;
118    length = len;
119  }
120};
121
122struct 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
146class CirclesGridFinder
147{
148public:
149  CirclesGridFinder(cv::Size patternSize, const std::vector<cv::Point2f> &testKeypoints,
150                    const CirclesGridFinderParameters &parameters = 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;
163private:
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