/* minidjvu - library for handling bilevel images with DjVuBitonal support

 *

 * frames.c - extracting frameworks and calculating "importance rating"

 *

 * Copyright (C) 2005  Ilya Mezhirov

 *

 * This program is free software; you can redistribute it and/or modify

 * it under the terms of the GNU General Public License as published by

 * the Free Software Foundation; either version 2 of the License, or

 * (at your option) any later version.

 *

 * This program is distributed in the hope that it will be useful,

 * but WITHOUT ANY WARRANTY; without even the implied warranty of

 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

 * GNU General Public License for more details.

 *

 * You should have received a copy of the GNU General Public License

 * along with this program; if not, write to the Free Software

 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

 *

 * 

 * minidjvu is derived from DjVuLibre (http://djvu.sourceforge.net)

 * All over DjVuLibre there is a patent alert from LizardTech

 * which I guess I should reproduce (don't ask me what does this mean):

 * 

 *  ------------------------------------------------------------------

 * | DjVu (r) Reference Library (v. 3.5)

 * | Copyright (c) 1999-2001 LizardTech, Inc. All Rights Reserved.

 * | The DjVu Reference Library is protected by U.S. Pat. No.

 * | 6,058,214 and patents pending.

 * |

 * | This software is subject to, and may be distributed under, the

 * | GNU General Public License, either Version 2 of the license,

 * | or (at your option) any later version. The license should have

 * | accompanied the software or you may obtain a copy of the license

 * | from the Free Software Foundation at http://www.fsf.org .

 * |

 * | The computer code originally released by LizardTech under this

 * | license and unmodified by other parties is deemed "the LIZARDTECH

 * | ORIGINAL CODE."  Subject to any third party intellectual property

 * | claims, LizardTech grants recipient a worldwide, royalty-free, 

 * | non-exclusive license to make, use, sell, or otherwise dispose of 

 * | the LIZARDTECH ORIGINAL CODE or of programs derived from the 

 * | LIZARDTECH ORIGINAL CODE in compliance with the terms of the GNU 

 * | General Public License.   This grant only confers the right to 

 * | infringe patent claims underlying the LIZARDTECH ORIGINAL CODE to 

 * | the extent such infringement is reasonably necessary to enable 

 * | recipient to make, have made, practice, sell, or otherwise dispose 

 * | of the LIZARDTECH ORIGINAL CODE (or portions thereof) and not to 

 * | any greater extent that may be necessary to utilize further 

 * | modifications or combinations.

 * |

 * | The LIZARDTECH ORIGINAL CODE is provided "AS IS" WITHOUT WARRANTY

 * | OF ANY KIND, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED

 * | TO ANY WARRANTY OF NON-INFRINGEMENT, OR ANY IMPLIED WARRANTY OF

 * | MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.

 * +------------------------------------------------------------------

 */

/* Frameworks are funny things...

 * The algorithm is to be commented yet.

 * Here's a picture illustrating what is a frame

 * (view with monospace font):

 *

 *  Original letter:        Its framework:

 *

  .....@@@@@@@@........ .....................

  ...@@@@@@@@@@@@...... ......@@@@@..........

  ..@@@@@@@@@@@@@@..... .....@@...@@@........

  ..@@@@@...@@@@@@@.... ....@@......@@.......

  ..@@@@.....@@@@@@.... ....@........@.......

  .@@@@@.....@@@@@@.... ....@........@.......

  .@@@@@.....@@@@@@.... ....@........@.......

  ..@@@@.....@@@@@@.... ....@........@.......

  ..........@@@@@@@.... .............@.......

  .......@@@@@@@@@@.... .............@.......

  .....@@@@@@@@@@@@.... ........@@@@@@.......

  ...@@@@@@@@@@@@@@.... ......@@@....@.......

  ..@@@@@@@..@@@@@@.... .....@@......@.......

  .@@@@@@....@@@@@@.... ...@@@.......@.......

  .@@@@@.....@@@@@@.... ...@.........@.......

  @@@@@......@@@@@@.... ..@@.........@.......

  @@@@@......@@@@@@.... ..@..........@.......

  @@@@@.....@@@@@@@.... ..@..........@.......

  @@@@@@....@@@@@@@.@@@ ..@@.........@.......

  .@@@@@@@@@@@@@@@@@@@@ ...@@.....@@@@@......

  .@@@@@@@@@@@@@@@@@@@@ ....@@..@@@...@@@@@..

  ..@@@@@@@@@.@@@@@@@@. .....@@@@............

  ....@@@@@....@@@@@... .....................

 * A letter is converted into grayshades,

 *   and a frame is the set of its purely black pixels after the transformation.

 * In the grayshade version of a letter,

 *   all pixels that were white remain absolutely white,

 *   the frame is black and the blackness falls down from it to the border.

 */

/* Offtopic: I wonder if this thing could help OCRing because frameworks

 * perfectly retain readability while becoming essentially 1-dimensional.

 */

#include "mdjvucfg.h"

#include "minidjvu.h"

#include <stdlib.h>

#include <assert.h>

#include <string.h>

#include <math.h>

/* Stuff for not using malloc in C++

 * (made by Leon Bottou; has no use in minidjvu,

 * but left here for potential DjVuLibre compatibility)

 */

#ifdef __cplusplus

# define MALLOC(Type)    new Type

# define FREE(p)         delete p

# define MALLOCV(Type,n) new Type[n]

# define FREEV(p)        delete [] p

#else

# define MALLOC(Type)    ((Type*)malloc(sizeof(Type)))

# define FREE(p)         do{if(p)free(p);}while(0)

# define MALLOCV(Type,n) ((Type*)malloc(sizeof(Type)*(n)))

# define FREEV(p)        do{if(p)free(p);}while(0)

#endif

/* This determines the gray level of the border (ratio of black).

 * Setting it to 1 will effectively eliminate grayshading.

 */

#define BORDER_FALLOFF .7 /* this is the main constant in all the matcher... */

typedef unsigned char byte;

static int donut_connectivity_test(byte *upper, byte *row, byte *lower)/*{{{*/

{

    /*(on the pictures below 0 is white, 1 is black or gray)

     *

     * 01.

     * 1 . -> 1

     * ...

     *

     * .0.

     * 1 1 ->  1

     * .0.

     *

     * all others -> 0

     */

    int sum, l, u, d, r;

    sum = (u = *upper ? 1 : 0) + (d = *lower ? 1 : 0) +

          (l = row[-1] ? 1 : 0) + (r = row[1] ? 1 : 0);

    switch(sum)

    {

        case 3:/*{{{*/

        {

            int x = 6 - (u + (l << 1) + d + (d << 1));

            switch(x)

            {

                case 0: /* l */

                    return upper[-1] && lower[-1] ? 0 : 1;

                case 1: /* d */

                    return lower[-1] && lower[1] ? 0 : 1;

                case 2: /* r */

                    return upper[1] && lower[1] ? 0 : 1;

                case 3: /* u */

                    return upper[-1] && upper[1] ? 0 : 1;

                default: assert(0); return 0;

            }

        }

        break;/*}}}*/

        case 2:/*{{{*/

        {

            int s = l + r;

            if (s & 1)

            {

                /*   A1.

                 *   1 0 - should be !A (2x2 square extermination)

                 *   .0.

                 */

                if (l)

                {

                    if (u)

                        return upper[-1] ? 0 : 1;

                    else

                        return lower[-1] ? 0 : 1;

                }

                else /* r */

                {

                    if (u)

                        return upper[1] ? 0 : 1;

                    else

                        return lower[1] ? 0 : 1;

                }

            }

            else

            {

                /*   .0.

                 *   1 1 - surely should be 1 to preserve connection

                 *   .0.

                 */

                return 1;

            }

        }

        break;/*}}}*/

        case 0: case 4:

            return 1;

        case 1:

            return 0;

        default: assert(0); return 0;

    }

    assert(0); return 0;

}/*}}}*/

static byte donut_transform_pixel(byte *upper, byte *row, byte *lower)/*{{{*/

{

    /* (center pixel should be gray in order for this to work)

     * (on the pictures below 0 is white, 1 is black or gray)

     *

     * 01.

     * 1 . -> center will become 1

     * ...

     *

     * .0.

     * 1 1 -> center will become 1

     * .0.

     *

     * 00.

     * 1 0 -> center will become 1

     * .0.

     *

     * 1..

     * 1 0 -> center will become 0

     * 1..

     *

     * 11.

     * 1 0 -> center will become 0

     * .0.

     *

     * .A.

     * A A -> center will become 1

     * .A.

     */

    int sum, l, u, d, r;

    if (!*row) return 0;

    sum = (u = *upper ? 1 : 0) + (d = *lower ? 1 : 0) +

          (l = row[-1] ? 1 : 0) + (r = row[1] ? 1 : 0);

    switch(sum)

    {

        case 1: case 3:/*{{{*/

        {

            int x = u + (l << 1) + d + (d << 1);

            if (sum == 3) x = (6 - x) ^ 2;

            switch(x)

            {

                case 0: /* r */

                    return upper[1] && lower[1] ? 0 : 1;

                case 1: /* u */

                    return upper[-1] && upper[1] ? 0 : 1;

                case 2: /* l */

                    return upper[-1] && lower[-1] ? 0 : 1;

                case 3: /* d */

                    return lower[-1] && lower[1] ? 0 : 1;

                default: assert(0); return 0;

            }

        }

        break;/*}}}*/

        case 2:/*{{{*/

        {

            int s = l + r;

            if (s & 1)

            {

                /*   A1.

                 *   1 0 - should be !A (2x2 square extermination)

                 *   .0.

                 */

                if (l)

                {

                    if (u)

                        return upper[-1] ? 0 : 1;

                    else

                        return lower[-1] ? 0 : 1;

                }

                else /* r */

                {

                    if (u)

                        return upper[1] ? 0 : 1;

                    else

                        return lower[1] ? 0 : 1;

                }

            }

            else

            {

                /*   .0.

                 *   1 1 - surely should be 1 to preserve connection

                 *   .0.

                 */

                return 1;

            }

        }

        break;/*}}}*/

        case 0: case 4:

            return 1; /* lone pixels are NOT omitted */

        default: assert(0); return 0;

    }

    assert(0); return 0;

}/*}}}*/

/* `pixels' should have a margin of 1 pixel at each side

 * returns true if the image was changed

 */

static int flay(byte **pixels, int w, int h, int rank, int **ranks)

{

    int i, j, result = 0;

    byte *buf = MALLOCV(byte, w * h);

    assert(pixels);

    assert(w);

    assert(h);

    for (i = 0; i < h; i++) for (j = 0; j < w; j++)

    {

        buf[w * i + j] =

            donut_transform_pixel(pixels[i-1] + j, pixels[i] + j, pixels[i+1] + j);

    }

    for (i = 0; i < h; i++)

    {

        byte *up = pixels[i-1], *row = pixels[i], *dn = pixels[i+1];

        byte *buf_row = buf + w * i;

        int *rank_row = NULL;

        if (ranks) rank_row = ranks[i];

        for (j = 0; j < w; j++)

        {

            if (row[j] && !buf_row[j])

            {

                if (!donut_connectivity_test(up + j, row + j, dn + j))

                {

                    row[j] = buf_row[j];

                    if (rank) rank_row[j] = rank;

                    result = 1;

                }

            }

            else

                row[j] = buf_row[j];

        }

    }

    FREEV(buf);

    return result;

}

/* TODO: use less temporary buffers and silly copyings */

MDJVU_IMPLEMENT void mdjvu_soften_pattern(byte **result, byte **pixels, int32 w, int32 h)/*{{{*/

{

    byte *r = MALLOCV(byte, (w + 2) * (h + 2));

    byte **pointers = MALLOCV(byte *, h + 2);

    int *ranks_buf = MALLOCV(int, w * h);

    int **ranks = MALLOCV(int *, h);

    int i, j, passes = 1;

    double level = 1, falloff;

    byte *colors;

    memset(r, 0, (w + 2) * (h + 2));

    memset(ranks_buf, 0, w * h * sizeof(int));

    for (i = 0; i < h + 2; i++)

        pointers[i] = r + (w + 2) * i + 1;

    for (i = 0; i < h; i++)

        memcpy(pointers[i+1], pixels[i], w);

    for (i = 0; i < h; i++)

        ranks[i] = ranks_buf + w * i;

    while(flay(pointers + 1, w, h, passes, ranks)) passes++;

    colors = MALLOCV(byte, passes + 1);

    falloff = pow(BORDER_FALLOFF, 1./passes);

    for (i = 0; i < passes; i++)

    {

        colors[i] = (byte) (level * 255);

        level *= falloff;

    }

    /* TODO: test the next line */

    /* colors[passes - 1] = 50; pay less attention to border pixels */

    colors[passes] = 0;

    pointers++;

    for (i = 0; i < h; i++)

    {

        for (j = 0; j < w; j++)

        {

            if (pointers[i][j])

            {

                result[i][j] = 255;

            }

            else

            {

                result[i][j] = colors[passes - ranks[i][j]];

            }

        }

    }

    pointers--;

    FREEV(colors);

    FREEV(ranks);

    FREEV(ranks_buf);

    FREEV(r);

    FREEV(pointers);

}/*}}}*/