Processing math: 3%
We use cookies to improve your experience with our site.

A Transfer Function Design for Medical Volume Data Using a Knowledge Database Based on Deep Image and Primitive Intensity Profile Features Retrieval

Younhyun Jung, Jim Kong, Bin Sheng, Jinman Kim

downloadPDF
盛斌, . 基于深度图像和基本强度剖面特征检索的医学体数据传输函数[J]. 计算机科学技术学报, 2024, 39(2): 320-335. DOI: 10.1007/s11390-024-3419-7
引用本文: 盛斌, . 基于深度图像和基本强度剖面特征检索的医学体数据传输函数[J]. 计算机科学技术学报, 2024, 39(2): 320-335. DOI: 10.1007/s11390-024-3419-7
Jung Y, Kong J, Sheng B et al. A transfer function design for medical volume data using a knowledge database based on deep image and primitive intensity profile features retrieval. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 39(2): 320−335 Mar. 2024. DOI: 10.1007/s11390-024-3419-7.
Citation: Jung Y, Kong J, Sheng B et al. A transfer function design for medical volume data using a knowledge database based on deep image and primitive intensity profile features retrieval. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 39(2): 320−335 Mar. 2024. DOI: 10.1007/s11390-024-3419-7.
盛斌, . 基于深度图像和基本强度剖面特征检索的医学体数据传输函数[J]. 计算机科学技术学报, 2024, 39(2): 320-335. CSTR: 32374.14.s11390-024-3419-7
引用本文: 盛斌, . 基于深度图像和基本强度剖面特征检索的医学体数据传输函数[J]. 计算机科学技术学报, 2024, 39(2): 320-335. CSTR: 32374.14.s11390-024-3419-7
Jung Y, Kong J, Sheng B et al. A transfer function design for medical volume data using a knowledge database based on deep image and primitive intensity profile features retrieval. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 39(2): 320−335 Mar. 2024. CSTR: 32374.14.s11390-024-3419-7.
Citation: Jung Y, Kong J, Sheng B et al. A transfer function design for medical volume data using a knowledge database based on deep image and primitive intensity profile features retrieval. JOURNAL OF COMPUTER SCIENCE AND TECHNOLOGY 39(2): 320−335 Mar. 2024. CSTR: 32374.14.s11390-024-3419-7.

基于深度图像和基本强度剖面特征检索的医学体数据传输函数

A Transfer Function Design for Medical Volume Data Using a Knowledge Database Based on Deep Image and Primitive Intensity Profile Features Retrieval

Funds: This work was supported by the Korea Health Technology Research and Development Project through the Korea Health Industry Development Institute under Grant No. HI22C1651, the National Research Foundation of Korea (NRF) under Grant No. 2021R1F1A1059554, and the Culture, Sports and Tourism Research and Development Program through the Korea Creative Content Agency Grant funded by the Ministry of Culture, Sports and Tourism of Korea under Grant No. RS-2023-00227648.
More Information
    Author Bio:

    Younhyun Jung received his B.S. degree in computer science from Inha University, Incheon, in 2008, and his Ph.D. degree in computer science from The University of Sydney, Sydney, in 2016. He is currently an assistant professor in computer science with School of Computing, Gachon University, Seongnam. He was a software engineer with Samsung Electronics from 2007 to 2010. His current research interests include volume rendering and multimodal medical image visualization

    Jim Kong received his B.S. (Hons.) degree in computer science from The University of Sydney, Sydney, in 2016. He is currently a software development engineer in Amazon, Sydney

    Bin Sheng received his B.A. degree in English and his B.Eng. degree in computer science from Huazhong University of Science and Technology, Wuhan, in 2004, and his M.Sc. degree in software engineering from the University of Macau, Macau, in 2007, and his Ph.D. degree in computer science and engineering from The Chinese University of Hong Kong, Hong Kong, in 2011. He is currently a professor with the Department of Computer Science and Engineering, Shanghai Jiao Tong University, Shanghai. He is an associate editor of the IEEE Transactions on Circuits and Systems for Video Technology, and The Visual Computer Journal. His current research interests include virtual reality and computer graphics

    Jinman Kim received his B.S. (Hons.) and his Ph.D. degrees in computer science both from the University of Sydney, Sydney, in 2001 and 2006, respectively. From 2008 to 2012, he was an ARC Post-Doctoral Research Fellow, one year leave from 2009 to 2010 to join the MIRALab Research Group, Geneva, as a Marie Curie senior research fellow. Since 2013, he has been with the School of Information Technologies, The University of Sydney, Sydney, where he was a senior lecturer, and became a professor in 2022. His current research interests include medical image analysis and visualization, computeraided diagnosis, and telehealth technologies. He is an associate editor of The Visual Computer Journal

    Corresponding author:

    Bin Sheng: shengbin@sjtu.edu.cn

  • 摘要:
    研究背景 

    本研究旨在深入探索计算机图形学及体绘制技术在医学图像分析领域中的实际运用。鉴于医学影像数据往往具有三维结构和体积特性,常通过切片堆叠的方式形成三维影像。尽管传统的体绘制技术能够实现一定程度的图像可视化,但在细节展现和效果优化方面仍存在明显不足。为此,本研究提出了一种基于内容检索的转移函数生成方法,旨在提升医学图像的可视化质量。直接体积渲染作为本研究的重点议题,其传输函数的设计与实施至关重要。目前,大多数直接体渲染技术仍需用户亲自浏览知识库,进行传输函数的选择与调整,这无疑增加了工作负担和人力成本。针对这一问题,本研究开发了一种高效的自动化检索知识库方法,以期在医学领域三维成像中实现更广泛的应用价值。通过本研究,有望为医学影像分析提供更准确、高效的可视化手段,进而推动相关领域的科技进步。这一研究成果将对医学影像处理与分析产生积极影响,有望为医疗诊断、治疗和研究提供更准确、直观和高效的视觉支持。

    目的 

    针对当前直接体积渲染方法存在的不足,如手动检索和调整传输函数的繁琐性,以及现有基于内容检索的传输函数设计方法在处理多感兴趣结构时的局限性,本文提出了一种创新的传输函数设计策略。通过引入一种新颖的基于内容检索的方法,该方法能够自动检索知识库,并融合自动识别感兴趣区域的推理过程,显著减少多维传输函数的设计与优化步骤。这一改进旨在优化医学图像的可视化效果,为医学诊断与分析提供更为直观、精确的视觉支持。

    方法 

    本文提出了基于三元输入查询的新型方法,旨在从给定的体积数据中精确提取体影像数据特征。此方法的核心在于构建一个用户定义的感兴趣结构射线,并辅以两个与射线共平面的三维图像。为了从这两张共平面图像中提取高级区域空间语义的图像特征,本文采用了预训练的卷积神经网络。在定位感兴趣结构方面,本文创新性地沿用了结构的强度轮廓,并结合动态时间规整技术,以应对相似轮廓间可能存在的微小对齐差异。此外,本文还开发了一种两阶段基于内容检索的方法,该方法通过巧妙结合卷积神经网络和动态时间规整两种技术的检索结果,实现了互补优化,从而显著提升了检索效率。为了提升用户交互的便捷性和直观性,本文还引入了一种基于笔画的、以图像为中心的交互方式。用户仅需简单绘制射线(在二维横截面视图上)或选择点(在三维直接体积渲染上),即可轻松生成三元输入查询。此外,对于需要强调特定感兴趣结构的情况,本文还提供了基于可见度的参数优化方案,以优化传输函数设计。

    结果 

    经过实验验证,本文提出的两阶段方法在检索各类感兴趣结构时,相较于传统的欧几里得距离基线方法,展现出了显著的优势。在召回率方面,两阶段方法平均提升了0.201,其中在肾脏检索方面的改善尤为明显,提升幅度高达0.304。这一提升充分证明了该方法在医学图像检索领域的有效性和实用性。在消融实验中,两阶段方法的表现同样令人瞩目。无论是对全局性更强的感兴趣结构(如动脉、骨骼和肝脏),还是对局部感兴趣结构(如肝脏、肺和脾),两阶段方法均展现出了优于单一组件(传统卷积神经网络和动态时间规整)的性能。在定性分析方面,两阶段方法在三元输入查询中能够准确识别所有感兴趣结构,这进一步验证了其在实际应用中的可靠性和准确性。与之相比,单一组件方法无法独立完成感兴趣结构的有效检索,这再次证明了组合两阶段方法的有效性。我们还通过一系列用例展示了所提出CBR-TF方法在医学体积可视化中的应用效果。用户可以通过简单的线条画在二维视图中指定感兴趣结构,进而在三维直接体积渲染中突出显示这些结构。这一功能为医学图像的解读和分析提供了极大的便利。在计算性能方面,虽然两阶段方法的计算时间(平均15.93秒)远高于ED基线方法(0.84秒),但考虑到其在检索性能上的显著提升,这一计算成本是可以接受的,这提示在未来的工作中可以进一步优化相关算法设计以提高计算效率。

    结论 

    本论文提出了一种基于内容检索的转移函数生成方法,以提高医学图像的可视化效果。该方法通过引入自动识别感兴趣区域(SOI)的案例推理(CBR)过程,大幅减少了多维传输函数(TF)设计的手动优化。实验结果表明,该方法在识别不同感兴趣区域(SOI)方面具有较高的准确性和召回率。该方法不仅能够自动生成高质量的转移函数,精确识别目标结构,还能通过融合图像语义与强度轮廓匹配,实现高效的可视化。

    Abstract:

    Direct volume rendering (DVR) is a technique that emphasizes structures of interest (SOIs) within a volume visually, while simultaneously depicting adjacent regional information, e.g., the spatial location of a structure concerning its neighbors. In DVR, transfer function (TF) plays a key role by enabling accurate identification of SOIs interactively as well as ensuring appropriate visibility of them. TF generation typically involves non-intuitive trial-and-error optimization of rendering parameters, which is time-consuming and inefficient. Attempts at mitigating this manual process have led to approaches that make use of a knowledge database consisting of pre-designed TFs by domain experts. In these approaches, a user navigates the knowledge database to find the most suitable pre-designed TF for their input volume to visualize the SOIs. Although these approaches potentially reduce the workload to generate the TFs, they, however, require manual TF navigation of the knowledge database, as well as the likely fine tuning of the selected TF to suit the input. In this work, we propose a TF design approach, CBR-TF, where we introduce a new content-based retrieval (CBR) method to automatically navigate the knowledge database. Instead of pre-designed TFs, our knowledge database contains volumes with SOI labels. Given an input volume, our CBR-TF approach retrieves relevant volumes (with SOI labels) from the knowledge database; the retrieved labels are then used to generate and optimize TFs of the input. This approach largely reduces manual TF navigation and fine tuning. For our CBR-TF approach, we introduce a novel volumetric image feature which includes both a local primitive intensity profile along the SOIs and regional spatial semantics available from the co-planar images to the profile. For the regional spatial semantics, we adopt a convolutional neural network to obtain high-level image feature representations. For the intensity profile, we extend the dynamic time warping technique to address subtle alignment differences between similar profiles (SOIs). Finally, we propose a two-stage CBR scheme to enable the use of these two different feature representations in a complementary manner, thereby improving SOI retrieval performance. We demonstrate the capabilities of our CBR-TF approach with comparison with a conventional approach in visualization, where an intensity profile matching algorithm is used, and also with potential use-cases in medical volume visualization.

  • Quantum computing has attracted more and more interest in the last decades, since it provides the possibility to efficiently solve important problems such as integer factorization[1], unstructured search[2], and solving linear equations[3]. However, the (great) improvements in computer science driven by quantum technology are still in the early stage, since large-scale quantum computers have not yet been built. IBM has developed the first 5-qubit backend called IBM QX2, followed by the 16-qubit backend IBM QX3. The revised versions of them are called IBM QX4 and IBM QX5, respectively. Google announced the realization of quantum supremacy, with the 53-qubit quantum processor Sycamore[4]. IBM Q Experience 1 provides the public with free quantum computing resources on the cloud and Qiskit 2, an open source quantum computing software framework.

    Users of early quantum computers mainly rely on quantum circuits to implement quantum algorithms. There is a gap between the design and the implementation of a quantum algorithm[5]. In the design stage, we usually do not consider any hardware connectivity constraints. But in order to implement an algorithm on a quantum physical device, physical constraints have to be taken into account. For example, IBM physical devices only support 1-qubit gates and the 2-qubit CX gate between two adjacent qubits. Hence, it is necessary to transform the circuits for quantum algorithms to satisfy both logical and physical constraints. It is called qubit mapping, which maps a logical circuit to a physical device by inserting additional gates. A major challenge for quantum information processing is quantum decoherence. Quantum gates are applied in a coherent period but the qubits stay in the coherent state for a very short time. The longest coherence time of a superconducting quantum chip is still within 10 μs–100 μs[6]. Thus, the main goal of qubit mapping is to reduce the number of additional gates and the depth of output circuits in an efficient way.

    In the current work, we use In-Memory Subgraph Matching (IMSM)[7] to generate partial isomorphic subgraphs of logical circuits and physical ones as a set of partial initial mappings. By exploiting an appropriate subgraph isomorphism and the connectivity of the logical circuits and the physical ones, we get a dense (clustered nodes) initial mapping, which avoids some nodes from being mapped to remote positions. Note that both subgraph isomorphism and the adjustment of qubit mapping are NP-complete[8]. Thus, to be practically efficient, we propose to use tabu search[9] to generate logical circuits that will be executed on the physical device. The advantage of tabu search is to jump out of local optimum and ensure the diversity of the transformed results. We insert SWAP gates, associated with the gates on the shortest path to the candidate set, which greatly reduces the search space and improves the search speed. We design three evaluation functions that consider not only the current gates but also the constraints of the gates already processed. Our experiments have been conducted by using the architectures of IBM Q Tokyo and Sycamore as the target physical devices. The experimental results show that the evaluation function based on calculating the number of additional gates inserts the smallest number of gates. We test several combinations of state-of-the-art initial mapping and adjustment algorithms aiming to insert fewer additional gates after qubit mapping. Generally speaking, Tabu Search Based Adjustment (TSA) outperforms the Zulehner-Paler-Wille (ZPW) algorithm[10], SWAP-Based BidiREctional heuristic search algorithm (SABRE)[11] and Filtered Depth-Limited Search (FiDLS)[12] in different aspects. When compared with the Dynamic Look-Ahead Heuristic technique (DLH)[13], which uses the maximum consecutive positive effect of an SWAP operation (MCPE) and the optimized version (MCPE_OP) as the heuristic cost function, the additional gates inserted by TSA in the DLH benchmarks have been reduced by 27.32% and 12.42%, respectively.

    The main contributions of this article are summarized as follows.

    1) We extend IMSM, which only generates a set of partial initial mappings, by completing the mapping based on the connectivity between qubits.

    2) We propose a heuristic circuit adjustment algorithm based on tabu search, TSA, which can adjust large-scale circuits much more efficiently than existing precise search and heuristic algorithms.

    3) We propose three look-ahead evaluation functions for the circuit adjustment; one employs configuration checking with aspiration (CCA)[14], and the other two use the number of additional gates and the depth of the generated circuit as evaluation criteria, taking into account both the current gates and some gates yet to be processed.

    4) We compare several state-of-the-art initial mapping and adjustment algorithms, and the results show that the initial mapping generated by our method requires inserting fewer SWAP gates, and TSA has better scalability than them for adjusting the mapping for large-scale circuits.

    The rest of this article is organized as follows. In Section 2, we discuss the related work. In Section 3, we recall some background in quantum computing and quantum information. In Section 4, we introduce the problem of qubit mapping and provide our detailed solution. Section 5 reports the experimental results. We conclude in the last section and discuss future work.

    Paler[15] has shown that initial mappings have an important impact on qubit mapping. Just by placing qubits in different positions from the default trivial placement in the circuit instances on actual noisy intermediate-scale quantum (NISQ) devices, the cost can be reduced by up to 10%. One important goal of circuit adjustment algorithms is to minimize the number of additional gates. There are currently five main methods to attack the qubit mapping problem.

    Unitary Matrix Decomposition Algorithm. It is used to rearrange a quantum circuit from the beginning while retaining the input circuit[16, 17]. It can be applied to a broad class of circuits consisting of generic gate sets, but the results are not so efficient as a compiler designed specifically for this task.

    Converting into Existing Problems. This approach converts the qubit mapping problem into some existing problems, such as AI planning[18, 19], integer linear programming[20], and satisfiability modulo theories (SMT)[21], and then uses existing tools to find the optimum in an acceptable amount of time for the problem. Furthermore, as the time cost is usually high, it can only process small-scale quantum circuits.

    Exact Methods. Siraichi et al. proposed an exact method[8]. It iterates over all possible mappings; thus it is only suitable for simple quantum circuits and cannot be extended to complex ones.

    Graph Theory. Shafaei et al. used the minimum linear permutation solution in graph theory to model the problem of reducing the interaction distance[22]. A two-step method was used to reduce the qubit mapping to a graph problem to minimize the number of additional gates[23, 24].

    Heuristic Search. Existing solutions mainly aim at inserting as few SWAP gates as possible[8, 10-13, 25, 26], using the fidelity of the generated circuit as the objective function[27] or minimizing the overall circuit latency[28]. At present, there are a number of methods[10, 11, 13, 22] that exploit the look-ahead idea. In particular, Zhu et al. proposed to dynamically adjust the number of look-ahead gates[13]. SABRE[11] depends on a random initial mapping. SAHS[26] is an annealing algorithm to find an initial mapping, but it is unstable. FiDLS[12] tends to search through all possible combinations of SWAP gates to minimize the number of executable 2-qubit gates. But the cost of a thorough search is very high, especially when dealing with medium-scale and large-scale circuits. DLH[13] can deal with some large-scale benchmarks. We will give a quantitative comparison with this method in Section 5. A variation-aware qubit movement strategy[27] was proposed, which takes advantage of the change in error rate and a change-aware qubit mapping strategy by trying to select the route with the lowest probability of failure. Lao et al. showed that the fidelity of a circuit is related to the delay and the number of gates[28]. Now some heuristic methods are also applied to other platforms such as Surface-17[28, 29] and Sycamore[12].

    In this section, we introduce some notions and notations of quantum computing. Let C denote the set of all complex numbers.

    Classical information is stored in bits, while quantum information is stored in qubits. Besides two basic states |0 and |1, a qubit can be in any linear superposition state like |ϕ=a|0+b|1, where a,bC satisfy the condition |a|2+|b|2=1. The intuition is that |ϕ is in the state |0 with probability |a|2 and in the state |1 with probability |b|2. We use the letter Q (resp. q) to denote a physical (resp. logical) qubit.

    A quantum gate acts on a qubit to change the state of the qubit. For example, the Hadamard (H) gate is applied on a qubit, and the CX gate is applied on two qubits. Their symbols and matrix forms are shown in Fig.1. The H gate turns state |0 (resp. |1) into (|0+|1)/2 (resp. (|0|1)/2). The CX gate is a generalization of the classical XOR gate, since the action of the gate may be summarized as \left| {{\boldsymbol{A}},{\boldsymbol{B}}} \right\rangle \rightarrow |{\boldsymbol{A}}, {\boldsymbol{B}} \oplus {\boldsymbol{A}}\rangle , where \oplus is addition modulo two, which is exactly what the XOR gate does. That is, the control qubit and the target qubit are XORed and stored in the target qubit. Here \left| {{\boldsymbol{A}},{\boldsymbol{B}}} \right\rangle is a shorthand of the product state \left| {\boldsymbol{A}} \right\rangle \left| {\boldsymbol{B}} \right\rangle =\left| {\boldsymbol{A}} \right\rangle \otimes \left| {\boldsymbol{B}} \right\rangle . We use an SWAP gate to exchange the states between two adjacent qubits, and multiple operations simulate moving non-adjacent qubits to adjacent positions. An SWAP gate can be implemented by three CX gates, or by inserting four H gates to change the direction of the middle CX gate, as illustrated in Fig.2.

    Figure  1.  Symbols of two quantum gates and their matrices.
    Figure  2.  Implementing an SWAP gate by CX gates and H gates.

    In a quantum circuit, each line represents a wire. The wire does not necessarily correspond to a physical wire but may correspond to the passage of time or a physical particle that moves from one location to another through space. The interested reader can find more details of these gates from the standard textbook[30]. The execution order of a quantum logical circuit is from left to right. The width of a circuit refers to the number of qubits in the circuit. The depth of a circuit refers to the number of layers executable in parallel. For example, the depth of the circuit in Fig.3(a) is 6, and the width is 5. We refer to a circuit with the number of 2-qubit gates no more than 100 as a small-scale circuit, a circuit with the number of 2-qubit gates more than 1000 as a large-scale circuit, and the rest are medium-scale circuits. It is unnecessary to consider quantum gates acting on single qubits since 1-qubit gates are local[22], which do not need to move the involved qubits for gate applications.

    Figure  3.  (a) Original quantum circuit. (b) Logical interaction graph of (a).

    In the current work, we mainly consider the physical circuits of the IBM Q series, called coupling graphs. Let {\cal{CG}}=(V_{{\cal{C}}}, E_{{\cal{C}}}) denote the coupling graph of a physical device, where V_{{\cal{C}}} is the set of physical qubits and E_{{\cal{C}}} is the set of edges representing the connectivity between qubits related by CX gates. Figs.4(a)–4(e) are the coupling graphs of the 5-qubit IBM QX2, IBM QX4, 16-qubit IBM QX3, IBM QX5, and the 20-qubit IBM Q Tokyo, respectively. The control of one qubit to a neighbor is unilateral, but for IBM Q Tokyo the control between two adjacent qubits is bilateral. The direction in each edge indicates the control direction of each 2-qubit gate, and 2-qubit gates can only be performed between two adjacent qubits.

    Figure  4.  Coupling graphs of IBM Q series. (a) IBM QX2. (b) IBM QX4. (c) IBM QX3. (d) IBM QX5. (e) IBM Q Tokyo.

    Given an interaction graph {\cal{IG}} , a coupling graph {\cal{CG}} , an initial mapping \tau , and a CX gate {\boldsymbol{g}}= \langle q_{{\rm{c}}},q_{{\rm{t}}} \rangle where q_{{\rm{c}}} is the control qubit and q_{{\rm{t}}} is the target qubit, if the gate {\boldsymbol{g}} is executable on coupling graph {\cal{CG}} , then \langle\tau[q_{{\rm{c}}}],\tau[q_{{\rm{t}}}] \rangle should be a directed edge on {\cal{CG}} .

    Example 1. Consider the logical interaction graph {\cal{IG}} and a coupling graph {\cal{CG}} shown in Fig.3(b) and the blue part of Fig.4(e). Let the initial mapping be as follows,

    \tau=\{q_{0}\rightarrow Q_{10}, q_{1}\rightarrow Q_{0}, q_{2}\rightarrow Q_{6},q_{3}\rightarrow Q_{5}, q_{4}\rightarrow Q_{11}\} .

    Then the 2-qubit gate {\boldsymbol{g}}_{0}=\langle q_{2},q_{1}\rangle is not executable, since the edge \langle \tau[q_{2}],\tau[q_{1}] \rangle = \langle Q_{6},Q_{0} \rangle does not exist in {\cal{CG}} . However, the gate {\boldsymbol{g}}_{1}=\langle q_{3},q_{4} \rangle is executable, since the edge \langle \tau[q_{3}],\tau[q_{4}] \rangle = \langle Q_{5},Q_{11} \rangle exists in {\cal{CG}} .

    Assume that the input circuit has only 1-qubit gates and CX gates[31, 32]. We expect to find a qubit mapping algorithm that, when given an input circuit, can produce an output circuit with a small number of additional gates in an acceptable amount of time. Roughly speaking, we propose a method of qubit mapping with the following three steps.

    1) Preprocessing. This step includes extracting the interaction graph from the input circuit and calculating the shortest paths of the coupling graph.

    2) Isomorphism and Completion. First, the subgraph isomorphism algorithm is used to find a set of partial initial mappings[7]. Then we perform a mapping completion to process the remaining nodes that do not satisfy all isomorphism requirements, according to the connectivity between the unmapped nodes and the mapped ones.

    3) Adjustment. After the second step, some logically adjacent nodes may be mapped to physically non-adjacent nodes, therefore, the quantum circuit is not executable on the coupling graph. We use a tabu search based adjustment algorithm to generate circuits that can be physically executed.

    In the preprocessing step, we adjust the input circuit described by an openQASM program[33] to extract the interaction graph from the input circuit and calculate the shortest paths of the coupling graph.

    Quantum gates acting on different qubits can be executed in parallel. The notation {\cal{L}}({\cal{C}})=\{{\cal{L}}_{0}, {\cal{L}}_{1}, \ldots, {\cal{L}}_{n}\} denotes the layered form of circuit {\cal{C}} , where {\cal{L}}_{i} \ (0 \leqslant i \leqslant n) stands for a set of quantum gates that can be executed in parallel. The quantum gate sets separated by the dotted lines in Fig.3(a) are the following: {\cal{L}}_{0}=\{{\boldsymbol{g}}_{0},{\boldsymbol{g}}_{1}\},{\cal{L}}_{1}=\{{\boldsymbol{g}}_{2}\}, {\cal{L}}_{2}=\{{\boldsymbol{g}}_{3},{\boldsymbol{g}}_{4}\}, {\cal{L}}_{3}=\{{\boldsymbol{g}}_{5},{\boldsymbol{g}}_{6}\},{\cal{L}}_{4}=\{{\boldsymbol{g}}_{7}\},{\cal{L}}_{5}=\{{\boldsymbol{g}}_{8}\} .

    At the same time of layering, we generate an interaction graph {\cal{IG}}=(V_{ {\cal{I}}}, E_{{\cal{I}}}) , which is an undirected graph with V_{{\cal{I}}} being the set of vertices, and E_{{\cal{I}}} the set of undirected edges that denotes the connectivity between qubits related by CX gates. Given a coupling graph and assuming that the distance of each edge is 1, we use the Floyd-Warshall algorithm[34] to calculate the shortest distance matrix, with {{D}}[Q_{{\rm{c}}}][Q_{{\rm{t}}}] denoting the shortest distance from Q_{{\rm{c}}} to Q_{{\rm{t}}} .

    Consider a CX gate {\boldsymbol{g}}= \langle q_{{\rm{c}}},q_{{\rm{t}}} \rangle . If q_{{\rm{c}}} and q_{{\rm{t}}} are mapped to Q_{{\rm{c}}} and Q_{{\rm{t}}} , respectively, then the cost of executing {\boldsymbol{g}} under the shortest path is denoted by cost_{\boldsymbol{g}}=7 \times({{D}}[Q_{{\rm{c}}}][Q_{{\rm{t}}}]-1) on devices with unilateral control. For IBM Q Tokyo, the cost is cost_{\boldsymbol{g}}=3 \times({{D}}[Q_{{\rm{c}}}][Q_{{\rm{t}}}]-1) .

    Example 2. Consider the QX5 coupling graph (cf. Fig.4(d)). Given a CX gate {\boldsymbol{g}} = \langle q_{1}, q_{2} \rangle , with q_{1} mapped to Q_{6} and q_{2} mapped to Q_{13} , the shortest distance between them is {{D}}[Q_6][Q_{13}]=3 . There are three shortest paths of moving from Q_{6} to an adjacent position of Q_{13} : \pi_{0}={Q_{6}\rightarrow Q_{5} \rightarrow Q_{4} \rightarrow Q_{13}}, \pi_{1}={Q_{6}\rightarrow Q_{5} \rightarrow Q_{12} \rightarrow Q_{13}}, \pi_{2}=Q_{6}\rightarrow Q_{11} \rightarrow Q_{12} \rightarrow Q_{13}. Their costs are given by cost_{\pi_{0}}=18,\ cost_{\pi_{1}}=14, and cost_{\pi_{2}}=14, respectively. Here cost_{\pi_i} for 0\leqslant i\leqslant 2 stands for the cost of swapping the qubits Q_{6} to Q_{13} along the path \pi_i .

    Generally speaking, in a coupling graph, it is almost impossible to find a subgraph that exactly matches the interaction graph. We regard the mapping with the largest number of mapped nodes as a good partial mapping. IMSM compares various compositions of several state-of-the-art subgraph isomorphism algorithms. Since IMSM cannot process disconnected graphs, we manually create connected graphs by linking isolated nodes to the ones with the largest degree in the interaction graph. Note that this does not change the architecture of the original circuit.

    The input of Algorithm 1 is a coupling graph {\cal{CG}} , an interaction graph {\cal{IG}} , and a partial mappings set T . Line 2 selects the largest number l of mapped nodes, and the partial mappings with l mapped nodes are used by the candidate set. Lines 3–22 complete the partial mappings. The function len(\tau) returns the size of \tau . In line 5, we initialize an empty queue V , which stores unmapped logical qubits, traverse the mapping \tau , and add the unmapped qubits to V . We then loop until V is empty, and all logical qubits are mapped to physical qubits. Line 7 takes out the first element in V to q . Line 8 gets the adjacency matrix of {\cal{CG}} . Line 9 initializes a list U , sorted by descending degree of connectivity to q . Lines 10–20 traverse U and select the node U[0] that has been mapped to the physical node Q in the coupling graph and has the largest number of logical connections to q in U . Line 13 deletes the node U[0] from U . Lines 15–17 select the node k adjacent to Q in the adjacency matrix and map q to that node. Finally, we generate a dense mapping.

    Algorithm 1. Complete the Initial Mapping
    Input: {\cal{CG}} : a coupling graph; {\cal{IG}} : an interaction graph; T : a partial mapping set obtained by IMSM;
    Output: results : a set of mapping relations between {\cal{IG}} and {\cal{CG}};
    1 Initialize results=\emptyset ;
    2 l \leftarrow \max_{\tau \in T}|\{i: \tau[i]\ne -1,\; i \leqslant len(\tau), \; i\in \mathbb{N} \}|
    3 for \tau\in T do
    4 if l=len(\tau) then
    5 V\leftarrow the unmapped logical qubits in \tau ;
    6 while len(V) >0 do
    7 q \leftarrow V. poll();
    8 {\boldsymbol{P}} \leftarrow {\cal{CG}}.adjacencyMatrix() ;
    9 U \leftarrow the neighbors of q in {\cal{IG}} ;
    10 while len(U)>0 do
    11 Q \leftarrow \tau[U[0]] ;
    12 k \leftarrow 0 ;
    13 U \leftarrow U\backslash U[0] ;
    14 while k < len({\boldsymbol{P}}[Q]) do
    15 if ({\boldsymbol{P}}[Q][k] {\rm{or}} {\boldsymbol{P}}[k][Q]\neq 0 {\rm{and\; not}} \tau. contains(k)) then
    16 \tau[q] \leftarrow k ;
    17 break;
    18 k \leftarrow k+1 ;
    19 if k\neq len({\boldsymbol{P}}[Q]) then
    20 break;
    21 results. add (\tau) ;
    22 {\bf{return}} results ;

    Example 3. Consider the interaction graph shown in Fig.3(a) and the coupling graph in Fig.4(e). Suppose we have a partial mapping set T=\{\tau_{0}, \tau_{1}, \ldots, \tau_{n}\} . We take one of the partial mappings as an example.

    \tau_{0}=\{q_{0}\rightarrow Q_{10}, q_{1}\rightarrow -1, q_{2}\rightarrow Q_{6}, q_{3}\rightarrow Q_{5}, q_{4}\rightarrow Q_{11}\},

    where q_{1}\rightarrow -1 means that q_{1} is not mapped to any physical qubit, therefore we need the mapping completion algorithm. The maximum number of mapped nodes is 4. We demonstrate how \tau_{0} is completed. We add all unmapped nodes to the queue V ; in this example, we have V=\{q_{1}\} . Then we loop until V is empty. We pop the first element q_1 of V , get the adjacency matrix of the target graph, and the candidate nodes list U=\{q_{3},q_{2},q_{4},q_{0}\} . Next, we traverse U and take out the first element q_{3} in U , and calculate the physical node Q_{5} as \tau_0[q_{3}]=Q_{5} . Finally, we map q_1 to the node connected to q_3 but not yet mapped. In this example, it can be directly mapped to Q_{0} . In the end, we obtain the mapping \tau_{0}=\{q_{0}\rightarrow Q_{10}, q_{1}\rightarrow Q_{0}, q_{2}\rightarrow Q_{6}, q_{3}\rightarrow Q_{5},q_{4}\rightarrow Q_{11}\}.

    Tabu search uses a tabu list to avoid searching repeated spaces and deadlock and amnesty rules to jump out of the local optimum to ensure the diversity of transformed results. Our circuit adjustment mainly relies on the tabu search algorithm, aiming to adjust those large-scale circuits that the existing algorithms are difficult to process and generate a circuit closer to the optimal solution.

    The calculation of the candidate set is shown in Algorithm 2. The input M_{{\rm{p}}} is a mapping from physical qubits to logical ones, where j = M_{{\rm{p}}}[i] means that the i -th physical qubit is mapped to the j -th logical qubit. The set M_{{\rm{l}}} denotes the mapping of logical qubits to physical ones, where j = M_{{\rm{l}}} [i] means that the i -th logical qubit is mapped to the j -th physical qubit. The set {\cal{L}} includes all the gates in the current layer, and the output is a candidate mapping set of the current mapping. The set E and the matrix {\boldsymbol{D}} contain the shortest paths and distances of all nodes in the coupled graph, respectively. Lines 3–7 delete the gate {\boldsymbol{g}} that can be executed in {\cal{L}} under the current mapping and gather the control qubit q_{{\rm{c}}} and target qubit q_{{\rm{t}}} of gate {\boldsymbol{g}} that cannot be executed into the set B . Lines 8–24 traverse gates {\boldsymbol{g}} in {\cal{L}} , and calculate the shortest paths between the nodes of {\boldsymbol{g}} . If the endpoints e.s and e.t of edge e intersect with B on the shortest path, then e is an element of the candidate set. Lines 14–20 update the mapping after the swap. Lines 21–24 generate a new candidate solution. Line 22 stores the swapped edges that will be used in the output circuit, and line 23 calculates the swap scores using an evaluation function.

    Algorithm 2. Calculate the Candidate Set
    Input: M_{{\rm{p}}} : the mapping from physical qubits to logical qubits; M_{{\rm{l}}} : the mapping from logical qubits to physical qubits; {\cal{L}} : gates included in the current layer of circuits; E : the shortest paths set of the coupling graph; {\boldsymbol{D}} : the distance matrix between nodes in the coupling graph;
    Output: results : the set of candidate mapping;
    1 Initialize results \leftarrow \emptyset ; B\gets \emptyset;
    2 for {\boldsymbol{g}} \in {\cal{L}} do
    3 if {\boldsymbol{g}} \; {\rm{is \;executable}} then
    4 {\cal{L}} \leftarrow {\cal{L}} \backslash \{{\boldsymbol{g}}\} ;
    5 else
    6 q_{{\rm{c}}}, q_{{\rm{t}}}\gets \; {\rm{the \;operating\; qubits\; of\; gate}}\; {\boldsymbol{g}} ;
    7 B\gets B\cup \{q_{{\rm{c}}}, q_{{\rm{t}}}\};
    8 for {\boldsymbol{g}}\in {\cal{L}} do
    9 q_{{\rm{c}}}, q_{{\rm{t}}}\gets {\rm{the\; operating\; qubits\; of\; gate}}\; {\boldsymbol{g}} ;
    10 for p \in E[M_{{\rm{l}}}[q_{{\rm{c}}}]][M_{{\rm{l}}}[q_{{\rm{t}}}]] do
    11 for e \in p do
    12 if e.s {\rm{and}} e.t \notin B then
    13 continue;
    14 M_{{\rm{p}}}^{\prime} \leftarrow M_{{\rm{p}}} ; M_{{\rm{l}}}^{\prime} \leftarrow M_{{\rm{l}}} ;
    15 Q_{1} \leftarrow M_{{\rm{p}}}^{\prime}[e.s] ; Q_{2} \leftarrow M_{{\rm{p}}}^{\prime}[e.t] ;
    16 M_{{\rm{p}}}^{\prime}[e.s] \leftarrow Q_{2} ; M_{{\rm{p}}}^{\prime}[e.t] \leftarrow Q_{1} ;
    17 if Q_{1}\neq -1 then
    18 M_{{\rm{l}}}^{\prime}[Q_{1}] \leftarrow Q_{2} ;
    19 if Q_{2}\neq-1 then
    20 M_{{\rm{l}}}^{\prime}[Q_{2}] \leftarrow Q_{1} ;
    21 s \leftarrow \emptyset ;
    22 s.swaps \leftarrow s.swaps \cup \{e\};
    23 s.value \leftarrow evaluate({\boldsymbol{D}},M_{{\rm{l}}}^{\prime},{\cal{L}}) ;
    24 results \leftarrow results \cup \{s\} ;
    25 {\bf{return}} results ;

    Example 4. Let us consider the mapping

    \tau_{0}= \{q_{0} \rightarrow Q_{10}, q_{1}\rightarrow Q_{0}, q_{2}\rightarrow Q_{6}, q_{3}\rightarrow Q_{5}, q_{4}\rightarrow Q_{11}\}.

    with {\cal{L}}_{0}=\{{\boldsymbol{g}}_{0},{\boldsymbol{g}}_{1}\} , cost_{{\boldsymbol{g}}_{1}}=0 , and cost_{{\boldsymbol{g}}_{0}}=3 . The gate {\boldsymbol{g}}_{1} can be executed directly in the \tau_{0} mapping, therefore we delete it from {\cal{L}}_{0} , but {\boldsymbol{g}}_{0} cannot be executed in the mapping \tau_{0} . The nodes that cannot be executed join the set B=\{q_{2}, q_{1}\} . The set of shortest paths is

    \{\{Q_{6}\rightarrow Q_{1} \rightarrow Q_{0} \}, \{Q_{6}\rightarrow Q_{5} \rightarrow Q_{0} \}\}.

    We traverse the shortest paths and calculate the candidate set. The current candidate set is \{(Q_{6},Q_{1}), (Q_{1},Q_{0}), (Q_{6},Q_{5}), (Q_{5},Q_{0}) \} .

    TSA takes a layered circuit and an initial mapping as input and outputs a circuit that can be executed in the specified coupling graph, as shown in Algorithm 3. The adjusted circuit mapping of each layer is used as the initial mapping of the next layer. Line 1 regards the initial mapping \tau_{{\rm{ini}}} as the best mapping \tau_{{\rm{best}}} . Lines 3–12 cyclically check whether all the gates in the current layer can be executed under the mapping \tau_{{\rm{best}}} . If all the gates are executable or the number of iterations reaches the given bound, the search is completed. Otherwise, the search continues. Line 4 gets the current mapping candidate, and line 7 finds the best mapping in the candidate set. Note that if the edge swapped by a candidate appears in the tabu list, the candidate will be removed from the candidate set. Then from the remaining candidates, we choose a mapping with the lowest cost. Line 9 takes the amnesty rules. If the best candidate is not found, the amnesty rules will select the mapping with the lowest cost in the candidate set as the best mapping. Lines 10–12 update the best mapping \tau_{{\rm{best}}} and insert the swapped edge performed by the best mapping to the tabu list tb . The motivation is to execute the generated circuit in parallel as much as possible and to avoid swapping the edges in the tabu list. Then it will check whether the termination condition of the algorithm is satisfied. The condition determines whether the number of iterations reaches the given bound, or the current mapping ensures all the gates in the current layer can be executed.

    Algorithm 3. Tabu Search
    Input: \tau_{{\rm{ini}}} : the initial mapping; tb : the tabu list;
    Output: \tau_{{\rm{best}}} : the best mapping;
    1 Initialize \tau_{{\rm{best}}} \leftarrow \tau_{{\rm{ini}}} ;
    2 it \leftarrow 1 ; /*the number of iterations*/
    3 while {\rm{not}} \ mustStop(it, \tau_{{\rm{best}}}) do
    4 C \leftarrow \tau_{{\rm{best}}}.candidates() /*candidate set*/
    5 if C {\rm{is\; empty}} then
    6 {\bf{break}} ;
    7 c_{{\rm{best}}} \leftarrow best\_candidates(C, tb) ;
    8 if c_{{\rm{best}}} {\rm{is\; empty}} then
    9 c_{{\rm{best}}} \leftarrow amnesty\_candidates(C, tb) ;
    10 \tau_{{\rm{best}}} \leftarrow c_{{\rm{best}}} ;
    11 tb \gets tb. add (c_{{\rm{best}}}.swaps) ;
    12 n \leftarrow n+1 ;
    13 {\bf{return}} \tau_{{\rm{best}}};

    We propose three evaluation functions: one introduces CCA; one uses the number of additional gates in the generated circuit as an evaluation criterion as given in (1); and the last one uses the depth of the generated circuit as an evaluation criterion as given in (2). They give rise to three variants of TSA called TSAcca, TSAnum, and TSAdep, respectively.

    CCA has mainly been used for Boolean Satisfiability (SAT) problems. We apply the idea of CCA to adjust circuits. Let submake represent the number of qubits for which two qubits are closer after an SWAP gate, and subbreak represent the number of qubits for which two qubits are farther apart after an SWAP gate. We introduce subscore= submake\ \, - subbreak into the evaluation function and adjust the weight with the Smooth Weight based Threshold (SWT) scheme[14].

    The output of the i -th layer, with i smaller than the depth of the circuit d , is used as the input of the (i+1) -th layer. Note that any SWAP gate in the i -th layer will affect the mapping of the (i+1) -th layer. If we only consider the gate of the current layer when selecting the SWAP gate, only the requirements of the i layer will be satisfied, not necessarily those of the next layer. Therefore, we take the gates from the i -th to the (i+l_{{\rm{a}}}) -th layer, with i+l_{{\rm{a}}} \leqslant d , into consideration, where l_{{\rm{a}}} is the number of look-ahead layers. It is necessary to give a higher priority to executing the gates in the i -th layer, therefore we introduce an attenuation factor \delta to control the influence of the gates in the look-ahead layers.

    \begin{split}& cost_{{\rm{num}}}(Q_{{\rm{c}}},Q_{{\rm{t}}}) =\sum\limits_{{\boldsymbol{g}} \in {\cal{L}}_{i}}3\times({{D}}[\tau[q_{{\rm{c}}}]][\tau[q_{{\rm{t}}}]]-1) + \\ &\qquad\delta \times \left(\sum\limits_{j=i}^{i+l_{{\rm{a}}}}\sum\limits_{{\boldsymbol{g}} \in {\cal{L}}_{j}}3\times({{D}}[\tau[q_{{\rm{c}}}]][\tau[q_{{\rm{t}}}]]-1)\right), \end{split} (1)
    cost_{{\rm{dep}}}(Q_{{\rm{c}}},Q_{{\rm{t}}}) = Depth\left(\bigcup\limits_{j=i}^{i+l_{{\rm{a}}}}{\cal{L}}_{j}\right). (2)

    Here cost_{{\rm{num}}}(Q_{{\rm{c}}}, Q_{{\rm{t}}}) (resp. cost_{{\rm{dep}}}(Q_{{\rm{c}}}, Q_{{\rm{t}}}) ) denotes the distance (resp. depth) of all the gates in layer {\cal{L}}_j ( i\leqslant j \leqslant i+l_{{\rm{a}}} ), after swapping the state of Q_{{\rm{c}}} with that of Q_{{\rm{t}}} . The function Depth({\cal{L}}) returns the depth of {\cal{L}} and the notation q_{{\rm{c}}} (resp. q_{{\rm{t}}} ) stands for the control (resp. target) qubit of gate {\boldsymbol{g}} .

    Example 5. Let us continue the previous example. We select the one with the lowest evaluation score from the candidate set. Assuming \delta=0.5 and l_{{\rm{a}}}=2 , for {\cal{L}}_{1}=\{{\boldsymbol{g}}_{2},{\boldsymbol{g}}_{0}\} , the candidate set is \{(Q_{6},Q_{1}), (Q_{1},Q_{0}), (Q_{6},Q_{5}), (Q_{5},Q_{0}) \}, and the costs are given as follows:

    \begin{aligned} & cost_{{\rm{num}}}(Q_{6},Q_{1})=0 , \quad\;\;\; cost_{{\rm{num}}}(Q_{1},Q_{0})=1.5 , \\ & cost_{{\rm{num}}}(Q_{6},Q_{5})=1.5, \quad cost_{{\rm{num}}}(Q_{5},Q_{0})=1.5 {\text{.}}\end{aligned}

    The algorithm chooses the first SWAP with the smallest score, and the mapping becomes \tau_{0}=\{q_{0} \rightarrow Q_{10}, q_{1}\rightarrow Q_{0}, q_{2}\rightarrow Q_{1},q_{3}\rightarrow Q_{5},q_{4}\rightarrow Q_{11}\} .

    The current mapping ensures that {\boldsymbol{g}}_{0} is executable. Thus we can continue to the next layer.

    Given an interaction graph {\cal{IG}}=(V_{{\cal{I}}},E_{{\cal{I}}}) and a coupling graph {\cal{CG}}=(V_{{\cal{C}}},E_{{\cal{C}}}) , we assume that the depth of the circuit is d and there are G 2-qubit gates in one layer. The candidate set consists of the edges connected to the control or target qubits, thus the size of the SWAP candidate set is 8\times G . The worst-case time complexity is O(d\times G\times(8\times G)^{(|E_{{\cal{C}}}|-1)}) , and the space complexity is O(G) .

    We compare TSA with several state-of-the-art algorithms for qubit mapping, namely ZPW[10], SABRE[11], FiDLS[12], and DLH[13]. Notice that other algorithms such as SAHS[26] and {\rm{t}} \mid {\rm{ket}}\rangle[25] are not listed because Li et al.[12] have pointed out that FiDLS is superior to SAHS and the latter outperforms {\rm{t}} \mid {\rm{ket}}\rangle[26]. The implementation in Python is available online 3. All the experiments are conducted on a Ubuntu machine with a 2.2 GHz CPU and 64 GB memory. We take the logarithm \log_{10} of both the x -axis and y -axis such that the experimental results are easy to observe. The time limit for each benchmark is one hour. Among the 159 benchmarks, we have considered, 158 of them are taken from some functions of RevLib[35], and one is added by our own. This dataset has also been adopted in several related work. We believe that it is representative and our comparative experiments are carried out on it. With the 159 benchmarks, we compare TSA with ZPW, SABRE, and FiDLS on IBM Q Tokyo, and with FiDLS on Sycamore. Since the code of DLH is not available online, we only make comparison with this algorithm on the number of inserted additional gates but not the running time. Note that SABRE uses a random initial mapping, thus for every benchmark we execute it five times, each with a different initial mapping, and report the best result out of the five trials. TSA uses unsorted candidates, and thus we execute it five times and take the best result. Other algorithms are deterministic, therefore they only run once. Fig.5 illustrates the entire process of our experiments. Below we go through it in more detail.

    Figure  5.  Sketch of the experiments.

    Firstly, we test TSA with fixed and variable look-ahead parameter l_{{\rm{a}}} . In Fig.6, different colors represent the logarithms of the number of additional gates. The lower the points in the figure, the fewer additional gates inserted. As for the look-ahead parameter l_{{\rm{a}}} , the optimal parameter for each circuit may be different. We have done thousands of experiments and found that when l_{{\rm{a}}}=2 , the number of additional gates is relatively small for all benchmarks. It means that a 2-layer look-ahead already gives a good performance for TSA.

    Figure  6.  Impact of the look-ahead parameter l_{{\rm{a}}} on search results.

    In Fig.7, we compare {\rm{TSA}}_{{\rm{cca}}} , {\rm{TSA}}_{{\rm{dep}}} and {\rm{TSA}}_{{\rm{num}}} using the 159 benchmarks mentioned above. Compared with {\rm{TSA}}_{{\rm{cca}}} (resp. {\rm{TSA}}_{{\rm{num}}} ), the depth of the generated circuits by {\rm{TSA}}_{{\rm{dep}}} is reduced by 2.37% (resp. 3.42%) on average. Compared with {\rm{TSA}}_{{\rm{cca}}} (resp. {\rm{TSA}}_{{\rm{dep}}} ), the number of additional gates by {\rm{TSA}}_{{\rm{num}}} is reduced by 2.69% (resp. 9.56%) on average. Therefore, it is preferable to use either {\rm{TSA}}_{{\rm{dep}}} or {\rm{TSA}}_{{\rm{num}}} , depending on the optimization objective to be either the depth or the number of additional gates of the resulting circuits.

    Figure  7.  Comparison of the number of additional gates inserted by {\rm{TSA}}_{{\rm{dep}}}, {\rm{TSA}}_{{\rm{cca}}}, and {\rm{TSA}}_{{\rm{num}}}.

    Secondly, we use the benchmarks[13] to compare {\rm{TSA}}_{{\rm{num}}} with DLH. Note that two heuristic cost functions MCPE and MCPE_OP are used in DLH. Since there is no code available online for DLH, we only compare the number of additional gates inserted with the circuits[13], as shown in Table 1. Compared with MCPE and MCPE_OP, {\rm{TSA}}_{{\rm{num}}} reduces the total number of additional gates by 27.32% and 12.42%, respectively.

    Table  1.  Comparison of MCPE, MCPE_OP and {\rm{TSA}}_{{\rm{num}}}
    Benchmark n G G_0 (MCPE) G_1 (MCPE_OP) G_2 ({\rm{TSA}}_{{\rm{num}}} ) \Delta_0(\%) \Delta_1 (\%)
    4mod5-v1_22 5 21 0 0 0 0.00 0.00
    mod5mils_65 5 35 0 0 0 0.00 0.00
    alu-v0_27 5 36 3 3 6 –100.00 –100.00
    decod24-v2_43 4 52 0 0 0 0.00 0.00
    4gt13_92 5 66 21 21 0 100.00 100.00
    ising_model_10 16 786 0 0 0 0.00 0.00
    ising_model_13 16 786 0 0 0 0.00 0.00
    ising_model_16 16 786 0 0 0 0.00 0.00
    qft_10 10 200 39 39 57 –46.15 –46.15
    qft_16 16 512 225 192 189 16.00 1.56
    rd84_142 15 343 153 108 99 35.29 8.33
    adr4_197 13 3439 1566 1224 1029 34.29 15.93
    radd_250 13 3213 1353 1047 852 37.03 18.62
    z4_268 11 3073 1071 855 915 14.57 –7.02
    sym6_145 14 3888 1017 1017 681 33.04 33.04
    misex1_241 15 4813 2118 1098 1032 51.27 6.01
    rd73_252 10 5321 2352 2193 1629 30.74 25.72
    cycle10_2_110 12 6050 2226 1968 1890 15.09 3.96
    square_root_7 15 7630 2061 1788 1509 26.78 15.60
    sqn_258 10 4459 3708 3057 3093 16.59 –1.18
    rd84_253 12 13658 6411 5697 4605 28.17 19.17
    co14_215 15 17936 5634 5062 6813 –20.93 –34.59
    sym9_193 10 34881 15420 13746 12315 20.14 10.41
    urf5_158 9 164416 69852 58947 56253 19.47 4.57
    hwb9_119 10 207775 93219 89355 78753 15.52 11.87
    urf4_187 11 512064 220329 168366 141768 35.66 15.80
    Sum 1307223 428778 355782 311598 27.32 12.42
    Note: n is the number of qubits, G is the number of gates in the input circuit, G_0G_2 are the numbers of additional gates inserted by MCPE, MCPE_OP and TSAnum, respectively, and \Delta_i=(G_i-G_2)/G_i.
    下载: 导出CSV 
    | 显示表格

    Thirdly, we compare the combinations of several algorithms for inserting fewer additional gates. In order to visualize the differences between ZPW, FiDLS, SABRE, and TSA, we have plotted a series of figures available online as supplementary materials 4. We use the initial mapping and adjustment algorithms from ZPW[10], SABRE[11], FiDLS[12], and TSA.

    In Table 2, we compare the performance of the four initial mapping algorithms of ZPW, SABRE, FiDLS, and TSA under the specific adjustment algorithms. For example, in the first row, the adjustment algorithm is fixed to be that of ZPW; there are 115 circuits that all of the four initial mapping algorithms can successfully transform and we compare the number of additional gates. As we can see, the initial mapping algorithm of TSA performs the best when used in conjunction with the five adjustment algorithms. It leads to a reduction of 41%, 30%, and 37% of additional gates compared with the initial mapping algorithms of ZPW, SABRE, and FiDLS.

    Table  2.  Comparison of the Initial Mapping Algorithms of ZPW, SABRE, FiDLS, and TSA
    Algorithm N G G_0 G_1 G_2 G_3 \Delta_0 (\%) \Delta_1 (\%) \Delta_2 (\%)
    ZPW 115 63666 29640 24951 27651 17412 41.26 30.22 37.03
    SABRE 108 77790 28671 26079 26412 16068 43.96 38.39 39.16
    FiDLS 120 209433 29484 28434 30195 25950 11.99 8.74 14.06
    {\rm{TSA}}_{{\rm{num}}} 120 163485 54969 52512 62817 45948 12.50 26.85 18.59
    {\rm{TSA}}_{{\rm{cca}}} 120 163485 57777 53922 61668 46305 19.86 14.13 24.91
    Note: N is the number of circuits that all the four initial mapping algorithms can successfully transform, G is the number of gates in the input circuits, G_0G_3 are the numbers of additional gates inserted by ZPW, SABRE, FiDLS, and TSA, respectively, and \Delta_i=(G_i-G_3)/G_i.
    下载: 导出CSV 
    | 显示表格

    We then compare the five adjustment algorithms from ZPW, SABRE, FiDLS, {\rm{TSA}}_{{\rm{num}}} , and {\rm{TSA}}_{{\rm{cca}}} under specific initial mapping algorithms in Table 3. FiDLS gives rise to the fewest additional gates. For example, in the second row, SABRE is used as the adjustment algorithm, 16632 (resp. 12072) gates are inserted under the initial mapping of SABRE (resp. TSA). The SABRE adjustment algorithm combined with the initial mapping provided by TSA has fewer gates inserted than the SABRE initial mapping algorithm in these benchmarks. This shows that the initial mapping of TSA is better than that of SABRE. FiDLS uses a deep search on the circuits, calculates the full permutation of all edges, and then selects the best among all the permutations according to an evaluation function. FiDLS takes large-scale search space and long search time for large-scale circuits. Overall, TSA performs well on large-scale circuits, trading off additional gates and runtime.

    Table  3.  Comparison of the Adjustment Algorithms of ZPW, SABRE, FiDLS, {\rm{TSA}}_{{\rm{num}}} , and {\rm{TSA}}_{{\rm{cca}}}
    Algorithm N G G_0 G_1 G_2 G_3 G_4 \Delta_0 (\%) \Delta_1 (\%) \Delta_2 (\%) \Delta_4 (\%)
    ZPW 94 29443 14472 11244 4938 10173 10389 29.71 9.53 –106.01 2.08
    SABRE 105 49987 19053 16632 6204 12072 11904 36.61 27.41 –94.58 –1.41
    FiDLS 109 105428 45813 31011 16668 37800 37851 17.49 –21.89 –126.78 0.13
    TSA 124 150464 49620 30447 19068 40461 40629 18.46 –32.89 –112.19 0.41
    Note: N is the number of circuits that all the five adjustment algorithms can successfully transform, G is the number of gates in the input circuits, G_0G_4 are the numbers of additional gates inserted by ZPW, SABRE, FiDLS, TSA_{\rm{num}}, and TSA_{\rm{cca}}, respectively, and \Delta_i=(G_i-G_3)/G_i.
    下载: 导出CSV 
    | 显示表格

    Fourthly, we compare the overall performance of {\rm{TSA}}_{{\rm{num}}} and {\rm{TSA}}_{{\rm{cca}}} with SABRE and FiDLS on IBM Q Tokyo. We test 159 circuits, including 66 small-scale circuits, 49 medium-scale circuits, and 44 large-scale ones. Note that in Table 4 and Fig.8 we do not display the data for ZPW. Instead, we make comparison with SABRE because it is already shown that SABRE is much more scalable than ZPW[11]. In Fig.8, the number of additional gates introduced by the blue bars is the largest, followed by the red ones. We can see that the yellow bars are the shortest when the x -axis is greater than 3, indicating that FiDLS has inserted the fewest gates in the large-scale circuits. The green bars are for {\rm{TSA}}_{{\rm{num}}} . The number of additional gates it introduces is slightly larger than that of FiDLS. It can also be seen from Table 4 that {\rm{TSA}}_{{\rm{num}}} takes much less time than FiDLS in general. SABRE successfully transforms 144 circuits, including all the small-scale and medium-scale circuits, and 29 large-scale ones, which takes 12436 seconds. FiDLS successfully transforms 159 circuits, which takes 63841 seconds. {\rm{TSA}}_{{\rm{num}}} and {\rm{TSA}}_{{\rm{cca}}} are much faster, as they successfully transform all the 159 circuits, taking 2465 seconds and 2523 seconds, respectively. Compared with SABRE, the number of additional SWAP gates generated by {\rm{TSA}}_{{\rm{num}}} is reduced by 51% on average, among the 115 small-scale and medium-scale circuits that both of them can successfully transform.

    Table  4.  Comparison of Runtime and Number of Circuits Successfully Transformed by SABRE, FiDLS, {\rm{TSA}}_{{\rm{num}}} , and {\rm{TSA}}_{{\rm{cca}}}
    Scale N G SABRE FiDLS {\rm{TSA}}_{{\rm{num}}} {\rm{TSA}}_{{\rm{cca}}}
    N_0 G_0 t_0 (s) N_1 G_1 t_1 (s) N_2 G_2 t_2 (s) N_3 G_3 t_3 (s)
    Small 66 5997 66 2301 2 66 1329 7 66 894 16 66 897 21
    Medium 49 21618 49 10218 22 49 5328 90 49 5199 57 49 5280 62
    Large 44 3289162 29 162522 12412 44 532485 63744 44 1013196 2392 44 1037427 2440
    Sum 159 3312734 144 175041 12436 159 539142 63841 159 1015521 2465 159 1043604 2523
    Note: N is the number of test circuits, G is the number of gates in the input circuits, N_0N_3 are the numbers of circuits successfully transformed by SABRE, FiDLS, TSA_{\rm{num}}, and TSA_{\rm{cca}} respectively, t_0t_3 are the runtime of SABRE, FiDLS, TSA_{\rm{num}}, and TSA_{\rm cca}, respectively, and G_0G_3 are the numbers of additional gates inserted by SABRE, FiDLS, TSA_{\rm{num}}, and TSA_{\rm cca}, respectively.
    下载: 导出CSV 
    | 显示表格
    Figure  8.  Comparison of SABRE, {\rm{TSA}}_{{\rm{cca}}}, {\rm{TSA}}_{{\rm{num}}} and FiDLS on IBM Q Tokyo.

    In small-scale (resp.middle-scale) circuits, {\rm{TSA}}_{{\rm{num}}} generates an average of 33% (resp. 2%) fewer additional SWAP gates compared with FiDLS. Specifically, FiDLS inserts 1329 (resp. 5328) additional gates, while the number is 894 (resp. 5199) for {\rm{TSA}}_{{\rm{num}}} . When dealing with large-scale circuits, although {\rm{TSA}}_{{\rm{num}}} inserts more additional gates, it can convert large-scale circuits more than 25 times faster than FiDLS, as we can see in the fourth row and the t_{2} -column of Table 4.

    Finally, we set the 53-qubit quantum processor Sycamore as our target device and compare TSA with FiDLS still on the 159 benchmarks. In each row of Table 5, the same initial mapping algorithm is used, and in each column, the same adjustment algorithm is used. Generally speaking, TSA leads to a reduction of 2%-3% for the number of inserted additional gates. In the experiment, we find that the degrees of the Sycamore nodes are small and the maximum is 4. If the degrees of nodes in the interaction graph are generally greater than the maximum degree of Sycamore, it is not very suitable to use subgraph isomorphism to generate the set of partial initial mappings. The algorithm tempts to first match the node with the largest degree. If the node with the maximum degree does not satisfy the isomorphism condition, the initial mapping generated by the subgraph isomorphism algorithm is not friendly. However, the adjustment of TSA is still very effective because the time cost is drastically lowered, going from 31896 seconds for FiDLS to 1795 seconds for {\rm{TSA}}_{{\rm{num}}} , that is, the latter is more than 17 times faster than the former.

    Table  5.  Comparing the Initial Mapping and Adjustment Algorithms of FiDLS and TSA on Sycamore
    Algorithm FiDLS {\rm{TSA}}_{{\rm{num}}} {\rm{TSA}}_{{\rm{cca}}} \Delta_1 (\%) \Delta_2 (\%)
    G_0 t_0 (s) G_1 t_1 (s) G_2 t_2 (s)
    FiDLS 2311560 31896 2245314 233 2257371 3392 2.86 2.56
    TSA 2305125 31211 2234937 1795 2252271 3390 3.04 2.29
    Note: The number of test circuits, N, is 159, the number of gates in the input circuits, G, is 3312734, G_0G_2 are the numbers of additional gates inserted by FiDLS, TSA_{\rm{num}} and TSA_{\rm{cca}}, respectively, t_0t_2 are the runtime of FiDLS, TSA_{\rm{num}}, and TSA_{\rm{cca}}, respectively, and \Delta_i=(G_0-G_i)/G_0.
    下载: 导出CSV 
    | 显示表格

    We proposed a scalable algorithm called Tabu Search-Based Adjustment (TSA) for qubit mapping. We first used a subgraph isomorphism algorithm and a mapping completion algorithm based on the connectivity between qubits to generate a high-quality initial mapping. Then we employed a look-ahead heuristic search to adjust the mapping, which takes into account the influence of the gates yet to be processed to reduce the number of additional gates. We compared the performance of the initial mapping and adjustment algorithms of TSA with state-of-the-art algorithms ZPW, SABRE, and FiDLS, using the architectures of IBM Q Tokyo and Sycamore as the target devices. Our experimental results show that the initial mapping of TSA gives rise to fewer SWAP gates inserted and the adjustment algorithm can be obtained in an acceptable amount of time. Most small-scale and medium-scale circuits can be transformed in a few seconds. For large-scale circuits, the results can be obtained within a few minutes. In the future, we will investigate how to reduce the number of additional gates inserted and increase the speed. We will also apply the proposed method to more noisy intermediato-scale quantum (NISQ) devices.

  • Figure  1.   Quarter-view visualization example of complementary 2D and 3D for a human CT volume. The three 2D cross-sectional views are shown in (a) axial, (b) coronal, and (c) sagittal views, respectively. 3D DVR of the same volume is shown in (d). We use 3D Slicer software[1] to generate the visualizations.

    Figure  2.   Overview of our CBR-TF approach.

    Figure  3.   Ray extraction example and the ray representations (four items) used for our knowledge database construction. A point (cyan circle) is selected on a plane surface (cyan lines) of a volume (black line cube) in the two primary axes (Y- and Z-axes). A ray (orange arrow dot line) is determined by casting it down to the third axis (X-axis). The four components were obtained as an image pair co-planar to the ray in X-Z axes and X-Y axes (two rectangles with orange lines), and an intensity and SOI label profile along the ray with its location coordinates.

    Figure  4.   Illustration of AlexNet architecture[18]. The 1st convolutional (Conv1) layer filters the 224\times224 input image with 96 kernels of size 11\times11 with a stride of 4 pixels. The 2nd convolutional (Conv2) layer takes as input the (max pooled) output of Conv1 and filters it with 256 kernels of size 5\times5. The 3rd, 4th, and 5th convolutional layers are connected to one another without any pooling. The 5th layer is max pooled to the fully-connected (FC) 6th layer. We use FC7 as a feature extractor for image matching.

    Figure  5.   Warping path between an intensity profile pair example (q_p and c_p) in DTW.

    Figure  6.   Comparison of our two-stage method with the ED baseline method[17] using (a) a TIQ that encounters three SOIs: the liver (bright green color), arteries (red color), and the kidney (blue color). The right column shows the intensity profiles with the SOI labels, and the other two left columns show the associated image pair, respectively. The bounding boxes with orange lines indicate the compartments used for the retrieval computation. (b) Retrieval from our two-stage method (an image pair + an intensity profile). (c) Retrieval from ED (an intensity profile).

    Figure  7.   Comparison of our two-stage method with the two individual compartments: the image based AlexNet method and the intensity profile based DTW method, with (a) a TIQ that passes through three SOIs: the liver (bright green color), the artery (red color), and bones (brown color). The bounding boxes with orange lines indicate the compartments used for the retrieval computation. (b) Retrieval from our two-stage method (an image pair + an intensity profile). (c) Retrieval from AlexNet compartment (an image pair). (d) Retrieval from DTW compartment (an intensity profile).

    Figure  8.   (a) Complex TIQ that passes through four SOIs: the liver (bright green color), bones (brown color), the kidney (blue color), and the spleen (peach color). (b)–(e) The four most similar retrieval results from our two-stage method. The smallest similarity distance (the best matching) is colored in orange for each compartment (each column). (e) The overall best result from our two-stage method, denoted by “*”.

    Figure  9.   Example of a use-case for our CBR-TF approach, where the typical quarter-view visualization of a medical volume is used: 2D cross-sectional (a) axial, (b) coronal, and (c) sagittal view, together with (d) a 3D DVR. A user specifies SOIs such as the kidneys (blue color) and the spine (brown color) by drawing a line containing them onto (a) the axial view (a ray with gray color) and our CBR-TF approach updates the DVR to emphasize them in 3D.

    Figure  10.   Example of a use-case for our CBR-TF approach for the visual enhancement of local SOIs directly from DVR visualization: (b) the liver (bright green color), (c) the kidney (blue color), and (d) the bone (brown color), within (a) an upper-abdomen DVR. Each of the SOIs is selected by a single mouse click (yellow circles) on (a) the initial DVR where we construct a viewing ray perpendicular to the camera origin which contains each SOI.

    Figure  11.   Comparison of TF and DVR visualization results from (b) our CBR-TF approach and (c) the ED baseline approach[17] using (a) TIQ that consists of two SOIs of the lungs (dark green color) and bones (brown color).

    Table  1   Recall for Retrieval Among Six Different SOIs for the ED Baseline[17] and Our Two-Stage CBR Method with Two Individual Compartments

    Method Artery Bone Kidney Liver Lung Spleen All
    ED baseline 0.453 0.491 0.344 0.649 0.552 0.363 0.518
    Our two-stage CBR method 0.612 0.692 0.648 0.778 0.829 0.644 0.719
    DTW (individual compartment) 0.530 0.645 0.542 0.760 0.808 0.569 0.672
    AlexNet (individual compartment) 0.549 0.681 0.615 0.745 0.795 0.454 0.679
    Note: The bold numbers are the highest.
    下载: 导出CSV

    Table  2   Recall for Retrieval Among Six Different SOIs for Our Two-Stage CBR Method with Three Different Types of Pre-Trained CNNs[18, 25, 26] in Comparison with the ED Baseline[17]

    Method Artery Bone Kidney Liver Lung Spleen All
    With pre-trained AlexNet 0.612 0.692 0.648 0.778 0.829 0.644 0.719
    With pre-trained GoogleNet 0.591 0.681 0.616 0.770 0.836 0.608 0.707
    With pre-trained ResNet 0.543 0.624 0.547 0.682 0.668 0.487 0.620
    ED baseline 0.453 0.491 0.344 0.649 0.552 0.363 0.518
    Note: The bold numbers are the highest.
    下载: 导出CSV

    Table  3   Recall for Retrieval Among Six Different SOIs for the Pre-Trained AlexNet[18] and Its Fine-Tuning Counterpart[27]

    Method Artery Bone Kidney Liver Lung Spleen All
    With pre-trained AlexNet 0.612 0.692 0.648 0.778 0.829 0.644 0.719
    With fine-tuned AlexNet 0.609 0.700 0.617 0.765 0.816 0.688 0.714
    Note: The bold numbers are the highest.
    下载: 导出CSV

    Table  4   Average Time to Calculate the Retrieval Results from the Knowledge Database Among the Four Different CBR Methods

    CBR Method Time (s)
    ED baseline 0.84
    Our two-stage method 15.93
    DTW (individual compartment) 1.14
    AlexNet (individual compartment) 15.70
    下载: 导出CSV
  • [1]

    Fedorov A, Beichel R, Kalpathy-Cramer J, Finet J, Fillion-Robin J C, Pujol S, Bauer C, Jennings D, Fennessy F, Sonka M, Buatti J, Aylward S, Miller J V, Pieper S, Kikinis R. 3D Slicer as an image computing platform for the quantitative imaging network. Magnetic Resonance Imaging, 2012, 30(9): 1323–1341. DOI: 10.1016/j.mri.2012.05.001.

    [2]

    Ljung P, Krüger J, Groller E, Hadwiger M, Hansen C D, Ynnerman A. State of the art in transfer functions for direct volume rendering. Computer Graphics Forum, 2016, 35(3): 669–691. DOI: 10.1111/cgf.12934.

    [3]

    Kniss J, Kindlmann G, Hansen C. Interactive volume rendering using multi-dimensional transfer functions and direct manipulation widgets. In Proc. the 2001 IEEE Visualization, Oct. 2001, pp.255–562. DOI: 10.1109/VISUAL.2001.964519.

    [4]

    Correa C, Ma K L. Size-based transfer functions: A new volume exploration technique. IEEE Trans. Visualization and Computer Graphics, 2008, 14(6): 1380–1387. DOI: 10.1109/TVCG.2008.162.

    [5]

    Caban J J, Rheingans P. Texture-based transfer functions for direct volume rendering. IEEE Trans. Visualization and Computer Graphics, 2008, 14(6): 1364–1371. DOI: 10.1109/TVCG.2008.169.

    [6]

    Jung Y, Kim J, Kumar A, Feng D D, Fulham M. Feature of interest-based direct volume rendering using contextual saliency-driven ray profile analysis. Computer Graphics Forum, 2018, 37(6): 5–19. DOI: 10.1111/cgf.13308.

    [7]

    Ropinski T, Praßni J, Steinicke F, Hinrichs K. Stroke-based transfer function design. In Proc. the 5th Eurographics/IEEE VGTC Conference on Point-Based Graphics, Aug. 2008, pp.41–48.

    [8]

    Guo H Q, Mao N Y, Yuan X R. WYSIWYG (what you see is what you get) volume visualization. IEEE Trans. Visualization and Computer Graphics, 2011, 17(12): 2106–2114. DOI: 10.1109/TVCG.2011.261.

    [9]

    Correa C D, Ma K L. Visibility histograms and visibility-driven transfer functions. IEEE Trans. Visualization and Computer Graphics, 2011, 17(2): 192–204. DOI: 10.1109/TVCG.2010.35.

    [10]

    Jung Y, Kim J, Eberl S, Fulham M, Feng D D. Visibility-driven PET-CT visualisation with region of interest (ROI) segmentation. The Visual Computer, 2013, 29(6): 805–815. DOI: 10.1007/s00371-013-0833-1.

    [11]

    Jung Y, Kim J, Kumar A, Feng D D, Fulham M. Efficient visibility-driven medical image visualisation via adaptive binned visibility histogram. Computerized Medical Imaging and Graphics, 2016, 51: 40–49. DOI: 10.1016/j.compmedimag.2016.04.003.

    [12]

    Jung Y, Kim J, Bi L, Kumar A, Feng D D, Fulham M. A direct volume rendering visualization approach for serial PET–CT scans that preserves anatomical consistency. International Journal of Computer Assisted Radiology and Surgery, 2019, 14(5): 733–744. DOI: 10.1007/s11548-019-01916-2.

    [13]

    Marks J, Andalman B, Beardsley P A, Freeman W, Gibson S, Hodgins J, Kang T, Mirtich B, Pfister H, Ruml W, Ryall K, Seims J, Shieber S. Design galleries: A general approach to setting parameters for computer graphics and animation. In Proc. the 24th Annual Conference on Computer Graphics and Interactive Techniques, Aug. 1997, pp.389–400. DOI: 10.1145/258734.258887.

    [14]

    Guo H Q, Li W, Yuan X R. Transfer function map. In Proc. the 2014 IEEE Pacific Visualization Symposium, Mar. 2014, pp.262–266. DOI: 10.1109/PacificVis.2014.24.

    [15]

    LeCun Y, Bengio Y, Hinton G. Deep learning. Nature, 2015, 521(7553): 436–444. DOI: 10.1038/nature14539.

    [16]

    Kumar A, Kim J, Cai W D, Fulham M, Feng D G. Content-based medical image retrieval: A survey of applications to multidimensional and multimodality data. Journal of Digital Imaging, 2013, 26(6): 1025–1039. DOI: 10.1007/s10278-013-9619-2.

    [17]

    Kohlmann P, Bruckner S, Kanitsar A, Groller M E. Contextual picking of volumetric structures. In Proc. the 2009 IEEE Pacific Visualization Symposium, Apr. 2009, pp.185–192. DOI: 10.1109/PACIFICVIS.2009.4906855.

    [18]

    Krizhevsky A, Sutskever I, Hinton G E. ImageNet classification with deep convolutional neural networks. Communications of the ACM, 2017, 60(6): 84–90. DOI: 10.1145/3065386.

    [19]

    Keogh E, Ratanamahatana C A. Exact indexing of dynamic time warping. Knowledge and Information Systems, 2005, 7(3): 358–386. DOI: 10.1007/s10115-004-0154-9.

    [20]

    Soler L, Hostettler A, Agnus V, Charnoz A, Fasquel J B, Moreau J, Osswald A B, Bouhadjar M, Marescaux J. 3D image reconstruction for comparison of algorithm database: A patient specific anatomical and medical image database. Technical Report, IRCAD, 2010. https://www.ircad.fr/research/data-sets/liver-segmentation-3d-ircadb-01/, Mar. 2024.

    [21]

    Castro S, Königy A, Löffelmanny H, Gröllery E. Transfer function specification for the visualization of medical data. Technical Report, Vienna University of Technology, 1998. https://citeseerx.ist.psu.edu/doc_view/pid/08d0bdf2ffe297661e78568baa8f612c91d8e1c1, Mar. 2024.

    [22]

    Harrower M, Brewer C A. ColorBrewer.org: An online tool for selecting colour schemes for maps. The Cartographic Journal, 2003, 40(1): 27–37.

    [23]

    Nelder J A, Mead R. A simplex method for function minimization. The Computer Journal, 1965, 7(4): 308–313. DOI: 10.1093/comjnl/7.4.308.

    [24]

    Lagarias J C, Reeds J A, Wright M H, Wright P E. Convergence properties of the Nelder-Mead simplex method in low dimensions. SIAM Journal on Optimization, 1998, 9(1): 112–147. DOI: 10.1137/S1052623496303470.

    [25]

    Szegedy C, Liu W, Jia Y Q, Sermanet P, Reed S, Anguelov D, Erhan D, Vanhoucke V, Rabinovich A. Going deeper with convolutions. In Proc. the 2015 IEEE Conference on Computer Vision and Pattern Recognition, Jun. 2015, pp.1–9. DOI: 10.1109/CVPR.2015.7298594.

    [26]

    He K M, Zhang X Y, Ren S Q, Sun J. Deep residual learning for image recognition. In Proc. the 2016 IEEE Conference on Computer Vision and Pattern Recognition, Jun. 2016, pp.770–778. DOI: 10.1109/CVPR.2016.90.

    [27]

    Shin H C, Roth H R, Gao M C, Lu L, Xu Z Y, Nogues I, Yao J H, Mollura D, Summers R M. Deep convolutional neural networks for computer-aided detection: CNN architectures, dataset characteristics and transfer learning. IEEE Trans. Medical Imaging, 2016, 35(5): 1285–1298. DOI: 10.1109/TMI.2016.2528162.

    [28]

    Meyer-Spradow J, Ropinski T, Mensmann J, Hinrichs K. Voreen: A rapid-prototyping environment for ray-casting-based volume visualizations. IEEE Computer Graphics and Applications, 2009, 29(6): 6–13. DOI: 10.1109/MCG.2009.130.

    [29]

    Ahmed K T, Ummesafi S, Iqbal A. Content based image retrieval using image features information fusion. Information Fusion, 2019, 51: 76–99. DOI: 10.1016/j.inffus.2018.11.004.

    [30]

    Vishraj R, Gupta S, Singh S. A comprehensive review of content-based image retrieval systems using deep learning and hand-crafted features in medical imaging: Research challenges and future directions. Computers and Electrical Engineering, 2022, 104: 108450. DOI: 10.1016/j.compeleceng.2022.108450.

    [31]

    Wasserthal J, Breit H C, Meyer M T, Pradella M, Hinck D, Sauter A W, Heye T, Boll D T, Cyriac J, Yang S, Bach M, Segeroth M. TotalSegmentator: Robust segmentation of 104 anatomic structures in CT images. Radiology: Artificial Intelligence, 2023, 5(5): e230024. DOI: 10.1148/ryai.230024.

    [32]

    Zhang C Y, Zheng H, Gu Y. Dive into the details of selfsupervised learning for medical image analysis. Medical Image Analysis, 2023, 89: 102879. DOI: 10.1016/j.media.2023.102879.

    [33]

    Chen X X, Wang X M, Zhang K, Fung K M, Thai T C, Moore K, Mannel R S, Liu H, Zheng B, Qiu Y C. Recent advances and clinical applications of deep learning in medical image analysis. Medical Image Analysis, 2022, 79: 102444. DOI: 10.1016/j.media.2022.102444.

    [34]

    Wang L, Qian X M, Zhang Y T, Shen J L, Cao X C. Enhancing sketch-based image retrieval by CNN semantic re-ranking. IEEE Trans. Cybernetics, 2020, 50(7): 3330–3342. DOI: 10.1109/TCYB.2019.2894498.

    [35]

    Huang R Z, Ma K L. RGVis: Region growing based techniques for volume visualization. In Proc. the 11th Pacific Conference on Computer Graphics and Applications, Oct. 2003, pp.355–363. DOI: 10.1109/PCCGA.2003.1238277.

图(11)  /  表(4)
计量
  • 文章访问数:  275
  • HTML全文浏览量:  12
  • PDF下载量:  46
  • 被引次数: 0
出版历程
  • 收稿日期:  2023-05-20
  • 修回日期:  2024-01-17
  • 录用日期:  2024-01-17
  • 网络出版日期:  2024-01-19
  • 刊出日期:  2024-05-22

目录

/

返回文章
返回