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

- Apply HMT (
`AndTrue2D`

) for each `Type1 `

templates - Apply HMT (
`AndTrue2D`

) for each `Type2 `

and `Type3 `

templates - Apply HMT (
`AndTrueFalseDontCare2D`

) for each `Type4 `

templates - OR the outcomes of step 1 and step 2
`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);
for (int i = 0; i < 4; i ++)
junctionMatrixList.Add(HitAndMissTransformation.AndTrue2D(srcBoolMatrix,
(bool[,])_kernelType1List[i]));
for (int i = 0; i < 4; i ++)
junctionMatrixList.Add(HitAndMissTransformation.AndTrue2D(srcBoolMatrix,
(bool[,])_kernelType2List[i]));
for (int i = 0; i < 8; i++)
junctionMatrixList.Add(HitAndMissTransformation.AndTrue2D(srcBoolMatrix,
(bool[,])_kernelType3List[i]));
List<double[,]> junctionType4RemovalMatrixList = new List<double[,]>(4);
for (int i = 0; i < 4; i++)
{
junctionType4RemovalMatrixList.Add(
HitAndMissTransformation.AndTrueFalseDontCare2D(srcBoolMatrix,
(double[,])
_kernelType4RemovalList[i]));
}
bool[,] dstMatrix = (bool[,])junctionMatrixList[0];
bool temp;
for (int i = 1; i < 16; i++)
{
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;
}
}
}
for (int i = 0; i < 4; i++)
{
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;
}
}
}

### 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

- Apply HMT (
`AndTrueFalse2D`

) for each pole-shape templates - Apply HMT (
`AndTrueFalse2D`

) for each L-shape templates - Apply HMT (
`AndTrueFalse2D`

) for each T-shape templates `OR `

the outputs of step 1, 2 and 3

Source Code Snippets: part of `FreeEndDetector.Apply() `

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]));
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 (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

- Search current point
`C`

's 8-connected neighbours - If there are more than one 8-connected neighbours
- Search
`C`

's 4-connected neighbour, `N4`

. (In this case, there must be one and only one 4-connected neighbour) - 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) - Otherwise, current line segment extends to
`C`

, remove `C`

from the source image, set the current point `C`

as `N4`

Otherwise,
- If the 8-connected neighbour,
`N8`

, is a junction point, close the current line segment tracing at `N8`

, remove `C`

from the source image; - If the
`N8`

is a free end, close the current line segment tracing at `N8`

, remove `C`

and `N8`

from the source image; - 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)
{
List<Point> eightNeighbourList =
Search8Neighbours(dstBoolMatrix, currentPoint);
if (eightNeighbourList.Count == 0)
{
lineSegment.AddEndPoint(new Point(currentPoint.X, currentPoint.Y));
freeEndList.Remove(currentPoint);
RemoveFromDstMatrix(ref dstBoolMatrix, currentPoint);
break;
}
if (eightNeighbourList.Count > 1)
{
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))
{
lineSegment.AddEndPoint(new Point(fourNeighbour.X,
fourNeighbour.Y));
break;
}
else if (!(IsInFreeEndList(fourNeighbour, freeEndList)))
{
lineSegment.AddPoint(new Point(fourNeighbour.X, fourNeighbour.Y));
RemoveFromDstMatrix(ref dstBoolMatrix, fourNeighbour);
currentPoint = fourNeighbour;
}
}
else
{
Point neighbour = (Point)eightNeighbourList[0];
if (IsInFreeEndList(neighbour, freeEndList))
{
lineSegment.AddEndPoint(new Point(neighbour.X, neighbour.Y));
freeEndList.Remove(neighbour);
RemoveFromDstMatrix(ref dstBoolMatrix, neighbour);
break;
}
else if (IsInTripleJunctionList(neighbour, tripleJunctionList))
{
lineSegment.AddEndPoint(new Point(neighbour.X, neighbour.Y));
break;
}
else
{
lineSegment.AddPoint(new Point(neighbour.X, neighbour.Y));
RemoveFromDstMatrix(ref dstBoolMatrix, neighbour);
currentPoint = neighbour;
}
}
};

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

Algorithm 4: Split Graph into Line Segments

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

Source Code Snippet: part of `LineSegmentSplitter.Apply()`

while (_freeEndList.Count > 0)
{
Point currentPoint = (Point)_freeEndList[0];
_freeEndList.RemoveAt(0);
LineSegment lineSegment = new LineSegment();
lineSegment.AddEndPoint(new Point(currentPoint.X, currentPoint.Y));
RemoveFromDstMatrix(ref dstBoolMatrix, currentPoint);
TraceSingleLineSegment(ref lineSegment, ref currentPoint,
ref dstBoolMatrix, ref _freeEndList, ref _tripleJunctionList);
_lineSegmentList.Add(lineSegment);
};
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];
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;
if (!IsInTripleJunctionList(currentPoint, _tripleJunctionList))
{
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);
}
for (int i = 0; i < fourNeighbourList.Count; i++)
{
if (i == index)
continue;
AddToDstMatrix(ref dstBoolMatrix, (Point)fourNeighbourList[i]);
}
index++;
}
foreach (Point neighbour in fourNeighbourList)
{
if (!IsInTripleJunctionList(neighbour, _tripleJunctionList))
RemoveFromDstMatrix(ref dstBoolMatrix, neighbour);
}
AddToDstMatrix(ref dstBoolMatrix, junctionPoint);
}
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];
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;
if (!IsInTripleJunctionList(currentPoint, _tripleJunctionList))
{
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);
}
for (int i = 0; i < fourDiagonalNeighbourList.Count; i++)
{
if (i == index)
continue;
AddToDstMatrix(ref dstBoolMatrix,
(Point)fourDiagonalNeighbourList[i]);
}
index++;
}
foreach (Point neighbour in fourDiagonalNeighbourList)
{
if (!IsInTripleJunctionList(neighbour, _tripleJunctionList))
RemoveFromDstMatrix(ref dstBoolMatrix, neighbour);
}
AddToDstMatrix(ref dstBoolMatrix, junctionPoint);
}
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);
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;
for (int kx = -1 * halfWk; kx <= halfWk; kx++)
{
for (int ky = -1 * halfHk; ky <= halfHk; ky++)
{
if (kernel[kx + halfWk, ky + halfHk])
{
if (!expandSrcBoolMatrix[x + kx, y + ky])
{
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);
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;
for (int kx = -1 * halfWk; kx <= halfWk; kx++)
{
for (int ky = -1 * halfHk; ky <= halfHk; ky++)
{
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);
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;
for (int kx = -1 * halfWk; kx <= halfWk; kx++)
{
for (int ky = -1 * halfHk; ky <= halfHk; ky++)
{
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