source: pwntcha/trunk/src/slashdot.c @ 386

Last change on this file since 386 was 386, checked in by Sam Hocevar, 15 years ago
  • clean up.
  • Property svn:keywords set to Id
File size: 10.5 KB
Line 
1/*
2 * slashdot.c: decode Slashdot captchas
3 * $Id: slashdot.c 386 2005-01-03 15:12:41Z sam $
4 *
5 * Copyright: (c) 2004 Sam Hocevar <sam@zoy.org>
6 *   This program is free software; you can redistribute it and/or
7 *   modify it under the terms of the Do What The Fuck You Want To
8 *   Public License as published by Banlu Kemiyatorn. See
9 *   http://sam.zoy.org/projects/COPYING.WTFPL for more details.
10 */
11
12#include <stdio.h>
13#include <stdlib.h>
14#include <string.h>
15#include <math.h>
16
17#include "config.h"
18#include "common.h"
19
20/* Our macros */
21#define FACTOR 1
22#define FONTNAME "share/font_dilated_half.png" // use with FACTOR = 1
23//#define FONTNAME "share/font.png" // use with FACTOR = 2
24//#define FONTNAME "share/font_dilated.png" // use with FACTOR = 2
25
26static struct image *count_objects(struct image *img);
27static struct image *rotate(struct image *img);
28static struct image *cut_cells(struct image *img);
29static struct image *find_glyphs(struct image *img);
30
31/* Global stuff */
32struct { int xmin, ymin, xmax, ymax; } objlist[100];
33int objects = 0, first = -1, last = -1;
34char *result;
35
36/* Main function */
37char * slashdot_decode(char *image)
38{
39    struct image *img, *tmp, *tmp2;
40
41    img = load_image(image);
42    if(img == NULL)
43        return NULL;
44
45    /* Slashdot captchas have 7 characters */
46    result = malloc(8 * sizeof(char));
47
48    /* Clean image a bit */
49    tmp = detect_lines(img);
50    tmp = fill_holes(tmp);
51
52    /* Detect small objects to guess image orientation */
53    tmp2 = median(tmp);
54    tmp2 = equalize(tmp2);
55    count_objects(tmp2);
56
57    /* Invert rotation and find glyphs */
58    tmp = rotate(tmp);
59    tmp = median(tmp);
60    tmp = find_glyphs(tmp);
61
62    return result;
63}
64
65/* The following functions are local */
66
67static struct image *count_objects(struct image *img)
68{
69    struct image *dst;
70    int gotblack = 1;
71    int x, y, i;
72    int r, g, b;
73
74    dst = new_image(img->width, img->height);
75
76    for(y = 0; y < img->height; y++)
77        for(x = 0; x < img->width; x++)
78        {
79            getpixel(img, x, y, &r, &g, &b);
80            setpixel(dst, x, y, r, g, b);
81        }
82
83    while(gotblack)
84    {
85        gotblack = 0;
86        for(y = 0; y < dst->height; y++)
87            for(x = 0; x < dst->width; x++)
88            {
89                getpixel(dst, x, y, &r, &g, &b);
90                if(r == 50 && g == 50 && b == 50)
91                {
92                    gotblack = 1;
93                    flood_fill(dst, x, y, 255 - objects, 0, 0);
94                    objects++;
95                }
96            }
97    }
98
99    //printf("%i objects\n", objects);
100
101    for(i = 0; i < objects; i++)
102    {
103        objlist[i].ymin = dst->height;
104        objlist[i].ymax = 0;
105
106        for(y = 0; y < dst->height; y++)
107            for(x = 0; x < dst->width; x++)
108            {
109                getpixel(dst, x, y, &r, &g, &b);
110                if(r == 255 - i && g == 0 && b == 0)
111                {
112                    if(y < objlist[i].ymin) { objlist[i].ymin = y; objlist[i].xmin = x; }
113                    if(y > objlist[i].ymax) { objlist[i].ymax = y; objlist[i].xmax = x; }
114                }
115            }
116        //printf("y min-max: %i %i (size %i)\n", objlist[i].ymin, objlist[i].ymax, objlist[i].ymax - objlist[i].ymin + 1);
117        if(objlist[i].ymax - objlist[i].ymin > 18 && objlist[i].ymax - objlist[i].ymin < 27)
118        {
119            if(first == -1)
120                first = i;
121            last = i;
122            flood_fill(dst, objlist[i].xmin, objlist[i].ymin, 0, 0, 255);
123        }
124    }
125
126#if 0
127    { CvPoint A, B;
128      A.x = (objlist[first].xmin + objlist[first].xmax) / 2;
129      A.y = (objlist[first].ymin + objlist[first].ymax) / 2;
130      B.x = (objlist[last].xmin + objlist[last].xmax) / 2;
131      B.y = (objlist[last].ymin + objlist[last].ymax) / 2;
132      cvLine(dst, A, B, 0, 2.0, 0);
133    }
134#endif
135
136    return dst;
137}
138
139static struct image *rotate(struct image *img)
140{
141    struct image *dst;
142    int x, y, xdest, ydest;
143    int r, g, b;
144    //int R, G, B;
145    int X = objlist[first].xmin - objlist[last].xmin;
146    int Y = objlist[first].ymin - objlist[last].ymin;
147    float xtmp, ytmp;
148    float sina = (1.0 * Y) / sqrt(1.0 * X * X + Y * Y);
149    float cosa = (1.0 * X) / sqrt(1.0 * X * X + Y * Y);
150    if(sina * cosa > 0)
151    {
152        sina = -sina;
153        cosa = -cosa;
154    }
155
156    dst = new_image(img->width * FACTOR, img->height * FACTOR);
157
158    for(y = 0; y < img->height * FACTOR; y++)
159        for(x = 0; x < img->width * FACTOR; x++)
160        {
161            xtmp = 1.0 * (x - img->width * FACTOR / 2) / FACTOR;
162            ytmp = 1.0 * (y - img->height * FACTOR / 2) / FACTOR;
163            xdest = xtmp * cosa - ytmp * sina + 0.5 * img->width;
164            ydest = ytmp * cosa + xtmp * sina + 0.5 * img->height;
165            //R = G = B = 0;
166            getpixel(img, xdest, ydest, &r, &g, &b);
167            //R += r; G += g; B += b;
168            //getpixel(img, xdest+1, ydest, &r, &g, &b);
169            //R += r; G += g; B += b;
170            //getpixel(img, xdest, ydest+1, &r, &g, &b);
171            //R += r; G += g; B += b;
172            //getpixel(img, xdest+1, ydest+1, &r, &g, &b);
173            //R += r; G += g; B += b;
174            //r = R / 4; g = G / 4; b = B / 4;
175            if(r == 255 && g == 0 && b == 255)
176                g = 255;
177            setpixel(dst, x, y, r, g, b);
178        }
179
180    return dst;
181}
182
183static struct image *cut_cells(struct image *img)
184{
185    struct image *dst;
186    int x, y;
187    int r, g, b;
188
189    dst = new_image(img->width, img->height);
190
191    for(y = 0; y < img->height; y++)
192        for(x = 0; x < img->width; x++)
193        {
194            getpixel(img, x, y, &r, &g, &b);
195            setpixel(dst, x, y, r, g, b);
196        }
197
198    for(x = 0; x < img->width; x++)
199    {
200        setpixel(dst, x, 0, 255, 255, 255);
201        setpixel(dst, x, img->height - 1, 255, 255, 255);
202    }
203
204    for(y = 0; y < img->height; y++)
205        for(x = 0; x < 7; x++)
206        {
207            setpixel(dst, x * img->width / 7, y, 255, 255, 255);
208            setpixel(dst, (x + 1) * img->width / 7 - 1, y, 255, 255, 255);
209        }
210
211    return dst;
212}
213
214static struct image *find_glyphs(struct image *img)
215{
216    char all[] = "abcdefgijkmnpqrstvwxyz";
217    struct
218    {
219        int xmin, xmax, ymin, ymax;
220        int count;
221    }
222    glyphs[22];
223    struct image *dst;
224    struct image *font = load_image(FONTNAME);
225    int x, y, i = 0;
226    int r, g, b;
227    int xmin, xmax, ymin, ymax, incell = 0, count = 0, startx = 0, cur = 0;
228    int distmin, distx, disty, distch;
229
230    if(!font)
231    {
232        fprintf(stderr, "cannot load font %s\n", FONTNAME);
233        exit(-1);
234    }
235
236    dst = new_image(img->width, img->height);
237
238    for(y = 0; y < img->height; y++)
239        for(x = 0; x < img->width; x++)
240        {
241            getpixel(img, x, y, &r, &g, &b);
242            setpixel(dst, x, y, 255, g, 255);
243        }
244
245    strcpy(result, "       ");
246
247    for(x = 0; x < font->width; x++)
248    {
249        int found = 0;
250        for(y = 0; y < font->height; y++)
251        {
252            getpixel(font, x, y, &r, &g, &b);
253            if(r < 128)
254            {
255                found = 1;
256                count += (255 - r);
257            }
258        }
259        if(found && !incell)
260        {
261            incell = 1;
262            xmin = x;
263        }
264        else if(!found && incell)
265        {
266            incell = 0;
267            xmax = x;
268#if 0
269            ymin = font->height;
270            ymax = 0;
271            for(y = 0; y < font->height; y++)
272            {
273                int newx;
274                int gotit = 0;
275                for(newx = xmin; newx < xmax; newx++)
276                {
277                    getpixel(font, newx, y, &r, &g, &b);
278                    if(r < 128)
279                    {
280                        gotit = 1;
281                        break;
282                    }
283                }
284                if(gotit)
285                {
286                    if(ymin > y) ymin = y;
287                    if(ymax <= y) ymax = y + 1;
288                }
289            }
290#else
291            ymin = 0;
292            ymax = font->height;
293#endif
294            glyphs[i].xmin = xmin;
295            glyphs[i].xmax = xmax;
296            glyphs[i].ymin = ymin;
297            glyphs[i].ymax = ymax;
298            glyphs[i].count = count;
299            count = 0;
300            i++;
301        }
302    }
303
304    if(i != 22)
305    {
306        printf("error: could not find 22 glyphs in font\n");
307        exit(-1);
308    }
309
310    while(cur < 7)
311    {
312        /* Try to find 1st letter */
313        distmin = 999999999;
314        for(i = 0; i < 22; i++)
315        {
316            int localmin = 99999999, localx, localy;
317//if(all[i] == 'i') continue;
318            xmin = glyphs[i].xmin;
319            ymin = glyphs[i].ymin;
320            xmax = glyphs[i].xmax;
321            ymax = glyphs[i].ymax;
322            //printf("trying to find %c (%i×%i) - ", all[i], xmax - xmin, ymax - ymin);
323            for(y = -5 * FACTOR; y < 5 * FACTOR; y++)
324                for(x = startx - 5 * FACTOR; x < startx + 5 * FACTOR; x++)
325                {
326                    int z, t, dist;
327                    dist = 0;
328                    for(t = 0; t < ymax - ymin; t++)
329                        for(z = 0; z < xmax - xmin; z++)
330                        {
331                            int r2;
332                            getgray(font, xmin + z, ymin + t, &r);
333                            getgray(img, x + z, y + t, &r2);
334                            dist += abs(r - r2);
335                        }
336    //                printf("%i %i -> %i\n", x, y, dist);
337                    //dist /= sqrt(xmax - xmin);
338                    dist = dist * 128 / glyphs[i].count;
339                    if(dist < localmin)
340                    {
341                        localmin = dist;
342                        localx = x;
343                        localy = y;
344                    }
345                }
346            //fprintf(stderr, "%i (%i,%i)\n", localmin, localx - startx, localy);
347            if(localmin < distmin)
348            {
349                distmin = localmin;
350                distx = localx;
351                disty = localy;
352                distch = i;
353            }
354        }
355
356        //fprintf(stderr, "%i (%i,%i)\n", distmin, distx - startx, disty);
357        //printf("min diff: %c - %i (%i, %i)\n", all[distch], distmin, distx, disty);
358
359        /* Print min glyph */
360        xmin = glyphs[distch].xmin;
361        ymin = glyphs[distch].ymin;
362        xmax = glyphs[distch].xmax;
363        ymax = glyphs[distch].ymax;
364        for(y = 0; y < ymax - ymin; y++)
365            for(x = 0; x < xmax - xmin; x++)
366            {
367                getpixel(font, xmin + x, ymin + y, &r, &g, &b);
368                if(r > 128) continue;
369                setpixel(dst, distx + x, disty + y, r, g, b);
370            }
371
372        startx = distx + xmax - xmin;
373        result[cur++] = all[distch];
374    }
375
376    return dst;
377}
378
Note: See TracBrowser for help on using the repository browser.