Pixel distance

For pixels P (x, y), Q (s, t), z(v, w), D(p, q) is used to represent the distance between pixels p and q. The following conditions should be met for the distance between pixels D(x, y) :

  • D(p, q) ≥ 0
  • D(p , q) = D(q , p)
  • D(p, q) + D(q, z) ≥ D(p, z)

Classification and calculation method of pixel distance

  • Euclidean Distance

    The straight-line distance between two pixels. In the same way as the straight line distance between two points in the cartesian coordinate system, the distance between two pixels in the X direction and Y direction is calculated, and then the distance between two pixels is obtained by using the Pythagorean theorem.


    D e = ( x 1 – x 2 ) 2 + ( y 1 – y 2 ) 2 D_e = \sqrt{(x_1-x_2)^2 + (y_1-y_2)^2 }

    According to the definition of Euclidean distance, the distance between two pixels in an image can have a fractional part. In a 5×5 matrix, the Euclidean distance to the center of the matrix for all pixels is shown as follows:

  • City-block Distance

    Block distance (also known as D4 distance) can only go in two directions, not diagonal. The distance between the two points is the sum of the distance between the horizontal and vertical. Of Euclidean distance from one pixel to the other pixels of the shortest distance, but sometimes we are not moved in the direction of the connection between two points, such as the connection between two points in a city there may be obstacles blocking, so from one point to another point need to walk along the street, so the distance measure is called blocks.


    D 4 = ∣ x 1 – x 2 ∣ + ∣ y 1 – y 2 ∣ D_4=|x_1-x_2|+|y_1-y_2|

    By the definition of block distance, the distance between two pixels in an image must be an integer. In a 5×5 matrix, the distance between all pixels and the block in the center of the matrix is shown as follows:

  • Chess Board Distance

    The checkerboard distance (also known as D8 distance) means that all the elements around P are adjacent, which means that it can go to any of the eight surrounding points, vertical and oblique. The shortest distance that can be walked horizontally or diagonally is actually the maximum distance that can be walked horizontally or vertically. Similar to block distance and chessboard distance is also assumed that two pixels are not able to close, in the direction of the connection between the pixel only move along the X direction and Y direction, but the distance is not said by a board pixels to move to another the distance between the pixel, but said two pixels to move to the same row or same column need to move when the maximum distance.


    D 8 = m a x ( ∣ x 1 – x 2 ∣ . ∣ y 1 – y 2 ∣ ) D_8 = Max (| x_1 – x_2 | to | y_1, y_2 |)

    According to the definition of checkerboard distance, the distance between two pixels in an image must be an integer. In a 5×5 matrix, the checkerboard distance between all pixels and the center of the matrix is shown as follows:

API

public static void distanceTransform(Mat src, Mat dst, int distanceType, int maskSize, int dstType) 
Copy the code

Parameter 1: SRC, input image, data type is CV_8U single-channel image

Parameter two: DST, the output image, with the same size as the input image, the data type is CV_8U or CV_32F single-channel image

Parameter 3: distanceType, select the mark of the method to calculate the distance between two pixels, the parameter can be the following value:

// C++: enum DistanceTypes
public static final int... DIST_L1 =1.// Block distance
        DIST_L2 = 2.// Euclidean distance
        DIST_C = 3.// checkerboard distance...Copy the code

Parameter 4: maskSize, the size of the distance transform mask matrix. If the previous parameter is DIST_L1 or DIST_C, this parameter is forced to be set to 3. Because the 3X3 template is the same as the 5X5 template. Possible values are as follows:

// C++: enum DistanceTransformMasks
public static final int
        DIST_MASK_3 = 3,
        DIST_MASK_5 = 5,
        DIST_MASK_PRECISE = 0;
Copy the code

Parameter 5: dstType, the data type of the output image, can be CV_8U or CV_32F. CV_8U applies only to scenarios where distanceType is DIST_L1.

operation

* author: yidong * 2020/6 */
class DistanceTransformActivity : AppCompatActivity() {
    private lateinit var mBinding: ActivityDistanceTransformBinding
    private lateinit var mBinary: Mat
    override fun onCreate(savedInstanceState: Bundle?). {
        super.onCreate(savedInstanceState)
        mBinding = DataBindingUtil.setContentView(this, R.layout.activity_distance_transform)

        val bgr = Utils.loadResource(this, R.drawable.number)
        val gray = Mat()
        Imgproc.cvtColor(bgr, gray, Imgproc.COLOR_BGR2GRAY)
        mBinary = Mat()
        // Pixels in the region are represented by zero
        Imgproc.threshold(gray, mBinary, 50.0.255.0, Imgproc.THRESH_BINARY_INV)
        showMat(mBinding.ivLena, mBinary)
        bgr.release()
        gray.release()
    }

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

    override fun onOptionsItemSelected(item: MenuItem): Boolean {
        title = item.title
        when (item.itemId) {
            R.id.dt_l1 -> {
                doDistanceTransform(Imgproc.DIST_L1)
            }
            R.id.dt_l2 -> {
                doDistanceTransform(Imgproc.DIST_L2)
            }
            R.id.dt_c -> {
                doDistanceTransform(Imgproc.DIST_C)
            }
        }
        return true
    }

    private fun showMat(view: ImageView, source: Mat) {
        val bitmap = Bitmap.createBitmap(source.width(), source.height(), Bitmap.Config.ARGB_8888)
        Utils.matToBitmap(source, bitmap)
        view.setImageBitmap(bitmap)
    }

    private fun doDistanceTransform(flag: Int) {
        val dst = Mat()
        // Calculate the approximate or exact distance between each binary image pixel and the nearest zero pixel. For zero image pixels, the distance is obviously zero.
        Imgproc.distanceTransform(mBinary, dst, flag, 5, CvType.CV_32S)
        dst.convertTo(dst, CvType.CV_8U)
        showMat(mBinding.ivResult, dst)
        dst.release()
    }
}
Copy the code

The effect

The source code

Github.com/onlyloveyd/…

In addition, you can also search my official account [OpenCV or Android], follow my series of articles and communicate with me.