cvpr cvpr2013 cvpr2013-184 knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Hu Ding, Branislav Stojkovic, Ronald Berezney, Jinhui Xu
Abstract: Computing accurate and robust organizational patterns of chromosome territories inside the cell nucleus is critical for understanding several fundamental genomic processes, such as co-regulation of gene activation, gene silencing, X chromosome inactivation, and abnormal chromosome rearrangement in cancer cells. The usage of advanced fluorescence labeling and image processing techniques has enabled researchers to investigate interactions of chromosome territories at large spatial resolution. The resulting high volume of generated data demands for high-throughput and automated image analysis methods. In this paper, we introduce a novel algorithmic tool for investigating association patterns of chromosome territories in a population of cells. Our method takes as input a set of graphs, one for each cell, containing information about spatial interaction of chromosome territories, and yields a single graph that contains essential information for the whole population and stands as its structural representative. We formulate this combinato- rial problem as a semi-definite programming and present novel techniques to efficiently solve it. We validate our approach on both artificial and real biological data; the experimental results suggest that our approach yields a nearoptimal solution, and can handle large-size datasets, which are significant improvements over existing techniques.
Reference: text
sentIndex sentText sentNum sentScore
1 The usage of advanced fluorescence labeling and image processing techniques has enabled researchers to investigate interactions of chromosome territories at large spatial resolution. [sent-5, score-0.846]
2 In this paper, we introduce a novel algorithmic tool for investigating association patterns of chromosome territories in a population of cells. [sent-7, score-1.023]
3 Our method takes as input a set of graphs, one for each cell, containing information about spatial interaction of chromosome territories, and yields a single graph that contains essential information for the whole population and stands as its structural representative. [sent-8, score-0.661]
4 Chromosome Territories (CTs) are distinct regions within the cell nu∗This research was supported in part by NSF through a grant IIS1115220. [sent-14, score-0.101]
5 Chromosome territories constitute a staple feature of nuclear architecture and are in constant dynamic interaction with other components of cell nucleus. [sent-16, score-0.406]
6 Recent studies show influence of arrangements of chromosome territories on some fundamental cell molecular processes (e. [sent-17, score-0.949]
7 For decades, determining how chromosomes are organized inside the cellular nucleus was a technically challenging process largely relying on manual measurements and observation ofexperts (see Fig. [sent-21, score-0.241]
8 Thus, obtaining accurate and robust chromosome interaction patterns from cell nucleus images will significantly facilitate analysis and im- prove overall understanding of molecular processes in cell nucleus [5, 6, 8, 10]. [sent-23, score-1.135]
9 An effective way of representing high level chromosome territory organization in each cell is to use a graph data structure, where every vertex is an individual chromosome territory and every edge represents the association (spatial proximity) of a pair of neighboring chromosome territories. [sent-24, score-2.201]
10 In a pair graph, each chromosome territory is associated with a chromosome number, and each chromosome number has multiplicity of two (one for each chromosome homolog). [sent-26, score-2.305]
11 1a, each chromosome number has two chromosome homologs which share the same color. [sent-28, score-1.11]
12 A graph that can be seen as representative for the set of pair graphs is called a Chromosome Association Pattern (CAP). [sent-29, score-0.188]
13 Despite recent developments in microscopy imaging, and labeling techniques, our abilities to calculate CAP for a given cell population are still limited. [sent-30, score-0.132]
14 1d from a set of is a label 3D microscopic nucleus images. [sent-33, score-0.201]
15 Related Works Several models in literature are applicable to finding chromosome territories association patterns. [sent-40, score-0.973]
16 The most popular one is median graph [16], which has received considerable attentions in recent years [11, 12, 14, 15]. [sent-41, score-0.296]
17 Given a set of input graphs with possible labels associated with vertices, the objective of a median graph problem is to compute a new graph, called median graph, that has the minimum distance to the input graphs. [sent-42, score-0.654]
18 Distance between two graphs is usually defined as their edit distance. [sent-43, score-0.142]
19 In the context of finding association patterns of chromosome territories, GMG, as well as any other median graph method, has two major limitations. [sent-45, score-1.018]
20 While this is in accordance with the edit distance definition, it gives mis- leading semantic interpretation in our biological application where vertex labels denote chromosome territories. [sent-48, score-0.707]
21 Secondly, GMG requires graphs with unique predefined labeling, this is in direct contrast with the uncertainty that we are facing in dealing with chromosome territory homologs. [sent-49, score-0.753]
22 Our Model Aiming to fix the aforementioned problems in existing approaches, we first enumerate 2k labeled graphs for each k-pair association graph, with each labeled graph corresponding to a permutation of the original k-pair graph. [sent-58, score-0.434]
23 Note that k is normally a small constant no more than 9 (this is due to the limitation of current labeling techniques in cell biology). [sent-59, score-0.101]
24 Then we map the 2kn labeled graphs to points in some metric space, such that the pairwise distance of any two points is equal to the Jaccard distance between the corresponding two labeled graphs. [sent-61, score-0.285]
25 To solve the chromatic median problem, we first give a Quadratic Integer Programming model, then relax it to a Semi-definite Programming (SDP) problem, and propose a multi-level rounding technique to solve the SDP problem. [sent-66, score-0.559]
26 It should be pointed out that although several rounding techniques exist for SDP [1, 13], the multi-level rounding technique is new, to the best of our knowledge. [sent-67, score-0.274]
27 e An a unweighed graph I (V, E) is a k-pair association graph = for IM, if it satisfies 1r. [sent-75, score-0.298]
28 Any two vertices from V are connect by an edge if the corresponding two chromosome territories are close 1 1 12 2 29 9 957 5 enough to each other in 3D space (based on some biological threshold). [sent-78, score-0.917]
29 Figure 1c shows the k-pair association graph, where k = 8, for the nucleus image given in Figure 1a. [sent-79, score-0.316]
30 From the above definition, it is easy to see that every kpair association graph has 2k different label differentiations. [sent-90, score-0.266]
31 For any two given graphs G1 = (V, E1) and G2 = (V, E2) with the same labeled vertex set V , the Jaccard Distance between them is defined as JD(G1,G2) = 1 −||EE11? [sent-94, score-0.195]
32 First, we recall that median point in geometry is also called Fermat Weber point. [sent-106, score-0.221]
33 For any set of n points {p1, p2, · · · ,pn} in Rd space, its median point is defined {asp Med = argx m∈iRndn1i? [sent-107, score-0.244]
34 Consequently, median point is often approximated by using some iterative procedure, such as Weiszfeld’s algorithm [21]. [sent-111, score-0.221]
35 In Section 5, we present a semi-definite programming formulation, which helps us to identify each pili and yields a 2-approximation solution for Chromatic Median, where the approximation ratio is over the cost function (3). [sent-119, score-0.268]
36 Formulation: from cap to chromatic median To solve the chromosome association pattern (CAP) problem, we use the following reduction from CAP to the Chromatic Median problem. [sent-121, score-1.21]
37 For each of the n nucleus images IMi, build a kpair a esascohci oaftio thne graph. [sent-123, score-0.211]
38 Enumerate the 2k possible Label Differentiations for each Ii, and generate the corresponding 2k labeled graphs {Ii1, · · · , I2ik }. [sent-126, score-0.153]
39 For any two labeled graphs Iis1 and Iit2 , we compute the Jaccard distance between them. [sent-131, score-0.177]
40 Since the Jac- card distance satisfies triangle inequality [7], we map the 2kn labeled graphs to 2kn points in some metric space. [sent-132, score-0.222]
41 For each group oflabeled graphs {Ii1, · · · , I2ik }, we dee. [sent-133, score-0.113]
42 Find the n points {pl11 , · · · ,plnn } by the semi-definite programming model given in Section 5, where each pili is the nearest point to Chromatic Median among Pi. [sent-137, score-0.268]
43 Mapping graphs into points: In Step 3 of the above reduction, we need to map all labeled graphs into points in some metric space. [sent-141, score-0.286]
44 Our idea is not to explicitly build the metric space; instead, we formulate the Chromatic Median problem as a semi-definite programming (in Section 5) which only requires the pairwise distances among the set of mapped points (i. [sent-143, score-0.162]
45 For a given set of labeled graphs {DGef1i , iGti2o , n· n· 6· , jGdn-}M wGit)h. [sent-150, score-0.153]
46 2(bc)showsanexampleof the column graph corresponding to the 0-1 Quadratic Programming, where the vertices sharing the same column of vertices. [sent-152, score-0.11]
47 n=1JD(G˜,Gi), E˜), (4) where JD(·) denotes the Jaccard Distance between two graphs ( JseDe Definition s3) th. [sent-155, score-0.113]
48 Ifwe consider each Gi as one point in some metric space, and the distance in the space is defined as the Jaccard Distance, then jd-MG is similar to the geometric median point otafn tchee, point-sets {GG is1 , Gim2i , ·a ·r ·t , Gthen g}e. [sent-156, score-0.265]
49 Compute the median point of {ν1 , ν2 , · · · , νn} using W. [sent-165, score-0.221]
50 Correspondingly, denote the graph as = (V, where the edges set is indicated by ˜ν (ρ). [sent-175, score-0.104]
51 Semi-definite Model for Chromatic Median In this section, we show that it is not necessary to find the exact chromatic median CMed. [sent-182, score-0.422]
52 Instead, it is sufficient to first find the n points {pl11 , · · · ,plnn }, where each plii is the nearest to CMed among all the points in Pi, and then output the Median Graph under Jaccard Distance for {I1l1, ··· , Ilnn} using the idea described in Section 4. [sent-183, score-0.241]
53 jn=1 | |pjlj − plii | |, so as to avoid finding CMed. [sent-188, score-0.241]
54 Since CMed is the geometric median point of {pl11 , · · · ,plnn }, by (2), we know that for any 1 ≤ j ≤ n, ? [sent-198, score-0.221]
55 Mhaevaen ||pjlj − plii | | ≤ ||pjlj − CMed| | + | |pili − CMed| |. [sent-217, score-0.241]
56 bove lemma suggests that minimizing the total pairwise distances enables us to obtain a 2-approximation for chromatic median. [sent-327, score-0.295]
57 Next, we introduce a quadratic programming model for finding the desired n points which minimize the total pairwise distances. [sent-328, score-0.151]
58 Finally, the 0-1 Quadratic Programming is to find a subgraph of the column graph with minimum total weight, where the subgraph contains exactly one ver- = n−y wis1,,ti2 tex from each column. [sent-349, score-0.121]
59 j=1 (15) The above 0-1 quadratic programming indicates that if we compute its optimal solution, we immediately obtain exactly one indicator variable, say xlii? [sent-372, score-0.146]
60 Then by Lemma 2, we know that the geometric median point of {pl11? [sent-376, score-0.221]
61 The optimal solution of the above 0-1 quadratic programming yields a 2-approximation for the chromatic median problem. [sent-382, score-0.549]
62 Semi-definite Programming Model Since the 0-1 quadratic programming is challenging to solve optimally [19], we convert it to a semi-definite programming model. [sent-385, score-0.225]
63 We first build an equivalent 0-1 semidefinite programming (SDP), and then use rounding technique to solve it. [sent-386, score-0.288]
64 The optimal solution of the above 0-1 semidefinite programming is equivalent to the optimal solution of the 0-1 quadratic programming. [sent-405, score-0.18]
65 Consequently, it yields a 2-approximation for the chromatic median problem. [sent-406, score-0.422]
66 Since X is not necessarily a 0d-e1fi mnitaetr mixa, troix xo Xbtai ∈n a feasible solution to CAP, we need to perform a rounding procedure on X to convert it into a 0-1 matrix. [sent-411, score-0.137]
67 Below, we introduce a multiple-level rounding algorithm to achieve a better solution. [sent-414, score-0.137]
68 Algorithm overview: Our algorithm performs log λ rounding steps iteratively. [sent-415, score-0.137]
69 Finally, after log λ iterations, there is only one positive number among the diagonal elements for each Xi,i, which is the final rounding result. [sent-418, score-0.163]
70 In the first part we evaluate the performance of our method on synthetic datasets, with each dataset consisting of a number of randomly generated k-pair association graphs. [sent-454, score-0.177]
71 In the second part, we apply our method for gauging the associations of chromosome territories in a population of cells belonging to WI 38 human lung fibroblast cell line. [sent-455, score-1.087]
72 For each synthetic dataset, we randomly generate a k-pair association graph, I= (V, E), as the ground truth. [sent-461, score-0.177]
73 Then we generate a set of kpair association graphs based on the ground truth with some percentage of input noise. [sent-462, score-0.304]
74 Athec ground truth graph for each input graph would be 1−11−+pp = tMruothre gorvaeprh, we regard nitp as gthraep expected objective value for the CAP-graph obtained by our method. [sent-465, score-0.15]
75 section we denote the number of (chromosome territory) pairs as k, the number of input k-pair association graphs in each dataset as n, and the input noise percentage as p. [sent-467, score-0.28]
76 Table 1: Results for the multi-level rounding 12+pp). [sent-481, score-0.137]
77 To determine the performance of the multilevel rounding technique, we show its comparison with the results obtained by single level round1 1 12 3239 90 91 9 aeAcngidrjevtas0 5. [sent-491, score-0.192]
78 The Jaccard distance values for multilevel rounding are significantly lower than those obtained by single level rounding. [sent-502, score-0.216]
79 Given two labeled graphs G1 = (V, E1) and G2 = (V, E2), Sorensen index is defined as Results are shown in Table 2, where our method achieves more than 10% improvements over all the three datasets, and the improvement becomes larger when the noise level increases. [sent-518, score-0.172]
80 The usage of advanced fluorescence labeling and image processing techniques has enabled researchers to investigate interactions of chromosome territories at large spatial resolution. [sent-532, score-0.846]
81 Current limits of microscopic image acquisition process allow at most 9 pairs of chromosome territories to be labeled per cell nucleus. [sent-533, score-0.999]
82 In this experiment, we focus on the study of associations of 8 chromosome territory pairs (with chromosome numbers from 1 to 9, except for 5) in WI 38 human lung fibroblast cells. [sent-534, score-1.3]
83 We run our algorithm on dataset consisting of 90 microscope nucleus images. [sent-535, score-0.19]
84 Each raw microscope image is a set of 2-D slices, where each slice corresponds to an image of the 3-D cell nucleus acquired at a certain focal plane. [sent-536, score-0.291]
85 Individual k-pair association graph for each cell is derived using nearest border to border distances among chromosome territories. [sent-538, score-0.899]
86 Like many biological problems, there is no ground truth for the CAP-graph on the cell nucleus images. [sent-540, score-0.326]
87 For the association pattern, we compare the edges in our association pattern with those in the graph [22] generated by GMG [18] using the same dataset. [sent-559, score-0.4]
88 Additionally, our method finds the following new association edges, where Table 4 shows them and their frequency among the dataset. [sent-561, score-0.148]
89 Note that since the nucleus images are in 3D and the association patterns may appear in different slices, we only show the associations in some slices. [sent-565, score-0.375]
90 From Figure 4b, it is easy to see that the labeled pairs of chromosome territories are indeed close to each other, which also confirms the effectiveness of our approach. [sent-566, score-0.865]
91 Table 4: Additional association edges discovered by our method Edges4 − 63 − 46 − 77 − 2 4 − 63 Frequency − 56. [sent-567, score-0.177]
92 Summary and Discussion In this paper we present an efficient method for recognizing the pattern of associations for chromosome territories in the cell nucleus. [sent-572, score-0.966]
93 Experiments using synthetic datasets reveal the scalability and high efficiency of our method, while the experiment on a cell nucleus image dataset shows the accuracy of our method for finding the association pattern of human chromosome terrirtories. [sent-575, score-1.001]
94 A linear programming approach for the weighted graph matching problem. [sent-583, score-0.173]
95 Three-dimensional maps of all chromosomes in human male fibroblast nuclei and prometaphase rosettes. [sent-618, score-0.116]
96 Chromosome territories, nuclear architecture and gene regulation in mamalian cells. [sent-639, score-0.104]
97 A generic framework for median graph computation based on a recursive embedding approach. [sent-660, score-0.296]
98 Generalized median graph computation by means of graph embedding in vector spaces. [sent-667, score-0.371]
99 A binary linear programming formulation of the graph edit distance. [sent-686, score-0.202]
100 A probabilistic model for the arrangement of a subset of human chromosome territories in wi38 human fibroblasts. [sent-743, score-0.825]
wordName wordTfidf (topN-words)
[('chromosome', 0.555), ('cmed', 0.313), ('territories', 0.27), ('plii', 0.241), ('median', 0.221), ('chromatic', 0.201), ('jaccard', 0.201), ('pili', 0.17), ('nucleus', 0.168), ('association', 0.148), ('rounding', 0.137), ('pljj', 0.128), ('gmg', 0.114), ('graphs', 0.113), ('cell', 0.101), ('programming', 0.098), ('sdp', 0.091), ('mag', 0.085), ('territory', 0.085), ('cap', 0.085), ('graph', 0.075), ('sorensen', 0.071), ('pli', 0.07), ('biological', 0.057), ('cremer', 0.057), ('multilevel', 0.055), ('semidefinite', 0.053), ('med', 0.052), ('chromosomes', 0.05), ('lemma', 0.05), ('gene', 0.044), ('fibroblast', 0.043), ('kpair', 0.043), ('pjlj', 0.043), ('stojkovic', 0.043), ('zeitz', 0.043), ('vertex', 0.042), ('xji', 0.04), ('associations', 0.04), ('labeled', 0.04), ('buffalo', 0.038), ('deletion', 0.038), ('plj', 0.038), ('fal', 0.035), ('nuclear', 0.035), ('jd', 0.035), ('vertices', 0.035), ('microscopic', 0.033), ('population', 0.031), ('bu', 0.031), ('synthetic', 0.029), ('quadratic', 0.029), ('edit', 0.029), ('edges', 0.029), ('arora', 0.028), ('boyle', 0.028), ('bridger', 0.028), ('ferrer', 0.028), ('gcap', 0.028), ('homolog', 0.028), ('mller', 0.028), ('solovei', 0.028), ('williamson', 0.028), ('definition', 0.028), ('jn', 0.027), ('pi', 0.027), ('speedup', 0.027), ('diagonal', 0.026), ('adaptive', 0.026), ('goemans', 0.025), ('genome', 0.025), ('regulation', 0.025), ('gauging', 0.025), ('ilnn', 0.025), ('inequality', 0.025), ('slices', 0.024), ('pairwise', 0.024), ('distance', 0.024), ('valveny', 0.023), ('molecular', 0.023), ('hardness', 0.023), ('nuclei', 0.023), ('cellular', 0.023), ('argx', 0.023), ('subgraph', 0.023), ('microscope', 0.022), ('indi', 0.022), ('lung', 0.022), ('fluorescence', 0.021), ('mukherjee', 0.02), ('metric', 0.02), ('distances', 0.02), ('immediately', 0.019), ('noise', 0.019), ('patterns', 0.019), ('sampling', 0.018), ('side', 0.018), ('ei', 0.018), ('enumerate', 0.018), ('pp', 0.018)]
simIndex simValue paperId paperTitle
same-paper 1 1.0000014 184 cvpr-2013-Gauging Association Patterns of Chromosome Territories via Chromatic Median
Author: Hu Ding, Branislav Stojkovic, Ronald Berezney, Jinhui Xu
Abstract: Computing accurate and robust organizational patterns of chromosome territories inside the cell nucleus is critical for understanding several fundamental genomic processes, such as co-regulation of gene activation, gene silencing, X chromosome inactivation, and abnormal chromosome rearrangement in cancer cells. The usage of advanced fluorescence labeling and image processing techniques has enabled researchers to investigate interactions of chromosome territories at large spatial resolution. The resulting high volume of generated data demands for high-throughput and automated image analysis methods. In this paper, we introduce a novel algorithmic tool for investigating association patterns of chromosome territories in a population of cells. Our method takes as input a set of graphs, one for each cell, containing information about spatial interaction of chromosome territories, and yields a single graph that contains essential information for the whole population and stands as its structural representative. We formulate this combinato- rial problem as a semi-definite programming and present novel techniques to efficiently solve it. We validate our approach on both artificial and real biological data; the experimental results suggest that our approach yields a nearoptimal solution, and can handle large-size datasets, which are significant improvements over existing techniques.
2 0.13568354 11 cvpr-2013-A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles
Author: Dror Sholomon, Omid David, Nathan S. Netanyahu
Abstract: In thispaper wepropose thefirst effective automated, genetic algorithm (GA)-based jigsaw puzzle solver. We introduce a novel procedure of merging two ”parent” solutions to an improved ”child” solution by detecting, extracting, and combining correctly assembled puzzle segments. The solver proposed exhibits state-of-the-art performance solving previously attempted puzzles faster and far more accurately, and also puzzles of size never before attempted. Other contributions include the creation of a benchmark of large images, previously unavailable. We share the data sets and all of our results for future testing and comparative evaluation of jigsaw puzzle solvers.
3 0.08389312 301 cvpr-2013-Multi-target Tracking by Rank-1 Tensor Approximation
Author: Xinchu Shi, Haibin Ling, Junling Xing, Weiming Hu
Abstract: In this paper we formulate multi-target tracking (MTT) as a rank-1 tensor approximation problem and propose an ?1 norm tensor power iteration solution. In particular, a high order tensor is constructed based on trajectories in the time window, with each tensor element as the affinity of the corresponding trajectory candidate. The local assignment variables are the ?1 normalized vectors, which are used to approximate the rank-1 tensor. Our approach provides a flexible and effective formulation where both pairwise and high-order association energies can be used expediently. We also show the close relation between our formulation and the multi-dimensional assignment (MDA) model. To solve the optimization in the rank-1 tensor approximation, we propose an algorithm that iteratively powers the intermediate solution followed by an ?1 normalization. Aside from effectively capturing high-order motion information, the proposed solver runs efficiently with proved convergence. The experimental validations are conducted on two challenging datasets and our method demonstrates promising performances on both.
4 0.077589117 9 cvpr-2013-A Fast Semidefinite Approach to Solving Binary Quadratic Problems
Author: Peng Wang, Chunhua Shen, Anton van_den_Hengel
Abstract: Many computer vision problems can be formulated as binary quadratic programs (BQPs). Two classic relaxation methods are widely used for solving BQPs, namely, spectral methods and semidefinite programming (SDP), each with their own advantages and disadvantages. Spectral relaxation is simple and easy to implement, but its bound is loose. Semidefinite relaxation has a tighter bound, but its computational complexity is high for large scale problems. We present a new SDP formulation for BQPs, with two desirable properties. First, it has a similar relaxation bound to conventional SDP formulations. Second, compared with conventional SDP methods, the new SDP formulation leads to a significantly more efficient and scalable dual optimization approach, which has the same degree of complexity as spectral methods. Extensive experiments on various applications including clustering, image segmentation, co-segmentation and registration demonstrate the usefulness of our SDP formulation for solving large-scale BQPs.
5 0.055882324 192 cvpr-2013-Graph Matching with Anchor Nodes: A Learning Approach
Author: Nan Hu, Raif M. Rustamov, Leonidas Guibas
Abstract: In this paper, we consider the weighted graph matching problem with partially disclosed correspondences between a number of anchor nodes. Our construction exploits recently introduced node signatures based on graph Laplacians, namely the Laplacian family signature (LFS) on the nodes, and the pairwise heat kernel map on the edges. In this paper, without assuming an explicit form of parametric dependence nor a distance metric between node signatures, we formulate an optimization problem which incorporates the knowledge of anchor nodes. Solving this problem gives us an optimized proximity measure specific to the graphs under consideration. Using this as a first order compatibility term, we then set up an integer quadratic program (IQP) to solve for a near optimal graph matching. Our experiments demonstrate the superior performance of our approach on randomly generated graphs and on two widelyused image sequences, when compared with other existing signature and adjacency matrix based graph matching methods.
6 0.051912531 189 cvpr-2013-Graph-Based Discriminative Learning for Location Recognition
7 0.050351359 450 cvpr-2013-Unsupervised Joint Object Discovery and Segmentation in Internet Images
8 0.049831994 149 cvpr-2013-Evaluation of Color STIPs for Human Action Recognition
9 0.049157858 329 cvpr-2013-Perceptual Organization and Recognition of Indoor Scenes from RGB-D Images
10 0.047949392 224 cvpr-2013-Information Consensus for Distributed Multi-target Tracking
11 0.047826324 165 cvpr-2013-Fast Energy Minimization Using Learned State Filters
12 0.045831818 300 cvpr-2013-Multi-target Tracking by Lagrangian Relaxation to Min-cost Network Flow
13 0.043461997 62 cvpr-2013-Bilinear Programming for Human Activity Recognition with Unknown MRF Graphs
14 0.043127637 140 cvpr-2013-Efficient Color Boundary Detection with Color-Opponent Mechanisms
15 0.042041767 264 cvpr-2013-Learning to Detect Partially Overlapping Instances
16 0.04162766 441 cvpr-2013-Tracking Sports Players with Context-Conditioned Motion Models
17 0.03981882 262 cvpr-2013-Learning for Structured Prediction Using Approximate Subgradient Descent with Working Sets
18 0.039484121 121 cvpr-2013-Detection- and Trajectory-Level Exclusion in Multiple Object Tracking
19 0.03901216 222 cvpr-2013-Incorporating User Interaction and Topological Constraints within Contour Completion via Discrete Calculus
20 0.03845666 321 cvpr-2013-PDM-ENLOR: Learning Ensemble of Local PDM-Based Regressions
topicId topicWeight
[(0, 0.089), (1, 0.013), (2, 0.002), (3, 0.011), (4, 0.032), (5, -0.004), (6, -0.007), (7, -0.026), (8, -0.031), (9, 0.009), (10, 0.029), (11, 0.007), (12, -0.049), (13, -0.024), (14, -0.021), (15, -0.007), (16, 0.01), (17, 0.004), (18, 0.062), (19, 0.006), (20, -0.018), (21, 0.038), (22, -0.054), (23, 0.035), (24, 0.057), (25, -0.015), (26, 0.047), (27, -0.025), (28, -0.01), (29, 0.017), (30, -0.001), (31, 0.002), (32, 0.035), (33, -0.06), (34, 0.057), (35, 0.033), (36, 0.033), (37, 0.019), (38, 0.055), (39, 0.018), (40, 0.003), (41, 0.005), (42, 0.001), (43, 0.054), (44, 0.042), (45, -0.037), (46, 0.034), (47, -0.048), (48, -0.003), (49, -0.033)]
simIndex simValue paperId paperTitle
same-paper 1 0.89397788 184 cvpr-2013-Gauging Association Patterns of Chromosome Territories via Chromatic Median
Author: Hu Ding, Branislav Stojkovic, Ronald Berezney, Jinhui Xu
Abstract: Computing accurate and robust organizational patterns of chromosome territories inside the cell nucleus is critical for understanding several fundamental genomic processes, such as co-regulation of gene activation, gene silencing, X chromosome inactivation, and abnormal chromosome rearrangement in cancer cells. The usage of advanced fluorescence labeling and image processing techniques has enabled researchers to investigate interactions of chromosome territories at large spatial resolution. The resulting high volume of generated data demands for high-throughput and automated image analysis methods. In this paper, we introduce a novel algorithmic tool for investigating association patterns of chromosome territories in a population of cells. Our method takes as input a set of graphs, one for each cell, containing information about spatial interaction of chromosome territories, and yields a single graph that contains essential information for the whole population and stands as its structural representative. We formulate this combinato- rial problem as a semi-definite programming and present novel techniques to efficiently solve it. We validate our approach on both artificial and real biological data; the experimental results suggest that our approach yields a nearoptimal solution, and can handle large-size datasets, which are significant improvements over existing techniques.
2 0.74025595 106 cvpr-2013-Deformable Graph Matching
Author: Feng Zhou, Fernando De_la_Torre
Abstract: Graph matching (GM) is a fundamental problem in computer science, and it has been successfully applied to many problems in computer vision. Although widely used, existing GM algorithms cannot incorporate global consistence among nodes, which is a natural constraint in computer vision problems. This paper proposes deformable graph matching (DGM), an extension of GM for matching graphs subject to global rigid and non-rigid geometric constraints. The key idea of this work is a new factorization of the pair-wise affinity matrix. This factorization decouples the affinity matrix into the local structure of each graph and the pair-wise affinity edges. Besides the ability to incorporate global geometric transformations, this factorization offers three more benefits. First, there is no need to compute the costly (in space and time) pair-wise affinity matrix. Second, it provides a unified view of many GM methods and extends the standard iterative closest point algorithm. Third, it allows to use the path-following optimization algorithm that leads to improved optimization strategies and matching performance. Experimental results on synthetic and real databases illustrate how DGM outperforms state-of-the-art algorithms for GM. The code is available at http : / / human s en s ing . c s . cmu .edu / fgm.
3 0.72987044 192 cvpr-2013-Graph Matching with Anchor Nodes: A Learning Approach
Author: Nan Hu, Raif M. Rustamov, Leonidas Guibas
Abstract: In this paper, we consider the weighted graph matching problem with partially disclosed correspondences between a number of anchor nodes. Our construction exploits recently introduced node signatures based on graph Laplacians, namely the Laplacian family signature (LFS) on the nodes, and the pairwise heat kernel map on the edges. In this paper, without assuming an explicit form of parametric dependence nor a distance metric between node signatures, we formulate an optimization problem which incorporates the knowledge of anchor nodes. Solving this problem gives us an optimized proximity measure specific to the graphs under consideration. Using this as a first order compatibility term, we then set up an integer quadratic program (IQP) to solve for a near optimal graph matching. Our experiments demonstrate the superior performance of our approach on randomly generated graphs and on two widelyused image sequences, when compared with other existing signature and adjacency matrix based graph matching methods.
4 0.6886999 11 cvpr-2013-A Genetic Algorithm-Based Solver for Very Large Jigsaw Puzzles
Author: Dror Sholomon, Omid David, Nathan S. Netanyahu
Abstract: In thispaper wepropose thefirst effective automated, genetic algorithm (GA)-based jigsaw puzzle solver. We introduce a novel procedure of merging two ”parent” solutions to an improved ”child” solution by detecting, extracting, and combining correctly assembled puzzle segments. The solver proposed exhibits state-of-the-art performance solving previously attempted puzzles faster and far more accurately, and also puzzles of size never before attempted. Other contributions include the creation of a benchmark of large images, previously unavailable. We share the data sets and all of our results for future testing and comparative evaluation of jigsaw puzzle solvers.
Author: Tianyang Ma, Longin Jan Latecki
Abstract: The proposed approach is based on standard graph transduction, semi-supervised learning (SSL) framework. Its key novelty is the integration of global connectivity constraints into this framework. Although connectivity leads to higher order constraints and their number is an exponential, finding the most violated connectivity constraint can be done efficiently in polynomial time. Moreover, each such constraint can be represented as a linear inequality. Based on this fact, we design a cutting-plane algorithm to solve the integrated problem. It iterates between solving a convex quadraticproblem of labelpropagation with linear inequality constraints, and finding the most violated constraint. We demonstrate the benefits of the proposed approach on a realistic and very challenging problem of cosegmentation of multiple foreground objects in photo collections in which the foreground objects are not present in all photos. The obtained results not only demonstrate performance boost induced by the connectivity constraints, but also show a significant improvement over the state-of-the-art methods.
6 0.61422503 350 cvpr-2013-Reconstructing Loopy Curvilinear Structures Using Integer Programming
7 0.59578663 9 cvpr-2013-A Fast Semidefinite Approach to Solving Binary Quadratic Problems
8 0.57899791 62 cvpr-2013-Bilinear Programming for Human Activity Recognition with Unknown MRF Graphs
9 0.56099802 280 cvpr-2013-Maximum Cohesive Grid of Superpixels for Fast Object Localization
10 0.55547148 300 cvpr-2013-Multi-target Tracking by Lagrangian Relaxation to Min-cost Network Flow
11 0.55434626 224 cvpr-2013-Information Consensus for Distributed Multi-target Tracking
12 0.55050713 234 cvpr-2013-Joint Spectral Correspondence for Disparate Image Matching
13 0.54939336 190 cvpr-2013-Graph-Based Optimization with Tubularity Markov Tree for 3D Vessel Segmentation
14 0.54463881 91 cvpr-2013-Consensus of k-NNs for Robust Neighborhood Selection on Graph-Based Manifolds
15 0.54320914 429 cvpr-2013-The Generalized Laplacian Distance and Its Applications for Visual Matching
16 0.53533125 222 cvpr-2013-Incorporating User Interaction and Topological Constraints within Contour Completion via Discrete Calculus
17 0.53469998 240 cvpr-2013-Keypoints from Symmetries by Wave Propagation
18 0.53141659 93 cvpr-2013-Constraints as Features
20 0.5189749 165 cvpr-2013-Fast Energy Minimization Using Learned State Filters
topicId topicWeight
[(3, 0.016), (10, 0.097), (16, 0.017), (26, 0.042), (33, 0.193), (39, 0.014), (59, 0.012), (65, 0.012), (67, 0.03), (69, 0.046), (87, 0.046), (94, 0.37)]
simIndex simValue paperId paperTitle
same-paper 1 0.68742526 184 cvpr-2013-Gauging Association Patterns of Chromosome Territories via Chromatic Median
Author: Hu Ding, Branislav Stojkovic, Ronald Berezney, Jinhui Xu
Abstract: Computing accurate and robust organizational patterns of chromosome territories inside the cell nucleus is critical for understanding several fundamental genomic processes, such as co-regulation of gene activation, gene silencing, X chromosome inactivation, and abnormal chromosome rearrangement in cancer cells. The usage of advanced fluorescence labeling and image processing techniques has enabled researchers to investigate interactions of chromosome territories at large spatial resolution. The resulting high volume of generated data demands for high-throughput and automated image analysis methods. In this paper, we introduce a novel algorithmic tool for investigating association patterns of chromosome territories in a population of cells. Our method takes as input a set of graphs, one for each cell, containing information about spatial interaction of chromosome territories, and yields a single graph that contains essential information for the whole population and stands as its structural representative. We formulate this combinato- rial problem as a semi-definite programming and present novel techniques to efficiently solve it. We validate our approach on both artificial and real biological data; the experimental results suggest that our approach yields a nearoptimal solution, and can handle large-size datasets, which are significant improvements over existing techniques.
Author: Amy Tabb
Abstract: This paper considers the problem of reconstructing the shape ofthin, texture-less objects such as leafless trees when there is noise or deterministic error in the silhouette extraction step or there are small errors in camera calibration. Traditional intersection-based techniques such as the visual hull are not robust to error because they penalize false negative and false positive error unequally. We provide a voxel-based formalism that penalizes false negative and positive error equally, by casting the reconstruction problem as a pseudo-Boolean minimization problem, where voxels are the variables of a pseudo-Boolean function and are labeled occupied or empty. Since the pseudo-Boolean minimization problem is NP-Hard for nonsubmodular functions, we developed an algorithm for an approximate solution using local minimum search. Our algorithm treats input binary probability maps (in other words, silhouettes) or continuously-valued probability maps identically, and places no constraints on camera placement. The algorithm was tested on three different leafless trees and one metal object where the number of voxels is 54.4 million (voxel sides measure 3.6 mm). Results show that our . usda .gov (a)Orignalimage(b)SilhoueteProbabiltyMap approach reconstructs the complicated branching structure of thin, texture-less objects in the presence of error where intersection-based approaches currently fail. 1
3 0.54912859 34 cvpr-2013-Adaptive Active Learning for Image Classification
Author: Xin Li, Yuhong Guo
Abstract: Recently active learning has attracted a lot of attention in computer vision field, as it is time and cost consuming to prepare a good set of labeled images for vision data analysis. Most existing active learning approaches employed in computer vision adopt most uncertainty measures as instance selection criteria. Although most uncertainty query selection strategies are very effective in many circumstances, they fail to take information in the large amount of unlabeled instances into account and are prone to querying outliers. In this paper, we present a novel adaptive active learning approach that combines an information density measure and a most uncertainty measure together to select critical instances to label for image classifications. Our experiments on two essential tasks of computer vision, object recognition and scene recognition, demonstrate the efficacy of the proposed approach.
4 0.54906201 204 cvpr-2013-Histograms of Sparse Codes for Object Detection
Author: Xiaofeng Ren, Deva Ramanan
Abstract: Object detection has seen huge progress in recent years, much thanks to the heavily-engineered Histograms of Oriented Gradients (HOG) features. Can we go beyond gradients and do better than HOG? Weprovide an affirmative answer byproposing and investigating a sparse representation for object detection, Histograms of Sparse Codes (HSC). We compute sparse codes with dictionaries learned from data using K-SVD, and aggregate per-pixel sparse codes to form local histograms. We intentionally keep true to the sliding window framework (with mixtures and parts) and only change the underlying features. To keep training (and testing) efficient, we apply dimension reduction by computing SVD on learned models, and adopt supervised training where latent positions of roots and parts are given externally e.g. from a HOG-based detector. By learning and using local representations that are much more expressive than gradients, we demonstrate large improvements over the state of the art on the PASCAL benchmark for both root- only and part-based models.
5 0.54839402 43 cvpr-2013-Analyzing Semantic Segmentation Using Hybrid Human-Machine CRFs
Author: Roozbeh Mottaghi, Sanja Fidler, Jian Yao, Raquel Urtasun, Devi Parikh
Abstract: Recent trends in semantic image segmentation have pushed for holistic scene understanding models that jointly reason about various tasks such as object detection, scene recognition, shape analysis, contextual reasoning. In this work, we are interested in understanding the roles of these different tasks in aiding semantic segmentation. Towards this goal, we “plug-in ” human subjects for each of the various components in a state-of-the-art conditional random field model (CRF) on the MSRC dataset. Comparisons among various hybrid human-machine CRFs give us indications of how much “head room ” there is to improve segmentation by focusing research efforts on each of the tasks. One of the interesting findings from our slew of studies was that human classification of isolated super-pixels, while being worse than current machine classifiers, provides a significant boost in performance when plugged into the CRF! Fascinated by this finding, we conducted in depth analysis of the human generated potentials. This inspired a new machine potential which significantly improves state-of-the-art performance on the MRSC dataset.
6 0.52360892 248 cvpr-2013-Learning Collections of Part Models for Object Recognition
7 0.52256161 225 cvpr-2013-Integrating Grammar and Segmentation for Human Pose Estimation
8 0.52245933 446 cvpr-2013-Understanding Indoor Scenes Using 3D Geometric Phrases
9 0.52244884 445 cvpr-2013-Understanding Bayesian Rooms Using Composite 3D Object Models
10 0.52244252 61 cvpr-2013-Beyond Point Clouds: Scene Understanding by Reasoning Geometry and Physics
11 0.52183402 285 cvpr-2013-Minimum Uncertainty Gap for Robust Visual Tracking
12 0.5217818 414 cvpr-2013-Structure Preserving Object Tracking
13 0.52136302 30 cvpr-2013-Accurate Localization of 3D Objects from RGB-D Data Using Segmentation Hypotheses
14 0.521025 325 cvpr-2013-Part Discovery from Partial Correspondence
15 0.52077538 360 cvpr-2013-Robust Estimation of Nonrigid Transformation for Point Set Registration
16 0.52044362 70 cvpr-2013-Bottom-Up Segmentation for Top-Down Detection
17 0.52039808 365 cvpr-2013-Robust Real-Time Tracking of Multiple Objects by Volumetric Mass Densities
18 0.5202949 104 cvpr-2013-Deep Convolutional Network Cascade for Facial Point Detection
19 0.52017385 267 cvpr-2013-Least Soft-Threshold Squares Tracking
20 0.51987755 227 cvpr-2013-Intrinsic Scene Properties from a Single RGB-D Image