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

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

размер 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
                }
            }
        }

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


image c# pixel
person user779444    schedule 21.07.2011    source источник

Ответы (3)


arrow_upward
5
arrow_downward

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

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

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

person Gabe    schedule 21.07.2011
comment
+1 за признание того, что на этот раз микрооптимизация - это то, что нужно :) - person Blindy; 21.07.2011
comment
Поэтому я должен создать 2 массива, используя бит блокировки: все изображение 1000x1000 и черный квадрат 50x50. И я просто проверю, содержит ли массив изображений массив черных квадратов 50x50? - person user779444; 23.07.2011
comment
@user: вам нужно создать массив только для изображения 1000x1000, потому что вы знаете, что другое изображение полностью черное. И вы не можете искать один массив внутри другого, потому что блок пикселей 50x50 не будет непрерывным в блоке пикселей 1000x1000. - person Gabe; 23.07.2011
comment
Есть ли способ преобразовать его в 2D-массив? - person user779444; 23.07.2011
comment
@user: вы можете преобразовать его в 2D-массив, но вам это не нужно. Вы можете просто изменить каждый вызов GetPixel(i, j) на что-то вроде array[i + j * stride], хотя точная формула будет зависеть от вашего формата растрового изображения. - person Gabe; 23.07.2011
comment
Что делать, если изображение стрелки не сплошное черное? А если стог сена, если полноцветное изображение, а иголка - это полноцветное изображение? Как бы вы реализовали метод Бойера-Мура (-Хорспул) в двумерном пространстве? - person mikew; 17.02.2013
comment
@mikew: Это гораздо более сложные вопросы. Вы должны задавать их как два или более отдельных вопроса. - person Gabe; 17.02.2013

arrow_upward
2
arrow_downward

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

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

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

person Matthew Scharley    schedule 21.07.2011

arrow_upward
1
arrow_downward

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

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

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

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

Изменить

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

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

person Pinakin Shah    schedule 21.07.2011
comment
Хотя ссылка выглядит круто, это должен быть комментарий, а не ответ, потому что из чтения страниц, на которые вы ссылаетесь, не очевидно, как это помогает решить проблему. - person Gabe; 21.07.2011
comment
Это готовая библиотека, которая избавит его от изобретения велосипеда. Я не уверен, почему это не ответ? Конечно, ему нужно немного покопаться, поскольку ни один из опубликованных ответов не является полным. - person Pinakin Shah; 21.07.2011
comment
Хороший ответ не просто содержит ссылку на инструмент, но и говорит как использовать этот инструмент для решения проблемы. Ссылка на пример очень помогает. - person Gabe; 21.07.2011