1
2 //=========================================================================================================//
3 //CAIR - Content Aware Image Resizer
4 //Copyright (C) 2009 Joseph Auman (brain.recall@gmail.com)
5
6 //=========================================================================================================//
7 //This library is free software; you can redistribute it and/or
8 //modify it under the terms of the GNU Lesser General Public
9 //License as published by the Free Software Foundation; either
10 //version 2.1 of the License, or (at your option) any later version.
11 //This library is distributed in the hope that it will be useful,
12 //but WITHOUT ANY WARRANTY; without even the implied warranty of
13 //MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 //Lesser General Public License for more details.
15 //You should have received a copy of the GNU Lesser General Public
16 //License along with this library; if not, write to the Free Software
17 //Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
18
19 //=========================================================================================================//
20 //This thing should hopefully perform the image resize method developed by Shai Avidan and Ariel Shamir.
21
22 //=========================================================================================================//
23 //TODO (maybe):
24 // - Try doing Poisson image reconstruction instead of the averaging technique in CAIR_HD() if I can figure it out (see the ReadMe).
25 // - Abstract out pthreads into macros allowing for multiple thread types to be used (ugh, not for a while at least)
26 // - Maybe someday push CAIR into OO land and create a class out of it (pff, OO is the devil!).
27
28 //=========================================================================================================//
29 //KNOWN BUGS:
30 // - The threading changes in v2.16 lost the reentrant capability of CAIR. (If this hits someone hard, let me know.)
31 // - The percent of completion for the CAIR_callback in CAIR_HD and CAIR_Removal is often wrong.
32
33 //=========================================================================================================//
34 //CHANGELOG:
35 //CAIR v2.19 Changelog:
36 // - Single-threaded Energy_Map(), which surprisingly gave a 35% speed boost. My attempts at multithreading this function became a bottleneck.
37 // If anyone has any idea on how to successfully multithread this algorithm, please let me know.
38 //CAIR v2.18 Changelog:
39 // - Overhauled my internal matrix handling for a 30% speed boost.
40 // - Complete overhaul of seam enlarging. CAIR now enlarges by the method intended in the paper. (Removed seams determine the added seams. See CAIR_Add())
41 // Because of this, the add_weight parameter is no longer needed.
42 // - Found and fixed a few boundary issues with the edge updates.
43 // - Fixed the non-standard void pointer usage with the thread IDs. (Special thanks to Peter Berrington)
44 // - Deprecated the Image Map functions until I can make something that doesn't suck.
45 //CAIR v2.17 Changelog:
46 // - Ditched vectors for dynamic arrays, for about a 15% performance boost.
47 // - Added some headers into CAIR_CML.h to fix some compiler errors with new versions of g++. (Special thanks to Alexandre Prokoudine)
48 // - Added CAIR_Threads(), which allows the ability to dynamically change the number of threads CAIR will use.
49 // NOTE: Don't ever call CAIR_Threads() while CAIR() is processing an image, unless you're a masochist.
50 // - Added CAIR_callback parameters to CAIR(), CAIR_Removal(), and CAIR_HD(). This function pointer will be called every cycle,
51 // passing the function the percent complete (0 to 1). If the function returns false, then the resize is canceled.
52 // Then, CAIR(), CAIR_Removal(), and CAIR_HD() would also return a false, leaving the destination image/weights in an unknown state.
53 // Set to NULL if this does not need to be used.
54 //CAIR v2.16 Changelog:
55 // - A long overdue overhaul of the threading system yielded about a 40% performance boost. All threads, semaphores, and mutexes are kept around for
56 // as long as possible, instead of destroying them every step.
57 // - I stumbled across a bug in CAIR_Add() where some parts of the artificial weight matrix weren't being updated, creating slightly incorrect images.
58 // - Comment overhauls to reflect the new threading.
59 //CAIR v2.15.1 Changelog:
60 // - Mutexes and conditions used in Energy_Map() are now properly destroyed, fixing a serious memory leak. This was discovered when
61 // processing huge images (7500x3800) that would cause the process to exceed the 32-bit address space.
62 // Special thanks to Klaus Nordby for hitting this bug. CAIR has now been tested up to 9800x7800 without issue.
63 // - A potential memory leak in Deallocate_Matrix() in the CML was squashed.
64 // - By default CAIR now uses 4 threads (yay quad-core!).
65 //CAIR v2.15 Changelog:
66 // - Added the new forward energy algorithm. A new CAIR_energy parameter determines the type of energy function to use. Forward energy
67 // produces less artifacts in most images, but comes at a 5% performance cost. Thanks to Matt Newel for pointing it out.
68 // Read the paper on it here: http://www.faculty.idc.ac.il/arik/papers/vidRet.pdf
69 // - The number of threads CAIR uses can now be set by CAIR_NUM_THREADS. This currently does not apply to the Energy calculations.
70 // On my dual-core system, I netted a 5% performance boost by reducing thread count from 4 to 2.
71 // - Separate destination weights for the resize to standardize the interface.
72 // - Removed "namespace std" from source headers. Special thanks to David Oster.
73 // - Removed the clipping Get() method from the CML. This makes the CML generic again.
74 // - Comment clean-ups.
75 // - Comments have been spell-checked. Apparently, I don�t speel so good. (thanks again to David Oster)
76 //CAIR v2.14 Changelog:
77 // - CAIR has been relicensed under the LGPLv2.1
78 //CAIR v2.13 Changelog:
79 // - Added CAIR_Image_Map() and CAIR_Map_Resize() to allow for "content-aware multi-size images." Now it just needs to get put into a
80 // file-format.
81 // - CAIR() and CAIR_HD() now properly copy the Source to Dest when no resize is done.
82 // - Fixed a bug in CAIR_HD(), Energy/TEnergy confusion.
83 // - Fixed a compiler warning in main().
84 // - Changed in Remove_Quadrant() "pixel remove" into "int remove"
85 // - Comment updates and I decided to bring back the tabs (not sure why I got rid of them).
86 //CAIR v2.12 Changelog:
87 // - About 20% faster across the board.
88 // - Unchanged portions of the energy map are now retained. Special thanks to Jib for that (remind me to ask him how it works :-) ).
89 // - Add_Edge() and Remove_Edge() now update the Edge in UNSAFE mode when able.
90 // - The CML now has a CML_DEBUG mode to let the developers know when they screwed up.
91 // - main() now displays the runtime with three decimal places for better accuracy. Special thanks to Jib.
92 // - Various comment updates.
93 //CAIR v2.11 Changelog: (The Super-Speedy Jib version)
94 // - 40% speed boost across the board with "high quality"
95 // - Remove_Path() and Add_Path() directly recalculate only changed edge values. This gives the speed of low quality while
96 // maintaining high quality output. Because of this, the quality factor is no longer used and has been removed. (Special thanks to Jib)
97 // - Grayscale values during a resize are now properly recalculated for better accuracy.
98 // - main() has undergone a major overhaul. Now most operations are accessible from the CLI. (Special thanks to Jib)
99 // - Now uses multiple edge detectors, with V_SQUARE offering some of the best quality. (Special thanks to Jib)
100 // - Minor change to Grayscale_Pixel() to increase speed. (Special thanks to Jib)
101 //CAIR v2.10 Changelog: (The great title of v3.0 is when I have CAIR_HD() using Poisson reconstruction, a ways away...)
102 // - Removed multiple levels of derefrencing in all the thread functions for a 15% speed boost across the board.
103 // - Changed the way CAIR_Removal() works for more flexibility and better operation.
104 // - Fixed a bug in CAIR_Removal(): infinite loop problem that got eliminated with its new operation
105 // - Some comment updates.
106 //CAIR v2.9 Changelog:
107 // - Row-majorized and multi-threaded Add_Weights(), which gave a 40% speed boost while enlarging.
108 // - Row-majorized Edge_Detect() (among many other functions) which gave about a 10% speed boost with quality == 1.
109 // - Changed CML_Matrix::Resize_Width() so it gracefully handles enlarging beyond the Reserve()'ed max.
110 // - Changed Energy_Path() to return a long instead of int, just in case.
111 // - Fixed an enlarging bug in CAIR_Add() created in v2.8.5
112 //CAIR v2.8.5 Changelog:
113 // - Added CAIR_HD() which, at each step, determines if the vertical path or the horizontal path has the least energy and then removes it.
114 // - Changed Energy_Path() so it returns the total energy of the minimum path.
115 // - Cleaned up unnecessary allocation of some CML objects.
116 // - Fixed a bug in CML_Matrix:Shift_Row(): bounds checking could cause a shift when one wasn't desired
117 // - Fixed a bug in Remove_Quadrant(): horrible bounds checking
118 //CAIR v2.8 Changelog:
119 // - Now 30% faster across the board.
120 // - Added CML_Matrix::Shift_Row() which uses memmove() to shift elements in a row of the matrix. Special thanks again to Brett Taylor
121 // for helping me debug it.
122 // - Add_Quadrant() and Remove_Quadrant() now use the CML_Matrix::Shift_Row() method instead of the old loops. They also specifically
123 // handle their own bounds checking for assignments.
124 // - Removed all bounds checking in CML_Matrix::operator() for a speed boost.
125 // - Cleaned up some CML functions to directly use the private data instead of the class methods.
126 // - CML_Matrix::operator=() now uses memcpy() for a speed boost, especially on those larger images.
127 // - Fixed a bug in CAIR_Grayscale(), CAIR_Edge(), and the CAIR_V/H_Energy() functions: forgot to clear the alpha channel.
128 // - De-tabbed a few more functions
129 //CAIR v2.7 Changelog:
130 // - CML has gone row-major, which made the CPU cache nice and happy. Another 25% speed boost. Unfortunately, all the crazy resizing issues
131 // from v2.5 came right back, so be careful when using CML_Matrix::Resize_Width() (enlarging requires a Reserve()).
132 //CAIR v2.6.2 Changelog:
133 // - Made a ReadMe.txt and Makefile for the package
134 // - De-tabbed the source files
135 // - Comment updates
136 // - Forgot a left-over Temp object in CAIR_Add()
137 //CAIR v2.6.1 Changelog:
138 // - Fixed a memory leak in CML_Matrix::Resize_Width()
139 //CAIR v2.6 Changelog:
140 // - Eliminated the copying into a temp matrix in CAIR_Remove() and CAIR_Add(). Another 15% speed boost.
141 // - Fixed the CML resizing so its more logical. No more need for Reserve'ing memory.
142 //CAIR v2.5 Changelog:
143 // - Now 35% faster across the board.
144 // - CML has undergone a major rewrite. It no longer uses vectors as its internal storage. Because of this, its resizing functions
145 // have severe limitations, so please read the CML comments if you plan to use them. This gave about a 30% performance boost.
146 // - Optimized Energy_Map(). Now uses two specialized threading functions. About a 5% boost.
147 // - Optimized Remove_Path() to give another boost.
148 // - Energy is no longer created and destroyed in Energy_Path(). Gave another boost.
149 // - Added CAIR_H_Energy(), which gives the horizontal energy of an image.
150 // - Added CAIR_Removal(), which performs (experimental) automatic object removal. It counts the number of negative weight rows/columns,
151 // then removes the least amount in that direction. It'll check to make sure it got rid of all negative areas, then it will expand
152 // the result back out to its original dimensions.
153 //CAIR v2.1 Changelog:
154 // - Unrolled the loops for Convolve_Pixel() and changed the way Edge_Detect() works. Optimizing that gave ANOTHER 25% performance boost
155 // with quality == 1.
156 // - inline'ed and const'ed a few accessor functions in the CML for a minor speed boost.
157 // - Fixed a few cross-compiler issues; special thanks to Gabe Rudy.
158 // - Fixed a few more comments.
159 // - Forgot to mention, removal of all previous CAIR_DEBUG code. Most of it is in the new CAIR_Edge() and CAIR_Energy() anyways...
160 //CAIR v2.0 Changelog:
161 // - Now 50% faster across the board.
162 // - EasyBMP has been replaced with CML, the CAIR Matrix Library. This gave speed improvements and code standardization.
163 // This is such a large change it has affected all functions in CAIR, all for the better. Reference objects have been
164 // replaced with standard pointers.
165 // - Added three new functions: CAIR_Grayscale(), CAIR_Edge(), and CAIR_Energy(), which give the grayscale, edge detection,
166 // and energy maps of a source image.
167 // - Add_Path() and Remove_Path() now maintain Grayscale during resizing. This gave a performance boost with no real
168 // quality reduction; special thanks to Brett Taylor.
169 // - Edge_Detect() now handles the boundaries separately for a performance boost.
170 // - Add_Path() and Remove_Path() no longer refill unchanged portions of an image since CML Resize's are no longer destructive.
171 // - CAIR_Add() now Reserve's memory for the vectors in CML to prevent memory thrashing as they are enlarged.
172 // - Fixed another adding bug; new paths have their own artificial weight
173 //CAIR v1.2 Changelog:
174 // - Fixed ANOTHER adding bug; now works much better with < 1 quality
175 // - a few more comment updates
176 //CAIR v1.1 Changelog:
177 // - Fixed a bad bug in adding; averaging the wrong pixels
178 // - Fixed a few incorrect/outdated comments
179 //CAIR v1.0 Changelog:
180 // - Path adding now working with reasonable results; special thanks to Ramin Sabet
181 // - Add_Path() has been multi-threaded
182 //CAIR v0.5 Changelog:
183 // - Multi-threaded Energy_Map() and Remove_Path(), gave another 30% speed boost with quality = 0
184 // - Fixed a few compiler warnings when at level 4 (just stuff in the CAIR_DEBUG code)
185 //=========================================================================================================//
186
187 #include "CAIR.h"
188 #include "CAIR_CML.h"
189 #include <cmath> //for abs(), floor()
190 #include <limits> //for max int
191 #include <pthread.h>
192 #include <semaphore.h>
193
194 using namespace std;
195
196 //=========================================================================================================//
197 //an image processing element
198 struct CML_element
199 {
200 CML_RGBA image; //standard image pixel value
201 int edge; //the edge value of the pixel
202 int weight; //its associated weight
203 int energy; //the calculated energy for this pixel
204 CML_byte gray; //its grayscale value
205 bool removed; //flag telling me if the pixel was removed during a resize
206 };
207 //an image being processed
208 typedef CML_Matrix<CML_element> CML_image;
209 //ok, now we have a single structure of all the info for a give pixel that we'll need.
210 //now, we create a matrix of pointers. when we remove a seam, shift this matrix. access all elements through this matrix.
211 //first, though, you'll need to fill in a CML_image, then set all the pointers in a CML_image_ptr. After the resizes are done,
212 //you'll need to pull the image and weights back out. See Init_CML_Image() and Extract_CML_Image()
213 typedef CML_Matrix<CML_element *> CML_image_ptr;
214
215 //=========================================================================================================//
216 //Thread parameters
217 struct Thread_Params
218 {
219 //Image Parameters
220 CML_image_ptr * Source;
221 CAIR_convolution conv;
222 CAIR_energy ener;
223 //Internal Stuff
224 int * Path;
225 CML_image * Add_Resize;
226 CML_image * Add_Source;
227 //Thread Parameters
228 int top_y;
229 int bot_y;
230 int top_x;
231 int bot_x;
232 bool exit; //flag causing the thread to exit
233 int thread_num;
234 };
235
236 //=========================================================================================================//
237 //Thread Info
238 Thread_Params * thread_info;
239
240 //Thread Handles
241 pthread_t * remove_threads;
242 pthread_t * edge_threads;
243 pthread_t * gray_threads;
244 pthread_t * add_threads;
245 int num_threads = CAIR_NUM_THREADS;
246
247 //Thread Semaphores
248 sem_t remove_sem[3]; //start, edge_start, finish
249 sem_t add_sem[3]; //start, build_start, finish
250 sem_t edge_sem[2]; //start, finish
251 sem_t gray_sem[2]; //start, finish
252
253 //early declarations on the threading functions
254 void Startup_Threads();
255 void Shutdown_Threads();
256
257
258 //=========================================================================================================//
259 #define MIN(X,Y) ((X) < (Y) ? (X) : (Y))
260 #define MAX(X,Y) ((X) > (Y) ? (X) : (Y))
261
262 //=========================================================================================================//
263 //== G R A Y S C A L E ==//
264 //=========================================================================================================//
265
266 //=========================================================================================================//
267 //Performs a RGB->YUV type conversion (we only want Y', the luma)
Grayscale_Pixel(CML_RGBA * pixel)268 inline CML_byte Grayscale_Pixel( CML_RGBA * pixel )
269 {
270 return (CML_byte)floor( ( 299 * pixel->red +
271 587 * pixel->green +
272 114 * pixel->blue ) / 1000.0 );
273 }
274
275 //=========================================================================================================//
276 //Our thread function for the Grayscale
Gray_Quadrant(void * id)277 void * Gray_Quadrant( void * id )
278 {
279 long int num = *((long int *)id);
280
281 while( true )
282 {
283 //wait for the thread to get a signal to start
284 sem_wait( &(gray_sem[0]) );
285
286 //get updated parameters
287 Thread_Params gray_area = thread_info[num];
288
289 if( gray_area.exit == true )
290 {
291 //thread is exiting
292 break;
293 }
294
295 int width = (*(gray_area.Source)).Width();
296 for( int y = gray_area.top_y; y < gray_area.bot_y; y++ )
297 {
298 for( int x = 0; x < width; x++ )
299 {
300 (*(gray_area.Source))(x,y)->gray = Grayscale_Pixel( &(*(gray_area.Source))(x,y)->image );
301 }
302 }
303
304 //signal we're done
305 sem_post( &(gray_sem[1]) );
306 }
307
308 return NULL;
309 } //end Gray_Quadrant()
310
311 //=========================================================================================================//
312 //Sort-of does a RGB->YUV conversion (actually, just RGB->Y)
313 //Multi-threaded with each thread getting a strip across the image.
Grayscale_Image(CML_image_ptr * Source)314 void Grayscale_Image( CML_image_ptr * Source )
315 {
316 int thread_height = (*Source).Height() / num_threads;
317
318 //setup parameters
319 for( int i = 0; i < num_threads; i++ )
320 {
321 thread_info[i].Source = Source;
322 thread_info[i].top_y = i * thread_height;
323 thread_info[i].bot_y = thread_info[i].top_y + thread_height;
324 }
325
326 //have the last thread pick up the slack
327 thread_info[num_threads-1].bot_y = (*Source).Height();
328
329 //startup the threads
330 for( int i = 0; i < num_threads; i++ )
331 {
332 sem_post( &(gray_sem[0]) );
333 }
334
335 //now wait for them to come back to us
336 for( int i = 0; i < num_threads; i++ )
337 {
338 sem_wait( &(gray_sem[1]) );
339 }
340
341 } //end Grayscale_Image()
342
343 //=========================================================================================================//
344 //== E D G E ==//
345 //=========================================================================================================//
346 enum edge_safe { SAFE, UNSAFE };
347
348 //=========================================================================================================//
349 //returns the convolution value of the pixel Source[x][y] with one of the kernels.
350 //Several kernels are avaialable, each with their strengths and weaknesses. The edge_safe
351 //param will use the slower, but safer Get() method of the CML.
Convolve_Pixel(CML_image_ptr * Source,int x,int y,edge_safe safety,CAIR_convolution convolution)352 int Convolve_Pixel( CML_image_ptr * Source, int x, int y, edge_safe safety, CAIR_convolution convolution)
353 {
354 int conv = 0;
355
356 switch( convolution )
357 {
358 case PREWITT:
359 if( safety == SAFE )
360 {
361 conv = abs( (*Source).Get(x+1,y+1)->gray + (*Source).Get(x+1,y)->gray + (*Source).Get(x+1,y-1)->gray //x part of the prewitt
362 -(*Source).Get(x-1,y-1)->gray - (*Source).Get(x-1,y)->gray - (*Source).Get(x-1,y+1)->gray ) +
363 abs( (*Source).Get(x+1,y+1)->gray + (*Source).Get(x,y+1)->gray + (*Source).Get(x-1,y+1)->gray //y part of the prewitt
364 -(*Source).Get(x+1,y-1)->gray - (*Source).Get(x,y-1)->gray - (*Source).Get(x-1,y-1)->gray );
365 }
366 else
367 {
368 conv = abs( (*Source)(x+1,y+1)->gray + (*Source)(x+1,y)->gray + (*Source)(x+1,y-1)->gray //x part of the prewitt
369 -(*Source)(x-1,y-1)->gray - (*Source)(x-1,y)->gray - (*Source)(x-1,y+1)->gray ) +
370 abs( (*Source)(x+1,y+1)->gray + (*Source)(x,y+1)->gray + (*Source)(x-1,y+1)->gray //y part of the prewitt
371 -(*Source)(x+1,y-1)->gray - (*Source)(x,y-1)->gray - (*Source)(x-1,y-1)->gray );
372 }
373 break;
374
375 case V_SQUARE:
376 if( safety == SAFE )
377 {
378 conv = (*Source).Get(x+1,y+1)->gray + (*Source).Get(x+1,y)->gray + (*Source).Get(x+1,y-1)->gray //x part of the prewitt
379 -(*Source).Get(x-1,y-1)->gray - (*Source).Get(x-1,y)->gray - (*Source).Get(x-1,y+1)->gray;
380 conv *= conv;
381 }
382 else
383 {
384 conv = (*Source)(x+1,y+1)->gray + (*Source)(x+1,y)->gray + (*Source)(x+1,y-1)->gray //x part of the prewitt
385 -(*Source)(x-1,y-1)->gray - (*Source)(x-1,y)->gray - (*Source)(x-1,y+1)->gray;
386 conv *= conv;
387 }
388 break;
389
390 case V1:
391 if( safety == SAFE )
392 {
393 conv = abs( (*Source).Get(x+1,y+1)->gray + (*Source).Get(x+1,y)->gray + (*Source).Get(x+1,y-1)->gray //x part of the prewitt
394 -(*Source).Get(x-1,y-1)->gray - (*Source).Get(x-1,y)->gray - (*Source).Get(x-1,y+1)->gray );
395 }
396 else
397 {
398 conv = abs( (*Source)(x+1,y+1)->gray + (*Source)(x+1,y)->gray + (*Source)(x+1,y-1)->gray //x part of the prewitt
399 -(*Source)(x-1,y-1)->gray - (*Source)(x-1,y)->gray - (*Source)(x-1,y+1)->gray ) ;
400 }
401 break;
402
403 case SOBEL:
404 if( safety == SAFE )
405 {
406 conv = abs( (*Source).Get(x+1,y+1)->gray + (2 * (*Source).Get(x+1,y)->gray) + (*Source).Get(x+1,y-1)->gray //x part of the sobel
407 -(*Source).Get(x-1,y-1)->gray - (2 * (*Source).Get(x-1,y)->gray) - (*Source).Get(x-1,y+1)->gray ) +
408 abs( (*Source).Get(x+1,y+1)->gray + (2 * (*Source).Get(x,y+1)->gray) + (*Source).Get(x-1,y+1)->gray //y part of the sobel
409 -(*Source).Get(x+1,y-1)->gray - (2 * (*Source).Get(x,y-1)->gray) - (*Source).Get(x-1,y-1)->gray );
410 }
411 else
412 {
413 conv = abs( (*Source)(x+1,y+1)->gray + (2 * (*Source)(x+1,y)->gray) + (*Source)(x+1,y-1)->gray //x part of the sobel
414 -(*Source)(x-1,y-1)->gray - (2 * (*Source)(x-1,y)->gray) - (*Source)(x-1,y+1)->gray ) +
415 abs( (*Source)(x+1,y+1)->gray + (2 * (*Source)(x,y+1)->gray) + (*Source)(x-1,y+1)->gray //y part of the sobel
416 -(*Source)(x+1,y-1)->gray - (2 * (*Source)(x,y-1)->gray) - (*Source)(x-1,y-1)->gray );
417 }
418 break;
419
420 case LAPLACIAN:
421 if( safety == SAFE )
422 {
423 conv = abs( (*Source).Get(x+1,y)->gray + (*Source).Get(x-1,y)->gray + (*Source).Get(x,y+1)->gray + (*Source).Get(x,y-1)->gray
424 -(4 * (*Source).Get(x,y)->gray) );
425 }
426 else
427 {
428 conv = abs( (*Source)(x+1,y)->gray + (*Source)(x-1,y)->gray + (*Source)(x,y+1)->gray + (*Source)(x,y-1)->gray
429 -(4 * (*Source)(x,y)->gray) );
430 }
431 break;
432 }
433 return conv;
434 }
435
436 //=========================================================================================================//
437 //The thread function, splitting the image into strips
Edge_Quadrant(void * id)438 void * Edge_Quadrant( void * id )
439 {
440 long int num = *((long int *)id);
441
442 while( true )
443 {
444 sem_wait( &(edge_sem[0]) );
445
446 //get updated parameters
447 Thread_Params edge_area = thread_info[num];
448
449 if( edge_area.exit == true )
450 {
451 //thread is exiting
452 break;
453 }
454
455 for( int y = edge_area.top_y; y < edge_area.bot_y; y++ )
456 {
457 //left most edge
458 (*(edge_area.Source))(0,y)->edge = Convolve_Pixel( edge_area.Source, 0, y, SAFE, edge_area.conv );
459
460 //fill in the middle
461 int width = (*(edge_area.Source)).Width();
462 for( int x = 1; x < width - 1; x++ )
463 {
464 (*(edge_area.Source))(x,y)->edge = Convolve_Pixel( edge_area.Source, x, y, UNSAFE, edge_area.conv );
465 }
466
467 //right most edge
468 (*(edge_area.Source))(width-1,y)->edge = Convolve_Pixel( edge_area.Source, width-1, y, SAFE, edge_area.conv);
469 }
470
471 //signal we're done
472 sem_post( &(edge_sem[1]) );
473 }
474
475 return NULL;
476 }
477
478 //=========================================================================================================//
479 //Performs full edge detection on Source with one of the kernels.
Edge_Detect(CML_image_ptr * Source,CAIR_convolution conv)480 void Edge_Detect( CML_image_ptr * Source, CAIR_convolution conv )
481 {
482 //There is no easy solution to the boundries. Calling the same boundry pixel to convolve itself against seems actually better
483 //than padding the image with zeros or 255's.
484 //Calling itself induces a "ringing" into the near edge of the image. Padding can lead to a darker or lighter edge.
485 //The only "good" solution is to have the entire one-pixel wide edge not included in the edge detected image.
486 //This would reduce the size of the image by 2 pixels in both directions, something that is unacceptable here.
487
488 int thread_height = (*Source).Height() / num_threads;
489 int height = (*Source).Height();
490 int width = (*Source).Width();
491
492 //setup parameters
493 for( int i = 0; i < num_threads; i++ )
494 {
495 thread_info[i].Source = Source;
496 thread_info[i].top_y = (i * thread_height) + 1; //handle very top row down below
497 thread_info[i].bot_y = thread_info[i].top_y + thread_height;
498 thread_info[i].conv = conv;
499 }
500
501 //have the last thread pick up the slack
502 thread_info[num_threads-1].bot_y = height - 1; //handle very bottom row down below
503
504 //create the threads
505 for( int i = 0; i < num_threads; i++ )
506 {
507 sem_post( &(edge_sem[0]) );
508 }
509
510 //while those are running we can go back and do the boundry pixels with the extra safety checks
511 for( int x = 0; x < width; x++ )
512 {
513 (*Source)(x,0)->edge = Convolve_Pixel( Source, x, 0, SAFE, conv );
514 (*Source)(x,height-1)->edge = Convolve_Pixel( Source, x, height-1, SAFE, conv );
515 }
516
517 //now wait on them
518 for( int i = 0; i < num_threads; i++ )
519 {
520 sem_wait( &(edge_sem[1]) );
521 }
522
523 } //end Edge_Detect()
524
525 //=========================================================================================================//
526 //== E N E R G Y ==//
527 //=========================================================================================================//
528
529 //=========================================================================================================//
530 //Simple fuction returning the minimum of three values.
531 //The obvious MIN(MIN(x,y),z) is actually undesirable, since that would guarantee three branch checks.
532 //This one here sucks up a variable to guarantee only two branches.
min_of_three(int x,int y,int z)533 inline int min_of_three( int x, int y, int z )
534 {
535 int min = y;
536
537 if( x < min )
538 {
539 min = x;
540 }
541 if( z < min )
542 {
543 return z;
544 }
545
546 return min;
547 }
548
549 //=========================================================================================================//
550 //Get the value from the integer matrix, return a large value if out-of-bounds in the x-direction.
Get_Max(CML_image_ptr * Energy,int x,int y)551 inline int Get_Max( CML_image_ptr * Energy, int x, int y )
552 {
553 if( ( x < 0 ) || ( x >= (*Energy).Width() ) )
554 {
555 return std::numeric_limits<int>::max();
556 }
557 else
558 {
559 return (*Energy)(x,y)->energy;
560 }
561 }
562
563 //=========================================================================================================//
564 //This calculates a minimum energy path from the given start point (min_x) and the energy map.
Generate_Path(CML_image_ptr * Energy,int min_x,int * Path)565 void Generate_Path( CML_image_ptr * Energy, int min_x, int * Path )
566 {
567 int min;
568 int x = min_x;
569
570 int height = (*Energy).Height();
571 for( int y = height - 1; y >= 0; y-- ) //builds from bottom up
572 {
573 min = x; //assume the minimum is straight up
574
575 if( Get_Max( Energy, x-1, y ) < Get_Max( Energy, min, y ) ) //check to see if min is up-left
576 {
577 min = x - 1;
578 }
579 if( Get_Max( Energy, x+1, y ) < Get_Max( Energy, min, y) ) //up-right
580 {
581 min = x + 1;
582 }
583
584 Path[y] = min;
585 x = min;
586 }
587 }
588
589 //=========================================================================================================//
590 //Forward energy cost functions. These are additional energy values for the left, up, and right seam paths.
591 //See the paper "Improved Seam Carving for Video Retargeting" by Michael Rubinstein, Ariel Shamir, and Shai Avidan.
Forward_CostL(CML_image_ptr * Edge,int x,int y)592 inline int Forward_CostL( CML_image_ptr * Edge, int x, int y )
593 {
594 return (abs((*Edge)(x+1,y)->edge - (*Edge)(x-1,y)->edge) + abs((*Edge)(x,y-1)->edge - (*Edge)(x-1,y)->edge));
595 }
596
Forward_CostU(CML_image_ptr * Edge,int x,int y)597 inline int Forward_CostU( CML_image_ptr * Edge, int x, int y )
598 {
599 return (abs((*Edge)(x+1,y)->edge - (*Edge)(x-1,y)->edge));
600 }
601
Forward_CostR(CML_image_ptr * Edge,int x,int y)602 inline int Forward_CostR( CML_image_ptr * Edge, int x, int y )
603 {
604 return (abs((*Edge)(x+1,y)->edge - (*Edge)(x-1,y)->edge) + abs((*Edge)(x,y-1)->edge - (*Edge)(x+1,y)->edge));
605 }
606
607 //=========================================================================================================//
608 //Calculate the energy map of the image using the edges and weights. When Path is set to NULL, the energy map
609 //will be completely recalculated, otherwise if it contains a valid seam, it will use it to only update changed
610 //portions of the energy map.
Energy_Map(CML_image_ptr * Source,CAIR_energy ener,int * Path)611 void Energy_Map(CML_image_ptr * Source, CAIR_energy ener, int * Path)
612 {
613 int min_x, max_x;
614 int min_x_energy, max_x_energy;
615 int boundry_min_x, boundry_max_x;
616 int height = (*Source).Height()-1;
617 int width = (*Source).Width()-1;
618
619 if(Path == NULL)
620 {
621 //calculate full region
622 min_x = 0;
623 max_x = width;
624 }
625 else
626 {
627 //restrict calculation tree based on path location
628 min_x = MAX(Path[0]-3, 0);
629 max_x = MIN(Path[0]+2, width);
630 }
631
632 //set the first row with the correct energy
633 for(int x = min_x; x <= max_x; x++)
634 {
635 (*Source)(x,0)->energy = (*Source)(x,0)->edge + (*Source)(x,0)->weight;
636 }
637
638 for(int y = 1; y <= height; y++)
639 {
640 //each itteration we expand the width of calculations, one in each direction
641 min_x = MAX(min_x-1, 0);
642 max_x = MIN(max_x+1, width);
643 boundry_min_x = 0;
644 boundry_max_x = 0;
645
646 //boundry conditions
647 if(max_x == width)
648 {
649 (*Source)(width,y)->energy = MIN((*Source)(width-1,y-1)->energy, (*Source)(width,y-1)->energy) + (*Source)(width,y)->edge + (*Source)(width,y)->weight;
650 boundry_max_x = 1; //prevent this value from being calculated in the below loops
651 }
652 if(min_x == 0)
653 {
654 (*Source)(0,y)->energy = MIN((*Source)(0,y-1)->energy, (*Source)(1,y-1)->energy) + (*Source)(0,y)->edge + (*Source)(0,y)->weight;
655 boundry_min_x = 1;
656 }
657
658 //store the previous max/min energies, use these to see if we can trim the tree
659 min_x_energy = (*Source)(min_x,y)->energy;
660 max_x_energy = (*Source)(max_x,y)->energy;
661
662 //fill in everything besides the boundries, if needed
663 if(ener == BACKWARD)
664 {
665 for(int x = (min_x + boundry_min_x); x <= (max_x - boundry_max_x); x++)
666 {
667 (*Source)(x,y)->energy = min_of_three((*Source)(x-1,y-1)->energy,
668 (*Source)(x,y-1)->energy,
669 (*Source)(x+1,y-1)->energy)
670 + (*Source)(x,y)->edge + (*Source)(x,y)->weight;
671 }
672 }
673 else //forward energy
674 {
675 for(int x = (min_x + boundry_min_x); x <= (max_x - boundry_max_x); x++)
676 {
677 (*Source)(x,y)->energy = min_of_three((*Source)(x-1,y-1)->energy + Forward_CostL(Source,x,y),
678 (*Source)(x,y-1)->energy + Forward_CostU(Source,x,y),
679 (*Source)(x+1,y-1)->energy + Forward_CostR(Source,x,y))
680 + (*Source)(x,y)->weight;
681 }
682 }
683
684 //check to see if we can restrict future calculations
685 if(Path != NULL)
686 {
687 if((Path[y] > min_x+3) && ((*Source)(min_x,y)->energy == min_x_energy)) min_x++;
688 if((Path[y] < max_x-2) && ((*Source)(max_x,y)->energy == max_x_energy)) max_x--;
689 }
690 }
691 }
692
693
694 //=========================================================================================================//
695 //Energy_Path() generates the least energy Path of the Edge and Weights and returns the total energy of that path.
Energy_Path(CML_image_ptr * Source,int * Path,CAIR_energy ener,bool first_time)696 int Energy_Path( CML_image_ptr * Source, int * Path, CAIR_energy ener, bool first_time )
697 {
698 //calculate the energy map
699 if( first_time == true )
700 {
701 Energy_Map( Source, ener, NULL );
702 }
703 else
704 {
705 Energy_Map( Source, ener, Path );
706 }
707
708 //find minimum path start
709 int min_x = 0;
710 int width = (*Source).Width();
711 int height = (*Source).Height();
712 for( int x = 0; x < width; x++ )
713 {
714 if( (*Source)(x,height-1)->energy < (*Source)(min_x,height-1)->energy )
715 {
716 min_x = x;
717 }
718 }
719
720 //generate the path back from the energy map
721 Generate_Path( Source, min_x, Path );
722 return (*Source)(min_x,height-1)->energy;
723 }
724
725 //=========================================================================================================//
726 //== A D D ==//
727 //=========================================================================================================//
728
729 //=========================================================================================================//
730 //averages two pixels and returns the values
Average_Pixels(CML_RGBA Pixel1,CML_RGBA Pixel2)731 CML_RGBA Average_Pixels( CML_RGBA Pixel1, CML_RGBA Pixel2 )
732 {
733 CML_RGBA average;
734
735 average.alpha = ( Pixel1.alpha + Pixel2.alpha ) / 2;
736 average.blue = ( Pixel1.blue + Pixel2.blue ) / 2;
737 average.green = ( Pixel1.green + Pixel2.green ) / 2;
738 average.red = ( Pixel1.red + Pixel2.red ) / 2;
739
740 return average;
741 }
742
743 //=========================================================================================================//
744 //This works like Remove_Quadrant, strips across the image.
Add_Quadrant(void * id)745 void * Add_Quadrant( void * id )
746 {
747 long int num = *((long int *)id);
748 Thread_Params add_area;
749
750 while( true )
751 {
752 sem_wait( &(add_sem[0]) );
753
754 //get updated_parameters
755 add_area = thread_info[num];
756
757 if( add_area.exit == true )
758 {
759 //thread is exiting
760 break;
761 }
762
763 //restore the image and weights from the source, we only care about the removed flags
764 int width = (*(add_area.Add_Resize)).Width();
765 for(int y = add_area.top_y; y < add_area.bot_y; y++)
766 {
767 for(int x = 0; x < width; x++)
768 {
769 (*(add_area.Add_Resize))(x,y).image = (*(add_area.Source))(x,y)->image;
770 (*(add_area.Add_Resize))(x,y).weight = (*(add_area.Source))(x,y)->weight;
771 }
772 }
773
774 //signal that part is done
775 sem_post( &(add_sem[2]) );
776
777 //wait to begin the adding
778 sem_wait( &(add_sem[1]) );
779
780 //get updated_parameters
781 add_area = thread_info[num];
782
783 //now we can actually enlarge the image, inserting pixels near removed ones
784 width = (*(add_area.Add_Resize)).Width();
785 for(int y = add_area.top_y; y < add_area.bot_y; y++)
786 {
787 int add_column = 0;
788 for(int x = 0; x < width; x++)
789 {
790 //copy over the pixel, setting the pointer, and incrimenting the large image to the next column
791 (*(add_area.Add_Source))(add_column,y).image = (*(add_area.Add_Resize))(x,y).image;
792 (*(add_area.Add_Source))(add_column,y).weight = (*(add_area.Add_Resize))(x,y).weight;
793 (*(add_area.Source))(add_column,y) = &(*(add_area.Add_Source))(add_column,y);
794 add_column++;
795
796 if((*(add_area.Add_Resize))(x,y).removed == true)
797 {
798 //insert a new pixel, taking the average of the current pixel and the next pixel
799 (*(add_area.Add_Source))(add_column,y).image = Average_Pixels( (*(add_area.Add_Resize))(x,y).image, (*(add_area.Add_Resize))(MIN(x+1,width-1),y).image );
800 (*(add_area.Add_Source))(add_column,y).weight = ((*(add_area.Add_Resize))(x,y).weight + (*(add_area.Add_Resize))(MIN(x+1,width-1),y).weight) / 2;
801 (*(add_area.Source))(add_column,y) = &(*(add_area.Add_Source))(add_column,y);
802 add_column++;
803 }
804 }
805 }
806
807 //signal the add thread is done
808 sem_post( &(add_sem[2]) );
809
810 } //end while(true)
811 return NULL;
812 }
813
814
815 //=========================================================================================================//
816 //Grab the current image data from Source and put it back into Resize_img. Then create the enlarged image
817 //by pulling the image and remove info from Resize_img and creating our new Source. Also, update Source_ptr
818 //while we're at it.
Add_Path(CML_image * Resize_img,CML_image * Source,CML_image_ptr * Source_ptr,int goal_x)819 void Add_Path( CML_image * Resize_img, CML_image * Source, CML_image_ptr * Source_ptr, int goal_x )
820 {
821 int height = (*Resize_img).Height();
822 int thread_height = height / num_threads;
823
824 //setup parameters
825 for( int i = 0; i < num_threads; i++ )
826 {
827 thread_info[i].Source = Source_ptr;
828 thread_info[i].Add_Source = Source;
829 thread_info[i].Add_Resize = Resize_img;
830 thread_info[i].top_y = i * thread_height;
831 thread_info[i].bot_y = thread_info[i].top_y + thread_height;
832 }
833
834 //have the last thread pick up the slack
835 thread_info[num_threads-1].bot_y = height;
836
837 //startup the threads
838 for( int i = 0; i < num_threads; i++ )
839 {
840 sem_post( &(add_sem[0]) );
841 }
842
843 //now wait for them to come back to us
844 for( int i = 0; i < num_threads; i++ )
845 {
846 sem_wait( &(add_sem[2]) );
847 }
848
849 //ok, we can now resize the source to the final size
850 (*Source).D_Resize(goal_x, height);
851 (*Source_ptr).D_Resize(goal_x, height);
852
853 for( int i = 0; i < num_threads; i++ )
854 {
855 sem_post( &(add_sem[1]) );
856 }
857
858 //now wait on them again
859 for( int i = 0; i < num_threads; i++ )
860 {
861 sem_wait( &(add_sem[2]) );
862 }
863
864 } //end Add_Path()
865
866 //forward delcration
867 bool CAIR_Remove( CML_image_ptr * Source, int goal_x, CAIR_convolution conv, CAIR_energy ener, bool (*CAIR_callback)(float), int total_seams, int seams_done );
868
869 //=========================================================================================================//
870 //Enlarge Source (and Source_ptr) to the width specified in goal_x. This is accomplished by remove the number of seams
871 //that are to be added, and recording what pixels were removed. We then add a new pixel next to the origional.
CAIR_Add(CML_image * Source,CML_image_ptr * Source_ptr,int goal_x,CAIR_convolution conv,CAIR_energy ener,bool (* CAIR_callback)(float),int total_seams,int seams_done)872 bool CAIR_Add( CML_image * Source, CML_image_ptr * Source_ptr, int goal_x, CAIR_convolution conv, CAIR_energy ener, bool (*CAIR_callback)(float), int total_seams, int seams_done )
873 {
874 //create local copies of the actual source image and its set of pointers
875 //we will resize this image down the number of adds in order to determine which pixels were removed
876 CML_image Resize_img((*Source_ptr).Width(),(*Source_ptr).Height());
877 CML_image_ptr Resize_img_ptr((*Source_ptr).Width(),(*Source_ptr).Height());
878 for(int y = 0; y < (*Source_ptr).Height(); y++)
879 {
880 for(int x = 0; x < (*Source_ptr).Width(); x++)
881 {
882 Resize_img(x,y).image = (*Source_ptr)(x,y)->image;
883 Resize_img(x,y).weight = (*Source_ptr)(x,y)->weight;
884 Resize_img(x,y).removed = false;
885 Resize_img_ptr(x,y) = &(Resize_img(x,y));
886 }
887 }
888
889 //remove all the least energy seams, setting the "removed" flag for each element
890 if(CAIR_Remove(&Resize_img_ptr, (*Source_ptr).Width() - (goal_x - (*Source_ptr).Width()), conv, ener, CAIR_callback, total_seams, seams_done) == false)
891 {
892 return false;
893 }
894
895 //enlarge the image now that we have our seam data
896 Add_Path(&Resize_img, Source, Source_ptr, goal_x);
897
898 return true;
899 } //end CAIR_Add()
900
901 //=========================================================================================================//
902 //== R E M O V E ==//
903 //=========================================================================================================//
904
905 //=========================================================================================================//
906 //more multi-threaded goodness
907 //the areas are not quadrants, rather, more like strips, but I keep the name convention
Remove_Quadrant(void * id)908 void * Remove_Quadrant( void * id )
909 {
910 long int num = *((long int *)id);
911 Thread_Params remove_area;
912
913 while( true )
914 {
915 sem_wait( &(remove_sem[0]) );
916
917 //get updated parameters
918 remove_area = thread_info[num];
919
920 if( remove_area.exit == true )
921 {
922 //thread is exiting
923 break;
924 }
925
926 //remove
927 for( int y = remove_area.top_y; y < remove_area.bot_y; y++ )
928 {
929 //reduce each row by one, the removed pixel
930 int remove = (remove_area.Path)[y];
931 (*(remove_area.Source))(remove,y)->removed = true;
932
933 //now, bounds check the assignments
934 if( (remove - 1) > 0 )
935 {
936 if( (*(remove_area.Source))(remove,y)->weight >= 0 ) //otherwise area marked for removal, don't blend
937 {
938 //average removed pixel back in
939 (*(remove_area.Source))(remove-1,y)->image = Average_Pixels( (*(remove_area.Source))(remove,y)->image,
940 (*(remove_area.Source)).Get(remove-1,y)->image );
941 }
942 (*(remove_area.Source))(remove-1,y)->gray = Grayscale_Pixel( &(*(remove_area.Source))(remove-1,y)->image );
943 }
944
945 if( (remove + 1) < (*(remove_area.Source)).Width() )
946 {
947 if( (*(remove_area.Source))(remove,y)->weight >= 0 ) //otherwise area marked for removal, don't blend
948 {
949 //average removed pixel back in
950 (*(remove_area.Source))(remove+1,y)->image = Average_Pixels( (*(remove_area.Source))(remove,y)->image,
951 (*(remove_area.Source)).Get(remove+1,y)->image );
952 }
953 (*(remove_area.Source))(remove+1,y)->gray = Grayscale_Pixel( &(*(remove_area.Source))(remove+1,y)->image );
954 }
955
956 //shift everyone over
957 (*(remove_area.Source)).Shift_Row( remove + 1, y, -1 );
958 }
959
960 //signal that part is done
961 sem_post( &(remove_sem[2]) );
962
963 //wait to begin edge removal
964 sem_wait( &(remove_sem[1]) );
965
966 //get updated parameters
967 remove_area = thread_info[num];
968
969 //now update the edge values after the grayscale values have been corrected
970 int width = (*(remove_area.Source)).Width();
971 int height = (*(remove_area.Source)).Height();
972 for(int y = remove_area.top_y; y < remove_area.bot_y; y++)
973 {
974 int remove = (remove_area.Path)[y];
975 edge_safe safety = UNSAFE;
976
977 //check to see if we might fall out of the image during a Convolve_Pixel() with a 3x3 kernel
978 if( (y<=4) || (y>=height-5) || (remove<=4) || (remove>=width-5) )
979 {
980 safety = SAFE;
981 }
982
983 //rebuild the edges around the removed seam, assuming no larger than a 3x3 kernel was used
984 //The grayscale for the current seam location (remove) and its neighbor to the left (remove-1) were directly changed when the
985 //seam pixel was blended back into it. Therefore we need to update any edge value that could be affected. The kernels CAIR uses
986 //are no more than 3x3 so we would need to update at least up to one pixel on either side of the changed grayscales. But, since
987 //the seams can cut back into an area above or below the row we're currently on, other areas beyond our one pixel area could change.
988 //Therefore we have to increase the number of edge values that are updated.
989 for(int x = remove-3; x < remove+3; x++)
990 {
991 //safe/unsafe check above should make Convolve_Pixel() happy, but do a min/max check on the x to be sure it's happy
992 (*(remove_area.Source))(MIN(MAX(x,0),width-1),y)->edge = Convolve_Pixel(remove_area.Source, MIN(MAX(x,0),width-1), y, safety, remove_area.conv);
993 }
994 }
995
996 //signal we're now done
997 sem_post( &(remove_sem[2]) );
998 } //end while( true )
999
1000 return NULL;
1001 } //end Remove_Quadrant()
1002
1003 //=========================================================================================================//
1004 //Remove a seam from Source. Blend the seam's image and weight back into the Source. Update edges, grayscales,
1005 //and set corresponding removed flags.
Remove_Path(CML_image_ptr * Source,int * Path,CAIR_convolution conv)1006 void Remove_Path( CML_image_ptr * Source, int * Path, CAIR_convolution conv )
1007 {
1008 int thread_height = (*Source).Height() / num_threads;
1009
1010 //setup parameters
1011 for( int i = 0; i < num_threads; i++ )
1012 {
1013 thread_info[i].Source = Source;
1014 thread_info[i].Path = Path;
1015 thread_info[i].conv = conv;
1016 thread_info[i].top_y = i * thread_height;
1017 thread_info[i].bot_y = thread_info[i].top_y + thread_height;
1018 }
1019
1020 //have the last thread pick up the slack
1021 thread_info[num_threads-1].bot_y = (*Source).Height();
1022
1023 //start the threads
1024 for( int i = 0; i < num_threads; i++ )
1025 {
1026 sem_post( &(remove_sem[0]) );
1027 }
1028 //now wait on them
1029 for( int i = 0; i < num_threads; i++ )
1030 {
1031 sem_wait( &(remove_sem[2]) );
1032 }
1033
1034 //now we can safely resize everyone down
1035 (*Source).Resize_Width( (*Source).Width() - 1 );
1036
1037 //now get the threads to handle the edge
1038 //we must wait for the grayscale to be complete before we can recalculate changed edge values
1039 for( int i = 0; i < num_threads; i++ )
1040 {
1041 sem_post( &(remove_sem[1]) );
1042 }
1043
1044 //now wait on them, ... again
1045 for( int i = 0; i < num_threads; i++ )
1046 {
1047 sem_wait( &(remove_sem[2]) );
1048 }
1049 } //end Remove_Path()
1050
1051 //=========================================================================================================//
1052 //Removes all requested vertical paths form the image.
CAIR_Remove(CML_image_ptr * Source,int goal_x,CAIR_convolution conv,CAIR_energy ener,bool (* CAIR_callback)(float),int total_seams,int seams_done)1053 bool CAIR_Remove( CML_image_ptr * Source, int goal_x, CAIR_convolution conv, CAIR_energy ener, bool (*CAIR_callback)(float), int total_seams, int seams_done )
1054 {
1055 int removes = (*Source).Width() - goal_x;
1056 int * Min_Path = new int[(*Source).Height()];
1057
1058 //setup the images
1059 Grayscale_Image( Source );
1060 Edge_Detect( Source, conv );
1061
1062 //remove each seam
1063 for( int i = 0; i < removes; i++ )
1064 {
1065 //If you're going to maintain some sort of progress counter/bar, here's where you would do it!
1066 if( (CAIR_callback != NULL) && (CAIR_callback( (float)(i+seams_done)/total_seams ) == false) )
1067 {
1068 delete[] Min_Path;
1069 return false;
1070 }
1071
1072 //determine the least energy path
1073 if( i == 0 )
1074 {
1075 //first time through, build the energy map
1076 Energy_Path( Source, Min_Path, ener, true );
1077 }
1078 else
1079 {
1080 //next time through, only update the energy map from the last remove
1081 Energy_Path( Source, Min_Path, ener, false );
1082 }
1083
1084 //remove the seam from the image, update grayscale and edge values
1085 Remove_Path( Source, Min_Path, conv );
1086 }
1087
1088 delete[] Min_Path;
1089 return true;
1090 } //end CAIR_Remove()
1091
1092 //=========================================================================================================//
1093 //Startup all threads, create all needed semaphores.
Startup_Threads()1094 void Startup_Threads()
1095 {
1096 //create semaphores
1097 sem_init( &(remove_sem[0]), 0, 0 ); //start
1098 sem_init( &(remove_sem[1]), 0, 0 ); //edge_start
1099 sem_init( &(remove_sem[2]), 0, 0 ); //finish
1100 sem_init( &(add_sem[0]), 0, 0 ); //start
1101 sem_init( &(add_sem[1]), 0, 0 ); //build_start
1102 sem_init( &(add_sem[2]), 0, 0 ); //finish
1103 sem_init( &(edge_sem[0]), 0, 0 ); //start
1104 sem_init( &(edge_sem[1]), 0, 0 ); //finish
1105 sem_init( &(gray_sem[0]), 0, 0 ); //start
1106 sem_init( &(gray_sem[1]), 0, 0 ); //finish
1107
1108 //create the thread handles
1109 remove_threads = new pthread_t[num_threads];
1110 edge_threads = new pthread_t[num_threads];
1111 gray_threads = new pthread_t[num_threads];
1112 add_threads = new pthread_t[num_threads];
1113
1114 thread_info = new Thread_Params[num_threads];
1115
1116 //startup the threads
1117 for( int i = 0; i < num_threads; i++ )
1118 {
1119 thread_info[i].exit = false;
1120 thread_info[i].thread_num = i;
1121
1122 pthread_create( &(remove_threads[i]), NULL, Remove_Quadrant, (void *)(&(thread_info[i].thread_num)) );
1123 pthread_create( &(edge_threads[i]), NULL, Edge_Quadrant, (void *)(&(thread_info[i].thread_num)) );
1124 pthread_create( &(gray_threads[i]), NULL, Gray_Quadrant, (void *)(&(thread_info[i].thread_num)) );
1125 pthread_create( &(add_threads[i]), NULL, Add_Quadrant, (void *)(&(thread_info[i].thread_num)) );
1126 }
1127 }
1128
1129 //=========================================================================================================//
1130 //Stops all threads. Deletes all semaphores and mutexes.
Shutdown_Threads()1131 void Shutdown_Threads()
1132 {
1133 //notify the threads
1134 for( int i = 0; i < num_threads; i++ )
1135 {
1136 thread_info[i].exit = true;
1137 }
1138
1139 //start them up
1140 for( int i = 0; i < num_threads; i++ )
1141 {
1142 sem_post( &(remove_sem[0]) );
1143 sem_post( &(add_sem[0]) );
1144 sem_post( &(edge_sem[0]) );
1145 sem_post( &(gray_sem[0]) );
1146 }
1147
1148 //wait for the joins
1149 for( int i = 0; i < num_threads; i++ )
1150 {
1151 pthread_join( remove_threads[i], NULL );
1152 pthread_join( edge_threads[i], NULL );
1153 pthread_join( gray_threads[i], NULL );
1154 pthread_join( add_threads[i], NULL );
1155 }
1156
1157 //remove the thread handles
1158 delete[] remove_threads;
1159 delete[] edge_threads;
1160 delete[] gray_threads;
1161 delete[] add_threads;
1162
1163 delete[] thread_info;
1164
1165 //delete the semaphores
1166 sem_destroy( &(remove_sem[0]) ); //start
1167 sem_destroy( &(remove_sem[1]) ); //edge_start
1168 sem_destroy( &(remove_sem[2]) ); //finish
1169 sem_destroy( &(add_sem[0]) ); //start
1170 sem_destroy( &(add_sem[1]) ); //build_start
1171 sem_destroy( &(add_sem[2]) ); //finish
1172 sem_destroy( &(edge_sem[0]) ); //start
1173 sem_destroy( &(edge_sem[1]) ); //finish
1174 sem_destroy( &(gray_sem[0]) ); //start
1175 sem_destroy( &(gray_sem[1]) ); //finish
1176 }
1177
1178
1179 //=========================================================================================================//
1180 //store the provided image and weights into a CML_image, and build a CML_image_ptr
Init_CML_Image(CML_color * Source,CML_int * S_Weights,CML_image * Image,CML_image_ptr * Image_ptr)1181 void Init_CML_Image(CML_color * Source, CML_int * S_Weights, CML_image * Image, CML_image_ptr * Image_ptr)
1182 {
1183 int x = (*Source).Width();
1184 int y = (*Source).Height(); //S_Weights should match
1185
1186 (*Image).D_Resize(x,y);
1187 (*Image_ptr).D_Resize(x,y);
1188
1189 for(int j = 0; j < y; j++)
1190 {
1191 for(int i = 0; i < x; i++)
1192 {
1193 (*Image)(i,j).image = (*Source)(i,j);
1194 (*Image)(i,j).weight = (*S_Weights)(i,j);
1195
1196 (*Image_ptr)(i,j) = &((*Image)(i,j));
1197 }
1198 }
1199 }
1200
1201 //=========================================================================================================//
1202 //pull the resized image and weights back out of the CML_image through the resized CML_image_ptr
Extract_CML_Image(CML_image_ptr * Image_ptr,CML_color * Dest,CML_int * D_Weights)1203 void Extract_CML_Image(CML_image_ptr * Image_ptr, CML_color * Dest, CML_int * D_Weights)
1204 {
1205 int x = (*Image_ptr).Width();
1206 int y = (*Image_ptr).Height();
1207
1208 (*Dest).D_Resize(x,y);
1209 (*D_Weights).D_Resize(x,y);
1210
1211 for(int j = 0; j < y; j++)
1212 {
1213 for(int i = 0; i < x; i++)
1214 {
1215 (*Dest)(i,j) = (*Image_ptr)(i,j)->image;
1216 (*D_Weights)(i,j) = (*Image_ptr)(i,j)->weight;
1217 }
1218 }
1219 }
1220
1221
1222 //=========================================================================================================//
1223 //Set the number of threads that CAIR should use. Minimum of 1 required.
1224 //WARNING: Never call this function while CAIR() is processing an image, otherwise bad things will happen!
CAIR_Threads(int thread_count)1225 void CAIR_Threads( int thread_count )
1226 {
1227 if( thread_count < 1 )
1228 {
1229 num_threads = 1;
1230 }
1231 else
1232 {
1233 num_threads = thread_count;
1234 }
1235 }
1236
1237 //=========================================================================================================//
1238 //== F R O N T E N D ==//
1239 //=========================================================================================================//
1240 //The Great CAIR Frontend. This baby will retarget Source using S_Weights into the dimensions supplied by goal_x and goal_y into D_Weights and Dest.
1241 //Weights allows for an area to be biased for removal/protection. A large positive value will protect a portion of the image,
1242 //and a large negative value will remove it. Do not exceed the limits of int's, as this will cause an overflow. I would suggest
1243 //a safe range of -2,000,000 to 2,000,000 (this is a maximum guideline, much smaller weights will work just as well for most images).
1244 //Weights must be the same size as Source. D_Weights will contain the weights of Dest after the resize. Dest is the output,
1245 //and as such has no constraints (its contents will be destroyed, just so you know).
1246 //The internal order is this: remove horizontal, remove vertical, add horizontal, add vertical.
1247 //CAIR can use multiple convolution methods to determine the image energy.
1248 //Prewitt and Sobel are close to each other in results and represent the "traditional" edge detection.
1249 //V_SQUARE and V1 can produce some of the better quality results, but may remove from large objects to do so. Do note that V_SQUARE
1250 //produces much larger edge values, any may require larger weight values (by about an order of magnitude) for effective operation.
1251 //Laplacian is a second-derivative operator, and can limit some artifacts while generating others.
1252 //CAIR also can use the new improved energy algorithm called "forward energy." Removing seams can sometimes add energy back to the image
1253 //by placing nearby edges directly next to each other. Forward energy can get around this by determining the future cost of a seam.
1254 //Forward energy removes most serious artifacts from a retarget, but is slightly more costly in terms of performance.
CAIR(CML_color * Source,CML_int * S_Weights,int goal_x,int goal_y,CAIR_convolution conv,CAIR_energy ener,CML_int * D_Weights,CML_color * Dest,bool (* CAIR_callback)(float))1255 bool CAIR( CML_color * Source, CML_int * S_Weights, int goal_x, int goal_y, CAIR_convolution conv, CAIR_energy ener, CML_int * D_Weights, CML_color * Dest, bool (*CAIR_callback)(float) )
1256 {
1257 //if no change, then just copy to the source to the destination
1258 if( (goal_x == (*Source).Width()) && (goal_y == (*Source).Height() ) )
1259 {
1260 (*Dest) = (*Source);
1261 (*D_Weights) = (*S_Weights);
1262 return true;
1263 }
1264
1265 //calculate the total number of operations needed
1266 int total_seams = abs((*Source).Width()-goal_x) + abs((*Source).Height()-goal_y);
1267 int seams_done = 0;
1268
1269 //create threads for the run
1270 Startup_Threads();
1271
1272 //build the image for internal use
1273 CML_image Image(1,1);
1274 CML_image_ptr Image_Ptr(1,1);
1275 Init_CML_Image(Source, S_Weights, &Image, &Image_Ptr);
1276
1277 if( goal_x < (*Source).Width() )
1278 {
1279 //reduce width
1280 if( CAIR_Remove( &Image_Ptr, goal_x, conv, ener, CAIR_callback, total_seams, seams_done ) == false )
1281 {
1282 Shutdown_Threads();
1283 return false;
1284 }
1285 seams_done += abs((*Source).Width()-goal_x);
1286 }
1287
1288 if( goal_y < (*Source).Height() )
1289 {
1290 //reduce height
1291 //works like above, except hand it a rotated image
1292 CML_image_ptr TImage_Ptr(1,1);
1293 TImage_Ptr.Transpose(&Image_Ptr);
1294
1295 if( CAIR_Remove( &TImage_Ptr, goal_y, conv, ener, CAIR_callback, total_seams, seams_done ) == false )
1296 {
1297 Shutdown_Threads();
1298 return false;
1299 }
1300
1301 //store back the transposed info
1302 Image_Ptr.Transpose(&TImage_Ptr);
1303 seams_done += abs((*Source).Height()-goal_y);
1304 }
1305
1306 if( goal_x > (*Source).Width() )
1307 {
1308 //increase width
1309 if( CAIR_Add( &Image, &Image_Ptr, goal_x, conv, ener, CAIR_callback, total_seams, seams_done ) == false )
1310 {
1311 Shutdown_Threads();
1312 return false;
1313 }
1314 seams_done += abs((*Source).Width()-goal_x);
1315 }
1316
1317 if( goal_y > (*Source).Height() )
1318 {
1319 //increase height
1320 //works like above, except hand it a rotated image
1321 CML_image_ptr TImage_Ptr(1,1);
1322 TImage_Ptr.Transpose(&Image_Ptr);
1323
1324 if( CAIR_Add( &Image, &TImage_Ptr, goal_y, conv, ener, CAIR_callback, total_seams, seams_done ) == false )
1325 {
1326 Shutdown_Threads();
1327 return false;
1328 }
1329
1330 //store back the transposed info
1331 Image_Ptr.Transpose(&TImage_Ptr);
1332 seams_done += abs((*Source).Height()-goal_y);
1333 }
1334
1335 //pull the image data back out
1336 Extract_CML_Image(&Image_Ptr, Dest, D_Weights);
1337
1338 //shutdown threads, remove semaphores and mutexes
1339 Shutdown_Threads();
1340 return true;
1341 } //end CAIR()
1342
1343 //=========================================================================================================//
1344 //== E X T R A S ==//
1345 //=========================================================================================================//
1346 //Simple function that generates the grayscale image of Source and places the result in Dest.
CAIR_Grayscale(CML_color * Source,CML_color * Dest)1347 void CAIR_Grayscale( CML_color * Source, CML_color * Dest )
1348 {
1349 Startup_Threads();
1350
1351 CML_int weights((*Source).Width(),(*Source).Height()); //don't care about the values
1352 CML_image image(1,1);
1353 CML_image_ptr image_ptr(1,1);
1354
1355 Init_CML_Image(Source,&weights,&image,&image_ptr);
1356 Grayscale_Image( &image_ptr );
1357
1358 (*Dest).D_Resize( (*Source).Width(), (*Source).Height() );
1359
1360 for( int x = 0; x < (*Source).Width(); x++ )
1361 {
1362 for( int y = 0; y < (*Source).Height(); y++ )
1363 {
1364 (*Dest)(x,y).red = image(x,y).gray;
1365 (*Dest)(x,y).green = image(x,y).gray;
1366 (*Dest)(x,y).blue = image(x,y).gray;
1367 (*Dest)(x,y).alpha = (*Source)(x,y).alpha;
1368 }
1369 }
1370
1371 Shutdown_Threads();
1372 }
1373
1374 //=========================================================================================================//
1375 //Simple function that generates the edge-detection image of Source and stores it in Dest.
CAIR_Edge(CML_color * Source,CAIR_convolution conv,CML_color * Dest)1376 void CAIR_Edge( CML_color * Source, CAIR_convolution conv, CML_color * Dest )
1377 {
1378 Startup_Threads();
1379
1380 CML_int weights((*Source).Width(),(*Source).Height()); //don't care about the values
1381 CML_image image(1,1);
1382 CML_image_ptr image_ptr(1,1);
1383
1384 Init_CML_Image(Source,&weights,&image,&image_ptr);
1385 Grayscale_Image(&image_ptr);
1386 Edge_Detect( &image_ptr, conv );
1387
1388 (*Dest).D_Resize( (*Source).Width(), (*Source).Height() );
1389
1390 for( int x = 0; x < (*Source).Width(); x++ )
1391 {
1392 for( int y = 0; y < (*Source).Height(); y++ )
1393 {
1394 int value = image(x,y).edge;
1395
1396 if( value > 255 )
1397 {
1398 value = 255;
1399 }
1400
1401 (*Dest)(x,y).red = (CML_byte)value;
1402 (*Dest)(x,y).green = (CML_byte)value;
1403 (*Dest)(x,y).blue = (CML_byte)value;
1404 (*Dest)(x,y).alpha = (*Source)(x,y).alpha;
1405 }
1406 }
1407
1408 Shutdown_Threads();
1409 }
1410
1411 //=========================================================================================================//
1412 //Simple function that generates the vertical energy map of Source placing it into Dest.
1413 //All values are scaled down to their relative gray value. Weights are assumed all zero.
CAIR_V_Energy(CML_color * Source,CAIR_convolution conv,CAIR_energy ener,CML_color * Dest)1414 void CAIR_V_Energy( CML_color * Source, CAIR_convolution conv, CAIR_energy ener, CML_color * Dest )
1415 {
1416 Startup_Threads();
1417
1418 CML_int weights((*Source).Width(),(*Source).Height());
1419 weights.Fill(0);
1420 CML_image image(1,1);
1421 CML_image_ptr image_ptr(1,1);
1422
1423 Init_CML_Image(Source,&weights,&image,&image_ptr);
1424 Grayscale_Image(&image_ptr);
1425 Edge_Detect( &image_ptr, conv );
1426
1427 //calculate the energy map
1428 Energy_Map( &image_ptr, ener, NULL );
1429
1430 int max_energy = 0; //find the maximum energy value
1431 for( int y = 0; y < image.Height(); y++ )
1432 {
1433 for( int x = 0; x < image.Width(); x++ )
1434 {
1435 if( image(x,y).energy > max_energy )
1436 {
1437 max_energy = image(x,y).energy;
1438 }
1439 }
1440 }
1441
1442 (*Dest).D_Resize( (*Source).Width(), (*Source).Height() );
1443
1444 for( int y = 0; y < image.Height(); y++ )
1445 {
1446 for( int x = 0; x < image.Width(); x++ )
1447 {
1448 //scale the gray value down so we can get a realtive gray value for the energy level
1449 int value = (int)(((double)image(x,y).energy / max_energy) * 255);
1450 if( value < 0 )
1451 {
1452 value = 0;
1453 }
1454
1455 (*Dest)(x,y).red = (CML_byte)value;
1456 (*Dest)(x,y).green = (CML_byte)value;
1457 (*Dest)(x,y).blue = (CML_byte)value;
1458 (*Dest)(x,y).alpha = (*Source)(x,y).alpha;
1459 }
1460 }
1461
1462 Shutdown_Threads();
1463 } //end CAIR_V_Energy()
1464
1465 //=========================================================================================================//
1466 //Simple function that generates the horizontal energy map of Source placing it into Dest.
1467 //All values are scaled down to their relative gray value. Weights are assumed all zero.
CAIR_H_Energy(CML_color * Source,CAIR_convolution conv,CAIR_energy ener,CML_color * Dest)1468 void CAIR_H_Energy( CML_color * Source, CAIR_convolution conv, CAIR_energy ener, CML_color * Dest )
1469 {
1470 CML_color Tsource( 1, 1 );
1471 CML_color Tdest( 1, 1 );
1472
1473 Tsource.Transpose( Source );
1474 CAIR_V_Energy( &Tsource, conv, ener, &Tdest );
1475
1476 (*Dest).Transpose( &Tdest );
1477 }
1478
1479 //=========================================================================================================//
1480 //Experimental automatic object removal.
1481 //Any area with a negative weight will be removed. This function has three modes, determined by the choice paramater.
1482 //AUTO will have the function count the veritcal and horizontal rows/columns and remove in the direction that has the least.
1483 //VERTICAL will force the function to remove all negative weights in the veritcal direction; likewise for HORIZONTAL.
1484 //Because some conditions may cause the function not to remove all negative weights in one pass, max_attempts lets the function
1485 //go through the remoal process as many times as you're willing.
CAIR_Removal(CML_color * Source,CML_int * S_Weights,CAIR_direction choice,int max_attempts,CAIR_convolution conv,CAIR_energy ener,CML_int * D_Weights,CML_color * Dest,bool (* CAIR_callback)(float))1486 bool CAIR_Removal( CML_color * Source, CML_int * S_Weights, CAIR_direction choice, int max_attempts, CAIR_convolution conv, CAIR_energy ener, CML_int * D_Weights, CML_color * Dest, bool (*CAIR_callback)(float) )
1487 {
1488 int negative_x = 0;
1489 int negative_y = 0;
1490 CML_color Temp( 1, 1 );
1491 Temp = (*Source);
1492 (*D_Weights) = (*S_Weights);
1493
1494 for( int i = 0; i < max_attempts; i++ )
1495 {
1496 negative_x = 0;
1497 negative_y = 0;
1498
1499 //count how many negative columns exist
1500 for( int x = 0; x < (*D_Weights).Width(); x++ )
1501 {
1502 for( int y = 0; y < (*D_Weights).Height(); y++ )
1503 {
1504 if( (*D_Weights)(x,y) < 0 )
1505 {
1506 negative_x++;
1507 break; //only breaks the inner loop
1508 }
1509 }
1510 }
1511
1512 //count how many negative rows exist
1513 for( int y = 0; y < (*D_Weights).Height(); y++ )
1514 {
1515 for( int x = 0; x < (*D_Weights).Width(); x++ )
1516 {
1517 if( (*D_Weights)(x,y) < 0 )
1518 {
1519 negative_y++;
1520 break;
1521 }
1522 }
1523 }
1524
1525 switch( choice )
1526 {
1527 case AUTO :
1528 //remove in the direction that has the least to remove
1529 if( negative_y < negative_x )
1530 {
1531 if( CAIR( &Temp, D_Weights, Temp.Width(), Temp.Height() - negative_y, conv, ener, D_Weights, Dest, CAIR_callback ) == false )
1532 {
1533 return false;
1534 }
1535 Temp = (*Dest);
1536 }
1537 else
1538 {
1539 if( CAIR( &Temp, D_Weights, Temp.Width() - negative_x, Temp.Height(), conv, ener, D_Weights, Dest, CAIR_callback ) == false )
1540 {
1541 return false;
1542 }
1543 Temp = (*Dest);
1544 }
1545 break;
1546
1547 case HORIZONTAL :
1548 if( CAIR( &Temp, D_Weights, Temp.Width(), Temp.Height() - negative_y, conv, ener, D_Weights, Dest, CAIR_callback ) == false )
1549 {
1550 return false;
1551 }
1552 Temp = (*Dest);
1553 break;
1554
1555 case VERTICAL :
1556 if( CAIR( &Temp, D_Weights, Temp.Width() - negative_x, Temp.Height(), conv, ener, D_Weights, Dest, CAIR_callback ) == false )
1557 {
1558 return false;
1559 }
1560 Temp = (*Dest);
1561 break;
1562 }
1563 }
1564
1565 //now expand back out to the origional
1566 return CAIR( &Temp, D_Weights, (*Source).Width(), (*Source).Height(), conv, ener, D_Weights, Dest, CAIR_callback );
1567 } //end CAIR_Removal()
1568
1569 //The following Image Map functions are deprecated until better alternatives can be made.
1570 #if 0
1571 //=========================================================================================================//
1572 //Precompute removals in the x direction. Map will hold the largest width the corisponding pixel is still visible.
1573 //This will calculate all removals down to 3 pixels in width.
1574 //Right now this only performs removals and only the x-direction. For the future enlarging is planned. Precomputing for both directions
1575 //doesn't work all that well and generates significant artifacts. This function is intended for "content-aware multi-size images" as mentioned
1576 //in the doctors' presentation. The next logical step would be to encode Map into an existing image format. Then, using a function like
1577 //CAIR_Map_Resize() the image can be resized on a client machine with very little overhead.
1578 void CAIR_Image_Map( CML_color * Source, CML_int * Weights, CAIR_convolution conv, CAIR_energy ener, CML_int * Map )
1579 {
1580 Startup_Threads();
1581 Resize_Threads( (*Source).Height() );
1582
1583 (*Map).D_Resize( (*Source).Width(), (*Source).Height() );
1584 (*Map).Fill( 0 );
1585
1586 CML_color Temp( 1, 1 );
1587 Temp = (*Source);
1588 CML_int Temp_Weights( 1, 1 );
1589 Temp_Weights = (*Weights); //don't change Weights since there is no change to the image
1590
1591 for( int i = Temp.Width(); i > 3; i-- ) //3 is the minimum safe amount with 3x3 convolution kernels without causing problems
1592 {
1593 //grayscale
1594 CML_gray Grayscale( Temp.Width(), Temp.Height() );
1595 Grayscale_Image( &Temp, &Grayscale );
1596
1597 //edge detect
1598 CML_int Edge( Temp.Width(), Temp.Height() );
1599 Edge_Detect( &Grayscale, &Edge, conv );
1600
1601 //find the energy values
1602 int * Path = new int[(*Source).Height()];
1603 CML_int Energy( Temp.Width(), Temp.Height() );
1604 Energy_Path( &Edge, &Temp_Weights, &Energy, Path, ener, true );
1605
1606 Remove_Path( &Temp, Path, &Temp_Weights, &Edge, &Grayscale, &Energy, conv );
1607
1608 //now set the corisponding map value with the resolution
1609 for( int y = 0; y < Temp.Height(); y++ )
1610 {
1611 int index = 0;
1612 int offset = Path[y];
1613
1614 while( (*Map)(index,y) != 0 ) index++; //find the pixel that is in location zero (first unused)
1615 while( offset > 0 )
1616 {
1617 if( (*Map)(index,y) == 0 ) //find the correct x index
1618 {
1619 offset--;
1620 }
1621 index++;
1622 }
1623 while( (*Map)(index,y) != 0 ) index++; //if the current and subsequent pixels have been removed
1624
1625 (*Map)(index,y) = i; //this is now the smallest resolution this pixel will be visible
1626 }
1627
1628 delete[] Path;
1629 }
1630
1631 Shutdown_Threads();
1632
1633 } //end CAIR_Image_Map()
1634
1635 //=========================================================================================================//
1636 //An "example" function on how to decode the Map to quickly resize an image. This is only for the width, since multi-directional
1637 //resizing produces significant artifacts. Do note this will produce different results than standard CAIR(), because this resize doesn't
1638 //average pixels back into the image as does CAIR(). This function could be multi-threaded much like Remove_Path() for even faster performance.
1639 void CAIR_Map_Resize( CML_color * Source, CML_int * Map, int goal_x, CML_color * Dest )
1640 {
1641 (*Dest).D_Resize( goal_x, (*Source).Height() );
1642
1643 for( int y = 0; y < (*Source).Height(); y++ )
1644 {
1645 int input_x = 0; //map the Source's pixels to the Dests smaller size
1646 for( int x = 0; x < goal_x; x++ )
1647 {
1648 while( (*Map)(input_x,y) > goal_x ) input_x++; //skip past pixels not in this resolution
1649
1650 (*Dest)(x,y) = (*Source)(input_x,y);
1651 input_x++;
1652 }
1653 }
1654 }
1655 #endif
1656
1657 //=========================================================================================================//
1658 //== C A I R H D ==//
1659 //=========================================================================================================//
1660 //This works as CAIR, except here maximum quality is attempted. When removing in both directions some amount, CAIR_HD()
1661 //will determine which direction has the least amount of energy and then removes in that direction. This is only done
1662 //for removal, since enlarging will not benifit, although this function will perform addition just like CAIR().
1663 //Inputs are the same as CAIR().
CAIR_HD(CML_color * Source,CML_int * S_Weights,int goal_x,int goal_y,CAIR_convolution conv,CAIR_energy ener,CML_int * D_Weights,CML_color * Dest,bool (* CAIR_callback)(float))1664 bool CAIR_HD( CML_color * Source, CML_int * S_Weights, int goal_x, int goal_y, CAIR_convolution conv, CAIR_energy ener, CML_int * D_Weights, CML_color * Dest, bool (*CAIR_callback)(float) )
1665 {
1666 Startup_Threads();
1667
1668 //if no change, then just copy to the source to the destination
1669 if( (goal_x == (*Source).Width()) && (goal_y == (*Source).Height()) )
1670 {
1671 (*Dest) = (*Source);
1672 (*D_Weights) = (*S_Weights);
1673 return true;
1674 }
1675
1676 int total_seams = abs((*Source).Width()-goal_x) + abs((*Source).Height()-goal_y);
1677 int seams_done = 0;
1678
1679 //build the internal image
1680 //I only use one image, but two image pointers. This way I can reuse the data.
1681 CML_image Temp(1,1);
1682 CML_image_ptr Temp_ptr(1,1);
1683 CML_image_ptr TTemp_ptr(1,1);
1684 Init_CML_Image( Source, S_Weights, &Temp, &Temp_ptr );
1685 TTemp_ptr.Transpose(&Temp_ptr);
1686
1687 //grayscale (same for normal and transposed)
1688 Grayscale_Image( &Temp_ptr );
1689
1690 //edge detect (same for normal and transposed)
1691 Edge_Detect( &Temp_ptr, conv );
1692
1693 //do this loop when we can remove in either direction
1694 while( (Temp_ptr.Width() > goal_x) && (Temp_ptr.Height() > goal_y) )
1695 {
1696 //find the least energy seam, and its total energy for the normal image
1697 int * Path = new int[Temp_ptr.Height()];
1698 int energy_x = Energy_Path( &Temp_ptr, Path, ener, true );
1699
1700 //now rebuild the energy, with the transposed pointers
1701 int * TPath = new int[TTemp_ptr.Height()];
1702 int energy_y = Energy_Path( &TTemp_ptr, TPath, ener, true );
1703
1704 if( energy_y < energy_x )
1705 {
1706 Remove_Path( &TTemp_ptr, TPath, conv );
1707
1708 //rebuild the losers pointers
1709 Temp_ptr.Transpose( &TTemp_ptr );
1710 }
1711 else
1712 {
1713 Remove_Path( &Temp_ptr, Path, conv );
1714
1715 //rebuild the losers pointers
1716 TTemp_ptr.Transpose( &Temp_ptr );
1717 }
1718
1719 delete[] Path;
1720 delete[] TPath;
1721
1722 if( (CAIR_callback != NULL) && (CAIR_callback( (float)(seams_done)/total_seams ) == false) )
1723 {
1724 Shutdown_Threads();
1725 return false;
1726 }
1727 seams_done++;
1728 }
1729
1730 //one dimension is the now on the goal, so finish off the other direction
1731 Extract_CML_Image(&Temp_ptr, Dest, D_Weights); //we should be able to get away with using the Dest as the Source
1732 Shutdown_Threads();
1733 return CAIR( Dest, D_Weights, goal_x, goal_y, conv, ener, D_Weights, Dest, CAIR_callback );
1734 } //end CAIR_HD()
1735