Задача: растровый центроид

Question

Я бы хотел вычислить центр тяжести растрового изображения (черно-белого), хранящегося в виде битового массива целых чисел.Я знаю, что существуют быстрые алгоритмы для подсчета количества установленных бит в целом числе, но это не помогает мне вычислить центроид.Любые идеи?

Например, если мое растровое изображение выглядит следующим образом:

111000
111000
111000
000000
000000
000000

Центр тяжести равен 1, 1. Упакован в 32-битные целые числа (вы выбираете Endian), этоможет выглядеть так: {ширина: 6, высота: 6} {3817734144, 0}.

Бонусные баллы, если вы также можете получить массу (в примере 9), не повторяя каждый бит.

Answer 1

Давайте предположим, что вы собираетесь обрабатывать эту строку одновременно.(Как только вы получите общую массу и центр масс каждой строки, это средневзвешенное значение для получения координат x и y центроида).

Другими словами, у вас есть строкабитов b _i и вы хотите вычислить сумму b _i f (i) для некоторых функций f.Если f (i) = 1, это число битов (назовем это C), а если f (i) = i, это даст суммарный момент массы M (которую вы будетеделим на C, чтобы получить центр масс.)

Для входных данных менее 8 бит вы можете легко хранить таблицы для C и M, каждый шириной 256 байтов.Запишем числа больше 8 бит как h: l, где l - младшие 8 бит числа, а h - остальные биты.

Тогда

C(h:l) = C(h:0) + C(0:l) = C(h) + C(l)
M(h:l) = M(h:0) + M(0:l) = M(h) + 8C(h) + M(l)

единственноехитрым битом является 8C (h), что соответствует сдвигу этих битов C (h) на 8 позиций, когда мы вычислили M (h) вместо M (h: 0).

не рекурсивно, если вашвведите как байт - это x0, x1, x2, x3 ...

C(x) = C(x0) + C(x1) +   C(x2) +   C(x3) + ...
M(x) = M(x0) + M(x1) +   M(x2) +   M(x3) + ...
             +8C(x1) + 16C(x2) + 24C(x3) + ...

, а затем вы можете передать M и C для усреднения по всем строкам.