This is the 20th day of my participation in the Genwen Challenge

Integral graph

Integral images were first proposed by Crow in 1984 to improve rendering speed in multi-scale perspective projections, and are a fast algorithm for calculating the sum of regions and squares of images. The core idea is to establish its own integral graph lookup table for each image. In the stage of image integral processing and calculation, the linear time calculation of mean convolution can be realized by direct search according to the pre-established integral graph lookup table, so that the time of convolution execution is not related to the radius window size. As one of the classical algorithms in image processing, image integral graph has been applied in HAAR/SURF image feature extraction, binary image analysis, NCC calculation of image similarity correlation, fast calculation of image convolution, etc.

The principle of

Different calculation rules are adopted to obtain different integral images:


s u m ( X . Y ) = ∑ x < X . y < Y image ( x . y ) {sum} (X,Y) = \sum _{x<X,y<Y} \texttt{image} (x,y)

s q s u m ( X . Y ) = ∑ x < X . y < Y image ( x . y ) 2 {sqsum} (X,Y) = \sum _{x<X,y<Y} \texttt{image} (x,y)^2

t i l t e d ( X . Y ) = ∑ y < Y . a b s ( x – X + 1 ) Or less Y – y – 1 i m a g e ( x . y ) {tilted} (X,Y) = \sum _{y<Y,abs(x-X+1) \leq Y-y-1} {image} (x,y)

Using these integral images, we can calculate the sum, mean and standard deviation over the region of horizontal or rotating rectangles in the image.


∑ x 1 Or less x < x 2 .   y 1 Or less y < y 2 image ( x . y ) = sum ( x 2 . y 2 ) – sum ( x 1 . y 2 ) – sum ( x 2 . y 1 ) + sum ( x 1 . y 1 ) \sum _{x_1 \leq x < x_2, \, y_1 \leq y < y_2} \texttt{image} (x,y) = \texttt{sum} (x_2,y_2)- \texttt{sum} (x_1,y_2)- \texttt{sum} (x_2,y_1)+ \texttt{sum} (x_1,y_1)

By integrating the image, we can blur the image quickly. In the case of multi-channel images, the sum of each channel is accumulated independently.

The figure below shows the integral calculation process of a vertical Rect (3,3,3,2) and an inclined Rect (5,1,2,3). Displays the selected pixels in the original image and the sum of related pixels in the integral image.

API

public static void integral3(Mat src, Mat sum, Mat sqsum, Mat tilted, int sdepth, int sqdepth)
Copy the code

  • Parameter one: SRC, input image is (W * H), 8 bits or floating point (32F or 64F).

  • Argument two: sum, the integral graph (and table), must be (W + 1) * (H + 1) and of type 32 – or 64-bit floating-point number.

  • Parameter 3: sqsum, the integral image of the square of pixel values (sum of squares), which is (W + 1) * (H + 1) double precision 64-bit floating point number set; .

  • Parameter four: tilted, an integral image rotated 45 degrees which is an array of (W + 1) * (H + 1) of the same type as sum.

  • Parameter 5: sdepth, the desired depth of the integrating image and the integrated image rotated by 45 degrees, CV_32S,CV_32F or CV_64F.

  • Parameter 6: sqdepth, the desired pixel value squared integral image depth, CV_32F or CV_64F.

The simplified method

public static void integral2(Mat src, Mat sum, Mat sqsum, int sdepth, int sqdepth)
Copy the code
public static void integral(Mat src, Mat sum, int sdepth)
Copy the code

operation

* author: yidong * 2020/12/16 */
class IntegralActivity : AppCompatActivity() {
    private val mBinding: ActivityIntegralBinding by lazy {
        ActivityIntegralBinding.inflate(layoutInflater)
    }

    private lateinit var rgb: Mat
    private lateinit var sum: Mat
    private lateinit var sqrSum: Mat

    override fun onCreate(savedInstanceState: Bundle?). {
        super.onCreate(savedInstanceState)
        setContentView(mBinding.root)
        val bgr = getBgrFromResId(R.drawable.lena)
        rgb = Mat()
        rgb = bgr.toRgb()
        mBinding.ivLena.showMat(rgb)

        sum = Mat()
        sqrSum = Mat()
        Imgproc.integral2(rgb, sum, sqrSum, CvType.CV_32S, CvType.CV_32F);
    }

    override fun onDestroy(a) {
        rgb.release()
        sum.release()
        sqrSum.release()
        super.onDestroy()
    }

    override fun onCreateOptionsMenu(menu: Menu?).: Boolean {
        menuInflater.inflate(R.menu.menu_integral, menu)
        return true
    }

    override fun onOptionsItemSelected(item: MenuItem): Boolean {
        when (item.itemId) {
            R.id.menu_integral_sum -> {
                doSumNormalize()
            }
            R.id.menu_integral_blur -> {
                doBlur()
            }
        }
        return true
    }

    private fun doSumNormalize(a) {
        val result = Mat()
        GlobalScope.launch(Dispatchers.Main) {
            mBinding.isLoading = true
            withContext(Dispatchers.IO) {
                Core.normalize(sum, result, 0.0.255.0, NORM_MINMAX, CV_8UC1)
            }
            mBinding.isLoading = false
            mBinding.ivResult.showMat(result)
        }
    }

    private fun doBlur(a) {
        GlobalScope.launch(Dispatchers.Main) {
            mBinding.isLoading = true
            val result = Mat.zeros(rgb.size(), rgb.type())
            withContext(Dispatchers.IO) {
                val w = rgb.cols()
                val h = rgb.rows()
                var x2 = 0
                var y2 = 0
                var x1 = 0
                var y1 = 0
                val ksize = 5
                val radius = ksize / 2
                val ch = rgb.channels()
                var cx = 0
                var cy = 0

                for (row in 0 until h + radius) {
                    y2 = if ((row + 1) > h) {
                        h
                    } else {
                        row + 1
                    }
                    y1 = if ((row - ksize) < 0) {
                        0
                    } else {
                        row - ksize
                    }
                    for (col in 0 until w + radius) {
                        x2 = if ((col + 1) > w) w else (col + 1);
                        x1 = if ((col - ksize) < 0) 0 else (col - ksize);
                        cx = if ((col - radius) < 0) 0 else col - radius;
                        cy = if ((row - radius) < 0) 0 else row - radius;
                        val num = (x2 - x1) * (y2 - y1)
                        val values = ByteArray(ch) { 0 }
                        for (i in 0 until ch) {
                            // Integral graph lookup and table, compute convolution
                            val s = getBlockSum(sum, x1, y1, x2, y2, i)
                            values[i] = (s / num).toByte()
                        }
                        result.put(cy, cx, values);
                    }
                }
            }
            mBinding.isLoading = false
            mBinding.ivResult.showMat(result)
        }
    }

    private fun getBlockSum(sum: Mat, x1: Int, y1: Int, x2: Int, y2: Int, i: Int): Int {
        // top left
        val tl = sum.get(y1, x1)[i].toInt()
        // top right
        val tr = sum.get(y2, x1)[i].toInt()
        // bottom left
        val bl = sum.get(y1, x2)[i].toInt()
        // bottom right
        val br = sum.get(y2, x2)[i].toInt()

        return(br - bl - tr + tl); }}Copy the code

The effect


The source code

Github.com/onlyloveyd/…