Выравнивание горизонта в фото-сервисе gfranq.com

В фото-сервисе gfranq.com ^[1] появилась возможность выравнивания фотографий на произвольный угол! Данный угол рассчитывается автоматически, но при необходимости он может быть легко изменен и в ручную. Линию горизонта можно рисовать правой кнопкой мыши, а также обрабатываемая фотография может быть прямоугольной, в отличие от instagram. Более того, предусмотрена опция для сохранения исходного размера изображения или покрытия максимальной площади в повернутом изображении.

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

Метод автоматического выравнивания горизонта

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

1. Определение границ.
2. Определения прямых линий.
3. Вычисление наиболее интенсивной линии.
4. Расчет угла между найденной линией и центром изображения.
5. Поворот изображения на расчитанный угол.
6. Расчет максимального прямоугольника, вписанного в повернутое изображение.

Далее данные этапы будут рассмотрены подробно.

Определение границ (оператор Кэнни).

Для определения границ было решено использовать детектор границ Кэнни, исходя из субъективных и объективных соображений (о чем можно почитать в википедии ^[2]).
Алгоритм Кэнни состоит из следующих этапов:

1. Преобразование изображения в черно-белый формат.
2. Размытие изображения по Гауссу.
3. Поиск градиентов.
4. Подавление немаксимумов и трассировка области неоднозначности.

Определение прямых линий (преобразование Хафа).

После того как границы на изображении были найдены (резкие изменения яркости или другие неоднородности), к нему можно применить алгоритм выделения прямых линий, поскольку линия горизонта обычно выглядит как прямая или почти прямая линий (возможно с шумами). В качестве данного алгоритма было выбрано преобразование Хафа ^[3]. Однако данное преобразование может возвращать очень большое количество линий, кроме того, оно возвращает изображение (матрицу), в котором по горизонтали отсчитываются углы линий, а по вертикали — расстояние от центра до линии, что неудобно для дальнейших этапов. Для решения этих проблем, была написана функция преобразования линий из полярных координат в прямоугольные:

private static WeightedLine HoughLineToTwoPointLine(double theta, short radius, double intensity, int width, int height)
{
    int r = radius;
    double t = theta;

    if (r < 0)
    {
        t += 180;
        r = -r;
    }

    t = (t / 180) * Math.PI;
    int w2 = width / 2;
    int h2 = height / 2;
    double x0 = 0, x1 = 0, y0 = 0, y1 = 0;
    if (theta != 0)
    {
        x0 = -w2;
        x1 = w2;
		double sint = Math.Sin(t);
		double cost = Math.Cos(t);
        y0 = (-cost * x0 + r) / sint;
        y1 = (-cost * x1 + r) / sint;
    }
    else
    {
        x0 = radius;
        x1 = radius;
        y0 = h2;
        y1 = -h2;
    }

    return new WeightedLine(x0 + w2, h2 - y0, x1 + w2, h2 - y1, intensity);
}

Вычисление результирующего угла

Функция вычисления угла между перпендикулярами, проходящими через центр изображения с размерами width и height и линии с координатами x1, y1, x2, y2 и горизонтальной линии (проще говоря угол, на который нужно повернуть изображение, чтобы линия горизонта x1, y1, x2, y2 оказалась выровненной по горизонтали):

public static double CalculateAngle(int width, int height, double x1, double y1, double x2, double y2)
{
    double dx = x2 - x1;
    double dy = y2 - y1;
    double x3 = width / 2;
    double y3 = height / 2;
    double r = dx * dx + dy * dy;
    double nx = (dx * (x3 * dx - dy * y1) + dy * (dx * y3 + x1 * dy)) / r - x3;
    double ny = (dx * (y1 * dx - x1 * dy) + dy * (dx * x3 + dy * y3)) / r - y3;
    double result = Math.Atan2(ny, nx) + Math.PI / 2;
    if (result > Math.PI)
        result = result - Math.PI * 2;
    return result;
}

Стоит отметить, что если рассчитанный угол превышает определенное заданное значение поворота (в нашем случае это 45°), то автоматический поворот выполняться не будет.

Вычисление результирующего вписанного прямоугольника

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

Для решения этой задачи был найден соответствующий вопрос на stackoverflow и один из ответов был модифицирован в следующий код: ссылка на stackoverflow ^[4].

Для лучшего осознания вышеописанных этапов, я подготовил графическую иллюстрацию процесса:

Технические детали

Наш проект разработан таким образом, что код определенных модулей написан на C#, который компилируется как под .NET, так и под JavaScript, о чем было описано в одной из предыдущих статей ^[5]. Соответственно код и данного модуля также был написан на C#. Для этого пришлось использовать одномерные массивы вместо двухмерных, а также учитывать некоторые другие ограничения Script# ^[6].

Поворот изображений в Google Chrome

К сожалению, в Google Chrome существует баг, заключающийся в отсутствии сглаживания изображений на границах при трансформациях (например, поворотах), что наглядно продемонстрировано на рисунке ниже слева, при этом сами изображения интерполируются правильно. В других современных версиях браузеров (IE, Firefox, Safari, Opera) данный баг замечен ны был. Поэтому был придуман способ как этого избежать: можно просто рисовать прозрачную границу около изображения (т.е. размер изображения будет на 2 пикселя меньше) с помощью следующего кода:

context.draw(image, 1, 1, decImageWidth - 2 * 1, decImageHeight - 2 * 1);

Таким образом удалось достичь эффекта сглаживания во всех браузерах (рисунок ниже справа).

Заключение

С помощью варьирования коэффициентов в алгоритме определения границ и преобразования Хафа, удалось достичь приемлемого качества и скорости автоматического выравнивания, что было проверено на нескольких примерах изображений. А на тех изображениях, где метод отрабатывает неправильно, угол легко можно исправить в ручную двумя способами, в чем вы можете убедиться на нашем фото-сервисе gfranq.com ^[1], добавив новую или редактируя уже существующую фотографию.

На мобильных платформах (iOS ^[7] и Android ^[8]) функция выравнивания фотографий появится в ближайшем будущем.

Автор: KvanTTT

Источник ^[9]