In recent years, median filtering detection has a widely application in many fields such as images' processing history tracking, image editing detection, image anti-forensics analyzing and anti-steganalysis analyz...
详细信息
In recent years, median filtering detection has a widely application in many fields such as images' processing history tracking, image editing detection, image anti-forensics analyzing and anti-steganalysis analyzing. In this paper, we propose two median filtering detection algorithms. The algorithm I is a recognition algorithm that can identify whether a given image has undergone median filtering. The algorithm II is a discriminating algorithm that can distinguish a median (average, Gaussian) filtered image from unfiltered images. Differing from the general framework of existing median filtering detectors, the contribution of our work is that the presented methods are not based on the statistical learning model. The proposed methods do not need any classifier, or any threshold. These methods are implemented by counting the number of specific Local Binary Pattern encoding patterns of a single image. Experimental results demonstrate that the proposed methods provide high accuracy and broad-spectrum robustness for tolerating content-preserving manipulations. Compared to state-of-the-art methods, the proposed methods exhibit high efficiency, high accuracy, and strong robustness.
Recently new classes of directed, acyclic graphs with n vertices, namely A(m)-orders where m is a larger than I integer, have been presented. These classes contain the interval orders, but are incomparable to trees. H...
详细信息
Recently new classes of directed, acyclic graphs with n vertices, namely A(m)-orders where m is a larger than I integer, have been presented. These classes contain the interval orders, but are incomparable to trees. Here it is shown that the complexity of recognizing the A(m)-order class is O(n(9)), hence independent of m. However, recognizing if a graph is in A(m)-orders for all m might be done in O(n(3)) time. These classes have an application in the preemptive multiprocessor scheduling problem. This problem is NP-hard if the number of processors is arbitrary but open for a fixed number of processors m. When the task graph is an A(m)-order, the problem is polynomial on m processors. Hence it is interesting to recognize such task graphs in a polynomial, independent of m time, especially when the number of processors is large, for instance on a computation grid. (C) 2009 Published by Elsevier B.V.
This paper presents new algorithms for recognizing several classes of perfectly orderable graphs. Bipolarizable and P-4-simplicial graphs are recognized in O(n(3.376)) time, improving the previous bounds of O(n(4)) an...
详细信息
This paper presents new algorithms for recognizing several classes of perfectly orderable graphs. Bipolarizable and P-4-simplicial graphs are recognized in O(n(3.376)) time, improving the previous bounds of O(n(4)) and O(n(5)), respectively. Brittle and semi-simplicial graphs are recognized in O(n(3)) time using a randomized algorithm, and O(n(3) log(2) n) time if a deterministic algorithm is required. The best previous time bound for recognizing these classes of graphs is O(m(2)). Welsh-Powell opposition graphs are recognized in O(n(3)) time, improving the previous bound of O(n(4)). HHP-free graphs and maxibrittle graphs are recognized in O(mn) and O(n(3.376)) time, respectively. (C) 2003 Elsevier Science B.V. All rights reserved.
Let G be a cube-free median graph. It is proved that k/2 >= root n-1 >= m/2 root n- >= root n >= root s >= r-1, where n, m, s, k, and r are the number of vertices, edges, squares, Theta-classes, and the...
详细信息
Let G be a cube-free median graph. It is proved that k/2 >= root n-1 >= m/2 root n- >= root n >= root s >= r-1, where n, m, s, k, and r are the number of vertices, edges, squares, Theta-classes, and the number of edges in a smallest Theta-class of G, respectively. Moreover, the equalities characterize Cartesian products of two trees of the same order. The cube polynomial of cube-free median graphs is also considered and it is shown that planar cube-free median graphs can be recognized in linear time. (c) 2006 Elsevier B.V. All rights reserved.
The respiratory health and comfort of animals are closely associated with the air quality of their living environment. The aim of the present work is to identify the relationship between animal sounds and air quality ...
详细信息
The respiratory health and comfort of animals are closely associated with the air quality of their living environment. The aim of the present work is to identify the relationship between animal sounds and air quality of their living environment. Cough sounds of 84 weaners and four important aerial factors (i.e., air temperature, relative humidity, ammonia concentration, and dust concentration) were measured. The resulting power spectral density (PSD) showed a significant difference in cough sounds from weaners under different air qualities. Moreover, the developed recognition algorithm, using mel frequency cepstrum coefficients (MFCCs), principal component analysis (PCA), and support vector machine (SVM), provided an average recognition rate of 95% for sound samples collected in different pig houses. The results indicate that the cough sound analysis can provide qualitative information about the situation of the air quality in commercial livestock buildings.
The problems of recognizing series-parallel graphs, outerplanar graphs, and generalized series-parallel graphs have been studied separately in the past. Efficient algorithms have been presented. However, none of the a...
详细信息
The problems of recognizing series-parallel graphs, outerplanar graphs, and generalized series-parallel graphs have been studied separately in the past. Efficient algorithms have been presented. However, none of the algorithms are certifying. A certifying algorithm generates, in addition to its answer, a certificate that can be used by a checker (a separate algorithm) to verify the correctness of the answer. The certificate is positive if the answer is 'yes', and is negative if the answer is 'no'. In this paper, an O(|E| + |V |)-time certifying algorithm that simultaneously determines if a graph G = (V, E) is series- parallel, outerplanar, or generalized series-parallel is presented. The positive certificates are a construction sequence for constructing G if G is series-parallel, a generalized construction sequence for constructing G if G is generalized series-parallel but not series-parallel, and the edge set of the exterior boundary of an outerplanar embedding of G if G is outerplanar. The negative certificates are forbidden subgraphs or forbidden structures of G. All these certificates are generated by making only one pass over G after a preprocessing step decomposing G into its biconnected components.(c) 2022 Elsevier B.V. All rights reserved.
In a companion paper [P.R.J. Asveld, Fuzzy context-free languages-Part 1: Generalized fuzzy context-free grammars, Theoret. Comput. Sci. (2005)] we used fuzzy context-free grammars in order to model grammatical errors...
详细信息
In a companion paper [P.R.J. Asveld, Fuzzy context-free languages-Part 1: Generalized fuzzy context-free grammars, Theoret. Comput. Sci. (2005)] we used fuzzy context-free grammars in order to model grammatical errors resulting in erroneous inputs for robust recognizing and parsing algorithms for fuzzy context-free languages. In particular, this approach enables us to distinguish between small errors ("tiny mistakes") and big errors ("capital blunders"). In this paper, we present some algorithms to recognize fuzzy context-free languages: particularly, a modification of Cocke-Younger-Kasami's algorithm and some recursive descent algorithms. Then we extend these recognition algorithms to corresponding parsing algorithms for fuzzy context-free languages. These parsing algorithms happen to be robust in some very elementary sense. (c) 2005 Elsevier B.V. All rights reserved.
We use breadth-first search and contractions of subgraphs to give a new and faster algorithm to recognize i-triangulated graphs. (C) 2000 Elsevier Science B.V. All rights reserved.
We use breadth-first search and contractions of subgraphs to give a new and faster algorithm to recognize i-triangulated graphs. (C) 2000 Elsevier Science B.V. All rights reserved.
The k-path graph P-k(H) Of a graph H has all length-k paths of H as vertices;two such vertices are adjacent in the new graph if their union forms a path or cycle of length k + 1 in H, and if the common edges of both p...
详细信息
The k-path graph P-k(H) Of a graph H has all length-k paths of H as vertices;two such vertices are adjacent in the new graph if their union forms a path or cycle of length k + 1 in H, and if the common edges of both paths form a path of length k - 1. In this paper we give a (nonpolynomial) recognition algorithm for k-path graphs, for every integer k greater than or equal to 2. The algorithm runs in polynomial time if we are only interested in k-path graphs of graphs of high enough minimum degree. We also present an O(\V\(4))-time algorithm that decides whether for any input graph G = (V,E) there exist some integer k greater than or equal to 1 and some graph H of minimum degree at least k + 1 with G = P-k(H). If it is, we show that Ic and H are unique, extending previous uniqueness results by Xueliang Li. (C) 2000 Elsevier Science B.V. All rights reserved.
作者：
Takaoka, AsahiKanagawa Univ
Dept Informat Syst Creat Kanagawa Ku Rokkakubashi 3-27-1 Yokohama Kanagawa 2218686 Japan
A simple-triangle graph (also known as a PI graph) is the intersection graph of a family of triangles defined by a point on a horizontal line and an interval on another horizontal line. The recognition problem for sim...
详细信息
A simple-triangle graph (also known as a PI graph) is the intersection graph of a family of triangles defined by a point on a horizontal line and an interval on another horizontal line. The recognition problem for simple-triangle graphs was a longstanding open problem, and recently a polynomial-time algorithm has been given (Mertzios, 2015). Along with the approach of this paper, we show a simpler recognition algorithm for simple-triangle graphs. To do this, we introduce the following problem: given a bipartite graph G and a set F of edges of G, find a 2-chain subgraph cover of G such that one of two chain subgraphs has no edges in F. We show an O(n(2) . min{m, (m) over cap})-time algorithm for this problem, where n and m are the number of vertices and edges of G, respectively, and (m) over cap is the number of non-edges between two independent sets of G. Using this result, we show that the recognition problem for simple-triangle graphs can be solved in O(n(2) . min{m, (m) over bar}) time, where (m) over bar is the number of non-edges of the given graph. (C) 2019 Elsevier B.V. All rights reserved.
暂无评论