1/**
2 * Title: Crop
3 *
4 * A couple of functions to crop images, automatically (auto detection of
5 * the borders color), using a given color (with or without tolerance)
6 * or using a selection.
7 *
8 * The threshold method works relatively well but it can be improved.
9 * Maybe L*a*b* and Delta-E will give better results (and a better
10 * granularity).
11 *
12 * Example:
13 * (start code)
14 *   im2 = gdImageAutoCrop(im, GD_CROP_SIDES);
15 *   if (im2) {
16
17 *   }
18 *   gdImageDestroy(im2);
19 *  (end code)
20 **/
21
22#include <gd.h>
23#include <stdlib.h>
24#include <string.h>
25#include <math.h>
26
27static int gdGuessBackgroundColorFromCorners(gdImagePtr im, int *color);
28static int gdColorMatch(gdImagePtr im, int col1, int col2, float threshold);
29
30/**
31 * Function: gdImageCrop
32 *  Crops the src image using the area defined by the <crop> rectangle.
33 *  The result is returned as a new image.
34 *
35 *
36 * Parameters:
37 *  src - Source image
38 *  crop - Rectangular region to crop
39 *
40 * Returns:
41 *  <gdImagePtr> on success or NULL
42 */
43gdImagePtr gdImageCrop(gdImagePtr src, const gdRectPtr crop)
44{
45    gdImagePtr dst;
46
47    if (src->trueColor) {
48        dst = gdImageCreateTrueColor(crop->width, crop->height);
49        gdImageSaveAlpha(dst, 1);
50    } else {
51        dst = gdImageCreate(crop->width, crop->height);
52        gdImagePaletteCopy(dst, src);
53    }
54    dst->transparent = src->transparent;
55
56    if (src->sx < (crop->x + crop->width -1)) {
57        crop->width = src->sx - crop->x + 1;
58    }
59    if (src->sy < (crop->y + crop->height -1)) {
60        crop->height = src->sy - crop->y + 1;
61    }
62#if 0
63printf("rect->x: %i\nrect->y: %i\nrect->width: %i\nrect->height: %i\n", crop->x, crop->y, crop->width, crop->height);
64#endif
65    if (dst == NULL) {
66        return NULL;
67    } else {
68        int y = crop->y;
69        if (src->trueColor) {
70            unsigned int dst_y = 0;
71            while (y < (crop->y + (crop->height - 1))) {
72                /* TODO: replace 4 w/byte per channel||pitch once avaiable */
73                memcpy(dst->tpixels[dst_y++], src->tpixels[y++] + crop->x, crop->width * 4);
74            }
75        } else {
76            int x;
77            for (y = crop->y; y < (crop->y + (crop->height - 1)); y++) {
78                for (x = crop->x; x < (crop->x + (crop->width - 1)); x++) {
79                    dst->pixels[y - crop->y][x - crop->x] = src->pixels[y][x];
80                }
81            }
82        }
83        return dst;
84    }
85}
86
87/**
88 * Function: gdImageAutoCrop
89 *  Automatic croping of the src image using the given mode
90 *  (see <gdCropMode>)
91 *
92 *
93 * Parameters:
94 *  im - Source image
95 *  mode - crop mode
96 *
97 * Returns:
98 *  <gdImagePtr> on success or NULL
99 *
100 * See also:
101 *  <gdCropMode>
102 */
103gdImagePtr gdImageCropAuto(gdImagePtr im, const unsigned int mode)
104{
105    const int width = gdImageSX(im);
106    const int height = gdImageSY(im);
107
108    int x,y;
109    int color, corners, match;
110    gdRect crop;
111
112    crop.x = 0;
113    crop.y = 0;
114    crop.width = 0;
115    crop.height = 0;
116
117    switch (mode) {
118        case GD_CROP_TRANSPARENT:
119            color = gdImageGetTransparent(im);
120            break;
121
122        case GD_CROP_BLACK:
123            color = gdImageColorClosestAlpha(im, 0, 0, 0, 0);
124            break;
125
126        case GD_CROP_WHITE:
127            color = gdImageColorClosestAlpha(im, 255, 255, 255, 0);
128            break;
129
130        case GD_CROP_SIDES:
131            corners = gdGuessBackgroundColorFromCorners(im, &color);
132            break;
133
134        case GD_CROP_DEFAULT:
135        default:
136            color = gdImageGetTransparent(im);
137            if (color == -1) {
138                corners = gdGuessBackgroundColorFromCorners(im, &color);
139            }
140            break;
141    }
142
143    /* TODO: Add gdImageGetRowPtr and works with ptr at the row level
144     * for the true color and palette images
145     * new formats will simply work with ptr
146     */
147    match = 1;
148    for (y = 0; match && y < height; y++) {
149        for (x = 0; match && x < width; x++) {
150            int c2 = gdImageGetPixel(im, x, y);
151            match = (color == c2);
152        }
153    }
154
155    /* Nothing to do > bye
156     * Duplicate the image?
157     */
158    if (y == height - 1) {
159        return NULL;
160    }
161
162    crop.y = y -1;
163    match = 1;
164    for (y = height - 1; match && y >= 0; y--) {
165        for (x = 0; match && x < width; x++) {
166            match = (color == gdImageGetPixel(im, x,y));
167        }
168    }
169
170    if (y == 0) {
171        crop.height = height - crop.y + 1;
172    } else {
173        crop.height = y - crop.y + 2;
174    }
175
176    match = 1;
177    for (x = 0; match && x < width; x++) {
178        for (y = 0; match && y < crop.y + crop.height - 1; y++) {
179            match = (color == gdImageGetPixel(im, x,y));
180        }
181    }
182    crop.x = x - 1;
183
184    match = 1;
185    for (x = width - 1; match && x >= 0; x--) {
186        for (y = 0; match &&  y < crop.y + crop.height - 1; y++) {
187            match = (color == gdImageGetPixel(im, x,y));
188        }
189    }
190    crop.width = x - crop.x + 2;
191    if (crop.x <= 0 || crop.y <= 0 || crop.width <= 0 || crop.height <= 0) {
192        return NULL;
193    }
194    return gdImageCrop(im, &crop);
195}
196/*TODOs: Implement DeltaE instead, way better perceptual differences */
197/**
198 * Function: gdImageThresholdCrop
199 *  Crop an image using a given color. The threshold argument defines
200 *  the tolerance to be used while comparing the image color and the
201 *  color to crop. The method used to calculate the color difference
202 *  is based on the color distance in the RGB(a) cube.
203 *
204 *
205 * Parameters:
206 *  im - Source image
207 *  color - color to crop
208 *  threshold - tolerance (0..100)
209 *
210 * Returns:
211 *  <gdImagePtr> on success or NULL
212 *
213 * See also:
214 *  <gdCropMode>, <gdImageAutoCrop> or <gdImageCrop>
215 */
216gdImagePtr gdImageCropThreshold(gdImagePtr im, const unsigned int color, const float threshold)
217{
218    const int width = gdImageSX(im);
219    const int height = gdImageSY(im);
220
221    int x,y;
222    int match;
223    gdRect crop;
224
225    crop.x = 0;
226    crop.y = 0;
227    crop.width = 0;
228    crop.height = 0;
229
230    /* Pierre: crop everything sounds bad */
231    if (threshold > 1.0) {
232        return NULL;
233    }
234
235    /* TODO: Add gdImageGetRowPtr and works with ptr at the row level
236     * for the true color and palette images
237     * new formats will simply work with ptr
238     */
239    match = 1;
240    for (y = 0; match && y < height; y++) {
241        for (x = 0; match && x < width; x++) {
242            match = (gdColorMatch(im, color, gdImageGetPixel(im, x,y), threshold)) > 0;
243        }
244    }
245
246    /* Pierre
247     * Nothing to do > bye
248     * Duplicate the image?
249     */
250    if (y == height - 1) {
251        return NULL;
252    }
253
254    crop.y = y -1;
255    match = 1;
256    for (y = height - 1; match && y >= 0; y--) {
257        for (x = 0; match && x < width; x++) {
258            match = (gdColorMatch(im, color, gdImageGetPixel(im, x, y), threshold)) > 0;
259        }
260    }
261
262    if (y == 0) {
263        crop.height = height - crop.y + 1;
264    } else {
265        crop.height = y - crop.y + 2;
266    }
267
268    match = 1;
269    for (x = 0; match && x < width; x++) {
270        for (y = 0; match && y < crop.y + crop.height - 1; y++) {
271            match = (gdColorMatch(im, color, gdImageGetPixel(im, x,y), threshold)) > 0;
272        }
273    }
274    crop.x = x - 1;
275
276    match = 1;
277    for (x = width - 1; match && x >= 0; x--) {
278        for (y = 0; match &&  y < crop.y + crop.height - 1; y++) {
279            match = (gdColorMatch(im, color, gdImageGetPixel(im, x,y), threshold)) > 0;
280        }
281    }
282    crop.width = x - crop.x + 2;
283
284    return gdImageCrop(im, &crop);
285}
286
287/* This algorithm comes from pnmcrop (http://netpbm.sourceforge.net/)
288 * Three steps:
289 *  - if 3 corners are equal.
290 *  - if two are equal.
291 *  - Last solution: average the colors
292 */
293static int gdGuessBackgroundColorFromCorners(gdImagePtr im, int *color)
294{
295    const int tl = gdImageGetPixel(im, 0, 0);
296    const int tr = gdImageGetPixel(im, gdImageSX(im) - 1, 0);
297    const int bl = gdImageGetPixel(im, 0, gdImageSY(im) -1);
298    const int br = gdImageGetPixel(im, gdImageSX(im) - 1, gdImageSY(im) -1);
299
300    if (tr == bl && tr == br) {
301        *color = tr;
302        return 3;
303    } else if (tl == bl && tl == br) {
304        *color = tl;
305        return 3;
306    } else if (tl == tr &&  tl == br) {
307        *color = tl;
308        return 3;
309    } else if (tl == tr &&  tl == bl) {
310        *color = tl;
311        return 3;
312    } else if (tl == tr  || tl == bl || tl == br) {
313        *color = tl;
314        return 2;
315    } else if (tr == bl) {
316        *color = tr;
317        return 2;
318    } else if (br == bl) {
319        *color = bl;
320        return 2;
321    } else {
322        register int r,b,g,a;
323
324        r = (int)(0.5f + (gdImageRed(im, tl) + gdImageRed(im, tr) + gdImageRed(im, bl) + gdImageRed(im, br)) / 4);
325        g = (int)(0.5f + (gdImageGreen(im, tl) + gdImageGreen(im, tr) + gdImageGreen(im, bl) + gdImageGreen(im, br)) / 4);
326        b = (int)(0.5f + (gdImageBlue(im, tl) + gdImageBlue(im, tr) + gdImageBlue(im, bl) + gdImageBlue(im, br)) / 4);
327        a = (int)(0.5f + (gdImageAlpha(im, tl) + gdImageAlpha(im, tr) + gdImageAlpha(im, bl) + gdImageAlpha(im, br)) / 4);
328        *color = gdImageColorClosestAlpha(im, r, g, b, a);
329        return 0;
330    }
331}
332
333static int gdColorMatch(gdImagePtr im, int col1, int col2, float threshold)
334{
335    const int dr = gdImageRed(im, col1) - gdImageRed(im, col2);
336    const int dg = gdImageGreen(im, col1) - gdImageGreen(im, col2);
337    const int db = gdImageBlue(im, col1) - gdImageBlue(im, col2);
338    const int da = gdImageAlpha(im, col1) - gdImageAlpha(im, col2);
339    const double dist = sqrt(dr * dr + dg * dg + db * db + da * da);
340    const double dist_perc = sqrt(dist / (255^2 + 255^2 + 255^2));
341    return (dist_perc <= threshold);
342    //return (100.0 * dist / 195075) < threshold;
343}
344
345/*
346 * To be implemented when we have more image formats.
347 * Buffer like gray8 gray16 or rgb8 will require some tweak
348 * and can be done in this function (called from the autocrop
349 * function. (Pierre)
350 */
351#if 0
352static int colors_equal (const int col1, const in col2)
353{
354
355}
356#endif
357