Название: Мелом расчерчен... Отправлено: Igors от Июнь 26, 2012, 15:51 Добрый день
Опять лезу с "мозголомной задачей" (нет чтобы прикручивать базу, настраивать моники) :) Чтобы задействовать все ядра расчет выполняется расчлененно. Представим себе имедж как шахматную доску, размер клетки напр 8х8 пыкселей - проход 1: считаются все "белые" клетки в четных строках - проход 2: считаются все "белые" клетки в нечетных строках - проход 3: считаются все "черные" клетки в четных строках - проход 4: считаются все "черные" клетки в нечетных строках На каждом проходе запускается N ниток, следующий проход начинается после окончания предыдущего (все нитки завершились). Однако клетки перекрываются на 1 пиксель, т.е считаются матрицы 9x9. напр на последнем проходе все краевые пиксели уже были посчитаны. Расчет начинается с установки ID для каждого пикселя - идентификатор подмножества внутри матрицы. Каждый пиксель должен находиться в одном - и только в одном - таком подмножестве. Нужно: если краевые точки уже были посчитаны (на предыдущих проходах), то они должны быть разделены на подмножества с учетом уже посчитанных ID. Например, если 2 точки при расчете одной матрицы оказались в одном подмножестве, то и при расчете смежной матрицы они также должны обязательно быть в одном. Если оказались в разных - то и в смежной клетке тоже в разных. Где и как хранить эти ID - обсуждается. Мысли, соображения? Спасибо Название: Re: Мелом расчерчен... Отправлено: alexis031182 от Июнь 26, 2012, 16:23 ... В контексте задачи:Расчет начинается с установки ID для каждого пикселя - идентификатор подмножества внутри матрицы. ... - Множество - матрица подмножеств 8х8; - Подмножество - это матрица пикселей 9х9; - ID для пикселя - это идентификатор Подмножества. Верно я понял? Название: Re: Мелом расчерчен... Отправлено: Igors от Июнь 26, 2012, 17:59 В контексте задачи: Да. Рассчитываются матрицы 9x9 с перекрытием в 1 пиксель. Пример- Множество - матрица подмножеств 8х8; - Подмножество - это матрица пикселей 9х9; - ID для пикселя - это идентификатор Подмножества. Верно я понял? Один проход считает матрицу (0, 0)(8. 8 ) Другой проход считает матрицу (0, 8 )(8. 16) Таким образом напр пиксель (0, 8 ) входит в обе матрицы. Подмножества - это непересекающиеся группы точек внутри матрицы. Возможна более краткая формулировка: - в каждом квадратике (матрице) выполняется кластерный анализ. Нужно "сшить" результаты (кластеры) между матрицами Название: Re: Мелом расчерчен... Отправлено: alexis031182 от Июнь 26, 2012, 19:47 Правильно ли я понял принцип формирования подмножеств? На вложенном изображении цифрами указал кол-во непересекающихся подмножеств. Последняя колонка выбивается из общей схемы, но к ней трафарет можно по разному прикладывать
Название: Re: Мелом расчерчен... Отправлено: Igors от Июнь 26, 2012, 20:09 Упрощенный пример: есть матрица 9х9, в каждом пикселе записан вектор нормали к поверхности. Тогда подмножества создаются примерно так
- взяли нормаль первого пикселя, создали множество (контейнер) и записали туда индекс этого пикселя - из всех оставшихся выбираем (и записываем в контейнер) индексы таких что угол с первой нормалью не превышает напр 10 градусов. - повторяем процесс до тех пор пока не останется "свободных" пикселей Если нормали сильно отличаются (напр грани куба) то в любой матрице точки на одной грани куба окажутся в 1 подмножестве (кластере). Однако для гладких поверхностей это может быть не так. Поэтому если есть точки просчитанные на предыдущих проходах, надо строить сначала кластеры для них. Но как это сделать? Название: Re: Мелом расчерчен... Отправлено: alexis031182 от Июнь 26, 2012, 20:21 М-да, теперь понял. После такого мне кажется, что в своём проекте я занимаюсь фигнёй :( Интересная задача.
Название: Re: Мелом расчерчен... Отправлено: alexis031182 от Июнь 26, 2012, 22:25 Одно подмножество может соответствовать нескольким матрицам, правильно?
Название: Re: Мелом расчерчен... Отправлено: Igors от Июнь 27, 2012, 10:39 Одно подмножество может соответствовать нескольким матрицам, правильно? Каждая нитка занимается "своей" матрицей, известно лишь что некоторые краевые пиксели уже были обсчитаны на предыдущих проходах и сохраненные в них данные можно/нужно использовать. После того как матрица обсчитана, нитка получит новую матрицу (никак не связанную с предыдущей). Поэтому единственное что можно сделать - сохранить какие-то данные в пикселях. Конечно напрашивается ID (номер подмножества) но он уникален только в пределах данной матрицы Название: Re: Мелом расчерчен... Отправлено: alexis031182 от Июнь 27, 2012, 11:03 Имеется ли возможность сохранять подмножества в некоем векторе матриц, индексы которого соответствовали бы порядковому номеру каждой из имеющихся матриц?
Поскольку при последующих проходах, при рассмотрении каждой конкретной матрицы нам фактически известны порядковые номера граничащих с текущей матриц, то поиск подмножества, содержащего информацию о граничащих пикселях текущей матрицы, будет тривиален. Название: Re: Мелом расчерчен... Отправлено: Igors от Июнь 27, 2012, 11:09 Имеется ли возможность сохранять подмножества в некоем векторе матриц, индексы которого соответствовали бы порядковому номеру каждой из имеющихся матриц? Да, хотя сохранение в пикселях выглядит проще и не требует никаких блокировокПоскольку при последующих проходах, при рассмотрении каждой конкретной матрицы нам фактически известны порядковые номера граничащих с текущей матриц, то поиск подмножества, содержащего информацию о граничащих пикселях текущей матрицы, будет тривиален. Красивое словечко "тривиально" :) Да, известно что граничащие пиксели были обсчитаны - и что?Название: Re: Мелом расчерчен... Отправлено: alexis031182 от Июнь 27, 2012, 11:56 Да, хотя сохранение в пикселях выглядит проще и не требует никаких блокировок Можно и в пикселах.Красивое словечко "тривиально" :) Если бы Вы восприняли его со значением "просто", и без принятия во внимание вероятного желания с моей стороны обозначить некую собственную значимость, то безусловно не стали бы концентрировать своё внимание на столь незначительной детали. Проще говоря, проще быть лучше :)Да, известно что граничащие пиксели были обсчитаны - и что? Стоп. Я никак не пойму... еслиЦитата: Igors Поэтому если есть точки просчитанные на предыдущих проходах, надо строить сначала кластеры для них. Кластер - это подмножество. У каждой обсчитанной точки есть идентификатор подмножества. Известно, какие из точек уже подсчитаны. Сравнение по id - есть чёткое определение, принадлежат ли точки разным или одному подмножеству. ТогдаЦитата: Igors если краевые точки уже были посчитаны (на предыдущих проходах), то они должны быть разделены на подмножества с учетом уже посчитанных ID. Например, если 2 точки при расчете одной матрицы оказались в одном подмножестве, то и при расчете смежной матрицы они также должны обязательно быть в одном. Если оказались в разных - то и в смежной клетке тоже в разных. По идее, вся необходимая информация имеется. Что же явилось проблемой? Или просто в теме подразумевался поиск другого, более эффективного решения?Название: Re: Мелом расчерчен... Отправлено: Igors от Июнь 27, 2012, 12:06 По идее, вся необходимая информация имеется. Что же явилось проблемой? Или просто в теме подразумевался поиск другого, более эффективного решения? Нет, речь идет о "просто решении". Да, интуитивно вроде понятно что решаемо (точно доказать не могу). Проблема в том что записанные ID локальны и как их задействовать (в контексте др матрицы) неясно. Также неясно как их хранить. Название: Re: Мелом расчерчен... Отправлено: alexis031182 от Июнь 27, 2012, 12:19 Нет, речь идет о "просто решении". Да, интуитивно вроде понятно что решаемо (точно доказать не могу). Проблема в том что записанные ID локальны и как их задействовать (в контексте др матрицы) неясно. Также неясно как их хранить. Другими словами, id подмножества стирается из пиксела как только будет завершён текущий проход?Название: Re: Мелом расчерчен... Отправлено: Igors от Июль 13, 2012, 12:58 В общем сделал я структуру данных для отслеживания ID локальных подмножеств. У каждой точки есть mLocalID[4]. Если точка внутри квадрата используется только mLocalID[0] - только 1 квадрат может записать. Для точек на границах используются 2 элемента и для угловых точек - все 4. Расклад показан в аттаче
Однако выяснилось "локальные подмножества" нельзя перевести в "глобальные подмножества". На последнем проходе подмножества извлекаются с учетом 4 посчитанных соседей. Получается что один сосед диктует "эти 2 точки в разных подмножествах" а другой "эти 2 в одном". И как разрешить этои конфликт - пока не знаю |