Как реализовать быстрое большинство голосов для битовой матрицы - PullRequest
Новая
       39

Как реализовать быстрое большинство голосов для битовой матрицы

0 голосов
/ 23 октября 2018

У меня есть представление большой битовой матрицы, где я хотел бы эффективно извлечь мажоритарный бит для каждого столбца матрицы (^ = битовое значение, которое встречается чаще всего).Фоном является то, что строки матрицы представляют дескрипторы объектов ORB, а искомое значение напоминает среднее значение в области Хемминга.

Реализация, с которой я сейчас работаю, выглядит следующим образом 

  // holds column-sum for each bit
  std::vector<int> sum(32 * 8, 0);

  // cv::Mat mat is a matrix of values € [0, 255] filled elsewhere
  for (size_t i = 0; i < mat.cols; ++i)
  {
    const cv::Mat &d = mat.row(i);
    const unsigned char *p = d.ptr<unsigned char>();

    // count bits set column-wise
    for (int j = 0; j < d.cols; ++j, ++p)
    {
      if (*p & (1 << 7)) ++sum[j * 8];
      if (*p & (1 << 6)) ++sum[j * 8 + 1];
      if (*p & (1 << 5)) ++sum[j * 8 + 2];
      if (*p & (1 << 4)) ++sum[j * 8 + 3];
      if (*p & (1 << 3)) ++sum[j * 8 + 4];
      if (*p & (1 << 2)) ++sum[j * 8 + 5];
      if (*p & (1 << 1)) ++sum[j * 8 + 6];
      if (*p & (1))      ++sum[j * 8 + 7];
    }
  }

  cv::Mat mean = cv::Mat::zeros(1, 32, CV_8U);
  unsigned char *p = mean.ptr<unsigned char>();

  const int N2 = (int)mat.rows / 2 + mat.rows % 2;
  for (size_t i = 0; i < sum.size(); ++i)
  {
    if (sum[i] >= N2)
    {
      // set bit in mean only if the corresponding matrix column
      // contains more 1s than 0s
      *p |= 1 << (7 - (i % 8));
    }

    if (i % 8 == 7) ++p;
  }

Узким местом является большая петля со всем смещением битов.Есть ли способ или известная немного магии, чтобы сделать это быстрее?

...