ImageGraph.cpp

Go to the documentation of this file.
00001 // -*- c-basic-offset: 4 -*-
00002 
00027 #include "ImageGraph.h"
00028 #include <queue>
00029 
00030 namespace HuginGraph
00031 {
00032 /* build adjacency list for all images in pano */
00033 ImageGraph::ImageGraph(const HuginBase::PanoramaData& pano, bool ignoreLinkedPosition)
00034 {
00035     if (pano.getNrOfImages() > 0)
00036     {
00037         m_graph.resize(pano.getNrOfImages());
00038         if (!ignoreLinkedPosition)
00039         {
00040             // handle all linked positions
00041             for (size_t i = 0; i < pano.getNrOfImages(); ++i)
00042             {
00043                 const HuginBase::SrcPanoImage& image = pano.getImage(i);
00044                 if (image.YawisLinked())
00045                 {
00046                     for (size_t j = i + 1; j < pano.getNrOfImages(); ++j)
00047                     {
00048                         if (image.YawisLinkedWith(pano.getImage(j)))
00049                         {
00050                             m_graph[i].insert(j);
00051                             m_graph[j].insert(i);
00052                         };
00053                     };
00054                 };
00055             };
00056         };
00057         // and now all control points
00058         const HuginBase::CPVector& cps = pano.getCtrlPoints();
00059         for (size_t i = 0; i < cps.size(); ++i)
00060         {
00061             if (cps[i].mode == HuginBase::ControlPoint::X_Y && cps[i].image1Nr != cps[i].image2Nr)
00062             {
00063                 m_graph[cps[i].image1Nr].insert(cps[i].image2Nr);
00064                 m_graph[cps[i].image2Nr].insert(cps[i].image1Nr);
00065             }
00066         }
00067     };
00068 };
00069 
00070 ImageGraph::ImageGraph(const HuginBase::CalculateImageOverlap& overlap)
00071 {
00072     const unsigned int nrImages = overlap.getNrOfImages();
00073     m_graph.resize(nrImages);
00074     // and now all control points
00075     for (size_t i = 0; i < nrImages-1; ++i)
00076     {
00077         for (size_t j = i + 1; j < nrImages; ++j)
00078         {
00079             if (overlap.getOverlap(i, j)>0.001)
00080             {
00081                 m_graph[i].insert(j);
00082                 m_graph[j].insert(i);
00083             }
00084         };
00085     };
00086 };
00087 
00088 template<typename VALUETYPE>
00089 void DepthFirstSearch(const ImageGraph::GraphList& graph, std::vector<VALUETYPE>& marks, const size_t vertex, const VALUETYPE setType, const VALUETYPE unvisitedType)
00090 {
00091     marks[vertex] = setType;
00092     for (HuginBase::UIntSet::const_iterator it = graph[vertex].begin(); it != graph[vertex].end(); ++it)
00093     {
00094         if (marks[*it] == unvisitedType)
00095         {
00096             DepthFirstSearch(graph, marks, *it, setType, unvisitedType);
00097         };
00098     };
00099 };
00100 
00101 ImageGraph::Components ImageGraph::GetComponents()
00102 {
00103     ImageGraph::Components comp;
00104     if (m_graph.empty())
00105     {
00106         return comp;
00107     };
00108     // and now the depth first search algorithm
00109     std::vector<size_t> marks(m_graph.size(), 0);
00110     size_t counter = 0;
00111     for (size_t i = 0; i < m_graph.size(); ++i)
00112     {
00113         if (marks[i] == 0)
00114         {
00115             counter++;
00116             DepthFirstSearch<size_t>(m_graph, marks, i, counter, 0);
00117         };
00118     };
00119     // now create the connected components as vector<UIntSet>
00120     comp.resize(counter);
00121     for (size_t imgNr = 0; imgNr < marks.size(); ++imgNr)
00122     {
00123         comp[marks[imgNr] - 1].insert(imgNr);
00124     }
00125     return comp;
00126 };
00127 
00128 bool ImageGraph::IsConnected()
00129 {
00130     if (m_graph.empty())
00131     {
00132         return false;
00133     };
00134     // and now the depth first search algorithm
00135     std::vector<bool> visited(m_graph.size(), false);
00136     DepthFirstSearch(m_graph, visited, 0, true, false);
00137     for (std::vector<bool>::const_iterator it = visited.begin(); it != visited.end(); ++it)
00138     {
00139         if (!(*it))
00140         {
00141             return false;
00142         }
00143     }
00144     return true;
00145 };
00146 
00147 void BreadthFirstSearchVisit(const ImageGraph::GraphList& graph,
00148     std::queue<size_t>& queue, std::vector<bool>& visited, BreadthFirstSearchVisitor* visitor)
00149 {
00150     while (!queue.empty())
00151     {
00152         const size_t vertex = queue.front();
00153         queue.pop();
00154         if (!visited[vertex])
00155         {
00156             visited[vertex] = true;
00157             HuginBase::UIntSet visitedNeighbors;
00158             HuginBase::UIntSet unvisitedNeighbors;
00159             for (HuginBase::UIntSet::const_iterator it = graph[vertex].begin(); it != graph[vertex].end(); ++it)
00160             {
00161                 if (visited[*it])
00162                 {
00163                     visitedNeighbors.insert(*it);
00164                 }
00165                 else
00166                 {
00167                     unvisitedNeighbors.insert(*it);
00168                     queue.push(*it);
00169                 };
00170             };
00171             visitor->Visit(vertex, visitedNeighbors, unvisitedNeighbors);
00172         };
00173     };
00174 }
00175 
00176 void ImageGraph::VisitAllImages(const size_t startImg, bool forceAllComponents, BreadthFirstSearchVisitor* visitor)
00177 {
00178     if (m_graph.empty())
00179     {
00180         return;
00181     }
00182     // range checking, just in case
00183     const size_t realStartImg = (startImg >= m_graph.size()) ? 0 : startImg;
00184     std::vector<bool> visited(m_graph.size(), false);
00185     std::queue<size_t> queue;
00186     // go down the graph starting from the startImg
00187     queue.push(realStartImg);
00188     BreadthFirstSearchVisit(m_graph, queue, visited, visitor);
00189     if (forceAllComponents)
00190     {
00191         // if the graph contains several components
00192         // we have not yet visited all images, so
00193         // restart the breadth first algorithm from the new component start
00194         for (size_t i = 0; i < m_graph.size(); ++i)
00195         {
00196             if (!visited[i])
00197             {
00198                 queue.push(i);
00199                 BreadthFirstSearchVisit(m_graph, queue, visited, visitor);
00200             };
00201         };
00202     };
00203 };
00204 
00205 }  // namespace HuginGraph

Generated on 27 May 2016 for Hugintrunk by  doxygen 1.4.7