A Character Validation Proposal for High-Speed Visual Monitoring of Expiration Codes on Beverage Cans ^†

Abstract

Character recognizers have generally focused on printed text on paper with an emphasis on generality rather than speed. This makes the proposed algorithms not applicable in the context of the very high-speed industrial validation of expiration codes printed on the metal surface of a can. The extreme demands of speed and the adverse effects of lighting and movement, among other things, make it necessary to develop an original and specific strategy. The strategy presented in this paper first selects which of the segmented shapes of a printed can are the best candidates for comparison with expected characters. This is followed by a technique based on the comparison of templates (templates matching), which we call “morphologies”, and are represented as bitmaps to take advantage of the hardware capabilities of general-purpose processors. The use of templates has the advantage of avoiding the construction of a feature vector. In an acquisition test in a real industrial plant, we have been able to successfully treat 438 cans in 44 s, with only one validation error in one character, achieving a compromise between speed and quality that is sufficient for industrial validation in the conditions cited.

1. Introduction

This paper is a continuation of a previous work, “A Character Segmentation Proposal for High-Speed Visual Monitoring of Expiration Codes on Beverage Cans” [1]. In the aforementioned work, an industrial validator of expiration codes printed on aluminum or tin cans, called MONICOD, was presented in all its stages except the last one. This last stage (the character validation) is presented for the first time in this paper.

MONICOD is a machine vision solution [2] for the validation of expiration codes stamped on the aluminum or tinplate bottom of the cans [3,4]. The critical characteristic that defines this system is the very high speed of execution to ensure a validation cadence according to the requirement of a production line. It operates at 200 frames per second in order to validate up to 35 cans per second. (see Figure 1). In this context, validating means verifying whether or not the expiration code is correct. In addition to this requirement, MONICOD has to deal, among other difficulties, with the reflective properties of the metal surfaces of moving cans, which cause glitter that can hide the printed code.

MONICOD carries out the work of code validation from the acquisition of frames in different phases:

• Selection of the best frame and area of interest, obtained in the transit of the can for code validation (see Figure 2). The area of interest is the region at the bottom of the can where the expiration code is printed.
• Enhancement and equalization [5,6] of the area of interest (see Figure 3a).
• Character segmentation.
  • Separation of ink and background (see Figure 3b) and grouping into ink fragments by threshold selection and flooding technique [7,8,9,10].
  • Organization of ink fragments into text lines (see Figure 3c).
  • Grouping of ink fragments into characters (see Figure 3d).

The purpose of these stages is to extract the information from the image that will be effectively validated (see Figure 4). The objective of this work is to present the last stage of MONICOD processing, which is the validation of codes.

2. Acquired Shapes and Expected Code

The previous stages provide us with a set of candidate characters that we generically call “shapes”. These characters are arranged in bands (from top to bottom) and, within a band, from left to right, as shown in Figure 4. A shape may or may not be a valid character, but all valid characters are shapes.

On the other hand, the “expected” code is updated every time a code validation is carried out. The expected code update is mainly based on the current date and time. Based on these data and the type of product, the expiration date is calculated.

The semantics of each character of the expiration code has no interest for the validation itself, but rather for its generation/update. Another factor to consider is the importance of each character to know if a failure in its validation is critical or not.

3. Validation and Recognition

The description of the problem, requirements, constraints, and input data fit perfectly with a validation problem, and so, and for the sake of speed, MONICOD is a validator. This is particularly important in the work presented here.

“Validate” does not necessarily imply “recognize”: by validating, we know beforehand and for sure what is expected to be stamped; otherwise, we would not be able to validate the imprint. This scenario is not the typical one faced by a recognizer, which tries to unravel the printed text without the knowledge of what may be there.

Since the validator has that knowledge, it can fine-tune its procedures, and even stop in the middle of the procedure as soon as there is an indication that what has been obtained does not correspond to what was expected. This is why validation is potentially faster than recognition.

Verification consists of comparing the acquired (segmented) code found in the image with the expected code generated internally by MONICOD (which is always assumed to be correct).

If recognition was used for validation, the procedure would be:

• Recognize the text.
• Compare the recognized text with the expected text.
• Give a decision from the comparison.

MONICOD does not carry out a recognition when validating the character, in the sense that it is not a question of determining which class it corresponds to, but whether or not it corresponds to a particular expected class. In the validation, the procedure would be:

• Compare the extracted shapes with the expected shapes.
• Give a decision from the comparison.

4. Morphologies, Morphological Families, and the Morphological Family Base

4.1. Morphologies

MONICOD bases its validation on the shape of the characters. To that end, it makes an extraction of basic characteristics of the shape. It compares the discretized shape with discretized character shapes that are entirely stored and retrieved in the character Morphological Family Base (MFB). MONICOD refers to these shapes contained in the MFB of characters as ‘morphologies’.

The morphology is the minimum unit of the MFB of characters. It is actually a binary template. Its structure is simple: it consists of a discrete and uncompressed representation of zeros and ones of dimension m x n. By convention, ‘zero’ (0) represents non-ink, and ‘one’ (1) represents ink. The relative positions of zeros and ones (ink and non-ink) maintain the same relationship as in the shape they represent. Thus, morphology is an explicit representation of binarized real-size shapes. It can be seen as a map of bits or cells being susceptible to their treatment with bit operations (see Figure 5). This accelerates the computation enormously.

Morphologies offer the following advantages:

• If the shapes are legible and recognizable, the associated morphologies will retain those qualities.
• Morphologies are extracted directly from segmentation without any analysis involving new operations such as the creation of a vector of characteristics [11,12,13,14,15,16,17,18,19].
• Industrial printing standardizes. It is expected that printed characters will be similar between cans and can be associated with the same morphology.

4.2. Distance between Two Morphologies

The most important action that can be done on a morphology is to compare it directly with another morphology and evaluate how much distance or similarity exists between them. It is the approximation known as template comparison or template matching.

It is necessary for MONICOD to carry out this operation as quickly as possible. For example, the Euclidean distance would be computationally too expensive. MONICOD defines its own distance between morphologies from the simple count (counting ones (or zeros) is a bit-level operation, identical to the scalar product between templates) of matches and non-matches in ink and background between the cells of two morphologies A and B. The values of the counters allow a simple evaluation of similarity.

For two morphologies to be comparable, they must have the same height and width (m and n). Four independent counters are used. Comparing A and B:

• Ink Coincidences (IC): Counts ink coincidences between A and B.
• No-Ink Coincidences (NIC): Count background coincidences between A and B.
• Absent Ink (AI): Counts non-coincidences due to absent ink in B that is present in A.
• Unexpected Ink (UI): Counts non-coincidences due to ink present in B that is not present in A.

If we exchange operands A and B to B and A, the magnitudes of the AI and UI counters are exchanged, while the NIC and IC counters remain the same. It is always fulfilled that:

$$\mathrm{N}\mathrm{I}\mathrm{C}+\mathrm{A}\mathrm{I}+\mathrm{U}\mathrm{I}+\mathrm{I}\mathrm{C}=\mathrm{m} \mathrm{x} \mathrm{n}$$

(1)

IC + AI corresponds to the amount of ink in A, and NIC + UI corresponds to the amount of no-ink or background in A.

The comparison methodology comprises two sub-phases. The first is limited to carry out a count of similarities and differences, cell by cell, between the stored template and the acquired template. The position within the template is not considered. The second computes a function that is parameterized by the count values of the first phase, which gives us a measure of similarity:

$$1-M\left(A,B\right) with M\left(A,B\right)=\frac{1}{2}\left(\frac{\left|A·B\right|}{\left|A\right|}+\frac{\left|\overline{A}·\overline{B}\right|}{\left|\overline{A}\right|}\right),$$

(2)

where A and B correspond to the expected and extracted template, respectively. $\left|X\right|$ and $\left|\stackrel{-}{X}\right|$are the number of ones and zeros in vector $X$, respectively. Thus, $\left|A·B\right|$ is the number of ones of the scalar product of vectors A and B. The denominators in Equation (2) are fixed and can be pre-calculated, which accelerates the calculation of the distance expression.

4.3. Morphological Families

In an ideal situation, a unique way to identify a character would be enough because it would be associated with a single character in an unambiguous way. It would be sufficient to compare the acquired shape with an artificially generated shape decided by the automatic code generator and determine if there is a match or not. This approach seems to make sense if we take into account that we are always printing with the same machine on surfaces of the same type. However, in practice, it is found that the acquired shapes do not present the expected uniformity (see Figure 6). There are several reasons for this: the printer does not have the same effectiveness in each print, the acquisition has differences due to changes in lighting, etc.

The morphological family is a logical grouping of morphologies that responds to the fact that each character is associated with a set or collection of equal valid shapes (see Figure 7).

The properties of a morphological family are:

• No repetition: There are never two identical morphologies within a morphological family.
• Relationship: All the morphologies have more similarity with any of the morphologies of its own family than with any other morphology belonging to another family (see Section 4.2).

4.4. Morphological Family Base (MFB)

The MFB contains the characters learned by MONICOD and manages recoveries, additions, and deletions (see Figure 8). The Morphological Family Base is maintained, consulted, and modified in memory: this way, we do not access the disk to rescue or update data. It can also be restarted to start a new learning from scratch.

The Morphological Family Base makes it possible to learn and validate characters, and if necessary, also recognition; however, MONICOD, as has been said, is not a recognition system.

The MFB operates with two key concepts: morphologies and morphological families.

The fundamental operations on the MFB that are possible to carry out both in validation time and learning time are the addition of a new morphology, suppression of a morphology, and sequential query of morphologies contained in a given morphological family.

5. Code Validation

There are three stages in the validation phase. The first stage is reduced to choosing which expected character we will compare with what acquired character: that is to say, to select the comparison pair. The second stage consists of the comparison itself: deciding whether the acquired character and the expected character are sufficiently similar or not. The third stage makes a global analysis of the code comparison and judges whether, with the positively validated characters, the code can be considered good or not.

5.1. Selection of Comparison Pair

The pair selection policy requires that:

• The searched characters are in the can.
• The next expected character is not examined until the current one has been found.
• If the acquired character does not correspond to the expected one, it will be assumed that the acquired character is noise and the system will advance to the next acquired character (but the expected character remains fixed).

The comparison is carried out character by character. This comparison maintains the Western reading order of the characters in the code to be validated: from left to right, from top to bottom.

Proceeding in this way offers several advantages:

• When reading from left to right, we have useful information to refine clusters of ink fragments, and we always leave complete characters behind. So, if the current grouping does not correspond to a character, the only alternative is to consider possible mergers with the grouping to the right.
• In the expiration codes, it seems that the importance of the characters decreases from left to right and from top to bottom; that is, within a line, a character is more likely to have equal or greater importance than the immediate character to its right. If the code is going to be negatively validated, it is better to know it as soon as possible, and giving priority to the important characters makes us advance in that purpose. This rule is fulfilled in all the studied codes.
• It is more likely that a line has greater or equal importance than that which is immediately lower. In all the studied codes (two lines), this rule is met.

The procedure follows these steps:

• The first line of the expected code not yet processed is selected in the order from top to bottom. If there are no expected lines to be processed, we go to the stage described in Section 5.3.
• We choose, within the bands of acquired shapes, the one that may contain the expected line selected in step 1. It will be done from top to bottom starting from the next band after the last band successfully verified. The rule to be fulfilled is that the selected band has the same or greater number of shapes than the number of characters of the expected code line (see Figure 9).
• Within the selected expected line, we select the first expected character not yet verified from the expected code following the order from left to right. If all the characters have already been validated, then the expected line has already been completely processed, and therefore, we return to step 1.
• Within the band of acquired shapes, we select the first acquired shape not yet treated. If there are no acquired shapes, it is necessary to select another band, so all the expected characters verified in this line become unverified, and we return to step 2.
• Verification is made between the morphological family of the expected character and the acquired shape (see Section 5.2).
  • The verification is negative: The current acquired shape is merged with the immediately following one and the verification between the morphological family of the expected character and the new shape, as the result of the described merging process, is repeated (see Figure 10 and Section 5.2),
    • Verification is positive: We consider the current and the next acquired shape as treated. The expected character is marked as verified. Go back to step 3.
    • The verification is negative. We consider the current acquired shape as noise. We mark it as treated (see Figure 11). Go back to step 4.
  • The verification is positive: The acquired shape is marked as treated. The expected character is marked as verified (see Figure 12). Go back to step 3.

5.2. Matching

This stage comprises three well-differentiated phases:

• The morphological family corresponding to the expected character is recovered from the MFB. The family must exist, and there must be morphologies within that family. Otherwise, we will face a critical failure in the validation, which should be notified to the operator immediately.
• The morphologies of the morphological family are recovered one by one. Each morphology is compared with the acquired shape. This comparison includes two tests:
  • Comparison of the amount of ink present. It is a previous filtering. The ink difference between the morphology and the acquired character is compared. A difference above a permissible maximum ink difference threshold makes it unnecessary to carry out a template matching. If it passes the ink covered area test, the second test is applied. Otherwise, it is stated that they are different. The similarity value in that case is 0.
  • Templates matching. A comparison of templates is made using the distance between morphologies described in Section 4.2 to evaluate the similarity between the morphology and the acquired character. The similarity value (distance) obtained is stored.
• Finally, the maximum similarity value obtained in the previous phase is chosen when facing all the morphologies of the morphological family with the acquired character. If it exceeds a certain threshold, the verification has been positive. Otherwise, it is negative. This result feeds the code validation resolution.

5.3. Validation Resolution

In this phase, it is determined whether the can is valid (positive validation) or not (negative validation). To make this decision, the system will work with:

• Which expected characters have been verified positively (in position and line) in the acquired can image. The procedure described in the previous sections provides this information.
• Which characters are important. The user has previously provided the system with this information through a configuration file.

The policy followed is: If all important characters are present in the can in the expected line/order, the expiration date printout is valid. Otherwise, the expiration date printout is not considered valid. MONICOD just updates a statistics of total, positive, and negative validated cans and launches a warning message in the case of a negative validation. The processing of this warning message goes beyond MONICOD and becomes the responsibility of the operator. If the validation is positive, it is expected that no action will be taken. On the other hand, if the validation is negative, different actions may be triggered: removing the affected can manually or mechanically, stopping the line to solve a chronic problem (it may be necessary, for example, to recalibrate the system...), ignoring the negative validation, etc.

6. Results

The expiration code validation algorithm described is integrated in MONICOD, which comprises several phases and stages. A test of the system has been carried out consisting of treating 8884 frames containing 465 cans, all of them correctly labeled with the expiration code. The total duration of the test was 44.42 s. MONICOD was able to process 200 images per second without requiring specific hardware.

The quality of the results obtained is detailed in

Table 1. Quality evaluation of the test performed.

Total Validations	Successful Validations	Failures
465	438	27

, while

Table 2. List of causes of test failures.

	Number of Failures	Percentage
Failure in the selection of the best can	13	50.0%
Band division failure	11	42.3%
Grouping failure	1	3.8%
Failure in character validation	1	3.8%

shows the causes of the failures. In the end, in the whole experiment there was only one validation failure with one character: It was marked as incorrect when it was actually correct.

As mentioned in the Section 1 Introduction, a frame does not go through all the phases. In fact, the frames that reach the validation phase are only those that show a perfectly centered can. As shown in Figure 13, the validation algorithm consumed less time than the other MONICOD phases during this test.

7. Conclusions and Future Works

The final phase of the current implementation of MONICOD has been presented: A character validator based on a template-matching scheme.

Considering the overall results, the algorithm broadly meets the required speed specifications. This has been possible due to the application of several strategies. First, there is the use of a template matching method. The template is a direct and immediate result of the segmentation, which keeps all the information of the shape, and makes it possible to omit a feature-extraction process. Second, there is the application of bit operations to perform template matching. Bit operations are supported at a low level by low-cost general-purpose processors, forming an inherent part of their architecture, so we guarantee great compatibility as well as great speed. Third, comparisons filtering is applied: It is only compared when it has been noticed that the amount of ink (that is achieved applying a bit-level operation consisting of counting 1 s) between the morphologies to be compared is approximately similar. If this is not the case, the similarity is estimated to be zero.

An important weakness of the algorithm is that it does not offer a good generalization. The construction of a good base of morphologies is key to alleviate this problem. In future works, we will study the learning mechanisms that allow the aforementioned construction to be automated, as well as a comparison with other techniques such as k-Nearest Neighbor KNN [20], neural networks [21], and support vector machines [22,23].