Method for optical recognition of markers

Abstract

The present invention relates to a robust method for optical recognition of markers in an outdoor environment. In this context, the present invention provides a method for optical recognition of optical markers comprising the steps of: acquiring an image; identifying regions of contiguous colours in the image by flood filling; extracting data and parameters of the contiguous regions; and detecting an optical marker by means of a convex hull algorithm and prediction of position of squares based on the data and parameters extracted from the contiguous Thus, the method of the present invention allows identification of markers, such as chequerboards and targets, unequivocally and with enough robustness as regards partial occlusions and variations of illumination.

Claims

1. Method for optical recognition of optical markers comprising the steps of: acquiring an image; identifying regions of contiguous colours in the image by flood filling; extracting data and parameters of the contiguous regions; and detecting an optical marker by a convex hull algorithm and prediction of position of squares based on the data and parameters extracted from the contiguous regions; wherein the step of detecting the optical marker further comprises an analysis of regularity of chequerboards, comprising at least one of the following substeps: (i) applying a convex hull algorithm using the 2D centres of the contiguous regions to find four outer squares at the edges of a chequerboard; (ii) calculating and storing the location of fixed squares using the four outer squares as reference; (iii) if the group of regions being analysed possesses sufficient regions, assigning regions to positions on the closest chequerboard having four outer squares; (iv) rejecting the chequerboard if more than one region is assigned to the same position.

2. Method according to claim 1, wherein the optical marker is a chequerboard.

3. Method according to claim 1, wherein the step of identifying regions of contiguous colours in the image comprises the following substeps: applying at least one filter to the image; detecting edges in the image so as to separate the different regions of contiguous colours; carrying out the filling of the separated regions using flood filling; and identifying each of the different regions of contiguous colours by their properties.

4. Method according to claim 3, wherein the substep of carrying out filling of the separated regions comprises at least one of the following substeps: receiving an edge map; creating a map of colour regions; initializing the map of colour regions by assigning an index to each pixel, the index being a number representing a colour; and performing the following steps, until the map of colour regions remains unchanged: (i) scanning the map of colour regions from left to right, from right to left, from top to bottom and from bottom to top in parallel, in any order; (ii) if the pixel is not located within any edge and its index is greater than that of the preceding pixel, giving the present pixel the same index as the preceding pixel.

5. Method according to claim 1, to wherein the step of detecting the optical marker comprises at least one of the following substeps: (i) calculating the convex hull of the centres of regions of contiguous colours grouped in the same region; (ii) for each vertex Vn in the convex hull, calculating the angle between the lines formed by Vn.fwdarw.Vn-1 and Vn.fwdarw.Vn-1; (iii) ordering the vertices by the calculated angles; and (iv) keeping the four vertices with the largest angles therebetween and discarding regions whose opposite angles are higher than a threshold.

6. Method according to claim 1, wherein the four outer squares are of the same colour, preferably wherein the four outer squares are black.

7. Method for optical recognition of optical markers comprising the steps of: acquiring an image; identifying regions of contiguous colours in the image by flood filling; extracting data and parameters of the contiguous regions; and detecting an optical marker based on the data and parameters extracted from the contiguous regions by combining the parameters in order to identify an optical marker, the optical marker being a target comprising a plurality of concentric circles; wherein the step of detecting the optical marker further comprises an analysis of regularity of chequerboards, comprising at least one of the following substeps: (i) applying a convex hull algorithm using the 2D centres of the contiguous regions to find four outer squares at the edges of a chequerboard; (ii) calculating and storing the location of fixed squares using the four outer squares as reference; (iii) if the group of regions being analysed possesses sufficient regions, assigning regions to positions on the closest chequerboard having four outer squares; (iv) rejecting the chequerboard if more than one region is assigned to the same position.

8. Method according to claim 7, further comprising a assigning a letter to each of the contiguous regions to identify the sequence of colours of the plurality of concentric circles.

Description

BRIEF DESCRIPTION OF THE FIGURES

(1) The detailed description presented hereunder refers to the appended figures and their respective reference numbers.

(2) FIG. 1a shows an example image in grey where the method of the present disclosure is applied.

(3) FIG. 1b shows initialization of the colour map with the respective indices with reference to FIG. 1a.

(4) FIG. 2a shows a typical edge map of the Sobel method applied to the present example.

(5) FIG. 2b shows a first scan from left to right applied to the present example.

(6) FIG. 3a shows a first scan from right to left applied to the present example.

(7) FIG. 3b shows a first scan from top to bottom applied to the present example.

(8) FIG. 4a shows a first scan from bottom to top applied to the present example.

(9) FIG. 4b shows a second scan from left to right applied to the present example.

(10) FIG. 5a shows a second scan from right to left applied to the present example.

(11) FIG. 5b shows a second scan from top to bottom applied to the present example.

(12) FIG. 6a shows the final configuration of the map after the second scan from bottom to top, the third scan from left to right and the third scan from right to left in the present example.

(13) FIG. 6b shows the final configuration of the map in the present example with the regions identified with unique colours.

(14) FIG. 7 shows a region of contiguous colours in a ring format.

(15) FIG. 8 shows chequerboards compared with irregular patterns.

(16) FIGS. 9 and 10 show chequerboards of different sizes that are identified in different positions and inclinations.

(17) FIG. 11 shows examples of occlusion patterns in which identification of the chequerboard will still take place successfully by the method of the present disclosure.

(18) FIGS. 12 and 13 shows examples of patterns of targets (markers) identifiable by the method of the present disclosure.

DETAILED DESCRIPTION OF THE INVENTION

(19) Firstly, it is emphasized that the description given hereunder will be based on a preferred embodiment. As will be obvious to a person skilled in the art, however, the invention is not limited to this particular embodiment.

(20) The present disclosure provides a method for optical recognition of markers. The method may be particularly suitable for recognising markers in an outdoor environment. The first step (a) of the method may be acquiring an image. Preferably, the image comprises optical markers located in the environment where it is desired to perform the recognition. The optical marker may be a target comprising concentric circles, or a checkerboard (i.e. an area made up of alternating coloured squares, such as black and white squares). The image may be acquired by any suitable method, for example by using a camera.

(21) The second part of the method is step (b) of identifying regions of contiguous colours in the image by flood filling (also known as parallel filling). This part of the method is preferably divided into the following steps:

(22) (i) optionally, applying at least one filter to the image;

(23) (ii) detecting edges so as to separate the different regions of contiguous colours;

(24) (iii) carrying out filling of the separated regions using flood filling; and

(25) (iv) identifying each of the different regions of contiguous colours by their properties.

(26) Preferably, step (ii) may be carried out using multiple edge algorithms, such as the Sobel method, widely known in the prior art. The document “BAGLODI, V. Edge detection comparison study and discussion of new methodology. In: IEEE Southeastcon 2009. [S.I.: s.n.], 2009. P. 446-446. ISSN 1091-0050.” describes in detail the use of the Sobel method, and its contents are incorporated here by reference.

(27) Preferably, step (iii) of performing filling of the separated regions using flood filling comprises the following substeps:

(28) (iii-a) receiving an edge map;

(29) (iii-b) creating a map of colour regions;

(30) (iii-c) initializing the map of colour regions by assigning each pixel to a unique index number, the index representing a colour; and

(31) (iii-d) performing the following steps until the map of colour regions remains unchanged:

(32) (iii-d-1) scanning the map of regions from left to right, from right to left, from top to bottom and from bottom to top, in parallel and in any order;

(33) (iii-d-1) if the pixel is not located within any edge and its index is greater than that of the preceding pixel, giving the present pixel the same index as the preceding pixel.

(34) FIGS. 1 to 6 illustrate the proposed algorithm for identifying regions of contiguous colours using an image created for this purpose. In particular, FIGS. 1a and 1b show, respectively, the example image in grey and initialization of the colour map with the respective indices. FIGS. 2a and 2b show, respectively, a typical edge map of the Sobel method and a first scan from left to right. In each row, when scanning from left to right, pixels which are not located within the edge and have a number greater than the previous pixel are given the same number as the previous pixel. For example, pixels 1-14 from FIG. 2a are given the number “O” in FIG. 2b. On the other hand, pixels 31-49 are not renumbered because they are part of the edge region. FIGS. 3a and 3b show, respectively, a first scan from right to left (in which there are no changes from FIG. 2b) and a first scan from top to bottom. FIGS. 4a and 4b show, respectively, a first scan from bottom to top (in which there are no changes from FIG. 3b) and a second scan from left to right. FIGS. 5a and 5b show, respectively, a second scan from right to left and a second scan from top to bottom. FIG. 6a shows the final configuration of the map afterthe second scan from bottom to top (no changes), the third scan from left to right (no changes) and the third scan from right to left.

(35) The two regions of the image are identified when the algorithm terminates, as illustrated in FIG. 6b. The number of parallel items of work is equal to the height of the image when scanning the lines and to the width of the image when scanning the lines. This may produce more than 1000 items of work in each case when processing a Full HD image (1920×1080 pixels). Scanning in all directions (left to right, right to left, from top to bottom and from bottom to top) is necessary because a change of edge index only occurs when the current pixel index is greater than the index of the preceding pixel.

(36) When the algorithm of step (iii) explained above is complete, the next step of identifying the different regions by their properties is carried out. Preferably, step (iv) of identifying each of the different regions by their properties includes characterizing (i.e. measuring, calculating or computing) said properties. In other words, at least one property is calculated for each region, which can then be used as an identifier (or to identify) that region. An example of the properties which may be calculated for a given shape of region is shown in the following table:

(37) TABLE-US-00001 TABLE 1 Property of the Region Computational method Area Number of pixels in the region Perimeter Number of pixels close to edges Average colour Average coulour of the pixels of the region Centre Middle coordinate (x, y) of the pixels in the region Average size Average distance of the pixels from the centre of the region Average radius Standard deviation of the distance from the pixel to the centre

(38) The third part of the method is step (c) of extracting data and parameters of the contiguous regions. In this step, each type of region possesses specific parameters, so that calculation of its properties is carried out depending on the type or format (e.g. shape) of the region.

(39) For example, concentric regions may be made up of multiple rings of the same colour, as shown in FIG. 7. In this case, each ring has a width w and average distance to the centre r. The data for the properties of the region are presented in Table 2 below and may be used for approximating the properties of the regions in ring format. In other words, the second column of Table 2 shows the exact mathematical definition of the properties below for a ring-shaped region. Then, the third column shows how the properties are linked to the properties in Table 1, so the “computational methods” of the second column of Table 1 can be used to calculate the properties of specifically ring-shaped regions.

(40) TABLE-US-00002 TABLE 2 Property of the Exact calculation in Approximation using the Ring terms of r and w properties of the region Average distance r Average size to the centre Width w Average radius Area 2.sub.TTrW Area of the region Perimeter 4.sub.TTr Perimeter of the region

(41) For identifying optical markers, criteria are proposed for adjacent regions to be identified and designated. The properties of the regions (such as those defined in Table 1) make it possible to decide which regions are adjacent to others, as presented in Table 3 below. That is, the properties of table 1 can be used to identify and designate adjacent regions as shown below.

(42) TABLE-US-00003 TABLE 3 Subjective Relevant criterion properties Approximation using the properties of the region Adjacent Centre of the Dist(Centre.sub.1,Centre.sub.2) <14 +2.AveSize.sub.1 + 9.8 AveRadius.sub.1 regions must be regions, average Dist(Centre.sub.1,Centre.sub.2) <14 +2.AveSize.sub.2 + 9.8 AveRadius.sub.2 close together sizes and average radii Adjacent regions must be separate from Centre of the regions, average sizes and $\frac{\max \left({\mathrm{AveSize}}_1,{\mathrm{AveSize}}_2\right)}{\mathrm{Dist}\left({\mathrm{Centre}}_1,{\mathrm{Centre}}_2\right)}<1$ one another average radii (without overlap) Geometric properties of adjacent regions must be similar Area of the regions and perimeters $\frac{\max \left({\mathrm{Area}}_1,{\mathrm{Area}}_2\right)}{\min \left({\mathrm{Area}}_1,{\mathrm{Area}}_2\right)}<1.7$   $\frac{\max \left({\mathrm{Perimeter}}_1{\mathrm{Perimeter}}_2\right)}{\mathrm{Min}\left({\mathrm{Perimeter}}_1,{\mathrm{Perimeter}}_2\right)}<1.7$

(43) Post-processing of the contiguity data (i.e. the data and parameters of the contiguous regions which are extracted) allows the creation of contiguity groups. Contiguity groups can be marked preferably with a circle of a random common colour for reasons of visualization and debugging, as shown in FIG. 8. One possible method of such post-processing is described below in step (d).

(44) It should be emphasized that chequerboards are particular cases of adjacent regions that possess specific properties of regularity. New algorithms may take this concept as a basis for identifying other patterns of contiguity regions and to create new customized optical markers.

(45) An example of the post-processing referred to above is the fourth part of the method is step (d) of detecting optical markers, such as targets and chequerboards, by means of a convex hull algorithm (also known as a convex wrapping algorithm) and prediction of position of squares.

(46) In the particular case of identification of chequerboards, the identification may be carried out by counting the number of regions of contiguous colours in a group as well as by checking the regularity of the internal spaces.

(47) In one implementation, step (d) of detecting targets and chequerboards by means of a convex hull algorithm and prediction of position of squares comprises post-processing applied to the group of adjacent regions, which locates the vertices of the chequerboard and inserts a rectangle at the cloud point, comprising the following substeps:

(48) (i) calculating the convex hull of the centres of regions of contiguous colours grouped in the same region;

(49) (ii) for each vertex v.sub.n in the convex hull, calculating the angle between the lines formed by v.sub.n.fwdarw.v.sub.n-1 and v.sub.n.fwdarw.v.sub.n-1;

(50) (iii) ordering the vertices of the convex hull by the calculated angles; and

(51) (iv) keeping the first four vertices with the largest angles therebetween and discarding regions whose opposite angles are higher than a threshold (i.e. very different from one another). In other words, the vertices which have the largest angles between them are assumed to be at the corners of the chequerboard.

(52) Planar chequerboards are preferably used for identifying parts of equipment of sufficiently low curvature. When there is low curvature, a marker glued on its surface would not be subjected to substantial deformations. When a chequerboard has four corner squares which are of different colours to the background colour, the corners of the chequerboard can be detected, and thus its dimensions can be determined. Preferably, all the vertices (i.e the corner squares) of the chequerboards are made up of black squares. A filter (e.g. a high contrast filter) may be used to improve the reliability of detection the corner squares of a chequerboard. This may be particularly useful when the corner squares are not black, or when the colours of the corner squares are not markedly different to the background colour.

(53) The method according to the present disclosure may be applied in the development of systems comprising multiple calibrated cameras. This may allow extraction of normal vector data from the markers of chequerboards, ensuring that the orientation and the positioning of that component are correct.

(54) Once the dimensions of the chequerboard are known (which may be done according to the method described above), it is possible to estimate where the centres of its internal regions are located. An analysis of the regularity of the chequerboards is carried out in groups of regions of contiguous colours, according to the following substeps:

(55) (i) applying a convex hull algorithm using the 2D centres of the contiguous regions to find four outer squares at the edges of a chequerboard;

(56) (ii) calculating and storing the location of fixed squares using the four outer squares as reference;

(57) (iii) if the group of regions being analysed possesses sufficient regions, assign regions to its position on the closest chequerboard having four outer squares;

(58) (iv) rejecting the chequerboard if more than one region is assigned to the same position.

(59) Step (iii) is used to assign each of the regions to a respective estimated position (i.e. fixed square) on the chequerboard. Step (iii) may be omitted if sufficient regions are not present in the group. This may be the case, for example, if chequerboard regions on the marker are obscured.

(60) Step (iv) provides a check that the four squares which were identified as outer squares of a chequerboard were correctly identified. If more than one region is assigned to the same position on the chequerboard in step (iii), this may indicate that the regions which would be mapped to the same position on the chequerboard are not in fact part of a chequerboard. This may in turn allow it to be determined that the four squares which were identified as outer squares are not in fact the four outer squares of a single chequerboard. In this case, the chequerboard is rejected.

(61) The outer squares as referred to above may be identified by determining that they have a colour different to that of the background. They may all have the same colour, and may, for example, be four black squares as described above.

(62) The analysis of regularity described above allows automatic identification of the dimensions of the chequerboard by successive checking of different sizes, as shown in FIGS. 9 and 10. It will be seen from these Figures that multiple targets of different types can be identified in the same image.

(63) The analysis of regularity may also compensate partial occlusions in squares of the chequerboard. In other words, chequerboard may still be identified when some squares are not visible. Groups of adjacent regions may be subject to partial occlusions or their internal regions may not be identified properly owing to the conditions of luminosity. In these cases, comparing the centres of the regions effectively identified with the expected positions of the squares allows recognition of the chequerboard even when various squares are not identified, provided the four black squares of the vertices (i.e. corners) are visible.

(64) The analysis of regularity will accept (i.e. be able to detect) chequerboards even if not all the positions envisaged on the board are occupied by a colour region. FIG. 11 shows examples of occlusion patterns (represented as overlaid squares) in which identification of the board will still take place successfully. This is because the squares at the corners of the chequerboard can be detected, and the overall shape and dimensions can be determined, despite some of the individual square regions of the chequerboard being obscured.

(65) In the case of identification of target-shaped markers that comprise concentric circles (rather than chequerboards), specific properties of regions of contiguous colours are employed for this type of marker, as presented in Table 4 below. It will be understood that the below properties allow ring-shaped regions to be identified, which in turn may allow the central circular region of a target-shaped marker.

(66) TABLE-US-00004 TABLE 4 Subjective Relevant criterion properties Mathematical implementation Adjacent regions must appear In a circular ring there is a $\frac{\mathrm{Perimeter}.Math.\mathrm{AveRadi}\mathrm{us}}{\mathrm{Area}}<3$ as a constant. circular ring (Perimeter × Width)/ Area = 2 In a circular ring typically r > w Properties of circular rings: r, w $\frac{\mathrm{AveSize}}{\mathrm{AveRadius}}<0.5$ Adjacent centres of rings that Distance between centres of $\frac{\mathrm{Dist}\left({\mathrm{Centre}}_1,{\mathrm{Centre}}_2\right)}{(\min \left(\mathrm{Av}{\mathrm{eRadius}}_1,\mathrm{Ave}{\mathrm{Radius}}_2\right)}<1.3$ make up regions concentric and their regions respective must be widths close together Widths of adjacent rings must be Width w of the regions $\frac{.Math.{\mathrm{AveRadius}}_1-{\mathrm{AveRadius}}_2.Math.}{\mathrm{Min}\left({\mathrm{AveRadius}}_1,\mathrm{AveRa}{\mathrm{dius}}_2\right)}<1.5$ substantially equal

(67) After identification of the regions of contiguous colours, it is possible to extract and store data of the region, such as which pixels belong to each region (list of [x,y] coordinates) and, from there, calculate the parameters presented in Table 1. By combining these parameters it is possible to identify targets (concentric regions—rings of the same colour whose centres are close together, as shown in FIG. 12) and adjacent regions (adjacent colour regions without overlap whose properties are substantially equal). Targets are identified by a sequence of characters relating to the sequence of colours thereof, according to the following index: W: white; P: black; R: red; G: green; B: blue; ?: colour unknown (not identified as W, P, R, G or B).

(68) For example, a sequence RWP?G signifies that the colour of the innermost region is red, followed by white, black, unidentified colour and green. FIGS. 12 and 13 show results of the proposed algorithm.

(69) Thus, the method of the present disclosure allows identification of markers, such as chequerboards and targets comprising concentric circles, unequivocally and with sufficient robustness, even in the situation of partial occlusions and/or variations of illumination.

(70) Numerous variations falling within the scope of protection of the present application are permitted. This reinforces the fact that the present invention is not limited to the particular configurations/embodiments described above.

(71) Modifications of the above-described apparatuses and methods, combinations between different variations as practicable, and variations of aspects of the invention that are obvious to those of skill in the art are intended to be within the spirit and scope of the claims.