QTREEMESH

Generation of QuadTree mesh from an image
Explore the docs »

View Demo · Report Bug · Request Feature

Table of Contents

1. About The Project
2. Getting Started
   • Installation
3. Usage
   1. Read Image
   2. Preprocessing
   3. QuadTree Algorithm
   4. Mesh Generation
   5. Export and Implementation
4. Theoretical Explanation
5. Roadmap
6. Contributing
7. License
8. Contact
9. Acknowledgments

About The Project

QTREEMESH is a python package that can create a Quadtree structure from an image. This tree data structure can also be converted to mesh structure that can be used in different areas of science, e.g. finite element analysis. The Quadtree algorithm in this package is based on pixels' intensity. For more information about this algorithm, please refer to Theoretical Explanation section of this doc.

(back to top)

Getting Started

This part explains how to install and use this package.

Installation

Install QTREEMESH from PyPI via pip.

pip install qtreemesh

(back to top)

Usage

There is a test.py file in examples folder that demonstrate how different parts of this package work. Here we go through this file line by line:

1. Read Image

First we import required tools from other libraries

from PIL import Image # to read image file properly
from numpy import asarray # for converting image matrix to array

Then we read the image and convert it to gray-scale. There are three example images in examples folder. 4.jpg is smaller than the two others and need fewer computation efforts.

im = Image.open("4.jpg").convert('L')

2. Preprocessing

The quadtree algorithm is most efficient when the image is square and the number of its pixels is an integer power of 2, i.e. $2^n$. There is a function image_preprocess() dedicated to the modification of the original image by padding it with zero intensity pixels and satisfying the mentioned requirement:

from qtreemesh import image_preprocess

imar = image_preprocess(asarray(im))

3. QuadTree Algorithm

The QuadTree decomposition can be performed on image_array using a recursive class QTree based on given tolerance.

from qtreemesh import QTree

quad = QTree(None, imar, 125) # QTree(None, image_array, tolerance)

QTree object may have 4 children QTree objects (can be accessed through attributes: north_west, north_east, south_west, south_east) and so on. Each QTree has an attribute divided that determines the existence of children partitions. There are also an property method for counting count_leaves and a method for saving tree leaves save_leaves (i.e. undivided partitions).

4. Mesh Generation

Common mesh data structure can be extracted from QuadTree structure using QTreeMesh class. After initiating the class, corresponding elements and nodes can be generated as attributes of the QTreeMesh object with the method create_elements. The resulted mesh may be illustrated using draw method.

from qtreemesh import QTreeMesh

mesh = QTreeMesh(quad)
mesh.create_elements()
mesh.draw(True, 'orangered') # mesh.draw(fill_inside, edge_color, save_name)

Each element in elements is a QTreeElement object that contains many attributes, e.g. element number : number, element nodes : nodes_numbers, element property (average of pixel intensities) : element_property and etc.

Example	Image	Mesh
4.jpg
5.jpg

For more examples, please refer to the Documentation

5. Export and Implementation

One can easily export generated mesh as vtk format using following line:

mesh.vtk_export(filename = "4_meshed.vtk")

and the result can be viewed in visualization applications such as ParaView:

It's worth mentioning that the method vtk_export() has no dependency to vtk related libraries and create .vtk file manually.

It is also possible to adjust the elements to handle hanging nodes and generate a mesh that is either triangular or quadrilateral/triangular (based on templates available in [2] and [3]).:

fem_nodes, fem_elements, fem_properties = mesh.adjust_mesh_for_FEM()

The default configuration generates FEM elements as triangles. To include both quadrilateral and triangle elements, set force_triagulation to False.

(back to top)

Theoretical Explanation

Introduction

A Quadtree is a special type of tree where each parent node has exactly four smaller nodes connected to it. Each square in the Quadtree is represented by a node. If a node has children, their squares are the four quadrants of its own square, which is why the tree is called a tree. This means that when you put the smaller squares of the leaves together, they make up the bigger square of the root.

In this figure, labels NW, NE, SE, and SW are representing different quadrants (North-West, North-East, South-East and South-West respectively).

While this algorithm has many applications in various fields of science (e.g., collision detection, image compression, etc.), this doc especially focuses on the mesh generation subject. There almost three major definition of problem:

1. Points set problems:

   In this case, there are a set of points ${p_i} : (x_i , y_i)$ (which can be interpreted as the position of objects), and we need to build the quadtree in such a way that every square contains at most $c$ point(s). First we consider the root square which contains all the points. Then we start recursively splitting squares until the criteria $n_p \le c$ met. In following figure, the quadtree of 11 points with $c = 1$ is illustrated:

   

   There are many different implementations of this variation of algorithm, for example in Python, C++, and C#.

2. Domain boundary problems:

   This type of problem is very common in mesh generation for CAD models. The domain of interest is defined by some lines that usually separate inside of the domain from outside of it. A common approach is to generate seed points on the boundary and create a quadtree just the same as points set problems. There will be some additional steps to convert quadtree to FEM mesh, such as removing the outside squares and trimming of boundary squares. The following figure illustrate quadtree of a circular domain.

   

3. Digital images problems:

   The quadtree decomposition of an image means dividing the image into squares with the same color (within a given threshold). Considering an image consisting of $2^n × 2^n$ pixels, the algorithm recursively split the image into four quadrants until the difference between the maximum and minimum pixels intensities becomes less than the specified tolerance.

   The current package is dedicated to these types of problems.

References

1. de Berg, M., Cheong, O., van Kreveld, M., & Overmars, M. (2008). Computational geometry: Algorithms and applications. In Computational Geometry: Algorithms and Applications. Springer Berlin Heidelberg. https://doi.org/10.1007/978-3-540-77974-2
2. Lo, D.S.H. (2015). Finite Element Mesh Generation (1st ed.). CRC Press. https://doi.org/10.1201/b17713
3. George, P. L. (1992). Automatic mesh generation and finite element method. Wiley. https://doi.org/10.1016/S1570-8659(96)80003-2

Roadmap

• Completing the codes documentation
• Adding details to README file
• Exporting data as vtk format
• Successfully implement in FEM software
  • Handling hanging nodes
  • Prepare required data
  • Illustrate usage in open-source FEM programs
• Prepare required data for SBFEM

See the open issues for a full list of proposed features (and known issues).

(back to top)

Contributing

Contributions are what make the open source community such an amazing place to learn, inspire, and create. Any contributions you make are greatly appreciated.

If you have a suggestion that would make this better, please fork the repo and create a pull request. You can also simply open an issue with the tag "enhancement". Don't forget to give the project a star! Thanks again!

(back to top)

License

Distributed under the MIT License. See LICENSE.txt for more information.

(back to top)

Contact

Sadjad Abedi - [email protected]

Project Link: https://github.com/Sad-Abd/qtreemesh

(back to top)

Acknowledgments

(back to top)