Здравствуйте!

Очень интересует используемый алгоритм при реализации инструмента "Magic Wand" в Adobe Photoshop.
Смысл в том, что при указании начальной точки и заданным параметром "Tolerance" программа выделяет область изображения со схожими цветами.

Видел несколько статей, но это не совсем то, что нужно.
Скажем, в этой статье:
http://www.losingfight.com/blog/2007/08/28/how-to-implement-a-magic-wand-tool/
...описан довольно очевидный способ, основанный на алгоритме "flood fill", по которому рекурсивно (или другим способом) для данной точки заданного цвета выбираются соседние по горизонтали и вертикали, отвечающие какому-то условию.

Но при реализации лично я не смог добиться хорошего результата. Дело в том, что, взяв для эксперимента jpg-изображение, не смог добиться хорошего результата — либо не выделяется ожидаемая область целиком, либо выделяется много лишнего).
Для тестирования использовал файл:
здесь

Ожидаю (по крайней мере Photoshop справляется с задачей), что окажется выделе "зеленый" круг.

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

Здравствуйте, MitjaT, Вы писали:

MT>Здравствуйте!

MT>Очень интересует используемый алгоритм при реализации инструмента "Magic Wand" в Adobe Photoshop.
MT>Смысл в том, что при указании начальной точки и заданным параметром "Tolerance" программа выделяет область изображения со схожими цветами.
MT>Видел несколько статей, но это не совсем то, что нужно.
MT>Скажем, в этой статье:
MT>http://www.losingfight.com/blog/2007/08/28/how-to-implement-a-magic-wand-tool/
MT>...описан довольно очевидный способ, основанный на алгоритме "flood fill", по которому рекурсивно (или другим способом) для данной точки заданного цвета выбираются соседние по горизонтали и вертикали, отвечающие какому-то условию.
MT>Но при реализации лично я не смог добиться хорошего результата. Дело в том, что, взяв для эксперимента jpg-изображение, не смог добиться хорошего результата — либо не выделяется ожидаемая область целиком, либо выделяется много лишнего).

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

MT>Для тестирования использовал файл:
MT>здесь
MT>Ожидаю (по крайней мере Photoshop справляется с задачей), что окажется выделе "зеленый" круг.
MT>Подскажите, пожалуйста, где можно почитать про использованный алгоритм?

Возьми любой open source графический редактор, тот же GIMP, а можно и старые версии paint.net, ну или любой другой более-менее известный, и посмотри, как это делается там.

Здравствуйте, MitjaT, Вы писали:

MT>Здравствуйте!

MT>Очень интересует используемый алгоритм при реализации инструмента "Magic Wand" в Adobe Photoshop.
MT>Смысл в том, что при указании начальной точки и заданным параметром "Tolerance" программа выделяет область изображения со схожими цветами.
MT>Ожидаю (по крайней мере Photoshop справляется с задачей), что окажется выделе "зеленый" круг.

Не знаю как сделано в Photoshop. Но предположу вот что:
1. Цветовая модель RGB не сильно подходит для "волшебной палочки". Более подходящей возможно будет HSV. Там, например, учитывается яркость тона. В статье же предложен достаточно грубый алгоритм вычисляния "цветового расстояния" между точками. О чем там собственно и написано.
2. В статье точки, выбираемые палочкой, определяются при сравнении с некой начальной точкой — выбранной пользователем. Возможно, в графических программах используется сравнение с близлежащими точками. Т.е. цвета точек, которые попадут в маску, могут достаточно сильно отличаться от начальной точки, однако переход к ним должен быть плавным.
3. Также, возможно, перед применением "волшебной палочки" картинка проходит какие-то фильтры, например, слабое размытие, чтобы различные шумы на картинке не влияли на результат.

В простейшем случае можно попробовать перейти к HSV и на основе этой модели выбрать подходящую функцию "цветового расстояния".