Участник:Artem.sevastopolsky/Преобразование Хаффа - История изменений

Artem.sevastopolsky в 15:48, 2 декабря 2016

2016-12-02T15:48:09Z

← Предыдущая версия		Версия от 15:48, 2 декабря 2016
Строка 2:		Строка 2:
	\| name = Преобразование Хаффа для поиска наиболее выраженных прямых линий на изображении		\| name = Преобразование Хаффа для поиска наиболее выраженных прямых линий на изображении
	\| serial_complexity = <math>O(NMK_\theta)</math>		\| serial_complexity = <math>O(NMK_\theta)</math>
	\| pf_height = <math>O(K_\theta + NM)</math>		\| pf_height = <math>O(1)</math> (с учетом блокировок чтения/записи памяти — <math>O(K_\theta + NM)</math>)
	\| pf_width = <math>O(NMK_\theta)</math>		\| pf_width = <math>O(NMK_\theta)</math>
	\| input_data = <math>O(NM)</math>		\| input_data = <math>O(NM)</math>

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

2016-11-21T05:56:27Z

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

← Предыдущая версия		Версия от 05:56, 21 ноября 2016
Строка 108:		Строка 108:
	[[file:Hough_strong_scaling_graph.png\|thumb\|center\|800px\|Рис. 2. График сильной масштабируемости]]		[[file:Hough_strong_scaling_graph.png\|thumb\|center\|800px\|Рис. 2. График сильной масштабируемости]]

	График сильной масштабируемости показывает, что чем больше используется потоков, тем выше производительность (и ниже время работы) алгоритма (за исключением случая, когда изображение малого размера). Тем не менее, стоит заметить, что при числе потоков большем, чем 8 или 16, рост производительности происходит медленнее, чем при числе потоков от 1 до 8 (но всё же линейно). ~~Единственная причина~~, по которой может наблюдаться такой эффект, — это необходимые блокировки для считывания и записи данных, находящихся в общей памяти. Как уже было отмечено в разделе [[#Ресурс параллелизма алгоритма]], эти операции увеличивают параллельную сложность, но данный эффект заметен только при достаточно большом числе потоков.		График сильной масштабируемости показывает, что чем больше используется потоков, тем выше производительность (и ниже время работы) алгоритма (за исключением случая, когда изображение малого размера). Тем не менее, стоит заметить, что при числе потоков большем, чем 8 или 16, рост производительности происходит медленнее, чем при числе потоков от 1 до 8 (но всё же линейно). Причина, по которой может наблюдаться такой эффект, — это необходимые блокировки для считывания и записи данных, находящихся в общей памяти. Как уже было отмечено в разделе [[#Ресурс параллелизма алгоритма]], эти операции увеличивают параллельную сложность, но данный эффект заметен только при достаточно большом числе потоков.

	Т. к. прирост производительности при числе потоков, много большем 16, по сравнению с числом потоков, равным 16, невелик, представляется разумным выбор числа потоков равным 16 или 32.		Т. к. прирост производительности при числе потоков, много большем 16, по сравнению с числом потоков, равным 16, невелик, представляется разумным выбор числа потоков равным 16 или 32.

Artem.sevastopolsky в 17:12, 20 ноября 2016

2016-11-20T17:12:41Z

← Предыдущая версия		Версия от 17:12, 20 ноября 2016
Строка 76:		Строка 76:

	[[file:HoughGraph.png\|thumb\|center\|800px\|Рис. 1. Информационный граф алгоритма преобразования Хаффа.]]		[[file:HoughGraph.png\|thumb\|center\|800px\|Рис. 1. Информационный граф алгоритма преобразования Хаффа.]]

			Стрелки из операций вычисления <math>\rho_t</math> в пиксели выходного изображения обозначают операцию инкремента (прибавления единицы в соответствующую ячейку аккумулятора). Параметр <math>\rho_t</math> и уровень квантования угла <math>t</math> влияет на выбор конкретной ячейки аккумулятора. Из каждого желтого круга выходит ровно одна стрелка в фиолетовый квадрат. В каждый фиолетовый квадрат может входить как 0, так и 1 или более стрелок.

	=== Ресурс параллелизма алгоритма ===		=== Ресурс параллелизма алгоритма ===
Строка 106:		Строка 108:
	[[file:Hough_strong_scaling_graph.png\|thumb\|center\|800px\|Рис. 2. График сильной масштабируемости]]		[[file:Hough_strong_scaling_graph.png\|thumb\|center\|800px\|Рис. 2. График сильной масштабируемости]]

	График сильной масштабируемости показывает, что чем больше используется потоков, тем выше производительность (и ниже время работы) алгоритма. Тем не менее, стоит заметить, что при числе потоков большем, чем 8 или 16, рост производительности происходит медленнее, чем при числе потоков от 1 до 8 (но всё же линейно). Единственная причина, по которой может наблюдаться такой эффект, — это необходимые блокировки для считывания и записи данных, находящихся в общей памяти. Как уже было отмечено в разделе [[#Ресурс параллелизма алгоритма]], эти операции увеличивают параллельную сложность, но данный эффект заметен только при достаточно большом числе потоков.		График сильной масштабируемости показывает, что чем больше используется потоков, тем выше производительность (и ниже время работы) алгоритма (за исключением случая, когда изображение малого размера). Тем не менее, стоит заметить, что при числе потоков большем, чем 8 или 16, рост производительности происходит медленнее, чем при числе потоков от 1 до 8 (но всё же линейно). Единственная причина, по которой может наблюдаться такой эффект, — это необходимые блокировки для считывания и записи данных, находящихся в общей памяти. Как уже было отмечено в разделе [[#Ресурс параллелизма алгоритма]], эти операции увеличивают параллельную сложность, но данный эффект заметен только при достаточно большом числе потоков.

			Т. к. прирост производительности при числе потоков, много большем 16, по сравнению с числом потоков, равным 16, невелик, представляется разумным выбор числа потоков равным 16 или 32.

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

Artem.sevastopolsky: Раздел масштабируемости

2016-11-20T16:39:32Z

Раздел масштабируемости

← Предыдущая версия		Версия от 16:39, 20 ноября 2016
Строка 73:		Строка 73:
	=== Информационный граф ===		=== Информационный граф ===

	На ~~рисунке ниже~~ показан информационный граф алгоритма с расшифровкой условных обозначений операций. Т. к. все пиксели изображения обрабатываются одинаково, входные и выходные данные алгоритма расположены на рисунке так, как расположены пиксели изображений при их вытягивании в длинный вектор. Это также сделано для упрощения иллюстрации.		На Рис. 1 показан информационный граф алгоритма с расшифровкой условных обозначений операций. Т. к. все пиксели изображения обрабатываются одинаково, входные и выходные данные алгоритма расположены на рисунке так, как расположены пиксели изображений при их вытягивании в длинный вектор. Это также сделано для упрощения иллюстрации.

	[[file:HoughGraph.png\|thumb\|center\|800px\|Рис. 1. Информационный граф алгоритма преобразования Хаффа.]]		[[file:HoughGraph.png\|thumb\|center\|800px\|Рис. 1. Информационный граф алгоритма преобразования Хаффа.]]
Строка 101:		Строка 101:
	=== Возможные способы и особенности параллельной реализации алгоритма ===		=== Возможные способы и особенности параллельной реализации алгоритма ===
	=== Масштабируемость алгоритма и его реализации ===		=== Масштабируемость алгоритма и его реализации ===

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

			[[file:Hough_strong_scaling_graph.png\|thumb\|center\|800px\|Рис. 2. График сильной масштабируемости]]

			График сильной масштабируемости показывает, что чем больше используется потоков, тем выше производительность (и ниже время работы) алгоритма. Тем не менее, стоит заметить, что при числе потоков большем, чем 8 или 16, рост производительности происходит медленнее, чем при числе потоков от 1 до 8 (но всё же линейно). Единственная причина, по которой может наблюдаться такой эффект, — это необходимые блокировки для считывания и записи данных, находящихся в общей памяти. Как уже было отмечено в разделе [[#Ресурс параллелизма алгоритма]], эти операции увеличивают параллельную сложность, но данный эффект заметен только при достаточно большом числе потоков.

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

Artem.sevastopolsky: Добавлен инф. граф

2016-11-20T15:12:18Z

Добавлен инф. граф

← Предыдущая версия		Версия от 15:12, 20 ноября 2016
Строка 72:		Строка 72:

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

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

			[[file:HoughGraph.png\|thumb\|center\|800px\|Рис. 1. Информационный граф алгоритма преобразования Хаффа.]]

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

Artem.sevastopolsky в 15:03, 20 ноября 2016

2016-11-20T15:03:14Z

← Предыдущая версия		Версия от 15:03, 20 ноября 2016
Строка 2:		Строка 2:
	\| name = Преобразование Хаффа для поиска наиболее выраженных прямых линий на изображении		\| name = Преобразование Хаффа для поиска наиболее выраженных прямых линий на изображении
	\| serial_complexity = <math>O(NMK_\theta)</math>		\| serial_complexity = <math>O(NMK_\theta)</math>
	\| pf_height = <math>O(1)</math>		\| pf_height = <math>O(K_\theta + NM)</math>
	\| pf_width = <math>O(NMK_\theta)</math>		\| pf_width = <math>O(NMK_\theta)</math>
	\| input_data = <math>O(NM)</math>		\| input_data = <math>O(NM)</math>
Строка 25:		Строка 25:
	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===

	Пусть имеется бинарное изображение <math>I(i, j), i \in \overline{0, N - 1}, j \in \overline{0, M - 1}</math> (интенсивность каждого пикселя равна либо нулю, либо единице). Преобразование Хаффа заключается в построении специального изображения — ''аккумулятора'' — по исходному изображению. Пространство, которому принадлежит аккумулятор, называют ''пространством Хаффа''. Обозначим аккумулятор через <math>A(\rho, \theta), \rho \in \overline{0, K_{\rho} - 1}, j \in \overline{0, K_{\theta} - 1}</math>. <math>K_{\rho}</math> выбирают равным <math>2\sqrt{N^2 + M^2}</math> для простоты реализации и наибольшей точности (тем не менее, можно переписать алгоритм так, чтобы <math>K_{\rho}</math> было произвольным, возможно, не зависящим от <math>N, M</math>). <math>K_{\theta}</math> выбирают произвольной константой, но наиболее естественным является выбор <math>K_{\theta}</math> (по одному уровню ~~квантованию~~ на каждый градус угла).		Пусть имеется бинарное изображение <math>I(i, j), i \in \overline{0, N - 1}, j \in \overline{0, M - 1}</math> (интенсивность каждого пикселя равна либо нулю, либо единице). Преобразование Хаффа заключается в построении специального изображения — ''аккумулятора'' — по исходному изображению. Пространство, которому принадлежит аккумулятор, называют ''пространством Хаффа''. Обозначим аккумулятор через <math>A(\rho, \theta), \rho \in \overline{0, K_{\rho} - 1}, j \in \overline{0, K_{\theta} - 1}</math>. <math>K_{\rho}</math> выбирают равным <math>\lceil 2 \cdot \sqrt{N^2 + M^2} \rceil</math> для простоты реализации и наибольшей точности (тем не менее, можно переписать алгоритм так, чтобы <math>K_{\rho}</math> было произвольным, возможно, не зависящим от <math>N, M</math>). <math>K_{\theta}</math> выбирают произвольной константой, но наиболее естественным является выбор <math>K_{\theta} = 180</math> (по одному уровню квантования на каждый градус угла).

	Каждый элемент аккумулятора отвечает определённой прямой линии: элемент <math>A(\rho + \sqrt{N^2 + M^2}, \theta)</math> соответствует прямой, имеющей уравнение <math>x\cos\theta + y\sin\theta = \rho.</math> В таком уравнении прямой <math>\rho</math> имеет смысл длины перпендикуляра (со знаком) к прямой от начала координат, <math>\theta</math> — угла между перпендикуляром и горизонтальной осью. Любая линия, проходящая через точки изображения, имеет единственную такую параметризацию.		Каждый элемент аккумулятора отвечает определённой прямой линии: элемент <math>A(\rho + \sqrt{N^2 + M^2}, \theta)</math> соответствует прямой, имеющей уравнение <math>x\cos\theta + y\sin\theta = \rho.</math> В таком уравнении прямой <math>\rho</math> имеет смысл длины перпендикуляра (со знаком) к прямой от начала координат, <math>\theta</math> — угла между перпендикуляром и горизонтальной осью. Любая линия, проходящая через точки изображения, имеет единственную такую параметризацию.
Строка 78:		Строка 78:

	* значение пикселя I[i][j] считывается из памяти атомарно,		* значение пикселя I[i][j] считывается из памяти атомарно,
	* значение пикселя A[\rho_t][t] инкрементируется атомарно,		* значение пикселя A[<math>\rho_t</math>][t] инкрементируется атомарно,
	* вычисление значения <math>\rho_t</math> производится внутри самого внутреннего цикла.		* вычисление значения <math>\rho_t</math> производится внутри самого внутреннего цикла.

	Для ускорения работы целесообразно подсчитать значения <math>\cos(\theta_t)</math> и <math>\sin(\theta_t)</math> для всех <math>t</math> заранее и сохранить в соответствующие массивы. В этом случае надо либо производить атомарные чтения из ~~этих массивов в общей памяти~~, либо скопировать эти массивы в память каждого потока.		Заметим, что высота ярусно-параллельной формы алгоритма является постоянной, т.е. параллельная сложность алгоритма составляет О(1) в терминах следующих операций: проверка условия (условный оператор), умножения, сложения, округления. Однако заметим, что параллельный алгоритм расчитан на обращение к изображению и аккумулятору, находящихся в общей памяти. Считывания памяти и записи в память необходимо производить атомарно, поэтому в терминах указанных операций и операций атомарного считывания/записи общей памяти параллельная сложность алгоритма составляет <math>O(K_\theta + NM)</math> (максимальное число одновременных обращений в общую память). Тем не менее, при числе потоков, много меньшем общего числа итераций циклов, и при случайном распределении задач по потокам можно считать, что на практике алгоритм имеет параллельную сложность О(1).

			Для ускорения работы целесообразно подсчитать значения <math>\cos(\theta_t)</math> и <math>\sin(\theta_t)</math> для всех <math>t</math> заранее и сохранить в соответствующие массивы. В этом случае надо либо расположить массивы в общей памяти и производить атомарные чтения из них, либо скопировать эти массивы в память каждого потока. Было исследовано, что последний вариант работает быстрее.

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

	* Входные данные алгоритма: бинарное изображение <math>I(i, j), i \in \overline{0, N - 1}, j \in \overline{0, M - 1}</math>.		* Входные данные алгоритма: бинарное изображение <math>I(i, j), i \in \overline{0, N - 1}, j \in \overline{0, M - 1}</math>.
	* Выходные данные алгоритма: аккумулятор <math>A(\rho, \theta), \rho \in \overline{0, \sqrt{N^2 + M^2} - 1}, j \in \overline{0, K_{\theta} - 1}</math>.		* Выходные данные алгоритма: аккумулятор <math>A(\rho, \theta), \rho \in \overline{0, \lceil 2 \cdot \sqrt{N^2 + M^2} \rceil - 1}, j \in \overline{0, K_{\theta} - 1}</math>, тип значения в ячейке — целочисленный.

	=== Свойства алгоритма ===		=== Свойства алгоритма ===
Строка 101:		Строка 103:
	Известные последовательные реализации алгоритма:		Известные последовательные реализации алгоритма:

	* [http://docs.opencv.org/2.4/doc/tutorials/imgproc/imgtrans/hough_lines/hough_lines.html OpenCV], реализует классическое и вероятностное преобразование Хаффа для прямых линий и окружностей. Библиотека имеет интерфейсы для C++ и Python.		* [http://docs.opencv.org/2.4/doc/tutorials/imgproc/imgtrans/hough_lines/hough_lines.html OpenCV] реализует классическое и вероятностное преобразование Хаффа для прямых линий и окружностей. Библиотека имеет интерфейсы для C++ и Python.
	* [http://scikit-image.org/docs/dev/api/skimage.transform.html Scikit-image], реализует классическое и вероятностное преобразование Хаффа для прямых линий, окружностей и эллипсов, а также функцию для выбора сильно отличающихся прямых по данным аккумулятора преобразования (skimage.transform.hough_line_peaks). Библиотека имеет интерфейс только для Python.		* [http://scikit-image.org/docs/dev/api/skimage.transform.html Scikit-image] реализует классическое и вероятностное преобразование Хаффа для прямых линий, окружностей и эллипсов, а также функцию для выбора сильно отличающихся прямых по данным аккумулятора преобразования (skimage.transform.hough_line_peaks). Библиотека имеет интерфейс только для Python.
	* [https://www.mathworks.com/help/images/ref/hough.html?requestedDomain=www.mathworks.com Встроенная реализация в Matlab] для поиска прямых линий. Также имеется [[https://www.mathworks.com/help/images/ref/imfindcircles.html реализация для поиска окружностей]].		* [https://www.mathworks.com/help/images/ref/hough.html?requestedDomain=www.mathworks.com Встроенная реализация в Matlab] для поиска прямых линий. Также имеется [https://www.mathworks.com/help/images/ref/imfindcircles.html реализация для поиска окружностей].

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

Artem.sevastopolsky: Добавил информацию о существующих реализациях

2016-11-19T20:42:50Z

Добавил информацию о существующих реализациях

← Предыдущая версия		Версия от 20:42, 19 ноября 2016
Строка 98:		Строка 98:
	=== Выводы для классов архитектур ===		=== Выводы для классов архитектур ===
	=== Существующие реализации алгоритма ===		=== Существующие реализации алгоритма ===

			Известные последовательные реализации алгоритма:

			* [http://docs.opencv.org/2.4/doc/tutorials/imgproc/imgtrans/hough_lines/hough_lines.html OpenCV], реализует классическое и вероятностное преобразование Хаффа для прямых линий и окружностей. Библиотека имеет интерфейсы для C++ и Python.
			* [http://scikit-image.org/docs/dev/api/skimage.transform.html Scikit-image], реализует классическое и вероятностное преобразование Хаффа для прямых линий, окружностей и эллипсов, а также функцию для выбора сильно отличающихся прямых по данным аккумулятора преобразования (skimage.transform.hough_line_peaks). Библиотека имеет интерфейс только для Python.
			* [https://www.mathworks.com/help/images/ref/hough.html?requestedDomain=www.mathworks.com Встроенная реализация в Matlab] для поиска прямых линий. Также имеется [[https://www.mathworks.com/help/images/ref/imfindcircles.html реализация для поиска окружностей]].

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

Artem.sevastopolsky в 20:30, 19 ноября 2016

2016-11-19T20:30:41Z

← Предыдущая версия		Версия от 20:30, 19 ноября 2016
Строка 2:		Строка 2:
	\| name = Преобразование Хаффа для поиска наиболее выраженных прямых линий на изображении		\| name = Преобразование Хаффа для поиска наиболее выраженных прямых линий на изображении
	\| serial_complexity = <math>O(NMK_\theta)</math>		\| serial_complexity = <math>O(NMK_\theta)</math>
	\| pf_height = <math>O(~~NMK_\theta~~)</math>		\| pf_height = <math>O(1)</math>
	\| pf_width = <math>O(1)</math>		\| pf_width = <math>O(NMK_\theta)</math>
	\| input_data = <math>O(NM)</math>		\| input_data = <math>O(NM)</math>
	\| output_data = <math>O(K_\theta \sqrt{N^2 + M^2})</math>		\| output_data = <math>O(K_\theta \sqrt{N^2 + M^2})</math>
Строка 14:		Строка 14:
	Преобразование Хаффа — это преобразование бинарного изображения, которое позволяет эффективно найти его наиболее выраженные прямые линии. Метод переводит бинарное изображение в изображение в специальном пространстве (''пространстве Хаффа''), в котором каждая ячейка отвечает за определённую линию. Преобразование было предложено П. Хаффом (P. Hough) в 1962 г. с целью создания метода для регистрации следов быстрых заряженных ионизирующих частиц в пузырьковой камере, и, потенциально, для поиска произвольных сложных шаблонов на фотографии.<ref>P. V. C. Hough, "Method and Means for Recognizing Complex Patterns", US Patent 3,069,654, Ser. No. 17,7156 Claims, 1962.</ref> В своём патенте П. Хафф предлагает электронную схему, реализация которой способна регистрировать следы пролетающих частиц, в то время как сам алгоритм в его современном описании был описан А. Розенфельдом (A. Rozenfeld) и другими математиками. Метод является одним из популярных и цитируемых методов в компьютерной графике.<ref>Hart, P. E., "How the Hough Transform was Invented", IEEE Signal Processing Magazine, Vol 26, Issue 6, pp 18 – 22 (November, 2009).</ref>		Преобразование Хаффа — это преобразование бинарного изображения, которое позволяет эффективно найти его наиболее выраженные прямые линии. Метод переводит бинарное изображение в изображение в специальном пространстве (''пространстве Хаффа''), в котором каждая ячейка отвечает за определённую линию. Преобразование было предложено П. Хаффом (P. Hough) в 1962 г. с целью создания метода для регистрации следов быстрых заряженных ионизирующих частиц в пузырьковой камере, и, потенциально, для поиска произвольных сложных шаблонов на фотографии.<ref>P. V. C. Hough, "Method and Means for Recognizing Complex Patterns", US Patent 3,069,654, Ser. No. 17,7156 Claims, 1962.</ref> В своём патенте П. Хафф предлагает электронную схему, реализация которой способна регистрировать следы пролетающих частиц, в то время как сам алгоритм в его современном описании был описан А. Розенфельдом (A. Rozenfeld) и другими математиками. Метод является одним из популярных и цитируемых методов в компьютерной графике.<ref>Hart, P. E., "How the Hough Transform was Invented", IEEE Signal Processing Magazine, Vol 26, Issue 6, pp 18 – 22 (November, 2009).</ref>

	Преобразование Хаффа используется в компьютерном зрении и цифровой обработке изображений для извлечения признаков из изображения. Алгоритм позволяет найти прямые линии, даже если разрывны, пересекаются другими ~~прямыми~~, являются частями более сложных линий, или если прямой принадлежат точки из разных частей изображения. В силу низкой вычислительной сложности (<math>O(NMK)</math>, где <math>N, M</math> — размеры изображения, <math>K</math> — число уровней квантования наклона прямой), алгоритм является одним из эффективных методов поиска прямых линий, и более эффективен, чем перебор по всевозможным линиям. Преобразование применяется к бинарному изображению, но его можно адаптировать для анализа произвольного черно-белого или цветного изображения, например, фотографии. Для этого необходимо применить к изображению любой детектор контуров, например, детектор Canny <ref>John Canny, A computational approach to edge detection, IEEE Transactions on pattern analysis		Преобразование Хаффа используется в компьютерном зрении и цифровой обработке изображений для извлечения признаков из изображения. Алгоритм позволяет найти прямые линии, даже если они разрывны, пересекаются с другими линиями, являются частями более сложных линий, или если прямой принадлежат точки из разных частей изображения. В силу низкой вычислительной сложности (<math>O(NMK)</math>, где <math>N, M</math> — размеры изображения, <math>K</math> — число уровней квантования наклона прямой), алгоритм является одним из эффективных методов поиска прямых линий, и более эффективен, чем перебор по всевозможным линиям. Преобразование применяется к бинарному изображению, но его можно адаптировать для анализа произвольного черно-белого или цветного изображения, например, фотографии. Для этого необходимо применить к изображению любой детектор контуров, например, детектор Canny <ref>John Canny, A computational approach to edge detection, IEEE Transactions on pattern analysis
	and machine intelligence (1986), no. 6, 679–698.</ref>, и далее работать с получившимся бинарным изображением.		and machine intelligence (1986), no. 6, 679–698.</ref>, и далее работать с получившимся бинарным изображением.

Строка 37:		Строка 37:
	для каждого j от 0 до <math>M</math> - 1		для каждого j от 0 до <math>M</math> - 1
	если I[i][j] не равно 0,		если I[i][j] не равно 0,
	<math>\rho_t := round(j \cdot \cos\theta_t + i \cdot \sin\theta_t + \sqrt{N^2 + M^2})</math>, где <math>round(x)</math> — функция округления числа <math>x</math>		<math>\rho_t := round(j \cdot \cos\theta_t + i \cdot \sin\theta_t + \sqrt{N^2 + M^2})</math>, где <math>round(x)</math> — функция округления числа <math>x</math> до ближайшего целого
	A[<math>\rho_t</math>][t] += 1		A[<math>\rho_t</math>][t] += 1

Строка 57:		Строка 57:
	=== Последовательная сложность алгоритма ===		=== Последовательная сложность алгоритма ===

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

	1. Загрузка изображения в оперативную память — <math>O(NM)</math>		1. Загрузка изображения в оперативную память — <math>O(NM)</math>
Строка 74:		Строка 74:

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

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

			* значение пикселя I[i][j] считывается из памяти атомарно,
			* значение пикселя A[\rho_t][t] инкрементируется атомарно,
			* вычисление значения <math>\rho_t</math> производится внутри самого внутреннего цикла.

			Для ускорения работы целесообразно подсчитать значения <math>\cos(\theta_t)</math> и <math>\sin(\theta_t)</math> для всех <math>t</math> заранее и сохранить в соответствующие массивы. В этом случае надо либо производить атомарные чтения из этих массивов в общей памяти, либо скопировать эти массивы в память каждого потока.

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

			* Входные данные алгоритма: бинарное изображение <math>I(i, j), i \in \overline{0, N - 1}, j \in \overline{0, M - 1}</math>.
			* Выходные данные алгоритма: аккумулятор <math>A(\rho, \theta), \rho \in \overline{0, \sqrt{N^2 + M^2} - 1}, j \in \overline{0, K_{\theta} - 1}</math>.

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

Artem.sevastopolsky: Добавил несколько подразделов

2016-11-19T19:39:16Z

Добавил несколько подразделов

Внесённые изменения

Artem.sevastopolsky: Добавлено мат. описание алгоритма

2016-11-19T17:59:44Z

Добавлено мат. описание алгоритма

← Предыдущая версия		Версия от 17:59, 19 ноября 2016
Строка 16:		Строка 16:
	Преобразование Хаффа используется в компьютерном зрении и цифровой обработке изображений для извлечения признаков из изображения. Алгоритм позволяет найти прямые линии, даже если разрывны, пересекаются другими прямыми, являются частями более сложных линий, или если прямой принадлежат точки из разных частей изображения. В силу низкой вычислительной сложности (<math>O(NMK)</math>, где <math>N, M</math> — размеры изображения, <math>K</math> — число уровней квантования наклона прямой), алгоритм является одним из эффективных методов поиска прямых линий, и более эффективен, чем перебор по всевозможным линиям.		Преобразование Хаффа используется в компьютерном зрении и цифровой обработке изображений для извлечения признаков из изображения. Алгоритм позволяет найти прямые линии, даже если разрывны, пересекаются другими прямыми, являются частями более сложных линий, или если прямой принадлежат точки из разных частей изображения. В силу низкой вычислительной сложности (<math>O(NMK)</math>, где <math>N, M</math> — размеры изображения, <math>K</math> — число уровней квантования наклона прямой), алгоритм является одним из эффективных методов поиска прямых линий, и более эффективен, чем перебор по всевозможным линиям.

	~~Также известно, что метод не является устойчивым к шуму на изображении. Кроме того, за~~ количество линий, которые считаются наиболее выраженными, отвечает значение специального порога, которое необходимо задать пользователю. Необходимость ручного подбора количества наиболее выраженных линий может считаться недостатком метода.		За количество линий, которые считаются наиболее выраженными, отвечает значение специального порога, которое необходимо задать пользователю. Необходимость ручного подбора количества наиболее выраженных линий может считаться недостатком метода.

	Метод имеет много модификаций, предназначенных для его ускорения или изменения его свойств. Одними из самых популярных модификаций алгоритма являются его варианты для поиска окружностей и эллипсов. Эти модификации обладают аналогичными свойствами и позволяют находить окружности и эллипсы, даже если на изображении они разрывны. Кроме того, возможен поиск более сложных аналитических кривых и кривых без параметризации (''Generalized Hough Transform''<ref>Hassanein A.S. et al., "A Survey on Hough Transform, Theory, Techniques and Applications", IJCSI Volume 12, Issue 1, January 2015</ref>).		Метод имеет много модификаций, предназначенных для его ускорения или изменения его свойств. Одними из самых популярных модификаций алгоритма являются его варианты для поиска окружностей и эллипсов. Эти модификации обладают аналогичными свойствами и позволяют находить окружности и эллипсы, даже если на изображении они разрывны. Кроме того, возможен поиск более сложных аналитических кривых и кривых без параметризации (''Generalized Hough Transform''<ref>Hassanein A.S. et al., "A Survey on Hough Transform, Theory, Techniques and Applications", IJCSI Volume 12, Issue 1, January 2015</ref>).

	Вычислительное ядро алгоритма представляет собой один тройной вложенный цикл, из тела которого производятся обращения записи в общую память, поэтому метод успешно подвергается распараллеливанию. При поиске кривой, параметризуемой <math>m</math> параметрами (<math>m=2</math> для прямой линии, <math>m=3</math> — для окружности, и т.д.), временная сложность повышается до <math>O(NMK^{m-1})</math> (при условии, что число уровней квантования всех параметров, кроме одного, равно <math>K</math>). Это представляет основную проблему применения метода на практике для сложных линий. Однако, т. к. вид алгоритма не меняется относительно алгоритма поиска прямых линий, модифицированный метод также допускает распараллеливание.		Вычислительное ядро алгоритма поиска прямых линий представляет собой один тройной вложенный цикл, из тела которого производятся обращения записи в общую память, поэтому метод успешно подвергается распараллеливанию. При поиске кривой, параметризуемой <math>m</math> параметрами (<math>m=2</math> для прямой линии, <math>m=3</math> — для окружности, и т.д.), временная сложность повышается до <math>O(NMK^{m-1})</math> (при условии, что число уровней квантования всех параметров, кроме одного, равно <math>K</math>). Это представляет основную проблему применения метода на практике для сложных линий. Однако, т. к. вид алгоритма не меняется относительно алгоритма поиска прямых линий, модифицированный метод также допускает распараллеливание.

	=== Математическое описание алгоритма ===		=== Математическое описание алгоритма ===

	~~Алгоритм имеет следующий вид:~~<~~ref~~>~~Hassanein A~~.S. ~~et al~~.~~, "~~A ~~Survey on Hough Transform~~, ~~Theory~~, ~~Techniques and Applications"~~, ~~IJCSI Volume 12~~, ~~Issue~~ 1, ~~January 2015~~</~~ref~~>		Пусть имеется бинарное изображение <math>I(i, j), i \in \overline{0, N - 1}, j \in \overline{0, M - 1}</math> (интенсивность каждого пикселя равна либо нулю, либо единице). Преобразование Хаффа заключается в построении специального изображения — ''аккумулятора'' — по исходному изображению. Пространство, которому принадлежит аккумулятор, называют ''пространством Хаффа''. Обозначим аккумулятор через <math>A(\rho, \theta), \rho \in \overline{0, K_{\rho} - 1}, j \in \overline{0, K_{\theta} - 1}</math>. <math>K_{\rho}</math> выбирают равным <math>2\sqrt{N^2 + M^2}</math> для простоты реализации и наибольшей точности (тем не менее, можно переписать алгоритм так, чтобы <math>K_{\rho}</math> было произвольным, возможно, не зависящим от <math>N, M</math>). <math>K_{\theta}</math> выбирают произвольной константой, но наиболее естественным является выбор math>K_{\theta}</math> (по одному уровню квантованию на каждый градус угла).

			Каждый элемент аккумулятора отвечает определённой прямой линии: элемент <math>A(\rho + \sqrt{N^2 + M^2}, \theta)</math> соответствует прямой, имеющей уравнение <math>x\cos\theta + y\sin\theta = \rho.</math> В таком уравнении прямой <math>\rho</math> имеет смысл длины перпендикуляра (со знаком) к прямой от начала координат, <math>\theta</math> — угла между перпендикуляром и горизонтальной осью. Любая линия, проходящая через точки изображения, имеет единственную такую параметризацию.

			Алгоритм преобразования изображения в пространство Хаффа имеет следующий вид:<ref>Hassanein A.S. et al., "A Survey on Hough Transform, Theory, Techniques and Applications", IJCSI Volume 12, Issue 1, January 2015</ref>

			А[i][j] := 0 для всех i, j;
			для каждого t от 0 до <math>K_{\theta}</math> - 1
			для каждого i от 0 до <math>N</math> - 1
			<math>\theta_t = -\frac{\pi}{2} + \frac{\pi \cdot i}{K_\rho}</math>
			для каждого j от 0 до <math>M</math> - 1
			если I[i][j] равно 0,
			<math>\rho_t = round(j \cdot \cos\theta_t + i \cdot \sin\theta_t + \sqrt{N^2 + M^2})</math>, где <math>round(x)</math> — функция округления числа <math>x</math>
			A[<math>\rho_t</math>][t] += 1

			После проведения указанных действий в массиве А содержится аккумулятор для изображения I. Для того чтобы получить наиболее выраженные прямые по данным из аккумулятора, необходимо взять <math>T</math> максимальных значений элементов аккумулятора и сопоставить им их прямые линии. Параметр метода <math>T</math> необходимо либо подобрать вручную, либо выбрать на основе значений аккумулятора.

	=== Вычислительное ядро алгоритма ===		=== Вычислительное ядро алгоритма ===