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

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