C # Сканирование изображения для определенного блока

Question

У меня есть картинка:

размером 1000x1000 белого цвета со случайными черными точками.(Он может содержать черный квадрат (размер 50x50))

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

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

        for (int i = 0; i < pic.Width; i++)
        {
            for (int j = 0; j < pic.Height; j++)
            {
                if (pic.GetPixel(i, j) == Color.Black)
                {
                    //Search for the entire square at that area
                }
            }
        }

И да, время важно (вот почему я не хочуполучить пиксель более миллиона раз).Есть идеи?

Answer 1

Как и алгоритм поиска строк Бойера-Мура , если элемент, который вы просматриваете, не является частью того, что вы ищете, вы можете пропустить весь размер того, что вы ищете. В вашем случае вы можете проверить, является ли данный пиксель черным. Если это не так, вы можете пропустить 50 пикселей вперед. Если это так, у вас есть небольшая коробка для поиска вашего черного квадрата.

Однако в этом случае вам может не понадобиться ничего сложного. Я предполагаю, что если ваш алгоритм слишком медленный, это потому, что вы вызываете функцию GetPixel миллион раз, а , что - медленная часть. Если вы можете поместить свои пиксели в двумерный массив, ваш алгоритм, вероятно, будет работать достаточно быстро, чтобы его не нужно было переписывать.

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

Answer 2

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

Теоретически, вам нужно только проверять наличие черного / белого в 1 пикселе из каждого блока 50x50. Если он черный, то вы пытаетесь распространяться оттуда, если он белый, тогда просто переходите к следующему блоку: ясно, что в этом блоке есть белый пиксель, поэтому здесь нет черного поля. После этого вы уже сократили свою работу до 1/2500-й по сравнению с тем, что было изначально, теперь вы сначала проверяете только 400 пикселей.

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

Answer 3

ознакомьтесь с пакетом фреймворков AForge.net. Он имеет библиотеку изображений с Blob и поиск по шаблону. Вы можете искать формы тоже. Это бесплатно.

Вы можете найти его здесь http://www.aforgenet.com/framework/

Вот ссылка, которая перечисляет функции

http://www.aforgenet.com/framework/features

Редактировать

Вот пример для проверки формы. Я использовал Aforge в прототипе, и он работал для меня.

http://www.aforgenet.com/articles/shape_checker/