На момент написания статьи я разрабатываю приложение для начинающих художников.
Одной из его функций является конструктор перспективы. С его помощью можно двигать точки схода, от которых исходят направляющие линии. Построенную сетку можно экспортировать как изображение.
Меня посетила мысль, что было бы здорово добавить возможность вставлять изображение из буфера обмена и автоматически генерировать для него перспективу.
Преобразование изображения
Текущее приложение я разрабатываю с использованием Compose Multiplatform под Android и Desktop. Чтобы поддерживать независимость от UI слоя, пришлось создать собственный класс для изображения – Image. Далее алгоритм по извлечению перспективы будет активно его использовать. Для оптимизации памяти и производительности информация о цвете пикселя хранится в виде одного числа в value-классе RGBPixel.
data class Image( val path: String, val width: Int, val height: Int, val pixels: List<RGBPixel> ) @JvmInline value class RGBPixel(private val packed: Int) { constructor(r: Int, g: Int, b: Int, a: Int = 255) : this( ((a and 0xFF) shl 24) or ((r and 0xFF) shl 16) or ((g and 0xFF) shl 8) or (b and 0xFF) ) val a: Int get() = (packed ushr 24) and 0xFF val r: Int get() = (packed shr 16) and 0xFF val g: Int get() = (packed shr 8) and 0xFF val b: Int get() = packed and 0xFF override fun toString(): String = "RGBPixel(r=$r, g=$g, b=$b)" }
Обработку по генерации перспективы я возложил на класс PerspectiveSceneExtractor, который обрабатывает изображение и возвращает список координат точек схода List<PerspectivePoint>.
Обычно линии объектов соединяются в определённые точки, но бывает, что линии от объектов идут параллельно, когда точка схода находится бесконечно далеко, например линия горизонта, у которой все горизонтальные линии уходят в бесконечность влево и вправо. Тогда нам необходимо знать под каким углом идут такие линии. Точки схода с определёнными координатами и для параллельных линий я решил хранить в одном классе PerspectivePoint, обозначив, что если точка схода бесконечно далеко, то её координаты будут равны Float.MAX_VALUE.
interface PerspectiveSceneExtractor { suspend fun extractPerspectiveScene(image: Image): List<PerspectivePoint> } data class PerspectivePoint( val x: Float, val y: Float, val direction: Float? = null ) { val isFinite: Boolean get() = x != Float.MAX_VALUE && y != Float.MAX_VALUE companion object { fun infinite(directionDegrees: Float) = PerspectivePoint(Float.MAX_VALUE, Float.MAX_VALUE, directionDegrees) } }
Далее рассмотрим сам алгоритм по извлечению перспективы.
Чтобы найти точки схода, требуется провести линии поверх объектов на изображении и найти места пересечения этих линий.
Чтобы чётко выделить границы объектов, сначала требуется преобразовать изображение в оттенки серого. Для этого я воспользовался стандартом Rec. 709, который учитывает особенности восприятия человеческим глазом. Коэффициенты 0.2126, 0.7152 и 0.0722 соответствуют вкладу красного, зелёного и синего каналов в воспринимаемую яркость.
У серого цвета значения red, green и blue одинаковые. Поэтому в целях оптимизации, я буду хранить значение цвета пикселя в виде одного числа Int, а всё изображение целиком – в классе-обёртке GrayImage.
data class GrayImage( val image: IntArray, val height: Int, val width: Int, ) private fun convertToGrayscale(image: Image): GrayImage { val gray = IntArray(image.width * image.height) { i -> val pixel = image.pixels[i] (0.2126 * pixel.r + 0.7152 * pixel.g + 0.0722 * pixel.b).toInt() } return GrayImage( image = gray, image.height, image.width ) }
Теперь когда изображение монохромное, мы можем обозначить границы объектов. Для этого я воспользовался оператором Собеля. Стоит отметить, что у этого алгоритма есть альтернативы, например оператор Кэнни, оператор Робертса и др.
Вкратце, суть оператора Собеля заключается в том, что мы проходим по каждому пикселю в изображении и сравниваем разность цветов его соседей. Если разность высокая, то в этом пикселе находится граница объекта. Если представлять визуально, то мы рисуем на черном фоне границы объектов белым цветом.
Для этого я написал метод detectEdges, в котором происходит обход по пикселям и вычисляются вертикальный и горизонтальные переходы цветов между соседними пикселями.
Затем мы сравниваем переход, если он превышает пороговое значение thresholdSq, то мы помечаем пиксель белым цветом. Если установить низкий порог, то в результате получится много "шума", если высокий, то потеряются слабые границы. Метод возвращает изображение в виде массива логических значений BlackWhiteImage, где true – наличие границы.
data class BlackWhiteImage( val image: BooleanArray, val height: Int, val width: Int, ) private fun detectEdges(grayImage: GrayImage): BlackWhiteImage { val edges = BooleanArray(grayImage.height * grayImage.width) { false } val thresholdSq = 16384 for (y in 1 until grayImage.height - 1) { for (x in 1 until grayImage.width - 1) { val gx = computeGradientX(grayImage, x, y) val gy = computeGradientY(grayImage, x, y) if (gx * gx + gy * gy > thresholdSq) { edges[y * grayImage.width + x] = true } } } return BlackWhiteImage(edges, grayImage.height, grayImage.width) }
Подробнее, как идёт вычисление перепадов цвета у соседних пикселей.
private fun computeGradientX(grayImage: GrayImage, x: Int, y: Int): Int { with(grayImage) { val idx = y * width + x return ( -image[idx - width - 1] + image[idx - width + 1] -2 * image[idx - 1] + 2 * image[idx + 1] -image[idx + width - 1] + image[idx + width + 1] ) } } private fun computeGradientY(grayImage: GrayImage, x: Int, y: Int): Int { with(grayImage) { val idx = y * width + x return ( -image[idx - width - 1] - 2 * image[idx - width] - image[idx - width + 1] + image[idx + width - 1] + 2 * image[idx + width] + image[idx + width + 1] ) } }
Поиск линий
Далее требуется провести линии поверх границ объектов изображения, чтобы в дальнейшем найти точки схода. Для построения линий я использовал преобразование Хафа (англ. Hough Transform).
Если кратко, то идея алгоритма заключается в том, что мы можем представить прямую линию в виде формулы:
где:
ρ (ро) — расстояние (нормаль) от начала координат до прямой
θ (тета) — угол наклона прямой (от 0 до 180°)
Через любую точку [x, y] в изображении может проходить бесконечное количество прямых линий. Если множество точек лежит в ряд вдоль одной линии, то для них будут соблюдаться общие значения ρ и θ.
Для поиска прямых линий нам требуется "аккумулятор" – двумерный массив, который будет хранит все возможные варианты расстояний ρ и углов θ в качестве индексов и количество точек, которые лежат на этих линиях.
Далее реализуется обход всех точек, которые лежат на границах объектов в изображении. Для всех линий в аккумуляторе, которые проходят через такую точку ставится "голос". Чем больше точек лежит на линии, тем больше у неё будет "голосов" в аккумуляторе.
В связи с тем, что у меня получались "шумные" линии, мне пришлось дополнительно вводить класс LineVote, который кроме количества голосов хранит минимальную и максимальную позиции точек, лежащих на линии, для дальнейшего вычисления её длины.
Это необходимо, чтобы затем отфильтровать и отбросить длинные линии с широким разбросом лежащих на них точек.
Затем выполняется обход по аккумулятору и возвращаются те линии, которые проходят ограничение по минимальной длине. Также если линия вышла широкой, у неё рядом могут лежать линии с большим количеством голосов, но в ответ попадёт та, у которой максимальное значение.
private class LineVote( var votes: Int = 0, var minProj: Float = Float.MAX_VALUE, var maxProj: Float = -Float.MAX_VALUE ) fun detectLines(edges: BlackWhiteImage): List<Line> { val width = edges.width val height = edges.height val maxRho = sqrt((width * width + height * height).toDouble()).toInt() val accumulator = Array(maxRho * 2) { Array(thetaSteps) { LineVote() } } vote(edges, accumulator, maxRho) return findLines(accumulator, maxRho) } private fun vote(edges: BlackWhiteImage, accumulator: Array<Array<LineVote>>, maxRho: Int) { val width = edges.width val height = edges.height for (y in 0 until height) { for (x in 0 until width) { if (edges.image[y * width + x]) { for (thetaIdx in 0 until thetaSteps) { val theta = Math.toRadians(thetaIdx.toDouble()) val rho = x * cos(theta) + y * sin(theta) val rhoIdx = (rho + maxRho).toInt() if (rhoIdx in 0 until maxRho * 2) { val alongX = -sin(theta) val alongY = cos(theta) val projection = (x * alongX + y * alongY).toFloat() val cell = accumulator[rhoIdx][thetaIdx] cell.votes++ cell.minProj = min(cell.minProj, projection) cell.maxProj = max(cell.maxProj, projection) } } } } } } private fun findLines(accumulator: Array<Array<LineVote>>, maxRho: Int): List<Line> { val lines = mutableListOf<Line>() for (rhoIdx in 0 until maxRho * 2) { for (thetaIdx in 0 until thetaSteps) { val cell = accumulator[rhoIdx][thetaIdx] val votes = cell.votes if (votes > threshold && isLocalMaximum(accumulator, rhoIdx, thetaIdx)) { val rho = rhoIdx - maxRho val theta = Math.toRadians(thetaIdx.toDouble()) val length = if (cell.maxProj > cell.minProj) { (cell.maxProj - cell.minProj) } else { 0f } val density = if (length > 0) votes / length else 0f lines.add( Line( rho = rho.toDouble(), theta = theta, votes = votes, length = length, density = density ) ) } } } return lines } private fun isLocalMaximum( accumulator: Array<Array<LineVote>>, rhoIdx: Int, thetaIdx: Int ): Boolean { val votes = accumulator[rhoIdx][thetaIdx].votes val offset = localMaxWindow / 2 for (dr in -offset..offset) { for (dt in -offset..offset) { if (dr == 0 && dt == 0) continue val nr = rhoIdx + dr val nt = thetaIdx + dt if (nr in accumulator.indices && nt in 0 until thetaSteps) { if (accumulator[nr][nt].votes >= votes) { return false } } } } return true }
Поиск точек схода
Теперь, когда мы построили линии поверх объектов, мы можем определить точки схода.
В связи с тем, что линии могут как пересекаться, так и быть параллельными, я решил разбить поиск и вначале искать параллельные линии, а затем уже пересекающиеся. Такой подход делает результат чище и избавляет от шумовых значений.
Для поиска параллельных линий, я группирую их по углам наклона, с учетом небольших отклонений, а затем нахожу средний угол.
Поиск пересекающихся линий требует предварительной фильтрации с удалением линий, которые совпадают с параллельными или имеют низкую плотность точек.
Дополнительно я сделал ограничение на количество результатов, взяв по три точки с обоих групп, оставив самые лучшие результаты.
private fun findVanishingPoints( lines: List<Line>, height: Int, width: Int, ): List<PerspectivePoint> { if (lines.size < 2) return emptyList() val parallelGroups = findParallelLines(lines) val infinitePoints = parallelGroups.map { group -> val angles = group.map {it.angle } val avgAngle = calculateCircularCenter(angles) PerspectivePoint.infinite(avgAngle) } val strongLines = takeStrongLines(lines, parallelGroups) val rawFinite = findIntersectionPoints(strongLines, height, width) .filter { point -> !isPointNearInfiniteDirection(point, infinitePoints, height, width,) } val finitePoints = sortVanishingPoints(rawFinite, width, height) return infinitePoints.take(3) + finitePoints.take(3) }
Посмотрим более подробнее на поиск параллельных линий. Вначале отсеиваются линии с низкой плотностью точек и идёт разбиение линий на кластеры с диапазоном углов в 10 градусов. Потом вычисляются максимальные плотность и количество "голосов" среди кластеров линий. Они используются для того, чтобы оставить наиболее явные параллельные линии среди выборки. Далее идёт сортировка кластеров по плотности точек и отсев соседних линий из результата. Выбранные коэффициенты фильтрации были подобраны эмпирическим путём.
Для кластеров вычисляются средние углы наклона их линий. Для этого используется круговое среднее, так как обычное арифметическое не работает для значений, переходящих через 0°/180°. Например, есть две линии с углами 178° и 2°, и они лежат почти горизонтально. Средний для них угол должен выйти не 90°, а 0°.
private fun findParallelLines(lines: List<Line>): List<List<Line>> { val denseLines = lines.filter { it.density >= 0.8f } val clusters = clusterLinesByAngles(denseLines, step = 10).filter { it.lines.size >= 3 } val maxClusterDensity = clusters.maxOfOrNull { it.avgDensity } ?: 1.0f val maxVotes = clusters.maxOfOrNull { it.topVotes } ?: 1 val filteredClusters = clusters .filter { it.avgDensity >= maxClusterDensity * 0.93f && it.topVotes >= maxVotes * 0.8 } .sortedByDescending { it.avgDensity } val uniqueClusters = mutableListOf<AngleCluster>() val angleThreshold = 15f for (cluster in filteredClusters) { val tooClose = uniqueClusters.any { existing -> val diff = abs(existing.center - cluster.center) minOf(diff, 180 - diff) < angleThreshold } if (!tooClose) { uniqueClusters.add(cluster) } } return uniqueClusters.map { it.lines } } private data class AngleCluster( val center: Float, val lines: List<Line>, val avgDensity: Float, val topVotes: Int ) private fun clusterLinesByAngles(lines: List<Line>, step: Int): List<AngleCluster> { if (lines.isEmpty()) return emptyList() val bins = mutableMapOf<Int, MutableList<Line>>() val halfStep = step / 2 for (line in lines) { val shifted = (line.angle + halfStep) % 180 val binIndex = (shifted / step).toInt() bins.getOrPut(binIndex) { mutableListOf() }.add(line) } return bins.map { (_, binAngles) -> val center = calculateCircularCenter(binAngles.map { it.angle }) val avgDensity = binAngles.map { it.density }.average().toFloat() val sortedVotes = binAngles.map {it.votes}.sortedDescending() val topVotes = sortedVotes[sortedVotes.size * 20 / 100] AngleCluster(center, binAngles, avgDensity, topVotes) } } fun calculateCircularCenter(angles: List<Float>): Float { val sumSin = angles.sumOf { sin(Math.toRadians((it * 2).toDouble())) } val sumCos = angles.sumOf { cos(Math.toRadians((it * 2).toDouble())) } return ((Math.toDegrees(atan2(sumSin, sumCos)).toFloat() / 2) + 180) % 180 }
Поиск точек схода также требует выборки явных пересекающихся прямых линий. Для этого остаются линии с высоким количеством "голосов" и плотностью точек, которых нет среди параллельных линий. Далее идёт сортировка точек по убыванию плотности и берутся 40 лучших линий, чтобы уменьшить количество дальнейших операций.
private fun takeStrongLines(lines: List<Line>, parallelGroups: List<List<Line>>): List<Line> { val parallelAngles = parallelGroups.flatMap { lines -> lines.map { it.angle } }.distinct() val tolerance = 7f val sortedVotes = lines.map {it.votes}.sortedDescending() val threshold = sortedVotes[sortedVotes.size * 35 / 100] return lines.filter { line -> line.votes >= threshold && line.density >= 0.9f && parallelAngles.none { parallelAngle -> val diff = abs(line.angle - parallelAngle) minOf(diff, 180 - diff) < tolerance } } .sortedWith(compareByDescending<Line> { it.density }.thenByDescending { it.votes }) .take(40) }
Далее мы ищем точки пересечения всех полученных линий и группируем их, если они достаточно близко лежат друг к другу. Каждая новая точка либо создаёт новый кластер, либо попадает уже в существующий. Затем идёт фильтрация точек пересечения по количеству сходящихся в них линий и расстоянию от краёв изображения. Если точка находится очень далеко, то она игнорируется.
private class Cluster { val points = mutableListOf<Pair<Float, Float>>() var centerX = 0f var centerY = 0f fun addPoint(point: Pair<Float, Float>) { val newSize = points.size + 1 centerX = (centerX * points.size + point.first) / newSize centerY = (centerY * points.size + point.second) / newSize points.add(point) } } private fun findIntersectionPoints( lines: List<Line>, height: Int, width: Int, ): List<PerspectivePoint> { if (lines.size < 2) return emptyList() val intersections = mutableListOf<Pair<Float, Float>>() for (i in 0 until lines.size - 1) { for (j in i + 1 until lines.size) { val intersection = findIntersection(lines[i], lines[j]) if (intersection != null) { intersections.add(intersection) } } } if (intersections.isEmpty()) return emptyList() val diagonalSq = width * width + height * height val thresholdSq = diagonalSq * 0.0004f val clusters = clusterIntersections(intersections, thresholdSq) val limit = max(width, height) * 5f return clusters .filter { cluster -> cluster.points.size >= 3 && abs(cluster.centerX) < limit && abs(cluster.centerY) < limit } .sortedByDescending { cluster -> cluster.points.size } .map { cluster -> PerspectivePoint(cluster.centerX, cluster.centerY) } } private fun clusterIntersections( points: List<Pair<Float, Float>>, thresholdSq: Float ): List<Cluster> { val clusters = mutableListOf<Cluster>() for (point in points) { var foundCluster = false for (cluster in clusters) { val distance = (point.first - cluster.centerX).pow(2) + (point.second - cluster.centerY).pow(2) if (distance < thresholdSq) { cluster.addPoint(point) foundCluster = true break } } if (!foundCluster) { clusters.add(Cluster().apply { addPoint(point) }) } } return clusters }
Поиск точки пересечения двух линий требует решения уравнения:
Для этого cosθ₁, cosθ₂, sinθ₁, sinθ₂ обозначаются за a1, a2, b1, b2 соответственно, и тогда уравнение принимает вид:
Теперь его можно решить через метод Крамера:
private fun findIntersection(line1: Line, line2: Line): Pair<Float, Float>? { val theta1 = line1.theta val theta2 = line2.theta val rho1 = line1.rho val rho2 = line2.rho val a1 = cos(theta1) val b1 = sin(theta1) val a2 = cos(theta2) val b2 = sin(theta2) val determinant = a1 * b2 - a2 * b1 if (abs(determinant) < 1e-6) return null val x = (b2 * rho1 - b1 * rho2) / determinant val y = (a1 * rho2 - a2 * rho1) / determinant return x.toFloat() to y.toFloat() }
Чтобы избежать дублирования, сделана проверка, если точка схода лежит вдоль параллельной линии, и лежит далеко от изображения, то она не добавляется в результат. Для этого вычисляется угол от центра изображения до точки и идёт сравнение с углами параллельных линий.
private fun isPointNearInfiniteDirection( point: PerspectivePoint, infinitePoints: List<PerspectivePoint>, height: Int, width: Int, ): Boolean { val centerX = width / 2f val centerY = height / 2f val dx = point.x - centerX val dy = point.y - centerY val pointAngle = atan2(dy, dx) val angleLimit = 10f val distanceLimit = max(width, height) * 2 for (infinitePoint in infinitePoints) { if (infinitePoint.direction != null) { val angleDiff = abs(pointAngle - infinitePoint.direction) % 180 val minDiff = minOf(angleDiff, 180 - angleDiff) if (minDiff < angleLimit) { val distance = sqrt(dx * dx + dy * dy) if (distance > distanceLimit) { return true } } } } return false }
Также может получиться, что алгоритм найдёт точки пересечения, которые лежат рядом друг с другом. И чтобы убрать ненужные результаты, похожие точки с меньшим количеством проходящих сквозь них линий попадают в конец списка. Так в результате будут наиболее разнообразные точки схода.
private fun sortVanishingPoints(points: List<PerspectivePoint>, width: Int, height: Int): List<PerspectivePoint> { if (points.isEmpty()) return emptyList() val threshold = max(width, height) * 0.01f val uniqueResult = mutableListOf<PerspectivePoint>() val similarPoints = mutableListOf<PerspectivePoint>() for (point in points) { val uniquePointExists = uniqueResult.any { existing -> val distance = (point.x - existing.x).pow(2) + (point.y - existing.y).pow(2) distance < threshold } val similarPointExists = similarPoints.any { existing -> val distance = (point.x - existing.x).pow(2) + (point.y - existing.y).pow(2) distance < threshold } if (uniquePointExists || similarPointExists) { similarPoints.add(point) } else { uniqueResult.add(point) } } return uniqueResult + similarPoints }
Результаты
Демонстрация работы алгоритма:
Итак, полученный алгоритм справляется с поставленной ему задачей и может быть использован в помощи художникам и дизайнерам.
К сожалению, алгоритм чувствителен к сильному шуму на изображении. В некоторых случаях могут появляться ложные точки схода, либо, наоборот, точки могут не определяться, если линии на изображении слабые.
Спасибо, что дочитали статью!
С исходным кодом проекта Вы можете ознакомиться на GitHub.
