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