/**************************************************************************************
IMPORTANT:  READ BEFORE DOWNLOADING, COPYING, INSTALLING OR USING.  
By downloading, copying, installing or using the software you agree 
to this license.  If you do not agree to this license, do not download, 
install, copy or use the software.

Contributors License Agreement

Copyright (c) 2001, Intel Corporation
All rights reserved.

Redistribution and use in source and binary forms, with or without modification, 
are permitted provided that the following conditions are met: 

* Redistributions of source code must retain the above copyright notice, this list 
of conditions and the following disclaimer. 

* Redistributions in binary form must reproduce the above copyright notice, this 
list of conditions and the following disclaimer in the documentation and/or other 
materials provided with the distribution. 

* The name of Contributor may not be used to endorse or promote products derived 
from this software without specific prior written permission. 

THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND 
ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 
WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 
IN NO EVENT SHALL THE  CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT 
OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 
HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 
OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 
SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
***************************************************************************************/

#include "precomp.h"
#include "cvexample.h"


static CvStatus icvPavlidis( uchar* img, int step, CvSize size );


CV_IMPL  void
cvRasterSkeleton( IplImage* image, int method )
{
    static const uchar bit_masks[] = "\x01\x02\x04\x08\x10\x20\x40\x80";

    CV_FUNCNAME("cvRasterSkeleton");

    __BEGIN__;

    CvSize size;
    int    step = 0;
    uchar *img = 0;

    CV_CHECK_MASK_IMAGE( image );
    cvGetImageRawData( image, &img, &step, &size );

    switch( method )
    {
    case CV_SKEL_PAVLIDIS:
        IPPI_CALL( icvPavlidis( img, step, size ));

    default:
        CV_ERROR( CV_StsBadArg, "Incorrect skeleton retrieval method" );
    }

    __END__;
}


static CvStatus icvPavlidis( uchar* img, int step, CvSize size )
{
    uchar  table[256];
    uchar  nval = 2;
    int    width = size.width - 2;
    uchar* img_start = img + step + 1;
    uhcar* img_end = img + (size.height-1)*step + 1;
    int    change_flag;
    int    deltas[4];
    int    skeleton_points = 0;
    int    i0, iters = 0;

    deltas[0] = 1;
    deltas[1] = -step;
    deltas[2] = -1;
    deltas[3] = step;

    memset( table, -1, sizeof(table));

    // build table
    for( i0 = 0; i0 < 256; i0++ )
    {
        int i90 = ((i0 >> 2)|(i0 << 6)) & 0xff;
        int i180 = ((i0 >> 4)|(i0 << 4)) & 0xff;
        int i270 = ((i0 >> 6)|(i0 << 2)) & 0xff;
    
        if( (i0 & 0x11) == 0 && (i0 & 0xe) != 0 && (i0 & 0xe0) != 0)
        {
            /* 9.3(a) first configuration: 0 degree */
            table[i0] = nval;
        }
        else if( (i90 & 0x11) == 0 && (i90 & 0xe) != 0 && (i90 & 0xe0) != 0)
        {
            /* 9.3(a) first configuration: 90 degree */
            table[i0] = nval;
        }
        else if( (i0 & 0x41) == 0 && (i0 & 0xe3) != 0 && (i0 & 0x80) != 0)
        {
            /* 9.3(a) second configuration: 0 degree */
            table[i0] = nval;
        }
        else if( (i90 & 0x41) == 0 && (i90 & 0xe3) != 0 && (i90 & 0x80) != 0)
        {
            /* 9.3(a) second configuration: 90 degree */
            table[i0] = nval;
        }
        else if( (i180 & 0x41) == 0 && (i180 & 0xe3) != 0 && (i180 & 0x80) != 0)
        {
            /* 9.3(a) second configuration: 180 degree */
            table[i0] = nval;
        }
        else if( (i270 & 0x41) == 0 && (i270 & 0xe3) != 0 && (i270 & 0x80) != 0)
        {
            /* 9.3(a) second configuration: 270 degree */
            table[i0] = nval;
        }
    }

    // iterative thinning
    do
    {
        int j; // neighboor index
        change_flag = 0;
        for( j = 0; j < 4; j++ )
        {
            int delta = deltas[j];
            uchar* p;
            for( p = img_start; p < img_end; p += step )
            {
                int x;
                for( x = 0; x < width; x++ )
                {
                    if( p[x] == 1 && p[delta + x] == 0 )
                    {
                        int val = (p[x + 1]&1) + (p[x-step+1]&1)*2 +
                                  (p[x-step]&1)*4 + (p[x-step-1]&1)*8 +
                                  ((p[x-1]&1) + (p[x+step-1]&1)*2 +
                                  (p[x+step]&1)*4 + (p[x+step+1]&1)*8)*16;
                        val = table[val];
                        change_flag |= val;
                        p[x] = (uchar)val;
                    }
                }
            }

            if( change_flag ) // remove all 255-pixels
            {
                for( p = img_start; p < img_end; p += step )
                {
                    int x;
                    for( x = 0; x < width; x++ )
                    {
                        int val = p[x];
                        val &= (val == 255) - 1;
                        p[x] = (uchar)val;
                    }
                }
            }
        }
        change_flag = change_flag == 255;
    }
    while( change_flag != 0 );

    // set non-zero pixels to 255
    uchar* p;
    for( p = img_start; p < img_end; p += step )
    {
        int x;
        for( x = 0; x < width; x++ )
        {
            p[x] = (uchar)(p[x] ? 255 : 0);
        }
    }

    return CV_OK;
}