Нахождение центра масс на двумерном растровом изображении

Question

Я кодирую игру, и я хотел бы иметь возможность найти центр масс произвольной формы на черно-белом растровом изображении, например:

 012345678
0.XX......
1..XXX....
2...XXX...
3..XXXXXXX
4...XXX...

Все "клетки" имеют одинаковый вес. Соседние по диагонали ячейки не считаются связанными, и форма всегда будет одиночной, поскольку до этого она уже разделялась другой функцией.

Он будет использоваться только для изображений с достаточно низким разрешением (возможно, не более 50х50) и не должен быть сверхточным, скорость предпочтительна.

У меня такое чувство, что есть правильный способ сделать это, но я не знаю, зачем искать Google.

Я кодирую это в ActionScript 3, но примеры на любом языке приветствуются, особенно если они созданы для понимания людьми.

РЕДАКТИРОВАТЬ: не стесняйтесь предполагать, что данные хранятся в любой структуре данных, которую вы считаете наиболее удобным для вашего примера. Я использую растровые изображения, но двумерные массивы или даже один массив тоже подойдут!

РЕДАКТИРОВАТЬ: Это код, который я в конечном итоге использовал, скорее всего, это может быть сделано быстрее, но я считаю, что это очень читабельно:

// _bmp is a private BitmapData instance
public function getCenterOfMass():Point {
    var avg     :Point  = new Point(0, 0);
    var points  :uint   = 0;

    for (var ix:uint = 0; ix < _bmp.width; ix++) {
        for (var iy:uint = 0; iy < _bmp.height; iy++) {
            if (_bmp.getPixel(ix, iy) == ACTIVE_COLOR) {
                avg.x += ix;
                avg.y += iy;
                points++;
            }
        }
    }

    avg.x /= points;
    avg.y /= points;

    return avg;
}

Answer 1

Как насчет этого алгоритма (псевдо-кода) на основе булевой матрицы, как в вашем примере:

xSum = 0
ySum = 0
points = 0

for point in matrix
    if point is marked
        xSum += pointX
        ySum += pointY
        points++

return (xSum/points, ySum/points)

Ничего слишком сложного, посчитайте, где X больше всего, то же самое для Y, разделите на количество очков, которые вы подсчитали, и вы получите центр масс. Вы можете еще больше усложнить это, придав определенным точкам разный вес при усреднении, но это должно быть вашим основным направлением.

---

Этот вопрос заставил меня задуматься о расширении этого вопроса, на которое я не смог найти хорошего ответа. Я разместил вопрос здесь: Поиск кластеров массы в матрице / растровом изображении

Answer 2

Вы можете посчитать количество соседних ячеек, а затем сосредоточиться на ячейках с наибольшим количеством соседей.

 012345678
0 XX      |
1  XXX    |
2   XXX   |
3  XXXXXXX|
4   XXX   |

 012345678
0 23      |
1  454    |
2   775   |
3  3686421|
4   454   |

В этом примере вы можете использовать единственную ячейку с 8 в качестве центральной точки.

Если вы получили несколько ячеек с одинаковым количеством соседей, вы просто снова запустите процедуру подсчета, но на этот раз только с ячейками с большим числом.

Например, давайте представим, что у ячеек, которые имели 6, 7 и 8, вместо всех было восемь соседей.

 012345678
0 23      |
1  454    |
2   885   |
3  3888421|
4   454   |

 012345678
0 --      |
1  ---    |
2   XX-   |
3  -XXX---|
4   ---   |

 012345678
0 --      |
1  ---    |
2   34-   |
3  -342---|
4   ---   |

 012345678
0 --      |
1  ---    |
2   -X-   |
3  --X----|
4   ---   |

В случае простой связи я бы выбрал ту, которая была ближе к центру. В этом случае это будет верхний из двух.

Примечание: я предполагаю, что вы не используете это для точного моделирования физики.

Answer 3

В зависимости от характера вашего интерпретатора actionscript и предварительной обработки фигур, вы можете увидеть улучшение скорости (по сравнению с прямым подходом, указанным Ювалом), первоначально создав вторую копию растрового изображения / массива, отраженного по диагонали затем с помощью функций манипулирования строками или строками суммируйте точки в каждой строке и столбце за один шаг. Это будет O (2m n) вместо O (n n) [см. Ниже], но с дополнительными издержками.

xSum = 0
ySum = 0
points = 0

for row in matrix
  ySum += rowX * countpoints(row)
  points += countpoints(row)
for row in mirroredmatrix
  xSum += rowX * countpoints(row)

return (xSum/points, ySum/points)

Где countpoints () подсчитывает количество точек подряд. Это основывается на точках подсчета (у которых O (n) время выполнения), имеющих меньший постоянный множитель, чем время выполнения наивного подхода (следовательно, выше, «m» - время выполнения точек подсчета, а «n» - время для интерпретатора, чтобы пройти через строку ). Характер countpoints () зависит от вашего метода хранения, который может включать подсчет символов в строке или битов в битовом поле.