절대값 대칭성과 사전 분류를 이용한 고속 Matching Pursuit

오석병,전병우,O, Seok-Byeong,Jeon, Byeong-U 대한전자공학회 2002 電子工學會論文誌-SP (Signal processing) Vol.39 No.2

비디오 데이터 부호화를 위한 여러 가지 방법들 중 matching pursuit을 이용한 비디오 부호화 방법은 저속 채널상에서 뛰어난 효율을 보이고 있으나, 기존의 블록 기반 변환 부호화 방법에 비하여 연산량이 월등히 많기 때문에 비디오 부호화에 적용하는 데는 어려운 점이 있다 본 논문에서는 matching pursuit의 전체 계산량 중 가장 큰 비중을 차지하는 내적 연산량을 줄이기 위해 matching pursuit의 내적연산에 사용되는 1차원 사전(Dictionary)을 구성하는 각각의 기본 신호들의 절대값이 대칭성을 가진다는 특성과, 크게 화질에 영향을 주지는 않지만 연산량을 줄이는 데는 도움을 줄 수 있도록 변형된 사전을 사용할 수 있다는 것, 그리고 주파수 특성을 이용하여 2차원 사전이 미리 분류될 수 있다는 사실을 이용한다. 실험결과에 나타난 바와 같이 제안하는 방법은 큰 화질 열화 없이, Neff가 제안한 사전의 분리성(Separability)을 이용한 기존의 고속 방법보다 내적 연산량에 소요되는 곱셈량을 약 1/8로 감소시키는 효과를 가져온다. Although the matching Pursuit is effective for video coding at low bit rate, it has a Problem since it needs much more calculation than the conventional block-based video coding method. The proposed fast matching pursuit method reduces inner product calculation that takes the most part of entire calculation by utilizing the symmetry of the absolute values of the one-dimensional Gator dictionary bases, the modified dictionary which allows faster matching without causing image quality degradation, and a Property of the two-dimensional Gabor dictionary that can be grouped in advance to four classes according to its frequency characteristics. Proposed method needs only about 1/8 of multiplications compared to the well-known separability-based fast method proposed by Neff.

시간차 보정을 적용한 Matching Pursuit 내삽 기법 연구

이재강,변중무,설순지,김영창 한국지구물리.물리탐사학회 2018 지구물리와 물리탐사 Vol.21 No.2

The recent research aim of seismic trace interpolation is to effectively interpolate the data with spatial aliasing. Among various interpolation methods, the Matching Pursuit interpolation, that finds the proper combination of basis functions which can best recover traces, has been developed. However, this method cannot interpolate aliased data. Thus, the multi-component Matching Pursuit interpolation and moveout correction method have been proposed for interpolation of spatially aliased data. It is difficult to apply the multi-component Matching Pursuit interpolation to interpolating the OBC (Ocean Bottom Cable) data which is the multi-component data obtained at the ocean bottom because the isolation of P wave component is required in advance. Thus, in this study, we dealt with an effective single-component matching Pursuit interpolation method in OBC data where P-wave and S-wave are mixed and spatial aliasing is present. To do this, we proposed the Ricker wavelet based single-component Matching Pursuit interpolation workflow with moveoutcorrection and systematically investigated its effectiveness. In this workflow, the spatial aliasing problem is solved by applying constant value moveout correction to the data before the interpolation is performed. After finishing the interpolation, the inverse moveout correction is applied to the interpolated data using the same constant velocity. Through the application of our workflow to the synthetic OBC seismic data, we verified the effectiveness of the proposed workflow. In addition, we showed that the interpolation of field OBC data with severe spatial aliasing was successfully performed using our workflow. 탄성파 내삽 기법의 최근 연구방향은 공간적 알리아싱이 존재하는 자료에서의 내삽을 효과적으로 수행하는 것이다. 다양한 내삽 기법 중 기저함수를 정의하여 트레이스를 가장 잘 복원할 수 있는 기저함수의 조합을 찾아내는 Matching Pursuit 내삽 기법이 개발된 바 있다. 그러나 이 방법은 공간적 알리아싱 문제를 해결하지 못하는데 이를 해결하기 위해다성분 Matching Pursuit 방법이 제안되었고 또한 시간차 보정(moveout correction) 방법도 소개된 바 있다. 다성분을 이용한 방법은 P파만을 갖는 다성분 자료가 획득되어야 하는데 해저면에서 다성분을 측정하는 OBC (Ocean Bottom Cable) 자료의 경우에는 P파 성분만을 분리하는 작업이 어려워 현장자료 적용이 힘들게 된다. 따라서 이 연구에서는 P파와 S파가 혼재하고 공간적 알리아싱이 존재하는 OBC 탐사 자료에서의 효과적인 단일성분 Matching Pursuit 내삽 기법을 다룬다. 이를 위해 시간차 보정을 포함하는 리커 요소파 기반의 단일성분 Matching Pursuit 내삽 기법 작업흐름도를 제안하고 그 효과를 체계적으로 살펴보았다. 이 작업흐름도는 내삽을 적용하기 전에 시간차 보정을 적용하고 다시 역 시간차보정을 적용하여 공간적 알리아싱 문제를 해결하였다. 제안한 작업흐름도를 OBC 측정을 가정한 합성탄성파탐사 자료에적용하여 그 효과를 검증하였고 현장자료에 적용함으로써 공간적 알리아싱이 심한 경우에도 내삽이 가능함을 확인하였다.

다중 후보 매칭 퍼슛

권석법,심병효,Kwon, Seokbeop,Shim, Byonghyo 한국방송∙미디어공학회 2012 방송공학회논문지 Vol.17 No.6

As a greedy algorithm reconstructing the sparse signal from underdetermined system, orthogonal matching pursuit (OMP) algorithm has received much attention. In this paper, we multiple candidate matching pursuit (MuCaMP), which builds up candidate support set in every iteration and uses the minimum residual at last iteration. Using the restricted isometry property (RIP), we derive the sufficient condition for MuCaMP to recover the sparse signal exactly. The MuCaMP guarantees to reconstruct the K-sparse signal when the sensing matrix satisfies the RIP constant ${\delta}_{N+K}<\frac{\sqrt{N}}{\sqrt{K}+3\sqrt{N}}$. In addition, we show a recovery performance both noiseless and noisy measurements. Orthogonal matching pursuit (OMP) 알고리듬은 underdetermined 시스템에서 희소 신호를 복구하는 대표적인 greedy 알고리듬으로 많은 관심을 받고 있다. 본 논문에서는 OMP 알고리듬의 반복과정에서 후보 support 집합들을 구성하여 마지막 반복과정에서 최소 잔차를 이용하는 multiple candidate matching pursuit (MuCaMP) 기법을 제안한다. MuCaMP 가 완벽한 신호 복원을 보장하기 위한 restricted isometry property (RIP)를 이용한 충분조건, ${\delta}_{N+K}<\frac{\sqrt{N}}{\sqrt{K}+3\sqrt{N}}$을 제시한다. 실험을 통해 후보 support 집합들의 크기에 따른 성능과 MuCaMP의 복원 성능이 기존의 기법들에 비해 우수함을 확인하였다.

Matching pursuit based robust acoustic event classification for surveillance systems

Nguyen, Q.,Choi, J. Pergamon Press ; Elsevier Science Ltd 2017 Computers & electrical engineering Vol.57 No.-

<P>The ability to automatically recognize acoustic events in real world conditions is an important application of the surveillance systems. This paper presents an acoustic event classification (AEC) method which uses the Matching Pursuit to extract the important Gabor atoms from input audio signals. Rather than extracting features in short-time frames, we apply the matching pursuit to the whole duration of an acoustic event. Information from atoms, such as time, frequency, and amplitude are used to construct time-frequency features. These features capture both spectral and temporal information of the sound event, which is analogous to the spectrogram representation. Experiments were performed on an 8-class database including human scream and gunshot. Under noisy and mismatched conditions, the proposed classification method achieves Fl-score of 0.814, which is superior to state-of-the-art methods. (C) 2016 Elsevier Ltd. All rights reserved.</P>

일반화된 직교 매칭 퍼슛 알고리듬

권석법,심병효 대한전자공학회 2012 電子工學會論文誌-SP (Signal processing) Vol.49 No.2

As a greedy algorithm reconstructing the sparse signal from underdetermined system, orthogonal matching pursuit (OMP) algorithm has received much attention in recent years. In this paper, we present an extension of OMP for pursuing efficiency of the index selection. Our approach, referred to as generalized OMP (gOMP), is literally a generalization of the OMP in the sense that multiple (N) columns are identified per step. Using the restricted isometry property (RIP), we derive the condition for gOMP to recover the sparse signal exactly. The gOMP guarantees to reconstruct sparse signal when the sensing matrix satisfies the RIP constant []. In addition, we show recovery performance and the reduced number of iteration required to recover the sparse signal. Compressive sensing 분야에서 orthogonal matching pursuit (OMP) 알고리듬은 underdetermined 시스템의 스파스 (sparse)신호를 복구하는 대표적인 greedy 알고리듬으로 많은 관심을 받고 있다. 본 논문에서는 OMP 알고리듬의 반복과정에서 하나이상의 support들을 선택할 수 있도록 하는 OMP 알고리듬의 일반화된 형태의 generalized orthogonal matching pursuit (gOMP)기법을 제안한다. gOMP가 완벽한 신호 복원을 보장하기 위해 restricted isometry property (RIP)를 이용한 충분조건,[]을 제시한다. 실험을 통해 gOMP는 매 반복과정에서 하나 이상의 support들를 선택함으로써 높은 복원 성능과 낮은 복잡도를 가짐을 확인하였다.

Group-Sparse Channel Estimation using Bayesian Matching Pursuit for OFDM Systems

( Yi Liu ),( Wenbo Mei ),( Huiqian Du ) 한국인터넷정보학회 2015 KSII Transactions on Internet and Information Syst Vol.9 No.2

We apply the Bayesian matching pursuit (BMP) algorithm to the estimation of time-frequency selective channels in orthogonal frequency division multiplexing (OFDM) systems. By exploiting prior statistics and sparse characteristics of propagation channels, the Bayesian method provides a more accurate and efficient detection of the channel status information (CSI) than do conventional sparse channel estimation methods that are based on compressive sensing (CS) technologies. Using a reasonable approximation of the system model and a skillfully designed pilot arrangement, the proposed estimation scheme is able to address the Doppler-induced inter-carrier interference (ICI) with a relatively low complexity. Moreover, to further reduce the computational cost of the channel estimation, we make some modifications to the BMP algorithm. The modified algorithm can make good use of the group-sparse structure of doubly selective channels and thus reconstruct the CSI more efficiently than does the original BMP algorithm, which treats the sparse signals in the conventional manner and ignores the specific structure of their sparsity patterns. Numerical results demonstrate that the proposed Bayesian estimation has a good performance over rapidly time-varying channels.

공간적인 알리아싱을 포함한 탄성파 트레이스의 내삽을 위한요소파 기반의 Matching Pursuit 기법

최지훈 ( Jihun Choi ),변중무 ( Joong Moo Byun ),설순지 ( Soon Jee Seol ) 한국지구물리·물리탐사학회 2014 지구물리와 물리탐사 Vol.17 No.2

Due to mechanical failure or geographical accessibility, the seismic data can be partially missed. In addition, it can be coarsely sampled such as crossline of the marine streamer data. This seismic data that irregular sampled andspatial aliased may cause problems during seismic data processing. Accurate and efficient interpolation method can solvethis problem. Futher more, interpolation can save the acquisition cost and time by reducing the number of shots and receivers. Among various interpolation methods, the Matching Pursuit method can be applied to any sampling type which is regular or irregular. However, in case of using sinusoidal basis function, this method has a limitation in spatial aliasing. Therefore, in this study, we have developed wavelet based Matching Pursuit method that uses wavelet instead of sinusoidal function for the improvement of dealiasing performance. In addition, we have improved interpolation speed by using inner product instead of L-2 norm.

1-비트 압축 센싱을 위한 효율적인 알고리즘

노예림,홍송남 한국통신학회 2022 韓國通信學會論文誌 Vol.47 No.9

In this paper, we consider a compressed sensing (CS) problem with multiple measurement vector (MMV), in which a set of sparse signals with the same support are recovered simultaneously from the corresponding measurements. Many practical problems (e.g., active user detection for massive connectivity, communication-efficient federated learning, and so on) have been formulated in this problem. Also, it is necessary to investigate one-bit CS under the MMV framework, in order to boost communication efficiency. Unfortunately, the best-known one-bit CS algorithms such as Bayesian matching pursuit (BMP) is not applicable to the emerging one-bit MMV problems. In these problems, we propose novel algorithms, named Turbo-BMP as nontrivial extensions of BMP, respectively. Simulation results demonstrate the superiority of the proposed algorithm. 본 논문에서는 같은 서포트를 가진 일련의 희소 신호가 해당 측정으로부터 동시에 복구되는 다중 측정 벡터(Multiple Measurement Vector, MMV)를 가진 압축 센싱(Compressive Sensing, CS) 문제를 고려한다. 이 문제에는 많은 실용적인 문제(예: 대규모 연결, 통신 효율 연합 학습 등에 대한 능동적인 사용자 탐지 등)가 형성되었다. 또한 통신 효율을 높이기 위해서는 다중 측정 벡터 프레임워크에서의 1-비트 압축 센싱에 대한 연구가 필요하다. 그러나, 베이지안 매칭 추구(Bayesian Matching Pursuit, BMP)와 같은 잘 알려진 1-비트 압축 센싱 알고리즘은새로운 1-비트 다중 측정 문제에 적용되지 않는다. 이러한 문제에서 우리는 BMP 알고리즘의 확장으로Turbo-BMP(Turbo-Bayesian Matching Pursuit)라는 새로운 알고리즘을 제안한다. 벤치마크 알고리즘으로써, M-BMP(Multiple Measurement Vector-Bayesian Matching Purrsuit)를 비교하여 시뮬레이션을 진행한다. 시뮬레이션 결과는 제안한 알고리즘인 Turbo-BMP의 우수성을 보여준다.

심음 분석을 위한 주파수 특성에 기반한 매칭퍼슈잇 방법

김일동(Il-Dong Kim),정규혁(Gyu-Hyeok Jeong),임종하(Jong-Ha Lim),이인성(In-Sung Lee) 大韓電子工學會 2010 電子工學會論文誌-SC (System and control) Vol.47 No.1

심음은 심질환을 진단하는 1차적인 수단이지만 비정상 심음인 S2에서 A2와 P2의 분열 신호와 S2에 S3의 분마음 간섭 신호는 전문 의사들조차 청각적으로 구분하기 쉽지 않아 초기 진단에 어려움이 있다. 본 논문에서는 청각적으로 구분이 어려운 심음들을 분류하기 위해 PCG 신호의 주파수 특성에 적합한 분석 및 합성 방법을 제안한다. 제안한 방법은 심음을 매칭 퍼슈잇으로 분해한 후 주파수 특성에 맞게 대역별로 합성하여 분석함으로써 청진으로 구분이 어려운 신호를 다른 상태의 심음과 구별한다. 실험 결과 분석을 통해 초기 진단 시 불명확한 S2의 분열 유무, S2의 분열 상태, 그리고 S3의 분마음 간섭 신호를 구별할 수 있었으며 분열의 정확한 시간 간격을 확인할 수 있었다. Although heart auscultation is an important tool for the diagnosis of heart disease, it is seen that the human ear is poorly suited for cardiac auscultation such as the paradoxical split of S2, the split of S2, and the summation of S2 and S3 gallop. In this paper, the analysis-synthesis method that is suitable for the characteristics of PCG is proposed to classify the heart sound. In analyzing the PCG according to matching pursuit method and synthesizing the PCG in each bandwidth based on the frequency characteristics, it sorts normal hearts with abnormal hearts that is difficult to classify as cardiac auscultation. The result shows that it qualifies the appearance of split in S2 and the paradoxical split of S2 and also can estimate the delay between the two components.

다중반송파 시스템의 정합추구 기반 희소 다중경로 채널 추정

김시현 水原大學校 2012 論文集 Vol.26 No.-

주파수 선택적 페이딩 채널을 위한 선형 채널 추정 방식의 성능은 파일럿의 개수에 비례하므로 채널 추정의 정확도를 높이기 위해서 많은 파일럿을 쓰지 않을 수 없으며 필연적으로 전송 효율성이 낮아지는 단점이 있다. 또한 다중경로 채널의 희소(sparse)한 특성을 활용하지 않고 있다. 본 논문에서는 압축센싱 기법을 이용하여 아주 적은 수의 파일럿으로 희소한 채널을 추정하는 정합추구 기반 알고리듬과 이를 위한 파일럿 배치 방법을 제안한다. 또한 모의 실험을 통해 LS (least square) 채널 추정 방식보다 적은 수의 파일럿으로 우수한 채널 추정 성능을 보임을 확인한다. Although linear channel estimation for the frequency selective fading channel has been widely deployed, its accuracy depends on the number of pilots to probe the channel. Thus, it is unavoidable to employ large number of pilots to enhance the channel estimation performance, which essentially leads to the degradation of the transmission efficiency. It even does not utilize the sparseness of the multipath channel. In this paper a sparse channel estimation scheme based on the matching pursuit algorithm, which requires far less number of pilots, with its assignment method is proposed. And the simulation results reveal the proposed algorithm shows superior channel estimation performance with fewer pilots to the LS based ones.