Augmented reality marker recognition algorithm based on cellular automata

Marker recognition in augmented reality systems has always been the bottleneck of augmented reality systems, taking up most of the system processing time. Even if regular geometric marks are used, the effect and real-time performance of the recognition algorithm are not ideal for augmented reality systems with high real-time requirements. Therefore, an algorithm for improving the marker recognition algorithm in augmented reality systems using a cellular automaton model and given evolution rules is proposed, and a specific implementation is made in the ARTOOLKIT system. Experimental results show that the real-time performance and recognition effect of the improved algorithm have been greatly improved.

0 Introduction

Augmented reality (AR) is a new technology that integrates real world information and virtual world information "seamlessly" with the rapid development of virtual reality (VR) and the need for practical applications. The augmented reality system is an application system that uses augmented reality technology. Its important features are: users have a sense of immersion, the virtual environment is integrated with the actual environment, and they can hardly feel the disharmony caused by the fusion of real and fake; the system is interactive, and users can directly interact with virtual objects or virtual environments through interactive devices: it is to add and locate virtual objects in three-dimensional space, and its research involves system structure, human-computer interface, three-dimensional registration, helmet display and other aspects. Using markers to achieve accurate registration of virtual objects is already a relatively mature technology, and has been widely used in environments such as indoors, outdoors and mobile applications. Among them, marker recognition has always been the bottleneck of the augmented reality system, occupying most of the system processing time. Even if regular geometric markers are used, the results and real-time performance of the recognition algorithm are not ideal for augmented reality systems with high real-time requirements.

Cellular automata (CA) is a dynamic system that is discrete in both time and space. Each cell (Cel1) scattered in a regular grid takes a finite number of discrete states, follows the same rules of action, and is updated synchronously according to certain local rules. A large number of cells constitute the evolution of a dynamic system through simple interactions. Unlike general dynamic models, cellular automata are not determined by strictly defined physical equations or functions, but are composed of a series of model construction rules. Any model that meets these rules can be regarded as a cellular automaton model. Therefore, cellular automata is a general term for a class of models, or a method framework. Its characteristics are that time, space, and state are all discrete, each variable only takes a finite number of states, and the rules for its state change are local in time and space.

1 Traditional recognition algorithm

The recognition process of visual markers includes inputting an image, outputting the bounding box of the image marker, and the coordinates of the feature points. The design requirements of this process are to have good accuracy and meet the real-time requirements, among which real-time is more important than accuracy. In the recognition of markers, the information that can generally be used is the edge information, geometric information, and chromaticity information of the marker. As shown in Figure 1. First, the image is converted into a binary image, and then the marker bounding box is obtained by using techniques such as corrosion, border extraction, and Hough transform, and then the feature point set is obtained by seed filling and geometric restriction.

2 Algorithm using CA model

The CA recognition algorithm is shown in Figure 2. It can be seen that the efficiency of the algorithm depends on the design of the CA module. The CA module used in this paper is as follows:

2.1 Cellular Space

Assume that the cell space is composed of two-dimensional M*N pixels. And assume that it is time synchronized. Define a two-dimensional image of size M~N

Where: M, N represent the height and width of the image respectively. Aid') represents the state value (i.e. gray value) of the point ( ). For the k-value image, ( takes the value in the state set . The video image with the mark is shown in Figure 3.

The neighbor mode adopts Moore type. Each cell is composed of 4 components: GCell (c, p, e, v), where C represents the grayscale. For simplicity, it is first binarized using the threshold to obtain 0 or 1. It is important to eliminate isolated points in the process, otherwise it will affect the recognition effect. P indicates whether it is an edge point, if it is an edge point, it is 1, otherwise it is 0. e indicates whether it is an edge, if it is, it is 1, otherwise it is 0. v indicates whether it is a vertex, if it is, it is 1, otherwise it is 0; i indicates whether it is a marked internal feature point, if it is, it is 1, otherwise it is 0. Using binary representation simplifies the operation. The initial matrix of the system is as follows

According to formula (1), c = (0, 1, ..., ) where the starting point is randomly selected. Experiments show that the effect of random selection is better than fixed selection, such as the boundary. The algorithm uses a fixed value boundary to ensure that the evolution operation does not exceed the rectangular space.

2.2 Evolution rules

(1) First determine whether it is an edge point. From the definition of edge, we know that if the state of a point is different from the state of most of its neighboring points, that is, the gradient changes significantly, then this point can be considered an edge point, otherwise it is considered a background point, that is, a non-edge point. Based on this theory, the position of the edge point is determined according to the following rules.

(2) There are two ways to determine whether it is an edge point. As shown in Figure 1, the mark is composed of a square with a fixed width. Let the width of the mark be d and the width of the black mark band be n. Then the following rules can be used to determine whether it is a point on the edge of the square. That is, it must be an edge point and satisfy that n consecutive points in the x or y direction are edge points. Or it satisfies that d consecutive points in the x or y direction are of the same grayscale. As shown in equations (4) and (5),

(3) Determine whether it is a vertex. If it is a vertex, it must be a point on the edge and satisfy the requirement that n consecutive points in the x or y direction have the same grayscale. As shown in formula (6):

(4) Internal feature points must be edge points and not side points, as follows

(5) The system end condition is very important. Otherwise, according to the current research on CA, it is easy to fall into a chaotic state. Therefore, the end condition must be set. According to the application, the end condition is to find all vertices and the number of feature points meets the requirements of feature recognition. As shown below:

3 Experimental Results

ARTOOLKIT is an efficient AR development platform. Its marker recognition adopts the traditional method. The author uses this platform to rewrite the algorithm of the marker recognition part and achieves better results. Under the same background and the same PC and camera, the comparative experimental results are shown in Table 1, Table 2, and Figure 4 and Figure 5. It can be seen that the system using the CA model has greatly improved the real-time performance while the recognition effect is very good.

4 Conclusion

Since the CA method uses binary operations and has limited evolution steps, the algorithm is very efficient and can better meet the real-time processing requirements of the AR system, leaving more time for the rendering program. Of course, since the application of CA in AR has just started, the CA algorithm should also be applied to many aspects of the AR system, such as coordinate system transformation, lighting processing, etc., which need further research.