sic 31 мая 2011 в 16:01

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

9 мин

+68

Комментарии 21

Volshebnyi 31 мая 2011 в 16:41

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

davinchi 2 июн 2011 в 12:08

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

pixxxel 31 мая 2011 в 16:41

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

sic 31 мая 2011 в 16:56

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

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

pixxxel 31 мая 2011 в 19:22

Я про <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 31 мая 2011 в 19:24

ой, я про это

sic 31 мая 2011 в 17:08

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

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

3al 31 мая 2011 в 16:59

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

Это как?

sic 31 мая 2011 в 17:07

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

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

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

3al 31 мая 2011 в 17:17

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

9mm 31 мая 2011 в 17:47

 

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 31 мая 2011 в 17:56

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

9mm 31 мая 2011 в 18:02

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

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

Fesor 31 мая 2011 в 20:01

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

Fesor 31 мая 2011 в 20:04

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

futureader 31 мая 2011 в 18:29

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

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

sic 1 июн 2011 в 10:37

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

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

futureader 1 июн 2011 в 11:16

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

stmuxa 31 мая 2011 в 20:54

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

vanfukov 1 июн 2011 в 10:33

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

sic 1 июн 2011 в 10:35

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

Зарегистрируйтесь на Хабре, чтобы оставить комментарий