libvot  0.1.3
A C++11 multithread library for image retrieval
image_graph.h
Go to the documentation of this file.
1 /*
2 Copyright (c) 2015, Tianwei Shen
3 All rights reserved.
4 
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are met:
7 
8 * Redistributions of source code must retain the above copyright notice, this
9  list of conditions and the following disclaimer.
10 
11 * Redistributions in binary form must reproduce the above copyright notice,
12  this list of conditions and the following disclaimer in the documentation
13  and/or other materials provided with the distribution.
14 
15 * Neither the name of libvot nor the names of its
16  contributors may be used to endorse or promote products derived from
17  this software without specific prior written permission.
18 
19 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
20 AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
21 IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
22 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE
23 FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
24 DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
25 SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
26 CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
27 OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 
30 */
31 
35 #ifndef IMAGEGRAPH_HEADER
36 #define IMAGEGRAPH_HEADER
37 
38 #include <iostream>
39 #include <cstdlib>
40 #include <vector>
41 #include <string>
42 #include <cassert>
43 #include <unordered_map>
44 
45 namespace vot
46 {
50 struct LinkEdge
51 {
52  size_t src;
53  size_t dst;
54  float score;
55  int p_match;
56  int g_match;
57 
58  LinkEdge(int src_ = -1, int dst_ = -1, float score_ = 0.0, int p_match_ = 0, int g_match_ = 0):
59  src(src_), dst(dst_), score(score_), p_match(p_match_), g_match(g_match_) {}
60 
62  LinkEdge(const LinkEdge &e)
63  {
64  src = e.src;
65  dst = e.dst;
66  score = e.score;
67  p_match = e.p_match;
68  g_match = e.g_match;
69  }
70 };
71 
75 struct ImageNode
76 {
77  int idx;
78  std::string image_name;
79  std::string sift_name;
80  ImageNode(int idx_ = -1, const std::string &iname = "", const std::string &sname = ""): idx(idx_), image_name(iname), sift_name(sname) {}
81 
83  ImageNode(const ImageNode & node)
84  {
85  idx = node.idx;
86  image_name = node.image_name;
87  sift_name = node.sift_name;
88  }
89 };
90 
95 {
96  typedef std::unordered_map<int, LinkEdge> EdgeMap;
97  typedef std::vector<std::vector<LinkEdge> > Edge2dArray;
98 public:
100  ImageGraph(int size);
102  ImageGraph(const std::vector<std::string> &image_filenames, const std::vector<std::string> &sift_filenames);
103  void addNode();
104  void addNode(const vot::ImageNode &n);
106  void addEdge(int src, int dst, double score = 0.0);
107  void addEdge(const vot::LinkEdge &n);
109  void addEdgeu(int src, int dst, double score = 0.0);
110  void addEdgeu(const vot::LinkEdge &n);
112  int numConnectedComponents(int threshold = 0);
113  bool kargerCut(std::vector<std::vector<int> > &global_min_cut);
115  bool consolidate(int k);
117  bool queryExpansion(Edge2dArray &expansion_lists, int level, int inlier_threshold = 150);
118  bool queryExpansionSub(int src, int tgt, double score, Edge2dArray &expansion_lists, bool **visit_mat, int level, int inlier_threshold);
120  bool graphvizu(std::string gv_filename, std::string graph_name);
122  void showInfo();
123  int adjListSize(int idx);
124  int nodeNum();
125 
126 private:
127  int size_;
128  std::vector<ImageNode> nodes_;
129  std::vector<EdgeMap> adj_maps_;
130 };
131 } // end of namespace vot
132 
133 #endif // IMAGEGRAPH_HEADER
ImageNode(int idx_=-1, const std::string &iname="", const std::string &sname="")
Definition: image_graph.h:80
int nodeNum()
Definition: image_graph.cpp:319
the image node used in image graph class
Definition: image_graph.h:75
std::string sift_name
the sift name
Definition: image_graph.h:79
void addNode()
Definition: image_graph.cpp:70
void addEdge(int src, int dst, double score=0.0)
Brief add one-way edge.
Definition: image_graph.cpp:84
void addEdgeu(int src, int dst, double score=0.0)
Brief add undirected edge.
Definition: image_graph.cpp:103
bool kargerCut(std::vector< std::vector< int > > &global_min_cut)
Definition: image_graph.cpp:151
ImageGraph(int size)
Brief construct ananymous image graph without filenames.
Definition: image_graph.cpp:51
bool graphvizu(std::string gv_filename, std::string graph_name)
Brief output the undirected visualization code for graphviz.
Definition: image_graph.cpp:286
bool queryExpansionSub(int src, int tgt, double score, Edge2dArray &expansion_lists, bool **visit_mat, int level, int inlier_threshold)
Definition: image_graph.cpp:212
std::string image_name
the image name
Definition: image_graph.h:78
int numConnectedComponents(int threshold=0)
Brief compute the number of connected components in a undirected graph (edge (i,j) and edge (j...
Definition: image_graph.cpp:116
void showInfo()
Brief output the information.
Definition: image_graph.cpp:274
int adjListSize(int idx)
Definition: image_graph.cpp:318
ImageNode(const ImageNode &node)
Copy constructor.
Definition: image_graph.h:83
bool queryExpansion(Edge2dArray &expansion_lists, int level, int inlier_threshold=150)
Brief Query expansion and its sub-routine.
Definition: image_graph.cpp:230
int idx
the optional original index (maybe in the image_list)
Definition: image_graph.h:77
namespace vot contains libvot functions and classes.
Definition: image_graph.cpp:49
bool consolidate(int k)
Brief Remove the singleton node from the graph.
Definition: image_graph.cpp:207
Image graph class.
Definition: image_graph.h:94