Сверхбыстрая разметка изображений

[Volshebnyi]

Метод действительно хорош. Однажды решал задачу подсчета областей (и их объема) в 3d-текстуре. В конце концов все точно также свелось к добавлению трехмерной сетки и проверке одинаковости цвета пикселей в ее узлах. Работало оно до ужаса медленно из-за очень большой точности сетки, но объем работ был не очень большой, так что CUDA в дело не пошла. А теперь уже все равно, как мне, так и заказчикам.
Вечером приду домой, откопаю исходники, буду читать и много думать. =)

[davinchi]

Знаю человека во Франкфурте, который предлагал позицию у себя за подсчёт энтропии системы частиц. Могу дать контакты и задание, вроде они так и не сделали это.

[pixxxel]

А что если закодировать изображение уголками?
Тогда сложность алгоритма станет на порядок меньше, да и вообще не будет зависеть от размера изображения

[sic]

я не очень понял что имеется в виду под «уголками».

однако имеет ли смысл уменьшать сложность алгоритма? его время работы почти совпадает со временем загрузки картинки в память.

[pixxxel]

Я про <a href='http://www.google.com.ua/url?sa=t&source=web&cd=1&ved=0CB4QFjAA&url=http%3A%2F%2Fcmp.felk.cvut.cz%2F~hlavac%2FTeachPresEn%2F11ImageProc%2F83CornersTalk.pdf&rct=j&q=schlesinger's%20corner%20representation&ei=Aj_lTZT8IMnQsgaTr9yXDQ&usg=AFQjCNG2cLbzF-asQ3SiQ7j-6-D8wg2amQ&sig2=aNJsZ2T8DW85J-6YBnFnkQ'>это (не знаю как правильно называется, что-то типа производной по изображению).
Получается, что пройти все пиксели нужно только один раз для нахождения уголков, а далее работать можно только с совокупностью уголков, которых на порядок меньше чем пикселей. Ну и много преимуществ, например, прощадь фигур можно вычислять чуть ли не бесплатно и тп

[pixxxel]

ой, я про это

[sic]

аа, по маске-то. да, наверное, это еще больше ускорило обсчет. и если реализовывать в несколько потоков на CPU — то лучше именно по маске.

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

[3al]

«оптимизировать», свернув цикл в один

Это как?

[sic]

не вдаваясь (пока) в подробности (хотя статью обязательно почитаю), вот так:

for (int pos = 0; pos < dims[0]*dims[1]; pos++)
{
image[pos] = 0;
}

или еще лучше, memset (...)

[3al]

Ага, это интереснее. Просто код в статье серьёзно мешает кэшу.

[9mm]


for (int x = 0; x < dims[0]; x++)
for (int y = 0; y < dims[1]; y++)
{
image[x + dims[0]*y] = 0;
}


Такое ощущение что тест составлен так чтобы CPU явно слил :)

Поменяйте итерацию по x и y местами, в моём случае время выполнения:
6830 (для x, затем y) и
157 (для x, затем y)

Проц: Атлон 64 x2 5600+ (2.9ГГц).

[9mm]

т.е.: 157 (для y, затем x)

[9mm]

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

Под вечер не в нимательно читаю.
Считайте мной вышенаписанное просто поддержанием разговора :)

[Fesor]

При компиляции в режиме отладки разница есть, но обычно такие мелочи как постфиксная инкрементация оптимизируются компилятором при релизе.

[Fesor]

Упс, невнимателен… надо бы все же поспать…

[futureader]

Честно говоря, не знаю в чем уникальность метода. В принципе — просто «паралельный вариант».
На счет объединения двух контактных областей в одну — надо делать тоже с помощью cuda. Процесс с областью (i,j) проверяет на контактность с областями справа (i,j+1) и снизу (i+1,j). Значительно сократите время на «сливание» областей.

И еще, как мне кажется, проще сделать прослойку в виде дескрипторов. Скажем, если замеченно, что область с цветом A контачит с цветом B, то они ссылаются на один дескриптор. По идее — наборов разных светов в одной области будет не велико, и метод с дескрипторами может помочь.

[sic]

да, пожалуй, «метод» слишком многообещающее название для такого подхода.

а как хранить эти дескрипторы? на CUDA есть большая ограниченность в использовании любых сложных структур.

[futureader]

«Дескриптор» это достаточно условное название. Просто — промежуточное звено. Можно провести аналог с палитрой. Номер каждого региона после первого прохода это номер ячейки в палитре. При слиянии регионов для соответсвующих ячеек устанавливается одно значение (только еще надо проверить, что все ячейки с объединящимися значениями получат новое ).

[stmuxa]

помню контест на топкодере был такой: реализовать этот алгоритм на куде.
у кого есть аккаунт, вот ссылка на задание.
www.topcoder.com/longcontest/?module=ViewProblemStatement&rd=13957&pm=10644

[vanfukov]

Забавное у вас понятие о средненькой видеокарте.

[sic]

и не только у меня: www.nix.ru/computer_hardware_news/hardware_news_viewer.html?id=164048