Binary fingerprint image thinning using template-based PCNNs

Real-Time Thinning Algorithms for 2D and 3D Images using GPU processors

The skeletonization of binary images is a common task in many image processing and machine learning applications. Some of these applications require very fast image processing. We propose novel techniques for efficient 2D and 3D thinning of binary images using GPU processors. The algorithms use bit-encoded binary images to process multiple points simultaneously in each thread. The simpleness of a point is determined based on Boolean algebra using only bitwise logical operators. This avoids computationally expensive decoding and encoding steps and allows for additional parallelization. The 2D algorithm is evaluated using a dataset of handwritten characters images. It required an average computation time of 3.53 ns for 32×32 pixels and 0.25 ms for 1024×1024 pixels. This is 52 to 18,380 times faster than a multi-threaded border-parallel algorithm. The 3D algorithm was evaluated based on clinical images of the human vasculature and required computation times of 0.27 ms for 128×128×128 voxels and 20.32 ms for 512×512×512 voxels, which is 32 to 46 times faster than the compared border-sequential algorithm using the same GPU processor. The proposed techniques enable efficient real-time 2D and 3D skeletonization of binary images, which could improve the performance of many existing machine learning applications.

MAT-Based Thinning for Line Patterns

Reducing branching effect and increasing boundary noise immunity are of great importance for thinning patterns. An approach based on medial axis transform (MAT) to obtain a connected 1-pixel wide skeleton with few redundant branches is presented in this paper. Though the obtained skeleton by MAT is isotropic with few redundant branches, however, the skeleton points are usually disconnected. In order to rend the merits of the MAT and avoid its disadvantages, the proposed approach is composed of distance-map generation, grouping, ridge-path linking, and refining to obtain the connected 1-pixel wide thin line. The ridge-path linking strategy can guarantee the skeletons connected, whereas the refining process can be readily performed by a conventional thinning process to obtain the 1-pixel wide thinned pattern. The performances investigated by branching effect, signal-to-noise ratio (SNR), and measurement of skeleton deviation (MSD) confirm the feasibility of the proposed MAT-based thinning for line patterns.

Efficient shortest-path-tree computation in network routing based on pulse-coupled neural networks

Shortest path tree (SPT) computation is a critical issue for routers using link-state routing protocols, such as the most commonly used open shortest path first and intermediate system to intermediate system. Each router needs to recompute a new SPT rooted from itself whenever a change happens in the link state. Most commercial routers do this computation by deleting the current SPT and building a new one using static algorithms such as the Dijkstra algorithm at the beginning. Such recomputation of an entire SPT is inefficient, which may consume a considerable amount of CPU time and result in a time delay in the network. Some dynamic updating methods using the information in the updated SPT have been proposed in recent years. However, there are still many limitations in those dynamic algorithms. In this paper, a new modified model of pulse-coupled neural networks (M-PCNNs) is proposed for the SPT computation. It is rigorously proved that the proposed model is capable of solving some optimization problems, such as the SPT. A static algorithm is proposed based on the M-PCNNs to compute the SPT efficiently for large-scale problems. In addition, a dynamic algorithm that makes use of the structure of the previously computed SPT is proposed, which significantly improves the efficiency of the algorithm. Simulation results demonstrate the effective and efficient performance of the proposed approach.