wmlbinary2d.cpp

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

    if ( i1 == 0 || i1 == i0 )
        return;

    int iSearch = i1;
    do
    {
        iSearch = aiAssoc[iSearch];
    }
    while ( iSearch != i1 && iSearch != i0 );

    if ( iSearch == i1 )
    {
        int iSave = aiAssoc[i0];
        aiAssoc[i0] = aiAssoc[i1];
        aiAssoc[i1] = iSave;
    }
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// L1 Distance Transform.
//
// This distance is also known as the "city block" distance or whatever.
// North, South, East, and West neighbors are 1 unit away.  NorthWest,
// NorthEast, SouthWest, and SouthEast neighbors are 2 units away.
//----------------------------------------------------------------------------
void Binary2D::GetL1Distance (int& riMaxDistance,
    ImageInt2D& rkTransform) const
{
    // Create a temporary copy of image to store intermediate information
    // during distance calculations.  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 );
    }

    GetL1DistanceZeroBoundary(riMaxDistance,kTemp);    

    // pack transformed image in smaller size output
    for (iY = 0; iY < rkTransform.GetBound(1); iY++)
    {
        for (iX = 0; iX < rkTransform.GetBound(0); iX++)
            rkTransform(iX,iY) = kTemp(iX+1,iY+1);
    }
}
//----------------------------------------------------------------------------
void Binary2D::GetL1DistanceZeroBoundary (int& riMaxDistance,
    ImageInt2D& rkTemp) const
{
    bool bChangeMade = true;
    int iDistance;
    for (iDistance = 1; bChangeMade; iDistance++)
    {
        bChangeMade = false;
        int iDistanceP1 = iDistance + 1;
        for (int iY = 1; iY+1 < rkTemp.GetBound(1); iY++)
        {
            for (int iX = 1; iX+1 < rkTemp.GetBound(0); iX++)
            {
                if ( rkTemp(iX,iY) == iDistance )
                {
                    if ( rkTemp(iX-1,iY) >= iDistance
                    &&   rkTemp(iX+1,iY) >= iDistance
                    &&   rkTemp(iX,iY-1) >= iDistance
                    &&   rkTemp(iX,iY+1) >= iDistance )
                    {
                        rkTemp(iX,iY) = iDistanceP1;
                        bChangeMade = true;
                    }
                }
            }
        }
    }

    riMaxDistance = iDistance;
}
//----------------------------------------------------------------------------

//----------------------------------------------------------------------------
// L2 Distance Transform (Euclidean Distance Transform)
//
// This program calculates the Euclidean distance transform of a binary
// input image.  The adaptive algorithm is guaranteed to give exact
// distances for all distances < 100.  Algorithm sent to me by John Gauch.
//
// From: John Gauch <[e-mail]>
// The basic idea is similar to a EDT described recently in PAMI by Laymarie
// from McGill.  By keeping the dx and dy offset to the nearest edge (feature)
// point in the image, we can search to see which dx dy is closest to a given
// point by examining a set of neighbors.  The Laymarie method (and Borgfors)
// look at a fixed 3x3 or 5x5 neighborhood and call it a day.  What we did was
// calculate (painfully) what neighborhoods you need to look at to guarentee
// that the exact distance is obtained.  Thus, you will see in the code, that
// we L2Check the current distance and depending on what we have so far, we
// extend the search region.  Since our algorithm for L2Checking the exactness
// of each neighborhood is on the order N^4, we have only gone to N=100.  In
// theory, you could make this large enough to get all distances exact.  We
// have implemented the algorithm to get all distances < 100 to be exact. 
//----------------------------------------------------------------------------
void Binary2D::GetL2Distance (double& rdMaxDistance,
    ImageDouble2D& rkTransform) const
{
    ImageInt2D kXNear(GetBound(0),GetBound(1));
    ImageInt2D kYNear(GetBound(0),GetBound(1));
    ImageInt2D kDist(GetBound(0),GetBound(1));

    L2Initialize(kXNear,kYNear,kDist);
    L2XpYp(kXNear,kYNear,kDist);
    L2XmYm(kXNear,kYNear,kDist);
    L2XpYm(kXNear,kYNear,kDist);
    L2XmYp(kXNear,kYNear,kDist);
    L2Finalize(kDist,rdMaxDistance,rkTransform);
}
//----------------------------------------------------------------------------
void Binary2D::L2Initialize (ImageInt2D& rkXNear,
    ImageInt2D& rkYNear, ImageInt2D& rkDist) const
{
    for (int iY = 0; iY < GetBound(1); iY++)
    {
        for (int iX = 0; iX < GetBound(0); iX++)
        {
            if ( (*this)(iX,iY) != 0 )
            {
                rkXNear(iX,iY) = 0;
                rkYNear(iX,iY) = 0;
                rkDist(iX,iY) = INT_MAX;
            }
            else
            {
                rkXNear(iX,iY) = iX;
                rkYNear(iX,iY) = iY;
                rkDist(iX,iY) = 0;
            }
        }
    }
}
//----------------------------------------------------------------------------
void Binary2D::L2Check (int iX, int iY, int iDx, int iDy,
    ImageInt2D& rkXNear, ImageInt2D& rkYNear, ImageInt2D& rkDist) const
{
    int iXp = iX + iDx, iYp = iY + iDy;

    if ( 0 <= iXp && iXp < GetBound(0)
    &&   0 <= iYp && iYp < GetBound(1) )
    {
        if ( rkDist(iXp,iYp) < rkDist(iX,iY) )
        {
            int iDx0 = rkXNear(iXp,iYp) - iX;
            int iDy0 = rkYNear(iXp,iYp) - iY;
            int iNewDist = iDx0*iDx0 + iDy0*iDy0;
            if ( iNewDist < rkDist(iX,iY) )
            {
                rkXNear(iX,iY) = rkXNear(iXp,iYp);
                rkYNear(iX,iY) = rkYNear(iXp,iYp);
                rkDist(iX,iY) = iNewDist;
            }
        }
    }
}
//----------------------------------------------------------------------------
void Binary2D::L2XpYp (ImageInt2D& rkXNear, ImageInt2D& rkYNear,
    ImageInt2D& rkDist) const
{
    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 = 0; iY < GetBound(1); iY++)
    {
        for (int iX = 0; iX < GetBound(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::L2XpYm (ImageInt2D& rkXNear, ImageInt2D& rkYNear,
    ImageInt2D& rkDist) const
{
    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 = 0; iX < GetBound(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::L2XmYp (ImageInt2D& rkXNear, ImageInt2D& rkYNear,
    ImageInt2D& rkDist) const
{
    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 = 0; iY < GetBound(1); 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::L2XmYm (ImageInt2D& rkXNear, ImageInt2D& rkYNear,
    ImageInt2D& rkDist) const