1793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler/*M/////////////////////////////////////////////////////////////////////////////////////// 2793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// 3793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// IMPORTANT: READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING. 4793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// 5793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// By downloading, copying, installing or using the software you agree to this license. 6793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// If you do not agree to this license, do not download, install, 7793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// copy or use the software. 8793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// 9793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// 10793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// License Agreement 11793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// For Open Source Computer Vision Library 12793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// 13793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Copyright (C) 2000-2008, Intel Corporation, all rights reserved. 14793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Copyright (C) 2009, Willow Garage Inc., all rights reserved. 15793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Third party copyrights are property of their respective owners. 16793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// 17793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Redistribution and use in source and binary forms, with or without modification, 18793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// are permitted provided that the following conditions are met: 19793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// 20793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// * Redistribution's of source code must retain the above copyright notice, 21793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// this list of conditions and the following disclaimer. 22793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// 23793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// * Redistribution's in binary form must reproduce the above copyright notice, 24793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// this list of conditions and the following disclaimer in the documentation 25793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// and/or other materials provided with the distribution. 26793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// 27793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// * The name of the copyright holders may not be used to endorse or promote products 28793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// derived from this software without specific prior written permission. 29793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// 30793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// This software is provided by the copyright holders and contributors "as is" and 31793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// any express or implied warranties, including, but not limited to, the implied 32793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// warranties of merchantability and fitness for a particular purpose are disclaimed. 33793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// In no event shall the Intel Corporation or contributors be liable for any direct, 34793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// indirect, incidental, special, exemplary, or consequential damages 35793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// (including, but not limited to, procurement of substitute goods or services; 36793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// loss of use, data, or profits; or business interruption) however caused 37793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// and on any theory of liability, whether in contract, strict liability, 38793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// or tort (including negligence or otherwise) arising in any way out of 39793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// the use of this software, even if advised of the possibility of such damage. 40793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// 41793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler//M*/ 42793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 43793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#include <stdlib.h> 44793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#include <math.h> 45793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler#include <vector> 46793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 47793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler/****************************************************************************************\ 48793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler* For EMDL1 Framework * 49793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler\****************************************************************************************/ 50793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslertypedef struct cvEMDEdge* cvPEmdEdge; 51793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslertypedef struct cvEMDNode* cvPEmdNode; 52793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstruct cvEMDNode 53793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler{ 54793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int pos[3]; // grid position 55793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler float d; // initial value 56793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int u; 57793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // tree maintainance 58793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int iLevel; // level in the tree, 0 means root 59793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cvPEmdNode pParent; // pointer to its parent 60793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cvPEmdEdge pChild; 61793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cvPEmdEdge pPEdge; // point to the edge coming out from its parent 62793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler}; 63793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstruct cvEMDEdge 64793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler{ 65793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler float flow; // initial value 66793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int iDir; // 1:outward, 0:inward 67793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // tree maintainance 68793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cvPEmdNode pParent; // point to its parent 69793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cvPEmdNode pChild; // the child node 70793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cvPEmdEdge pNxt; // next child/edge 71793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler}; 72793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslertypedef std::vector<cvEMDNode> cvEMDNodeArray; 73793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslertypedef std::vector<cvEMDEdge> cvEMDEdgeArray; 74793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslertypedef std::vector<cvEMDNodeArray> cvEMDNodeArray2D; 75793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslertypedef std::vector<cvEMDEdgeArray> cvEMDEdgeArray2D; 76793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslertypedef std::vector<float> floatArray; 77793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslertypedef std::vector<floatArray> floatArray2D; 78793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 79793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler/****************************************************************************************\ 80793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler* EMDL1 Class * 81793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler\****************************************************************************************/ 82793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerclass EmdL1 83793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler{ 84793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerpublic: 85793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler EmdL1() 86793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 87793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler m_pRoot = NULL; 88793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler binsDim1 = 0; 89793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler binsDim2 = 0; 90793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler binsDim3 = 0; 91793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler dimension = 0; 92793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler nMaxIt = 500; 93793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 94793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 95793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler ~EmdL1() 96793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 97793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 98793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 99793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler float getEMDL1(cv::Mat &sig1, cv::Mat &sig2); 100793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler void setMaxIteration(int _nMaxIt); 101793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 102793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerprivate: 103793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler //-- SubFunctions called in the EMD algorithm 104793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler bool initBaseTrees(int n1=0, int n2=0, int n3=0); 105793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler bool fillBaseTrees(float *H1, float *H2); 106793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler bool greedySolution(); 107793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler bool greedySolution2(); 108793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler bool greedySolution3(); 109793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler void initBVTree(); 110793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler void updateSubtree(cvPEmdNode pRoot); 111793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler bool isOptimal(); 112793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler void findNewSolution(); 113793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler void findLoopFromEnterBV(); 114793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler float compuTotalFlow(); 115793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 116793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerprivate: 117793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int dimension; 118793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int binsDim1, binsDim2, binsDim3; // the hitogram contains m_n1 rows and m_n2 columns 119793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int nNBV; // number of Non-Basic Variables (NBV) 120793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int nMaxIt; 121793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cvEMDNodeArray2D m_Nodes; // all nodes 122793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cvEMDEdgeArray2D m_EdgesRight; // all edges to right 123793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cvEMDEdgeArray2D m_EdgesUp; // all edges to upward 124793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler std::vector<cvEMDNodeArray2D> m_3dNodes; // all nodes for 3D 125793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler std::vector<cvEMDEdgeArray2D> m_3dEdgesRight; // all edges to right, 3D 126793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler std::vector<cvEMDEdgeArray2D> m_3dEdgesUp; // all edges to upward, 3D 127793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler std::vector<cvEMDEdgeArray2D> m_3dEdgesDeep; // all edges to deep, 3D 128793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler std::vector<cvPEmdEdge> m_NBVEdges; // pointers to all NON-BV edges 129793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler std::vector<cvPEmdNode> m_auxQueue; // auxiliary node queue 130793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cvPEmdNode m_pRoot; // root of the BV Tree 131793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cvPEmdEdge m_pEnter; // Enter BV edge 132793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int m_iEnter; // Enter BV edge, index in m_NBVEdges 133793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cvPEmdEdge m_pLeave; // Leave BV edge 134793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int m_nItr; // number of iteration 135793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // auxiliary variables for searching a new loop 136793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler std::vector<cvPEmdEdge> m_fromLoop; 137793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler std::vector<cvPEmdEdge> m_toLoop; 138793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int m_iFrom; 139793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int m_iTo; 140793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler}; 141