发布人:     发布日期: 2023-05-04    浏览次数:

近日，威尼斯论坛wnsr及前沿交叉研究院甘祥超教授团队在TPAMI (IEEE Transactions on Pattern Analysis and Machine Intelligence, IF=24.314)上发表题为“An integrated fast Hough transform for multidimensional data”的研究论文（https://doi.org/10.1109/TPAMI.2023.3269202），介绍了一种在多维空间数据点云中检测直线、平面及超平面等目标的快速检测算法。它可以用于高维数据的数据挖掘、分类和模式识别，在计算机视觉、自动驾驶、人工智能和数据分类等方向具有广泛应用前景。

直线检测是物体识别的基础，在人工智能和计算机视觉中具有举足轻重的地位。当拓展到三维甚至更高维度的数据空间时，霍夫变换对应的检测目标是平面和超平面(hyperplane)。但是由于“数据维度的诅咒”，在多维空间中相应算法的计算量和复杂度往往呈指数级的增加。目前，由IBM公司的Li等人于1986年提出的快速霍夫变换专利算法是该领域唯一可用的算法，该算法被一些通用的计算机图像处理类库如gandalf开源实现并获得广泛应用。但该算法具有重大缺陷，一是其数学模型使用同数据维度相等数量的参数子空间，同一目标可能会投射到多个子空间中，需要额外算法检测冗余目标；二是算法精度在参数空间非均匀分布，存在众多检测效率谷点。

本研究建立了新的直线、平面及超平面的数学模型，并开发了一体化快速霍夫变换。一体化快速霍夫变换只需要使用一个单一的参数空间，并利用单一k字节树编码所有参数空间的信息，大大消减系统中的计算量和存储需求。这一新方法还具有两个重要的优势：首先，IBM快速霍夫变换的拟合模式对应的是最小二乘法，数据噪声只存在数据的一个维度上，而一体化快速霍夫变换则对应总最小二乘拟合算法，模型假设数据噪声是遍布所有维度的，因此对数据噪声容忍度更好，在实际应用中很好解决了IBM快速霍夫变换的算法精度在参数空间非均匀分布的问题。其次，一体化快速霍夫变换中，在数据空间中彼此距离越近的目标在参数空间中越聚集，这使我们可以直观的图形显示参数空间中的数据分析过程，从而快速判断目标的数量，可视化的指导系统参数设定并避免重复识别目标。

图一. 三维空间的点云数据及一体化快速霍夫变换参数空间映射

图二. Kinect拍摄的三维RGB-D图片、深度图及一体化快速霍夫变换检测检测出来的平面

南京农业大学为该论文唯一单位，威尼斯论坛wnsr在读二年级博生李艳慧为该论文第一作者，甘祥超教授为该论文通讯作者。该研究得到科技部科技创新2030---“新一代人工智能”，国家自然科学基金，江苏省前沿引领技术基础研究专项，现代作物生产省部共建协同创新中心等项目的资助。