Емельянов Эдуард Владимирович (eddy_em) wrote,
Емельянов Эдуард Владимирович
eddy_em

Мысли насчет распараллеливания маркировки связанных областей

Графики из предыдущей темы (блин, обнаружил, что я вчера все делал в /tmp, а перенести в ~/Dropbox забыл! Поэтому все изменения пошли коту под хвост, уцелело лишь то, что в ЖЖшке выложил, так что посчитать коэффициенты не могу, а тесты заново делать ломает) показывают, что зависимость скорости вычислений от количества пикселей на объекте (а также — количества объектов и их размера) имеет степенной вид, причем степень довольно плавно изменяется при изменении размера изображения.

Таким образом, если время вычислений T = Nm, где N - количество пикселей на изображении, то разбиение изображения на M кусков может позволить ускорить вычисления в том случае, если
T1 = M·[(N/M)m + t(sqrt(N/M))] < T.
Здесь t - время выполнения операции слияния границ соседних блоков с соответствующей ремаркировкой.



Понятно, что если блоки достаточно большие, второе слагаемое внутри скобок будет значительно меньше первого. Грубо пренебрегая им, получим в нулевом приближении, что разбиение изображения на M блоков ускоряет вычисления в Mm-1 раз. Однако, учитывая то, что второе слагаемое в скобках пропорционально своему аргументу, раскрытие скобок даст нам нечто вроде
M1-m + k·sqrt(MN)/T < 1,
где k - некий постоянный коэффициент. Таким образом, выигрыш в производительности очень сильно будет зависеть от m, k (при некоторых их комбинациях выигрыш вообще невозможен), а также собственном M (причем, учитывая то, что у нас получается степенное уравнение, оптимальных значений M может быть несколько, "смотря как карта ляжет").

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

Само распараллеливание я себе представляю так. Разделим изображение на M кусков (полосами или прямоугольниками — зависит от размера изображения; но, скорее всего, все-таки прямоугольниками). Выделим глобальный массив для ремаркировок assoc[M][s];, где s - предельное количество ассоциаций в одном сегменте. Также выделим массивы размера M для хранения количества меток и количества объектов в каждом сегменте. Потом запустим M потоков выделения объектов в каждом сегменте. Внутри каждого сегмента оставим нетронутой пограничную область шириной в 1 пиксель: скажем, правый столбец и нижнюю строку.

После завершения всех потоков обновляем массивы ремаркировок: к номеру каждого объекта в очередном сегменте добавляем количество объектов в предыдущих сегментах.

Теперь нам нужно провести стыковку соседних областей. Этот процесс тоже допускает параллелизацию. Пробегая по пограничным областям каждого сегмента, устанавливаем ненулевой пиксель в значение ближайшего ненулевого пикселя этого сегмента или же новое значение, производя соответствующие ремаркировки. Самый худший вариант — отдельный объект в виде полосы шириной в 1 пиксель, находящийся точно на границе: никаких ремаркировок не будет, но счетчик объектов инкрементируется. А это приведет к тому, что нужно будет полностью обновить огромный общий массив ремаркировок, увеличив его размер на 1. Еще нужно не забывать, что в углах каждой области (кроме пограничных вариантов) необходимо проверить пиксели четырех областей (с соответствующими изменениями в массиве ремаркировок). В итоге коэффициент k в приведенной выше формулке может стать вполне приличным.

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

Tags: c, snippets, поиск связанных областей
Subscribe

  • Темы-2

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

  • Темы для творческих работ школьников

    В связи с возможным проведением очной весенней школы АФШ (детей набрали еще прошлым летом, но пока очно не было возможности встретиться из-за…

  • Бюджетная читалка с алиэкспресса

    Долго искал вменяемые электронные читалки, но за формат примерно А4 просят около $900, вообще озверели. ОК, решил взять мелкую дешевую читалку, чтобы…

promo eddy_em august 17, 2019 12:33 3
Buy for 10 tokens
Юра намедни напечатал корпус для хронометра. Для первого блина получилось неплохо: И еще немного фотографий:
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

  • 2 comments