Реализация алгоритма Преобразование Хафа (Hough Transform) (+визуализация работы)

    Не так давно я написал свою первую статью, благодаря которой стал полноценным хабражителем. Но все же метод, предложенный мною, калибрует со значительной ошибкой 5-7%, глупо терять на таком месте шанс на удачный результат. Поэтому решено было реализовать метод, опубликованный Vasyutka в этом топике, на который меня направил ZlodeiBaal, за что ему спасибо. Для реализации идеи использую кроссплатформенную обертку .NET над OpenCV — EMGU.

    Первым же делом предлагаю посмотреть, как он работает:



    Сам процесс визуализации длился около 6 — 8 часов, так как был взят небольшой шаг для θ, да и сделано все было для одного раза.

    Предполагается, что читатель знаком с алгоритмом. Если нет, то можно сделать это тут «Цифровая обработка изображений» Р. Гонсалес. Р. Вудс. Издание 3-е, 2012 г. страницы 848 — 854 или «Цифровая обработка изображений» Р. Гонсалес. Р. Вудс. 2005 г. Глава 10. В книгах написана исчерпывающая информация для написания программы.

    Постобработка


    Первым делом необходимо визуализировать прямые, сделать это можно с помощью трех операции:

                CvInvoke.GaussianBlur(gray, gray, new Size(3, 3), 0, 1, BorderType.Default);
                CvInvoke.Sobel(gray, gray, DepthType.Default, 0, 1, 3);
                CvInvoke.Canny(gray, gray, 70, 130);
    

    Сглаживание CvInvoke.GaussianBlur уберет лишние детали, оператор Собеля CvInvoke.Sobel с коэффициентом умножения по Kx = 0 и Ky = 1 визуализирует только горизонтальные линии, а оператор Кэнни CvInvoke.Canny окончательно выделит границы и бинаризирует изображение.

    Определение границ для ρ и θ


    public double SomeMethode(Image<Gray, byte> gray)
    {
                int D = (int)(Math.Sqrt(gray.Width * gray.Width + gray.Height * gray.Height));
                Image<Gray, int> houghSpace = new Image<Gray, int>(181, ((int)(1.414213562 * D) * 2) + 1);
    }
    

    houghSpace — аккумулятор значений, диапазон которого по θ [-90°, 90°], а по ρ — [-sqrt(2)*D, sqrt(2)*D] — где D — расстояние между двумя углами расположенных по диагонали.

    Кэшируем значение углов


    Все просто, кэшируем значение sinθ и cosθ. Где rad — шаг заполнения таблицы, на видео он был взят в 20 раз меньше, чем (Math.PI / 180).

    private double[,] CreateTable()
            {
                double[,] table = new double[2, 181]; // 0 - cos, 1 - sin;
                double rad = (Math.PI / 180);
                double theta = rad * -90;
                for (int i = 0; i < 181; i++)
                {
                    table[0, i] = Math.Cos(theta);
                    table[1, i] = Math.Sin(theta);
                    theta += rad;
                }
                return table;
            }
    

    Нахождения HotPoint'a


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

    public double SomeMethode(Image<Gray, byte> gray)
    {
                int D = (int)(Math.Sqrt(gray.Width * gray.Width + gray.Height * gray.Height));
                Image<Gray, int> houghSpace = new Image<Gray, int>(181, ((int)(1.414213562 * D) * 2) + 1);
                int xpoint = 0;
                double maxT = 0;
                double[,] table = CreateTable();
                for (int xi = 0; xi < gray.Width; xi++)
                    for (int yi = 0; yi < gray.Height; yi++)
                    {
                        if (gray[yi, xi].Intensity == 0) continue;
                        for (int i = 0; i < 181; i++)
                        {
                            int rho = (int)((xi * table[0, i] + yi * table[1, i])) + (houghSpace.Height / 2);
                            Gray g = new Gray(houghSpace[rho, i].Intensity + 1);
                            if (g.Intensity > maxT)
                            {
                                maxT = g.Intensity;
                                xpoint = i;
                            }
                            houghSpace [rho, i] = g;
                        }
                    }
    }
    


    Расчет угла поворота


                double thetaHotPoint = ((Math.PI / 180) * -90d) + (Math.PI / 180) * xpoint;
                return (90 - Math.Abs(thetaHotPoint) * (180 / Math.PI)) * (thetaHotPoint< 0 ? -1 : 1);
    

    Таким образом, мы получили угол, на который необходимо трансформировать изображение, чтобы самый длинный отрезок имел горизонтальное положение.
    • +15
    • 16,9k
    • 8
    Поделиться публикацией
    Ой, у вас баннер убежал!

    Ну. И что?
    Реклама
    Комментарии 8
      0
      Музыку к видео тоже выбирал ZlodeiBaal? Уж больно зловеще вышло…
        0
        Нет, чтобы на YouTube предложено из бесплатных, то и наложил не глядя=)
        0
        у меня сложилось впечатление, что преобрахование Хафа — довольно медленное.
        сколько идет обработка одной картинки? (кстати, какого они размера?)
          0
          Нет, все достаточно быстро при правильной реализации. Долго шел перерасчет тепла, так как с расчетом каждой точки тепло в некоторых точках изменялось. Расчет тепла ведется для изображения с разрешением 3801*516. Код статьи написан для наглядности, конечно стоит избавиться:
          Gray g = new Gray(houghSpace[rho, i].Intensity + 1);

          и обязательно, от:
          (houghSpace.Height / 2)

          Да, и OpenCL в помощь=))
            +1
                        int halfHeight = houghSpace.Height / 2;
                        int intensity = 0;
                        for (int xi = 0; xi < gray.Width; xi++)
                        {
                            for (int yi = 0; yi < gray.Height; yi++)
                            {
                                if (gray.Data[yi, xi, 0] == 0) continue;
                                for (int i = 0; i < 181; i++)
                                {
                                    int rho = (int)((xi * table[0, i] + yi * table[1, i])) + halfHeight;
                                    if ((intensity = houghSpace.Data[rho, i, 0]++) > maxT)
                                    {
                                        maxT = intensity;
                                        xpoint = i;
                                    }
                                }
                            }
                        }
            


            В таком виде, 90 — 70 мс для изображения 360*180.
              0
              хм, интересно!
              Спасибо!
            0
            Для несчастного Хафа тащить OpenCV?
            Да уж, вы, батенька, знаете толк в микроскопах!
              0
              В проекте используется каскад Хаара=)

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое