A Cellular-Automaton-Type Region Extraction Algorithm and its FPGA Implementation

Teppei Nakano; Takashi Morie; Makoto Nagata; Atsushi Iwata

doi:10.20965/jrm.2005.p0378

single-rb.php

« previous

JRM Vol.17 No.4 pp. 378-386

doi: 10.20965/jrm.2005.p0378

(2005)

Paper:

Views over last 60 days: 370

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

Received:

December 14, 2004

Accepted:

February 19, 2005

Published:

August 20, 2005

Keywords:

cellular-automaton, region extraction, labeling, pixel-parallel operation, FPGA implementation

Abstract

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.

Cite this article as:

T. Nakano, T. Morie, M. Nagata, and A. Iwata, “A Cellular-Automaton-Type Region Extraction Algorithm and its FPGA Implementation,” J. Robot. Mechatron., Vol.17 No.4, pp. 378-386, 2005.

Data files:

References

[1] 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.
[2] 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.
[3] 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.
[4] 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.
[5] 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.
[6] D. L. Wang, and D. Terman, “Locally Excitatory Globally Inhibitory Oscillator Networks,” IEEE Trans. Neural Networks, Vol.6, No.1, pp. 283-286, 1995.
[7] 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.

[1] [1] 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.

[2] [2] 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.

[3] [3] 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.

[4] [4] 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.

[5] [5] 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.

[6] [6] D. L. Wang, and D. Terman, “Locally Excitatory Globally Inhibitory Oscillator Networks,” IEEE Trans. Neural Networks, Vol.6, No.1, pp. 283-286, 1995.

[7] [7] D. L. Wang, and D. Terman, “Image Segmentation Based on Oscillatory Correlation,” Neural Computation, Vol.9, No.4, pp. 805-836, 1997.

A Cellular-Automaton-Type Region Extraction Algorithm and its FPGA Implementation

Teppei Nakano*, Takashi Morie*, Makoto Nagata**, and Atsushi Iwata***

Teppei Nakano^, Takashi Morie^, Makoto Nagata^,
and Atsushi Iwata^*