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

Last change on this file since 389 was 389, checked in by Sam Hocevar, 15 years ago
  • use OpenCV rather than Imlib2 if both are available.
  • cleaned up the slashdot code.
  • decode phpBB captchas.
  • added filter_contrast.
  • Property svn:keywords set to Id
File size: 10.9 KB
Line 
1/*
2 * slashdot.c: decode Slashdot captchas
3 * $Id: slashdot.c 389 2005-01-03 21:48:54Z 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, first, last;
34char *result;
35
36/* Main function */
37char * decode_slashdot(struct image *img)
38{
39    struct image *tmp1, *tmp2, *tmp3, *tmp4, *tmp5, *tmp6, *tmp7;
40
41    /* Initialise local data */
42    objects = 0;
43    first = -1;
44    last = -1;
45
46    /* Slashdot captchas have 7 characters */
47    result = malloc(8 * sizeof(char));
48
49    /* Clean image a bit */
50    tmp1 = filter_detect_lines(img);
51    tmp2 = filter_fill_holes(tmp1);
52
53    /* Detect small objects to guess image orientation */
54    tmp3 = filter_median(tmp2);
55    tmp4 = filter_equalize(tmp3, 200);
56    count_objects(tmp4);
57
58    /* Invert rotation and find glyphs */
59    tmp5 = rotate(tmp2);
60    tmp6 = filter_median(tmp5);
61    tmp7 = find_glyphs(tmp6);
62
63    /* Clean up our mess */
64    image_free(tmp1);
65    image_free(tmp2);
66    image_free(tmp3);
67    image_free(tmp4);
68    image_free(tmp5);
69    image_free(tmp6);
70    image_free(tmp7);
71
72    /* aaaaaaa means decoding failed */
73    if(!strcmp(result, "aaaaaaa"))
74        result[0] = '\0';
75
76    return result;
77}
78
79/* The following functions are local */
80
81static struct image *count_objects(struct image *img)
82{
83    struct image *dst;
84    int gotblack = 1;
85    int x, y, i;
86    int r, g, b;
87
88    dst = image_new(img->width, img->height);
89
90    for(y = 0; y < img->height; y++)
91        for(x = 0; x < img->width; x++)
92        {
93            getpixel(img, x, y, &r, &g, &b);
94            setpixel(dst, x, y, r, g, b);
95        }
96
97    while(gotblack)
98    {
99        gotblack = 0;
100        for(y = 0; y < dst->height; y++)
101            for(x = 0; x < dst->width; x++)
102            {
103                getpixel(dst, x, y, &r, &g, &b);
104                if(r == 50 && g == 50 && b == 50)
105                {
106                    gotblack = 1;
107                    filter_flood_fill(dst, x, y, 255 - objects, 0, 0);
108                    objects++;
109                }
110            }
111    }
112
113    //printf("%i objects\n", objects);
114
115    for(i = 0; i < objects; i++)
116    {
117        objlist[i].ymin = dst->height;
118        objlist[i].ymax = 0;
119
120        for(y = 0; y < dst->height; y++)
121            for(x = 0; x < dst->width; x++)
122            {
123                getpixel(dst, x, y, &r, &g, &b);
124                if(r == 255 - i && g == 0 && b == 0)
125                {
126                    if(y < objlist[i].ymin) { objlist[i].ymin = y; objlist[i].xmin = x; }
127                    if(y > objlist[i].ymax) { objlist[i].ymax = y; objlist[i].xmax = x; }
128                }
129            }
130        //printf("y min-max: %i %i (size %i)\n", objlist[i].ymin, objlist[i].ymax, objlist[i].ymax - objlist[i].ymin + 1);
131        if(objlist[i].ymax - objlist[i].ymin > 18 && objlist[i].ymax - objlist[i].ymin < 27)
132        {
133            if(first == -1)
134                first = i;
135            last = i;
136            filter_flood_fill(dst, objlist[i].xmin, objlist[i].ymin, 0, 0, 255);
137        }
138    }
139
140#if 0
141    { CvPoint A, B;
142      A.x = (objlist[first].xmin + objlist[first].xmax) / 2;
143      A.y = (objlist[first].ymin + objlist[first].ymax) / 2;
144      B.x = (objlist[last].xmin + objlist[last].xmax) / 2;
145      B.y = (objlist[last].ymin + objlist[last].ymax) / 2;
146      cvLine(dst, A, B, 0, 2.0, 0);
147    }
148#endif
149
150    return dst;
151}
152
153static struct image *rotate(struct image *img)
154{
155    struct image *dst;
156    int x, y, xdest, ydest;
157    int r, g, b;
158    //int R, G, B;
159    int X = objlist[first].xmin - objlist[last].xmin;
160    int Y = objlist[first].ymin - objlist[last].ymin;
161    float xtmp, ytmp;
162    float sina = (1.0 * Y) / sqrt(1.0 * X * X + Y * Y);
163    float cosa = (1.0 * X) / sqrt(1.0 * X * X + Y * Y);
164    if(sina * cosa > 0)
165    {
166        sina = -sina;
167        cosa = -cosa;
168    }
169
170    dst = image_new(img->width * FACTOR, img->height * FACTOR);
171
172    for(y = 0; y < img->height * FACTOR; y++)
173        for(x = 0; x < img->width * FACTOR; x++)
174        {
175            xtmp = 1.0 * (x - img->width * FACTOR / 2) / FACTOR;
176            ytmp = 1.0 * (y - img->height * FACTOR / 2) / FACTOR;
177            xdest = xtmp * cosa - ytmp * sina + 0.5 * img->width;
178            ydest = ytmp * cosa + xtmp * sina + 0.5 * img->height;
179            //R = G = B = 0;
180            getpixel(img, xdest, ydest, &r, &g, &b);
181            //R += r; G += g; B += b;
182            //getpixel(img, xdest+1, ydest, &r, &g, &b);
183            //R += r; G += g; B += b;
184            //getpixel(img, xdest, ydest+1, &r, &g, &b);
185            //R += r; G += g; B += b;
186            //getpixel(img, xdest+1, ydest+1, &r, &g, &b);
187            //R += r; G += g; B += b;
188            //r = R / 4; g = G / 4; b = B / 4;
189            if(r == 255 && g == 0 && b == 255)
190                g = 255;
191            setpixel(dst, x, y, r, g, b);
192        }
193
194    return dst;
195}
196
197static struct image *cut_cells(struct image *img)
198{
199    struct image *dst;
200    int x, y;
201    int r, g, b;
202
203    dst = image_new(img->width, img->height);
204
205    for(y = 0; y < img->height; y++)
206        for(x = 0; x < img->width; x++)
207        {
208            getpixel(img, x, y, &r, &g, &b);
209            setpixel(dst, x, y, r, g, b);
210        }
211
212    for(x = 0; x < img->width; x++)
213    {
214        setpixel(dst, x, 0, 255, 255, 255);
215        setpixel(dst, x, img->height - 1, 255, 255, 255);
216    }
217
218    for(y = 0; y < img->height; y++)
219        for(x = 0; x < 7; x++)
220        {
221            setpixel(dst, x * img->width / 7, y, 255, 255, 255);
222            setpixel(dst, (x + 1) * img->width / 7 - 1, y, 255, 255, 255);
223        }
224
225    return dst;
226}
227
228static struct image *find_glyphs(struct image *img)
229{
230    char all[] = "abcdefgijkmnpqrstvwxyz";
231    struct
232    {
233        int xmin, xmax, ymin, ymax;
234        int count;
235    }
236    glyphs[22];
237    struct image *dst;
238    struct image *font = image_load(FONTNAME);
239    int x, y, i = 0;
240    int r, g, b;
241    int xmin, xmax, ymin, ymax, incell = 0, count = 0, startx = 0, cur = 0;
242    int distmin, distx, disty, distch;
243
244    if(!font)
245    {
246        fprintf(stderr, "cannot load font %s\n", FONTNAME);
247        exit(-1);
248    }
249
250    dst = image_new(img->width, img->height);
251
252    for(y = 0; y < img->height; y++)
253        for(x = 0; x < img->width; x++)
254        {
255            getpixel(img, x, y, &r, &g, &b);
256            setpixel(dst, x, y, 255, g, 255);
257        }
258
259    strcpy(result, "       ");
260
261    for(x = 0; x < font->width; x++)
262    {
263        int found = 0;
264        for(y = 0; y < font->height; y++)
265        {
266            getpixel(font, x, y, &r, &g, &b);
267            if(r < 128)
268            {
269                found = 1;
270                count += (255 - r);
271            }
272        }
273        if(found && !incell)
274        {
275            incell = 1;
276            xmin = x;
277        }
278        else if(!found && incell)
279        {
280            incell = 0;
281            xmax = x;
282#if 0
283            ymin = font->height;
284            ymax = 0;
285            for(y = 0; y < font->height; y++)
286            {
287                int newx;
288                int gotit = 0;
289                for(newx = xmin; newx < xmax; newx++)
290                {
291                    getpixel(font, newx, y, &r, &g, &b);
292                    if(r < 128)
293                    {
294                        gotit = 1;
295                        break;
296                    }
297                }
298                if(gotit)
299                {
300                    if(ymin > y) ymin = y;
301                    if(ymax <= y) ymax = y + 1;
302                }
303            }
304#else
305            ymin = 0;
306            ymax = font->height;
307#endif
308            glyphs[i].xmin = xmin;
309            glyphs[i].xmax = xmax;
310            glyphs[i].ymin = ymin;
311            glyphs[i].ymax = ymax;
312            glyphs[i].count = count;
313            count = 0;
314            i++;
315        }
316    }
317
318    if(i != 22)
319    {
320        printf("error: could not find 22 glyphs in font\n");
321        exit(-1);
322    }
323
324    while(cur < 7)
325    {
326        /* Try to find 1st letter */
327        distmin = 999999999;
328        for(i = 0; i < 22; i++)
329        {
330            int localmin = 99999999, localx, localy;
331//if(all[i] == 'i') continue;
332            xmin = glyphs[i].xmin;
333            ymin = glyphs[i].ymin;
334            xmax = glyphs[i].xmax;
335            ymax = glyphs[i].ymax;
336            //printf("trying to find %c (%i×%i) - ", all[i], xmax - xmin, ymax - ymin);
337            for(y = -5 * FACTOR; y < 5 * FACTOR; y++)
338                for(x = startx - 5 * FACTOR; x < startx + 5 * FACTOR; x++)
339                {
340                    int z, t, dist;
341                    dist = 0;
342                    for(t = 0; t < ymax - ymin; t++)
343                        for(z = 0; z < xmax - xmin; z++)
344                        {
345                            int r2;
346                            getgray(font, xmin + z, ymin + t, &r);
347                            getgray(img, x + z, y + t, &r2);
348                            dist += abs(r - r2);
349                        }
350    //                printf("%i %i -> %i\n", x, y, dist);
351                    //dist /= sqrt(xmax - xmin);
352                    dist = dist * 128 / glyphs[i].count;
353                    if(dist < localmin)
354                    {
355                        localmin = dist;
356                        localx = x;
357                        localy = y;
358                    }
359                }
360            //fprintf(stderr, "%i (%i,%i)\n", localmin, localx - startx, localy);
361            if(localmin < distmin)
362            {
363                distmin = localmin;
364                distx = localx;
365                disty = localy;
366                distch = i;
367            }
368        }
369
370        //fprintf(stderr, "%i (%i,%i)\n", distmin, distx - startx, disty);
371        //printf("min diff: %c - %i (%i, %i)\n", all[distch], distmin, distx, disty);
372
373        /* Print min glyph */
374        xmin = glyphs[distch].xmin;
375        ymin = glyphs[distch].ymin;
376        xmax = glyphs[distch].xmax;
377        ymax = glyphs[distch].ymax;
378        for(y = 0; y < ymax - ymin; y++)
379            for(x = 0; x < xmax - xmin; x++)
380            {
381                getpixel(font, xmin + x, ymin + y, &r, &g, &b);
382                if(r > 128) continue;
383                setpixel(dst, distx + x, disty + y, r, g, b);
384            }
385
386        startx = distx + xmax - xmin;
387        result[cur++] = all[distch];
388    }
389
390    return dst;
391}
392
Note: See TracBrowser for help on using the repository browser.