Оптимизация L oop больших точек в большом облаке точек - PullRequest
Новая
       38

Оптимизация L oop больших точек в большом облаке точек

0 голосов
/ 13 апреля 2020

Все, что у меня есть следующая реализация линии, определяющей преобразование Хафа для облаков точек (набор точек в 3-х пространствах) 

internal sealed class LineHoughTransform : ILineHoughTransform
{
    private readonly double _dX;
    private readonly double _maxX;

    private readonly long _countX;
    private readonly long _countB;

    private readonly IDiscreetSphere _sphere;

    public LineHoughTransform(Vector3 minParameterVector, Vector3 maxParameterVector, double dX, int sphereGranularity)
    {
        _dX = dX;

        _sphere = new Icosahedron();
        _sphere.Create(sphereGranularity);

        _countB = _sphere.Points.Count;
        _maxX = Math.Max(maxParameterVector.Norm(), minParameterVector.Norm());

        var rangeX = 2 * _maxX;
        if (_dX == 0.0)
            _dX = rangeX / 64.0;

        _countX = (long)(rangeX / _dX).RoundToNearest();

        VotingSpace = new Dictionary<long, int>();
    }

    public int GetLine(ref Vector3 a, ref Vector3 b)
    {
        int votes = 0;
        long index = 0;

        foreach (var storedVote in VotingSpace)
        {
            if (storedVote.Value > votes)
            {
                votes = storedVote.Value;
                index = storedVote.Key;
            }
        }

        // Retrieve x' coordinate from VotingSpace[_countX * _countX * _countB].
        double x = index / (_countX * _countB);
        index -= (long)(x * _countX * _countB);
        x = x * _dX - _maxX;

        // Retrieve y' coordinate from VotingSpace[_countX * _countX * _countB].
        double y = index / _countB;
        index -= (long)y * _countB;
        y = y * _dX - _maxX;

        // Retrieve directional vector and Compute anchor point according to Eq. (3).
        b = _sphere.Points[(int)index];

        a.X = (float)(x * (1 - ((b.X * b.X) / (1 + b.Z))) - y * ((b.X * b.Y) / (1 + b.Z)));
        a.Y = (float)(x * (-((b.X * b.Y) / (1 + b.Z))) + y * (1 - ((b.Y * b.Y) / (1 + b.Z))));
        a.Z = (float)(-x * b.X - y * b.Y);

        return votes;
    }

    public void Add(IPointCloud pointCloud)
    {
        CastVote(pointCloud, true);
    }

    public void Subtract(IPointCloud pointCloud)
    {
        CastVote(pointCloud, false);
    }

    private void CastVote(IPointCloud pointCloud, bool add)
    {
        if (pointCloud == null || pointCloud.Vertices == null)
            return;

        foreach (var vertex in pointCloud.Vertices)
            PointVote(vertex.Point, add);
    }

    private void PointVote(Vector3 point, bool add)
    {
        // Loop over directions B.
        for (int j = 0; j < _sphere.Points.Count; ++j)
        {
            // Denominator in Eq. (2).
            Vector3 b = _sphere.Points[j];
            double beta = 1 / (1 + b.Z);

            // Compute x' and y' according to Eq. (2).
            double newX = ((1 - (beta * (b.X * b.X))) * point.X) - (beta * (b.X * b.Y) * point.Y) - (b.X * point.Z);
            double newY = (-beta * (b.X * b.Y) * point.X) + ((1 - (beta * (b.Y * b.Y))) * point.Y) - (b.Y * point.Z);

            long x_i = (long)((newX + _maxX) / _dX).RoundToNearest();
            long y_i = (long)((newY + _maxX) / _dX).RoundToNearest();

            // Compute one-dimensional index from three indices.
            // x_i * <number of planes> * <number of direction vectors> + y_i * <number of direction vectors> + <loop index>
            long index = (x_i * _countX * _countB) + (y_i * _countB) + j;

            if (!VotingSpace.ContainsKey(index))
                VotingSpace.Add(index, 0);

            if (add)
                VotingSpace[index]++;
            else
                VotingSpace[index]--;
        }
    }

    public Dictionary<long, int> VotingSpace { get; private set; }
}

Я хотел бы улучшить скорость этого кода, поэтому я попытался использовать 

public ConcurrentDictionary<long, int> VotingSpace { get; private set; }

с 

private void CastVote(IPointCloud pointCloud, bool add)
{
    if (pointCloud == null || pointCloud.Vertices == null)
        return;

    Parallel.ForEach(pointCloud.Vertices, vertex => PointVote(vertex.Point, add));
}

Обратите внимание, что pointCloud в CastVote может содержать огромное количество точек, и увеличение VotingSpace становится 

if (!VotingSpace.ContainsKey(index))
    VotingSpace.TryAdd(index, 0);

if (add)
    VotingSpace[index]++;
else
    VotingSpace[index]--;

Однако иногда TryAdd дает сбой, вызывая сбой моего алгоритма вызова. Я попытался повторить попытку на TryAdd, но это не помогло решить проблему пропущенных индексов. Как я могу сделать этот класс оптимально многопоточным, максимально простым и работать точно так же, как и оригинал?

1 Ответ

1 голос
/ 14 апреля 2020

При работе с одновременными коллекциями вы обычно используете специальные API Atomi c, которые они предлагают. В этом случае вам, вероятно, следует использовать метод ConcurrentDictionary.AddOrUpdate: 

VotingSpace.AddOrUpdate(index,
    addValueFactory: (key) => add ? 1 : -1,
    updateValueFactory: (key, existingValue) => existingValue + (add ? 1 : -1));
...