Keywords

1 Introduction

In industrial automation, template matching is a well-known machine vision approach for estimating the pose of object. As demands for production efficiency have increased, the ability to match multi object with different rotation angles in an image efficiently has become increasingly important, especially in integral circuit (IC) manufacturing fields. Traditional matching algorithms can’t already meet these demands, when the objects arranged closely under different illumination conditions.

Over the last two decades, various template matching algorithms have been proposed [1–3]. The most popular algorithm is the normalized cross correlation (NCC) [4]. It compensates for both additive and multiplicative variations under the uniform illumination changes. Because of lacking rotation invariance, when an object in the target image is rotated with respect to the template, a set of templates at different orientations is required. This procedure is brute-force and time-consuming. In order to increase the searching speed under different rotation angles, different algorithms by using salient and distinctive features such as regions, edges, contours and points, are proposed to get the rotation invariant. Invariant moments matching methods [5–7] are effective especially for rotated binary patterns, but its poor performance to noise and occlusion. Geometric hashing (GH) [8] is a good method in matching the objects with simple geometric structure, but it is limited to noise and complex shape objects. Generalized Hough transform (GHT) [9] is robust against rotation, scaling, which utilizes voting through local edges evidences. However, it needs enormous memory to store the voting space for selecting the maximum score point and it is unable to deal with the problem of multi rotation objects matching.

Many algorithms using gradient information extracted from the image are proposed. These algorithms are stably resistant to light transformation and widely used in object recognition [10]. Histograms of Oriented Gradient (HOG) [11] has significantly existing feature sets for human detection, but it has limit of recognizing large-angles-rotation objects. The latest matching algorithms based on scale and rotation invariant key-points with histograms of gradient information, like SIFT [12, 13], PCA-SIFT [14], SURF [15] and GLOH [16, 17], present very spectacular recognition performance. However, they fail to find some simple shapes with little grayscale variations. These algorithms have a prohibitive complexity so that they are difficult to be applied in industry.

Orientation codes [18] are based on the utilization of gradient orientation histograms for searching rotation-invariant object in the case of illumination fluctuations. The method consists of two stages. The first stage estimates the approximate rotation angle of the object image by using histograms of the orientation codes. Second, orientation code matching at the right orientation is applied only to the best histogram matches. Marion [19] presented a much faster technique by using integral histograms. The gradient orientation histograms are not intrinsically rotation invariant and a histogram shifting is necessary in order to find the best angle. Thus, this algorithm cannot deal with the condition of array-arranged multi objects.

This paper proposes a radial ring code histograms (RRCH) algorithm for multi-object template matching. The algorithm has the robustness against position translation, angle rotation and illumination changes. By using radial gradient codes which is the relative angle between gradient direction and position vector, it performs better than the original orientation codes algorithm, and the identification ability of multi objects is also improved. Distance ring projections are essentially adopted to improve the restriction of surrounding objects clutter. Various type objects can be matched by adapting adjustable weights in different regions. The proposed method is invariant to illumination owing to utilization of gradient information rather than pixel brightness directly. In addition, the method is more suitable used in multi-object coarse-search step to get the small candidate area and combined with other fine-matching steps.

The rest of this paper is organized as follows: Sect. 2 presents the problem about conventional orientation codes and describes the proposed RRCH algorithm. The implementation details and experimental results are given in Sect. 3. Conclusions follow in Sect. 4.

2 Matching with Radial Ring Code Histograms

The gradient orientation histograms [19] applied in coarse-search is not effective for searching multi objects. As shown in Fig. 1(a), the subimages under the blue circle and blue circle are obviously different. However, the gradient orientation histograms of the two subimages are similar, as showed in Fig. 1(b). This figure proves that the gradient orientation histogram can not match well, when the multi objects arranged closely.

Fig. 1.
figure 1

The problem in searching multi objects: (a) Two circle regions in sample object image, (b) Orientation histograms of the two regions (Color figure online).

Full size image

Radial ring code histogram is proposed to tackle the problem. It is based on gradient information combining with the spatial structure. Firstly, gradient direction is transformed into radial gradient codes by the principle of statistics. Then, ring distance projection is utilized to acquire radial ring codes. Next, radial ring code histograms are calculated. Through comparing the histograms similarity between template image and the target image, the positions of multi objects are estimated. The detail procedure is described in this section.

2.1 Radial Ring Codes

Gradient information is chosen to generate the descriptor because of the little sensitivity to illumination changes. There are various operations, like Sobel operator, to calculate horizontal derivatives \( \nabla f_x \) and vertical derivatives \( \nabla f_y \) for computing the gradient direction \( \ \varPhi (x,y) = \tan ^{-1} (\nabla f_y/\nabla f_x) \) and gradient magnitude \( \varOmega (x,y) = \sqrt{\nabla f_y^2+\nabla f_x^2}\).

A circle effective region is selected to obtain the rotation invariance. The center of the circular region is regarded as a rotation reference point. The present point P in the region and the reference point O are linked to a straight line. The angle between this line and the gradient direction of the present point P is called as radial gradient angle \(\alpha \), as shown in Fig. 2. If the image is rotated counterclockwise angle \( \theta \), P is transformed into \(P^{'}\). Obviously, the relative angle \( \alpha \) does not change with the rotation.

Fig. 2.
figure 2

Radial gradient angle

Full size image
Table 1. Radial gradient codes
Full size table

The range of the gradient direction is \( [-\pi , \pi ] \), while the radial gradient angle is \( [0, \pi ] \). To reduce the amount of computation, the radial gradient angles are quantified as the radial gradient codes using Eq. 1

$$\begin{aligned} \varUpsilon (x,y) = round(\frac{\alpha (x,y)}{\triangle \alpha }),{\,}when \quad \varOmega (x,y) > T \end{aligned}$$
(1)

The radial angle is divided into N groups, which can not be chosen too large or small, considering the rotation errors. To suppress the effective of noise, the radial gradient code is computed, when the magnitude is larger than the threshold T. The angle step is \( \triangle \alpha = \pi /N\), the relationship between radial gradient angles and radial gradient codes is shown in Table 1.

The radial gradient angle at one point changes with the different reference point. In Fig. 3, the relative angles between \({{\varvec{g}}}_{{\varvec{1}}}\) and the line OA or the line \(O^{'}A\) are distinct. Therefore, the amplitude of the angle change is related to the radial distance (between the reference point and the present point). The radial distance is closer, the radial gradient angle changes more sharp. The evidence is that \( \angle O^{'}AO\) and \( \angle O^{'}BO\) are different. Thus, its essential to take a separate treatment with different radial distance.

The ring distance projection is a process as a partition step in our approach. As shown in Fig. 4, the effective region is segmented into two parts: inner circle and outer ring. If a reference point moves one pixel, the change value of radial gradient angle in outer ring should be littler than \(\triangle \alpha \). The radius of inner circle r can be calculated in Eq. (2).

$$\begin{aligned} \begin{array}{ll} r\ge \frac{1}{ \tan ^{-1} (\triangle \alpha ) }\\ r\le R \end{array} \end{aligned}$$
(2)

r is chosen as \(\frac{1}{2}R\) here. If there is only one region with radial gradient codes, the descriptor size is N, else the descriptor dimension is 2N. Sometimes, N dimensional vectors to represent an image is finite to achieve reliable matching. The descriptor with radial ring codes increases the vector dimension to improve the feature representation capability and ensure the rotation invariant feature description. Certainly, the more the dimensions are, the more computational cost is.

Fig. 3.
figure 3

A contrast with two different reference point

Full size image
Fig. 4.
figure 4

Illustration of ring distance projection

Full size image
Fig. 5.
figure 5

(a) Radial ring code Histograms in N, (b) Radial ring code Histograms in 2N.

Full size image

2.2 Radial Ring Code Histograms for Matching

In a region, codes are counted respectively to be expressed as radial ring code histograms. Histograms of the different regions are arranged according to a certain order. There is an example about two kinds of histograms in \(N=9\). In Fig. 5(b), the first N histograms are from inner circle, while the second N histograms are from outer ring. The radial ring code histograms can be written as

$$\begin{aligned} {{\varvec{V}}}=[\nu (0),\nu (1),\ldots ,\nu (k)], \quad (k=N-1 \quad or \quad k=2N-1) \end{aligned}$$
(3)

RRCH is a real rotation invariant feature description, which does not depend on the main direction. It is stronger and more adaptable than the traditional method including nonlinear illumination changes. The weight of inner circle is \(\omega \) and the weight of outer ring is \(1-\omega \). Generally, \(\omega \) is less than 0.5, when there are two regions.

Template image and subimage (part of object image with the same size of template image) are transformed into a vector in form of radial ring code histograms. There are some approaches to compare the correspondence with two vectors by distance or similar metric [20], such as the Chi-Square statistic, Euclidean distance or Manhattan distance. For multi object matching, there will be more difficult to make a contrast. So the similarity is

$$\begin{aligned} \begin{array}{ll} S = \frac{\sum ^{N-1}_{i=0} min({{\varvec{V}}}_{{\varvec{{M}}}}(i),{{\varvec{V}}}_{{\varvec{{O}}}}(i))}{\sum ^{N-1}_{i=0}({{\varvec{V}}}_{{\varvec{{M}}}}(i))},(k=N-1)\\ S = \frac{\sum ^{N-1}_{i=0} w\cdot min({{\varvec{V}}}_{{\varvec{{M}}}}(i),{{\varvec{V}}}_{{\varvec{{O}}}}(i))+\sum ^{2N-1}_{i=N} (1-w)\cdot min({{\varvec{V}}}_{{\varvec{{M}}}}(i),{{\varvec{V}}}_{{\varvec{{O}}}}(i))}{\sum ^{N-1}_{i=0}(w\cdot {{\varvec{V}}}_{{\varvec{{M}}}}(i))+\sum ^{2N-1}_{i=N}((1-w)\cdot {{\varvec{V}}}_{{\varvec{{M}}}}(i))},(k=2N-1,0\le \omega \le 1) \end{array} \end{aligned}$$
(4)

The radial ring code histograms of template image is \({{\varvec{V}}}_{{\varvec{{M}}}}\) and subimage is \({{\varvec{V}}}_{{\varvec{{O}}}}\). \(min({{\varvec{V}}}_{{\varvec{{M}}}},{{\varvec{V}}}_{{\varvec{{O}}}})\) is to get max overlapping values in two histograms. The formula is different when k is \(N-1\) or \(2N-1\) and can be changed for various objects.

Ultimately, template image is sliding window through the entire image to search objects and get the score matrix. According to the threshold, the candidate areas are inquired with local maximum score.

Fig. 6.
figure 6

LED machine

Full size image
Fig. 7.
figure 7

The histogram of the object image in Fig. 1

Full size image

3 Experiment

This section verifies the performance of the proposed method. First of all, a test for rotation-variance is shown. Secondly, the computation time is in comparison with some similar techniques. Thirdly, the multi object detection is essential to be validated. Finally, there are some experiments about the robustness of illumination varying. The images for this test are grabbed from LED machines in Fig. 6.

Fig. 8.
figure 8

IC chips for rotation-variant test: (a) Template image, (b) Rotation image, (c) the histograms of the IC chips (a)(b).

Full size image
Fig. 9.
figure 9

Time test: (a) Template image (19\(\,\times \,\)19 pixels), (b) Object image (60\(\,\times \,\)80 pixels), (c) The computation time of NCC and RRCH in different angle searching ranges.

Full size image
Fig. 10.
figure 10

IC chips for robust test: (a) LED chips with illumination-fluctuations, (b) LED chips with illumination-fluctuations and noise, (c) Orientation Code Histograms Score matrix for figure (a), (d) Orientation Code Histograms Score matrix for figure (b), (e) RRCH Score matrix for figure (a), (f) RRCH Score matrix for figure (b), (g) x = 26, score contrast for figure (a), (h) y = 76, score contrast for figure (b).

Full size image

To confirm rotation-variance of the presented algorithm, IC chips were rotated with various arbitrary angles. An example is shown in Fig. 8. As can be seen, the histograms of the IC chips are closely resembled with high similarity. Meanwhile, the picture proves that when the patterns are rotated, the histograms are similar. Figure 8 shows that the proposed method plays a good performance on matching the object with rotation.

As explained above, NCC is the method to search objects by a set of templates with different rotation angles. The computational time of the proposed algorithm was also compared with NCC in different angle ranges, shown in Fig. 9. All the computations were performed with C language under the same conditions without any acceleration or speed promotion. From the experiment results, it can be seen that the computation time of NCC is increasing with the angle searching range, while the computation time of RRCH is remain unchanged due to the rotation invariance.

There is a problem presented in Sect. 2.1, the conventional method cannot recognize the difference between the red and the blue region in Fig. 1. However, RRCH is used for the two regions, the result shown in Fig. 7 is that histograms are larger different than the method. It means that RRCH is adaptable to solve the problem in multi objects matching.

There are same multi arrayed chips. The template images were extracted one of them in Fig. 10(a)(b), and Orientation Code Histograms and RRCH were used to get the results of score, shown in Fig. 10(c)(d)(e)(f). Chips were in illumination-invariant condition with different angles in Fig. 10(a). The environment for the image in Fig. 10(b) was more complicated, multi chips with illumination-fluctuations and noise. Figure 10(g)(h) verifies that the RRCH can be used to distinguish the position of the object with the other disturbing factors better than Orientation Code Histograms. If the score threshold is set appropriately, the small candidate areas can be selected quickly.

4 Conclusion

In this paper, a new method for multi-object matching method, called RRCH, is proposed. It is achieved with the utilization of gradient information in the form of radial ring codes. The method is robust for detecting objects in noisy environments in spite of illumination changes. Experiments demonstrate the rotation- and brightness invariance of the proposed method for object search. However, there is much room to promote in speed and optimal parameters and the method can be combined with other template matching algorithms. The method is more suitable used in multi-object coarse-search step to get the small candidate area and combined with other fine-matching steps.