HN 日本語サマリー

← 一覧へ戻る
プログラミング

OCR向けリード・ソロモン符号:汚れた印刷コードのための誤り訂正

Reed-Solomon for OCR: error correction for messy printed codes (github.com)

6 pointsby chasangchual2 コメント

要約

このプロジェクトは、印刷されたコード、クーポン、ID、ラベルなどのOCRを最適化する誤り訂正機能を提供します。OCRが記号を誤読した場合でも、リード・ソロモン符号の誤り訂正能力の範囲内であれば、元のメッセージを検出・修正することができます。特に、ドットマトリックスプリンターやインク切れのプリンターなど、印刷環境が理想的でない場合にOCRの信頼性を向上させるのに役立ちます。

全文翻訳

Reed-SolomonによるOCR

概要

このプロジェクトは、印刷されたコード、クーポン、ID、ラベル向けの、OCRに最適化されたエラー訂正機能を提供します。

目標は、Reed-Solomon ECC(誤り訂正符号)とOCRセーフなパリティテキストを備えたコンパクトなコードを印刷することです。OCRが1つ以上のシンボルを誤読した場合、デコーダーはスキャンされたコードが無効であることを検出し、どのシンボル位置に不整合があるかを特定し、エラー数が設定されたReed-Solomonの制限内であれば元のメッセージを訂正できます。

これは、印刷環境が理想的でない場合に特に役立ちます。例としては、ピンが欠けているドットマトリックスプリンター、インクが切れかかっているリボン、低解像度の印刷、汚れが付着しやすいラベル、またはOCRが読み取る前に印刷された文字が部分的に損傷する可能性のあるワークフローなどが挙げられます。

スキャン品質が十分に良好で、OCRの誤りが訂正能力を超えないと仮定すれば、制御された印刷コードのワークフローにおいてOCRの信頼性を100%に近づけることができます。

Reed-Solomonエラー訂正

ReedSolomonForOcr は GF(256) 上の Reed-Solomon を実装しています。

  • シンボルサイズ: 8ビット
  • 最大コードワード長: 255シンボル
  • エンコード形式: メッセージ + パリティ
  • 訂正能力: 最大 floor(nsym / 2) 個の未知のシンボルエラー

例えば、nsym=10 は10個のパリティシンボルを追加し、最大5個の未知のシンボルエラーを訂正できます。

通常のバイト指向APIは、0..255 の範囲の整数シンボルで動作します。

from importlib.util import module_from_spec, spec_from_file_location

spec = spec_from_file_location("reed_solomon_ocr", "reed-solomon-ocr.py")
module = module_from_spec(spec)
spec.loader.exec_module(module)

ReedSolomonForOcr = module.ReedSolomonForOcr

rs = ReedSolomonForOcr(nsym=10)
message = ReedSolomonForOcr.bytes_to_symbols(b"HELLO-123")

codeword = rs.encode(message)
is_valid = rs.check(codeword)
decoded = rs.correct(codeword)

assert is_valid
assert decoded == message

OCRセーフな文字

OCRの誤りは、しばしば似た文字の間で発生します。文字セットを縮小して混乱を避ける場合、似た文字のグループから最も区別しやすい文字を選択してください。

推奨される英数字の選択肢:

  • 0 と O の場合: どちらも保持しない。0 と O の両方を削除する。
  • 1, I, l の場合: 数字の 1 のみ保持する。大文字の I と小文字の l を削除する。
  • 2 と Z の場合: 数字の 2 を保持する。大文字の Z を削除する。
  • 5 と S の場合: 数字の 5 を保持する。大文字の S を削除する。
  • 8 と B の場合: 数字の 8 を保持する。大文字の B を削除する。
  • 6 と G の場合: 数字の 6 を保持する。大文字の G を削除する。
  • V と U の場合: 大文字の U を保持する。大文字の V を削除する。

最終的なセーフ文字リスト:

  • セーフな数字: 2 3 4 5 6 7 8 9
  • セーフな文字: A C D E F H J K L M N P Q R T U W X Y

コーデックはこのOCRセーフアルファベットをパリティテキストに使用します。

23456789ACDEFHJKLMNPQRTUWXY

Reed-SolomonシンボルはGF(256)バイトであるため、1つのパリティバイトを1つのOCRセーフ文字に収めることはできません。実装では、各パリティバイトを2つのOCRセーフ文字としてエンコードします。

使用方法

OCRセーフパリティでのエンコード
rs = ReedSolomonForOcr(nsym=10)
message = ReedSolomonForOcr.bytes_to_symbols(b"HELLO-123")

message_symbols, safe_parity = rs.encode_with_ocr_safe_parity(message)

print(message_symbols)
print(safe_parity)

両方を印刷または保存します。

  • message_symbols: 元のメッセージシンボル
  • safe_parity: OCRセーフなパリティ文字
OCRセーフパリティからのコードワード再構築
codeword = rs.codeword_from_ocr_safe_parity(message_symbols, safe_parity)
assert rs.check(codeword)
OCRセーフパリティによる破損メッセージの訂正
corrupted_message = message_symbols[:]
corrupted_message[0] ^= 0x55

decoded = rs.correct_with_ocr_safe_parity(corrupted_message, safe_parity)

assert decoded == message
バイトヘルパー
symbols = ReedSolomonForOcr.bytes_to_symbols(b"ABC123")
data = ReedSolomonForOcr.symbols_to_bytes(symbols)
互換性ラッパー関数

モジュールはラッパー関数も公開しています。

codeword = module.rs_encode_msg(message, nsym=10)
decoded = module.rs_correct_msg(codeword, nsym=10)

message_symbols, safe_parity = module.rs_encode_msg_with_ocr_safe_parity(message, nsym=10)
decoded = module.rs_correct_msg_with_ocr_safe_parity(message_symbols, safe_parity, nsym=10)

デモとテストの実行

python3 main.py
python3 -m unittest -v