Skip to content

Latest commit

 

History

History
218 lines (178 loc) · 12.6 KB

File metadata and controls

218 lines (178 loc) · 12.6 KB

Автоматическое выравнивание горизонта на фотографиях

Дисклеймер. Оригинальная статья была написана в сентябре 2013 года, поэтому сейчас, в 2017 году, часть материала может быть не актуальна.

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

Данный метод был реализован в фото-сервисе gfranq.com в 2013 году.

Пример выравнивания

Этапы алгоритма

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

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

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

Определение границ

Для определения границ было решено использовать детектор границ Кэнни исходя из субъективных и объективных соображений.

Алгоритм Кэнни состоит из следующих этапов:

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

Поскольку алгоритм хорошо описан в Википедии, детали этапов не будут раскрываться.

Определение прямых линий

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

Более того, такое преобразование возвращает изображение (матрицу), в котором по горизонтали отсчитываются угловые коэффициенты линий, а по вертикали - расстояние от центра изображения до этих линий. Это создает неудобства при выполнении для дальнейших этапов. Для решения такой проблемы была написана функция преобразования полярных координат в прямоугольные:

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 и один из ответов был модифицирован в следующий код:

calculateLargestRect = function(angle, origWidth, origHeight) {
    var w0, h0;
    if (origWidth <= origHeight) {
        w0 = origWidth;
        h0 = origHeight;
    }
    else {
        w0 = origHeight;
        h0 = origWidth;
    }
    // Angle normalization in range [-PI..PI)
    var ang = angle - Math.floor((angle + Math.PI) / (2*Math.PI)) * 2*Math.PI;
    ang = Math.abs(ang);
    if (ang > Math.PI / 2)
        ang = Math.PI - ang;
    var sina = Math.sin(ang);
    var cosa = Math.cos(ang);
    var sinAcosA = sina * cosa;
    var w1 = w0 * cosa + h0 * sina;
    var h1 = w0 * sina + h0 * cosa;
    var c = h0 * sinAcosA / (2 * h0 * sinAcosA + w0);
    var x = w1 * c;
    var y = h1 * c;
    var w, h;
    if (origWidth <= origHeight) {
        w = w1 - 2 * x;
        h = h1 - 2 * y;
    }
    else {
        w = h1 - 2 * y;
        h = w1 - 2 * x;
    }
    return {
        w: w,
        h: h
    }
}

Для лучшего понимания работы метода автоматического выравнивания горизонта я подготовил графическую иллюстрацию процесса: Algorithm Steps

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

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

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

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

Сглаживание на повернутом изображении

Заключение

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