Some small documentation updates
[libdai.git] / examples / example_imagesegmentation.cpp
1 /* This file is part of libDAI - http://www.libdai.org/
2 *
3 * libDAI is licensed under the terms of the GNU General Public License version
4 * 2, or (at your option) any later version. libDAI is distributed without any
5 * warranty. See the file COPYING for more details.
6 *
7 * Copyright (C) 2006-2010 Joris Mooij [joris dot mooij at libdai dot org]
8 * Copyright (C) 2006-2007 Radboud University Nijmegen, The Netherlands
9 */
10
11
12 #include <iostream>
13 #include <dai/alldai.h> // Include main libDAI header file
14 #include <CImg.h> // This example needs a recent version of CImg to be installed
15
16
17 // For backwards compatibility with old CImg interface
18 // #define CIMGOLD
19
20
21 using namespace dai;
22 using namespace std;
23 using namespace cimg_library;
24
25
26 /// Converts an image into a FactorGraph as described in section 1.1.3 of [\ref Moo08]
27 /** The grayscale pixel values of the image are transformed by a nonlinear transformation
28 into the local fields for each binary Ising variable, and the pairwise interactions
29 are uniform.
30 \param img The input image (should be grayscale, with 0 corresponding to background
31 and 255 corresponding to foreground)
32 \param J The pairwise interaction strength (should be positive for smoothing)
33 \param th_min Minimal value of local field strength (corresponding to background)
34 \param th_max Maximal value of local field strength (corresponding to foreground)
35 \param scale Typical difference in pixel values between fore- and background
36 \param pbg Probability that a pixel belongs to the background (in percent)
37 \param evidence The local evidence (represented as a grayscale image)
38 **/
39 template<class T>
40 FactorGraph img2fg( const CImg<T> &img, double J, double th_min, double th_max, double scale, double pbg, CImg<unsigned char> &evidence ) {
41 vector<Var> vars;
42 vector<Factor> factors;
43
44 #ifdef CIMGOLD
45 size_t dimx = img.width; // Width of the image in pixels
46 size_t dimy = img.height; // Height of the image in pixels
47 #else
48 size_t dimx = img.width(); // Width of the image in pixels
49 size_t dimy = img.height(); // Height of the image in pixels
50 #endif
51 size_t N = dimx * dimy; // One variable for each pixel
52
53 // Create variables
54 cout << " Image width: " << dimx << endl;
55 cout << " Image height: " << dimy << endl;
56 cout << " Pairwise interaction strength: " << J << endl;
57 cout << " Minimal local evidence strength: " << th_min << endl;
58 cout << " Maximal local evidence strength: " << th_max << endl;
59 cout << " Scale of pixel values: " << scale << endl;
60 cout << " Percentage of background: " << pbg << endl;
61 cout << " Creating " << N << " variables..." << endl;
62 // Reserve memory for the variables
63 vars.reserve( N );
64 // Create a binary variable for each pixel
65 for( size_t i = 0; i < N; i++ )
66 vars.push_back( Var( i, 2 ) );
67
68 // Build image histogram
69 CImg<float> hist = img.get_channel( 0 ).get_histogram( 256, 0, 255 );
70 size_t cum_hist = 0;
71
72 // Find the critical level which corresponds with the seperation
73 // between foreground and background, assuming that the percentage
74 // of pixels in the image that belong to the background is pbg
75 size_t level = 0;
76 for( level = 0; level < 256; level++ ) {
77 cum_hist += (size_t)hist(level);
78 if( cum_hist > pbg * dimx * dimy / 100.0 )
79 break;
80 }
81
82 // Create factors
83 cout << " Creating " << (3 * N - dimx - dimy) << " factors..." << endl;
84 // Reserve memory for the factors
85 factors.reserve( 3 * N - dimx - dimy );
86 // th_avg is the local field strength that would correspond with pixel value level
87 // th_width is the width of the local field strength range
88 double th_avg = (th_min + th_max) / 2.0;
89 double th_width = (th_max - th_min) / 2.0;
90 // For each pixel
91 for( size_t i = 0; i < dimx; i++ )
92 for( size_t j = 0; j < dimy; j++ ) {
93 // Add a pairwise interaction with the left neighboring pixel
94 if( i >= 1 )
95 factors.push_back( createFactorIsing( vars[i*dimy+j], vars[(i-1)*dimy+j], J ) );
96 // Add a pairwise interaction with the upper neighboring pixel
97 if( j >= 1 )
98 factors.push_back( createFactorIsing( vars[i*dimy+j], vars[i*dimy+(j-1)], J ) );
99 // Get the pixel value
100 double x = img(i,j);
101 // Apply the nonlinear transformation to get the local field strength
102 double th = th_avg + th_width * tanh( (x - level) / scale );
103 // Add a single-variable interaction with strength th
104 factors.push_back( createFactorIsing( vars[i*dimy+j], th ) );
105
106 // For visualization, we calculate a grayscale level corresponding to the local field strength
107 unsigned char g = (unsigned char)((tanh(th) + 1.0) / 2.0 * 255.0);
108 // and store it in the evidence image
109 if( g > 127 ) {
110 evidence(i,j,0) = 255;
111 evidence(i,j,1) = 2 * (g - 127);
112 evidence(i,j,2) = 2 * (g - 127);
113 } else {
114 evidence(i,j,0) = 0;
115 evidence(i,j,1) = 0;
116 evidence(i,j,2) = 2*g;
117 }
118 }
119
120 // Create the factor graph out of the variables and factors
121 cout << "Creating the factor graph..." << endl;
122 return FactorGraph( factors.begin(), factors.end(), vars.begin(), vars.end(), factors.size(), vars.size() );
123 }
124
125
126 /// Perform an inference algorithm on a factorgraph, and visualize intermediate beliefs
127 /** \param fg The factorgraph (should have only binary variables)
128 * \param algOpts String specifying the inference algorithm and its options in the format "NAME[key1=val1,key2=val2,...,keyn=valn]"
129 * \param maxIter Maximum number of iterations to perform
130 * \param tol Convergence tolerance
131 * \param m Final magnetizations
132 * \param dimx Image width
133 * \param dimy Image height
134 * \param disp Handle for displaying the intermediate beliefs
135 */
136 double doInference( FactorGraph& fg, string algOpts, size_t maxIter, double tol, vector<double> &m, size_t dimx, size_t dimy, CImgDisplay &disp ) {
137 // Construct inference algorithm
138 cout << "Inference algorithm: " << algOpts << endl;
139 cout << "Constructing inference algorithm object..." << endl;
140 InfAlg* ia = newInfAlgFromString( algOpts, fg );
141
142 // Initialize inference algorithm
143 cout << "Initializing inference algorithm..." << endl;
144 ia->init();
145
146 // Initialize vector for storing the magnetizations
147 m = vector<double>( fg.nrVars(), 0.0 );
148
149 // Construct an image that will hold the intermediate single-variable beliefs
150 CImg<unsigned char> image( dimx, dimy, 1, 3 );
151
152 // maxDiff stores the current convergence level
153 double maxDiff = 1.0;
154
155 // Iterate while maximum number of iterations has not been
156 // reached and requested convergence level has not been reached
157 cout << "Starting inference algorithm..." << endl;
158 for( size_t iter = 0; iter < maxIter && maxDiff > tol; iter++ ) {
159 // Set magnetizations to beliefs
160 for( size_t i = 0; i < fg.nrVars(); i++ )
161 m[i] = ia->beliefV(i)[1] - ia->beliefV(i)[0];
162
163 // For each pixel, calculate a color coded magnetization
164 // and store it in the image for visualization
165 for( size_t i = 0; i < dimx; i++ )
166 for( size_t j = 0; j < dimy; j++ ) {
167 unsigned char g = (unsigned char)((m[i*dimy+j] + 1.0) / 2.0 * 255.0);
168 if( g > 127 ) {
169 image(i,j,0) = 255;
170 image(i,j,1) = 2 * (g - 127);
171 image(i,j,2) = 2 * (g - 127);
172 } else {
173 image(i,j,0) = 0;
174 image(i,j,1) = 0;
175 image(i,j,2) = 2*g;
176 }
177 }
178
179 // Display the image with the current beliefs
180 #ifdef CIMGOLD
181 disp << image;
182 #else
183 disp = image;
184 #endif
185
186 // Perform the requested inference algorithm
187 // (which could be limited to perform only 1 iteration)
188 maxDiff = ia->run();
189
190 // Output progress
191 cout << " Iterations = " << iter << ", maxDiff = " << maxDiff << endl;
192 }
193 cout << "Finished inference algorithm" << endl;
194
195 // Clean up inference algorithm
196 delete ia;
197
198 // Return reached convergence level
199 return maxDiff;
200 }
201
202
203 /// Main program
204 /** This example shows how one can use approximate inference in factor graphs
205 * on a simple vision task: given two images, identify smooth regions where these
206 * two images differ more than some threshold. This can be used to seperate
207 * foreground from background if one image contains the background and the other
208 * one the combination of background and foreground.
209 */
210 int main(int argc,char **argv) {
211 cout << "This program is part of libDAI - http://www.libdai.org/" << endl;
212 cout << "(Use the option -h for getting help with the command line arguments.)" << endl;
213 // Display program usage, when invoked from the command line with option '-h'
214 cimg_usage( "This example shows how libDAI can be used for a simple image segmentation task" );
215 // Get command line arguments
216 const char* file_i1 = cimg_option( "-i1", "example_img_in1.jpg", "Input image 1" );
217 const char* file_i2 = cimg_option( "-i2", "example_img_in2.jpg", "Input image 2" );
218 const char* file_o1 = cimg_option( "-o1", "example_img_out1.jpg", "Output image (local evidence)" );
219 const char* file_o2 = cimg_option( "-o2", "example_img_out2.jpg", "Output image (magnetizations)" );
220 const double J = cimg_option( "-J", 2.4, "Pairwise interaction strength (i.e., smoothing strength)" );
221 const double th_min = cimg_option( "-thmin", -3.0, "Local evidence strength of background" );
222 const double th_max = cimg_option( "-thmax", 3.2, "Local evidence strength of foreground" );
223 const double scale = cimg_option( "-scale", 40.0, "Typical difference in pixel values between fore- and background" );
224 const double pbg = cimg_option( "-pbg", 90.0, "Percentage of background in image" );
225 const char *infname = cimg_option( "-method", "BP[updates=SEQMAX,maxiter=1,tol=1e-9,logdomain=0]", "Inference method in format name[key1=val1,...,keyn=valn]" );
226 const size_t maxiter = cimg_option( "-maxiter", 100, "Maximum number of iterations for inference method" );
227 const double tol = cimg_option( "-tol", 1e-9, "Desired tolerance level for inference method" );
228 const char *file_fg = cimg_option( "-fg", "", "Output factor graph" );
229
230 // Read input images
231 cout << endl;
232 cout << "Reading input image 1 (" << file_i1 << ")..." << endl;
233 CImg<unsigned char> image1 = CImg<>( file_i1 );
234 cout << "Reading input image 2 (" << file_i2 << ")..." << endl;
235 CImg<unsigned char> image2 = CImg<>( file_i2 );
236
237 // Check image sizes
238 #ifdef CIMGOLD
239 if( (image1.width != image2.width) || (image1.height != image2.height) )
240 cerr << "Error: input images should have same size." << endl;
241 size_t dimx = image1.width;
242 size_t dimy = image1.height;
243 #else
244 if( (image1.width() != image2.width()) || (image1.height() != image2.height()) )
245 cerr << "Error: input images should have same size." << endl;
246 size_t dimx = image1.width();
247 size_t dimy = image1.height();
248 #endif
249
250 // Display input images
251 cout << "Displaying input image 1..." << endl;
252 CImgDisplay disp1( image1, "Input image 1", 0 );
253 cout << "Displaying input image 2..." << endl;
254 CImgDisplay disp2( image2, "Input image 2", 0 );
255
256 // Construct absolute difference image
257 cout << "Constructing difference image..." << endl;
258 CImg<int> image3( image1 );
259 image3 -= image2;
260 image3.abs();
261 // Normalize difference image
262 image3.norm( 1 ); // 1 = L1, 2 = L2, -1 = Linf
263
264 // Normalize the difference by the average value of the background image
265 for( size_t i = 0; i < dimx; i++ ) {
266 for( size_t j = 0; j < dimy; j++ ) {
267 int avg = 0;
268 #ifdef CIMGOLD
269 for( int c = 0; c < image1.dimv(); c++ )
270 avg += image1( i, j, c );
271 avg /= image1.dimv();
272 #else
273 for( int c = 0; c < image1.spectrum(); c++ )
274 avg += image1( i, j, c );
275 avg /= image1.spectrum();
276 #endif
277 image3( i, j, 0 ) /= (1.0 + avg / 255.0);
278 }
279 }
280 image3.normalize( 0, 255 );
281
282 // Display difference image
283 cout << "Displaying difference image..." << endl;
284 CImgDisplay disp3( image3, "Relative difference of both inputs", 0 );
285
286 // Convert difference image into a factor graph and store
287 // the local evidence in image4 for visualization
288 CImg<unsigned char> image4( dimx, dimy, 1, 3 );
289 cout << "Converting difference image into factor graph..." << endl;
290 FactorGraph fg = img2fg( image3, J, th_min, th_max, scale, pbg, image4 );
291
292 // Display local evidence
293 cout << "Displaying local evidence..." << endl;
294 CImgDisplay disp4( image4, "Local evidence", 0 );
295 cout << "Saving local evidence as JPEG in " << file_o1 << endl;
296 image4.save_jpeg( file_o1, 100 );
297 if( strlen( file_fg ) > 0 ) {
298 cout << "Saving factor graph as " << file_fg << endl;
299 fg.WriteToFile( file_fg );
300 }
301
302 // Solve the inference problem and visualize intermediate steps
303 CImgDisplay disp5( dimx, dimy, "Beliefs during inference", 0 );
304 vector<double> m; // Stores the final magnetizations
305 cout << "Solving the inference problem...please be patient!" << endl;
306 doInference( fg, infname, maxiter, tol, m, dimx, dimy, disp5 );
307
308 // Visualize the final magnetizations
309 for( size_t i = 0; i < dimx; i++ )
310 for( size_t j = 0; j < dimy; j++ ) {
311 unsigned char g = (unsigned char)((m[i*dimy+j] + 1.0) / 2.0 * 255.0);
312 if( g > 127 ) {
313 image4(i,j,0) = image2(i,j,0);
314 image4(i,j,1) = image2(i,j,1);
315 image4(i,j,2) = image2(i,j,2);
316 } else
317 #ifdef CIMGOLD
318 for( size_t c = 0; c < (size_t)image4.dimv(); c++ )
319 image4(i,j,c) = 255;
320 #else
321 for( size_t c = 0; c < (size_t)image4.spectrum(); c++ )
322 image4(i,j,c) = 255;
323 #endif
324 }
325 cout << "Displaying the final result of the segmentation problem..." << endl;
326 CImgDisplay main_disp( image4, "Foreground/background segmentation result", 0 );
327
328 cout << "Saving the final result of the segmentation problem as JPEG in " << file_o2 << endl;
329 image4.save_jpeg( file_o2, 100 );
330
331 cout << "Close the last image display in order to finish." << endl;
332 #ifdef CIMGOLD
333 while( !main_disp.is_closed )
334 cimg::wait( 40 );
335 #else
336 while( !main_disp.is_closed() )
337 cimg::wait( 40 );
338 #endif
339
340 return 0;
341 }