图论分割算法算子消耗模型OCM的建立与分析  

Operator cost model(OCM) and analysis based on graph-based segmentation

作　　者：李荪[1] 李哲英[2] 刘佳[2] 吕彩霞[2] 

机构地区：[1]北京交通大学电子信息工程学院,北京100044 [2]北京联合大学北京市信息服务重点实验室,北京100101

出　　处：《电子测量与仪器学报》2012年第11期1011-1018,共8页Journal of Electronic Measurement and Instrumentation

摘　　要：算法时间复杂度与算法的具体实现方法有关,为使时间复杂度分析具有普遍性,提出了微处理器系统无关的算法操作算子消耗模型(OCM)。根据对最小生成树(MST)图论分割算法的分析,提取算法中操作算子消耗特性,建立了该算法的OCM。MST图论分析算法的OCM给出了该算法的固有计算复杂度,在选择了微处理器系统后,可通过OCM直接获得该算法的时间复杂度。分析结果表明,对于特定尺寸的图像,降低MST图论分割算法时间复杂度的关键是减少加法、除法和比较算子的操作,或优化这3个操作算子的执行过程。同时,对于具有加、减、乘、除、开方和比较运算的微处理系统,该算法算子总消耗量随着k的增大会逐渐减小,当k值趋于无穷大时,算子总消耗量处于稳定的状态。The time complexity of the algorithm is closely related to the specific implementation method. In order to make the analysis of the time complexity more universal, the operator cost model （OCM） was proposed, which has nothing to do with the micro- processor system. According to the analysis of the graph segmentation algorithm based on the minimum spanning tree （MST）, the cost of operators, such as addition, subtraction, multiplication, division and function calculation, is extracted and the operator model is de- veloped. The OCM of the graph-based segmentation based on MST provides the computation complexity with inherent cost characteris- tics. After choosing the microprocessor system, the time complexity can be computed directly. The analysis results show that, as to the images with particular size, decreasing the operating times or optimizing the executing process is the key to reduce the time complexity of the graph-based segmentation based on MST. Meanwhile, in the microprocessor system having the addition, subtraction, multiplica- tion, division and function calculation, the variation of k has a larger impact on total cost of operators with mining value of k. When the value of k goes to infinity, total cost of operators is in a stable condition.

关 键 词：图论分割 计算复杂度 算子消耗模型 

分 类 号：TN301.5[电子电信—物理电子学]