Russian Qt Forum

Добрый день

Есть картинка напр 1kx1k, то есть всего миллион пикселей. Каким-то образом отобрана/маркирована тысяча пикселей (т.е. очень небольшой процент). Теперь пробегаемся по всем пикселям, для каждого смотрим маркированных ближайших соседей. Допустим все они оказались одного (или близкого) цвета. Все хорошо, пошли дальше. Если нет - надо маркировать новый пиксель. Это изменит расклад как для последующих так и для предыдущих - теперь новая точка может оказаться ближайшей вместо старой. Заметим что мы совсем не обязаны немедленно маркировать тот самый пиксель где есть дисбаланс. Задача "сбалансировать всех" а какой пиксель отбирать - наше дело. Конечная цель понятна - описать картинку приближенно небольшим числом пикселей.

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

Спасибо

Напрямую матрица в памяти. Если пиксел разумных размеров, то это несколько метров в памяти. Для современных систем - пшик. :)

Ну матрица в памяти, и что, как искать-то? Прямым перебором окрестности - прикинем. Радиус 20, значит для каждого пикселя перебрать 440 соседей. Это убого даже для простейшего случая и не годится вообще при первом же усложнении.

А главное - как избежать поиска практически по всему миллиону пикселей снова и снова? Обычно на каждом проходе добавляется очень небольшое число новых пикселей (меньше и меньше с каждым проходом). Т.е. изменяется расклад в очень небольшой области.

Про параллельную реализацию - я так понял даже не беретесь. Ну да, здесь думать надо, это Вам не в СУБД  керосин заливать  :) 

Может я не совсем понял, но из того что понял я бы делал примерно так(уже с учетом распараллеливания):
1) Делю количество пикселей на количество потоков, каждому потоку даю работу обработать свой участок.
2) На первом проходе выявляются пиксели требующие обработки и номер пикселя добавляется в единый список пикселей.
3) Из единого списка пикселей раздаю потокам пиксели так, чтоб гарантированно не пересекались области работы этих потоков.
4) Каждый поток получив пиксель обрабатывает свою область вокруг пикселя и если требуется обработать еще пиксели в своей области, то добавляют их в список пикселей(это для того чтоб можно было контролировать области работы потоков).
5) Пункты 3-4 повторяются до достижения результата.
Но я не знаю что у тебя за задача стоит и поэтому может можно еще проще ее решить.

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

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

Каким образом выявляются? Как уже говорилось выше, прямой перебор/сканирование не годится

Допустим выявлена группа/банда 10 пикселей стоящих "кучно".

С одной ниткой: маркируем первый, проверяем 9 остальных, допустим  все хорошо, больше маркировать не требуется, пошли дальше

С 2-мя нитками: маркируем первый, проверяем остальные, но вот беда: только 5 из них обрабатываются нашей ниткой, 4 остальные - другой. Что делать?

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

Если что-то непонятно выкладывай картинки, на них проще объяснить.

А так нет воспроизводимости. Если мы спланировали работу 1 ниткой - будут маркироваться одни пиксели. Если 2-мя - уже другие. Др числом ниток - третьи

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

- маркировали какой-то пиксель. Тогда с тупым перебором мы должны
- проверить все точки вокруг этого пикселя (сотни)
- для каждого проверяемого найти его ближайших соседей (чтобы выяснить с ним все Oк)

С квадратичным перебором никакого железа не хватит

Незная точно что вам нужно конечно врятли кто-то угадает то что необходимо.

Ну ладно остановимся пока на одной нитке, ибо вам важно в каком порядке обрабатываются пиксели:
1) Проходим по всему массиву и составляем список пикселей для обработки.
2) Проходим по списку и обрабатываем, те что необходимо проверить тоже в список добавляем.
3) Повторяем второй шаг пока не закончатся пиксели.
А вот насчет того чтоб избавиться от необходимости проверки всех точек вокруг пикселя надо знать конкретные условия, например если мы изменяем точку и если на расстоянии нее в 10 пикселей в четыре стороны нету пикселей меньшей цветности то можно добавить квадраты в которых описаны минимальные значения своего участка. И сделать участки можно перекрывающимися. Тогда можно проверить если есть такой пиксель, то производим проверку в нужном квадрате, если нету то продолжаем обработку.
Если задача узкоспециализированна, то надо отталкиваться от условий задачи а не искать способ на все случаи жизни.

Каждый пиксель имеет "радиус захвата" который может быть разным для разных пикселей, но всегда известен. Когда пиксель маркируется все точки внутри круга подлежат перепроверке на валидность. Проверка может быть очень всякой-разной, но в любом случае исходные данные для нее = все маркированные пиксели захватывающие данный + конечно расстояния до них.

С этим тоже не все так просто. Получив на первом проходе список инвалидов мы имеем выбор - типа можем ту точку маркировать, а можем и эту. Оптимально выбрав мы можем заметно сократить общее число отмеченных.

Понимаю, но это палка о двух концах - чрезмерная привязка к конкретике, мягко говоря, "не украшает"

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

А на чем я могу здесь "специализироваться"? Так или иначе мне надо знать расклад, т.е. какие (маркированные) пиксели захватывают/влияют на данный.

Честно говоря, постановка задачи немного мутная..
Не понятно чего в итоге хотите получить?

Наверное проще увеличить контрастность рисунка и будет у вас гораааздо меньше "разных цветов", в зависимости от того, на сколько сильно "шумный" рисунок. Другой вопрос - как вы этот винегрет из координат будете хранить и воспроизводить? А так 1000*1000 при условии что в памяти это разворачивается в битмап (4 байта на пиксель = R+G+B и какая-то там масочка, которая не всегда используется), соответственно выравнивается по 4 байта и имеет вполне съедобную структуру, при прямом обращении к памяти скорость просто шикарна. Где-то у меня даже старые билдеровские исходники дома валялись, задача была: отсканированный рисунок почистить от шумов, повысить контрастность и затем найти на нём контур детали (как раз сохранялись координаты этой детали с определённым шагом между точками). Работал с BMP, на omnibook xe2 (Pentium II, 64 Мб ОЗУ) шуршало только в путь.

Тебе нужны LODы? Ну так сделай пару лодов, и выбирай их в зависимости от необходимой точности.

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

Память брать можно. Сейчас пиксель под 100 байт, может будет больше, ничего, переживу, это мои проблемы.

1) По всем - это вообще по всем 10^6 или по маркерованным?
2)  для каждого смотрим маркированных ближайших соседей. В смысле?
3) Допустим все они оказались одного (или близкого) цвета. Кто они? Ближайшие маркированные соседи или просто ближайшие соседи?
4) Все хорошо, пошли дальше. Если нет - надо маркировать новый пиксель. Какой именно?
5) Это изменит расклад как для последующих так и для предыдущих - теперь новая точка может оказаться ближайшей вместо старой.  Этого я вообще не понимаю..

Какая то запутанная логика(

Можно на каком нить миниатюрном примере: Что вначале было и что в конце должно быть?

Пока подробнее какие именно пиксели надо искать не напишешь, врятли получишь ответ.
Это тоже самое что спросить какой лучше алгоритм сжатия использовать, не объяснив какие данные необходимо сжать. Может это текст(PPMD), звук(flac), бинарные файлы(upx) и т.д.

По сабжу - ну будет там скучная собственная структурка, в которой будет три переменных: вертикаль, горизонталь, цвет пихеля. Дёшево и сердито. Никаких деревьев и прочих плясок с бубнами. И в итоге всё равно получается "тупой перебор". Выигрыша от "распоточить", не будет, там же не рассчёты, а тупой поиск в примерно одной области памяти, больше затраты будут на поддержку "многопоточности" и сохранение атомарности для списка, в который структурка пишется.

Псевдокод

C++ (Qt)
bool ValidatePixel( const CPixel & target, const std::vector <CPixel *> & markedNeighbours )
 

Аргументы

- target - немаркированный пиксель подлежащий проверке
- markedNeighbours - вектор всех маркированных пикселей которые влияют на target (т.е. target лежит внутри круга захвата для каждого элемента вектора)

Возвращаемое значение: true если с target'ом "все хорошо" и баланс достигнут. Иначе false

Что значит "все хорошо"? Здесь уже используется масса вариантов, некоторые из них отпадут, новые добавятся. По существу это еще одна (другая) задача. Простейший пример: вычисляем средний цвет по всем markedNeighbours и сравниваем его с цветом target. Разница не превышает заданный порог - вернули true, иначе false. Наша тема - поиск, и с этой точки зрения нам важно только одно - изменился вектор источников - валидность пикселя возможно изменилась. Расчет закончен если для всех немаркированных пикселей ValidatePixel вернула true.

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

А проблемы такие

1) Пробегаясь для каждого немаркированного надо как-то собрать маркированных соседей

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

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

По первому пункту: не понятно, что значит: надо как то собрать маркированных соседей? 

Ну тот вектор markedNeighbours (пост #19) надо же как-то получить, он ведь разный для каждого проверяемого

Ну так модифицируйте его при каждом проходе..  ???

Вроде как напрашивается граф: к маркированной точке приделываем список ближайших маркированных точек с расстояниями.
Далее проверяем только их - обход графа в ширину.

А чего это мы так отчаянно (и неумело) велосипедим?  Может это... стоит открыть книжки?  :)