A Cellular-Automaton-Type Region Extraction Algorithm and its FPGA Implementation
Teppei Nakano*, Takashi Morie*, Makoto Nagata**,
and Atsushi Iwata***
*Graduate School of Life Science and Systems Engineering, Kyushu Institute of Technology, Hibikino, Wakamatsu-ku, Kitakyushu 808-0196, Japan
**Department of Computer and Systems Engineering, Kobe University, Nada-ku, Kobe 657-8501, Japan
***Graduate School of Advanced Sciences of Matter, Hiroshima University, Higashi-Hiroshima 739-8526, Japan
This paper proposes a new region extraction algorithm and its digital LSI architecture based on cellular-automaton operation for very fast image processing. The algorithm sequentially extracts each region defined by a closed boundary. From digital logic simulation using Verilog-HDL, the proposed circuit with pixel-parallel operation can operate 100 times faster than serial labeling for a 100×100-pixel image. We implemented the proposed circuit in an FPGA for 30×30-pixel image processing. In an experiment with the FPGA, five regions are successfully extracted one by one within 6μs at a clock frequency of 25MHz.
-  H. Ando, T. Morie, M. Miyake, M. Nagata, and A. Iwata, “Image Object Extraction using Resistive-Fuse and Oscillator Networks and a Pulse-Modulation Circuit for their LSI Implementation,” in Ext. Abs. of Int. Conf. on Solid State Devices and Materials (SSDM), pp. 368-369, 2000.
-  H. Ando, T. Morie, M. Miyake, M. Nagata, and A. Iwata, “Image Segmentation/Extraction Using Nonlinear Cellular Networks and their VLSI Implementation Using Pulse-Modulation Techniques,” IEICE Trans. Fundamentals., Vol.E85-A, No.2, pp. 381-388, 2002.
-  T. Morie, M. Miyake, M. Nagata, and A. Iwata, “A 1-D CMOS PWM Cellular Neural Network Circuit and Resistive-Fuse Network Operation,” in Ext. Abs. of Int. Conf. on Solid State Devices and Materials (SSDM), pp. 90-91, 2001.
-  H. M. Alnuweiri, and V. K. Prasanna, “Parallel Architectures and Algorithms for Image Component Labeling,” IEEE Trans. Pattern Analysis and Machine Intelligence, Vol.14, No.10, pp. 1014-1034, 1992.
-  R. E. Cypher, J. L. C. Sanz, and L. Snyder, “Algorithms for Image Component Labeling on SIMD Mesh-Connected Computers,” IEEE Trans. Computers, pp. 276-281, 1990.
-  D. L. Wang, and D. Terman, “Locally Excitatory Globally Inhibitory Oscillator Networks,” IEEE Trans. Neural Networks, Vol.6, No.1, pp. 283-286, 1995.
-  D. L. Wang, and D. Terman, “Image Segmentation Based on Oscillatory Correlation,” Neural Computation, Vol.9, No.4, pp. 805-836, 1997.
This article is published under a Creative Commons Attribution-NoDerivatives 4.0 Internationa License.
Copyright© 2005 by Fuji Technology Press Ltd. and Japan Society of Mechanical Engineers. All right reserved.