連続する数値を検出するアルゴリズムを教えてください

Question

はじめに

いつもお世話になっています。
表題の件について質問があります。

C言語でQRコードを実装しているのですが、その実装の一部にマスクの失点を計算する処理があります。
簡単に言いますと、「黒と白で構成されているQRコードにおいて同じ色が連続で続くと良くないので、
その様なパターンを減点してより点数の高いパターンを採用する」と言う処理です。

処理そのものの実装は全く難しくないのですが、連続するモジュールの算出方法を少し簡単に出来ないかな？
と思い質問しました。

#define WHITE_MODULE (0x00)	// この値を変える事で分かりやすくなるなら変更してもOK
#define BLACK_MODULE (0xFF)	// この値を変える事で分かりやすくなるなら変更してもOK
typedef unsigned char BYTE;
int ErrPointLine(BYTE *pQRdata, int version)
{
    int Eret=0; /* エラーポイント */
//  int line_max = _qr_code_info[version].side_module_num;
    int line_max = 40;  // 暫定で 40 固定

    // 列
    for( int h=0 ; h < line_max ; h++ ){
        int blacks = 0;
        int whites = 0;
        const BYTE *pHead = pQRdata + (line_max * h);
        for(int n=0 ; n < line_max ; n++ ){
            BYTE LineCol = *(pHead + n);

            if(LineCol == BLACK_MODULE){
                blacks++;
                whites=0;
            }
            else if(LineCol == WHITE_MODULE){
                blacks=0;
                whites++;
            }
            
            // 同色が5つ続くなら+3の失点
            if(blacks == 5 || whites == 5){
                Eret += 3;
            }
            else if(blacks > 5 || whites > 5){
                // 以後続くたびに+1の失点
                Eret++;
            }
        }
    }
    printf("Total Error Point = %d\n", Eret);

    return Eret;
}

良い知恵がありましたらぜひ教えてください。

Answer 1

こんにちは。

大差ないですが、私はこのような時次のようなアルゴリズムで実装します。

• 最後の状態を記録する変数を１つ設ける：現在の行の先頭値で初期化
• カウンタを１つ設ける：1で初期化
• 行の先頭の次から行の最後までループ
• 最後の状態と現在の値が同じなら、＋＋カウンタ

そうでないなら、カウンタ=1

• カウンタの値に応じた処理

---

【追記】
ソースを書ける方なら分かってくれるかなと思って手抜きしました。
下記イメージです。（コンパイルしてませんのでエラーがでたら悪しからず。）
列数が0の時は異常動作します。現在は列数=行数=line_maxですが、もし列数と行数を異なるパラメータにする時はパラメータ・チェックが必要です。

#define WHITE_MODULE (0x00)    // この値を変える事で分かりやすくなるなら変更してもOK
#define BLACK_MODULE (0xFF)    // この値を変える事で分かりやすくなるなら変更してもOK
typedef unsigned char BYTE;
int ErrPointLine(BYTE *pQRdata, int version)
{
    int Eret=0; /* エラーポイント */
//  int line_max = _qr_code_info[version].side_module_num;
    int line_max = 40;  // 暫定で 40 固定

    // 列
    for( int h=0 ; h < line_max ; h++ ){
        int counter= 1;
        const BYTE *pHead = pQRdata + (line_max * h);
        BYTE last = *pHead;
        for(int n=1 ; n < line_max ; n++ ){
            BYTE LineCol = *(pHead + n);

            if(LineCol == last ){
                counter++;
            }
            else {
                last=LineCol;
                counter=1;
            }

            // 同色が5つ続くなら+3の失点
            if(counter == 5){
                Eret += 3;
            }
            else if(counter> 5){
                // 以後続くたびに+1の失点
                Eret++;
            }
        }
    }
    printf("Total Error Point = %d\n", Eret);

    return Eret;
}

Comments

[kuma_dansyaku]

回答ありがとうございます。

申し訳ありません。
自分の知識不足でどうやればいいのか理解できませんでした。

回答して頂いたのに申し訳ありませんでした。

[WoodenHamlet]

質問者さんのソースにおける blacks, whites を、「別に分ける必要ないよね」という視点からの回答だと思います。
直前の色と同じ→カウントアップ
直前の色と違う→カウントクリア
とすれば、「同じ色が何度つづいた」を知ることができるということですね

[kuma_dansyaku]

なるほどわかりました。
ありがとうございます。

ヒントを頼りに自己解決に書いた解釈で良かったとみたいですね。
補足ありがとうございました。

Answer 2

XOR(排他的論理和)を使って前後が同じかどうかを判定する様に変更しました。

// 列
for( int y=0 ; y < line_max ; y++ ){
    const BYTE *pHead = pQRdata + (line_max * y);  // 1ライン毎の先頭アドレス
    for(int x=1 , cnt=1; x < line_max ; x++ ){
        if( pHead[x-1]^pHead[x] ){
            cnt=1;
            continue;
        }
        cnt++;
        // 同色が5つ続くなら+3の失点
        if(cnt == 5){
            Eret += 3;
        }
        else if(cnt > 5){
            // 以後続くたびに+1の失点
            Eret++;
        }
    }
}