Skip to content

Instantly share code, notes, and snippets.

@RankoR
Last active Apr 2, 2021
Embed
What would you like to do?
Fast 2D DCT implementation for 32*32 array, but can be adapted for any fixed dimension. Inspired by the CocoaImageHashing impl for iOS.
package pro.labster.dct
import kotlin.math.cos
import kotlin.math.sqrt
/**
* Around 20x faster than a naive implementation
*/
class DctAlgorithm2DFast : DctAlgorithm {
private val coefficients = DoubleArray(DIMENSION)
private val coefficients1 = Array(DIMENSION) { DoubleArray(DIMENSION) }
private val coefficients2 = Array(DIMENSION) { DoubleArray(DIMENSION) }
private val coefficientsV = Array(DIMENSION) { DoubleArray(DIMENSION) }
init {
coefficients.fill(1.0)
coefficients[0] = 1.0 / sqrt(2.0)
for (i in 0 until DIMENSION) {
for (j in 0 until DIMENSION) {
coefficients1[i][j] = cos((2 * i + 1.0) / DOUBLE_DIMENSION * j * Math.PI)
coefficients2[i][j] = coefficients1[i][j]
coefficientsV[i][j] = coefficients[i] * coefficients[j] / sqrt(2.0 * DIMENSION)
}
}
}
override fun apply(data: Array<DoubleArray>): Array<DoubleArray> {
if (data.size != DIMENSION || data[0].size != DIMENSION) {
throw IllegalArgumentException("Data dimension is not ${DIMENSION}x$DIMENSION")
}
val result = Array(DIMENSION) { DoubleArray(DIMENSION) }
for (u in 0 until DIMENSION) {
for (v in 0 until DIMENSION) {
var sum = unrollDctI(data, coefficients1, coefficients2, u, v)
sum *= coefficientsV[u][v]
result[u][v] = sum
}
}
return result
}
/**
* Do NOT replace with for-loop, it would significantly slow down the algo implementation
*/
private fun unrollDctI(data: Array<DoubleArray>, co1: Array<DoubleArray>, co2: Array<DoubleArray>, u: Int, v: Int): Double {
var newSum = 0.0
newSum = unrollDctJ(data, newSum, co1, co2, 0, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 1, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 2, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 3, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 4, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 5, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 6, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 7, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 8, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 9, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 10, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 11, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 12, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 13, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 14, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 15, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 16, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 17, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 18, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 19, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 20, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 21, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 22, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 23, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 24, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 25, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 26, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 27, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 28, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 29, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 30, u, v)
newSum = unrollDctJ(data, newSum, co1, co2, 31, u, v)
return newSum
}
/**
* Do NOT replace with for-loop, it would significantly slow down the algo implementation
*/
private fun unrollDctJ(data: Array<DoubleArray>, sum: Double, co1: Array<DoubleArray>, co2: Array<DoubleArray>, i: Int, u: Int, v: Int): Double {
var newSum = sum
newSum += inlineDctSum(data, co1, co2, i, u, 0, v)
newSum += inlineDctSum(data, co1, co2, i, u, 1, v)
newSum += inlineDctSum(data, co1, co2, i, u, 2, v)
newSum += inlineDctSum(data, co1, co2, i, u, 3, v)
newSum += inlineDctSum(data, co1, co2, i, u, 4, v)
newSum += inlineDctSum(data, co1, co2, i, u, 5, v)
newSum += inlineDctSum(data, co1, co2, i, u, 6, v)
newSum += inlineDctSum(data, co1, co2, i, u, 7, v)
newSum += inlineDctSum(data, co1, co2, i, u, 8, v)
newSum += inlineDctSum(data, co1, co2, i, u, 9, v)
newSum += inlineDctSum(data, co1, co2, i, u, 10, v)
newSum += inlineDctSum(data, co1, co2, i, u, 11, v)
newSum += inlineDctSum(data, co1, co2, i, u, 12, v)
newSum += inlineDctSum(data, co1, co2, i, u, 13, v)
newSum += inlineDctSum(data, co1, co2, i, u, 14, v)
newSum += inlineDctSum(data, co1, co2, i, u, 15, v)
newSum += inlineDctSum(data, co1, co2, i, u, 16, v)
newSum += inlineDctSum(data, co1, co2, i, u, 17, v)
newSum += inlineDctSum(data, co1, co2, i, u, 18, v)
newSum += inlineDctSum(data, co1, co2, i, u, 19, v)
newSum += inlineDctSum(data, co1, co2, i, u, 20, v)
newSum += inlineDctSum(data, co1, co2, i, u, 21, v)
newSum += inlineDctSum(data, co1, co2, i, u, 22, v)
newSum += inlineDctSum(data, co1, co2, i, u, 23, v)
newSum += inlineDctSum(data, co1, co2, i, u, 24, v)
newSum += inlineDctSum(data, co1, co2, i, u, 25, v)
newSum += inlineDctSum(data, co1, co2, i, u, 26, v)
newSum += inlineDctSum(data, co1, co2, i, u, 27, v)
newSum += inlineDctSum(data, co1, co2, i, u, 28, v)
newSum += inlineDctSum(data, co1, co2, i, u, 29, v)
newSum += inlineDctSum(data, co1, co2, i, u, 30, v)
newSum += inlineDctSum(data, co1, co2, i, u, 31, v)
return newSum
}
/**
* Note: Inlining speeds it up 6x, don't blindly believe the linter. And yep, I've checked it, just believe me
*/
private inline fun inlineDctSum(data: Array<DoubleArray>, co1: Array<DoubleArray>, co2: Array<DoubleArray>, i: Int, u: Int, j: Int, v: Int): Double {
return co1[i][u] * co2[j][v] * data[i][j]
}
private companion object {
private const val DIMENSION = 32
private const val DOUBLE_DIMENSION = DIMENSION * 2
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment