Структуры данных для поиска

[Igors]

Добрый день

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

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

Спасибо

[Tonal]

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

[Igors]

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

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

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

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

[V1KT0P]

Добрый день

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

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

Спасибо

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

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

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

[Igors]

2) На первом проходе выявляются пиксели требующие обработки и номер пикселя добавляется в единый список пикселей.

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

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

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

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

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

[V1KT0P]

2) На первом проходе выявляются пиксели требующие обработки и номер пикселя добавляется в единый список пикселей.

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

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

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

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

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

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

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

[Igors]

Короче я считаю надо делать так:
Пример с двумя нитками: левая часть обрабатывается первой ниткой, правая второй. ..

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

Ну так перебор полюбому должен быть надо же выявить все пиксели.

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

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

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

[V1KT0P]

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

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

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

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

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

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

[Igors]

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

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

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

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

Если задача узкоспециализированна, то надо отталкиваться от условий задачи а не искать способ на все случаи жизни.

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

[V1KT0P]

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

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

[Igors]

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

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

[m_ax]

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

[Igors]

Не понятно чего в итоге хотите получить?

Конечная цель понятна - описать картинку приближенно небольшим числом пикселей.

[QuAzI]

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

[V1KT0P]

Конечная цель понятна - описать картинку приближенно небольшим числом пикселей.

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