Perspective Extraction from Images: Sobel + Hough

Automatic Vanishing Point Extraction from Images in Kotlin

The PerspectiveSceneExtractor class analyzes an image, converts it to grayscale, detects edges using the Sobel operator, and applies the Hough Transform to find lines. The result is a list of PerspectivePoint objects with vanishing point coordinates or directions of parallel lines.

Image and Pixel Representation

To keep it UI-independent, we use a value class Image with packed pixels in RGBPixel. This minimizes memory usage.

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
}

Vanishing points are stored in PerspectivePoint. Coordinates set to Float.MAX_VALUE indicate an infinite point with a direction in degrees.

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

Grayscale Conversion

The conversion uses the Rec. 709 standard with weights 0.2126 (R), 0.7152 (G), and 0.0722 (B) to match human brightness perception. The result is a GrayImage with one Int per 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)
}

Edge Detection with Sobel Operator

The Sobel operator computes gradients in X and Y for each pixel. If the gradient magnitude exceeds the threshold (thresholdSq = 16384), the pixel is marked as an edge.

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

Gradients are computed considering neighboring pixels:

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 {
    // similar implementation for Y
}

Hough Transform for Line Detection

Lines are parameterized as ρ = x·cos(θ) + y·sin(θ). The accumulator is a 2D array over ρ and θ (thetaSteps steps). Each edge point votes for lines passing through it.

The LineVote class tracks votes, projections for length, and density:

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

Voting process:

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)
                    // update votes and projections
                }
            }
        }
    }
}

Lines are selected based on local vote maxima, minimum length, and density.

Key Algorithm Parameters

• thetaSteps: Number of discrete angles (typically 180 for 1° steps).
• threshold: Minimum votes required for a line.
• localMaxWindow: Window size for local maximum checks.
• thresholdSq: Sobel operator threshold (16384).

Key Takeaways

• Packing pixels into Int reduces memory usage by 75% compared to separate channels.
• Rec. 709 ensures accurate grayscale matching human perception.
• Sobel is faster than Canny for large images.
• Hough filtering by length and density removes noisy lines.
• Infinite vanishing points are modeled with directions for horizons.

— Editorial Team