Forem: A A

[WPF] Draw Tree Topology

A A — Sat, 11 Jan 2025 00:39:03 +0000

How to draw tree topology in WPF

When expressing data structures with parent-child relationships, we use a tree topology as shown below, but other than TreeView, WPF has no components or libraries for graphical display.
In addition, TreeView becomes more difficult to view as the number of nodes increases and the depth of the tree increases.

In this article, we show how to graphically render the tree topology as follows.
The application displaying the topology is also available on Github below.

https://github.com/wjtj52twa/WpfDrawTreeTopology

Tree Structure Data

The application reads the json file containing the tree structure data and draws the tree topology in WPF's Canvas, and the json file is “data.json” directly under the executable file.

The json data for the topology displayed in this article uses the following

{
  "Text": "Root",
  "Children": [
    {
      "Text": "Node1",
      "Children": [
        {
          "Text": "Node1-1",
          "Children": []
        },
        {
          "Text": "Node1-2",
          "Children": []
        },
        {
          "Text": "Node1-2",
          "Children": []
        }
      ]
    },
    {
      "Text": "Node2",
      "Children": [
        {
          "Text": "Node2-1",
          "Children": []
        },
        {
          "Text": "Node2-2",
          "Children": [
            {
              "Text": "Node2-2-1",
              "Children": []
            },
            {
              "Text": "Node2-2-2",
              "Children": []
            }
          ]
        },
        {
          "Text": "Node2-2",
          "Children": []
        }
      ]
    },
    {
      "Text": "Node3",
      "Children": []
    }
  ]
}

The above tree structure is expanded into the “TreeNode” class and referenced in the program.
Parent” is set to the parent node and ‘Children’ to the child nodes, and the structure is such that the nodes are connected to the tree structure.

The “X” and “Y” properties are used to set the coordinates for drawing the tree structure, and the calculation method is described below. There are also other properties and functions for calculation, but the details are omitted.

namespace TreeTopology
{
    public class TreeNode
    {
        public TreeNode? Parent { get; set; } = null;

        public List<TreeNode> Children { get; set; } = new List<TreeNode>();

        public string Text { get; set; } = string.Empty;

        public float X { get; set; }

        public float Y { get; set; }

        public float Mod { get; set; }

        public void SetParentReferences()
        {
            foreach (var child in Children)
            {
                child.Parent = this;
                child.SetParentReferences();
            }
        }

        (Omitted...)
    }
}

Overall processing until the tree structure is drawn

The following is an overview of the process up to drawing the tree topology and the program.
The program is processed when the “Read topology json” button is pressed. The “data.json” file is read and parsed into the TreeNode class using “JsonSerializer”.

Reading json file with tree structure defined.
Parse json data to create TreeNode class, property sets for parent and child nodes
Calculate coordinates of the tree topology
Drawing the tree topology

private void ReadTopologyJsonButton_Click(object sender, RoutedEventArgs e)
{
    try
    {
        // Get the path directly under the executable file
        string filePath = AppDomain.CurrentDomain.BaseDirectory + "data.json";

        // Check file exsited
        if (!File.Exists(filePath))
        {
            Console.WriteLine("File not found: data.json.");
            return;
        }

        // Read file contents
        string jsonData = File.ReadAllText(filePath);

        // Deserialize JSON to TreeNode object
        TreeNode root = JsonSerializer.Deserialize<TreeNode>(jsonData, new JsonSerializerOptions
        {
            PropertyNameCaseInsensitive = true
        }) ?? throw new InvalidOperationException("Failed to deserialize JSON.");


        bool isHorizontal = HorizontalRadioButton.IsChecked ?? false;
        if (root != null)
        {
            // Set Parent property
            root.SetParentReferences();

            // Calculate coordinates of tree topology
            TreeHelper.CalculateNodePositions(root, isHorizontal);

            // Draw Topology
            DrawTopology.Draw(TopologyCanvas, root, isHorizontal);
        }

    }
    catch (Exception ex)
    {
        // Error
        Console.WriteLine("Exception Error: " + ex.Message);
    }
}

Calculate coordinates of topology

To draw the tree structure, we calculate the coordinate position of each node. The coordinates are calculated according to the following rules to ensure a “clean” display of the tree structure.

Tree edges do not overlap with other edges.
Nodes at the same depth are placed on the same horizontal line.
Trees are drawn as narrow as possible.
the parent node is drawn in the middle of its children nodes
Sub-trees of the same structure are drawn in the same way, no matter where the sub-trees are located.

According to the above rules, the following processing steps are used to calculate the coordinates. The basic idea is to construct the coordinates and subtrees in order from the terminal leaf node, and then proceed with the coordinate calculation in the direction of the root (parent) while adjusting the position among the subtrees.

process leaf nodes using tree depth-first search (DFS)
- Start at the lowest level of the tree (leaf node).
- Initially initialize the leaf nodes to the appropriate coordinates.
- Y-coordinate is set by the depth of the node.
placement of child nodes
- For the first child node in a subtree at a leaf node, set the X coordinate to 0.
- For the second and subsequent child nodes, the X-coordinate shall be the X-coordinate of the neighboring child node + 1
- Once the placement of a child node in a subtree is complete, the parent node is placed in the middle of the child nodes
eliminate overlap between subtrees
- Perform a shift operation to ensure proper spacing between each subtree.
- At this time, the entire subtree, including the child nodes, is shifted in parallel to eliminate overlap.
determination of absolute position
- Calculate steps 2~3 sequentially starting from the leaf node, and finally calculate the coordinates up to the root node

The following tree structure is created for the final enemy. The coordinates are stored in the “X” and “Y” properties of the TreeNode class. The coordinates can be changed to those of a horizontal tree structure by swapping the “X” and “Y” coordinates.

Drawing the topology

According to the calculated coordinates of each node, the following code draws a tree topology in Canvas. Draw the nodes as Rectangle and connect the nodes with Lines.

public static class DrawTopology
{
    // Node dimensions
    private static double nodeWidth = 140.0d;
    private static double nodeHeight = 40.0d;

    // Line colors
    private static SolidColorBrush green = Brushes.Green;
    private static SolidColorBrush black = Brushes.Black;

    // Canvas size
    private static double canvasHeight = 0;
    private static double canvasWidth = 0;

    /// <summary>
    /// Draws the tree topology on the canvas.
    /// </summary>
    /// <param name="canvas">The Canvas to draw on.</param>
    /// <param name="root">The root node of the tree.</param>
    /// <param name="isHorizontal">True for horizontal layout; false for vertical layout.</param>
    public static void Draw(this Canvas canvas, TreeNode root, bool isHorizontal = false)
    {
        canvas.Children.Clear();
        canvasHeight = 0;
        canvasWidth = 0;

        if (isHorizontal) canvas.drawHorizontal(root);
        else canvas.drawVertical(root);
    }

    /// <summary>
    /// Creates a line connecting two points.
    /// </summary>
    /// <param name="x1">Start point X-coordinate.</param>
    /// <param name="y1">Start point Y-coordinate.</param>
    /// <param name="x2">End point X-coordinate.</param>
    /// <param name="y2">End point Y-coordinate.</param>
    /// <param name="brush">Color of the line.</param>
    /// <param name="thickness">Thickness of the line.</param>
    /// <returns>A Line object.</returns>
    private static Line createLine(double x1, double y1, double x2, double y2, Brush brush, double thickness)
    {
        Line line = new Line();
        line.X1 = x1;
        line.Y1 = y1;
        line.X2 = x2;
        line.Y2 = y2;
        line.Stroke = brush;
        line.StrokeThickness = thickness;
        return line;
    }

    /// <summary>
    /// Creates a rectangle representing a node.
    /// </summary>
    /// <param name="x">X-coordinate of the rectangle.</param>
    /// <param name="y">Y-coordinate of the rectangle.</param>
    /// <param name="width">Width of the rectangle.</param>
    /// <param name="height">Height of the rectangle.</param>
    /// <param name="stroke">Border color of the rectangle.</param>
    /// <param name="thickness">Border thickness of the rectangle.</param>
    /// <param name="fill">Fill color of the rectangle.</param>
    /// <returns>A Rectangle object.</returns>
    private static Rectangle createRect(double x, double y, double width, double height, Brush stroke, double thickness, Brush fill)
    {
        Rectangle rect = new Rectangle();
        rect.RadiusX = 8d;
        rect.RadiusY = 8d;
        Canvas.SetLeft(rect, x);
        Canvas.SetTop(rect, y);
        rect.Width = width;
        rect.Height = height;
        rect.Stroke = stroke;
        rect.StrokeThickness = thickness;
        rect.Fill = fill;
        return rect;
    }

    /// <summary>
    /// Creates text content to display within a node.
    /// </summary>
    /// <param name="text">The text content.</param>
    /// <param name="fontSize">Font size of the text.</param>
    /// <param name="brush">Text color.</param>
    /// <param name="x">X-coordinate of the text.</param>
    /// <param name="y">Y-coordinate of the text.</param>
    /// <param name="widh">Width of the text container.</param>
    /// <param name="height">Height of the text container.</param>
    /// <param name="hAlign">Horizontal alignment of the text.</param>
    /// <param name="vAlign">Vertical alignment of the text.</param>
    /// <returns>A ContentControl containing the text.</returns>
    private static ContentControl createText(string text, double fontSize, Brush brush, double x, double y, double widh, double height, HorizontalAlignment hAlign, VerticalAlignment vAlign)
    {
        ContentControl content = new ContentControl();
        Canvas.SetLeft(content, x);
        Canvas.SetTop(content, y);
        content.Width = widh;
        content.Height = height;

        TextBlock tb = new TextBlock();
        tb.Text = text;
        tb.FontSize = fontSize;
        tb.Foreground = brush;
        tb.HorizontalAlignment = hAlign;
        tb.VerticalAlignment = vAlign;
        content.Content = tb;

        return content;
    }

    /// <summary>
    /// Draws the tree in a horizontal layout.
    /// </summary>
    /// <param name="canvas">The Canvas to draw on.</param>
    /// <param name="node">The current node to draw.</param>
    private static void drawHorizontal(this Canvas canvas, TreeNode node)
    {
        // Spacing between nodes
        double spaceX = 120;
        double spaceY = 50;

        // Draw the current node
        var x = node.X * spaceX + node.X * nodeWidth;
        var y = node.Y * spaceY + node.Y * nodeHeight;
        canvas.Children.Add(createRect(x, y, nodeWidth, nodeHeight, green, 2.0d, Brushes.White));
        canvas.Children.Add(createText(node.Text, 16.0d, black, x, y - 1, nodeWidth, nodeHeight, HorizontalAlignment.Center, VerticalAlignment.Center));

        // Update canvas size
        canvas.updateCanvasSize(x + nodeWidth, y + nodeHeight);

        foreach (var child in node.Children)
        {
            // Draw connecting line
            var line_x = child.X * spaceX + child.X * nodeWidth;
            var line_y = child.Y * spaceY + child.Y * nodeHeight + nodeHeight / 2;
            canvas.Children.Add(createLine(x + nodeWidth, y + nodeHeight / 2, line_x, line_y, green, 2.5d));

            // Draw child nodes
            canvas.drawHorizontal(child);
        }
    }

    /// <summary>
    /// Draws the tree in a vertical layout.
    /// </summary>
    /// <param name="canvas">The Canvas to draw on.</param>
    /// <param name="node">The current node to draw.</param>
    private static void drawVertical(this Canvas canvas, TreeNode node)
    {
        // Spacing between nodes
        double spaceX = 50;
        double spaceY = 120;

        // Draw the current node
        var x = node.X * spaceX + node.X * nodeWidth;
        var y = node.Y * spaceY + node.Y * nodeHeight;
        canvas.Children.Add(createRect(x, y, nodeWidth, nodeHeight, green, 2.0d, Brushes.White));
        canvas.Children.Add(createText(node.Text, 16.0d, black, x, y - 1, nodeWidth, nodeHeight, HorizontalAlignment.Center, VerticalAlignment.Center));

        // Update canvas size
        canvas.updateCanvasSize(x + nodeWidth, y + nodeHeight);

        foreach (var child in node.Children)
        {
            // Draw connecting line
            var line_x = child.X * spaceX + child.X * nodeWidth + nodeWidth / 2;
            var line_y = child.Y * spaceY + child.Y * nodeHeight;
            canvas.Children.Add(createLine(x + nodeWidth / 2, y + nodeHeight, line_x, line_y, green, 2.5d));

            // Draw child nodes
            canvas.drawVertical(child);
        }
    }

    /// <summary>
    /// Updates the canvas size based on the drawn elements.
    /// </summary>
    /// <param name="canvas">The Canvas to update.</param>
    /// <param name="widht">The new width of the canvas.</param>
    /// <param name="height">The new height of the canvas.</param>
    private static void updateCanvasSize(this Canvas canvas, double widht, double height)
    {
        if (widht > canvasWidth)
        {
            canvasWidth = widht;
            canvas.Width = widht;
        }

        if (height > canvasHeight)
        {
            canvasHeight = height;
            canvas.Height = height;
        }
    }
}

Source Code

The project files for the created application are available for sale at the following site. If you would like to review the entire source code, please feel free to purchase it.

https://aktwjtj.gumroad.com/l/WpfDrawTreeTopology

[Paper Implementation] Fast Shape-based Template Matching

A A — Sun, 22 Dec 2024 11:26:04 +0000

Fast Shape-based Template Matching

While there has been tremendous progress in image and object recognition using DeepLearning and large-scale language models in recent years, this article will describe fast shape-based template matching using classical image processing. The algorithm is based on the following paper with our own improvements, and the implemented application is available on github.

Paper:
https://stefan-hinterstoisser.com/papers/hinterstoisser2011linemod.pdf

Github:
https://github.com/AkitoArai709/HighSpeedShapeBaseTemplateMattching

Background and Algorithm Overview

The main methods used to detect objects in images are “template matching” and “statistical methods/Deep Learning”. Each has the following characteristics.

Template Matching does not require learning and is characterized by its high processing speed. However, it is easily affected by changes in lighting and background, and real-time processing may be difficult.
Statistical methods and Deep Learning provide robust detection that is less affected by lighting and background. However, these methods require large amounts of training data and high computational resources.

In this paper, we propose an efficient and robust method for detecting textureless objects by solving these problems.

In the paper's approach, template data is created from images using only the gradient direction of objects as features, and objects similar to the template data are searched for in test images. By treating only the gradient direction without considering the norm (magnitude) of the gradient, robustness against contrast changes is improved. Similarity is calculated by calculating the cosine of the gradient direction of the feature points to determine the degree of agreement with the template data.
However, since cosine is computationally expensive, a look-up table that quantizes the gradient direction and obtains an evaluation value for each direction is used to streamline the computation cost, and the SSE instruction is used to speed up the process.

Image Processing Approach

Calculate the gradient angle of the edge (gradient) from the template image to be searched and create template data with the gradient angle as a feature. Scan the template data against the test image to obtain similarity.
When the template image is O and the test image is L, the similarity is calculated by the following formula.

ori denotes the gradient angle, and R(c+r) denotes the neighborhood gradient of size T centered at position c+r in the input image. Cosine evaluates the degree of agreement of the gradient angles. In other words, the maximum degree of agreement (cosine) of the feature points of the template with respect to the neighborhood of R(c+r) is calculated, and the value obtained for all feature points is added to the cosine, which is the similarity.

Calculation of gradient direction

Calculate the luminance gradient from the image using a Sobel filter to obtain the gradient direction; for RGB color images, calculate the gradient of each color channel separately and find the gradient direction of the largest channel using the following formula.

The gradient direction is quantized in 8 directions to calculate the response map in a later step. To make it robust to noise, the gradient direction that appears most frequently in a 3x3 neighborhood is placed at each location for gradient norms above a threshold value. Let L be the quantized gradient direction map.

Diffusion in gradient direction

To avoid the evaluation of the cosine and max operators in (1) each time the template is evaluated for a test image location, a new binary representation (J) of the gradient around each image location is introduced. This binary representation and the lookup table table are used to efficiently precompute the maximum value of the max operation.
First, an image of the binary representation (J) with the gradient direction diffused is shown below.

The quantized gradient direction is encoded in a binary representation, and each bit is assigned a gradient direction. This gradient direction is diffused to the neighborhood to create a binary representation (J).
By using a binary representation, J can be obtained by shifting the bits within a specified range and performing an OR operation to calculate the diffusion. The range to be shifted is the neighborhood of size T indicated in (2).

Calculating the response map

Next, the binary representation (J) is precomputed for similarity to each azimuth using a lookup table. The pre-calculated result is defined as the response map. An image of the response map is shown below.

One response map is created for each quantization azimuth. The principle is to calculate and store the maximum similarity for a particular azimuth (image on the right). This calculation is performed by preparing a lookup table in which the similarity for each azimuth is stored, and the similarity is indexed by azimuth (image on the left). Based on this response map, a quantized 8-azimuth response map is created.

For reference, an example of a lookup table with azimuths of 0 degrees (→) and 90 degrees (↑) is shown below. If the azimuths are coincident, “1” is obtained for cos(0), and you can see that the similarity decreases with each deviation in azimuth.

For each azimuth i, the value at each position c in the response map Si is calculated as follows: T denotes the lookup table.

The final similarity calculation is as follows.

Memory linearization for parallelization

Modern processors not only read data from main memory at any one time, but also read multiple data lines, called cache lines, at the same time. If memory is accessed from random locations, the cache is lost and computation speed is reduced.
On the other hand, accessing multiple values from the same cache line is very efficient. Therefore, storing data in the order in which they are accessed can speed up calculations.
Since it is efficient to evaluate every T-th pixel due to the aforementioned diffusion of orientation to the size T neighborhood, the response map is stored in memory in a cache-friendly order, as shown in the following figure.

Reassemble each response map so that values T pixels apart on the X axis are placed next to each other in memory. When the current row is finished, proceed to the rows T pixels apart on the Y-axis.

The linear memory for the different directions of the template (black arrows in the figure below) can be shifted and added by the offset according to the relative position (Rx,Ry)^T of the template relative to the anchor coordinates (search reference coordinates) to calculate the similarity on the input image to the template. The computation can be accelerated by executing these additions with parallel SSE instructions.

The above is the content described in the paper. The following is a verification of the implementation.

Diffusion in a T-neighborhood

As mentioned above, this algorithm diffuses the features to the T neighborhood and evaluates every Tth pixel to improve the efficiency of calculation.
With respect to the size of T, the results of detection at T=8, T=4, and T=1 are shown below.

T=8	T=4	T=1

I see that at T=8, the displacement is large with respect to the object, and as the T size is decreased, it fits better. This is because when diffusing with T size, all evaluation values are the same in the vicinity of T, and it is not possible to narrow down the best fitting position.
This is not a problem if you want to detect approximate positions, but if you want to perform detailed positioning, you need to reduce the size of T. However, reducing the size of T slows down the detection speed, making it a tradeoff between speed and accuracy.

In the application published on github, both high speed and high accuracy are achieved by performing a coarse search for diffusion and pyramid processing in the vicinity of T, followed by a detailed search at T=1.

Evaluation with various images

How the results of evaluation with various images. We also used a dataset published by Hashimoto Laboratory of Chukyo University for the evaluation.

http://isl.sist.chukyo-u.ac.jp/Archives/archives.html

Shogi Piece

Template image size: 149x131

Test image size: 600x400

Detection time: 56[ms]

Puzzle Piece

Template image size: 153x115
Test image size: 600x400
Detection time: 27[ms].

T-shape plate

Template image size: 107x121

Test image size: 600x400

Detection time: 380[ms] !

Discussion of evaluation results

While the chess pieces and puzzle pieces were matched relatively fast and with high similarity, the T-plates took longer to match compared to them.
This is likely due to the large number of objects with similar feature values and the fact that many candidate objects were found in the initial coarse search, which took time in the detailed search. It is also possible that the contours are not well detected due to the similar coloring of the search target and other objects. If the detection sensitivity of the contours is adjusted, the detection similarity may increase, but it will be vulnerable to noise.

Source Code

The complete project set of the application published on github is available for sale at the following site. If you would like to actually check and run the source code of the algorithms introduced, please purchase it.

source code