CODE39 デコーダーの実装方法について調べてみた

# CODE39 デコードについて

CODE39 の技術的な事はこちらを参照: https://www.keyence.co.jp/ss/products/autoid/codereader/basic_code39.jsp

「黒 白 黒 白 黒 白 黒 白 黒」の 9 つのバーの幅 (大小) によってキャラクタが決まります。

`*` で始まり `*` で終わります。パターンは `■□□■□■■□■■□■`

![2020-03-19_21h53_27.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/364126/1b6947e9-69e5-24d3-20c0-42c235fdc0d9.png)

皆さん一体どうやってこんなモノをデコードしているんでしょう。

zbar を使っているのですが、
zbar では認識できず ZXing.Net では認識できるバーコードがあります。

デコーダーの実装に、どのような差異があるのでしょうか…?

## zbar: code39.c

code39.c に出てくる横幅はだいたい約 32 倍された数字になっています。

9 つのバー幅が確定するとキャラクタの判定に移ります。

```txt
      code39: s=1345 001010010 i=0e chk=52 c=2b/19 dir=0 [valid start]
```

- `s=1345` は、9 つのバーの全長です。
- `001010010` は、バーの右側から見て 0=小 1=大 で表現します。

この大小判定がまたややこしい。

```
    decode[0]: w=0 (0)
    decode[1]: w=128 (4)
      code39: s=128 
    decode[2]: w=224 (7)
    decode[3]: w=97 (3.03125)
      code39: s=449 1
    decode[4]: w=96 (3)
    decode[5]: w=223 (6.96875)
      code39: s=768 
    decode[6]: w=97 (3.03125)
    decode[7]: w=287 (8.96875)
      code39: s=1152 1010010
    decode[8]: w=97 (3.03125)
    decode[9]: w=96 (3)
      code39: s=1345 001010010 i=0e chk=52 c=2b/19 dir=0 [valid start]
```

- `unsigned e` は `w=128` などの整数です。
- `unsigned s` は `s=1345` です。

```c
static inline unsigned char code39_decode1 (unsigned char enc,
                                            unsigned e,
                                            unsigned s)
{
    unsigned char E = decode_e(e, s, 72);
    if(E > 18)
        return(0xff);
    enc <<= 1;
    if(E > 6) {
        enc |= 1;
        dbprintf(2, "1");
    }
    else
        dbprintf(2, "0");
    return(enc);
}

/* fixed character width decode assist
 * bar+space width are compared as a fraction of the reference dimension "x"
 *   - +/- 1/2 x tolerance
 *   - measured total character width (s) compared to symbology baseline (n)
 *     (n = 7 for EAN/UPC, 11 for Code 128)
 *   - bar+space *pair width* "e" is used to factor out bad "exposures"
 *     ("blooming" or "swelling" of dark or light areas)
 *     => using like-edge measurements avoids these issues
 *   - n should be > 3
 */
static inline int decode_e (unsigned e,
                            unsigned s,
                            unsigned n)
{
    /* result is encoded number of units - 2
     * (for use as zero based index)
     * or -1 if invalid
     */
    unsigned E = ((e * n * 2 + 1) / s - 3) / 2;
    return((E >= n - 3) ? -1 : E);
}
```

素人判断なのでアレですが、全長の 10% (正確には 7 ÷ 72 か?) を越えると「大」とみなされるようです。

この組み合わせで一致するキャラクタがなければ、デコード・エラーになります。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/364126/a76ed159-cecc-1a7b-5d87-9d57a2d97b5d.png)

1 行目は 300 dpi のモノクロでスキャンしたバーコード
2 行目は 9 本のバーの全長
3 行目は太いと判断する長さ

バーコードの文字列は `*$D` です。
この判定方法では 2 文字目でエラーになります。
`$` はすべて「細い黒バー」なのに、5 ピクセルの「太い黒バー」が混じっていると判定されるからです。

## ZXing.Net: Code39Reader.cs

ざっと見た感じ、9 つのバーを絞り込むまでは同じっぽいです。

`toNarrowWidePattern` の実装が肝で、インテリジェントに感じました。

```csharp
        // For efficiency, returns -1 on failure. Not throwing here saved as many as 700 exceptions
        // per image when using some of our blackbox images.
        private static int toNarrowWidePattern(int[] counters)
        {
            int numCounters = counters.Length;
            int maxNarrowCounter = 0;
            int wideCounters;
            do
            {
                int minCounter = Int32.MaxValue;
                foreach (var counter in counters)
                {
                    if (counter < minCounter && counter > maxNarrowCounter)
                    {
                        minCounter = counter;
                    }
                }
                maxNarrowCounter = minCounter;
                wideCounters = 0;
                int totalWideCountersWidth = 0;
                int pattern = 0;
                for (int i = 0; i < numCounters; i++)
                {
                    int counter = counters[i];
                    if (counter > maxNarrowCounter)
                    {
                        pattern |= 1 << (numCounters - 1 - i);
                        wideCounters++;
                        totalWideCountersWidth += counter;
                    }
                }
                if (wideCounters == 3)
                {
                    // Found 3 wide counters, but are they close enough in width?
                    // We can perform a cheap, conservative check to see if any individual
                    // counter is more than 1.5 times the average:
                    for (int i = 0; i < numCounters && wideCounters > 0; i++)
                    {
                        int counter = counters[i];
                        if (counter > maxNarrowCounter)
                        {
                            wideCounters--;
                            // totalWideCountersWidth = 3 * average, so this checks if counter >= 3/2 * average
                            if ((counter << 1) >= totalWideCountersWidth)
                            {
                                return -1;
                            }
                        }
                    }
                    return pattern;
                }
            } while (wideCounters > 3);
            return -1;
        }
```

大の幅のバーがちょうど 3 つになるまで、小の幅のバー判定を緩くして行く様です。
念のため… 黒く太いバーが 3 本、ではなく、白く太いバーも含めて合計 3 本です。

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/364126/f7977e44-9cb4-22c4-e054-636ae9f03b65.png)

この方法であれば 2 文字目も何とかギリギリ… 太いバー 3 本の判定ができました。