Простенький алгоритм для поиска изолиний

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

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

поищи «Алгоритмы ГРАФОР» - в статье хорошо и ясно описан алгоритм построения изолиний. Или найди и подцепи сам графор :)

когда-то по нему делал свой велосипед :)

Фортран? Боюсь, проще будет с нуля написать, чем переписывать с фортрана.

Фортран? Боюсь, проще будет с нуля написать, чем переписывать с фортрана.

поэтому и говорю - смотреть ОПИСАНИЯ алгоритмов. Сами алг. весьма компактны и легко реализуются на чём хош :)

дык fortran ведь же вроде легко линкуется с C

Можно глянуть потрошки MathGL или gnuplot.

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

Затем для каждой изолинии остается замкнуть контуры, это можно сделать при помощи std::map.

Это несложно и даже интересно;-)

Я делал абсолютно тупым методом перебора. У тебя в любом случае должны быть какие-то ячейки — треугольники, квадраты, и т.д. и т.п. Что такое линия уровня? Это просто кривая по которой пересекается твоя поверхность с плоскостью. Обходишь все треугольники (квадраты) и смотришь пересекается ли поверхность на треугольнике (квадрате) с плоскостью. Если пересекается, то рисуешь отрезок. Поверхность на треугольнике можно на самом деле считать плоскостью, поэтому пересечение будет по отрезку. В общем, все тривиально, никаких замыканий потом искать не надо. Картинки получаются красивые.

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

Можно, например, прогнать изображение через медианный фильтр, затем сделать пороговые преобразования (вроде «постеризации» gimp'а), затем полученное изображение прогнать через градиентный фильтр (например, Собель) - ненулевые значения дадут примерное положение изолиний. Далее как-то надо будет пройтись по этим изолиниям и, исходя из уровней интенсивности опорного (неотфильтрованного) изображения уточнить координаты узлов.

На словах все просто, а на деле что-то не кумекается...

Да и фильтров уйма, на CUDA я еще их не реализовал (планирую в ближайшее время), а на CPU в 4 потока фильтрация картинки в 9Мпикс занимает аж полторы секунды - многовато).

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

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

Что значит вычислить? Если ты знаешь уровень на котором находится изолиния, то ты можешь найти все её отрезки, а найдя отрезки ты можешь их все соединить. В случае гладких поверхностей просто находим min и max и разбиваем этот диапозон на K частей и соответственно рисуем K изолиний. В случае изображений у тебя может получаться негладкое и даже разрывное нечто, тут уже такой способ не прокатит.

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

Но это же очень долго (секунд 10-15 для изображения в 9Кпикс). Хочется чего-нибудь побыстрее...

Ты уже это сделал, чтобы утверждать, что это долго?

Я уже выше говорил: фильтрация (через БПФ) занимает полторы секунды, медианная будет занимать еще больше. Остальные операции довольно быстрые. Ну и поиск связанных областей лептоника выполняет меньше, чем за секунду, для такого изображения.

Хотя, можно попробовать еще делать тупую пороговую бинаризацию, поиск связанных областей и выделение контуров. И так несколько раз - для каждого уровня изолиний. Т.е., скажем, надо нам разбить изображение по интенсивности на 32 уровня изолиниями; сначала обнуляем все, что меньше Imax/32, остальное заменяем единицами, ищем области, получаем изолинии первого уровня; затем - обнуляем все, меньше Imax/16 и т.п.

Но что-то боюсь, что долго это будет...

// переписать, что ли, для начала на CUDA алгоритм поиска связанных областей?

Че та Вы мудрите... руки дойдут - сделаю, там неск десятков строк, правда на С++.

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

вроде:

1. находим нижную и верхную точки

2. танцуя от сюда ищем изолинию

3. следующая изолиния находится внутри первой (прогрессирующее уменьшение точек), если мы не выше верхней точки goto 1

4. profit

s/goto 1/goto 2/

Зависит от числа изолиний. При большом числе изолиний и большом объеме данных тормозит весьма прилично.

Мдя...я таки сделал для себя, но заняло это чуть ли не 100 строчек (на С++), при том что у меня очень длинные строчки;-(

Много возни оказалось с поиском отрезков, и в особенности с замыканием контуров. Код далеко не идеален, но работает. В общем можно глянуть тут http://a-iv.ru/aivlib/include/algs.hpp ф-я mk_isolines и ужаснуться;-)

Спасибо, посмотрю.

Итак, дошли у меня руки до реализации этих «шагающих квадратов». Для выявления изолиний делаю следующее: сначала по выбранному алгоритму (линейный, логарифмический, экспоненциальный, степенной) «постеризую» изображение (т.е. разбиваю его на N уровней интенсивности); далее строю маску, как в алгоритме «шагающих квадратов»:

	#pragma omp parallel for
	for(y = 0; y < h-1; y++){
		int x;
		unsigned char *in = levels + y*w, *out = mask + y*(w-1);
		unsigned char m, a,b,c,d;
		for(x = 0; x < w-1; x++, in++, out++){
			a = *in, b = *(in+1), c = *(in+w), d = *(in+w+1);
			m = MIN(MIN(a,b), MIN(c,d));
			*out = ((a!=m)<<3) | ((b!=m)<<2) | ((d!=m)<<1) | (c!=m);
		}
	}

А вот с реализацией распознавания и сохранения контуров возник затык:

• Во-первых, непонятно, как однопроходным алгоритмом распознать все контуры (или все-таки использовать стандартный подход и сканировать все пиксели изображения, в случае обнаружения контура проходить по контуру, обнуляя значения в уже просмотренных пикселях, возвращаться и сканировать дальше?). Еще вариант - взять «распознавалку» из лептоники, но там на выходе получится очень много данных.
• Во-вторых, непонятно как замыкать контуры и «проскакивать» разрывы. Особенно если на каком-либо пикселе сходится несколько изолиний (скажем, резкий контрастный край).
• В-третьих, вопрос - как сохранять обнаруженные изолинии. Я себе представляю это как массив структур. Индекс элемента массива соответствует очередному уровню интенсивности, а сам элемент - список обнаруженных изолиний. Каждый элемент списка в свою очередь является списком координат точек изолиний, полученных линейной интерполяцией из метода «шагающих квадратов». Нормально это, или можно сделать более осмысленное хранение?

Итак, алгоритм сделаю многопроходным, черт с ним, что чуть медленнее будет работать - все быстрее медианной фильтрации.

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

Для одного потока идея проста: сканируем подряд все пиксели маски; как только находим ненулевое значение, вычисляем для него уровень серого и добавляем в массив изолиний новый контур и его первую точку, вычисленную каким-либо (пока не придумал) образом; далее переходим, в зависимости от значения данного пикселя маски, к ее следующему пикселю, обнуляя текущий; повторяем, пока не упремся в 0; возращаемся к пикселю, идущему вслед за тем, на котором мы обнаружили первую точку контура, и продолжаем поиск далее.

Как это распараллелить - не понимаю.

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

В принципе, куски можно склеить на следующем проходе: последовательно для каждого уровня генерировать битовую маску, значения которой == 1, если интенсивность изображения в точке выше заданного значения уровня. Потом лептоникой найти все замкнутые контуры и «соединить» все изолинии внутри них.

Но таким способом я могу и сразу изолинии искать - поочередно делать «срезы» по заданному уровню, искать связанные области и обводить их по границе при помощи все тех же «шагающих квадратов».

Вот все думаю, как бы все это реализовать так, чтобы и попроще было, и побыстрее?

Судя по последним тредам, ты там ядрёну бомбу программируешь.

:)

Нет, всего лишь обрабатывалку изображений.

Итак, после долгих мучений я таки сделал наброски как бы шагающих квадратов. Глюков пока полным-полно, зато работает быстро :) Постараюсь в ближайшее время все глюки убрать (пока самый главный глюк - расчет координат очередного узла изолинии, который производится мною совершенно неправильно). Надеюсь, придумаю как в квадрате из четырех точек рассчитать координаты одной точки, лежащей где-нибудь в районе середины пересечения плоскости уровня и поверхности изображения.

С самим методом «шагающих квадратов» почти ничего общего этот велосипед не имеет, т.к. мозгов на реализацию «шагающих квадратов» у меня не хватило.

Ура, товарищи! Заработало!!!

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

Для тестовой картинки 3000х3000 изолинии по шести равномерно распределенным уровням вычисляются ~150мс.

Многовато, конечно, но как это распараллелить я так и не придумал (для распараллеливания, чтобы избежать коллизий, придется искать изолинии в каждой выделенной области изображения отдельно, а затем «склеивать» общие для соседних областей изолинии. Как это делать - ума не приложу).

Странно как-то мой алгоритм работает. Точнее - глючит ужасно!

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

Продолжение от AIv

а кто написал эту статью и где она была опубликована?