У меня есть картина:
размер 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
}
}
}
И да, время важно (вот почему я не хочу получать пиксель более миллиона раз). Любые идеи?
Ответ 1 · рейтинг 5 · Gabe
Подобно алгоритму поиска строк Бойера-Мура, если элемент, который вы ищете, at не является частью того, что вы ищете, вы можете пропустить весь размер того, что вы ищете. В вашем случае вы можете проверить, является ли данный пиксель черным. Если это не так, вы можете пропустить вперед 50 пикселей. Если это так, у вас есть небольшая коробка для поиска вашего черного квадрата.
Впрочем, в этом случае вам может и не понадобиться ничего столь сложного. Я предполагаю, что если ваш алгоритм слишком медленный, это потому, что вы вызываете функцию GetPixel миллион раз, и это медленная часть. Если вы сможете превратить свои пиксели в двумерный массив, ваш алгоритм, вероятно, будет работать достаточно быстро, чтобы его не нужно было переписывать.
Предполагая, что вы используете System.Drawing.Bitmap, ознакомьтесь с LockBits документацией. небольшой пример, который включает копирование растрового изображения в одномерный массив для сверхбыстрого доступа.
Ответ 2 · рейтинг 2 · Matthew Scharley
Если вы ищете только квадрат определенного размера, вы можете оптимизировать это, сканируя только каждую 50-ю строку (или столбец) пикселей, тем самым значительно сократив свою рабочую нагрузку.
Теоретически вам нужно проверять наличие черного/белого только в 1 пикселе из каждого блока 50x50. Если он черный, то вы пытаетесь распространить оттуда, если он белый, то просто переходите к следующему блоку: очевидно, что в этом блоке есть белый пиксель, поэтому здесь нет черного ящика. После этого вы уже сократили свою работу до 1/2500 от того, что было изначально, теперь вы сначала проверяете только 400 пикселей.
Обычно лучшая оптимизация, особенно при первоначальной разработке алгоритма, заключается в сокращении проделанной работы, а не в повышении ее эффективности. Попробуйте придумать творческие способы уменьшения ввода до более удобного размера.
