使用摩尔邻域方法在二维图像中追踪边界
4.71/5 (15投票s)
在二维图像中追踪对象的边界
引言
本文介绍了一种使用摩尔邻域概念在 C++ 中实现边界追踪算法的方法。输出是 2D 图像中对象边界上的连续点集。当前的实现仅支持图像中的单个连通对象。
背景
我需要对图像中一个孔洞对象的边界点进行重采样。我使用了摩尔邻域概念来追踪这个孔洞对象的边界，并使用边界长度的分数来重采样点。输入图像如下所示
Using the Code
输入图像的值假定为背景为 0，前景为 255。
首先，我们需要找到边界的起始像素。为此，我们将逐行遍历图像，并将第一个非零像素指定为边界的起始像素。
然后，我们将使用摩尔邻域方法以顺时针方向追踪边界，直到再次到达起始像素。
算法
- 逐行遍历 2D 矩阵
- 将第一个非零像素设置为 S（边界的起点）
- 将当前像素设置为 p；将此非零像素添加到边界像素列表中
- 将 p 进入的像素设置为 b（回溯像素）
- 获取 p 的 3 * 3 邻域，并从 b 以顺时针方向搜索下一个顺时针非零像素
- 重复步骤 3 到 5，直到 p 与 S 相同
/*
* Description - Get the continuous boundary points
* Parameters
* InputImage - Input image
* Width_i - Width of the image
* Height_i - Height of Image
* BoundaryPoints - Vector of boundary points (output)
*/
void TraceBoundaryPoints::GetContinousBoundaryPoints( unsigned char* InputImage,
int Width_i, int Height_i,
std::vector<Point2D>& BoundaryPoints )
{
int nImageSize = Width_i * Height_i;
if( NULL != InputImage )
{
int Offset[8][2] = {
{ -1, -1 }, // +----------+----------+----------+
{ 0, -1 }, // | | | |
{ 1, -1 }, // |(x-1,y-1) | (x,y-1) |(x+1,y-1) |
{ 1, 0 }, // +----------+----------+----------+
{ 1, 1 }, // |(x-1,y) | (x,y) |(x+1,y) |
{ 0, 1 }, // | | | |
{ -1, 1 }, // +----------+----------+----------+
{ -1, 0 } // | | (x,y+1) |(x+1,y+1) |
}; // |(x-1,y+1) | | |
// +----------+----------+----------+
const int NEIGHBOR_COUNT = 8;
Point2D BoundaryPixelCord;
Point2D BoundaryStartingPixelCord;
Point2D BacktrackedPixelCord;
int BackTrackedPixelOffset[1][2] = { {0,0} };
bool bIsBoundaryFound = false;
bool bIsStartingBoundaryPixelFound = false;
for(int Idx = 0; Idx < nImageSize; ++Idx ) // getting the starting pixel of boundary
{
if( 0 != InputImage[Idx] )
{
BoundaryPixelCord.X = Idx % Width_i;
BoundaryPixelCord.Y = Idx / Width_i;
BoundaryStartingPixelCord = BoundaryPixelCord;
BacktrackedPixelCord.X = ( Idx - 1 ) % Width_i;
BacktrackedPixelCord.Y = ( Idx - 1 ) / Width_i;
BackTrackedPixelOffset[0][0] = BacktrackedPixelCord.X - BoundaryPixelCord.X;
BackTrackedPixelOffset[0][1] = BacktrackedPixelCord.Y - BoundaryPixelCord.Y;
BoundaryPoints.push_back( BoundaryPixelCord );
bIsStartingBoundaryPixelFound = true;
break;
}
}
Point2D CurrentBoundaryCheckingPixelCord;
Point2D PrevBoundaryCheckingPixxelCord;
if( !bIsStartingBoundaryPixelFound )
{
BoundaryPoints.pop_back();
}
while( true && bIsStartingBoundaryPixelFound )
{
int CurrentBackTrackedPixelOffsetInd = -1;
for( int Ind = 0; Ind < NEIGHBOR_COUNT; ++Ind )
{
if( BackTrackedPixelOffset[0][0] == Offset[Ind][0] &&
BackTrackedPixelOffset[0][1] == Offset[Ind][1] )
{
CurrentBackTrackedPixelOffsetInd = Ind;// Finding the bracktracked
// pixel's offset index
break;
}
}
int Loop = 0;
while( Loop < ( NEIGHBOR_COUNT - 1 ) && CurrentBackTrackedPixelOffsetInd != -1 )
{
int OffsetIndex = ( CurrentBackTrackedPixelOffsetInd + 1 ) % NEIGHBOR_COUNT;
CurrentBoundaryCheckingPixelCord.X = BoundaryPixelCord.X + Offset[OffsetIndex][0];
CurrentBoundaryCheckingPixelCord.Y = BoundaryPixelCord.Y + Offset[OffsetIndex][1];
int ImageIndex = CurrentBoundaryCheckingPixelCord.Y * Width_i +
CurrentBoundaryCheckingPixelCord.X;
if( 0 != InputImage[ImageIndex] )// finding the next boundary pixel
{
BoundaryPixelCord = CurrentBoundaryCheckingPixelCord;
BacktrackedPixelCord = PrevBoundaryCheckingPixxelCord;
BackTrackedPixelOffset[0][0] = BacktrackedPixelCord.X - BoundaryPixelCord.X;
BackTrackedPixelOffset[0][1] = BacktrackedPixelCord.Y - BoundaryPixelCord.Y;
BoundaryPoints.push_back( BoundaryPixelCord );
break;
}
PrevBoundaryCheckingPixxelCord = CurrentBoundaryCheckingPixelCord;
CurrentBackTrackedPixelOffsetInd += 1;
Loop++;
}
if( BoundaryPixelCord.X == BoundaryStartingPixelCord.X &&
BoundaryPixelCord.Y == BoundaryStartingPixelCord.Y ) // if the current pixel =
// starting pixel
{
BoundaryPoints.pop_back();
bIsBoundaryFound = true;
break;
}
}
if( !bIsBoundaryFound ) // If there is no connected boundary clear the list
{
BoundaryPoints.clear();
}
}
}
算法的输出如下所示。红色表示追踪的边界。
注意事项
此算法仅适用于封闭区域。如果对象不是封闭的，则需要进行一些预处理操作，例如形态学膨胀或闭合。如果有多个对象，则追踪第一个对象的边界，然后使用边界信息屏蔽该对象，并获取下一个对象，依此类推。OpenCV 库用于加载和显示输入和输出图像。
bwboundaries matlab 函数实现了摩尔邻域追踪算法