Extrakce perspektivy z obrázků: Sobel + Hough

Automatické extrahování úběžných bodů perspektivy z obrázků v Kotlinu

Třída PerspectiveSceneExtractor analyzuje obrázek, převádí ho do odstínů šedi, detekuje hrany pomocí Sobelova operátoru a aplikuje Houghovu transformaci pro hledání čar. Výsledkem je seznam PerspectivePoint se souřadnicemi úběžných bodů nebo směry paralelních čar.

Reprezentace obrázku a pixelů

Pro nezávislost na UI se používá value-třída Image s zabalenými pixely v RGBPixel. Tím se minimalizuje spotřeba paměti.

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
}

Úběžné body jsou uloženy v PerspectivePoint. Souřadnice Float.MAX_VALUE označují nekonečný bod se směrem ve stupních.

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

Převod do stupňů šedi

Konverze používá standard Rec. 709 s koeficienty 0.2126 (R), 0.7152 (G), 0.0722 (B) pro zohlednění vnímání jasu. Výsledkem je GrayImage s jedním Int na 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)
}

Detekce hran pomocí Sobelova operátoru

Sobelův operátor vypočítává gradienty podle X a Y pro každý pixel. Pokud velikost gradientu překročí prah (thresholdSq = 16384), pixel je označen jako hrana.

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 se vypočítávají s ohledem na sousedy:

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 {
    // analogicky pro Y
}

Houghova transformace pro hledání čar

Čáry jsou parametrizovány jako ρ = x·cos(θ) + y·sin(θ). Akumulátor je 2D-pole podle ρ a θ (thetaSteps kroků). Každý bod na hraně hlasuje pro procházející čáry.

Třída LineVote sleduje hlasy, projekce pro délku a hustotu:

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

Hlasování:

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)
                    // aktualizace hlasů a projekcí
                }
            }
        }
    }
}

Čáry jsou vybrány podle lokálního maxima hlasů, minimální délky a hustoty.

Klíčové parametry algoritmu

• thetaSteps: počet diskrétních úhlů (obvykle 180 pro krok 1°).
• threshold: minimální počet hlasů pro čáru.
• localMaxWindow: okno pro kontrolu lokálního maxima.
• thresholdSq: prah pro Sobelův operátor (16384).

Co je důležité

• Balení pixelů do Int snižuje paměť o 75 % ve srovnání s oddělenými kanály.
• Rec. 709 zajišťuje přesné stupně šedi pro lidské vnímání.
• Sobel je vhodnější než Canny pro rychlost na velkých obrázcích.
• Houghova filtrace podle délky a hustoty odstraňuje šumové čáry.
• Nekonečné úběžné body jsou modelovány směrem pro horizonty.

— Editorial Team