Простой алгоритм для обрезки пустых границ изображения с помощью кода?

В настоящее время я ищу довольно быстрый и разумно точный алгоритм в С#/. NET, чтобы сделать эти шаги в коде:

Загрузите изображение в память.
Начиная с цвета в позиции (0,0), найдите незанятое пространство.
Отбросьте это ненужное пространство.

Я проиллюстрировал, чего я хочу достичь:

То, что я могу себе представить, - это получить цвет пикселя в (0,0), а затем сделать несколько строк unsafe по очереди/по столбцу, проходящим через все пиксели, до тех пор, пока я не встречу пиксель с другим цвет, затем отрезать границу.

Я просто боюсь, что это действительно очень медленно.

Итак, мой вопрос:

Знаете ли вы о каких-либо быстрых алгоритмах (в идеале без каких-либо сторонних библиотек), чтобы вырезать "пустые" границы из образа/растрового изображения в памяти?

Боковое примечание. Алгоритм должен быть "разумным, точным", а не на 100% точным. Некоторое терпение, подобное одной линии слишком много или слишком мало обрезанных, будет в порядке.

Дополнение 1:

Я только что завершил реализацию моего алгоритма грубой силы самым простым способом. Посмотрите код на Pastebin.com.

Ответ 1

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

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

Конечно, надеюсь, что вы не это патегологический случай с шириной 1 пиксель в центре изображения:) Или двойной патологический случай отключенных объектов на вашем изображении, так что все изображение центрировано, но ничто не пересекает диагональ,

Одно улучшение, которое вы могли бы сделать, - дать вашему "цвету удара" некоторый допуск (возможно, возможно?)

Ответ 2

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

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

начинайте с центральной линии (0, длина /2) и начинайте в одном направлении за раз, исследуйте линии, как в двоичном поиске.

сделайте это для всех сторон.

это уменьшит сложность до log n до базы 2

Ответ 3

Во-первых, ваш текущий алгоритм в основном является наилучшим.

Если вы хотите, чтобы он работал быстрее, вы можете закодировать его на С++. Это, как правило, более эффективно, чем управляемый небезопасный код.

Если вы остаетесь в С#, вы можете использовать параллельные расширения для запуска на нескольких ядрах. Это не уменьшит нагрузку на машину, но уменьшит задержку, если таковая имеется.

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

Ответ 4

Во-первых, вы можете преобразовать растровое изображение в byte[] с помощью LockBits(), это будет намного быстрее, чем GetPixel(), и вам не потребуется идти unsafe.

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

Двоичный поиск может улучшить крошечный бит, но это не так уж важно, поскольку это может спасти вам линию поиска по каждому направлению в лучшем случае.

Ответ 5

Хотя я предпочитаю ответ Таранга, я хотел бы дать несколько советов о том, как "изолировать" объекты в изображении, ссылаясь на заданный цвет переднего плана и фона, который называется "сегментация" и используется при работе в поле "оптического контроля", где изображение не просто обрезано каким-либо обнаруженным объектом, но объекты подсчитываются и также измеряются, то, что вы можете измерить на объекте, это область, контур, диаметр и т.д.

Прежде всего, вы начнете действительно проецировать свое изображение, начиная с координат x/y 0,0, и идти слева направо и сверху вниз, пока не найдете пиксель, который имеет другое значение как задний план. Чувствительность сегментации определяется путем определения значения оттенков серого в фоновом режиме, а также значения оттенков серого на переднем плане. Возможно, вы пройдете через изображение, как сказано, по координатам, но из просмотра программ вы просто пройдете через массив пикселей. Это означает, что вам придется иметь дело с формулой, которая вычисляет координату x/y для индекса пикселя в массиве пикселей. Эта формула обязательно требует ширины и высоты изображения.

Для вашей заботы об урожае, я думаю, что когда вы нашли так называемую "опорную точку" вашего объекта переднего плана, вы обычно будете ходить по найденному объекту, используя формулу, которая обнаруживает соседние пиксели одного и того же значения foregeground, Если есть только один объект для обнаружения, как в вашем случае, легко хранить эти координаты пикселей, наиболее северные, восточные, самые южные и западные. Эти 4 координаты отмечают прямоугольник, в котором находится ваш объект. С помощью этой информации вы можете рассчитать ширину и высоту новых изображений (обрезанное изображение).