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, Intel Corporation, all rights reserved. 14793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Copyright (C) 2013, OpenCV Foundation, 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 "precomp.hpp" 44793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 45793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler/****************************************************************************************\ 46793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler* Watershed * 47793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler\****************************************************************************************/ 48793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 49793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslernamespace cv 50793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler{ 51793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// A node represents a pixel to label 52793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstruct WSNode 53793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler{ 54793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int next; 55793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int mask_ofs; 56793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int img_ofs; 57793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler}; 58793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 59793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler// Queue for WSNodes 60793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstruct WSQueue 61793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler{ 62793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler WSQueue() { first = last = 0; } 63793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int first, last; 64793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler}; 65793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 66793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 67793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslerstatic int 68793ee12c6df9cad3806238d32528c49a3ff9331dNoah PreslerallocWSNodes( std::vector<WSNode>& storage ) 69793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler{ 70793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int sz = (int)storage.size(); 71793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int newsz = MAX(128, sz*3/2); 72793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 73793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler storage.resize(newsz); 74793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( sz == 0 ) 75793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 76793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler storage[0].next = 0; 77793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler sz = 1; 78793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 79793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( int i = sz; i < newsz-1; i++ ) 80793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler storage[i].next = i+1; 81793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler storage[newsz-1].next = 0; 82793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler return sz; 83793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 84793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 85793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 86793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 87793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 88793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslervoid cv::watershed( InputArray _src, InputOutputArray _markers ) 89793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler{ 90793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Labels for pixels 91793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int IN_QUEUE = -2; // Pixel visited 92793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int WSHED = -1; // Pixel belongs to watershed 93793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 94793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // possible bit values = 2^8 95793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int NQ = 256; 96793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 97793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler Mat src = _src.getMat(), dst = _markers.getMat(); 98793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler Size size = src.size(); 99793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 100793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Vector of every created node 101793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler std::vector<WSNode> storage; 102793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int free_node = 0, node; 103793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Priority queue of queues of nodes 104793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // from high priority (0) to low priority (255) 105793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler WSQueue q[NQ]; 106793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Non-empty queue with highest priority 107793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int active_queue; 108793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int i, j; 109793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Color differences 110793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int db, dg, dr; 111793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int subs_tab[513]; 112793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 113793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // MAX(a,b) = b + MAX(a-b,0) 114793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler #define ws_max(a,b) ((b) + subs_tab[(a)-(b)+NQ]) 115793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // MIN(a,b) = a - MAX(a-b,0) 116793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler #define ws_min(a,b) ((a) - subs_tab[(a)-(b)+NQ]) 117793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 118793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Create a new node with offsets mofs and iofs in queue idx 119793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler #define ws_push(idx,mofs,iofs) \ 120793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { \ 121793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( !free_node ) \ 122793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler free_node = allocWSNodes( storage );\ 123793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler node = free_node; \ 124793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler free_node = storage[free_node].next;\ 125793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler storage[node].next = 0; \ 126793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler storage[node].mask_ofs = mofs; \ 127793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler storage[node].img_ofs = iofs; \ 128793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( q[idx].last ) \ 129793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler storage[q[idx].last].next=node; \ 130793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler else \ 131793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler q[idx].first = node; \ 132793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler q[idx].last = node; \ 133793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 134793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 135793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Get next node from queue idx 136793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler #define ws_pop(idx,mofs,iofs) \ 137793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { \ 138793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler node = q[idx].first; \ 139793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler q[idx].first = storage[node].next; \ 140793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( !storage[node].next ) \ 141793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler q[idx].last = 0; \ 142793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler storage[node].next = free_node; \ 143793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler free_node = node; \ 144793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mofs = storage[node].mask_ofs; \ 145793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler iofs = storage[node].img_ofs; \ 146793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 147793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 148793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Get highest absolute channel difference in diff 149793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler #define c_diff(ptr1,ptr2,diff) \ 150793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { \ 151793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler db = std::abs((ptr1)[0] - (ptr2)[0]);\ 152793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler dg = std::abs((ptr1)[1] - (ptr2)[1]);\ 153793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler dr = std::abs((ptr1)[2] - (ptr2)[2]);\ 154793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler diff = ws_max(db,dg); \ 155793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler diff = ws_max(diff,dr); \ 156793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler assert( 0 <= diff && diff <= 255 ); \ 157793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 158793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 159793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler CV_Assert( src.type() == CV_8UC3 && dst.type() == CV_32SC1 ); 160793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler CV_Assert( src.size() == dst.size() ); 161793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 162793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Current pixel in input image 163793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const uchar* img = src.ptr(); 164793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Step size to next row in input image 165793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int istep = int(src.step/sizeof(img[0])); 166793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 167793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Current pixel in mask image 168793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int* mask = dst.ptr<int>(); 169793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Step size to next row in mask image 170793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int mstep = int(dst.step / sizeof(mask[0])); 171793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 172793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( i = 0; i < 256; i++ ) 173793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler subs_tab[i] = 0; 174793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( i = 256; i <= 512; i++ ) 175793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler subs_tab[i] = i - 256; 176793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 177793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // draw a pixel-wide border of dummy "watershed" (i.e. boundary) pixels 178793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( j = 0; j < size.width; j++ ) 179793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mask[j] = mask[j + mstep*(size.height-1)] = WSHED; 180793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 181793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // initial phase: put all the neighbor pixels of each marker to the ordered queue - 182793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // determine the initial boundaries of the basins 183793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( i = 1; i < size.height-1; i++ ) 184793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 185793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler img += istep; mask += mstep; 186793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mask[0] = mask[size.width-1] = WSHED; // boundary pixels 187793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 188793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( j = 1; j < size.width-1; j++ ) 189793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 190793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int* m = mask + j; 191793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( m[0] < 0 ) m[0] = 0; 192793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( m[0] == 0 && (m[-1] > 0 || m[1] > 0 || m[-mstep] > 0 || m[mstep] > 0) ) 193793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 194793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Find smallest difference to adjacent markers 195793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const uchar* ptr = img + j*3; 196793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int idx = 256, t; 197793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( m[-1] > 0 ) 198793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler c_diff( ptr, ptr - 3, idx ); 199793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( m[1] > 0 ) 200793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 201793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler c_diff( ptr, ptr + 3, t ); 202793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler idx = ws_min( idx, t ); 203793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 204793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( m[-mstep] > 0 ) 205793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 206793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler c_diff( ptr, ptr - istep, t ); 207793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler idx = ws_min( idx, t ); 208793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 209793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( m[mstep] > 0 ) 210793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 211793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler c_diff( ptr, ptr + istep, t ); 212793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler idx = ws_min( idx, t ); 213793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 214793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 215793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Add to according queue 216793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler assert( 0 <= idx && idx <= 255 ); 217793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler ws_push( idx, i*mstep + j, i*istep + j*3 ); 218793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler m[0] = IN_QUEUE; 219793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 220793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 221793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 222793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 223793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // find the first non-empty queue 224793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( i = 0; i < NQ; i++ ) 225793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( q[i].first ) 226793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler break; 227793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 228793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // if there is no markers, exit immediately 229793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( i == NQ ) 230793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler return; 231793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 232793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler active_queue = i; 233793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler img = src.ptr(); 234793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mask = dst.ptr<int>(); 235793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 236793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // recursively fill the basins 237793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for(;;) 238793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 239793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int mofs, iofs; 240793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int lab = 0, t; 241793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int* m; 242793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const uchar* ptr; 243793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 244793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Get non-empty queue with highest priority 245793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Exit condition: empty priority queue 246793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( q[active_queue].first == 0 ) 247793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 248793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( i = active_queue+1; i < NQ; i++ ) 249793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( q[i].first ) 250793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler break; 251793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( i == NQ ) 252793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler break; 253793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler active_queue = i; 254793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 255793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 256793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Get next node 257793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler ws_pop( active_queue, mofs, iofs ); 258793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 259793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Calculate pointer to current pixel in input and marker image 260793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler m = mask + mofs; 261793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler ptr = img + iofs; 262793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 263793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Check surrounding pixels for labels 264793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // to determine label for current pixel 265793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler t = m[-1]; // Left 266793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( t > 0 ) lab = t; 267793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler t = m[1]; // Right 268793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( t > 0 ) 269793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 270793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( lab == 0 ) lab = t; 271793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler else if( t != lab ) lab = WSHED; 272793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 273793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler t = m[-mstep]; // Top 274793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( t > 0 ) 275793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 276793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( lab == 0 ) lab = t; 277793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler else if( t != lab ) lab = WSHED; 278793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 279793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler t = m[mstep]; // Bottom 280793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( t > 0 ) 281793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 282793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( lab == 0 ) lab = t; 283793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler else if( t != lab ) lab = WSHED; 284793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 285793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 286793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Set label to current pixel in marker image 287793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler assert( lab != 0 ); 288793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler m[0] = lab; 289793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 290793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( lab == WSHED ) 291793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler continue; 292793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 293793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // Add adjacent, unlabeled pixels to corresponding queue 294793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( m[-1] == 0 ) 295793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 296793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler c_diff( ptr, ptr - 3, t ); 297793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler ws_push( t, mofs - 1, iofs - 3 ); 298793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler active_queue = ws_min( active_queue, t ); 299793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler m[-1] = IN_QUEUE; 300793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 301793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( m[1] == 0 ) 302793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 303793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler c_diff( ptr, ptr + 3, t ); 304793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler ws_push( t, mofs + 1, iofs + 3 ); 305793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler active_queue = ws_min( active_queue, t ); 306793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler m[1] = IN_QUEUE; 307793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 308793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( m[-mstep] == 0 ) 309793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 310793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler c_diff( ptr, ptr - istep, t ); 311793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler ws_push( t, mofs - mstep, iofs - istep ); 312793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler active_queue = ws_min( active_queue, t ); 313793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler m[-mstep] = IN_QUEUE; 314793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 315793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( m[mstep] == 0 ) 316793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 317793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler c_diff( ptr, ptr + istep, t ); 318793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler ws_push( t, mofs + mstep, iofs + istep ); 319793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler active_queue = ws_min( active_queue, t ); 320793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler m[mstep] = IN_QUEUE; 321793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 322793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 323793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 324793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 325793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 326793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler/****************************************************************************************\ 327793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler* Meanshift * 328793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler\****************************************************************************************/ 329793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 330793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 331793ee12c6df9cad3806238d32528c49a3ff9331dNoah Preslervoid cv::pyrMeanShiftFiltering( InputArray _src, OutputArray _dst, 332793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler double sp0, double sr, int max_level, 333793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler TermCriteria termcrit ) 334793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler{ 335793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler Mat src0 = _src.getMat(); 336793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 337793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( src0.empty() ) 338793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler return; 339793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 340793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler _dst.create( src0.size(), src0.type() ); 341793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler Mat dst0 = _dst.getMat(); 342793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 343793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int cn = 3; 344793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const int MAX_LEVELS = 8; 345793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 346793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( (unsigned)max_level > (unsigned)MAX_LEVELS ) 347793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler CV_Error( CV_StsOutOfRange, "The number of pyramid levels is too large or negative" ); 348793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 349793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler std::vector<cv::Mat> src_pyramid(max_level+1); 350793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler std::vector<cv::Mat> dst_pyramid(max_level+1); 351793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cv::Mat mask0; 352793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int i, j, level; 353793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler //uchar* submask = 0; 354793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 355793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler #define cdiff(ofs0) (tab[c0-dptr[ofs0]+255] + \ 356793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler tab[c1-dptr[(ofs0)+1]+255] + tab[c2-dptr[(ofs0)+2]+255] >= isr22) 357793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 358793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler double sr2 = sr * sr; 359793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int isr2 = cvRound(sr2), isr22 = MAX(isr2,16); 360793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int tab[768]; 361793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 362793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 363793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( src0.type() != CV_8UC3 ) 364793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler CV_Error( CV_StsUnsupportedFormat, "Only 8-bit, 3-channel images are supported" ); 365793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 366793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( src0.type() != dst0.type() ) 367793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler CV_Error( CV_StsUnmatchedFormats, "The input and output images must have the same type" ); 368793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 369793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( src0.size() != dst0.size() ) 370793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler CV_Error( CV_StsUnmatchedSizes, "The input and output images must have the same size" ); 371793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 372793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( !(termcrit.type & CV_TERMCRIT_ITER) ) 373793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler termcrit.maxCount = 5; 374793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler termcrit.maxCount = MAX(termcrit.maxCount,1); 375793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler termcrit.maxCount = MIN(termcrit.maxCount,100); 376793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( !(termcrit.type & CV_TERMCRIT_EPS) ) 377793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler termcrit.epsilon = 1.f; 378793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler termcrit.epsilon = MAX(termcrit.epsilon, 0.f); 379793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 380793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( i = 0; i < 768; i++ ) 381793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler tab[i] = (i - 255)*(i - 255); 382793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 383793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // 1. construct pyramid 384793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler src_pyramid[0] = src0; 385793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler dst_pyramid[0] = dst0; 386793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( level = 1; level <= max_level; level++ ) 387793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 388793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler src_pyramid[level].create( (src_pyramid[level-1].rows+1)/2, 389793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler (src_pyramid[level-1].cols+1)/2, src_pyramid[level-1].type() ); 390793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler dst_pyramid[level].create( src_pyramid[level].rows, 391793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler src_pyramid[level].cols, src_pyramid[level].type() ); 392793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cv::pyrDown( src_pyramid[level-1], src_pyramid[level], src_pyramid[level].size() ); 393793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler //CV_CALL( cvResize( src_pyramid[level-1], src_pyramid[level], CV_INTER_AREA )); 394793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 395793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 396793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mask0.create(src0.rows, src0.cols, CV_8UC1); 397793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler //CV_CALL( submask = (uchar*)cvAlloc( (sp+2)*(sp+2) )); 398793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 399793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // 2. apply meanshift, starting from the pyramid top (i.e. the smallest layer) 400793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( level = max_level; level >= 0; level-- ) 401793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 402793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cv::Mat src = src_pyramid[level]; 403793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cv::Size size = src.size(); 404793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const uchar* sptr = src.ptr(); 405793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int sstep = (int)src.step; 406793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler uchar* mask = 0; 407793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int mstep = 0; 408793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler uchar* dptr; 409793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int dstep; 410793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler float sp = (float)(sp0 / (1 << level)); 411793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler sp = MAX( sp, 1 ); 412793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 413793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( level < max_level ) 414793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 415793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cv::Size size1 = dst_pyramid[level+1].size(); 416793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cv::Mat m( size.height, size.width, CV_8UC1, mask0.ptr() ); 417793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler dstep = (int)dst_pyramid[level+1].step; 418793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler dptr = dst_pyramid[level+1].ptr() + dstep + cn; 419793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mstep = (int)m.step; 420793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mask = m.ptr() + mstep; 421793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler //cvResize( dst_pyramid[level+1], dst_pyramid[level], CV_INTER_CUBIC ); 422793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cv::pyrUp( dst_pyramid[level+1], dst_pyramid[level], dst_pyramid[level].size() ); 423793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler m.setTo(cv::Scalar::all(0)); 424793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 425793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( i = 1; i < size1.height-1; i++, dptr += dstep - (size1.width-2)*3, mask += mstep*2 ) 426793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 427793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( j = 1; j < size1.width-1; j++, dptr += cn ) 428793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 429793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int c0 = dptr[0], c1 = dptr[1], c2 = dptr[2]; 430793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mask[j*2 - 1] = cdiff(-3) || cdiff(3) || cdiff(-dstep-3) || cdiff(-dstep) || 431793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cdiff(-dstep+3) || cdiff(dstep-3) || cdiff(dstep) || cdiff(dstep+3); 432793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 433793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 434793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 435793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cv::dilate( m, m, cv::Mat() ); 436793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mask = m.ptr(); 437793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 438793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 439793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler dptr = dst_pyramid[level].ptr(); 440793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler dstep = (int)dst_pyramid[level].step; 441793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 442793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( i = 0; i < size.height; i++, sptr += sstep - size.width*3, 443793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler dptr += dstep - size.width*3, 444793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler mask += mstep ) 445793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 446793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( j = 0; j < size.width; j++, sptr += 3, dptr += 3 ) 447793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 448793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int x0 = j, y0 = i, x1, y1, iter; 449793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int c0, c1, c2; 450793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 451793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( mask && !mask[j] ) 452793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler continue; 453793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 454793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler c0 = sptr[0], c1 = sptr[1], c2 = sptr[2]; 455793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 456793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler // iterate meanshift procedure 457793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( iter = 0; iter < termcrit.maxCount; iter++ ) 458793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 459793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const uchar* ptr; 460793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int x, y, count = 0; 461793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int minx, miny, maxx, maxy; 462793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int s0 = 0, s1 = 0, s2 = 0, sx = 0, sy = 0; 463793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler double icount; 464793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int stop_flag; 465793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 466793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler //mean shift: process pixels in window (p-sigmaSp)x(p+sigmaSp) 467793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler minx = cvRound(x0 - sp); minx = MAX(minx, 0); 468793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler miny = cvRound(y0 - sp); miny = MAX(miny, 0); 469793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler maxx = cvRound(x0 + sp); maxx = MIN(maxx, size.width-1); 470793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler maxy = cvRound(y0 + sp); maxy = MIN(maxy, size.height-1); 471793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler ptr = sptr + (miny - i)*sstep + (minx - j)*3; 472793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 473793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( y = miny; y <= maxy; y++, ptr += sstep - (maxx-minx+1)*3 ) 474793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 475793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int row_count = 0; 476793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler x = minx; 477793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler #if CV_ENABLE_UNROLLED 478793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( ; x + 3 <= maxx; x += 4, ptr += 12 ) 479793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 480793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int t0 = ptr[0], t1 = ptr[1], t2 = ptr[2]; 481793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( tab[t0-c0+255] + tab[t1-c1+255] + tab[t2-c2+255] <= isr2 ) 482793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 483793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler s0 += t0; s1 += t1; s2 += t2; 484793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler sx += x; row_count++; 485793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 486793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler t0 = ptr[3], t1 = ptr[4], t2 = ptr[5]; 487793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( tab[t0-c0+255] + tab[t1-c1+255] + tab[t2-c2+255] <= isr2 ) 488793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 489793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler s0 += t0; s1 += t1; s2 += t2; 490793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler sx += x+1; row_count++; 491793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 492793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler t0 = ptr[6], t1 = ptr[7], t2 = ptr[8]; 493793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( tab[t0-c0+255] + tab[t1-c1+255] + tab[t2-c2+255] <= isr2 ) 494793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 495793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler s0 += t0; s1 += t1; s2 += t2; 496793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler sx += x+2; row_count++; 497793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 498793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler t0 = ptr[9], t1 = ptr[10], t2 = ptr[11]; 499793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( tab[t0-c0+255] + tab[t1-c1+255] + tab[t2-c2+255] <= isr2 ) 500793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 501793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler s0 += t0; s1 += t1; s2 += t2; 502793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler sx += x+3; row_count++; 503793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 504793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 505793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler #endif 506793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler for( ; x <= maxx; x++, ptr += 3 ) 507793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 508793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler int t0 = ptr[0], t1 = ptr[1], t2 = ptr[2]; 509793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( tab[t0-c0+255] + tab[t1-c1+255] + tab[t2-c2+255] <= isr2 ) 510793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler { 511793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler s0 += t0; s1 += t1; s2 += t2; 512793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler sx += x; row_count++; 513793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 514793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 515793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler count += row_count; 516793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler sy += y*row_count; 517793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 518793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 519793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( count == 0 ) 520793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler break; 521793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 522793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler icount = 1./count; 523793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler x1 = cvRound(sx*icount); 524793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler y1 = cvRound(sy*icount); 525793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler s0 = cvRound(s0*icount); 526793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler s1 = cvRound(s1*icount); 527793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler s2 = cvRound(s2*icount); 528793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 529793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler stop_flag = (x0 == x1 && y0 == y1) || std::abs(x1-x0) + std::abs(y1-y0) + 530793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler tab[s0 - c0 + 255] + tab[s1 - c1 + 255] + 531793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler tab[s2 - c2 + 255] <= termcrit.epsilon; 532793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 533793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler x0 = x1; y0 = y1; 534793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler c0 = s0; c1 = s1; c2 = s2; 535793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 536793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler if( stop_flag ) 537793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler break; 538793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 539793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 540793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler dptr[0] = (uchar)c0; 541793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler dptr[1] = (uchar)c1; 542793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler dptr[2] = (uchar)c2; 543793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 544793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 545793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler } 546793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 547793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 548793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 549793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler/////////////////////////////////////////////////////////////////////////////////////////////// 550793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 551793ee12c6df9cad3806238d32528c49a3ff9331dNoah PreslerCV_IMPL void cvWatershed( const CvArr* _src, CvArr* _markers ) 552793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler{ 553793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cv::Mat src = cv::cvarrToMat(_src), markers = cv::cvarrToMat(_markers); 554793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cv::watershed(src, markers); 555793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 556793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 557793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 558793ee12c6df9cad3806238d32528c49a3ff9331dNoah PreslerCV_IMPL void 559793ee12c6df9cad3806238d32528c49a3ff9331dNoah PreslercvPyrMeanShiftFiltering( const CvArr* srcarr, CvArr* dstarr, 560793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler double sp0, double sr, int max_level, 561793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler CvTermCriteria termcrit ) 562793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler{ 563793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cv::Mat src = cv::cvarrToMat(srcarr); 564793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler const cv::Mat dst = cv::cvarrToMat(dstarr); 565793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler 566793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler cv::pyrMeanShiftFiltering(src, dst, sp0, sr, max_level, termcrit); 567793ee12c6df9cad3806238d32528c49a3ff9331dNoah Presler} 568