nips nips2003 nips2003-168 knowledge-graph by maker-knowledge-mining

168 nips-2003-Salient Boundary Detection using Ratio Contour

Source: pdf

Author: Song Wang, Toshiro Kubota, Jeffrey M. Siskind

Abstract: This paper presents a novel graph-theoretic approach, named ratio contour, to extract perceptually salient boundaries from a set of noisy boundary fragments detected in real images. The boundary saliency is deﬁned using the Gestalt laws of closure, proximity, and continuity. This paper ﬁrst constructs an undirected graph with two different sets of edges: solid edges and dashed edges. The weights of solid and dashed edges measure the local saliency in and between boundary fragments, respectively. Then the most salient boundary is detected by searching for an optimal cycle in this graph with minimum average weight. The proposed approach guarantees the global optimality without introducing any biases related to region area or boundary length. We collect a variety of images for testing the proposed approach with encouraging results. 1

Reference: text

Summary: the most important sentenses genereted by tfidf model

sentIndex sentText sentNum sentScore

1 edu Abstract This paper presents a novel graph-theoretic approach, named ratio contour, to extract perceptually salient boundaries from a set of noisy boundary fragments detected in real images. [sent-7, score-1.364]

2 The boundary saliency is deﬁned using the Gestalt laws of closure, proximity, and continuity. [sent-8, score-0.527]

3 This paper ﬁrst constructs an undirected graph with two different sets of edges: solid edges and dashed edges. [sent-9, score-0.585]

4 The weights of solid and dashed edges measure the local saliency in and between boundary fragments, respectively. [sent-10, score-0.916]

5 Then the most salient boundary is detected by searching for an optimal cycle in this graph with minimum average weight. [sent-11, score-1.004]

6 Those methods usually have difﬁculties in ﬁnding the globally optimal boundaries in terms of the selected saliency deﬁnitions. [sent-22, score-0.388]

7 Recently we have witnessed some advanced methods, like ratio region [5], minimum cut[17], normalized cut [14], globally optimal region/cycle [9], and ratio cut [15], which aim to produce globally optimal boundaries. [sent-23, score-0.357]

8 However, those pixel-grouping based methods usually have difﬁculties in effectively incorporating perceptual rules, such as boundary smoothness, into their saliency deﬁnitions. [sent-24, score-0.508]

9 Instead of operating directly on the image pixels, another class of methods is designed based on some pre-extracted boundary fragments (or for brevity, fragments) 1 , which can be obtained using some standard edge-detection methods like Canny detectors. [sent-25, score-0.676]

10 1(a), although those fragments are disconnected and contain serious noise, they provide abundant information on boundary length, tangent directions, and curvatures, which can greatly facilitate the incorporation of advanced perceptual rules like boundary smoothness. [sent-27, score-0.983]

11 Shashua and Ullman [13] presents a parallel network model for detecting salient boundary based on fragment proximity, boundary length, and boundary smoothness. [sent-28, score-1.29]

12 Elder and Zucker [6] use the shortest-path algorithm to connect fragments to form salient closed boundaries. [sent-31, score-0.791]

13 This paper presents a new graph based approach to extract salient closed boundaries from a set of fragments detected from real images. [sent-33, score-1.143]

14 The boundary saliency is based on the well-known Gestalt laws of closure, proximity, and continuity. [sent-35, score-0.527]

15 To avoid the various biases as in Elder and Zucker [6], this paper deﬁnes the boundary saliency as the average saliency along the whole boundary. [sent-36, score-0.735]

16 We ﬁnally formulate the salient-boundary detection problem into a problem for ﬁnding an optimal cycle in an undirected graph. [sent-37, score-0.374]

17 2 Problem Formulation (a) (b) (c) (d) Figure 1: An illustration of detecting salient boundaries from some fragments. [sent-40, score-0.465]

18 (a) Boundary fragments, (b) salient boundary by connecting some fragments with dashed curves, (c) a solid-dashed graph, and (d) an alternate cycle in (c). [sent-41, score-1.514]

19 The basic primitives in the ratio-contour approach are a set of noisy (boundary) fragments extracted by edge detection. [sent-42, score-0.602]

20 For simplicity, here we assume each detected fragment is a continuous open curve segment with two endpoints, as shown in Fig. [sent-43, score-0.401]

21 Our goal is to identify and connect a subset of fragments to form the most salient structural boundary as shown in Fig. [sent-45, score-0.982]

22 In this paper, we measure the boundary saliency using simple Gestalt laws of closure, proximity, and continuity. [sent-47, score-0.527]

23 The closure means that the salient boundary must be a closed contour. [sent-48, score-0.619]

24 Considering the boundary proximity and the continuity, we deﬁne its 1 Most literatures use the terminology edge instead of fragment. [sent-54, score-0.52]

25 We can see that the un-normalized cost T (B) combines the total gap-length and curvature along the boundary B and has bias to produce a short boundary. [sent-58, score-0.393]

26 The most salient boundary B is then the one with the minimum cost R(B). [sent-60, score-0.582]

27 We can formulate the above cost into an undirected graph G = (V, E) with vertices V = {v1 , v2 , · · · , vn } and edges E = {e1 , e2 , · · · , em }. [sent-62, score-0.393]

28 A unique vertex is constructed from each fragment endpoint. [sent-63, score-0.374]

29 Two different kinds of edges, solid edges and dashed edges, are constructed between vertices. [sent-64, score-0.479]

30 (a) If vi and vj correspond to the two endpoints of the same fragment, we construct a solid edge between vi and vj to model this fragment. [sent-65, score-0.434]

31 (b) Between each possible vertex pair vi and vj , we construct a dashed edge to model the gap or a virtual fragment (dashed curves in Fig. [sent-66, score-0.772]

32 1(c), which is made up of 3 solid edges for three fragments and all 15 possible dashed edges. [sent-69, score-0.878]

33 For clarity, sometimes we call the boundary fragment a real fragment when both real and virtual fragments are involved. [sent-70, score-1.392]

34 The constructed graph always has even number of vertices, as each real fragment has two endpoints. [sent-71, score-0.45]

35 More interestingly, no two solid edges are incident from the same vertex and each vertex has exactly one incident solid edge. [sent-72, score-0.805]

36 We further deﬁne an alternate cycle in a solid-dashed graph as a simple cycle that traverses the solid edges and dashed edges alternately. [sent-74, score-1.436]

37 Examples of a soliddashed graph and an alternate cycle are given in Fig. [sent-75, score-0.517]

38 Since a boundary always traverses real fragments and virtual fragments alternately, it can be described by an alternate cycle. [sent-77, score-1.443]

39 Note that not all the cycles in a solid-dashed graph are alternate cycles, because two adjacent dashed edges can appear sequentially in the same cycle. [sent-78, score-0.705]

40 According to the cost function (1), we deﬁne a weight function w(e) and a length function l(e) for each edge e. [sent-79, score-0.345]

41 For convenience, we deﬁne B(e) as a function that gives the (real or virtual) fragment corresponding to an edge e. [sent-80, score-0.398]

42 We can see that the most salient boundary with minimum cost (1) corresponds to an alternate cycle C with minimum cycle ratio CR(C) = w(e) . [sent-83, score-1.375]

43 e∈C l(e) e∈C Fragments extracted from real images usually contain noise, intersections, and even some closed curves, which cause difﬁculties in estimating the curve length, curvature, and therefore, the edge weight and length. [sent-84, score-0.4]

44 In the following, we ﬁrst present a polynomial-time algorithm to identify the alternate cycle with the minimum cycle ratio CR(C). [sent-86, score-0.793]

45 3 Ratio-Contour Algorithm For simplicity, we denote the alternate cycle with minimum cycle ratio as MRA (Minimum Ratio Alternate) cycle. [sent-87, score-0.793]

46 In this section, we introduce a graph algorithm for ﬁnding the MRA cycle in polynomial time. [sent-88, score-0.368]

47 (a) Both the weight and edge length of the solid edges can be set to zero by merging them into the weight and length of their adjacent dashed edges, without changing the underlying MRA. [sent-90, score-1.061]

48 (b) The problem of ﬁnding an MRA cycle can be reduced to a problem of detecting a negativeweight alternate (NWA) cycle in the same graph. [sent-91, score-0.715]

49 (c) Finding NWA cycles in a solid-dashed graph with zero solid-edge weights and zero solid-edge lengths can be reduced to ﬁnding a minimum-weight perfect matching (MWPM) in the same graph. [sent-92, score-0.428]

50 2(a) and (b), each solid edge e can only be adjacent to a set of dashed edges, say {e1 , e2 , · · · , eK }, in a solid-dashed graph, and no two solid edges are adjacent to each other. [sent-96, score-0.844]

51 Therefore, we can directly merge the solid-edge weight and length to its adjacent dashed edges by w(ek ) ← w(ek ) + w(e) Nk l(ek ) ← l(ek ) + l(e) , k = 1, 2, · · · K, Nk where Nk = 2 if ek shares one vertex with e as in Fig. [sent-97, score-0.764]

52 Then we reset the weight and length of this solid edge to zero, i. [sent-100, score-0.452]

53 While solid and dashed edges are traversed alternately in an alternate cycle, it is not difﬁcult to achieve the following conclusion. [sent-104, score-0.623]

54 1 The above processing of edge weights and edge-lengths does not change the cycle ratio of any alternate cycles. [sent-106, score-0.626]

55 (a) Merging the weight and length of a solid edge to its adjacent dashed edges. [sent-108, score-0.644]

56 (d) Derived cycle from the perfect matching shown in (c). [sent-111, score-0.446]

57 2 The MRA cycle in a solid-dashed graph G = (V, E) is invariant to the following linear transform on the edge weight w(e) ← w(e) − b · l(e), ∀e ∈ E. [sent-115, score-0.63]

58 There always exists an optimal b = b∗ so that after weight transform (2), the MRA cycle has the cycle ratio of zero. [sent-118, score-0.722]

59 In this case, the MRA cycle is the same as the cycle with total edge weight of zero. [sent-119, score-0.793]

60 The detection of the optimal b∗ and the MRA cycle can then be reduced into a problem of ﬁnding the NWA cycle (negative weight alternate cycle). [sent-120, score-0.843]

61 Basically, if we can detect an NWA cycle after the edge weight transform (2), we know b > b∗ . [sent-121, score-0.525]

62 With an NWA cycle detection algorithm, we can use binary or sequential search to locate the optimal b∗ and the desired MRA cycle. [sent-123, score-0.337]

63 1, it is easy to see that the linear transform (2) always preserves zero weight and zero length for all solid edges in this search process. [sent-126, score-0.579]

64 3 Reducing to Minimum Weight Perfect Matching The problem of detecting an NWA cycle in a solid-dashed graph can be reduced to a problem of ﬁnding a minimum weight perfect matching (MWPM) in the same graph. [sent-128, score-0.729]

65 A perfect matching in G denotes a subgraph that contains all the vertices in G while each vertex only has one incident edge. [sent-129, score-0.405]

66 2(c), where three thick edges together with their vertices form a perfect matching. [sent-131, score-0.33]

67 The MWPM is the perfect matching with minimum total edge weight. [sent-132, score-0.4]

68 As all the solid edges form a trivial perfect matching with total weight zero, the MWPM in our solid-dashed graph should have non-positive total weight. [sent-133, score-0.762]

69 We can construct a set of cycles from a perfect matching P by (a) removing from P all the solid edges and their endpoints, and (b) adding to P any solid edges in the solid-dashed graph G whose two endpoints are still in P after the removal in (a). [sent-134, score-1.089]

70 The remaining subgraph must consist of a set of cycles because each remaining vertex has two incident edges: one is solid and the other one is dashed. [sent-135, score-0.393]

71 As all the solid edges have zero weight and zero length, it is not difﬁcult to see that the total weight of the perfect matching is the same as the total weight of the resulting cycles. [sent-139, score-0.905]

72 4 Edge-Weight and Edge-Length Functions We need to estimate the curvature and length of both real and virtual fragments for deﬁning w(e) and l(e) of solid and dashed edges. [sent-142, score-1.022]

73 In this paper, we approximate a fragment by a set of quadratic splines with the parametric form xi (ti ) xi Ai Bi t2 i = + , yi (ti ) yi Ci Di ti where 0 ≤ ti ≤ 1 is the parameter for the spline. [sent-144, score-0.359]

74 3 where solid curves in (a) and (b) are fragments before and after smoothing. [sent-147, score-0.604]

75 However, estimating these quantities for a virtual fragment is not trivial, as no information is given on how the virtual fragment should look like. [sent-150, score-0.712]

76 First, a pair of endpoints involved in forming a particular dashed edge is connected with a straight line. [sent-152, score-0.362]

77 In this smoothed curve segment, the virtual fragment is then the part corresponding to the straight line before the smoothing. [sent-155, score-0.417]

78 3(b) shows a resulting virtual fragment used for estimating curvature, length, and ﬁnally edge weight. [sent-157, score-0.496]

79 (b) Smoothed real fragments and an estimated virtual fragment. [sent-160, score-0.584]

80 (d) Smoothed fragments after breaking undesired connections, corresponding to the portion of the box in (c). [sent-162, score-0.469]

81 In real implementation, another issue is that the detected fragments using edge detectors may not be disjoint open curves as assumed in Section 2. [sent-164, score-0.742]

82 It is common that some fragments are connected in the form of intersections, attachments, and even undesired closure, as shown in Fig. [sent-165, score-0.469]

83 In the constructed graph, they (u1 , u2 , and u3 ) are connected by dashed edges with zero weight and zero length. [sent-171, score-0.498]

84 Attachment speciﬁes the case where two fragments are undesirably connected into a single fragment as shown in Fig. [sent-172, score-0.693]

85 This greatly hurts the reliability of salient boundary detection as those attached fragments may exclude many desired dashed edges from the graph. [sent-174, score-1.327]

86 We alleviate this problem by splitting all the fragments at their high-curvature points, as illustrated in Figs. [sent-175, score-0.435]

87 Similarly, we can break closed fragments into open fragments at high-curvature points, as shown in Fig. [sent-177, score-0.92]

88 5 Experiments and Discussion In this section, we test the proposed ratio-contour algorithm to extract the salient boundaries from real images. [sent-182, score-0.471]

89 For initial fragment detection, we use the standard Canny edge detector in the Matlab software with its default threshold settings. [sent-183, score-0.398]

90 In the implementation, for each vertex, we only keep certain number of incident dashed edges with smallest length. [sent-187, score-0.406]

91 B(e 2) B(e 2) B(e 3) B(e 3) B(e 1) B(e 1) u2 e3 (d) u2 e2 u3 e1 (c) (b) (a) u1 B(e 1) e2 u1 e3 e1 u1 e1 u2 (f) (e) Figure 4: An illustration of fragment identiﬁcation and graph construction in some special cases. [sent-188, score-0.398]

92 (a), (b), and (c) show the detected fragments with intersections, attachments, and closures. [sent-189, score-0.517]

93 Figure 5 shows salient boundaries detected from seven real images, together with the initial fragments from Canny detector. [sent-193, score-0.958]

94 Each subﬁgure from (a) to (g) contains three images, left: original images, middle: Canny detection results, and right: the detected most salient boundaries. [sent-196, score-0.425]

95 6 Conclusions We have presented a novel graph-theoretic approach, named ratio contour, for extracting perceptually salient boundaries from a set of noisy boundary fragments detected in real images. [sent-197, score-1.363]

96 The approach guarantees the global optimality without introducing any biases re- lated to region area or boundary length, and exhibits promising performance in extracting salient objects from real cluttered images. [sent-198, score-0.676]

97 One potential extension of this research is to extract multiple salient objects that are overlapped or share part of boundaries by performing ratio-contour algorithm iteratively. [sent-199, score-0.42]

98 Extracting salient contours from images: An analysis of the saliency network. [sent-215, score-0.537]

99 Segmentation of multiple salient closed contours from real images. [sent-270, score-0.406]

100 Structural saliency: The detection of globallly salient structures using a locally connected network. [sent-280, score-0.343]

similar papers computed by tfidf model

tfidf for this paper:

wordName wordTfidf (topN-words)

[('fragments', 0.435), ('salient', 0.269), ('cycle', 0.263), ('fragment', 0.258), ('boundary', 0.241), ('saliency', 0.232), ('edges', 0.179), ('mra', 0.176), ('alternate', 0.149), ('edge', 0.14), ('proximity', 0.139), ('nwa', 0.137), ('solid', 0.135), ('dashed', 0.129), ('boundaries', 0.121), ('mwpm', 0.117), ('ek', 0.109), ('perfect', 0.107), ('graph', 0.105), ('virtual', 0.098), ('canny', 0.098), ('incident', 0.098), ('weight', 0.094), ('endpoints', 0.093), ('curvature', 0.091), ('length', 0.083), ('detected', 0.082), ('vertex', 0.08), ('cycles', 0.08), ('matching', 0.076), ('detection', 0.074), ('ratio', 0.074), ('gestalt', 0.068), ('contour', 0.065), ('adjacent', 0.063), ('closure', 0.059), ('laws', 0.054), ('real', 0.051), ('elder', 0.051), ('closed', 0.05), ('nk', 0.047), ('bi', 0.046), ('dt', 0.045), ('minimum', 0.044), ('vertices', 0.044), ('intersections', 0.043), ('vision', 0.042), ('detecting', 0.04), ('nding', 0.039), ('sarkar', 0.039), ('thornber', 0.039), ('zucker', 0.039), ('undirected', 0.037), ('connect', 0.037), ('constructed', 0.036), ('images', 0.036), ('contours', 0.036), ('globally', 0.035), ('ti', 0.035), ('perceptual', 0.035), ('illustration', 0.035), ('guy', 0.034), ('undesired', 0.034), ('amir', 0.034), ('attachments', 0.034), ('shashua', 0.034), ('kubota', 0.034), ('traverses', 0.034), ('perceptually', 0.034), ('curves', 0.034), ('intelligence', 0.034), ('total', 0.033), ('continuity', 0.033), ('vj', 0.033), ('transactions', 0.033), ('cut', 0.032), ('smoothed', 0.032), ('segment', 0.032), ('pattern', 0.031), ('advanced', 0.031), ('merging', 0.031), ('alternately', 0.031), ('splines', 0.031), ('di', 0.03), ('zero', 0.03), ('biases', 0.03), ('extract', 0.03), ('curve', 0.029), ('williams', 0.029), ('cluttered', 0.029), ('jacobs', 0.029), ('culties', 0.029), ('extracting', 0.029), ('cost', 0.028), ('transform', 0.028), ('connecting', 0.028), ('smoothing', 0.028), ('shares', 0.027), ('optimality', 0.027), ('noisy', 0.027)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.99999958 168 nips-2003-Salient Boundary Detection using Ratio Contour

Author: Song Wang, Toshiro Kubota, Jeffrey M. Siskind

2 0.088787623 50 nips-2003-Denoising and Untangling Graphs Using Degree Priors

Author: Quaid D. Morris, Brendan J. Frey

Abstract: This paper addresses the problem of untangling hidden graphs from a set of noisy detections of undirected edges. We present a model of the generation of the observed graph that includes degree-based structure priors on the hidden graphs. Exact inference in the model is intractable; we present an eﬃcient approximate inference algorithm to compute edge appearance posteriors. We evaluate our model and algorithm on a biological graph inference problem. 1 Introduction and motivation The inference of hidden graphs from noisy edge appearance data is an important problem with obvious practical application. For example, biologists are currently building networks of all the physical protein-protein interactions (PPI) that occur in particular organisms. The importance of this enterprise is commensurate with its scale: a completed network would be as valuable as a completed genome sequence, and because each organism contains thousands of diﬀerent types of proteins, there are millions of possible types of interactions. However, scalable experimental methods for detecting interactions are noisy, generating many false detections. Motivated by this application, we formulate the general problem of inferring hidden graphs as probabilistic inference in a graphical model, and we introduce an eﬃcient algorithm that approximates the posterior probability that an edge is present. In our model, a set of hidden, constituent graphs are combined to generate the observed graph. Each hidden graph is independently sampled from a prior on graph structure. The combination mechanism acts independently on each edge but can be either stochastic or deterministic. Figure 1 shows an example of our generative model. Typically one of the hidden graphs represents the graph of interest (the true graph), the others represent diﬀerent types of observation noise. Independent edge noise may also be added by the combination mechanism. We use probabilistic inference to compute a likely decomposition of the observed graph into its constituent parts. This process is deemed “untangling”. We use the term “denoising” to refer to the special case where the edge noise is independent. In denoising there is a single hidden graph, the true graph, and all edge noise in the observed graph is due E1 1 eij E2 i 2 eij j xij i j i j X Figure 1: Illustrative generative model example. Figure shows an example where an observed graph, X, is a noisy composition of two constituent graphs, E 1 and E 2 . All graphs share the same vertex set, so each can be represented by a symmetric matrix of random binary variables (i.e., an adjacency matrix). This generative model is designed to solve a toy counter-espionage problem. The vertices represent suspects and each edge in X represents an observed call between two suspects. The graph X reﬂects zero or more spy rings (represented by E 1 ), telemarketing calls (represented by E 2 ), social calls (independent edge noise), and lost call records (more independent edge noise). The task is to locate any spy rings hidden in X. We model the distribution of spy ring graphs using a prior, P (E 1 ), that has support only on graphs where all vertices have degree of either 2 (i.e., are in the ring) or 0 (i.e., are not). Graphs of telemarketing call patterns are represented using a prior, P (E 2 ), under which all nodes have degrees of > 3 (i.e., are telemarketers), 1 (i.e., are telemarketees), or 0 (i.e., are neither). The displayed hidden graphs are one likely untangling of X. to the combination mechanism. Prior distributions over graphs can be speciﬁed in various ways, but our choice is motivated by problems we want to solve, and by a view to deriving an eﬃcient inference algorithm. One compact representation of a distribution over graphs consists of specifying a distribution over vertex degrees, and assuming that graphs that have the same vertex degrees are equiprobable. Such a prior can model quite rich distributions over graphs. These degree-based structure priors are natural representions of graph structure; many classes of real-world networks have a characteristic functional form associated with their degree distributions [1], and sometimes this form can be predicted using knowledge about the domain (see, e.g., [2]) or detected empirically (see, e.g., [3, 4]). As such, our model incorporates degree-based structure priors. Though exact inference in our model is intractable in general, we present an eﬃcient algorithm for approximate inference for arbitrary degree distributions. We evaluate our model and algorithm using the real-world example of untangling yeast proteinprotein interaction networks. 2 A model of noisy and tangled graphs For degree-based structure priors, inference consists of searching over vertex degrees and edge instantiations, while comparing each edge with its noisy observation and enforcing the constraint that the number of edges connected to every vertex must equal the degree of the vertex. Our formulation of the problem in this way is inspired by the success of the sum-product algorithm (loopy belief propagation) for solving similar formulations of problems in error-correcting decoding [6, 7], phase unwrapping [8], and random satisﬁability [9]. For example, in error-correcting decoding, inference consists of searching over conﬁgurations of codeword bits, while comparing each bit with its noisy observation and enforcing parity-check constraints on subsets of bits [10]. For a graph on a set of N vertices, eij is a variable that indicates the presence of an edge connecting vertices i and j: eij = 1 if there is an edge, and eij = 0 otherwise. We assume the vertex set is ﬁxed, so each graph is speciﬁed by an adjacency matrix, E = {eij }N . The degree of vertex i is denoted by di and the i,j=1 degree set by D = {di }N . The observations are given by a noisy adjacency matrix, i=1 X = {xij }N . Generally, edges can be directed, but in this paper we focus on i,j=1 undirected graphs, so eij = eji and xij = xji . Assuming the observation noise is independent for diﬀerent edges, the joint distribution is P (X, E, D) = P (X|E)P (E, D) = P (xij |eij ) P (E, D). j≥i P (xij |eij ) models the edge observation noise. We use an undirected model for the joint distribution over edges and degrees, P (E, D), where the prior distribution over di is determined by a non-negative potential fi (di ). Assuming graphs that have the same vertex degrees are equiprobable, we have N eij ) , fi (di )I(di , P (E, D) ∝ i j=1 where I(a, b) = 1 if a = b, and I(a, b) = 0 if a = b. The term I(di , j eij ) ensures that the number of edges connected to vertex i is equal to di . It is straightforward to show that the marginal distribution over di is P (di ) ∝ fi (di ) D\di nD j=i fj (dj ) , where nD is the number of graphs with degrees D and the sum is over all degree variables except di . The potentials, fi , can be estimated from a given degree prior using Markov chain Monte Carlo; or, as an approximation, they can be set to an empirical degree distribution obtained from noise-free graphs. Fig 2a shows the factor graph [11] for the above model. Each ﬁlled square corresponds to a term in the factorization of the joint distribution and the square is connected to all variables on which the term depends. Factor graphs are graphical models that unify the properties of Bayesian networks and Markov random ﬁelds [12]. Many inference algorithms, including the sum-product algorithm (a.k.a. loopy belief propagation), are more easily derived using factor graphs than Bayesian networks or Markov random ﬁelds. We describe the sum-product algorithm for our model in section 3. (a) I(d ,e + e +e +e 4 14 24 34 44 d1 e11 e12 e14 4 d3 d2 e13 f 4(d ) e22 e23 e24 (b) ) d1 d4 e33 e34 e1 e44 11 x11 x11 x12 x13 x14 x22 x23 x24 x33 d1 1 x34 x44 e2 11 e1 12 x12 e2 12 d1 2 e1 13 e1 e2 13 e1 14 x13 e1 22 x14 e2 14 d1 3 23 x22 e2 22 x23 e2 23 4 e1 e1 24 e2 24 e1 33 x24 34 x33 e2 33 x34 e2 34 e1 44 x44 e2 44 P( x44 | e44 ) (c) d4 s41 e14 e24 d2 1 d4 e34 e44 e14 s42 e24 s43 e34 d2 2 d2 3 d2 4 s44 P( x e44 44 1 ,e 2 ) 44 44 |e Figure 2: (a) A factor graph that describes a distribution over graphs with vertex degrees di , binary edge indicator variables eij , and noisy edge observations xij . The indicator function I(di , j eij ) enforces the constraint that the sum of the binary edge indicator variables for vertex i must equal the degree of vertex i. (b) A factor graph that explains noisy observed edges as a combination of two constituent graphs, with edge indicator variables e 1 and e2 . ij ij (c) The constraint I(di , j eij ) can be implemented using a chain with state variables, which leads to an exponentially faster message-passing algorithm. 2.1 Combining multiple graphs The above model is suitable when we want to infer a graph that matches a degree prior, assuming the edge observation noise is independent. A more challenging goal, with practical application, is to infer multiple hidden graphs that combine to explain the observed edge data. In section 4, we show how priors over multiple hidden graphs can be be used to infer protein-protein interactions. When there are H hidden graphs, each constituent graph is speciﬁed by a set of edges on the same set of N common vertices. For the degree variables and edge variables, we use a superscript to indicate which hidden graph the variable is used to describe. Assuming the graphs are independent, the joint distribution over the observed edge data X, and the edge variables and degree variables for the hidden graphs, E 1 , D1 , . . . , E H , DH , is H P (X, E 1 , D1 , . . . , E H , DH ) = P (xij |e1 , . . . , eH ) ij ij j≥i P (E h , Dh ), (1) h=1 where for each hidden graph, P (E h , Dh ) is modeled as described above. Here, the likelihood P (xij |e1 , . . . , eH ) describes how the edges in the hidden graphs combine ij ij to model the observed edge. Figure 2b shows the factor graph for this model. 3 Probabilistic inference of constituent graphs Exact probabilistic inference in the above models is intractable, here we introduce an approximate inference algorithm that consists of applying the sum-product algorithm, while ignoring cycles in the factor graph. Although the sum-product algorithm has been used to obtain excellent results on several problems [6, 7, 13, 14, 8, 9], we have found that the algorithm works best when the model consists of uncertain observations of variables that are subject to a large number of hard constraints. Thus the formulation of the model described above. Conceptually, our inference algorithm is a straight-forward application of the sumproduct algorithm, c.f. [15], where messages are passed along edges in the factor graph iteratively, and then combined at variables to obtain estimates of posterior probabilities. However, direct implementation of the message-passing updates will lead to an intractable algorithm. In particular, direct implementation of the update for the message sent from function I(di , j eij ) to edge variable eik takes a number of scalar operations that is exponential in the number of vertices. Fortunately there exists a more eﬃcient way to compute these messages. 3.1 Eﬃciently summing over edge conﬁgurations The function I(di , j eij ) ensures that the number of edges connected to vertex i is equal to di . Passing messages through this function requires summing over all edge conﬁgurations that correspond to each possible degree, di , and summing over di . Speciﬁcally, the message, µIi →eik (eik ), sent from function I(di , j eij ) to edge variable eik is given by I(di , di {eij | j=1,...,N, j=k} eij ) j µeij →Ii (eij ) , j=k where µeij →Ii (eij ) is the message sent from eij to function I(di , j eij ). The sum over {eij | j = 1, . . . , N, j = k} contains 2N −1 terms, so direct computation is intractable. However, for a maximum degree of dmax , all messages departing from the function I(di , j eij ) can be computed using order dmax N binary scalar operations, by introducing integer state variables sij . We deﬁne sij = n≤j ein and note that, by recursion, sij = sij−1 + eij , where si0 = 0 and 0 ≤ sij ≤ dmax . This recursive expression enables us to write the high-complexity constraint as the sum of a product of low-complexity constraints, N I(di , eij ) = j I(si1 , ei1 ) {sij | j=1,...,N } I(sij , sij−1 + eij ) I(di , siN ). j=2 This summation can be performed using the forward-backward algorithm. In the factor graph, the summation can be implemented by replacing the function I(di , j eij ) with a chain of lower-complexity functions, connected as shown in Fig. 2c. The function vertex (ﬁlled square) on the far left corresponds to I(si1 , ei1 ) and the function vertex in the upper right corresponds to I(di , siN ). So, messages can be passed through each constraint function I(di , j eij ) in an eﬃcient manner, by performing a single forward-backward pass in the corresponding chain. 4 Results We evaluate our model using yeast protein-protein interaction (PPI) data compiled by [16]. These data include eight sets of putative, but noisy, interactions derived from various sources, and one gold-standard set of interactions detected by reliable experiments. Using the ∼ 6300 yeast proteins as vertices, we represent the eight sets of putative m interactions using adjacency matrices {Y m }8 m=1 where yij = 1 if and only if putative interaction dataset m contains an interaction between proteins i and j. We similarly use Y gold to represent the gold-standard interactions. m We construct an observed graph, X, by setting xij = maxm yij for all i and j, thus the observed edge set is the union of all the putative edge sets. We test our model (a) (b) 40 0 untangling baseline random empirical potential posterior −2 30 log Pr true positives (%) 50 20 10 −4 −6 −8 0 0 5 10 −10 0 false positives (%) 10 20 30 degree (# of nodes) Figure 3: Protein-protein interaction network untangling results. (a) ROC curves measuring performance of predicting e1 when xij = 1. (b) Degree distributions. Compares the empirical ij degree distribution of the test set subgraph of E 1 to the degree potential f 1 estimated on the ˆ ij training set subgraph of E 1 and to the distribution of di = j pij where pij = P (e1 = 1|X) is estimated by untangling. on the task of discerning which of the edges in X are also in Y gold . We formalize this problem as that of decomposing X into two constituent graphs E 1 and E 2 , the gold true and the noise graphs respectively, such that e1 = xij yij and e2 = xij − e1 . ij ij ij We use a training set to ﬁt our model parameters and then measure task performance on a test set. The training set contains a randomly selected half of the ∼ 6300 yeast proteins, and the subgraphs of E 1 , E 2 , and X restricted to those vertices. The test contains the other half of the proteins and the corresponding subgraphs. Note that interactions connecting test set proteins to training set proteins (and vice versa) are ignored. We ﬁt three sets of parameters: a set of Naive Bayes parameters that deﬁne a set of edge-speciﬁc likelihood functions, Pij (xij |e1 , e2 ), one degree potential, f 1 , which ij ij is the same for every vertex in E1 and deﬁnes the prior P (E 1 ), and a second, f 2 , that similarly deﬁnes the prior P (E 2 ). The likelihood functions, Pij , are used to both assign likelihoods and enforce problem constraints. Given our problem deﬁnition, if xij = 0 then e1 = e2 = 0, ij ij otherwise xij = 1 and e1 = 1 − e2 . We enforce the former constraint by setij ij ting Pij (xij = 0|e1 , e2 ) = (1 − e1 )(1 − e2 ), and the latter by setting Pij (xij = ij ij ij ij 1|e1 , e2 ) = 0 whenever e1 = e2 . This construction of Pij simpliﬁes the calculation ij ij ij ij of the µPij →eh messages and improves the computational eﬃciency of inference beij cause when xij = 0, we need never update messages to and from variables e1 and ij e2 . We complete the speciﬁcation of Pij (xij = 1|e1 , e2 ) as follows: ij ij ij ym Pij (xij = 1|e1 , e2 ) ij ij = m ij θm (1 − θm )1−yij , if e1 = 1 and e2 = 0, ij ij ym m ij ψm (1 − ψm )1−yij , if e1 = 0 and e2 = 1. ij ij where {θm } and {ψm } are naive Bayes parameters, θm = i,j m yij e1 / ij i,j e1 and ij ψm = i,j m yij e2 / ij i,j e2 , respectively. ij The degree potentials f 1 (d) and f 2 (d) are kernel density estimates ﬁt to the degree distribution of the training set subgraphs of E 1 and E 2 , respectively. We use Gaussian kernels and set the width parameter (standard deviation) σ using leaveone-out cross-validation to maximize the total log density of the held-out datapoints. Each datapoint is the degree of a single vertex. Both degree potentials closely followed the training set empirical degree distributions. Untangling was done on the test set subgraph of X. We initially set the µ Pij →e1 ij messages equal to the likelihood function Pij and we randomly initialized the 1 µIj →e1 messages with samples from a normal distribution with mean 0 and variij ance 0.01. We then performed 40 iterations of the following message update order: 2 2 1 1 µe1 →Ij , µIj →e1 , µe1 →Pij , µPij →e2 , µe2 →Ij , µIj →e2 , µe2 →Pij , µPij →e1 . ij ij ij ij ij ij ij ij We evaluated our untangling algorithm using an ROC curve by comparing the actual ˆ test set subgraph of E 1 to posterior marginal probabilities,P (e1 = 1|X), estimated ij by our sum-product algorithm. Note that because the true interaction network is sparse (less than 0.2% of the 1.8 × 107 possible interactions are likely present [16]) and, in this case, true positive predictions are of greater biological interest than true negative predictions, we focus on low false positive rate portions of the ROC curve. Figure 3a compares the performance of a classiﬁer for e1 based on thresholding ij ˆ P (eij = 1|X) to a baseline method based on thresholding the likelihood functions, Pij (xij = 1|e1 = 1, e2 = 0). Note because e1 = 0 whenever xij = 0, we exclude ij ij ij the xij = 0 cases from our performance evaluation. The ROC curve shows that for the same low false positive rate, untangling produces 50% − 100% more true positives than the baseline method. Figure 3b shows that the degree potential, the true degree distribution, and the predicted degree distribution are all comparable. The slight overprediction of the true degree distribution may result because the degree potential f 1 that deﬁnes P (E 1 ) is not equal to the expected degree distribution of graphs sampled from the distribution P (E 1 ). 5 Summary and Related Work Related work includes other algorithms for structure-based graph denoising [17, 18]. These algorithms use structural properties of the observed graph to score edges and rely on the true graph having a surprisingly large number of three (or four) edge cycles compared to the noise graph. In contrast, we place graph generation in a probabilistic framework; our algorithm computes structural ﬁt in the hidden graph, where this computation is not aﬀected by the noise graph(s); and we allow for multiple sources of observation noise, each with its own structural properties. After submitting this paper to the NIPS conference, we discovered [19], in which a degree-based graph structure prior is used to denoise (but not untangle) observed graphs. This paper addresses denoising in directed graphs as well as undirected graphs, however, the prior that they use is not amenable to deriving an eﬃcient sumproduct algorithm. Instead, they use Markov Chain Monte Carlo to do approximate inference in a hidden graph containing 40 vertices. It is not clear how well this approach scales to the ∼ 3000 vertex graphs that we are using. In summary, the contributions of the work described in this paper include: a general formulation of the problem of graph untangling as inference in a factor graph; an eﬃcient approximate inference algorithm for a rich class of degree-based structure priors; and a set of reliability scores (i.e., edge posteriors) for interactions from a current version of the yeast protein-protein interaction network. References [1] A L Barabasi and R Albert. Emergence of scaling in random networks. Science, 286(5439), October 1999. [2] A Rzhetsky and S M Gomez. Birth of scale-free molecular networks and the number of distinct dna and protein domains per genome. Bioinformatics, pages 988–96, 2001. [3] M Faloutsos, P Faloutsos, and C Faloutsos. On power-law relationships of the Internet topology. Computer Communications Review, 29, 1999. [4] Hawoong Jeong, B Tombor, R´ka Albert, Z N Oltvai, and Albert-L´szl´ Barab´si. e a o a The large-scale organization of metabolic networks. Nature, 407, October 2000. [5] J. Pearl. Probabilistic Reasoning in Intelligent Systems. Morgan Kaufmann, San Mateo CA., 1988. [6] D. J. C. MacKay and R. M. Neal. Near Shannon limit performance of low density parity check codes. Electronics Letters, 32(18):1645–1646, August 1996. Reprinted in Electronics Letters, vol. 33, March 1997, 457–458. [7] B. J. Frey and F. R. Kschischang. Probability propagation and iterative decoding. In Proceedings of the 1996 Allerton Conference on Communication, Control and Computing, 1996. [8] B. J. Frey, R. Koetter, and N. Petrovic. Very loopy belief propagation for unwrapping phase images. In 2001 Conference on Advances in Neural Information Processing Systems, Volume 14. MIT Press, 2002. [9] M. M´zard, G. Parisi, and R. Zecchina. Analytic and algorithmic solution of random e satisﬁability problems. Science, 297:812–815, 2002. [10] B. J. Frey and D. J. C. MacKay. Trellis-constrained codes. In Proceedings of the 35 th Allerton Conference on Communication, Control and Computing 1997, 1998. [11] F. R. Kschischang, B. J. Frey, and H.-A. Loeliger. Factor graphs and the sum-product algorithm. IEEE Transactions on Information Theory, Special Issue on Codes on Graphs and Iterative Algorithms, 47(2):498–519, February 2001. [12] B. J. Frey. Factor graphs: A uniﬁcation of directed and undirected graphical models. University of Toronto Technical Report PSI-2003-02, 2003. [13] Kevin P. Murphy, Yair Weiss, and Michael I. Jordan. Loopy belief propagation for approximate inference: An empirical study. In Uncertainty in Artiﬁcial Intelligence 1999. Stockholm, Sweden, 1999. [14] W. Freeman and E. Pasztor. Learning low-level vision. In Proceedings of the International Conference on Computer Vision, pages 1182–1189, 1999. [15] M. I. Jordan. An Inroduction to Learning in Graphical Models. 2004. In preparation. [16] C von Mering et al. Comparative assessment of large-scale data sets of protein-protein interactions. Nature, 2002. [17] R Saito, H Suzuki, and Y Hayashizaki. Construction of reliable protein-protein interaction networks with a new interaction generality measure. Bioinformatics, pages 756–63, 2003. [18] D S Goldberg and F P Roth. Assessing experimentally derived interactions in a small world. Proceedings of the National Academy of Science, 2003. [19] S M Gomez and A Rzhetsky. Towards the prediction of complete protein–protein interaction networks. In Paciﬁc Symposium on Biocomputing, pages 413–24, 2002.

3 0.083468862 85 nips-2003-Human and Ideal Observers for Detecting Image Curves

Author: Fang Fang, Daniel Kersten, Paul R. Schrater, Alan L. Yuille

Abstract: This paper compares the ability of human observers to detect target image curves with that of an ideal observer. The target curves are sampled from a generative model which speciﬁes (probabilistically) the geometry and local intensity properties of the curve. The ideal observer performs Bayesian inference on the generative model using MAP estimation. Varying the probability model for the curve geometry enables us investigate whether human performance is best for target curves that obey speciﬁc shape statistics, in particular those observed on natural shapes. Experiments are performed with data on both rectangular and hexagonal lattices. Our results show that human observers’ performance approaches that of the ideal observer and are, in general, closest to the ideal for conditions where the target curve tends to be straight or similar to natural statistics on curves. This suggests a bias of human observers towards straight curves and natural statistics.

4 0.071044654 121 nips-2003-Log-Linear Models for Label Ranking

Author: Ofer Dekel, Yoram Singer, Christopher D. Manning

Abstract: Label ranking is the task of inferring a total order over a predeﬁned set of labels for each given instance. We present a general framework for batch learning of label ranking functions from supervised data. We assume that each instance in the training data is associated with a list of preferences over the label-set, however we do not assume that this list is either complete or consistent. This enables us to accommodate a variety of ranking problems. In contrast to the general form of the supervision, our goal is to learn a ranking function that induces a total order over the entire set of labels. Special cases of our setting are multilabel categorization and hierarchical classiﬁcation. We present a general boosting-based learning algorithm for the label ranking problem and prove a lower bound on the progress of each boosting iteration. The applicability of our approach is demonstrated with a set of experiments on a large-scale text corpus. 1

5 0.066582769 152 nips-2003-Pairwise Clustering and Graphical Models

Author: Noam Shental, Assaf Zomet, Tomer Hertz, Yair Weiss

Abstract: Signiﬁcant progress in clustering has been achieved by algorithms that are based on pairwise afﬁnities between the datapoints. In particular, spectral clustering methods have the advantage of being able to divide arbitrarily shaped clusters and are based on efﬁcient eigenvector calculations. However, spectral methods lack a straightforward probabilistic interpretation which makes it difﬁcult to automatically set parameters using training data. In this paper we use the previously proposed typical cut framework for pairwise clustering. We show an equivalence between calculating the typical cut and inference in an undirected graphical model. We show that for clustering problems with hundreds of datapoints exact inference may still be possible. For more complicated datasets, we show that loopy belief propagation (BP) and generalized belief propagation (GBP) can give excellent results on challenging clustering problems. We also use graphical models to derive a learning algorithm for afﬁnity matrices based on labeled data. 1

6 0.066563442 30 nips-2003-Approximability of Probability Distributions

7 0.063714974 11 nips-2003-A Mixed-Signal VLSI for Real-Time Generation of Edge-Based Image Vectors

8 0.061018191 134 nips-2003-Near-Minimax Optimal Classification with Dyadic Classification Trees

9 0.059976019 88 nips-2003-Image Reconstruction by Linear Programming

10 0.057987116 191 nips-2003-Unsupervised Context Sensitive Language Acquisition from a Large Corpus

11 0.056210637 133 nips-2003-Mutual Boosting for Contextual Inference

12 0.053498626 109 nips-2003-Learning a Rare Event Detection Cascade by Direct Feature Selection

13 0.053174134 143 nips-2003-On the Dynamics of Boosting

14 0.050279047 96 nips-2003-Invariant Pattern Recognition by Semi-Definite Programming Machines

15 0.049267221 192 nips-2003-Using the Forest to See the Trees: A Graphical Model Relating Features, Objects, and Scenes

16 0.048328698 79 nips-2003-Gene Expression Clustering with Functional Mixture Models

17 0.047613401 104 nips-2003-Learning Curves for Stochastic Gradient Descent in Linear Feedforward Networks

18 0.0471211 81 nips-2003-Geometric Analysis of Constrained Curves

19 0.046830881 128 nips-2003-Minimax Embeddings

20 0.045690689 43 nips-2003-Bounded Invariance and the Formation of Place Fields

similar papers computed by lsi model

lsi for this paper:

topicId topicWeight

[(0, -0.148), (1, -0.036), (2, 0.024), (3, 0.012), (4, -0.073), (5, -0.093), (6, -0.03), (7, -0.015), (8, -0.008), (9, -0.063), (10, 0.01), (11, 0.016), (12, 0.038), (13, -0.014), (14, -0.021), (15, -0.086), (16, -0.07), (17, -0.118), (18, 0.004), (19, 0.073), (20, -0.019), (21, -0.091), (22, -0.057), (23, -0.044), (24, -0.102), (25, -0.013), (26, 0.1), (27, 0.041), (28, -0.123), (29, 0.115), (30, -0.092), (31, -0.021), (32, 0.024), (33, 0.026), (34, -0.039), (35, -0.137), (36, -0.104), (37, -0.004), (38, -0.021), (39, -0.02), (40, -0.004), (41, 0.101), (42, 0.026), (43, -0.165), (44, -0.088), (45, -0.081), (46, 0.066), (47, 0.175), (48, -0.004), (49, 0.06)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.97718388 168 nips-2003-Salient Boundary Detection using Ratio Contour

Author: Song Wang, Toshiro Kubota, Jeffrey M. Siskind

2 0.6418227 50 nips-2003-Denoising and Untangling Graphs Using Degree Priors

Author: Quaid D. Morris, Brendan J. Frey

3 0.60027599 30 nips-2003-Approximability of Probability Distributions

Author: Alina Beygelzimer, Irina Rish

Abstract: We consider the question of how well a given distribution can be approximated with probabilistic graphical models. We introduce a new parameter, effective treewidth, that captures the degree of approximability as a tradeoff between the accuracy and the complexity of approximation. We present a simple approach to analyzing achievable tradeoffs that exploits the threshold behavior of monotone graph properties, and provide experimental results that support the approach. 1

4 0.56294227 85 nips-2003-Human and Ideal Observers for Detecting Image Curves

Author: Fang Fang, Daniel Kersten, Paul R. Schrater, Alan L. Yuille

5 0.39883351 11 nips-2003-A Mixed-Signal VLSI for Real-Time Generation of Edge-Based Image Vectors

Author: Masakazu Yagi, Hideo Yamasaki, Tadashi Shibata

Abstract: A mixed-signal image filtering VLSI has been developed aiming at real-time generation of edge-based image vectors for robust image recognition. A four-stage asynchronous median detection architecture based on analog digital mixed-signal circuits has been introduced to determine the threshold value of edge detection, the key processing parameter in vector generation. As a result, a fully seamless pipeline processing from threshold detection to edge feature map generation has been established. A prototype chip was designed in a 0.35-µm double-polysilicon three-metal-layer CMOS technology and the concept was verified by the fabricated chip. The chip generates a 64-dimension feature vector from a 64x64-pixel gray scale image every 80µsec. This is about 104 times faster than the software computation, making a real-time image recognition system feasible. 1 In tro du c ti o n The development of human-like image recognition systems is a key issue in information technology. However, a number of algorithms developed for robust image recognition so far [1]-[3] are mostly implemented as software systems running on general-purpose computers. Since the algorithms are generally complex and include a lot of floating point operations, they are computationally too expensive to build real-time systems. Development of hardware-friendly algorithms and their direct VLSI implementation would be a promising solution for real-time response systems. Being inspired by the biological principle that edge information is firstly detected in the visual cortex, we have developed an edge-based image representation algorithm compatible to hardware processing. In this algorithm, multiple-direction edges extracted from an original gray scale image is utilized to form a feature vector. Since the spatial distribution of principal edges is represented by a vector, it was named Projected Principal-Edge Distribution (PPED) [4],[5], or formerly called Principal Axis Projection (PAP) [6],[7]. (The algorithm is explained later.) Since the PPED vectors very well represent the human perception of similarity among images, robust image recognition systems have been developed using PPED vectors in conjunction with the analog soft pattern classifier [4],[8], the digital VQ (Vector Quantization) processor [9], and support vector machines [10] . The robust nature of PPED representation is demonstrated in Fig. 1, where the system was applied to cephalometric landmark identification (identifying specific anatomical landmarks on medical radiographs) as an example, one of the most important clinical practices of expert dentists in orthodontics [6],[7]. Typical X-ray images to be experienced by apprentice doctors were converted to PPED vectors and utilized as templates for vector matching. The system performance has been proven for 250 head film samples regarding the fundamental 26 landmarks [11]. Important to note is the successful detection of the landmark on the soft tissue boundary (the tip of the lower lip) shown in Fig. 1(c). Landmarks on soft tissues are very difficult to detect as compared to landmarks on hard tissues (solid bones) because only faint images are captured on radiographs. The successful detection is due to the median algorithm that determines the threshold value for edge detection. Sella Nasion Orbitale By our system (a) By expert dentists Landmark on soft tissue (b) (c) Fig. 1: Image recognition using PPED vectors: (a,b) cephalometric landmark identification; (c) successful landmark detection on soft tissue. We have adopted the median value of spatial variance of luminance within the filtering kernel (5x5 pixels), which allows us to extract all essential features in a delicate gray scale image. However, the problem is the high computational cost in determining the median value. It takes about 0.6 sec to generate one PPED vector from a 64x64-pixel image (a standard image size for recognition in our system) on a SUN workstation, making real time processing unrealistic. About 90% of the computation time is for edge detection from an input image, in which most of the time is spent for median detection. Then the purpose of this work is to develop a new architecture median-filter VLSI subsystem for real-time PPED-vector generation. Special attention has been paid to realize a fully seamless pipeline processing from threshold detection to edge feature map generation by employing the four-stage asynchronous median detection architecture. 2 P r o je c t e d P r i n c i pa l E dg e Dis tribution (PPED ) Projected Principal Edge Distribution (PPED) algorithm [5],[6] is briefly explained using Fig. 2(a). A 5x5-pixel block taken from a 64x64-pixel target image is subjected to edge detection filtering in four principal directions, i.e. horizontal, vertical, and ±45-degree directions. In the figure, horizontal edge filtering is shown as an example. (The filtering kernels used for edge detection are given in Fig. 2(b).) In order to determine the threshold value for edge detection, all the absolute-value differences between two neighboring pixels are calculated in both vertical and horizontal directions and the median value is taken as the threshold. By scanning the 5x5-pixel filtering kernels in the target image, four 64x64 edge-flag maps are generated, which are called feature maps. In the horizontal feature map, for example, edge flags in every four rows are accumulated and spatial distribution of edge flags are represented by a histogram having 16 elements. Similar procedures are applied to other three directions to form respective histograms each having 16 elements. Finally, a 64-dimension vector is formed by series-connecting the four histograms in the order of horizontal, +45-degree, vertical, and –45-degree. Edge Detection 64x64 Feature Map (64x64) (Horizontal) 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 -1-1-1-1-1 0 0 0 0 0 (Horizontal) Threshold || Median Scan (16 elements) Edge Filter PPED Vector (Horizontal Section) 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 -1 -1 -1 -1 -1 0 0 0 0 0 0 0 0 1 0 0 1 1 0 -1 0 1 0 -1 0 1 0 -1 -1 0 0 -1 0 0 0 Horizontal +45-degree 0 0 0 0 0 Threshold Detection Absolute value difference between neiboring pels. 1 1 1 1 1 0 -1 0 -1 0 -1 0 -1 0 -1 0 0 0 0 0 0 -1 0 0 0 1 0 -1 -1 0 0 1 0 -1 0 0 1 1 0 -1 0 0 0 1 0 Vertical (a) -45-degree (b) Fig. 2: PPED algorithm (a) and filtering kernels for edge detection (b). 3 Sy stem Orga ni za ti o n The system organization of the feature map generation VLSI is illustrated in Fig. 3. The system receives one column of data (8-b x 5 pixels) at each clock and stores the data in the last column of the 5x6 image buffer. The image buffer shifts all the stored data to the right at every clock. Before the edge filtering circuit (EFC) starts detecting four direction edges with respect to the center pixel in the 5x5 block, the threshold value calculated from all the pixel data in the 5x5 block must be ready in time for the processing. In order to keep the coherence of the threshold detection and the edge filtering processing, the two last-in data locating at column 5 and 6 are given to median filter circuit (MFC) in advance via absolute value circuit (AVC). AVC calculates all luminance differences between two neighboring pixels in columns 5 and 6. In this manner, a fully seamless pipeline processing from threshold detection to edge feature map generation has been established. The key requirement here is that MFC must determine the median value of the 40 luminance difference data from the 5x5-pixel block fast enough to carry out the seamless pipeline processing. For this purpose, a four-stage asynchronous median detection architecture has been developed which is explained in the following. Edge Filtering Circuit (EFC) 6 5 4 3 2 1 Edge flags H +45 V Image buffer 8-b x 5 pixels (One column) Absolute Value Circuit (AVC) Threshold value Median Filter Circuit (MFC) -45 Feature maps Fig. 3: System organization of feature map generation VLSI. The well-known binary search algorithm was adopted for fast execution of median detection. The median search processing for five 4-b data is illustrated in Fig. 4 for the purpose of explanation. In the beginning, majority voting is carried out for the MSB’s of all data. Namely, the number of 1’s is compared with the number of 0’s and the majority group wins. The majority group flag (“0” in this example) is stored as the MSB of the median value. In addition, the loser group is withdrawn in the following voting by changing all remaining bits to the loser MSB (“1” in this example). By repeating the processing, the median value is finally stored in the median value register. Elapse of time Median Register : 0 1 X X 0 1 1 0 0 0 1 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 MVC0 MVC1 MVC2 MVC3 MVC0 MVC1 MVC2 MVC3 MVC0 MVC1 MVC2 MVC3 MVC0 MVC1 MVC2 MVC3 Majority Flag : 0 0 X X X Majority Voting Circuit (MVC) Fig. 4: Hardware algorithm for median detection by binary search. How the median value is detected from all the 40 8-b data (20 horizontal luminance difference data and 20 vertical luminance difference data) is illustrated in Fig. 5. All the data are stored in the array of median detection units (MDU’s). At each clock, the array receives four vertical luminance difference data and five horizontal luminance difference data calculated from the data in column 5 and 6 in Fig. 3. The entire data are shifted downward at each clock. The median search is carried out for the upper four bits and the lower four bits separately in order to enhance the throughput by pipelining. For this purpose, the chip is equipped with eight majority voting circuits (MVC 0~7). The upper four bits from all the data are processed by MVC 4~7 in a single clock cycle to yield the median value. In the next clock cycle, the loser information is transferred to the lower four bits within each MDU and MVC0~3 carry out the median search for the lower four bits from all the data in the array. Vertical Luminance Difference AVC AVC AVC AVC Horizontal Luminance Difference AVC AVC AVC AVC AVC Shift Shift Median Detection Unit (MDU) x (40 Units) Lower 4bit Upper 4bit MVC0 MVC2 MVC1 MVC3 MVC4 MVC5 MVC6 MVC7 MVCs for upper 4bit MVCs for lower 4bit Fig. 5: Median detection architecture for all 40 luminance difference data. The majority voting circuit (MVC) is shown in Fig. 6. Output connected CMOS inverters are employed as preamplifiers for majority detection which was first proposed in Ref. [12]. In the present implementation, however, two preamps receiving input data and inverted input data are connected to a 2-stage differential amplifier. Although this doubles the area penalty, the instability in the threshold for majority detection due to process and temperature variations has been remarkably improved as compared to the single inverter thresholding in Ref. [12]. The MVC in Fig. 6 has 41 input terminals although 40 bits of data are inputted to the circuit at one time. Bit “0” is always given to the terminal IN40 to yield “0” as the majority when there is a tie in the majority voting. PREAMP IN0 PREAMP 2W/L IN0 2W/L OUT W/L ENBL W/L W/L IN1 IN1 2W/L 2W/L W/L ENBL IN40 W/L W/L IN40 Fig. 6: Majority voting circuit (MVC). The edge filtering circuit (EFC) in Fig. 3 is composed as a four-stage pipeline of regular CMOS digital logic. In the first two stages, four-direction edge gradients are computed, and in the succeeding two stages, the detection of the largest gradient and the thresholding is carried out to generate four edge flags. 4 E x p e r i m e n t a l R es u l t s The feature map generation VLSI was fabricated in a 0.35-µm double-poly three-metal-layer CMOS technology. A photomicrograph of the proof-of-concept chip is shown in Fig. 7. The measured waveforms of the MVC at operating frequencies of 10MHz and 90MHz are demonstrated in Fig. 8. The input condition is in the worst case. Namely, 21 “1” bits and 20 “0” bits were fed to the inputs. The observed computation time is about 12 nsec which is larger than the simulation result of 2.5 nsec. This was caused by the capacitance loading due to the probing of the test circuit. In the real circuit without external probing, we confirmed the average computation time of 4~5 nsec. Edge-detection Filtering Circuit Processing Technology 0.35µm CMOS 2-Poly 3-Metal Median Filter Control Unit Chip Size 4.5mm x 4.5mm MVC Majority Voting Circuit X8 Supply Voltage 3.3 V Operation Frequengy 50MHz Vector Generator Fig. 7: Photomicrograph and specification of the fabricated proof-of-concept chip. 1V/div 5ns/div MVC_Output 1V/div 8ns/div MVC_OUT IN IN 1 Majority Voting operation (a) Majority Voting operation (b) Fig. 8: Measured waveforms of majority voting circuit (MVC) at operation frequencies of 10MHz (a) and 90 MHz (b) for the worst-case input data. The feature maps generated by the chip at the operation frequency of 25 MHz are demonstrated in Fig. 9. The power dissipation was 224 mW. The difference between the flag bits detected by the chip and those obtained by computer simulation are also shown in the figure. The number of error flags was from 80 to 120 out of 16,384 flags, only a 0.6% of the total. The occurrence of such error bits is anticipated since we employed analog circuits for median detection. However, such error does not cause any serious problems in the PPED algorithm as demonstrated in Figs. 10 and 11. The template matching results with the top five PPED vector candidates in Sella identification are demonstrated in Fig. 11, where Manhattan distance was adopted as the dissimilarity measure. The error in the feature map generation processing yields a constant bias to the dissimilarity and does not affect the result of the maximum likelihood search. Generated Feature maps Difference as compared to computer simulation Sella Horizontal Plus 45-degrees Vertical Minus 45-degrees Fig. 9: Feature maps for Sella pattern generated by the chip. Generated PPED vector by the chip Sella Difference as compared to computer simulation Dissimilarity (by Manhattan Distance) Fig. 10: PPED vector for Sella pattern generated by the chip. The difference in the vector components between the PPED vector generated by the chip and that obtained by computer simulation is also shown. 1200 Measured Data 1000 800 Computer Simulation 600 400 200 0 1st (Correct) 2nd 3rd 4th 5th Candidates in Sella recognition Fig. 11: Comparison of template matching results. 5 Conclusion A mixed-signal median filter VLSI circuit for PPED vector generation is presented. A four-stage asynchronous median detection architecture based on analog digital mixed-signal circuits has been introduced. As a result, a fully seamless pipeline processing from threshold detection to edge feature map generation has been established. A prototype chip was designed in a 0.35-µm CMOS technology and the fab- ricated chip generates an edge based image vector every 80 µsec, which is about 10 4 times faster than the software computation. Acknowledgments The VLSI chip in this study was fabricated in the chip fabrication program of VLSI Design and Education Center (VDEC), the University of Tokyo with the collaboration by Rohm Corporation and Toppan Printing Corporation. The work is partially supported by the Ministry of Education, Science, Sports, and Culture under Grant-in-Aid for Scientific Research (No. 14205043) and by JST in the program of CREST. References [1] C. Liu and Harry Wechsler, “Gabor feature based classification using the enhanced fisher linear discriminant model for face recognition”, IEEE Transactions on Image Processing, Vol. 11, No.4, Apr. 2002. [2] C. Yen-ting, C. Kuo-sheng, and L. Ja-kuang, “Improving cephalogram analysis through feature subimage extraction”, IEEE Engineering in Medicine and Biology Magazine, Vol. 18, No. 1, 1999, pp. 25-31. [3] H. Potlapalli and R. C. Luo, “Fractal-based classification of natural textures”, IEEE Transactions on Industrial Electronics, Vol. 45, No. 1, Feb. 1998. [4] T. Yamasaki and T. Shibata, “Analog Soft-Pattern-Matching Classifier Using Floating-Gate MOS Technology,” Advances in Neural Information Processing Systems 14, Vol. II, pp. 1131-1138. [5] Masakazu Yagi, Tadashi Shibata, “An Image Representation Algorithm Compatible to Neural-Associative-Processor-Based Hardware Recognition Systems,” IEEE Trans. Neural Networks, Vol. 14, No. 5, pp. 1144-1161, September (2003). [6] M. Yagi, M. Adachi, and T. Shibata,

6 0.38793662 22 nips-2003-An Improved Scheme for Detection and Labelling in Johansson Displays

7 0.37116626 99 nips-2003-Kernels for Structured Natural Language Data

8 0.35855415 71 nips-2003-Fast Embedding of Sparse Similarity Graphs

9 0.35711855 191 nips-2003-Unsupervised Context Sensitive Language Acquisition from a Large Corpus

10 0.35358629 135 nips-2003-Necessary Intransitive Likelihood-Ratio Classifiers

11 0.34631956 75 nips-2003-From Algorithmic to Subjective Randomness

12 0.3353129 88 nips-2003-Image Reconstruction by Linear Programming

13 0.31913194 174 nips-2003-Semidefinite Relaxations for Approximate Inference on Graphs with Cycles

14 0.31615207 121 nips-2003-Log-Linear Models for Label Ranking

15 0.31569564 38 nips-2003-Autonomous Helicopter Flight via Reinforcement Learning

16 0.3117134 104 nips-2003-Learning Curves for Stochastic Gradient Descent in Linear Feedforward Networks

17 0.29048911 25 nips-2003-An MCMC-Based Method of Comparing Connectionist Models in Cognitive Science

18 0.27989054 128 nips-2003-Minimax Embeddings

19 0.27472299 134 nips-2003-Near-Minimax Optimal Classification with Dyadic Classification Trees

20 0.27280313 81 nips-2003-Geometric Analysis of Constrained Curves

similar papers computed by lda model

lda for this paper:

topicId topicWeight

[(0, 0.037), (11, 0.088), (20, 0.278), (29, 0.018), (30, 0.013), (35, 0.076), (53, 0.075), (71, 0.063), (76, 0.043), (85, 0.042), (91, 0.133), (99, 0.027)]

similar papers list:

simIndex simValue paperId paperTitle

same-paper 1 0.82355875 168 nips-2003-Salient Boundary Detection using Ratio Contour

Author: Song Wang, Toshiro Kubota, Jeffrey M. Siskind

2 0.76920605 146 nips-2003-Online Learning of Non-stationary Sequences

Author: Claire Monteleoni, Tommi S. Jaakkola

Abstract: We consider an online learning scenario in which the learner can make predictions on the basis of a ﬁxed set of experts. We derive upper and lower relative loss bounds for a class of universal learning algorithms involving a switching dynamics over the choice of the experts. On the basis of the performance bounds we provide the optimal a priori discretization for learning the parameter that governs the switching dynamics. We demonstrate the new algorithm in the context of wireless networks.

3 0.56997228 12 nips-2003-A Model for Learning the Semantics of Pictures

Author: Victor Lavrenko, R. Manmatha, Jiwoon Jeon

Abstract: We propose an approach to learning the semantics of images which allows us to automatically annotate an image with keywords and to retrieve images based on text queries. We do this using a formalism that models the generation of annotated images. We assume that every image is divided into regions, each described by a continuous-valued feature vector. Given a training set of images with annotations, we compute a joint probabilistic model of image features and words which allow us to predict the probability of generating a word given the image regions. This may be used to automatically annotate and retrieve images given a word as a query. Experiments show that our model signiﬁcantly outperforms the best of the previously reported results on the tasks of automatic image annotation and retrieval. 1

4 0.5638203 173 nips-2003-Semi-supervised Protein Classification Using Cluster Kernels

Author: Jason Weston, Dengyong Zhou, André Elisseeff, William S. Noble, Christina S. Leslie

Abstract: A key issue in supervised protein classiﬁcation is the representation of input sequences of amino acids. Recent work using string kernels for protein data has achieved state-of-the-art classiﬁcation performance. However, such representations are based only on labeled data — examples with known 3D structures, organized into structural classes — while in practice, unlabeled data is far more plentiful. In this work, we develop simple and scalable cluster kernel techniques for incorporating unlabeled data into the representation of protein sequences. We show that our methods greatly improve the classiﬁcation performance of string kernels and outperform standard approaches for using unlabeled data, such as adding close homologs of the positive examples to the training data. We achieve equal or superior performance to previously presented cluster kernel methods while achieving far greater computational efﬁciency. 1

5 0.5414356 73 nips-2003-Feature Selection in Clustering Problems

Author: Volker Roth, Tilman Lange

Abstract: A novel approach to combining clustering and feature selection is presented. It implements a wrapper strategy for feature selection, in the sense that the features are directly selected by optimizing the discriminative power of the used partitioning algorithm. On the technical side, we present an efﬁcient optimization algorithm with guaranteed local convergence property. The only free parameter of this method is selected by a resampling-based stability analysis. Experiments with real-world datasets demonstrate that our method is able to infer both meaningful partitions and meaningful subsets of features. 1

6 0.54074258 88 nips-2003-Image Reconstruction by Linear Programming

7 0.54007745 65 nips-2003-Extending Q-Learning to General Adaptive Multi-Agent Systems

8 0.5395366 107 nips-2003-Learning Spectral Clustering

9 0.53897339 55 nips-2003-Distributed Optimization in Adaptive Networks

10 0.53777558 30 nips-2003-Approximability of Probability Distributions

11 0.53773934 81 nips-2003-Geometric Analysis of Constrained Curves

12 0.53543466 37 nips-2003-Automatic Annotation of Everyday Movements

13 0.53540093 125 nips-2003-Maximum Likelihood Estimation of a Stochastic Integrate-and-Fire Neural Model

14 0.53531367 78 nips-2003-Gaussian Processes in Reinforcement Learning

15 0.53527659 164 nips-2003-Ranking on Data Manifolds

16 0.53454226 158 nips-2003-Policy Search by Dynamic Programming

17 0.53447115 79 nips-2003-Gene Expression Clustering with Functional Mixture Models

18 0.53439951 91 nips-2003-Inferring State Sequences for Non-linear Systems with Embedded Hidden Markov Models

19 0.53388852 68 nips-2003-Eye Movements for Reward Maximization

20 0.53257775 116 nips-2003-Linear Program Approximations for Factored Continuous-State Markov Decision Processes