/ ------------------------------------------------------------------------ // This program is complementary material for the book: // // Frank Nielsen // // Visual Computing: Geometry, Graphics, and Vision // // ISBN: 1-58450-427-7 // // Charles River Media, Inc. // // // All programs are available at http://www.charlesriver.com/visualcomputing/ // // You may use this program for ACADEMIC and PERSONAL purposes ONLY. // // // The use of this program in a commercial product requires EXPLICITLY // written permission from the author. The author is NOT responsible or // liable for damage or loss that may be caused by the use of this program. // // Copyright (c) 2005. Frank Nielsen. All rights reserved. // ------------------------------------------------------------------------ // ------------------------------------------------------------------------ // File: srg.cpp // // Description: Statistical region growing segmentation using the union-find data structure // ----------- // Region growing based on statistical concentration inequalities // // Basic skeleton of the implementation of CVPR 2003 and TPAMI 2004 // Richard Nock and Frank Nielsen, "Statistical Region Merging", // IEEE Transactions on Pattern Analysis and Machine Intelligence, 2004. // // Frank Nielsen and Richard Nock, "On Region Merging: the Statistical Soundness of Fast Sorting, with Applications", // IEEE Computer Vision and Pattern Recognition 2003. // 1. Read PPM Image // 2. Sort by increasing order all pairs of adjacents pixels in 4-connectivity using max channel difference // 3. Do region growing using the statistical predicate // 4. Merge small regions (those having size less than 0.1% of image size) // 5. Draw white borders of regions // 6. Save PPM Image #define _WINDOWS #include "stdafx.h" #include #include // Union-Find Data Structure // See Tarjan, R. E. "Efficiency of a Good But Not Linear Set Union Algorithm," Journal of the ACM (JACM), 22(2), 215-225, 1975 class ggvUnionFind{ public: int *rank; int *parent; ggvUnionFind(int n) {int k; parent=new int[n]; rank=new int[n]; for (k = 0; k < n; k++) {parent[k] = k;rank[k] = 0; } } ~ggvUnionFind() {delete [] rank; delete [] parent;} // Find procedures int ggvUnionFind::Find(int k) { while (parent[k]!=k ) k=parent[k]; return k;} // Assume x and y being roots int ggvUnionFind::UnionRoot(int x, int y) { if ( x == y ) return -1; if (rank[x] > rank[y]) {parent[y]=x; return x;} else { parent[x]=y;if (rank[x]==rank[y]) rank[y]++;return y;} } }; // Portable pixelmap I/O // // P6 // width height // max // rgb (in binary) void SaveImagePPM(unsigned char * data, int w, int h, char * file) { //ifstream IN(file, ios::in); //if (IN) {cerr<<"File "<> w >> h; IN >> maxc; IN.get(dummy1); img=new unsigned char[3*w*h]; IN.read(img, 3*w*h); IN.close(); return img; } #include #define max3(a,b,c) max(max((a),(b)),(c)) #define max(A,B) ((A>B) ? (A):(B)) #define min(A,B) ((A (const ggvRmpair & rhs) {return (diff>rhs.diff);} }; // Sorting with buckets void BucketSort(ggvRmpair * &a, int n) { int i; int nbe[256], cnbe[256]; ggvRmpair *b; b=new ggvRmpair[n]; for(i=0;i<256;i++) nbe[i]=0; // class all elements according to their family for(i=0;iFind(index); // Get the index root // average color choice rastero[3*index] =(unsigned char)Ravg[indexb]; rastero[3*index+1] = (unsigned char)Gavg[indexb]; rastero[3*index+2] =(unsigned char)Bavg[indexb]; index++; } } // Merge small regions void ggvRm::MergeSmallRegion() { int i,j, C1,C2, index; index=0; for(i=0;iFind(index); C2=UF->Find(index-1); if (C2!=C1) {if ((N[C2]Find(index); C2=UF->Find(index-1-w); if (C2!=C1) { for(k=-borderthickness;k<=borderthickness;k++) for(l=-borderthickness;l<=borderthickness;l++) { index=(i+k)*w+(j+l); if ((index>=0)&&(indexUnionRoot(C1,C2); nreg=N[C1]+N[C2]; ravg=(N[C1]*Ravg[C1]+N[C2]*Ravg[C2])/nreg; gavg=(N[C1]*Gavg[C1]+N[C2]*Gavg[C2])/nreg; bavg=(N[C1]*Bavg[C1]+N[C2]*Bavg[C2])/nreg; N[reg]=nreg; Ravg[reg]=ravg; Gavg[reg]=gavg; Bavg[reg]=bavg; } // Region-growing segmentation framework int ggvRm::Segment() { int i,j,index; int reg1,reg2; ggvRmpair * order; int npair; int cpair=0; int C1,C2; // Consider C4-connectivity here npair=2*(w-1)*(h-1)+(h-1)+(w-1); order=new ggvRmpair[npair]; for(i=0;iFind(reg1); reg2=order[i].r2; C2=UF->Find(reg2); if ((C1!=C2)&&(MergePredicate(C1,C2))) MergeRegions(C1,C2); } delete [] order; return 1; } // Main program #include int main(int argc, char* argv[]) { int w, h; unsigned char *imgppm; char filenamein[256], filenameout[256]; ggvRm * seg; cout<<"Visual Computing: Geometry, Graphics, and Vision (ISBN:1-58450-427-7)"<ppm with XnView.)"<=2) sprintf(filenamein,argv[1]); else sprintf(filenamein,"srg-source.ppm"); if (argc>=3) sprintf(filenameout,argv[2]); else sprintf(filenameout,"srg-output.ppm"); imgppm=LoadImagePPM(filenamein, w, h); seg=new ggvRm(w,h,imgppm); seg->Segment(); seg->MergeSmallRegion(); // optional seg->OutputSegmentation(); // optional: write in the rastero buffer seg->DrawBorder(); // optional SaveImagePPM(seg->rastero,w,h,filenameout); cout<<"Press Return key"<