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

Last change on this file since 383 was 383, checked in by Sam Hocevar, 15 years ago
  • Put font in share/
  • Fixed file headers
  • Property svn:keywords set to Id
File size: 17.4 KB
Line 
1/*
2 * slashdot.c: decode Slashdot captchas
3 * $Id: slashdot.c 383 2005-01-03 10:58:23Z 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.png" // use with FACTOR = 2
23//#define FONTNAME "share/font_dilated.png" // use with FACTOR = 2
24#define FONTNAME "share/font_dilated_half.png" // use with FACTOR = 1
25
26/* Global stuff */
27char *result;
28
29struct
30{
31    int xmin, ymin, xmax, ymax;
32}
33objlist[100];
34int objects = 0, first = -1, last = -1;
35
36/* Functions */
37
38void flood_fill(struct image *img, int x, int y, int r, int g, int b)
39{
40    int oldr, oldg, oldb;
41    int nextr, nextg, nextb;
42
43    if(x < 0 || y < 0 || x >= img->width || y >= img->height)
44        return;
45
46    getpixel(img, x, y, &oldr, &oldg, &oldb);
47    setpixel(img, x, y, r, g, b);
48
49    getpixel(img, x + 1, y, &nextr, &nextg, &nextb);
50    if(nextr == oldr && nextg == oldg && nextb == oldb)
51        flood_fill(img, x + 1, y, r, g, b);
52
53    getpixel(img, x - 1, y, &nextr, &nextg, &nextb);
54    if(nextr == oldr && nextg == oldg && nextb == oldb)
55        flood_fill(img, x - 1, y, r, g, b);
56
57    getpixel(img, x, y + 1, &nextr, &nextg, &nextb);
58    if(nextr == oldr && nextg == oldg && nextb == oldb)
59        flood_fill(img, x, y + 1, r, g, b);
60
61    getpixel(img, x, y - 1, &nextr, &nextg, &nextb);
62    if(nextr == oldr && nextg == oldg && nextb == oldb)
63        flood_fill(img, x, y - 1, r, g, b);
64}
65
66struct image *count_objects(struct image *img)
67{
68    struct image *dst;
69    int gotblack = 1;
70    int x, y, i;
71    int r, g, b;
72
73    dst = new_image(img->width, img->height);
74
75    for(y = 0; y < img->height; y++)
76        for(x = 0; x < img->width; x++)
77        {
78            getpixel(img, x, y, &r, &g, &b);
79            setpixel(dst, x, y, r, g, b);
80        }
81
82    while(gotblack)
83    {
84        gotblack = 0;
85        for(y = 0; y < dst->height; y++)
86            for(x = 0; x < dst->width; x++)
87            {
88                getpixel(dst, x, y, &r, &g, &b);
89                if(r == 50 && g == 50 && b == 50)
90                {
91                    gotblack = 1;
92                    flood_fill(dst, x, y, 255 - objects, 0, 0);
93                    objects++;
94                }
95            }
96    }
97
98    //printf("%i objects\n", objects);
99
100    for(i = 0; i < objects; i++)
101    {
102        objlist[i].ymin = dst->height;
103        objlist[i].ymax = 0;
104
105        for(y = 0; y < dst->height; y++)
106            for(x = 0; x < dst->width; x++)
107            {
108                getpixel(dst, x, y, &r, &g, &b);
109                if(r == 255 - i && g == 0 && b == 0)
110                {
111                    if(y < objlist[i].ymin) { objlist[i].ymin = y; objlist[i].xmin = x; }
112                    if(y > objlist[i].ymax) { objlist[i].ymax = y; objlist[i].xmax = x; }
113                }
114            }
115        //printf("y min-max: %i %i (size %i)\n", objlist[i].ymin, objlist[i].ymax, objlist[i].ymax - objlist[i].ymin + 1);
116        if(objlist[i].ymax - objlist[i].ymin > 18 && objlist[i].ymax - objlist[i].ymin < 27)
117        {
118            if(first == -1)
119                first = i;
120            last = i;
121            flood_fill(dst, objlist[i].xmin, objlist[i].ymin, 0, 0, 255);
122        }
123    }
124
125#if 0
126    { CvPoint A, B;
127      A.x = (objlist[first].xmin + objlist[first].xmax) / 2;
128      A.y = (objlist[first].ymin + objlist[first].ymax) / 2;
129      B.x = (objlist[last].xmin + objlist[last].xmax) / 2;
130      B.y = (objlist[last].ymin + objlist[last].ymax) / 2;
131      cvLine(dst, A, B, 0, 2.0, 0);
132    }
133#endif
134
135    return dst;
136}
137
138struct image *rotate(struct image *img)
139{
140    struct image *dst;
141    int x, y, xdest, ydest;
142    int r, g, b, R, G, B;
143    int X = objlist[first].xmin - objlist[last].xmin;
144    int Y = objlist[first].ymin - objlist[last].ymin;
145    float xtmp, ytmp;
146    float sina = (1.0 * Y) / sqrt(1.0 * X * X + Y * Y);
147    float cosa = (1.0 * X) / sqrt(1.0 * X * X + Y * Y);
148    if(sina * cosa > 0)
149    {
150        sina = -sina;
151        cosa = -cosa;
152    }
153
154    dst = new_image(img->width * FACTOR, img->height * FACTOR);
155
156    for(y = 0; y < img->height * FACTOR; y++)
157        for(x = 0; x < img->width * FACTOR; x++)
158        {
159            xtmp = 1.0 * (x - img->width * FACTOR / 2) / FACTOR;
160            ytmp = 1.0 * (y - img->height * FACTOR / 2) / FACTOR;
161            xdest = xtmp * cosa - ytmp * sina + 0.5 * img->width;
162            ydest = ytmp * cosa + xtmp * sina + 0.5 * img->height;
163            //R = G = B = 0;
164            getpixel(img, xdest, ydest, &r, &g, &b);
165            //R += r; G += g; B += b;
166            //getpixel(img, xdest+1, ydest, &r, &g, &b);
167            //R += r; G += g; B += b;
168            //getpixel(img, xdest, ydest+1, &r, &g, &b);
169            //R += r; G += g; B += b;
170            //getpixel(img, xdest+1, ydest+1, &r, &g, &b);
171            //R += r; G += g; B += b;
172            //r = R / 4; g = G / 4; b = B / 4;
173            if(r == 255 && g == 0 && b == 255)
174                g = 255;
175            setpixel(dst, x, y, r, g, b);
176        }
177
178    return dst;
179}
180
181struct image *fill_holes(struct image *img)
182{
183    struct image *dst;
184    int x, y;
185    int r, g, b;
186
187    dst = new_image(img->width, img->height);
188
189    for(y = 0; y < img->height; y++)
190        for(x = 0; x < img->width; x++)
191        {
192            getpixel(img, x, y, &r, &g, &b);
193            setpixel(dst, x, y, r, g, b);
194        }
195
196    for(y = 0; y < dst->height; y++)
197        for(x = 2; x < dst->width - 2; x++)
198        {
199            int c1, c2, c3, c4, c5;
200            getpixel(img, x-2, y, &c1, &g, &b);
201            getpixel(img, x-1, y, &c2, &g, &b);
202            getpixel(img, x, y, &c3, &g, &b);
203            getpixel(img, x+1, y, &c4, &g, &b);
204            getpixel(img, x+2, y, &c5, &g, &b);
205            if(c1 < 127 && c2 < 127 && c3 > 128 && c4 < 127)
206                c3 = (c1 + c2 + c4) / 3;
207            else if(c2 < 127 && c3 > 128 && c4 < 127 && c5 < 127)
208                c3 = (c2 + c4 + c5) / 3;
209            setpixel(dst, x, y, c3, c3, c3);
210        }
211
212    for(x = 0; x < dst->width; x++)
213        for(y = 2; y < dst->height - 2; y++)
214        {
215            int c1, c2, c3, c4, c5;
216            getpixel(img, x, y-2, &c1, &g, &b);
217            getpixel(img, x, y-1, &c2, &g, &b);
218            getpixel(img, x, y, &c3, &g, &b);
219            getpixel(img, x, y+1, &c4, &g, &b);
220            getpixel(img, x, y+2, &c5, &g, &b);
221            if(c1 < 127 && c2 < 127 && c3 > 128 && c4 < 127)
222                c3 = (c1 + c2 + c4) / 3;
223            else if(c2 < 127 && c3 > 128 && c4 < 127 && c5 < 127)
224                c3 = (c2 + c4 + c5) / 3;
225            setpixel(dst, x, y, c3, c3, c3);
226        }
227
228    return dst;
229}
230
231struct image *cut_cells(struct image *img)
232{
233    struct image *dst;
234    int x, y;
235    int r, g, b;
236
237    dst = new_image(img->width, img->height);
238
239    for(y = 0; y < img->height; y++)
240        for(x = 0; x < img->width; x++)
241        {
242            getpixel(img, x, y, &r, &g, &b);
243            setpixel(dst, x, y, r, g, b);
244        }
245
246    for(x = 0; x < img->width; x++)
247    {
248        setpixel(dst, x, 0, 255, 255, 255);
249        setpixel(dst, x, img->height - 1, 255, 255, 255);
250    }
251
252    for(y = 0; y < img->height; y++)
253        for(x = 0; x < 7; x++)
254        {
255            setpixel(dst, x * img->width / 7, y, 255, 255, 255);
256            setpixel(dst, (x + 1) * img->width / 7 - 1, y, 255, 255, 255);
257        }
258
259    return dst;
260}
261
262struct image *detect_lines(struct image *img)
263{
264    struct image *dst;
265    int x, y;
266    int r, ra, rb, g, b;
267
268    dst = new_image(img->width, img->height);
269
270    /* Remove white lines */
271    for(y = 0; y < img->height; y++)
272        for(x = 0; x < img->width; x++)
273        {
274            getpixel(img, x, y, &r, &g, &b);
275            setpixel(dst, x, y, r, g, b);
276#if 1
277            if(y > 0 && y < img->height - 1)
278            {
279                getpixel(img, x, y - 1, &ra, &g, &b);
280                getpixel(img, x, y + 1, &rb, &g, &b);
281                if(r > ra && (r - ra) * (r - rb) > 5000)
282                    setpixel(dst, x, y, ra, ra, ra);
283            }
284#endif
285        }
286
287    /* Remove black lines */
288    for(y = 0; y < img->height; y++)
289        for(x = 0; x < img->width; x++)
290        {
291            getpixel(dst, x, y, &r, &g, &b);
292            if(y > 0 && y < img->height - 1)
293            {
294                getpixel(img, x, y - 1, &ra, &g, &b);
295                getpixel(img, x, y + 1, &rb, &g, &b);
296                if(r < ra && (r - ra) * (r - rb) > 500)
297                    setpixel(dst, x, y, ra, ra, ra);
298            }
299        }
300
301    return dst;
302}
303
304struct image *equalize(struct image *img)
305{
306    struct image *dst;
307    int x, y;
308    int r, g, b;
309
310    dst = new_image(img->width, img->height);
311
312    for(y = 0; y < img->height; y++)
313        for(x = 0; x < img->width; x++)
314        {
315            getpixel(img, x, y, &r, &g, &b);
316            if(r < 200) r = 50; else r = 200;
317            setpixel(dst, x, y, r, r, r);
318        }
319
320    return dst;
321}
322
323struct image *trick(struct image *img)
324{
325#define TSIZE 3
326    struct image *dst;
327    int x, y, i, j, val, m, more, l, less;
328    int r, g, b;
329
330    dst = new_image(img->width, img->height);
331
332    for(y = 0; y < img->height; y++)
333        for(x = 0; x < img->width; x++)
334            setpixel(dst, x, y, 255, 255, 255);
335
336    for(y = TSIZE/2; y < img->height - TSIZE/2; y++)
337        for(x = TSIZE/2; x < img->width - TSIZE/2; x++)
338        {
339            getpixel(img, x + j - TSIZE/2, y + i - TSIZE/2, &val, &g, &b);
340            m = more = l = less = 0;
341            for(i = 0; i < TSIZE; i++)
342                for(j = 0; j < TSIZE; j++)
343                {
344                    getpixel(img, x + j - TSIZE/2, y + i - TSIZE/2, &r, &g, &b);
345                    if(r > val)
346                    {
347                        more += r;
348                        m++;
349                    }
350                    else if(r < val)
351                    {
352                        less += r;
353                        l++;
354                    }
355                }
356
357            if(l >= 6)
358                i = less / l;
359            else if(m >= 6)
360                i = more / m;
361            else
362                i = val;
363            setpixel(dst, x, y, i, i, i);
364        }
365
366    return dst;
367}
368
369struct image *smooth(struct image *img)
370{
371#define SSIZE 3
372    struct image *dst;
373    int x, y, i, j, val;
374    int r, g, b;
375
376    dst = new_image(img->width, img->height);
377
378    for(y = 0; y < img->height; y++)
379        for(x = 0; x < img->width; x++)
380            setpixel(dst, x, y, 255, 255, 255);
381return dst;
382
383    for(y = SSIZE/2; y < img->height - SSIZE/2; y++)
384        for(x = SSIZE/2; x < img->width - SSIZE/2; x++)
385        {
386            val = 0;
387            for(i = 0; i < SSIZE; i++)
388                for(j = 0; j < SSIZE; j++)
389                {
390                    getpixel(img, x + j - SSIZE/2, y + i - SSIZE/2, &r, &g, &b);
391                    val += r;
392                }
393
394            i = val / (SSIZE * SSIZE);
395            setpixel(dst, x, y, i, i, i);
396        }
397
398    return dst;
399}
400
401struct image *median(struct image *img)
402{
403#define MSIZE 4
404    struct image *dst;
405    int x, y, i, j, val[MSIZE*MSIZE];
406    int r, g, b;
407
408    dst = new_image(img->width, img->height);
409
410    for(y = 0; y < img->height; y++)
411        for(x = 0; x < img->width; x++)
412            setpixel(dst, x, y, 255, 255, 255);
413
414    for(y = MSIZE/2; y < img->height - MSIZE/2; y++)
415        for(x = MSIZE/2; x < img->width - MSIZE/2; x++)
416        {
417            for(i = 0; i < MSIZE; i++)
418                for(j = 0; j < MSIZE; j++)
419                {
420                    getpixel(img, x + j - SSIZE/2, y + i - SSIZE/2, &r, &g, &b);
421                    val[i * MSIZE + j] = r;
422                }
423
424            /* Bubble sort power! */
425            for(i = 0; i < MSIZE * MSIZE / 2 + 1; i++)
426                for(j = i + 1; j < MSIZE * MSIZE; j++)
427                    if(val[i] > val[j])
428                    {
429                        register int k = val[i];
430                        val[i] = val[j];
431                        val[j] = k;
432                    }
433
434            i = val[MSIZE * MSIZE / 2];
435            setpixel(dst, x, y, i, i, i);
436        }
437
438    return dst;
439}
440
441struct image * find_glyphs(struct image *img)
442{
443    char all[] = "abcdefgijkmnpqrstvwxyz";
444    struct
445    {
446        int xmin, xmax, ymin, ymax;
447        int count;
448    }
449    glyphs[22];
450    struct image *dst;
451    struct image *font = load_image(FONTNAME);
452    int x, y, i = 0;
453    int r, g, b, r2, g2, b2;
454    int xmin, xmax, ymin, ymax, incell = 0, count = 0, startx = 0, cur = 0;
455    int distmin, distx, disty, distch;
456
457    if(!font)
458    {
459        fprintf(stderr, "cannot load font %s\n", FONTNAME);
460        exit(-1);
461    }
462
463    dst = new_image(img->width, img->height);
464
465    for(y = 0; y < img->height; y++)
466        for(x = 0; x < img->width; x++)
467        {
468            getpixel(img, x, y, &r, &g, &b);
469            setpixel(dst, x, y, 255, g, 255);
470        }
471
472    strcpy(result, "       ");
473
474    for(x = 0; x < font->width; x++)
475    {
476        int found = 0;
477        for(y = 0; y < font->height; y++)
478        {
479            getpixel(font, x, y, &r, &g, &b);
480            if(r < 128)
481            {
482                found = 1;
483                count += (255 - r);
484            }
485        }
486        if(found && !incell)
487        {
488            incell = 1;
489            xmin = x;
490        }
491        else if(!found && incell)
492        {
493            incell = 0;
494            xmax = x;
495#if 0
496            ymin = font->height;
497            ymax = 0;
498            for(y = 0; y < font->height; y++)
499            {
500                int newx;
501                int gotit = 0;
502                for(newx = xmin; newx < xmax; newx++)
503                {
504                    getpixel(font, newx, y, &r, &g, &b);
505                    if(r < 128)
506                    {
507                        gotit = 1;
508                        break;
509                    }
510                }
511                if(gotit)
512                {
513                    if(ymin > y) ymin = y;
514                    if(ymax <= y) ymax = y + 1;
515                }
516            }
517#else
518            ymin = 0;
519            ymax = font->height;
520#endif
521            glyphs[i].xmin = xmin;
522            glyphs[i].xmax = xmax;
523            glyphs[i].ymin = ymin;
524            glyphs[i].ymax = ymax;
525            glyphs[i].count = count;
526            count = 0;
527            i++;
528        }
529    }
530
531    if(i != 22)
532    {
533        printf("error: could not find 22 glyphs in font\n");
534        exit(-1);
535    }
536
537while(cur < 7)
538{
539    /* Try to find 1st letter */
540    distmin = 999999999;
541    for(i = 0; i < 22; i++)
542    {
543        int localmin = 99999999, localx, localy;
544//if(all[i] == 'i') continue;
545        xmin = glyphs[i].xmin;
546        ymin = glyphs[i].ymin;
547        xmax = glyphs[i].xmax;
548        ymax = glyphs[i].ymax;
549        //printf("trying to find %c (%i×%i) - ", all[i], xmax - xmin, ymax - ymin);
550        for(y = -5 * FACTOR; y < 5 * FACTOR; y++)
551            for(x = startx - 5 * FACTOR; x < startx + 5 * FACTOR; x++)
552            {
553                int z, t, dist;
554                dist = 0;
555                for(t = 0; t < ymax - ymin; t++)
556                    for(z = 0; z < xmax - xmin; z++)
557                    {
558                        getgray(font, xmin + z, ymin + t, &r);
559                        getgray(img, x + z, y + t, &r2);
560                        dist += abs(r - r2);
561                    }
562//                printf("%i %i -> %i\n", x, y, dist);
563                //dist /= sqrt(xmax - xmin);
564                dist = dist * 128 / glyphs[i].count;
565                if(dist < localmin)
566                {
567                    localmin = dist;
568                    localx = x;
569                    localy = y;
570                }
571            }
572        //fprintf(stderr, "%i (%i,%i)\n", localmin, localx - startx, localy);
573        if(localmin < distmin)
574        {
575            distmin = localmin;
576            distx = localx;
577            disty = localy;
578            distch = i;
579        }
580    }
581
582    //fprintf(stderr, "%i (%i,%i)\n", distmin, distx - startx, disty);
583    //printf("min diff: %c - %i (%i, %i)\n", all[distch], distmin, distx, disty);
584
585    /* Print min glyph */
586    xmin = glyphs[distch].xmin;
587    ymin = glyphs[distch].ymin;
588    xmax = glyphs[distch].xmax;
589    ymax = glyphs[distch].ymax;
590    for(y = 0; y < ymax - ymin; y++)
591        for(x = 0; x < xmax - xmin; x++)
592        {
593            getpixel(font, xmin + x, ymin + y, &r, &g, &b);
594            if(r > 128) continue;
595            setpixel(dst, distx + x, disty + y, r, g, b);
596        }
597
598    startx = distx + xmax - xmin;
599    result[cur++] = all[distch];
600}
601
602    return dst;
603}
604
605char * slashdot_decode(char *image)
606{
607    struct image *img, *tmp, *tmp2;
608
609    img = load_image(image);
610    if(img == NULL)
611        return NULL;
612
613    result = malloc(8 * sizeof(char));
614//    display(img);
615
616//    tmp = equalize(img);
617//    display(tmp);
618//    tmp = fill_holes(tmp);
619//    display(tmp);
620
621//    dst = median(tmp);
622//tmp = smooth(img);
623tmp = fill_holes(img);
624tmp = median(tmp);
625//tmp = smooth(tmp);
626//display(tmp);
627//tmp = trick(tmp);
628//display(tmp);
629tmp = equalize(tmp);
630//display(tmp);
631
632tmp = detect_lines(img);
633tmp = fill_holes(tmp);
634//tmp = cut_cells(tmp);
635//display_image(tmp);
636
637tmp2 = median(tmp);
638tmp2 = equalize(tmp2);
639count_objects(tmp2);
640//display_image(tmp2);
641
642//tmp = median(tmp);
643tmp = rotate(tmp);
644tmp = median(tmp);
645//display_image(tmp);
646//tmp = equalize(tmp);
647//tmp = cut_cells(tmp);
648//        cvSaveImage(argv[2], tmp);
649
650tmp = find_glyphs(tmp);
651//display_image(tmp);
652
653//        cvSaveImage(argv[3], tmp);
654
655    return result;
656}
657
Note: See TracBrowser for help on using the repository browser.