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 #include <stdlib.h> 44 #include <math.h> 45 #include <vector> 46 47 /****************************************************************************************\ 48 * For EMDL1 Framework * 49 \****************************************************************************************/ 50 typedef struct cvEMDEdge* cvPEmdEdge; 51 typedef struct cvEMDNode* cvPEmdNode; 52 struct cvEMDNode 53 { 54 int pos[3]; // grid position 55 float d; // initial value 56 int u; 57 // tree maintainance 58 int iLevel; // level in the tree, 0 means root 59 cvPEmdNode pParent; // pointer to its parent 60 cvPEmdEdge pChild; 61 cvPEmdEdge pPEdge; // point to the edge coming out from its parent 62 }; 63 struct cvEMDEdge 64 { 65 float flow; // initial value 66 int iDir; // 1:outward, 0:inward 67 // tree maintainance 68 cvPEmdNode pParent; // point to its parent 69 cvPEmdNode pChild; // the child node 70 cvPEmdEdge pNxt; // next child/edge 71 }; 72 typedef std::vector<cvEMDNode> cvEMDNodeArray; 73 typedef std::vector<cvEMDEdge> cvEMDEdgeArray; 74 typedef std::vector<cvEMDNodeArray> cvEMDNodeArray2D; 75 typedef std::vector<cvEMDEdgeArray> cvEMDEdgeArray2D; 76 typedef std::vector<float> floatArray; 77 typedef std::vector<floatArray> floatArray2D; 78 79 /****************************************************************************************\ 80 * EMDL1 Class * 81 \****************************************************************************************/ 82 class EmdL1 83 { 84 public: 85 EmdL1() 86 { 87 m_pRoot = NULL; 88 binsDim1 = 0; 89 binsDim2 = 0; 90 binsDim3 = 0; 91 dimension = 0; 92 nMaxIt = 500; 93 } 94 95 ~EmdL1() 96 { 97 } 98 99 float getEMDL1(cv::Mat &sig1, cv::Mat &sig2); 100 void setMaxIteration(int _nMaxIt); 101 102 private: 103 //-- SubFunctions called in the EMD algorithm 104 bool initBaseTrees(int n1=0, int n2=0, int n3=0); 105 bool fillBaseTrees(float *H1, float *H2); 106 bool greedySolution(); 107 bool greedySolution2(); 108 bool greedySolution3(); 109 void initBVTree(); 110 void updateSubtree(cvPEmdNode pRoot); 111 bool isOptimal(); 112 void findNewSolution(); 113 void findLoopFromEnterBV(); 114 float compuTotalFlow(); 115 116 private: 117 int dimension; 118 int binsDim1, binsDim2, binsDim3; // the hitogram contains m_n1 rows and m_n2 columns 119 int nNBV; // number of Non-Basic Variables (NBV) 120 int nMaxIt; 121 cvEMDNodeArray2D m_Nodes; // all nodes 122 cvEMDEdgeArray2D m_EdgesRight; // all edges to right 123 cvEMDEdgeArray2D m_EdgesUp; // all edges to upward 124 std::vector<cvEMDNodeArray2D> m_3dNodes; // all nodes for 3D 125 std::vector<cvEMDEdgeArray2D> m_3dEdgesRight; // all edges to right, 3D 126 std::vector<cvEMDEdgeArray2D> m_3dEdgesUp; // all edges to upward, 3D 127 std::vector<cvEMDEdgeArray2D> m_3dEdgesDeep; // all edges to deep, 3D 128 std::vector<cvPEmdEdge> m_NBVEdges; // pointers to all NON-BV edges 129 std::vector<cvPEmdNode> m_auxQueue; // auxiliary node queue 130 cvPEmdNode m_pRoot; // root of the BV Tree 131 cvPEmdEdge m_pEnter; // Enter BV edge 132 int m_iEnter; // Enter BV edge, index in m_NBVEdges 133 cvPEmdEdge m_pLeave; // Leave BV edge 134 int m_nItr; // number of iteration 135 // auxiliary variables for searching a new loop 136 std::vector<cvPEmdEdge> m_fromLoop; 137 std::vector<cvPEmdEdge> m_toLoop; 138 int m_iFrom; 139 int m_iTo; 140 }; 141
