Мелом расчерчен...

[Igors]

Добрый день

Опять лезу с "мозголомной задачей" (нет чтобы прикручивать базу, настраивать моники)  
Чтобы задействовать все ядра расчет выполняется расчлененно. Представим себе имедж как шахматную доску, размер клетки напр 8х8 пыкселей

- проход 1:   считаются все "белые" клетки в четных строках
- проход 2:   считаются все "белые" клетки в нечетных строках
- проход 3:   считаются все "черные" клетки в четных строках
- проход 4:   считаются все "черные" клетки в нечетных строках

На каждом проходе запускается N ниток, следующий проход начинается после окончания предыдущего (все нитки завершились). Однако клетки перекрываются на 1 пиксель, т.е считаются матрицы 9x9. напр на последнем проходе все краевые пиксели уже были посчитаны. Расчет начинается с установки ID для каждого пикселя - идентификатор подмножества внутри матрицы. Каждый пиксель должен находиться в одном - и только в одном - таком подмножестве.

Нужно: если краевые точки уже были посчитаны (на предыдущих проходах), то они должны быть разделены на подмножества с учетом уже посчитанных ID. Например, если 2 точки при расчете одной матрицы оказались в одном подмножестве, то и при расчете смежной матрицы они также должны обязательно быть в одном. Если оказались в разных - то и в смежной клетке тоже в разных. Где и как хранить эти ID - обсуждается.  

Мысли, соображения?

Спасибо

[alexis031182]

...
Расчет начинается с установки ID для каждого пикселя - идентификатор подмножества внутри матрицы.
...

В контексте задачи:
- Множество - матрица подмножеств 8х8;
- Подмножество - это матрица пикселей 9х9;
- ID для пикселя - это идентификатор Подмножества.
Верно я понял?

[Igors]

В контексте задачи:
- Множество - матрица подмножеств 8х8;
- Подмножество - это матрица пикселей 9х9;
- ID для пикселя - это идентификатор Подмножества.
Верно я понял?

Да. Рассчитываются матрицы 9x9 с перекрытием в 1 пиксель. Пример

Один проход считает матрицу (0, 0)(8. 8 )
Другой проход считает матрицу (0, 8 )(8. 16)

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

- в каждом квадратике (матрице) выполняется кластерный анализ. Нужно "сшить" результаты (кластеры) между матрицами

[alexis031182]

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

[Igors]

Упрощенный пример: есть матрица 9х9, в каждом пикселе записан вектор нормали к поверхности. Тогда подмножества создаются примерно так

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

Если нормали сильно отличаются (напр грани куба) то в любой матрице точки на одной грани куба окажутся в 1 подмножестве (кластере). Однако для гладких поверхностей это может быть не так. Поэтому если есть точки просчитанные на предыдущих проходах, надо строить сначала кластеры для них. Но как это сделать?

 

[alexis031182]

М-да, теперь понял. После такого мне кажется, что в своём проекте я занимаюсь фигнёй Интересная задача.

[alexis031182]

Одно подмножество может соответствовать нескольким матрицам, правильно?

[Igors]

Одно подмножество может соответствовать нескольким матрицам, правильно?

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

Поэтому единственное что можно сделать - сохранить какие-то данные в пикселях. Конечно напрашивается ID (номер подмножества) но он уникален только в пределах данной матрицы

[alexis031182]

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

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

[Igors]

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

Да, хотя сохранение в пикселях выглядит проще и не требует никаких блокировок

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

Красивое словечко "тривиально" Да, известно что граничащие пиксели были обсчитаны -  и что?

[alexis031182]

Да, хотя сохранение в пикселях выглядит проще и не требует никаких блокировок

Можно и в пикселах.

Красивое словечко "тривиально"

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

Да, известно что граничащие пиксели были обсчитаны -  и что?

Стоп. Я никак не пойму... если

Поэтому если есть точки просчитанные на предыдущих проходах, надо строить сначала кластеры для них.

Кластер - это подмножество. У каждой обсчитанной точки есть идентификатор подмножества. Известно, какие из точек уже подсчитаны. Сравнение по id - есть чёткое определение, принадлежат ли точки разным или одному подмножеству. Тогда

если краевые точки уже были посчитаны (на предыдущих проходах), то они должны быть разделены на подмножества с учетом уже посчитанных ID. Например, если 2 точки при расчете одной матрицы оказались в одном подмножестве, то и при расчете смежной матрицы они также должны обязательно быть в одном. Если оказались в разных - то и в смежной клетке тоже в разных.

По идее, вся необходимая информация имеется. Что же явилось проблемой? Или просто в теме подразумевался поиск другого, более эффективного решения?

[Igors]

По идее, вся необходимая информация имеется. Что же явилось проблемой? Или просто в теме подразумевался поиск другого, более эффективного решения?

Нет, речь идет о "просто решении". Да, интуитивно вроде понятно что решаемо (точно доказать не могу). Проблема в том что записанные ID локальны и как их задействовать (в контексте др матрицы) неясно. Также неясно как их хранить.

[alexis031182]

Нет, речь идет о "просто решении". Да, интуитивно вроде понятно что решаемо (точно доказать не могу). Проблема в том что записанные ID локальны и как их задействовать (в контексте др матрицы) неясно. Также неясно как их хранить.

Другими словами, id подмножества стирается из пиксела как только будет завершён текущий проход?

[Igors]

В общем сделал я структуру данных для отслеживания ID локальных подмножеств. У каждой точки есть mLocalID[4]. Если точка внутри квадрата используется только  mLocalID[0] - только 1 квадрат может записать. Для точек на границах используются 2 элемента и для угловых точек - все 4. Расклад показан в аттаче

Однако выяснилось "локальные подмножества" нельзя перевести в "глобальные подмножества". На последнем проходе подмножества извлекаются с учетом 4 посчитанных соседей. Получается что один сосед диктует "эти 2 точки в разных подмножествах" а другой "эти 2 в одном". И как разрешить этои конфликт - пока не знаю