Участник:Nikkou/Фильтр Собеля - История изменений

Nikkou: /* Информационный граф */

2017-12-08T08:48:17Z

Информационный граф

← Предыдущая версия		Версия от 08:48, 8 декабря 2017
Строка 78:		Строка 78:

	=== Информационный граф ===		=== Информационный граф ===
			[[Файл:Graph.png]]

	Группы вершин:		Группы вершин:

Nikkou: /* Ресурс параллелизма алгоритма */

2017-12-08T08:14:33Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 08:14, 8 декабря 2017
Строка 102:		Строка 102:

	3) Одномерные свертки можно считать независимо по каждому пикселю - массовый параллелизм. Можно сделать их вычисление параллельным на практике если и не по пикселям, то по крайней мере по специально сконструированным блокам изображения для оптимального выполнения на GPU.		3) Одномерные свертки можно считать независимо по каждому пикселю - массовый параллелизм. Можно сделать их вычисление параллельным на практике если и не по пикселям, то по крайней мере по специально сконструированным блокам изображения для оптимального выполнения на GPU.

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

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

Nikkou: /* Масштабируемость реализации алгоритма */

2017-12-08T08:10:09Z

Масштабируемость реализации алгоритма

← Предыдущая версия		Версия от 08:10, 8 декабря 2017
Строка 126:		Строка 126:

	[[Файл:Strong.PNG]]		[[Файл:Strong.PNG]]

	~~График слабой масштабируемости:~~

	~~[[Файл:Weak.PNG]]~~

	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===

Nikkou в 08:09, 8 декабря 2017

2017-12-08T08:09:46Z

← Предыдущая версия		Версия от 08:09, 8 декабря 2017
Строка 59:		Строка 59:
	Запись на C++-подобном псевдокоде:		Запись на C++-подобном псевдокоде:
	<pre>float sobel(float img) {		<pre>float sobel(float img) {
	// ~~diff_kernel is~~ [1, 0, -1]~~; sum_kernel is~~ [1, 2, 1]		// Оператор собеля разложим на одномерные свертки с ядрами [1, 0, -1] и [1, 2, 1]
	horiz_der = conv(img, diff_kernel, sum_kernel);		// Здесь они обозначены как соответственно diff_kernel и sum_kernel
	vert_der = conv(img, sum_kernel, diff_kernel);		horiz_der = conv(img, diff_kernel, sum_kernel); // Аппроксимация производной по горизонтальному направлению
			vert_der = conv(img, sum_kernel, diff_kernel); // Аппроксимация производной по вертикальному направлению
	return combine_horiz_vert(horiz_der, vert_der);		return combine_horiz_vert(horiz_der, vert_der);
	}		}

	for (int i = 0; i < n_images; i++) {		for (int i = 0; i < n_images; i++) {
	img = get_input(i);		img = get_input(i); // Чтение изображения с диска
	res = sobel(img);		res = sobel(img);
	write_result(res);		write_result(res); // Запись результата на диск
	}</pre>		}</pre>

Nikkou: /* Литература */

2017-12-02T17:42:28Z

Литература

← Предыдущая версия		Версия от 17:42, 2 декабря 2017
Строка 144:		Строка 144:

	== Литература ==		== Литература ==

			Podlozhnyuk, V. (2007). Image convolution with CUDA. NVIDIA Corporation white paper, June, 2097(3).

			Ogawa, K., Ito, Y., & Nakano, K. (2010, November). Efficient Canny edge detection using a GPU. In Networking and Computing (ICNC), 2010 First International Conference on (pp. 279-280). IEEE.

			Luo, Y., & Duraiswami, R. (2008, June). Canny edge detection on NVIDIA CUDA. In Computer Vision and Pattern Recognition Workshops, 2008. CVPRW'08. IEEE Computer Society Conference on (pp. 1-8). IEEE.

	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]

Nikkou: /* Существующие реализации алгоритма */

2017-12-02T17:39:12Z

Существующие реализации алгоритма

← Предыдущая версия		Версия от 17:39, 2 декабря 2017
Строка 133:		Строка 133:
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===
			В силу возможности эффективно распараллелить фильтрацию с ядром Собеля и широких возможностей практического применения, есть

			- последовательные реализации (OpenCV)

			- параллельные реализации на CUDA для GPU: [https://github.com/JoeLoser/Sobel-Filter-CUDA 1], [https://github.com/JakubDziworski/Cuda-Sobel 2]

			- параллельная реализация на MPI для CPU: [https://github.com/cnavarropalos/sobel-mpi ссылка].

			Автор статьи написал параллельную реализацию, которая использует и MPI для распределения входных данных по GPU на узлах, и CUDA для эффективного просчета на GPU. За основу был взят [https://github.com/phrb/intro-cuda/tree/master/src/cuda-samples/3_Imaging/convolutionSeparable код примера эффективной реализации сепарабельной двумерной свертки над CUDA] от NVIDIA.

	== Литература ==		== Литература ==

	[[Категория:Начатые статьи]]		[[Категория:Начатые статьи]]

Nikkou: /* Масштабируемость алгоритма и его реализации */

2017-12-02T17:29:18Z

Масштабируемость алгоритма и его реализации

← Предыдущая версия		Версия от 17:29, 2 декабря 2017
Строка 118:		Строка 118:
	==== Масштабируемость алгоритма ====		==== Масштабируемость алгоритма ====
	==== Масштабируемость реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
			При обилии входных данных очень легко распределить различные изображения на различные процессы. Но при параллельной обработке одного изображения возникают тонкости, связанные с барьерными синхронизациями между операциями, эффективным использованием быстрой памяти и "разогревом" GPU.

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

	График сильной масштабируемости:		График сильной масштабируемости:

Nikkou: /* Масштабируемость реализации алгоритма */

2017-12-02T17:09:59Z

Масштабируемость реализации алгоритма

← Предыдущая версия		Версия от 17:09, 2 декабря 2017
Строка 118:		Строка 118:
	==== Масштабируемость алгоритма ====		==== Масштабируемость алгоритма ====
	==== Масштабируемость реализации алгоритма ====		==== Масштабируемость реализации алгоритма ====
			График сильной масштабируемости:

			[[Файл:Strong.PNG]]

			График слабой масштабируемости:

			[[Файл:Weak.PNG]]

	=== Динамические характеристики и эффективность реализации алгоритма ===		=== Динамические характеристики и эффективность реализации алгоритма ===
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===

Nikkou: /* Ресурс параллелизма алгоритма */

2017-12-02T17:06:30Z

Ресурс параллелизма алгоритма

← Предыдущая версия		Версия от 17:06, 2 декабря 2017
Строка 100:		Строка 100:
	2) Одномерные свертки в разложении двумерной могут считаться независимо. Это конечный параллелизм.		2) Одномерные свертки в разложении двумерной могут считаться независимо. Это конечный параллелизм.

	3) ~~Однромерные~~ свертки можно считать независимо по каждому пикселю - массовый параллелизм. Можно сделать их вычисление параллельным на практике если и не по пикселям, то по крайней мере по специально сконструированным блокам изображения для оптимального выполнения на GPU.		3) Одномерные свертки можно считать независимо по каждому пикселю - массовый параллелизм. Можно сделать их вычисление параллельным на практике если и не по пикселям, то по крайней мере по специально сконструированным блокам изображения для оптимального выполнения на GPU.

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===

Nikkou: /* Входные и выходные данные алгоритма */

2017-12-02T16:59:29Z

Входные и выходные данные алгоритма

← Предыдущая версия		Версия от 16:59, 2 декабря 2017
Строка 103:		Строка 103:

	=== Входные и выходные данные алгоритма ===		=== Входные и выходные данные алгоритма ===
			Входные данные: K вещественных матриц размером N*M с диапазоном значений от 0 до 1. О структуре данных нельзя делать предположений.
			Выходные данныые: K вещественных матриц размером N*M. Дополнительно можно отнормировать диапазон значений результата для визуализации.

	=== Свойства алгоритма ===		=== Свойства алгоритма ===