Perspektivenextraktion aus Bildern: Sobel + Hough

Automatische Fluchtpunktextraktion aus Bildern in Kotlin

Die Klasse PerspectiveSceneExtractor analysiert ein Bild, wandelt es in Graustufen um, erkennt Kanten mit dem Sobel-Operator und wendet die Hough-Transformation an, um Linien zu finden. Das Ergebnis ist eine Liste von PerspectivePoint-Objekten mit Fluchtpunktkoordinaten oder Richtungen paralleler Linien.

Bild- und Pixel-Darstellung

Um unabhängig von der Benutzeroberfläche zu bleiben, verwenden wir eine Value-Klasse Image mit gepackten Pixeln in RGBPixel. Das minimiert den Speicherverbrauch.

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
}

Fluchtpunkte werden in PerspectivePoint gespeichert. Koordinaten mit Float.MAX_VALUE deuten auf einen unendlichen Punkt mit Richtung in Grad hin.

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

Umwandlung in Graustufen

Die Umwandlung nutzt den Rec. 709-Standard mit Gewichten 0,2126 (R), 0,7152 (G) und 0,0722 (B), um der menschlichen Helligkeitswahrnehmung zu entsprechen. Das Ergebnis ist eine GrayImage mit einem Int pro Pixel.

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

Kantenerkennung mit Sobel-Operator

Der Sobel-Operator berechnet für jeden Pixel die Gradienten in X- und Y-Richtung. Überschreitet die Gradientengröße den Schwellwert (thresholdSq = 16384), wird der Pixel als Kante markiert.

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

Gradienten werden unter Berücksichtigung der Nachbarpixel berechnet:

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 {
    // ähnliche Implementierung für Y
}

Hough-Transformation zur Linienerkennung

Linien werden parametrisiert als ρ = x·cos(θ) + y·sin(θ). Der Akkumulator ist ein 2D-Array über ρ und θ (thetaSteps Schritte). Jeder Kantenpunkt stimmt für Linien ab, die durch ihn verlaufen.

Die Klasse LineVote verfolgt Abstimmungen, Projektionen für Länge und Dichte:

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

Abstimmungsprozess:

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)
                    // Abstimmungen und Projektionen aktualisieren
                }
            }
        }
    }
}

Linien werden basierend auf lokalen Abstimmungsmaxima, Mindestlänge und Dichte ausgewählt.

Wichtige Algorithmusparameter

• thetaSteps: Anzahl diskreter Winkel (typisch 180 für 1°-Schritte).
• threshold: Mindestabstimmungen für eine Linie.
• localMaxWindow: Fenstergroße für lokale Maxima-Prüfungen.
• thresholdSq: Sobel-Schwellwert (16384).

Wichtige Erkenntnisse

• Pixel in Int packen reduziert Speicherverbrauch um 75 % im Vergleich zu separaten Kanälen.
• Rec. 709 gewährleistet präzise Graustufenwahrnehmung wie beim Menschen.
• Sobel ist bei großen Bildern schneller als Canny.
• Hough-Filterung nach Länge und Dichte entfernt verrauschte Linien.
• Unendliche Fluchtpunkte werden mit Richtungen für Horizonte modelliert.

— Editorial Team