СПОСОБ И УСТРОЙСТВО ДЛЯ ОБНАРУЖЕНИЯ ПРЯМОЙ ЛИНИИ

1. Способ для обнаружения прямой линии, отличающийся тем, что способ содержит этапы, на которых:
- получают набор признаков гистограммы градиентов каждой из соответствующих пиксельных точек в изображении, при этом набор признаков гистограммы градиентов выполнен с возможностью отражать характеристики прямой линии локальной области, в которой расположена пиксельная точка;
- определяют по меньшей мере один возможный вариант направления прямой линии, которая должна обнаруживаться, согласно наборам признаков гистограммы градиентов соответствующих пиксельных точек; и
- определяют точное направление и точную позицию прямой линии, которая должна обнаруживаться, согласно по меньшей мере одному возможному варианту направления.
2. Способ по п. 1, отличающийся тем, что получение набора признаков гистограммы градиентов соответствующих пиксельных точек в изображении содержит этапы, на которых:
- для каждой пиксельной точки (i, j) из соответствующих пиксельных точек, вычисляют набор g(i, j) градиентов направления пиксельной точки, при этом набор g(i, j) градиентов направления включает в себя значения градиентов направления пиксельной точки в K направлениях, и значение градиента направления пиксельной точки в любом направлении означает абсолютное значение разности между значением полутонов пиксельной точки и значением полутонов смежной пиксельной точки в этом направлении, K≥2; и
- вычисляют набор h(i, j) признаков гистограммы градиентов пиксельной точки согласно набору g(i, j) градиентов направления пиксельной точки.
3. Способ по п. 2, отличающийся тем, что вычисление набора h(i, j) признаков гистограммы градиентов пиксельной точки согласно набору g(i, j) градиентов направления пиксельной точки содержит этапы, на которых:
- соответственно вычисляют значения  локального градиента пиксельной точки в K направлениях, при этом значение  локального градиента в k-направлении равно сумме значений градиентов направления всех пиксельных точек в локальной области, в которой расположена пиксельная точка, в k-направлении, и при этом k представляет направление;
norm
norm
- вычисляют среднее значение h(i, j) градиента пиксельной точки, при этом среднее значение h(i, j) градиента равно извлечению корня суммы квадратов соответствующих значений  локального градиента пиксельной точки;
norm
k
- делят значение  локального градиента на среднее значение h(i, j) градиента, чтобы получать признак h(i, j) гистограммы градиентов пиксельной точки в k-направлении; и
- определяют набор признаков гистограммы градиентов в K направлениях в качестве набора h(i, j) признаков гистограммы градиентов пиксельной точки.
4. Способ по п. 3, отличающийся тем, что способ дополнительно содержит этапы, на которых:
norm
norm
- для каждой пиксельной точки (i, j) из соответствующих пиксельных точек обнаруживают, меньше или нет среднее значение h(i, j) градиента предварительно определенного среднего значения T; и
norm
norm
- если результат обнаружения заключается в том, что среднее значение h(i, j) градиента меньше предварительно определенного среднего значения T, задают соответствующие признаки гистограммы градиентов в наборе h(i, j) признаков гистограммы градиентов пиксельной равными нулю.
5. Способ по п. 2, отличающийся тем, что определение по меньшей мере одного возможного варианта направления прямой линии, которая должна обнаруживаться, согласно наборам признаков гистограммы градиентов соответствующих пиксельных точек содержит этапы, на которых:
- для каждой из соответствующих пиксельных точек выбирают направление, соответствующее признаку гистограммы градиентов, имеющему максимальное значение в наборе признаков гистограммы градиентов, в качестве основного направления локальной области, в которой расположена пиксельная точка;
- проводят статистические вычисления числа голосов основных направлений локальных областей, в которых расположены соответствующие пиксельные точки в K направлениях; и
- выбирают направление, перпендикулярное направлению, имеющему число голосов, которое превышает пороговое значение числа голосов, в качестве возможного варианта направления прямой линии, которая должна обнаруживаться.
6. Способ по п. 3, отличающийся тем, что определение по меньшей мере одного возможного варианта направления прямой линии, которая должна обнаруживаться, согласно наборам признаков гистограммы градиентов соответствующих пиксельных точек содержит этапы, на которых:
- для каждой из соответствующих пиксельных точек, выбирают направление, соответствующее признаку гистограммы градиентов, имеющему максимальное значение в наборе признаков гистограммы градиентов, в качестве основного направления локальной области, в которой расположена пиксельная точка;
- проводят статистические вычисления числа голосов основных направлений локальных областей, в которых расположены соответствующие пиксельные точки в K направлениях; и
- выбирают направление, перпендикулярное направлению, имеющему число голосов, которое превышает пороговое значение числа голосов, в качестве возможного варианта направления прямой линии, которая должна обнаруживаться.
7. Способ по п. 4, отличающийся тем, что определение по меньшей мере одного возможного варианта направления прямой линии, которая должна обнаруживаться, согласно наборам признаков гистограммы градиентов соответствующих пиксельных точек содержит этапы, на которых:
- для каждой из соответствующих пиксельных точек, выбирают направление, соответствующее признаку гистограммы градиентов, имеющему максимальное значение в наборе признаков гистограммы градиентов, в качестве основного направления локальной области, в которой расположена пиксельная точка;
- проводят статистические вычисления числа голосов основных направлений локальных областей, в которых расположены соответствующие пиксельные точки в K направлениях; и
- выбирают направление, перпендикулярное направлению, имеющему число голосов, которое превышает пороговое значение числа голосов, в качестве возможного варианта направления прямой линии, которая должна обнаруживаться.
8. Способ по п. 1, отличающийся тем, что определение точного направления и позиции прямой линии, которая должна обнаруживаться, согласно по меньшей мере одному возможному варианту направления содержит этапы, на которых:
- для каждого из возможных вариантов направлений формируют по меньшей мере одну линию сканирования, параллельную возможному варианту направления;
- соответственно вычисляют совпадающее расстояние каждой линии сканирования, при этом совпадающее расстояние линии сканирования выполнено с возможностью отражать степень близости линии сканирования к прямой линии, которая должна обнаруживаться;
- выбирают линию сканирования, имеющую минимальное совпадающее расстояние, в качестве возможного варианта прямой линии; и
- определяют точное направление и позицию прямой линии, которая должна обнаруживаться, согласно возможному варианту прямой линии.
9. Способ по п. 8, отличающийся тем, что соответствующее вычисление совпадающего расстояния каждой линии сканирования содержит этапы, на которых:
- для каждой из линий сканирования, получают n точек выборки посредством дискретизации на линии сканирования, n≥1;
- вычисляют совпадающее расстояние между набором признаков гистограммы градиентов для каждой из соответствующих точек выборки и набором признаков гистограммы градиентов шаблонов в направлении, перпендикулярном возможному варианту направления; и
- суммируют совпадающие расстояния n точек выборки, чтобы получать совпадающее расстояние линии сканирования.
10. Способ по п. 8, отличающийся тем, что определение точного направления и позиции прямой линии, которая должна обнаруживаться, согласно возможному варианту прямой линии содержит этапы, на которых:
- формируют прямоугольную область, имеющую предварительно определенный размер, посредством использования возможного варианта прямой линии в качестве центральной оси;
- соответственно выбирают u точек и v точек на двух сторонах прямоугольной области, перпендикулярной возможному варианту прямой линии, и соединяют каждые две точки на двух сторонах с тем, чтобы получать u×v сегментов линии, u≥1, v≥1;
- соответственно вычисляют совпадающее расстояние каждого сегмента линии из u×v сегментов линии, при этом совпадающее расстояние сегмента линии выполнено с возможностью отражать степень близости сегмента линии к прямой линии, которая должна обнаруживаться; и
- выбирают прямую линию, которой принадлежит сегмент линии, имеющий минимальное совпадающее расстояние, в качестве прямой линии, которая должна обнаруживаться.
11. Способ по любому из п.п. 1-10, отличающийся тем, что способ дополнительно содержит этапы, на которых:
- для любой прямой линии, которая должна обнаруживаться, обнаруживают, существует или нет в изображении вторая прямая линия, которая должна обнаруживаться, которая удовлетворяет первому предварительно определенному условию, при этом первое предварительно определенное условие включает в себя то, что вторая прямая линия, которая должна обнаруживаться, и прямая линия, которая должна обнаруживаться, имеют точку пересечения внутри изображения, и угол между ними меньше порогового значения угла;
- если результат обнаружения заключается в том, что вторая прямая линия, которая должна обнаруживаться, которая удовлетворяет первому предварительно определенному условию, существует, добавляют вторую прямую линию, которая должна обнаруживаться, в набор возможных вариантов прямых линий;
- для любых двух из вторых прямых линий, которые должны обнаруживаться в наборе возможных вариантов прямых линий, обнаруживают, существует или нет третья прямая линия, которая должна обнаруживаться, которая удовлетворяет второму предварительно определенному условию, при этом второе предварительно определенное условие включает в себя то, что третья прямая линия, которая должна обнаруживаться, отличается от прямой линии, которая должна обнаруживаться, и третья прямая линия, которая должна обнаруживаться, пересекает обе из двух вторых прямых линий, которые должны обнаруживаться, с двумя точками пересечения внутри изображения;
- если результат обнаружения заключается в том, что третья прямая линия, которая должна обнаруживаться, которая удовлетворяет второму предварительно определенному условию, существует, добавляют четырехугольник, состоящий из прямой линии, которая должна обнаруживаться, двух вторых прямых линий, которые должны обнаруживаться, и третьей прямой линии, которая должна обнаруживаться, в набор возможных вариантов прямоугольников;
- для каждого четырехугольника в наборе возможных вариантов прямоугольников вычисляют совпадающее расстояние прямоугольника, при этом совпадающее расстояние четырехугольника выполнено с возможностью отражать степень близости четырехугольника к прямоугольнику, который должен обнаруживаться, и совпадающее расстояние четырехугольника равно сумме совпадающих расстояний сегментов линии, соответствующих четырем сторонам четырехугольника; и
- определяют четырехугольник, имеющий минимальное совпадающее расстояние или совпадающее расстояние, меньшее порогового значения для определения совпадения, в качестве прямоугольника, который должен обнаруживаться.
12. Устройство для обнаружения прямой линии, отличающееся тем, что устройство содержит:
- модуль получения признаков, выполненный с возможностью получать набор признаков гистограммы градиентов каждой из соответствующих пиксельных точек в изображении, при этом набор признаков гистограммы градиентов выполнен с возможностью отражать характеристики прямой линии локальной области, в которой расположена пиксельная точка;
- модуль определения возможных вариантов, выполненный с возможностью определять по меньшей мере один возможный вариант направления прямой линии, которая должна обнаруживаться, согласно наборам признаков гистограммы градиентов соответствующих пиксельных точек; и
- модуль определения точных показателей, выполненный с возможностью определять точное направление и точную позицию прямой линии, которая должна обнаруживаться, согласно по меньшей мере одному возможному варианту направления.
13. Устройство по п. 12, отличающееся тем, что модуль получения признаков включает в себя блок вычисления градиентов и блок вычисления признаков, при этом:
- блок вычисления градиентов выполнен с возможностью, для каждой пиксельной точки (i, j) из соответствующих пиксельных точек, вычислять набор g(i, j) градиентов направления пиксельной точки, при этом набор g(i, j) градиентов направления включает в себя значения градиентов направления пиксельной точки в K направлениях, и значение градиента направления пиксельной точки в любом направлении означает абсолютное значение разности между значением полутонов пиксельной точки и значением полутонов смежной пиксельной точки в этом направлении, K≥2, и
- блок вычисления признаков выполнен с возможностью вычислять набор h(i, j) признаков гистограммы градиентов пиксельной точки согласно набору g(i, j) градиентов направления пиксельной точки.
14. Устройство по п. 13, отличающееся тем, что блок вычисления признаков включает в себя субблок локальных градиентов, субблок средних градиентов, субблок вычисления признаков и субблок определения признаков, при этом:
- субблок локальных градиентов выполнен с возможностью соответственно вычислять значения  локального градиента пиксельной точки в K направлениях, при этом значение  локального градиента в k-направлении равно сумме значений градиентов направления всех пиксельных точек в k-направлении в локальной области, в которой расположена пиксельная точка, и при этом k представляет направление,
norm
norm
- субблок средних градиентов выполнен с возможностью вычислять среднее значение h(i, j) градиента пиксельной точки, при этом среднее значение h(i, j) градиента равно извлечению корня суммы квадратов соответствующих значений  локального градиента пиксельной точки,
norm
k
- субблок вычисления признаков выполнен с возможностью делить значение  локального градиента на среднее значение h(i, j) градиента, чтобы получать признак h(i, j) гистограммы градиентов пиксельной точки в k-направлении, и
- субблок определения признаков выполнен с возможностью определять набор признаков гистограммы градиентов в K направлениях в качестве набора h(i, j) признаков гистограммы градиентов пиксельной точки.
15. Устройство по п. 14, отличающееся тем, что устройство дополнительно включает в себя субблок обнаружения средних значений и субблок задания признаков равными нулю, при этом:
norm
norm
- субблок обнаружения средних значений выполнен с возможностью, для каждой пиксельной точки (i, j) из соответствующих пиксельных точек, обнаруживать, меньше или нет среднее значение h(i, j) градиента предварительно определенного среднего значения T, и
norm
norm
- субблок задания признаков равными нулю выполнен с возможностью задавать соответствующие признаки гистограммы градиентов в наборе h(i, j) признаков гистограммы градиентов пиксельной равными нулю, если результат обнаружения заключается в том, что среднее значение h(i, j) градиента меньше предварительно определенного среднего значения T.
16. Устройство по п. 13, отличающееся тем, что модуль определения возможных вариантов включает в себя блок выбора направлений, блок статистических вычислений числа голосов и блок выбора возможных вариантов, при этом:
- блок выбора направлений выполнен с возможностью, для каждой из соответствующих пиксельных точек, выбирать направление, соответствующее признаку гистограммы градиентов, имеющему максимальное значение в наборе признаков гистограммы градиентов, в качестве основного направления локальной области, в которой расположена пиксельная точка,
- блок статистических вычислений числа голосов выполнен с возможностью проводить статистические вычисления числа голосов основных направлений локальных областей, в которых расположены соответствующие пиксельные точки в K направлениях, и
- блок выбора возможных вариантов выполнен с возможностью выбирать направление, перпендикулярное направлению, имеющему число голосов, которое превышает пороговое значение числа голосов, в качестве возможного варианта направления прямой линии, которая должна обнаруживаться.
17. Устройство по п. 14, отличающееся тем, что модуль определения возможных вариантов включает в себя блок выбора направлений, блок статистических вычислений числа голосов и блок выбора возможных вариантов, при этом:
- блок выбора направлений выполнен с возможностью, для каждой из соответствующих пиксельных точек, выбирать направление, соответствующее признаку гистограммы градиентов, имеющему максимальное значение в наборе признаков гистограммы градиентов, в качестве основного направления локальной области, в которой расположена пиксельная точка,
- блок статистических вычислений числа голосов выполнен с возможностью проводить статистические вычисления числа голосов основных направлений локальных областей, в которых расположены соответствующие пиксельные точки в K направлениях, и
- блок выбора возможных вариантов выполнен с возможностью выбирать направление, перпендикулярное направлению, имеющему число голосов, которое превышает пороговое значение числа голосов, в качестве возможного варианта направления прямой линии, которая должна обнаруживаться.
18. Устройство по п. 15, отличающееся тем, что модуль определения возможных вариантов включает в себя блок выбора направлений, блок статистических вычислений числа голосов и блок выбора возможных вариантов, при этом:
- блок выбора направлений выполнен с возможностью, для каждой из соответствующих пиксельных точек, выбирать направление, соответствующее признаку гистограммы градиентов, имеющему максимальное значение в наборе признаков гистограммы градиентов, в качестве основного направления локальной области, в которой расположена пиксельная точка,
- блок статистических вычислений числа голосов выполнен с возможностью проводить статистические вычисления числа голосов основных направлений локальных областей, в которых расположены соответствующие пиксельные точки в K направлениях, и
- блок выбора возможных вариантов выполнен с возможностью выбирать направление, перпендикулярное направлению, имеющему число голосов, которое превышает пороговое значение числа голосов, в качестве возможного варианта направления прямой линии, которая должна обнаруживаться.
19. Устройство по п. 12, отличающееся тем, что модуль определения точных показателей включает в себя блок формирования сканирования, блок вычисления совпадения сканирований, блок выбора сканирования и блок определения точных показателей, при этом:
- блок формирования сканирования выполнен с возможностью, для каждого из возможных вариантов направлений, формировать по меньшей мере одну линию сканирования, параллельную возможному варианту направления,
- блок вычисления совпадения сканирований выполнен с возможностью соответственно вычислять совпадающее расстояние каждой линии сканирования, при этом совпадающее расстояние линии сканирования выполнено с возможностью отражать степень близости линии сканирования к прямой линии, которая должна обнаруживаться,
- блок выбора сканирования выполнен с возможностью выбирать линию сканирования, имеющую минимальное совпадающее расстояние, в качестве возможного варианта прямой линии, и
- блок определения точных показателей выполнен с возможностью определять точное направление и позицию прямой линии, которая должна обнаруживаться, согласно возможному варианту прямой линии.
20. Устройство по п. 19, отличающееся тем, что блок вычисления совпадения сканирований включает в себя субблок получения выборок, субблок вычисления совпадения выборок и субблок суммирования выборок, при этом:
- субблок получения выборок выполнен с возможностью, для каждой из линий сканирования, получения n точек выборки посредством дискретизации на линии сканирования, n≥1,
- субблок вычисления совпадения выборок выполнен с возможностью вычислять совпадающее расстояние между набором признаков гистограммы градиентов для каждой из соответствующих точек выборки и набором признаков гистограммы градиентов шаблонов в направлении, перпендикулярном возможному варианту направления, и
- субблок суммирования выборок выполнен с возможностью суммировать совпадающие расстояния n точек выборки, чтобы получать совпадающее расстояние линии сканирования.
21. Устройство по п. 19, отличающееся тем, что блок определения точных показателей включает в себя субблок формирования прямоугольников, субблок формирования сегментов линии, субблок вычисления совпадения сегментов линии и субблок выбора сегментов линии, при этом:
- субблок формирования прямоугольников выполнен с возможностью формировать прямоугольную область, имеющую предварительно определенный размер, посредством использования возможного варианта прямой линии в качестве центральной оси,
- субблок формирования сегментов линии выполнен с возможностью соответственно выбирать u точек и v точек на двух сторонах прямоугольной области, перпендикулярной возможному варианту прямой линии, и соединять каждые две точки на двух торонах, с тем чтобы получать u×v сегментов линии, u≥1, v≥1,
- субблок вычисления совпадения сегментов линии выполнен с возможностью соответственно вычислять совпадающее расстояние каждого сегмента линии из u×v сегментов линии, при этом совпадающее расстояние сегмента линии выполнено с возможностью отражать степень близости сегмента линии к прямой линии, которая должна обнаруживаться, и
- субблок выбора сегментов линии выполнен с возможностью выбирать прямую линию, которой принадлежит сегмент линии, имеющий минимальное совпадающее расстояние, в качестве прямой линии, которая должна обнаруживаться.
22. Устройство по любому из п.п. 12-21, отличающееся тем, что устройство дополнительно содержит:
- первый модуль обнаружения, выполненный с возможностью, для любой прямой линии, которая должна обнаруживаться, обнаруживать то, существует или нет в изображении вторая прямая линия, которая должна обнаруживаться, которая удовлетворяет первому предварительно определенному условию, при этом первое предварительно определенное условие включает в себя то, что вторая прямая линия, которая должна обнаруживаться, и прямая линия, которая должна обнаруживаться, имеют точку пересечения внутри изображения, и угол между ними меньше порогового значения угла;
- модуль возможных вариантов прямых линий, выполненный с возможностью добавлять вторую прямую линию, которая должна обнаруживаться, в набор возможных вариантов прямых линий, если результат обнаружения заключается в том, что вторая прямая линия, которая должна обнаруживаться, которая удовлетворяет первому предварительно определенному условию, существует; и
- второй модуль обнаружения, выполненный с возможностью, для любых двух из вторых прямых линий, которые должны обнаруживаться в наборе возможных вариантов прямых линий, обнаруживать то, существует или нет третья прямая линия, которая должна обнаруживаться, которая удовлетворяет второму предварительно определенному условию, при этом второе предварительно определенное условие включает в себя то, что третья прямая линия, которая должна обнаруживаться, отличается от прямой линии, которая должна обнаруживаться, и третья прямая линия, которая должна обнаруживаться, пересекает обе из двух вторых прямых линий, которые должны обнаруживаться, с двумя точками пересечения внутри изображения;
- модуль возможных вариантов прямоугольников, выполненный с возможностью добавлять четырехугольник, состоящий из прямой линии, которая должна обнаруживаться, двух вторых прямых линий, которые должны обнаруживаться, и третьей прямой линии, которая должна обнаруживаться, в набор возможных вариантов прямоугольников, если результат обнаружения заключается в том, что третья прямая линия, которая должна обнаруживаться, которая удовлетворяет второму предварительно определенному условию, существует;
- модуль вычисления совпадения, выполненный с возможностью, для каждого четырехугольника в наборе возможных вариантов прямоугольников, вычислять совпадающее расстояние прямоугольника, при этом совпадающее расстояние четырехугольника выполнено с возможностью отражать степень близости четырехугольника к прямоугольнику, который должен обнаруживаться, и совпадающее расстояние четырехугольника равно сумме совпадающих расстояний сегментов линии, соответствующих четырем сторонам четырехугольника; и
- модуль определения прямоугольников, выполненный с возможностью определять четырехугольник, имеющий минимальное совпадающее расстояние или совпадающее расстояние, меньшее порогового значения для определения совпадения, в качестве прямоугольника, который должен обнаруживаться.