JP2000269824A

JP2000269824A - データ符号化装置及びデータ復号化装置

Info

Publication number: JP2000269824A
Application number: JP2000006252A
Authority: JP
Inventors: Kenji Hisatomi; 健治久富; Kazuyuki Murata; 和行村田; Takehito Yamaguchi; 岳人山口; Hideyuki Kuwano; 秀之桑野; Yuji Okada; 雄治岡田; Naoki Takahashi; 直樹高橋; Joji Tanaka; 丈二田中
Original assignee: Matsushita Electric Industrial Co Ltd
Current assignee: Panasonic Holdings Corp
Priority date: 1999-01-12
Filing date: 2000-01-12
Publication date: 2000-09-29

Abstract

(57)【要約】【課題】従来の技術では２次元画像上に直線状にの
る直線状ノイズに対してはエラー訂正ができない場合が
ある。【解決手段】ランダム誤り訂正符号方式とバースト誤り
訂正符号方式の２種類のエラー訂正方式により、それぞ
れ少なくとも１種の誤り訂正符号を用いてビットデータ
を符号化する。そして、この符号化したビットデータを
規定２次元領域に行列状に配列して２次元画像を生成し
媒体に印刷する。このとき、再配置マップに基づいて上
記符号化したビットデータを再配置することも可能であ
る。一方、復号化は上記のようにして印刷された２次元
画像をよみとって、ランダム誤り訂正処理とバースト誤
り訂正処理を行うことになる。上記再配置マップを用い
たときは、復号時にも上記２次元画像を読み込んだ後に
上記再配置マップに基づいて並び替え前のビットデータ
に変換する。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、２次元コードなど
２次元の規定領域内に画像としてデータを格納する際の
データ符号化装置とこの格納された符号化データを復号
するデータ復号化装置に関するものである。

【０００２】

【従来の技術】商品の流通管理や工場での部品管理にバ
ーコードを用いるシステムが普及しているが、画像処理
技術の発達やＣＣＤテレビカメラなどが安価になり利用
しやすくなったことを背景にして、１次元バーコードよ
り格納する情報量が大きい２次元コードの開発や利用が
行われつつある。

【０００３】２次元コードは一般にその大きな情報格納
量を利用して、２次元コード内のビットデータの破損な
どのノイズに対するエラー訂正機能を持っている。例え
ば、国際自動認識工業会（ＡＩＭＪＡＰＡＮ）の規格
書「２次元コード−ＱＲコード−技術仕様ＡＩＭＪ−
ＴＣ−３−１」に記載されているＱＲコードと称される
２次元コードにおいては、リードソロモン符号かハミン
グ符号の何れか一方を適用してエラー訂正用のビットデ
ータを付加することにより、２次元コード上にのった汚
れなどのノイズによるビットデータの読み取りエラーを
訂正する機能を持っている。

【０００４】上記ビットデータの読み取りエラーを訂正
する機能は、適用する符号化方式によってエラー訂正効
率のよいノイズパターンと訂正効率の悪いノイズパター
ンがある。例えば、上記リードソロモン符号方式はバー
スト誤りに対して有効に作用し、上記ハミング符号方式
はランダム誤りに対して有効に作用する。この他にもラ
ンダム誤りに対して有効な符号方式として拡大ハミング
符号やＢＣＨ符号（Bose/Chaudhuri/Hocquengen 符
号）、バースト誤りに対して有効な符号方式としてイレ
ージャー符号や隣接符号などがある。

【０００５】

【発明が解決しようとする課題】しかしながら、上記従
来のデータ符号化装置やデータ復号化装置では、２次元
画像を印刷するときに出やすい縦筋に出現する直線状ノ
イズや、２次元画像が印刷されている紙などの媒体が折
り曲げられることによって現れる影による横筋の直線状
ノイズなど、２次元画像上に直線状にのる直線状ノイズ
に対してはエラー訂正ができない場合がある。

【０００６】例えば、上記リードソロモン符号方式は、
図２０に示すようにビットデータを幾つかのブロックＢ
０〜Ｂｊに分割するとともに、これらのブロックＢ０〜
Ｂｊに対してパリティブロックＢｐ０〜Ｂｐｊを付加し
てバースト誤り訂正機能（ブロック単位の誤りを訂正す
る機能）を持たせるようにしている。

【０００７】しかしながら、この場合、訂正可能なブロ
ックの数には限度があり、この限度を越えての複数のブ
ロックにまたがるような直線状ノイズに対してはエラー
訂正が不可能である。

【０００８】また上記ハミング符号方式では、図２１に
示すようにビットデータを複数の集合体Ｑ０〜Ｑｋに分
割するとともに、これら各集合Ｑ０〜Ｑｋに対して誤り
訂正ビットＱｐ０〜Ｑｐｋを付加してランダム誤り訂正
機能（集合を構成する各ビットを訂正する機能）を持た
せるようにしている。

【０００９】しかしながら、この場合、１つの集合体内
での訂正可能なビット数には限度があり、この限度を越
えたビット数の誤り、例えば上記集合の長さ方向の直線
状ノイズに対してはエラー訂正が不可能である。

【００１０】またさらに、上記従来のデータ符号化装置
やデータ復号化装置では、これら出現頻度の高いノイズ
に対して、デコード処理時間を最小にするような誤り訂
正符号方式を選択することもできない。

【００１１】本発明は叙上の如き実状に対処し、ランダ
ム誤り訂正符号方式とバースト誤り訂正符号方式の２種
類のエラー訂正方式をもちいてビットデータを符号化す
るデータ符号化装置及びデータ復号化装置を提供するこ
とを目的とするものである。そして、どの向きの直線状
ノイズがのってもエラー訂正能力を確実に働かせるとと
もに、２次元画像上にのりやすい直線状ノイズの向きに
応じてビットデータの再配置マップを変更することによ
り、エラー訂正時間を含めたデコード処理時間を最小に
することを目的とするものである。

【００１２】

【課題を解決するための手段】本発明は上記目的を達成
するために以下の手段を採用している。

【００１３】すなわち、本発明のデータ符号化装置は、
ランダム誤り訂正符号方式とバースト誤り訂正符号方式
の２種類のエラー訂正方式により、それぞれ少なくとも
１種の誤り訂正符号を用いてビットデータを符号化す
る。そして、この符号化したビットデータを規定２次元
領域に行列状に配列して２次元画像を生成し媒体に印刷
することを特徴とするものである。

【００１４】この場合、再配置マップに基づいて上記符
号化したビットデータを再配置し、この再配置マップに
基づいて、上記符号化されたビットデータを規定２次元
領域上に配置する際に、ランダム誤り訂正符号を付加し
たときのビットデータの集合を、上記規定２次元領域内
で行または列の何れか一方向に直線状に並べて配置する
ことも可能である。

【００１５】また、上記再配置マップを複数保持した再
配置マップ保持手段と、上記再配置手段で使用する再配
置マップを選択する再配置マップ指定手段とを設け、こ
の再配置マップ指定手段が、最も頻発するビットエラー
の方向と、上記ビットデータの集合の長さ方向とが交差
する再配置マップを選択することも好適である。

【００１６】一方、本発明のデータ復号化装置は、本発
明のデータ符号化装置で媒体に印刷された２次元画像を
読み込んで、電子データのビットデータに変換する２次
元画像読み込み手段を備える。また、この変換後のビッ
トデータでランダム誤り訂正符号を付加されたビットデ
ータの集合に対して誤り訂正と復号とを行うランダム誤
り訂正手段と、バースト誤り訂正符号を付加された上記
ビットデータの集合に対して誤り訂正と復号とを行うバ
ースト誤り訂正手段とを備えることを特徴とするもので
ある。

【００１７】この場合、上記２次元画像読み込み手段の
後段に、上記読み込んだ２次元コード等の２次元画像を
上記再配置マップに基づいて並び替え前のビットデータ
に変換するマップ配置復元処理手段を設けることも可能
である。

【００１８】上記本発明のデータ符号化装置と複合化装
置においては、ランダム符号化したビットデータの集合
の長さ方向のノイズに対しては上記バースト誤り訂正符
号が作用する。またバースト符号化したビットデータの
ブロックを複数にわたり貫通するノイズに対しては上記
ランダム誤り訂正符号が作用する。従って、２次元画像
上にどの向きのノイズがのっても、エラー訂正能力を確
実に働かせることが可能である。更に、複数のランダム
誤り訂正符号、バースト誤り訂正符号を用いることで、
より複雑な形状のノイズに対してもエラー訂正を行うこ
とができる。

【００１９】また、上記ノイズの向きに応じてビットデ
ータの再配置マップを作成し、あるいはどの向きの直線
状ノイズが２次元画像上にのりやすいかによって再配置
マップを変更することにより、上記ビットデータのブロ
ックの方向とノイズの方向とが交差するようにして、訂
正時間の速いランダム誤り訂正符号方式を優先的に利用
し、これによりエラー訂正時間を含めたデコード処理時
間を最小にすることが可能である。

【００２０】

【発明の実施の形態】以下さらに添付図面を参照して、
本発明の実施の形態を説明する。

【００２１】（実施の形態１）図１は本発明の実施の形
態１によるデータ符号化復号化装置のブロック図であ
り、この装置におけるビットデータの符号化の構成につ
いて図２のフローチャートを参照して説明する。尚、図
１において実線矢印は処理の流れを、また、白線矢印は
ビットデータの流れを示す。

【００２２】データ入出力手段３Ａより入力された所定
数、例えば１６ビットのビットデータは、ワークメモリ
９Ａに入力され、それとともにハミング符号エンコーダ
４Ａ（ここでは８．４ハミング符号化方式を用いる場合
を例とする）が起動する。このハミング符号エンコーダ
４Ａは、図４（ａ）に示すように上記ワークメモリ９Ａ
上のビットデータを所定ビット数毎の集合Ｄａ〜Ｄｄ
（ここでは４ビット毎の４つの集合）に分割し、同図
（ｂ）に示すように、各々の集合Ｄａ〜Ｄｄに上記
（８．４）ハミング符号化方式より導かれる誤り訂正ビ
ット５〜８を４ビットずつ付加（ステップ１ａ〜２ａ）
して８ビット単位の新たな集合Ｈａ〜Ｈｄを得る。尚、
図４及び以降の図において、太枠で囲まれたビットのデ
ータは”１”、囲まれていないビットのデータは”０”
であるものとする。

【００２３】この（８．４）ハミング符号化方式では、
上記のように１つの集合を構成する８ビットのデータの
うち１ビットの誤りを訂正することができるので、ハミ
ング符号エンコーダ４Ａは、ビットデータ列中に離散し
て存在するエラービットに対して誤りを訂正するランダ
ム誤り訂正機能を付与したことになる。ただし、上記８
ビットのデータ中の２ビット以上の誤りを訂正したいと
きには、さらに訂正ビット数の多いハミング符号化方式
を用いる必要がある。

【００２４】このように、上記ハミング符号エンコーダ
４Ａによってランダム誤り訂正ビットを付加されると、
次に、リードソロモン符号エンコーダ５Ａが起動する。
このリードソロモン符号エンコーダ５Ａは、図４（ｂ）
に示した上記各８ビットのビットデータの４つの集合Ｒ
ａ〜Ｒｄ（＝Ｈａ〜Ｈｄ）に対して、同図（ｃ）に示す
ように４つのパリティブロックＲｅ〜Ｒｈを生成し、付
与する（ステップ３ａ）。

【００２５】この４つのパリティブロックＲｅ〜Ｒｈ
は、１ブロックが８ビットで構成され、このリードソロ
モン符号化方式を適用したエラー訂正能力は、ビットデ
ータの集合Ｒａ〜Ｒｄの４つとパリティブロックＲｅ〜
Ｒｈの４つを合わせた８つのブロックＲａ〜Ｒｈに対し
て、２ブロックまでの誤りを訂正することができる。よ
って、リードソロモン符号エンコーダ５Ａは、１ブロッ
クを構成するビットデータに集中的に発生する誤りに対
する訂正機能、すなわちバースト誤り訂正機能を付与し
たことになる。但し、より多くのブロックに対する訂正
をしたい場合は、より多くの訂正ブロックを用いる必要
がある。

【００２６】なお、上記においてランダム符号化を先に
実行したが、バースト符号化を先に行ってもよいことは
もちろんである。

【００２７】次いで、２次元画像生成手段６Ａが起動
し、該２次元画像生成手段６Ａはワークメモリ９Ａ上に
あるランダムおよびバースト誤り訂正符号が付加された
ビットデータに基づいて以下に説明する２次元画像、例
えば２次元コードを生成する。ここで、ビットデータを
２次元コードに置換するとき、上記リードソロモン符号
エンコーダ５Ａで得られた各ブロックＲａ〜Ｒｈを単位
にして、図５（ｃ）に示すように各ブロックＲａ〜Ｒｈ
を規定の（行、列のビット配列数が所定数である）２次
元領域内の行または列の何れか一方向に並べて配置する
（ステップ４ａ）。

【００２８】この配置順序は図５（ｂ）に示す再配置手
段１０Ａとしての再配置マップ１０Ｍに記載されてお
り、２次元画像生成手段６Ａは再配置マップ１０Ｍに基
づいて上記ビットデータのブロックＲａ〜Ｒｈを図５
（ｃ）に示すように配列する。なお、図５（ｂ）（ｃ）
において、ａ〜ｈはブロックを意味し、該ａ〜ｈに対に
なっている１〜８は１ブロック内でのビットデータの順
番を表している。

【００２９】このようにして生成された２次元コードは
プリンタ１Ａに入力され、紙などの媒体に２次元画像と
して印刷される（ステップ５ａ）。

【００３０】次に、上記実施の形態１のデータ符号化復
号化装置におけるビットデータの復号化の処理について
図３のフローチャートを参照して説明する。

【００３１】上記のように紙などの媒体に印刷された２
次元画像は、スキャナ２Ａで読み込まれ（ステップ１
ｂ）、ワークメモリ９Ａに入力され、これと同時に、マ
ップ再配置復元処理手段１３Ａが起動する。

【００３２】このマップ配置復元処理手段１３Ａでは、
前記２次元画像生成手段６Ａが再配置マップ１０Ｍを基
に並べ替えたビットデータを、同じ再配置マップ１０Ｍ
を基にして、上記並べ替える前の元のビットデータに復
元する（ステップ２ｂ）。

【００３３】このようにビットデータが復元されると、
ハミング符号デコーダ７Ａが起動する（ステップ３
ｂ）。

【００３４】ここで、もし図６に示すように、２次元画
像上に斜めに直線状に貫くノイズがのっていても、その
ノイズが一直線上に並んだブロックとは異なる向きであ
る場合、ひとつのブロック内でノイズによって壊される
ビットは１ビット以下であるため、上記ハミング符号デ
コーダ７Ａがランダム誤り訂正機能でエラービットを訂
正する（ステップ４ｂ−１）。

【００３５】また、図７に示すようにそのノイズが一直
線上に並んだブロックと同じ向きであり、ひとつのブロ
ック内の２ビット以上を壊しているならば、ビットデー
タは上記ハミング符号デコーダ７Ａでは訂正され内状態
で、次のステップのリードソロモン符号デコーダ８Ａで
処理される（ステップ４ｂ−２）。

【００３６】すなわち、ハミング符号デコーダ７Ａでの
処理が終了すると、リードソロモン符号デコーダ８Ａが
起動し、ここでバースト誤り訂正処理がなされることに
なる。

【００３７】すなわち、図６に示すように２次元画像を
斜めに貫く直線状ノイズがのっていても、そのノイズが
一直線上に並んだブロックとは異なる向きであるなら
ば、ひとつのブロック内でノイズによって壊されるビッ
トは１ビット以下であるので、上記ステップ４ｂ−１で
上記ハミング符号デコーダ７Ａによって既にエラー訂正
済みとなっている。

【００３８】これに対し、図７に示すように２次元画像
上を縦に貫く直線状ノイズがのっていて、そのノイズが
一直線上に並んだブロックと同じ向きであり、ひとつの
ブロック内の２ビット以上にエラーを発生している場合
は、上記したようにこのエラービットはハミング符号デ
コーダ７Ａでは訂正されずにリードソロモン符号デコー
ダ８Ａにそのまま渡される。このとき、他の７つのブロ
ックは無傷であるので、上記リードソロモン符号デコー
ダ８Ａでバースト誤り訂正機能を適用して、７つの無傷
のブロックをもとにエラービットを含んだブロックを訂
正することが可能である（ステップ５ｂ）。

【００３９】このように、ハミング符号デコーダ７Ａと
リードソロモン符号デコーダ８Ａを介してワークメモリ
９Ａ上で元のビットデータに復元されると、該ビットデ
ータはデータ入出力手段３Ａに転送され、出力される
（ステップ６ｂ〜ステップ７ｂ）。

【００４０】（実施の形態２）次に、本発明の実施の形
態２におけるデータ符号化復号化装置について説明す
る。

【００４１】図８は上記実施の形態２のデータ符号化復
号化装置を示す概略構成図であり、前記実施の形態１の
データ符号化復号化装置の再配置手段１０Ａが、この実
施の形態２では再配置マップデータベース１２Ａとキー
ボード１１Ａとに置き換えられている。尚、図１の場合
と同様、実線矢印は処理の流れを、また、白線矢印はビ
ットデータの流れを示す。

【００４２】上記再配置マップデータベース１２Ａは再
配置マップ保持手段として、複数種類の再配置マップ１
０Ｍを複数備えており、上記キーボード１１Ａは再配置
マップ指定手段として、上記複数の再配置マップの何れ
を使用するかを指定する。この再配置マップ指定手段と
しては、ユーザーが指定できる手段であれば、上記キー
ボード１１Ａに限定されるものではなく、例えばタッチ
パネルに上記再配置マップを名称、番号等で表示して、
ユーザに選択させるようにしてもよい。

【００４３】上記実施の形態２のデータ符号化復号化装
置におけるビットデータの符号化の手順について、図９
のフローチャートを参照して説明する。

【００４４】なお、図９のステップ１ｃからステップ４
ｃまでの手順は、図２で説明した実施の形態１のデータ
符号化復号化装置の場合（図２ステップ１ａ〜ステップ
５ａ参照）と同じであるため、その説明を省略する。

【００４５】この実施の形態２のデータ符号化復号化装
置では、例えば図１０や図１１に示すようなブロックの
方向が異なる複数の再配置マップを再配置マップデータ
ベース１２Ａに備えており、ユーザーは、発生しやすい
直線状ノイズの向きを考慮して、上記複数の再配置マッ
プのなかから、どの再配置マップを基にビット配列を実
行するかを選択し、キーボード１１Ａを介してその再配
置マップを指定する（ステップ６ｃ〜ステップ５ｃ）。

【００４６】この指定に基づいて、２次元画像生成手段
６Ａでワーキメモリ９Ａ上の２次元画像のビット再配列
が実行される（ステップ６ｃ）。そのときの直線状ノイ
ズの向きとビットデータの配列方向との関係を、図１０
と図１１をもとに説明する。

【００４７】図７に示すような、ブロック単位でのエラ
ー訂正に用いられるリードソロモン符号方式のエラー訂
正は、ハミング符号方式のエラー訂正に比べてエラー訂
正にかかる処理時間が長い。よって、処理時間を短くす
るためには、先ずハミング符号方式でエラー訂正してで
きるだけエラービットの数を少なくしてからリードソロ
モン符号方式のエラー訂正を実行する。

【００４８】したがって、上記ハミング符号方式でのエ
ラー訂正が有効に作用するように、すなわちブロック内
で多数のビットが破壊される状態が発生しないように、
ブロックの長さ方向とノイズの方向が異なる再配置マッ
プ１０Ｍを選ぶ。

【００４９】このような手順を採用した場合に、上記再
配置マップ１０Ｍの選択は以下のようにノイズの発生す
る方向によって決定される。

【００５０】例えば、プリンタ機器などで２次元画像を
印刷する時には、図１０に示すようにローラーの汚れな
どの原因により、用紙排出方向と同方向の直線状ノイズ
Ｎ１がでやすい。その時には、ブロックＢｋの長さ方向
が図１０に示す上記ノイズＮ１と直交するような方向、
すなわちブロックＢｋの長さ方向が列方向のドット配置
になる再配置マップを選ぶ。

【００５１】また、ファクシミリ装置などを経由して２
次元画像を印刷する場合には、図１１に示すように通信
エラーが発生するとこのエラーを黒ラインあるいは白ラ
インとして印刷することが行われ、この黒ラインあるい
は白ラインは用紙排出方向と垂直な方向に直線状ノイズ
Ｎ３として現れることが多くなる。その時には、同図に
示すように、ブロックＢｋの長さ方向が上記直線状ノイ
ズＮ３と直交する方向、すなわちブロックＢｋの長さ方
向が行方向のドット配置になる再配置マップを選ぶ。

【００５２】尚、上記図１０、図１１の場合と異なって
傾斜したノイズが発生することも考えられるが、図１２
に示すように、ブロックＢｋを構成するビットデータを
該ノイズＮ３と直交するように傾斜して配置する再配置
マップを採用することができる。

【００５３】更に、上記図１０、図１１に示す２つの状
態を同時に満足する方法として、ビットデータを用紙排
出方向に斜めに配列することも考えられる。このように
作成された２次元画像はプリンタ１Ａに送られ、紙など
の媒体に２次元画像として印刷される（ステップ７
ｃ）。

【００５４】なお、この実施の形態２のデータ符号化復
号化装置におけるビットデータの復号化の動作について
は、上記実施の形態１で図３を参照して説明した内容と
同じであるため、その説明を省略する。

【００５５】ただし、この実施の形態２のデータ符号化
復号化装置では、図９のフローチャートのステップ５ｃ
において、最も出現頻度の高い向きの直線状ノイズに対
して、ランダム誤り訂正よりエラー訂正に時間のかかる
バースト誤り訂正を避けるべくキーボード１１Ａを通じ
て再配置マップを選択しているので、短いデコード時間
でデコードできる可能性が高まることになる。

【００５６】（実施の形態３）図１３は本発明の第３の
実施の形態によるデータ符号化復号化装置の構成を示す
ブロック図であり、この装置におけるビットデータの符
号化の構成について図１４のフローチャートを参照して
説明する。尚、図１の場合と同様、実線矢印は処理の流
れを、また、白線矢印はビットデータの流れを示す。

【００５７】図１で説明したと同様、データ入出力手段
３Ａより入力された所定数、例えば１６ビットのビット
データは、ワークメモリ９Ａに入力され、ここで以下に
説明する処理がなされる（ステップ１ｄ）。

【００５８】上記のようにワークメモリ９Ａにビットデ
ータが入力されると、パターン検出手段１５Ａが起動
し、該パターン検出手段１５Ａは用紙の方向と該用紙に
印字された行の方向の関係（行方向が用紙の長い方向か
短い方向か）を示す方向パターンを検出し、その検出結
果を符合化方式組合せ決定手段１４Ａに渡す。符合化方
式組合せ決定手段１４Ａは上記方向パターンに基づい
て、ビットデータを符号化するときに、後述する符号化
方式の内どの符号化方式をどのような順序で組み合わせ
て用いるのかを決定する（ステップ２ｄ）。

【００５９】なお、パターン検出手段１５Ａで検出する
上記方向パターンは、用紙の方向と行方向の関係に限ら
ず、特定の使用環境でのノイズパターンを検出してもよ
いし、ユーザが経験やマニュアルに基づいて判断した結
果を反映してもよい。本実施の形態では、組み合わせる
符号化方式としてハミング符号、リードソロモン符号、
ＢＣＨ符号（Bose/Chaudhuri/Hocquengen 符号）の３種
類を用意する。

【００６０】これらのうち、ハミング符号とＢＣＨ符号
はランダム誤り訂正符号に分類され、リードソロモン符
号はバースト誤り訂正符号に分類される。そして以下の
説明ではハミング符号、リードソロモン符号、ＢＣＨ符
号の順に適用してビットデータを符号化する場合を例と
して説明する。

【００６１】なお、用意する符号化方式は上記３種類に
限定されるのでなく、それ以上の種類の符号化方式を用
いてもよく、また用意した符号化方式の全種類を使用す
るのでなく、状況に応じて必要な種類の符号化方式を使
用するようにしてもよい。また、例えばハミング符号、
ＢＣＨ符号、ハミング符号の順に符号化するように、同
じ符号化方式を何度使ってもよい。更に、符号方式組合
せ決定手段１４Ａでは、符号化方式の組合せを上記のよ
うにパターン検出手段１５Ａの検出した方向パターンに
依存して組み合わせを決定するのではなく、あらかじめ
決められた組み合わせと順序に従うようにしてもよい。

【００６２】この実施の形態では、上記のようにワーク
メモリ９Ａにあるビットデータに対して、まず、上記符
号方式組合せ決定手段１４Ａ決定した組合せの１番目の
符号化方式であるハミング符号化方式が実行される。こ
こでは（８．４）ハミング符号化方式を用いることと
し、上記ビットデータにハミング符号を付加する手順に
ついては本発明の実施の形態１と同様であるので、説明
を省略する。

【００６３】このように、上記ハミング符号エンコーダ
４Ａによってビットデータにハミング符号（ランダム誤
り訂正ビット）が付加されると、リードソロモン符号エ
ンコーダ５Ａが起動して、リードソロモン符号が付加さ
れる。この手順についても本発明の実施の形態１と同様
であるので、説明を省略する（ステップ１ｄ〜ステップ
５ｄ）。

【００６４】以上のように、上記リードソロモン符号エ
ンコーダ５Ａによってバースト誤り訂正ビットを付加さ
れたビットデータは、ＢＣＨ符号エンコーダ１６Ａ（こ
こでは（１６．１５）ＢＣＨ符号化方式を用いる場合を
例とする）に渡される。

【００６５】上記ＢＣＨ符号エンコーダ１６Ａは、図１
５に示した上記各８ビットのビットデータのブロックＲ
ａ〜Ｒｈの中、ブロックＲａとブロックＲｃに含まれる
ビット、合計１６ビット、更に該１６ビットに対する１
５ビットのパリティブロックαを生成し付与して塊Σα
とする。同様にブロックＲｂとＲｄのビットとそれに対
応するパリティブロックβとよりなる塊Σβ、ブロック
ＲｅとＲｇのビットとそれに対応するパリティブロック
γとよりなる塊Σγ、ブロックＲｆとＲｈのビットとそ
れに対応するパリティブロックδとよりなる塊Σδを生
成する（ステップ５ｄ）。このＢＣＨ符号化方式を適用
したエラー訂正能力は、上記３１ビットからなる一つの
塊のなかの３ビットの誤りまで訂正することができる。

【００６６】このように複数種類の誤り訂正符号が付加
されたビットデータは２次元画像生成手段６Ａに渡され
る（ステップ６ｄ）。この２次元画像生成手段６Ａで
は、図１６（ｂ）に示す再配置手段１０Ａとしての再配
置マップ１０Ｍに、従って、上記ビットデータを図１６
（ｃ）に示すように配列し、２次元コードを生成する
（ステップ７ｄ）。

【００６７】なお、図１６（ｂ）、（ｃ）において、ａ
〜ｈは上記ブロックＲａ〜Ｒｈを意味し、該ａ〜ｈに対
になっている１〜８は１ブロック内でのビットデータの
順番を表している。更にα〜δはパリティブロックを意
味し、該α〜δに対になっている１〜８は上記パリティ
ブロックα〜δ内でのビットデータの順番を表してい
る。

【００６８】このようにして生成された２次元コードは
プリンタ１Ａに入力され、紙などの媒体に２次元コード
画像として印刷される（ステップ８ｄ）。

【００６９】次に、上記実施の形態３のデータ符号化復
号化装置におけるビットデータの復号化の動作について
図１７のフローチャートを参照して説明する。

【００７０】上記のように紙などの媒体に印刷された２
次元コード画像は、スキャナ２Ａで読み込まれてワーク
メモリ９Ａに入力される（ステップ１ｅ）。

【００７１】マップ配置復元処理手段１３Ａは、上記の
ようにワークメモリ９Ａに入力されたビットデータに対
して、上記２次元画像生成手段６Ａが使用したのと同じ
再配置マップ１０Ｍを基にして、上記並べ替える前の元
のビットデータに復元する（ステップ２ｅ）。

【００７２】パターン検出手段１５Ａは上記のようにワ
ークメモリ９Ａ上で復元されたビットデータに基づいて
方向パターンを検出し、その内容を符号化方式組合せ決
定手段１４Ａに通知する。この通知を受けた符号化方式
組合せ決定手段１４Ａでは、組み合わされている符号化
方式とその使用の順番を決定するようになっている（ス
テップ３ｅ）。ここで決定された順番に従って、以下に
説明するように各デコーダが起動し、ビットデータを復
号していく。今回の例では上記順番をハミング符号、リ
ードソロモン符号、ＢＣＨ符号の順と仮定し、マップ配
置復元処理手段１３Ａで本来の状態に配列されたビット
データを、まず、ハミング符号デコーダ７Ａに渡すこと
になる（ステップ４ｅ）。

【００７３】ここで、もし図１８に示すように、２次元
コード画像上にまとまった面積を占めるノイズＮ４がの
っている場合、８ビットから構成される１つの訂正集合
（誤り訂正符号を含むビットの集合：ここではブロック
Ｒ）のうち、ブロックＲｃ（ビットｃ１〜ｃ８）、ブロ
ックＲｄ（ビットｄ１〜ｄ８）、及びブロックＲｅ（ビ
ットｅ１〜ｅ８）の３つのブロックＲではノイズＮ４に
よって壊されるビットはそれぞれ２ビットであるため、
上記ハミング符号デコーダ７Ａがランダム誤り訂正機能
でエラービットを訂正することはできない（ステップ５
ｅ−２：ステップ５ｅ−１参照）。

【００７４】次に、ビットデータはリードソロモン符号
デコーダ８Ａに渡され、ここでバースト誤り訂正処理が
される（ステップ６ｅ）。しかし、図１８に示すよう
に、２次元コード画像上にまとまった面積を占めるノイ
ズＮ４が残っている場合、リードソロモン符号化方式か
ら見た訂正単位のブロックＲのうち、ブロックＲｃ，Ｒ
ｄ，Ｒｅの３ブロックが壊されていて、この例で使用し
ている２ブロックまで訂正可能というリードソロモン符
号化方式の性能を越えてビットデータが壊されている。
よってここでもエラービットを訂正することはできない
（ステップ７ｅ−２：ステップ７ｅ−１参照）。

【００７５】次に、ビットデータはＢＣＨ符号デコーダ
１７Ａに渡され、ここで訂正処理される（ステップ８
ｅ）。ここでの訂正は、図１９に示すようにＢＣＨ符号
方式からみた３１ビット（ａ１〜ａ８、α１〜α８、ｃ
１〜ｃ８、α９〜α１５）を上記一つの塊Σ（ここでは
Σα）とみた場合に、この塊Σαのなかにエラービット
が３ビット以下であるので、エラービットを訂正するこ
とが可能である（ステップ９ｅ）。

【００７６】このように、ハミング符号デコーダ７Ａと
リードソロモン符号デコーダ８ＡとＢＣＨ符号デコーダ
１７Ａを介して元のビットデータが復元され、データ入
出力手段３Ａに転送され、出力される（ステップ１０ｅ
〜ステップ１１ｅ）。

【００７７】なお、実施の形態２の場合と同様に、上記
実施の形態３において再配置マップを複数種用意し、ノ
イズの発生方向などを考慮してユーザがキーボード等に
より適切な再配置マップを選択できるようにすることも
できる。また、再配置マップはここで例示した配置順序
のものに限らず、規定の２次元領域内の任意の配列順序
を採用することができる。

【００７８】以上、本発明の各実施の形態ににおいて、
上記再配置マップを省略して、ハミング符号エンコーダ
４Ａまたはリードソロモン符号エンコーダ５Ａから転送
されたビットデータをそのまま２次元画像生成手段６Ａ
で２次元画像とすることも可能である。

【００７９】また、本願出願人は、スキャナ等の画像入
力手段より入力した文書画像に対応する画像データを画
像ファイルとして内蔵の磁気ディスク等へ記憶し、この
ように記憶した画像ファイルを再びプリンタ等より印刷
できる画像情報処理装置を提案している。これによれ
ば、上記２次元コードを上記文書画像の特定ページに印
刷して、この２次元コードに基づいて上記のように記憶
された文書画像を特定することも可能である。

【００８０】更に、以上の説明では２次元コードを例と
して説明を行ったが、本発明の適用される２次元画像は
２次元コードに限られず、ビットデータの集合を符号化
することによって得られる２次元画像一般を含んでい
る。

【００８１】

【発明の効果】以上説明したように、本発明はランダム
誤り訂正符号方式とバースト誤り訂正符号方式の２種類
のエラー訂正方式をもちいてビットデータを符号化し復
号化している。このため、ランダム符号化したビットデ
ータの集合の長さ方向のノイズに対しては上記バースト
誤り訂正符号が作用し、またバースト符号化したビット
データのブロックを複数にわたり貫通するノイズに対し
ては上記ランダム誤り訂正符号が作用する。従って、２
次元画像上にどの向きのノイズがのっても、エラー訂正
能力を確実に働かせることが可能である。また複数のラ
ンダム誤り訂正符号、バースト誤り訂正符号を用いるこ
とで、より複雑な形状のノイズに対してもエラー訂正を
行うことができる。

【００８２】さらに、上記ノイズの向きに応じてビット
データの再配置マップを作成し、あるいはどの向きの直
線状ノイズが２次元画像上にのりやすいかによって再配
置マップを変更することが可能である。これにより、上
記ビットデータのブロックの方向とノイズの方向とが交
差するようにして、訂正時間の速いランダム誤り訂正符
号方式を優先的に利用できる。従って、エラー訂正時間
を含めたデコード処理時間を最小にすることが可能であ
る。

【図面の簡単な説明】

【図１】本発明の実施の形態１のデータ符号化復号化装
置を示す構成図である。

【図２】実施の形態１のデータ符号化復号化装置におけ
るデータ符号時のフローチャートである。

【図３】実施の形態１のデータ符号化復号化装置におけ
るデータ復号時のフローチャートである。

【図４】実施の形態１のデータ符号化復号化装置におけ
るビットデータの符号化手順を示す説明図である。

【図５】実施の形態１のデータ符号化復号化装置におけ
る２次元画像上でのドットの再配置仕様を示す説明図で
ある。

【図６】各ブロックを横切る方向に直線状ノイズがのっ
た場合の例を示す図である。

【図７】１ブロックと同方向に直線状ノイズがのった場
合の例を示す図である。

【図８】本発明の実施の形態２のデータ符号化復号化装
置を示す構成図である。

【図９】実施の形態２のデータ符号化復号化装置実施に
おけるデータ符号時のフローチャートである。

【図１０】用紙排出方向と同じ向きの直線状ノイズがの
った場合の再配置マップの仕様を示す図である。

【図１１】用紙排出方向と垂直な向きの直線状ノイズが
のった場合の再配置マップの仕様を示す図である。

【図１２】用紙に対してビットデータを斜めに配置する
再配置マップの仕様を示す図である。

【図１３】本発明の実施の形態３のデータ符号化復号化
装置を示す構成図である。

【図１４】実施の形態３のデータ符号化復号化装置実施
におけるデータ符号時のフローチャートである。

【図１５】ＢＣＨ符号化におけるビットデータの符号化
手順を示す説明図である。

【図１６】実施の形態３のデータ符号化復号化装置にお
ける２次元画像上でのドットの再配置仕様を示す説明図
である。

【図１７】実施の形態３のデータ符号化復号化装置にお
けるデータ復号時のフローチャートである。

【図１８】まとまった面積を占めるノイズがのった場合
の例を示す図である。

【図１９】ＢＣＨ符号による誤り訂正の説明図である。

【図２０】リードソロモン符号方式で誤り訂正機能を付
加する際の説明図である。

【図２１】ハミング符号方式で誤り訂正機能を付加する
際の説明図である。

【符号の説明】

１Ａプリンタ２Ａスキャナ３Ａデータ入出力手段４Ａハミング符号エンコーダ５Ａリードソロモン符号エンコーダ６Ａ２次元画像生成手段７Ａハミング符号デコーダ８Ａリードソロモン符号デコーダ９Ａワークメモリ１０Ａ再配置手段１０Ｍ再配置マップ１１Ａキーボード１２Ａ再配置マップデータベース１３Ａマップ配置復元処理手段１４Ａ符号化方式組合せ決定手段１５Ａパターン検出手段１６ＡＢＣＨ符号エンコーダ１７ＡＢＣＨ符号デコーダ

フロントページの続き (72)発明者山口岳人大阪府門真市大字門真1006番地松下電器産業株式会社内 (72)発明者桑野秀之大阪府門真市大字門真1006番地松下電器産業株式会社内 (72)発明者岡田雄治大阪府門真市大字門真1006番地松下電器産業株式会社内 (72)発明者高橋直樹大阪府門真市大字門真1006番地松下電器産業株式会社内 (72)発明者田中丈二大阪府門真市大字門真1006番地松下電器産業株式会社内

Claims

【特許請求の範囲】

【請求項１】任意のビットデータの集合に対して、少
なくとも１種の誤り訂正符号を付加して符号化する第１
の符号化手段と、上記第１の符号化手段により符号化されたビットデータ
の集合に対して、少なくとも１種の誤り訂正符号を付加
して符号化する第２の符号化手段と、上記第１及び第２の符号化手段によって符号化したビッ
トデータを規定２次元領域に行列状に配列して２次元画
像を生成するマーク生成手段とを備えることを特徴とす
る、データ符号化装置。
【請求項２】上記第１の符号化手段がランダム誤り訂
正符号を付加するランダム符号化手段であり、上記第２
の符号化手段がバースト誤り訂正符号を付加するバース
ト符号化手段である、請求項１に記載のデータ符号化装
置。
【請求項３】上記第１の符号化手段がバースト誤り訂
正符号を付加するバースト符号化手段であり、上記第２
の符号化手段がランダム誤り訂正符号を付加するランダ
ム符号化手段である、請求項１に記載のデータ符号化装
置。
【請求項４】上記２次元画像を媒体に印刷する２次元
画像印刷手段を備える、請求項１に記載のデータ符号化
装置。
【請求項５】上記第１及び第２の符号化手段によって
符号化したビットデータを並べ替える順番を示した再配
置マップと、上記再配置マップに基づいて、上記符号化したビットデ
ータを２次元領域上に再配置し上記マーク生成手段に渡
す再配置手段とを備える、請求項１に記載のデータ符号
化装置。
【請求項６】上記ランダム誤り訂正符号を付加したと
きのビットデータの集合を、上記規定２次元領域内の行
または列のいずれか一方向に並べて配置する上記再配置
マップを備える、請求項２に記載のデータ符号化装置。
【請求項７】上記バースト誤り訂正符号を付加したと
きのビットデータの集合を、上記規定２次元領域内の行
または列のいずれか一方向に並べて配置する上記再配置
マップを備える、請求項３に記載のデータ符号化装置。
【請求項８】上記複数種の再配置マップを保持した再
配置マップ保持手段と、上記再配置手段で使用する再配置マップを選択する再配
置マップ指定手段とを備え、上記再配置マップ指定手段が、最も頻発するビットエラ
ーの方向と、上記ビットデータの集合の長さ方向とが交
差する再配置マップを選択する、請求項５に記載のデー
タ符号化装置。
【請求項９】第１の符号化手段と第２の符号化手段に
よって、それぞれ少なくとも１種の誤り訂正符号を付加
して符号化したビットデータを基に印刷された２次元画
像を読み込んで、ビットデータに変換する２次元画像読
み込み手段と、第１の符号化手段によって誤り訂正符号を付加されたビ
ットデータの集合に対して、誤り訂正と復号とを行う第
１の復号化手段と、第１の符号化手段によって誤り訂正符号を付加されたビ
ットデータの集合に対して、誤り訂正と復号とを行う第
２の復号化正手段とを備えることを特徴とする、データ
復号化装置。
【請求項１０】上記第１の復号化手段がランダム誤り
訂正符号に基づいて誤り訂正と復号とを行うランダム復
号化手段であり、上記第２の復号化手段がバースト誤り
訂正符号に基づいて誤り訂正と復号とを行うバースト復
号化手段である、請求項９に記載のデータ復号化装置。
【請求項１１】上記第１の復号化手段がバースト誤り
訂正符号に基づいて誤り訂正と復号とを行うバースト復
号化手段であり、上記第２の復号化手段がランダム誤り
訂正符号に基づいて誤り訂正と復号とを行うランダム復
号化手段である、請求項９に記載のデータ復号化装置。
【請求項１２】上記２次元画像読み込み手段の後段
に、上記読み込んだ２次元画像を、ビットデータの符号
化後の並べ替えの順番を示した再配置マップに基づい
て、並び替え前のビットデータに変換するマップ配置復
元処理手段を設けた、請求項９に記載のデータ復号化装
置。