Алговики - Вклад [ru]

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

2017-12-08T08:48:17Z

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

Описание параллельной реализации алгоритма фильтрации Собеля.

Автор: А.Г.Лыжов (401 группа).

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Фильтр Собеля - дискретный дифференциальный оператор, который используется для приближения градиента яркости изображения. Он часто используется в алгоритмах выделения границ при обработке изображений. Фильтр Собеля был предложен Ирвином Собелем и Гэри Фелдманом в лаборатории искусственного интеллекта Стэнфорда в 1968.

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

=== Математическое описание алгоритма ===
Исходные данные:

* изображение <math>A^{N\cdot M}</math>

Вычисляемые данные:

* матрица аппроксимации модуля градиента <math>G^{N\cdot M}</math>

* матрица аппроксимации направления градиента <math>\Theta^{N\cdot M}</math>

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

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

<math>
\mathbf{G}_x = \begin{bmatrix}
+1 & 0 & -1 \\
+2 & 0 & -2 \\
+1 & 0 & -1
\end{bmatrix} * \mathbf{A}
,\
\mathbf{G}_y = \begin{bmatrix}
+1 & +2 & +1\\
0 & 0 & 0 \\
-1 & -2 & -1
\end{bmatrix} * \mathbf{A}
</math>

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

<math>\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }</math>

<math>\mathbf{\Theta} = \operatorname{atan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро совпадает с алгоритмом, так как все описанные операции выполняются за <math>O(M\cdot N)</math> на одном изображении.

=== Макроструктура алгоритма ===
Макроструктуру в основном составляют:

1) двумерные свертки, приведенные в математическом описании;

2) операция поэлементного геометрического среднего между промежуточными аппроксимациями.

Эти элементы алгоритма приведены в разделе с математическим описанием.

=== Схема реализации последовательного алгоритма ===
Запись на C++-подобном псевдокоде:
<pre>float *sobel(float *img) {
// Оператор собеля разложим на одномерные свертки с ядрами [1, 0, -1] и [1, 2, 1]
// Здесь они обозначены как соответственно diff_kernel и sum_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);
}

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

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

=== Последовательная сложность алгоритма ===
<math>O(M\cdot N \cdot K)</math> при обработке K изображений размером M*N, так как все макроэлементы, составляющие структуру алгоритма, выполняются за константу для одного пикселя.

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

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

1) выполняет операцию чтения изображения с диска. Количество вершин равно количеству изображений K.

2) выполняет горизонтальную свертку каждого изображения.

3) выполняет вертикальную свертку каждого изображения.

4) комбинирует частичные результаты.

5) записывает результат на диск.

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

Граф альтернативно можно представить и более детально, например, раскрыв макрооперации сверток изображения по строкам, столбцам, элементам ядер.

=== Ресурс параллелизма алгоритма ===
Группы параллельных ветвей:

1) Операции над разными изображениями независимы и образуют массово параллельные ветви.

2) Одномерные свертки в разложении двумерной могут считаться независимо. Это конечный параллелизм.

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

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

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

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

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

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

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

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

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

- последовательные реализации (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.

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

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.

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

Файл:Graph.png

2017-12-08T08:47:57Z

Nikkou:

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

2017-12-08T08:14:33Z

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

Описание параллельной реализации алгоритма фильтрации Собеля.

Автор: А.Г.Лыжов (401 группа).

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Фильтр Собеля - дискретный дифференциальный оператор, который используется для приближения градиента яркости изображения. Он часто используется в алгоритмах выделения границ при обработке изображений. Фильтр Собеля был предложен Ирвином Собелем и Гэри Фелдманом в лаборатории искусственного интеллекта Стэнфорда в 1968.

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

=== Математическое описание алгоритма ===
Исходные данные:

* изображение <math>A^{N\cdot M}</math>

Вычисляемые данные:

* матрица аппроксимации модуля градиента <math>G^{N\cdot M}</math>

* матрица аппроксимации направления градиента <math>\Theta^{N\cdot M}</math>

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

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

<math>
\mathbf{G}_x = \begin{bmatrix}
+1 & 0 & -1 \\
+2 & 0 & -2 \\
+1 & 0 & -1
\end{bmatrix} * \mathbf{A}
,\
\mathbf{G}_y = \begin{bmatrix}
+1 & +2 & +1\\
0 & 0 & 0 \\
-1 & -2 & -1
\end{bmatrix} * \mathbf{A}
</math>

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

<math>\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }</math>

<math>\mathbf{\Theta} = \operatorname{atan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро совпадает с алгоритмом, так как все описанные операции выполняются за <math>O(M\cdot N)</math> на одном изображении.

=== Макроструктура алгоритма ===
Макроструктуру в основном составляют:

1) двумерные свертки, приведенные в математическом описании;

2) операция поэлементного геометрического среднего между промежуточными аппроксимациями.

Эти элементы алгоритма приведены в разделе с математическим описанием.

=== Схема реализации последовательного алгоритма ===
Запись на C++-подобном псевдокоде:
<pre>float *sobel(float *img) {
// Оператор собеля разложим на одномерные свертки с ядрами [1, 0, -1] и [1, 2, 1]
// Здесь они обозначены как соответственно diff_kernel и sum_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);
}

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

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

=== Последовательная сложность алгоритма ===
<math>O(M\cdot N \cdot K)</math> при обработке K изображений размером M*N, так как все макроэлементы, составляющие структуру алгоритма, выполняются за константу для одного пикселя.

=== Информационный граф ===
Группы вершин:

1) выполняет операцию чтения изображения с диска. Количество вершин равно количеству изображений K.

2) выполняет горизонтальную свертку каждого изображения.

3) выполняет вертикальную свертку каждого изображения.

4) комбинирует частичные результаты.

5) записывает результат на диск.

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

Граф альтернативно можно представить и более детально, например, раскрыв макрооперации сверток изображения по строкам, столбцам, элементам ядер.

=== Ресурс параллелизма алгоритма ===
Группы параллельных ветвей:

1) Операции над разными изображениями независимы и образуют массово параллельные ветви.

2) Одномерные свертки в разложении двумерной могут считаться независимо. Это конечный параллелизм.

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

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

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

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

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

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

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

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

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

- последовательные реализации (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.

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

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-08T08:10:09Z

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

Описание параллельной реализации алгоритма фильтрации Собеля.

Автор: А.Г.Лыжов (401 группа).

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Фильтр Собеля - дискретный дифференциальный оператор, который используется для приближения градиента яркости изображения. Он часто используется в алгоритмах выделения границ при обработке изображений. Фильтр Собеля был предложен Ирвином Собелем и Гэри Фелдманом в лаборатории искусственного интеллекта Стэнфорда в 1968.

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

=== Математическое описание алгоритма ===
Исходные данные:

* изображение <math>A^{N\cdot M}</math>

Вычисляемые данные:

* матрица аппроксимации модуля градиента <math>G^{N\cdot M}</math>

* матрица аппроксимации направления градиента <math>\Theta^{N\cdot M}</math>

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

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

<math>
\mathbf{G}_x = \begin{bmatrix}
+1 & 0 & -1 \\
+2 & 0 & -2 \\
+1 & 0 & -1
\end{bmatrix} * \mathbf{A}
,\
\mathbf{G}_y = \begin{bmatrix}
+1 & +2 & +1\\
0 & 0 & 0 \\
-1 & -2 & -1
\end{bmatrix} * \mathbf{A}
</math>

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

<math>\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }</math>

<math>\mathbf{\Theta} = \operatorname{atan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро совпадает с алгоритмом, так как все описанные операции выполняются за <math>O(M\cdot N)</math> на одном изображении.

=== Макроструктура алгоритма ===
Макроструктуру в основном составляют:

1) двумерные свертки, приведенные в математическом описании;

2) операция поэлементного геометрического среднего между промежуточными аппроксимациями.

Эти элементы алгоритма приведены в разделе с математическим описанием.

=== Схема реализации последовательного алгоритма ===
Запись на C++-подобном псевдокоде:
<pre>float *sobel(float *img) {
// Оператор собеля разложим на одномерные свертки с ядрами [1, 0, -1] и [1, 2, 1]
// Здесь они обозначены как соответственно diff_kernel и sum_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);
}

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

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

=== Последовательная сложность алгоритма ===
<math>O(M\cdot N \cdot K)</math> при обработке K изображений размером M*N, так как все макроэлементы, составляющие структуру алгоритма, выполняются за константу для одного пикселя.

=== Информационный граф ===
Группы вершин:

1) выполняет операцию чтения изображения с диска. Количество вершин равно количеству изображений K.

2) выполняет горизонтальную свертку каждого изображения.

3) выполняет вертикальную свертку каждого изображения.

4) комбинирует частичные результаты.

5) записывает результат на диск.

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

Граф альтернативно можно представить и более детально, например, раскрыв макрооперации сверток изображения по строкам, столбцам, элементам ядер.

=== Ресурс параллелизма алгоритма ===
Группы параллельных ветвей:

1) Операции над разными изображениями независимы и образуют массово параллельные ветви.

2) Одномерные свертки в разложении двумерной могут считаться независимо. Это конечный параллелизм.

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

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

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

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

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

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

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

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

- последовательные реализации (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.

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

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-08T08:09:46Z

Nikkou:

Описание параллельной реализации алгоритма фильтрации Собеля.

Автор: А.Г.Лыжов (401 группа).

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Фильтр Собеля - дискретный дифференциальный оператор, который используется для приближения градиента яркости изображения. Он часто используется в алгоритмах выделения границ при обработке изображений. Фильтр Собеля был предложен Ирвином Собелем и Гэри Фелдманом в лаборатории искусственного интеллекта Стэнфорда в 1968.

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

=== Математическое описание алгоритма ===
Исходные данные:

* изображение <math>A^{N\cdot M}</math>

Вычисляемые данные:

* матрица аппроксимации модуля градиента <math>G^{N\cdot M}</math>

* матрица аппроксимации направления градиента <math>\Theta^{N\cdot M}</math>

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

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

<math>
\mathbf{G}_x = \begin{bmatrix}
+1 & 0 & -1 \\
+2 & 0 & -2 \\
+1 & 0 & -1
\end{bmatrix} * \mathbf{A}
,\
\mathbf{G}_y = \begin{bmatrix}
+1 & +2 & +1\\
0 & 0 & 0 \\
-1 & -2 & -1
\end{bmatrix} * \mathbf{A}
</math>

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

<math>\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }</math>

<math>\mathbf{\Theta} = \operatorname{atan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро совпадает с алгоритмом, так как все описанные операции выполняются за <math>O(M\cdot N)</math> на одном изображении.

=== Макроструктура алгоритма ===
Макроструктуру в основном составляют:

1) двумерные свертки, приведенные в математическом описании;

2) операция поэлементного геометрического среднего между промежуточными аппроксимациями.

Эти элементы алгоритма приведены в разделе с математическим описанием.

=== Схема реализации последовательного алгоритма ===
Запись на C++-подобном псевдокоде:
<pre>float *sobel(float *img) {
// Оператор собеля разложим на одномерные свертки с ядрами [1, 0, -1] и [1, 2, 1]
// Здесь они обозначены как соответственно diff_kernel и sum_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);
}

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

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

=== Последовательная сложность алгоритма ===
<math>O(M\cdot N \cdot K)</math> при обработке K изображений размером M*N, так как все макроэлементы, составляющие структуру алгоритма, выполняются за константу для одного пикселя.

=== Информационный граф ===
Группы вершин:

1) выполняет операцию чтения изображения с диска. Количество вершин равно количеству изображений K.

2) выполняет горизонтальную свертку каждого изображения.

3) выполняет вертикальную свертку каждого изображения.

4) комбинирует частичные результаты.

5) записывает результат на диск.

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

Граф альтернативно можно представить и более детально, например, раскрыв макрооперации сверток изображения по строкам, столбцам, элементам ядер.

=== Ресурс параллелизма алгоритма ===
Группы параллельных ветвей:

1) Операции над разными изображениями независимы и образуют массово параллельные ветви.

2) Одномерные свертки в разложении двумерной могут считаться независимо. Это конечный параллелизм.

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

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

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

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

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

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

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

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

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

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

- последовательные реализации (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.

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

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:42:28Z

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

Описание параллельной реализации алгоритма фильтрации Собеля.

Автор: А.Г.Лыжов (401 группа).

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Фильтр Собеля - дискретный дифференциальный оператор, который используется для приближения градиента яркости изображения. Он часто используется в алгоритмах выделения границ при обработке изображений. Фильтр Собеля был предложен Ирвином Собелем и Гэри Фелдманом в лаборатории искусственного интеллекта Стэнфорда в 1968.

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

=== Математическое описание алгоритма ===
Исходные данные:

* изображение <math>A^{N\cdot M}</math>

Вычисляемые данные:

* матрица аппроксимации модуля градиента <math>G^{N\cdot M}</math>

* матрица аппроксимации направления градиента <math>\Theta^{N\cdot M}</math>

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

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

<math>
\mathbf{G}_x = \begin{bmatrix}
+1 & 0 & -1 \\
+2 & 0 & -2 \\
+1 & 0 & -1
\end{bmatrix} * \mathbf{A}
,\
\mathbf{G}_y = \begin{bmatrix}
+1 & +2 & +1\\
0 & 0 & 0 \\
-1 & -2 & -1
\end{bmatrix} * \mathbf{A}
</math>

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

<math>\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }</math>

<math>\mathbf{\Theta} = \operatorname{atan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро совпадает с алгоритмом, так как все описанные операции выполняются за <math>O(M\cdot N)</math> на одном изображении.

=== Макроструктура алгоритма ===
Макроструктуру в основном составляют:

1) двумерные свертки, приведенные в математическом описании;

2) операция поэлементного геометрического среднего между промежуточными аппроксимациями.

Эти элементы алгоритма приведены в разделе с математическим описанием.

=== Схема реализации последовательного алгоритма ===
Запись на C++-подобном псевдокоде:
<pre>float *sobel(float *img) {
// diff_kernel is [1, 0, -1]; sum_kernel is [1, 2, 1]
horiz_der = conv(img, diff_kernel, sum_kernel);
vert_der = conv(img, sum_kernel, diff_kernel);
return combine_horiz_vert(horiz_der, vert_der);
}

for (int i = 0; i < n_images; i++) {
img = get_input(i);
res = sobel(img);
write_result(res);
}</pre>

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

=== Последовательная сложность алгоритма ===
<math>O(M\cdot N \cdot K)</math> при обработке K изображений размером M*N, так как все макроэлементы, составляющие структуру алгоритма, выполняются за константу для одного пикселя.

=== Информационный граф ===
Группы вершин:

1) выполняет операцию чтения изображения с диска. Количество вершин равно количеству изображений K.

2) выполняет горизонтальную свертку каждого изображения.

3) выполняет вертикальную свертку каждого изображения.

4) комбинирует частичные результаты.

5) записывает результат на диск.

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

Граф альтернативно можно представить и более детально, например, раскрыв макрооперации сверток изображения по строкам, столбцам, элементам ядер.

=== Ресурс параллелизма алгоритма ===
Группы параллельных ветвей:

1) Операции над разными изображениями независимы и образуют массово параллельные ветви.

2) Одномерные свертки в разложении двумерной могут считаться независимо. Это конечный параллелизм.

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

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

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

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

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

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

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

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

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

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

- последовательные реализации (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.

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

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

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

Описание параллельной реализации алгоритма фильтрации Собеля.

Автор: А.Г.Лыжов (401 группа).

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Фильтр Собеля - дискретный дифференциальный оператор, который используется для приближения градиента яркости изображения. Он часто используется в алгоритмах выделения границ при обработке изображений. Фильтр Собеля был предложен Ирвином Собелем и Гэри Фелдманом в лаборатории искусственного интеллекта Стэнфорда в 1968.

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

=== Математическое описание алгоритма ===
Исходные данные:

* изображение <math>A^{N\cdot M}</math>

Вычисляемые данные:

* матрица аппроксимации модуля градиента <math>G^{N\cdot M}</math>

* матрица аппроксимации направления градиента <math>\Theta^{N\cdot M}</math>

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

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

<math>
\mathbf{G}_x = \begin{bmatrix}
+1 & 0 & -1 \\
+2 & 0 & -2 \\
+1 & 0 & -1
\end{bmatrix} * \mathbf{A}
,\
\mathbf{G}_y = \begin{bmatrix}
+1 & +2 & +1\\
0 & 0 & 0 \\
-1 & -2 & -1
\end{bmatrix} * \mathbf{A}
</math>

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

<math>\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }</math>

<math>\mathbf{\Theta} = \operatorname{atan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро совпадает с алгоритмом, так как все описанные операции выполняются за <math>O(M\cdot N)</math> на одном изображении.

=== Макроструктура алгоритма ===
Макроструктуру в основном составляют:

1) двумерные свертки, приведенные в математическом описании;

2) операция поэлементного геометрического среднего между промежуточными аппроксимациями.

Эти элементы алгоритма приведены в разделе с математическим описанием.

=== Схема реализации последовательного алгоритма ===
Запись на C++-подобном псевдокоде:
<pre>float *sobel(float *img) {
// diff_kernel is [1, 0, -1]; sum_kernel is [1, 2, 1]
horiz_der = conv(img, diff_kernel, sum_kernel);
vert_der = conv(img, sum_kernel, diff_kernel);
return combine_horiz_vert(horiz_der, vert_der);
}

for (int i = 0; i < n_images; i++) {
img = get_input(i);
res = sobel(img);
write_result(res);
}</pre>

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

=== Последовательная сложность алгоритма ===
<math>O(M\cdot N \cdot K)</math> при обработке K изображений размером M*N, так как все макроэлементы, составляющие структуру алгоритма, выполняются за константу для одного пикселя.

=== Информационный граф ===
Группы вершин:

1) выполняет операцию чтения изображения с диска. Количество вершин равно количеству изображений K.

2) выполняет горизонтальную свертку каждого изображения.

3) выполняет вертикальную свертку каждого изображения.

4) комбинирует частичные результаты.

5) записывает результат на диск.

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

Граф альтернативно можно представить и более детально, например, раскрыв макрооперации сверток изображения по строкам, столбцам, элементам ядер.

=== Ресурс параллелизма алгоритма ===
Группы параллельных ветвей:

1) Операции над разными изображениями независимы и образуют массово параллельные ветви.

2) Одномерные свертки в разложении двумерной могут считаться независимо. Это конечный параллелизм.

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

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

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

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

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

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

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

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

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

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

- последовательные реализации (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

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

Описание параллельной реализации алгоритма фильтрации Собеля.

Автор: А.Г.Лыжов (401 группа).

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Фильтр Собеля - дискретный дифференциальный оператор, который используется для приближения градиента яркости изображения. Он часто используется в алгоритмах выделения границ при обработке изображений. Фильтр Собеля был предложен Ирвином Собелем и Гэри Фелдманом в лаборатории искусственного интеллекта Стэнфорда в 1968.

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

=== Математическое описание алгоритма ===
Исходные данные:

* изображение <math>A^{N\cdot M}</math>

Вычисляемые данные:

* матрица аппроксимации модуля градиента <math>G^{N\cdot M}</math>

* матрица аппроксимации направления градиента <math>\Theta^{N\cdot M}</math>

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

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

<math>
\mathbf{G}_x = \begin{bmatrix}
+1 & 0 & -1 \\
+2 & 0 & -2 \\
+1 & 0 & -1
\end{bmatrix} * \mathbf{A}
,\
\mathbf{G}_y = \begin{bmatrix}
+1 & +2 & +1\\
0 & 0 & 0 \\
-1 & -2 & -1
\end{bmatrix} * \mathbf{A}
</math>

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

<math>\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }</math>

<math>\mathbf{\Theta} = \operatorname{atan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро совпадает с алгоритмом, так как все описанные операции выполняются за <math>O(M\cdot N)</math> на одном изображении.

=== Макроструктура алгоритма ===
Макроструктуру в основном составляют:

1) двумерные свертки, приведенные в математическом описании;

2) операция поэлементного геометрического среднего между промежуточными аппроксимациями.

Эти элементы алгоритма приведены в разделе с математическим описанием.

=== Схема реализации последовательного алгоритма ===
Запись на C++-подобном псевдокоде:
<pre>float *sobel(float *img) {
// diff_kernel is [1, 0, -1]; sum_kernel is [1, 2, 1]
horiz_der = conv(img, diff_kernel, sum_kernel);
vert_der = conv(img, sum_kernel, diff_kernel);
return combine_horiz_vert(horiz_der, vert_der);
}

for (int i = 0; i < n_images; i++) {
img = get_input(i);
res = sobel(img);
write_result(res);
}</pre>

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

=== Последовательная сложность алгоритма ===
<math>O(M\cdot N \cdot K)</math> при обработке K изображений размером M*N, так как все макроэлементы, составляющие структуру алгоритма, выполняются за константу для одного пикселя.

=== Информационный граф ===
Группы вершин:

1) выполняет операцию чтения изображения с диска. Количество вершин равно количеству изображений K.

2) выполняет горизонтальную свертку каждого изображения.

3) выполняет вертикальную свертку каждого изображения.

4) комбинирует частичные результаты.

5) записывает результат на диск.

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

Граф альтернативно можно представить и более детально, например, раскрыв макрооперации сверток изображения по строкам, столбцам, элементам ядер.

=== Ресурс параллелизма алгоритма ===
Группы параллельных ветвей:

1) Операции над разными изображениями независимы и образуют массово параллельные ветви.

2) Одномерные свертки в разложении двумерной могут считаться независимо. Это конечный параллелизм.

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

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

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

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

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

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

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

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

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

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

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

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

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

2017-12-02T17:09:59Z

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

Описание параллельной реализации алгоритма фильтрации Собеля.

Автор: А.Г.Лыжов (401 группа).

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Фильтр Собеля - дискретный дифференциальный оператор, который используется для приближения градиента яркости изображения. Он часто используется в алгоритмах выделения границ при обработке изображений. Фильтр Собеля был предложен Ирвином Собелем и Гэри Фелдманом в лаборатории искусственного интеллекта Стэнфорда в 1968.

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

=== Математическое описание алгоритма ===
Исходные данные:

* изображение <math>A^{N\cdot M}</math>

Вычисляемые данные:

* матрица аппроксимации модуля градиента <math>G^{N\cdot M}</math>

* матрица аппроксимации направления градиента <math>\Theta^{N\cdot M}</math>

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

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

<math>
\mathbf{G}_x = \begin{bmatrix}
+1 & 0 & -1 \\
+2 & 0 & -2 \\
+1 & 0 & -1
\end{bmatrix} * \mathbf{A}
,\
\mathbf{G}_y = \begin{bmatrix}
+1 & +2 & +1\\
0 & 0 & 0 \\
-1 & -2 & -1
\end{bmatrix} * \mathbf{A}
</math>

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

<math>\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }</math>

<math>\mathbf{\Theta} = \operatorname{atan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро совпадает с алгоритмом, так как все описанные операции выполняются за <math>O(M\cdot N)</math> на одном изображении.

=== Макроструктура алгоритма ===
Макроструктуру в основном составляют:

1) двумерные свертки, приведенные в математическом описании;

2) операция поэлементного геометрического среднего между промежуточными аппроксимациями.

Эти элементы алгоритма приведены в разделе с математическим описанием.

=== Схема реализации последовательного алгоритма ===
Запись на C++-подобном псевдокоде:
<pre>float *sobel(float *img) {
// diff_kernel is [1, 0, -1]; sum_kernel is [1, 2, 1]
horiz_der = conv(img, diff_kernel, sum_kernel);
vert_der = conv(img, sum_kernel, diff_kernel);
return combine_horiz_vert(horiz_der, vert_der);
}

for (int i = 0; i < n_images; i++) {
img = get_input(i);
res = sobel(img);
write_result(res);
}</pre>

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

=== Последовательная сложность алгоритма ===
<math>O(M\cdot N \cdot K)</math> при обработке K изображений размером M*N, так как все макроэлементы, составляющие структуру алгоритма, выполняются за константу для одного пикселя.

=== Информационный граф ===
Группы вершин:

1) выполняет операцию чтения изображения с диска. Количество вершин равно количеству изображений K.

2) выполняет горизонтальную свертку каждого изображения.

3) выполняет вертикальную свертку каждого изображения.

4) комбинирует частичные результаты.

5) записывает результат на диск.

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

Граф альтернативно можно представить и более детально, например, раскрыв макрооперации сверток изображения по строкам, столбцам, элементам ядер.

=== Ресурс параллелизма алгоритма ===
Группы параллельных ветвей:

1) Операции над разными изображениями независимы и образуют массово параллельные ветви.

2) Одномерные свертки в разложении двумерной могут считаться независимо. Это конечный параллелизм.

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

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

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
График сильной масштабируемости:

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

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

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

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

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

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

Файл:Strong.PNG

2017-12-02T17:09:02Z

Nikkou:

Файл:Weak.PNG

2017-12-02T17:08:08Z

Nikkou:

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

2017-12-02T17:06:30Z

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

Описание параллельной реализации алгоритма фильтрации Собеля.

Автор: А.Г.Лыжов (401 группа).

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Фильтр Собеля - дискретный дифференциальный оператор, который используется для приближения градиента яркости изображения. Он часто используется в алгоритмах выделения границ при обработке изображений. Фильтр Собеля был предложен Ирвином Собелем и Гэри Фелдманом в лаборатории искусственного интеллекта Стэнфорда в 1968.

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

=== Математическое описание алгоритма ===
Исходные данные:

* изображение <math>A^{N\cdot M}</math>

Вычисляемые данные:

* матрица аппроксимации модуля градиента <math>G^{N\cdot M}</math>

* матрица аппроксимации направления градиента <math>\Theta^{N\cdot M}</math>

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

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

<math>
\mathbf{G}_x = \begin{bmatrix}
+1 & 0 & -1 \\
+2 & 0 & -2 \\
+1 & 0 & -1
\end{bmatrix} * \mathbf{A}
,\
\mathbf{G}_y = \begin{bmatrix}
+1 & +2 & +1\\
0 & 0 & 0 \\
-1 & -2 & -1
\end{bmatrix} * \mathbf{A}
</math>

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

<math>\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }</math>

<math>\mathbf{\Theta} = \operatorname{atan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро совпадает с алгоритмом, так как все описанные операции выполняются за <math>O(M\cdot N)</math> на одном изображении.

=== Макроструктура алгоритма ===
Макроструктуру в основном составляют:

1) двумерные свертки, приведенные в математическом описании;

2) операция поэлементного геометрического среднего между промежуточными аппроксимациями.

Эти элементы алгоритма приведены в разделе с математическим описанием.

=== Схема реализации последовательного алгоритма ===
Запись на C++-подобном псевдокоде:
<pre>float *sobel(float *img) {
// diff_kernel is [1, 0, -1]; sum_kernel is [1, 2, 1]
horiz_der = conv(img, diff_kernel, sum_kernel);
vert_der = conv(img, sum_kernel, diff_kernel);
return combine_horiz_vert(horiz_der, vert_der);
}

for (int i = 0; i < n_images; i++) {
img = get_input(i);
res = sobel(img);
write_result(res);
}</pre>

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

=== Последовательная сложность алгоритма ===
<math>O(M\cdot N \cdot K)</math> при обработке K изображений размером M*N, так как все макроэлементы, составляющие структуру алгоритма, выполняются за константу для одного пикселя.

=== Информационный граф ===
Группы вершин:

1) выполняет операцию чтения изображения с диска. Количество вершин равно количеству изображений K.

2) выполняет горизонтальную свертку каждого изображения.

3) выполняет вертикальную свертку каждого изображения.

4) комбинирует частичные результаты.

5) записывает результат на диск.

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

Граф альтернативно можно представить и более детально, например, раскрыв макрооперации сверток изображения по строкам, столбцам, элементам ядер.

=== Ресурс параллелизма алгоритма ===
Группы параллельных ветвей:

1) Операции над разными изображениями независимы и образуют массово параллельные ветви.

2) Одномерные свертки в разложении двумерной могут считаться независимо. Это конечный параллелизм.

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

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

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

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

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

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

2017-12-02T16:59:29Z

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

Описание параллельной реализации алгоритма фильтрации Собеля.

Автор: А.Г.Лыжов (401 группа).

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Фильтр Собеля - дискретный дифференциальный оператор, который используется для приближения градиента яркости изображения. Он часто используется в алгоритмах выделения границ при обработке изображений. Фильтр Собеля был предложен Ирвином Собелем и Гэри Фелдманом в лаборатории искусственного интеллекта Стэнфорда в 1968.

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

=== Математическое описание алгоритма ===
Исходные данные:

* изображение <math>A^{N\cdot M}</math>

Вычисляемые данные:

* матрица аппроксимации модуля градиента <math>G^{N\cdot M}</math>

* матрица аппроксимации направления градиента <math>\Theta^{N\cdot M}</math>

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

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

<math>
\mathbf{G}_x = \begin{bmatrix}
+1 & 0 & -1 \\
+2 & 0 & -2 \\
+1 & 0 & -1
\end{bmatrix} * \mathbf{A}
,\
\mathbf{G}_y = \begin{bmatrix}
+1 & +2 & +1\\
0 & 0 & 0 \\
-1 & -2 & -1
\end{bmatrix} * \mathbf{A}
</math>

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

<math>\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }</math>

<math>\mathbf{\Theta} = \operatorname{atan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро совпадает с алгоритмом, так как все описанные операции выполняются за <math>O(M\cdot N)</math> на одном изображении.

=== Макроструктура алгоритма ===
Макроструктуру в основном составляют:

1) двумерные свертки, приведенные в математическом описании;

2) операция поэлементного геометрического среднего между промежуточными аппроксимациями.

Эти элементы алгоритма приведены в разделе с математическим описанием.

=== Схема реализации последовательного алгоритма ===
Запись на C++-подобном псевдокоде:
<pre>float *sobel(float *img) {
// diff_kernel is [1, 0, -1]; sum_kernel is [1, 2, 1]
horiz_der = conv(img, diff_kernel, sum_kernel);
vert_der = conv(img, sum_kernel, diff_kernel);
return combine_horiz_vert(horiz_der, vert_der);
}

for (int i = 0; i < n_images; i++) {
img = get_input(i);
res = sobel(img);
write_result(res);
}</pre>

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

=== Последовательная сложность алгоритма ===
<math>O(M\cdot N \cdot K)</math> при обработке K изображений размером M*N, так как все макроэлементы, составляющие структуру алгоритма, выполняются за константу для одного пикселя.

=== Информационный граф ===
Группы вершин:

1) выполняет операцию чтения изображения с диска. Количество вершин равно количеству изображений K.

2) выполняет горизонтальную свертку каждого изображения.

3) выполняет вертикальную свертку каждого изображения.

4) комбинирует частичные результаты.

5) записывает результат на диск.

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

Граф альтернативно можно представить и более детально, например, раскрыв макрооперации сверток изображения по строкам, столбцам, элементам ядер.

=== Ресурс параллелизма алгоритма ===
Группы параллельных ветвей:

1) Операции над разными изображениями независимы и образуют массово параллельные ветви.

2) Одномерные свертки в разложении двумерной могут считаться независимо. Это конечный параллелизм.

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

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

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

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

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

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

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

2017-12-02T16:56:45Z

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

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

2017-12-02T16:56:00Z

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

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

2017-12-02T16:50:02Z

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

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

2017-12-02T16:45:50Z

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

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

2017-12-02T15:23:56Z

Nikkou: /* Схема реализации последовательного алгоритма */

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

2017-12-02T15:23:01Z

Nikkou:

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

2017-11-13T12:04:11Z

Nikkou: Новая страница: «Описание параллельной реализации алгоритма фильтрации Собеля. Автор: А.Г.Лыжов (401 групп…»

Фильтр Собеля

2017-10-17T17:44:11Z

Nikkou: /* Вычислительное ядро алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Фильтр Собеля - дискретный дифференциальный оператор, который используется для приближения градиента яркости изображения. Он часто используется в алгоритмах выделения границ при обработке изображений. Фильтр Собеля был предложен Ирвином Собелем и Гэри Фелдманом в лаборатории искусственного интеллекта Стэнфорда в 1968.

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

=== Математическое описание алгоритма ===
Исходные данные:

* изображение <math>A^{N\cdot M}</math>

Вычисляемые данные:

* матрица аппроксимации модуля градиента <math>G^{N\cdot M}</math>

* матрица аппроксимации направления градиента <math>\Theta^{N\cdot M}</math>

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

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

<math>
\mathbf{G}_x = \begin{bmatrix}
+1 & 0 & -1 \\
+2 & 0 & -2 \\
+1 & 0 & -1
\end{bmatrix} * \mathbf{A}
,\
\mathbf{G}_y = \begin{bmatrix}
+1 & +2 & +1\\
0 & 0 & 0 \\
-1 & -2 & -1
\end{bmatrix} * \mathbf{A}
</math>

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

<math>\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }</math>

<math>\mathbf{\Theta} = \operatorname{atan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right)</math>

=== Вычислительное ядро алгоритма ===
Вычислительное ядро совпадает с алгоритмом, так как все описанные операции выполняются за <math>O(M\cdot N)</math> на одном изображении.

=== Макроструктура алгоритма ===
=== Схема реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===
=== Информационный граф ===
=== Ресурс параллелизма алгоритма ===
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма ===

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

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

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

Фильтр Собеля

2017-10-17T17:40:14Z

Nikkou: /* Математическое описание алгоритма */

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
Фильтр Собеля - дискретный дифференциальный оператор, который используется для приближения градиента яркости изображения. Он часто используется в алгоритмах выделения границ при обработке изображений. Фильтр Собеля был предложен Ирвином Собелем и Гэри Фелдманом в лаборатории искусственного интеллекта Стэнфорда в 1968.

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

=== Математическое описание алгоритма ===
Исходные данные:

* изображение <math>A^{N\cdot M}</math>

Вычисляемые данные:

* матрица аппроксимации модуля градиента <math>G^{N\cdot M}</math>

* матрица аппроксимации направления градиента <math>\Theta^{N\cdot M}</math>

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

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

<math>
\mathbf{G}_x = \begin{bmatrix}
+1 & 0 & -1 \\
+2 & 0 & -2 \\
+1 & 0 & -1
\end{bmatrix} * \mathbf{A}
,\
\mathbf{G}_y = \begin{bmatrix}
+1 & +2 & +1\\
0 & 0 & 0 \\
-1 & -2 & -1
\end{bmatrix} * \mathbf{A}
</math>

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

<math>\mathbf{G} = \sqrt{ {\mathbf{G}_x}^2 + {\mathbf{G}_y}^2 }</math>

<math>\mathbf{\Theta} = \operatorname{atan}\left({ \mathbf{G}_y \over \mathbf{G}_x }\right)</math>

=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Схема реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===
=== Информационный граф ===
=== Ресурс параллелизма алгоритма ===
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма ===

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

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

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

Фильтр Собеля

2017-10-17T17:16:19Z

Nikkou: /* Общее описание алгоритма */

Фильтр Собеля

2017-10-17T17:06:10Z

Nikkou: Структурный шаблон

== Свойства и структура алгоритма ==
=== Общее описание алгоритма ===
=== Математическое описание алгоритма ===
=== Вычислительное ядро алгоритма ===
=== Макроструктура алгоритма ===
=== Схема реализации последовательного алгоритма ===
=== Последовательная сложность алгоритма ===
=== Информационный граф ===
=== Ресурс параллелизма алгоритма ===
=== Входные и выходные данные алгоритма ===
=== Свойства алгоритма ===

== Программная реализация алгоритма ==
=== Особенности реализации последовательного алгоритма ===
=== Локальность данных и вычислений ===
==== Локальность реализации алгоритма ====
===== Структура обращений в память и качественная оценка локальности =====
===== Количественная оценка локальности =====
=== Возможные способы и особенности параллельной реализации алгоритма ===
=== Масштабируемость алгоритма и его реализации ===
==== Масштабируемость алгоритма ====
==== Масштабируемость реализации алгоритма ====
=== Динамические характеристики и эффективность реализации алгоритма ===
=== Выводы для классов архитектур ===
=== Существующие реализации алгоритма ===

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

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

Структура описания свойств алгоритмов

2017-10-17T17:05:20Z

Nikkou: Статью следует удалить из-за ошибки в названии