WO2010031110A1

WO2010031110A1 - Data storage device and encoding/decoding methods

Info

Publication number: WO2010031110A1
Application number: PCT/AU2009/001205
Authority: WO
Inventors: Keng Tiong Tan; Douglas Kian Wu Chai; Hiroko Kato; Siong Khai Ong
Original assignee: Edith Cowan University
Priority date: 2008-09-16
Filing date: 2009-09-11
Publication date: 2010-03-25

Abstract

This invention relates to a data storage device, and methods of encoding and decoding a data storage device. More particularly, the invention relates to the field of encoding and decoding of machine-based data using high capacity multi-coloured composite bar codes or other symbol sets in a colour space. It has utility in, for example, bar code applications using mobile devices to provide a colour two-dimensional bar code for true ubiquitous computing.

Description

Data storage device and encoding/decoding methods

Field of the Invention

[0001] This invention relates to a data storage device, and methods of encoding and decoding a data storage device. More particularly, the invention relates to the field of encoding and decoding of machine-based data using high capacity multi-coloured composite bar codes or other symbol sets in a colour space. It has utility in, for example, bar code applications using mobile devices to provide a colour two- dimensional bar code for true ubiquitous computing.

Background Art

[0002] The following discussion of the background art is intended to facilitate an understanding of the present invention only. It should be appreciated that the discussion is not an acknowledgement or admission that any of the material referred to was part of the common general knowledge of the person skilled in the art in any jurisdiction as at the priority date of the invention.

[0003] With camera phones having become near-ubiquitous, automatic identification and data capture technologies can work as an interface to bridge the physical and digital world. Examples of such technologies are bar code, Radio Frequency Identification (RFID) and Near Field Communication (NFC). Most are used as either a visible or an invisible tag to connect these two worlds. As the notion of ubiquitous computing has permeated, these technologies and their applications have been developed in order to create a ubiquitous computing environment.

[0004] Ubiquitous computing refers to where people use computers in their natural environment without realising the computers' presence due to the naturalness of their existence. It is a world where human-to-human interaction has higher priority over human-to-computer interaction. In such a world, human beings are not dependent on computers. Rather, computers exist to work for humans, making their lives convenient, while the machines invisibly, synchronising themselves in the background. [0005] Of the automatic identification and data capture technologies, bar codes, especially two dimensional (2D) bar codes, have attracted the attention of many researchers and companies due to the potential for inexpensive operation.

[0006] Bar codes have been used for mobile applications to deliver a multitude of different mobile services over mobile phones and related mobile devices, such as Personal Digital Assistants (PDAs) and other mobile computing devices. Such applications range from providing Uniform Resource Locator (URL) information to link a mobile device to the Internet, through to using the. bar code as a form of e-ticket for airlines or event admissions. In other industries, bar codes are even used as security tokens and containers for secured biometric data for security applications. The variety of bar code applications keeps on growing by the day, especially with its pervasive and ubiquitous use with mobile devices. Hence, there is an ever growing demand for higher capacity bar codes, suited for robust application on mobile devices. Two approaches to higher capacity bar codes are: (i) using a coloured symbol set and (ii) increasing the size of the bar code. There are known limitations for either approaches in the current prior art, especially as regards identification thereof using mobile devices with compromised, low resolution cameras.

[0007] Despite the introduction and promotion of numerous 2D bar codes and their applications, this technology has received mixed success. This may be the result of the immaturity of the technology as a ubiquitous computing tool, which affects its usability and robustness. In general, one dimensional (1 D) bar codes work as indexes to backend databases, while 2D bar codes can operate as robust data files by themselves. 2D bar codes can be roughly classified into two groups: (i) index 2D bar code; and (ii) database 2D bar code. The index 2D bar code works in the same way as 1 D bar codes, as both require continuous network connectivity to function. On the other hand, the database 2D bar code, initially invented to improve data capacity for industrial use, can encode data into a bar code symbol, thus allowing access to data regardless of network connectivity. [0008] The index 2D bar codes focus on robust and reliable reading, taking into account the reading limitations of the respective readers. Thus, most of these bar code devices can operate robustly even when used with resource-limited camera phones. However, their severely limited data capacity constrains their possible applications and their primary task at present is merely linking camera phones to the designated Web pages. Additional tasks may then be performed based on the Web-link established. However, few useful tasks can be done without network connectivity and back-end databases with current bar codes of which the inventors are aware. However, the database 2D bar codes with their greater data capacity can provide a wider variety of applications, regardless of network connectivity.

[0009] As an example of this, a user can encode his personal details into a database 2D bar code symbol and print it on his or her ID card. Using a camera phone with bar code reading software, the symbol can be read and the personal details can then be saved in the phone address book without manual input. No network connectivity or additional cost is required. The maximum data capacity of database 2D bar codes has been improving over the recent years, resulting in the introduction of newer applications. Currently, certain of these applications (e.g. Trillcode) have progressed to the stage of being able to encode sounds, which can then be played on the camera phones.

[0010] Often the greater data capacity can only be achieved at the cost of reading robustness of the bar code symbols. When improving data capacity within a given space, the number of data cells must be increased, resulting in a reduction in the size of the bar code "cells". Dedicated scanners may cope well with this, but when camera phones are used as the image processing device, the bar code cell size is critical due to camera phones' inferior image quality (e.g. low resolution, lack of auto focus function and Floating Point Unit). Once the size of each data cell falls below the point where two adjacent cells can be clearly distinguished by the reading software, the bar code symbol cannot be successfully decoded. In other words, the data capacity can be increased only up to the point where each data cell is still legible. This severely limits the maximum data capacity of the existing database 2D bar codes. [0011] There has been an increase in the applications that require massive data including images and/or sounds. Inexpensive mass data storages have become prevalent and this has lead users to take storage capacity for granted, in terms of both availability and cost. At present, however, there are no 2D bar codes for mobile applications that can encode a whole tune or a complete image such as an entire photo within a reasonable given space (e.g., 5 cm x 5 cm). No database 2D bar codes have achieved this yet, let alone index 2D bar codes. Considering the demand for massive data storages, there is a need for a 2D bar code with improved data capacity. This in turn will assist in providing a wider variety of applications. There is also a need for methods of improving the robustness of bar code to ensure sufficient fidelity of the information presented on the bar code.

[0012] At present, three colour 2D bar codes exist of which the inventors are aware: ColorCode, High Capacity Colour Bar code (HCCB) and Paper Memory (PM) Code. While ColorCode works as a so-called index 2D bar code, the HCCB and PM Code are classified as database 2D bar codes.

[0013] In 2000, Han et al. developed ColorCode, a colour 2D bar code designed for use with inexpensive cameras such as web cameras and mobile phones. ColorCode has overcome certain problems in image fidelity by using reference cells that provide the standard colour for correctly distinguishing each reproduced cell. The value of each cell colour in the data area is determined relative to the value of the standard colour in the reference cells. Because the relative difference between the cell colour and the standard colour is consistent, a bar code reader can correctly retrieve the data even when the colour values have changed from their original values via the devices used and the media upon which the colour images are printed.

[0014] Despite its potential to improve data capacity, ColorCode uses colour elements merely for eye-catching symbol design. On the other hand, both the HCCB and PM Code systems have been developed to improve the data capacity within a given symbol space, by encoding colour symbols. The HCCB system can achieve at least three times the density of industry standard 2D bar codes such as PDF417 or Data Matrix within the given space by encoding colour symbols into a triangular cell set, which takes up less space than square cells.

[0015] PM Code uses a unique layered structure to improve data capacity within a given available symbol space significantly. A PM Code symbol is made up of a plurality of layers with each consisting of a 2D matrix bar code. The cells in particular colour combinations each comprise a layer. The colour of each cell in the surface layer may present the colour of a single code layer or the resultant colour from adding the plurality of code layers. When the resultant colour is identical to the colour used in one of the layers, the resultant colour will be converted to a designated colour according to the PM Code colour conversion algorithm that involves two colour spaces: the RGB (i.e., Red, Green and Blue) colour space and the HSB (hue, saturation, brightness) colour space.

[0016] The PM Code colour conversion algorithm, together with its index information code included in the surface layer, enables the decoding software to detect the presence or absence of colour cells in each layer, which in turn enables the successful reading of each code layer, resulting in successful decoding of the entire PM Code.

[0017] Both HCCB and PM Code have been proposed as so-called maximal 2D bar codes in terms of data capacity for a given symbol space. However, when used with resource-limited camera phones, these colour 2D bar codes allow only a limited set of colours, such as 4 (or a maximum of 8 colours), because neither of these systems were specifically designed for mobile applications. This prevents them from being used as a robust ubiquitous computing tool. In other words, the number of colours for encoding data needs to be increased in order to achieve the data capacity required for a ubiquitous computing tool. Furthermore, all the colours must be robustly identified and retrieved even when digital image capturing means as simple as camera phones are used as image processing devices.

[0018] Hence, although colour-based bar codes have been proposed in the prior art, it is often that these bar codes can only use a limited set of colours, such as 4 colours, for mobile devices application. This is the limitation found in US Patent Application No: 20050285761 , assigned to Microsoft Corporation. While this application claims a bar code with a multitude of colours, its embodiment for mobile devices can only support up to 4 colours.

[0019] Some of these colour bar codes only encode a limited capacity of data content per square centimetre of symbol surface on output device, which is often, but not limited to, a hard copy produced by a colour ink jet or colour laser printer. This is the limitation found in US Patent No: 7,020,327, assigned to ColorZip Media, Inc. (Seoul, KR). While this Application is targeted for mobile devices, it also uses a very limited number of colours (less than 8) and its data cell size is rather large relative to the total bar code surface area, hence, it can only encode a limited capacity of data content per square centimetre of symbol surface on output device.

[0020] Another problem associated with colour bar codes is that information pertaining to the bar code, such as bar code version and error correction level, is often included in the symbol itself, thus, reducing the data capacity of the symbol. This limitation is found in US Patent No: 6,267,296, assigned to Denso Corporation (Kariya, JP). While this Application is for a black and white bar code, it has been adopted for use in mobile applications on mobile devices. This prior art contains the bar code information, such as bar code version and timing information within the finder pattern of the bar code, which is part of the data area of the bar code symbol. This reduces the data capacity of the symbol.

[0021] On the other hand, there is a physical limit to the physical size possible for a bar code, especially one suited for mobile applications on mobile devices. The physical size of the bar code is limited by both the capacity of the device to capture the entirety of the bar code symbol, with the required fidelity, and the surface available for presenting the bar code on the output device, as either a hard or soft copy.

[0022] Another problem typically associated with colour bar codes is that higher capacity colour based bar codes need to be scanned using scanning devices with reading fidelity often not found on mobile devices, such as camera mobile phones. Further, poor image capture and compression algorithms, such as JPEG image compression format, are often used on resources limited mobile devices, such as camera mobile phone, which further deteriorates the fidelity of the captured symbol image by introducing blurring artefacts at the edges between information cells within the bar code. This limits the minimum size of each colour cell within the bar code symbol, thus, limiting the total data capacity of the symbol for a given physical size.

[0023] In summary, the use of colour based bar code and other symbolic encoding, in colour space, technologies using mobile devices such as camera mobile phones has been limited by the physical size of the actual symbol in relation to the information encoded within, and also by the image capturing mechanism on such mobile devices to effectively discriminate between a greater multitude of colours, especially under varied lighting conditions by an inexperienced, lay operator. Another limiting factor has been the colour fidelity of the hard copy output devices, such as colour printers, in reproducing the true colours of such colour based bar code or symbol sets in a colour space.

[0024] The present invention seeks to address or at least ameliorate one or more the problems associated with prior art devices.

Disclosure of the Invention

[0025] The inventors have revealed that by developing data storage devices comprising symbols that are at a distinguishable distance apart across more than one colour space they can maximize the data capacity of the device and produce data storage devices that operate across a platform of technologies including with resource- limited devices. In particular, the inventors have developed high capacity multi-coloured composite data storage devices (such as bar codes or other symbol sets) that operate in more than one colour space. [0026] According to a first aspect the invention resides in a data storage device comprising:

(a) a data representation region; and

(b) an information storage device detection means,

wherein the data representation region is: (i) marked by the information storage detection means, and separated there from; and (ii) composed of symbols that are at a distinguishable distance apart across more than one colour space.

[0027] Preferably, the invention resides around the selection of colour symbols that are at a distinguishable distance apart across more than one colour space. The symbols used in the data field are preferably selected to be symbols that are at a maximal distance apart across more than one colour space.

[0028] Previously, colour symbols have been selected as maximum distances apart in only one colour space, which is usually Red Green Blue (RGB) for colour bar codes. This limits the number of colour symbols that can be used to robustly encode and decode data in a colour bar code on a mobile device, which often captures and stores images in a compressed format. This is because colour symbols that are maximum distances apart in the printed and displayed format (usually in the CMYK and RGB coloured space, respectively) may not always be at maximum distances apart in the captured and stored format (often in the YCbCr format for Joint Picture Encoding Group (JPEG) format on mobile devices). Thus, it is known in the prior art that for robust encoding and decoding of data in colour bar codes for mobile devices, only a limited colour symbols can be used, thus limiting the maximum data density possible for a given bar code size.

[0029] The present invention seeks to address the limitation of prior art devices by providing a data storage device that employs colour symbols that are at distinguishable distances apart (preferably maximal distances) in the printed and displayed format and in the captured and stored format (i.e. more than one colour space). Such devices have particular application with resource-limited mobile devices. That is, the device can robustly and ubiquitously operate with resource-limited mobile devices, by maximizing the data capacity for a given space and has improved tolerance to physical/mechanical damage. When the data coding device is used in this application it is termed Mobile Multi-Colour Composite (MMCC).

[0030] As used herein, the term "colour space" means the theoretical construct that defines the range of colours that e.g. (a) can be reproduced by a given output device or (b) be seen by human eye under certain conditions.

[0031] As used herein, the term "colour" includes black and white. The term "CMYK" refers to the four colour inks used in most colour printing: Cyan, Magenta, Yellow, and Key (black). The term "YCbCr" refers a family of colour spaces used as a part of the colour image pipeline in video and digital photography systems, where Y is the luminance component and Cb and Cr are the blue-difference and red-difference colour components. The term "Gray code" means a binary numeral system where two successive values differ in only one bit.

[0032] The data representation region is preferably a matrix of cells existent as optically-readable or machine-readable symbols. The optically-readable or machine- readable symbols are desirably in the form of a plane including reference colours KRWC. The reference colours may be placed at, or proximal, the corners of the symbol, either individually or in combination.

[0033] The data representation region may be in the form of 20 x 20, 30 x 30, or 40 x 40 cells, or any suitable variation or intermediates thereof. Typically, the data representation region is in the form of a 30 x 30 data cell.

[0034] The data representation region further preferably include between about 2 and 128 reference points on the plane. More preferably there are between 2 and 60, between 4 and 50 between 6 and 30 or between 8 and 20 reference points on the plane. Desirably, there are 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 , 12, 13, 14, 15, 16, 17, 18, 19, 20 reference points on the plane. For example, 9 reference points are present on the plane. Preferably, the values of the reference points equal the values of the colour symbols used to encode the data. The reference points may be "0,0,0," "0.5,0,0," "1 ,0,0," "0,0.5,0.5," "0.5,0.5,0.5," "1 ,0.5,0.5," "0,1 ,1 ," "0.5,1 ,1" and "1 ,1 ,1 ," in the normalized RGB colour range [0, 1], each reference point representing, respectively, black, brown, red, dark green, grey, tan, cyan, sky blue and white. In addition to these 9 colours, yellow "1 ,1 ,0" may be selected as a colour symbol, resulting in 10 colour symbols available for encoding data.

[0035] According to one embodiment of the present invention, machine based data are encoded in Red Green Blue (RGB) colour space using RGB colours which are furthest apart within both the RGB and the YCbCr colour spaces, where the latter, is the colour space used by the JPEG format, which is the image compression method employed in mobile camera phones. This reduces the fidelity deterioration of the captured symbol image due to JPEG compression, thus allowing more colours to be used and an increase in data capacity of the resultant colour bar code.

[0036] The data representation region and the information storage device detection means are desirably separated by a separator. The separator may be a coloured separator. The coloured separator may be in the form of a border of between 1 and 5 pixels in width, preferably between 1 and 3 pixels in width, most preferably a single pixel border. The border may be white and may be continuous.

[0037] According to the present invention, information of the bar code version and error correction level is encoded in the information storage device detection means or finder pattern using another bar code symbol. The finder pattern is the pattern within the bar code that helps the decoding device to locate the position of the bar code within the captured image. This allows more data to be encoded within the bar code symbol of the current invention. Reference to the printed colour used in the invention is included within the finder pattern. This allows for the reader or optical device to calibrate its colour reading in accordance with the actual captured colour from an output device, which is often, but not limited to, a hard copy produced by a colour ink jet or colour laser printer.

[0038] According to the invention the information storage device detection means preferably includes or forms a finder pattern for the data representation region. The finder may be a coloured pattern or it may be black. In a preferred form of the invention, the finder pattern comprises header information. The header information may be substantially square in shape, although other polygonal shapes are within the scope of the present invention. Desirably the finder pattern comprises a black bounding border. In a highly preferred form of the invention the header information is presented, in the form of a 1 D bar code or 2D bar code. The header information bar code may be a black and white bar code.

[0039] The finder pattern may also include a reference area, or cells for colour calibration within itself. As such, the reference area or cells may act as references for colour calibration within the data storage device. The reference cells may have a regularly repeating polygonal shape, such as a triangle or a square. When the cells are triangular in shape, each triangle may have a base approximately 1.5 times as long as the operative height thereof.

[0040] The data storage device may also include a sample pixel proximal to, or at, the centre of the device, thereby to define a centroid reference cell.

[0041] According to a second aspect of the present invention, there is provided a method of encoding a data storage device, the method comprising the steps of:

a) compressing raw data to be encoded;

b) error protecting the compressed data;

c) interleaving the error protected data; and

d) mapping the interleaved data to form the data storage device wherein the device comprises data cells represented as symbols that are selected so that the symbols are at a distinguishable distance apart across more than one colour space.

[0042] In a highly preferred form of the invention the colour of each data cell is determined by the following steps:

a) computing of the distance between each reference point and its neighbouring reference points;

b) determining the minimum distance between each reference point and its neighbouring colours;

c) creating a zone having a boundary whose radius is equivalent to a first predefined percentage minimum distance from each reference point, with the percentage increasing until the radiuses reaches a second pre-defined percentage of the minimum distance; and

d) performing the colour determination process, producing a colour cluster of each colour.

[0043] The first pre-defined percentage minimum distance from each reference point may be calculated as a circular boundary having a radius equivalent to between 10% and 40% of the minimum distance from each reference point, in certain embodiments between 20% and 30%, preferably about 25% of the minimum distance from each reference point.

[0044] The second pre-defined percentage of the minimum distance may be between 20% and 70%, in certain embodiments between 40% and 60%, preferably about 50% of the minimum distance from each reference point.

[0045] The percentage of the minimum distance from each reference point may be increased incrementally or step wise in steps of 0.1% and 20%, preferably between 1% and 10%, most preferably about 5%, until the radius reaches the second pre-defined minimum distance. [0046] This process will continue and be repeated until either (i) the number of assigned colours to each reference colour reaches between 1% and 5%, preferably between 2% and 4%, most preferably about 3% of all the colour symbols; or (ii) the radius of each circle reaches the second pre-defined minimum distance.

[0047] The method may include the further steps of calculating the average of the colour values of each colour cluster, which results in a new reference point for the corresponding colour; and validating the new reference point.

[0048] The method may include the step of comparing the minimum distance previously obtained and the distance between the new reference point and its closest neighbouring reference point and, if the former is shorter, regarding the new reference point to be valid, or, if the former is not shorter, regarding the new reference point to be invalid. When the new reference point is invalid, the previous reference point is used for the subsequent colour determination process.

[0049] Once the new reference points are acquired, the entire colour determination process may be repeated until all the reference points for respective colour used and the colour of each colour symbol is determined.

[0050] Mapping between colour symbols and the corresponding data values may be accomplished using the code conversion table provided in Table 1.

[0051] According to a third aspect of the present invention, there is provided a method of decoding a data storage device, the method comprising the steps of:

a) finding a pattern within the data storage device;

b) decoding data within a data representation means of the data storage device;

c) de-interleaving the decoded data;

d) error correcting the de-interleaved data;

e) decompressing the error corrected data; and f) retrieving the encoded data.

[0052] The step of retrieving the encoded data may include de-compressing the data, prior to reconstructing the data.

Bar Codes

[0053] According to a fourth aspect of the present invention, there is provided a bar code, the bar code comprising:

a) a data representation region that includes a matrix of bar code cells arranged in an optically readable form to carry information; and

b) an information storage device detection means that includes a pattern that operates as a finder pattern for bar code detection and contains header information and reference cells;

wherein (a) the matrix of bar code cells define a data field, (b) the cells are present as symbols wherein the symbols used in the data representation region are selected to be symbols that are at a distinguishable distance apart across more than one colour space; and (c) the data field is marked by the finder pattern, separated by a separator.

[0054] The symbols used in the data field are preferably selected to be maximal distance apart across more than one colour space.

[0055] Bar codes produced according to the invention have the advantage that they can robustly and ubiquitously operate with resource-limited mobile devices. They store data at high density by maximizing the data capacity for a given space. The term "high density" when referring to a bar code, means a bar code having a data capacity to encode more than 13 alphanumeric digits. Furthermore they have improved tolerance to physical/mechanical damage.

[0056] As used herein, the term "bar code cell" means the component of a bar code which represents one unit of data content, while the term "bar code cell size" means is the physical size of the bar code cell. [0057] The finder pattern may be coloured. Desirably the coloured pattern is a black bounding border. The reference cells may also be colour cells. Furthermore the separator may be coloured. The separator may be between one and five pixels in width, between 1 and 3 pixels in width, or about 1 pixel in width. In one embodiment, the coloured separator is a single pixel border, and is white.

[0058] The header information may be included in a header information bar code. Preferably the header information is a one dimensional bar code, but may be a two, or more, dimensional bar code. Preferably the header information is a index 2D bar code. As used herein, the term "index 2D bar code" means the variant of bar codes where their contents are links or indexes to off code information stores.

[0059] The header information may also encoded information pertaining to at least one of the encoding, decoding, error protection, symbol dimension, security, bar code version, error correction level, or other applicable header information of the bar code.

[0060] The bar code may be encoded and decoded using a range of devices including mobile devices. In one embodiment, the encoding or the decoding of the bar code may be on a mobile device, while the other process may occur on a non-mobile device, or vice versa.

[0061] The bar code may be produced or rendered as a printed hard copy or it may be produced as a digital soft copy. Preferably, the bar code is produced as a digital display.

[0062] According to a fifth embodiment of the present invention, there is provided a method of encoding a bar code, the method comprising the steps of:

a) compressing raw data to be encoded using a compression algorithm suited to the data type;

b) error protecting the compressed data using an error correction encoding scheme that is suitable for the output medium of a bar code encoding device; c) interleaving the error protected data using an interleaving operation;

d) mapping the interleaved data to form the data storage device wherein the device comprises data cells represented as symbols that are selected so that the symbols are at a distinguishable distance apart across more than one colour space;

e) creating a header information bar code; and

f) producing a bar code.

[0063] The interleaving operation may be a random operation or a pseudo-random operation.

[0064] The encoding method may be implemented as software stored on a computer readable medium containing instructions for execution by a processor, and the instructions, when executed, perform the encoding process.

[0065] The encoding method may be implemented as hardware, with digital logics, which, when executed, perform the encoding process.

[0066] According to a sixth embodiment of the present invention, there is provided a method of decoding a bar code having interleaved data mapped onto symbols, the method comprising the steps of:

a) finding a finder pattern within a captured image of the bar code on a decoding device;

b) correcting symbol distortions within the captured digital image to produce a corrected bar code symbol;

c) decoding the header information bar code from the corrected bar code symbol within the captured digital image;

d) sampling reference cells from the corrected bar code symbol within the captured digital image; e) decoding symbols within the data field of the corrected bar code symbol within the captured digital image;

f) de-interleaving the decoded data from the corrected bar code symbol within the captured digital image;

g) error correcting the de-interleaved data from the corrected bar code symbol within the captured digital image ; and

h) decompressing the error corrected data from the corrected bar code symbol within the captured digital image.

[0067] The decoding method may thus include the steps of:

a) retrieving the header information;

b) sampling colour values of colour reference cells from known positions;

c) reading the set of colour values of a centroid of at least one bar code cell;

d) determining the colour of the, or each, bar code cell;

e) mapping the colour symbols to corresponding data values;

f) performing error detection and correction; and

g) retrieving the encoded data.

[0068] The decoding method may be implemented as a software product stored on a computer readable medium containing instructions for execution by a processor, and the instructions, when executed, perform the decoding method.

[0069] The decoding method may be implemented as a hardware product, with digital logics, which, when executed, perform the decoding method.

[0070] The header information may include information relating to the security settings, indicators for use, and the symbol version. The symbol may be constructed such that the position of the colour reference cells is included in the header information, as well as information which allows for the calculation of the centroid of each data cell, when used in conjunction with the computed symbol size.

[0071] The step of sampling the colour values of colour reference cells from the known position may comprise single pixel sampling. The step of sampling the colour values of colour reference cells from the known position may comprise plural pixels sampling. The method may include the step of calculating or determining the average of the colour values of the sampled pixels (in one embodiment 9 samples pixels) or a 3 x 3 window having a center which defines a center pixel of the target cell.

[0072] To avoid a stained pixel changing the whole colour value, the method may include the step of removing extremes by computing the gaps in colour values between adjacent pixels prior to performing the averaging calculation.

[0073] The step of reading the set of colour values of the centroid of each data cell may include the step of computing the positions of the centroids of each data cell. In any calculations of this form it is advantageous to calculate the cell height and width separately, as the shape of the device or cell may be slightly changed after the orientation and distortion correction.

[0074] In a seventh aspect of the present invention, there is provided a bar code comprising a matrix of cells arranged in an optically readable symbol to carry information, where symbols used in the matrix of cells are selected as symbols that are at a distinguishable distance apart across more than one colour space. The distance apart may be maximal.

[0075] According to an eighth aspect of the present invention, there is provided a bar code comprising a header information bar code to contain its header information, where the header information bar code contains encoded information pertaining to at least one of the encoding, decoding, error protection, symbol dimension, security or other applicable header information of the bar code. [0076] The bar codes of the invention may be encoded and decoded using mobile devices. As such, it may be encodable or decodable using mobile devices or non- mobile devices. Preferably, the encoding or the decoding of the bar code is on a mobile device, while the other process may be on a non-mobile device, or vice versa.

[0077] The bar code symbol may be in the form of 20 x 20, 30 x 30, or 40 x 40 data cells, or any suitable variation or intermediates thereof. Typically, the symbol is in the form of a 30 x 30 data cell.

[0078] The header information bar code may be a one dimensional bar code. The header information bar code may be a two, or more, dimensional bar code. The header information bar code may contain additional information such as (i) error correction levels, (ii) security settings; and (iii) one or more structured append indicators.

[0079] The bar code may be produced as a printed hard copy or as a digital soft copy. Preferably the bar code is produced as a digital display.

[0080] According to a further aspect of the invention, there is provided a method of generating a bar code symbol, the method comprising the steps of:

1. compressing raw data to be encoded;

2. error-protecting the compressed data;

3. mapping the error-protected data onto colour symbols;

4. creating a header information bar code; and

5. generating a bar code symbol.

[0081] According to a still further aspect of the invention, there is provided a symbol recognition operation for recognizing a finder pattern having at least one corner, the operation including the steps of:

1. thresholding and binarizing the input image; 2. locating a candidate for the finder pattern of a bar code symbol in accordance with an aspect of the invention;

. 3. correcting the orientation of the candidate finder pattern;

4. performing a projective transformation to correct symbol distortion; and

5. separating the bar code symbol area from the background image by cropping.

[0082] Thresholding may be accomplished by converting the coloured symbol to a binarized image, or a black and white image.

[0083] The method may include the step, once the finder pattern is located, of calculating the coordinates of the corners (or other reference coordinates) of the finder pattern, thereby to measure the length of each side of the finder pattern to enable the calculation of the orientation of the located finder pattern.

[0084] When correcting the orientation of the finder pattern, the method may include the step of locating an operatively lower or bottom part of the finder pattern where a further bar code and/or reference cells may be embedded, by computing the width of each side of the bounding border.

[0085] The step of performing a projective transformation to correct symbol distortion may be accomplished by quadrilaterals to quadrilaterals mapping between the code plane and image plane of the symbol, typically using centroids of cells at the corners of the finder pattern.

[0086] The step of cropping may occur in a coloured image format (and not in the binarized image format).

[0087] Embodiments of the present invention have the advantage of providing a data storage device such as a colour bar code that is both robust over more than one image format and has a high data capacity. This allows the bar code to operate on both mobile and non-mobile devices, and other relatively low optical resolution devices. This also has the advantage of allowing more data to be encoded in the bar code, while header information is encoded in an enjoined but separate bar code.

[0088] Embodiments of the invention have increased the usable colours that may be employed in a data storage device such as a bar. This in turn has increased the data capacity of the bar code.

[0089] Embodiments of the present invention seek to address problems in the prior art relating to the encoding and decoding of machine-based data using high capacity colour-based bar code or other symbol sets in a colour space using mobile devices. They do so by encoding the machine based data using colours at a distinguishable, preferably maximum, distance between each other across two or more colour spaces pertinent to the image reproduction, capture, display and compression formats of the mobile device.

General

[0090] Those skilled in the art will appreciate that the invention described herein is susceptible to variations and modifications other than those specifically described. The invention includes all such variation and modifications. The invention also includes all of the steps and features referred to or indicated in the specification, individually or collectively and any and all combinations or any two or more of the steps or features.

[0091] Throughout this specification, unless the context requires otherwise, the word "comprise" or variations such as "comprises" or "comprising", will be understood to imply the inclusion of a stated integer or group of integers but not the exclusion of any other integer or group of integers. It is also noted that in this disclosure and particularly in the claims and/or paragraphs, terms such as "comprises", "comprised", "comprising" and the like can have the meaning attributed to it in U.S. Patent law; e.g., they can mean "includes", "included", "including", and the like; and that terms such as "consisting essentially of and "consists essentially of have the meaning ascribed to them in U.S. Patent law, e.g., they allow for elements not explicitly recited, but exclude elements that are found in the prior art or that affect a basic or novel characteristic of the invention. [0092] Furthermore, throughout the specification and claims, unless the context requires otherwise, the word "include" or variations such as "includes" or "including", will be understood to imply the inclusion of a stated integer or group of integers but not the exclusion of any other integer or group of integers.

[0093] Other definitions for selected terms used herein may be found within the detailed description of the invention and apply throughout. Unless otherwise defined, all other technical terms used herein have the same meaning as commonly understood to one of ordinary skill in the art to which the invention belongs.

[0094] Other aspects and advantages of the invention will be apparent to those skilled in the art from a review of the ensuing description.

Brief Description of the Drawings

[0095] Further aspects of the invention will now be described, by way of example only, with reference to the following description, drawings and table. In the drawings and table:

[0096] Figure 1 illustrates a mobile multi-coloured composite (MMCC) 2-dimensional (2D) bar code symbol for encoding data at high density, suitable for mobile devices, according to embodiments of the present invention;

[0097] Figure 2 illustrates the 9 colour symbols represented in Red Green Blue (RGB) colour space, according to an embodiment of the present invention;

[0098] Figure 3 illustrates the same 9 colour symbols from Figure 2 represented in YCbCr colour space, according to an embodiment of the present invention;

[0099] Figure 4 illustrates the same 9 colour symbols from Figure 2 represented in HSV colour space, according to an embodiment of the present invention;

[00100] Figure 5 illustrates the same 9 colour symbols from Figure 2 represented in HSI colour space, according to an embodiment of the present invention; [00101] Figure 6 illustrates certain MMCC 2D bar code symbol encoding operations, according to an embodiment of the present invention;

[00102] Figure 7 illustrates certain MMCC 2D bar code symbol decoding operations, according to an embodiment of the present invention;

[00103] Figure 8 the orientation of the MMCC 2D bar code symbol, according to an embodiment of the present invention;

[00104] Figure 9 illustrates properties used for computing the position of the centroid of each data cell, according to an embodiment of the present invention;

[00105] Figure 10 illustrates a square-like grid arrangement for colour symbols in at least one colour space, according to an embodiment of the present invention;

[00106] Figure 11 illustrates an octagon-like arrangement for colour symbols in at least one colour space, according to an embodiment of the present invention.

Illustrative Embodiment of the Invention

[00107] The present invention is not to be limited in scope by any of the specific embodiments described herein. The following embodiments are presented for exemplification only.

[00108] Figure 1 illustrates a data storage device of an embodiment of the present invention in the form of a mobile multi-coloured composite (MMCC) 2D bar code for mobile devices. According to the presented embodiment, a coloured, preferably black, pattern 101 is used to encompass or mark the MMCC coloured cells 102 which define a data representation region or data field. This pattern 101 , preferably in the form of a black bounding border, also serves as a data storage device detection means or finder pattern for a mobile device to locate and re-orient the captured MMCC 2D bar code. Locating the captured 2D bar code involves the process of finding the actual bar code within the captured image. This image of the captured bar code may require some re- orientation due to the fact that it may be distorted or rotated, or both, within the captured view of the mobile device. Re-orientation involves transformation of the bar code image and correction against geometric distortions such as rotation and/or tilting. To protect the MMCC coloured cells 102 from being smeared by the black bounding border 101 , a single coloured, pixel border 103 (white in this embodiment) is used to separate the MMCC coloured cells 102 from the black bounding border 101. Once, the MMCC 2D bar code image has been located and re-oriented, the detection and decoding algorithm on the mobile device will further detect and decode the black and white header information bar code 104, which is embedded in the 101 black bounding border. This header information bar code carries the MMCC 2D bar code encoding information, which includes (i) level of error correction used; (ii) number of data cells used; and (iii) security settings used. As the resultant colours in the captured image of the MMCC 2D bar code are dependent on the printed output, the lighting conditions when the image was captured, and the colour sensitivity of the camera on the capturing mobile device, reference colour cells 105 are used to aid the colour decoding process of the MMCC 2D bar code. These reference colour cells are each bounded by a one pixel wide border (white in this embodiment) to allow better colour separation between the reference colour cells.

[00109] Figure 2 illustrates an embodiment of the current invention where 9 colour symbols, each labelled according to their Red, Green and Blue colour components, are selected in RGB colour space. One of these 9 colour symbols is 555, where its Red component is 5, its Green component is 5 and its Blue component is also 5.

[00110] The 9 colour symbols when translated into YCbCr colour space are illustrated in Figure 3, where 555 is the same colour symbol translated from the RGB colour space. An observation of Figure 3 is that even though the translated 9 colour symbols are not at the same distances apart in the YCbCr colour space as they were in the RGB colour space, the distances between the 9 translated colour symbols are still at a distinguishable, preferably at maximal, distance apart in YCbCr colour space, as they were in the RGB colour space. [00111] Figure 4 shows the same 9 colour symbols translated into the Hue Saturation and Value (HSV) colour space, where 555 is the same colour symbol both in the RGB and the YCbCr colour spaces. Even though the translated 9 colour symbols are not at the same distances apart in the HSV colour space as they were in either the YCbCr colour space or the RGB colour space, the distances between the 9 translated colour symbols are still at a distinguishable, preferably at maximal, distance apart in HSV colour space, as they were in the YCbCr colour space or the RGB colour space.

[00112] Figure 5 shows the same 9 colour symbols translated into the Hue, Saturation and Intensity (HSI) colour space, where 555 is the same colour symbol in the YCbCr, the RGB and the HSV colour spaces. Even though the translated 9 colour symbols are not at the same distances apart in the HSI colour space as they were in either the YCbCr colour space or the RGB colour space or the HSV colour space, the distances between the 9 translated colour symbols are still at a distinguishable, preferably at maximal, distance apart in HSI colour space, as they were in the YCbCr colour space or the RGB colour space or the HSV colour space.

[00113] This allows robust encoding and decoding of data in colour bar codes for mobile devices, where more than one colour symbol can be selected. According to the invention, symbols are selected that are at a distinguishable, in certain embodiments preferably at a maximal, distance apart across more than one colour space.

[00114] According to an embodiment of the invention an ancillary or additional bar code may be used to encode header information of a given bar code and to embed this header information bar code (for example, 104 in Figure 1 ) in the finder pattern of the main bar code (for example, Figure 1 ). This allows more header information to be robustly stored in a limited space, without taking away or interfering with any data encoding space (for example 102 in Figure 1 ) from the main bar code. It also prevents the cell size falling below a certain point where two adjacent cells can no longer clearly be distinguished. [00115] Processes for encoding data in the mobile multi-coloured composite (MMCC) 2D bar code are illustrated in Figure 6. In the first step 601 , information data to be encoded is compressed using a data compression algorithm, such as arithmetic coding. Then in 602, error correction coding will be applied on the compressed data. An example of such an error correction coding is Reed Solomon coding. Then in 603, these error correction encoded data are interleaved so that consecutive data are not clustered together. This will ensure that when an error does occur in the decoding process, no long consecutive streams of data are in error, as error correction algorithms such as Reed Solomon are best at correcting burst errors and not long chain of consecutive errors. An example of data interleaving is to use pseudo-random interleaving. Then in 604, the interleaved data are encoded using the selected colour symbols that are at a distinguishable, in this embodiment maximal, distance apart across more than one colour space. Having completed this data-to-colour symbol mapping process, the code header information, such as error correction level used, bar code size, security parameters and so forth are created and encoded in another bar code symbology at step 605. Finally at 606, a MMCC 2D bar code (such as that illustrated in Figure 1 ), which comprises the encoded colour symbols (102 in Figure 1 ), header information bar code (104 in Figure 1), reference colour cells (105 in Figure 1 ) and finder pattern (101 in Figure 1) is produced.

[00116] An error correction level can be selected according to the user's requirements. Generally, an error correction rate will be approximately 22%. Once the data are compressed, Reed-Solomon codes are computed and added to the compressed data in step 602. 8 bits are used to encode each symbol. Prior to applying the random interleaving operation in step 603, these data are converted to decimal integers and padded with "0"s as required. The zero-padding is performed when the amount of data is not sufficient to be encoded into a certain version of the invention. For example, when the number of the integers (i.e., the data to be encoded) is less than 900 for certain version of the MMCC 2D bar code comprising 30 x 30 data cells, zero-padding is performed. After all the necessary operations have been completed, the entire data are interleaved in step 603. [00117] In an embodiment of step 604 of Figure 6, the data with error-protection are preferably mapped to colour symbols according to a code conversion mapping method. Table 1 presents an example of such a mapping method. The sets of colour values are presented in the normalized range [0, 1].

Table 1 illustrates a code mapping method, according to an embodiment of the present invention.

[00118] The mapping of binary information bits to colour symbols in a MMCC 2D bar code (ie step 604 in Figure 6), is illustrated in Table 2. Firstly, the binary information bits are grouped into information symbols of 3-bit, and these information symbols of 3- bit are then mapped to the 9 colours symbols, such as that presented in Figure 2. This mapping is according to the table illustrated in Table 2, where the symbols of 3-bit are categorised as 3-bit Gray code, where each adjacent Gray code is mapped to colour symbol that are non-adjacent and distinguishably apart in a given colour space. A control information symbol CTRL is mapped to the colour symbol 555 of Figure 2. This mapping can assist to minimise the potential error in decoding of the information bits encoded in the colour symbols of the MMCC 2D bar code. The reverse of this mapping is performed at step 704 of Figure 7. The reverse mapping is done by mapping the colour symbol on the right column to the 3-bit Gray code in the left column, of the mapping in Table 2.

Table 2 illustrates the mapping of 3-bit Gray code to the 9 colour symbols from Figure 2, according to an embodiment of the present invention.

[00119] In step 605 of Figure 6, the code header information, such as error correction level used, bar code size, security parameters and so forth are created and encoded in another bar code symbology. This header information bar code can be either 1 D bar code or 2D bar code. Encoding the symbol version is essential in order to decode the present invention accurately since it defines the number of data cells and the position of the colour reference area. Additional information such as error correction level, security setting and a structured append indicator can also be encoded.

[00120] In an embodiment of step 606 of Figure 6, the bar code symbol of the MMCC is preferably produced as print on paper or be displayed on digital screen.

[00121] An embodiment of the current invention in decoding a MMCC 2D bar code is illustrated in Figure 7. Firstly, in 701 , the finder pattern of the MMCC 2D bar code is located in the captured image on the mobile device. If no MMCC 2D bar code finder pattern can be located within the image, then the decoding process will end. If the finder pattern is located within the image, then, step 702 of the decoding process is to correct for the MMCC 2D bar code symbol distortions within the captured image. The corrected distortions include, but are not restricted to, symbol rotation, symbol tilting and symbol skewing. Once the MMCC 2D bar code symbol within the captured image has been correctly re-oriented, step 703 of the decoding process is to decode and interpret the header information bar code within the finder pattern in order to determine the encoding parameters of the MMCC 2D bar code. Furthermore, the colour from the colour cells in the captured image of the MMCC 2D bar code is also sampled. These sampled reference colours will be used to determine the base reference colours of the data cells within the captured MMCC 2D bar code. Based on these sampled reference colours, the MMCC 2D bar code colour symbols are decoded in step 704 of the decoding process. The decoded data is then de-interleaved using the inverse interleaving operation (step 603) of the encoding process illustrated in Figure 6. This is done in step 705 of Figure 7. The de-interleaved data is then processed by an error detection and correction decoding operation, step 706, which is suited to the error correction coding employed in step 602 of Figure 6. For example, for Reed Solomon coding, the Viterbi decoding operation is employed. The successfully decoded data will then, in step 707, be decompressed by a decompression operation suited to the compression algorithm of step 601 of Figure 6. If the error detection and correction decoding process is unsuccessful, the decoded data cannot be decoded and will result in the termination of the MMCC 2D bar code decoding process. Otherwise, step 708 will extract the raw data from the decompression process of step 707.

[00122] In an embodiment of step 701 in Figure 7, a thresholding process is performed to convert the captured colour image to a binarized image or black and white image, which facilitates detection and correction of the target. This process removes the effect of colour including the colours in the reference cells, leaving the skeleton of the finder pattern and the background image with similar colour values to the finder pattern. Thresholding may be conducted in two different but preferably ways: using a modified adaptive thresholding method known in the art and/or using the threshold empirically (i.e. known in the art as "global thresholding"). The former scheme is an effective method to remove the uneven lighting effect from the input/captured image and, in fact, demonstrated strong capability in removing the lighting effect. However, as known in the art, the adaptive thresholding is very time consuming even when the floating point operations are replaced with the shifted integer operations to reduce the operation time. Furthermore, the latter method can save considerable time and computational power. Moreover, there was no significant difference observed in the quality between the images thresholded by the adaptive thresholding and the "global thresholding" method even when the target images were exposed to rather strong lighting effect. Thus, for this embodiment either one, or both, thresholding methods can be applied as one part of step 701 in Figure 7.

[00123] In an embodiment of step 701 in Figure 7, the solid border 101 of Figure 1, wherein the header information 104 and colour reference cells 105 are embedded, allows the area of the finder pattern to be used as a criterion to search for a candidate finder pattern. In this embodiment, the decoder first searches for a candidate for the finder pattern within the captured image. Once the finder pattern is located, the coordinates of its four corners are calculated, which are then used to measure the length of each side of the rectangular finder pattern. The size of each side and the coordinates of the four corners enable the calculation of the orientation of the located finder pattern.

In an embodiment of step 702 in Figure 7, in correcting the orientation of the candidate finder pattern, the operatively lower or bottom part of the finder pattern, where another bar code and the reference cells are embedded, may be found by computing the width of each side of the bounding border. The widest side should be the bottom. The lengths of the opposite side (Λ) and the adjacent side (w) can be obtained via the coordinates of both ends of the bottom (see Figure 8). Hence, the orientation angle (θ) between the x- axis of the image and the base of the lower/bottom part can be calculated as:

Θ = arctan — . w [00124] In another embodiment of step 702 in Figure 7, in correcting the bar code symbol distortion, the projective transformation that is preferably applied (also known as homogeneous transformation or projective mapping), is the quadrilaterals to quadrilaterals mapping between the code plane and image plane. This can be performed once four corresponding points in the finder pattern are located. The centroids of cells at, or proximal to, the corners of the finder pattern are used in this calculation.

[00125] The general form of a projective transformation is a rational linear mapping, as known in the art, and the code coordinate (u, v) is mapped to the image coordinate (x, y) with:

au + bv + c du + ev + f

X = . 5 y = gu + hv + i gu + hv + i '

where one can assume i=1 without loss of generality.

[00126] The remaining 8 unknown coefficients a to h, which denote the external parameters (e.g., position and direction) and the internal parameters (e.g., focal length) of the camera capturing the bar code image, is obtained from the four point correspondences by computing,

X₀ M ₀

X₁ M ₁

X₂U ₂

X₃ M ₃ y_ϋ ^uo

y₂u₂

y₃u ₃

[00127] Once all the necessary corrections are performed, the next step is decoding the bar code, step 703 in Figure 7. Prior to decoding, the image is cropped leaving only the 2D bar code symbol, which improves the subsequent decoding performance. This operation is applied to the coloured image, and not the binarized image.

[00128] In an embodiment of step 703 in Figure 7, the header information is retrieved. This header information can include optional information such as security setting and an indicator for use of the structured append. Of these, the important information is the symbol version that defines the number of cells in the data area and the position of the colour reference area. Together with the computed symbol size (i.e., its height and width), the former information enables the calculation of the centroid of each data cell. The position of the colour reference cells are fixed, depending on the symbol version.

[00129] In another embodiment of step 703 in Figure 7, the values of the colour reference cells are sampled. There are two sampling approaches to retrieve the colour values: a single pixel sampling and plural pixels sampling. The former approach is to simply sample the centroid of each cell and retrieve the set of the colour values belong to that single pixel. In the latter approach, more than one pixel within each cell is sampled and the set of the average of each R, G and B colour component of the sampled values are considered to represent the colour values of that cell.

[00130] When, for example, an ink stain happens to be on the sampled pixel and the colour values are determined accordingly, referring the values of that single pixel may result in incorrect colour determination of data cells. To avoid this, the latter approach is adopted for sampling the colour values of the reference cells. The average is taken from the colour values of the 9 sampled pixels or the 3 * 3 window whose centre is the centre pixel of the target cell. In order to avoid a stained pixel changing the whole colour value, the extremes are removed by computing the gaps in colour values between adjacent pixels before the average calculation.

[00131] To read the centroid of each data cell, first, the positions of the centroids must be computed. [00132] As illustrated in Figure 9, the width of the solid bounding border is equivalent to a side of a square data cell. The operatively lower or bottom part of the finder pattern corresponds to 5 times the side of a data cell. Hence, the height, H_c and the width, W_c of each data cell can be computed from the height, H_f and the width, W_f of the finder pattern and the number of data cells as:

H_c = ^f-

Number of cells + 6

and

W_f w_c = Number of cells + 2 >

respectively. Although the shape of the data cells is originally square, the cell height and width are calculated separately as the shape may be slightly changed after the orientation and distortion correction. This results in accurate computation of the centroids.

[00133] In contrast to the sampling approach taken in the second step, a single pixel sampling is applied to reading data cells, due to two reasons. The first reason is that it can save computational power. Another reason is that it may reduce the chance to introduce unreliable colour values. As compared to the reference cells, the size of data cells is rather small. Furthermore, there are no separators between data cells, which cause colour blending at the edges between the adjacent data cells. The centroid of each cell is the furthest point from the blending effect, and as a result, the set of colour values of the centroid is considered to be the most reliable information.

[00134] Due to computational errors (e.g., a cumulative error), it is possible that the reading software samples the colour values at the pixel slightly off the real centroid. If, for example, the centre of the 3 * 3 window is off the accurate point, some of the pixels around it should be even further. This means they are closer to the edge pixels under the blending effect, increasing the chance to sample unreliable colour values. [00135] In an embodiment of step 704 in Figure 7, wherein the colour of each data cell is determined, this can be achieved by comparing the set of sampled colour values with those in the colour reference cells. The Euclidean distances between the set of the sampled colour values and those of each reference cell in the 3D RGB colour space are first calculated. Then, the colour of the sampled cell is determined by selecting the reference colour whose colour values are closest to those of that data cell.

[00136] The use of reference cells is desirable for robust colour bar code reading. However, it may not be perfectly reliable all the time. In fact, it has appeared that the values of reference cells are often lower as compared to those of data cells. A possible cause for this is the location of the colour reference area. Although the reference cells are enclosed by 4-pixel-wide white separator, the reference area is embedded in the black finder pattern, which often darkens the entire area. To solve this problem, the invention provides a colour sampling scheme to determine new reference points. These can be obtained in the following steps:

1. Compute the distance between each reference point and its neighbouring reference points;

2. Find the minimum distance between each reference point and its neighbouring colours;

3. Create a circular boundary whose radius is equivalent to the 25% of the minimum distance from each reference point;

The percentage will increase by 5% until the radius reaches the 50 of the minimum distance.

4. Perform the colour determination process, making the colour cluster of each colour;

It will continue until either the number of assigned colours to each reference colour reaches the 3% of all the colour symbols or the radius of each circle reaches the 50% of the minimum distance. 5. Calculate the average of the colour values of each colour cluster, which results in a new reference point for the corresponding colour; and

6. Validating the new reference point.

By comparing the minimum distance previously obtained and the distance between the new reference point and its closest neighbouring reference point, if the former is shorter, the new reference point is considered to be valid, or else invalid. When the new reference point is invalid, the previous reference point is used for the subsequent colour determination process.

[00137] Once the new reference points are acquired, the entire colour determination process is repeated. This is done until all the colours in the data cells are determined. Then the coloured data cells are mapped to their corresponding data values. In one embodiment, this mapping between colour symbols and the corresponding data values can be done simply using the code conversion table (see Table 1 ) or if encoding was done using 3-bit Gray code, then by using the mapping in Table 2. This is the inverse operation of the MMCC 2D bar code encoding process 604 in Figure 6.

[00138] In yet another embodiment, a combination of the Reed-Solomon coding and interleaving techniques is used to protect data in the MMCC 2D bar code symbol. Thus, to detect and correct errors, the data is first de-interleaved in step 705 of Figure 7. The de-interleaved data is then corrected when errors are found in step 706 of Figure 7.

[00139] In a further embodiment, generally, the data is compressed before they were encoded into a MMCC 2D bar code symbol. Hence, in this embodiment of the present invention, the data are first decompressed in step 707 of Figure 7, and then, the original data are reconstructed in step 708 of Figure 7.

[00140] In an embodiment of the invention, the arrangement of the colour symbols in at least one of the colour spaces is of the shape of a square-like grid arrangement such as illustrated in Figure 10. In this embodiment, each of the grid coordinates (Rj, C_j), as illustrated in Figure 10, where i = {1 , 2, 3,4} and j = {1 ,2,3,4}, maps to one 3 dimensional coordinate in the or each colour spaces. There also can exist more than one layer of such square-like grid arrangement within the same colour space, such that these layers and their respective colour symbols are at a distinguishable, preferably at maximal, distance apart in the or each colour spaces.

[00141] In another embodiment, the arrangement of the colour symbols in at least one of the colour spaces is of the shape of an octagon-like grid arrangement such as illustrated in Figure 11. In this embodiment, as illustrated in Figure 11 , one octagon-like grid arrangement, where the colour symbol positions are marked with solid dots and joint by dashed lines, can exist on its own, or (as illustrated in Figure 11 ), be overlaid with at least another octagon-like grid arrangement, where the colour symbol positions are marked with round circles and joint by solid lines, within the same colour space, such that these arrangements and their respective colour symbols are at a distinguishable, preferably at maximal, distance apart in the or each colour spaces. In this embodiment, each of the colour symbols map to one 3 dimensional coordinate in the or each colour spaces.

[00142] In yet another embodiment, the arrangement of the colour symbols in at least one of the colour spaces is of the shape of a geometric grid arrangement, where such an arrangement can exist on its own, or together with one or more other geometric grid arrangement within the same colour space, such that these arrangements and their respective colour symbols are at a distinguishable, preferably at maximal, distance apart in the or each colour spaces.

[00143] Modifications and variations such as would be apparent to a skilled addressee are deemed to be within the scope of the present invention.

Claims

The Claims Defining the Invention are as Follows:

1. A data storage device comprising:

(a) a data representation region; and

(b) an information storage device detection means,

2. A bar code, the bar code comprising:

3. A data storage device according to claim 1 or a bar code according to claim 2 wherein the symbols are at a maximal distance apart across more than one colour space.

4. A data storage device according to claim 1 or a bar code according to claim 2 wherein the data representation region is a matrix of cells existent as optically- readable or machine-readable symbols.

5. A data storage device according to claim 1 or a bar code according to claim 2 wherein the data representation region includes between 2 and 128 reference points

6. A data storage device according to claim 1 or a bar code according to claim 2 wherein the data representation region includes 9 reference points

7. A data storage device according to claim 1 or a bar code according to claim 2 wherein the data representation region and the information storage device detection means are separated by a separator.

8. A data storage device according to claim 1 or a bar code according to claim 2 wherein the information storage device detection means is a finder pattern that helps the decoding device to locate the position of the bar code within the captured image.

9. A data storage device according to claim 1 or a bar code according to claim 2 wherein the information storage device detection means encodes header information in the form of a 1 D bar code or 2D bar code.

10. A data storage device or a bar code according to claim 9 wherein the header information includes information pertaining to at least one of the encoding, decoding, error protection, symbol dimension, security, bar code version or error correction level.

11. A data storage device according to claim 1 or a bar code according to claim 2 adapted for encoded and or decoded using a mobile device.

12. A method of encoding a data storage device as defined by any one of claims 1 and 3 to 11 , the method comprising the steps of:

a) compressing raw data to be encoded;

b) error protecting the compressed data;

c) interleaving the error protected data; and

13. Use of a mobile device for encoding a data storage device as defined by any one of claims 1 and 3 to 11 , wherein the device employs the method of claim 12.

14. A method of encoding a bar code as defined by any one of claims 2 to 11 , the method comprising the steps of:

b) error protecting the compressed data using an error correction encoding scheme that is suitable for the output medium of a bar code encoding device;

c) interleaving the error protected data using an interleaving operation;

e) creating a header information bar code; and

f) producing a bar code.

15. Use of a mobile device for encoding a bar code as defined by any one of claims 2 to 11 , wherein the device employs the method of claim 14.

16. A method of decoding a data storage device as defined by any one of claims 1 and 3 to 11 , the method comprising the steps of:

a) finding a pattern within the data storage device;

b) decoding data within a data representation means of the data storage device;

c) de-interleaving the decoded data;

d) error correcting the de-interleaved data; e) decompressing the error corrected data; and

f) retrieving the encoded data.

17. Use of a mobile device for decoding a data storage device as defined by any one of claims 1 and 3 to 11 , wherein the device employs the method of claim 16.

18. A method of decoding a bar code as defined by any one of claims 2 to 11 , the method comprising the steps of:

d) sampling reference cells from the corrected bar code symbol within the captured digital image;

e) decoding symbols within the data field of the corrected bar code symbol within the captured digital image;

g) error correcting the de-interleaved data from the corrected bar code symbol within the captured digital image; and

19. Use of a mobile device for decoding a bar code as defined by any one of claims 2 to 11 , wherein the device employs the method of claim 18.

20. A data storage device as claimed in claim 1 or a bar code as claimed in claim 2, substantially as herein described and illustrated.

21. A method of encoding a bar code as claimed in claim 14, substantially as herein described and illustrated.

22.A method of decoding a bar code as claimed in claim 18, substantially as herein described and illustrated.