Блог

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

Подсчет уникальных пикселей в нарисованном изображении фигур

#c# #algorithm #graphics

#c# #алгоритм #графика

Вопрос:

Я работаю над графическим приложением, в котором пользователь может рисовать на холсте любое количество линий (с некоторой толщиной от точки A до точки B), прямоугольников или эллипсов.

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

Мой наивный алгоритм заключается в реализации формы bool.Содержит (x, y) для каждой фигуры и вызывает его для каждой нарисованной фигуры для каждого пикселя изображения, чтобы определить, был ли этот пиксель нарисован линией, прямоугольником или эллипсом.

Работая другим способом, я мог бы создать пустую форму.Установите пиксели (bool[,] canvas) и установите для каждой фигуры значение true, для каждого пикселя, который она содержит. Это то, что я на самом деле реализовал, и с большими наборами данных это происходит мучительно медленно.

У меня такое чувство, что есть более прямой способ перейти от необработанных данных формы к нужному мне результату без проверки каждого пикселя. Итак, мой вопрос заключается в том, учитывая набор данных формы, существует ли O (n) функция bool[,] IsColored(int x, int y) {}, которая может генерировать матрицу истинных / ложных значений для цветных пикселей более непосредственно, чем любая из идей, которые я дал?

Комментарии:

1. Что, если вы его нарисуете? Результирующее растровое изображение по сути является такой матрицей

2. Что вы подразумеваете под O (n)? Реализация формы. Содержит (x, y) и вызывает его один раз для каждой фигуры — O (n), где n — количество фигур.

3. Почему форма не может просто вернуть набор пикселей, который она содержит?

4. Какая часть вашей SetPixels(bool[,]) версии «мучительно медленная»? Конечно, не поиск — он создает массив значений bool? В этом случае вам могут просто понадобиться лучшие алгоритмы рендеринга для ваших фигур.

5. Одно предупреждение: методы GetPixel and SetPixel в Bitmap классе работают чертовски медленно. Вам нужно использовать прямой низкоуровневый доступ, если вы хотите работать с более чем несколькими пикселями.

Ответ №1:

Избегайте этого Bitmap.GetPixel метода. Это очень, очень медленно. Если возможно, ваш низкоуровневый доступ к растровым данным с LockBits помощью или аналогичных методов.

В одном из моих проектов я использовал:

 public void LoadFromBitmap(Bitmap bmp)
    {
        if (bmp.Width != Width || bmp.Height != Height)
            throw new ArgumentException("Size missmatch");
        unsafe
        {
            BitmapData bmpData = null;
            try
            {
                bmpData = bmp.LockBits(new System.Drawing.Rectangle(0, 0, bmp.Width, bmp.Height), ImageLockMode.ReadOnly, PixelFormat.Format32bppArgb);

                for (int y = 0; y < bmpData.Height; y  )
                {
                    uint* p = (uint*)((byte*)bmpData.Scan0   y * bmpData.Stride);
                    for (int x = 0; x < bmpData.Width; x  )
                    {
                        this[x, y] = RawColor.FromARGB(*p);
                        p  ;
                    }
                }
            }
            finally
            {
                if (bmpData != null)
                    bmp.UnlockBits(bmpData);
            }
        }
    }

https://github.com/CodesInChaos/ChaosUtil/blob/master/Chaos .Image/Pixels.cs

Другой оптимизацией является реализация пула для вашего пикселя, содержащего массивы. По моему опыту, частое выделение объектов в куче больших объектов очень сильно подчеркивает gc.

Ответ №2:

Два метода, о которых вы говорите, обычно являются вашими двумя основными вариантами. Либо проверяйте каждый пиксель по мере необходимости, либо заранее создайте какую-то структуру данных для быстрого поиска.

Если у вас большой холст, но только несколько фигур (таким образом, относительно мало «включенных» пикселей), то, возможно, лучше всего просто записывать каждый пиксель, на который попадает любая фигура, например, в хэш.

 HashSet<KeyValuePair<int,int>> listOfPixelsHitByAnyShape = new HashSet()

foreach(Shape s in allShapes)
{
    s.Draw(listOfPixelsHitByAnyShape); // will update listOfPixelsHitByAnyShape
}

// Now we can easily query if a pixel is set
bool isSet = listOfPixelsHitByAnyShape.Contains(new KeyValuePair(10,99))

Это должно быть быстрым для поиска, за счет памяти и времени для создания HashSet.

Но это будет не так быстро, как ваша SetPixels(bool[,] canvas) версия, и не будет использовать столько памяти (в редком случае, о котором мы говорим).

Ответ №3:

Если вы не используете графическую библиотеку, пожалуйста, пожалуйста, сделайте это!

Если это графическое приложение, предположительно, вы уже рисуете то, что вводит пользователь. Разве вы не можете просто запросить это? Вы всегда можете использовать 2 разные цели: одну для версии pretty user, а другую для запроса (каждый объект имеет уникальный цвет).

Как вы хотите справиться с перекрытиями?

О каком большом наборе данных мы говорим? Рендеринг должен быть «бесплатным», поскольку растровое изображение может быть построено по мере рисования пользователем в приложении.

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