2024, 35(6):2583-2584. DOI: 10.13328/j.cnki.jos.007103
摘要:
2024, 35(6):2585-2607. DOI: 10.13328/j.cnki.jos.007096
摘要:Go 语言, 也称Golang, 由于其语法简单、原生支持并发、自动内存管理等特性, 近年受到很多开发者的欢迎. Go 语言期望开发者不必了解变量或对象是分配在栈上还是在堆中, 而由 Go 编译器的逃逸分析来决定分配位置, 再由 Go 垃圾收集器自动回收无用的堆对象. Go 的逃逸分析必须正确决定对象的分配位置以保证内存状态的正确性. 然而, 目前 Go 社 区中逃逸相关问题频发, 潜在导致程序崩溃等致命问题, 而目前对该方面的研究缺失. 为有效检测编译器生成的代码是否存在可能引起运行时崩溃的非法内存引用, 填补研究空白, 对Go 程序执行进行抽象建模, 并提出两条判定写入违例的规则. 基于这两条规则, 克服 Go 二进制中高层语义缺失、运行时信息不便获取等挑战, 设计一个轻量化的分析工具 DBI-Go. DBI-Go 采用静态分析加动态二进制插桩的分析方式, 基于动态二进制分析框架 Pin 来实现, 可以识别 Go 二进制中违例的 store 指令. 实验结果表明, DBI-Go 可以检测出 Go 社区中所有已知的逃逸相关 Issues; DBI-Go 还发现一个目前 Go 社区未知的问题, 该问题已经得到确认. 在实际项目上的应用则表明 DBI-Go 可以帮助开发人员找出逃逸算法的错误. 测试结果还表明DBI-Go 采取的措施可以有效降低误报率且在 93.3% 的情况下带来的额外运行时开销小于原先的 2 倍. 同时, DBI-Go 无需修改 Go 的编译运行时, 可以适配不同版本的 Go, 有较高的适用性.
2024, 35(6):2608-2630. DOI: 10.13328/j.cnki.jos.007100
摘要:指针分析是对软件进行编译优化、错误检测的核心基础技术之一. 现有经典指针分析框架, 如Doop, 会将待分析程序和分析算法转化成Datalog评估问题并进行求解, 如程序规模较大, 单次求解分析时间开销较大. 在程序频繁变更发布的情况下, 相关程序分析的开销更是难以负担. 近年来, 增量分析作为一种在代码频繁变更场景下有效复用已有分析结果提升分析效率的技术受到了越来越多的关注. 然而, 目前的增量指针分析技术通常针对特定算法设计, 支持的指针分析选项有限, 其可用性也受到较大限制. 针对上述问题, 设计并实现一种基于差分式Datalog求解的增量指针分析框架DDoop (Differential Doop). DDoop实现增量输入事实生成技术与增量分析规则自动化重写技术, 将多版本程序增量分析问题表达为差分Datalog评估问题, 从而可以充分利用成熟的差分式Datalog求解引擎, 如DDlog, 来实现端到端的增量指针分析, 并最大化兼容复用Doop中已有的指针分析实现, 提供透明的增量化支持. 在广泛应用的真实世界程序上对DDoop进行实验评估, 实验结果显示DDoop相较于非增量的Doop框架具有显著的性能优势, 同时高度兼容Doop中已有的各种指针分析规则.
2024, 35(6):2631-2647. DOI: 10.13328/j.cnki.jos.007097
摘要:寄存器绑定是高层次综合中的一个基础优化问题, 主要目标是在保证电路功能的同时最小化寄存器资源的使用. 传统的方法尝试将编译器的寄存器分配算法应用于寄存器绑定中, 但却忽略了分配问题与绑定问题的差异性, 因此在绑定过程中引入了额外的资源约束, 或采用了不适合电路设计的编译优化技巧, 从而导致资源浪费. 为解决这些问题, 将寄存器绑定问题转化为连续多重着色问题, 并提出一种基于位宽与顶点度结合的启发式求解方法. 所提方法通过对变量的位宽和活跃区间等信息的细粒度刻画和建模, 能够进一步优化寄存器资源的开销, 同时无需插入额外的指令. 将该算法与两种典型算法进行比较, 实验结果表明, 所提算法在MiBench测试集的96.72%的测试用例中达到理论最优解, 比其他两种方法分别提高31.5%和25.1%; 在Rosetta测试集的所有测试用例中均表现为最优解, 比其他两种方法分别提高7.41%和7.39%.
2024, 35(6):2648-2667. DOI: 10.13328/j.cnki.jos.007098
摘要:申威众核片上多级存储层次是缓解众核“访存墙”的重要结构. 完全由软件管理的SPM结构和片上RMA通信机制给应用性能提升带来很多机会, 但也给应用程序开发优化与移植提出了很大挑战. 为充分挖掘片上存储层次特点提升应用程序性能, 同时减轻用户编程优化负担, 提出一种多级存储层次访存与通信融合的编译优化方法. 该方法首先设计融合编译指示, 将程序高层信息传递给编译器. 其次构建编译优化收益模型并设计启发式循环优化方案迭代求解框架, 并由编译器完成循环优化方案的求解和优化代码的变换. 通过编译生成的DMA和RMA批量数据传输操作, 将较低存储层次空间中高访问延迟的核心数据批量缓冲进低访问延迟的更高存储层次空间中. 在3个典型测试用例上进行优化实验测试与分析, 结果表明所提出的优化在性能上与手工优化相当, 较未优化版程序性能有显著提升.
2024, 35(6):2668-2686. DOI: 10.13328/j.cnki.jos.007102
摘要:随着深度学习模型和硬件架构的快速发展, 深度学习编译器已经被广泛应用. 目前, 深度学习模型的编译优化和调优的方法主要依赖基于高性能算子库的手动调优和基于搜索的自动调优策略. 然而, 面对多变的目标算子和多种硬件平台的适配需求, 高性能算子库往往需要为各种架构进行多次重复实现. 此外, 现有的自动调优方案也面临着搜索开销大和缺乏可解释性的挑战. 为了解决上述问题, 提出AutoConfig, 一种面向深度学习编译优化的自动配置机制. 针对不同的深度学习计算负载和特定的硬件平台, AutoConfig可以构建具备可解释性的优化算法分析模型, 采用静态信息提取和动态开销测量的方法进行综合分析, 并基于分析结果利用可配置的代码生成技术自动完成算法选择和调优. AutoConfig创新性地将优化分析模型与可配置的代码生成策略相结合, 不仅能保证性能加速效果, 还能减少重复开发的开销, 同时可以简化调优过程. 在此基础上, 进一步将AutoConfig集成到深度学习编译器Buddy Compiler中, 对矩阵乘法和卷积的多种优化算法建立分析模型, 并将自动配置的代码生成策略应用在多种SIMD硬件平台上进行评估. 实验结果可验证AutoConfig在代码生成策略中完成参数配置和算法选择的有效性. 与经过手动或自动优化的代码相比, 由AutoConfig生成的代码可达到相似的执行性能, 并且无需承担手动调优的重复实现开销和自动调优的搜索开销.
2024, 35(6):2687-2723. DOI: 10.13328/j.cnki.jos.007099
摘要:随着信息技术的快速发展, 涌现出各种新型处理器体系结构. 新的体系结构出现为处理器多样化发展带来机遇的同时也提出了巨大挑战, 需要兼容运行已有软件, 确保较为丰富的软件生态群. 但要在短期内从源码编译构建大量生态软件并非易事, 二进制翻译作为一种直接从二进制层面迁移可执行代码技术, 支持跨平台软件兼容运行, 既扩大了软件生态群, 又有效降低了应用程序与硬件之间的耦合度. 近年来, 二进制翻译技术研究取得了较大进展. 为总结现有成果并分析存在的不足, 首先介绍二进制翻译技术的分类以及典型的二进制翻译系统, 之后从指令翻译方法、关键问题研究、优化技术等方面分别进行分析总结, 接着阐述二进制翻译技术的核心应用领域, 最后对二进制翻译技术的潜在研究方向进行展望.
2024, 35(6):2724-2752. DOI: 10.13328/j.cnki.jos.007101
摘要:群体智能系统通过邻居个体的信息交互实现群体级别的应用任务, 具有良好的鲁棒性和灵活性. 与此同时, 大多数开发人员难以对分布式、并行的个体交互机制进行描述. 一些高级语言允许用户以串行思维方式、从系统全局角度来编程并行的群体智能计算任务, 而无需考虑通信协议、数据分布等底层交互细节. 但面向用户、全局声明式的群体智能系统应用程序与个体并行执行逻辑存在的巨大语义差距, 使得编译过程复杂进而导致应用程序开发效率不高. 提出一个编译系统及其支撑工具, 支持将高级的群体智能系统应用程序转换为安全、高效的分布式实现. 所提编译系统通过并行信息识别, 计算划分, 交互信息生成技术, 将面向系统全局、串行编程的群体智能应用程序编译为面向个体独立执行的并行目标代码, 从而使用户不必了解个体间的复杂交互机制. 设计一种标准化中间表示, 将复杂群体智能计算任务转换为群体智能算子和输入输出变量组合而成的标准化语义模块序列, 其以独立于平台的形式表示源程序信息, 屏蔽目标硬件平台的异构性. 在一个群体智能系统案例平台中部署和测试所提编译系统, 结果表明该系统能够有效将群体智能应用程序编译为平台可执行的目标代码并提升应用程序开发效率, 其生成的代码在一系列基准测试中具有比现有编译器更好的性能.
2024, 35(6):2753-2774. DOI: 10.13328/j.cnki.jos.006836
摘要:以深度神经网络(deep neural network, DNN)为基础构建的自动驾驶软件已成为最常见的自动驾驶软件解决方案. 与传统软件一样, DNN也会产生不正确输出或意想不到的行为, 基于DNN的自动驾驶软件已经导致多起严重事故, 严重威胁生命和财产安全. 如何有效测试基于DNN的自动驾驶软件已成为亟需解决的问题. 由于DNN的行为难以预测和被人类理解, 传统的软件测试方法难以适用. 现有的自动驾驶软件测试方法通常对原始图片加入像素级的扰动或对图片整体进行修改来生成测试数据, 所生成的测试数据通常与现实世界差异较大, 所进行扰动的方式也难以被人类理解. 为解决上述问题, 提出测试数据生成方法IATG (interpretability-analysis-based test data generation), 使用DNN的解释方法获取自动驾驶软件所做出决策的视觉解释, 选择原始图像中对决策产生重要影响的物体, 通过将其替换为语义相同的其他物体来生成测试数据, 使生成的测试数据更加接近真实图像, 其过程也更易于理解. 转向角预测模型是自动驾驶软件决策模块重要组成部分, 以此类模型为例进行实验, 结果表明解释方法的引入有效增强IATG对转向角预测模型的误导能力. 此外, 在误导角度相同时IATG所生成测试数据比DeepTest更加接近真实图像; 与semSensFuzz相比, IATG具有更高误导能力, 且IATG中基于解释分析的重要物体选择技术可有效提高semSensFuzz的误导能力.
2024, 35(6):2775-2794. DOI: 10.13328/j.cnki.jos.006904
摘要:代码评审是现代软件开发过程中被广泛应用的最佳实践之一, 其对于软件质量保证和工程能力提升都具有重要意义. 代码评审意见是代码评审最主要和最重要的产出之一, 其不仅是评审者对代码变更的质量感知, 而且是作者修复代码缺陷和提升质量的重要参考. 目前, 全球各大软件组织都相继制定了代码评审指南, 但仍缺少针对代码评审意见质量的有效的评价方式和方法. 为了实现可解释的、自动化的评价, 开展文献综述、案例分析等若干实证研究, 并在此基础上提出一种基于多标签学习的代码评审意见质量评价方法. 实验使用某大型软件企业的34个商业项目的共计17 000条评审意见作为数据集. 结果表明所提出的方法能够有效地评价代码评审意见质量属性和质量等级. 除此以外, 还提供若干建模经验, 如评审意见标注和校验等, 旨在帮助那些受代码评审困扰的软件组织更好地实施所提出的方法.
2024, 35(6):2795-2820. DOI: 10.13328/j.cnki.jos.006905
摘要:机器学习方法可很好地与软件测试相结合, 增强测试效果, 但少有学者将其运用于测试数据生成方面. 为进一步提高测试数据生成效率, 提出一种结合SVM (support vector machine)和XGBoost (extreme gradient boosting)的链式模型, 并基于此模型借助遗传算法实现多路径测试数据生成. 首先, 利用一定样本训练若干个用于预测路径节点状态的子模型(SVM和XGBoost), 通过子模型的预测精度值筛选最优子模型, 并根据路径节点顺序将其依次链接, 形成一个链式模型C-SVMXGBoost (chained SVM and XGBoost). 在利用遗传算法生成测试用例时, 使用训练好的链式模型代替插桩法获取测试数据覆盖路径(预测路径), 寻找预测路径与目标路径相似的路径集, 对存在相似路径集的预测路径进行插桩验证, 获取精确路径, 计算适应度值. 在交叉变异过程中引入样本集中路径层级深度较大的优秀测试用例进行重用, 生成覆盖目标路径的测试数据. 最后, 保留进化生成中产生的适应度较高的个体, 更新链式模型C-SVMXGBoost, 进一步提高测试效率. 实验表明, C-SVMXGBoost较其他各对比链式模型更适合解决路径预测问题, 可提高测试效率. 并且通过与已有经典方法相比, 所提方法在覆盖率上提高可达15%, 平均进化代数也有所降低, 在较大规模程序上其降低百分比可达65%.
2024, 35(6):2821-2843. DOI: 10.13328/j.cnki.jos.006906
摘要:软件产品线测试是一项非常具有挑战性的工作. 基于相似性的测试方法通过提升测试集的多样性以达到提高测试覆盖率和缺陷检测率的目的. 因其具有良好的可拓展性和较好的测试效果, 目前已成为软件产品线测试的重要手段之一. 在该测试方法中, 如何产生多样化的测试用例和如何维护测试集的多样性是两个关键问题. 针对以上问题, 提出一种基于多样性可满足性(SAT)求解器和新颖性搜索(novelty search, NS)的软件产品线测试算法. 具体地, 所提算法同时采用两类多样性SAT求解器产生多样化的测试用例. 特别地, 为了改善随机局部搜索SAT求解器的多样性, 提出一种基于概率向量的通用策略产生候选解. 此外, 为同时维护测试集的全局和局部多样性, 设计并运用两种基于NS算法思想的归档策略. 在50个真实软件产品线上的消融和对比实验验证多样性SAT求解器和两种归档策略的有效性, 以及所提算法较其他主流算法的优越性.
2024, 35(6):2844-2862. DOI: 10.13328/j.cnki.jos.006907
摘要:BPEL (business process execution language)是一种可执行的Web服务组合语言. 与传统程序相比, BPEL程序在编程模型、执行方式等方面存在较大差异. 这些新特点使得如何定位并修改测试阶段发现的BPEL程序故障成为挑战, 面向传统软件的故障修复技术难以直接应用于BPEL程序. 从变异分析角度出发, 提出一种基于模板匹配的BPEL程序故障修复方法BPELRepair. 为了克服基于变异分析的故障修复技术计算开销高的缺点, 从补丁生成、测试用例选择以及终止条件3个角度提出多种优化策略. 开发一个BPEL故障修复支持工具, 提高故障修复的自动化程度与效率. 采用经验研究的方式, 评估所提故障修复技术及优化策略的有效性. 实验结果表明, 所提故障修复方法能够成功修复约53%的BPEL程序故障; 所提优化策略能够显著降低搜索匹配、补丁程序验证、测试用例执行与故障修复等方面的开销.
2024, 35(6):2863-2879. DOI: 10.13328/j.cnki.jos.006910
摘要:代码搜索是当下自然语言处理和软件工程交叉领域的一个重要分支. 开发高效的代码搜索算法能够显著提高代码重用的能力, 从而有效提高软件开发人员的工作效率. 代码搜索任务是以描述代码片段功能的自然语言作为输入, 在海量代码库中搜索得到相关代码片段的过程. 基于序列模型的代码搜索方法DeepCS虽然取得了很好的效果, 但这种方法不能捕捉代码的深层语义. 基于图嵌入的代码搜索方法GraphSearchNet能缓解这个问题, 但没有对代码与文本进行细粒度匹配, 也忽视了代码图和文本图的全局关系. 为了解决以上局限性, 提出基于关系图卷积网络的代码搜索方法, 对构建的文本图和代码图编码, 从节点层面对文本查询和代码片段进行细粒度匹配, 并应用神经张量网络捕捉它们的全局关系. 在两个公开数据集上的实验结果表明, 所提方法比先进的基线模型DeepCS和GraphSearchNet搜索精度更高.
2024, 35(6):2880-2902. DOI: 10.13328/j.cnki.jos.006918
摘要:第三方库检测是Android应用安全分析领域的上游任务, 其检测精度对于恶意应用检测、重打包检测、隐私泄露等下游任务有显著影响. 为了提升检测精度和效率, 采用相似性比较的思想, 提出一种基于包结构和签名的第三方库检测方法, 命名为LibPass. LibPass以流水线式模式组合主模块识别、第三方库候选识别和细粒度检测等3个组件. 主模块识别方法区分主程序二进制代码与引入的第三方库二进制代码, 旨在提升方法检测效率. 在此基础上, 提出由第三方库候选识别和细粒度检测构成的两阶段检测方法. 前者利用包结构特征的稳定性来应对应用程序的混淆行为以提升混淆情形下的检测精度, 并利用包结构签名完成快速比对以识别候选第三方库, 达到显著降低成对比较次数、提升检测效率的目的; 后者在前者涮选出的候选中, 通过更细粒度但代价更高的相似性分析精确地识别第三方库及其对应的版本. 为了验证方法的性能和效率, 构建3个评估不同检测能力的基准数据集, 在这些基准数据集上开展实验验证, 从检测性能、检测效率和抗混淆性等方面对实验结果进行深入分析, 结果表明LibPass具备较高的检测精度, 检测效率, 以及应对多种常用混淆操作的能力.
2024, 35(6):2903-2922. DOI: 10.13328/j.cnki.jos.006920
摘要:基于宽度学习的动态模糊推理系统(broad-learning-based dynamic fuzzy inference system , BL-DFIS)能自动构建出精简的模糊规则并获得良好的分类性能. 然而, 当遇到大型复杂的数据集时, BL-DFIS因会使用较多模糊规则来试图达到令人满意的识别精度, 从而对其可解释性造成了不利影响. 对此, 提出一种兼顾分类性能和可解释性的模糊神经网络, 将其称为特征扩展的随机向量函数链神经网络(FA-RVFLNN). 在该网络中, 一个以原始数据为输入的RVFLNN被作为主体结构, BL-DFIS则用作性能补充, 这意味着FA-RVFLNN包含具有性能增强作用的直接链接. 由于主体结构的增强节点使用Sigmoid激活函数, 因此, 其推理过程可借助一种模糊逻辑算子(I-OR)来解释. 而且, 具有明确含义的原始输入数据也有助于解释主体结构的推理规则. 在直接链接的支撑下, FA-RVFLNN可利用增强节点、特征节点和模糊节点学到更丰富的有用信息. 实验表明: FA-RVFLNN既减缓了主体结构RVFLNN中过多增强节点带来的“规则爆炸”问题, 也提高了性能补充结构BL-DFIS的可解释性(平均模糊规则数降低了50%左右), 在泛化性能和网络规模上仍具有竞争力.
2024, 35(6):2923-2935. DOI: 10.13328/j.cnki.jos.006927
摘要:实体识别是信息抽取的关键技术. 相较于普通文本, 中文医疗文本的实体识别任务往往面对大量的嵌套实体. 以往识别实体的方法往往忽视了医疗文本本身所特有的实体嵌套规则而直接采用序列标注方法, 为此, 提出一种融合实体嵌套规则的中文实体识别方法. 所提方法在训练过程中将实体的识别任务转化为实体的边界识别与边界首尾关系识别的联合训练任务, 在解码过程中结合从实际医疗文本中所总结出来的实体嵌套规则对解码结果进行过滤, 从而使得识别结果能够符合实际文本中内外层实体嵌套组合的组成规律. 在公开的医疗文本实体识别的实验上取得良好的效果. 数据集上的实验表明, 所提方法在嵌套类型实体识别性能上显著优于已有的方法, 在整体准确率方面比最先进的方法提高0.5%.
2024, 35(6):2936-2950. DOI: 10.13328/j.cnki.jos.006928
摘要:检测训练集分布之外的分布外(out-of-distribution, OOD)样本对于深度神经网络(deep neural network, DNN)分类器在开放环境的部署至关重要. 检测OOD样本可以视为一种二分类问题, 即把输入样本分类为“分布内(in-distribution, ID)”类或“分布外”类. 进一步地, 检测器自身还可能遭受到恶意的对抗攻击而被再次绕过. 这些带有恶意扰动的OOD样本称为对抗OOD样本. 构建鲁棒的OOD检测器以检测对抗OOD样本是一项更具挑战性的任务. 为习得可分离且对恶意扰动鲁棒的表示, 现有方法往往利用辅助的干净OOD样本邻域内的对抗OOD样本来训练DNN. 然而, 由于辅助的OOD训练集与原ID训练集的分布差异, 训练对抗OOD样本无法足够有效地使分布内决策边界对对抗扰动真正鲁棒. 从ID样本的邻域内生成的对抗ID样本拥有与原ID样本近乎一样的语义信息, 是一种离分布内区域更近的OOD样本, 对提升分布内边界对对抗扰动的鲁棒性很有效. 基于此, 提出一种半监督的对抗训练方法——谛听, 来构建鲁棒的OOD检测器, 用以同时检测干净OOD样本和对抗OOD样本. 谛听将对抗ID样本视为一种辅助的“近OOD”样本, 并将其与其他辅助的干净OOD样本和对抗OOD样本联合训练DNN, 以提升OOD检测的鲁棒性. 实验结果表明, 谛听在检测由强攻击生成的对抗OOD样本上具有显著的优势, 同时在原分类主任务及检测干净OOD样本上保持先进的性能.
2024, 35(6):2951-2973. DOI: 10.13328/j.cnki.jos.006901
摘要:混合事务与分析处理数据库系统(HTAP)因其在一套系统上可以同时处理混合负载而逐渐获得大众认可. 为了不影响在线事务处理(OLTP)业务的写入性能, HTAP数据库系统往往会通过维护数据多版本或额外副本的方式来支持在线分析处理(OLAP)任务, 从而引入了TP/AP端版本的数据一致性问题. 同时, HTAP数据库系统面临资源隔离下实现高效数据共享的核心挑战, 且数据共享模型的设计综合权衡了业务对性能和数据新鲜度之间的要求. 因此, 为了系统地阐释现有HTAP数据库系统数据共享模型及优化策略, 首先根据TP生成版本与AP查询版本的差异, 通过一致性模型定义数据共享模型, 将HTAP数据共享的一致性模型分为3类, 分别为线性一致性, 顺序一致性与会话一致性. 然后, 梳理数据共享模型的全流程, 即从数据版本标识号分配, 数据版本同步, 数据版本追踪3个核心问题出发, 给出不同一致性模型的实现方法. 进一步, 以典型的HTAP数据库系统为例对具体实现进行深入的阐释. 最后, 针对数据共享过程中涉及的版本同步、追踪、回收等模块的优化策略进行归纳和分析, 并展望数据共享模型的优化方向, 指出数据同步范围自适应, 数据同步周期自调优和顺序一致性的新鲜度阈值约束控制是提高HTAP数据库系统性能和新鲜度的可能手段.
2024, 35(6):2974-2998. DOI: 10.13328/j.cnki.jos.006915
摘要:推荐系统在成熟的数据挖掘技术推动下, 已能高效地利用评分数据、行为轨迹等显隐性信息, 再与复杂而先进的深度学习技术相结合, 取得了很好的效果. 同时, 其应用需求也驱动着对基础数据的深度挖掘与利用, 以及对技术要求的减负成为一个研究热点. 基于此, 提出一种利用GCN (graph convolutional network)方法进行深度信息融合的轻量级推荐模型LG_APIF. 该模型结合行为记忆, 通过艾宾浩斯遗忘曲线模拟用户兴趣变化过程, 采用线性回归等相对轻量的传统方法挖掘项目的自适应周期等深度信息; 分析用户当前的兴趣分布, 计算项目的兴趣量, 以获取用户的潜在兴趣类型; 构建用户-类型-项目三元组的图结构, 并结合减负后的GCN技术来生成最终的项目推荐列表. 实验验证所提方法的有效性, 通过与8个经典模型在Last.fm, Douban, Yelp, MovieLens数据集中的对比, 表明该方法在Precision, Recall及NDCG指标上都得到良好改善, 其中, Precision平均提升2.11%, Recall平均提升1.01%, NDCG平均提升1.48%.
2024, 35(6):2999-3012. DOI: 10.13328/j.cnki.jos.006926
摘要:超图是普通图的泛化表示, 在许多应用领域都很常见, 包括互联网、生物信息学和社交网络等. 独立集问题是图分析领域的一个基础性研究问题, 传统的独立集算法大多都是针对普通图数据, 如何在超图数据上实现高效的最大独立集挖掘是一个亟待解决的问题. 针对这一问题, 提出一种超图独立集的定义. 首先分析超图独立集搜索的两个特性, 然后提出一种基于贪心策略的基础算法. 接着提出一种超图近似最大独立集搜索的剪枝框架即精确剪枝与近似剪枝相结合, 以精确剪枝策略缩小图的规模, 以近似剪枝策略加快搜索速度. 此外, 还提出4种高效的剪枝策略, 并对每种剪枝策略进行理论证明. 最后, 通过在10个真实超图数据集上进行实验, 结果表明剪枝算法可以高效地搜索到更接近于真实结果的超图最大独立集.
2024, 35(6):3013-3035. DOI: 10.13328/j.cnki.jos.006894
摘要:深度学习在图像、文本、语音等媒体数据的分析任务上取得了优异的性能. 数据增强可以非常有效地提升训练数据的规模以及多样性, 从而提高模型的泛化性. 但是, 对于给定数据集, 设计优异的数据增强策略大量依赖专家经验和领域知识, 而且需要反复尝试, 费时费力. 近年来, 自动化数据增强通过机器自动设计数据增强策略, 已引起了学界和业界的广泛关注. 为了解决现有自动化数据增强算法尚无法在预测准确率和搜索效率之间取得良好平衡的问题, 提出一种基于自引导进化策略的自动化数据增强算法SGES AA. 首先, 设计一种有效的数据增强策略连续化向量表示方法, 并将自动化数据增强问题转换为连续化策略向量的搜索问题. 其次, 提出一种基于自引导进化策略的策略向量搜索方法, 通过引入历史估计梯度信息指导探索点的采样与更新, 在能够有效避免陷入局部最优解的同时, 可提升搜索过程的收敛速度. 在图像、文本以及语音数据集上的大量实验结果表明, 所提算法在不显著增加搜索耗时的情况下, 预测准确率优于或者匹配目前最优的自动化数据增强方法.
2024, 35(6):3036-3051. DOI: 10.13328/j.cnki.jos.006895
摘要:视网膜层边界的形态变化是眼部视网膜疾病出现的重要标志, 光学相干断层扫描(optical coherence tomography, OCT)图像可以捕捉其细微变化, 基于OCT图像的视网膜层边界分割能够辅助相关疾病的临床判断. 在OCT图像中, 由于视网膜层边界的形态变化多样, 其中与边界相关的关键信息如上下文信息和显著性边界信息等对层边界的判断和分割至关重要. 然而已有分割方法缺乏对以上信息的考虑, 导致边界不完整和不连续. 针对以上问题, 提出一种“由粗到细”的基于端到端深度神经网络和图搜索(graph search, GS)的OCT图像视网膜层边界分割方法, 避免了非端到端方法中普遍存在的“断层”现象. 在粗分割阶段, 提出一种端到端的深度神经网络—注意力全局残差网络(attention global residual network, AGR-Net), 以更充分和有效的方式提取上述关键信息. 具体地, 首先设计一个全局特征模块(global feature module, GFM), 通过从图像的4个方向扫描以捕获OCT图像的全局上下文信息; 其次, 进一步将通道注意力模块(channel attention module, CAM)与全局特征模块串行组合并嵌入到主干网络中, 以实现视网膜层及其边界的上下文信息的显著性建模, 有效解决OCT图像中由于视网膜层形变和信息提取不充分所导致的误分割问题. 在细分割阶段, 采用图搜索算法去除AGR-Net粗分割结果中的孤立区域或和孔洞等, 保持边界的固定拓扑结构和连续平滑, 以实现整体分割结果的进一步优化, 为医学临床的诊断提供更完整的参考. 最后, 在两个公开数据集上从不同的角度对所提出的方法进行性能评估, 并与最新方法进行比较. 对比实验结果也表明所提方法在分割精度和稳定性方面均优于现有方法.
2024, 35(6):3052-3068. DOI: 10.13328/j.cnki.jos.006921
摘要:人们对图像显示设备高分辨率和逼真视觉感知的需求随着现代信息技术的发展日益增长, 这对计算机软硬件提出了更高要求, 也为渲染技术在性能与工作负载上带来更多挑战. 利用深度神经网络等机器学习技术对渲染图像进行质量改进和性能提升成为了计算机图形学热门的研究方向, 其中通过网络推理将低分辨率图像进行上采样获得更加清晰的高分辨率图像是提升图像生成性能并保证高清细节的一个重要途径. 而渲染引擎在渲染流程中产生的几何缓存(geometry buffer, G-buffer)包含较多的语义信息, 能够帮助网络有效地学习场景信息与特征, 从而提升上采样结果的质量. 设计一个基于深度神经网络的低分辨率渲染内容的超分方法. 除了当前帧的颜色图像, 其使用高分辨率的几何缓存来辅助计算并重建超分后的内容细节. 所提方法引入一种新的策略来融合高清缓存与低清图像的特征信息, 在特定的融合模块中对不同种特征信息进行多尺度融合. 实验验证所提出的融合策略和模块的有效性, 并且, 在和其他图像超分辨率方法的对比中, 所提方法体现出明显的优势, 尤其是在高清细节保持方面.