色数計算の高速化

　ビットマップの色数計算のプログラムは、色数を数えるのに時間がかかるため色が増えてくると実用的とは言い難いものでした。そこで、今回はもっと高速な方法を考えてみる事にします。

フラグによる画像の色数計算

　今回は、フルカラーの2²⁴色それぞれに「フラグ」を用意します。つまり、2²⁴個のフラグを用意して、表れた色をそこに記録して行く事で色の数を数えるわけです。例えば、フラグ配列をf[2²⁴]とすると、表れた色clに対応するf[cl]を１にする事になります。このようにしてフラグを立てて行くと、最後に立っているフラグの個数で色がわかる事になるでしょう。
　単純に考えて、Byte配列fColors[2²⁴]をフラグ配列とすると、ビットマップlpBMP（dwWidth×dwHeight）の色数を数える関数は以下のようになります。

  DWORD count(void) { /* ビットマップ内のに対する色数を数える */

      DWORD i,j,dwCount=0,dwPixel=0;
      LPBYTE fColors;

      /* フラグ配列用メモリを確保 */
      fColors=GlobalAlloc(GPTR,256*256*256);

      for (i=0;i<dwHeight;i++)
          for (j=0;j<dwWidth;j++) {

              /* (j,i)の色をdwPixelに３２ビットで格納 */
              CopyMemory(&dwPixel,lpBMP+j*3+i*dwLength,3);

              /* フラグのdwPixel番を検査 */
              if (fColors[dwPixel]==0) {

                  /* フラグのdwPixel番を立てる */
                  fColors[dwPixel]=1;
                  dwCount++; /* 色数カウンタ更新 */

              }

          }

      GlobalFree(fColors);

      return dwCount;

  }

　ただ、考えてみるとフラグは「あるかないか」だけですから、１ビットで良いんですね。上のプログラムは、実に１６ＭＢものメモリを取っていますが、本当に必要なのは１６ＭＢｉｔ、と。フラグを立てる時にも、何バイト目ではなく何ビット目、という指定をすれば良いでしょう。
　では、フラグのｎビット目をフラグ配列で探すにはどうすれば良いのでしょうか。フラグ配列はByte型なので、一つ８ビットでした。ですから、まずｎビット目のフラグはｎ÷８バイト目にある事になり、さらにｎ÷８バイト目のｎ mod ８（ｎを８で割った余り）ビット目がフラグのｎビットに対応する事になります。
　フラグ内のあるビットが立っている、という事はそのビットだけを１にした数値との論理積が０でない、という事と同値である点に注意すれば、バイト型フラグ配列（ってのも変な表現ですが。要するに連続したフラグ領域ですね）fColorsのｎビット目が立っているかを調べる判定文は以下のようになるでしょう。

　if ((fColors[n/8] & (1 << (n % 8))==0)

　色を数える時は、まず対応するフラグを見てこの色が出てきているかを調べます。そして、もしこれまでに出てきた事がなければ、フラグを立てて色数カウンタを増やします。

  DWORD count(void) { /* ビットマップ内の色数を数える */

      DWORD i,j,dwBit,dwByte,dwCount=0,dwPixel=0;
      LPBYTE fColors;

      fColors=GlobalAlloc(GPTR,256*256*32);

      for (i=0;i<dwHeight;i++)
          for (j=0;j<dwWidth;j++) {

              /* (j,i)の色をdwPixelに３２ビットで格納 */
              CopyMemory(&dwPixel,lpBMP+j*3+i*dwLength,3);

              /* dwPixelビット目の位置を計算 */
              dwByte=dwPixel/8;
              dwBit=dwPixel%8;

              /* フラグ領域のdwPixelビット目を検査 */
              if ((fColors[dwByte] & (1 << dwBit))==0) {

                  /* フラグ領域のdwPixelビット目を立てる */
                  fColors[dwByte]=fColors[dwByte]|(1 << dwBit);
                  dwCount++; /* 色数カウンタ更新 */

              }

          }

      GlobalFree(fColors);

      return dwCount;

  }

プログラム

プログラムソース表示

　２４ビットフルカラービットマップをウインドウにドラッグ＆ドロップするか「読み込み」ボタンで読み込むと、そのビットマップ内の色数を数えてウインドウのタイトルバーに表示します。速度的には、ほぼ問題はないでしょう。メモリも２ＭＢ使いますが、少なくとも今のパソコンなら問題にならないですね。