凸包
凸包（Convex Hull）是一个计算几何（图形学）中的概念。在一个实数向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。X的凸包可以用X内所有点(X1，...Xn)的凸组合来构造.在二维欧几里得空间中，凸包可想象为一条刚好包着所有点的橡皮圈。用不严谨的话来讲，给定二维平面上的点集，凸包就是将最外层的点连接起来构成的凸多边形，它能包含点集中所有的点。
凸包
凸包缺陷
凸包缺陷
如图所示，黑色的轮廓线为convexity hull（凸包），而convexity hull（凸包）与手掌之间的部分为convexity defects（凸包缺陷）.
API
代码语言：javascript复制public static void convexHull(MatOfPoint points, MatOfInt hull, boolean clockwise)
- 参数一：points，输入的二维点集。
- 参数二：hull，输出凸包点索引集合。索引指的是第一个参数中二维点集的索引。
- 参数三：clockwise，方向标志位。true时，凸包顺序为顺时针方向；false时，凸包顺序为逆时针方向。
public static void convexityDefects(MatOfPoint contour, MatOfInt convexhull, MatOfInt4 convexityDefects)
- 参数一：contour，输入的轮廓。
- 参数二：convexhull，上面convexHull方法的输出结果hull。
- 参数三：convexityDefects，凸包缺陷特征集合。每个convexity defect区域有四个特征量：起始点（startPoint），结束点(endPoint)，距离convexity hull最远点(farPoint)，最远点到convexity hull的距离(depth)。
算法
[217] Jack Sklansky. Finding the convex hull of a simple polygon. Pattern Recognition Letters, 1(2):79–83, 1982.
操作
代码语言：javascript复制/**
* 凸包检测，凸包缺陷
*
* @author yidong
* @date 2020/10/13
*/
class ConvexHullActivity : AppCompatActivity() {
private lateinit var mBinding: ActivityConvexHullBinding
private lateinit var mSource: Mat
private lateinit var mGray: Mat
override fun onCreate(savedInstanceState: Bundle?) {
super.onCreate(savedInstanceState)
mBinding = DataBindingUtil.setContentView(this, R.layout.activity_convex_hull)
val bgr = Utils.loadResource(this, R.drawable.star)
mSource = Mat()
mGray = Mat()
Imgproc.cvtColor(bgr, mGray, Imgproc.COLOR_BGR2GRAY)
Imgproc.cvtColor(bgr, mSource, Imgproc.COLOR_BGR2RGB)
mBinding.ivLena.showMat(mSource)
doConvexHull()
}
private fun doConvexHull() {
val binary = Mat()
Imgproc.threshold(mGray, binary, 25.0, 255.0, Imgproc.THRESH_BINARY)
val tmp = mSource.clone()
val contours = mutableListOf<MatOfPoint>()
val hierarchy = Mat()
Imgproc.findContours(
binary,
contours,
hierarchy,
Imgproc.RETR_TREE,
Imgproc.CHAIN_APPROX_SIMPLE
)
for (contour in contours) {
val hull = MatOfInt()
val defects = MatOfInt4()
Imgproc.convexHull(contour, hull)
val indexList = hull.toList()
val contourList = contour.toList()
for (i in 0 until indexList.size) {
val index = indexList[i % indexList.size]
val nextIndex = indexList[(i 1) % indexList.size]
val point = contourList[index]
Imgproc.circle(
tmp,
point,
10,
Scalar(255.0, 255.0, 0.0),
2,
Imgproc.LINE_8,
0
)
Log.d(App.TAG, contourList[i].toString())
Imgproc.line(
tmp,
point,
contourList[nextIndex],
Scalar(255.0, 255.0, 0.0),
10,
Imgproc.LINE_8,
0
)
}
Imgproc.convexityDefects(contour, hull, defects)
val defectsList = defects.toList()
for (i in 0 until defectsList.size step 4) {
val start = contourList[defectsList[i]]
val end = contourList[defectsList[i 1]]
val far = contourList[defectsList[i 2]]
Imgproc.line(
tmp,
start,
far,
Scalar(0.0, 0.0, 205.0),
8,
Imgproc.LINE_8,
0
)
Imgproc.line(
tmp,
far,
end,
Scalar(0.0, 0.0, 205.0),
8,
Imgproc.LINE_8,
0
)
Imgproc.line(
tmp,
end,
start,
Scalar(0.0, 0.0, 205.0),
2,
Imgproc.LINE_8,
0
)
}
mBinding.ivResult.showMat(tmp)
}
binary.release()
hierarchy.release()
tmp.release()
}
override fun onDestroy() {
mSource.release()
mGray.release()
super.onDestroy()
}
}
效果
下图中，黄色部分为凸包，蓝色部分为凸包缺陷。
凸包与凸包缺陷
源码
https://github.com/onlyloveyd/LearningAndroidOpenCV
