A Simple Parallel Algorithm for the Medial Axis Transform (Special Issue on Architectures Algorithms and Networks for Massively parallel Computing)

スポンサーリンク

概要

• 論文の詳細を見る

• The medial axis transform (MAT) is an image representation scheme. For a binary image, the MAT is defined as a set of upright maximal squares which consist of pixels of value 1 entirely. The MAT plays an important role in image understanding. This paper presents a parallel algorithm for computing the MAT of an n×n binary image. We show that the algorithm can be performed in O(log n) time using n^2/log n processors on the EREW PRAM and in O(log log n) time using n^2/log log n processors on the common CRCW PRAM. We also show that the algorithm can be performed in O(n^2/p^2+n) time on a p×p mesh and in O(n^2/p^2+(n log p)/p) time on a p^2 processor hypercube (for 1≦p≦n). The algorithm is cost optimal on the PRAMs, on the mesh (for 1≦p≦√ltngt) and on the hypercube (for 1≦ p≦n/log n).

• 社団法人電子情報通信学会の論文
• 1996-08-25

著者

• Fujiwara Hideo

  Graduate School Of Information Science Nara Institute Of Science And Technology

• Fujiwara Hideo

  The Authors Are With The Graduate School Of Information Science Nara Institute Of Science And Techno

• Inoue M

  Graduate School Of Information Science Nara Institute Of Science And Technology

• Inoue Michiko

  Graduate School Of Information Science Nara Institute Of Science And Technology (naist)

• Fujiwara Hideo

  Naist

• Fujiwara Hideo

  Graduate School Of Infromation Science Nara Institute Of Science And Technology (naist)

• Fujiwara Hideo

  Nara Institute Of Science And Technology

• MASUZAWA Toshimitsu

  Graduate School of Information Science and Technology, Osaka University

• MASUZAWA Toshimitsu

  the Graduate School of Information Science and Technology, Osaka University

• FUJIWARA Akihiro

  Graduate School of Information Science, Nara Institute of Science and Technology

• Inoue Michiko

  Graduate School Of Information Science Nara Institute Of Science And Technology

• Masuzawa Toshimitsu

  Graduate School Of Information Science Nara Institute Of Science And Technology

• Masuzawa Toshimitsu

  Nara Institute Of Sciences And Technology

• Masuzawa Toshimitsu

  Graduate School Of Engineering Science Osaka University

• Masuzawa Toshimitsu

  Department Of Computer Science Graduate School Of Information Science And Technology Osaka Universit

• Fujiwara Hideo

  Graduate School Of Information Of Science Nara Institute Of Science And Technology

• Fujiwara H

  Nara Inst. Sci. And Technol. Kansai Science City Jpn

• Fujiwara A

  Ntt Docomo Inc. Yokosuka‐shi Jpn

関連論文

• Classification of Sequential Circuits Based on τ^k Notation and Its Applications(VLSI Systems)
• Fault-Tolerant and Self-Stabilizing Protocols Using an Unreliable Failure Detector
• F-Scan: A DFT Method for Functional Scan at RTL
• Analyzing Path Delay Fault Testability of RTL Data Paths:A Non-Scan Approach (デザインガイヤ2000) -- (VLSIの設計/検証/テスト及び一般)
• B-5-152 Impact of EDCA Parameters on Throughput Improvement in Layer-2 Mesh Networks with Hidden Terminal Problems
• B-5-151 EDCA Based Congestion Control Method for WLAN Mesh Networks
• Experimental Evaluation of Adaptive Contention Window Control for Layer-2 Mesh Networks
• Performance Evaluation of Mesh Network using Multi Frequency Bands
• Enhancement of Mesh Network Oriented IEEE802.11 MAC Protocol
• Performance Evaluation of Mesh Network using Multi Frequency Bands
• Enhancement of Mesh Network Oriented IEEE802.11 MAC Protocol
• B-5-250 Fairness Improvement by Enhanced IEEE802.11 MAC Protocol in Wireless Mesh Network
• B-5-249 Enhancement of Mesh Network Oriented IEEE802.11 MAC Protocol
• On the Effect of Scheduling in Test Generation
• Testing for the Programming Circuit of SRAM-Based FPGAs
• Analysis of Test Generation Complexity for Stuck-At and Path Delay Faults Based on τ^k-Notation(Complexity Theory)
• Reduction in Over-Testing of Delay Faults through False Paths Identification Using RTL Information
• A DFT Selection Method for Reducing Test Application Time of System-on-Chips(SoC Testing)(Test and Verification of VLSI)
• A Test Plan Grouping Method to Shorten Test Length for RTL Data Paths under a Test Controller Area Constraint(Test)(Dependable Computing)
• A Test Plan Grouping Method to Shorten Test Length for RTL Data Paths under a Test Controller Area Constraint
• Design for Two-Pattern Testability of Controller-Data Path Circuits
• Analyzing Path Delay Fault Testability of RTL Data Paths:A Non-Scan Approach (デザインガイヤ2000) -- (VLSIの設計/検証/テスト及び一般)
• Analyzing Path Delay Fault Testability of RTL Data Paths: A Non-Scan Approach (デザインガイヤ2000) -- (VLSIの設計/検証/テスト及び一般)
• New DFT Techniques of Non-Scan Sequential Circuits with Complete Fault Efficiency
• NoC-Compatible Wrapper Design and Optimization under Channel-Bandwidth and Test-Time Constraints
• On NoC Bandwidth Sharing for the Optimization of Area Cost and Test Application Time
• Scheduling Power-Constrained Tests through the SoC Functional Bus
• NoC Wrapper Optimization under Channel Bandwidth and Test Time Constraints
• Power-Conscious Microprocessor-Based Testing of System-on-Chip
• Power-Conscious Microprocessor-Based Testing of System-on-Chip(テスト,システム設計及び一般)
• A Self-Adaptive Routing Protocol in Wireless LANs Based on Attractor Selection
• A Biologically Inspired Self-Adaptation of Replica Density Control
• A Message-Efficient Peer-to-Peer Search Protocol Based on Adaptive Index Dissemination
• An Efficient Index Dissemination in Unstructured Peer-to-Peer Networks
• Self-Adaptive Mobile Agent Population Control in Dynamic Networks Based on the Single Species Population Model(Distributed Cooperation and Agents)
• Timed Uniform Atomic Broadcast in Presence of Crash and Timing Faults(Foundations of Computer Science)
• Delay Fault Testing of Processor Cores in Functional Mode(Dependable Computing)
• A Test Generation Framework using Checker Circuits and its Application to Path Delay Test Generation
• A Broadside Test Generation Method for Transition Faults in Partial Scan Circuits
• A Broadside Test Generation Method for Transition Faults in Partial Scan Circuits
• A Broadside Test Generation Method for Transition Faults in Partial Scan Circuits
• A Broadside Test Generation Method for Transition Faults in Partial Scan Circuits
• Equivalence of Sequential Transition Test Generation and Constrained Combinational Stuck-at Test Generation
• A Design Scheme for Delay Testing of Controllers Using State Transition Information
• Wait-Free Linearizable Distributed Shared Memory
• Parallel Algorithms for the All Nearest Neighbors of Binary Image on the BSP Model
• High-Level Synthesis for Weakly Testable Data Paths(Special Issue on Test and Diagnosis of VLSI)
• A Simple Parallel Algorithm for the Medial Axis Transform (Special Issue on Architectures Algorithms and Networks for Massively parallel Computing)
• Timed Atomic Broadcast Resiliet to Multiple Timing Faults
• FOREWORD
• Thermal-Aware Test Access Mechanism and Wrapper Design Optimization for System-on-Chips
• Thermal-aware test scheduling with cycle-accurate power profiles and test partitioning (システムLSI設計技術・デザインガイア2007--VLSI設計の新しい大地を考える研究会)
• Thermal-aware test scheduling with cycle-accurate power profiles and test partitioning (ディペンダブルコンピューティング)
• Thermal-aware test scheduling with cycle-accurate power profiles and test partitioning (VLSI設計技術)
• Power constrained IP core wrapper design with partitioned clock domains (回路とシステム)
• Power constrained IP core wrapper design with partitioned clock domains (VLSI設計技術)
• Power constrained IP core wrapper design with partitioned clock domains (信号処理)
• Timed Atomic Broadcast Resiliet to Multiple Timing Faults
• A Parallel Method for the Prefix Convex Hulls Problem
• Distributed Leader Election on Chordal Ring Networks
• Positron Annihilation in Nearly Perfect Crystals of Aluminum during Slow Cooling
• Performance Analysis of Parallel Test Generation for Combinational Circuits
• Optimal Granularity of Parallel Test Generation on the Client-Agent-Server Model
• Scheduling for Independent-Task Applications on Heterogeneous Parallel Computing Environments under the Unidirectional One-Port Model(Parallel and Distributed Computing,Foundations of Computer Science)
• Scheduling for Gather Operation in Heterogeneous Parallel Computing Environments
• A New Class of Sequential Circuits with Combinational Test Generation Complexity for Path Delay Faults
• SPIRIT:A High Robust Combinational Test Generation Algorithm (デザインガイヤ2000) -- (VLSIの設計/検証/テスト及び一般)
• Design for Hierarchical Two-Pattern Testability of Data Paths
• A Self-Stabilizing Spanning Tree Protocol that Tolerates Non-quiescent Permanent Faults
• A DFT Method for Core-Based Systems-on-a-Chip Based on Consecutive Testability
• A Fault Dependent Test Generation Method for State-Observable FSMs to Increase Defect Coverage under the Test Length Constraint
• Elucidation of Anti-allergic Activities of Curcumin-Related Compounds with a Special Reference to Their Anti-oxidative Activities(Medicinal Chemistry)
• Classification of Sequential Circuits Based on Combinational Test Generation Complexity
• Fault-Tolerance of Distributed Algorithms : Self-Stabilization and Wait-Freedom(Special Issue on Algorithm Engineering : Surveys)
• Hierarchical Composition of Self-Stabilizing Protocols Preserving the Fault-Containment Property
• Distributed Construction Protocols of Probabilistic Degree-Weighted Peer-to-Peer Overlays
• Self-Stabilization in Dynamic Networks
• A Non-scan DFT Method at Register-Transfer Level to Achieve 100% Fault Efficiency (特集:システムLSIの設計技術と設計自動化)
• Parallel Selection Algorithms for CGM and BSP Models with Application to Sorting (特集 並列処理) -- (並列・分散アルゴリズム)
• Efficient Linearizable Implementation of Shared FIFO Queues and General Objects on a Distributed System(Special Section on Discrete Mathematics and Its Applications)
• Self-Stabilizing Agent Traversal on Tree Networks(Distributed Cooperation and Agents)
• Power-Constrained Test Synthesis and Scheduling Algorithms for Non-Scan BIST-able RTL Data Paths(Dependable Computing)
• F-Scan : A DFT Method for Functional Scan at RTL
• A Low Power Deterministic Test Using Scan Chain Disable Technique
• A secure scan design approach using extended de Bruijn graph (ディペンダブルコンピューティング)
• A New Data Structure for SAT-Based Static Learning With Impact on Test Generation (特集 新アーキテクチャLSI技術および一般)
• Non-scan Design for Testability for Synchronous Sequential Circuits Based on Fault-Oriented Conflict Analysis(Fault Tolerance)
• Non-scan Design for Testability for Synchronous Sequential Circuits Based on Fault-Oriented Conflict Analysis
• A Method of Path Mapping from RTL to Gate Level and Its Application to False Path Identification
• Differential Behavior Equivalent Classes of Shift Register Equivalents for Secure and Testable Scan Design
• A Method of Parallelizing Consensuses for Accelerating Byzantine Fault Tolerance

もっと見る 閉じる

スポンサーリンク