Wyodrębnianie perspektywy z obrazów: Sobel + Hough

Automatyczne wyodrębnianie punktów zbiegu perspektywy z obrazów w Kotlinie

Klasa PerspectiveSceneExtractor analizuje obraz, przekształca go w odcienie szarości, wykrywa krawędzie za pomocą operatora Sobela i stosuje transformację Hougha do wyszukiwania linii. Wynik to lista PerspectivePoint ze współrzędnymi punktów zbiegu lub kierunkami linii równoległych.

Reprezentacja obrazu i pikseli

Dla niezależności od interfejsu użytkownika użyto klasy wartości Image z pakowanymi pikselami w RGBPixel. To minimalizuje zużycie pamięci.

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
}

Punkty zbiegu są przechowywane w PerspectivePoint. Współrzędne Float.MAX_VALUE oznaczają nieskończony punkt z kierunkiem w stopniach.

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)
    }
}

Przekształcenie w odcienie szarości

Konwersja używa standardu Rec. 709 ze współczynnikami 0.2126 (R), 0.7152 (G), 0.0722 (B) dla uwzględnienia percepcji jasności. Wynik to GrayImage z jednym Int na piksel.

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(gray, image.height, image.width)
}

Wykrywanie krawędzi operatorem Sobela

Operator Sobela oblicza gradienty po X i Y dla każdego piksela. Jeśli wielkość gradientu przekroczy próg (thresholdSq = 16384), piksel jest oznaczany jako krawędź.

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)
}

Gradienty są obliczane z uwzględnieniem sąsiadów:

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 {
    // analogicznie dla Y
}

Transformacja Hougha do wyszukiwania linii

Linie są parametryzowane jako ρ = x·cos(θ) + y·sin(θ). Akumulator to tablica 2D według ρ i θ (thetaSteps kroków). Każdy punkt na krawędzi głosuje za przechodzącymi liniami.

Klasa LineVote śledzi głosy, projekcje dla długości i gęstości:

private class LineVote(
    var votes: Int = 0,
    var minProj: Float = Float.MAX_VALUE,
    var maxProj: Float = -Float.MAX_VALUE
)

Głosowanie:

private fun vote(edges: BlackWhiteImage, accumulator: Array<Array<LineVote>>, maxRho: Int) {
    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)
                    // aktualizacja głosów i projekcji
                }
            }
        }
    }
}

Linie są wybierane na podstawie lokalnego maksimum głosów, minimalnej długości i gęstości.

Kluczowe parametry algorytmu

• thetaSteps: liczba dyskretnych kątów (zwykle 180 dla kroku 1°).
• threshold: minimalna liczba głosów dla linii.
• localMaxWindow: okno dla sprawdzania lokalnego maksimum.
• thresholdSq: próg dla operatora Sobela (16384).

Co jest ważne

• Pakowanie pikseli w Int zmniejsza pamięć o 75% w porównaniu z oddzielnymi kanałami.
• Rec. 709 zapewnia dokładne odcienie szarości dla ludzkiej percepcji.
• Sobel jest preferowany nad Canny dla prędkości na dużych obrazach.
• Filtracja Hougha według długości i gęstości usuwa szumne linie.
• Nieskończone punkty zbiegu są modelowane kierunkiem dla horyzontów.

— Editorial Team