A method for data compression and representation of textual information in the form of a barcode is proposed in the paper. The main idea of the proposed method is preliminary data compressing along with the use of three colors. Increasing the number of colors used in a barcode symbol allows to encode data with higher density in comparison with two-color barcodes. Thus, the advantage of the proposed method is that it enables either representation of the same amount of input data on a smaller area or a larger amount of data in a barcode symbol of the same size. The matter of a color contrast is also discussed in the paper. Since an information carrier (e.g. goods package) can have an arbitrary background color depending on a use case, a contrast ratio value should be considered while choosing a specific set of colors for barcode elements in each particular use case to make the barcode reading procedure more accurate.
Although barcodes as a technology appeared in the early 1950s, when the first patent for the barcode was received, their popularity has not been reduced even in the contemporary era of smartphones and mass digitalization. On the contrary, barcoding technology use is widening in practical applications because of its evident advantages: data entering accuracy, processing time reduction, scanning simplicity, etc.
Matrix, or two-dimensional, barcodes deserve particular attention. Among multiple benefits any barcode offers, 2D barcodes allow to encode more information than it would be possible using a classical one-dimensional barcode, due to storing data both horizontally and vertically. As a result, there are countless possible applications for matrix barcodes starting from logistics and advertising and finishing with hospitals and financial institutions. New use cases are constantly appearing as the use of portable digital devices, smartphones in particular, is headily expanding.
Along with the emergence of new applications, new problems concerned with barcodes arise. Specifically, one of the subjects of particular interest is increasing amounts of encoded data with preservation of a barcode symbol size. The possible way of resolving this problem is to augment number of colors, which are used in a barcode. Normally, black and white are the colors of any barcode. Adding the third color allows to increase data storing capacity of a barcode symbol in comparison with a black-and-white barcode.
The most well-known among multicolor barcodes is Microsoft’s High Capacity Color Barcode (HCCB) [1]. The main benefit of the HCCB code is that greater compression can be achieved due to the use of 4 or 8 colors, instead of standard blackand-white palette. Moreover, data can occupy smaller space at the barcode symbol because of the triangle shape of HCCB symbols. However, a HCCB code requires Microsoft libraries and software to be installed in order to create or use it, and there are no open source libraries. It limits new applications development to a certain extent.
In [2] the authors propose the High Capacity Colored Two Dimensional (HCC2D) code approach aimed at increasing data amount that can be stored along with preserving the strong reliability and robustness properties of a standard QR code. The authors provided their experimental results, which showed that HCC2D has higher data density than QR code does, although its computational overhead is lower. The main advantage of HCC2D is that this new approach solves most of the problems appearing in detection and alignment of a standard 2D code.
The authors of the paper [3] present a new approach to color barcode decoding which does not require a reference color palette. They also propose algorithms to select subsets of barcode elements which can be decoded with low error probability.
In the patent [4] the authors propose the way of storing data decoded from a barcode as character-based data in an auxiliary field (e.g. a comment field) of an image file.
An approach to the localization and segmentation of a 2D color barcode as well as its evaluation on a diverse collection of images of Microsoft's HCCB is presented and discussed in [5].
Multicolor barcodes have considerable potential that should be developed. There are numerous problems, which can be solved in various ways, and one of such problems is, in particular, compressing data before encoding them, what would result in increasing an overall barcode capacity. In this paper we propose a new method of the tricolor barcoding, which combines the multicolor concept and additional data compression. 2 2.1
A matrix barcode symbol, which is the subject of the proposed research, consists of a set of tricolor barcode patterns. In its turn, a barcode pattern is considered as a graphical representation of elements, which are matrix cells of one of three colors.
Maximum capacity of a barcode symbol is = 3 barcode patterns, as we consider 3 colors and is a number of cells in the barcode pattern. Table 1 presents the relationship between barcode symbol maximal capacity and barcode pattern digital capacity. [6]. Version 1 has 21×21 cells size. The highest version is Version 40, which has 177×177 cells and, therefore, consists of 31329 cells that can encode 3 Kbyte of data. Thus, the approach we propose in this paper allows to store much larger amount of information in one barcode, even though of bigger size.
Let us define a symbolism of the barcode, which is an alphabet Ω of cardinality Ω = 3 . The alphabet Ω consists of all possible -digits tricolor barcode patterns. Barcode patterns can be divided into two groups: informational patterns Ω and auxiliary patterns Ω auxiliary patterns is Ω . Capacity of informational patterns is Ω . Since Ω = Ω ∪ Ω , then Ω + Ω and capacity of = Ω = 3 .
Informational barcode patterns are used to encode input information that shall be represented on a carrier. Auxiliary patterns are aimed to store additional information, such as indicators of switching between encoding modes, START and STOP signs, scanner settings, etc.
An initial input textual data can be considered as a sequence of alphanumeric symbols
= 1 2 … ℎ, where ⊂ ASCII(256) and ℎ is a length of the text. Each symbol can belong to one of the character sets: a set of letters , a set of digits or a set of special symbols .
To be encoded, the input sequence is divided into adjacent subsequences 1 2 … , where = 1 2 … contains elements from either , ter sets. In , the subsequences can follow each other in any order.
In general, alphanumeric symbols belong to extended ASCII. However, practically there is no need to consider 256 ASCII characters, as each use case uses a certain set of characters. Thus, we consider an alphabet , which is a subset of extended ASCII with cardinality
consisted of a restricted number of characters that are used in the certain domain. The alphabet corresponds to a numeric set {0, 1, … , − 1} that represents numbers of the symbols as they are ordered in the alphabet .
Let us now overview the proposed Tricolor Barcoding Method. Generally, each or characsubsequence = 1 2 … of the symbols of the alphabet must be transformed into a barcode pattern. The consecutive set of barcode pattern form then a tricolor matrix barcode symbol that can be located on a physical carrier.
Thus, in the barcode form, the subsequence 1 2 … of alphanumeric characters corresponds to a subsequence of barcode patterns: = 1 2 … , where ⊂ Ω
.
At the first stage of the method, the transformation → , i.e. ( 1 2 … ) → → ( 1 2 … ) has to be fulfilled. Practically, the transformation of adjacent symbols of the alphabet into barcode patterns of the alphabet Ω (i.e. the barcode symbolism) means a transformation of -digits number in a notation into -digits number in a notation Ω
:
As the main purpose of this method is to encode input information with a maximal
compression so that more textual data can be represented in the same barcode symbol,
the following conditions have to be true when fulfilling the transformation (
) { ]log3 [ >
≤ Ω where ]log3 [ is a length of the ternary sequence, which corresponds to an alphais a number of tricolor cells on a carrier numeric sequence = 1 2 … , and that represent the subsequence
.
The conditions (
In order to asses input data compression, we calculate a ratio of a length of the
ternary sequence that corresponds with alphanumeric sequence to a number of cells
on a carrier that represents subsequence in barcoded form:
(
The method proposed in the section above can provide different results depending on the parameter and, consequently, a maximum barcode symbol capacity. In Table 1 the dependency between a number of elements in one barcode pattern and the overall barcode capacity is shown.
The parameter is essential for a resulting barcode and compression of data stored
in this barcode, as it follows from (
for = 8. It is easy to see that there are several local extremums among all
the solutions of the inequality system (
The important remark is that we consider only those values, which are greater than 10. The reason for such restriction is attributable to the fact that an alphabet with cardinality
= 10 is the smallest possible alphabet for numerals from 0 to 9. There is no sense to consider smaller alphabets with cardinality < 10, for example, for parting certain punctuation symbols as a separate alphabet, since they would hardly form a long sequence that could have an impact upon the overall data compression.
For instance, one of the extremums for = 6 is equal to 31 with 7(61)8(31) =
1,267. It has quite good compression coefficient, but an alphabet of cardinality
= 31 is not enough to cover both Latin letters and numbers from 0 to 9. Therefore,
we search for the nearest solution that would meet the size of such alphanumeric
alphabet. Such a solution is = 38. Its compression coefficient is 7(61)8(38) = 1,200,
which is 6% less than the extremum has, however it perfectly matches the
alphanumeric alphabet consisted of 26 Latin letter and 10 numerals. Moreover, its
transformation (
= 31, which is "19" → "10". Therefore, even though = 38 provides us with smaller compression, it benefits comparing to the extremum.
Thus, a set of requirements has to be taken into consideration, such as: an alphabet cardinality, a compression coefficient value, and complexity of → transformation. Practically, these are criteria for the most efficient in particular field alphabets, which poses a multicriteria optimization problem that can be solved with appropriate optimization methods.
The alphabets chosen from among the solutions of (
For example, regarding = 5, we can use the following 4 barcoding modes: the ASCII mode with an alphabet of cardinality = 134, the decimal numbers mode with an alphabet of cardinality = 10, the hexadecimal numbers mode with an alphabet of cardinality = 28, and the textual mode with an alphabet of cardinality = 93. 3
The Tricolor Barcoding Method described in the subsection above is aimed at increasing data density, which is especially important when representing large amount of information. In the general case, these three colors are black, gray, and white (BGW) that makes the method being an extension of a classical matrix black-and-white barcoding approach.
The use of black, gray, and white colors is conditioned by the simplicity of producing such barcode symbols. All it requires is an ordinary black-and-white printer, which also makes a barcode production process cheap and affordable. However, in specific cases the BGW barcodes can be rather hard to be scanned because of inappropriate background colors of a barcode carrier.
The BGW palette is quite a good choice for monochromatic carriers, contrasting to a barcode symbol. In such case, a BGW barcode can easily be read by scanners. The situation is worsening when a carrier background (e.g. packing of goods) either is insufficiently contrasting to BGW palette or consists of several colors or a multicolor pattern. Depending on specific colors and type of environment illumination, scanning might become inaccurate. To overcome the scanning problem, a concept of both contrast range and color models can be used.
In color theory, contrast is the difference in luminance between two adjacent colors or overlaid colors (foreground and background). Luminance is the intensity of light emitted from a surface per unit area in a given direction [7].
In order to raise successfulness of barcode scanning procedure, it is important that colors using in tricolor barcode would be contrast to a background of a carrier object. Thus, background colors must be analyzed in the view of contrast degree before producing a barcode symbol, so that barcode cells would be painted over colors with high contrast ratio.
A color contrast ratio is the ratio of the luminance of the brightest color (which is
white in the extreme case) to the luminance of the darkest color (which is black in the
extreme case) [8]:
= ( 1 + 0.05)/( 2 + 0.05)
(
Let us consider an example for monochromatic background with the color code #69afdb. If we choose barcode colors 1 and 2 with the codes #22047d and #d2ff7f respectively, the contrast ratio for these two colors is 13.28. Then let us take the third color 3 with the code #e04ceb. The contrast between 1 and 3 is 4.63 and the contrast between 2 and 3 is 2.86. Thus, the average contrast between barcode colors is 6.9. The average contrast between the background and the barcode is 4.9, which is sufficient for error-free scanning. 4
The proposed Tricolor Barcoding Method allows us to suggest a technology of tricolor barcoding aimed at encoding input textual data into a tricolor barcode of higher data density and, respectfully, greater information capacity.
The barcoding process can be divided into several phases presented at Figure 2.
The first phase is inputting textual, mainly alphanumeric, data into computer system. A scanner or a smartphone camera can be used for this purpose.
The second phase is setting the barcoding software up in accordance with the
relevant data domain. This process consists of 3 steps: (
At the third phase initial data are being compressed and transformed into corresponding barcode patterns that form an overall barcode symbol at the next stage.
The process of production of the barcode symbol is considered as the fifth phase of the barcoding technology. At the last stage the ready-made barcode symbol is being located on the carrier as a label. Size and location of the label depend on a use case. 5
The barcoding method proposed in this paper allows to encode textual information with increasing data density when representing encoded information as a barcode. The approach combines tricolor barcoding with the auxiliary procedure of data compression. The use of the third color alongside with additional data compression allows to represent more information on the same area of a barcode symbol.
Although the most efficient version of the proposed tricolor barcode is BGW Code, as it uses the black-gray-white palette, which makes a barcode production process to be quite easy and cheap, sometimes these colors are not suitable for accurate scanning from a colored carrier. In this case selection of appropriate colors can increase a contrast ratio for such a carrier and, thus, ensures error-free reading of the barcode.
The tricolor barcoding approach has its potential for further research and development. As barcode labeling is used in multiple use cases, an additional study can be fulfilled in order to determine proper alphabets and, consequently, barcoding modes to make the proposed approach widely used.