A Parallel Skeletonization Algorithm Based on Two-Dimensional Cellular Automata and its VLSI Implementation

This paper presents a new parallel algorithm for binary object skeletonization and its implementation in VLSI. The proposed skeletonization algorithm is based on a digital geometry concept known as the 'Voronoi diagram, which is established, after an edge detection pre-processing step, through the time evolution of Cellular Automata. The proposed algorithm is both space and time efficient, since it does not require any distance calculations and ordering of distances as in the case of other skeletonization algorithms nor the application of complex 'template' criteria to guarantee object connectiveness as in the case of thinning algorithms. Additionally, the proposed Cellular Automaton architecture achieves high frequency of operation and it is especially suited for VLSI implementation due to its inherent parallelism, structural locality, regularity and modularity. A set of quantitative measures was defined in this paper in order to evaluate the performance of the proposed algorithm. It was found that the proposed algorithm for pattern skeletonization outperforms already existing algorithms, with respect to these measures.     

Acceleration of cellular automata algorithms using genetic algorithms

The following problem is solved: Given a Cellular Automaton with continuous state space which simulates a physical system or process, use a Genetic Algorithm in order to find a Cellular Automaton with discrete state space, having the smallest possible lattice size and the smallest possible number of discrete states, the results of which are as close as possible to the results of the Cellular Automaton with continuous state space. The Cellular Automaton with discrete state space evolves much faster than the Cellular Automaton with continuous state space. The state spaces of two Cellular Automata have been discretized using a Genetic Algorithm. The first Cellular Automaton simulates the two-dimensional photoresist etching process in integrated circuit fabrication and the second is used to predict forest fire spreading. A general method for the discretization of the state space of Cellular Automata using a Genetic Algorithm is also presented. The aim of this work is to provide a method for accelerating the execution of algorithms based on Cellular Automata (Cellular Automata algorithms) and to build a bridge between Cellular Automata as models for physical systems and processes and Cellular Automata as a VLSI architecture.     

A VLSI architecture for a half-edge-based corner detector

Corner detection is a low-level feature detection operator that is of great use in image processing applications, for example, optical flow and structure from motion by image correspondence. The detection of corners is a computationally intensive operation. Past implementations of corner detection techniques have been restricted to software. In this paper we propose an efficient very large-scale integration (VLSI) architecture for detection of corners in images. The corner detection technique is based on the half-edge concept and the first directional derivative of Gaussian. Apart from the location of the corner points, the algorithm also computes the corner orientation and the corner angle and outputs the edge map of the image. The symmetrical properties of the masks are utilized to reduce the number of convolutions effectively, from eight to two. Therefore, the number of multiplications required per pixel is reduced from 1800 to 392. Thus, the proposed architecture yields a speed-up factor of 4.6 over conventional convolution architectures. The architecture uses the principles of pipelining and parallelism and can be implemented in VLSI.     

A VLSI Image Processing Architecture Dedicated to Real-Time Quality Control Analysis in an Industrial Plant

In this paper, we present a VLSI architecture for real-time image processing in quality control industrial applications: automation of the visual inspection phase of mechanical parts treated by the Fluorescent Magnetic Particle Inspection method for structural-defect detection. The VLSI architecture implements a highly constrained neural network tailored for this specific application: the multi-layer perceptron with strictly local connections. The learning of the weights is performed off line by using the adaptive simulated-annealing algorithm. The neural network has been trained on real plant data: recognition results of the training and classification tasks compare favorably with those obtained by expert human operators.The VLSI architecture receives as input the image (taken on-line on the plant) of a mechanical part and it will find out if at least one structural surface defect is present. The VLSI architecture was optimized, through a set of transformations on the high-level VHDL specifications of the neural network algorithm, to reach real-time operating conditions. Following the proposed approach and the designed architecture, we designed and successfully tested a custom VLSI chip for the real-time implementation of the recognition task.     

GOTICA - generation of optimal topologies by irregular cellular automata

In recent years the Cellular Automata (CA) concept has been successfully applied to structural topology optimization problems. In the engineering implementation of CA, the design domain is decomposed into a lattice of cells, and a particular cell together with the cells to which it is connected forms a neighborhood. It is assumed that the interaction between cells takes place only within the neighborhood and the states of cells are updated synchronously in subsequent time steps according to some local rules.The majority of results that have been obtained so far were based on regular lattices of cells. However, a practical engineering analysis and design in many cases require using highly irregular meshes for complicated geometries and/or stress concentration regions. The aim of the present paper is to extend the concept of CA towards the implementation of unstructured grid of cells related to non-regular mesh of finite elements. Introducing an irregular lattice of cells allows to reduce the number of design variables without loosing the accuracy of results and without an excessive increase of the number of elements caused by using a fine mesh for a whole structure. The implementation of non-uniform cells of Cellular Automaton requires a reformulation of standard local rules, for which the influence of the neighborhood on the current cell is independent of sizes of the neighboring cells.     

区域耦合状态转移概率化元胞自动机模型

针对多区域系统内部各个子区域属性的差异化,提出多区域耦合状态转移概率化元胞自动机模型。在该模型中,运用区域耦合原理和耦合区域信息交换规则来构造元胞自动机（CA）模型的演化规则,实现局部子区域之间的信息交换,运用不同类型的元胞自动机模型对子区域分别建立不同的CA模拟模型,并用概率化方法处理模拟模型中元胞状态的转化,实现各个子区域状态的演化。实验表明,子区域在保持自身演化形态相对独立的同时,通过边界区域耦合进行演化连接,各个子区域内的元胞能与其边界耦合区域内的元胞保持一种相对稳定的有序形态,且一个子区域的影响能在一定程度上传递到其他子区域内。该模型能很好地处理大规模复杂区域环境下的空间演化模拟。     

用于小目标检测的TDNLMS自适应预测器结构优化

讨论用于小目标检测的TDNLMS(Two-Dimensional Normalized Least Mean Square)自适应预测器VLSI实现中的结构优化问题．通过分析小目标图像的特点，使预测器直接处理隔行扫描图像，从而取消了帧存环节，大大减少了片内存储器数量．另外，在基本保持检测性能的基础上，通过对算法进行优化，提高了预测器的工作速度．达到实时图像处理．实验证明本方案不仅提高了预测器的数据通过率．而且简化了硬件电路，降低了设计难度．是一种为合理的方案．     

利用角点历史信息的异常行为识别算法

针对视频监控场景中的异常行为事件,如突然的奔跑、人群的异常聚集等现象,提出一种利用角点运动历史图策略的行为识别算法,即首先通过角点提取算法进行场景角点提取;然后通过时间累积获取角点的历史图,通过角点历史图将场景中的角点划分为静态角点和动态角点;最后通过动态角点分析完成监控场景异常行为分析识别。新算法充分利用了图像的时空信息,并且克服了场景光照影响,增强了异常行为检测与识别的准确性。通过真实场景实验可以看出,新算法能够对不同监控场景的异常行为进行准确检测,并且其检测速度快,满足实际应用需求。     

Fuzzy Logic Control ASIC Chip

A fuzzy logic control VLSI chip,F100,for industry process real-time control has been designed and fabricated with 0.8μm CMOS technology.The chip has the features of simplicity,felexibility and generality.This paper presents the Fuzzy control inrerence method of the chip,its VLSI implementation,and testing esign consideration.     

Detecting the Dominant Points by the Curvature-Based Polygonal Approximation

Detecting dominant points is an important step for object recognition. Corner detection and polygonal approximation are two major approaches for dominant point detection. In this paper, we propose the curvature-based polygonal approximation method which combines the corner detection and polygonal approximation techniques to detect the dominant points. This detection method consists of three procedures: (1) extract the break points that do not lie on a straight line, (2) detect the potential corners, and (3) perform polygonal approximation by partitioning the curves between two consecutive potential corners. Both quantitative and qualitative evaluations have been conducted. Experimental results show that the combined methods are superior to the conventional methods, and the dominant points can be properly detected by the combined methods.     

基于FPGA改进电路的高性能正则表达式匹配算法

针对正则表达式匹配过程中吞吐率低及逻辑资源占用数多的问题,提出一种完全基于现场可编程门阵列(FPGA)逻辑电路的改进确定有限自动机(DFA)匹配算法。首先,该算法统计了DFA中每个状态的大多数转移边都会集中指向相同状态特征的结果,随后根据正则表达式的转移矩阵为DFA的每个状态设置一条默认的转移边,最后进行逻辑电路简化处理,并采用L7-filter规则集进行实测。实验结果表明,改进后的DFA方案与非确定有限自动机(NFA)方案相比,有10%~60%的规则获得了更高的吞吐率,62%~87%的规则占用了更少的逻辑资源。     

一个抽取边界曲线特征点的新算法

景物的特征点抽取是模式识别及计算机视觉中的一个重要问题,已出现的多种检测特征点的方法中主要有角检测法和多边形逼近法。在这两种方法基础之上,人们又提出了结合两种方法的综合方法。提出了一种新的综合方法,首先应用一个简单的角检测方法,然后利用前面计算曲率时的一些值在检测到的角点之间加入一些特征点。实验结果表明新方法比传统方法执行速度更快,并且克服了传统方法的缺陷。     

Corner block list representation and its application with boundary constraints

Floorplanning is a critical phase in physical design of VLSI circuits. The stochastic optimization method is widely used to handle this NP-hard problem. The key to the floorplanning algorithm based on stochastic optimization is to encode the floorplan structure properly. In this paper, corner block list (CBL)-a new efficient topological representation for non-slicing floorplan-is proposed with applications to VLSI floorplan. Given a corner block list, it takes only linear time to construct the floorplan. In floorplanning of typical VLSI design, some blocks are required to satisfy some constraints in the final packing. Boundary constraint is one kind of those constraints to pack some blocks along the pre-specified boundaries of the final chip so that the blocks are easier to be connected to certain I/O pads. We implement the boundary constraint algorithm for general floorplan by extending CBL. Our contribution is to find the necessary and sufficient characterization of the blocks along the boundary repre     

A new hardware module for automated visual inspection based on a cellular automaton architecture

This paper presents the design and VLSI implementation of a new automated visual inspection system based on a cellular automaton architecture, suitable for circular object inspection. Cellular Automata (CA) transform the area of the object of interest into a number of evolution steps in the CA space. The proposed technique does not require the extraction of image features, such as boundary length and total area, which are computationally expensive in other methods. The die size dimensions of the chip, for a 16×16 pixel image, are 3.73 mm×3.09 mm=11.52 mm² and its maximum frequency of operation is 25 MHz. Experimental results using computer-generated images, as well as real images obtained and processed through a commercial vision system, showing the suitability of the proposed hardware module for detecting circular objects, are also presented. Targeted applications include inspection tasks (accept/reject operations) of circular objects, such as tablets in the pharmaceutical industry, and detection of uncoated areas, foreign objects and level of bake in the confectionery and food industry.     

On implementing addition in VLSI technology

In this paper we discuss the rules for evaluation of arithmetic algorithms based on the speed of their VLSI implementations. We present the rules which are simple enough to be useful for quick estimates, but yet reflect basic dependencies. By applying these rules we derived a simple scheme for VLSI implementation of addition (ALU), with a near minimal number of gates and small and regular area. Despite its simplicity, this scheme outperforms carry-lookahead and recurrence solver schemes as demonstrated by simulation of the actual implementation of examples. This is because the properties of the scheme are based on the dependencies and assumptions reflecting the real conditions existing in VLSI-CMOS technology. We discuss these results and demonstrate by actual implementation of examples that the measures based on the number of logic levels are not applicable to the new VLSI technologies.     

基于改进凸包检测的芯片图像字符区域定位

针对半导体芯片在激光打印时可能出现字符倾斜、字符位置错误等缺陷,提出一种基于改进凸包检测的半导体芯片图像字符区域定位方法.首先,利用三轴图像采集平台采集多幅半导体芯片图像,切分提取出若干单幅芯片图像;其次,采用Harris角点检测获取图像角点分布图,改进凸包检测算法,剔除非字符区域角点,获取最外围角点凸包线;最后,拟合...     

VLSI design and implementation of a real-time image segmentation processor

Image segmentation is a crucial part of machine vision applications. In this paper a system to perform real-time segmentation of images is presented. It uses a real-time segmentation VLSI chip that is based on a gradient relaxation algorithm and is designed using the Path Programmable Logic design methodology developed at the University of Utah. The system design considerations, system specifications, and an input/output format for the chip are discussed. The actual design of the chip is given that uses pipeline methodology to achieve real-time performance with a compact VLSI layout. The implementation of the segmentation system is presented and the segmentation chip and the overall system are evaluated with regard to real-time performance and segmentation results.This work was supported in part by Grant ISI-856-0393 from the National Science Foundation.     

基于细胞自动机的交通流模拟控制

该文以JAVA语言为仿真工具,通过构造二维细胞自动机模型,对平面十字交叉路口的交通流进行了分析和模拟控制。仿真结果较为理想,这充分说明了细胞自动机极其广泛的应用前景。