wmlbinary2d.cpp

来自「3D Game Engine Design Source Code非常棒」· C++ 代码 · 共 985 行 · 第 1/3 页

{
    const int iK1 = 1;
    const int iK2 = 169;   // 13^2
    const int iK3 = 961;   // 31^2
    const int iK4 = 2401;  // 49^2
    const int iK5 = 5184;  // 72^2

    for (int iY = GetBound(1)-1; iY >= 0; iY--)
    {
        for (int iX = GetBound(0)-1; iX >= 0; iX--)
        {
            int iDist = rkDist(iX,iY);
            if ( iDist > iK1 )
            { 
                L2Check(iX,iY,1,0,rkXNear,rkYNear,rkDist); 
                L2Check(iX,iY,1,1,rkXNear,rkYNear,rkDist); 
                L2Check(iX,iY,0,1,rkXNear,rkYNear,rkDist); 
            }
            if ( iDist > iK2 )
            { 
                L2Check(iX,iY,2,1,rkXNear,rkYNear,rkDist); 
                L2Check(iX,iY,1,2,rkXNear,rkYNear,rkDist); 
            }
            if ( iDist > iK3 )
            { 
                L2Check(iX,iY,3,1,rkXNear,rkYNear,rkDist); 
                L2Check(iX,iY,3,2,rkXNear,rkYNear,rkDist); 
                L2Check(iX,iY,2,3,rkXNear,rkYNear,rkDist); 
                L2Check(iX,iY,1,3,rkXNear,rkYNear,rkDist); 
            }
            if ( iDist > iK4 )
            { 
                L2Check(iX,iY,4,1,rkXNear,rkYNear,rkDist); 
                L2Check(iX,iY,4,3,rkXNear,rkYNear,rkDist); 
                L2Check(iX,iY,3,4,rkXNear,rkYNear,rkDist); 
                L2Check(iX,iY,1,4,rkXNear,rkYNear,rkDist); 
            }
            if ( iDist > iK5 )
            { 
                L2Check(iX,iY,5,1,rkXNear,rkYNear,rkDist); 
                L2Check(iX,iY,5,2,rkXNear,rkYNear,rkDist); 
                L2Check(iX,iY,5,3,rkXNear,rkYNear,rkDist); 
                L2Check(iX,iY,5,4,rkXNear,rkYNear,rkDist);
                L2Check(iX,iY,4,5,rkXNear,rkYNear,rkDist); 
                L2Check(iX,iY,2,5,rkXNear,rkYNear,rkDist); 
                L2Check(iX,iY,3,5,rkXNear,rkYNear,rkDist); 
                L2Check(iX,iY,1,5,rkXNear,rkYNear,rkDist); 
            }
        }
    }
}
//----------------------------------------------------------------------------
void Binary2D::L2Finalize (const ImageInt2D& rkDist, double& rdMaxDistance,
    ImageDouble2D& rkTransform) const
{
    rdMaxDistance = 0.0;
    for (int iY = 0; iY < GetBound(1); iY++)
    {
        for (int iX = 0; iX < GetBound(0); iX++)
        {
            double dDist = Mathd::Sqrt(rkDist(iX,iY));
            if ( dDist > rdMaxDistance )
                rdMaxDistance = dDist;

            rkTransform(iX,iY) = dDist;
        }
    }
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// Skeletonization.
//
// Boundary pixels are trimmed from the object one layer at a time based on
// their adjacency to interior pixels.  At each step the connectivity and
// cycles of the object are preserved.
//----------------------------------------------------------------------------
void Binary2D::GetSkeleton (ImageInt2D& rkSkeleton) const
{
    // Create a temporary copy of image to store intermediate information
    // during skeletonization.  The original image is embedded in an
    // image with two more rows and two more columns so that the image
    // boundary pixels are properly handled.
    ImageInt2D kTemp(GetBound(0)+2,GetBound(1)+2);  // initially zero
    int iX, iY, iXP, iYP;
    for (iY = 0, iYP = 1; iY < GetBound(1); iY++, iYP++)
    {
        for (iX = 0, iXP = 1; iX < GetBound(0); iX++, iXP++)
            kTemp(iXP,iYP) = ( (*this)(iX,iY) ? 1 : 0 );
    }

    Trim4(kTemp);
    Trim3(kTemp);
    Trim2(kTemp);

    // pack skeleton in smaller size output
    for (iY = 0, iYP = 1; iY < rkSkeleton.GetBound(1); iY++, iYP++)
    {
        for (iX = 0, iXP = 1; iX < rkSkeleton.GetBound(0); iX++, iXP++)
            rkSkeleton(iX,iY) = ( kTemp(iXP,iYP) ? 1 : 0 );
    }
}
//----------------------------------------------------------------------------
bool Binary2D::Interior2 (ImageInt2D& rkImage, int iX, int iY)
{
    bool b1 = rkImage(iX,iY-1) > 0;
    bool b3 = rkImage(iX+1,iY) > 0;
    bool b5 = rkImage(iX,iY+1) > 0;
    bool b7 = rkImage(iX-1,iY) > 0;
    return (b1 && b3) || (b3 && b5) || (b5 && b7) || (b7 && b1);
}
//----------------------------------------------------------------------------
bool Binary2D::Interior3 (ImageInt2D& rkImage, int iX, int iY)
{
    int iNbrs = 0;
    if ( rkImage(iX-1,iY) > 0 ) iNbrs++;
    if ( rkImage(iX+1,iY) > 0 ) iNbrs++;
    if ( rkImage(iX,iY-1) > 0 ) iNbrs++;
    if ( rkImage(iX,iY+1) > 0 ) iNbrs++;
    return iNbrs == 3;
}
//----------------------------------------------------------------------------
bool Binary2D::Interior4 (ImageInt2D& rkImage, int iX, int iY)
{
    return rkImage(iX-1,iY) > 0
        && rkImage(iX+1,iY) > 0
        && rkImage(iX,iY-1) > 0
        && rkImage(iX,iY+1) > 0;
}
//----------------------------------------------------------------------------
bool Binary2D::MarkInterior (ImageInt2D& rkImage, int iValue,
    InteriorFunction oIsInterior)
{
    bool bNoInterior = true;

    for (int iY = 0; iY < rkImage.GetBound(1); iY++)
    {
        for (int iX = 0; iX < rkImage.GetBound(0); iX++)
        {
            if ( rkImage(iX,iY) > 0 )
            {
                if ( oIsInterior(rkImage,iX,iY) )
                {
                    rkImage(iX,iY) = iValue;
                    bNoInterior = false;
                }
                else
                {
                    rkImage(iX,iY) = 1;
                }
            }
        }
    }

    return bNoInterior;
}
//----------------------------------------------------------------------------
bool Binary2D::IsArticulation (ImageInt2D& rkImage, int iX, int iY)
{
    static int s_aiArticulation[256] =
    {
        0,0,0,0,0,1,0,0,0,1,0,0,0,1,0,0,
        0,1,1,1,1,1,1,1,0,1,0,0,0,1,0,0,
        0,1,1,1,1,1,1,1,0,1,0,0,0,1,0,0,
        0,1,1,1,1,1,1,1,0,1,0,0,0,1,0,0,
        0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
        1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
        0,1,1,1,1,1,1,1,0,1,0,0,0,1,0,0,
        0,1,1,1,1,1,1,1,0,1,0,0,0,1,0,0,
        0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0,
        1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,0,
        0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,
        0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,
        0,0,0,0,1,1,0,0,1,1,0,0,1,1,0,0,
        1,1,1,1,1,1,1,1,1,1,0,0,1,1,0,0,
        0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,
        0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0
    };

    // Converts 8 neighbors of pixel (x,y) to an 8-bit value, bit = 1 iff
    // pixel is set.
    int iByte = 0;
    if ( rkImage(iX-1,iY-1) )  iByte |= 0x01;
    if ( rkImage(iX,  iY-1) )  iByte |= 0x02;
    if ( rkImage(iX+1,iY-1) )  iByte |= 0x04;
    if ( rkImage(iX+1,iY  ) )  iByte |= 0x08;
    if ( rkImage(iX+1,iY+1) )  iByte |= 0x10;
    if ( rkImage(iX  ,iY+1) )  iByte |= 0x20;
    if ( rkImage(iX-1,iY+1) )  iByte |= 0x40;
    if ( rkImage(iX-1,iY  ) )  iByte |= 0x80;

    return s_aiArticulation[iByte] == 1;
}
//----------------------------------------------------------------------------
bool Binary2D::ClearInteriorAdjacent (ImageInt2D& rkImage, int iValue)
{
    bool bNoRemoval = true;

    for (int iY = 0; iY < rkImage.GetBound(1); iY++)
    {
        for (int iX = 0; iX < rkImage.GetBound(0); iX++)
        {
            if ( rkImage(iX,iY) == 1 )
            {
                bool bInteriorAdjacent =
                    rkImage(iX-1,iY-1) == iValue ||
                    rkImage(iX  ,iY-1) == iValue ||
                    rkImage(iX+1,iY-1) == iValue ||
                    rkImage(iX+1,iY  ) == iValue ||
                    rkImage(iX+1,iY+1) == iValue ||
                    rkImage(iX  ,iY+1) == iValue ||
                    rkImage(iX-1,iY+1) == iValue ||
                    rkImage(iX-1,iY  ) == iValue;

                if ( bInteriorAdjacent && !IsArticulation(rkImage,iX,iY) )
                {
                    rkImage(iX,iY) = 0;
                    bNoRemoval = false;
                }
            }
        }
    }

    return bNoRemoval;
}
//----------------------------------------------------------------------------
void Binary2D::Trim4 (ImageInt2D& rkImage)
{
    while ( true )
    {
        if ( MarkInterior(rkImage,4,Interior4) )
        {
            // No interior pixels, trimmed set is at most 2-pixels thick.
            break;
        }

        if ( ClearInteriorAdjacent(rkImage,4) )
        {
            // All remaining interior pixels are either articulation points
            // or part of blobs whose boundary pixels are all articulation
            // points.  An example of the latter case is shown below.  The
            // background pixels are marked with '.' rather than '0' for
            // readability.  The interior pixels are marked with '4' and the
            // boundary pixels are marked with '1'.
            //
            //   .........
            //   .....1...
            //   ..1.1.1..
            //   .1.141...
            //   ..14441..
            //   ..1441.1.
            //   .1.11.1..
            //   ..1..1...
            //   .........
            //
            // This is a pathological problem where there are many small holes
            // (0-pixel with north, south, west, and east neighbors all
            // 1-pixels) that your application can try to avoid by an initial
            // pass over the image to fill in such holes.  Of course, you do
            // have problems with checkerboard patterns...
            break;
        }
    }
}
//----------------------------------------------------------------------------
void Binary2D::Trim3 (ImageInt2D& rkImage)
{
    while ( true )
    {
        if ( MarkInterior(rkImage,3,Interior3) )
        {
            // No interior pixels, trimmed set is at most 2-pixels thick.
            break;
        }

        if ( ClearInteriorAdjacent(rkImage,3) )
        {
            // All remaining 3-values can be safely removed since they are
            // not articulation points and the removal will not cause new
            // holes.
            for (int iY = 0; iY < rkImage.GetBound(1); iY++)
            {
                for (int iX = 0; iX < rkImage.GetBound(0); iX++)
                {
                    if ( rkImage(iX,iY) == 3
                    &&   !IsArticulation(rkImage,iX,iY) )
                    {
                        rkImage(iX,iY) = 0;
                    }
                }
            }
            break;
        }
    }
}
//----------------------------------------------------------------------------
void Binary2D::Trim2 (ImageInt2D& rkImage)
{
    while ( true )
    {
        if ( MarkInterior(rkImage,2,Interior2) )
        {
            // No interior pixels, trimmed set is at most 1-pixel thick.
            // Call it a skeleton.
            break;
        }

        if ( ClearInteriorAdjacent(rkImage,2) )
        {
            // Removes 2-values that are not articulation points.
            for (int iY = 0; iY < rkImage.GetBound(1); iY++)
            {
                for (int iX = 0; iX < rkImage.GetBound(0); iX++)
                {
                    if ( rkImage(iX,iY) == 2
                    &&   !IsArticulation(rkImage,iX,iY) )
                    {
                        rkImage(iX,iY) = 0;
                    }
                }
            }
            break;
        }
    }
}
//----------------------------------------------------------------------------