The k-nearest neighbor (KNN) algorithm has been widely used in pattern recognition, regression, outlier detection and other data mining areas. However, it suffers from the large distance computation cost, especially w...
详细信息
The k-nearest neighbor (KNN) algorithm has been widely used in pattern recognition, regression, outlier detection and other data mining areas. However, it suffers from the large distance computation cost, especially when dealing with big data applications. In this paper, we propose a new fastsearch (FS) algorithm for exact k-nearest neighbors based on optimal triangle-inequality-based (OTI) check strategy. During the procedure of searching exact k-nearest neighbors for any query, the OTI check strategy can eliminate more redundant distance computations for the instances located in the marginal area of neighboring clusters compared with the original TI check strategy. Considering the large space complexity and extra time complexity of OTI, we also propose an efficient optimal triangle-inequality-based (EOTI) check strategy. The experimental results demonstrate that our proposed two algorithms (OTI and EOTI) achieve the best performance compared with other related KNN fast search algorithms, especially in the case of dealing with high-dimensional datasets. (C) 2019 Elsevier B.V. All rights reserved.
In the re-evaluated paper, Xie et al. proposed a new fast search algorithm for vector quantization encoding, which optimized the priority checking order of variance and norm inequality in order to speed up the encodin...
详细信息
In the re-evaluated paper, Xie et al. proposed a new fast search algorithm for vector quantization encoding, which optimized the priority checking order of variance and norm inequality in order to speed up the encoding procedure. CPU time of different encoding algorithms is given to support their algorithm. However, first, some of the experimental data in the re-evaluated paper are unreasonable and unrepeatable. And second, as an improved algorithm of equal-average equal-variance equal-norm nearest neighbor fast search algorithm, the re-evaluated algorithm in fact cannot achieve a better performance than the existing improved equal-average equal-variance nearest neighbor fast search algorithm. In this paper, these two problems are analyzed, re-evaluated, and discussed in detail.
Digital image source identification primarily focuses on analyzing and detecting the machine imprints or camera fingerprints left by imaging devices during the imaging process to trace the origin of digital images. Th...
详细信息
Digital image source identification primarily focuses on analyzing and detecting the machine imprints or camera fingerprints left by imaging devices during the imaging process to trace the origin of digital images. The development of a swift searchalgorithm is crucial for the effective implementation of camera source identification. Despite its importance, this domain has witnessed limited research, with existing studies predominantly focusing on search efficiency while neglecting robustness, which is essential. In practical scenarios, query images often suffer from poor signal quality due to noise, and the variability in fingerprint quality across different sources presents a significant challenge. Conventional brute-force searchalgorithms (BFSAs) prove largely ineffective under these conditions because they lack the necessary robustness. This paper addresses the issues in digital image source identification by proposing a rapid fingerprint searchalgorithm based on global information. The algorithm innovatively introduces a search priority queue (SPQ), which analyzes the global correlation between the query fingerprint and all reference fingerprints in the database to construct a comprehensive priority ranking, thereby achieving the efficient retrieval of matching fingerprints. Compared to the traditional brute-force searchalgorithm (BFSA), our method significantly reduces computational complexity in large-scale databases, optimizing from O(nN) to O(nlogN), where n is the length of the fingerprint, and N is the number of fingerprints in the database. Additionally, the algorithm demonstrates strong robustness to noise, maintaining a high matching accuracy rate even when image quality is poor and noise interference is significant. Experimental results show that in a database containing fingerprints from 70 cameras, our algorithm is 50% faster in average search time than BFSA, and its matching accuracy rate exceeds 90% under various noise levels. This method not o
For the characteristics of the depth map with a large smooth area, it is not necessary in the 3D-High-Efficiency Video Coding (3D-HEVC) to use TZ search for inter-frame prediction. According to the parallelism of dept...
详细信息
ISBN:
(纸本)9789881476883
For the characteristics of the depth map with a large smooth area, it is not necessary in the 3D-High-Efficiency Video Coding (3D-HEVC) to use TZ search for inter-frame prediction. According to the parallelism of depth map interframe algorithms, analyzed the parallelism of full search, three-step search and diamond search in the array structure, this paper proposes a parallel implementation method of 3D-HEVC depth map inter-frame prediction based on array processor. Considering only the depth map encoding, the experimental results show that the synthesized frequency under the BEE4 FPGA chip is as high as 100.261MHZ. Compared with the software 3D-HEVC Test Model (HTM) version 16.1, without affecting the video quality, the speedup ratio of the full search mode can reach 35, the speedup ratio of the three-step search mode can reach 160, and the speedup ratio of the diamond search can reach 233.
The latest video coding standard High Efficiency Video Codec (HEVC) recommends diamond and square searchalgorithm as the fast integer motion estimation (IME). Besides, there are many other fast motion estimation algo...
详细信息
ISBN:
(数字)9781728151632
ISBN:
(纸本)9781728151632
The latest video coding standard High Efficiency Video Codec (HEVC) recommends diamond and square searchalgorithm as the fast integer motion estimation (IME). Besides, there are many other fast motion estimation algorithms, such as, 3-steps search, 4 steps search, etc. However, the complexity and structure of these algorithm's search patterns makes it difficult to implement in hardware. This paper proposes two novel IME hardware-friendly search patterns, so called Wide Diamond and Wide Hexagon. Comparing to the recommended fast search algorithm, experimental results show that the IME time taken is reduced 3 times and 5 times, respectively, in case of applying Wide Hexagon algorithm and Wide Diamond algorithm, while the bit rate and Peak signal to Noise ratio PSNR are virtually unchanged.
In the encoding depth map of 3D-HEVC, a fast block searchalgorithm is proposed to solve the problem of fixed block pattern of inter-view prediction algorithm. Variable block sizes mode is used to select prediction mo...
详细信息
ISBN:
(纸本)9781728132488
In the encoding depth map of 3D-HEVC, a fast block searchalgorithm is proposed to solve the problem of fixed block pattern of inter-view prediction algorithm. Variable block sizes mode is used to select prediction mode by comparing depth values, and then the algorithm is parallelly mapped to a video array processor. Compared with HTM16.2 software implementation, the average encoding time of the proposed algorithm is reduced by more than 100 times. In addition, the hardware resource usage is reduce by 27.21% with similar processing speeds.
Block matching based motion estimation (BMME) is widely used in video compression and stereoscopic image processing. Given that the full searchalgorithm is not efficient enough, many fast motion estimation algorithms...
详细信息
ISBN:
(纸本)9781538682401
Block matching based motion estimation (BMME) is widely used in video compression and stereoscopic image processing. Given that the full searchalgorithm is not efficient enough, many fast motion estimation algorithms are based on BMME. Adaptive rood path search (ARPS), which is an important process of the BMME method, exploits the inter-block correlation and zero-motion prejudgment to reduce the search cost. Although ARPS is very efficient, there is a gap between ARPS and full search in accuracy. In this manuscript, we propose a novel adaptive rood path search (N-ARPS) algorithm with small-motion prejudgment (SMP). SMP is to select appropriate search strategy for each block according to its motion properties. In addition, region of support (ROS) expansion is applied to have a better prediction for the initial search. Experimental results show that the proposed fast search algorithm has a near-optimal search accuracy and extremely lower computational complexity when compared with standard-of-the-art algorithms.
作者：
Zhang, JieHenan Univ
Puyang Inst Technol Dept Math & Informat Engn Puyang 457000 Peoples R China
In order to improve the accuracy of database retrieval, a fast retrieval algorithm of feature information in database based on Naive Bayes is proposed. Firstly, the data structure of database is analyzed, and the algo...
详细信息
In order to improve the accuracy of database retrieval, a fast retrieval algorithm of feature information in database based on Naive Bayes is proposed. Firstly, the data structure of database is analyzed, and the algorithm of semantic correlation degree feature extraction is designed. The feature extraction results are processed by clustering, and the interference data is processed by noise reduction and filtering, so that the information can be retrieved quickly. Experimental results show that the proposed algorithm has higher accuracy in database retrieval.
Most of the fastsearch motion estimation algorithms reduce the computational cost of motion estimation (ME) greatly by checking only a few search points inside the search area by using full distortion measure. This p...
详细信息
Most of the fastsearch motion estimation algorithms reduce the computational cost of motion estimation (ME) greatly by checking only a few search points inside the search area by using full distortion measure. This paper proposes multi-layer motion estimation (MME) which employs partial distortion as its distortion measure to reduce the number of computations involved in each search point instead of reducing the number of search points. The MME, first, constructs the layers from the reference frame so as to facilitate the calculation of partial distortion measures on the layers. Later, it searches motion vectors by computing the partial distortion measures on the layers. A layer is an image which is derived from the reference frame such that the summation of a block of pixels in the reference frame determines the point of a layer. It has been noticed on different video sequences that many motion vectors on the layers are the same as those searched on the reference frame. Experimental results on a wide variety of video sequences show that the proposed algorithm outperforms the other popular conventional fastsearch motion estimation algorithms computationally while maintaining the motion prediction quality very close to the full-searchalgorithm.
Motion estimation is an essential procedure in video coding and object tracing, but it always has a high computational load. Some low bit-depth motion estimation methods, such as one/two-bit transform or gray coding b...
详细信息
ISBN:
(纸本)9781509011346
Motion estimation is an essential procedure in video coding and object tracing, but it always has a high computational load. Some low bit-depth motion estimation methods, such as one/two-bit transform or gray coding based methods, have lower complexity. However, one-bit transform based methods are sensitive to noise, whereas two-bit transform and gray coding methods use many bit planes or operations to perform motion estimation. In this paper, we select features with high representative by two means. First, we present an improved one-bit transform with pre-processing techniques. Second, an adaptive matching criterion was introduced to pick out features with higher representative. Moreover, a fast search algorithm is also proposed to reduce the searching cost. The experimental results show that the proposed algorithm outperforms other methods both in matching accuracy and in computation efficiency.
暂无评论