United States Patent (19)
`Hara et al.
`
`54
`
`75
`
`73
`
`21
`22
`51
`52
`58
`
`OPTICALLY READABLE TWO
`DMENSIONAL CODE AND METHOD AND
`APPARATUS USNG THE SAME
`
`Inventors: Masahiro Hara, Nagoya; Motoaki
`Watabe, Toyokawa; Tadao Nojiri,
`Oobu; Takayuki Nagaya, Nagoya; Yuji
`Uchiyama, Aichi-ken, all of Japan
`Assignees: Nippondenso Co., Ltd., Kariya;
`Kabushiki Kaisha Toyota Chuo
`Kenkyusho, Aichi-ken, both of Japan
`
`Appl. No.: 403,548
`Filed:
`Mar 14, 1995
`Int. Cl. ............. G06K 19/06: G06K 7/10
`U.S. C. ....................................... 235/294; 235/462
`Field of Search .................................. 235/456, 454,
`235/494. 460, 470, 465; 250/566; 382/56
`
`56
`
`References Cited
`U.S. PATENT DOCUMENTS
`4,263,504 4/1981 Thomas ................................... 235.454
`4,528,444 7/1985 Hara et al. .............................. 235/462
`4,736,109 4/988 Dvorzsak ......
`... 235,494 X
`4,896,029
`1/1990 Chandler et al. .....
`... 235,494
`4,924,078 5/1990 Sant'Anselmo et al. .
`... 235,494
`4,939.354 7/1990 Priddy et al. ........................... 235/.456
`4,958.064 9/1990 Kirkpatrick ..
`... 235,462 X
`5,053,609 10/1991 Priddy et al. ........................... 235/436
`5,124.536 6/1992 Priddy et al. .
`... 235,432
`5.126,542
`6/1992 Priddy et al. ...
`... 235/.456
`5, 89,292 2/1993 Batterman et al.
`... 235/494.
`5202,552 4/1993 Little et al. ............................. 235,494
`5204,515 4/1993 Yoshida .....
`... 235,494 X
`5,288,986 2/1994 Pine et al. ............................... 235,494
`
`
`
`USOO5726435A
`Patent Number:
`Date of Patent:
`
`11
`45
`
`5,726,435
`Mar. 10, 1998
`
`5296,693 3/1994 Hughes-Hartogs ..................... 235,494
`5,324.923 6/1994 Cymbalski et al. ....
`... 235,494
`5,343,031
`8/1994 Yoshida ..........
`... 235,494
`5,40,620 4/1995 Yoshida ......
`... 235.7494
`5,464.974 11/1995 Priddy et al. ........................... 235,494
`
`FOREIGN PATENT DOCUMENTS
`0561334 9/1993 European Pat. Off. ............... 235.7494
`0564708 10/1993 European Pat. Off. ............... 235,494
`212579 1/1990 Japan ..................................... 235,494
`33.8791
`2/1991 Japan ..................................... 235,494
`4157587
`5/1992 Japan ..................................... 235,494
`61-72371
`4/1996 Japan.
`
`Primary Examiner-Donald T. Hajec
`Assistant Examiner. Thien Minh Le
`Attorney, Agent, or Firm-Cushman, Darby & Cushman IP
`Group of Pillsbury Madison & Sutro LLP
`57
`ABSTRACT
`A two-dimensional code 1 consists of three positioning
`symbols 2, a data region 3, timing cells 4 and an apex
`detecting cell 5. The shape of the whole code 1 is a square
`having the same number of vertical and lateral cells. A
`scanning line passing through the center of each positioning
`symbols 2 always gives a constant frequency component
`ratio-dark:light:dark:light:dark=1:1:3:1:1, irrespective of
`the scanning direction. For this reason, even if a rotational
`angle of the two-dimensional code is not certain, the specific
`frequency component ratio of each positioning symbol 2 can
`be easily detected by executing only one scanning operation
`in a predetermined direction. Hence, the coordinates of the
`center of each positioning symbols 2 can be easily found.
`Thus, the position of the two-dimensional code 1 is quickly
`identified.
`
`61 Claims, 13 Drawing Sheets
`
`Samsung, Exh. 1035, p. 1
`
`

`

`U.S. Patent
`
`Mar. 10, 1998
`
`Sheet 1 of 13
`
`5,726,435
`
`A/G 7
`l
`2.
`3a MY
`
`2.
`
`
`
`Samsung, Exh. 1035, p. 2
`
`

`

`U.S. Patent
`
`Mar. 10, 1998
`
`Sheet 2 of 13
`
`5,726,435
`
`
`
`Samsung, Exh. 1035, p. 3
`
`

`

`U.S. Patent
`
`Mar. 10, 1998
`
`Sheet 3 of 13
`
`5,726,435
`
`F/G, 44
`
`P2
`
`i
`P 4b 4a
`-----------
`H J
`1 H 3
`
`
`
`2
`
`P3
`
`3|
`
`
`
`Ll
`
`
`
`P4
`
`
`
`R1
`
`Samsung, Exh. 1035, p. 4
`
`

`

`U.S. Patent
`
`Mar 10, 1998
`
`Sheet 4 of 13
`
`5,726,435
`
`
`
`
`
`Samsung, Exh. 1035, p. 5
`
`

`

`U.S. Patent
`
`Mar. 10, 1998
`
`Sheet 5 of 13
`
`5,726,435
`
`A/G 6B
`ARELA7 EO AAR7
`
`rxAS
`
`3& --6
`&
`&N-16
`SXXXXX
`&
`
`
`
`
`
`
`
`exX X s
`
`2
`6XX
`&&.
`& X 16 & &
`XXXXXXXXXX
`XX
`XXXXXXXXX
`SX9
`
`
`
`Samsung, Exh. 1035, p. 6
`
`

`

`Mar. 10, 1998
`
`Sheet 6 of 13
`
`US. Patent
`
`33 —
`
`5,726,435
`
`L
`
`K
`LK
`h
`cr
`a
`x
`© *
`m <
`x
`Q
`oy
`gi
`SR G GX
`us
`TS
`cst
`Cn ee
`e
`oe
`oe
`
`Samsung, Exh. 1035,p. 7
`
`Samsung, Exh. 1035, p. 7
`
`

`

`U.S. Patent
`
`Mar. 10, 1998
`
`5,726,435
`
`Sheet 7 of 13
`
`Samsung, Exh. 1035, p. 8
`
`Samsung, Exh. 1035, p. 8
`
`

`

`U.S. Patent
`
`Mar. 10, 1998
`
`Sheet 8 of 13
`
`5,726,435
`
`
`
`A/G, 94
`
`51 a : DS
`
`
`
`Samsung, Exh. 1035, p. 9
`
`

`

`U.S. Patent
`
`Mar. 10, 1998
`
`Sheet 9 of 13
`
`5,726,435
`
`A/G 77A A/G 77B F/G 77C
`
`A/G 724
`
`
`
`A/G 72B
`
`69
`
`bs babibolo
`
`
`
`Samsung, Exh. 1035, p. 10
`
`

`

`U.S. Patent
`
`Mar. 10, 1998
`
`Sheet 10 of 13
`
`5,726,435
`
`A/G 74
`
`DATA SET
`
`BINARY ENCODING
`
`ADD CRC CODE
`
`ADD ERROR CORRECTION
`CODE
`
`TWO-DMENSONAL
`ARRANGEMENT
`
`101
`
`102
`
`103
`
`104
`
`O 5
`
`106
`
`TAKE EXCLUSIVE-OR WITH
`CELL-FEATURE-CONVERSION
`MATRX PATTERN
`
`O7
`
`DETECTION OF OPTIMUM
`PLACEMENT
`
`PRINTING OPERATION i
`
`108
`
`09
`
`PLACEMENT NTO TWO
`DIMENSONAL CODE
`
`END
`
`Samsung, Exh. 1035, p. 11
`
`

`

`U.S. Patent
`
`Mar. 10, 1998
`
`Sheet 11 of 13
`
`5,726,435
`
`A/G 76
`
`START OF READING
`OPERATION
`
`BINARY ENCODNG OF
`MAGE SIGNAL
`
`STORE BINARY-CODED IMAGE
`INTO MEMORY
`
`DETECT COORD NATES OF
`POST ON ING SYMBO
`
`
`
`Thr
`OR MORE POST ONNG
`SYMBOLS 2
`
`
`
`YES
`SELECT THREE POST ONING
`SYMBOLS
`
`CALCULATE COORDNATES
`OF APEX HAVING NO
`POSITONING SYMBOL
`
`
`
`
`
`
`
`DETECTED
`
`
`
`APEX
`DETECTING CELL
`DETECTED 9
`
`360 NOT
`DETECTED
`
`OBTAN COORD NATES OF
`CENTER OF EACH TMING
`CELL
`
`OBTAN COORD NATES OF
`CENTER OF EACH DATA CELL
`
`380
`
`390
`
`
`
`
`
`
`
`
`
`S THERE
`ANOTHER COMBINATON
`OF POSITONING
`SYNBOLS 2
`
`Samsung, Exh. 1035, p. 12
`
`

`

`U.S. Patent
`
`Mar. 10, 1998
`
`Sheet 12 of 13
`
`5,726,435
`
`A/G 16
`GD
`
`". 10
`
`JUDGE WHE-AND-BLACK PATTERN
`OF DATA CELLS
`
`girl:
`
`READ INFORMATION OF CELL
`FEATURE-CONVERSION MATRIX
`PATTERN
`
`420
`
`TAKE EXCLUSIVE-OR WITH CEL
`FEATURE-CONVERSION MATRX
`PATTERN
`
`DIW DE DATA REGON INTO
`CHARACTER CELL GROUPS
`
`CONVERT EACH CHARACTER CEL
`
`GROUP INTO DATA (CHARACTER) E.
`
`430
`
`40
`
`NO
`ERROR
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`450
`
`ERROR DETECTED
`BY ERROR-CORRECTING
`CODE
`
`ERROR FOUND
`CORRECT DATA ERROR
`
`460
`
`
`
`ERROR DETECTED
`BY ERROR DEECTING CODE
`(CRC CODE) 9
`
`40 ERROR
`FOUND
`
`NO ERROR
`END OF READING OPERATION
`
`(2)
`
`Samsung, Exh. 1035, p. 13
`
`

`

`U.S. Patent
`
`Mar. 10, 1998
`
`Sheet 13 of 13
`
`5,726,435
`
`
`
`A/G 16
`ARELATED AAR
`
`4b 4a
`
`4.
`
`
`
`
`
`
`
`A/G 79
`ARELA/AO AAR7
`
`13
`
`130
`||||N||
`
`HOST COMPUTER
`
`Samsung, Exh. 1035, p. 14
`
`

`

`5,726.435
`
`1
`OPTCALLY READABLE TWO.
`DMENSONAL CODE AND METHOD AND
`APPARATUS USING THE SAME
`
`BACKGROUND OF THE INVENTION
`
`5
`
`2
`determine the orientation of the code matrix, thus letting us
`accurately predict the positions of all the cells based upon
`the positions of light and dark squares of these two dotted
`sides, assuring an accurate reading operation. However,
`using a large amount of cells only for determining the
`position of each cell is not desirable since the number of the
`remaining cells available in the matrix for representing other
`information is reduced accordingly.
`Moreover, the matrix disclosed in U.S. Pat. No. 4939,354
`uses a series of linearly arrayed binary-coded cells for
`representing one character. Such a cell arrangement is dis
`advantageous in that them is the possibility that numerous
`amounts of data may become unreadable due to the presence
`of a stain (spot or void).
`Furthermore, there is a possibility that exactly the same
`pattern as that of the characteristic four peripheral sides may
`happen to occur within the data area. This will necessitate
`complicated processing for the reading operation.
`Accordingly, such a complicated reading operation will
`require a significantly long time to complete.
`In general, compared with bar codes, two-dimensional
`codes allow us to deal with a large amount of data. This
`means that two-dimensional codes require a fairly long time
`to decode the data. In addition, as suggested in the above
`described problem, a long period of time is required in a
`reading-out operation for picking up two-dimensional codes
`only from the image data taken in. Yet further, one of other
`factors taking a long period of time is decode preprocessing
`which includes rotational angle detection and coordinate
`conversion processing, both of which are mandatory when
`each two-dimensional code is randomly placed with an
`uncertain rotational angle with respect to a reading device.
`Still further, the two-dimensional codes themselves are
`inherently weak against stains due to the nature of storing
`numerous information in the form of a two-dimensional
`pattern within a relatively small area.
`SUMMARY OF THE INVENTION
`Accordingly, in view of above-described problems
`encountered in the related are, a principal object of the
`present invention is to provide a novel two-dimensional
`code capable of assuring excellent accuracy during the
`reading operation and providing an excellent data ratio (i.e.
`a ratio of a data area to the whole code area).
`In order to accomplish this and other related objects, a
`first aspect of the present invention provides a two
`dimensional code comprising: cells, each representing
`binary-coded data; the cells being placed on a two
`dimensional matrix as a pattern, so as to be readable by a
`scanning operation along a predetermined scanning line; and
`at least two positioning symbols disposed at predetermined
`positions in the matrix, each of the positioning symbols
`having a pattern capable of gaining an identical frequency
`component ratio irrespective of orientation of the scanning
`line when the scanning line passes through the center of each
`positioning symbol.
`In the above two-dimensional code, it is preferable that
`the predetermined positions are apexes of the two
`dimensional matrix, or the positioning symbol has a pattern
`including concentric similar figures successively
`overlapped, or there are provided a series of timing cells
`including light and dark cells alternately arrayed with an
`inclination of 111 in the two-dimensional matrix. The binary
`coded data may include a plurality of characters, and each of
`the characters is represented by a group of cells disposed in
`a two-dimensional region of the two-dimensional matrix.
`
`O
`
`5
`
`25
`
`30
`
`35
`
`1. Field of the Invention
`This invention relates to an optically readable code for
`inputting information into a computer or the like, and more
`particularly to an optically readable two-dimensional code
`including cells representing binary-coded data and placed on
`a two-dimensional matrix so as to form a binary-coded
`pattern.
`2. Related Art
`A generally known method of reading a two-dimensional
`code includes steps of taking in an image of the two
`dimensional code by means of an image input device, such
`as a TV camera, and then detecting the position of the
`concerned two-dimensional code to read out content of the
`code. Subsequently, the size of the code matrix is obtained
`based upon the two-dimensional code thus read out, and the
`coordinates of data cells in the code matrix are successively
`obtained. Then, a judgement is made as to whether each data
`cell is "0" or "1" (i.e. light or dark). thus converting each of
`the data cells into character information.
`Such a two-dimensional code is generally advantageous,
`when it is compared with a bar code, in that a large amount
`of CD information can be stored in a relatively smaller area.
`To realize high accuracy in the reading operation of such
`two-dimensional codes, conventional technologies have
`been adopting encoding theories using various encoding
`technologies, such as an error detecting encoding operation
`and an error-correcting encoding operation. However, it
`should be pointed out that the present-day advancement of
`a reading operation of this kind of two-dimensional codes is
`still at a level that must rely on software processing executed
`by a high-performance CPU, as described later. Thus, there
`is room for improvement regarding the speed at which
`two-dimensional codes are read.
`One problem is that the two-dimensional code itself has a
`code arrangement unsuitable for a fast reading operation. In
`addition, this code arrangement is not suitable for the
`processing required to handle the rotation of the two
`dimensional code.
`45
`For example, Japanese Patent Application No. 12579/
`1990, which is a counterpart application of U.S. Pat. No.
`4,939.354, discloses a matrix having two solid sides con
`sisting of consecutively arrayed dark (black) squares only
`and another two dotted sides consisting of alternately
`arrayed light (white) and dark squares. Detection is per
`formed by discriminating each of these four sides based on
`their characteristic line profile and then determining an
`orientation of the matrix. However, in determining its posi
`tion and its rotational angle, it is necessary to scan the image
`of the matrix so extensively from every direction that all the
`characteristic patterns of these four sides are completely
`recognized.
`Furthermore, an image of the matrix is not always con
`stant in size, thus an error may occur in the detection of a cell
`when the position of the cell is predicted according to a
`predetermined interval. Still further, when light squares or
`dark squares are arrayed consecutively and extensively,
`some reading methods will possibly result in erroneous
`detection. According to U.S. Pat. No. 4939.354, two dotted
`sides are disclosed consisting of alternately arrayed light and
`dark squares. Therefore, all that needs to be done is to
`
`SO
`
`55
`
`65
`
`Samsung, Exh. 1035, p. 15
`
`

`

`5,726.435
`
`5
`
`10
`
`15
`
`3
`Furthermore, an apex detecting cell is disposed on an apex
`of the matrix where the positioning symbol is not disposed.
`A second aspect of the present invention provides a
`two-dimensional code reading apparatus for optically read
`ing a two-dimensional code including binary-coded cells
`placed on a two-dimensional matrix as a pattern, the two
`dimensional code including a symbol disposed in the vicin
`ity of an apex of the two-dimensional matrix, the symbol
`having a pattern including concentric similar figures over
`lapped successively, the reading apparatus comprising: an
`image pickup device taking an image of the two
`dimensional code, then converting the image into image
`signals pixel by pixel in response to light intensity of the
`image, and successively outputting resultant image signals;
`and a decoder unit decoding the resultant image signals into
`binary-coded signals; wherein the decoder unit comprises:
`binary-encoding means for binary encoding the image sig
`nals in accordance with a level of each signal, and outputting
`binary-coded signals successively; memory means for stor
`ing the binary-coded signals as image data in accordance
`with aposition of a pixel where the image was taken; symbol
`detecting means for detecting a specific pattern correspond
`ing to the symbol based on the binary-coded signals; apex
`detecting means for detecting coordinates of the symbol
`from the image data stored in the memory means based on
`the specific pattern detected by the symbol detecting means;
`matrix position determining means for finalizing a contour
`and an orientation of the two-dimensional matrix based on
`the coordinates of the symbol detected by said apex detect
`ing means, thereby identifying all the coordinates of the
`binary-coded cells placed on the two-dimensional matrix;
`and reading means for reading out the image data stored in
`the memory means in accordance with the finalized contour
`and orientation of the two-dimensional matrix.
`In the above two-dimensional code reading apparatus it is
`preferable that the two-dimensional code comprises a series
`of timing cells including light and dark cells alternately
`arrayed in the matrix, optically readable by the image pickup
`device; and the decoder unit further comprises timing cell
`detecting means for detecting coordinates of each timing cell
`from the image data stored in the memory means in accor
`dance with the coordinates of the symbol obtained by the
`apex detecting means, the timing cells determining a cell
`position of the image data in accordance with their intervals.
`The two-dimensional code is created by taking an
`45
`exclusive-OR between a predetermined provisional two
`dimensional code and a two-dimensional cell-feature
`conversion code which includes a specific conversion pat
`tern represented by light and dark cells corresponding to a
`data region of the provisional two-dimensional code; and the
`reading means restores information of the two-dimensional
`code by taking an exclusive-OR between the two
`dimensional image data obtained from the image pickup
`means and two-dimensional image data of the two
`dimensional cell-feature-conversion code stored in the
`55
`memory means.
`A third aspect of the present invention provides a two
`dimensional code reading method for optically reading a
`two-dimensional code including binary-coded cells placed
`on a two-dimensional matrix as a pattern, comprising steps
`of: disposing a symbol in the vicinity of an apex of the
`matrix of the two-dimensional code, the symbol having a
`pattern including concentric similar figures overlapped suc
`cessively; taking an image of the two-dimensional code by
`an image pickup device, then converting the image into
`image signals pixel by pixel in response to the light intensity
`of the image, and binary encoding the image signals in
`
`4
`accordance with a level of each signal, then storing the
`binary-coded signals as image data in a memory means in
`accordance with a position of a pixel where the image was
`taken; detecting a specific pattern corresponding to the
`symbol based on the binary-coded signals, as parallel pro
`cessing to the step of storing the binary-coded signals in the
`memory means; detecting coordinates of the symbol from
`the image data stored in the memory means based on the
`detection of the specific pattern; finalizing a contour and an
`orientation of the two-dimensional matrix based on the
`coordinates of the symbol, thereby identifying all the coor
`dinates of the binary-coded cells placed on the two
`dimensional matrix; and reading out the image data stored in
`the memory means in accordance with the finalized contour
`and orientation of the two-dimensional matrix.
`A fourth aspect of the present invention provides a
`two-dimensional code comprising: cells each representing a
`binary-coded data; the cells being placed on a two
`dimensional matrix as a pattern, so as to be readable by a
`scanning operation along a predetermined scanning line; and
`timing cells arrayed in the matrix in alternating light and
`dark manner with an inclination of 1/1.
`A fifth aspect of the present invention provides a two
`dimensional code comprising: cells, each representing
`binary-coded data; the cells being placed on a two
`dimensional matrix as a pattern, so as to be readable by a
`scanning operation along a predetermined scanning line;
`wherein the two-dimensional code is created by taking an
`exclusive-OR between a predetermined provisional two
`dimensional code and a two-dimensional cell-feature
`conversion code which includes a specific conversion pat
`tern corresponding to a data region of the two-dimensional
`code.
`A sixth aspect of the present invention provides a two
`dimensional code comprising: cells, each representing
`binary-coded data; the cells being placed on a two
`dimensional matrix as a pattern, so as to be readable by a
`scanning operation along a predetermined scanning line; and
`a group of cells representing a character, disposed in a
`two-dimensional region of the matrix.
`In the above fourth or sixth aspect of the present
`invention, it is preferable to further provide at least two
`positioning symbols disposed at predetermined positions in
`the matrix, each of the positioning symbols having a pattern
`capable of gaining an identical frequency component ratio
`irrespective of orientation of the scanning line when the
`scanning line passes through the center of each positioning
`symbol.
`In the above fifth aspect of the present invention, it is
`preferable that the specific conversion pattern includes light
`and dark cells, and the exclusive-OR is taken cell by cell
`between the predetermined provisional two-dimensional
`code and the two-dimensional cell-feature-conversion code.
`Moreover, a seventh aspect of the present invention
`provides a two-dimensional code comprising: cells. each
`representing binary-coded data; the cells being placed on a
`two-dimensional matrix as a pattern, so as to be readable by
`a scanning operation along a predetermined scanning line; at
`least two positioning symbols disposed at predetermined
`positions in the matrix, each of the positioning symbols
`having a pattern capable of gaining an identical frequency
`component ratio irrespective of orientation of the scanning
`line when the scanning line passes through the center of each
`positioning symbol; and data cells being processed by a
`predetermined conversion processing into a characteristic
`pattern different from the pattern of the positioning symbols.
`
`25
`
`35
`
`65
`
`Samsung, Exh. 1035, p. 16
`
`

`

`5,726.435
`
`S
`According to the present invention, there are provided at
`least two positioning symbols disposed at predetermined
`positions in the matrix. Each of the positioning symbols has
`a pattern capable of gaining the same frequency component
`ratio irrespective of orientation of a scanning line when the
`scanning line passes through the center of each positioning
`symbol. Accordingly, this positioning symbol enables us to
`surely obtain the same characteristic frequency component
`ratio inrespective of the orientation of a scanning line. It is,
`hence, not necessary to repeat the scanning operation exten
`sively changing its scanning angle. Thus, in the scanning
`operation of the code matrix, at least two predetermined
`positions are quickly and easily detected. Once the prede
`termined two positions are detected in the code matrix, the
`position and a rotational angle of the whole matrix are easily
`calculated based on the distance and angle between them.
`The predetermined positions can be apexes (i.e. comers)
`of the matrix. When the predetermined positions are apexes
`of the matrix, they will be found immediately during the
`scanning search, and obtaining the contour of the two
`dimensional code will be easy. Furthermore, it is advanta
`geous that the apexes are seldom disturbed by other code
`patterns when they are searched.
`The positioning symbols are disposed in at least two
`comers of the matrix, and each positioning symbol is a
`pattern including concentric successively overlapped similar
`figures.
`In this invention, it should be understood that the pattern
`capable of gaining the same frequency component ratio is a
`light-and-dark pattern which is consistently similar regard
`less of the direction of the scanning angle when the scanning
`line passes through the center of the pattern. For example,
`such a pattern will include concentric successively over
`apped similar figures. More specifically, one typical pattern
`consists of a large square of dark cells, a middle square of
`light cells concentric with but smaller in size than the large
`square, and a small square of dark cells concentric with but
`Smaller in size than the middle square. The figures are not
`limited to squares only; for example, circles, hexagons and
`other various figures, especially regular polygons, circles
`and ellipses can preferably be used. However, in view of the
`fact that the most popular shape of the matrix is a square, the
`most preferable positioning symbol would be a square or a
`rectangle since its shape fits the matrix and loss of space can
`be suppressed to a minimum level. Particularly, a square is
`most preferable since it assures the least amount of loss.
`According to the present invention, the two-dimensional
`code includes a series-of light and dark cells alternately
`arrayed in the matrix with an inclination of 1/1.
`Arraying light and dark cells in an alternating manner is
`advantageous in that the position of each cell unit is easily
`detected compared with the arrangement of consecutively
`arrayed light (white) or dark (black) cells. However, if the
`arrangement of alternately arrayed light and dark cells
`(hereinafter referred to as alternating light and dark cells) is
`parallel to the side, according to the related art such alter
`nating light-and-dark cells must stretch along at least two
`directions-i.e. in both a vertical direction and a horizontal
`direction, to cover the positions of all the cells involved in
`the matrix. However, for a square matrix being one example
`of the present invention, the line of such alternating light
`and-dark cells is disposed with an inclination of 1/1 from an
`apex. In this case, the number of cells constituting the
`alternating light-and-dark cells is as small as the number of
`cells constituting one side of the square matrix. Thus, the
`remaining cells are effectively available for other useful
`information.
`
`6
`Of course, it is preferable that the line of the alternating
`light-and-dark cells is disposed diagonally from an apex in
`view of the ease in searching for the positions of alternating
`light-and-dark cells. However, the same can be disposed
`5 from an intermediate point of a side instead of the apex. In
`such a case, the matrix will include a plurality of 1/1 inclined
`lines of alternating light-and-dark cells.
`For a matrix other than a square, a 1/1 inclined line of
`alternating light-and-dark cells starting from one apex can
`o not connect two diagonally disposed apexes. This means that
`such a 1/1 inclined line cannot cover all the cells. But, this
`problem is solved by providing another 1/1 inclined line of
`alternating light-and-dark cells starting from the other apex.
`In the event that the problem is not solved, it will be effective
`is to provide still another 1/1 inclined line of alternating
`light-and-dark cells starting from an appropriate intermedi
`ate portion of a side. Even in such a case, it is possible to
`gain more available space for other information than the
`related art arrangement of arraying alternating light-and
`o dark cells along both the vertical and lateral sides.
`A group of cells representing a character in the data region
`can be summarized in a two-dimensional pattern. This
`two-dimensional arrangement is useful in that the number of
`characters becoming unreadable due to the presence of a
`25 stain having a predetermined area is minimized. The two
`dimensional arrangement is advantageous in reducing the
`affect of a stain. Therefore, the number of spoiled characters
`can be reduced. The two-dimensional arrangement will be.
`for example, embodied as a square or a rectangular pattern.
`30 In the case that the cell number of one character unit does not
`fit a square or a rectangle, it will be possible to combine two
`characters to form a square or a rectangle.
`The two-dimensional code can be processed by a prede
`termined conversion processing into a desirable pattern,
`35 instead of directly placing it on the matrix. For example, in
`the two-dimensional code, a pattern of the data region can be
`differentiated from that of the non-data region. In this
`invention, the non-data region includes the above-described
`positioning symbols and the 1/1 inclined alternating light
`40 and-dark cells whose characteristic patterns must be
`detected in the beginning of the scanning operation. Thus, it
`is important for conversion processing to eliminate like
`patterns existing in the data region.
`For example, there is provided a conversion matrix of the
`45 same size as the data region in which a predetermined
`pattern for conversion is formed. Then, the data region is
`converted into a different pattern by taking an exclusive-OR
`with this pattern. One predetermined pattern will not always
`guarantee that the data region is reliably converted into a
`50 desirable pattern. It is thus recommended that a plurality of
`predetermined patterns be prepared beforehand, so that the
`same number of different patterns are produced by convert
`ing the data region by each of these patterns. Then, the
`preferable pattern is selected from among them by deter
`55 mining which one is most different from the non-data region.
`Moreover, it is desirable in the present invention that there
`is provided an apex detecting cell which is disposed on an
`apex of the matrix where the positioning symbol is not
`disposed.
`BRIEF DESCRIPTION OF THE DRAWENGS
`The above and other objects, features and advantages of
`he present invention will become more apparent from the
`following detailed description which is to be read in con
`65 junction with the accompanying drawings, in which:
`FIG. 1 is a view illustrating one example of a two
`dimensional code in accordance with the present invention;
`
`60
`
`Samsung, Exh. 1035, p. 17
`
`

`

`5,726.435
`
`O
`
`15
`
`20
`
`25
`
`7
`FIGS. 2A and 2B are views illustrating the frequency
`characteristics of the positioning symbols in accordance
`with the present invention;
`FIGS. 3A-3C are views illustrating placement and pro
`cessing of the positioning symbols in accordance with the
`present invention;
`FIGS. 4A and 4B are views illustrating placement of
`timing cells in accordance with the present invention;
`FIG. 5 is a view showing allocation of characters in
`accordance with the present invention;
`FIGS. 6A-6C are views comparatively illustrating the
`affect of a stain in the present invention and the related art;
`FIGS. 7A-7C are views showing characteristics of a
`conventional binary-encoding circuit;
`FIG. 8 is a view illustrating pattern conversion processing
`for differentiating the data region from the non data region
`in accordance with the present invention;
`FIGS. 9A and 9B are views showing dummy lines pro
`vided around the two-dimensional code in accordance with
`the present invention;
`FIG. 10 is a view showing another example of the two
`dimensional code in accordance with the present invention;
`FIGS. 11A-11C are views showing various modifications
`of the positioning symbols in accordance with the present
`invention;
`FIGS. 12A and 12B are views illustrating various modi
`fications of placement of the character cell groups combined
`with each other in accordance with the present invention;
`FIG. 13 is a view showing another embodiment of the
`two-dimensional code in accordance with the present
`invention, which is characterized by a rectangular shape;
`FIG. 14 is a flow chart showing a series of processes
`ranging from the encoding operation of the two-dimensional
`code to the printing operation in accordance with the present
`invention;
`FIG. 15 is a flow chart showing a reading operation of the
`two-dimensional code in accordance with the present inven
`tion;
`FIG. 16 is a flow chart showing the remainder of the
`reading operation of the above two-dimensional code in
`accordance with the present invention;
`FIG. 17 is a view showing an arrangement of a reading
`device in accordance with the present invention;
`FIG. 18 is a view showing a typical placement of con
`ventional timing cells; and
`FIG. 19 is a view illustrating an invalidation processing of
`a conventional bar code.
`
`8
`located at the remaining comer of the two-dimensional code
`1. This two-dimensional code 1, a square code, is constituted
`by the same number of vertical and lateral cells (21 cellsX21
`cells). Each cell is selected from optically discriminable two
`kinds of cells, white (light) and black (dark) cells as shown
`in the drawings and in the explanation of this embodiment.
`The timing cells 4 correspond to 1/1 inclined alternating
`light and-dark cells. The apex detecting cell 5 acts as one of
`the timing cells 4. FIG. 1 shows a blank condition where no
`data is described in the data region 3.
`The positioning symbols 2.2.2 are disposed at three of the
`four comers of the two-dimensional code 1. The light and
`dark arrangement of cells in each positioning symbol 2 is
`characterized by a pattern consisting of a large square 2a of
`blackcells, a middle square 2b of white cells concentric with
`but smaller in size than the large square 2a, and a small
`square 2c of black cells concentric with the middle square
`2b, but smaller in size.
`FIG. 2 shows the scanning operation of this positioning
`symbol 2 and resul