Split a Single-Pixel-Width Connected Line Graph Into Line Segments by The Hit-and-Miss Transformation

• Download source files - 18.4 KB
• Download demo project - 13.6 KB

An algorithm is proposed to split a single-pixel-width connected line graph into line segments by the Hit-and-Miss transformation (HMT). Firstly, junction points and free end points are detected by a set of HMTs. Then, line segments are traced between junctions and free ends. The algorithm has been implemented in C#.

1. Introduction

1.1 Line Graph and Line Segments

A single-pixel-width connected line graph (Figure 1 (a)) can be obtained by thinning [1] (thinning algorithm is not in the source codes) a black-and-white silhouette (Figure 1 (b)). The line segments are the basic components of the graph. Therefore, it has attracted much interest to split the graph into line segments. Nevertheless, it is not an easy task as it sounds.

(a) (b)

Figure 1 (a) Example silhouette (b) thinning result, i.e., the single-pixel-width connected line graph

1.2 Challenges

Before going to the Hit-and-Miss transformation, the following strategy sounds facilely. Since the graph is connected, we can start from any free end, trace along the line segments, save the line segment and start multi-trace when it comes to a junction. Nevertheless, it is far more difficult and complex than I thought to design comprehensive rules for detecting a junction, or starting multi-line segments tracing. It is because the graph is connected by an 8-connected relationship.

In lattice image morphological theory, there are two simple neighbour relationships of the contiguous pixels. Figure 2(a) depicts a 4-connected relationship, while Figure 2 (b) depicts an 8-connected relationship. (Note that line segments are in black and the background is white. Colourful figures are for display and illustration purpose.)

(a) (b)

Figure 2 (a) Four blue pixels are 4-connected neighbours of the red pixel (b) Eight green pixels are 8-connected neighbours of the red pixel.

If the graph is connected by an 8-connected relationship, it is not always the case that only the pixel having only two neighbours is part of a line segment stem, or the pixel is a junction if it has more than two neighbours. Figure 3 (a) shows an L-shape line segment, of which the red pixels have three neighbours according 8-connected relationship. But they cannot be regarded as junctions. Figure 3 (b) shows a cross graph, which should be split into four line segments. Only the red pixel should be detected as a junction, even though the blue pixels also have more than two neighbours. Figure 3 (c) shows another scenario where the number of the neighbours again is not capable of correctly detecting the line segment stem and junctions. Though it is possible to labour a set of comprehensive rules to handle the above scenarios, Hit-and-Miss transformation can easily detect free ends of the line segments and the junctions, by which it is then a piece of cake to split the graph into line segments.

(a) (b) (c)

Figure 3 (a) L-shape line segment (b) cross-figure graph (c) another scenario

1.3 Hit-and-Miss Transform

The Hit-and-Miss transform is a basic binary morphological operation, which is generally used to detect particular patterns in a black-and-white image. The template, a.k.a., kernel, which is a small matrix, defines the particular patterns, with 1 meaning foreground pixel, 0 meaning background pixel, and "don't care" pixels. For an instance, Figure 4 (a) gives a T-junction template. The template slides on the input binary image pixel-wise, does AND operation for all the pixels inside template that expect those "don't care's". The corresponding pixel in the output binary image is set as the outcome of the "binary convolution". "True" means the template is exactly matched. For more of Hit-and-Miss transformation, please refer to the articles on CVOnline.

2. Algorithm

2.1 Detect Junctions

Triple junction is a basic junction type. Figure 4 (a), (b) and (c) give three type of triple junction templates. By rotating Figure 4 (a) and (b) clockwise 90, 180, and 270 degrees, there are four Type1 and Type2 triple junction templates, respectively. By rotating Figure 4 (c) clockwise 45, 90, 135, ... and 315 degrees, there are eight Type3 triple junction templates. Note that there is no "0" element in these templates, so the Hit-and-Miss transformation (HMT) is done by an AndTrue2D operation, illustrated in Section 3.1.

(a) (b) (c)

Figure 4 (a) Type1 triple junction (T-junction) template (b) Type2 triple junction template (c) Type 3 triple junction template. Red pixels indicate foreground pixels. White pixels indicate "don't care" pixels.

To solve the scenario as shown in Figure 3 (b) and (c), one more type of templates (Type4 as shown in Figure 5) is designed to detect the blue pixels and reject them as junctions. Also, by rotating clockwise every 90 degrees, there are four Type4 removal templates. There are "0" elements in this type of templates, and "don't care" as well, so the Hit-and-Miss transformation (HMT) is done by an AndTrueFalseDontCare2D operation, illustrated in Section 3.3.

Figure 5: Type4 removal template. Red pixels indicate foreground. Blue pixels indicate background. White pixels indicate "don't care's".

The algorithm of detecting junctions is:

Algorithm 1: Detect Junctions

1. Apply HMT (AndTrue2D) for each Type1 templates
2. Apply HMT (AndTrue2D) for each Type2 and Type3 templates
3. Apply HMT (AndTrueFalseDontCare2D) for each Type4 templates
4. OR the outcomes of step 1 and step 2
5. XOR the outcome of step 4 with the outcomes of step 3

Source Code Snippet: part of JunctionDetector.Apply()

List<bool[,]> junctionMatrixList = new List<bool[,]>(16);
// AndTrue operations with 4 Type1 kernels, T-junction
for (int i = 0; i < 4; i ++)
    junctionMatrixList.Add(HitAndMissTransformation.AndTrue2D(srcBoolMatrix,
                          (bool[,])_kernelType1List[i]));
// AndTrue operation with 4 Type2 kernels
for (int i = 0; i < 4; i ++)
    junctionMatrixList.Add(HitAndMissTransformation.AndTrue2D(srcBoolMatrix,
                          (bool[,])_kernelType2List[i]));
// AndTrue operation with 8 Type3 kernels
for (int i = 0; i < 8; i++)
    junctionMatrixList.Add(HitAndMissTransformation.AndTrue2D(srcBoolMatrix,
                          (bool[,])_kernelType3List[i]));
// detect type 2 junctions which locate neighbour to type 1 junctions,
// T-junction direction
List<double[,]> junctionType4RemovalMatrixList = new List<double[,]>(4);
for (int i = 0; i < 4; i++)
{
    junctionType4RemovalMatrixList.Add(
             HitAndMissTransformation.AndTrueFalseDontCare2D(srcBoolMatrix, 
                 (double[,])
             _kernelType4RemovalList[i]));
}
// OR result from Type1, Type2, and Type3
bool[,] dstMatrix = (bool[,])junctionMatrixList[0];
bool temp;
for (int i = 1; i < 16; i++)
// for each junction output
{
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            temp = ((bool[,])junctionMatrixList[i])[x, y];
            dstMatrix[x, y] = dstMatrix[x, y] || temp;
        }
    }
}
// remove Type4 removal
for (int i = 0; i < 4; i++)
// for each junction type 2 output
{
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            temp = ((bool[,])junctionType4RemovalMatrixList[i])[x, y];
            if (temp)
                dstMatrix[x, y] = false;  // remove operation
        }
    }
}

2.2 Detect Free Ends

There are three types of free end templates, pole-shape (Figure 6 (a)), L-shape (Figure 6 (b)), and T-shape (Figure 6 (c)). By rotating clockwise every 45 degrees, there are eight pole-shape and L-shape templates, respectively. By rotating clockwise every 90 degrees, there are four T-shape templates. Note that there are "0" elements requiring background also matches. Therefore, HMT is done by an AndTrueFalse2D operation, illustrated in Section 3.2.

(a) (b) (c)

Figure 6 (a) Pole-shape free end template (b) L-shape free end template (c) T-shape free end template. Red pixels indicate foreground pixels. Blue pixels indicate background pixels.

The algorithm of detecting free ends is:

Algorithm 2: Detect Free Ends

1. Apply HMT (AndTrueFalse2D) for each pole-shape templates
2. Apply HMT (AndTrueFalse2D) for each L-shape templates
3. Apply HMT (AndTrueFalse2D) for each T-shape templates
4. OR the outputs of step 1, 2 and 3

Source Code Snippets: part of FreeEndDetector.Apply()

// AndTrue operations with 16 kernels
List<bool[,]> dstMatrixList = new List<bool[,]>(20);
for (int i = 0; i < 8; i++)
    dstMatrixList.Add(HitAndMissTransformation.AndTrueFalse2D(srcBoolMatrix,
                     (bool[,])_kernelType1List[i]));
for (int i = 0; i < 8; i++)
    dstMatrixList.Add(HitAndMissTransformation.AndTrueFalse2D(srcBoolMatrix,
                     (bool[,])_kernelType2List[i]));
for (int i = 0; i < 4; i++)
    dstMatrixList.Add(HitAndMissTransformation.AndTrueFalse2D(srcBoolMatrix,
                     (bool[,])_kernelType3List[i]));
// OR all dstMatrixs
bool[,] dstMatrix = (bool[,])dstMatrixList[0];
int height = dstMatrix.GetLength(1);
int width = dstMatrix.GetLength(0);
bool temp;
for (int i = 1; i < 20; i++)
// for each AndTrue output
{
    for (int y = 0; y < height; y++)
    {
        for (int x = 0; x < width; x++)
        {
            temp = ((bool[,])dstMatrixList[i])[x, y];
            dstMatrix[x, y] = dstMatrix[x, y] || temp;
        }
    }
}

2.3 Trace Line Segments

Once junction points and free ends have been detected, it is much easier now to split the graph into line segments. Each line segment has two end points (free end or junction) and some stem points. We start tracing a line segment from an end point to another end point by the following algorithm:

Algorithm 3: Trace One Line Segment

1. Search current point C's 8-connected neighbours
2. If there are more than one 8-connected neighbours
1. Search C's 4-connected neighbour, N4. (In this case, there must be one and only one 4-connected neighbour)
2. If N4 is a junction point, close the current line segment tracing at N4, remove C from the source image (i.e., set C as false)
3. Otherwise, current line segment extends to C, remove C from the source image, set the current point C as N4
3. Otherwise,
1. If the 8-connected neighbour, N8, is a junction point, close the current line segment tracing at N8, remove C from the source image;
2. If the N8 is a free end, close the current line segment tracing at N8, remove C and N8 from the source image;
3. Otherwise, current line segment extends to C, remove C from the source image, set the current point C as N8.

Note that, Algorithm 3 removes free ends and stem points from the source image to avoid re-visiting them. But, the junctions remain.

Source Code Snippet: part of LineSegmentSplitter.TraceSingleLineSegment()

while (true)
// trace a line segment
{
    // search 8 neighbours
    List<Point> eightNeighbourList =
              Search8Neighbours(dstBoolMatrix, currentPoint);
    if (eightNeighbourList.Count == 0)
    // this scenario happens if a line segment is only 2 pixels in length
    // current is a free end.
    {
        lineSegment.AddEndPoint(new Point(currentPoint.X, currentPoint.Y));
        freeEndList.Remove(currentPoint);
        RemoveFromDstMatrix(ref dstBoolMatrix, currentPoint);
        break;
    }              
    if (eightNeighbourList.Count > 1)
    // more than one 8 neighbours
    {
        // search 4 neighbours
        List<Point> fourNeighbourList =
              Search4Neighbours(dstBoolMatrix, currentPoint);
        if (fourNeighbourList.Count > 1)
            throw new ApplicationException(
               "LineSegmentSplitter::ApplyDoubleGraylevelImageFilter()," +
               " current point is not a junction point but detected " +
               "more than one 4 neighbours.");
        Point fourNeighbour = (Point)fourNeighbourList[0];
        if (IsInTripleJunctionList(fourNeighbour, tripleJunctionList))
        // the four neighbour is a junction point
        // close line segment at the junction point
        // stop tracing
        {
            lineSegment.AddEndPoint(new Point(fourNeighbour.X,
                                              fourNeighbour.Y));
            break;
        }
        else if (!(IsInFreeEndList(fourNeighbour, freeEndList)))
        // the four neighbour is a line segment point
        // add four neighbour to line segment
        // set four neighbour the current point
        // remove four neighbour from dst matrix
        {
            lineSegment.AddPoint(new Point(fourNeighbour.X, fourNeighbour.Y));
            RemoveFromDstMatrix(ref dstBoolMatrix, fourNeighbour);
            currentPoint = fourNeighbour;
        }
    }
    else
    // only one neighbours
    {
        Point neighbour = (Point)eightNeighbourList[0];
        if (IsInFreeEndList(neighbour, freeEndList))
        // next neighbour is an end point
        // close line segment at next neighbour
        // remove the end point from end point list
        // remove the end point from dstMatrix
        // stop tracing
        {
            lineSegment.AddEndPoint(new Point(neighbour.X, neighbour.Y));
            freeEndList.Remove(neighbour);
            RemoveFromDstMatrix(ref dstBoolMatrix, neighbour);
            break;
        }
        else if (IsInTripleJunctionList(neighbour, tripleJunctionList))
        // next neighbour is a junction point
        // close line segment at next neighbour
        // stop tracing
        {
            lineSegment.AddEndPoint(new Point(neighbour.X, neighbour.Y));
            break;
        }
        else
        // next neighbour is a line segment point
        // add neighbour to line segment
        // remove neighbour from dstMatrix
        // set neighbour as current point
        {
            lineSegment.AddPoint(new Point(neighbour.X, neighbour.Y));
            RemoveFromDstMatrix(ref dstBoolMatrix, neighbour);
            currentPoint = neighbour;
        }
    }
};  // while(true)

The following algorithm uses Algorithm 1, 2, and 3 to split the graph into line segments:

Algorithm 4: Split Graph into Line Segments

1. Apply Algorithm 1 to obtain junction points list
2. Apply Algorithm 3 to obtain free end points list
3. Start from each free end points, apply Algorithm 3 to trace line segments
4. Start from each junction points' 4-connected neighbours, apply Algorithm 3 to trace line segments
5. Start from each junction point's 8-connected neighbours, apply Algorithm 3 to trace line segments
6. Remove those isolated junction points or connect the contiguous junction points

Source Code Snippet: part of LineSegmentSplitter.Apply()

// start tracing line segment from end points
while (_freeEndList.Count > 0)
// for each end point
{
    Point currentPoint = (Point)_freeEndList[0];
    _freeEndList.RemoveAt(0);   // remove end point from end point list  
    LineSegment lineSegment = new LineSegment();
    // add current point in line segment as "end point"
    lineSegment.AddEndPoint(new Point(currentPoint.X, currentPoint.Y));
    // remove current point from dstMatrix
    RemoveFromDstMatrix(ref dstBoolMatrix, currentPoint);
    // trace single line segment
    TraceSingleLineSegment(ref lineSegment, ref currentPoint, 
        ref dstBoolMatrix, ref _freeEndList, ref _tripleJunctionList);
    _lineSegmentList.Add(lineSegment);
}; // while(_freeEndList.Count > 0)
// start tracing line segments from junction points
// firstly, trace only 4-neighbours of all the junction points
foreach (Point junctionPoint in _tripleJunctionList)
{
    RemoveFromDstMatrix(ref dstBoolMatrix, junctionPoint);
    List<Point> fourNeighbourList = Search4Neighbours(dstBoolMatrix, 
        junctionPoint);
    int index = 0;
    while (index < fourNeighbourList.Count)
    {
        Point neighbour = fourNeighbourList[index];
        // remove the other neighbours from dst matrix
        for (int i = 0; i < fourNeighbourList.Count; i++)
        {
            if (i == index)
                continue;
            RemoveFromDstMatrix(ref dstBoolMatrix, 
                (Point)fourNeighbourList[i]);
        }
        LineSegment lineSegment = new LineSegment();
        lineSegment.AddEndPoint(new Point(junctionPoint.X, junctionPoint.Y));
        Point currentPoint = neighbour;
        // current point could be a junction point or a line segment point
        if (!IsInTripleJunctionList(currentPoint, _tripleJunctionList))
        // current is a line segment point
        {
            lineSegment.AddPoint(new Point(currentPoint.X, currentPoint.Y));
            RemoveFromDstMatrix(ref dstBoolMatrix, currentPoint);
            TraceSingleLineSegment(ref lineSegment, ref currentPoint, 
                ref dstBoolMatrix, ref _freeEndList, ref _tripleJunctionList);
            _lineSegmentList.Add(lineSegment);
        }
        // add the other neighbours to dst matrix
        for (int i = 0; i < fourNeighbourList.Count; i++)
        {
            if (i == index)
                continue;
            AddToDstMatrix(ref dstBoolMatrix, (Point)fourNeighbourList[i]);
        }
        index++;
    } // while (fourNeighbourList.Count > 0)
    // remove all non-junctin four diagonal neighbours from dst bool matrix
    foreach (Point neighbour in fourNeighbourList)
    {
        if (!IsInTripleJunctionList(neighbour, _tripleJunctionList))
            RemoveFromDstMatrix(ref dstBoolMatrix, neighbour);
    }
    AddToDstMatrix(ref dstBoolMatrix, junctionPoint);
} // foreach _tripleJunctionList
// secondly, trace only 4-diagonal-neighbours of all the junction points
foreach (Point junctionPoint in _tripleJunctionList)
{
    RemoveFromDstMatrix(ref dstBoolMatrix, junctionPoint);
    List<Point> fourDiagonalNeighbourList = SearchDiagonal4Neighbours(
        dstBoolMatrix, junctionPoint);
    int index = 0;
    while (index < fourDiagonalNeighbourList.Count)
    {
        Point neighbour = (Point)fourDiagonalNeighbourList[index];
        // remove the other neighbours from the dst matrix
        for (int i = 0; i < fourDiagonalNeighbourList.Count; i++)
        {
            if (i == index)
                continue;
            RemoveFromDstMatrix(ref dstBoolMatrix, 
                (Point)fourDiagonalNeighbourList[i]);
        }
        LineSegment lineSegment = new LineSegment();
        lineSegment.AddEndPoint(new Point(junctionPoint.X, junctionPoint.Y));
        Point currentPoint = neighbour;
        // current point could be a junction point or a line segment point
        if (!IsInTripleJunctionList(currentPoint, _tripleJunctionList))
        // current is a line segment point
        {
            lineSegment.AddPoint(new Point(currentPoint.X, currentPoint.Y));
            RemoveFromDstMatrix(ref dstBoolMatrix, currentPoint);
            TraceSingleLineSegment(ref lineSegment, ref currentPoint, 
                ref dstBoolMatrix, ref _freeEndList, ref _tripleJunctionList);
            _lineSegmentList.Add(lineSegment);
        }
        // add the other neighbours to the dst matrix
        for (int i = 0; i < fourDiagonalNeighbourList.Count; i++)
        {
            if (i == index)
                continue;
            AddToDstMatrix(ref dstBoolMatrix, 
                (Point)fourDiagonalNeighbourList[i]);
        }
        index++;
    } // while(fourDiagonalNeighbourList.Count > 0)
    // remove all non-junctin four diagonal neighbours from dst bool matrix
    foreach (Point neighbour in fourDiagonalNeighbourList)
    {
        if (!IsInTripleJunctionList(neighbour, _tripleJunctionList))
            RemoveFromDstMatrix(ref dstBoolMatrix, neighbour);
    }

    AddToDstMatrix(ref dstBoolMatrix, junctionPoint);
}            
// thirdly, connect the contiguous junction points  
foreach (Point junctionPoint in _tripleJunctionList)
{
    List<Point> neighbourList = Search8Neighbours(dstBoolMatrix, 
        junctionPoint);
    if (neighbourList.Count == 0)
        RemoveFromDstMatrix(ref dstBoolMatrix, junctionPoint);
    else
    {
        foreach (Point endPoint in neighbourList)
        {
            LineSegment lineSegment = new LineSegment();
            lineSegment.AddEndPoint(new Point(junctionPoint.X, 
                junctionPoint.Y));
            lineSegment.AddEndPoint(new Point(endPoint.X, endPoint.Y));
            _lineSegmentList.Add(lineSegment);
        }
        RemoveFromDstMatrix(ref dstBoolMatrix, junctionPoint);
    }
}

3. Hit-and-Miss Transform Source Codes

3.1 AndTrue2D

Source Code Snippet: part of HitAndMissTransformation.AndTrue2D()

bool[,] expandSrcBoolMatrix =
        BoundFillingBackgroundIntensityExpand(srcBoolMatrix, kernel);
// prepare dst bool matrix
int expandHeight = expandSrcBoolMatrix.GetLength(1);
int expandWidth = expandSrcBoolMatrix.GetLength(0);
bool[,] expandDstBoolMatrix = new bool[expandWidth, expandHeight];
int xStart = halfWk;
int xEnd = width + halfWk;
int yStart = halfHk;
int yEnd = height + halfHk;
for (int x = xStart; x < xEnd; x++)
{
    for (int y = yStart; y < yEnd; y++)
    {
        bool isHit = true;
        // inside kernel
        for (int kx = -1 * halfWk; kx <= halfWk; kx++)
        {
            for (int ky = -1 * halfHk; ky <= halfHk; ky++)
            {
                // kernel, expandSrcBoolMatrix,
                // and expandDstBoolMatrix are bool[,]
                if (kernel[kx + halfWk, ky + halfHk])
                // kernel element is true
                {
                    if (!expandSrcBoolMatrix[x + kx, y + ky])
                    // image element is false
                    {
                        isHit = false;
                        break;
                    }
                }
            }
        }
        expandDstBoolMatrix[x, y] = isHit;
    }
}
bool[,] dstBoolMatrix =
  BoundFillingBackgroundIntensityShrink(expandDstBoolMatrix, kernel);

Note that, before applying "binary convolution", the source image is boundary expanded by filling the expanded part background values (False).

3.2 AndTrueFalse2D

Source Code Snippet: part of HitAndMissTransformation.AndTrueFalse2D():

bool[,] expandSrcBoolMatrix =
       BoundFillingBackgroundIntensityExpand(srcBoolMatrix, kernel);
// prepare dst bool matrix
int expandHeight = expandSrcBoolMatrix.GetLength(1);
int expandWidth = expandSrcBoolMatrix.GetLength(0);
bool[,] expandDstBoolMatrix = new bool[expandWidth, expandHeight];
int xStart = halfWk;
int xEnd = width + halfWk;
int yStart = halfHk;
int yEnd = height + halfHk;
for (int x = xStart; x < xEnd; x++)
{
    for (int y = yStart; y < yEnd; y++)
    {
        bool isHit = true;
        // inside kernel
        for (int kx = -1 * halfWk; kx <= halfWk; kx++)
        {
            for (int ky = -1 * halfHk; ky <= halfHk; ky++)
            {
                // kernel is a bool[,]
                // expandSrcBoolMatrix, and expandDstBoolMatrix are bool[,]
                if ((kernel[kx + halfWk, ky + halfHk] &&

                    !expandSrcBoolMatrix[x + kx, y + ky])
                    || (!kernel[kx + halfWk, ky + halfHk] &&
                         expandSrcBoolMatrix[x + kx, y + ky]))
                {
                    isHit = false;
                    break;
                }
            }
        }
        expandDstBoolMatrix[x, y] = isHit;
    }
}
bool[,] dstBoolMatrix =
  BoundFillingBackgroundIntensityShrink(expandDstBoolMatrix, kernel);

3.3 AndTrueFalseDontCare2D

The kernel now is not a bool array, but a double array, as there are "TRUE", "FALSE", and "Don't Care" three values. Let value 1.0 be "TRUE", value 0.0 be "FALSE", and value "0.5" be "Don't Care".

Source Code Snippet: part of HitAndMissTransformation.AndTrueFalseDontCare2D():

bool[,] expandSrcBoolMatrix =
       BoundFillingBackgroundIntensityExpand(srcBoolMatrix, kernel);
// prepare dst bool matrix
int expandHeight = expandSrcBoolMatrix.GetLength(1);
int expandWidth = expandSrcBoolMatrix.GetLength(0);
bool[,] expandDstBoolMatrix = new bool[expandWidth, expandHeight];
int xStart = halfWk;
int xEnd = width + halfWk;
int yStart = halfHk;
int yEnd = height + halfHk;
for (int x = xStart; x < xEnd; x++)
{
    for (int y = yStart; y < yEnd; y++)
    {
        bool isHit = true;
        // inside kernel
        for (int kx = -1 * halfWk; kx <= halfWk; kx++)
        {
            for (int ky = -1 * halfHk; ky <= halfHk; ky++)
            {
                // kernel is a double[,]
                // expandSrcBoolMatrix, and expandDstBoolMatrix are bool[,]
                if ((kernel[kx + halfWk, ky + halfHk] == 1 && 
                    !expandSrcBoolMatrix[x + kx, y + ky])
                || (kernel[kx + halfWk, ky + halfHk] == 0 && 
                    expandSrcBoolMatrix[x + kx, y + ky]))
                {
                    isHit = false;
                    break;
                }
            }
        }
        expandDstBoolMatrix[x, y] = isHit;
    }
}
bool[,] dstBoolMatrix =
  BoundFillingBackgroundIntensityShrink(expandDstBoolMatrix, kernel);

4. Results and Conclusion

It turns out it is much easier to develop "Algorithm 1" to "Algorithm 4" and implement them using C# to split a single-pixel-width connected graph into line segments. Figure 7 shows the split line segments. Line segment ends are in red while stem points are in blue. "Algorithm 1" detects junctions, covering every scenario shown in Figure 3 and the ones not shown. "Algorithm 2" detects free ends. "Algorithm 4" accomplishes splitting the graph into line segments.

Figure 7 Line segments image

Reference

[1] Peter I Rockett, An Improved Rotation-Invariant Thinning Algorithm. IEEE Trans. Pattern Anal. Mach. Intel. 27(10): 1671-1674 (2005)

History

• 01.08.2007, first version
• 16.08.2007, updated source